BC/NW 2010; №2 (17):10.3

ОБ ОДНОМ МЕТОДЕ АППРОКСИМАЦИИ ИЗОБРАЖЕНИЯ

ДЛЯ ПРЕДИКТИВНОЙ СХЕМЫ СЖАТИЯ

Чернов П.А.

(Московский энергетический институт (технический университет), Россия)

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

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

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

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

Вопрос 1). Реализации метода SPIHT отличаются относительно невысокой вычислительной сложностью [6]. Данный метод является прогрессивным, позволяет остановить процесс кодирова-ния/декодирования в любой момент, и при этом возможно получить некое восстановленное изображение. Метод SPIHT обеспечивает восстановленное изображение наилучшего качества для коэффициента сжатия, определяемого моментом останова процесса кодирова-ния/декодирования, т.е. не требуется оптимизация каких-либо параметров сжатия для получения восстановленного изображения наилучшего качества при заданном коэффициенте сжатия.

На практике может оказаться, что минимальный коэффициент сжатия без потерь исходного изображения обеспечивает аппроксимация, полученная путем сжатия с потерями исходного изображения с коэффициентом сжатия из некоторого небольшого подинтервала интервала (0,1). Тогда не требуется выполнять кодирование/декодирование вейвлет-коэффициентов по методу SPIHT после достижения коэффициента сжатия соответствующего правой границе подинтервала. Чем меньше правая граница подинтервала, тем быстрее будет выполнено кодирование/декодирование вейвлет-коэффициентов.

Недостатки метода SPIHT. При очень низких коэффициентах сжатия существуют методы обеспечивающие восстановленное изображение существенно лучшего качества [7]. Классическая реализация метода SPIHT предполагает сосредоточение энергии изображения в низкочастотной области, что выполняется не всегда.

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

Выполнение дискретного вейвлет-преобразования может быть ускорено путем перенесения вычислений с центрального процессора на видеокарту с графическим процессором. В работе [8] было показано, что данный прием позволяет ускорить выполнение ДВП примерно в 20 раз. Сами видеокарты являются массовым и относительно недорогим продуктом.

Авторская реализация дискретного вейвлет-преобразования и кодирования вейвлет-коэффициентов по методу SPIHT, с использованием особенностей прогрессивного сжатия, позволила получить 7 аппроксимаций в секунду на одном ядре центрального процессора Intel Core2Quad q6600 (ядро Kentsfield) 2.4 ГГц с 4 Гбайт ОЗУ (DDR3, 1333 МГц, двухканальный режим), операционная система Windows XP SP2. Аппроксимации были получены с коэффициентом сжатия из полуинтервала (0, 0.1]. Тестовое изображение «Lena»: 512*512 точек, формат BMP, 24 бита на точку. Профилирование программы показало, что около 90% времени уходит на выполнение дискретного вейвлет-преобразования. С учетом возможности ускорения выполнения дискретного вейвлет-преобразования силами видеокарты и задействования всех ядер процессора видятся достижимыми скорости генерации более 70 аппроксимаций в секунду.

Вопрос 2). Получив 70 аппроксимаций в секунду, желательно иметь возможность оценивать их со сравнимыми скоростями.

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

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

Третий способ – использование существующих метрик оценки качества аппроксимации, таких как отношение пикового сигнала к шуму (PSNR), или разработка новых.

Реализован алгоритм сжатия с потерями, использующий дискретное вейвлет преобразование CDF 9/7 и кодирование вейвлет-коэффициентов по методу SPIHT, генерирующий серии аппроксимаций. Планируется повысить скорость генерации аппроксимаций за счет перенесения выполнения дискретного вейвлет-преобразования на видеокарту с использованием OpenCL, поддержка которого имеется на уровне драйверов устройств производства NVidia и AMD.

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

При декодировании выполнять подбор аппроксимации не требуется, т.к. она передается декодеру. Метод сжатия получается несимметричным.

ЛИТЕРАТУРА

1. Чернов П.А., Гольцов А.Г. Применение аппроксимации в предиктивной схеме сжатия изображений // Труды XVII международной научно-технической конференции «Информационные средства и технологии». 20-22 октября 2009 г., Москва. В 3 томах. Т.2. – М.: Издательский дом МЭИ, с. 249-252.

1. Pearlman W.A., Said A. Set Partition Coding: Part I of Set Partition Coding and Image Wavelet Coding Systems // Foundations and Trends in Signal Processing. Vol. 2. №2. P. 95-180, Now Publishers, Delft, The Netherlands, 2008.

2. Pearlman W.A., Said A. Image Wavelet Coding Systems: Part II of Set Partition Coding and Image Wavelet Coding Systems // Foundations and Trends in Signal Processing. Vol. 2. №3. P. 181-246, Now Publishers, Delft, The Netherlands, 2008.

3. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы / под ред. В.М. Курейчика. – 2-е изд., испр. и доп. – М.: Физматлит, 2006. – 320 с.

4. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы: пер. с польск.
И.Д. Рудинского. М.: Горячая линия – Телеком, 2006. – 452 с.

5. Said A., Perlman W.A. A New Fast and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees // IEEE Trans. CSVT. – 1996. Vol. 6. №3. P. 243-250.

6. Moinuddin A. A., Khan. E. Wavelet based embedded image coding using unified zero-block-zero-tree approach // Proceedings on IEEE International Conference on Acoustics, Speech and Signal Processing. 2006. Vol. 2. Pp. 453–456.

7. Чобану М.К., Волков М.В. Цифровая обработка многомерных сигналов: предпосылки прорыва. // Электроника: НТБ. Вып. №3. М.: Техносфера, 2007. С. 64-73.