Одним из направлений, на которое непосредственно влияет технологический прогресс, является передача информации. В каком виде она передается, каким методом, насколько быстро и как считывается — все это зависит от уровня доступных технологий. Ярким примером того является QR-код, появившийся в начале 90-ых в Японии и ставший одним из самых популярных методов передачи небольшой информации. В наши дни QR-код можно встретить и на упаковках различных товаров, и на рекламных буклетах, и на визитках и т. д. Однако, несмотря на свою универсальность и простоту, QR-код может столкнуться с проблемой считывания, связанной с топологией поверхности, на которую он нанесен. Ученые из Барселонского университета (Испания) разработали новую методологию улучшения считывания QR-кодов, основанную на подгонке топографии базовой произвольной поверхности с помощью тонкопластинчатых сплайнов. Как именно ученые пришли к созданию этого метода, и насколько он эффективен? Ответы на эти вопросы мы найдем в докладе ученых.

Основа исследования

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


Изображение №1

Тем не менее в реальности QR-коды все же присутствие на самых разных поверхностях, в результате чего возникают проблемы считывания. В рассматриваемом нами сегодня труде ученые описывают новый подход к уменьшению ошибок считывания, используя сам QR-код для подгонки поверхности под заранее установленной топографической моделью на основе известных тонкопластинчатых сплайнов. Тонкие пластинчатые сплайны используются для разложения общей деформаций на основные деформации. Например, в труде «A deformable model for fingerprint matching» ученые использовали их для регистрации отпечатков пальцев из нескольких захватов с нелинейными деформациями. На изображении №1 показаны три отпечатка пальца (a, b и c) и нелинейная деформация, смоделированная с помощью фреймворка TPS (d и e), для соответствия исходному отпечатку пальца.

Авторы рассматриваемого сейчас труда сравнивают копланарное считывание по умолчанию из стандарта QR-кода и современные методы считывания QR-кодов с помощью предлагаемого ими фреймворка TPS.


Изображение №2

Структура QR-кода включает в себя набор определенных паттернов (узоров) для обнаружения QR-кода:

• Паттерн поиска: углы QR-кода (коих три) для нарушения симметрии и ориентирования QR-кода в сцене (2a);
• Паттерн выравнивания: размещен внутри QR-кода, чтобы помочь в исправлении некопланарных деформаций (2b);
• Полосы синхронизации: расположены вдоль двух границ QR-кода, между парой паттернов поиска, чтобы помочь в исправлении копланарных деформаций (2c).
• Четвертый угол: угол, не отмеченный ни одним из трех паттернов поиска. Его можно найти как точку пересечения прямых продолжений самых дальних краев двух паттернов поиска (2d). Он полезен при линейных, копланарных и некопланарных деформациях.

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


Изображение №3

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

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

f: R² → R²

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

A ∙ P = Q

где A — матрица, представляющая отображение, P — ориентиры в области R², а Q — те же ориентиры в области значений отображения. После того как матрица, представляющая отображение A, найдена, любая точка может быть исправлена путем умножения матрицы на A. Для аффинных проекций для решения системы необходимы только три ориентира:



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



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



где g(p_0,0, p_1,0) до g(p_1,5, p_0,0) — цилиндрические составляющие для каждого ориентира; в результате имеется 8 неизвестных a_i,j плюс 3 неизвестных w_j веса для подгонки. Следовательно, нужно как минимум шесть ориентиров для решения системы. Цилиндрические составляющие определяются как:



где r ∈ R — радиус цилиндра, а c₀ ∈ R — первая координата любой точки на центральной линии цилиндра.


Изображение №4

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

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


Алгоритм 1


Алгоритм 2

Предложенный метод TPS подробно показан в алгоритме 1 и 2. Первый алгоритм показывает, как подогнать матрицу отображения TPS из набора ориентиров, а второй — как использовать матрицу отображения TPS для исправления любой точки. Подобно цилиндрическому преобразованию, система уравнений в формализме TPS является расширением аффинной системы. Однако использование ориентиров меняется, поскольку каждый ориентир используется как центр радиального базисного сплайна. Сплайны являются функциями с действительными значениями, центрированными на заданном ориентире:

h: [0, ∞) → R

которые учитывают метрику на векторном пространстве. Их значение зависит только от расстояния заданной точки на плоскости до определенного ориентира:

h_c(v) = h(||v — c||)

где v ∈ Rⁿ — точка, в которой вычисляется функция, c ∈ Rⁿ — ориентир, h — радиальная базисная функция, а h_c(v) определяется как ядро h в c с метрикой ‖ ⋅ ‖. Эти радиальные базисные функции остаются открытыми для множественных определений. Обычный сплайн, используемый в вышеупомянутых работах, — это полиномиальная радиальная базисная функция второго порядка, которая является надлежащей функцией для вычисления сплайнов в отображениях R² с целью минимизации энергии изгиба и имитации упругого поведения тонкой металлической пластины. Таким образом, пусть h будет:

h® = r²ln®

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



Использование радиальной базисной функции h можно найти в шагах 4–6 и 3–5 алгоритма 1 и 2 соответственно. Как уже было сказано, аналогично цилиндрическим преобразованиям, аффинное преобразование расширено, теперь с N нелинейными сплайнами:



Стоит отметить, что присутствуют только аффинные веса a_i,j, поскольку это определение не включает перспективное преобразование. Кроме того, в отличие от предыдущих преобразований, эта система не сбалансирована: у нас есть всего 2N + 6 весов для вычисления (2N w_j,k сплайновых весов плюс 6 a_i,j аффинных весов), однако в данном труде было определено только N ориентиров. Вот почему в формализме TPS налагаются следующие условия: сумма коэффициентов w_j,k должна быть равна 0, а также их перекрестное произведение с координатами ориентиров p_i,k; такие условия заставляют сплайновые вклады стремиться к 0 на бесконечности, в то время как аффинные вклады преобладают:



В шагах 7–10 алгоритма №1 показано, как все предыдущие условия могут быть объединены в одну систему уравнений. После того как система будет решена для заданного набора ориентиров, исходные ориентиры P и матрица отображения A могут быть использованы для оценки коррекции любой точки на подогнанной поверхности TPS, используя процедуру алгоритма №2.

Подготовка к экспериментам

Изображение №5

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


Изображение №6

Ученые создали 3 набора данных для оценки производительности различных преобразований в разных сценариях с произвольными формами поверхностей:

• Синтетические QR-коды (SYNT / Synthetic QR Codes). Этот набор данных был предназначен для оценки влияния данных и геометрии QR-кода на предлагаемые методы коррекции деформации. Для этого были сгенерированы QR-коды как цифровые изображения (без их последующей печати), затем к ним были применены аффинные и проективные преобразования напрямую (6a). Этот набор данных содержал 12 версий QR-кода (от версии 1 до 12), каждая из которых повторялась 3 раза с различными случайными данными (ID), и 19 проекций плюс исходная. Взаимное объединение всех этих вариаций дало в общей сложности 720 изображений для обработки предлагаемыми алгоритмами подгонки поверхности;
• QR-коды на плоских поверхностях (FLAT / QR Codes on flat surfaces). В этом наборе данных ученые закодировали только 1 QR-код версии 7 и распечатали его. Этот QR-код помещали на разные плоские поверхности и делали снимки с помощью портативных устройств (6b). Таким образом, ожидались только проективные деформации в этом наборе данных. Кроме того, захваченные изображения были увеличены, чтобы они соответствовали тому же количеству изображений из предыдущего набора данных. Увеличение изображений состояло в искусственном применении проективного преобразования к изображениям;
• QR-коды на сложных поверхностях (SURF / QR Codes on challenging surfaces). В этом наборе данных использовался тот же QR-код, что и в наборе данных FLAT, но его помещали поверх сложных поверхностей, таких как бутылки, или вручную деформировали QR-коды (6c). Ожидалось, что в наборе данных будут цилиндрические и произвольные деформации. Кроме того, захваченные изображения были увеличены, чтобы они соответствовали размеру других наборов данных.

Таблица №1

Эти 3 набора данных связаны по конструкции, так как они были созданы в одной и той же среде Python с несколькими пакетами, среди которых: qrcode, использовался для создания QR-кодов; imgaug, использовался для создания проективных преобразований; scikit-image, использовался для восстановления ориентиров из QR-кода и подгонки поверхностей; и pyzbar, использовался для чтения QR-кодов. Таблица 1 показывает общие свойства этих наборов данных QR-кодов.

Результаты экспериментов

Изображение №7

Ученые подобрали четыре преобразования (AFF, PRO, CYL и TPS) к поверхности под всеми образцами QR-кода из трех наборов данных (SYNT, FLAT и SURF). Чтобы визуально оценить точность каждого преобразования, квадратная решетка равноотстоящих точек на предсказанной поверхности QR-кода была спроецирована обратно в исходное пространство изображения (фото выше).

Результаты показали, что методы AFF, PRO и CYL не смогли правильно сопоставить случайную поверхность (т. е. деформированную вручную), как и ожидалось. Вместо этого TPS хорошо сработал в этих условиях, являя собой отличный пример силы сплайнового разложения для сопоставления медленно меняющихся топографий, если доступно достаточно большое количество ориентиров. Для цилиндрических деформаций (т. е. QR-кодов на бутылках) методы AFF и PRO снова оказались безуспешными. CYL показал себя лучше с маленькими бутылками, чем с большими. По-видимому, более выраженная кривизна (т. е. меньший радиус бутылки, r) облегчает подгонку этого параметра и улучшает качество общего радиуса прогнозирования проецируемого цилиндра перед подгонкой поверхности. Таким образом, метод CYL правильно подгоняет радиус цилиндра с одной из сторон QR-кодов с 2 паттернами поиска и часто не подгоняет противоположную сторону. Интересно, что метод TPS показал себя противоположно методу CYL в цилиндрических деформациях, справляясь с лучшими поверхностями с небольшой кривизной.

Чтобы оценить влияние этих возможностей прогнозирования поверхности на фактическое считывание данных QR-кода, ученые запустили полный процесс декодирования для всех изображений в трех наборах данных (SYNT, FLAT и SURF) с четырьмя преобразованиями (AFF, PRO, CYL и TPS). Там, после исправления деформации поверхности, данные QR-кода были извлечены с помощью одного из самых распространенных декодеров штрих-кодов (ZBar) с использованием оболочки Python. Таким образом, в этом эксперименте фактически оценивалось, как ошибка, допущенная при оценке геометрии QR-кода из-за деформации поверхности и перспективы, влияет на оценку отдельных битов черного/белого пикселей.

Затем был определен показатель успешности читаемости данных ® как:



где N_decoded — количество успешно декодированных QR-кодов, а N_total — общее количество QR-кодов заданного набора данных и преобразований. Такое число напрямую связано с пользовательским опытом. В сценарии ручного считывания оно говорит о том, как часто пользователю придется повторять попытку считывания (например, R = 95% означает 5 повторений из каждых 100 использований). В приложениях с автоматическим сканированием QR-кодов это измеряет, сколько времени потребуется для сбора данных.


Изображение №8

На графике выше суммированы показатели читаемости четырех преобразований с тремя наборами данных. Для наборов данных SYNT и FLAT методы PRO, CYL и TPS набрали 100% или около того. AFF набрал только 78% и 60% для наборов данных SYNT и FLAT соответственно. Это связано с тем, что в AFF отсутствуют перспективные компоненты, которые PRO и CYL включают для решения этой проблемы. Примечательно, что TPS набрал аналогичные PRO и CYL баллы для этих двух наборов данных: несмотря на то, что TPS не включает перспективу напрямую, он состоит из аффинных и нелинейных членов, а последние могут соответствовать перспективной деформации.


Изображение №9

Это поведение также подтверждается для сгенерированных данных в наборе данных SYNT (график выше), где TPS показал себя немного хуже на изображениях с перспективной деформацией, аналогично AFF. Также на графике выше видно, что AFF показал наилучшую производительность (97%) в подмножестве изображений, где присутствовало только аффинное преобразование, и более низкую производительность в проективных изображениях (70%).


Изображение №10

На графике выше показаны сегрегированные данные для набора данных SURF, ни AFF, ни PRO преобразования не справились с декодированием хотя бы одного QR-кода (1%–2%). CYL показал себя хорошо для цилиндрических поверхностей в наборе данных SURF (62%), но уступил результатам TPS на 13 баллов (с 62% до 75%). Более того, CYL набрал менее 30% на изображениях без явных цилиндрических деформаций, в то время как TPS остался значительно выше 85%. Это замечательный результат для TPS, учитывая, что остальные преобразования полностью не справились с этой задачей.


Изображение №11

В заключение ученые хотели сравнить предлагаемую методологию с популярным современным декодером, таким как ZBar. Для этого ученые снабдили ZBar всеми вышеописанными наборами данных изображений (без предварительной обработки и с внесенными поправками на геометрию поверхности). График выше показывает, что реализация Zbar, которая считывает пиксели QR-кода из каждой строки QR-кода как одномерный штрихкод, очень хорошо работает с набором данных SYNT. Но на более реалистичных изображениях, снятых смартфоном из FLAT, ZBar показал себя плохо, преуспев только примерно в 2∕3 набора данных. Удивительно, но ZBar все еще смог декодировать некоторые изображения набора данных SURF. Ученые сравнили эти результаты с объединенной последовательностью преобразований CYL и TPS, которые можно рассматривать как TPS с откатом к методу CYL, поскольку CYL имеет свой собственный откат в PRO. Этот метод оказался немного лучше ZBar в наборе данных SYNT, но получил идеальный результат в наборе данных FLAT, где ZBar испытывает трудности (100% против 75%), и продемонстрировал замечательное преимущество (84% против 19%) при декодировании самого сложного набора данных SURF. Из этого следует, что предложенный в данном труде метод превосходит самые современные технологии при работе со сложными топографиями поверхностей.

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

Эпилог

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

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

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

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

Немного рекламы

Спасибо, что остаётесь с нами. Вам нравятся наши статьи? Хотите видеть больше интересных материалов? Поддержите нас, оформив заказ или порекомендовав знакомым, облачные VPS для разработчиков от $4.99, уникальный аналог entry-level серверов, который был придуман нами для Вас: Вся правда о VPS (KVM) E5-2697 v3 (6 Cores) 10GB DDR4 480GB SSD 1Gbps от $19 или как правильно делить сервер? (доступны варианты с RAID1 и RAID10, до 24 ядер и до 40GB DDR4).

Dell R730xd в 2 раза дешевле в дата-центре Maincubes Tier IV в Амстердаме? Только у нас 2 х Intel TetraDeca-Core Xeon 2x E5-2697v3 2.6GHz 14C 64GB DDR4 4x960GB SSD 1Gbps 100 ТВ от $199 в Нидерландах! Dell R420 — 2x E5-2430 2.2Ghz 6C 128GB DDR3 2x960GB SSD 1Gbps 100TB — от $99! Читайте о том Как построить инфраструктуру корп. класса c применением серверов Dell R730xd Е5-2650 v4 стоимостью 9000 евро за копейки?