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

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

21 Ноябрь 2010

Распознавание двухмерных штрих кодов с произвольным углом наклона и поворота камеры

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

На настоящий момент существует большое количество двухмерных штриховых кодов (бар-кодов), наиболее популярными среди которых являются Aztec Code, DataMatrix, PDF-417 и QR Code. У каждого из этих кодов есть свои достоинства и недостатки, что позволяет использовать их в различных условиях. Современные алгоритмы и системы распознавания бар-кодов во многих случаях обрабатывают изображения, находящиеся параллельно плоскости камеры или же расположенные только под одним углом. Сама процедура распознавания в таких случаях значительно упрощается, как и время на получение конечного результата. Однако, поддержка распознавания кодов, не чувствительных к наклону камеры и углу поворота, имеет большое значение для расширения функциональности сканеров кодов, но алгоритмы распознавания должны быть достаточно быстры для использования на мобильных системах.

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

Общий алгоритм распознавания двухмерного кода.

  1. Предварительная обработка изображения.
  2. Детектирование ориентировочных элементов (границ и краевых точек кода).
  3. Восстановление матрицы кода.
  4. Декодирование данных.

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

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

Таблица 1. Функции библиотеки ImagePak для предварительной обработки изображений

Название

Описание

Img_Erode

Операция эрозии в окне 3 на 3

Img_Dilate

Операция наращения в окне 3 на 3

Adaptive2ThresholdImage

Функция адаптивной монохромной трансформации

AllocationBordersRect

Функция выделения границ

CONTOUR:: Find

Функция находит контуры в области изображения, включая их вложенность

SegmentationH

Функция реализует алгоритм сегментации на основе гистограмм яркости с выделением бинарных блоков

Детектирование ориентировочных элементов (границ и краевых точек кода). Данный этап значительно отличается для различных кодов. В коде Aztec главные элементы детектирования находятся не по краям, а внутри кода. Учитывая особенности кода, можно находить контур с наибольшим уровнем вложенности (CONTOUR:: ReturnMaxLevel), и из его центра двигаться в стороны по горизонтали и вертикали. Считая количество перепадов яркости, можно добраться до внутренних границ внешнего четырёхугольника мишени (Рис. 1). При повороте кода на плоскости будет изменяться только ширина участков одного цвета. Полученные четыре точки X1, X2, X3, X4 должны принадлежать одному контуру (CONTOUR:: ReturnPointInContour). Если одному контуру принадлежит меньше трёх точек, значит найденный ранее центр не соответствует центру Aztec кода.

Рис. 1. Поиск внутренних точек внешнего четырёхугольника мишени кода Aztec

Рис. 1. Поиск внутренних точек внешнего четырёхугольника мишени кода Aztec

Поскольку известно, что найденный контур должен состоять из четырёх линий и возможно помех, то определяются направляющие линии (Рис. 2) и угловые точки A, B, C, D (CONTOUR:: Return4DistantPoints и CONTOUR:: Accuracy4RombPoints). Для полученного четырёхугольника строятся диагонали, а на их продолжениях определяются дальние точки ориентировочных элементов мишени Aztec Code A1, B1, C1, D1 (Рис. 2). После проверки ориентировочных элементов, найденные точки характеризуют положение кода в пространстве. Затем читаются и декодируются 40 бит информации, находящейся между ориентировочными элементами.

Рис. 2. Направляющие линии и ориентировочные элементы в коде Aztec

Рис. 2. Направляющие линии и ориентировочные элементы в коде Aztec

В отличие от кода Aztec, DataMatrix не обладает явно выраженными ориентировочными элементами. Поэтому необходимо детектировать прямой угол и три угловых точки, а затем находить четвёртую точку [2]. Обычно при анализе кода DataMatrix контур, которому принадлежит прямой угол, является наибольшим среди остальных контуров принадлежащих коду (Рис. 3а). Определив 4 наиболее удалённые друг от друга точки A-B1-C-D (CONTOUR:: Return4DistantPoints), проверяется, образуют ли три точки угол из двух линий (CONTOUR:: AccuracyLine), к примеру, на рисунке 3б показан угол A-D-C. Если такой угол найден, то проверяется наличие пунктирной линии по краям (AccuracyLine2), т.е. пунктирный угол A-B-C. При этом сама точка B изначально неизвестна и находится при поиске пунктирных линий путём определение их пересечений. Для того чтобы найти пунктирную линию, с помощью простых геометрических операций определяются диапазоны, где она может находиться (рис. 3б). После чего по аналогии с подходом для определения пунктирных линий в коде Aztec, определяются граничные пунктирные линии и их точка пересечения.

Рис. 3. Выделен наибольший контур и его содержимое (а); 4 наиболее удалённый точки контура A-B1-C-D, 4 точки DataMatrix кода A-B-C-D, диапазоны линий (б)

Рис. 3. Выделен наибольший контур и его содержимое (а); 4 наиболее удалённый точки контура A-B1-C-D, 4 точки DataMatrix кода A-B-C-D, диапазоны линий (б)

В отличие от кодов Aztec и DataMatrix, код PDF-417 обладает элементами для детектирования, «унаследованными» от одномерных штриховых кодов. Эта особенность позволяет легко и надёжно детектировать местоположение кода на изображении после предварительной обработки. Для детектирования кода при его любом направлении достаточно определить с определённым интервалом между друг другом горизонтальные и вертикальные линии, по которым будут анализироваться перепады яркости (Рис. 4а). Интервал не должен быть больше размера кода.

Рис. 4. Виртуальные линии для детектирования кода PDF-417, выделены начало и конец кода (а), выделенные 4 точки (б)

Рис. 4. Виртуальные линии для детектирования кода PDF-417, выделены начало и конец кода (а), выделенные 4 точки (б)

Анализируя перепады яркости в обе стороны, необходимо определить пропорции яркости начала и конца кода – соответственно (8,1,1,1,1,1,1,3) и (7,1,1,3,1,1,1,2,1). После детектирования местоположения кода находятся 4 точки, определяющие информационную зону кода. Это делается путём продления перпендикулярных основному направлению линий (Рис. 4б).

Восстановление матрицы кода. Aztec код имеет дополнительные синхронизирующие линии, которые необходимо находить перед этапом восстановления матрицы кода или совместно с этим этапом. Центральные направляющие линии позволяют уточнять ширину каждого слоя (на рисунке 5а обозначены «1»). Для их определения обычно достаточно знать угловые точки A, B, C, D. Согласно направляющим линиям четырёхугольника и центральным направляющим код делится на слои (на рисунке 5а обозначены «2»).

При получении слоёв необходимо помнить об эффекте увеличения угла наклона линий относительно центральных направляющих при увеличении расстояния. Направления внутренних линий первого слоя определяются из точек A1, B1, C1, D1, а внешние – через точку на синхронизирующей центральной линии и рассчитанному наклону. После чего можно приступать к восстановлению матрицы кода (Рис. 5б), используя функции GRID:: CreateGrid, GRID:: RecogCells и GRID:: ReturnGrid1.

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

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

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

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

Рис. 6. Расположение синхронизирующих линий в Aztec Code (а); зависимость дисперсии от угла при определении пунктирной линии (б)

Рис. 6. Расположение синхронизирующих линий в Aztec Code (а); зависимость дисперсии от угла при определении пунктирной линии (б)

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

При восстановлении матрицы DataMatrix нужно построить на полученных линиях сетку, и определить значения ячеек. Однако, поскольку размеры кода могут быть большими, то из-за наклона камеры возможно изменение размера ячеек. Поэтому по размерам ячеек граничных пунктирных линий определяется зависимость их изменений с использованием метода наименьших квадратов (функция Approximation). После этого строится сетка с различными значениями размеров ячеек (Рис. 7).

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

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

При распознавании кодов с большим количеством ячеек, когда добавляются дополнительные синхронизирующие линии, необходимо дополнительно выделять тёмные линии между блоками (Рис. 8а). Для этого при определении граничной пунктирной линии выделяются места, где должны находиться синхронизирующие линии. Задаются возможные диапазоны углов, в которых может находиться линия. После чего для каждого возможного местоположения линии вычисляется количество захватываемых тёмных точек. Для сглаживания полученного графика можно использовать вычисление показателя тёмных линий по следующему подходу: Y(i) = x(i-1)+x(i)+x(i+1), где i – шаг угла, x – количество тёмных пикселей для шага. Данный подход реализован в функции AccuracyLineBlack. На рисунке 8б показан пример вычисления описанного показателя для приведённого примера. Максимальное значение соответствует направлению синхронизирующей линии.

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

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

Поскольку код PDF-417 был разработан с идеологией одномерных штриховых кодов, то в нём нет матрицы данных в том виде, как в рассмотренных выше кодах. Тёмные и белые элементы здесь не одинакового размера, что несколько затрудняет распознавание. Поэтому при восстановлении данных кода необходимо руководствоваться другими принципами.

Информационный символ в коде PDF-417 представляет собой комбинацию из 8 перепадов яркости, начиная с тёмного и заканчивая светлым, например, (3, 1, 1, 1, 1, 1, 3, 6) в относительных размерах. Символы разделены по столбцам, которые на рисунке 4б разделены двумя вертикальными линиями, и по строкам. Для того, чтобы максимально исключить ошибки существуют 3 таблицы символов из 929 элементов, которые чередуются между собой, т.е. первая строка – 1 таблица, вторая строка – 2 таблица, третья строка – 3 таблица, четвёртая строка – снова 1 таблица и т.д.

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

Рис. 9. Восстановление информации из кода PDF-417

Рис. 9. Восстановление информации из кода PDF-417

Декодирование данных. Декодирование осуществляется с использованием методики Рида-Соломона [4], например, реализованного в библиотеке Фила Карна (http://www.ka9q.net).

Реализация алгоритмов распознавания двухмерных кодов с помощью библиотеки ImagePak позволяет обрабатывать за доли секунды изображения размером 1600 на 1200 пикселей на персональном компьютере с частотой процессора 2ГГц. Однако при использовании описанного подхода на мобильных устройствах необходимо оптимизировать работу функций, например, объединяя некоторые из них.

Литература:

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

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

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

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

(C) Российский фонд фундаментальных исследований, 2010.

15 Ноябрь 2010

Тестовые изображения для распознавания Aztec Code, Small Aztec Code, PDF-417, DataMatrix

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

http://vidikon.com/download/test_aztec.zip – 163 изображения Aztec (20 711 KB)
http://vidikon.com/download/test_saztec.zip – 51 изображение Small Aztec (21 305 KB)

http://vidikon.com/download/pdf417.zip – 146 изображений PDF-417 (18 306 KB)

http://vidikon.com/download/dmtest.zip– 111 изображений DataMatrix (54 017 KB)  небольшие размеры

http://vidikon.com/download/dmtest1.zip– 38 изображения DataMatrix (22 602 KB)  небольшие блочные размеры

http://vidikon.com/download/dmtest2.zip– 21 изображений DataMatrix (16 576 KB)  большие блочные размеры

(C) Российский фонд фундаментальных исследований, 2010.

12 Ноябрь 2010

Aztec code: принципы кодирования

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

Структура

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

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

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

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

Рис. 1.2. Элементы для нахождения, ориентации и синхронизации Aztec кода

Рис. 1.2. Элементы для нахождения, ориентации и синхронизации Aztec кода

Кодируемые данные располагаются по слоям (уровням), которые обвиваются вокруг центральной мишени по так называемому принципу «домино» по часовой стрелке (Рис. 1.3).

Рис. 1.3. Расположение данных, структура кодовых слов и принцип «домино» в Aztec Code

Рис. 1.3. Расположение данных, структура кодовых слов и принцип «домино» в Aztec Code

Информация о режиме кодирования находится между ориентировочными элементами мишени по принципу «домино» и содержит в себе 40 бит. Уровни шириной в два бита и с различной длиной кодовых слов (см. рис. 1.3) располагаются по принципу «домино», исключая синхронизирующие элементы – пунктирные линии сетки, которых при увеличении количества уровней становится больше. Центральные пунктирные линии присутствуют в любом стандартном коде Aztec. Остальные линии добавляются между 4 и 5 слоями, в слоях 12 и 27, разделяя кодовые слова.

В начальном уровне #1 содержится 128 бит информации, а в последующих добавляется по 32 бита, поэтому общее количество бит информации в символе длины L может быть рассчитано по формуле:

r7_4. (1.1)

Коррекция Рида-Соломона [3] осуществляется для кодовых слов различной длины:

- в 1-2 уровневых символах используются 6-битные кодовые слова;

- в 3-8 уровневых символах используются 8-битные кодовые слова;

- в 9-22 уровневых символах используются 10-битные кодовые слова;

- в 23-32 уровневых символах используются 12-битные кодовые слова.

Поэтому количество кодовых слов, о которых говорится в блоке данных, рассчитывается следующим образом:

r7_5, (1.2)

где K – количество бит в кодовом слове, а div – функция целого деления.

Возможные размеры символов Aztec Code представлены в таблице 1.1. В таблице показаны физические размеры символов и их вместимость (количество кодовых слов умноженных на количество бит).

Низкоуровневое кодирование

Информация о режиме кодирования, как отмечалось выше, содержит 40 бит, из которых только 16 бит содержат полезную информацию, остальные 24 бита – выполняют функцию коррекции ошибок Рида-Соломона. Первые 5 бит содержат размер символа, который определяется через количество слоёв минус 1. Т.е. если первые 5 бит – нулевые, то код содержит только 1 уровень. Следующие 11 бит кодируют длину сообщения, которая определяется как количество кодовых слов минус 1, включая символы следующие за кодовыми словами для контроля ошибок.

Таблица 1.1. Размеры и вместимость символов Aztec Code

Уровни

Размер

Вместимость

Уровни

Размер

Вместимость

Уровни

Размер

Вместимость

1

19×19

21×6

12

67×67

364×10

23

113×113

920×12

2

23×23

48×6

13

71×71

416×10

24

117×117

992×12

3

27×27

60×8

14

75×75

470×10

25

121×121

1066×12

4

31×31

88×8

15

79×79

528×10

26

125×125

1144×12

5

37×37

120×8

16

83×83

588×10

27

131×131

1224×12

6

41×41

156×8

17

87×87

652×10

28

135×135

1306×12

7

45×45

196×8

18

91×91

720×10

29

139×139

1392×12

8

49×49

240×8

19

95×95

790×10

30

143×143

1480×12

9

53×53

230×10

20

101×101

894×10

31

147×147

1570×12

10

57×57

272×10

21

105×105

940×10

32

151×151

1664×12

11

61×61

316×10

22

109×109

1020×10

Эти 16 служебных бит расположены в 4-битных словах, а остальные 6 проверочных слов добавляются кодированием Рида-Соломона с полем Галуа GF(16), основанным на главном полиноме модуля x4+x+1 (коэффициент генерации полинома = 19). Порождающий полином (x-21)..(x-26) следующий:

r7_6. (1.3)

Все десять слов следуют друг за другом, начиная с верхнего левого угла.

Информационное сообщение (закодированное в уровнях символа) кодируется по-разному в зависимости от размеров. В таблице 1.2 показаны характеристики распределения Рида-Соломона, необходимые для кодирования-декодирования информации.

Таблица 1.2. Размеры кодовых слов и главные полиномы модуля

Уровни

Размер кодового слова

Поле Галуа

Полином

Коэффициент генерации

1-2

6 бит

GF(64)

x6+x+1

67

3-8

8 бит

GF(256)

x6+x5+x3+x2+1

301

9-22

10 бит

GF(1024)

x10+x3+1

1033

23-32

12 бит

GF(4096)

x12+x6+x5+x3+1

4201

Высокоуровневое кодирование

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

На этапе 1 берутся символы сообщения, которые кодируются с использованием таблицы 1.3. Размеры символов могут быть 4, 5 и 8 бит – соответственно для цифр (Digit), остальных режимов таблицы 1.3 и побайтного кодирования. Сообщение начинает кодироваться в режиме Upper и может быть переключено в другой режим с помощью UL (Upper), LL (Lower), ML (Mixed), PL (Punct), DL (Digit) или переведено в режим только для ввода единственного символа с помощью US (Upper) и PS (Punct). При переключении на режим Digit происходит смена количества бит на символ с 5 на 4.

BS (Binary Shift) – переключение на ввод 8-битной строки символов с заданным размером. После BS следует 5-битное значение: если неравно нуля, то содержит в себе количество последующих байт строки; если 0, то следующие 11 бит содержат в себе количество байт минус 31. После окончания строки, кодирование возвращается в режим, который был до BS.

Таблица 1.3. Высокоуровневое кодирование Aztec Code

Upper

Lower

Mixed

Punct

Digit

Value

Char

ASCII

Char

ASCII

Char

ASCII

Char

ASCII

Char

ASCII

0

PS

PS

PS

FLG(n)

***

PS

1

SP

32

SP

32

SP

32

CR

13

SP

32

2

A

65

a

97

SOH

1

CR LF

13,10

0

48

3

B

66

b

98

STX

2

.SP

46,32

1

49

4

C

67

c

99

ETX

3

,SP

44,32

2

50

5

D

68

d

100

EOT

4

:SP

58,32

3

51

6

E

69

e

101

ENQ

5

!

33

4

52

7

F

70

f

102

AVK

6

34

5

53

8

G

71

g

103

BEL

7

#

35

6

54

9

H

72

h

104

BS

8

$

36

7

55

10

I

73

i

105

HT

9

%

37

8

56

11

J

74

j

106

LF

10

&

38

9

57

12

K

75

k

107

VT

11

39

,

44

13

L

76

l

108

FF

12

(

40

.

46

14

M

77

m

109

CR

13

)

41

UL

15

N

78

n

110

ESC

27

*

42

US

16

O

79

o

111

FS

28

+

43

17

P

80

p

112

GS

29

,

44

18

Q

81

q

113

RS

30

-

45

19

R

82

r

114

uS

31

.

46

20

S

83

s

115

@

64

/

47

21

T

84

t

116

\

92

:

58

22

U

85

u

117

^

94

;

59

23

V

86

v

118

_

95

<

60

24

W

87

w

119

`

96

=

61

25

X

88

x

120

|

124

>

62

26

Y

89

y

121

~

126

?

63

27

Z

90

z

122

DEL

127

[

91

28

LL

US

LL

]

93

29

ML

ML

UL

{

123

30

DL

DL

PL

}

125

31

BS

BS

BS

UL

Символ, обозначенный FLG(n) в таблице 1.3, является специальным флагом, представляющим различные неинформационные символы, предоставляемые многими стандартными символиками. В битовом потоке значение FLG(n) сопровождается 3 дополнительными битами, кодирующими аргумент «n» в бинарном режиме, поэтому значение n может быть от 0 до 7.

FLG(0) представляет «FNC1» – флажок данных происходящий от Code 128. Когда FNC1 используется в первой позиции данных, это сигнализирует об использовании правил EAN/UPC формата данных, использующих Application Identifiers, и установке бита 0 в модификаторе идентификаторе символики. Когда FNC1 используется во второй позиции данных или в третьей позиции следуют 2 цифры, то это сигнализирует об использовании некоторого другого индустриально-специфического формата, идентифицированного предыдущими данными и устанавливающим бит 1 в модификаторе. Когда FNC1 используется в дальнейших локациях, он служит в качестве разделителя области и вставляет ASCII код 29 в это место в выходных данных.

FLG(1)- FLG(6) предназначены для представления расширенного канального переходного символа ECE, который в выходной строке данных представлен как «\nnnnnn», наклонная черта влево, сопровождаемая 6 цифрами. Присутствие ECE где-нибудь в символе принуждает все наклонные черты влево внутри кодируемых данных быть удвоенным в выходной строке и также устанавливает бит 2 в модификаторе идентификаторе символики. Аргумент «n» показывает, сколько из этих 6 цифр явно кодируются, используя режим Digit, в символе, заполненном нулями. ECE #000123, например, кодируется FLG(3), после чего кодирование возвращается в режим предшествующий FLG(n).

FLG(7) пока не используется.

На втором шаге кодировании сообщения результирующий поток бит делится на последовательность из B-битных (B = 6, 8, 10 или 12) кодовых слов. Анализируя последовательность, первые B-1 бит проверяются на наличие одинаковых бит информации. Если все B-1 бит равны 0, тогда добавляется бит пустышки (dummy), который равен 1, сразу после первых B-1 бит кодового слова, после чего следует последний бит и дальнейшие элементы последовательности. Если все B-1 бит равны 1, тогда добавляется бит пустышки (dummy), который равен 0. Это делается для того, чтобы «разбавить» возможные одинаковые биты в коде, чтобы не принесло пользы для чтения кода.

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

Пример кодирования

Возьмём пример кодирования фразы «Test code». На рисунке 1.4. показано, как происходит перевод в биты информации и получения последовательности.

Перевод в биты

ASCII символ

Значение из табл. 1.3

Биты

T

LL

e

s

t

SP

c

o

d

e

21

28

6

20

21

1

4

16

5

6

10101

11100

00110

10100

10101

00001

00100

10000

00101

00110

Последовательность

10101+11100+00110+10100+10101+00001+00100+10000+00101+00110

Рис. 1.4. Перевод в биты информации и получение последовательности

Если используется одноуровневый Aztec Code, то необходимо разбить последовательность по 6 бит. Затем проверить, необходимо ли добавлять dummy. Если нужно, то добавить (Рис. 1.5). После этого добавляются кодовые слова контроля ошибок, и генерируется код (Рис. 1.6). Как видно из рисунка, значительную часть слоя занимают корректирующие кодовые слова Рида-Соломона.

Перевод в блоки кодовых слов

Блоки бит

Кодовое слово

101011

110000

110101

001010

100001

001001

000000

101001

10

43

48

53

10

33

9

0

41

Добавление dummy

Блоки бит

Кодовое слово

101011

110000

110101

001010

100001

001001

000001

010100

110111

43

48

53

10

33

9

1

20

55

Рис. 1.5. Перевод в кодовые слова и добавление dummy

Рис. 1.6. 1-уровневый Aztec Code кодирующий фразу «Test Code»

Рис. 1.6. 1-уровневый Aztec Code кодирующий фразу «Test Code»

(C) Российский фонд фундаментальных исследований, 2010.

9 Ноябрь 2010

Распознавание PDF-417

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

В отличие от кодов Aztec и DataMatrix, код PDF-417 обладает элементами для детектирования, «унаследованными» от одномерных штриховых кодов. Эта особенность позволяет легко и надёжно детектировать местоположение кода на изображении после предварительной обработки. Для детектирования кода при его любом направлении достаточно определить с определённым интервалом между друг другом горизонтальные и вертикальные линии, по которым будут анализироваться перепады яркости (Рис. 1а). Интервал не должен быть больше размера кода.

Рис. 10. Виртуальные линии для детектирования кода PDF-417, выделены начало и конец кода (а), выделенные 4 точки (б)

Рис. 1. Виртуальные линии для детектирования кода PDF-417, выделены начало и конец кода (а), выделенные 4 точки (б)

Анализируя перепады яркости в обе стороны, необходимо определить пропорции яркости начала и конца кода – соответственно (8,1,1,1,1,1,1,3) и (7,1,1,3,1,1,1,2,1). После детектирования местоположения кода находятся 4 точки, определяющие информационную зону кода. Это делается путём продления перпендикулярных основному направлению линий (Рис. 1б).

Поскольку код PDF-417 был разработан с идеологией одномерных штриховых кодов, то в нём нет матрицы данных в том виде, как в рассмотренных выше кодах. Тёмные и белые элементы здесь не одинакового размера, что несколько затрудняет распознавание. Поэтому при восстановлении данных кода необходимо руководствоваться несколько другими принципами.

Информационный символ в коде PDF-417 представляет собой комбинацию из 8 перепадов яркости, начиная с тёмного и заканчивая светлым, например, (3, 1, 1, 1, 1, 1, 3, 6) в относительных размерах. Символы разделены по столбцам, которые на рисунке 10б разделены двумя вертикальными линиями, и по строкам. Для того, чтобы максимально исключить ошибки существуют 3 таблицы символов из 929 элементов, которые чередуются между собой, т.е. первая строка – 1 таблица, вторая строка – 2 таблица, третья строка – 3 таблица, четвёртая строка – снова 1 таблица и т.д.

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

Рис. 2. Восстановление информации из кода PDF-417

Рис. 2. Восстановление информации из кода PDF-417

Восстановленная информация также декодируется с использованием методики Рида-Соломона.

(C) Российский фонд фундаментальных исследований, 2010.

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