11 Скелет формы (Лекции 2016 года)

Генерация признаков формы наоснове скелетов• Исходное описание образа в виде бинарногоизображения• Построение скелета образа• Построение признакового описания на основеанализа скелета1Классификация формы по границе(а)(в)(б)Классификация фигур по границе:• по размерам и числу граничных контуров,• по локальным характеристикам кривизны и гладкости границы,• по соотношению между периметром и площадью фигур2Недостаточность границы(а)(б)(в)(г)3Серединные оси фигуры4Скелет – множество серединных осей5Пустой круг фигурыПустым кругом фигуры A называется замкнутое множествоточек~S r ( p ) = {q : q ∈ R 2 , d ( p, q ) ≤ r}(а)(б)(в)~S r ( p ) ⊂ A.такое, чтоМаксимальным пустым кругом называется пустой круг, которыйне содержится ни в каком другом пустом круге. Другое название– вписанный круг.6Скелет фигурыСкелетом фигуры называется множество центров всех еёмаксимальных пустых кругов.BABAIIEEFFHHGGCDCD(а)(б)(в)(а) фигура и её граница;(б) примеры максимальных пустых кругов;(в) скелет фигуры.7Скелет – дескриптор формы(а)(б)(в)(г)8Метафора «Пожар в степи»9Скелет дискретной фигуры10Скелетизация через утончение11Принципы алгоритма Розенфельда1.

Имитация пожара в степи путём последовательногоперекрашивания граничных точек объекта2. На каждом шаге перекрашивание всех граничных точек,имеющих смежные фоновые точки с одногонаправления: сверху, снизу, слева или справа3. Перекрашивание только тех чёрных граничных точек,которые имеют две или больше соседних чёрных точек4. Перекрашивание только тех чёрных граничных точек,которые не нарушают связности оставшейся частифигуры. При этом связность и соседство оцениваютсялибо по 4-смежности, либо по 8-смежности12Алгоритм Розенфельда для4-смежной структуры соседства(а) исходный(г) запад(б) север(д) восток(в) юг(е) север13Алгоритм Розенфельда для8-смежной структуры соседства(а) исходный(д) восток(б) север(е) север(в) юг(г) запад(ж) юг(з) север14Концевые и изолированные точки• Граничная точка p называется:(b) северной, (c) восточной, (d) западной, (e) южной.• Граничная точка называется 4-концевой (8-концевой), еслитолько одна из её 4-соседних (8-соседних) точек является чёрной.• Граничная точка называется 4-изолированной (8-изолированной),если среди её 4-соседних (8-соседних) нет чёрных точек.15Простые точкиГраничная точка называется 4-простой (8-простой), если приперекрашивании её в белый цвет не изменяется 4-связность (8связность) остающихся черных точек в пределах её 3×3окрестности.Точка p:(a) 4-простая, но не 8-простая;(b) 8-простая, но не 4-простая;(c) не 8-простая и не 4-простая;(d) 8-простая и 4-простая.16Алгоритм для 4-смежностиПовторять, пока на шагах 1-4 меняется цвет хотя бы одной точки:Шаг 1: (параллельно) Заменить все чёрные точки на белые, еслиони – северные граничные точки, являются 4-простыми, нони 4-изолированными, ни 4-концевыми.Шаг 2: (параллельно) Заменить все чёрные точки на белые, еслиони – южные граничные точки, являются 4-простыми, но ни4-изолированными, ни 4-концевыми.Шаг 3: (параллельно) Заменить все чёрные точки на белые, еслиони – восточные граничные точки, являются 4-простыми, нони 4-изолированными, ни 4-концевыми.Шаг 4: (параллельно) Заменить все чёрные точки на белые, еслиони – западные граничные точки, являются 4-простыми, нони 4-изолированными, ни 4-концевыми.17Алгоритм Зонга-СуняA(p1) – количество переходов0-1 в последовательноститочек p2, p3, …, p9, p2;B(p1) – количество соседнихчёрных точек для точки p1.pi=0 – белая точка, pi =1 – чёрная точка,На каждой итерации выполняются тришага перекрашивания чёрных точек.18Шаги перекрашиванияШаг 1.

Удаление точек на юго-восточной границе и северозападных угловых точек:Точка p1 перекрашивается, если выполняются следующиеусловия:3) p2×p4×p6=01) 2 ≤ B(p1) ≤ 64) p4×p6×p8=02) A(p1)=1Шаг 2. Удаление точек на северо-западной границе и юговосточных угловых точек:3) p2×p4×p8=01) 2 ≤ B(p1) ≤ 64) p2×p6×p8=02) A(p1)=1Шаг 3. Ищутся две чёрные точки по вертикали или горизонтали,которые окружены белыми:1) (1−p9)×p4×p6=13) (1−p3)×p6×p8=12) (1−p5)×p8×p2=14) (1−p7)×p2×p4=119Признаки формыТопологическая структура скелетного графа:• Количество терминальных вершин• Количество вершин третьей степени• Наличие цикловМетрические свойства:• Длины ветвей• Ширина элементов (расстояние от точекскелета до границы).20Проблема устойчивостиМалые изменения формы приводят к существеннымизменениям скелета.21Задача регуляризации скелетаСтрижка скелета:- удаление «шумовых» ветвей;- выделение существенных фундаментальных элементов.22Принципы стрижки скелета1.

Многоугольная фигура2. Скелет фигуры4. Силуэт стриженного скелета3. «Стриженый» скелет фигуры23Базовый скелет фигурыБазовым скелетом фигуры С будем называть такойминимальный укороченный подграф S ′ её скелета S , для силуэтакоторого VS′ выполнено условие H (C,VS′ ) ≤ ε , где ε – заданнаяположительная величина, а H (C,VS′ ) – хаусдорфово расстояниемежду фигурой С и силуэтом VS′ .24Регуляризованный скелет25ПриложенияБиометрическая идентификация по форме ладони26Сравнение формы ладонейСилуэт ладониГраничныймногоугольникα2Скелет ладониα1α3α4α5Гибкий объектНормализацияСравнение27Классификация отпечатка пальцаБинарноеизображениеМногоугольнаяфигураСкелетОсобыеточки28Маршрутизация29Маршрутизация30.