KR20020007894A

KR20020007894A - 실시간 입체 영상 정합 시스템

Info

Publication number: KR20020007894A
Application number: KR1020000041424A
Authority: KR
Inventors: 정홍; 오윤수
Original assignee: 정명식; 학교법인 포항공과대학교
Priority date: 2000-07-19
Filing date: 2000-07-19
Publication date: 2002-01-29
Anticipated expiration: 2020-07-19
Also published as: JP2002159023A; EP1175104A3; KR100374784B1; DE60109858D1; EP1175104A2; DE60109858T2; ATE292876T1; EP1175104B1; US20020025075A1; US6862035B2

Abstract

본 발명을 영상 처리 시스템에 관한 것으로, 보다 상세하게는 실시간으로 비디오 이미지 시퀀스의 스테레오 정합을 위한 시스템에 관한 것이다. 실시간 입체 영상 정합 시스템은 제1 및 제2 카메라로부터 입력되는 영상을 디지털 신호로 변환하는 신호 변환수단, 상기 제1 및 제2 디지털 영상신호의 한 스캔 라인의 픽셀 쌍으로부터 소정의 정합 코스트를 계산하고 최소의 정합 코스트를 결정하는 결정값을 추적하여 본 수단의 동작 유/무를 결정하는 소정의 활성 정보에 따라 상기 결정값을 양안차 추정치로 출력하는 영상 정합 수단, 상기 영상 정합 수단의 출력을 디스플레이 하기 위한 디스플레이 수단을 포함한다. 본 발명에 따르면, Bayesian Sense에 최적화된 새로운 동적 프로그래밍에 근거한 알고리즘을 사용하여 비디오 이미지 시퀀스들을 병렬 처리함으로써 실시간으로 스테레오 정합이 가능하도록 하는 효과가 있다.

Description

실시간 입체 영상 정합 시스템{A system for maching stereo image in real time}

본 발명을 영상 처리 시스템에 관한 것으로, 보다 상세하게는 실시간으로 비디오 이미지 시퀀스의 스테레오 정합을 위한 시스템에 관한 것이다.

스테레오 정합(Stereo Maching)은 한 쌍의 2차원 이미지로부터 3차원의 공간 정보를 재 창출하는 스테레오 비젼(Stereo vision) 중심이되는 프로세스이다. 연구논문[Uemsh R. Dhond and J. K. Aggarwal. Structure from stereo - a review. IEEE Transactions on Systems, Man, and Cybernetics, 19(6):553-572, nov/dec1989]를 보면 스테레오 정합에 대한 기본적인 사항 및 몇 가지 중요한 개발 분야를 찾을 수 있다. 이 연구논문에서 같은 광학 특성을 가진 한 쌍의 카메라는 각각의 정렬된 수평 이미지 스캔라인을 가지는 유사한(similar) 공간 영역을 취하기 위하여 정렬되기 때문에 같은 평면에 놓인다. 각각 픽셀(pixel) 쌍들이 동일한 3차원 공간의 점들에 대응되는 것과 같이 한 이미지에서의 픽셀들을 나머지 이미지에서의 픽셀들로 매칭함으로써, 간단한 기하학적 특성들을 이용하여 카메라로부터 그 점의 거리를 알아낼 수 있다. 여기서 기하학적 특성이 깊이(Depth)이다. 수평 스캔 라인의 정렬은 정합하는 픽셀 쌍이 각각의 이미지에서 같은 스캔 라인 위에 놓일 것이라는 것을 보증한다. 각각의 이미지에서 몇몇 픽셀들은 다른 이미지에서 정합하는 픽셀을 갖지 않을 수도 있는데 이것이 오클루젼(Occlusion) 이라고 알려진 경우이다. 처리 과정에서 가장 어려운 부분이 정합 픽셀을 찾는 것, 즉 스테레오 정합부분이다.

스테레오 정합에서 픽셀의 공간 정보 또는 거리의 계산은 Mapping, Geology, Testing, Inspection, Navigation, Virtual Reality, Medicine 등등을 포함한 산업과 연구의 많은 분야에서 매우 중요하다. 추가적으로 이러한 분야에서 몇몇은 정보에 즉각적으로 반응해야 하기 때문에 실시간 공간 정보를 요구한다. 특히, 로보틱스(Robotics)와 자동 운항(Autonomous Vehicles)에 있어서 명백하다.

연구 논문[Stuart Geman and Donald Geman. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-6(6):721-741, November 1984]에서는 스테레오 정합으로 Kirkpatric et al에 의해 발표된 Simulated Annealing에 근거한 Stochastic Optimization 방법과 Markov Random Fields를 사용한 방법을 기술하였다. 이것은 Mean Field 이론을 사용한 Geiger와 Girosi와 같은 다른 사람들에 의해 더 발전되었다. 그러나 이러한 방법들은 본질적으로 반복적이어서 매우 긴 연산 시간을 초래하기 때문에 실시간 스테레오 정합에는 부적절한 문제점이 있었다.

연구논문[H. H. Baker and T. O. Binford. Depth from edge and intensity based stereo. In Proceedings of the Inernational Joint Conference on Artificial Intelligence, page 631-636, Vancouver, Canada, 1981]와 연구논문[Y. Ohta and T. Kanade. Stereo by intra- and inter-scanline search. IEEE Trasactions on Pattern Analysis and Machine Intelligence, PAMI-7(2):139-154, March 1985]는 스테레오 정합으로 동적 프로그래밍(Dynamic Programming:DP)에 근거한 방법을 기술하였다. 양쪽 방법들은 픽셀 정합을 찾기 위해 Dual-level DP와 스스로 발견하게 하는(Heuristic) Post-processing을 사용한다. 연구논문[Ingemar J. Cox, Sunita L. Hingorani, Satish B. Rao, and Bruce M. Maggs. A maximum likelihood stereo algorithm. Computer Vision and Image Understanding, 63(3):542-567, May 1996)과 연구논문[Stan Birchfield and Carlo Tomasi. Depth discontinuities by pixel-to-pixel stereo. In Proceedings of the IEEE International Conference on Computer Vision, pages 1073-1080m, Bombay, India, 1998]에서는 스스로 발견하게 하는 Post-processing과 더불어 이산 픽셀 지향 방법에서 Single-level DP를 사용하였다. 연구논문[Peter N. Belhumeur. A Bayesian approach to binocular stereopsis. International Journal of Computer Vision, 19(3):237-260, 1996]에서는 Sub-pixel Resolution과 더불어 더 복잡한 DP 방법을 기술하였다. 비록 이러한 방법들이 Markov Random Field에 근거한 것들에 비해 빠르지만 그것들은 병렬 처리에 대하여 잘 스케일(Scale)되지 않고 따라서 여전히 실시간 스테레오 정합에는 부적합한 문제점이 있었다.

본 발명이 이루고자 하는 기술적인 과제는 종래 기술의 문제점을 해결하기 위한 것으로 Bayesian Sense에 최적화된 새로운 동적 프로그래밍에 근거한 알고리즘을 사용하여 비디오 이미지 시퀀스 들을 병렬 처리함으로써 실시간으로 스테레오 정합이 가능하도록 하는 실시간 입체 영상 정합 시스템을 제공하는데 있다.

도 1은 본 발명에 따른 실시간 입체 영상 정합 시스템의 블록도 이다.

도 2는 도 1 중 SMC의 상세도 이다.

도 3은 도 2 중 프로세싱 엘리먼트의 상세도 이다.

도 4는 도 3 중 전방 프로세서의 상세도 이다.

도 5는 도 3 중 결정 스택의 상세도 이다.

도 6은 도 3 중 후방 프로세서의 상세도 이다.

본 발명이 이루고자 하는 기술적인 과제를 해결하기 위한 실시간 입체 영상 정합 시스템은 제1 및 제2 카메라로부터 입력되는 영상을 디지털 신호로 변환하는 신호 변환수단; 상기 제1 및 제2 디지털 영상신호의 한 스캔 라인의 픽셀 쌍으로부터 소정의 정합 코스트를 계산하고 최소의 정합 코스트를 결정하는 결정값을 추적하여 본 수단의 동작 유/무를 결정하는 소정의 활성 정보에 따라 상기 결정값을 양안차 추정치로 출력하는 영상 정합 수단; 및 상기 영상 정합 수단의 출력을 디스플레이 하기 위한 디스플레이 수단을 포함하는 것이 바람직하다.

이하, 첨부된 도면을 참조하여 본 발명을 상세히 설명한다.

도 1에 도시된 시스템은 피사체의 좌측 영상을 촬영하는 좌측 카메라(10), 피사체의 우측 영상을 촬영하는 우측 카메라(11), 좌측 및 우측 카메라(10,11)의 영상신호를 디지털 변환하여 각각 출력하는 영상 처리부(12), 디지털 좌측 및 우측 영상으로부터 양안차를 계산하는 SMC(Stereo Maching Chip)(13), 양안차에 의한 영상을 디스플레이하는 사용자 시스템(14)으로 구성된다.

도 2는 도 1 중 SMC의 상세도 이다.

도 2에 도시된 SMC는 N/2개로 구성되어 영상 처리부(12)의 디지털 우측 영상 신호를 저장하는 우측 영상 레지스터(20), N/2개로 구성되어 영상 처리부(12)의 디지털 좌측 영상 신호를 저장하는 좌측 영상 레지스터(21), N개로 구성되어 클럭 제어신호 및 리드/라이트 신호에 의해 좌측 및 우측 영상으로부터 양안차를 출력하는 프로세싱 엘리먼트(22), 우측 영상 레지스터(20), 좌측 영상 레지스터(21) 및 프로세싱 엘리먼트(22)의 동작을 제어하기 위한 클럭을 제공하는 클럭 제어부(23)로 구성된다. (여기서 N은 2의 배수이다.)

도 3은 도 2 중 프로세싱 엘리먼트의 상세도 이다.

도 3에 도시된 프로세싱 엘리먼트는 우측 영상 레지스터(20) 및 좌측 영상 레지스터(21)에 저장된 한 스캔 라인의 픽셀을 입력으로 하여 정합 코스트 및 결정값을 출력하는 전방 프로세서(Foward Processor)(30), 전방 프로세서(30)에서 출력되는 결정값을 저장하는 결정 스택(Decision Stack)(31), 동작 유/무를 결정하는 활성 비트에 상기 결정 저장 수단에서 출력되는 결정값으로 양안차를 출력하는 후방 프로세서(Backward Processor)(32)로 구성된다.

도 4는 도 3 중 전방 프로세서의 상세도 이다.

도 4에 도시된 전방 프로세서는 우측 영상 레지스터(20) 및 좌측 영상 레지스터(21) 한 라인의 각 픽셀의 차로 정합 코스트를 계산하는 절대값 계산 수단(41), 절대값 계산 수단(41)에서 계산된 정합 코스트와 피드백된 전체 코스트를 가산하는 제1 가산기(42), 제1 가산기(42)의 출력과 인접된 프로세싱 엘리먼트(22)의 코스트를 비교하여 가장 작은 코스트 및 결정값을 출력하는 비교기(43), 비교기(43)의 비교 결과로 출력되는 가장 작은 코스트를 전체 코스트로 저장하는 코스트 레지스터(Cost Register)(44), 코스트 레지스터(44)에 저장된 전체 코스트와 오클루션 정보를 가산하여 인접 프로세싱 엘리먼트(22)로 출력하는 제2 가산기(45)로 구성된다.

도 5는 도 3 중 결정 스택의 상세도 이다.

도 5에 도시된 결정 스택은 비교기(43)에서 출력되는 결정값과 피드백된 제2 결정 레지스터(53)에서 선택된 결정값 중 하나를 선택하는 제1 멀티플렉서(Multiplexer, 이하 MUX로 표기함)(50), 제1 MUX(50)에서 선택된 결정값을 저장하고 제1 MUX(50)로 피드백 및 후방 프로세서(32)로 출력하는 제1 결정 레지스터(51), 제1 결정 레지스터(51)에서 선택된 결정값 및 피드백된 결정값 중 하나를 선택하는 제2 MUX(52), 제2 MUX(52)에서 선택된 결정값을 저장하고 제1 MUX(50)로 피드백하는 제2 결정 레지스터(53)로 구성된다.

도 6은 도 3 중 후방 프로세서의 상세도 이다.

도 6에 도시된 후방 프로세서는 인접한 프로세싱 수단의 활성 정보 경로와 피드백된 활성 정보 경로를 논리합 하는 OR 게이트(60), OR 게이트(60)의 논리합 결과 최종의 활성 정보 및 그 경로를 저장하는 활성 레지스터(61), 결정 스택(31)에서 출력되는 결정값에 따라 활성 레지스터(61)의 최종 활성 정보 경로를 다중화 하여 인접 프로세싱 엘리먼트(22) 및 OR 게이트(60)로 출력하는 디멀티 플렉서(Demultiplexer, 이하, DEMUX라 표기함)(62), 활성 레지스터(61)의 활성 정보 경로에 따라 결정 스택(31)에서 출력되는 결정값으로부터 양안차를 출력하는 3상태 버퍼(63)로 구성된다.

이어서 도 1∼도 6을 참조하여 본 발명을 상세히 설명한다.

본원 발명의 시스템은 한 쌍의 디지털 영상으로부터 양안차(Disparity)를 계산하는 것이다. 이 영상은 광축(Optical axes)이 평행하고 동일한 평면상에 촛점면(Focal plane)을 형성하는 동일한 한 쌍의 카메라(10,11)로부터 얻어야만 한다.

좌측 및 우측 카메라(10,11)에 입력된 영상은 영상 처리부(12)에서 디지털로 변환되고 각 영상의 한 스캔 라인이 픽셀 단위로 SMC(13)에 공급된다. 스캔 라인이 SMC(13)로 모두 전달되고 난 후에, 양안차 데이터가 픽셀 단위로 출력된다. 양안차가 출력되는 과정은 한 쌍의 영상의 모든 스캔 라인에 대하여 동일하게 반복된다. 따라서 이후에서는 한 쌍의 스캔 라인의 처리 과정에 대하여 설명한다.

도 2에 도시된 바와 같이 SMC(13)는 내부적으로 N개의 동일한 프로세싱 엘리먼트(22)로 구성된 선형 어레이와 N/2개의 영상 레지스터(20,21)로 구성된 선형어레이 2개를 가지고 있다. 여기서 N은 2의 배수이다. 우측 영상 레지스터(20)에는디지털 변환된 우측 카메라(11)의 영상이 저장되고, 좌측 영상 레지스터(21)에는 디지털 변환된 좌측 카메라(10)의 영상이 저장된다.

프로세싱 엘리먼트(22)는 지정된 최대 양안차까지 선형 어레이 형태로 복제될 수 있고, 각 프로세싱 엘리먼트(22)는 이웃하는 프로세싱 엘리먼트(22)와 정보를 교환할 수 있다. 이 구조는 프로세싱 엘리먼트(22)의 갯수에 제한없이 최대 속도로 동작할 수 있게 하고, 프로세싱 엘리먼트(22)의 수가 최대 양안차와 같은 경우에는 비디오 영상 흐름과 보조를 유지할 수 있다.

클럭 제어부(23)는 시스템 클럭을 2개의 내부 클럭으로 나누어 좌측 및 우측 레지스터(20,21), 프로세싱 엘리먼트(22)를 제어한다. 클럭 제어부(23)에서 출력되는 ClkE는 짝수번째의 시스템 클럭 사이클에 토글하고(최초의 시스템 클럭 사이클을 0으로 정의한다), 짝수번째의 프로세싱 엘리먼트(22)와 우측 영상 레지스터(20)에 공급한다. 클럭 제어부(23)에서 출력되는 ClkO는 홀수번째의 시스템 클럭 사이클에 토글하고, 홀수번째의 프로세싱 엘리먼트(22)와 좌측 영상 레지스터(21)에 공급된다.

그러므로 짝수번째 프로세싱 엘리먼트(22)와 우측 영상 레지스터(20)부터 시작하여 매 시스템 클럭 사이클 마다 프로세싱 엘리먼트(22) 절반과 영상 레지스터(20 또는 21) 절반이 클럭에 의해 동작한다. 처리단계는 리드/라이트 신호(F/B 또는 R/W, 이하, R/W로 표기함)에 의해 제어된다. R/W 신호 선이 하이 상태이면 데이터가 쓰여지고, 로우 단계이면 데이터가 읽혀진다.

영상 픽셀 데이터는 우측 영상 레지스터(20)와 좌측 영상 레지스터(21)로 공급된다. 시스템 클럭 마다 데이터의 한 픽셀이 우측 영상 레지스터(20) 및 좌측 영상 레지스터(21)로 입력되는데, 클럭 제어부(23)의 ClkE에 의해서 우측 영상 픽셀이, ClkO에 의해서 좌측 영상이 입력된다. 우측 및 좌측 레지스터(20,21)는 프로세싱 엘리먼트(22)에 N/2 쌍의 데이터를 공급하므로써 초기화 된다. 동작 원리에 의해 좌측 영상이 우측 영상 보다 N/2-1 지연되어 공급되어야 한다. 그래서 좌측 영상으로 공급되는 초기의 N/2-1 개의 데이터는 임의의 값을 가져도 무방하다.

초기화 과정의 마지막 ClkO에서 우측 영상의 스캔 라인의 모든 데이터가 프로세싱 엘리먼트(22)로 입력되고 난 후, 좌측 영상의 스캔 라인에서는 첫번째 픽셀이 프로세싱 엘리먼트(22)로 입력된다. 이때 각 프로세싱 엘리먼트 내부의 레지스터들이 적절한 초기값으로 설정되는데, 프로세싱 엘리먼트 0의 초기값은 0이고, 다른 모든 프로세서의 초기값은 가능한 최대치가 된다. 그러면 처리과정은 현재 스캔 라인의 데이터를 마칠 때까지 매 시스템 클럭 마다 입력되는 픽셀 데이터에 대해서 계속된다.(ClkE에서는 우측 영상, ClkO에서는 좌측 영상)

좌측 영상이 지연되어 프로세싱 엘리먼트(22)로 입력되기 때문에, 좌측 영상의 입력이 끝나기 전에 우측 영상 데이터의 입력이 끝나게 된다. 이 경우에 우측 영상 레지스터(20)는 데이터를 계속 읽지만, 이 데이터는 SMC(13)의 동작에 영향을 주지 못한다. 그러므로 ClkE 사이클의 마지막 N/2-1 개의 데이터는 어떤 값이어도 무방하다.

프로세싱 에리먼트(22)로 픽셀 데이터의 입력이 끝나게 되면, R/W 신호가 로우 상태로 표시되고, 각각의 프로세싱 엘리먼트(22)는 활성 비트(Activation bit)가 적당한 값으로 설정된다. 프로세싱 엘리먼트 0(22)는 활성 비트가 하이 상태로 설정되고 다른 프로세싱 엘리먼트(1∼N)(22)는 로우 상태로 설정된다. 하이 상태인 활성 비트는 매 시스템 클럭 사이클 마다 다음 프로세싱 엘리먼트(22)로 전달되고, 주어진 시간에 오직 한개의 프로세서만 활성 비트가 하이 상태가 된다. 활성 비트가 하이 상태인 프로세싱 엘리먼트(22)의 출력을 방해하지 않기 위하여 다른 모든 프로세싱 엘리먼트(22)의 출력은 고 임피던스 상태가 되어야 한다.

양안차 출력은 (-1, 0, +1)과 같이 증감 형태의 값을 가져서 초기의 양안차 값 0으로부터 시작하여 양안차의 변화를 나타내거나 각 프로세싱 엘리먼트(22)의 출력인 실제 양안차 값을 가질 수 있다.

각 프로세싱 엘리먼트(22)는 도 3에 도시된 바와 같이 전방 프로세서(30), 결정 스택(31), 후방 프로세서(32)로 구성된다.

전방 프로세서(30)의 상세도가 도 4에 도시되어 있다.

절대값 계산 수단(41)는 우측 영상 레지스터(20)의 픽셀 Rin 및 좌측 영상 레지스터(21)의 픽셀 Lin의 절대값 차로부터 정합 코스트를 계산한다. 계산된 정합 코스트는 제1 가산기(42)에서 피드백된 전체 코스트와 가산된다. 이 정합 비용은 그 프로세싱 엘리먼트(22)의 전체 코스트에 가산되고, 비교기(43)의 입력 중 하나가 된다.

비교기(43)의 다른 두입력은 인접된 프로세싱 엘리먼트(22)의 코스트 출력 단자인 Uout에 각각 연결된다(Uin1 및 Uin2). 비교기(43)는 3개의 입력 중에서 최소 값을 선택하고 이 코스트를 클럭이 가해질 때마다 새로운 전체 코스트가 되어코스트 레지스터(44)에 저장된다. 선택된 입력의 식별(결정값)은 Uin이 최소이면 -1, Uin2이 최소이면 +1, 다른 경우이며 0이되고, 이 값은 Dfout으로 출력된다.

제2 가산기는 코스트 레지스터(44)에 저장된 전체 코스트와 오클루션 정보 Co를 가산하여 Uout 단자를 통해 인접 프로세싱 엘리먼트(22)로 출력한다. 이때 오클루션 Co는 계산된 상수 값이고, 이 값은 전체 코스트와 더해져서 이웃하는 프로세싱 엘리먼트(22)에 전달된다.

결정 스택(31)은 세가지의 가능한 결정값을 저장하기 위해서 2비트 레지스터로 구성되어 후입 선출 방식으로 동작한다. 결정 스택(31)의 상세도가 도 5에 도시되어 있다.

결정 스택(31) 데이터 흐름의 방향은 R/W 신호 선에 의해 제어된다. 그래서 전방 프로세서(30)의 Dfout에 연결된 Dsin 신호가 결정 스택(31)에 쓰여진다. 제1 MUX(50)는 비교기(43)에서 출력되는 결정값과 제2 결정 레지스터(53)에서 피드백된 결정값 중 하나를 선택한다. 제1 결정 레지스터(51)는 제1 MUX(50)에서 선택된 결정값을 저장하고, 후방 프로세서(32)로 Dsout 단자를 통하여 출력한다. 제2 MUX(52)는 제1 결정 레지스터(51)에서 선택된 결정값 및 피드백된 결정값 중 하나를 선택하고, 제2 결정 레지스터(53)는 제2 MUX(52)에서 선택된 결정값을 저장하고 제2 MUX(52)로 피드백한다.

후방 프로세서(32)는 최적의 양안차를 재조합하는 기능을 한다. 후방 프로세서(32)의 상세도가 도 6에 도시되어 있다.

후방 프로세서(32)는 활성화 비트를 저장하는 활성 레지스터(61)를 포함하고있다. 그래서 활성 비트가 하이 상태인 후방 프로세서(32)만이 활성화 된다. OR 게이트(60)는 인접한 프로세싱 엘리먼트(22)의 활성 비트 경로(Ain1, Ain2)와 피드백된 활성 비트 경로(Aself)를 논리합 한다. Ain1 단자는 아래에 위치한 프로세싱 엘리먼트(22)의 Aout2 단자에 연결되고, Ain2는 위에 위치한 프로세싱 엘리먼트(22)의 Aout1 단자에 에 연결되어 있다. 이 입력 들은 활성 비트가 전달될 경로를 나타내고, 이들 입력 중에서 활성 비트가 하이 상태이면 OR 게이트(60)의 출력이 하이 상태가 된다.

OR 게이트(60)의 입력 중 Aself 단자는 활성 비트의 내부 경로로 클럭이 인가되었을 때 활성 비트의 상태를 유지하도록 한다. 활성 비트의 새로운 값은 후방 프로세서(32)에 클럭이 인가될때 활성 레지스터(61)에 설정된다. 후방 프로세서(32)는 1입력 3출력 DEMUX(62)를 제어하기 위해 결정 스택(31)의 출력 Dsout에 Dbin에 있는 값을 사용한다. DEMUX(62)의 출력은 Aout1, Aself, Aout2인데 이들은 Dbin이 각각 -1, 0, +1인 경우에 활성 비트와 같은 값을 가진다. 그렇지 않은 경우에는 출력이 0이된다. 그러므로 Dbin은 활성 비트가 전달되는 방향을 제어하는 데 사용된다.

활성 비트가 하이 상태이면 3상태 버퍼(63)가 동작하여 Dbin이 Dbout으로 출력된다. 그리고 이 값이 양안차의 추정치로써 SMC(13)에서 출력된다. 그렇지 않으면, 3상태 버퍼(63)는 고 임피던스 상태가 되어 다른 후방 프로세서(32)의 출력을 방해하지 않도록 한다.

다른 방법으로 Dbin 대신에 프로세서의 번호를 Dbout에 출력하는 것이다.Dbin을 출력하는 방식에서는 양안차 값의 상대적인 변경을 나타내는 것인데, 프로세서 번호를 출력하는 방식에서는 실제의 양안차 값을 나타내는 것이다.

본 발명은 스캔 라인 쌍에서 각 픽셀의 정합을 다음 알고리즘에 의하여 구현한다.

1. 초기화 : 노드 0을 제외한 모든 노드의 비용을 무한대로 설정한다.

U[0,0]=0

U[0,j]=∞, j∈{1,....,N-1}

2. 재귀 : 각 스텝과 사이트 i에 대하여 가장 좋은 경로와 코스트를 찾는다.

For i=1 to 2N do:

For each j∈{0,....,N-1}:

if i+j is even

if i+j is odd

3. 종료:

d[2N] = P[2N, 0]

4. 백트랙킹:

For i=2N-1 to 0 do:

판단 P[i,j]은 결정 스택(31)에 저장된다. 결정 스택(31)을 위한 클럭이 전체적인 동작을 제어한다. 전방 재귀는 전방 프로세서(30)에 의해 수행되고, 후방 재귀는 후방 프로세서(32)에 의해 수행된다.

이 알고리즘의 특성과 본 발명에서의 구현 방법에 의해서 핵심적인 전방 재귀는 동일한 프로세서를 이용하여 병렬적으로 모든 심도에 대하여 처리된다. 결과적으로 한 개의 프로세싱 엘리먼트(22)는 카메라가 한 픽셀을 출력하는 시간 이내에 한 사이트에서 한 전방 재귀를 수행할 수 있다. 프로세싱 엘리먼트(22)는 가능한 최대 심도까지 복제할 수 있으므로 본 발명은 입체 영상 정합을 비디오 카메라의 출력 비율 대로 처리할 수 있다.

다음에 프로세서 및 결정 스택의 구조에 대하여 설명한다.

1. 전방 계산을 위한 구조

전방 프로세서(30)의 구조는 도 4에 도시되어 있다. 시간 i에서 전방 프로세서(30) j 내의 비교기의 출력 U[i,j]는 다음과 같다.

매 시간에서 각 판단의 출력은 다음과 같다.

이들 판단은 결정 스택(31) 어레이에 저장된다.

2. 결정 스택

결정 스택(31)은 N 워드로 구성된 LIFO(Last-In First-Out) 레지스터 배열이다. 그리고 각각의 워드는 2비트로 구성된다. 각각의 프로세싱 엘리먼트(22)마다 한 개의 결정 스택(31)이 있다. 전방 프로세서(30)의 처리 동안에 매 스탭에 해당하는 P[i,j]는 결정 스택에 저장된다. 후방 프로세서(32) 처리 동안에 이러한 결정값은 역순으로 출력된다.

3. 후방 계산을 위한 구조

알고리즘의 백트래킹 부분의 구조가 도 6에 도시되어 있다. 후방 처리를 위해 결정 스택(31)의 출력은 반대 방향으로 쉬프트 되므로 다음과 같이 표시된다.

P[i,j] for i = 2N-1 to 0

i = 2N에서 1 비트 활성 레지스터(61) 중에서 a[0,j]를 제외한 모든 a[0,0]은 0으로 초기화 된다. 각 후방 프로세서(32)의 활성 출력은 다음과 같다.

재귀 출력(Aself) : a[i+1,j] δ(P[i+1,j]),

상방 출력(Aout2) : a[i+1,j+1] δ(1-P[i+1,j+1]),

하방 출력(Aout1) : a[i+1,j-1] δ(-1-P[i+1,j-1])

활성 레지스터(61)는 매 시간 마다 다음과 같이 갱신된다.

후방 프로세서(32)의 경로 판단 출력은 다음과 같다.

P^*[i,j] = a[i,j]P[i,j]

그리고 매 시간 스텝에서 전체적인 최적 경로 판단은 다음과 같다.

위를 하드웨어로 구현시 누산기가 필요치 않으며 모든 i에 대한 P[i,j]의 출력은 P[i]으 ㅣ입력에 함께 연결한 구조를 가진다.

마지막 계산은 국지적인 양안차의 변화를 절대적인 양안차에 누산하는 것이다.

본 발명은 상술한 실시 예에 한정되지 않으며 본 발명의 사상 내에서 당업자에 의한 변형이 가능함은 물론이다.

상술한 바와 같이 본 발명에 따르면, Bayesian Sense에 최적화된 새로운 동적 프로그래밍에 근거한 알고리즘을 사용하여 비디오 이미지 시퀀스 들을 병렬 처리함으로써 실시간으로 스테레오 정합이 가능하도록 하는 효과가 있다.

Claims

제1 및 제2 카메라로부터 입력되는 영상을 디지털 신호로 변환하는 신호 변환수단;

상기 제1 및 제2 디지털 영상신호의 한 스캔 라인의 픽셀 쌍으로부터 소정의 정합 코스트를 계산하고 최소의 정합 코스트를 결정하는 결정값을 추적하여 본 수단의 동작 유/무를 결정하는 소정의 활성 정보에 따라 상기 결정값을 양안차 추정치로 출력하는 영상 정합 수단; 및

상기 영상 정합 수단의 출력을 디스플레이 하기 위한 디스플레이 수단을 포함하는 실시간 입체 영상 정합 시스템.
제 1항에 있어서, 상기 신호 변환수단으로 입력되는 영상은

광축이 평행하고 동일한 평면 상에 촛점면을 형성하는 동일한 상기 제1 및 제2 카메라로부터 얻어지는 것을 특징으로 하는 실시간 입체 영상 정합 시스템.
제 1항에 있어서, 상기 영상 정합 수단에서 상기 정합 코스트는

상기 제1 및 제2 픽셀에 상기 스캔 라인에서 픽셀들이 정합되지 않은 경우인 오클루션 정보를 포함하여 계산하는 것을 특징으로 하는 실시간 입체 영상 정보 시스템.
제 1항에 있어서 상기 영상 정합부는

상기 제1 카메라에 의한 디지털 영상 픽셀을 저장하는 제1 저장수단;

상기 제2 카메라에 의한 디지털 영상 픽셀을저장하는 제2 저장수단;

상기 제1 및 제2 저장수단으로부터 입력된 픽셀로부터 소정의 양안차 추정치를 출력하는 프로세싱 수단; 및

상기 제1 및 제2 저장수단과 상기 프로세싱 수단의 동작을 제어하기 위한 클럭을 제공하는 클럭 제어수단을 포함하는 것을 특징으로 하는 실시간 입체 영상 정합 시스템.
제 4항에 있어서,

상기 프로세싱 수단을 N개, 상기 제1 및 제2 저장수단은 N/2개로 구성된 것을 특징으로 하는 실시간 입체 영상 정합 시스템. (여기서 N은 2의 배수)
제 5항에 있어서, 상기 프로세싱 수단은 이웃 하는 다른 프로세싱 수단과 정보를 교환하는 것을 특징으로 하는 실시간 입체 영상 정합 시스템.
제 5항에 있어서, 상기 N개의 프로세싱 수단 중

소정의 양안차를 출력하는 프로세싱 수단만이 활성화 되고 나머지 프로세싱 수단들은 고 임피던스 상태를 유지하는 것을 특징으로 하는 실시간 입체 영상 정합 시스템.
제 4항에 있어서, 상기 제1 및 제2 저장수단은 상기 프로세싱 수단으로 한 스캔 라인의 픽셀이 완료되면 초기화 되는 것을 특징으로 하는 실시간 입체 영상 정합 시스템.
제 4항에 있어서, 상기 제1 저장수단에 저장되는 픽셀은 상기 클럭에 의해 우측 영상보다 N/2-1 지연되는 것을 특징으로 하는 실시간 입체 영상 정합 시스템.
제 4항에 있어서, 상기 클럭 제어 수단은

상기 짝수번째 프로세서와 상기 제2 저장수단에 공급되는 제1 클럭과 상기 홀수번째 프로세서와 상기 제1 저장수단에 공급되는 제2 클럭을 출력하는 것을 특징으로 하는 실시간 입체 영상 정합 시스템.
제 4항에 있어서, 상기 프로세싱 수단은

상기 제1 및 제2 저장수단의 한 스캔 라인의 픽셀을 입력으로 하여 소정의 정합 코스트 및 결정값을 출력하는 제1 프로세서;

제 1 프로세서에서 출력되는 결정값을 저장하는 결정 저장 수단; 및

상기 소정의 활성 정보에 의해 상기 결정 저장 수단에서 출력되는 결정값으로 소정의 양안차를 출력하는 제2 프로세서를 포함하는 것을 특징으로 하는 실시간 입체 영상 정합 시스템.
제 11항에 있어서,

외부에서 쓰기 제어신호가 입력되면 상기 제1 프로세서가 동작하고, 외부에서 읽기 제어신호가 입력되면 상기 제2 프로세서가 동작하는 것을 특징으로 하는 실시간 입체 영상 정합 시스템.
제 11항에 있어서, 상기 결정 저장수단은

상기 제1 프로세서에서 가장 나중에 출력되는 결정값이 상기 제2 프로세서에가장 먼저 입력되는 후입 선출 방식의 구조로 된 것을 특징으로 하는 실시간 입체 영상 정합 시스템.
제 11항에 있어서, 제1 프로세서는

상기 제1 및 제2 저장수단의 한 라인의 픽셀로부터 정합 코스트를 계산하는 정합 코스트 계산 수단;

상기 계산된 정합 코스트와 피드백된 전체 코스트를 가산하는 제1 가산 수단;

상기 제1 가산 수단의 출력과 상기 인접된 프로세싱 수단의 코스트를 비교하여 가장 작은 코스트 및 결정값을 출력하는 비교수단;

상기 비교 결과 가장 작은 코스트를 전체 코스트로 저장하는 저장수단;

상기 전체 코스트와 오클루션 정보를 가산하여 인접 프로세싱 수단으로 출력하는 상기 제2 가산수단을 포함하는 것을 특징으로 하는 실시간 입체 영상 정합 시스템.
제 11항에 있어서, 상기 결정 저장수단은

상기 비교수단에서 출력되는 결정값과 피드백된 이전 상태의 결정값 중 하나를 선택하는 선택 수단; 및

상기 선택 결과를 저장하고, 상기 선택 수단의 앞단의 선택 수단의 입력으로 피드백 또는 상기 제2 프로세서로 출력 시키는 결정 레지스터를 포함하는 것을 특징으로 하는 실시간 입체 영상 정합 시스템.
제 15항에 있어서, 상기 선택 수단은

상기 쓰기 제어신호에 의해 상기 비교수단에서 출력되는 결정값을 선택하고, 상기 읽기 제어 신호에 의해 상기 결정 레지스터에 저장된 결정값을 선택하는 것을 특징으로 하는 실시간 입체 영상 정합 시스템.
제 11항에 있어서, 상기 제2 프로세서는

상기 인접한 프로세싱 수단의 활성 정보 경로와 피드백된 활성 정보 경로를 논리합 하는 논리합 수단;

상기 논리합 결과 최종의 활성 정보 및 그 경로를 저장하는 레지스터;

상기 결정 저장수단에서 출력되는 결정값에 따라 상기 레지스터의 최종 활성 정보 경로를 다중화 하여 상기 인접 프로세싱 수단과 상기 논리합 수단으로 피드백 하는 다중화 수단; 및

상기 레지스터의 활성 정보에 따라 상기 결정 저장 수단에서 출력되는 결정값을 소정의 양안 추정치로 출력하는 버퍼를 포함하는 것을 특징으로 하는 실시간 입체 영상 정합 시스템.
제 17항에 있어서, 상기 결정 저장수단의 출력은 상기 다중화 수단의 활성 정보 전달 방향을 제어하는 것을 특징으로 하는 실시간 입체 영상 정합 시스템.