Деякий час назад (о, боже, вже рік пройшов!) На питання, чи буде комусь цікавий огляд по сучасним методам сегментації зображення сторінки документа, я отримав позитивну відповідь (від massimus). І сьогодні нарешті вирішив цей огляд зробити.
На сторінці є текст і картинки. Потрібно розбити на блоки текст і виділити картинки.
Отже, нам потрібно розбити текст на блоки і виділити картинки. Як бачите, про таблиці, діаграмах і інших вишукуваннях тут мови не йде; більш того, часто припускають, що картинки висококонтрастними і при цьому добре бінаризованими - тобто їх межі в принципі можна знайти, працюючи тільки з монохромним зображенням.
Також в дослідженнях часто використовують поняття «манхеттенський» і «неманхеттенскій» layout. «Манхеттенський» - це такий, в якому кордони всіх блоків прямі (кожен блок або прямокутний, або є кілька прямокутників, у яких деякі вершини і частини сторін загальні), «неманхеттенскій» не задовольняє таким обмеженням.
Для початку ми розберемо деякі алгоритми, призначені для роботи з «Манхеттенського» документом.
Це найбільш древній алгоритм - мабуть, перше, що спадає на думку, коли стикаєшся з завданням сегментації. Вперше описаний в далекому 1982 році, в статті K.Y. Wong, R.G. Casey, F.M. Wahl. Document Analysis System.
У двох словах він працює так: давайте трошки размажем слова по вертикалі і по горизонталі, утворені зв'язкові області будуть готовими блоками.
Якщо описати трохи докладніше, то вийде так:
- Беремо зображення сторінки в RLE-поданні
- Видаляємо білі RLE-штрихи (= послідовність білих пікселів) довжиною менше lT_horz. Отримуємо зображення Image_1
- Початкове зображення повертаємо на 90 градусів і на повернутому зображенні видаляємо білі RLE-штрихи довжиною менше lT_vert. Повертаємо зображення назад і отримуємо зображення Image_2
- Робимо AND зображень Image_1 і Image_2
- На отриманому зображенні ще разок видалимо білі штрихи довжиною менше T_Final
Пов'язані області на отриманому зображенні - це готові блоки. Їх варто розділити на текстові і нетекстові. У 1982 році ще не було такого арсеналу засобів машинного навчання, без них було важко - дерево рішень малювали вручну.
Ось так приблизно виглядають проміжні зображення і кінцеві блоки:
Переваги алгоритму зрозумілі - він простий, працює з RLE зображенням і тільки з ним, а значить і швидкий. Сам алгоритм ніде явно не спирається на те, що вхідний документ - «манхеттенський». Втім, якщо подумати, то на «неманхеттенском» алгоритм не спрацює - на наведеному нижче прикладі текст приклеїться до картинки.
По-справжньому погана новина полягає в тому, що на «Манхеттенському» документі склейки тексту і «нетекста» також дуже часті, в SKB це помічено.
Recursive XY cut
Через пару років, в 1984 році, був описаний більш просунутий метод сегментації сторінки, який називається recursive XY cut. Він описаний в статті G. Nagy and S. Seth. «Hierarchical representation of optically scanned documents» та в 90-і роки активно розвивався.
Про цей метод вже явно сказано, що він годиться тільки для Манхеттенського документа. Суть методу в тому, що ми розбиваємо сторінку на блоки по черзі, ділячи блоки по вертикалі або по горизонталі. Тобто алгоритм приблизно такий:
- Готуємо сторінку, очищаючи її від дрібного сміття
- Виділяємо зв'язкові області. Можна навіть і трохи їх пооб'едінять і отримати щось на зразок слів, якщо раптом хтось вміє такі об'єднання безпечно будувати. Але в рамках даного поста будемо називати їх «зв'язкові області».
- Обчислюємо глобальні параметри алгоритму, наприклад, медіанну висоту і ширину символу.
Далі алгоритм запускаємо рекурсивно, починаючи з усією сторінки:
- Шукаємо, як би можна поділити блок вертикальним або горизонтальним розрізом.
- Якщо змогли - ділимо і рекурсивно запускаємо розподіл кожної з частин.
- Якщо не змогли, зупиняємося.
Що стосується пункту про те, як ділити блок. Пропонується два способи - або по білому просвіту (його можна знайти на проекції блоку на горизонтальну або вертикальну вісь відповідно) або по довгій і досить добре ізольованою чорної прямій лінії.
В результаті всіх цих поділів виходить деревна структура, як справа внизу на малюнку:
Прямо скажемо, не найпоширеніша конфігурація навіть для газет, не кажучи вже про журналах і офісних документах. Але зустрічається, в газетах вже точно.
Більш серйозною проблемою алгоритму бачиться все ж його підпорядкування порогам. Скажімо на такому фрагменті буде складно відокремити заголовок від тексту, що не порвавши при цьому заголовок:
А тут буде досить важко відокремити картинку від тексту, спираючись лише на пороги по відстані:
Зрозуміло, актуальні ще й загальні для всіх представлених в цьому пості алгоритмів проблеми - як не відірвати нумерацію від нумерованого списку і як позбутися від обмежень, які я вказав на початку (що є тільки текст і висококонтрастні картинки).
Сегментація за допомогою максимальних білих прямокутників
Тепер розповімо про ідею сегментувати сторінку за допомогою максимальних білих прямокутників. Що таке «максимальний білий прямокутник»? Білий - це значить, що в ньому немає чорних крапок (зрозуміло, що зображення треба попередньо позбавити від дрібного сміття). Максимальний - означає, що його не можна збільшити ні вліво, ні вправо, ні вгору, ні вниз так, щоб він залишився білим. Далі замість чорних крапок ми будемо розглядати зв'язкові області. Як і в рекурсивних перетинах, ми можемо їх якось сгруппірровать, але знову не будемо на цьому зупинятися. Зрозуміло, що практично для кожної відсканованої сторінки таких білих прямокутників - десятки тисяч. Але для цілей сегментації можуть знадобитися тільки найбільші. Алгоритм їх пошуку запропонований в статті Thomas M. Breuel. Two Geometric Algorithms for Layout Analysis
другий алгоритм з цих «two» виділяє рядка між цими білими роздільниками, але, як мені здається, він не особливо-то видатний, якщо комусь цікаво, дивіться в статті.
Повернемося до задачі пошуку максимальних білих прямокутників. Можна ввести поняття «якість» для прямокутника.
Назвемо функцію якості Q (r) для прямокутника r монотонної. якщо при r1 ⊆ r2 виконується Q (r1) = 1), а T2 і Ta - це ще два порога. Сенс цієї умови полягає в тому, що варто об'єднати два слова в рядку, але якщо ці два слова мають різну висоту, то об'єднувати осередки треба з більшою обережністю.
Після того як знайшли все осередки, які потрібно об'єднати, об'єднуємо їх - і діаграма Вороного перетворюється в готову сегментацію.
Недоліки діаграми Вороного знову ті ж - обмеження залежать тільки від порогів, та ж неясність з картинками. Безсумнівна перевага даного методу полягає ще й в тому, що він містить тільки три параметри, які треба підібрати - і ці параметри вказані явно.
На цьому я закінчую свій огляд наукових досягнень, пов'язаних з сегментацією сторінки. А наука, думаю, ще своє слово скаже :)