Обработка и передача изображений

Вид материала

Документы

Содержание Qwc алгоритм вейвлет-сжатия изображений Алгоритм сжатия QWC Q – коэффициент квантования, n Результаты эксперимента Тестирование на качество восстановленного изображения

Подобный материал:

• Обработка и передача изображений, 213.76kb.
• Анализ, обработка и передача динамических изображений в моделях виртуальной реальности, 80.25kb.
• Обработка и передача изображений, 243.48kb.
• Обработка и передача изображений, 149.44kb.
• Обработка и передача изображений, 357.76kb.
• Обработка и передача изображений, 241.81kb.
• 1. Информационные технологии. Структура информационного процесса. Сбор, обработка,, 1016.5kb.
• Обработка и передача изображений, 203.92kb.
• Белорусский государственный университет применение информационных технологий при анализе, 187.23kb.
• Обработка и передача измерительной информации, 201.84kb.

coverings method for calculation FRACTAL dimensions of landscape images

Petukhov N.

Siberian State Aerospace University named after academician M.F.Reshetnev, Russia, Krasnoyarsk

The important problem of computer vision systems is connected with texture analysis. Many methods of texture analysis were developed during last years, however an uncountable variety of natural and artificial textures do impossible to describe universal definition a texture. Landscape images can be interpreted as a set of textural natural fragments and manned object's images.

Often fractal geometry (measurement fractal dimensions D) is used for definition of natural textures. Fractal dimension is the unique characteristic of natural objects. Many papers devote to leaning fractal dimension of natural object's images. But their authors do not focus special attention on that fact, that strict definition of fractal dimensions is applied for the abstract mathematical sets. Natural objects being natural fractals show properties of self-similarity on the limited interval of spatial scales. Accordingly, methods for calculation of fractal dimensions which give correct results for abstract mathematical fractals, can lead inexact (and at times erroneous) to results for natural fractal objects meeting in the nature.

Fractal dimensions D is calculated usually by three algorithms: a method of a covering a surface standards; the dispersive scaling founded on an estimation the law of function distribution of average squares; a dimension estimation on degree of an approximating polynomial function for a spectrum power of process. Now the first method is most extended.

The method of coverings has two kinds of realization: a covering a square grid and a covering a two-dimensional surface. The most simple method realization is a method of coverings, which impose of a square grid on fractal image and calculate number of cages N (r) for fractal gets. When the distance r between parallel lines of grid becomes small enough, ratio ln (r)/ln (1/r) converges to final value, and is considered as fractal dimension.

The method of designing coverings consists in designing of a two-dimensional surface so that quantum values of two-dimensional signal intensity are settled down between two functions, top U and bottom L surfaces. Top surface U contains the set of the points which values always, at least, on one quantum exceed the intensity of an entrance signal. Bottom surface L has values of points, which always low, at least, on one quantum of intensity of the entrance image. These surfaces at a zero scale of scale are equal to the initial image.

The designed covering formed by two specific functions has a thickness 2. For a two-dimensional signal the "surface" area is the volume occupied with a covering and divided on size 2. The area of "surface" of intensity A () within a window of supervision R is calculated the subtraction of points from bottom "surface" to top "surface" with the further summation on all windows. Fractal dimension defines by inclination log A () as function log .

However only fractal dimension hasn't enough for the description of same natural objects, because different fractals can have the identical dimension, but differ by texture parameters. For the description of such textures is used the filling concept. Filling concerns statistical characteristics of the second degree and changes as follows: filling is not enough for a texture with low density, and oversize, when a texture has granular properties.

Now the program allowing calculate the fractal dimension is developed, according to methods specified above. The preliminary analysis shows, that the method of two-dimensional coverings is more exact, because two boundary surfaces are used for recognition of natural objects on the image.




QWC АЛГОРИТМ ВЕЙВЛЕТ-СЖАТИЯ ИЗОБРАЖЕНИЙ

Сидоров Д.В., Осокин А.Н.

Томский политехнический университет

Введение

Стандарт сжатия цифровых изображений JPEG2000 на основе вейвлет-преобразования считается одним из наиболее перспективных. В пределах стандарта существует множество программных реализаций (проприетарные - ACDSee, LeadTools, Mjp2000, Lurawave, свободные – Jasper, JJ2000, и т. д.), значительно отличающихся качеством восстановленного изображения [1]. Главной причиной ограниченного распространения JPEG2000 является сложность программной реализации, низкая скорость сжатия/распаковки и, как следствие, высокие требования к производительности при переносе на аппаратную платформу. Длительность процесса сжатия вызвана в большей степени сложностью этапов квантования, блочного кодирования и организации выходного потока, занимающих порядка 80% общего времени сжатия [2]. Поэтому, на основе стандарта JPEG2000, авторами был разработан более простой и быстрый алгоритм вейвлет-сжатия QWC (Quick Wavelet Compress, название авторов), обладающий практически равным JPEG2000 качеством восстановленного изображения (при одинаковой степени сжатия) и высокой скоростью сжатия/распаковки.

Алгоритм сжатия QWC

Алгоритм QWC имеет аналогичную стандарту JPEG2000 схему сжатия (рис. 1).



Рис. 1. Схема сжатия изображений стандарта JPEG2000 и алгоритма QWC

Этапы предварительной обработки и вейвлет-преобразования стандарта JPEG2000 и алгоритма QWC совпадают.

На этапе квантования, в отличие от стандарта JPEG2000 (где используется равномерный скалярный квантователь), в алгоритме QWC используется субполосный скалярный квантователь с различными коэффициентами квантования для субполос (уровней) высокочастотных вейвлет-коэффициентов. Применение неравномерного квантователя увеличивает качество восстановленного изображения при неизменной степени сжатия, независимо от используемого вейвлет-преобразования [5].

Исходя из специфики вейвлет-преобразования считается, что энергия высокочастотных (ВЧ) субполос HL₁, HH₁, LH₁ при пирамидальном разложении описывает наиболее мелкие детали изображения, следовательно, для этих субполос коэффициент скалярного квантования может быть большим [5, 6]. Субполосы LH₂, HH₂, HL₂ – описывают более крупные детали и обладают большим значением энергии, следовательно, коэффициент квантования для данных полос должен быть меньше. Для субполос уровнем выше (HL₃, HH₃, LH₃ и т. д.) процесс аналогичен: , где Q – коэффициент квантования, n – шаг вейвлет-преобразования.

Указанная выше взаимосвязь распределения энергии между ВЧ субполосами позволяет построить субполосный скалярный квантователь с неравномерным шагом коэффициента квантования. К сожалению, процесс определения зависимости энергий субполос и вычисление соответствующих коэффициентов квантования достаточно длителен, поэтому для ускорения определения коэффициентов квантования было предложено использовать следующую упрощенную зависимость: , где i – уровень разложения коэффициентов или шаг вейвлет-преобразования, L – выравнивающая константа.

В алгоритме сжатия QWC, так же как и в стандарте JPEG2000, главным и достаточным параметром при сжатии, который указывает пользователь, является либо коэффициент сжатия K_с, либо размер сжатого файла. Но коэффициент сжатия не единственный параметр, участвующий в квантовании и арифметическом сжатии, начальный коэффициент квантования Q и поправочный коэффициент L также должны быть заданы. Так как пользователь задает только коэффициент сжатия (размер файла), то нужно определить зависимость коэффициента квантования Q и поправочного коэффициента L от коэффициента сжатия K_с. Теоретическое определение коэффициентов Q и L является достаточно сложным процессом, поэтому для облегчения получения коэффициентов K_с, Q и L был поставлен эксперимент.

Эксперимент

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

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

В качестве исходных данных для эксперимента были использованы эталонные изображения набора цветных изображений Calgary Corpus с глубиной цвета 24 бита на пиксель и пять полутоновых изображений глубиной 8 бит на пиксель, полученных конвертированием без потерь из оригинальных.

Для проведения эксперимента и определения четырех массивов значений коэффициентов Q и L была разработана программа для СКК ТПУ «СКИФ-политех», определяющая на наборе эталонных изображений наиболее оптимальные соотношения коэффициентов K_с, Q и L. Использование кластера ТПУ вызвано большим объемом вычислений и простотой распараллеливания вычислений.

Результаты эксперимента

Результатом работы экспериментальной программы стали 4 массива значений Q и L для цветных и полутоновых изображений, задающие для выбранного пользователем коэффициента сжатия K_с значения коэффициента квантования Q и значение поправочного коэффициента L. В виду невысокого качества оценки изображений по метрике SSIM часть значений массивов Q и L оказались не адекватны, зачастую в массиве значений присутствовали «пробелы» (нулевые или стартовые значения) в значениях коэффициентов. Для исправления ситуации массивы значений коэффициентов Q и L для цветных и полутоновых изображений были кусочно аппроксимированы и сглажены.

Следующий этап сжатия алгоритма QWC – этап блочного кодирования (см. рис. 1). Процесс блочного кодирования алгоритма QWC, в отличие от процесса блочного кодирования в стандарте JPEG2000 [7], был значительно упрощен: исключен алгоритм предсказания, исключено разбиение на независимые блоки, уменьшено количество проходов по изображению при арифметическом сжатии до 1 и инициализация арифметического кодера происходит только 1 раз.

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

Тестирование на качество восстановленного изображения

Согласно проведенному тестированию на пяти изображениях из набора Calgary Corpus (ранее участвовавших в эксперименте) алгоритм QWC проигрывает JPEG2000 (реализация от ACDSee, т.к. согласно [1] обладает наилучшим качеством восстановленного изображения) в среднем 3 % по метрике SSIM. Разработанный алгоритм QWC так же эффективно сжимает и изображения, не участвовавшие в эксперименте. В качестве примера на рис. 2, а, изображен участок произвольного изображения (не участвовавшего в определении коэффициентов, размер изображения 16001200 пикселей, глубина цвета 24 бита), сжатого стандартом JPEG2000 (ACDSee) (рис. 2, б, SSIM=0,70929; K_с=60) и алгоритмом QWC (рис. 2, в, SSIM=0,64978; K_с=60). Экспертная оценка отдает предпочтение изображению сжатому QWC (рис. 2, в) перед JPEG2000 (рис. 2, б), т. к. алгоритм QWC при сжатии сохранил структуру мелких деталей изображения (стебли травы).

а	б	в

Рис. 2. Участок изображения: а) оригинального; б) сжатого стандартом JPEG2000; в) сжатого алгоритмом QWC