Телефон: 8-800-350-22-65
WhatsApp: 8-800-350-22-65
Telegram: sibac
Прием заявок круглосуточно
График работы офиса: с 9.00 до 18.00 Нск (5.00 - 14.00 Мск)

Статья опубликована в рамках: XXXII Международной научно-практической конференции «Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ» (Россия, г. Новосибирск, 26 мая 2015 г.)

Наука: Информационные технологии

Скачать книгу(-и): Сборник статей конференции

Библиографическое описание:
Овцынова В.В. СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ ПОИСКА ГРАНИЦ // Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ: сб. ст. по мат. XXXII междунар. студ. науч.-практ. конф. № 5(31). URL: http://sibac.info/archive/technic/5(31).pdf (дата обращения: 29.03.2024)
Проголосовать за статью
Конференция завершена
Эта статья набрала 0 голосов
Дипломы участников
У данной статьи нет
дипломов

СРАВНИТЕЛЬНЫЙ  АНАЛИЗ  АЛГОРИТМОВ  ПОИСКА  ГРАНИЦ

Овцынова  Виктория  Валерьевна

магистрант  группы  13ИВТ-1мг,  ФБГОУ  ВПО  «Брянский  государственный  технический  университет»,  РФ,  г.  Брянск

Е- mailvovcynova@gmail.com

Буйвал  Александр  Константинович

научный  руководитель,  канд.  техн.  наук,  доц.,  ФБГОУ  ВПО  «Брянский  государственный  технический  университет»,  РФ,  г.  Брянск

 

С  развитием  науки  и  техники  все  больше  технических  устройств  ввода  графической  информации  (фото-  и  видеокамеры)  используют  автоматическое  наведение  и  распознавание  различных  объектов,  в  первую  очередь  лиц  людей.  Но  немаловажным  является  и  определение  местоположения  различных  статических  объектов,  связанное  с  определением  границ  этих  объектов.  Для  решения  задачи  определения  границ  объектов  существует  множество  различных  алгоритмов,  применимость  которых  напрямую  зависит  от  конкретной  прикладной  задачи.

Определение  объектов  и  их  границ  широко  используется  в  робототехнике  для  навигации  роботов.  При  этом  используется  информация  не  только  с  камеры,  но  и  с  других  датчиков.

Существует  достаточно  много  определений  понятия  контур  изображения.  В  общем  случае,  под  контуром  понимают  внешнее  очертание  объекта  на  изображении,  вдоль  которого  происходит  резкое  изменение  яркости.  При  обнаружении  контура  объекта  необходимо  руководствоваться  основными  свойствами,  присущими  любому  контуру:  кривизна  и  компонент.  Первое  частично  определяется  процессом  формирования  изображения  и  может  варьироваться.  Наличие  второго  —  компонент  —  неизбежно,  так  как  большинство  объектов  в  природе  не  имеют  идеально  прямые  края,  в  следствие  чего  возникает  проблема  «разбиения»  контура  на  составляющие  компоненты.  Сам  компонент  представляет  собой  некоторую  часть  контура,  чьи  точки  полностью  соединены  друг  с  другом  отдельными  сегментами  общего  контура.  Каждый  компонент,  в  свою  очередь,  характеризуется  замкнутостью,  которая  определяет  является  ли  последняя  точка  компонента  его  первой  точкой.  Наиболее  сложными  в  обнаружении  являются  контуры,  состоящие  из  множества  компонент  открытого  типа.

Немаловажную  роль  при  определение  контура  объекта  играет  цвет  самого  объекта,  а  так  же  цвета  окружающей  среды.  В  случае,  если  перепады  яркости  и  цвета  будут  незначительными,  обнаружение  границ  объекта  на  изображении  будет  затруднено.  Так  же  свою  лепту  вносят  помехи  на  самом  изображении,  которые  так  же  затрудняют  процесс  обнаружения  краев  объекта  на  изображении.  Поэтому  перед  непосредственным  поиском  границ  объектов  необходимо  провести  некоторые  подготовительные  действия  по  улучшению  качества  изображения.

На  данный  момент  разработано  множество  методов  улучшения  изображений.  При  рассмотрении  этого  процесса  в  контексте  его  использования  в  сфере  робототехники,  стоит  отметить  применимость  специализированных  программных  библиотек  реализующих  алгоритмы  улучшения  изображений.  Эти  библиотеки,  как  и  методы  которые  они  реализуют,  описаны  в  различных  источниках.  Наиболее  эффективным  методом  является  метод  улучшения  гистограммы  изображения  с  помощью  эквализации  (автоматический  метод  поиска  функции  преобразования,  которая  сформирует  изображение  с  равномерной  гистограммой)  [1].  Сама  гистограмма  рассматривается  как  функция  яркости  пикселей  изображения.

Обнаружение  границ  объектов  в  робототехнике  начинается  с  построения  модели,  на  которую  накладывается  изображение  полученное  с  камер.  После  чего  происходит  рендеринг  модели  для  построения  списка  видимых  линий  с  помощью  их  координат.  Поиск  края  наложенного  изображения  происходит  с  помощью  выделения  нормалей  от  линий  модели,  при  этом  необходимо  сузить  угол  поиска  примерно  до  45о.

Обнаружение  самих  краев  объекта  можно  произвести  по  одному  из  ниже  представленных  алгоритмов.

Операторы  Собеля  и  Лапласа

Оператор  Собеля  используется  для  вычисления  приближения  градиента  яркости  изображения.  Он  вычисляет  градиент  яркости  изображения  в  каждой  точке.  Таким  образом  можно  получить  направление  наибольшего  изменения  яркости  и  величину  ее  изменения  по  этому  направлению,  а  следовательно  определить  как  меняется  яркость  изображения  в  каждом  пиксиле,  вероятность  нахождения  точки  на  границе  объекта  и  ее  ориентацию.  Таким  образом  применяя  оператор  Собеля  можно  получить  вектор,  пересекающий  границу  областей  различной  яркости  в  направлении  ее  увеличения  (точка  на  границе  объекта).  Оператор  Собеля  основан  на  свертке  изображения  небольшими  целочисленными  фильтрами  в  вертикальном  и  горизонтальном  направлениях,  поэтому  его  относительно  легко  вычислять.  Оператор  использует  наложение  на  каждую  точку  изображения  двух  масок  вращения.  Эти  маски  представляют  собой  две  ортогональные  матрицы  размерностью  ,  представленные  на  рис.  1.

 

Рисунок  1.  Маски  Собеля

 

Эти  маски  выявляют  границы,  расположенные  вертикально  и  горизонтально  на  изображении.  При  раздельном  наложении  этих  масок  на  изображение  можно  получить  оценку  градиента  по  каждому  из  направлений  Gx,  Gy.  Конечное  значение  градиента  определяется  по  формуле

 

 

Оператор  Лапласа  позволяет,  в  свою  очередь  вычислить  лапласиан  изображения  (сумма  производных  второго  порядка)  путем  умножения  каждого  элемента  двумерной  апертуры    на  соответствующий  элемент  так  называемой  матрицы  Лапласа,  представленной  на  рис.  2.

 

Рисунок  2.  Матрицы  Лапласа

 

Детектор  границ  Canny

Этот  метод  является  самым  популярным  в  использовании  для  реализации  в  компьютерном  зрении.  Сам  алгоритм  выполняется  в  несколько  шагов:

1.  устранение  шума  и  лишних  деталей;

2.  подсчет  градиента  изображения;

3.  уменьшение  толщины  краев  (edge  thinning);

4.  связывание  отдельных  краев  в  контур  (edge  linking).

Детектор  границ  так  же  использует  вышеописанный  оператор  Собеля  для  получения  первой  производной  в  горизонтальном  (Gy)  и  вертикальном  (Gx)  направлениях.  Через  вычисление  этого  градиента  можно  найти  угол  направления  всей  границы.

 

 

После  чего  вычисленный  угол  округляется  до  одного  из  четырех  углов,  представляющих  вертикаль,  горизонталь,  а  так  же  две  диагонали  (как  уже  было  описано  выше,  под  углом  45о).

В  результате  применения  этого  метода  получаются  двоичное  изображение,  содержащие  границы.

Преобразование  Хафа

Этот  метод  используется  для  поиска  линий  и  других  простых  форм  на  изображении.  Преобразование  Хафа  используется  для  поиска  объектов,  принадлежащих  отдельному  классу  фигур  (например,  прямая  или  окружность)  с  использованием  процедур  голосования.

Для  поиска  линий  в  основу  берется  утверждение,  что  абсолютно  любая  точка  изображения  может  являться  частью  некоторого  набора  линий.  Сам  алгоритм  использует  представление  линий  в  полярной  системе  координат,  которое  имеет  следующий  вид

 

 

где:  x  и  y  —  координаты;

f  —  угол  между  перпендикуляром  к  прямой  и  осью  OX;

R  —  длина  нормали  к  прямой  из  начала  координат.

Через  каждую  точку  с  координатами  (x,  y)  на  изображении  можно  провести  несколько  прямых  с  разными  значениями  R  и  f,  таким  образом  каждой  точке  (x,  y)  изображения  соответствует  набор  точек  (R,  f)  в  пространстве,  образующий  синусоиду.

Таблица  1. 

Сравнительная  характеристика  алгоритмов  на  опытных  примерах  c   изображением  куба

Алгоритм

Количество  распознанных  граней  из  5  опытов  (max /min)

Количество  распознанных  граней  из  15  опытов  (max /min)

Количество  распознанных  граней  из  25  опытов  (max /min)

Детектор  Canny,  преобразование  Хафа  (при  настройке  угла  в  270о)

9  /  7

9  /  6

10  /  7

Операторы  Собеля  и  Лапласа  (с  порядком  производной  1)

7  /  6

7  /  6

7  /  6

 

Список  литературы:

1.Вудс  Р.  Цифровая  обработка  изображений.  Издание  3-е,  исправленное  и  дополненное.  /  Р.  Вудс,  Р.  Гонсалес.  М.:  Техносфера,  2012.  —  1104  с.

2.Senthilkumaran  N.A.  Study  on  Edge  Detection  Methods  for  Image  Segmentation  /  N.  Senthilkumaran,  R.  Rajesh  /  Proceedings  of  the  International  Conference  on  Mathematics  and  Computer  Science  (ICMCS-2009).  —  2009.  —  Vol.  1.  —  P.  255—259.

3.Яне  Б.  Цифровая  обработка  изображений.  М.:  Техносфера,  2007.  —  584  с.

4.Yusef  Shafi  S.  Designing  Node  and  Edge  Weights  of  a  Graph  to  Meet  Laplacian  Eigenvalue  Constraints  /  S.  Yusef  Shafi,  Murat  Arcak,  Laurent  El  Ghaoui  /  University  of  California,  Berkeley.

Проголосовать за статью
Конференция завершена
Эта статья набрала 0 голосов
Дипломы участников
У данной статьи нет
дипломов

Оставить комментарий

Форма обратной связи о взаимодействии с сайтом
CAPTCHA
Этот вопрос задается для того, чтобы выяснить, являетесь ли Вы человеком или представляете из себя автоматическую спам-рассылку.