10 Границы формы (Лекции 2016 года)

Генерация признаков формы наоснове анализа границ• Исходное описание образа в виде бинарногоизображения• Выделение границ образа• Построение признакового описания на основеанализа границ1Выделение формы на основебинаризацииПримеры полутоновых изображений (вверху) и полученных наоснове их обработки бинарных изображений (внизу)2Дискретное представление формыНепрерывное и дискретное представление формы3Растровая решётка1. Растровой решёткой называется квадратная решётка Ζ ,2состоящая из точек евклидовой плоскости с целочисленнымикоординатами.2.

В растровой решётке две точки называются непосредственнымисоседями (или просто соседями), если евклидово расстояниемежду ними равно 1.3. В растровой решётке две точки называются косвеннымисоседями, если расстояние между ними равно2.4Растровая решётка и структурысоседства4.4-смежностью (или сильной смежностью) называетсяструктура соседства, при которой соседними точкамисчитаются только непосредственные соседи.5. 8-смежностью (или слабой смежностью) называетсяструктура соседства, при которой соседними точкамисчитаются как непосредственные, так и косвенные соседи.Структуры соседства точек растровой решётки: 4-смежность и 8-смежность.5Граф смежности множества точекP ⊂ Z 2 – множество точек в растровой решётке.G = P, E – граф, вершинами которого являются точки из P , арёбрами – прямолинейные отрезки, соединяющие все пары соседнихвершин.

Соседство вершин задаётся принятой структурой соседства.Граф G называется графом смежности множества точек P .Графы смежности для 4-смежности и 8-смежности6Связность множества точек6. Множество точек в растровой решётке называется связным,если его граф смежности является связным.7. Два множества точек в растровой решётке называютсяразделёнными, если их объединение не является связным.Связные и разделённые множества точек7Дискретная фигураРассмотрим бинарное изображение на растровой решётке,задаваемое двухцветной раскраской точек.

Множество чёрныхточек растровой решётки изображает объекты, а множество белыхточек – фон.Дискретнойфигуройназываетсямаксимальноесвязноеконечное множество чёрных точек в растровой решётке.8Граничные точки дискретнойфигурыТочка дискретной фигуры называется граничной, если онаимеет соседнюю точку, не принадлежащую фигуре в 4смежной структуре соседства.Граничные точки дискретной фигуры9Задача построения границы• Необходимо не только найти все граничные точки, но иупорядочить их вдоль края фигуры.• При этом граница фигуры может состоять из несколькихсвязных компонент (внутренние и внешние контура).• На изображении может быть несколько фигур.Решение задачи включает два этапа:1.Поиск границы2.Прослеживание границы10Поиск границы• Задача поиска состоит в том, чтобы найти хотя бы однуграничную точку для каждого граничного контура.• Поиск достаточно вести только среди горизонтальныхпар смежных точек.• Поиск может быть выполнен построчнымсканированием бинарного изображения.

Построчноесканирование – это просмотр всех строк дискретнойсцены сверху вниз и всех точек в строках слева направо11Прослеживание границыПрослеживание границы лужи12Симплексное прослеживаниеПрослеживание катящимся треугольником (симплексом)13Начальный треугольник• Входными данными для начала прослеживания является горизонтальнаяпара разноцветных точек: L = ( L.x, L.

y ) – левая точка (чёрная), аR = ( R.x, R. y ) – правая точка (белая). Чёрные точки лежат слева, абелые справа по ходу прослеживания.• Третья вершина T = (T .x, T . y ) начального треугольника выбираетсятак, чтобы вершины треугольника L, R, T образовали правую тройку,т.е. располагались против часовой стрелки.RTLTLRTRДиагональное направлениеДля диагонального направления:для антидиагонального:LTLRАнтидиагональное направлениеT .x = R.x, T .

y = R. y + ( R.x − L.x) ,T .x = L.x, T . y = L. y + ( R.x − L.x) .14Переворот треугольника• Переворот выполняется через сторону треугольника RT илиLT , причём через ту из них, у которой концевые точки имеютразные цвета (через разноцветную сторону).• Новый треугольник является центрально симметричным старомуотносительно центра стороны, через которую выполняетсяпереворот.RRLTNNLTT + ( L − R ) если T чёрнаяN =T + ( R − L ) если T белая15Новый треугольник- треугольник на шаге m ,( Lm+1 , Rm+1 , Tm+1 ) - треугольник на шаге( Lm , Rm , Tm )m + 1, Lm , если Tm белаяLm+1 = Tm , если Tm чернаяTm , если Tm белаяRm+1 =  Rm , если Tm чернаяTm+1 = N m16Завершение прослеживанияУсловиесовпадениезавершениевновь( Lm+1 , Rm+1 , Tm+1 )спроцессаобразованногоначальнымпрослеживания:треугольникатреугольником( L0 , R0 , T0 ) , т.е.

Lm+1 = L0 , Rm+1 = R0 , Tm+1 = T0 .17След трассировки3837036 34 32 30135 33 31 29245367238 10 12 22911 13 213914(а)(б)1516172827262524201918(в)Пройденное при прослеживании множество точекS = ( L0 , R0 , T0 , T1 , T2 ,K, Tm ) называется следом трассировки.18Продолжение поиска границы(а)(в)(д)(е)(б)(г)Найденные горизонтальные граничные пары (верхний ряд),матрица пометок (нижний ряд).Условие: в найденной горизонтальной граничной паре должнабыть хотя бы одна непомеченная точка.19Аппроксимация границымногоугольниками20Минимальные разделяющиемногоугольники21Первая вершина минимальногоразделяющего многоугольника53846211191213454443423337394130 34 353638402916214632202224234948101518193575150471417522625283127Первая угловая – черная точка в первой граничной пареДля каждой угловой точки определяется сектор обзора – перваябелая и первая чёрная точки в списке вслед за угловой.22Алгоритм вытягивания границы1.

Перебор точек следа трассировки, расположенных вследза угловой;2. Для каждой точки следа проверка на попадание в секторобзора и корректировка сектора обзора;3. Процесс завершается, когда очередная угловая точкасовпала с начальной.23Коррекция сектора обзораКоррекциясектора обзора(а)(б)(в)(г)Появление новойугловой точкиСохранениестарого сектораобзора(д)(е)24Вычисление угловых точек25Вычисление признаков формы помногоугольной границе1. Длина границы (периметр)2. Площадь фигуры3. Округлость фигуры4. Энергия изгиба5.

Количество углов6. Количество отверстий7. Признаки Фурье26Геометрические признакиV0 ,V1 ,K,Vn - вершины многоугольника, V0 = Vn ,Vi = ( xi , yi ), i = 0,K, n - координаты вершин,nПериметр: P = ∑ ( xi − xi −1 ) 2 + ( yi − yi −1 ) 2i =11 n−1Площадь: S = ⋅ ∑ [(Vi − V0 ) × (Vi +1 − V0 )],2 i =1где [a ⋅ b] = a x ⋅ by − a y ⋅ bx - векторное произведениевекторов a = (a x , a y ) и b = (bx , by ) .P2Округлость: γ =4π ⋅ S1 n−1 2Энергия изгиба: E (n) = ∑ k i , ki = θ i +1 − θ i .P i =027Признаки ФурьеРассмотрим последовательность комплексных чиселu k = xk + i ⋅ y k .Для n точек uk определим ДФП:2πf l = ∑ u k exp − i ⋅ ⋅ l ⋅ k  , l = 0,1,..., N − 1.Nk =0Получим f l – Фурье-описание границы.N −128Свойства признаков ФурьеРассмотрим, как изменяется f l при сдвиге, повороте, масштабированиии сдвиге начальной точки.Сдвиг описывается следующим образом: x k′ = x k + ∆x , y k′ = y k + ∆yи u k′ = u k + ∆u ′ .

Тогда1, при l = 0f l′ = f l + ∆uδ (l ), где δ = .0, при l ≠ 0При l = 0 f 0′ ≠ f 0 , т.к.f 0′ = f 0 + ∆uδ (0 ) = f 0 + ∆u ≠ f 0 .При l ≠ 0 f l′ = f l , т.к.f l′ = f l + ∆uδ (l ) = f l + ∆u ⋅ 0 = f l29Поворот описывается следующим соотношением: u k′ = u k ⋅ exp( jθ ) .Следовательно, f l′ = f l ⋅ exp( jθ ) , т.е. поворот не меняет модулей, аименно f l′ = f l .Масштабирование описывается следующим соотношением:u k′ = a ⋅ u k . Следовательно, f l′ = a ⋅ f l .

Т.к.f j′f i′= a,=aиfjfiто масштабирование не меняет соотношенияf i′ f i= .f j′ f jСдвиг начальной точки определяется следующим образом: u k′ = u k −k .2π⋅ k0 ⋅ l ,Следовательно f l′ = f l ⋅ exp − j ⋅N0т.е. сдвиг начальной точки сохраняет модули: f l′ = f l .3031.