2 CAD : CAD 7

1 CAD 2017.6.25

2 CAD 2 3 1998 1 0 6 : CAD 7

3 CAD 2017 6

4 0 7 0.1 1............................. 7 0.2 2............................. 8 0.3 3............................ 9 0.4 4............................ 9 0.5 5............................. 10 0.6 6 :...................................... 11 0.7 7........................... 12 1 13 1.1........................................ 13 1.2.................................... 13 1.3........................................ 14 1.4...................................... 14 1.5........................................ 14 1.6......................................... 15................................................ 15 2 16 2.1........................................ 16 2.2...................................... 16 2.3......................................... 17 2.4......................................... 17 2.5...................................... 17 2.6......................................... 17 2.7..................................... 18................................................ 18

5 3 20 3.1......................................... 20 3.2......................................... 20 3.3........................................... 20 3.4....................................... 21 3.5............................................ 21 3.6....................................... 21 3.7......................................... 21................................................ 22 4 23 4.1...................................... 23 4.2................................... 24 4.3......................................... 24 4.4......................................... 25 4.5....................................... 25................................................ 25 5 27 5.1...................................... 27 5.2...................................... 27 5.3...................................... 27 5.4...................................... 28 5.5...................................... 28 5.6...................................... 28 5.7 2.......................................... 29 5.8...................................... 29 5.9...................................... 30 5.10....................................... 30 5.11 2.......................................... 31 5.12....................................... 31 5.13...................................... 32................................................ 32 6 : 34 6.1........................................... 34

6 6.2................................... 37 6.3...................................... 40 6.4...................................... 42 6........................................... 46................................................ 47 7 49 7.1............................................ 49 7.2...................................... 49 7.3........................................... 51 7.4........................................ 52 7.5......................................... 53 7.6........................................... 56 7.7........................................ 58 7........................................... 61................................................ 63 65 67

7 0 1 2 0.1 1 1 2 2 F (x, y) = 0 t (x(t), y(t)) xy

0 8 0.2 2 2 3 2 3 3 3 3 3 t (x(t), y(t), z(t)) xyz

0 9 0.3 3 z = f(x, y) F (x, y, z) = 0 (x(u, v), y(u, v), z(u, v)) 2 0.4 4 3

0 10 ) 0 1 2 3 0 1 1 2 0 0 0 1 1 1 2 2 2 1 2 0.5 5 1 2 3 1 2 3 2 3 4 0 3 2 2 3 3 3 2 2 2 2 4 4 4

0 11 2 2 3 4 (, 0), (, 0) 5 (, 0, 0), (0,, 0), (0, 0, ) 2 2 2 2 2 2 2 2 0.6 6 : 3 3

0 12 3 3 0.7 7 2 2 2

13 1 1.1 (a, b) a, b a, b (a, b) = 0 a, b a, b = 0 a u (u, a) a u 1.2 a, b a, b a, b 1.3 a, b a, b a, b a, b 1.2 (1.15) P n a n P n a 1.6(a) (1.16) R(θ) a θ R(θ)a

1 14 1.3 h n (1.27) 1 r 0 u (1.29) 2 2 1.4 xy O θ t x y (1.40), (1.42), (1.43) O θ t (1.41), (1.44), (1.45) 1.5 F (x, y) = 0 t x = x(t), y = y(t) F (1.53) F (1.59) x = x(t), y = y(t) (1.57), (1.59) k k

15 1.6 3 (1.72) s (1.73) κ s x = x(s), y = y(s) (1.74) κ a, b,... (geometricalgebar) [65] a a R Ra (versor) R RaR. 20 (1.8) a, b a, b 2 2 a, b a, b

16 2 2.1 a, b, c a, b, c a, b, c c a, b a b c = a b a, b a, b a, b, c 2.1(a) a, b, c a, b, c 2.1(b) a, b, c a, b, c a, b (a, b) = 0 a, b a b = 0 a, b, c a, b, c = 0 2.2 (2.16) P n a n P n a 2.2(a) (2.17) R(n, Ω) a n Ω R(n, Ω)a a n ω / ȧ = ω a ω = ωn

2 17 2.3 m O n (1.29) m, n m 2 + n 2 = 1 n m 2.3(b) 1 r 0 u (1.28) 2.3(a) 2 2 2.4 h n 2.5(b) 2 3 2.5 xyz O R t x y z O R t 2.6 t x = x(t), y = y(t), z = y(t) (2.58) x = x(t), y = y(t), z = z(t) (2.60), (2.61)

18 k k 2.7 2.10 3 3 s (2.68) κ τ s x = x(s), y = y(s), z = z(s) (2.70) κ τ (2.13) a, b, c a, b, c 3 3 1 a, b, c (Sir William Rowan Hamilton: 1805 1865) (quaternion) q = q 0 + q 1 i + q 2 j + q 3 k z = x + iy i, j, k i 2 = j 2 = k 2 = 1 (Hermann Günter Grassmann: 1809 1877) (Grassmann algebra) 2 p 1, p 2 l l = p 1 p 2 3 p 1, p 2, p 3 Π Π = p 1 p 2 p 3 (outer product)

19 (Josiah Willard Gibbs: 1839 1903) (a, b) a b a, b, c (vector calculus) 3 (David Orlin Hestenes: 1933 ) [65] 2 3 1 (join) (meet) (dual plane) (dual point) (dual line) 2 (duality theorem) 3 (2.20) (Benjamin Olinde Rodrigues: 1795-1851) (Rodrigues formula) 3 (2.17) (2.22) binormal (moving frame)

20 3 3.1 xyz z = f(x, y) F (x, y, z) = 0 u, v x = x(u, v), y = y(u, v), z = z(u, v) 3.2 z = f(x, y) f(x, y) 3.3 xy (3.13) H K (K > 0) (K = 0) (K < 0) 3.5

3 21 3.4 3.5 F (x, y, z) = 0 F (3.35) F (3.36) κ H K 2 F F (3.40) (3.42) 3.6 x = x(u, v), y = y(u, v), z = z(u, v) x, y, z u, v e 1, e 2 (3.53) n (3.54) e 1, e 2, n {e 1, e 2, n} (3.60) κ H K {e 1, e 2, n} (3.78), (3.79) 3.7 {e 1, e 2, n} (u, v) e i / u j, n/ u j u = u 1, v = u 2 (3.91), (3.92) j k ij ff 2

22 (3.94) (3.95) 2 3 (differential geometry) (3.15) (total curvature) (Gaussian curvature) 3.3 (Jan Johan Koenderink: 1943 )[28] 3.6 (u, v) (tensor calculus) 3 CAD (Albert Einstein: 1879 1955) (1936 ) (statistical geometry)

23 4 4.1 3 0 1 2 3

4 24 0 4.2 4.7 0 S 1 0 1 2 3 4.11 4.3 0 4.13 0 4.13 1 1 4.15 0 0 4.13 1 4.16 2 4.19, 4.20 3

25 4.21 0 3 1 1 1 4.4 uv xyz 2 u, v 3 u, v 2 x, y, z 4 x, y, z 4.5 0 x f(x) = 0, g(x) = 0 x 2 x, y f(x, y) = 0, g(x, y) = 0, h(x, y) = 0 x, y [27 32] (catastorophy) 1970 (René Frédéric Thom: 1923 2002)[52]

26 4.5

27 5 5.1 1 3 1 2 0 1 1 (5.4) 5.2 2 L, l v L p p v l P 2 5.3 0 (5.10) 1

5 28 5.4 2 4 2 (, 0) (0, ) 2 (0, 0) (1, 1) 1 (5.13) (5.15) 5.5 2 Π, π v Π p p v π P 2 5.6 0 (5.17) 2

5 29 3 3 (5.21), (5.22), (5.23) 5.7 2 2 x 2 + y 2 = 1 2 2 1 2 2 3 3 2 2 2 5.8 2 5.18(a) 2 2 2 2 2 2

5 30 2 5.18(b) 2 5.9 3 5 3 (, 0, 0), (0,, 0) (0, 0, ) 2 (0, 0, 0) (1, 1, 1) 1 (5.44) (5.47) 5.10 0 (5.49) 3

5 31 4 4 (5.55), (5.56), (5.57) 5.11 2 2 1 2 x 2 + y 2 + z 2 = 1 1 2 2 2 4 4 2 2 5.12 2 5.24) 2 2 2 2 2 2 2 2

32 5.13 Π v p p v Π P 2 2 Π v π Π p p v π P p 2 π 2 π π π π CAD (homogeneous coordinate) 1 2 3 4 2 2 0 2 1 2 0 CAD (projective space) (topology) 1 (point at infinity) 2 (linet at infinity) 2 3 (planet at infinity)

33 CAD 5.10 (x, y, z) (x, y, z ) x y = A z A (5.51) 1 4 4 B x y z 1 x y z 1 = x x x y y BA z C,..., D y z = D BA z 1 1 1 CAD [ x y z 1] [ x y z 1] = [ x y z 1 ]A 4 4 B [ x y z 1] = [ x y z 1 ]AB C,..., D [ x y z 1] = [ x y z 1 ]ABC D CAD x y z 1 ( x y z 1) ABC A B C...

34 6 : 3 6.1 3 A : (x A, y A ), B : (x B, y B ), C : (x C, y C ) (x, y) (barycentric coordinates) (α, β, γ) (x, y) ( ) ( ) ( ) ( ) x x A x B x C = α + β + γ, α + β + γ = 1 (6.1) y y B y C y C x A x B x C α x y A y B y C β = y. (6.2) 1 1 1 γ 1 5.30 α = 1 x x B x C y y D B y C, β = 1 x A x x C y D A y y C, γ = 1 D 1 1 1 1 1 1 x A x B x C D = y A y B y C 1 1 1 x A x B x y A y B y 1 1 1, (6.3)

6 : 35 A A γ > 0 P β > 0 γ > 0 β < 0 P B α > 0 B α > 0 C C (a) (b) 6.1: P (a) P ABC (a) P ABC 3 A : (x A, y A ), B : (x B, y B ), C : (x C, y C ) (x, y) (α, β, γ) (6.3) (α, β, γ) (x, y) (6.1) (6.1) 6.1 ABC (1/3, 1/3, 1/3) 6.2 P (α, β, γ) A, P BC D B, P CA E C, P AC F 6.1 α : β : γ = P BC : P CA : P AB (6.4) 6.1 ABC ABC (α, β, γ) (area coordinages) 6.2 6.1 (x, y) ABC α 0, β 0, γ 0 α > 0, β > 0, γ > 0 6.2 (x, y) BC, CA, AB α = 0, β = 0, γ = 0 α < 0 (x, y) BC A β < 0 CA B γ < 0 AB C 6.1 6.1, 6.2 (6.3) (α, β, γ) 1.1

6 : 36 β = 0 α > 0 β < 0 γ < 0 γ = 0 α = 0 α > 0 β > 0 γ < 0 B A α > 0 β > 0 γ > 0 α > 0 β < 0 γ > 0 α < 0 β > 0 γ < 0 α < 0 β > 0 γ > 0 C α < 0 β < 0 γ > 0 6.2: BC, CA, AB α = 0, β = 0, γ = 0 6.2 n r r (subspace) r (affine space) r (flat) 3 0 1 2 3 3 n n 1 (hyperplane) n N n N r 1,..., r N c 1 x 1 + + c N x N (6.5) c 1 + + c N = 1 (affine combination) r 1,..., r N r 1,..., r N (6.5) c 1 + + c N = 1 c 1 0,..., c N 0 (convex conbination) r 1,..., r N (convex hull) r 1,..., r N (convex set) 2 (6.1) 6.1 3 3 n (general position) n + 1 n 6.2 n + 1 n (simplex) 0 1 2 3

6 : 37 - A A - B (α, β, γ ) (α, β, γ ) C - C B 6.3: Ā B C ABC 6.4: 6.2 Ā B C ABC Ā B C (α, β, γ) ABC (α, β, γ) 6.3 ( x, ȳ) (x, y) 1 6.2 x = a 11 x + a 12 ȳ + a 13, y = a 21 x + a 22 ȳ + a 23 (6.6) 2 (affine transformation) (5.14) 6.3 6.4 (6.6) (5.18) x a 11 a 12 a 13 x y = a 21 a 22 a 23 ȳ (6.7) 1 0 0 1 1 (6.6), (6.7) ( x, ȳ) (x, y)

6 : 38 ABC (x, y) 1. (x, y) ABC (α, β, γ) ( (6.3)) 2. α 0, β 0, γ 0 Ā B C (α, β, γ) ( x, ȳ) ( (6.1)) 3. ( x, ȳ) (x, y) Ā B C ABC (texture mapping) 6.3 Ā B C ( x, ȳ) ABC (x, y) (x, y) ( x, ȳ) R G B (x, y) (6.6), (6.7) ( x, ȳ) (x, y) 1 (x, y) 2 (x, y) ( x, ȳ) ( x, ȳ) 4 ( x, ȳ) (i, j) ξ = x i, η = ȳ j (i, j) I(i, j) ( x, ȳ) 6.4 I( x, ȳ) = (1 ξ)(1 η)i(i, j) + ξ(1 η)i(i + 1, j) + (1 ξ)ηi(i, j + 1) + ξηi(i + 1, j + 1) (6.8)

6 : 39 (i, j) η 1-η (i, j+1) ξ 1-ξ (i+1, j) η 1-η (i+1, j+1) 6.5: I(i, j) I(i, j + 1) η : 1 η I(i + 1, j) I(i + 1, j + 1) η : 1 η ξ : 1 ξ I(i, j) I(i, j + 1) η : 1 η I(i + 1, j) I(i + 1, j + 1) η : 1 η ξ : 1 ξ 6.5 ξ : 1 ξ η : 1 η 1 1 1 (bilinear interpolation) 3 3 6.6(a) 3 6.6(b) 6.6(a) 6.6(b) 6.6(a) 3 6.4 (rendering)

6 : 40 3 (smooth shading) 3 3 CAD 3 (computer vision) 3 3 (3D reconstruction) 6.3 (5.13) (projective transformation, homography) 1 1 x = h 11x + h 12 y + h 13 h 31 x + h 32 y + h 33, ȳ = h 21x + h 22 y + h 23 h 31 x + h 32 y + h 33 (6.9) 6.7 (x, y), ( x, ȳ) X : Y : Z, X : Ȳ : Z 5.6 x = X/Z, y = Y/Z, x = X/ Z, ȳ = Ȳ / Z (5.17) X h 11 h 12 h 13 X Ȳ = k h 21 h 22 h 23 Y (6.10) Z h 31 h 32 h 33 Z k 0 6.5 3 3 (projection transformation matrix, homography matrix) (6.9), (6.10) (6.6), (6.7) h 31 = h 32 = 0 3 {a 1, a 2, a 3 } (reciprocal system) {ã 1, ã 2, ã 3 } (a) (b) 6.6: (a) 3 (b) 3

6 : 41 ã 1 = a 2 a 3 a 1, a 2, a 3, ã 2 = a 3 a 1 a 1, a 2, a 3, ã 3 = a 1 a 2 a 1, a 2, a 3 (6.11) 6.3 {a 1, a 2, a 3 } {ã 1, ã 2, ã 3 } (a i, ã j ) = δ ij (6.12) δ ij i = j 1 i 0 0 (3.58), (3.74) (6.12) a 2 a 3 a 2, a 3 2.1 a 1, a 2, a 3 (a 1 a 2, a 3 ) (2.13) a 1, ) a 2, a 3 A = (a 1 a 2 a 3 ã 1, ã 2, ã 3 ) (ã Ã = 1 ã 2 ã 3 (6.12) A Ã = I ( ) ) 6.3 Ã = ã 1 ã 2 ã 3 A = (a 1 a 2 a 3 6.6 Ã = (A ) 1 (= (A 1 ) ) (6.13) ABC Ā B C A, B, C X A : Y A : Z A, X B : Y B : Z B, X C : Y C : Z C Ā, B, C X : Ā Y : ZĀ, X Ā B : Y B : Z B, X C : Y C : Z C {(X A, Y A, Z A ), (X B, Y B, Z B ), (X C, Y C, Z C ) } {( X A, ỸA, Z A ), ( X B, ỸB, Z B ), ( X C, ỸC, Z C ) } 6.4 αβγ 0 α, β, γ X Ā X A H = α Y Ā Ỹ A Z A Z Ā X B + β Y B Z B X B Ỹ B Z B + γ X C Y C Z C X C Ỹ C Z C (6.14) 3 A, B, C 3 Ā, B, C 6.7:

6 : 42 6.7 (6.10) H α, β, γ 6.8 6.9 6.5 α + β + γ = 1 (6.14) (α, β, γ) ABC Ā B C 6.4 (6.14) α = β = γ 6.4 ABCD Ā B C D ABCD Ā B C D 3 3 A, B. C 3 Ā, B. C (6.14) α, β, γ D D 6.6 (6.14) H D D α, β, γ W A = X A X D + ỸAY D + Z A Z D, W B = X B X D + ỸBY D + Z B Z D, W C = X C X D + ỸCY D + Z C Z D (6.15) 1 6.10 X W Ā A X BW B X CW C α Y W Ā A Y BW B Y CW C β = Z W Ā A Z BW B Z CW C γ 6.5 X D Y D Z D (6.16) (6.16) ABCD Ā B C D 4 A, B, C, D 4 Ā, B, C, D 6.3 (6.9) 6.11 Ā B C D, ABCD 4 Ā, B. C, D (xā, y Ā ), (x B, y B ), (x C, y C ), (x D, y D ) 4 A, B. C, D (x A, y A ), (x B, y B ), (x C, y C ), (x D, y D ) X A x A Y A = y A, 1 Z A X B Y B Z B = x B y B 1, X C Y C Z C = x C y C 1,

6 : 43 X Ā Y Ā Z Ā = x Ā y Ā 1, X B Y B Z B = x B y B 1, X C Y C Z C = x C y C 1 (6.17) Ā B C D ABCD (6.17) (6.15) W A, W B, W C (6.16) α, β, γ (6.14) H ABCD (x, y) 1. (x, y) ABCD ( x, ȳ) x x ȳ = Z[H y ] (6.18) 1 1 Z[ ] 3 1 Z[(X, Y, Z) = (X/Z, Y/Z, 1) 2. Ā B C D ( x, ȳ) (x, y) 6.6 5.6 (6.17), (6.18) Z 1 Z[ ] (6.10) k (x, y) ABCD (x, y) ABC BCD 6.1 (6.14) ABC Ā B C Ā B C D ABCD α, β, γ (6.16) D D 6.3 RGB ( x, ȳ) (x, y) ( x, ȳ) 1

6 : 44 (a) (b) 6.8: (a) (b) 3 6.8(b) 3 6.8(a) 6.8(b) 6.8(b) 5.5 5.13 3 6.8(b) 6.8(a) (projection mapping) 6.7 6.8 (calibration) 3 6.2 3 1 2 5.10 5 6m

6 : 45 (a) (b) 6.9: (a) 2 4 (b) 4 4 2 4 4 4 6.9 (image mosaicing) (mosaicing) 6.8 2 4 2 2 6.1. (6.4) 6.2. (6.6) 1 6.3. (6.6) 3 Ā : (xā, yā), B : (x B, y B), C : (x C, y C) 3 A : (x A, y A ), B : (x B, y B ), C : (x C, y C ) a 11, a 12,..., a 23 6.4. 1 (6.8) 6.5. (6.9) (6.10) 6.6. (A ) 1 = (A 1 )

6 46 6.7. (6.14) 3 A, B, C 3 Ā, B, C 6.8. 6.5 6.9. 6.4 6.10. A, B, C, D Ā, B, C, D H (6.14) α, β, γ (6.16) 6.11. (6.9) A : (x A, y A ), B : (x B, y B ), C : (x C, y C ), D : (x D, y D ) Ā : (xā, yā), B : (x B, y B), C : (x C, y C), D : (x D, y D) h 11, h 12,..., h 33 6 6.1 ABC ABC ABC 6.2 1 3

47 6.3 6.4 3 3 3 3 (voxel) CT MRI (volume data) (solid texture) 3 (3D texture) 3

48 [49] 3 [67] 6.4 (video mapping) [69] [71] HMD (virtual reality) (feature point) (Harris operator)[57] SIFT (SIFT operator)[70] (descriptor) RANSAC [56] 4 [67] [67]

49 7 2 7.1 5.3 1 1 (transformation) 1. 2. 3. (group of transformation) xy 7.2 (Euclidean transformation) ( ) x y = ( cos θ sin θ ) ( ) ( sin θ x + cos θ y t 1 t 2 ) (7.1)

7 50 7.1: (rigid motion) (motion) (congruence transformation) (x, y) O θ (t 1, t 2 ) 2 2 7.1 (7.1) x cos θ sin θ t 1 x y = sin θ cos θ t 2 y (7.2) 1 0 0 1 1 (group of Euclidean transformations) (congruent) (Euclidean geometry) O x 1.4 1.4 xy θ (t 1, t 2 ) x y 7.2 xy (x, y) x y (x, y ) (x, y) (x, y ) (7.1) θ (t 1, t 2 ) ( t 1, t 2 ) θ (1.40), (1.41) 1.10

7 51 y y 2 2 1 O 1 2 x 1 O 1 2 x 7.2: 7.3 (similar transformation) ( ) ( x cos θ y = s sin θ ) ( ) ( sin θ x + cos θ y t 1 t 2 ), s 0 (7.3) (x, y) O θ s (t 1, t 2 ) 2 2 7.3 (7.3) x s cos θ s sin θ t 1 x y = s sin θ s cos θ t 2 y, s 0 (7.4) 1 0 0 1 1 (group of similar transformations) s = 1 (similar) (similar geometry) 7.3:

7 52 y y 2 2 1 O 1 2 x 1 O 1 2 x 7.4: xy s θ (t 1, t 2 ) x y 7.4 xy (x, y) x y (x, y ) (x, y) (x, y ) (7.3) 7.1 3 (Euclidean reconstruction) 7.4 (similar transformation) (5.14), (6.6) ( ) ( ) ( ) ( x a 11 a 12 x y = + a 21 a 22 y a 13 a 23 ), a 11 a 22 a 12 a 21 0 (7.5) 2 2 7.5

7 53 7.5: (7.5) x a 11 a 12 a 13 x y = a 21 a 22 a 23 y, a 11 a 22 a 12 a 21 0 (7.6) 1 0 0 1 1 (group of affine transformations) (7.5) s ( 0) s = 1 (affine geometry) xy x y 7.6 xy (x, y) x y (x, y ) (x, y) (x, y ) (7.5) (oblique coordinate system) (orthogonal coordinate system) (Cartesian coordinate sytem) 7.5 N (x 1, y 1 ),..., (x N, y N ) (x 1, y 1 ),..., (x N, y N ) N = 3 6.3 N

7 54 y y 2 2 1 O 1 2 x 1 O 1 2 x 7.6: 7.1 x = 1 N N x α, α=1 ȳ = 1 N N y α, α=1 x = 1 N N x α, α=1 ȳ = 1 N N y α (7.7) α=1 (7.5) x, y, x, y x α, y α, x α, y α (1/N) N α=1 ( ) ( ) ( ) ( ) 1 N x α = 1 N a 11 a 12 x α a 13 + N N a 21 a 22 y α a 23 α=1 y α α=1 ( ) ( ) ( ) ( x a 11 a 12 x ȳ = + a 21 a 22 ȳ a 13 a 23 ( x, ȳ) ( x, ȳ ) ) (7.8) (7.9) x α, y α, x α, y α (7.5) (7.9) ( x α x y α ȳ ) ( ) ( a 11 a 12 = a 21 a 22 x α x y α ȳ α = 1,..., N ( ) ( ) ( ) x 1 x x N x a 11 a 12 x 1 x x N x y 1 ȳ y N = ȳ a 21 a 22 y 1 ȳ y N ȳ ) (7.10) (7.11)

7 55 ( x 1 x x N x y 1 ȳ y N ȳ ) x 1 x y 1 ȳ ( ) ( a 11 a 12 x 1 x x N x = a 21 a 22 y 1 ȳ y N ȳ.. x N x y N ȳ ) x 1 x y 1 ȳ. x N x. y N ȳ (7.12) N ( N α=1 (x α x )(x α x)/n N α=1 (x α x )(y α ȳ)/n N α=1 (y α ȳ )(x α x)/n N α=1 (y α ȳ )(y α ȳ)/n = ( a 11 a 12 a 21 a 22 ) ( N α=1 (x α x) 2 /N N α=1 (y α ȳ)(x α x)/n ) ) N α=1 (x α x)(y α ȳ)/n N α=1 (y α ȳ) 2 /N (7.13) ( ) ( N a 11 a 12 α=1 = (x α x )(x α x)/n ) N α=1 (x α x )(y α ȳ)/n a 21 a N 22 α=1 (y α ȳ )(x α x)/n N α=1 (y α ȳ )(y α ȳ)/n ( N α=1 (x α x) 2 ) /N N 1 α=1 (x α x)(y α ȳ)/n (7.14) N α=1 (y α ȳ)(x α x)/n N α=1 (y α ȳ) 2 /N a 11, a 12, a 21, a 22 a 13, a 23 (7.9) ( ) ( ) ( x = ȳ a 13 a 23 a 11 a 12 a 21 a 22 ) ( ) x ȳ (7.15) (7.14) s s s 2 s 7.2 2 2 7.1 (7.5) (7.6) 7.2 2 0 σ (likelihood) (maximum likelihood estimation) (7.13) {(x α, y α )} (covariance matrix) {(x α, y α )}, {(x α, y α)} (correlation matrix) 7.3

7 56 s s = a 2 11 + a 2 12 + a2 21 + a2 22 2 (7.16) (7.14) s A R A (singular value decomposition) A = U ( ) σ1 0 V (7.17) 0 σ 2 U, V σ 1 σ 2 ( 0) (singular value) R = UV (7.18) σ 1, σ 2 A σ 1 1, σ 2 1 1 R (7.16) (7.18) (7.17), (7.18) 7.6 6.3 (projective transformation, homography) (6.9), (5.13) x = h 11x + h 12 y + h 13 h 31 x + h 32 y + h 33, y = h 21x + h 22 y + h 23 h 31 x + h 32 y + h 33 (7.19) 7.7 7.7:

7 57 (7.19) (5.17) 6.5 X h 11 h 12 h 13 X Ȳ = k h 21 h 22 h 23 Y (7.20) Z h 31 h 32 h 33 Z k 0 (group of projective transformations) (7.19) h 33 = h 32 = 0, h 33 0 (projective geometry) (cross ratio) 5.1 xy x y 7.8 xy (x, y) x y (x, y ) (x, y) (x, y ) (7.19) 5.4 x y (0,0) ( (1,1) ( (, 0), (0, ) ( (1,1) 4 x (, 0) x x x (, 0) (1, 1) x y (0, ) y y y oo y 2 2 1 1 O 1 2 x O 1 2 x oo 7.8: (0, 0) (1, 1) (, 0), (0, ) (, 0), (0, )

7 58 (, 0), (0, ) x, y N (x 1, y 1 ),..., (x N, y N ) (x 1, y 1 ),..., (x N, y N ) N = 4 6.4 6.3 N (7.19) 6.3 2 N 7.3 7.4 7.3 2 2 7.7 7.9 projective affine similar Eculidean identity 7.9:

7 59 (group of translations) (group of rotations) (invariant) (invariance) 4 3 2 2 5.7 5.18 (Felix Christian Klein: 1849 1925) (Erlangen program) 7.5 7.5, 7.6 2 (residual) 7.9 A B 7.10

7 60 class A class B data 7.10: B A B A (degree of freedom) 9 8 6, 4, 3 (overfitting) 0 (geometric model selection) (model selection criterion) J = ( ) + ( ) (7.21) 1 2 2 (penalty term) (penalty term) J AIC(geometric AIC) BIC(geometric BIC) MDL(geometric MDL) 7.1. (7.14), (7.15) 2 a 11,..., a 23 ( ) J = 2 N x ( ( ) ( ) ( α a 11 a 12 x α + N a 21 a 22 y α α=1 y α a 13 a 23 ) ) 2 2/N (7.22)

6 61 7.2. (7.11) (7.14) (7.6) a 11,..., a 23 7.3. (7.19) 6.3 2 N (x 1, y 1 ),..., (x N, y N ) N (x 1, y 1 ),..., (x N, y N ) 7 7.1 7.2 O θ (t 1, t 2 ) (7.1) 2 2 7.1 7.2 7.3 O θ s ( 0) (t 1, t 2 ) (7.3) 2

6 62 7.3 7.4 7.4 1 (7.5) 7.5 7.6 7.5 (x α, y α ) (x α, y α), α = 1,..., N 3 (N = 3) N > (7.14), (7.15) 2 2 7.1

63 7.6 1 (7.19) 4 7.7 7.8 4 4 6.4 6.3 N (> 4) 7.3 7.7 7.9 (7.17), (7.18) [23] [61] [63]

64 [67] 7.9 [58, 59] AIC BIC MDL [60] [64] [62] Triono [72] 2 6.4 2 [68] [66] 3 GPS

65 [56] M. A. Fischler and R. C. Bolles: Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography, Communications of the ACM, 24-6(1981), pp. 381 395. [57] C. Harris and M. Stephens: A combined corner and edge detector, Proceedings of the 4th Alvey Vision Conference, August 1988, Manchester, U.K., pp. 147 151. [58] K. Kanatani: Comments on Symmetry as a Continuous Feature, IEEE Transactions on Pattern Analysis and Machine Intelligence, 19-3 (1997), pp. 246 247. [59] K. Kanatani: Comments on Nonparametric Segmentation of Curves into Various Representations, IEEE Transactions on Pattern Analysis and Machine Intelligence, 19-12 (1997), pp. 1391 1392. [60] K. Kanatani: Geometric information criterion for model selection, International Journal of Computer Vision, 26-2 (1998), pp. 171 189. [61] (2003). [62] K. Kanatani: Uncertainty modeling and model selection for geometric inference, IEEE Transactions on Pattern Analysis and Machine Intelligence, 26-10 (2004), pp. 1307 1319. [63] (2005). [64] K. Kanatani: Geometric BIC, IEICE Transaction on Information & Systems, E93-D-1 (2010), pp. 141 151. [65] Geometric Algebra:, (2014). [66] K. Kanatani and C. Matsunaga: Computing internally constrained motion of 3-D sensor data for motion interpretation, Pattern Recognition, 46-6 (2013), pp. 1700 1709. [67] 3, (2016).

66 [68] AIC A Vol. J83-A-6 (2000), pp. 686 693. [69] Vol. J83-12 (2000), pp. 944 946. [70] D. Lowe: Distinctive image features from scale-invariant keypoints, International Journal of Computer Vision, 60-2 (2004), pp. 91 110. [71] M. Sakamoto, Y. Sugaya, and K. Kanatani: Homography optimization for consistent circular panorama generation, Proceedings of the 2000 IEEE Pacific-Rim Symposium on Image and Video Technology, December 2006, Hsinchu, Taiwan, pp. 1195-1205. [72] I. Triono, N. Ohta and K. Kanatani: Automatic recognition of regular figures by geometric AIC, IEICE Transactions on Information and Systems, E81-D-2 (1998), pp. 246 248.

67 6 7.1. (6.3) α α = 1 x x B x x C x D y y B y y C y 1 0 0 = 1 D x B x x C x y B y y C y = 1 ( ) ( ) xb x xc x D, = 1 P B, P C y B y y C y D 1 2, 3 (3,3) (1.8) 1.1 P B, P C α P BC 2/D β P CA 2/D γ P AB 2/D 1.1 P ABC 6.1(b) 7.2. (6.3) (x, y) (α, β, γ) (x, y) 1 (6.1) (α, β, γ) (x, y) (α, β, γ) 1 ( x, ȳ) (α, β, γ) (x, y) (x, y) (6.6) ( x, ȳ) 1 7.3. Ā, B, C A, B, C (6.6) x A = a 11 x Ā + a 12 y Ā + a 13, y A = a 21 x Ā + a 22 y Ā + a 23, x B = a 11 x B + a 12 y B + a 13, y B = a 21 x B + a 22 y B + a 23, x C = a 11 x C + a 12 y C + a 13, y C = a 21 x C + a 22 y C + a 23 xā y Ā 1 x B y B 1 a 11 a 12 = x A x B, x C y C 1 a 13 x C xā y Ā 1 x B y B 1 a 21 a 22 = y A y B x C y C 1 a 23 y C 1 a 11, a 12,..., a 23 Ā B C 2 6.1 0 7.4. 6.5 I(i, j) I(i, j + 1) η : 1 η I(i + 1, j) I(i + 1, j + 1) η : 1 η

68 ξ : 1 ξ ( ) ( ) I( x, ȳ) = (1 ξ) (1 η)i(i, j) + ηi(i, j + 1) + ξ (1 η)i(i + 1, j) + ηi(i + 1, j + 1) = 1 ξ)(1 η)i(i, j) + ξ(1 η)i(i + 1, j) + (1 ξ)ηi(i, j + 1) + ξηi(i + 1, j + 1) ξ : 1 ξ η : 1 η 7.5. X : Ȳ : Z = x : ȳ : 1 = h 11X/Z + h 12 Y/Z + h 13 : h 21X/Z + h 22 Y/Z + h 23 : 1 h 31 X/Z + h 32 Y/Z + h 33 h 31 X/Z + h 32 Y/Z + h 33 X = h 11 Z + h Y 12 Z + h X 13 : h 21 Z + h Y 22 Z + h X 23 : h 31 Z + h Y 32 Z + h 33 = h 11 X + h 12 Y + h 13 Z : h 21 X + h 22 Y + h 23 Z : h 31 X + h 32 Y + h 33 Z 0 k X = k(h 11 X + h 12 Y + h 13 Z), Ȳ = k(h 21 X + h 22 Y + h 23 Z), Z = k(h31 X + h 13 Y + h 33 Z) (6.10) 7.6. AA 1 = I (A 1 ) A = I (A 1 ) A (A 1 ) = (A ) 1 7.7. A H X A Y A Z A ( = α XĀ Y Ā Z Ā X Ā = α Y Ā Z Ā X A Ỹ A Z A 1 + β + β X B X B Y B Ỹ B Z B Z B X C 0 + γ Y C X B Y B Z B Z C + γ X C Y C Z C X C ) Ỹ C Z C X A Y A Z A 0 (7.23) Ā B, C B, C 7.8. (6.14) H αβγ 0 α, β, γ α + β + γ = 1 (X A, Y A, Z A ) = (x A, y A, 1), (X B, Y B, Z B ) = (x B, y B, 1), (X C, Y C, Z C ) = (x C, y C, 1) (X Ā, ȲĀ, Z Ā ) = (x Ā, y Ā, 1), (X B, Y B, Z ) = (x B, y B, 1), (X C, Y C, Z C) = (x C, y C, 1) H x A y A = α xā y Ā1, H x B y B = β x B y, H x C y C 1 1 B1 1 = γ x C y C1

69 ABC G : (x G, y G ) H Ḡ : (xḡ, y Ḡ ) k 0 x Ḡ x G (x A + x B + x C )/3 yḡ1 = kh y G = kh (y A + y B + y C )/3 = k ( x A x B 3 H y A + y B + y C 1 1 1 1 1 = k ( α xā y 3 Ā1 + β x B y + γ x C y ) B1 C1 x C ) 3 α + β + γ = 1 k = 3 ( ) xḡ xḡ ( ) ( ) ( ) xā x = α + β B x + γ C yā y B y C (6.1) α, β, γ Ḡ Ā B C 7.9. H Ḡ (α, β, γ) (1, 1, 1) (α, β, γ) = (1, 1, 1) G Ḡ A, B, C, G Ā, B, C, Ḡ A, B, C A, B, C, G Ā, B, C, Ḡ A, B, C, G Ā, B, C, Ḡ H (α, β, γ) = (1, 1, 1) α + β + γ = 1 α, β, γ α = β = γ 7.10. H D D X D X D Y D = kh Y D Z D k 0 H (6.14) α, β, γ k (6.14) X D Y D Z D Z Ā Z D ( = α XĀ X A Y Ā Ỹ A + β X B X B Y B Ỹ B + γ Z Ā Z A Z B Z B X Ā X B X C = α Y Ā W A + β Y B W B + γ Y C W C (6.15) (6.16) Z B 7.11. (6.9) 1 Z C X C Y C Z C X C ) Ỹ C Z C X D Y D Z D h 11 x + h 12 y + h 13 = h 31 xx + h 32 xy + h 33 x

70 A, B, C, D Ā, B, C, D h 11 x A + h 12 y A + h 13 = h 31 x A x A + h 32 x A y A + h 33 x A h 11 x B + h 12 y B + h 13 = h 31 x B x B + h 32 x B y B + h 33 x B h 11 x C + h 12 y C + h 13 = h 31 x C x C + h 32 x C y C + h 33 x C h 11 x D + h 12 y D + h 13 = h 31 x D x D + h 32 x D y D + h 33 x D (6.9) 2 h 21 x + h 22 y + h 23 = h 31 ȳx + h 32 ȳy + h 33 ȳ A, B, C, D Ā, B, C, D h 21 x A + h 22 y A + h 23 = h 31 ȳ A x A + h 32 ȳ A y A + h 33 ȳ A h 21 x B + h 22 y B + h 23 = h 31 ȳ B x B + h 32 ȳ B y B + h 33 ȳ B h 21 x C + h 22 y C + h 23 = h 31 ȳ C x C + h 32 ȳ C y C + h 33 ȳ C h 21 x D + h 22 y D + h 23 = h 31 ȳ D x D + h 32 ȳ D y D + h 33 ȳ D 1 x A y A 1 0 0 0 x A x A x A y A h 11 x A x B y B 1 0 0 0 x B x B x B y B h 12 x B x C y C 1 0 0 0 x C x C x C y C h 13 x C x D y D 1 0 0 0 x D x D x D y D h 21 0 0 0 x A y A 1 ȳ A x A ȳ A y A h 22 = h 33 x D ȳ A 0 0 0 x B y B 1 ȳ B x B ȳ B y B h 23 ȳ B 0 0 0 x C y C 1 ȳ C x C ȳ C y C h 31 ȳ C 0 0 0 x D y D 1 ȳ D x D ȳ D y D h 32 ȳ D 0 h 11, h 12,..., h 33 h 33 = 1 0 h 33 = 0 0 h 11, h 12,..., h 32 7.1. (7.22 J = 2 N N ( ) ( ) a11 a ( 12 xα + a 22 y α α=1 a 21 ( a13 7 a 23 ) ( x α y α a 13 J = 1 N ( ) ( ) a11 a ( 12 xα + a 13 N a 21 a 22 y α = 1 N α=1 ) ( ) ( ) ( ) ( ) a11 a, 12 xα a13 x + α a 21 a 22 y α a 23 y α ) ( a13 N (a 11 x α + a 12 y α + a 13 x α) α=1 a 23 ) ( x α y α ) ( ) 1, ) 0

71 a 23 J = 1 N (a 21 x α + a 22 y α + a 23 y a 23 N α) α=1 0 ( ) ( ) a11 a 12 x + a 22 ȳ a 21 ( a13 a 23 ) ( ) ( ) x 0 ȳ = 0 (7.9) (7.9) J J = 2 N N ( a11 a ( 12 α=1 a 21 a 22 ) ( xα x y α ȳ ) a 11 J = 1 N ( a11 a ( 12 a 11 N a 21 a 22 = 1 N α=1 ( x α x y α ȳ ) ( xα x y α ȳ ) ) ( ) ( ) a11 a, 12 xα x a 21 a 22 y α ȳ ( x α x y α ȳ ), ( 1 0 0 0 ( x α x ) ( ) xα x ) y α ȳ N (a 11 (x α x) 2 + a 12 (x α x)(y α ȳ) (x α x )(x α x)) α=1 a 12, a 21, a 12 J a 12 = 1 N J a 21 = 1 N J a 22 = 1 N N (a 11 (x α x)(y α ȳ) + a 12 (y α ȳ) 2 (x α x )(y α ȳ)) α=1 N (a 21 (x α x) 2 + a 22 (x α x)(y α ȳ) (y α ȳ )(x α x)) α=1 N (a 21 (x α x)(y α ȳ) + a 22 (y α ȳ) 2 (y α ȳ )(y α ȳ)) α=1 0 ( ) ( N a11 a 12 α=1 (x α x) 2 ) N /N α=1 (x α x)(y α ȳ)/n a 21 a N 22 α=1 (x N α x)(y α ȳ)/n α=1 (x α x) 2 /N ( N α=1 (x α x )(x α x))/n ) N α=1 (x α x ( ) )(y α ȳ)/n 0 0 N α=1 (y α x )(x α x)/n = N α=1 (y α x )(y α ȳ)/n 0 0 (7.13) y α ȳ 7.2. (x α, y α ), (x α, y α), α = 1,..., N (7.6) x 1 x N a 11 a 12 a 13 x 1 x y 1 y N N = a 21 a 22 a 23 y 1 y N 1 1 0 0 1 1 1 x 1 x x 1 y 1 1 N y 1 y N... = a 11 a 12 a 13 a 21 a 22 a 23 x 1 x N x 1 y 1 1 y 1 y N... 1 1 x N y N 1 0 0 1 1 1 x N y N 1 N N α=1 x αx α /N N α=1 x αy α /N x N α=1 y αx α /N N α=1 y αy α /N ȳ = a N 11 a 12 a 13 α=1 a 21 a 22 a 23 x2 α/n N α=1 x αy α /N x N α=1 x ȳ 1 0 0 1 x αy α /N N α=1 y2 αn ȳ x ȳ 1 ) )

72 N a 11 a 12 a 13 α=1 x αx α /N N α=1 x αy α /N x N a 21 a 22 a 23 = N α=1 0 0 1 y αx α /N α=1 N x2 α/n N α=1 x αy α /N x α=1 y αy α /N ȳ N α=1 x αy α /N N α=1 y2 αn ȳ x ȳ 1 x ȳ 1 7.1 J = 2 N x α y α a 11 a 12 a 13 a 21 a 22 a 23 x α y α 2 N α=1 1 0 0 1 1 7.3. (x α, y α ), (x α, y α) (7.19) 1 h 11 x α +h 12 y α +h 13 = h 31 x αx α +h 32 x α y α +h 33 x α, h 21 x α +h 22 y α +h 23 = h 31 y αx α +h 32 y αy α +h 33 y α α = 1,... N 1 x 1 y 1 1 0 0 0 x 1x 1 x 1y 1 x 1......... x N y N 1 0 0 0 x N x N x N y N x N 0 0 0 x 1 y 1 1 y 1x 1 y 1y 1 y 1......... 0 0 0 x N y N 1 y N x N y N y N y N 2 N 1 N h 11 h 12 h 13 h 21 h 22 h 23 h 31 h 32 h 33 0 0 0 0 = 0 0 0 0 0 h 11 x 1 x N 0 0 h 12 y 1 y N 0 0 h 13 1 1 0 0 h 21 0 0 x 1 x N h 22 0 0 y 1 y N h 23 0 0 1 1 h 31 x 1x 1 x N h 32 x N y 1x 1 y N x N x 1y 1 x N y N y 1y 1 y N y N h 33 x 1 x N y 1 y N x 1 y 1 1 0 0 0 x 1x 1 x 1y 1 x h 11 1 h 12......... h 13 x N y N 1 0 0 0 x N x N x N y N x h 21 N 0 0 0 x 1 y 1 1 y 1x 1 y 1y 1 y 1 h 22 h 23......... 0 0 0 x N y N 1 y N x N y N y h 31 N y N h 32 h 33 2 ( h 11. h 33, M h 11. h 33 ) ( )

73 M N N α=1 x2 α/n α=1 x αy α /N x N α=1 x N αy α /N α=1 y2 α/n ȳ x ȳ 1 0 0 0 M = 0 0 0 0 0 0 N α=1 x αx 2 α/n N α=1 x αx α y α /N N α=1 x αx α /N N α=1 x αx α y α /N N α=1 x αyα/n 2 N α=1 x αy α /N N α=1 x αx α /N N α=1 x αy α /N x 0 0 0 0 0 0 0 0 0 N N α=1 x2 α/n α=1 x αy α /N x N α=1 x αy α /N N α=1 y2 α/n ȳ x ȳ 1 N α=1 y αx 2 α/n N α=1 y αx α y α /N N N α=1 y αx α y α /N N α=1 y αy 2 α/n N N α=1 y αx α /N N α=1 y αy α /N ȳ α=1 y αx α /N α=1 y αy α /N N α=1 x αx 2 α/n N α=1 x αx α y α /N N α=1 x αx α /N N α=1 x αx α y α /N N α=1 x αy 2 α/n N α=1 x αy α /N N α=1 x αx α /N N α=1 x αy α /N x N α=1 y αx 2 α/n N α=1 y αx α y α /N N α=1 y αx α /N N α=1 y αx α y α /N N α=1 y αyα/n 2 N α=1 y αy α /N N α=1 y αx α /N N α=1 y αy α /N ȳ N α=1 (x α 2 + y α 2 )x 2 α/n N α=1 (x α 2 + y α 2 )x α y α /N N α=1 (x α 2 + y α 2 )x α /N N α=1 (x α 2 + y α 2 )x α y α /N N α=1 (x α 2 + y α 2 )yα/n 2 N α=1 (x α 2 + y α 2 )y α /N N α=1 (x 2 α + y α 2 )x α /N N α=1 (x α 2 + y α 2 )y α /N N α=1 (x α 2 + y α 2 )/N (7.19) {h ij } h 2 11 + + h 2 33 = 1 2 ( ) {h ij } M

74 Albert Einstein, 22 affine geometry, 53 affine space, 36 affine combination, 36 affine transformation, 37, 52 group of affine transformations, 53, 22 topology, 32 general position, 36 moving frame, 19 motion, 50 Erlangen program, 59 overfitting, 60 outer product, 18 group of rotations, 59 Gaussian curvature, 22 virtual reality, 48 image mosaicing, 45 catastorophy, 25 AIC geometric AIC, 60 MDL geometric MDL, 60 geometric algebra, 15, 19 BIC geometric BIC, 60 geometric model selection, 60 descriptor, 48 Josiah Willard Gibbs, 19 covariance matrix, 55 Felix Christian Klein: 1849 1925, 59 Hermann Günter Grassmann, 18 Grassmann algebra, 18 Cramer s formula, 34 join, 19 Jan Johan Koenderink, 22, 25 meet, 19 calibration, 44 rigid motion, 50 congruent, 50 congruence transformation, 50 computer vision, 40 maximum likelihood estimation, 55 residual, 59 3 3D texture, 47 3 3D reconstruction, 40 quaternion, 18 SIFT SIFT operator, 48 projective geometry, 57 projective space, 32 projective transformation, homography, 40, 56 projection transformation matrix, homography matrix, 40 group of projective transformations, 57

75 oblique coordinate system, 53 barycentric coordinates, 34 degree of freedom, 60 binormal, 19 smooth shading, 40 total curvature, 22 1 bilinear interpolation, 39 correlation matrix, 55 similar, 51 similar geometry, 51 similar transformation, 51 group of similar transformations, 51 dual line, 19 duality theorem, 19 dual point, 19 dual plane, 19 reciprocal system, 40 solid texture, 47 simplex, 36 hyperplane, 36 orthogonal coordinate system, 53 Cartesian coordinate sytem, 53 texture mapping, 38 tensor calculus, 22 statistical geometry, 22 homogeneous coordinate, 32 moving frame, 19 singular value, 56 singular value decomposition, 56 feature point, 48 convex conbination, 36 convex set, 36 convex hull, 36 René Frédéric Thom, 25 binormal, 19 penalty term, 60 Sir William Rowan Hamilton, 18 Harris operator, 48 video mapping, 48 differential geometry, 22 cross ratio, 57 subspace, 36 invariance, 59 invariant, 59 flat, 36 projection mapping, 44 group of translations, 59 vector calculus, 19 versor, 15 David Orlin Hestenes, 19 penalty term, 60 transformation, 49 group of transformation, 49 voxel, 47 volume data, 47 linet at infinity, 32 point at infinity, 32 planet at infinity, 32 area coordinages, 35

76 mosaicing, 45 model selection criterion, 60 Euclidean geometry, 50 Euclidean reconstruction, 52 Euclidean transformation, 49 group of Euclidean transformations, 50 likelihood, 55 RANSAC, 48 rendering, 39 Benjamin Olinde Rodrigues, 19 Rodrigues formula, 19 Rodrigues formula, 19