Введение к работе
Актуальность темы. Развитие сети Интернет и других мультимедийных приложений наряду с доступностью все более мощных компьютеров и прогрессом в технологии производства медиа-устройств привели к широкому использованию цифровых изображений, к заниманию ими все большей части информационного пространства. В последние годы быстро развиваются системы передачи, обработки и хранения мультимедийной информации. На этом фоне важным является решение вопросов устранения информационной избыточности, улучшения алгоритмов сжатия изображений и их восстановления и разработки эффективных, вычислительных процедур для реализации этих алгоритмов. Сжатие актуально для повышения как скорости передачи, так и эффективности хранения изображений.
Дискретное вейвлет-преобразование (ДВП) и векторное квантование (ВК) являются двумя мощными и эффективными инструментами,, применяемыми для сжатия изображений. В последние 10-15 лет было написано много работ и статей о них, были приложены огромные усилия объединить их для получения еще более эффективных методов. На сегодняшний день предложено немало алгоритмов и методов сжатия изображений в области ДВП, действует основанный на ДВП международный стандарт JPEG2QQ0.
Квантование данных является хорошо изученной задачей. В то же время вопрос минимизации объема сжатых квантованных данных при заданной допустимой ошибке квантования, известный еще как проблема распределения бит, в общем виде не имеет решения (существуют решения для частных случаев). Кроме того, применение на практике метода ВК встречает ряд проблем. Статистические характеристики данных должны быть известны заранее и не изменяться, по возможности, во время сжатия, а фотографические изображения обычно обладают нестационарной статистикой. Также теоретически оптимальный квантователь может быть получен с нереальными условиями - произвольные значения (в достаточной мере большие) размерности и количества векторов представления. Наконец, ВК -достаточно сложный и трудоемкий метод, хоть и очень эффективный. Поэтому на практике необходимо применять дополнительные меры. Помимо этого, многие исследования направлены на развитие процессов генерации кодовых книг.
Увеличение степени сжатия изображений методами на основе ДВП приводит к росту значений ошибок восстановления вейвлет-коэффициентов и визуальному ухудшению восстановленных изображений. При использовании традиционных алгоритмов мелкие детали (границы) частично теряются при высоких степенях сжатия - наблюдаются размытости целых областей в изображении. Сохранение этих деталей является важным при сжатии фотографических изображений.
В связи с этим актуальной является задача поиска эффективных алгоритмов обработки значений вейвлет-коэффициентов, позволяющих сократить потери информации при квантовании и восстановлении значений вейвлет-коэффициентов. Кроме того, есть необходимость исследования и совершенствования существующих методов и средств сжатия на основе ВК в области ДВП для решения описанных выше проблем, а также улучшения их характеристик и расширения области применения.
В общем виде решение задачи сжатия цветных фотографических изображений можно свести к решению задачи эффективного сжатия полутоновых (grayscale) изображений (ПИ) изображений с глубиной цвета 8 бит на пиксел. Это следует из того, что изображение с цветовой схемой RGB первоначально представляется в виде комбинации яркостнои и двух цветовых составляющих.
Область исследования. Диссертационная работа выполнена в соответствии с пунктами 4 - «Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации», 5 - «Разработка специального математического и программного обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации», 12 - «Визуализация, трансформация и анализ информации на основе компьютерных методов обработки информации» специальности 05.13.01 - «Системный анализ, управление и обработка информации (в науке и технике)» и пунктами 2 - «Исследование процессов генерации, представления, передачи, хранения и отображения аналоговой, цифровой, видео-, аудио- и мультимедиаинформации; разработка рекомендаций по совершенствованию и созданию новых соответствующих алгоритмов и процедур», 12 - «Разработка методов эффективного использования сетей, систем и устройств телекоммуникаций в различных отраслях народного хозяйства (связь)» специальности 05.12.13 - «Системы, сети и устройства телекоммуникаций».
Объектом исследования являются способы преобразования, сжатия и передачи полутоновых изображений по цифровым каналам связи телекоммуникационных сетей с позиции системного подхода.
Предметом исследования являются формы представления, методы сжатия и обработки полутоновых изображений в области дискретных вейвлет-преобразований, методы адаптивного векторного квантования, пространствен-но-ориентирован-ного и энтропийного кодирования данных, в частности, цифровых изображений, методы оптимального кодирования на базе информационной теории Rate-Distortion, методы децимации коэффициентов преобразования.
Цель работы состоит в проведении комплексных исследований для получения научно-обоснованных решений, направленных на разработку эффективных систем, методик и алгоритмов сжатия полутоновых изображений, основанных на адаптивном и многоступенчатом решетчатом векторном квантовании, дискретном вейвлет-преобразовании, позволяющих увеличить точность обработки деталей изображений, практическое применение которых повысит качественные характеристики систем архивирования данных и передачи графической информации по каналам связи.
Для достижения поставленной цели необходимо решить следующие задачи:
провести анализ существующих систем и методов сжатия ПИ на базе ВК в области ДВП с определением возможности их модификации и создания новых, способных к адаптации в процессе обработки и позволяющие ограничить допустимые потери и обеспечить требуемые показатели качества; выполнить синтез схемы трансформационного кодирования ПИ, обладающей малой ресурсоёмкостью и относительно невысокой вычислительной сложностью;
уточнить классификацию алгоритмов адаптивного ВК (АВК) на основе
критерия битрейт-искажение (R-D) с выделением сильных и слабых сторон для разработки простого и надежного алгоритма, соответствующего поставленным задачам, позволяющего выбирать нужные приоритеты в сжатии изображения;
исследовать и применить структурированный метод решетчатого ВК (РВК) для уменьшения сложности вычислений, отказавшись от трудоемкого полного поиска при формировании кодовых книг;
создать методику сжатия ПИ на базе многоступенчатого ВК, которая будет эффективно уменьшать ошибки квантования значимых коэффициентов субполос ДВП для получения лучшего качества обрабатываемого изображения;
разработать новые алгоритмические решения процесса обработки ПИ, сокращающие используемые вычислительные ресурсы - объемы потребляемой памяти и время вычислений (время кодирования/декодирования) при значительном уменьшении, по сравнению с известными подходами, вносимых в процессе кодирования искажений; обеспечить высокие скорость и степень сжатия результатов квантования субполос ДВП, исследовав и применив эффективный энтропийный метод кодирования без потерь;
провести вычислительные экспериментальные исследования разработанных методик и алгоритмов кодирования ПИ, выполнить аналитическое и имитационное моделирование; оценить коэффициент сжатия и искажение восстановленных изображений, сжатых с помощью предложенных методик и алгоритмов, в сравнении с аналогичной оценкой существующих алгоритмов компрессии для определения их эффективности и возможностей.
Методы исследования. В диссертационной работе применялись теоретические и экспериментальные методы исследования.
Теоретические исследования основаны на использовании теории информации, теории кодирования источника, математической статистики, теории вероятности, основ машинной графики, теории обработки и анализа изображений.
В экспериментальных исследованиях разработанных моделей, методик и алгоритмов применялись методы системного анализа, прикладной теории информации, кодирования и ДВП изображений, цифровой обработки изображений и машинной графики, основы системного программирования и имитационного моделирования. Была осуществлена программная реализация алгоритмов в среде Matlab с последующей проверкой разработанных теоретических положений и оценкой полученных результатов, включающей сравнение с существующими методами.
При создании программной модели применялись численные методы, методы объектно-ориентированного программирования.
Достоверность и обоснованность полученных в работе результатов и выводов подтверждается сопоставительным анализом разработанных и существующих методик и алгоритмов, а также итогами проведения вычислительного эксперимента и компьютерного моделирования.
Теоретические положения, установленные в работе, обосновываются последовательным и корректным применением математического аппарата при получении выводов из исходных посылок, а также аналитической проверкой этих посылок и выводов результатами систематического исследования.
Достоверность результатов экспериментального исследования обеспечена их согласованностью с результатами теоретического исследования и воспроизводимостью па объемах экспериментального материала, а также выбором обоснованных критериев при построении алгоритмов обработки информации, обос-
nuj»annv^mn.» inJvi|_*w^ruxtt <ші Ojjri juviun uv>pttvUjtJ\.Ja iijri, паїллдгі^^іР-tvi .cj..d.i.C|jii|jc;ia-
ции полученных практических результатов.
На защиту выносятся результаты разработки и.исследования новых методик и алгоритмических решений сжатия ПИ, а также результаты их моделирования, в том числе:
формальная схема ВК, описывающая его основные определения и свойства в кратких терминах и обозначениях;
классификация алгоритмов АВК на основе критерия битрейт-искажение (R-D), результаты их сравнения между собой;
онлайновый алгоритм АВК субполос ДВП (АСВК) с возможностью контроля битрейта кодирования, а также качества изображения;
схема РВК и формирование кодовой книги решетчатого квантователя, алгоритм квантования на основе кубической решетки, обладающей самой простой формой структуры и позволяющей уменьшить сложность вычислений;
методика и алгоритм многоступенчатого РВК (МРВК), уменьшающая ошибки квантования значимых коэффициентов высокочастотных субполос ДВП, структура кодера и декодера ПИ на их основе;
алгоритм адаптивной обработки порогового значения (АОП) для поиска значимых коэффициентов в субполосе и аппроксимация пороговой функции;
реализация модифицированного энтропийного адаптивного кодирования кодами переменной длины с кодами Голомба результатов квантования субполос ДВП на основе обхода по битовым плоскостям;
программная модель и полученные с ее помощью результаты проведения экспериментальных исследований и проверки разработанных методик и алгоритмов сжатия ПИ, их сравнительная оценка с существующими на примере тестовых изображений по показателю PSNR и степени сжатия.
Научная новизна результатов диссертационного исследования, полученных лично автором, заключается в следующем:
предложена и исследована схема обработки ПИ для эффективного их сжатия на основе технологии ВК в области ДВП, учитывающая внутри- и межполосные зависимости между вейвлет-коэффициентами и позволяющая варьировать показатели степени сжатия и искажения;
уточнена 'классификация алгоритмов метода АВК на основе критерия битрейт-искажение (R-D); выполнено аналитическое сравнение алгоритмов и отмечены достоинства и недостатки алгоритмов;
разработан онлайновый алгоритм АСВК, являющийся быстрым, т.к. выполняется за один цикл, и надежным в результате того, что потери контролируются такими предельными параметрами, как битрейт и искажение; его применение в методе сжатия уменьшает сложность вычислительных процессов генерации кодовых книг по сравнению с аналогичными алгоритмами, а свойство адаптивности позволяет решить вопрос нестационарности кодируемых изо-
бражений и серьезно уменьшить размерности векторов и, что является, отчасти, следствием последнего, размеры строимых кодовых книг;
- применено и исследовано РВК на основе кубической решетки для сжа
тия коэффициентов субполос ДВП ПИ, которое обеспечивает значительное
Уиіvxioiuwiikxw Cjivj-MMiuvifi >ui-i»iwjivni:irl, ULi\fctii>ii>*A7ivi> иі I^jj^uwyuvvjivJ iiujiriOivj ло-
иска, и существенное сокращение сложности структуры схемы кодирования на основе ВК за счет решетчатых регулярных структур;
предложена методика многоступенчатого РВК и её вычислительно эффективный алгоритм для значительного уменьшения ошибок квантования значимых высокочастотных вейвлет-коэффициентов, основанный на масштабировании их перед квантованием и после восстановления; представлена гибридная схема кодера и декодера ПИ на ее основе;
разработаны схема и алгоритм АОП для более точного поиска значимых коэффициентов в субполосах, вычисляющая пороговые значения за два шага; выполнена аппроксимация пороговой функции;
построена и применена модифицированная схема энтропийного кодирования последовательности индексов решетчатой кодовой книги на основе кодов Голомба, обеспечивающая высокие степень и скорость сжатия.
Практическая полезность работы заключается в применении новых эффективных методик и алгоритмов сжатия ПИ. Разработана программная модель, реализующая методы и технологию обработки ПИ на основе использования РВК в области вейвлет-преобразований. Она обеспечивает реализацию предложенных вычислительных схем и алгоритмов обработки ПИ, эффективное их кодирование и сжатие, что позволяет использовать модель в целях исследовательских экспериментов и дальнейшего развития предложенных методик для цветных изображений.
Важным для практики результатом теоретических изысканий является то, что разработанные алгоритмы кодирования ПИ на практике свели вычислитель-ноемкую комбинаторную задачу ВК коэффициентов субполос ДВП к однопроходной процедуре обработки адаптируемой кодовой книги, что можно считать эффективным с точки зрения экономии ресурсов медиа-устройств - объема потребляемой памяти и загрузки процессора, а также обеспечили надежность ре-зультата'ввиду того, что потери контролируются предельными параметрами. Эффективность предложенной методики заключается в сокращении на целый порядок количества вычислительных операций и увеличения качества восстановленного после сжатия изображения по сравнению с традиционными алгоритмами.
Структура разработанных алгоритмов сжатия ПИ предоставляет разработчикам возможность эффективной программно-аппаратной реализации на различных типах вычислительных систем. Предложенные способы кодирования изображений могут быть использованы в системах передачи, обработки и хранения графической информации, а результаты диссертационного исследования можно рекомендовать для внедрения в учебный процесс.
Реализация и использование результатов работы. Полученные результаты использованы и апробированы для опытно-производственной эксплуатации системы обработки графических данных, их представления и кодирования
для повышения коммуникативных возможностей в телекоммуникационных системах в ЗАО «Ресурсинвест».
Полученные результаты использованы в учебном процессе ГОУ ВПО «ИжГТУ» при изучении дисциплин «Компьютерная трафика», «Интерактивные графические системы», «Кодирование и цифровая обработка информации».
Апробация работы. Основные положения и результаты диссертации докладывались на российских и международных научно-технических конференциях и симпозиумах, а конкретно на: Российской научно-технической конференции «Приборостроение в XXI веке. Интеграция науки, образования и производства» (Ижевск, 2006); Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы» (Таганрог, 2007); Международной научно-технической конференции «Информационные технологии в инновационных проектах» (Ижевск, 2007); 34-й и 35-й Международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе» (Украина, Крым, Ялта-Гурзуф, 2007, 2008); Международном симпозиуме «Надежность и качество» (Пенза, 2008); IX Международной научно-технической конференции «Искусственный интеллект — 2008. Интеллектуальные системы - 2008» (пос. Кацивели, АР Крым, Украина, 2008).
Публикации. Основные научные результаты по теме диссертации опубликованы в 15 научных работах в региональных журналах, сборниках научных трудов и материалов конференций. Автор имеет 3 научных труда в изданиях, выпускаемых в РФ и рекомендуемых ВАКом для публикации основных результатов диссертаций.
Структура диссертационной работы. Диссертация содержит введение, 4 главы и заключение, изложенные на 152 стр. машинописного текста. В работу включены 40 рис., 5 табл., список литературы из 126 наименований. В приложении представлен акт об использовании результатов работы.
Похожие диссертации на Инструментальные средства сжатия полутоновых изображений на основе адаптивного и многоступенчатого решетчатого векторного квантования
