Хабрахабр

Издевательски точный, быстрый и легковесный поиск баркодов через семантическую сегментацию

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

В ходе исследований у нас получилось с помощью сравнительно оригинального подхода искать такие простые объекты весьма точно (мы побили state-of-the-art) и достаточно быстро (real-time на среднем CPU). Баркоды — объекты с достаточно простой структурой. О результатах нашего исследования мы и расскажем в этой статье. Плюс наш детектор очень легкий, имеющий всего 30к весов.

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

Что есть баркод и зачем его искать?

Вы наверняка слышали про штрих-коды и QR-коды — это как раз частные случаи баркодов. Баркоды (Barcodes) — общее название для группы форматов машиночитаемых данных. В современном мире их можно обнаружить на билетах, на товарах в магазине, в официальных документах и во многих других местах.

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

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

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

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

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

Постановка задачи и метрики качества

Что бы нам хотелось от создаваемого детектора баркодов?

  1. Находить все баркоды на изображении достаточно точно*
  2. Находить в том числе длинные и очень узкие баркоды
  3. Real-time на cpu

5. *В качестве основной метрики точности предлагается использовать f-меру по объектам при пороге IoU=0. Также будем смотреть на precision, recall и detection rate.

Формальное определение метрик

Имея истинную ($G$) и предсказанную ($R$) маски объекта, IoU вычисляется как площадь пересечения, деленная на площадь объединения. Для начала введем понятие IoU — Intersection over Union (другое название — Jaccard Index).

$J(G,F) = \frac{|G \cup F|}$

Теперь, основываясь на этой мере, введем понятия precision, recall, f-мера и detection rate. Легко заметить, что IoU принимает значения от 0 до 1.

Установим порог IoU равным некоторому фиксированному числу $t$ (например, 0. Пусть в выборке N объектов. Для некоторого объекта $G$, и детекции $R$ считаем, что если $J(G, R) \ge t$, объект найден (1), иначе считаем, что объект не найден (0). 5). f-мера определяется стандартно как среднее гармоническое $2*precision(t)*recall(t)/(precision(t)+recall(t))$. Тогда $recall(t)$ определяется как доля найденных объектов выборки, $precision(t)$ — доля детекций, соответствующих хотя бы одному объекту выборки.

Пусть в выборке M картинок с объектами. Осталось разобраться с тем, что такое detection rate. Detection rate называется доля картинок, по которым общий IoU всех истинных объектов с общим IoU всех предсказанных объектов больше заданного порога t. Посчитаем IoU между истинными и предсказанными масками по картинке, аналогично отсечем по порогу картинки.

Однако рассмотрим такую ситуацию — пусть на изображении есть один очень большой и один очень маленький объекты, а детектор нашел большой и не нашел маленький. В предыдущих исследованиях (по детектированию баркодов) для оценки качества принято использовать detection rate. В то время как $recall$ будет не больше 0. В таком случае detection rate просигнализирует об ошибке только в случае очень большого порога $t$ близком к 1. То есть для такого примера f-мера может просигнализировать ошибку раньше (в смысле меньшего порога $t$) чем detection rate. 5 при произвольных значениях порога $t$, что также сделает f-меру меньше 1.

Поэтому в своих экспериментах мы опирались на f-меру, а detection rate использовали для сравнения с работами прошлых лет.

Вдохновляемся детекторами текста

Существуют также более поздние версии YOLOv2 и YOLOv3, но в целом данный подход хорош для более-менее квадратных объектов, а вот в нахождении узких, но сильно вытянутых объектов данный подход уже не так силен. Пожалуй, самый известный и популярный детектор объектов в случае, когда важна скорость — YOLO (You Only Look Once).

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

Суть подхода в следующем — давайте решать задачу instance segmentation так:

  1. Для каждого пикселя будем решать задачу бинарной классификации (текст/не текст).
  2. Для каждого пикселя будем предсказывать 8 связей (links) с его соседями. Связь означает, что данная пара пикселей принадлежат одному объекту (instance).
  3. Получив по изображению карту сегментации текст/не текст и карты со связями, соберем граф, в котором вершины будут пикселями, у которых предсказан класс текста, а ребра — линки.
  4. Находим в этом графе связные компоненты.
  5. Вокруг каждой связной компоненты выделяем минимальный охватывающий прямоугольник (например, используя OpenCV), который и будет итоговой детекцией.

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

Данный подход для поиска текста дает достаточно приличные результаты, сравнимые со state-of-the-art.

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

  1. Решаем задачу семантической сегментации — для каждого пикселя определяем класс баркод/не баркод.
  2. Строим граф с вершинами в пикселях, у которых определился тип баркод. В качестве ребер вместо того чтобы искать линки, считаем, что между любой парой соседних пикселей типа баркод есть линк.
  3. Находим связные компоненты в данном графе.
  4. Вокруг каждой связной компоненты выделяем минимальный охватывающий прямоугольник, который и будет итоговой детекцией.

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

Архитектура сети для семантической сегментации

Немного истории, что обычно используют

В U-Net пространственное разрешение сначала постепенно уменьшалось в Encoder, затем постепенно увеличивалось в Decoder, также присутствовали связи (skip connections) из промежуточных признаков Encoder'а в промежуточные признаки Decoder'a. В целом, семантическая сегментация с помощью нейросетей ведет свою историю примерно с 2013 года с появления U-Net. рисунок ниже), которые дали лучшее качество, но требовали больше памяти и вычислений для обработки. Чуть позже появились 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 будет расти экспоненциально (тогда как в случае с обычными свертками он растет линейно).

(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
На рисунке (source) показано экспоненциальное увеличение receptive field нейронной сети при последовательном применении dilated сверток.

В статье этот блок используется поверх сети, которая уже умеет неплохо решать задачу сегментации для уточнения этих предсказаний с помощью информации о контексте. В статье "Multi-Scale Context Aggregation by Dilated Convolutions" на основе этого свойства придуман специальный блок (называемый авторами Context Module), использующийся для сбора информации из контекста текущего пикселя.

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

  1. Downscale Module — начальные свертки для извлечения простейших признаков и уменьшения разрешения.
  2. Context Module — по сути набор dilated сверток, которые быстро увеличат receptive field, таким образом собрав признаки с большего контекста.
  3. Финальный слой (1x1 свертка), получающий карту вероятностей для семантической сегментации баркод/не баркод. Также, в случае если мы хотим различать тип детектируемых баркодов, предсказывается дополнительно N каналов (смотреть далее).

То есть, в полученной архитектуре в каждом слое используется константное небольшое число каналов C=24, первые 3 свертки уменьшают разрешение, последующие свертки (Context Module) наращивает receptive field каждого элемента карты признаков.

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

Тогда мы решили сделать сепарабельными только первые 3 свертки, которые работают с бОльшими разрешениями изображения, и, соответственно, требуют больше вычислений по сравнению с последующими свертками. Изначально мы пробовали сделать все свертки сепарабельными, но от этого качество сильно упало. Итого за счет сепарабельности, нейросеть ускорилась еще на 20%. При этом качество от такой замены упало уже совсем не значительно.

N отвечает за количество различных типов объектов (в нашем случае баркодов), которые мы хотим различать. Остался последний неразъясненный момент — что значит число N в последнем слое. Если же мы все же хотим различать типы баркодов (это баркод типа [такого-то]), то в последнем слое добавляется N каналов, в которых предсказываются вероятности быть какого-то определенного типа. Если же у нас рассматривается простейший случай — когда надо только находить объекты, а определять их тип не надо (это баркод и не важно какой) — можно считать N=0. Теперь, получив детекцию в виде прямоугольника, в котором находится баркод, можно усреднить вероятности классов внутри этого найденного прямоугольника, из чего узнать тип найденного баркода.

Результаты

В целом задача поиска баркодов не пользуется особой популярностью, за последние лет 10 выходило только 1-2 статьи в год (как известно, простейший способ побить state-of-the-art — найти непопулярную задачу, что у нас в итоге и получилось...). Получив какое-то решение, всегда стоит посмотреть вокруг и сравнить качество полученного решения с более ранними исследованиями. В таблице ниже сравнение с другими подходами на двух датасетах, на одном из которых у нас получились лучшие результаты.

Однако главная фишка найденного решения не в точности, а в скорости — по сравнению с тем же YOLO на том же GPU (GTX 1080), причем на большем разрешении изображения, наш метод работает в ~3. Превосходство, конечно, не супер впечатляющее, но все же присутствует. 5 раза быстрее.

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

Заключение

По сути, данная работа основана на двух простых идеях:

  1. Детектирование через семантическую сегментацию.
  2. Использования последовательности dilated сверток с небольшим числом каналов для максимально быстрого наращивания receptive field.

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

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

По результатам экспериментов с баркодами мы написали статью, которая будет представлена на ICDAR2019 в Сиднее.

Литература

  1. Статья с результатами наших экспериментов и большим числом подробностей. Universal Barcode Detector via Semantic Segmentation
  2. Прекрасная обзорная статья про развитие архитектур для семантической сегментации. link
  3. PixelLink: Detecting Scene Text via Instance Segmentation
  4. Статья про использование dilated сверток для улучшения предсказаний с помощью сбора информации из контекста. Multi-Scale Context Aggregation by Dilated Convolutions
    Computer Vision Research Group
Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть