Новые возможности в распознавании баркодов

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

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

Задача: разработать iOS-приложение с функцией сканирования линейных (1D) штрихкодов. Штрихкоды должны считываться без дополнительного выравнивания по горизонтальной оси и непрерывно, т. е. должны распознаваться все кадры, попадающие с камеры, до тех пор, пока устройство не получит сигнал закончить считывание.

Фаза на GPU

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

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

В качестве хранилища данных будем использовать текстуры. По сути они будут являться матрицами с которыми мы будем производить операции. Нужно понимать, что одна из самых трудоемких операций для GPU это — вычитывание значения пиксела текстуры. Поэтому, из соображений производительности, стараемся использовать для хранения данных все 4 канала(RGBA) каждого пиксела текстуры.

Шаг 1. Переведем полученное с камеры изображение в режим градаций серого (grayscale), т.к. информация о цвете не важна для алгоритма:

Для получения серого используем следующее выражение (здесь и далее программный код на языке glsl):

float grayscale = dot(texture2D(CameraTexture, textureCoordinate).rgb, vec3(0.299, 0.587, 0.114));

Шаг 2. Произведем фильтрацию изображения методом свертки. Для этого рассчитываем значения градиента яркости изображения по четырем направлениям: 0, 90, 45 и 135 градусов. Применим фильтрацию по всем 4-м направлениям в одном проходе. Для сохранения результатов используем все четыре канала текстуры (R, G, B, A).

Фильтрующие матрицы:

0 градусов

-0.25    -0.25

0.25     0.25

90 градусов

0.25      -0.25

0.25      -0.25

45 градусов

0      -0.25      0

0.25     0       -0.25

0       0.25      0

135 градусов

0       0.25      0

0.25     0       -0.25

0      -0.25      0

Результат:

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

Шаг 3. Для уменьшения шумности, фильтруем карту яркости, используя алгоритм размытия по Гауссу. Для сокращения объемов вычислений уменьшим изображение в 2 раза. Фильтрацию Гауссом делаем в 2 прохода, 1 проход по оси абсцисс, второй проход по оси ординат.

Результат:

Шаг 4. За один проход рассчитаем разность модулей градиентов по ортогональным направлениям. Отличительной чертой штрихкодов является то, что они имеют достаточно большие градиент яркости по одному направлению, и низкий по ортогональному направлению. Т. е. если мы найдем разность ортогональных градиентов по всему кадру мы сможем «проявить» области штрихкодов и «потушить» остальной шум. Запишем полученные результаты в каналы R разницу 0-90 и G разницу 45-135.

Результат:

Шаг 5. После этого конвертируем отфильтрованное изображение в bitmap. Для этого сравниваем полученные средние значения яркости с заранее заданным порогом: т.е. значения, что выше, конвертируем в пикселы белого цвета, что ниже — в черные. Можно использовать метод Оцу для адаптивной бинаризации. Как промежуточный результат получаем практически черный экран с несколькими белыми прямоугольниками — вероятными областями штрихкодов.

Результат:

Фаза на CPU

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

Результат:

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

В результате для одного штрихкода получаем текстуру следующего вида:

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

Фаза на GPU

Шаг 1. На GPU произведем обработку единичной линии сканирования (scan line) с каждой текстуры штрихкода, исследуем вектор изменения яркости и построим карту экстремумов. Передадим полученные данные текстур карт яркости и значения экстремумов для обработки на CPU, используя объект CVOpenGLESTextureCacheRef.

Результат:

Шаг 2. В канал R сохраняем величину яркости каждого пиксела, в канал G — верхний экстремум, в канал B — нижний экстремум.

Шаг 3. Полученную текстуру передаем на CPU, где происходит окончательный анализ, а затем и расшифровка штрихкода.

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

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

С помощью нашего алгоритма можно, например, прочитать такие штрихкоды:

В заключение несколько слов о технических характеристиках разработанного нами приложения:

• на данный момент реализовано чтение штрихкодов стандарта ISBN, CODABAR, CODE39 и ISBN. Однако, благодаря тому, что наш прототип является масштабируемым и модульным, к нему без труда можно подключать желаемые алгоритмы для распознавания других форматов штрихкодов;
• производительность приложения на iPhone 4 достигает 20 операций распознавания в секунду, для iPhone 4S этот показатель выше;
• текущая версия прототипа может работать на iPhone 4, iPhone 4S, iPad 2 и на камерах с фиксированным или переменным фокусом.

В будущем мы планируем расширить список платформ, поддерживающих наше приложение. А поскольку мы использовали открытые и кроссплатформенные технологии, такие, как OpenGL 2.0 и OpenCV, перенести прототип на другие платформы не составит труда. Также в перспективе — усовершенствование алгоритма:

• использовать несколько линий сканирования для анализа;
• задействовать exif-данные каждого кадра для предварительной подготовки изображения и применение других видов оптимизации для увеличения качества и скорости считывания.

Если у вас возникли вопросы, вы всегда их можете нам задать.