Анализ алгоритмов
компьютерного зрения

Введение

В данной статье мы рассмотрим три существующих метода к распознанию объектов на изображении: контурный анализ, поиск шаблона (более известный, как template matching) и сопоставление по ключевым точкам (feature detection, description & matching). Конечно, компьютерное зрение не ограничивается только затрагиваемыми подходами. Помимо них можно выделить так называемые генетические алгоритмы, применяемые, в частности, для распознания лиц. Или же поиск объектов по цвету. Исследование подобных подходов стоит отнести к отдельной статье. Основная наша цель — познакомить читателя с некоторыми алгоритмами компьютерного зрения. При желании более подробная информация по каждому из описываемых методов может быть найдена в приведённом списке литературы.

Для программной реализации рассматриваемых алгоритмов нами использовалась библиотека компьютерного зрения OpenCV версии 2.4.3. Это библиотека с открытым исходным кодом, написанная на языке C++ и распространяемая под лицензией BSD, что означает возможность её бесплатного использования как в академических, так и в коммерческих целях.

Контурный анализ

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

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

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

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

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

вполне будет найден на таком изображении:

Для этого на рис. 1 сначала производится поиск всех контуров и формируется шаблон каждого слова — массив контуров букв, пронумерованный по порядку появления. Затем на рис. 2 аналогичным образом ищутся все контуры и последовательно сравниваются с полученными ранее шаблонами. Если процент совпадения достаточно велик — фраза считается найденной. Библиотека компьютерного зрения OpenCV обладает удобным набором функций для поиска, отображения и сравнения контуров. Для этого сначала необходимо привести картинку к оттенкам серого, бинаризовать полученное изображение, и после этого воспользоваться функцией:
#include «opencv2/highgui/highgui.hpp»
#include «opencv2/imgproc/imgproc.hpp»
#include
#include
#include

using namespace cv;
using namespace std;

int main( int argc, char** argv ) {
Mat src; Mat src_gray; Mat canny_output;
vector > contours;
vector hierarchy;
int thresh = 100;
RNG rng(12345);

src = imread(argv[1], 1);

/* преобразование к оттенкам серого */
cvtColor( src, src_gray, CV_BGR2GRAY );

/* поиск граней с помощью алгоритма Кенни */
Canny( src_gray, canny_output, thresh, thresh*2, 3 );

/* поиск контуров */
findContours( canny_output, contours, hierarchy, CV_RETR_TREE, CV_CHAIN_APPROX_SIMPLE, Point(0, 0) );

/// отрисовка контуров
Mat drawing = Mat::zeros( canny_output.size(), CV_8UC3 );
for( int i = 0; i< contours.size(); i++ ) {
Scalar color = Scalar( rng.uniform(0, 255), rng.uniform(0,255), rng.uniform(0,255) );
drawContours( drawing, contours, i, color, 2, 8, hierarchy, 0, Point() );
}

/* показ результата в отдельном окне */
namedWindow( «Contours», CV_WINDOW_AUTOSIZE );
imshow( «Contours», drawing );
waitKey(0);
return(0);
}


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

Template matching

Данный метод применяется для поиска участков изображений, которые наиболее схожи с некоторым заданным шаблоном. Таким образом, входными параметрами метода являются:

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

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

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

Template matching является хорошим выбором, когда необходимо быстро проверить наличие некоторого объекта на изображении. Также в интернете можно найти различные примеры использования алгоритма для идентификации человека по лицу. Такой подход значительно проще реализовать, нежели при помощи обучаемых алгоритмов. Ниже приведён пример реализации поиска объекта по шаблону. При желании его можно легко адаптировать для поиска шаблона прямо на видеопотоке веб-камеры или камеры мобильного устройства.
#include «opencv2/highgui/highgui.hpp»
#include «opencv2/imgproc/imgproc.hpp»
#include
#include

using namespace std;
using namespace cv;

int main( int, char** argv ) {
Mat result;
const char* image_window = «Work Result»;

/* варианты метода сравнения:
CV_TM_SQDIFF, CV_TM_SQDIFF_NORMED, CV_TM_CCORR,
CV_TM_CCORR_NORMED, CV_TM_CCOEFF, CV_TM_CCOEFF_NORMED */
int match_method = CV_TM_SQDIFF;

/* загружаем тестируемое изображение и шаблон */
Mat sourceImg = imread( argv[1], 1 );
Mat templateImg = imread( argv[2], 1 );

/* создаем копию исходного изображения для последующего отображения в окне результата */
Mat img_display;
sourceImg.copyTo( img_display );

/* создаем матрицу результата сравнения */
int result_cols = sourceImg.cols — templateImg.cols + 1;
int result_rows = sourceImg.rows — templateImg.rows + 1;
result.create( result_cols, result_rows, CV_32FC1 );

/* выполняем сравнение и нормализуем результат */
matchTemplate( sourceImg, templateImg, result, match_method );
normalize( result, result, 0, 1, NORM_MINMAX, −1, Mat() );

/* находим наилучшее совпадение с помощью функции minMaxLoc */
double minVal; double maxVal; Point minLoc; Point maxLoc;
Point matchLoc;

minMaxLoc( result, &minVal, &maxVal, &minLoc, &maxLoc, Mat() );

/* Для методов SQDIFF и SQDIFF_NORMED наилучшая область совпадения соответствует наименьшему значению.
Для остальных методов — чем выше значение, тем лучше. */
if( match_method == CV_TM_SQDIFF || match_method == CV_TM_SQDIFF_NORMED ) {
matchLoc = minLoc;
} else {
matchLoc = maxLoc;
}

/* рисуем контур вокруг найденной области и показываем полученное изображение */
rectangle( img_display, matchLoc, Point( matchLoc.x + templateImg.cols , matchLoc.y + templateImg.rows ), Scalar::all(0), 2, 8, 0 );
namedWindow( image_window, CV_WINDOW_AUTOSIZE );
imshow( image_window, img_display );

/* при необходимости аналогичным образом может быть выведено изображение, хранящееся в переменной result */

waitKey(0);
return 0;
}


Однако стоит понимать, что template matching не позволяет с уверенностью сказать был ли найден исходный объект, поскольку это вероятностная характеристика, зависящая от масштаба, углов обзора, поворотов картинки и наличия физических помех. Также возможны ложные срабатывания алгоритма, когда искомого объекта на самом деле нет, но имеются какие-то общие детали у шаблона и области на тестируемом изображении. Конечно, подобной ситуации можно избежать путём проверки значения коэффициента совпадения (чтобы он не был меньше некоторого граничного предела), однако это не всегда будет работать должным образом ввиду описанных выше причин.

Feature Detection

Концепция feature detection в компьютерном зрении относится к методам, которые нацелены на вычисление абстракций изображения и выделения на нем ключевых особенностей. Данные особенности затем используются для сравнения двух изображений с целью выявления у них общих составляющих. Не существует строго определения того, что такое ключевая особенность картинки. Ею могут быть как изолированные точки, так и кривые или некоторые связанные области. Примерами таких особенностей могут служить грани объектов и углы.

Мы рассмотрим алгоритмы, которые для своей работы используют ключевые точки (feature points) изображения. Под ключевыми точками понимаются некоторые участки картинки, которые являются отличительными для данного изображения.

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

• Детектор (feature detector) — осуществляет поиск ключевых точек на изображении.
• Дескриптор (descriptor extractor) — производит описание найденных ключевых точек, оценивая их позиции через описание окружающих областей.
• Матчер (matcher) — осуществляет построение соответствий между двумя наборами точек изображений.

Ниже мы приведём код программы, которая в качестве входных параметров получает изображение искомого объекта и картинку, на которой его нужно найти. Результатом её работы будет изображение с построенными линиями соответствий между ключевыми точками двух картинок, а также отмечено положение искомого объекта на тестируемом изображении.
#include «opencv2/core/core.hpp»
#include «opencv2/features2d/features2d.hpp»
#include «opencv2/highgui/highgui.hpp»
#include «opencv2/calib3d/calib3d.hpp»
#include «opencv2/nonfree/features2d.hpp»
#include
#include

using namespace cv;

int main( int argc, char** argv ) {
/* переводим изображения в оттенки серого */
Mat img_object = imread( argv[1], CV_LOAD_IMAGE_GRAYSCALE );
Mat img_scene = imread( argv[2], CV_LOAD_IMAGE_GRAYSCALE );

/* Шаг 1: поиск точек с помощью детектора SURF */
int minHessian = 400;
SurfFeatureDetector detector( minHessian );
std::vector keypoints_object, keypoints_scene;
detector.detect( img_object, keypoints_object );
detector.detect( img_scene, keypoints_scene );

/* Шаг 2: вычисление дескрипторов точек */
SurfDescriptorExtractor extractor;
Mat descriptors_object, descriptors_scene;
extractor.compute( img_object, keypoints_object, descriptors_object );
extractor.compute( img_scene, keypoints_scene, descriptors_scene );

/* Шаг 3: сопоставление точек посредством матчера FLANN */
FlannBasedMatcher matcher;
std::vector< DMatch > matches;
matcher.match( descriptors_object, descriptors_scene, matches );
double max_dist = 0; double min_dist = 100;

/* Подсчет минимального и максимального расстояния между точками для последующей фильтрации совпадений */
for( int i = 0; i < descriptors_object.rows; i++ ) {
double dist = matches[i].distance;
if ( dist < min_dist ) min_dist = dist;
if ( dist > max_dist ) max_dist = dist;
}

/* Отбираем только «хорошие» связи: расстояние между которыми меньше, чем 3*min_dist */
std::vector< DMatch > good_matches;
for( int i = 0; i < descriptors_object.rows; i++ ) {
if( matches[i].distance < 3*min_dist ) {
good_matches.push_back( matches[i]);
}
}

/* формируем изображение, на котором будут отражены найденные связи */
Mat img_matches;
drawMatches( img_object, keypoints_object, img_scene, keypoints_scene,
good_matches, img_matches, Scalar::all(-1), Scalar::all(-1),
vector(), DrawMatchesFlags::NOT_DRAW_SINGLE_POINTS );


/* формируем набор «хороших» точек с шаблонного и тестируемого изображений */
std::vector obj;
std::vector scene;
for( size_t i = 0; i < good_matches.size(); i++ ) {
obj.push_back( keypoints_object[ good_matches[i].queryIdx ].pt );
scene.push_back( keypoints_scene[ good_matches[i].trainIdx ].pt );
}

/* находим матрицу гомографию между изображениями по алгоритму RANSAC */
Mat H = findHomography( obj, scene, CV_RANSAC );

/* с помощью матрицы гомографии проецируем углы искомого объекта на тестируемое изображение */
std::vector obj_corners(4);
std::vector scene_corners(4);
obj_corners[0] = cvPoint(0,0);
obj_corners[1] = cvPoint( img_object.cols, 0 );
obj_corners[2] = cvPoint( img_object.cols, img_object.rows );
obj_corners[3] = cvPoint( 0, img_object.rows );
perspectiveTransform(obj_corners, scene_corners, H);

/* соединяем спроецированные точки линиями, чтобы обозначить местоположение найденного объекта */
Point2f offset( (float)img_object.cols, 0);
line( img_matches, scene_corners[0]+offset, scene_corners[1] + offset, Scalar(0, 255, 0), 4 );
line( img_matches, scene_corners[1]+offset, scene_corners[2] + offset, Scalar( 0, 255, 0), 4 );
line( img_matches, scene_corners[2]+offset, scene_corners[3] + offset, Scalar( 0, 255, 0), 4 );
line( img_matches, scene_corners[3]+offset, scene_corners[0] + offset, Scalar( 0, 255, 0), 4 );

imshow( «Work Result», img_matches );
waitKey(0);
return 0;
}


Результат выполнения программы

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

В отличие от template matching и контурного анализа, алгоритмы поиска ключевых точек более устойчивы к помехам, трансформациям и позволяют находить объекты даже при наличии физических помех. При этом высокая скорость работы некоторых методов позволяет применять их для поиска изображений в режиме реального времени даже на мобильных устройствах, что привело к возможности использования дополненной реальности в смартфонах и планшетных компьютерах рядовых пользователей. По аналогичному принципу работают и многие другие имеющиеся движки дополненной реальности (например, библиотека Vuforia от компании Qualcomm). Для достижения как можно более качественного уровня трекинга объекта (маркера) — он должен обладать достаточно большим числом уникальных (стабильных) ключевых точек, которые библиотека дополненной реальности быстро может выделить на видеопотоке и сопоставить с имеющимся шаблонным набором. Для этого необходимо использовать как можно более быстрый детектор, дескриптор и матчер, а также разработать алгоритм, который бы мог с уверенностью сказать, что объект был найден. Если выбор первых трёх компонентов осуществляется путём проведения экспериментов с замером скорости работы и оценкой инвариантности относительно различных трансформаций (подобные исследования мы уже отметили выше), то последняя составляющая требует более детальной проработки. Прежде всего это связано с тем, что отсутствуют какие-то стандартные программные средства, которые могли бы нам с уверенностью заявить о факте нахождения маркера. Подобные фильтры необходимо реализовывать самостоятельно с учётом задач проекта, в котором они будут использоваться.

Выводы

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

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