Проста технологія класифікації розпізнаних сторінок ділових документів на основі методу Template Matching

image
Завдання класифікації добре відома: потрібно віднести довільний об'єкт з деякої вибірки до одного чи кількох класів з заздалегідь визначеного безлічі класів.
1. Постановка завдання
Алгоритм класифікації може бути побудований на основі машинного навчання, використовує певну навчальну вибірку об'єктів, про які відомо, до яких класів вони належать.
Також добре відомий метод Template Matching (зіставлення шаблонів), який складається у попередній підготовці шаблонів для всіх можливих класів. Прийняття рішення про належність тестового об'єкта до певного класу здійснюються за критерієм мінімуму (максимуму) деякої функції зіставлення об'єкта і його шаблону (в [1] розглядається об'єкта — зображення символів). Цей метод є одним з найбільш простих для розуміння і власної реалізації, по суті, необхідно вирішити питання про подання об'єкта деяким шаблоном і вибору функції зіставлення.
Розглянемо задачу класифікації розпізнаних сторінок ділових документів. Ділові документи, що використовуються у документообігу, в тому числі в обміні документами між організаціями, що володіють певною стандартизацією, вони можуть бути як неструктурованими, так і структурованими. У банках або страхових компаніях часто необхідні такі документи як довіреність, договір, картка із зразками підписів і печаток, статут, контракт, рахунок (invoice англійською), свідоцтва про реєстрацію і т. п. При створенні та ведення електронних архівів паперові документи оцифровуються, а цифрові образи сторінок (скани сторінок) можуть бути розпізнані й проаналізовані. Одним із завдань аналізу є класифікація образу сторінки, складається в перевірці приналежності образу сторінки певного класу. Така потреба з'являється при контролі образів документів, доданих користувачем в якості електронних копій.
Для аналізу інформації, що міститься в образі документа (зокрема, класифікації) можна використовувати програми розпізнавання рукописного тексту (OCR). В даний час одним з найбільш популярних рішень є Tesseract OCR, наприклад, у дисертації [2] ця OCR була обрана для розпізнавання корпусу архівних документів з наступних причин: можливість вільного поширення, а також представлення результатів розпізнавання у форматі HOCR (HTML OCR) із збереженням інформації про координати розпізнаних слів.
Tesseract OCR залежно від ступеня зашумлення тексту і власних здібностей може розпізнавати образи сторінок успішно чи неуспішно. Систематичний неуспіх може бути пов'язаний з об'єктивними труднощами розпізнавання певних класів документів, наприклад, паспортів громадянина РФ, програма розпізнавання якій була описана нами в іншій статті [3]. Характерні помилки Tesseract OCR можна розділити на кілька видів:
  • Е1: повна відмова від розпізнавання сторінки, аж до того, що не розпізнано жодного слова;
  • Е2: число помилок настільки велике, що людина не може зрозуміти документ за його текстового подання у форматі HOCR (наприклад, див. на ілюстрації вище – на ній наведено реальний приклад невдалого розпізнавання документа "Свідоцтво про постановку на облік в ІМНС" з допомогою Tesseract OCR версії 3.04.00);
  • Е3: неправильно розпізнана структура сторінки, наприклад, коли розташовані поруч фрагменти тексту в результаті виявилися рознесеними на значну відстань;
  • Е4: наявність невеликого числа помилок, коли в більшості невірно розпізнаних слів присутній 1-2 помилки.
У цій статті ми будемо розглядати класифікацію сторінок тільки таких документів, які масово розпізнаються Tesseract OCR, у припущенні про ймовірне виникнення помилок типу Е3 і Е4.
Розглянемо іншу задачу класифікація образів сторінок документів. У наявному наборі багатосторінкових файлів зображень, кожен з яких містить сторінки одного або кількох документів, необхідно визначити межі кожного з наявних документів і віднести знайдені документи до одного з заздалегідь відомих класів. Отримані порції сторінок зберігається в електронному архіві як окремі документи.
Далі ми розповімо про простому методі класифікації сторінок документів, заснованому не зіставленні із заздалегідь підготовленими шаблонами класів. Метод дозволяє обробляти односторінкові, так і багатосторінкові документи, він дозволяє врахувати деякі помилки розпізнавання OCR.
2. Опис шаблонів і зіставлення з шаблонами
Ми пропонуємо створювати шаблони класів на основі ключових слів і способи комбінування декількох ключових слів.
Модель неструктурованого документа у вигляді структури над множиною ключових слів є досить відомою. Наприклад, див. опису моделей документа у вигляді
  • векторної моделі або "мішка слів", тобто мультимножества входять в документ слів [4],
  • мовної моделі, що враховує порядок слів (що враховує ймовірність появи послідовності слів) [5],
  • тематичної моделі, що використовує теми, що складаються з наборів слів [6, 7].
Ми опишемо підхід до створення шаблонів, використовує перераховані вище механізми і враховує помилки і особливості розпізнавання.
В якості базових ознак будуть виступати розпізнані слова у формі символів слова і його властивостей:
W = (T(W), m1(W), m2(W), m3(W), m4(W), m5(W), m6(W)),
де T(W) – ядро слова, тобто послідовність символів і знаків "?" і "∗", останні використовуються для задання множини слів, наприклад, "∗ab?c" задає безліч слів з довільним числом символів, з останніми символами ab?c, на місці "?" може бути довільний символ.
m1(W) – поріг відстані при порівнянні двох слів T(W) і Wr. Для порівняння двох слів необхідно вибрати метрику (функцію відстані), ми використовували відстань Левенштейна [8] або спрощену функцію, що враховує лише кількість операцій заміни одного символу на інший. В останньому випадку відстань d(T(W), Wr) підраховується тільки для слів однакової довжини, для слів із знаками "?" відповідні символи в порівнянні не беруть участь, а для слів із знаками "∗" порівнюються потрібні підрядка. Якщо d(T(W), Wr)<m2(W), то слова є ідентичними, в іншому випадку – різними. У найпростішому випадку m2(W) – це максимальне числа операцій заміни при трансформації T(W) Wr.
m2(W) – обмеження на довжину слова Wr при порівнянні T(W) і Wr, має сенс для слів, що містять "∗".
m3(W) – ознака залежності від регістру (case sensitive/insensitive) при порівнянні символів.
m4(W) – прямокутник слова, що складається з координат в діапазоні [0,1], що використовуються для перевірки попадання слова в зазначений прямокутник.
m5(W) – ознака заперечення слова, який вказує, що цього слова не має бути в тексті. За допомогою m5(W) можна організувати перевірку наявності, так і відсутності слова W в тексті.
m6(W) – буде описаний нижче.
При пошуку слова T(W) в розпізнаному тексті документа T ми перевіряємо істинність умови
WrT: d(T(W), Wr) < m2(W) ∧ (F(Wr) ∩ m4(W) = F(Wr))
де F(Wr) – прямокутник слова Wr, тобто координати слова, витягнуті з результатів розпізнавання у форматі HOCR, абсциси і ординати нормуються на ширину і висоту вихідного зображення. При порівнянні використовується параметр m3(W). Взагалі кажучи, може бути знайдено декілька слів {Wr}, ідентичних ключовому слову T(W).
Визначимо для випадку m5(W)=0 предикат P(W, T)=1, якщо в розпізнаному тексті документа T знайдено хоча б одне слово, ідентичне слова W, і P(W, T)=0, якщо в тексті не знайдено жодного слова, ідентичного слова W. Якщо слово володіло ознакою m5(W)=1, то P(W, T)=0, якщо в розпізнаному тексті документа T знайдено хоча б одне слово, ідентичне слова W, і P(W, T)=1, якщо в тексті не знайдено жодного слова, ідентичного слова W.
Також нам знадобиться оцінки d(T(W), Wr) слів, ідентичних слова T(W).
Далі визначимо розміщення слів як впорядкована множина слів R = W1,W2,..., для якого перевірятиметься наявність кожного з слів в розпізнаному документі T:
P(W1, T) ∧ P(Wr, T) ∧… (1)
і додатково для кожної пари слів Wi і Wi+1 перевіряється умова
r(Wi+1) – r(Wi) < m5(W), (2)
де функція r(W) дає номер слова W у тексті T, упорядкованому механізмами OCR. Тобто параметр mr6(W) визначає відстань між сусідніми словами в розміщенні, при mr(Wi+1) = ∞ умова (2) не перевіряється, а перевіряється тільки порядок слідування слів.
Для розміщення R може бути заданий m7(R) – прямокутник розміщення, сенс якого аналогічний прямокутника слова, перевіряється, чи містяться повністю знайдені в тексті T слова, ідентичні словами W1,W2..., у прямокутнику m6(R).
Виконання умов (1), (2) та умови перевірки відповідності рамці m7(R) прямокутника визначає предикат приналежності розміщення R тексту T: P(R, T)=1. У найпростішому випадку розміщення може складатися з одного єдино слова, в загальному випадку для обчислення P(R, T) потрібен перебір множин, ідентичних словами W1,W2… .
Визначимо оцінку d(R, T) розміщення як мінімальну з оцінок слів: min(d(W1, T), d(W2, T), ...).
Тепер визначимо поєднання як безліч розміщень S = R1,R2,..., для якого перевірятиметься наявність кожного з розміщень в розпізнаному документі T:
P(R1, T) ∧ P(R2, T) ∧… (3)
Порядок розміщень неважливий. На додаток до умови (3) може бути додано порівняння всіх прямокутників слів з поєднання з прямокутником поєднання m8(S). Зазначені умови визначають предикат приналежності поєднання S тексту T: P(S, T)=1.
Оцінку d(S, T) поєднання визначимо як мінімальну з оцінок розміщень, що входять до поєднання: min(d(R1, T), d(R2, T), ...).
І, нарешті, визначимо шаблон M як безліч поєднань S1,S2,..., для якого приналежність шаблону розпізнаної тексту T встановлюється перевіркою вираження
P(M, T) = P(S1, T) ∨ P(S2, T) ∨… (4)
На додаток до умові (4) може бути додано порівняння всіх прямокутників слів шаблону з прямокутником поєднання m8(M).
Оцінку d(M, T) шаблону визначимо як максимальну оцінок поєднань, що входять в шаблон: max(d(S1, T), d(S2, T), ...).
До наявних порівнянь шаблону з розпізнаним текстом додамо перевірки відповідності деяких властивостей тексту (символів на сторінці m9(T), кількість колонок тексту m10(T)) з аналогічними властивостями шаблону m9(M), m10(M).
Якщо n класів готовий набір шаблонів M1, ..., Mn, завдання перевірки відповідності класу Mi розпізнаної сторінки документа T зводиться до обчислення відстані d(Mi, T) за викладеною схемою і порівняно цієї відстані з заздалегідь відомим порогом d1. Якщо справедливо max(Mi) < d1 документ T відповідає класу i.
Пояснимо необхідність використання елементів запропонованих шаблонів.
Прості одиничні помилки виду Е4, часто з'являється в певному слові, можуть бути проігноровані з допомогою знаків "?" і "∗" в масці слова. Для контролю довжини слова, що включає знак "∗", може бути використаний параметр m2, наприклад, ключові слова "ДОГОВІР", "Договору" можуть бути описані ядром "ДОГОВІР∗" з обмеження m2=8, що виключає з розгляду слова типу "договороздатність". Ядро "? ОБМОВА" не дозволяє розрізняти слова "ДОГОВІР" і "АОГОВОР".
Поріг m1 може бути використаний для вимоги повного збігу ключового слова і слова з тексту, наприклад, при m1=0 ядро "ДОГОВІР" при пошуку в тексті не допускає вибору слів "АОГОВОР" або "ДОГО8ОР", що відрізняються однією операцій заміни символу.
Параметр m3 також дозволяє ігнорувати помилки розпізнавання регістра символу.
Прямокутник слова (розміщення, поєднання, шаблону) m4 забезпечує часткове опис шаблону структури документа за рахунок вилучення ключових слів із зазначених областей образу документа. Зрозуміло, дуже кордону прямокутників не можуть бути вказані точно, з-за варіативності частин документів.
Помилки виду Е3, тобто неправильно розпізнана структура сторінки, можуть бути іноді проігноровані налаштуванням розміщень. Розміщення природним чином описує словосполучення або декілька розташованих рядом слів. У разі розбиття колонки тексту на два стовпці з-за помилок розпізнавання описане розміщення буде знайдено, якщо не вказувати відстані між словами m6.
Можливість перевіряти як наявність, так і відсутність слів, встановлюється параметром m5, дозволяє складати шаблони для схожих документів, поділяючи їх за допомогою ключових слів, присутніх в одному класі документів та присутніх в іншому.
Наведені пояснення показують корисність описаної схеми шаблонів для класифікації розпізнаних з помилками текстів. Описана схема є простою у тому сенсі, що створення шаблону в деяких випадках є простою справою, а сам шаблон виходить інтуїтивно зрозумілим. Наприклад, документ "Договір оренди нежитлового приміщення" можна описати таким шаблоном:
  • ключові слова:
image
  • розміщення: R1=W1, R2=W2&W3&W4, R3=W2&W5&W6, R4=W7&W8&W9&W10, рамки у всіх розміщень відсутні,
  • поєднання: S1 =R1R2, S2 =R1&R3, S3 = R3, рамки у всіх сполучень відсутні,
  • шаблон: M = S1&S2&S3, шаблон є рамка m8(M) = {(0.0,0.0), (0.3,0.9)}.
Завдання вибору найкращого класу вирішується обчисленням відстаней d(M1, T), ..., d(Mn, T), відкидання таких класів Mj, що справедливо d(Mj, T) > d1, упорядкуванням отриманого набору за зростанням (по суті, ми хочемо вибрати один або кілька класів з мінімальним штрафом за не відповідність шаблону тексту) і збереженням однієї або декількох альтернатив d(Mi1, T), d(Mi2, T),… Тобто найкращим чином тексту T відповідає клас i1, а інші класи i2,… впорядковані по відстані. Вирішення конфліктів d(Mi1, T) = d(Mi2, T) в найпростішому випадку провести, відмовившись від класифікації, у деяких випадках конфлікт усувається використанням додаткових ознак m9, m10.
3. Формування шаблонів (навчання)
Очевидно, що описаний спосіб зіставлення з шаблонами є простим, проте, певна складність є в процесі формування шаблонів, тобто у навчанні.
Розглянемо процес формування шаблонів на реальному прикладі для потоку документів 45 класів. Ми готували шаблони в кілька етапів, орієнтуючись на ключові слова на першій сторінці багатосторінкових документів.
Етап 1. Спочатку ми розглядали безліч еталонних документів. Для кожного класу були підготовлені кілька зразків ідеальних документів, результати розпізнавання яких помилки відсутні. Текстові подання цих документів були перетворені в мішки слів, тобто в мультимножества слів, з числа яких були видалені стоп-слова (короткі слова, ПІБ, числові дані, дати тощо). Далі простими переборными алгоритмами з цих мультимножеств були обрані поодинокі слова і словосполучення з кількох слів, властиві одному з класів. Основна увага зверталася на характерні слова з заголовків і назв розділів документа. Таким чином було складено декілька розміщень, добре відділяють одні класи від інших. Таким чином ми шукали ядра ключових слів, а інші параметри встановлювали за замовчуванням. Відразу ж було виявлено кілька проблемних класів, наприклад, перша сторінка документів класу "Статут" могла бути представлена одним єдиним ключовим словом "Статут", яке часто зустрічається в інших документах, наприклад, в документах класу "Договір". Для усунення цієї проблеми ми використовували два прийоми:
  • використання слів, які не повинні зустрічатися на першій сторінці документів класу "Статут",
  • використання ознаки m9(T) – кількість символів на сторінці – який добре виділяв сторінки документів класу "Статут".
Етап 2. Далі, незважаючи на деякі недосконалості класифікації кожним шаблонами, ми перейшли до вибірки документів, що складається з 50-100 зразків реальних документів (односторінкових і багатосторінкових), розпізнавання яких давало широкий спектр помилок всіх видів Е1 – Е4. Аналіз помилок дозволив виявити деяку кількість сторінок, які вимагали модифікації шаблонів, і сторінки, які не могли бути класифіковані нашою технологією (насамперед, з-за великої кількості помилок розпізнавання). Модифікація шаблонів зводилася до пошуку нових розміщень та комбінацій, пошуку слів, які не повинні зустрічатися в документі, а також до вибору параметрів ключових слів, насамперед, прямокутників m4 і відстаней між словами m6. Аналіз результатів класифікації проводився за наступними критеріями:
image
Правильно класифіковані сторінки оцінюються точністю (n1+m2)/(n1+ n2+ n3+m1+m2), помилок помилкової класифікації – як (n2+m2)/(n1+n2+n3+m1+m2), а відмови від класифікації – як (n3)/(n1+ n2+ n3+m1+m2).
Сама неприємна помилка класифікації – це помилкова класифікація непервой (проміжної і останньої) сторінку багатосторінкового документа. Це пояснюється наступним зберіганням багатосторінкового документа у вигляді кількох частин і необхідністю корекції, що вимагає пошуку відсутньої частини документа. Для класифікації непервых сторінок застосовувався описаний метод, що використовує шаблони проміжних і останніх сторінок. Інші помилки класифікації (неправильна класифікація першої сторінки багатосторінкового документа або єдиною сторінки односторінкового документа) виправляються простою заміною класу за допомогою довідника.
Етап 3. Перші два етапи засновані на використання правил (власне шаблонів) для віднести до того чи іншого класу. Для вибірок великого обсягу (3000 – 30000 зразків кожного класу) можливо проведення машинного навчання, наприклад, відомим методом побудови бінарного дерева рішень CART (Classification and Regression Trees [9]). Вихідними даними для навчання є описи відомих з попередніх етапів ключових слів у вигляді ядра і ознак. На цих ознаках будувалося кілька дерев, для кожного класу, з стратегії один проти всіх. Якщо деякий документ у процесі класифікації не був розпізнаний не одним з дерев, формується відмова класифікації. З відомих особливостей методу CART, відзначимо необхідність досить великого обсягу навчальної вибірки для стабільного навчання. З-за цього ми не будемо наводити результати класифікації, отримані за допомогою методу CART, хоча в цілому вони перевершують результати класифікації, отримані за допомогою навчання на етапах 1 і 2.
4. Експерименти
Для експериментів було використано два тестових множини:
  • містить образи документів середнього і поганої якості оцифровки, підібрані для етапу навчання (884 сторінки),
  • містить образи документів середньої якості оцифровки, отримані незалежно від етапу навчання (3014 сторінок).
Результати класифікації наведені нижче у двох таблицях:
image
З наведених таблиць ясно, що описана нами технологія класифікації дає точність 0.86 – 0.95, при цьому помилкова класифікація не перевищує 0.01, інші помилки відносяться до відмов від класифікації. Тобто запропонований метод не завжди спрацьовує, але рідко пропонує невірний клас.
Швидкодія реалізованої класифікації (збірка Release за допомогою Microsoft Visual Studio 2013) досить велика: 3000 розпізнаних сторінок обробляються приблизно за 1 хвилину на комп'ютері Intel® Core(TM) i7-4790 CPU 3.60 GHz, 16,0 GB, Windows 7 prof 64-bit. Однак власне розпізнавання OCR Tesseract, необхідне для вихідного файлу HOCR, займає декілька секунд.
Для зменшення частки сторінок, що залишилися неклассифицированными, необхідні можливі наступні кроки:
  • застосування методів бінаризації, знімають фон на забруднених документа та документи зі складним фоном,
  • використання інших OCR,
  • використання більш результативних методів класифікації, що базуються на пошуку ключових слів, наприклад, побіжно описаний вище метод CART.
Висновок
Описана технологія класифікації була використана в реалізованих Smart Engines проектах введення і аналізу потоку відсканованих документів.
Описана технологія є простою для розуміння і самостійної реалізації для вирішення аналогічних завдань.

Список корисних джерел

  1. Гонсалес Р., Вудс Р. Цифрова обробка зображень. М: Техносфера, 2005. 1070 с.
  2. Смирнов С. В. ТЕХНОЛОГІЯ І СИСТЕМА АВТОМАТИЧНОГО КОРЕКТУВАННЯ РЕЗУЛЬТАТІВ ПРИ РОЗПІЗНАВАННІ АРХІВНИХ ДОКУМЕНТІВ. Дисертація на здобуття наукового ступеня кандидата технічних наук, СПт:, 2015. – 130 с.
  3. "Розпізнавання Паспорта РФ на мобільному телефоні" (https://habrahabr.ru/company/smartengines/blog/252703/)
  4. D. Martin, Jurafsky D. Speech and Language Processing. An introduction to natural language processing, computational linguistics, and speech recognition. Pearson Prentice Hall, 2009. – 988 p.
  5. Ponte J. M., Croft W. B. A modeling Language Approach to Information Retrieval // Proc. Conference on Research and Development in Information Retrieval. ACM. 1998. – С. 275-281.
  6. Indexing by Latent Semantic Analysis / S. Deerwester [та ін] // Journal of the American Society for Information Science. 1990. – T. 41, № 6. – С. 391.
  7. Черняк О. Л. РОЗРОБКА ОБЧИСЛЮВАЛЬНИХ МЕТОДІВ АНАЛІЗУ ТЕКСТІВ З ВИКОРИСТАННЯМ АНОТОВАНИХ СУФФИКСНЫХ ДЕРЕВ. Дисертація на здобуття наукового ступеня кандидата технічних наук, М:, 2016. – 124 с
  8. Левенштейн в. І. Двійкові коди з виправленням випадінь, вставок і заміщень символів, – М.: Доповіді АН СРСР, т. 163.4, 1965. — 845-848 с.
  9. Breiman L., Friedman J. H., Olshen R. A., & Stone C. J. Classification and regression trees. Monterey // CA: Wadsworth & Brooks/Cole Advanced Books & Software, 1984. – 368 p.
Джерело: Хабрахабр

0 коментарів

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