Цифровая обработка изображений
16 Представление (запись) границы объекта
16.1 Цепной код
Определяются восемь возможных векторов
направления - от 000 до 111 (от 0 до 7).
Тогда запись границы объекта будет содержать
координату стартовой точки (пикселя) и далее –
трехбитовые коды направления очередных шагов

Цифровая обработка изображений
Например, граница задается кодом:
1001 1010 111 110 000 001 000 110 101 101
110 011 010 100 010 001
Задача – восстановить кривую
Другой (обобщенный) вариант цепного кода –
запись функции угла касательной к границе от длины

Цифровая обработка изображений
16.2 Запись границы в виде отрезков прямых линий
Алгоритм:
1) соединить две наиболее удаленные точки контура
2) для каждой из «половинок»
- если расстояние от точки (пикселя),
наиболее удаленной от линии,
соединяющей крайние точки, больше некоторого значения,
то эта точка соединяется с каждым из концов,
образуя два новых отрезка
3) далее операция повторяется для каждого из
образованных отрезков до тех пор, пока не будет
удовлетворен критерий аппроксимации криволинейного
участка прямой линией

Цифровая обработка изображений

16.3 Описание границы с помощью В-сплайнов
В-сплайны представляют собой
кусочно-полиномиальные функции,
с помощью которых можно аппроксимировать
контуры объектов на изображении,
используя небольшое количество параметров.
Результат – сглаженная кривая

Цифровая обработка изображений
x? t ?

Пусть t – переменная длины кривой,
определяют координаты точки
y?t ?
в координатной плоскости.
Тогда для произвольной точки кривой
справедлива запись
n
?
?
z ? t ? ?? pi Bik ? t ?
i ?0

?
T
z ? t ? ?? x? t ?, y ? t ? ? ,

?
T
pi ?? pi1 , pi 2 ?

Цифровая обработка изображений
нормализованные В-сплайны k-го порядка могут быть
сгенерированы с помощью рекурсивной формулы

Bik

?
t ? ti ? Bik ? 1 ? t ? ? ti ?k ? t ? Bi ?1k ? 1 ? t ?
?t ? ?
?
,
ti ? k ? 1 ? ti

ti ?k ? ti ?1

k ?2,3...

? 1, ti ?t ? ti ?1
Bi1 ? t ? ??
иначе
? 0,

Параметр k контролирует порядок полинома
на каждом участке (k=3 – квадратичный,
k=4 – кубический полином)

Цифровая обработка изображений
Если узловые точки расположены эквидистантно,
то есть

ti ?1 ? ti ??t , ?i
Тогда

Bik ? t ? ?B0 k ? t ? i ?,

i ?k ? 1, k ,..., n ? k ? 1

Для единичного шага вдоль кривой

0
i?k
?
?
ti ?? i ? k ? 1 k ?i ?n
?n? k ?2
i?n
?

Цифровая обработка изображений
Выражения для однородных В-сплайнов
0 ?t ? 1
? t,
? 1, 0 ?t ? 1
?
B01 ? t ? ??
B02 ? t ? ?? 2 ? t , 1 ?t ? 2
? 0, иначе
? 0,
иначе
?
?
t3
,
0 ?t ? 1
?
6
?
?
t2
3
2
?
3
t
?
12
t
? 12t ? 4
,
0
?
t
?
1
?
?
, 1 ?t ? 2
? 2 2
?
6
? ? t ? 3t ? 1.5, 1 ?t ? 2
? 3
2
B03 ? t ? ??
B04 ? t ? ?? 3t ? 24t ? 60t ? 44
2
, 2 ?t ? 3
? ?3 ? t ? ,
?
2 ?t ? 3
6
?
?
3
2
?
?
4
?
t
??
?
0
иначе
,
3 ?t ? 4
?
6
??
0,
иначе

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

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

Цифровая обработка изображений

Одна из ключевых задач –
определить минимальное количество
контрольных точек,
обеспечивающих В-сплайновое
представление границы с заданной погрешностью

Цифровая обработка изображений
16.4 Описание границ методом дескрипторов Фурье
Поскольку линия, представляющая границу
какого-либо объекта,
замкнута (ее значения будут повторяться
с периодом, равным длине периметра границы),
то она может быть записана в виде ряда Фурье
Если кривая представлена N точками

u ? n ? ?x? n ? ? jy ? n ?,

n ?0,1,..., N ? 1

Цифровая обработка изображений
то дискретное преобразование Фурье будет иметь вид
1
u? n? ?
N

N?1

? 2?kn ?
a? k ? exp? j
?,
?
? N ?
k ?0
N?1
2?kn ?
?
a? k ? ?? u ? n ? exp? ? j
?,
N ?
?
n ?0

0 ?n ? N ? 1
0 ?k ? N ? 1

Комплексные коэффициенты разложения или
какая-нибудь их комбинация и называются
дескрипторами Фурье

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

Граница

u~ ? n ? ?u ? n ? ? u0

Масштабирование

u~ ? n ? ??u ? n ?

Замена начальной
точки

u~ ? n ? ?u ? n ? n0 ?

Вращение

Дескрипторы Фурье

u~ ? n ? ?u ? n ? exp? j? 0 ?

a~? k ? ?a? k ? ? u0? ? k ?

a~ ? k ? ??a? k ?
2?n0 k ?
?
a~ ? k ? ?a? k ? exp? ? j
?
N ?
?

a~ ? k ? ?a? k ? exp? j? 0 ?

Цифровая обработка изображений
Из приведенной таблицы видно, что дескрипторы
Фурье обладают инвариантными свойствами.
Например, модули всех дескрипторов инвариантны
к положению начальной точки, вращению.
Отношение (комплексного) дескриптора к его модулю
инвариантно к масштабированию.
Эти свойства могут быть использованы
в обнаружении объектов одинаковой формы,
независимо от их размеров и ориентации (поворота
в плоскости)
Однако надо учитывать, что сами по себе амплитуда
и фаза дескрипторов в отдельности не могут
быть использованы для (взаимно-однозначного) описания
границы

Цифровая обработка изображений
16.5 Сопоставление (сравнение) объектов по их границам
Дескрипторы Фурье могут быть использованы
для сравнения
объектов похожей формы,
даже если они имеют различные размеры и
отличаются по ориентации в пространстве
Если a? k ? и b? k ? являются дескрипторами Фурье
границ двух объектов на изображении

u ? n ? и v? n ?

Цифровая обработка изображений

то по форме они одинаковы (относятся к одному классу),
если мала величина, рассчитываемая по формуле

? N?1
2?
d ? u0 , ? , ? 0 , n0 ? ? min ? ? u ? n ? ? ?v? n ? n0 exp? j? 0 ? ? u0 ? ?
u 0 ,? ,? 0 , n0
? n ?0
?


Случайные презентации

Файл
319145.ppt
Диплом_Штифанов.ppt
236507.ppt
284981.ppt
292776.ppt




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.