KR20150130078A

KR20150130078A - 신장 트리 생성 방법 및 장치，스테레오 매칭 방법 및 장치，업 샘플링 방법 및 장치，및 기준 픽셀 생성 방법 및 장치

Info

Publication number: KR20150130078A
Application number: KR1020140057176A
Authority: KR
Inventors: 최욱; 남동경; 이기창
Original assignee: 삼성전자주식회사
Priority date: 2014-05-13
Filing date: 2014-05-13
Publication date: 2015-11-23
Anticipated expiration: 2034-05-13
Also published as: US9401022B2; CN105100768B; EP2947626A1; KR102240570B1; US20150332447A1; CN105100768A; EP2947626B1

Abstract

신장 트리 생성 방법 및 장치, 스테레오 매칭 방법 및 장치, 업 샘플링 방법 및 장치, 및 기준 픽셀 생성 방법 및 장치가 개시된다. 일 실시예에 따르면 기준 픽셀들에 기초하여 신장 트리가 생성될 수 있다. 또한, 생성된 신장 트리에 기초하여 스테레오 매칭 또는 업 샘플링이 수행될 수 있다. 또한, 스테레오 비디오에 기초하여 기준 픽셀이 생성될 수 있다.

Description

신장 트리 생성 방법 및 장치，스테레오 매칭 방법 및 장치，업 샘플링 방법 및 장치，및 기준 픽셀 생성 방법 및 장치{METHOD AND APPARATUS FOR GENERATING SPANNING TREE，METHOD AND APPARATUS FOR STEREO MATCHING，METHOD AND APPARATUS FOR UP-SAMPLING，AND METHOD AND APPARATUS FOR GENERATING REFERENCE PIXEL}

아래 실시예들은 신장 트리 생성 방법 및 장치, 스테레오 매칭 방법 및 장치, 업 샘플링 방법 및 장치, 및 기준 픽셀 생성 방법 및 장치에 관한 것이다.

일반적으로 컴퓨터 비전이란 영상을 이용하여 정보를 얻어내는 기술을 말하며, 영상을 이용하여 거리 정보를 획득하는 기술을 스테레오 비전이라 한다.

스테레오 시스템에서는 카메라가 가로로 두 개 위치하므로, 좌영상과 우영상의 대응점을 찾는 것이 중요한데, 이를 스테레오 매칭이라 한다. 가장 기본적인 스테레오 매칭 기법은 우영상의 모든 픽셀에서 좌영상의 픽셀을 비교함으로써 가장 유사한 대응점을 찾을 수 있다. 이러한 대응점을 구하면 거리를 결정할 수 있다.

일 측에 따른 신장 트리 생성 방법은 입력 영상을 위한 기준 픽셀들에 대한 정보를 수신하는 단계; 및 상기 기준 픽셀들에 대한 정보에 기초하여, 상기 입력 영상에 포함된 픽셀들을 연결하는 신장 트리를 생성하는 단계를 포함한다. 상기 기준 픽셀들은 상기 입력 영상에 포함된 일반 픽셀들에 비하여 추가 정보를 더 포함할 수 있다.

상기 일반 픽셀들 각각은 인텐시티(intensity) 정보 및 위치 정보 중 적어도 하나를 포함할 수 있다. 상기 추가 정보는 시차(disparity) 정보 및 깊이(depth) 정보 중 적어도 하나를 포함할 수 있다.

상기 신장 트리는 상기 입력 영상에 포함된 픽셀들을 최소 비용으로 연결하는 최소 신장 트리를 포함할 수 있다. 상기 신장 트리는 복수의 서브 트리들을 포함하고, 상기 복수의 서브 트리들 각각은 상호 연관성이 높은 픽셀들을 포함하며, 상기 복수의 서브 트리들은 페널티(penalty)가 부과된 에지로 연결될 수 있다.

상기 신장 트리를 생성하는 단계는 상기 기준 픽셀들이 루트 노드가 되도록 서브 트리들을 생성하는 단계; 및 상기 서브 트리들 사이의 에지 비용들을 조절함으로써, 상기 서브 트리들을 연결하는 단계를 포함할 수 있다.

다른 일 측에 따른 스테레오 매칭 방법은 스테레오 매칭을 위한 제1 입력 영상과 제2 입력 영상을 수신하는 단계; 상기 제1 입력 영상에 포함된 픽셀들을 연결하는 신장 트리를 획득하는 단계; 상기 픽셀들 중 일반 픽셀들의 데이터 비용들, 상기 픽셀들 중 기준 픽셀들의 데이터 비용들, 및 상기 신장 트리에 포함된 에지들의 에지 비용들에 기초하여, 상기 픽셀들 중 어느 하나의 픽셀을 위한 복수의 후보 시차들에 대응하는 축적 데이터 비용들을 계산하는 단계; 및 상기 축적 데이터 비용들을 비교함으로써, 상기 복수의 후보 시차들 중 어느 하나의 후보 시차를 상기 어느 하나의 픽셀의 시차(disparity)로 결정하는 단계를 포함한다.

또 다른 일 측에 따른 업 샘플링 방법은 입력 영상에 포함된 픽셀들을 연결하는 신장 트리를 획득하는 단계; 상기 픽셀들 중 기준 픽셀들의 데이터 비용들, 및 상기 신장 트리에 포함된 에지들의 에지 비용들에 기초하여, 상기 픽셀들 중 어느 하나의 픽셀을 위한 복수의 후보 깊이들에 대응하는 축적 데이터 비용들을 계산하는 단계; 및 상기 축적 데이터 비용들을 비교함으로써, 상기 복수의 후보 깊이들 중 어느 하나의 후보 깊이를 상기 어느 하나의 픽셀의 깊이로 결정하는 단계를 포함한다.

또 다른 일 측에 따른 기준 픽셀 생성 방법은 스테레오 비디오에 포함된 제1 영상 시퀀스 및 제2 영상 시퀀스를 추적하는 단계; 및 상기 제1 영상 시퀀스의 추적 결과, 상기 제2 영상 시퀀스의 추적 결과, 및 이전 프레임에서 스테레오 매칭된 결과에 기초하여, 현재 프레임을 위한 기준 픽셀들을 생성하는 단계를 포함한다.

또 다른 일 측에 따른 신장 트리 생성 장치는 입력 영상을 위한 기준 픽셀들에 대한 정보를 수신하는 수신부; 및 상기 기준 픽셀들에 대한 정보에 기초하여, 상기 입력 영상에 포함된 픽셀들을 연결하는 신장 트리를 생성하는 생성부를 포함한다.

또 다른 일 측에 따른 스테레오 매칭 장치는 스테레오 매칭을 위한 제1 입력 영상과 제2 입력 영상을 수신하는 수신부; 상기 제1 입력 영상에 포함된 픽셀들을 연결하는 신장 트리를 획득하는 획득부; 상기 픽셀들 중 일반 픽셀들의 데이터 비용들, 상기 픽셀들 중 기준 픽셀들의 데이터 비용들, 및 상기 신장 트리에 포함된 에지들의 에지 비용들에 기초하여, 상기 픽셀들 중 어느 하나의 픽셀을 위한 복수의 후보 시차들에 대응하는 축적 데이터 비용들을 계산하는 계산부; 및 상기 축적 데이터 비용들을 비교함으로써, 상기 복수의 후보 시차들 중 어느 하나의 후보 시차를 상기 어느 하나의 픽셀의 시차(disparity)로 결정하는 결정부를 포함한다.

또 다른 일 측에 따른 업 샘플링 장치는 입력 영상에 포함된 픽셀들을 연결하는 신장 트리를 획득하는 획득부; 상기 픽셀들 중 기준 픽셀들의 데이터 비용들, 및 상기 신장 트리에 포함된 에지들의 에지 비용들에 기초하여, 상기 픽셀들 중 어느 하나의 픽셀을 위한 복수의 후보 깊이들에 대응하는 축적 데이터 비용들을 계산하는 계산부; 및 상기 축적 데이터 비용들을 비교함으로써, 상기 복수의 후보 깊이들 중 어느 하나의 후보 깊이를 상기 어느 하나의 픽셀의 깊이로 결정하는 결정부를 포함한다.

또 다른 일 측에 따른 기준 픽셀 생성 장치는 스테레오 비디오에 포함된 제1 영상 시퀀스 및 제2 영상 시퀀스를 추적하는 추적부; 및 상기 제1 영상 시퀀스의 추적 결과, 상기 제2 영상 시퀀스의 추적 결과, 및 이전 프레임에서 스테레오 매칭된 결과에 기초하여, 현재 프레임을 위한 기준 픽셀들을 생성하는 생성부를 포함한다.

도 1은 일 실시예에 따른 기준 픽셀을 설명하는 도면.
도 2는 일 실시예에 따른 시차 정보를 포함하는 기준 픽셀들을 설명하는 도면.
도 3은 일 실시예에 따른 깊이 정보를 포함하는 기준 픽셀들을 설명하는 도면.
도 4 내지 도 16은 일 실시예에 따른 기준 픽셀을 이용한 신장 트리의 생성을 설명하는 도면들.
도 17 및 도 18은 일 실시예에 따른 신장 트리를 이용한 스테레오 매칭 또는 업 샘플링 동작을 설명하는 도면들.
도 19 및 도 20은 일 실시예에 따른 스테레오 비디오를 이용한 기준 픽셀의 생성을 설명하는 도면들.
도 21 내지 도 25는 실시예들에 따른 동작 흐름도.
도 26 내지 도 29는 실시예들에 따른 블록도.

이하, 실시예들을 첨부된 도면을 참조하여 상세하게 설명한다. 각 도면에 제시된 동일한 참조 부호는 동일한 부재를 나타낸다.

하기에서 설명될 실시예들은 스테레오 영상, 멀티-뷰 영상, 라이트 필드 영상, 또는 깊이 영상의 처리에 적용될 수 있고, 3차원 모델링 또는 유저 인터페이스 등에 사용될 수 있다.

일 실시예에 따른 기준 픽셀

도 1은 일 실시예에 따른 기준 픽셀을 설명하는 도면이다. 도 1을 참조하면, 일 실시예에 따른 영상(100)은 복수의 픽셀들을 포함한다. 복수의 픽셀들은 영상(100)을 표현하는 정보를 포함할 수 있다. 예를 들어, 영상(100)을 표현하는 정보는 인텐시티(intensity) 정보일 수 있다. 영상(100)이 색상 영상(color image)인 경우 복수의 픽셀들 각각은 (R, G, B) 정보를 포함할 수 있다.

영상(100)에 포함된 복수의 픽셀들 각각은 영상(100) 내 좌표로 식별될 수 있다. 이 때, 복수의 픽셀들 각각은 고유한 인덱스로 지시될 수 있다.

예를 들어, 영상(100)이 4 x 4 매트릭스 형태의 픽셀들을 포함하는 경우, 첫 번째 행의 첫 번째 열에 위치하는 픽셀은 인덱스 '1'로 지시되고, 첫 번째 행의 두 번째 열에 위치하는 픽셀은 인덱스 '2'로 지시되며, 첫 번째 행의 세 번째 열에 위치하는 픽셀은 인덱스 '3'으로 지시되고, 첫 번째 행의 네 번째 열에 위치하는 픽셀은 인덱스 '4'로 지시될 수 있다. 또한, 두 번째 행의 첫 번째 열에 위치하는 픽셀은 인덱스 '5'로 지시되고, 두 번째 행의 두 번째 열에 위치하는 픽셀은 인덱스 '6'으로 지시되며, 두 번째 행의 세 번째 열에 위치하는 픽셀은 인덱스 '7'로 지시되고, 두 번째 행의 네 번째 열에 위치하는 픽셀은 인덱스 '8'로 지시될 수 있다. 이 경우, 네 번째 행의 네 번째 열에 위치하는 픽셀은 인덱스 '16'으로 지시될 수 있다.

임의의 픽셀을 지시하는 인덱스는 해당 픽셀의 좌표와 1 대 1 대응되므로, 임의의 픽셀을 지시하는 인덱스는 해당 픽셀의 좌표로 용이하게 치환될 수 있다. 이러한 관점에서, 영상(100)에 포함된 복수의 픽셀들은 위치 정보를 포함할 수 있다.

영상(100)에 포함된 복수의 픽셀들 중 일부의 픽셀들은 나머지 픽셀들에 비하여 추가 정보를 더 포함할 수 있다. 예를 들어, 픽셀(110), 픽셀(120), 픽셀(130), 및 픽셀(140)은 다른 픽셀들에 비하여 추가 정보를 더 포함할 수 있다. 이하, 영상과 관련된 일반적인 정보만 포함하는 픽셀은 일반 픽셀이라고 지칭되고, 일반 픽셀에 비하여 추가 정보를 더 포함하는 픽셀은 기준 픽셀이라고 지칭될 수 있다. 여기서, 영상과 관련된 일반적인 정보는 인텐시티 정보 및 위치 정보일 수 있다.

추가 정보는 영상(100) 내 기준 픽셀의 위치에서 영상(100)을 추가적으로 표현하는 정보일 수 있다. 예를 들어, 픽셀(110), 픽셀(120), 픽셀(130), 및 픽셀(140)은 영상(100)에 포함된 기준 픽셀들로, 일반 픽셀들에 비하여 깊이(depth) 정보 또는 시차(disparity) 정보를 더 포함할 수 있다. 깊이 정보 및 시차 정보와 관련된 보다 상세한 사항은 후술하는 실시예들을 통하여 설명한다.

기준 픽셀들의 위치에 대응하는 추가 정보는 다양한 방식에 의하여 미리 주어질 수 있다. 예를 들어, 추가 정보는 기준 픽셀들의 위치에 대응하여 더 정확하고 더 복잡한 알고리즘을 수행함으로써 계산될 수 있다. 또는, 추가 정보는 더 효율적인 알고리즘을 수행하여 계산된 결과 중 신뢰성이 높은 결과를 추출함으로써 획득될 수 있다. 또는, 추가 정보는 기준 픽셀들의 위치에 대응하여 추가 정보를 측정하는 센서를 이용하여 획득될 수 있다. 또는, 영상이 연속하는 복수의 프레임들 중 어느 하나의 프레임에 해당하는 경우, 추가 정보는 이전 프레임의 정보에 기초하여 추정될 수 있다.

기준 픽셀들에 포함된 추가 정보는 영상(100)의 처리에 이용될 수 있다. 아래에서 상세히 설명하겠으나, 기준 픽셀들에 포함된 추가 정보를 이용하여 일반 픽셀들의 위치에 대응하는 추가 정보가 생성될 수 있다. 예를 들어, 기준 픽셀들을 이용하여 스테레오 매칭이 수행되거나, 기준 픽셀들을 이용하여 깊이 영상 업 샘플링이 수행될 수 있다. 스테레오 매칭 및 깊이 영상 업 샘플링과 관련된 보다 상세한 사항은 후술하는 실시예들을 통하여 설명한다.

도 2는 일 실시예에 따른 시차 정보를 포함하는 기준 픽셀들을 설명하는 도면이다. 도 2를 참조하면, 일 실시예에 따른 영상(200)은 스테레오 영상(stereo image)일 수 있다. 영상(200)은 왼쪽 눈에 대응하는 제1 영상(210)과 오른쪽 눈에 대응하는 제2 영상(220)을 포함한다.

영상(200)은 스테레오 카메라(stereo camera)에 의하여 생성될 수 있다. 스테레오 카메라는 사람의 양 눈과 같이 수평 방향으로 미리 정해진 거리만큼 이격된 두 개의 카메라들로 구성될 수 있다. 두 개의 카메라들은 동시에 동일한 장면(scene) 또는 동일한 대상(object)를 촬영할 수 있다. 왼쪽 눈에 대응하는 카메라는 왼쪽 눈에 대응하는 제1 영상(210)을 생성하고, 오른쪽 눈에 대응하는 카메라는 오른쪽 눈에 대응하는 제2 영상(220)을 생성할 수 있다.

이 때, 제1 영상(210) 및 제2 영상(220)에 포함된 복수의 픽셀들 중 일부의 픽셀의 위치에 대응하는 추가 정보가 미리 주어질 수 있다. 전술한 바와 같이 추가 정보가 미리 주어지는 일부의 픽셀은 기준 픽셀이라고 지칭될 수 있다. 예를 들어, 제1 영상(210)은 기준 픽셀(211), 기준 픽셀(212), 기준 픽셀(213), 및 기준 픽셀(214)를 포함하고, 제2 영상(220)은 기준 픽셀(221), 기준 픽셀(222), 기준 픽셀(223), 및 기준 픽셀(224)를 포함할 수 있다.

제1 영상(210)과 제2 영상(220)에 포함된 기준 픽셀들은 각각 시차 정보를 포함할 수 있다. 시차 정보는 양안 시차(binocular disparity)의 정도를 나타내는 정보일 수 있다. 시차 정보를 설명하기 위하여, 스테레오 영상을 처리하는 기법 중 스테레오 매칭(stereo matching) 기법을 간략히 설명한다.

스테레오 매칭 기법은 왼쪽 눈에 대응하는 영상과 오른쪽 눈에 대응하는 영상을 서로 매칭하는 기법이다. 왼쪽 눈에 대응하는 영상과 오른쪽 눈에 대응하는 영상은 동일한 장면 또는 동일한 객체를 동시에 촬영함으로써 얻어지므로, 왼쪽 눈에 대응하는 영상에 포함된 적어도 일부의 픽셀들은 오른쪽 눈에 대응하는 영상에 포함된 적어도 일부의 픽셀들에 매칭될 수 있다. 매칭되는 두 픽셀들은 실제 장면 또는 실제 객체의 동일한 포인트에 대응될 수 있다.

스테레오 영상이 수평적으로 평행하게 설치된 두 개의 카메라들에 의하여 생성된다고 가정하면, 매칭되는 두 픽셀들은 y축 방향으로는 동일한 좌표 값을 가지고, x축 방향으로 상이한 좌표 값을 가질 수 있다. 이 때, 매칭되는 두 픽셀들의 x축 좌표 값들의 차이는 양안 시차의 정도를 나타낼 수 있다.

제1 영상(210)에 포함된 기준 픽셀(211)은 제2 영상(220)에 포함된 기준 픽셀(221)에 매칭될 수 있다. 이 경우, 기준 픽셀(211)의 시차 정보는 기준 픽셀(211)의 x축 좌표 값에서 기준 픽셀(221)의 x축 좌표 값을 차감한 값일 수 있다. 기준 픽셀(221)의 시차 정보는 기준 픽셀(221)의 x축 좌표 값에서 기준 픽셀(211)의 x축 좌표 값을 차감한 값일 수 있다.

제1 영상(210)에 포함된 기준 픽셀(212), 기준 픽셀(213), 및 기준 픽셀(214)는 각각 제2 영상(220)에 포함된 기준 픽셀(222), 기준 픽셀(223), 및 기준 픽셀(224)에 매칭될 수 있다. 이 경우, 기준 픽셀(212), 기준 픽셀(213), 및 기준 픽셀(214)은 각각 시차 정보를 포함할 수 있다. 또한, 기준 픽셀(222), 기준 픽셀(223), 및 기준 픽셀(224)은 각각 시차 정보를 포함할 수 있다.

아래에서 상세히 설명하겠으나, 기준 픽셀들에 포함된 시차 정보를 이용하여 일반 픽셀들의 위치에 대응하는 시차 정보가 생성될 수 있다. 예를 들어, 기준 픽셀들을 이용하여 스테레오 매칭이 수행될 수 있다. 간략히 설명하자면, 임의의 일반 픽셀에 대응하여 여러 후보 시차 정보가 존재하고, 기준 픽셀들을 이용하여 여러 후보 시차 정보 중 해당 일반 픽셀의 시차 정보가 결정될 수 있다.

도 3은 일 실시예에 따른 깊이 정보를 포함하는 기준 픽셀들을 설명하는 도면이다. 도 3을 참조하면, 일 실시예에 따른 영상(300)은 고해상도의 색상 영상과 저해상도의 깊이 영상(depth image)을 결합한 영상일 수 있다. 깊이 영상은 깊이 카메라(depth camera)에 의하여 생성될 수 있다. 깊이 영상에 포함된 복수의 픽셀들은 깊이(depth) 정보를 포함할 수 있다.

깊이 정보는 깊이 카메라에 의하여 촬영되는 객체와 깊이 카메라 사이의 거리를 포함할 수 있다. 깊이 영상에 포함된 복수의 픽셀들은 객체의 서로 다른 포인트에 대응된다. 임의의 픽셀의 깊이 정보는 해당 픽셀에 대응하는 포인트와 깊이 카메라 사이의 거리일 수 있다.

고해상도의 색상 영상과 저해상도의 깊이 영상을 결합하는 경우, 깊이 영상에 포함된 복수의 픽셀들은 색상 영상에 포함된 복수의 픽셀들 중 일부 픽셀들에 대응될 수 있다. 이 경우, 색상 영상에 포함된 복수의 픽셀들 중 일부 픽셀들의 위치에 대응하는 깊이 정보가 깊이 영상에 의하여 주어질 수 있다.

예를 들어, 영상(300)에 포함된 복수의 픽셀들 중 일부 픽셀들(301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 및 312)의 위치에 대응하는 깊이 정보가 깊이 영상에 의하여 주어질 수 있다. 이 경우, 일부 픽셀들(301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 및 312)은 다른 픽셀들에 비하여 깊이 정보를 더 포함하므로, 일부 픽셀들(301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 및 312)은 기준 픽셀들이다.

아래에서 상세히 설명하겠으나, 기준 픽셀들에 포함된 깊이 정보를 이용하여 일반 픽셀들의 위치에 대응하는 깊이 정보가 생성될 수 있다. 예를 들어, 기준 픽셀들을 이용하여 깊이 영상 업 샘플링이 수행될 수 있다. 간략히 설명하자면, 임의의 일반 픽셀에 대응하여 여러 후보 깊이 정보가 존재하고, 기준 픽셀들을 이용하여 여러 후보 깊이 정보 중 해당 일반 픽셀의 깊이 정보가 결정될 수 있다.

일 실시예에 따른 신장 트리

이하, 일 실시예에 따른 기준 픽셀을 이용하여 영상을 처리하는 방법을 설명한다. 다시 도 1을 참조하면, 영상(100)에 포함된 복수의 픽셀들 중 픽셀(110), 픽셀(120), 픽셀(130), 및 픽셀(140)만 추가 정보를 포함한다. 일 실시예에 따르면, 기준 픽셀들에 포함된 추가 정보를 이용하여 일반 픽셀들의 위치에 대응하는 추가 정보를 생성하기 위하여, 신장 트리(spanning tree)가 생성될 수 있다. 신장 트리는 연결된 무향 그래프(connected, undirected graph)의 부분 그래프로, 연결된 무향 그래프의 모든 노드들(nodes)을 연결하는 트리이다.

아래에서 상세히 설명하겠으나, 생성된 신장 트리는 기준 픽셀들에 포함된 추가 정보를 일반 픽셀들로 빠르고 정확하게 전파(propagation)하는 데 이용될 수 있다. 기준 픽셀에 포함된 추가 정보는 미리 주어진 신뢰성 있는 정보이므로, 일반 픽셀의 위치에 대응하는 미지의 추가 정보를 계산하기 위하여 기준 픽셀에 포함된 신뢰성 있는 추가 정보가 전파될 수 있다. 이하, 기준 픽셀은 글로벌 컨트롤 포인트(global control point, gcp)라고 지칭되고, 일반 픽셀은 논-글로벌 컨트롤 포인트(non-global control point, non-gcp)라고 지칭될 수 있다.

생성된 신장 트리는 최소 신장 트리(minimum spanning tree, MST)일 수 있다. 하나의 그래프에서 복수의 신장 트리들이 존재할 수 있다. 최소 신장 트리는 그래프의 각 변(edge)에 비용(cost)이 주어지는 경우 복수의 신장 트리들 중 비용이 최소인 신장 트리이다. 최소 신장 트리는 최소 비용 신장 트리(minimum cost spanning tree)라고 지칭될 수 있다.

일 실시예에 따른 신장 트리 생성 방법은 두 단계로 수행될 수 있다. 우선, 복수의 서브 트리들이 생성될 수 있다. 그 다음, 서브 트리들을 이용하여 신장 트리가 생성될 수 있다.

이하 설명의 편의를 위하여, 일반 픽셀에 포함된 일반적인 정보는 인텐시티 정보이고, 기준 픽셀에 더 포함된 추가 정보는 시차 정보인 경우를 가정한다. 다만, 실시예들은 이러한 경우에 제한되지 않으며, 일반 픽셀 또는 기준 픽셀이 다른 정보를 포함하는 경우에도 동일하게 적용될 수 있다.

서브 트리들은 표 1의 알고리즘에 의하여 생성될 수 있다. 표 1의 알고리즘의 입력은 입력 영상과 입력 영상을 위한 gcp들이고, 표 1의 알고리즘의 출력은 복수의 서브 트리들이다.

여기서, I_u는 픽셀 u의 인텐시티 정보이고, I_v는 픽셀 v의 인텐시티 정보이다. 또한, 가중치(weight)는 에지의 비용을 지칭할 수 있다. root(u)는 픽셀 u가 속하는 서브 트리의 루트 노드이고, root(v)는 픽셀 v가 속하는 서브 트리의 루트 노드이다. Th(u)는 픽셀 u가 속하는 서브 트리의 임계 비용(threshold cost)이고, Th(v)는 픽셀 v가 속하는 서브 트리의 임계 비용이다. 임계 비용은 미리 정해질 수 있다. 예를 들어, 모든 서브 트리의 임계 비용은 동일하게 정해질 수 있다. 또는 각각의 서브 트리의 임계 비용은 해당 서브 트리의 루트 노드의 유형에 따라 상이하게 정해질 수 있다.

생성된 서브 트리들 각각은 해당하는 루트와 연결된 하나의 영역으로 분류될 수 있다. 임의의 서브 트리의 루트 노드가 gcp인 경우, 해당 서브 트리의 루트 노드는 인텐시티 정보, 위치 정보, 및 시차 정보를 포함할 수 있다. 임의의 서브 트리의 루트 노드가 non-gcp인 경우, 해당 루트 노드는 인텐시티 정보 및 위치 정보를 포함할 수 있다. 임의의 서브 트리의 루트 노드에 포함된 정보는 해당 서브 트리를 대표하는 정보로 이용될 수 있다.

최소 신장 트리는 표 2의 알고리즘에 의하여 생성될 수 있다. 표 2의 알고리즘의 입력 영상, 입력 영상을 위한 gcp들, 및 표 1의 알고리즘에 의하여 생성된 복수의 서브 트리들이다. 표 2의 알고리즘의 출력은 입력 영상 전체를 커버하는 최소 신장 트리이다.

여기서, d_u는 픽셀 u의 시차 정보이고, d_v는 픽셀 v의 시차 정보이다. 또한, Th_d(u)는 픽셀 u가 속하는 서브 트리의 시차 정보 임계 비용이고, Th_d(v)는 픽셀 v가 속하는 서브 트리의 시차 정보 임계 비용이다.

이하, 도 4 내지 도 16을 참조하여 표 1 의 알고리즘 및 표 2의 알고리즘을 상세하게 설명한다. 도 4를 참조하면, 일 실시예에 따른 입력 영상(400)은 4 x 4 매트릭스 형태의 픽셀들을 포함한다. 전술한 바와 같이, 입력 영상(400)에 포함된 픽셀들 각각은 고유한 인덱스로 지시될 수 있다. 이하, 픽셀 idx (idx는 양의 정수)는 인덱스 idx에 의하여 지시되는 픽셀을 지칭한다.

입력 영상(400)에 포함된 복수의 픽셀들 중 픽셀 4, 픽셀 5, 픽셀 12, 및 픽셀 13은 기준 픽셀이고, 나머지 픽셀들은 일반 픽셀일 수 있다. 또한, 입력 영상(400)은 크게 세 개의 영역들로 분류될 수 있다. 예를 들어, 입력 영상(400)은 제1 영역(410)에 대응하는 제1 객체와 제2 영역(420)에 대응하는 제2 객체를 포함할 수 있다. 제3 영역(430)은 배경에 해당할 수 있다.

도 5를 참조하면, 일 실시예에 따른 그래프(500)는 도 4의 입력 영상(400)에 포함된 픽셀들에 대응하는 노드들을 포함하는 그래프이다. 표 1의 알고리즘의 제1 스텝에서 그래프(500)의 인접 픽셀들이 연결될 수 있다. 인접 픽셀들은 다양하게 정해질 수 있다.

예를 들어, 임의의 픽셀의 인접 픽셀들은 해당 픽셀과 상, 하, 좌, 우로 인접한 픽셀들로 정해질 수 있다. 또는, 임의의 픽셀의 인접 픽셀들은 해당 픽셀과 상, 하, 좌, 우, 또는 대각선 방향으로 인접한 픽셀들로 정해질 수 있다. 또는, 임의의 픽셀의 인접 픽셀들은 해당 픽셀을 제외한 나머지 모든 픽셀들로 정해질 수 있다. 이하, 설명의 편의를 위하여 임의의 픽셀의 인접 픽셀들은 해당 픽셀과 상, 하, 좌, 우로 인접한 픽셀들인 경우를 가정한다.

표 1의 알고리즘의 제1 스텝에서 그래프(500)의 인접 픽셀들 사이의 비용이 계산될 수 있다. 인접 픽셀들 사이의 비용은 다양하게 계산될 수 있다. 예를 들어, 인접 픽셀들 사이의 비용은 인접 픽셀들의 인텐시티 정보에 기초하여 계산될 수 있다. 또는, 인접 픽셀들 사이의 비용은 인접 픽셀들의 인텐시티 정보 및 위치 정보에 기초하여 계산될 수 있다. 이하, 설명의 편의를 위하여 인접 픽셀들 사이의 비용은 인접 픽셀들 사이의 인텐시티 차이의 절대값으로 계산되는 경우를 가정한다.

그래프(500)에 포함된 픽셀들은 크게 세 개의 영역들로 분류될 수 있다. 제1 영역(510)은 도 4의 제1 영역(410)에 대응하고, 제2 영역(520)은 도 4의 제2 영역(420)에 대응하며, 제3 영역(530)은 도 4의 제3 영역(430)에 대응한다.

동일한 영역에 속하는 인접 픽셀들 사이의 비용은 상이한 영역에 속하는 인접 픽셀들 사이의 비용보다 작을 수 있다. 도 6을 참조하면, 표 1의 알고리즘의 제2 스텝에서 그래프(500)에 포함된 에지들이 비용의 오름차순으로 정렬될 수 있다. 예를 들어, 그래프(500)에 포함된 에지들 중 픽셀 11과 픽셀 15를 연결하는 에지의 비용이 가장 작고, 픽셀 6과 픽셀 7을 연결하는 에지의 비용이 가장 클 수 있다.

도 7을 참조하면, 표 1의 알고리즘의 제3 스텝에서 에지들이 정렬된 순서대로 방문된다. 예를 들어, 픽셀 11과 픽셀 15를 연결하는 에지가 제일 먼저 방문될 수 있다. 픽셀 11과 픽셀 15는 모두 non-gcp이므로, 표 1의 알고리즘의 제3-2 스텝에서 에지 비용과 임계 비용이 비교된다. 이하, 에지 비용은 인접 픽셀들 사이의 비용을 지칭하고, 임계 비용은 인접 픽셀들 각각이 속하는 서브 트리의 임계 비용 중 작은 것을 지칭할 수 있다.

또한, 이하 설명의 편의를 위하여 동일한 영역에 속하는 인접 픽셀들 사이의 비용은 임계 비용보다 작고, 상이한 영역에 속하는 인접 픽셀들 사이의 비용은 임계 비용보다 크다고 가정한다. 픽셀 11과 픽셀 15는 동일한 영역(530)에 속하므로, 표 1의 알고리즘의 제3-2 스텝에서 픽셀 11과 픽셀 15가 연결된다.

인접 픽셀들이 연결되는 경우, 생성되는 서브 트리의 임계 비용이 갱신될 수 있다. 예를 들어, 생성되는 서브 트리의 임계 비용은 연결되기 전 인접 픽셀들 각각의 임계 비용에 기초하여 갱신될 수 있다. 다만, 동일한 영역에 속하는 인접 픽셀들 사이의 비용은 임계 비용보다 작고 상이한 영역에 속하는 인접 픽셀들 사이의 비용은 임계 비용보다 크다고 가정하였으므로, 이하에서 임계 비용의 갱신에 대한 설명은 생략한다.

인접 픽셀들이 모두 non-gcp인 경우, 연결된 이후 생성되는 서브 트리의 레벨이 작아지도록 루트 노드가 선택될 수 있다. 인접 픽셀들 중 어느 것이 선택되더라도 생성되는 서브 트리의 레벨이 동일한 경우, 인덱스가 작은 픽셀이 선택되거나 인덱스가 큰 픽셀이 선택되거나 랜덤하게 어느 하나의 픽셀이 선택될 수 있다. 이하, 설명의 편의를 위하여, 인접 픽셀들 중 어느 것이 선택되더라도 생성되는 서브 트리의 레벨이 동일한 경우 인덱스가 작은 픽셀이 선택된다고 가정한다. 이 경우, 픽셀 11이 루트 노드로 선택된다.

다음으로 픽셀 1과 픽셀 2를 연결하는 에지가 방문된다. 픽셀 1과 픽셀 2는 모두 non-gcp이므로, 표 1의 알고리즘의 제3-2 스텝에서 에지 비용과 임계 비용이 비교된다. 픽셀 1과 픽셀 2는 동일한 영역(510)에 속하므로, 표 1의 알고리즘의 제3-2 스텝에서 픽셀 1과 픽셀 2가 연결된다. 인접 픽셀들 중 어느 것이 선택되더라도 생성되는 서브 트리의 레벨이 동일하므로, 픽셀 1이 루트 노드로 선택된다.

다음으로 픽셀 8과 픽셀 12를 연결하는 에지가 방문된다. 픽셀 8은 non-gcp이고 픽셀 12는 gcp이므로, 표 1의 알고리즘의 제3-1 스텝에서 에지 비용과 임계 비용이 비교된다. 픽셀 8과 픽셀 12는 동일한 영역(520)에 속하므로, 표 1의 알고리즘의 제3-1 스텝에서 픽셀 8과 픽셀 12가 연결된다. 인접 픽셀들 중 어느 하나의 픽셀이 gcp인 경우, gcp인 픽셀이 생성되는 서브 트리의 루트 노드로 선택된다. 이 경우, 픽셀 12가 루트 노드로 선택된다.

다음으로 픽셀 7과 픽셀 8을 연결하는 에지가 방문된다. 픽셀 7은 non-gcp이고 픽셀 8이 속하는 서브 트리의 루트 노드인 픽셀 12는 gcp이므로, 표 1의 알고리즘의 제3-1 스텝에서 에지 비용과 임계 비용이 비교된다. 픽셀 7과 픽셀 8은 동일한 영역(520)에 속하므로, 표 1의 알고리즘의 제3-1 스텝에서 픽셀 7과 픽셀 8이 연결된다. 또한, 픽셀 8이 속하는 서브 트리의 루트 노드인 픽셀 12가 gcp이므로 픽셀 12가 루트 노드로 선택된다.

다음으로 픽셀 2와 픽셀 6을 연결하는 에지가 방문된다. 픽셀 2가 속하는 서브 트리의 루트 노드인 픽셀 1은 non-gcp이고 픽셀 6도 non-gcp이므로, 표 1의 알고리즘의 제3-2 스텝에서 에지 비용과 임계 비용이 비교된다. 픽셀 2와 픽셀 6은 동일한 영역(510)에 속하므로, 표 1의 알고리즘의 제3-2 스텝에서 픽셀 2와 픽셀 6이 연결된다. 픽셀 2가 속하는 서브 트리의 루트 노드인 픽셀 1과 픽셀 6 중 어느 것이 선택되더라도 생성되는 서브 트리의 레벨이 동일하므로, 인덱스가 작은 픽셀 1이 루트 노드로 선택된다.

다음으로 픽셀 10과 픽셀 11을 연결하는 에지가 방문된다. 픽셀 10은 non-gcp이고 픽셀 11이 속하는 서브 트리의 루트 노드인 픽셀 11도 non-gcp이므로, 표 1의 알고리즘의 제3-2 스텝에서 에지 비용과 임계 비용이 비교된다. 픽셀 10과 픽셀 11은 동일한 영역(530)에 속하므로, 표 1의 알고리즘의 제3-2 스텝에서 픽셀 10과 픽셀 11이 연결된다. 픽셀 11이 속하는 서브 트리의 루트 노드인 픽셀 11이 선택되는 경우 생성되는 서브 트리의 레벨이 더 작아지므로, 픽셀 11이 루트 노드로 선택된다.

다음으로 픽셀 15과 픽셀 16을 연결하는 에지가 방문된다. 픽셀 15가 속하는 서브 트리의 루트 노드인 픽셀 11은 non-gcp이고 픽셀 16도 non-gcp이므로, 표 1의 알고리즘의 제3-2 스텝에서 에지 비용과 임계 비용이 비교된다. 픽셀 15와 픽셀 16은 동일한 영역(530)에 속하므로, 표 1의 알고리즘의 제3-2 스텝에서 픽셀 15와 픽셀 16이 연결된다. 픽셀 15가 속하는 서브 트리의 루트 노드인 픽셀 11이 선택되는 경우 생성되는 서브 트리의 레벨이 더 작아지므로, 픽셀 11이 루트 노드로 선택된다.

다음으로 픽셀 9과 픽셀 13을 연결하는 에지가 방문된다. 픽셀 9는 non-gcp이고 픽셀 13은 gcp이므로, 표 1의 알고리즘의 제3-1 스텝에서 에지 비용과 임계 비용이 비교된다. 픽셀 9와 픽셀 13은 동일한 영역(510)에 속하므로, 표 1의 알고리즘의 제3-1 스텝에서 픽셀 9와 픽셀 13이 연결된다. 픽셀 13이 gcp이므로, 픽셀 13이 루트 노드로 선택된다.

다음으로 픽셀 5와 픽셀 9를 연결하는 에지가 방문된다. 픽셀 5는 gcp이고 픽셀 9가 속하는 서브 트리의 루트 노드인 픽셀 13도 gcp이므로, 표 1의 알고리즘의 제3-3 스텝에서 픽셀 5와 픽셀 9는 연결되지 않는다.

다음으로 픽셀 1과 픽셀 5를 연결하는 에지가 방문된다. 픽셀 1이 속하는 서브 트리의 루트 노드인 픽셀 1은 non-gcp이고 픽셀 5는 gcp이므로, 표 1의 알고리즘의 제3-1 스텝에서 에지 비용과 임계 비용이 비교된다. 픽셀 1과 픽셀 5는 동일한 영역(510)에 속하므로, 표 1의 알고리즘의 제3-1 스텝에서 픽셀 1과 픽셀 5는 연결된다. 픽셀 5가 gcp이므로, 픽셀 5가 루트 노드로 선택된다.

다음으로 픽셀 3과 픽셀 4를 연결하는 에지가 방문된다. 픽셀 3은 non-gcp이고 픽셀 4는 gcp이므로, 표 1의 알고리즘의 제3-1 스텝에서 에지 비용과 임계 비용이 비교된다. 픽셀 3과 픽셀 4는 동일한 영역(520)에 속하므로, 표 1의 알고리즘의 제3-1 스텝에서 픽셀 3과 픽셀 4가 연결된다. 픽셀 4가 gcp이므로, 픽셀 4가 루트 노드로 선택된다.

다음으로 픽셀 5와 픽셀 6을 연결하는 에지가 방문된다. 픽셀 5와 픽셀 6은 이미 동일한 서브 트리에 속하므로, 픽셀 5와 픽셀 6은 연결되지 않는다. 신장 트리는 트리에 해당하고, 트리는 사이클릭 경로(cyclic path)를 가지지 않기 때문이다.

다음으로 픽셀 10과 픽셀 14를 연결하는 에지가 방문된다. 픽셀 10이 속하는 서브 트리의 루트 노드인 픽셀 11은 non-gcp이고 픽셀 14도 non-gcp이므로, 표 1의 알고리즘의 제3-2 스텝에서 에지 비용과 임계 비용이 비교된다. 픽셀 10과 픽셀 14는 동일한 영역(530)에 속하므로, 표 1의 알고리즘의 제3-2 스텝에서 픽셀 10과 픽셀 14가 연결된다. 픽셀 10이 속하는 서브 트리의 루트 노드인 픽셀 11이 선택되는 경우 생성되는 서브 트리의 레벨이 더 작아지므로, 픽셀 11이 루트 노드로 선택된다.

다음으로 픽셀 3과 픽셀 7을 연결하는 에지가 방문된다. 픽셀 3이 속하는 서브 트리의 루트 노드인 픽셀 4는 gcp이고 픽셀 7이 속하는 서브 트리의 루트 노드인 픽셀 12도 gcp이므로, 표 1의 알고리즘의 제3-3 스텝에서 픽셀 3과 픽셀 7은 연결되지 않는다.

다음으로 픽셀 4와 픽셀 8을 연결하는 에지가 방문된다. 픽셀 4가 속하는 서브 트리의 루트 노드인 픽셀 4는 gcp이고 픽셀 8이 속하는 서브 트리의 루트 노드인 픽셀 12도 gcp이므로, 표 1의 알고리즘의 제3-3 스텝에서 픽셀 4와 픽셀 8은 연결되지 않는다.

다음으로 픽셀 14와 픽셀 15를 연결하는 에지가 방문된다. 픽셀 14와 픽셀 15는 이미 동일한 서브 트리에 속하므로, 픽셀 14와 픽셀 15는 연결되지 않는다.

다음으로 픽셀 9와 픽셀 10을 연결하는 에지가 방문된다. 픽셀 9가 속하는 서브 트리의 루트 노드인 픽셀 13은 gcp이고 픽셀 10이 속하는 서브 트리의 루트 노드인 픽셀 11은 non-gcp이므로, 표 1의 알고리즘의 제3-1 스텝에서 에지 비용과 임계 비용이 비교된다. 픽셀 9는 제1 영역(510)에 속하고 픽셀 10은 제3 영역(530)에 속하므로, 표 1의 알고리즘의 제3-1 스텝에서 픽셀 9와 픽셀 10은 연결되지 않는다.

이후에 방문되는 에지들의 비용들은 모두 임계 비용보다 크므로, 이후에 방문되는 에지들은 연결되지 않는다. 도 8을 참조하면, 표 1의 알고리즘이 수행된 결과 다섯 개의 서브 트리들(810, 820, 830, 840, 및 850)이 생성된다.

도 9를 참조하면, 표 2의 알고리즘의 제1 스텝에서 루트 노드들 사이의 에지들을 위한 비용들이 계산된다. 위치가 인접한 루트 노드들 사이의 에지들을 위한 비용들만 계산될 수도 있고, 또는 루트 노드들 사이의 모든 에지들을 위한 비용들이 계산될 수도 있다. 이하, 루트 노드들 사이의 모든 에지들을 위한 비용들이 계산되는 경우를 설명한다. 인접하지 않은 루트 노드들 사이의 에지를 방문하기 위하여 케이-디(k-dimensional, k-d) 트리가 이용될 수 있다.

루트 노드들 사이의 에지들을 위한 비용은 다양하게 계산될 수 있다. 예를 들어, gcp인 루트 노드와 gcp인 루트 노드 사이의 비용은 인텐시티 정보, 위치 정보, 및 시차 정보 중 적어도 하나에 기초하여 계산될 수 있다. 또한, non-gcp인 루트 노드와 gcp인 루트 노드 사이의 비용은 인텐시티 정보 및 위치 정보 중 적어도 하나에 기초하여 계산될 수 있다. 또한, non-gcp인 루트 노드와 non-gcp인 루트 노드 사이의 비용은 인텐시티 정보 및 위치 정보 중 적어도 하나에 기초하여 계산될 수 있다.

도 10을 참조하면, 표 2의 알고리즘의 제2 스텝에서 루트 노드들 사이의 에지들이 비용의 오름차순으로 정렬된다. 예를 들어, 제1 서브 트리(810)의 루트 노드인 픽셀 4와 제4 서브 트리(840)의 루트 노드인 픽셀 12 사이의 비용이 가장 작을 수 있다. 또한, 제1 서브 트리(810)의 루트 노드인 픽셀 4와 제3 서브 트리(830)의 루트 노드인 픽셀 11 사이의 비용이 가장 클 수 있다.

도 11을 참조하면, 표 2의 알고리즘의 제3 스텝에서 에지들이 정렬된 순서대로 방문된다. 예를 들어, 픽셀 4와 픽셀 12를 연결하는 에지가 제일 먼저 방문될 수 있다. 픽셀 4와 픽셀 12는 모두 gcp이므로, 표 2의 알고리즘의 제3-1 스텝에서 에지 비용과 임계 비용이 비교된다. 이하, 에지 비용은 방문된 에지의 비용을 지칭하고, 임계 비용은 방문된 에지에 의하여 연결되는 루트 노드들 각각이 속하는 서브 트리의 임계 비용 중 작은 것을 지칭할 수 있다. 에지 비용 및 임계 비용은 각각 인텐시티 정보, 위치 정보, 및 시차 정보 중 적어도 하나와 관련될 수 있다.

또한, 이하 설명의 편의를 위하여 동일한 영역에 속하는 루트 노드들 사이의 비용은 임계 비용보다 작고, 상이한 영역에 속하는 루트 노드들 사이의 비용은 임계 비용보다 크다고 가정한다. 픽셀 4와 픽셀 12는 동일한 영역(520)에 속하므로, 표 2의 알고리즘의 제3-1 스텝에서 픽셀 4와 픽셀 12가 연결된다. 픽셀 12가 루트 노드로 선택되는 경우 생성되는 서브 트리의 레벨이 작아지므로, 픽셀 12가 루트 노드로 선택된다.

도 12를 참조하면, 다음으로 픽셀 5와 픽셀 13을 연결하는 에지가 방문된다. 픽셀 5와 픽셀 13은 모두 gcp이므로, 표 2의 알고리즘의 제3-1 스텝에서 에지 비용과 임계 비용이 비교된다. 픽셀 5와 픽셀 13은 동일한 영역(510)에 속하므로, 표 2의 알고리즘의 제3-1 스텝에서 픽셀 5와 픽셀 13이 연결된다. 픽셀 5가 루트 노드로 선택되는 경우 생성되는 서브 트리의 레벨이 작아지므로, 픽셀 5가 루트 노드로 선택된다.

다음으로 픽셀 11과 픽셀 13을 연결하는 에지가 방문된다. 다만, 픽셀 13은 더 이상 루트 노드가 아니므로, 픽셀 11과 픽셀 13은 연결되지 않는다. 다음으로 픽셀 4와 픽셀 5를 연결하는 에지가 방문된다. 다만, 픽셀 4는 더 이상 루트 노드가 아니므로, 픽셀 4와 픽셀 5는 연결되지 않는다. 다음으로 픽셀 12와 픽셀 13을 연결하는 에지가 방문된다. 다만, 픽셀 13은 더 이상 루트 노드가 아니므로, 픽셀 12와 픽셀 13은 연결되지 않는다.

도 13을 참조하면, 다음으로 픽셀 5와 픽셀 11을 연결하는 에지가 방문된다. 픽셀 5는 gcp이고 픽셀 11은 non-gcp이므로, 표 2의 알고리즘의 제3-2 스텝에서 픽셀 5와 픽셀 11이 연결된다. 표 1의 알고리즘이 수행된 결과 gcp를 루트로 하는 서브 트리와 non-gcp를 루트로 하는 서브 트리는 서로 다른 영역에 속하므로, 표 2의 알고리즘의 제3-2 스텝에서 에지 비용과 임계 비용을 비교할 필요 없이 픽셀 5와 픽셀 11을 연결하는 에지의 비용에 페널티(penalty)가 부과된다. 또한, 픽셀 5가 루트 노드로 선택되는 경우 생성되는 서브 트리의 레벨이 작아지므로, 픽셀 5가 루트 노드로 선택된다.

도 14를 참조하면, 다음으로 픽셀 5와 픽셀 12를 연결하는 에지가 방문된다. 픽셀 5와 픽셀 12는 모두 gcp이므로, 표 2의 알고리즘의 제3-1 스텝에서 에지 비용과 임계 비용이 비교된다. 픽셀 5는 제1 영역(510)에 속하고 픽셀 12는 제2 영역(520)에 속하므로, 표 2의 알고리즘의 제3-1 스텝에서 픽셀 5와 픽셀 12를 연결하는 에지의 비용에 페널티가 부과된다. 또한, 픽셀 5가 루트 노드로 선택되는 경우 생성되는 서브 트리의 레벨이 작아지므로, 픽셀 5가 루트 노드로 선택된다.

도 15를 참조하면, 표 2의 알고리즘이 수행된 결과 신장 트리(1500)가 생성된다. 신장 트리(1500)는 도 14의 트리(1400)에 해당한다.

이하 도 16을 참조하여, 표 1의 알고리즘 및 표 2의 알고리즘 수행 과정을 간략하게 재 설명한다. 표 1의 알고리즘에 의하여 제1 서브 트리(1610), 제2 서브 트리(1620), 제3 서브 트리(1630), 및 제4 서브 트리(1640)이 생성될 수 있다. 이 때, 하나의 서브 트리에는 최대 하나의 gcp만 포함되도록 서브 트리들이 생성된다.

표 2의 알고리즘에 의하여 서브 트리들의 루트 노드들이 연결된다. 이 때, 에지(1615)와 같이 gcp와 gcp를 연결하는 에지의 비용은 인텐시티 정보, 위치 정보, 및 시차 정보 중 적어도 하나를 이용하여 계산될 수 있다. 예를 들어, gcp와 gcp를 연결하는 에지의 비용은 수학식 1, 수학식 2, 수학식 3, 수학식 4, 수학식 5, 및 수학식 6 중 어느 하나로 계산될 수 있다. 이 밖에도 gcp와 gcp를 연결하는 에지의 비용을 계산하는 방식은 다양하게 변형될 수 있다.

여기서, x_u는 픽셀 u의 위치 정보이고, x_v는 픽셀 v의 위치 정보이며, α는 위치 정보를 위한 파라미터이다. d_u는 픽셀 u의 시차 정보이고, d_v는 픽셀 v의 시차 정보이며, β는 시차 정보를 위한 파라미터이다. I_u는 픽셀 u의 인텐시티 정보이고, I_v는 픽셀 v의 인텐시티 정보이며, γ는 인텐시티 정보를 위한 파라미터이다.

물론, 에지(1615)의 비용이 임계 비용보다 큰 경우, 에지(1615)의 비용에 페널티가 부과될 수 있다.

non-gcp는 시차 정보를 포함하지 않으므로, 에지(1625)와 같이 gcp와 non-gcp를 연결하는 에지의 비용은 인텐시티 정보 및 위치 정보 중 적어도 하나를 이용하여 계산될 수 있다. 이 때, 에지(1625)의 비용에 페널티가 부과된다. 예를 들어, gcp와 non-gcp를 연결하는 에지의 비용은 수학식 7로 계산될 수 있다. 이 밖에도 gcp와 non-gcp를 연결하는 에지의 비용을 계산하는 방식은 다양하게 변형될 수 있다.

여기서, T는 페널티이다. 또한, non-gcp는 시차 정보를 포함하지 않으므로, 에지(1635)와 같이 non-gcp와 non-gcp를 연결하는 에지의 비용은 인텐시티 정보 및 위치 정보 중 적어도 하나를 이용하여 계산될 수 있다. 이 때, 에지(1635)의 비용에 페널티가 부과된다. 예를 들어, non-gcp와 non-gcp를 연결하는 에지의 비용은 수학식 7로 계산될 수 있다. 이 밖에도 non-gcp와 non-gcp를 연결하는 에지의 비용을 계산하는 방식은 다양하게 변형될 수 있다.

일 실시예에 따른 스테레오 매칭

이하 도 17 및 도 18을 참조하여, 일 실시예에 따른 신장 트리를 이용한 스테레오 매칭 기법을 설명한다. 전술한 바와 같이, 스테레오 매칭 기법은 왼쪽 눈에 대응하는 영상 내 픽셀과 오른쪽 눈에 대응하는 영상 내 픽셀을 매칭하는 기법이다. 스테레오 매칭 기법은 왼쪽 눈에 대응하는 영상을 기준으로 수행될 수 있고, 오른쪽 눈에 대응하는 영상을 기준으로 수행될 수도 있다. 이하, 설명의 편의를 위하여 왼쪽 눈에 대응하는 영상을 기준으로 스테레오 매칭 기법이 수행되는 경우를 가정한다.

왼쪽 눈에 대응하는 영상에 포함된 임의의 픽셀 x의 시차 정보를 구하기 위하여, 여러 후보 시차 정보

중 가장 적합한 후보 시차 정보가 선택될 수 있다. 가장 적합한 후보 시차 정보를 선택하기 위하여, 픽셀 x에서 각각의 후보 시차 정보

에 대응하는 데이터 비용(data cost)이 계산될 수 있다.

보다 구체적으로, 수학식 8을 참조하면, 픽셀 집합 {x'}은 왼쪽 눈에 대응하는 영상의 픽셀 x에 매칭될 가능성이 있는 오른쪽 눈에 대응하는 영상의 픽셀들로 구성된다.

또한, 수학식 9를 참조하면, 데이터 비용은 픽셀 x와 픽셀 집합 {x'} 사이의 유사성을 판단하기 위한 함수로 정의될 수 있다.

여기서, D_x(d)는 픽셀 x에서 후보 시차 정보 d에 대응하는 데이터 비용이다. I_l은 왼쪽 눈에 대응하는 영상의 인텐시티 정보이고, I_r은 오른쪽 눈에 대응하는 영상의 인텐시티 정보이다. W는 픽셀 x의 특징 벡터(feature vector)를 계산하기 위해 설정되는 영역이다.

예를 들어, I_l의 픽셀 (x, y)와 그 주변 영역 W의 인텐시티 정보에 의하여 결정되는 제1 특징 벡터와 I_r의 픽셀 (x-d, y)와 그 주변 영역 W'의 인텐시티 정보에 의해서 결정되는 제2 특징 벡터가 서로 유사할수록 D_x(d)는 작은 값을 출력할 수 있다. 또한, 제1 특징 벡터와 제2 특징 벡터가 서로 상이할수록 D_x(d)는 큰 값을 출력할 수 있다.

예를 들어, 스테레오 매칭을 위한 데이터 비용은 수학식 10 및 수학식 11과 같이 정의될 수 있다.

여기서, D_v(d)는 데이터 비용이고, D_v ^conventional(d)는 인텐시티 정보에 기초하여 계산되는 일반적인 데이터 비용이며, G_v(d)는 gcp를 위한 데이터 비용이다. μ와 κ는 D_v ^conventional(d)와 G_v(d)의 가중치를 결정하는 파라미터들이다. d_v는 gcp인 픽셀 v에 미리 주어진 시차 정보이다. G_max는 미리 정해진 데이터 비용의 최대 값이다.

gcp인 픽셀 v1의 경우 κ가 μ에 비하여 충분히 크게 설정될 수 있다. 예를 들어, κ는 1로 설정되고 μ는 0으로 설정될 수 있다. 후보 시차 정보 d가 gcp인 픽셀 v1에 미리 주어진 시차 정보와 동일한 경우 데이터 비용은 최소 값인 0을 가지고, 후보 시차 정보 d가 gcp인 픽셀 v1에 미리 주어진 시차 정보와 상이한 경우 데이터 비용은 최대 값인 G_max를 가진다.

non-gcp인 픽셀 v2의 경우 μ가 κ에 비하여 충분히 크게 설정될 수 있다. 예를 들어, μ는 1로 설정되고 κ는 0으로 설정될 수 있다. non-gcp인 픽셀 v2의 경우 시차 정보가 미리 주어지지 않으므로, D_v ^conventional(d)를 이용하여 후보 시차 정보 d에 대응하는 데이터 비용이 계산될 수 있다.

스테레오 매칭의 성능을 향상시키기 위하여 축적 데이터 비용(accumulated data cost)이 이용될 수 있다. 예를 들어, 픽셀 v의 데이터 비용을 계산하기 위하여 하나의 데이터 비용 D_x(d)을 이용하는 대신, 수학식 12를 이용하여 미리 정해진 영역에 포함된 픽셀들의 데이터 비용들이 가중 합산될 수 있다.

여기서,

는 픽셀 x에서 후보 시차 정보 d에 대응하는 축적 데이터 비용이다. R_x는 픽셀 x의 축적 데이터 비용을 계산하기 위한 미리 정해진 영역이고, w(i, x)는 픽셀 x의 축적 데이터 비용을 계산하기 위하여 합산되는 픽셀 i의 데이터 비용의 가중치이다. D_i(d)는 R_x에 포함된 픽셀 i에서 후보 시차 정보 d에 대응하는 데이터 비용이다. D_i(d)는 수학식 10에 대응할 수 있다.

이 때, 영역 R_x의 커버리지(coverage)와 가중 합산을 위한 가중치 w(x, i)는 축적 데이터 비용

의 성능을 결정하는 주요 파라미터들일 수 있다. 수학식 13을 참조하면, 일 실시예에 따른 신장 트리를 이용하여, 이미지 전체를 커버하는 픽셀들의 데이터 비용들이 가중 합산될 수 있다.

여기서,

는 픽셀 v에서 후보 시차 정보 d에 대응하는 축적 데이터 비용이다. I는 이미지 전체를 커버하는 픽셀들의 집합이고, w(u, v)는 픽셀 v의 축적 데이터 비용을 계산하기 위하여 합산되는 픽셀 u의 데이터 비용의 가중치이다. D_u(d)는 I에 포함된 픽셀 u에서 후보 시차 정보 d에 대응하는 데이터 비용이다. D_u(d)는 수학식 10에 대응할 수 있다.

w(u, v)는 두 픽셀 u와 v 사이의 측지 거리(geodesic distance)일 수 있다. 예를 들어, w(u, v)는 수학식 14를 이용하여 계산될 수 있다.

여기서,

는 신장 트리에서 픽셀 v로부터 픽셀 u에 이르는 경로에 있는 에지들의 비용들이 합산된 값이다.

는 w(u, v)를 위한 파라미터이다.

예를 들어, 도 17을 참조하면, w(2, 1)은 픽셀 2로부터 픽셀 1로의 경로(1710)에 있는 에지들의 비용들의 합이다. 또한, w(7, 1)은 픽셀 7로부터 픽셀 1로의 경로(1720)에 있는 에지들의 비용들의 합이다. 또한, w(13, 1)은 픽셀 13으로부터 픽셀 1로의 경로(1730)에 있는 에지들의 비용들의 합이다.

픽셀 v와 연관성이 높은 픽셀 u1일수록, 픽셀 u로부터 픽셀 v로의 경로에 있는 에지들의 비용들의 합이 작아지므로, w(u1, v)의 값이 커진다. 반대로, 픽셀 v와 연관성이 낮은 픽셀 u2일수록, 픽셀 u2로부터 픽셀 v로의 경로에 있는 에지들의 비용들의 합이 커지므로, w(u2, v)의 값이 커진다.

일 예로, 도 17을 참조하면, w(2, 1)은 w(7, 1)에 비하여 충분히 큰 값을 가질 수 있다. 다시 말해, 픽셀 2로부터 픽셀 1로의 경로(1710)에 있는 에지의 비용은 픽셀 7로부터 픽셀 1로의 경로(1720)에 있는 에지들의 비용들의 합보다 충분히 작을 수 있다. 픽셀 7로부터 픽셀 1로의 경로(1720)에는 픽셀 12와 픽셀 5를 연결하는 에지가 존재하는데, 픽셀 12와 픽셀 5를 연결하는 에지는 신장 트리가 생성될 때 페널티가 부과된 에지이기 때문이다.

다른 예로, 도 18을 참조하면, w(10, 16)은 w(9, 16)에 비하여 충분히 큰 값을 가질 수 있다. 다시 말해, 픽셀 10으로부터 픽셀 16으로의 경로(1810)에 있는 에지들의 비용들의 합은 픽셀 9로부터 픽셀 16으로의 경로(1820)에 있는 에지들의 비용들의 합보다 충분히 작을 수 있다. 픽셀 9로부터 픽셀 16으로의 경로(1820)에는 픽셀 5와 픽셀 11을 연결하는 에지가 존재하는데, 픽셀 5와 픽셀 11을 연결하는 에지는 신장 트리가 생성될 때 페널티가 부과된 에지이기 때문이다.

수학식 15를 참조하면, 후보 시차 정보 d ∈ {0, ..., d_max} 각각에 대한

, ...,

가 계산되면, 축적 데이터 비용을 가장 작게 만드는 후보 시차 정보 d_v*가 픽셀 v의 시차 정보로 결정된다.

일 실시예에 따른 업 샘플링

일 실시예에 따른 신장 트리를 이용한 스테레오 매칭 기법은 업 샘플링 기법에 응용될 수 있다. 도 3을 참조하면, 고해상도의 색상 영상과 저해상도의 깊이 영상이 주어지는 경우, 깊이 영상의 픽셀들에 대응하는 색상 영상의 픽셀들이 깊이 정보를 더 포함하는 기준 픽셀들이 될 수 있다.

영상(300) 전체를 커버하는 신장 트리는 전술한 방식 그대로 생성될 수 있다. 기준 픽셀들에 기초하여 서브 트리들이 생성되고, 서브 트리들의 루트들이 서로 연결됨으로써 신장 트리가 생성될 수 있다.

깊이 영상 업 샘플링을 위한 데이터 비용은 다음과 같이 정의될 수 있다. 우선, non-gcp인 픽셀의 데이터 비용은 0으로 설정된다. 또한, gcp인 픽셀의 데이터 비용은 수학식 16 및 수학식 17과 같은 히스토그램(histogram)의 형태로 정의될 수 있다.

여기서, D_v(d)는 gcp인 픽셀 v를 위한 데이터 비용이고, κ_v와 σ_d는 데이터 비용을 위한 파리미터들이다. d_v는 gcp인 픽셀 v에 미리 주어진 깊이 정보이다.

수학식 13과 수학식 14을 이용하여 후보 깊이 정보 d ∈ {0, ..., d_max} 각각에 대한

, ...,

가 계산될 수 있다. 수학식 18을 참조하면, 축적 데이터 비용을 가장 크게 만드는 후보 깊이 정보 d_v*가 픽셀 v의 깊이 정보로 결정된다.

다시 도 3을 참조하면, 전술한 업 샘플링 기법을 통하여 깊이 영상의 해상도는 색상 영상의 해상도만큼 증가될 수 있다. 깊이 영상의 업 샘플링 기법은 깊이 맵 업 샘플링(depth map up-sampling)이라고 지칭될 수 있다.

일 실시예에 따른 기준 픽셀의 생성

도 19 및 도 20은 일 실시예에 따른 스테레오 비디오를 이용한 기준 픽셀의 생성을 설명하는 도면들이다. 일 실시예에 따른 기준 픽셀은 스테레오 비디오(stereo video)로부터 추출될 수 있다.

스테레오 비디오는 연속된 스테레오 영상들을 포함한다. 스테레오 비디오는 왼쪽 눈에 대응하는 제1 영상 시퀀스 및 오른쪽 눈에 대응하는 제2 영상 시퀀스를 포함할 수 있다. 제1 영상 시퀀스 및 제2 영상 시퀀스 각각에서 광류(optical flow) 또는 특징 벡터(feature vector)가 트래킹(tracking)될 수 있다. 또한, 트래킹 결과에서 신뢰성이 높은 광류 또는 특징 벡터가 검출될 수 있다. 제1 영상 시퀀스 및 제2 영상 시퀀스 각각의 광류 또는 특징 벡터는 시간 축 방향으로 프레임 간 대응 관계를 나타낸다.

도 19를 참조하면, 영상(1920)은 이전 프레임의 스테레오 영상이고, 영상(1930)은 현재 프레임의 스테레오 영상일 수 있다. 또한, 영상(1910)은 이전 프레임에서 영상(1920)이 스테레오 매칭된 결과 생성된 영상일 수 있다. 영상(1910)은 시차 맵(disparity map)이라고 지칭될 수 있다. 시차 맵은 시차 정보의 크기에 따라 영상의 밝기를 달리하는 영상이다. 예를 들어, 시차가 작은 픽셀의 밝기는 어둡게 설정되고, 시차가 큰 픽셀의 밝기는 밝게 설정될 수 있다.

이전 프레임에서 스테레오 매칭이 수행되고 이전 프레임에서 현재 프레임으로의 트래킹이 수행되었다고 가정하면, 현재 프레임의 기준 픽셀들이 생성될 수 있다. 예를 들어, 트래킹 결과 및 이전 프레임에서의 스테레오 매칭 결과를 이용하여, 현재 프레임의 영상(1930) 중 왼쪽 영상에 포함된 픽셀(1931)의 시차 정보가 계산될 수 있다. 이 경우, 픽셀(1931)은 기준 픽셀이 될 수 있다.

보다 구체적으로, 제1 영상 시퀀스의 트래킹 결과, 현재 프레임의 왼쪽 영상에 포함된 픽셀(1931)은 이전 프레임의 왼쪽 영상에 포함된 픽셀(1921)에 대응될 수 있다. 또한, 이전 프레임에서 스테레오 매칭이 수행된 결과, 픽셀(1921)은 픽셀(1922)에 매칭될 수 있다. 이 경우, 픽셀(1921)과 픽셀(1922) 사이에는 수학식 19와 같은 관계가 성립할 수 있다.

여기서, x_r ^t ^-1은 픽셀(1922)의 x축 좌표 또는 픽셀(1922)에 대응하는 시차 맵 내 픽셀(1912)의 x축 좌표이고, x_l ^t ^-1은 픽셀(1921)의 x축 좌표 또는 픽셀(1921)에 대응하는 시차 맵 내 픽셀(1911)의 x축 좌표이며, d_l ^t ^-1은 픽셀(1921)의 시차 정보이다.

또한, 제2 영상 시퀀스의 트래킹 결과, 이전 프레임의 오른쪽 영상에 포함된 픽셀(1922)은 현재 프레임의 오른쪽 영상에 포함된 픽셀(1932)에 대응될 수 있다. 픽셀(1931)은 픽셀(1921)에 대응되고, 픽셀(1921)은 픽셀(1922)에 대응되며, 픽셀(1922)은 픽셀(1932)에 대응되므로, 픽셀(1931)은 픽셀(1932)에 매칭될 수 있다. 그 결과, 픽셀(1931)의 시차 정보는 수학식 20과 같이 계산될 수 있다.

여기서, d_l ^t은 픽셀(1931)의 시차 정보이고, x_l ^t은 픽셀(1931)의 x축 좌표이며, x_r ^t은 픽셀(1932)의 x축 좌표이다. 픽셀(1931)의 시차 정보가 수학식 20에 의하여 계산되므로, 픽셀(1931)은 기준 픽셀로 이용될 수 있다.

스테레오 매칭을 위한 데이터 비용은 전술한 수학식 10 및 수학식 11과 같이 정의될 수 있다. 기준 픽셀의 데이터 비용 G_v(d)는 시간적 프라이어(temporal prior)라고 지칭될 수 있다.

도 20을 참조하면, 광류 또는 특징 벡터의 트래킹 결과를 완전히 신뢰하기 어려운 경우에도 현재 프레임에서 기준 픽셀이 생성될 수 있다. 영상(2020)은 이전 프레임의 스테레오 영상이고, 영상(2030)은 현재 프레임의 스테레오 영상일 수 있다. 또한, 영상(2010)은 이전 프레임에서 영상(2020)이 스테레오 매칭된 결과 생성된 영상일 수 있다.

이전 프레임에서 현재 프레임으로의 트래킹이 수행되었으나 트래킹 결과를 완전히 신뢰하기 어려운 경우, 현재 프레임의 하나의 픽셀은 이전 프레임의 복수의 픽셀들에 대응될 수 있다. 보다 구체적으로, 제1 영상 시퀀스의 트래킹 결과, 현재 프레임의 왼쪽 영상에 포함된 픽셀(2031)은 이전 프레임의 왼쪽 영상에 포함된 픽셀(2021) 및 픽셀(2022)에 대응될 수 있다.

이전 프레임에서 스테레오 매칭이 수행된 결과, 픽셀(2021)은 픽셀(2023)에 매칭되고, 픽셀(2022)는 픽셀(2024)에 매칭될 수 있다. 또는, 픽셀(2021)에 대응하는 시차 맵 내 픽셀(2011)은 시차 맵 내 픽셀(2013)에 매칭되고, 픽셀(2022)에 대응하는 시차 맵 내 픽셀(2012)는 시차 맵 내 픽셀(2014)에 매칭될 수 있다.

제2 영상 시퀀스의 트래킹 결과, 이전 프레임의 오른쪽 영상에 포함된 픽셀(2023) 및 픽셀(2024)는 각각 현재 프레임의 오른쪽 영상에 포함된 복수의 픽셀들에 대응될 수 있다.

일 예로, 제1 영상 시퀀스의 추적 결과의 신뢰도 및 제2 영상 시퀀스의 추적 결과의 신뢰도 중 적어도 하나에 기초하여, 픽셀(2031)과 매칭되는 픽셀이 결정될 수 있다. 예를 들어, 제1 영상 시퀀스의 추적 결과 픽셀(2031)과 대응되는 이전 프레임의 복수의 픽셀들 중 신뢰도가 가장 선택될 수 있다. 픽셀(2031)에 대응되는 이전 프레임의 복수의 픽셀들의 신뢰도는 픽셀(2031)과의 유사도에 기초하여 계산될 수 있다. 픽셀(2031)과의 유사도는 픽셀의 위치 정보 및/또는 픽셀의 인텐시티 정보에 기초하여 계산될 수 있다. 또한, 픽셀(2031)과의 유사도는 픽셀을 포함하는 패치(patch)의 유사도로 계산될 수 있다.

선택된 픽셀이 픽셀(2022)라고 가정하면, 픽셀(2022)는 이전 프레임에서의 스테레오 매칭 결과에 따라 픽셀(2024)에 대응될 수 있다. 픽셀(2024)는 현재 프레임에서의 픽셀(2032) 및 픽셀(2033)에 대응될 수 있다. 이 경우, 제2 영상 시퀀스의 추적 결과의 신뢰도에 기초하여 어느 하나의 픽셀이 선택될 수 있다. 픽셀(2024)에 대응되는 현재 프레임의 복수의 신뢰도는 픽셀(2024)와의 유사도에 기초하여 계산될 수 있다. 픽셀(2024)와의 유사도는 픽셀의 위치 정보 및/또는 픽셀의 인텐시티 정보에 기초하여 계산될 수 있다. 또한, 픽셀(2024)와의 유사도는 픽셀을 포함하는 패치의 유사도로 계산될 수 있다.

선택된 픽셀이 픽셀(2033)이라고 가정하면, 픽셀(2031)은 픽셀(2033)에 매칭된다. 이 경우, 픽셀(2031)의 시차 정보는 픽셀(2031)의 x축 좌표와 픽셀(2033)의 x축 좌표의 차이로 계산될 수 있다.

다른 예로, 제1 영상 시퀀스의 추적 결과의 신뢰도 및 제2 영상 시퀀스의 추적 결과의 신뢰도 중 적어도 하나에 기초하여, 데이터 비용을 위한 함수가 결정될 수 있다. 예를 들어, 현재 프레임의 픽셀 v에서 후보 시차 정보 d에 대응하는 데이터 비용은 수학식 21과 같이 정의될 수 있다.

여기서, g(d; patchsimilarity)는 제1 영상 시퀀스의 추적 결과의 신뢰도 및 제2 영상 시퀀스의 추적 결과의 신뢰도가 높을수록, 더 작은 값을 가지는 함수이다.

예를 들어, 현재 프레임의 왼쪽 영상에서 픽셀 v의 시차 정보를 계산하기 위하여 현재 프레임의 오른쪽 영상에서 픽셀 v의 x축 좌표로부터 후보 시차 정보 d만큼 떨어진 픽셀 u를 가정하자. 현재 프레임의 픽셀 v는 이전 프레임의 픽셀 v'에 대응되고, 이전 프레임의 픽셀 v'는 이전 프레임의 픽셀 u'에 대응되며, 이전 프레임의 픽셀 u'은 현재 프레임의 픽셀 u에 대응될 수 있다. 이 경우, g(d; patchsimilarity)는 제1 영상 시퀀스의 추적 결과의 신뢰도는 (픽셀 v, 픽셀 v') 대응 쌍의 신뢰도에 해당하고, 제2 영상 시퀀스의 추적 결과의 신뢰도는 (픽셀 u', 픽셀 u) 대응 쌍의 신뢰도에 해당할 수 있다.

스테레오 매칭을 위한 데이터 비용은 전술한 수학식 10 및 수학식 21과 같이 정의될 수 있다. 기준 픽셀의 데이터 비용 G_v(d)는 시간적 프라이어(temporal prior)라고 지칭될 수 있다.

전술한 실시예들은 다양한 방식으로 조합되거나 응용될 수 있다. 예를 들어, 스테레오 비디오의 첫 번째 프레임에 대하여 스테레오 매칭이 완료된 상태에서, 이후 프레임들의 스테레오 매칭을 위하여 전술한 실시예들이 조합되어 적용될 수 있다.

보다 구체적으로, 일 실시예에 따른 기준 픽셀의 생성 방법에 따라 첫 번째 프레임의 스테레오 매칭 정보에 기초하여 두 번째 프레임의 기준 픽셀 정보가 생성될 수 있다. 일 실시예에 따른 신장 트리 생성 방법에 따라 두 번째 프레임의 기준 픽셀 정보에 기초하여 두 번째 프레임을 위한 신장 트리가 생성될 수 있다. 일 실시예에 따른 스테레오 매칭 방법에 따라 두 번째 프레임을 위한 신장 트리에 기초하여 두 번째 프레임을 위한 스테레오 매칭이 수행될 수 있다. 전술한 과정은 이후 프레임들에도 그대로 적용될 수 있다.

실시예들에 따른 동작 흐름도의 설명

도 21 내지 도 25는 실시예들에 따른 동작 흐름도이다. 도 21을 참조하면, 일 실시예에 따른 신장 트리 생성 방법은 입력 영상을 위한 기준 픽셀들에 대한 정보를 수신하는 단계(2110) 및 기준 픽셀들에 대한 정보에 기초하여 상기 입력 영상에 포함된 픽셀들을 연결하는 신장 트리를 생성하는 단계(2120)을 포함한다.

도 22를 참조하면, 신장 트리를 생성하는 단계(2120)는 기준 픽셀들이 루트 노드가 되도록 서브 트리들을 생성하는 단계(2121) 및 서브 트리들 사이의 에지 비용들을 조절함으로써 서브 트리들을 연결하는 단계(2122)를 포함한다.

도 23을 참조하면, 일 실시예에 따른 스테레오 매칭 방법은 스테레오 매칭을 위한 제1 입력 영상과 제2 입력 영상을 수신하는 단계(2310), 제1 입력 영상에 포함된 픽셀들을 연결하는 신장 트리를 획득하는 단계(2320), 픽셀들 중 일반 픽셀들의 데이터 비용들, 픽셀들 중 기준 픽셀들의 데이터 비용들, 및 신장 트리에 포함된 에지들의 에지 비용들에 기초하여 픽셀들 중 어느 하나의 픽셀을 위한 복수의 후보 시차들에 대응하는 축적 데이터 비용들을 계산하는 단계(2330) 및 축적 데이터 비용들을 비교함으로써 복수의 후보 시차들 중 어느 하나의 후보 시차를 어느 하나의 픽셀의 시차로 결정하는 단계(2340)을 포함한다.

도 24를 참조하면, 일 실시예에 따른 업 샘플링 방법은 입력 영상에 포함된 픽셀들을 연결하는 신장 트리를 획득하는 단계(2410), 픽셀들 중 기준 픽셀들의 데이터 비용들 및 신장 트리에 포함된 에지들의 에지 비용들에 기초하여 픽셀들 중 어느 하나의 픽셀을 위한 복수의 후보 깊이들에 대응하는 축적 데이터 비용들을 계산하는 단계(2420) 및 축적 데이터 비용들을 비교함으로써 복수의 후보 깊이들 중 어느 하나의 후보 깊이를 어느 하나의 픽셀의 깊이로 결정하는 단계(2430)을 포함한다.

도 25를 참조하면, 일 실시예에 따른 기준 픽셀 생성 방법은 스테레오 비디오에 포함된 제1 영상 시퀀스 및 제2 영상 시퀀스를 추적하는 단계(2510) 및 제1 영상 시퀀스의 추적 결과, 제2 영상 시퀀스의 추적 결과 및 이전 프레임에서 스테레오 매칭된 결과에 기초하여 현재 프레임을 위한 기준 픽셀들을 생성하는 단계(2520)을 포함한다.

도 21 내지 도 25에 도시된 각 단계들에는 도 1 내지 도 20을 통하여 전술한 사항들이 그대로 적용될 수 있으므로, 보다 상세한 설명은 생략한다.

실시예들에 따른 블록도의 설명

도 26 내지 도 29는 실시예들에 따른 블록도이다. 도 26을 참조하면, 일 실시예에 따른 신장 트리 생성 장치(2600)는 수신부(2610) 및 생성부(2620)를 포함한다. 수신부(2610)는 입력 영상을 위한 기준 픽셀들에 대한 정보를 수신한다. 생성부(2620)는 기준 픽셀들에 대한 정보에 기초하여 입력 영상에 포함된 픽셀들을 연결하는 신장 트리를 생성한다.

도 27을 참조하면, 일 실시예에 따른 스테레오 매칭 장치(2700)는 수신부(2710), 획득부(2720), 계산부(2730), 및 결정부(2740)을 포함한다. 수신부(2710)는 스테레오 매칭을 위한 제1 입력 영상과 제2 입력 영상을 수신한다. 획득부(2720)는 제1 입력 영상에 포함된 픽셀들을 연결하는 신장 트리를 획득한다. 계산부(2730)은 픽셀들 중 일반 픽셀들의 데이터 비용들, 픽셀들 중 기준 픽셀들의 데이터 비용들 및 신장 트리에 포함된 에지들의 에지 비용들에 기초하여 픽셀들 중 어느 하나의 픽셀을 위한 복수의 후보 시차들에 대응하는 축적 데이터 비용들을 계산한다. 결정부(2740)는 축적 데이터 비용들을 비교함으로써 복수의 후보 시차들 중 어느 하나의 후보 시차를 어느 하나의 픽셀의 시차로 결정한다.

도 28을 참조하면, 일 실시예에 따른 업 샘플링 장치(2800)는 획득부(2810), 계산부(2820), 및 결정부(2830)를 포함한다. 획득부(2810)는 입력 영상에 포함된 픽셀들을 연결하는 신장 트리를 획득한다. 계산부(2820)는 픽셀들 중 기준 픽셀들의 데이터 비용들, 및 신장 트리에 포함된 에지들의 에지 비용들에 기초하여 픽셀들 중 어느 하나의 픽셀을 위한 복수의 후보 깊이들에 대응하는 축적 데이터 비용들을 계산한다. 결정부(2830)는 축적 데이터 비용들을 비교함으로써 복수의 후보 깊이들 중 어느 하나의 후보 깊이를 어느 하나의 픽셀의 깊이로 결정한다.

도 29를 참조하면, 일 실시예에 따른 기준 픽셀 생성 장치(2900)는 추적부(2910) 및 생성부(2920)를 포함한다. 추적부(2910)는 스테레오 비디오에 포함된 제1 영상 시퀀스 및 제2 영상 시퀀스를 추적한다. 생성부(2920)는 제1 영상 시퀀스의 추적 결과, 제2 영상 시퀀스의 추적 결과 및 이전 프레임에서 스테레오 매칭된 결과에 기초하여 현재 프레임을 위한 기준 픽셀들을 생성한다.

도 26 내지 도 29에 도시된 각 모듈들에는 도 1 내지 도 20을 통하여 전술한 사항들이 그대로 적용될 수 있으므로, 보다 상세한 설명은 생략한다.

이상에서 설명된 실시예들은 하드웨어 구성요소, 소프트웨어 구성요소, 및/또는 하드웨어 구성요소 및 소프트웨어 구성요소의 조합으로 구현될 수 있다. 예를 들어, 실시예들에서 설명된 장치, 방법 및 구성요소는, 예를 들어, 프로세서, 콘트롤러, ALU(arithmetic logic unit), 디지털 신호 프로세서(digital signal processor), 마이크로컴퓨터, FPGA(field programmable gate array), PLU(programmable logic unit), 마이크로프로세서, 또는 명령(instruction)을 실행하고 응답할 수 있는 다른 어떠한 장치와 같이, 하나 이상의 범용 컴퓨터 또는 특수 목적 컴퓨터를 이용하여 구현될 수 있다. 처리 장치는 운영 체제(OS) 및 상기 운영 체제 상에서 수행되는 하나 이상의 소프트웨어 애플리케이션을 수행할 수 있다. 또한, 처리 장치는 소프트웨어의 실행에 응답하여, 데이터를 접근, 저장, 조작, 처리 및 생성할 수도 있다. 이해의 편의를 위하여, 처리 장치는 하나가 사용되는 것으로 설명된 경우도 있지만, 해당 기술분야에서 통상의 지식을 가진 자는, 처리 장치가 복수 개의 처리 요소(processing element) 및/또는 복수 유형의 처리 요소를 포함할 수 있음을 알 수 있다. 예를 들어, 처리 장치는 복수 개의 프로세서 또는 하나의 프로세서 및 하나의 콘트롤러를 포함할 수 있다. 또한, 병렬 프로세서(parallel processor)와 같은, 다른 처리 구성(processing configuration)도 가능하다.

소프트웨어는 컴퓨터 프로그램(computer program), 코드(code), 명령(instruction), 또는 이들 중 하나 이상의 조합을 포함할 수 있으며, 원하는 대로 동작하도록 처리 장치를 구성하거나 독립적으로 또는 결합적으로(collectively) 처리 장치를 명령할 수 있다. 소프트웨어 및/또는 데이터는, 처리 장치에 의하여 해석되거나 처리 장치에 명령 또는 데이터를 제공하기 위하여, 어떤 유형의 기계, 구성요소(component), 물리적 장치, 가상 장치(virtual equipment), 컴퓨터 저장 매체 또는 장치, 또는 전송되는 신호 파(signal wave)에 영구적으로, 또는 일시적으로 구체화(embody)될 수 있다. 소프트웨어는 네트워크로 연결된 컴퓨터 시스템 상에 분산되어서, 분산된 방법으로 저장되거나 실행될 수도 있다. 소프트웨어 및 데이터는 하나 이상의 컴퓨터 판독 가능 기록 매체에 저장될 수 있다.

실시예에 따른 방법은 다양한 컴퓨터 수단을 통하여 수행될 수 있는 프로그램 명령 형태로 구현되어 컴퓨터 판독 가능 매체에 기록될 수 있다. 상기 컴퓨터 판독 가능 매체는 프로그램 명령, 데이터 파일, 데이터 구조 등을 단독으로 또는 조합하여 포함할 수 있다. 상기 매체에 기록되는 프로그램 명령은 실시예를 위하여 특별히 설계되고 구성된 것들이거나 컴퓨터 소프트웨어 당업자에게 공지되어 사용 가능한 것일 수도 있다. 컴퓨터 판독 가능 기록 매체의 예에는 하드 디스크, 플로피 디스크 및 자기 테이프와 같은 자기 매체(magnetic media), CD-ROM, DVD와 같은 광기록 매체(optical media), 플롭티컬 디스크(floptical disk)와 같은 자기-광 매체(magneto-optical media), 및 롬(ROM), 램(RAM), 플래시 메모리 등과 같은 프로그램 명령을 저장하고 수행하도록 특별히 구성된 하드웨어 장치가 포함된다. 프로그램 명령의 예에는 컴파일러에 의해 만들어지는 것과 같은 기계어 코드뿐만 아니라 인터프리터 등을 사용해서 컴퓨터에 의해서 실행될 수 있는 고급 언어 코드를 포함한다. 상기된 하드웨어 장치는 실시예의 동작을 수행하기 위해 하나 이상의 소프트웨어 모듈로서 작동하도록 구성될 수 있으며, 그 역도 마찬가지이다.

이상과 같이 실시예들이 비록 한정된 실시예와 도면에 의해 설명되었으나, 해당 기술분야에서 통상의 지식을 가진 자라면 상기의 기재로부터 다양한 수정 및 변형이 가능하다. 예를 들어, 설명된 기술들이 설명된 방법과 다른 순서로 수행되거나, 및/또는 설명된 시스템, 구조, 장치, 회로 등의 구성요소들이 설명된 방법과 다른 형태로 결합 또는 조합되거나, 다른 구성요소 또는 균등물에 의하여 대치되거나 치환되더라도 적절한 결과가 달성될 수 있다. 그러므로, 다른 구현들, 다른 실시예들 및 특허청구범위와 균등한 것들도 후술하는 특허청구범위의 범위에 속한다.

Claims

입력 영상을 위한 기준 픽셀들에 대한 정보를 수신하는 단계; 및
상기 기준 픽셀들에 대한 정보에 기초하여, 상기 입력 영상에 포함된 픽셀들을 연결하는 신장 트리를 생성하는 단계
를 포함하는 신장 트리 생성 방법.
제1항에 있어서,
상기 기준 픽셀들은
상기 입력 영상에 포함된 일반 픽셀들에 비하여 추가 정보를 더 포함하는, 신장 트리 생성 방법.
제2항에 있어서,
상기 추가 정보는
시차(disparity) 정보 및 깊이(depth) 정보 중 적어도 하나를 포함하는, 신장 트리 생성 방법.
제2항에 있어서,
상기 일반 픽셀들 각각은
인텐시티(intensity) 정보 및 위치 정보 중 적어도 하나를 포함하는, 신장 트리 생성 방법.
제1항에 있어서,
상기 신장 트리는
상기 입력 영상에 포함된 픽셀들을 최소 비용으로 연결하는 최소 신장 트리를 포함하는, 신장 트리 생성 방법.
제1항에 있어서,
상기 신장 트리는
복수의 서브 트리들을 포함하고, 상기 복수의 서브 트리들 각각은 상호 연관성이 높은 픽셀들을 포함하며, 상기 복수의 서브 트리들은 페널티(penalty)가 부과된 에지로 연결되는, 신장 트리 생성 방법.
제1항에 있어서,
상기 신장 트리를 생성하는 단계는
상기 기준 픽셀들이 루트 노드가 되도록 서브 트리들을 생성하는 단계; 및
상기 서브 트리들 사이의 에지 비용들을 조절함으로써, 상기 서브 트리들을 연결하는 단계
를 포함하는, 신장 트리 생성 방법.
제7항에 있어서,
상기 서브 트리들을 생성하는 단계는
상기 입력 영상에 포함된 픽셀들에 기초하여 후보 픽셀 쌍들을 결정하는 단계;
상기 후보 픽셀 쌍들의 에지 비용들을 계산하는 단계;
상기 에지 비용들의 크기에 따라 순차적으로 후보 픽셀 쌍을 선택하는 단계; 및
상기 선택된 후보 픽셀 쌍에 포함된 제1 픽셀이 속하는 제1 서브 트리와 상기 선택된 후보 픽셀 쌍에 포함된 제2 픽셀이 속하는 제2 서브 트리에 기초하여, 상기 제1 픽셀과 상기 제2 픽셀의 연결여부를 결정하는 단계
를 포함하는, 신장 트리 생성 방법.
제8항에 있어서,
상기 후보 픽셀 쌍들의 에지 비용들을 계산하는 단계는
상기 후보 픽셀 쌍들 중 어느 하나의 후보 픽셀 쌍에 포함된 두 픽셀들의 밝기 정보, 및 위치 정보 중 적어도 하나에 기초하여 상기 두 픽셀들 사이의 에지 비용을 계산하는 단계
를 포함하는, 신장 트리 생성 방법.
제8항에 있어서,
상기 제1 픽셀과 상기 제2 픽셀의 연결여부를 결정하는 단계는
상기 제1 서브 트리의 제1 루트 노드가 기준 픽셀인지 여부, 상기 제2 서브 트리의 제2 루트 노드가 기준 픽셀인지 여부, 및 상기 제1 픽셀과 상기 제2 픽셀 사이의 에지 비용에 기초하여 상기 제1 픽셀과 상기 제2 픽셀을 연결하는 단계
를 포함하는, 신장 트리 생성 방법.
제8항에 있어서,
상기 제1 픽셀과 상기 제2 픽셀의 연결여부를 결정하는 단계는
상기 제1 서브 트리의 제1 루트 노드가 기준 픽셀이고, 상기 제2 서브 트리의 제2 루트 노드가 기준 픽셀인 경우, 상기 제1 픽셀과 상기 제2 픽셀을 연결하지 않는 단계
를 포함하는, 신장 트리 생성 방법.
제8항에 있어서,
상기 제1 픽셀과 상기 제2 픽셀의 연결여부를 결정하는 단계는
상기 제1 서브 트리의 제1 루트 노드가 기준 픽셀이고, 상기 제2 서브 트리의 제2 루트 노드가 기준 픽셀이 아니며, 상기 제1 픽셀과 상기 제2 픽셀 사이의 에지 비용이 상기 제1 서브 트리의 임계 비용 및 상기 제2 서브 트리의 임계 비용보다 작은 경우, 상기 제1 픽셀과 상기 제2 픽셀을 연결하는 단계; 및
상기 제1 픽셀과 상기 제2 픽셀의 연결로 인하여 생성되는 제3 서브 트리의 제3 루트 노드를 제1 루트 노드로 설정하는 단계
를 포함하는, 신장 트리 생성 방법.
제8항에 있어서,
상기 제1 픽셀과 상기 제2 픽셀의 연결여부를 결정하는 단계는
상기 제1 서브 트리의 제1 루트 노드가 기준 픽셀이 아니고, 상기 제2 서브 트리의 제2 루트 노드가 기준 픽셀이 아니며, 상기 제1 픽셀과 상기 제2 픽셀 사이의 에지 비용이 상기 제1 서브 트리의 임계 비용 및 상기 제2 서브 트리의 임계 비용보다 작은 경우, 상기 제1 픽셀과 상기 제2 픽셀을 연결하는 단계; 및
상기 제1 픽셀과 상기 제2 픽셀의 연결로 인하여 생성되는 제3 서브 트리의 깊이가 작아지도록, 상기 제3 서브 트리의 제3 루트 노드를 상기 제1 루트 노드 및 상기 제2 루트 노드 중 어느 하나로 설정하는 단계
를 포함하는, 신장 트리 생성 방법.
제7항에 있어서,
상기 서브 트리들을 연결하는 단계는
상기 서브 트리들에 기초하여 후보 서브 트리 쌍들을 결정하는 단계;
상기 후보 서브 트리 쌍들의 에지 비용들을 계산하는 단계;
상기 에지 비용들의 크기에 따라 순차적으로 후보 서브 트리 쌍을 선택하는 단계; 및
상기 선택된 후보 서브 트리 쌍에 포함된 제1 서브 트리와 상기 선택된 후보 서브 트리 쌍에 포함된 제2 서브 트리에 기초하여, 상기 제1 서브 트리와 상기 제2 서브 트리의 연결여부를 결정하는 단계
를 포함하는, 신장 트리 생성 방법.
제14항에 있어서,
상기 후보 서브 트리 쌍들의 에지 비용들을 계산하는 단계는
상기 후보 서브 트리 쌍들 중 어느 하나의 후보 서브 트리 쌍에 포함된 두 서브 트리들의 두 루트 노드들이 기준 픽셀들인 경우, 상기 두 루트 노드들의 밝기 정보, 위치 정보, 시차 정보, 및 깊이 정보 중 적어도 하나에 기초하여 상기 두 루트 노드들 사이의 에지 비용을 계산하는 단계
를 포함하는, 신장 트리 생성 방법.
제14항에 있어서,
상기 후보 서브 트리 쌍들의 에지 비용들을 계산하는 단계는
상기 후보 서브 트리 쌍들 중 어느 하나의 후보 서브 트리 쌍에 포함된 두 서브 트리들의 두 루트 노드들 중 적어도 하나가 기준 픽셀이 아닌 경우, 상기 두 루트 노드들의 밝기 정보, 및 위치 정보 중 적어도 하나에 기초하여 상기 두 루트 노드들 사이의 에지 비용을 계산하는 단계
를 포함하는, 신장 트리 생성 방법.
제14항에 있어서,
상기 제1 서브 트리와 상기 제2 서브 트리의 연결여부를 결정하는 단계는
상기 제1 서브 트리의 제1 루트 노드가 기준 픽셀인지 여부, 상기 제2 서브 트리의 제2 루트 노드가 기준 픽셀인지 여부, 및 상기 제1 루트 노드와 상기 제2 루트 노드 사이의 에지 비용에 기초하여 상기 제1 서브 트리와 상기 제2 서브 트리를 연결하는 단계
를 포함하는, 신장 트리 생성 방법.
제14항에 있어서,
상기 제1 서브 트리와 상기 제2 서브 트리의 연결여부를 결정하는 단계는
상기 제1 서브 트리의 제1 루트 노드가 기준 픽셀이고, 상기 제2 서브 트리의 제2 루트 노드가 기준 픽셀이며, 상기 제1 루트 노드와 상기 제2 루트 노드 사이의 에지 비용이 상기 제1 서브 트리의 임계 비용 및 상기 제2 서브 트리의 임계 비용보다 작은 경우, 상기 제1 루트 노드와 상기 제2 루트 노드를 연결하는 단계; 및
상기 제1 루트 노드와 상기 제2 루트 노드의 연결로 인하여 생성되는 제3 서브 트리의 깊이가 작아지도록, 상기 제3 서브 트리의 제3 루트 노드를 상기 제1 루트 노드 및 상기 제2 루트 노드 중 어느 하나로 설정하는 단계
를 포함하는, 신장 트리 생성 방법.
제14항에 있어서,
상기 제1 서브 트리와 상기 제2 서브 트리의 연결여부를 결정하는 단계는
상기 제1 서브 트리의 제1 루트 노드가 기준 픽셀이고, 상기 제2 서브 트리의 제2 루트 노드가 기준 픽셀이며, 상기 제1 루트 노드와 상기 제2 루트 노드 사이의 에지 비용이 상기 제1 서브 트리의 임계 비용 및 상기 제2 서브 트리의 임계 비용 이상인 경우, 상기 제1 루트 노드와 상기 제2 루트 노드 사이의 에지 비용을 증가시키면서 상기 제1 루트 노드와 상기 제2 루트 노드를 연결하는 단계; 및
상기 제1 루트 노드와 상기 제2 루트 노드의 연결로 인하여 생성되는 제3 서브 트리의 깊이가 작아지도록, 상기 제3 서브 트리의 제3 루트 노드를 상기 제1 루트 노드 및 상기 제2 루트 노드 중 어느 하나로 설정하는 단계
를 포함하는, 신장 트리 생성 방법.
제14항에 있어서,
상기 제1 서브 트리와 상기 제2 서브 트리의 연결여부를 결정하는 단계는
상기 제1 서브 트리의 제1 루트 노드가 기준 픽셀이고, 상기 제2 서브 트리의 제2 루트 노드가 기준 픽셀이 아닌 경우, 상기 제1 루트 노드와 상기 제2 루트 노드 사이의 에지 비용을 증가시키면서 상기 제1 루트 노드와 상기 제2 루트 노드를 연결하는 단계; 및
상기 제1 루트 노드와 상기 제2 루트 노드의 연결로 인하여 생성되는 제3 서브 트리의 제3 루트 노드를 상기 제1 루트 노드로 설정하는 단계
를 포함하는, 신장 트리 생성 방법.
제14항에 있어서,
상기 제1 서브 트리와 상기 제2 서브 트리의 연결여부를 결정하는 단계는
상기 제1 서브 트리의 제1 루트 노드가 기준 픽셀이 아니고, 상기 제2 서브 트리의 제2 루트 노드가 기준 픽셀이 아닌 경우, 상기 제1 루트 노드와 상기 제2 루트 노드 사이의 에지 비용을 증가시키면서 상기 제1 루트 노드와 상기 제2 루트 노드를 연결하는 단계; 및
상기 제1 루트 노드와 상기 제2 루트 노드의 연결로 인하여 생성되는 제3 서브 트리의 깊이가 작아지도록, 상기 제3 서브 트리의 제3 루트 노드를 상기 제1 루트 노드 및 상기 제2 루트 노드 중 어느 하나로 설정하는 단계
를 포함하는, 신장 트리 생성 방법.
스테레오 매칭을 위한 제1 입력 영상과 제2 입력 영상을 수신하는 단계;
상기 제1 입력 영상에 포함된 픽셀들을 연결하는 신장 트리를 획득하는 단계;
상기 픽셀들 중 일반 픽셀들의 데이터 비용들, 상기 픽셀들 중 기준 픽셀들의 데이터 비용들, 및 상기 신장 트리에 포함된 에지들의 에지 비용들에 기초하여, 상기 픽셀들 중 어느 하나의 픽셀을 위한 복수의 후보 시차들에 대응하는 축적 데이터 비용들을 계산하는 단계; 및
상기 축적 데이터 비용들을 비교함으로써, 상기 복수의 후보 시차들 중 어느 하나의 후보 시차를 상기 어느 하나의 픽셀의 시차(disparity)로 결정하는 단계
를 포함하는 스테레오 매칭 방법.
제22항에 있어서,
상기 기준 픽셀들은
상기 일반 픽셀들에 비하여 시차 정보를 더 포함하는, 스테레오 매칭 방법.
제22항에 있어서,
상기 신장 트리는
복수의 서브 트리들을 포함하고, 상기 복수의 서브 트리들 각각은 상호 연관성이 높은 픽셀들을 포함하며, 상기 복수의 서브 트리들은 페널티(penalty)가 부과된 에지로 연결되는, 스테레오 매칭 방법.
제22항에 있어서,
상기 일반 픽셀들 중 어느 하나의 일반 픽셀의 데이터 비용은
상기 일반 픽셀의 밝기 정보, 및 상기 제2 입력 영상에서 상기 일반 픽셀에 대응되는 픽셀로부터 후보 시차만큼 이격된 픽셀의 밝기 정보에 기초하여 계산되는, 스테레오 매칭 방법.
제22항에 있어서,
상기 기준 픽셀들 중 어느 하나의 기준 픽셀의 데이터 비용은
상기 기준 픽셀의 시차 정보, 및 후보 시차에 기초하여 계산되는, 스테레오 매칭 방법.
제26항에 있어서,
상기 기준 픽셀의 데이터 비용은
상기 기준 픽셀의 밝기 정보, 및 상기 제2 입력 영상에서 상기 기준 픽셀에 대응되는 픽셀로부터 후보 시차만큼 이격된 픽셀의 밝기 정보에 더 기초하여 계산되는, 스테레오 매칭 방법.
제22항에 있어서,
상기 복수의 후보 시차들 중 어느 하나의 후보 시차에 대응하는 축적 데이터 비용은
상기 후보 시차에 대응하는 상기 픽셀들의 데이터 비용들을 가중 합산(weighted sum)함으로써 계산되는, 스테레오 매칭 방법.
제28항에 있어서,
상기 가중 합산을 위한 상기 픽셀들의 가중치들은
상기 신장 트리에서 상기 어느 하나의 픽셀과 나머지 픽셀들을 연결하는 경로들에 대응하는 에지 비용들에 기초하여 계산되는, 스테레오 매칭 방법.
입력 영상에 포함된 픽셀들을 연결하는 신장 트리를 획득하는 단계;
상기 픽셀들 중 기준 픽셀들의 데이터 비용들, 및 상기 신장 트리에 포함된 에지들의 에지 비용들에 기초하여, 상기 픽셀들 중 어느 하나의 픽셀을 위한 복수의 후보 깊이들에 대응하는 축적 데이터 비용들을 계산하는 단계; 및
상기 축적 데이터 비용들을 비교함으로써, 상기 복수의 후보 깊이들 중 어느 하나의 후보 깊이를 상기 어느 하나의 픽셀의 깊이로 결정하는 단계
를 포함하는 업 샘플링 방법.
제30항에 있어서,
상기 기준 픽셀들은
상기 입력 영상에 포함된 일반 픽셀들에 비하여 깊이 정보를 더 포함하는, 업 샘플링 방법.
제30항에 있어서,
상기 신장 트리는
복수의 서브 트리들을 포함하고, 상기 복수의 서브 트리들 각각은 상호 연관성이 높은 픽셀들을 포함하며, 상기 복수의 서브 트리들은 페널티(penalty)가 부과된 에지로 연결되는, 업 샘플링 방법.
제30항에 있어서,
상기 기준 픽셀들 중 어느 하나의 기준 픽셀의 데이터 비용은
상기 기준 픽셀의 깊이 정보, 및 후보 깊이에 기초하여 계산되는, 업 샘플링 방법.
제30항에 있어서,
상기 복수의 후보 깊이들 중 어느 하나의 후보 깊이에 대응하는 축적 데이터 비용은
상기 후보 깊이에 대응하는 상기 픽셀들의 데이터 비용들을 가중 합산(weighted sum)함으로써 계산되는, 업 샘플링 방법.
제34항에 있어서,
상기 가중 합산을 위한 상기 픽셀들의 가중치들은
상기 신장 트리에서 상기 어느 하나의 픽셀과 나머지 픽셀들을 연결하는 경로들에 대응하는 에지 비용들에 기초하여 계산되는, 업 샘플링 방법.
스테레오 비디오에 포함된 제1 영상 시퀀스 및 제2 영상 시퀀스를 추적하는 단계; 및
상기 제1 영상 시퀀스의 추적 결과, 상기 제2 영상 시퀀스의 추적 결과, 및 이전 프레임에서 스테레오 매칭된 결과에 기초하여, 현재 프레임을 위한 기준 픽셀들을 생성하는 단계
를 포함하는 기준 픽셀 생성 방법.
제36항에 있어서,
상기 추적하는 단계는
상기 제1 영상 시퀀스의 광류(optical flow) 및 상기 제2 영상 시퀀스의 광류를 추적하는 단계; 및
상기 제1 영상 시퀀스의 특징 벡터(feature vector) 및 상기 제2 영상 시퀀스의 특징 벡터를 추적하는 단계
중 적어도 하나를 포함하는, 기준 픽셀 생성 방법.
제36항에 있어서,
상기 기준 픽셀들을 생성하는 단계는
상기 제1 영상 시퀀스의 추적 결과에 기초하여, 상기 제1 영상 시퀀스의 현재 프레임의 제1 픽셀에 대응하는 상기 제1 영상 시퀀스의 이전 프레임의 제2 픽셀을 결정하는 단계;
상기 제2 픽셀의 시차 정보에 기초하여, 상기 제2 픽셀에 대응하는 상기 제2 영상 시퀀스의 상기 이전 프레임의 제3 픽셀을 결정하는 단계;
상기 제2 영상 시퀀스의 추적 결과에 기초하여, 상기 제3 픽셀에 대응하는 상기 제2 영상 시퀀스의 상기 현재 프레임의 제4 픽셀을 결정하는 단계; 및
상기 제4 픽셀에 기초하여 상기 제1 픽셀의 시차 정보를 계산하는 단계
를 포함하는, 기준 픽셀 생성 방법.
제36항에 있어서,
상기 기준 픽셀들을 생성하는 단계는
상기 제1 영상 시퀀스의 추적 결과에 기초하여, 상기 제1 영상 시퀀스의 현재 프레임의 제1 픽셀에 대응하는 상기 제1 영상 시퀀스의 이전 프레임의 제2 픽셀들을 결정하는 단계;
상기 제2 픽셀들의 시차 정보에 기초하여, 상기 제2 픽셀들에 대응하는 상기 제2 영상 시퀀스의 상기 이전 프레임의 제3 픽셀들을 결정하는 단계;
상기 제2 영상 시퀀스의 추적 결과에 기초하여, 상기 제3 픽셀들에 대응하는 상기 제2 영상 시퀀스의 상기 현재 프레임의 제4 픽셀들을 결정하는 단계;
상기 제1 영상 시퀀스의 추적 결과의 신뢰도 및 상기 제2 영상 시퀀스의 추적 결과의 신뢰도 중 적어도 하나에 기초하여, 상기 제4 픽셀들 중 어느 하나의 픽셀을 선택하는 단계; 및
상기 선택된 픽셀에 기초하여 상기 제1 픽셀의 시차 정보를 계산하는 단계
를 포함하는, 기준 픽셀 생성 방법.
제1항 내지 제39항 중에서 어느 하나의 항의 방법을 실행시키기 위한 프로그램이 기록된 컴퓨터 판독 가능한 기록 매체.
입력 영상을 위한 기준 픽셀들에 대한 정보를 수신하는 수신부; 및
상기 기준 픽셀들에 대한 정보에 기초하여, 상기 입력 영상에 포함된 픽셀들을 연결하는 신장 트리를 생성하는 생성부
를 포함하는 신장 트리 생성 장치.
스테레오 매칭을 위한 제1 입력 영상과 제2 입력 영상을 수신하는 수신부;
상기 제1 입력 영상에 포함된 픽셀들을 연결하는 신장 트리를 획득하는 획득부;
상기 픽셀들 중 일반 픽셀들의 데이터 비용들, 상기 픽셀들 중 기준 픽셀들의 데이터 비용들, 및 상기 신장 트리에 포함된 에지들의 에지 비용들에 기초하여, 상기 픽셀들 중 어느 하나의 픽셀을 위한 복수의 후보 시차들에 대응하는 축적 데이터 비용들을 계산하는 계산부; 및
상기 축적 데이터 비용들을 비교함으로써, 상기 복수의 후보 시차들 중 어느 하나의 후보 시차를 상기 어느 하나의 픽셀의 시차(disparity)로 결정하는 결정부
를 포함하는 스테레오 매칭 장치.
입력 영상에 포함된 픽셀들을 연결하는 신장 트리를 획득하는 획득부;
상기 픽셀들 중 기준 픽셀들의 데이터 비용들, 및 상기 신장 트리에 포함된 에지들의 에지 비용들에 기초하여, 상기 픽셀들 중 어느 하나의 픽셀을 위한 복수의 후보 깊이들에 대응하는 축적 데이터 비용들을 계산하는 계산부; 및
상기 축적 데이터 비용들을 비교함으로써, 상기 복수의 후보 깊이들 중 어느 하나의 후보 깊이를 상기 어느 하나의 픽셀의 깊이로 결정하는 결정부
를 포함하는 업 샘플링 장치.
스테레오 비디오에 포함된 제1 영상 시퀀스 및 제2 영상 시퀀스를 추적하는 추적부; 및
상기 제1 영상 시퀀스의 추적 결과, 상기 제2 영상 시퀀스의 추적 결과, 및 이전 프레임에서 스테레오 매칭된 결과에 기초하여, 현재 프레임을 위한 기준 픽셀들을 생성하는 생성부
를 포함하는 기준 픽셀 생성 장치.