Использование дистанционных преобразований

Дистанционное преобразование – преобразование, которое каждой точке изображения ставит в соответствие расстояние в заданной метрике до ближайшей точки фона (Рис. 4). Формальная запись:

,

(2.3)

где  – некоторая метрика.

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

Классификация по способу вычисления расстояния:

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

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

· Дистанционные преобразования на основе решения эйконального уравнения [26], где расстояние находится из конечных разностей первого или второго порядков расстояний соседних вокселей

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

Рисунок 4 – Дистанционные карты с использованием а) шахматной метрики

б) (3,4)-метрики Чамфера

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

· методы утоньшения, использующие дистанционную карту для определения приоритета выбора вокселей для удаления [28]

· методы поиска градиента [29] предполагающие выявление районов неоднородного градиента и маркировки таких вокселей в качестве кандидатов на удаление.

· методы вычисления дивергенции используют в [30] в качестве функции приоритета для удаления «простых» вокселей с малым значением дивергенции.

· методы адаптивного утоньшения характеризуются сравнениями между значением дистанционной карты в вокселе и средним значением дистанционной карты его соседей [31].

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

Для связности большинство алгоритмов используют минимальные остовные деревья[32], кратчайшие пути[33] или другие алгоритмы на графах.

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

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