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

В рубриці DOU Labs ми запрошуємо IT-компанії ділитись досвідом власних цікавих розробок та внутрішніх технологічних ініціатив. Питання і заявки на участь надсилайте на  Данный адрес e-mail защищен от спам-ботов, Вам необходимо включить Javascript для его просмотра. .

У цій статті я опишу наш досвід у вирішенні окремого випадку проблем 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 групи:
— Зображення з високою якістю, що можуть легко бути розпізнаними;
— Прийнятні зображення;
— Зображення з низькою якістю.

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

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

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

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

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

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

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