«Применение ит в обработке медицинских изображений» (стр. 3 из 7)

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

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

Связность

Это свойство является следствием гомотопии. Если средняя линия соответствует односвязной компоненте, то она должна быть связной.

Помехоустойчивость

Как показано на рисунке 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], средняя линия рассчитывается путем морфологической эрозии диаграмм Вороного на основе геодезической функции.