+7 989 669 15 15



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




Белим Сергей Викторович *
Кутлунин Павел Евгеньевич **

д.ф.-м.н., профессор *
аспирант**
ОмГУ им. Ф.М. Достоевского, г. Омск


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

Ключевые слова: выделение контуров, поиск границ на изображении.




Библиографическое описание: Белим С.В., Кутлунин П.Е. ИСПОЛЬЗОВАНИЕ АЛГОРИТМА КЛАСТЕРИЗАЦИИ ДЛЯ ВЫДЕЛЕНИЯ КОНТУРОВ НА ИЗОБРАЖЕНИЯХ [Текст] // Перспективы развития научных исследований в 21 веке: сборник материалов 7-й международной науч.-практ. конф., (г. Махачкала, 28 февраля, 2015г.) - Махачкала: Издательство "Апробация", 2015 – C.35-37


Введение Необходимость выделения контуров на цифровых изображениях возникает в процессе решения большого количества задач, связанных с анализом графических объектов. На сегодняшний день большинство алгоритмов выделения контуров основываются на дифференциальных операторах [1, 2]. В качестве альтернативы дифференциальным фильтрам используются статистические методы выделения границ [3, 4] и методы, основанные на вейвлет-преобразованиях [5]. Основным недостатком этих алгоритмов является чувствительность к шуму.

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

1. Постановка задачи и метод её решения

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

Представим изображение в виде множества точек пятимерного пространства RGBXY. Первые три координаты каждой точки определяются цветовыми составляющими пикселя, последние две координаты определяются координатами пикселя на изображении.

Сопоставим построенному множеству точек полносвязный граф. Множество вершин графа будет совпадать с множеством пикселей изображения. Длина ребра будет равна Евклидовому расстоянию между точками в пятимерном пространстве RGBXY. Расстояния между точками vi и vj будем обозначать d(vi,vj). Для выделения односвязных областей одного цвета на изображении выполним кластеризацию построенного графа. Для кластеризации графа используем алгоритм, основанный на построении минимального остовного дерева [6]. Будем использовать жадный алгоритм для построения минимального остовного дерева.

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

Кластеризация состоит в разбиении минимального остовного дерева на поддеревья. Разбиение производится отбрасыванием некоторых рёбер. Из логики алгоритма следует, что к кластеру в первую очередь присоединяются пиксели, расположенные вдоль его границы и имеющие близкий цвет. При исчерпании таких точек, происходит переход на одну из точек, значительно отличающихся по цвету. Такой переход соответствует переходу на новую односвязную область одного цвета.

Для искусственных изображений поиск переходов и кластеризация представляет собой достаточно простую задачу. Для фотографических изображений выделить пики значительно сложнее. Поэтому будем строить иерархию кластеров. Найдём ребро наибольшей длины. Обозначим его длину через R0. Проведём кластеризацию первого уровня, отбросив рёбра, длины которых превышают 0,9R0. При кластеризации k-го уровня отбрасываем рёбра длиной более 0,9kR0.

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

2. Компьютерный эксперимент

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

На рисунке 1 представлено изображения «Перцы» и границы областей полученные для него. Как видно из рисунка уже на четвёртом уровне кластеризации удаётся выделить все основные контуры изображения.

а) исходное изображение, б) контурыРис. 1. Результат работы алгоритма для изображения «Перцы»:

 

      
 а)  б)

Проведём эксперимент с устойчивостью предложенного алгоритма к случайным импульсным шумам. Результаты для изображения «Перцы» представлены на рисунке 2. Как видим, наличие шума приводит лишь к небольшому размытию линии границы.  

 

 

Рис. 2. Устойчивость выделенного контура к случайным импульсным  

шумам: а) изображение, зашумлённое на 10%, б) контуры, выделенные

для зашумлённого изображения.

 

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

3. Обсуждение результатов и выводы

Отличительными особенностями предложенного алгоритма выделения контуров являются устойчивость к влиянию помех и возможность варьирования уровня детализации выделяемых контуров. Из недостатков метода можно отметить несколько большую трудоёмкость по сравнению с дифференциальными фильтрами (O(n) для диффиренциальных фильтров, O(n2) для предложенного алгоритма, где n – количество пикселей на изображении).

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

 

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

  1.    Фисенко В. Т. Компьютерная обработка и распознавание изображений / Фисенко В. Т., Фисенко Т. Ю. // – СПб.: СПбГУ ИТМО, 2008. – 192 с.
  2.   Сойфер В. А. Методы компьютерной обработки изображений – М.: Физматлит, 2003. – 784 с.
  3.    Бондина Н.Н. Использование статистических характеристик для выделения границ в медицинских изображениях / Бондина Н.Н., Кривенцов В.Э. // Вестник НТУ "ХПИ", 2013, № 39 (1012) С.22-27.
  4.    Huang C.P. An Integrated Edge Detection Method Using Mathematical Morphology / Huang C.P., Wang R.Z. // Pattern Recognition and Image Analysis. 2006. V. 16, № 3. P. 406–412.
  5.    Антощук С.Г. Выделение контуров объектов методом двукратного гиперболического вейвлет-преобразования / Антощук С.Г., Бабилунга О.Ю., Николенко А.А. // Електромашинобудування та електрообладнання.      2005. В. 65. С. 65–69.
  6.  Солнцева М.О. Применение методов кластеризации узлов на графах с разрежёнными матрицами смежности в задачах логистики / Солнцева М.О., Кухаренко Б. Г. // Труды МФТИ. 2013. Т. 5, № 3, С. 75-83.
Предстоящие заочные международные научно-практические конференции
A-415
Направления: все научные дисциплины
Прием материалов 31 декабря 2017 г
P-116
Направления: педагогика,психология,культурология
Прием материалов 24 декабря 2017 г.
E-415
Направления: экономика,социология
Прием материалов 24 декабря 2017 г.