Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Увеличение компрессии изображений в алгоритмах с фурье–преобразованиями Голованов Роман Вячеславович

Увеличение компрессии изображений в алгоритмах с фурье–преобразованиями
<
Увеличение компрессии изображений в алгоритмах с фурье–преобразованиями Увеличение компрессии изображений в алгоритмах с фурье–преобразованиями Увеличение компрессии изображений в алгоритмах с фурье–преобразованиями Увеличение компрессии изображений в алгоритмах с фурье–преобразованиями Увеличение компрессии изображений в алгоритмах с фурье–преобразованиями Увеличение компрессии изображений в алгоритмах с фурье–преобразованиями Увеличение компрессии изображений в алгоритмах с фурье–преобразованиями Увеличение компрессии изображений в алгоритмах с фурье–преобразованиями Увеличение компрессии изображений в алгоритмах с фурье–преобразованиями Увеличение компрессии изображений в алгоритмах с фурье–преобразованиями Увеличение компрессии изображений в алгоритмах с фурье–преобразованиями Увеличение компрессии изображений в алгоритмах с фурье–преобразованиями
>

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

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Голованов Роман Вячеславович. Увеличение компрессии изображений в алгоритмах с фурье–преобразованиями: диссертация ... кандидата физико-математических наук: 05.13.11 / Голованов Роман Вячеславович;[Место защиты: Национальный исследовательский университет «МИЭТ»].- Москва, 2014.- 134 с.

Содержание к диссертации

Введение

1 Критерий оценки качества изображения 9

1.1 Проблема 9

1.2 Обзор существующих критериев 12

1.2.1. Пиковое отношение сигнал/шум (12). 1.2.2. Современные критерии оценки качества изображения (14)

1.3 Разработка новых математических критериев 16

1.3.1. Критерий сглаженных градиентов SGC (16).

1.3.2. Критерий сглаженной адаптации SAC (18). 1.3.3. Перспективы (19)

1.4 Тестирование критериев 21

1.4.1. Базы изображений (21).

1.4.2. Сравниваемые критерии (21).

1.4.3. Общепринятая методика тестирования (21).

1.4.4. Ранжирование по среднему месту (23).

1.4.5. Ранжирование по среднему PLCC (24).

1.4.6. Выводы (25)

1.5 Результаты главы 26

2 Базы тестовых изображений 27

2.1 Введение 27

2.1.1. Создание базы (27). 2.1.2. Рекомендации (28)

2.2 Обзор существующих баз 29

2.2.1. База TID2008 (31). 2.2.2. База LIVE (34)

2.3 Объединение баз 35

2.3.1. Экспертные и критериальные оценки (35). 2.3.2. Наглядная работа критерия качества (43). 2.3.3. Регрессии (48). 2.3.4. Объединение баз (50)

2.4 Тестирование критериев 52

2.5 Результаты тестирования 53

2.5.1. Сравнение по отношению стандартов (54). 2.5.2. Сравнение по коэффициентам корреляции (54). 2.5.3. Условные субъективные оценки (54)

2.6 Результаты главы 55

3 Улучшения кодека JPEG 56

3.1 Выбор направления 56

3.2 Стандартный кодек JPEG 57

3.2.1. Описание алгоритма (57).

3.2.2. Реализация программы (61)

3.3 Матрица квантования 61

3.3.1. Стандартный размер (61).

3.3.2. Произвольный размер (62).

3.3.3. Преимущество (63)

3.4 Алгоритм BigJPEG 64

3.4.1. Обоснование алгоритма (64).

3.4.2. Программная реализация (65).

3.4.3. Методика сравнения (66).

3.4.4. Анализ результатов (66).

3.4.5. Демонстрация на изображениях (71).

3.4.6. Выводы (86)

3.5 Алгоритм JPEG-IT 86

3.5.1. Описание (86).

3.5.2. Методика сравнения (87).

3.5.3. Анализ результатов (88).

3.5.4. Демонстрация на изображениях (90).

3.5.5. Выводы (95)

3.6 Результаты главы 95

4 Фурье-аппроксимация гладких непериодических функций 96

4.1 Проблема 96

4.2 Сходимость рядов Фурье 97

4.3 Одномерный случай 100

4.3.1. Эффект Гиббса (100).

4.3.2. Чётное продолжение (100).

4.3.3. Нечётное продолжение (100).

4.3.4. Дальнейшее повышение гладкости (101).

4.3.5. Простое продолжение высокой гладкости (101)

4.4 Двумерный случай 106

4.4.1. Классическое продолжение (107).

4.4.2. Чётное продолжение (108).

4.4.3. Нечётное продолжение (108)

4.5 Усечение ряда Фурье 109

4.5.1. Усечение по квадрату (109).

4.5.2. Усечение по треугольнику (110).

4.5.3. Оптимальное усечение (110).

4.5.4. Построение гиперболического усечения (112)

4.6 Нечётное продолжение в сжатии изображений 115

4.6.1. Чётное продолжение (115).

4.6.2. Простое нечётное продолжение (116).

4.6.3. Устранение блочного эффекта (117).

4.6.4. Нечётное продолжение со сглаживанием (117).

4.6.5. Результаты численных расчётов (118)

4.7 Обобщения 119

4.7.1. Сеточная функция (119).

4.7.2. Неравномерные сетки (119).

4.7.3. Гистограммы (119)

4.8 Результаты главы 120

Заключение 121

Список рисунков 127

Список таблиц

Введение к работе

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

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

Предметная область. Исследование ведётся в нескольких смежных областях, соответствующих паспорту специальности 05.13.11:

1. Моделирование, разработка методик и алгоритмов для цифровой об
работки изображений.

2. Оценка качества работы алгоритмов сжатия изображений.
Предметами исследования являются алгоритмы дискретного преоб
разования Фурье для сжатия изображений с потерями и критерии оценки
качества получаемого изображения посредством таких алгоритмов.

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

Для достижения цели были поставлены и решены следующие научно-технические задачи:

  1. Разработка алгоритма адаптивного кодирования в кодеках на основе дискретного косинусного преобразования (ДКП).

  2. Обобщение алгоритмов сжатия изображений на основе ДКП на блоки произвольного размера.

  1. Построение математического критерия оценки качества искажённого изображения, соответствующего человеческому восприятию.

  2. Повышение достоверности методов тестирования алгоритмов на базах изображений с различными видами искажений.

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

В ходе исследования производилось численное моделирование на компьютере с использованием написанных и доработанных приложений на языках C и C++, а также пакета MATLAB.

Эксперимент состоял в сравнении результатов теоретических расчётов с экспертными оценками, взятыми из современных баз тестовых изображений.

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

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

Личный вклад автора. В основу диссертации легли результаты исследований, выполненных лично автором. Личный вклад автора состоял также в непосредственном участии в получении исходных данных, в аппробации результатов исследований, в обработке и интерпретации полученных данных, в подготовке основных публикаций по выполненной работе.

Научная новизна. В работе предлагаются следующие новые алгоритмы, методы и программы.

  1. Предложен алгоритм BigJPEG, обобщающий кодек JPEG на блоки большего размера, и его программная реализация.

  2. Предложена экономичная схема кодирования JPEG-IT для базового кодека JPEG и её программная реализация.

  3. Создан критерий оценки качества изображения, построенный на основе нормы Соболева.

  4. Предложен метод объединения баз тестовых изображений, построенных на основе разнотипных экспертных оценок.

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

6. Проведено сравнение алгоритмов сжатия изображений на основе лучшего по достоверности современного критерия оценки качества изображения.

Практическая значимость:

  1. Разработанные кодеки BigJPEG и JPEG-IT, повышающие сжатие изображений от 9 до 20%, целесообразно использовать для хранения и передачи изображений в условиях технических ограничений аппаратуры.

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

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

Основные положения, выносимые на защиту:

  1. Разработанные кодеки BigJPEG и JPEG-IT повышают сжатие изображений от 9 до 20% при том же качестве по сравнению с базовым кодеком JPEG.

  2. Предложенная методика сравнения критериев оценки качества изображений на объединённой базе позволяет достоверно ранжировать критерии качества и оценивать их доверительную вероятность.

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

Апробация. Основные результаты работы докладывались на 15-й Международной конференции «Цифровая обработка сигналов и её применение» (Москва, 2013 г.), на 19-ой, 20-ой и 21-ой Всероссийских межвузовских научно-технических конференциях студентов и аспирантов «Микроэлектроника и информатика» (Москва, МИЭТ, 2012, 2013 и 2014 гг.), на научном семинаре ЗАО «ЭЛВИС-НеоТек» (Москва, Зеленоград, 2013 г.), на научном семинаре ФТИАН (Москва, 2014 г.).

Публикации. По теме диссертации опубликовано 9 работ, в том числе 5 статей в журналах, рекомендованных ВАК: «Доклады Российской академии наук» — 2, «Цифровая обработка сигналов» — 1 и «Математическое моделирование» — 2. Получено 2 свидетельства о государственной регистрации программы для ЭВМ.

Структура и объём диссертации. Диссертация состоит из введения и четырёх глав, изложена на 134 страницах, содержит 101 рисунок и 16 таблиц. Список литературы насчитывает 94 источника.

Разработка новых математических критериев

Пример 1.1.2. В военной технике активно ведутся разработки беспилотных летательных аппаратов (БПЛА). Их используют при аэрофотосъёмке местности. Полученную серию снимков объединяют, получая тем самым карту местности. Типовой проблемой в таком случае является проявление артефактов на границах снимков. Для устранения подобных дефектов разрабатывают специальные алгоритмы, которые позволяют производить аккуратную «сшивку» кадров или делать постобработку «сшитого» изображения [4] (см. пример на Рис. 1.2). От качества изображения может зависеть результат разведывательной операции. В условиях военных действий это является очень важным.

Пример 1.1.3. В обычных условиях БПЛА может ориентироваться в воздухе по сигналам с датчиков спутниковой навигационной системы ГЛОНАСС или GPS и автономно следовать заданному маршруту. Управляющие сигналы также могут передаваться по каналу радиосвязи из командного центра. В боевых условиях противник может использовать средства радиопомех, так что БПЛА будет дезориентирован, а связь с ним потеряна.

Поэтому другая актуальная задача — это обеспечение автономного перемещения БПЛА. Летательный аппарат должен уметь следовать маршруту по опорным точкам на местности. Опорные точки — это характерные объекты местности, такие как здания, дороги, мосты и естественный ландшафт. Их можно использовать для определения координат и параметров движения [5]. БПЛА делает снимок, далее алгоритм обработки изображения должен выделить опорные участки и вычислить координаты и параметры движения (см. пример на Рис. 1.3). Каждый раз запускать БПЛА и проверять работу Рисунок 1.2 — Пример создания бесшовного изображения по снимкам с БПЛА алгоритмов — слишком дорого. Поэтому такие алгоритмы проще верифицировать специально построенными математическими моделями, а критерий IQA должен использоваться для определения приемлемого сочетания качество-сжатие. Это позволит экономить ресурсы самого БПЛА и упростит процедуру тестирования алгоритмов. Рисунок 1.3 — Пример работы алгоритма поиска опорных точек по снимкам с БПЛА

Однако построить критерий IQA оказывается не просто. Этому вопросу посвящена обширная литература [6–10] и др. Обычно исследователи исходят из некоторых естественных идей и пишут достаточно простые критерии. На практике они не очень хорошо совпадают с экспертными оценками. Их начинают усложнять, причем довольно эклектичным образом и при этом вводят ряд свободных (подгоночных) параметров. Итоговые формулы зачастую оказываются весьма громоздкими. Получаются искусственные конструкции, хорошо работающие на той базе экспертных оценок, по которой подбирались их свободные параметры. На других базах результаты могут быть заметно хуже. Для тестирования критериев IQA созданы различные базы тестовых изображений [11–16]. Обычно одному оригиналу соответствует несколько искажённых изображений, для которых известна экспертная оценка. На таких базах производится тестирование критериев и делаются выводы о достоверности получаемых результатов.

Разработка критериев IQA (image quality assesment — оценка качества изображения) — это относительно новая область исследований. Активные работы в данном направлении ведутся с начала 2000-х годов [6, 9, 10, 17, 18]. Поскольку в большинстве случаев человек является конечным пользователем алгоритмов обработки и передачи изображений, то самый надёжный способ оценки качества изображений — это субъективная оценка. Действительно, средняя экспертная оценка (MOS — mean opinion score) давно признана лучшим способом измерения качества изображения. Однако сбор экспертных оценок , как правило, занимает много времени и дорог.

Задача разработки критерия IQA заключается в разработке математической модели, которая способна предсказывать воспринимаемое качество изображения точно и без настроек на конкретную ситуацию. Алгоритм должен прогнозировать то качество изображения, которое в среднем сообщает эксперт. Успешное развитие таких критериев оценки имеет большую перспективу во многих прикладных задачах. Например, в автоматизированных системах передачи изображений или видео. Система автоматически подбирает приемлемое качество в зависимости от загруженности линий связи. Другая область — это тестирование алгоритмов обработки изображений. К ним относятся алгоритмы сжатия, шумоподавления, повышения качества, стеганографии и другие.

Пиковое отношение сигнал/шум. Самый простой и, к сожалению, всё ещё широко распространённый критерий IQA — среднее квадратичное отклонение (СКО) или mean opinion score (MSE), которое определяется по формуле 12 = ( -), (1.1) =1 где и — яркости соответствующих пикселей изображения и , — общее число пикселей в изображении. Чаще используют величину пикового отношения сигнал/шум (ПОСШ) или peak signal-noise ratio (PSNR), основанный на MSE 2 =10log , (1.2) где — максимальное значение яркости пикселя в данном изображении. Для 8-битного изображения = 255.

Метрики (1.1) и (1.2) вычисляются просто. К тому же MSE имеет понятное физическое определение — это энергия ошибки в сигнале. Тем не менее, MSE и PSNR уже давно критикуют за плохую связь с воспринимаемым качеством изображения. Простой пример из [10] показан на Рис. 1.4. Изображения (a)–(g) имеют одинаковый MSE, тем не менее визуально они сильно отличаются. В то же время изображения (h)–(j) воспринимаются одинаково, хотя значения MSE существенно отличаются.

Обзор существующих баз

К настоящему времени имеется несколько объёмных баз тестовых изображений. Зачастую они сильно отличаются друг от друга, по структуре, методам сбора экспертных оценок, типам искажений, набору эталонных искажений и другим характеристикам. Поэтому, проводя тестирование критериев на разных базах, можно получать разные результаты. В отдельных случаях результаты могут оказаться сильно разными. Такое встречается во многих зарубежных работах. Исследователи проводят тестирование своего критерия качества и сторонних на нескольких базах и получают результаты, которые нельзя однозначно интерпретировать.

Проблема сопоставления результатов тестирования критериев качества между базами нами уже поднималась в [30]. В Главе 1 описаны несколько возможных решений, предложенных нами. Это очень простые решения, которые дают почти одинаковые результаты. Однако эти методы не учитывают особенностей построения самих баз тестовых изображений, что влияет на достоверность выводов.

В данной главе предлагается идея объединения нескольких баз тестовых изображений. Методика объединения подробно описана и продемонстрирована на примере объединения двух наиболее представительных баз тестовых изображений TID2008 [11] и LIVE [12]. На объединённой базе мы провели тестирование наиболее распространённых критериев оценки качества, в том числе критерии предложенные в данной работе.

Рекомендации. Нами был проделан эксперимент по созданию своей базы тестовых изображений. Был сформирован набор из 4-х оригинальных изображений. Для каждого оригинала предлагалось 7 искажений разного рода. В качестве экспертов привлекалась группа студентов, которая должна была оценивать качество тестовых искажённых изображений.

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

Экспертная оценка. Разработка правил сбора экспертных оценок — важный этап работы. Для экспертов разрабатывается специальная инструкция. От выбора способов оценивания, подготовки шкалы оценивания напрямую зависит конечный результат. В итоге по экспертным оценкам необходимо получить количественную характеристику восприятия качества искажённого изображения.

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

При проведении качественного оценивания, эксперт должен ранжировать несколько искажённых изображений по ухудшению качества. Такое ранжирование обычно менее субъективно. Разные эксперты ранжируют изображения почти одинаково (если интенсивности искажения не слишком близки). Но это ранжирование нужно переводить в количественные оценки. Процедура такого перевода математически не определена, что вносит свою долю субъективизма.

Поэтому априори нельзя сказать какой из двух способов лучше. Многое зависит от чёткости инструкции и личного контакта исследователя с экспертами.

Можно проводить смешанный опрос. В таком случае эксперты должны оценить каждое изображение в баллах и параллельно проводить ранжирование. Это наиболее содержательный эксперимент. К сожалению базы с такими экспертными оценками нам не встречались в научной литературе. Шкала оценок. Для количественного оценивания разумно использовать 10-ти бальную шкалу. При разработке шкалы очень важно правильно сопоставить баллы с качественным восприятием. Каждый бал должен описываться словом или фразой и должен иметь понятные словесные пояснения. В Табл. 2.1 приведена предлагаемая шкала. Таблица 2.1 — Шкала оценивания искажённых изображений по качеству Балл Школьный балл Словесное описание качества Пояснение 10 5+ Идеальное Нет отличий 9 5 Отличное Отличий почти не видно 8 5- Отличное с оговоркой Отличия заметны 7 4+ Почти отличное Есть дефекты, совершенно не влияющие на содержимое фотографии 6 4 Хорошее Есть очевидные дефекты, не значительно влияющие на содержимое фотографии 5 4- Приемлемое Есть дефекты, искажающие отдельные (мелкие) детали изображения 4 3 удовлетворительное Почти не видно мелких деталей 3 3- Почти плохое Заметно искажены крупные детали 2 2 Плохое (неудовл.) Содержимое фотографии просматривается с трудом 1 1 Ужасное Содержимое фотографии искажено полностью

Эта шкала соответствует школьной шкале оценивания качества знаний, принятой в России. Школьный учитель формально работает с пятибалльной шкалой от 1 до 5. Фактически он использует десятибалльную шкалу, ставя плюсы и минусы, см. Табл. 2.1. Промежуточные баллы позволяют учителю действовать более гибко.

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

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

В настоящее время известно много сторонних общедоступных баз тестовых изображений, см. например [33]. Распространёнными являются шесть баз тестовых изобра-29 жений. Они приведены в Табл. 2.2. Видно, что все они отличаются по характеристикам. К сожалению, для некоторых баз не все характеристики удалось привести, так как они отсутствуют в источниках. Таблица 2.2 — Характеристики наиболее известных баз тестовых изображений Название TID2008 LIVE Cornell A57 IVC Toyama MICT CSIQ Работа [11] [12] [16] [14] [15] [13] Год 2008 2006 2007 2006 2008 2010 Страна Украина, США США США Китай США Финляндия, Италия Объём 1700 779 54 235 168 870 Цвет изображений цветные цветные чёрно-белые цветные, чёрно-белые цветные цветные Оригиналы 25 29 3 10 14 30 Типы искажений 17 5 6 4 2 6 Число экспертов 838 138 — 15 16 35 Метод оценки парное сравнение по шкале — — по шкале ранжирование Шкала MOS 0..9 1..100 0..1 1..5 1..5 0..1 Дисперсия MOS 0,63 2,33 — — 0,69 0,084 — год определён по дате последнего изменения файлов в архиве базы

Все перечисленные базы — зарубежные. Наибольшее число баз представлено исследователями из США, что соответствует подавляющему большинству работ среди разработчиков критериев оценки качества (см. Табл. 1.1). Отечественные разработки мы не встречали.

Самая объёмная база — TID2008, далее идут базы LIVE и CSIQ. Они содержат почти в два раза меньше тестовых изображений. Другие базы ещё существенно меньше по объёму. Для создания больших баз использовалось 25–30 эталонных изображений, в то время как другие содержали от 3 до 14 эталонов. Многообразие эталонных изображения позволяет проводить более достоверное тестирование. Почти все базы содержат цветные изображения, но есть и исключения. В базе Cornell-A57 все изображения чёрно-белые, а в базе IVC есть как чёрно-белые так и цветные.

Важной характеристикой базы является количество типов искажений. Больше всего искажений содержится в базе TID2008, а в остальных существенно меньше (почти в 3 раза). Однако во всех базах встречаются такие виды искажений, как сжатие кодеками JPEG или JPEG2000, шумовые искажения, размытие, сдвиг средней яркости и изменение контраста.

Методика построения баз также сильно отличается. Во-первых, в экспертном оценивании привлекалось разное число респондентов. Во-вторых, методики сравнения были принципиально разными. Количественное оценивание делалось в базах LIVE, Toyama-MICT. Качественное сравнение делалось в базах TID2008 и CSIQ. Причём в каждой из баз качественное оценивание делалось по разным принципам. В TID2008 проводилось парное сравнение искажённых изображений, а в базе CSIQ эксперты должны были упорядочить массив изображений по качеству. Во всех случаях эксперты оценивали изображения на экранах мониторов, что также влияет на результаты оценивания.

Описание алгоритма (57).

Результаты сравнения по разным методикам представлены в Табл. 2.7. Мы проделали тестирование на объединённой базе для 19 наиболее распространённых критериев, перечисленных в Табл. 1.1. Расчёты проводились, как на полной базе, так и на усечённой. Стандартные отклонения критериев качества рассчитывались относительно линейных регрессий. Они используют шкалу экспертных оценок и выражаются в баллах. В таблице приведены отношения стандарта критерия к стандарту базы /, а также различные коэффициенты корреляции. После каждого отношения или коэффициента курсивом указано ранжирование критерия по этой величине; первые три места выделены жирным шрифтом.

Сравнение по отношению стандартов. Рассмотрим случай усечённой базы. По количественным значениям / рассмотренные критерии можно разделить на 3 груп пы. В первой содержится лишь один лидирующий критерий VIF с отношением / 3.52. Далее с заметным отрывом идёт очень плотная группа из 9 критериев с отноше ниями от 4.05 до 4.53. В неё также входит наш критерий SGC, близкий по значениям к лидерам группы. Дальше с заметным отрывом следует третья группа с отношениями от 5.06 до 7.73.

Соотношение / позволяет не только провести ранжирование, но и оценить статистическую достоверность критериев. Очевидно, чем ближе соотношение к нулю, тем надёжнее критерий. Однако даже у лучшего критерия VIF это отношение соответствует доверительной вероятности 0.0004! Для остальных критериев доверительные вероятности заметно меньше. Это показывает, что все критерии ещё очень далеки от адекватной передачи человеческого восприятия искажённого изображения.

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

Сравнение по коэффициентам корреляции. Видно, что ранжирование по раз ным коэффициентам корреляции оказывается неодинаковым. При этом упорядочивание по коэффициенту парной корреляции Пирсона дало такой же результат что и ранжиро вание по /. Нельзя утверждать, что такое совпадение будет всегда. Однако можно сделать вывод, что ранжирование по PLCC является достаточно хорошим эвристическим методом. Однако, в отличие от сравнения по стандартам, это не позволяет оценить стати стическую достоверность выводов. Упорядочивание по SRCC и KRCC для многих критериев даёт ранжирование примерно сходное с /. Однако некоторые критерии занимают совсем другие позиции. Тем самым, ранжирование по этим коэффициентам существенно менее надёжно, и мы не рекомендуем их использовать.

Некоторые критерии, например PSNRHA и PSNRHMA, имеют дополнительную специализацию по отдельным типам искажений. Они рассчитаны на работу с искажениями яркости или контрастности, где оказываются лучше других критериев. Поэтому интересно также тестирование критериев на полной объединённой базе. Эти результаты приведены в последних столбцах Табл. 2.7. Все значения заметно хуже, чем в соответствующих колонках усечённой базы, что естественно. Ранжирование критериев меняется. Первое место сохраняет критерий VIF, хотя его отрыв от второго места сокращается. Критерий PSNRHA выходит с третьего места на второе. Критерий PSNRHMA уходит со второго места на четвёртое. Наш критерий SGC поднимается с шестого места на третье. Вдобавок произошла ротация нескольких критериев второй и третьей групп, а граница между ними исчезла.

Можно дополнительно оценить стабильность работы критериев беря сумму мест для усечённой и полной базы в колонках /. Первое место занимает VIF (2 очка), на втором месте PSNRHA (5 очков), на третьем PSNRHMA (6 очков), на четвёртом SGC (9 очков), остальные имеют 15 и более очков. Это показывает, какие критерии следует предпочесть. 2.5.3. Условные субъективные оценки. Для дальнейшей работы нам необходимо опре делить интервалы качества лучшего критерия для условных субъективных оценок. Услов ными субъективными оценками удобно оперировать, когда делаются выводы о результа тах работы какого-либо алгоритма обработки изображений. Проще работать с небольшим числом субъективных оценок, поэтому были выбраны следующие словесные описания качества: «отличное», «хорошее», «удовлетворительное» и «плохое».

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

Сопоставление значений метрик качества IQA и экспертных оценок MOS, сделанные ранее, позволяют для любого математического критерия качества выделить диапазон значений, который относится к той или иной субъективной оценке. Для критерия VIF, показавшего лучшие результаты соответствия человеческому восприятию, мы выделяем следующие диапазоны значений: «отличное» [0.75; 1.00], «хорошее» [0.50 0.75), «удовлетворительное» [0.25; 0.50) и «плохое» [0.00; 0.25).

Эффект Гиббса

Задачам аппроксимации непериодических функций посвящена обширная математическая литература (см. [61–65] и другие). Функции аппроксимируют разложением в ряды, сплайнами, вейвлетами и другими способами. При выборе того или иного способа аппроксимации нужно исходить из требуемой точности. Если необходимо достичь высокой точности, то нужно уметь аккуратно вычислять много членов ряда. Важным фактором также является простота реализации и быстродействие выбранного метода на практике.

Хорошо известны способы аппроксимации с помощью многочленов Чебышева, Ле-жандра, Лагерра, Эрмита и других. Ими удобно пользоваться в тех случаях, когда вычисления относительно простые. При реализации различных способов аппроксимации на практике возникают трудности. Современная вычислительная техника имеет хорошие аппаратные и программные средства для вычисления степенных и тригонометрических функций с высокой точностью. Программы для вычисления специальных функций обычно хорошо работают при малых порядках этих функций (меньше 10). При более высоких порядках обычно начинают сказываться ошибки округления, которые уже при порядках 20 становятся неприемлемо большими.

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

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

Рассмотрим непериодическую функцию (). Путь она задана на отрезке [0,], причем первые - 1 производных непрерывны, а -я — кусочно-непрерывна. При разложении () в ряд Фурье необходимо считать отрезок [0,] её периодом и периодически продолжить функцию. Если = 0 продолжение будет разрывным, а сходимость фурье–аппроксимации вблизи разрыва будет плохой (эффект Гиббса [66,67]). На практике для того, чтобы улучшить сходимость рядов Фурье, функцию и(х) предварительно чётно продолжают на отрезок [—7г,7г] (см. например [68]). После этого используется разложение по косинусам. При таком продолжении отсутствуют разрывы и(х) на границах. Этот подход заметно улучшает сходимость. Очевидно, при этом не гарантируется отсутствие разрывов первой производной и (х), что соответствует случаю р = 1. В [69, 70] предложен метод двойного периода, позволяющий использовать разложение одновременно по двум тригонометрическим подсистемам. Однако взаимная не ортогональность подсистем ухудшает сходимость для такого разложения, а применение метода в случае двумерной аппроксимации оказывается сложным и малоэффективным.

Давно известен способ улучшения сходимости рядов, ставший классическим. Он был сформулирован в начале XX-го века академиком Крыловым [71]. Основная идея — устранение разрывов исходной функции и(х) путём вычитания кусочно-заданного полинома г(х). Далее полученная функция v(x) = и(х) — г(х) разлагалась в ряд Фурье классическим методом (по синусам и косинусам). Подробная схема рассуждений изложена, например, в [72,73]. Как отмечается в [74], дальнейшее развитие и усовершенствование были достигнуты усилиями К. Эркгофа [75-78] и Д. Готтлиба [79-84] за последние 20 лет. Во всех этих работах отрезок задания функции и(х) принимался за её период.

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

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

Эффект Гиббса. Напомним простейший способ разложения непериодической функции в ряд Фуре. Примем отрезок задания функции [0,Т] за её период и периодически продолжим эту функцию на всю ось х. Даже если и(х) имела на отрезке [0,Т] много непрерывных производных, такое периодическое продолжение было бы разрывным в точках Xk = кТ, где к — целое число. Поэтому для такого продолжения следует полагать р = 0. Частичные суммы Фурье FN(X) при этом сильно осциллируют в малых окрестностях точек разрыва {xk}. Причем амплитуды этих осцилляций не убывают при N — +оо и составляют «. Чётное продолжение. Для обработки сигналов известен лучший способ. Отрезок [0,Т] принимается за половину периода функции. На вторую половину периода функция продолжается чётно, а далее — периодически. Если и(х) непрерывна на [0,Т], то полученное продолжение также будет непрерывным. Однако первая производная и (х) будет разрывная в точках Xk = кТ. Поэтому чётному продолжению соответствует р = 1. Эффект Гиббса при этом отсутствует, а сходимость ряда Фурье существенно улучшается в сравнении с простейшим продолжением.

Заметим, что такую же скорость сходимости можно обеспечить и в классическом продолжении, если использовать методы устранения разрывов путём вычитания специально подобранного линейного многочлена [68]. Однако в методе чётного продолжения этот результат получается более естественным путём и, вдобавок, приводит к более простым вычислениям.

При чётном продолжении немного упрощается и алгоритм. Если отрезок задания функции линейным преобразованием перевести в [0,7г], то продолженная и(х) будет чётной функцией. Поэтому в её ряде Фурье будут отсутствовать синусоидальные гармоники, и останутся только cos(nx). Вдвое уменьшается количество членов ряда и тот промежуток, на котором интегрируется функция при вычислении коэффициентов Фурье. Поэтому трудоемкость алгоритма уменьшается в 4 раза, что существенно в технических приложениях. Кроме того улучшение сходимости ряда позволяет ограничиться меньшим числом коэффициентов, что значительно уменьшает трудоёмкость.

Нечётное продолжение. Покажем, что, объединяя идею продолжения на вторую половину периода с идей устранения разрывов, можно предложить более эффективный метод. Пусть задана функция и(х), х є [0,7г] непрерывная вместе с первой производной. В общем случае и(0) = и(тг). Построим прямую, проходящую через граничные точки. Вычитая соответствующую линейную функцию из и(х), получим новую функцию

Похожие диссертации на Увеличение компрессии изображений в алгоритмах с фурье–преобразованиями