×Закрыть

DOU Labs: як в DevelopEx розв’язали проблему текстового розпізнавання

В рубриці DOU Labs ми запрошуємо IT-компанії ділитись досвідом власних цікавих розробок та внутрішніх технологічних ініціатив. Питання і заявки на участь надсилайте на editors@dou.ua.

У цій статті я опишу наш досвід у вирішенні окремого випадку проблем OCR. Алгоритм має високу точність розпізнавання символів зображення, навіть якщо воно зроблено з поганою якістю. З огляду на обмежений об’єм, детальний розгляд процесу імплементації дещо скорочено, а також спрощено викладення алгоритмічних кроків.

Проблема і підхід до розпізнавання коду

У вкладенні розміщено фотографію пачки сигарет, що містить спеціальний відформатований код (чотири трійки символів, розділених пробілами), яка зазвичай друкується на нижній частині упаковки.

Цей код повинен бути розпізнаний і виданий у вигляді рядка.

Зразки зображень

Шукаючи вирішення проблеми, ми спочатку спробували використати стандартні OCR модулі (наприклад, Tesseract). Проте, в результаті досягнута якість розпізнавання у нашому випадку виявилась недостатньою через низку причин. Так, зображення можуть бути розмитими або оберненими. Позаяк, стандартизовані підходи не використовують додаткову інформацію: формат коду чи сам факт того, що коди друкують спеціальним шрифтом, однаковий для всіх пачок. В результаті, ми вирішили запропонувати наш власний алгоритм.

Наш підхід передбачає поділ рішення на три основних частини.
— Знайти код;
— Виокремити його знаки;
— Розпізнати кожен зі знаків.

Знаходження коду

Ця частина складається з чотирьох кроків:
1) Попередня обробка зображення;
2) Фільтрація шумів і вилучення обмежуючих прямокутників;
3) Визначення кута повороту і можливого розташування коду;
4) Вибір області коду.

Попередня обробка зображення. Цей крок включає перетворення вхідного фото на бінарне зображення. З допомогою OpenCV library ми виконуємо 3 наступних алгоритми:
— Перетворення зображення у формат шкали сірого кольору (cvtColor);
— Нормалізація (normalize);
— Виконання адаптивного порогу Гауса (adaptiveThreshold).

Початкове зображення

Шкала сірого

Нормалізовано

Після виконання адаптивного порогу Гауса (binary image)

Фільтрація шумів і вилучення обмежуючих прямокутників. На цьому етапі ми шукаємо точки сполучення чорних пікселів, використовуючи алгоритм Breadth-First Search. Зону, що містить занадто малу кількість таких точок, слід вважати шумом і, відповідно, вилучити з зображення. Для решти зображення ми виділяємо обмежуючі прямокутники. Прямокутники, які не схожі на форму символу, не будуть прийняті до уваги.

Зображення перед фільтруванням

Відфільтроване зображення з вилученими прямокутниками

Визначення місця повороту і можливого розташування коду. У цій частині алгоритму ми знаходимо групи прямокутників, що або розташовані на одній лінії, або відступають від неї з невеликим відхиленням (кожне зображення має декілька таких груп). За допомогою цих ліній ми прораховуємо ротацію фото (як середній кут всіх ліній). Тоді ми вилучаємо менші зони, кожна з яких містить лінію і відповідний прямокутник.

Група прямокутників з відповідними лініями

Зображення після ротації


Вилучені зони

Відбір зони коду. Завершивши раніше описаний етап, ми отримали кілька зон, одна з яких містить код, що ми шукаємо. Наразі ми приймаємо кожну зону тексту як матрицю, де всі чорні пікселі — одиниці, а білі — 0. Для кожного cтовпчика ми рахуємо сумарну кількість одиниць і позначаємо їх як масив сolumn_sum. Зауважте, що стовпчики, що належать до зон з символами, що не відображаються, мають нижче значення, ніж стовпчики, що є частиною знаків.

Використовуючи вище описане, а також те, що ми можемо прорахувати приблизну ширину трійки символів (можливо те, що показник широти та висоти кожного знака, надрукований шрифтом коду, завжди один і той же), ми можемо визначити зону тексту коду, застосувавши такий алгоритм:
— Для кожного елемента у сolumn_sum виводимо середнє значення в інтервалі з центром на цьому елементі і довжиною, що рівна приблизній широті трійки знака. Позначимо це як новий масив mean_сolumn_sum;
— Для кожного елемента у масиві mean_сolumn_sum приймемо до уваги ті ж інтервали, що й у попередньому кроці. Відбираємо елементи, що мають максимальне значення на відповідних інтервалах. Якщо серед таких елементів ми знаходимо чотири, що розташовані на однаковій дистанції, це означає, що ми знайшли зону з кодом. Також ці чотири елементи відповідають центральним стовпчикам трійки знаків.




Зона вміщує код




Зона без коду

Вилучення знаків

Оскільки розташування центрів та приблизна широта трійок уже відомі, ми можемо вилучити зони, де ці трійки зображені. Потім кожна трійка має бути окремо оброблена. Почнемо з урізання непотрібного місця довкола трійки. Далі, з огляду на те, що всі знаки мають однакову широту, ми можемо визначити, де закінчуються та починаються літери. Таким чином, знаки можуть бути вилучені для подальшого розпізнавання.

Виокремлення знаків із трійки

Розпізнавання коду

На останньому етапі алгоритм працює окремо з кожним знаком, що були отримані у попередній частині. В результаті кожен знак буде розпізнано. Насправді, розпізнавання окремих знаків зображення — досить давня проблема,що стала класичним завданням машинного навчання. Існує кілька рішень, але ми впровадили наш власний простий алгоритм, що включає два кроки:
1) Тренування класифікатора машинного навчання;
2) Розпізнавання знаків.

Тренування класифікатора машинного навчання. На цьому етапі проводиться попередня обробка даних, необхідних для розпізнавання. Для кожного знаку (як букви, так і цифри) ми розробляємо низку сект тренінгу шляхом збору великої кількості зображення. Тренувальний процес має на меті створення «середнього» зображення для кожного знаку.

Розпізнавання знаків. Наразі, коли у нас є «середнє» зображення для кожної літери та цифри, всі знаки вкладеного коду можуть бути розпізнані за допомогою простої hypnotize function:
— Обчислити «помилку» між кожним малюнком і введеним символом зображення;
— Знайти шаблон з мінімальною «помилкою» від вхідного зображення. Символ, який зображений на ньому, і буде тим, який ми шукаємо.

Точність OCR алгоритму

Ми протестували наш алгоритм на близько 200 зображеннях. Всі зображення поділили на 3 групи:
— Зображення з високою якістю, що можуть легко бути розпізнаними;
— Прийнятні зображення;
— Зображення з низькою якістю.

Приклад зображення високої якості

Приклад прийнятного зображення

Приклад зображення низької якості

Алгоритм було протестовано двома різними шляхами. Спочатку було протестовано, чи можливе правильне розпізнавання знаків та підтвердження цілого коду. Якщо принаймні один знак був розпізнаний невірно, весь алгоритм не спрацьовував для розпізнавання коду. Ви можете побачити результат у таблиці, наведеній нижче:

Якість зображення Відсоток розпізнавання цілого коду Відсоток розпізнавання окремих знаків
Висока 72%96%
Прийнятна 42% 88%
Низька 27% 77%

Виконання алгоритму OCR

Спочатку алгоритм був розроблений для портативного промислового сканера на основі Raspberry Pi і роботі з потоком камери в реальному масштабі часу. Так як Raspberry Pi має дуже обмежені обчислювальні ресурси, вимоги продуктивності алгоритму дуже високі. Складність нашого алгоритму — це O(nm), де n — ширина зображення і m — висота зображення в пікселях. Це означає, що кожна частина алгоритму працює швидше (або принаймні не повільніше), ніж зчитування зображення. Ця перевага нашого алгоритму в порівнянні з ковзаючим вікном підходу, який також може бути використаний для виявлення коду.

Стаття написана у співавторстві з моїм колегою Антоном Пугачем.

LinkedIn

25 комментариев

Подписаться на комментарииОтписаться от комментариев Комментарии могут оставлять только пользователи с подтвержденными аккаунтами.

Дуже цікава та реалістична стаття (нарешті на ДОУ).

Так надихнувся вашими результатами що захотілося повторити успіх з можливо іншими алгоритмами.
Але я наштовхнувся на проблемку. На відміну від інших товарів — цигарки не можна просто прийти до магазину на пофоткати. В результаті для утвореня навчальної виботки треба купувати дуже багато цигарок. А я навіть не палю (((

Тому хотів попрохати у вас навчальну виборку або пораду як її можна зібрати.

Дуже вдячний за відповідь.

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

Шкода.

Так чи інакше, дуже вдячний вам і вашому клієнту, якщо він дзволить опублікувати дані.

Достойная статья, спасибо

А какой язык использовали для машинного обучения?

Raspberry Pi
Так что вероятнее всего плюсы, чтобы не сидеть в туче языков.
Но они использовали OpenCV, а у нее биндинги есть под всё. Причем разницы в написании под разные языки 0. Так что можешь юзать любой от жабыскрипта до плюсов, разницы в бытсродействии не заметишь особой. Причем OpenCV умеет и CUDA и OpenCL (c этим правда гемора отгребешь).
А да, у OpenCV есть порт и под Андроид.

Я поняла, а что вы используете для распознания речи?

Я устал от этой области до чертиков и новую математику там я уже не тяну так, как в молодости, так что пытаюсь потиху уйти из нее.
А так вот 3 наиболее используемых движка HTK, Sphinx, Kaldi. Который из них круче, не скажу.
kaldi выглядит очень неплохо, но есть один большой глюк. Дану Пови почему-то тюкнуло в бошку в качестве скриптового движка использовать bash — вот это жесть, как она есть и вечный танец с бубном. Математика у них написана на плюсах и достаточно неплохо, правда некоторые соглашения по написанию кода отдают 80-ми и провоцируют танцы с утечками памяти при использовании. А, еще они фанаты автотулов (так что сборка под разные платформы тоже танцы с бубном). Дока у kaldi тоже очень плохая. За 4 месяца пахача я в деталях kaldi не смог поднять (в деталях, это значит, осуществлять тонкую ее настройку и править их код по необходимости), мне на понимание ее нужно где-то 6-8 месяцев пахача. Но, уверен, что есть много людей, что и за месяц ее поймут.
Но по некоторым тестам у kaldi качество распознавания получше, что у HTK, Sphinx.
Ну и для Андроида ты можешь использовать гугловский движок.

Ви кажете, що весь код розпізнається десь 27-72% випадків. Це для статичного зображення. Чи вдалося покращити результати під час аналізу відеопотоку?

Для статических изображений.

Добра стаття, дякую. Прикладне рішення з досить простою але вірною механікою. Як вирішуєте можливість зустрічі коду з трьох символів I чи l у шукомій четвірці символів, а також можливість зустріти 11.11 в полі з датою? Наскльки я розумію їх матричний слід буде досить схожим.

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

Congrats !

Ой спасибо, отдохнул душой читая нормальную статью.

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

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

Возможно и очередной велосипед. Но перед тем как его изобретать были опробованы самые разные велосипеды от шоссейников до фетбайков. К сожалению, ни один не подошел под наш кейз. Если знаете такой поделитесь ссылкой )

Може це і велосипед.
Але колись в мене була дещо схожа задача, і наче ж методи всі ті ж самі і відомі, але зібрати все до купи і змусити розпізнавати з солідною якістю — капець не просто.
Тоді мені така стаття була б корисною.
Так що автори молодці, хоч і не використовують cutting edge підходів на сьогодні.

Иногда лучше свой велосипед, чем на шоссейнике ездить по горам.

О, приличная статья на ДОУ. Конечно ничего супер-пупер-крутого, но приятно такое читать.
Было бф интересно еще послушать, что-нибудь дополнительно для низкокачественных изображений делали?
В общем спасибо за такую статью.

Зону, що містить занадто малу кількість таких точок, слід вважати шумом
А якщо шрифт не буде товстим і літери фрагментуються на ланцюжки груп пікселів?

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

Не хватает ссылки на гитхаб ))

Зачем? В деталях же всё написано. Повторить элементарно. Ну и немного повозиться, понятно придется, но так хоть понимать детальнее будешь.

Подписаться на комментарии