Deep Learning of Binary Hash Codes for Fast Image Retrieval

 

1. Introduction

- Content-based image retrieval (CBIR)은 image content 분석을 통해 유사한 이미지를 찾는 것을 목표로 함

- CBIR에서 image representation과 계산 비용은 둘 다 중요한 역할

- large database에서 빠른 검색은 더욱 필요성이 증가하고 있음

 

* CBIR에서 deep CNN을 이용한 사례

- deep CNN : object detection, image classification, segmentation 등 다양한 vision task에서 좋은 성능을 보임

- 이는 deep CNN이 mid-level image representation을 학습하는 능력이 있음을 의미함

- [14] : image retrieval 위해 7번째 layer의 feature vector를 이용하여 ImageNet에서 뛰어난 성능 보임
         그러나 4096 차원의 두 벡터 사이의 유사성을 직접 계산하는 것은 비효율적

- [1] : CNN feature를 PCA를 이용하여 압축하고, 차별화된 차원 감소 방법을 이용하여 좋은 성능을 보임

 

* 빠른 검색을 위한 방법

- hashing based method : 고차원 feature를 저차원 공간으로 투영시키고, compact binary code를 생성

- 생성된 binary code에 binary pattern matching이나 Hamming distance measurement 이용하면 빠른 이미지 검색 가능 & 계산 비용 극도로 감소 & 검색 효율성 최적화 가능

- 대부분의 이런 방법들은 similarity matrix를 이용하는 pair-wised method, 이는 large-dataset에는 맞지 않음

 

* key question

- large-scale 데이터 베이스로부터 어떻게 효율적으로 연관성 있는 데이터를 검색할 수 있을까

- hasing을 얻는 것에 deep CNN의 이점을 활용할 수 있을까

- pair-wised method 대신에 deep CNN으로부터 직접적으로 compact binary code를 생성할 수 있을까

 

* 본 논문 제안 방법론

- image representation과 binary hashing code를 동시에 학습하는 supervised deep CNN 모델 제안

- binary code는 class label의 가장 중요한 특징이 되는 latent concept를 나타내는 hidden layer에 의해 학습됨

- 즉 pair-wised input 필요 없음

- deep CNN의 이점을 받아 point-wise manner을 통해 binary hashing code를 학습함

- 전통적인 방법에 비교하여 데이터 사이즈에 쉽게 scalable하므로 large 데이터셋에 적합함

2. Releted Work

 

3. Method

3-1. First component

- [14]에서 제안한 large-scale ImageNet dataset supervised pre-trained CNN 모델 사용

- 1000개의 object class와 1.2 million개의 이미지 데이터로 구성된 데이터셋으로 학습

3-2. Second component

- 최근 연구에서는 입력 이미지에 의해 유도된 F6~F8 layer의 feature activation이 시각적 시그니처 역할을 할 수 있음을 보여줌

- 이러한 mid-level image representation의 사용은 다양한 task에서 좋은 성능 보임

- 그러나 고차원 벡터인 이 시그니처들은 large 데이터셋에서 image retrieval를 위해서는 비효율적

- 계산 비용을 줄이는 실용적인 방법은 feature vector를 binary code로 변환하는 것

 

- domian specific image representation과 hash-like (or binary coded) function을 동시에 학습시키는 것이 목표

- 마지막 분류 layer인 F8이 h개의 hidden attribute가 on/off인지(binary)에 의존한다고 가정

- 즉 유사한 binary activation을 가진 이미지가 같은 label로 분류

 

- F7과 F8 사이에 fully connected layer인 latent layer H를 넣음

 

- H는 F7로부터 풍부한 feature의 abstraction을 제공할 뿐 아니라, mid-level feature와 high-level 의미론을 연결

- H는 sigmoid function을 이용하여 activation은 {0, 1}로 근사됨

 

- target-domain 데이터셋으로 제안한 네트워크 fine-tune

- deep CNN의 초기 가중치는 first component와 같음

- latent layer H와 마지막 분류 layer인 F8의 초기 가중치는 랜덤하게 초기화

 

- The initial random weights of latent layer H acts like LSH which uses random projections for constructing the hashing bits. The codes are then adapted from LSH to those that suit the data better from supervised deep-network learning. (? 이해 안됨)

 

- deep CNN model에 큰 수정 없이 목표 달성

3-3. Third component

- coarse-to-fine search strategy을 이용하여 빠르고 정확한 image retrieval

 

3-3-1. Coarse-level Search

- latent layer 결과 유사한 binary activation을 가진, 즉 유사한 high-level 의미론적 의미를 가진 후보 set를 생성

 

- 이미지가 주어지면 이미지 시그니처를 의미하는 latent layer의 output을 추출

- threshold에 의해 activation을 binarizing하여 binary code 얻음

- retrieval을 위한 모든 이미지의 binary code (H1 ... Hn) 저장

- 주어진 query image의 binary code Hq도 추출

- Hq와 retrieval 이미지 Hi 사이의 Hamming distance가 일정 threshold보다 낮다면 해당 이미지 i를 후보 pool P에 넣음

 

3-3-2. Fine-level Search

- mid-level image representation에 기반하여 유사한 외관을 가진 이미지들을 필터링하여 similarity ranking 매김

 

- query 이미지와 후보 pool P(m개)가 주어지면 F7 layer로부터 feature vector 추출하여 Vq와 Vi(i=1...m) 형성

- Vq와 Vi 사이의 Euclidean distance를 유사도 level로 정의, 즉 Euclidean distance가 짧을수록 유사함을 의미

- 후보 pool의 모든 이미지와 query 이미지 사이의 Euclidean distance을 오름차순으로 정렬, 랭킹 부여

- query 이미지와 유사한 top k ranked 이미지 retrieval 가능

4. Experimental Results

4-1. Datasets

* MNIST dataset

- category 10개 / training image 60000 / test image 10000

 

* CIFAR-10 dataset

- category 10개 / training image 50000 / test image 10000

 

* Yahoo-1M dataset

- shopping product image

- category 116개 / 총 image 1124087

4-2. Evaluation Metrics

- ranking based criterion 사용

- Rel(i)는 i번째 ranked image와 query image가 같은 label이면 1, 아니면 0

4-3. Results on MNIST Dataset

- deep CNN을 새로운 domain에 맞추기 위해 F8 layer를 10-way softmax로 수정함

- deep CNN의 latent layer의 효과를 측정하기 위해 latent layer의 뉴런 수 h를 48, 128로 설정

- deep CNN을 MNIST 데이터셋에 맞게 학습시키기 위해 SGD 적용

- 위 표는 latent layer와 다른 여러개의 모델의 test error 결과

- 48 latent node일 때 test error가 0.47%로 좋은 성능 보임

- 다른 모델은 분류 task를 위해 최적화된 반면, 본 논문에서 제안 모델은 image retrieval을 위해 디자인 된 것인데 좋은 성능을 보인 것

- 48 latent node가 128 latent node일 때 보다 더 낮은 error rate, 아마도 더 많은 node가 overfitting을 유발했기 때문

- 48 latent layer의 binary code와 hamming distance를 이용하여 관련된 이미지를 검색한 retrieval 평가

- 위 그래프는 supervised 방법(KSH, MLH, BRE, CNNH, CNNH+), unsupervised 방법(LSH, SH, ITQ)과 비교

- 검색한 이미지의 수를 변화시켰을 때(top k의 k를 변화시킨 듯?) 제안 모델이 가장 안정적인 성능

- pair-wised similarity information을 decomposition을 통해 hashing function을 얻는 CNNH+에 비해 1% 더 좋은 성능

- 오직 class label 정보만 필요한 우리 point-wised 방법(이게 왜 point-wised?)이 더 효과적이고 좋은 성능

- 48 latent node와 128 latent node 모두 image retrieval을 위한 informative binary code를 잘 학습함

4-4. Results on CIDAT-10 Dataset

- deep CNN을 새로운 domain에 맞추기 위해 F8 layer를 10-way softmax로 수정함

- deep CNN의 latent layer의 효과를 측정하기 위해 latent layer의 뉴런 수 h를 48, 128로 설정

- deep CNN을 CIFAR-10 데이터셋에 맞게 fine-tune 진행

- 제안 모델이 다른 모델에 비해 accuracy 꽤 좋은 성능

- deep CNN에 binary latent layer를 더하는 것이 분류 성능을 크게 변화시키지 않음을 의미

- 48 latent layer의 binary code와 hamming distance를 이용하여 관련된 이미지를 검색한 retrieval 평가

- 제안 모델이 모든 supervised 방법과 unsupervised 방법에 비해 좋은 성능

- CNNH+에 비해 30% 더 좋은 성능

- hidden concept를 나타내는 latent layer를 사용하는 것이 효과적인 binary code를 학습하는 실용적인 방법

- 48 latent node에서 128 latent node로 증가시켰을 때 더 외관이 유사한 이미지가 검색됨

- h=128일 때 더 말의 머리 이미지와 유사한 이미지가 검색됨

4-5. Results on Yahoo-1M Dataset

- 이 데이터셋은 다양한 종류의 제품 이미지와 사람 유무, 사람 포즈와 같은 noisy background로 이루어져 있음

- F8 layer의 neuron 수는 116개, latent layer의 neuron 수 h는 128로 설정함

- deep CNN을 Yahoo-1M 데이터셋에 맞게 fine-tune 진행

- 116 category clothing 분류 task에서 83.75% accuracy 도달

- 위 그림의 Mary Janes 이미지와 같이 예측이 잘못된 몇몇 경우는 해당 이미지가 여러 카테고리 사이에서 모호하기 때문인 것으로 추정

- This is demanding to achieve by using previous pairwised-data approaches due to the large time and storage complexity. (? 결국 여기서 우리도 pair-wised 방법을 썼다는거야?)

 

- AlexNet : pre-train CNN의 F7 features [14] (얘도 데이터셋에 맞게 fine tune 한거겠지? 그럼 차이는 latent layer 뿐?)

- Ours-ES : 제안 network의 F7 features

- Ours-BCS : 제안 network의 latent binary code

- Ours-HDS : 제안 network의 F7 features와 binary code 둘 다

 

- F7 features를 retrieval에 사용하는 경우 L2-norm distance에 기반한 exhaustive search (or linear search)

- binary code를 사용하는 경우 Hamming distance 기반

- F7 features & binary code 사용하는 경우 coarse-to-fine hierarchical search

- 랜덤하게 1000개의 이미지를 뽑아 같은 데이터셋 내에서 유사한 이미지 검색

 

- 제안 방법론이 기존 AlexNet feature 보다 훨씬 좋은 성능 보임

- 처음에는 BCS보다 ES, HDS가 더 좋은 retrieval precision 보임

- 일정 이후부터는 ES보다 BDS가 더 좋고 안정적인 retrieval precision 보임

- 이것은 학습된 binary code가 높은 식별력과 유용한 정보를 담고 있음을 나타냄

- HDS는 BCS와 ES를 상호보완하며 전반적으로 가장 좋은 retrieval precision 보임

- 위 그림은 각 모델 별 top 5 retrieved 이미지 보여줌

- AlexNet은 매우 다양한 이미지를 검색함

- 제안 모델 3가지의 경우는 query 이미지와 같은 label의 더 유사한 이미지를 검색함

- binary code를 이용하기 때문에 BCS가 매우 빠른 검색 속도를 보임

- BCS는 전통적인 exhaustive 방법에 비해 971.3배 빠른 속도를 보임 

5. Conclusions

- 빠른 image retrieval을 위해 hash-like binary code를 생성하는 간단하지만 효과적인 deep learning framework 제안

- domain specific image representation과 hash-like function을 동시에 학습시키기 위해 deep CNN에 latent-attribute layer 추가

- pair-wised 유사성에 의존하지 않아 데이터셋 사이즈에 굉장히 scalable함

- 실험 결과 deep CNN에 간단한 수정만 했으나 이전 best retrieval 결과에 비해 MNIST는 1%, CIFAR-10은 30%의 retrieval precision을 향상시킴

- 1 million shopping image의 large-scale 데이터셋에서 제안 방법론의 확장성과 효과를 보여줌

---

본 논문 : Lin, K., Yang, H. F., Hsiao, J. H., & Chen, C. S. (2015). Deep learning of binary hash codes for fast image retrieval. IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, 2015-October, 27–35. https://doi.org/10.1109/CVPRW.2015.7301269

 

[1] : A. Babenko, A. Slesarev, A. Chigorin, and V. Lempitsky. Neural codes for image retrieval. In Proc. ECCV, pages 584– 599. Springer, 2014. 

[14]: A. Krizhevsky, I. Sutskever, and G. E. Hinton. ImageNet classification with deep convolutional neural networks. In Proc. NIPS, 2012.

 

* Hamming distance

- 두 개의 길이가 같은 문자열 사이의 거리를 측정

- 둘 중 하나의 문자열에서 몇 개의 문자를 바꿔야 두 문자열이 같아지느냐

- 같은 위치에 있는 두 문자를 비교해 다른 문자의 수를 세는 것

- 연속성은 고려하지 않음

- 주로 에러 감지에 쓰임

---

개인적 리뷰

- coarse-to-fine search strategy 간단한 아이디어 같은데 결과도 좋고 흥미롭다

- CNN의 중간 feature activation을 활용할 순 없을까 고민이었는데, convolution layer는 아니였지만 그래도 모델 중간에 나오는 feature를 활용하려는 점이 흥미롭다

- image retrieval의 최종 목적은 뭐지..? 분류랑은 다른 task로 구분하는 것 같은데 분류가 목적이 아니면 유사한 image를 찾는 것이 무슨 의미가 있지..? 이쪽 분야를 좀 더 공부해봐야 할 듯

- pair-wised method가 뭘까 궁금