Книги по разным темам Pages:     | 1 | 2 | Непрерывное скелетное представление изображения с контролируемой точностью Леонид Местецкий, Иван Рейер Тверской Государственный Университет Тверь, Россия L.Mest@ru.net границы области, а непрерывное распространение огня Аннотация моделируется дискретным процессом последовательного сжигания соседних черных точек растра. Процесс В работе рассматривается задача УстрижкиФ непрерывного построения скелета дискретного образа реализуется в скелетного представления изображения с контролируемой различных алгоритмах лутончения [2], в алгоритме точностью. Скелет чрезвычайно чувствителен к локальным дистанционных карт [3]. Следует отметить, однако, что свойствам границы образа. Поэтому при построении получаемые при этом дискретные скелеты обладают скелетного представления большое внимание уделяется следующими недостатками. Во-первых, расстояние между выделению в скелете части, отражающей фундаментальные точками растра при их построении измеряется не в структурные свойства образа, и удалению элементов, евклидовой метрике, а в зависимости от используемого появление которых обусловлено шумовыми эффектами.

понятия 4- или 8-соседства точек растра, в метрике l1 или l.

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

представления не проводится.

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

формализации понятия УфундаментальнойФ части скелета и Полезность понятия скелета давно и хорошо известна, выделении в скелете аппроксимирующей изображение методам вычисления и использования скелетов посвящено многоугольной фигуры УбазовогоФ скелета, огромное количество работ, начиная с первой работы Блама аппроксимирующего УфундаментальнуюФ часть с заданной [5]. Однако все, кто так или иначе пытался применить точностью.

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

1. ВВЕДЕНИЕ Особую роль при этом играет кривизна границы. С каждой Математически строгое понятие скелета определено для точкой локального максимума кривизны (в частности с замкнутой плоской области: это множество тех ее точек, для точкой излома) границы, связана отдельная ветвь скелета.

которых существует не менее двух равноудаленных Получается, что две области, имеющие несущественные для ближайших точек границы области. Из этого следует, что глаз различия границы, например, за счет шумов, имеют каждая точка скелета является центром окружности, лежащей принципиально различные в смысле топологической в области и касающейся ее границы в двух или более точках структуры скелеты. Вместе с тем, сравнительный анализ этих (так называемой максимальной пустой окружности). Для того различающихся скелетов показывает, что в них присутствуют чтобы распространить понятие скелета на дискретные общие ветви, которые и определяют фундаментальные растровые образы, используется другое определение, свойства структуры образа. Задача состоит в том, чтобы основанное на метафоре пожара в прерии [1].

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

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

области, в которых сходятся два или более огненных фронта, При этом явные критерии определения существенных и являются по определению точками скелета. Эквивалентность несущественных элементов скелета не формулируются, и этих определений, очевидно, следует из того соображения, отсечение осуществляется на основе эвристических правил что точка схода фронтов равноудалена от ближайших точек [6]. В результате не может быть оценена точность возгорания на границе. Пожар в прерии служит основой вычисленных скелетов, что затрудняет их дальнейшее для определения и построения скелета в терминах растровых использование, например, в задачах распознавания бинарных изображений. Подмножество черных точек растра изображений. Целью нашей работы является построение рассматривается как дискретный образ некоторой замкнутой корректного критерия выделения существенных элементов области, граничные точки растрового пятна - как образ скелета, а также метода, реализующего такое выделение.

International Conference Graphicon 2003, Moscow, Russia, Идея решения этой задачи состоит в следующем. Определим 1) хаусдорфово расстояние между областями и для каждой замкнутой области некоторую -окрестность - H(,) множество всех замкнутых областей, отличающихся от 2) хаусдорфово расстояние между границами областей исходной не больше чем на заданную величину в некоторой метрике (используется хаусдорфова метрика [7]). Далее H(,).

элемент скелета области будем считать существенным, если Определение 2: -коридором области P будем называть он присутствует (т.е. имеет близкие элементы) в скелетах замкнутую -окрестность границы области.

всех областей, входящих в эту окрестность. Практический результат, который мы хотим получить - это метод Определение 3: -расширением полигональной области P + определения существенных элементов в скелете области, P (рис. 1) будем называть объединение P и -коридора P.

составляющих так называемый базовый скелет этой области.

Таким образом, мы рассчитываем найти ту скелетную P + = P U{ - коридор P}.

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

1. Для растрового изображения построить аппроксимирующую замкнутую область. Точность аппроксимации при этом задается (например, равной размеру одного пикселя растрового образа). А вид аппроксимирующей области в этом случае не имеет решающего значения. Проще всего воспользоваться многоугольной фигурой, поскольку для построения ее скелета существуют эффективные алгоритмы [8, 9, 4].

2. Построить скелет аппроксимирующей области.

Рисунок 2: Шип выпуклого угла.

3. Провести стрижку скелета с контролируемой точностью c помощью предлагаемого метода. Точность стрижки Рассмотрим - выпуклый угол полигональной области P. pi i при этом задать в соответствии с точностью - вершина этого угла, Bi - биссектриса этого угла.

аппроксимации растрового изображения.

Рассмотрим a - точку на Bi, удаленную от вершины угла pi на, и b - точку пересечения прямых, параллельных сторонам Работа выполнена при поддержке Российского Фонда угла и находящихся на расстоянии от сторон угла (рис. 2).

фундаментальных исследований (РФФИ), проект 02-0100667.

Определение 4: отрезок ab будем называть шипом Si выпуклого угла.

i 2. БАЗОВЫЙ СКЕЛЕТ ПОЛИГОНАЛЬНОЙ ОБЛАСТИ. ЕГО СВОЙСТВА Определение 5: -сужением P - полигональной области P (рис. 1) будем называть объединение разности области P и Пусть P - некоторая полигональная область, а - некоторое коридора P с шипами всех выпуклых углов P.

положительное число.

P - = (P \ { - коридор P}) U S, U Conc(P) где Conc(P) - множество всех выпуклых углов P.

Рисунок 1: -расширение и -сужение полигональной области.

Определение 1: Будем называть область, имеющую Рисунок 3: Максимальные -допустимые круги для кусочно-гладкую гарницу, -близкой области с кусочнополигональной области.

гладкой границей, если выполнены следующие условия:

International Conference Graphicon 2003, Moscow, Russia, точках A и B. Рассмотрим проходящие через A и B радиусы Определение 6: круг C будем называть -допустимым кругом круга С, pA+ и pB+.

для P, если:

Справедлива следующая 1) H (P, P U C) ;

Теорема 2: Скелет произвольной -близкой P области 2) H (P,(P U C)) пересекает хотя бы один из радиусов pA+ и pB+. Точка этого Определение 7: круг C будем называть максимальным - пересечения удалена от центра круга p не более чем на допустимым кругом для P (рис. 3), если:

/cos 2( /2), 1) C является -допустимым кругом для P;

где - угол между сторонами полигональной области, 2) C не содержится целиком ни в каком другом -допустимом которых касается круг C=(p,rЦ).

для P круге.

Теорема 2 позволяет сделать следующие выводы о свойствах Справедливы следующие утверждения.

базового скелета. Для каждого ребра базового скелета существует некоторое >, такое, что в -окрестности ребра Утверждение 1: Если C=(p,r) - максимальный -допустимый находятся точки скелета любой -близкой P области. Кроме круг для P, то C=(p,rЦ) - максимальный пустой круг для P.

того, через -окрестность каждого ребра базового скелета для Утверждение 2: Если C=(p,r) - максимальный пустой круг любой -близкой P области будет проходить ветвь скелета для P, то C=(p,r+) - максимальный -допустимый круг для этой области, максимальные пустые круги которой касаются P.

сегментов границы, проходящих через -окрестности Следствием этих утверждений является следующая сайтов границы P, бисектором которых является данное ребро. Таким образом, можно говорить, что каждое ребро Теорема 1: Множество центров максимальных -допустимых базового скелета аппроксимирует некоторую ветвь скелета кругов для P совпадает со множеством центров любой -близкой P области с точностью. Если же взять max максимальных пустых кругов для P.

- максимальное из всех таких, то базовый скелет можно Определение 8: круг C будем называть базовым кругом для рассматривать как аппроксимацию существенной части полигональной области P, если выполнено следующее:

скелета любой -близкой P области с точностью max.

1) C является максимальным -допустимым кругом для P;

3. ПОСТРОЕНИЕ БАЗОВОГО СКЕЛЕТА 2) Пересечение C с P - не содержится целиком ни в одном максимальном -допустимом для P круге, не совпадающем с Теперь рассмотрим, каким образом можно выделить в кругом C.

скелете аппроксимирующей полигональной области базовый Определение 9: множество центров всех базовых кругов для скелет.

P будем называть базовым скелетом P и обозначать MAbase(P).

Отметим, что согласно Теореме 1 базовый скелет P является подмножеством скелета P.

C C C' A+ A D p Рисунок 5: Круг C не является базовым.

Базовый круг C с центром на бисекторе пары сайтов, B образующей выпуклый угол, не должен иметь пересечений с -окрестностью вершины угла, то есть должен пересекать соответствующий шип. В противном случае он не был бы B+ базовым, так как нашелся бы другой -допустимый для P Рисунок 4: К Теореме 2.

круг, содержащий пересечение C с P - (рис. 5).

Рассмотрим C=(p,r) - произвольный базовый круг для P Соответственно, возникает следующая идея построения радиуса r с центром в точке p. Как было показано выше, с базового скелета. Выберем одну из терминальных вершин этим кругом связан круг C=(p,rЦ), который является скелета и начнем движение по инцидентному этой вершине максимальным для P и касается границы P по крайней мере в ребру вглубь области, УстираяФ ребро. При этом мы двух точках (рис. 4). Пусть круг C касается границы P в рассматриваем поведение максимального -допустимого круга, центр которого совпадает с точкой скелета, в которой International Conference Graphicon 2003, Moscow, Russia, мы находимся. Если при движении по ребру этот круг 5. ЛИТЕРАТУРА пересекает шип соответствующего выпуклого угла, мы [1] U. Montanari. A method for obtaining skeletons using a прекращаем движение. Такую операцию проведем с каждым quasi-Euclidean distance. J. ACM, 15(4), pp. 600-624, 1968.

терминальным ребром. Остановка происходит и в том случае, если мы дошли до противоположной вершины скелета и [2] L. Lam, S.-W. Lee, C. Y. Suen. Thinning methodologies: A стерли ребро целиком, а пересечения с шипом не произошло.

comprehensive survey. IEEE Trans. PAMI, 14(9), Sept 1992.

При этом степень противоположной вершины понижается и в [3] R. L. Ogniewicz, O. Kbler. Hierachic Voronoi skeletons.

дальнейшем может стать равной 1. Из такой вершины мы Pattern Recognition, 28, pp. 343-359, 1995.

тоже начнем движение, проверяя круг на пересечение уже не с одним шипом, а с двумя. [4] Л. М. Местецкий. Непрерывный скелет бинарного растрового изображения. Труды межд. конф. "Графикон98", Москва, 1998.

[5] H. Blum. A transformation for extracting new descriptors of shape. Models for the Perception of Speech and Visual Form, pp.

362--380. MIT Press, 1967.

[6] D. Shaked, A. M. Bruckstein. Pruning medial axes.

Computer Vision and Image Understanding, Vol. 69, No. 2, 1998, pp. 156-169.

[7] А. Н. Колмогоров, С. В. Фомин. Элементы теории функций и функционального анализа. - М.: Наука, 1981.

[8] D. G. Kirkpatrik. Efficient computation of continuous skeletons. In 20th Annu. Symp. Found. Computer Sci., pp. 18-27, 1979.

Рисунок 6: Скелет полигональной области.

[9] D. T. Lee Medial axis transformation of a planar shape.

Процедура построения заканчивается, когда в скелете не IEEE Trans. PAMI, PAMI-4, No. 4, Jul 1982.

останется ни одной терминальной вершины, из которой можно начать движение. Оставшиеся ребра образуют Авторы базовый скелет (рис. 6-7).

Местецкий Леонид Моисеевич - зав. кафедрой информационных систем и технологий ТвГУ E-mail: L.Mest@ru.net Рейер Иван Александрович - аспирант В - РАН.

E-mail: reyer@forecsys.ru

Abstract

Pages:     | 1 | 2 |    Книги по разным темам