Технологии распознавания 2D бар-кодов

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


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

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


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

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


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

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


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

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


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

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


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

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


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

     Декодирование осуществляется с использованием методики Рида-Соломона.
     Работа выполнена при поддержке РФФИ, грант 10-07-00039.

     Вы можете скачать тестовые выборки бар-кодов
163 изображения Aztec (20711 KB)
51 изображение Small Aztec (21305 KB)
146 изображений PDF-417 (18306 KB)
111 изображений DataMatrix (54017 KB)
38 изображений DataMatrix (22602 KB)
21 изображение DataMatrix (16576 KB)

Сообщить об ошибке в тексте


(C)2004-2012. Кручинин Александр
support@vidikon.com