Вероятностные методы экономного кодирования видеоинформации тема диссертации и автореферата по ВАК РФ 05.13.13, кандидат технических наук Семенюк, Владимир Витальевич

• Семенюк, Владимир Витальевич
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Семенюк, Владимир Витальевич

Введение

1 Вероятностный подход в теории экономного кодирования

1.1. Информационное описание.

1.2. Вероятностный подход.

1.2.1. Энтропия.

1.2.2. Дешифруемые коды.

1.2.3. Оптимальная длина кода.

1.3. Методы генерации кода.

1.3.1. Префиксное кодирование.

1.3.2. Алгоритм Шеннона

1.3.3. Алгоритм Хаффмана

1.3.4. Статические системы префиксных кодов it 1.3.5. Арифметическое кодирование.

1.4. Контекстно-зависимое моделирование.

1.4.1. Проблема идентификации состояний.

1.4.2. Контекстно-зависимые модели.

1.4.3. Метод вложенных разбиений.

1.5. Получение вероятностных оценок на основе статистического анализа информационной выборки.

1.5.1. Метод получения неадаптивных оценок.

1.5.2. Метод получения адаптивных оценок с использованием скользящего окна

1.5.3. Метод получения адаптивных оценок с периодическим масштабированием значений счетчиков частот появления символов.

1.5.4. Метод получения адаптивных оценок с множителем

Введение диссертации (часть автореферата) на тему «Вероятностные методы экономного кодирования видеоинформации»

На сегодняшний день актуальна проблема хранения и передачи информации в цифровом виде. Для получения компактных информационных представлений применяются технологии экономного кодирования. Использование этих технологий позволяет существенно снизить требования, предъявляемые к объему информационных носителей, а также ощутимо увеличивает скорость передачи информации по каналам связи.

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

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

Выбор направления исследования основан на результатах сравнительного анализа существующих алгоритмов экономного кодирования. Алгоритм экономного кодирования представляет собой определенный способ генерации экономного кода на основе приближенной модели порождения кодируемой информации. С целью снижения вычислительной сложности на практике долгое время применялись упрощенные методы

1 Объектом изучения являются методы кодирования, а не сопутствующие им способы преобразования информации. информационного моделирования и генерации кода. В качестве моделей брались простейшие комбинаторные модели, а генерация кода осуществлялась с использованием наиболее быстрых реализаций префиксного кодирования. В настоящее время постановка задачи изменилась: на первый план стала все чаще выходить эффективность кодирования. Сегодня становится целесообразным применение более сложных технологий кодирования, которые позволяют достичь максимально компактного информационного представления.

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

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

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

Задачи исследования. В рамках диссертационного исследования решались следующие задачи:

1. Подробный анализ существующих методов контекстно-зависимого вероятностного кодирования.

2. Повышение эффективности широко распространенных стандартных схем кодирования JPEG и MPEG за счет использования контекстно-зависимых вероятностных методов.

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

При решении указанных задач были выделены и отдельно рассмотрены две подзадачи:

1. Создание строгого формального описания контекстно-зависимых вероятностных моделей.

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

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

На защиту выносятся следующие результаты:

1. Формулировка и доказательство неравенства Макмиллана для случая неразделимых кодов. Вычисление величины оптимального вклада символа в результирующую длину кода.

2. Алгебраическое доказательство оптимальности алгоритма Хаффма-на для системы представления информации с произвольным основанием.

3. Формализация контекстно-зависимых вероятностных моделей.

4. Обобщение метода PPM (Prediction by Partial String Matching) -метод вложенных разбиений.

5. Метод получения адаптивной вероятностной оценки на основе статистики появления символов.

6. Алгоритм экономного кодирования коэффициентов дискретного косинусного преобразования.

7. Алгоритм экономного кодирования изображений на основе дискретного вейвлет-преобразования.

Научная новизна работы:

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

2. Предложено ранее не фигурировавшее в литературе строгое алгебраическое доказательство оптимальности алгоритма Хаффмана для системы представления информации с произвольным основанием.

3. Предложена строгая формализация контекстно-зависимых моделей.

4. Проведено обобщение метода РРМ

5. Предложен новый метод получения адаптивных вероятностных оценок.

6. Разработан новый высокоэффективный алгоритм экономного кодирования коэффициентов дискретного косинусного преобразования.

7. Разработан новый высокоэффективный алгоритм экономного кодирования изображений на основе дискретного вейвлет-преобразования.

Практическая ценность работы:

1. Разработанный алгоритм экономного кодирования коэффициентов дискретного косинусного преобразования позволяет в среднем на 10% повысить эффективность общепринятых стандартных схем JPEG и MPEG.

2. Разработанный алгоритм экономного кодирования изображений на основе дискретного вейвлет-преобразования является наиболее эффективным алгоритмом в своем классе. При фиксированном размере выходного кода эффективность алгоритма на 0.05-0.2 dB выше эффективности аналогичных решений. Алгоритм может быть успешно применен на практике для получения экономных представлений неподвижных изображений и видеопотоков.

3. Предложенный метод получения адаптивных вероятностных оценок является эффективной заменой методу, наиболее часто используемому на практике. В частности, применение разработанного метода в алгоритме кодирования изображений на основе дискретного вейвлет-преобразования в среднем позволило на 0.5% повысить эффективность кодирования и на 10% увеличить его производительность.

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

Результаты диссертационной работы используются в учебном процессе на кафедре компьютерных технологий факультета информационных технологий и программирования Санкт-Петербургского государственного университета информационных технологий, механики и оптики. В частности, автором диссертации самостоятельно разработан и в течение трех лет преподается на кафедре курс лекций «Экономное кодирование дискретной информации».

Апробация результатов работы. Результаты диссертационного исследования были представлены на XI-й всероссийской научно-методической конференции «Телематика'2004», а также на 1-й конференции молодых ученых Санкт-Петербургского государственного университета информационных технологий, механики и оптики.

Публикации. Основные результаты диссертационного исследования опубликованы в 5 работах общим объемом 137 страниц: 3 статьи [6, 7, 8], 1 тезис [9] и 1 монография [10]. Все работы написаны без соавторов.

Структура диссертационной работы выглядит следующим образом. Работа состоит из введения, основной части и заключения. Основная часть включает в себя 2 главы.

Заключение диссертации по теме «Телекоммуникационные системы и компьютерные сети», Семенюк, Владимир Витальевич

2.3. Основные результаты и выводы

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

1. Разработан новый высокоэффективный алгоритм экономного кодирования коэффициентов дискретного косинусного преобразования (см. раздел 2.2.2).

2. Разработан новый высокоэффективный алгоритм экономного кодирования изображений на основе дискретного вейвлет-преобразования (см. раздел 2.2.3).

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

Заключение

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

1. Сформулировано и доказано неравенство Макмиллана для случая неразделимых кодов. Вычислена величина оптимального вклада символа в результирующую длину кода сообщения.

2. Алгебраически доказана оптимальность алгоритма Хаффмана для системы представления информации с произвольным основанием.

3. Предложена строгая формализация контекстно-зависимых вероятностных моделей.

4. Осуществлено обобщение метода РРМ.

5. Предложен новый метод получения адаптивной вероятностной оценки на основе статистики появления символов.

6. Разработан новый алгоритм экономного кодирования коэффициентов дискретного косинусного преобразования.

7. Разработан новый алгоритм экономного кодирования изображений на основе дискретного вейвлет-преобразования.

Список литературы диссертационного исследования кандидат технических наук Семенюк, Владимир Витальевич, 2004 год

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

2. Кричевский Р. Е. Сжатие и поиск информации. М.: Радио и связь, 1989.

3. Левенштейн В. И. Об избыточности и замедлении разделимого кодирования натуральных чисел // Проблемы кибернетики. М., 1968. - Вып. 20. - С. 173 - 179.

4. Рябко Б. Я. Сжатие информации с помощью стопки книг // Проблемы передачи информации. 1980. - Т. 16, Вып. 4. - С. 16 - 21.

5. Рябко Б. Я., Фионов А. Н. Эффективный метод адаптивного арифметического кодирования для источников с большими алфавитами // Проблемы передачи информации. 1999. - Т. 35, Вып. 4. - С. 95 - 108.

6. Семенюк В. В. Алгоритм экономного кодирования коэффициентов дискретного косинусного преобразования // Известия вузов. Приборостроение. 2004. - Т. 47, Вып. 8. - С. 24 - 28.

7. Семенюк В. В. Метод адаптивного кодирования двоичной информационной выборки // Известия вузов. Приборостроение. 2004. -Т. 47, Вып. 5. - С. 36 - 41.

8. Семенюк В. В. Применение вероятностного моделирования в методах экономного кодирования видеоинформации // Труды XI Всероссийской научно-методической конференции Теле-матика'2004. Санкт-Петербург, Россия, 7-10 июня, 2004. -С. 186 - 187.

9. Семенюк В. В. Экономное кодирование дискретной информации.- СПб: СПб ГИТМО (ТУ), 2001. 115 с. - ISBN 5-7577-0076-9.

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

11. Хаффмен Д. А. Метод построения кодов с минимальной избыточностью: Пер. с англ. // Кибернетический сборник. М.: ИЛ, 1961. - Вып. 3. - С. 79 - 87.

12. Шеннон К. Математическая теория связи: Пер. с англ. // Работы по теории информации и кибернетике. М.: ИЛ, 1963. -С. 243 - 332.

13. Шкарин Д. А. Повышение эффективности алгоритма РРМ // Проблемы передачи информации. 2001. - Т. 37, Вып. 3. -С. 44 - 54.

14. Antonini М., Barlaud М., Mathieu P., Daubechies I. Image Coding Using Wavelet Transform // IEEE Trans, on Image Processing.- 1992. Vol. 1, N. 2. - P. 205 - 220.

15. Bloom C. Solving the Problems of Context Modeling. -http: / / www.cbloom.com / papers / ppmz.zip.

16. Bunt on S. Semantically Motivated Improvements for PPM Variants // The Computer J. 1997. - Vol. 40, N. 2/3. - P. 76 - 93 .

17. Calderbank R., Daubechies I., Sweldens W., Yeo B. L. Wavelet Transforms That Map Integers to Integers // J. Applied and Computational Harmonic Analysis (ACHA). 1998. - Vol. 5, N. 3. -P. 332 - 369.

18. Chrysafis C., Ortega A. Efficient Context-Based Entropy Coding for Lossy Wavelet image compression // Proc. IEEE Data Compression Conf. Snowbird, Utah, USA, Mar. 25 - 27, 1997. - P. 241 - 250.

19. Cleary J. G., Witt en I. H. Data Compression Using Adaptive Coding and Partial String Matching // IEEE Trans, on Communications. 1984. - Vol. 32, N. 4. - P. 396 - 402.

20. De Prisco R., De Sentis A. On the Redundancy Achieved by Huffman Codes // Information Sciences. 1996. - Vol. 88, N. 1. -P. 131 - 148.

21. Fano R. M. Technical N65. The Research Labaratory of Electronics, MIT, Max. 17, 1949.

22. Gallager R. G. Variations on a Theme by Huffman // IEEE Trans, on Information Theory. 1980. - Vol. 26, N. 1. - P. 15 - 25.

23. Golomb S. W. Run-Length Encoding // IEEE Trans, on Information Theory. 1966. - Vol. 12, N. 4. - P. 399 - 401.

24. Guazzo M. A General Minimum-Redundancy Source-Coding Algorithm // IEEE Trans, on Information Theory. 1980. - Vol. 26, N. 1.- P. 15 25.

25. Howard P. G. Lossless Image Comression / The Design and Analysis of efficient Lossless Data Comperssion Systems: Tech. rept. N CS-93-28.- Dept. of Computer Science, Brown University, Providence, Rhode Island, USA, 1993.

26. Howard P. G. Text Comression / The Design and Analysis of efficient Lossless Data Comperssion Systems: Tech. rept. N CS-93-28. Dept. of Computer Science, Brown University, Providence, Rhode Island, USA, 1993.

27. Howard P. G., Vitter J. S. Practical Implementations of Arithmetic Coding // Storer A. Image and Text Compression. Kluwer Academic Publishers, Massachusetts, USA, 1992. - P. 85 - 112.

28. Howard P. G., Vitter J. S. Arithmetic Coding for Data Compression // Proc. IEEE. 1994. - Vol. 82, N. 6. - P. 857 - 865.

29. Karush J. A Simple Proof of an Inequality of McMillan // IEEE Trans. Information Theory. Apr., 1961. - IT-7. - P. 118.

30. Kraft L. A Device for Quantizing, Grouping and Coding Amplitude Modulated Pulses: MS Thesis. Dept. of Electrical Engineering, MIT, Cambridge, Massachusetts, USA, 1949.

31. Langdon G. A Simple General Binary Source Code // IEEE Trans. Information Theory. Sep., 1982. - IT-28. - P. 800 - 803.

32. LoPresto S. M., Ramchandran K., Orchard M. T. Image Coding Based on Mixture Modeling of Wavelet Coefficients and a Fast Estimation-Quantization Framework // Proc. IEEE Data Compression Conf. Snowbird, Utah, USA, Mar. 25 - 27, 1997. - P. 221 - 230.

33. Marpe D., Cycon H. L. Efficient Pre-coding Techniques for Wavelet-Based Image Compression // Proc. PCS'97 (ITG Fachbericht). -Berlin, Germany, 1997. P. 45 - 50.

34. McMillan B. Two Inequalities Implied by Unique Decipherability // IEEE Trans. Information Theory. Dec., 1956. - IT-2. - P. 115 - 116.

35. Merhav N., Seroussi G., Weinberger M. J. Coding of Sources with Two-Sided Geometric Distributions and Unknown Parameters // IEEE Trans. Information Theory. Jan., 2000. - Vol. 46, N. 1. -P. 229 - 236.

36. Moffat A. M. A Note on the PPM Data Compression Algorithm: Res. rept. 88/7. Dept. of Computer Science, University of Melbourne, Victoria, Australia, 1988.

37. Moffat A. M. Implementing the PPM Data Compression Scheme 11 IEEE Trans, on Communications. 1990. - Vol. 38, N. 11. -P. 1917 - 1921.

38. O'Neal J. B. Predictive Quantizing Differential Pulse Code Modulation for the Transmission of Television Signals // Bell Systems Tech. J. 1966. - N. 5. - P. 689 - 721.

39. Pasco R. Source Coding Algorithms for Fast Data Compression: Ph.D. thesis. Dept.of Electrical Engineering, Stanford University, California, USA, 1976.

40. Pennebaker W. В., Mitchell J. L., Langdon G. G., Arps R. B.

41. An Overview of the Basic Principles of the Q-Coder Adaptive Binary Arithmetic Coder // IBM J. Research and Development. 1988. -Vol. 32, N. 6. - P. 717 - 726.

42. Rice R. F. Some Practical Universal Noiseless Coding Techniques: JPL Publication 79 22. - Jet Propulsion Labaratory, Pasadena, California, USA, Mar., 1979.

43. Rissanen J. J. Generalized Kraft Inequality and Arithmetic Coding // IBM J. Research and Development. 1976. - Vol. 20, N. 3. -P. 198 - 203.

44. Rissanen J. J., Langdon G. G. Arithmetic Coding // IBM J. Research and Development. 1979. - Vol. 23, N. 2. - P. 146 - 162.

45. Rubin F. Arithmetic Stream Coding Using Fixed Precision Registers // IEEE Trans. Information Theory. 1979. - Vol. 25, N. 6. -P. 672 - 675.

46. Rubin F. Experiments in Text File Compression // CACM. 1976. -Vol. 19, N 11. - P. 617 - 623.

47. Said A. and Pearlman W. A. A New Fast and Efficient Image Codec Based on Set Partitioning in Hierachical Trees // IEEE Trans.on Circuits and Systems for Video Technology. 1996. - Vol. 6, N. 3.- P. 243 250.

48. Shapiro J. M. Embedded Image Coding Using Zerotrees of Wavelets Coefficients // IEEE Trans, on Signal Processing. 1993. - Vol. 41, N. 12. - P. 3445 - 3462.

49. Schindler M. A Fast Renormalization for Arithmetic Coding // Proc. IEEE Data Compression Conf. Snowbird, Utah, USA, Mar. 30 -Apr. 1, 1998. - P. 572.

50. Taubman D. High Performance Scalable Image Compression with EBCOT // IEEE Trans, on Image Processing. 2000. - Vol. 9, N. 7. -P. 1170 - 2000.

51. Weinberger M. J., Seroussi G., Sapiro G. The LOCO-I Lossless Image Compression Algorithm: Principles and Standardization into JPEG-LS // IEEE Trans, on Image Processing. 2000. - Vol. 9, N. 8.- P. 1309 1324.

52. Witten I. H., Bell Т. C. The Zero Frequency Problem: Estimating the Probabilities of Novel Events in Adaptive Text Compression // IEEE Trans. Information Theory. 1987. - Vol. 37, N. 6. -P. 1085 - 1094.

53. Witten I. H., Neal R. M., Cleary J. G. Arithmetic Coding for Data Compression // CACM. 1987. - Vol. 30, N 6. - P. 520 - 540.

54. Wu X., Memon N. D. Context-Based, Adaptive, Lossless Image Coding // IEEE Trans, on Communications. 1997. - Vol. 45, N. 4. -P. 437 - 444.

55. Xiong Z., Ramchandran K., Orchard M. T. Space-FYequency Quantization for Wavelet Image Coding // IEEE Trans, on Image Processing. 1997. - Vol. 6, N. 5. - P. 677 - 693.

56. Xiong Z., Ramchandran K., Orchard M. T. Wavelet Packet Image Coding Using Space-Frequency Quantizaion // IEEE Trans, on Image Processing. 1998. - Vol. 7, N. 6. - P. 892 - 698.

57. Yoo Y., Ortega A., Yu B. Image Subband Coding Using Progressive Classification and Adaptive Quantization // IEEE Trans, on Image Processing. 1999. - Vol. 8, N. 12. - P. 1702 - 1715.

58. Zandi A., Allen. J., Schwartz E., Boliek M. CREW: Comression with Reversible Embedded Wavelets // Proc. IEEE Data Compression Conf. Snowbird, Utah, USA, Mar. 28 - 30, 1995. - P. 351 - 360.

59. ISO/IEC / JTC 1/SC 29/WG 10 Information Technology -Digital Compression and Coding of Continuous-Tone Still Images, ISO/IEC 10918.

60. ISO/IEC / JTC 1/SC 29/WG 11 Information Technology -Coding of Moving Pictures and Associated Audio for Digital Storage Media at up to About 1,5 Mbit/s, ISO/IEC 11172.

61. ISO/IEC / JTC 1/SC 29/WG 11 Information Technology -Generic Coding of Moving Pictures and Associated Audio Information, ISO/IEC 13818.

62. ISO/IEC / JTC 1/SC 29/WG 1 Information Technology Lossless and Near-Lossless Compression of Continous-Tone Still Images, ISO/IEC 14495.

63. ISO/IEC / JTC 1/SC 29/WG 11 Information Technology -Coding of Audio-Visual Objects, ISO/IEC 14496.

64. ISO/IEC JTC 1/SC 29/WG 11 and ITU-T SG 16 Q.6 Study of Final Committee Draft of Joint Video Specification, ITU-T Rec. H.264 / ISO/IEC 14496-10 AVC, JVT-F100, Dec., 2002.

65. ISO/IEC / JTC 1/SC 29/WG 1 Information Technology JPEG 2000 Image Coding System, ISO/IEC 15444.

66. ISO/IEC / JTC 1/SC 24/WG 7 Information technology -Computer Graphics and Image Processing Portable Network Graphics (PNG): Functional Specification, ISO/IEC 15948.

67. ITU-T SG 16 Video Codec for Audiovisual Services at px64 kbits, ITU-T Recommendation H.261.

68. ITU-T SG 16 Video coding for low bit rate communication, ITU-T Recommendation H.263.