In this thesis, we address three problems of the tf-idf weighting, the hierarchical scoring and intra-class key-words in the image retrieval using very large dimensional Bag-of-Words (BoW) representation. The tf-idf weighting method, which is a commonly used codebook weighting scheme, is usually understood to improve retrieval performance however its degree is not too significant. Rather, it sometimes brings a problem of worsening precision. The hierarchical scoring, which is commonly used in hierarchical codebook, the precision improvement differs depending on the dataset as the number of levels that are considered in scoring gets larger. Intra-class key-words, which represent their class most well, have not taken into consideration in BoW representation based image retrieval because of its too high dimensionality. Despite different classes have different key-word, only a same weight or standard is applied to every image classes. To overcome these three different problems, we suggest a new codewords weighting method preserving the independence model of BoWs representation that codewords occur independently in one image. In the problems of tf-idf weighting and the hierarchical scoring, the proposed method only focuses on improving the algorithms without using any extra cue besides two types of signature, document frequency used for tf-idf weighting and the level for hierarchical scoring. Since the document frequency and the level are related with inter-class discriminability, we define the two values as key-signatures. In the problem of considering intra-class key-words, the proposed method gives relevant weight to codewords according to its statistical appearance within a class. Since an intra-class variance of frequencies of a codeword is related with its intra-class importance, we define that kind of value as another key-signature. We also define a function, called Weight Mapping Function (WMF), that maps a weight value from a key-signature. In order to obtain optimal WMF shapes for each key-signature type, we learn the WMFs using randomly sampled training data by means of optimization method. From the WMF of document frequency or level, we produce a global weight vector for every classes, in the other hand, we produce intra-class weight vectors for each class from the WMF of intra-class variance. We conducted experiments with UKbench and OXford5K dataset, and our approach outperformed the tf-idf weighting and hierarchical scoring, without extra cue and additional computation in on-line stage. The proposed intra-class weighting method also shows noticeable improvement on UKbench dataset.
본 논문에서 우리는 초 고차원 Bag-of-Words (BoW) 표현법 기반의 이미지 검색을 위한 세 가지 문제를 다룬다. 세 가지 문제는 tf-idf 가중치 방법론과 계층적 스코어링 및 클래스 내부의 키워드에 관한 것이다. 대부분의 이미지 검색 시스템에서 사용하고 있는 tf-idf 가중치 방법론의 경우 일반적으로 이미지 검색의 검색성능을 향상시킨다고 여겨지지만, 실제로는 그 향상의 폭이 매우 작고 때로는 오히려 성능에 해를 끼치기도 한다. 계층 코드북 기반의 이미지 검색에 사용되는 계층적 스코어링의 경우도 스코어링에 고려하는 레벨의 수가 많아질수록 일반적으로 검색 성능이 향상된다고 여겨지지만, 데이터베이스의 성질에 따라 성능향상이 상이하고 특정 데이터베이스에 대해서는 오히려 성능에 해를 끼친다. 또한 대부분의 이미지 검색 시스템은 서로 다른 클래스는 서로 다른 키워드를 갖는다는 사실을 반영하지 않고 있다. 초 고차원 표현법 기반의 이미지 검색은 이미지 한 장이 초 고차원으로 기술되어 일반적인 기계학습 기법을 통하여 이러한 사실을 반영하는 것이 쉽지 않기 때문에, 대부분의 이미지 검색 시스템들은 모든 클래스에 대하여 동일한 하나의 가중치 벡터나 기준을 적용하고 있다. 우리는 이 세 가지 문제를 일관된 하나의 방법으로 해결하기 위하여 새로운 코드워드 가중치 방법론을 제안한다. 본 가중치 방법론은 기존 BoW 표현법이 갖는 코드워드별 독립성을 보존한다. tf-idf 가중치 방법론과 계층적 스코어링의 경우, 우리는 기존의 방법론들이 각각 사용하고 있는 정보인 코드워드의 문서 빈도와 레벨 외에 아무런 추가 정보를 사용하지 않고 이 방법론들의 성능을 향상시키는데 초점을 맞춘다. 코드워드의 문서 빈도와 레벨은 클래스 간 구별성과 밀접하게 연관되어있는 지표이기 때문에 우리는 코드워드별 이 두 가지 값을 중요 지표라 정의한다. 클래스 내부의 키워드를 고려하는 문제의 경우, 우리는 본 방법론을 통하여 한 클래스 내에서 코드워드들이 발생하는 통계적인 빈도에 따라 합리적인 가중치를 코드워드들에 할당할 것이다. 여기서 클래스 내부에서 코드워드별 발생 빈도의 분산이 이들의 중요성과 밀접한 관련이 있기 때문에, 우리는 이러한 종류의 값을 역시 중요 지표라 정의한다. 또한 한 코드워드가 가지는 중요 지표 값으로부터 가중치 값으로 변환해주는 가중치 매핑 함수를 정의하였다. 주어진 데이터베이스에서 구별성을 최대화 시키는 최적의 가중치 매핑 함수 모양을 결정하기 위하여 우리는 주어진 데이터베이스로 부터 무작위로 표본을 추출하여 가중치 매핑 함수의 모양을 최적화 기법으로 학습하였다. 문서 빈도와 레벨을 가중치로 매핑하는 함수의 경우 전체 클래스에 동일하게 적용되는 전역 가중치 벡터를 생성하고, 클래스 내부의 분산을 가중치로 매핑하는 함수의 경우 각 클래스별로 적용되는 서로 다른 가중치 벡터들을 생성한다. 우리는 제안한 방법론을 검증하기 위하여, UKbench 데이터베이스와 Oxford5K 데이터베이스를 이용해 성능을 평가하였다. 본 방법론은 온라인 상태에서 추가되는 계산 비용은 거의 없었으며, 코드워드의 문서 빈도와 레벨 외에 아무런 추가 정보 없이 기존의 tf-idf 가중치 방법론과 계층적 스코어링 방법을 능가하였다. 또한 우리가 제안한 클래스별 키워드를 고려하는 가중치 방법론의 경우도 이를 고려하지 않은 검색 성능을 크게 능가하였다.
