근사 근접 이웃 인덱싱 기반의 유사 이미지 검색 방법에 관한 연구
A Study on Approximate Nearest Neighbor Indexing Based Image Retrieval Methods
- 주제어 (키워드) 근사 근접 이웃 , 인덱싱 , 유사 이미지 검색 , 벡터 유사도 , Approximate Nearest Neighbor , Indexing , Image Retrieval , Vector Similarity
- 발행기관 서강대학교 정보통신대학원
- 지도교수 박운상
- 발행년도 2022
- 학위수여년월 2022. 2
- 학위명 석사
- 학과 및 전공 정보통신대학원 데이터사이언스
- 실제 URI http://www.dcollection.net/handler/sogang/000000066616
- UCI I804:11029-000000066616
- 본문언어 한국어
- 저작권 서강대학교 논문은 저작권 보호를 받습니다.
초록 (요약문)
이미지 검색은 많은 곳에서 활용되고 있으며 이미지 데이터의 양도 방대해지고 있다. 이미지 검색 방법 중 현재 가장 많이 사용하는 방법은 딥러닝 모델의 CNN(Convolution Neural Network)을 활용하여 Feature(특성)을 수치화한 고정된 크기의 벡터 형태로 추출한 후, 벡터 간 거리 이용하여 유사도를 계산하는 것이다. 그러나 데이터 건수가 커짐에 따라 비교해야 할 벡터의 건수도 커짐으로써 검색 속도가 느려지고 구현 역시 힘들어지고 있다. 이를 보완 하기 위해 정확도를 조금 포기하고 검색 속도를 높여 검색의 효율을 높이는 Approximate Nearest Neighbor 연구가 계속되고 있다. 본 논문에서는 Approximate Nearest Neighbor 구현체를 활용하여 IVF, HNSW 인덱스를 클러스터 및 노드 연결 개수 등을 변경하며 어떤 알고리즘에서 빠른 검색 속도와 정확도를 갖는지 실험해 보고 양자화(Quantization)를 활용하여 정확도와 검색 속도를 해치지 않는 선에서 어느 정도까지 압축할 수 있는지 실험을 진행했다. 실험 결과 GIST1M 데이터 세트를 기준으로 HNSW 알고리즘의 32개 노드 연결로 생성한 인덱스에 SQ(Scalar uantization) 8로 압축을 진행했을 때, Brute force 대비 품질지표는 9% 낮아졌지만 80배 빠르고 인덱스 크기도 1/3로 줄어드는 것을 확인하였다. 실험의 최종 단계에서 해당 인덱스를 실제 이미지 검색엔진에 적용하였을 때도 유사 이미지가 잘 찾아지는 것을 확인하여 실험을 통한 인덱스 선택이 잘되었음을 검증하였다. 또한 이미지 검색을 위한 특성 추출을 위한 4가지 CNN 모델에 대한 비교 실험을 진행하여, 낮은 차원의 벡터를 만들어주면서 분류성능이 좋은 모델이 이미지 검색엔진을 만들 때 더 적합함을 확인하였다.
more초록 (요약문)
Image search is widely used, and the size of image data is increasing rapidly. Among the image search methods, the most commonly used method is to extract features in the form of fixed-sized vectors, quantify features using convolution neural networks (CNNs) of deep learning models and then calculate similarities using distances between vectors. However, as the number of data increases, the number of vectors to be compared increases, which slows the search speed and makes it challenging to implement the system. To compensate for those problems, research on Approximate Neighbor increases search efficiency by compensating accuracy to a certain degree. In this paper, we experimented with IVF and HNSW indexes to change the number of cluster and node connections and examined to what extent they can be compressed without compromising accuracy using quantization. Experiments on GIST1M's dataset showed that when compression was performed to SQ (Scalar Quantization) 8 on an index generated by 32 node connections of the HNSW algorithm, the quality index was 9% lower than brute force method, but the index size was reduced to 1/3 and search speed becomes 80 times faster. In the final stage of the experiment with real images, it was verified that the index based image search method retrieves similar images successfully. In addition, a comparative experiment was conducted on four different CNN models for feature extraction, confirming that a model with better classification performance with lower dimensional vector is more suitable to develop image search engines.
more