Восстановление гладкого многообразия по полю точек в приложении к задаче анализа данных компьютерной томографии

Таким образом данный метод предполагает, что при использовании достаточно “плотной" выборки исходное гладкое изображение можно в каждой точке выборки ограничить конусами Рис.8Рис. Конусы и приближенная нормальРезультаты использованияcrustalgorithmпредставлены на Рис. 9Рис. 8 Результат работы алгоритмаИтого предложенный алгоритм реконструкции, несмотря на существенную сложность реализации имеет несколько неоспоримых преимуществ: для него есть гарантии топологического сходства полученного и исходного объектов, а так же он достаточно устойчив к неравномерным выборкам, что в свою очередь означает, что он показывает лучшие результаты на зашумленных изображениях, чем алгоритм альфа-форм.Natural neighbor interpolationТретий метод, который будет представлен в этой работе также использует диаграммы Вороного, однако в качестве результата, в отличие от первых двух, предлагает гладкую поверхность.Пусть – как и прежде, выборка точек, принадлежащих, гладкой поверхности в .На этот раз они упорядочены каким-либо образом . S – восстанавливаемая поверхность, – соответствующая диаграмма Вороного. Введем понятие естественной окрестности точки x(см. Рис. 8).Естественная окрестность точки x – ячейка Вороного точки x, если бы xбыла добавлена в выборку.Естественные соседи точки x – точки выборки, ячейки которых пересекаются с естественной окрестностью точки x.Естественный регион - часть пересекающаяся с естественной окрестностью x.Рис. Естественная окрестность точки x обозначена пунктирной линиейПусть теперь – объем . Введем тогда понятие естественной координаты относительно :Функции обладают следующими свойствами[10]:Они непрерывно дифференцируемы.Перейдем непосредственно к интерполяции. Пусть к каждой точке выборки привязан некоторыйнепрерывный функционал (описывающий в некотором смысле поверхность), такой что . Зададим Natural neighbor interpolation так:где – достаточно малая константа. Как нетрудно видеть, непрерывно дифференцируема и интерполирует [10]. Далее по теореме Сарда [11] обратная к непрерывно дифференцируема почти везде.Осталось выбрать . В статье [10] она предлагается в таком формате:где – нормаль к исходной поверхности в точке . Иначе говоря, – плоскость перпендикулярная искомому многообразию в . Итак, интерполяция - - то, что мы ищем. Алгоритм таким образом состоит, по существу, из трех этаповРасчёт диаграммы ВороногоРасчётNatural neighbor interpolation – функции.Восстановление поверхности -.Преимущество данного алгоритма по сравнению с предыдущими заключается в том, что он выдает на выходе гладкое многообразие. Более того, он устойчив к неравномерным и редким выборкам. Так же в [10] доказывается, что чем более частая выборка, тем меньше Хаусдорфово расстояние между и . Недостатком в общем случае является тот факт, что алгоритм требует знания о нормалях к реконструируемому многообразию, но для задачи обработки данных компьютерной томографии это ограничение является не критичным.Результат практического использованияNaturalneighborinterpolationизображен ниже (см. Рис. 9).Рис. 9РезультаталгоритмаNatural neighbor interpolationЗАКЛЮЧЕНИЕИтак, в работе были проанализированы и сопоставлены три наиболее популярных алгоритма восстановления гладких (и не обязательно, как в случае с альфа-формами) многообразий по заданному полю точек в трехмерном пространстве. Стоит сказать, что есть еще множество подходов, не столь широко используемых ввиду разных причин, но достойных упоминания, о них можно прочитать в [10]. Все описанное выше приводит к мысли, что наука о реконструкции изображений в ближайшее время будет наиболее бурно развиваться в сторону решения следующих вопросов:Снижение влияния шумовУменьшение ограничений на возможные выборкиСоздание алгоритмов с геометрическими и топологическими гарантиями результатаСоздание алгоритмов максимально простых в имплементации и отладке.Созданные уже методы должны быть оформлены в виде программ для ЭВМ, протестированы и в случае отсутствия коммерческого интереса выложены в открытый доступ для максимально скорого распространения, и как следствие совершенствования алгоритмов. Предложенные в данной работе описания алгоритмов crust, naturalneighborinterpolation и метода альфа-форм могут послужить в дальнейшем основой для разъясняющих материалов к подобным программам.СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ1. Марусина М.Я., Казначеева А.О. Современные виды томографии / Учебное пособие. - СПб: СПБГУ ИТМО, 2006. - 132 с. - 100 экз.2. Computed tomography. Its history and technology. Siemens medical. www.siemensmedical.com3. Amenta N. et al. A simple algorithm for homeomorphic surface reconstruction //Proceedings of the sixteenth annual symposium on Computational geometry. – 2000. – С. 213-222.4.Edelsbrunner H., Mücke E. P. Three-dimensional alpha shapes //ACM Transactions on Graphics (TOG). – 1994. – Т. 13. – №. 1. – С. 43-72.5. Chazal F., Lieutier A. Smooth manifold reconstruction from noisy and non-uniform approximation with guarantees //Computational Geometry. – 2008. – Т. 40. – №. 2. – С. 156-170.6.Fischer K. Introduction to alpha shapes //Department of Information and Computing Sciences, Faculty of Science, Utrecht University. – 2000. – Т. 17.7. Aggarwal A. et al. A linear-time algorithm for computing the Voronoi diagram of a convex polygon //Discrete & Computational Geometry. – 1989. – Т. 4. – №. 6. – С. 591-604.8. Aurenhammer F. Voronoi diagrams—a survey of a fundamental geometric data structure //ACM Computing Surveys (CSUR). – 1991. – Т. 23. – №. 3. – С. 345-405.9. Lee D. T., Lin A. K. Generalized Delaunay triangulation for planar graphs //Discrete & Computational Geometry. – 1986. – Т. 1. – №. 3. – С. 201-217.10. Boissonnat J. D., Cazals F. Smooth surface reconstruction via natural neighbour interpolation of distance functions //Computational Geometry. – 2002. – Т. 22. – №. 1-3. – С. 185-203.11. Fomenko A. T., Kunii T. L. Topological modeling for visualization. – Springer Science & Business Media, 2013.