[CV] Hartley’s Normalization

Hartley’s Normalization

Hartley's normalization은
Stereo Calibration의 Fundamental Matrix를 구하는데
주로 사용되는 normalization으로
기하학적 좌표들을 다룰 때 수치적 안정성을 확보하기 위해 애용됨.

 

Hartley의 normalization은

• Fundamental Matrix를 constrained linear squares로 구할 때 
• 수치적 안정성을 확보하게 해 줌.

---

1.  수치적 불안정성의 원인

1-1. 큰 수와 작은 수의 혼합

이미지 좌표(u-v coordinates)는 일반적으로 pixel 단위로 측정되므로, 값의 범위가 매우 커지게 됨: 수백에서 수천.

이러한 큰 수와 작은 수가 혼합되면, 컴퓨터로 계산하는 경우 precision 문제로 오차가 발생하여 결과가 정확하지 않음.

---

1-2. 행렬 condition number의 악화 (매우 큰 condition number)

Matrix의 condition number(조건수)는 matrix의 수치적 안정성을 나타냄.

Condition number가 클수록 matrix의 item 중 일부가 약간의 차이가 있을 경우, 전체 결과에 매우 큰 오차로 이어짐.

2022.12.02 - [.../Math] - [Math] ill-posed, well-posed, ill-conditioned, well-conditioned matrix (or problem)

[Math] ill-posed, well-posed, ill-conditioned, well-conditioned matrix (or problem)

 

데이터가 제대로 normalization(정규화)되지 않은 경우,

Fundamental Matrix를 계산할 때 사용되는 matrix의 condition number가 좋지 않기 때문(매우 큰 condition number)에

least squares나 SVD 등을 수행하기 전에 normalization을 하는 게 필요함.

---

2. Normalization의 효과

2-1. Data Scaling (데이터 스케일링)

Normalization은 모든 데이터를 동일한 scale로 변환함.

 

예를 들어,

• 각 점이 origin(원점)에서 평균적으로 동일한 거리에 위치하도록 변환하여
• 큰 수와 작은 수의 혼합으로 인한 수치적 문제를 방지할 수 있음.

---

2-2. Condition Number 개선

Normalization은 matrix의 condition number를 개선하여 계산의 수치적 안정성을 높임.

matrix의 condition number가 작아지면, item의 작은 변화로 인한 에러 증폭이 없어져 결과의 정확도가 향상됨.

---

3. Hartley's Normalization

1997년에 Richard Hartley가 발표한 방법.

주어진 points로 구성된 set을

• 중심 이동 (=좌표 평균을 origin으로)과
• 스케일링을 통해

변환하여 points의 좌표 평균이 origin(원점)에 오고

origin으로부터의 평균 거리가 $\sqrt{2}$가 되도록 수정하는 방법임.

---

3-1. 구체적인 과정

1) 중심 계산:

$$
\bar{x} = \frac{1}{n} \sum_{i=1}^{n} x_i, \quad \bar{y} = \frac{1}{n} \sum_{i=1}^{n} y_i
$$

여기서 $\bar{x}$와 $\bar{y}$는 x좌표와 y좌표의 평균임.

---

2) 평균 거리 계산:

$$
d = \frac{1}{n} \sum_{i=1}^{n} \sqrt{(x_i - \bar{x})^2 + (y_i - \bar{y})^2}
$$

여기서 $d$는 각 점이 중심에서 떨어진 평균 거리임.

---

3) Scaling Factor $s$ 계산:

$$
s = \frac{\sqrt{2}}{d}
$$

이 Scaling Factor 는 변환된 점들의 mean distance 를 $\sqrt{2}$로 만듦.

---

4) Normalization Matrix $\mathbf{T}$ 계산:

$$
\mathbf{T} = \begin{pmatrix}
s & 0 & -s\bar{x} \\
0 & s & -s\bar{y} \\
0 & 0 & 1
\end{pmatrix}
$$

여기서 $\mathbf{T}$는 주어진 점들을 normalization하기 위한 Transform Matrix임.

---

5) 변환 적용:

주어진 점 $(x_i, y_i)$는 다음과 같이 변환됨:
$$
(x_i', y_i', 1)^\top = \mathbf{T} (x_i, y_i, 1)^\top
$$

변환 후의 점 $(x_i', y_i')$는 normalization된 좌표임.

---

4. 예제: Normalization 및 Denormalization 과정

4-1. 주어진 점 집합

이미지 1의 점들:
$$
{(100, 200), (150, 250), (200, 300), (250, 350), (300, 400)}
$$

이미지 2의 점들:
$$
{(110, 210), (160, 260), (210, 310), (260, 360), (310, 410)}
$$

---

4-2. Normalization 과정

1) 중심 계산:

이미지 1:
$$
\bar{x}_1 = \frac{100 + 150 + 200 + 250 + 300}{5} = 200, \quad \bar{y}_1 = \frac{200 + 250 + 300 + 350 + 400}{5} = 300
$$

 

이미지 2:
$$
\bar{x}_2 = \frac{110 + 160 + 210 + 260 + 310}{5} = 210, \quad \bar{y}_2 = \frac{210 + 260 + 310 + 360 + 410}{5} = 310
$$

---

2) 평균 거리 계산:

이미지 1:
$$
d_1 = \frac{1}{5} \sum_{i=1}^{5} \sqrt{(x_i - 200)^2 + (y_i - 300)^2} = \frac{1}{5} (141.42 + 70.71 + 0 + 70.71 + 141.42) = 84.85
$$

 

이미지 2:
$$
d_2 = \frac{1}{5} \sum_{i=1}^{5} \sqrt{(x_i' - 210)^2 + (y_i' - 310)^2} = \frac{1}{5} (141.42 + 70.71 + 0 + 70.71 + 141.42) = 84.85
$$

---

3) Scaling Factor 계산:

이미지 1:
$$s_1 = \frac{\sqrt{2}}{d_1} = \frac{\sqrt{2}}{84.85} \approx 0.0167$$

 

이미지 2:
$$s_2 = \frac{\sqrt{2}}{d_2} = \frac{\sqrt{2}}{84.85} \approx 0.0167$$

---

4) Normalization 행렬 ($\mathbf{T}$) 계산:

이미지 1:
$$
\mathbf{T}_1 = \begin{pmatrix}
0.0167 & 0 & -0.0167 \times 200 \\
0 & 0.0167 & -0.0167 \times 300 \\
0 & 0 & 1
\end{pmatrix} = \begin{pmatrix}
0.0167 & 0 & -3.34 \\
0 & 0.0167 & -5.01 \\
0 & 0 & 1
\end{pmatrix}
$$

 

이미지 2:
$$
\mathbf{T}_2 = \begin{pmatrix}
0.0167 & 0 & -0.0167 \times 210 \\
0 & 0.0167 & -0.0167 \times 310 \\
0 & 0 & 1
\end{pmatrix} = \begin{pmatrix}
0.0167 & 0 & -3.51 \\
0 & 0.0167 & -5.18 \\
0 & 0 & 1
\end{pmatrix}
$$

---

5) Transform 적용:

이미지 1의 첫 번째 점 (100, 200):
$$
(x_1', y_1', 1)^\top = \mathbf{T}_1  (100, 200, 1)^\top = \begin{pmatrix}
0.0167 & 0 & -3.34 \\
0 & 0.0167 & -5.01 \\
0 & 0 & 1
\end{pmatrix}  \begin{pmatrix}
100 \\
200 \\
1
\end{pmatrix} = \begin{pmatrix}
-1.67 \\
-1.67 \\
1
\end{pmatrix}
$$

 

이미지 2의 첫 번째 점 (110, 210):
$$
(x_1'', y_1'', 1)^\top = \mathbf{T}_2  (110, 210, 1)^\top = \begin{pmatrix}
0.0167 & 0 & -3.51 \\
0 & 0.0167 & -5.18 \\
0 & 0 & 1
\end{pmatrix}  \begin{pmatrix}
110 \\
210 \\
1
\end{pmatrix} = \begin{pmatrix}
-1.67 \\
-1.67 \\
1
\end{pmatrix}
$$

---

4-3. Denormalization 과정

Normalization된 Fundamental Matrix $\mathbf{F}'$를 다시 원래 좌표계로 변환하기 위해 denormalization 과정이 필요함. denormalization은 다음과 같이 수행됨:

1. 두 이미지의 normalization matrix $\mathbf{T}_1$과 $\mathbf{T}_2$를 구함.
2. 최종 Fundamental Matrix $\mathbf{F}$는 $\mathbf{F} = \mathbf{T}_2^\top  \mathbf{F}' \mathbf{T}_1$로 계산됨.

$$(\mathbf{T}_2\mathbf{p}')^\top \mathbf{F}' \mathbf{T}_1 \mathbf{p} = \mathbf{p}'^\top \color{red}{\mathbf{T}_2^\top \mathbf{F}' \mathbf{T}_1} \mathbf{p} = \mathbf{p}'^\top \color{red}{\mathbf{F}} \mathbf{p}$$

 

예를 들어, 다음과 같이 normalization된 Fundamental Matrix $\mathbf{F}'$가 있다고 가정함:
$$
\mathbf{F}' = \begin{pmatrix}
0.0001 & 0.002 & -0.3 \\
-0.002 & 0.0001 & 0.1 \\
0.4 & -0.1 & 1
\end{pmatrix}
$$

denormalization matrix $\mathbf{T}_1$과 $\mathbf{T}_2$를 이용하여 최종 Fundamental Matrix $\mathbf{F}$를 계산함:
$$
\mathbf{F} = \mathbf{T}_2^\top  \mathbf{F}'  \mathbf{T}_1
$$

 

각 denormalization 행렬의 전치를 계산함:
$$
\mathbf{T}_2^\top = \begin{pmatrix}
0.0167 & 0 & 0 \\
0 & 0.0167 & 0 \\
-3.51 & -5.18 & 1
\end{pmatrix}
$$

그 다음, $\mathbf{T}_2^\top$와 $\mathbf{F}'$의 곱을 계산함:
$$
\mathbf{T}_2^\top  \mathbf{F}' = \begin{pmatrix}
0.0167 & 0 & 0 \\
0 & 0.0167 & 0 \\
-3.51 & -5.18 & 1
\end{pmatrix}  \begin{pmatrix}
0.0001 & 0.002 & -0.3 \\
-0.002 & 0.0001 & 0.1 \\
0.4 & -0.1 & 1
\end{pmatrix} = \begin{pmatrix}
0.00000167 & 0.0000334 & -0.00501 \\
-0.0000334 & 0.00000167 & 0.00167 \\
0.0149 & -0.0150 & -0.00809
\end{pmatrix}
$$

 

마지막으로, 이 결과를 $\mathbf{T}_1$과 곱하여 최종 Fundamental Matrix $\mathbf{F}$를 얻음:
$$
\mathbf{F} = \begin{pmatrix}
0.00000167 & 0.0000334 & -0.00501 \\
-0.0000334 & 0.00000167 & 0.00167 \\
0.0149 & -0.0150 & -0.00809
\end{pmatrix}  \begin{pmatrix}
0.0167 & 0 & -3.34 \\
0 & 0.0167 & -5.01 \\
0 & 0 & 1
\end{pmatrix} = \begin{pmatrix}
0.000000028 & 0.000000558 & -0.00837 \\
-0.000000558 & 0.000000028 & 0.0028 \\
0.0149 & -0.0150 & -0.00809
\end{pmatrix}
$$

---

5. 전체 알고리즘

1. 두 이미지에서 대응하는 점들의 집합 ${(x_i, y_i)}$와 ${(x_i', y_i')}$를 normalization함.
2. normalization된 점들을 사용하여 Fundamental Matrix $\mathbf{F}'$를 구함.
3. 최종 Fundamental Matrix $\mathbf{F}$는 $\mathbf{F} = \mathbf{T}_2^\top \mathbf{F}'  \mathbf{T}_1$로 계산됨. 여기서 $\mathbf{T}_1$과 $\mathbf{T}_2$는 각 이미지에 대해 구한 normalization 행렬임.