Покомпонентная дифференциация

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

Алгоритмы утоньшения непосредственно могут классифицировать обрабатываемые точки как точки сочленения.

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

Метод множеств уровня может также непосредственно определить точки сочленения (как центры построенных множеств уровней).

 

Связность

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

 

Надежность

Алгоритмы утоньшения, а также алгоритмы, основанные на дистанционных картах и диаграммах Вороного, чувствительны к шумам и генерируют много ненужных ответвлений в скелете. Некоторые подходы используют постобработку получившихся скелетов [28].

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

Многие из этих алгоритмов, описанных в литературе, как правило, иллюстрируется лишь несколькими примерами и не протестированы на большой базе данных общих 3D объектов (например, базы данных 3D-моделей [40]). Таким образом, остается неясным, как надежны в целом эти алгоритмы в отношении выбора их параметров.

 

Гладкость

Из-за дискретного характера объектов, алгоритмы утоньшения не дают плавных средних линий.

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

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

 

Иерархичность

Иерархичность (способность создавать семейства средних линий различной сложности), не достижима при использовании алгоритмов утоньшения, поскольку при воксельной обработке существует только два варианта: сохранить его или удалить его. Скелет получается только на последней итерации алгоритма.

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

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

 

Эффективность

Алгоритм топологического утоньшения – практически линейный процесс относительно числа вокселей объекта. Большинство вокселей входного объекта удаляются, когда они обрабатываются впервые (в качестве «простых» точек); «непростые» точки обрабатываются повторно. Сложность анализа таких алгоритмов затруднено, так как конечный результат зависит от входных данных.

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

Вычислительная сложность построения диаграмм Вороного для множества из n точек в худшем случае , хотя на практике она почти линейна [4]. Как и в случае с дистанционными картами, здесь необходима постобработка.

Сложность вычисления потенциального поля  [15], где n – общее число вокселей. Для больших объектов или объектов с высоким разрешением этот метод работает очень долго.

Краткие выводы

В таблице 1 для каждого класса алгоритмов представлены достигаемые или недостигаемые свойства. «Да» означает то, что класс алгоритма гарантирует сохранение того или иного свойства, «Нет» в противном случае. Пустые места оставлены, если свойство сохраняется только некоторыми алгоритмами в классе или в случае, когда свойство слишком сложно для анализа подхода определенного класса (как было показано выше)

 

Таблица 1 – Свойства, достижимые различными классами алгоритмов.

Свойство	Утоньшение	Дистан-ционные карты	Диаграммы Вороного	Обще-полевые методы
Гомотопность	Да		Да	Нет
Инвариантность		Да		Да
Восстанавли-ваемость	Нет		Нет	Нет
Тонкость				Да
Определение сочленений			Да	Да
Связность	Да
Надежность	Нет	Нет	Нет	Да
Гладкость				Да
Иерархичность	Нет			Да
Эффективность	Да	Да	Да	Нет