ДонНТУ   Портал магистров

Реферат по теме выпускной работы

Содержание

Введение

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

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

Актуальность

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

и служит для облегчения проблемы логической группировки пикселей изображения.

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

Приведем примеры некоторых практических применений сегментации:

Цель работы

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

Задачи

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

Предполагаемые результаты

В результате работы планируется получить:

Новизна

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

Обзор аналогичных исследований

Магистрантами ДонНТУ ранее проводились исследования по изучению сегментации изображений. Депутат Е. В., Скобцов Ю. А. [14] исследовали возможность сегментации изображений с помощью алгоритма муравьиных колоний. Савченко Д.А. [15] также исследовал методы сегментации изображений. Чудовская А.К. [16] проводила исследования по реализации алгоритма выделения контуров Кэнни с использованием технологии NVidia CUDA.

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

Одни из ранних исследований проводили 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. Время работы разработанного алгоритма линейно зависит от размерности входных данных.

Классификация существующих алгоритмов

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

Одна из классификаций алгоритмов разделяет существующие методы на следующие подмножества (рисунок 1) [5]:

Схема классификации алгоритмов сегментации

Рисунок 1 - Схема классификации алгоритмов сегментации. Анимация - 8 кадров, задержка 500 мс, 3000 мс для последнего кадра

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

Алгоритмы из данной группы могут давать неточные результаты, особенно при высоком уровне шума на изображении, что требует дополнительной пред- или пост-обработки изображения [7].

Простейшее преобразование — бинаризация. Она представляет собой операцию порогового разделения, которая в результате дает бинарное изображение. Целью операции бинаризации является радикальное уменьшение количества информации, содержащейся на изображении. В процессе бинаризации исходное полутоновое изображение, имеющее некое количество уровней яркости, преобразуется в черно-белое изображение, пиксели которого имеют только два значения – 0 и 1.

Различают несколько видов пороговой обработки:

Алгоритмы выделения краев позволяют обозначить границы элементов на изображении. Наиболее известным таким алгоритмом является детектор краёв Кэнни (Canny edge detector) [6]

Основные шаги алгоритма:

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

Алгоритмы извлечения областей оперируют таким понятием как «регион» или «область», а также «семя» — изначально заданный пиксель, из которого в последствии вырастает область. Изначально задается несколько центров («семян») регионов на изображении и далее происходит рост этих регионов за счет поглощения соседних пикселей. Подобные алгоритмы в качестве входных данных требуют указания центров регионов для более качественной сегментации. [13]

Метод разрастания областей из семян требует дополнительного ввода. Результат сегментации зависит от выбора семян. Шум на изображении может вызвать то, что семена плохо размещены. Метод разрастания областей без использования семян — это изменённый алгоритм, который не требует явных семян. В качестве меры близости пикселей используется интенсивность пикселя и средняя интенсивность по региону δ.

Алгоритм начинает с одной области A1 — пиксель, выбранный здесь, незначительно влияет на конечную сегментацию. На каждой итерации алгоритм рассматривает соседние пиксели так же, как метод разрастания областей с использованием семян. Но метод разрастания областей отличается тем, что если минимальная δ не меньше, чем заданный порог T, то пиксель добавляется в соответствующую область Aj. В противном случае пиксель считается сильно отличающимся от всех текущих областей Ai и создаётся новая область An+1, содержащая этот пиксель.

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

Для того чтобы избавиться от зависимости от начальных значений и автоматизировать алгоритм, можно включить в него некоторую статистическую информацию и априорные значения. Например, критерий однородности, который был предложен Pohle Toennies [7], делает алгоритмы адаптируемыми к различным значениям начальных точек.

Алгоритм, использующий квадродеревья, берет в качестве корня дерева всё изображение и если оно не является однородным, то происходит процесс разбиения изображения на 4 области — дочерние узлы корня. Для сыновей повторяется аналогичный процесс. В свою очередь, если 4 сына однородны, то они объединяются (процесс слияния) в один узел. Процесс повторяется рекурсивно до тех пор, пока возможно выполнить разбиение и слияние.

Алгоритм роста регионов

Главная цель сегментации — это разделение изображения на регионы.

Базовые положение алгоритма сегментации (рисунок 2)

Основные положения алгоритма роста регионов

Рисунок 2 - Основные положения алгоритма роста регионов

a) сегментация должна быть полной, т. е. каждый пиксель изображения должен принадлежать какому-либо региону;

b) все пиксели в регионе должны быть объединены с помощью заранее определенного правила (предиката);

c) регионы должны быть непересекающимися;

d) все пиксели в регионе должны иметь одинаковое (приблизительно одинаковое) значение свойства, по которому выполняется сегментация;

e) свойства пикселей в смежных регионах должны значительно отличаться друг от друга.

Базовые концепции исходных точек

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

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

При выборе свободного пикселя для анализа можно использовать методы 4 или 8 соседей (рисунок 3).

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

Рисунок 3 - Схема выбора следующего пикселя для анализа

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

Список источников

  1. Blasiak Anna. A Comparison of Image Segmentation Methods. Электронный ресурс. Режим доступа http://dspace.nitle.org/bitstream/handle/10090/781/s10csci2007blasiak.pdf?sequence=1 свободный. – Загл. с экрана. – Яз. англ.
  2. Wassenberg Jan. Middelmann Wolfgang, Sanders Peter. An Efficient Parallel Algorithm for Graph-Based Image Segmentation. Электронный ресурс. Режим доступа http://algo2.iti.kit.edu/wassenberg/wassenberg09parallelSegmentation.pdf свободный. - Загл. с экрана. – Яз. англ.
  3. Pantofaru Caroline, Hebert Martial. A Comparison of Image Segmentation Algorithms. Режим доступа http://www.ri.cmu.edu/pub_files/pub4/pantofaru_caroline_2005_1/pantofaru_caroline_2005_1.pdf свободный. - Загл. с экрана. – Яз. англ.
  4. Zhen Ma, João Manuel R. S. Tavares, R. M. Natal Jorge. A review on the current segmentation algorighms for medical images. Режим доступа http://repositorio-aberto.up.pt/bitstream/10216/7125/2/17022.pdfhttp://repositorio-aberto.up.pt/bitstream/10216/7125/2/17022.pdf свободный. – Загл. с экрана. – Яз. англ.
  5. Поршнев С.В., Левашкина А. О. Универсальная классификация алгоритмов сегментации изображений. Электронный ресурс. Режим доступа http://jurnal.org/articles/2008/inf23.html свободный.
  6. Canny, J. A Computational Approach to Edge Detection. Ээлектронный ресурс. Режим доступа http://www.limsi.fr/Individu/vezien/PAPIERS_ACS/canny1986.pdf свободный. - Загл. с экрана. – Яз. англ.
  7. Pohle, R., Toennies, K. D. Segmentation of Medical Images Using Adaptive Region Growing. Электронный ресурс. Режим доступа http://wwwisg.cs.uni-magdeburg.de/bv/pub/pdf/mi_4322_153.pdf свободный. - Загл. с экрана. – Яз. англ.
  8. Alireza Khotanzad, Abdelmajid Bouarfa. Image segmentation by a perallel, non- parametric histogram based clustering algorithm. Электронный ресурс. Режим доступа http://www.cs.gsu.edu/~wkim/index_files/papers/imagesegmentation.pdf свободный. - Загл. с экрана. – Яз. англ.
  9. Brian Fulkerson, Stefano Soatto. Really quick shift: Image segmentation on a GPU. Электронный ресурс. Режим доступа http://www.vision.ucla.edu/papers/fulkersonS10really.pdf свободный. – Загл. с экрана. – Яз. англ.
  10. Nawal Copty , Sanjay Ranka , Geo rey Fox , Ravi V. Shankar. A Data Parallel Algorithm for Solving the Region Growing Problem on the Connection Machine. Режим доступа http://www.new-npac.org/users/fox/pdftotal/sccs-0596.pdf свободный. – Загл. с экрана. – Яз. англ.
  11. Lucas Lattari, Anselmo Montenegro, Aura Conci, Esteban Cluaa, Virginia Mota, Marcelo Bernardes Vieirab, Gabriel Lizarragac. Using graph cuts in GPUs for color based human skin segmentation. Режим доступа http://pire.fiu.edu/publications/Graph_Cuts_2011.pdf свободный. – Загл. с экрана. – Яз. англ.
  12. Shahram Rahimi, M. Zargham, A. Thakre. A Parallel Fuzzy C-Mean algorithm for Image Segmentation. Режим доступа http://opensiuc.lib.siu.edu/cs_pubs/26/ свободный. – Загл. с экрана. – Яз. англ.
  13. Frank Y. Shih, Shouxian Cheng, Automatic seeded region growing for color image segmentation. Электронный ресурс. Режим доступа http://www.csd.uoc.gr/~hy471/papers/AutomaticSRGColor.pdf свободный. – Загл.с экрана. – Яз. англ.
  14. Депутат Е. В., Скобцов Ю. А, Сегментация медицинских изображений с помощью алгоритма муравьиных колоний., Информационные управляющие системы и компьютерный мониторинг 2010/ Сборник материалов к I Всеукраинской научно-технической конференции студентов, аспирантов и молодых ученых.- Донецк, ДонНТУ-2010, с.12-16.
  15. Савченко Д. А., Исследование методов сегментации изображений, Режим доступа http://masters.donntu.ru/2010/fknt/savchenko/diss/index.htm свободный. – Загл.с экрана.
  16. Чудовская А.К., Исследование возможностей распараллеливания алгоритмов выделения контуров объектов по технологии CUDA, Режим доступа http://masters.donntu.ru/2010/fknt/chudovskaja/diss/index.htm свободный. – Загл.с экрана.