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

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

24 Ноябрь 2010

Эффективность управления процессом распознавания образов в реальном времени

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

Кручинин, А.Ю. Эффективность управления процессом распознавания образов в реальном времени : труды IX международной научно-технической конференции «Новые информационные технологии и системы» / А.Ю. Кручинин. – Пенза: Изд-во ПГУ, 2010. – Ч1. – С. 150-155.

Kruchinin, A.YU. Effective management of pattern recognition in real time Proceedings of the IX international scientific-technical conference “New information technologies and systems” / AY Kruchinin. – Penza: Izd PGU, 2010. – T1. – P. 150-155.

http://vidikon.com/doc/text1010.doc

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

r9_1,                                (1)

где tω – интервал времени, потраченный на распознавание образа ωx; t – ограничивающий интервал времени; Dз, D – соответственно заданное и фактическое значение достоверности распознавания; Pз, P – соответственно заданная и фактическая производительность работы СРО реального времени.

В данной работе предлагается подход к расчёту эффективности СРО реального времени путём оценки достоверности и производительности.

Рассмотрим некоторую вычислительную систему, на которой в реальном времени одновременно распознаются 1 или более образов. Пусть условием к работе системы является необходимость распознать эти образы с достоверностью большей либо равной Dз за минимальное время. Различные образы можно распознавать с уровнем Dз за разное время. В работе [1] показано, что в зависимости от сложности распознавания образов можно выбирать различное количество информации для обеспечения уровня Dз в каждом конкретном случае. На рисунке 1 изображены зависимости достоверности результатов от сложности распознавания и репрезентативности данных для двух образов с нормальными распределениями признаков.

Понятие сложности распознавания характеризует меру близости образов и определяется, как вероятность ошибки распознавания [1] при объёме характеризующих объект данных N равном 1.

Как видно из рисунка 1, для Dз = 0,9 образы с различной сложностью можно распознать при разном объёме данных N. Зная сложность распознавания образов можно выбирать такие режимы работы СРО, при которых Dз D и объём данных для распознавания минимален.

Основным вопросом при применении описанного подхода к выбору режима распознавания является определение значения сложности распознавания конкретного образа. В идеале при решении задачи на вход должны поступать не только признаки неизвестного образа, но и его сложность распознавания. На практике это трудно осуществимо, т.к. обычно для того, чтобы оценить значение сложности распознавания образа, необходимо его идентифицировать. Однако можно использовать сложность распознавания предыдущего образа для распознавания текущего образа. Данный подход применим в случае, когда на СРО в потоке через интервал времени поступают порциями неизвестные образы, причём изменение образов в потоке происходит постепенно. Такая ситуация возможна, например, при анализе видеопотока с видеокамеры, геофизических исследованиях скважин [2] и т.п. Негативным эффектом от описанного подхода является то, что, при переходе от анализа образа с малой сложностью распознавания к большей, может возникнуть ситуация, когда система работает в режиме Dз > D. Поэтому необходимо оценить эффективность управления процессом распознавания образов.

Рисунок 1. – Зависимости достоверности результатов D от сложности распознавания Sl и репрезентативности данных.

Рисунок 1. – Зависимости достоверности результатов D от сложности распознавания Sl и репрезентативности данных.

Допустим, что на СРО реального времени поступают неизвестные образы из возможной группы образов:

r9_3, (2)

где K > 1 – количество классов образов, а вероятность их появления не зависит от номера испытания. Тогда последовательность образов, поступающих на СРО, можно описать однородной цепью Маркова [3]. Матрица переходов последовательности на шаге 1 описывается следующим образом:

r9_4,                                                   (3)

где pij – условная вероятность перехода из i-го состояния в j-ое. Номер состояния характеризует режим СРО для анализа образа с тем же номером. Режим характеризуется объёмом данных для распознавания в соответствии с выражением (2) и рисунком 1:

r9_5.                                                    (4)

При установившемся режиме СРО в одном состоянии D ~ Dз, поэтому матрица статистического уровня достоверности при переходе из одного состояния в другое имеет следующий вид:

r9_6.          (5)

Для того, чтобы вычислить безусловную вероятность появления каждого образа достаточно рассчитать матрицу перехода за L шагов (где ), которая вычисляется согласно следующему выражению [3]:

r9_7.                                                            (6)

Результирующая матрица будет содержать одинаковые строки с безусловными вероятностями для каждого состояния p = {p1, p2, …, pK}:

r9_8.                                                   (7)

Согласно теореме умножения вероятностей [3] можно найти вероятность каждого перехода в выражении (3), которая будет равна произведению безусловной вероятности состояния на условную вероятность перехода в то же или другое состояние. Данные вероятности необходимы для определения среднего значения достоверности распознавания образов:

r9_9.        (8)

Производительность работы СРО напрямую связана с объёмом анализируемых данных, поэтому достаточно вычислить средний объём данных на распознавания одного образа для оценки производительности:

r9_10.                                             (9)

Далее приведён пример расчета средней достоверности и репрезентативности данных. Имеются три класса образов с различной сложностью Sl = {0,1; 0,3; 0,5}, для распознавания которых с Dз = 0,9 требуются различные объёмы данных N = {1, 3, 6} соответственно. Матрица переходов и матрицы статистической достоверности следующие:

r9_11,r9_12 .                                  (10)

Используя выражение (6) с L = 15, рассчитываются безусловные вероятности p = {0,353; 0,373; 0,275}. Подставив полученные вероятности в выражение (8) и (9) определяются средние значения достоверности и объёма данных: Dср = 0,88; Nср = 3,617. В то время, как если бы СРО работала в одном режиме (N = 6), то Dср = 0,933; Nср = 6. Не смотря на значительный прирост в производительности (в 1,66 раза), СРО при управлении процессом распознавания работает ниже уровня Dз. Однако эта проблема устраняется если немного завысить Dз при построении матрицы MD или поменять режимы работы, например, установив N = {3, 3, 6}, соответственно:

r9_13.                                                      (11)

В этом случае Dср = 0,91; Nср = 4,323, что в 1,388 раз быстрее работы СРО без управления при сохранении достоверности большей Dз. Сравнительные гистограммы всех трёх режимов представлены на рисунке 2.

Рисунок 2. – Достоверность распознавания и средний объём данных для режимов СРО: без управления (1), управление N = {3, 3, 6} (2), управление N = {1, 3, 6} (3).

Рисунок 2. – Достоверность распознавания и средний объём данных для режимов СРО: без управления (1), управление N = {3, 3, 6} (2), управление N = {1, 3, 6} (3).

Зная показатели достоверности и производительности работы СРО не сложно вычислить режим, удовлетворяющий (1), для этого необходимо знать показатели функций затрат:

r9_15,                                            (12)

где Z0 – затраты независящие от производительности и достоверности распознавания СРО, Z1 – затраты, обусловленные производительностью, Z2 – затраты обусловленные ошибками при распознавании образов.

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

Литература

  1. Кручинин, А.Ю. Управление процессом распознавания образов в реальном времени / А.Ю. Кручинин // Автоматизация и современные технологии. – 2010. – №3. – С. 33-37.
  2. Кручинин А.Ю., Аралбаев Т.З. Оптимизация геофизических исследований скважин на основе многофакторной имитационной модели // Вестник Самарского государственного университете, серия «Технические науки».  2007. № 2 (20).
  3. Гмурман, В.Е. Теория вероятностей и математическая статистика / В.Е. Гмурман. М. : Высш. шк., 2004. 479 с.

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.

Старые записи »

Работает на WordPress