Разложение матрицы аффинного преобразования

в 13:57, , рубрики: Алгоритмы, математика, матрицы, Программирование

Не так давно в процессе разработки редактора 2D-графики возникла задача разложить матрицу аффинного преобразования на плоскости, на произведение матриц простых преобразований с тем, чтобы отобразить их пользователю и предложить какую-то более-менее адекватную интерпретацию того, что произошло с объектом на канвасе. Честно говоря, эта задача вызвала у меня определенные трудности. Университет я закончил уже давно, и мне было непонятно, а возможно ли это сделать в принципе, учитывая, что исходная матрица могла быть результатом произвольной последовательности сдвигов, масштабов, поворотов, и переносов, причем каждое преобразование могло иметь свой произвольный центр. И, во-вторых, непонятно было, как найти семь параметров, имея всего шесть коэффициентов матрицы. Ключом к решению этой задачи оказалась статья "Разложение матрицы центроаффинного преобразования для нормализации изображения"¹, в которой рассматривается такая же задача, но без учета преобразования переноса и для преобразований относительно центра координат. Далее я фактически просто адаптирую результаты этой статьи с учетом переноса и для произвольного центра преобразований.

Итак, пусть матрица, задающая произвольное преобразование на плоскости, имеет вид:

    ┌           ┐
    │ a11 a12 0 │
M = │ a21 a22 0 │.
    │ a31 a32 1 │
    └           ┘

Ее определитель

det = a11⋅a22 - a12⋅a21, det ≠ 0.

Пусть точка на плоскости задается вектор-строкой вида (x, y, 1), а ее преобразование – умножением справа на матрицу преобразования:

                            ┌           ┐
              ┌         ┐   │ a11 a12 0 │
p1 = p0 • M = │ x0 y0 1 │ • │ a21 a22 0 │
              └         ┘   │ a31 a32 1 │
                            └           ┘

В упомятнутой выше статье¹ утверждается, что произвольная матрица M центроаффинного преобразования может быть представлена как произведение матриц R поворота, матрицы Hx сдвига вдоль оси X и матрицы S масштабирования:

Mc = R • Hx • S

Здесь

    ┌                  ┐
    │  cos(α) sin(α) 0 │
R = │ -sin(α) cos(α) 0 │,
    │     0      0   1 │
    └                  ┘
     ┌         ┐
     │ 1  hx 0 │
Hx = │ 0  1  0 │,
     │ 0  0  1 │
     └         ┘
    ┌         ┐
    │ sx 0  0 │
S = │ 0  sy 0 │,
    │ 0  0  1 │
    └         ┘

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

M = T0 • S • H • R • T0⁻¹ • T,
     ┌             ┐
     │ 1    0    0 │
T0 = │ 0    1    0 │,
     │ -tx0 -ty0 1 │
     └             ┘
       ┌           ┐ 
       │ 1   0   0 │
T0⁻¹ = │ 0   1   0 │,
       │ tx0 ty0 1 │
       └           ┘
    ┌         ┐ 
    │ 1  0  0 │
T = │ 0  1  0 │.
    │ tx ty 1 │
    └         ┘

Подставив выражения для матриц простых преобразований получим следующие выражения для коэффициентов M:

a11 = sx⋅cos(α) - sx⋅hx⋅sin(α)
a12 = sx⋅hx⋅cos(α) + sx⋅sin(α)
a21 = -sy⋅sin(α)
a22 = sy⋅cos(α)
a31 = tx + tx0⋅(1 - (sx⋅cos(α) - sx⋅hx⋅sin(α))) + ty0⋅sy⋅sin(α) 
    = tx + tx0⋅(1 - a11) - ty0⋅a21
a32 = ty + ty0⋅(1 - cos(α)⋅sy) - tx0⋅(sx⋅hx⋅cos(α) + sx⋅sin(α))
    = ty + ty0⋅(1 - a22) - tx0⋅a12

Решая данные уравнения относительно sx, sy, α, hx, tx, ty, после некоторых упрощений, получим выражения для искомых параметров:

if a22=0
   α = π/2,
   sy = -a21
else
   α = atan(-a21/a22),
   sy = a22/cos(α),

sx = det(M)/sy,
hx = (a11⋅a21 + a12⋅a22)/det,

tx = a31 + ty0⋅a21 + tx0⋅(a11 - 1),
ty = a32 + tx0⋅a12 + ty0⋅(a22 - 1).

Выражения для α, sx, sy, hx сооветствуют аналогичным в статье¹, хотя и несколько отличаются от них по форме. Кроме того мы получили формулы расчета параметров преобразования переноса tx и ty. Хочется также заметить, что даже если в оригинальной последовательности присутствовали сдвиги вдоль обеих осей, в разложении достаточно лишь сдвига вдоль одной из осей (здесь – вдоль оси X). Кроме того, поскольку угол поворота определен как результат функиции арктангенса, он принципиально ограничен значениями от -90˚ до +90˚. Учитывая также, что угол поворота на 180˚ соответсвует sx=-1 и sx=-1, мы имеем здесь некоторую неоднозначность. Например, изначально имея поворот на 120˚ при разложении по данному алгоритму мы получим -60˚ и sx=sy=-1.


¹) Путятин Е.П., Яковлева Е.В., Любченко В.А. «Разложение матрицы центроаффинного преобразования для нормализации изображения»

Автор: ilowry

Источник



https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js