A universal algorithm for discretizing bichromatic two-dimensional graphic codes

Full Text

1. ВВЕДЕНИЕ

По мере компьютеризации и цифровизации систем управления обществом возникла необходимость в новой форме представления информации – в форме компактных графических кодов.

Наибольшей информационной емкостью и устойчивыми перспективами применения обладают двумерные коды – DataMatrix и QR-коды.

Эти коды стали повсеместными и используются для внутреннего учета – на складах, в цехах и компаниях. Благодаря кодам возможно оптимизировать формирование заказов, контроль остатков и запасов и отслеживание всей цепочки поставок или производства. На производстве маркировка кодами позволяет повысить конкурентоспособность продукции за счет постоянного контроля качества продукции и организации обратной связи с клиентами. Система маркировки позволяет успешно бороться с контрафактной продукцией.

DataMatrix считаются кодами промышленного применения. Ключевой областью применения DataMatrix в России является маркировка товарных групп, подлежащих обязательному отслеживанию через систему “Честный ЗНАК”. Сегодня к таким группам относятся лекарство, табачные изделия, молочные продукты, парфюм, фототехника, одежда, обувь и текстиль, автомобильные шины. Данный список постоянно расширяется за счет добавления новых групп.

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

Стандартные DataMatrix и QR-коды, считающиеся весьма удобными в использовании, на самом деле представлены несколькими версиями, обеспечивающими запись либо большей, либо сокращенной по объему информации с целью оптимизации расходов на запись/считывание данных в каждом конкретном случае.

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

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

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

Целью настоящих исследований является разработка универсального алгоритма, превращающего в последовательность 0–1 записанные в реальных условиях двумерные коды, версии которых имеют квадратную форму.

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

Прежде чем перейти к изложению основного материала подчеркнем, что в литературе представлено множество методов и алгоритмов обработки (дискретизации и подготовки к декодированию) двумерных кодов, зарегистрированных в реальных условиях съемки. Подавляющее большинство описанных алгоритмов укладываются в одну схему: 1 – определение вида кода, 2 – дискретизация на модули, 3 – бинаризация модулей и декодирование. В нашей работе продвигается альтернативная схема, создающая предпосылки к разработке универсального алгоритма: 1 – превращение любого двумерного кода в канонический квадрат, 2 – высоконадежная дискретизация его на модули, 3 – бинаризация модулей, 4 – установление типа и версии кода по битовой последовательности с последующим декодированием.

Логика всего цикла распознавания требует, чтобы на начальной стадии объект был обнаружен и изолирован от фона. В таком случае, полный цикл обработки двумерного кода будет состоять из последовательности следующих процедур: обнаружение кода, его локализация, дискретизация на модули и декодирование. Первые две процедуры – обнаружение и локализация кодов – подробно исследованы в авторских работах [1, 2], поэтому нет большого смысла на них здесь останавливаться, можно лишь отметить, что предложенная в [1] функция осцилляций яркости служит надежному обнаружению кодов на изображении, а преобразование Хафа оказалось эффективным инструментом решения задачи локализации четырехугольных кодов.

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

2. ДИСКРЕТИЗАЦИЯ КОДА

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

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

В работе [3] предложен алгоритм считывания информации кодов Data Matrix, в котором после локализации кода, в общем случае повернутого на произвольный угол по отношению к горизонтальному направлению, по сканированию шаблона синхронизации (Timing Pattern), расположенного на границе кода, определяется количество строк и столбцов кода и их ширина. Пересечения этих строк и столбцов образуют темные и светлые квадратные ячейки (модули) кода, в общем случае повернутые относительно канонического горизонтального направления. Темные и светлые модули затем трансформируются в бинарную матрицу. Недостаток данного способа дискретизации кода на модули состоит в необходимости строго фронтальной съемки кода, сложность и невысокая точность алгоритма при установлении наклонных границ переходов светлых и темных модулей шаблона синхронизации (Timing Pattern), чувствительность его к шуму, а также применимость лишь для Data Matrix.

В запатентованном способе [4] определение размеров ячеек (модулей) двумерного кода производится на основе анализа распределения длин белых и черных последовательностей пикселей при сканировании изображения кода вверх, вниз, влево и вправо, начиная от некоторой точки внутри области двумерного кода. Минимальная длина последовательности, встречающаяся с частотой не ниже предопределенного уровня, выбирается в качестве ширины и высоты квадратной ячейки (модуля), по которой восстанавливается вся сетка модулей локализованного кода. Недостаток данного способа заключается в сложности и низкой надежности алгоритма определения размеров ячейки (модуля) кода, вследствие необходимости оценки уровня частоты в распределении длин черных и белых последовательностей, ниже которого результаты не должны приниматься в расчет; ввиду обязательного исключения черных и белых последовательностей существенно малой длины, частота появления которых будет всегда высока при наличии шума, а также при расфокусировке и смазывании изображения. Следует отметить, что в данном способе предполагается канонический квадратный вид двумерных графических кодов как объектов обработки, который в общем случае невозможно обеспечить в реальных условиях съемки.

В работе [5] предлагается алгоритм, в котором ячейки двумерного кода извлекаются за четыре шага. На первом шаге из анализа распределения градиента интенсивности изображения локализованного, произвольно повернутого кода строится гистограмма ориентации ребер, и выбираются две доминирующие ориентации, расположенные примерно на величину 90° друг от друга, и поэтому соответствующие границам резких переходов интенсивности между строками (одна группа ребер) и столбцами (перпендикулярная им группа ребер) двумерного кода. На втором шаге для пикселов, образующих обнаруженные ребра, выполняется преобразование Хафа. Нахождение максимумов преобразования Хафа позволяет математически описать прямые, соответствующие границам строк и столбцов двумерного кода, на третьем шаге алгоритма. На четвертом шаге определяются координаты центрального пикселя каждой ячейки (модуля) кода как координаты минимума по осям х и у между двумя последовательными максимумами по осям х и у соответственно. Недостатком способа является математическая сложность четырех-шагового алгоритма, лежащего в основе способа, и, как следствие, низкая надежность получения результатов в общем случае. Главное ограничение алгоритма заключается в искажении направлений ребер при больших углах съемки и, как следствие, невозможность определения границ строк и столбцов по преобразованию Хафа.

Авторами статьи [6] представляется способ распознавания QR-кода, в котором на основе горизонтального и вертикального сканирования бинаризованного изображения обнаруженного и изолированного QR-кода определяются три опознавательные метки (шаблоны Finder Patterns). После определения ориентации QR-кода по анализу взаимного расположения опознавательных меток, находится ширина ячейки (модуля) простым делением ширины одного из трех шаблонов на 7 (7 × 7 – число модулей в опознавательной метке) и уточняется версия кода. Затем по формулам преобразования перспективы [7] код приводится к каноническому квадратному виду и производится дискретизация его на квадратные ячейки (модули) в соответствии с найденным значением их ширины. Недостатками предложенного способа являются его узкая специализация для расшифровки только QR-кодов, допустимые лишь небольшие отклонения съемки по углу от фронтальной, низкая точность определения ширины ячейки, и как следствие малая надежность результатов дискретизации кода на модули.

В предлагаемом авторами данной статьи алгоритме, претендующем на роль универсального для двумерных кодов произвольного вида, выделяются две процедуры – трансформация кода в канонический квадрат и дискретизация кода на модули по анализу максимумов средних производных от интенсивности по декартовым осям.

2.1. Трансформация кода в канонический квадрат

При решении задачи трансформации локализованного четырехугольника (1ʹ2ʹ3ʹ4ʹ) в квадрат (1234) (см. рис. 1) должны быть определены функции преобразования f и g, в общем записываемые как

$\begin{array}{c}{x}^{\text{'}}=f\left(x,y,x^{\text{'}},y^{\text{'}}\right),\\ y^{\text{'}}=g\left(x,y,x^{\text{'}},y^{\text{'}}\right).\end{array}$ (1)

 

Рис. 1. Преобразование четырехугольника (1ʹ2ʹ3ʹʹ) в квадрат (1234): (а) схема обратного преобразования, (б) схема вычисления интенсивности пикселей.

 

В рамках настоящих исследований были протестированы два способа трансформации (1): 1) с использованием простых формул, предложенных (без всякого, кстати, обоснования) в работе [8], 2) с использованием известных формул преобразования перспективы [7].

Заметим, что иллюстрирующий графический материал (рис. 1) подходит для описания обоих способов. Пусть функции f и g (1) допускают свое определение по известным координатам вершин четырехугольника и квадрата. С целью минимизации яркостных искажений и исключения пустых пикселей на изображениях трансформация одной фигуры в другую производится в форме обратного преобразования, т. е. квадрата (1234) в четырехугольник (1ʹ2ʹ3ʹ4ʹ) (рисунок 1а). В таком случае, после определения конкретного вида функций f и g (1) при построении изображения квадрата целочисленные координаты его пикселей пробегают весь выбранный диапазон по х и у (рисунок 1б), а полученные по формулам преобразований (1) (нецелочисленные) координаты xʹ и yʹ позволяют вычислить интенсивность в точке (xʹ, yʹ) по формулам двумерной интерполяции, например, билинейной, с использованием значений интенсивности ближайших четырех пикселей (i, j), (i + 1, j), (i, j + 1) и (i + 1, j + 1) исходного изображения. Вычисленная таким образом интенсивность точки (xʹ, yʹ) транслируется в интенсивность пиксела (x, y) на изображении квадрата (см. рисунок 1б).

Способ 1.

Формулы преобразования (1), предложенные в [8], имеют вид

$\begin{array}{c}{x}^{\text{'}}=c_{1}x+c_{2}y+c_{3}xy+c_4,\\ y^{\text{'}}=c_{5}x+c_{6}y+c_{7}xy+c_8,\end{array}$ (2)

где c₁ – c₆ – неизвестные коэффициенты, которые необходимо найти для определения функций преобразования f и g (1).

Формулы преобразования (2) каждой из четырех вершин записываются как

${x^{\text{'}}}_k=c_1{x}_k+c_2{y}_k+c_3{x}_k{y}_k+c_4,$

${y^{\text{'}}}_k=c_5{x}_k+c_6{y}_k+c_7{x}_k{y}_k+c_8,$

где k = 1, 2, 3, 4.

Поскольку полное число уравнений для четырех преобразуемых вершин равно восьми, то получаем замкнутую систему уравнений относительно восьми неизвестных коэффициентов c_i, i = 1, 2 … 8. В этом способе трансформации решение системы удается получить в виде последовательности достаточно простых выражений

$c_1=\frac{c_{15}^{+}+c_{15}^{-}}{2}, c_5=\frac{c_{15}^{+}-c_{15}^{-}}{2},$

$c_2=\frac{c_{26}^{+}+c_{26}^{-}}{2}, c_6=\frac{c_{26}^{+}-c_{26}^{-}}{2},$

$c_3=\frac{c_{37}^{+}+c_{37}^{-}}{2}, c_7=\frac{c_{37}^{+}-c_{37}^{-}}{2},$

$c_4=\frac{c_{48}^{+}+c_{48}^{-}}{2}, c_8=\frac{c_{48}^{+}-c_{48}^{-}}{2},$

$c_{15}^{\pm }=\frac{b_1^{\pm }{a}_{11}-b_2^{\pm }{a}_{01}}{a_{00}{a}_{11}-a_{10}{a}_{01}}, c_{26}^{\pm }=\frac{b_1^{\pm }-a_{10}{c}_{15}^{\pm }}{a_{01}},$

$c_{37}^{\pm }=\frac{s_1^{\pm }-s_2^{\pm }-\left(x_1-2\right)c_{15}^{\pm }-\left(y_1-y_2\right)c_{26}^{\pm }}{g_{01}},$

$c_{48}^{\pm }=s_1^{\pm }-c_{15}^{\pm }{x}_1-c_{26}^{\pm }{y}_1-c_{37}^{\pm }{x}_1{y}_1,$

$b_k^{\pm }=\left(s_k^{\pm }-s_{k+1}^{\pm }\right)g_{k+\mathrm{1,}k+2}-\left(s_{k+1}^{\pm }-s_{k+2}^{\pm }\right)g_{k,k+1},$

$k=\mathrm{1,2,}$

$a_{00}=\left(x_1-x_2\right)g_{23}-\left(x_2-x_3\right)g_{12},$

$a_{01}=\left(y_1-y_2\right)g_{23}-\left(y_2-y_3\right)g_{12},$

$a_{10}=\left(x_2-x_3\right)g_{34}-\left(x_3-x_4\right)g_{23},$

$a_{11}=\left(y_2-y_3\right)g_{34}-\left(y_3-y_4\right)g_{23},$

$g_{i, i+1}=x_i{y}_i-x_{i+1}{y}_{i+1}, i=\mathrm{1,2,} \mathrm{3,}$

$s_k^{\pm }={x^{\text{'}}}_k\pm {y^{\text{'}}}_k,$

$k= \mathrm{1,} \mathrm{2,} \mathrm{3,} 4.$

Восстановление тестовых квадратных изображений (в статье не приводятся) по формулам преобразования (2), полученных при съемке под разными углами, показало практическое отсутствие искажений в диапазоне углов съемки от 0° до 10° по отношению к нормали. Еще большее увеличение угла съемки приводит к недопустимым искажениям. Т.е. предложенное в [8] преобразование (2) годится только для случаев строго фронтальной съемки.

На рис. 2 представлен пример трансформации локализованного QR-кода (рис. 2а), расположенного на верхней грани куба, угол съемки которого составляет около 45°, в канонический квадрат (рис. 2б). Обращает на себя внимание искажение размеров и вертикально-горизонтальных пропорций всех трех меток обнаружения. Отношение линейных размеров самой большой метки (левый нижний угол) к размерам самой маленькой (правый верхний угол) составляет примерно 7:5 и является количественной характеристикой уровня искажений при трансформации (2).

 

Рис. 2. Трансформация QR-кода (а), предварительно локализованного четырехугольником (1234) на верхней грани куба по формулам: (б) – (2), (в) – (3).

 

Способ 2.

Строго обоснованные математические формулы преобразования перспективы [7] имеют вид

$\begin{array}{c}{x}^{\text{'}}=a_{11}x+a_{21}y+a_{31}-a_{13}x{x}^{\text{'}}-a_{23}y{x}^{\text{'}},\\ y^{\text{'}}=a_{12}x+a_{22}y+a_{32}-a_{13}x{y}^{\text{'}}-a_{23}y{y}^{\text{'}}.\end{array}$ (3)

Записывая эту пару уравнений для четырех соответствующих вершин произвольного четырехугольника и квадрата, получим систему восьми линейных алгебраических уравнений относительно неизвестных коэффициентов a₁₁, a₂₁, a₃₁, a₁₂, a₂₂, a₃₂, a₁₃ и a₃₁, которую удобно представить в матрично-векторной форме:

$\left[\begin{array}{cccccccc}{x}_1& y_1& 1& 0& 0& 0& -x_1{x^{\text{'}}}_1& -y_1{x^{\text{'}}}_1\\ x_2& y_2& 1& 0& 0& 0& -x_2{x^{\text{'}}}_2& -y_2{x^{\text{'}}}_2\\ x_3& y_3& 1& 0& 0& 0& -x_3{x^{\text{'}}}_3& -y_3{x^{\text{'}}}_3\\ x_4& y_4& 1& 0& 0& 0& -x_4{x^{\text{'}}}_4& -y_4{x^{\text{'}}}_4\\ 0& 0& 0& x_1& y_1& 1& -x_1{y^{\text{'}}}_1& -y_1{y^{\text{'}}}_1\\ 0& 0& 0& x_2& y_2& 1& -x_2{y^{\text{'}}}_2& -y_2{y^{\text{'}}}_2\\ 0& 0& 0& x_3& y_3& 1& -x_3{y^{\text{'}}}_3& -y_3{y^{\text{'}}}_3\\ 0& 0& 0& x_4& y_4& 1& -x_4{y^{\text{'}}}_4& -y_4{y^{\text{'}}}_4\end{array}\right]\left[\begin{array}{c}{a}_{11}\\ a_{21}\\ a_{31}\\ a_{12}\\ a_{22}\\ a_{32}\\ a_{13}\\ a_{23}\end{array}\right]=\left[\begin{array}{c}{x^{\text{'}}}_1\\ {x^{\text{'}}}_2\\ {x^{\text{'}}}_3\\ {x^{\text{'}}}_4\\ {y^{\text{'}}}_1\\ {y^{\text{'}}}_2\\ {y^{\text{'}}}_3\\ {y^{\text{'}}}_4\end{array}\right].$

Решение данной системы уравнений методом Гаусса с частичным выбором главного элемента и последующее восстановление по формулам преобразования перспективы (3) тестовых квадратных изображений (в статье не приводятся), продемонстрировало практическое отсутствие яркостных и геометрических искажений в диапазоне углов съемки вплоть до 60°.

На рис. 2в представлен пример трансформации локализованного QR-кода, расположенного на верхней грани куба (рис. 2а). Сравнение качества способов трансформаций (2) и (3) делается в пользу второго, поскольку оно сохраняет исходное соотношение линейных размеров структурных элементов кода.

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

2.2. Построение сетки

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

На рис. 3 представлен пример трансформации локализованного четырехугольного кода (рис. 3а) в канонический квадрат (рис. 3б) с последующей дискретизацией его на структурные единицы.

 

Рис. 3. Трансформация и дискретизация DataMatrix: (а) – исходный для обработки локализованный код, (б) – результат трансформации четырехугольника (1234) в канонический квадрат, (в) – средний модуль производной по y интенсивности квадратного кода и кусочно-линейный фон (background), (г) – средний модуль производной после вычитания кусочно-линейного фона, (д) – наложение сетки с n × n = 24 × 24 ячейками, (е) – код с бинарными модулями.

 

На рис. 3в показан средний модуль частной производной по y; средний модуль частной производной по x имеет похожий вид и поэтому не демонстрируется. Практика применения алгоритма позволила повысить надежность процедуры поиска максимумов функции вида рис. 3в за счет предварительного вычитания ее кусочно-линейного фона, проходящего через минимумы. После вычитания фона удается однозначно определить положительный уровень функции, выше которого располагаются все искомые максимумы (обозначенные маленькими кружками) (рис. 3г). В соответствии с координатами максимумов на плоскости рисунка квадратного кода располагаются горизонтальные и вертикальные линии сетки (номера максимумов совпадают с номерами линий), т. е. производится его дискретизация на n × n модулей (рис. 3д).

Стоит заметить, что частные производные $I_y\left(x,y\right)=\frac{\partial I}{\partial y}$ от интенсивности I(x, y) каждого столбца с номером x цифрового изображения размером L × L могут быть найдены во всех L пикселах столбца по формулам численного дифференцирования [9]:

$I_y\left(x,y\right)=I\left(x,y-2\right)-8I\left(x,y-1\right)+8I\left(x,y+1\right)-$

$-I\left(x,y+2\right), y=\mathrm{3,4}\dots L-\mathrm{2,}$

причем для производных в крайних пикселях слева y = 1, y = 2 и справа y = L – 1, y = L можно использовать формулы с эксклюзивными весовыми коэффициентами [9] или приравнять их значениям производных в узлах x = 3 и x = L – 2 соответственно.

Среднее значение модуля производной определяется с помощью выражения

$p\left(y\right)=\overline{\left|I_y\left(x,y=\text{const}\right)\right|}=\frac{1}{L}\sum _{x=1}^L\left|I_y\left(x,y\right)\right|,$

$y=\mathrm{1,2}\dots L.$

Способ нахождения средних частных производных по x аналогичен выше описанному.

3. БИНАРИЗАЦИЯ МОДУЛЕЙ

Следующий этап обработки двумерного кода заключается в бинаризации его n × n модулей. Во многих случаях здесь могут использованы стандартные методы пороговой бинаризации изображений [10], причем в нашем случае за интенсивность пиксела изображения размером n × n принимается среднее значение интенсивности ${\overline{I}}_{ij}$ ячейки сетки (модуля). Еще лучшие результаты показывают методы локальной бинаризации [11]. Вполне возможна в перспективе разработка эффективных методов бинаризации модулей кода при использовании дополнительной информации о распределении интенсивности внутри каждого из них, а не только о ее средней величине.

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

$d_{ij}=\left\{\begin{array}{c}\mathrm{0,} {\overline{I}}_{ij}\ge I_t,\\ \mathrm{1,} {\overline{I}}_{ij}<I_t,\end{array}\right.$

где i, j = 1, 2, ... n; n – размер кода; I_t – пороговое значение интенсивности. С целью визуального контроля качества распознавания исходного кода данная матрица закрашивается белыми (d_ij = 0) и черными (d_ij = 1) небольшими квадратами (рис. 3е). Однако еще раз подчеркнем важный момент – на выходе предложенных алгоритмов дискретизации графических кодов получаем двумерную битовую последовательность 0 и 1.

Рис. 4 демонстрирует универсальность предложенных алгоритмов. Тестирование описанной методики на множестве различных кодов показала ее эффективность при восстановлении исходной битовой последовательности 0 и 1 без предопределения типа кода.

 

Рис. 4. Обработка двумерных кодов: (а) – Aztec, (б) – GridMatrix. Верхний ряд 1 – исходные изображения, средний ряд 2 – результат обнаружения, локализации, трансформации в канонический квадрат и дискретизации на модули двумерного кода, нижний ряд 3 – результат бинаризации модулей кода (двумерная последовательность 0 и 1).

 

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

Например, DataMatrix сопровождается L-образной опознавательной меткой, поэтому сумма элементов первой или последней строки, а также первого или последнего столбца будет равна размеру кода n, т. е.

или $\sum _{i=1}^n{d}_{i1}=n$ или $\sum _{i=1}^n{d}_{in}=n,$

или $\sum _{j=1}^n{d}_{1j}=n,$ или $\sum _{j=1}^n{d}_{nj}=n.$

причем элементы противоположной строки и столбца в этом случае есть чередующиеся 0 и 1 (метки синхронизации). Более того, тестирование алгоритмов показало, что строгие равенства в этих условиях могут быть заменены на $\ge \left(n-k\right)$, где k – небольшое число, а также могут допускаться нарушения строгого чередования 0 и 1. В таком случае при определенных потерях информации (при обработке некачественных изображений) тип кода все равно определяется однозначно.

QR-код отличается тем, что в трех его углах располагаются черно-белые квадратные опознавательные метки размером 7 × 7, первая и седьмая строки которой, а также первый и седьмой столбцы есть последовательность семи битовых 1. Имеются другие очевидные особенности этих меток, которые могут быть использованы при идентификации. Практика тестирования предложенных алгоритмов также показала допустимость небольших отклонений содержания меток обрабатываемого QR-кода от установленного идеального образца.

Вывод, который может быть здесь сделан, заключается в том, что предлагаемый метод распознавания допускает не строгое соответствие между метками стандартного образца двумерного кода и объекта обработки. Такой вывод оказывается вполне логичным, но в некоторой степени неожиданным.

Версия кода определяется аналогичным образом по специфическим меткам.

После определения типа двумерного кода сменой строк и столбцов битовой матрицы d_ij может быть обеспечена его стандартная каноническая ориентация.

После определения типа и версии кода, смены его ориентации на каноническую можно запускать процедуру его дешифрования, которая не является сложной и регламентирована стандартами.

Для отладки предложенных алгоритмов и целей практического распознавания двумерных графических кодов разработано (C + + Qt) программное приложение Quantron CodeReader pro. В приложение включены дополнительные опции адаптивной медианной фильтрации [12], фильтрации гауссовских шумов и морфологической обработки изображений. В качестве финальной демонстрации достоинств предложенных алгоритмов на рис. 5 представляются результаты полного цикла распознавания изображения кода DataMatrix плохого качества, которое не удается дешифровать сканером смартфона Redmi Note 12.

 

Рис. 5. Результаты полного цикла распознавания DataMatrix низкого качества: (а) – исходное изображение кода на жестяной банке, (б) – код после обнаружения и локализации, трансформации и дискретизации, (в) – бинаризованный канонически ориентированный код.

 

На рис. 5a показано исходное изображение кода, на рис. 5б – код после обнаружения и локализации на основе оригинальных авторских методов [1], трансформации в канонический квадрат, дискретизации на модули, и на рис. 5в – код после бинаризации модулей и переориентации. В предпоследней колонке модулей на рис. 5в обнаруживается модуль серого цвета как индикатор того, что используемый в программе алгоритм бинаризации не смог однозначно идентифицировать 0 или 1 в соответствующей ячейке сетки (второй ряд сверху) на рис. 5б. Однако такой сбой не может оказать влияние на окончательный результат дешифрования, поскольку двумерные коды содержат в себе дополнительную информацию – коды Рида-Соломона коррекции ошибок, позволяющие восстанавливать до 30% потерянных данных. Результатом распознавания двумерной двоичной последовательности на рис. 5в является строка символов 0104603725770003215ABIEM: Y7DR? Y{GS}93QoBp.

4. ТЕСТИРОВАНИЕ МЕТОДА

Вследствие отсутствия специальных тестовых примеров для оценки эффективности методов распознавания двумерных кодов в нашем эксперименте использовались изображения Data Matrix и QR-кодов из открытого доступа в интернете, размер которых варьировался от 0.3 Мп до 5 Мп, а минимальный размер модуля превышал 4 пикселя. Распознавание кода принималось успешным, если однозначно определялся его тип и отсутствовали визуально контролируемые значительные искажения структуры.

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

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

Расфокусировка и размазывание изображения кода снижает максимумы производных и поэтому затрудняет определение положений линий сетки дискретизации. Падение качества двумерного кода при расфокусировке продемонстрировано на рис. 6. Среднеквадратическое отклонение σ интенсивности каждой строки (столбца) идеального черно-белого Data Matrix или QR-кода заключено в пределах от 0.4 до 0.5 в формате записи яркости пикселей байтовыми числами от 0 до 1 (рис. 6а). При расфокусировке изображения σ уменьшается (рис. 6б). Исследования показали, что граница надежного построения сетки модулей находится выше значения среднеквадратического отклонения, приблизительно равного 0.2–0.3.

 

Рис. 6. Эффект расфокусировки QR-кода: (а) – идеальный код и профиль интенсивности выделенной строки (σ = 0.49), (б) – расфокусированный код и профиль интенсивности выделенной строки (σ = 0.20).

 

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

4. ЗАКЛЮЧЕНИЕ

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

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

About the authors

A. A. Trubitsyn

Ryazan State Radio Engineering University named after V.F. Utkina; Kvantron Group LLC

Author for correspondence.
Email: assur@bk.ru
Russian Federation, 59/1 st. Gagarina, Ryazan, 390005; 28a st. Engelsa, room. H2, Ryazan, 390010

M. V. Shadrin

Kvantron Group LLC

Email: m.shadrin@kvantron.com
Russian Federation, 28a st. Engelsa, room. H2, Ryazan, 390010

S. I. Holkin

LLC “Operator-CRPT”

Email: assur@bk.ru
Russian Federation, 15 Rochdelskaya st., building 16A, premises I, Moscow, 123376

References

Supplementary files