Инженерная составляющая матрицы

Для обычного пользователя QR-код — это просто беспорядочный квадрат черно-белых пикселей. Но с инженерной точки зрения изобретение Denso Wave 1994 года представляет собой мастер-класс по геометрии, обработке сигналов и математике с исправлением ошибок.

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

1. Геометрия ориентации: шаблоны поиска и выравнивания

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

\текст Соотношение диаграммы направленности видоискателя (под любым углом): [Черный] [Белый] [Черный] [Белый] [Черный] 1 : 1 : 3 : 1 : 1 \

Почему существует ровно три шаблона Finder?

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

Вращение (вверх): Поскольку в четвертом углу (справа внизу) нет рисунка, сканер мгновенно определяет, перевернуто ли изображение или вбок, и поворачивает сетку данных в цифровом виде.
Масштаб (расстояние): Физическое расстояние между тремя точками сообщает датчику камеры, насколько точно находится код, что позволяет программному обеспечению масштабировать цифровую сетку для соответствия.
Перспектива/Наклон (Углы): Если сканировать QR-код под острым углом, три точки образуют неровный треугольник, а не идеальный прямоугольный треугольник. Сканер использует искаженные углы для математического «выравнивания» и выравнивания изображения перед считыванием данных.

Коэффициент сканирования 1:1:3:1:1

Шаблоны поиска представляют собой вложенный квадрат модуля $7\times7$. Независимо от того, под каким углом лазер или датчик камеры проходит через центр этих квадратов, соотношение черных, белых и черных модулей всегда математически постоянно: 1 часть черного, 1 часть белого, 3 части черного, 1 часть белого, 1 часть черного.

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

Для чего нужны меньшие внутренние квадраты?

По мере увеличения размера версии QR-кодов (с версии 2 до версии 40) они включают в себя меньшие одиночные вложенные квадраты, называемые Шаблоны выравнивания.

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

2. Как кодируются данные: сопоставление двоичных данных с кремнием

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

Перед рендерингом входные данные (например, URL-адрес) обрабатываются в одном из четырех режимов кодирования:

Числовой: лучше всего подходит для необработанных чисел (3 цифры преобразуются в 10 бит).
Буквенно-цифровой: поддерживаются заглавные буквы, цифры и основные символы (2 символа преобразуются в 11 бит).
Байт: Стандартная кодировка UTF-8 (каждый символ преобразуется в стандартное 8-битное двоичное представление).
Кандзи: оптимизирован для двухбайтовых японских символов.

Для стандартного URL-адреса, такого как https://ez-qr-generator.com, генератор использует байтовый режим. Строка преобразуется в последовательность 8-битных байтов, которые затем физически сопоставляются с сеткой, начиная с правого нижнего угла, зигзагами вверх и вниз, пропуская структурные шаблоны.

3. Исправление ошибок Рида-Соломона: восстановление поврежденных данных

Определяющей особенностью QR-кода является его способность сканироваться, даже если он частично порван, загрязнен или скрыт. Эта надежность обеспечивается Коррекция ошибок Рида-Соломона — точно такой же математике на основе полинома, которая используется для передачи данных с зондов дальнего космоса (таких как «Вояджер») и для воспроизведения музыки на поцарапанных аудио-CD.

Когда генерируется QR-код, система не просто записывает ваш URL-адрес. Он рассматривает байты двоичных данных как коэффициенты сложного математического полиномиального уравнения. Используя эти коэффициенты, генератор вычисляет дополнительные избыточные «байты четности» и добавляет их в конец данных.

В зависимости от выбранного уровня коррекции ошибок эти байты четности занимают разные проценты сетки:

Уровень L (Низкий): Восстанавливает до 7% потерянных данных.
Уровень M (средний): Восстанавливает до 15% потерянных данных.
Уровень Q (квартиль): Восстанавливает до 25% потерянных данных.
Уровень H (высокий): восстанавливает до 30% потерянных данных (настоятельно рекомендуется для кодов с пользовательским стилем и центрированными логотипами).

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

4. Скрытый шаг: математические шаблоны маскировки

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

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

\текст Пример формулы маскировки (Маска 0): Примените XOR к пикселю, если: (строка + столбец) % 2 == 0
Генератор пропускает необработанный QR-код через все восемь формул маскировки, используя операцию XOR (которая инвертирует указанные пиксели на основе математической формулы сетки).

Чтобы решить, какую маску использовать, генератор сравнивает восемь результатов со строгой системой подсчета штрафных баллов:

Наказание 1: Вычитаются баллы за пять и более последовательных модулей одного цвета в строке или столбце.
Наказание 2: Вычитаются очки за любые $2\times2$ блоки одного цвета.
Наказание 3: Вычитаются баллы за шаблоны, напоминающие шаблоны искателя 1:1:3:1:1 (чтобы не запутать сканер).
Наказание 4: Вычитаются баллы, если общее соотношение черных и белых модулей значительно отклоняется от идеального соотношения 50/50.

Маска с наименьшим штрафным баллом навсегда применяется к сетке. Идентификатор этой конкретной маски (от 0 до 7) затем записывается непосредственно в модули метаданных рядом с шаблонами поиска, сообщая приложению сканирования, какую именно математическую формулу следует использовать для изменения маски и чтения базовых данных.