Автор: Комаричев М.Е., Зори С.А.
Источник: Інформаційні управляючі системи та комп’ютерний моніторинг (ІУС-2012) / Матерiали III мiжнародної науково-технiчної конференцiї студентiв, аспiрантiв та молодих вчених. — Донецьк, ДонНТУ — 2012, Электронный сборник, с. 495 - 500.
Комаричев М.Е., Зори С.А. Сегментация изображений на параллельных вычислительных системах. Рассмотрены задачи и области применения сегментации изображений, классифицированы алгоритмы сегментации, сделаны выводы об актуальности и возможности сегментации изображений с использованием параллельных вычислительных систем.
Одной из основных задач в области компьютерного зрения является задача извлечения информации и знаний из изображений. Сегментация — это процесс разбиения изображения на сегменты (кластеры, суперпиксели), которые представляют собой множества пикселей, объединенные по тем или иным признакам. Сегментация позволяет уменьшить объем информации на изображении и облегчить его анализ. Кроме того, решение задачи сегментации изображений является ключевым для многих других задач и методов компьютерного зрения, таких как:
и служит для облегчения проблемы логической группировки пикселей изображения.
В некоторых предметных областях возникают трудности с определением правил, по которым выполняется сегментация, к тому же после определения оптимального правила сегментации возникает множество вычислительных проблем связанных с нахождением необходимой сегментации.
Приведем примеры некоторых практических применений сегментации:
Для сегментации изображений было разработано несколько универсальных алгоритмов. Так как общего решения для задачи сегментации изображений не существует, часто эти методы приходится совмещать со знаниями из предметной области, для более эффективного решения задачи в конкретной предметной области.
Одна из классификаций алгоритмов разделяет существующие методы на следующие подмножества [5]:
Алгоритмы пороговой обработки достаточно просты в реализации. Порог — это признак (свойство), которое помогает разделить искомый сигнал на классы. Операция порогового разделения заключается в сопоставлении функции (к примеру функция может возвращать яркость пикселя) для каждого пикселя изображения с заданным значением порога.
Алгоритмы из данной группы могут давать неточные результаты, особенно при высоком уровне шума на изображении, что требует дополнительной пред- или пост-обработки изображения [7].
Простейшее преобразование — бинаризация. Она представляет собой операцию порогового разделения, которая в результате дает бинарное изображение. Целью операции бинаризации является радикальное уменьшение количества информации, содержащейся на изображении. В процессе бинаризации исходное полутоновое изображение, имеющее некое количество уровней яркости, преобразуется в черно-белое изображение, пиксели которого имеют только два значения – 0 и 1.
Различают несколько видов пороговой обработки:
Алгоритмы выделения краев позволяют обозначить границы элементов на изображении. Наиболее известным таким алгоритмом является детектор краёв Кэнни (Canny edge detector) [6]
Основные шаги алгоритма:
Как следствие того, что группа этих алгоритмов работает с отдельными пикселями, возникает недостаток — возможны разрывы в найденных границах, что требует некоторой постобработки для устранения неточностей.
Алгоритмы извлечения областей оперируют таким понятием как «регион» или «область», а также «семя» — изначально заданный пиксель, из которого в последствии вырастает область. Изначально задается несколько центров («семян») регионов на изображении и далее происходит рост этих регионов за счет поглощения соседних пикселей. Подобные алгоритмы в качестве входных данных требуют указания центров регионов для более качественной сегментации. [13]
Метод разрастания областей из семян требует дополнительного ввода. Результат сегментации зависит от выбора семян. Шум на изображении может вызвать то, что семена плохо размещены. Метод разрастания областей без использования семян — это изменённый алгоритм, который не требует явных семян. В качестве меры близости пикселей используется интенсивность пикселя и средняя интенсивность по региону δ.
Алгоритм начинает с одной области A1 — пиксель, выбранный здесь, незначительно влияет на конечную сегментацию. На каждой итерации алгоритм рассматривает соседние пиксели так же, как метод разрастания областей с использованием семян. Но метод разрастания областей отличается тем, что если минимальная δ не меньше, чем заданный порог T, то пиксель добавляется в соответствующую область Aj. В противном случае пиксель считается сильно отличающимся от всех текущих областей Ai и создаётся новая область An+1, содержащая этот пиксель.
Алгоритм роста регионов [13] также является типичным представителем алгоритмов, использующих регионы. После выбора начальных позиций алгоритм начинает искать соседние пиксели, интенсивности которых лежат в интервалах, определенных порогами и затем объединяют их, чтобы расширить регион.
Для того чтобы избавиться от зависимости от начальных значений и автоматизировать алгоритм, можно включить в него некоторую статистическую информацию и априорные значения. Например, критерий однородности, который был предложен Pohle Toennies [7], делает алгоритмы адаптируемыми к различным значениям начальных точек.
Алгоритм, использующий квадродеревья, берет в качестве корня дерева всё изображение и если оно не является однородным, то происходит процесс разбиения изображения на 4 области — дочерние узлы корня. Для сыновей повторяется аналогичный процесс. В свою очередь, если 4 сына однородны, то они объединяются (процесс слияния) в один узел. Процесс повторяется рекурсивно до тех пор, пока возможно выполнить разбиение и слияние.
Сегментация изображений зачастую является первым шагом перед применением алгоритмов обработки изображений более высокого уровня. При необходимости выполнения обработки в режиме реального времени возникает проблема с производительностью программной системы, выполняющей сегментацию. Это связано с тем, что алгоритмы работают с отдельными пикселями и количество операций достаточно велико. Для преодоления этой проблемы необходимо выполнять сегментацию параллельно с использованием нескольких вычислительных узлов. В настоящее время активно ведутся исследования по распараллеливанию алгоритмов сегментации.
Одни из ранних исследований проводили Alireza Khotanzad и Abdel Majud Bouarfa . Их работа [8] посвящена сегментации изображений с использованием порогового алгоритма кластеризации. В результате их работы было получено восьмикратное ускорение работы алгоритма при использовании 11 процессоров.
В исследованиях, проведенных Shahram Rahimi, M. Zargham и A. Thakre [12], рассматривается возможность распараллеливания алгоритма C-Mean, использующего нечеткое разбиение пикселей на кластеры. Было достигнуто девятикратное ускорение при эффективности близкой к единице. В ходе исследований была выявлена прямопропорциональная зависимость между количеством процессоров и приростом скорости сегментации изображения.
Исследования Nawal Copty, Sanjay Ranka, Geo rey Fox, Ravi V. Shankar [10] также показывают хорошие результаты при распараллеливании алгоритма роста регионов. Исследования проводились с использованием вычислительной системы, построенной с архитектурой MIMD. В результате также замечен значительный рост скорости обработки при использовании большого числа вычислительных узлов.
В работе Jan Wassenberg, Wolfgang Middelmann и Peter Sanders [2] описали алгоритм сегментации на графах с использованием вычислительной системы с архитектурой SMP. Время работы разработанного алгоритма линейно зависит от размерности входных данных.
В ходе работы планируется исследование возможности эффективной реализации алгоритмов сегментации на графических параллельных мультипроцессорах видеокарт ПК с использованием технологии NVIDIA CUDA. Преимущества использования технологии NVIDIA CUDA:
Как видно, технология NVIDIA CUDA привлекательна как для разработчика (по причине использования популярного языка и наличие мощных библиотек), так и для потенциального пользователя системы сегментирования с использованием параллельных вычислительных технологий (по причине дешевизны оборудования и скорости разработки).
Исследования показали, что существует достаточно много алгоритмов для сегментации изображений и их всевозможных модификаций. Алгоритмы допускают корректировки для применения в конкретных прикладных областях.
Существующие алгоритмы сегментации можно условно разбить на 3 класса:
В некоторых прикладных областях, таких как обработка спутниковых снимков, обработка аэрофотоснимков, а также в обработке медицинских изображений, используются изображения высокого разрешения, а некоторые задачи требуют обработки изображений в режиме реального времени.
Алгоритмы сегментации требуют обработки каждого пикселя изображения, что приводит к росту требований к вычислительным мощностям. Исследование возможности реализации существующих алгоритмов на параллельных вычислительных системах позволит решить существующие проблемы и увеличить скорость обработки изображений.
Технология NVIDIA CUDA является привлекательной как для разработчиков - использование популярного языка, наличие мощных библиотек, так и для потенциального пользователя системы сегментирования с использованием параллельных вычислительных технологий — дешевизна оборудования и скорость разработки.