Max Taranukhin: ноября 2012

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

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

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

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

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:

int main(int argc, char *argv[])

{

        if (argc < 3) return -1;

        for (int i = 1; i < argc; ++i) {

                cvNamedWindow(argv[i]);

                images.push_back(cvLoadImage(argv[i]));

                cvShowImage(argv[i], images.at(i-1));

        }

        IplImage *result;

        std::cout << "Make a panorama from images:n";

        for (int i = 0; i < images.size() - 1; ++i)

        {

                if (i > 0) images.at(i) = result;

                remapping(images.at(i), images.at(i+1), &result);

        }

        cvNamedWindow("win");

        cvShowImage("win", result);

        cvWaitKey();

        for (int i = 0; i < images.size(); ++i)

                cvReleaseImage(&images.at(i));

        cvReleaseImage(&result);

        cvDestroyAllWindows();

        return 0;

}

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

int remapping(IplImage *img1, IplImage *img2, IplImage **result)

{

        // features points

        CvSeq *keyPoints1, *keyPoints2;

        CvSeq *desPoints1, *desPoints2;

        // for cvExtractSURF

        CvMemStorage *storage = cvCreateMemStorage();

        CvSURFParams params = cvSURFParams(500,1);

        std::vector<int> ptPairs;

        std::cout << "Remapping...n";

        cvExtractSURF(img1, 0, &keyPoints1, &desPoints1, storage, params);

        cvExtractSURF(img2, 0, &keyPoints2, &desPoints2, storage, params);

        flannFindPairs(keyPoints1, desPoints1, keyPoints2, desPoints2, ptPairs);

        int n = (int)(ptPairs.size()/2);

        if (n < 4) return 0;

        std::vector<CvPoint2D32f> pt1, pt2;

        pt1.resize(n);  pt2.resize(n);

        for(int j = 0; j < n; ++j) {

                pt1[j] = ((CvSURFPoint*)cvGetSeqElem(keyPoints1,ptPairs[j*2]))->pt;

                pt2[j] = ((CvSURFPoint*)cvGetSeqElem(keyPoints2,ptPairs[j*2+1]))->pt;

        }

        srcPoints = cv::Mat(1, n, CV_32FC2, &pt1[0]);

        disPoints = cv::Mat(1, n, CV_32FC2, &pt2[0]);

        // Calculating matrix of homography

        H = cv::findHomography(srcPoints, disPoints, CV_RANSAC, 5);

        std::cout << "Perspective transformation H between two images:n";

        std::cout << "H = n" << H << "n";

        int maxX, maxY, minX, minY;

        int maxX2, maxY2, minX2, minY2;

        // Define image's size

        ImageSizePoint(img1, &H, &minX, &minY, &maxX, &maxY);

        ImageSizePoint(img2, 0, &minX2, &minY2, &maxX2, &maxY2);

        // Select the most minimal

        minX = std::min(minX, minX2); minY = std::min(minY, minY2);

        // if the image is out of the window border             // the move images

        if (minX < 0) minX = std::abs(minX);

        else    minX = 0;

        if (minY < 0) minY = std::abs(minY);

        else    minY = 0;

        globalMaxX = std::max(maxX, maxX2);

        globalMaxY = std::max(maxY, maxY2);

        // Create final image

        *result = cvCreateImage(cvSize(  std::max(maxX,maxX2) + minX,

                                        std::max(maxY,maxY2) + minY)

                                        ,img2->depth,img2->nChannels);

        // H^(-1)

        H=H.inv();

        CvScalar s;

        // Display original 2nd image

        for (int i = 0; i < img2->height; ++i)

                for (int j = 0; j < img2->width; ++j)

                {

                        s = cvGet2D(img2, i, j);

                        cvSet2D(*result, i+minY, j+minX, s);

                }

        vector<double> x;

        // Remapping 1st image

        for (int i = -minY; i < ((*result)->height - minY); ++i)

                for (int j = -minX; j < ((*result)->width - minX); ++j)

                {

                        // Compute point's coordinates at remapping image

                        // x = H^(-1)*x'

                        x = matrixMultiplication(&H, j, i);

                        // If does computed point exists at 1st image

                        // note: x(0)=j' x(1)=i'

                        if (    x(1)>=0 && x(1)<img1->height &&

                                x(0)>=0 && x(0)<img1->width)

                        {

                                s = cvGet2D(img1, x(1), x(0));

                                cvSet2D(*result, i+minY, j+minX, s);

                        }

                }

        return 1;

}

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

void flannFindPairs(...)

void ImageSizePoint(...)

vector<double> matrixMultiplication(...)

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

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

где А, В - произвольные числа, которые не могут равняется нулю одновременно. Вектор (А, В) - называется нормальным вектором прямой, который является перпендикулярным к прямой. При С=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:

$x=l\times l'$

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

$l=x\times x'$

Попробуем найти пересечение двух параллельных прямых l=(a, b,c)

. Найдем их векторное произведение:

$\left|\begin{matrix} i & j & k \\ a & b & c \\ a & b & c'\end{matrix} \right| =(c'-c)(ib-ja)\Rightarrow(b,-a,0)^T$

Т.е. мы получили точку лежащую на бесконечности в направлении (b,-a), что соответствует действительности.
Вектор в однородных координатах $(x_1, x_2, x_3), x_3\neq 0$ , соответствует точке из двухмерного пространства $\mathbb{R}^2$ . Если $\mathbb{R}^2$ дополнить точками где последняя координата x_3=0

, то мы получим так называемое проективное пространство $\mathbb{P}^2$ . Точки где последняя координата x_3=0

, называются идеальными точками или точками на бесконечности.

Max Taranukhin

воскресенье, 11 ноября 2012 г.

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

воскресенье, 4 ноября 2012 г.

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

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

воскресенье, 11 ноября 2012 г.

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

воскресенье, 4 ноября 2012 г.

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

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

воскресенье, 11 ноября 2012 г.

воскресенье, 4 ноября 2012 г.