Понарамное фото с использованием OpenCV

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

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

1. Для каждого из двух изображений найти особые точки (о том что это такое ниже) и их дескрипторы.
2. Сопоставление особых точек двух изображений.
3. Отсеивание ложных совпадений точек.
4. Построение матрицы гомографии. 
5. Проецирование с помощью полученной матрицы гомографии одного изображения на другое.

Теперь подробнее по каждому пункту.

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

Есть несколько алгоритмов решающих задачу нахождения особых точек изображения. Те что я знаю, это алгоритм Speeded Up Robust Features (SURF) и Scale Invariant Feature Transform (SIFT). Описанием этих алгоритмов я заниматься не буду. Достаточно хорошо оба алгоритма описаны на хабре (SURF, SIFT). Для выявления особых точек в нашей программе будем использовать SURF, хотя можно было бы использовать и SIFT.

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

3. Из предыдущего шага мы получили набор особых точек которые сравнивая по дескрипторам являются общими для двух изображений. В этом наборе точек могут оказаться ложные совпадения. Т.е. может оказаться что дескрипторы точек совпадают, но на самом деле эти точки принадлежат совершенно разным частям изображений. Этих точек будет совсем не много в сравнении с "правильно" совпавшим точками, но нам их надо каким-то образом отсеять. Для этого мы будем использовать еще один алгоритм который называется RANdom SAmple Consensus (RANSAC), который поможет отсеять ложно совпавшие точки. 

4. На этом шаге мы построим матрицу гомографии для двух изображений.

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

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

1. int main(int argc, char *argv[])
2. {
3.         if (argc < 3) return -1;
4.  
5.         for (int i = 1; i < argc; ++i) {
6.                 cvNamedWindow(argv[i]);
7.                 images.push_back(cvLoadImage(argv[i]));
8.                 cvShowImage(argv[i], images.at(i-1));
9.         }
10.  
11.         IplImage *result;
12.  
13.         std::cout << "Make a panorama from images:n";
14.         for (int i = 0; i < images.size() - 1; ++i)
15.         {
16.                 if (i > 0) images.at(i) = result;
17.                 remapping(images.at(i), images.at(i+1), &result);
18.         }
19.  
20.         cvNamedWindow("win");
21.         cvShowImage("win", result);
22.  
23.         cvWaitKey();
24.  
25.         for (int i = 0; i < images.size(); ++i)
26.                 cvReleaseImage(&images.at(i));
27.  
28.         cvReleaseImage(&result);
29.         cvDestroyAllWindows();
30.  
31.         return 0;
32. }

В качестве входных параметров программа принимает имена файлов изображений (при условии что файлы находятся в той же папке что и  исполняемый файл) в том порядке котором они будут склеиваться. Каждое изображение будет перед склейкой показано в отельном окне (6 строка), а так же загружено в вектор (7). Вывод изображений в 8й строке. В 11й строке объявляется структура которая будет содержать результат склейки. Функция remapping в строке 17 склеивает два изображения. Результат склейки всех изображений будет выведен на экран в строке 21. В конце освобождается память.
Рассмотрим функцию remapping:

1. int remapping(IplImage *img1, IplImage *img2, IplImage **result)
2. {
3.         // features points
4.         CvSeq *keyPoints1, *keyPoints2;
5.         CvSeq *desPoints1, *desPoints2;
6.         // for cvExtractSURF
7.         CvMemStorage *storage = cvCreateMemStorage();
8.         CvSURFParams params = cvSURFParams(500,1);
9.  
10.         std::vector<int> ptPairs;
11.  
12.         std::cout << "Remapping...n";
13.  
14.  
15.         cvExtractSURF(img1, 0, &keyPoints1, &desPoints1, storage, params);
16.         cvExtractSURF(img2, 0, &keyPoints2, &desPoints2, storage, params);
17.  
18.         flannFindPairs(keyPoints1, desPoints1, keyPoints2, desPoints2, ptPairs);
19.  
20.         int n = (int)(ptPairs.size()/2);
21.         if (n < 4) return 0;
22.  
23.         std::vector<CvPoint2D32f> pt1, pt2;
24.         pt1.resize(n);  pt2.resize(n);
25.  
26.         for(int j = 0; j < n; ++j) {
27.                 pt1[j] = ((CvSURFPoint*)cvGetSeqElem(keyPoints1,ptPairs[j*2]))->pt;
28.                 pt2[j] = ((CvSURFPoint*)cvGetSeqElem(keyPoints2,ptPairs[j*2+1]))->pt;
29.         }
30.  
31.         srcPoints = cv::Mat(1, n, CV_32FC2, &pt1[0]);
32.         disPoints = cv::Mat(1, n, CV_32FC2, &pt2[0]);
33.         // Calculating matrix of homography
34.         H = cv::findHomography(srcPoints, disPoints, CV_RANSAC, 5);
35.  
36.         std::cout << "Perspective transformation H between two images:n"; 
37.         std::cout << "H = n" << H << "n";
38.  
39.         int maxX, maxY, minX, minY;
40.         int maxX2, maxY2, minX2, minY2;
41.         // Define image's size
42.         ImageSizePoint(img1, &H, &minX, &minY, &maxX, &maxY);
43.         ImageSizePoint(img2, 0, &minX2, &minY2, &maxX2, &maxY2);
44.         // Select the most minimal
45.         minX = std::min(minX, minX2); minY = std::min(minY, minY2);
46.         // if the image is out of the window border             // the move images
47.         if (minX < 0) minX = std::abs(minX);
48.         else    minX = 0;
49.         if (minY < 0) minY = std::abs(minY);
50.         else    minY = 0;
51.         globalMaxX = std::max(maxX, maxX2);
52.         globalMaxY = std::max(maxY, maxY2);
53.         // Create final image
54.         *result = cvCreateImage(cvSize(  std::max(maxX,maxX2) + minX,
55.                                         std::max(maxY,maxY2) + minY)
56.                                         ,img2->depth,img2->nChannels);
57.  
58.         // H^(-1)
59.         H=H.inv();
60.  
61.         CvScalar s;
62.         // Display original 2nd image
63.         for (int i = 0; i < img2->height; ++i)
64.                 for (int j = 0; j < img2->width; ++j)
65.                 {
66.                         s = cvGet2D(img2, i, j);
67.                         cvSet2D(*result, i+minY, j+minX, s);
68.                 }
69.  
70.         vector<double> x;
71.         // Remapping 1st image
72.         for (int i = -minY; i < ((*result)->height - minY); ++i)
73.                 for (int j = -minX; j < ((*result)->width - minX); ++j)
74.                 {
75.                         // Compute point's coordinates at remapping image
76.                         // x = H^(-1)*x'
77.                         x = matrixMultiplication(&H, j, i);
78.  
79.                         // If does computed point exists at 1st image
80.                         // note: x(0)=j' x(1)=i'
81.                         if (    x(1)>=0 && x(1)<img1->height &&
82.                                 x(0)>=0 && x(0)<img1->width)
83.                         {
84.                                 s = cvGet2D(img1, x(1), x(0));
85.                                 cvSet2D(*result, i+minY, j+minX, s);
86.                         }
87.                 }
88.         return 1;
89. }

Все волшебство выполняется именно в этой функции. В качестве параметров принимается два изображения для которых в строках 15 и 16 с помощью библиотечных функций OpenCV ищутся особые точки и их дескрипторы по алгоритму SURF. В строке 18 с помощью функции flannFindPairs сравниваются полученных ключевые точки. Если общих точек оказалось совсем мало, то в строке 21 мы завершаем работу функции, т.е. данные два изображения разные и склеить их не удастся.  В строке 34, мы находим матрицу гомографии с помощью библиотечной функции findHomography. Обратите внимание, что в параметрах указанно значение CV_RANSAC, т.е. для поиска матрицы гомографии будет использоваться алгоритм RANSAC. В строках с 39 по 56 мы вычисляем размеры конечного изображения и создаем соответствующего размера окно.
По скольку мы собираемся проецировать первое изображение в плоскость второго нам необходимо найти обратную матрицу к матрице гомографии, что и выполняется в строке 59.
Второе изображение оставляем исходным, т.е. мы его просто копируем в результирующее изображение (62-68), а вот первое копируем, но уже умножая на обратную матрицу гомографии (72-87). При этом надо отметить, что копирования и первого и второго изображения происходит с некоторым сдвигом. Это выполняется для этого что бы все изображение поместилось в результирующее окно. Вот собственно и все.
Так же в программе используются вспомогательные функции:

1. void flannFindPairs(...)
2. void ImageSizePoint(...)
3. vector<double> matrixMultiplication(...)

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

Проективное преобразование

И так, мы уже знаем что такое однородные координаты и проективное пространство  (или проективная плоскость). Есть еще одно очень важно понятие в проективной геометрии это проективное преобразование. Формальное определение выглядит так:

Проективным преобразованием - называется биективное отображение , такое что, для данных трех точек x, y и z лежащих на одной прямой, точки h(x), h(y) и h(z) так же будут лежать на одной прямой.
Иногда проективное преобразование называют гомографией. Для того что бы задать проективное преобразование между двумя проективными плоскостями используют так называемую матрицу гомографии H. Матрица гомографии H является не вырожденной матрицей размера 3х3. Тогда преобразование между двумя точками можно записать в следующем виде:

или в короче:

Как же вычислить матрицу гомографии? Этот вопрос пока остается открытым. При программировании же матрицу гомографии получают по 8 точкам - 4 точки с одного изображения и 4 точки с другого изображения. В библиотеке компьютерного зрения OpenCV есть специальная функция для нахождения матрицы гомографии cvFindHomography. 

Прямая линия в однородных координатах и проективное пространство

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

,

где А, В - произвольные числа, которые не могут равняется нулю одновременно. Вектор (А, В) - называется нормальным вектором прямой, который является перпендикулярным к прямой. При С=0 прямая проходит через начало координат.

Эта прямая может быть заданна вектором:

Соответствие между этим вектором и прямой определяется с точностью до k≠0. т.к. прямые Ax+By+C=0 и (kA)x+(kB)y+C=0 являются эквивалентными и векторы (A, B, C) и k(A, B, C) так же являются эквивалентными. Тогда мы можем говорить о некотором классе эквивалентности между вектором и прямой. Из этого класса исключается вектор (0, 0, 0) который не соответствует ни одной прямой.  

Для того что бы точка X=(x, y) принадлежала прямой l=(A, B, C) необходимо и достаточно что бы Ax+By+C=0. Это может быть записано в терминах скалярного произведения векторов, если X это точка в однородных координатах:

Это удобно вычислять при программировании используя матрицы. Т.е.:

Для того что бы узнать точку пересечения x для двух прямых l и l' необходимо найти векторное произведение этих двух прямых, результатом которого и будет искомая точка X:

А для того что бы построить прямую линию l проходящую через две точки x и x', необходимо вычислить векторное произведение:

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

Т.е. мы получили точку лежащую на бесконечности в направлении (b,-a), что соответствует действительности.
Вектор в однородных координатах , соответствует точке из двухмерного пространства .  Если   дополнить точками где последняя координата , то мы получим так называемое проективное пространство . Точки где последняя координата , называются идеальными точками или точками на бесконечности.

Однородные координаты

Что это такое?
Способ представления точки c координатами  в n-мерном пространстве в виде набора , где хотя бы один элемент отличен от нуля.

Где используется?
В компьютерной графике для представления объектов в пространстве.

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

Ну и как записать бесконечно удаленную точку в однородных координатах?
Выглядит это так:  - данная запись так же означает что перед нами не точка, а вектор. А запись вида:  говорит о том что перед нами точка, а не вектор. 

Инверсия односвязного списка

Очень долго тупил над этой задачей. На практике проще использовать чтение списка с конца. Так что задача имеет больше учебный характер. Немного погуглив нашел решение с помощью рекурсии.

Node * reverse(Node *head)
{
        if (head == 0) return 0;
        if (head->next == 0) return head;

        Node * tmp = reverse(head->next);

        head->next->next = head;
        head->next = 0;
        return tmp;
}

Инкапсулация

Инкапсулация в широком смысле упаковка данных вместе с функциями.

(с) Б. Эккель

Условная компиляция

Часто необходимо некоторым способом отладить программу. Конечно это надо делать с помощью отладчика типа gdb. Но иногда случается так, что отладчика нет под рукой и тогда на помощь может прийти условная компиляция с выводом отладочной информации. Но отсутствие отладчика не такая уж часто встречаемая проблема. Есть и другая задача, где применение условной компиляции неизбежно. Представьте себе, что ваша программа будет работать на нескольких платформах и в зависимости от платформы необходимо выполнять те или иные действия. Например подключать специфические для  данной ОС заголовочные файлы и соответственно вызывать разные функции. Здесь уж точно не обойтись без условной компиляции.
Для условной компиляции используются директивы препроцессора. Как известно директивы препроцессора начинаются с символа #. Например:

 #include <iostream>  //деректива препроцессора которая подключает заголовочный файл

Для условной компиляции используется директива

#ifdef NAME
...
#endif

или

#ifdef NAME
...
#elseif
...
#endif

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

#include <iostream>

int main()
{
        int var = 5;

        #ifdef DEBUG
                std::cout << "var: " << var << "\n";
        #endif
}

Для вывода отладочной информации необходимо определить имя DBUG в командной строке компилятора. Для компилятора GCC данная команда выполняется с помощью ключа -D name, где name - имя определяемой константы. Например:

g++ test.cpp -o test -D DEBUG

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

Представление float в памяти

Размер float на моем компьютере равен 4 байтам или 32 битам:

cout << sizeof(float); // 4

Согласно стандарту IEEE 754 формат представления float в памяти компьютера следующий:

0	0	1	1	1	1	1	1	1	0	0	1	1	1	1	0	0	0	0	0	0	1	0	0	0	0	0	1	1	0	0	1
1	8								23

Это представление числа 1,2345.

Т.е. 1 бит отводится под знак, 8 бит отводится для представления целой части и оставшиеся 23 бита для представления дробной части. А само вычисление производится по формуле:

Пример: Возьмем число изображенное выше 1,2345. Согласно формуле (-1)^0=1, т.е. наше число положительно. Далее вычисляем показатель степени. Для этого переведем двоичное значение 8ми битного поля целой части в десятичное представление:

01111111 =  1*2^0+1*2^1+1*2^2+1*2^3+1*2^4+1*2^5+1*2^6+0*2^7=

=1+2+4+8+16+32+64=127

Вычисляем по формуле:

2^(127-127)=2^0=1

Осталось вычислить дробную часть:

00111100000010000011001=1*2^(-3)+1*2^(-4)+1*2^(-5)+1*2^(-6)+1*2^(-13)+1*2^(-19)+1*2^(-20)+1*2^(-23)=0,125+0,0625+0,03125+0,01563+0,00012+0,0000019073+0,0000009537+0.000000119=(приблизительно)0,2345

Окончательно имеем 1+0,2345=1,2345.
Для того что бы увидеть битовое представление float на компьютере можно воспользоваться маленькой программкой:

#include <iostream>
using namespace std;

// Печать одной байта в битах
void printInBinary(const unsigned char val)
{
        for (int i = 7; i &gt;= 0; --i)
                if (val &amp; (1 &lt;&lt; i))
                        cout &lt;&lt; "1";
                else
                        cout &lt;&lt; "0";
}

int main()
{
        float f = 1.2345;
        unsigned char *ucp = 
              reinterpret_cast<unsigned char*="">(&amp;f);

        for (int i = sizeof(float) - 1; i &gt;= 0; --i)
                printInBinary(ucp[i]);
}

Трансляторы

Традиционно трансляторы делятся: интерпретаторы и компиляторы.

Интерпретатор - транслирует исходный текст программы в операции (которые могут состоять из нескольких машинных команд) и немедленно выполняет эти операции.

Компилятор - транслирует исходный текст программы в машинные команды, которые записывает в файл.

По мотивам Эккеля

Механизмы ООП

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


Объектно-ориентированное, или объектное, программирование (в дальнейшем ООП) — парадигма программирования, в которой основными концепциями являются понятия объектов и классов.[0]


Механизмы ООП:

• Инкапсуляция — свойство языка программирования, позволяющее пользователю не задумываться о сложности реализации используемого программного компонента (то, что у него внутри), а взаимодействовать с ним посредством предоставляемого интерфейса (публичных членов — методов, данных etc.), а также объединить и защитить жизненно важные для компонента данные.[1]
• Полиморфизм — возможность объектов с одинаковой спецификацией иметь различную реализацию. Полиморфизмом в программировании называется переопределение наследником функций-членов базового класса.[2]
• Наследование — механизм позволяющий описать новый класс на основе уже существующего (родительского), при этом свойства и функциональность родительского класса заимствуются новым классом. В C++ при наследовании одного класса от другого наследуется реализация класса, плюс класс-наследник может добавлять свои поля и функции или переопределять функции базового класса.[3]

Википедия пишет про еще один механизм:

• Абстракция — это придание объекту характеристик, которые четко определяют его концептуальные границы, отличая от всех других объектов. Основная идея состоит в том, чтобы отделить способ использования составных объектов данных от деталей их реализации в виде более простых объектов, подобно тому, как функциональная абстракция разделяет способ использования функции и деталей её реализации в терминах более примитивных функций, таким образом, данные обрабатываются функцией высокого уровня с помощью вызова функций низкого уровня.[4]