3.5. Линейные преобразования фрагментов изображения

При работе с готовыми растровыми изображениями часто возникает необходимость в преобразовании какого-либо выделенного фрагмента изображения в другую заданную область. Исходное и результирующее изображения могут размещаться либо непосредственно в видеопамяти, либо в оперативной памяти (обычно в формате bitmap).

Рассмотрим вначале частный случай, когда обе области – исходная Im1 и новая Im2 ограничены параллелограммами, причем ориентация и размеры параллелограммов могут быть различными (рис. 3.2).

Рис. 3.2

Для задания области Im1 достаточно указать три вершины параллелограмма, например T₁, T₂ и T₃. Координаты вершины T₄ при необходимости несложно рассчитать по точкам T₁, T₂ и T₃. Область Im2 также должна быть задана тройкой вершин P₁, P₂, P₃, соответствующих вершинам T₁, T₂, T₃. Координаты точки Р₄. можно найти по координатам точек P₁, P₂, P₃.

Если иметь преобразование W, ставящее в соответствие всякой точке P из Im2 точку T из Im1 (см. рис. 3.2), то поставленную задачу можно решить путем построчного сканирования области Im2, в процессе которого для каждой точки P с целочисленными координатами из Im2 с помощью W находится соответствующая точка T в Im1. Когда точка T найдена ее цветом нужно закрасить точку P.

Для наглядности матрицы-строки однородных координат точек T₁, T₂, T₂, P₁, P₂, P₃ будем обозначать так же, как и сами точки:

T₁ = [x_T1 y_T1 1], T₂ = [x_T2 y_T2 1], T₃ = [x_T3 y_T3 1];

P₁ = [x_P1 y_P1 1], P₂ = [x_P2 y_P2 1], P₃ = [x_P3 y_P3 1].

Преобразование W должно быть единым для всех точек области прибытия Im2, в том числе и для точек P₁, P₂, P₃, соответствующих точкам T₁, T₂, T₃. Поэтому

T₁ = P₁ W; (3.37)

T₂ = P₂ W; (3.38)

T₃ = P₃ W. (3.39)

Отметим, что преобразование W должно возвращать значение координаты v=1.

Чтобы найти W, объединим соотношения (3.37) – (3.39) в общую формулу:

M_t = M_p W, (3.40)

где

Умножим слева обе части уравнения (3.40) на матрицу M_p ^-1 , обратную матрице M_p:

M_p ^-1  M_t = M_p ^-1  M_p  W. (3.41)

В результате получим формулу для вычисления коэффициентов матрицы W искомого преобразования:

W = M_p ^-1  M_t. (3.42)

Ниже приводится алгоритм преобразования фрагмента изображения из области Im1 в область Im2.

1. Последовательно просматривая список вершин (P₁, P₂, P₃, P₄) области прибытия, найти границы ее сканирования Ymin и Ymax.

2. Для каждой строки Y из [Ymin . . Ymax] выполнить пп. 2.1 – 2.2.

2.1. Найти координаты xl и xr левой и правой точек пересечения области Im2 со строкой Y.

2.2. Для каждого целого X из [xl . . xr] выполнить пп. 2.2.1– 2.2.2.

2.2.1. Преобразовать с помощью преобразования W точку P = (X, Y) области Im2 в область Im1, т.е. вычислить координаты (X₁, Y₁) соответствующей точки T.

2.2.2. Считать код цвета точки T и переписать его в точку P.

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

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

Лекция 4. Трехмерная компьютерная графика