8
$\begingroup$

Can someone explain me how we can compute RQ decomposition for a given matrix (say, $3 \times 4$). I know how to compute QR decomposition.

I know the function in MATLAB which computes this RQ decomposition. But, I want to know how we can do that on paper.

PS: The practical use of RQ decomposition is in extracting the intrinsic and extrinsic parameters of the camera when the camera matrix $P(3 \times 4$) is given

thanks!

$\endgroup$
15
$\begingroup$

$\newcommand\iddots{\mathinner{ \kern1mu\raise1pt{.} \kern2mu\raise4pt{.} \kern2mu\raise7pt{\Rule{0pt}{7pt}{0pt}.} \kern1mu }}$

This concerns $RQ$ decompositions of square matrices.

Suppose you have a $n \times n$ matrix $A$ and want to compute the RQ decomposition. If you know how to compute QR decompositions, you will just need a few transpositions / row-column permutations.

Note that given the matrix $P := \begin{bmatrix} & & 1\\ & \iddots & \\ 1 & & \\ \end{bmatrix}$ (this is different to the camera matrix mentioned in the question), we get that $AP$ reverses the order of columns of $A$ and $PA$ reverses the order of rows. Also note that $P^T = P$ and $PP = E_n$, so $P^{-1} = P = P^T$, in particular $P$ is orthogonal.

Consider the following algorithm:

i.) Compute $\tilde A := PA$ (i.e. reverse rows of $A$)

ii.) Compute decomposition of $\tilde A ^T = \tilde Q \tilde R$

iii.) Set $Q := P \tilde Q^T$ (i.e. reverse rows of $\tilde Q^T$, note that $Q$ is orthogonal)

iv.) Set $R := P \tilde R^T P$

In step iv.) the following happens: $\tilde R$ is an upper triangular matrix. By transposing it, it becomes a lower triangular matrix. So we reverse rows and columns and obtain again an upper triangular matrix $R$. See sketch (start with lower triangular, reverse rows, then revere columns).

$$\begin{bmatrix} * & \cdot & \cdot \\ * & * & \cdot \\ * & * & * \end{bmatrix} \to \begin{bmatrix} * & * & * \\ * & * & \cdot \\ * & \cdot & \cdot \end{bmatrix} \to \begin{bmatrix} * & * & * \\ \cdot & * & * \\ \cdot & \cdot & * \\ \end{bmatrix} $$

Altogether $R$ and $Q$ yields our decomposition:

$$RQ = (P \tilde R^T P)(P \tilde Q^T) = P \tilde R^T \tilde Q^T = P(\tilde Q \tilde R)^T = P(\tilde A ^T)^T = P \tilde A = PPA = A$$

$\endgroup$
5
  • $\begingroup$ Copied as Comment by @NicholasCasale: From this link, and working through a RQ decomposition for an image projection, it seems that the accepted answer needs a left-to-right flip on R for it to be upper triangular. (MATLAB's fliplr(.)) $\endgroup$ – hardmath Feb 11 '17 at 6:04
  • $\begingroup$ You seem to be saying that $r(\tilde{R}^T)$ is upper triangular when $\tilde{R}$ is upper triangular. But although $\tilde{R}^T$ is surely lower triangular in this case, reversing the rows (which amounts to premultiplying by a particular permutation matrix $P$) does not produce an upper triangular matrix: $$\begin{bmatrix} * & \cdot & \cdot \\ * & * & \cdot \\ * & * & * \end{bmatrix} \to \begin{bmatrix} * & * & * \\ * & * & \cdot \\ * & \cdot & \cdot \end{bmatrix} $$ $\endgroup$ – hardmath Feb 11 '17 at 16:22
  • $\begingroup$ @hardmath Thanks, I refactored my post. It should be okay now. If you don't mind, please have a look and tell me if you see any more mistakes! $\endgroup$ – johnnycrab Feb 11 '17 at 21:00
  • $\begingroup$ At a glance you fixed it exactly as I would have. It might worth a caution that your permutation matrix $P$ differs from the "camera matrix" $P$ briefly mentioned in the Question. $\endgroup$ – hardmath Feb 11 '17 at 21:08
  • 1
    $\begingroup$ Ah, yes, didn't recognize there is also a $P$ in the question. Thanks again for all the effort! $\endgroup$ – johnnycrab Feb 11 '17 at 21:14
0
$\begingroup$

The solution by @jonnycrab is good when you have a QR-factorizer in hand. Here is the RQ Decomposition algorithm for a $3 \times 3$ matrix $A$ from Appendix A4.1.1 in Multiple view Geometry in Computer Vision 2nd ed. by Richard Hartley and Andrew Zisserman.

The rotation matrices for the $x,$ $y,$ and $z$ axes are:

$ Q_x = \left[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & c & -s \\ 0 & s & c \end{array}\right],\ \ Q_y = \left[\begin{array}{ccc} c & 0 & s \\ 0 & 1 & 0 \\ -s & 0 & c \end{array}\right],\ \ Q_z = \left[\begin{array}{ccc} c & -s & 0 \\ s & c & 0 \\ 0 & 0 & 1 \end{array}\right] $

where $c = \cos\theta,$ and $s = \sin\theta$ for some angle $\theta.$

  1. $R \leftarrow A$
  2. Multiply $R \leftarrow R Q_x$ so that $R_{32}$ becomes zero (see below).
  3. Multiple $R \leftarrow R Q_y$ so that $R_{31}$ is zero. This does not change the second column so $R_{32}$ remains zero.
  4. Multiple $R \leftarrow R Q_z$ so that $R_{21}$ is zero. The first two columns are replaced by linear combinations of themselves so $R_{31}$ and $R_{32}$ remain zero.
  5. $Q = (Q_x Q_y Q_z)^T$

    • The second step yields the equation $R_{32}\cdot c + R_{33}\cdot s = 0.$ A solution that satisfies the constraint $s^2 + c^2 = 1$ is $c = \frac{R_{33}}{\sqrt{R_{32}^2 + R_{33}^2}}$ and $s = \frac{-R_{32}}{\sqrt{R_{32}^2 + R_{33}^2}}.$ Note that we had two choices for the sign of $s;$ our choice forces $R_{33}$ to be positive.

    • For the third step we have $R_{31} \cdot c - R_{33} \cdot s = 0.$ The solution is $c = \frac{R_{33}}{\sqrt{R_{31}^2 + R_{33}^2}}$ and $s = \frac{R_{31}}{\sqrt{R_{31}^2 + R_{33}^2}}.$ Again, we could have chosen both $s$ and $c$ to be negative, but our choice yields a positive value for $R_{33}.$

    • For the fourth step we have $R_{21}\cdot c + R_{22}\cdot s = 0$. The solution is $c = \frac{R_{22}}{\sqrt{R_{21}^2 + R_{22}^2}}$ and $s = \frac{-R_{21}}{\sqrt{R_{21}^2 + R_{22}^2}}$ which forces $R_{22}$ to be positive.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.