РОЗДІЛ 2
МЕТОДИ ТА АЛГОРИТМИ РОЗПІЗНАВАННЯ РУКОПИСНИХ МАТЕМАТИЧНИХ ТЕКСТІВ
Розроблений програмний комплекс перетворює отриманий за допомогою сканера графічний знімок сторінки вихідного документа, що містить рукописний математичний текст, у її електронне представлення у форматі LaTeX. Під рукописним математичним текстом тут мається на увазі сукупність роздільно-рукописних символів із заданого алфавіту, організована у вигляді окремих рядків, що складають абзаци. Абзаци можуть містити як винятково формули, так і звичайний текст із формульними вставками. В обох випадках формули виділяються спеціальним символом "#". Це пов'язано з тим, що звичайний текст і формули мають різні форми представлення, а їх розділення може бути неоднозначним. Вирішення цієї неоднозначності без використання розділяючого символу вимагає семантичного аналізу контексту та суттєво ускладнює комплекс.
Програмний комплекс складається з декількох функціональних блоків і має таку структуру:
2.1. Представлення вихідних даних
Графічний знімок вихідного документа однозначно задається функцією яскравості , визначеною в області ,
де - кількість піксельних рядків на знімку, - кількість піксельних стовпців на знімку. Для зменшення обсягу оброблюваної інформації діапазон кольорів графічного знімка обмежується відтінками сірого. У цьому випадку функція яскравості приймає цілі значення на відрізку [0; 255]. Значення "0" відповідає мінімальній яскравості (тобто чорному кольору), а значення "255" - максимальній (тобто білому кольору). Для зручності подальшого опису алгоритмів будемо представляти графічний знімок вихідного документа у вигляді матриці розміру , вихідні значення елементів якої визначені функцією яскравості,
, , .
Означення 1. Елементи матриці , значення яких дорівнюють нулю, будемо називати інформаційними, а елементи, значення яких рівні 255, - фоновими.
Означення 2. Графічним об'єктом назвемо сукупність 8-зв'язних інформаційних елементів, де під 8-зв'язністю мається на увазі таке сусідство елементів і , при якому виконуються умови , .
Означення 3. Символом назвемо графічний об'єкт чи сукупність графічних об'єктів, якому чи якій може відповідати деяке ключове слово.
2.2. Попередня обробка вихідного документа
Отриманий за допомогою технічних засобів (наприклад, сканера) графічний знімок вихідного документа проходить попередню обробку, метою якої є усунення шумів та сторонньої інформації. Результатом попередньої обробки є монохромне зображення (тобто зображення, матриця якого містить тільки інформаційні та фонові елементи), на якому в ідеальному випадку присутні тільки символи розпізнаваного тексту. Попередня обробка графічного знімка вихідного документа здійснюється фільтрами двох типів: пороговим та медіанним.
Пороговий фільтр класифікує елементи матриці знімка на інформаційні та фонові відповідно до їхніх значень та встановленого порогу фільтрації.
, , ,
де - поріг фільтрації, який задається користувачем в графічному інтерфейсі програмного комплексу.
При достатній контрастності знімка даний фільтр дозволяє повністю усунути сторонню інформацію зі знімка. У більшості випадків порогового фільтра досить для обробки графічного знімка, отриманого за допомогою сканера. Але якщо на знімку присутній контрастний шум, застосування порогового фільтра приведе до появи помилкових інформаційних та фонових елементів. Зв'язні сукупності помилкових елементів невеликої площі ігноруються при подальшому виділенні символів та обчисленні їх геометричних характеристик. Мінімальна величина площі символу задається користувачем в графічному інтерфейсі програмного комплексу. Уникнути появи сукупностей помилкових елементів можна за допомогою більш точного регулювання порогу фільтрації.
Додатковим засобом для боротьби з виникненням сукупностей помилкових елементів є медіанна фільтрація [108]. Вибираючи різні маски фільтрації, можна отримати гарні результати у боротьбі з контрастним шумом. Недолік даного виду фільтрації - його низька швидкодія у порівнянні з пороговою фільтрацією, тому використовувати її варто тільки в крайньому випадку, коли не вдається одержати бажаний результат за допомогою налаштування порогового фільтра.
2.3. Виділення рядків у вихідному документі
У переважній більшості документів текст, а також формули організовані у вигляді окремих рядків. У межах кожного з рядків між символами існують неявні структурні зв'язки, що поряд із самими символами безпосередньо беруть участь в утворенні змістовного навантаження тексту, але символи з різних рядків таких взаємозв'язків не мають, за винятком, можливо, останнього і першого символу двох суміжних рядків. Цей факт дозволяє автоматично виключити виконання операцій виявлення структурних зв'язків зі свідомо негативним результатом при проведенні аналізу тексту по рядках. Алгоритм виділення рядків використовує у своїй роботі вертикальну гістограму заповнення матриці знімка, що розраховується за формулою
, .
Для чіткого визначення границь кожного з рядків гістограма проходить декілька етапів попередньої обробки.
1. На гістограмі розглядаємо нерозривні області такі, що
, .
2. На першому етапі інвертуємо нерозривні області гістограми , що задовольняють умові
, .
3. На другому етапі інвертуємо нерозривні області гістограми , що задовольняють умові
, .
Означення 4. Інвертуванням нерозривної області гістограми називається перетворення
, .
Границі кожного з рядків визначаються як границі відповідних нерозривних областей на гістограмі, що задовольняють умові , . Значення задається користувачем в графічному інтерфейсі програмного комплексу.
Результатом роботи алгоритму виділення рядків є список об'єктів, що містять характеристичну інформацію про кожен з рядків (посилання на матрицю знімка, місце розташування у вихідному документі). Дана інформація використовується в подальшому алгоритмами групування символів та генерації LaTeX-представлення. Для підвищення робастності проце
- Київ+380960830922