артості природних спотворень, ніж різниця в окремих точках.
Однак сканер зазвичай спотворює зразки по-іншому: він спотворює ще й аргументи функцій, тобто зміщує точки на графіку горизонтально. Такі спотворення відповідають поданням f = g про h, причому міра цих спотворень тим більше, чим далі h від тотожної функції. Можливо, інтеграл від (h! - I) 2 добре наближає квадрат шуканого відстані; але горизонтальні спотворення зазвичай змішані з вертикальними, і тому потрібен спосіб, що дозволяє знаходити наближення стійко до вертикальних спотворень.
Пропонований спосіб - не що інше, як модифікація алгоритму з вейвлетами під вимір горизонтальних спотворень. Відрізок ділиться на дві частини, не обов'язково рівно навпіл, але так, щоб інтеграли за двома половин були рівні; потім ділиться ще раз, і так далі. Вище описаний той же самий алгоритм у двовимірному варіанті. p> У програмі при підрахунку різниці елементи підпису додатково множилися на коеффициент, в геометричній прогресії залежить від рівня розрізу. Підібрані експериментально пороги такі: відмова від пари букв, якщо відстань більше 170 (знаменник 0,9, з рівнями важливості), або якщо відстань більше 250 (знаменник 1,15, з рівнями важливості), або якщо відстань більше 215 (Без прогресії і без рівнів важливості). br/>
Отримання монохромних зображень
Алгоритм JB2 вміє стискати тільки монохромні (Чорно-білі, без проміжних сірих кольорів) зображення. Файли формату DjVu можуть містити й зображення в тонах сірого, і кольорові малюнки, але все одно в такому файлі окремо зберігається монохромний малюнок, а окремо додаткова інформація про колір. Тому щоб стиснути в такому вигляді будь-яке зображення, що містить текст, необхідно, спочатку виділити з нього монохромне.
Самий простий спосіб для цього - оголосити всі пікселі темніше половини білого чорними, а решта - білими. Під Linux це виконується командою pgmtopbm-threshold, а під Windows цю операцію виконує стандартний редактор Paint, коли зберігає кольорові картинки як монохромні.
Цей спосіб добре працює тільки тоді, коли зображення вже схоже на монохромне. Однак, якщо в ньому є занадто бліді літери або затемнені поля, то в результаті одні контури можуть пропасти, а інші - з'явитися. Щоб справлятися з такими випадками потрібен алгоритм, який звертає більше уваги на різкість кордонів і правильність ліній, ніж на абсолютну величину кольору.
Пропонований алгоритм - крок у цьому напрямку: він прагне виділити найбільш різкі контури; при цьому в якості побічного ефекту видаляються чорні поля навколо відсканованого листа і між сторінками книги.
Отже, спочатку в зображенні виділяються контури - зв'язкові компоненти ліній рівня (Яскравості), у яких рівень кратний заздалегідь обраної величиною. У програмі ця величина становить одну чверть повного відстані між білим і чорним. При цьому ми будемо вважати, що ця яскравість проходить між рівнями пікселів, і таким чином, контур проходить між пікселями, а не через них. Топологічно кожен контур еквівалентний окружності, і у нього є нескінченна зовнішня і кінцева внутрішня частина. Контур може бути осветляющим (всередині яскравіше) і затемняють (всередині темніше).
Для кожного контуру підраховується В«різкістьВ» - величина, що дорівнює за визначенням модулю суми перепадів яскравості по всіх ребрах контуру (ребро - це частина контуру, що проходить між двома пікселями). Перепад яскравості у ребра дорівнює різниці яскравості того пікселя, який всередині контуру, і того, який зовні. При цьому для контурів, що проходять по краю всього зображення, будемо вважати пікселі, що лежать поза цього краю абсолютно чорними. При скануванні у країв малюнка зазвичай виникають чорні поля; таке рішення штучно робить зовнішні контури цих полів освітлюючими і зменшує їх різкість.
Контури можуть бути вкладені один в одного (точніше, один у нутро іншого). Будемо вважати, що є фіктивний контур, що проходить по краю зображення, в який вкладені всі інші. Тоді контури утворюють орієнтоване дерево по вкладеності, і фіктивний контур - його корінь.
Розфарбуємо контури в чорний і білий кольори так, щоб максимізувати описану нижче функцію. При цьому кожен піксель отримає той колір, який має найбільший внутрішній з містять його контурів.
Побудуємо функцію виграшу від розмальовки дерева контурів, яку треба спрямувати до максимуму. При цьому можна заборонити деякі розмальовки, присвоївши їм спеціальне значення В«мінус нескінченністьВ».
Покладемо виграш рівним сумі по всіх контурах наступної величини. Фіктивний кореневої контур повинен бути білим (цим і досягається видалення полів); ​​таким чином, чорний кореневої контур заборонений. Контур, що має той же колір, що і батько, дає нульовий внесок у виграш. У наступних випадках контуру заборонено мати колір, відмінний від кольору батька: якщо окремий алгоритм для фільтрування непотрібних контурів визнав...
