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

Глава I. Введение.

1.1. Компрессия данных.^

1.2. Сжатие «с потерями».

Глава II. Краткий обзор современных методов анализа и компрессии изображений.

2.1. Методы прямого анализа изображения.

2.1.1. Фрактальное сжатие.

2.1.2. Векторное квантование.

2.1.3. Взвешенные конечные автоматы.

2.2. Спектральный анализ.

2.2.1. Дискретное косинусное преобразование.Р

2.2.2. Мультирезолюционный (кратномасштабный) анализ.

2.3. Выводы.-.

Глава III. Постановка задачи.

3.1. Постановка задачи.

3.2. Выбор технических средств.

3.2.1. Операционная система (ОС).

3.2.2. Модульная технология.

3.2.3. Средство разработки.

3.3. Краткое содержание работы.

Глава IV. Теоретические основы метода.

4.1. Общее описание метода.

4.2. Обработка изображения (мультирезолюционный анализ).

4.2.1. Выбор схемы разложения.

4.2.2. Лифтинговая схема.

4.2.3. Обработка границ.

4.2.4. Обработка областей с нечетной шириной/высотой.

4.2.5. «Пакетная» обработка.

4.3. Запись (кодирование) спектральных коэффициентов.

4.3.1. Древовидная структура данных.

4.3.2. Кодирование вложенными нулевыми деревьями (Embedded ZeroTrees).

4.3.3. Разбиение иерархических деревьев на множества (Set Partitioning in Hierarchical Trees — SPIHT).

4.3.4. Построение «деревьев» при нечетных размерах блока.

4.3.5. «Плавающий» порог (threshold).

4.4. Представление цветовой информации.

4.5. Выводы.

Глава V. Программная реализация.

5.1. Общее описание.

5.2. Взаимодействие интерфейсов (функциональная схема).

5.2.1. Компрессия изображения.

5.2.2. Декомпрессия сжатого изображения.

5.2.3. Последовательная декомпрессия изображения.

5.3. Реализация интерфейсов.

5.3.1. Интерфейс IEngine.

5.3.2. Интерфейс Ilmage.

5.3.3. Интерфейс ICompressHeader.

5.3.4. Интерфейс IFileStream.

5.4. Особенности реализации алгоритмов.

5.4.1. Представление данных.

5.4.2. Смешивание цветовых компонентов.

5.4.3. Иерархия классов для реализации методов обработки.

5.4.4. Словарь символов в алгоритме кодирования ZeroTrees.

5.5. Формат выходного потока.

5.6. Выводы.

Глава VI. Тестирование.

6.1. Тестирование.

6.2. Сравнение.

Глава VII. Заключение.

7.1. Обобщающие выводы.

7.2. Основные результаты.

7.3. Перспективность разработок.

7.2. Основные результаты

• Для корректной обработки границ изображения предложен метод «четного продолжения» — зеркалирование приграничных точек относительно крайних. При применении этого метода не возникает «всплесков» высокочастотных коэффициентов на краях изображения, что приводит к увеличению степени компрессии и отсутствию искажений около границ.

• Решена проблема обработки изображений произвольного размера — для обработки областей с нечетной длиной и/или шириной было предложено «приписывать» последний столбец или строку исходной области к низкочастотным коэффициентам (для получения лучшего результата необходима соответствующая нормировка низкочастотных коэффициентов). Для применения этого решения разработан алгоритм построения древовидных структур коэффициентов, необходимых для кодирования (при этом у одного родителя может оказаться от одного до девяти потомков).

• Для хранения цветовой информации было решено использовать схему цветов УСЬСг, в которой компонента яркости отделяется от цветовых компонент, менее важных для восприятия. Была разработана схема смешивания различных цветовых компонентов, позволяющая указывать размер блока данных для каждого компонента (то есть задавать «вес» соответствующей компоненты в выходном потоке).

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

• Разработан новый усовершенствованный словарь символов в алгоритме кодирования вложенными нулевыми деревьями — словарь с варьирующейся длиной символов, что позволяет кодировать часто встречающиеся символы более короткими цепочками битов. Также введен дополнительный более короткий словарь для кодирования символов, передаваемых на вспомогательном проходе. Эти модификации позволяют уменьшить размер выходного потока при фиксированном объеме кодируемых данных.

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

Разработанный модуль имеет следующие дополнительные возможности:

• Возможность получения выходного потока любого размера — для восстановления изображения достаточно получить заголовок потока.

• Поточность данных (и, как следствие — возможность «докачки» данных — подробнее об этом см. во введении) — в модуле реализована возможность «последовательной» декомпрессии изображения. Вследствие этого также появляется возможность использования результатов компрессии для получения потоков с различной степенью сжатия — производится компрессия с максимальным из необходимых размером выходных данных, а меньшие размеры получаются с помощью «обрезания» хвоста выходного потока. Эта возможность приобретает значение при необходимости пересылки изображения нескольким клиентам с разным качеством.

• Возможность сохранения цветного изображения в черно-белом (grayscale) формате.

• Возможность задания размера блока данных для компонент яркости и цветности (то есть указать «важность» соответствующей компоненты).

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

7.3. Перспективность разработок

Метод, представленный в работе, и реализующий его модуль представляют собой ядро, на котором могут базироваться дальнейшие исследования в области сжатия изображений. Перечислим несколько путей, по которым может идти дальнейшее развитие:

1. Поиск более эффективных фильтров обработки (не обязательно вейвлетов);

2. Поиск более эффективных алгоритмов кодирования высокочастотных коэффициентов;

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

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

5. Разработка алгоритмов пост-процессинга, то есть дополнительной обработки изображения, проводимой после восстановления изображения с целью маскировки возникших в процессе сжатия/восстановления артефактов.

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

1. Архитектура Microsoft Windows для разработчиков. Учебный курс /Microsoft Windows Architecture for Developer's Training/. Microsoft Press,1998.

2. Булдырев B.C., Павлов Б.С. Линейная алгебра и функции многих переменных, с. 242-245, Ленинград, Издательство Ленинградского университета, 1985.

3. Грегори М. Использование Visual С++ 6. Специальное издание. СПб, Вильяме, 1999.

4. Мюррей У. Visual С++. Руководство для профессионалов. СПб, BHV -Санкт-Петербург, 1997.

5. Романов В.Ю. Популярные форматы файлов для хранения графических изображений. Москва, Унитех, 1992.

6. Страуструп Б. Язык программирования С++. СПб, Невский диалект,1999.

7. Фролов А.В., Фролов Г.В. Операционная система Windows 95 для программистов (библиотека системного программиста, том 22). Москва, Диалог-МИФИ, 1996.

8. Чеппел Д. Технологии ActiveX и OLE /Understanding ActiveX and OLE/. Microsoft Press, 1997.

9. Aharoni G., Averbuch A., Coifman R., Israeli M. Local Cosine Transform — A Method for the Reduction of the Blocking Effect in JPEG. Journal on Math. Imag. Vision, vol. 3, pp. 7-38, 1993.

10. Antonini M., Barlaud M., Mathieu P., Daubechies I. Image Coding Using Wavelet Transform, IEEE Transactions on Image Processing, vol. 1, pp.205220, 1992.

11. Bell Т., Cleary J.G., Witten I.H. Text Compression. Englewood Cliffs, NJ: Prentice Hall, 1990.

12. Beylkin G., Coifman R., Rokhlin V. Fast Wavelet Transform and Numerical Algorithms. Communication on Pure and Applied Mathematics, vol. 44, pp. 141-183, 1991.

13. Blaszczak M. Professional MFC with Visual C++ 6, Wrox Press, 1999.

14. Burrus C.S., Gopinath R.A., Guo H. Introduction to Wavelets and Wavelet Transforms: A Primer. Englewood Cliffs, NJ: Prentice-Hall, 1997.

15. Calderbank R., Daubechies I., Sweldens W., Yeo B.-L. Wavelet transforms that map integers to integers. Applied and Computational Harmonic Analysis, vol. 5, no. 3, pp. 332-369, 1998.

16. Canny J. A computation Approach to Edge Detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 8, no. 6, pp. 679-698, 1986.

17. Chen X., Huang J., Loh E. Two-dimensional fast Fourier transform and pattern processing with IBM PC. Am. J. Phys., vol. 56, no. 8, pp. 747-749, 1988.

18. Chou P.A., Lookabaugh T.,Gray R.M. Entropy-constrained vector quantization. IEEE Transactions on Information Theory, vol. 37, pp. 31-42, January 1989.

19. Chui C.K. An Introduction to Wavelets. Academic Press, San Diego, CA, 1992.

20. Chui C.K., Quak E. Wavelets on a Bounded Interval. In Numerical Methods of Approximation Theory, vol. 9, Braess D. and Schumaker L.L., Eds. Birkhauser Verlag, Basel, pp. 53-75, 1992.

21. Chui C.K., Wang J.Z. A General Framework of Compactly Supported Splines and Wavelets. Journal of Approximation Theory, vol. 71, no. 3, pp. 263-304, 1992.

22. Cohen A., Daubechies I., Feauveau J.C. Biorthogonal Bases of Compactly Supported Wavelets. Communication on Pure and Applied Mathematics, vol. 45, pp. 485-560, 1992.

23. Cohen A., Daubechies I., Vial P. Multiresolution analysis, wavelets and fast algorithms on an interval. Applied and Computational Harmonic Analysis, vol. 1, no. l,pp. 54-81, 1993.

24. Coifman R.R., Meyer Y., Quake S., Wickerhauser M.V. Signal Processing and Compression with Wave Packets. In Proceedings of the International Conference on Wavelets, Marseille, Meyer Y., Ed., Masson, Paris, 1989.

25. Coifman R.R., Wickerhauser M.V. Entropy based algorithms for best basis selection. IEEE Transactions on Information Theory, vol. 32, pp. 712-718, Mar. 1992.

26. Criminal Justice Information Services. WSQ Grayscale Fingerprint Image Compression Specification. Federal Bureau of Investigation, Feb. 1993.

27. Dahmen W. Stability of multiscale transformations. Tech. rep., Institut fur Geometrie und angewandete Mathematik, RWTH Aachen, 1994.

28. Daubechies I. Orthonormal Bases of Compactly Supported Wavelets. Comm. Pure Appl. Math., vol. 41, pp. 906-966, 1988.

29. Daubechies I. Orthonormal Bases of Compactly Supported Wavelets II: Variations on a theme. SIAM Journal on Mathematical Analysis, vol. 24, no. 2, pp. 499-519, 1993.

30. Daubechies I. Ten Lectures on Wavelets. Philadelphia, PA: SIAM, 1992.

31. Daubechies I. The wavelet transform, time-frequency localization and signal analysis. IEEE Transactions on Information Theory, no. 5, pp. 961-1005, 1990.

32. Daubechies I., Sweldens W. Factoring Wavelet Transforms into Lifting Steps. J. Fourier Anal. Appl., vol. 4, no. 3, pp. 245-267, 1998.

33. Davis G.M., Chawla S. Image coding using optimized significance tree quantization. In Proceeding of the Data Compression Conference (Storer J. A. and Cohn M., eds.), pp. 387-396, Mar 1997.

34. Davis G.M., Nosratinia A. Wavelet-based Image Coding: An Overview. Applied and Computational Control, Signals, and Circuits, vol. 1, no. 1, spring 1998.

35. DeVore R.A., Jawerth B., Lucier B.J. Image Compression through Wavelet Transform Coding. IEEE Transactions on Information Theory, vol. 38, pp. 719-746, Mar. 1992.

36. DeVore R.A., Lucier B.J. Wavelets. In Acta Numerica, no. 1 (1991), Cambridge University Press, pp. 1-56, 1991.

37. Duttweiler D.L., Chamzas C. Probability estimation in arithmetic and adaptive-Huffman entropy coders. IEEE Transactions on Image Processing, vol. 4, pp. 237-246, 1995.

38. Feig E., Linzer E. Discrete cosine transform algorithms for image data compression. Electronic Imaging '90 East, Boston, MA, pp. 84-87, 1990.

39. Fisher Y. Fractal image compression with quadtrees. Fractal Image Compression, Yuval Fisher, Ed. chapter 3, pp.55-77, Springer-Verlag, 1995.

40. Gersho A., Gray R.M. Vector Quantization and Signal Compression. Kluwer Academic Publishers, 1992.

41. Hafner U. Refining image compression with weighted finite automata. In Storer J.A. and Cohn M., editors, Proceeding of the Data Compression Conference, pp. 359-368, 1996.

42. Hafner U., Albert J., Frank S. Unger M. Image and Video Coding with Weighted Finite Automata. IEEE Journal on Selected Areas in Communication, vol. XX, no. V, 1999.

43. Harten A. Multiresolution representation of data: A general framework. SIAM Journal on Numerical Analysis, vol. 33, no. 3, pp. 1205-1256, 1996.

44. Haskell B.G., Puri A., Netravali A.N. Digital Video: An Introduction to MPEG-2. Chapman & Hall, ISBN 0-412-08411-2, 1997.

45. Herley C. Orthogonal time-varying filter banks and wavelets. Proceeding of the IEEE Int. Symp. Circuits Systems, vol. 1, pp. 391-394, May 1993.

46. Herley C., Xiong Z., Ramchandran K., Orchard M. Joint space-frequency segmentation using balanced wavelet packet tree for least-cost image representation. IEEE Transactions on Image Processing, no. 9, 1997.

47. Hilton M.L., Jawerth B.D., Sengupta A.N. Compressing Still and Moving Images with Wavelets. Multimedia Systems 3, 1994.

48. Hubbard B.B. The World According to Wavelets: The Story of a Mathematical Technique in the Making. A K Peters, Ltd., 1996.

49. ITU-T Recommendation H.223, Multiplexing protocol for low bit rate multimedia communications. 1996.51 .ITU-T Recommendation H.263, Video coding for low bit rate communication. 1998.

50. ITU-T Recommendation H.324, Terminal for low bit rate multimedia communication. 1998.

51. Jain A.K. Fundamentals of Digital Image Processing. Prentice Hall, 1989.

52. Jawerth B., Hilton M.L., Hunstberger T.L. Local Enhancement of Compressed Images. Journal Math. Imag. Vision, vol. 3, pp. 39-49, 1993.

53. Jawerth B., Sweldens W. An overview of wavelets based multiresolution analyses. SIAM Review, vol. 36, no. 3, pp. 377-412, 1994.

54. Lawton W.M. Necessary and Sufficient Conditions for Constructing Orthonormal Wavelets Bases. Journal of Mathematical Physics, vol. 32, no. 1, pp. 57-61, 1991.

55. Lewis A.S. Knowles G. Video Compression using 3D Wavelet Transforms. Electr. Letters 26, no. 6, pp. 396-397, 1992.

56. Lindbloom B. J., Accurate Color Reproduction for Computer Graphics Applications. Computer Graphics, vol. 23, no. 3, pp. 117-126, July 1989.

57. Linde Y., Buzo A., Gray R.M. An Algorithm for Vector Quantizer Design. IEEE Transactions on Communications, vol. 28, no. 1, pp. 84-95, 1980.

58. Mallat S. A theory for multiresolution signal decomposition: the wavelet representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, no. 7, pp. 674-693, 1989.

59. Mallat S. Analysis of low bit rate image transform coding. IEEE Transactions on Signal Processing, no. 4, pp. 1127-1142, 1998.

60. Mallat S. Multiresolution Approximations and Wavelet Orthonormal Bases of L (RR). Transactions on American Mathematical Society, vol. 315, no. 1, pp. 69-87, 1989.

61. Mallat S., Falzon F. Understanding image transform codes. In Proceeding of the SPIE Aerospace Conference, Orlando, Apr. 1997.

62. Marr D., Hildreth E. Theory of Edge Detection. Proc. Royal Society of London B, 207, London, pp. 187-217, 1980.

63. MSDN Library. Microsoft Corporation. October 1999.

64. Parke F.I., Waters K. Computer Facial Animation, A.K. Peters, Wellesley, MA, USA, 1996.

65. Peitgen H.O., Saupe D. The Science of Fractal Images. Springer Verlag, 1998.

66. Puri A., Schmidt R.L., Haskell B.G. Improvements in DCT Based Video Coding. Proceeding of the SPIE Visual Communications and Image Processing, San Jose, Feb. 1997.

67. Puri A., Schmidt R.L., Haskell B.G. Performance Evaluation of the MPEG-4 Visual Coding Standard. Proceeding of the SPIE Visual Communications and Image Processing, San Jose, Jan. 1998.

68. Quak E., Weyrich N. Decomposition and Reconstruction Algorithms for Spline Wavelets on a Bounded Interval. Tech. Rep. 294, Department of Mathematics, Texas A&M University, April 1993.

69. Rabbani M., Jones P.W. Digital Image Compression Techniques, SPIE Opt. Eng. Press, Bellingham, Washington, 1991.

70. Rao K., Tip P. The Discrete Cosine Transform. New York: Academic Press, 1990.

71. Reissell L.-M. Wavelet multiresolution representation of curves and surfaces. CVGIP: Graphical Models and Image Processing, vol. 58, no. 2, pp. 198-217, 1996.

72. Rioul O., Vetterli M. Wavelets and signal processing. IEEE Signal Processing Magazine, no. 10, pp. 14-38, 1991.

73. Rogerson D. Inside COM with CD-ROM. Microsoft Press, 1996.

74. Ruskai M.B., Beylkin G., Coifman R., Daubechies I., Mallat S., Meyer Y., Raphael L., Eds. Wavelets and their Applications. Jones and Bartlett, 1992.

75. Said A., Perlman W. A New Fast and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees. IEEE Transactions on Circuits and System for Video Technology, vol. 6, no. 3, pp. 243-250, June 1996.

76. Servetto S., Ramchandran K., Orchard M. Wavelet based image coding via morphological prediction of significance. Proceedings of IEEE ICIP-95, pp. 530-533, Oct. 1995.

77. Shapiro J.M. Embedded Image Coding Using Zerotrees of Wavelet Coefficients. IEEE Transactions on Signal Processing, vol. 41, no. 12, pp. 3445-3462, Dec. 1993.

78. Smith J.R., Chang S.F. Frequency and spatially adaptive wavelet packets. Proceeding of the ICASSP, May 1995.

79. Stollnitz E.J., DeRose T.D., Salesin D.H. Wavelets for Computer Graphics: A Primer, Part 1. IEEE Computer Graphics and Applications, vol. 15, no. 3, pp. 76-84, May 1995.

80. Strang G. The Discrete Cosine Transform. SIAM Review, vol. 41, no. 1, pp. 135-147, 1999.

81. Strang G. Wavelets and dilation equation: A brief introduction. SIAM Review, no. 4, pp. 614-627, 1989.

82. Strang G., Nguyen T. Wavelets and Filter Banks. Wellesley, Cambridge, 1996.

83. Sweldens W. Construction and Applications of Wavelets in Numerical Analysis. Ph.D. thesis, Department of Computer Science, Katholieke Universiteit Leuven, Belgium, 1994.

84. Sweldens W. Lifting scheme: A construction of second generation wavelets. SIAM Journal on Mathematical Analysis, vol. 29, no. 2, pp. 511-546, 1997.

85. Sweldens W. Lifting scheme: A custom-design construction of biorthogonal wavelets. Applied and Computational Harmonic Analysis, vol. 3, no. 2, pp. 186-200, 1996.

86. Sweldens W. Lifting scheme: A new philosophy in biorthogonal wavelet constructions. Wavelet Applications in Signal and Image Processing III, pp. 68-79, Proceeding of the SPIE 2569, 1995.

87. Sweldens W., Piessens R. Quadrature formulae and asymptotic error expansions for wavelet approximations of smooth functions. SIAM Journal of Numerical Analysis, vol. 31, pp. 1240-1264, Aug. 1994.

88. Sweldens W., Schroder P. Building your own wavelets at home. Wavelets in Computer Graphics, pp. 15-87, ACM SIGGRAPH Course notes, 1996.

89. Tian J., Wells R.O. Vanishing moments and biorthogonal wavelet system. Mathematics in Signal Processing IV, Institute of Mathematics and Its Applications Conference Series, Oxford University Press, 1996.

90. Tolhuizen L.M.G., Hollmann H.D.L., Kalker T.A.C.M. On the realizability of bi-orthogonal M-dimensional 2-band filter banks. IEEE Transactions on Signal Processing, 1995.

91. Understanding COM+, Microsoft Press, 1999.

92. Unser M. Approximation power of biorthogonal wavelet expansions. IEEE Transactions on Signal Processing, vol. 44, pp. 519-527, Mar. 1996.

93. Unser M., Aldroubi A., Eden M. A family of polynomial spline wavelet transforms. Signal Processing, no. 30, pp. 141-162, 1993.

94. Van Dyck R.E., Marshall T.G., Chine M., Moayeri N. Wavelet video coding with ladder structures and entropy-constrained quantization. IEEE Transactions on Circuits and Systems for Video Technology, vol. 6, no. 5, pp. 483-495, 1996.

95. Vetterli M., Herley C. Wavelets and filter banks: Theory and design. IEEE Transactions on Acoustic, Speech, Signal Processing, vol. 40, no. 9, pp. 22072232, 1992.

96. Voss R.P. Fractal Fergeries. In Fundamental Algorithms for Computer Graphics, Earnshaw R.A., Ed. Springer-Verlag, 1985.

97. Wang Y., Orchard M., Reibman A.,Vaishampayan V. Redundancy ratedistortion analysis of multiple description coding using pairwise correlation transforms. Proceeding of the IEEE ICIP, vol. 1, pp. 608-611, 1997.

98. Wallace G.K. The JPEG Still Picture Compression Standard. Communications of the ACM 34, no. 4, pp. 30-44, 1991.

99. Wandell B.A. Foundations of Vision. Sunderland, MA: Sinauer Associates, 1995.

100. Watson A., Yang G., Soloman J., Villasenor J. Vidual thresholds for wavelet quantization error. In Proceeding of the SPIE, vol. 2657, pp. 382-392, 1996.

101. Wickerhauser M. Acoustic signal compression with wavelet packets. In Chui C. ed. Wavelets: A Tutorial in Theory and Applications, Academic Press, Boston, pp. 679-700, 1992.

102. Woods J.W., O'Neil S.D. Subband coding of images. IEEE Transactions on Acoustic, Speech, Signal Processing, vol. 34, no. 5, pp. 1278-1288, 1986.

103. Zandi. A., Allen J., Schwartz E., Boliek M. CREW: Compression with reversible wavelets. Proceedings of IEEE Data Compression Conference, pp. 212-221, 1995.