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

ВНИМАНИЕ! БЛОГ ПЕРЕЕХАЛ ПО АДРЕСУ
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.

Нет комментариев

Еще нет комментариев.

RSS лента комментариев к этой записи.

Извините, комментирование на данный момент закрыто.

Работает на WordPress