(після очищення або хоча б один чорний піксель стане білим, або все скінчиться). На практиці, однак, їх число приблизно дорівнює половині характерною товщини лінії. Якщо в зображенні є великий чорний ділянка, то алгоритм буде працювати довго, тому в програмі алгоритм застосовується до кожної букви окремо.
У програмі використовуються два тести, засновані на цьому алгоритмі. Чисельні значення порогів підібрані експериментально.
У першому тесті знаменник геометричній прогресії, за якою убуває рівень важливості чорних пікселів, дорівнює 0, тобто враховуються тільки найважливіші пікселі. Нехай максимальний рівень важливості дорівнює 1, тоді якщо число штрафних очок менше 2,1% від площі зображення (рахуючи і білі і чорні пікселі), то вони визнаються однаковими; якщо більше 5%, то завідомо різними.
Під другому тесті знаменник геометричної прогресії дорівнює 0,85. Якщо штраф менше 3,1% площі, зображення вважаються однаковими, якщо більше 7,8% - завідомо різними.
Швидкий відмова для пари різних букв
Для того, щоб прискорити програму порівняння пари букв, вельми корисно вміти швидко відкидати пари різних букв.
Пропонується алгоритм, який генерує по кожному зображенню коротке слово - В«підписВ». Підпис може мати будь-який наперед заданий розмір; зараз в програмі її довжина дорівнює 31 байту.
Підписи можна інтерпретувати як точки в багатовимірному евклідовому просторі і знаходити відстань між ними. Абсолютно однакові зображення, природно, потраплять в одну крапку, а схожі букви будуть близькі. Якщо відстань занадто велике, то букви можна вважати різними.
Алгоритм працює таким чином. Прямокутник букви розрізається на дві частини по горизонталі, але не обов'язково навпіл, а так, щоб число чорних пікселів по обидві сторони розрізу було приблизно рівним. Якщо жодного чорного пікселя НЕ було, то розріз проводиться посередині. Потім кожен з двох одержані прямокутників розрізається надвоє вертикальним розрізом по тому ж правилу: число пікселів по різні сторони розрізу повинно бути приблизно рівним. Потім кожен з чотирьох прямокутників розрізається по горизонталі і так далі, горизонтальні і вертикальні розрізи чергуються.
Положення кожного розрізу відповідає число від 0 до 1: 0 відповідає крайньому лівому або крайнього верхнього положенню, 1 - крайнього правого або крайнього нижнього. Кожен розріз породжує два прямокутники, які теж можуть бути розрізані. Таким чином, виходить двійкове дерево, в кожній вершині якого стоїть число від 0 до 1. Для зберігання в байті кількості можна перенормировать в інтервал від 0 до 255 і округлити. p> Дерево розрізів вкладається в одну послідовність по наступному правилу: весь прямокутник зображення відповідає першому числу в послідовності; якщо якийсь прямокутник відповідає елементу номер п, то прямокутники, які з нього вийшли розрізом, відповідають елементам номер 2п і 2п + 1.
Щоб зменшити вагу прикордонних пікселів і поліпшити точність алгоритму, його можна комбінувати з алгоритмом визначення важливості пікселів, описаним у попередньому розділі. У цьому випадку алгоритм проводить розріз так, щоб зрівняти суму рівнів важливості чорних пікселів по обидві сторони розрізу.
Викладений алгоритм заснований на наступній ідеї. Припустимо, що є два одновимірних масиву (наприклад, звуки). Їх можна представити як дві безперервні функції,/і д. Необхідно визначити відстань між цими функціями, і бажано, щоб ніж найімовірніше був перехід одного зразка в інший під дією якихось природних спотворень, тим менше було обумовлене відстань. Природно окреслити коло допустимих елементарних спотворень, присвоїти кожному з них якусь вартість, і визначити відстань між/і д як мінімальну вартість набору елементарних спотворень, необхідну, щоб перетворити/в д.
Якщо вважати елементарними спотвореннями зрушення точок графіка по вертикалі, то відстанню стане щось на зразок інтеграла від |/- д точний вигляд залежить від вартості, приписується елементарним спотворень. Однак вертикальне зміщення всього графіка на 1 зазвичай вважається меншим спотворенням, ніж накладення випадкового шуму, по модулю не перевершує 0,5. Значить, однакове зміщення великого числа точок коштує дешевше ніж зміщення кожної точки по окремості.
Алгоритми, використовують вейвлети, враховують цю обставину. У найпростішому варіанті розкладання по ВЕЙВЛЕТ будується так. Спочатку в перший вейв-років-коефіцієнти записується середнє значення по всьому відрізку. Потім відрізок розрізається на дві рівні частини, і різниця в середньому значенні в лівій і правій частині записується в другій вейвлет-коефіцієнти. Цей процес розрізання навпіл і виписування різниці в середніх продовжується далі з кожним з отриманих відрізків.
Зміна одного вейвлет-коеффициента призводить до однакового зміщення цілої групи точок. Таким чином, різниця в вейвлет-коефіцієнти представляє краще наближення до в...
