В программе используются два теста, основанные на этом алгоритме. Численные значения порогов подобраны экспериментально.
В первом тесте знаменатель геометрической прогрессии, по которой убывает уровень важности черных пикселей, равен 0, то есть учитываются только самые важные пиксели. Пусть максимальный уровень важности равен 1, тогда если число штрафных очков меньше 2,1% от площади изображения (считая и белые и черные пиксели), то они признаются одинаковыми; если больше 5%, то заведомо разными.
Во втором тесте знаменатель геометрической прогрессии равен 0,85. Если штраф меньше 3,1% площади, изображения считаются одинаковыми, если больше 7,8% — заведомо разными.
Быстрый отказ для пары разных букв
Для того, чтобы ускорить программу сравнения пары букв, весьма полезно уметь быстро отбрасывать пары разных букв.
Предлагается алгоритм, который генерирует по каждому изображению короткое слово — «подпись». Подпись может иметь любой наперед заданный размер; сейчас в программе ее длина равна 31 байту.
Подписи можно интерпретировать как точки в многомерном евклидовом пространстве и находить расстояние между ними. Абсолютно одинаковые изображения, естественно, попадут в одну точку, а похожие буквы будут близки. Если расстояние слишком большое, то буквы можно считать различными.
Алгоритм работает следующим образом. Прямоугольник буквы разрезается на две части по горизонтали, но не обязательно пополам, а так, чтобы число черных пикселей по обе стороны разреза было примерно равным. Если ни одного черного пикселя не было, то разрез проводится посередине. Затем каждый из двух получившихся прямоугольников разрезается надвое вертикальным разрезом по тому же правилу: число пикселей по разные стороны разреза должно быть примерно равным. Затем каждый из четырех прямоугольников разрезается по горизонтали и так далее, горизонтальные и вертикальные разрезы чередуются.
Положению каждого разреза соответствует число от 0 до 1: 0 соответствует крайнему левому или крайнему верхнему положению, 1 — крайнему правому или крайнему нижнему. Каждый разрез порождает два прямоугольника, которые тоже могут быть разрезаны. Таким образом, получается двоичное дерево, в каждой вершине которого стоит число от 0 до 1. Для хранения в байте числа можно перенормировать в интервал от 0 до 255 и округлить.
Дерево разрезов укладывается в одну последовательность по следующему правилу: весь прямоугольник изображения соответствует первому числу в последовательности; если какой-то прямоугольник соответствует элементу номер п, то прямоугольники, которые из него получились разрезом, соответствуют элементам номер 2п и 2п + 1.
Чтобы уменьшить вес приграничных пикселей и улучшить точность алгоритма, его можно комбинировать с алгоритмом определения важности пикселей, описанным в предыдущем разделе. В этом случае алгоритм проводит разрез так, чтобы сравнять сумму уровней важности черных пикселей по обе стороны разреза.
Изложенный алгоритм основан на следующей идее. Предположим, что имеется два одномерных массива (например, звуки). Их можно представить как две непрерывные функции, / и д. Необходимо определить расстояние между этими функциями, и желательно, чтобы чем вероятнее был переход одного образца в другой под действием каких-то естественных искажений, тем меньше было определяемое расстояние. Естественно очертить круг допустимых элементарных искажений, присвоить каждому из них некую стоимость, и определить расстояниемежду / и д как минимальную стоимость набора элементарных искажений, необходимую, чтобы превратить / в д.
Если считать элементарными искажениями сдвиги точек графика по вертикали, то расстоянием станет что-то вроде интеграла от |/ — д\ точный вид зависит от стоимости, приписываемой элементарным искажениям. Однако вертикальное смещение всего графика на 1 обычно считается меньшим искажением, чем наложение случайного шума, по модулю не превосходящего 0,5. Значит, одинаковое смещение большого числа точек стоит дешевле, чем смещение каждой точки по отдельности.
Алгоритмы, использующие вейвлеты, учитывают это обстоятельство. В простейшем варианте разложение по вейвлетам строится так. Сначала в первый вейв-лет-коэффициэнт записывается среднее значение по всему отрезку. Затем отрезок разрезается на две равные части, и разница в среднем значении в левой и правой части записывается во второй вейвлет-коэффициэнт. Этот процесс разрезаний пополам и выписывания разности в средних продолжается дальше с каждым из полученных отрезков.
Изменение одного вейвлет-коэффициэнта приводит к одинаковому смещению целой группы точек. Таким образом, разница в вейвлет-коэффициэнтах представляет лучшее приближение к стоимости естественных искажений, чем разница в отдельных точках.
Однако сканер обычно искажает образцы по-другому: он искажает еще и аргументы функций, то есть смещает точки на графике горизонтально. Такие искажения соответствуют представлению f = g о h, причем мера этих искажений тем больше, чем дальше hот тождественной функции. Возможно, интеграл от (h! — I)2 хорошо приближает квадрат искомого расстояния; но горизонтальные искажения обычно смешаны с вертикальными, и поэтому нужен способ, позволяющий находить приближение устойчиво к вертикальным искажениям.
Предлагаемый способ — не что иное, как модификация алгоритма с вейвлетами под измерение горизонтальных искажений. Отрезок делится на две части, не обязательно ровно пополам, но так, чтобы интегралы по двум половинам были равны; затем делится еще раз, и так далее. Выше описан тот же самый алгоритм в двумерном варианте.
В программе при подсчете разности элементы подписи дополнительно умножались на коэффициэнт, в геометрической прогрессии зависящий от уровня разреза. Подобранные экспериментально пороги такие: отказ от пары букв, если расстояние больше 170 (знаменатель 0,9, с уровнями важности), либо если расстояние больше 250 (знаменатель 1,15, с уровнями важности), либо если расстояние больше 215 (без прогрессии и без уровней важности).
Получение монохромных изображений
Алгоритм JB2 умеет сжимать только монохромные (черно-белые, без промежуточных серых цветов) изображения. Файлы формата DjVu могут содержать и изображения в тонах серого, и цветные рисунки, но все равно в таком файле отдельно хранится монохромный рисунок, а отдельно добавочная информация о цвете. Поэтому чтобы сжать в таком виде любое изображение, содержащее текст, необходимо, сначала выделить из него монохромное.
Самый простой способ для этого — объявить все пиксели темнее половины белого черными, а остальные — белыми. Под Linux это выполняется командой pgmtopbm -threshold, а под Windows эту операцию выполняет стандартный редактор Paint, когда сохраняет цветные картинки как монохромные.
Этот способ хорошо работает только тогда, когда изображение уже похоже на монохромное. Однако, если в нем есть слишком бледные буквы или затемненные поля, то в результате одни контуры могут пропасть, а другие — появиться. Чтобы справляться с такими случаями, нужен алгоритм, который обращает больше внимания на резкость границ и правильность линий, чем на абсолютную величину цвета.
Предлагаемый алгоритм — шаг в этом направлении: он стремится выделить наиболее резкие контуры; при этом в качестве побочного эффекта удаляются черные поля вокруг отсканированного листа и между страницами книги.
Итак, сначала в изображении выделяются контуры — связные компоненты линий уровня (яркости), у которых уровень кратен заранее выбранной величине. В программе эта величина составляет одну четверть полного расстояния между белым и черным. При этом мы будем считать, что эта яркость проходит между уровнями пикселей, и таким образом, контур проходит между пикселями, а не через них. Топологически каждый контур эквивалентен окружности, и у него есть бесконечная внешняя и конечная внутренняя часть. Контур может быть осветляющим (внутри ярче) и затемняющим (внутри темнее).
Для каждого контура подсчитывается «резкость» — величина, равная по определению модулю суммы перепадов яркости по всем ребрам контура (ребро — это часть контура, проходящая между двумя пикселями). Перепад яркости у ребра равен разности яркости того пикселя, который внутри контура, и того, который снаружи. При этом для контуров, проходящих по краю всего изображения, будем считать пиксели, лежащие вне этого края абсолютно черными. При сканировании у краев рисунка обычно возникают черные поля; такое решение искусственно делает внешние контуры этих полей осветляющими и уменьшает их резкость.
Контуры могут быть вложены друг в друга (точнее, один во внутренность другого). Будем считать, что есть фиктивный контур, проходящий по краю изображения, в который вложены все остальные. Тогда контуры образуют ориентированное дерево по вложенности, и фиктивный контур — его корень.
Раскрасим контуры в черный и белый цвета так, чтобы максимизировать описанную ниже функцию. При этом каждый пиксель получит тот цвет, который имеет самый внутренний из содержащих его контуров.
Построим функцию выигрыша от раскраски дерева контуров, которую надо устремить к максимуму. При этом можно запретить некоторые раскраски, присвоив им специальное значение «минус бесконечность».
Положим выигрыш равным сумме по всем контурам следующей величины. Фиктивный корневой контур должен быть белым (этим и достигается удаление полей); таким образом, черный корневой контур запрещен. Контур, имеющий тот же цвет, что и родитель, дает нулевой вклад в выигрыш. В следующих случаях контуру запрещено иметь цвет, отличный от цвета родителя: если отдельный алгоритм для фильтрования ненужных контуров признал его мусором; если контур осветляющий, а родитель белый; или если контур затемняющий, а родитель черный. Если же родитель затемняющего контура белый, а сам контур черный, или родитель осветляющего контура черный, а сам контур белый, то его вклад в выигрыш равен резкости.