초록 ▼

Ⅰ. 해당 연도 추진 현황
Ⅰ-2 해당 연도 추진 실적
계획
(원천-1) 고차원과 대용량 데이터
추진실적
본 연구에서는 고차원 대규모 데이터를 효율적으로 저장하고, 빠른 속도의 검색을 수행하기 위한 이진 코드화 기술을 개발한다. 특히 본 기술은 기하급수적으로 늘고 있는 이미지 혹은 영상 콘텐츠의 내용 기반 검색 시스템에서 핵심적인 역할을 한다.
기존에는 공간 데이터를 저장하고 검색하기 위해 kd-tree, R-tree, k-means tree 와 같은 계층자료구조 (hierarchical data s

Ⅰ. 해당 연도 추진 현황
Ⅰ-2 해당 연도 추진 실적
계획
(원천-1) 고차원과 대용량 데이터
추진실적
본 연구에서는 고차원 대규모 데이터를 효율적으로 저장하고, 빠른 속도의 검색을 수행하기 위한 이진 코드화 기술을 개발한다. 특히 본 기술은 기하급수적으로 늘고 있는 이미지 혹은 영상 콘텐츠의 내용 기반 검색 시스템에서 핵심적인 역할을 한다.
기존에는 공간 데이터를 저장하고 검색하기 위해 kd-tree, R-tree, k-means tree 와 같은 계층자료구조 (hierarchical data structure)를 사용하였다. 하지만 이들 방법은 데이터의 차원이 올라감에 따라 선형 탐색보다 느린 검색 속도를 제공하며, 또한 데이터의 압축을 고려하지 않기 때문에 대규모 데이터에 적합하지가 않다.
1차년도의 개발 목표는 고차원 데이터를 유사도를 보존하는 간결한 이진 코드로 압축하고, 이때 k-근접 질의 검색을 수행하여 원본 데이터에서 검색했을 때의 정확도와 비교해 최소 10% 이상의 정확도를 가지는 이진 코드화 압축 기술을 개발하는 것이다. 본 연구진은 100만장의 이미지에서 추출한 고차원의 이미지 기술자 데이터를 초구 (hyper-sphere)를 기반으로 하는 해싱 방법을 사용하여 압축하였다.
개발한 이진코드화 알고리즘의 정확도를 검증하기 위하여, 이미지 검색 분야에서 널리 사용되는 GIST 이미지 기술자를 이용하였다. 구체적으로는 100만개의 384차원 GIST 이미지 기술자를 256 비트로 압축한 후 200개의 근접 데이터 검색 결과 정확도를 mAP (mean Average Precision) 으로 측정하였다. 위의 결과 그림에서 확인 할 수 있는 것처럼, 초구 해싱 이진화 코드 압축을 수행한 후 새롭게 제안한 거리 측정 방식인 초구 해밍 거리 (Spherical Hamming Distance, SHD)를 사용하여 본 연구는 1차 년도의 개발 목표치인 정확도 10%를 넘어 11.6%의 정확도 결과를 달성하였다. 본 결과는 공인인증을 받은 결과이며 별첨1. 전자부품연구원 공인인증 시험성적서에 첨부되었다.

계획
(원천-2) 비-유클리드 거리 측정법
추진실적
본 연구에서는 유클리드 거리 (Euclidean distance) 가 아닌 비-유클리드 거리를 기준으로 한 근접 질의에 대해 다룬다. 응용 분야에 따라서 유클리드 거리보다 더 효과적인거리에 대한 정의가 있을 수 있고, 때로는 유클리드 거리를 적용할 수 없을 수도 있기 때문에 실용적인 근접 질의 연구에 있어서 매우 중요하다 할 수 있다.
1차년도에서는 특히 커널 함수로 유사도가 정의된 공간에서의 근접 질의에 대해 연구한다. 구체적으로 커널 함수는 두 데이터 벡터 사이의 유사도를 정의한다. 커널 함수의 한 예로 히스토그램 인터섹션 (HI: histogram intersection) 이 있는데, 이는 두 벡터 사이의 유사도를 각 차원의 값들 사이에 작은 것들의 합으로 정의 한다. 이는 두 벡터를 히스토그램으로 고려하였을 때, 둘이 얼마나 겹치는지를 계산 한다고 할 수 있다.
본 연구진은 (원천-1)의 이진 코드화 기술을 임의의 커널 함수를 지원하는 방법으로 확장하였다. 구체적으로는 커널 트릭 (kernel trick)을 이용하여, 유클리드 거리로 정의된 이진코드화 방법을 커널 함수만을 이용한 형태로 재표현 하는 것이다. 그 뿐만 아니라 계산의 고속화를 위하여 커널 행렬 등을 활용하여 중복적인 계산을 최소화 하는 최적화도 진행하였다.
1차년도의 개발 목표는 정량적 목표 평가 환경과 평가 방법을 만족하는 비-유클리드 거리 측정법 3가지를 개발하는 것이다. 본 연구진은 100만 장의 이미지 데이터에서 다양한 비-유클리드 거리 측정법을 이용한 k-근접 질의 검색을 수행하였고, 그 결과 아래의 3가지 비 유클리드 거리 측정법이 이미지 검색 분야에서 유클리드 거리 측정법을 사용하는 경우보다 2배 이상의 검색 정확도를 보이는 것을 확인하였다. 3가지 거리 측정법은 1) Linear, 2) RBF (Radial Basis Function), 3) HI (Histogram Intersection) 이다:
위의 3가지 거리 측정법을 이용한 k-근접 질의 검색은 GIST를 이용한 960차원 벡터로 표현된 이미지 데이터를 다양한 길이의 이진 코드로 압축했을 때, 3가지 모두 유클리드 거리 측정법을 이용한 LSH (Locality Sensitive Hashing) 방법보다 2배 이상의 mAP 점수를 보였다. 구체적으로는 이미지 데이터를 32 bit의 이진 코드로 압축했을 때, LSH 방법에 비하여 Linear 커널은 6.4배, RPF 커널은 4.5배, HI 커널은 3.1배 높은 mAP 점수를 보였다. 이는 제시한 3가지 측정법이 전부 유의미한 척도임을 보이는 지표이다. 별첨한 공인인증 시험 당시에는 각각의 커널에서 주로 쓰이는 차원의 이미지 데이터를 사용하였으나, 동일한 차원 상에서의 평가를 위해 960차원으로 고정하여 추가 실험하였다.

목차 Contents

• 표지 ... 1
• 제출문 ... 2
• 연차보고서 ... 3
• Ⅰ. 해당 연도 추진 현황 ... 4
• Ⅰ-1 기술개발 추진 일정 ... 4
• Ⅰ-2 해당 연도 추진 실적 ... 5
• Ⅱ. 기술개발결과 ... 14
• Ⅲ. 결론 및 차년도 계획 ... 24
• Ⅳ. 사업비 사용현황 ... 26
• Ⅵ. 자체보안관리진단표 ... 27
• Ⅶ. 유형적 발생품(연구시설, 연구장비 등) 구입 및 관리 현황 ... 28
• 끝페이지 ... 28