Усунення перспективних спотворень і розгинання кривих рядків на фотографіях книжкових розворотів

минулого разу в статті «Пошук лінії корінця на фотографіях книжкових розворотів» ми обіцяли розповісти про те, що трапляється з фотографією книжкового розвороту після цього, а саме — про усунення перспективних спотворень і розгинання кривих рядків тексту. Без цього отримати якісні результати OCR практично неможливо.

Отже, вважаємо, що ми вже знайшли на фотографії лінію корінця, скористаємося цим знанням, щоб визначити ваніш-точки для сторінок розвороту (vanishing point). Ваніш-точки – це точки перетину паралельних прямих у перспективній проекції книги на площину зображення. Вони обидві повинні розташовуватися на продовженні цієї лінії, але для кожної зі сторінок положення точки може бути своє. Схематично це показано на наступній ілюстрації (насправді, це лог для налагодження). Лінія корінця виділена червоним, лінії, що перетинаються в ваніш-точках, – зеленим.



Як правило, ваніш-точки двох сторінок знаходяться недалеко один від одного, але наведений приклад показує, що так буває не завжди: для лівої сторінки цього розвороту зелені лінії сходяться дуже слабо і ваніш-точка лежить далеко внизу, а для правого – вгорі, відносно близько від краю зображення.

Яким чином можна знайти ці лінії на зображенні? На допомогу нам знову-таки приходить перетворення Хафа (Hough transform), тільки зображення ми повинні для цього підготувати відповідним чином. Постараємося виділити межі текстових блоків на зображенні максимально простим способом. Для цього виконаємо наступні нескладні дії:

1) Бінаризація;
2) Нормалізація зображення за розмірами, наприклад до 800 пікселів по довшій стороні;
3) Морфологічне нарощування (dilation, r = 6);
4) Морфологічний градієнт (r = 1).







Якщо до отриманого зображення застосувати швидке перетворення Хафа, ми отримаємо:



На ньому чітко помітні кілька локальних максимумів, що відповідають межам сторінок і текстових блоків. Лінія корінця розділяє ці множини на два (назвемо їх «ліве» і «праве» відповідно), при цьому кожен з них добре описується лінією в просторі Хафа. Як відомо, ліній у просторі Хафа відповідають точки в просторі зображення. Це і є шукані ваніш-точки.

Для пошуку ліній у просторі Хафа пропонується спочатку виділити локальні максимуми за допомогою алгоритму non-maximum suppression. Відкидаємо всі максимуми слабкіше 0.2 від найбільшого. В принципі, шум можна фільтрувати і по-іншому, тут важливо залишити лише точки, що відповідають протяжним контурів на зображенні градієнта. Групу максимумів з околиці точки, відповідної лінії корінця (на малюнку в початку статті вона виділена червоним), ми усредняем і додаємо центр кластера до «лівим» і «правим» множиною точок із збільшеною вагою. Застосовуємо метод найменших квадратів (МНКдля пошуку ліній, що описують наші безлічі точок (на малюнку вони виділені зеленим). Таким чином, ми отримали ваніш-точки в просторі вихідного зображення. На жаль, зобразити їх на ньому не вийде, оскільки вони лежать далеко за його межами. Знаючи положення цих точок, ми намалювали віртуальні лінії, що перетинаються в них – дивимося ще раз на першу картинку, вони там виділені зеленим.

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



Зрозуміло, можна ставити підстави трапецій вище або нижче, зовнішні сторони зрушувати назовні або всередину і отримувати при цьому інші проективні перетворення, але нам на цьому етапі важливо лише, щоб корінець став вертикальним, а рядки – однакової довжини. Застосовуємо отримані проективні перетворення незалежно для кожної зі сторінок, отримуємо:



Вертикальну перспективу можна вважати виправленої. Переходимо тепер до розгинанню кривих рядків.

Виділяємо похилі «фрагменти» слів на зображенні (а для цього картинка бинаризуется, на ній виділяються зв'язкові компоненти, будується граф, що описує їх взаємне положення, відбувається попередня збірка слів). Колір показує кут нахилу фрагмента: якщо < 0 – зелений, якщо > 0 – червоний, рівний 0 (округлено до 1 градуса) – синій.



Під «фрагментом» ми тут розуміємо «склеїлися в слово» зв'язкові компоненти. Йому може відповідати як слово, так і якийсь фрагмент слова, це лише результат попереднього аналізу, не претендує на істину. Можна бачити, що виділилися далеко не всі слова, але для побудови моделі сторінки цього буде достатньо.

Використовуємо наступну модель сторінки:



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

Використовуємо звичний вже МНК, щоб знайти вектор параметрів . Далі, зробимо фільтрацію викидів, т. до. ми могли помилково замість фрагмента слова виділити десь щось інше (аналіз у нас був грубий, попередній).



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

Спробуємо з допомогою нашої моделі «простежити» рядка до кінця. Центри фрагментів слів будуть служити «затравками» для алгоритму простежування.

Підготуємо зображення для дослідження кривих рядків:

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

Замикання і розмикання виконуємо вікном шириною R = w/100, w – ширина зображення. Згладжування виконуємо σ = h/400, h – висота зображення.

Простежуємо рядка, починаючи з центру кожного фрагмента слова в обидві сторони.



Зміщуємося кожен раз на фіксований крок R по горизонталі і по вертикалі. Значення кута визначаємо по моделі. Робимо пошук локального максимуму у вертикальному стовпчику заввишки ±3 пікселя. Продовжуємо процес з уточненого положення. Критерій зупинки – відсутність локального максимуму або значення максимуму не перевершує шумовий поріг (T = 30).



В результаті дослідження отримуємо набагато більше даних відрізків з уточненим значенням кута нахилу. Уточнюємо нашу модель з використанням цих даних.

Використовуючи отриману з моделі карту кутів, будуємо карту локальних зсувів. При цьому враховуємо кут горизонтальної перспективи в поточній точці:



Зміщення в будь-якій точці множимо на . Це дозволяє «розтягнути» букви в області корінця.

► ► ►

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


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

0 коментарів

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