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

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

Opencv — это супер библиотека для работы с изображениями, которая написана под все популярные операционные системы, очень много всего умеет, есть хорошая документация. Но поскольку я привык работать с java, я нашел библиотеку-обертку на java для opencv: Javacv.
В javacv, к сожалению, с документацией и примерами все хуже, но при желании тоже можно разобраться. Сначала это у меня не получалось и я даже перешел на C++, но потом понял, что можно читать официальную документацию для C++ и пользоваться ей на java. Все классы и методы в java именованы либо точно так же, либо очень похоже.

Ниже я расскажу кратко об алгоритме, и как с нуля написать на java программу для поиска фрагмента изображения.

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

1. Сделать много фотографий где игрушка есть в кадре (положительная выборка)
2. Сделать много фотографий, где нет игрушки. (отрицательная выборка)
3. Установить opencv
4. Обучить алгоритм распознавания, получив на выходе xml файл с результатом
5. Подключить javacv
6. Написать небольшую программу на java, распознающую изображение по данному xml файлу

Об алгоритме

В opencv реализован алгоритм Виолы — Джонса, которым необходимо воспользоваться для решения этой задачи. Алгоритм был изобретен в 2001 году и сейчас сложно найти человека, который ни разу с ним не сталкивался. Яркий пример: выделение лиц в фото или видеокамере:

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

Во первых сразу определимся, что работа идет только с черно-белыми изображениями. Будем работать на примере распознавания лица. Давайте попытаемся увидеть особенности, свойственные именно лицу:

Что видно? Нос яркий, но слева и справа от носа темные участки. Под бровями светло, а ниже темно, щеки светлые и т.д...  Особенно хорошо это замечают художники, чтобы нарисовать правдоподобный портрет им необходимо точно уловить все эти особенности.

А что если все темные участки заменять черным цветом, а светлые белым? Узнаем мы лицо? Узнаем. А если делать эту замену не попиксельно, а крупными блоками, узнаем? Узнаем.  А если все зачеркнуть и на месте глаз, рта и носа поставить черточки узнаем?

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

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

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

Подготовка выборки для обучения

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

Установка opencv

Установка opencv под windows очень проста и состоит из двух шагов:

1. Запустить самораспаковывающийся архив, который можно скачать здесь
2. Установить переменные среды:
1. OPENCV_DIR = [куда распакавали архив]\build\x64\vc12 (или vc11 в зависимости от версии Micrisof Visuial C++ )
2. PATH = PATH + %OPENCV_DIR%\bin

Рекомендую устанавливать последнюю версию, с ней работать гораздо легче. 

Обучение алгоритма

Обучение алгоритма тоже состоит из двух шагов. Сначала надо подготовить vec файл с положительной выборкой с помощью opencv_createsamples.exe. У этой программы есть множество параметров, описанных в документации, ниже необходимый минимум:

opencv_createsamples.exe -info good.txt -vec samples.vec -w 20 -h 20 

good.txt — это файл, описывающий положительную выборку. Каждая строка представляет одну фотографию. Пример строки:

good\1.jpg  1  0 0 414 148

Сначала указывается имя файла относительно good.txt, затем через пробел количество искомых элементов на фотографии, затем координаты прямоугольника, внутри которого расположен искомый объект. Удобнее организовывать выборку так, чтобы каждая положительная фотография представляла собой обрезанное изображение обрезанного объекта.
samples.vec — имя файла, куда запишется результат выполнения программы
w и h — размеры образца. Здесь нужно указывать минимальный размер, чтобы отличить объект. Размеры должны быть пропорциональны объекту. Удобно сделать пробный запуск программы с дополнительными параметрами -num 5 -show и наглядно посмотреть результат работы, подготовив 5 пробных образцов.

Второй шаг является непосредственным обучением:
 

opencv_traincascade.exe -data haar -vec samples.vec 

-bg bad.txt -numStages 16 -minHitRate 0.99 

-maxFalseAlarmRate 0.4 -numPos 140 -numNeg 150 -w 20 -h 20

haar — папка, куда класть полученные результаты.
samples.vec — тот самый файл с положительной выборкой, который был сделан на первом шаге
bad.txt — адрес файла-описания отрицательных примеров. Структура аналогичная good.txt, но в строке указывается только имя файла.
numStages=16 — количество уровней каскада, которые программа будет обучать. Чем больше уровней, тем точнее, но тем дольше. Нормальное их количество от 16 до 25.
minHitRate=0.999 — коэффициент, определяющий качество обучения. Доля ошибок по исходной выборке. Чем выше коэффициент, тем выше уровень ложных тревог.
maxFalseAlarmRate =0.4 — уровень ложной тревоги. AdaBoost — такой алгоритм, который может любой уровень ложной тревоги по выборке натянуть. Но лучше что-то разумное сделать. По умолчанию все ставят 0.5. Но, возможно, будет иметь смысл поиграться. В случае, если выборка очень хорошая, то уровень требуемой тревоги будет быстро достигнут, и обучение будет остановлено.
numPos=140 — количество позитивных примеров. ВАЖНО! Казалось бы, тут должно стоять число файлов, которые у вас были. Но это не так (в большинстве руководств это не отмечено). Чем ниже коэффициент «minHitRate », тем больше ваших файлов будет считаться непригодными. В большинстве случаев достаточно поставить numPos 80% от имеющихся у вас положительных файлов. Лучше перестраховаться, чтобы через день работы программа не вылетела с ошибкой:)
numNeg=150 — количество имеющихся у вас негативных примеров.
w=20 h=20 — размер примитива. Точно такой же, как и на первом шаге.
(Часть материала взята из замечательной статьи на хабре, которую советую прочесть)

Обучение может длиться очень долго. У меня было около 150 отрицательных и положительных примеров, обучение прервалось спустя несколько часов на 12 стадии, достигнув максимального уровня тревоги. Пока я пишу этот пост, у меня обучается другая выборка уже третьи сутки. После обучения в папке haar появится файл cascade.xml — он и является результатом обучения.

Программа для распознавания на java

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

import org.bytedeco.javacpp.opencv_core;
import org.bytedeco.javacpp.opencv_objdetect;

import static org.bytedeco.javacpp.opencv_imgcodecs.*;
import static org.bytedeco.javacpp.opencv_imgproc.cvRectangle;

public class Detector {

    private static final String CASCADE_FILENAME = "C:\\learn\\cascade.xml";
    private static  opencv_objdetect.CascadeClassifier classifier = new opencv_objdetectCascadeClassifier(CASCADE_FILENAME);

 private static boolean handleImage(String srcFName, String resultFName) {
        //читаем изображение из файла
        opencv_core.Mat mat = imread(srcFName, CV_LOAD_IMAGE_GRAYSCALE); 
        //сюда складываем найденное
        opencv_core.RectVector rectVector = new opencv_core.RectVector(); 
        classifier.detectMultiScale(mat, rectVector); //поиск фрагментов
        boolean hasFound = rectVector.size() > 0;
        if (hasFound) {
            //открываем снова изображение для рисования
            opencv_core.IplImage src = cvLoadImage(srcFName, 0); 
            for (int i = 0; i <= rectVector.size(); i++) {
                opencv_core.Rect rect = rectVector.get(i);
                int height = rect.height();
                int width = rect.width();
                int x = rect.tl().x();
                int y = rect.tl().y();
                opencv_core.CvPoint start = new opencv_core.CvPoint(x, y);
                opencv_core.CvPoint finish = new opencv_core.CvPoint(x + width, y + height);
                //обводим объект в прямоугольник
                cvRectangle(src, start, finish, opencv_core.CvScalar.RED, 2, 8, 0); 
            }
            cvSaveImage(resultFName, src); //сохраняем копию с обведенными объектами
        }
        return hasFound;
    }
}

В образцах javacv можно найти другой пример для распознавания изображений, но он работает со старым API opencv, который использует устаревший формат файла cascade.xml. Для нового формата необходимо работать с современным API.

Работа алгоритма

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