KR100460222B1

KR100460222B1 - 멀티미디어 스트림에 대한 구조적 인덱스 정보 기술 방법, 진행형 비디오 인덱싱 방법 및 시스템

Info

Publication number: KR100460222B1
Application number: KR10-2002-0033822A
Authority: KR
Inventors: 전성배; 윤경로
Original assignee: 엘지전자 주식회사
Priority date: 2002-06-17
Filing date: 2002-06-17
Publication date: 2004-12-04
Also published as: KR20030096798A

Abstract

본 발명은 비디오의 구조적 정보인 씬(Scene) 정보와 샷(Shot) 정보, 그리고 그들의 연관관계를 자동으로 추출하는 자동 비디오 인덱싱 시스템에 관한 것이다.

본 발명은 신규 샷(Shot_cur) 및 샷 히스토그램을 검출하는 단계, 상기 샷(Shot_cur)에 대하여 매치 윈도우내의 샷간의 비유사도를 측정하고 비유사도에 따라 샷간의 링크 설정, 링크가 설정된 씬의 연결 씬(Linked Scene)으로의 등록, 씬/레이블/샷간의 연관관계 정보를 갱신하는 단계, 매치 윈도우 크기를 기준으로 하여 현재의 샷에서 매치 윈도우 크기만큼 떨어져 있는 샷(Shot_cur-τo)과 그 이전의 샷(Shot_cur-τo-1)이 각각 단절 씬(Broken Scene), 연결 씬(Linked Scene)에 속해있는지에 대한 정보와, 각각의 샷이 속한 씬들이 동일한지의 여부에 따라, 아무 동작도 하지 않거나, 두개의 샷이 속해 있는 씬끼리의 통합(Merge)을 하거나, 씬 경계 선언의 동작을 하는 단계와, 상기 확정된 씬/레이블/샷 정보를 포함하는 씬 정보를 영구 저장장치에 기록하고 저장된 씬 정보를 위하여 할당된 동적 메모리 영역을 해제하는 단계; 를 포함하여 이루어진 진행형 비디오 인덱싱 알고리즘이다.

Description

멀티미디어 스트림에 대한 구조적 인덱스 정보 기술 방법, 진행형 비디오 인덱싱 방법 및 시스템{Structural index informaion description method for multimedia stream, progressive video indexing method and system}

본 발명은 멀티미디어 콘텐트의 검색이나 브라우징, 요약을 위한 비디오 인덱싱 시스템에 관한 것으로서, 특히 비디오 콘텐트의 구조적 정보인 씬(Scene) 정보와 샷(Shot) 정보, 그리고 그들의 연관관계를 자동으로 추출하는 자동 비디오 인덱싱 시스템에 관한 것이다.

멀티미디어 콘텐트에 대하여 사용자가 원하는 데이터를 선별하여 주는 멀티미디어 브라우징 시스템에서, 가장 기본적인 연구는 비디오 콘텐트를 분석하는 작업이며, 대부분의 비선형적인 비디오 브라우징 기능은 샷 세그멘테이션(Shot segmentation)과 샷 클러스터링(Shot clustering) 기술을 기반으로 하고 있다.

도1은 샷 세그멘테이션과 샷 클러스터링의 관계를 보여주고 있으며, 도2는 샷 세그멘테이션 기술과 샷 클러스터링 기술을 이용한 비디오 콘텐트 요약방법을 보여주고 있다. 비디오 스트림은 샷 세그멘테이션 모듈에 의하여 샷 단위로 분할되며, 샷 클러스터링은 샷 세그멘테이션 결과를 바탕으로 씬 정보를 구축한다. 도2에 나타낸 예를 살펴보면, 비디오 스트림에서 검출된 9개의 샷이 클러스터링 프로세스에 의하여 1개의 씬으로 요약되고, 1개의 씬은 3개의 키프레임(Keyframe)으로 대표된다. 이와 같이 클러스터링 프로세스를 이용하면 샷 세그멘테이션 보다 훨씬 높은 수준의 비디오 콘텐트 요약이 가능하다.

디지털 비디오 환경에서 사용자는 원하는 콘텐트만을 선별적으로 시청하기를 원하며, 하이라이트(Highlight) 등을 원하기도 한다. 또한 하나의 콘텐트에서 자신이 원하는 부분만을 선별적으로 시청하기를 원하기도 한다. 비 선형적 비디오 브라우징(Non linear video browsing)이란, 비디오를 시청함에 있어서 사용자가 원하는 부분만을 취사 선택하여 선별적으로 브라우징이 가능하게 하거나, 비디오의 일정 부분만을 재생하여 요약 정보를 빠른 시간 안에 제공하거나, 원하는 부분으로 빠르게 이동할 수 있는 수단을 제공하는 일련의 브라우징 방법을 의미한다.

이러한 의미에서 키프레임 인터페이스를 기반으로 한 스토리 보드(Story board)가 제안되었으며, 구조적 정보를 제공하기 위하여 ToC(Table of Contents) 인터페이스가 제안되었으며, 비디오 콘텐트의 구조적 정보를 이용한 스키핑(Structure based skipping) 및 빠른 시간 내에 비디오 콘텐트에 대한 요약 정보를 제공하는 비디오 스키밍(Video Skimming)기술이 연구되었다.

도3은 샷 클러스터링 기술과 비 선형적인 비디오 브라우징과의 관계를 요약하여 보여주는 도면이다. 샷 클러스터링 프로세스는 검출된 샷으로부터 논리적인 이야기 단위인 LSU(Logical Story Unit : 씬)를 검출하는 프로세스이다.

샷 클러스터링 과정을 거치면 하나의 콘텐트는 여러 개의 씬으로 분할되고, 각각의 씬은 서브-씬 또는 개별 샷의 연결로 구성된다. 즉, 샷 클러스터링 과정을 통해서 하나의 비디오 콘텐트의 구조적 정보가 추출된다.

이렇게 추출된 비디오 콘텐트의 구조적 정보는 키프레임을 이용한 비디오 콘텐트 요약을 위해 활용된다. 대표적인 예가 ToC 인터페이스와 스토리 보드 인터페이스이다. 샷 세그멘테이션의 결과만을 이용하면, 비디오 콘텐트의 의미적 정보를 기반으로 하는 키프레임의 개수 조절이 어렵지만, 샷 클러스터링의 결과로 얻어진 구조적 정보를 이용하면 하나의 콘텐트를 요약하기 위한 키프레임의 개수 조절이 자유로우며, 멀티미디어 콘텐트를 사용자에게 내용상의 의미를 충분히 전달하는 압축된 형식으로 제공할 수 있다.

샷 클러스터링을 통해 얻어진 구조적 정보는 키프레임 인터페이스 뿐만 아니라, 비디오 콘텐트의 요약적 내용을 동영상의 형태로 제공하는 자동 비디오 스키밍과 자동 하이라이트 시스템의 중요한 입력으로 활용된다. 즉, 비디오 스키밍 시스템이나 자동 하이라이트 시스템은 비디오 콘텐트의 구조적 정보를 이용하여, 각각의 씬 별로 디스플레이될 구간을 결정하고 이를 디스플레이 함으로써 샷 세그멘테이션의 결과만으로는 제공하기 어려운 높은 수준의 비디오 스키밍과 하이라이트를 제공할 수 있다.

기존의 샷 클러스터링 기술로서 샷간의 차이에 근거하여, 동일한 씬 내에서는 비슷한 샷들이 반복적으로 나타남을 기준으로 씬을 검출하는 방법이 있다. 이 방법에서는 각각의 샷에서 추출된 2~3개의 키프레임으로부터 가상의 이미지를 생성하여 샷을 비교하는 기준으로 이용하며, 두개의 샷을 비교함에 있어서는 블록매칭을 이용한다. 즉 샷 A로부터 얻어진 가상의 키프레임 F_A와 샷 B로부터 얻어진 가상의 키프레임 F_B를 비교함에 있어서. F_A와 F_B간의 블록 시퀀스 매칭을 통하여 이미지간의 차이를 구하고 이를 샷간의 차이로 정한다. 이와 같이 샷간의 차이에 근거하여, 동일한 씬 내에서는 비슷한 샷들이 반복적으로 나타나는 것을 기준으로 씬을 검출하였다.

상기 기술한 샷 클러스터링 알고리즘은 템플릿을 이용하지 않는 샷 클러스터링 방법에서 매우 주목할 만한 연구 결과이다. 그러나 샷간의 차이를 구함에 있어서 블록 매칭을 이용하였고, 블록의 쉬프트 매칭을 이용하므로 시간이 많이 걸리고, 부가적인 메모리가 요구된다.

또한, 샷 세그멘테이션과 샷 클러스터링을 동시에 수행하기 위한 구체적인 방법을 제시하지 못하였다. 또한 구체적인 구현을 위하여 제한된 메모리를 사용할 경우의 알고리즘에 대한 방법도 제시하지 못했다. 또한 상기 기술한 방법을 이용하면 대화 장면 등 비슷한 장면이 반복적으로 발생하는 부분은 하나의 씬으로 검출이 가능하지만, 각기 특성이 다른 샷들의 연결로 이루어진 장면들로 구성된 부분에서는 씬의 개수가 급격히 증가하는 현상을 보이게 되므로, 결과적으로 일반적인 비디오 콘텐트에 대한 만족할 만한 수준의 요약을 제공하기 어렵다.

일반적으로 실시간 처리 시스템이나 셋탑 박스 응용 등을 위하여서는 샷 세그멘테이션과 샷 클러스터링 작업이 동시에 진행되어야 하며, 제한된 메모리를 사용하여야 하고, 그 수행 속도가 매우 빨라야 한다. 따라서 기존의 알고리즘은 녹화와 인덱싱, 브라우징이 동시에 가능한 PVR(Personal Video Recorder)과 같은 셋탑 박스 구현에는 적합하지 않다.

그러나 디지털 방송이 일반화되고 녹화와 재생이 동시에 가능한 셋탑 박스가 시장에 출시되면서, 이러한 장치에서 키프레임을 이용한 비디오 요약과 네비게이션 기능 및 자동 스키밍, 하이라이트 제공과 같은 비선형적인 비디오 브라우징 기능을 제공하기 위한 연구가 필요하다. 그러나 기존의 샷 클러스터링 연구는 디지털 콘텐트에 대한 구조적 정보 추출에 관심이 많았기 때문에, 셋탑 박스와 같은 시스템에서의 샷 클러스터링 기술 적용에 관해서는 별다른 연구가 없었으며, 알고리즘 역시 메모리 효율이나 계산의 단순화 등이 집중적으로 고려되지 않았다. 디지털 방송이 일반화되면 사용자들은 더 많은 부가 기능을 요구할 것이고, 그에 따라 셋탑 박스에서의 비선형적인 비디오 브라우징의 요구는 증가할 것이므로 셋탑 환경에 적용이 가능한 샷 클러스터링 알고리즘과 시스템이 요구된다.

본 발명은 VOD서버와 같은 비디오 아카이브(video archive)에서는 물론이고, PVR과 같은 셋탑 박스 시스템에서 키프레임을 이용한 비디오 콘텐트 요약 및 네비게이션 방법과 자동 비디오 스키밍 및 하이라이트 제공을 위해 이용될 수 있는 실시간 비디오 인덱싱 방법과 비디오 인덱싱 시스템을 제공함을 목적으로 한다.

특히, 본 발명은 1.비디오 콘텐트의 구조적 정보(Scene/Shot 구조) 추출, 2.샷 세그멘테이션 결과를 이용한 샷 클러스터링 프로세스, 3.빠른 수행 시간(압축 도메인의 가공된 데이터 이용), 4.제한된 메모리 이용, 5.샷 세그멘테이션과 샷 클러스터링 프로세스가 실시간으로 동시에 수행, 6.검출된 씬을 연결 씬(Linked Scene)과 단절 씬(Broken Scene)으로 구별, 7.비선형적 비디오 브라우징을 위한 효과적이고 효율적인 인덱스 구조 생성을 특징으로 하는 비디오 인덱싱 시스템과 그 비디오 인덱싱 방법을 제공함을 목적으로 한다.

상기 특징에 따른 본 발명의 비디오 인덱싱 알고리즘과 시스템은 기존의 알고리즘이나 시스템과는 달리, 비디오 압축 도메인으로부터 특징소(Feature)를 추출하여 인덱싱을 하므로 속도가 매우 빠르며, 제한된 메모리를 사용하며, 샷 세그멘테이션(Shot segmentation)과 샷 클러스터링(Shot clustering) 프로세스가 동시에 수행 가능하며, 멀티미디어 스트림의 녹화나, 디코딩, 재생, 인코딩과 동시에 수행 가능한 진행형 비디오 인덱싱 알고리즘을 제공하는데 또 다른 목적이 있다.

또한 상기한 바와 같이 본 발명의 비디오 인덱싱 시스템은 실시간 시스템에 적용이 가능하며, 샷 클러스터링 프로세스는 샷 세그멘테이션 프로세스에서 사용하는 특징소 데이터와, 샷 세그멘테이션의 결과물인 샷 정보를 이용하므로 별도의 특징 추출 작업이 불필요하기 때문에 매우 빠른 수행시간을 보장하고, 씬을 연결 씬과 단절 씬으로 구분하는 방법을 제공하여, 비디오 콘텐트에 대한 키프레임 요약이나 비디오 스키밍(Video skimming), 자동 하이라이트 생성에 중요한 단서를 제공하며, 씬의 레이블(Label) 개념을 도입하여 비디오 스키밍, 스키핑 및 자동 하이라이트 구성에 중요한 단서를 제공함으로써 여러 가지 비선형적인 비디오 브라우징 방법에 응용 가능한 효과적인 인덱스 구조를 생성하는데 또 다른 목적이 있다.

도1은 샷 세그멘테이션과 클러스터링의 개념을 나타낸 도면

도2는 샷 세그멘테이션과 클러스터링을 이용한 비디오 요약 방법의 일예를 나타낸 도면

도3은 샷 클러스터링과 비선형적인 비디오 브라우징과의 관계를 나타낸 도면

도4는 본 발명에서 연결 씬과 단절 씬의 개념을 설명하기 위한 도면

도5는 본 발명에서 클러스터링의 개념을 요약하여 나타낸 도면

도6은 본 발명의 비디오 인덱싱 알고리즘의 순서도

도7은 본 발명의 비디오 인덱싱 알고리즘 수행의 예를 나타낸 도면

도8은 본 발명의 비디오 인덱싱 시스템에 따른 인덱스 자료구조의 예를 나타낸 도면

도9는 본 발명의 비디오 인덱싱 시스템의 구성을 나타낸 도면

상기 목적을 달성하기 위한 본 발명의 진행형 비디오 인덱싱 방법은,

비디오 콘텐트에서 샷 정보로 신규 샷(Shot_cur) 및 샷 히스토그램을 추출하는 단계와; 상기 추출된 샷 정보를 이용해서 샷간의 비유사도를 기반으로 샷간 링크를 설정하고 링크가 설정된 씬을 연결 씬으로 등록하고 씬, 레이블, 샷간의 연관 관계 정보를 설정하는 단계와; 현재의 샷(Shot_cur)에서 매치 윈도우 크기만큼 떨어져 있는 샷(Shot_cur-τo)과 그 이전의 샷(Shot_cur-τo-1)이 각각 상기 단절 씬에 속한 것인지 혹은 연결 씬에 속한 것인지에 대한 정보와, 상기 각각의 샷이 속한 씬들이 동일한지 혹은 다른지에 따라, 상기 두개의 샷(Shot_cur-τo, Shot_cur-τo-1)이 속해 있는 씬끼리의 통합(merge)을 하거나, 씬 경계 선언을 하는 단계와; 상기 통합되거나 경계가 선언된 씬 정보를 저장하는 단계; 를 포함하여 이루어지는 것을 특징으로 하는 진행형 비디오 인덱싱 방법이다.

또한 상기 본 발명의 진행형 비디오 인덱싱 방법에서, 상기 비유사도의 측정은 상기 샷(Shot_cur)에 대하여 매치 윈도우내의 샷간의 비유사도를 측정하며, 측정된 비유사도를 이용해서 최소의 비유사도를 갖는 샷(Shot_min)을 검출한 후, 해당 비유사도가 특정 임계치 이하이면 샷간의 링크를 설정하고 링크가 설정된 씬을 연결 씬으로 등록하는 것을 특징으로 한다.

또한 상기 본 발명의 진행형 비디오 인덱싱 방법에서, 상기 씬은 하나 이상의 연속된 샷의 시퀀스로 정의되고, 상기 레이블은 씬 내에서 샷 간의 비 유사도가 특정 임계치(τ_shotdiff)이하인 샷들의 시퀀스로 정의되며, 하나의 레이블은 한 개 이상의 샷을 포함하는 것을 특징으로 한다.

또한 상기 본 발명의 진행형 비디오 인덱싱 방법에서, 상기 씬은 레이블의 리스트로 표현되며, 레이블은 샷의 리스트로 표현되는 것을 특징으로 한다.

또한 상기 본 발명의 진행형 비디오 인덱싱 방법에서, 상기 연결 씬은 씬 내에 두개 이상의 샷을 구성 요소로 가지는 레이블이 존재하는 씬임을 의미하고, 단절 씬은 씬 내에 두개 이상의 샷을 구성 요소로 가지는 레이블이 존재하지 않는 씬을 의미하는 것을 특징으로 한다.

또한 본 발명의 상기 진행형 비디오 인덱싱 방법에서, 상기 매치 윈도우는 현재의 샷(Shot_cur)이 검출된 시점으로부터 이전의 몇 개의 샷 오프셋(τ_o) 이내에존재하는 샷들이 시간 순서로 배열된 FIFO 구조로 이루어지는 것을 특징으로 한다.

또한 본 발명의 상기 진행형 비디오 인덱싱 방법에서, 상기 새로이 입력된 샷(Shot_cur)에 대하여 단일 씬과 단일 레이블, 단일 샷 정보를 추가하고, 이에 대한 링크 설정 작업을 통하여 새로이 입력된 단일 씬/단일 레이블/단일 샷 정보를 갱신하는 것을 특징으로 한다.

또한 본 발명의 상기 진행형 비디오 인덱싱 방법에서, 상기 기준 샷과 최소의 비유사도를 갖는 샷(Shot_min)간의 링크를 구성하는 경우에는 두개의 샷을 동일한 레이블에 할당하여 레이블 정보를 갱신하고, 두개의 샷이 포함된 씬들을 통합(merge)하며, 새로운 샷이 추가된 씬을 연결 씬으로 표기하여 씬 정보를 갱신하고, 링크가 구성되지 않는 경우에는 새로운 단절 씬에 새로운 레이블을 할당하고 거기에 기준 샷을 할당한 정보를 기록하는 것을 특징으로 한다.

또한 본 발명의 상기 진행형 비디오 인덱싱 방법에서, 상기 현재의 샷(Shot_cur)에서 매치 윈도우 크기만큼 떨어져 있는 샷(Shot_cur-τo)과 그 이전의 샷(Shot_cur-τo-1)에 대하여 각각의 샷이 속한 씬이 연결 씬인지 단절 씬인지를 파악하고, 두 샷(Shot_cur-τo와 Shot_cur-τo-1)이 속한 씬이 동일한 씬인지 다른 씬인지를 판단하여, 두개의 샷이 모두 단절 씬에 속한 경우에는 샷(Shot_cur-τo-1)이 속한 씬 정보에 샷(Shot_cur-τo)이 속한 씬을 통합(merge)하고, 두개의 샷 중에서 하나는 단절씬에 속하고 나머지 하나는 연결 씬에 속한 경우에는 씬 경계가 발생하였음을 선언하고샷(Shot_cur-τo-1)이 속한 씬 정보를 저장장치에 저장 가능한 상태로 변경하며, 두개의 샷이 모두 연결 씬에 속하고 두개의 샷이 속한 씬이 동일할 경우에는 아무런 동작을 하지 않고, 두개의 샷이 모두 연결 씬에 속하고 두개의 샷이 속한 씬이 다른 경우에는 씬 경계가 발생하였음을 선언하고 샷(Shot_cur-τo-1)이 속한 씬 정보를 저장장치에 저장 가능한 상태로 변경하는 것을 특징으로 한다.

또한 본 발명의 상기 진행형 비디오 인덱싱 방법에서, 상기 씬통합 또는 씬 경계 선언 후에 그 씬 정보를 저장함에 있어, 신규 확정 씬이 등록될 때마다 영구 저장 장치에 저장하는 정책을 사용하는 경우에는 신규 확정 씬에 대한 씬 정보를 저장장치에 저장하고; 일정량 이상의 확정 씬 정보가 채워진 이후에 한꺼번에 저장하는 정책을 사용하는 경우에는 신규 확정 씬 정보가 일정량 이상 등록된 경우에만 확정 씬들에 대한 정보를 저장장치에 저장하며, 신규 확정 씬 정보가 없는 경우에는 상기 샷 정보 추출단계로 분기하는 것을 특징으로 한다.

또한 상기 목적을 달성하기 위한 본 발명의 진행형 비디오 인덱싱 시스템은,

외부입력과 클러스터링 상황에 따라 비디오 인덱싱을 수행하기 위한 클러스터링 제어수단과; 클러스터링 제어부수단에 의해 씬 경계 검출 판단을 위한 씬 경계 검출수단과; 샷 클러스러링 알고리즘에서 두개의 샷 의 비유사도를 측정하고 이를 바탕으로 하여 링크를 설정하고 메모리의 씬/레이블/샷 정보를 갱신하는 작업을 하는 링크 설정수단과; 미디어 파일에서 샷 정보를 추출하기 위한 샷 인덱스 결정수단과; 샷 인덱스 추출을 위하여 미디어 파일을 디코딩하여 세그멘테이션과 클러스터링 작업을 위한 특징소를 추출하는 특징소 추출수단과; 샷 인덱스 결정수단으로부터 입력되는 샷 인덱스를 관리하고 이를 클러스터링 제어수단에 알리는 샷 인덱스 입력수단과; 샷 인덱스 입력수단으로부터 입력되는 샷 인덱스와, 링크 설정수단, 씬 경계 검출수단으로부터 생성되고 갱신되는 씬/레이블 인덱스를 관리하고 클러스터링 제어수단의 제어 신호에 따라 필요한 경우 저장 장치에 인덱스 정보를 기록하는 일을 담당하는 인덴스 관리수단; 을 포함하여 샷 세그멘테이션과 샷 클러스터링을 동시에 수행하여 멀티미디어 콘텐트에 대한 씬/샷/레이블에 대한 정보와 그들 간의 연관관계를 기술한 구조적 인덱스 정보를 추출하는 것을 특징으로 하는 진행형 비디오 인덱싱 시스템이다.

또한 상기 본 발명의 진행형 비디오 인덱싱 시스템에서, 상기 특징소 추출수단은 비디오 인덱싱 시스템이 인덱싱하고자 하는 미디어에 대한 정보를 클러스터링 제어수단으로부터 받아 비디오 인덱싱에 필요한 특징소들을 추출하고 해당 데이터가 준비되면 샷 인덱스 결정수단으로 데이터를 전송하는 것을 특징으로 한다.

또한 상기 본 발명의 진행형 비디오 인덱싱 시스템에서, 상기 샷 인덱스 결정수단은 클러스터링 제어수단으로부터 샷 인덱스 추출 명령을 받아 특징소 추출수단을 이용하여 필요한 정보를 추출하고 이를 샷 인덱스 입력수단으로 전달하며, 새로운 샷이 검출될 때마다 또는 미디어에 대한 샷 세그멘테이션이 종료될 때 이를 샷인덱스 입력수단에 알리는 것을 특징으로 한다.

또한 상기 본 발명의 진행형 비디오 인덱싱 시스템에서, 상기 샷 인덱스 입력수단은 새로운 샷이 입력되면 인덱스 관리수단에 새로운 샷을 등록한 후 클러스터링 제어수단에 이를 알리며, 샷 세그멘테이션이 종료된 경우도 종료되었음을 클러스터링 제어수단에 알리는 것을 특징으로 한다.

또한 상기 본 발명의 진행형 비디오 인덱싱 시스템에서, 상기 클러스터링 제어수단은 샷 인덱스 결정수단으로부터 입력되는 샷에 대한 정보를 바탕으로 링크 설정수단을 통하여 링크를 설정하고 인덱스 관리수단이 관리하는 씬/레이블/샷 정보를 갱신하며, 씬 경계 검출수단을 제어하여 씬 경계가 발생하였는지를 검사하고, 씬경계 검사지점에 대한 통합(merge), 경계 선언 등의 오퍼레이션을 수행하여 메모리의 씬/레이블/씬 간의 정보를 인덱스 관리수단을 통하여 갱신하도록 제어하고, 씬 경계 검출수단으로부터 씬 경계 선언이 발생한 경우에 다시 인덱스 관리수단을 이용하여, 씬 경계가 선언된 씬에 대한 정보를 저장장치에 저장할 수 있도록 제어하는 것을 특징으로 한다.

또한 상기 본 발명의 진행형 비디오 인덱싱 시스템에서, 상기 인덱스 관리수단은 저장 정책에 따라 씬 경계가 선언될 때마다 확정된 씬 정보를 저장장치에 저장하거나, 일정량 이상 씬 정보가 추출된 후에 씬 정보를 한꺼번에 저장하고 저장된 씬 정보에 대한 메모리 구조를 자동 해제하는 것을 특징으로 한다.

또한 상기 목적을 달성하기 위한 본 발명의 비디오 인덱스 정보 기술방법은, 멀티미디어 콘텐트를 ;

하나 이상의 샷들의 연속적인 시퀀스인 씬들의 리스트로 정의하고, 각각의 씬을 시작 시점과 종료 시점을 포함하는 구간 정보와, 씬에 속한 하나 이상의 샷들을 저장하기 위한 샷 리스트 정보와, 씬에 속한 하나 이상의 레이블을 저장하기위한 레이블 리스트 정보와, 연결 씬인지 단절 씬인지를 지정하는 플래그 정보를 포함하여 기술하는 것을 특징으로 하는 멀티미디어 스트림에 대한 구조적 인덱스 정보 기술 방법이다.

또한 상기 본 발명의 멀티미디어 스트림에 대한 구조적 인덱스 정보 기술방법에서, 상기 샷 리스트의 구성 요소는 개별 샷이며, 샷 정보는 시작 시점과 종료 시점을 포함하는 구간 정보를 이용하여 기술되는 것을 특징으로 한다.

또한 상기 본 발명의 멀티미디어 스트림에 대한 구조적 인덱스 정보 기술방법에서, 상기 샷 리스트의 구성요소는 개별 샷이며, 샷 정보는 시작 시점과 종료 시점을 포함하는 구간정보 및, 샷에 대한 키프레임 정보를 포함하여 기술되는 것을 특징으로 한다.

또한 상기 본 발명의 멀티미디어 스트림에 대한 구조적 인덱스 정보 기술방법에서, 상기 레이블 리스트의 구성 요소는 개별 레이블이며, 레이블 정보는 씬내에서 해당 레이블을 할당받은 샷들의 리스트임을 특징으로 한다.

또한 상기 본 발명의 멀티미디어 스트림에 대한 구조적 인덱스 정보 기술방법에서, 상기 레이블 리스트의 구성 요소는 개별 레이블이며, 레이블 정보는 씬내에서 해당 레이블을 할당받은 샷들의 리스트와 레이블에 대한 키프레임 정보를 포함하여 기술되는 것을 특징으로 한다.

또한 상기 본 발명의 멀티미디어 스트림에 대한 구조적 인덱스 정보 기술방법에서, 상기 씬 정보는 씬을 대표하기 위한 키프레임 정보를 더 포함하여 기술되는 것을 특징으로 한다.

상술한 바와 같이 본 발명의 구조적 정보 추출이 가능한 진행형 비디오 인덱싱 시스템에 따른 비디오 인덱싱 방법 즉, 샷 클러스터링 방법은 샷 정보 추출단계, 링크 설정 단계, 씬 경계 판단 단계, 확정된 씬 정보를 디스크와 같은 영구 저장장치에 저장하는 단계로 이루어지는 것을 특징으로 한다.

더욱 상세하게는, 상기 첫번째 단계인 샷 정보 추출단계에서는 샷 세그멘테이션 알고리즘의 결과를 입력으로 받는 단계이며, 두번째 단계인 링크 설정단계는 메모리에 존재하는 매치 윈도우(Match window)(즉, 일정 범위) 내의 샷들과 첫번째 단계에서 검출된 샷간의 비유사도 측정을 통하여 새로 검출된 샷에 대한 대하여 링크를 구성하고, 레이블 정보와 씬정보를 설정하여 링크를 구성하는 단계이며, 세번째 단계인 씬 경계 판단 단계는 매치윈도우 크기를 기준으로 하여 현재의 샷에서 매치 윈도우 크기만큼 떨어져 있는 샷(Shot_cur-τo)과 그 이전의 샷(Shot_cur-τo-1) 간의 씬 경계를 검출하는 단계이며, 네번째 단계인 저장단계는 씬 경계가 선언된 경우 더 이상 변화하지 않을 씬 정보를 디스크에 저장하도록 명령하고, 다음 샷을 입력 받기 위하여 상기 샷(Shot_cur-τo-1)에 해당되는 메모리를 해제함으로써 본 시스템이 제한된 메모리 상에서 운용될 수 있도록 효율적으로 관리할 수 있게 하는 단계이다.

본 발명의 비디오 인덱싱 방법은 상기 첫번째 단계에서 샷 세그멘테이션 정보와 샷 히스토그램 정보를 이용하며, 두번째 단계에서 메모리의 매치 윈도우를 설정함으로써 샷 시퀀스에 관계없이 메모리를 제한적으로 사용할 수 있게 함을 특징으로 하며, 세번째 단계에서 씬 경계를 계속 판단하고, 네번째 단계에 의하여 메인 메모리에는 변경 가능한 인덱스를 저장하고 디스크와 같은 영구 저장 장치에는 확정된 인덱스가 저장되도록 보장하는 진행형 알고리즘으로 구현됨을 특징으로 한다.

다음은 본 발명의 비디오 인덱싱 방법을 요약하고, 각 단계를 더욱 상세하게 설명한다.

[제 1단계] : 샷 세그멘테이션 알고리즘을 이용하여 신규 샷(Shot_cur) 및 샷 히스토그램(ShotHist(Shot_cur)) 검출.

제 1단계는 샷 세그멘테이션 알고리즘을 이용해서 신규 샷(Shot_cur)을 검출하고, 또 검출되는 샷에 대하여 샷 히스토그램(ShotHist(Shot_cur))을 검출하는 과정이다.

샷 세그멘테이션은 일반적으로 스트림에서의 모션, 칼라 분포, 오디오 등의 연속성과 불연속성을 감지하고 이를 종합적으로 판단하여 개별 샷을 검출한다. 참고로, 샷 클러스터링은 일반적으로 장르 의존적인 지식을 기반으로 하여 각 샷들간의 유사성을 이용하거나, 중심이 되는 특정 이벤트를 검출함으로써 비디오 스트림을 논리적인 이야기 단위인 씬을 검출하는 프로세스이다. 샷 히스토그램은 본 발명에서 2가지 방식에 의하여 구해질 수 있는데, "하나의 샷에서 일정 기준으로 샘플링된 이미지들의 칼라 히스토그램의 평균 히스토그램"인 제1샷 히스토그램과, "하나의 샷에서 일정 기준으로 샘플링된 대표 이미지의 칼라 히스토그램"인 제2샷 히스토그램을 구한다.

[제 2단계] : 상기 제 1단계의 입력으로 얻어진 샷에 대하여 단일 단절 씬/단일 레이블/단일 샷 구조를 할당하고, 제 1단계의 입력으로 얻어진 샷과 매치 윈도우 내의 샷들과의 샷간 비유사도 측정을 하고, 최소의 비유사도를 갖는 샷(Shot_min)과의 비유사도가 일정 임계치 이하이면 새로 검출된 샷(Shot_cur)에 대하여 링크(Link) 정보를 설정하고 해당 샷(Shot_cur)이 속한 레이블 및 씬 정보를 갱신하며, 이때 링크가 설정되면 해당 샷이 속하게되는 씬을 연결 씬(Linked Scene)으로 설정하는 단계이다.

먼저, 본 발명 제2단계에서 샷간의 비유사도를 측정하는 방법에 대해서 설명한다.

[두 샷의 비 유사도 측정 방법]

샷 클러스터링을 위하여 가장 기초적인 단계는 두개의 샷간의 유사도 및 비유사도 측정이다. 샷간의 유사도/비유사도 측정에는 여러 가지 방법이 사용될 수 있지만, 본 발명에서는 두개의 샷간의 유사도 및 비유사도 측정을 위하여 샷 히스토그램을 이용한다. 샷 히스토그램의 히스토그램은 2가지 방식에 의하여 구해질 수 있는데, 앞서 설명한 바와 같이 제1샷 히스토그램은 "하나의 샷에서 일정 기준으로 샘플링된 이미지들의 칼라 히스토그램의 평균 히스토그램"이며, 제2샷 히스토그램은 "하나의 샷에서 일정 기준으로 샘플링된 대표 이미지의 칼라 히스토그램"이다.

이와 같이 샷 히스토그램을 두개의 샷간의 유사도 및 비유사도 측정의 기준으로 택한 이유는 이미지에 대한 칼라 히스토그램은 샷 세그멘테이션 과정에서 이미 추출되기 때문에 효율적으로 각 샷에 대한 샷 히스토그램을 구할 수 있으므로 그 수행속도가 매우 빠르기 때문이다. 아래의 식1은 제1샷 히스토그램의 수학적 정의이다.

이때, Hist(A)+Hist(B)는;

(Hist(A)+Hist(B))[m] = (Hist(A))[m]+(Hist(B))[m] l=0,1,2,...,n-1 ;로 정의된다.

샷 히스토그램이나 히스토그램은 모두 배열로서 정의되며, 본 발명의 설명을 위하여 Hist(A)는 프레임 A에 대한 칼라 히스토그램을 의미하고, ShotHist(S)는 샷 S에 대한 샷 히스토그램을 의미하며, ShotHist₁(S)은 샷 S에 대한 제1샷 히스토그램을 의미하며, ShotHist₂(S)는 샷 S에 대한 제2샷 히스토그램을 의미한다.

i번째 샷은 Shot_i로 표기하며, Shot_i에서 샘플링된 이미지의 수를 j라 하고, (Hist(A))[m]은 이미지 A에서 나타나는 m번째 칼라 인덱스를 갖는 칼라들에 대한 빈도 수를 의미하며, 칼라 히스토그램의 총 칼라 인덱스의 개수를 n이라 한다.

i번째 샷(Shot_i)에 대한 제1샷 히스토그램(ShotHist₁(Shot_i))은 샷 세그멘테이션을 위하여 샷(Shot_i)내에서 칼라히스토그램을 추출한 각각의 이미지 프레임(F_k: k=1,...,j)에 대한 이미지 히스토그램 (Hist(F_k))의 평균 히스토그램이며, 제2샷 히스토그램(ShotHist₂(Shot_i)=Hist(F_R))은 샷 내에서 샘플링된 특정 이미지에 대한 히스토그램이다. 이미지 히스토그램(Hist(F_k))은 배열로서 정의되고, 각각의 인덱스는 칼라 인덱스를 의미하며, 그 값은 각각의 칼라 인덱스에 해당하는 칼라가 해당 이미지에서 나타난 빈도 수를 의미한다. 그러므로 ShotHist(Shot_i)는, i번째 샷(Shot_i)에서 어떤 칼라가 얼마만큼 나타났는지에 대한 분포를 나타내는 자료구조이다.

본 발명에서는 샷 히스토그램을 추출하기 위하여 샷 내의 모든 프레임을 이용하지는 않는다. F_k는 샷 세그멘테이션을 위하여 일정한 규칙에 의하여 샘플링 되어 칼라 히스토그램이 추출된 이미지만을 의미한다. MPEG과 같은 압축 방식을 이용한 비디오 콘텐트에 대하여서는 샷 내의 I 프레임만이 F_k로 이용된다. 또한 빠른 알고리즘을 위하여 원 이미지를 복원한 뒤 칼라 히스토그램을 구하지 않고, 빠른 칼라 히스토그램 추출을 위하여 DC이미지(DC Image) 상에서 칼라 히스토그램을 추출한다.

이렇게 추출된 샷 히스토그램을 기반으로 하여 두 샷간의 유사도와 비유사도를 구하는데, 식2는 두개의 샷(Shot_i와 Shot_j)의 제1샷 히스토그램을 기반으로 한 제1비유사도(ShotDiff₁(Shot_i,Shot_j))와 제2샷 히스토그램을 기반으로 한 제2 비유사도(ShotDiff₂(Shot_i,Shot_j))를 구하는 방법을 나타낸 것이다.

이와 같이 샷간의 비유사도(ShotDiff(Shot_i,Shot_j))는 제1비유사도 또는 제2비유사도를 이용하여 구할 수 있다. 제1비유사도 또는 제2비유사도를 어떻게 이용할 것인가의 선택은 클러스터링 알고리즘이나 시스템의 상황, 외부 입력에 의해 변경될 수 있다. 식3은 샷간의 비유사도 'ShotDiff(Shot_i,Shot_j)' 를 구하는 방법을 나타낸 것이다.

여기서, 만약 이미지 히스토그램의 각 빈(bin)의 합이 1이면, 샷 히스토그램의 각 빈의 합도 1이며, 샷간의 비유사도 ShotDiff(Shot_i,Shot_j) 는 최소 0에서 최대 2까지의 값을 가진다.

상기 식3에서 알 수 있듯이 샷간의 비유사도(ShotDiff(Shot_i,Shot_j))는 제1비유사도(ShotDiff₁(Shot_i,Shot_j))만 사용하거나, 제2비유사도(ShotDiff₂(Shot_i,Shot_j))만을 사용하거나, 또는 이 둘에 가중치(α,β)를 적용하여 구한 유사도 즉, (α× ShotDiff₁(Shot_i,Shot_j) + β×((ShotDiff₂(Shot_i,Shot_j)를 사용한다.

앞서 설명한 본 발명 제2단계의 서두에서 기술한 바와 같이 본 발명에서는 씬에 대하여 연결 씬과 단절 씬의 개념을 정의하고 사용한다.

본 발명 비디오 인덱싱 방법에 따른 샷 클러스터링을 위하여 다음과 같이 연결 씬(Linked Scene)과 단절 씬(Broken Scene)을 정의한다. 연결 씬이란, 한 씬내에서 비슷한 씬들이 반복적으로 나타나는 씬을 의미하며, 단절 씬은 그렇지 않은 씬을 의미한다. 예를 들어 대화 장면 등의 경우에는 연결 씬이 많이 이용되며, 액션 장면이나, 빠른 이야기 전개를 위하여서는 단절 씬이 많이 이용된다.

또한, 본 발명의 클러스터링 알고리즘 설명을 위해서 레이블(Label)이라는 개념을 정의한다. 레이블은 "하나의 씬 내에서 일정 샷 오프셋 이내에 존재하는 비슷한 샷들의 시퀀스 집합"으로 정의되며, 씬은 "레이블의 시퀀스"로 정의된다.

연결 씬은 두개 이상의 샷 시퀀스들로 정의되는 레이블이 하나 이상 존재 하는 씬이며, 단절 씬은 두개 이상의 샷들로 정의되는 레이블이 없는 씬이다.

도4는 본 발명의 씬, 레이블, 연결 씬, 단절 씬 등을 설명하기 위한 도면이다. 도4에서 각각의 A1, A2, A3, B1,... 등은 개별 샷을 의미하며, 도4의 (a)는 레이블이 3개인 연결 씬의 구조에 대한 예제이고, 도4의 (b)는 레이블이 6개이며, 샷의 개수도 6개(A,B,C,D,E,F)인 단절 씬의 구조에 대한 예제이다. 도4의 (a)에서 살펴보면 각각의 개별 샷에 대하여 링크(Link)를 설정하였고, 또 레이블(Label)이 어떤 개념으로 사용되고 있는가를 표현하고 있다.

이와 같이 본 발명의 샷 클러스터링을 위해서는 앞서 기술한 링크 설정 단계가 필요하다. 다음에는 링크를 설정하는 방법을 설명한다.

일단 샷 클러스터링 프로세스에 새로운 샷이 입력되면 단일씬/단일레이블/단일샷 구조가 할당된다. 샷간의 링크 설정은 앞서 설명된 샷간의 비유사도 측정 방법과 샷 오프셋을 이용하는데, i번째 샷(Shot_i)과 i-k 번째 샷(Shot_i-k)간의 샷 오프셋은 k=i-(i-k)로 정의된다. 본 발명의 인덱싱 알고리즘에서는 i번째 샷(Shot_i)과 i-k 번째 샷(Shot_i-k)간의 오프셋(k)이 일정 범위(τ_o) 이내이며 샷의 비유사도가 일정 범위(τ_shotdiff) 이내인 경우에 i번째 샷(Shot_i)과 i-k 번째 샷(Shot_i-k)간의 링크(link)를 설정하고, 그렇지 않으면 i번째 샷(Shot_i)과 i-k 번째 샷(Shot_i-k)간의 링크를 설정하지 않는다. 다음의 식4는 이와 같이 두개의 샷간의 링크 설정 방법을 수식적으로 요약한 것이다. 상기 링크가 설정된 두 샷은 하나의 레이블에 속하게 되며, 같은 씬에 속하게 된다.

상기한 바와 같이 링크 설정 단계에서 새로이 샷 클러스터링 프로세스에 입력된 샷이 속한 씬 및 레이블에 대한 갱신 작업이 이루어진다. 즉, 상기 식4의 조건에 의하여 일단 링크가 설정되면, i번째 샷에 대한 레이블 아이디(Label ID)가 i-k번째 샷과 동일한 레이블 아이디로 갱신되며 i-k~i 까지의 샷이 동일한 씬에 속하게 된다. 만일 이전의 클러스터링 프로세스에 의하여 l ≤i-k ≤m 의 관계가 성립하는 l~m까지의 샷이 하나의 씬으로 등록되어 있으면, l~i 까지의 샷 시퀀스가 하나의 씬이 되고, i번째 샷은 이 씬에 속하게 된다.

본 발명의 알고리즘은 메모리에 관리할 샷 정보의 개수를 미리 지정하므로 제한된 메모리를 사용하는 시스템 상에서 구현이 가능하다.

도5a는 6개의 샷들로 샷 메모리(Shot Memory)를 제한하는 FIFO를 구성하여 사용한 예이다. 샷 메모리(Shot Memory)의 크기는 구현환경 및 알고리즘 성능을 위해 달라질 수 있다.

[제 3단계] : 매치윈도우(Match Window)의 크기를 기준으로 하여 현재의 샷에서 매치 윈도우 크기만큼 떨어져 있는 샷(Shot_cur-τo)과 그 이전의 샷(Shot_cur-τo-1)간의 씬 경계를 체크한다. 이 때 두개의 샷이 단절 씬에 속해있는지, 연결 씬에 속해있는지, 같은 씬에 속해 있는지, 다른 씬에 속해 있는지의 여부에 따라서 스킵(Skip), 씬 머지(Scene Merge), 씬 경계(Scene Break)설정의 오퍼레이션을 수행한다.

본 발명 제3단계에서 씬 경계를 검사하는 방법과 그 오퍼레이션을 설명한다.

본 발명의 비디오 인덱싱 알고리즘은 샷 세그멘테이션 작업과 샷 클러스터링 작업이 동시에 수행됨을 특징으로 함은 이미 기술한 바와 같다. 샷 클러스터링 알고리즘 입장에서 보면, 하위의 샷 세그멘테이션 작업에 의하여 신규로 검출된 샷들이 계속하여 입력되고, 이를 바탕으로 샷 클러스터링 프로세스는 샷들간의 링크를 설정하고, 씬 경계(Scene Break)를 검출한다.

도5의 (a), (b)는 본 발명의 알고리즘을 도식화 한 것이다. 새로운 샷이 샷 세그멘테이션 알고리즘에 의하여 샷 클러스터링 알고리즘에 입력되면, 샷 클러스터링 알고리즘은 앞서 설명한 바와 같이 일정 범위(매치 윈도우)이내의 오프셋을 가지는 샷들에 대하여 비슷한 샷이 존재하는지를 검사한다.

매치 윈도우내의 각 샷들에 대하여 기준샷(Shot_cur)과의 비유사도를 측정하고 해당 비유사도가 가장 작은 샷(Shot_min)과의 비유사도가 일정 임계치(τ_shotdiff) 이내이면 기준샷(Shot_cur)과 비유사도가 가장 작은 샷(Shot_min)간의 링크를 설정하고 기준 샷(Shot_cur)의 레이블 아이디(ID)를 비유사도가 가장 작은 샷(Shot_min)의 레이블 아이디로 결정하고, 비유사도가 가장 작은 샷(Shot_min)이 속한 씬으로부터 기준 샷(Shot_cur)까지의 샷 시퀀스는 하나의 씬에 속한다고 판단하고 해당 씬은 연결 씬으로 간주한다.

도5a에서는 k+6번째 샷(Shot_cur=Shot_k+6)이 입력되면 기준샷(Shot_k+6)과 매치 윈도우 내의 샷들(Shot_k+1~Shot_k+5)간의 비유사도를 측정한다. 만일 k+4번째 샷(Shot_k+4)이 최소 비유사도 샷(Shot_min)으로 판단되고 해당 비유사도가 일정임계치(τ_shotdiff)보다 작다면, 도5a에 나타낸 바와 같이 기준샷(Shot_k+6)과 k+4번째 샷(Shot_k+4)간에 링크를 설정하고 이전의 클러스터링 프로세스에 의해 k+1번째 샷 ~ k+5번째 샷(Shot_{k+1 ~}Shot_k+5)이 하나의 씬으로 등록되어 있고 해당 씬은 연결 씬으로 정의되어 있으므로, k+1번째 샷 ~ k+6번째 샷(Shot_k+1~ Shot_k+6)이 하나의 씬으로 등록된다.

그러나 기준샷(Shot_cur)과 해당 비유사도가 가장 작은 샷(Shot_min)과의 비유사도가 일정 임계치(τ_shotdiff)보다 크면 기준샷(Shot_cur)에 대하여 새로운 씬과 새로운 레이블을 부여하며 새로운 씬은 단절 씬으로 기록된다.

새로이 검출된 기준샷(Shot_cur)에 대하여 상기 링크 설정 및 레이블 할당 작업이 모두 끝나면, 현재의 샷에서 매치 윈도우 크기만큼 떨어져 있는 샷(Shot_cur-τo)과 그 이전의 샷(Shot_cur-τo-1)간의 씬경계 검출을 한다.

씬 경계 검출 방법은 두개의 샷이 연결 씬으로 결정되어 있는지 혹은 단절 씬으로 결정되어 있는지에 대한 정보와, 두개의 샷(Shot_cur-τo, Shot_cur-τo-1)이 동일한 씬에 속해 있는지의 여부를 이용한다. 경우에 따라서 씬 경계를 선언하거나, 두개의 샷을 동일한 씬으로 머지(Merge)하거나, 별도의 오퍼레이션이 없이 다음 샷의 입력을 기다리기도 한다.

따라서 본 발명의 비디오 인덱싱 알고리즘을 위해서는 해당 샷과 레이블과의관계 및 해당 레이블과 씬과의 관계 등에 대한 정보가 메모리에 항상 기술되어야 한다. 또한, 본 발명의 비디오 인덱싱 알고리즘은 새로이 샷이 검출된 경우, 검출된 샷에 대하여 바로 씬 경계를 검사하지 않고 매치 윈도우 크기만큼의 이전의 샷에 대하여 씬 경계를 검출하여 진행형 알고리즘을 구성하는 것을 특징으로 한다.

지금까지 설명한 씬 경계 검출 방법을 몇 가지 경우로 나누어 도5b를 참조하여 더욱 자세히 설명하면 다음과 같다.

[경우 1(Case1)] : 두개의 샷(Shot_cur-τo, Shot_cur-τo-1)이 모두 단절 씬에 속해 있는 경우.

이 경우는 두개의 샷을 동일한 씬에 속하도록 머지(Merge)한다. 머지 작업(Merge Operarion)은 현재의 샷(Shot_cur)에서 매치 윈도우 크기만큼 떨어져 있는 샷(Shot_cur-τo) 정보를 그 이전의 샷(Shot_cur-τo-1)에 추가함으로써 이루어진다.

이러한 머지 작업을 수행하는 이유는 액션 장면이나 빠른 이야기 전개 요약 부분 등을 하나의 씬으로 구성하여 비디오 콘텐트를 좀더 압축하여 요약할 수 있게 하기 위함이다.

[경우 2(Case2)] : 두개의 샷(Shot_cur-τo, Shot_cur-τo-1)중 하나는 단절 씬에, 하나는 연결 씬에 속한 경우.

이러한 경우에는 차후의 알고리즘 수행의 경우에도 새로이 검출된 샷과 샷(Shot_cur-τo-1)에 대한 링크 설정 작업이 수행되지 않으며, 두개의 샷(Shot_cur-τo,Shot_cur-τo-1)이 각기 다른 씬에 속해 있으므로 더 이상 같은 씬에 속할 경우가 존재하지 않는다. 따라서 이때에는 두개의 샷간에 씬 경계가 존재함을 선언하고 이전 씬(Shot_cur-τo-1이 속한 씬)의 정보를 영구 저장장치에 저장할 수 있다.

[경우 3(Case3)] : 두개의 샷(Shot_cur-τo, Shot_cur-τo-1)이 모두 연결 씬에 속한 경우.

이 경우의 오퍼레이션은 두가지의 경우로 나뉜다. 즉 두개의 샷(Shot_cur-τo, Shot_cur-τo-1)이 동일한 씬에 속한 경우와 각기 다른 씬에 속해있는 경우로 나뉘는데, 두개의 샷(Shot_cur-τo, Shot_cur-τo-1)이 동일한 씬에 속한 경우(Case3-1)에는 별다른 오퍼레이션을 수행하지 않으며, 두개의 샷이 다른 씬에 속한 경우(Case3-2)에는 더 이상 두개의 샷간의 링크 설정 프로세스가 수행되지 않으므로 두개의 샷간에 씬 경계가 존재함을 선언하고 이전 씬(Shot_cur-τo-1이 속한 씬)의 정보를 영구 저장장치에 저장할 수 있다.

[제 4단계] : 상기 제 3단계 수행이후, 이전 샷(Shot_cur-τo-1)을 샷 메모리에서 해제하며, 씬 경계가 선언된 경우에 이전 샷(Shot_cur-τo-1)이 속한 씬 정보를 영구 저장장치에 저장하고, 해당 씬에 대한 메모리 정보를 해제한다.

지금까지 설명한 본 발명의 비디오 인덱싱 방법 제1단계 내지 제4단계는 도6의 순서도로 표현할 수 있다.

샷 클러스터링 프로세스는 시작 단계에서 앞서 설명한 환경 변수(τ_o, τ_shotdiff)를 초기화하고 기타 변수(cur=0)를 초기화한다(단계 601).

샷 클러스터링은 이후에 샷 세그멘테이션 엔진에 샷 세그멘테이션 정보를 요구하고 샷 세그멘테이션 엔진이 새로운 샷(Shot_cur)을 검출하거나 미디어의 종료 시점에 도달할 때까지 대기한다(단계 602). 새로운 샷이 검출되면 단계 603으로 분기하여 샷 클러스터링 작업을 수행하고, 그렇지 않은 경우에는 단계 613으로 분기하여 메모리에 남은 씬, 레이블, 샷 정보에 대해 클러스터링 작업을 마무리한다. 단계 613으로 분기한 이후의 작업은 미디어에서 검출된 총 샷의 개수가 τ_o이하(즉, τ_o<= cur)이거나, 클러스터링 프로세스의 마지막 단계에서 더 이상 새로운 샷이 존재하지 않는 경우에 수행되는 서브루틴이다.

단계 613에서 샷의 개수에 해당하는 변수 즉, 현재 샷 번호(cur)가 τ_o이상인 경우는 단계 614로 분기하여 τ_o= τ_o-1로 설정한 후 단계 615에서 τ_o가 '0'보다 작지 않으면 단계 608로 분기하고, '0'보다 작은 경우에는 단계 618로 분기하여 메모리에 남은 씬 정보를 영구 저장장치(disk)에 저장한 후 종료하며, 상기 단계 613에서 현재 샷 번호(cur)가 τ_o이하인 경우에는 단계 616으로 분기하여 τ_o= cur-1로 설정한 후 단계 617에서 현재 샷 번호(cur)가 '0'인가를 판단하여 '0'이 아니면 단계 608로 분기하고 '0'이면 단계 618로 분기하여 메모리에 남은 씬 정보를 영구 저장장치에 저장한 후 종료한다.

한편, 클러스터링 프로세스가 단계 603으로 분기하면, 현재 샷 번호(cur)를 증가시키고, 해당 샷에 대한 단일 단절 씬/단일 레이블/단일 샷 구조를 메모리에 추가한다. 그리고 메모리 샷 리스트에서 새로이 검출된 샷(Shot_cur)과의 샷간 비유사도가 가장 작은 샷(Shot_min)을 찾는다. 여기서 찾은 최소 비유사도 샷(Shot_min)과의 샷간 비유사도 ShotDiff(Shot_cur, Shot_min)를 일정 임계치(τ_shotdiff)와 비교한다(단계 604).

최소 비유사도 샷(Shot_min)과의 샷간 비유사도 ShotDiff(Shot_cur, Shot_min)가 일정 임계치(τ_shotdiff) 보다 작으면 단계 605로 분기하여 샷(Shot_cur, Shot_min)간의 링크를 설정하고, 샷에 연결된 레이블 정보 및 씬 정보를 갱신하고, 그렇지 않으면 단계 606으로 분기하여 씬 경계를 검사할 필요가 있는지를 판단한다. 즉, 샷 개수(ShotNum)를 τ_o와 비교하여, 샷 경계 검출 단계 필요조건이 만족(ShotNum > τ_o)되면 클러스터링 프로세스는 단계 607로 분기하며, 그렇지 않으면 다시 단계 602로 분기하여 다음의 샷이 검출되기를 기다리거나 미디어에 대한 세그멘테이션 종료가 선언되기를 기다린다.

단계 607이후의 단계는 씬 경계를 검출하고 그에 따라 알맞은 오퍼레이션을 수행하는 단계이다. 먼저 단계 607에서 씬 경계 검출 대상의 두개의 샷에 대하여 연결 씬에 속하는지, 단절 씬에 속하는지의 여부와, 두개의 샷이 동일한 씬에 속하는지 다른 씬에 속하는지를 판단한 후, 이에 따라 각각의 경우(Case1, Case2,Case3-1, Case3-2)를 판단하고(단계 608), 단계 608에 의해 결정된 각각의 경우(Case)에 따라 단계 609로부터 각각의 오퍼레이션을 수행한다.

즉, 단계 607에서 L1=IsLinked(Shot_cur-τo-1), L2=IsLinked(Shot_cur-τo), bSame=ISSame(SceneOf(Shot_cur-τo-1),SceneOf(Shot_cur-τo))로 설정하고 그 다음 단계 608에서 L1,L2의 값(True or False)에 따라 각각의 경우(Case1, Case2, Case3-1, Case3-2)를 설정하며, 그 다음 단계(609)에서 어떤 경우인가를 판단하여 각 경우에 대한 오퍼레이션을 수행하는 것이다.

여기에서 경우에 따른 오퍼레이션을 살펴보면 다음과 같다.

먼저, 두개의 샷이 모두 단절 씬에 속하는 경우(Case1)에는 단계 610으로 분기하여 두개 샷 중에서 시간적으로 이전의 샷(Shot_cur-τo-1)이 속한 씬에 이후의 샷(Shot_cur-τo)을 포함시키며, 두개의 샷 중에서 하나는 단절 씬에, 하나는 연결 씬에 속하는 경우(Case2)에는 단계 611로 분기하여 두개의 샷(Shot_cur-τo, Shot_cur-τo-1)간에 씬 경계가 존재함을 선언하고, 단계 612로 분기하여 이전 샷(Shot_cur-τo-1)이 속한 씬의 정보를 디스크에 저장하고 그 샷(Shot_cur-τo-1)이 속한 해당 메모리를 해제한다.

두개의 샷이 모두 연결 씬에 속하고 두개의 샷이 속한 씬이 동일한 경우(Case3-1)에는 아무런 오퍼레이션을 수행하지 않으며, 두개의 샷이 모두 연결 씬에 속하고 각각의 샷이 속한 씬이 다른 경우(Case3-2)에는 단계 611로 분기하여두개의 샷(Shot_cur-τo, Shot_cur-τo-1)간에 씬 경계가 존재함을 선언하고, 단계 612로 분기하여 이전 샷(Shot_cur-τo-1)이 속한 씬의 정보를 디스크에 저장하고 해당 메모리를 해제한다.

이상의 경우에 따른 오퍼레이션이 모두 수행되면 본 발명의 프로세스는 단계 602로 분기하여 다음의 샷이 검출되기를 기다리거나 미디어에 대한 세그멘테이션 종료가 선언되기를 기다린다

도7a 및 도7b에서 (a) 내지 (l)은 본 발명 비디오 인덱싱 시스템의 알고리즘의 실행 예를 설명하기 위한 도면이다. 설명을 위하여 샷간의 비유사도 검사를 위한 오프셋을 '5'라 가정한다. 도7을 이용하여 단계별로 알고리즘의 적용을 살펴보면 다음과 같다.

도7a, 7b에서 A,B,C,...는 샷, 샷 아래에 표기된 일련번호 1,2,3,..는 샷 번호, L은 링크를 표현하고 있으며, 앞서 기술한 매치 윈도우를 각각 표기하였다.

[a] Shot₁이 입력된 경우(도7a에서 단계 a)

이전의 샷이 없으므로 링크를 설정하거나 씬 경계 검사 작업을 할 필요가 없다. 이 샷에 대한 정보는 단일씬/단일 레이블/단일 샷 정보로 추가되며, 메모리에는 총 1개의 단절 씬이 존재한다.

[b] Shot₂가 입력된 경우(도7a에서 단계 b)

이 경우는 매치 윈도우 내에 매치된 샷이 없으므로 단일씬/단일 레이블/단일 샷 정보로 추가되며, 메모리에는 총 2개의 단절 씬이 존재하고, 씬 경계 검사 작업을 할 필요가 없다.

[c] Shot₃이 입력된 경우(도7a에서 단계 c)

이 경우에도 매치 윈도우 내에 매치된 샷이 없으므로 단일씬/단일 레이블/단일 샷 정보로 추가되며, 메모리에는 총 3개의 단절 씬이 존재하고, 씬 경계 검사 작업을 할 필요가 없다.

[d] Shot₄가 입력된 경우(도7a에서 단계 d)

이 경우에는 매치 윈도우 내에 매치된 샷(Shot₁)이 있으므로 Shot₁~ Shot₄를 하나의 씬으로 등록하고 이를 연결 씬으로 표시하며(링크 설정), 메모리에는 총 1개의 연결 씬(Shot₁~ Shot₄)이 존재하게 되고, 씬 경계 검사 작업을 할 필요가 없다. 즉, 연결 씬에 3개의 레이블이 존재한다(A,B,C).

[e] Shot₅가 입력된 경우(도7a에서 단계 e)

이 경우에도 매치 윈도우 내에 매치된 샷(Shot₃)이 있으므로 Shot₃~ Shot₅가 하나의 씬에 존재하며, 여기서 이전에 Shot₁~ Shot₄가 하나의 씬으로 이미 등록이 되어 있으므로 Shot₁~ Shot₅를 하나의 씬으로 등록한다. 그리고 메모리에는 총 1개의 연결 씬(Shot₁~ Shot₅)이 존재하게 되며 씬 경계 검사 작업을 할 필요가 없다. 결과는 연결 씬에 3개의 레이블이 존재한다(A,B,C).

[f] Shot₆이 입력된 경우(도7a에서 단계 f)

이 경우에는 매치 윈도우 내에 매치된 샷이 없으므로 단일씬/단일 레이블/단일 샷 정보로 추가하고, 메모리에는 총 1개의 연결 씬(Shot₁~ Shot₅)과 총 1개의 단절 씬(Shot₆)이 존재하며, 씬 경계 검사 작업을 할 필요가 없다.

[g] Shot₇이 입력된 경우(도7a에서 단계 g)

이 경우에는 매치 윈도우 내에 매치된 샷이 없으므로 단일씬/단일 레이블/단일 샷 정보로 추가하고, 두개의 샷(Shot₁과 Shot₂)사이의 씬경계 검사를 하는데, 두개의 샷 모두 동일한 연결 씬에 속해 있으며 두개의 샷이 속해 있는 씬이 같으므로 씬경계 검사 결과의 오퍼레이션이 없다. 즉, 앞서 기술한 경우(Case3-1)에 해당한다. 그리고 메모리에는 총 1개의 연결 씬(Shot₁~ Shot₅)과 총 2개의 단절 씬(Shot₆, Shot₇)이 존재한다.

[h] 샷8(Shot₈), 샷9(Shot₉)가 입력되고, Shot₁₀이 입력된 경우(도7b에서 단계 h)

이 경우 매치 윈도우 내에 매치된 샷이 없으므로 단일씬/단일 레이블/단일 샷 정보로 추가하고, Shot₄와 Shot₅사이의 씬경계 검사가 필요하며, 상기 두개의 샷 모두 동일한 연결 씬에 속해 있으며 두개의 샷이 속해 있는 씬이 같으므로 씬경계 검사 결과의 오퍼레이션이 없다(Case3-1). 메모리에는 총 1개의 연결 씬(Shot₁~ Shot₅)과 총 5개의 단절 씬(Shot₆~ Shot₁₀)이 존재하게 된다.

[i] Shot₁₁이 입력된 경우(도7b에서 단계 i)

이 경우 매치 윈도우 내에 매치된 샷이 없으므로 단일씬/단일 레이블/단일 샷 정보로 추가하고, Shot₅와 Shot₆사이의 씬경계 검사가 이루어져서, Shot₅가 연결 씬에 속해 있으며 Shot₆이 단절 씬에 속해 있으므로(Case2) 씬 경계를 선언한다. 그리고 씬 경계 선언 후 Shot₁~Shot₅가 속한 씬에 대한 정보를 디스크에 저장(Write to disk)하고 Shot₁~Shot₅가 속한 씬에 대한 메모리 정보 해제가 이루어지며, 메모리에는 총 6개의 단절 씬((Shot₆~ Shot₁₁)이 존재한다.

[j] Shot₁₂가 입력된 경우(도7b에서 단계 j)

이 경우 매치 윈도우 내에 매치된 샷이 없으므로 단일씬/단일 레이블/단일 샷 정보로 추가하고, Shot₆과 Shot₇사이의 씬경계 검사가 이루어지는데, Shot₆과 Shot₇이 모두 단절 씬에 속해 있으므로(Case1) Shot₆이 속한 씬에 Shot₇의 정보를 추가(Merge)하며, 메모리에는 총 6개의 단절 씬(Shot₆+ Shot₇, (Shot₈~ Shot₁₂)이 존재하게 된다.

[k] Shot₁₃이 입력된 경우(도7b에서 단계 k)

이 경우에는 매치 윈도우 내에 매치된 샷(Shot₉)이 있으므로 Shot₉~ Shot₁₃를 하나의 씬으로 등록하고 이를 연결 씬으로 표시하며, Shot₇과 Shot₈사이의 씬경계검사를 하는데, Shot₇과 Shot₈이 모두 단절 씬에 속해 있으므로(Case1) Shot₇이 속한 씬에 Shot₈의 정보를 추가하고, 메모리에는 총 1개의 단절 씬(Shot₆~Shot₈의 머지)과 총 1개의 연결 씬(Shot₉~Shot₁₃)이 존재한다.

[l] Shot₁₄가 입력된 경우(도7b에서 단계 l)

이 경우에는 매치 윈도우 내에 매치된 샷(Shot₁₁)이 있으므로 Shot₁₁~ Shot₁₄가 하나의 씬에 존재하는데, 여기서 이전에 Shot₉~ Shot₁₃가 하나의 씬으로 등록이 되어 있으므로 Shot₉~ Shot₁₄를 하나의 씬으로 등록한다. 그리고 Shot₈과 Shot₉사이의 씬경계 검사가 이루어지며, Shot₈이 단절 씬에 속해 있고 Shot₉가 연결 씬에 속해 있으므로(Case2) 씬 경계를 선언한다. 씬 경계 선언후 Shot₆~Shot₈이 속한 씬에 대한 정보를 디스크에 저장하고 Shot₆~Shot₈이 속한 씬에 대한 메모리 정보를 해제하며, 그 결과 메모리에는 총 1개의 연결 씬(Shot₉~ Shot₁₄) 존재하게 된다.

지금까지 설명한 본 발명에서 제안된 비디오 인덱싱 알고리즘을 이용하면 인덱스 구조가 파일(file)에 저장되는데, 도8은 본 발명의 알고리즘 수행 결과로 얻어지는 구조적 정보가 표현된 인덱스 구조를 도식화 한 것이다.

콘텐트의 구조적 정보(Content Description)(80)는 씬의 리스트(List of Scene)(Scene₁, Scene₂,..., Scene_k, Scene_k+1)(81)로 정의되며, 각각의 씬은 구간정보[Start_k, End_k], 씬 종류 플래그 즉, 연결 씬/단절 씬(Linked/Broken), 하위 샷들의 리스트(List of Shot), 레이블 리스트(List of Label), 키프레임 리스트(List of KFs)로 표현되며, 키프레임 리스트는 경우에 따라 생략될 수 있다.

씬의 구간 정보는 해당 씬의 미디어 상에서의 시작시간 정보(Start_k)와 종료시간 정보(End_k)를 가리키며, 씬 종류 플래그는 연결 씬(Linked)인지 단절 씬(Broken)인지를 표현하기 위한 플래그이다. 하위 샷들의 리스트(List of Shot)는 씬에 속한 샷들의 리스트를 의미하며, 레이블 리스트(List of Label)는 샷 클러스터링 프로세스에 의해 추출된 레이블의 정보들을 표현하기 위한 리스트이다.

샷 리스트(List of Shot)의 구성요소는 개별 샷(S₀ ^k, S₁ ^k, S₂ ^k,...,S_m ^k)(84)이며, 레이블 리스트(List of Label)의 구성 요소는 레이블(L₀ ^k, L₁ ^k, L₂ ^k,...,L_n ^k)(2)이다. 샷 정보(85)는 구간정보(예: Start₂ ^k, End₂ ^k) 및 해당 키프레임(Shot KF)으로 정의되며 키프레임 정보(Shot KF)는 생략이 가능하다. 또한 레이블의 정보(83)는 해당 샷리스트(List of Shot) 및 키프레임(Label KF)으로 정의되며 여기서도 키프레임 정보는 생략 가능하다. 레이블의 샷리스트에는 샷 클러스터링 프로세스에서 해당 레이블를 할당받은 샷 정보들(예: S₁ ^k, S₅ ^k, S₈ ^k,...)이 기술된다. 본 발명의 알고리즘은 레이블 및 씬에 대한 키프레임을 할당 할 수 있도록 한다. 레이블 및 씬에 대한 키프레임 할당 작업은 본 알고리즘의 제 4단계에서 수행된다.

상기 레이블 정보는 비디오 스키밍과 같은 응용에 있어서 전체 내용을 빠른시간 안에 요약하여 브라우징이 가능하게 하기 위한 자료구조이며, 씬 키프레임과 레이블 키프레임은 콘텐트를 구조적으로 요약하기 위한 자료 구조이다.

이와 같이 샷에 대한 레이블 정보가 있으면, 동일한 레이블에 속한 샷을 되도록 재생하지 않음으로써 보다 함축적인 비디오 스키밍 시스템을 구성할 수 있으며, 레이블의 키프레임으로부터 씬 키프레임을 선택하게 되면, 비슷한 장면에서 씬 키프레임이 추출되는 것을 막을 수 있다.

또한 연결 씬은 주로 대화 장면이나 드라마에서 등장 인물간의 상호 작용이 반복적으로 표현되는 장면에 주로 사용되는 씬 구조이며, 단절 씬은 주로 빠른 이야기 전개나 요약, 액션 장면 등에 주로 사용되는 의미적 정보를 담고 있으므로 본 발명의 자료구조는 키프레임 요약이나 스키밍에서 각기 단절 씬인지 연결 씬인지에 따라서 각기 다른 키프레임 요약을 제공하거나, 각기 다른 세그먼트 재생 방법을 적용할 수 있게 하여 보다 진보된 형태의 비 선형적 비디오 브라우징을 가능하게 한다. 따라서 본 발명의 인덱스 자료구조를 이용하면 레이블 정보가 함께 제공되지 않는 비디오 인덱싱 시스템이나 알고리즘에 비하여 보다 높은 수준의 비 선형적 비디오 브라우징을 가능하게 한다.

도9는 본 발명 구조적 정보 추출이 가능하며 제한된 메모리를 사용하는 진행형 비디오 인덱싱 시스템의 구성을 보여준다.

도9에 나타낸 본 발명의 인덱싱 시스템은, 외부입력과 클러스터링 상황에 따라 비디오 인덱싱을 수행하기 위한 클러스터링 제어부(91), 클러스터링 제어부에 의해 씬 경계 검출을 판단하는 기능을 위한 씬 경계 검출부(92), 샷 클러스러링 알고리즘에서 두개의 샷간의 비유사도를 측정하고 이를 바탕으로 링크를 설정하고 메모리의 씬/레이블/샷 정보를 갱신하는 작업을 하는 링크 설정기(93), 샷 인덱스 결정기로부터 입력되는 샷 인덱스를 관리하고 이를 클러스터링 제어부에 알리는 샷 인덱스 입력부(94), 샷인덱스 입력부로부터 입력되는 샷 인덱스와, 링크 설정기, 씬 경계 검출부로부터 생성되고 업데이트 되는 씬/레이블 인덱스를 관리하고 클러스터링 제어부의 제어 신호에 따라 필요한 경우, 영구 저장 장치인 디스크에 인덱스 정보를 기록하는 일을 담당하는 인덱스 관리부(95), 상기 인덱스 관리부(95)에 의해서 관리되는 인덱스 파일(96), 미디어 파일에서 샷 정보를 추출하기 위한 샷 인덱스 결정기(97), 샷 인덱스 추출을 위하여 미디어 파일을 전체적으로 디코딩 하지 않고 부분적으로 디코딩하여 세그멘테이션과 클러스터링 작업을 위한 특징소를 추출하는 특징소 추출부(98), 상기 특징소 추출부에 미디어 파일을 제공하기 위한 비디오 스트림(99)으로 이루어진다.

특징소 추출부(98)는 비디오 인덱싱 시스템이 인덱싱하고자 하는 미디어에 대한 정보를 클러스터링 제어부(91)로부터 받아 비디오 인덱싱에 필요한 특징소들을 비디오 스트림(99)으로부터 추출하고 해당 데이터가 준비되면 샷 인덱스 결정기(97)로 데이터를 전송한다.

샷 인덱스 결정기(97)는 클러스터링 제어부(91)로부터 샷 인덱스 추출 명령을 받아 특징소 추출부(98)를 이용하여 필요한 정보를 추출하고 이를 샷 인덱스 입력부(94)로 전달한다. 이때 샷 인덱스 결정기(97)는 새로운 샷이 검출될 때마다, 또는 미디어에 대한 샷 세그멘테이션이 종료될 때 이를 샷인덱스 입력부(94)에 알려준다.

샷 인덱스 입력부(94)는 새로운 샷이 입력되면 인덱스 관리부(95)에 새로운 샷을 등록한 후 클러스터링 제어부(91)에 이를 알려주며, 샷 세그멘테이션이 종료된 경우도 종료되었음을 클러스터링 제어부(91)에 알려준다.

클러스터링 제어부(91)는 샷 인덱스 입력부(94)로부터 입력되는 샷에 대한 정보를 바탕으로 링크 설정기(93)를 통하여 링크를 설정하고 인덱스 관리부(95)가 관리하는 씬/레이블/샷 정보를 갱신하고, 씬 경계 검출부(92)를 제어하여 씬 경계가 발생하였는지를 검사하고, 씬경계 검사 지점에 대한 머지(Merge), 경계 선언 등의 오퍼레이션을 수행하여 메모리의 씬/레이블/씬 간의 정보를 인덱스 관리부(95)를 통하여 갱신하도록 제어하고, 씬 경계 검출부(92)로부터 씬 경계 선언이 발생한 경우에 다시 인덱스 관리부(95)를 이용하여, 씬 경계가 선언된 씬에 대한 정보를 영구 저장장치에 저장할 수 있도록 하는 제어를 담당한다.

여기에서 인덱스 관리부(95)는 씬 경계가 선언될 때마다 확정된 씬 정보를 디스크에 기록할 수 도 있으며, 일정량 이상 씬 정보가 추출된 후에 씬 정보를 한꺼번에 디스크에 저장하는 시스템을 이용할 수도 있다. 디스크에 저장된 씬 정보에 대한 메모리 구조는 인덱스 관리부(95)의 제어에 의해 해제 될 수 있다.

이러한 시스템을 이용하면, 멀티미디어 스트림에 대한 구조적 정보를 진행형 알고리즘을 이용하여 추출할 수 있다. 즉, 샷 세그멘테이션이 진행되면서 몇 개의샷에 대한 판단 지연(Delay)은 있지만, 이에 대한 최대값을 확정하여 줌으로써 실시간 시스템에 응용이 가능하며, 미디어에 대한 샷 세그멘테이션이 종료됨과 거의 동시에 구조적 정보에 대한 인덱싱이 완료된다

본 발명의 비디오 인덱싱 시스템과 비디오 인덱싱 방법 및 그 구조를 이용하면, 미디어로부터 샷 인덱스와 씬 인덱스, 그리고 하나의 씬 내에서의 샷들의 반복 정보 등을 포함하는 구조적 정보를 한꺼번에 추출할 수 있다. 또한 본 발명의 알고리즘과 시스템은 진행형 알고리즘을 특징으로 하며, 수행속도가 매우 빠르며 소량의 메모리만을 요구하므로 방송국이나 VOD서버와 같은 비디오 아카이브(Video Archive)는 물론 PVR과 같은 실시간 처리 셋탑박스 시스템의 인덱싱 시스템으로 활용될 수 있다. 또한 본 발명은 씬/샷 간의 관계뿐만 아니라 씬과 레이블의 관계, 레이블과 샷간의 관계를 동시에 추출함으로써 비디오 콘텐트에 대한 키프레임 요약이나, 비디오 스키밍, 자동 하이라이트 생성에 있어서 레이블 정보가 제공되지 않는 기타의 클러스터링 시스템에 비하여 더 많은 정보를 제공한다. 따라서 본 발명의 인덱싱 알고리즘과 시스템은 비 선형적인 비디오 브라우징을 위한 모든 인덱싱 시스템에 적용이 가능하다.

Claims

샷 세그멘테이션과 샷 클러스터링을 동시에 수행하여 멀티미디어 콘텐트에 대한 씬/샷/레이블에 대한 정보와 그들 간의 연관관계를 기술하는 인덱스 정보를 추출하는 것을 특징으로 하며,

비디오 콘텐트에서 샷 정보로 신규 샷(Shot_cur) 및 샷 히스토그램을 추출하는 단계와;

상기 추출된 샷 정보를 이용해서 샷간의 비유사도를 기반으로 샷간 링크를 설정하고 링크가 설정된 씬을 연결 씬으로 등록하고 씬, 레이블, 샷간의 연관 관계 정보를 설정하는 단계와;

현재의 샷(Shot_cur)에서 매치 윈도우 크기만큼 떨어져 있는 샷(Shot_cur-τo)과 그 이전의 샷(Shot_cur-τo-1)이 각각 단절 씬에 속한 것인지 혹은 연결 씬에 속한 것인지에 대한 정보와, 상기 각각의 샷이 속한 씬들이 동일한지 혹은 다른지에 따라, 상기 두개의 샷(Shot_cur-τo, Shot_cur-τo-1)이 속해 있는 씬끼리의 통합(merge)을 하거나, 씬 경계 선언을 하는 단계와;

상기 통합되거나 경계가 선언된 씬 정보를 저장하는 단계; 를 포함하여 이루어지는 것을 특징으로 하는 진행형 비디오 인덱싱 방법.
제 1 항에 있어서, 상기 비유사도의 측정은 상기 샷(Shot_cur)에 대하여 매치 윈도우내의 샷간의 비유사도를 측정하며, 측정된 비유사도를 이용해서 최소의 비유사도를 갖는 샷(Shot_min)을 검출한 후, 해당 비유사도가 특정 임계치 이하이면 샷간의 링크를 설정하고 링크가 설정된 씬을 연결 씬으로 등록하는 것을 특징으로 하는 진행형 비디오 인덱싱 방법.
제 1 항에 있어서, 상기 씬은 하나 이상의 연속된 샷의 시퀀스로 정의되고, 상기 레이블은 씬 내에서 샷 간의 비 유사도가 특정 임계치(τ_shotdiff)이하인 샷들의 시퀀스로 정의되며, 하나의 레이블은 한 개 이상의 샷을 포함하는 것을 특징으로 하는 진행형 비디오 인덱싱 방법.
제 1 항에 있어서, 상기 씬은 레이블의 리스트로 표현되며, 레이블은 샷의 리스트로 표현되는 것을 특징으로 하는 진행형 비디오 인덱싱 방법.
제 1 항에 있어서, 상기 연결 씬은 씬 내에 두개 이상의 샷을 구성 요소로 가지는 레이블이 존재하는 씬임을 의미하고, 단절 씬은 씬 내에 두개 이상의 샷을 구성 요소로 가지는 레이블이 존재하지 않는 씬을 의미하는 것을 특징으로 하는 진행형 비디오 인덱싱 방법.
제 1 항에 있어서, 상기 매치 윈도우는 현재의 샷(Shot_cur)이 검출된 시점으로부터 이전의 몇 개의 샷 오프셋(τ_o) 이내에 존재하는 샷들이 시간 순서로 배열된 FIFO 구조로 이루어지는 것을 특징으로 하는 진행형 비디오 인덱싱 방법.
제 1 항에 있어서, 상기 새로이 입력된 샷(Shot_cur)에 대하여 단일 씬과 단일 레이블, 단일 샷 정보를 추가하고, 이에 대한 링크 설정 작업을 통하여 새로이 입력된 단일 씬/단일 레이블/단일 샷 정보를 갱신하는 것을 특징으로 하는 진행형 비디오 인덱싱 방법.
제 1 항에 있어서, 상기샷(Shot _cur )과 최소의 비유사도를 갖는 샷(Shot_min)간의 링크를 구성하는 경우에는 두개의 샷에 동일한 레이블을 할당하여 레이블 정보를 갱신하고, 두개의 샷이 포함된 씬들을 통합(merge)하며, 새로운 샷이 추가된 씬을 연결 씬으로 표기하여 씬 정보를 갱신하고, 링크가 구성되지 않는 경우에는 새로운 단절 씬에 새로운 레이블을 할당하고 거기에 기준 샷을 할당한 정보를 기록하는 것을 특징으로 하는 진행형 비디오 인덱싱 방법.
제 1 항에 있어서, 상기 현재의 샷(Shot_cur)에서 매치 윈도우 크기만큼 떨어져 있는 샷(Shot_cur-τo)과 그 이전의 샷(Shot_cur-τo-1)에 대하여 각각의 샷이 속한 씬이 연결 씬인지 단절 씬인지를 파악하고, 두 샷(Shot_cur-τo와 Shot_cur-τo-1)이 속한 씬이 동일한 씬인지 다른 씬인지를 판단하여, 두개의 샷이 모두 단절 씬에 속한 경우에는 샷(Shot_cur-τo-1)이 속한 씬 정보에 샷(Shot_cur-τo)이 속한 씬을 통합(merge)하고, 두개의 샷 중에서 하나는 단절씬에 속하고 나머지 하나는 연결 씬에 속한 경우에는 씬 경계가 발생하였음을 선언하고 샷(Shot_cur-τo-1)이 속한 씬 정보를 저장장치에 저장 가능한 상태로 변경하며, 두개의 샷이 모두 연결 씬에 속하고 두개의 샷이 속한 씬이 동일할 경우에는 아무런 동작을 하지 않고, 두개의 샷이 모두 연결 씬에 속하고 두개의 샷이 속한 씬이 다른 경우에는 씬 경계가 발생하였음을 선언하고 샷(Shot_cur-τo-1)이 속한 씬 정보를 저장장치에 저장 가능한 상태로 변경하는 것을 특징으로 하는 진행형 비디오 인덱싱 방법.
제 1 항에 있어서, 상기 씬통합 또는 씬 경계 선언 후에 그 씬 정보를 저장함에 있어, 신규 확정 씬이 등록될 때마다 영구 저장 장치에 저장하는 정책을 사용하는 경우에는 신규 확정 씬에 대한 씬 정보를 저장장치에 저장하고; 일정량 이상의 확정 씬 정보가 채워진 이후에 한꺼번에 저장하는 정책을 사용하는 경우에는 신규 확정 씬 정보가 일정량 이상 등록된 경우에만 확정 씬들에 대한 정보를 저장장치에 저장하며, 신규 확정 씬 정보가 없는 경우에는 상기 샷 정보 추출단계로 분기하는 것을 특징으로 하는 진행형 비디오 인덱싱 방법.
외부입력과 클러스터링 상황에 따라 비디오 인덱싱을 수행하기 위한 클러스터링 제어수단과;

클러스터링제어수단에 의해 씬 경계 검출 판단을 위한 씬 경계 검출수단과;

샷 클러스러링 알고리즘에서 두개의 샷 의 비유사도를 측정하고 이를 바탕으로 하여 링크를 설정하고 메모리의 씬/레이블/샷 정보를 갱신하는 작업을 하는 링크 설정수단과;

미디어 파일에서 샷 정보를 추출하기 위한 샷 인덱스 결정수단과;

샷 인덱스 추출을 위하여 미디어 파일을 디코딩하여 세그멘테이션과 클러스터링 작업을 위한 특징소를 추출하는 특징소 추출수단과;

샷 인덱스 결정수단으로부터 입력되는 샷 인덱스를 관리하고 이를 클러스터링 제어수단에 알리는 샷 인덱스 입력수단과;

샷 인덱스 입력수단으로부터 입력되는 샷 인덱스와, 링크 설정수단, 씬 경계 검출수단으로부터 생성되고 갱신되는 씬/레이블 인덱스를 관리하고 클러스터링 제어수단의 제어 신호에 따라 필요한 경우 저장 장치에 인덱스 정보를 기록하는 일을 담당하는 인덴스 관리수단;

을 포함하여 샷 세그멘테이션과 샷 클러스터링을 동시에 수행하여 멀티미디어 콘텐트에 대한 씬/샷/레이블에 대한 정보와 그들 간의 연관관계를 기술한 구조적 인덱스 정보를 추출하는 것을 특징으로 하는 진행형 비디오 인덱싱 시스템.
제 11 항에 있어서, 상기 특징소 추출수단은 비디오 인덱싱 시스템이 인덱싱하고자 하는 미디어에 대한 정보를 클러스터링 제어수단으로부터 받아 비디오 인덱싱에 필요한 특징소들을 추출하고 해당 데이터가 준비되면 샷 인덱스 결정수단으로데이터를 전송하는 것을 특징으로 하는 진행형 비디오 인덱싱 시스템.
제 11 항에 있어서, 상기 샷 인덱스 결정수단은 클러스터링 제어수단으로부터 샷 인덱스 추출 명령을 받아 특징소 추출수단을 이용하여 필요한 정보를 추출하고 이를 샷 인덱스 입력수단으로 전달하며, 새로운 샷이 검출될 때마다 또는 미디어에 대한 샷 세그멘테이션이 종료될 때 이를 샷인덱스 입력수단에 알리는 것을 특징으로 하는 진행형 비디오 인덱싱 시스템.
제 11 항에 있어서, 상기 샷 인덱스 입력수단은 새로운 샷이 입력되면 인덱스 관리수단에 새로운 샷을 등록한 후 클러스터링 제어수단에 이를 알리며, 샷 세그멘테이션이 종료된 경우도 종료되었음을 클러스터링 제어수단에 알리는 것을 특징으로 하는 진행형 비디오 인덱싱 시스템.
제 11 항에 있어서, 상기 클러스터링 제어수단은 샷 인덱스 결정수단으로부터 입력되는 샷에 대한 정보를 바탕으로 링크 설정수단을 통하여 링크를 설정하고 인덱스 관리수단이 관리하는 씬/레이블/샷 정보를 갱신하며, 씬 경계 검출수단을 제어하여 씬 경계가 발생하였는지를 검사하고, 씬경계 검사지점에 대한 통합(merge), 경계 선언 등의 오퍼레이션을 수행하여 메모리의 씬/레이블/씬 간의 정보를 인덱스 관리수단을 통하여 갱신하도록 제어하고, 씬 경계 검출수단으로부터 씬 경계 선언이 발생한 경우에 다시 인덱스 관리수단을 이용하여, 씬 경계가 선언된 씬에 대한 정보를 저장장치에 저장할 수 있도록 제어하는 것을 특징으로 하는 진행형 비디오 인덱싱 시스템.
제 11 항에 있어서, 상기 인덱스 관리수단은 저장 정책에 따라 씬 경계가 선언될 때마다 확정된 씬 정보를 저장장치에 저장하거나, 일정량 이상 씬 정보가 추출된 후에 씬 정보를 한꺼번에 저장하고 저장된 씬 정보에 대한 메모리 구조를 자동 해제하는 것을 특징으로 하는 진행형 비디오 인덱싱 시스템.
멀티미디어 콘텐트를 ;

하나 이상의 샷들의 연속적인 시퀀스인 씬들의 리스트로 정의하고,

각각의 씬을 시작 시점과 종료 시점을 포함하는 구간 정보와,

씬에 속한 하나 이상의 샷들을 저장하기 위한 샷 리스트 정보와,

씬에 속한 하나 이상의 레이블을 저장하기 위한 레이블 리스트 정보와,

연결 씬인지 단절 씬인지를 지정하는 플래그 정보를 포함하여 기술하는 것을 특징으로 하는 멀티미디어 스트림에 대한 구조적 인덱스 정보 기술 방법.
제 17 항에 있어서, 상기 샷 리스트의 구성 요소는 개별 샷이며, 샷 정보는 시작 시점과 종료 시점을 포함하는 구간 정보를 이용하여 기술되는 것을 특징으로 하는 멀티미디어 스트림에 대한 구조적 인덱스 정보 기술 방법.
제 17 항에 있어서, 상기 샷 리스트의 구성요소는 개별 샷이며, 샷 정보는 시작 시점과 종료 시점을 포함하는 구간정보 및, 샷에 대한 키프레임 정보를 포함하여 기술되는 것을 특징으로 하는 멀티미디어 스트림에 대한 구조적 인덱스 정보 기술 방법.
제 17 항에 있어서, 상기 레이블 리스트의 구성 요소는 개별 레이블이며, 레이블 정보는 씬내에서 해당 레이블을 할당받은 샷들의 리스트임을 특징으로 하는 멀티미디어 스트림에 대한 구조적 인덱스 정보 기술 방법.
제 17 항에 있어서, 상기 레이블 리스트의 구성 요소는 개별 레이블이며, 레이블 정보는 씬내에서 해당 레이블을 할당받은 샷들의 리스트와 레이블에 대한 키프레임 정보를 포함하여 기술되는 것을 특징으로 하는 멀티미디어 스트림에 대한 구조적 인덱스 정보 기술 방법.
제 17 항에 있어서, 상기 씬 정보는 씬을 대표하기 위한 키프레임 정보를 더 포함하여 기술되는 것을 특징으로 하는 멀티미디어 스트림에 대한 구조적 인덱스 정보 기술 방법.