Сжатие цифровых изображений на основе дискретного псевдокосинусного преобразования

Выводы и заключение.

В процессе выполнения диссертационной работы получены следующие научные результаты:

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

2) Определены статистические характеристики спектров ДПКП изображений, которые использованы для построения алгоритма статистического кодирования в предложенном методе сжатия на основе ДПКП.

3) Предложен алгоритм статистического кодирования спектров ДПКП, использующий многомодельное кодирование и кодирование с отбрасыванием нулевых областей, позволивший достигнуть эффективности сжатия, сравнимой с эффективностью сжатия метода JPEG.

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

5) Разработано программное обеспечение, реализующее предложенный метод.

6) Определены характеристики вычислительной сложности и эффективности сжатия разработанного метода в сравнении с методом JPEG на основе ДКП.

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

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

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

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

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

Также представляет интерес рассмотрение схемы кодирования знака с алфавитом кодирования из трех символов — «+», «-», «О», что позволит исключить из алфавита кодирования модулей переменных составляющих нулевой символ. Предполагается, что благодаря такой схеме уменьшатся битовые затраты на кодирование нулевых коэффициентов, составляющих около 2/3 от всех кодируемых переменных составляющих.

Еще одним перспективным направлением развития метода является внедрение квантования с различными дискретами, соответствующими разным обобщенным частотам спектра ДПКП.

Программное обеспечение, реализующее разработанный метод сжатия на базе ДПКП в модификации 2.0, было использовано в ОАО «НПО Энергомаш» для организации хранения изображений жидкостных ракетных двигателей и его узлов, которые выполняют при штатном фотоконтроле до и после проведения огневых испытаний [17, 19]. Акт внедрения результатов диссертационной работы приведен в Приложении 9.

1. Ахмед Н., Pao К. Р. Ортогональные преобразования при обработке цифровых сигналов: Пер. с англ. М.: Связь, 1980. — 248 с.

2. Гонсалес Р., Вудс Р. Цифровая обработка изображений. — М.: Техносфера, 2005. 1072 с.

3. Грузман И. С., Киричук В. С., Косых В. 77. и др. Цифровая обработка изображений в информационных системах. Новосибирск: Изд-во НГТУ, 2002. — 352 с.

4. Дмитриев В. И. Прикладная теория информации: Учеб. для студ. вузов. М.: Высш. шк, 1989. — 320 с.

5. Добеши И. Десять лекций по вейвлетам. Москва, Ижевск: НИЦ «Регулярная и хаотическая динамика», 2004. — 464 с.

6. Залманзон Л. А. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. М.: Наука, 1989. — 496 с.

7. Захаров М. В. Об одной реализации арифметического кода Электронный ресурс. URL: http://www.maxime.net.ru/doc/mfarc.ps.gz.

8. Калиткин Н. Н. Численные методы. М.: Наука, 1978 — 512 с.

9. Ковалев В. И., Курина В. В. Методы обработки телеметрической информации на основе ортогональных преобразований // Труды ОАО НПО Энергомаш имени академика В. П. Глушко. № 27. — Москва: НПО Энергомаш, 2010. -С.254—280.

10. Кочетков М. Е., Умняшкин С. В. О сравнении критериев для оценки эффективности декоррелирующих преобразований. М.: МГИЭТ (ТУ), 1998. -34 с. — Депонировано в ВИНИТИ 13.04.98 № 1069-В98.

11. Курина В. В. Метод сжатия изображений на основе дискретного псевдокосинусного преобразования // Микроэлектроника и информатика -2010. 17-я Всеросс. межвуз. науч.-тех. конф-я студ. и аспир.: Тезисы докладов. -Москва: МИЭТ, 2010. С. 147.

12. Курина В. В. Оценка эффективности применения дискретного псевдокосинусного преобразования для сжатия изображений // Известия вузов. Электроника. -2010. -№ 2. С. 78−80.

13. Курина В. В. Параметры статистического кодирования в задаче вейвлет-компрессии изображений // Микроэлектроника и информатика 2006. 13-я Всеросс. межвуз. науч.-тех. конф-я студ. и аспир.: Тезисы докладов. — Москва: МИЭТ, 2006.-С. 162.

14. Курина В. В. Учет корреляции знака при вейвлет-кодировании изображений // Микроэлектроника и информатика 2005. 12-я Всеросс. межвуз. науч.-тех. конф-я студ. и аспир.: Тезисы докладов. — Москва: МИЭТ, 2005. — С. 179.

15. Курина В. В., Кучев А. С. Разработка методики сжатия изображений для базы данных по испытаниям // Труды ОАО НПО Энергомаш имени академика В. П. Глушко. № 24. — Москва: НПО Энергомаш, 2006. — С. 279−291.

16. Прэтт У. Цифровая обработка изображений: Пер. с англ. М.: Мир, 1982. -Кн. 1−312 с.

17. Розанов Ю. А. Случайные процессы. -М.: Наука, 1971. -288 с.

18. Семенюк В. В. Обзор стандарта JPEG 2000 Электронный ресурс. СПб, 2002. -URL: http://compression.ru/download/articles/jpeg/semenjuk2001jpeg2000.pdf.

19. Семенюк В. В. Экономное кодирование дискретной информации Электронный ресурс. СПб.: СПбГИТМО (ТУ). — 2001. — URL: compression.ru/download/articles/revuniv/semenyuk2001economencoding.pdf.

20. Стрелков Ф. В., Умняшкин С. В. Контекстное кодирование коэффициентов дискретного косинусного преобразования (ДКП) в JPEG-подобной схеме компрессии // Цифровая обработка сигналов. 2003. — № 2. — С. 5−10.

21. Умняшкин С. В. Анализ эффективности применения ортогональных преобразований для кодирования дискретных сигналов с коррелированными отсчетами // Цифровая обработка сигналов. 2008. — № 4. — С. 15−18.

22. Умняшкин С. В. Использование контекстного арифметического кодирования для повышения сжатия данных по схеме JPEG // Известия вузов. Электроника. 2001. — № 3. — С. 96−99.

23. Умняшкин С. В. Математические основы цифровой обработки и кодирования сигналов: Учебное пособие. -М.: МИЭТ, 2004. 176 с.

24. Умняшкин С. В. О модификации дискретного косинусного преобразования // Изв. Тул. гос. ун-та. Сер. Математика. Механика. Информатика. Тула: ТулГУ, 1998.-Т. 4.-Вып. 1.-С. 143−147.

25. Умняшкин В. В. Применение дискретного преобразования Крестенсона-Леви в цифровой обработке изображений: Диссертация на соискание ученой степени кандидата технических наук. М.: МИЭТ, 1997. — 196 с.

26. Умняшкин С. В., Безуглова Е. А. Контекстное кодирование коэффициентов дискретного косинусного преобразования на основе межблочной корреляции в JPEG-подобной схеме компрессии // Цифровая обработка сигналов. 2004. -№ 2.-С. 13−17.

27. Умняшкин С. В., Курина В. В. Алгоритм сжатия изображений на основе дискретного псевдокосинусного преобразования // Цифровая обработка сигналов. 2009. — № 3. — С. 2−7.

28. Хэмминг Р. В. Теория кодирования и теория информации: Пер. с англ. — М.: Радио и связь, 1983. 176 с.

29. Чуй. Ч.

Введение

в вейвлеты. Москва: Мир, 2001. — 412 с.

30. Adams М. D. The JasPer Project home page Электронный ресурс. 1999. -URL: http://www.ece.uvic.ca/~mdadams/jasper/.

31. Advanced video coding for generic audiovisual services // ITU-T Recommendation H.264. 2007 (ISO/1EC 14 496−10. Information Technology. Coding of AudioVisual Objects. Part 10: Advanced Video Coding).

32. Andrews H. C., Hunt B. R. Digital image restoration. Englewood Cliffs (NJ): Prentice Hall, 1977. — 238 p.

33. Arai Y., Agui Т., Nakajima M. A fast dct-sq scheme for images // Trans. IEICE. -Nov. 1988.-Vol. E-71. No. 11.-P. 1095.

34. Berger T. Rate distortion theory: a mathematical basis for data compression. Englewood Cliffs NJ: Prentice-Hall, 1971. 311 p.

35. Center for Image Processing Research Электронный ресурс. -URL: http://www.cipr^i.edu/resource/stills/miscl .html.

36. Chan S. С., Ho K. L. A new two-dimensional fast cosine transform algorithm // IEEE Trans, on Signal Processing. Feb. 1991. — Vol. 39. — No. 2. — P. 481−485.

37. Chen W.-H., Smith C., Fralick S. A fast computational algorithm for the discrete cosine transform I I IEEE Trans. Com. Sept. 1977. — Vol. 25. — No. 9. — P. 10 041 011.

38. Costantini R. et al. A low-complexity video coder based on the discrete Walsh Hadamar transform // Proc. European signal processing conference (Tampere, Finland, September 5−8). 2000. — P. 1217−1221.

39. Cutler C. C. Differential quantization of communication signals. Patent 2−605−361. -July 1952.

40. Davis G., Nosratinia A. Wavelet-based image coding: an overview // Applied and computational control, signals and circuits. 1998. — Vol. 1. — No. 1. — P. 205−269.

41. Deever A., Hemami S. S. What’s your sign?: Efficient sign coding for embedded wavelet image coding // Proc. IEEE Data Compression Conf. (Snowbird, UT, 28−30 March 2000). 2000. — P. 273−282.

42. Digital compression and coding of continuous-tone still images. Requirements and guidelines // ITU-T Recommendation T.81. September 1992. (ISO/IEC IS 10 918−1. JPEG Part 1).

43. Dimitrov V., Wahid K. Multiplierless DCT algorithm for image compression applications // Information theories & applications. Vol. 11. — P. 162−169.

44. Duhamel P., Guillemot C. Polynomial transform computation of the 2-D DCT // IEEE International Conference on Acoustics, Speech, and Signal Processing. Apr. 1990.-Vol. 3.-P. 1515−1518.

45. Eliott D. F., Rao K. R. Fast transforms: algorithms, analyses, applications. London: Academic Press, 1982. 488 p.

46. Fano R. M. Technical N65. The Research Laboratory of Electronics, MIT. — Mar. 17, 1949.

47. Feig E., Winograd S. Fast algorithms for the discrete cosine transform // IEEE Trans, on Signal Processing. Sept. 1992. — Vol. 40. — No. 9. — P. 2174−2193.

48. Feig E., Winograd S. On the multiplicative complexity of discrete cosine transform // IEEE trans, on information theory. July 1992. — Vol. 38. — No. 4. — P. 1387−1391.

49. Fog A. Instruction tables: Lists of instruction latencies, throughputs and microoperation breakdowns for Intel, AMD and VIA CPUs 3jieicrpoHH?>m pecypc.

50. URL: http://www.agner.org/optimize/instructiontables.pdf.

51. Haar A. Zur Theorie der Orthogonal Funktionen-System. Inaugural Disertation // Math. Annalen. 1955. — No. 5. — P. 17−31.

52. Hadamar J. Resolution d’une question realative aux determinants // Bulletin des Sciences Mathematiques. 1893. — Ser. 2 — No. 17. — P. 240−246.

53. Hallapuro A., Karczewicz M. Low complexity transform and quantization Part 1: Basic implementation // ISO/IEC JTC1/SC29/WG11 and ITU-T SG16 Q.6 Document JVT-B038. — January 2001.

54. Howard P. G., Vitter J. S. Design and analysis of fast text compression based on quasi-arithmetic coding // Proc. Data Compression Conference (Snowbird, Utah, March 1993). 1993. — P. 98−107.

55. Huffman D. A. A method for the construction of minimum redundancy codes // Proc. I.R.E.- 1952.-Vol. 4D. No. 9.-P. 1098−1101.

56. Independent JPEG group Электронный ресурс. URL: http://www.ijg.org.

57. Jayant N., Noll P. Digital coding of waveforms: principles and applications to speech and video // Englewood Cliffs NJ: Prentice-Hall, 1984. 688 p.

58. JPEG 2000 Image coding system: core coding system // ITU-T Recommendation T.800. August, 2002 (ISO/IEC IS 15 444−1, JPEG 2000 Part 1. — December, 2000).

59. Katto J., Yasudo Y. Performance evaluation of subband coding and optimization its filter coefficients // SPIE Proc. Visual Communication and Image Processing (Boston, MA).-Nov. 1991.-Vol. 1605.-P. 95−106.

60. Lee B. G. A new algorithm to compute discrete cosine transform // IEEE Trans, on Acoustics, Speech and Signal Processing. Dec. 1984. — Vol. 32. — No. 6. — P. 12 431 245.

61. Lengwehasatit K., Ortega A. DCT computation with minimal average number of operations // Proc. of Visual Communication and Image Processing (VCIP '97, San Jose, CA). Feb. 1997. — Vol. SPIE-3024. — P. 71−82.

62. Liang Jie, Tran T. D. Fast multiplierless approximations of the DCT with the lifting scheme // IEEE Transactions on Signal Processing. 2001. — Volume 49. — No. 12. -P. 3032−3044.

63. Loeffler C., Lightenberg A., Moschytz G. Practical fast Id dct algorithms with 11 multiplications // Proc. IEEE ICASSP. Feb. 1989. — Vol. 2. — P. 988−991.

64. Mallat } S. A theory for multiresolution signal decomposition: the wavelet representation // IEEE Transactions on Pattern Analysis and Machine Intelligence. -July 1989.-Vol. 11. No. 7-P. 674−693.

65. Marcellin M. W., Gormish M. J., Bilgin A., Boliek M. An overview of JPEG-2000 // Proc. of the Conference on Data Compression (Snowbird, Utah, March 2000). -2000.-P. 523−541.

66. Marpe D., Wiegand T. A highly efficient multiplication-free binary arithmetic coder and its application in video coding // Proceedings of IEEE International Conference on Image Processing (ICIP 2003). Sept. 2003. — Volume 2. — P. II — 263−6 vol.3.

67. Martin G. N. N. Range encoding: an algorithm for removing redundancy from digitized message. March 1979 (presented to Video & Data Recording Conference, Southampton, UK, July 24−27 1979).

68. Merhav N. Multiplication-free approximate algorithms for compressed domain linear operations on images // IEEE Transactions on Image Processing. Feb 1999. -Volume 8. — Issue 2. — P. 247−254.

69. MPEG-1. Coding of moving pictures and associated audio for digital storage media at up to about 1,5 Mbit/s // ISO/IEC JTC1/SC29/WG11 N MPEG 96. June 1996.

70. MPEG-2. Generic coding of moving pictures and associated audio information // ISO/IEC JTC1/SC29/WG11 N MPEG 00. October 2000.

71. Pao I-Ming, Sun Ming-Ting. Approximation of calculation for forward discrete cosine transform // IEEE Transactions on Circuits and Systems for Video Technology. June 1998.-Vol. 8.-No. 3.-P. 264−268.

72. Pearl J. On coding and filtering stationary signals by discrete Fourier transforms // IEEE Trans. Inf. Theory. 1973. — Vol. 19. — No. 2. — P. 229−232.

73. Pennebaker W. B., Mitchell J. L. JPEG still image data compression standard. NY: Springer, 1992. 650 p.

74. Pennebaker W. B., Mitchell J. L., Langdon G. G., Arps R. B. An overview of the basic principles of the Q-coder adaptive binary arithmetic coder // IBM Journal of Research and Development. -Nov. 1988. Vol. 32. — No. 6. — P. 717−726.

75. Pratt W. K., Andrews H. C., Kane J. Hadamar transform image coding // Proc. IEEE. -January 1969.-Vol. 57.-No. 1.-P. 58−68.

76. Rabbani M., Joshi R. An overview of the JPEG 2000 still image compression standard // Signal processing: Image communication. January 2002. — Vol. 17. -No. l.-P. 3¹⁸.

77. Rao K. R., Yip P. Discrete cosine transform: algorithms, advantages, applications. -New York: Academic Press, 1990. 512 p.

78. Rieder P., Gotze J., Sauer M., Nossek J. A. Orthogonal approximation of the discrete cosine transform // Proc. of European Conference on Circuit Theory and Design (Istanbul, Turkey). 1995. — P. 1003−1006.

79. Rissanen J. J. Generalized Kraft inequality and arithmetic coding // IBM Journal of Research and Development. May 1976. — Vol. 20. — No. 3. — P. 198−203 (first published as IBM Research Report RJ-1591, June 1975).

80. Rissanen J. J., Mohiuddin K. M. A multiplication-free multialphabet arithmetic code // IEEE Transactions on Communications. February 1989. — Vol. 37. — No. 2. -P. 93−98.

81. Said A., Pearlman W. A. A new, fast and efficient image codec based on set partitioning in hierarchical trees // IEEE Transactions on circuits and systems for video technology. June 1996. — Vol. 6. — No. 3. — P. 243−250.

82. Schindler M. Range encoder homepage 3jieKipoHHE. iH pecypc. Oct. 1999. -URL: http://www.compressconsult.com/rangecoder/.

83. Shannon C. E. A mathematical theory of communication // Bell System Technical Journal. Vol. 27. — No. 3. -July 1948. — P. 379−423- No. 4. — October, 1948. — P. 623−656.

84. Shapiro. J. M. Embedded image coding using zerotrees of wavelet coefficients // IEEE Transactions on Signal Processing. Dec. 1993. — Vol. 41. No. 12 — P. 34 453 462.

85. Strang G., Nguyen T. Wavelets and filter banks. Massachusetts: Wellesley-Cambridge Press, 1997. — 440 p.

86. The USC-SIPI Image Database Электронный ресурс. -URL: http://sipi.usc.edu/database/index.html.

87. Todd S., Langdon G.G., Rissanen J. Parameter reduction and context selection for compression of gray-scale images // IBM Journal of Research and Development. -Mar. 1985.-Vol. 29.-No. 2.-P. 188−193.

88. URL: http://sylvana.net/jpeg-ari/jpeg-ari.zip.

89. Video Coding for Low Bitrate Communication // ITU-T Recommendation H.263. -1996.

90. Wallace G. K. The JPEG still picture compression standard // Communications of the ACM. April 1991. — Volume 34. — Number 4. — P. 30¹⁴.

91. Wang. Z. Fast algorithm for the discrete W transform and for the discrete Fourier transform // IEEE Trans, on Acoustics, Speech and Signal Processing. Aug. 1984. -Vol. 32.-No. 4.-P. 803−816.

92. Wang Z., BovikA. C., Sheikh H. R., Simoncelli E. P. Image quality assessment: from error visibility to structural similarity // IEEE Transactions on Image Processing. -Apr. 2004. Vol. 13. — No. 4. — P. 600−612.

93. Witten I. H., Neal R. M., Cleary J. G. Arithmetic coding for data compression // Communication of the ACM. June 1987. — Volume 30. — Number 6. — P. 520 -540.

94. Xiong Z., Ramchandran K., Orchard M. Wavelet packets image coding using space-frequency quantization // IEEE Trans, on Image Proc. 1998. -Vol. 7. — No. 6. — P. 892−898.