Методи сегментації зображень на основі графів

Abstract

Досліджується задача сегментації зображення на основі використання колірних і текстурних відмінностей областей. В роботі проаналізовані існуючі методи та алгоритми сегментації зображень. Наведений короткий опис алгоритмів автоматичної сегментації. Акцент зроблено на методах сегментації, основаних на представлені зображення у вигляді графу. Досліджено аспекти ефективної реалізації алгоритму, зокрема використання структури даних «об’єднання множин, які не перетинаються» та однонаправленого зв’язаного списку. Запропоновано модифікацію алгоритму з сортуванням ребер графу за лінійний час, яка дала приріст швидкодії в 4 рази. Проаналізовано вплив вхідних параметрів на результат сегментації. Показано залежність результату сегментації від метрики відмінності кольорів. Запропоновано модифікацію алгоритму з використанням суперпікселізації, яка дозволила уникнути пересегментації зображення.

Исследуется задача сегментации изображения на основе использования цветовых и текстурных различий областей. В работе проанализированы существующие методы и алгоритмы сегментации изображений. Приведено краткое описание алгоритмов автоматической сегментации. Акцент сделан на методах сегментации, которые основаны на представлении изображения в виде графа. Исследованы аспекты эффективной реализации алгоритма, в частности использование структуры данных «cистема непересекающихся множеств» и однонаправленного связанного списка. Предложена модификация алгоритма с сортировкой ребер графа за линейное время, которая дала прирост быстродействия в 4 раза. Проанализировано влияние входных параметров на результат сегментации. Показана зависимость результата сегментации от метрики различия цветов. Предложена модификация алгоритма с использованием суперпикселизации, которая позволила избежать пересегментации изображения.

We study the problem of image segmentation through the use of color and texture areas differences. The existent image segmentation methods and algorithms have been analyzed in the work. A brief description of automatic segmentation algorithms is shown. The focus was on the methods of segmentation based on image represented as a graph. The aspects of an efficient algorithm implementation, in particular the use of Disjoint-set data structure and singly linked linear list are investigated. Modification of algorithm with graph edges sorting in linear time is proposed. This modification gave a performance increase of 4 times. The impact of input parameters on the segmentation result is analyzed. Segmentation result dependence on the color difference metrics is shown. Modification of algorithm with superpixels using is proposed, that allowed to avoid image oversegmentation.