Розпізнавання тексту в ABBYY FineReader

    Систему розпізнавання тексту в FineReader можна описати дуже просто.
 
У нас є сторінка з текстом, ми розбираємо її на текстові блоки, потім блоки розбираємо на окремі рядки, рядки на слова, слова на літери, літери розпізнаємо, далі по ланцюжку збираємо все назад в текст сторінки.
 
 
 
Виглядає дуже просто, але диявол, як завжди, криється в деталях.
 
Про рівень від документа до рядка тексту поговоримо як-небудь наступного разу. Це велика система, в якій є багато своїх складнощів. В якості деякого введення, мабуть, можна залишити тут ось таку ілюстрацію до алгоритму виділення рядків.
 
 
 
У цій статті ми почнемо розповідь про розпізнавання тексту від рівня рядка і нижче.
 
Невелике попередження: система розпізнавання FineReader — дуже велика і постійно допрацьовується протягом багатьох років. Описувати цю систему цілком з усіма її нюансами, по-перше, краще кодом, а по-друге, — займе дуже-дуже багато місця. Тому до того, що тут описано, рекомендуємо ставитися як до якоїсь дуже узагальненої теорії, що стоїть за практичною системою. Тобто загальні ідеї та напрямки в технології приблизно схожі на правду, але щоб зрозуміти до дрібниць, що ж там на практиці відбувається, краще не читати цю статтю, а працювати у нас над розробкою цієї системи.
 
 

Граф лінійного поділу

Отже, у нас є чорно-біле зображення рядки тексту. Насправді зображення, звичайно, сіре або кольорове, а чорно-білим стає після бінаризації (про бінаризації теж потрібно писати окрему статтю, а поки частково може допомогти <a href = "www.google.com/ # q = text + binarization "> ось це .
 
Так от, нехай у нас є чорно-біле зображення рядки тексту. Нам потрібно його поділити на слова, а слова на символи для розпізнавання. Базова ідея, як звичайно, очевидна — шукаємо на зображенні рядки вертикальні білі просвіти, а далі кластерізуем їх по ширині: широкі просвіти — це пропуски між словами, вузькі — між символами.
 
 
 
Ідея чудова, але в реальному житті ширина прогалин може бути дуже неоднозначним показником, наприклад, для тексту з нахилом або невдалого поєднання символів або злиплих тексту.
 
 
 
Рішень у проблеми, загалом, два. Рішення перше — вважати якусь «видиму» ширину присвятив. Людина може практично будь-який текст, навіть незнайомою мовою, точно поділити на слова, а слова на символи. Це відбувається тому, що мозок фіксує не вертикальне відстань між символами, а якийсь видимий обсяг порожнього простору між ними. Рішення хороше і ми його, звичайно, використовуємо, тільки працює воно не завжди. Наприклад, текст може бути пошкоджений при скануванні і деякі потрібні просвіти можуть зменшитися або, навпаки, сильно збільшитися.
 
Це приводить нас до другого рішенням — графу лінійного поділу. Ідея в наступному — якщо у нас є кілька варіантів, де поділити рядок на слова, а слова на літери, то давайте відзначимо всі можливі точки поділу, які ми змогли придумати. Шматок зображення між двома зазначеними точками будемо вважати кандидатом літери (або слова). Варіант графа лінійного може бути простим, якщо текст хороший і немає проблем з визначенням точок поділу або складним, якщо зображення було погане.
 
 
 
 
 
Тепер завдання. У нас є безлічі вершин графа, потрібно знайти шлях від першої вершини до останньої, що проходить через якусь кількість проміжних вершин (не обов'язково всі) з найкращою якістю. Починаємо думати, що нам це нагадує. Згадуємо курс оптимального управління з інституту, розуміємо, що це підозріло схоже на задачі динамічного програмування.
 
Давайте подумаємо, що нам потрібно, щоб алгоритм перебору всіх варіантів не вибухнув.
 
Для кожної дуги в графі нам потрібно визначити її якість. Якщо ми працюємо з графом лінійного поділу слова на символи, то кожна дуга у нас — це символ. Як якість цієї дуги ми використовувати впевненість розпізнавання цього символу, як його порахувати ми Поговрим пізніше. А якщо ми працюємо з ГЛД на рівні рядки, та кожна дуга цього ГЛД — це варіант розпізнавання слова, який у свою чергу був отриманий з символьного графа. Тобто нам потрібно вміти оцінювати загальну якість повного шляху в графі лінійного поділу.
 
Якість повного шляху в графі ми будемо визначати як суму якості всіх дуг МІНУС штраф за весь варіант. Чому саме мінус? Це дає нам можливість швидко оцінити максимально можливу якість варіанту шляху по сумі якості дуг цього шляху, а це означає, що більшість варіантів ми будемо відсікати ще до підрахунку загальної якості варіанту.
 
Таким чином для ГЛД ми приходимо до стандартному алгоритму динамічного програмування — знаходимо точки лінійного поділу, будуємо шлях від початку до кінця по дугах з найбільшим якістю, вираховуємо підсумкову вартість побудованого варіанту. А далі перебираємо шляху в ГЛД в порядку зменшення сумарного якості елементів з постійним оновленням знайденого кращого варіанту, поки не зрозуміємо, що всі необроблені варіанти свідомо гірше, ніж поточний кращий варіант.
 
 

Гіпотези зображення

Перш, ніж ми спустимося на рівень розпізнавання окремих слів, у нас є ще одна тема яка не обговорювалася, — гіпотези зображення фрагмента.
 
Ідея в наступному — у нас є зображення тексту, з яким ми збираємося працювати. Дуже хочеться все зображення обробляти однаковим чином, але правда в тому, що в реальному світі зображення всі різні — вони можуть бути отримані з різних джерел, вони можуть бути різної якості, вони можуть бути по-різному відскановані.
 
З одного боку, здається, що різноманітність можливих спотворень повинно бути дуже велике, але якщо почати розбиратися, виявляється тільки обмежений набір можливих спотворень. Тому ми використовуємо систему гіпотез тексту.
 
У нас є визначений набір можливих гіпотез проблемного тексту. Для кожної гіпотези потрібно визначити:
 
     
  • Швидкий спосіб з'ясувати, чи застосовна ця гіпотеза до цьому зображенню, причому зробити це тільки на основі характеристик зображення, до розпізнавання.
  •  
  • Метод для виправлення на зображенні проблем конкретної гіпотези.
  •  
  • Критерій якості правильності вибору гіпотези за підсумками розпізнавання зображення, плюс, можливо, рекомендації для наступних гіпотез.
  •  
 
 
На зображенні вище можна побачити гіпотези для різної бінаризації і контрастності вихідного зображення.
 
У результаті обробка гіпотез виглядає так:
 
 
     
  1. По зображенню згенерувати найбільш відповідну гіпотезу.
  2.  
  3. Виправити спотворення від обраної гіпотези.
  4.  
  5. Розпізнати отримане зображення.
  6.  
  7. Оцінити якість розпізнавання.
  8.  
  9. Якщо якість розпізнавання покращився, то оцінити, чи потрібно застосовувати нові гіпотези до зміненого зображенню.
  10.  
  11. Якщо якість погіршився, то повернутися до вихідного зображення і спробувати застосувати до нього яку-небудь іншу гіпотезу.
  12.  
 
 
 
 
 
 
 
На зображеннях показано послідовне застосування гіпотез білого шуму та стисненого тексту.
 
 

Оцінка якості слова

У нас залишилися нерозкритими дві важливих теми: оцінка загальної якості розпізнавання слова і розпізнавання символів. Розпізнавання символу — тема на кілька розділів, тому спочатку обговоримо оцінку якості розпізнаного слова.
 
Отже у нас є якийсь варіант розпізнавання слова. Перше, що спадає на думку, — перевірити його за словником і дати йому штраф, якщо воно в словнику не знайшлося. Ідея хороша, але не всі мови є словники, не всі слова в тексті можуть бути словниковими (імена власні, наприклад), і, якщо вже ми заглиблюємося в складності, — не все в тексті взагалі може бути словами в стандартному розумінні цього терміна.
 
Трохи раніше ми говорили, що будь-які оцінки за слово цілком повинні бути негативними, щоб у нас нормально працював перебір по ГЛД. Зараз нам це почне активно заважати, тому давайте зафіксуємо, що у нас є якась заздалегідь визначена максимальна позитивна оцінка слова, слову ми даємо позитивні бонуси, а фінальний негативний штраф визначаємо як різниця набраних бонусів і максимальної оцінки.
 
Ок, нехай ми розпізнаємо фразу «Вася прилітає рейсом SU106 в 23.55 20/07/2015». Ми, звичайно, можемо оцінювати тут якість кожного слова за загальними правилами, але це буде досить дивно. Скажімо, і SU106 і Вася цілком зрозумілі в цьому рядку слова, але очевидно, що правила утворення у них різні і, по ідеї, верифікація теж повинна бути різною
 
Звідси з'являється ідея моделей. Модель слова — це якесь узагальнений опис конкретного типу слів у мові. У нас, звичайно, буде модель стандартного слова в мові, але також будуть моделі чисел, абревіатур, дат, скорочень, власних назв, URL і т.д.
 
Що нам дають моделі і як їх нормально використовувати? Фактично ми звертаємо у зворотний бік нашу систему перевірки слова — замість того щоб для варіанту слова довго дізнаватися, що ж це таке, ми даємо кожної моделі вирішувати, чи підходить їй даний варіант слова і наскільки добре вона його оцінює.
 
 
 
 
 
З самої постановки задачі формуються наші вимоги до архітектури моделі. Модель повинна вміти:
 
 
     
  • Швидко сказати, підходить чи ні для неї варіант слова. Стандартна перевірка включає всі перевірки дозволених наборів символів для кожної букви в слові. Скажімо, у словниковому слові пунктуація повинна бути тільки на початку або в кінці, а в середині слова набір пунктуації сильно обмежений, і поєднання пунктуації сильно обмежена (супер-здатність?!), А в моделі числа в основному повинні бути цифри, крім дозволеного в даній мові символьного суфікса (10-е, 10 th ).
  •  
  • Вміти за своєю внутрішньою логікою оцінити якість розпізнаваного слова. Приміром, слово зі словника повинно явно оцінюватися вище, ніж просто набір символів.
  •  
 
При оцінці якості моделі не варто забувати, що наше завдання в результаті — порівнювати моделі між собою, тому їх оцінки повинні бути узгоджені. Більш-менш нормальний спосіб цього добитися — це ставитися до оцінки моделі як до оцінки ймовірності побудувати слово по даній моделі. Скажімо, словникових слів у звичайному мові досить багато, і отримати словникове слово при неправильному розпізнаванні нескладно. А от зібрати нормальний, відповідний під всі правила телефонний номер вже набагато складніше.
 
У підсумку при розпізнаванні деякого фрагмента рядка у нас виходить приблизно така схема:
 
 
 
Окремим пунктом при оцінці варіантів розпізнавання йдуть додаткові емпіричні штрафи, які не вписуються ні в концепцію моделей, ні в оцінку розпізнавання. Скажімо, «ТОВ Роги і копита» і «000 Роги і копита» виглядають як два однаково нормальних варіанту (особливо якщо в шрифті 0 (нуль) і О (буква О) слабо відрізняються пропорціями). Але при цьому досить очевидно, який варіант розпізнавання повинен бути правильним. Для таких невеликих конкретних знань про світ зроблена окрема система правил, яка може додатково штрафувати не сподобалися їй варіанти після оцінок моделей.
 
Про саме розпізнавання поговоримо вже в наступній частині цього посту. Підписуйтесь на блог компанії, щоб не пропустити :)
    
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.