Разработка программного приложения для реализации параллельного алгоритма масштабирования изображений методом бикубической интерполяции - Дипломная работа

Часто при масштабировании изображений возникает необходимость не просто увеличить или уменьшить разрешение изображения, но и изменить при этом соотношение сторон изображения. В то время как при дискретизации непрерывная функция преобразуется в дискретную, интерполяция восстанавливает сигнал, потерянный в процессе дискретизации, путем сглаживания входных данных с помощью функции интерполяции. Важно понимать, что при интерполяции в изображение не добавляется новых деталей и новой «полезной» информации. Изображение, изначально полученное в высоком разрешении, всегда более предпочтительно с точки зрения качества, чем изображение, полученное путем масштабирования с низкого разрешения до высокого. Однако ступенчатая интерполяция и бикубическая интерполяция будут также рассмотрены с целью сравнения качества и времени обработки изображений.Существует две основные категории методов интерполяции: детерминированные и статистические методы интерполяции. Различие состоит в том, что детерминированные методы интерполяции предполагают некоторую зависимость между точками выборки, например, линейность в случае линейной иtrialоляции. Статистические методы интерполяции аппроксимируют сигнал, минимизируя ошибку оценки. Однако интерполяцию в нескольких измеtrialх для общего случая иногда трудно описать, поэтому целесообразно рtrialтривать n-мерную интерполяцию, как произведение n одномерных интерполяций.Алгоритм ближайшего соседа выбирает значение ближайшей точки и вообще не учитывает значения соседних точек, получая кусочно-постоянную функцию интерполяции. Алгоритм очень прост в реализации и широко используется при 3D-рендеринге в реальном времени для выбора значений цвета текстурированной поверхности. На рисунке 1 красными точками изображены входные данные, точки в которых известно значение интерполируемой функции.Алгоритм ступенчатой интерполяции является самым простым, как с точки зрения реализации, так и с точки зрения вычислительной трудоемкости.Основная идея состоит в том, чтобы интерполировать функцию, последовательно применив несколько раз одномерную линейную интерполяцию.Если две известные точки заданы координатами и , линейный интерполянт является прямой линией между этими точками. Для значения x в интервале значение у на прямой может быть вычислено из следующего уравнения: - 11 точки; Более близкая точка имеет больше влияния на результат интерполяции, чем более удаленная точка. Веса и являются нормированными расстояниями между точкой , значение функции в которой неизвестно, и каждой из точек и , значения функций в которых известны. На рисунке 3 красными точками изображены входные данные, точки в которых известно значение интерполируемой функции.Алгоритм билинейной интерполяции вычислительно более сложен, чем алгоритм ступенчатой интерполяции, однако результирующее изображение выглядит значительно более гладко, чем результат использования метода ступенчатой интерполяции.Бикубическая интерполяция - расширение одномерной интерполяции многочленами третьей степени на случай функции двух переменных, значения которой заданы на двумерной регулярной сетке. Поверхность, полученная в результате бикубической интерполяции, является гладкой функцией, в отличие от поверхностей, полученных в результате билинейной интерполяции или интерполяции методом ближайшего соседа. Основой бикубической интерполяции является такая операция, как Эрмитова интерполяция и непосредственно связанный с ней объект под названием кубический Эрмитов сплайн.Рассмотрим кубическую интерполяцию некоторой функции, заданной своими значениями и значениями первой производной. Если значения функции и ее производной известны при и , то функция может быть интерполирована на отрезке [0,1] с использованием многочлена третьей степени. В случае интерполяции изображения, оно играет роль интерполируемой функции, известными значениями которой являются цвета пикселей оригинального изображения, значения производной нам не известны. Интерполируем функцию в том же интервале Тогда значения функции и производной можно вычислить по следующим формулам: [] Поскольку изображение является функцией двух переменных, интерполяцию необходимо проводить по двум направлениям (по вертикали и по горизонтали).Алгоритм бикубической интерполяции вычислительно более сложен, чем алгоритм билинейной интерполяции, однако результирующее изображение выглядит более гладко, чем результат работы метода билинейной интерполяции.При интерполяции изображений изображение играет роль функции. Таким образом изображение играет роль функции двух переменных. Для удобства будем сопоставлять каждому пикселю точку на плоскости, а координатами этой точки считать координаты центра пикселя. Глубина цвета измеряется в количестве бит, необходимых для хранения информации о цвете одного пикселя. Исходное изображение имело ширину 6 пикселей и высоту 4 пикселя.В случае ступенчатой интерполяции значение цвета в каждой точке результирующего изображения принимается равным значению цвета в ближайшей точке исходного изображения.

Оглавление

Введение .....................................................................................................3

Общая постановка задачи..........................................................................6

1. Обзор существующих методов интерполяции изображений...............8

1.1. Ступенчатая интерполяция..............................................................9

1.1.1. Описание ....................................................................................9

1.1.2. Краткая характеристика...........................................................10

1.2. Билинейная интерполяция.............................................................11

1.2.1. Описание ..................................................................................11

1.2.2. Математический аппарат.........................................................11

1.2.3. Краткая характеристика...........................................................14

1.3. Бикубическая интерполяция..........................................................15

1.3.1. Описание ..................................................................................15

1.3.2. Математический аппарат.........................................................16

1.3.3. Краткая характеристика...........................................................19

2. Разработка алгоритма...........................................................................20

2.1. Ступенчатая интерполяция............................................................24

2.2. Билинейная интерполяция.............................................................24

2.3. Бикубическая интерполяция..........................................................28

2.4. Распараллеливание алгоритма.......................................................30

3. Реализация алгоритма ..........................................................................31

3.1. Формат хранения данных ..............................................................31

3.2. Код основных функций..................................................................31

4. Создание приложения..........................................................................36

4.1. Требования к приложению............................................................36

4.2. Основные возможности.................................................................36

4.3. Основные элементы интерфейса...................................................36

4.3.1. Главное окно приложения.......................................................36

4.3.2. Главное меню...........................................................................37

4.3.3. Диалог масштабирования........................................................37

5. Тестирование........................................................................................39

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

5.1.1. Пример 1...................................................................................39

5.1.2. Пример 2...................................................................................40

5.1.3. Пример 3...................................................................................40

5.1.4. Пример 4...................................................................................41

5.1.5. Пример 5...................................................................................42

5.2. Сравнение различных методов интерполяции по времени обработки изображений..................................................................................43

5.3. Исследование масштабируемости параллельного алгоритма .....44

Заключение...............................................................................................47

Список литературы ..................................................................................48

Приложение.