Распознавание образов для программистов

ВНИМАНИЕ! БЛОГ ПЕРЕЕХАЛ ПО АДРЕСУ
RECOG.RU

30 Март 2010

22. Функция ExtractSURF

написано в рубрике: OpenCV — Кручинин Александр @ 11:30 ДП

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

 

Функция ExtractSURF

 

void cvExtractSURF(

const CvArr* image,

const CvArr* mask,

CvSeq** keypoints,

CvSeq** descriptors,

CvMemStorage* storage,

CvSURFParams params

);

Параметры:

image

Входное 8-битное изображение (градации серого).

mask

Необязательная входная 8-битная маска. Если маска не нужна, то этот параметр равен 0. Особенности находятся только в тех областях, которые содержат больше чем 50% пикселей маски неравных нулю.

keypoints

Выходной параметр; двойной указатель на последовательность ключевых точек. Это будет последовательность структуры CvSURFPoint.

descriptors

Необязательный параметр вывода; двойной указатель на последовательность описателей; в зависимости от значения params.extended, каждый элемент последовательности будет или с 128 элементами с плавающей запятой (CV_32F) или вектор с 64 элементами. Если параметр NULL, описатели не вычисляются.

storage

Хранилище памяти для последовательности точек и дескрипторов.

params

Различные параметры алгоритма объединены в структуре CvSURFParams.

 

Функция cvExtractSURF находит хорошие особенности изображения так, как описано в [1]. Для каждой особенности возвращает ее местоположение, размер, ориентацию и произвольный описатель. Функция может использоваться для прослеживания объекта и локализации, изображения и т.д.

 

Структура CvSURFPoint

 

typedef struct CvSURFPoint

{

CvPoint2D32f pt; // позиция особенности в пределах изображения

int laplacian;   // -1, 0 или +1. Признак лапласиана в точке.

// Может использоваться для ускорения сравнения особенностей

// (обычно особенности с лапласианами не могут соответствовать)

int size;           // размер особенности

float dir;         // ориентация особенности: угол 0..360

float hessian; // значение матрицы Гессе (может использоваться, чтобы

                      //приблизительно оценить силы особенности;

                                 // подробнее в params.hessianThreshold)

}

CvSURFPoint;

 

Структура CvSURFParams

 

typedef struct CvSURFParams

{

int extended; // Если0 , то стандартные дескрипторы (64 элемента каждый),

          // 1 – расширенные дескрипторы (128 элементов каждый)

double hessianThreshold; // Только особенности с keypoint.hessian большим, чем должны быть извлечены

// Хорошее заданное по умолчанию значение – ~300-500 (может зависеть от среднего числа

// локального контраста и точность изображения).

// Пользователь может далее отфильтровывать некоторые особенности, основанные на их значениях матрицы Гессе

// или других характеристик

int nOctaves; // число октав, которые нужно использовать для извлечения.

          // С каждой следующей октавой размер особенности удвоен (3 по умолчанию)

int nOctaveLayers; // номер уровней в пределах каждой октавы (4 по умолчанию)

}

CvSURFParams;

 

CvSURFParams cvSURFParams(double hessianThreshold, int extended=0); //возвращает значения по умаолчанию

 

Литература:

1. Herbert Bay, Tinne Tuytelaars and Luc Van Gool “SURF: Speeded Up Robust Features”, Proceedings of the 9th European Conference on Computer Vision, Springer LNCS volume 3951, part 1, pp 404–417, 2006.

21 Март 2010

21. Выделение отличных от фона объектов

написано в рубрике: OpenCV — Кручинин Александр @ 9:57 ДП

Одной из задач распознавания графических образов является задача выделения на заранее известном неподвижном фоне объектов, которых раньше там не было. Эта задача несколько отличается от той, что была рассмотрена в параграфе 12. Там надо было найти направление движения. В этом параграфе будет рассмотрено, как, к примеру, выделить руку на неподвижном фоне. Программа достаточно простая, она представлена в листинге 21.1.

 

Листинг 21.1. Выделение новых объектов на известном фоне

//Необходимо подключить камеру

      CvCapture* capture = 0;

    capture = cvCaptureFromCAM(0 );

 

      if (!capture) return 1;

 

      cvNamedWindow( “Motion”, 1 );

 

      IplImage* image[MAX_CAM_CADR];

 

      CvScalar color;

      CvPoint cv1;

      CvFont font;

      cvInitFont( &font, CV_FONT_HERSHEY_SIMPLEX, 1.3f,

                 1.3f,0,1, 8 );

 

      cv1.x=70;   cv1.y=120;

      color = CV_RGB(255,0,255);

 

      int i,j;

      for(;;)

      {

            IplImage* image1;

            if( !cvGrabFrame( capture ))

                break;

        image1 = cvRetrieveFrame( capture );

           

            cvPutText( image1, “Press, when you ready”, cv1, &font, color );

 

 

        cvShowImage( “Motion”, image1);

 

        if( cvWaitKey(10) >= 0 ) break;

      }

 

      //обучаем фон

 

      for(i=0;i<MAX_CAM_CADR;i++)

    {

        if( !cvGrabFrame( capture ))

                break;

        image[i] = cvRetrieveFrame( capture );

 

        cvShowImage( “Motion”, image[i]);

 

        if( cvWaitKey(20) >= 0 ) break;

    }

 

      //Теперь надо посчитать m  для каждых

 

      float *m=new float[image[0]->height*image[0]->width*3];   

 

      int i1,j1;

      uchar* ptr;

 

 

      for(i=0;i<image[0]->height;i++)

            for(j=0;j<image[0]->width;j++)

                  for(j1=0;j1<3;j1++)

                  {

                        m[(i*image[0]->width+j)*3+j1]=0;

                        for(i1=0;i1<MAX_CAM_CADR;i1++)

                        {

                             ptr = (uchar*) (image[i1]->imageData);

                             m[(i*image[0]->width+j)*3+j1]+=ptr[j*3+i*image[i1]->widthStep+j1];

                        }

                        m[(i*image[0]->width+j)*3+j1]=m[(i*image[0]->width+j)*3+j1]/MAX_CAM_CADR;

                  }

 

      //Раз запомнили – можно входить в цикл обработки изображений

 

      float porog=60.0;

      float k=0;

 

      for(;;)

      {

            IplImage* image1;

            if( !cvGrabFrame( capture ))

                break;

        image1 = cvRetrieveFrame( capture );

           

 

            ptr = (uchar*) (image1->imageData);

            for(i=0;i<image[0]->height;i++)

                  for(j=0;j<image[0]->width;j++)

                  {

                        k=0;

                        for(j1=0;j1<3;j1++)

                             k+=abs(m[(i*image1->width+j)*3+j1]-ptr[j*3+i*image1->widthStep+j1]);

                            

                        if (k<=porog)

                        for(j1=0;j1<3;j1++){

                             if (j1==0) ptr[j*3+i*image1->widthStep+j1]=255;

                             else ptr[j*3+i*image1->widthStep+j1]=0;

                        }

                  }

 

        cvShowImage( “Motion”, image1);

 

        if( cvWaitKey(10) >= 0 ) break;

      }

     

                 

      //Удаляем все

 

      cvReleaseCapture( &capture );

    cvDestroyWindow( “Motion” );

 

      delete m;

 

Смысл выделения неизвестных объектов заключается в следующем. В буфер image запоминается определённое количество кадров первоначального фона. В программе это делается во втором цикле, а в первом ожидается нажатие любой клавиши. Затем, под каждую точку и каждый цвет (R, G и B) выделяется память, в которую будет записываться среднее значение, полученное в нескольких определённых кадрах. После того, как среднее значение подсчитано, программа входит в цикл выделения неизвестных объектов. Здесь porog – это пороговое значение, характеризующее отклонение от среднего, выше которого можно считать объект неизвестным. Проверяя каждую точку изображения на отличия от этого порога, выделяем неизвестные объекты. Значения порога зависят от освещения, появления теней и качества камеры. Результат работы программы представлен на рисунке 21.1

Рис. 21.1. Результат выделения неизвестных объектов на изображении

Рис. 21.1. Результат выделения неизвестных объектов на изображении

16 Март 2010

20. Нейронные сети в OpenCV (Neural networks)

написано в рубрике: OpenCV — Кручинин Александр @ 12:04 ПП

ML поддерживает нейронные сети прямого распространения, а особенно многослойные перцептроны (MLP). MLP состоит из входного уровня, выходного уровня и одного или нескольких скрытых уровней. Каждый уровень в MLP включает один или более нейронов, который направлено связаны с нейронами предыдущего и следующего уровней. На рисунке 20.1 приведён пример 3-х уровневого перцептрона с 3-мя входными, 2-мя выходными и 5-ью скрытыми нейронами.

 

Рис. 20.1. Пример перцептрона

Рис. 20.1. Пример перцептрона

Все нейроны в MLP подобны. Каждый из них имеет несколько входных связей (то есть требуется значения вывода от нескольких нейронов в предыдущем уровне) и нескольких связей вывода (то есть ответ для нескольких нейронов в следующем уровне). Значения, найденные на предыдущем уровне суммированы с некоторыми весовыми коэффициентами, индивидуальными для каждого нейрона, плюс значение смещения (bias), и сумма преобразовывается, используя функцию активации f, которая может быть также различна для различных нейронов (Рис. 20.2).

 

Рис. 20.2

Рис. 20.2

Учитывая выводы {xj} уровня n, выводы {yi} уровня n+1 вычислены как:

20.3.                          (20.1)

Могут использоваться различные функции активации, ML поддерживает три.

1. Функция идентичности (CvANN_MLP::IDENTITY): f(x)=x

2. Симметричная сигмовидная (CvANN_MLP::SIGMOID_SYM):

20.4.                            (20.2)

Заданный по умолчанию выбор для MLP. Стандартный сигмоид с β=1, α=1 показан на рисунке 20.3.

 

Рис. 20.3. Симметричная сигмовидная функция.

Рис. 20.3. Симметричная сигмовидная функция.

3. Функция гауссиана (CvANN_MLP::GAUSSIAN):

20.6                               (20.3)

Но она не полностью поддерживается на настоящий момент.

 

В ML все нейроны имеют те же самые функции активации, с теми же самыми свободными параметрами (α, β), которые определены пользователем и не изменены обучающими алгоритмами.

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

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

Чем больше размер сети (включая скрытые уровни), тем больше гибкость сети, а ошибка минимальна. Однако при увеличении размера сети может возникать ошибка шума, которая после достижения определенного предела начинает расти. Кроме того, большие сети намного дольше обучать, чем малые.

ML поддерживает 2 алгоритма MLP: 1) классический случайный последовательный алгоритм с обратным распространением; 2) пакетный RPROP алгоритм.

15 Март 2010

19. Машинное обучение в OpenCV

написано в рубрике: OpenCV — Кручинин Александр @ 10:17 ПП

19. Машинное обучение в OpenCV

 

В OpenCV поддерживаются следующие алгоритмы машинного обучения (Machine Learning).

 

1. Mahalanobis

 

Расстояние Махаланобиса. Метод основан на корреляции между переменными, с которой разные модели могут быть выявлены и проанализированы [1,2].

 

2. K-means

 

Метод кластеризации k-средних. Алгоритм представляет собой модификацию EM-алгоритма для разделения смеси гауссиан. Он разбивает множество элементов векторного пространства на заранее известное число кластеров k [3,4,5].

 

3. Normal/Naive Bayes classifier

 

Порождающий классификатор, особенностью которого является то, что гауссиан распределен и статистически независим друг от друга, что на самом деле не является истиной [6,7].

 

4. Decision trees

 

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

 

5. Boosting

 

Это обучение с учителем. Полное решение классификации основано на весовом комбинировании решений группы классификаторов. При тренировке обучают классификаторы по одному. Каждый классификатор в группе слаб (только чуть-чуть лучше случайного выбора). При тренировке обучается не только решение классификатора, но и какой вес оно будет иметь [10,11].

 

6. Random trees

 

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

 

7. Face detector / Haar classifier

 

Используется boosting. Уже есть обученные классификаторы для распознавания лиц [14].

 

8. Expectation maximization (EM)

 

Максимизация ожидания. Порождающий неконтролируемый, используемый для кластеризации. [15,16]

 

9. K-nearest neighbors

 

K-ближайших соседей. [17]

 

10. Neural networks / Multilayer perceptron (MLP)

 

         Нейронные сети. Больше всего подходит для распознавания символов – медленно обучается, но быстро работает [18].

 

11. Support vector machine (SVM)

 

Метод опорных векторов. Это набор схожих алгоритмов вида «обучение с учителем», использующихся для задач классификации и регрессионного анализа. Этот метод принадлежит к семейству линейных классификаторов. Он может также рассматриваться как специальный случай регуляризации по А. Н. Тихонову. Особым свойством метода опорных векторов является непрерывное уменьшение эмпирической ошибки классификации и увеличение зазора [19,20].

 

 

Литература:

1. P. Mahalanobis, “On the generalized distance in statistics,” Proceedings of the National Institute of Science 12 (1936): 49–55.

2. http://en.wikipedia.org/wiki/Mahalanobis_distance

3. S. Lloyd, “Least square quantization in PCM’s” (Bell Telephone Laboratories Paper), 1957. [“Lloyd’s algorithm” was later published in IEEE Transactions on Information Theory 28 (1982): 129–137.]

4. H. Steinhaus, “Sur la division des corpmateriels en parties,” Bulletin of the Polish Academy of Sciences and Mathematics 4 (1956): 801–804.

5. http://ru.wikipedia.org/wiki/K-means

6. M. Minsky, “Steps toward artifi cial intelligence,” Proceedings of the Institute of Radio Engineers 49 (1961): 8–30.

7. M. E. Maron, “Automatic indexing: An experimental inquiry,” Journal of the Association for Computing Machinery 8 (1961): 404–417.

8. L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone, Classification and Regression Trees, Monteray, CA: Wadsworth, 1984.

9. http://en.wikipedia.org/wiki/Decision_tree

10. Y. Freund and R. E. Schapire, “A decision-theoretic generalization of on-line learning and an application to boosting,” Journal of Computer and System Sciences 55 (1997): 119–139.

11. http://en.wikipedia.org/wiki/Boosting

12. T. K. Ho, “Random decision forest,” Proceedings of the 3rd International Conference on Document Analysis and Recognition (pp. 278–282), August 1995.

13. L. Breiman, “Random forests,” Machine Learning 45 (2001): 5–32.

14. P. Viola and M. J. Jones, “Robust real-time face detection,” International Journal of Computer Vision 57 (2004): 137–154.

15. A. Dempster, N. Laird, and D. Rubin, “Maximum likelihood from incomplete data via the EM algorithm,” Journal of the Royal Statistical Society, Series B 39 (1977): 1–38.

16. http://en.wikipedia.org/wiki/Expectation-maximization_algorithm

17. E. Fix, and J. L. Hodges, “Discriminatory analysis, nonparametric discrimination: Consistency properties” (Technical Report 4), USAF School of Aviation Medicine, Randolph Field, Texas, 1951.

18. D. E. Rumelhart, G. E. Hinton, and R. J. Williams, “Learning internal representations by error propagation,” in D. E. Rumelhart, J. L. McClelland, and PDP Research Group (Eds.), Parallel Distributed Processing. Explorations in the Microstructures of Cognition (vol. 1, pp. 318–362), Cambridge, MA: MIT Press, 1988.

19. V. Vapnik, Th e Nature of Statistical Learning Theory, New York: Springer- Verlag, 1995.

20. http://ru.wikipedia.org/wiki/Support_vector_machine

13 Март 2010

Модель для тестирования стереозрения

написано в рубрике: OpenCV, Стереозрение — Кручинин Александр @ 6:14 ПП

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

http://vidikon.com/download/test.zip [70КБ]

На рисунке 1 показан скриншот этой модели.

 

Рис.1. Скриншот модели

Рис.1. Скриншот модели

При запуске программы должно появиться 3 окна – большое и два маленьких, каждое из которых является отдельным процессом. Большое окно является основным, в котором показана 3-мерная модель.

Все действия необходимо осуществлять, когда окно находится в фокусе. Два других окна – это показания двух камер – левой и правой – находящиеся на видимом в главном окне шаре.

Клавиши:

F1 – в главном окне появляется и исчезает верхняя крышка.

F2 – делаются скриншоты с обоих камер и сохраняются в файлы.

Мышь:

Движения мышью при нажатой левой кнопке позволяют перетаскивать в главном окне всю сцену, а при нажатой правой кнопке – поворачивать её. Движения при нажатой клавише Left Ctrl приводят к смене обзора камер в дополнительных двух окнах. А нажатие левой кнопки мыши при нажатой клавише Left Ctrl приводит к движению шара (и камер) по направлению обзора.

Требования: Windows XP (наверняка более высшие), OpenGL 1.1. 

При использовании OpenCV для получения трёхмерной картины мира с камер нужно пользоваться следующей матрицей:

           Q[0][0]=1.000000 ;Q[0][1]=0.000000 ;Q[0][2]=0.000000 ;Q[0][3]=-155.5;

            Q[1][0]=0.000000 ;Q[1][1]=1.000000 ;Q[1][2]=0.000000 ;Q[1][3]=-102.5;

            Q[2][0]=0.000000 ;Q[2][1]=0.000000 ;Q[2][2]=0.000000 ;Q[2][3]=1157.85;

            Q[3][0]=0.000000 ;Q[3][1]=0.000000 ;Q[3][2]=-10;Q[3][3]=30 ;

155.5 и 102.5 – это центр изображения. Расстояние между камерами 0.01, а фокус – 1157.85. 

 

Старые записи »

Работает на WordPress