Система предикативного сжатия графической информации на основе ее представления в виде полевой структуры тема диссертации и автореферата по ВАК РФ 05.12.13, кандидат технических наук Носков, Алексей Борисович

• Носков, Алексей Борисович
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Носков, Алексей Борисович

1. Анализ существующих методов сжатия графической информации

1.1. Система обработки изображений

1.2. Функция изображения

1.3. Хранение видеоданных

1.3.1. TIFF-формат

1.3.2. GIF-формат

1.3.3. JPEG-формат

1.3.3.1. Дискретное косинусное преобразование (DCT)

1.3.3.2. Квантование

1.3.3.3. Сжатие

1.3.3.4. Перспективы методов сжатия с потерями

1.3.3.5. Техника сжатия JPEG без потерь (Lossless Л^ЕО)

1.3.4. Формат BMP

1.4. Методы сжатия полутоновых изображений

1.4.1. Модель изображения

1.4.2. Предикативное кодирование

1.4.3. Адаптивное квантование

1.4.4. Адаптивное предсказание

1.4.5. Замечания о предикативном кодировании

1.4.6. Системы кодирования с синтезом высокочастотной составляющей

1.4.7. Кодирование с обрезанием блоков

1.4.8. Метод пирамиды лапласианов

1.4.9. Контурно-текстурная схема

1.4.10. Кодирование цветных изобраэюений

1.4.11. Кодирование псевдоцветами

1.5. Точность восстановления изображения

1.6. Обобщение характеристик и особенностей различных графических форматов

1.7. Выводы

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

2.1. Математическая модель

2.2. Переход от «аналоговой» модели к «цифровой»

2.2.1. Особенности дискретной модели

2.2.2. Экспериментальная проверка цифровой модели

2.3. Вероятностные оценки сжатия на основе полевой модели

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

2.3.2. Возможности сж:атия за счет устранения плоскостной корреляции

2.4. Первоначальная модель системы сжатия

2.4.1. Процедура разделения исходного изобраэюения

2.4.2. Экспериментальная проверка эффективности разделения изобраэюения на предикативное и остаточное поле

2.5. Выводы

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

3.1. Структура замкнутой системы сжатия

3.2. Процедуры и интерфейс замкнутой системы сжатия

3.3. Оценка эффективности сжатия

3.4. Выводы

4. Усовершенствование системы сжатия на основе полевой модели

4.1. Улучшение цветовой насыщенности предикативного поля

4.1.1. Поле цветности как совокупность решений краевых задач для полностью перекрывающих исходное изображение зон

4.1.2. Приближенное решение краевой задачи для каж:дой зоны

4.1.3. Разработка алгоритма ИЗ

4.2. Подсистема сжатия контурной информации на основе кромок

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

4.4. Алгоритм сжатия кромок

4.5. Построение конечной улучшенной системы сжатия

4.6. Применение системы предикативного сжатия в Интернет

4.7. Выводы

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

Данная работа посвящена созданию системы сжатия графической информации на основе особого подхода к представлению изображений, который ранее в литературе не встречался и строился с непосредственным участием автора [1-10]. Под системой здесь понимаются в совокупности элементы, на основе которых строился конечный результат, - программа сжатия и восстановления, а именно: математическая модель, «цифровая» форма модели, алгоритм компрессии и декомпрессии, экспериментальные модели проверки работоспособности составляющих алгоритмов, разработанные отладочные программы, и, наконец, конечная программная система сжатия и восстановления изображений по разработанной в рамках диссертации схеме.Область и инструменты исследования. Областью исследования в работе являются новые подходы к сжатию графической информации на основе ее представления в виде полевой структуры.Инструментами исследования и разработки служили: уравнения состояния, вероятностные оценки, различные платформы языка программирования C++ и многочисленные эксперименты с применением, в первую очередь, компонент разработанной системы, а также стандартных средств обработки и контроля изображений [1-4,6,8-15,17-48].Актуальность темы. Использование графической информации широко распространено в любых видах информационных систем. Объемы графической информации обьлно превосходят другие типы данных, а затраты ресурсов на сжатие зачастую бывают дешевле затрат на хранение несжатых данных и их передачу, поэтому сжатие графики имеет высокую степень актуальности, как для целей хранения графических данных, так и для их передачи. Качество и степень сжатия влияют на эффективность использования графики во всех системах информационного обеспечения. При этом наибольшую степень сжатия получают в методах, для которых характерна несущественная (неразличимая глазом) потеря информации. В настоящее время таких методов, которые работают по сложным алгоритмам и разрабатываются, как правило, специализированными группами разработчиков и компаниямипроизводителями программного обеспечения, существует достаточно большое количество. Однако универсального и пригодного по всем статьям метода или способа сжатия не существует [12,15,17,23,27,29]. Кроме того, дефицит отечественных методов с большой степенью сжатия создает юридические сложности при разработке больших телекоммуникационных систем, включающих в себя в качестве компонент системы сжатия графической информации.Вышесказанное позволяет сделать однозначный вывод, что исследование любых новых подходов и методов сжатия и восстановления графической информации, является достаточно востребованным и экономически оправданным.Цель исследования. Целью представленной работы является проведение теоретических и практических исследований по возможности сжатия визуальной информации на основе ее представления в виде полевой структуры.В такой полевой структуре совокупность значений градаций цветности в точках изображения рассматривается как некое скалярное поле. Эти исследования были проведены для случая, в котором полевая структура изображения строится на основе функции Грина для двухмерного уравнения Пуассона [13,8,16,19,34].Основные задачи исследования.1. Используя в качестве основы функцию Грина для уравнения Пуассона [1-3,8,16], исследовать возможность создания целесообразного предикативного поля, которое создается особыми точками (пикселями с резкими перепадами градаций цветности). Решены следующие подзадачи: - разработка процедуры перехода к дискретной модели при наличии обобщенных функций, характерных при работе с функциями Грина; вероятностная оценка эффективности разделения исходного изображения на предикативное и остаточное поля; - построение адекватной алгоритмической и программной моделей; - проведение на указанной модели экспериментов с различными типами изображений.2. Построение (для оценки возможности эффективного раздельного сжатия изображения) первоначальной замкнутой системы, в которой исходное изображение делится на предикативное поле и остаточное поля с дальнейшей их раздельной компрессией и декомпрессией. В качестве исходного материала послужили: разработанная на первом этапе модель (предварительная математическая модель сжатия и восстановления предикативного поля) и программные коды метода JPEG [12], использованного для сжатия остаточного поля. Построение этой сложной в алгоритмическом и программном аспектах системы потребовало разработки не только схем сжатия и восстановления изображения и соответствующих алгоритмов и программных кодов, но и развитого интерфейса, позволяющего производить на этой системе различные исследования для развития метода сжатия.3. Разработка усовершенствованной (конкурентоспособной) системы сжатия визуальной информации. Эта задача решалась в двух аспектах: - теоретические и экспериментальные исследования возможности увеличения степени сжатия за счет усложнения схемы обработки путем введения дополнительного поля («поля цветности»); - построение усовершенствованной подсистемы сжатия контурной составляющей (набора особых точек) на основе новой математической модели представления этой составляющей и обработки (дополнительно это потребовало разработки модулей сжатия и восстановления указанного набора с высокой степенью компрессии).Практическая ценность и область применения результатов.Разработанный метод сжатия графической информации и его программная реализация относятся к области исследований, которые создают новую основу построения разнообразных систем сжатия для применения в Интернет, видеоконференциях, системах хранения графических данных и других информационных системах, использующих графический способ представления информации. В проведенных исследованиях намечены пути дальнейшего совершенствования разработанной системы сжатия с целью одновременного увеличения степени сжатия и улучшения качества восстановленных изображений. Это дает возможность при продолжении разработок в данном направлении улучшать конкурентоспособность этой разработки в отношении существующих методов сжатия графических изображений.Выносимые на защиту положения 1. Если визуальная информация полностью определяется матрицей интенсивности (набором значений цветовых градаций в каждом пикселе), то последняя, представленная в виде полевой структуры, является хорошей моделью для обработки и сжатия изображений.2. Частное решение двухмерного уравнения Пуассона, используя свойства функции Грина, позволяет выделить из изображения составляющую с ярко выраженной контурной корреляцией.3. Рассчитанная и апробированная коррекция частного решения уравнения Пуассона позволяет перейти к цифровой модели не только в регулярных точках (пикселях), но и в окрестностях особых точек, для которых характерен резкий перепад градаций цветности.4. Разделение исходного изображения на предикативное и остаточное поля с последующим их раздельным сжатием дает возможность увеличить (в некоторых случаях существенно) сжатие изображений.5. Введение «поля цветности», которое в сумме с частным решением уравнения Пуассона в первом приближении соответствует общему решению, существенно приближает предикативное поле к исходному изображению.6. Разработанный формат представления цепочек из особых точек позволяет заметно увеличить степень компрессии предикативного поля.7. Метод сжатия, основанный на полевой модели, является более универсальным, чем, например, метод JPEG и GIF.Достоверность исследования основана на применении апробированного уравнения Пуассона и решении соответствующих краевых задач, а также подтверждается результатами работы системы предикативного сжатия графической информации, построенной в результате множества преобразований и видоизменений исходного варианта. Данные, полученные в результате большого количества экспериментов, произведенных как на этапах построения системы сжатия, так и на конечном ее варианте, дают основание считать результаты исследовательской работы достоверными. Кроме того, достоверность результатов получила подтверждение в результате экспертных оценок по ГОСТу 26320-84, проведенных в СПб филиале ОАО «ВымпелкомРегион» (см. акт экспертной оценки).Внедрение полученных результатов. Результаты диссертационной работы внедрены в ООО НПФ «Беркут» при разработке системы организации телеконференций в качестве алгоритмической базы (см. акт внедрения). Кроме того, они также используются в лекционных и лабораторных занятиях по специальности 220400 «Программное обеспечение вычислительной техники и автоматизированных систем», в НИРС и УИРС. С помощью разрабатываемой системы можно будет уменьшить затраты ресурсов на хранение и передачу по сети графической информации, что безусловно станет ценным достижением. Ведь при существующем многообразии методов и алгоритмов сжатия, которые разрабатывались огромным количеством специалистов, любые, даже малые преимущества нового метода компрессии относительно существз^ющих, будут свидетельством его конкурентоспособности и ценности.Поэтому, прежде чем приступать к разработке, проведем анализ основных существующих алгоритмов сжатия графики для определения их недостатков, из которых будет следовать необходимое направление исследования, приводящее к достижению поставленной цели.

Заключение диссертации по теме «Системы, сети и устройства телекоммуникаций», Носков, Алексей Борисович

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

(высокочастотное) поле и остаточное поле на основе функции Грина для двухмерного уравнения Пуассона.4. Разработана процедура перехода от непрерывной к цифровой модели для выражений, включающих функции Грина.5. Произведены вероятностные оценки эффективности разделения изображения на предикативное и остаточное поле для последующего сжатия.6. Разработана алгоритмическая и программная модель, позволившая экспериментально подтвердить эффективность раздельного сжатия составляющих изображения.7. Построена замкнутая система сжатия, которая на основе предложенного подхода позволяет сжимать изображения на уровне лучших методов сжатия.8. Разработана процедура трехступенчатого сжатия за счет введения «поля цветности», что позволило существенно приблизить предикативное поле к исходному изображению.9. Разработан новый формат сжатия, учитывающий «плавные» изменения цветовых градаций вдоль контура, что позволило существенно увеличить степень компрессии предикативного поля.Ю.Построена усовершенствованная система сжатия, в которой полученные результаты не уступают (а для некоторых случаев специальных изображений, существенно превосходят) методам GIF и JPEG.В целом, можно констатировать, что решение в данной диссертационной работе комплекса задач позволило на основе полевых структур, ограниченных рамками уравнения Пуассона, создать конкурентоспособную систему сжатия с хорошими перспективами ее дальнейшего развития.

Список литературы диссертационного исследования кандидат технических наук Носков, Алексей Борисович, 2004 год

1. Носков А.Б. и др. Сжатие графической информации на основе представления изображения в виде полевой структуры // Труды учебных заведений связи / СПбГУТ. СПб, 1998. № 164. 88.

2. Носков А.Б. и др. Концепция сжатия графической информации на основе представления изображения в виде полевой структуры // 5-я ICNAS: сб. докл. / ЛОНИИС. СПб, 1998.

3. Носков А.Б. и др. Алгоритм компрессии и декомпрессии графической информации, представленной в виде полевой структуры // 52 НТК: тез. докл. / СПбГУТ. СПб, 1999. 36.

4. Носков А.Б. Построение TCP/IP стека для обучающих целей // 51-я НТК: тез. докл. / СПбГУТ. СПб, 1998. 117.

5. Носков А.Б. я др. Разработка подсистемы сжатия информации в виде упорядоченных цепочек // 52-я НТК: тез. докл. / СПбГУТ. СПб, 1999. 36.

6. Носков А.Б. Построение системы сжатия графической информации для передачи по каналам связи с помощью протокола TCP/IP в режиме реального времени // 52-я НТК: тез. докл. / СПбГУТ. СПб, 1999. 38.

7. Носков А.Б. Разработка интернет-приложения с использованием предикативного метода сжатия графической информации // 2-я Международная НТК «Техника и технология связи» / СПбГУТ. СПб, 2000. 32.

8. Носков А.Б и др. Система предикативного сжатия изображения на основе полевой модели // Труды учебных заведений связи / СПбГУТ. СПб, 2000. № 166. 36.

9. Климов А. Форматы графических файлов. Киев: ДиаСофт ЛТД, 1995.

10. Боровик А.А. Технология сжатия данных // Компьютер. 1991. № 2.

11. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. М.: Наука, 1968.

12. Ансон Л., Барнсли М. Фрактальное сжатие изображений // Мир ПК. 1992. №4. 21 .Орловский Е.Л. Передача факсимильных изображений. М.: Связь, 1980.

13. Прэтт У. Цифровая обработка изображений / Пер. с англ. М.: Мир, 1982.

14. Шеннон К. Работы по теории информации и кибернетике / Пер. с англ. М.: Иностранная литература, 1963. 2А.Яншин В.В. Анализ и обработка изображений: Принципы и алгоритмы: учебное пособие для вузов. М.: Машиностроение, 1995.

15. Мюррей Д.Д , Райнер У. Ван. Энциклопедия форматов графических файлов / Пер. с англ. Киев: BITV, 1997

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

17. Сван Т. Форматы файлов Windows. М.: Бином, 1995. 2S. Александров B.B., Горский Н.Д. Представление и обработка изображений: рекурсивный подход. Л.: Наука, 1985.

18. Александров В.В., Горский Н. Д. Алгоритмы и программы структурного метода обработки данных. Л.: Наука, 1983. ЪОДуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976. ЪХ.Розенфелъд А. Распознавание и обработка изображений. М.: Мир, 1972.

19. Ефимов В.М., Золотухин Ю.Н., Колесников А.Н. Оценка эффективности некоторых алгоритмов сокращения избыточности информации при абсолютной точности воспроизведения // Автометрия. 1991. № 6.

20. Rosenfeld А., Как А.С. Digital Picture processing. New York: Academic Press, 1982.

21. Green W.B. Digital Image Processing. New York, 1982.

22. Pavlidis T. Algorithms for Graphics and Image Compression. Rockville MD: Computer Science Press, 1982. Зв.ЫпсИеу A. Practical Image Processing in C. Wiley. New York, 1991.

23. Batchelor В., Waltz F. Interactive Image Processing for Machine Vision, Springer, Berlin, 1993. 3%.Pitas I. Digital Image Processing Algorithms. Prentice Hall, Englewood CHffs,NJ, 1993.

24. Dougherty E.R. Digital Image Processing Methods. New York: Dekker, 1994.

25. Kabir I. High Performance Computer Imaging, Manning. Prentice Hall, August 1996.

26. Huang T.S. Advances in Computer Vision and Image Processing: Volume 2, Image Enhancement and Restoration. Greenwich, CT: JAI Press Inc., 1986.

27. Simon J.C. From Pixels to Features. Amsterdam: North Holland, 1989.

28. Landy M.S. Computational Models of Visual Processing. Cambridge MA: MIT Press, 1991.

29. Paulus D. Pattern Recognition and Image Processing in C++. Vieweg Braunschweig (Germany), 1995.

30. Spann М., Nieminen A. Adaptive Gaussian Weighted Filtering for Image Segmentation. PRL, 1988.

31. Pai N.R., Pal S.K. Image Model, Poisson Distribution and Object Extraction. PRAI, 1991.