Использование диаграмм Вороного

Диаграмма Вороного конечного множества точек S на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек более близких к одному из элементов множества S, чем к любому другому элементу множества [41].

Пример диаграммы Вороного продемонстрирован на рисунке 5.

Рисунок 5 – а) 10 сгенерированных точек и б) построенная для них диаграмма Вороного.

Популярный подход состоит в использовании диаграмм Вороного [34], порожденых вершинами трехмерной полигональной сетки или непосредственно точками границы. Внутренние ребра и грани диаграммы Вороного, могут быть использованы для выделения средних линий и плоскостей. Средняя линия может быть получена из медиальной плоскости путем утоньшения последней. В работе [35], определяется число "шаровых областей " (непересекающихся максимальные шары), центры которых позднее объединеняются в среднюю линию, используя информацию медиальной поверхности. В работе [36], средняя линия рассчитывается путем морфологической эрозии диаграмм Вороного на основе геодезической функции.

Общеполевые методы

Кроме дистанционных карт могут использоваться другие типы карт, построенные с помощью функций, отличных от функции расстояния.

В этот класс включена обобщенная потенциальная функция поля [37] [38] [15], где потенциал во внутренней точке объекта определяется как сумма потенциалов, возникающих на границе объекта. В дискретном случае [15], граничные воксели считаются точечными зарядами, генерирующими потенциальное поле. Функция электростатического поля используется в [38] для создания потенциала внутри объекта. Также используется частный случай потенциального поля – сила отталкивания – в работах [37] [38] и [15] (Рис. 6).

Скелет строится через определение локальных экстремумов построенного поля и объединения их.

Рисунок 6 – Поле сил отталкивания двумерного изображения.

Локальные экстремумы могут быть найдены за счет критических точек векторного поля [15] или обнаружения локальных максимумов вдоль эквипотенциальных контуров [2]. Другие методы непосредственно используют «силовые» алгоритмы, начиная в нескольких стартовых точках («семенах») и используя тот факт, что вычисляемые силы затухают в пиковых точках.

Основным преимуществом этих функций перед функцией расстояния является то, что они могут выделять сглаженные линии на медиальных поверхностях. Это происходит потому, что они принимают во внимание большие приграничные районы, а не только ближайшие точки на границе. Это также создает эффект усреднения, который делает эти алгоритмы менее чувствительны к шумам на границе. Тем не менее, вычислительная сложность у них гораздо выше.