ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2014, № 3, с. 94-103
РАСПОЗНАВАНИЕ ОБРАЗОВ И ОБРАБОТКА ИЗОБРАЖЕНИЙ
УДК 519.722
РАЗРАБОТКА АЛГОРИТМА БЫСТРОГО ВЫДЕЛЕНИЯ УГОЛКОВЫХ ЭЛЕМЕНТОВ НА ЦИФРОВЫХ СНИМКАХ*
© 2014 г. М. С. Веркеенко
Москва, ФГУП ГОСНИИАС
Поступила в редакцию 28.11.13 г., после доработки 23.12.13 г.
Представлен метод выделения уголковых точек на цифровых снимках, который отличается высокой стабильностью и эффективностью по отношению ко многими разработанным ранее методам детектирования уголков. Стабильность выделения уголков особенно важна в задачах машинного зрения, связанных с координатной привязкой снимков одного и того же объекта, реконструкцией цифровых моделей поверхностей по набору снимков и отслеживанием объектов. Подавляющее число алгоритмов одинаково хорошо выделяют как истинные уголки, так и лишние точки, не соответствующие реальным углам объектов. Представленный алгоритм лишен этого недостатка, а также может быть использован для покадровой обработки видео в реальном времени, например в системах навигации мобильных роботов и беспилотных летательных аппаратов. Кроме того, предложенный алгоритм может быть адаптирован к любому набору данных, так как в его основе лежит метод машинного обучения. Преимущества разработанного метода демонстрируются на примере выделения уголков на снимках типового ангара и кадрах с участием международной космической станции.
Б01: 10.7868/80002338814030160
Введение. Появление нового поколения беспилотных летательных аппаратов (БПЛА) и наземных автономных роботов с элементами искусственного интеллекта повышает требования к системам навигации. Стандартом для таких систем уже на текущий момент является использование видеоизображения с одной или нескольких бортовых камер, поэтому актуальность задачи обработки видеоданных в реальном времени на бортовых вычислителях для последующей навигации очень высока. Для решения этой задачи применяются различные методы машинного зрения, в обязательном порядке включающие анализ различных характерных черт изображений: четких контуров, областей и точек интереса (характерных точек). В качестве основных достоинств точек интереса выступают относительная простота и скорость их выявления. Кроме того, на изображениях не всегда удается выделить другие характерные черты, в то время как характерные точки в подавляющем большинстве случаев выделить можно. Точки интереса могут использоваться не только для навигации мобильных аппаратов, но и в задачах, связанных с координатной привязкой снимков одного и того же объекта [1] и реконструкцией цифровых моделей поверхностей по набору снимков [2].
Под точками интереса понимаются центральные пиксели окрестностей изображения, обладающих высокой локальной информативностью. В качестве численной меры информативности предлагаются различные формальные критерии, называемые операторами интереса. Характерные точки должны удовлетворять следующим требованиям:
Повторяемость — точка интереса должна находиться в том же месте, несмотря на изменения точки обзора и освещения,
Значимость — каждая точка интереса должна иметь уникальное описание,
Компактность и эффективность — точек интереса гораздо меньше, чем пикселей в изображении,
Локальность — область вокруг точки интереса занимает маленькую область изображения, таким образом, например работа с этой областью нечувствительна к возможным перекрытиям.
Классическим примером такой точки является вершина угла на изображении. Точки интереса на снимках образуются как за счет геометрии объекта, представленного на снимке, к примеру, реальный угол дома, так и за счет текстуры объекта. В предыдущие годы было разработано боль-
* Работа выполнена при финансовой поддержке РФФИ (проект № 11-08-00703 а).
шое количество методов детектирования характерных точек, которые можно разделить на два класса.
К первому классу относятся методы, основанные на анализе яркостного изображения. Одним из первых методов такого класса является алгоритм Моравека [3]. Этот алгоритм проверяет каждый пиксель изображения. Сила уголка при этом определяется как наименьшая сумма квадратов разностей (СКР) между участком и его соседями (по горизонтали, вертикали и двум диагоналям). Если это число локально максимально, то особенность присутствует. Харрис и Стивенс улучшили детектор углов Моравека, рассматривая дифференциальную оценку угла по отношению к направлению непосредственно, вместо использования сдвинутых пятен [4]. Авторы этого метода вводят производные по некоторым принципиальным направлениям, раскладывая функцию интенсивности в ряд Тейлора. По сравнению со своим предшественником данный детектор инвариантен относительно поворота, количество ошибок детектирования углов не велико за счет введения свертки с гауссовыми весовыми коэффициентами, однако результаты детектирования значительно меняются при масштабировании изображения. Помимо детектора Харриса существуют другие методы обнаружения углов, позволяющие решать эту задачу в зависимости от масштаба изображения. Наибольшую популярность получили детекторы SIFT [5] и его ускоренный вариант SURF [6]. Детектор SIFT основан на идее поиска локальных максимумов в так называемом пространстве переменного масштаба. Детектор SURF использует ту же идею пространства переменного масштаба, что и детектор SIFT, но функция Гаусса приближается прямоугольным фильтром 9 х 9. Однако существенный недостаток всех описанных детекторов — невозможность их применения для выделения точек интереса в реальном времени на видеопоследовательности из-за относительно высоких вычислительных затрат этих алгоритмов. Решением этой задачи явился детектор FAST, позволивший существенно ускорить процесс выделения точек интереса, сохранив при этом относительно высокую повторяемость выделяемых точек за счет того, что он не требует вычисления производных яркости [7]. В основе алгоритма FAST лежит принцип машинного обучения с использованием дерева принятия решений (алгоритм ID3 [8]). В качестве набора атрибутов для алгоритма построения дерева принятия решений и последующей классификации выступают результаты сравнения яркостей пикселей, лежащих на окружности, с яркостью центральной точки. При детектировании уголков методом FAST сначала происходит быстрое тестирование с применением четырех пикселей, оставляющее только потенциальные точки интереса, потом для каждой оставшейся точки происходит быстрая классификация с помощью построенного ранее дерева принятия решений и подавление немаксимумов. Идея машинного обучения легла в свою очередь в основу метода, предложенного в этой статье.
Вторым классом являются методы выделения точек интереса, основанные на анализе контуров, извлеченных с яркостного изображения. Контуры на изображении обычно соответствуют границе двух областей. В области уголковой точки кривизна этой границы может быть максимальной либо там может происходить соединение нескольких сегментов линий. Для детектирования уголков на контурных изображениях применяются различные методы. Часть методов содержит полигональную аппроксимацию для поиска точек пересечения контуров или максимума кривизны контура [9]. Многие из них используют связанные контуры. Так как контуры легко квантуются, то такие методы нацелены на оценку кривизны при вычислении, например, значения угла в каждой точке контура [10]. Также может использоваться преобразование Хаффа [11]. В этом случае каждый контур заменяется некоторым отрезком, а уголковыми точками считаются точки, лежащие на пересечении этих отрезков.
Данные методы имеют один или несколько недостатков:
одинаково хорошо выделяют как истинные уголки, так и точки, соответствующие неровностям фотографируемых поверхностей,
не выделяют многие истинные неуголковые точки,
производительности недостаточно для обработки видеокадров в реальном времени.
Предложенный в этой статье алгоритм выделения уголковых точек лишен этих недостатков и объединяет преимущества обоих классов детектирования точек.
Детектор использует дерево принятия решений для классификации уголковых и неуголковых пикселей изображения. В качестве обучающей выборки для построения дерева применяются векторы атрибутов, полученные на контурных изображениях с базой уголковых точек, созданной оператором. Для получения вектора атрибутов предназначен оригинальный алгоритм циклического контурного аккумулятора. Аккумулятор формирует для каждой точки уникальный вектор бинарных атрибутов на основе информации о контурных пикселах внутри соответствующей круговой окрестности. После построения дерево принятия решений применяется для де-
Рис. 1. Набор снимков типового ангара "Ангар"
Рис. 2. Ряд кадров синтетического видео с участием МКС "МКС"
тектирования уголковых пикселей. При этом для каждого классифицируемого пиксела предварительно также строится вектор атрибутов при помощи циклического контурного аккумулятора.
1. Исходные данные для детектирования уголков. Для отработки и исследования свойств разработанного метода был выбран набор снимков с разрешением 1402 х 931 пикселей с изображениями типового ангара, получивший условное название "Ангар" (рис. 1), и ряд кадров с разрешением 720 х 576 пикселей с синтетического видео с участием международной космической станции (МКС) под условным названием "МКС" (рис. 2). Также оператором были сформированы обучающая и оценочная базы уголковых точек для обоих наборов снимков.
2. Формирование набора атрибутов для машинного обучения. Для создания дерева принятия решений применяется вектор атрибутов, извлеченных не с изображения в оттенках серого, а с контурного изображения.
2.1. Выделение контуров на изображениях. Такое изображение может быть получено с использованием алгоритма Канни [12]. Предварительно изображение обрабатывается сглаживающим и дифференциальным фильтром, затем производится подавление локальных немаксимумов градиентного изображения и дополнительная морфологическая обработка для обрезки коротких ответвлений контуров. Результат показан на рис. 3.
2.2. Циклический контурный аккумулятор для получения набора атрибутов. Для машинного обучения необходимо сфо
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.