png png
к ленте

Фильтрация ключевых
точек изображений

Июнь'10
author
Николай Демьянков
специалист департамента мобильной разработки
Июнь'10

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

Введение

Задача сопоставления двух изображений, а также поиска маркера на видеопотоке в режиме реального времени (прежде всего, на мобильных устройствах) имеет прямое отношение к популярной в настоящее время технологии дополненной реальности. Для её решения используются различные алгоритмы компьютерного зрения: контурный анализ, сопоставление шаблонов (template matching), сравнение ключевых точек (feature point detection & description) и др. В настоящей статье мы затронем подход, связанный с поиском изображения-маркера на некоторой картинке по его ключевым точкам. Данный процесс можно разбить на четыре этапа:

  • Выделение ключевых точек с помощью детектора (feature detector).
  • Описание найденных точек с помощью дескриптора (feature descriptor).
  • Получение набора связей (соответствий) между ключевыми точками при помощи матчера (matcher).
  • Анализ полученных связей с целью определения факта нахождения маркер на изображении.

Реализация первых трёх пунктов не составляет особого труда ввиду наличия широкого класса библиотек компьютерного зрения. Среди них стоит выделить библиотеку OpenCV (которой мы и будем пользоваться в дальнейшем), написанную на языке C++ и обладающую наиболее широким набор функций. Прежде всего, в ней имеется модуль Feature Points Detection & Description, содержащий реализации различных детекторов, дескрипторов и матчеров. Ввиду этого, первые три пункта поиска маркера на изображении решаются достаточно просто и без каких-либо серьёзных затруднений. Основная сложность состоит в четвёртом шаге, поскольку нет какой-то специальной функции, которая могла бы уверенно сказать — находится искомый объект на изображении или нет.

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

Исследование методов фильтрации ключевых точек изображений с целью повышения качества и скорости их сопоставления
Пример ошибочных связей.

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

H = cv::findHomography( obj, scene, cv::CV_RANSAC);
if (someMethodToCheckHomography(H)) {
 cv::perspectiveTransform(obj, true_points, H);
 for( i = 0; i < matches.size(); i++ ){
  dx = scene[i].x - true_points[i].x;
  dy = scene[i].y - true_points[i].y;
  delta = dx*dx+dy*dy;
  if (delta < MAX_DELTA) {
   good_matches.push_back(matches[i]);
    }
 }
}

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

Фундаментальная матрица
и эпиполярная геометрия

Помимо алгоритма поиска матрицы гомографии, в OpenCV есть функция для нахождения матрицы фундаментального преобразования, работающая по схеме RANSAC. Данную матрицу можно использовать для фильтрации по эпиполярным линиям. Стоит отметить, что похожим образом реализован алгоритм фильтрации geometric consistency checking (ORSA) и функция cv::stereoRecifyTransform().

Исследование методов фильтрации ключевых точек изображений с целью повышения качества и скорости их сопоставления
Эпиполярные линии.
F = cv::findFundamentalMat(obj, scene, cv::CV_FM_RANSAC);
cv::computeCorrespondEpilines(obj, 1, F, lines1);
cv::computeCorrespondEpilines(scene, 2, F, lines2 );
for(i = 0; i < matches.size(); i++){
 d1 = fabs(obj[i].x*lines2[i].x + obj[i].y*lines2[i].y + lines2[i].z);
 d2 = fabs(scene[i].x*lines1[i].x + scene[i].y*lines1[i].y + lines1[i].z);
   If (d1<= threshold && d2 <= threshold) {
   good_matches.push_back(matches[i]);
   }
}

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

  • Алгоритм имеет высокую скорость работы: примерно 0.13 сек. на 1041 соответствие (поиск фундаметальной матрицы работает по схеме RANSAC).
  • Качество работы значительно лучше, чем в случае проверки матрицы гомографий, даже при наличии большого числа ложных связей.

Исследование методов фильтрации ключевых точек изображений с целью повышения качества и скорости их сопоставления
Фильтрация фундаментальной матрицей.

Недостатки подхода:

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

Исследование методов фильтрации ключевых точек изображений с целью повышения качества и скорости их сопоставления
Соответствия в узком секторе.

Как и в случае с алгоритмом поиска гомографии, была замечена сильная зависимость от разрешения искомого объекта (эталона). Чем меньше разница в размере эталона и искомого изображения, тем фильтрация выполняется более качественно. Если же искомый объект становится больше аналогичного объекта на тестируемом изображении — качество фильтрации начинает резко падать.

Исследование методов фильтрации ключевых точек изображений с целью повышения качества и скорости их сопоставления
Увеличенный эталон.

Матрица оптимального
аффинного преобразования

Библиотека OpenCV обладает набором функций, применяемых для определения аффинных преобразований между двумя множеством точек. Для поиска оптимального преобразования используется функция cv::estimateRigidTransform(). Сама по себе она не выдает приемлемых результатов, т.к. корректно работает только при очень малом количестве ложных связей. Однако если данный набор был предварительно обработан каким-то другим фильтром, уменьшающим количество ложных соответствий — данный метод позволяет избавиться от оставшихся.

Исследование методов фильтрации ключевых точек изображений с целью повышения качества и скорости их сопоставления
Фильтрация фундаментальной матрицей вместе с cv::estimateRigidTransform()
cv::Mat M = cv::estimateRigidTransform(obj, scene, false);
m = M.ptr();
for( i = 0; i < seg_in.size(); i++ ) {
 dx = m[0]*obj[i].x + m[1]*obj[i].y + m[2] - scene[i].x;
 dy = m[3]*obj[i].x + m[4]*obj[i].y + m[5] - scene[i].y;
 delta = dx*dx+dy*dy;
 if(delta < threshold) {
   good_matches.push_back(matches[i]);
  }
}

Преимущества данного подхода:

  • Алгоритм работает очень быстро.
  • Отсекает практически все ложные связи.

Его недостатки:

  • Работает только при малом количестве outlier. Фактически, он может применяться только вместе с каким-то другим алгоритмом в качестве финального этапа фильтрации.
  • Плохо работает при перспективных искажениях (например, при большом угле наклона). Частично это можно компенсировать, указав в функции cv::estimateRigidTransform() в качестве третьего параметра значение true. Однако при этом теряется его жесткость в плане отсеивания всех помех, т.е. иногда всё же остаётся небольшое число ложных связей.

solvePnPRansac

Данная функция из библиотеки OpenCV ищет матрицу поворота и матрицу сдвига камеры. Для ее работы предполагается выполнение предварительной калибровки камеры — определение её параметров (фокусное расстояние, угол наклона пикселей и т.д.). Функция особенно удобна тем, что на выходе отдает индексы точек корректных связей между двумя наборами feature points. К тому же по матрицам сдвига и поворота, при необходимости, можно определить примерное положение камеры в пространстве на момент съёмки.

float camm[9] = { 600, 0, cx, 0, 600, cy, 0, 0, 1};
cv::Mat cv::cameraMatrix(3, 3, cv::CV_32F, camm);
useExtrinsicGuess = false;
iterationsCount = 500;
reprojectionError = 8.0;
minInliersCount = matches.size() * 2 / 3;
flags = cv::ITERATIVE;
cv::solvePnPRansac(object3DPoints, image2DPoints, cameraMatrix, noArray(), rvec, tvec, useExtrinsicGuess, iterationsCount,
reprojectionError, minInliersCount, inliers, flags);
for (i = 0; i < inliers.size(); i++) {
  good_matches.push_back(matches[inliers[i]]);
}

Преимущества:

  • Определяет положение камеры в пространстве относительно искомого изображения.

Недостатки:

  • Низкое качество работы без предварительной фильтрации связей.
  • Низкая скорость выполнения.
  • Не дает стабильного результата: на одном и том же изображении может находить разное количество связей.
  • Имеется определённый процент ложных срабатываний: некоторые из связей, которые алгоритм посчитал хорошими, на самом деле некорректны.

Поиск геометрически связанных групп

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

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

Соотношение сторон:

Соотношение площадей:

Соотношения углов:

Среди признаков выделялись:

  1. Свойства подобия:
    • Расстояние на эталоне от точки в группе до других точек в той же группе пропорционально соответствующему расстоянию на тестируемом изображении.
    • Углы между тремя точками на эталоне переходят в такие же углы на искомом изображении.
  2. Площадь ортогональной проекции многоугольника на плоскость равна произведению его площади на косинус угла между плоскостью многоугольника и плоскостью проекции. Таким образом, с точностью до перспективных искажений можно утверждать о том, что отношение площади любого треугольника в группе на эталоне к площади на искомом изображении постоянно.

Были опробованы алгоритмы, как с полным перебором всех связей, так и выборка по схеме RANSAC. Дадим описание логики работы каждого из них.

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

  1. Первый этап:
    • Выбираются две любые связи таким образом, чтобы точки как на эталоне так и на искомом изображении были достаточно далеко друг от друга.
    • Каждая связь кроме предыдущих двух, проверяется на сохранение расстояний и углов. Если отклонение достаточно мало — точка записывается в группу.
    • Для следующей точки проверка ведется уже не по двум связям, а по всей найденной группе.
    • Работа продолжается циклически, пока количество связей в группе не достигнет некоторого заданного значения. От порога количества повторений зависит скорость работы на несовпадающих изображениях.
  2. Второй этап. Поскольку последние N связей в полученной группе оказываются проверенными по большему набору, чем предыдущие, они имеют более высокий шанс быть хорошими (inlier).
    • Берутся три точки из N последних связей построенной группы таким образом, чтобы они не были слишком близки друг к другу.
    • Каждая связь, кроме выбранных трёх, проверяется на сохранение геометрических параметров (здесь уже можно использовать сравнение площадей треугольников).
    • Если количество связей сгруппированных на втором шаге превышает заданный порог, группа выдается в качестве результата.

Второй подход является алгоритмом полного перебора, выполняющим поиск треугольника, который наилучшим образом сохраняет группу связей с некоторым заданным объемом:

  • Перебираются все тройки точек, и ищется треугольник, который имел бы большую площадь на эталоне (это позволяет исключить ситуацию, при которой находится только часть изображения — рис. 4) и сохранял бы пропорции с некоторым допущением.
  • Когда такой треугольник находится (ABC -> A’B’C’), осуществляется проверка каждой связи (D -> D’) относительно данного треугольника: рассчитывается отношение площадей треугольников, образованных каждой стороной найденного и точками связи (рис. 8).
  • Если группа недостаточно велика — ищется следующий треугольник.

Как показали эксперименты, алгоритмы с полным перебором дают более стабильный результат, могут обнаруживать inlier точки даже если их число значительно меньше outlier точек. При этом, скорость его работы значительно меньше, чем у рандомизированых алгоритмов, особенно если указать достаточно низкий порог числа точек в искомой группе.

Интересным подходом для поиска геометрических групп является использование гистограмм: вместо того, чтобы сравнивать связи по некоторым критериям, выполняется построение гистограммы данного критерия (рис. 9). По ней определяется значение критерия, имеющее максимальный вес, после чего находятся все связи, которые его сформировали.

Гистограмма распределения углов между парами связей.

На основе данного подхода было разработано два метода: поиск центра изображения и анализ угла поворота.

Поиск центра изображения

На любой отрезок BC, соединяющий ключевые точки на эталонном изображении, можно опустить перпендикуляр из центра изображения — AD. Тогда посредством вычисления дополнительных коэффициентов (k и j) можно восстановить центр A’ на тестируемом изображении:

Поиск центра изображения с помощью гистограммы.

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

Преимущества данного подхода:

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

Недостатки:

  • Оставляет некоторое количество ложных связей.
  • Не точно работает при больших перспективных искажениях. Скопление несколько размазывается в этом случае.
  • Алгоритм может найти соответствия в слишком узком секторе изображения.

Усложненный поиск центра

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

Анализ угла поворота

Через любые две точки на эталонном изображении можно провести прямую, и найти угол между ней и координатной осью X. Аналогичный процесс выполняется и на тестируемом изображении. Разница угла на эталоне и угла на искомом изображении будет сохраняться с некоторой погрешностью для всех пар правильных связей.

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

Преимущества подхода:

  • Хорошая скорость работы: 0.038 сек. на 1090 соответствиях.
  • При оценке учитывает все связи, что позволяет работать при очень большом количестве плохих соотношений.

Недостатки:

  • Оставляет некоторое количество ложных связей.
  • Алгоритм может найти соответствия в узком секторе изображений.

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

Другие алгоритмы на основе
поиска пика гистограмм

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

Вывод

В статье были рассмотрены существующие подходы и предложены новые методы к поиску эталонных изображений на тестируемых картинках, используя алгоритмы Feature Point Detection. Каждый из описанных алгоритмов обладает своими достоинствами и недостатками и по отдельности не позволяет точно сказать, найден ли искомый объект на тестируемом изображении или нет. Однако если воспользоваться одновременно несколькими подобными фильтрами — можно добиться высокого качества работы алгоритмов при оптимальной скорости выполнения. В частности, имеет смысл следующая схема фильтрации связей:

  • В качестве предварительного фильтра использовать анализ угла поворота.
  • В качестве финального — усложненный поиск центра.

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