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

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

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

Используемый алгоритм  Границы на изображении – это кривые, ограничивающие односвязные области одного цвета. Алгоритм ищет границы в два этапа. На первом этапе на изображении выделяются односвязные области одного цвета. На втором этапе ищутся кривые, ограничивающие данные области. Набор пикселей исходного изображения преобразуется в множество точек векторного пространства RGBXY (три цветовые координаты и две пространственные). Цветовые координаты каждой точки нормализуются.

Построенному множеству точек сопоставляется полносвязный граф. Длина ребра равна Евклидовому расстоянию между точками в пятимерном пространстве RGBXY. Для выделения односвязных областей одного цвета на изображении выполняется кластеризация построенного графа. Для кластеризации графа используем алгоритм, основанный на построении минимального остовного дерева (для его построения используется жадный алгоритм). При кластеризации минимальное остовное дерево разбивается на поддеревья. Разбиение производится отбрасыванием рёбер, превышающих некоторую длину на определённом шаге алгоритма. Для этого удаляются рёбра больше некоторого порога t = r_coefficient^iter * MAX_DISTANCE, где r_coefficient принадлежит (0, 1), MAX_DISTANCE – максимальное расстояние между двумя точками, iter – номер итерации. После удаления рёбер с весом, превышающим t, дерево разбивается на поддеревья, представляющие собой односвязные области на изображении.

В алгоритме также выполняется проверка, что размер полученных кластеров после разбиения превышает некоторый порог minimum_cluster_size; если размер кластера меньше данного порога, ребро, удаление которого привело к такому разбиению, не удаляется. Таким образом, на каждой новой итерации алгоритм производит более глубокую кластеризацию. Процесс кластеризации останавливается при t < percent * MAX_DISTANCE.

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

Алгоритм разработан Кутлуниным П.Е. и Белимом С.В.. Подробное описание алгоритма можно найти в статье [1].

[1] Белим С.В., Кутлунин П.Е. Выделение контуров на изображениях с помощью алгоритма кластеризации // Компьютерная оптика. - 2015. Т. 39, № 4. - С. 119-124].

На вход программе подаётся 5 обязательных параметров:

1) file_name - путь к изображению, которое необходимо разбить на односвязные области;

2) r_coefficient - коээфициент уменьшения расстояния между рёбрами. Рёбра, превышающие значение r_coefficient * MAX_DISTANCE на очередной итерации, удаляются из дерева, тем самым распадаясь на поддеревья, представляющие собой односвязные области на исходном изображении. MAX_DISTANCE - максимальное расстояние между двумя рёбрами в исходном остовном дереве;

3) percent - процент от MAX_DISTANCE, при достижении значения которого алгоритм останавливает свою работу;

4) minimum_cluster_size - ограничение на минимальное количество пикселей в односвязной области;

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

После запуска программы в директории расположения программы будет создан файл с результатом работы программы с названием %original_name%_bounds.bmp, где original_name – название исходного файла file_name без расширения.

Результатом работы программы является изображение с выделенными границами областей (белый фон и чёрные границы).

Инструментальные средства создания  программа написана на языке Java. Для написания использовались стандартные библиотеки классов JDK, в том числе классы из пакетов java.awt и javax.imageio для работы с изображениями.

Вложение  прикреплён архив иboundsearchresults.zip, в котором представлены результаты работы программы для искусственных и фотографических изображений (всего 3 изображения). Программа запускалась со следующими параметрами: r_coefficient=0,8; percent=10; minimum_cluster_size=30; color_intervals=16.