12장 멀티미디어 정보 검색 : 색인과 탐색 목차 12.1 소개 12.2 배경 – 공간 접근 방법 12.3 일반적인 멀티미디어 색인 방법 12.4 1차원 시계열 12.5 2차원 컬러 이미지 12.6 자동 특징 추출 12.7 연구 동향 및 쟁점 12.8 참고 문헌 고찰 최신정보검색론 Chapter 12

12.1 소개 질의 된 객체와 정확히 또는 대략적으로 일치하는 객체들을 찾기 위하여, 멀티미디어 객체들이 저장된 데이터베이스로부터 빠른 탐색 방법을 설계하는 문제를 주로 다룸 두 객체 사이의 거리를 측정은 거리 함수 D()로 정의 두 객체 O1 과 O2가 주어졌을 때, 두 객체 사이의 거리(비유사성)는 다음과 같이 표시됨 D( O1, O2) 최신정보검색론 Chapter 12

12.1 소개 (계속) 유사도 질의는 다음 두 개의 범주로 분류 질의 형태의 이상적인 조건 - 전체 정합 : N개의 객체 O1, O2,…,ON 와 질의 객체 Q 일 때, Q로 부터 거리가 ε 범위내의 데이터 객체들을 찾기를 원함 - 부분 패턴 정합 : N개의 객체 O1, O2,…,ON 와 질의 객체 Q, 허용 오차 ε 이 주어졌을 때, 질의에 일치되는 객체의 일부를 찾고자 함 질의 형태의 이상적인 조건 - 빨라야 함 - 정확해야 함 - 필요한 공간이 작아야 함 - 동적이어야 함 최신정보검색론 Chapter 12

12.2 배경 – 공간 접근 방법 객체들을 f차원 공간의 한 점으로 대응시키는 것 - 다중 속성 접근 방법 (multiattribute access method) - 공간 접근 방법(spatial access method)또는 SAM R*트리와 R트리 계열 선형 사분 트리(linear quadtree) 그리드파일(grid-file) 최신정보검색론 Chapter 12

12.2 배경 – 공간 접근 방법(계속) 선형 사분 트리의 계산 복잡도는 질의영역의 초월 평면에 비례함 (초월 평면은 차원에 따라 지수적 증가) R-트리 (대표적인 공간 접근 방법) - 최소 범위 사각형(MBR)으로 공간 객체를 표현 - 데이터 사각형(data rectangle)은 클러스터를 형성 - 부모 노드를 형성 (재귀적으로 조부모 노드를 형성) - 결국 트리 구조를 형성 최신정보검색론 Chapter 12

12.2 배경 – 공간 접근 방법(계속) 최신정보검색론 Chapter 12 점선은 조부모 노드, 굵은 점선은 증조부모 노드(이 예에서는 root 노드)이다. 최신정보검색론 Chapter 12

12.2 배경 – 공간 접근 방법(계속) 최신정보검색론 Chapter 12

12.3 일반적인 멀티미디어 색인 방법 ‘완전 정합’질의 문제의 정의 순차 탐색이 느린 두 가지 이유 - N개의 객체 집합 O1, O2,…,ON - 두 객체(Oi, Oj) 간의 거리/비유사도는 함수 D(Oi, Oj) - 사용자는 질의 객체 Q와 허용 오차 ε을 지정 순차 탐색이 느린 두 가지 이유 - 거리 계산의 비용이 큼 - 데이터베이스 크기 N이 너무 큼 GEMINI방법으로 두 가지 단점을 해결 - 신속불결 검사 : 만족하지 않는 객체들을 빠르게 제거 - 공간 접근 방법의 이용 : 순차 탐색보다 빠른 검색을 수행 최신정보검색론 Chapter 12

12.3 일반적인 멀티미디어 색인 방법(계속) 두 시계열 S와 Q사이의 거리 함수 대응 함수 F() F()가 객체를 f차원의 점으로 대응시키는 함수라고 하면, F(O)는 객체 O에 해당하는 f차원의 점이다. 최신정보검색론 Chapter 12

12.3 일반적인 멀티미디어 색인 방법(계속) 최신정보검색론 Chapter 12 [그림 12.3]R*-트리의 기본 개념 : 시계열 데이터베이스 S1,…,Sn : 각 시계열은 특징 공간의 한 점에 대응된다. 허용오차 ε 인 구가 된다. 최신정보검색론 Chapter 12

12.3 일반적인 멀티미디어 색인 방법(계속) 완전 정합 질의에 대한 탐색 알고리즘 하한계(lower bounding) 질의 객체 Q를 특징 공간 내의 한 점 F(Q)에 대응 공간 접근 방법을 사용하여, F(Q)로 부터 원하는 허용 오차 ε 내의 모든 점들을 검색 허용 오차 내의 객체들을 검색/ Q로부터 실제 거리를 계산/ 착오경보를 제거 완전 정합 질의에 대한 착오 제거가 없다는 보장을 위해, 특징 추출 함수 F()는 아래의 공식을 만족해야 한다. Dfeature(F(O1), F(O2)) ≤ D(O1, O2) 최신정보검색론 Chapter 12

12.3 일반적인 멀티미디어 색인 방법(계속) 빠른 유사도 탐색을 위한 GEMINI방법 - 착오제거가 없다는 것을 보장 - 질의점 F(Q)에 최근접 점인 F(P)를 찾음 - 질의 객체 Q와 반지름 ε=D(Q,P)를 가지는 범위 질의를 생성 두 객체간의 거리 함수 D()를 결정 신속 불결 검사를 제공하기 위해 하나 이상의 숫자 특징 추출 함수(numerical feature extraction function)를 찾음 정확성을 보장하기 위해, 특징 공간의 거리가 실제 거리 D()의 하한계임을 증명 f차원 특징 벡터를 검색하고 지정하기 위해, SAM을 사용 최신정보검색론 Chapter 12

12.3 일반적인 멀티미디어 색인 방법(계속) 특징 추출 질문 성공적인 대답을 위한 두 가지 목적 - 단계 3(거리 하한계)을 용이하게 함 - 객체들에 대한 대부분의 특성을 반영 함 신속부결 여과의 원리와 하한계 정리의 결합(해결책) - 차원 재앙 (예: 시계열) - 특징의 잡음 (예: 컬러 이미지) 만약 각 데이터 객체를 묘사하기 위해,오직 하나의 숫자 특징만을 사용한다면, 그 특징은 무엇이 될 것인가? 최신정보검색론 Chapter 12

12.4 1차원 시계열 GEMINI에 따라, 두 시계열간의 거리 척도를 결정 전형적인 거리 함수 : 유클리드 거리 원하는 시계열과 유사한 것을 찾기 위해 시계열 컬렉션을 탐색 12.4.1 거리 함수 GEMINI에 따라, 두 시계열간의 거리 척도를 결정 전형적인 거리 함수 : 유클리드 거리 - 금융과 예보 응용에 일상적으로 사용 최신정보검색론 Chapter 12

12.4.2 특징 추출과 하한계 하한계를 만족하는 특징 집합 조건 Parseval 정리 - 거리를 유지하면서 하한계를 만족 - 대응하는 시계열에 대한 많은 정보를 지님 Parseval 정리 - DFT가 두 신호 사이의 거리, 신호의 에너지 보존 최신정보검색론 Chapter 12

12.4.2 특징 추출과 하한계 (계속) 경사 에너지 스펙트럼(skewed energy spectrum) - b=2일 때 : 임의 주행 (random walk) 또는 갈색 잡음 상태 - b>2일 때 : 흑색 잡음 (black noise) 상태 - b=1일 때 : 분홍색 잡음 (pink noise)상태 최신정보검색론 Chapter 12

12.4.2 특징 추출과 하한계 (계속) 최신정보검색론 Chapter 12 30,000개의 측정지 중 에서 처음 3,000개의 측정치) (b) 1/F 선을 따라서 나타나는 푸리에 변환의 로그-로그 진폭 최신정보검색론 Chapter 12

12.4.3 실험 최신정보검색론 Chapter 12 [그림 12. 6] 완전 정합 질의에 대해서 질의당 탐색 시간 대 시계열의 개수 N (GEMINI(검은 선)과 순차탐색(회색 선) ) [그림 12.5] 범위 질의를 위한 실행 시간의 변환 (DB 크기 N은 400개의 시계열이다) 최신정보검색론 Chapter 12

12.4.3 실험 (계속) GEMINI를 시계열에 적용해서 얻은 결론 - 경사 스펙트럼을 가지는 신호에 대해서 최소 응답 시간은 소수의 푸리에 계수(f= 1,2,3)로 얻을 수 있음 - 1차원 시계열의 성공으로, 어떤 신호가 경사 스펙트럼을 가진다면, GEMINI는 2차원이상의 신호에 대해서도 가능성이 높음 최신정보검색론 Chapter 12

12.5 2차원 컬러 이미지 두 가지 주된 자료형인 장면 (이미지 ≡ scene)과 항목을 가지는 정지 영상 데이터베이스에 대한 방법 - 장면 : 하나의 (컬러) 이미지 - 항목 : 장면의 일부분(예: 사람, 대강의 질감, 사과) - 각 장면은 0 이상의 항목을 가짐 - 항목을 인식하고 추출하는 것은 이 책의 범위를 벗어남 최신정보검색론 Chapter 12

12.5.1 이미지에 대한 특징과 거리 함수 히스토그램이 구하면 두 히스토그램(k*1 벡터) 와 사이의 거리를 측정하는 방법 [그림 12.7] 상상으로 만든 일몰 사진에 대한 컬러 히스토그램의 예: 빨간색, 분홍색, 주황색 청색의 픽셀은 많지만, 노란색, 흰색, 녹색의 픽셀은 조금밖에 없다. 최신정보검색론 Chapter 12

12.5.2 하한계 GEMINI 방법을 컬러 색인에 적용시 장애 요인 - 거리 함수가 이차함수라는 것 - 차원 재앙 : 예) 컬러 특징의 수 K가 64나 256처럼 매우 큼 - 거리 함수가 이차함수라는 것 [그림 12.8] 두 컬러 히스토그램 사이의 잡음에 대한 설명 최신정보검색론 Chapter 12

12.5.2 하한계 (계속) 이미지나 항목의 평균 컬러 벡터 3차원 평균 컬러 벡터 사이의 유클리드 거리 정의 아래와 같이 정의 3차원 평균 컬러 벡터 사이의 유클리드 거리 정의 최신정보검색론 Chapter 12

12.5.3 실험 순차 계산 방법(naïve)과 GEMINI의 공간 접근 방법의 성능비교 최신정보검색론 Chapter 12 응답 시간과 선택도 최신정보검색론 Chapter 12

12.5.3 실험 (계속) 결론 - GEMIMI 방법은 평균 RGB거리를 사용하여 신속함, 정당성을 보장하는 타당한 정리를 얻음 - 잡음 문제를 해결, GEMINI는 추가 비용 없이 차원재앙 문제를 해결 - 즉 dhist()를 계산하기 위해서 요구되는 k는 64 또는 256인 반면에 GEMINI에서는 f=3개의 특징만 요구 최신정보검색론 Chapter 12

12.6 자동 특징 추출 그림 12.10에서 k=3개의 특징/차원을 생성한 후, 7개의 부류에 속하는 35개의 문헌에 대한 FastMap의 결과를 보여준다. 그 부류들 :농구 보고서(Bbr), 컴퓨터 과학 기술 보고서의 초록(Abs), 요리법(Rec)등 거리함수는 코사인 유사도의 감소 함수 최신정보검색론 Chapter 12

12.6 자동 특징 추출 (계속) 최신정보검색론 Chapter 12 [그림 12.10] 3차원 공간에서 FastMap을 적용한 후의 문헌 컬렉션 : (a) 전체 컬렉션 (b) 점선 부분의 상자를 확대한 것 최신정보검색론 Chapter 12

12.7 연구 동향 및 쟁점 두 가지 개념을 결합하는 GEMINI 방법에 초점 - 조건에 만족되지 않는 객체들을 빨리 제거하는 신속불결 검사를 고안해야 함 - R*-트리와 같은 최신 공간 접근 방법[400]을 사용하여, f차원의 점들을 구성하여 빠른 탐색 방법을 찾는 것 멀티미디어와 복합 미디어 데이터 집합에 대한 데이터 마이닝이 가장 주목할만한 연구 방향 최신정보검색론 Chapter 12

12.8 참고 문헌 고찰 공간 접근 방법 - 구조와 알고리즘 [290] : 최신 공간 접근 방법의 조사가 이뤄짐 Guttman의 초기 논문[330], Hilbert R-트리[427], GiST 트리 [119]의 여과 알고리즘과 [521] 및 [458]의 방법 TV-트리[519], SR-트리[431], X-트리[83] - 거리 측정 트리 하나의 거리함수만 요구하는 클러스터 계층을 구성 Burkhard-Keller 방법[131], 고정 질의 트리[47], GNAT 트리[116], MVP 트리[112], M-트리[172] >특정 추출을 요구하지 않는 대신 시각화와 데이터마이닝을 제공하지 못함 최신정보검색론 Chapter 12

12.8 참고 문헌 고찰 (계속) 멀티미디어 색인과 DSP 및 특정 추출 - GEMINI – 특징 추출 [400] : 빠른 색인을 위한 특징 추출을 제안한 최초의 논문 [249] : 하한계 정리의 증명 MDS[462] : 자동 특징 추출 알고리즘 FastMap : O(N)을 가지는 방법 - 기계열 [706], [840] BoxJenkins 방법론[109] [149, 808] : 최근의 비선형 예측 방법 최신정보검색론 Chapter 12

12.8 참고 문헌 고찰 (계속) - 디지털 신호 처리(Digital Signal Processing : DSP) 전통적인 푸리에 변환[622], JPEG 이미지 압축 표준[802] 웨이블릿 변환(DWT)[689], [651] - 이미지 특징과 유사도 함수 [53, 224, 285], [125], [244] - 멀티미디어 색인의 다른 응용 [305, 7, 246], [800], [244], [381, 454, 635], [733, 80, 714] - 데이터 마이닝 전통적인 기계 학습[565], 통계학[408] 최신정보검색론 Chapter 12