Как настольная игра и небоскребы вдохновили на разработку QR-кода
Про QR код на том же Хабре есть огромное количество информации. Ничего удивительного: сейчас сложно найти отрасль, где бы он не применялся. Тут и банковские операции, и идентификация товаров, и цифровые визитки. Преимущества очевидны: считывается мгновенно любым смартфоном, причем даже если треть QR кода повреждена, а еще хранит до 2935 байт двоичного кода.
Но сегодня поговорим не про технические нюансы. Вы знали, что его придумали благодаря любви к играм и небоскребам? Если не знали, устраивайтесь поудобнее — поговорим об истории появления QR кода.
До появления QR кода
Пожалуй, первым способом печатного кодирования стал жаккардовый станок, появившийся в 1804 году. Суть заключалась в том, что в него загружались перфокарты с двоичным кодом: они буквально говорили, в какой момент и какой нити опуститься в определенном месте или наоборот подняться, в зависимости от последовательности отверстий. Благодаря этому изобретению получались сложные узоры, скорость значительно возросла, а риск человеческой ошибки был сведен к минимуму. Только успевай менять нити и следить за перфокартами.
Отверстия наносились на картон или деревянные пластины. Иногда, в зависимости от сложности узора, требовались сотни разных перфокарт
Система звукового кодирования типа «точка-тире», или азбука Морзе, появилась чуть позже, в 1838 году. Именно она продемонстрировала, что любой символ можно передать в виде последовательности 1 и 0. Кстати, на азбуку Морзе опирались при создании первых штрихкодов.
«Морзянка», пожалуй, никогда не потеряет актуальности
Еще одной важной вехой стала перепись населения США в 1890 году. Уникальной ее делало то, что в ней впервые применялся автоматизированный подход: данные с листов опроса переносились на перфокарту и затем обрабатывались с помощью табулятора. Эту идею предложил и впоследствии популяризовал знаменитый инженер Герман Холлерит. Если прошлую перепись 1880 года считали около 8 лет, то благодаря новой системе первые данные опубликовали уже через 6 недель — 62 947 714 жителей.
Электрическая машина по подсчету голосов
В 1932 году студент Гарвардского университета по имени Уоллес Флинт написал дипломную работу, в которой ориентировался на опыт как раз переписи населения США. На тот момент в Америке появлялись сети супермаркетов, а в них активно шли покупатели. Чтобы упростить работу, Уоллес Флинт предложил такую систему:
Покупатель не ходит в поисках продуктов на многоэтажных полках, а берет каталог, протыкает отверстие напротив продуктов и передает кассиру.
Тот вставляет в считывающее устройство — механизм запускается.
Через сложную систему конвейеров и толкателей продукты складывались бы в корзину на кассе — оставалось только пробить чек. Заодно в системе появится информация о точных остатках продуктов и объемах продаж за день, месяц и год.
К сожалению, из-за сложности реализации ничего не вышло. Да и из-за Великой Депрессии выделить такую значительную инвестицию ни один супермаркет не решился.
Один из первых супермаркетов Америки Piggly Wiggly — 1918 год, а народу как в очереди за молоком в СССР конца 80-х
После войны к теме автоматизации работы супермаркетов в США вернулись. Один из руководителей супермаркета в Филадельфии обратился к знакомому декану Технологического университета Дрекселя с просьбой помочь идентифицировать товар. Уж очень много времени уходило у кассиров из-за большого ассортимента. Декан поручил решить задачу аспирантам Бернарду Сильверу и Норману Вудланду.
Поначалу они искали способ наносить на товары специальные чернила, которые бы светились только под ультрафиолетовым светом. Но ничего не вышло. В какой-то момент Вудланд воскликнул: «Черт возьми. А что если попробовать азбуку Морзе?». Он предложил вытянуть эти точки в виде вертикальных темных полос. Широкая — тире, узкая — точка. А чтобы не нужно было думать над ориентацией товара, Сильвер предложил сделать штрих-код круглым.
Оставалось только считать темные и светлые области и по длительности получить зашифрованный код. На это ушло долгих 4 года, прежде чем в 1952 году на тот момент уже инженеры, а не аспиранты, создали сканер круглых штрихкодов. Работала система так:
Мощная 500 Вт лампа светила на сканер штрих-кода;
Отраженный свет попадал на фотодетектор;
Оператор-кассир водил лампой: интенсивность отраженного света менялась, в зависимости от ширины полосок. Это улавливал фотодетектор.
Круглый штрихкод на банке с зеленой фасолью
Однако устройство было настолько непрактичным, что Вудланд и Сильвер пытались найти, кто сможет профинансировать их исследования. Все кончилось тем, что никто ничего не профинансировал, а патенты оказались в руках Радиокомпании Америки (RCA).
Следующий важный шаг — это появление цветовой кодировки KarTrack для железнодорожных вагонов. Суть была той же самой: нужно было быстро и точно определять, какой вагон подъезжает к определенному пути. Дэвид Коллинз в 1967 году придумал на базе концепции Вудланда и Сильвера оригинальную идею.
На вагоны наносились 13 цветных полос, расположенных горизонтально. Напротив располагался сканер: лампа мощностью в 200 Вт светила на вращающееся зеркало, из-за чего луч перемещался в вертикальной плоскости. Как бы сканировал по вертикали. Отраженный свет попадал на фотодетекторы (еще они называются фототрубки) с цветными фильтрами: красным и синим. Дальше происходило вот что:
Если луч попадал на красную полосу, срабатывал только красный фотодетектор;
Если попадал на синюю полосу, то срабатывал только синий фотодетектор;
Если на белый (точнее в клеточку), то срабатывали оба фотодетектора;
Если луч попадал на черный, то не срабатывало ничего.
То есть с одной полосы можно было передать 16 сигналов. Но использовалось только 12: передавались цифры от 0 до 9, контрольная сумма и метки «старт» + «стоп». Это позволяло считывать номера вагонов, их принадлежность и так далее. С появлением интегральных микросхем и компьютеров PDP-8, объединившихся в сеть, появилась реальная возможность построить систему по идентификации вагонов.
Сканеры располагались на расстоянии 2–3 метров и помещались в закрытые металлические шкафы со степенью защиты IP67
Штрих-код состоял из 13 полос синего, красного, черного цвета, а также заштрихованных областей. Сертификация подтвердила, что на скорости до 97 км/ч номер вагона считывается в 95% случаев. По факту скорость проходящих на станции поездов редко превышала 30 км/ч
Однако система была не очень надежной: луч часто отклонялся в сторону, и зеркало приходилось перенастраивать. А еще в непогоду этикетки часто загрязнялись, из-за чего белый и черный путались — это вызывало огромную головную боль операторов. KarTrack просуществовала до конца 70-х годов, пока от нее не отказались в пользу RFID меток (кстати, они появились уже в 1973 году). Но это уже тема отдельной статьи — мы говорим про оптические системы.
В 1973 году инженер IBM Джордж Лорер и знакомый нам уже Норман Вудланд, перешедший на работу в IBM, предложили идею современного штрихкода — Universal Product Code (UPC). Вместо круглых этикеток решили перейти на линейные — это сильно упрощало печать, да и округлые линии сильнее смазывались при печати.
Пример кодировки UPC-A
Первый вариант кодировки назвали UPC-A. Он состоит из 11 цифр (от 0 до 9) и одной контрольной суммы — итого 12 цифр. Любая из цифр кодируется 7 полосами шириной 0,33 мм каждая — назовем это модулем. Полосы могут быть черными и белыми — логично, что это соответствует 0 и 1. Получается, что на любую цифру приходится 7 бит. Итого на 12 цифр получится 84 полосы, не считая системных. Есть два правила:
Каждый модуль обязательно содержит 2 черных и 2 белых полосы.
Ширина черных и белых полос, идущих подряд, не может быть больше 4.
Цифра | Код | Цифра | Код |
0 | 0001101 | 5 | 0110001 |
1 | 0011001 | 6 | 0101111 |
2 | 0010011 | 7 | 0111011 |
3 | 0111101 | 8 | 0110111 |
4 | 0100011 | 9 | 0001011 |
Кодировка для цифр слева — для цифр справа каждый бит инвертирован
Очень упрощенное объяснение, как кодируются цифры
Слева, справа и по центру расположено 3 разделительных линии по 3 полосы: 1–0–1. Это сделано, чтобы при сканировании код считывался как слева направо, так и справа налево — это минимизирует ошибки кассира. Если обратите внимание, то полосы симметрично инвертированы относительно друг друга.
Для расчета контрольной суммы используют алгоритм:
Суммируются все цифры на нечетных позициях (1-я, 3-я и так далее), а результат умножается на три
К результату прибавляются все цифры на четных позициях (2-я, 4-я и так далее).
Округляют в большую сторону до числа, кратного 10
Делят получившееся число на 10
Результат вычитают из 10
Пример расчета контрольной суммы
Сам считанный код из 11 цифр состоит из трех частей:
Префикс — 1 цифра
Код производителя — 5 цифр
Код товара SKU — 5 цифр
Чуть подробнее вы можете прочитать в спецификации.
В 1974 году систему распознавания UPC кодировки впервые внедрили в супермаркет Marsh в городе Трой, штат Огайо. Первая продажа — 10 пачек жевательной резинки Wrigley. IBM на тот момент уже разработала и первый сканер на базе твердотельного лазера, и систему компьютерного учета.
Конечно, это было очень удобно: можно было отслеживать товарооборот, учитывать складские запасы и так далее. Но из-за высокой стоимости оборудования к 1979 году только 1% ритейлеров в США использовали UPC кодировку. Но после того, как компьютеры стали массовым и доступным явлением, цена на оборудование упала — к 1984 году уже больше 80% торговых точек Америки использовали штрихкоды.
Надо отметить, что появлялось много и других систем. Например:
Code 39, который позволял кодировать буквы латинского алфавита и некоторые специальные символы. Был внедрен в 1981 году Министерством обороны США для маркировки всей продукции, поставляемой вооруженным силам.
EAN-13, аналог UPC-A, введенный в европейских странах в 1977 году. Ключевое отличие: добавлена 13 закодированная цифра. Позже появился и более простой формат EAN-8 для размещения на более компактных товарах вроде сигарет и жвачки.
Многочисленные клоны UPC-a вроде UPC-E, UPC-2, UPC-5 и прочих.
Вот лишь некоторые примеры разных стандартов кодирования — на самом деле их намного больше
Во второй половине 80-х годов штрихкоды шагали по миру и внедрялись не только в торговлю, но и в производство. Например, их активно использовала японская компания Denso — крупный производитель автозапчастей.
Как Масахиро Хара придумал QR код
Инженер дочерней компании Denso Wave (входила в холдинг Toyota и занималась системами оптического распознавания) Масахиро Хара понимал, насколько штрихкоды изменили подход к производству и хранению продукции в лучшую сторону. Но также он видел их недостатки: стандартный UPC-A мог передавать, как мы знаем, до 12 цифр.
Представьте, что у вас в одной коробке хранится 100 однотипных запчастей. Они сгруппированы, скажем, по принадлежности к определенной модели авто. Каждая группа деталей имеет свой артикульный номер — допустим 10 или 12 цифр, потому что каталог деталей огромен. Рабочему надо взять деталь из коробки и пикнуть штрихкод. Но деталь маленькая, поэтому код размещается прямо на коробке: чем больше таких групп, тем больше этих штрихкодов.
Рабочий Toyota при сборке двигателя, 1989 год
Хара расспросил рабочих и выяснил, что иногда им приходилось считывать по сотне штрих-кодов в день — это отнимало очень много времени. Для японцев, одержимых оптимизацией производства (привет, Toyota и ее канбан), это было неприемлемо. Хара решил изменить подход и уменьшить это время. Как этого можно добиться?
Ну, первое и самое очевидное: доработать систему штрихкодов и запихнуть в нее больше цифр. Проблема в том, что тогда этикетки будут становится больше по размерам — их не наклеишь на небольшие коробки или детали. Важно использовать площадь максимально эффективно. А уменьшать ширину полос и расстояние между ними невозможно из-за разрешающей способности сканеров того времени.
Тогда есть другой путь: изменить подход и придумать, как уместить больше информации на как можно меньшей площади. А еще, кроме цифр, было классно уместить туда и кандзи — японские иероглифы, чтобы при сканировании у человека появлялся еще и текст.
Во время одного из обедов Масахиро Хара привычно сел играть в свою любимую игру го с одним из коллег. Как вдруг, глядя на доску, ему пришла в голову идея. Вот как он описывает ее:
«Однажды я смотрел на доску и обратил внимание, как го-иси (камни) выстроились на пересечении линий поля в двух направлениях. Получался такой большой массив информации — почему бы не использовать это?»
Игра го действительно очень напоминает QR код при взгляде сверху. Не находите?
Конечно, идея 2D кодов не была новой. Впервые ее использовал Дэвид Алле в 1987 в так называемом Code 49. Он чем-то напоминает UPC, но имеет больше полос и самое главное — есть несколько рядов один над другим. Такая вариативность позволяла уже хранить намного больше данных, например еще и 128 ASCII символов.
Первый 2D код имел 18 полос и 17 пробелов в каждой строке. Более подробно с алгоритмом можете познакомиться здесь
В 1991 году появился еще один код, который используется и сейчас — это кодировка PDF417, позволяюащя упаковывать до 2710 символов. Вы можете видеть их сейчас на каждой декларации 3-НДФЛ или билете на самолет. Причем в этом стандарте сразу применялось полиномиальное кодирование Рида-Соломона.
Однако все эти варианты не очень подходили под задачу Масахиро Хара. Дело в том, что все они по-прежнему занимали довольно много места, но самое главное — были чувствительны к ориентации сканера. У рабочих автомобильного завода нет времени думать о том, под каким углом нужно поворачивать сканер.
В один из дней, как позже вспоминал Хара, он ехал на работу на синкансене и думал о проблеме. В какой-то момент он посмотрел в окно и увидел небоскребы с разных сторон от поезда. Глядя на них, можно было точно понять, где и как движется поезд, если знать их расположение. Он вспоминает:
«Я просто увидел это огромное здание и подумал: «А что, если добавить такие маяки на наш код?». Тогда можно было бы не думать об ориентации — система сама бы все определила, да еще и легко отличать код от текста»
Дальше начались бесконечные эксперименты. Какого размера должны быть эти знаки? Хара и его команда попробовали разные соотношения черного и белого (ширину контрастных областей), пытаясь добиться стабильного распознавания. Ничего не получалось.
По легенде, Масахиро Хара додумался до такой компоновки благодаря небоскребам
Тогда Хара поручил просканировать сотни газет и журналов, чтобы найти это оптимальное соотношение. Спустя три месяца удалось обнаружить, что оптимальное соотношение черного и белого, необходимое для QR-кода, составляет 1:1:3:1:1. Если расположить эти «башни» в трех углах, то можно будет легко выделить узор кода на фоне текста и позволить программно понимать, где верх, а где низ.
В 1994 году компания Denso Wave явила свое открытие миру и назвала его QR кодом — сокращение от Quick Response (с англ. «Быстрый отклик»). Состоящий из черных квадратов, расположенных по специальному алгоритму, он стал следующим шагом после UPC кодировки. Например, позволял хранить до 7089 цифр вместо 12 и поддерживал кодирование Рида-Соломона — QR код будет надежно считываться, даже если повредится до 30% его площади.
Самая первая версия QR кода имела размер 21×21 пиксель, а каждая последующая увеличивалась на 4 модуля по горизонтали и вертикали. Сейчас максимальная версия — 40, при которой QR код имеет размер 177×177 пикселей.
Очень кратко о том, как все организовано: точнее, как именно обрабатывается считанная сканером информация.
Все двумерное пространство поделено на области, реализующие алгоритм. Давайте рассмотрим главные на примере самой простой, первой версии QR-кода с размером 21×21 пиксель:
Символ для позиционирования. Тут понятно — важнейшие символы, позволяющие считывать QR код быстро и под разными углами.
5 бит: системная информация. Она определяет две важных вещи:
2 первых бита — это уровень коррекции ошибок, как раз относительно кодировки Рида-Соломона. Может быть 7%, 15%, 25% и 30%.
3 следующих бита — это битовая маска, которая даст 8 возможных комбинаций. Она используется для анализа следующего поля.
Эти 5 бит информации являются частью системной информации (зеленое поле на рисунке) и частично дублируются в других частях. Это дополнительно защищает данные от повреждения.
4 бита: режим. В QR-коде есть 4 основных режима (еще есть FNC1 и ECI, но про них не будем), которые определяются после применения маски из предыдущего шага:
Цифровой: 10 бит на три цифры, до 7089 символов.
Буквенно-цифровой: поддерживаются 10 цифр, буквы от A до Z и несколько спецсимволов. 11 бит на два символа, до 4296 символов.
Байтовый: данные в любой подходящей кодировке (по умолчанию ISO 8859–1), до 2953 символов.
Кандзи: 13 бит на иероглиф, до 1817 символов.
Эта информация показывает заранее, какой тип данных ожидать в следующих полях.
8–10 бит: длина сообщения. В этом поле сканер понимает, сколько конкретно сколько бит необходимо пройти, чтобы ожидать целостное сообщение. Точная длина зависит от режима: например, для числовых данных будет 10 бит (напомним, помещается до 7089 символов), а в байтовом — 8 бит (до 2953 символов).
X бит: сами данные. Данные считываются в строго определенном порядке (обозначены цифрами), в зависимости от направления прохода: снизу, вбок или сверху. Максимальная длина ограничена полем «конец сообщения», а также зависит от уровня коррекции ошибок и версии.
Есть еще несколько полей: например, те самые области, предназначенные для корректировки ошибок. Но их мы рассматривать не будем, как и более продвинутые версии QR кодов, в том числе крошечный Micro QR, прямоугольный rMQR и другие. Рекомендуем ознакомиться со стандартом ГОСТ Р ИСО/МЭК 18004–2015 или посмотреть пример в статье на Хабре с одним миллионом просмотров.
Почему QR код стал настолько массовым
QR код, предложенный Denso Wave, быстро стал стандартом в Toyota и у других автомобильных производителей. Однако никто не ожидал, что его оценят и в других отраслях Японии: например, те же ритейлеры или государственные ведомства. С 1997 года QR код получил с десяток патентов в Японии (в том числе и на технологии сканирования и обработки — Denso Wave занималась и этим тоже), а в 2000 году стал международным стандартом ISO. Его начали применять по всему миру.
Масахиро Хара полагает, что есть три причины такого массового распространения технологии:
1. Скорость. Он работает в несколько раз быстрее по сравнению даже со штрихкодами, несущими меньший объем информации, благодаря описанной выше технологии кодирования и распознавания.
2. Надежность. Еще раз — даже если до 30% QR кода повреждено или не несет значащей информации, остальную часть можно спокойно и так же быстро считать. То есть можно размещать логотипы или другую рекламную информацию прямо внутри.
3. Доступность. На QR код не нужны никакие лицензии, он изначально был открытым проектом. А с середины 2000-х годов, когда появились телефоны с камерами и научились читать QR коды, для бизнеса наступил настоящий рай. Теперь клиенту не надо вводить длинный адрес сайта: навел камеру на визитку, баннер или брошюру и тут же знакомишься с каталогом продуктов или услуг онлайн. При этом не требуется никаких специальных сканеров штрихкодов.
Кстати, после распространения QR кода появились и другие стандарты. Например, двоичный Data Matrix (используется в системе ЕГАИС и «Честный знак»), Aztec (железнодорожные операторы вроде Deutsche Bahn или Trenitalia) и другие. Но все-таки с популярностью QR кодов им не сравнится.
Вот лишь некоторые отрасли, которые сразу приходят в голову, где изобретение Масахиро Хара используется регулярно:
Безналичная оплата. Практически в любом магазине РФ сейчас есть эта функция, как часть системы быстрых платежей (СБП). Открываете раздел «Платежи» в приложении вашего банка, наводите камеру и жмете «Оплатить». Более того: часто продавцы просят использовать именно такой способ оплаты, чтобы снизить комиссию за эквайринг. По QR кодам также можно платить, скажем, за коммуналку или оплату проезда.
Реклама. Кроме уже упомянутых визиток или каталогов, есть и более оригинальные варианты. К примеру, QR коды размещают на крышах зданий, стенах, стаканчиках с кофе и даже на банкнотах — так рекламируется Центральный Банк.
Билеты. Если покупаете билет на поезд, в театр или на футбол, всёе приходит в электронном виде. Можно распечатать или показать QR код на входе прямо с экрана смартфона.
История. Например, в тех же музеях QR коды позволяют не только получить информацию об экспонате, но и даже поучаствовать в виртуальной экскурсии.
Еще можно вспомнить минимум с десяток применений QR кода в повседневной жизни. А как вы обычно им пользуетесь? Делитесь в комментариях!
НЛО прилетело и оставило здесь промокод для читателей нашего блога:
-15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.
