Уверены, что на сегодняшний день не найдется ни одного читателя Хабра, который не был бы знаком с QR-кодами. Эти двумерные штрихкоды повсюду. Закономерно, что в мире существует много инструментов, позволяющих с некоторой долей эффективности добавить QR-коды в свой проект. Вся соль в том, что эта упомянутая эффективность напрямую зависит от качества инструмента, который используется для распознавания QR-кодов. И тут возникает классическая вилка: можно решить задачу (очень) хорошо и (очень) дорого, а можно бесплатно и как-то. А можно ли доработать бесплатное так, чтобы все-таки решить задачу хорошо? Если интересно, заглядывайте под кат.

Распознавание QR-кода на фотографии – хорошо поставленная задача машинного зрения. Во-первых, в задаче исследуется объект, изначально специально разработанный для «удобного» распознавания. Во-вторых, сама задача разбивается на несколько независимых понятных подзадач: локализация QR-кода, ориентация QR-кода и непосредственно декодирование QR-кода. Так оказалось, что общественное достояние уже довольно давно обладает хорошими библиотеками, способными решить последние две задачи: ориентацию и декодирование QR-кода. Одна проблема: для качественного декодирования такие библиотеки ожидают на вход хорошее бинарное изображение непосредственно штрихкода. И наоборот, задаче локализации штрихкода на изображении уделяется мало внимания.

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

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

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

Информационная справка по теме статьи

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

QR-код

QR-код (сокращение от Quick Response Code) – двумерный штрихкод, который был разработан в Японии в середине 90-х годов для целей автомобильной промышленности. Благодаря возможности быстрого считывания и большей по сравнению с линейными штрихкодам ёмкости, система QR-кодов стала популярна во всем мире в различных областях жизнедеятельности.

В отличие от стандартных линейных штрихкодов, которые обычно сканируют аппаратно, QR-код часто сканируется камерой. Структура QR-кода полностью описана стандартом ISO/IEC 18004 (The ISO/IEC standard 18004). Для построения устойчивого алгоритма распознавания таких изображений QR-код обладает некоторыми реперными точками, которые формируют функциональный шаблон (function pattern): три квадрата в углах изображения штрихкода (которые называются finder patterns) и меньшие синхронизирующие квадратики по всему изображению штрихкода (которые называются alignment patterns). Такие точки позволяют нормализовать размер изображения и его ориентацию.

Рис. Структура QR-кода

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

Рис. Различные допустимые варианты QR-кода

Метод Виолы и Джонса

Только ленивый на Хабре еще не писал про метод Виолы и Джонса. Даже мы в своем блоке делали это несколько раз (например, здесь, здесь или здесь). И все равно, считаем необходимым совсем кратко, буквально в двух абзацах рассказать, что же это такое.

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

В качестве признакового пространства метод Виолы и Джонса использует прямоугольные признаки Хаара, значение которых вычисляется как разность сумм яркостей пикселов областей изображения внутри смежных прямоугольников. Для эффективного вычисления значения признаков Хаара используется интегральное изображения, которое также известно в литературе под термином summed-area table. С каждым признаком метод Виолы и Джонса связывает бинарный «слабый» классификатор h(x):?>{-1,+1}, обычно представленный в виде распознающего дерева с одним ветвлением:



где ? и p – пороговое значение признака и четность (parity) классификатора соответственно. Далее с помощью метода машинного обучения AdaBoost строится «сильный» классификатор как линейная суперпозиция указанных выше «слабых» классификаторов. Высокая скорость работы метода Виолы и Джонса обеспечивается за счет использования каскада «сильных» классификаторов, который позволяет за малое количество вычислений локализовать «пустые» (не содержащие объект) регионы изображения.

Алгоритм детектирования QR-кодов

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

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

• в классическом методе Виолы и Джонса используется семейство признаков Хаара, которые «подчеркиваю» текстурные особенности объекта, а в нашем случае, хотя QR-код и состоит из черных и белых барселов, их распределение сильно отличается от штрихкода к штрихкоду;
• классический метод Виолы и Джонса предназначен для однотипных детектирования объектов в заданной ориентации, что также не соблюдается в нашей задаче.

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

Градиентные признаки Хаара

Для построения эффективного детектора QR-кодов мы использовали специальное семейство градиентных признаков [1]. Данные признаки представляют собой прямоугольные признаки Хаара, вычисляемые поверх карты направленных границ, что позволяет существенно улучшить их обобщающую силу.

Карта направленных границ представляет собой изображение модуля градиента, где дополнительно учитывается преимущественное направление градиента в точке (x,y), определяемое как дискретизация угла границы на горизонтальное, вертикальное, +45° и –45° направления. Для построения детектора QR-кодов мы использовали два типа карты направленных границ: карту прямых границ и карту диагональных грани.

Пусть задано исходное изображение f(x,y). Тогда можно посчитать приближенное значение производной вдоль горизонтального и вертикального направлений, используя оператор Собеля:



Кроме того, используя g_x и g_y, можно в каждой точке изображения посчитать направление градиента:



Карта прямых границ содержит преимущественно горизонтальные и вертикальные границы и вычисляется следующим образом:



Карта диагональных границ содержит преимущественно границы вдоль диагоналей и вычисляется следующим образом:



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

Рис. Иллюстрация карты направленных границ: (a) исходное изображение QR-кода, (b) карта прямых границ, (с) изображение повернутого QR-кода (d) карта диагональных границ повернутого QR-кода

Решающее дерево сильных классификаторов

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

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

Древовидный классификатор позволяет обучать более эффективные с точки зрения полноты классификаторы для вариативных объектов по сравнению с классическими каскадными классификаторами.

Экспериментальные результаты

В рамках эксперимента по оценке эффективности предложенного в данной статье способа локализации штрихкода был подготовлен набор изображений штрихкодов, состоящий из 264 изображений. Физический размер изображений составлял порядка 1 МПикс. На каждом изображении присутствует только один QR-код в произвольной ориентации, площадь штрихкода составляла не менее 10% от площади всего изображения. На рисунке ниже представлены примеры изображений из собранного набора.

Рис. Примеры изображений из собранного набора изображений штрихкодов

Подготовленный набор изображений был поделен на обучающую выборку и тестовую выборку. Размер обучающей выборки составил 88 изображений, размер тестовой выборки составил 176 изображений.

Обучающий набор использовался для как для подготовки положительных примеров, так и для подготовки отрицательных примеров. Так как исходное количество положительных примеров было мало, мы использовали технологию аугментации данных [3]. В частности, мы применили вращение вокруг центра штрихкода с шагом в 15?. После аугментации количество положительных примеров составило 2088 примеров.

На одних и тех же положительных и отрицательных примерах нами было обучено три детектора QR-кода: классический каскадный классификатор со стандартными признаками Хаара, классический каскадный классификатор с граничными признаками, а также древовидный классификатор с граничными признаками. Первый каскадный классификатор состоял из 12 уровней и содержал в общей сложности 58 признаков. Второй каскадный классификатор состоял из 8 уровней и содержал в общей сложности 39 признаков. Обученный древовидный классификатор состоял из 39 вершин, содержал в общей сложности 110 признаков, максимальный путь от вершины до листа составил 9. Ниже представлена схема обученного древовидного классификатора.

Рис. Схема обученного древовидного классификатора

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

Из таблицы видно, что предварительная локализация QR-кода с помощью описанного метода позволяет существенно улучшить качество декодирования штрихкодов (количество ошибок декодирования сократилось на 44%). Кроме того, результаты также демонстрируют, что применение оригинального метода Виолы и Джонса (с классическими признаками Хаара и каскадным классификатором) не эффективны в задаче локализации QR-кодов.

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

Рис. Иллюстрация работы обученных детекторов на одном и том же изображении

Заключение

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