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

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

29 Октябрь 2010

Оптимизация систем распознавания образов реального времени

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

Вышла статья в журнале “Автоматизация в промышленности” http://www.avtprom.ru:

Кручинин, А.Ю. Оптимизация систем распознавания образов реального времени / А.Ю. Кручинин / Автоматизация в промышленности. – 2010. – №10. – С. 6-9.

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

Kruchinin A.Yu. Optimization of real-time pattern recognition systems

An approach to the optimization of pattern recognition process in real time is offered which allows to make a trade-off between the risks of recognition error losses and the recognition rate.
Keywords: process control, pattern recognition, recognition complexity, adequacy, data representativeness, optimization, optimality criterion, real time.

18 Октябрь 2010

Распознавание 2D бар-кодов с видеокамеры на мобильном устройстве на примере Aztec Code

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

Кручинин, А.Ю Распознавание 2D бар-кодов с видеокамеры на мобильном устройстве на примере Aztec Code [Электронный ресурс]: Материалы Международной научной конференции, посвященной 55-летию Оренбургского государственного университета, 14—15 окт. 2010 г., Оренбург/ Оренбург. гос. ун-та. — Оренбург: ГОУ ОГУ, 2010.

Kruchinin, A.YU. Recognition 2D bar-codes using the camera device in mobile phones on example Aztec Code [Electronic resource]: Material to International scientific conference, denoted 55 Orenburg state university, October 14-15 2010, Orenburg/ OSU. – Orenburg: GOU OGU, 2010.

http://vidikon.com/doc/text1009.pdf

Внедрение двухмерных штриховых кодов в практику, таких как DataMatrix, PDF417, Aztec Code, OR Code, на настоящий момент происходит по всему миру, включая и Россию. Не смотря на существующие достаточное количество разработок в области распознавания двухмерных штрих кодов (например, корпорации Google http://code.google.com/p/zxing/), в том числе и российских (например, ООО «НПЦ» Интелком» http://intelcom.ru), рынок программных средств недостаточно насыщен данной продукцией. Существующие разработки в большинстве случаев позволяют распознавать коды только при точном наведении камеры. Поэтому разработка алгоритмов для распознавания двухмерных штрих кодов, которые не чувствительны к наклону камеры и углу поворота, достаточно быстры для использования на мобильных системах, имеет большое значение для науки и практики. В данной статье описан подход к распознаванию 2D бар-кодов на примере Aztec Code. Работа выполнена при поддержке РФФИ, грант 10-07-00039-а.

Отечественных публикаций по распознаванию двухмерных бар-кодов практически нет, кроме [2]. В тоже время в зарубежных источниках эта тематика рассматривается уже достаточно давно, например, в [3, 4, 5]. В работе [4] предложен подход к распознаванию QR Code с произвольным углом наклона и поворота камеры. Используя алгоритмы, описанные в [2, 5], и подход к распознаванию QR Code был разработан алгоритм распознавания Aztec Code.

Основной особенностью Aztec кода является присутствие в нём центральной мишени, что позволяет наносить код в те места, где края могут быть заполнены какими-то цветами, в отличие, к примеру, от DataMatrix кода, в котором обязательно должна быть зона, огораживающая код от остальной части изображения. Технология Aztec Code позволяет кодировать до 3832 цифровых символов, 3067 символов алфавита или 1914 байт. Пример Aztec Code представлен на рисунке 1.

Рис.1. Пример Aztec кодирования
Рис.1. Пример Aztec кодирования

Предварительным действием перед распознаванием бар-кода является его детектирование на изображении. Многие разработчики используют технологию градиентов яркости для локализации кодов на изображении, например [3]. Однако, это не всегда необходимо. Например, если пользователь нажал кнопку мобильного устройства с целью сделать кадр изображения с камеры, то он предполагает, что в этом кадре обязательно есть бар-код, причём он занимает значительную часть изображения. Поэтому локализация бар-кода является отдельной и не всегда необходимой операцией, которая не будет рассмотрена в данной работе.

Алгоритм распознавания Aztec Code состоит из нескольких этапов. На первом этапе производится обработка изображения, в которую включается: а) получение монохромного изображения; б) выделение границ тёмных блоков точек. Монохромное изображение может получаться путём задания уровня пороговой яркости или с помощью адаптивной методики, технологии которой реализованы в библиотеках ImagePak (http://imagepak.vidikon.com), OpenCV.

На втором этапе определяется центр мишени. В работе [4] показан достаточно простой способ определения мишеней QR Code, предложенного его разработчиками. А именно, анализ изображения по параллельным линиям – горизонтальным, вертикальным и под углом 45 градусов. При нахождении нужного чередования чёрно-белых пикселей – считается, что мишени найдены. При анализе Aztec Code, из-за большой вложенности мишени, можно пойти путём контурного анализа – выделения наиболее вложенного контура. От примерного центра мишени алгоритм передвигается к краям, и определяются четыре внутренние линии и точки (Рис. 2а), вычисляя размеры диагоналей, определяются внешние точки и линии (Рис. 2а).

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

 

Рис. 2. Внутренние (1) и внешние (2) линии и точки мишени (а); ориентировочные элементы мишени (б)
Рис. 2. Внутренние (1) и внешние (2) линии и точки мишени (а); ориентировочные элементы мишени (б)

Затем читаются и декодируются 40 бит информации, находящейся между ориентировочными элементами [5, 6], которые содержат информацию о количестве слоёв (5 бит), кодовых слов (11 бит) и корректировочные слова Рида-Соломона (24 бита) с полем Галуа GF(16), где коэффициент генерации полинома равен 19.

В работе [4] после нахождения мишеней QR Code предлагается произвести обратное перспективное преобразование формы кода. Т.е., если правильное расположение кода должно быть такое, как показано на рисунке 1, а для распознавания поступил код, показанный на рисунке 2, тогда, используя приведённые в [4] формулы, необходимо преобразовать распознаваемый код в правильное положение (Рис. 3).

Рис. 3. Обратное перспективное преобразование
Рис. 3. Обратное перспективное преобразование

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

На четвёртом этапе выделяются центральные направляющие пунктирные линии (на рисунке 4а обозначены «1»). Согласно этим направляющим и наклону линий со второго этапа код делится на слои (на рисунке 4а обозначены «2»).

Рис. 4. Ориентировочные центральные пунктирные линии (1); разделение кода (2) на слои (а); конечная сетка кода (б)
Рис. 4. Ориентировочные центральные пунктирные линии (1); разделение кода (2) на слои (а); конечная сетка кода (б)

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

На шестом этапе полученные значения ячеек, преобразуются в массив 6, 8, 10, 12 битных кодовых слов (в зависимости от размеров кода) и декодируются с использованием методики Рида-Соломона [1]. Поля Галуа GF(64), GF(256), GF(1024), GF(4096) – соответственно.

При количестве слоёв кода большем 4 добавляются дополнительные направляющие пунктирные линии (Рис. 5).

Рис. 5. Расположение синхронизирующих линий в Aztec Code
Рис. 5. Расположение синхронизирующих линий в Aztec Code

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

После того, как для всех значений возможных углов найдена дисперсия, находится её минимальной значение, которое и будет соответствовать линии в наибольшей степени соответствующей пунктиру (Рис. 6). На графике минимум достигается на шаге 21, который и соответствует направлению пунктирной линии.

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

Рис. 6. Зависимость дисперсии от угла при определении пунктирной линии
Рис. 6. Зависимость дисперсии от угла при определении пунктирной линии

Разработанный алгоритм обладает достоинством относительно существующих в распознавании кодов, повёрнутых на плоскости под любым углом и с наклоном снимающей камеры до 45 градусов. По результатам тестирования достоверность распознавания алгоритма близка к 100% при отсутствии шумов и размером ячейки больше чем 2 на 2 пикселя. Быстродействие алгоритма позволяет использовать его на мобильных телефонах и КПК.

 

Литература:

1. Блейхут Р. Теория и практика кодов, контролирующих ошибки: пер. с англ. – М.: Мир, 1986. – 576 с.

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

3. «A two-dimensional bar code reader» Normand, N.; Viard-Gaudin, C.; Pattern Recognition, 1994. Vol. 3 – Conference C: Signal Processing, Proceedings of the 12th IAPR International Conference on October 9-13, 1994 Page(s):201 – 203 vol.3 Digital Object Identifier 0.1109/ICPR.1994.577158.

4. «Barcode readers using the camera device in mobile phones» Ohbuchi, E.   Hanaizumi, H. Hock, L.A.  ,Cyberworlds, 2004 International Conference on, page 260 – 265.

5. ISO/IEC 24778:2008(E) Information technology – Automatic identification and data capture techniques – Aztec Code bar code symbology specification. – 2008.

6. United States Patent 5591956. Longacre Jr., Andrew (Skaneateles, NY), Hussey, Rob (Liverpool, NY) Two dimensional data encoding structure and symbology for use with optical readers. Patent dated Jan. 7, 1997. Dedication filed March 20, 1997. 

Работает на WordPress