이번 강의에서는 훈련 데이터의 스코어에서 우리의 불행(unhapness)을 계량화하는 손실 함수를 정의할 것이다. 또한 로스 함수를 최소화하는 파라미터를 효율적으로 찾는 방법인 최적화(optimization)에 대해서도 다룰 것이다. 저번 시간에 다루었던 데이터를 생각해보자.

손실 함수(Loss function)

손실 함수(loss function)는 위 그림에 설명되어 있는 것과 같이 주어진 예제의 데이터셋에 대해서 현재 분류기(classifier)가 잘 작동하고 있는지 보여주는 역할을 한다.

Multiclass SVM의 loss의 경우 hinge loss를 이용한다 hinge함수는 위에 정의되어 있는 것과 같다. hinge는 지랫대라고 번역이 되는데, 마치 생긴게 지랫대 같이 생겼기 때문이다. 위 그래프는, S~j~ (예측 정답 레이블의 점수)가 주어졌을 때, L~i~와 S~yi~ 간의 그래프이다.

Multiclass SVM Loss의 예제 코드는 위와 같다. 가중치와 이미지의 특징벡터를 곱하면 스코어가 나온다. 그 후, SVM loss의 식대로 계산을 해준다. 이 때, 위의 코드에서 scores - socres[y] + 1은 넘파이에서 브로드캐스팅을 통해 계산되기 때문에, 벡터 계산이 수행된다. 그러면, y위치의 값은 정답 레이블의 위치로, loss 계산에 포함되지 않으므로, 0으로 바꾸어준다. 그후, margin벡터에 있는 모든 loss의 값을 합하면, 최종 로스의 값이 도출된다.

그렇다면, 이 때, L=0으로 만드는 파라미터W의 쌍은 한 쌍 만이 존재할까? 답은 아니다라고 할 수 있다. 왜냐하면 앞에 상수가 곱해져도 값은 0이 나올 수 있다. 밑의 예시를 보자.

Regularization

훈련 데이터를 이용하여 분류기를 훈련시키면 위의 그림과 같이 훈련 데이터에 대해서는 아주 잘 맞는 분류기를 얻어낼 수 있다.

하지만, 테스트 데이터에 대해서는 위 그림과 같이 잘 맞지 않게 된다. 즉, 훈련 데이터에 오버피팅(overfitting)이 발생할 수 있다.

그렇기 때문에 이를 방지하기 위한 방법중 하나가 규제(regularization)이다. 규제를 통하여 가중치가 한쪽으로 치우치는 것을 방지한다.

L1, L2 regularization같은 경우는 가중치의 제곱혹은 양의 값을 로스함수에 더하여, 해당 가중치가 너무커서, 해당 가중치에 분류기가 편중되어있을 경우, 로스함수에 해당 가중치의 값을 더하여 이 가중치 때문에, 마치 손실함수가 커지는것과 같은 효과를 불러일으켜 해당 가중치를 줄이는 방식으로 규제를 하게 된다. 이와 다른 방법으로, dropout, batchnormalization, 등과 같은 방법이 있다고 한다.

위에서 설명한 L2 regularzation의 weight decay의 예시이다. 두 파라미터에 대해서 wx의 값은 모두 1이 나오지만, 규제항을 살펴보면, R(W~1~)=1 이 나오며, R(W~2~)=0.25가 나온다. 이처럼 한쪽으로 쏠리게 되면, 규제항의 값이 크게 나오게 된다.

소프트맥스 분류기(Softmax Classifier)

여태 까지는 분류기를 통해나온 최종적인 스코어를 바로 로스함수에 넣어 이용하였다. 하지만 이번에는 이 점수를 확률값으로써 간주하여 계산하는 분류기를 살펴볼 것이다.

위 그림에서 빨간 박스로 표시되어있는 식이 소프트맥스 식이다. 만약에 우리가 예측을 했을 때, 정답레이블이 제일 첫번째 레이블일 때, y=[1,0,0,0]의 점수로 예측했다면, 사실 소프트맥스값은 높게 나오지 않는다. 왜냐하면 점수의 개념이기 때문에, y=[250,1,2,1]과 같이 나올 때, 소프트맥스를 취해야 확률 값이 높게 측정될 것이다. 그렇기 때문에, 소프트맥스는 정답레이블을 더 잘 예측할 수 있도록 유도할 수 있는 장치가 있다고 생각이 든다.

위의 그림처럼, 소프트맥스를 이용하면 우리가 계산한 스코어를 확률값 처럼 계산할 수 있게 된다. 마지막에 log에 -를 취한 이유는, 사실 cross entropy식의 형태와 같다고 볼 수 있다. 이에 대해서는 후에 살펴보자.

SVM loss와 softmax로스 함수의 계산은 위 그림과 같다.

이때, SVM loss와 softmax loss를비교해보자. 이 때, 한 예를 계산해보면, SVM loss([10,9,9])=0, softmaxLoss([10,9,9])=$\alpha$ 가 나오게 된다. Loss function은 0에 수렴하면 최적이라고 생각하는 함수이다. SVM loss는 클래스간 스코어가 차이가 별로 나지 않음에도 불구하고 이를 최적의 값이라고 판별하는 단점이 존재하게 된다. 반면에 softmax loss는 위에서 말한것 처럼, 예측할 때, 점수의 차이를 크게 벌리기 위하여 노력하는 loss function이라 할 수 있다.

경사하강법(Gradient descent)

위와 같은 산을 내려온다고 생각해보자. 과연 길을 찾아 내려가는게 효율적일까?

첫 번째로, 무작정 길을 찾아 내려가는 무작위 탐색(random search) 방법이 존재한다. 위 코드를 보면, 파라미터가 매 iteration마다 랜덤하게 설정되는 모습을 볼 수 있다.

위 방법의 결과는 어떨까? 정확도가 15.5%밖에는 안된다. CIFAR-10에서 아무것도 안하고 찍기만해도 클래스가 10개이기 때문에 확률이 10%가 나오는것을 감안해보면, 아무것도 안한 것이랑 똑같다.

두 번째 전략은, 경사를 따라 내려가는 방법이다.

경사(slope) 즉, 그라디언트(gradient) 를 따라 내려가는 방법이다. 식은 위와 같다. 그라디언트는 해당 지점에서 가장 가파른 경사를 뜻한다. 그렇기 때문에 이를 찾아 내려가는 것은 해당 시점에서는 밑으로 내려가는 가장 빠른 지점이라는 뜻이된다.

그러면 위 식에 따라 그라디언트를 계산해보자. 우선 0.0001만큼 step을 가보자. 이렇게 파라미터의 벡터중 하나의 원소에 대해서만 진행하는 것은, 실제로 편미분을 통해서 진행이 되기 때문이다. 즉, 이 파라미터가 0.0001 만큼 변할 때, 그라디언트를 계산하는 것이다.

이때는 흔히 수치미분식을 계산해주는 것 처럼 계산을 해주면 그라디언트를 구할 수 있다.

하지만 이와 같이 하나하나씩 계산하는 것은 너무나 느리고 어리석은 방법이라고 할 수 있다. 우리는 이전에 배웠던 미적분학을 통하여 훨씬 간결하게 계산해 나갈 수 있다.

즉, 위에서 보았던 수치해석적 그라디언트는 근사적이고, 기술하기 쉬우나 매우 느리다. 하지만 우리가 배운식을 통하여 식으로써 표현된 그라디언트를 바로 코드로 옮기면, 더욱 정확하고 빠르게 계산할 수 있으며, 분석이 가능하다. 실제 응용에서도, 항상 분석적 그라디언트를 사용하지만, 수치해석적 그라디언트를 통해 다시 확인해보며 이를 그라디언트 체크라고 한다.

경사하강법은 그라디언트를 계산 후, 앞에 학습률(learning rate, 여기서는 step_size로 표현)(그레디언트 반영률 이라고 보면 된다.), 곱한 값을 기존의 가중치값에 빼서, 가중치를 업데이트 하는 방식으로 진행한다.

이 때, 확률적 경사하강법(stochastic gradient descent)라는 방법이 있다. 차이는 딱 한가지이다. 경사하강법은 가중치를 업데이트 할 때, 모든 데이터를 이용하지만 확률적 경사하강법은 배치(batch)를 설정하여 일부분에 대해서만 훈련을 진행한 후 가중치 업데이트를 진행한다. 이 떄, 확률적 경사하강법은 경사하강법에 비해서 한 번 훈련시키는데 훈련 시간이 적다는 장점이 존재한다. 하지만 경사하강법 보다는 다소 불안정적인편이지만, 거의 웬만한 상황에서는 똑같이 수렴한다.

Aside

image features

추가적으로 다루는 부분인것 같다. 개구리의 이미지에서 다음과 같은 특징의 그래프를 추출해 냈다고 하자.

그런데 웬만해서 이렇게 추출된 특징은 선형 분류가 불가능하다. 이때, 위의 그림처럼 원래는 선형 분류기로 분류가 불가능한 특징을 특정 변환을 통하여 선형 분류기가 분류할 수 있도록 변화시키고자 한다.

이 때 쓰이는 방법중 하나가 Histogram of Oriented Gradients(HoG)라는 방법으로 이미지를 nxn의 그리도(격자영역, 그냥 일정 크기의 사각형으로 나눈다는 뜻이다.)그리고 나눈 사각형 안에서 엣지의 방향을 9개의 구역으로 구분하여 해당 격자안에 엣지의 방향이 어떻게 분포되있는 가를 특징으로 사용하는 방법이다.

두 번째 방법은 bag of words이다. 단어의 가방이라는 뜻으로, NLP영역에서 먼저 출발한 방법이다. 이것이 이미지 도메인에 적용된 방법이다. 우선적으로 랜덤한 패치를 추출한 후, 각 패치들을 클러스터링한다. 그렇게 되면, 그 특징들을 대표할 수 있는 클러스터링 센터가 생기게 된다. 이 센터 하나가 보통 코드워드(codeword)가 되며, 이 코드워드가 모인것이 코드북(codebook)이 된다. 이후에 이미지를 코드워드를 이용하여 인코딩(encoding)을 진행한다. 해당 코드워드가 이미지에 얼마나 많이 나타나는지가 히스토그램으로써 인코딩이 진행된다. 히스토그램값을 확률(bayesian) 혹은 특징벡터(SVM등)으로 이용한다고 한다.

현재는 이러한 feature extraction을 수행하는 방법에서 convolution network를 이용하는 방법으로 건너오고 있다. 앞서 소개한 단순한 feature extraction 방법보다. convolutional network를 이용한 방법이 더욱 feature를 잘 학습한다고 한다.

SIFT(Scale Invariant Feature Transform)

전에 배웠던 harris corner detector, shi-tomasi corner detector는 scale변화에 약하다는 장점이 있다고 했었다. 다른 점에대해서도 전에 배웠던 두 corner detector보다 더 강인하고 scale에 대해서도 훨씬 더 강인한 알고리즘이 SIFT이다. 즉, SIFT는 이미지의 크기, 회전, 방향등의 affine transform에서 나오는 성질들과 스케일에 강인한 알고리즘이다.

• SIFT의 과정
  1. scale space만들기
  2. DoG(Difference of Gaussian)
  3. Key candidates 찾기
  4. Accurate keypoint localization
  5. Orientation Assignment
  6. Key point descriptor
  7. Key matching

Scale에 대해서의 글을 읽고 scale에 대해서 안다고 하고, 바로 첫 번째 과정부터 설명을 하겠다.

1. Scale space 만들기

1. 원본 이미지를 2배 확대한 후, $\sigma = 1.6$인 Gaussian kernel로 blurring을 진행한 이미지가 Octave 1의 level1에 해당한다. 즉 이것이 시작이다.
2. $k=\sqrt2$로 설정한다. 즉 level2의 inner scale = $\sqrt2 \sigma$가 되도록 convolution을 진행해야한다. 그러므로 blurring 해야하는 가우시안 커널의 $\sigma$ 값은 $(\sqrt2 * 1.6)^2 = (1.6)^2 + \sigma ^ 2$가 된다. 이런 식으로 계속해서 더 높은 level을 계산한다.
3. 5level 까지 계산되었을 때, blurring을 멈추고 inner scale이 $2\sigma$인 부분의 이미지를 2배의 down-sampling을 진행한다. down-sampling된 이미지가 octave 2의 시작 이미지가 된다.
4. Octave 4까지 위의 계산을 반복한다.

2. DoG 계산

Scale space에 대해서 배울 때, DoG로 LoG를 근사한다고 하였다(LoG 및 DoG도 가능하면 보고 오면 좋다). SIFT에서는 LoG커널을 통하여, 극점 을 찾아내어 blob검출을 필요로 한다. 그렇기 때문에, 대신 DoG를 계산하여 LoG를 근사한다.

3. Key candidates 찾기

DoG 연산 후, 한 octave에서 5개의 이미지가 4개의 DoG 결과로 줄어든 모습을 확인할 수 있다. 그리고 4개의 DoG로 부터 3개씩 짝지어 극값을 찾아준다. [그림3]을 보았을 때, X표시한 지점이 주변의 모든 26개의 픽셀값 보다 크거나, 작을때 즉, maximum 혹은 minimum일 때만 key points 후보가 선정된다는 것이다. 최종적으로, 한 Octave에서 2장의 극값 이미지가 나오고, 4개의 octave가 존재하므로, 총 8장의 극값 이미지가 나오게 된다.

[그림3]에 보면 Scale이란 단어가 보인다. [그림2]의 이미지를 보면 level1과 level3의 inner scale은 $\sigma, 2\sigma$로 두 배 차이가 난다. 이 때 이것이 [그림3]에서 적혀있는 scale이다. 앞으로 s라고 언급하겠다. 이렇게 극값 계산시 3개의 level의 DoG이미지를 이용하기 때문에, 참고한 논문에서는 한 옥타브당 level의 개수는 s+3으로 설정해야 한다고 하였다.

그리고 s=2라면, 세 개의 DoG이미지를 모아놨을 때 scale=2라는 뜻이므로, scale 변화비율 k는 $k=(2)\frac{1}{s}$를 만족해야 한다.

4. Accurate keypoint localization

3번 과정을 통해서 key후보를 찾았다. 이 후보들 중에는 contrast가 너무 낮거나(그러므로, 노이즈에 민감하다) DoG가 엣지에 민감하기 때문에, 엣지위에 존재하는 잘못된 key후보들이 있을수가 있다.

4.1 low contrast 해결

논문에서는 low contrast문제를 해결하기 위해서, 테일러 급수를 통해서 interpolation된 극값의 위치를 잡아내어 해당 위치($\hat{X}$)에서, $D(\hat{X})$의 값이 일정 값 이하이면 keypoint의 후보에서 reject하는 방법을 사용하기로 하였다. 실제로 이 방법은 효과적이었다고 하였다. 해당 과정의 식은 다음과 같다.

DoG를 테일러 급수를 이용하여 전개한 것은 [식1]과 같다. 위 식이 이해가 안가는 분은 Khan academy의 강의를 보고 오면 좋을것 같다. 우리는 이제 테일러 급수의 극값의 위치를 구해야 한다. 그렇기 때문에, 테일러 급수의 미분식을 구한 후, 미분식=0 을 만족시키는 X값을 찾아야 한다.

Paper에는 위와같이 결과값만 나와있는데, 풀어서 전개를 해봤다. 전개해본 과정은 아래와 같다.

이렇게 해서 극값의 위치를 찾아내었다. 그런 다음, [식2]에서 얻은 값을, [식1]에 대입 해서 극값을 얻어내자. 그 다음 그 극값이 0.03보다 작으면 key 후보는 reject된다. 과정을 식으로 나타내면 다음과 같다.

4.2 key candidates sensitive to edge 해결

그 다음으로는, edge에서 민감하게 반응하여 잘못 선출된 key후보를 제거해야 한다. 논문에서는 poorly defined peak in DoG function will have a large principal curvature across the edge but a small one in the perpendicular direction. 즉, 잘못 검출된 지점은 엣지에서는 큰 주곡률을 가지지만, 수직방향으로는 작은주곡률은 가진다고 번역이된다. 주곡률이 무엇인지는 잘 모르겠지만, 고유값이 주곡률을 의미한다고 한다. 그래서 위와같은 성질을 이용해서 논문에서는 고유값의 비율을 체크해서 일정값 이하면, 작은주곡률 혹은 균일한 주곡률을 가졌다 판단하고, 비율이 일정값 이상이면, 큰 주곡률과, 작은 주곡률을 가졌다고 판단하여 reject한다. 식은 아래와 같다.

Hessian matrix의 고유값을 각각 $\alpha, \beta$라고 하자. 선형대수에서 배웠듯이 서Hessian matrix의 trace와 determinent를 다음과 같이 구할 수 있다.

이 때, $\alpha > \beta$라 하자. 그리고, 임의의 상수 $r$에 대하여, $\alpha = r\beta$를 만족한다고 하자. 이 때 다음과 같은 비율을 정의하자.

위에서 제시된 [식7]을 만족 시키면 accept 하고, 만족 시키지 않으면 reject한다. 이 때, 논문에서는 $r=10$이 적절한 값이라고 말하고 있다.

5. Orientation Assignment

이제 key point들을 추려냈으니, rotation invariant를 위해서 keypoint에 방향을 할당할 차례다. key 를 중앙으로 하여 주변으로 16X16의 윈도우를 설정한 뒤, 그 윈도우 안의 이미지를 Gaussian blurring을 수행한다. 그 후 gradient의 방향과 크기를 정해준다.

이 때, Gaussian blurring을 할 때 논문에서는 다음과 같이 말하고 있다. The scale of the keypoint is used to select the Gaussian smoothed image, L, with the closet scale, so that all computations are performed in a scale-invaraiant manner 즉 keypoint의 scale에 따라 smoothing 하는 gaussian kernel의 분산값이 달라지는 말로 해석된다. 어떻게 달라지는 지는 코드를 참고해봐야 알 것 같다.

그리고 Gradient의 방향과 크기가 계산된 후에, Gradient magnitude map(image)의 원래 keypoint의 scale의 1.5배 를 만드는 분산($\sigma$)을 가지는 가우시안 커널로 Gradient magnitude image를 convolution하여 magnitude값을 재설정한다. 위의 과정을 요약하자면 다음과 같다.

1. key를 중심으로 16X16 윈도우 설정
2. 윈도우 Gaussian blurring(분산은 keypoint의 scale에 따라 다름)
3. Gradient의 방향과 크기 계산
4. keypoint의 scale의 1.5배의 분산을 지닌 가우시안 커널로 gradient magnitude image를 convolution 하여 magnitude값 재설정(가중, weighting)

읽으면서, 각 keypoint 들에 대해서 위와 같은 연산을 하고 있다는 것을 기억하면서 따라오자. 지금 까지 수행된 과정은 16X16 window의 각 픽셀의 gradient와 그 크기를 구하였다. 아직, keypoint에 대해서 방향을 할당하지 않았다. 이제 key point에 방향을 할당해보자.

0~360도를 기준으로, 36개의 bin을 설정하자. 즉 구간을 0~9, 10~19, … , 350~359로 나누자는 뜻이다. 위에서 계산한 gradient 의 방향을 나타내는 이미지와 weighted gradient magnitude map에서 gradient크기 값을 사용해야한다. 만약에 (1,1) pixel의 gradient 방향이 15도 이고, weighted gradient크기가 20 이었다면, 10~10의 bin에 20만큼 채우는 것이다. 이렇게 모든 픽셀에 대해서 똑같은 과정을 반복하여 히스토그램을 형성한다. 만약에 최고점의 80%이상 되는 bin들이 더 존재한다면, 그 방향도 keypoint의 방향으로 취급한다. 즉, 복수의 방향이 할당될 수 있다는 뜻이다. 히스토그램 형성 결과는 아래와 같다.

6. Key Point Descriptor

이제 keypoint에 descriptor를 만들어줄 차레다. decriptor를 번역해보자면 ‘설명자’정도로 할 수 있겠다. 그런데 생각해보면 이미 keypoint의 방향,크기 까지 구했는데 이걸로 keypoint를 설명할 수 있는거 아닌가? 이미 keypoint의 특징을 구했는데 이걸로 비교를 하면 되지 않을까? 라고 생각이 들것이다. [그림9]를 보고 얘기해보자.

얼핏 보면 같아보인다. 그런데 과연 왼쪽과 오른쪽 그림의 keypoint를 비교하여 찾아낼 수 있을까? 우리가 두 그림이 같은 그림이고, 회전된 그림이라는 것을 안다면 가능할 것이다. 왜냐하면 다시 돌려서 비교하면 되기 때문이다. 그런데 우리가 하려는 것은 그런게 아니다. 우리는 입력받는그림의 스케일이 다르던, 회전된 정도가 다르던 이러한 정보를 모르는 상태에서 매칭을 진행하고 싶은 것이다. 그렇다면 우리가 위에서 알아낸 것들은 도대체 무엇일까? 마치 절대좌표와 상대좌표같은 개념을 다루기 위한 keypoint의 정보(특징)을 알아낸 것이다. 예를 들어, 우리가 일반적으로 사용하는 데카르트 좌표계와 극좌표계, 아니면 선형대수에서 다루는 기저가 다르다고 할 수도 있을 것이다. 아니면 똑같인 1일이래도 지구에서 1일과, 화성에서 1일이 다르다는 이런 개념이다.

즉,해당 이미지의 기준만 고려해서 구해진 keypoint의 특징이라는 것이다. 그렇기 때문에 다른 상태에 놓인 이미지들과 비교해주기 위해서 다른 정보가 더 필요한데 그것이 바로 descriptor이다. 그렇다면 descriptor가 무엇인지 어떻게 decriptor 역할을 하는지 살펴보자.

5번 과정과 상당히 유사하다. 5번 과정과 똑같이 제일 먼저 keypoint를 기준으로 16X16윈도우를 만들어준다. 그리고, window크기의 1/2인 값을 $\sigma$(여기서는 아마 8)로 가지는 Gaussian kernel을 곱해주어 가중치를 준다. 이는 keypoint로 부터의 거리에 따라 영향력을 달리하기 위함이다. 그 다음 16X16윈도우에서 똑같이 Gradient 계산을 해준다 그 후, 16X16 window를 16개의 4X4윈도우로 나눈다. 그 후, 4X4 윈도우에서 5번 과정에서 했던것과 똑같은 방식으로 히스토그램을 그린다. 이 때, 히스토그램 생성시 bin은 8개만! 만들어준다. 즉 0~44, 45~89, … , 320~359로 나눈다. 그렇게 하면 여기서는 5번 과정처럼 크기가 큰 방향만 고르지 않고 모든 방향을 모두 선택한다. 그렇게 한다면 총, 한 개의 4x4윈도우 에서 8개의 방향이 나오게 된다. 그렇게 된다면 16개의 윈도우 에서 총 128개의 feature vectors가 생성되는 것이다.

그리고 가장 중요한 과정이 남았다. 16X16 윈도우의 중심이 되는 keypoint가 있었단는 것을 다시 기억해내자. 우리는 그 keypoint를 중심으로 16X16윈도우를 만들고 4X4 윈도우로 나누었다. 그 중5번 과정에서 keypoint의 방향과 크기를 구했었다. 이제 마지막으로 4X4윈도우에서 구한 vector들에서 중심이 되는 keypoint의 orientation vector를 빼주자. 이렇게 한다면 rotation invariant한 성질이 완성된다.

그리고 또한, 밝기에 불변한 값을 가지기 위해서 정규화(Normalization)과정이 필요하다 한다. feature vectors의 크기를 1로 만드는 과정이다. 추가적으로, 비선형적 밝기 변화에 대해서 값이 0.2 이상으로 나오면 제대로 검출이 안되기 때문이라고 한다. 그렇기 때문에, 최대값 max값을 찾고, 그 값을 a라고 할 때, 전체를 5a로 나눈다면 0.2이상의 값이 검출이 안될 것이다. 이렇게 처리하는 부분은 참고한 링크에서 인용하였다.

7. Key matching & Clustering

Key matching은 key의 모든 descriptor간의 유클리디안 거리를 파악하여 key간의 거리를 파악하여 비교하는것 같습니다. 또한 이렇게 하여 가까운 key끼리 matching을 한 후, matching이 잘 이루어 졌는지 확인하기 위하여 GHT(Generalized Hough Transform)을 수행하여, matching된 부분이 centroid로 잘 대응되는지 inlier를 확인한다고 합니다.

유클리디안 거리가 뭔지도 알고, GHT가 무엇인지도 개략적으로 알지만, 구현부를 보지 않는 이상 석연치 않는 부분이 많은 것 같습니다. 아직 공부할게 많아서 시간을 내기 힘들겠지만, 무언가 SIFT의 다른 오픈소스를 보고 customizing을 해보는 것을 해본다면 많은 공부가 될 것 같다는 생각이 들어 꼭 시간을 내어 해보고 싶은 생각이 듭니다. SIFT에 관한 게시물은 이번에는 이것으로 마치며, 다음에 더 아는게 생기거나, 코드 customizing을 해볼 시, 추가 업데이트를 하도록 하겠습니다. 감사합니다.

References

• Distinctive Image Features from Scale-Invariant Keypoints
• bskyvision 심교훈 - SIFT
• 한국과학기술원 전기 및 전자공학과 최성필 님의 SIFT 정리자료

신호를 전송하거나, 신호에 관련된 정보를 저장할 때, continuous하게 저장하거나 보낼 수 없는 경우에, 해당 신호의 일부만을 sampling하여 정보를 저장하고, 이를 복원하여 사용한다고 한다. 즉, 신호를 discrete하게 만들어서 취급한다는 것이다. sampling theory는 sampling을 할 때, 어떻게 sampling을 해야하는가를 말한다. 이 때 유명한 theory중 하나가 Nyquist sampling theorem이다. 이에 대해서 간략하게 살펴보자.

Nyquist Sampling

간단하게 말해서 nyquist samping은 sampling 주파수가 신호의 대역폭보다 2배 커야한다는 것이다. 즉, $W_s > 2B$라고 할 수 있다. 이를 time domain에서 설명하면, $T_s < P/2$ sampling하는 간격이 신호의 주기(period)의 $1/2$보다 작아야 한다는 것이다. 왜 그런 것인지는 아래 그림을 보자.

[그림1]에서 위 그림은 nyquist sampling을 만족하는 간격으로 sampling을 진행한 것이고, 밑 그림은 만족하지않는 간격으로 smapling을 진행한 것이다. 그 결과를 주파수도메인에서 분석한 것이 오른쪽 그림들이다.

time domain에서 촘촘하게 sampling을 하면, frequency domain에서는 더 넓게 분포하는 형태로 나타나게 된다. 왜냐하면, time과 frequency는 반비례하기 때문이다. 즉, time domain에서 촘촘하게 sampling 한다는 것은, frequency domain에서 sampling frequency의 간격은 넓어진다는 것이다.

그렇다면, 이제 이 주기가 왜 중요한지 살펴보도록하자. 아래 그림을 보자.

time domain과 frequency domain에서의 sampling모습을 나타낸 것이다. time domain에서는 곱의 형태로 나타난다. fourier transform에서 배웠듯이, time domain에서 곱 연산은 frequency domain으로 나타내었을 때, 컨볼루션연산으로 바뀌게 된다. 즉 delta-train 의 convoultion연산을 다시 생각하면 된다.

이제 [그림1]이 나타낸게, 시간과 주파수도메인 에서의 sampling이라는 것을 이해했을 것이다. 그렇다면 다시 [그림1]을 보자.[그림1]에서 위, 아래 중 어떤게 샘플링이 적절하게 된 것일까? 정답은 바로 위 경우다. 적고나니 이미 정답을 위해서 말했다… 그렇다면 왜 적절하게 sampling이 된 것일까? nyquist sampling에 맞게 sampling을 했기 때문이다. 그렇다면 왜 nyquist sampling theorem을 따라야 하는가? 그 이유가 바로[그림1]의 아래 이유 때문인데, Aliasing이라는 현상이 일어나기 때문이다. aliasing은 [그림1]의 아래 그림처럼 sampling하였을 때, 주파수 도메인에서 그래프가 겹쳐버린다면, 우리가 원하는 신호를 표현해내지 못하기 때문이다.

[그림1]의 위에 그림을 보면, 우리가 원하는 신호가 잘 보존되있는 것을 확인할 수 있다. 그런데 밑에 그림을 보면 그 신호들이 겹쳐져있는 부분이있다. 그 신호들의 겹쳐진 부분들은 서로 더해지게 된다. 그렇게 되면 우리가 원하던 형태와 다른 형태가 된다. 즉, 원래의 신호가 어떤 신호였는지 알 수 없게 되는 것이다. 그렇다면, 우리가 원하는 신호로의 복원은 할 수 없게 된다.

이 때, 이 신호들이 겹쳐지지 않게 하는 최소한의 간격을 제시한것이 바로 Nyquist theorem이다.

Gaussian kernel sampling

위 그림은 이미지 도메인에서 Gaussian kernel을 sampling 한 것을 나타낸다. [그림3]에서 윗 부분이 이미지의 공간 도메인(saptial domain) 아랫부분이 주파수도메인을 나타낸다. 가우시안 커널의 sampling을 보자면, aliasing이 일어나지 않는 범위에서 sampling 주파수가 생성되야하는 것을 알 수 있다.

우리가 알고있듯이, Gaussian distribution은 분산인 $\sigma$의 영향을 받는다. 아래 그림에 나타나있다.

또한 [그림4]에서 알 수 있듯이, spatial domain과 frequency domain의 $\sigma$값은 반비례관계를 갖는다. 이것이 의미하는 바는 공간 도메인의 $\sigma_s$값이 높다면, 주파수 도메인의 $\sigma_f$값은 낮으므로, sampling frequency가 낮아도 된다는 것을 의미하며, 반대로 $\sigma_s$가 낮다면, 주파수 도메인의 $\sigma_f$값은 높으므로, sampling frequency가 높아야 된다는 것이다. 즉, 후에 scale space를 구축할 때 다시 한번 나오겠지만, down sampling을 할수록 이미지의 크기가 작아지는데, 그에 따라 $\sigma_s$가 같이 커지기 때문에 aliasing을 방지할 수 있게 된다.

그런데 [그림5]를 보면, checkboard pattern의 크기가 클 수록, deta 함수간의 주파수 간격이 멀어지는 것을 볼 수가 있다. 이것만 보면 down sampling할 때, 이미지의 크기가 충분히 크다면, blurring을 많이 안해줘도 될것 같다는 생각이 든다. 왜냐하면 sampling frequency가 충분히 커지기 때문에, aliasing이 발생하지 않을것 같기 때문이다.

Reference

• 혁펜하임 Sampling 강의
• Aliasing, Image Sampling and Reconstruction
• A Generalized Framework for Interactive Volumetric Point-Based Rendering
• Milania’s Blog
• Lesson 14 - 2D FFT
• CS 430 spring 2005

LoG(Laplacian of Gaussian)

Laplacian of Gaussian은 이름에서도 알 수 있듯이,Laplacian + Gaussian 입니다. 즉, 이미지를 Gaussian kernel로 한 번 미분한후, laplacian 연산자를 적용하여 한 번더 미분한것을 의미합니다. 미분연산자는 이미지에서 edge, ridge, corner, blob가 같은 특징들을 검출하는 데에 쓰입니다. 라플라시안 연산자는 미분연산자의 발산(divergence)의 성질을 가지고 있기 때문에, 밝기가 서서히 변하는 엣지에 대해서는 반응하지 않습니다. 이러한 부분 때문에, 1차 미분연산자와 다르게 엣지를 보다 샤프하게 잘 검출해냅니다. LoG연산자는 2차 미분연산자인 Laplacian 연산자가 잡음에 민감한 문제점을 해결하기 위해서 Gaussian smoothing을 적용한 후 laplacian을 수행하는 연산자 입니다. 특히 LoG연산자는 극점 검출에 용이하기 때문에, blob검출에 잘 쓰입니다.

그렇다면 이미지에 가우시안 스무딩을 하고 라플라시안 연산자를 적용해야 한다고 물어보면 아니라고 생각합니다. 왜냐하면 컨볼루션 연산간에는 결합법칙이 성립하기 때문에, 가우사인 연산자와 라플라시안 연산자를 먼저 컨볼루션한 후 이미지와 컨볼루션 할 수 있습니다. 그렇게 되면 LoG연산자를 미리 만들어 놓을 수가 있습니다.

식을 보면 1D의 경우에는 축이 한개의 축밖에 없으므로, Gaussian의 이차 미분이 그대로 LoG의 식과 같아지는 모습을 볼 수 있습니다.

[그림2]는 LoG를 컨볼루션한 결과를 나타냅니다. (a)의 경우에는 Gaussian커널의 1차미분, 2차미분 커널로 edge detection을한 결과를 나타냅니다. (b),(c)는 blob에 대한 LoG kernel 과의 convolution 결과 입니다. 여기서 blob은 extrema로써 순간적으로 밝아지거나 어두워지는 것을 의미합니다. (b)의 경우에는 여러 신호에 대한 LoG커널의 결과를 보여줍니다. 이 때, $\sigma=1로$ 일정합니다. (c)의 경우에는 한 신호에 대해서 $\sigma$ 값이 다른 LoG kernel과의 convolution 결과를 나타냅니다.

여기서 주목해야 할 점은, **신호에 따라서 극대 극소값을 가지는 대응하는 ** $\sigma$ 값이 있다는 것입니다.

normalization을 위해서는 LoG에 $\sigma$ 를 곱해주면 됩니다.

DoG(Difference of Gaussian)

DoG는 scale space구성과 관련이 깊다. scale space글과 같이 보는 것을 추천한다. DoG는 한국말로 번역하면 가우시안 차이 입니다. 즉, 서로다른 $\sigma$ 값을 가지는 가우시안 커널의 차를 이용하는 것입니다. 그렇다면 가우시안 커널의 차를 이용해서 무엇을 할까요? 바로 LoG에 대한 근사입니다. 계산량 때문에 LoG를 근사하는 DoG를 사용한다고 하는데, 사실 위에 말한것처럼 LoG커널을 미리 만들어두고 사용하면, 굳이 DoG를 사용하지 않아도 될것같다고 생각이 듭니다.

그렇다면 어떻게, DoG과 LoG를 근사할 수 있을까를 살펴보면, 1994, Lindeberg의 Scale-space theory in computer vision, 11-15p에 언급이 되어있으니 살펴보시기 바랍니다. 또한, Causality in Scale Space에도 언급이 되어 있습니다. Causality in scale space의 글에 따르면, small sacle에서 large scale로 증가할 때, 새로운 디테일이나 구조가 나타나면 안된다고 합니다. 이것을 Causality라고 한다고 나와 있습니다.

[그림4]를 보면 smoothing이 됨에 따라 약간씩 구조가 변하긴 하지만, 전반적인 특징적인 부분들, 특히 극대점, 들은 거의 유지되는 모습을 볼 수 있습니다. 이렇듯 기존의 구조를 개략적으로 유지하면서, 새로운 구조가 나타나지 않는성질을 causality라고 하는것 같습니다.

Causality를 만족하는 식을 구성하면, infinite domain에서의 linear heat diffusion equation과 같이지고, 열 확산 방정식의 $\sigma=\sqrt{2t}$로 놓고 대입하여 스케일만 조정하면, Gaussian의 식을 얻을 수 있다고 합니다. 즉, 열이 중앙에서 주변으로 서서히 퍼지는 과정이 마치, 가우시안 스무딩을 점차 진행( $\sigma$ )가 증가함에 따라, 이미지가 점점 블러링 되는 과정과 동일하게 볼 수 있다는 뜻이 됩니다.

여기서 중요한 점은, 열 확산 방정식과 동일하게 볼 수 있다는 점입니다. 열 확산 방정식은 다음과 같은 식을 만족합니다.

그런데 위 [식1]은 편미분으로 식이 구성되어있다. 즉, 매우 미소한 공간이라는 뜻이다. 이러한 $\sigma$값은 실제로 다룰 수 없으므로, $\sigma$와 근처에 있는 $k\sigma$값을 지니는 가우시안 커널을 이용하여 DoG연산으로 LoG를 근사할 수 있다.식을 보면 아래와 같다. 이렇게 구성하는 것은 나중에 다룰 scale space와 연관된다.

그리고, 원래는 미소변위에 대해서 식이 성립했으므로, k가 1에 최대한 가까워 질수록 LoG에 더욱 잘 근사하게 된다.

References

• 다크 프로그래머 Scale Space와 이미지 피라미드(image pyramid)
• Distinctive Image Features from Scale-Invariant Keypoints

딥러닝, 머신러닝을 공부할 때 처음에 힘든 것중에 하나가 바로 데이터의 행렬 표기였습니다. 단순히 행렬로 표시하는게 어려운게 아니고, 행렬에 관한 미분연산을 이해하기가 힘들었었습니다. 그 때는 그런 개념이구나 단순히 이해하고 넘어갔었는데, 그 때 보다는 아주 조금 더 이해가 늘은 것 같습니다. 아무래도 여러 시도를 하다보니까, 눈에 익고 손에 익은 탓인것 같아요. 그래서 약간 익은 김에 기억한 부분을 정리하고자 합니다… 남들에게 강의할만한 정리는 아니고 제 머릿속에 있는 것을 정리하고, 다른 분들이 정리해두신 내용을 제가 나중에 봤을 때 도움을 얻기위한 정리라고 볼 수 있습니다.

행렬 연산과 미분

행렬 연산

1. Column picture and Row picture

   

행렬을 보다보면 위 두개의 관점에서 보는게 자유로워 져야 읽기가 편해진다. 선형성을 다룰 때 행렬식을 보통 column picture로 나타낸다.

1. Quadratic form(이차형식)

   [식2] Quadratic form, x는 벡터, A는 행렬이다.

여기서 A는 대칭행렬임을 잠깐 짚고 넘어가자. 다른 곳에서 또 쓰일지 모른다. 이러한 Quadratic form형태는 다변수 함수에 대한 연산을 행렬식으로 나타낼 때, 많이 보인다. 예를들어, 테일러 급수를 표현한다고 하면, 테일러급수의 이차미분항이 Quadratic form으로 표현된다.

행렬 미분

아래 나오는 표와 식들은 위키피디아를 참고하였습니다. 아래는 numerator중심 표현의 식들입니다.

1. 스칼라 함수의 벡터미분

   

   그라디언트의 경우와 동일합니다.

2. 벡터 혹은 다변수 벡터함수의 스칼라 미분

   

3. 벡터 혹은 다변수 벡터함수의 벡터미분

   

4. 행렬의 스칼라 미분

   

5. 스칼라의 행렬 미분

   

위의 표는 다크 프로그래머님의 블로그를 참고하였습니다. 위키피디아에 더 많은 공식들을 정리해 놨으니, 행렬식을 이용한 증명이 이해가 안갈때에는 위키피디아를 참고하면 좋을것 같습니다.