Исследование возможностей распараллеливания алгоритмов выделения контуров объектов по технологии CUDA

АВТОРЕФЕРАТ

Введение

Цели и задачи, которые должны решаться

Актуальность темы работы

Предполагаемая научная новизна

Планируемые практические результаты

Описание некоторых существующих алгоритмов

Решение задачи и результаты исследований

Выводы

Введение

Контурный анализ — совокупность методов выделения, описания и преобразования контуров изображения. Он является важным этапом обработки изображений и распознавания зрительных образов. Контур целиком определяет форму изображения и содержит всю необходимую информацию для распознавания изображений по их форме. Такой подход позволяет не рассматривать внутренние точки изображения и тем самым сократить объем обрерабатываемой информации. Как следствие, это может обеспечить работу системы распознавания в реальном времени. Так же данный подход позволит сократить объем запоминающих устройств системы распознавания.^[1]

Задачи контурного анализа возникают в системе технического зрения при обработке изображений и распознавании зрительных образов. Одной из задач контурного анализа является собственно выделение контуров изображения. Выделенные границы объектов в дальнейшем используются для автоматического нахождения и распознавания объектов, представленных на изображении. Основными потребителями алгоритмов выделения контуров являются системы реального времени. Наиболее популярными представителями таких систем являются системы автоматического контроля качества производимой продукции, а так же системы слежения за соблюдением правил дорожного движения. Такие системы должны точно, а главное, быстро выделять контуры объектов на изображении, а затем классифицировать их и анализировать, либо сравнивать с шаблоном. Для достижения необходимого быстродействия предлагается использовать программно-аппаратную платформу CUDA.

Цели и задачи, которые должны решаться

Целью дипломной работы является исследование возможности реализации алгоритма выделения контуров с использованием технологии CUDA. Среди задач можно выделить следующие:

1. Обзор существующих алгоритмов выделения контуров.
2. Анализ существующих алгоритмов с точки зрения качества выделения и возможности распараллеливания алгоритма.
3. Исследование возможностей технологии CUDA.
4. Выбор алгоритма для реализации, его модификация, обоснование выбора.

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

Актуальность темы работы

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

Следует отметить, что над проблемой выделения контуров работают также ученые разных стран. Например, профессор университета южной Флориды Судеп Саркар, профессор и председатель департамента наук и вычислительной техники Кевин Бауэр (университет Нотр-Дам), доктор, руководитель Дрексельской лаборатории автоматизированных систем Пауль О.

Предполагаемая научная новизна

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

Планируемые практические результаты

В результате планируется создать программную реализацию модифицированного алгоритма, способного эффективно и быстро определять контуры на изображениях. Основным условием для работы предполагаемой программы будет являться наличие видеокарты компании nVidia с технологией CUDA (чипы GeForce серии 6 и выше)^[10] на ПК, с которого будет производиться запуск программы.

Описание некоторых существующих алгоритмов выделения контуров

Метод активных контуров

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

Алгоритм метода заключается в следующем: cначала контур инициализируется в виде некоторой простой линии (например, окружности). Затем производится деформация контура, с целью заключения внутри его области, которая содержит пиксели объекта.

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

E_i = α * E_int(ν_i) + β * E_ext(ν_i)

E_int(ν_i) — функция энергии, зависящая от формы контура.

E_ext(ν_i) — функцией энергии, зависящая от свойств изображения и типа градиента в окрестности точки ν_i.

α и β — константы, обеспечивающие относительную коррекцию величин энергии.

E_i, E_int(ν_i), E_ext(ν_i) являются матрицами. Значение в центре каждой матрицы соответствует энергии контура в отметке ν_i. Каждая отметка ν_i стремится в ν_i', соответствующей положению минимального значения в E_i.

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

Змейки на водоразделе

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

Итеративные алгоритмы змеек (активных контуров) зачастую имеют трудности, связанные с локальным минимумом, так как гибкость энергии функционала на изображении не гарантирована. Чтобы достигнуть общий минимум, при этом избегая нахождения локального, нужно учесть весь набор возможных кривых, и при этом очень быстро выбрать наиболее подходящую. Однако, как правило, число всех возможных имеющихся кривых для объекта на изображении очень велико для быстрого выбора. Оптимальный выход для того, чтобы ускорить процесс минимизации, это исключить ненужные кривые, не упуская важные для нас. Вполне очевидно, что это маловероятно. Наилучший выход — это устранить больше кривых. Трансформация на водоразделе предлагает эффективный способ определения таких нужных и ненужных кривых.^[3]

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

В большинстве случаев, изображения содержат больше, чем только один интересующий объект. Следовательно, необходимо найти несколько решений путем запуска нескольких змеек в изображение. Змейки могут касаться друг друга, но полное перекрывание нежелательно. Это означает, что каждой змейке необходима своя собственная территория для нахождения решения. Достаточная зона для каждой змейки поможет процессу минимизации и снизит временные затраты на вычисление, поскольку обычно эта зона меньше, чем вся область изображения. Зона определяется за счет передвижения каждой точки исходной змейки по оси, которая нормальна к ее касательной. Расстояние, на которое сдвигается, должно быть достаточно велико, чтобы захватить границу объекта в зону змейки.^[4]

Точки на водоразделе в зоне змейки — это предполагаемые точки настоящей границы объекта. Однако, число точек поиска для каждой точки змейки все еще достаточно велико, чтобы справиться за один раз, поэтому предлагается «грубо-точная» стратегия для нахождения решения. Для нахождения удачного решения используются два последовательных процесса минимизации.

Предполагается, что граница объекта будет представлена с помощью n–точек змейки и у нас есть зона змейки, определенная внутренней и внешней кривыми. Рисуется прямая li, которая проходит через точку змейки vi, в направлении перпендикулярной к ее касательной. m точек линии l, которые пересекаются линиями водораздела в зоне змейки — это блуждающие состояния для точки змейки v. Затем грубый процесс минимизации выбирает множество точек среди общего количества блуждающих мест расположения на прямой l, с помощью динамического программирования. Так как  используется минимальное множество точек в зоне, полученный в результате конечный контур может быть не достаточно четким. Некоторые точки находятся на большем расстоянии друг от друга, чем другие из-за грубого округления. Однако, все точки змейки расположены возле настоящей границы объекта. Для более четкого представления контура необходимо слегка переставить эти точки. Берется более специфичную зону, снова используются результаты предыдущего шага. Определена новая зона змейки. Теперь эта зона разделена на n — эквидистантных частей. Наконец, удачный процесс минимизации посредством динамического программирования выбирает то множество точек змейки среди общего количества блуждающих точек (точек водораздела), в соответствующих эквидистантных частях.

Алгоритм, реализующий метод динамического программирования

В рамках данного подхода необходимо найти непрерывную границу Г. При этом рассматриваются различные варианты положения линии границы в окне. Например, в случае, если линия границы делит наше окно сверху вниз, как это показано на рис. 1.8, то , где  — координата Х прохождения границы в i-й строке,   и . Далее используется функционал качества в следующем виде:

где — некоторые оценки значений u и h..

Минимизация L выполняется методом динамического программирования на основе алгоритма, в процессе применения которого происходит оптимальная оценка и самой границы G .^[5]

Решение задач и результаты исследований

Наиболее логичным выбором алгоритма выделения контура является нейросетевой алгоритм, так как нейроны в одном слое нейросети работают независимо друг от друга и являются идеальными кандидатами для вынесения на независимые скалярные процессоры.

Для реализации процедуры выделения контура с помощью нейронной сети была принята следующая модель. На вход нейронной сети подается изображение окна наблюдения размером m Х n. Это изображение удовлетворяет следующим требованиям:

1. Изображение всегда содержит элемент контура, то есть в любом представленном изображении содержится граница перепада яркостей объекта и фона.
2. На изображении только один контур, то есть не предусматривается работа алгоритма с множественными   контурами.
3. На изображении может присутствовать аддитивный гауссов шум, который препятствует правильной работе алгоритма.

На выходе необходимо получить основные параметры прямой, аппроксимирующей границу перепада яркости: u  — интенсивность фона, u + h — интенсивность объекта, d — расстояния от центра окна до прямой, φ  — угол наклона прямой. Данные параметры показаны на рис. 1.

Рисунок 1 — Граница объект/фон в элементарном окне

 

Для реализации этой модели была выбрана нейронная сеть типа многослойный персептрон, так как задача носит явно статистический характер. Сеть содержит два слоя. В первом слое 10 нейронов, во втором 4.^[7] Все искусственные нейроны используют логистическую функцию активации. Архитектура сети изображена на рис. 2.

Рисунок 2 — Нейронная сеть

 

Следует обратить особое внимание на первое требование к окну изображения. Так как окна, подаваемые на нейросеть, должны обязательно содержать часть границы, и при том только одну (требование 2), то необходимо каким-либо образом эти окна найти. Одним из вариантов решения этой задачи является нахождение предварительного контура более быстрым и грубым методом. Затем найденное приближение контура разбивается на участки, которые уточняются на нейросети. Кроме того, отдельной задачей является сбор разрозненных участков контуров в один непрерывный контур. Решить эту задачу можно, к примеру, находя среднюю точку между двумя крайними точками аппроксимирующей прямой у двух соседних окон.^[8] Процесс нахождения границ схематично показан на рисунке 3.

Рисунок 3 — Процесс нахождения границ изображения

Анимация создана в среде Adobe PhotoShop CS2; состоит из 6 кадров с задержкой 1с между кадрами; количество циклов воспроизведения ограничено 10ю; объем анимации — 27 Кб, размер 250х250 пикселей

 

В качестве алгоритма предварительного определения контуров выбрана комбинация из нескольких этапов алгоритма Canny, а именно:

Шаг 1. Первым шагом является фильтрация шума в исходном изображении. Фильтр Гаусса можно вычислить с помощью простой маски. После того как подходящая маска была рассчитана, сглаживание Гаусса может быть выполнено с помощью стандартных методов свертки. Маски свертки, как правило, гораздо меньше, чем само изображение. В результате, маска двигается над изображением, манипулируя квадратом пикселей за один раз. Чем больше ширина маски Гаусса, тем меньше чувствительность детектора к шуму. Локализация ошибки в обнаружении краев так же немного увеличивается с увеличением ширины Гауссиана.^[9]

Шаг 2. Нахождение края силы путем взятия градиента изображения. Оператор Собеля выполняет 2-D пространственное измерение градиента в изображении. Тогда приближенные градиенты абсолютных величин (края сил) в каждой точке может быть найдено. Оператор Собеля использует пару 3x3 масок свертки: оценки градиента в направлении х (столбцы) и оценки градиента в Y-направлении (строк).

Величина, или край силы, градиента затем аппроксимируется по формуле: |G| = |Gx| + |Gy|

Шаг 3. Гистерезис используется в качестве средства устранения полос. Полоса — это разбиение контура края, вызванное оператором выходного колебания выше и ниже порогового уровня. Если единственный порог, T1 применяется к изображению и край имеет среднюю силу, равную T1, то из-за шума, будут случаи, когда край опускается ниже порогового уровня. В равной степени он будет также распространяться выше порога принятия края, похожего на пунктирную линию. Чтобы избежать этого, гистерезис использует 2 порога, высокий и низкий. Любой пиксель в изображении, который имеет значение большее, чем T1 предположительно является краевым пикселем, и немедленно обозначается как таковой. Затем, любые пиксели, которые соединяются с этим краевым пикселем, и которые имеют значение, большее, чем T2, также выбираются как краевые пиксели. Для начала движения вдоль края необходим градиент T2, а для окончания — градиент ниже T1.^[6]

Этот алгоритм также может быть распараллелен для расчета на программно-аппаратном комплексе CUDA путем разбиения изображения на участки и расчет этих участков на разных процессорах.

В итоге все изображение разбивается на окна размером m X n, пригодные для обработки нейросетью, но обработке подвергаются только те из них, которые содержат ровно один участок контура.

Выводы

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

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

1. Фурман Я.А., Юрьев А.Н., Яншин В.В. Цифровые методы обработки и распознавания бинарных изображений. — Красноярск, 1992. — 248с. — http://www.4tivo.com/education/2329-cifrovye-metody-obrabotki-i.html^[↑]
2. Блонкин А.В. Преобразование растр-вектор изображений сосудов» // Материалы X Международной конференции «Системы проектирования, технологической подготовки производства и управления этапами жизненного цикла промышленного продукта CAD/CAM/PDM». — Институт проблем управления российской академиии наук, Москва, 2006. — http://lab18.ipu.rssi.ru/projects/conf2006/1/... ^[↑]
3. Williams D.J., Shah M. A Fast Algorithm for Active Contours and Curvature Estimation. — Computer Vision, Graphics and Image Processing, vol.55, 1992. — pages.cs.wisc.edu/~dyer/ai-qual/williams-cvgip92.pdf ^[↑]
4. Kaas M., Witkin A. Terzopoulos D. Snakes: Active Contour Models. — Int. Journal of Computer Vision, vol.1, no.4, 1987. — www.cs.ucla.edu/~dt/papers/ijcv88/ijcv88.pdf ^[↑]
5. Перов А.И., Соколов Г.Г. Алгоритм последовательного выделения контура объекта на двумерных цифровых изображениях // Научный журнал Воронежского государственного университета. Серия: Радиотехника, №7,1998. — www.vestnik.vsu.ru/pdf/analiz/2008/01/sirota_2.pdf ^[↑]
6. Green B. Canny Edge Detection Tutoria // Drexel Autonomous Systems Lab., 2002. — http://www.pages.drexel.edu/~weg22/can_tut.html ^[↑]
7. Сирота А.А., Соломатин А.И. Статистические алгоритмы обнаружения границ объектов на изображениях. — Воронеж: Вестник ВГУ, № 1, 2008. — www.vestnik.vsu.ru/.../sirota_2.pdf^[↑]
8. Чудовская А.К. Возможности распараллеливания алгоритмов выделения контура по технологии CUDA // Искусственный интеллект.— Донецк: ІПШІ МОН і НАН України “Наука і освіта”, 2010.
9. Прэтт У. Цифровая обработка изображений, том 2 — Москва: Мир, 1982 — 478с.
10. Лосев С. Перспективы параллельных вычислений на GPU от Nvidia — Hard’n’Soft, №6 — 2009. — www.nvidia.eu/cuda/files/HardnSoft_026_027_trends_Cuda.pdf

При написании данного реферата, магистерская работа еще не завершена. Окончательное завершение: декабрь 2010 года. Полный текст работы и все материалы по теме могут быть получены у автора или его руководителя после указанной даты.

Автобиография

Автореферат

Библиотека

Ссылки

Отчет о поиске

Инд.раздел