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

в 12:09, , рубрики: ABBYY, barcode, neural networks, object detection, Блог компании ABBYY, искусственный интеллект, машинное обучение, нейросети, обработка изображений

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Итак, мы определились с общей схемой решения. Пункты 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 свертке, т.к. в итоговом решении мы будем полагаться на ее свойства.

Обычная свертка работает примерно так

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

В то время как dilated свертка изображена ниже (на изображении dilated фактор равен 2)

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

Можно заметить что обычная свертка на самом деле является частным случаем dilated свертки (с dilation фактором 1).

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

Если бы все было так просто...

Главное требование к нашей нейросети, помимо качества, — скорость. В наших данных встречаются баркоды настолько мелкие относительно размера изображения, что минимальное разрешение, на котором имеет смысл запускать нейросеть, должно быть хотя бы 512x512, а лучше 1024х1024. При этом есть требование работать на CPU не больше 100 мс на изображении (причем еще и на одном ядре!). По совокупности требований ко входному разрешению и общему времени работы задача выходит весьма не тривиальной. При таких жестких ограничениях использование сильных, глубоких архитектур не представляется возможным. Справедливости ради, требование про 100 мс на одном ядре мы так и не выполнили, но итоговое решение работает 40 мс на 4х ядрах (Intel Core i5, 3.2 ГГц).

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

Вдохновляемся Context Aggregation Network

У dilated сверток имеется следующее полезное свойство — если применить их последовательно с экспоненциально возрастающим dilated фактором, receptive field будет расти экспоненциально (тогда как в случае с обычными свертками он растет линейно).

Издевательски точный, быстрый и легковесный поиск баркодов через семантическую сегментацию - 21
На рисунке (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, но использовать его не для улучшения предсказаний уже имеющейся хорошей модели, а в качестве основной части сверточной сети, которая и будет решать эту проблему. В целом же, наша архитектура устроена следующим образом (см. таблицу):

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

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

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

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

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

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

Результаты

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

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

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

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

Помимо преимущества в скорости, есть и преимущество в весе итоговой модели. Детектор имеет ~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

Автор: ABBYYTeam

Источник


* - обязательные к заполнению поля