QUANTIZATION NOISE ANALYSIS FOR DISCRETE WAVELET TRANSFORM IMAGE FILTERING


Cite item

Full Text

Abstract

This paper solves an analysis problem for the quantization noise caused by the rounding of the coefficients of discrete wavelet transform (DWT) filters and its influence on the image processing result in order to determine the minimum bit-width of coefficients at which the quantization noise does not have a significant effect on the image processing result or does not affect it at all. The implementation of the DWT method is proposed, which makes it possible to determine the effective bit-width of the wavelet-filter coefficients and simplify the rounding operations. Formulas are derived for determining the minimum bit-width of the coefficients at which the DWT restored image shows the high quality (40 dB) or matches the original one, depending on the wavelet used. Simulation of image DWT using the bit-width calculated according to the derived formulas confirms the results obtained. All calculations are performed only on fixed-point numbers.

Full Text

Введение Методы цифровой обработки изображений (ЦОИ) широко используются в различных областях науки и техники [1-2]: медицине, биологии, физике, астрономии, а также в промышленной, оборонной и правоохранительной сферах деятельности. Одними из актуальных задач ЦОИ являются очистка от шума и сжатие [1-3]. Для решения этих задач на практике используются различные преобразования, наиболее распространенными из которых являются преобразование Фурье (стандарт JPEG) [4] и вейвлет-преобразование (стандарт JPEG 2000) [5-6]. При аппаратной реализации дискретного вейвлет-преобразования (ДВП) на современных устройствах (FPGA, ASIC и др.) [7-8] возникает вопрос о разрядности коэффициентов фильтров ДВП, эффективной с точки зрения затрачиваемых ресурсов, и, в тоже время, необходимой для достижения результатом обработки высокого качества. В материалах по аппаратной реализации ДВП на FPGA [9-11], CUDA [12-13] и CBIC [14] данный вопрос не исследован. В [15] авторы частично затрагивают этот вопрос, однако они лишь определяют число дополнительных разрядов, необходимых для минимизации погрешности, возникающей в результате округления переменных после выполнения операций на разных этапах ДВП. В работе будет решена задача анализа шума квантования [16-17], возникающего в результате округления коэффициентов фильтров ДВП, и его влияния на результат обработки изображений с целью определения минимальной разрядности коэффициентов, при которой шум квантования не оказывает существенного влияния на результат обработки изображений или вовсе не влияет на него. Будет предложена реализация метода ДВП изображений, призванная уменьшить влияние шума квантования на результирующую погрешность вычислений. Также будут предложены формулы расчета минимальной разрядности коэффициентов фильтров ДВП для аппаратной реализации метода. В исследуемом методе все данные представлены в формате с фиксированной точкой, что открывает возможность эффективной аппаратной реализации на современных устройствах (FPGA, ASIC и др.). Основы ДВП изображений Представим цифровое изображение из строк и столбцов как функцию где и пространственные координаты . Значения пикселей зависят от типа изображения. В данной статье мы акцентируем внимание на полутоновых и цветных изображениях. Таким образом, значения пикселей представляются в виде для полутоновых изображений и для цветных, где номер цвета (например, красный, зеленый и синий, соответственно). ДВП изображения осуществляется путем последовательного наложения на изображение набора вейвлет-фильтров. Схема двумерного одноуровневого ДВП изображений, представленная на рисунке 1, имеет ввиду следующие этапы действий. Рисунок 1. Схема ДВП изображений 1. Анализ строк производится путем разложения изображения по строкам низкочастотным и высокочастотным фильтрами ДВП и понижающей в два раза дискретизации . 2. Анализ столбцов производится путем разложения коэффициентов, полученных на первом этапе, по столбцам аналогично анализу строк. В результате анализа (прямого двумерного ДВП) исходного изображения мы получаем четыре набора коэффициентов разложения изображения , называемых аппроксимирующими (низкочастотными) и детализирующими (высокочастотными: горизонтальными, вертикальными и диагональными соответственно. 3. Синтез столбцов производится путем повышающей в два раза дискретизации коэффициентов разложения изображения по столбцам и дополнением нулями, восстановления низкочастотным и высокочастотным фильтрами ДВП и суммирования соответствующих результатов. 4. Синтез строк производится для коэффициентов, полученных на третьем этапе, по строкам аналогично синтезу столбцов. В результате синтеза (обратного двумерного ДВП) коэффициентов происходит восстановление исходного изображения . Теоретически, исходное изображение должно быть полностью восстановлено. Однако на практике возникает шум квантования, обусловленный цифровым форматом представления информации. Будем считать, что вейвлет-фильтры состоят из коэффициентов , где - обозначение фильтра ДВП; - номер коэффициента; - число коэффициентов вейвлет-фильтра. Операция наложения данного фильтра называется сверткой и выполняется следующим образом: где - результат свертки по строкам; - результат свертки по столбцам. Далее будем рассматривать только вейвлеты с компактным носителем. Коэффициенты вейвлет-фильтров связаны соотношениями [2]: (1) Возникает вопрос о минимальной разрядности коэффициентов фильтров ДВП, эффективной с точки зрения аппаратной реализации на современных устройствах, и необходимой для достижения восстановленным изображением высокого качества. Для ответа на этот вопрос необходимо преобразовать коэффициенты в формат с фиксированной точкой. Сделаем это следующим образом: умножим их на и округлим к большему . При этом разрядность коэффициентов фильтров ДВП можно определить по формуле . Значения пикселей обработанного изображения необходимо нормировать следующим образом: все полученные в результате восстановления изображения значения разделить на (так как операция свертки выполняется четыре раза), и округлить к меньшему , что частично или полностью компенсирует погрешность округления коэффициентов фильтров ДВП, в зависимости от ее величины. В качестве критерия оценки качества обработки изображений используется числовая характеристика , или пиковое отношение сигнал-шум, между двумя изображениями (оригиналом и полученным изображением ), вычисляемая следующим образом [18]: где - максимальное значение яркости пикселей изображений; - среднеквадратическое отклонение (СКО) значений яркости изображения , определяемое для полутоновых [18] и цветных [19] изображений по формулам Характеристика имеет логарифмическую природу и измеряется в децибелах, дБ. Чем лучше качество обработки изображения, тем больше величина . Для одинаковых (тождественно равных) изображений . Качество обработки изображения считается высоким, если , так как значение 40 дБ описывает разницу между двумя изображениями, практически незаметную для зрителя [18]. Теоретический анализ максимальной погрешности метода ДВП изображений Изначально погрешность возникает в результате преобразования коэффициентов фильтра ДВП (шум квантования). Затем она возрастает при свертке, повышающей дискретизации и сложении результатов сверток. Округление после нормирования значений восстановленного изображения так же оказывает влияние. Отметим следующие важные факты. 1. Абсолютная погрешность метода ДВП максимальна, когда максимальны все значения яркости пикселей изображения. 2. Согласно формуле (1), рассматриваемые анализирующие и синтезирующие вейвлет-фильтры состоят из одинаковых коэффициентов, следовательно, и максимальные абсолютные погрешности вычислений так же будут равны. По этой причине в рамках теоретических расчетов вейвлет-фильтры подразделяются только на низкочастотные и высокочастотные . 3. Суммы коэффициентов низкочастотных и высокочастотных вейвлет-фильтров равны и соответственно. Введем обозначения: - предельная абсолютная погрешность (ПАП) вычисления значения коэффициента изображения на -ом этапе, возникшая в результате свертки с последовательностью вейвлет-фильтров ; - точное значение суммы коэффициентов вейвлет-фильтра ; - точное значение вычислений на -ом этапе, после свертки с последовательностью вейвлет-фильтров . В результате повышающей дискретизации погрешности для всех коэффициентов разложения изображения подразделяются на две группы (рис. 2, где ) и ). В ходе восстановления изображения повышающая дискретизация применяется дважды. В результате мы получаем четыре группы погрешностей , где . Таким образом, к введенным обозначениям необходимо добавить дополнительный индекс , обозначающий вычисления по пространственным характеристикам коэффициентов. Рисунок 2. Схема подразделения погрешностей при повышающей дискретизации Рассмотрим алгоритм проведения теоретических расчетов для оценки максимальной погрешности вычислений метода одноуровневого ДВП изображений. Этап 1. Округление коэффициентов вейвлет-фильтров. Вычислим точные значения сумм и этих коэффициентов и погрешности и округления коэффициентов вейвлет-фильтров и в большую сторону, : Этап 2. Разложение по строкам. Вычислим точные значения и погрешности свертки с вейвлет-фильтрами и по строкам: Все , представляющие собой результат свертки с фильтром , равны нулю. Этап 3. Разложение по столбцам. Вычислим точные значения и погрешности свертки с вейвлет-фильтрами и по столбцам: Этап 4. Восстановление по столбцам. Вычислим точные значения и погрешности свертки с вейвлет-фильтрами и по столбцам, где : Этап 5. Суммирование по столбцам. Вычислим погрешности сумм , Этап 6. Восстановление по строкам. Вычислим точные значения и погрешности свертки с вейвлет-фильтрами и по строкам, : Этап 7. Суммирование по строкам. Вычислим погрешности сумм , : Этап 8. Нормирование коэффициентов. Вычислим погрешности деления на , : Этап 9. Округление восстановленных значений. Вычислим погрешности округления вниз ; : Полученные значения представляют собой результирующую погрешность и позволяют вычислить характеристику оценки качества обработки изображения (2) где . Далее представим сравнение результатов расчетов по формуле (2) с данными моделирования. Моделирование метода ДВП изображений Моделирование проведено в программной среде MatLab версии R2017b для 8-битного полутонового изображения «Лена». Для обработки использованы вейвлеты Добеши , . Вейвлет-фильтры Добеши получены с помощью команды «wfilters» [20]. Разложение и восстановление изображения осуществлены с помощью команд «dwt2» и «idwt2» [20] соответственно. Моделирование, как и теоретический анализ, осуществлено в соответствии с предложенной реализацией метода ДВП изображений. Пример обработки изображения «Лена» вейвлетом представлен на рисунке 3. Видно, что при увеличении разрядности качество обработки постепенно улучшается: при изображение засветлено; тогда как при восстановленное изображение неотличимо на глаз от исходного; а при восстановленное изображение тождественно равно исходному. Таблица 1. Значения , при которых изображение достигает качества в дБ и Результаты 40 Теоретические 9 11 11 11 12 12 12 12 13 13 Практические 9 10 10 10 11 11 11 12 12 12 Разница 0 1 1 1 1 1 1 0 1 1 Теоретические 12 13 13 14 14 14 14 14 15 15 Практические 10 12 12 12 13 13 13 13 13 14 Разница 2 1 1 2 1 1 1 1 2 1 а) б) в) г) Рисунок 3. Результат обработки изображения «Лена» вейвлетом : а) исходное изображение; б) , дБ; в) , дБ; г) , . В таблице 1 представлены значения , при которых, согласно результатам теоретического анализа - см. формуле (2) и моделирования, восстановленное после одноуровневого ДВП вейвлетами Добеши , изображение достигает качества в дБ и , а также разница между ними. На основе данных из таблицы 1 мы можем сделать следующие выводы. 1. Величину и разрядность , при которых результат одноуровневого ДВП изображений не содержит искажений, видимых зрителю , можно определить по формуле (3) где - число коэффициентов фильтров ДВП. 2. Степень множителя и разрядность , при которых результат одноуровневого ДВП изображений не содержит искажений , можно определить по формуле (4) Формулы (3) и (4) являются приближенными. Получаемые при их использовании значения иногда избыточны, то есть превышают разрядности, представленные в таблице 1. 3. При моделировании метода одноуровневого ДВП для коэффициентов вейвлет-фильтров в среднем потребовалось на один разряд меньше, чем в результатах теоретических расчетов. Наличие данной разницы объясняется направленностью проведения теоретических расчетов на определение максимальной погрешности вычислений. Аппаратная реализация исследуемого метода обладает следующими преимуществами: - скорость выполнения операций с числами в формате с фиксированной точкой существенно выше, чем в формате с плавающей точкой; - операции умножения и деления на в двоичной записи числа соответствуют сдвигу запятой на знаков вправо или влево соответственно, что существенно упрощает и ускоряет их выполнение; - округление к большему и к меньшему аналогично отсечению дробной части числа с увеличением целой части на единицу, в случае округления к большему. Это позволяет избежать трудностей, связанных с определением цифр дробной части округляемых чисел; - при использовании конкретного вейвлета можно достичь сокращения используемых ресурсов, так как старшие информационные разряды большинства коэффициентов фильтров ДВП равны нулю. Заключение В статье решена задача анализа шума квантования, возникающего в результате округления коэффициентов фильтров ДВП, и его влияния на результат обработки изображений с целью определения минимальной разрядности коэффициентов, при которой шум квантования не оказывает существенного влияния на результат обработки изображений или вовсе не влияет на него. Разработанный метод позволяет рассчитать максимальную погрешность вычислений, которая может возникнуть в результате одноуровневого ДВП изображения согласно (2). Формулы (3)-(4) позволяют определить минимальную разрядность коэффициентов вейвлет-фильтров, при которой результат одноуровневого ДВП изображения достигает высокого качества или не отличается от исходного, в зависимости от используемого вейвлета. Все данные представлены в формате с фиксированной точкой и упрощенным выполнением операций округления. Полученные результаты открывают возможность для эффективной аппаратной реализации метода одноуровневого ДВП на современных устройствах (FPGA, ASIC и др.) для очистки от шума и сжатия изображений в медицине, биологии, физике, астрономии, а также в промышленной, оборонной и правоохранительной сферах и других областях науки и техники.
×

About the authors

Nikolai Ivanovich Chervyakov

North-Caucasus Federal University

Email: ncherviakov@ncfu.ru

Pavel Alekseevich Ljahov

North-Caucasus Federal University

Email: ljahov@mail.ru

Nikolay Nikolaevich Nagornov

North-Caucasus Federal University

Email: sparta1392@mail.ru

References

  1. Gonzalez R.C., Woods R.E. Digital Image Processing, 3rd ed. - Prentice Hall, 2007. - 976 p.
  2. Bovik A. Handbook of Image and Video Processing, 2nd ed. - Academic Press, 2005. - 1412 p.
  3. Shih F.U. Image Processing and Pattern Recognition: Fundamentals and Techniques. - Wiley-IEEE Press, 2010. - 552 p.
  4. Vetterli M., Kovacevic J., Goyal V.K. Foundations of Signal Processing. Cambridge University Press, 2014. - 715 p.
  5. Daubechies I. Ten Lectures on Wavelets. - Society for Industrial and Applied Mathematics, 1992. - 380 p.
  6. Mallat S. A Wavelet Tour of Signal Process the Sparse way, 3rd ed. Academic Press, 2009. - 824 p.
  7. Tan L., Jiang J. Digital Signal Processing: Fundamentals and Applications, 2nd ed. - Academic Press, 2013. - 876 p.
  8. Bailey D.G. Design for Embedded Image Processing on FPGAs. - Wiley-IEEE Press, 2011. - 496 p.
  9. Liu Y., Lai E.M.-K. Design and implementation of an RNS-based 2-D DWT processor // IEEE Transactions on Consumer Electronics. - 2004. - Vol. 50(1). - P. 376-385. doi: 10.1109/TCE.2004.1277887.
  10. Kotteri K.A., Barua S., Bell A.E., Carletta J.E. A comparison of hardware implementations of the biorthogonal 9/7 DWT: convolution versus lifting // IEEE Transactions on Circuits and Systems II: Express Briefs. - 2005. - Vol. 52(5). - P. 256-260. doi: 10.1109/TCSII.2005.843496.
  11. Meher P.K., Mohanty B.K., Patra J.C. Hardware-Efficient Systolic-Like Modular Design for Two-Dimensional Discrete Wavelet Transform // IEEE Transactions on Circuits and Systems II: Express Briefs. - 2008. - Vol. 55(2). - P. 151-155. doi: 10.1109/TCSII.2007.911801.
  12. Laan W.J., Jalba A.C., Roerdink J.B. Accelerating Wavelet Lifting on Graphics Hardware Using CUDA // IEEE Transactions on Parallel and Distributed Systems. - 2011. - Vol. 22(1). - P. 132-146. doi: 10.1109/TPDS.2010.143.
  13. Safari A., Niras C.V., Kong Y. Power-performance enhancement of two-dimensional RNS-based DWT image processor using static voltage scaling // Integration, the VLSI Journal. - 2016. - Vol. 53. - P. 145-156. doi: 10.1016/j.vlsi.2015.12.006
  14. Ramirez J., Meyer-Base U., Taylor F. e.a. Design and Implementation of High-Performance RNS Wavelet Processors Using Custom IC Technologies // Journal of VLSI Signal Processing. - 2003. - Vol. 34. - P. 227-237. doi: 10.1023/A:1023296218588.
  15. Cheng C.-C., Huang C.-T., Chen C.-Y. e.a. On-Chip Memory Optimization Scheme for VLSI Implementation of Line-Based Two-Dimentional Discrete Wavelet Transform // IEEE Transactions on Circuits and Systems for Video Technology. - 2007/ - Vol. 17(7). - P. 814-822. doi: 10.1109/TCSVT.2007.897106.
  16. Schlichthärle D. Digital Filters: Basics and Design, 2nd ed. - Springer, 2011. - 527 p.
  17. Mehrnia A, Willson A.N. A Lower Bound for the Hardware Complexity of FIR Filters // IEEE Circuits and Systems Magazine. - 2017. - Vol. 18(1). - P. 10-28. doi: 10.1109/MCAS.2017.2785422.
  18. Rao K.R, Yip P.C. The Transform and Data Compression Handbook. CRC Press, 2001. - 399 p.
  19. Basso A, Cavagnino D., Pomponui V. e.a. Blind Watermarking of Color Images Using Karhunen-Loève Transform Keying // The Computer Journal. - 2011. - Vol. 54(7). - P. 1076-1090. doi: 10.1093/comjnl/bxq052.
  20. Смоленцев Н.К. Основы теории вейвлетов. Вейвлеты в MatLAB. М.: ДМК, 2005. - 304 с.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2018 Chervyakov N.I., Ljahov P.A., Nagornov N.N.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies