ЛЕКЦИИ_LUN
.pdf
Лекция 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 |
|
|
|
|
Лекция 14.
14 Определение границ объектов на изображении
14.1 Выделение контуров
Наиболее важная операция, предшествующая сегментации, идентификации и классификации объектов на изображении Интуитивно – всякая точка (пиксель) на изображении, находящаяся в области
резкого изменения интенсивности (уровня серого), может быть отнесена к контурной точке. Для двумерной непрерывной функции ее производная в точке указывает на направление в сторону максимального значения, а перпендикулярное ему направление – будет определять направление контура
f |
|
f x |
|
f y |
fx cos f y sin |
r |
|
x r |
|
y r |
|
Максимальное значение производной обеспечивается условием
f
0r
Выделение контура – формула описывает, как же направлена граница. Если хотим выделить границу, то выбираем точку, где производная имеет максимум (одномерная). Если плоскость – то нужно найти максимум производной в двумерном случае.
Это приводит к уравнению для угла направления |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
f y |
|
fx |
sin g |
f y |
cos g |
0 |
|
g |
tan 1 |
|
|
|||
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
fx |
|
f |
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
2 |
|
|
|
|
|
|
|
|||
|
|
|
fx |
f y |
|
|
|
|
|
|
||
r |
max |
|
|
|
|
|
|
|
|
|
|
|
Задача – найти эквивалентные этой формуле (дискретные) цифровые операторы.
Определяем угол, под которым эта функция имеет максимальный подъем Само максимальное значение – корень из суммы квадратов.
Градиентные операторы.
Функция оценки градиента дискретного двумерного изображения может выполняться с помощью двух масок, наложение которых на изображение позволяет определить значение производной в двух взаимно перпендикулярных направлениях
g m, n 
g12 m, n g22 m, n
g tan 1 g2 m, n g1 m, n
Переписывание формул не а координатах, в в m,n – мы работаем в дискрете.
Часто значение производной оценивается по формуле
g m, n g1 m, n g2 m, n
Наиболее часто применяемые операторы:
Prewitt:
1 0 |
1 |
1 1 1 |
|||||
1 |
0 |
1 |
|
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
1 |
0 |
1 |
|
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
Слева дифференцирование по х, справа дифференцирование по у. Интересует максимум производной. Формула не правильная, но мы ей пользуемся.
Sobel:
1 |
0 |
1 |
1 2 |
1 |
||||
2 |
0 |
2 |
|
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
1 |
|
1 |
2 |
1 |
|
|
|
|
|
|
|
|
|
|
Изотропный:
1 |
|
1 |
1 |
|
|
|
|
|||||||
0 |
|
|
2 |
1 |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
2 0 |
2 |
|
|
0 |
0 |
|
|
0 |
|
|||||
|
1 |
0 |
1 |
|
|
1 |
|
2 |
|
1 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Сверху: С усилением центрального направления. Изотропный – по Пифагору корень из 2х.
В результате для каждого пикселя изображения будет получено значение
градиента и его направление. Пиксель будет отнесен к точке контура в том |
|
случае, когда его значение превышает некоторое пороговое значение |
|
1, |
m, n I g |
m, n |
|
0, |
иначе |
I g m, n ; |
g m, n t |
Как правило, порог составляет несколько (5…8) процентов от максимального значения градиента на всем изображении.
Много проблем с выбором порога Что такое порог?
Компас-операторы Компас-операторы определяют значения производных в нескольких
(четырех) направлениях, значение градиента приравнивается максимальной из этих производных, а его направление – направлению этой производной Варианты компас-операторов
1 0 |
1 |
1 1 0 |
1 1 1 |
0 |
1 |
1 |
|||||||||
1 |
0 |
1 |
1 |
0 |
1 |
|
0 |
0 |
0 |
|
1 0 |
1 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
1 |
|
0 |
1 |
1 |
|
1 |
1 |
1 |
|
1 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вместо того, чтобы работать с углом тетта (указывает уровень максимального возрастания). Компасных операторов всего 4, важно зацепиться за модуль производной, а не за знак.
Варианты компас-операторов (только северного направления):
1 |
1 |
1 |
5 |
5 |
5 |
||
|
1 |
2 |
1 |
|
3 0 |
3 |
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
3 |
3 |
3 |
||
|
|
|
|
|
|
|
|
14.2Операторы Лапласа для выделения контура
Ксожалению, градиенты 1-го порядка работают хорошо лишь тогда, когда переход от одного уровня серого к другому достаточно крутой. Однако переходная зона может быть широкой и тогда более надежными становятся градиенты 2-го порядка.
Хорош в местах, где есть переход от минуса к плюсу: преодоление нуля – максимум первой производной.
В этом случае часто используется оператор Лапласа
2 f |
|
2 f |
|
2 f |
|
|
x2 |
|
y 2 |
Три варианта дискретной реализации оператора Лапласа
0 |
1 |
0 |
1 |
1 |
1 |
1 |
2 |
1 |
||||
1 |
4 1 |
1 8 |
1 |
2 |
4 2 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
|
1 |
1 |
1 |
|
1 |
2 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Суммы всех коэффициентов маски обязаны равняться нулю - выполняют функцию определения 2й производной.
Контурные точки – точки пересечения нуля или один из локальных экстремумов.
Но!! Производные 2-го порядка очень чувствительны к шуму. Кроме того, пороговое отсечение 2-й производной приводит к двойной линии контура.
2я производная очень чувствительна к шуму. Если сигнал зашумлен, то лучше Лаплас не применять.
Информация об угле направленности контурных линий может быть получена поиском точек пересечения нуля 2-ой производной вдоль произвольного направления.
2 fr 2
2 fx2
sin
cos |
2 |
|
2 |
f |
sin cos |
2 |
f |
sin |
2 |
|
|
x y |
y2 |
|
|||||||
|
|
|
|
|
|
|
||||
14.3 Операторы выделения одиночных линий
Эти операторы настроены на выделение участков границы, а также на соединение контурных точек в линию. Наиболее распространенный дискретный оператор выделения линий:
1 |
1 |
1 |
2 |
1 |
1 |
1 2 |
1 |
1 |
1 |
2 |
|||||
|
2 |
2 2 |
|
1 2 |
1 |
1 |
2 |
1 |
1 2 |
1 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
1 |
2 |
|
1 |
2 |
1 |
|
2 |
1 |
1 |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Проходят всеми 4мя масками и из 4х результатов выбирают лучший.
14.4 Отслеживание контурных точек Граница – замкнутая кривая, состоящая из контурных точек. Граница объекта
– важнейшая характеристика при анализе, необходимая для расчета различных геометрических признаков – таких как периметр, площадь и т.д.
Алгоритм описания границы для бинарного изображения:
1)Начало – любая точка, принадлежащая контуру
2)Поворот налево + шаг (один пиксел)
3)Если новая точка находится внутри объекта – повтор п.2
4)Если новая точка находится вне объекта – поворот направо + шаг
5)Вернуться к пунктам 2,3
6)Продолжать до тех пор, пока очередная точка не совпадет с начальной
14.5Алгоритмы соединения точек контура
взамкнутую линию
Результатом проведения операций по выделению контуров с помощью
градиентных операторов (1-го или 2-го порядка) возможна ситуация, при которой границы представлены лишь отдельными участками, между которыми – пропуски. Задача состоит в воссоединении контурных точек в (замкнутую) границу Результат компас-оператора выделения контурных точек – модуль градиента и угол, под которым возможно направление границы – перпендикулярное направлению возрастания градиента. Угол может принимать значение, кратное 45
Алгоритм соединения строится на оценке на каждом шаге величины целевой функции, которая в данном случае равна значению градиента в каждом из трех возможных направлений шага, то есть (+45 , 0 ,-45 ).
Более общий алгоритм для воссоединения контурных точек, удаленных друг от друга на значительное расстояние. В этом случае могут быть альтернативные варианты проведения границы.
Задача ставится как задача динамического программирования, в которой критерием выбора управляет целевая функция, оценивающая “эффект” от выбора того или иного пути соединения краевых точек Функция цели в этом случае выглядит так
|
|
|
|
|
N |
|
|
N |
|
|
|
N |
|
||||
x1...xN , N |
|
g xk |
|
|
|
|
xk |
xk 1 |
|
|
d xk , xk 1 |
|
|||||
|
|
|
|
||||||||||||||
|
|
|
|
|
k 1 |
|
|
k 2 |
|
|
|
k 2 |
|
||||
|
g x |
k |
|
|
- модуль градиента в точке, |
|
|
|
|
||||||||
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
xk - угол, под которым направлена граница в точке, d xk , xk 1 - величина шага от одной точке к другой,
Функция цели
N |
|
|
N |
|
|
N |
|
||||
x1...xN , N |
|
g xk |
|
|
|
|
xk |
xk 1 |
|
d xk , xk 1 |
|
|
|
|
|
||||||||
k 1 |
|
|
k 2 |
|
|
k 2 |
|
||||
,
-- весовые коэффициенты, имеющие смысл «платы» за изменение направления границы и изменение шага (предпочтительным является путь по прямой – причем по горизонтали или вертикали)