# BoVW ![](https://www.googleapis.com/download/storage/v1/b/kaggle-forum-message-attachments/o/inbox%2F3879542%2F309d819c6b29f7149c8a66e09e0f7da6%2FBow.png?generation=1604901070523914&alt=media) [그림 1] BoVW의 흐름도 BoVW는 원래 Bag of Words(BoW)로 문서를 분류하기 위한 방법론으로 사용됐다. 문서 속 단어의 분포를 통해서 문서의 라벨을 추측하는 방법론이다. 이러한 방법론을 영상분류에 적용하기 위해서, 문서 속 단어의 분포를 영상의 특징점의 분포로 바꾼 것이 BoVW이다. ![](https://www.googleapis.com/download/storage/v1/b/kaggle-forum-message-attachments/o/inbox%2F3879542%2F287379c7e001b9c910af74a4d2c889a2%2FBoW_all.png?generation=1604905204813436&alt=media) [그림 2] BoVW 설명도 0 BoVW 의 전체적인 이해를 위해 그림 2번을 보면 아래와 같은 순서로 진행 된다. - 1. 각 클래스 사진들의 **특징점**을 검출한 후 사진 하단 부처럼 모은다. - 2. 모은 모든 특징점을 분석하여, 사진 중단부 그래프 속 x축 즉 모든 영상을 대표할 특징점들(codebook)을 선정한다. - 3. 사진 중단부 그래프와 같이 선정한 codebook 이 각 영상에 포함된 빈도 (histogram)를 모든 영상에 대해 구한다. 이 **Histogram** 이 2D 영상을 표현하는 1D vector 가 된다. - 4. 3번 과정을 통해 구한 1D vector를 feature vector로 생각하여 SVM을 학습하여 최종적으로 classification을 진행한다. ## 1. 영상 특징점(SIFT) 검출 ![](https://www.googleapis.com/download/storage/v1/b/kaggle-forum-message-attachments/o/inbox%2F3879542%2F47ee45e50d86f04bf4df3fc250bf8cb0%2FBow_1.png?generation=1604903376894286&alt=media) [그림 3] BoVW 설명도 1, 영상 특징점 검출(words 검출) 기존 BoW가 단어의 분포를 보고 문서의 라벨을 추측했다면, BoVW는 영상의 특징점 분포를 보고 라벨을 추측한다. 설명을 위해 그림 3를 보면 , 사람 영상 속에서 특징이라 할 수 있는 특징점(눈,코,입, 턱 등) 을 특징점("words") 라고 지칭하여 저장한다. **예시를 위해서 특징점을 (눈,코,입 등) 으로 표현했지만 사실은 밝기값의 차이 등을 활용한 SIFT라는 영상의 특징점 검출하는 알고리즘을 사용한다.** ![](https://www.googleapis.com/download/storage/v1/b/kaggle-forum-message-attachments/o/inbox%2F3879542%2F08d89223aa2fbe3c2677a1c05a33c4ec%2FSIFT.png?generation=1604904329992771&alt=media) [그림 4] SIFT 표현 SIFT를 사용해 영상의 특징점을 추출하여, 추출된 곳은 표현하면 그림 4 과 같이 표현 할 수 있다. SIFT에 관한 자세한 설명은 참고 자료들을 보길 바란다. ### DenseSIFT ![](https://www.googleapis.com/download/storage/v1/b/kaggle-forum-message-attachments/o/inbox%2F3879542%2Fe6decfdd3c78d611a87c8d5e6071ff85%2FSIFT.png?generation=1605022203856596&alt=media) [그림 SIFT] DenseSIFT와 SIFT 비교 SIFT는 영상 전체를 분석하여 특징점을 추출한다. 이렇게 영상을 분석을 하면 특징점이 영상 전체에 고르게 분포되지 않고 특정 위치에 몰려있거나 아예 특징점이 검출되지 않을 수도있다. 따라서 영상의 모든 부분의 특징을 사용하기 위해서 DenseSIFT가 사용된다. DenseSIFT는 keypoint 즉 특징점의 위치를 미리 선정해두고 그 위치에서 특징점을 검출한다. SIFT와 DenseSIFT의 차이는 그림 SIFT를 통해 확인 할 수 있다. ### 코드 구현 - 기본 SIFT 구현 ``` def extract_sift_descriptors(img): # img.shape==[256,256,3] ## SIFT 정의 sift = cv2.xfeatures2d.SIFT_create() ## 영상의 키포인트를 detect 하고 키포인트의 Descriptor를 compute 하는것을 동시에 진행 keypoints, descriptors = sift.detectAndCompute(img, None) ## descriptor 반환 return descriptors ``` - Dense SIFT구현 ``` def extract_DenseSift_descriptors(img): # img.shape==[256,256,3] ########################################### # 기본 SIFT 와 동일하게 sift 정의 ########################################### # 영상 전체에 미리 keypoint를 정의 keypoints = [cv2.KeyPoint(x, y, DSIFT_STEP_SIZE) for y in range(0, img.shape[0], DSIFT_STEP_SIZE) for x in range(0, img.shape[1], DSIFT_STEP_SIZE)] ########################################### # 기본 SIFT 에서는 detectAndCompute를 사용했지만 # Dense SIFT는 위에서 생성한 keypoint를 사용해 compute 만을 진행 ########################################### return descriptors ``` ## 2. Codebook 생성 ![](https://www.googleapis.com/download/storage/v1/b/kaggle-forum-message-attachments/o/inbox%2F3879542%2F4359c190255960253b37f96f69a0d922%2Fcodevook.png?generation=1604904714473588&alt=media) [그림 5] BoVW 설명도 2 , Codebook 모든 영상의 SIFT 특징점을 검출하여 [그림 5]와 같이 모은다. 이렇게 모은 모든 특징점을 분석하여 이 전체 데이터셋을 대표할 수 있는 특징점들을 찾아야 한다. ![](https://www.googleapis.com/download/storage/v1/b/kaggle-forum-message-attachments/o/inbox%2F3879542%2F6ab011a3a36dac8b1ad1ed16431c8624%2FKmeans.png?generation=1604906528788962&alt=media) [그림 6] Kmeans clustering 모든 특징점을 대표할 수 있는 특징점(Codebook)을 찾는 방법론으로 Kmeans clustering 을 사용한다. 이 방법론은 데이터를 입력받아 이를 소수의 그룹으로 묶는 알고리즘이다. 이 알고리즘은 [그림 6]처럼 label이 없는 데이터를 입력받아 각 데이터에 label을 할당함으로써 군집화를 수행한다. 군집화를 한 후 각 군집을 표현할 수 있는 중심점들을 Codebook으로 사용한다. 군집의 갯수는 사용자가 정하는 것으로 클수록 좋다. (물론 어느순간부터 성능은 수렴한다. 약 cluster 2000개 정도부터는 수렴한다는 보고가 있다.) Kmeans 가 데이터를 군집화 하는 방식은 참고사이트에서 확인 바란다. ### 코드 구현 - X=모든 영상의 특징점을 모은 Matrix - X.shape ==[3060, 1024, 128]==[ 영상 갯수, 키포인트 갯수,SIFT descriptor길이] - voc_size==cluster갯수 ``` def build_codebook(X, voc_size): ########################################### # X를 [3060*128]로 reshape # num_cluster를 voc_size로 주고 Kmeans를 정의 # Kmeans 의 fit 함수를 사용해 data의 cluster center 찾기 ########################################### return # Kmeans 내장 변수인 cluster_center를 반환 ``` ## 3. Histogram 생성 ![](https://www.googleapis.com/download/storage/v1/b/kaggle-forum-message-attachments/o/inbox%2F3879542%2F77ec2160ce96fb8e6a888e02ec9960f3%2FBow_hist.png?generation=1604907320515797&alt=media) [그림 7] BoVW 설명도 3. Histogram Codebook을 생성한 후, 그림 7 과 같이 각 영상의 특징점과 Codebook을 비교하여 Histogram을 생성합니다. 특징점과 codebook을 비교하여, 그 특징점과 가장 유사한 Cluster center의 빈도 수를 높히는 것이다. 영상의 모든 특징점과 codebook을 비교하여 histogram을 생성하게 되면, 2D 영상을 1D feature vector로 표현할 수 있게 된다. ### 코드 구현 - def BoW( descriptor, codebook) - descriptor= 영상하나의 특징점 Matrix - descriptor.shape==[1024,128] - codebook= Kmeans를 통해 검출한 Cluster centers - codebook.shape==[num_cluster,1024,128] - def input_vector_encoder(feature, codebook) - feature=descriptor - codebook=codebook ``` def input_vector_encoder(feature, codebook): ########################################### # scipy.cluster.vq 를 사용해 각 Dense SIFT와 유사한 codebook의 Index를 반환 받아 사용 # 구한 Index들 histogram을 np.histogram 을 사용해 histogram을 구한다 # np.histogram 사용시 bin=range(codebook.shape[0] + 1), normed=True 로 설정 ########################################### return word_hist def BoW( descriptor, codebook): code = input_vector_encoder(descriptor.tolist(), codebook) return # code를 flatten 하여 반환 ``` ## 4. SVM : classification ![](https://www.googleapis.com/download/storage/v1/b/kaggle-forum-message-attachments/o/inbox%2F3879542%2F8c305606c612af03417ef3334e47e575%2FSVM.png?generation=1605013920265537&alt=media) [그림 8] SVM Histogram으로 이루어진 feature vector 를 이용해 Classification을 진행할때는, 머신러닝의 정석적인 방법론이라 할수있는 Support vector maching(SVM)을 사용한다. SVM은 결정 경계(Decision Boundary) 즉 분류를 위한 기준 선을 정의하는 모델이다. 이 모델은 그림 8의 margin 즉 선과 데이터의 최단 거리가 최대한 먼 경계를 찾는 것을 목표로 한다. 자세한 설명은 참고 사이트를 확인 바란다. SVM 을 통해 Decision Boundary를 찾게 된다면 Test dataset의 라벨을 분류 할 수 있게된다. ### 코드 구현 - def SVM(train_data,train_label,test_data) - train_data=모든 학습 영상의 BoW Matrix - train_data.shape==[3060,200] - train_label=모든 학습 영상의 라벨 - train_label.shape==[3060,] - test_data=모든 시험 영상의 BoW Matrix - test_data.shape==[1712,200] ``` def SVM(train_data,train_label,test_data): ########################################### # svm.SVC() 를 사용해 SVM 정의 # SVM과 파라미터 {'kernel':('linear', 'rbf'), 'C':[0.1 ,1, 10, 100, 1000]} 를 사용해 GridSearchCV() 정의 # 정의한 GridSearchCV의 함수인 fit을 사용해 train_data 학습 # 정의한 GridSearchCV의 predict 함수를 사용해 test_data 에 대한 정답을 추론 ########################################### return predict ``` ## 5. Inference SVM 까지 학습을 완료하면 Test Set의 라벨을 추정할 수 있게 된다. 추정하는 과정을 다시 요약하면 다음과 같다. - 1. Test 영상의 SIFT 특징점 검출 - 2. SIFT 특징점와 codebook을 비교해 histogram 생성 - 3. histogram 을 SVM 모델에 넣어 클래스를 추정 ### 참고 자료 - [BoVW](https://darkpgmr.tistory.com/125) - [영상 특징점 && SIFT](https://darkpgmr.tistory.com/131) - [SIFT](https://bskyvision.com/21) - [kmeans](https://untitledtblog.tistory.com/132) - [SVM 이론](https://github.com/sejongresearch/2020.MachineLearning/blob/master/LectureNote/10%E1%84%8C%E1%85%AE%E1%84%8E%E1%85%A1_SVM(%E1%84%80%E1%85%B5%E1%84%80%E1%85%A8%E1%84%92%E1%85%A1%E1%86%A8%E1%84%89%E1%85%B3%E1%86%B8)_%E1%84%8B%E1%85%B5%E1%84%85%E1%85%A9%E1%86%AB.pdf) - [SVM 실습](https://github.com/sejongresearch/2020.MachineLearning/blob/master/LectureNote/10%E1%84%8C%E1%85%AE%E1%84%8E%E1%85%A1_SVM(%E1%84%80%E1%85%B5%E1%84%80%E1%85%A8%E1%84%92%E1%85%A1%E1%86%A8%E1%84%89%E1%85%B3%E1%86%B8)_%E1%84%89%E1%85%B5%E1%86%AF%E1%84%89%E1%85%B3%E1%86%B8.pdf)