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

Abstract

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

An efficient graph-based image segmentation algorithm is considered. The aspects of an efficient algorithm implementation, in particular the use of Disjoint-set data structure with its heuristics «path compression» and «union by rank», are investigated. Modification of algorithm with graph edges sorting in linear time is proposed. The impact of input parameters on the segmentation result is analyzed. Defined predicates for measuring for a boundary between two regions.