Computer Vision Summary | 컴퓨터 비전 총정리 -1

1.Support Vector Machine

SVM(Support Vector Machine)은 Linear classifier(초평면을 이용하는 분류기)들 중에 하나이다. 분류상으로는 supervised Learning에 속한다.

SVM에서 중요한 요소 3가지는 Margin, Support Vector, Kernel 이다.

1) 마진(margin)

마진은 하나의 데이터 포인트와 hyper plane 사이의 거리를 말한다. 정확히는 각각의 클래스의 데이터 벡터들로 부터 주어진 Hyper plane 까지의 거리중 가장 짧은 것을 말한다. 마진이 클수록 분별을 잘하는 분류기.

2) 서포트벡터(Support Vector)

Hyper Plane 까지의 거리가 가장 짧은 데이터 벡터를 서포트 벡터라 한다. 이것으로 인해 SVM이 가지는 장점은 새로운 데이터 포인트가 들어왔을 때, 전체 데이터 포인트와의 내적거리를 보지않고 서포트 벡터와의 내적 거리만 구하면 되므로 상당히 계산비용을 줄일 수 있다.

3) 커널(Kernel)

선형분리가 불가능한 저차원의 데이터를 고차원의 공간의 값으로 매핑시켜 Hyperplane으로 분류 가능한 선형문제로 변환시켜 분류를 가능하게 한다. 하지만 차원을 높임으로 인해 계산비용이 높아지는 문제가 생기는데 이를 해결할 수 있는 방법이 커널법이다.

각 특징벡터의 고차원 매핑함수를 각각 정의하지 않고 전체의 내적함수만 정의하여 계산량을 줄일 수 있다. 여기서 나온 내적함수가 커널함수이고 이렇게 계산량을 줄이는 방법을 커널법이라 한다.

2. Adaboost

Adaboost는 Adaptive boosting의 약자로 간단한 weak classifier들이 상호보완 하도록 단계적(순차적)으로 학습하고, 이들을 조합하여 최종 strong classifier의 성능을 증폭시킨다. Weak classifier들을 한 번에 하나씩 순차적으로 학습시킬 때, 먼저 학습된 분류기가 잘못 분류한 결과 정보를 다음 분류기의 학습시 사용하여 이전 분류기의 단점을 보완하도록 한다. 즉, 이전 분류기가 오분류한 샘플의 가중치를 adaptive하게 바꾸어가며 잘못 분류되는 데이터에 더 집중하여 잘 학습하고 분류할 수 있도록 한다. 최종 분류기는 개별 약한 분류기들에 각각 가중치를 적용, 조합하여 얻을 수 있다. 다른 학습 알고리즘보다 overfitting에 덜 취약하지만, 잡음이 많은 데이터와 outlier에는 취약한 모습을 보인다. Adaboost의 수행과정은 다음과 같다.

1. 모든 training sample들의 weight를 동일하게 초기화한다.

2. 모든 feature에 대해 training smaple들을 얼마나 잘 분류하는지 weighted error를 계산하여 성능 평가한다. Positive를 negative로 분류하거나 negative를 positive로 분류하는 경우를 error라 하며, sample들의 weight를 고려하여 weighted error를 계산한다.

3. 분류 성능이 가장 좋은(=weighted error가 가장 작은) 하나의 feature를 해당 round t에서의 weak classifier로 한다.

4. 해당 weak classifier의 weight를 weighted error를 이용해 구한다. 에러가 크면 weight는 작게, 에러가 작으면 weight가 커지도록 하여 성능이 좋은 weak classifier의 판단을 더 신뢰하여 점수를 더 준다.

5. training sample들의 weight를 업데이트한다. 잘못 분류된 sample의 weight는 증가, 잘 분류된 sample의 weight는 감소시킨다. 이전 단계에서 잘못 분류된 sample을 제대로 분류할 수 있는 feature가 다음 단계에서 weak classifier로 될 수 있다.

2~5번 과정을 반복하며, 매 iteration round 마다 분류 성능이 가장 좋은 하나의 feature를 선택하여 해당 iteration round에서의 weak classifier로 한다. 최종 결과물은 T개의 weak classifier를 weighted linear combination하여 최종 strong classifier를 얻는다.

Hx=α1h1x+…+αThTx
Hx=t=1Tαtht(x)

H: Final strong classifier
h: Weak classifier
α: Weight of weak classifier
t: Iteration round (1, 2, 3, … , T)

3. Neural Networks

신경망(Neural Networks)은 머신러닝의 모델 중에 하나이다. 신경망의 작동원리는 다음과 같다.

뇌의 신경세포에는 정보를 저장하는 공간이 따로 없고 그저 다른 신경세포에서 오는 신호를 받아 자신의 신호를 내보내는 역할만을 한다. 뇌는 이런 신경세포들이 연결된 거대한 네트워크이며, 신경세포들의 연결 상태가 바로 뇌에 저장된 정보를 나타낸다. 신경망은 이러한 뇌의 작동 원리를 본 떠 만들었다. 수많은 신경세포가 연결되어 뇌를 구성하는 것처럼 신경망은 뇌의 신경세포에 해당하는 ‘노드’라고 하는 작은 요소들을 연결해 만든 네트워크이다. 노드들의 연결 가중치를 통해 신경세포의 연결관계를 흉내낸다.

Neural Network는 기본적으로 다음과 같은 구조를 지니고 있다. 입력이 들어오면 적절한 weight가 곱해지고 더해진다. 그리고 activation function이 취해진 후 그 결과 값을 출력한다. 이것 또한 신경세포에서 일정 threshold의 전류가 입력되지 않으면 출력되지않고, threshold 이상의 전류가 입력되면 출력이 나가는 것과 같은 원리이다.

 

 

4. Bayes classifier

베이즈 분류기는 주로 스팸 필터나 키워드 검색을 활용한 문서 분류에 사용되는 지도 학습 분류기이다. 베이즈 분류기의 기본 원리는 조건부 확률(사건 A가 발생했을 때, 사건 B가 발생할 확률)에 베이즈 정리를 적용하고, 문서나 데이터를 구성하는 각각의 요소들이 등장할 확률에 대한 독립성을 가정하여 입력 벡터를 분류하는 확률적 분류이다.

베이즈 분류기는 지도 학습 알고리즘이다. 따라서 분류기가 실행되기 이전에 학습 벡터를 통한 학습이 이루어져야 한다.  학습이 이루어진 다음 분류기에 입력 벡터를 입력하면, 분류기는 조건부 확률을 계산하여 학습 벡터에 명시된 클래스들 중 하나로 입력 벡터를 분류한다. 모든 클래스에 대해 조건부 확률식을 계산하여, 확률이 가장 높은 클래스를 선택하는 것이 베이즈 분류기 알고리즘의 기본 원리이다.

 

참고: http://untitledtblog.tistory.com/31

 

 

5. K-nearest neighbors

K-NN(K-nearest neighbors) 알고리즘은 지도 학습의 한 종류로 레이블이 있는 데이터를 사용하여 분류 작업을 하는 알고리즘이다. 알고리즘의 이름에서 볼 수 있듯이 데이터로부터 거리가 가까운 k개의 다른 데이터의 레이블을 참조하여 분류하는 알고리즘이다. 주로 거리를 측정할 때 유클리디언 거리 계산법을 사용하여 거리를 측정하는데, 벡터의 크기가 커지면 계산이 복잡해진다. K에 따라 분류 결과가 달라지므로 적절한 k를 선정하는 것이 k_NN 알고리즘의 중요한 요소이다. 너무 작은 k일 때, 과적합의 우려가 있고, 너무 큰 k일 때, 데이터의 구조를 파악하는데 어려움이 있다.

k-NN의 장점

알고리즘이 간단하여 구현하기 쉽다.

수치 기반 데이터 분류 작업에서 성능이 좋다.

K-NN의 단점

학습데이터의 양이 많으면 분류 속도가 느려진다.(사전 계산을 할수 없기 때문에 학습 과정이 따로 없어 분류 속도가 느리다)

차원(벡터)의 크기가 크면 계산량이 많아진다.

참고: http://untitledtblog.tistory.com/31

참고: http://horae.tistory.com/entry/KNN-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-1

 

6. Decision tree

의사결정나무(Decision tree)는 데이터를 분석하여 이들 사이에 존재하는 패턴을 예측 가능한 규칙들의 조합으로 나타내며, 그 모양이 ‘나무’와 같다고 해서 의사결정나무라 불린다. 질문을 던져서 대상을 좁혀나가는 ‘스무고개’와 비슷한 개념이다.

의사결정나무는 나무를 뒤집어 놓은 것과 같은 모양을 한다. 초기지점은 root node이고 분기가 거듭될수록 그에 해당하는 데이터의 개수가 줄어든다. Terminal node 간에 교집합은 없다.

의사결정나무는 분류(classification)와 회기(regression)가 모두 가능하다. 범주나 연속형 수치 모두 예측이 가능하다는 말이다.

의사결정나무는 분기 마다 변수 영역을 두개로 구분하고 각 영역의 순도(homogeneity)가 증가, 불순도(impurity) 혹은 불확실성(uncertainty)이 최대한 감소하도록 하는 방향으로 학습을 진행한다.

의사결정나무의 학습 과정은 입력 변수 영역을 두개로 구분하는 재귀적 분기(recursive partitioning)와 너무 자세하게 구분된 영역을 통합하는 가지치기(pruning) 두가지 과정으로 나뉜다. 가지치기는 분기가 너무 많아서 학습데이터에 과적합(overfitting)되는 것을 방지한다. 다만 데이터를 버리는 것이 아니라 분기를 합치는 개념이다.

 

참고: https://ratsgo.github.io/machine%20learning/2017/03/26/tree/

 

 

7. Random forest

Random forest란 decision tree의 단점을 개선하기 위한 알고리즘 중 가장 지배적인 알고리즘이다. 의사결정나무는 트리의 특성상 깊게 자랄 수 있어 과적합(overfitting)이 발생하는 문제를 가지는데 랜덤포레스트는 다수의 의사결정나무를 결합하여 이러한 과적합을 평균화 시켜 오류를 줄이고자 하는 모델이다. 다양성을 극대화 하여 예측력이 상당히 우수한 편이고 배깅과 동일하게 부트스트랩 표본을 이용한 다수의 트리의 예측 결과를 종합하여 의사결정을 진행하기 때문에 안정성도 상당히 높다는 장점을 가진다. 하지만 기존 트리의 장점인 설명력을 잃고, 데이터셋이 큰 것 중에서 변수가 많을 때 랜덤포레스트가 적절하지 못하다는 단점을 가진다.

랜덤 포레스트의 학습 원리

1.     주어진 트레이닝 데이터 세트에서 무작위로 중복을 허용하여 n개를 선택(부트스트랩)

2.     선택한 n개의 데이터 샘플에서 데이터 특성값을 중복 허용 없이 d개를 선택

3.     이를 이용해 의사결정트리를 학습하고 생성

4.     1~3단계를 k번 반복

5.     생성된 k개의 의사결정트리를 이용해 예측하고, 예측된 결과의 평균이나 가장 많이 등장한 예측 결과를 선택하여 최종 예측값으로 결정(ensemble - bagging)

 

8. Pinhole camera model

핀홀(pinhole)이란 말 그대로 종이에 핀으로 뚫은 구멍 같은 매우 작은 구멍을 말한다. 핀홀을 통해서 들어오는 빛을 받아들여 촬영하는 카메라를 핀홀 카메라라고 한다.

핀홀 카메라 모델은 물체에 반사된 빛이 우리 눈의 수정체(또는 카메라의 렌즈)를 거쳐서 망막(또는 카메라의 센서)에 도달하는 구조를 관찰하는데 유용하다.

핀홀 카메라의 원리는 3차원인 실제 세계에서 빛이 물체의 어느 한점에 반사되면, 다양한 각도의 공선 중에서 핀홀을 향하는 광선만이 핀홀 평면에 가로막히지 않고 나아가게된다. 결과적으로 이 광선은 영상 평면 또는 투영 평면이라고 불리는 곳에 맻히게된다. 이 상의 크기는 핀홀 카메라의 초점 거리에 의해 결정된다. 이상적인 핀홀 카메라일 경우, 초점 거리는 핀홀 구멍에서부터 영상 평면까지의 거리이다.

위의 그림에서 A와 a는 각각 실제 물체의 크기와 영상 내의 물체 크기를 나타낸다. 그림에서 꼭지점을 맞대고 있는 두 삼각형을 잘 살펴보면 다음과 같은 관계를 찾을 수 있다.

이를 이용하여 영상에서의 물체의 크기는 다음과 같이 구해진다.

 

9. Camera calibration

3차원의 세상을 카메라로 찍으면 2차원의 이미지로 변하게 된다. 이 때, 3차원의 점들이 이미지 상에서 어디에 맺히는지 기하학적으로 보면 영상을 찍을 당시의 카메라의 위치 및 방향에 의해 결정된다. 하지만 실제 이미지는 사용된 카메라의 렌즈, 렌즈와 이미지 센서의 거리, 렌즈와 이미지 센서가 이루는 각 등 카메라 내부의 기구적인 부분에서 크게 영향을 받는다. 따라서 3차원 점들이 영상에 투영된 위치를 구하거나 역으로 영상좌표로부터 3차원 공간좌표를 복원할 때에는 이러한 내부 요인을 제거해야만 정확한 계산이 가능해진다. 그리고 이러한 내부 요인의 파라미터 값을 구하는 과정을 카메라 캘리브레이션이라 한다.

카메라 영상은 3차원 공간상의 점들을 2차원 이미지 평면에 투사함으로써 얻어진다. 핀홀 카메라 모델에서 이러한 변환 관계는 다음과 같이 모델링 된다.

여기서 (X,Y,Z)는 월드 좌표계상의 3D점의 좌표, [R|T]는 월드 좌표계를 카메라 좌표계로 변환시키기 위한 회전/이동변환 행렬(extrinsic parameters)이며 A는 camera matrix(intrinsic parameters) 이다.

카메라 내부 파라미터는 3가지로 구성된다.

1.     초점거리 : 렌즈중심과 이미지 센서와의 거리 ( fx, fy)

2.     주점 : 카메라 렌즈의 중심에서 이미지 센서에 내린 수선의 발의 영상좌표 (Cx, Cy)

3.     비대칭 계수 : 이미지 센서의 cell array의 y축이 기울어진 정도(skew_c)

http://darkpgmr.tistory.com/32

 

 

10. Stereo calibration

Stereo calibration은 두 카메라 사이의 기하학적 관계를 계산하는 과정이다., 찾은 코너들을 이용하여 stereoCalibrate 함수를 이용하여 두 카메라 간의 기하학적 관계를 얻는다. 이 기하학적 관계는 회전과 이동의 정보를 담고 있다.

Stereo calibration은 두 카메라 간의 관계를 정립하기 위한 calibration 과정이다. Calibration을 하기 위해 체커보드를 사용하는 것은 체커보드의 코너점을 매칭점으로 사용하기 위함이다. Stereo calibration을 하기 위해서는 두 카메라가 각각 calibration 되어 있어야한다. 그 둘의 내부 파라미터와 대응점들을 이용해 두 카메라의 관계를 구한다.

Essential matrix는 실제 3차원 한 점 P를 왼쪽 카메라가 바라봤을 때와 오른쪽 카메라가 바라봤을 때의 기하학적인 관계를 나타내고, Fundamental matrix는 왼쪽 카메라에서 촬영된 영상에서의 점과 오른쪽 카메라에서 촬영된 점 사이의 관계를 나타낸다. Fundamental matrix는 Essential matrix(회전과 이동 정보 = 위치관계 정보) + 두 카메라 간의 내부 파라미터 행렬 정보도 포함한다.