접수일자: 2012년 10월 6일 심사(수정)일자: 2012년 10월 20일 게재확정일자 : 2013년 4월 10일
†Corresponding author
본 연구는 정부(교육과학기술부)의 재원으로 한국연구재단 의 지원을 받아 수행된 기초연구사업의 연구 결과입니다.
(No.2012-008062) 또한, 본 연구는 지식경제부 및 한국산업 기술평가관리원의 산업융합원천기술개발사업(정보통신)의 일환으로 수행하였습니다. (KI001810041244, 스마트TV 2.0 소프트웨어 플랫폼) 연구비 지원에 감사드립니다.
This is an Open-Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0) which permits unrestricted non-commercial use, dis- tribution, and reproduction in any medium, provided the original work is properly cited.
PCA-SIFT의 차원 중복점을 이용한 이미지 기반 이미지 검색 시스템
Image-based Image Retrieval System Using Duplicated Point of PCA-SIFT
최기룡*․정혜욱*․이지형*†
GiRyong Choi, Hye-Wuk Jung and Jee-Hyoung Lee†
*성균관대학교 컴퓨터공학과
†Department of Computer Engineering, Sungkyunkwan University
요 약
최근 멀티미디어 정보가 보편화됨에 따라 인터넷에서 이미지를 기반으로 정보를 검색하려는 다양한 시도가 진행되고 있다.
그러나 이미지에는 다양한 패턴이 포함되어 있기 때문에 정확하게 원하는 이미지를 찾는 것은 아직 어려움이 많다. 본 논 문에서는 인터넷 쇼핑몰의 상품검색을 효율적으로 할 수 있는 이미지 기반 검색 시스템을 제안한다. 제안된 검색 방법은 SIFT(Scale Invariant Feature Transform) 알고리즘을 이용하여 이미지 검색을 위한 특징을 추출하고, PCA-SIFT를 이용 하여 여러 차원에서 키포인트의 매칭을 반복하여 누적 후 사용자가 원하는 상품을 찾아준다. 제안된 방법의 효율성을 검증 하기 위해, 다양한 패턴의 상품 이미지를 이용하여 기존 SIFT, PCA-SIFT 방법과 제안된 방법을 비교한 결과, 상표가 포 함되지 않은 이미지의 경우 제안방법이 가장 높은 변별력을 보였으며, 효과적인 이미지 검색의 가능성을 보였다.
키워드 : SIFT, PCA-SIFT, PCA, CBIR, Image Matching, Dimension Reduction
Abstract
Recently, as multimedia information becomes popular, there are many studies to retrieve images based on images in the web. However, it is hard to find the matching images which users want to find because of various patterns in images. In this paper, we suggest an efficient images retrieval system based on images for finding products in inter- net shopping malls. We extract features for image retrieval by using SIFT (Scale Invariant Feature Transform) algo- rithm, repeat keypoint matching in various dimension by using PCA-SIFT, and find the image which users search for by combining them. To verify efficiency of the proposed method, we compare the performance of our approach with that of SIFT and PCA-SIFT by using images with various patterns. We verify that the proposed method shows the best distinction in the case that product labels are not included in images.
Key Words : SIFT, PCA-SIFT, PCA, CBIR, Image Matching, Dimension Reduction
1. 서 론
정보통신기술의 발전은 사람들에게 많은 편리함을 가져 다주었다. 사람들은 언제, 어디서나 네트워크에 접속하여 원 하는 정보를 찾을 수 있게 되었고, 손쉽게 목적을 이룰 수 있게 되었다. 이에 따라 사용자들의 요구사항은 더욱 증가 하여 기존의 텍스트 기반 데이터뿐 만 아니라 멀티미디어 형태와 같이 다양한 형태의 정보를 요구하고 있다. 기존 이 미지와 같이 멀티미디어 정보를 검색하는 방법은 텍스트 기 반 이미지 검색방법인 TBIR(Text-based image retrieval) 과 이미지가 갖는 모양, 색상, 패턴 등의 내용을 기반으로 검색하는 CBIR(Content-based image retrieval) 방법이 있 다[1,2]. TBIR은 사용자가 입력한 특정 키워드가 해당 이미 지를 포함한 웹페이지에 존재하는 경우 검색 결과로 보여주 게 되는 방법이다. 이러한 방법은 사용자가 찾고자 하는 이 미지의 다양성을 고려하지 않았기 때문에 사용자가 원하는
그림 1. 이미지 검색 시스템의 전체 프로세스.
Fig. 1. Whole process of image matching system.
이미지를 찾아주는데 한계가 있다. 반면, CBIR은 다양한 이 미지의 내용 정보를 표현하고 검색에 사용하기 때문에 사용 자들과의 상호작용을 통한 검색결과를 도출해 낼 수 있다 [3]. 그러나 구글 이미지 검색과 같은 CBIR을 이용한 검색 시스템은 이미지를 이용하여 검색이 가능하지만, 단순 검색 에 불과해 사용자와의 상호작용은 이끌어내지 못하고 있다 [4]. 또한 본 논문의 선행 연구인 SIFT(Scale Invariant Feature Transform) 특징을 이용한 쇼핑몰의 이미지 기반 검색 시스템은 사용자가 직접 촬영한 이미지를 이용하여 검 색 할 수 있어 사용자와 상호작용을 할 수 있지만, 이미지 검색의 매칭률이 높지 않은 단점이 있다[7].
본 논문에서는 PCA-SIFT 기법을 이용하여 보다 정확하 게 원하는 상품을 찾을 수 있는 방법을 제안한다.
PCA-SIFT는 SIFT의 특징점 추출 시 더 많은 차원으로 분할하여 낮은 차원으로 줄이는 방법으로 빠른 연산속도와 높은 정확성을 가지는 장점이 있다. 본 논문에서는 이러한 PCA-SIFT 방법에 매칭을 실시하는 차원을 분할하여 매칭 을 반복하고, 반복값을 누적하여 더 효율적인 검색법을 모 색하였다. 그리고 실험을 통하여 개선된 알고리즘이 기존 알고리즘에 비해 얼마나 효율적인지를 분석해 보았다.
본 논문은 다음과 같은 순서로 구성되어 있다. 2장에서는 SIFT 방법 및 이를 개선한 관련연구에 대해 기술한다. 3장 에서는 본 연구에서 제안하는 다중 차원 PCA-SIFT 방법 에 대해 설명하고, 4장에서는 다양한 이미지를 이용한 실험 결과를 제시한다. 5장에서는 결론 및 향후 연구에 대해 기 술한다.
2. 관련연구
David Lowe는 회전과 크기 변환에 강인한 이미지 특징 점을 추출하고, 이를 이용하여 이미지를 매칭하는 알고리즘 인 SIFT를 제안하였다[5,6]. SIFT는 다음과 같이 4단계로 구분 할 수 있다.
(1) 스케일(scale)과 키포인트(keypoint)의 산출 (2) 키포인트의 지역화(localization)
(3) 오리엔테이션(orientation) 산출 (4) 키포인트 특징점(descriptor) 기술
키포인트는 x좌표, y좌표, 스케일과 오리엔테이션, 그리 고 128차원으로 이루어진 특징점으로 구성된다. 이후 매칭 단계에서 키포인트간 특징점들의 유클리드 거리의 합을 이 용하여 매칭을 수행한다. SIFT 이미지 매칭 방법은 매칭률 이 좋은 편이고 사진의 회전이나 크기 변환에 크게 영향을 받지 않는다는 장점이 있지만, 비용이 크고 물체의 어핀 (affine) 변화에 민감하다는 문제점이 있다.
PCA(Principal Component Analysis)는 고차원의 데이 터들을 분산이 가장 큰 방법으로 줄이는 차원축소 기법이 다. PCA 방법은 데이터 매트릭스의 무게중심이 원점이 되 도록 이동시킨 후, 매트릭스의 공분산(covariance)을 구한 다. 여기서 나온 공분산의 고유값(eigenvalue)과 고유벡터 (eigenvector)를 구하고, 고유값에 따라 고유벡터들을 정렬 한 후, 축소를 원하는 차원수 만큼의 고유벡터를 추출하여 매트릭스로 만든다. 원점으로 이동시킨 데이터 매트릭스와 새로 구한 매트릭스를 곱한 뒤, 이를 다시 원래위치로 이동 시킴으로서 차원축소가 완료된다.
PCA-SIFT는 PCA기법을 SIFT에 적용한 방법으로서, SIFT의 3단계까지의 방법은 동일하다[9]. SIFT에서 키포 인트를 중심으로 128차원의 특징점을 기술한데 반해, PCA-SIFT에서는 41×41의 패치를 추출한다. 여기서 추출 된 패치와 미리 계산된 고유벡터 알고리즘을 곱하여 36차원 으로 축소된 특징점을 구할 수 있다. PCA-SIFT는 SIFT에 비해 차원수가 적어 비교가 빠르다는 장점이 있다. 그리고 SIFT에 비해 어핀 변화에 강인하다는 장점이 있으나, 동일 그림의 회전, 크기 변화 감지에는 SIFT보다 낮은 성능을 보여준다[10].
3. 개선된 PCA-SIFT 알고리즘을 이용한 이미지 매칭
본 논문에서는 다중 차원 PCA-SIFT를 적용시켜 더 효 율적인 이미지 기반 검색 시스템을 제안한다. 시스템은 다 음과 같다. 사용자는 원하는 서비스를 위하여 이미지를 서 버로 전송하고, 서버는 DB에서 해당 이미지를 매칭하여 사 용자에게 정보를 전송한다. 단순한 텍스트 데이터가 아닌 이미지 정보를 그대로 전송해서 답해주기에 사용자는 더 효 율적인 서비스 이용이 가능하다[8].
그림 1은 제안하는 방법의 전체적인 프로세스를 나타내 며 그 순서는 다음과 같다.
① 사용자가 서비스에 이용할 상품을 발견.
② 사용자가 해당 상품의 이미지를 서버로 전송.
③ 서버는 수신한 이미지의 특징을 추출.
④ 서버는 추출한 특징을 바탕으로 DB에 저장되어 있는 특징과 비교하여 이미지 매칭을 실시해 상품을 검색.
⑤ 서버는 해당 상품의 정보를 웹서비스(web service)와 함께 사용자에게 전송.
⑥ 사용자는 정보를 받고 서비스를 이용.
3.1 다중 차원 PCA-SIFT 알고리즘
입력된 이미지는 SIFT 알고리즘에 따라 키포인트를 찾 고, 키포인트의 스케일과 오리엔테이션을 구하는 데까지 진 행한다. 추출된 키포인트를 이용하여 특징점을 찾기위해
매칭방법 평균 매칭 순위 평균 매칭
표준편차 최상위 매칭 수 유효 매칭 수 항목 별 표준편차 평균
SIFT 1.83 5.11 63 68 13.86
PCA-SIFT 27.73 19.61 6 13 2.26
다중 차원
PCA-SIFT 31.69 20.99 4 12 7.31
표 1. 상표를 포함한 이미지에 대한 매칭 결과.
Table 1. Matching result of images including product labels.
PCA-SIFT 알고리즘에 따라 41×41의 패치를 PCA에 적용 하여 차원을 줄인다. PCA-SIFT 알고리즘에 의하면 적용 후의 차원은 36차원이 되어야 하지만, 다중 차원 PCA-SIFT에서는 다양한 차원으로 변환하여 여러 차원의 특징점들을 저장한다. 허용 최대 차원을 n, 변동 계수를 ,
일 때 로 만드는 정수인 상수를 라 할 때,
차원축을 포함할 때의 반복 횟수 는 식 (1)과 같이 정 의하였다.
(1) 이 때, 는 ≦ ≦ 의 조건을 만족하여야 한다.차원축이 포함된 특징점들은 번 매칭을 반복수행 하게 되므로, 가 같은 중 가장 큰 값들이 특징점의 차원이 된다.
3.2 이미지 매칭 방법
이미지 매칭은 PCA로 축소된 특징점 집합과, DB에 저 장된 상품의 정보를 이용하여 수행하였다. 이미지 과 이 미지 를 비교할 때, 의 키포인트 과 의 키포인트
의 특징량의 유클리드 거리 제곱 값(Squared euclidean distance)를 사용하여 매칭한다. 의 특징량을 , 의 특징량을 라 하면 유클리드 거리 는 식 (2)와 같이 표현할 수 있다.
(2) 이와 같이 산출된 를 이용하여, KNN(K-Nearest Neighbor)기법을 사용하여 이미지 사이에 대응하는 키포인 트들을 매칭한다. 이때, K=2를 사용하여 입력 이미지의 키 포인트에서 가장 가까운 키포인트 외에도, 두 번째로 가까 운 키포인트를 찾아내어, 가장 가까운 키포인트와 비율을 비교하여 임계치 이하면, 입력 이미지의 키포인트와 가장 가까운 키포인트는 매칭된다고 볼 수 있다. 이러한 작업을 준비된 특징점 집합의 수만큼 각각의 차원에서 반복하고 이 를 누적하여 가장 매칭 수가 높은 이미지의 상품이 가장 유 효한 상품으로 판별하였다.
4. 실험 방법 및 결과
입력 이미지군과 DB 이미지군을 준비하여 각각의 이미 지에 대해 SIFT, PCA-SIFT, 다중 차원 PCA-SIFT 기법 으로 매칭을 실시하고, 그 결과를 비교 분석하는 실험을 실 시하였다. 다중 차원 PCA-SIFT는 , 를 사용 하여 실험하였다. 입력 이미지군은 상품의 사진을 찍어 별 도의 처리 없이 사용하였으며, DB 이미지군은 동일 상품의 다른 이미지를 배경을 지운 채 사용하였고, 각각의 사진쌍 들은 서로 다른 각도에서 촬영되었다. 이미지는 총 294개를 사용하였다. 각각의 이미지군은 상품에 이름이 나와 있는 경우와 상품에 이름이 나와있지 않은 경우의 두 부류로 나 누어 실험을 진행하였다.
표 1은 이미지에 이름이 들어있는 이미지들, 표 2는 이미 지에 이름이 들어있지 않은 이미지들을 매칭한 결과이다.
각 표에서 평균 매칭 순위는 입력 이미지군의 이미지에 대 응하는 DB이미지군의 이미지로의 매칭의 순위의 평균이고, 평균 매칭 표준편차는 이때의 표준 편차를 의미한다. 최상 위 매칭 수는 매칭 결과에 대응되는 이미지로 매칭 순위 1 위를 차지한 경우의 수이고, 유효 매칭 수는 대응 이미지로 의 매칭이 5위내에 들었을 경우의 수이다. 항목 별 표준편 차 평균은, 각각의 입력 이미지가 행하는 매칭의 결과로 나 온 키포인트의 수로 표준편차들을 구한 후, 모든 이미지에 대해 표준편차의 평균을 구한 값이다.
표 1의 SIFT 알고리즘을 사용한 결과를 살펴보면, 이미 지 매칭도가 매우 높은 것을 평균 매칭 순위가 1.83이라는 결과를 통하여 알 수 있다. 항목 별 표준편차 평균도 13.86 으로 매우 높아 다른 이미지와의 구분을 쉽게 할 수 있다.
반면, PCA-SIFT와 다중 차원 PCA-SIFT는 모두 SIFT에 비해 현저히 낮은 성능을 보여주었다.
표 2에서는 SIFT 알고리즘을 적용한 경우 평균 매칭 순 위가 23.17으로, 표 1에 비해 크게 낮아졌음을 알 수 있다.
또한 항목 별 표준편차 평균 역시 1.28로 표 1에 표시한 결 과에 비해 크게 낮아졌음을 알 수 있다. PCA-SIFT를 적용 한 경우, 평균 매칭 순위와 유효 매칭 수가 SIFT보다 낮아 매칭 성공률은 SIFT보다 약간 낮으나, 항목 별 표준편차 평균이 SIFT보다 높아 변별력이 더 높다. 다중 차원 PCA-SIFT의 경우, 평균 매칭 순위는 PCA-SIFT보다 낮 지만, 유효 매칭 수에 있어서는 PCA-SIFT보다 좋은 성능 을 내었다. 항목 별 표준편차 평균은 SIFT, PCA-SIFT에 비해 큰 폭으로 상승해 변별력이 크게 늘어난 것을 알 수 있다.
매칭방법 평균 매칭 순위 평균 매칭
표준편차 최상위 매칭 수 유효 매칭 수 항목 별 표준편차 평균
SIFT 23.17 19.57 3 18 1.28
PCA-SIFT 30.86 23.19 4 10 1.85
다중 차원
PCA-SIFT 34.44 23.13 4 12 5.73
표 2. 상표를 포함하지 않은 이미지에 대한 매칭 결과.
Table 2. Matching result of images without product labels.
그림 2. 상표를 포함하는 이미지에 대한 매칭 결과비교.
Fig. 2. The comparison of matching result to an image including a product label.
그림 3. 상표를 포함하지 않는 이미지에 대한 매칭 결과비교.
Fig. 3. The comparison of matching result to an image without a product label.
표 1과 표 2를 통해 볼 때, SIFT는 이미지에 이름이 포 함되어 있을 경우, 그 부분을 키포인트로 잡아 해당 상품을 정확하게 인지하는 것이 가능하였다. 반면, PCA-SIFT와 다중 차원 PCA-SIFT는 이름이 있는 이미지 매칭에 효율 적이지 않았다. 하지만 이미지에 이름 등을 특징할 수 있는 확실한 표기가 없는 경우, SIFT 알고리즘은 그렇지 않은 경우에 비해 현저히 낮은 성능을 보여주면서, 대응되는 이 미지와 그렇지 않은 이미지 간의 차이가 협소하여 변별력이 떨어지는 것을 알 수 있다. PCA-SIFT는 표 1과 표 2 사이 에 큰 차이는 나지 않지만 약간의 성능 감소가 일어남을 알 수 있다. 다중 차원 PCA-SIFT는 표 2에서 SIFT에 비해 부족한 성능을 보였지만 항목 별 표준편차 평균이 높아 상 대적으로 뛰어난 변별력을 나타냄을 확인하였다. 그림 2는 상표를 포함하는 이미지를 이용한 매칭 결과를 비교한 것이 다. 그림 2(a)는 SIFT를 이용한 실험결과로 이름이 있는 부 분이 정확하게 매칭되는 것을 보여준다. 그러나 다중 차원 PCA-SIFT를 적용한 경우 그림 2(b)와 같이 매칭 오류로 인해 많은 outlier가 발생하여 매칭률이 낮다. 이와는 반대 로 이미지에 상표가 포함되어있지 않는 경우 그림 3(a)와 같이 SIFT를 이용했을 때는 키포인트가 추출되지 않기 때 문에 매칭에 실패했다. 그러나 다중 차원 PCA-SIFT를 적 용한 경우 그림 3(b)와 같이 키포인트를 찾아 매칭에 성공 하였다. 이와같이 본 논문에서 제안한 방법은 다중차원 PCA-SIFT을 사용했기 때문에 일반적인 SIFT 방법에서 키포인트를 찾지 못하는 이미지로부터 키포인트를 찾아 매 칭이 가능하다.
5. 결론
본 논문에서는 기존 PCA-SIFT의 개선된 알고리즘을 제 안하고, 선행연구에서 제안된 이미지 기반 검색 시스템에 적용하여 그 효율성을 알아보았다. 이미지 내에 상표가 포 함되어 있어 사물의 특징이 명확하게 나타날 경우에는 SIFT가 굉장히 효율적인 알고리즘을 확인하였다. 그러나 반대의 경우에는 다중 차원 PCA-SIFT가 비슷한 정확성을 가지면서도 변별력이 높음을 확인 하였고, 이미지의 수가 더욱 많아져도 대응되는 이미지를 찾을 수 있는 확률이 높 아질 것이라 예상할 수 있다. 따라서 이미지 기반 검색 시 스템에서는 SIFT 알고리즘 적용 후에도 이미지의 선택이 명확하지 않을 경우에 다중 차원 PCA-SIFT를 사용하는 것이 효율적이라 할 수 있다. 향후에는 낮은 매칭 확률 개
선, 특징점 계산 및 매칭 시간 단축 등에 대한 연구를 지속 할 예정이다.
References
[1] Imran Shafiq Ahmad, “Text-based image indexing and retrieval using formal concept analysis,” In KSⅡ transactions on internet and information systems, vol.2, no.3, pp. 251–267, 2008.
[2] Town and Sinclair, “Language-based querying of image collections on the basis of an expensible ontology,” Int. J. Image Vision Computer, vol.22, no.3, pp. 251–267, 2004.
[3] Smeulders, Arnold W. M.; Worring, Marcel; Santini, Simone; Gupta, Amarnath; Jain, Ramesh,
“Content-Based Image Retrieval at the End of the Early Years,” IEEE Transactions on Pattern Analysis and Machine Intelligence archive, vol.22, no.12, pp. 1349-1380, 2000.
[4] Google, “Google 이미지 검색”, Available:
http://www.google.co.kr/imghp, [Accessed: October 24, 2012].
[5] D. Lowe, “Object Recognition from Local Scale -Invariant Features,” In International Conference on Computer Vision, pp. 1150-1157, 1999.
[6] D. Lowe, “Distinctive Image Features from Scale- Invariant Keypoints,” International Journal of Computer Vision, vol.2, no.60, pp. 91-110, 2004.
[7] Hironobu Fujiyoshi, “Gradient-Based Feature Extraction -SIFT and HOG-,” Computer Vision for Visual Surveillance and Mobile Robotics (CVIM 160), pp. 211-224, 2007.
[8] GiRyong Choi, Hye-Wuk Jung and Jee-Hyong Lee, “Contents-based Image Retrieval System Design of Shopping Mall using SIFT Matching,"
Proceedings of the Korean Institute of Intelligent Systems, vol. 22, no. 1, pp. 161-163, 2012.
[9] Y Ke, R Sukthankar, “PCA-SIFT: A more distinc- tive representation for local image descriptors,”
IEEE CVPR vol.2, pp. II-506 - II-513, 2004.
[10] L. Juan, O. Gwun, “A comparison of SIFT, PCA-SIFT and SURF,” International Journal of Image Processing, pp. 143–152, 2009.
저 자 소 개
최기룡(GiRyong Choi)
2013년 : 성균관대학교 컴퓨터공학과 학사 2013년～현재 : 한국과학기술원 전산학과
석사과정
관심분야 : 컴퓨터 비전, 데이터 마이닝, 지능시스템, 기계학습 E-mail : [email protected]
정혜욱(Hye-Wuk Jung)
1999년 : 한성대학교 정보공학과 학사 2005년 : 성균관대학교 정보보호학과 석사 2013년 : 성균관대학교 컴퓨터공학과 박사 2013년～현재 : 성균관대학교 정보 및 지능시스템 연구실 연구원
관심분야 : 컴퓨터 비전, 패턴인식, 생체인식, 지능시스템, 사용자 모델링.
E-mail : [email protected]
이지형(Jee-Hyong Lee)
1993년 : 한국과학기술원 전산학과 학사 1995년 : 한국과학기술원 전산학과 석사 1999년 : 한국과학기술원 전산학과 박사 2002년～현재 : 성균관대학교 정보통신 공학부 부교수
관심분야 : 지능시스템, 기계학습, 사용자 모델링 E-mail : [email protected]
