Содержание к диссертации
Введение
1. Анализ методов сжатия и маркирования изображений 10
1.1. Классы цифровых изображений 11
1.2. Кодирование и декодирование изображения 13
1.3. Классификация алгоритмов сжатия 16
1.4. Методы обхода плоскости 18 1.4Л. ZigZag сканирование 18
1.4.2. Обход строками 19
1.4.3. Обход полосами 19
1.4.4. Контурный обход 20
1.4.5. Обход по спирали 21
1.5. Методы сжатия изображений без потерь 22
1.5.1. Сжатие методом кодирования серий (RLE) 22
1.5.2. Сжатие по методу Хаффмана 23
1.5.3. Алгоритм Лемпеля-3ива 23
1.5.4. Алгоритм JBIG 24
1.5.5. Алгоритм Lossless JPEG 25
1.6. Сжатие изображений с потерями 26
1.6.1. Метод сжатия JPEG 27
1.6.2. Рекурсивно волновой алгоритм 30
1.6.3. Фрактальные методы сжатия 32
1.7. Оценка качества восстановленного изображения 35
1.8. Методы защиты авторского права на основе цифровых з7 водяных знаков
1.8.1. Технологии маркирования 3 8
1.8.2. Введение в алгоритмы маркирования 41 Выводы 45
2. Определение базисов вейвлет функций оптимальных для сжатия изображений
2.1.Вейвлеты 48
2.1.1. Непрерывные вейвлет преобразования 49
2.1.2. Частотное описание вейвлет преобразований 52
2.1.3. Дискретное вейвлет преобразование 53
2.1.3.1. Матричное описание ДВП 53
2.1.3.2. Описание ДВП посредством блоков фильтров 54
2.1.4. Пакеты вейвлетов 55
2.1.5. Целочисленные вейвлет преобразования 57
2.1.5.1. Целочисленное вычисление вейвлет преобразования 58 (2Д)
2.1.5.2. Вейвлет преобразование лэйзи 58
2.1.5.3. Целочисленное вычисление вейвлет преобразования „ (1,3)
2.1.5.4. Целочисленное вычисление вейвлет преобразования gQ (2,6)
2.1.5.5. Целочисленное вычисление вейвлет преобразования (5,3)
2.2. Определение целочисленного вейвлет преобразования оптимального для сжатия изображений
Выводы 68
3. Развитие методов сжатия изображений на основе вейвлет преобразований
3.1. Используемые обратимые дискретные ортогональные преобразования
3.2. Квантование вейвлет коэффициентов 72
3.3. Развитие методов обхода плоскости вейвлет коэффициентов 73
3.3.1. Древовидный обход вейвлет коэффициентов 73
3.3.2. Псевдо ZigZag сканирование плоскости вейвлет 74 коэффициентов
3.4. Методы сжатия изображений на основе вейвлет преобразований ''
3.4.1. Метод нульдерева 79
3.4.2. Использование кодовой книги для кодирования вейвлет коэффициентов
3.4.3. Метод шаблонно-блочного кодирования 83
3.4.4. Методы кодирования вейвлет коэффициентов, упорядоченных в ZigZag порядке
3.4.4.1. Адаптивное кодирование 86
3.4.4.3. Разряди о срезовый алгоритм кодирования 88
3.4.5. Метод сжатия на основе выделения локальных однородных областей
3.4.6. Разрядное кодирование вейвлет деревьев 97
3.5. Вычислительная сложность алгоритмов сжатия изображений на основе вейвлет преобразования
Выводы 108
4. Внедрение технологии цифрового маркирования в методы сжатия изображений
4.1. Маркирование компонент детализации 110
4.2. Технология слияния логотипа с маркируемым изображением * ^
4.3. Модифицированный метод маркирования Corvi 116
4.4. Исследование устойчивости методов маркирования изображений к алгоритмам цифровой обработки сигнала
Выводы 126
Заключение 127
Литература 129
- Оценка качества восстановленного изображения
- Описание ДВП посредством блоков фильтров
- Квантование вейвлет коэффициентов
- Разрядное кодирование вейвлет деревьев
Введение к работе
Актуальность проблемы. С прогрессом средств вычислительной техники и широким распространением мультимедиа контента всё большая часть информации в вычислительных системах представляется в виде цифровых изображений. Поэтому проблема улучшения алгоритмов сжатия изображений достаточно актуальна. Сжатие изображений важно как для увеличения скорости передачи по сети, так и для эффективного хранения. С другой стороны, широкое использование цифровых изображений приводит к необходимости разработки средств их идентификации и защиты авторских прав. На сегодняшний день существует большое число методов цифрового маркирования изображений, решающих эту задачу. Однако, большинство методов не совместимы с методами сжатия изображений.
Для уменьшения объема графических данных используют большое число алгоритмов сжатия, к которым предъявляется много жёстких требований, как по объёму сжатого файла, качеству восстановленного изображения, так и по ресурсоёмкости самого алгоритма сжатия. К тому же из-за широкого развития сетевых технологий важно, чтобы методы сжатия позволяли постепенно «прорисовывать» изображение в процессе закачки из сети.
Решение проблемы сжатия изображения использовало достижения и стимулировало развитие многих областей техники и науки.
Выявление структуры данных - ключевой аспект эффективного преобразования данных. Среди существующих алгоритмов сжатия можно выделить спектральные методы сжатия, фрактальные методы сжатия и методы сжатия на основе аппроксимаций.
Помимо JPEG, MPEG к спектральным методам сжатия относятся методы, основанные на вейвлет преобразовании. Данные вейвлет преобразования могут быть представлены в виде поддерева, которое может быть эффективно закодировано.
Возможен так же смешанный фрактал ьно-вейвлетовый метод кодирования изображения, в котором вейвлет сжатию подвергаются однородные объекты, выделяемые на исходном изображении.
Однако существующие методы имеют следующие недостатки: невысокий коэффициент сжатия и, как правило, отсутствие механизмов защиты авторских прав в сохранённом изображении, а так же отсутствие возможности «постепенной» загрузки сжатого изображения из сети.
В связи с этим представляется актуальной задача разработки новых алгоритмов сжатия изображений с большим коэффициентом сжатия и включающих в себя механизмы защиты авторского права.
Целью настоящей работы является совершенствование существующих и разработка новых методов сжатия цифровых изображений на основе дискретного ортогонального вейвлет преобразования, выработка рекомендаций по применению реализованных методов для решения различных практических задач, а также разработка методов цифрового маркирования изображений для их совмещения с разработанными методами сжатия изображений,
Задачами исследования являются:
Совершенствование алгоритмов сжатия изображений на основе дискретного
ортогонального вейвлет преобразования, а именно:
определение оптимального дискретного ортогонального вейвлет преобразования различных базисов, например Хаара, базис (5,3);
определение оптимальных способов сканирования матрицы вейвлет коэффициентов;
разработка методов нахождения значимых вейвлет коэффициентов;
разработка алгоритма сжатия изображений на основе выделения локальных
однородных областей (фрактально-вейвлетовый метод кодирования
изображения);
разработка и исследование алгоритмов добавления идентификационной
информации в сжимаемое изображение; построение алгоритма цифрового
маркирования изображений, совместимого с методами сжатия изображения
на основе вейвлет преобразования.
Методы исследований основаны на теории спектральной обработки сигналов, теории информации и статистическом анализе данных.
Научная новизна работы заключается в следующем:
разработаны методы кодирования вейвлет коэффициентов на основе словарного и разрядно-срезового алгоритмов, которые при соизмеримых с существующими методами коэффициентах сжатия обладают меньшей трудоёмкостью;
усовершенствован метод сегментации изображения, основанный на введении дополнительных ограничений на форму области при выделении локальных однородных областей, выборе одной, а не двух стартовых точек и адаптивного поиска порогов яркостей области;
разработан метод сжатия изображения на основе кодирования локальных однородных областей с использованием дискретных ортогональных вейвлет преобразований;
разработан метод цифрового маркирования изображений, совместимый с алгоритмами сжатия изображений на основе вейвлет преобразований, и обладающий высокой устойчивостью маркерного знака к алгоритмам цифровой обработки сигнала.
Основные положения, выносимые на защиту: 1. Результаты исследования по выбору оптимального дискретного ортогонального вейвлет преобразования для сжатия изображений, исходя из
соотношения вычислительной сложности преобразования к размеру файла данных после вторичного сжатия.
Метод сжатия изображений на основе словарного кодирования вейвлет коэффициентов.
Метод сжатия изображения на основе кодирования локальных однородных областей.
Метод сжатия изображения на основе разрядно-срезового кодирования вейвлет коэффициентов.
Методы цифрового маркирования, совместимые с алгоритмами сжатия изображений на основе дискретных ортогональных вейвлет преобразований.
Апробация работы. Результаты выполненных исследований докладывались на XXXIV научно-технической конференции студентов, аспирантов и молодых учёных: академии гражданской авиации; XXXII научно-технической конференции профессорско-преподавательского состава ИТМО;
XXXIV научно-технической конференции студентов, аспирантов и молодых
учёных, 2002г.: Министерства транспорта российской федерации
государственной службы гражданской авиации академии гражданской авиации;
XXXV научно-технической конференций студентов, аспирантов и молодых
учёных, 2003 г.: Министерства транспорта российской федерации
государственной службы гражданской авиации академии гражданской авиации;
Санкт-Петербургского государственного института точной механики и оптики
- «Научно-технический вестник», 2003г.; XXXIV научной и учёбно-
методической конференции СПбГУИТМО, 2005 г.
По теме диссертации опубликовано 8 работ (из них 3 работы без соавторов), в том числе 4 статьи.
Структура и объем диссертации.
Диссертация состоит из введения, четырёх глав, заключения, списка литературы и трёх приложений. Рукопись содержит 157 страниц текста, 59 рисунков и 15 таблиц. Список литературы включает 82 наименований.
Оценка качества восстановленного изображения
Проблема защиты авторского права на мультимедиа информацию существовала всегда, но стала особенно актуальной с развитием средств вычислительной техники и средств телекоммуникации. В настоящее время существует возможность создавать большое число копий цифровых аудио- и видеоданных без потери их качества, а также беспрепятственно их распространять по сети. Данное обстоятельство привело к разработке систем защиты авторского права и систем защиты от копирования мультимедиа информации. Одним из направлений данной деятельности является цифровое маркирование данных [35,41,42,48,54,67,68,71,77,80].
Для защиты данных можно использовать хорошо зарекомендовавшие себя алгоритмы шифрования, но для мультимедиа данных это не лучший выбор. Зашифрованную мультимедиа информацию невозможно ни увидеть, ни услышать без расшифровки. Для данной категории информации хотелось бы иметь такие средства, которые позволяли бы «подписывать» данные без потери информативности, т.е. заметного ухудшения качества изображения или звука. В этом случае «подписанный» объект можно слушать или просматривать, но одновременно можно в любой момент доказать, кому он принадлежит.
При этом особенно важным является устойчивость цифровой подписи. Сжатие мультимедийных данных, стандартные методы цифровой обработки сигналов: фильтрации, масштабирование, повороты - всё это оказывает влияние на цифровую подпись.
Этим искажениям в той или иной степени противостоят методы цифрового маркирования мультимедиа информации.
Методы цифрового маркирования похожи на античную методику сокрытия информации, известную как стеганография. Эти методы могут применяться к данным, имеющим избыточность, и скрывают в них информацию о владельце или иные данные.
Подпись, скрываемую в данных, называют «цифровым водяным знаком» - ЦВЗ. ЦВЗ может иметь различную природу: логотип компании, случайная последовательность чисел или начальные параметры для ее генерации.
Цель маркирования - определение:
владельца объекта маркирования;
изменений, произведённых над объектом маркирования;
легальности объекта маркирования (права его использования)
В работе сделан акцент на методы маркирования изображений, которые могли бы быть совмещены с методами сжатия изображения, которые были представлены выше.
Описание ДВП посредством блоков фильтров
Ранее рассматривалось субполосное преобразование, как фильтрация с последующим прореживанием в два раза. В данном случае имеется два фильтра й„ и g„, т.е. банк фильтров - двухполосный и может быть изображен, как показано на рис.2.1. Фильтры F и Е означают фильтрацию фильтрами h_„ и g_„, соответственно. В нижней ветви схемы выполняется низкочастотная фильтрация. В результате получается некоторая аппроксимация сигнала, лишенная деталей низкочастотная (НЧ) субполоса. В верхней части схемы выделяется высокочастотная (ВЧ) субполоса. Отметим, что при обработке сигналов константа 2,/2 всегда выносится из банка фильтров и сигнал домножается на 2.
Итак, схема (рис.2.1) делит сигнал уровня j = Q на два сигнала уровня у = 1. Далее, вейвлет преобразование получается путем рекурсивного применения данной схемы к НЧ части. При осуществлении вейвлет преобразования изображения каждая итерация алгоритма применяется вначале к строкам, затем — к столбцам изображения (строится так называемая пирамида Маллата).
Вейвлет преобразование сигнала выполняется путем его пропускания через каскадное соединение фильтров. При этом каскадирование производится по низкочастотной области. Причина этого в неявном предположении, что эта область содержит больше информации об исходном сигнале. В результате получается «однобокое» дерево (рис. 2.2(a)). Данное предположение оправданно для многих реальных сигналов. В самом деле, оно означает, что сигнал является низкочастотным на большом интервале времени, а высокочастотные составляющие появляются на коротком интервале. Однако для некоторых сигналов это предположение не выполняется.
Метод пакетов вейвлетов основан на определении того, по какой области на данном уровне выгоднее производить каскадирование. Для этого вначале производится каскадирование по обеим субполосам. В результате получается так называемое «полное», «сбалансированное» дерево (рис. 2.2(6)), напоминающее дерево, присущее кратковременному преобразованию Фурье, Далее, на основе введенной функции стоимости определяется наилучший путь по этому дереву (рис. 2.2(B)).
Если исходный блок вейвлет фильтров был ортогональным, то и схема, соответствующая любой конфигурации дерева, будет ортогональной, так как она есть не что иное, как каскадное соединение ортогональных блоков.
Квантование вейвлет коэффициентов
В отличие от JPEG кодирования, при квантовании вейвлет коэффициентов используется однородное квантование. Это значит, что-либо все коэффициенты из всех субполос квантуются одним и тем же коэффициентом квантования, либо для каждой из субполос выбирается свой коэффициент квантования, но для всех частотных коэффициентов данной субполосы он остаётся постоянным. Выбор различных коэффициентов квантования для разных субполос является более предпочтительным, т.к. позволяет мягко регулировать качество восстановленного изображения. Например, для высокочастотных субполос можно выбрать больший коэффициент квантования, а для низкочастотной субполосы установить данный коэффициент меньше, тем самым сохранив больше информации для восстановления изображения.
Следует отметить, что коэффициенты квантования выбираются экспериментально и являются одними из задаваемых параметров для всех рассматриваемых алгоритмов сжатия. 3.3. Развитие методов обхода плоскости вейвлет коэффициентов
Для качественного сжатия вейвлет коэффициентов необходим учет взаимосвязей между коэффициентами из различных субполос вейвлет разложения. В высокочастотных субполосах имеются, обычно, большие области с нулевой или малой энергией. Области с высокой энергией повторяют от субполосы к субполосе свои очертания и местоположение. Медленно изменяющиеся гладкие области исходного изображения хорошо описывают низкочастотные (НЧ) вейвлет базисы, что приводит к «упаковке» энергии в малом числе коэффициентов НЧ области.
Наиболее очевидным в данном случае методом обхода вейвлет коэффициентов является древовидный обход.
Впервые идея нульдерева была предложена А.Льюисом и Г.Ноулесом [75]. В их алгоритме применялась древовидная структура данных для описания вейвлет коэффициентов (рис. 3.3). Корневой узел дерева представляет коэффициент масштабирующей функции в самой НЧ области и имеет три отпрыска. Узлы дерева соответствуют вейвлет коэффициентам масштаба, равного их высоте в дереве. Каждый из узлов имеет четыре отпрыска, соответствующих вейвлет коэффициентам следующего уровня и того же пространственного расположения. Низом дерева являются листьевые узлы, не имеющие отпрысков.
Таким образом, для каждого коэффициента из субполосы LL2, получается 3 вектора (ветки дерева), содержащие по 6 коэффициентов каждый:
В дальнейшем выбранные коэффициенты кодируются на основе метода нуль-дерева.
Данный способ обхода вейвлет коэффициентов позволяет установить взаимосвязь только между коэффициентами одной из ветвей вейвлет дерева. Поскольку вейвлет коэффициенты сохраняют свой масштаб от уровня к уровню преобразования, то способ обхода вейвлет коэффициентов, связывающий коэффициенты всех ветвей корневого узла дерева, может оказаться предпочтительней. Одним из таких способов обхода плоскости вейвлет коэффициентов является псевдо ZigZag обход.
3.3.2. Псевдо ZigZag сканирование плоскости вейвлет коэффициентов
Для того чтобы связать вейвлет коэффициенты всех ветвей корневого узла дерева, можно попытаться обойти их в ZigZag порядке. Поскольку при вейвлет преобразовании сохраняется масштаб вейвлет коэффициентов от уровня к уровню преобразования, то при таком способе обхода будет наблюдаться некоторая упорядоченность коэффициентов преобразования. Данный способ обхода не приведёт к строгой упорядоченности коэффициентов, но при этом будет сохраняться общая тенденция к убыванию значений коэффициентов.
Разрядное кодирование вейвлет деревьев
Данный алгоритм представляет собой синтез 2-х методов кодирования вейвлет коэффициентов: метода нульдерева и разрядно срезового алгоритма кодирования.
В алгоритме кодирования используются 4 параметра кодирования, отвечающие за качество и степень сжатия изображения:
Thr - порог для определения «ветвей», являющихся нуль деревом,
L2 — число бит, используемое для кодирования коэффициентов из субполосы LL2,
L1 - число бит, используемое для кодирования коэффициентов из субполос (HL2, LH2, НН2),
L0 - число бит, используемое для кодирования коэффициентов из субполос (HL1, LH1, НН1). После двухуровневого вейвлет преобразования и квантования вейвлет коэффициентов для каждого коэффициента из субполосы LL2 динамически формируется вектор Vr из значений соответствующих коэффициентов смежных субполос. Вектор Vr максимально может содержать 16 коэффициента (Рис 3.3.)
Алгоритм формирования вектора Vr.
Пусть на начальном этапе вектор Vr состоит из одного элемента: F 2 (рис.3), и длина этого вектора /v=l. Если данный коэффициент значимый, т.е. F,":I Thr, то его потомки F2, F"?, F""2, также значимы, и они помещаются в вектор Vr, таким образом, его длина становиться h равной 4. Если бы значение коэффициента F 2 оказалось меньше либо равным порогу, то потомки данного коэффициента считались бы не значимыми, и формирование вектора Vr было бы прекращено. Затем, аналогично коэффициенту F f, рассматриваются значения коэффициенты F jF"",F2. Например, если \F"y2\ Thr, то потомки данного коэффициента F" 1.y,F" 1.y,F" .y+l,F" li2.y являются значимыми и помещаются в вектор Vr . Если нет, то рассматривается следующий коэффициент F y2 и его потомки, и так далее. Таким образом, от одного корневого коэффициента F 2, рассматривая все его потомки и отсевая незначимые коэффициенты на основе правила нуль дерева динамически формируется вектор Vr, длина которого может варьироваться от 1 до 16. Полученные коэффициенты затем кодируются с помощью разрядно срезового алгоритма. В зависимости от группы, к которой принадлежит коэффициент, от него оставляют L2, L1 или L0 значимых бит. Формирование новых кодов возможно при горизонтальном или вертикальном обходе полученных коэффициентов.
При горизонтальном обходе код формируется сначала из 0-х бит выбранных коэффициентов, затем из 1-х, 2-х и т.д.
При вертикальном обходе код формируется сначала из значимых бит коэффициентов группы А, затем из бит коэффициентов группы В и группы С.
Второй метод кодирования позволяет реализовать удобную возможность постепенного проявления изображения при его восстановлении, что особенно удобно при загрузке изображения из сети.
Поскольку при вейвлет разложении существует низкочастотная составляющая и компоненты детализации, то если на сторону клиента сначала передать закодированную низкочастотную составляющую LL2, распаковывав её, можно получить очень грубое представление исходного изображения. Затем клиент получает среднечастотные детализирующие составляющие, и улучшает качество принятого изображения и наконец, получив последние высокочастотные закодированные детализирующие составляющие, может полностью восстановить изображение.
Такое кодирование удобно для загрузки больших изображений через сеть, например, цифровые фотографии или большие детальные карты.
