Алгоритм сортировки по глубине использующий Z- буфер.

Принципиальное отличие от алгоритма Ньюэма- Санча заключа-ется в том, что Z координаты рассматриваются не для многоугольников, а для точек экрана. Для хранения Z координат используется буфер глубины или Z-буфер, который может представить из себя как часть ОП, так и специальный сегмент памяти, принадлежащей графической подсистеме ПК. Перед началом работы алгоритма выполняются следующие операции:

1) в видео буфер заносится изображение фона;

2) в Z-буфер заносится максимальное значение Zmax.

Затем каждый многоугольник раскладывается в растр и записывается в видео буфер без сортировки по глубине. При разложении в растр для каждой точки i-ого многоугольника c координатами (x,y) выполняются следующие действия:

- вычисление глубины i-ого многоугольника – точки Zi (x,y);

- в том случае, если рассчитанное значение Zi(x,y) < Zбуф(x,y), то цвет многоугольника заносится в точку (x,y) видеобуфера. В противном случае изменения видеобуфера не происходит и осуществляется переход к следующей точке.

Таким образом, после обработки всех многоугольников сцены в Z-буфере оказываются координаты ближайших к наблюдателю объектов. Единственной трудоемкой операцией является вычисление Z-координат многоугольника по координатам (x,y). Однако если рассматривать эту операцию более детально, то и ее трудоемкость можно значительно снизить.

Для вычисления Z(x,y) используется формула Ax+By+Cz+D=O отсюда: Z(x,y) = - (Ax+By+D)/C, т.к. развертка идет вдоль строк, то полное вычисление Z координат можно производить один раз на строку растра. Остальные значения вычисляются как Z(x+Ux,y): Z = Z1 + A*Ux/C. Таким образом, при отображении очередного пиксела растра необходима одна операция вычитания.

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

Недостаток. Необходимость значительного объема буфера глубины.

Область применения:

1) мультимедийные игровые программы;

2) аппаратная реализация 3D-ускорителя, предназначенного для бытовых/игровых ПК.

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

Конец 27 вопроса.
28. Простейшие алгоритмы масштабирования растровых изображений.

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

На рис. 4.43 черным цветом показана исходная дискретная целочисленная решетка. Величины, расположенные в узлах этой решетки известны: это яркости соответствующих составляющих в исходном изображении. Синим цветом показана новая сетка, в узлах которой требуется вычислить значения цветовых составляющих. Восстановление уровней яркости в узлах новой сетки и называется “передискретизацией”. Поскольку координаты чаще всего не попадают в узлы дискретной решетки (рис. 2.3), то возникает задача восстановления соответствующего значения яркости по ближайшим узлам. Она решается с помощью методов двумерной интерполяции. Именно эти методы и определяют качество результирующего изображения. Интерполяционное ядро имеет значительное влияние на численное поведение интерполированных функций. Теоретически оптимальную интерполяцию обеспечивает известная sinc-функция, в одномерном случае имеющая вид:

 

 

Математическое описание метода состоит в следующем:

• вычисляется диагональ прямоугольника исходной сетки Dgnl;

• вычисляется расстояние от каждого узла до заданной точки и разность с диагональю:

R0= Dgnl – D0;

R1= Dgnl – D1;

R2= Dgnl – D2;

R3= Dgnl – D3;

• вычисляется сумма этих расстояний

SumR= R0+R1+R2,+R3;

• вычисляется значение цветовой составляющей в точке:

V= (A R0+B R1+C R2+D R3)/SumR.

Линейная интерполяция

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

Для того чтобы получить уравнение плоскости необходимо знать координаты 3-х точек. Уравнение задается в матричной форме:

Вычислив определитель и выразив координату z=f(x,y) мы получим формулу, приемлемую для вычисления цветовых составляющих в точках, лежащих внутри ячейки исходной сетки. Но как показывает анализ решаемой задачи, полученную формулу можно значительно упростить, если ввести ограничения, накладываемые практической реализацией. Для примера рассмотрим произвольную ячейку исходной сетки.

Если точка, яркость которой необходимо вычислить, расположена внутри треугольника АВС, то уравнение плоскости рассчитывается с использованием координат этих точек. Если же точка принадлежит треугольнику BDС, то плоскость рассчитывается по этим 3 точкам, с учетом того, что за (x1, y1) принимаются координаты точки D(x’1, y’1).

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

Конец 28 вопроса.
29. Масштабирование растровых изображений с использованием форм Безье и В-сплайнов.

Выяснилось, что эта функция имеет более предпочтительные высокочастотные свойства, нежели кубический B-spline, и было предложено называть данную функцию высокоразрешающим интерполяционным кубическим сплайном. Варьируя значением параметра a в пределах от –1 (рис. 10а) до -1/2 (рис. 10б) в каждом конкретном случае можно добиться приемлемой точности при передискретизации.

Конец 29 вопроса.
30. Алгоритмы фильтрации растровых изображений, базирующиеся на свертке.

Свертка - это алгоритм общего назначения, который можно использовать в различных преобразованиях растровых изображений. Свертка (convolution), или свернутое матричное произведение, представляет собой результат следующей матричной операции: C = A • B = ΣΣ aij×bij. Каждый элемент в области примыкания (на рис.4.41 она имеет размер 3х3) умножается на ядро свертки аналогичной размерности: C = P • K = ΣΣ pij×kij,

где pij - значения пикселей, из области примыкания, а kij –элементы ядра свертки, называемые весовыми факторами, или коэффициентами свертки.

Результат С при этом заменяет значение рассматриваемого элемента изображения. Размеры и структура весовых факторов, содержащихся в ядре свертки, определяют тип 2D-преобразования. Изменение весового фактора в пределах ядра свертки влияет на величину и, возможно, на знак общей суммы и, таким образом, воздействует на значение рассматриваемого элемента изображения. Большинство матриц ядер имеют размер 3х3 (или в общем случае - нечетное число рядов и колонок). Этот формат коэффициентов свертки в пределах ядра используется на практике в качестве стандарта. Увеличение размера ядра повышает гибкость процесса свертки. На рис. 4.41 представлена схема процесса свертки. Область примыкания описывается матрицей P =pij, где pij - значения пикселей, входящих в область примыкания пикселя pyx, расположенного в позиции x строки y. Для ядра размером 3х3:

i = (y-1)÷(y+1),

j = (x-1) ÷(x+1)).

При фильтрации изображений возникает ряд трудностей.

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

1) данные на краях изображения не учитываются или

2) данные изображения могут копироваться, для того чтобы “синтезировать” дополнительные данные границы.

Вторая трудность связана с выходом новых значений преобразуемых элементов за пределы допустимых значений. Для большинства ядер новые значения преобразуемых элементов находятся в пределах действительных значений от 0 до 255. К сожалению, ядро размытия дает значения, выпадающие из диапазона действительных значений элементов изображения. По этой причине в алгоритм свертки вводится масштабирование.

При внимательном рассмотрении становится понятным, почему ядро размытия дает такие большие значения, в отличие от других ядер. Во всех ядрах, за исключением ядра размытия, сумма всех весовых коэффициентов равна либо 0, либо 1. Сумма коэффициентов ядра размытия равна 25. Это означает, что расчет весовой суммы будет равен 25 значениям элементов изображения в области примыкания 5х5. Окончательный выбор параметра масштабирования является субъективным и зависит от вида изображения. Также необходимо учесть в алгоритме свертки знак значений элементов изображения. Если ядро свертки содержит отрицательные вещественные коэффициенты, что характерно для большинства ядер, можно получить отрицательное значение интенсивности элементов изображения. По этой причине отрицательное значение элементов изображения при свертке устанавливают равное 0. Для того чтобы рассмотреть отрицательные значения интенсивности используются другие методы. Например, можно использовать абсолютное значение интенсивности вместо присваивания значения, равного 0. Другой метод состоит в масштабировании всех значений элементов таким образом, чтобы отрицательные значения стали равными 0.

В рамках данного раздела рассматриваются следующие фильтры, использующие алгоритм свертки:

• низкочастотные пространственные фильтры;

• высокочастотные пространственные фильтры;

• усиление края методом сдвига и разности;

• усиление края методом выравнивающего фильтра;

• усиление края методом направленного градиента;

• усиление края по Лапласу;

• фильтры размытия;

• медианный фильтр.

Далее рассмотрим все вышеперечисленные типы фильтров, использующие алгоритм свертки.