KR20000068660A - 3차원 장면 재구성 방법과 재구성 장치 및 디코딩 시스템 - Google Patents

Abstract

본 발명은 3차원 장면 재구성의 새로운 방법에 관한 것이다. 종래의 방법은 종종 관련된 물체의 경계 부피의 3D 재구성에 제한되는 반면, 각각의 뷰에서 숨겨진 부분에 대한 정보를 제공하는, 단일의 카메라에 의해 취해진 2D 뷰로부터 3D 기하학적 모델의 복원의 제안된 방법은 초기화 및 프로젝션 부단계와 후속하는 개선 프로세스를 포함하는 부시스템(11)에서 구현되는 제 1의 깊이 라벨링 단계, 및 부시스템(12)에서 구현되는 제 2의 재구성 단계에 따라 구현된다. 장면이 두 뷰에 대해 얻어진 3D 깊이 맵의 근접한 좌표에 의해, 3D 모델이 식별되고 추출된다. 멀디미디어 서비스에서 부가적인 기능의 응용이 있다.

Description

3차원 장면 재구성 방법과 재구성 장치 및 디코딩 시스템{Method of reconstruction of tridimensional scenes and corresponding reconstruction device and decoding system}

본 발명은 N 개의 연속하는 실제 장면(real scene)의 이미지에 대응하는 2차원 비디오 시퀀스로부터 3차원 장면을 재구성하는 방법과, 그 재구성 장치 및 디코딩 시스템에 관한 것이다.

최근의 기술적 경향에서(그리고 시간과 공간에서 소정의 관계를 갖는 객체로서의 그래픽과 비디오 자료를 인코딩하기 위한 수단을 제공하기 위해 의도된 미래의 MPEG-4 표준안에 관련된 모든 관점에서) 입체 이미지(stereo image)와 가상 환경에 관련된 모든 것은, 예를 들면 엔지니어링, 디자인 또는 제조업에서 중요한 툴이 되고 있다. 두 개의 약간 상이한 조망 각도(view angles)에서 동일한 장면을 기록함으로써 일반적으로 생성되는 입체 이미지는 상기 이미지가 쌍으로 고려되고 입체 쌍의 각 이미지가 각각의 눈에 의해 관측되는 경우 3차원(3D)으로 인식된다. 또한, 이러한 입체 및 가상 현실의 상황에서, 생성되는 환경으로의 자유로운 워크스루(free walkthrough)가 요구되고 가능하다. 이러한 가상 환경의 생성은, 통상적으로 하기의 단계에 따른 화상 합성 툴(picture synthesis tools)에 의해 수행된다:

(a) (예를 들면, 상 표현(facet representation)을 사용함으로써) 관련된 장면의 3D 기하학적 모델의 복원 단계;

(b) 특정 관점에 따른 장면을 계산하고 모든 공지의 요소(예를 들면, 빛, 상(facet)의 반사 특성, 실제 장면의 요소 사이의 일치 등등)를 고려하기 위해 제공되는 렌더링 단계.

그러나, 장면의 3D 기하학적 모델의 재구성은 모든 유효한 장면 사이의 이미지 매칭을 수행하는 것을 필요로 한다. "Multiframe image point matching and 3D sruface reconstruction"(R.Y.Tsai, IEEE Trans. on Pattern Analysis and Machine Intelligence, vol.PAMI-5, n^o2, March 1983,pp.159-174)의 문헌에서, 이러한 일치 문제점은 (입력 화상의 샘플링 그리드에 대응하는 축을 따라, 한정된 검색 윈도우(search window) 내에서) 한 번의 단일의 과정(pass)에서 모든 다른 장면의 정보를 고려하는 상관 함수를 계산하여, 이러한 방식으로 노이즈와 주기적인 구조에 대해 보다 확고한 방법을 제공함으로써 해결된다. 이러한 함수의 극소는 검색 윈도우 중앙에서 픽셀의 깊이의 평가를 제공한다. 불행하게도, 이러한 깊이 평가는 샘플링 그리드에 대해 비선형 의존성(가장 간단한 경우에 1/x)을 갖는다. 또한, 한 화상으로부터 얻어진 표면에 대한 깊이 맵 평가는 다른 화상으로부터 얻어진 동일한 표면의 깊이 맵 평가와 쉽게 비교될 수 없는데, 그 이유는 이들이 동일한 기준 그리드를 공유하지 않기 때문이다(이들은 각각의 화상 샘플링 그리드에만 참조된다).

본 발명의 목적은 이러한 결점을 더 이상 나타내지 않는 장면 재구성 방법을 제공하는 것이다.

이 때문에 본 발명은 본원의 서두에서 규정된 재구성 방법에 관련되며, 각각의 이미지에 대해, 3각형 영역으로 분할된, 일련의 시퀀스에서,

(A) 각각의 장면이 연속하는 3D 시트의 프로젝션으로 간주되고, 상기 3D 시트의 깊이 맵에 대응하는 불일치 맵을 얻기 위해서 다중-장면 매칭이 각각의 장면에 대해 독립적으로 수행되는 제 1의 깊이 라벨링 단계와;

(B) 3D 공간의 옥트리 구획(octree subdivision)이 수행되고 모든 3D 깊이 시트(depth sheet)의 교차점에 놓여 있는 복셀(voxels)(부피 요소)이 유지되는 제 2의 3D 모델 추출 단계를 포함한다. 옥트리는 경계 입방체(bounding cube)에 의해 둘러싸이고 각각의 입방체를, 단일의 큰 입방체인 루트 노드에서 시작하는 8개의 부입방체(subcubes)로 반복적으로 분할함으로써 구성되는 2진값 용적 측정 데이터(binary volumetric data)의 집합을 설명하기 위해 사용되는 트리 구조의 표현이다: 옥트리는 통상적인 객체의 인접한 복셀 사이에 큰 일관성이 존재하기 때문에 많은 용적 측정의 객체에 대해 유효한 표현이다.

이러한 접근으로, 3D 세계 좌표 시스템에서 깊이의 샘플링 값에 대응하는 축을 따른 상관 함수(사용자에 의해 임의적으로 제공되는 깊이 샘플링 그리드(depth sampling grid)를 구성한다)는 모든 장면을 고려하여 계산되고, 이 함수의 최소는 상기 좌표 시스템에서의 깊이의 적절한 값에 직접적으로 관련된다(이것은 다중 깊이 측정이 상이한 관점(view point)으로부터 얻어질 때 아주 유익하다). 깊이 샘플링 그리드는 사용자에 의해 임의적으로 제공되며 재구성된 표면에 대한 약간의 사전 지식을 고려하여 규칙적으로 간격을 가지고 선택된다(예를 들면 상기 표면이 실내 장면의 경우와 같이 소정의 경계 박스 내에 놓여 있는 경우).

미국 특허 제 5,598515호는 다수의 2차원 장면 이미지로부터 이러한 장면의 요소 또는 3차원 장면을, 복잡한 절차에 따라 재구성하는 시스템 및 방법을 상술하는데, 본 발명의 경우, 상기 복잡한 절차는 수렴이 얻어질 때까지 연속하는 개선(successive refinements)에 제공되는 아주 단순한 절차에 의해 대체된다.

본 발명에 따르면, 상기 깊이 라벨링 단계는 관련된 이미지에 대한 예비 3D 깊이 시트를 제 1의 반복동안 정의하기 위해 제공되는 초기화 부단계, 및 각각의 영역의 각각의 정점(vertex)에 대해, 상기 정점에 대해 특별하게 정의된 윈도우 상의 각각의 (N-1) 쌍의 장면 사이의 상관 비용의 합에 대응하는 각각의 샘플링된 깊이에 대한 에러 벡터를 정의하고 최소 상관 비용을 제공하는 인덱스를 저장하기 위한 개선 부단계를 연속적으로 포함하고, 상기 제 1의 반복 이후에 상기 초기화 부단계를 이미지 평면 근처의 정점 맵과 파라미터에 따른 이미지 획득 장치의 위치와 시야(field of view)를 먼저 조정하고 그 다음 각각의 정점에 대해 상기 획득 장치의 광학 중심과 상기 정점을 통과하는 라인을 교차하는 복셀을 조망 방향에서 열거하며, 상기 이미지 평면에 가장 가까운 복셀을 선택하기 위한 프로젝션 부단계로 대체하기 위해 의도된 부가적인 단계를 포함하는 것이 바람직하다.

본 발명의 다른 목적은 이러한 방법을 실행하는 재구성 장치를 제안하는 것이다.

이 때문에, 본 발명은 실제 장면의 N 개의 연속하는 이미지에 대응하는 2 차원 비디오 시퀀스로부터 3 차원 장면을 재구성하기 위한 장치에 관련되는데,

(Ⅰ) 상기 시퀀스의 N 개의 이미지의 각각은 3각형 영역으로 분할되고;

(Ⅱ) 상기 장치는, 상기 시퀀스의 각각의 이미지를 처리하기 위해,

(A) 깊이 라벨링 부시스템으로서,

(1) 제 1의 반복동안 각각의 (N-1) 쌍의 장면 사이의 상관 비용의 합에 대응하는 샘플링된 깊이에 대한 에러 벡터와 최소 상관 비용을 제공하는 인덱스를 정의하기 위해 제공된 초기화 장치로서, 상기 영역의 각각의 정점의 깊이 값은 이웃하는 영역에 대해 얻어진 깊이 사이의 보간에 의해 계산되는 상기 초기화 장치와;

(2) 각각의 정점의 정점에 대해 이전에 범위가 정해진 윈도우 상의 에러 벡터와, 최소 상관 비용을 제공하는 인덱스를 정의하기 위해 제공되는 개선 장치를 연속하여 포함하는 상기 깊이 라벨링 부시스템과;

(B) 복셀 그리드의 해상도를 선택하고, 각각의 장면에 대해, 각각의 깊이 맵에 의해 제공되는 비어 있지 않은 공간 내부에 놓여 있는 복셀과, 최종적으로, 모든 비어 있지 않은 공간의 교차선에 놓여 있는 복셀만을 유지하기 위해 제공되는 재구성 부시스템을 포함하며;

(Ⅲ) 상기 깊이 라벨링 부시스템은 후속하는 반복동안 상기 초기화 장치를 대체하기 위해 의도되고 이미지 획득 장치의 시야와 위치를 조정하기 위해 제공되는 프로젝션 장치, 및 각각의 정점에 대해, 조망 방향에서 상기 획득 장치의 광학 중심과 정점을 통과하는 라인을 교차하는 복셀을 열거하고 상기 이미지 평면에 가장 가까운 복셀을 선택하기 위한, 상기 이미지 평면에 아주 근접한 정점 맵을 또한 포함하는 것을 특징으로 한다.

본 발명의 이점은 첨부된 도면을 참조한 하기의 설명으로부터 더 잘 이해되어질 것이다.

도 1은 본 발명에 따른 재구성 장치의 개략도.

도 2는 도 1의 장치의 초기화 장치에서 수행되는 동작을 설명하는 도면.

도 3은 도 1의 장치의 개선 장치에서 수행되는 동작을 설명하는 도면.

도 4는 도 1의 장치의 3D 재구성 부시스템에서 수행되는 동작을 설명하는 도면.

도 5는 도 1의 장치의 프로젝션 장치에서 수행되는 동작을 설명하는 도면.

도 1에 도시된 장치는, 본 발명에 따라, N 개의 연속하는 2차원 이미지(2D)의 장면의 시퀀스에 기초해서, 3차원 형태(3D)로 상기 장면의 재구성을 허용하도록 의도된 것이다. 상기 복원은 반복하도록 이도된 두 단계에서의 구현에 따라 두 부시스템(11, 12)에서 실현된다. 상기 제 1의 단계는 깊이 라벨링 단계인데; 각각의 뷰는 연속하는 3D 시트의 프로젝션으로서 간주되고, 다중-뷰 매칭은 그 불일치 맵을 얻기 위해 각각의 뷰에 대해 독립적으로 수행되며, 각각의 불일치 맵은 3D 시트의 깊이 맵에 대응한다(상기 불일치의 측정은 깊이 산정을 제공하는데, 상기 불일치는 우측(좌측) 이미지에 대한 좌측(우측) 이미지에 대한 패치의 시프트이며, 임의의 일치 문제의 출력이 불일치 맵이다). 두 번째 단계는 3D 모델 추출 단계인데, 3D 공간의 옥트리 구획이 수행되고 모든 3D 깊이 시트의 교차점에 놓여 있는 복셀은 유지된다.

따라서, 도 1의 장치는 두 부분으로 더 나누어진다: 상기 제 1의 깊이 라벨링 단계를 수행하기 위한 깊이 라벨링 부시스템(11)과 상기 제 2의 모델 추출 단계를 수행하기 위한 3D 재구성 부시스템(12). 상기 깊이 라벨링 부시스템(11) 자체는 초기화 장치, 프로젝션 장치(112), 및 개선 장치(refinement device; 113)를 포함한다.

상기 초기화 장치는, 도 1에 도시된 바와 같이, 테스트 회로(1111)와 후속하는 초기화 회로(1112)를 포함한다. 상기 테스트 회로(1111)는 프로시져의 시작에서, 반복이 첫 번째인 경우 회로(1112)로 향하거나(YES) 또는 상기 초기화가 이미 수행된 경우 장치(112)로 향하도록(NO) 전환하기 위해 제공된다.

만약 I가 깊이 시트를 복원하기를 희망하는 이미지이고 I1 내지 IN이 다중-뷰 매칭을 위해 사용되는 화상이라면, 관련된 시야(field of view) 내에서, I의 이미지 평면과 평행하게 놓여 있는 것으로 가정되는 삼각형 영역으로 I가 분할되는 것으로 가정된다. 각각의 영역(R(I))에 대해서, 현재의 시야에서 소정의 깊이(D1, D2, …, Di, …, DM)의 집합(S) 중에서 이 영역의 깊이를 얻기 위해, 세 동작이 부단계(1112a, 1112b)에서 계속적으로 수행된다.

상기 부단계(1112a)(도 2의 상부)는 각각의 영역에 대해 규정된 길이의 에러 벡터(V(i))를 계산하는 것을 허용하며, 상기 벡터는 각각의 샘플링된 깊이(C는 기준 광학 중심이다)는 하기의 수학식에 의해 표현되는 (N-1) 쌍의 뷰의 각각의 뷰(이미지(i), 이미지(j)) 사이의 상관 비용의 합이다:

V(i)의 각 좌표는 각각의 뷰에서 깊이(Di)에서 마주치게되는 에러의 합에 대응한다. 상관 측정 에러(err(i)[Ik, Ij])는 깊이(Di)에 놓여 있는 것으로 가정되는 이미지(Ij)에서 영역(R(Ij))의 픽셀과 R(I)의 픽셀 사이의 평방근 에러이며 뷰(I 및 Ij)의 좌표 시스템에 관련하는 프로젝션 매트릭스를 사용하여 얻어진다. 부단계(1112b)(도 2의 중간 부분)는 각각의 영역에 대해 최소의 상관 비용을 제공하는 인텍스를 탐색하고, 부단계(1112c)(도 2의 하부)는, 이웃한 영역에 대해 얻어진 깊이 사이의 보간에 의해, 각각의 영역의 각 정점에 대한 그 깊이 값을 계산한다(즉, 삼각형 영역의 각 정점의 깊이는 정점을 공유하는 영역의 깊이의 평균일 것이다).

초기화로 인해, 예비 3D 깊이 시트가 이미지(I)에 대해 얻어진다. 각 영역(R(I))은 이제, 세 정점의 3D 좌표에 의해 주어지는 그 3D 위치와 방향의 평가를 갖는다. 그러나 상기 영역의 방향은 이미지(I)의 이미지 평면과 평행하게 놓여 있다는 초기 가정에 더 이상 따르지 않는다.

초기화 장치는 반복적으로 사용되고 이미지(I)의 각 영역의 방향의 새로운 평가를 고려하면서 다시 수행된다. 다른 접근법이 최종적으로 선호된다: 각각의 영역에 독립적으로 에러 벡터를 검색하는 대신, 에러 벡터는 I에서의 정점에 대해 독립적으로 검색된다(깊이 평가는 이웃한 정점에 대한 깊이 평가를 변경시키지 않으면서 각각이 정점에 대해 검색된다). 이러한 접근법은 개선 장치(113)에서 수행된다.

도 1에 도시된 바와 같이(그리고 도 3에서 상기 장치에서 수행되는 부단계를 도시한다), 상기 회로(1112)의 출력에서 유효한 깊이 맵을 수신하는 이 장치(113)는, 각각의 정점에 대해, 상관 비용이 측정될 윈도우(W)를 정의하는(도 3의 상부) 벡터 계산 회로(1131)를 포함한다. 각각의 정점에 대해, 에러 벡터가 계산되고(도 3의 중간 부분), 이것은 각각의 샘플링된 깊이에 대해, 범위가 정해진 윈도우 상의 (N-1)개 쌍의 뷰(이미지(i), 이미지(j))의 각각의 뷰 사이의 상관 비용의 합에 대응한다. 판정 회로(1132)에서, 각각의 정점에 대한 최소 상관 비용을 제공하는 인덱스가 발견된다(도 3의 하부). 개량된 3D 깊이 시트는 이제 유효하게 된다.

상기 장치(113)의 출력에서 유효한 깊이 맵은 깊이 라벨링 부시스템(11)의 출력 신호이고 3D 재구성 부시스템(12)으로 전송되는데, 상기 3D 재구성 부시스템(12)은, 도 1에 도시된 바와 같이(그리고 도 4에는 상기 장치에서 수행되는 부단계를 도시한다), 해상도 정의 장치(121)와 후속하는 일련의 복셀 선택 장치(122) 및 테스트 회로(123)를 포함한다. 상기 장치(121)에서, 복셀 그리드의 해상도가 선택된다(도 4의 상부). 상기 장치(122)에서, 각각의 뷰에 대해, 각각의 깊이 맵에 의해 제공되는 비어 있지 않은 공간 내부에 놓여 있는 복셀은 유지되고(도 4의 중간 부분), 모든 비어있지 않은 공간의 교차점에 놓여 있는 복셀만이 최종적으로 유지된다(도 4의 하부). 그 다음 수렴의 테스트가 테스트 회로(123)에서 수행되는데, 이전 단계의 일부는 상기 수렴이 얻어질 때까지 반복되어야 한다.

이전에 상술된 첫 번째 반복동안 초기화가 수행되었기 때문에, 두 번째 반복의 시작에서 상기 테스트 회로(1111)는 이제 프로젝션 장치(112)로 향해 전환한다. 상기 회로(11112)에서 수행되는 상기 제 1의 부단계(1112a, 1112b, 1112c)에 관해서, 상기 장치(112)에 제공되고 도 5에 도시된 상기 부단계(1121a, 1121b)는, (a) 카메라 파라미터에 따라 카메라의 시야와 위치, 및 상기 정점 맵을 이미지 평면에 아주 가깝게 조정하고, (b) 각각의 정점에 대해, 관측 방향에서, 카메라의 광학적 중심과 정점을 통과하는 라인을 교차하는 복셀을 열거하고, 상기 이미지 평면에 가장 가까운 복셀을 선택한다. 도 5의 하부에 도시된 바와 같이, 상기 장치(112)의 출력은 이미 상술된 바와 같이 동작하는 개선 장치(113)를 향해 (제 1의 반복의 경우 상기 장치(112)의 출력과 같이) 전송된다.

Claims (5)

1. N 개의 연속하는 실제 장면의 이미지에 대응하는 2차원 비디오 시퀀스로부터 3차원 장면을 재구성하는 방법에 있어서,

   삼각형 영역으로 분할된 상기 시퀀스의 각각의 이미지에 대해, 직렬로,

   (A) 각각의 장면이 연속하는 3D 시트의 프로젝션으로 간주되고, 상기 3D 시트의 깊이 맵에 대응하는 불일치 맵을 얻기 위해서 다중-장면 매칭이 각각의 장면에 대해 독립적으로 수행되는 제 1의 깊이 라벨링 단계와;

   (B) 3D 공간의 옥트리 구획(octree subdivision)이 수행되고 모든 3D 깊이 시트(depth sheet)의 교차점에 놓여 있는 복셀(voxels)(부피 요소)이 유지되는 제 2의 3D 모델 추출 단계를 포함하는 3차원 장면 재구성 방법.
2. 제 1항에 있어서,

   상기 깊이 라벨링 단계는 관련된 이미지에 대한 예비 3D 깊이 시트를 제 1의 반복동안 정의하기 위해 제공되는 초기화 부단계, 및 각각의 영역의 각각의 정점(vertex)에 대해, 상기 정점에 대해 특별하게 정의된 윈도우 상의 각각의 (N-1) 쌍의 장면 사이의 상관 비용의 합에 대응하는 각각의 샘플링된 깊이에 대한 에러 벡터를 정의하고 최소 상관 비용을 제공하는 인덱스를 저장하기 위한 개선 부단계를 연속적으로 포함하고, 상기 제 1의 반복 이후에 상기 초기화 부단계를 이미지 평면 근처의 정점 맵과 파라미터에 따른 이미지 획득 장치의 위치와 시야(field of view)를 먼저 조정하고 그 다음 각각의 정점에 대해 상기 획득 장치의 광학 중심과 상기 정점을 통과하는 라인을 교차하는 복셀을 조망 방향에서 열거하며, 상기 이미지 평면에 가장 가까운 복셀을 선택하기 위한 프로젝션 부단계로 대체하기 위해 의도된 부가적인 단계를 포함하는 3차원 장면 재구성 방법.
3. 제 2항에 있어서,

   상기 3D 모델 추출 단계는 복셀 그리드의 해상도를 정의하기 위해 제공되는 해상도 정의 부단계, 및 각각의 뷰에 대해 각각의 깊이 맵에 의해 제공되는 비어 있지 않은 공간 내부에 놓여 있는 복셀을 유지하고 그 다음 모든 비어 있지 않은 공간의 교차선에 놓여 있는 복셀만을 유지하기 위해 제공되는 복셀 선택 부단계를 포함하는 3차원 장면 재구성 방법.
4. N 개의 연속하는 실제 장면의 이미지에 대응하는 2차원 비디오 시퀀스로부터 3차원 장면을 재궝하기 위한 장치에 있어서,

   (Ⅰ) 상기 시퀀스의 N 개의 이미지의 각각은 3각형 영역으로 분할되고;

   (Ⅱ) 상기 장치는, 상기 시퀀스의 각각의 이미지를 처리하기 위해,

   (A) 깊이 라벨링 부시스템으로서,

   (1) 제 1의 반복동안 각각의 (N-1) 쌍의 장면 사이의 상관 비용의 합에 대응하는 샘플링된 깊이에 대한 에러 벡터와 최소 상관 비용을 제공하는 인덱스를 정의하기 위해 제공된 초기화 장치로서, 상기 영역의 각각의 정점의 깊이 값은 이웃하는 영역에 대해 얻어진 깊이 사이의 보간에 의해 계산되는 상기 초기화 장치와;

   (2) 각각의 정점의 정점에 대해 이전에 범위가 정해진 윈도우 상의 에러 벡터와, 최소 상관 비용을 제공하는 인덱스를 정의하기 위해 제공되는 개선 장치를 연속하여 포함하는 상기 깊이 라벨링 부시스템과;

   (B) 복셀 그리드의 해상도를 선택하고, 각각의 장면에 대해, 각각의 깊이 맵에 의해 제공되는 비어 있지 않은 공간 내부에 놓여 있는 복셀과, 최종적으로, 모든 비어 있지 않은 공간의 교차선에 놓여 있는 복셀만을 유지하기 위해 제공되는 재구성 부시스템을 포함하며;

   (Ⅲ) 상기 깊이 라벨링 부시스템은 후속하는 반복동안 상기 초기화 장치를 대체하기 위해 의도되고 이미지 획득 장치의 시야와 위치를 조정하기 위해 제공되는 프로젝션 장치, 및 각각의 정점에 대해, 조망 방향에서 상기 획득 장치의 광학 중심과 정점을 통과하는 라인을 교차하는 복셀을 열거하고 상기 이미지 평면에 가장 가까운 복셀을 선택하기 위한, 상기 이미지 평면에 아주 근접한 정점 맵을 또한 포함하는 것을 특징으로 하는 3차원 장면 재구성 장치.
5. 제 4항에 따른 재구성 장치를 포함하는 비디오 디코딩 시스템.