Geometric transformations in Computer Vision

Cũng như hầu hết các lớp dạy về Computer Vision hay Computer Graphics, lớp của UC Berkeley trên coursera cũng bắt đầu  bằng mô hình pinhole camera (tất nhiên là sau một bài tổng quan về computer vision, với nhiều nội dung thú vị mà ta có thể trở lại khi có dịp). Điều hơi “bất ngờ” là ngay sau đó, nội dung quan trọng thứ 2 là nói về các phép biến đổi hình học trong 2D và 3D, bao gồm Rigid body transformation, orthogonal transformation, affine transformation, biểu diễn phép quay trong 3D v.v…

Bài này sẽ tóm tắt một số ý chính của các phép biến đổi hình học, coi như là một trong những bài trực tiếp về Computer Vision hiếm hoi trên blog này, mặc dù mục tiêu ban đầu và xuyên suốt của blog là viết về Computer Vision 🙂

1. Khái niệm Pose và Shape

Trong mô hình pinhole camera, một điểm trong không gian được gán cho một tọa độ 3D với hệ trục tọa độ là cố định đối với camera. Khi một điểm di chuyển, tọa độ của nó thay đổi. Chẳng hạn một cái bàn trong không gian có thể thay đổi vị trí của nó so với camera nhưng bản thân cái bàn không thay đổi. Trong computer graphics, ta gắn cho cái bàn thêm một hệ trục tọa độ nữa (gọi là object coordinates) bên cạnh world coordinates gắn với camera. Trong computer vision, ta nắm bắt thực tế này bằng 2 khái niệm là poseshape.

  • Pose: miêu tả vị trí và hướng của vật thể so với camera. Trong 3D, ta biểu diễn pose bằng 6 tham số: 3 cho vị trí và 3 cho phép quay.
  • Shape: tọa độ của các điểm trên vật thể so với hệ tọa độ gắn trên vật thể (object coordinates).

Khi cái bàn di chuyển, pose của nó thay đổi nhưng shape là không đổi, trừ khi ta làm biến dạng cái bàn bằng cách nào đó. Cụ thể hơn, dưới tác dụng của phép quay và phép tịnh  tiến, shape là không đổi. Tổng quát hơn, phép quay và phép tịnh tiến là trường hợp cụ thể của rigid body transformation mà ta sẽ nghiên cứu trong bài này. Ngoài ra ta cũng sẽ điểm qua orthogonal transformation và affine transformation. Cả 3 dạng này đều có nhiều ứng dụng thực tiễn trong vision.

Một cách tổng quát, tọa độ của 1 điểm \textbf{a} trong 3D được biểu diễn bằng 1 vector 3 chiều \textbf{a} = \left[x\;y\;z\right]^\top\in \mathbb{R}^3. Một phép biến đổi (transformation) \psi được định nghĩa là ánh xạ điểm \textbf{a}\in \mathbb{R}^3 thành điểm \psi\left(\textbf{a}\right)\in \mathbb{R}^3.

Từ đó ta có định nghĩa biến đổi tuyến tính (linear transformation) là các biến đổi có dạng \psi \left( \textbf{a} \right) = \textbf{Aa}, với \textbf{A} là ma trận nào đó.

2. Rigid body transformation, Orthogonal transformation và Affine transformation

Ta tóm tắt bằng bảng sau

Tên Định nghĩa Dạng của \psi Các phép biến đổi
Orthogonal transformation \psi \left(\textbf{a}\right)\cdot\psi\left(\textbf{b}\right) = \textbf{a}\cdot\textbf{b}

Bảo toàn tích vô hướng

\psi\left(\textbf{a}\right) = \textbf{Aa}

với A là ma trận orthogonal.

rotation, reflection
Rigid body transformation

(còn gọi là Euclidean transformation hay isometry)

\parallel \psi\left(\textbf{a}\right) - \psi\left(\textbf{b}\right)\parallel = \parallel \textbf{a} - \textbf{b} \parallel

Bảo toàn khoảng cách giữa 2 điểm bất kì

\psi\left(\textbf{a}\right) = \textbf{Aa} + \textbf{t}

với A là ma trận biểu diễn một orthogonal transformation  và t là một phép tịnh tiến.

rotation, reflection, translation
Affine transformation Bảo toàn đường thẳng và bảo toàn tỉ lệ  \psi\left(\textbf{a}\right) = \textbf{Aa} + \textbf{t}

với A là ma trận không suy biến bất kì (det(A)\neq 0).

  rotation, reflection, translation, shearing…
Projective transformation

(Homography)

Bảo toàn đường thẳng  \psi\left(\textbf{p}\right) = \textbf{Pp}

với p là tọa độ thuần nhất và P là ma trận 4\times 4

Ngoài ra ta còn một số tính chất rất đẹp:

  • Trong orthogonal transformation, nếu A là ma trận orthogonal thì A^{-1}=A^\topdet\left(A\right) = 1 hoặc det\left(\textbf{A}\right)=-1. Ma trận orthogonal A với định thức bằng 1 ứng với phép quay và định thức -1 ứng với phép đối xứng (reflection). Cụ thể trong 2D thì ma trận A chỉ có thể thuộc 1 trong 2 dạng sau:
    \left[\begin{array}{cc}\cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{array}\right] hoặc  \left[\begin{array}{cc}\cos\theta & \sin\theta \\ \sin\theta & -\cos\theta \end{array}\right]
    Trong 3D phép quay có hơi phức tạp hơn, ta sẽ xem xét trong một bài khác.
  • Trong orthogonal transformation, 2 phép quay liên tiếp sẽ cho ta một phép quay, nhưng 2 phép phản xạ liên tiếp cũng cho một phép quay (dễ dàng kiểm tra).
  • Orthogonal transformation bảo toàn norm:
    \psi\left(\textbf{a}\right)\cdot\psi\left(\textbf{a}\right) = \textbf{a}\cdot\textbf{a} \Rightarrow \parallel a\parallel = \parallel \psi(a)\parallel
    nghĩa là bảo toàn khoảng cách từ điểm a đến gốc tọa độ. Dễ dàng chứng minh. Bằng trực giác ta cũng thấy rằng phép tịnh tiến không bảo toàn norm.
  • Mọi phép biến đổi orthogonal đều là rigid body transformation.
  • Họ các phép biến đổi rigid body transformation có dạng \psi\left(\textbf{a}\right) = \textbf{Aa} + \textbf{t} tạo thành một nhóm với tính đóng, phần tử đơn vị, phần tử nghịch đảo và thỏa tính kết hợp. Đây là kết quả rất đẹp mà nếu có dịp ta sẽ trở lại sau.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s