Козловский А. Н. Алгоритм обнаружения вершины угла на основе аппроксимации контура бинарного изображения // Международный научный журнал "Интернаука". - 2018. - №20. https://doi.org/10.25313/2520-2057-2018-20-4379
Технические науки
УДК 004.932
Козловский Антон Николаевич
магистр технических наук
Kazlouski Anton
Master of Engineering Science
АЛГОРИТМ ОБНАРУЖЕНИЯ ВЕРШИНЫ УГЛА НА ОСНОВЕ АППРОКСИМАЦИИ КОНТУРА БИНАРНОГО ИЗОБРАЖЕНИЯ
VERTEX DETECTION ALGORITHM BASED ON BINARY IMAGE CONTOUR APPROXIMATION
Аннотация. Задача обнаружения вершины угла является одной из центральных проблем цифровой обработки изображений. Рассматривается модификация разработанного автором алгоритма обнаружения вершины угла. Предложено использовать алгоритм прослеживания контура бинарного изображения на основе анализа окрестности Мура. Это позволило улучшить правила начала и завершения прослеживания, а также правила определения претендента вершиной угла. Показано, что предложенный алгоритм является более быстродейственным по сравнению с алгоритмом разработанным автором ранее.
Ключевые слова: проективная инварианта, вершина угла, окрестность Мура, прослеживание контура.
Summary. The vertex detection task is one of the central problems of image processing. This paper presents the modified version of the developed by the author algorithm for vertex detection. It is suggested to use the Moore-neighbor tracing algorithm. This has improved starting and stopping criteria, as well as rules for determining the candidate as the vertex. It was shown that the proposed algorithm takes less time in comparison with the algorithm developed by the author earlier.
Key words: projective invariant, vertex, Moore neighborhood, contour tracing.
Последние достижения в развитии аппаратного и программного обеспечения сделали возможным практическое использование различных информационных систем, направленных на поддержку принятия решений. Алгоритмы цифровой обработки изображений находят все более широкое применение в научных и прикладных исследованиях в различных областях деятельности человека. Исследователи всего мира уделяют внимание их разработке. В области компьютерного зрения проблема обнаружения характерной черты изображения является одной из фундаментальных, так как является ключевым этапом решения различных задач. В ее качестве выступают геометрические понятия, такие как: вершина угла, кривая, поверхность и другие. Вершина угла представляется координатами одного отсчета изображения. Это позволяет устанавливать соответствие между разными множествами вершин углов с наименьшими вычислительными затратами. Проективное отображение сохраняет вершину угла. Поэтому разработка алгоритма обнаружения вершины угла инвариантного относительно проективного искажения актуальна в научном и практическом плане.
Алгоритм обнаружения вершины угла используются при решении задач: обнаружения и распознавания простого объекта, совмещения изображений и многих других.
Целью статьи является улучшение разработанного автором алгоритма обнаружения вершины угла на основе аппроксимации контура бинарного изображения направленными отрезками, для более быстродейственного выделения. В начале работы показана актуальность решаемой задачи. Далее во втором разделе приводится краткий обзор основных алгоритмов обнаружения вершины угла на изображении. Постановка задачи приведена в разделе 3. В разделах 4-7 описаны разработанные автором алгоритмы: обнаружения вершины угла, определения отсчета бинарного изображения претендентом на вершину угла, кодирования контура претендента на вершину угла и определения претендента вершиной угла. Отметим, что в основе алгоритма кодирования контура претендента на вершину угла (раздел 5) лежит прослеживания конечного контура бинарного изображения на основе анализа окрестности Мура. Результаты тестирования показаны в разделе 8. В 9-ом разделе представлены выводы работы.
Из математики известно, что проективное отображение сохраняет вершину угла, кроме случаев его превращения преобразованием в развернутый или полный углы. Однако известные в литературе алгоритмы обнаружения вершины угла [1–12] не обладают инвариантностью относительно проективного отображения. Отметим ранее разработанный автором алгоритм, выделяющий вершину угла инвариантно относительно проективного отображения [13]. Это достигается за счет выполняемой аппроксимации контура направленными отрезками. Математическая модель контура изображения подробно рассматриваются в работе [14].
При решении многих ключевых задач цифровой обработки изображений важнейшую роль играет вершина угла. Ее обнаружение отличается сложностью. Проведенный анализ [1–15] показал, что вершина угла v определяется с помощью некоторого алгоритма обработки исходного изображения, представленного в бинарном виде. В частности, вершина угла может быть выделена на изображении I в случае равенства значения первой или второй производной функции f нулю: f’(x) = 0 или f”(x) = 0, x Î W.
Под изображением I будем понимать непрерывное отображение f: W → R, W Ì Rd, где d – это его пространственная размерность, а функция f имеет компактный носитель.
Вершина угла v – это точка O, откуда берут начало два и более луча или вектора; где сходятся два и более отрезка; где две и более прямых, лучей или отрезков пересекаются.
Задача 1. Пусть нам дано изображение I. Необходимо обнаружить и локализовать вершину угла v (V{vi}) исходного изображения.
Трудность обнаружения вершины угла v на изображении I обусловлена сложностью разработки алгоритма обнаружения точки O, с учетом требования равенства значения первой или второй производной функции f нулю. Поскольку функция f известна только в дискретных отсчетах, то невозможно вычислить ее производную до тех пор, пока она не будет определена. При этом приближение ее производной можно определить лишь с ограниченной точностью. На практике используются различные маски для численного приближения производной функции f, в частности, дифференциальный оператор: Превитта [15], Собеля [15], Робертса [16] и др.
При обнаружении вершины v угла на изображении I возникают ошибки двух родов. Ошибка первого рода заключается в отклонении основной гипотезы, в то время как она справедлива, т. е. вершина угла v объекта изображения I не была обнаружена.
Ошибка второго рода заключается в принятие основной гипотезы, в то время как она не верна, т. е. произошло ошибочное обнаружение вершины угла v объекта изображения I. Эти ошибки оцениваются на основе коэффициентов k1 и k2: k1 = N/R и k2 = L/R, где N – количество необнаруженных вершин углов; L – количество определенных ложных вершин углов; R – общее число вершин углов изображения I, N, L и R ÎΝ.
Рассматривается модификация разработанного автором алгоритма обнаружения вершины угла v. Выполняемая аппроксимация контура бинарного изображения направленными отрезками позволяет достигать инвариантность относительно проективного искажения. Его отличительной особенностью является применение алгоритма прослеживания контура на основе анализа окрестности Мура [17-18].
Окрестность отсчета (i, j) изображения I или окно обработки w – это множество его отсчетов, содержащее сам отсчет (i, j), и близкие (в каком-либо смысле) к нему отсчеты исходного изображения.
Алгоритм обнаружения вершины угла на основе аппроксимации контура бинарного изображения направленными отрезками (Ag. 1) включает следующие шаги:
Шаг 1. Выделить контур как границу объекта изображения I;
Шаг 2. Определить претендент r на вершину угла v;
Шаг 3. Сформировать код контура претендента r на вершину угла v;
Шаг 4. Если код контур корректен, то определить является ли претендент r вершиной угла v. Иначе алгоритм завершается.
Рассмотрим эти шаги подробнее.
Одним из возможных путей выделения контура на изображении I является применение алгоритма обнаружения края Кэнни [19] к исходному изображению. Ширина контура равняется одному отсчету изображения. Подробно задача выделения контура как границы объекта изображения рассмотрена в работах [14; 19-20].
Разработанные автором алгоритмы определения отсчета бинарного изображения претендентом r на вершину угла и кодирования контура претендента r на вершину угла, лежащие в основе второго и третьего шага, подробно рассматриваются ниже.
Определение претендента r вершиной угла v выполняется, на четвертом шаге работы алгоритма Ag. 1, посредством разработанных автором правил. В их основе лежит аппроксимации полученного на предыдущем шаге кода контура направленными отрезками.
Алгоритма Ag. 1 опирается в своей работе на следующие параметры:
Временная сложность алгоритма Ag. 1 равна O(n).
В основе рассматриваемого алгоритма лежит анализ контура бинарного изображения, выполняемый в окне обработке w при сканировании исходного изображения I представленного в бинарном виде в порядке построчной развертки – слева направо в строке и сверху вниз по строкам.
В случае выполнения нескольких условий отсчет (i, j) бинарного изображения относится к одному из двух типов претендентов r на вершину угла v: претендент первого r1 или второго r2 типа (рис. 1). В их основе лежит дифференциальный оператор Робертса [16]. Здесь, i – это номер столбца, j – это номер строки.
a б
Рис. 1. Схемы определения произвольного отсчета бинарного изображения претендентом r на вершину угла v: a) первый тип r1; б) второй тип r2
На рис. 1 рассматриваемый отсчет (i, j) бинарного изображения обозначен крестиком, а также отсчеты c: (i+1, j) и (i, j+1) или (i–1, j) и (i, j+1), образующие вершину угла v отмечены черными квадратами. Необходимым условием определения отсчета (i, j) претендентом r на вершину угла v является равенство значений отсчетов c единице. Достаточное условие есть выполнение дополнительных критериев, в частности, значения отсчетов, обозначенные нулем и пятеркой на рис. 1, не равны единице одновременно. Выполняемый анализ обусловлен присущими изображению различного рода шумами, например, эффектом ложного контура [21].
Отсчеты c претендента r на вершину угла v могут образовывать произвольный угол, за исключением развернутого и полного углов. Пусть отсчет c0 = (i, j+1), а отсчет c1 = ,,,.
Алгоритм определения произвольного отсчета бинарного изображения претендентом первого или второго типа на вершину угла (Ag. 2) состоит из следующих шагов:
Шаг 1. В случае если значение отсчета (i, j+1), расположенного по отношению к текущему отсчету (i, j) сканирования, равняется единице. Тогда, в первом случае, если значение отсчета (i+1, j) равно единице, то обнаружены отсчеты c претендента первого типа r1. Во втором случае, если значение отсчета (i–1, j) равняется единице, то обнаружены отсчеты c претендента второго типа r2. В противных случаях алгоритм завершается;
Шаг 2. Выполняется в случае, если на шаге 1 были обнаружены отсчеты с претендента первого типа r1. Тогда, если значение одного из отсчетов (i+2, j–1) или (i–1, j+2) равняется нулю и значения отсчетов (i–1, j) и (i, j–1) или (i+1, j+2) и (i+2, j+1) не равняются единице одновременно. При этом отсутствуют отсчеты подобные текущим отсчетам c ((i+1, j) и (i, j+1)), расположенные по отношению к ним: слева ((i, j) и (i–1, j+1)) и справа ((i+2, j) и (i+1, j+1)) или снизу ((i, j+2) и (i+1, j+1)) и сверху ((i, j) и (i+1, j–1)). Кроме того, значение одного из отсчетов (i+1, j–1), (i–1, j+1) или (i–1, j+2) не равно единице. В этом случае, рассматриваемый отсчет (i, j) является претендентом первого типа r1 на вершину угла v. Алгоритм завершается;
Шаг 3. Выполняется в случае, если на шаге 1 были обнаружены отсчеты c претендента второго типа r2. Тогда, если значение одного из отсчетов (i–2, j–1) или (i+1, j+2) равняется нулю и значения отсчетов (i+1, j) и (i, j–1) или (i–1, j+2) и (i–2, j+1) не равняются единице одновременно. При этом отсутствуют отсчеты подобные текущим отсчетам c ((i–1, j) и (i, j+1)), расположенные по отношению к ним: слева ((i–2, j) и (i–1, j–1)) и справа ((i, j) и (i+1, j+1)) или снизу ((i, j+2) и (i–1, j+1)) и сверху ((i, j) и
(i–1, j–1)). Кроме того, значение одного из отсчетов (i–1, j–1), (i+1, j+1) или (i+1, j+2) не равно единице. В этом случае, рассматриваемый отсчет (i, j) является претендентом второго типа r2 на вершину угла v. Алгоритм завершается.
Временная сложность алгоритма Ag. 2 равна O(1).
Контур Γ претендента r на вершину угла v подразделяется на две части: конечный контур Γa и конечный контур Γb. Начальным отсчетом a0 конечного контура Γa является отсчет c1, a0 = c1, а начальным отсчетом a0 конечного контура Γb является отсчет c0, a0 = c0 (рис. 2).
a б
Рис. 2. Контур бинарного изображения: a) контур 1; б) контур 2
Длины конечных контуров Γa и Γb полагаются равными и не превышают заданное число элементов n. Их кодирование осуществляется стандартными ЭВ [20] согласно предложенному способу (рис. 3) на основе 8-связного цепного кода Фримана [20-21].
Рис. 3. Нумерация и кодирование направлений 8-связного цепного кода Фримана
На рис. 3 код для каждого из направлений 8-связного цепного кода Фримана указан в скобках.
В литературе известно большое количество алгоритмов прослеживания контура бинарного изображения [17-18; 20–22], в частности, на основе анализа окрестности Мура [17-18], Розенфельда [20], Павлидиса [22]. Каждый, из них имеет свои достоинства и недостатки. Целью его применения, является прослеживание конечных контуров Γa и Γb, где длина каждого из которых не превосходит n элементов (в частности, 8). Поэтому в первом приближении нам подойдет любой из отмеченных алгоритмов. Однако среди них выделим алгоритм на основе анализа окрестности Мура [17; 18], позволяющий выполнять обнаружение следующего элемента контура на основе осмотра отсчетов окрестности его текущего элемента, как по часовой стрелке, так и против нее. При этом возможно определить начальное и конечное направления осмотра. Все это хорошо дополняет алгоритм Ag. 2.
Алгоритм кодирования контура претендента на вершину угла (Ag. 3) включает следующие шаги:
Шаг 1. Задать отсчет a0 конечных контуров Γa и Γb, а также начальное и конечное направления осмотра обнаружения следующего элемента контура a1;
Шаг 2. Выполнить прослеживание и кодирование конечного контура Γa;
Шаг 3. Если значение размера кода контура ∆Γa меньше n. Тогда в случае если рассмотрены все возможные начальные направления осмотра, то полученный код удаляем и алгоритм завершается, в противном случае задаем значение нового начального направления (следующие по порядку осмотра) и продолжаем с шага 2. Иначе выполняем шаг 4.
Шаг 4. Выполнить прослеживание и кодирование конечного контура Γb;
Шаг 5. Если значение размера кода контура ∆Γb меньше n. Тогда в случае если рассмотрены все возможные начальные направления осмотра, то полученный код удаляем и алгоритм завершается, в противном случае задаем значение нового начального направления (следующие по порядку осмотра) и выполняем шаг 4. Иначе алгоритм завершается.
Рассмотрим эти шаги подробнее.
Прослеживание контура выполняется на основе алгоритма анализа окрестности Мура [17]. Кодирование контура выполняется на основе описанного выше способа (см. рис. 3). Правила начала и завершения прослеживания контура бинарного изображения подробно представлены ниже.
Правила начала прослеживания контура бинарного изображения:
Правила завершения прослеживания контура бинарного изображения:
Временная сложность алгоритма Ag. 3 равна O(n).
Сопоставление претендента r вершине угла v выполняется посредством разработанных автором правил, подразделяющихся на две категории: соответствия претендента ложной вершине угла и соответствия претендента вершине угла. В их основе лежит аппроксимация кода контуров ∆Γa и ∆Γb направленными отрезками.
Алгоритм определения претендента вершиной угла (Ag. 4) состоит из следующих шагов:
Шаг 1. Выполнить правила соответствия претендента ложной вершине угла. В случае выполнения любого из них считаем, что рассматриваемый претендент r не является вершиной угла v и алгоритм завершается;
Шаг 2. Выполнить правила соответствия претендента вершине угла. В случае выполнения любого из них считаем, что рассматриваемый претендент r является вершиной угла v и алгоритм завершается.
Пусть значения кодов следующих направлений 8-связного цепного кода Фримана: 1, 3, 5 и 7 (см. рис. 3), формируют множество С = {1, 3, 5, 7}.
Правила соответствия претендента ложной вершине угла:
Правила соответствия претендента вершине угла:
Временная сложность алгоритма Ag. 4 равна O(1).
Тестирование алгоритмов Ag. 1 и алгоритма [13] выполнялось со следующими значениями параметров: n = 8, wk = 1 и mx = my = 3. Выделение контура изображения осуществлялось на основе алгоритма обнаружения края Кэнни [19], использующегося со значениями порогов: T1 = 0 и T2 = 0,35. Ширина контура равняется одному отсчету изображения. Использовалась база из 100 различных реальных изображений.
Тесты показали, что представленный в данной работе алгоритм Ag. 1 сопоставим по точности обнаружения с ранее разработанным автором алгоритмом [13]. Для обоих алгоритмов k1 = 0,07 и k2 = 0,09. Однако отличается меньшим временем обработки. Произошло увеличение быстродействия в среднем в 2,1 раза.
Алгоритм Ag. 1 находит свое практическое применение при решении задачи обнаружения и распознавания простого объекта на изображениях, а также в задачах дистанционного зондирования [23–25].
Заключение. Предложена модификация разработанного автором алгоритма обнаружения вершины угла на изображении, состоящая в применении алгоритма прослеживания контура на основе анализа окрестности Мура. Это позволило упростить критерии обнаружения вершины угла. В частности, правила начала и завершения прослеживания контура. Проведенное тестирование показало, что разработанный автором алгоритм обнаруживает вершину угла с меньшим временем обработки по сравнению с алгоритмом разработанным автором ранее.
Источник финансирования исследования. Данное исследование было самофинансировано на средства самого автора.
Литература