주로 image retrieval 을 처음 공부할 때, bag-of-visual-word 라는 방법으로 입문을 하고 합니다. BOVW 방법은 영상에서 local descriptor 를 추출하고 이를 대표하는 단어를 골라 사전을 만든 뒤, 각 단어의 분포를 global descriptor 로 사용하게 됩니다. 이와 같은 방법을 사용하게 되면 주로 precision이 높은, 즉, 예측한 것 중에 상당 수가 positive인 반면에 ground truth 에 포함된 positive 를 모두 찾아내지 못하게 됩니다. 다른 말로 하면 recall 이 낮게 나오게 되는 것입니다. 낮은 recall 은 local descriptor 를 추출할 때와 단어의 분포를 표현하는 quantization 과정에서 noise 를 포함하고 있는 것이 원인이 됩니다.
Text retreival 에서는 앞선 원인을 해결하기 위해 주로 query expansion 의 방식을 사용하는데, 본 논문에 저자는 이에 영감을 얻어 영상 도메인에서 새로운 query expansion 방식을 제안하게 되었습니다.
1. Real-time Object Retrieval
새로운 Query expansion 의 방식을 적용하기에 앞서 저자는 retrieval 베이스 모델을 BOVW 로 선택하였습니다. 영상에서 SIFT 를 이용하여 local descriptor 를 뽑았고 이를 K-means clustering 방식으로 중심점을 찾아 단어로 선정한 뒤 이의 분포로 global descriptor 를 표현했습니다. 그리고 Query 의 global descriptor 와 유사한 top k 벡터를 k nearest neighbor 방식으로 찾아내게 됩니다.
2. Spatial Verification
본 논문이 제안한 방식에서는 query 의 global descriptor 벡터와 top k 에 새로운 query expansion 방식을 적용하기 위해 spatial verification 을 먼저 적용합니다. 이는 query expansion 시 false positive 가 성능 향상에 방해가 되기 때문이며 RANSAC 을 통해 필터링 하게 됩니다. RANSAC 의 objective function 으로는 자유도가 6인 Affine transform 을 사용하며 두 영상의 local point 로 inlier 의 수를 계산해내게 됩니다. 저자가 밝히기를 경험적으로 inlier 의 수가 20개 이상이면 신뢰할 만하다 여겨 positive 로 사용하였고 top 1000 의 데이터 베이스 영상에서 20장 연속 postive 가 나오지 않으면 탐색을 멈추고 이전까지 찾았던 positive 만을 사용하게 됩니다.
3. Methods
- Query expansion baseline
저자는 제안한 새로운 query expansion 방식과 비교하기 위해 top 5 의 영상의 global descriptor 를 평균내어 baseline 으로 선정하게 되었습니다. 이때 spatial verification 은 적용하지 않았다고 합니다.
- Transitive closure expansion
Top k 의 후보 군에서 RANSAC 의 inlier 개수로 우선 순위 큐를 구성하게 됩니다. Inlier 수가 많은 순서 대로 이 global descriptor 와 가장 유사한 벡터를 찾게 되며 우선 순위 큐에 inlier 개수에 따라 적절한 위치에 넣어주며 처음 top k 에 대해 이러한 re-query 과정을 모두 거치면 반복을 멈추게 됩니다. 그리고 queue 의 가장 앞에 있는 후보를 사용하게 됩니다.
- Average query expansion
50개 이하의 top m (<50) 의 global descriptor 와 query 의 global descriptor 를 평균내게 됩니다. 단, 평균을 낼 때 후보군 영상을 query 에 역투영시켜 공통된 영역의 global descriptor 만을 사용하게 됩니다.
- Recursive average query expansion
이 방식은 average query expansion 의 성능을 올리기 위해 제안되었으며 평균을 내고 re-query 한 후보군에서 positive 영상이 30장 찾아질 때까지 반복하는 방식 입니다.
- Multiple image resolution expansion
저자는 후보군의 해상도 또한 query 의 object 가 잘 관찰될 수 있는 요인이라 생각하여 resolution 에 대한 expansion 도 추가 하였습니다. Top k 의 영상을 각각 query 에 Affine transform 으로 역투영 하여 겹치는 부분을 해상도의 변화 정도로 정의하고 이 변화의 구간을 각각 (0, 4/5), (2/3, 3/2), (5/4, inf) 로 나눠 Top k 의 영상을 분류한 다음 각각 average query expansion 의 방식을 적용해 re-query 하였습니다. 그리고 각 re-query 된 후보군들은 inlier 의 순서대로 top k 에 추가 하는 방식 입니다.
4. Experiment
Fig 2. 는 resolution expansion 방식으로 Oxford+Flickr1 데이터 셋에서 retrieval 하였을 때 precision recall curve 이며 좌측은 적용 이전, 우측은 적용 후 그래프 입니다. 논문에서 제안된 방법 중 하나인 resolution expansion 방식이 높은 precision 에서 높은 recall 을 얻어낼 수 있도록한 것을 확인할 수 있습니다.
Table 1. 은 제안된 방식들이 Oxford+Flickr1 데이터 셋과 Oxford+Flickr1+Flickr2 데이터 셋에서 각 클래스마다 보여주는 성능을 기록한 표입니다. 행 목록에서 ori 는 original query 를 사용했을 때, qeb 는 query expansion baseline, trc 는 transitive closure, avg 는 average query expansion, rec 는 recusive average query expansion 그리고 sca 는 resolution expansion 을 의미합니다. 제안된 각 방법들이 baseline 보다 좋은 성능을 내고 있으며 resolution expansion 의 경우 월등한 성능을 보여주는 것을 확인할 수 있습니다.
multiple image resolution expansion 방법에 대해 선뜻 잘 그려지지 않는데요. “affine transform 으로 역투영하여~” 하는 부분에 대해서 설명 좀 부탁드립니다.
query 와 top k 영상 간의 matching 포인트를 찾고 이 포인트 들에 대해 Affine transform 을 object function으로 하는 RANSAC 알고리즘을 돌려 최적의 Affine transform 을 구한 뒤, topk 영상을 변환하여 query 와 겹치는 영역을 찾는다는 의미 입니다.