Geometry and Algebra of Projective Views

Presentation on theme: "Geometry and Algebra of Projective Views"— Presentation transcript:

1 Geometry and Algebra of Projective Views
Cho, Hang Shin Computer Graphics Lab. Korea University

2 In Vision.. (x,y) (x,y,z) 2D Image 3D Geometry

3 In Graphics… Projection P0 P U (X,Y,Z) (x,y)

4 But, Inverse is Very Ambiguous!
(X,Y, ?... P (x,y) P0

5 Using Two View Points.. Epipolar Constraints as the basic Geometry
of the Vision Techniques...

6 Contents Vector Space Linear combination Affine Space
Homogeneous Coordinates Matrices Determinants Solving linear Equations

7 Content(Cont’d) Duality Linear Transformation Projection Equation
Camera Calibration in terms of Geometric View Epipolar Geometry

8 Part I Vectors and Matrices In Computer Graphics

9 Points and Vectors Point : 좌표계의 한 점을 차지 ,위치표시
Vector : 두 position간의 차로 정의 Magnitude와 Direction으로 표기 V P2 P1 x1 x2 y1 y2

10 Vectors (Cont’d) 3-Dimensional Vector
Vector Addition and Scalar Multiplication    V x z y

11 Scalar Product For Cartesian reference frame, Some Properties
Dot Product, Inner Product라고도 함 |V2|cos  V2 V1 For Cartesian reference frame, Some Properties Commutative Distributive

12 ux,uy,uz를 각 축의 단위 vector라 하면,
Vector Product V1 V2 V1  V2  ux,uy,uz를 각 축의 단위 vector라 하면, Properties AntiCommutative Not Assotiative Distributive

13 Vector Spaces A nonempty set V of vectors
Addition + Scalar Multiplication u+v = v+u  V · (u+v)+w = u+(v+w) u+0 = u · u+(-u) = 0 cu V ,(c is scalar) c(u+v) = cu+cv · (c+d)u = cu+du c(du) = (cd)u · 1u = u

14 Linear Combination Consist of scalar and vectors
Ex) Single Vector의 linear combination v v  v  : real number  : nonnegative

15 Span Span Ex) Span{v1,v2}  v1 +v2 v1 v2
Vector set의 모든 가능한 linear combination을 지칭 Ex) Span{v1,v2}  v1 +v2 v1 v2 두 Vector의 linear combination

16 Linearly Independence
A set of vectors B={v1,…,vp} in V is said to be linearly independent if the vector equation has only the trivial solution c1=0,…,cp=0. (3,1) (6,2) Linearly dependent, w in Span{u,v} u v w Linearly dependent, Collinear (3,2) w (6,2) Linearly independent, w not in Span{u,v} u v Linearly independent, Not collinear

17 The standard basis for R3
어떤 linearly independent vector set B에 의해 vector space H가 span될 때, 이 vector set B를 H의 basis 라 한다. H = Span{b1, … ,bp} z u3 u1 u2 y x The standard basis for R3

18 Orthogonal Basis Orthogonal basis ※ Orthonormal basis
- 각 원소 vector들이 서로 직교 할 때 z for all k for all j k - u3 u1 u2 - y x Orthonormal basis ※ Orthonormal basis 각 원소 vector들이 서로 직교 하면서 동시에 단위 vector로 이루어져 있을 때

19 Affine Space The Extension of the Vector Space
Geometric operation들이 의미를 갖는 공간 Vector Space의 0 같은 일정 기준점이 없다. Points와 그에 종속된 vector들로 표현 P Truncated plane (No Origin) : Vector Space P 기준의 새 좌표계 설정 : Affine Space

20 Affine Combination Linear combination of points in an affine space make no sense Parametric Representation 사용 P , t is real number Q P Q R

21 Parametric Representations
Defects in Nonparametric representation Explicit function의 경우 1. Can only represent infinite lines, not finite line segments 2. Cannot represent vertical lines(m=) 3. Can only 2D lines, not 3D Implicit function의 경우 원하는 것 이상의 표현을 포함 Ex) 원호의 표현 : y 발표 순서는 다음과 같습니다. 연구 목적, 관련 연구, 연구 특징을 살펴보고 연구 내용과 실험 결과를 설명 드린 후에 결론 및 향후 연구로 본 발표를 마치겠습니다. x

22 Parametric Representations
x,y,z좌표를 직접 쓰는 대신 parameter u를 사용 Ex) Circle Ex) Spherical Surface 발표 순서는 다음과 같습니다. 연구 목적, 관련 연구, 연구 특징을 살펴보고 연구 내용과 실험 결과를 설명 드린 후에 결론 및 향후 연구로 본 발표를 마치겠습니다. ※ u는 latitude를, v는 longitude를 나타냄.

23 Matrix Representations and Homogeneous Coordinates
P’ = T(tx, ty) P P’ = R() P P’ = S(sx, sy)P y x z =3 z =2 z =1 P(3x1,3y1,3) P(2x1,2y1,2) P(x1,y1,1) P(hx1,hy1,h) 한글을 발음하는 입술 애니메이션은 다음과 같은 문제점을 갖고 있습니다. 한글은 외국어와 차이가 있어 외국 모델을 그대로 사용할 수 없으며 연구 개요에서 보셨듯이 선행 연구는 부정확한 발음을 표현하고 동시조음도 고려하지 않아 실재와 다른 움직임을 보였습니다. 본 연구는 음절을 자연스럽게 발음하고 음절간의 움직임도 부드럽게 표현하는 모델을 구현하는 것이 목적입니다. 3D Representarion of homogeneous space

24 Matrices Scalar multiplication and Matrix Addition Definition
A rectangular array of quantities Scalar multiplication and Matrix Addition

25 Matrix Multiplication
Definition Properties Not Commutative Assotiative Distributive Scalar multiplication × = (i,j) j-th column i-th row m l n

26 Translation y P x (a) y P’ x (b)

27 Scaling x’ = xf + (x-xf) sx , y’ = yf + ( y- yf) sy x’ = x · Sx ,
y’ = y · Sy x’ x P2 (xf, yf) : fixed point x y (xf,yf) P1 P3 x’ = xf + (x-xf) sx , y’ = yf + ( y- yf) sy

28 Rotation P’ = R P x = r cos  , y = r sin 
(x’,y’) P’ = R P x = r cos  , y = r sin  x’ = r cos ( + ) = r cos  cos  - r sin  sin  y’ = r sin ( + ) = r cos  sin  + r sin  cos   x’= x cos  - y sin , y’ = x sin  + y cos  r  (x,y) r  죄표중심을 회전점으로 각  만큼 회전

29 Determinant of a Matrix
For n 2, the Determinant of nn matrix A is, and for a 2 by 2 matrix, Ex) if A is a triangular matrix, det A is the product of the entries on the main diagonal of A

30 Properties of Determinants
Row Operations Let A,B be a square matrix 1) A의 한 행의 실수배가 다른 row에 더해져 B를 만들었다면, detB = detA 2) A의 두 행이 교환되어 B를 생성했다면, detB = -detA 3) A의 한 행이 k배된 것이 B라면, detB = kdetA Ex) Column Operations

31 Solving Linear Equation
where, ajk and bj are known Using Matrix Equation ※Coefficient Matrix A의 역행렬이 존재할 때만 성립

32 Inverse Matrix • Definition • Properties • 2  2 matrix의 경우
If ad-bc = 0, then A is not invertible.

33 Inverse Matrix • Algorithm for Finding A-1 : Row reduction
[ I A-1] 형태의 row reduction이 존재하지 않으면, A is not invertible. Ex)

34 Cramer’s Rule For invertible nn matrix A and b, let Ai(b) be the matrix obtained from A by replacing column i by the vector b, x of Ax=b is, column i Ex) detA=2

35 Gaussian Elimination System에서 한 행의 실수배를 다른 행에서 빼어 연립방정식의 차수를 줄여나가다, 한 변수의 해가 구해지면, 역으로 대입해 나머지 변수값을 구한다. • Elementary Row Operation 1. Multiply any row of the augmented matrix by a nonzero constant 2. Add a multiple of one row to a multiple of any other row 3. Interchange the order of any two rows

36 Using Row Operations

37 Consistency of Linear System
1. Unknown variable의 수에 비해 equation의 수가 적을 때 No Unique solution (Infinite set of solution) 2. Unknown variable의 수에 비해 equation의 수가 많을 때 1) Consistent한 경우 : 구한 해가 남은 방정식에 대해서도 성립(redundant) 2) Inconsistent한 경우 (infinity) (no solution)

38 Singular Matrix • nn system이 unique solution을 갖지 않을 때 , 그 system
의 coefficient matrix를 singular하다고 한다. • 일반적으로 coefficient matrix를 triangulization했을 때, diagonal에 0이 있으면 singular하다. ( No solution,Inconsistent ) ( Infinity,redundant )

39 Iterative Method - Gaussian Elimination의 roundoff error를 해결하기 위함

40 Norms The magnitude of multicomponent entities like matrices and vectors(the measure of “bigness” or “smallness”) Four properties 1. Must have a value greater than or equal to 0. 2. Must be multiplied by |k| if the matrix is multiplied by the scalar k. 3. The norm of the sum of two matrices must not exceed the sum of the norms 4. The norm of the product of two matrices must not exceed the product of the norms Vector의 p-norm Matrix의 2-norm