Классификация изображений с использованием bag-of-words методов

Введение

Презентацию к лабораторной работе Вы можете скачать здесь.

Дополнительные материалы к лабораторной работе Вы можете скачать здесь.

В лабораторной работе рассматривается один из наиболее распространенных классов алгоритмов классификации изображений: так называемые bag-of-words (также известные как bag-of-features или bag-of- keypoints) методы [13]. Фактически bag-of-words подход использует в качестве описания гистограмму вхождений отдельных шаблонов в изображение. Корни идеи восходят к задаче классификации текстов, для решения которой используют описания в виде гистограмм вхождений в документ слов из заранее составленного словаря.

Основные шаги алгоритмов класса bag-of-words могут быть описаны следующим образом:

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

В настоящей работе рассматривается ряд методов детектирования ключевых точек и построения их дескрипторов, обучения словаря с использованием алгоритма кластеризации k-средних(KMeans) [5], а также построения признаковых описаний объектов на основе данного словаря. Приводятся примеры использования алгоритмов обучения с учителем для классификации изображений с использованием вычисленных признаковых описаний. В работе демонстрируется использование соответствующих операций на базе средств открытой библиотеки компьютерного зрения OpenCV [19].

1. Методические указания

1.1. Цели и задачи работы

Цель данной работы – изучить bag-of -words подход для классификации изображений с использованием соответствующих функций библиотеки компьютерного зрения OpenCV.

Данная цель предполагает решение следующих задач:

1. Изучить bag-of-words подход для классификации изображений и принцип работы базовых операций обработки изображений:

2. Рассмотреть прототипы функций, реализующих перечисленные операции в библиотеке OpenCV.

3. Разработать простые примеры использования указанного набора функций.

4. Разработать консольное приложение, содержащее реализацию bag-of- words подхода для задачи классификации изображений двух категорий.

5. Провести вычислительный эксперимент на основе подмножества изображений из набора данных Caltech-101 [14].

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

7. Реализовать подход для построения словаря на основе Gaussian Mixture Model [5] и сравнить полученные результаты с ранее реализованным подходом.

1.2. Структура работы

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

1.3. Тестовая инфраструктура

Вычислительные эксперименты проводились с использованием следующей инфраструктуры (табл. 11.1).

1.4. Требования к участнику лабораторной работы

Необходимо предварительное изучение участником работы теоретического материала по следующим темам:

Также требуется ознакомление с материалами лабораторной работы "Машинное обучение в библиотеке OpenCV".

1.5. Рекомендации по проведению занятий

При выполнении данной лабораторной работы рекомендуется следующая последовательность действий:

2. Обзор возможностей модуля features2d библиотеки OpenCV

2.1. Детектирование ключевых точек на изображении

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

Одним из наиболее простых алгоритмов, который находит на изображении углы, является детектор Моравеца (Moravec) [15]. Основная идея алгоритма заключается в поиске точек, соответствующих максимуму изменения суммарной интенсивности в окрестности рассматриваемого пикселя при смещении данной окрестности на один пиксель в каждом из восьми принципиальных направлений (2 горизонтальных, 2 вертикальных и 4 диагональных). Основными недостатками данного детектора являются отсутствие инвариантности к преобразованию типа "поворот" и возникновение большого числа ложных срабатываний на диагональных ребрах. Детектор Моравеца обладает свойством анизотропии в 8 принципиальных направлениях смещения окна.

Детектор Харриса (Harris) [16] строится на основании детектора Моравеца и является его улучшением. По сравнению со своим предшественником он инвариантен относительно поворота, количество ложных срабатываний не велико за счет введения свертки с Гауссовыми весовыми коэффициентами. Однако результаты поиска значительно меняются при масштабировании изображения. Также существуют модификации детектора Харриса, которые учитывают вторые производные функции интенсивности (например, детектор Харриса-Лапласа (Harris- Laplace) [10]).

Детектор MSER (Maximally Stable Extremal Regions) [9] выделяет множество регионов, являющихся областями локального экстремума интенсивности, максимально устойчивыми к вариациям интенсивности в окрестности данных регионов. Детектор обладает свойством инвариантности относительно масштабирования изображения. Похожая идея поиска областей с экстремальными свойствами интенсивности пикселей, устойчивых к изменению масштаба, лежит в основе детекторов LoG (Laplacian of Gaussian [7]) и SIFT [8]).

Приведенные выше детекторы определяют расположение ключевых точек на изображении, используя только пиксели исходного изображения. Альтернативный подход состоит в том, чтобы использовать алгоритмы машинного обучения для тренировки классификатора точек на некотором множестве изображений. FAST-детектор (Features from Accelerated Test) [11] является типичным представителем данного класса детекторов.

Более подробное описание детекторов ключевых точек приведено в лекционной части курса.

В библиотеке OpenCV реализованы следующие детекторы: FAST [11], STAR [1], SIFT [8], SURF [2], ORB [12], MSER [9], GoodFeaturesToTrack [20], Harris [16], Dense [17], Simple blob [17]. Для использования детекторов особых точек необходимо подключить заголовочный файл opencv2/features2d/features2d.hpp и библиотеку features2d243(d).lib.

Классы, содержащие реализацию данных детекторов, унаследованы от базового абстрактного класса FeatureDetector. Рассмотрим подробнее методы данного класса.

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

Ptr<FeatureDetector> FeatureDetector::create( 
                                const string detectorType) 
                                

В качестве параметра данной функции передается строка, содержащая идентификатор типа детектора ("FAST", "STAR", "SIFT", "SURF", "ORB", "MSER", "GFTT" (GoodFeaturesToTrack), "HARRIS", "Dense", "SimpleBlob".

Для того, чтобы найти на изображении ключевые точки с использованием созданного детектора, необходимо вызвать метод detect

void FeatureDetector::detect(const Mat image,        
vector<KeyPoint> keypoints,  
         const Mat mask=Mat() ) const 
         

Рассмотрим параметры данного метода:

Необходимо учесть, что при использовании детекторов SIFT и SURF требуется в исходном коде дополнительно подключить заголовочный файл opencv2/nonfree/nonfree.hpp, а в настройках проекта библиотеку nonfree243(d).lib. Наряду с этим вызвать функцию инициализации данного модуля: initModule_nonfree().

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

// fileName – путь к изображению 
// keypoints – найденные ключевые точки на изображении 
void DetectKeypointsOnImage(const string fileName, 
                            vector<KeyPoint> keypoints) 
{ 
  // загружаем изображение из файла 
Mat img = imread(fileName);  
// инициализируем модуль nonfree для использования 
// детектора SIFT  
initModule_nonfree();  
// создаем SIFT детектор 
Ptr<FeatureDetector> featureDetector = 
                  FeatureDetector::create("SIFT"); 
// детектируем ключевые точки  
// на загруженном изображении 
featureDetector->detect(img, keypoints);  
} 

2.2. Вычисление детекторов ключевых точек на изображении

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

Одним из наиболее известных дескрипторов ключевых точек является SIFT (Scale Invariant Feature Transform) [8], в основе которого лежит идея вычисления гистограммы ориентированных градиентов в окрестности особой точки. Модификацией данного дескриптора является PCA-SIFT [6], который строится по той же схеме, используя окрестность большего размера. Для результирующего набора дескрипторов осуществляется снижение размерности векторов посредством анализа главных компонент (Principal Component Analysis, PCA) [5].

Дескриптор SURF (Speeded up Robust Features) [2] также относится к числу тех дескрипторов, которые одновременно выполняют поиск особых точек и строят их описание, инвариантное к изменению масштаба и повороту изображения. Фактически данный дескриптор представляет собой взвешенные значения градиентов и их абсолютных значений в 16 квадрантах, на которые разбита окрестность особой точки.

Цель создания дескриптора BRIEF (Binary Robust Independent Elementary Features) [4] состояла в том, чтобы обеспечить распознавание одинаковых участков изображения, которые были получены с разных углов обзора. При этом ставилась задача уменьшить количество выполняемых вычислений. В окрестности точки выбирается некоторым образом множество пар пикселей, и на данном множестве строится набор бинарных тестов, представляющих собой сравнение интенсивности в соответствующих пикселях. Результаты тестов объединяются в битовую строку, которая и является итоговым дескриптором ключевой точки. Более эффективной альтернативой дескриптору BRIEF является бинарный дескриптор ORB [12].

Подробное описание дескрипторов ключевых точек можно найти в лекционной части курса.

В библиотеке OpenCV реализовано вычисление следующих дескрипторов ключевых точек: SIFT, SURF, BRIEF, ORB, для использования которых необходимо в исходном коде приложения подключить заголовочный файл opencv2/features2d/features2d.hpp, а в настройках проекта библиотеку features2d243(d).lib

Классы, содержащие реализацию алгоритмов вычисления данных дескрипторов, унаследованы от базового абстрактного класса DescriptorExtractor. Рассмотрим подробнее методы данного класса.

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

Ptr<DescriptorExtractor> DescriptorExtractor::create( 
                     const string descriptorExtractorType) 
                     

В качестве параметра данной функции передается строка, содержащая идентификатор типа дескриптора ("SIFT", "SURF", "BRIEF", "ORB").

Для того чтобы вычислить дескрипторы ключевых точек на изображении с использованием созданного детектора, необходимо вызвать метод compute.

void  DescriptorExtractor::compute(const  Mat  image,          
          vector<KeyPoint> keypoints,  
Mat descriptors) const 

Рассмотрим параметры данного метода:

Необходимо учесть, что при использовании дескрипторов SIFT и SURF требуется дополнительно подключить заголовочный файл opencv2/nonfree/nonfree.hpp и библиотеку opencv_nonfree243(d).lib, а также вызвать функцию инициализации данного модуля: initModule_nonfree().

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

// img – исходное изображение 
// keypoints – ключевые точки на изображении 
// descriptors – вычисленные значения дескрипторов 
//          ключевых точек     
void ComputeKeypointDescriptorsOnImage( 
                  const string fileName, 
                  vector<KeyPoint> keypoints,  
                  Mat descriptors) 
{ 
  // инициализируем модуль nonfree для использования 
// дескрипторов SIFT 
// (если данная функция ранее не вызывалась) 
initModule_nonfree();  
// создаем объект класса вычисления SIFT дескрипторов 
Ptr<DescriptorExtractor> descExtractor = 
              DescriptorExtractor::create("SIFT"); 
// вычисляем дескрипторы ключевых точек  
// на загруженном изображении 
descExtractor->compute(img, keypoints, descriptors);  
} 

2.3. Обучение словаря с использованием алгоритма кластеризации K-means

Одним из основных подходов к обучению словаря дескрипторов является использование алгоритмов кластеризации, в частности, K-means [5], который разбивает множество объектов на заранее известное число кластеров. В основе данного алгоритма лежит итерационная процедура, в рамках которой вычисляются центроиды кластеров (как математическое ожидание относящихся к данным кластерам объектов), а потом обновляется информация о принадлежности каждого объекта к кластерам путем выбора ближайшего центроида.

Для обучения словаря с использованием алгоритма K-means в библиотеке OpenCV реализован класс BOWKMeansTrainer, унаследованный от базового абстрактного класса BOWKMeansTrainer. Рассмотрим методы данного класса.

BOWKMeansTrainer(int clusterCount,  
const TermCriteria   termcrit = TermCriteria(), 
   int attempts=3, int flags=KMEANS_PP_CENTERS)
   

Параметры конструктора данного класса соответствуют параметрам функции kmeans библиотеки OpenCV.

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

void BOWTrainer::add(const Mat descriptors)  

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

После того, как выборка сформирована, обучение словаря выполняется с использованием метода cluster.

Mat BOWTrainer::cluster() 

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

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

// descriptors – предвычисленный набор дескрипторов 
// изображений, используемый при построении словаря; 
// vocSize – размер словаря; 
Mat  BuildVocabulary(const  std::vector<Mat>  descriptors,   
int vocSize) 
{ 
  // создаем объект класса BOWTrainer с числом 
// кластеров, равным vocSize, и остальными 
// параметрами, используемыми по умолчанию 
BOWKMeansTrainer bowTrainer(vocSize); 
// добавляем дескрипторы особых точек с изображений, 
// используемых при обучении словаря  
for (size_t i = 0; i < descriptors.size(); i++) 
{ 
     bowTrainer.add(descriptors[i]); 
} 
// вызываем метод обучения словаря 
Mat voc = bowTrainer.cluster(); 
return voc; 
} 

2.4. Вычисление признаковых описаний изображений

Большинство известных алгоритмов обучения с учителем требует описания каждого объекта в виде векторов одинаковой длины. В связи с этим напрямую использовать вычисленные значения дескрипторов, объединенные в один вектор, для решения задачи классификации не представляется возможным, т.к. в общем случае число ключевых точек на изображениях различно. К тому же, такое представление в любом случае не обладало бы инвариантностью относительно многих преобразований изображения, т.к. при этом обычно изменяется расположение данных точек и, следовательно, расположение дескрипторов внутри объединенного вектора. Данная проблема решается при использовании bag-of-words подхода [13], в котором изображение описывается не самими дескрипторами, а частотами встречаемости их различных типов на изображении. Типы дескрипторов описываются словарем, который содержит центроиды кластеров дескрипторов особых точек. Таким образом, в случае, когда словарь уже вычислен, признаковое описание изображения вычисляется по следующей схеме:

Библиотека OpenCV содержит класс BOWImgDescriptorExtractor, реализующий данную схему. Рассмотрим подробнее методы данного класса.

BOWImgDescriptorExtractor::BOWImgDescriptorExtractor( 
const Ptr<DescriptorExtractor> dextractor,  
const Ptr<DescriptorMatcher> dmatcher) 

Рассмотрим параметры конструктора данного класса:

Для того чтобы задать словарь, используемый при вычислении признакового описания изображения, необходимо вызвать метод setVocabulary

 
void  BOWImgDescriptorExtractor::setVocabulary(const  Mat 
vocabulary) 

В качестве параметра данному методу передается матрица, содержащая центроиды кластеров (обычно это матрица возвращается методом cluster класса BOWTrainer).

Вычисление признакового описания изображения осуществляется при помощи метода compute.

 
void BOWImgDescriptorExtractor::compute(const Mat image, 
vector<KeyPoint> keypoints,  Mat imgDescriptor, 
vector<vector<int>>* pointIdxsOfClusters=0, 
Mat* descriptors=0 ) 

Рассмотрим параметры данного метода:

Два последних параметра являются необязательными.

Рассмотрим пример функции, которая принимает на вход изображение и словарь дескрипторов ключевых точек и возвращает вычисленное признаковое описание изображения

 
// img – исходное изображение 
// voc – словарь дескрипторов ключевых точек; 
// imgDesc – вычисленное признаковое описание изображения 
void ComputeImgDescriptor(Mat img, Mat voc, Mat imgDesc) 
{ 
  // создаем SIFT детектор ключевых точек 
  Ptr<FeatureDetector> featureDetector = 
                         FeatureDetector::create("SIFT"); 
  // создаем объект класса вычисления 
  // SIFT дескрипторов ключевых точек 
Ptr<DescriptorExtractor> dExtractor = 
               DescriptorExtractor::create("SIFT"); 
// создаем объект класса, находящего ближайший 
// к дескриптору центроид (по L2 метрике) 
Ptr<DescriptorMatcher> descriptorsMatcher =  
                DescriptorMatcher::create("BruteForce"); 
  // создаем объект класса, вычисляющего 
  // признаковое описание изображений 
Ptr<BOWImgDescriptorExtractor> bowExtractor = new  
                              BOWImgDescriptorExtractor( 
                                    dExtractor,  
                                    descriptorsMatcher); 
  // устанавливаем используемый словарь 
  // дескрипторов ключевых точек 
bowExtractor->setVocabulary(voc); 
// находим ключевые точки на изображении vector<KeyPoint> keypoints; 
featureDetector->detect(img, keypoints); 
// вычисляем признаковое описание изображения 
bowExtractor->compute(img, keypoints, imgDesc); 
} 

3. Программная реализация

3.1. Разработка программы классификации изображений с использованием bag-of-words методов

3.1.1. Требования к приложению

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

3.1.2. Структура приложения

Приложение будет состоять из набора вспомогательных функций (auxiliary.cpp/h), основного модуля, содержащего реализацию основных стадий bag-of-words подхода к классификации изображений с использованием функций OpenCV (bow.cpp/h), и файла c исходным кодом основной функции (main.cpp). В рамках лабораторной работы предлагается реализовать функции из основного модуля; вспомогательные функции и код основной функции поставляется в реализованном виде.

Рассмотрим вспомогательные функции.

void GetFilesInFolder(const string dirPath, 
                      std::vector<string> filesList) 
                      

Заполняет массив filesList списком всех файлов с расширением *.jpg из директории dirPath. Рассмотрим параметры данной функции:

void InitRandomBoolVector(vector<bool> mask, double prob)

Заполняет булевский вектор mask случайными значениями (true с вероятностью prob). Рассмотрим параметры данной функции:

Рассмотрим функции из модуля bow.cpp, которые необходимо реализовать в рамках лабораторной работы.

Mat TrainVocabulary(const std::vector<string> filesList, 
     const std::vector<bool> isVoc,  
   const Ptr<FeatureDetector> keypointsDetector, 
     const Ptr<DescriptorExtractor> dExtractor, 
int vocSize)