Affine Transformation of Points

mediumPROGeometric TransformationsComputer Vision 2

Implement an affine transformation to map a list of 2D points using a given 2x3 transformation matrix. This process involves applying a linear transformation followed by a translation to each point.

The affine transformation is a fundamental concept in Computer Vision and Geometric Transformations, as it preserves straight lines and ratios of distances between points lying on a straight line. The transformation can be represented by the equation $\begin{bmatrix} x' \\ y' \end{bmatrix} = M \cdot \begin{bmatrix} x \\ y \\ 1 \end{bmatrix}$ , where $M$ is the 2x3 transformation matrix and $\begin{bmatrix} x \\ y \\ 1 \end{bmatrix}$ is the point in homogeneous coordinates.

Here are the steps to apply the transformation:

Convert each point to homogeneous coordinates by appending 1 to the coordinates.
Multiply the resulting vector by the 2x3 transformation matrix. The main equation for this process is:

\begin{bmatrix} x' \\ y' \end{bmatrix} = \begin{bmatrix} m_{00} & m_{01} & m_{02} \\ m_{10} & m_{11} & m_{12} \end{bmatrix} \cdot \begin{bmatrix} x \\ y \\ 1 \end{bmatrix}

This technique is widely used in image processing and computer vision applications.

Example

Input

M = [[1, 0, 5], [0, 1, 10]]
points = [[0, 0], [1, 1]]

Output

[[5.0, 10.0], [6.0, 11.0]]

Reasoning

We apply the affine transformation to the first point (0, 0) using the given matrix $M = \begin{bmatrix} 1 & 0 & 5 \\ 0 & 1 & 10 \end{bmatrix}$ : $\begin{bmatrix} x' \\ y' \end{bmatrix} = \begin{bmatrix} 1*0 + 0*0 + 5 \\ 0*0 + 1*0 + 10 \end{bmatrix} = \begin{bmatrix} 5 \\ 10 \end{bmatrix}$ .
Then, we apply the same transformation to the second point (1, 1): $\begin{bmatrix} x' \\ y' \end{bmatrix} = \begin{bmatrix} 1*1 + 0*1 + 5 \\ 0*1 + 1*1 + 10 \end{bmatrix} = \begin{bmatrix} 6 \\ 11 \end{bmatrix}$ .
The transformed points are then rounded to 4 decimal places, but since the results are already integers, they remain the same.
The final output is a list of the transformed points: $[[5.0, 10.0], [6.0, 11.0]]$ .

Constraints

M is a 2x3 matrix (list of 2 rows, each with 3 elements)
points is a list of [x, y] pairs
Return list of [x', y'] rounded to 4 decimal places

Learn this in

Image ProcessingCV Study Plan Image Alignment and StitchingCV Study Plan

More from Computer Vision 2

1D Bilateral Filterhard Image Sharpening with Unsharp Maskmedium Gaussian Blurmedium Gaussian Kernel Generationeasy 2D Image Convolutioneasy

Concept primerPREVIEW

Background Knowledge

Affine transformations are a fundamental concept in computer vision and geometry, used to describe transformations that preserve straight lines and ratios of distances between points. These transformations can be represented by a 2x3 matrix $M$ , which is applied to a point $(x, y)$ to produce a new point $(x', y')$ . The transformation matrix $M$ has the form:

M = \begin{bmatrix} m_{00} & m_{01} & m_{02} \\ m_{10} & m_{11} & m_{12} \end{bmatrix}

The transformation is applied by multiplying the matrix $M$ with the homogeneous coordinates of the point $(x, y, 1)$ , resulting in the transformed point $(x', y')$ .

The key concept here is the use of homogeneous coordinates, which allow for the representation of affine transformations using matrix multiplication. Homogeneous coordinates are a way of representing points in a projective space, where each point is represented by a vector of coordinates $(x, y, w)$ , with the constraint that $(x, y, w) = (kx, ky, kw)$ for any non-zero scalar $k$ . This allows for the representation of points at infinity, which is essential for affine transformations.

In the context of this problem, the given affine transformation matrix $M$ represents a specific transformation, such as rotation, scaling, or translation, or a combination of these. The goal is to apply this transformation to a list of 2D points and return the transformed points.

Algorithm/Approach

The general approach to solving this problem involves applying the affine transformation matrix $M$ to each point in the list of 2D points. This can be done using matrix multiplication, where each point is represented as a homogeneous coordinate vector $(x, y, 1)$ .

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.