Как устроен QR-код и почему он не боится грязи

Откуда взялись двумерные коды

Обычный штрихкод знаком каждому по упаковкам товаров в магазине. Он состоит из чередующихся чёрных и белых полос разной толщины. Такой код называют одномерным, потому что сканер считывает его только в одном направлении — по горизонтали. Полоски кодируют ограниченный объём информации, обычно от 10 до 30 символов. Этого хватает для идентификатора товара, но записать длинную интернет-ссылку или подробный текст в такие рамки невозможно.

В начале 1990-х годов на заводах японской компании Denso Wave, поставлявшей автозапчасти для Toyota, возникла серьёзная проблема. Рабочим приходилось сканировать до десяти разных штрихкодов на одной коробке с деталями, чтобы зафиксировать сборку. Очереди на конвейере росли, сканеры периодически ошибались, а на бланках не оставалось свободного места.

В 1994 году инженер Масахиро Хара придумал решение. Во время обеденного перерыва он наблюдал за игрой в го, где игроки расставляют чёрные и белые камни по клеткам сетки. Хара понял, что данные можно размещать одновременно по горизонтали и по вертикали. Название новой разработки составили из первых букв английских слов Quick Response — быстрый отклик, подчеркивая способность датчика мгновенно распознавать узор.

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

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

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

Угловые квадраты имеют строгую пропорцию ширины линий 1:1:3:1:1. Это означает, что чёрная рамка, белая полоса, центральный чёрный квадрат, вторая белая полоса и вторая чёрная рамка соотносятся по толщине именно в такой пропорции. Масахиро Хара проанализировал тысячи печатных страниц, газет и упаковок, чтобы выяснить, какое сочетание контрастных линий реже всего встречается в реальном мире. Оказалось, что соотношение 1:1:3:1:1 почти уникально, поэтому камера телефона находит код за доли секунды и не путает его с окружающим текстом.

Как работает алгоритм защиты от повреждений

Устойчивость к царапинам, краске и пыли обеспечивает алгоритм Рида — Соломона. Эту математическую модель изобрели учёные Ирвинг Рид и Гюстав Соломон ещё в 1960 году. Изначально метод создавали для передачи данных через помехи в дальнем космосе, а позже применили в компакт-дисках, чтобы музыка играла без заиканий даже на поцарапанном пластике.

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

Четыре уровня живучести

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

• Уровень L допускает восстановление около 7% повреждённых данных и используется на чистых экранах мониторов.
• Уровень M восстанавливает до 15% утерянной информации и считается универсальным стандартом для магазинных чеков и билетов.
• Уровень Q справляется с потерей до 25% площади и подходит для наружной рекламы, подверженной дождю и пыли.
• Уровень H выдерживает уничтожение до 30% модулей и применяется в суровых промышленных условиях.

Чем выше выбран уровень надёжности, тем больше проверочных модулей приходится рисовать. При одинаковом объёме текста код с уровнем H выглядит заметно плотнее и состоит из гораздо более мелких точек, чем код с уровнем L.

Почему пиксели распределены равномерно

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

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