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



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


Авторы: Muthukrishnan R, Radha M.

Источник: International Journal of Computer Science & Information Technology (IJCSIT), 3(6). — С. 259–267.


Аннотация

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

Введение

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

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

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

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

Сегментация изображений

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

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

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

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

Алгоритмы выделение границ

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

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

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

В технической литературе приведено и описано большое количество алгоритмов выделения контуров и границ. В данной работе рассмотрены наиболее популярные методы. К ним относятся: оператор Робертса, Собеля, Превитта, Кирша, Робинсона, алгоритм Канни и LoG-алгоритм.

Оператор Робертса

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

Оператор Собеля

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

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

Оператор Превитта

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

Оператор Кирша

Обнаружение границ этим методом было введено Киршем в 1971 году. Алгоритм основан на использовании всего одной маски, которую вращают по восьми главным направлениям: север, северо-запад, запад, юго-запад, юг, юго-восток, восток и северо-восток. Маски имеют следующий вид:

Величина границы определена как максимальное значение, найденное с помощью маски. Определенное маской направление выдает максимальную величину. Например, маска k0 соответствует вертикальной границе, а маска k5 — диагональной. Можно также заметить, что последние четыре маски фактически такие же, как и первые, они являются зеркальным отражением относительно центральной оси матрицы.

Оператор Робинсона

Метод Робинсона, введенное в 1977, подобен методу Кирша, но является более простым в реализации в силу использования коэффициентов 0, 1 и 2. Маски данного оператора симметричны относительно центральной оси, заполненной нулями. Достаточно получить результат от обработки первых четырех масок, остальные же можно получить, инвертируя первые.

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

Выделение контура методом Marr-Hildreth

Marr-Hildreth (1980) метод — метод обнаружения границ в цифровых изображениях, который обнаруживает непрерывные кривые везде, где заметны быстрые и резкие изменения яркости группы пикселей. Это довольно простой метод, работает он с помощью свертки изображения с LoG-функцией или как быстрая аппроксимация с DoG. Нули в обработанном результате соответствуют контурам. Алгоритм граничного детектора состоит из следующих шагов:

Выделение контура методом LoG

Алгоритм выделения контуров Лаплассиан Гауссиана был предложен в 1982 году. Данный алгоритм является второй производной, определенной как:

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

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

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

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

Алгоритм:

В отличии от операторов Робертса и Собеля, алгоритм Канни не очень восприимчив к шуму на изображении.

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

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

Все описанные алгоритмы были реализованы в программной среде MATLAB R2009a и протестированы на фотографии университета. Цель эксперимента заключается в получении обработанного изображения с идеально выделенными контурами. Оригинальное изображение и результаты его обработки представлены на рисунке 1.

Оригинальное изображение и результат работы различных алгоритмов выдеоения контуров

Рисунок 1 — Оригинальное изображение и результат работы различных алгоритмов выдеоения контуров


При анализе полученных результатов были выявлены следующие закономерности: операторы Робертса, Собеля и Превитта дают очень различные результаты. Marr-Hildreth, LoG и Канни практически одинаково обнаружили контуры объекта, Кирш и Робинсон дали такой же результат. Но наблюдая полученные результаты можно сделать вывод, что алгоритм Канни справляется на порядок лучше других.

Выводы

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

В данной статье была предпринята попытка изучить на практике методы выделения контуров объектов, основанных на разрывах яркости полутонового изображения. Исследование относительной производительности каждого из приведенных в данной статье методов осуществлялся с помощью программного средства MATLAB. Анализ результатов обработки изображения показал, что такие методы, как Marr-Hildreth, LoG и Канни дают практически одинаковые результаты. Но все же при обработке данного тестового изображения наилучшие результаты можно наблюдать после работы алгоритма Канни, хотя при других условиях лучшим может оказаться другой метод.

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


Список использованной литературы

1. Canny J.F. (1983) Finding edges and lines in images, Master's thesis, MIT. AI Lab. TR-720.
2. Canny J.F. (1986) A computational approach to edge detection, IEEE Transaction on Pattern Analysis and Machine Intelligence, 8. — P. 679–714.
3. Courtney P, Thacker N.A. (2001) Performance Characterization in Computer Vision: The Role of Statistics in Testing and Design, Chapter in: Imaging and Vision Systems: Theory, Assessment and Applications, Jacques Blanc-Talon and Dan Popescu (Eds.), NOVA Science Books.
4. Hanzi Wang (2004) Robust Statistics for Computer Vision: Model Fitting, Image Segmentation and Visual Motion Analysis, Ph.D thesis, Monash University, Australia.
5. Huber P.J. (1981) Robust Statistics, Wiley New York.
6. Kirsch R. (1971) Computer determination of the constituent structure of biological images, Computers and Biomedical Research, 4. — P. 315–328.
7. Lakshmi S, Sankaranarayanan V. (2010) A Study of edge detection techniques for segmentation computing approaches, Computer Aided Soft Computing Techniques for Imaging and Biomedical Applications. — P. 35–41.
8. Lee K., Meer P. (1998) Robust Adaptive Segmentation of Range Images, IEEE Trans. Pattern Analysis and Machine Intelligence, 20(2). — P. 200–205.
9. Marr D, Hildreth E. (1980) Theory of edge detection, Proc. Royal Society of London, B, 207. — P. 187–217.
10. Marr D. (1982) Vision, Freeman Publishers.
11. Marr P., Doron Mintz. (1991) Robust Regression for Computer Vision: A Review, International Journal of Computer Vision, 6(1). — P. 59–70.
12. Orlando J. Tobias, Rui Seara (2002) Image Segmentation by Histogram Thresholding Using Fuzzy Sets, IEEE Transactions on Image Processing, Vol.11, No.12. — P. 1457–1465.
13. Punam Thakare (2011) A Study of Image Segmentation and Edge Detection Techniques, International Journal on Computer Science and Engineering, Vol 3, No.2. — P. 899–904.
14. Rafael C., Gonzalez, Richard E. Woods, Steven L. Eddins (2004) Digital Image Processing Using MATLAB, Pearson Education Ptd. Ltd, Singapore.
15. Ramadevi Y. (2010) Segmentation and object recognition using edge detection techniques, International Journal of Computer Science and Information Technology, Vol 2, No.6. — P. 153–161.
16. Roberts L. (1965) Machine Perception of 3-D Solids, Optical and Electro-optical Information Processing, MIT Press.
17. Robinson G. (1977) Edge detection by compass gradient masks, Computer graphics and image processing, 6. — P. 492–501.
18. Rousseeuw P. J., Leroy A. (1987) Robust Regression and outlier detection, John Wiley & Sons, New York.
19. Senthilkumaran N., Rajesh R. (2009) Edge Detection Techniques for Image Segmentation — A Survey of Soft Computing Approaches, International Journal of Recent Trends in Engineering, Vol. 1, No. 2. — P. 250–254.
20. Sowmya B., Sheelarani B. (2009) Colour Image Segmentation Using Soft Computing Techniques, International Journal of Soft Computing Applications, Issue 4. — P. 69–80.
21. Umesh Sehgal (2011) Edge detection techniques in digital image processing using Fuzzy Logic, International Journal of Research in IT and Management, Vol.1, Issue 3. — P. 61–66.
22. Yu, X, Bui, T.D. & et al. (1994) Robust Estimation for Range Image Segmentation and Reconstruction, IEEE trans. Pattern Analysis and Machine Intelligence, 16 (5). — P. 530–538.