Топологическое утоньшение

Методы топологического утоньшения строят скелет путем удаления вокселей границы объекта до тех пор, пока не будет получена необходимая тонкость. Все утоньшающие алгоритмы функционируют в дискретных пространствах и основываются на концепте «простой» точки, введенной Morgenthaler в 1981 [17]. «Простая» точка [18] это воксель, который может быть удален без изменения топологии объекта. Важное свойство «простых» точек состоит в том, что они могут быть определены локально, то есть путем анализа локальной окрестности, что делает алгоритмы топологического утоньшения более эффективными.

    Процесс утоньшения начинается от границы объекта и продолжается, пока не останется «простых» точек. На каждой итерации, каждый граничный воксель проверяется на принадлежность множеству «простых» точек. Условия обычно реализованы как шаблоны (или маски) размера 3x3x3 или более. Центр маски совмещается с рассматриваемым вокселем и анализируется окрестность этого вокселя. Все воксели в маске имеют величины «0», «1» или «не опреден». Величина «0» соответствует вокселю границы, «1» – вокселю объекта, «не определен» может принадлежать как границе, так и объекту.

    В то же время, удаление всех «простых» точек объекта приводит к укорочения самого скелета, потому что концевые точки скелеты сами являются «простыми».

    Существуют несколько подклассов утоньшающих алгоритмов, различающихся по способу определения «простых» точек, а также порядком их удаления.

· методы направленного утоньшения удаляют воксели строго с одного направления на каждом шаге (например, север-юг-верх-низ-запад-восток) используя различные вариации направлений и условий обнаружения конечных точек [19]. Эти методы чувствительны к выбору порядка направлений.

· методы последовательного утоньшения подполей  – методы, делящие дискретное пространство на несколько подмножеств, называемых подполями, и на каждой подитерации удаляются воксели, принадлежащие определенному подполю. Используется различное число подполей: 2 [20], 4 [21] or 8 [22]. Например, для подхода деления на 2 подполя [20], два вокселя находятся в разных подполях, если они разъединены границей объекта.

· полностью параллельные методы [23] – алгоритмы, рассматривающие все граничные точки для удаления в одной итерации. В целях сохранения топологии рассматривается как правило окрестность из 26 соседей.

На рисунке 3 представлен пример топологического утоньшения.

Рисунок 3 – Пример алгоритма утоньшения для двумерного случая. Граничные точки, помечаются «B» и затем удаляются, если они «простые»