텍스트 정보와 시각 정보를 이용한 내용 기반 웹 이미지 검색 시스템 : A Content based Web Image Retrieval System using Textual and Visual Information
- 발행기관 서강대학교 대학원
- 지도교수 낭종호
- 발행년도 2007
- 학위수여년월 2007. 8
- 학위명 박사
- 학과 및 전공 컴퓨터학
- 식별자(기타) 000000104318
- 본문언어 한국어
목차
최근 웹 기술의 발달과 디지털 이미지 생산 장비의 발달로 인해 WWW에서 이미지의 양이 증가하고 있다. 당연히, 이러한 웹 이미지들에 대한 관리 및 검색에 대한 요구도 함께 증가하고 있다. 과거 다양한 이미지 검색에 대한 연구들이 있었지만 이러한 방법들을 웹 환경에 바로 적용한다면 웹 환경에서의 이미지가 가지고 있는 몇 가지 특징 때문에 검색 결과에 대한 만족도가 떨어지게 될 것이다. 따라서 기존의 이미지 검색
방법들을 웹 환경에 적용하기 위해서는 다음 두 가지 주요한 사항들을 고려해야만 한다. 하나는 의미 정보가 반영된 검색 결과를 만드는데 기반이 되는 웹 이미지 자동 주석의 정확성 확보 문제이고 또 다른 하나는 검색 시 적정한 수준의 검색 속도 확보 문제이다. 본 논문에서는 이러한 사항들에 대한 충분한 고려와 함께 설계 및 구현된 내용 기반 웹 이미지 검색 시스템을 제안한다. 첫 번째 문제 해결을 위해 웹 문서에 포함된 텍스트 정보와 이미지로부터 추출된 시각 정보를 함께 이용한 자동 주석 방법을 제안한다. 제안한 자동 주석 방법은 정확성을 높이기 위해 2단계 과정으로 이루어지는데, 1차로 웹 문서 내 이미지와 텍스트간 관계 정보를 통계적으로 분석하여 만든 규칙에 의해 후보 주석들이 선택된다. 이 과정에서 C4.5기반의 결정 트리가 규칙 유도 도구로서 사용되었다. 2차 과정은 시각 정보에 의한 필터링 과정으로, 개념 별로 이미지들을 모아 클러스터링한 후 개념과 연관 정도가 낮은 클러스터에 포함된 이미지들을 필터링한다. 실험에 의하면, 제안한 방법을 이용하였을 경우 선택된 주석의 평균 정확률과 재현률은 평균 92% 와 95%를 각각 보여주었다. 두 번째로 검색 속도 향상을 위해 고차원 데이터의 비트맵 표현으로 데이터 크기를 줄이고 비트 연산을 통해 계산량을 줄인 고차원 데이터 색인 방법 HBI (Hierarchical Bitmap Indexing) 을 제안한다. 또한 연관 피드백에 의한 재 검색 시간을 줄이기 위해 “Triangle Inequality” 에 기반한 별도의 색인 방법 FQD(Filtering by Query Difference) 을 함께 제안한다. 제안한 두 색인 방법은 함께 사용할 수 있으며 재 검색 시간을 더욱 단축시킬 수 있다. 실험에 의하면, 순차 검색에 비해 평균 3 ~ 4 배 검색 속도가 향상 되었으며 FQD를 이용한 재 검색 시에는 평균 5 ~ 6 배 검색 속도가 향상 되었다. 제안한 방법들을 적용하여 웹 이미지 수집 및 자동 주석 도구, 검색 서버, 검색 클라이언트로 구성된 프로토타입 검색 시스템을 구축하였고, 구축된 시스템이 원활히 동작하는 것을 확인함으로써 각 방법들이 실제 시스템에 적용 가능함을 입증하였다. 제안한 문제 해결 방법들과 시스템에 기반한다면 WWW 환경에서 효과적인 내용 기반 이미지 검색 시스템을 구축할 수 있을 것이다.
목차
Advent of new technologies in WWW(World Wide Web) and personal devices such as digital camera and mobile phone lead to increase the number of images on WWW. Consequently, the needs of efficient and effective mining, managing, and searching techniques for web images have been increased as well. Even though there have been many studies for image retrieval, they can not give satisfactory results of image retrieval in web environment. To adapt the traditional image retrieval techniques to the web environment, we should consider two main issues such that how to precisely annotate images collected from WWW to improve the quality of search results and how to make the system scalable to a large set of collected images. This thesis proposes a complete content based web image retrieval system by which images on WWW are automatically collected, managed, and searched with sufficient consideration for the above issues. To tackle the first issue, a rule based web image annotation method which improves the precision and recall of annotation is proposed. In this method, a set of rules with high estimated accuracy which determines whether or not a word can be the keyword of an image in a web page is inferred by the statistical analysis of the relationship between images and their keywords in web pages. C4.5 is used as a tool to infer these rules. Then, the modified hierarchical clustering based on the weighted combination of MPEG-7 visual descriptors proceeds to refine the annotation results. Upon experimental results, the precision and recall of annotation by the proposed method were about 92% and 95% respectively. To tackle the second issue, an efficient high dimensional indexing structure, called HBI (Hierarchical Indexing Method) is proposed. In this structure, each high dimensional feature is represented as some bitmaps with compact size. Using these compact representations, a lot of irrelevant images could be quickly filtered-out by a couple of simple XOR operations, and it helps to reduce the filtering process of similarity search in high dimensional data space. An optimization algorithm, called FQD (Filtering by Query Difference), for the similarity search with relevance feedback is also proposed. It reuses the previously calculated distances between the original query and all objects in the database when filtering the irrelevant objects in the successive search with modified query. It helps to further reduce the search time of similarity search with relevance feedback. Experimental results show that the similarity search using HBI is about 3 ~4 times faster than VA-File while guaranteeing the exact solutions, and FQD for relevance feedback helps to further reduce the elapsed time of successive similarity search compared to the one for the first search. To show the superiority of the proposed algorithms, we build up a prototype system for content based web image retrieval based on the proposed algorithms. It consists of
a web image miner that periodically collects images on WWW and annotate them, a search server that manages the collected images and their visual and textual features, and a search client that generate a query object and helps to brows the images from the results. The proposed algorithms and system could be used as a reference model to build a content based web image retrieval system.
