БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Выпускная работа по«Основам информационных технологий»Магистрант № 2ПМ37факультета прикладной математики и информатикикафедры информационных систем управленияГончаров Дмитрий АлександровичРуководители:профессор Абламейко Сергей Владимирович,доцент Кожич Павел ПавловичМинск – 2011 г. Оглавление Оглавление 3Реферат на тему «Применение ИТ в обработке медицинских изображений» 4 Введение 4 Глава 1 Анализ проблемы и постановка задачи 5 1.1 Общая схема обработки изображений 5 1.2 Особенности медицинских изображений 7 1.3 Формальная постановка задачи 8 Глава 2 Проблема выделения средних линий 9 2.1 Свойства средних линий 9 2.2 Существующие алгоритмы выделения средних линий 12 2.2.1 Топологическое утоньшение 12 2.2.2 Использование дистанционных преобразований 14 2.2.3 Использование диаграмм Вороного. 16 2.2.4 Общеполевые методы 16 2.3 Сравнение существующих методов 17 Глава 3 Практическая реализация 22 3.1 Архитектура и состав системы 22 3.2 Взаимодействие с клинической АСУ 25 3.3 Методика решения прикладных задач и демонстрация использования 26 Заключение 30 Список литературы к реферату 30Предметный указатель к реферату 32Интернет ресурсы в предметной области исследования 33Действующий личный сайт в WWW 34Граф научных интересов 35Тестовые вопросы по Основам информационных технологий 36Презентация магистерской диссертации 37Список литературы к выпускной работе 38Приложение 41 ^ Реферат на тему «Применение ИТ в обработке медицинских изображений» Введение Выделение средних линий объектов является важным этапом в обработке изображений для последующих вычислений различных (линейных, площадных, объемных) характеристик объекта, а также описания и распознавания объектов. Также оно может использоваться для мониторинга заболеваний путем контроля изменений на изображениях. Существует ряд алгоритмов позволяющих построить бинарный 3D скелет. Но из-за особенностей медицинских изображений таких как зашумленность, большие расстояния между слоями, геометрические и оптические искажения, нечеткие границы объектов, динамическое изменение объектов, с их помощью нельзя построить устойчивые к шумам средние линии. К тому же в случае исследования лучевыми методами много информации получают на основе данных плотности ткани. Поэтому при построении скелета сосудов желательно учитывать полутоновые свойства. Для решения этой задачи разработан алгоритм полутонового утоньшения, позволяющий построить образ сосудистой системы для дальнейшего анализа. В основе построения скелета сосудов лежит алгоритм псевдодистанционной карты [1]. Псевдодистанционная карта позволяет выполнить оценку расстояний между вокселями изображения и определить общие топологические свойства изображения. Локальные максимумы составляют основу для построения скелета такого изображения. В образовании скелета не участвуют приграничные локальные максимумы, которые удаляются по условию проверки близости границы, размеров и направления. Оставшиеся локальные максимумы образуют квазискелет, который исключает топологические особенности, связанные с неровностью границ и обладает большей устойчивостью к масштабированию и повороту.^ Глава 1 Анализ проблемы и постановка задачи 1.1 Общая схема обработки изображений Обработка изображений — любая форма обработки информации, для которой входные данные представлены изображением. Обработка изображений может осуществляться как для получения изображения на выходе (например, подготовка к полиграфическому тиражированию, к телетрансляции и т. д.), так и для получения другой информации (например, распознание текста, подсчёт числа и типа клеток в поле микроскопа и т. д.). Полезно разделить весь процесс обработки изображений на две большие категории: методы, в которых на входе и на выходе имеются изображения, и методы, где на вход поступают изображения, а на выходе возникают признаки и атрибуты, выделенные на основании этих изображений. Эта схема не подразумевает, что к изображению применяется каждый из описанных процессов. Регистрация изображения – первый из процессов, показанных на Рис.1. Регистрация может оказаться предельно простой, как в случае, когда исходное изображение уже представлению в цифровой форме. В общем случае стадия регистрации изображения включает некоторую предобработку, например, масштабирование. Улучшение изображения входит в число наиболее простых и впечатляющих областей цифровой обработки изображений. По существу, за методами улучшения изображений стоит идея выявления плохо различимых деталей или просто подчеркивания интересующих характеристик на исходном изображении. Известным примером улучшения является усиления контраст изображения, потому что в результате «оно выглядит лучше». Важно иметь в виду, что улучшение качества – весьма субъективная область в обработке изображений. Восстановление изображений – это область, также связанная с повышение визуального качества изображения, однако, в отличие от собственно улучшения, критерии которого субъективны, восстановление изображения является объективным в том смысле, что методы восстановления изображений опираются на математические или вероятностные модели искажений изображения. Напротив, улучшение изображений основано на субъективных предпочтениях человеческого восприятия, которые связаны с тем, что именно считается «хорошим» результатом улучшения. Обработка изображений как этап следует отделять от понятия обработки изображении как весь процесс изменений изображения и получения некоторых атрибутов. Сюда может включатся и вейвлетная обработка (для представления изображений с несколькими степенями разрешения одновременно) и морфологическая обработка (связана с инструментами для извлечения таких компонент изображения, которые могут быть полезны для представления и описания формы). Сегментация разделяет изображение на составные части или объекты. В целом автоматическая сегментация принадлежит к числу самых трудных задач цифровой обработки изображений. Излишне подробная сегментация уводит процесс решения задачи обработки изображения на сложный путь, если требуется идентифицировать объекты по отдельности. С другой стороны, недостаточно подробная или же ошибочная сегментация почти неизбежно приведет к возникновению ошибок на финальной стадии обработки. Представление и описание почти всегда следуют непосредственно за этапом сегментации, на выходе которого обычно имеются лишь необработанные данные о пикселях, которые либо образуют границу области (т.е. дается множество пикселей, отделяющих одну область изображения от другой), либо представляют все точки самих областей. В обоих случаях необходимо преобразовать данные в форму, пригодную для компьютерной обработки. Первое решение, которое следует принять – должна ли эти данные представляться в форме границ областей или областей целиком. Представление границами подходит для тех случаев, когда в центре внимания находятся внешние характеристики формы областей, например, углы и изгибы. Представление областями более уместно, если акцент делается на внутренних свойствах объектов, например, текстуре или форме скелета. В некоторых приложениях эти представления дополняют друг друга. Выбор способа представления – лишь часть принятия решения по преобразованию «сырых» пиксельных данных в подходящую для дальнейшей компьютерной обработки форму. Должен быть еще указан метод описания данных, при котором бы выдвигались на передний план интересующие признаки. Построение описания, иначе называемое выбором признаков, связано с выделением атрибутов, которые бы выражали интересующую количественную информацию или бы моги служить основой для различения классов объектов. Распознавание представляет собой процесс, которые присваивает некоторому объекту идентификатор (например, «бедренная кость») на основании его описателей. Рассмотрим взаимосвязь между базой знаний и модулями обработки. На самом деле, знание о проблемной области, т.е. база знаний, некоторым образом закодировано внутри самой системы обработки изображений. Это знание может быть очень простым, как детальное указание участков изображения, где должна находиться интересующая информация, что позволит ограничить область поиска. База знаний может быть и очень сложной, как, например, взаимосвязанный список всех наиболее вероятных дефектов в задаче контроля материалов, либо база данных спутниковых изображений некоторого района с высоким разрешение в прикладных задачах обнаружения изменений, происходящих в этом районе. Помимо того, что база знаний руководит работой каждого модуля обработки, она также управляет взаимодействием между модулями. Эта отличительная особенность показана на рис. 1 с помощью двунаправленных стрелок между обрабатывающими модулями и базой знаний. Рисунок 1 – Основные стадии цифровой обработки изображений^ 1.2 Особенности медицинских изображений Существует несколько различных видов медицинских изображений, отличающихся как по способу получения и области применения, так и по особенностям конечного изображения. Ниже перечислены основные типы медицинских изображений. Ангиографией является отображение тока крови по артериям и венам тела. До появления магниторезонансной терапии ангиография проводилась единственным способом. Для увеличения контраста сосудов в кровь человека вводилось рентгеноконтрастное вещество. Сосуды на ангиографических изображениях представляют собой сложные протяженные объекты с меняющимся контрастом. Поэтому основным механизмом в обработке и анализе таких изображений, позволяющим сохранить топологические свойства сосудов, является полутоновое утоньшение.Ультразвуковые изображения – это полутоновые изображения, которые синтезируются с помощью отраженных ультразвуковых волн. Получение этих изображений основано на способности ультразвука проникать внутрь органа и взаимодействовать с тканью. Информация о структуре органа кодируется с помощью отраженных ультразвуковых волн. Ультразвуковые волны преломляются и отражаются в основном на границах регионов, которые имеют различные акустические характеристики. Современные сканеры оснащены гироскопом и позволяют отслеживать направление луча, что позволяет строить трехмерные изображения.Гистологические изображения – цветные изображения гистологических срезов, сфотографированных с оптическим увеличением в 100-1000 раз. Объектами гистологического анализа являются фрагменты клеток и клеточных структур. Существует несколько способов получения 3D гистологических изображений, но самым распространенным является конфокальная микроскопия, которая позволяет получить объемные изображения клеточных образований и фрагментов ткани. Основным недостатком конфокальной микроскопии является изменения освещенности объекта в различные промежутки времени.Компьютерная томография измеряет плотность ткани посредством ослабления рентгеновских лучей. Однако компьютерная томография характеризуется большим количеством проекционных изображений. Именно по ним строится томограмма, полностью отражая пространственные свойства исследуемого объекта. Использование проекций дает ряд преимуществ по сравнению с рентгеновскими снимками. Прежде всего, это возможность построения трехмерной модели объекта, объекты могут быть отделены друг от друга, можно получить срез практически в любой области. Однако расстояние между полученными слоями гораздо больше расстояния между соседними пикселями слоя, что приводит к необходимости реконструкции пропущенных данных.^ 1.3 Формальная постановка задачи Средние линии имеют несколько различных математических определений, содержащихся в технической литературе. Эти определения аналогичны для непрерывных пространств, но обычно приводят к разным результатам в дискретных пространствах. В двумерном случае средняя линия [2] фигуры это множество кривых, определяемых как геометрическое место точек, которые имеют, по крайней мере, две ближайшие точки границы фигуры [3]. В трехмерном случае, соответствующий объект называется средней (или медиальной) плоскостью (Рис. 2). Рисунок 2 – а) Средняя линия в двухмерном случае б) Пример влияния граничных шумов на конечный результат, в) средняя плоскость в трехмерном случаеНаиболее наглядное определение средней линии дается через точки гашения в модели распространения огня, где граница фигуры сделана полностью из сухой травы, которую подожгли и средняя линия состоит из множества точек, где огни разных фронтов встречаются и гасят друг друга [2]. Также средние линии могут определяться как геометрическое место центров максимальных шаров (или дисков в двухмерном случае) [4]. Более формально, положим – трехмерный объект. Шар радиуса r с центром в точке определяется как , где – расстояние между двумя точками x и y в . Шар называется максимальным, если для него не существует шара большего радиуса, принадлежащего объекту, полностью содержащего [5]. Основное неудобство средних линий состоит в чувствительности к небольшим изменениям границ объекта [6][7]. Пример, приведенный на рис. 2(б), наглядно демонстрирует, как малые изменения границ приводят к большим изменениям средней линии.^ Глава 2 Проблема выделения средних линий 2.1 Свойства средних линий В этом пункте рассматриваются различные свойства средних линий, которые были получены путем анализа литературы и различных приложений скелетов в компьютерной графике и визуализации.Гомотопность (сохранение топологии) Средние линии должны быть топологически эквивалентны исходному объекту [4][8]. Сохранение топологии может быть сформулировано следующим образом: Два объекта имеют одинаковую топологию, если они имеют одинаковое число связных компонент и полостей. Однако для средних линий отсутствует понятие полости (из-за одномерности). Поэтому в [10] было предложено следующее определение гомотопности: Скелет сохраняет топологию исходного объекта, если он содержит то же самое число связных компонент и имеет по крайней мере одну петлю для каждой полости в исходном объекте. Циклы в скелете могут быть найдены с помощью алгоритма поиска в глубину, а наличие полостей в исходном объекте можно определить, используя метод, предложенный в [9].^ Инвариантность относительно изометрических преобразований Обозначим изометрическое преобразование (преобразование, в котором сохраняются расстояния между точкам) через ^ T, рассматриваемый объект через O, объект, подвергшийся преобразованию T(O), а его скелет должен быть таким же, как и трансформированный скелет исходного объекта, т.е. критерий инвариантности можно переписать (2.1) Это свойство очень важно для приложений, где средние линии используются для описания объекта.Восстанавливаемость В [11][12] рассматривают способность некоторых скелетов восстанавливать исходный объект из скелета. Учитывая определение средних линий как множества центров максимальных вписанных шаров, очевидным решением восстановления является вычисление и хранение для каждой точки скелета расстояния до ближайшей точки границы. Если обозначить функцию восстановления через , тогда точное восстановление означает (2.2) Трехмерный объект может быть полностью восстановлен из его представления средними линиями. Это свойство часто используется в приложениях для сжатия объектов, а также для визуализации [13]. В тоже время в общем случае, полное восстановление из-за дискретности множества вокселей не всегда возможно.Толщина Желательно, скелет должен быть одномерным, т.е. шириной в один воксель во всех направлениях, исключая точки сочленения различных ветвей. Можно выделить три типа точек скелета [22]: регулярные точки, которые имеют ровно два соседних вокселя; конечные точки, имеющие ровно один соседний воксель, и точки соединения, которые могут иметь три или более соседей. Тонкость и восстанавливаемость являются двумя противоречащими друг другу свойствами. Даже для объектов, в средних поверхностях которых фактически содержатся только кривые (например, для трубчатых объектов), скелет шириной в один воксель может не содержать все необходимые центры максимальных шаров для точной реконструкции объекта.Центрированность Важной характеристикой средней линии является его центрированность в пределах объекта. Для достижения идеальной центрированности необходимо, чтобы средняя линия находилась на медиальной поверхности, а сама медиальная поверхность была сосредоточена в пределах объекта. Кроме того, требуется, чтобы средняя линия находилась по центру медиальной поверхности [10]. Это свойство очень важно в приложениях сжатия изображений, а также в некоторых научных приложениях, например, в вычислении средней линии вихря [11] Тем не менее, в большинстве случаев, точной центрированности извлеченного скелета не требуется или нежелательно (с учетом известной чувствительности скелета к малым возмущениям на границе объекта) [6] [7]. Приближенной центрированности достаточно для многих приложений, таких как виртуальная навигация или визуализация. Например, в виртуальной колоноскопии, надежность (см. ниже) и гладкость пути более важны, чем точная центрированность [14].^ Покомпонентная дифференциация С помощью средних линий можно различать различные компоненты исходного объекта, т.е. логические компоненты объекта должны быть биективны логическим компонентам средних линий. Покомпонентная дифференциация отличается от гомотопности в том, что она касается логического восприятия составных частей единого объекта, в то время как последняя связана с геометрической составляющей компонентов, образующих различные объекты. Проверка, удовлетворяет ли скелет этим свойствам, является сложной задачей, так как определение компоненты объекта не является достаточно точным, а определяется с участием человеческого восприятия, которое по своей сути субъективно.Связность Это свойство является следствием гомотопии. Если средняя линия соответствует односвязной компоненте, то она должна быть связной.Помехоустойчивость Как показано на рисунке 2 (б), средняя линия очень чувствительна к небольшим изменениям на границе. Желательное свойство скелета – слабая чувствительность к шуму на границе объекта, то есть, скелет объекта без шума и скелет того же объекта с шумом должны быть аналогичны.Гладкость Гладкость не только эстетическое свойство, но на самом деле полезно в некоторых приложениях. Например, в виртуальной навигации, которая использует среднюю линию как путь прохода камеры. Путь должен быть как можно более плавным, чтобы избежать резких изменений в изображении.Иерархичность Средняя линия сложных объектов может отражать естественную иерархию сложных объектов [15]. Иерархический подход является полезным, поскольку он может создать набор средних линий разных сложностей, которые могут быть использованы в различных приложениях. В строгой иерархии, скелет на определенном уровне в иерархии содержит все средние линии слоев ниже в иерархии в качестве подмножества. Такая строгая иерархия полезна в приложениях с использованием различных разрешений.^ 2.2 Существующие алгоритмы выделения средних линий Существует много различных алгоритмов выделения средних линий для двумерного и трехмерного случаев. Хотя некоторые из 2D алгоритмы распространяются на 3D, мы ограничиваем наше рассмотрение алгоритмов, специально предназначенных для трехмерного случая. В современной литературе обычно используется схема классификации, в которой выделяются следующие классы [16]: основанные на топологическом утоньшении, на использовании дистанционных карт (поиск точек хребта), а также на использовании диаграмм Вороного. Тем не менее, существуют методы, которые принадлежат нескольким классам одновременно (например, методы, основанные на дистанционных преобразованиях, которые используют топологическое утоньшение для «обрезки» получившегося скелета).^ 2.2.1 Топологическое утоньшение Методы топологического утоньшения строят скелет путем удаления вокселей границы объекта до тех пор, пока не будет получена необходимая тонкость. Все утоньшающие алгоритмы функционируют в дискретных пространствах и основываются на концепте «простой» точки, введенной Morgenthaler в 1981 [17]. «Простая» точка [18] это воксель, который может быть удален без изменения топологии объекта. Важное свойство «простых» точек состоит в том, что они могут быть определены локально, то есть путем анализа локальной окрестности, что делает алгоритмы топологического утоньшения более эффективными. Процесс утоньшения начинается от границы объекта и продолжается, пока не останется «простых» точек. На каждой итерации, каждый граничный воксель проверяется на принадлежность множеству «простых» точек. Условия обычно реализованы как шаблоны (или маски) размера 3x3x3 или более. Центр маски совмещается с рассматриваемым вокселем и анализируется окрестность этого вокселя. Все воксели в маске имеют величины «0», «1» или «не опреден». Величина «0» соответствует вокселю границы, «1» – вокселю объекта, «не определен» может принадлежать как границе, так и объекту. В то же время, удаление всех «простых» точек объекта приводит к укорочения самого скелета, потому что концевые точки скелеты сами являются «простыми». Существуют несколько подклассов утоньшающих алгоритмов, различающихся по способу определения «простых» точек, а также порядком их удаления.методы направленного утоньшения удаляют воксели строго с одного направления на каждом шаге (например, север-юг-верх-низ-запад-восток) используя различные вариации направлений и условий обнаружения конечных точек [19]. Эти методы чувствительны к выбору порядка направлений.методы последовательного утоньшения подполей – методы, делящие дискретное пространство на несколько подмножеств, называемых подполями, и на каждой подитерации удаляются воксели, принадлежащие определенному подполю. Используется различное число подполей: 2 [20], 4 [21] or 8 [22]. Например, для подхода деления на 2 подполя [20], два вокселя находятся в разных подполях, если они разъединены границей объекта.полностью параллельные методы [23] – алгоритмы, рассматривающие все граничные точки для удаления в одной итерации. В целях сохранения топологии рассматривается как правило окрестность из 26 соседей.На рисунке 3 представлен пример топологического утоньшения. Рисунок 3 – Пример алгоритма утоньшения для двумерного случая. Граничные точки, помечаются «B» и затем удаляются, если они «простые»^ 2.2.2 Использование дистанционных преобразований Дистанционное преобразование – преобразование, которое каждой точке изображения ставит в соответствие расстояние в заданной метрике до ближайшей точки фона (Рис. 4). Формальная запись: , (2.3) где – некоторая метрика. Алгоритмы для построения карт расстояний могут быть классифицированы по нескольким критериям. Классификация по способу вычисления расстояния: Чамферные дистанционные преобразования [24], где новое значение расстояния для вокселя вычисляется из расстояний его соседей и соответствующих весов маски. Векторные дистанционные преобразования [25], в котором для каждого обработанного вокселя хранится вектор ближайших точек границы, а для необработанного вокселя этот вектор строится, используя вектора соседей из шаблонной окрестности. Дистанционные преобразования на основе решения эйконального уравнения [26], где расстояние находится из конечных разностей первого или второго порядков расстояний соседних вокселей Квадратное евклидово дистанционное преобразование [27], в котором вместо расстояния до ближайшей точки фона хранится квадрат этого расстояния, что позволяет воспользоваться некоторыми преимуществами. Рисунок 4 – Дистанционные карты с использованием а) шахматной метрики б) (3,4)-метрики ЧамфераХребтовые точки дистанционной карты соответствуют вокселям, которые находятся в центре объекта. Они выступают в качестве потенциальных кандидатов точек средних линий. Ниже перечислены некоторые подходы, использующиеся для поиска вокселей-кандидатов:методы утоньшения, использующие дистанционную карту для определения приоритета выбора вокселей для удаления [28] методы поиска градиента [29] предполагающие выявление районов неоднородного градиента и маркировки таких вокселей в качестве кандидатов на удаление. методы вычисления дивергенции используют в [30] в качестве функции приоритета для удаления «простых» вокселей с малым значением дивергенции.методы адаптивного утоньшения характеризуются сравнениями между значением дистанционной карты в вокселе и средним значением дистанционной карты его соседей [31]. Множество вокселей-кандидатов обычно имеет большую размерность и следующий шаг как правило заключается в уменьшении их количества. Для связности большинство алгоритмов используют минимальные остовные деревья [32], кратчайшие пути [33] или другие алгоритмы на графах. Некоторые методы сначала используют объединение, затем удаление вокселей путем нахождения кратчайшего пути в связанном множестве [29]. Основное преимущество этих методов в том, что вычисление дистанционной карты происходит очень быстро (за линейное время от числа вокселей), что очень важно во многих приложениях.^ 2.2.3 Использование диаграмм Вороного. Диаграмма Вороного конечного множества точек S на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек более близких к одному из элементов множества S, чем к любому другому элементу множества [41]. Пример диаграммы Вороного продемонстрирован на рисунке 5. Рисунок 5 – а) 10 сгенерированных точек и б) построенная для них диаграмма Вороного. Популярный подход состоит в использовании диаграмм Вороного [34], порожденых вершинами трехмерной полигональной сетки или непосредственно точками границы. Внутренние ребра и грани диаграммы Вороного, могут быть использованы для выделения средних линий и плоскостей. Средняя линия может быть получена из медиальной плоскости путем утоньшения последней. В работе [35], определяется число "шаровых областей " (непересекающихся максимальные шары), центры которых позднее объединеняются в среднюю линию, используя информацию медиальной поверхности. В работе [36], средняя линия рассчитывается путем морфологической эрозии диаграмм Вороного на основе геодезической функции.^ 2.2.4 Общеполевые методы Кроме дистанционных карт могут использоваться другие типы карт, построенные с помощью функций, отличных от функции расстояния. В этот класс включена обобщенная потенциальная функция поля [37] [38] [15], где потенциал во внутренней точке объекта определяется как сумма потенциалов, возникающих на границе объекта. В дискретном случае [15], граничные воксели считаются точечными зарядами, генерирующими потенциальное поле. Функция электростатического поля используется в [38] для создания потенциала внутри объекта. Также используется частный случай потенциального поля – сила отталкивания – в работах [37] [38] и [15] (Рис. 6). Скелет строится через определение локальных экстремумов построенного поля и объединения их. Рисунок 6 – Поле сил отталкивания двумерного изображения.Локальные экстремумы могут быть найдены за счет критических точек векторного поля [15] или обнаружения локальных максимумов вдоль эквипотенциальных контуров [2]. Другие методы непосредственно используют «силовые» алгоритмы, начиная в нескольких стартовых точках («семенах») и используя тот факт, что вычисляемые силы затухают в пиковых точках. Основным преимуществом этих функций перед функцией расстояния является то, что они могут выделять сглаженные линии на медиальных поверхностях. Это происходит потому, что они принимают во внимание большие приграничные районы, а не только ближайшие точки на границе. Это также создает эффект усреднения, который делает эти алгоритмы менее чувствительны к шумам на границе. Тем не менее, вычислительная сложность у них гораздо выше.^ 2.3 Сравнение существующих методов В этом пункте рассмотрены различные подходы к построению средних линий и их воздействие на различные свойства, описанные в пункте 2.2.Гомотопность Алгоритмы утоньшения обеспечивают гомотопность, поскольку удаляются только те воксели, которые не меняют топологию объектов. Поскольку методы, основанные на дистанционных картах, не выделяют скелет напрямую, сохранение топологии зависит от последующих шагов – обрезки и связывания. Очевидно, что алгоритмы, основанные на минимальных остовых деревьях не сохраняют топологию, потому что они не могут создавать петель. Средние линии, построенные алгоритмами, основанными на общеполевых методах, могут быть несвязными даже для односвязных объектов [15], так как этот класс алгоритмов сильно зависит от разрешения изображений, а также от погрешностей при вычислениях.^ Инвариантность при изометрических преобразованиях Направленные методы утоньшения чувствительны к ориентации объекта. Окончательный результат (конечные точки, число ветвей и их местоположение) зависит от порядка, в котором обработаны различные направления. Дистанционные карты, диаграммы Вороного и методы, основанные на характеристиках полей, не зависят от ориентации объекта. Во всех случаях, затрагивающих дискретные представления объектов, конечное представление воксельной сетки допускает небольшую погрешность при преобразовании объектов. В результате даже при том, что алгоритмы выделения средних линий не чувствительны к ориентации, сами входные данные уже несут некоторую погрешность из-за преобразования. Эта погрешность обнаруживается на границе преобразованного объекта, и этот эффект подобен эффекту поверхностного шума.Восстанавливаемость Средняя линия или средняя поверхность трехмерного объекта захватывает локальное симметричное представление в объекте через различные типы элементов: участки поверхности в скелете представляют симметрические пластинчатые области исходной формы, в то время как отдельные кривые в скелете соответствуют цилиндрическим (трубчатым) областям формы. Очевидно, что независимо от используемого метода выделения, полная и точная реконструкция исходного объекта не возможна при наличии информации, сохраненной в одной только средней линии. Так как скелет содержит только сегменты кривой, плоские части объекта не могут быть восстановлены от него. Цилиндрические формы (то есть, формы, которые могут быть точно представлены обобщенными цилиндрами), представляют специальный класс объектов, которые могут быть точно восстановлены от одного только скелета. Общие формы могут только быть приближены обобщенной цилиндрической реконструкцией. Ясно, что более плотный скелет кривой приведет к более точному результату. При восстановлении с помощью подхода наращивания шаров [31] необходима информация дистанционной карты для определения радиуса шара, который будет выращен из каждого вокселя скелета. В этом отношении, методы, основанные на дистанционных картах, имеют преимущество перед другими методами, потому что эта информация доступна.Толщина Алгоритмы утоньшения могут непосредственно построить тонкий скелет (при использовании утоньшающих шаблонов). Параллельные алгоритмы утончения, которые удаляют все простые воксели сразу, возможно, не в состоянии достигнуть соответствующего представления из-за ограничений топологии. На рисунке 4 имеем прямоугольник, ширина которого четное число вокселей. На последнем шаге процесса утоньшения средняя линия будет шириной в 2 вокселя. Хотя все воксели этой кривой «простые» точки, удаляя их полностью, мы бы удалили всю среднюю линию. На данном этапе никакие другие «простые» точки не могут быть удалены, и скелет не представлен в 1D. У направленных методов утончения предусмотрена эта проблема: один ряд вокселей в средней линии будет удален, а второй ряд будет сохранен в последующих шагах. Методы, основанные на дистанционных картах и диаграммах Вороного не представляют скелет в 1D. Для обоих методов необходима постобработка по уменьшению количества вокселей [39].Центрированность Алгоритмы утоньшения и методы полевых характеристик не гарантируют центрированность. В случае направленного утоньшения, центрированность зависит от порядка применения различных направлений. В случае общеполевых методов, которые рассматривают области, отличные от ближайших точек границы, центрированность также не гарантируется. Методы, использующие дистанционные карты могут лучше достигать центрированности, потому что информация о центрах (максимальных шаров) включена в дистанционную карту. Геометрические методы напрямую вычисляют контактные точки (точки, которых касаются границы максимальных вписанных сфер) также могут достигать центрированности. Методы, основанные на диаграммах Вороного, зависят от выбора плотности поверхности объекта: плотный объект дает более отцентрированную среднюю линию, но увеличивает время работы. Проблемы с центрированностью возникают [39] особенно в регионах, где топология объекта изменяется между последовательными множествами уровней. Это также зависит от разрешения (расстояние между двумя последовательными множествами уровней).^ Покомпонентная дифференциация Способность различать различные компоненты средней линии зависит от способности обнаруживать точки сочленения, т.е. точки, в которых соединяются две или более линии. Алгоритмы утоньшения непосредственно могут классифицировать обрабатываемые точки как точки сочленения. Методы, основанные на дистанционных картах сами по себе не могут определять тип точек построенного скелета. Обычно данная классификация происходит на этапе постобработки [19]. Тем не менее, переход размещения для этих классов методов чувствителен к шуму. Метод множеств уровня может также непосредственно определить точки сочленения (как центры построенных множеств уровней).Связность Связность обычно гарантируется всеми классами алгоритмов. Некоторые алгоритмы (утоньшения, алгоритм множеств уровня) явно поддерживают связность во время выполнения, тогда как для других необходима постобработка.Надежность Алгоритмы утоньшения, а также алгоритмы, основанные на дистанционных картах и диаграммах Вороного, чувствительны к шумам и генерируют много ненужных ответвлений в скелете. Некоторые подходы используют постобработку получившихся скелетов [28]. Общеполевые подходы менее восприимчивы к шуму из-за большого количества включенных усредняющих основных вычислений. Эти методы являются более чувствительными к разрешению, поскольку средняя линия в объектах может привести к неустойчивости в численных расчетах. Многие из этих алгоритмов, описанных в литературе, как правило, иллюстрируется лишь несколькими примерами и не протестированы на большой базе данных общих 3D объектов (например, базы данных 3D-моделей [40]). Таким образом, остается неясным, как надежны в целом эти алгоритмы в отношении выбора их параметров.Гладкость Из-за дискретного характера объе