Модели и алгоритмы построения криволинейных скелетов пространственных форм тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Хромов, Денис Валерьевич

• Хромов, Денис Валерьевич
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Хромов, Денис Валерьевич

Содержание

Введение

Глава 1. Трёхмерные криволинейные скелеты: постановка задачи

1.1. Трехмерные формы и связанные с ними прикладные задачи

1.2. Серединная ось

1.3. Криволинейный скелет

1.3.1. Понятие криволинейного скелета

1.3.2. Свойства криволинейных скелетов

1.3.3. Алгоритмы построения

1.4. Основные выводы

Глава 2. Математическая модель криволинейных скелетов

2.1. Жирные кривые

2.2. Пространственные циркуляры и криволинейные скелеты

2.3. Мера близости между формой и аппроксимирующим пространственным циркуляром

2.4. Аппроксимация плоской многоугольной фигуры

2.5. Основные выводы

Глава 3. Алгоритмы построения скелетов

3.1. Общая схема алгоритма

3.2. Построение первого приближения при помощи графов Риба

3.2.1. Графы Риба

3.2.2. Порождающая функция

3.2.3. Вложение графа Риба

3.3. Построение первого приближения при помощи плоских проекций

3.3.1. Общая идея

3.3.2. Построение трёхмерного криволинейного скелета по плоской проекции

3.3.3. Выбор оптимальной плоской проекции

3.4. Численная оптимизация

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

3.4.2. Вычисление промежуточных значений

3.4.3. Корректность алгоритма

3.5. Анализ вычислительной сложности алгоритма

3.5.1. Построение первого приближения при помощи графов Риба

3.5.2. Построение первого приближения при помощи плоских проекций

3.5.3. Оптимизация методом градиентного спуска

3.6. Основные выводы

Глава 4. Вычислительный эксперимент

4.1. Практическая реализация

4.2. Экспериментальная проверка модели

4.3. Свойства алгоритма

4.4. Основные выводы

Заключение

Литература

Введение диссертации (часть автореферата) на тему «Модели и алгоритмы построения криволинейных скелетов пространственных форм»

Введение

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

Актуальность темы В настоящее время возникает большое количество практических задач, связанных с анализом формы трехмерных объектов. Это связано с широким распространением устройств, позволяющих получать цифровые трёхмерные модели объектов реального мира. Такие модели, как правило, представляют собой вексельные изображения, облака точек или полигональные поверхности. Все эти структуры данных на практике обладают очень большой размерностью и в явном виде не содержат в себе информации о форме исходных трехмерных объектов с «человеческой» точки зре-пя. Поэтому генерация признаков в таких задачах может вызывать существенные трудности. Кроме того, зачастую требуется построить алгоритмы, работающие в режиме реального времени, что накладывает дополнительные ограничения па эффективность.

В задачах анализа формы плоских изображений хорошо зарекомендовало себя примсиспис аппарата непрерывных скелетов. Скс-

летом двумерной области называют плаиарную укладную некоторого графа, удачно схватывающего основные геометрические свойства фигуры. Визуально скелет выглядит как утончение исходной формы до набора одномерных линий. Извлекать признаковую информацию из такого графа значительно проще, чем из исходного гранично-контурного описания двумерной области. Обычно скелет двумерной области определяется как сё серединная ось — множество центров максимальных вписанных в эту область кругов [19] (хотя существуют и другие модели, например, прямолинейные скелеты — straight skeletons [131).

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

Тем не менее, существует большая потребность в математической модели, описывающей аналог двумерной серединной оси в трёхмерном пространстве именно как пространственную укладпу пското-

рого графа. В литературе такие объекты принято называть криволинейными скелетами (curve-skeletons). Несмотря на большое количество публикаций по этой теме, общего строгого определения криволинейного скелета до сих пор не существует [24]. В многочисленных публикациях обычно предлагаются разнообразные эвристики для построения скелетов, при этом криволинейный скелет определяется как то, что получается на выходе описываемых авторами алгоритмов. Это означает, что не существует какого-либо обоснованного метода для оценки и сравнения различных подходов между собой, если не считать таковым визуальную оценку качества скелетов, получаемых при помощи различных алгоритмов.

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

а также математического аппарата для строгой численной оценки качества различных конкретных способов построения скелетов.

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

Предлагаемый подход основан на использовании специальных геометрических примитивов — пространственных циркуляров. Циркуляры, с одной стороны, могут рассматриваться в качестве приближенного представления трёхмерных объектов самой разнообразной формы, а с другой — для них естественным и однозначным образом вводится понятие криволинейного скелета. Отсюда вытекает основная идея метода: всякую трёхмерную фигуру можно с некоторой погрешностью аппроксимировать при помощи пространственного циркуляра, тогда скелетом этой фигуры можно считать скелет аппрок-симируюущего её циркуляра. При этом численной оценкой качества скелета является величина погрешности аппроксимации.

Таким образом, алгоритм построения криволинейного скелета

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

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

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

Методы исследования Работа носит тсоретико-эксперимеиталь-пый характер. Теоретическая часть содержит в себе элементы дифференциальной геометрии, вычислительных методов, теории графов, теории сложности алгоритмов и вычислений. Для проведения экспе-

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

Научная значимость Многочисленные публикации о трёхмерных криволинейных скелетах не опираются на общую теоретическую базу; отсутствует даже общепринятое определение криволинейного скелета. Это делает невозможным содержательное обсуждение и сравнение различных конкретных способов построения скелетов. Настоящая работа призвана заполнить этот пробел. Предлагаемое общее предслепие криволинейных скелетов включает в себя различные эвристические определения, позволяя при этом численно оценивать степень соответствия между тем или иным скелетом и исходной моделью.

Наличие численной меры качества скелетов позволяет формулировать задачу трёхмерной скелетизации как задачу оптимизации некоторой функции; в работе описан основанный па этом подходе алгоритм, основанный на использовании численных методов для уточнения получаемых скелетов.

Практическая значимость Трёхмерные криволинейные скелеты находят широкое применение в многочисленных задачах анализа формы трёхмерных изображений. К ним относятся задачи анализа

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

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

Алгоритмы, работающие на основе предлагаемой модели, эффективны и теоретически обоснованы — последнее обстоятельство также содержит в себе элемент новизны, т.к. общепринятый порядок заключается в определении скелета как результата работы некоторого эвристического алгоритма.

Апробация работы Результаты работы докладывались и обсуждались на следующих научных конференциях и семинарах:

• научно-техническая конференция «Техническое зрение в системах управления» TVCS 2011 (Москва, Россия, 2011 год) [10];

• международная конференция «Advanced Concepts for Intelligent

Vision Systems» ACIVS 2011 (Гспт, Бельгия, 2011 год) [36];

• всероссийская конференция «Математические методы распознавания образов» ММРО-15 (Петрозаводск, Россия, 2011 год)

[31;

• международная конференция «21th International Conference on Computer Graphics and Vision» GraphiCon 2011 (Москва, Россия, 2011 год) [391;

• международная конференция «24th Canadian Conference on Computational Geometry» CCCG 2012 (Шарлоттауп, Канада, 2012 год) [40];

• ярославская международная конференция «Дискретная геометрия», посвященная 100-летию А.Д. Александрова (Ярославль, Россия, 2012 год) [38].

Личный вклад. Все результаты, выносимые на защиту, получены автором самостоятельно. Постановка задачи была выполнена сов- 1 местио с научным руководителем.

Публикации по теме диссертации в изданиях списка ВАК: [11, 36]. Другие публикации по теме диссертации: [3, 10, 37-40].

Структура и объём диссертационной работы. Работа состоит из оглавления, введения, четырёх глав, заключения и списка литера-

туры. Содержание работы изложено па 133 страницах.

В первой главе рассматриваются основные понятия, связанные с темой работы: трёхмерные формы и способы их описания, серединная ось и её свойства, криволинейные скелеты и способы их построения, предложенные в существующей литературе по этой теме; формулируется постановка задачи построения трёхмерного криволинейного скелета.

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

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

В четвёртой главе описывается практическая реализация алго-

ритма построения криволинейных скелетов и анализируются результаты вычислительных экспериментов.

В заключении подводится итог выполненной работе.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Хромов, Денис Валерьевич

4.4. Основные выводы

1. Все описанные в настоящей работе алгоритмы были реализованы на практике. Полученные скелеты являются корректными и согласуются с интуитивным представлением о криволинейных а) е = 7.96 (Ь) е = 1.64 (с) £ = 0.84

Рис. 4.13: Криволинейный скелет и пространственный циркуляр модели лошади в первом приближении (а), после одной (Ь) и двух (с) итераций градиентного метода. скелетах пространственных форм.

2. Эксперимент продемонстрировал, что процедуры, которые существенно зависят от осмысленности используемой меры сходства между формой и аппроксимирующим циркуляром (например, численная оптимизация циркуляра или выбор плоской проекции методом Монте-Карло), корректны. Таким образом, практическая применимость предложенной математической модели подтверждена экспериментально.

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

Заключение

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

Предлагаемый метод основан на аппроксимации трёхмерных фигур при помощи примитивов специального вида — пространственных циркуляров. Для пространственного циркуляра даётся строгое и однозначное определение криволинейного скелета. Скелет исходной фигуры при этом определяется как скелет аппроксимирующего её циркуляра, а погрешность аппроксимации даёт численную оценку качества полученного скелета. В работе предложена специальная функция погрешности, в которой формализовано интуитивное человеческое представление о том, что должен представлять из себя криволинейный скелет произвольной пространственной фигуры.

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Хромов, Денис Валерьевич, 2012 год

Литература

1. Кормен Т., Лейзерсоп Ч., Ривест Р., Шень А. Алгоритмы: построение и анализ. МЦНМО, 2004. ISBN: 9785947741971.

2. Корн Г., Кори Т. Справочник по математике для научных работников и инженеров. М.: «Наука», 1973.

3. Местецкий Л.., Хромов Д.. Криволинейные скелеты трёхмерных форм // Доклады 15-й Всероссийской конференции «Математические методы распознавания образов». 2011.

4. Розепфсльд А. Распознавание и обработка изображений. М.: Мир, 1972.

5. Васильев Ф. Методы оптимизации. Факториал Пресс, 2002. ISBN: 5-88688-056-9.

6. Рашевский П. Курс дифференциальной геометрии. М.: Издательство ЛКИ, 2008. ISBN: 978-5-382-00673-4.

7. Местецкий Л. Непрерывная морфология бинарных изображений: фигуры, скелеты,циркуляры. М.: Физматлит, 2009. ISBN: 978-5-9221-1050-1.

8. Цискаридзе А. Восстановление пространственных циркулярных моделей по силуэтным изображениям: Ph. D. thesis / Московский физико-технический институт. 2010.

9. Милнор Дж. Теория Морса. М.: Издательство ЛКИ, 2011. ISBN: 978-5-382-01284-1.

10. Хромов Д.. Построение трёхмерных криволинейных скелетов при помощи пространственных циркуляров // Научио-техииче-ская конференция «Техническое зрение в системах управления». Тезисы докладов. 2011.

11. Хромов Д. Трехмерные циркуляры и криволинейные скелеты // Известия ВУЗов. Математика. 2012. по. 4. Р 90-99.

12. Abdel-Harnid Gamal Н , Yang Yec-Hong. Multircsolution Skeletonization: An Electrostatic Field-Based Appioach // ICIP (1). 1994. P. 949-953.

13. Aichholzcr O., Auienhammcr F. Straight Skeletons foi General Polygonal Figuies in the Plane. Spiinger-Verlag, 1996. P. 117-126.

14. Atrnosukarto I., Wilamowska K., Hcikc C., Shapiio L 3D object classification using salient point patterns with application to craniofacial reseaich // Pattern Recogn. 2010. Vol. 43, no 4 P. 1502-1517.

15. Attene M., Biasotti S , Spagnuolo M. Shape understanding by contour driven rctiling // THE VISUAL COMPUTER. 2003. Vol. 19. P. 2-3.

16. Au 0., Tai C., Chu H. et al. Skeleton extraction by rricsh contraction // ACM SIGGRAPH 2008 papers. SIGGRAPH '08. New York, NY, USA: ACM, 2008. P. 44:1-44:10.

17. Bag S., Harit G A medial axis based thinning stiategy and structural feature extraction of character images. // ICIP. IEEE, 2010. P. 2173-2176.

18. Biasotti S. Topological Techniques for Shape Undcistanding // IN CENTRAL EUROPEAN SEMINAR ON COMPUTER GRAPHICS, CESCG. 2001. P 1.

19. Blum H. A Transformation foi Extracting New Descriptors of Shape // Models for the Perception of Speech and Visual Form / Ed. by W. Wathcn-Dunn. Cambridge: MIT Press, 1967 P. 362-380.

20. Bouix S., Siddiqi K., Tannenbaum A. Flux driven fly throughs // Proceedings of the 2003 IEEE computer society conference on Computer vision and pattern recognition. CVPR'03 Washington, DC, USA: IEEE Computer Society, 2003. P. 449-454.

21. Bruck J., Gao J., Jiang A MAP: medial axis based geometric routing in sensor networks // Proceedings of the 11th annual mternational conference on Mobile computing and networking. MobiCom '05. New York, NY, USA: ACM, 2005. P. 88-102

22. Cao J., Tagliasacchi A., Olson M. et al Point Cloud Skeletons

via Laplacian Based Contraction // Proceedings of the 2010 Shape Modeling International Conference. SMI '10. Washington, DC, USA-IEEE Computer Society, 2010. P. 187-197.

23. Chazal F., Soufflet R. Stability and Finiteness Properties of Medial Axis and Skeleton // Journal of Dynamical and Control Systems

2004. Vol. 10, no. 2. P. 149-170.

24. Cornea N., Silver D. Curve-skeleton properties, applications, and algorithms // IEEE Transactions on Visualization and Computer Graphics 2007. Vol. 13. P. 530-548

25. Cornea Nicu D., Silver D., Yuan X., Balasubrarnanian R. Computing hierarchical curve-skeletons of 3d objects // The Visual Computer

2005. Vol. 21.

26. Curnani A., Guiducci A. Recovering the 3D structure of tubular objects from stereo silhouettes // Pattern Recogn. 1997. Vol 30, no. 7. P. 1051-1059.

27. Curless B., Levoy M. A volumetric method for buildmg complex models from range images // Proceedings of the 23rd annual conference on Computer graphics and interactive techniques SIGGRAPH '96. New York, NY, USA- ACM, 1996. P. 303-312.

28. Dcy T., Sun J. Defining and computing curvc-skclctons with medial geodesic function // Proceedings of the fourth Eurographics

symposium on Geometry processing SGP '06 Aire-la-Ville, Switzerland, Switzerland: Eurographics Association, 2006 P. 143-152.

29. Drira H., Amor B., Siivastava A., Daoudi M. A Ricmarmian analysis of 3D nose shapes for partial human biometrics. // ICCV. IEEE, 2009. P. 2050-2057.

30. Edclsbrurmer H. Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science. Springer, 2004 ISBN: 9783540137221.

31. Fol-Lcyrnarie F. Three-dimensional shape representation via shock flows: Ph.D. thesis. Providence, RI, USA: Brown University, 2003 AAI3087258.

32 Forbes K., Nicolls F., de Jagcr G., Voigt A Shapc-from-Silhouette with two mirrors and an uncalibrated camera // Proceedings of the 9th European conference on Computer Vision - Volume Part II. ECCV'06. Berlin, Heidelberg- Springer-Verlag, 2006. P. 165-178

33. Frosini P. A distance for similarity classes of submanifolds of a Euclidean space // Bulletin of the Australian Mathematical Society 1990 Vol. 42, no. 03. P. 407-415.

34. Guggeri F. Perceptual Shape Analysis: Approaching gcorrrctrrc

problems with elements of perception psychology: Ph. D. thesis / University of Cagliari. 2012.

35. Hiransakolwong Nualsawat., Vu Khanh., Hua Kien A.., Lang Shcau-Dong. Shape recognition based on the medial axis approach // ICME'04. 2004. P. 257-260.

36. Khromov D. Curve-skeletons based on the fat graph approximation // Proceedings of the 13th international conference on Advanced concepts for intelligent vision systems. ACIVS'll Berlin, Heidelberg: Springer-Verlag, 2011. P. 239-248.

37. Khromov D. 3D circular shapes and curve skeletons // Russian Mathematics (Iz VUZ). 2012. Vol. 56. P 75-83 10.3103/S1066369X1204010X.

38. Khromov D.. A Numerical Approach of the Curve-Skeletons Problem // Yaroslavl International Conference "Discrete Geometry "dedicated to the centenary of A.D. Alexandrov. 2012.

39. Khromov D.., Mestetskiy L.. 3D Curve-Skeletons Extraction and Evaluation // Proceedings of the 21th International Conference on Computer Graphics and Visionth (GraphiCon 2011). 2011.

40. Khromov D ., Mestetskiy L.. 3D Skeletonization as an Optimization Problem // In Proceedings of the 24th Canadian Conference on Computational Geometry 2012

41. Laboratory Rensselaer Polytechnic Institute Image Processing , Meagher. Octree Encoding: a New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer. 1980.

42. Laurentini A. The Visual Hull Conccpt for Silhouette-Based Image Understanding // IEEE Trans. Pattern Anal. Mach. Intcll 1994. Vol. 16, no. 2. P. 150-162.

43. Licutier A. Any open bounded subset of Rn has the same homotopy type than its medial axis // Proceedings of the eighth ACM symposium on Solid modeling and applications. SM '03. New York, NY, USA- ACM, 2003 P. 65-75. URL-http://doi.acm.org/10.1145/781606.781620.

44. Livesu M., Guggcri F., Scatcni R. Reconstructing the Curve-Skeletons of 3D Shapes Using the Visual Hull // IEEE Transactions on Visualization and Computer Graphics. 2012. Vol. 18 P. 1891-1901.

45. Lu M., Karnakura M., Zheng B et al. Clustering Bayon Face Towers Using Restored 3D Shape Models // International Conference on Culture and Computing. 2011. Vol. 0. P. 39-44

46. Ma M., Sonka M. A fully parallel 3D thinning algorithm and its

applications // Cornput. Vis. Image Undcrst. 1996. Vol. 64, no. 3 P. 420-433.

47 Mestetskii L. Fat cuivcs and representation of planar figures // Computers & Graphics. 2000. Vol. 24, no. 1 P 9 - 21.

48. Mcstctskiy L., Bakina I., Kurakin A. Hand geometry analysis by continuous skeletons // Proceedings of the 8th international conference on Image analysis and recognition - Volume Part II. ICIAR'll. Berlin, Heidelberg: Springer-Verlag, 2011. P. 130-139.

49. Rceb G. Sur les points singuliers d'une foirnc de Pfaff complètement intcgrable ou d'une fonction numérique. // Comptes Rendus de L'Acadcmic ses Seances, Paris. 1946. Vol. 222.

50. Schnabcl R.. Wessel R., Wahl R., Klein R Shape Recognition in 3D Point-Clouds // The 16-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision'2008 / Ed. by V. Skala. UNION Agcncy-Scicnce Press, 2008.

51. Shinagawa Y., Kunii T., Kergosien Y. Surface Coding Based on Morse Theory // IEEE Cornput. Graph. Appl. 1991 Vol 11, no. 5 P. 66-78.

52. Svensson S., I Nystro institution = Computerized Image Analysis journal = Pattern Recognition Letters note = address for co-author: Gabriclla Sarmiti di Baja, Istituto di Cibernetica, National Research

Council of Italy (CNR), Pozzuoli (Napoli), Italy nurnbei = 12 pages = 1419-1426 title = Curve skeletonization of surface-like objccts in 3D images guided by voxel classification volume — 23 year = 2002., institution = Uppsala University, Centre for Image Analysis.

53 Tagliasacchi A., Alhashim I., Olson M., Zhang H. Mean Curvature Skeletons // Cornp. Giaph. Forum. 2012. Vol. 31, no. 5. P. 1735-1744.

54. Turk G., Levoy M. Zippercd polygon meshes from range images // Proceedings of the 21st annual conference on Computer graphics and interactive techniques. SIGGRAPH '94. New York, NY, USA: ACM, 1994. P. 311-318.

55. Vcigeest J., Spanjaard S., Song Y Directed mean Hausdorff distance of parameterized freeform shapes in 3D: a ease study // The Visual Computer. 2003. Vol. 19. P. 480-492.

56. Welzl E. Smallest Enclosing Disks (balls and Ellipsoids) // Results and New Trends in Computer Sciencc. Springer-Verlag, 1991 P. 359-370.

57. Wu F., Ma W., Liou P. ct al. Skeleton Extraction of 3D Objccts with Visible Repulsive Force. 2003.

58. Yan P., Bowyer K. A fast algorithm for ICP-based 3D shape

biometries // Cornput. Vis. Image Underst. 2007. Vol. 107, no 3. P. 195-202.

59. Zwettler G., Pfeifcr F., Swoboda R., Backfrieder W. Accelerated Skeletonization Algorithm for Tubular Structures in Laige Datascts by Randomized Erosion. 2008.