Поиск объектов на изображениях? Имея обучающую выборку и минимальный набор знаний о нейросетях, любой студент сегодня может получить решение определенной точности. Однако большинство нейросетей, использующихся для решения этой задачи, достаточно глубокие, а соответственно, требуют много данных для обучения, сравнительно медленно работают на этапе inference (особенно если на устройстве отсутствует GPU), много весят и достаточно энергозатратны. Все вышеперечисленное может быть весьма критично в определенных случаях, в первую очередь, для мобильных приложений.
Баркоды — объекты с достаточно простой структурой. В ходе исследований у нас получилось с помощью сравнительно оригинального подхода искать такие простые объекты весьма точно (мы побили state-of-the-art) и достаточно быстро (real-time на среднем CPU). Плюс наш детектор очень легкий, имеющий всего 30к весов. О результатах нашего исследования мы и расскажем в этой статье.
Но прежде чем говорить о решении, стоит все же немного погрузиться в предметную область, и начать, пожалуй, стоит с того, что такое баркоды.
Что есть баркод и зачем его искать?
Баркоды (Barcodes) — общее название для группы форматов машиночитаемых данных. Вы наверняка слышали про штрих-коды и QR-коды — это как раз частные случаи баркодов. В современном мире их можно обнаружить на билетах, на товарах в магазине, в официальных документах и во многих других местах.
Баркоды принято разделять на одномерные, представленные набором черных и белых полос, и двумерные, состоящие из мелких квадратных или прямоугольных блоков. Как можно видеть на рисунке, в целом различные типы весьма похожи между собой.
Сложность могут представлять баркоды некоторых типов, у которых не специфицирована длина. Подобные баркоды могут быть сколь угодно длинными и при этом очень тонкими.
Пример выше искусственный, однако баркоды с аналогичными пропорциями встречаются в реальных документах, в частности в инвойсах.
И раз уж это машиночитаемые форматы, они должны сравнительно легко распознаваться аппаратурой. Однако первый шаг на пути к распознаванию — это поиск, и именно о нем и пойдет речь в данной статье.
Стоит отметить, что лазерные сканеры и многие приложения подразумевают активное участие человека — требуется явно навести камеру/сканер на баркод, дабы тот распознался, в таком случае необходимость в поиске, естественно, отпадает. Однако в данном сценарии пользователи вынуждены затрачивать дополнительные усилия со своей стороны, что не есть хорошо. Такой подход также не позволяет распознавать несколько объектов на изображении, ограничиваясь только одним.
Постановка задачи и метрики качества
Что бы нам хотелось от создаваемого детектора баркодов?
- Находить все баркоды на изображении достаточно точно*
- Находить в том числе длинные и очень узкие баркоды
- Real-time на cpu
*В качестве основной метрики точности предлагается использовать f-меру по объектам при пороге IoU=0.5. Также будем смотреть на precision, recall и detection rate.
Для начала введем понятие IoU — Intersection over Union (другое название — Jaccard Index). Имея истинную (
) и предсказанную (
) маски объекта, IoU вычисляется как площадь пересечения, деленная на площадь объединения.
Легко заметить, что IoU принимает значения от 0 до 1. Теперь, основываясь на этой мере, введем понятия precision, recall, f-мера и detection rate.
Пусть в выборке N объектов. Установим порог IoU равным некоторому фиксированному числу 
(например, 0.5). Для некоторого объекта 
, и детекции 
считаем, что если 
, объект найден (1), иначе считаем, что объект не найден (0). Тогда 
определяется как доля найденных объектов выборки, 
— доля детекций, соответствующих хотя бы одному объекту выборки. f-мера определяется стандартно как среднее гармоническое 
.
Осталось разобраться с тем, что такое detection rate. Пусть в выборке M картинок с объектами. Посчитаем IoU между истинными и предсказанными масками по картинке, аналогично отсечем по порогу картинки. Detection rate называется доля картинок, по которым общий IoU всех истинных объектов с общим IoU всех предсказанных объектов больше заданного порога t.
В предыдущих исследованиях (по детектированию баркодов) для оценки качества принято использовать detection rate. Однако рассмотрим такую ситуацию — пусть на изображении есть один очень большой и один очень маленький объекты, а детектор нашел большой и не нашел маленький. В таком случае detection rate просигнализирует об ошибке только в случае очень большого порога 
близком к 1. В то время как 
будет не больше 0.5 при произвольных значениях порога 
, что также сделает f-меру меньше 1. То есть для такого примера f-мера может просигнализировать ошибку раньше (в смысле меньшего порога 
) чем detection rate.
Поэтому в своих экспериментах мы опирались на f-меру, а detection rate использовали для сравнения с работами прошлых лет.
Вдохновляемся детекторами текста
Пожалуй, самый известный и популярный детектор объектов в случае, когда важна скорость — YOLO (You Only Look Once). Существуют также более поздние версии YOLOv2 и YOLOv3, но в целом данный подход хорош для более-менее квадратных объектов, а вот в нахождении узких, но сильно вытянутых объектов данный подход уже не так силен.
Так что мы решили пойти другим путем. Как легко заметить, строчки с текстом на изображении также весьма вытянутые и узкие, а задача поиска текста на изображениях в научном сообществе достаточно популярна (уж точно популярнее поиска баркодов) и для нее придуманы различные интересные архитектуры, основанные на графовой структуре. Наше решение мотивировано как раз одной из работ по поиску текста, в которой предложена архитектура PixelLink.
PixelLink для поиска текста
Суть подхода в следующем — давайте решать задачу instance segmentation так:
- Для каждого пикселя будем решать задачу бинарной классификации (текст/не текст).
- Для каждого пикселя будем предсказывать 8 связей (links) с его соседями. Связь означает, что данная пара пикселей принадлежат одному объекту (instance).
- Получив по изображению карту сегментации текст/не текст и карты со связями, соберем граф, в котором вершины будут пикселями, у которых предсказан класс текста, а ребра — линки.
- Находим в этом графе связные компоненты.
- Вокруг каждой связной компоненты выделяем минимальный охватывающий прямоугольник (например, используя OpenCV), который и будет итоговой детекцией.
Данный процесс наглядно изображен на схеме, рисунок взят из оригинальной статьи.
Данный подход для поиска текста дает достаточно приличные результаты, сравнимые со state-of-the-art.
PixelLink для поиска баркодов
Возвращаемся теперь к баркодам. Мы задались вопросом — а так ли нам нужны эти линки? Ведь баркоды, в отличие от текста, в подавляющем большинстве случаев находятся далеко друг от друга. Да и вообще по спецификации у многих типов баркодов обязательно должен быть некий зазор до ближайших соседних объектов.
В общем мы решили, что линки нам особо не нужны, и модифицировали подход следующим образом:
- Решаем задачу семантической сегментации — для каждого пикселя определяем класс баркод/не баркод.
- Строим граф с вершинами в пикселях, у которых определился тип баркод. В качестве ребер вместо того чтобы искать линки, считаем, что между любой парой соседних пикселей типа баркод есть линк.
- Находим связные компоненты в данном графе.
- Вокруг каждой связной компоненты выделяем минимальный охватывающий прямоугольник, который и будет итоговой детекцией.
Итак, мы определились с общей схемой решения. Пункты 2-4 можно считать тривиальными, а вот как именно справиться с семантической сегментацией, давайте обсудим далее.
Архитектура сети для семантической сегментации
Немного истории, что обычно используют
В целом, семантическая сегментация с помощью нейросетей ведет свою историю примерно с 2013 года с появления U-Net. В U-Net пространственное разрешение сначала постепенно уменьшалось в Encoder, затем постепенно увеличивалось в Decoder, также присутствовали связи (skip connections) из промежуточных признаков Encoder'а в промежуточные признаки Decoder'a. Чуть позже появились dilated свертки (см. рисунок ниже), которые дали лучшее качество, но требовали больше памяти и вычислений для обработки. Ну и, в конце концов, появился подход, известный как Deeplabv3+, комбинирующий оба эти подхода и являющийся state-of-the-art среди human-designed архитектур на момент написания этой статьи (на самом деле, благодаря Neural Architecture Search, уже были получены более эффективные решения, например).
Остановимся немного подробнее на dilated свертке, т.к. в итоговом решении мы будем полагаться на ее свойства.
Обычная свертка работает примерно так
В то время как dilated свертка изображена ниже (на изображении dilated фактор равен 2)
Можно заметить что обычная свертка на самом деле является частным случаем dilated свертки (с dilation фактором 1).
Вообще обсуждение решений для семантической сегментации — тема для отдельной немаленькой статьи, я лишь хотел сделать небольшое напоминание, в котором самое важное — разобраться с устройством dilated свертки. Если вы плохо знакомы с семантической сегментацией, здесь лучший известный автору обзор, впрочем, для понимания того, что будет происходить дальше, ознакомление с ним не обязательно.
Если бы все было так просто...
Главное требование к нашей нейросети, помимо качества, — скорость. В наших данных встречаются баркоды настолько мелкие относительно размера изображения, что минимальное разрешение, на котором имеет смысл запускать нейросеть, должно быть хотя бы 512x512, а лучше 1024х1024. При этом есть требование работать на CPU не больше 100 мс на изображении (причем еще и на одном ядре!). По совокупности требований ко входному разрешению и общему времени работы задача выходит весьма не тривиальной. При таких жестких ограничениях использование сильных, глубоких архитектур не представляется возможным. Справедливости ради, требование про 100 мс на одном ядре мы так и не выполнили, но итоговое решение работает 40 мс на 4х ядрах (Intel Core i5, 3.2 ГГц).
К сожалению, все известные нам архитектуры для семантической сегментации категорически не укладывались в данные ограничения. Так что перед нами стоял выбор: или неизвестно как придумывать что-то совсем новое, или попытаться максимально упростить одну из популярных архитектур. Гениальных идей у нас не появилось, так что мы выбрали последнее.
Вдохновляемся Context Aggregation Network
У dilated сверток имеется следующее полезное свойство — если применить их последовательно с экспоненциально возрастающим dilated фактором, receptive field будет расти экспоненциально (тогда как в случае с обычными свертками он растет линейно).
На рисунке (source) показано экспоненциальное увеличение receptive field нейронной сети при последовательном применении dilated сверток. (a) F1 получается из F0 применением свертки с dilation=1, receptive field = 3x3 для каждого элемента в F1 (b) F2 получается из F1 применением свертки с dilation=2, receptive field = 7x7 для каждого элемента в F2 (c ) F3 получается из F2 применением свертки с dilation=4, receptive field = 15x15 для каждого элемента в F3
В статье "Multi-Scale Context Aggregation by Dilated Convolutions" на основе этого свойства придуман специальный блок (называемый авторами Context Module), использующийся для сбора информации из контекста текущего пикселя. В статье этот блок используется поверх сети, которая уже умеет неплохо решать задачу сегментации для уточнения этих предсказаний с помощью информации о контексте.
Мы решили взять этот Context Module, но использовать его не для улучшения предсказаний уже имеющейся хорошей модели, а в качестве основной части сверточной сети, которая и будет решать эту проблему. В целом же, наша архитектура устроена следующим образом (см. таблицу):
- Downscale Module — начальные свертки для извлечения простейших признаков и уменьшения разрешения.
- Context Module — по сути набор dilated сверток, которые быстро увеличат receptive field, таким образом собрав признаки с большего контекста.
- Финальный слой (1x1 свертка), получающий карту вероятностей для семантической сегментации баркод/не баркод. Также, в случае если мы хотим различать тип детектируемых баркодов, предсказывается дополнительно N каналов (смотреть далее).
То есть, в полученной архитектуре в каждом слое используется константное небольшое число каналов C=24, первые 3 свертки уменьшают разрешение, последующие свертки (Context Module) наращивает receptive field каждого элемента карты признаков.
В таблице гиперпараметров архитектуры, помимо прочего, указано, является ли свертка на текущем слое сепарабельной. Сепарабельные свертки теоретически дают ускорение порядка k^2 раз по сравнению с обычной сверткой, где k — размер фильтра. На практике ускорение может быть намного меньше (все зависит от разрешения изображения, количества входных и выходных фильтров).
Изначально мы пробовали сделать все свертки сепарабельными, но от этого качество сильно упало. Тогда мы решили сделать сепарабельными только первые 3 свертки, которые работают с бОльшими разрешениями изображения, и, соответственно, требуют больше вычислений по сравнению с последующими свертками. При этом качество от такой замены упало уже совсем не значительно. Итого за счет сепарабельности, нейросеть ускорилась еще на 20%.
Остался последний неразъясненный момент — что значит число N в последнем слое. N отвечает за количество различных типов объектов (в нашем случае баркодов), которые мы хотим различать. Если же у нас рассматривается простейший случай — когда надо только находить объекты, а определять их тип не надо (это баркод и не важно какой) — можно считать N=0. Если же мы все же хотим различать типы баркодов (это баркод типа [такого-то]), то в последнем слое добавляется N каналов, в которых предсказываются вероятности быть какого-то определенного типа. Теперь, получив детекцию в виде прямоугольника, в котором находится баркод, можно усреднить вероятности классов внутри этого найденного прямоугольника, из чего узнать тип найденного баркода.
Результаты
Получив какое-то решение, всегда стоит посмотреть вокруг и сравнить качество полученного решения с более ранними исследованиями. В целом задача поиска баркодов не пользуется особой популярностью, за последние лет 10 выходило только 1-2 статьи в год (как известно, простейший способ побить state-of-the-art — найти непопулярную задачу, что у нас в итоге и получилось...). В таблице ниже сравнение с другими подходами на двух датасетах, на одном из которых у нас получились лучшие результаты.
Превосходство, конечно, не супер впечатляющее, но все же присутствует. Однако главная фишка найденного решения не в точности, а в скорости — по сравнению с тем же YOLO на том же GPU (GTX 1080), причем на большем разрешении изображения, наш метод работает в ~3.5 раза быстрее.
Помимо преимущества в скорости, есть и преимущество в весе итоговой модели. Детектор имеет ~30 тысяч весов, в то время как подавляющее большинство современных сверточных сетей (даже заточенных под мобильные устройства) имеют миллионы параметров. Итоговое решение весит даже меньше LeNet, который имел ~60 тысяч параметров.
Заключение
По сути, данная работа основана на двух простых идеях:
- Детектирование через семантическую сегментацию.
- Использования последовательности dilated сверток с небольшим числом каналов для максимально быстрого наращивания receptive field.
В результате была получена очень легкая и быстрая архитектура, тем не менее показывающая вполне достойные результаты (и даже побившая SOTA в непопулярной задаче поиска баркодов). Кроме того, применение данного подхода не ограничивается баркодами. Мы использовали эту же архитектуру для нахождения текста, поиска визиток и паспортов, получив хорошие результаты и для этих задач.
Стоит, тем не менее, отметить, что данный подход в таком виде имеет ограничения. Если совсем рядом находятся 2 объекта одного типа, они будут слипаться в один. Возможно, в следующих сериях, мы расскажем, как бороться с такой проблемой.
По результатам экспериментов с баркодами мы написали статью, которая будет представлена на ICDAR2019 в Сиднее.
Литература
- Статья с результатами наших экспериментов и большим числом подробностей. Universal Barcode Detector via Semantic Segmentation
- Прекрасная обзорная статья про развитие архитектур для семантической сегментации. link
- PixelLink: Detecting Scene Text via Instance Segmentation
- Статья про использование dilated сверток для улучшения предсказаний с помощью сбора информации из контекста. Multi-Scale Context Aggregation by Dilated Convolutions
Computer Vision Research Group
Автор: ABBYYTeam
