Алгоритм распознавания ценников, который работает даже на терминалах сбора данных +5


Привет, Хабр! Сегодня мы продолжаем нашу классическую серию статей про то, как с использованием методов обработки изображений и распознавания образов сделать что-то полезное с практической точки зрения. Сегодня речь пойдет о задаче распознавания ценников. Обычных ценников товаров, которые каждый может встретить в любом магазине. Только для обеспечения должной практичности мы добавим важное требование в постановку задачи: распознаваемые изображения получают при помощи малоформатной цифровой камеры, а вычислительное устройство имеет существенные ограничения по ресурсам. Другими словами, мы расскажем, как распознавать ценники на вычислительно слабом мобильном устройстве (кстати, здесь речь идет не столько о дешевом китайском смартфоне, сколько о специальных промышленных терминалах сбора данных, которые в силу ряда причин тоже обладают достаточно слабыми “мозгами”). Итак, если Вам интересна тема автоматизации ритейла, добро пожаловать под кат!



 


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


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


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


В сегодняшней статье на Хабре мы расскажем про вычислительно эффективный поиск, локализацию и распознавание цены на изображении ценника. Как и обещали, будет рассмотрен практически значимый вариант постановки задачи: когда для распознавания ценников используется вычислитель уровня Odroid XU4 (доступный для исследователей одноплатный компьютер, который по вычислительным характеристикам немного уступает терминалам Honeywell) при условии существенных ограничений на параметры съемки. В сегодняшней статье сконцентрируемся только на распознавании retail-цены, а не других элементов ценника.


Особенности задачи распознавания ценников


Рассмотрим особенности поставленной задачи:


  1. Ценник занимает большую часть кадра.
  2. Ценник подчиняется определенным правилам заполнения (формату) с незначительным варьированием.
  3. Размеры поступающих изображений отклоняются от заданных незначительно.
  4. Изображение ценника приходит с камеры смартфона или фронтальной камеры роботизированной платформы.
  5. Отсутствие ответа лучше, чем неверный ответ. Это вызвано возможными потерями при использовании неверного ответа: печать ненужных новых ценников, неверное ценообразование, лишние действия персонала.

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


  1. Наличие бликов
  2. Размытые и не очень четкие изображения
  3. Наличие шумов на изображении
  4. Окружение вокруг ценника: разные дополнительные акционные бирки или сложный фон из-за товаров позади.
  5. Наклон изображения

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


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





 


Алгоритм распознавания ценников


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



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


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


Неравномерное освещение протяженных объектов в сцене приводит к неравномерной яркости их прообразов на изображении. Для компенсации неравномерности было решено использовать алгоритм локальной бинаризации Ниблэка.


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


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


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



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


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


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



После ветвления на каждом изображении вычисляются 8-связные компоненты связности. После этого они анализируются в два этапа.


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



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


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



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


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


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


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



 


Тестирование


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


В датасете присутствовало 708 изображений, из которых 29 не имели корректных изображений ценников (далее корректные изображения). Среди корректных 679: ~80 были повернуты, ~90 затемнены, ~150 имели низкий контраст, ~ 40 имели наложения и 50 размыты. Размеры изображений распределены в пределах от 1350x700 до 800x400.


Тестирование было произведено как на только корректных изображениях, так и на полном датасете.


Качество оценивалось по следующим показателям:


  • True Positive (TP) — количество корректных изображений, на которых правильно найдена зона цены,
  • True Negative (TN) — количество некорректных изображений, которые были забракованы,
  • False Positive (FP) — количество корректных изображений, на которых зона была найдена неправильно, и количество некорректных изображений, на которых было что-то (ошибочно) найдено,
  • False Negative (FN) — количество корректных изображений, которые были забракованы.

Вот результаты детекции ценников на корректных изображениях:


Total TP, # TP, % TN, # TN, % FP, # FP, % FN, # FN, % Precision, % Recall, % Accuracy, %
679 664 97.8 0 0.000 13 1.9 2 0.3 98.1 99.7 97.8

Вот результаты детекции ценников на всем тестовом наборе данных:


Total TP, # TP, % TN, # TN, % FP, # FP, % FN, # FN, % Precision, % Recall, % Accuracy, %
708 664 93.8 15 2.1 27 3.8 2 0.3 96.1 99.7 95.9

А вот результаты распознавания цены для корректно найденных зон:


Correct zone found Correct value Correct value, %
664 650 97.9

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


Не забываем про время работы алгоритма: среднее время распознавания изображения от подачи на вход алгоритму до получения значения цены — 162 миллисекунды на целевом Odroid-XU4 в однопоточном режиме.


Заключение


Несмотря ни на какие катаклизмы и вирусы, у магазинов будут клиенты и деньги. А значит, всегда будут желающие заработать на автоматизации ритейла. При этом ритейл является одной из самых жадных до автоматизации и сокращению расходов отраслей экономики — другими словами, при автоматизации перед ритейлом стоит задача начать зарабатывать на вложенном уже сегодня (максимум завтра). И, конечно, удовлетворить запрос на интеллектуальную автоматизацию бизнес-процессов ритейлу готовы большое количество программистов/студентов/стартаперов (нужное подчеркнуть), которые предлагают “прототипы алгоритмов”. Большое количество разработчиков таких “помогающих” ритейлу (и не только ему) систем объясняется очевидной доступностью инструментов обучения нейронных сетей и машинного обучения. При этом у лиц, принимающих решения о внедрении в ритейле, уже есть понимание того, что работа прототипа в “лабораторных условиях” далеко не всегда гарантирует, что даже за существенные деньги он может быть доведен до требуемых показателей качества. Спасибо за внимание.




К сожалению, не доступен сервер mySQL