Выделение и описание контуров

Материал из Техническое зрение
Перейти к: навигация, поиск

Содержание

Выделение контуров на бинарных изображениях.

Это задача, двойственная выделению связных областей. При этом считается, что $\textit{контурная точка области - это любая точка, принадлежащая области, в окрестности которой имеются точки, не принадлежащие данной области}$.


Отслеживающие алгоритмы.

$\textit{Отслеживающие алгоритмы }$основаны на том, что на изображении отыскивается объект (первая встретившаяся точка объекта) и контур объекта отслеживается и векторизуется. Достоинством данных алгоритмов является их простота, к недостаткам можно отнести их последовательную реализацию и некоторую сложность при поиске и обработке внутренних контуров. Пример отслеживающего алгоритма - "алгоритм обхода контура", или "алгоритм жука", - приведен на рис. 4. "Жук" начинает движение с белой области по направлению к черной. Как только он попадает на черный элемент, он поворачивает налево и переходит к следующему элементу. Если этот элемент белый, то жук поворачивается направо, иначе - налево. Процедура повторяется до тех пор, пока жук не вернется в исходную точку. Координаты точек перехода с черного на белое и с белого на черное и описывают границу объекта.


4-1-4.jpg

Схема работы отслеживающего алгоритма "жука"

4-1-5.jpg

Различные ситуации, встречающиеся в ходе сканирования


Сканирующие алгоритмы.

$\textit{Сканирующие алгоритмы}$ основаны на просмотре (сканировании) всего изображения и выделении контурных точек без отслеживания контура объекта.

Рассмотрим алгоритм, основанный на разработанной схеме хранения полосы изображения в памяти ЭВМ и нахождении контурных точек в процессе движения полосы по всему изображению. Для обработки информации в полосе различают два случая: выявление ситуации в полосе изображения и ее разрешение. В полосе одновременно хранятся две строки изображения (текущая и предыдущая). Анализируются $x$-координаты черных серий обеих строк в порядке их возрастания (слева направо) и выявляются пять ситуаций, которые могут возникнуть.

Ситуация "начало" возникает в том случае, когда черная серия текущей строки полностью покрывается белой серией предыдущей строки (рис. 5$\textit{а}$).

Для ситуации "продолжение" характерно частичное перекрытие черных серий обеих строк (рис. 5$\textit{б}$).

Если две соседние черные серии текущей строки покрываются черной серией предыдущей строки, возникает ситуация "ветвление" (рис. 5$\textit{в}$).

Ситуация "слияние" выявляется в том случае, когда черная серия текущей строки касается двух соседних черных серий предыдущей строки (рис. 5$\textit{г}$).

Ситуация "конец" возникает, когда белая серия текущей строки полностью покрывает черную серию предыдущей строки (рис. 5$\textit{д}$).


Обрабатываемые строки представлены в виде массивов структур, куда входит координата $x$ начала/конца черной серии и адрес буфера, предназначенного для сбора и хранения информации по одной ветке (части контура), которая пересекает обрабатываемую строку. В буфере содержатся тип ветки (левая или правая в зависимости от расположения черной серии связной компоненты), ее внутренний номер, параметры отслеженной части контура (длина, площадь, габариты) и ее координатное описание, адрес буфера парной ветки, которая является частью того же контура, и некоторые другие параметры.

При выявлении ситуации "начало" из стека свободных буферов выбирают два (для левой и правой веток). Каждая пара веток имеет свой уникальный номер, который возрастает по мере появления новых веток.

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

При выявлении ситуации "ветвление" точки ветвления обрабатываются по аналогии с ситуацией "начало".

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

Ситуация "конец" свидетельствует о том, что либо закончилось отслеживание внешнего контура, либо сливаются ветки одного контура. Обработка производится по аналогии с обработкой ситуации "слияние".

Прослеживание контуров на полутоновых изображениях.

Методы выделения контуров уже были подробно рассмотрены в разделе 3.4. Результатом работы процедур выделения контуров является контурный препарат, представляющий собой множество не связанных друг с другом краевых точек. Для дальнейшей работы с контурами необходимо из множества выделенных краевых точек сформировать кривые (ломаные).

Задача прослеживания контуров (edge following) также является объектом отдельных исследований, поскольку является одной из ключевых в работе с контурами. В настоящее время разработано достаточно много различных алгоритмов прослеживания контуров, которые можно разделить на несколько групп:

  1. методы, использующие информацию о значении и направлении градиента в каждой точке;
  2. методы, использующие динамическое программирование для решения задачи прослеживания контура;
  3. методы поиска оптимального пути в графе. Каждая краевая точка представляется вершиной графа.

Рассмотрим, например, алгоритм прослеживания контуров, относящийся к первой группе. Суть метода заключается в предположении о том, что точки, принадлежащие одному контуру, должны иметь близкие значения модуля и направления вектора градиента. Рассматривается окрестность точки $\langle i,j \rangle$ размером $M \times M$ (обычно используют окрестность $3 \times 3$), и в каждой точке $\langle k,l \rangle$ окрестности проверяются следующие условия:


  1. $\left| {G_{i,j} -G_{k,l} } \right|\le \Delta G$,
  2. $\left| {\alpha _{i,j} -\alpha _{k,l} } \right|\le \Delta \alpha ,$

где $\langle i,j \rangle$ - центральная точка окрестности; $G$ - модуль градиента; $\alpha $ - направление градиента в точке; $\Delta G$ - предельное значение расхождения модулей градиента в точках $\langle i,j \rangle$ и $\langle k,l \rangle$; $\Delta \alpha $ - предельное значение расхождения направлений векторов градиента в точках $\langle i,j \rangle$ и $\langle k,l \rangle$.

Если в точке $\langle k,l \rangle$ выполняются описанные выше условия, то считается, что пара точек принадлежит одному контуру. Для упрощения вычисления направления края весь диапазон возможных значений $0,\ldots, 360$° разбивается на 8 направлений (секторов). Каждое направление отличается от соседнего на $45$ °. При этом поиск точек, принадлежащих одному контуру, следует проводить среди точек соседних секторов, имеющих расхождения значений градиентов меньше заданного порога. Результатом выполнения процедуры прослеживания является дискретное представление контуров, при котором каждый контур определяется множеством точек, из которых он состоит.

Полученный контурный препарат в дискретном представлении далее подвергается анализу на предмет выделения на нем точек ветвления (точки соединения кривых). Наличие точек ветвления свидетельствует о сложной геометрической структуре объекта, существенно затрудняет формальное описание и сам процесс распознавания объектов. Выделение точек ветвления позволяет значительно упростить структуру объекта путем разбиения контура на множество кривых.

Выделение линеаментов.

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

Иллюстрацией современного подхода к выделению прямых линий может, например, служить улучшенная модификация классического метода в котором сначала определяются края путем свертки с двумя простыми $2\times 2$ масками, затем пикселы группируются в так называемые области поддержки линии (ОПЛ). Каждая ОПЛ включает пикселы с одинаковой ориентацией градиента. Прямая линия на ОПЛ определяется путем пересечения двух плоскостей: первая из них аппроксимирует поверхность интенсивности, вторая, горизонтальная плоскость, представляет средневзвешенную интенсивность.

Рассмотрим вариант этого метода, состоящий из следующих шагов.


  1. Вычисление градиента исходного изображения.

Обозначим: $f$ - исходное изображение; $f^{x}$, $f^{y}$ - производные исходного изображения по координатам $x$ и $y$ соответственно; $m$ - модуль градиента; $a$ - направление градиента.

Производные изображения вычисляются с помощью оператора Собела :

$$ \begin{gather}\tag{1} {f}^x = \left[ {\begin{matrix} {-1} & 0 & 1 \cr {-2} & 0 & 2 \cr {-1} & 0 & 1 \cr \end {matrix} }\right]* f, \quad {f}^y = \left[ {\begin{matrix} {-1} & {-2} & {-1} \cr 0 & 0 & 0 \cr 1 & 2 & 1 \cr \end {matrix} }\right] * f . \end{gather} $$

В (1) знаком * обозначена операция свертки изображения с маской.

Выбор такого оператора обусловлен простотой его реализации, а также тем, что он обладает свойством подавления шумов.

Затем вычисляются модуль и направление градиента $$ \begin{gather}\tag{2} m_{ij} =\sqrt {(f_{ij}^x )^2+(f_{ij}^y )^2} ,{\begin{array}{*{20}c} & {a_{ij} = arctg \frac{f_{ij}^y }{f_{ij}^x }}\\ \end{array} }, \end{gather} $$

$i,j=1,\ldots, N$, $N$ - размер изображения.

В зависимости от знаков $f_{ij}^x $, $f_{ij}^y$ направление градиента $a_{ij} $ преобразуется в диапазон от $0$ до $2\pi $. На рис. 6 показаны результаты вычисления градиента исходного изображения.

4-1-6.jpg

Результаты вычисления градиента изображения: $\textit{а}$ - модуль градиента, $\textit{б}$ - направление градиента

  1. Группировка пикселов в ОПЛ путем деления пространства ориентации градиентов на сектора с углом $\phi $. Из-за слабой чувствительности оператора Собела к истинной ориентации градиента создаются два варианта разбиений: $p^{(1)}$ и $p^{(2)}$, которые далее объединяются. Разбиение на сектора производится по формулам

$$ p_{ij}^{(1)} =\left[ {\frac{a_{ij} }{\phi }} \right], \qquad {p_{ij}^{(2)} =\left[ {\frac{a_{ij} +2\pi +\frac{\phi }{2}}{\phi }} \right]}, $$ здесь [{\ldots}] - целая часть числа.

Экспериментально найдено, что значение $\phi =30$° является достаточным для представления ОПЛ, т.е. изображение $p^{(1)}$ содержит номера секторов $0,\ldots, 11$, а изображение $p^{(2)}$ содержит номера секторов $12,\ldots, 23$. На рис. 7$\textit{а,б}$ показаны результаты такого разбиения.

  1. Определение с помощью стандартного алгоритма восьмисвязной разметки областей которые образуются в результате выполнения шага 2), а именно, изображения $p^{(i)}$ $(i=1,2)$ разбиваются на $N_i $ областей, которые обозначим $R_k^{(i)} \quad (k=1,\ldots, N_i )$. Каждая область $R_k^{(i)} $ является ОПЛ и определяет проходящую через нее линию, которую обозначим $l_k^{(i)} $.
  2. Создание путем слияния изображений $p^{(1)}$ и $p^{(2)}$ нового изображения $p$ (рис. 7$\textit{в}$). Каждый пиксел $\langle i,j \rangle$ изображения $p$ получает значение $p_{ij}^{(1)} $ или $p_{ij}^{(2)}$ в зависимости от того, какая из ОПЛ - $R_k^{(1)} $ или $R_l^{(2)} $ - cодержит более длинную линию. Здесь $k,l$ - номера областей на изображениях $p^{(1)}$ и $p^{(2)}$, соответственно, содержащие пиксел $\langle i,j \rangle$. Этот прием позволяет несколько уменьшить ошибки в окончательном представлении ОПЛ, связанные с неточной дискретизацией направлений вычисленных градиентов.
  3. Разбиение изображения $p$ на $N$ областей, которые обозначим $R_k $ $(k=1,\ldots, N)$, и определение всех таких областей с помощью стандартного алгоритма восьмисвязной разметки.
  4. Определение с субпиксельной точностью проходящей через область ОПЛ $R_k $ линии $l_k $ с помощью описанного ниже алгоритма.

4-1-7.jpg

Результаты формирования областей поддержки линий: $\textit{а}$ - изображение $p^{(1)}$ ; $\textit{б}$ - изображение $p^{(2)}$ ; $\textit{в}$ - изображение $p$

Вначале для каждого пиксела $(x,y)$ из $R_k $ вычисляются параметры плоскости, аппроксимирующей поверхность интенсивности исходного изображения $f$.

Плоскость представляется уравнением

$$ \begin{gather}\tag{3} z=ax+by+c. \end{gather} $$

Реальная форма поверхности интенсивности изображения $f$ в области $R_k $ обычно отличается от плоскости, поэтому удобнее найти уравнение плоскости как решение методом наименьших квадратов задачи минимизации ошибки аппроксимации: $$ f(x_i ,y_i )=ax_i +by_i +c+\epsilon _i , $$ или, в матричной форме, $$ \textrm{\textbf{l}}=\textbf{G}\textrm{\textbf{p}}+ \boldsymbol{\epsilon} , $$ где $\textbf{G} =\left[ {..{\begin{array}{*{20}c} {x_1 } & {y_1 } & 1 \\ {...} & {...} & {...} \\ {x_n } & {y_n } & 1 \\ \end{array} }} \right]$ - матрица плана, состоящая из координат пикселов области $R_k $ ($n$ - число пикселов области), $\textbf{l}$ - вектор наблюдений длиной $n$, состоящий из значений яркости изображения $f$ в области $R_k , \boldsymbol{\epsilon} $ - вектор ошибки длиной $n$, определяющий отличие проводимой плоскости от реальной функции яркости в области $R_k $.

Целесообразно ввести также $\textbf{H}$ - весовую матрицу размером $n\times n$, состоящую из значений модуля градиента $H_{ii} =m(x_i ,y_i )$, $H_{ij} =0$, $i\ne j$. В результате пикселы области $R_k $ с большим значением модуля градиента имеют больший "вес" при определении коэффициентов уравнения плоскости. Решение системы нормальных уравнений методом наименьших квадратов имеет вид $$ \textbf{p} = \left[ {abc} \right]^\textrm{Т}=(\textbf{G}^{\textrm{T}}\textbf{HG})^{-1}{\textbf{G}}^{\textrm{T}}{\textbf{HI}}. $$ Как уже говорилось выше, прямая линия в области $R_k $ определяется как результат пересечения найденной плоскости, аппроксимирующей поверхность яркости в области $R_k $, и горизонтальной плоскости, представляющей среднюю яркость в области $R_k $. При вычислении средней яркости "весом" является значение модуля градиента, чем достигается центрирование прямой линии внутри области. Горизонтальная плоскость представляется уравнением

$$ \begin{gather}\tag{4} z=\frac{\sum\limits_{\langle x,y \rangle\in R_k } {m(x,y)f(x,y)} }{\sum\limits_{\langle x,y \rangle\in R_k } {m(x,y)} }=c_1 . \end{gather} $$

Пересечение плоскостей (3), (4) определяет прямую $l_k $ с уравнением $$ dx + ey + f = 0, $$ где $$ d=a, \quad e=b, \quad f=c-c_{1}. $$ Крайние точки отрезка вычисляются путем пересечения прямой линии и сторон минимального прямоугольника, содержащего область $R_k $.

На рис. 8 показаны информативные участки тестового изображения, сформированные по результатам работы алгоритма выделения линий.

4-1-8.jpg

Информативные участки изображения на основе выделенных линеаментов. Показаны линеаменты с длиной более $L$: $\textit{а}$ - $L=6$; $\textit{б}$ - $L=10$; $\textit{в}$ - $L=15$

Производится вычисление для каждого отрезка следующих атрибутов:


  1. крайние точки;
  2. длина;
  3. нормализованные параметры уравнения линии;
  4. угол между линией и осью абсцисс;
  5. средние яркости в полосе с одной и с другой стороны от линии.

На основе этих атрибутов далее формируются отношения между отрезками для более сложной семантической интерпретации двумерного поля.

Способы описания контуров.

Контурные коды

Дискретное представление кривой в виде последовательности точек с координатами $\langle x,y \rangle$ крайне неэффективно. Более эффективным является представление с помощью цепных кодов (chain code) при использовании которых вектор, соединяющий две соседние точки, кодируется одним символом, принадлежащим конечному множеству. Обычно при пользовании цепным кодом рассматривается окрестность точки размером $3 \times 3$ и $4$ или $8$ возможных направлений кодирования (рис. 9).

4-1-9.jpg 4-1-10.jpg
Направления кодирования в цепных кодах:

$\textit{а} - $4$ направления; $\textit{б} - $8$ направлений

Фрагмент контура

Начиная с первой точки, производится обход контура по часовой стрелке, при этом каждая последующая точка кодируется числом $1$ - $8$, в зависимости от своего расположения относительно центральной точки окрестности. Результатом кодирования является последовательность, состоящая из цифр $1$ - $8$. Пример кодирования кривой (рис. 10) при помощи цепного кода: $7 7 1 2 1 0 7 6 6 6 7 1 1 0 0 7 6 7 7 1 1 2 2 3 3 4$.


Данный способ представления кривой имеет следующие недостатки:


  1. зависимость от начальной точки кодирования.
  2. не обладает свойством инвариантности к вращению.
  3. неустойчивость к зашумлению. Локальные изменения контура могут привести к различным результатам кодирования.


Другим способом представления кривой является кусочно-полиномиальная аппроксимация. Задача аппроксимации заключается в отыскании кривой, проходящей вблизи заданного множества точек контура. Кривая разбивается отдельными узлами на отрезки, при этом аппроксимирующая функция на каждом из них имеет вид $$ f(x)=a_0 +a_1 x+a_2 x^2+\ldots +a_n x^n, $$ где $a_n$ - коэффициенты полинома, подлежащие определению на каждом отрезке.

Кусочно-линейная аппроксимация.

Наиболее простым и скоростным методом аппроксимации является кусочно-линейная аппроксимация. В данном случае для каждой пары узлов необходимо определить всего лишь два коэффициента $a_0 $ и $a_1 $, при этом общее число коэффициентов, подлежащих определению, равно $2(n-1)$, где $n$ - общее число узлов.

Например, для кусочно-линейной аппроксимации может быть использован итеративный алгоритм подбора концевых точек. На первом этапе работы алгоритма концевые точки контура $A$ и $B$ соединяются прямой линией. Для всех оставшихся точек вычисляются расстояния до прямой $AB$. Точка, имеющая наибольшее отклонение от прямой $AB$, берется в качестве дополнительного узла. При этом кривая заменяется двумя отрезками $AC$ и $CB$ (рис. 11$\textit{б}$). Процедура продолжается до тех пор, пока максимальное значение отклонения точек меньше заданного порога. Точность аппроксимации прямыми линиями определяется величиной порога.

Основным недостатком кусочно-линейной аппроксимации является то, что аппроксимирующая функция не является гладкой (первые производные терпят разрыв в узлах сетки), а также зависимость результатов аппроксимации от исходных экспериментальных данных. Отсутствие гладкости функции не является существенным ограничением, в то время как зависимость результатов аппроксимации от начальных 4-1-11.jpg

Итеративный подбор концевых точек: $\textit{а}$ - первый этап; $\textit{б}$ - второй этап; $\textit{в}$ - третий этап

условий (точек $A$ и $B$) часто не позволяет использовать данный метод аппроксимации для задач отождествления контуров.


Аппроксимация сплайнами.

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

Рациональным сплайном называется функция $s_R (x)$, которая на каждом отрезке $[x_i ,x_{i+1} ]$ имеет вид $$ s_R (x)=a_i t+b_i (1-t)+\frac{c_i t^3}{1+p_i (1-t)}+\frac{d_i (1-t)^3}{1+q_i t}, $$ где $t=\frac{x-x_i }{h_i }$, $h_i =x_{i+1} -x_i $, $p_i ,q_i $ - заданные числа, $-1<p_i ,q_i <\infty $

Параметры $p_i ,q_i $ определяют свойства рациональных сплайнов: если $p_i ,q_i $ близки к нулю, то рациональный сплайн становится кубическим. Если же параметры $p_i ,q_i $ достаточно велики, то оценки погрешности сплайна сопоставимы со сплайнами первой степени. В большинстве случаев принято полагать $p_i =q_i $.


Функция кривизны.

Одним из важнейших параметров, характеризующих контур, является его $\textit{кривизна}$. Кривизна обладает свойствами инвариантности к сдвигу, повороту и вычисляется по формуле $$ K(x,y)=\frac {f'_x f''_y - f''_x f'_y } {\sqrt{\left( {f'_x}^2+{f'_y}^2 \right)^3}}, $$ где $f'_x , f'_y $ - первые производные по $x$ и $y$ соответственно; $f''_x , f''_y $ - вторые производные по $x$ и $y$;

Для описания контуров часто используют естественное представление кривой. При этом контур представляют в виде одномерной функции какого-либо атрибута от длины дуги. Длину дуги дискретного контура в точке $P(j) = \langle x_j ,y_j \rangle $ можно аппроксимировать следующим образом: $$ l_j =\sum \limits_{i=1}^{j-1} \sqrt {(x_i -x_{i+1} )^2+(y_i -y_{i+1} )^2}. $$ Естественное представление кривой подразумевает отсутствие на контурах точек соединений и разветвлений, в противном случае контур не может быть представлен в виде одномерной функции. Данное ограничение требует введения дополнительных процедур обработки и анализа полученного контурного препарата:


  1. поиск на контурах точек ветвления;
  2. разделения сложных структур на составляющие.


Одним из наиболее часто используемых представлений контура является функция кривизны $K(l)$. Достоинством функции кривизны является инвариантность к сдвигу и повороту, однако кривизна обладает следующими недостатками:


  1. отсутствие инвариантности к масштабу;
  2. проблемы, возникающие при сравнении прямолинейных контуров. Прямолинейные контура не могут быть представлены в виде функции кривизны;
  3. необходимость аппроксимации кривых для точного вычисления производных в точке.

4-1-12.jpg

Функция кривизны

Перегиб.

Одним из недостатков использования функции кривизны является необходимость аппроксимации контура для более точного вычисления первых двух производных в точках. Устранить данный недостаток можно при помощи замены кривизны на другой атрибут, обладающий схожими достоинствами. Аналогом кривизны является величина перегиба (k-curvature) контура в точке, однако для получения величины перегиба не требуется аппроксимация кривой, а используется дискретное представление кривой в виде последовательности пиксельных координат точек контура. Для вычисления значения перегиба в точке $P[i]$ необходимо:


1. выбрать две точки последовательности $P[i-k]$ и $P[i+k]$, равноудаленные от $P[i]$ на $k$ точек;

2. определить наклон в левую $K\{L\}$ и правую $K\{R\}$ сторону от точки $P[i]$

$$ K\{L\}= arctg \left( {\frac{b}{a}}\right); $$

3. вычислить разность между углами наклона $K\{L\}$ и $K\{R\}$

$$ K' =K\{L\}-K\{R\}, $$ где $K'$ - величина перегиба в точке.


Если контур не содержит точек ветвления (соединения), то его можно представить в виде одномерной функции перегиба $K'(l)$ (рис. 13).

Особые точки контуров.

В качестве характерных признаков можно использовать число и положения особых точек контура (точки максимального переги-

4-1-13.jpg

Вычисление перегиба в точке ($k=6$)

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

В данной работе были рассмотрены различные варианты выделения особых точек на полученных контурах. Наиболее простым и быстрым способом является описанный выше поиск точек максимального перегиба при помощи итеративного алгоритма подбора концевых точек. Однако использование данного алгоритма не принесло положительных результатов. Неустойчивость его работы определяется достаточно сильной зависимостью результатов поиска точек от начальных условий (концевых точек контура). Недостаточная помехозащищенность не позволяет использовать данный метод для выделения особых точек на контурах.

Другим, более надежным способом выделения особых точек является поиск экстремальных значений какого-либо атрибута контура. В данной работе использовались локальные экстремумы функции кривизны, для поиска которых необходимо:


  1. Выполнить кусочно-полиномиальную аппроксимацию контура;
  2. Построить функцию кривизны;
  3. Найти все локальные экстремумы кривизны.

Кусочно-полиномиальная аппроксимация кривой позволяет более точно вычислить значения первых двух производных по направлениям в точках, а следовательно, и значение самой кривизны.

Описанный алгоритм выделения особых точек контура обладает инвариантностью к сдвигу и повороту, а также устойчивостью к шумам.

4-1-14.jpg

Функция перегиба

4-1-15.jpg

Локальные экстремумы функции кривизны

Полезные ссылки

  1. ☝ К началу
  2. ☜ Выделение и описание характерных элементов изображения
Личные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты