Бинарный поиск

Для упорядоченных линейных списков существуют более эффективные алгоритмы поиска, хотя и для таких списков применим последовательный поиск. Бинарный поиск состоит в том, что ключ V (в нашем примере 0,341) сравнивается со средним элементом списка. Если эти значения окажутся равными, то искомый элемент найден, в противном случае поиск продолжается в одной из половин списка. Нахождение элемента бинарным поиском осуществляется очень быстро. Max бинарного поиска равен log2(N). Недостаток бинарного поиска заключается в необходимости последовательного хранения списка, что усложняет операции добавления и исключения элементов.

Алгоритм, оперирующий двоичными дробями.

Двоичная дробь задается как 0,а₁,а₂,а₃,…а_i = а₁1/2 + а₂ 1/4 + а₃ 1/8 + …+ а_i 1/2ⁱ. Таким образом, при сжатии в дробь дописываются дополнительные знаки до тех пор, пока получившееся число не попадет в интервал, соответствующий закодированной последовательности символов. Получившееся число полностью задает закодированную последовательность при аналогичном алгоритме декодирования.

Фрактальный алгоритм.

Фрактальное сжатие основано на том, что в более компактной форме изображение представляется с помощью коэффициентов системы итерируемых функций (Iterated Function System –IFS). Прежде чем рассматривать процесс сжатия, разберем, как IFS строит изображение – процесс декомпрессии. IFS представляет собой набор трехмерных преобразований (аффинных преобразований), в случае обработки изображений переводящих одно изображение в другое, то есть преобразованию подвергаются точки в трехмерном пространстве (координаты х, y, яркость). Наглядно этот процесс иллюстрируется при помощи понятия “фотокопировальной машины”, состоящей из экрана, на котором присутствует исходное изображение, и системы линз, которые проецируют изображение на другой экран. При этом:

- линзы могут проецировать часть изображения произвольной формы в любое другое место нового изображения;

- области, в которые проецируются изображения, не пересекаются;

- линза может менять яркость и уменьшать контрастность;

- линза может зеркально отражать и поворачивать свой фрагмент изображения;

- линза должна масштабировать (причем только уменьшая) свой фрагмент изображения.

Расставляя линзы и меняя их характеристики, можно управлять получаемым изображением. Одна итерация работы машины заключается в том, что по исходному изображению с помощью проектирования строится новое, после чего новое берется в качестве исходного. Утверждается, что в процессе итераций получается изображение, которое перестает изменяться. Оно будет зависеть только от расположения и характеристик линз и не будет зависеть от исходного изображения. Это изображение называется неподвижной точкой или аттрактором данной IFS. Соответствующая теория гарантирует наличие ровно одной неподвижной точки для каждой IFS.

Поскольку отображение линз является сжимающим, каждая линза в явном виде задает самоподобные области в нашем изображении. Благодаря самоподобию получается сложная структура изображения при любом увеличении. Таким образо, интуитивно понятно, что система итерируемых функций задает фрактал (нестрогое толкование термина – самоподобный математический объект). Наиболее известны два изображения, полученные с помощью IFS: треугольник Серпинского и папоротник Барнсли. Треугольник Серпинского задается тремя, а папоротник Барнсли четырьмя аффинными преобразованиями (или в нашей терминологии – “линзами”). Каждое изображение кодируется считанным числом байтов, в то время как изображение, построенное с их помощью, может занимать несколько мегабайт. На рис. 7 показан принцип построения треугольника Серпинского.

Рис. 7 Треугольник Серпинского.

Оставляя теоретическое обоснование фрактальной компрессии за рамками курса, рассмотрим основные особенности алгоритма, его достоинства и недостатки.

Итак, системе итерируемых функций однозначно ставится в соответствие неподвижная точка – изображение. Процесс компрессии заключается в поиске коэффициентов системы, а процесс декомпрессии – в проведении итераций системы до стабилизации полученного изображения (неподвижной точки IFS). На практике бывает достаточно 7 – 16 итераций.

Для построения алгоритма введем следующие определения: доменной областью - Д - называется область изображения, для которой ищется ей соответствующая на другом изображении, ранговй областью – Р - называется область изображения, соответствующая доменной.

Очевидно, что основной задачей при компрессии фрактальным алгоритмом является нахождение соответствующих аффинных преобразований. В самом общем случае можно переводить любые по размеру и форме области изображения, однако число перебираемых вариантов разных фрагментов оказывается астрономическим. Поэтому введем (в учебных целях) следующие ограничения:

- все области являются квадратами со сторонами, параллельными сторонам изображения, т.е. аппроксимация всего многообразия геометрических фигур производится квадратами;

- при переводе доменной области в ранговую уменьшение размеров производится ровно в два раза, что существенно упрощает и компрессор, и декомпрессор;

- все доменные блоки – квадраты и имеют фиксированный размер, изображение равномерной сеткой разбивается на набор доменных блоков;

- доменные области берутся “через точку” по осям Х и У, что сразу уменьшает перебор в четыре раза;

- при переводе доменной области в ранговую поворот куба возможен только на 0, 90, 180, 270 градусов, с общим числом преобразований (считая пустое) равным 8, возможно зеркальное преобразование;

- масштабирование (сжатие) по вертикали (яркости) осуществляется в фиксированное число раз -0,75.

Эти ограничения позволяют:

1. Построить алгоритм, для которого требуется сравнительно малое число операций даже на достаточно больших изображениях.

2. Компактно представить данные для записи в файл. На каждое аффинное преобразование в IFS:

- два числа для того, чтобы задать смещение доменного блока (если ограничиться входным изображением размером 512х512), достаточно 8 бит на каждое число;

- три бита для того, чтобы задать преобразование симметрии при переводе доменного блока в ранговый;

- 7 – 9 бит для того, чтобы задать сдвиг по яркости при переводе.

Информацию о размере блоков можно хранить в заголовке файла. Таким образом, на одно аффинное преобразование затрачено менее 4 байт. В зависимости от того, каков размер блока, можно высчитать, сколько блоков будет в изображении. Например, для файла в градациях серого 256 цветов 512х512 пикселов при размере блка 8 пикселов аффинных преобразований будет 4096 (512/8x512/8). На каждое потребуется по 3,5 байта. Следовательно, если исходный файл занимал 512х512 = 262144 байт (без учета заголовка), то файл с коэффициентами будет занимать 14336 байт. Степень сжатия – 18 раз. Файл с коэффициентами может также обладать избыточностью, и может быть подвергнут дальнейшей обработке.

Отрицательные стороны предложенных ограничений:

- поскольку все области являются квадратами, невозможно воспользоваться подобием объектов, по форме далеких от квадратов (в реальных изображениях подобие встречается часто);

- невозможно воспользоваться подобием объектов в изображении, коэффициент подобия между которыми сильно отличается от двойки;

- алгоритм не сможет воспользоваться подобием объектов в изображении, угол между которыми не кратен 90 градусам.

Такова плата за скорость компрессии и за простоту упаковки коэффициентов в файл. Сам алгоритм упаковки сводится к перебору всех доменных блоков и подбору для каждого соответствующего ему рангового блока.

Для каждого рангового блока делается проверка со всеми возможными доменными блоками (в том числе с прошедшими преобразование симметрии), находится вариант с наименьшим среднеквадратическим отклонением, после чего коэффициенты этого преобразования сохраняются в файл. Коэффициенты – это: координаты найденного блока, числа от 0 до 7, характеризующие преобразование симметрии (поворот, отражение блока), сдвиг по яркости для этой пары блоков.

Декомпрессия алгоритма фрактального сжатия достаточно проста. Необходимо провести несколько итераций трехмерных аффинных преобразований, коэффициенты которых были получены на этапе компрессии. В качестве начального может быть взято абсолютно любое изображение (например, абсолютно черное), поскольку соответствующий математический аппарат гарантирует сходимость последовательности изображений, получаемых в ходе итераций IFS, к неподвижному изображению (близкому к исходному). Поскольку коэффициенты для ранговых блоков (которые в наше частном случае являются квадратами одинакового размера)записывались последовательно, получается, что при декомпрессии последовательно заполняется изображение по квадратам сетки разбиения с использованием аффинного преобразования. При обработке полноцветного изображения алгоритмом операции выполняются таким же образом.

Таким образом, мы рассмотрели ряд методов обработки и алгоритмов сжатия данных, отличных от методов, изложенных в материалах предыдущих лекций. Изложенный материал демонстрирует многообразие подходов к проблеме обработки изображений и звука. В определенной мере показаны нерешенные проблемы, обозначены направления поиска решения задач общего и частного характера.

ЛИТЕРАТУРА:

1. Красильников Н.Н. Цифровая обработка изображений М.: “Вузовская книга” 2001 г. стр. 33 – 101, 136 – 144.

2. Ватолин Д., Ратушняк А., Cмирнов М., Юкин В. Методы сжатия данных. М.: “Диалог – МИФИ” 2003 г. Стр. 35 – 42, 67 – 75, 321 – 333.

13