ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.04.2025
Просмотров: 664
Скачиваний: 1
Лекция 16.
16 Описание области, занимаемой объектом, его структуры и формы
16.1 Представление области
1) Запись в виде кода следующего вида Пример: (2,1)2, (2,4)1, (3,0)5, (4,2)2, (4,5)1, (5,3)4, (6,1)2, (6,5)1, (7,0)2;
Где кодовая ячейка имеет вид: (КоординатаX, КоординатаY)Количество пикселей,принадлежащих объекту в строке
2)Представление с помощью проекций (томография)
3)Представление в виде квадратичного дерева
Все изображение (квадратное) разбивается на 4-е части. Каждая из частей получает обозначение “g” (grey - серый), если в области содержатся и черные (black) и белые (white) пиксели; если же в области находятся только черные (белые) пиксели, то область получает обозначение “b” (“w”). Каждая из частей с обозначением “g” делится также на четыре части и т.д.
Пример (то же изображение, что в предыдущем случае): g(wwg(wwbb)w)g(g(wwbw)wg(bwww)g(bbbw)) g(g(bbwb)g(wwwb)g(bbbw)w)g(wg(wbbb)g(bbbw)w)
16.2 Описание структуры объекта
1) Скелетизация Скелет – совокупность точек, равноотстоящих от (локальных) границ
объекта (равны перпендикуляры, опущенные на границы по обе стороны от |
|||||
точки скелета) |
|||||
Алгоритм скелетизации: |
|||||
uk m, n u0 m, n |
min |
uk 1 |
i, j ; i, j |
: |
m, n;i, j 1 |
m,n;i, j |
|||||
u0 m, n u m, n ; |
k 1,2.... |
||||
m, n : uk m, n uk i, j , |
m, n;i, j 1 |
||||
m, n;i, j -расстояние между точками (m,n) и (i,j)
2) Запись в виде соединения примитивов – элементарных структурных фрагментов
16.3Описание формы объекта
1)Геометрические признаки
а) периметр T |
dt |
||||||||||||||||||||||||
x2 t y2 t |
|||||||||||||||||||||||||
б) площадь S dxdy y t |
dx t |
dt x t |
dy t |
dt |
|||||||||||||||||||||
dt |
dt |
||||||||||||||||||||||||
в) радиусы вписанной и описанной окружностей |
Rmin |
Rmax |
|||||||||||||||||||||||
г) компактность |
T 2 |
||||||||||||||||||||||||
4 S |
1 |
T |
2 |
2 |
d 2 y 2 |
d 2 x 2 |
|||||||||||||||||||
\ |
|||||||||||||||||||||||||
E |
k t |
dt, |
k t |
||||||||||||||||||||||
2 |
2 |
||||||||||||||||||||||||
д) граничная (изгибная) энергия |
T |
dt |
dt |
||||||||||||||||||||||
0 |
|||||||||||||||||||||||||
2) Признаки в виде моментов |
|||||||
а) центр масс m |
1 |
m, |
n |
1 |
n , где N – число пикселей в области |
||
N |
N |
||||||
m,n |
m,n |
||||||
б) центральный момент (p+q)-го порядка pq |
m m p n n q |
||||||
в) ориентация – угол момента инерции |
m,n |
||||||
Момент инерции объекта вдоль направления |
|||||||
I m m sin n n cos 2
m,n
Для определения направления, вдоль которого момент инерции принимает минимальное значение, надо приравнять производную момента инерции по углу нулю
dI |
0 |
1 |
2 11 |
||||||||||||||||||||||
arctan |
|||||||||||||||||||||||||
d |
2 |
20 |
02 |
||||||||||||||||||||||
x cos y sin |
max , min |
, max |
, min |
||||||||||||||||||||||
г) описанный прямоугольник |
|||||||||||||||||||||||||
x sin y cos |
|||||||||||||||||||||||||
Длина и ширина прямоугольника определяются по формулам |
|||||||||||||||||||||||||
l max min , |
w max |
min |
|||||||||||||||||||||||
д) описанный эллипс. Большая и малая оси определяются аналогично |
|||||||||||||||||||||||||
прямоугольнику |
2 4 2 |
R |
I |
l |
|||||||||||||||||||||
е) эксцентриситет |
20 |
02 |
11 |
max |
max |
||||||||||||||||||||
S |
R |
I |
w |
||||||||||||||||||||||
min |
|||||||||||||||||||||||||
min |
|||||||||||||||||||||||||
Лекция 15.
15 Представление (запись) границы объекта
15.1 Цепной код Определяются восемь возможных векторов направления - от 000 до 111 (от 0
до 7).
Тогда запись границы объекта будет содержать координату стартовой точки (пикселя) и далее – трехбитовые коды направления очередных шагов Например, граница задается кодом:
1001 1010 111 110 000 001 000 110 101 101 110 011 010 100 010 001
Задача – восстановить кривую Другой (обобщенный) вариант цепного кода – запись функции угла касательной к границе от длины
15.2 Запись границы в виде отрезков прямых линий
Алгоритм:
1)соединить две наиболее удаленные точки контура
2)для каждой из «половинок»- если расстояние от точки (пикселя), наиболее удаленной от линии, соединяющей крайние точки, больше некоторого значения, то эта точка соединяется с каждым из концов, образуя два новых отрезка
3)далее операция повторяется для каждого из образованных отрезков до тех пор, пока не будет удовлетворен критерий аппроксимации криволинейного участка прямой линией
15.3 Описание границы с помощью В-сплайнов В-сплайны представляют собой кусочно-полиномиальные функции, с помощью которых можно аппроксимировать контуры объектов на изображении, используя небольшое количество параметров. Результат – сглаженная кривая.
Пусть t – переменная длины кривой,
x t y t определяют координаты точки в координатной плоскости. Тогда для произвольной точки кривой справедлива запись
n |
t |
||||||||||
z |
t pi Bik |
||||||||||
i 0 |
|||||||||||
t x t , y t |
T |
T |
|||||||||
z |
, |
pi |
pi1, pi 2 |
||||||||
нормализованные В-сплайны k-го порядка могут быть сгенерированы с |
|||||||||||
помощью рекурсивной формулы |
|||||||||||
B |
t |
t ti |
Bik 1 t |
ti k |
t Bi 1k 1 |
t |
, |
k 2,3... |
|||
ik |
ti k 1 ti |
ti k ti 1 |
|||||||||
Bi1 |
t |
1, |
ti |
t ti 1 |
|||||||
0, |
иначе |
||||||||||
Параметр k контролирует порядок полинома на каждом участке (k=3 – квадратичный, k=4 – кубический полином)
Если узловые точки расположены эквидистантно, то есть
ti 1 ti t, |
i |
||||||||||||||||||||||||||||
Тогда |
|||||||||||||||||||||||||||||
Bik t B0k t i , |
i k 1, k,..., n k 1 |
||||||||||||||||||||||||||||
Для единичного шага вдоль кривой |
|||||||||||||||||||||||||||||
0 |
i k |
||||||||||||||||||||||||||||
i n |
|||||||||||||||||||||||||||||
ti i k 1 k |
|||||||||||||||||||||||||||||
i n |
|||||||||||||||||||||||||||||
n k 2 |
|||||||||||||||||||||||||||||
Выражения для однородных В-сплайнов |
|||||||||||||||||||||||||||||
1, |
0 t 1 |
t, |
0 t 1 |
||||||||||||||||||||||||||
B |
t |
B |
t |
2 t, |
1 t 2 |
||||||||||||||||||||||||
01 |
иначе |
02 |
|||||||||||||||||||||||||||
0, |
0, |
иначе |
|||||||||||||||||||||||||||
t |
3 |
, |
0 t 1 |
||||||||||||||||||||||||||
2 |
6 |
||||||||||||||||||||||||||||
t |
|||||||||||||||||||||||||||||
, |
0 t 1 |
3t |
3 |
12t |
2 |
12t 4 |
|||||||||||||||||||||||
, 1 |
t 2 |
||||||||||||||||||||||||||||
2 |
|||||||||||||||||||||||||||||
2 |
6 |
||||||||||||||||||||||||||||
3t |
1.5, |
1 t 2 |
|||||||||||||||||||||||||||
B03 t |
t |
B04 |
t |
3 |
24t |
2 |
60t 44 |
||||||||||||||||||||||
2 |
3t |
||||||||||||||||||||||||||||
3 t |
, |
2 t 3 |
, 2 |
t 3 |
|||||||||||||||||||||||||
6 |
|||||||||||||||||||||||||||||
2 |
|||||||||||||||||||||||||||||
4 t |
3 |
||||||||||||||||||||||||||||
0 |
иначе |
, |
3 t 4 |
||||||||||||||||||||||||||
6 |
|||||||||||||||||||||||||||||
0, |
иначе |
||||||||||||||||||||||||||||
Контрольные точки служат не только коэффициентами разложения по В- сплайнам в приведенной формуле, но и определяют положение вершин многоугольника, аппроксимирующего гладкую границу объекта.
Число контрольных точек для точного воспроизведения заданной границы обычно много меньше, чем число точек, которые определяют гладкую кривую. При этом может быть получено сжатие данных с коэффициентом компрессии порядка 10-100. Для того, чтобы переместить объект (с границей) в пространстве, масштабировать или повернуть на какой-либо угол, достаточно все эти операции проделать с контрольными точками. Многие геометрические признаки объекта на изображении (центр масс, площадь, периметр) могут быть легко рассчитаны по контрольным точкам. Одна из ключевых задач – определить минимальное количество контрольных точек, обеспечивающих В-сплайновое представление границы с заданной погрешностью
15.4 Описание границ методом дескрипторов Фурье Поскольку линия, представляющая границу какого-либо объекта, замкнута
(ее значения будут повторяться с периодом, равным длине периметра |
|||||||||
границы), то она может быть записана в виде ряда Фурье |
|||||||||
Если кривая представлена N точками |
|||||||||
u n x n jy n , |
n 0,1,..., N 1 |
||||||||
то дискретное преобразование Фурье будет иметь вид |
|||||||||
1 |
N 1 |
2 kn |
|||||||
u n |
a k exp j |
, |
0 n N 1 |
||||||
N k 0 |
N |
||||||||
N 1 |
2 kn |
||||||||
a k u n exp |
j |
, |
0 k N 1 |
||||||
n 0 |
N |
||||||||
Комплексные коэффициенты разложения или какая-нибудь их комбинация и называются дескрипторами Фурье. Наиболее типичные геометрические преобразования с исходным объектом на изображении приводят к соответствующим операциям над дескрипторами Фурье.
Преобразование
Перемещение в плоскости
Масштабирование
Замена начальной точки
Вращение
Граница
~ |
n u n u0 |
u |
|
~ |
n u n |
u |
|
~ |
n u n n0 |
u |
|
~ |
n u n exp j 0 |
u |
Дескрипторы Фурье
a |
k a k u0 k |
|||
~ |
||||
a |
k a k |
|||
~ |
||||
~ |
2 n0k |
|||
a |
k a k exp |
j |
||
N |
||||
~ |
||||
a |
k a k exp j 0 |
|||
Из приведенной таблицы видно, что дескрипторы Фурье обладают инвариантными свойствами. Например, модули всех дескрипторов инвариантны к положению начальной точки, вращению. Отношение (комплексного) дескриптора к его модулю инвариантно к масштабированию. Эти свойства могут быть использованы в обнаружении объектов одинаковой формы, независимо от их размеров и ориентации (поворота в плоскости) Однако надо учитывать, что сами по себе амплитуда и фаза дескрипторов в отдельности не могут быть использованы для (взаимно-однозначного) описания границы.
15.5 Сопоставление (сравнение) объектов по их границам Дескрипторы Фурье могут быть использованы для сравнения объектов похожей формы, даже если они имеют различные размеры и отличаются по ориентации в пространстве. Если a k и b k являются дескрипторами Фурье границ двух объектов на изображенииu n и v n ,то по форме они одинаковы (относятся к одному классу), если мала величина, рассчитываемая по формуле:
d u0 , , 0 , n0 |
min |
N 1 |
u n v n n0 exp j 0 |
u0 |
2 |
|
u0 , , 0 ,n0 |
n 0 |