Microsoft Word doc

Transcription

1

2 工 學 博 士 學 位 請 求 論 文 同 心 圓 區 劃 基 盤 敍 述 子 를 이용한 大 容 量 停 止 映 像 및 動 映 像 資 料 의 高 速 識 別 The Fast Identification of Large Image and Video Database using Concentric Circle Partitioning based Descriptor 2008 年 2 月 仁 荷 大 學 校 大 學 院 電 子 工 學 科 ( 情 報 工 學 專 攻 ) 曺 益 煥

3 工 學 博 士 學 位 請 求 論 文 同 心 圓 區 劃 基 盤 敍 述 子 를 이용한 大 容 量 停 止 映 像 및 動 映 像 資 料 의 高 速 識 別 The Fast Identification of Large Image and Video Database using Concentric Circle Partitioning based Descriptor 2008 年 2 月 指 導 敎 授 鄭 東 錫 이 論 文 을 工 學 博 士 學 位 論 文 으로 提 出 함 仁 荷 大 學 校 大 學 院 電 子 工 學 科 ( 情 報 工 學 專 攻 ) 曺 益 煥

4 이 論 文 을 曺 益 煥 의 博 士 學 位 論 文 으로 認 定 함 2008 年 2 月 主 審 최 상 방 副 審 정 동 석 委 員 윤 광 섭 委 員 오 원 근 委 員 최 경 호 3

5 목 차 목 차...4 그림 목차 표 목차.. 8 요 약...9 ABSTRACT. 11 제 1 장 서론 제 2 장 관련 연구 멀티미디어 검색과 식별 멀티미디어 검색 MPEG-7 영상 서술자 색상 서술자 텍스쳐 서술자 형태학적 서술자 움직임 서술자 멀티미디어 핑거프린팅 멀티미디어 식별 응용분야 국제 표준 기술 제정 제 3 장 정지 영상 식별을 위한 서술자 원형 구획 기반 서술자의 모델링 동심원 구획 기반 서술자 동심원 구획 정지 영상 서술자 추출 평균 픽셀값 분포

6 평균 차분값 분포 대칭적 차분값 분포 원형 차분값 분포 정지 영상 서술자 정합 제 4 장 동영상 식별을 위한 서술자 대표 프레임 선택 시공간 정보를 이용한 동영상 서술자 추출 동영상 서술자 정합 시간적 후보 구간 선정 동영상 서술자 유사도 판별 제 5 장 정지 영상 서술자 성능 평가 성능 평가 모델 성능 평가 및 실험 환경 독립성 평가 강인성 평가 서술자 크기 평가 서술자 추출 속도 평가 서술자 정합 속도 평가 제 6 장 동영상 서술자 성능 평가 성능 평가 모델 성능 평가 및 실험 환경 강인성 평가 서술자 크기 평가 서술자 정합 속도 제 7 장 결론 제 8 장 참고문헌

7 그림 목차 그림 2.1 예시 기반 검색의 예 그림 2.2 검색과 식별의 응용 비교 그림 2.3 MPEG-7 표준의 범위 그림 2.4 MPEG-7 요소들 사이의 관계 그림 2.5 MPEG-7 표준 기술을 이용한 응용의 예 그림 2.6 색상의 서로 다른 공간적 긴밀성의 예 그림 2.7 구조화된 색상과 구조화되지 않은 색상 분포의 예 그림 2.8 균등 텍스쳐 서술자의 특징 추출을 위한 주파수 영역 도시 그림 2.9 규칙성의 예 그림 2.10 영상에서의 다섯가지 경계선 유형 그림 2.11 세부 이미지와 영상 블록의 정의 그림 2.12 다양한 형태의 예 그림 2.13 ART 기저 함수의 실수부 그림 차원 객체와 대응되는 외곽선 형태 그림 2.15 다양한 카메라 움직임의 예 그림 2.16 불법 콘텐츠 추적 시스템의 예 그림 2.17 해시 함수의 예 그림 2.18 정지 영상 식별자를 위한 제안된 새로운 ground truth 모델 그림 3.1 블록 기반 구획 그림 3.2 블록 구획의 예 그림 3.3 반지름 및 각도 방향에 대한 동심원 구획 그림 3.4 동심원 구획 기반 서술자 추출 순서 그림 3.5 영상의 동심원 구획의 예 그림 3.6 입력 영상의 정규화 그림 3.7 평균 픽셀 분포 그림 3.8 해시 함수를 이용한 평균 픽셀값 분포로부터 이진 수열의 생성의 예 그림 3.9 대칭적 차분값 계산의 예 그림 4.1 동영상 서술자 추출을 위한 전체 블록다이어그램 그림 4.2 주기 t를 갖는 대표 프레임의 추출 그림 4.4 시공간 정보를 이용한 동영상 서술자의 구조 그림 4.5 전체 서술자 비교 방식을 이용한 동영상 서술자의 후보 구간 탐색

8 그림 4.6 일부 구간과 임계치를 이용한 동영상 서술자의 정합 그림 5.1 색상 배치 서술자의 교차 거리 히스토그램(MPEG-7) 그림 5.2 경계선 히스토그램 서술자의 교차 거리 히스토그램(MPEG-7) 그림 5.3 PCA-HASH 알고리즘의 교차 거리 히스토그램 그림 5.4 라돈 변환 기반 핑거프린팅 알고리즘의 교차 거리 히스토그램 그림 5.6 각 알고리즘 별 정밀도-재연성 곡선 그림 5.7 다양한 변형에 대한 모든 알고리즘들의 검출 성공률의 비교 그림 5.8 다양한 각도 단계에 따른 검출 성공률의 비교 그림 5.9 다양한 각도 단계에 따른 평균 검출 성공률 그림 5.10 다양한 반지름 단계에 따른 검출성공률의 비교 그림 5.11 다양한 반지름 단계에 따른 평균 검출 성공률 그림 6.1 질의 동영상과 원본 동영상 사이의 정합 구간의 검출 그림 6.2 실험에 사용된 뮤직비디오 클립의 예 그림 6.3 다양한 변형에 따른 검출 성공률 그림 6.4 다양한 변형에 따른 정합 시간 그림 6.5 후보 구간 길이와 임계치에 대한 평균 상대적 검색 성공률 그림 6.6 후보 구간의 길이와 임계치에 따른 평균 속도 향상률 그림 6.7 후보 구간 길이와 임계치에 따른 상대적 검색 성공률과 속도 향상률의 관 계

9 표 목차 표 2.1 멀티미디어 검색과 식별의 비교 표 2.2 MPEG-7 표준의 세부 구성 표 3.1 기하학적 변형과 비기하학적 변형의 예 표 5.1 정지 영상 서술자의 강인성 테스트를 위한 변형의 종류 표 5.2 제안된 서술자 구현에 사용된 실험 변수 표 5.3 모든 알고리즘별 임계거리값 표 5.4 알고리즘 별 검출 영상 수에 대한 평균 정밀도 및 재연성 표 5.5 다양한 변형에 대한 각 알고리즘의 검출 성공률 표 5.6 다양한 각도 단계에 따른 강인성 표 5.7 다양한 반지름 단계에 따른 검출 성공률 표 5.8 알고리즘 별 서술자의 크기 표 5.9 알고리즘별 서술자 추출 속도 표 5.10 알고리즘 별 정합 속도 표 6.1 동영상 서술자의 강인성 평가를 위한 변형 표 6.3 다양한 변형에 따른 검출 성공률 표 6.4 다양한 변형에 따른 총 정합 시간 (msec) 표 6.5 후보 정합 구간 길이와 임계치에 따른 변형별 검출 성공률 표 7.1 정지 영상 식별을 위한 알고리즘 비교

10 요 약 본 논문에서는 대용량 정지 영상 및 동영상 자료에 대한 고속 식별을 가능토록 하는 새로운 서술자를 제안하고 있다. 멀티미디어 식별은 기존의 검색과는 다르 게 질의와 유사한 영상을 데이터베이스에서 찾는 것이 아니라 질의와 내용적으 로 일치하는 영상을 찾아내는 기능을 말한다. 다양한 연구를 통하여 멀티미디어 검색을 위한 많은 서술자가 제안되었고 이 중 높은 성능을 보이는 것들은 MPEG-7 국제 표준화를 거쳐서 표준 서술자로서 제정이 되었다. 그러나 기존의 멀티미디어 검색에 비하여 더 높은 성능을 요구하는 식별을 위한 서술자에 대 한 연구는 상대적으로 많지 않았으며 최근에 디지털 핑거프린팅 또는 복사본 검출과 같은 연구를 통해서 다양한 기술들이 제안되고 있다. 대용량 멀티미디어 자료에 대한 고속 식별을 위하여 본 논문에서는 동심원 구 획 기반 정지 영상 및 동영상 서술자를 제안한다. 제안된 방법은 정지 영상의 경우 영상의 중심으로부터 정해진 반지름 단계와 각도 단계를 이용하여 영상을 동심원 형태로 구획한다. 그리고 구획된 동심원의 세부 영역으로부터 4가지 특 징 분포를 추출한다. 4가지 특징 분포는 각각 평균 픽셀값 분포, 평균 차분값 분 포, 평균 대칭적 차분값 분포 그리고 평균 원형 차분값 분포이다. 추출된 특징 분포는 제안된 해시 함수를 통해 이진 수열 형태로 변환된다. 추출된 이진 수열 은 병합되어 최종적으로 하나의 서술자를 구성하게 되고 정합 시에는 가장 간 단한 연산인 XOR 연산을 통하여 해밍 거리를 계산하여 유사도를 판별한다. 동 9

11 영상 서술자는 정지 영상 서술자를 확장하여 일정한 주기단위로 대표 프레임을 추출하여 해당 프레임에 정지 영상 서술자를 추출한 후 모든 대표 프레임에 대 하여 병합하여 최종 서술자로 사용한다. 본 논문에서는 동영상 서술자의 빠른 정합을 위하여 간단한 부분 검색 방법을 제안하였으며 기본적으로는 정지 영상 서술자와 마찬가지로 해밍 거리를 이용한다. 제안된 고속 식별을 위한 서술자의 성능을 평가하기 위하여 본 논문에서는 평 가 모델을 제안하였으며 약 6만여장의 대용량 정지 영상 자료와 26가지의 다양 한 변형에 대한 실험 결과 1ppm의 양성 오류율의 조건 하에서 약 98.4%의 높 은 강인성을 보여 주었다. 더불어 하나의 영상에 대하여 서술자는 192비트의 상 대적으로 작은 크기를 소비하였다. 더불어 서술자의 형태가 이진 수열형태이기 때문에 매우 빠른 정합 속도를 보여주며 초당 약 1,500만개의 서술자를 정합시 킬 수 있다. 동영상 서술자의 경우 약 97.4%의 강인성을 보여주었으며 일부 구 간과 임계치를 이용한 검색 기법을 통하여 전체 프레임 검색 방법대비 약 98% 이상의 강인성을 유지하면서 속도는 평균적으로 최대 약 1.5배 향상되었다. 따 라서 본 연구 결과물은 대용량 멀티미디어 자료를 기반으로 하는 고속 식별 서 비스나 불법 복사본 검색 시스템에 유용하리라 판단된다. 10

12 ABSTRACT In this dissertation, we proposed new descriptor which makes fast identification possible for large image and video database. Multimedia identification is the functionality to find out same image to query one in database while multimedia retrieval is to find out the similar image in database. From various researches, a lot of descriptors for multimedia retrieval have been proposed and some of them with high performance were selected as standard technologies through MPEG-7 standard activity. However the research of descriptor for multimedia identification, which requires higher performance, has not been enough relatively and various technologies have been suggested from the research for digital fingerprinting and replica or copy detection recently. For fast identification for large collection of multimedia database, concentric circle partitioning based image and video descriptor is proposed in this dissertation. In case of image, the proposed method partitions image into concentric circle shape in according to fixed radius and angle levels from the center of image. And from the partitioned sub-regions of concentric circles, 4 feature distributions are extracted. The extracted 4 feature distributions are average pixel intensity distribution, average difference distribution, average symmetric difference distribution and average circular difference distribution. The extracted feature 11

13 distributions are converted into binary string using the proposed Hash function. The converted binary strings are merged finally into one descriptor and the similarity is obtained by calculating Hamming distance to use the simplest XOR operation at the matching stage. The proposed video descriptor extends image descriptor and extracts the representative frame in fixed period and image descriptor is extracted for each representative frame. And then all image descriptors from each representative frames are merged and it is used as final video descriptor. In this dissertation, for the fast matching process the simple partial searching method is proposed and basically Hamming distance is used like image descriptor. To evaluate the performance of the proposed descriptor for fast identification, the evaluation model is proposed and experiment results with about 60,000 images and 26 modifications shows that the proposed method has about 98.4% robustness under 1ppm false positive rate and the descriptor spends 192 bits for one image. In addition, it shows very fast matching speed of 15,000,000 pairs per second. Video descriptor shows about 97.4% robustness and its matching speed can be improved by maximum 1.5 times with keeping robustness more over 98% against full frame searching method thanks to the proposed fast searching method using partial section and threshold value. Therefore it is thought that this research results will be very useful for fast identification application based on large size multimedia data or illegal copy searching system. 12

14 제 1 장 서론 현대사회의 디지털 미디어에서 가장 대중의 관심을 받는 것이 하나는 바로 영상 분야이다. 이미 우리는 길지 않은 세월 동안 TV라는 영상 매체의 길들여졌고 이러한 TV로 대표되는 영상 미디어는 이제 인류와는 떼려야 뗄 수 없는 관계가 되어 그 영향력은 더욱 커져가고 있다. 인터넷이 보급되고 WWW(World Wide Web)을 통해서 사람들이 좀 더 친숙하게 인터넷을 이용 할 수 있는 서비스가 개발되면서 디지털 영상 미디어는 인터넷이라는 통신망의 기반 위에 빠르게 대중에게 그 영향력을 넓혀갈 수 있었다. 좀 더 다양한 정보와 풍부한 자료를 원하는 사용자의 요구는 인터넷이라는 매체의 특징과 맞물려 시너지 효과를 낳기에 충분했다. 그 결과 WWW는 영상과 텍스트를 기반으로 정보를 전달하는 기능을 우선적으로 발전시키게 되었고 정보 제공자들 역시 이러한 사용자의 요구와 특성을 우선적으로 인터넷에 반영하게 되었다. 인터넷 초기의 발전을 이끄는데 지대한 공헌을 한 것이 성인 콘텐츠라는 것을 부인 할 수 없는 것도 이러한 이유 때문이다. 인터넷과 디지털 영상 미디어는 이로서 TV에 이어 두 번째의 전성기를 맞이하게 되었다. 이와 함께 다양한 통신 수단과 진보된 전달 수단들이 속속 개발되고 보급되면서 영상 미디어의 영향력은 더욱 커지게 되었고 이전에는 상상하기 힘들었던 고품질의 영상 미디어가 손쉽게 제작되고 유통되고 제공되기에 13

15 이르렀다. 이러한 영상은 크게 정지 영상과 동영상으로 나뉘어 질 수 있으며 현재 영상 미디어와 관계된 관련 산업의 제품들은 크게 미디어를 제작하고 유통하고 이용하는 것의 3분야로 나뉘어 질 수 있다. 디지털 영상 미디어의 제작을 위해서 필요로 하는 기기로서는 대표적으로 디지털 카메라와 캠코더를 들 수 있다. 이 두 가지 기기는 현재 대중에게 가장 널리 알려져 있고 실제로도 가장 많이 사용하는 전자기기 중 하나이다. 기존의 필름 카메라와는 달리 디지털 소자와 저장매체를 이용하기 때문에 아날로그 환경에서보다 보다 편리하고 저렴한 비용으로 많은 데이터를 생산해 낼 수 있다. 최근에는 실제 필름 카메라의 화질과 맞먹는 품질을 갖춘 디지털 카메라들이 속속 등장하고 있어서 실제로 아날로그의 장점을 디지털 미디어가 모두 흡수하면서 디지털 미디어 자체의 장점은 더욱 부각시키는 현상이 관찰되고 있다. 이러한 현상은 고품질의 영상 미디어의 손쉬운 제작 환경을 마련하는 계기가 되었다. 인터넷은 이와 같이 만들어진 디지털 영상 미디어를 손쉽게 유통시키고 배포 할 수 있는 다양한 인프라를 갖추고 있다. 사용자는 이제 별다른 조작 없이도 자신이 생산해낸 고품질의 영상 미디어를 쉽게 가공하고 배포 할 수 있게 되었다. 최근에는 웹이 개개인의 개성을 중시하는 경향으로서 블로그(blog)나 개인 홈페이지를 기반으로 UCC(User Created Contents)라 불리는 개인의 미디어를 자유롭게 배포하는 방식을 많이 취하고 있다. 이를 위해 관련 비즈니스 사업자들은 사용자가 최대한 간편하고 효율적으로 개인의 영상 미디어를 배포할 수 있는 편리한 도구를 제공하고 있다. 이러한 웹 기반의 인터넷은 14

16 미디어의 배포뿐만이 아니라 취득에도 손쉬운 방법을 제공한다. 이렇듯 디지털 영상 미디어에 대한 수요와 공급은 어느 쪽이 높다 낮다는 논의하는 것이 무의미할 만큼 그야말로 폭발적으로 연쇄반응을 일으키며 인터넷을 중심으로 하는 통신 망을 따라 유통되고 있다. 이러한 상황에서 멀티미디어 데이터에 대한 관리의 부재로 인하여 많은 문제들이 발생하고 있으며 이로 인해 방대한 양의 미디어에 대한 관리의 필요성이 제기되어 왔다. 인터넷을 기반으로 하는 디지털 영상 미디어의 유통에 있어서 대표적이며 가장 유용한 관리 도구는 검색(retrieval)이다. 세부적으로 검색에는 여러 가지 방법이 있지만 이러한 방법론을 떠나서 인터넷을 통해서 유통되는 방대한 미디어들 중에서는 사용자가 필요로 하는 정보도 있지만 오히려 사용자에게는 불필요한 정보의 비중이 월등히 높다. 따라서 이러한 불필요한 정보들 사이에서 사용자가 필요로 하는 정보만을 정확히 검색해 내는 것이 무엇보다도 중요하다. 오늘날 인터넷에서 검색엔진 및 검색 사이트의 중요성이 높은 것도 역시 같은 맥락이라고 볼 수 있다. 전 세계적으로는 Google[1], 국내에서는 NAVER[2]로 대표되는 인터넷 검색엔진은 얼마나 사용자가 필요로 하는 정보를 정확히 검색해 내느냐 하는 능력에 따라 전체 인터넷 사용의 패러다임을 바꾸어 놓을 만큼 중요한 위치를 차지하고 있다. 질의 방식에 따라 차이가 있지만 기본적으로 검색은 질의와 유사한 정보를 결과물로서 제시하는 것을 목적으로 하며 그 결과물들이 질의와 실제로 얼마나 유사하며 유용한 정도가 성능의 척도로 사용된다. 멀티미디어 검색을 위해서 15

17 영상 또는 동영상의 특징(feature)를 이용하는 것이 일반적인 방법이며 주로 색상(color), 텍스쳐(texture), 형태(shape)등을 이용한다[3-10]. 이와 관련된 다양한 연구와 함께 멀티미디어 검색기술은 국제 표준 기술로서 발전되어 MPEG-7이라는 이름으로 제정되었다[11, 12]. 멀티미디어 검색은 각각 서로 다른 영상 및 동영상의 특징을 이용함으로써 유사한 영상이나 동영상의 기준 역시 사용되는 특징에 한정되는 단점이 있다. 따라서 내용적으로 유사하지 않은 영상도 실제 사용된 특징이 비슷하면 서로 유사한 영상으로 잘못 판별하게 된다. 게다가 내용적으로는 유사한 영상이 사용되는 특징 값이 서로 다르다는 이유로 서로 무관한 관계로 잘못 판단할 가능성이 높다는 단점이 있다. 검색의 특정 용도로서 식별(identification)은 실제로 매우 중요한 응용분야이다. 식별이란 질의와 유사한 결과물을 원하는 것이 아니라 질의와 동일한 것을 결과물로 정확히 도출해 내는 것을 말한다. 예를 들어 특정 데이터베이스에서 질의와 똑같은 것을 정확히 찾아내는 것이 식별의 대표적인 경우이다. 본 논문에서 사용하는 내용 기반 식별은 기본적인 식별의 개념을 확장하여 두 미디어의 형태가 변경되었더라도 미디어 자체의 내용이 동일하다면 같은 미디어로서 인정한다. 즉 데이터베이스 내에서 질의와 형태적으로는 다르지만 내용적으로는 동일한 미디어를 결과물로 도출 해야만 정확한 식별 기능을 수행했다고 판단 할 수 있다. 실제로 멀티미디어 데이터로 구성되는 대용량 데이터베이스는 새롭게 생성되는 수많은 데이터들이 주를 이루지만 어떠한 하나의 데이터로부터 변형되거나 복사되어 동시에 존재하는 16

18 경우도 상당수 존재한다. 더불어 인터넷을 통해 유통되는 데이터들 역시 그 자체가 단순한 이동이 아니라 복사되는 경우가 대부분을 이루고 복사된 데이터는 사용자들에 의해서 조금씩 변형이 가해지게 되는 경우가 대부분이다. 이를 테면 사용자는 특정 웹사이트로부터 사진을 자신의 PC로 내려 받아 자신이 원하는 대로 변형한 다음 다시 자신의 PC에 재저장하게 된다. 이러한 경우 PC를 포함한 네트워크 상에는 원본을 포함한 복사본과 변형본이 함께 존재하게 된다. 만약 이 사용자가 다시 한번 자신의 변형된 사진을 배포하게 된다면 원본에 대한 복사본과 변형본은 기하급수적으로 늘어나게 된다. 따라서 인터넷과 같은 네트워크 기반을 둔 현재 상황에서 이러한 복사본 및 변형본만을 정확하게 찾을 수 있는 기술이 매우 요구되는 상황이다. 기존의 멀티미디어 식별 기능을 수행 할 수 있는 기술로서 대표적으로 복제 검출 기술이 한 예가 될 수 있다[13-20]. 복제 검출 기술은 특정 영상이 복제되거나 원본과 유사한 수준의 변형이 가해졌을 경우 일련의 특징을 비교함으로써 원본의 복사본을 검색해 내는 기술이다. 이와 함께 멀티미디어 핑거프린팅 기술 역시 응용분야는 조금씩 다르지만 식별 기술과 매우 유사한 기능을 수행한다[21-24]. 핑거프린팅 기술은 영상 또는 동영상으로부터 변형에 불변한 고유의 핑거프린트를 추출하여 구성한 데이터베이스를 이용하여 불법적으로 변형되거나 배포된 미디어를 찾아내는 기술이다. 그러나 복제 검출 기술이나 핑거프린팅 기술은 대부분 수백 또는 수천장의 소규모 데이터베이스를 기준으로 실험되었고 일부 변형에 대해서만 강인하고 기타 변형에 대해서는 17

19 취약한 성능을 보인다. 더불어 대용량 데이터베이스 처리를 위해서는 빠른 정합 속도가 보장되어야 하나 대부분의 알고리즘이 검색 성능에 초점을 맞춘 나머지 상대적으로 매우 높은 복잡도를 보이는 단점이 있다. 몇몇 알고리즘의 경우 이진 수열 형태를 이용하여 빠른 정합 속도를 보이지만 이 경우 반대로 변형에 대하여 매우 낮은 성능을 보이는 것이 일반적이다[19, 21]. 따라서 영상의 변형에 불변하고 대용량 데이터베이스에 사용이 가능하도록 매우 빠른 정합 속도와 함께 높은 강인성을 갖는 식별자의 개발이 필요하다. 본 논문에서는 영상 내의 공간적인 위치에 따라 상대적인 픽셀값의 관계를 이용하여 영상의 고유함을 서술함으로써 동일한 내용의 영상은 변형되더라도 동일한 영상으로 인식하는 식별을 위한 서술자를 제안하였다. 이를 위하여 본 논문에서 제안된 서술자는 먼저 영상을 정해진 각도 단계와 반지름 단계를 사용하여 동심원 형태로 구획한다. 가장 빈번한 변형 중 하나인 영상회전의 경우에도 동심원 형태로 구획된 하나의 고리영역에서는 상대적인 위치가 바뀔지언정 고리 내의 픽셀은 그대로 유지되어 회전에 불변한 서술이 가능해 진다. 이와 함께 구획된 세부 영역 사이에서 서로 공간적인 위치에 따른 상대적인 관계를 서술하는데 영상자체의 형태를 서술하기 위하여 다양한 공간적인 관계를 이용한다. 이 때 공간적인 관계를 따질 때 전혀 관련 없는 영역만을 서술할 경우 자칫 서술자의 분포가 랜덤 분포를 보일 수 있으므로 영상 내의 고유의 정보를 표현할 수 있고 영상마다 나름 고유의 규칙성을 보일 수 있는 공간적인 분포를 이용한다. 본 논문에서는 하나의 반지름 영역을 18

20 하나의 공간적인 위치로 이용하고 세부 구역별로 주변 영역과 동심원의 중심에 대하여 대칭적인 위치의 영역과의 관계를 서술한다. 서술자는 최종적으로 이진 수열 형태로 변환되어 매우 빠른 속도로 정합이 가능하며 이를 통해 매우 많은 영상을 포함한 대용량 데이터베이스에서도 적용이 가능하다. 본 논문은 총 8장으로 구성되며 2장에서는 본 논문의 목표와 관련된 기존의 연구 동향에 대한 소개를 하고 3장에서는 정지 영상 식별을 위해서 본 논문에서 제안한 방법을 자세하게 기술한다. 그리고 4장에서는 동영상 식별을 위한 제안된 방법을 기술한다. 5장과 6장에서는 각각 정지 영상과 동영상 식별을 위하여 본 논문에서 제안된 방법들의 성능에 대한 평가를 수행하였으며 그 결과를 도시한다. 그리고 7장에서는 본 논문에 대한 결론을 기술하고 마지막으로 8장에서는 본 연구와 관련된 참고 문헌을 소개한다. 19

21 제 2 장 관련 연구 2장에서는 정지 영상 및 동영상의 검색과 식별에 관련된 기존의 연구들을 소개한다. 먼저 멀티미디어 검색과 식별의 차이점에 대하여 개략적인 설명과 함께 일반적인 멀티미디어 검색 기술 그리고 멀티미디어 검색을 위한 국제 표준인 MPEG-7의 정지 영상 및 동영상 관련 서술자들을 자세히 소개한다. 또한 멀티미디어 데이터의 식별을 위한 관련 연구들을 정리하고 현재의 동향을 살펴본다 멀티미디어 검색과 식별 일반적으로 정지 영상 및 동영상 식별은 기존의 검색과 많은 부분에서 비슷한 부분을 공유하지만 궁극적으로는 다른 목표를 가지고 있다. 우선적으로 기존의 검색은 글자 기반 질의 방식과 예시 기반 질의 의 두 가지 방식이 존재한다. 식별은 입력 자체가 결과물의 형태와 동일한 미디어이기 때문에 예시 기반 질의만이 가능하다. 글자 기반 질의의 경우는 사용자의 주관이 많은 부분 개입되어 결과물과의 정확한 식별 여부를 판단하기가 불가능하다. 또한 검색의 경우 사용자 또는 알고리즘의 주관적인 특성이 개입되어 결과물을 도출하게 된다. 글자 기반 질의의 경우 어떠한 특정 질의에 대해서 검색할 경우 검색 알고리즘의 주관적인 특성에 따라 질의의 특정적인 부분만을 고려하여 결과를 20

22 도출한다. 예를 들어, 바다 라는 것을 질의로 입력하여 정지 영상 또는 동영상을 검색할 경우 미디어 내에서 바다와 관련성이 높을 경우 결과물 사이에는 전혀 다른 콘텐츠라고 할지라도 높은 상관성을 지닌 결과물로 출력된다. 예시 기반 질의로서 동해안 바다 사진을 입력하였을 경우에도 검색 알고리즘의 특성에 따라 바다 색깔만을 기준으로 검색할 수 도 있고 바다 모양만을 보고 바다가 아닌 다른 영상을 검색해 낼 수도 있다 (그림 2.1). 그림 2.1 예시 기반 검색의 예 Figure 2.1 Searching example using query by sample 그러나 식별의 경우에는 입력으로 사용한 영상과 동일한 내용을 갖는 특정 결과물을 원하기 때문에 궁극적으로 검색과 식별에는 이와 같은 차이점이 21

23 존재한다. 검색에는 특징 기반 검색과 내용 기반 검색의 두 가지 방식이 존재한다. 위에서 언급한 일반적으로 어떠한 주관적인 성향을 가지고 검색을 수행하는 것이 바로 특징 기반 검색이고 이때 특징으로 사용하는 대상이 검색 결과의 주관성을 좌우한다. 이에 반해 내용 기반 검색은 질의 미디어가 지니고 있는 내용을 분석하여 유사한 결과물을 도출한다. 그러나 두 가지 방법 모두 질의와 동일한 결과물을 원하는 것은 아니다. 이에 반해 식별은 내용 기반 식별 기능만을 고려하며 질의로 사용된 미디어와 동일한 내용을 갖는 미디어를 검색해 내는 것이 주요 목표이다. 따라서 어떠한 몇 가지 특징에만 의지하여 검색을 수행하는 것이 아니라 실제로 미디어가 의미하는 내용이 무엇이고 그와 같은 내용을 담고 있는 콘텐츠를 찾아내어야 한다. 그림 2.2은 실질적인 검색과 식별의 응용에서의 차이점을 보여주고 있다. 다수의 정지 영상으로 구성되어 있는 데이터베이스에 대하여 특정 영상을 질의로 사용할 경우 검색의 경우와 식별의 경우는 서로 다른 결과를 보여준다. 검색의 경우 질의와 어떠한 특징적으로(예: 색상) 유사한 영상들을 결과물로 도출하지만 식별의 경우 질의와 동일하거나 질의의 변형된 영상들만을 결과물로 도출한다. 그림 2.2에서 보듯이 검색의 경우 지정된 특징만을 이용하기 때문에 색상이 변하거나 회전이 된 영상들을 찾지 못하고 유사한 색상의 영상들만을 출력하는 반면 식별의 경우 회전이 되거나 색상의 변화가 생긴 경우를 원본과 동일한 것으로 인식하는 것을 볼 수 있다. 22

24 그림 2.22 검색과 식별 별의 응용 비교 교 Figure Comparison in applica ations betwee en retrieval and a identifica ation 검색의 경우 실제로 로 질의와 유사한 유 정보를 를 갖는 결과 과물을 원하는 는 만큼 출력할 수 있다. 다만 상위 결과물이 이 좀 더 연관성이 연 높아 아야만 한다. 그러나 식별의 경우 우 내용적으로 원하는 일치하는 결과물의 것은 수 수는 한정되어 어 한정적 적이기 때문 문에 있다. 다 다시 말해 실제 정 정확하게 질의와 부합되는 결과물은 정해진 정 결과물 물의 수보다 적을 수도 있다. 따라서 서 내용적으로 로 서로 다른 영상끼 끼리는 확연 연한 차이를 보여야만 한다. 이를 를 독립성(paiir-wise independencce)이라고 하며 이는 서로 로 다른 영상을 같은 것이 이라고 잘못 판단할 확률인 양성 성 오류율(falsse positive ra ate)로써 평가 가한다. 그리고 고 식별에서의 의 실제 성능 평가는 는 정해진 양성 오류율을 기준으로 성능 성 평가를 하게 된다. 따라서 일반적으로 식별의 성능 능은 매우 낮은 낮 수준의 특정 양성 오류율로 정해진 23

25 독립성을 보장하는 조건하에서의 식별 성능을 나타낸다. 검색과 식별 기능 모두 질의와 대상이 존재하고 일반적으로 대상은 데이터베이스의 형태를 이루어 질의에 대하여 대상 내에서 원하는 결과물을 도출하는 형식을 띈다는 점에서는 공통점이 있으며 대상을 구성하는 방식은 둘 다 일괄처리 방식으로서 검색이나 식별을 위한 서술자를 추출하는 과정은 상대적으로 복잡도 조건에 제약을 덜 받게 된다. 그러나 반대로 실제로 검색이나 식별을 수행하기 위해서는 질의에 대하여 데이터베이스 내에서 대조 및 정합 작업이 이루어져야 한다. 일반적으로 데이터베이스 내에는 많은 양의 미디어에 대하여 표현된 대용량의 서술자가 들어있기 때문에 질의에 대하여 정합하는 속도는 매우 높은 조건을 요구하게 된다. 이는 검색과 식별 모두 마찬가지이다. 위와 같은 검색과 식별의 차이점을 정리하면 표 2.1과 같다. 표 2.1 멀티미디어 검색과 식별의 비교. Table 2.1 Comparison between multimedia retrieval and identification. 질의 형태 멀티미디어 검색 (Multimedia Retrieval) 글자 기반, 예시 기반 질의 모두 가능 멀티미디어 식별 (Multimedia Identification) 예시 기반 질의 가능 검색 방법 특징 기반 내용 기반 추출 환경 일괄처리(off-line) 일괄처리(off-line) 정합 환경 실시간 처리(on-line) 실시간 처리(on-line) 24

26 이와 같은 조건을 만족하는 멀티미디어 데이터 식별을 위한 알고리즘을 개발하는 것이 매우 요구되며 본 논문에서는 동심원 구획 기반 서술자를 이용하여 고속으로 정지 영상 및 동영상을 대용량 데이터베이스에서 질의에 대하여 정확하게 식별해 내는 방법을 제안하고 있다 멀티미디어 검색 멀티미디어 검색은 대량의 멀티미디어 데이터베이스 내에서 원하는 미디어를 효과적으로 표현하고 검색해내는 기술을 말한다[3, 8, 10, 25]. 멀티미디어 검색 연구의 시초는 1970년대로 거슬러 올라가는데 1979년 픽토리얼 응용을 위한 데이터베이스 관리 기술에 관한 학술회의가 개최된 이래 많은 관련 연구가 이루어졌다[26-28]. T. Kato는 이전에도 영상에 대한 사람의 인식에 관한 연구를 수행하였는데 이를 바탕으로 1992년에 영상에 대한 독립적인 표현의 방법을 통해서 영상 데이터베이스를 관리하는 방식을 제안하였다[29]. 대표적인 응용으로서 대략적인 스케치를 질의로 사용하여 영상을 검색해 내는 기술을 제안하였다. 초기 대부분의 멀티미디어 검색은 컴퓨터 비젼의 차원에서 연구되어 주로 특징 기반 유사도 검색이 주를 이루었다[30]. 여기서 사용되는 특징은 크게 색상, 텍스쳐 그리고 형태이다. 색상 정보는 영상을 구성하는 중요한 정보 중 하나로서 일반적으로 히스토그램 형태로 많이 사용되며 영상에 대한 전역(global) 정보로서 매우 유용하다[4]. 텍스쳐 정보는 영상 내에서 표현되는 일종의 질감정보로서 개개의 픽셀들이 25

27 모여서 이루는 일정한 패턴을 사용한다[5, 6]. 텍스쳐 정보와 컬러 정보는 서로 상호 보완적인 성격이 짙기 때문에 복합적으로 사용함으로써 성능 향상을 꾀하기도 한다[31, 32]. 일반적으로 색상정보는 전역 정보를 나타내고 텍스쳐 정보는 국소(local) 정보를 나타냄으로써 서로의 장단점이 서로 유기적으로 결합되어 더 높은 성능을 이끌게 된다. 형태를 이용하는 검색 방법은 일반적인 영상에 적용하기 보다는 실제로 특정 응용에 대해서 적용하는 것이 일반적이다[33, 34]. 형태를 직접 이용하기 위해서는 전처리 단계로서 분할(segmentation)과정이 필요한데 이러한 분할 작업은 매우 어려운 분야 중 하나이기 때문에 안정적인 검색 성능을 보장하기 어렵다. 이러한 기본적인 영상의 특징을 이용하던 검색 방법은 그 밖의 여러 가지 특징을 추가적으로 연구가 되었고 2000년대 들어서 이러한 것들이 정비되어 MPEG-7이라는 국제 표준으로 정리되었다[11, 35]. 검색 성능을 보다 높이기 위해서 새로운 특징을 개발하고 이러한 추출된 특징 사이의 유사도를 측정하는 방법에 대한 연구도 함께 이루어 졌다. Beretti는 그래프 정합 방법에 근거한 새로운 유사도 측정 알고리즘을 제안하였으며 Cooper는 시간 정보와 픽셀 정보를 동시에 활용한 새로운 유사도 측정 방법을 제안하였다[36, 37]. 최근 들어서는 기존의 특징 기반 방법들이 해결하기 힘들었던 크기 변환과 부분 삭제 등의 변형에도 강인하도록 특징점 기반 방법들이 제안되었는데 Lindberg는 특징 크기 단계(characteristic scale level)라는 이론을 정립하여 각 특징점 별로 해당되는 크기를 자동적으로 할당하도록 하여 다른 크기 불변 알고리즘들의 기반 역할을 26

28 하였다[38]. 이후 크기 단계를 결정하는 요소로서 Laplacian of Gaussian (LoG)가 Mikolajczyk 와 Schmid에 의해서 제안되었고 실제로 매우 좋은 성능을 보여주었다[39]. 이와 더불어 Lowe는 difference of Gaussian(DoG)를 이용하여 유사한 크기 단계를 구성할 수 있도록 알고리즘을 정립하였고 많은 분야에서 활용되고 있다[40]. 그러나 이러한 특징점 기반 크기 불변 알고리즘은 실제로 특징점을 추출하는데 있어서 재연성이 완벽하게 보장되지 않는 이유로 많은 부가적인 연산을 필요로 한다. 그럼에도 불구하고 기존에 서술자들이 해결하기 힘들었던 심각한 변형에 대한 강인성을 유지하기 때문에 지속적으로 연구가 이루어지고 있다 MPEG-7 영상 서술자 MPEG-7은 국제 표준 기구인 ISO/IEC에서 기존의 멀티미디어 데이터와 관련된 표준인 MPEG-1과 MPEG-2와 함께 나날이 증가하는 멀티미디어 데이터에 대한 효율적인 서술(description)과 관리(management)를 위하여 제정한 국제 표준 기술이다[11, 35]. MPEG-7 표준은 기존에 제정된 멀티미디어 관련 다양한 표준과 독립적 또는 상호 보완적으로 사용이 가능하고 후에 제정될 표준과의 보완성을 동시에 고려하였다. 이러한 특징으로 인해서 MPEG-7 표준은 다른 멀티미디어 표준 기술에 좀 더 폭넓은 유연성을 제공하는 역할을 수행한다. 기본적으로 MPEG-7은 멀티미디어 콘텐츠의 디지털 신호로서의 묘사를 통해서 콘텐츠에 맞는 서술자를 생성해내는 것에 기본적인 목표를 두고 27

29 있으며 그림 2.3은 이러한 MPEG-7 표준의 범위를 도시하고 있다. 그림 2.3에서 보다시피 MPEG-7 표준은 실제 멀티미디어 데이터의 묘사 또는 서술하는 기술에 초점을 맞추고 있으며 MPEG-7을 통해서 미디어에 대한 서술자(descriptor)의 가공 및 응용은 실제 MPEG-7 표준의 범주에는 속하지 않는다. 그림 2.3 MPEG-7 표준의 범위 Figure 2.3 The scope of MPEG-7 standard 실제로 MPEG-7 표준 기술을 통해서 생성되는 멀티미디어 데이터의 묘사된 정보를 효율적으로 활용하기 위해서는 자동적으로 대량의 멀티미디어 데이터에 대하여 해당 서술자를 추출하도록 하는 기술이 뒷받침되어야 한다. 이러한 기술과의 접목을 통해서 많은 양의 멀티미디어 데이터로부터 서술자를 추출하여 데이터베이스화 시키면 서술자로 이루어진 데이터베이스만으로도 다양하게 콘텐츠를 관리하고 제어할 수 있게 된다. MPEG-7에서는 이러한 서술자의 체계적이고 효율적인 제어를 위하여 관련 요소들을 정의하고 있다. 그림 2.4는 MPEG-7의 관련 요소들의 관계를 나타내고 있다[41]. 그림 2.4에서 28

30 서술자(descriptors)는 가장 기본적이면서도 중요한 요소로서 멀티미디어 데이터로부터 추출한 특징을 묘사하고 표현하는 구조를 나타내며 실제로 MPEG-7 기술에서의 기본단위라고 볼 수 있다. 이러한 서술자들은 서술 방법(Description Scheme)을 통하여 구조화 되어 개별적으로 표현된 서술자들을 유기적으로 연결함으로써 좀 더 효율적으로 서술자가 사용될 수 있도록 돕니다. 이러한 서술자와 서술 방법은 모두 서술 정의 언어(Description Definition Language)를 통해서 정의되고 이렇게 정의된 규칙에 의하여 모든 요소들이 구성된다. 이렇게 구성된 서술자는 최종적으로 텍스트 형태나 이진(binary)형태로 구성되어 응용된다. Description Definition Language Definition DS1 D6 D7 D1 DS1 D8 D2 D4 D1 D3 D5 D2 D4 DS1 D5 D3 Encoding & Delivery Descriptors Descriptor Scheme 그림 2.4 MPEG-7 요소들 사이의 관계 Figure 2.4 The relation of MPEG-7 elements 이렇게 생성된 MPEG-7 멀티미디어 서술자를 이용하면 다양한 분야에서 29

31 응용이 가능하며 주로 검색과 인덱싱에서 사용 할 수 있다. 그림 2.5은 MPEG-7기술을 이용한 실제 응용 시스템의 예를 보여주고 있다. 그림 2.5 MPEG-7 표준 기술을 이용한 응용의 예 Figure 2.5 Example of the application using MPEG-7 standard technology 먼저 이 시스템의 시작은 다양한 멀티미디어 데이터에서 출발한다. 이러한 다양한 멀티미디어 데이터로부터 각각 응용 분야와 목표에 부합하는 특징을 추출한다. 추출된 특징들은 MPEG-7의 서술자와 서술 방법 등을 이용하여 독립적인 서술자 구조가 완성되어 최종적으로는 이진 형태나 텍스트 또는 XML형태로 재생산된다. 서술자는 데이터베이스로서 저장 매체에 정적으로 저장될 수도 있고 형태적 변화를 거친 다음 통신선로를 통해 전송될 수도 있다. 이러한 형태를 띄는 서술자 또는 하나의 데이터베이스로서의 그들의 집합은 다양한 분야에서 사용 가능한데 검색을 위하여 사용될 수도 있고 다양한 30

32 대용량의 정보를 일정한 규칙에 의하여 분류하여 열람하는 용도로서도 사용이 가능하다. 특정 응용에서는 통신선로를 통해 전송되는 모든 데이터에 대해서 서술자 데이터베이스를 검색하여 특정 정보들만을 선별할 수도 있다. 현재 MPEG-7은 총 10개의 부분으로 분류되어 있으며 표 2.2와 같다. 표 2.2 MPEG-7 표준의 세부 구성. Table 2.2 Components of MPEG-7 standards. 순 번 Part 1 Part 2 Part 3 Part 4 Part 5 Part 6 Part 7 Part 8 Part 9 Part 10 이 름 System Description Definition Language (DDL) Visual Audio Multimedia Description Scheme (MDS) Reference Software Conformance Testing Extraction and use of Descriptions Profiles and Levels Schema Definition MPEG-7의 첫 번째 파트는 시스템(system) 파트로서 MPEG-7을 이용하여 실제 시스템을 구축 할 때 필요한 것들을 구성하는 부분이며 주로 서술자의 효율적인 저장과 전송 그리고 미디어와의 동기화에 주안점을 두고 있다. 두 31

33 번째 파트는 서술자 정의 언어로서 서술자 또는 서술 방법 등에 사용될 언어를 정의하는 부분이다. 이 파트에서는 사용될 데이터 형태나 콘텐츠 모델 등을 정의한다. 세 번째 파트는 영상에 관련된 서술자를 정의한 부분으로서 주로 정지 영상과 동영상에 초점을 맞추고 있으며 부가적으로 얼굴인식 기술을 다루고 있다. Part 4는 음성 데이터를 위한 서술자를 정의하고 있다. Part 5는 일반적인 특징들과 미디어로부터 추출한 서술자를 효율적으로 결합 및 보완 사용하기 위한 멀티미디어 서술 방법에 대하여 정의하고 있다. 여섯 번째 파트는 전체 MPEG-7 표준을 위한 참조 소프트웨어에 대한 내용을 담고 있으며 Part 7은 MPEG-7의 정의된 표준과 일치하는 구현을 위한 개괄적인 안내서 역할을 하고 있다. Part 8은 실제 표준 기술로서 채택된 필수 내용은 아니지만 실제 서술도구의 사용방법과 이를 이용한 서술자의 추출에 대하여 자세하게 기술하고 있다. Part 9은 MPEG-7의 표준기술을 이용한 세부적인 프로파일(profile)과 각 프로파일에서의 세부 레벨(level)을 정의하고 있으며 마지막으로 Part 10은 부가적으로 서술자 정의 언어를 구성하기 위한 추가적인 스키마에 대한 정보를 담고 있다. 위와 같은 여러 가지 MPEG-7의 세부 구성 요소들 중에서 실제로 가장 중요한 부분은 멀티미디어 데이터를 위한 서술자를 기술하고 있는 Part 3와 Part 4 이다. 그 중에서도 정지 영상 또는 동영상 데이터에 대한 서술자는 Part 3에서 기술되어 있다. 영상 서술자에는 크게 색상, 텍스쳐, 형태학적 그리고 움직임 서술자가 있다. 각 영상 서술자의 자세한 알고리즘은 다음과 같다. 32

34 색상 서술자 컬러 서술자는 정지 영상 또는 동영상내의 컬러 정보를 이용하여 미디어를 묘사하는 서술자로서 MPEG-7 총 7가지의 색상 서술자가 정의되어 있고 다음과 같다. 색상 공간 (color space) 색상 양자화 (color quantization) 주요 색상 (dominant color) 가변 색상 (scalable color) 색상 배치(color layout) 색상 구조 (color structure) GoF/GoP 색상 색상 공간 색상 공간 서술자는 정지 영상에 대하여 다양한 색상 공간에 따라서 콘텐츠를 서술하기 위해 정의되어 있는 서술자로서 일반적으로 RGB, YCbCr, HSV(Hue Saturation Value) 그리고 HMMD(Hue Max Min Difference)등의 색상 공간을 표현한다. 33

35 색상 양자화 색상 양자화는 각 색상 공간에서 색상 값을 정해진 정수형 값으로 치환하는 함수를 정의하고 있다. 색상 공간과 색상 양자화는 주로 독립적으로 사용되기 보다는 보조적인 서술자로 다른 서술자와 같이 사용된다 주요 색상 주요 색상 서술자는 영상내의 특정 영역을 소수의 색상수를 이용하여 표현하고자 할 때 유용한 서술자이며 특정 영역이 아닌 영상 전체에 대해서도 가능하다. 이 색상 서술자에서 색상 양자화가 사용되며 각 양자화된 색상의 사용빈도를 계산하여 주요 색상을 표현한다. 영상내의 주요 색상의 빈도를 계산할 때에는 공간적 긴밀성(coherency)를 고려하여 계산하게 된다. (a) (b) 그림 2.6 색상의 서로 다른 공간적 긴밀성의 예 (a) 낮은 긴밀 성, (b) 높은 긴밀성 Figure 2.6 Example of different spatial coherency of color. (a) low coherency, (b) high coherency 이를 테면 그림 2.6에서 두 영상은 히스토그램은 동일하지만 영상내의 34

36 공간적 긴밀성 측면에서는 (a)영상이 (b)영상에 비해 보다 높은 긴밀성을 지니게 된다[41]. 따라서 주요 색상 서술자에서는 이러한 공간적 긴밀성을 같이 고려하여 최종적인 색상의 빈도를 계산한다 가변 색상 가변 색상 서술자는 HSV 색상 공간 내에서의 영상의 색상 히스토그램의 일종으로서 Haar 변환을 통해서 가변적으로 이진 형태로 변조화가 가능하다. 이진 변환에서의 표현이 가변적이기 때문에 서술자의 정확도와 서술자의 데이터 크기 사이에서 사용자가 적절한 선택을 통해서 최적의 서술자를 추출할 수 있다. 가변 색상 서술자는 주로 색상 기반의 영상의 검색 및 색인에 주로 사용된다 색상 배치 색상 배치 서술자는 영상 내에서 색상의 공간적인 분포를 표현하는데 효율적인 도구이며 매우 적은 연산량으로도 높은 성능을 보인다. 특히 서술자의 정합에 있어서 매우 적은 연산량을 요구 하기 때문에 동일한 시간 내에 대량의 데이터를 처리 할 수 있다. 기본적으로 이 서술자는 YCbCr 색상 공간을 사용하고 각 색상 값은 8bit의 양자화 범위를 가지고 있다. 더불어 정지 영상은 물론 비디오 프레임에도 직접 적용이 가능하기 때문에 다양한 응용 분야에서 35

37 사용이 가능하다. 서술자의 이진 표현에 있어서 색상 배치 서술자는 가변 색상 서술자와 마찬가지로 데이터 크기와 정확도에 있어서 가변성을 제공하기에 두 가지 요소를 고려하여 서술자의 크기를 결정할 수 있다 색상 구조 색상 구조 서술자는 영상 내의 색상 정보뿐만 아니라 영상 자체의 구조적인 정보까지 표현할 수 있다. 이 서술자는 주로 정지 영상의 검색에 효과적으로 활용가능하며 특히 불규칙하고 독립적인 객체로 구성되어 있는 영상이 주요 대상이 된다. 이 서술자는 특정 형태를 지닌 색상 구조 요소를 이용하여 국소적인 색상 구조를 묘사하여 기존과는 다른 형태의 색상 히스토그램을 구성한다. 그림 2.7 구조화된 색상과 구조화되지 않은 색상 분포의 예 Figure 2.7 Example of structured and unstructured color distribution 영상내의 같은 색상 분포라도 구조화되어 있는 경우와 구조화 되어 있지 36

38 않은 경우는 그림 2.7을 통해 이해 할 수 있다[41] GoF/GoP 색상 GoF/GoP 색상 서술자는 정지 영상에서 주로 사용되던 색상 정보를 비디오 데이터에 대하여 사용하기 위하여 정의되었다. 이 서술자는 실제로 가변 색상 서술자를 비디오를 위하여 확장한 방법이며 이를 위해 약간의 전처리 과정을 필요로 한다. 정지 영상에서 사용 가능한 가변 색상 서술자를 사용하기 위해서 GoF/GoP 색상 서술자는 우선적으로 정해진 GoF(Group of Frames) 또는 GoP(Group of Pictures)에 있는 각 프레임으로부터 HSV 색상 공간상의 색상 히스토그램을 구한다. 그리고 가변 색상 서술자에서 Haar 변환을 취하기 전에 각 프레임으로부터 구해진 다수의 히스토그램의 각 색상축의 값들을 정해진 방법에 따라서 병합한다. 병합하는 방법으로는 평균값, 중간값, 최소값의 세가지 방법이 정의되어 있다. 위의 세가지 방법 중 한가지를 이용하여 각 히스토그램을 병합하여 하나의 히스토그램을 생성한 후 기존의 가변 색상 서술자에서와 마찬가지로 Haar 변환을 통하여 최종적인 서술자를 완성한다. GoF/GoP 색상 서술자는 상대적으로 매우 적은 연산량을 요구하며 최종적으로 생성된 서술자의 크기 역시 매우 작아 빠르게 비디오 데이터를 검색하는데 주로 사용된다. 37

39 텍스쳐 서술자 다양한 영상들 중에서 물, 토양 이나 옷감같이 특정한 패턴이 영상 내에 표현되는 경우에는 이러한 패턴을 서술할 수 있는 텍스쳐 서술자를 이용하는 것이 효과적이다. 일반적으로 텍스쳐 정보는 다수의 픽셀값이 모인 일정 이상의 영역에 독립적으로 나타나는 특징값으로서 규칙적으로 또는 불규칙적으로 영상 내에서 나타난다. MPEG-7에서는 총 3개의 텍스쳐 서술자를 정의하고 있고 다음과 같다. 균등 텍스쳐(homogeneous texture) 텍스쳐 열람(texture browsing) 경계선 히스토그램(edge histogram) 균등 텍스쳐 균등 텍스쳐 서술자는 대용량의 정지 영상 데이터베이스 내에서 비슷한 패턴을 지닌 영상들을 검색하고 열람하는 것을 주요 목표로 삼고 개발되었다. 기본적으로 이 서술자는 모든 영상은 다양한 형태를 띠는 각각의 작은 균등한 모양을 갖는 텍스쳐들의 집합이라고 가정하고 있으며 따라서 이러한 각각의 텍스쳐들을 이용하여 전체 영상의 패턴을 서술하는 것을 시도한다. 이러한 개별적인 텍스쳐를 이용하게 되면 영상의 검색에 있어서 다양한 목적으로 38

40 활용할 수 있다. 대표적으로 균등 텍스쳐 서술자를 이용할 경우 질의의 형태 역시 다양하게 사용할 수 있다. 영상내의 개별적인 텍스쳐의 특징을 질의로 결합하여 사용함으로써 다양한 응용이 가능하다. 균등 텍스쳐는 이러한 기능을 위하여 일반적으로 영상을 총 30개의 Gabor 필터를 이용하여 필터링을 수행하고 주파수 영역에서의 1차 2차 모멘트를 구하여 최종적으로 62개의 숫자로서 영상을 표현한다. 그림 2.8은 균등 서술자를 추출하기 위하여 주파수 영역을 30개 영역으로 구획한 것이다[41]. 총 30가지의 필터는 각각 5가지의 크기, 6가지의 방향성분에 따라서 각각 필터링된다. 대부분의 계산량은 이러한 필터링에 의해 좌우된다. 그림 2.8 균등 텍스쳐 서술자의 특징 추출을 위한 주파수 영역 도시 Figure 2.8 Frequency layout for homogeneous texture feature extraction 39

41 텍스쳐 열람 텍스쳐 열람 서술자는 기본적으로 영상내의 텍스쳐의 인지적인 특징을 표현하는데 목표를 두고 있다. 인간이 영상이나 사물을 보고 느끼는 해당 형상에 대한 인지적인 특징은 규칙성과 방향성 그리고 텍스쳐의 세밀함을 이용하여 표현 가능하다. 텍스쳐 열람 서술자에서 규칙성은 그 정도에 따라 총 4단계로 구분되며 그림 2.9는 규칙성의 예를 보여주고 있다. 이 서술자는 최대 12bits의 매우 작은 크기를 가지며 서술자의 추출은 기존의 균등 텍스쳐와 유사하다. 먼저 크기와 방향 성분에 대하여 Gabor 필터링을 취한 다음 방향성을 표현하기 위해 주 방향을 구하고 차례로 규칙성과 세밀함을 주 방향에 대하여 투영을 이용하여 계산한다. (a)) (b) (c) (d) 그림 2.9 규칙성의 예 (a)매우 규칙적, (b)규칙적, (c)약간 규칙적, (d)불 규칙적 Figure 2.9 Example of regularity. (a)highly regular, (b)regular, (c)slightly regular, (d)irregular 경계선 히스토그램 경계선 히스토그램 서술자는 영상내의 경계선의 형태를 방향 성분에 따라서 다섯 가지로 구분하며 각 방향 성분이 영상 전체에서 차지하는 비율을 40

42 히스토그램으로 표현한 서술자이다. 다섯 가지의 방향 성분은 각각 수평, 수직 방향과 두 개의 대각선 그리고 마지막으로 무방향성을 포함하고 있다 (그림 2.10). (a) 수직 (b) 수평 (c) 45 방향 (d) 135 방향 (e) 무방향 그림 2.10 영상에서의 다섯가지 경계선 유형 Figure 2.10 Five types of edge in image 경계선 히스토그램의 추출을 위해서 영상은 4 4의 총 16개의 블록으로 나뉘어 지고 각 블록 별로 5가지 방향 성분에 대하여 히스토그램을 구하게 된다 (그림 2.11). sub-image (0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) image-block (2,0) (2,1) (2,2) (2,3) (3,0) (3,1) (3,2) (3,3) 그림 2.11 세부 이미지와 영상 블록의 정의 Figure 2.11 Definition of sub-image and image-block 41

43 영상의 인지에 있어서 경계선은 매우 중요한 역할을 수행하기 때문에 이러한 경계선의 적절한 분포를 효율적으로 표현함으로써 균등한 텍스쳐만이 아닌 다양한 형태를 지닌 일반적인 영상의 검색과 분류에 매우 훌륭한 성능을 보인다. 더불어 경계선 히스토그램은 색상 서술자와 같은 다른 서술자와 결합하여 사용할 경우 좀 더 나은 성능을 얻을 수 있다 형태학적 서술자 영상 내에서 인간이 인지하는 형태나 모양은 어떠한 객체나 영역을 이루는 픽셀들의 공간적인 배치와 매우 밀접한 관계를 맺고 있다. 형태학적 서술자는 이러한 픽셀의 공간적인 배치에 초점을 맞추어 영상을 표현하는 서술자이며 MPEG-7의 형태학적 서술자는 크게 2차원과 3차원으로 나뉘어 지며 모두 3가지의 서술자를 아래와 같이 정의하고 있다. 영역기반 형태(region shape) 외곽선 기반 형태(contour shape) 3차원 형태(shape 3D) 영역 기반 형태 그림 2.12에서와 같이 일반적으로 객체의 형태는 하나의 영역으로 이루어져 42

44 있거나 각각의 영역의 집합으로 이루어져 있다. 영역 기반 형태 서술자는 이러한 영역의 모든 픽셀값을 이용하여 서술자를 만들어 낸다. 그림 2.12 다양한 형태의 예 Figure 2.12 Examples of various shapes 영역 기반 형태 서술자는 극좌표에 기반을 둔 ART(Angular Radial Transform) 변환을 이용하여 형태를 기술하며 그림 2.13은 영상의 중심이 원점일 때 ART변환의 2차원 기저함수를 나타낸 것이다. 그림 2.13 ART 기저 함수의 실수부 Figure 2.13 Real parts of the ART basis function 외곽선 기반 형태 외곽선 기반 형태 서술자는 영상 내의 객체 또는 영역의 형태를 해당 43

45 영역을 둘러싸고 있는 외곽선을 기반으로 표현하는 서술자이다. 이 서술자는 곡률 크기 공간(curvature scale space) 변환을 이용하여 외곽선 형태의 인지적 특징을 표현한다. 그림 차원 객체와 대응되는 외곽선 형태 Figure D visual object and its corresponding contour shape 곡률 크기 공간 변환을 이용하여 외곽선을 표현하기 위하여 외곽선의 요면(concave, 凹 面 )과 철면(convex, 凸 面 )을 구분하여 표현해야 한다. 이를 위해서 그림 2.14와 같이 외곽선의 단계별로 전개시켜 주요한 요면 또는 철면을 서술함으로써 실제 외곽선의 특징을 매우 작은 데이터 크기로도 표현 할 수 있다 차원 형태 3차원 형태 서술자는 3D 메쉬(mesh) 모델에 대한 형태학적 서술자를 44

46 정의하고 있으며 일반적인 3D 표면(surface)의 특징을 주로 이용하고 있다 움직임 서술자 움직임(motion)은 카메라를 이용한 정지 영상 또는 동영상에서 매우 주요한 특징값이 된다. 이러한 움직임을 정지 영상 또는 동영상에 대한 서술자로 활용하기 위하여 MPEG-7은 4가지의 움직임 관련 서술자를 아래와 같이 정의하고 있다. 카메라 움직임(camera motion) 움직임 궤적(motion trajectory) 파라메트릭 움직임(parametric motion) 움직임 활성도(motion activity) 카메라 움직임 카메라의 움직임은 크게 3차원 공간에서 각 축에 따라서 회전(roll), 틸트(tilt) 그리고 팬(pan)의 3가지로 분류된다 (그림 2.15). 이밖에 카메라 자체가 각 축에 따라서 움직이는 것을 각각 붐(boom), 돌리(dolly) 그리고 트랙(track)이라고 한다. 이러한 카메라의 움직임을 표현하기 위해 MPEG-7에서는 카메라 움직임 서술자를 정의하고 있다. 45

47 그림 2.15 다양한 카메라 움직임의 예 Figure 2.15 Examples of various camera motions 움직임 궤적 움직임 궤적 서술자는 움직이는 객체의 궤적을 표현하기 위해 정의된 서술자로서 해당 객체의 대표 점의 시공간적 위치를 표현함으로써 비디오 데이터의 검색과 분류에 매우 좋은 성능을 보인다. 특히나 사전 지식을 가지고 멀티미디어 데이터의 검색이나 분류를 하고자 하는 특정 응용 분야에서 매우 유용한데 대표적으로 자동차 도로 감시분야나 스포츠 방송 분야에서는 해당 분야의 특징적인 부분을 서술자 또는 질의에 적용할 수 있다. 예를 들면 도로 감시 카메라의 경우 화면상의 특정 영역을 정해진 속도 이상으로 지나가는 경우만을 검색해내는 등의 응용이 가능하다. 움직임 궤적은 프레임별로 키 포인트를 정하고 사이의 움직임 값은 정해진 내삽법(interpolation)에 의하여 추정된다 파라메트릭 움직임 파라메트릭 움직임 서술자는 기본적으로 객체의 움직임을 정해진 몇 가지의 46

48 움직임 변환 모델을 이용하여 근사적으로 모델링이 가능하다는 가정을 두고 있으며 이 모델을 파라미터만을 계산해 서술함으로써 매우 작은 크기의 서술자로서도 움직임을 효과적으로 표현할 수 있다. 이 서술자로 표현이 가능한 움직임 변환 모델은 회전(rotation), 크기변환(scaling), 이동(translation)등이 있으며 더불어 수평 원근 모델과 투영 모델 그리고 4차원 모델등이 포함된다. 다양한 움직임 모델을 정의하고 이 모델을 개별적인 객체에 적용함으로써 다수의 움직임을 효율적으로 표현할 수 있으며 이러한 특징덕분에 다양한 질의형식이 가능해 진다. 단순한 질의 형식뿐만이 아니라 특정 움직임 만을 요구하는 등의 고급질의가 가능하여 다양한 응용 분야에서 활용이 가능하다 움직임 활성도 인간이 인지하는 영상내의 움직임은 종종 빠르다 또는 느리다 는 식으로 인지가 가능하다. 이외에도 움직임이 단순하다 또는 반대로 움직임이 복잡하다 라고 인지할 수도 있다. 움직임 활성도 서술자는 이러한 영상내의 움직임의 활동량을 표현하기 위해 정의되었다. 이 서술자는 영상내의 움직임의 정도를 크기, 방향, 공간적 분포, 공간적인 집중도 그리고 시간적 분포의 5가지로 구분하여 기술하고 있다. 47

49 2.4. 멀티미디어 핑거프린팅 기존의 멀티미디어 검색 기술과는 그 태생을 달리하는 멀티미디어 핑거프린팅 기술은 콘텐츠의 저작권 보호 관점에서 기술 개발이 시작되었다. 기존의 콘텐츠 보호 기술은 크게 두 가지 측면으로 나뉠 수 있다. 첫 번째는 암호화(encryption)방법으로 이는 유통하고자 하는 콘텐츠를 특정 키를 이용하여 암호화 한 다음 암호화된 데이터를 유통시킨 후 사용자는 암호화를 풀기 위한 키를 공급받아 원하는 콘텐츠를 사용하도록 하는 것이다. 이 기술은 암호화 키를 모르면 콘텐츠 자체를 사용할 수 없기 때문에 매우 효과적이고 실제로 오랫동안 많은 분야에서 사용되어 왔으며 현재에도 대부분의 디지털 콘텐츠의 유통에서 큰 역할을 담당하고 있다. 실제로 현재 대부분의 음원 데이터를 포함한 멀티미디어 콘텐츠의 유통은 DRM이라 불리는 시스템하에서 진행되고 있으며 이 DRM시스템의 근간은 암호화 과정이 차지하고 있다. 그러나 암호화 알고리즘을 통하여 콘텐츠를 부호화 하고 복호화 하기 위해 사용자로 하여금 암호 입력과 같은 부가적인 작업을 요구하며 이러한 사항은 좀 더 편리하고 간편하게 콘텐츠를 이용하고자 하는 사용자의 욕구에 반하는 것이다. 더불어 다양한 멀티미디어 기기를 사용하는 사용자 입장에서는 한번 복호화한 것을 다시 자신의 다른 멀티미디어 기기로 이동하기 위해서는 다시금 암호화를 진행하거나 아예 이를 허락하지 않는 등의 많은 제약이 따르기 때문에 사용을 꺼리게 된다. 이러한 이유 때문에 최근에는 실제로 암호화를 하지 않고 콘텐츠를 배포해야 한다는 Free DRM 콘텐츠의 유통을 주장하는 사례도 종종 48

50 볼 수 있으며 실제로 미국 Apple사의 음원 유통 시스템인 itunes에서도 이와 같은 암호화 하지 않은 음원을 판매하고 있다[42]. 더불어 암호화의 가장 큰 단점은 일단 암호화된 콘텐츠가 복호화되고 나면 저작권 보호를 위한 어떠한 수단도 존재하지 않는다는 것이다. 이와 같이 복호화된 후 불법으로 유통되고 사용되는 콘텐츠에 대해서는 보호 할 방법이 모호해 지는 셈이다. 이러한 암호화의 단점을 해결하고자 제시된 방법이 디지털 워터마킹 기법이다. 디지털 워터마킹은 콘텐츠에 사용자가 인지하지 못하도록 저작권 정보를 삽입하는 일종의 데이터 은닉기술로서 사용자 입장에서는 기존의 콘텐츠에 아무런 제약이 없기 때문에 별다른 추가작업이나 불편 없이 마음대로 콘텐츠를 이용할 수 있다는 장점이 있다. 또한 멀티미디어 데이터의 포맷 역시 변동이 없기 때문에 자신의 멀티미디어 기기를 교체하거나 추가적인 작업을 요구하지 않는다. 디지털 워터마킹 기술로 저작권을 보호하는 방법에서는 콘텐츠의 생성자가 콘텐츠내에 자신의 고유한 저작권 정보인 워터마크를 삽입한다. 이렇게 워터마크가 삽입된 영상은 유통경로를 통하여 배포된다. 불법 사용자는 이 콘텐츠를 그대로 복제해서 사용하거나 변형을 취하여 사용하게 되는데 이후 두 불법 사용되는 콘텐츠에 대해서 저작권에 대한 분쟁이 일어났을 경우 콘텐츠로부터 워터마킹 기술을 이용하여 저작권 정보를 추출하여 분쟁을 해결할 수 있다. 또한 워터마킹 기술은 해당 콘텐츠내에 저작권 정보가 삽입되어 있기 때문에 원본 콘텐츠를 복제하여도 동일한 저작권 정보를 추출할 수 있다. 그러나 디지털 워터마킹 기술은 콘텐츠가 원본에 대하여 변형이 49

51 가해질 경우 본래의 삽입된 저작권 정보를 추출하기가 쉽지 않다는 치명적인 단점을 가지고 있다. 워터마킹 기술은 정보 자체를 원본 콘텐츠 내에 삽입하기 때문에 콘텐츠가 손상될 경우 워터마킹된 정보도 역시 같이 손상이 된다. 따라서 손상 정도가 심해질수록 본래의 정확한 정보를 추출하는 것이 어려워져 실제로 저작권 분쟁이 발생했을 경우 본래의 저작자가 누군지 밝혀내는 것이 매우 어렵다. 이러한 암호화 방법과 워터마킹 방법을 보완하기 위해서 개발된 것이 디지털 핑거프린팅(fingerprinting) 기술이다. 핑거프린팅이라는 단어에서 알 수 있듯이 디지털 핑거프린팅은 사람이 각자 고유한 지문을 가지고 있는 것처럼 디지털 콘텐츠가 가지는 유일성을 일정한 크기내의 디지털 정보로서 표현 가능하도록 하는 기술이다. 핑거프린팅을 이용한 저작권 보호 기술은 특정 콘텐츠에 대하여 저작권 정보와 해당 콘텐츠로부터 추출한 핑거프린트 정보를 이용하여 후에 다른 콘텐츠 또는 해당 콘텐츠가 변형되어 불법적으로 사용되고 있을 경우미리 추출해놓은 핑거프린트와 대조를 통해서 원저작자의 권리를 주장할 수 있도록 하는 기술이다. 그림 2.16은 디지털 핑거프린팅 기술을 이용한 불법 콘텐츠 추적 시스템의 예이다. 먼저 콘텐츠의 생성 또는 배포 전에 각 콘텐츠에 대한 고유한 핑거프린트를 추출한다. 추출된 핑거프린트는 데이터베이스에 계속적으로 저장되고 핑거프린트가 추출된 콘텐츠는 유통 시스템을 통해 정상적으로 배포된다. 이 때 특정 불법 사용자가 이 콘텐츠를 불법으로 유통시킬 수 있다. 저작자의 동의없이 불법으로 인터넷상으로 50

52 유통되고 있는 콘텐츠를 콘텐츠 검색 로봇이인터넷 상에서 찾아서 핑거프린트를 추출한 다음 핑거프린트 데이터베이스에 있는 핑거프린트들과 대조 작업을 거친다. 대조 결과 데이터베이스 내의 보호받는 콘텐츠 중 하나의 핑거프린트와 일치하면 해당 콘텐츠는 불법으로 유통되고 있다는 것을 알 수 있다. 그림 2.16 불법 콘텐츠 추적 시스템의 예 Figure 2.16 Example of illegal contents tracking system 디지털 핑거프린트는 기존의 해시(hash) 함수의 기능과 매우 유사하다고 할 수 있다[43]. 해시 함수란 주어진 콘텐츠로부터 일정 길이의 의사난수(pseudo random number)를 생성해 내는 기술을 말하며 이렇게 생성된 수열을 해시값이라 하며 서로 다른 콘텐츠일 경우에는 해시값 역시 서로 다른 값을 가져야만 한다. 따라서 개별적인 콘텐츠에 대하여 고유의 값을 만들어 낼 수 51

53 있다. 그림 2.17 해시 함수의 예 Figure 2.17 Example of hash function 그림 2.17에서 해시 함수는 입력으로 들어온 단어나 문장으로부터 일정한 길이의 수열을 생성해 낸다. 기본적인 해시 함수는 입력되는 콘텐츠가 정확히 일치하지 않고 조금이라도 틀리면 전혀 다른 수열을 만들어 낸다. 그러나 디지털 멀티미디어 콘텐츠는 쉽게 변형되고 조작이 가능하기 때문에 기존의 해시 함수를 이용할 경우 서로 같은 콘텐츠라 할지라도 전혀 다른 해시값을 생성해 낼 확률이 매우 높다. 서로 다른 콘텐츠의 구별 또는 각 콘텐츠의 고유한 해시값을 이용한 콘텐츠의 분별에는 유용하지만 자기자신의 변형된 형태 역시 다른 콘텐츠로 인식해버리는 현상이 생기게 된다. 따라서 기존의 해시 함수를 이용하여 멀티미디어 콘텐츠의 저작권을 보호하기에는 무리가 따르며 이를 보완하는 디지털 핑거프린트 기술은 기존의 해시 함수의 기능과 함께 다음과 같은 조건을 만족해야만 한다. 52

54 단방향성(one way function) 독립성(independecy) 강인성(robustness) 단방향성이란 주어진 콘텐츠로부터 핑거프린트를 추출하는 것은 가능하지만 반대로 핑거프린트로부터 콘텐츠 자체를 예측해내는 것은 불가능해야 함을 의미하고 독립성은 서로 다른 콘텐츠는 서로 다른 핑거프린트를 가져야 하고 반대로 서로 유사한 핑거프린트를 갖는 경우 콘텐츠가 서로 다를 가능성이 적어야 함을 의미한다. 이 두 가지 조건은 해시 함수와 핑거프린팅 기술 모두 갖추어야 하는 요건으로서 서로 다른 콘텐츠를 구별하는 기능에 초점을 맞추고 있다 [44]. 해시 함수와는 다르게 핑거프린팅 기술에 필요한 추가적인 조건은 강인성으로서 콘텐츠가 변형을 일으키거나 손상을 당하더라도 원본과 동일한 핑거프린트를 생성해 내야 한다는 것을 의미한다. 콘텐츠가 내포하는 내용이 동일하다면 설사 외부 형태가 손상되거나 변형되었더라도 동일한 핑거프린트 값을 가져야만 핑거프린트만으로도 두 콘텐츠가 내용상 동일한 콘텐츠라는 것을 증명할 수 있다 [45]. 이와 관련된 대표적인 알고리즘으로서 라돈(radon) 변환을 이용한 알고리즘이 제안되었는데 이 방법은 회전 변형에 불변한 라돈 변환을 영상에 대하여 취한 다음 자기상관성(auto-correlation)과 푸리에(Fourier) 변환을 이용하여 크기 변환에 강인한 서술자를 추출하였다[21]. 정지 영상 53

55 핑거프린팅의 대표적인 알고리즘인 이 방법은 우선 회전과 같은 기하학적 변환에 강인한 핑거프린트를 추출하기 위해서 라돈 변환을 이용하였다. 라돈 변환은 중심으로부터 각 각도와 반지름에 따른 투영의 집합이며 식 (2.1)과 같이 표현할 수 있다. - - (2.1) g(, s θ) = f (, x y)( δ x cosθ + y sin θ sdxdy ), where < s <, 0 θ < π. 중심으로부터 거리 s와 각도 θ에 해당하는 투영값은 식 (2.1)과 같이 계산된다. 기하학적 변환에 강인한 핑거프린트 추출을 위하여 라돈 변환후 자기 상관(auto-correlation)값을 계산한다. 라돈 변환후 회전변형은 θ방향으로의 이동이며 로그 사상(log mapping)과 이차원 FFT(Fast Fourier Transform)을 통하여 회전, 크기변환 등에 강인한 값을 추출할 수 있다. 이 방법은 라돈 변환을 사용함으로써 기하학적 변환에 강인할 뿐만 아니라 일반 압축과 영상 왜곡과 같은 변형에도 강인함을 보인다. 멀티미디어 콘텐츠의 인식이라는 측면에서 검색과 해시 함수 핑거프린팅은 서로 밀접한 관계를 맺고 있다. 각각의 방식 모두 기본적으로는 미디어로부터 특징을 추출하여 그것을 중심으로 질의와 유사한 대상을 데이터베이스로부터 추출한다. 그러나 본 논문에서 주안점을 두고 있는 멀티미디어 식별 기능과 비교해 보자면 검색에서 사용되는 미디어의 특징과 기술방법들은 대부분 목표 자체도 다를 뿐 아니라 방법 역시 적절치 않은 경우가 많다. MEPG-7의 54

56 멀티미디어 검색 기술은 질의 미디어와 유사한 특징을 갖는 대상을 찾는 것을 목적으로 하기 때문에 질의로 사용된 미디어와 설령 다른 미디어를 찾더라도 크게 문제가 없다. 그러나 위에서 언급한 바와 같이 멀티미디어 핑거프린팅에 있어서는 서로 다른 미디어는 유사한 결과를 보여서는 안 된다. 이 점이 멀티미디어 검색과 지각적(perceptual) 해시 함수로 대표되는 멀티미디어 핑거프린팅 기술의 가장 큰 차이점이다. 디지털 핑거프린팅의 개념을 기존의 해시 함수와 접목시켜 영상을 식별하고 검색하는 연구가 많이 진행되어 왔다. Kalker는 기존의 워터마킹 기술과 함께 지각적 해시 함수기술을 언급하면서 기존의 기술과 인식(recognition)을 병합하여 사용해야 함을 주장했으며[46], Mihcak는 영상 내에서 작은 변형 에 대해 불변한 기하학적 특성에 기반하여 반복적으로 웨이블렛 필터를 통해 영상마다 고유한 불규칙성의 출력을 만드는 알고리즘을 제안하였다[47]. Monga는 특징점을 이용한 방법을 제안하였는데 이것을 위해 먼저 시각적으로 중요하지 않은 영역으로부터 최대한 불변한 특징점을 추출할 수 있는 알고리즘을 제안하였으며 추출된 특징을 양자화 하여 지각적 강인성을 높인 알고리즘을 제안하였다. 이와 함께 Swanminathan은 기하학적 변환에 강인한 푸리에 멜린 변환[48, 49]에 사용자 키를 적용하여 불규칙한 값을 추출하도록 하는 해시 방법을 제안하였다[50]. 멀티미디어 핑거프린팅과 시작은 다르지만 유사한 개념의 기술이 복사본 검출(replica detection)이다. 복사본 검출은 엄밀히 얘기하자면 원본과 똑같이 55

57 복제된 원본은 빠른 시간 내에 찾아내는 기술을 일컫는다. 그러나 최근에는 복제라는 의미를 원본을 복제하여 변형을 가한 영상도 복사본이라 가정하여 확장하여 사용되고 있다. Maret는 색상, 텍스쳐, 색상의 공간적인 분포와 같은 다수의 특징을 추출하여 유사한 특징을 병합한 후 영상간의 유사도를 병합된 그룹끼리의 유사도의 합으로서 복사본을 구별하는 알고리즘을 제안하였다[51]. Yan은 기하학적 변환에 강인한 특징점 정보와 검색의 효율성을 높이기 위해서 Locality-Sensitive Hash(LSH)방법을 이용하여 기하학적 변형이 생긴 복사본도 검출 할 수 있는 알고리즘을 제안하였다[13]. 이 방법에서 특징점 추출은 PCA-SIFT(Principle Component Analysis-Scale Invariant Feature Transform)를 사용하여 기존의 SIFT방법보다 성능을 높였다[40, 52]. 또한 일반적인 변형과는 다르게 원본 영상에 강제로 글씨가 중첩되는 변형에 대하여 강인함을 보이는 알고리즘도 제안되었다[53]. Wang은 영상으로부터 추출된 특징을 PCA를 이용하여 주성분의 일부만을 사용하여 변형에 강인하고 해시 함수를 이용하여 정합 속도를 빠르게 한 알고리즘을 제안하였다[19]. 이 방법은 웹 상에서의 이미지 검색을 위한 방법으로서 본 논문에서 목표로 하는 바와 같이 대용량 데이터베이스를 기준으로 삼고 있다. 따라서 기본적으로 빠른 정합 속도를 갖고 이를 위해 최종적인 서술자는 이진 수열 형태를 갖게 된다. 이진 수열 형태의 서술자를 생성하기 위해 먼저 영상을 n n개의 블록으로 나눈다. 그리고 각 블록에 대하여 블록 평균값을 구한다. k 차원의 특징값은 식(2.2)과 같이 계산된다. 56

58 f k = 1 N i, j Bk I( i, j) k=1,2,...,n B 는 k번째 블록, N 는 B안의 전체 픽셀 수이고 k k k Iij (, ) 는 (, ij) 위치에서의 픽셀값을 나타낸다. 2 (2.2) 이렇게 n n개의 블록으로부터 구해진 블록 평균은 1차원 벡터로 변환되어 사용되며 서로 다른 n 2 값을 갖는 특징 벡터를 서로 병합하여 사용한다. 높은 차원의 특징 벡터와 낮은 차원의 특징 벡터를 병합하여 사용함으로써 다중 해상도 효과를 낼 수 있다. 이렇게 추출된 1차원 벡터 중 PCA를 이용하여 차원의 크기를 줄인다. 마지막으로 PCA를 통과한 특징 벡터를 식 (2.3)와 같은 간단한 해쉬 함수를 이용하여 이진 수열로 변환한다. 1 if G i,k > mean H i,k = 0 if G i,k mean mean 는 k차원을 갖는 특징 벡터의 평균값이며 k ik, 는 차원을 갖는 특징벡터의 번째 특징값을 나타낸다. G k i k k (2.3) 서술자의 형태가 이진 수열 형태이기 때문에 정합은 간단한 XOR연산을 이용한 해밍거리를 이용하여 빠른 속도로 수행할 수 있다. 이 밖에도 복사본 검출을 위한 많은 연구가 이루어졌으나 명확한 성능 평가 기준이 없고 실제 적용할 만한 대용량의 데이터를 기준으로 실험된 연구는 소수에 불과한 현실이다. 57

59 2.5. 멀티미디어 식별 앞서 살펴본 바와 같이 멀티미디어 핑거프린팅 기술은 그 목적과 접근 방법에 있어서 기존의 멀티미디어 검색 기술 또는 인식 기술과 일정 부분 공유되는 부분이 없지 않지만 많은 부분이 다르다고 할 수 있다. 멀티미디어 핑거프린팅 기술 중에서도 이를 이용한 멀티미디어 식별 기술은 최근 다양한 응용 분야가 기대되는 분야이다. 이를 위해서 국제 표준 기구인 MPEG에서는 기존의 MPEG-7과 함께 이를 위한 표준기술 제정을 위한 작업을 활발히 진행하고 있다 응용분야 멀티미디어 식별 기술은 다음과 같은 다양한 응용 분야에서 활용이 가능하다[54]. 광고 모니터링 (media usage monitoring) 일반적으로 광고주는 자신이 의뢰한 광고가 실제로 TV나 라디오와 같은 매체에서 계약된 시각에 정해진 시간만큼 방송되고 있는지 확인할 필요가 있다. 비단 자신의 광고의 정확한 집행을 떠나서 특정 미디어의 사용량을 검사하여 비즈니스에 활용할 수도 있다. 멀티미디어 식별 기술은 실제 방송을 실시간으로 모니터링 하면서 매 순간 미디어의 서술자를 추출하여 추출된 서술자와 자신의 58

60 광고 콘텐츠의 서술자를 빠르게 비교하여 계약상의 절차대로 자신의 광고가 방영되고 있는지를 점검할 수 있다. 저작권 관리 (copyright management) 멀티미디어 소유자의 입장에서는 로열티의 징수, 브랜드관리 및 불법 사용물의 검사를 위하여 자신의 콘텐츠가 어디서 어떻게 사용되고 있는지 인지하는 것이 매우 중요하다. 개인 사진 목록 관리 (personal photo-collection management) 디지털 카메라 사용자는 종종 자신의 사진을 소프트웨어를 이용하여 편집하거나 보정하고 다른 이로부터 얻은 사진을 자신의 의도에 따라 편집하기도 한다. 이러한 작업은 본질적으로는 하나인 사진을 여러 가지 다른 형태로 만들어 내는 결과를 낳게 된다. 따라서 개인 사용자에게는 이러한 변형된 사진들과 원본 사진을 자동적으로 연결해 주는 것이 매우 유용한 응용 사례가 될 수 있다. 멀티미디어 식별 기술은 변형된 사진에 대해서도 동일한 서술자를 얻을 수 있으므로 원본과 그의 변형본을 자동적으로 검색해 낼 수 있다. 콘텐츠 연결 (content linking) 인터넷상에서 같은 미디어가 다른 곳에서 존재하는 것은 매우 유용한 59

61 정보가 될 수 있다. 검색 엔진에서 특정 영상의 검색을 원할 경우 같은 영상이 존재하는 서로 다른 링크를 가지고 있다면 가장 빠른 곳으로부터 영상을 받을 수 있도록 자동적으로 링크를 제공하는 서비스가 가능하며 이러한 서비스를 통해 검색을 효율성을 획기적으로 높일 수 있다. 멀티미디어 식별 기술을 이용하여 인터넷으로부터 자동적으로 미디어를 검색하면서 관련 서술자를 추출하여 데이터 베이스를 구성한다. 미디어에 대한 서술자가 추가될 때 이미 구성된 데이터 베이스 내에서 검색을 통하여 이미 저장된 콘텐츠가 있는지를 검사한다. 이러한 작업을 통하여 동일한 콘텐츠인 경우 해당 링크만을 기록함으로써 검색 및 저장의 효율성을 높일 수 있다. 미상의 콘텐츠 식별 (unknown content identification) 특정 미디어를 공유하거나 배포할 경우 제목이나 저작자와 같은 부가 정보가 제공되지 않은 채로 배포되는 경우가 있다. 이런 경우 멀티미디어 식별 기술을 이용하며 빠르게 미디어 만으로도 해당 미디어에 대한 관련 정보를 데이터 베이스로부터 얻을 수 있다. 부가정보를 원하는 미디어로부터 서술자를 추출하여 관련 데이터 베이스로부터 서술자를 검색한다. 데이터 베이스로부터 일치하는 서술자를 찾았으며 해당 서술자에 대해 기록되어 있는 부가정보를 쉽게 얻을 수 있다 국제 표준 기술 제정 60

62 멀티미디어 식별은 본래 정지 영상 식별자 (image identifier)라는 이름으로 정지 영상에 대한 표준 작업을 시작했으며 그림 2.18과 같이 기존의 검색과는 다른 개념의 ground truth 모델을 기반으로 하고 있다 [55], [56]. 그림 에서 데이터베이스 내에는 Source 0과 그 밖의 다른 데이터 들이 존재한다. 그리고 Source 1, Source 2,, Source n은 Source 0로부터 변형되어 생긴 파생적인 데이터 들이다. 이 때 질의로서 source #을 입력했을 경우 Source 0를 포함하여 파생된 데이터들도 모두 동일한 ground truth로 인식되어야만 한다. 그림 2.18 정지 영상 식별자를 위한 제안된 새로운 ground truth 모델 Figure 2.18 The new proposed ground truth model for image identifier 이러한 모델을 기반으로 MPEG에서는 2005년 10월 Nice에서 새로운 MPEG-7 표준으로서 VCE(Visual Core Experiment)-6를 시작했다[57]. 이를 시작으로 61

63 새로운 영상 식별자 표준 기술 및 이를 검증하기 위한 실험 조건이 구성되었고 새로운 성능 평가 방법도 제안되었다. 초기에 hit ratio로 명명되었던 강인성 평가 기준은 후에 success ratio라는 이름으로 바뀌면서 그 정의를 새롭게 하였다. 영상이 변형되었을 경우의 강인성을 테스트하기 위해서 사용되는 영상 변형의 종류도 초기에 11가지에서 현재는 17가지로 늘어났으며 각 변형에 대해서 정도에 따라서 최대 3가지 단계로 다시 나누어 총 변형은 41개로 늘어났다. 강인성 테스트와 함께 기존의 MPEG-7 서술자의 성능 비교와는 다른 독립성(independence) 테스트를 동시에 진행함으로써 제안된 기술의 분별력을 평가 할 수 있게 되었다. 현재 정지 영상 식별자의 표준화 작업은 2007년 1월 첫번째 XM(Experiment Model)문서가 채택되었고 현재까지 XM단계를 진행하고 있다[58]. 현재 정지 영상 식별자는 공식적으로 정지 영상 서명(image signature)이라는 이름으로 정정되었고 크게 기본 조건(basic condition)과 복합 조건(complex condition)으로 나뉘어져 있다[59]. 이와 함께 총 41가지의 현재 표준화 회의에서 진행중인 변형종류와 강도는 표 2.3와 같다. 성능 평가의 조건은 위에서 언급한대로 두 종류로 나뉘어지며 기본 조건의 경우 독립성 테스트에서 0.05 ppm(parts per million)기준, 복합 조건의 경우 10 ppm의 기준을 적용하여 성능 평가를 진행하고 있다. 실험에 사용되는 영상의 수는 독립성 테스트의 경우 약 13만장의 서로 다른 영상을 사용하고 강인성 테스트에서는1만장의 원본영상을 사용한다. 62

64 표 2.3 정지 영상 식별자 성능 평가를 위한 변형종류 및 강도 Table 2.3 Various modifications and levels for the performance evaluation of image identifier Levels Modifications Heavy Medium Light Brightness change +25% +20% +10% Color to monochrome conversion N/A N/A JPEG compression with varying Quality factors Color reduction I = R G B QF 30 QF 60 QF 80 GIF 8bit version 16bit: RGB(565) Gaussian Noise Histogram equalization N/A N/A YES Image enhancement via Auto-level N/A N/A YES Blur Geometric transformation mask size: 7x7 mask size: 5 5 mask size: 3 3 Simple Rotation Rotation Scaling (width-height ratio) 50% 70% 90% Translation 30% 20% 10% Flip N/A N/A left-right Aspect ratio change N/A Width x 1.5 (e.g. 4:3 6:3) Width x 1.33 (e.g. 4:3 16:9) Crop 60% 70% 90% Skew Perspective (Focal length=500) The modification level refers to the standard deviation of the Gaussian noise. It has been found that histogram equalisation causes severe distortion to some images. The histogram equalisation is therefore only performed on a subset of the images in List B. This subset is referred to as List C. The modification level refers to the proportion of the width & height remaining after the cropping 63

65 또한 정지 영상에 대한 표준화 작업을 시작한 이후에 이를 기초로 2006년 1월 Marrakech 회의에서 동영상 식별자에 대한 작업을 VCE-7이라는 이름으로 처음으로 시작하였다[60]. 대부분의 뼈대는 기존의 정지 영상 식별자의 표준화 작업을 참고 하고 있으며 동영상의 변형종류와 강도는 표 2.4와 같다. 표 2.4 동영상 식별자 성능 측정을 위한 다양한 변형과 강도 Table 2.4 Various modifications and levels for the performace evaluation of video identifier Levels Modifications Heavy Medium Light Text/logo overlay * 30% 20% 10% Severe compression (at CIF resolution) 64kbps 256kbps 512kbps Resolution reduction (from SD) N/A QCIF CIF Frame-rate reduction (from 30 fps) 4fps 5fps 15fps Capturing on camera (at SD resolution) ** 10% 5% 0% Analog VCR recording & recapturing (100% of image captured) *** 5 times 3 times 1 time Color to monochrome conversion N/A N/A I = R G B Brightness change +20% +10% +5% * - percentage of text/logo area. ** - percentage of extra background area. *** - number of times of digital->analog->capture. - 4 fps is chosen because it involves non-integral rate-conversion and is therefore significantly harder than 5 fps. 이와 같은 변형에 대하여 강인한 정지 영상 및 동영상 식별자 기술을 개발하여 국제 표준으로 채택하는 것이 현재 MPEG-7 VCE-6, VCE-7 표준화 64

66 작업에서의 주안점이라 할 수 있다. 그러나 위와 같은 강인성에 앞서 현재 정지 영상 및 동영상 식별자 기술 개발에 있어서 선결조건은 낮은 정합 복잡도 (complexity)이다. 즉 멀티미디어 식별자 기술은 매우 방대한 데이터베이스를 대상으로 하기 때문에 실기간으로 정합이 이루어져야만 한다. 따라서 최종적으로 미디어에서 추출되는 서술자의 크기와 정합 속도가 우선시 되고 있다. 이러한 요구조건을 정리하여 최근 MPEG 표준화 회의에서는 이러한 정지 영상 및 동영상 식별자 기술에 대하여 CfP(Call for Proposals)를 채택하여 기술적 관심도를 높이려고 노력하고 있다[54]. 65

67 제 3 장 정지 영상 식별을 위한 서술자 3.1. 원형 구획 기반 서술자의 모델링 정지 영상은 밝기(luminance) 성분과 컬러(chrominance) 성분으로 나뉘어진다. 인간의 눈은 이러한 밝기 성분과 컬러 성분을 기반으로 물체를 인식하게 된다. 실제 인간의 눈에는 밝기 성분을 인지하는 rods 와 컬러 성분을 인지하는 cones가 분포하고 있으며 상대적으로 rods의 수가 cones의 수보다 월등히 많다. 따라서 인간의 눈은 밝기의 미세한 변화에는 민감한 반면 컬러의 변화에는 둔감하다 [61-63]. 이는 결국 밝기 성분이 지니는 정보가 컬러 성분이 지니는 정보보다 훨씬 더 인간의 눈에는 영향력이 크다는 것을 의미한다. 따라서 영상이 지니는 정보는 컬러 성분 보다는 밝기 성분에 좀 더 집중되어 있다고 판단 할 수 있다. 이와 같은 이유로 영상으로부터 컬러 성분을 배제하고 밝기 성분만을 가지고 표현하는 것이 일반적인 영상처리의 기본 과정이며 이는 식 (3.1)와 같이 표현 할 수 있다. I[ L] = air [ ] + big [ ] + cib [ ] (3.1) 식 에서 I[R], I[G], I[B]는 각각 영상의 Red, Green, Blue성분을 나타낸다. 특정 색상 공간 변환에 따라 색상 성분으로부터 밝기 성분이 계산된다. 색상 공간 66

68 변환의 계수인 a, b, c는 각 색상 공간 변환의 종류에 따라 결정된다. 이와 같이 영상의 대표적인 정보를 표현하는 밝기 성분을 기반으로 영상의 변형을 나누어 보면 크게 기하학적 (geometrical) 변형과 비기하학적 (non-geometrical) 변형으로 나뉘어 진다. 표 3.1는 기하학적 변형과 비기하학적 변형의 예를 정리한 것이다. 표 3.1 기하학적 변형과 비기하학적 변형의 예 Table 3.1 Examples of geometrical and non-geometrical modifications 기하학적 변형 비기하학적 변형 Brightness change, Contrast change, Rotation, Scaling, Flip Blurring, Sharpen, Noise, Image enhancement, Compression 두 변형 사이의 차이점은 기하학적 변형의 경우 픽셀값의 변화는 없고 단지 픽셀의 위치가 변한다. 반면 비기하학적인 변형의 경우 픽셀의 위치는 바뀌지 않지만 각각의 픽셀값에 변화가 생긴다. 또한 기하학적 변형 영상의 경우 일부 영상이 제거되거나 새로운 영상이 생성되기도 한다. 일반적인 영상의 변형은 식 (3.2)과 같이 표현 할 수 있다. I ( x, y) = α I( x, y) + β (3.2) 식 (3.2)에서 I ( xy, ) 는 영상 내에서 ( x, y) 위치의 변형된 픽셀값을 나타낸다. 그리고 ( x, y) 와 ( x, y) 의 관계는 식 (3.3)와 같이 일반화 할 수 있다. 67

69 x a b e x y c d f y = (3.3) 식 (3.3)의 일반화된 변환행렬은 기하학적 변형과 비기하학적 변형에 따라서 세부적으로 값이 결정된다. 식 (3.4)는 기하학적 변형을 위한 변환식이고 기본적으로 회전을 고려한 경우이다. 이 때 (a, b)는 회전축의 중심점의 위치를 나타내고 일반적으로 영상의 중심을 회전축으로 사용할 경우 각각 너비와 높이의 절반에 해당하는 값을 갖는다. 기하학적 변형에서는 픽셀값 자체의 변화는 없기 때문에 α, β는 각각 1과 0의 값을 갖는다. 반면 식 (3.5)는 픽셀의 위치는 변화가 없기 때문에 변환 행렬은 단위 행렬(Identity matrix)가 되며 오직 α, β 값에 따라 픽셀값의 변화만이 생긴다. x cosθ sinθ acosθ bsinθ a x y sinθ cosθ asinθ bcosθ b y = α = 1, β = 0 (3.4) x x y y = (3.5) 위와 같은 영상의 변형에 강인한 서술자를 모델링 하기 위하여 기하학적 변형과 비기하학적 변형에 대하여 분리하여 고려하여야 한다. 대표적인 68

70 비기하학적인 변형은 다음 식 (3.6)과 같이 나타낼 수 있다. Brightness : I ( x, y) = I( x, y) + β Contrast : I ( x, y) = α I( x, y) M 2 M 2 Blurring : I ( x, y) = α I( x + i, y + j) i= M 2 j= M 2 i, j (3.6) 이외에도 다양한 비기하학적인 변형이 있지만 대부분의 비기하학적 변형은 선형적 특성을 따르고 있다. 비록 선형적 특성을 지니고 있지 않더라도 대비(contrast)에서 보듯이 상대적으로 큰 값을 가진 픽셀은 상대적으로 작은 값을 가진 픽셀보다 항상 큰 값을 유지한다. 이것은 실제로 영상내의 상대적인 픽셀값의 차이가 실제로 영상의 정보가 되고 상대적인 픽셀값의 대소 관계가 바뀌게 되면 전혀 다른 정보를 띄게 된다. 따라서 비기하학적 변형에서 두 위치의 픽셀값의 관계는 다음 식 (3.7)과 같이 나타낼 수 있다. if I( x, y ) > I( x, y ), then I ( x, y ) > I ( x, y ) (3.7) a a b b a a b b 식 (3.7)은 서로 다른 위치인 (x a, y a )와 (x b, y b ) 사이의 픽셀 사이의 대소관계는 변형이 일어나도 바뀌지 않는다는 것을 의미한다. 일부 영상에 잡음(noise)이 첨가될 경우 각 픽셀마다 서로 다른 변화가 일어나므로 식 (3.7)이 성립하지 않을 가능성이 크다. 이러한 경우를 위하여 W H의 영상을 N M의 세부 블록으로 나누어 각 블록의 평균값을 이용한다 (그림 3.1). 69

71 (a) (b) 그림 3.1 블록 기반 구획 (a) 원본 영상, (b) 블록 평균값으로 이루어진 단순화된 영상 Figure 3.1 Block-based partition. (a) original image, (b) rough image made by block mean 식 (3.7)을 블록 단위의 거시적인 측면으로 확장하면 식 (3.8)과 같다. if B( X, Y ) > B( X, Y ), then B ( X, Y ) > B ( X, Y ). a a b b a a b b w h 1 여기서 B( nm, ) = I( nw+ imh, + j) andw= W N, h= H M. w h i = 1 j = 1 (3.8) 세부 블록의 평균값을 이용함으로써 잡음과 같이 개별 픽셀값의 무작위적인 변화에 대해서도 동일하게 적용이 가능하다. 이와 같이 영상이 자신의 주된 정보를 지닌 채로 변형이 될 경우 픽셀값 또는 픽셀 블록값은 선형적으로 변형되므로 영상내의 서로 다른 위치에서의 대소관계 역시 변형 전과 변형 후에 동일하게 유지된다. 영상의 이러한 고유한 특징을 이용하면 밝기 변화, 대조 변화 및 잡음 등에도 불변한 서술자의 개발이 가능하다. 그리고 다른 변형들 중에서 압축과 블러링등은 실제로 픽셀단위의 값은 변하여 변형 정도가 70

72 심해질수록 형태의 변화가 일어나지만 블록 단위의 평균값은 크게 바뀌지 않으므로 평균 픽셀 블록값의 대소관계는 바뀌지 않는다. 따라서 영상의 변형에 불변한 서술자를 위해서 서로 다른 위치의 영역을 관계를 설정하는 것이 필요하다. 일반적으로 비기하학적인 변형에서는 그림 3.1(b)와 같이 정방형의 블록으로 나누어 다른 위치에 있는 블록간의 평균 픽셀값의 비교를 통해서 서술자의 형성이 가능하다. 영상에 변형이 일어나더라도 블록의 위치는 바뀌지 않기 때문에 비교하는 블록의 위치만 알고 있다면 다수의 블록들 중에서 서로 다른 위치의 블록을 비교하는 것은 매우 다양한 경우의 수를 산출해 낼 수 있다. 따라서 영상에 따라서 매우 다양한 패턴을 만들어 낼 수 있고 많은 영상의 독립적인 구분이 가능해 진다. 이러한 영상내의 서로 다른 위치의 블록 픽셀값의 상대적인 대소관계는 기하학적 변형에서도 마찬가지로 적용된다. 오히려 기하학적 변형에서는 픽셀값 자체의 변화가 없기 때문에 지정된 서로 다른 위치의 블록 픽셀값은 영상이 변형되어도 동일한 대소 관계를 유지한다. 다만 기하학적인 변형의 경우 픽셀의 위치가 바뀌므로 비교 대상이 되는 블록의 위치 역시 바뀌어 동일한 블록을 기억해야만 기하학적 변형에도 불변한 관계를 서술할 수 있다. 식 (3.9)은 이와 같은 기하학적 변형에서의 서로 다른 위치의 블록 픽셀값의 관계를 보여주고 있다. 71

73 if B( X, Y ) > B( X, Y ), then B ( X, Y ) > B ( X, Y ). a a b b a a b b X X 여기서 = G, G. Y Y 는 기하학적 변환 행렬이다 (3.9) 식 (3.4)와 같이 대표적인 기하학적 변형인 회전의 경우를 고려하면 그림 3.1(b)의 사각형의 블록 구획으로부터 식 (3.9)과 같은 블록 평균값 사이의 일정한 대소관계의 유지가 불가능하다. 사각형의 블록은 회전 변형 시 원래의 사각형 형태가 아닌 다른 형태를 갖기 때문에 원래의 블록 형태와 정확한 정합을 이루어 내는 것이 불가능하다. 회전 변형의 정도를 미리 알고 있으면 정확한 정합이 가능하지만 영상의 변형될 때 그 정도를 정확히 예측하는 것은 매우 어려운 일이며 추가적인 계산이 필요하다. 이러한 문제는 그림 3.2(b)와 같은 원형 구획을 통하여 회전 변형에 대하여 식 (3.9)의 성립이 가능하다. (a) (b) 그림 3.2 블록 구획의 예 (a) 사각형 블록 구획, (b) 원형 블록 구획 Figure 3.2 Examples of block partition. (a) square block partition, (b) circular block partition 고리 형태의 블록은 회전하더라도 동일한 블록 평균 픽셀값을 유지하므로 서로 다른 블록 (또는 고리) 사이의 대소 관계는 회전 변형에 관계없이 72

74 유지된다. 기타 고려되는 크기 변환, 대칭등과 같은 기하학적 변형에 대해서도 원형 구획을 통한 블록 간의 대소 관계의 서술은 불변한다. 본 논문에서 제안하는 정지 영상 식별을 위한 서술자는 위와 같은 영상의 원형의 구획된 상태에서 다양한 변형에 대하여 불변인 블록 간의 대소관계를 기본으로 하고 있다. 아울러 블록 간의 절대적인 차분값을 그대로 서술자로 사용하지 않고 상대적인 대소 관계만을 이진법적으로 사용한다. 이러한 방법은 다수의 비트를 필요로 하는 스칼라 값을 단 하나의 비트로 표현하기 때문에 서술자의 크기를 작게 만드는 효과와 함께 다양한 변형에 대하여 둔감한 서술자의 표현이 가능하도록 한다 동심원 구획 기반 서술자 본 논문에서는 정지 영상을 위한 식별자와 이를 확장한 형태의 동영상을 위한 식별자를 제안하고 있다. 제안된 알고리즘은 입력된 영상을 동심원(concentric circle)으로 영역을 구획하고 각 영역들의 상대적 및 공간적인 관계를 서술하는 독립적인 서술자를 만들어낸다. 일반적으로 동심원이란 같은 중심점을 가지면서 서로 다른 반지름을 갖는 원들의 집합을 말한다. 입력된 영상에 대하여 영상의 중심위치를 동심원의 중심점으로 가정하여 동심원을 그려서 영상을 다수의 세부 영역으로 나눈다. 이때 구획된 영역은 그림 3.3과 같이 정해진 반지름뿐만 아니라 각도 방향으로도 나뉘게 된다. 그림 3.3에서 좌측 영상은 같은 중심점과 서로 다른 반지름을 갖는 일반적인 동심원 형태를 73

75 보여주며 이로 인해 하나의 원이 다수의 고리(ring)형태의 영역으로 구획된다. 이에 비해 우측 영상에서는 일반적인 동심원 형태에서 일정한 각도별로 구획을 추가하였으며 이로 인해 하나의 고리는 다시 다수의 영역으로 구획된다. 제안된 알고리즘은 이렇게 구획된 세부 영역으로부터 모든 특징을 추출하게 된다. 그림 3.3 반지름 및 각도 방향에 대한 동심원 구획 Figure 3.3 Concentric circle partition in according to radius and angle direction 이러한 확장된 동심원 형태로 구획된 세부 영역으로부터 공간적인 관계를 고려하여 몇 가지의 특징을 추출할 수 있으며 이렇게 추출된 특징값들을 병합하여 최종 서술자를 구성한다. 본 논문에서 제안하는 정지 영상을 식별을 위한 서술자는 고속 정합을 가능하기 위해 최종 형태는 이진수열로 구성된다. 또한 회전에 불변한 서술자의 구성을 위하여 개별 특징값 계산시 구획된 영역 중고리 영역당 하나의 값을 갖도록 하며 최종적으로는 개별 특징값 계산시 하나의 고리는 한 비트를 할당한다. 따라서 전체 서술자의 크기 또는 길이는 전체 영상을 동심원 구획 시 얼마나 많은 수의 고리를 할당하느냐에 따라 74

76 달라진다. 본 논문에서 제안하는 정지 영상 식별을 위한 서술자 추출은 그림 3.4와 같은 순서를 통해 이루어 진다. 그림 3.4 동심원 구획 기반 서술자 추출 순서 Figure 3.4 Extraction sequence of the concentric circle partitioning based descriptor 본 논문에서 제안하는 서술자를 추출하기 위해서 입력되는 영상은 높이와 너비 중 짧은 쪽을 기준으로 크기를 정규화 시킨다. 그리고 영상의 중심점을 기준으로 극좌표계로 전환한다. 이렇게 전환된 픽셀들을 기준으로 정해진 반지름 단계와 각도 단계로 영상을 구획한다. 이렇게 구획된 각각의 영역에 대하여 다음의 4가지 특징 분포를 추출한다. 75

77 평균 픽셀값 분포 평균 차분값 분포 대칭적 차분값 분포 원형 차분값 분포 이렇게 추출된 특징 분포는 최종적으로 이진 수열 형태로 서술자를 생성하기 위해 제안된 해시 함수를 이용하여 변환되며 각 특징 분포별로 생성된 이진 수열을 최종적으로 하나로 병합된 서술자를 구성한다. 제안된 서술자의 추출 과정은 이어지는 장에서 자세하게 기술된다 동심원 구획 서술자의 추출을 위한 동심원 구획 방법은 본 논문에서 제안하고 있는 방법의 기본요소 중 하나이며 동심원 형태의 영역 구획을 이용하여 영상내의 픽셀값의 상대적인 분포를 서술함으로써 영상의 고유한 특징을 나타내는데 초점을 맞추고 있다. 그림 3.5은 입력 영상에 대하여 동심원 형태의 구획을 통하여 영상의 중심영역을 구획하고 있는 형태를 보여주고 있다. 76