Аннотация: Задача обнаружения характерной черты изображения является одной из центральных проблем цифровой обработки изображений. В статье рассматривается улучшение разработанного автором алгоритма обнаружения вершины угла объекта изображения на основе аппроксимации контура бинарного изображения векторами. В частности, представлены новые правила аппроксимации контура бинарного изображения направленными отрезками, для более точного и быстро действенного обнаружения вершины угла. Приводится краткий обзор основных алгоритмов обнаружения характерной черты изображения. Дается сравнительная оценка этих алгоритмов.
Ключевые слова: сегментация изображения, контурный анализ, объект изображения, характерная черта изображения, вершина угла.
Технические науки
УДК 004.932
Козловский Антон Николаевич
магистр технических наук
Kazlouski A. M.
Master of Engineering Science
АЛГОРИТМ ОБНАРУЖЕНИЯ ВЕРШИНЫ УГЛА НА ИЗОБРАЖЕНИИ НА ОСНОВЕ АППРОКСИМАЦИИ КОНТУРА БИНАРНОГО ИЗОБРАЖЕНИЯ
VERTEX DETECTION ALGORITHM IN IMAGE PROCESSING BASED ON BINARY IMAGE CONTOUR APPROXIMATION
Аннотация: Задача обнаружения характерной черты изображения является одной из центральных проблем цифровой обработки изображений. В статье рассматривается улучшение разработанного автором алгоритма обнаружения вершины угла объекта изображения на основе аппроксимации контура бинарного изображения векторами. В частности, представлены новые правила аппроксимации контура бинарного изображения направленными отрезками, для более точного и быстро действенного обнаружения вершины угла. Приводится краткий обзор основных алгоритмов обнаружения характерной черты изображения. Дается сравнительная оценка этих алгоритмов.
Ключевые слова: сегментация изображения, контурный анализ, объект изображения, характерная черта изображения, вершина угла.
Summary: The salient image feature detection task is one of the central problem of image processing. This paper presents the improvement of the developed by the author the vertex detection algorithm in image processing based on approximation of binary image contour by vector. For example, new rules on approximation with given accuracy of binary image contour by directed segments were developed to more accurately and quickly effective detection of the vertex. Brief emphasis on main image salient feature detection algorithms provided. The comparative evaluation of these algorithms carried out.
Keywords: image segmentation, contour analysis, image object, salient image feature, the vertex.
Введение
В последние десятилетия значительный прогресс в развитии аппаратного и программного обеспечения, а также методик технического зрения сделал возможным практическое использование различных информационных систем, направленных на поддержку принятия решений. Алгоритмы цифровой обработки изображений находят все более широкое применение в научных и прикладных исследованиях в различных областях деятельности человека. Одной из важнейших задач цифровой обработки изображений является разработка алгоритма обнаружения характерной черты изображения, так как ее выделение является ключевым этапом решения различных задач. Поэтому разработка алгоритма обнаружения характерной черты изображения актуальна в научном и практическом плане.
Алгоритмы обнаружения характерной черты изображения используются при решении задачи обнаружения и распознавания объекта на изображении, совмещения изображений и многих других.
В качестве характерной черты изображения выступают отсчет, кривая или объект. В литературе известно большое количество алгоритмов обнаружения характерной черты изображения на основе анализа окрестности его отсчета [1–21]. Их общим недостатком является отсутствие инвариантности относительно проективного отображения.
Целью статьи является улучшение разработанного автором алгоритма обнаружения вершины угла на изображении на основе аппроксимации контура бинарного изображения направленными отрезками [22]. Например, разработаны новые правила аппроксимации с заданной точностью контура бинарного изображения векторами, направленные на повышение результативности и быстродействия обнаружения. Приводится краткий обзор основных алгоритмов обнаружения вершины угла на изображении.
Характерный отсчет изображения
В качестве характерной черты изображения выступает его отсчет. Для дефиниции характерного отсчета изображения воспользуемся понятием окрестности.
Пусть функция f: R2 → R, определенная на множестве W Ì R2 – это изображение I. Под объектом (областью) O на изображении I будем понимать область определения: W Ì R2.
Окрестность отсчета (i, j) изображения I – это множество отсчетов, содержащее отсчет (i, j) и близкие (в каком-либо смысле) к нему отсчеты.
Под характерным отсчетом s изображения I будем понимать отсчет (i, j) с окрестностью Nbhd(i, j), которую можно выделить (каким-либо образом) из остального множества окрестностей {Nbhd(ni)} изображения I.
В литературе известно большое количество алгоритмов обнаружения характерного отсчета изображения [1–22]. Общим недостатком алгоритмов [1–8] является отсутствие геометрического смысла. При этом алгоритмы SIFT [1], PCA-SIFT [2], SURF [3], GLOH [4], DAISY [5] и BRIEF [6] чувствительны к изменению угла, под которым получено изображение. Дескриптора контекст формы [7, 8] инвариантен относительно отображения сдвига, масштаба и поворота, а также устойчив к изменению формы объекта. Дескриптор масштабного пространства кривизны (curvature scale space, МПК) инвариантен к аффинным искажениям и устойчив к помехам [9].
Часто в роли характерной черты изображения выступает вершина угла его объекта [10–22]. Проективное отображение сохраняет вершину угла, кроме случаев превращения угла преобразованием в угол 0, p и 2p (рад). Однако большинство известных алгоритмов обнаружения вершины угла на изображении [10–21] не обладают инвариантностью относительно проективного отображения.
Из математики известно, что угол может быть образован, например, двумя векторами или дугами, а также кривыми на плоскости.
Определение 1. Угол есть фигура (рис. 1), образованная двумя лучами OA и OB (стороны угла), исходящими из одной точки O (вершина угла) [23].
Рис. 1. Угол BOA
Из классической теории экстремалей как решения дифференциальных уравнений известно, что функции y(x) или yi(x), минимизирующие или максимизирующие определенный интеграл I = 
F[y(x), y′(x), x]dx или
I = F[y1(x), y2(x), …, yn(x); y′1(x), y′2(x), …, y′n(x); x]dx, могут иметь угловые точки для значений х, таких что ∂2F/∂y′2 = 0 или матрица [∂2F/∂y′i∂y′k] – полуопределенная для некоторых y, y′ или y1, y2, …, yn; y′1, y′2, …, y′n или же когда F имеет разрывы [24].
Угловые точки, в частности, могут встречаться [24]:
1. для некоторых x на интервале значений x («свободная» угловая точка [x1, y(x1)] или [x1: y1(x1), y2(x1), …, yn(x1)], рис. 2, а);
2. на кривой, поверхности и гиперповерхности
S(x, y) = 0 или S(x: y1, y2, …, yn) = 0,
пересекаемых экстремалями («преломление» экстремалей рис. 2, b);
3. на границе некоторой области, из которой экстремали исключены посредством ограничений-неравенств
S(x, y) ≤ 0 или S(x: y1, y2, …, yn) ≤ 0
(рис. 2, в и г)
Рис. 2. Экстремали с угловыми точками [24]: а) «свободная» угловая точка; b) преломление экстремали; c) отражение экстремали; d) граничный (односторонний) экстремум
Проблема обнаружения вершины угла на изображении I(x, y)ÎR обусловлена сложностью численного приближения производной функции интенсивности изображения I. Поскольку она известна только в дискретных отсчетах, то невозможно вычислить производную до тех пор, пока не будет определена интенсивность дифференцируемой функции, проходящей через эти отсчеты. При этом приближения ее производных можно определить лишь с ограниченной точностью. На практике используются различные маски для численного приближения производной функции интенсивности изображения I, в частности, дифференциальный оператор Робертса [25], Превитта [26], Собеля [26] и др.
Пусть «свободная» угловая точка – это вершина угла v. Рассмотрим широко распространенные алгоритмы обнаружения вершины угла на изображении более подробно.
Алгоритмы обнаружения вершины угла Моравека [10] и Харриса [11, 12] инвариантны по отношению к повороту и не чувствительны к изменениям значения интенсивности изображения, но недостаточно точно определяют вершину угла v.
Основным недостатком алгоритмов обнаружения вершины угла на основе дескриптора МПК [14, 15], является чувствительность дескриптора МПК к локальной вариации контура. При этом имеющиеся способы сглаживания не являются достаточными для решения проблемы. Говоря другими словами, Гауссиан с большим значением δ уменьшает шум, но воздействует на локализацию, а Гауссиан с малым значением δ чувствителен к шуму. Наибольшее распространение получили алгоритмы обнаружения вершины угла на основе дескриптора МПК [14, 15].
Известны алгоритмы обнаружения вершины угла на изображении, направленные на решение конкретных задач [20, 21].
Как уже упоминалось выше, почти все известные алгоритмы обнаружения характерного отсчета изображения [1–21] обладают инвариантностью относительно отображений аффинной группы. Аффинное отображение является частным случаем проективного отображения. Поэтому разработка алгоритма обнаружения вершины угла на изображении инвариантного относительно проективного отображения актуальна.
Постановка задачи
Задача 1. Пусть нам дано изображение I(x, y)ÎR. Необходимо обнаружить и локализовать вершину угла v (V{vi}) объекта O исходного изображения I.
Анализ поставленной задачи [1–22, 26] показывает, что вершина угла v определяется с помощью некоторого алгоритма обработки исходного изображения, представленного в бинарном виде.
Под произвольным контуром Γ изображения I будем понимать связное множество его отсчетов: Γ = {ni}, i = 0, ..., k – 1, k > 0, k Î Ν.
Подробно теория контурного анализа рассмотрена в работах [27, 28].
При обнаружении вершины v угла на изображении I возникают ошибки двух родов. Ошибка первого рода заключается в отклонении основной гипотезы, в то время как она справедлива, т. е. вершина угла v объекта изображения I не была обнаружена.
Ошибка второго рода заключается в принятие основной гипотезы, в то время как она не верна, т. е. произошло ошибочное обнаружение вершины угла v объекта изображения I. Это связано, в частности, со сложностью анализа как окрестности характерного отсчета Nbhd(si) изображения I, так и произвольного контура бинарного изображения. Эти ошибки оцениваются на основе коэффициентов k1 и k2: k1 = N/R и k2 = L/R, где N – количество необнаруженных вершин углов; L – количество определенных ложных вершин углов; R – общее число вершин углов изображения I, N, L и R ÎΝ.
Алгоритм обнаружения вершины угла на изображении на основе аппроксимации контура бинарного изображения
В основе разработанного автором алгоритма обнаружения вершины угла v лежит аппроксимация с заданной точностью контура бинарного изображения направленными отрезками 
и 
, исходящими из общей точки O (рис. 1). Выделение вершины угла v выполняется за один проход по исходному изображению I, представленному в бинарном виде, в порядке построчной развертки.
Алгоритм обнаружения вершины угла на изображении на основе аппроксимации контура бинарного изображения направленными отрезками (Ag. 1) включает следующие шаги:
Шаг 1. Выделить контур как границу объекта O изображения I;
Шаг 2. Произвести сканирование исходного изображения I представленного в бинарном виде в порядке построчной развертки – слева направо в строке и сверху вниз по строкам;
Шаг 3. Определить претендент r на вершину угла v;
Шаг 4. Сформировать код контура претендента r на вершину угла v;
Шаг 5. Идентифицировать претендента r как вершиной угла v.
Рассмотрим эти шаги подробнее.
Одним из возможных путей выделения контура на изображении I является применение алгоритма обнаружения края Кэнни [29] к исходному изображению I. Ширина контура равняется одному отсчету изображения. Подробно задача выделения контура как границы объекта изображения рассмотрена в работах [27, 29].
Произвольный отсчет (i, j) бинарного изображения может быть отнесен к одному из двух типов претендентов r на вершину угла v: претендент на вершину угла v первого типа r1 или претендент на вершину угла v второго типа r2 – при выполнении нескольких условий (рис. 3). В их основе лежит дифференциальный оператор Робертса [25].
Рис. 3. Схемы определения произвольного отсчета бинарного изображения претендентом r на вершину угла v: a) первый тип r1; b) второй тип r2
На рис. 3 произвольный отсчет (i, j) бинарного изображения обозначен крестиком. Отсчеты (i+1, j) и (i, j+1) или (i–1, j) и (i, j+1) c образующие вершину угла v (точка O, рис. 1) обозначены черными квадратами. Равенство значений отсчетов c единице является необходимым условием для определения произвольного отсчета (i, j) бинарного изображения претендентом r на вершину угла v. Достаточным условием является выполнение дополнительных требований, в частности, значения отсчетов, обозначенных нулем и пятеркой на рис. 3, не равняются единице одновременно.
Отсчеты c претендента r на вершину угла v могут образовывать произвольный угол, за исключением развернутого и полного углов. Пусть отсчет c0 = (i, j+1), а отсчет c1 = 
.
Алгоритм определения произвольного отсчета бинарного изображения претендентом на вершину угла первого или второго типа (Ag. 2) состоит из следующих шагов:
Шаг 1. Если значение отсчета (i, j+1), расположенного по отношению к текущему отсчету (i, j) сканирования, равняется единице, тогда, в первом случае, если значение отсчета (i+1, j) равно единице, то обнаружены отсчеты c ((i+1, j) и (i, j+1)) претендента r1 на вершину угла v. Во втором случае, если значение отсчета (i–1, j) равняется единице, то обнаружены отсчеты c ((i–1, j) и (i, j+1)) претендента r2 на вершину угла v;
Шаг 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, расположенные относительно рассматриваемых отсчетов 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) является претендентом на вершину угла v первого типа r1. Алгоритм завершается;
Шаг 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, расположенные относительно рассматриваемых отсчетов 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) является претендентом на вершину угла v второго типа r2. Алгоритм завершается.
Временная сложность алгоритма Ag. 2 не превзойдет 19 операций сравнения.
Шаги 2 и 3 алгоритма Ag. 2 обусловлены эффектом ложного контура [27, 30], в результате которого контуры на изображении могут соединяться, образуя сегменты контуров, и эти сегменты иногда соединяются подобно границам. Например, контуры могут образовать ломаную линию, состоящую из чередующихся вертикальных и горизонтальных отрезков, или окрестность в виде матрицы размером M×P отсчетов, где M и PÎΝ.
Контур Γ претендента r на вершину угла v подразделяется на две части: контур Γa и контур Γb.
Контур Γa (направленный отрезок , рис. 1) – это контур Γ начальным отсчетом a0 которого является отсчет c1.
Контур Γb (направленный отрезок , рис. 1) – это контур Γ начальным отсчетом a0 которого является отсчет c0.
Длины контуров Γa и Γb полагаются равными и не превышают заданное число отсчетов n. Их кодирование осуществляется стандартными ЭВ [27] согласно предложенному способу (рис. 4) на основе 8-связного цепного кода Фримана [27, 30].
Рис. 4. Нумерация и кодирование направлений 8-связного цепного кода Фримана
На рис. 4 код для каждого из направлений 8-связного цепного кода Фримана указан в скобках.
Идентификация претендента r как вершины угла v выполняется, на пятом шаге работы алгоритма Ag. 1, посредством разработанных правил на основе аппроксимации с заданной точностью кода контуров ∆Γa и ∆Γb направленными отрезками и .
В основе работы алгоритма Ag. 1 лежат следующие параметры:
Пусть размер входа алгоритма Ag. 1 определяет контур длинной m отсчетов, где m = 2*n. Тогда его вычислительная сложность TAg.1 = Θ(m).
Результат работы алгоритма Ag. 1, алгоритма на основе дескриптора МПК [14] и алгоритма Харриса [11] изображены на рис. 5.
Рис. 5. Примеры работы алгоритмов обнаружения вершины угла на тестовых изображениях I1 и I2, размером 717×209 и 594×224 отсчетов: a), b) алгоритм Ag. 1, n = 8; c), d) алгоритм обнаружения вершины угла на основе дескриптора МПК [14]; e), f) алгоритм Харриса [11]
Из рис. 5 видно, что алгоритм Ag. 1 лучше обнаруживает вершину угла v с наименьшим количеством ошибок второго рода.
Алгоритм формирования кода контура претендента на вершину угла
Пусть нам дан претендент r на вершину угла v первого или второго типа. Тогда формирование кода его контура ∆Γ (контуры Γa и Γb, см. рис. 6) выполняется стандартными ЭВ на основе 8-связного цепного кода Фримана.
Рис. 6. Угол BOA на бинарном изображении: a) изображение 1; b) изображение 2
Алгоритм кодирования контура претендента на вершину угла (Ag. 3) включает следующие шаги:
Шаг 1. Задать начальное и конечное направления обнаружения отсчета a0 контуров Γa и Γb;
Шаг 2. Выполнить кодирование контуров Γa и Γb;
Шаг 3. Проверить размер кода контуров ∆Γa и ∆Γb. В случае если он < n для любого из них, тогда выполнить алгоритм начиная с шага 1 еще раз и завершить его. Иначе алгоритм завершается.
Рассмотрим эти шаги подробнее.
Прослеживание и кодирование линии контуров Γa и Γb претендента r на вершину угла v выполняется на основе следующих правил.
Правила начала прослеживания линии контура бинарного изображения:
Правила прослеживания линии контура бинарного изображения. Отличительной особенностью рассматриваемого алгоритма анализа контура бинарного изображения, является независимость его работы от алгоритма прослеживания линии контура. Отметим, что при прослеживании линии контура также осуществляется подсчет количества того или иного направления в коде соответствующего контура и подсчет количества одинаковых направлений, следующих друг за другом. Нумерация и кодирование направлений 8-связного цепного кода Фримана выполняется согласно схемы, приведенной на рис. 4.
Правила завершения прослеживания линии контура бинарного изображения. Кодирование линии контура прекращается в случае выполнения одного из следующих условий:
Временная сложность алгоритма Ag. 3 не превзойдет 4 операций сравнения плюс временная сложность алгоритма прослеживания линии контура не превосходящей 4*n отсчетов изображения.
Алгоритм идентификации претендента как вершины угла
Идентификация претендента r как вершины угла v выполняется посредством разработанных автором правил, подразделяющихся на две категории: правила идентификации претендента r как ложной вершины угла и правила идентификации претендента r как вершины угла v. В основе разработанных правил лежит аппроксимация кода контуров ∆Γa и ∆Γb направленными отрезками и .
Алгоритм идентификации претендента как вершины угла (Ag. 4) состоит из следующих шагов:
Шаг 1. Проверить размер кода контуров ∆Γa и ∆Γb. В случае если он < n для любого контура завершить алгоритм;
Шаг 2. Выполнить правила идентификации претендента как ложной вершины угла. В случае выполнения любого из правил полагаем, что претендент r не является вершиной угла v и алгоритм завершается;
Шаг 3. Выполнить правила идентификации претендента как вершины угла. В случае выполнения любого из правил полагаем, что претендент r является вершиной угла v. Алгоритм завершается.
Рассмотрим эти шаги подробнее.
Пусть направления 1, 3, 5 и 7 (см. рис. 4) формируют множество С = {1, 3, 5, 7}.
Правила идентификации претендента как ложной вершины угла:
