Разбиение изображений на односвязные области с помощью алгоритма кластеризации

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

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

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

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

Для изображения ищется самый популярный интервал цветов. На изображении находится точка, попадающая в самый популярный интервал цветов, и имеющая одну соседнюю точку такого же цвета. Данная точка выбирается в качестве начальной для алгоритма кластеризации. По всем точкам строится минимальное остовное дерево. Для начальной точки и всех точек, не присоединённых к дереву, вычисляется расстояние между точками. Точка с наименьшим расстоянием до начальной точки присоединяется к дереву ребром с весом, равным данному расстоянию. Далее для всех точек (вершин) в дереве вычисляются расстояния для всех «неиспользованных» точек, а точка с наименьшим расстоянием присоединяется к дереву. Алгоритм продолжается пока все точки не будут присоединены к дереву. Для выделения односвязных областей требуется разбить данное дерево на поддеревья. Для этого начнём удалять рёбра с весом больше некоторого порога t . После этого дерево разбивается на поддеревья, представляющие собой односвязные области на изображении. В алгоритме выполняется проверка, что размер полученных кластеров после разбиения превышает некоторый порог minimum_cluster_size; если размер кластера меньше данного порога, ребро, удаление которого привело к такому разбиению, не удаляется. Таким образом, на каждой новой итерации алгоритм производит более глубокую кластеризацию. Подробное описание алгоритма - в статье [1].

[1] Белим С.В., Кутлунин П.Е. Использование алгоритма кластеризации для разбиения изображения на односвязные области // Наука и образование: электронное научно-техническое издание, 2015, №.3, URL: http://technomag.bmstu.ru/doc/759275.html].

Функциональные возможности  Изображение размером 256х256 пикселей на компьютере с двухъядерным процессором Intel Core i5 2.26GHz обрабатывается около 3 минут. Минимальное остовное дерево для этого изображения занимает в памяти 12 Мб. Ограничений со стороны алгоритма на размер обрабатываемого изображения не накладывается.

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

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

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

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

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

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

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

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

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

Вложение  Прикреплён архив imagesegmentationexample.zip, в котором представлены результаты работы программы для изображения «Перцы» размером 100х100 пикселей. Программа запускалась со следующими параметрами: r_coefficient=0,8; percent=5; minimum_cluster_size=30; color_intervals=16.

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