КОМПРЕССИЯ ЗАШУМЛЕННЫХ ИЗОБРАЖЕНИЙ АДАПТИВНЫМ ВЕЙВЛЕТ-КОДЕКОМ
32
УДК 681.7.069.32
Ю. С. БЕХТИН, Д. В. ТИТОВ
КОМПРЕССИЯ ЗАШУМЛЕННЫХ ИЗОБРАЖЕНИЙ АДАПТИВНЫМ ВЕЙВЛЕТ-КОДЕКОМ
Представлен основанный на итеративном извлечении когерентных структур новый метод построения вейвлет-кодеков, предназначенных для компрессии зашумленных изображений.
Ключевые слова: вейвлет, алгоритм, фактор, изображение.
Введение. Современный рынок радиоэлектронных устройств предлагает ряд микрочи-
пов, специально созданных для компрессии видеоданных. Большую их часть составляют так
называемые вейвлет-кодеки (например, ADV6xx фирмы Analog Devices). Такие кодеки бази-
руются на одном из известных методов вейвлет-компрессии изображений, как EZW, SPIHT,
EBCOT, JPEG2000 и др. [1—4]. К сожалению, они малоэффективны при заданной степени
сжатия зашумленных изображений, которые описываются моделью вида [4]:
Y = X +Z,
(1)
где Y — наблюдаемое изображение, X — неизвестный оригинал, Z — не зависящий от ориги-
нала X аддитивный (гауссов) шум с нулевым средним.
Различные методы компрессии зашумленных изображений могут быть разделены на две
группы. Методы первой, например [5, 6], нацелены на достижение максимально возможного
качества декодированных искаженных изображений путем применения такой степени сжа-
тия, при которой достигается наибольшее значение пикового отношения сигнал/шум
(ПОСШ). Подобные методы относительно легко реализовать на существующих микрочипах,
однако при этом не всегда обеспечивается заданная степень сжатия. Методы второй группы
(см. например, [7]) нацелены на поиск оптимального критерия распределения квоты битов.
Однако такие методы содержат громоздкие вычислительные процедуры и пока не могут быть
реализованы на микрочипах.
В настоящей статье предлагается способ сокращения вычислительных процедур, кото-
рый может быть реализован на микрочипах благодаря относительной простоте и быстрой
сходимости алгоритма.
Постановка задачи. Вейвлет-декомпозиция W зашумленного изображения (1) может
быть также представлена в виде аддитивной модели
WY = W (Y ) = W ( X + Z ) = W (X ) + W (Z ) = WX + WΞ ,
(2)
где WX = W ( X ), WΞ = W (Z ) — центрированные и некоррелированные случайные процессы,
причем процесс WΞ условно полагаем нормально распределенным.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 2
Компрессия зашумленных изображений адаптивным вейвлет-кодеком
33
Вейвлет-коэффициенты должны быть подвергнуты пороговой обработке и закодированы. С учетом ошибки равномерного квантования ∆2 = 12σu2q [4], где ∆ — интервал квантования,
значение порога τ может быть приравнено нулевой зоне кодека τ = θ∆ , что дает
τ2 = 12θ2σu2q ,
(3)
где θ — коэффициент, регулирующий отношение между шириной нулевой зоны и интервалом квантования (по умолчанию для многих кодеков θ=1). Значение τ может быть приравне-
но любому вейвлет-коэффициенту τ = wYM , M < I , I — число точек изображения.
Вейвлет-коэффициенты, попавшие в нулевую зону, считаются незначимыми и обнуляются. Следовательно, можно ожидать некоторого шумоподавления при компрессии зашумленных изображений. Тогда средняя квадратическая ошибка (СКО) восстановления оригинала
{ } ∑E WX −WXˆ 2
=
1 I
I
( wX i
i=1
− wXˆi ) 2
=
σ2
− εσ2
+ σW2 ξ
+ εσu2q ,
(4)
∑ ∑где
σ2
=
1 I
I
wY2i
i=1
—
дисперсия
всех
вейвлет-коэффициентов;
σ2
=
1 M
M
wY2i
i=1
— дисперсия
значимых вейвлет-коэффициентов (оставшихся после пороговой обработки), M / I = ε ;
∑σW2 ξ
=
1 I
I i=1
wξ2i
— дисперсия вейвлет-коэффициентов шума с нулевым средним;
∑σu2q
=
1 M
M
σu2q i
i=1
— дисперсия ошибки квантования для M значимых вейвлет-коэффициентов.
Из уравнения (4) следует, что для достижения наибольшего ПОСШ необходимо полу-
чить максимальное значение дисперсии значимых вейвлет-коэффициентов и минимальное —
дисперсии ошибки квантования. Данные требования противоречивы, поскольку большое зна-
чение M, снижающее ошибку аппроксимации, приводит к увеличению ошибки квантования.
Таким образом, необходимо найти оптимальное в смысле минимума СКО (4) значение поро-
га, определяющего число значимых вейвлет-коэффициентов М.
Алгоритм работы кодека. В соответствии с уравнением (4) полученная после компрес-
{ }сии минимальная СКО, записанная в форме E WX − WXˆ 2 , эквивалентна максимуму
( )ε σ2 − σ2uq . Метод функционирования кодека, базирующийся на извлечении М когерентных
структур из зашумленного изображения, представляется в итеративной форме:
f (M ) = ε(σ2 − σu2q ) → max ,
M
(5)
∑ ( )∀ wYi 2 ≥ ρ2I −M I wYi 2 = ρ2I −M I σ2 − εσ2 , i=M +1
(6)
где пороговое значение для коэффициента корреляции между нормальным шумом и любым
вейвлет-базисом определяется как [8]:
max1≤k≤I wξk Z
≤
2 ln I σZ = I σZ
2 ln I I
= ρI .
Оценка Xˆ оригинального изображения является суммой М когерентных структур
(7)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 2
34 Ю. С. Бехтин, Д. В. Титов
{ }∑Xˆ = M W −1 wYk , k =1
(8)
вычисленных через обратное вейвлет-преобразование, которые формируют псевдоизображе-
ния по правилу
MI
{ } { }∑ ∑YM = Y − W −1 wYk =
W −1 wYk .
k =1 k =M +1
(9)
Таким образом, поиск когерентных структур схож с грубой пороговой обработкой вейв-
лет-коэффициентов с величиной порога [8]
∑τ = ρI −M
I wYk 2 .
k =M +1
(10)
Если произведена сортировка всех вейвлет-коэффициентов по амплитуде, предлагае-
мый алгоритм будет содержать следующую последовательность шагов.
1. Положить M = I −1 (инициализация алгоритма).
2. Вычислить кумулятивную сумму квадратов вейвлет-коэффициентов и в соответствии
с (10) вычислить значение порога для данного (текущего) коэффициента корреляции ρI −M .
3. Вычислить новое (скорректированное) значение M числа значимых вейвлет-коэф-
фициентов, используя неравенство (6).
4. Проверить достижение максимума целевой функции (5).
5. Если максимальное значение целевой функции (5) получено, то закончить вычисле-
ния; в противном случае — переход к шагу 2.
Результаты моделирования. К настоящему времени собран достаточно обширный ста-
тистический материал, доказывающий эффективность разработанного кодека. В таблице при-
водятся усредненные численные результаты компрессии четырех тестовых изображений, взя-
тых из библиотеки MatLab [4]. Для сравнения использовались алгоритм компрессии SPIHT и
так называемый „идеальный кодер“ Oracle [3, 8].
Кодек (для 0,2 б/пкс)
ПОСШ, дБ SSIM
Oracle SPIHT Адаптивный вейвлет Oracle SPIHT Адаптивный вейвлет
10 32,24 30,27 31,02 0,89 0,64 0,78
σ2Z
25 29,25 25,89 28,39 0,81 0,58 0,74
35 25,67 24,68 24,58 0,76 0,47 0,69
Аддитивный шум в соотношении (1) моделировался с использованием генератора слу-
чайных чисел, распределенных по нормальному закону с нулевым средним и дисперсией σ2Z ,
изменяющейся в ходе экспериментов. Для кодека использовалось трехуровневое быстрое вейвлет-преобразование на основе биортогонального банка фильтров CDF 9.7 [4]. Численные результаты для ПОСШ и комплексной оценки структурного сходства SSIM (Structural SIMilarity) приведены в таблице. На рис. 1 и 2 показаны результаты применения нового кодека для обработки радиолокационного изображения (для 8 и 0,2 б/пкс соответственно). Как видно из таблицы и рисунков, предложенный алгоритм обеспечивает лучшее восстановление зашумленного изображения как визуально, так и численно по критериям ПОСШ и SSIM.
Эксперименты показали, что предложенный алгоритм имеет относительно быструю сходимость. Это означает, что после трех итераций не наблюдается улучшение восстановленного после компрессии зашумленного изображения. Это важное свойство алгоритма позволяет
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 2
Компрессия зашумленных изображений адаптивным вейвлет-кодеком
35
реализовать его на микрочипах, работающих в реальном масштабе времени. Предлагаемый
алгоритм запрограммирован на ПЛИС фирмы Xilinx с помощью программного обеспечения
ISE версии 6.3 и апробирован с помощью специально разработанного симулятора.
yy
100 100
200 200
300 300
400 400
500 500
600 600
700 700
800 800
900 100 200 300 400 500 600 700 800 900 x
900 100 200 300 400 500 600 700 800 900 x
Рис. 1
Рис. 2
Данная работа выполнена в рамках реализации ФЦП „Научные и научно-педагогические
кадры инновационной России на 2009—2013 гг.“, контракт 16.740.11.0086.
СПИСОК ЛИТЕРАТУРЫ
1. Shapiro J. Embedded image coding using zerotrees of wavelet coefficients // IEEE Trans. on Signal Proc. 1993. Vol. 41. P. 3445—3462.
2. Lewis A. S., Knowles G. Image compression using the 2-D wavelet transform // IEEE Trans. on Image Proc. 1992. Vol. 1, N 2. P. 244—250.
3. Said A., Pearlman W. A. A new fast and efficient image codec based on set partitioning in hierarchical trees // IEEE Trans. on Circ. and Syst. Video Tech. 1996. Vol. 6.
4. Gonzalez R. C., Woods R. E. Digital Image Processing. NY: Addison Wesley, 1992.
5. Ponomarenko N., Lukin V., Zriakhov M., Egiazarian K., Astola J. Estimation of accessible quality in noisy image compression // Proceedings of EUSIPCO. Florence, Italy, 2006. Septеmber.
6. Al-Snaykh O.-K., Mercereau R. M. Lossy compression of noisy images // IEEE Trans. on Image Proc. 1998. Vol. 7, N 12. P. 1641—1652.
7. Chang S. G., Yu B., Vetterli M. Adaptive wavelet thresholding for image de-noising and compression // IEEE Trans. on Image Proc. 2000. Vol. 9, N 9. P. 1532—1546.
8. Mallat S., Zhang Z. Matching pursuits with time-frequency dictionaries // IEEE Trans. on Signal Proc. 1993. Vol. 41, N 12. P. 3397—3415.
Юрий Станиславович Бехтин Дмитрий Витальевич Титов
Сведения об авторах — д-р техн. наук, профессор; Рязанский государственный радиотехниче-
ский университет, кафедра автоматики и информационных технологий в управлении; E-mail: aitu@rgrtu.ryazan.ru — аспирант; Юго-Западный государственный университет, кафедра вычислительной техники, Курск; E-mail: amazing2004@inbox.ru
Рекомендована Юго-Западным государственным университетом
Поступила в редакцию 24.10.11 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 2
УДК 681.7.069.32
Ю. С. БЕХТИН, Д. В. ТИТОВ
КОМПРЕССИЯ ЗАШУМЛЕННЫХ ИЗОБРАЖЕНИЙ АДАПТИВНЫМ ВЕЙВЛЕТ-КОДЕКОМ
Представлен основанный на итеративном извлечении когерентных структур новый метод построения вейвлет-кодеков, предназначенных для компрессии зашумленных изображений.
Ключевые слова: вейвлет, алгоритм, фактор, изображение.
Введение. Современный рынок радиоэлектронных устройств предлагает ряд микрочи-
пов, специально созданных для компрессии видеоданных. Большую их часть составляют так
называемые вейвлет-кодеки (например, ADV6xx фирмы Analog Devices). Такие кодеки бази-
руются на одном из известных методов вейвлет-компрессии изображений, как EZW, SPIHT,
EBCOT, JPEG2000 и др. [1—4]. К сожалению, они малоэффективны при заданной степени
сжатия зашумленных изображений, которые описываются моделью вида [4]:
Y = X +Z,
(1)
где Y — наблюдаемое изображение, X — неизвестный оригинал, Z — не зависящий от ориги-
нала X аддитивный (гауссов) шум с нулевым средним.
Различные методы компрессии зашумленных изображений могут быть разделены на две
группы. Методы первой, например [5, 6], нацелены на достижение максимально возможного
качества декодированных искаженных изображений путем применения такой степени сжа-
тия, при которой достигается наибольшее значение пикового отношения сигнал/шум
(ПОСШ). Подобные методы относительно легко реализовать на существующих микрочипах,
однако при этом не всегда обеспечивается заданная степень сжатия. Методы второй группы
(см. например, [7]) нацелены на поиск оптимального критерия распределения квоты битов.
Однако такие методы содержат громоздкие вычислительные процедуры и пока не могут быть
реализованы на микрочипах.
В настоящей статье предлагается способ сокращения вычислительных процедур, кото-
рый может быть реализован на микрочипах благодаря относительной простоте и быстрой
сходимости алгоритма.
Постановка задачи. Вейвлет-декомпозиция W зашумленного изображения (1) может
быть также представлена в виде аддитивной модели
WY = W (Y ) = W ( X + Z ) = W (X ) + W (Z ) = WX + WΞ ,
(2)
где WX = W ( X ), WΞ = W (Z ) — центрированные и некоррелированные случайные процессы,
причем процесс WΞ условно полагаем нормально распределенным.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 2
Компрессия зашумленных изображений адаптивным вейвлет-кодеком
33
Вейвлет-коэффициенты должны быть подвергнуты пороговой обработке и закодированы. С учетом ошибки равномерного квантования ∆2 = 12σu2q [4], где ∆ — интервал квантования,
значение порога τ может быть приравнено нулевой зоне кодека τ = θ∆ , что дает
τ2 = 12θ2σu2q ,
(3)
где θ — коэффициент, регулирующий отношение между шириной нулевой зоны и интервалом квантования (по умолчанию для многих кодеков θ=1). Значение τ может быть приравне-
но любому вейвлет-коэффициенту τ = wYM , M < I , I — число точек изображения.
Вейвлет-коэффициенты, попавшие в нулевую зону, считаются незначимыми и обнуляются. Следовательно, можно ожидать некоторого шумоподавления при компрессии зашумленных изображений. Тогда средняя квадратическая ошибка (СКО) восстановления оригинала
{ } ∑E WX −WXˆ 2
=
1 I
I
( wX i
i=1
− wXˆi ) 2
=
σ2
− εσ2
+ σW2 ξ
+ εσu2q ,
(4)
∑ ∑где
σ2
=
1 I
I
wY2i
i=1
—
дисперсия
всех
вейвлет-коэффициентов;
σ2
=
1 M
M
wY2i
i=1
— дисперсия
значимых вейвлет-коэффициентов (оставшихся после пороговой обработки), M / I = ε ;
∑σW2 ξ
=
1 I
I i=1
wξ2i
— дисперсия вейвлет-коэффициентов шума с нулевым средним;
∑σu2q
=
1 M
M
σu2q i
i=1
— дисперсия ошибки квантования для M значимых вейвлет-коэффициентов.
Из уравнения (4) следует, что для достижения наибольшего ПОСШ необходимо полу-
чить максимальное значение дисперсии значимых вейвлет-коэффициентов и минимальное —
дисперсии ошибки квантования. Данные требования противоречивы, поскольку большое зна-
чение M, снижающее ошибку аппроксимации, приводит к увеличению ошибки квантования.
Таким образом, необходимо найти оптимальное в смысле минимума СКО (4) значение поро-
га, определяющего число значимых вейвлет-коэффициентов М.
Алгоритм работы кодека. В соответствии с уравнением (4) полученная после компрес-
{ }сии минимальная СКО, записанная в форме E WX − WXˆ 2 , эквивалентна максимуму
( )ε σ2 − σ2uq . Метод функционирования кодека, базирующийся на извлечении М когерентных
структур из зашумленного изображения, представляется в итеративной форме:
f (M ) = ε(σ2 − σu2q ) → max ,
M
(5)
∑ ( )∀ wYi 2 ≥ ρ2I −M I wYi 2 = ρ2I −M I σ2 − εσ2 , i=M +1
(6)
где пороговое значение для коэффициента корреляции между нормальным шумом и любым
вейвлет-базисом определяется как [8]:
max1≤k≤I wξk Z
≤
2 ln I σZ = I σZ
2 ln I I
= ρI .
Оценка Xˆ оригинального изображения является суммой М когерентных структур
(7)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 2
34 Ю. С. Бехтин, Д. В. Титов
{ }∑Xˆ = M W −1 wYk , k =1
(8)
вычисленных через обратное вейвлет-преобразование, которые формируют псевдоизображе-
ния по правилу
MI
{ } { }∑ ∑YM = Y − W −1 wYk =
W −1 wYk .
k =1 k =M +1
(9)
Таким образом, поиск когерентных структур схож с грубой пороговой обработкой вейв-
лет-коэффициентов с величиной порога [8]
∑τ = ρI −M
I wYk 2 .
k =M +1
(10)
Если произведена сортировка всех вейвлет-коэффициентов по амплитуде, предлагае-
мый алгоритм будет содержать следующую последовательность шагов.
1. Положить M = I −1 (инициализация алгоритма).
2. Вычислить кумулятивную сумму квадратов вейвлет-коэффициентов и в соответствии
с (10) вычислить значение порога для данного (текущего) коэффициента корреляции ρI −M .
3. Вычислить новое (скорректированное) значение M числа значимых вейвлет-коэф-
фициентов, используя неравенство (6).
4. Проверить достижение максимума целевой функции (5).
5. Если максимальное значение целевой функции (5) получено, то закончить вычисле-
ния; в противном случае — переход к шагу 2.
Результаты моделирования. К настоящему времени собран достаточно обширный ста-
тистический материал, доказывающий эффективность разработанного кодека. В таблице при-
водятся усредненные численные результаты компрессии четырех тестовых изображений, взя-
тых из библиотеки MatLab [4]. Для сравнения использовались алгоритм компрессии SPIHT и
так называемый „идеальный кодер“ Oracle [3, 8].
Кодек (для 0,2 б/пкс)
ПОСШ, дБ SSIM
Oracle SPIHT Адаптивный вейвлет Oracle SPIHT Адаптивный вейвлет
10 32,24 30,27 31,02 0,89 0,64 0,78
σ2Z
25 29,25 25,89 28,39 0,81 0,58 0,74
35 25,67 24,68 24,58 0,76 0,47 0,69
Аддитивный шум в соотношении (1) моделировался с использованием генератора слу-
чайных чисел, распределенных по нормальному закону с нулевым средним и дисперсией σ2Z ,
изменяющейся в ходе экспериментов. Для кодека использовалось трехуровневое быстрое вейвлет-преобразование на основе биортогонального банка фильтров CDF 9.7 [4]. Численные результаты для ПОСШ и комплексной оценки структурного сходства SSIM (Structural SIMilarity) приведены в таблице. На рис. 1 и 2 показаны результаты применения нового кодека для обработки радиолокационного изображения (для 8 и 0,2 б/пкс соответственно). Как видно из таблицы и рисунков, предложенный алгоритм обеспечивает лучшее восстановление зашумленного изображения как визуально, так и численно по критериям ПОСШ и SSIM.
Эксперименты показали, что предложенный алгоритм имеет относительно быструю сходимость. Это означает, что после трех итераций не наблюдается улучшение восстановленного после компрессии зашумленного изображения. Это важное свойство алгоритма позволяет
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 2
Компрессия зашумленных изображений адаптивным вейвлет-кодеком
35
реализовать его на микрочипах, работающих в реальном масштабе времени. Предлагаемый
алгоритм запрограммирован на ПЛИС фирмы Xilinx с помощью программного обеспечения
ISE версии 6.3 и апробирован с помощью специально разработанного симулятора.
yy
100 100
200 200
300 300
400 400
500 500
600 600
700 700
800 800
900 100 200 300 400 500 600 700 800 900 x
900 100 200 300 400 500 600 700 800 900 x
Рис. 1
Рис. 2
Данная работа выполнена в рамках реализации ФЦП „Научные и научно-педагогические
кадры инновационной России на 2009—2013 гг.“, контракт 16.740.11.0086.
СПИСОК ЛИТЕРАТУРЫ
1. Shapiro J. Embedded image coding using zerotrees of wavelet coefficients // IEEE Trans. on Signal Proc. 1993. Vol. 41. P. 3445—3462.
2. Lewis A. S., Knowles G. Image compression using the 2-D wavelet transform // IEEE Trans. on Image Proc. 1992. Vol. 1, N 2. P. 244—250.
3. Said A., Pearlman W. A. A new fast and efficient image codec based on set partitioning in hierarchical trees // IEEE Trans. on Circ. and Syst. Video Tech. 1996. Vol. 6.
4. Gonzalez R. C., Woods R. E. Digital Image Processing. NY: Addison Wesley, 1992.
5. Ponomarenko N., Lukin V., Zriakhov M., Egiazarian K., Astola J. Estimation of accessible quality in noisy image compression // Proceedings of EUSIPCO. Florence, Italy, 2006. Septеmber.
6. Al-Snaykh O.-K., Mercereau R. M. Lossy compression of noisy images // IEEE Trans. on Image Proc. 1998. Vol. 7, N 12. P. 1641—1652.
7. Chang S. G., Yu B., Vetterli M. Adaptive wavelet thresholding for image de-noising and compression // IEEE Trans. on Image Proc. 2000. Vol. 9, N 9. P. 1532—1546.
8. Mallat S., Zhang Z. Matching pursuits with time-frequency dictionaries // IEEE Trans. on Signal Proc. 1993. Vol. 41, N 12. P. 3397—3415.
Юрий Станиславович Бехтин Дмитрий Витальевич Титов
Сведения об авторах — д-р техн. наук, профессор; Рязанский государственный радиотехниче-
ский университет, кафедра автоматики и информационных технологий в управлении; E-mail: aitu@rgrtu.ryazan.ru — аспирант; Юго-Западный государственный университет, кафедра вычислительной техники, Курск; E-mail: amazing2004@inbox.ru
Рекомендована Юго-Западным государственным университетом
Поступила в редакцию 24.10.11 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 2