Декодирование

Научные изыскания позволяют нам не только лучше понимать окружающий наш мир, но и контролировать некоторые процессы и явления. За долгие годы исследований и экспериментов мы научились менять свойства материалов, манипулировать электромагнитными полями, видеть далекие планеты и звезды, разбирать по кирпичикам клетки и многое другое. Некоторые новообретенные умения сильно удивили бы ученых прошлого. Одним из таких умений является возможность менять форму луча света. Но как это применить на практике? Ученые из Оттавского университета (Оттава, США) предложили создать обрамленный оптический узел, который можно использовать для хранения и кодирования информации. Как ученые завязывали луч света в узел, каковы свойства такой структуры и насколько безопасно хранить данные на оптических узлах? На эти и другие вопросы мы найдем ответы в докладе ученых. Поехали.

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

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

Как мы прекрасно знаем, любой объект или процесс поддается математическому описанию, и узлы не исключение. С точки зрения математики, узел это вложение окружности в трехмерное евклидово пространство.


Типы простых узлов.

Математическая классификация узлов достаточно обширна (трилистник, печать Соломона, узел Листинга и т.д.). В данном же исследовании был задействован особый вид узлов обрамленный. Такой узел создается из плоской ленты. Грубо говоря, это своего рода запутанная лента Мебиуса.

Вторым компонентом исследования, естественно, был свет, а именно структурированный свет, представляющий собой оптическое поле с определенными пространственными и временными особенностями, которые можно менять. Как напоминают ученые, создание таких структур в основном опирается на концепции, связанные с сингулярной оптикой, т.е. изучение неоднородностей в оптических волновых полях. Неоднородности, которые можно найти в оптических фазах или в поляризации, именуются оптическими сингулярностями. Их можно использовать для создания оптических лучей разной сложности: от лучей с единственной сингулярностью до волновых полей, образующих топологические полосы и узлы.

К числу последних как раз и относится ранее упомянутая лента Мебиуса, а также разные типы узлов. Проблема в том, что подобные структуры часто рассматриваются как двумерные, нежели трехмерные, т.е. как оптические лучи с единственной сингулярностью.

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

Создание оптического обрамленного узла

Узел, как мы уже знаем, это описание того, как запутанные нити/линии/полосы расположены в пространстве. По этой причине при анализе в рамках физической структуры узлы обычно обнаруживаются в полях, определяемых областями, которые однозначно образуют кривые в трехмерном пространстве. Такие узловые кривые были продемонстрированы в таких системах, как вихри в жидкостях, нули интенсивности в скалярных оптических полях и в пределах C-линий оптических полей поляризации.

C-линии, в частности, состоят из кривых чистой круговой поляризации в монохроматических электромагнитных полях. Одна из их самых отличительных особенностей связана со структурой поляризационного поля в непосредственной близости от них. Если точнее, то они заключены в поляризационные эллипсы с большой осью, которая вращается на целые числа, кратные , вдоль замкнутого контура, окружающего C-линию (1а и 1d).


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

В случае параксиальных* оптических лучей поляризация ограничивается плоскостью, поперечной распространению луча, например плоскостью xy.

Параксиальный луч* луч, который распространяется вдоль оси центрированной оптической системы.

Как показано на 1а, это ограничение уменьшает плоскость, в которой можно проследить вращение оси поляризации. Однако непараксиальные лучи могут иметь векторы поляризации, нормаль которых не перпендикулярна распространению луча. Как показано на 1b, этот нормальный вектор, в свою очередь, определяет плоскость, в которой ось эллипса совершает половину оборота вокруг C-линии.

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

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

Учитывая приведенное выше определение, обрамление замкнутой C-линии было определено осью соседнего эллипса поляризации, которого идет перпендикулярно касательной к C-линии.

Данная концепция проиллюстрирована на 1а и 1b, где разными цветами отмечены эллипсы поляризации, окружающие C-линию, ось которой перпендикулярна ее касательной, что и определяет ее обрамление.

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

На 1с показано, что это можно реализовать посредством узлового поля E^k, определяемого циркулярно поляризованной составляющей (E^k_-) с узловыми фазовыми сингулярностями и продольно поляризованной составляющей (E^k_z), гарантирующей, что E^k соответствует уравнениям Максвелла.

Путем наложения E^k на плоскую волну с противоположной спиральностью поляризации (E^p₊) создаются узловые C-линии, возникающие из сингулярной структуры E^k (1d и 1e).

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


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

Например, узел трилистник (2а) может быть выражен как закрытие косы на 2b. Такое представление можно применить и к узлам/косам в трехмерном пространстве. Например, трилистник, внедренный в тор (2c), может быть получен посредством стереографической проекции косы, заключенной в цилиндр (2d).

Один из способов выполнить эту проекцию выразить эту косу как нули комплексного поля. Это поле записывается как функция комплексных координат (u, v), которые относятся к пространственным координатам (x, y, h), в которые коса вложена через u = x + iy и v = exp(ih). Это заплетенное поле, в свою очередь, может быть преобразовано в соответствующий ему узел со стереографической проекцией, определяемой:



где (, , z) цилиндрические координаты трехмерного пространства, в которое теперь вложен узел.

Данная проекция превращает косу, определенную на (x, y, h), в узел в (, , z), соединяя два ее конца, тем самым отображая координату h на .

Вышеупомянутая проекция в значительной степени используется при построении узловых оптических полей. В частности, скалярное оптическое поле может быть построено путем согласования его поля вдоль плоскости z = 0 с полем комплексного узла, возникающего в результате проекции косы. Когда это оптическое поле является параксиальным, то его формулировка в последующих z-плоскостях может быть получена с помощью методов параксиального распространения. Затем этот метод может быть расширен для описания параксиальных узловых C-линий.

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

Также было использовано преобразование координат для кривой, образованной узловой С-линией. Это преобразование эффективно разрезает узел по заданному азимутальному углу и разворачивает его, тем самым сопоставляя координату узла с координатой h пространства. Во время этого процесса обеспечивается локальное сохранение ориентации обрамления узла. На 2е показал узел трилистник до, а на 2f этот же узел после данной процедуры.

Такое преобразование позволило определить определенную информацию касательно узлов (угол закручивания, например). В данном случае угол закручивания состоит из азимутальной ориентации ленты в обрамлении, где нормаль совпадает с касательной к развернутому узлу (2g).

Кодирование информации на узел

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

Метод записи данных основан на паре чисел (, ), где натуральное число, а число, связанное как с , так и с топологической структурой обрамленного узла.



где k обозначает прядь в косе рассматриваемого обрамленного узла, d_k количество полуоборотов вдоль k пряди, демонстрирующей полуоборот (т.е. d_k = если пряди не скручены), p_k простое число, присвоенное k пряди. M = _kd_k состоит из общего числа полуоборотов в обрамлении узла.

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



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

Теоретический пример: Алиса и Боб

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

Это сообщение является результатом работы (выходные данные) программы, обрабатывающей некие входные данные (набор чисел d_k, где k = 1, 2,, n). Ожидается, что запуск программы с таким набором предоставит сообщение Алисы.

Алиса представляет свою программу и ее выходные данные в виде обрамленной косы. Сама операция, выполняемая программой, идентифицируется как последовательность пересечений на планарной диаграмме косы, а исходные данные это количество полуоборотов на прядь. Программа Алисы полностью определена как обрамленная коса с n прядями в виде узловой ленты (К_A).

Предположим, что Алиса не хочет отправлять Бобу оригинал обрамленной косы, а лишь К_A. В таком случае возможно усложнить К_A, тем самым скрыв (зашифровав) оригинальную обрамленную косу.

Следовательно, необходимо выполнить ряд действий. Сначала нужно выбрать натуральное число . Далее определить проекцию обрамленной косы по отношению к К_A. Для этого нужно распределить количество полуоборотов в К_A для разных прядей косы, то есть установить d_k так, чтобы M_A = _kd_k.

Следом необходимо присвоить простые числа p_k прядям, демонстрирующим полуобороты. И наконец определить число согласно формуле 2.

После того как данная процедура завершена, Алиса может отправить Бобу ленту К_A, завязанную узлом, и числа (, ).

Естественно, полученное сообщение необходимо расшифровать. Для этого Боб должен вычислить N_,(M_A), разложение которых на простые множители дает d_k. За счет этого Боб может восстановить оригинал обрамленной косы, которую отправила ему Алиса.


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

Данная операция по обмену данными показана на схеме выше.

Если свести все к простым терминам, то у Алисы есть лента (данные), которая она хочет передать Бобу. Эту ленту можно преобразовать в сложный узел и закодировать исходное состояние, предоставив средства для декодирования исключительно Бобу.

Практические эксперименты

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

Следующим этапом исследования стала практическая реализация приведенного выше теоретического примера. В опыте были использованы параксиально-узловые C-линии, полученные посредством интерферометра Саньяка (4а).

Это устройство разделяет однородно поляризованный световой луч на две ортогонально поляризованные компоненты, каждая из которых модулируется пространственным модулятором света (SLM от spatial light modulator). SLM отображает голограммы, в которых зашифрованы как интенсивность, так и фаза целевого оптического поля.

Одна компонента модулируется для получения пучка с узловыми оптическими вихрями, такими как E^k_- (1c). Вторая компонента модулируется, чтобы сформировать большой гауссов пучок, который равномерно покрывает всю узловую составляющую, тем самым эффективно принимая на себя роль плоской волны E^p₊ (1c).

На выходе из интерферометра два луча когерентно складываются, тем самым преобразуя узловые фазовые вихри E^k_- в параксиально-узловые C-линии. Узел и его обрамление затем можно реконструировать с помощью измерений поляризационной томографии, позволяющих получить профиль поляризации поля.

С помощью данной экспериментальной установки удается получить узлы разных типов: трилистник и печать Соломона (пятилистник). На 4b показаны голограммы, отображаемые на SLM, а также амплитуды и фазы полей, которые они должны создавать.

Фаза поля для узла трилистника и для узла пятилистника представлены следующими формулами:





где масштабированная и безразмерная версия цилиндрической радиальной координаты, азимутальная координата, a, b, s параметры, определяющие форму узла.

Для узла-трилистника рассматривались параметры a = 1, b = 0.5 и s = 1,2, тогда как для узла-пятилистника использовались a = 0.5, b = 0.24 и s = 0.65.


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

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

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

Эпилог

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

Как отмечают сами ученые, ранее подобные структуры (оптические узлы) уже изучались, однако лишь как двумерные системы. В этом же труде их наконец-то рассмотрели как полноценные трехмерные структуры, что позволило куда лучше понять их свойства и возможные варианты применения.

Одним из таких применений является передача зашифрованных данных. Авторы исследования заявляют, что современные технологии позволяют с высокой точностью манипулировать различными параметрами лучей света (интенсивность, фаза, длина волны и т.д.). Возможность менять эти параметры позволяет кодировать и декодировать информацию посредством исключительно оптических методов.

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

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

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

Спасибо, что остаётесь с нами. Вам нравятся наши статьи? Хотите видеть больше интересных материалов? Поддержите нас, оформив заказ или порекомендовав знакомым, облачные 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 раза дешевле в дата-центре Equinix 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 евро за копейки?

Баркод, безусловно, относится к одному из тех изобретений человечества, которые изменили течение нашей жизни. Благодаря появлению штрихового кодирования и его последующей эволюции, многие обыденные действия не только значительно упростились и ускорились, но иногда и приобрели неожиданные формы. В процессе нашей деятельности по разработке и улучшению алгоритмов интеллектуального распознавания документов (IDR) и движка распознавания баркодов Smart BarcodeReader мы постоянно систематизируем знания в предметной области. Понимание того, как развивается технология, позволяет нам совершенствовать наши разработки, делать их более быстрыми, точными и эффективными. Сегодня мы расскажем о том, как эволюционировал (и продолжает эволюционировать) баркод от линейного черно-белого рисунка к многомерной конструкции.



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

Идея кодирования товаров появилась одновременно с идеей организации работы идеального супермаркета, разработанной студентом Гарвардской школы бизнеса Уоллесом Флинтом в начале 1930-х годов. Предложенное техническое решение предполагало, что покупатель самостоятельно формирует перечень покупок на складе, делая проколы в специальной перфокарте покупателя. На кассе эта перфокарта по задумке должна была считываться специальным устройством, товары подавались при помощи специального транспортера, а процесс обслуживания был быстрым и для покупателя, и для продавца. Главная проблема заключалась в том, что на тот период технологии и оборудование для обслуживания подобных процессов практически отсутствовали: ЭВМ, которая требовалась бы для организации считывания и обработки информации подобного класса была бы слишком громоздка и дорога.

Следующий подход к кодированию товарного ассортимента был предпринят в 1948 году, когда аспирантами-энтузиастами из Дрексельского технологического института (США) началась проработка технологии сбора аналитической информации о покупках непосредственно на кассах в супермаркетах на основании маркировки товаров. Тогда группа исследователей создала гибрид технологии оптической звуковой дорожки (optical soundtrack) и азбуки Морзе. В классической технологии оптической звуковой дорожки по краю кинопленки наносится покрытие с неравномерной плотностью. Эта неравномерность приводит к тому, что интенсивность луча проектора, проходящего через него, также изменяется. Эти колебания яркости и преобразуются в звук.

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

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

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

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

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

В конце 60-х годов в США началась разработка универсальной системы нумерации товаров как средства идентификации. Система штрихового кодирования, которую начали применять в торговле, была разработана в 1972 году и получила название UPC Universal Product Code. Штрих-коды этой системы начали присваивать всем видам товаров, производимым и зарегистрированных в США и Канаде. Одноименная организация начала активную пропаганду и внедрение использования штрих-кодов в промышленность и торговлю. Первое историческое считывание штрих-кода стандарта UPC в рознице произошло в американском супермаркете в 1974 году.

С 1977 года в Западной Европе для идентификации потребительских товаров стала применяться аналогичная американской система под названием Европейский артикул (EAN European Article Numbering). Сегодня именно эта ассоциация и занимается распределением штрих-кодов для производителей товаров. Чтобы избежать дублирования номеров, штрих-коды товарам выдаются централизованно международной ассоциацией, включающей 98 организаций из 100 стран мира. Производитель может получить штрих-код для своего товара, предварительно зарегистрировавшись в этой ассоциации.

Штрих-коды семейств UPC и EAN оперируют достаточно небольшим алфавитом, позволяющим закодировать достаточно ограниченный объем информации. UPC, используемый в США, состоит из 12 символов, EAN из 13 цифр и является немного усовершенствованной модификацией кода UPC. Кодирующие символы это вертикальные полосы различной ширины и пробелы между ними. В стандартных линейных кодах зашифрована информация о стране происхождения товара, организации-изготовителе, непосредственно код товара. Для проверки корректности кода в конце размещается контрольная цифра и специальный знак, указывающий на то, что товар производится по лицензии.


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



Штрих-код типа UPC-A код разделен на 2 равные части и отображается в виде темных (штрихов) и светлых (пробелов) полос, которые кодируют 12-значный номер UPC-A. Каждая цифра это уникальный набор из 2 штрихов и 2 пробелов переменной ширины в 1, 2, 3 или 4 модуля (в данном случае минимальная дискретная ширина полосы). При этом общая ширина кодирующих полос для каждой цифры остается неизменной 7 модулей. Таким образом содержательная часть товарного кода UPC-A кодируется в 84 единицах.

Многие задавались вопросом, почему на разных штрих-кодах одинаковые цифры могут быть несколькими разными способами (некоторые даже строили на сей счет конспирологические теории). Делов в том, что алгоритм кодирования штрих-кода не совсем линейный. В правой и левой частях кода цифры кодируются неодинаково: чередование штрихов и пробелов в цифрах происходит по трем наборам последовательностей (A, B и С). В последовательности А темных модулей всегда нечетное количество, в наборах В и С четное. При этом набор В представляет собой инверсию набора а (штрихи заменены пробелами и наоборот), а набор С зеркальное отражение набора В. Знаки символа в числовых наборах А и В всегда начинаются слева со светлого модуля и заканчиваются справа темным модулем, а в числовом наборе С начинаются слева с темного модуля и заканчиваются справа светлым модулем. В левой стороне при кодировании цифр используются наборы А или В в зависимости от позиции цифры в коде, правая сторона кодируется набором C. Алгоритмы кодирования подробно прописаны в стандартах. Например, в этом.

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

Форматы штрих-кодов постоянно совершенствуются и меняются. На сегодняшний день помимо принятых в международном товарообороте стандартных Universal Product Code и European Article Numbering существует более 300 стандартов штрих-кодирования.

С 2005 года принят международный стандарт, в котором используются три основные типа кодирования информации о товарах:

• EAN-8 (сокращённый) кодируется 8 цифр.
• EAN-13 (полный) кодируется 13 цифр (12 значащих + 1 контрольная сумма).
• EAN-128 позволяет кодировать любое количество букв и цифр, объединенных в регламентированные группы.

В отличие от EAN-8 и EAN-13, кодом EAN-128 (GS1-128) используется производителями, перевозчиками и торговыми компаниями для обмена данными о перевозимых грузах. В этом, более длинном коде, может содержаться расширенная информация, такая как номера накладных, индексы пунктов назначения, объемы перевозимого груза, коды товара и серийные номера изделий, сроки годности и пр.

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

Эра 2-D

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

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

В двумерном коде, как и следует из названия, кодирование происходит не по одному направлению, а по двум. Действительно, если расположить несколько одномерных кодов в виде чередующихся фрагментов, получится простейший двумерный код типа Stacked Linear (составной линейный). Если мы упакуем модули в квадрат получится матричный баркод (Matrix).

Пример составного линейного баркода PDF417, появившийся в 1991 году и запатентованный в 1993. Код PDF417 состоит из строк, образуемых словами набором из чередующихся штрихов и пробелов (4 штриха, 4 пробела первое число из названия кода). Общая длина каждого слова 17 модулей (второе число в названии кода).

Помимо собственно содержательных слов, каждая строка состоит из старт-паттерна (крайнего левого набора, ключевых слов (индикаторов они занимают крайние позиции на строке), необходимых для коррекции ошибок, и стоп-паттерна (Впрочем, существует также и так называемый усеченный PDF417 (truncated), где исключен индикатор правой строки и уменьшен шаблон остановки до одной линии. Таким образом, усеченные PDF417 занимают меньше места, но они более восприимчивы к неправильному прочтению. Такой вариант PDF417 используют только там, где риск повреждения изображение кода минимальный). Так как все слова имеют одинаковую длину, размещенные одна под другой строки образуют колонки. В самом коде PDF417 как количество строк, так и количество столбцов может варьироваться: код может содержать от 3 до 90 строк, и иметь ширину от от 3 до 30 столбцов включительно, не считая столбцов со словами индикаторами. Подробная статья про кодирование PDF417 недавно выходила на Хабре здесь, а о возможности его ручного декодирования здесь.



Особенность кода PDF417 заключается в возможности кодировать информацию в текстовом режиме, числовом режиме и режиме данных (байт-режиме).

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

Как и предшественник линейный штрих-код, PDF417 создавался в тот период, когда мобильные телефоны представляли собой устройства чуть меньше чемодана, а о встроенных камерах, пожалуй, даже не задумывались. Поэтому его использование подразумевало наличие специализированных сканеров, предназначенных для считывания такого кода. Это объясняет сложность данного штрих-кода и повышенные требования к разрешению печати.

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

Код в матрице

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

Код Data Matrix

Код DataMatrix был изобретен компанией International Data Matrix в середине 1980-х для программы Space Shuttle, где требовалась маркирровка большого количестко деталей. Data Matrix был разработан до PDF417, а не предшествовал ему, как указывается в некоторых источниках. Важное преимущество кода его компактность и простота нанесения. В настоящее время Data Matrix описывается соответствующими стандартами ISO.



DataMatrix это двумерный штрих-код, который может хранить до 3116 цифр и до 2335 букв. Информация в баркоде Data Matrix кодируется черными и белыми квадратами (модулями) при этом минимальный линейный размер модуля 0.255 мм.

Шаблон поиска (finding pattern) в виде буквы L две сплошные линии на внешней стороне кода Data Matrix.Этот шаблон позволяет сканеру штрих-кода задать изображению правильную ориентацию и считать информацию в правильном порядке.

Второй важный шаблон, необходимый для понимания кода машиной, шаблон синхронизации (clocking pattern, clock track). Он необходим для информирования системы считывания о количестве модулей в матрице и для правильного распознавания сетки, на которой размещены модули.

Зона тишины (quiet zone) это область отделяющая границу штрих-кода от фона и других изображений. Для Data Matrix ширина зоны тишины равна линейному размеру используемого модуля. Маленькие габариты для зоны тишины позволяют минимизировать площадь нанесения Data Matrix на поверхность.

Специфика Data Matrix позволяет читать его как в прямом так и отраженном свете (то есть при использовании инвертированного изображения, при котором светлые модули становятся темными).

Еще одно преимущество Data Matrix, что от квадратные модули могут быть заменены на круглые. Это дополнительно расширяет возможности использования различных технологий нанесения, например в виде тиснения или ударной гравировки. Впрочем, эта же технология замены квадратного модуля на круглый взята на вооружения и в других разновидностях кодов, например в QR-коде.

Стандартизированный код Data Matrix сегодня рассматривается как ключевое звено идентификации и маркировки фармацевтических товаров и медицинских изделий. С 1 июля 2020 года маркировка кодами Data Matrix станет обязательной для всех лекарств, находящихся в обороте в России.

Подробный процесс создания Data Matrix описан здесь.

Код AZTEC

Баркод типа Aztec появился в 1995 году, как пишут, в результате объединения лучших практик разработки баркодов предыдущих поколений. Вид и структура кода Azteс разработана таким образом, чтобы она была одинаково удобна как для нанесения и считывания. Символы в целом квадратные на квадратной сетке с квадратным центральным прицелом из концентрических темных и светлых квадратов типа яблочка мишени (в англоязычных описаниях используется термин bulls eye).

Самый маленький символ Aztec Code имеет площадь 15 x 15 модулей, а самый большой 151 x 151. Самый маленький символ Aztec Code кодирует 13 цифровых или 12 буквенных символов, тогда как самый большой символ Aztec Code кодирует 3832 цифровых или 3067 буквенных символов.



В этом материале мы не ставим своей задачей подробно разбирать каждый код в отдельности, тем более, что про Aztec великолепно написано во всех подробностях на Хабре здесь.

QR-код

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

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

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

В таком QR-коде можно легко закодировать адрес интернет-страницы, которая будет открываться при наведении на нее мобильного телефона:



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



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

Ниже пример QR-кода самой большой размерности, который позволяет закодировать до 1852 символов.



Перечисленные баркоды QR-коды позволяют кодировать цифровые и текстовые данные примерно с одинаковой эффективностью. Согласно сравнению, приведенному на сайте РИТ-сервис, специализирующейся на обработке штрих-кодов, QR-код позволяет кодировать большие объёмы цифровых данных на меньшей площади при одинаковом размере модуля по сравнению с Aztec и Data Matrix кодировать большие объёмы цифровых данных. Код Data Matrix уступает QR коду при кодировании более 88 цифр, Aztec уступает QR-коду при кодировании более 170 цифр. Но по эффективности кодирования текста QR-код значительно уступает Aztec, а Data Matrix превосходит только при объёме текста большем 298 символов. Однако, при кодировании текста набранного прописными (заглавными) буквами эффективности QR-код и Aztec близки, а Data Matrix уступает QR-коду уже при кодировании 88 букв.

Что объединяет все эти коды?

Машине важно понимать, что перед ней код, где находится его начало и конец. Для этого используются зоны тишины, специальные пограничные паттерны и прицелы. Кроме этого, машине необходимо понимать, в каком формате записаны данные, то есть как производить декодирование в виде цифр, цифро-буквенного текста, или в формате данных. Машина также должна иметь возможность скорректировать ошибки, чтобы случайное выпадение нескольких пикселов изображения баркода не приводило к его полной нечитаемости. Коррекция ошибок в кодах DataMatrix, Aztec, QR осуществляется с помощью кодов Рида-Соломона, исправляющих ошибки чтения и позволяющие распознавать данные даже в сильно испорченных кодах (вплоть до 30% поверхности).

Зачем вообще нужны баркоды?

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

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

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

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

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

В чем задача и проблемы распознавания баркодов?

Каждый баркод должен быть распознан. Если он не может быть распознан, то из баркода он превращается в нераспознаваемый художественный орнамент.

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

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

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

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

А что дальше?

Где два измерения, там 3 и 4. В середине 2006 года Японская компания Content Idea of ASIA c гордостью заявили о том, что они изобрели первый в истории 3D-код. В PM-коде (от образовано от paper memory бумажная память ) в качестве третьего измерения к двумерному QR-коду был добавлен цвет. Добавление цветной компоненты, по заявлению изобретателя Татсуи Онода, если в черно белом двумерном QR-коде можно зашифровать 3 кб информации, то в трехмерном до 720 (то есть в 240 раз больше). Вместо ссылки на изображение, используя топологию цветного 3D-кода, можно зашифровать картинку целиком, а также небольшие видео и аудио фрагменты. Технология получила патенты в Японии и Европе. Судя по всему, проект развивался до 2013 года, а к настоящему моменту заморожен или закрыт. Сайт японской компании-изобретателя не обновляется с 2013 года, а скачать приложение в официальных магазинах приложений уже невозможно. (При желании его можно скачать с некоторых зеркал в сети и на размещенных на сайте разработчика образцах посмотреть, как оно работает).



В 2010 году Microsoft пошла дальше объявила о создании новой концепции высокоплотных цветных баркодов (High Capacity Color Barcode (HCCB)), где код был представлен уже в виде той же QR-подобной матрицы, однако в качестве элементов кода выступали не черные квадратные модули, а цветные (4 или 8 цветов) треугольники, каждый из которых занимал ячейки.



Проект HCCB тоже просуществовал до 2013 года: тогда Microsoft объявила о том, что проект не будет поддерживаться и был закрыт в 2015.Недавно в сети появилась информация о том, что Apple разрабатывает новые типы кодов, которые будут доступны в будущих модификациях ОС. Речь идет о круглых баркодах, где информация кодируется в виде 4-х цветных капель размещенных по центру и по периметру круга.

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

Логично предположить, что вслед за кодами с тремя параметрами, последуют четырехмерные коды, динамически изменяющиеся во времени. С точки зрения теории это очень интересные задачи, ставящие вопрос о необходимости одновременной разработки софта, позволяющего распознавать такого рода объекты. И здесь мы подходим к концепции 4D-распознавания, о котором мы расскажем позже.

В качестве послесловия

В 2013 году появилась забавная программа для мобильников Barcode KANOJO, которая декодировала (или делала вид, что декодировала) баркод не совсем привычным способом. Вместо заложенного набора символов на экране мобильного появлялась виртуальная подруга (kanojo) персонаж аниме соответствующая просканированному коду. С ней можно было дружить, завоевывать доверие (и любовь???). Проект просуществовал достаточно недолго, персонажи не генерировались а, скорее всего, просто выбирались из некоторого набора созданных заранее с внешнего сервера данных, который сейчас недоступен.

Привет Хабр.

В настоящее время существует не так уж много стандартов связи, которые с одной стороны, любопытны и интересны, с другой стороны, их описание не занимает 500 страниц в формате PDF. Одним из таких, несложных для декодирования, является сигнал VHF Omni-directional Radio Beacon (VOR), используемый в аэронавигации.


VOR Beacon (с) wikimedia.org

Для начала вопрос читателям как сформировать сигнал так, чтобы с помощью ненаправленной приемной антенны можно было определять направление? Ответ под катом.

Общая информация

Система Very high frequency Omni-directional Range (VOR) используется для аэронавигации еще с 50х годов прошлого века, и состоит из радиомаяков относительно небольшой дальности (100-200 км), работающих в диапазоне частот УКВ 108-117 МГц (частота называется very high frequency вероятно потому, что есть еще маяки NDB, работающие в диапазоне средних волн 400-900 КГц). Размещение направленной антенны на самолете конструктивно неудобно, поэтому возникла задача, как закодировать в самом сигнале информацию о направлении на маяк.

Принцип работы на пальцах можно объяснить следующим образом. Представим, что у нас есть обычный маяк, посылающий узкий луч зеленого света, лампа которого вращается 1 раз в минуту. Очевидно, что раз в минуту мы будем видеть вспышку света, но одна такая вспышка много информации не несет. Добавим к маяку вторую ненаправленную лампу цвета красного цвета, вспыхивающую в момент, когда луч маяка проходит направление на север. Т.к. период вспышек и координаты маяка известны, посчитав задержку между красной и зеленой вспышками, можно узнать азимут на север. Все просто. Осталось сделать то же самое, но с помощью радио. Решено это было с помощью изменения фаз. Для передачи используется два сигнала: фаза первого является постоянной (reference), фаза второго (variable) меняется сложным образом в зависимости от направления излучения каждому углу соответствует свой сдвиг фазы. Таким образом, каждый приемник будет получать сигнал со своим сдвигом фаз, пропорциональным азимуту на маяк. Технология пространственной модуляции осуществляется с помощью специальной антенны (Alford Loop, см КДПВ) и особой, довольно хитрой модуляции. Которая собственно и является темой этой статьи.

Представим, что у нас есть обычный legacy-маяк, работающий с 50х годов, и передающий сигналы в обычной АМ-модуляции азбукой Морзе. Вероятно, когда-то давно, штурман действительно слушал эти сигналы в наушниках и отмечал направления линейкой и циркулем на карте. Мы хотим добавить к сигналу новые функции, но так, чтобы не порушить совместимость со старыми. Тема знакомая, ничто не ново Было сделано следующим образом к АМ сигналу добавили низкочастотный 30 Гц тон, исполняющий функцию reference-phase сигнала, и высокочастотную компоненту, закодированную частотной модуляцией на частоте 9.96 КГц, передающую variable phase сигнал. Выделив два сигнала и сравнив фазы, мы получаем искомый угол от 0 до 360 градусов, который и является нужным азимутом. При этом, всё это не помешает слушать маяк обычным образом и остается совместимым со старыми АМ-приемниками.

Перейдем от теории к практике. Запустим SDR-приемник, выберем модуляцию АМ и ширину полосы 12 КГц. Частоты маяков VOR можно легко найти в сети. На спектре сигнал выглядит следующим образом:



В данном случае сигнал маяка передается на частоте 113.950 МГц. В центре видна легко узнаваемая линия амплитудной модуляции и сигналы азбукой морзе (.- что значит AMS, Амстердам, аэропорт Schiphol). Вокруг на расстоянии 9.6 КГц от несущей видны два пика, передающие второй сигнал.

Запишем сигнал в WAV (не MP3 сжатие с потерями убьет всю структуру сигнала) и откроем его в GNU Radio.

Декодирование

Шаг 1. Откроем файл с записанным сигналом, и применим к нему фильтр низких частот, чтобы получить первый reference-сигнал. Граф GNU Radio показан на рисунке.



Результат: низкочастотный сигнал с частотой 30 Гц.



Шаг 2: декодируем variable phase сигнал. Как говорилось выше, он расположен на частоте 9.96 КГц, нам нужно перенести его на нулевую частоту и подать на FM-демодулятор.

Граф GNU Radio:



Все, задача решена. Мы видим два сигнала, разность фаз которых указывает на угол от приемника до VOR-маяка:



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

К счастью, все это вручную можно не делать: существует уже готовый проект на Python, декодирующий сигналы VOR из WAV-файлов. Собственно, его изучение и вдохновило меня на изучение этой темы.

Желающие могут запустить программу в консоли и получить готовый угол в градусах из уже записанного файла:



Фанаты авиации могут даже сделать себе портативный приемник из RTL-SDR и Raspberry Pi. Кстати, на настоящем самолете данный индикатор выглядит примерно так:


Image www.aopa.org

Заключение

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

Как обычно, всем удачных экспериментов.

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

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

Работу беспилотных авто можно сравнить с уравнением, в котором очень много переменных, которые нужно учесть все без исключения для получения верного результата. Пешеходы, другие авто, качество дорожного покрытия (видимость разделительных полос), целостность систем самого беспилотника и т.д. Многие исследования ученых, провокационные заявления политиков, колкие статьи журналистов базируются на связи между беспилотным автомобилем (далее просто авто или автомобиль) и пешеходом. Это вполне логично, ибо человек и его безопасность должны стоять на первом месте, особенно учитывая непредсказуемость его поведения. Морально-этические споры о том, кто будет виноват, если автомобиль собьет пешехода, выскочившего на дорогу, продолжаются до сих пор.

Однако, если убрать из нашего образного уравнения переменную пешеход, то все равно останется много потенциально опасных факторов. Погода является одним из них. Очевидно, что в плохую погоду (ливень или снежная буря) видимость может снизиться настолько, что порой приходится просто остановиться, ибо ехать нереально. Зрение автомобилей, конечно, сложно сравнить со зрением человека, но их датчики страдают от снижения видимости не меньше нас. С другой стороны у машин есть более широкий арсенал этих датчиков: камеры, радары диапазона миллиметровых волн (MMW), система глобального позиционирования (GPS), гиростабилизатор (IMU), система обнаружение и определение дальности с помощью света (LIDAR) и даже ультразвуковые системы. Несмотря на это многообразие органов чувств, автономные машины все еще слепы во время плохой погоды.

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

При семантической сегментации вместо обнаружения объекта на изображении каждый пиксель классифицируется индивидуально и присваивается классу, который пиксель представляет лучше всего. Другими словами, семантическая сегментация это классификация на уровне пикселей. Классическая семантическая сегментация сверточная нейронная сеть (CNN от convolutional neural network) состоит из кодирующей и декодирующей сетей.

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

Двумя ключевыми компонентами в декодирующих сетях являются так называемые слой MaxUnpooling и слой свертки Transpose. Слой MaxUnpooling (аналог слоя MaxPooling операция пулинга с функцией максимума) необходим для снижения размерности обрабатываемых данных.


Пример операции MaxPooling.

Существует несколько методов распределения значений (т.е. пуллинга), которые имеют общую цель сохранить местоположения максимальных значений в слое MaxPooling и использовать эти местоположения для размещения максимальных значений обратно в совпадающие местоположения в соответствующем слое MaxUnpooling. Этот подход требует, чтобы сеть кодирования-декодирования была симметричной, в которой каждый уровень MaxPooling в кодере имеет соответствующий уровень MaxUnpooling на стороне декодера.

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

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

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

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

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

Третий, но не менее важный, аспект это объединение датчиков. Под этим подразумевается буквальное объединение данных от нескольких датчиков для получения более полной картины и уменьшения вероятных погрешностей и неточностей в данных отдельных датчиков. Существует однородное и неоднородное объединение датчиков. Примером первого может быть использование нескольких спутников для уточнения местоположения по GPS. Примером второго является объединение данных камер, LiDAR и Radar для беспилотных авто.

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


Таблица преимуществ и недостатков датчиков, используемых в беспилотных авто.

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

Сбор данных

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

Для проведения дальнейших работ, включающих расчеты, моделирование и тестирование, необходимо было много данных. Чем больше, тем лучше, говорят сами ученые, и это вполне логично, когда речь идет о работе различных датчиков (камеры, LiDAR и Radar). Среди множества уже существующих наборов данных был выбран DENSE, которые охватывает большую часть необходимых для исследования нюансов.

DENSE также является проектом, нацеленным на решение проблем нахождения пути в суровых погодных условиях. Ученые, работавшие над DENSE, проехали порядка 10000 км по Северной Европе, записывая данные с нескольких камер, нескольких LiDAR, радаров, GPS, IMU, датчиков дорожного трения и тепловизионных камер. Набор полученных данных состоит из 12000 выборок, которые можно разбить на более мелкие подгруппы, описывающие конкретные условия: день+снег, ночь+туман, день+ясно и т.д.

Однако для правильной работы модели необходимо было провести коррекцию данных из DENSE. Исходные изображения камеры в наборе данных имеют размер 1920 х 1024 пикселей, их уменьшили до 480 х 256 для более быстрого обучения и тестирования модели.

Данные LiDAR хранятся в формате массива NumPy, который нужно было преобразовать в изображения, масштабировать (до 480 x 256) и нормализовать.

Данные радара хранятся в файлах JSON, по одному файлу для каждого кадра. Каждый файл содержит словарь обнаруженных объектов и несколько значений для каждого объекта, включая x-координаты, y-координаты, расстояние, скорость и т.д. Такая система координат параллельна плоскости автомобиля. Чтобы преобразовать ее в вертикальную плоскость, нужно учитывать только y-координату.


Изображение 1: проецирование y-координаты на плоскость изображения (слева) и обработанный кадр радара (справа).

Полученные изображения подвергались масштабированию (до 480 x 256) и нормализации.

Разработка CNN модели

Изображение 2: архитектура разработанной CNN модели.

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

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

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

Выходные данные от всех потоков изменяются и объединяются в одномерный вектор, который подключен к сети из трех скрытых слоев с ReLU активацией. Затем данные преобразуются в двумерный массив, который передается в сеть декодирования, состоящую из четырех последовательных этапов MaxUnpooling и транспонированной свертки для повышения дискретизации данных до размера ввода (480x256).

Результаты обучения/тестирования CNN модели

Обучение и тестирование проводились на Google Colab с использованием GPU. Подмножество данных, размеченных вручную, состояло из 1000 выборок данных камеры, LiDAR и радара 800 для обучения и 200 для тестирования.


Изображение 3: потери в обучающих выборках во время фазы обучения.

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


Изображение 4: точность в тестовых выборках во время фазы тестирования.

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

Однако этот показатель не является идеальным. В некоторых случаях определенный класс недостаточно представлен в выборке, от чего точность пикселей будет значительно выше (чем на самом деле) из-за того, что не хватает пикселей для тестирования модели для определенного класса. Посему было решено дополнительно использовать MIoU среднее отношение области пересечения к области объединения.


Визуально представление IoU.

Подобно точности пикселей, точность по IoU вычисляется для каждого кадра, а конечный показатель точности это среднее от этих значений. Однако MIoU рассчитывается для каждого класса отдельно.


Таблица значений точности.


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

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

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

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

Эпилог

Отношение к беспилотным автомобилям неоднозначное. С одной стороны, робомобиль нивелирует такие риски, как человеческий фактор: нетрезвый водитель, лихачество, безответственное отношение к ПДД, малый опыт вождения и т.д. Другими словами, робот не ведет себя как человек. Это хорошо, так ведь? И да, и нет. Во многом автономные транспортные средства превосходят водителей из плоти и крови, но далеко не во всем. Плохая погода тому яркий пример. Человеку, конечно, непросто ехать во время снежной бури, но для беспилотных авто это было практически нереально.

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

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

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

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

Спасибо, что остаётесь с нами. Вам нравятся наши статьи? Хотите видеть больше интересных материалов? Поддержите нас, оформив заказ или порекомендовав знакомым, облачные 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 евро за копейки?