멀티미디어 정보 검색에서 멀티미디어 데이터는 고차원 공간상의 벡터로 표현된다. 두 벡터간의 유사도를 계산하기 위한 척도로는 유클리드 거리가 널리 사용된다. 그러나 고차원 공간에서 유클리드 거리를 계산하는 것은 많은 연산을 필요로 한다. 따라서, 효율적인 질의 ...

멀티미디어 정보 검색에서 멀티미디어 데이터는 고차원 공간상의 벡터로 표현된다. 두 벡터간의 유사도를 계산하기 위한 척도로는 유클리드 거리가 널리 사용된다. 그러나 고차원 공간에서 유클리드 거리를 계산하는 것은 많은 연산을 필요로 한다. 따라서, 효율적인 질의 처리를 위해서는 벡터들 간의 유사도 계산을 빠르게 하는 것이 매우 중요하다. 효율적인 유사도 계산을 통해 질의 처리 성능을 높이기 위하여, 본 연구에서는 고차원 벡터의 놈과 각도 성분을 기반으로 하는 유클리드 거리의 근사 함수를 제안한다. 두 벡터간의 각도 성분을 근사하기 위하여, 기준 벡터라는 개념을 도입한다. 제안하는 기법은 근사된 각도 성분을 이용하여 유클리드 거리를 근사함으로써, 기존의 Cauchy-Schwartz 부등식을 이용하는 근사 기법에 비교하여 거리 근사 오차를 크게 줄일 수 있다. 또한, 제안하는 기법에 의한 거리 근사 값은 실제 유클리드 거리보다 항상 작거나 같음을 이론적으로 증명한다. 이는 근사된 거리를 이용한 멀티미디어 정보 검색에서 착오 기각을 발생하지 않음을 의미한다.
고차원 특징 벡터를 효율적으로 검색하기 위하여 다양한 색인 기법이 제안되어 왔다. 그러나 특징 벡터의 차원이 증가하면서 색인 기법의 효율성이 급격히 떨어지는 차원의 저주 문제가 발생한다. 차원의 저주 문제를 해결하기 위하여 색인하기 이전에 원 특징 벡터를 저차원 공간상의 벡터로 사상하는 차원 축소 기법이 제안된 바 있다. 본 연구에서는 벡터의 놈과 각도 성분을 이용하여 유클리드 거리를 근사하는 함수를 기반으로 하는 새로운 차원 축소 기법을 제안한다. 먼저, 유클리드 거리 근사를 위하여 추정된 각도의 오차의 발생 원인을 분석하고, 이 오차를 줄이기 위한 기본 방향을 제시한다. 제안하는 새로운 차원 축소 기법은 고차원 특징 벡터를 다수의 특징 서브 벡터들의 집합으로 분리하고, 각 특징 서브 벡터로부터 놈과 각도 성분을 근사하여 차원을 축소하는 기법이다.
각도 성분을 정확하게 근사하기 위해서는 올바른 기준 벡터의 설정이 필수적이다. 따라서 본 연구에서는 최적 기준 벡터의 조건을 제시하고, Levenberg-Marquardt 알고리즘을 이용하여 기준 벡터를 선정하는 방법을 제안한다. 또한, 축소된 저차원 공간상의 벡터들을 위한 새로운 거리 함수를 정의하고, 이 거리 함수가 유클리드 거리 함수의 하한 함수가 됨을 이론적으로 증명한다. 이는 제안된 기법이 착오 기각의 발생을 허용하지 않으면서 효과적으로 차원을 줄일 수 있음을 의미하는 것이다.
다차원 데이터 벡터를 색인하기 위하여 R*-tree 색인 구조가 널리 사용되어왔다. R*-tree를 사용한 검색에서 정답을 보장하면서 효율적으로 검색하기 위해서는 제약조건이 존재한다. R*-tree는 최소 경계 사각형(Minimum bounding Rectangle, MBR)을 기반으로 하기 때문에, 효율적인 검색을 위해서는 질의 영역이 MBR의 형태로 표현되어야 한다. 또한, 질의 벡터와 MBR까지의 거리는 질의 벡터와 해당 MBR 내의 어떤 벡터와의 거리보다 항상 작거나 같아야 한다. 본 연구에서는 이러한 제약조건을 만족하기 위하여 새로운 질의 영역을 정의한다. 정의한 질의 영역은 실제 질의 영역을 모두 포함한다. 또한, 질의 벡터와 MBR까지의 거리가 MBR 내부의 모든 벡터와의 거리 보다 항상 작거나 같다는 관계를 유지하기 위하여, MBR 확장 기법을 제안한다.

1. 연구 결과
본 연구에서는 효율적인 멀티미디어 정보 검색을 위한 방법에 관하여 다루었다. 멀티미디어 정보 검색에서는 멀티미디어 데이터를 효과적으로 표현하기 위하여 멀티미디어 데이터를 고차원 벡터로 표현한다. 또한 거리 함수를 이용하여 유사 검색을 수행하 ...

1. 연구 결과
본 연구에서는 효율적인 멀티미디어 정보 검색을 위한 방법에 관하여 다루었다. 멀티미디어 정보 검색에서는 멀티미디어 데이터를 효과적으로 표현하기 위하여 멀티미디어 데이터를 고차원 벡터로 표현한다. 또한 거리 함수를 이용하여 유사 검색을 수행하게 된다. 그러나 이 과정에서 유사 검색을 위한 거리 계산의 연산 복잡도가 높아 검색 효율이 떨어지는 문제가 존재한다. 또한 고차원 벡터를 색인하기 위하여 기존의 R*-tree와 같은 다차원 색인 구조를 사용할 경우 차원이 증가함에 따라 검색 성능이 급격히 떨어지는 차원의 저주 문제가 발생한다. 본 연구에서는 앞서 제시한 문제들을 해결하기 위한 방안에 관하여 연구를 진행하였고, 본 연구를 통하여 다음과 같은 연구 성과를 얻었다.

1) 유클리드 거리 함수의 하한 함수 제안
- 본 연구에서는 각도 근사 기법을 이용한 유클리드 거리 함수의 하한 함수를 제안하였다. 이를 위하여 기준 벡터라는 개념을 도입하였다. 기준 벡터는 데이터 벡터와 질의 벡터 사이의 각도 성분을 근사하기 위해 사전에 각 데이터 벡터의 각도 성분을 계산해 두기 위해 사용하는 벡터로써, 이 기준 벡터의 선정 결과에 따라 전체 성능이 영향을 받는다. 따라서 본 연구에서는 기준 벡터를 선택하기 위한 두 가지 조건을 제시하였다. 첫째, 근사하고자 하는 벡터는 최대한 같은 평면상에 존재해야 한다. 둘째, 기준 벡터는 최대한 축에 가깝게 존재해야 한다. 본 연구에서는 이러한 제약조건을 만족하는 기준 벡터 생성 방법으로 Levenberg-Marquardt 알고리즘을 이용한 기준 벡터 선정 방법을 제안하였다. 제안한 방법으로 선정된 기준 벡터를 활용하여 각도 성분을 근사하고 근사된 각도 성분을 이용한 거리 함수 또한 제안하였다. 제안한 거리 함수는 원 유클리드 거리의 하한이 됨을 이론적으로 증명하였다.

2) 차원의 저주 문제를 해결하기 위한 새로운 차원 축소 기법 제안
앞서 제안한 각도 근사 기법의 경우 차원이 증가할 수록 각도 근사 오차가 커짐을 확인하였다. 이러한 근사 오차를 줄이기 위하여 본 연구에서는 고차원 벡터를 하위 벡터의 그룹으로 정의하고 각 하위 벡터에 대하여 각도 근사 기법을 적용하는 차원 그룹화 기법을 제안하였다. 이는 각 하위 벡터의 놈과 각도 성분만을 저장해 놓는 방식으로 고차원 데이터를 저차원 데이터로 변환하는 새로운 방식의 차원 축소 기법이다. 이를 통해 고차원 데이터를 색인하고 검색할 경우 발생하는 차원의 저주 문제를 해결할 수 있음을 확인하였다. 이 과정에서 저차원 공간에서 벡터간 거리를 효율적으로 계산할 수 있느 새로운 거리 함수를 제안하였다.
고차원 특징 벡터에 대한 유사 검색에서 정답을 보장하는 검색을 위해서는 축소된 저차원 벡터 공간에서의 거리 값이 고차원 특징 벡터 공간에서의 거리 값보다 항상 작거나 같아야 한다는 Lower-bound property가 항상 만족하여야 한다. 본 연구에서 제안한 거리 함수 역시 Lower-bound property가 성립함을 이론적으로 증명하였다. 따라서 제안한 방법에 의한 정보 검색은 착오 기각이 발생하지 않음을 보장한다.

3) 제안한 차원 축소 기법에 기반한 효과적인 색인 및 검색 기법 제안
저차원 공간으로 변환된 특징 벡터를 효과적으로 검색하기 위해서는 색인 구조를 이용하여 색인하고 검색할 수 있어야 한다. 또한 정답을 보장하기 위해서는 축소된 저차원 공간에서
이를 위해 본 연구에서는 MBR기반의 색인 구조인 R*-tree를 도입하였고, 트리 서치 과정에서 착오 기각이 발생하지 않음을 보장하는 검색 방법을 제안하였다. 즉, 검색 단계에서 MBR을 확장함으로써, 원 유클리드 공간에서 거리를 반영하여 MBR을 필터링 할 수 있도록 하였다. 제안하는 MBR 확장 기법은 항상 MBR을 확장하는 것이 아니라 특정 조건에 부합할 경우에만 수행하고 또한 확장되는 영역을 최소화함으로써 부가적으로 검사해야 하는 데이터 양을 최소화 하였다. 이를 통해 착오 기각 없이 효과적으로 검색 할 수 있음을 증명하였다.

2. 활용 방안
본 연구에서 제안한 고차원 벡터에 대한 효과적인 차원 축소 기법과 이에 기반한 색인 및 검색 기법은 유클리드 거리를 기반으로 하는 멀티미디어 정보 검색에 있어서, 특징 벡터의 종류에 무관하게 적용할 수 있는 기법이다. 따라서 상품 검색 등 최근 대용량 멀티미디어 데이터에 대한 검색이 필요한 분야에 손 쉽게 적용하여 효율을 높일 수 있을 것이다. 또한 멀티미디어 데이터 기술 표준으로 자리잡은 MPEG7 기술자에 대한 효과적인 검색 기법으로 활용 가능할 것이다.