В машинном зрении и робототехнике есть забавный класс задачек: обнаружение заранее известных меток. Сюда можно отнести всё: QR-коды, Augmented Reality ( AR, дополненная реальность), задачи позиционирования объектов (motion capture, определение местоположения), детектирование объектов по меткам, классификация объектов в робототехнике (например при автоматической сортировке), помощь автоматическим системам в позиционировании (роботизированные захваты), трекинг объектов, и.т.д.
В статье описаны основные методы захвата меток, их возможности, границы применимости.
Дальность работы
В первую очередь, до того, как описывать сами методы, введём их краткую классификацию, чтобы в дальнейшем описывать их уже по группам.
Ближняя зона – это зона, в которой возможно детектирование с высоким разрешением, достаточным, чтобы увидеть штрих-код. Средняя зона – где разрешения достаточно для пространственного разделения внешнего контура метки. Дальняя зона – где метка сопоставима с размерами пикселя. Дальнобойные методы можно использовать в ближней и средней зоне.
Методы ближней зоны
Эти методы позволяют не только детектировать метку, но и детектировать достаточно большое количество информации с этой метки. Существенный минус таких методов – требуется высокое разрешение, а значит, метка должна быть крупной. Плюс – автоматическое считывание большого количества информации, иногда это удобно (например, при сортировке посылок).
К методам ближней зоны относится всё разнообразие штрих-кодов, QR-код, Aztec code, MaxiCode, и.т.д. Производить тут сравнение не буду, написано про эту тему много, в том числе на Википедии.
Способы выделения
Первый метод – выделение основных направлений преобразованием Хафа.
Сначала на изображении выделяются все границы. Для изображения строится гистограмма направлений границ. Два главных максимума будут определять пространственную ориентацию метки.
В окрестности обоих максимумов строится преобразование Хафа. В этом преобразовании выделяется 16 главных максимумов, по которым находится уточнённая ориентация паттерна QR-кода, а так же размер строки.
После чего осуществляется натягивание маски QR-кода и точное считывание информации.
Второй метод распространённый в интернете это поиск через каскад Хаара. Метод подробно описан во многих местах, поэтому не буду подробно на нём останавливаться. Обученным каскадом ищется угловая метка QR-кода. После нахождения кандидата ищутся оси симметрии, которые задают ориентацию самого кода.
Третий метод. Берётся набор тестовых прямых, для которых ищутся места, где происходит чередование черного и белого в отношении (1:1:3:1:1). Это отношение справедливо для любого поворота метки.
Места, в которых происходит выделение тестового сегмента, рассматриваются как кандидаты на месторасположение опорных символов QR-кода.
Указанные три метода имеют много вариаций. Существуют и другие методы (в том числе, можно использовать методы, которые будут рассмотрены ниже), но все они менее распространены. Основная цель детектирования штрих-кодов — чтение с них информации. Если информация плохо видна и может не считаться – от метода уже не требуется работоспособность, даже если сам QR-код хорошо виден. Поэтому все методы, заточеные под QR-коды обычно не выделяют положение кода маленького размера, даже если его видно.
Методы средней зоны
Методами средней зоны назовём те методы, где не требуется извлекать информацию из образца, а просто требуется его обнаружение и поиск его ориентации. В последнее время самой популярной задачей такого плана является задача AR (augmented reality). Думаю, что об этом наслышаны уже все. Но, на всякий случай, вот пример работы такой технологии:
Приведённый пример сделан с помощью самого известного AR-фреймворка ARToolKit, доступного под GNU GPL. Он детектирует черные квадраты, в центре которых стоит 1-2 символа. Например такие:
Фреймворк детектирует связанные области тёмного цвета и выполняет для них контурный анализ. Краткое описание принципа его работы уже было на Хабре, не буду его повторять.
Второй по простоте и популярности способ поиска AR-метки это использование SURF /SIFT. При этом шаблоном является не прямоугольник с меткой, а любое изображение.
Про использование SURF в качестве AR-маркера на Хабре тоже была подробная статья.
Минусом обоих методов является необходимость наличия достаточного разрешения. К тому же для обоих алгоритмов достаточно важна априорная оценка того, какого размера будет метка на экране. Например, детекторы границ, используемые в первом методе и настроенные на разные размеры объектов будут выдавать принципиально разные результаты:
Конечно, настроить детектор особенностей, будь то SURF, SIFT, Haar, HOG, или что-то другое, можно на достаточно мелкое изображение (сохраняя возможность детектирования крупной его версии), но тогда работать он будет долго, а ориентацию восстановить будет всё равно невозможно.
Методы дальней зоны
На мой взгляд, приведённые выше методы стары как мир и ничего особенно интересного из себя не представляют. На каждый из них есть тысячи статей, миллионы реализаций. Методы, позволяющие детектирование в дальней зоне, менее известны, имеется меньшее количество OpenSource решений, приходится всегда что-то делать самому.
Классической задачей дальней зоны можно называть motion capture, хотя это лишь наиболее популярное из применений. Метки могут помогать роботам при позиционировании себя на местности, решать задачи AR (например дорисовать дом на местности), следить за объектами, и.т.д. В каком-то смысле даже задача привязки к звёздному небу может считаться задачей детектирования меток.
В первую очередь методы дальней зоны тоже оптические, но не следует забывать и об остальных способах, про которые упомянуто ближе к концу.
Оптическое обнаружение в видеопотоке
Самым простым и дешёвым методом является обнаружение в видеопотоке. Какую метку видно с любого расстояния? Только ярко светящуюся точку. На этом построен весь метод. Есть два способа создавать такие точки: лампочкой и светоотражателем, на который светить лампочкой.
Основная часть алгоритмов в таких системах — это, безусловно, алгоритмы ведения точки и алгоритмы дальнейшей обработки получаемого поля точек. Сами алгоритмы выделения сложности не представляют. Сводятся они обычно к детектированию локальных максимумов. Несколько примеров того, как это можно сделать есть, в этих статьях (1, 2, 3).
Стоит отметить только, что оптические алгоритмы хороши в помещениях и ночью. Днём на солнце лампочка может теряться в тысячах других бликов (в дорогих системах, снимающих тысячи кадров в секунду можно использовать временное кодирование сигнала, для его отделения).
Радиолокационные метки
Перейдём к меткам, не использующим оптику. Начнём с радиодиапазона.
Сюда можно отнести всё: системы с планетарным замахом, GPS, Глонасс — это в конце концов такие же метки. Есть более локальные методы, с зоной действия примерно в город. А простой радиомаяк может быть меткой присутствия объекта в окрестности устройства. При этом его детектирование будет значительно проще и надёжнее, чем детектирование любой из оптических меток.
Звуковые методы
Удивительно, но очень мало информации есть о звуковых метках. Их несложно сделать, они устойчивы к засветке. Конечно, точность не очень высокая, и будет зависеть от базы между приёмниками. Комплектуха для них нужна такая же как для всем известных датчиков расстояния, которые стоят по 2 доллара:
Делается база из нескольких приёмников, а передатчик является меткой. Пару раз сталкивались с задачами, где хотелось бы их использовать, но в итоге шли по более простому пути оптических меток.
Вроде из широко используемых методов ничего не забыл (понятно, что для кодов, AR меток и методов motion capture есть много вариаций). Есть ещё экзотические методы (уголковые светоотражатели для лидаров), но они редки. Если вдруг кому-то придёт в голову что-то ещё, пишите, попробую вставить.
Автор: ZlodeiBaal
