
어떤 사물이 움직이는 사물이라고 정의할 수 있을까?
움직임은 우선 시간이라는 차원이 있기에 존재하는 개념이다.
그렇기에 2차원 영상 기준, 움직이는 영상은 2차원 데이터 + 시간으로 이루어진다.

즉, 시간이 경과했을 때, 특정 픽셀의 변화가 없다면? 해당 픽셀에 해당하는 객체는 움직이는 사물이 아닌 배경이라고 판단하면 되고,
시간이 경과했을 때 픽셀의 변화가 있다면, 해당 픽셀에 해당하는 객체는 움직이는 사물이라고 판단할 수 있을 것이다.

## Background Subtraction

원본 영상에서 배경을 빼는 방식으로 움직이는 사물만을 추출할 수 있다.
즉, 원본 영상에서 배경을 추출하는 영역이 가장 중요한 부분인데, 이 배경을 추출하는 방법을 알아보자.

![231203-153249](/posts/final_08/231203-153249.png)

우선 배경(Background)은 시간에 따른 영상 스택에서 픽셀의 변화가 없거나 매우 천천히 변하는 영역일 것이다.
물론 현실에서는 시간변화에 따른 일조량, 그림자 차이 등등 여러 요소가 있기 때문에 배경을 추출하는 방식에는 정해진 방식이 없다.
그렇기에 지금껏 배운 컴퓨터 비전 지식을 총동원해야 한다.

아무튼 배경을 추출했다면, 원본에서 배경을 뺄 수 있을텐데, 그럼 결과물로 어떤 영상이 나올까?
움직이는 객체(foreground object)와 약간의 노이즈만이 나올 것이다.
이렇게 나온 영상에 대해 절댓값을 취하고(음수가 나올 수 있기 때문) thresholding을 하면 foreground object 만 얻을 수 있을 것이다.

$$
|I(x,y,t) - B(x,y,t)| > Th
$$

이제 특정 시각에서 배경을 추출하는 여러 아이디어를 알아보자.

### Frame Differencing

![231203-154303](/posts/final_08/231203-154303.png)

단순히 이전 프레임의 영상을 배경으로 삼는 것이다.

$$
B(x,y,t) = I(x,y,t-1)
$$

단순해 보이지만, 생각보다 잘 동작한다.

만약 사물의 움직임이 threshold에 걸리지 않을만큼 느려서 인식이 잘 안되는 경우에는 이전 프레임 말고, 10 프레임 이전과 같은 영상을 사용하는 방식을 취할 수도 있다.

### Mean Filter

![231203-154321](/posts/final_08/231203-154321.png)

이전 프레임들의 평균값을 배경으로 사용하는 것이다.

$$
B(x,y,t) = \frac{1}{n} \sum_{i=0}^{n-1}I(x,y,t-i)
$$

### Median Filter

![231203-154402](/posts/final_08/231203-154402.png)

이전 프레임들의 중앙값을 배경으로 사용하는 것이다.

$$
B(x,y,t) = median\{I(x,y,t-i)\}
$$

영상에서 움직임을 감지하는 방법에 대해 알아봅니다.

Motion


## SVD

Singular Value Decomposition은 행렬을 여러 행렬로 분해하는 방법이다.
보통 아래와 같은 기호로 표현한다.

$A = U$ $\sum$ $V^T$

행렬 A는 세 행렬로 분해되는데, 각 행렬이 어떤 특성을 갖는지 알아보자.

![231203-141325](/posts/final_07/231203-141325.png)

우선 SVD된 행렬에서 $U$, $V^T$는 normalize 되어있다.
그리고, $\sum$는 대각 행렬인데, 원소가 내림차순으로 정렬되어 있다.

여기서 대각행렬이 내림차순으로 정렬된다는 특징이 매우 중요한데, 왜 중요한지 아래의 예시를 보며 알아보자.

$$
\begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6
\end{bmatrix} = \\
\begin{bmatrix}
-0.39 & -0.92 \\
-0.92 & 0.39
\end{bmatrix} \times \begin{bmatrix}
9.51 & 0 & 0 \\
0 & 0.77 & 0
\end{bmatrix} \times \begin{bmatrix}
-0.42 & -0.57 & -0.70 \\
0.81 & 0.11 & -0.58 \\
0.41 & -0.82 & 0.41
\end{bmatrix}
$$

여기서 $U$와 $\sum$을 먼저 계산하자.

$$
\begin{bmatrix}
-3.68 & -0.71 & 0 \\
-8.8 & 0.30 & 0
\end{bmatrix} \times \begin{bmatrix}
-0.42 & -0.57 & -0.70 \\
0.81 & 0.11 & -0.58 \\
0.41 & -0.82 & 0.41
\end{bmatrix}
$$

$\sum$이 내림차순 정렬되어 있었기 때문에 $U \sum$의 1열의 값이 크고, 2열은 값이 작은 것을 확인할 수 있다.

이 때, 위 두 행렬 $U \sum$ 와 $V^T$ 의 i열 i행의 원소만을 가지고 $A_{pi}$ 를 만들어보자.

$$
\begin{bmatrix}
{\color{Red} -3.68} & -0.71 & 0 \\
{\color{Orange} -8.8} & 0.30 & 0
\end{bmatrix} \times \begin{bmatrix}
{\color{Red} -0.42} & {\color{Orange} -0.57} & {\color{Orange} -0.70} \\
0.81 & 0.11 & -0.58 \\
0.41 & -0.82 & 0.41
\end{bmatrix} \\
= {\color{Orange} \begin{bmatrix}
{\color{Red} 1.6} & 2.1 & 2.6 \\
3.8 & 5.0 & 6.2
\end{bmatrix}} = A_{p1}
$$

$$
\begin{bmatrix}
-3.68 & {\color{Orange} -0.71} & 0 \\
-8.8 & {\color{Orange} 0.30} & 0
\end{bmatrix} \times \begin{bmatrix}
-0.42 & -0.57 & -0.70 \\
{\color{Orange} 0.81} & {\color{Orange} 0.11} & {\color{Orange} -0.58} \\
0.41 & -0.82 & 0.41
\end{bmatrix} \\
= {\color{Orange} \begin{bmatrix}
-0.6 & -0.1 & 0.4 \\
0.2 & 0 & -0.2
\end{bmatrix}} = A_{p2}
$$

즉, $\sum$의 크기 비율에 맞게 $A$를 $A_{p1}$, $A_{p2}$로 분해할 수 있다.

근데 이걸 왜 했느냐?
A를 6픽셀의 영상이라고 했을 때, A를 2개의 영상으로 분해한 꼴이다.
이 때, 에너지 레벨이 큰 영상부터 작은 영상 순서대로 분해한 것인데, **에너지 레벨이 크다**는 것은 **가장 두드러지는 특징**을 의미한다.
즉, 사람 얼굴을 예로 들면, 위의 partial 영상부터 타원모양, 눈코입 위치, 피부 질감과 같이 큰 특징 순으로 얼굴영상을 분해한 것이다.

위 예시는 2개의 특징으로밖에 분리를 못하였지만, 아래의 예시를 살펴보자.

![231203-143845](/posts/final_07/231203-143845.png)

특징을 300개를 추출했는데, 그 중 상위 10개의 특징들로만 영상을 재구성하였다.
단, 3%만의 특징으로만 영상을 복원했는데, 상당히 원본을 닮을 수 있는 이유는 아래에서 알아보자.

---

## PCA

Principal Component Analysis는 주성분 분석이라고 하는데, 이를 이용하면 고차원 데이터를 저차원 데이터로 차원 축소를 시킬 수 있다.
그런데 그 과정에서 데이터의 손실이 최소화 되도록 하는데, 어떤식으로 최소화 하는지 알아보자.

![231203-145410](/posts/final_07/231203-145410.png)

키, 몸무게로 표현된 2차원 데이터가 있다.
이 데이터를 1차원으로 잘 낮춰보기 위해 PCA를 사용하자.

![231203-145633](/posts/final_07/231203-145633.png)

특정 직선에 수선의 발을 내렸을 때, 평균으로부터 수선의 발 까지의 길이의 제곱의 합이 최대가 되도록 하는 최적의 직선을 찾는다.

![231203-145832](/posts/final_07/231203-145832.png)

그리고, 그 최적의 직선에 수직인 다른 직선을 긋는다.

![231203-150105](/posts/final_07/231203-150105.png)

각 PC축이 전체 데이터를 얼마나 잘 표현하고 있는지 분석하기 위해 회전한다.
여기서 이 회전은 SVD의 $U$ 행렬변환에 해당한다.

![231203-150324](/posts/final_07/231203-150324.png)

그리고 각 축이 데이터를 얼마나 잘 표현하는지에 대한 척도로 평균과 수선의 발까지의 거리의 제곱의 합으로 분석한다.
여기서 분석 결과가 SVD의 $\sum$ 행렬에 해당한다.

만약 PC1이 PC2 보다 압도적으로 전체 데이터를 잘 표현한다면?

![231203-150637](/posts/final_07/231203-150637.png)

PC1 만으로도 전체 데이터를 표현해도 크게 상관 없을 것이다.
따라서 PC2를 사용하지 않음으로써 차원을 낮출 수 있다.

![231203-144044](/posts/final_07/231203-144044.png)

대부분의 주요 특징은 높은 에너지 레벨을 보이고, 사소하고 디테일한 특징은 낮은 에너지 레벨을 보이기 때문에,
SVD에서 상위 몇개의 특징만으로 원본 영상을 비슷하게 재현할 수 있는 것이다.

---

## Face Recognition

이제 기본 배경 지식을 어느정도 알았으니, 얼굴 인식하는 방식에 대해 알아보자.

![231203-150956](/posts/final_07/231203-150956.png)

100x100 pixel의 얼굴 영상은 1만 차원의 하나의 포인트로 대응된다.

![231203-151306](/posts/final_07/231203-151306.png)

즉, 1만개의 특징 중, 얼굴을 표현하는 상위의 특징들로 차원을 축소한다면?
얼굴인 영상만을 인식할 수 있을 것이다.

따라서 PCA를 이용해서 얼굴의 가장 큰 특징벡터(sub-space)를 찾는 방식으로 얼굴 인식을 할 수 있으며,
sub-space는 학습 데이터를 학습을 시켜 얼굴의 eigenvector 들을 구하는 방식으로 진행된다.

![231203-151850](/posts/final_07/231203-151850.png)

얼굴의 특징을 나타내는 eigenvector를 구했다면, 이를 이용해서 여러 얼굴을 만들수도 있다.

![231203-151927](/posts/final_07/231203-151927.png)

이러한 여러 얼굴은 아래의 공식으로 표현할 수 있다.

$$
x_i \approx \mu + a_1 \phi _1 + a_2 \phi _2 + ... + a_k \phi _k
$$

여기서 중요한 점은 특징을 1만개를 사용하여 얼굴을 만든 것이 아니라, k개 만을 가지고 만들었다는 점이다.
즉, 1만 차원의 얼굴 영상을 단 k차원으로 줄여서 파악할 수 있다.

얼굴을 인식하는 방법과 그에 사용되는 선형대수학을 다뤄봅니다.

Face Recognition


## Classifiers

시각, 크기, 밝기 등등의 요소 때문에 사물인식이 어려워진다.
현실적으로는 사물의 특징을 뽑고, 그 특징을 이용해서 분류기를 학습시키는 ML 방식으로 이를 해결한다.
그렇기에 이번엔 어떤 종류의 분류기를 사용하면 어떤 식으로 사물을 구분할 수 있는지에 대한 내용을 중점적으로 다뤄보자.

### K-Nearest Neighbor

![231203-133822](/posts/final_06/231203-133822.png)

일반 Nearest Neighbor 방식은 학습된 분류기에 새로운 Test example이 들어오면, 가장 유클리드 거리상으로 가까운 점의 분류로 분류하는 방식이다.
하지만, 이 방식은 outlier에 대해 취약하기 때문에 k개의 가까운 점들을 찾고, 가장 많은 분류로 분류하는 방식이 K-Nearest Neighbor 방식이다.

한마디로 비슷한 데이터와 같은 부류로 분류가 되는 것인데, 이 때문에 실제로 잘 분류가 되지 않기도 한다.

| Pros | Cons |
|---|---|
| 구현이 간단함 | 차이(거리) 함수를 잘 설계해야 함 |
| 비선형적인 경계에서도 잘 동작함 | 테스트 시간이 오래 걸림 |
| 분류(클래스)가 늘어나도 잘 동작함 ||
| 파라미터가 늘어나도 잘 동작함 ||

### Linear

![231203-134242](/posts/final_06/231203-134242.png)

학습에 사용된 데이터를 가장 잘 분류할 수 있는 선형 함수를 예측하는 방법으로, 입력데이터가 들어왔을 때, 학습된 선형 함수에 의해 분류가 이루어진다.

![231203-134446](/posts/final_06/231203-134446.png)

하나의 선형 함수는 해당 선형 함수가 분류하는 데이터에 대한 일치도를 점수로 표현하게 되는데,
그렇기에 여러 사물을 분류하기 위해서는 사물의 종류만큼의 선형 함수를 학습을 시켜야 한다.

각각의 선형 함수는 다른 함수의 계산 결과에는 영향을 주지 않지만, 학습되는 과정에서는 영향을 주게 된다.

| Pros | Cons |
|---|---|
| 파라미터의 차원이 낮기에 간단한 방식으로 표현됨 | 선형 함수는 2개의 클래스로만 분류 가능 (비선형은 여러개 가능) |
| 테스트가 빠름 | 데이터가 선형적으로 분류가 안될 수 있음 |

---

## Bag of Features

Classifiers와 마찬가지로 특징점을 사용한다.

![231203-135123](/posts/final_06/231203-135123.png)

하지만, 이 방식은 특징점들의 분포를 분석하여 객체를 파악한다는 특징에서 위 방식과 다르게 동작한다.

Bag of Features는 아래와 같은 단계로 객체를 분류한다.

1. 영상의 특징 추출

    영상의 특징을 추출하는 방법은 [**`Feature Detection`**](https://wjlee611.github.io/blog/univ_com-vision/final_03#sift-descriptor) 에서 설명한 방식대로 추출한다.
    여기선 영상의 특징을 128개로 추출했다고 가정하자.

2. 특징을 이용한 학습

    이제 특징을 이용해서 학습을 진행시켜야 하는데, 학습은 아래와 같은 단계를 거치게 된다.

    ![231203-135732](/posts/final_06/231203-135732.png)

    비슷한 특징점들은 비슷한 descriptor를 갖고있다.
    그렇기에 128차원 공간에서 비슷한 위치에 위치하게 될 것이다.

    특징점들의 위치를 모두 저장하고, 이를 클러스터링하여 클러스터의 중앙값을 대푯값으로 지정하면 학습이 완료된다.
    (K-means clustering 방법을 사용하면 된다.)

    ![231203-140110](/posts/final_06/231203-140110.png)

3. 영상 분류

    이제 새로 들어온 영상에 대해 특징점을 추출하고, 이를 학습된 분류기에 넣으면 특징들에 대한 분포 히스토그램이 나오게 된다.

    ![231203-140319](/posts/final_06/231203-140319.png)

    물론, 어떤 히스토그램 분포가 어떤 객체인지 분류하기 위해서는 그 분포 경향 역시 학습을 통한 분류기를 만들어야 한다.

하지만, Bag of Features 방식에는 큰 문제점이 하나 있는게, 영상을 분해한 특징들로만 객체를 파악하기 때문에, 위치와 무관하게 영상을 분류하게 된다.
만약, 위치도 파악하여 영상을 분류해야 한다면, Spatial Pyramids 방식을 사용하면 된다.
간단하게 말해서 영상을 쪼개서 분할된 영상에 대해 각각 Bag of Features 방식을 적용하는 방법이다.

사물을 인식하는 방법을 알아봅니다.

Object Recognition

## Thresholding

에너지 레벨을 thresholding 하는 방식으로 segmentation하는 기법입니다.
영역별로 threshold를 다르게 적용하는 방식도 있지만, 이번엔 전체적으로 같은 threshold 기준을 적용하는 방법을 알아볼 예정입니다.

![231202-151956](/posts/final_05/231202-151956.png)

영상의 에너지레벨들을 을 잘 분할할 수 있는 에너지레벨을 기준으로 threshold를 하면 segmentation이 가능합니다.
그 방법은 아래와 같은 순서로 진행됩니다.

1. 임의로 분할할 에너지레벨 T를 잡음.
2. T를 기준으로 두 영역을 나눔 (between-class variance 관점).
3. 각 영역의 평균을 계산함.
4. 평균의 가운데 값으로 T를 이동.
5. 2~4의 과정을 반복해 T가 특정 위치로 수렴하게 함.

위 방식을 거치면 단순한 영상에 대한 경우에는 segmentation이 가능합니다.

하지만, 약간의 노이즈가 끼거나 그림자가 지는 경우에는 정확하게 segmentation할 수 없을 뿐더러,
단순한 영상이라 하더라도, 초기에 T를 잘 못 설정하면 동작하지 않는다는 한계가 있습니다.

이를 해결하기 위한 몇 가지 방법들을 소개합니다.

### Otsu's Method

between-class variance 관점에서는 가장 최적해를 도출해주는 방식으로 알려져있으며, 수식은 다음과 같습니다.

$$
\sigma _B^2 = P_1(m_1-m_G)^2 + P_2(m_2-m_G)^2
$$

$m_G$는 영상 전체의 평균이고, $m_i$는 threshold에 대한 class i에 대한 평균입니다 (위의 3번에 해당).
$P_i$는 threshold에 대한 class i의 확률로서, 위 식은 에러를 계산할 때 크기를 반영해서 계산한다는 의미입니다.

![231202-153042](/posts/final_05/231202-153042.png)

즉, 영상에서 threshold할 때 큰 객체 뿐만 아니라, 작은 객체역시 threshold 가능합니다.

### Smoothing

노이즈가 있는 영상에 대한 thresholding을 해야할 때 적용해볼 수 있는 방법입니다.

![231202-153204](/posts/final_05/231202-153204.png)

smoothing을 적용하면 threshold가 가능한 수준으로 히스토그램이 변할 수 있습니다.
하지만, 디테일은 약간 뭉게진다는 한계는 있습니다.

### Edge

노이즈도 있고, 매우 작은 영역을 검출해야 하는 경우에는 위의 두 방식 역시 제대로 동작하지 않을 수 있습니다.
그럴 때 시도할 수 있는 방법으로 edge를 이용해서 시도하는 방법입니다.

![231202-153519](/posts/final_05/231202-153519.png)

노이즈가 있는 영상에 대해 gradient를 구하고, threshold(99.7%)를 하여 우상단의 영상을 얻습니다.
이후 원본과 곱연산을 하여 좌하단의 영상을 구하고, 해당 영상에 대해 threshold를 하면 segmentation이 가능합니다.

<tip>
 지금부터 알아보는 내용에는 정형화된 방식이 없습니다.
 상황에 맞는 방식을 사용하는 것이 좋습니다.
 
 예로 들어, 노이즈가 많다? &rarr; smoothing을 해볼까?
 세밀한 특징을 찾아야 한다? &rarr; edge를 구해볼까? 하는 식으로 말이죠.
</tip>

---

## K-means clustering

K-means 군집화 방법은 빅데이터, 인공지능 자료에서도 언급한 바가 있으니, 이론적인 내용은 생략하고, 바로 영상에 적용하는 방법에 대해 알아보겠습니다.

1. 영상을 feature space로 변형한다.
2. feature space 상에서 k-means clustering을 수행한다.
3. 군집화 결과를 본래 영상공간으로 변형한다.

즉, feature space를 어떻게 설계하느냐에 따라 segmentation 되는 방식이 달라지게 됩니다.
우선 간단한 예시로 intensity(에너지 레벨)를 feature space로 사용해 봅시다.

![231202-154403](/posts/final_05/231202-154403.png)

만약, feature space를 RGB값으로 사용한다면? 위와 다른 결과가 나올 것입니다.

하지만, 색상, 에너지레벨만을 이용하는 feature space를 사용하는 경우 문제가 있습니다.
바로, 물리적인 공간이 떨어진 곳도 같은 cluster(segmentation)으로 분류가 된다는 점입니다.

이를 해결하려먼 feature space를 만들 때 intensity + position(x, y)도 함께 묶어 만들어주면, 위치가 크게 떨어져 있으면 다른 cluster로 묶이게 만들 수 있습니다.

![231202-154837](/posts/final_05/231202-154837.png)

그럼에도 불구하고, 위 방식 만으로는 위의 영상을 segmentation 할 수는 없을 것입니다. (사람이 하라해도 힘들 듯...)

이를 개선하기 위해 질감(texture)을 사용하여 feature space를 구성하는 방식을 사용해볼 수 있을 것입니다.

<tip>
 `질감(texture)?`
 
 일종의 패턴으로, 특정 모양의 필터는 특정 모양의 패턴에만 반응하는 것을 이용합니다.
 즉, 필터에 대한 반응성의 정도를 질감이라고 생각하면 될 거 같습니다.
</tip>

![231202-155131](/posts/final_05/231202-155131.png)

예로 들어 위의 24종의 필터에 대한 반응도를 이용해 feature space를 만든다면, feature space는 24차원으로 구성될 것이며, 비슷한 질감인 부분은 비슷한 feature space 영역에 위치하게 되고,
결국, 비슷한 질감은 같은 cluseter로 군집화 될 것입니다.

k-means 방식은 간단하며, 빠르게 계산할 수 있고, feature space를 잘만 설계한다면 아주 잘 동작한 알고리즘처럼 보이지만, k-means 방법 역시 한계가 존재합니다.

- k를 얼마로 설정해야 하는지 모른다.
- 초기값에 민감함.
- outlier에 민감함.

 ![231202-155927](/posts/final_05/231202-155927.png)

- 클러스터를 원형으로만 생성할 수 있음.

 ![231202-155938](/posts/final_05/231202-155938.png)

- 평균을 계산할 수 있다는 전제가 필요함.


---

## Mean shift clustering

이 방식은 Mean shift algorithm을 이용하여 clustering 하는 방법으로, mean shift algorithm은 feature space에서 밀집도가 높은 부분을 찾는 알고리즘 입니다.

![231202-160412](/posts/final_05/231202-160412.png)

1. 초기점을 하나 랜덤으로 설정하고, 탐색 윈도우 W의 크기를 적절히 세팅한다.
2. W의 무게중심을 계산한다.
3. W를 무게중심으로 이동시킨다.
4. W가 움직이지 않을 때까지 반복한다.

![231202-160348](/posts/final_05/231202-160348.png)

간단하게 이해해보자면, 각 feature space의 점들이 밀집도가 높아지는 방향으로 흘러가고, 한 점에서 모이는 점들은 같은 cluster로 분류됩니다.
이러한 특성 때문에 k-means의 한계를 극복할 수 있습니다.

![231202-160450](/posts/final_05/231202-160450.png)

정리하면, k-means는 거리 중심으로 segmentation 했는 반변,
mean shift는 무게 중심이 어디로 이동하지는지를 중심으로 segmentation 을 수행합니다.

mean shift 방식은 아래와 같은 장점이 있습니다.

- 일반적으로 여러 분야에서 사용 가능.
- 모델*이 필요없다. 즉, 어떠한 형태도 잘 클러스터링이 된다.
 *모델: 얼굴을 잘 감지하는 모델, 타원을 잘 감지하는 모델 등등...
- 파라미터가 1개(W 크기)밖에 없기에 단순하며, 그 1개 마저도 정하기 쉽다.
- outlier에 대해서도 잘 동작한다.

물론 W 크기에 종속적으로 동작한다는 단점이 있습니다.

영상을 잘게 구역화(분할)하는 방법을 알아봅니다.

Segmentation


영상을 변환하는 방법은 [**`가상세계 - Matrix and Transformations`**](https://wjlee611.github.io/blog/univ_virtual-worlds/mid_04#2d-linear-transformations)에서 소개했었습니다.
이제 영상이 주어졌을 때 어떻게 위 변환식을 도출하는지에 대한 과정을 살펴보겠습니다.

## Transformation Fitting

![231202-122618](/posts/final_04/231202-122618.png)

영상이 위와 같이 변환된다고 가정해봅시다.
이 때 위의 식에서 하나의 특징점은 아래와 같은 식을 통해 변환된다고 할 수 있습니다.

$$
\begin{bmatrix}
x_i' \\
y_i'
\end{bmatrix} = \begin{bmatrix}
m_1 & m_2 \\
m_3 & m_4
\end{bmatrix} \begin{bmatrix}
x_i \\
y_i
\end{bmatrix} + \begin{bmatrix}
t_1 \\
t_2
\end{bmatrix}
$$

식은 2개, 모르는 미지수는 6개.
즉, 3개의 점에 대한 변환식을 구하면 6개의 미지수($m_i$, $t_1$, $t_2$)를 모두 구할 수 있습니다.

여기서 위 식을 아래와 같이 변환할 수 있는데요,

$$
\begin{bmatrix}
& & ... \\
x_i & y_i & 0 & 0 & 1 & 0 \\
0 & 0 & x_i & y_i & 0 & 1 \\
& & ...
\end{bmatrix} 
\begin{bmatrix}
m_1 \\
m_2 \\
m_3 \\
m_4 \\
t_1 \\
t_2
\end{bmatrix} = \begin{bmatrix}
... \\
x_i' \\
y_i' \\
...
\end{bmatrix}
$$

특징점 변환식 하나 당 `...` 부분에 식이 들어갑니다.
위 식을 $MP = X$ 라고 합시다.
그렇다면, 특징점이 5개라면 식이 10개가 만들어져 $M$은 10by6 행렬이 만들어지는 것이죠.

참고로, 최소 3개가 필요한 것이고, 더 많은 특징점을 사용한다면 $P$에 대한 오차를 선형대수학을 이용하여 줄일 수 있습니다.

이제 양변에 $M^{-1}$를 취해준다면, $P = M^{-1}X$를 사용하여 미지수 6개를 얻을 수 있습니다.

---

## RANSAC

위의 선형대수학 방식을 이용하여 특징점이 변환되는 pair를 선으로 연결하여 시각화 하면 아래와 같은 모습을 보입니다.

![231202-124547](/posts/final_04/231202-124547.png)

대부분은 맞지만, 몇몇 outlier가 있습니다.
이런 outlier 때문에 선형 변환 P에 오차가 생기기 마련인데요, RANSAC은 이런 outlier를 빼고 예측할 수 있는 방법을 제공합니다.

RANSAC은 아래의 방식을 통해 outlier의 영항을 제거하고, inlier로만 예측하도록 도와줍니다.

1. 랜덤으로 특징점을 선택한다.
    운이 좋다면 피팅이 잘 될 것이고, 운이 좋지 않다면 잘 안될 것이다.

    참고로, 좋은 피팅의 경우에는 랜덤 선택되지 않은 특징점에 대해서도 에러가 작을 것이고, outlier에 대해서만 에러가 클 것이다.

    ![231202-125407](/posts/final_04/231202-125407.png)

2. 렌담으로 선택된 특징점을 이용해서 Transformation을 구한다.

    ![231202-125425](/posts/final_04/231202-125425.png)

3. 구한 Transform(P)에 대해서 에러를 계산하여 inlier를 찾아본다.

    ![231202-125458](/posts/final_04/231202-125458.png)

4. inlier의 개수가 충분히 크다면 그 inlier를 이용해서 더 정밀한 Transformation을 구한다.

    ![231202-125538](/posts/final_04/231202-125538.png)

5. 1~3 과정을 반복하며 가장 큰 inlier를 찾도록 개수를 추적한다.

    ![231202-125553](/posts/final_04/231202-125553.png)

    ![231202-125604](/posts/final_04/231202-125604.png)

    ![231202-125613](/posts/final_04/231202-125613.png)

단, 이런 알고리즘의 특성 덕분에 대부분의 데이터가 inlier로 존재하고, 일부 데이터만이 outlier로 존재하는 경우에만 잘 동작합니다.

### calculate trial counts
그렇다면 유효한 fitting을 하기위해 얼마나 많은 비교 연산(시도)을 해야할까?

p를 inlier의 비율이라 하고, s를 시도횟수라고 하자.

이 때, 특징점 k개를 모두 inlier에서만 선택할 확률은 $p^k$이다.
즉, 특징점에 outlier가 포함되는 확률은 $1 - p^k$이다.

이 때, fitting을 하기위해 s번 시도를 하는데, s번 동안 모두 outlier가 포함되어 피팅이 되는 확률은 $(1 - p^k)^s$ 이며, 이 확률은 RANSAC이 실패하여 피팅에 실패할 확률을 의미한다.

따라서 P가 피팅에 성공할 확률이라 한다면 1-P는 피팅에 실패할 확률이란 뜻이고, 아래와 같은 관계식이 도출된다.

$$
1-P = (1 - p^k)^s
$$

$$
s = log(1-P) / log(1-p^k)
$$

예로 들어 90%가 inlier이고(p=0.9), 특징점 샘플의 수는 50개(k=50) 이며, 99.9% 확률로 피팅에 성공(P=0.999)해야 한다고 했을 때,

$$
s = log(1-0.999) / log(1-0.9^{50}) \approx 1337
$$

즉, 약 1300번 정도의 시도를 해야 99.9% 확률로 피팅에 성공할 수 있다는 뜻이다.

영상을 변환하는 방법을 알아봅니다.

Image Transform and RANSAC

영상에서 특징점을 찾고 이를 매칭하는 방식에 대한 기본적인 아이디어는 다음과 같습니다.

1. 흥미로운 포인트를 찾는다.
2. 흥미로운 포인트를 설명하기 위한 벡터를 추출한다.
3. 흥미로운 포인트를 정보 벡터를 이용해서 매칭한다.

이번 포스트에선 그 흥미로운 포인트를 찾는 방식(아이디어)와 정보 벡터를 구하는 방식을 알아보겠습니다.

## Feature Point

특징점을 찾을 때 중요한 요소가 있습니다.

- 같은 특징은 다수의 영상에서 반복적으로 발견되어야 한다.
 영상A와 영상B의 특징점이 다르게 추출되면 매칭이 성립되지 않기 때문입니다.
 또한, 영상의 이동, 회전, 스케일링, 시점에 따른 왜곡, 빛의 변화, 노이즈가 있어도 동일한 특징점을 찾도록 하는게 좋습니다.

- 특징점은 구분되는 설명(description)이 있어야 한다. (위의 벡터)
- 정말 좋은 특징점 일부만 추출해야 하고, 찾는 과정이 효율적이어야 한다.
- 특징점이 가능한 작은 영역에서만 존재해야 한다.
 영상A에서 발견된 특징점(예로 얼굴을 구분하는 특징점들)이 영상B에서는 발견되지 않을 수 있기에 넓게잡지 않고 좁게 잡는것이 좋습니다.

이를 염두에 둔 특징점을 찾는 알고리즘에 대해 알아보겠습니다.

---

## Harris Corner

Harris Corner 방식은 꼭짓점을 특징점으로서 찾는 방법입니다.

![231127-223020](/posts/final_03/231127-223020.png)

꼭짓점임을 알 수 있는 방법은 영상에서의 특정 방향에 대한 변화량을 측정하면 됩니다.

꼭짓점도, 모서리도 아닌 평탄한 부분에서의 x, y 축에 대한 변화량은 작거나 0에 가깝습니다.
반면에 모서리에 해당하는 부분은 x 또는 y 축 둘 중 하나에 대한 변화량만 큽니다.

이것과 대조되게 꼭짓점에 해장하는 부분은 x, y 모든 축에대한 변화량이 클 것입니다.
변화량을 측정하는 함수식은 아래와 같습니다.

$$
E(u,v) = \sum_{{x,y}}^{} W(x,y)[{I(x+u, y+v) - I(x,y)}]^2
$$

여기서 W는 탐색하는 윈도우 함수이고, I는 해당 좌표의 에너지 레벨입니다.
이 때, $(u,v)$는 W가 이동하는 방향 벡터입니다.
즉, $(u,v)$가 90$^{\circ}$ 라면 이상적인 결과가 나올 것입니다.

위 식을 테일러 급수로 근사하면 아래와 같은 식이 도출됩니다.

$$
E(u,v) \approx [u \; v] M \begin{bmatrix}
u \\
v
\end{bmatrix}
$$

여기서 M은 아래와 같습니다.

$$
M = \sum_{{x,y}}^{} W(x,y) \begin{bmatrix}
I_x^2 & I_xI_y \\
I_xI_y & I_y^2
\end{bmatrix}
= \begin{bmatrix}
\lambda_1 & 0 \\
0 & \lambda_2
\end{bmatrix}
$$

여기서 $\lambda_1$, $\lambda_2$는 각각 x, y축 방향으로의 gradient 크기를 의미합니다.

즉, $\lambda_1$, $\lambda_2$의 크기 비교를 통해 Window가 가리키는 부분을 구분할 수 있습니다.

| flat | edge | corner |
|---|---|---|
| $\lambda_1 \approx \lambda_2$ | $\lambda_1 >> \lambda_2$ | $\lambda_1 \approx \lambda_2$ |
| $\lambda_1$, $\lambda_2$: small | $\lambda_1 << \lambda_2$ | $\lambda_1$, $\lambda_2$: large |

그렇다면, 얼마나 커야 corner로 판단할 수 있을까요?

답은 설계하기 나름입니다.
하지만 나름 설계하는 기준은 있습니다.

![231207-234701](/posts/final_03/231207-234701.png)

edge-corner는 아래와 같은 기준으로 판단할 수 있습니다.

$$
\theta = det(M) - \alpha trace(M)^2 = \lambda_1 \lambda_2 - \alpha(\lambda_1 + \lambda_2)^2
$$

즉, 도심같이 복잡해서 아주 큰 특징들만 검출할 필요가 있는 경우에는 $\alpha$를 크게 두어 크다고 판단하는 threshold를 높입니다. (corner영역을 줄임)
반대로, 사막과 같이 미세한 특징도 검출할 필요가 있는 경우에는 $\alpha$를 작게 두어 크다고 판단하는 threshold를 낮춥니다. (corner영역을 늘림)
한마디로 $\alpha$가 커질수록 특징점의 개수가 줄어듧니다.

flat-corner는 $\lambda$의 threshold 크기로 판단합니다.
한마디로 threshold가 커질수록 특징점의 개수가 줄어듧니다.

마지막으로 Harris corner(이하 HC)의 특징을 알아봅시다.

HC는 rotation, transition invariant 합니다.
즉, 영상을 회전시키거나 평행이동 시켜도 동일한 특징점을 찾아낼 수 있습니다.

하지만, scale invariant 하지는 않습니다.
![231127-230442](/posts/final_03/231127-230442.png)

---

## Scale Invariant Keypoint Detection

HC의 개선판으로 Window의 크기(patch size)도 찾아내어 scale invariant하게 특징점을 찾는 방법입니다.

![231127_231400](/posts/final_03/231127_231400.gif)

위 영상은 Window 사이즈에 따른 특정 지점에서의 코너성을 함수로 표현한 것입니다.
그렇가면, 좋은 함수란 무엇을까요?

![231127-231710](/posts/final_03/231127-231710.png)

좋은 함수는 코너성이 최고로 나타나는 지점이 유일하게 결정되는 함수가 좋은 함수라고 판단합니다.
그렇다면 좋은 함수의 예시는 무엇이 있을까요?

### Blob detection in 2D

2D 가우시안의 라플라시안으로, 특정 크기의 원형 영상에만 반응하는 필터입니다.

![231127-232134](/posts/final_03/231127-232134.png)

어떤식으로 반응하는지는 아래의 영상을 보며 이해해봅시다.

![231127_232600](/posts/final_03/231127_232600.gif)

여기서 중요한 2가지 특징이 있습니다.

1. 필터 크기에 맞는 원형 영상에 대해서만 반응을 한다.
2. scale invariant 하게 반응한다.

즉, 특정 픽셀에서 반응값이 클 때의 $\sigma$값을 참고해서 Window 사이즈를 결정하면 Scale Invariant Keypoint Detection 를 구현할 수 있습니다.

참고로 위 영상은 해바라기라서 잘 되는 것이 아닌가? 원형 영상이 없으면 못 감지하는게 아닌가 하실 수 있겠습니다.
하지만, 극단적으로 원형이 아닌 영상이 아니고서야 여러 $\sigma$에 해당하는 Blob 필터가 동시에 반응하는 형식으로 잘 반응합니다.
(예시 영상이 있지만, 혐오스러울 수 있기에 올리진 않겠습니다)

---

## SIFT Descriptor

지금까지 특징점을 찾는 방법을 알아보았다면, 이제는 특징점을 설명하는 방법을 알아봅시다.

Scale Invariant Feature Transform Descriptor는 픽셀별로 그레디언트(방향)을 구하고, 이를 히스토그램으로 정리한 뒤 벡터로 관리하여 정보를 담는 방식입니다.

![231127-233809](/posts/final_03/231127-233809.png)

예로 들어 특징점 주변의 16셀에 대한 방향을 8개의 벡터로 표현한다면, 각 특징점마다 16*8 = 128길이의 Descriptor가 생성될 것입니다.

이 특징은 scale, rotation invariant 하기에 정보로서 이용 가치가 있습니다.

---

마지막으로 매칭은 어떻게 할까요?
... 무식하게 모든 조합에 대해 특징점과 그 descriptor를 비교하면 됩니다.

영상에서 특징점을 찾고 매칭하는 법을 알아봅니다.

Feature Detection and Matching


## Edge Detector

이전에 [**`라플라시안 커널`**](https://wjlee611.github.io/blog/univ_com-vision/mid_05#laplacian) 에서 다뤘던 내용의 연장입니다.

![231125-171834](/posts/final_02/231125-171834.png)

값은 상관없지만, 방향성이 있어야 하며, 합이 0인 커널을 구현하면 해당 방향으로의 line edge를 검출할 수 있습니다.

![231125-172028](/posts/final_02/231125-172028.png)

하지만, 위 영상 I 처럼 극명하게 경계가 정해지는 영상은 드뭅니다.
대부분의 영상은 아래의 가운데 영상처럼 경계가 명확하게 구분되는 편은 아닙니다.

![231125-172325](/posts/final_02/231125-172325.png)

따라서 이런 경우까지 고려하기 위해 2중 미분을 통해 edge를 검출하는 것이 좋습니다.

![231125-172357](/posts/final_02/231125-172357.png)

하지만, 영상에 노이즈가 낀 경우에는 2중 미분을 한다고 해서 edge를 검출할 수 없습니다.

![231125-173158](/posts/final_02/231125-173158.png)

따라서 우선 미분을 하기 전에 smoothing filter를 적용해서 노이즈를 줄인 후 edge를 검출하면 검출 성능이 올라갈 수 있습니다.

물론, smoothing filter를 적용하면 경계 역시 블러될 수 있습니다.
그럼에도 불구하고, 경계는 찾을 수 있습니다.

![231125-173502](/posts/final_02/231125-173502.png)

참고로 미분 역시 컨볼루전으로 간단하게 처리될 수 있기 때문에 아래와 같이 연산 과정을 간략하게 할 수 있습니다.
(e.g. \[1, 0\]을 컨볼루전 하면 미분된 효과를 얻을 수 있습니다.)

![231125-173638](/posts/final_02/231125-173638.png)

이런식으로 경계를 강조한 뒤에 threshold를 하면 edge를 검출할 수 있습니다.

---

## Canny edge detector

Canny edge detector은 위에서 살펴본 기본적인 edge 검출 방식을 개선시킨 방식입니다.

| Edge detector | Canny edge detector |
|---|---|
| 1. smoothing filter (가우시안의 미분) 적용 | 1. smoothing filter (가우시안의 미분) 적용 |
| 2. gradient의 크기만 구함 | 2. gradient의 크기와 뱡향을 구함 |
| | 3. Non-maximum suppression |
| | 4. Hysteresis thresholding |

1, 2번 까지 진행하고 threshold 하는 경우에는 차이가 없습니다.
하지만 3, 4 번의 과정을 추가로 진행하여 더 나은 edge를 검출할 수 있습니다.

### Non-maximum suppression

![231125-181229](/posts/final_02/231125-181229.png)

기존의 방식대로 검출할 경우 gradient의 크기만을 구하기 때문에 검출하는 edge의 두께가 두꺼워지는 문제가 발생합니다.

![231125-181445](/posts/final_02/231125-181445.png)

하지만, Canny 방식은 방향 역시 구하기 때문에 선의 두께를 얇게 만들어주면서 edge를 결정할 수 있습니다.

![231125-182005](/posts/final_02/231125-182005.png)

그러나, 여전히 약한 edge가 존재하는 문제가 있습니다.

### Hysteresis thresholding

약한 edge는 주면의 edge와 linking 하는 방식으로 해결하게 됩니다.

![231125-182203](/posts/final_02/231125-182203.png)

그렇게 하기 위해 일단 Low, High threshold를 우선 정합니다.
이후에 threshold시 아래와 같은 판단을 거쳐 edge를 확정합니다.

- threshold 값이 Low 보다 낮다?
  edge가 아님.

- threshold 값이 high 보다 크다?
  edge임.

- threshold 값이 Low, High 사이이다?
  약한 edge임. 따라서 양 쪽에 edge가 있을 경우에만 edge로 판단.

이렇게 진행된 Canny 방식은 확실히 이전보다 나은 성능을 보입니다.

![231125-182457](/posts/final_02/231125-182457.png)

참고로, 처음의 가우시안 필터의 세기를 크게 한다면 강한 에지만 살아남게 됩니다.

---

## Hough transform

Hough transform은 line detector 중 하나인데, 그 방식이 피팅(투표)하는 방식으로 좀 특이하다.

![231125-210610](/posts/final_02/231125-210610.png)

우선 영상에서 edge points를 찾아내고, 이후에는 무수히 많은 직선을 그었을 때,
가장 많은 edge points를 지나는 직선이 선택되는 방식이다.

이 때 드는 의문점이 있다.
무수히 많은 직선을 긋는다는게 시간복잡도 상으로 간단하게 구현 가능한걸까?
일반적인 방식으로 영상에 긋는 방식으로는 불가능 할것이다.
하지만, 영상을 변환하는 과정을 거치면 가능해지는데, 그 방식을 살펴보자.

### Hough space

![231125-210859](/posts/final_02/231125-210859.png)

Hough space는 직선의 방정식의 파라미터를 축으로 하는 공간이다.
따라서 영상 공간에서의 직선은 Hough 공간에서는 점으로 표시된다.

![231125-211018](/posts/final_02/231125-211018.png)

반대로 영상 공간에서의 점은?
해당 점을 지나는 직선은 무수히 많을 것이다.
따라서 그 무수히 많은 직선을 Hough 공간상에서 무수히 많은 점으로 찍으면 하나의 직선 형태로 표현될 것이다.

![231125-211151](/posts/final_02/231125-211151.png)

이를 응용해서 무수히 많은 점을 지나는 직선을 찾는 방식은 위 그림과 같다.

영상 공간의 점은 Hough 공간에서 직선으로 표현되기 때문에,
Hough 공간에서의 교점은 영상 공간에서의 모든 점을 지나는 직선이 된다.

하지만, Hough 공간을 확대해보면 실제로 한 점에서 만나는 경우는 드물기 때문에 약간의 근사를 해야하며 거기서 약간의 오차가 발생할 수 있다.

![231125-211441](/posts/final_02/231125-211441.png)

영상에서 경계를 검출하는 방법을 알아봅니다.

Edge Detection

<notice>
 이미지 훼손은 아래와 같은 공식에 의해 이루어졌다는 가정하에 진행됩니다.
 따라서 현실 세계의 훼손을 복원할 때는 제대로 동작하지 않습니다.

 $$
 g(x,y) = h(x,y) * f(x,y) + \eta(x,y)
 $$

 $h$: 훼손 함수
 $\eta$: 노이즈
 
 즉, 이미지를 복원시킨다는 것은 훼손된 영상 $g$에 대해 $h$ 와 $\eta$를 알고 있을 때, 그 영향을 제거하는 방향으로 진행합니다.
</notice>

## Noise Restoration

우선 영상의 노이즈를 줄이는 방식을 알아보겠습니다.

### Noise Model

노이즈를 줄이기 위해서는 노이즈가 어떻게 생겼는지 분석할 필요가 있습니다.
100%는 아니지만, 자연계에서 노이즈가 발생하는 방식은 여러 방식으로 모델링하여 추상화 할 수 있지만, 그 중에 대표적인 노이즈 모델에 대해서만 알아보겠습니다.

1. `Gaussian Noise`

 ![231125-152000](/posts/final_01/231125-152000.png)
 ![231125-152908](/posts/final_01/231125-152908.png)

 Gaussian Noise는 말 그대로 가우시안 분포를 따르는 노이즈 패턴으로 자연계에서 발견할 수 있는 형태를 갖습니다.

2. `Uniform Noise`

 ![231125-153500](/posts/final_01/231125-153500.png)
 ![231125-153644](/posts/final_01/231125-153644.png)

 Uniform Noise는 동일한 확률 분포로 노이즈 패턴을 갖는 형태입니다.

2. `Impulse (Salt-and-Pepper) Noise`
 
 ![231125-154000](/posts/final_01/231125-154000.png)
 $$
 p(z) = \left\{\begin{matrix}
 P_a \; for \; z=a \\
 P_b \; for \; z=b \\
 0 \; otherwise\end{matrix}\right. 
 $$

 Salt-and-Pepper Noise는 일정 확률로 0 또는 255로 노이즈가 생기는 형태입니다.

### Mean filter

Mean filter는 간단하게 말해서 기존에 많이 써왔던 smoothing filter와 동일합니다.
직역하면 평균값 필터 입니다.

$$
\hat{f}(x,y) = \frac{1}{mn} \sum_{(s,t)\in S_{xy}}^{} g(s,t)
$$

즉, 전체적인 노이즈를 뿌옇게 만듦으로서 노이즈를 줄이는 것이기에 가우시안 노이즈에 효과적 입니다.
하지만, 영상의 디테일이 뭉게진다는 한계가 존재합니다.

### Median filter

Median filter는 간단하게 말하면 특정 윈도우 $S$ 내부의 값을 일렬로 정렬했을 때 가운데 값으로 대체하는 필터입니다.
직역하면 중앙값 필터 입니다.

$$
\hat{f}(x,y) = \underset{(s,t)\in S_{xy}}{median} \{g(s,t)\}
$$

즉, 0, 255와 같은 특이값을 중앙값으로 대체할 수 있기 때문에 Salt-and-Pepper 노이즈에 효과적 입니다.
하지만, 특정 윈도우 영역에 노이즈가 우연히 많이 분포하게 될 경우 복원이 불가능 합니다.

### Adaptive Mean filter

Adaptive filter는 기존 필터와 다르게 영상의 특징을 반영하여 영역별로 다르게 필터링을 한다는 특징이 있습니다.

$$
\hat{f}(x,y) = g(x,y) - \frac{\sigma_\eta^2}{\sigma_L^2} (g(x,y) - m_L)
$$

이 수식을 자세히 분석해봅시다.

$\sigma_\eta^2$가 0 이라는 뜻은 노이즈의 분산이 0이라는 뜻입니다. 즉, 노이즈가 없다는 뜻입니다.
이 때의 위 수식의 좌변은 $g(x,y)$만 남게 됩니다.
즉, 노이즈가 없는 영상은 별 다른 변환 없이 통과하게 됩니다.

$\sigma_L^2$가 $\sigma_\eta^2$에 비해 매우 높은 경우는?
노이즈의 분산에 비해 영상 자체의 분산이 매우 크다는 의미입니다.
즉, 영상의 변화율이 크기 때문에 디테일을 살리기 위해 필터($m_L$)의 강도를 매우 약하게 설정해야 한다는 의미입니다.
실제로 $\sigma_\eta^2$/$\sigma_L^2$를 0.1과 같은 작은 값을 넣고 계산하면 필터의 영향력이 10%만 발휘된 변환 영상을 얻을 수 있습니다.

$\sigma_L^2$가 $\sigma_\eta^2$와 같은 경우는?
노이즈의 분산이 원본영상 + 노이즈의 분산과 같다는 의미입니다.
즉, 영상의 변화율이 없다는 의미이므로, 필터를 강하게 해서 디테일을 뭉게도 영향이 없는 상태입니다.
실제로 $\sigma_\eta^2$/$\sigma_L^2$에 1을 넣고 계산하면 100% 필터링된 변환 영상을 얻을 수 있습니다.

이렇듯, 노이즈의 분산($\sigma_\eta^2$)과 원본영상 + 노이즈의 분산($\sigma_L^2$)을 비교하여 필터($m_L$)링 강도를 결정하면, 디테일이 필요한 부분은 필터링을 약하게, 디테일이 필요없는 부분은 필터링을 강하게 하여 노이즈를 줄일 수 있습니다.

### Adaptive Median filter

이 경우엔 수식이 아닌, 일련의 명령어 집합으로 소개가 되어있기에 일단 소개하고 한 줄 한 줄 분석해보도록 하겠습니다.

![231125-163400](/posts/final_01/231125-163400.png)

`Line 1~3`
median이 min, max가 아닌 값이 있다?
&rarr; 주변에 salt, pepper도 있고, 원본 영상도 섞여있다.
&rarr; B에서 후 처리.

`Line 4~6`
median이 min, max값 중 하나라면 해당 부분이 salt, pepper인지, 아니면 원본 영상 자체가 0, 255 값을 갖는건지 알 수 없다.
&rarr; 윈도우 사이즈($S_{xy}$)를 키워서 A 재시도.

`Line 7~9`
픽셀 값이 min, max가 아니다?
&rarr; 노이즈가 아니고 원본 값이다.
&rarr; 원본 영상 그대로 리턴.

`Line 10`
픽셀 값이 min, max값 중 하나라면 해당 부분은 salt, pepper 노이즈일 것.
&rarr; 중앙값 리턴.

---

## Degradation Restoration

### Estimating the Degradation Function

이제 노이즈는 어느정도 제거했다고 가정하고, 훼손 함수 $h$를 추정하는 법을 알아봅시다.
추정만 해낼 수 있다면 이를 역으로 연산하는 과정을 통해서 제거할 수 있기 때문에 추정하는 대표적인 3가지 방식에 대해 알아봅시다.

- Observation

 부분의 H는 전체의 H와 같기 때문에 부분을 잘 선택하고, 노가다(?)를 통한 원본 영상을 만들어내어 그 변환과정(H)을 얻을 수 있다면, 전체 영상에 대한 복원이 가능해집니다.

- Experimentation

 impulse에 대한 H의 response를 보면 그 변환과정(H)을 얻을 수 있습니다.

- Mathematical modeling

### Inverse filter

이제 찾아낸 훼손 함수 H를 기반으로 복원을 해봅시다.
그 전에 앞서 가정했던 이미지 훼손 공식을 푸리에 변환한 식을 살펴봅시다.

$$
G(u,v) = F(u,v)H(u,v) + N(u,v)
$$

노이즈(N)는 앞에서 많이 줄였기에 없다고 가정했을 때 우리가 복원해야 하는 원본 영상 F는 다음과 같이 정의할 수 있습니다.

$$
\hat{F}(u,v) = \frac{G(u,v)}{H(u,v)} = F(u,v) + \frac{N(u,v)}{H(u,v)}
$$

복원이 완벽하게 이뤄질 수는 없기에 $\hat{F}$의 형태로 표현하였습니다.
이 식에서 $\frac{N(u,v)}{H(u,v)}$ 부분을 유심히 살펴봅시다.

![231125-165953](/posts/final_01/231125-165953.png)

보통 노이즈는 모든 주파수 구간에서 동일하게 일어납니다.
하지만, 훼손은 보통 저주파수 영역에서 크게 일어나는 특징이 있습니다. (그렇다네요)

따라서 고주파수 영역에서는 $\frac{N(u,v)}{H(u,v)}$ 값이 매우 커지는,
즉, 노이즈가 부스트되는 현상이 발생하게 됩니다.

![231125-170139](/posts/final_01/231125-170139.png)

따라서 훼손을 줄이는 과정에서 적당히 lowpass 를 해주는 것이 영상 품질을 높이는데 도움이 될 수 있습니다.

훼손된 영상을 최대한 복원해보는 방식에 대해 알아봅니다.

Image Restoration

## Fourier Transform

푸리에 변환을 간단하게 말하면 시간, 공간 도메인의 주기를 갖는 사인파의 합을 주파수 도메인의 함수로의 변환을 말한다.

<tip>
 `도메인 간의 관계`
 
 ![231018-211849](/posts/mid_06/231018-211849.png)
 
 시간 도메인이 길다는 의미는 주파수가 낮다는 뜻이다.
 따라서 푸리에 변환시 저주파수 영역에서 값이 크게 나타난다.
 반대의 경우도 마찬가지.
 
 [**`전에 헷갈렸던 내용`**](https://wjlee611.github.io/blog/univ_com-vision/mid_02#sampling)으로 다시 돌아가서 보면 이해될 것.
</tip>

### Property

이제 영상을 푸리에 변환을 통해 주파수 도메인으로 변화를 시킬건데, 그 결과물을 분석하는 법을 알아보자.

![231018-212424](/posts/mid_06/231018-212424.png)

DC, 즉, 원점에 가까워 질 수록 주파수가 낮은 영역, 멀 수록 주파수가 높은 영역을 나타내는데,
영상에서의 주파수는 변화율이라고 보면 된다.
즉, 주파수가 크다 라는 의미는 영상이 변화하는 부분이 많다는 뜻이다.

![231018-213206](/posts/mid_06/231018-213206.png)

이 변환결과를 보고 이해해보자.

우선 주파수 데이터를 보면 먼 곳이 어둡다.
즉 영상 전체적으로 확확 변하는 부분이 적다는 뜻이다.

그런데 X 모양으로는 밝은 것을 볼 수 있다.
이 뜻은 해당 방향과 수직한 방향으로 변화가 많다는 것을 의미한다.
실제로 원본 영상을 보면 같은 방향으로 홈도 파져있고, 변화가 많은 모습을 확인할 수 있다.

그리고 미세하게 세로 방향으로 점선과 같은 무늬가 있다.
이는 원본 영상에서 가로 방향으로 긴 무언가가 변화가 큼을 의미한다.
실제로 원본 영상에는 가로로 흰 실같은 무언가가 있다.

마지막으로 주파스 데이터 전체적으로 노이즈가 있다.
이는 원본 영상에서도 노이즈가 있다는 뜻이다.

---

## Frequency Domain Filtering

이제 푸리에 변환을 이용해서 주파수 도메인으로 변환된 영상을 이용한 필터링을 해보자.

이 것이 가능한 이유는 LTI System 이기에 가능한 것이다.
LTI System과 푸리에 변환을 이용한 연산의 단순화에 대한 내용은 [**`여기`**](https://wjlee611.github.io/blog/univ_com-vision/mid_02)에서 확인하자.

![231018-214840](/posts/mid_06/231018-214840.png)

앞으로 살펴볼 필터링에 대해 이 영상과 주파수 영상을 사용할 예정이다.
여기서 주파수 영상의 얇은 흰 원 부분은 무시하자.
일종의 $D_0$로 반지름을 나타내는 것인데, 원본 영상을 푸리에 변환 할 경우에는 나오지 않는다.

### Ideal Lowpass Filter

![231018-214145](/posts/mid_06/231018-214145.png)

원본 영상을 푸리에 변환을 하고, 그 주파수 영상에 대해 위 사진의 흰색 영역만 살리고 나머지는 검게 만든 후 다시 역 푸리에 변환을 해볼 것이다.
이 때, 위의 흰색 영역을 보면 낮은 주파수 영역만을 통과시킴을 알 수 있다.
즉, 고주파수 영역, 변화량이 많은 영역을 없앤다는 뜻인데, 변화량이 많은 영역을 없앤다?
즉, 영상을 뿌옇게 만들어 변화량이 적어지도록 하겠다는 의미이다.

정리하면 Lowpass filter를 통과시키면 영상 전반적으로 Smoothing filter처리를 한 결과를 얻을 수 있다.

해당 주파수 필터는 다음과 같이 정의할 수 있는데,

$$
H(u,v) = \left\{\begin{matrix}
1 \;\; if \;\; D(u,v) \leq D_0 \\
0 \;\; if \;\; D(u,v) > D_0 
\end{matrix}\right.
$$

이렇게 이상적으로 0과 1이 나뉘는 필터를 Ideal Lowpass filter라고 부른다.

![231018-215052](/posts/mid_06/231018-215052.png)

상단부터 지그재그 모양으로 $D_0$가 5, 15, 30, 80, 230 값으로 통과시키는 주파수 대역을 점점 늘린 변환 결과이다.

$D_0$ = 5, 즉 매우 낮은 주파수를 갖는 대역만 통과시킨 영상은 영상이 매우 Smoothing 처리된 것을 확인할 수 있다.
이게 무슨 의미냐면 그정도의 낮은 변화율로는 원본 영상의 가파른 변화를 표현하지 못하고,
변환된 영상 정도의 완만한 변화율만 표현 가능하다는 뜻이다.

따라서 $D_0$의 값을 키울수록 높은 변화도 표현 가능해져 점점 영상이 선명해지는 것을 볼 수 있다.
다르게 말하면 **$D_0$ 값이 클수록 필터링 강도가 약해진다**.

이때 주의깊게 볼 점은 변환된 영상에서 뭔가 일렁이는 듯한 노이즈가 생겼다는 점이다.
왜 이런게 생긴걸까?

바로 Ideal filter 특성 때문에 고주파수 영역을 깔끔하게 날려버렸기 때문에 세밀한 변화를 묘사하지 못해 화질이 떨어진 것이다.
이를 개선할 수 없을까?

### Butterworth Lowpass Filter

\'가능.\' 당연히 개선할 수 있다.
주파수 영역을 필터링할 때 적절하게 고주파수 영역을 통과시킨다면 화질 개선이 가능한데, 그 방법이 Butterworth 방식이다.

![231018-215943](/posts/mid_06/231018-215943.png)

약간의 곡률을 추가함으로서 일부 고주파수 영역을 통과시킨다.
이 그래프를 구현하는 식은 다음과 같이 생겼다.

$$
H(u,v) = \frac{1}{1+[D(u,v) / D_0]^{2n}}
$$

실제로 개선이 되었을까?

![231018-220523](/posts/mid_06/231018-220523.png)

Smoothing 효과는 살짝 약해졌지만, 확실이 울렁이는 듯한 노이즈는 제거되었다.
약간의 화질 개선이 이루어 진 것이다.

### Gaussian Lowpass Filter

![231018-220657](/posts/mid_06/231018-220657.png)

$$
H(u,v) = e^{-D^2(u,v)/2D_0^2}
$$

위에 두 필터보다 성능이 좋은 가우시안 필터도 있다.
그런데 Butterworth와 육안으로 구별되는 정도는 아니다.

---

### Highpass Filter

Lowpass는 영상을 뿌옇게 만들었는데, 반대로 Highpass는?
그렇다. 영상을 더 샤프하게 만든다.
정확하게 말하면 변화가 큰 부분만을 남기기에 Laplacian filter와 유사한 기능을 수행한다.

![231018-221102](/posts/mid_06/231018-221102.png)

위에서 부터 차례대로 Ideal, Butterworth, Gaussian Highpass Filter이다.
함수를 구하는 방법은 그저 1에서 Lowpass 함수를 빼주면 된다.
(Butterworth의 경우에는 $D$(분모) 와 $D_0$(분자)의 위치를 변환하면 된다)

![231018-221329](/posts/mid_06/231018-221329.png)

Ideal Highpass의 결과이다.
역시 $D_0$값을 키울수록 필터의 강도가 약해진다.
그렇기에 노이즈 역시 줄어든다.

![231018-221426](/posts/mid_06/231018-221426.png)

같은 필터 강도의 결과이다. 왼쪽부터 차례대로 Ideal, Butterworth, Gaussian Highpass이다.
이번엔 Butterworth와 Gaussian도 육안으로 차이가 난다.
여기서도 마찬가지로 Gaussian filter가 노이즈가 없고 깔끔하다.

주파수 도메인에서의 필터링에 대해 다뤄봅니다.

Filtering in the Frequency Domain


## Kernel

Filtering과 Convolution에 적용할 데이터를 Kernel 이라고 부른다.
즉, 원본 영상에 어떤 커널을 Filtering 혹은 Convolution 하느냐에 따라 다른 출력물이 나오는 것이다.

커널에 적용방식은 뒤에 Filtering과 Convolution에서 다룰 예정이니 참고만 하고 나중에 다시오자.

### Moving Average (Smoothing)

가로, 세로가 N인 배열의 원소가 모두 $1/N^2$ 로 채워진 커널이다.
이 커널을 적용하면 이미지가 뿌옇게 변하게 된다.

### Laplacian

3$\times$3 배열에 중심이 -4, 상하좌우가 1, 나머지가 0으로 채워진 커널이다.
이 커널을 적용하면 이미지 주변부가 강조되고, 중심부는 약화된다.

Laplacian을 적용한 필터를 원본 이미지에서 빼는 방식으로 Sharping Filter를 구현할 수 있다.

### Shift

중심으로부터 n만큼 떨어진 거리에 1, 나머지는 0으로 채우면 Filtering의 경우 해당 방향의 반대 방향으로 영상이 이동한다.
예로 들어 3$\times$3 배열 중 가운데 왼쪽만 1, 나머지는 0인 커널로 영상을 Filtering시 영상은 오른쪽으로 1픽셀 Shift된다.

---

## Filtering

![231017-225146](/posts/mid_05/231017-225146.png)

영상의 주변부의 값을 이용해 변형시키는 과정을 필터링이라고 한다.
필터링 과정은 [**`LTI System`**](https://wjlee611.github.io/blog/univ_com-vision/mid_02#lti-system)에서 이루어진다.

이 필터링은 크게 Correlation Filtering (just Filtering)과 Convolution Filtering (just Convolution)으로 나뉘게 되는데,
두 방식의 차이를 비교해보며 위에서 소개한 두 커널을 적용하면 이미지가 어떤식으로 바뀌는지 알아보자.

### Filtering (Correlation)

$$
g(m,n) = f(m,n) * h(m,n) \\
= \sum_{k=m-a}^{m+a}\sum_{l=n-a}^{n+a}f[k,l]\times h[m-k,n-l]
$$

필터링은 `커널의 변형이 없이` 연산된다.

위 수식을 보면 픽셀별로 주변 $a$만큼의 픽셀의 값을 참고하여 연산이 진행됨을 알 수 있는데, 이를 아래 그림으로 살펴보자.
이 때 사용한 커널은 위에서 언급한 `Moving Average` 커널이다.

![filtering_gif](/posts/mid_05/moving_average_filtering.gif)

위 영상은 커널사이즈가 3$\times$3 ($a=1$)인 Moving Average Kernel을 Filtering 한 결과이다.
전반적으로 화면이 뿌옇게 변하는 영상을 얻을 수 있다.  

### Convolution

$$
g(m,n) = f(m,n) * h(m,n) \\
= \sum_{k=m-a}^{m+a}\sum_{l=n-a}^{n+a}f[k,l]\times h[n-k,m-l]
$$

자세히 보면 h의 **m, n**의 위치가 Filtering과 `반대`이다.
즉, 컨볼루전은 `커널이 대각선 반전`되어 연산된다.

![231018-204207](/posts/mid_05/231018-204207.png)

좌상단은 원본 영상, 우상단은 그 원본 영상에 Laplacian 커널을 Convolution한 결과이다.
좌상단 영상에서 우상단 영상을 빼면 좌하단과 같이 영상의 윤곽선이 선명해지는 Sharping Filter를 구현할 수 있다.
그런데 이게 어떻게 가능한걸까?

이걸 가능케 하기 위해선 우선 사람이 빛을 인지할 때 그 민감도를 인지하는 법을 알아야 한다.

![231018-204430](/posts/mid_05/231018-204430.png)

사람이 밝은 빛을 보다가 어두운 빛을 보면은 원색보다 더 어둡게 느끼고,
어두운 빛을 보다가 밝은 빛을 보면은 원색보다 더 밝게 느끼는 현상이 발생하는데, 이를 이용하는 것이다.

구현할 때 빛의 밝기 `변화`에 초점을 맞춰보자.
변화, 즉, 미분을 이용하는 것이다.

> 밝아진다 &rarr; 기울기가 양의 기울기 &rarr; 기울기가 증가함

그림으로 살펴보자.

![231018-204831](/posts/mid_05/231018-204831.png)

밝기가 감소하기 시작하는 부분의 밝기는 높여주고, 감소가 끝나는 부분의 밝기는 높여주면 선명해지는 효과가 있다.
그런데 2번 미분한 값을 보자.
우리가 원하는 변화량과 정확히 반대의 값을 갖는다.

즉, `2차 미분값을 원본 영상에서 빼주면`, 우리가 원하는 Sharping Filter를 구현할 수 있다.

그런데 영상처리에서 미분계산이 너무 코스트가 크지 않을까 걱정이 된다.

$$
f'(x) = \frac{df}{dx} = \frac{f(x + \Delta x) - f(x)}{x + \Delta x - x}
$$

하지만, 실제로 그렇지 않다.
디지털에서 영상 처리를 할 때는 Quantization를 했기 때문에 $\Delta x$의 매우 작은 값은 1이 된다.
따라서 다음과 같은 식으로 정리된다.

$$
\frac{df}{dx} = f(x + 1) - f(x) \\
{} \\
\frac{d^2f}{dx^2} = f(x + 1) - 2f(x) + f(x - 1) 
$$

이 값은 사실 각각 `h[0, -1, 1]` / `h[1, -2, 1]`의 컨볼루전과 같다.
따라서 1차원 영상의 경우에는 영상에 `h[1, -2, 1]` 커널을 컨볼루전 하면 된다.

2차원은 위 방식을 편미분을 사용하여 비슷한 방식으로 진행하면 된다.
`x에 대한 편미분` + `y에 대한 편미분` 값을 더하면 다음과 같은 3 $\times$ 3 배열이 나오는데, 이 배열을 컨볼루전하면 원하는 Laplacian Filter를 구현할 수 있다.

![231018-210553](/posts/mid_05/231018-210553.png)

## Boundary (Edge)

Filtering 부분에서 gif영상으로 봤을 때 가장자리는 데이터를 채워주지 못했다.
그 이유는 커널 중심을 가장자리 영역으로 잡았을 때, 영상 외부의 값을 참조해야 값을 계산해야 하기 때문이다.

이런 부분에 대한 해결책으로 간단하게 3가지만 알아보자.

![231018-210916](/posts/mid_05/231018-210916.png)

`zero padding` 방식은 없는 영상 영역을 0으로 채우고 하는 간단한 기법이다.

`boundary value repetition`은 최외각 픽셀의 데이터를 반복하여 채우는 간단한 기법이다.

`mirroring`은 마치 거울이 있는것 처럼 픽셀값을 반사하여 채우는 기법이다.

Filtering 과 Convolution 의 동작방식과 차이를 다뤄봅니다.

Filtering and Convolution

## Color

![231017-141752](/posts/mid_04/231017-141752.png)

하얀색 빛은 RGB 색상의 빛을 모두 합칠 때 나타난다는 건 많이들 알고있을 것이다.
하지만, 빛의 삼원색과 색상의 합을 두고는 의문이 든다.
왜 마젠타와 노란색을 섞으면 밝아지는 것이 아닌 어두워지는 걸까.. 하고.

색상이 보인다 라는 것은 사물이 `해당 색상의 빛을 반사`하고 `나머지 색상의 빛을 흡수`하기 때문이다.
마젠타는 RB의 빛의 혼합이다. 즉 Green 색을 흡수한다는 뜻이다.
노랑은 RG의 빛의 혼합이다. 즉 Blue 색을 흡수한다는 뜻이다.
따라서 마젠타와 노랑을 섞은 색은 Green, Blue 색을 흡수한다는 뜻이니 R만 반사할 것이다.
그렇기에 밝아지는게 아닌 어두워져서 Red 색상을 띄게 되는 것이다.

### RGB Model

![231017-142916](/posts/mid_04/231017-142916.png)

RGB 모델은 아주 익숙한 색상 모델이다.
빛의 삼원색인 Red, Green, Blue 색상의 빛의 밝기로 색상을 표현한다.

### HSI Model

![231017-143217](/posts/mid_04/231017-143217.png)

HSI 모델은 생소하지만, 활용성이 뛰어난 색상 모델이다.
Hue, Saturation, Intensity의 3요소로 색상을 표현한다.

`Hue`는 색상을 표현하는 각도로 `색조` 라고도 부른다.
0$\degree$는 Red, 180$\degree$는 Cyan 등 각도 하나만으로 모든 색상을 나타내게 된다.

`Saturation`은 색상의 포함 정도로 `채도` 라고도 부른다.
Saturation값이 클수록 색상을 많이 함유하고 있다는 뜻이다.
따라서 Saturation이 0이 되면 색상이 존재하지 않는, Gray 색상이 되어버린다.

`Intensity`는 빛의 세기를 표현하는 정도로 `강도` 라도도 부른다.
Intensity값이 클수록 빛이 강하다는 뜻이니 흰색에 가까워진다.

### RGB vs HSI

두 모델간의 가장 큰 차이라면 '빛의 밝기가 색상에 영향을 주는 가' 이다.

RGB는 각 채널을 같은 비율로 늘리고 줄이는 방식으로 빛의 밝기를 조절한다.
따라서 빛의 밝기가 변하면 다른 색상이라고 취급된다.

하지만 HSI는 빛의 밝기를 I채널에서 관리한다.
따라서 빛의 밝기가 변해도 같은 색상으로 취급된다. (정확히는 H, S값이 변하지 않는다)

두 모델간 차이를 확인하기 위한 이미지이니 참고하자.

![231017-211125](/posts/mid_04/231017-211125.png)

---

## Pseudocolor Image Processing

흑백 데이터를 사람이 보기 쉽게 컬러로 대응시키는 과정을 의미한다.

### Intensity Slicing

![231017-211341](/posts/mid_04/231017-211341.png)

Intensity 값을 기준으로 다르게 색상일 입히는 방식이다.
Slicing plane을 여러개 두면 여러 색상으로 여러 범위의 색상을 입힐 수도 있다.

![231017-211515](/posts/mid_04/231017-211515.png)

---

## Color Transformations

기본적으로 앞서 배웠던 영상 변환과 같은 공식을 사용해서 변환한다.

$$
g(x,y) = T[f(x,y)]
$$

하지만 수식적인 부분은 뒤로 미뤄두고 어떤 채널을 어떻게 변화하면 영상이 어떻게 변화하는지를 중점적으로 알아보자.

### Intensity

![231017-212214](/posts/mid_04/231017-212214.png)

위 영상은 Intensity만 30% 줄인 영상이다.

![231017-212235](/posts/mid_04/231017-212235.png)

그 결과 RGB 모델은 모든 채널이 30% 감소했지만,
HSI 모델은 I 채널만 30% 감소한 모습을 볼 수 있다.

### Color Complements

![231017-212435](/posts/mid_04/231017-212435.png)

위 영상은 보색으로 색상을 반전시킨 영상이다.
그 결과 RGB 모델은 각 색상 채널이 상하반전된 모습을 취하게 되었다.

HSI 모델은 색상이 반전되었기에,
Hue는 180$\degree$만큼 shift된 모습의 그래프를 보이게 되었고, Intensity 역시 반전되었다.
하지만, S는 역시 변화가 없다.

---

## Tone and Color Correction

이번엔 색상과 밝기 등을 수정하면서 어떻게 하면 영상을 보기좋게 만들 수 있는지 알아보자.

![231017-214520](/posts/mid_04/231017-214520.png)

RGB 채널에 ease 커브를 줄 경우 어두운 부분은 더 어둡게, 밝은 부분은 더 밝게 만들 수 있다.
하지만 역시 밝기만 건드렸기 때문에 H, S값의 변화는 없다.

![231017-214624](/posts/mid_04/231017-214624.png)

전체적으로 너무 밝은 영상의 경우에는 곡률을 아래로 주게 될 경우
영상 톤을 전체적으로 어둡게 바꿀 수 있다.

![231017-214711](/posts/mid_04/231017-214711.png)

반대의 경우도 가능하다.

![231017-215001](/posts/mid_04/231017-215001.png)

색상별로 톤 변화를 줄 수 있다.
이 경우 색상도 바뀐다.

본인 기준 특이하다고 생각되었던건 특정 색상을 어둡게 커브를 줬더니 영상에서는 오히려 해당 색이 많이 보이도록 조정되었다는 점이 인상적이었다.

---

## Color Slicing

특정 색상영역을 추출하는 기법이다.
예로들어 피부색을 추출하고 싶다면, 피부색과 오차범위에 해당하는 색상만을 선택하여 남기는 작업을 수행하게 된다.

특정 영역을 선별하는 공식은 아래 2가지 방법이 있다.

$$
s_i = \left\{\begin{matrix}
0.5 \;\; if[|r_j-a_j| > \frac{W}{2}]_{any \; 1 \leq j \leq n} \\
r_i \;\; otherwise
\end{matrix}\right.
$$

RGB 3채널을 기준으로($n=3$) 픽셀의 색상($r_j$)과 기준값($a_j$)의 차이가 오차범위($W/2$)보다 크면 0.5로 세팅하고,
오차범위 내부, 즉, 추출하고자 하는 색상 영역이면 원색상을 유지한다.

이 때, 허용범위는 RGB 스페이스에서 `정육면체` 모양으로 구성되게 된다.
따라서 실제 원했던 색상영역보다 약간 더(꼭짓점 부분) 색상을 포함할 수 있다.

 

$$
s_i = \left\{\begin{matrix}
0.5 \;\; if\sum_{j=1}^{n}(r_j-a_j)^2 > R_0^2, \\
r_i \;\; otherwise
\end{matrix}\right.
$$

RGB 3채널을 기준으로($n=3$) 픽셀의 색상($r_j$)과 기준값($a_j$)의 차이가 오차범위($R_0$)보다 크면 0.5로 세팅하고,
오차범위 내부, 즉, 추출하고자 하는 색상 영역이면 원색상을 유지한다.

이 때, 허용범위는 RGB 스페이스에서 `구` 모양으로 구성되게 된다.
따라서 실제 원했던 색상영역을 정확하게 표현할 수 있다.

![231017-214142](/posts/mid_04/231017-214142.png)

왼쪽은 첫번째 방법으로, 오른쪽은 두번째 방법으로 Slicing한 영상이다.
더 나아보이는 방식으로 취사선택하면 될 거 같다.

색상과 관련된 용어와 변환을 다뤄봅니다.

Color Image

## Transform Functions

입력 영상에 대해 밝기값(에너지 레벨)의 변화를 가하고 싶다면 단순히 픽셀값의 데이터에 변화를 가하면 된다.

$$
s = T(r)
$$

하지만, 특정 데이터를 어떻게 변화시키는지에 따라 출력 영상이 달라지고, 거기에서 얻을 수 있는 정보도 달라진다.
그 데이터를 변화시키는 기준인 변환 함수의 종류와, 그 결과를 알아보자.

<notice>
 얻을 수 있는 정보가 달라진다는 표현을 사용했는데,
 **강조**하고싶은 정보가 달라진다는 것이지 **실제** 정보량 자체는 변하지 않는다.
 물론 임의로 특정 밝기 영역을 0으로 만든다면 정보량이 줄어들 수는 있다.
 하지만 **물리적인 정보량은 절대 늘어나지 않는다**. (사람 눈에 보기 편하게 바꿀 뿐)
</notice>

### Basic

![231016-212632](/posts/mid_03/231016-212632.png)

이제부터 그래프를 해석하는 능력이 중요해진다.
예로 들어 `Log` 함수를 변환 함수로 선택한다면 `전반적으로 영상이 밝아짐`을 알 수 있어야 한다.
$y=-x$ 형태의 `Negative` 함수를 선택한다면 영상 명암이 아래와같이 `반전`될 것이다.

![231016-213010](/posts/mid_03/231016-213010.png)

### Power-Law (Gamma)

위의 기본 함수로는 세부적으로 변화시키기 힘들것이다.
하지만 아래의 함수를 이용하면 상수값($\gamma$)를 변화시켜 변환을 세부적으로 처리할 수 있게된다.

$$
s = cr^\gamma
$$

감마값이 커질수록 변환된 영상이 어두워지는 특징이 있다.

![231016-213224](/posts/mid_03/231016-213224.png)

감마 함수는 Gamma correction에 자주 사용되곤 하는데,
이게 뭐냐면, 출력 장치의 빛의 세기를 조정해 원본 영상과 같은 영상을 디스플레이 할 수 있도록 하는 과정이다.

![231016-213529](/posts/mid_03/231016-213529.png)

### Piecewise-Linear

선형 커브를 여러 범위로 쪼갠 함수로
특정 범위의 값을 확장하거나, 임의의 값으로 변경할 때 사용한다.

![231016-214238](/posts/mid_03/231016-214238.png)

함수가 좌상단과 같이 주어질 경우 우상단의 이미지가 좌하단의 이미지처럼 변환된다.
특정 범위의 값을 확장시켜 비슷한 레벨의 빛을 분산시켜 차이를 만든 것이다.

$\overline{(r_1,s_1)(r_2,s_2)}$의 기울기를 수직으로 만들면 `Threshold` 함수라고 불리우게 되는데,
그렇게 되면 특정 범위 이하의 빛은 검은색, 이상의 빛은 흰색으로 이분된다.

이러한 처리 기법을 `Contrast Stretching` 라고 부른다.

![231016-214728](/posts/mid_03/231016-214728.png)

이렇게 함수가 주어진 경우에는 영상이 다음과 같이 변환된다.

![231016-214753](/posts/mid_03/231016-214753.png)

특정 부분을 제외한 나머지 영역을 죽이거나, 특정 부분만을 강조할 때 사용하는데,
이런 처리 기법을 `Intensity-Level Slicing` 라고 부른다.

---

## Histogram Processing

<tip>
 `Histogram`
 데이터의 분포를 한 눈에 볼 수 있는 그림 혹은 그래프
</tip>

영상의 에너지 레벨 분포를 알고싶다면 다음과 같은 과정으로 구할 수 있다.

$$
h(r_k) = n_k
$$

여기서 $r_k$는 k번째 gray level(에너지 레벨 0~255)를 나타내고,
$n_k$는 그 에너리 레벨을 갖는 픽셀의 개수를 의미한다.
코드로 구현한다면 다음과 같이 구현할 수도 있을것이다.

```cpp:.cpp
unsigned int Histogram[256] = {0};

for (h=0; h<H; h++) {
 for (w=0; w<W; w++) {
 Histogram[img[w][h]]++;
 }
}
```

하지만 단순 픽셀 수를 세기만 한다면, 매우 큰 영상의 경우 평균적인 빛의 밝기가 어두움에도 값이 크게 나오는 문제가 발생할 수 있다.
따라서 영상 크기에 따라 자료해석의 차이를 없애도록 영상 크기로 나누어 확률로서 일반화하게 된다.

$$
p(r_k) = \frac{n_k}{WH}
$$

이걸 왜 하는건지 알아보기 전에 우선 서로 다른 영상별로 수집된 히스토그램을 살펴보자.

![231016-220848](/posts/mid_03/231016-220848.png)

히스토그램의 분포를 살펴보면 모든 영역에 골고루 분배된 영상이 가장 보기 좋음을 알 수 있다.
그렇다면 히스토그램 분포를 분산시키는게 영상 품질 개선에 도움이 된다는 것을 알게 되었다.

### Equalization

그렇다면 히스토그램 분포를 골고루 분배할 수 있을까?

![231016-221610](/posts/mid_03/231016-221610.png)

결론부터 말하면 이렇게 이상적으로 분배는 불가능하다.
0이었던 데이터를 0과 1로 적절히 분산하는 방법이 없기 때문이다.

![231016-222414](/posts/mid_03/231016-222414.png)

이렇게 구현하는 것이 최선일 것이다.

구현에 있어 중요한 점은 **일정 범위 내**의 변환 전과 변환 후의 `확률 분포는 같아야 한다`는 점이다.
예로 들어 변환 전의 범위 `0~1`은 변환 후의 범위 `0~3`으로 대응되는데, `각 구간의 확률의 합은 동일`함을 알 수 있다.
이 사실을 식으로 일반화 하면 다음과 같아진다.

$$
\sum_{i=0}^{r}p_r(i) = \sum_{i=0}^{s}p_s(i)
$$

이를 연속적인 값으로 표현하기 위해 적분식으로 변환하면 다음과 같아진다.

$$
\int_{0}^{r}p_r(w)dw = \int_{0}^{s}p_s(w)dw
$$

여기서 다시 상기해보자면 $p_r$은 원본 히스토그램 분포(확률 함수)이고, $p_s$는 목표로 하는 히스토그램 분포이다.
이상적인 확률 함수는 다음 그림과 같을 것이다.

![231016-222950](/posts/mid_03/231016-222950.png)

해당 함수는 $p_s = \frac{1}{L-1}$ 로 표현 가능한데 이를 위의 적분식에 대입하면 다음과 같이 정리할 수 있다.

$$
\int_{0}^{r}p_r(w)dw = \int_{0}^{s}p_s(w)dw = \int_{0}^{s}\frac{1}{L-1}dw = \frac{s}{L-1} \\
{} \\
s = T(r) = (L-1)\int_{0}^{r}p_r(w)dw
$$

이제 이 공식을 이용해서 프로그래밍하기 위해 다시 불연속적인 값의 합으로 바꿔보자.

$$
s_k = T(r_k) = (L-1)\sum_{j=0}^{k}p_r(r_j)
$$
($k$는 일정 범위에 해당하는 x축의 값이다.)

이 때, $p_r(r_j)$는 위에서 히스토그램의 확률로서 일반화 한 식을 대입하면 된다.
즉 최종 변환식은 다음과 같다.

$$
s_k = T(r_k) = \frac{L-1}{MN}\sum_{j=0}^{k}n_j \; , \;\; k=0, 1, ..., L-1
$$

아래 표를 기준으로 연습을 해보자.

| $r_k$ | $n_k$ | $p_r(r_k) = n_k/MN$ | s_k
|---|---|---|---|
| $r_0$ = 0 | 790 | 0.19 | $s_0$ = 1.33 &rarr; 1 |
| $r_1$ = 1 | 1023 | 0.25 | $s_1$ = 3.08 &rarr; 3 |
| $r_2$ = 2 | 850 | 0.21 | $s_2$ = 4.55 &rarr; 5 |
| $r_3$ = 3 | 656 | 0.16 | $s_3$ = 5.67 &rarr; 6 |
| $r_4$ = 4 | 329 | 0.08 | $s_4$ = 6.23 &rarr; 6 |
| $r_5$ = 5 | 245 | 0.06 | $s_5$ = 6.65 &rarr; 7 |
| $r_6$ = 6 | 122 | 0.03 | $s_6$ = 6.86 &rarr; 7 |
| $r_7$ = 7 | 81 | 0.02 | $s_7$ = 7.00 &rarr; 7 |
$L=8$

$$
s_0 = T(r_0) = (8-1)\sum_{j=0}^{0}p_r(r_j) = 7 \times 0.19 = 1.33 \\
s_1 = T(r_1) = (8-1)\sum_{j=0}^{1}p_r(r_j) = 7 \times (0.19 + 0.25) = 3.08 \\
$$

즉, $s_0$가 1이기 때문에, $r_0$(0)에 존재하던 에너지 레벨을 1로 올리고,
$s_1$가 3이기 때문에, $r_0$(1)에 존재하던 에너지 레벨을 3로 올리는 과정을 거치면 Equalization을 달성할 수 있다.

이련 변환의 경우 히스토그램과 $T(r)$의 그래프는 다음과 같은 모양을 갖게 된다.

![231016-225134](/posts/mid_03/231016-225134.png)

이런 경우 Equalization을 진행한 영상은 원본 영상에 비해 물리적인 정보량은 줄어들게 된다.
하지만, 사람의 눈으로 보기에는 더 보기 좋은 영상이 된다.

서로 다른 영상에 대해 Equalization을 적용한 예시와 그 $T(r)$ 함수를 살펴보자.

![231016-225624](/posts/mid_03/231016-225624.png)
![231016-225636](/posts/mid_03/231016-225636.png)

여기서 알 수 있는 점은 원본의 히스토그램 분포가 빽빽하게 모여있을 수록 변환된 영상의 히스토그램 분포에 빈공간이 많이 생긴다는 것이다. (정보량의 손실이 많아진다)

### Specification

하지만 히스토그램을 이용한 Equalization이 만능인 것은 아니다.

![231016-225928](/posts/mid_03/231016-225928.png)

이런 영상처럼 너무 극단으로 몰린 경우에 적용한 결과는 다음과 같이 나올 수 있는데,

![231016-230011](/posts/mid_03/231016-230011.png)

이런 경우에는 단순히 $p_s = \frac{1}{L-1}$ 를 사용하여 변환 함수를 구하는 것 보다,
사용자 정의 함수 $p_z$를 만들어서 처리하는게 더 좋은 영상을 만들 수 있다.

![231016-230350](/posts/mid_03/231016-230350.png)

이미지 밝기 변환에 대한 내용을 다뤄봅니다.

Intensity Transformations

## LTI System

Linear Time Invariant System은 다음과 같은 성질을 갖는다.

1. Linear
 선형성을 유지한다.

 <tip>
 `선형성`

 $$
 H[a_if_i(x,y) + a_jf_j(x,y)] \\
 = a_iH[f_i(x,y)] + a_jH[f_j(x,y)] \\
 = a_ig_i(x,y) + a_jg_j(x,y)
 $$
 </tip>

2. Time Invariant
 시간에 대해 불변성을 갖는다.
 즉, 시간이 변해도 delay만 있을 뿐, 동일한 input에 대해 동일한 output을 내보낸다.

### System Response

신호 처리를 위해 신호를 디지털화 한 다음 변환(filter)을 가해서 다시 연속적인 신호로 변환하기 위한 과정을 살펴보자.

![231015-222017](/posts/mid_02/231015-222017.png)

우선 신호를 특정 구간에서 일정한 값으로 근사한다.
그리고 특정 구간에 대해 근사된 데이터에 변환(filter)를 가한다. 
(참고로 filtering에 대해선 추후에 소개할 예정. 지금은 LTI System을 이용해서 신호를 변환하는 과정만 살펴보자.)

그렇게 변환된 데이터를 다시 연속적인 신호로 변환하기 위해선 LTI System에 Pulse를 적용한 결과를 응용하면 된다.

![231015-222538](/posts/mid_02/231015-222538.png)

넓이가 1인 Pulse를 LTI System에 통과시키면 위와 같은 그래프로 변형된다고 하자.
이 때, LTI System은 선형성을 유지하고 시간 불변성을 갖기 때문에 Pulse의 세기가 커지거나, 시간이 shift돼도,
LTI System을 통과해도 그 변화가 유지된다.

그렇기에 위에서 변환된 데이터를 특정 구간에 대해 Pulse라고 생각한다면,
그 데이터를 LTI System에 통과시키면 다음과 같이 변환될 것이다.

![231015-222954](/posts/mid_02/231015-222954.png)

## Convolution

위에서 언급한 Pulse에 대해 단위 시간(T)를 0에 가깝게 보내면 연속적인 신호에 대한 Pulse가 되는데, 이를 Impulse라고 한다.
이런 Impulse를 LTI System에 통과시키면 위에서 봤던 그래프 형태로 나오게 되는데, 이를 임펄스 반응 이라고 하고, $h(t)$ 라고 하자.

![231015-223956](/posts/mid_02/231015-223956.png)

입력 신호 $f$와 출력 신호 $y$는 다음과 같은 관계를 갖게 된다.

$$
y(t) = f(t) * h(t)
$$

즉, LTI System의 출력($y$)은 시스텝의 임펄스 반응($h$)과 입력($f$)의 Convolution이다.

## Fourier Transform

![231015-224927](/posts/mid_02/231015-224927.png)

푸리에 변환의 기본적인 아이디어는 주기적인 어떠한 함수는 모두 sin파 또는 cos파의 합으로 표현(근사)될 수 있다에서 출발한다.

푸리에 변환을 거치면 시간에 대한 함수가 주파수에 대한 함수로 변환되는데,
시간 축이 주파수 축으로 변환된다는 뜻이다.
단적인 예로, 주기가 $2\pi$이고, 크기가 1인 sin함수는 크기가 1이고, $u=1 (2\pi)$인 Impulse 형태로 그려진다.

<tip>
 `푸리에 변환`
 $$
 F(u) = \int_{-\infty}^{\infty} f(x)e^{-i2\pi ux}dx
 $$

 `역 푸리에 변환`
 $$
 f(x) = \frac{1}{2\pi}\int_{-\infty}^{\infty} F(u)e^{iux}dx
 $$
</tip>

그런데 왜 푸리에 변환을 알아야 할까?
바로 푸리에 변환을 사용하면 Convolution 연산이 매우 간단한 형태로 변환되기 때문이다.

$$
G(u) = \int_{-\infty}^{\infty}g(x)e^{-i2\pi ux}dx \\
= \int_{-\infty}^{\infty}\int_{-\infty}^{\infty}f(\tau)h(x-\tau)e^{-i2\pi ux}dx \\
= \int_{-\infty}^{\infty}\int_{-\infty}^{\infty}[f(\tau)e^{-i2\pi u\tau}d\tau][h(x-\tau)e^{-i2\pi u(x-\tau)}dx] \\
= \int_{-\infty}^{\infty}[f(\tau)e^{-i2\pi u\tau}d\tau]\int_{-\infty}^{\infty}[h(x')e^{-i2\pi ux'}dx'] \\ 
= F(u)H(u)
$$

즉, 기존 도메인($x$)에서의 Convolution 연산이 푸리에 변환된 주파수 도메인($u$)에서는 단순 곱셈으로 표현된다.

![231015-230238](/posts/mid_02/231015-230238.png)

따라서 Convolution 연산을 간단하게 하기 위해서는 일단 푸리에 변환 후 곱연산을 수행해서 다시 역 푸리에 변환을 거치는 과정을 수행하는게 좋다.

### Sampling

[**`이전 포스트`**](https://wjlee611.github.io/blog/univ_com-vision/mid_01#aliasing)에서 Sampling이 적으면 Aliasing이 발생한다고 했었는데, 그 이유을 알아보자.

![231015-230835](/posts/mid_02/231015-230835.png)

왼쪽은 시간 도메인 기준으로 입력 신호에 적절하게 샘플링된 Impulse를 Convolution하면 좌하단처럼 샘플링이 이루어진다.
오른쪽은 왼쪽을 푸리에 변환한 결과로 Convolution 대신 곱연산한 결과이다.

~~(본인도 이해는 안되지만)~~ 여기서 중요한 것은 샘플링이 촘촘할 수록
푸리에 변환된 스펙트럼이 듬성듬성 해진다는 점이다.

만약, 샘플링이 적은수가 되었다면 우하단의 입력 신호의 스펙트럼 봉우리(?)가 오버랩될 것이다.
오버랩 되는 경우 원본을 복구할 수 없기에 Aliasing이 발생하는 것이다.

신호 처리에 대한 기초적인 정보입니다.

Singal Processing Fundamentals

## Sampling & Quantization

연속적인 자연계의 현상을 기록하기 위해서는 이미지를 불 연속적인 형태. 즉, 디지털로 변환해야 한다.

예로 들어 이미지의 좌표가 100.32라면? 반올림을 하던지 적당히 100과 같은 불 연속적인 값으로 치환해야 하며,
에너지레벨 역시 이와 같은 방식으로 디지털화 해야한다.

이렇게 자연계의 연속적인(무한한) 값을 `디지털화 하기 위해 유한하게` 자르는 과정을 `Sampling`이라 하고,
무한 소수의 데이터를 `양자화시켜 비트에 저장할 수 있게` 자르는 과정을 `Quantization`라고 한다.

![231015-201653](/posts/mid_01/231015-201653.png)

**좌상단**의 이미지 중에서 $\overline{AB}$ 를 디지털화 해본다면,
**우상단**의 그래프처럼 에너지레벨(빛의 밝기)이 표현될 것이다. (지글지글 거리는 것은 센서의 한계로인한 노이즈)
샘플링을 일정 구간으로 잘라 네모난 점으로 표현하면 **좌하단**의 이미지처럼 될 것이고,
이를 양자화하면 **우하단**의 이미지처렴 변화하여 디지털로 저장할 수 있게 된다.

![231015-202204](/posts/mid_01/231015-202204.png)

이런 방식으로 2차원 이미지를 디지털화 하면 위와 같은 모양이 될텐데,
연속적인 데이터를 불연속적인 데이터로 변환하면서 어쩔 수 없는 데이터의 손실이 발생할 수 있다.

<tip>
 픽셀의 가로축은 x축, 세로축은 y축이며,
 x좌표는 늘 보던 좌표계와 마찬가지로 오른쪽으로 갈 수록 커지지만,
 y좌표는 반대로 내려갈수록 커진다. **(y축 반전 주의)**
 
 M행 N열(M$\times$N)의 이미지는 다음과 같은 배열에 저장할 수 있다.

 $$
 f(x,y) = \begin{bmatrix}
 f(0,0) & f(0,1) & ... & f(0,N-1) \\
 f(1,0) & f(1,1) & ... & f(1,N-1) \\
 ... & ... & ... & ... \\
 f(M-1,0) & f(M-1,1) & ... & f(M-1,N-1) \\
 \end{bmatrix}
 $$
</tip>

### Aliasing

![231015-205116](/posts/mid_01/231015-205116.png)

샘플링을 위 이미지와 같이 극단적으로 적게 할 경우, 조건이 없다면 원본 데이터를 유추할 수 없게 된다.
또는 변화량이 너무 큰 경우에도 위와 같은 Aliasing 현상이 발생할 수 있다.
예로 들어서 선풍기를 영상으로 찍으면 멈춰있는 듯한 현상이 그런 경우이다.

### Quantization Level

![231015-204846](/posts/mid_01/231015-204846.png)

양자화를 얼마나 세밀하게 할지를 Quantization Level이 결정한다.
레벨이 적을수록 듬성듬성 양자화하게 되고(점선 간격이 늘어남), 이는 화질 저하로 이어진다.
하지만 용량은 절약될 것이다.

### Size (Storage bits)

이렇게 저장된 영상의 크기를 구해보자.

<notice>
 이미지의 화질은 M$\times$N으로 가정하고,
 각 픽셀은 0~255, 즉, 8 bits의 에너지 레벨을 갖는다고 가정하자.
</notice>

단색 이미지(Gray Image)의 경우 1픽셀은 8bits가 필요하기에 1byte.
이 픽셀이 M$\times$N개 있으니 M$\times$Nbytes.
컬러 이미지의 경우 RGB 3개의 색상 채널이 있으니 3을 곱해서 M$\times$N$\times$3bytes 가 된다.

위 계산 결과는 하나의 이미지에 대한 사이즈로, 동영상의 경우에는 30프레임의 경우 추가로 30을 더 곱해줘야 할 것이다.

### Saturation

![231015-203543](/posts/mid_01/231015-203543.png)

센서까지 차이가 있던 데이터가 샘플링 과정에서 차이가 없어지는, Saturation 현상이 발생할 수 있다.

### Gray Level

![231015-203931](/posts/mid_01/231015-203931.png)
![231015-203946](/posts/mid_01/231015-203946.png)

Gray Level이 높을 수록 에너지 레벨을 세분화해서 표현할 수 있다.
따라서 디스플레이 장치가 좋지 않아서 Gray Level이 낮을 경우 같은 이미지라도 위 사진처럼 다르게 표현될 수 있다.

## Interpolation

디지털화된 이미지의 사잇값을 적절히 채워 실제 데이터를 추측하는 과정,
또는, 저화질의 영상의 픽셀값을 채워 고화질로 바꾸거나, 영상의 회전, 축소시 픽셀값을 추측하는 과정을 Interpolation 라고 한다.

### Pixel math

보통 아래와 같은 행렬간의 연산 혹은 픽셀별 계산으로 처리된다.

$$
\begin{bmatrix}
a_{11} & a_{12} \\
a_{21} & a_{22} \\
\end{bmatrix}
+
\begin{bmatrix}
b_{11} & b_{12} \\
b_{21} & b_{22} \\
\end{bmatrix}
=
\begin{bmatrix}
a_{11} + b_{11} & a_{12} + b_{12} \\
a_{21} + b_{21} & a_{22} + b_{22} \\
\end{bmatrix}
$$

$$
\begin{bmatrix}
a_{11} & a_{12} \\
a_{21} & a_{22} \\
\end{bmatrix}
\begin{bmatrix}
b_{11} & b_{12} \\
b_{21} & b_{22} \\
\end{bmatrix}
=
\begin{bmatrix}
a_{11}b_{11} + a_{12}b_{21} & a_{11}b_{12} + a_{12}b_{22} \\
a_{21}b_{11} + a_{22}b_{21} & a_{21}b_{12} + a_{22}b_{22} \\
\end{bmatrix}
$$

단, 보통 픽셀값은 0~255 사이의 값을 갖기 때문에, overflow, underflow에 대해 적절하게 처리해줘야 한다.

### Linear

$H[f(x,y)] = g(x,y)$ 와 같은 변환 함수 $H$가 있을 때,
아래의 특성을 만족하면 $H$가 선형이라고 한다.

$$
H[a_if_i(x,y) + a_jf_j(x,y)] \\
= a_iH[f_i(x,y)] + a_jH[f_j(x,y)] \\
= a_ig_i(x,y) + a_jg_j(x,y)
$$

즉 연산 순서에 상관없다면 선형이라 하며, 대부분의 이미지 처리 연산은 선형이다.

### Image Rotation

![231015-212235](/posts/mid_01/231015-212235.png)

특정 픽셀을 $\theta$만큼 반 시계방향으로 회전시킬 경우 아래와 같은 연산을 가해주면 된다.

$$
\begin{bmatrix}
x' \\
y'
\end{bmatrix}
=
R(\theta)
\begin{bmatrix}
x \\
y
\end{bmatrix}
=
\begin{bmatrix}
cos\theta & -sin\theta \\
sin\theta & cos\theta
\end{bmatrix}
\begin{bmatrix}
x \\
y
\end{bmatrix}
$$

하지만, 이 경우에는 원점을 중심으로 회전되기 때문에,
영상을 중심으로 회전시켜야 하는 경우에는 다음과 같은 스탭을 거쳐야 한다.

1. 영상을 중심으로 평행 이동 시킨다.
2. 삼각함수를 이용해 영상을 회전시킨다.
3. 다시 영상을 원위치로 평행 이동 시킨다.

하지만, 위 연산은 선형이기 때문에 각 픽셀별로 아래 하나의 연산으로 처리해도 상관없다.

$$
\begin{bmatrix}
x' \\
y'
\end{bmatrix}
=
\begin{bmatrix}
cos\theta & -sin\theta \\
sin\theta & cos\theta
\end{bmatrix}
\begin{bmatrix}
x - W/2\\
y - H/2
\end{bmatrix}
+
\begin{bmatrix}
W/2\\
H/2
\end{bmatrix}
$$

<notice>
 영상 변환을 하기 위해서는 `변환 후(x, y)`의 좌표를 연산을 통해 `변환 전(x', y')`의 좌표를 구하고,
 그 좌표의 데이터를 가져와 Quantization하여 변환 후의 좌표에 대입하는 과정을 거쳐야 한다.
</notice>

### Image Interpolation

![231015-214108](/posts/mid_01/231015-214108.png)

검은색 input 영상을 흰색 output 영상으로 upscaling하거나, 영상 회전과 같이
변환 후의 영상의 좌표가 픽셀에 정확히 들어가지 않는 경우, 검은색 픽셀값을 이용해 흰색 픽셀값을 추측해야 한다.
추측하는 방식에는 보통 아래와 같은 방법들이 있다.

1. Replication
 이전 픽셀값의 데이터를 그대로 사용하는 방법이다.
2. Nearest Neighbor
 본인과 가까운 픽셀의 데이터를 그대로 사용하는 방법이다.

위 두 방법의 경우 Interpolation은 가능하지만, 이미지 화질의 개선이 이루어지지는 않는다.
적당한 화질 개선을 위해서는 아래의 방법을 고려해볼 수 있다.

3. (Bi)linear Interpolation
 근처 픽셀값을 이용해 평균 데이터를 계산하여 사용하는 방법이다.

![231015-214947](/posts/mid_01/231015-214947.png)

$$
q_1 = (1-a)p_1 + ap_2 \\
q_2 = (1-a)p_3 + ap_4 \\
{} \\ 
q = (1-b)q_1 + bq_2
$$

디지털 이미지에 대한 기초적인 정보입니다.

Digital Image Fundamentals

3학년 2학기 컴퓨터비전 수업 아카이브