и говорить В«такВ», тому що в іншому випадку ніякої алгоритм класифікації не застрахований від помилок.
Розглянемо всі букви в тексті і застосуємо до кожної пари порівняння. Тепер оголосимо класами зв'язкові компоненти щодо відповіді В«такВ». Це і буде та відповідь, яка видає програма. Однак програма працює швидше за рахунок того, що класів зазвичай набагато (в середньому в 5-10 разів) менше, ніж букв. Крім того, вона враховує відповіді В«ніВ».
Програма працює таким чином. Будемо класифікувати літери по одній, порівнюючи кожну букву з раніше переглянутих. При цьому раніше переглянуті букви вже розбиті на класи.
Отже, візьмемо нову букву і по черзі порівняємо її з усіма наявними класами. Порівняння літери з класом влаштовано так: буква порівнюється з усіма елементами класу до отримання першого відповіді В«такВ» чи В«ніВ», який і оголошується результатом порівняння букви з класом. Якщо всі порівняння дали В«може бутиВ», то результатом порівняння букви з класом буде В«ніВ».
Тепер об'єднаємо букву і всі класи, що дали відповідь В«такВ», в один клас, після чого перейдемо до наступної букви.
Алгоритм порівняння пари букв повинен не помилятися, якщо він говорить В«такВ» чи В«ніВ»; при цьому алгоритм тим краще, ніж менше число разів він говорить В«може бутиВ».
Основний алгоритм порівняння пари букв
У DjVuLibre 3.5 використовується простий алгоритм порівняння пари букв. Зображення накладаються одне на інше і вважається кількість відрізняються пікселів. Якщо ця кількість не перевищує 6% від їх загального числа (в одній з картинок), то букви вважаються однаковими. Поріг в 6% підбирався експериментально і, до речі, іноді дає помилки, ототожнюючи літери В«іВ» і В«нВ».
У цього алгоритму є недолік: він ніяк не враховує специфіку спотворень, що вносяться сканером. Зазвичай сканер не змінює довільні пікселі на протилежні, а спотворює контури зображення. Тому, алгоритм можна поліпшити, якщо оцінити для кожного пікселя ймовірність зміни. Ця ймовірність більше біля кордону букви і менше в її середині.
Пропонується спосіб, що привласнює кожному чорному пікселя зображення рівень важливості; ніж важливіше піксель, тим менша ймовірність, що сканер заступить його на білий. Якщо в парі картинок з двох відповідних один одному пікселів один чорний, а другий білий, то парі картинок нараховуються штрафні очки, пропорційні рівню важливості чорного пікселя. Таким чином, вплив прикордонних пікселів на суму штрафних очок зменшується.
Спосіб полягає в наступному: визначається деякий перетворення чорно-білого зображення - В«очищенняВ». У ході очищення білі пікселі залишаються білими. Після декількох послідовних очисток зображення перестає змінюватися. Чорні пікселі, що вижили всі очищення, оголошуються найбільш важливими; важливість інших чорних пікселів зменшується в геометричній прогресії в міру того, на скільки очисток менше вони витримали.
Кожна очищення виконується в два проходи. При кожному проході послідовно (рядки йдуть зверху вниз, в строчці зліва направо) проглядаються всі пікселі зображення.
Під час першого проходу деякі чорні пікселі можуть бути оголошені кандидатами на видалення. Під час другого проходу деякі кандидати можуть бути видалені, тобто перефарбовані в білий.
Під час першого проходу піксель оголошується кандидатом на видалення, якщо він і його вісім сусідів не розфарбовані ні одним з наступних п'яти способів з точністю до поворотів і відображень:
В
Знаки питання означають, що піксель може бути будь-якого кольору. Таким чином, картинка з чотирма знаками питання еквівалентна шістнадцяти окремим розмальовки.
У випадку якщо піксель лежить на кордоні зображення, його сусіди, що лежать за межами зображення, вважаються білими.
Перші два правила означають, що зв'язність букви щодо переходів від пікселя до одному з його чотирьох сусідів не повинна порушуватися.
Третє правило забороняє видалення одиночних пікселів.
Четверте правило означає, що тільки пікселі з кордону чорного і білого можуть бути видалені.
П'яте правило допомагає зберегти форму літери при очищенні, забороняючи видаляти В«ВиступаючіВ» пікселі. p> Під час другого проходу кандидати на видалення перефарбовуються у білий колір, якщо ці пікселі і їх вісім сусідів не розфарбовані одним із способів, показаних вище на перших чотирьох малюнках. Правило збереження форми втрачає сенс, якщо частину зображення вже очищена, а частина - ні.
Пікселі, що стали білими, беруть участь у наступних тестах вже як білі. Це гарантує збереження зв'язності в зображенні.
Час, необхідну для однієї очищення, пропорційно числу пікселів у зображенні. Час, необхідний для роботи всього алгоритму, більше у стільки разів, скільки потрібно очисток. Їх число заздалегідь обмежено числом чорних пікселів в зображенні плюс один...
