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

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

30 Январь 2010

RR1. Распознавание речевых команд

написано в рубрике: Распознавание речи — Кручинин Александр @ 8:07 ДП

Сегодня речь пойдёт о распознавании речевых команд. Теоретических подходов, патентов на изобретения и алгоритмы достаточно много. Ниже будет описано как программисту, без каких-либо речевых библиотек, разработать систему дикторозависимого распознавания речевых команд.

Прежде всего, вам нужен интерфейс для чтения/записи звуковых файлов и принятия информации с микрофона. Вы можете пользоваться готовыми библиотеками ил создать что-то своё, например, в листинге 1 показана простейшая функция для чтения звукового файла из одного старого престарого класса.

Листинг 1. Чтение несжатого WAV-файла

int WAVREAD::OpenFile(LPSTR FileName)

{

      WAVEFORMATEX wfx;

      char *p;

      DWORD *uk,size,readed;

      char buf[4],buf1[256],buf2[256];

      unsigned char buffer[1000];

      int i,k;

 

      HANDLE hFile=INVALID_HANDLE_VALUE;

      hFile=CreateFile(FileName,GENERIC_READ,FILE_SHARE_READ,0,

            OPEN_EXISTING,0,0);

      if (hFile==INVALID_HANDLE_VALUE) {

            return 1;

      }

      ReadFile(hFile,(void*)buf,4,&readed,0);

      if (buf[0]!=’R’ || buf[1]!=’I’ || buf[2]!=’F’ || buf[3]!=’F')

      {

            return 2;

      }

      ReadFile(hFile,(void*)buf,4,&readed,0);

      ReadFile(hFile,(void*)buf,4,&readed,0);

      if (buf[0]!=’W’ || buf[1]!=’A’ || buf[2]!=’V’ || buf[3]!=’E')

      {

            return 3;

      }

      ReadFile(hFile,(void*)buf,4,&readed,0);

      if (buf[0]!=’f’ || buf[1]!=’m’ || buf[2]!=’t’ || buf[3]!=’ ‘)

      {

            return 4;

      }

      ReadFile(hFile,(void*)buf,4,&readed,0);

      uk=(DWORD*)buf;

      size=uk[0];

      if (size>18) size=18;

      ReadFile(hFile,(void*)buffer,size,&readed,0);

      wfx=CreateWfx(*((WORD*)buffer),*((WORD*)buffer+1),

            *((DWORD*)buffer+1),*((DWORD*)buffer+2),

            *((WORD*)buffer+6),*((WORD*)buffer+7) );

      i=0;

      this->wfx=wfx;//Create wfx

      if (wfx.cbSize!=0)

            do{

                  ReadFile(hFile,(void*)buffer,1,&readed,0);

                  i++;

                  if (i==wfx.cbSize) break;

            }while(true);

      //Read Data from file

      k=0;

      do{

            k=ReadFile(hFile,(void*)buf,1,&readed,0);

            if (k==0) return 5;

            if (buf[0]==’d'){

                  k=ReadFile(hFile,(void*)buf,1,&readed,0);

                  if (k==0) return 5;

                if (buf[0]==’a')

                  {

                        k=ReadFile(hFile,(void*)buf,1,&readed,0);

                        if (k==0) return 5;

                        if (buf[0]==’t')

                        {

                             k=ReadFile(hFile,(void*)buf,1,&readed,0);

                             if (k==0) return 5;

                             if (buf[0]==’a')

                                   break;

                        }

                  }

            }

      }while(true);

      ReadFile(hFile,(void*)buf,4,&readed,0);

      size=*((DWORD*)buf);

      this->Size=size;

      this->Data= new BYTE[size];

      ReadFile(hFile,(void*)this->Data,size,&readed,0);

 

      if (hFile!=INVALID_HANDLE_VALUE)

             CloseHandle(hFile);

 

      return 0;

}

 

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

 http://www.fftw.org/

 Пользоваться её довольно просто – подключите lib-файл к проекту, выделите память для данных и вызовите БПФ функцию (Листинг 2).

 Листинг 2. Использование функций fftw

      fftw_complex *in, *out;

      fftw_plan pp;

      in = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * Signal_All1);

      out = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * Signal_All1);

      long o;

      for(o=0;o<Signal_All1;o++) {

            in[o][0]=Signal_ptr1[o];

            in[o][1]=0;

      }

      pp = fftw_plan_dft_1d(Signal_All1, in, out, FFTW_FORWARD, FFTW_ESTIMATE);

      fftw_execute(pp);

       fftw_destroy_plan(pp);

      fftw_free(in); fftw_free(out);

 

Далее, для удобства тестирования у вас должны быть функции вывода на экран (или в графический файл) содержимого WAV-файла и его спектра. Пример и того и другого для команды «Вставить» показаны на рисунках 1-2.

Рис. 1. Содержимое WAV-файла

Рис. 1. Содержимое WAV-файла

Рис.2. Спектр сигнала

Рис.2. Спектр сигнала

 

В качестве эталонов при распознавании у вас будут спектры команд, с которыми будут сравниваться неизвестные образы, поступающие например с микрофона. Для сравнения можно использовать корреляционный анализ. Но предварительно надо усреднить сигнал, построив гистограмму с меньшим количеством элементов, чем на рисунке 2. На рисунке 3 показано как строится гистограмма для 8 элементов. Значения внутри столбцов гистограммы усредняются, а диапазон частот выбирается в диапазоне человеческого голоса (до 8кГц).

Рис. 3. Гистограмма для 8 элементов

Рис. 3. Гистограмма для 8 элементов

Можно подобрать общее количество элементов гистограммы, при которых распознавание наилучшее. Например, 70.

Затем необходимо сравнивать неизвестный сигнал из 70 элементов с известным сигналом из 70 элементов по коэффициенту парной корреляции:

rr1.4                 (1)

где Mx  и My – оценки матожидания для переменных  x и y, Kxy – коэффициент  ковариации, sx  и  sy  – средние квадратичные отклонения

К сожалению, данный подход даёт невысокую достоверность, Так для набора из 5 команд: «Копировать», «Печать», «Вставить», «Команда», «Сохранить», достоверность распознавания составила чуть больше 90% на тестовой выборке из 135 команд.

26 Январь 2010

12. Управляем презентацией взмахом руки

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

12. Управляем презентацией взмахом руки

 

Наверняка многим из вас приходило в голову управлять действиями компьютера с помощью, например, движения рук. Хорошо было бы управлять переключением слайдов презентации на расстояния без использования специализированных средств, а только при наличии обычной Web-камеры. В листинге 12.1 представлен код функции, позволяющей определить взмах руки и эмулировать нажатие клавиши.

 

Листинг 12.1. Функция детектирования взмаха руки

void FoundMotion(IplImage* img1,IplImage* img2)

{

//Установка начальных параметров

      short VKCode = ‘ ‘;

      CvSize img_sz = cvGetSize( img1 );

      int win_size = 10;

 

      IplImage* eig_image = cvCreateImage( img_sz, IPL_DEPTH_32F, 1 );

      IplImage* tmp_image = cvCreateImage( img_sz, IPL_DEPTH_32F, 1 );

     

      int corner_count = MAX_CORNERS;

 

      CvPoint2D32f* cornersA = new CvPoint2D32f[ MAX_CORNERS ];

 

      cvGoodFeaturesToTrack(img1,eig_image,tmp_image,cornersA,&corner_count,

                                     0.01,5.0,0,3,0,0.04);

      cvFindCornerSubPix(img1,cornersA,corner_count,cvSize(win_size,win_size),

                                cvSize(-1,-1),cvTermCriteria(CV_TERMCRIT_ITER|CV_TERMCRIT_EPS,20,0.03));

 

      //Создаются дополнительные массивы для cvCalcOpticalFlowPyrLK

      char features_found[ MAX_CORNERS ];

      float feature_errors[ MAX_CORNERS ];

      CvSize pyr_sz = cvSize( img1->width+8, img2->height/3 );

      IplImage* pyrA = cvCreateImage( pyr_sz, IPL_DEPTH_32F, 1 );

      IplImage* pyrB = cvCreateImage( pyr_sz, IPL_DEPTH_32F, 1 );

      CvPoint2D32f* cornersB = new CvPoint2D32f[ MAX_CORNERS ];

 

      cvCalcOpticalFlowPyrLK(img1,img2,pyrA,pyrB,cornersA,cornersB,corner_count,cvSize( win_size,win_size ),5,features_found,feature_errors,cvTermCriteria( CV_TERMCRIT_ITER | CV_TERMCRIT_EPS, 20, .3 ),0);

 

      int all=0;

      int up=0;

      int down=0;

      F_LINE f;

//Совпадения с точками нашли, можно их обрабатвать

      for( int i=0; i<corner_count; i++ ) {

            if( features_found[i]==0|| feature_errors[i]>550 ) {

                                                continue;

            }

            CvPoint p0 = cvPoint(cvRound( cornersA[i].x ),cvRound( cornersA[i].y ));

            CvPoint p1 = cvPoint(cvRound( cornersB[i].x ),cvRound( cornersB[i].y ));

            //Удаляем точки с небольшим смещением

            if (sqrt((double)pow((double)p0.x-p1.x,2)+(double)pow((double)p0.y-p1.y,2))<10) continue;

            //Делаем формулу линии

            all++;

            f=MakeLine(p0.x,p0.y,p1.x,p1.y);

            //Только вертикальные линии

            if (f.b==2 && absf(f.b1)<0.2)

            {

                  if (p1.y<p0.y) down++;

                  else up++;

                  cvLine( img2, p0, p1, CV_RGB(255,0,0),2 );

            }

      }

      cvShowImage( “M”, img2);

 

      cvReleaseImage( &eig_image );

      cvReleaseImage( &tmp_image  );

      cvReleaseImage( &pyrA  );

      cvReleaseImage( &pyrB );

      delete cornersA;

      delete cornersB;

 

      if (motion_1>0) motion_1–;

      if (motion_1==10) motion_1=0;

 

      if (all>20)

      if ((double)up/all>0.4 && (double)down/all<0.1)

      {

            //объект двигается вверх

            if (motion_1<10) motion_1=10;

      }

 

      if (all>20)

      if ((double)down/all>0.4 && (double)up/all<0.1)

      {

            //объект идёт вниз

            if (motion_1>0 && motion_1<8) {

                  printf(”vzmax222222222\n”);

                  //Состоялся взмах

                  motion_1=15;

                  VKCode=VK_RIGHT;

                  keybd_event(VKCode, 0, 0, 0);

            }

 

      }

 

      printf(”%d;%d;%d\n”,all,up,down);

}

 

Листинг описан поверхностно – без подробного описания назначения функций. Часть кода взята из известной книги «Learning OpenCV» [1].

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

const int MAX_CORNERS = 500;

Первоначально выделяется память под хранение углов cornersA. Затем с помощью функции cvGoodFeaturesToTrack() находятся углы с наибольшим собственным значением в изображении. С помощью функции cvFindCornerSubPix() определяется точное местоположение углов или радиальных седловых точек.

После создания дополнительных массивов вызывается функция cvCalcOpticalFlowPyrLK(), которая осуществляет алгоритм слежения за точками Lucas-Kanade tracker. Подробнее об это алгоритме вы можете почитать в публикации [2] или в описании OpenCV.

В результате работы функции находятся совпадения с точками на втором изображении. Затем идёт обработка полученных результатов. В функции используются дополнительные переменные, структура и функция (Листинг 12.2).

 

Листинг 12.2. Дополнительные переменные, структуры и функции

//Переменная для отслеживания комбинации движения

int motion_1=0;

 

struct F_LINE

{

      int k1;

      int b;

      double b1,b2;

};

 

 

F_LINE MakeLine(double x1,double y1,double x2,double y2)

{

      F_LINE f;

      f.k1=3;

            //вычисляем координаыт линии от i3 к i4

      f.b=1;

      if (absf(x1-x2)<absf(y1-y2)) f.b=2;

      if (f.b==1)

      {

            //y=f(x);

            f.b1=(double)(y2-y1)/(x2-x1);

            f.b2=(double)y1-(double)x1*f.b1;

      }

      if (f.b==2)

      {

            //x=f(y);

            f.b1=(double)(x2-x1)/(y2-y1);

            f.b2=(double)x1-(double)y1*f.b1;     }

      return f;

}

 

В начале обработки удаляются точки, чьё смещение было минимальным – поскольку надо «ловить» смещение движущегося объекта. После вычисления формулы линии мы оставляем только вертикальные (или почти вертикальные) линии, т.к. будем отслеживать взмах вверх-вниз.

Посчитав общее количество линий, количество линий направленных вниз и вверх, переходим к этапу определения взмаха. Здесь используется переменная motion_1, манипулируя установкой значения которой, можно добиться оптимального по времени взмаха руки.

Если взмах состоялся, то эмулируется нажатие кнопки вправо с помощью функции keybd_event(). Пример слежения за точками представлен на рисунке 12.1.

Рис. 12.1 Наблюдение за движением руки
Рис. 12.1 Наблюдение за движением руки

Литература:

1. Bradsky G., Kaehler A. Learning OpenCV – O’Reilly, 2008. – 555 p.

2. http://cgm.computergraphics.ru/content/view/54

20 Январь 2010

S2. УПРАВЛЕНИЕ ПРОЦЕССОМ РАСПОЗНАВАНИЯ ОБРАЗОВ НА ОСНОВЕ ОЦЕНКИ ЕГО СЛОЖНОСТИ

написано в рубрике: Распознавание образов — Кручинин Александр @ 3:36 ДП

Кручинин, А.Ю. Управление процессом распознавания образов на основе оценки его сложности : Сборник статей X международной научно-технической конференции «Информационно-вычислительные технологии и их приложения» / А.Ю. Кручинин. – Пенза: РИО ПГСХА, 2009. – С. 143-149.

http://vidikon.com/doc/text1004.doc

Наиболее значимым критерием эффективности системы распознавания образов является достоверность результатов распознавания, значение которой в идеале должно стремиться к 100%. Однако на практике обычно существуют ограничения, которые не позволяют увеличивать объём измерительной информации без потери производительности системы распознавания. Поэтому имеет большое значение нахождение оптимума в процессе распознавания, который с одной стороны обеспечивает требуемый уровень достоверности, а с другой – высокую производительность.

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

В работе [2] показано, что для нахождения оптимального режима функционирования системы управления процессом распознавания в реальном времени необходима не только идентификация неизвестных образов, но и оценка достоверности и сложности распознавания. Сложность (Sl) определяется как вероятность ошибки распознавания образов (рис. 1) [3], т.е. Sl равно ε.

Сложность распознавания определяется качеством признаков (см. рис. 1) и их количеством. Если исходить из того, что признаки независимы, то при достаточно большом количестве испытаний сложность распознавания от нескольких признаков будет определяться выражением:

rec4.1,                                          (1)

где xj – признаки распознавания; n – общее количество признаков.

Рис. 1. Графики распределений плотностей вероятности значений признаков распознавания: ε – области ошибочного распознавания

Рис. 1. Графики распределений плотностей вероятности значений признаков распознавания: ε – области ошибочного распознавания

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

rec4.3,                                                     (2)

где N – объем выборки, характеризующий репрезентативность.

Чтобы определить данную зависимость для вероятностных методов распознавания образов, например для метода Байеса [1], проводился вычислительный эксперимент.

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

rec4.4,             (3)

где x – признак, по которому определяется пересечение распределений; σ1, σ2 – оценки средних квадратичных отклонений распределений образов A и B; a1, a2 – оценки математических ожиданий.

Для построения таблицы зависимостей (2) были выделены 10 значений сложности из возможного интервала от 0 до 1. Каждое значение сложности нуждалось в определении своей функции достоверности от репрезентативности данных. Известно, что статистическая достоверность определяется по выражению:

rec4.5,                                                      (4)

где N1 – количество правильно распознанных образов, N2 – общее количество контрольных образов. Поэтому для каждого значения репрезентативности проводилось не менее 100000 испытаний.

Каждое испытание проводилось в следующие этапы: 1) выбирались два образа с заданной сложностью, т.е. определялись σ1, σ2 и a1, a2; 2) с использованием генератора случайных чисел нормального распределения для образа A получалось N значений, которые характеризуют репрезентативность; 3) для каждого значения определялась вероятность отнесения к образу A или B (рис. 2); 4) вычислялась единичная достоверность результата того, что неизвестный образ является образом A, по следующим соображениям:

rec4.6   ,                                       (5)

rec4.7,                                                   (6)

где i – номер значения; PA(xi), PB(xi) – вероятность отнесения  неизвестного образа к A и B по значению xi; P(A), P(B) – общие значения вероятностей образов A и B; De – единичная достоверность.

 

Рис. 2. Определение вероятности отнесения неизвестного образа к A или B по значению xi

Рис. 2. Определение вероятности отнесения неизвестного образа к A или B по значению xi

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

 Табл.1. Зависимости достоверности результатов от сложности распознавания и репрезентативности данных

Sl
N

0,000

0,100

0,200

0,300

0,400

0,500

0,600

0,700

0,800

0,900

1,000

1

1,000 0,950 0,901 0,850 0,799 0,748 0,698 0,648 0,598 0,549 0,500

2

1,000 0,990 0,966 0,930 0,884 0,832 0,773 0,708 0,642 0,571 0,500

3

1,000 0,998 0,986 0,964 0,927 0,879 0,819 0,749 0,672 0,588 0,500

4

1,000 0,999 0,995 0,981 0,953 0,911 0,853 0,779 0,694 0,600 0,500

5

1,000 1,000 0,998 0,990 0,971 0,935 0,881 0,806 0,715 0,611 0,500

6

1,000 1,000 0,999 0,995 0,980 0,950 0,901 0,827 0,733 0,621 0,500

7

1,000 1,000 1,000 0,997 0,987 0,963 0,917 0,846 0,748 0,630 0,500

8

1,000 1,000 1,000 0,998 0,991 0,972 0,931 0,862 0,763 0,639 0,500

9

1,000 1,000 1,000 0,999 0,995 0,979 0,943 0,876 0,776 0,646 0,500

10

1,000 1,000 1,000 0,999 0,996 0,984 0,952 0,888 0,788 0,653 0,500

11

1,000 1,000 1,000 1,000 0,997 0,988 0,960 0,899 0,799 0,660 0,500

12

1,000 1,000 1,000 1,000 0,998 0,990 0,966 0,908 0,810 0,667 0,500

13

1,000 1,000 1,000 1,000 0,999 0,992 0,971 0,917 0,819 0,673 0,500

14

1,000 1,000 1,000 1,000 0,999 0,994 0,976 0,925 0,828 0,679 0,500

15

1,000 1,000 1,000 1,000 0,999 0,995 0,980 0,932 0,836 0,685 0,500

16

1,000 1,000 1,000 1,000 1,000 0,996 0,983 0,938 0,844 0,691 0,500

17

1,000 1,000 1,000 1,000 1,000 0,997 0,986 0,944 0,851 0,696 0,500

18

1,000 1,000 1,000 1,000 1,000 0,998 0,988 0,949 0,859 0,701 0,500

19

1,000 1,000 1,000 1,000 1,000 0,998 0,989 0,954 0,866 0,706 0,500

20

1,000 1,000 1,000 1,000 1,000 0,999 0,990 0,958 0,872 0,711 0,500

 На основе данных зависимостей можно выбирать такие режимы работы оборудования и аппаратуры системы управления процессом распознавания, при которых значение достоверности будет выше заданного уровня, а производительность является максимальной. Для заданного значения достоверности равного 0,9 на рисунке 4 показано, какое количество информации необходимо при различных значениях сложности.

 

Рис. 3. Зависимости достоверности результатов от сложности распознавания и репрезентативности данных; Рис. 4. Требуемое количество информации для обеспечения заданного значения достоверности 0,9 при различной сложности
Рис. 3. Зависимости достоверности результатов от сложности распознавания и репрезентативности данных; Рис. 4. Требуемое количество информации для обеспечения заданного значения достоверности 0,9 при различной сложности

Любую задачу распознавания можно решить, перейдя от нескольких образов, к двум. Однако, данную методику выбора режима распознавания можно применять и для случаев с несколькими эталонными образами (Рис. 5).

Зависимости D от Sl и N определяются методом распознавания. Так, если в описанном выше способе учитывать вероятности не каждого испытания, а математическое ожидание значений всех испытаний, то зависимости будут выглядеть по-другому (Рис. 6).

Рис. 5-6. Кривые достоверности распознавания от репрезентативности при заданном значении сложности: (5) концептуальные (k – общее число эталонных образов) и экспериментальные зависимости достоверности D от объёма выборки N для двух образов (6)
Рис. 5-6. Кривые достоверности распознавания от репрезентативности при заданном значении сложности: (5) концептуальные (k – общее число эталонных образов) и экспериментальные зависимости достоверности D от объёма выборки N для двух образов (6)

При большом значении N единичная достоверность приближается к статистической:

rec4.11.                                                   (7)

Однако при малых значениях N значение De может сильно отличаться от D. Для подтверждения этого и определения области нахождения De для уровня значимости 0,1 был проведен вычислительный эксперимент, который базировался на предыдущем. Единичная достоверность, определявшаяся на 4 этапе, сохранялась в массив данных, а после проведения всех 100000 испытаний отбрасывалось 10% минимальных и максимальных значений. В результате была построена таблица интервальных значений (табл. 2), в которой представлены области изменения единичной достоверности для различных значений сложности распознавания и репрезентативности данных. 

Анализируя таблицу и полученные графики, были сделаны следующие выводы:

– верхняя граница интервала единичной достоверности при N=1 уменьшается, а нижняя граница интервала при значении сложности от 0,0 до 0,5 уменьшается, от 0,5 до 1,0 увеличивается;

– интервал при увеличении N уменьшается совместно со стремлением статистической достоверности к единице;

– при Sl>0,5 интервал при увеличении N первоначально увеличивается, а потом уменьшается, увеличение интервала происходит за счёт процедуры перемножения вероятностей.

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

Sl
N

0,000

0,100

0,200

0,300

0,400

0,500

0,600

0,700

0,800

0,900

1,000

1

[1,000; 1,000]

[0,524; 1,000]

[0,298; 0,999]

[0,231; 0,996]

[0,214; 0,984]

[0,213; 0,963]

[0,236; 0,906]

[0,275; 0,826]

[0,331; 0,723]

[0,406; 0,607]

[0,500; 0,500]

2

[1,000; 1,000]

[0,963; 1,000]

[0,662; 1,000]

[0,385; 1,000]

[0,261; 0,999]

[0,215; 0,993]

[0,210; 0,972]

[0,234; 0,916]

[0,286; 0,808]

[0,374; 0,656]

[0,500; 0,500]

3

[1,000; 1,000]

[0,999; 1,000]

[0,933; 1,000]

[0,646; 1,000]

[0,378; 1,000]

[0,247; 0,999]

[0,208; 0,990]

[0,213; 0,956]

[0,257; 0,861]

[0,350; 0,692]

[0,500; 0,500]

4

[1,000; 1,000]

[1,000; 1,000]

[0,991; 1,000]

[0,860; 1,000]

[0,540; 1,000]

[0,307; 1,000]

[0,221; 0,997]

[0,205; 0,977]

[0,239; 0,900]

[0,331; 0,723]

[0,500; 0,500]

5

[1,000; 1,000]

[1,000; 1,000]

[0,999; 1,000]

[0,962; 1,000]

[0,729; 1,000]

[0,403; 1,000]

[0,251; 0,999]

[0,204; 0,987]

[0,229; 0,924]

[0,318; 0,746]

[0,500; 0,500]

6

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[0,990; 1,000]

[0,851; 1,000]

[0,500; 1,000]

[0,280; 0,999]

[0,208; 0,993]

[0,217; 0,943]

[0,304; 0,769]

[0,500; 0,500]

7

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[0,998; 1,000]

[0,936; 1,000]

[0,627; 1,000]

[0,332; 1,000]

[0,220; 0,996]

[0,214; 0,957]

[0,296; 0,787]

[0,500; 0,500]

8

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[0,999; 1,000]

[0,967; 1,000]

[0,724; 1,000]

[0,376; 1,000]

[0,226; 0,997]

[0,209; 0,967]

[0,284; 0,805]

[0,500; 0,500]

9

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[0,988; 1,000]

[0,826; 1,000]

[0,449; 1,000]

[0,246; 0,998]

[0,207; 0,975]

[0,279; 0,822]

[0,500; 0,500]

10

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[0,996; 1,000]

[0,890; 1,000]

[0,513; 1,000]

[0,262; 0,999]

[0,206; 0,980]

[0,271; 0,834]

[0,500; 0,500]

11

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[0,999; 1,000]

[0,936; 1,000]

[0,589; 1,000]

[0,285; 0,999]

[0,205; 0,985]

[0,266; 0,847]

[0,500; 0,500]

12

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[0,999; 1,000]

[0,961; 1,000]

[0,646; 1,000]

[0,300; 1,000]

[0,204; 0,988]

[0,258; 0,860]

[0,500; 0,500]

13

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[0,979; 1,000]

[0,720; 1,000]

[0,331; 1,000]

[0,209; 0,991]

[0,254; 0,870]

[0,500; 0,500]

14

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[0,989; 1,000]

[0,784; 1,000]

[0,364; 1,000]

[0,211; 0,993]

[0,251; 0,879]

[0,500; 0,500]

15

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[0,993; 1,000]

[0,821; 1,000]

[0,380; 1,000]

[0,213; 0,994]

[0,243; 0,889]

[0,500; 0,500]

16

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[0,997; 1,000]

[0,878; 1,000]

[0,432; 1,000]

[0,220; 0,995]

[0,240; 0,896]

[0,500; 0,500]

17

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[0,998; 1,000]

[0,903; 1,000]

[0,452; 1,000]

[0,224; 0,996]

[0,237; 0,903]

[0,500; 0,500]

18

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[0,999; 1,000]

[0,931; 1,000]

[0,494; 1,000]

[0,228; 0,997]

[0,235; 0,912]

[0,500; 0,500]

19

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[0,949; 1,000]

[0,526; 1,000]

[0,231; 0,998]

[0,231; 0,916]

[0,500; 0,500]

20

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[1,000; 1,000]

[0,965; 1,000]

[0,572; 1,000]

[0,239; 0,998]

[0,230; 0,922]

[0,500; 0,500]

 

На рис. 7-8 представлены графики интервала единичной достоверности для значения сложности 0,5 и 0,8.

для уровня значимости 0,1 для сложности 0,5 (7) и 0,8 (8)”]Рис. 7-8. Интервал единичной достоверности [Demin, Demax] для уровня значимости 0,1 для сложности 0,5 (7) и 0,8 (8)

Рис. 7-8. Интервал единичной достоверности [Demin, Demax

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

 

Литература:

1. Горелик, А.Л. Методы распознавания / А.Л. Горелик, В.А. Скрипкин. М. : Высш. шк, 2004. 261 с.

2. Кручинин, А.Ю. Модель динамической оптимизации режимов мониторинга и диагностирования буровой скважины / А.Ю. Кручинин, Т.З. Аралбаев // Известия ОрелГТУ, серия «Информационные технологии». 2006. № 1 (2). С. 81-85.

3. Фукунага, К. Введение в статистическую теорию распознавания образов / К. Фукунага. М. : Наука, 1979. 368 с.

19 Январь 2010

S1. АЛГОРИТМ РАСПОЗНАВАНИЯ ДВУМЕРНЫХ ГРАФИЧЕСКИХ КОДОВ С ПРОИЗВОЛЬНЫМ УГЛОМ ПОВОРОТА И НАКЛОНА КАМЕРЫ

написано в рубрике: Распознавание 2D штрих-кодов, Распознавание образов — Кручинин Александр @ 12:13 ДП

Кручинин, А.Ю. Алгоритм распознавания двумерных графических кодов с произвольным углом поворота и наклона камеры : материалы седьмой всероссийской научно-практической конференции (с международным участием) «Современные информационные технологии в науке, образовании и практике» / А.Ю. Кручинин. – Оренбург: ИПК ГОУ ОГУ, 2008. – С. 193-196.

http://vidikon.com/doc/text1003.doc

Линейные штриховые коды и двумерные бар коды в настоящее время используются повсеместно. Двумерные коды внедрены во многих областях – медицине, фармацевтики, обработки документов, торговле, почте, сборочном производстве и др. На рынке программного обеспечения распознаванию бар кодов выделена собственная ниша, в которой успешно работает ряд отечественных и зарубежных компаний, таких как: ООО «НПЦ «Интелком» (http://www.intelcom.ru), Inlite Research Inc. (http://www.inliteresearch.com), IDAutomation.com Inc. (http://www.idautomation.com), Semacode Corporation (http://semacode.com), KAYWA AG (http://www.kaywa.com) и множество других. Целая гамма программных продуктов с ценами, варьирующимися в диапазоне от сотен до тысяч долларов, позволяет сделать вывод, что качественный и недорогой программный продукт может составить конкуренцию в области распознавания бар кодов на мобильных телефонах, карманных компьютерах, персональных компьютерах и средствах для разработчиков программного обеспечения.

Одним из самых популярных и широко распространенных двумерных матричных кодов является код DataMatrix, содержащий чёрно-белые элементы или элементы двух различных степеней яркости в форме квадрата, размещённые в прямоугольной или квадратной группе [1,2]. DataMatrix поддерживает различные режимы кодирования. Технология 2D DataMatrix кодов позволяет кодировать до 1556 байт, 2335 символов латинского алфавита и 3116 цифровых единиц. Пример данного кода, зашифровывающий фразу «test code» в режиме кодировки «TEXT», представлен на рисунке 1. В настоящей статье приведен разработанный автором алгоритм для распознавания двумерных графических кодов DataMatrix, на базе которого был создан программный продукт DataMatrix Recognizer для операционных систем Windows 9x, 2000, XP, 2003, Vista (http://vidikon.com).

Рис. 1 – Пример DataMatrix кода фразы «test code»
Рис. 1 – Пример DataMatrix кода фразы «test code»

Алгоритм получения двумерной матрицы состоит из пяти этапов. На первом этапе производится обработка изображение, в которую включается: а) получение монохромного изображения; б) выделение границ тёмных блоков точек. Изображения до обработки и после представлены на рисунке 2. При получении монохромного изображения устанавливается пороговое значение яркости, которое разделяет цвет на чёрный или белый. Пороговое значение задается вручную или автоматически по общей яркости картинки. Выделяются граничные точки по признаку наличия в качестве соседней одной или нескольких фоновых точек  [4].

Рис. 2 – а) изображение, полученное камерой; б) обработанное изображение
Рис. 2 – а) изображение, полученное камерой; б) обработанное изображение

После получения обработанного изображения с выделенными границами, происходит переход ко второму этапу. В цикле перебираются все точки изображения и выявляются отдельные чёрные блоки, очерченные одной граничной линией (рис. 3).

Рис. 3 – Выделение отдельного чёрного блока
Рис. 3 – Выделение отдельного чёрного блока

Третий этап заключается в том, что определяются четыре крайние точки матрицы. Первоначально для каждого блока находятся четыре наиболее удаленные друг от друга точки, и определяется – образуют ли три точки угол из двух линий (к примеру, на рис. 4а показан угол 1-2-3). Если такой угол найден, то проверяется наличие пунктирной линии по краям (1-4-3). При этом сама точка №4 изначально неизвестна и находится при поиске пунктирных линий путём определение их пересечений. Для того чтобы найти пунктирную линию, определяются диапазоны, где она может быть (рис. 4б). Диапазоны отражают возможные наклоны камеры при проведении съёмки. Используя метод дихотомии [3] перебираются возможные углы в данных диапазонах постепенно приближаясь к искомой пунктирной линии. Зная две линии, находится точка №4.

Рис. 4 – а) 1,2,3,x – наиболее удаленные друг от друга точки выделенного блока; 1,2,3,4 – угловые точки DataMatrix; б) диапазоны нахождения пунктирных линий
Рис. 4 – а) 1,2,3,x – наиболее удаленные друг от друга точки выделенного блока; 1,2,3,4 – угловые точки DataMatrix; б) диапазоны нахождения пунктирных линий

На четвертом этапе определяются линии сетки (рис. 5). А на пятом этапе производится построение искомой матрицы по заполнению каждой ячейки сетки (рис. 6). После построения матрицы находится закодированный текст по известным алгоритмам.

Рис. 5 – Полученная сетка матрицы для различных положений кода
Рис. 5 – Полученная сетка матрицы для различных положений кода

 

Рис. 6 – Полученный код матрицы
Рис. 6 – Полученный код матрицы

 По проведенному тестированию разработанного алгоритма (языки C++, Java), а также с учетом того, что механизм коррекции ошибок основанный на кодировании Рида-Соломона обеспечивает правильность распознавания с наличием от 28% до  62% ошибок матрицы [1,2], достоверность распознавания составила 100% на выборке более 100 тестовых изображений с произвольным поворотом кода на плоскости и наклоном камеры до 45 градусов. Время распознавания изображения с характеристиками 640 на 480 пикселей при 24-битном разрешении составляло десятые доли секунды даже на таких старых персональных компьютерах, как Pentium II 433МГц. В дальнейшем возможно применение данного алгоритма на мобильных телефонах, так как при тестировании время распознавания аналогичного изображения на телефоне Nokia 3110 Classic (J2ME MIDP 2.0) составляет около секунды. Разработанный программный продукт по сравнению с другими имеет более надежное распознавание на малых размерах кодов (до 48 на 48 ячеек матрицы), которые в основном и применяются.

Литература:

1.       ANSI/AIM BC11 ISS – Data Matrix.

2.       ISO/IEC 16022:2000 Information technology – International symbology specification – Data Matrix.

3.       Аттетков, А.В. Методы оптимизации / А.В. Аттетков, С.В. Галкин, В.С. Зарубин. – М. : Изд-во МГТУ им. Н.Э. Баумана, 2003. – 440 с.

4.       Введение в контурный анализ; приложения к обработке изображений и сигналов/ Я.А.Фурман, А.В.Кревецкий, А.К.Передреев, А.А.Роженцов, Р.Г.Хафизов, И.Л.Егошина, А.Н.Леухин; Под ред. Я.А.Фурмана. – 2-е изд., испр. – М.:ФИЗМАТЛИТ, 2003. – 592 с. 

 

18 Январь 2010

R2. Трансформация изображений: Перевод изображения в монохромное

написано в рубрике: OpenCV, Распознавание образов — Кручинин Александр @ 7:29 ДП

Часто при анализе изображения его переводят в монохромное для упрощения работы. Собственно говоря, сделать это достаточно просто (Листинг 2.1).

 

int i,j;

double yyy;

 

if (Width*3%4==0) Width_1= Width*3;

  else Width_1= Width*3+4-Width*3%4;

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

  for(j=0;j<Width;j++)

  {  

      yyy=(double)(0.222* bytes[j*3+i*Width_1]+

                   0.707*bytes[j*3+i*Width_1+1]+

                   0.071*bytes[j*3+i*Width_1+2]);

      if (yyy>border_brightness){

            bytes[j*3+i*Width_1]=255;

            bytes[j*3+i*Width_1+1]=255;

            bytes[j*3+i*Width_1+2]=255;

      }

      else

      {

            bytes[j*3+i*Width_1]=0;

            bytes[j*3+i*Width_1+1]=0;

            bytes[j*3+i*Width_1+2]=0;

      }                

}

Листинг 2.1. Перевод 24-битного изображения в монохромное

 

Имеется массив данных bytes, в котором хранится 24-битное изображение в несжатом формате. Известны его размеры Width и Height. Сигнал яркости Y формируется из RGB сигнала по следующей формуле:

rec2.0.                                         (2.1)

Задав изначально пороговый уровень border_brightness изображение переводится в монохромное путём сравнения больше-меньше этого уровня. По такому принципу работает функция cvThreshold из OpenCV.

При таком подходе нужно делать предположение об известной яркости входного изображения или определять пороговый уровень дополнительным анализом всех точек изображения. Так, например, при распознавании штрих-кодов можно построить гистограмму распределения значений яркости [9, 10], по которой определить необходимый пороговый уровень. Пример гистограммы приведён на рисунке 2.1.

Рис. 2.1. Гистограмма распределения значений яркостей
Рис. 2.1. Гистограмма распределения значений яркостей

Технология гистограмм применяется во многих алгоритмах распознавания изображений. Поддержка её встроена в библиотеку OpenCV. Такой подход называется бинарным.

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

Задаются блоки на изображении с одинаковыми шириной и высотой, значения которых являются нечётными, т.к. они являются окрестностями центрального пикселя. Суть метода такова: для каждого пикселя определяются окрестности, в которых вычисляется среднее значение яркости, которое и является пороговым значением T(x,y) для текущего пикселя. Для 24-битного изображения преобразования в монохромное может осуществляться по следующей формуле:

rec2.2,         (2.2)

где src(x,y) – RGB-значения пикселя с координатами x и y на исходном изображении, dst(x,y) – соответственно конечного изображения.

Пример отличия работы этих двух подходов на рисунке 2.2. И тот и другой подходы имеет смысл применять в различных ситуациях с учётом необходимых требований.

Рис. 2.2. Два подхода к преобразованию в монохромное изображение: бинарный и адаптивный

Рис. 2.2. Два подхода к преобразованию в монохромное изображение: бинарный и адаптивный

Литература:

9. Roger C. Palmer, The bar code book. Helmers Publishing, Inc. Formerly North American Technology, Inc., 1995.

10. Краснобаев А.А. Алгоритмы распознавания штриховых кодов, Препринт

Института прикладной математики им. М.В. Келдыша РАН, 2004, №84, 29 с.

11. Bradsky G., Kaehler A. Learning OpenCV – O’Reilly, 2008.

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

Работает на WordPress