KR101544021B1

KR101544021B1 - Apparatus and method for generating 3d map

Info

Publication number: KR101544021B1
Application number: KR1020120120523A
Authority: KR
Inventors: 박순용; 최성인
Original assignee: 경북대학교 산학협력단
Priority date: 2012-10-29
Filing date: 2012-10-29
Publication date: 2015-08-13
Also published as: KR20140054710A

Abstract

본 발명의 3차원 지도 생성 장치 및 방법에 관한 것으로, 소정의 시간 간격으로 스테레오 영상들을 연속적으로 촬영하는 스테레오 영상 촬영 장치; 상기 스테레오 영상들로부터 상기 소정의 시간 간격으로 3차원 거리 영상들을 생성하는 거리 영상 생성 장치; 상기 스테레오 영상들에 대응하는 상기 3차원 거리 영상들을 정합함으로써, 상기 스테레오 영상 촬영 장치의 위치 정보를 추정하는 위치 추정 장치; 및 상기 3차원 거리 영상들 및 상기 3차원 거리 영상들에 대응하는 상기 스테레오 영상 촬영 장치의 상기 위치 정보를 이용하여 3차원 지도를 생성하는 3차원 지도 생성부를 포함하는 3차원 지도 생성 장치를 제공한다.The present invention relates to a three-dimensional map generating apparatus and method, and more particularly, to a stereo image photographing apparatus for continuously photographing stereo images at predetermined time intervals. A distance image generating device for generating three-dimensional distance images at the predetermined time intervals from the stereo images; A position estimator for estimating position information of the stereo image photographing apparatus by matching the three-dimensional distance images corresponding to the stereo images; And a three-dimensional map generating unit for generating a three-dimensional map using the three-dimensional distance images and the position information of the stereo image photographing apparatus corresponding to the three-dimensional distance images .

Description

TECHNICAL FIELD [0001] The present invention relates to a three-dimensional map generating apparatus and a three-

본 발명은 3차원 지도(3D Map)를 생성하는 장치 및 3차원 지도를 생성하는 방법에 관한 것이다.The present invention relates to a device for generating a three-dimensional map (3D Map) and a method for generating a three-dimensional map.

도로 및 도로 주변의 환경을 나타내는 지도에는 주로 2차원 지도가 활용되고 있다. 예를 들어, 차량용 내비게이션은 2차원 지도상에 차량의 현재 위치 및 차량의 주행 방향을 화살표로 표시하며, 운전자에게 주행 경로를 안내한다. 그런데, 2차원 지도는 실제 도로 및 도로 주변의 환경을 정확하게 나타내지 않기 때문에, 도심 지역인 경우 차량 운전자가 내비게이션 단말기의 주행 경로 안내 문구를 정확하게 판단하지 못하여, 차량이 주행 경로와 인접한 다른 주행 경로로 이탈하게 되는 등, 2차원 지도만으로 목적지에 쉽게 도달하기 어려운 상황이 발생할 수 있다.Two-dimensional maps are mainly used for maps representing the environment around roads and roads. For example, a car navigation system displays on the two-dimensional map the current position of the vehicle and the running direction of the vehicle by using arrows, and guides the driver to the running route. However, since the two-dimensional map does not accurately represent the environment around the actual road and the road, the driver of the vehicle can not correctly determine the driving route guidance phrase of the navigation terminal in the case of the downtown area, In such a situation, it is difficult to easily reach the destination with a two-dimensional map only.

이에 따라, 최근에는 3차원 지도를 제공하는 시스템에 대한 연구가 이루어지고 있다. 예를 들어, 레이저 스캐너를 차량에 탑재하여, 차량을 주행하면서 레이저 스캐너를 이용하여 도로 및 주변 환경에 대한 3차원 영상을 촬영하고, 촬영된 영상과 대응하는 위치 정보를 위성항법시스템(GPS; Global Positioning System)을 이용하여 기록하여 데이터베이스로 구축함으로써 3차원 지도를 생성하는 기술이 소개되었다. 그러나, GPS는 오차가 수 미터에 이르기 때문에, 도로들과 골목길 및 건물들이 매우 복잡하게 얽혀 있는 지역에서는 내비게이션의 안내 문구에 따른 차량의 주행 경로 전환 시점을 정확히 이해하지 못하여, 차량이 주행 경로로부터 이탈하는 등의 문제점이 여전히 발생할 수 있다.Accordingly, recently, a system for providing a three-dimensional map has been studied. For example, a laser scanner is mounted on a vehicle, a three-dimensional image of a road and a surrounding environment is photographed using a laser scanner while the vehicle is traveling, and position information corresponding to the photographed image is transmitted to a GPS Positioning System) to create a database and create a 3D map. However, since the error of the GPS is several meters, in the area where the roads, the alleys and the buildings are intertwined with each other in a very complicated manner, it is difficult to accurately understand the turning point of the vehicle traveling route according to the navigation instruction, And the like.

본 발명은 스테레오 영상 정보를 이용하여 3차원 지도를 생성할 수 있는 3차원 지도 생성 장치 및 3차원 지도 생성 방법을 제공하는 것을 목적으로 한다.An object of the present invention is to provide a three-dimensional map generating device and a three-dimensional map generating method capable of generating a three-dimensional map using stereo image information.

본 발명의 다른 목적은 지피에스(GPS; Global Positioning System)와 같은 위치 추정 장치를 사용하지 않고도 3차원 지도를 생성할 수 있는 3차원 지도 생성 장치 및 3차원 지도 생성 방법을 제공하는 것에 있다.Another object of the present invention is to provide a three-dimensional map generating apparatus and a three-dimensional map generating method capable of generating a three-dimensional map without using a position estimating apparatus such as a Global Positioning System (GPS).

본 발명의 또 다른 목적은 3차원 지도의 도로 및 주변 환경의 위치 추정에 대한 오차를 줄일 수 있는 3차원 지도 생성 장치 및 3차원 지도 생성 방법을 제공하는 것에 있다.It is another object of the present invention to provide a three-dimensional map generating apparatus and a three-dimensional map generating method capable of reducing an error in the estimation of the position of the road and the surrounding environment of the three-dimensional map.

본 발명이 해결하고자 하는 과제는 이상에서 언급된 과제로 제한되지 않는다. 언급되지 않은 다른 기술적 과제들은 이하의 기재로부터 당업자에게 명확하게 이해될 수 있을 것이다.The problems to be solved by the present invention are not limited to the above-mentioned problems. Other technical subjects not mentioned may be clearly understood by those skilled in the art from the following description.

본 발명의 일 측면에 따른 3차원 지도 생성 장치는 소정의 시간 간격으로 스테레오 영상들을 연속적으로 촬영하는 스테레오 영상 촬영 장치; 상기 스테레오 영상들로부터 상기 소정의 시간 간격으로 3차원 거리 영상들을 생성하는 거리 영상 생성 장치; 상기 스테레오 영상들에 대응하는 상기 3차원 거리 영상들을 정합함으로써, 상기 스테레오 영상 촬영 장치의 위치 정보를 추정하는 위치 추정 장치; 및 상기 3차원 거리 영상들 및 상기 3차원 거리 영상들에 대응하는 상기 스테레오 영상 촬영 장치의 상기 위치 정보를 이용하여 3차원 지도를 생성하는 3차원 지도 생성부를 포함한다.According to an aspect of the present invention, there is provided a three-dimensional map generating apparatus, comprising: a stereoscopic image photographing apparatus for continuously photographing stereo images at predetermined time intervals; A distance image generating device for generating three-dimensional distance images at the predetermined time intervals from the stereo images; A position estimator for estimating position information of the stereo image photographing apparatus by matching the three-dimensional distance images corresponding to the stereo images; And a three-dimensional map generating unit for generating a three-dimensional map using the three-dimensional distance images and the position information of the stereo image photographing apparatus corresponding to the three-dimensional distance images.

본 발명은 일 측면에 따르면, 상기 위치 추정 장치는, 상기 스테레오 영상들의 특징점들을 이용하여 상기 스테레오 영상들에 대응하는 상기 3차원 거리 영상들을 정합하여 상기 스테레오 영상 촬영 장치의 움직임을 추정함으로써 상기 스테레오 영상 촬영 장치의 상기 위치 정보를 추정하는 3차원 지도 생성 장치가 제공될 수 있다.According to an aspect of the present invention, the position estimating apparatus estimates the motion of the stereo image photographing apparatus by matching the three-dimensional distance images corresponding to the stereo images using the feature points of the stereo images, A three-dimensional map generating apparatus for estimating the position information of the photographing apparatus may be provided.

본 발명은 일 측면에 따르면, 상기 위치 추정 장치는, 연속적으로 촬영된 상기 스테레오 영상들로부터 2차원 특징점들을 추출하는 특징점 추출부; 연속되는 상기 스테레오 영상들로부터 추출된 상기 2차원 특징점들을 매칭시키는 특징점 매칭부; 매칭된 상기 2차원 특징점들 중에서 스테레오 기하 제약 조건을 만족하지 않는 외치점을 제거하는 외치점 제거부; 상기 2차원 특징점들에 대응하는 상기 3차원 거리 영상의 3차원 특징점들을 이용하여 연속되는 3차원 거리 영상들 간의 변환 행렬을 최적화함으로써 상기 스테레오 영상 촬영 장치의 움직임을 추정하는 움직임 추정부; 및 상기 2차원 특징점들 및 상기 3차원 특징점들을 이용하여 상기 스테레오 영상 촬영 장치의 투영 행렬을 최적화함으로써 상기 스테레오 영상 촬영 장치의 상기 움직임을 정제하는 움직임 정제부를 포함하는 3차원 지도 생성 장치가 제공될 수 있다.According to an aspect of the present invention, the position estimation apparatus includes a feature point extraction unit for extracting two-dimensional feature points from the stereo images continuously captured; A feature point matching unit for matching the two-dimensional feature points extracted from the continuous stereo images; An outlier point removing unit that removes outline points that do not satisfy the stereo geometry constraint among the matched two-dimensional feature points; A motion estimator for estimating a motion of the stereo image photographing apparatus by optimizing a transformation matrix between consecutive three-dimensional distance images using the three-dimensional feature points of the three-dimensional distance image corresponding to the two-dimensional feature points; And a motion refinement unit for refining the motion of the stereo image photographing apparatus by optimizing the projection matrix of the stereo image photographing apparatus using the two-dimensional feature points and the three-dimensional feature points, have.

본 발명은 일 측면에 따르면, 상기 거리 영상 생성 장치는, 상기 소정의 시간 간격으로 획득된 각 스테레오 영상의 좌안 영상 및 우안 영상의 왜곡을 보정하는 보정부; 상기 좌안 영상 및 우안 영상의 잡음을 제거하는 저역통과 필터; 상기 좌안 영상 및 우안 영상을 매칭시키는 스테레오 매칭부; 및 삼각화 기법에 기초하여 상기 스테레오 영상에 대응하는 3차원 정보를 산출함으로써, 상기 3차원 거리 영상을 생성하는 삼각화부를 포함하는 3차원 지도 생성 장치가 제공될 수 있다.According to an aspect of the present invention, the distance image generating apparatus includes a correcting unit correcting distortion of a left eye image and a right eye image of each stereo image acquired at the predetermined time interval; A low pass filter for removing noise of the left eye image and the right eye image; A stereo matching unit for matching the left eye image and the right eye image; And a triangulation unit for generating the three-dimensional distance image by calculating three-dimensional information corresponding to the stereo image based on the triangulation technique.

본 발명은 일 측면에 따르면, 상기 스테레오 영상 촬영 장치는 차량에 탑재되며, 상기 차량이 주행함에 따라 도로 및 상기 도로의 주변 환경을 포함하는 상기 스테레오 영상들을 상기 소정의 시간 간격으로 연속적으로 촬영하는 3차원 지도 생성 장치가 제공될 수 있다.According to an aspect of the present invention, there is provided a stereoscopic image photographing apparatus comprising: a stereoscopic image photographing apparatus, which is mounted on a vehicle and sequentially photographs the stereoscopic images including the road and the surrounding environment of the road at the predetermined time intervals as the vehicle travels; A 2D map generating device may be provided.

본 발명의 다른 일 측면에 따른 3차원 지도 생성 방법은 스테레오 영상 촬영 장치를 이용하여 소정의 시간 간격으로 스테레오 영상들을 연속적으로 촬영하는 단계; 상기 스테레오 영상들로부터 상기 소정의 시간 간격으로 3차원 거리 영상들을 생성하는 단계; 연속적으로 촬영된 상기 스테레오 영상들에 대응하는 상기 3차원 거리 영상들을 정합함으로써, 상기 스테레오 영상 촬영 장치의 위치 정보를 추정하는 단계; 및 상기 3차원 거리 영상들 및 상기 3차원 거리 영상들에 대응하는 상기 스테레오 영상 촬영 장치의 상기 위치 정보를 이용하여 3차원 지도를 생성하는 단계를 포함한다.According to another aspect of the present invention, there is provided a method of generating a three-dimensional map, the method comprising: sequentially capturing stereo images at predetermined time intervals using a stereo image photographing apparatus; Generating three-dimensional distance images at the predetermined time intervals from the stereo images; Estimating position information of the stereoscopic image photographing apparatus by matching the three-dimensional distance images corresponding to the continuously captured stereoscopic images; And generating a three-dimensional map using the three-dimensional distance images and the position information of the stereo image photographing apparatus corresponding to the three-dimensional distance images.

본 발명의 다른 일 측면에 따르면, 상기 위치 정보를 추정하는 단계는, 상기 스테레오 영상들의 특징점들을 이용하여 상기 스테레오 영상들에 대응하는 상기 3차원 거리 영상들을 정합하여 상기 스테레오 영상 촬영 장치의 움직임을 추정함으로써 상기 스테레오 영상 촬영 장치의 상기 위치 정보를 추정하는 3차원 지도 생성 방법이 제공될 수 있다.According to another aspect of the present invention, the step of estimating the position information may include estimating the motion of the stereo image photographing apparatus by matching the three-dimensional distance images corresponding to the stereo images using the feature points of the stereo images, A three-dimensional map generating method of estimating the position information of the stereo image photographing apparatus can be provided.

본 발명의 다른 일 측면에 따르면, 상기 위치 정보를 추정하는 단계는, 연속적으로 촬영된 상기 스테레오 영상들로부터 2차원 특징점들을 추출하는 단계; 연속되는 상기 스테레오 영상들로부터 추출된 상기 2차원 특징점들을 매칭시키는 단계; 매칭된 상기 2차원 특징점들 중에서 스테레오 기하 제약 조건을 만족하지 않는 외치점을 제거하는 단계; 상기 2차원 특징점들에 대응하는 상기 3차원 거리 영상의 3차원 특징점들을 이용하여 연속되는 3차원 거리 영상들 간의 변환 행렬을 최적화함으로써 상기 스테레오 영상 촬영 장치의 움직임을 추정하는 단계; 및 상기 2차원 특징점들 및 상기 3차원 특징점들을 이용하여 상기 스테레오 영상 촬영 장치의 투영 행렬을 최적화함으로써 상기 스테레오 영상 촬영 장치의 상기 움직임을 정제하는 단계를 포함하는 3차원 지도 생성 방법이 제공될 수 있다.According to another aspect of the present invention, the step of estimating the position information includes: extracting two-dimensional feature points from the continuously captured stereo images; Matching the two-dimensional feature points extracted from the continuous stereo images; Removing an outlier point that does not satisfy the stereo geometry constraint among the matched two-dimensional feature points; Estimating a motion of the stereo image photographing apparatus by optimizing a transformation matrix between consecutive three-dimensional distance images using the three-dimensional feature points of the three-dimensional distance image corresponding to the two-dimensional feature points; And a step of refining the motion of the stereo image photographing apparatus by optimizing the projection matrix of the stereo image photographing apparatus using the two-dimensional feature points and the three-dimensional feature points .

본 발명의 다른 일 측면에 따르면, 상기 3차원 거리 영상들을 생성하는 단계는, 상기 소정의 시간 간격으로 획득된 각 스테레오 영상의 좌안 영상 및 우안 영상의 왜곡을 보정하는 단계; 상기 좌안 영상 및 상기 우안 영상의 잡음을 제거하는 단계; 상기 좌안 영상 및 상기 우안 영상을 매칭시키는 단계; 및 삼각화 기법에 기초하여 상기 스테레오 영상에 대응하는 3차원 정보를 산출함으로써, 상기 3차원 거리 영상을 생성하는 단계를 포함하는 3차원 지도 생성 방법이 제공될 수 있다.According to another aspect of the present invention, the step of generating the three-dimensional distance images includes: correcting distortion of the left eye image and the right eye image of each stereo image acquired at the predetermined time interval; Removing noise of the left eye image and the right eye image; Matching the left eye image and the right eye image; And generating the three-dimensional distance image by calculating three-dimensional information corresponding to the stereo image based on the triangulation technique.

본 발명의 또 다른 일 측면에 따른 3차원 지도 생성 방법은 연속되는 스테레오 영상들에 대응하는 연속되는 3차원 거리 영상들을 정합하여 상기 스테레오 영상들 각각에 대응하는 위치 정보를 추정하고, 상기 3차원 거리 영상들 및 추정한 상기 위치 정보를 이용하여 3차원 지도를 생성하는 단계를 포함한다.According to another aspect of the present invention, there is provided a three-dimensional map generation method for estimating position information corresponding to each of stereo images by matching successive three-dimensional distance images corresponding to successive stereo images, And generating a three-dimensional map using the images and the estimated position information.

본 발명의 또 다른 일 측면에 따르면, 차량을 주행시키면서 상기 차량에 탑재한 스테레오 영상 촬영 장치를 이용하여 도로 및 상기 도로의 주변 환경을 포함하는 상기 스테레오 영상들을 연속적으로 촬영하는 단계를 더 포함하는 3차원 지도 생성 방법이 제공될 수 있다.According to another aspect of the present invention, there is provided a method of driving a vehicle, comprising the steps of continuously photographing the stereo images including a road and a surrounding environment of the road using a stereo image photographing apparatus mounted on the vehicle while driving the vehicle A method of generating a 2D map can be provided.

본 발명의 실시예에 의하면, 스테레오 영상으로부터 3차원 지도를 생성할 수 있다.According to an embodiment of the present invention, a three-dimensional map can be generated from a stereo image.

또한, 본 발명의 실시예에 의하면, 지피에스(GPS; Global Positioning System)와 같은 위치 추정 장치를 사용하지 않고도 3차원 지도를 생성할 수 있으며, 3차원 지도의 도로 및 주변 환경의 위치 추정에 대한 오차를 줄일 수 있다.According to the embodiment of the present invention, a three-dimensional map can be generated without using a position estimation device such as a global positioning system (GPS), and an error .

도 1은 본 발명의 일 실시예에 따른 3차원 지도 생성 장치의 구성도이다.
도 2는 본 발명의 일 실시예에 따른 3차원 지도 생성 장치를 구성하는 거리 영상 생성 장치의 예시적인 구성도이다.
도 3은 본 발명의 일 실시예에 따른 3차원 지도 생성 장치를 구성하는 위치 추정 장치의 예시적인 구성도이다.
도 4는 본 발명의 일 실시예에 따른 3차원 지도 생성 방법의 흐름도이다.
도 5는 도 4에 도시된 단계 S42의 흐름도이다.
도 6은 도 4에 도시된 단계 S43의 흐름도이다.
도 7은 스테레오 영상의 좌안 및 우안 영상에 대한 에피폴라 기하를 설명하기 위한 개념도이다.
도 8은 강체 지속성 제약에 대하여 설명하기 위한 개략도이다.1 is a configuration diagram of a three-dimensional map generating apparatus according to an embodiment of the present invention.
FIG. 2 is an exemplary configuration diagram of a distance image generating apparatus constituting a three-dimensional map generating apparatus according to an embodiment of the present invention.
3 is an exemplary configuration diagram of a position estimating apparatus constituting a three-dimensional map generating apparatus according to an embodiment of the present invention.
4 is a flowchart of a three-dimensional map generation method according to an embodiment of the present invention.
5 is a flowchart of step S42 shown in Fig.
6 is a flowchart of step S43 shown in Fig.
7 is a conceptual diagram for explaining the epipolar geometry for the left eye and right eye images of a stereo image.
8 is a schematic diagram for explaining rigid persistence constraints.

본 발명의 다른 이점 및 특징, 그리고 그것들을 달성하는 방법은 첨부되는 도면과 함께 상세하게 후술하는 실시예를 참조하면 명확해질 것이다. 그러나 본 발명은 이하에서 개시되는 실시예에 한정되는 것이 아니라 서로 다른 다양한 형태로 구현될 수 있으며, 단지 본 실시예는 본 발명의 개시가 완전하도록 하고, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자에게 발명의 범주를 완전하게 알려주기 위해 제공되는 것이며, 본 발명은 청구항의 범주에 의해 정의될 뿐이다. 만일 정의되지 않더라도, 여기서 사용되는 모든 용어들(기술 혹은 과학 용어들을 포함)은 이 발명이 속한 종래 기술에서 보편적 기술에 의해 일반적으로 수용되는 것과 동일한 의미를 갖는다. 일반적인 사전들에 의해 정의된 용어들은 관련된 기술 그리고/혹은 본 출원의 본문에 의미하는 것과 동일한 의미를 갖는 것으로 해석될 수 있다. 본 명세서에서 사용된 용어는 실시예들을 설명하기 위한 것이며 본 발명을 제한하고자 하는 것은 아니다.Other advantages and features of the present invention and methods of achieving them will be apparent by referring to the embodiments described hereinafter in detail with reference to the accompanying drawings. The present invention may, however, be embodied in many different forms and should not be construed as being limited to the embodiments set forth herein. Rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the concept of the invention to those skilled in the art. Is provided to fully convey the scope of the invention to those skilled in the art, and the invention is only defined by the scope of the claims. Although not defined, all terms (including technical or scientific terms) used herein have the same meaning as commonly accepted by the generic art in the prior art to which this invention belongs. Terms defined by generic dictionaries may be interpreted to have the same meaning as in the related art and / or the text of this application. The terminology used herein is for the purpose of illustrating embodiments and is not intended to be limiting of the present invention.

한편, 본 명세서 전체에서 사용되는 '~부'의 용어는 적어도 하나의 기능이나 동작을 처리하는 단위를 의미할 수 있다. 예를 들어 소프트웨어, FPGA 또는 ASIC과 같은 하드웨어 구성요소를 의미할 수 있다. 그렇지만 '~부'의 용어가 소프트웨어 또는 하드웨어에 한정되는 의미는 아니다. '~부'는 어드레싱할 수 있는 저장 매체에 있도록 구성될 수도 있고 하나 또는 그 이상의 프로세서들을 재생시키도록 구성될 수도 있다. 따라서, 일 예로서 '~부'는 소프트웨어 구성요소들, 객체지향 소프트웨어 구성요소들, 클래스 구성요소들 및 태스크 구성요소들과 같은 구성요소들과, 프로세스들, 함수들, 속성들, 프로시저들, 서브루틴들, 프로그램 코드의 세그먼트들, 드라이버들, 펌웨어, 마이크로 코드, 회로, 데이터, 데이터베이스, 데이터 구조들, 테이블들, 어레이들 및 변수들을 포함한다. 구성요소들과 '~부' 안에서 제공되는 기능은 더 작은 수의 구성요소들 및 '~부'들로 결합되거나 추가적인 구성요소들과 '~부'들로 더 분리될 수 있다.The term " part " used throughout this specification may mean a unit for processing at least one function or operation. For example, a hardware component, such as a software, FPGA, or ASIC. However, the term '~' is not meant to be limited to software or hardware. &Quot; to " may be configured to reside on an addressable storage medium and may be configured to play one or more processors. Thus, by way of example, 'parts' may refer to components such as software components, object-oriented software components, class components and task components, and processes, functions, , Subroutines, segments of program code, drivers, firmware, microcode, circuitry, data, databases, data structures, tables, arrays, and variables. The functions provided in the components and components may be combined into a smaller number of components and parts or further separated into additional components and parts.

본 발명의 실시예에 따른 3차원 지도 생성 장치는 연속적으로 촬영된 스테레오 영상들로부터 연속적인 3차원 거리 영상들을 생성하고, 3차원 거리 영상들을 정합하여 스테레오 영상 촬영 장치의 위치 정보를 추정함으로써 3차원 지도를 생성하므로, 연속적으로 촬영되는 스테레오 영상들로부터 3차원 지도를 생성할 수 있으며, 지피에스(GPS; Global Positioning System)를 사용하지 않고도 3차원 지도를 생성할 수 있으며, GPS를 기반으로 하여 생성된 3차원 지도와 대비하여 피촬영 대상의 위치 추정 오차를 줄일 수 있다.The three-dimensional map generation apparatus according to an embodiment of the present invention generates consecutive three-dimensional distance images from consecutively captured stereo images, aligns the three-dimensional distance images, and estimates the position information of the stereo image photographing apparatus, The 3D map can be generated from the stereo images continuously captured, and the 3D map can be generated without using the GPS (Global Positioning System), and the 3D map generated based on the GPS The position estimation error of the object to be imaged can be reduced compared to the 3D map.

도 1은 본 발명의 일 실시예에 따른 3차원 지도 생성 장치의 구성도이다. 도 1을 참조하면, 본 발명의 일 실시예에 따른 3차원 지도 생성 장치(100)는 스테레오 영상 촬영 장치(110), 거리 영상 생성 장치(120), 위치 추정 장치(130) 및 3차원 지도 생성부(140)를 포함한다. 스테레오 영상 촬영 장치(110)는 소정의 시간 간격으로 스테레오 영상들을 연속적으로 촬영한다. 스테레오 영상 촬영 장치(110)에 의해 촬영된 스테레오 영상들은 3차원 거리 영상의 생성을 위해 거리 영상 생성 장치(120)로 입력되며, 스테레오 영상들 각각에 대응하는 스테레오 영상 촬영 장치(110)의 위치 정보를 추정하기 위하여 위치 추정 장치(130)로 입력된다. 스테레오 영상 촬영 장치(110)는 예를 들어 스테레오 비전 카메라일 수 있다. 스테레오 영상은 좌안 영상(left image) 및 우안 영상(right image)을 포함할 수 있다. 일 실시예에 있어서, 스테레오 영상 촬영 장치(110)는 좌안 영상 촬영용 카메라(미도시) 및 우안 영상 촬영용 카메라(미도시)를 포함할 수 있다.1 is a configuration diagram of a three-dimensional map generating apparatus according to an embodiment of the present invention. Referring to FIG. 1, a 3D map generating apparatus 100 according to an embodiment of the present invention includes a stereo image photographing apparatus 110, a distance image generating apparatus 120, a position estimating apparatus 130, (140). The stereo image photographing apparatus 110 sequentially photographs stereo images at predetermined time intervals. Stereo images taken by the stereo image photographing apparatus 110 are input to the distance image generating apparatus 120 for generating a three-dimensional distance image, and the position information of the stereo image photographing apparatus 110 corresponding to each of the stereo images Is input to the position estimating device 130 for estimating the position of the vehicle. The stereo imaging device 110 may be, for example, a stereo vision camera. The stereo image may include a left image and a right image. In an embodiment, the stereoscopic image capturing apparatus 110 may include a left eye image capturing camera (not shown) and a right eye image capturing camera (not shown).

일 실시예에 있어서, 스테레오 영상 촬영 장치(110)는 차량에 탑재될 수 있다. 스테레오 촬영 장치(110)는 차량이 주행함에 따라 도로 및 도로의 주변 환경을 포함하는 스테레오 영상들을 소정의 시간 간격으로 연속적으로 촬영할 수 있다. 소정의 시간 간격은 예를 들어, 스테레오 촬영 장치(110)의 프레임 레이트(frame rate)(fps)에 따라 결정될 수 있다. 거리 영상 생성 장치(120)는 스테레오 영상 촬영 장치(110)에 의해 촬영된 스테레오 영상들로부터 소정의 시간 간격으로 3차원 거리 영상들을 생성한다. 거리 영상 생성 장치(120)에 의해 생성된 3차원 거리 영상들은, 3차원 거리 영상들 각각에 대응하는 스테레오 영상 촬영 장치(110)의 위치 정보를 추정하기 위하여 위치 추정 장치(130)로 입력된다. 3차원 거리 영상은 예를 들어 좌안 영상과 우안 영상의 스테레오 정합을 통해 생성되어, 3차원 정보를 포함할 수 있다. 이때, 3차원 거리 영상은 스테레오 영상의 2차원 정보 및 3차원 정보를 모두 포함할 수 있으므로, '2.5차원 거리 영상'으로 표현될 수도 있다.In one embodiment, the stereo imaging device 110 may be mounted in a vehicle. The stereo photographing apparatus 110 can continuously photograph stereo images including a road and a surrounding environment of the road at predetermined time intervals as the vehicle travels. The predetermined time interval may be determined according to the frame rate (fps) of the stereo photographing apparatus 110, for example. The distance image generating apparatus 120 generates three-dimensional distance images at predetermined time intervals from the stereo images taken by the stereo image photographing apparatus 110. The three-dimensional distance images generated by the distance image generating apparatus 120 are input to the position estimating apparatus 130 for estimating the position information of the stereo image photographing apparatus 110 corresponding to each of the three-dimensional distance images. The three-dimensional distance image is generated through stereo matching of the left eye image and the right eye image, for example, and may include three-dimensional information. At this time, the 3D distance image may include both the 2D information and the 3D information of the stereo image, and thus may be expressed as a '2.5-dimensional distance image'.

거리 영상 생성 장치(120)에 의해 생성된 연속되는 두 3차원 거리 영상 사이의 시간 간격은 스테레오 영상 촬영 장치(110)의 연속되는 두 스테레오 영상 사이의 시간 간격과 동일할 수 있다. 여기서, 두 스테레오 영상이 '연속하다'라는 것은 두 스테레오 영상의 촬영 시점의 사이에 촬영된 다른 영상이 존재하지 않는다는 것, 두 스테레오 영상이 시간적으로 연속된 순서로 촬영된 것임을 의미할 수 있다. 예를 들어, 전체 N 프레임의 스테레오 영상이 촬영되었을 때, N 프레임 중 t-1 시점에 촬영된 n-1번째 프레임, t 시점에 촬영된 n번째 프레임의 연속한 스테레오 영상들로부터 n-1번째 3차원 거리 영상, n번째 3차원 거리 영상의 연속한 3차원 거리 영상들을 생성할 수 있다.The time interval between successive two-dimensional distance images generated by the distance image generating apparatus 120 may be the same as the time interval between two consecutive stereo images of the stereo image photographing apparatus 110. [ Here, the two stereo images are 'continuous', which means that there is no other image taken between the shooting times of the two stereo images, which means that the two stereo images are taken in temporally successive order. For example, when a stereo image of all N frames is captured, the (n-1) th frame captured at time t-1 and the consecutive stereo images of nth frame captured at time t Dimensional distance image, and the n-th three-dimensional distance image.

도 2는 본 발명의 일 실시예에 따른 3차원 지도 생성 장치를 구성하는 거리 영상 생성 장치의 예시적인 구성도이다. 도 2를 참조하면, 거리 영상 생성 장치(120)는 보정부(121), 저역통과 필터(122), 스테레오 매칭부(123) 및 삼각화부를 포함한다. 보정부(121)는 스테레오 촬영 장치(110)에 의해 소정의 시간 간격으로 획득된 각 스테레오 영상의 좌안 영상 및 우안 영상의 왜곡을 보정(rectification, calibration)한다. 저역통과 필터(Low Pass Filter)(122)는 스테레오 촬영 장치(110)에 의해 획득된 각 스테레오 영상의 좌안 영상 및 우안 영상의 잡음을 제거한다. 동일 시점에서 촬영된 각 스테레오 영상의 좌안 영상 및 우안 영상은 잡음이 제거된 후 스테레오 매칭부(123)로 입력된다. 스테레오 매칭부(123)는 스테레오 정합 기법(stereo matching)을 이용하여 동일 시점에서 촬영된 각 스테레오 영상의 좌안 영상 및 우안 영상을 매칭시킨다. 삼각화부(124)는 삼각화 기법(triangulation)을 이용하여 스테레오 영상에 대응하는 3차원 정보를 산출함으로써, 3차원 거리 영상을 생성할 수 있다.FIG. 2 is an exemplary configuration diagram of a distance image generating apparatus constituting a three-dimensional map generating apparatus according to an embodiment of the present invention. 2, the distance image generation apparatus 120 includes a correction unit 121, a low-pass filter 122, a stereo matching unit 123, and a triangulation unit. The correcting unit 121 rectifies and corrects distortion of the left eye image and the right eye image of each stereo image acquired at a predetermined time interval by the stereo image sensing apparatus 110. [ A low pass filter 122 removes the noise of the left eye image and the right eye image of each stereo image obtained by the stereo image sensing device 110. The left eye image and the right eye image of each stereo image photographed at the same point are input to the stereo matching unit 123 after the noise is removed. The stereo matching unit 123 matches the left eye image and the right eye image of each stereo image photographed at the same point in time using a stereo matching technique. The triangulation unit 124 can generate a three-dimensional distance image by calculating three-dimensional information corresponding to a stereo image using a triangulation method.

다시 도 1을 참조하면, 위치 추정 장치(130)는 스테레오 영상 촬영 장치(110)에 의해 촬영된 스테레오 영상들 및 거리 영상 생성 장치(120)에 의해 생성된 3차원 거리 영상들을 이용하여 스테레오 영상 촬영 장치(110)의 위치 정보를 추정한다. 일 실시예에 있어서, 위치 추정 장치(130)는 스테레오 영상 촬영 장치(110)에 의해 연속적으로 촬영된 스테레오 영상들로부터 2차원 특징점들을 추적하고, 추적한 2차원 특징점들을 이용하여 스테레오 영상들에 대응하는 3차원 거리 영상들을 정합함으로써 스테레오 영상 촬영 장치(110)의 위치 정보를 추정할 수 있다. 일 실시예에 있어서, 위치 추정 장치(130)는 스테레오 영상들에 대응하는 3차원 거리 영상들을 정합하고, 3차원 거리 영상들의 정합에 따른 스테레오 영상 촬영 장치(110)의 카메라의 움직임을 추정(motion estimation)함으로써, 스테레오 영상 촬영 장치(110)의 위치를 추정할 수 있다.Referring again to FIG. 1, the position estimating apparatus 130 estimates the position of the stereo image by using the stereo images taken by the stereo image photographing apparatus 110 and the three-dimensional distance images generated by the distance image generating apparatus 120, And estimates the position information of the device 110. In one embodiment, the position estimating apparatus 130 tracks two-dimensional feature points from stereo images continuously captured by the stereo image photographing apparatus 110, and uses two-dimensional feature points that are traced to correspond to stereo images The position information of the stereo image photographing apparatus 110 can be estimated by matching the three-dimensional distance images. In one embodiment, the position estimating apparatus 130 may be configured to match the three-dimensional distance images corresponding to the stereo images, to estimate the motion of the camera of the stereo image photographing apparatus 110 according to the matching of the three- the position of the stereo image photographing apparatus 110 can be estimated.

도 3은 본 발명의 일 실시예에 따른 3차원 지도 생성 장치를 구성하는 위치 추정 장치의 예시적인 구성도이다. 도 3을 참조하면, 위치 추정 장치(130)는 특징점 추출부(131), 특징점 매칭부(132), 외치점 제거부(133), 움직임 추정부(134) 및 움직임 정제부(135)를 포함한다. 특징점 추출부(131)는 연속적으로 촬영된 스테레오 영상들로부터 2차원 특징점들을 추출한다. 예를 들어, 특징점 추출부(131)는 연속되는 스테레오 영상들의 좌안 영상 또는 우안 영상으로부터 2차원 특징점들을 추출할 수 있다. 특징점은 예를 들어, 영상의 회전, 스케일, 또는 이동 변환 등에 따라 동일한 위치가 찾아지는 화소를 의미할 수 있다. 특징점 매칭부(132)는 연속되는 스테레오 영상들로부터 추출된 2차원 특징점들을 매칭(matching)시킨다. 외치점 제거부(133)는 2차원 특징점들 중에서 스테레오 기하 제약 조건을 만족하지 않는 외치점(outlier point)을 제거한다. 움직임 추정부(134)는 외치점을 제외한 2차원 특징점들의 정보를 사용하여 스테레오 영상 촬영 장치(110)의 카메라의 움직임을 추정(motion estimation)할 수 있다. 일 실시예에 있어서, 움직임 추정부(134)는 스테레오 영상들의 2차원 특징점들에 대응하는 3차원 거리 영상의 3차원 특징점들을 이용하여 연속되는 3차원 거리 영상들 간의 변환 행렬을 최적화함으로써 스테레오 영상 촬영 장치(110)의 움직임을 추정할 수 있다. 움직임 정제부(135)는 스테레오 영상 촬영 장치(110)의 카메라의 움직임을 정제(motion refinement)한다. 일 실시예에 있어서, 움직임 정제부(135)는 스테레오 영상들의 2차원 특징점들 및 3차원 거리 영상의 3차원 특징점들을 이용하여 스테레오 영상 촬영 장치(110)의 투영 행렬을 최적화함으로써 스테레오 영상 촬영 장치(110)의 움직임을 정제할 수 있다. 위치 추정 장치(130)의 보다 구체적인 기능에 대하여는 후술한다.3 is an exemplary configuration diagram of a position estimating apparatus constituting a three-dimensional map generating apparatus according to an embodiment of the present invention. 3, the position estimating apparatus 130 includes a feature point extracting unit 131, a feature point matching unit 132, an external point removing unit 133, a motion estimating unit 134, and a motion refinement unit 135 do. The feature point extracting unit 131 extracts two-dimensional feature points from the continuously captured stereo images. For example, the feature point extracting unit 131 may extract the two-dimensional feature points from the left eye image or the right eye image of successive stereo images. The minutiae point may mean, for example, a pixel in which the same position is sought according to rotation, scale, or motion conversion of the image. The feature point matching unit 132 matches the two-dimensional feature points extracted from the continuous stereo images. The outlier point removing unit 133 removes an outlier point that does not satisfy the stereo geometry constraint among the two-dimensional feature points. The motion estimator 134 may estimate motion of the camera of the stereo image photographing apparatus 110 using the information of the two-dimensional feature points excluding the outlier point. In one embodiment, the motion estimator 134 optimizes the transformation matrix between successive three-dimensional distance images using the three-dimensional feature points of the three-dimensional distance image corresponding to the two-dimensional feature points of the stereo images, The motion of the device 110 can be estimated. The motion refinement unit 135 refines motion of the camera of the stereo image photographing apparatus 110. In one embodiment, the motion refinement unit 135 may optimize the projection matrix of the stereo image photographing apparatus 110 by using the two-dimensional feature points of the stereo images and the three-dimensional feature points of the three- 110 can be refined. More specific functions of the position estimating apparatus 130 will be described later.

다시 도 1을 참조하면, 3차원 지도 생성부(140)는 거리 영상 생성 장치(120)에 의해 생성된 3차원 거리 영상들 및 3차원 거리 영상들 각각에 대응하는 스테레오 영상 촬영 장치(110)의 위치 정보를 이용하여 3차원 지도를 생성한다. 본 발명의 일 실시예에 따른 3차원 지도 생성 장치(100)는 복수의 스테레오 영상 촬영 장치를 포함할 수 있다. 이러한 실시예의 경우, 3차원 지도 생성부(140)는 각 스테레오 영상 촬영 장치에 대응하는 3차원 거리 영상을 하나의 영상으로 합성하여, 보다 넓은 시역의 3차원 지도 데이터를 생성할 수 있다.1, the three-dimensional map generating unit 140 generates a three-dimensional (2D) image of the stereoscopic image photographing apparatus 110 corresponding to each of the three-dimensional distance images and the three-dimensional distance images generated by the distance image generating apparatus 120 A three-dimensional map is generated using the location information. The 3D map generating apparatus 100 according to an embodiment of the present invention may include a plurality of stereo image photographing apparatuses. In such an embodiment, the three-dimensional map generating unit 140 may synthesize the three-dimensional distance images corresponding to the respective stereo image photographing apparatuses into one image to generate three-dimensional map data with a wider viewing area.

이하에서는 본 발명의 일 실시예에 따른 3차원 지도 생성 방법에 대해 설명한다. 본 발명의 일 실시예에 따른 3차원 지도 생성 방법은 연속적으로 촬영된 스테레오 영상들로부터 연속적인 3차원 거리 영상들을 생성하고, 3차원 거리 영상들을 정합하여 스테레오 영상 촬영 장치의 위치 정보를 추정함으로써 3차원 지도를 생성하므로, 연속적으로 촬영되는 스테레오 영상들로부터 3차원 지도를 생성할 수 있으며, 지피에스(GPS; Global Positioning System) 등과 같은 위치 추정 장치 없이도 3차원 지도를 생성할 수 있으며, GPS를 기반으로 하여 생성된 3차원 지도와 대비하여 도로 및 주변 환경 등의 위치 추정 오차를 줄일 수 있다.Hereinafter, a three-dimensional map generation method according to an embodiment of the present invention will be described. The three-dimensional map generation method according to an embodiment of the present invention generates consecutive three-dimensional distance images from continuously captured stereo images, aligns the three-dimensional distance images, and estimates position information of the stereo image photographing apparatus 3D map can be generated from stereo images continuously captured, and 3D map can be generated without using a position estimation device such as GPS (Global Positioning System). Also, based on GPS, Dimensional map, it is possible to reduce the position estimation error of the road and surrounding environment.

도 4는 본 발명의 일 실시예에 따른 3차원 지도 생성 방법의 흐름도이다. 도 4에 도시된 단계들은 도 1 내지 도 3에 도시된 3차원 지도 생성 장치의 구성들에 의하여 수행될 수 있다. 도 1 내지 도 4를 참조하면, 본 발명의 일 실시예에 따른 3차원 지도 생성 방법은, 스테레오 영상 촬영 장치(110)를 이용하여 소정의 시간 간격으로 스테레오 영상들을 연속적으로 촬영하는 단계(S41), 스테레오 영상들로부터 소정의 시간 간격으로 3차원 거리 영상들을 생성하는 단계(S42), 3차원 거리 영상들을 정합함으로써, 스테레오 영상 촬영 장치(110)의 위치 정보를 추정하는 단계(S43) 및 3차원 거리 영상들 및 3차원 거리 영상들에 대응하는 스테레오 영상 촬영 장치(110)의 위치 정보를 이용하여 3차원 지도를 생성하는 단계(S44)를 포함한다.4 is a flowchart of a three-dimensional map generation method according to an embodiment of the present invention. The steps shown in Fig. 4 may be performed by the configurations of the three-dimensional map generating apparatus shown in Figs. 1 to 4, a three-dimensional map generating method according to an embodiment of the present invention includes sequentially photographing stereo images at a predetermined time interval (S41) using a stereo image photographing apparatus 110, A step S42 of generating 3D distance images at predetermined time intervals from the stereo images, a step S43 of estimating the position information of the stereo image photographing apparatus 110 by matching the 3D distance images, Dimensional map using the position information of the stereo image photographing apparatus 110 corresponding to the distance images and the three-dimensional distance images (S44).

이를 보다 구체적으로 설명하면, 먼저 단계 S41에서 스테레오 영상 촬영 장치(110)는 소정의 시간 간격으로 스테레오 영상들을 연속적으로 촬영한다. 다음으로, 단계 S42에서 거리 영상 생성 장치(120)는 스테레오 영상 촬영 장치(110)에 의해 촬영된 스테레오 영상으로부터 3차원 거리 영상을 생성한다.More specifically, in step S41, the stereo image photographing apparatus 110 continuously photographs stereo images at predetermined time intervals. Next, in step S42, the distance image generating apparatus 120 generates a three-dimensional distance image from the stereo image photographed by the stereo image photographing apparatus 110. [

도 5는 도 4에 도시된 단계 S42의 흐름도이다. 도 2 및 도 5를 참조하여 단계 S42를 보다 구체적으로 설명하면 다음과 같다. 먼저, 단계 S51에서 보정부(121)는 영상 교정(Image Rectification)을 수행하여, 소정의 시간 간격으로 획득된 각 스테레오 영상의 좌안 영상 및 우안 영상의 왜곡을 보정한다. 예를 들어, 스테레오 영상 촬영 장치(110)의 각 카메라(좌안 영상 촬영용 카메라 및 우안 영상 촬영용 카메라)로부터 획득한 영상은 카메라가 가지고 있는 고유의 렌즈 특성에 의해 왜곡된 형태로 저장될 수 있다. 이러한 경우에 있어, 에피폴라 제약(Epipolar constraint)을 만족하는 삼각화(triangulation)를 정상적으로 수행하기 위해, 영상의 왜곡을 없애는 영상 교정을 수행할 수 있다. 이러한 영상 교정에 의하여, 각 카메라의 영상면은 각 영상의 행이 수평적으로 일치되도록 정렬될 수 있다.5 is a flowchart of step S42 shown in Fig. Step S42 will be described in more detail with reference to FIGS. 2 and 5 as follows. First, in step S51, the correcting unit 121 performs image rectification to correct distortions of the left eye image and the right eye image of each stereo image acquired at predetermined time intervals. For example, an image obtained from each camera (a camera for a left eye image and a camera for a right eye image) of the stereo image photographing apparatus 110 may be stored in a distorted form due to inherent lens characteristics of the camera. In this case, in order to normally perform triangulation satisfying the epipolar constraint, the image correction that eliminates image distortion can be performed. By this image correction, the image plane of each camera can be aligned such that the rows of each image are horizontally aligned.

다음으로, 단계 S52에서 저역통과 필터(Low-Pass Filter)(122)는 좌안 영상 및 우안 영상의 잡음을 제거한다. 단계 S51에 따른 영상 교정을 거친 교정 영상(rectified image)은 에일리어싱(aliasing) 현상을 보일 수 있으므로, 저역통과 필터(122)는 교정 영상으로부터 에일리어싱 현상의 원인이 되는 고주파 성분을 제거할 수 있다. 저역통과 필터(122)는 예를 들어 교정 영상에 대해서 가우시안 필터(Gaussian filter)를 적용하여 영상의 평활화를 실시할 수 있다.Next, in step S52, a low-pass filter 122 removes noise of the left eye image and the right eye image. The rectified image subjected to the image correction according to the step S51 may exhibit an aliasing phenomenon, so that the low-pass filter 122 can remove the high-frequency component which causes the aliasing phenomenon from the corrected image. The low-pass filter 122 may apply a Gaussian filter to the corrected image to smooth the image.

단계 S53에서 스테레오 매칭부(123)는 스테레오 영상의 좌안 영상 및 우안 영상을 매칭시킨다. 일 실시예에 있어서, 스테레오 매칭부(123)는 SAD(Sum of Absolute Difference) 알고리즘을 사용하여 스테레오 영상의 좌안 영상 및 우안 영상을 매칭시킴으로써, 스테레오 영상의 좌안 영상 및 우안 영상 사이의 일치점(corresponding point)을 획득할 수 있다.In step S53, the stereo matching unit 123 matches the left eye image and the right eye image of the stereo image. In one embodiment, the stereo matching unit 123 matches the left eye image and the right eye image of a stereo image using a Sum of Absolute Difference (SAD) algorithm so that a corresponding point between the left eye image and the right eye image of the stereo image Can be obtained.

단계 S54에서 삼각화부(124)는 삼각화 기법을 이용하여 스테레오 영상에 대응하는 3차원 정보를 산출함으로써, 3차원 거리 영상을 생성한다. 단계 S53에서 스테레오 매칭부(123)에 의한 스테레오 매칭을 통하여, 좌안 영상으로부터 매칭점 (x₁,y₁)이 획득되고, 우안 영상으로부터 매칭점 (x_r,y_r)이 획득되었을 때, 삼각화부(124)는 아래의 수식 1에 따라 카메라 좌표계의 3차원 점을 산출함으로써, 3차원 거리 영상을 생성할 수 있다.In step S54, the triangulation unit 124 generates a three-dimensional distance image by calculating three-dimensional information corresponding to the stereo image using a triangulation technique. When the matching point (x ₁ , y ₁ ) is obtained from the left eye image and the matching point (x _r , y _r ) is obtained from the right eye image through stereo matching by the stereo matching unit 123 in step S 53, The distance calculation unit 124 can generate a three-dimensional distance image by calculating a three-dimensional point of the camera coordinate system according to Equation 1 below.

[수식 1][Equation 1]

여기서, PC는 카메라 좌표계의 3차원 점, X, Y, Z는 각각 3차원 점의 X축, Y축, Z축 좌표, T는 트랜스포즈(Transpose), b는 좌안 영상 촬영 카메라와 우안 영상 촬영 카메라 사이의 거리(베이스라인 거리), x_c는 영상의 설정된 x축 중심 좌표, y_c는 영상의 설정된 y축 중심 좌표, f는 카메라의 초점 거리를 나타낸다. 좌안 영상 촬영 카메라와 우안 영상 촬영 카메라의 초점 거리가 다를 경우, f는 단계 S51에서의 영상 교정을 통해 보정된 초점 거리를 의미할 수 있다.Here, PC is a three-dimensional point of the camera coordinate system, X, Y and Z are X-axis, Y-axis and Z-axis coordinates of a three-dimensional point, T is a transpose, b is a left- X _c is the x-axis center coordinate of the image, y _c is the y-axis center coordinate of the image, and f is the focal length of the camera. When the focal distance of the left eye image capturing camera and that of the right eye image capturing camera are different, f may mean a focal distance corrected through image correction in step S51.

다시 도 4를 참조하면, 단계 S42에서 거리 영상 생성 장치(120)에 의해 3차원 거리 영상이 생성되면, 단계 S43에서 위치 추정 장치(130)는 스테레오 영상들에 대응하는 3차원 거리 영상들을 정합함으로써, 스테레오 영상 촬영 장치(110)의 위치 정보를 추정한다. 일 실시예에 있어서, 위치 추정 장치(130)는 스테레오 영상들의 2차원 특징점들을 이용하여 스테레오 영상들에 대응하는 3차원 거리 영상들을 정합하여 스테레오 영상 촬영 장치(110)의 움직임을 추정함으로써 스테레오 영상 촬영 장치(110)의 위치 정보를 추정할 수 있다.Referring again to FIG. 4, in step S42, when a three-dimensional distance image is generated by the distance image generation apparatus 120, the position estimation apparatus 130 in step S43 aligns three-dimensional distance images corresponding to the stereo images , And estimates the position information of the stereo image photographing apparatus 110. In one embodiment, the position estimating apparatus 130 estimates the motion of the stereo image photographing apparatus 110 by matching the three-dimensional distance images corresponding to the stereo images using the two-dimensional feature points of the stereo images, The location information of the device 110 can be estimated.

도 6은 도 4에 도시된 단계 S43의 흐름도이다. 도 3 및 도 6을 참조하면, 먼저, 단계 S61에서 특징점 추출부(131)는 연속적으로 촬영된 스테레오 영상들로부터 2차원 특징점을 추출한다. 일 실시예에 있어서, t-1 시점에서 촬영된 이전 프레임에 해당하는 스테레오 영상과, t 시점에서 촬영된 현재 프레임에 해당하는 스테레오 영상이 존재하는 경우, 특징점 추출부(131)는 이전 프레임에 해당하는 스테레오 영상의 좌안 영상 및 현재 프레임에 해당하는 스테레오 영상의 좌안 영상으로부터 2차원 특징점을 추출하거나, 이전 프레임에 해당하는 스테레오 영상의 우안 영상 및 현재 프레임에 해당하는 스테레오 영상의 우안 영상으로부터 2차원 특징점을 추출할 수 있다.6 is a flowchart of step S43 shown in Fig. Referring to FIGS. 3 and 6, first, in step S61, the feature point extraction unit 131 extracts two-dimensional feature points from the continuously captured stereo images. In one embodiment, if there is a stereo image corresponding to a previous frame photographed at a time point t-1 and a stereo image corresponding to a current frame photographed at a time point t, the feature point extracting unit 131 extracts Dimensional feature points from the left eye image of the stereo image corresponding to the current frame and the left eye image of the stereo image corresponding to the current frame or the right eye image of the stereo image corresponding to the current frame, Can be extracted.

단계 S62에서 특징점 매칭부(132)는 연속되는 프레임에 해당하는 스테레오 영상들의 2차원 특징점을 매칭시킨다. 일 실시예에 있어서, 특징점 매칭부(132)는 SURF 알고리즘을 이용하여 시간적으로 연속적으로 촬영된 두 스테레오 영상의 2차원 특징점을 매칭할 수 있다. 단계 S61에서 이전 스테레오 영상의 좌안 영상과 현재 스테레오 영상의 좌안 영상(또는 우안 영상)으로부터 2차원 특징점을 추출한 경우, 특징점 매칭부(132)는 이전 스테레오 영상의 좌안 영상(또는 우안 영상)으로부터 추출된 2차원 특징점 및 현재 스테레오 영상의 좌안 영상(또는 우안 영상)으로부터 추출된 2차원 특징점을 매칭할 수 있다. 특징점 매칭부(132)는 예를 들어, 64차원의 벡터로 이루어진 기술자들을 서로 비교한 뒤 유사도가 가장 높은 특징점을 선택함으로써 시간적으로 연속하는 두 스테레오 영상의 정합(matching) 관계를 획득할 수 있다. 특징점 매칭부(132)는 예를 들어, 최근접 이웃법(nearest neighbor) 또는 FLANN(Fast Library for Approximate Nearest Neighbors) 등의 기법을 사용하여 특징점 매칭을 수행함으로써, 일치점(correspondence point)을 찾을 수 있다. 일 실시예에 있어서, 특징점 매칭부(132)는 매칭 성능을 높이기 위해, 기술자 비교시 특징점의 기하적인 제약을 추가할 수 있다. 특징점 매칭부(132)는 특징점 매칭시 예를 들어 아래의 조건들을 만족하는지 여부를 확인하여, 해당 조건들 a), b), c)을 모두 만족하는 특징점을 일치점으로 결정할 수 있다.In step S62, the feature point matching unit 132 matches two-dimensional feature points of stereo images corresponding to consecutive frames. In one embodiment, the feature point matching unit 132 may match the two-dimensional feature points of two stereo images taken temporally consecutively using the SURF algorithm. In step S61, when the two-dimensional feature point is extracted from the left eye image of the previous stereo image and the left eye image (or the right eye image) of the current stereo image, the feature point matching unit 132 extracts the two- Two-dimensional feature points and two-dimensional feature points extracted from the left eye image (or right eye image) of the current stereo image can be matched. The feature point matching unit 132 may acquire a matching relationship of two stereo images temporally continuous, for example, by comparing descriptors having a 64-dimensional vector with each other and then selecting feature points having the highest similarity. The feature point matching unit 132 can perform a feature point matching using a technique such as a nearest neighbor or Fast Library for Approximate Nearest Neighbors (FLANN) to find a correspondence point . In one embodiment, the feature point matching unit 132 may add geometric constraints of feature points in comparing descriptors to enhance matching performance. The feature point matching unit 132 may determine whether the feature points a), b), and c) satisfy the following conditions, for example, when matching the feature points.

a) 회전 제약 : 일치점 사이의 방향 차이는 20°이내여야 한다.a) Rotational constraint: The directional difference between coincidence points shall be within 20 °.

b) 스케일 제약 : 일치점 사이의 스케일 차는 한 단계 내외이거나 같은 스케일이어야 한다.b) Scale constraint: The scale difference between coincidence points should be one step or the same scale.

c) 매칭 유일성 제약 : 일대다 매칭 결과를 보이는 특징점에 대해서는 모호성이 있는 것으로 판단하여 일치점 군에서 제외시킨다. 매칭을 성공한 특징점들은 일대일 관계를 유지해야 한다.c) Matching Uniqueness Constraint: It is judged that there is ambiguity about minutiae that show one-to-many matching results, and they are excluded from the matching point group. Matching successful feature points should maintain a one-to-one relationship.

단계 S63에서 외치점 제거부(133)는 2차원 특징점 사이의 외치점을 제거한다. 여기서, 외치점은 좌안 영상과 우안 영상에 대한 소정의 기하 제약을 만족하지 않는 특징점을 말하며, 좌안 영상과 우안 영상에 대한 소정의 기하 제약을 만족하는 내치점과 대비된다. 일 실시예에 있어서, 외치점 제거부(133)는 에피폴라(epipolar) 기하 제약 및 RANSAC(RANdom Sample Consensus) 알고리즘을 이용하여 2차원 매칭 정보의 외치점을 제거할 수 있다.In step S63, the outlier point removing unit 133 removes the outlier point between the two-dimensional feature points. Here, the eclipse point is a feature point that does not satisfy the predetermined geometric constraint on the left eye image and the right eye image, and is compared with an internal point that satisfies predetermined geometric constraints on the left eye image and the right eye image. In one embodiment, the utterance point remover 133 may remove the cue points of the two-dimensional matching information using an epipolar geometry constraint and a RANSAC (Random Sample Consensus) algorithm.

도 7은 스테레오 영상의 좌안 및 우안 영상에 대한 에피폴라 기하를 설명하기 위한 개념도이다. 도 7을 참조하여 스테레오 영상의 좌안 및 우안 영상에 대한 에피폴라 기하 정의에 대해 설명하면 다음과 같다. 도 7에서 O와 O'는 각각 좌안 영상 촬영 카메라, 우안 영상 촬영 카메라의 주축점(principal point)을 나타내며, P는 3차원 공간상에 놓여 있는 객체를 이루는 3차원 점을 나타내며, x는 3차원 점(P)을 좌안 영상 촬영 카메라의 영상 평면(image plane)(IMP1)에 투영하였을 때 맺히는 투영점을 나타내며, x'는 3차원 점(P)을 우안 영상 촬영 카메라의 영상 평면(IMP2)에 투영하였을 때 맺히는 투영점을 나타낸다. 3차원 점(P)과 2차원 투영점들(x,x')은 에피폴라 기하 관계에 놓여있다고 말하며, 각 영상 평면(IMP1,IMP2)에 투영된 2차원 점(x,x')은 일치점(또는 정합점)으로 간주될 수 있다. 그리고 각 카메라의 주축점들(O,O') 사이를 잇는 선에 해당하는 에피폴라 축(epipolar axis)

과 각 영상 평면(IMP1,IMP2)이 교차하여 만들어지는 점을 에피폴(epipole)(e, e')로 칭하며, 카메라 주축점(O, O') 및 대상 공간에 존재하는 3차원 점(P)에 의해 만들어지는 삼각형 면을 포함하는 평면을 에피폴라 면(epipolar plane)(EP)이라고 부른다.7 is a conceptual diagram for explaining the epipolar geometry for the left eye and right eye images of a stereo image. The definition of the epipolar geometry for the left eye and right eye images of a stereo image will be described with reference to FIG. In FIG. 7, O and O 'represent the principal points of the left eye imaging camera and the right eye imaging camera, respectively, P represents a three-dimensional point constituting an object lying on the three-dimensional space, Represents a projection point formed when the point P is projected onto the image plane IMP1 of the left eye imaging camera and x 'represents the projection point of the 3D point P on the image plane IMP2 of the right eye imaging camera Represents a projected point that is formed when projected. The two-dimensional point (x, x ') projected on each of the image planes (IMP1, IMP2) is referred to as a coincidence point (Or a matching point). And an epipolar axis corresponding to a line connecting the main axis points (O, O ') of each camera,

(O, O ') and a three-dimensional point P existing in the object space (P, E') are referred to as epipoles ) Is referred to as an epipolar plane (EP).

좌안 영상 촬영 카메라의 영상 평면(IMP1)에 맺히는 투영점(x)은 3차원 점(P)과 좌안 영상 촬영 카메라의 주축점(O)을 연결하는 선

위의 한 점이 되며, 원근(perspective)법을 사용하는 핀홀(pinhole) 카메라 모델을 사용하는 것으로 가정하였을 때, 핀홀 카메라 모델의 특성에 따라,

선 상의 무수한 점들이 같은 영상점 x로 투영될 수 있다. 선

상에 있는 3차원 점 P_k(k=1...n)을 우측 영상 평면(IMP2)에 투영하였을 때 맺히는 2차원 투영점들은 영상점 x'와 에피폴 e'를 잇는 선

상에 놓이게 되며, 이와 같이 에피폴라 면(EP)이 영상 평면(IMP2)과 교차하면서 만들어지는 선

을 에피폴라 선(epipolar line)(EL)이라고 부른다.The projection point x formed on the image plane IMP1 of the left eye image capturing camera is a line connecting the three-dimensional point P and the main axis point O of the left eye image capturing camera

If one assumes that a pinhole camera model using a perspective method is used, then, depending on the characteristics of the pinhole camera model,

Numerous points on the line can be projected at the same image point x. line

The two-dimensional projection points formed when the three-dimensional point P _k (k = 1 ... n) on the right image plane IMP2 are projected on the image plane x '

And thus the epipolar plane EP intersects with the image plane IMP2,

Is called an epipolar line (EL).

기본행렬(Fundamental Matrix)은 에피폴라 기하를 대수적으로 표현하기 위해 활용되는 행렬이다. 동차좌표계(homogeneous coordinate)로 표현하였을 때, 에피폴라 기하에 따라 2차원 일치점 x와 x'의 관계는 예를 들어 3×3 행렬에 해당하는 기본행렬을 이용하여 아래의 수식 2로 나타낼 수 있다. The Fundamental Matrix is a matrix that is used to express the epipolar geometry algebraically. When expressed as a homogeneous coordinate, the relationship between the two-dimensional coincidence x and x 'according to the epipolar geometry can be expressed by the following equation (2) using, for example, a basic matrix corresponding to a 3 × 3 matrix.

[수식 2][Equation 2]

여기서, F는 기본행렬, Fx는 에피폴라 선(EL)을 의미한다. 이때, 두 일치점 x, x'의 z축 좌표는 영상 교정을 통해 '1'의 값을 갖도록 보정된 것으로 가정한다. x'는 에피폴라 선(EL) 위의 한 점이어야 하므로, 기본행렬 F는 에피폴라 제약을 나타내는 행렬이라 할 수 있다. 따라서, 두 영상 사이의 에피폴라 기하 관계를 설명하는 기본행렬 F를 정확하게 산출할 수 있다면, 두 영상 사이의 일치점(x,x')은 물론 외치점(outlier point)을 구분할 수 있다.Here, F denotes a basic matrix and Fx denotes an epipolar line (EL). At this time, it is assumed that the z-axis coordinates of the two coincidence points x and x 'are corrected to have a value of' 1 'through image correction. Since x 'must be a point on the epipolar line (EL), the basic matrix F can be said to be a matrix indicating an epipolar constraint. Therefore, if the basic matrix F describing the epipolar geometric relationship between two images can be accurately calculated, it is possible to distinguish the outliers as well as the coincidence points (x, x ') between the two images.

외치점 제거부(133)는 에피폴라(epipolar) 기하 제약 및 RANSAC 알고리즘을 이용하여 외치점을 구분하고, 2차원 매칭 정보의 외치점을 제거할 수 있다. 일 실시예에 있어서, 외치점 제거부(133)는 기본행렬을 만들기 위한 8개의 일치점을 선택하고, 선택한 8개의 일치점으로 8점 알고리즘을 적용하여 기본행렬 F를 구성할 수 있다. 다음으로, 외치점 제거부(133)는 a) 기본행렬 F에 나머지 일치점들을 모두 적용한 뒤, b) 일치점이라고 판단되는 갯수를 카운트하고, c) 그 값이 미리 정해진 임계치(threshold)를 넘을 경우 알고리즘을 중단하고, d) 외치점이라고 판단되는 점들의 정보를 리턴할 수 있다. 만약, 일치점이라고 판단되는 갯수가 임계치에 미치지 못하는 경우에는 과정 a)~d)를 L회 반복 수행할 수 있다. 이때, 반복횟수 L은 아래 수식 3에 의하여 확률적으로 계산될 수 있다.The utterance point removing unit 133 can distinguish the utterance points using the epipolar geometry constraint and the RANSAC algorithm, and remove the utterance points of the two-dimensional matching information. In one embodiment, the utterance point removing unit 133 can construct the basic matrix F by selecting eight coincidence points for creating a basic matrix and applying an eight-point algorithm to the selected eight coincidence points. Next, the outlier point removing unit 133 a) applies all the remaining coincidence points to the basic matrix F, b) counts the number of coincidence points, and c) if the value exceeds a predetermined threshold, And d) return the information of the points determined as the outlier points. If the number of coincident points does not reach the threshold value, steps a) to d) may be repeated L times. At this time, the number L of repetitions can be calculated stochastically according to Equation (3) below.

[수식 3][Equation 3]

여기서, p_fail은 하나의 데이터에 대한 RANSAC 테스트가 실패할 확률을 나타내며, p_g는 적어도 한 개의 데이터가 테스트에 성공할 확률을 나타낸다. L회의 반복 수행에도 불구하고 정해진 임계치를 만족하지 못하는 경우 외치점 걸러내기를 중단하고 알고리즘이 실패한 것으로 간주할 수 있다.Here, p _fail denotes the probability of failure of the RANSAC test for one piece of data, and p _g denotes the probability that at least one piece of data succeeds in the test. If the determined threshold is not satisfied despite the repetition of L times, it is possible to stop the filtering of the outlier and consider the algorithm to be unsuccessful.

외치점 제거부(133)는 아래의 수식 4를 사용하여 에피폴라 선과 일치점 사이의 거리를 계산한 뒤, 전체 특징점들(매칭점들) 중에서 오류값(ε)이 미리 결정된 수치 이하에 해당하는 일치점들의 수가 일정 비율을 넘었을 때, 기본행렬이 유효하다고 판단하여, 외치점들을 매칭군에서 제외시킬 수 있다.The utterance point removing unit 133 calculates the distance between the epipolar line and the point of coincidence using Equation 4 below and then calculates the distance between the point of coincidence where the error value? It is determined that the basic matrix is valid, and the outlier points can be excluded from the matching group.

[수식 4][Equation 4]

다시 도 6을 참조하면, 단계 S64에서 움직임 추정부(134)는 외치점이 제외된 2차원 특징점들의 정보를 사용하여 3차원 거리 영상들의 움직임을 추정할 수 있다. 일 실시예에 있어서, 움직임 추정부(134)는 2차원 특징점들에 대응하는 3차원 거리 영상의 3차원 특징점들을 이용하여 연속되는 3차원 거리 영상들 간의 변환 행렬을 최적화함으로써 스테레오 영상 촬영 장치(110)의 움직임을 추정할 수 있다. 즉, 움직임 추정부(134)는 연속하는 두 프레임 사이의 3차원 대 3차원 매칭(정합) 관계를 구함으로써, 스테레오 영상 촬영 장치(110)의 3차원 카메라 모션(motion)을 추정할 수 있다. 카메라 모션은 예를 들어 강체 변환(rigid body transformation)을 사용하여 계산될 수 있다. 각 영상 프레임에 대한 카메라 자세(pose)의 정확도는 2차원 특징점과 대응되는 3차원 깊이 정보의 정확도에 의하여 영향받을 수 있으므로, 움직임 추정부(134)는 신뢰할 수 있는 3차원 특징점들을 구분해내어 3차원 움직임을 추정할 수 있다. 잘못된 3차원 깊이 정보를 가려내기 위하여, 3차원 월드 공간에서 강체는 변하지 않는다는 강체 지속성 제약을 이용하여 복원된 3차원 데이터에 대한 신뢰도 테스트를 수행할 수 있다.Referring again to FIG. 6, in step S64, the motion estimation unit 134 may estimate the motion of the three-dimensional distance images using the information of the two-dimensional feature points excluding the outlier point. In one embodiment, the motion estimation unit 134 may optimize the transformation matrix between successive three-dimensional distance images using the three-dimensional feature points of the three-dimensional distance image corresponding to the two-dimensional feature points, Can be estimated. That is, the motion estimation unit 134 can estimate the three-dimensional camera motion of the stereo image photographing apparatus 110 by obtaining a three-dimensional to three-dimensional matching (matching) relationship between two consecutive frames. The camera motion can be computed using, for example, a rigid body transformation. Since the accuracy of the camera pose for each image frame can be influenced by the accuracy of the 3D depth information corresponding to the 2D feature points, the motion estimation unit 134 classifies the reliable 3D feature points into 3 Dimensional motion can be estimated. In order to detect the incorrect 3D depth information, a reliability test can be performed on the restored 3D data using the rigid body persistence constraint that the rigid body does not change in the 3D world space.

카메라가 동일한 3차원 장면(scene)을 바라보면서 움직이고 있다고 가정하였을 때, 각 카메라의 뷰 시점에서 획득된 3차원 데이터는 강체 지속 특성에 따라 원칙적으로는 같은 크기(scale)로 복원되어야 한다. 도 8은 강체 지속성 제약에 대하여 설명하기 위한 개략도이다. 도 8을 참조하면, 이전 프레임(frame t-1)과 현재 프레임(frame t) 사이에서 임의로 2차원 매칭 관계에 있는 2개의 일치점 {(xⁱ _t-1,xⁱ _t),(x^j _t-1,x^j _t)}이 선택되었을 때, 3차원 거리 영상을 사용하면 각 카메라 좌표계를 기준으로 2개의 일치점과 대응하는 3차원 깊이 정보 {(Xⁱ _t-1,Xⁱ _t),(X^j _t-1,X^j _t)}를 획득할 수 있다.Assuming that the camera is moving while looking at the same three-dimensional scene, the three-dimensional data acquired at the viewpoint of each camera should be restored to the same scale in principle according to the rigid body continuity characteristic. 8 is a schematic diagram for explaining rigid persistence constraints. Referring to FIG. 8, two coincident points {(x ⁱ _t-1 , x ⁱ _t ), (x ^j _t ( _t ) _-1, ^j x _t)} this three-dimensional image by using a distance a three-dimensional depth information ^{_{{(X i t-1,}} X i t) corresponding to the two ilchijeom relative to the camera coordinate system when each is selected, ( X ^j _t-1 , X ^j _t )}.

이전 프레임(frame t-1)에 해당하는 2개의 3차원 점 (Xⁱ _t _-1,X^j _t _-1) 사이의 유클리디안 거리(euclidean distance)는 강체 지속 제약에 따라 현재 프레임(frame t)에 해당하는 2개의 3차원 점 (Xⁱ _t,X^j _t) 사이의 유클리디안 거리와 같거나 적어도 유사해야 한다. 아래의 수식 5는 이러한 강체 지속성 제약을 나타낸다.The euclidean distance between two three-dimensional points (X ⁱ _t _-1 , X ^j _t _-1 ) corresponding to the previous frame (frame t-1) (X ⁱ _t , X ^j _t ) corresponding to the three-dimensional point (X ⁱ , X ^j ). Equation 5 below represents this rigid body persistence constraint.

[수식 5][Equation 5]

여기서, δ는 미리 설정된 임계값(cm)을 의미한다. 강체 지속성 제약 테스트에 따라 유효하다고 판단된 3차원 대응점군 정보 {X_t _-1}, {X_t}가 최소 세 점 이상 주어졌다고 가정하였을 때, 움직임 추정부(134)는 아래의 수식 6에 따라 에너지값이 최소화되도록 하는 변환 행렬을 산출함으로써, 3차원 거리 영상의 움직임을 추정한다.Here,? Denotes a preset threshold value (cm). When it is assumed that at least three points of three-dimensional corresponding point group information {X _t _-1 } and {X _t } that are determined to be valid according to the rigid body persistence constraint test have been given at least three points, the motion estimation unit 134 calculates The motion of the three-dimensional distance image is estimated by calculating a transformation matrix that minimizes the energy value.

[수식 6][Equation 6]

여기서, T_<t-1,t>는 변환 행렬을 나타내고, R_<t-1,t>는 변환행렬의 회전 행렬을 나타내고, t_<t-1,t>는 변환 행렬의 이동 행렬을 나타내며, e는 에너지값을 나타낸다.Here, T _{<t-1, t>} represents a transformation matrix, R _{<t-1, t>} represents a rotation matrix of the transformation matrix, t _< e represents the energy value.

다음으로, 단계 S65에서 움직임 정제부(135)는 3차원 거리 영상들의 모션(motion)을 정제한다. 일 실시예에 있어서, 움직임 정제부(135)는 2차원 특징점들 및 3차원 특징점들을 이용하여 스테레오 영상 촬영 장치(110)의 투영 행렬을 최적화함으로써 스테레오 영상 촬영 장치(110)의 움직임을 정제할 수 있다. 즉, 움직임 정제부(135)는 투영 오차 최소화를 이용하여 카메라 모션의 정제를 수행할 수 있다. 움직임 정제부(135)는 예를 들어, 아래의 수식 7과 같은 Levenberg-Marquardt 알고리즘을 이용하여 비용함수 값 f_reproj이 최소화가 되도록 하는 비선형 최적화 과정을 수행함으로써, 모션 정제를 수행할 수 있다.Next, in step S65, the motion refinement unit 135 refines the motion of the three-dimensional distance images. In one embodiment, the motion refinement unit 135 may refine the motion of the stereo image photographing apparatus 110 by optimizing the projection matrix of the stereo image photographing apparatus 110 using the two-dimensional feature points and the three- have. That is, the motion refinement unit 135 can perform refinement of the camera motion using the projection error minimization. The motion refinement unit 135 can perform motion refinement, for example, by performing a nonlinear optimization process that minimizes the cost function value f _reproj using the Levenberg-Marquardt algorithm as shown in Equation (7) below.

[수식 7][Equation 7]

여기서, P, X, x는 각각 카메라 투영행렬과 3차원 특징점 및 2차원 특징점을 나타내며, I_t _-1은 이전 프레임의 2차원 점 및 3차원 점을 나타내며, I_t는 현재 프레임의 2차원 점 및 3차원 점을 나타낸다.Here, P, X, and x represent a camera projection matrix, a 3D feature point, and a 2D feature point, I _t _-1 represents a two-dimensional point and a three-dimensional point of the previous frame, and I _t represents a two- And a three-dimensional point.

다시 도 4를 참조하면, 단계 S44에서 3차원 지도 생성부(140)는 거리 영상 생성 장치에 의해 생성된 3차원 거리 영상들 및 위치 추정 장치(130)에 의해 산출한 3차원 거리 영상들에 대응하는 스테레오 영상 촬영 장치(110)의 위치 정보를 이용하여 3차원 지도를 생성할 수 있다. 본 발명의 실시예에 따라 생성된 3차원 지도 정보는 도로 및 주변 환경의 형상 정보 및 색상 정보를 모두 포함할 수 있다. 일 실시예에 의하면, 정확한 위치 정보가 알려져 있는 위치에서부터 3차원 지도 생성을 개시할 경우, 이를 기준으로 스테레오 영상의 분석 및 3차원 거리 영상의 정합을 기반으로 하여, 측정 영역 전체에 대한 위치 정보를 정확하게 추정함으로써, 실제의 도로 및 주변 환경과의 오차가 적은 3차원 지도를 생성할 수 있다.Referring again to FIG. 4, in step S44, the three-dimensional map generation unit 140 generates three-dimensional distance images generated by the distance image generation apparatus and three-dimensional distance images calculated by the position estimation apparatus 130 Dimensional map using the location information of the stereo image photographing apparatus 110. [ The 3D map information generated according to the embodiment of the present invention may include both shape information and color information of the road and surrounding environment. According to an embodiment, when starting the generation of the three-dimensional map from the position where the accurate position information is known, based on the analysis of the stereo image and the matching of the three-dimensional distance image, By accurately estimating the three-dimensional map, it is possible to generate a three-dimensional map with little error between the actual road and the surrounding environment.

이상의 실시예들은 본 발명의 이해를 돕기 위하여 제시된 것으로, 본 발명의 범위를 제한하지 않으며, 이로부터 다양한 변형 가능한 실시예들도 본 발명의 범위에 속할 수 있음을 이해하여야 한다. 예를 들어, 본 발명의 실시예에 도시된 각 구성 요소는 분산되어 실시될 수도 있으며, 반대로 여러 개로 분산된 구성 요소들은 결합되어 실시될 수 있다. 따라서, 본 발명의 기술적 보호범위는 특허청구범위의 기술적 사상에 의해 정해져야 할 것이며, 본 발명의 기술적 보호범위는 특허청구범위의 문언적 기재 그 자체로 한정되는 것이 아니라 실질적으로는 기술적 가치가 균등한 범주의 발명에 대하여까지 미치는 것임을 이해하여야 한다.It is to be understood that the above-described embodiments are provided to facilitate understanding of the present invention, and do not limit the scope of the present invention, and it is to be understood that various modifications may be made within the scope of the present invention. For example, each component shown in the embodiment of the present invention may be distributed and implemented, and conversely, a plurality of distributed components may be combined. Therefore, the technical protection scope of the present invention should be determined by the technical idea of the claims, and the technical protection scope of the present invention is not limited to the literary description of the claims, The invention of a category.

100: 3차원 지도 생성 장치 110: 스테레오 영상 촬영 장치
120: 거리 영상 생성 장치 121: 보정부
122: 저역통과 필터 123: 스테레오 매칭부
124: 삼각화부 130: 위치 추정 장치
131: 특징점 추출부 132: 특징점 매칭부
133: 외치점 제거부 134: 움직임 추정부
135: 움직임 정제부 140: 3차원 지도 생성부100: 3D map generating device 110: stereo image photographing device
120: distance image generating device 121:
122: low-pass filter 123: stereo matching unit
124: Triangulation part 130: Position estimation device
131: feature point extracting unit 132:
133: Outside point removing unit 134: Motion estimation unit
135: motion refinement unit 140: three-dimensional map generation unit

Claims

delete

A stereo image photographing device for photographing stereo images continuously at predetermined time intervals;
A distance image generating device for generating three-dimensional distance images at the predetermined time intervals from the stereo images;
A position estimator for estimating position information of the stereo image photographing apparatus by matching the three-dimensional distance images corresponding to the stereo images; And
And a three-dimensional map generating unit for generating a three-dimensional map using the three-dimensional distance images and the position information of the stereo image photographing apparatus corresponding to the three-dimensional distance images,
The position estimating apparatus includes:
Estimating the position information of the stereoscopic image photographing apparatus by estimating the motion of the stereoscopic image photographing apparatus by matching the 3D distance images corresponding to the stereo images using the feature points of the stereo images,
The position estimating apparatus includes:
A feature point extraction unit for extracting two-dimensional feature points from the stereo images continuously captured;
A feature point matching unit for matching the two-dimensional feature points extracted from the continuous stereo images;
An outlier point removing unit that removes outline points that do not satisfy the stereo geometry constraint among the matched two-dimensional feature points;
Dimensional distance images corresponding to the two-dimensional feature points so that an energy value representing a distance value between corresponding three-dimensional feature points in successive three-dimensional distance images is minimized by using three-dimensional feature points of the three- A motion estimator for estimating a motion of the stereo image photographing apparatus by calculating a transformation matrix between three-dimensional distance images; And
Calculating a projection matrix of the stereo image photographing apparatus using the two-dimensional feature points, the three-dimensional feature points, and the transformation matrix so that a cost function value is minimized according to a Levenberg-Marquardt algorithm, And a motion refinement unit for refining the motion,
Wherein the 3D distance images include a first distance image and a second distance image,
Wherein the corresponding three-dimensional feature points include first corresponding points of the first distance image and second corresponding points of the second distance image that correspond one-to-one to the first corresponding points,
Wherein the motion estimator comprises:
A distance between the first corresponding point and a point at which the conversion matrix is applied to a second corresponding point corresponding to the first corresponding point is calculated for each of the first corresponding points and a distance between the first corresponding point and the second corresponding point corresponding to the first corresponding points is calculated Estimating a motion of the stereo imaging apparatus by calculating the transformation matrix such that the energy value corresponding to the sum is minimized,
The difference between the Euclidean distance between the first corresponding points and the Euclidean distance between the second corresponding points has a value smaller than a preset threshold value,
Wherein the motion estimator estimates the motion by calculating the transformation matrix such that the energy value is minimized according to Equation 1 below,
[Formula 1]

_{Wherein t <t-1, t>} represents the transformation matrix, R _{<t-1, t>} represents a rotation matrix of the transformation matrix, and t _< Wherein X ⁱ _t-1 represents the first corresponding point, X ⁱ _t represents the second corresponding point, N represents the number of the first corresponding points, Wherein N represents the number of corresponding points, and N represents an integer value of 3 or more.

The method of claim 3,
The distance image generating apparatus includes:
A correcting unit correcting distortion of the left eye image and the right eye image of each stereo image acquired at the predetermined time interval;
A low pass filter for removing noise of the left eye image and the right eye image;
A stereo matching unit for matching the left eye image and the right eye image; And
Dimensional map corresponding to the stereo image based on a triangulation technique to generate the three-dimensional distance image.

The method of claim 3,
Wherein the stereoscopic image photographing apparatus is mounted on a vehicle and continuously photographs the stereo images including the road and the surrounding environment of the road at the predetermined time intervals as the vehicle travels.

delete

Continuously photographing stereo images at predetermined time intervals using a stereo image photographing apparatus;
Generating three-dimensional distance images at the predetermined time intervals from the stereo images;
Estimating position information of the stereoscopic image photographing apparatus by matching the three-dimensional distance images corresponding to the continuously captured stereoscopic images; And
Dimensional map using the position information of the stereo image photographing apparatus corresponding to the three-dimensional distance images and the three-dimensional distance images,
Wherein the step of estimating the position information comprises:
Estimating the position information of the stereoscopic image photographing apparatus by estimating the motion of the stereoscopic image photographing apparatus by matching the 3D distance images corresponding to the stereo images using the feature points of the stereo images,
Wherein the step of estimating the position information comprises:
Extracting two-dimensional feature points from the continuously captured stereo images;
Matching the two-dimensional feature points extracted from the continuous stereo images;
Removing an outlier point that does not satisfy the stereo geometry constraint among the matched two-dimensional feature points;
Dimensional distance images corresponding to the two-dimensional feature points so that an energy value representing a distance value between corresponding three-dimensional feature points in successive three-dimensional distance images is minimized by using three-dimensional feature points of the three- Estimating a motion of the stereoscopic image photographing apparatus by calculating a transformation matrix between three-dimensional distance images; And
Calculating a projection matrix of the stereo image photographing apparatus using the two-dimensional feature points, the three-dimensional feature points, and the transformation matrix so that a cost function value is minimized according to a Levenberg-Marquardt algorithm, And refining the motion,
Wherein the 3D distance images include a first distance image and a second distance image,
Wherein the corresponding three-dimensional feature points include first corresponding points of the first distance image and second corresponding points of the second distance image that correspond one-to-one to the first corresponding points,
Estimating the motion comprises:
Calculating a distance between the first corresponding point and a point at which the conversion matrix is applied to the second corresponding point, for each of the first corresponding points, and calculating the energy corresponding to the sum of the distances calculated for each of the first corresponding points Calculating a value; And
And estimating the motion of the stereo image photographing apparatus by calculating the transformation matrix such that the energy value is minimized,
The difference between the Euclidean distance between the first corresponding points and the Euclidean distance between the second corresponding points has a value smaller than a preset threshold value,
Wherein the motion estimator estimates the motion by calculating the transformation matrix such that the energy value is minimized according to Equation 1 below,
[Formula 1]

9. The method of claim 8,
Wherein the generating the three-dimensional distance images comprises:
Correcting distortion of the left eye image and the right eye image of each stereo image acquired at the predetermined time interval;
Removing noise of the left eye image and the right eye image;
Matching the left eye image and the right eye image; And
And generating the three-dimensional distance image by calculating three-dimensional information corresponding to the stereo image based on the triangulation technique.

delete