KR102457891B1 - 이미치 처리 방법 및 장치 - Google Patents

Abstract

3차원 이미지를 위한 깊이(depth) 정보를 산출하는 방법이 개시된다. 깊이(depth) 정보를 산출하는 방법은 2차원 이미지에 포함되는 적어도 하나의 셀의 값에 기초하여 패턴을 생성하는 과정, 상기 패턴을 투사하는 과정, 상기 패턴이 반사된 이미지를 촬영하는 과정 및 상기 패턴이 반사된 이미지에 기초하여 상기 깊이 정보를 산출하는 과정을 포함한다.

Description

이미치 처리 방법 및 장치 {METHOD AND APPARATUS FOR IMAGE PROCESSING}

본 발명의 다양한 실시 예들은 이미지 처리 방법 및 장치에 대한 것으로, 보다 상세하게는, 2차원 및 3차원 이미지 처리를 위한 방법 및 장치에 대한 것이다.

증강현실(AR: augmented reality) 또는 가상현실(VR: virtual reality)에 대한 관심도가 높다. 이에 따라, 증강현실(또는 가상현실)을 구현하고자 하는 전자 기기가 다양하게 개발되고 있다.

증강현실(또는 가상현실)을 구현하기 위하여, 3D 환경을 모델링 기법들이 개발되고 있으며, 그 예로는 수동 입체 방식 및 능동 투사 방식이 있다.

3D 환경을 리모델링하기 위해서는 이미지의 깊이 정보가 필요하다. 깊이 정보를 산출하기 위해 다양한 방법이 개발되고 있으며 그 예로는, 일정한 코드를 투사하여 이를 기반으로 깊이 정보를 산출하는 구조 광 기반 해법들이 있다.

본 발명은, 3D 환경을 모델링하기 위한 이미지 처리 방법 및 장치를 제공한다.

본 발명의 일 실시 예에 따른 깊이 정보 산출 방법은, 2차원 이미지에 포함되는 적어도 하나의 셀의 값에 기초하여 패턴을 생성하는 과정, 상기 패턴을 투사하는 과정, 상기 패턴이 반사된 이미지를 촬영하는 과정 및 상기 패턴이 반사된 이미지에 기초하여 상기 깊이 정보를 산출하는 과정을 포함한다.

본 발명의 일 실시 예에 따른 단말은, 프로젝터, 촬영부 및 2차원 이미지에 포함되는 적어도 하나의 셀의 값에 기초하여 패턴을 생성하고, 상기 패턴을 투사하도록 상기 프로젝터를 제어하고, 상기 패턴이 반사된 이미지를 촬영하도록 상기 촬영부를 제어하고, 상기 패턴이 반사된 이미지에 기초하여 상기 깊이 정보를 산출하는 프로세서를 포함한다.

상술한 바와 같이, 본 발명에 따르면, 깊이 정보를 산출하여 3D 환경을 모델링할 수 있다.

도 1은 본 발명의 일 실시 예에 따른 3차원(3D) 환경 맵 복원 시스템을 도시한다.
도 2는 본 발명의 일 실시 예에 따른 단말을 도시한다.
도 3은 본 발명의 다른 실시 예에 따른 단말을 도시한다.
도 4는 본 발명의 일 실시 예에 따른 단말의 블록도이다.
도 5a 및 5b는 본 발명의 다양한 실시 예에 따른 이차원 세포 자동화를 위해 고려되는 이웃 구조들을 도시한다.
도 6은 본 발명의 일 실시 예에 다른 세포 자동화 패턴 생성 방법의 흐름도이다.
도 7은 본 발명의 일 실시 예에 따른 2차원 이미지를 도시한다.
도 8은 본 발명의 일 실시 예에 다른 세포 자동화 패턴 생성을 위한 규칙을 도시한다.
도 9는 본 발명의 일 실시 예에 따른 연속된 셀들을 도시한다.
도 10은 본 발명의 일 실시 예에 따른 인접한 셀들을 도시한다.
도 11은 본 발명의 일 실시 예에 따른 최초값 설정 방법을 설명하기 위한 도면이다.
도 12는 본 발명의 일 실시 예에 따른 초기값이 설정된 결과를 도시한다.
도 13 내지 17은 본 발명의 일 실시 예에 따른 세포 자동화의 세부 과정을 도시한다.
도 18은 본 발명의 일 실시 예에 따른 전자장 필터에 대한 피치 크기와 세포 자동생성을 위한 셀 크기를 결정 방법을 설명하기 위한 도면이다.
도 19는 본 발명의 일 실시 예에 따른 2차원 이미지를 도시한다.
도 20은 본 발명의 다른 실시 예에 따른 2차원 이미지를 도시한다.
도 21은 본 발명의 일 실시 예에 따른 세포 자동화 패턴의 프로젝션 및 캡쳐 과정을 도시한다.
도 22는 본 발명의 다른 실시 예에 따른 세포 자동화 패턴의 프로젝션 및 캡쳐 과정을 도시한다.
도 23은 본 발명의 일 실시 예에 따른 세포 자동화 패턴의 디코딩 방법의 흐름도이다.
도 24a 및 24b는 본 발명의 일 실시 예에 따른 클러스터링 방법을 도시한다.
도 25a 내지 25e는 본 발명의 일 실시 예에 따른 클러스터링의 결과를 도시한다.
도 26a 내지 26f는 본 발명의 일 실시 예에 따른 세포 자동화 패턴 인식 방법을 도시한다.
도 27은 본 발명의 일 실시 예에 따른 세포 자동화 패턴의 인덱스를 도시한다.
도 28은 본 발명의 일 실시 예에 따른 세포 자동화 패턴의 인덱스를 처리하는 방법을 도시한다.
도 29a 내지 29h는 본 발명의 일 실시 예에 따른 수평 수직 연결 요소 검색 방법을 도시한다.
도 30a 내지 30h는 본 발명의 일 실시 예에 따른 수직 클러스터에 대한 디스패리티 추정 방법을 도시한다.
도 31a 내지 31d는 본 발명의 일 실시 예에 따른 수평 클러스터에 대한 디스패리티 추정 방법을 도시한다.
도 32a 및 32b는 본 발명의 일 실시 예에 따른 수직 클러스터 차이와 수평 클러스터 차이의 합을 결정하는 방법을 도시한다.
도 33a 및 33b는 본 발명의 일 실시 예에 따른 쉬프트 테이블 결정 방법을 도시한다
도 34a 내지 34g는 본 발명의 다른 실시 예에 따른 수직 클러스터에 대한 디스패리티 추정 방법을 도시한다.
도 35a 및 35b는 본 발명의 다른 실시 예에 따른 쉬프트 테이블 결정 방법을 도시한다
도 36a 내지 36c는 본 발명의 또 다른 실시 예에 따른 쉬프트 테이블 결정 방법을 도시한다
도 37a 내지 37c는 본 발명의 또 다른 실시 예에 따른 쉬프트 테이블 결정 방법을 도시한다
도 38a 내지 38e는 본 발명의 일 실시 예에 따른 경계 셀 처리 방법의 예시를 도시한다.
도 39a 내지 39e는 본 발명의 다른 실시 예에 따른 경계 셀 처리 방법의 예시를 도시한다.
도 40a 내지 40e는 본 발명의 또 다른 실시 예에 따른 경계 셀 처리 방법의 예시를 도시한다.
도 41a 내지 41e는 본 발명의 또 다른 실시 예에 따른 경계 셀 처리 방법의 예시를 도시한다.
도 42는 본 발명의 일 실시 예에 따른 오브젝트 분할(object segmentation)을 도시한다.
도 43은 본 발명의 일 실시 예에 따른 오브젝트 분할 방법의 흐름도이다.
도 44a 내지 44h는 본 발명의 일 실시 예에 따른 오브젝트 분할 방법을 설명하기 위한 도면이다.
도 45a 내지 45f는 본 발명의 다른 실시 예에 따른 오브젝트 분할 방법을 설명하기 위한 도면이다.
도 46a 내지 46c는 본 발명의 일 실시 예에 따른 삼각측량 방법을 도시한다.
도 47은 본 발명의 다양한 실시 예에 따른 세포 자동화 격자의 종류들을 도시한다.
도 48은 본 발명의 다양한 실시 예에 따른 직사각 격자에 대한 세포 자동화 규칙들의 예를 제시한다.
도 49는 본 발명의 일 실시 예에 따른 이차원 패턴을 도시한다.
도 50은 본 발명의 다른 실시 예에 따른 이차원 패턴을 도시한다.
도 51은 본 발명의 일 실시 예에 따른 세포 자동화 전개를 도시한다.
도 52는 본 발명의 일 실시 예에 따른 이차원 세포 자동화 규칙을 도시한다.
도 53은 본 발명의 일 실시 예에 따른 세포 자동화를 도시한다.
도 54a 내지 54d는 본 발명의 다른 실시 예에 따른 세포 자동화를 도시한다.
도 55a 내지 55d는 본 발명의 다양한 실시 예에 따른 세포 자동화의 자체 복구를 도시한다.
도 56은 본 발의 일 실시 예에 따른 세포 자동화를 위한 초기 상태들의 생성을 도시한다.
도 57a 및 57b는 본 발명의 일 실시 예에 따른 초기 단계에서 생성된 패턴을 도시한다.
도 58은 본 발명의 다양한 실시 예에 따른 유전적 패턴을 도시한다.
도 59a 및 59b는 본 발명의 다양한 실시 예에 따른 매칭 영역을 도시한다.
도 60은 본 발명의 일 실시 예에 따른 패턴의 이미지 및 세포 자동화의 격자 간 대응관계를 도시한다.
도 61a 및 61b는 본 발명의 일 실시 예에 따른 세포 자동화 격자의 계산된 그리드에 대한 물리적 그리드의 매핑을 도시한다.
도 62는 본 발명의 일 실시 예에 따른 컨볼루션을 도시한다.
도 63a 및 63b는 본 발명의 일 실시 예에 따른 커널 근사화 개념을 도시한다.
도 64는 본 발명의 일 실시 예에 따른 컨볼루션 연산을 도시한다.
도 65는 본 발명의 일 실시 예에 따른 유전적 패턴의 생성을 도시한다.
도 66은 본 발명의 일 실시 예에 따른 정적 자가 조직된 상태를 달성하기 위한 에포크 별 이차원 세포 자동화 전개를 도시한다.
도 67은 본 발명의 일 실시 예에 따른 유전적 알고리즘 GA를 이용하여 전역적 양태를 전개시킴에 따른 이차원 세포 자동화의 단순화되거나 근사화된 성능을 도시한다.
도 68은 본 발명의 일 실시 예에 따른 컨볼루팅 커널로서의 근사화 중 천이 규칙 내 연결 성분을 도시한다.
도 69은 본 발명의 일 실시 예에 따른 포인트 클라우드 밀도 감소를 도시한다.
도 70은 본 발명의 일 실시 예에 따른 3차원 이미지를 위한 깊이 정보를 산출하는 방법을 나타내는 흐름도이다.

이하, 본 발명의 실시 예들을 첨부한 도면들을 참조하여 상세히 설명한다. 그리고, 하기에서는 본 발명의 실시 예들에 따른 동작을 이해하는데 필요한 부분만이 설명되며, 그 이외의 부분의 설명은 본 발명의 요지를 흩트리지 않도록 생략될 것이라는 것을 유의하여야 한다. 그리고 후술되는 용어들은 본 발명의 실시 예들에서의 기능을 고려하여 정의된 용어들로서 이는 사용자, 운용자의 의도 또는 관례 등에 따라 달라질 수 있다. 그러므로 그 정의는 본 명세서 전반에 걸친 내용을 토대로 내려져야 할 것이다.

본 발명은 다양한 변경을 가할 수 있고 여러 가지 실시 예들을 가질 수 있는 바, 특정 실시 예들을 도면들에 예시하여 상세하게 설명한다. 그러나, 이는 본 발명을 특정한 실시 형태에 대해 한정하려는 것이 아니며, 본 발명의 사상 및 기술 범위에 포함되는 모든 변경, 균등물 내지 대체물을 포함하는 것으로 이해되어야 한다.

또한, 본 발명의 실시 예들에서, 별도로 다르게 정의되지 않는 한, 기술적이거나 과학적인 용어를 포함해서 여기서 사용되는 모든 용어들은 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자에 의해 일반적으로 이해되는 것과 동일한 의미를 가지고 있다. 일반적으로 사용되는 사전에 정의되어 있는 것과 같은 용어들은 관련 기술의 문맥상 가지는 의미와 일치하는 의미를 가지는 것으로 해석되어야 하며, 본 발명의 실시 예에서 명백하게 정의하지 않는 한, 이상적이거나 과도하게 형식적인 의미로 해석되지 않는다.

이하에서, 도면을 참조하여 본 개시의 다양한 실시 예들을 상세히 설명한다.

도 1은 본 발명의 일 실시 예에 따른 3차원(3D) 환경 맵 복원 시스템을 도시한다.

3차원 환경 맵 복원 시스템은 전자기파(electromagnetic waves)(또는 광) 소스(source)(22-1), 전자기장 필터 또는 마스크(22), 광 수용부(21)를 포함할 수 있다.

전자기파 소스(22-1)는 전자기파의 빔을 방사(또는 조사)한다.

전자기장 필터 또는 마스크(22)는 렌즈 시스템에 기반하여 오브젝트(29)(또는 3차원 공간)에 방사할 전자기장의 공간 분포의 패턴을 형성한다.

광 수용부(21)는 오브젝트(29)(또는 3차원 공간)로부터 반사되는 전자기장을 감지(detection)하여 전자기장의 공간 분포를 기록한다. 광 수용부(21)는 디텍터(21-1)를 포함할 수 있다.

본 발명의 일 실시 예에 따르면, 전자기파 소스(22-1), 전자기장 필터 또는 마스크(22) 및 광 수용부(21)는 전자 장치에 포함될 수 있다. 이하, 전자 장치의 일 예로 단말의 구성을 상세히 설명한다.

도 2는 본 발명의 일 실시 예에 따른 단말을 도시한다.

도 2를 참조하면, 단말(10)은 광 프로젝터(light projector)(또는 프로젝터) (11, 12), IR(infrared) 카메라(13, 14) 및 RGB 카메라(15)를 포함한다.

광 프로젝터(11, 12)는 패턴(또는 패턴 2차원 이미지)을 투사한다.

IR 카메라(13, 14-1, 14-2)는 투사된 패턴이 오브젝트에 반사된 이미지(예를 들어, 2차원 이미지)를 촬영한다.

RGB 카메라(15)는 예를 들어, 가시광선 영역에서 공간 또는 오브젝트를 촬영한다.

도 2에서, 광 프로젝터(11, 12)와 IR 카메라(13, 14-1, 14-2)는 각각 참조번호 12 및 13(구현 방식 1) 또는 참조번호 11 및 14(구현 방식 2)에 구비될 수 있다. 일 예로, 광 프로젝터(11, 12)와 IR 카메라(13, 14-1, 14-2) 간의 거리(b, 베이스)는 100mm 이하로 설정될 수 있다(16, 18). 또한, RGB 카메라(15)와 IR 카메라(14-1, 14-2) 간의 거리는 10mm 이상 거리로 이격될 수 있다(17).

도 3은 본 발명의 다른 실시 예에 따른 단말을 도시한다.

도 3은 단말(30)의 전면(30-1) 및 후면(30-2)을 도시한다.

단말(30)의 전면(30-1)은 IR 카메라(31) 및 광 프로젝터(32)를 포함한다. 단말(30)의 후면(30-2)은 IR 카메라(33) 및 광 프로젝터(34) 및 RGB 카메라(35)를 포함한다. 여기서, 도 1과 중복되는 설명은 생략한다.

도 4는 본 발명의 일 실시 예에 따른 단말의 블록도이다.

여기서, 도 1 내지 2와 중복되는 설명은 생략한다.

단말(400)은 프로젝터(410), 촬영부(420) 및 프로세서(430)를 포함한다.

프로젝터(410)는 광을 투사한다. 일 예로, 프로젝터(410)는 일정한 광의 패턴을 투사할 수 있다. 여기서, 패턴은 적외선으로 투사될 수 있다.

촬영부(420)는 투사된 광의 이미지를 촬영할 수 있다. 일 예로, 촬영부(420)는 투사된 적외선이 반사된 이미지를 촬영할 수 있다. 여기서, 촬영부(420)는 RGB 촬영 기능을 포함할 수 있다. 또는, 단말(400)은 RGB 촬영 기능을 가지는 촬영부를 추가적으로 포함할 수 있다.

프로세서(430)는 단말(400)을 전반적으로 제어한다. 특히, 프로세서(430)는 세포 자동화 전개를 이용하여 패턴을 생성할 수 있다. 즉, 프로세서(430)는 2차원 이미지에 포함되는 적어도 하나의 셀의 값에 기초하여 패턴을 생성할 수 있다. 패턴을 생성하는 과정은 2차원 이미지에 포함되는 복수의 셀들 각각에 값을 설정하는 과정이다.

2차원 이미지에 포함되는 복수의 셀 각각에는 적어도 두 개의 값들 중 하나가 할당될 수 있다. 여기서, 셀은 2차원 이미지 및 패턴을 구성하는 단위이다. 일 예로, 상기 적어도 두 개의 값은 '0'과 '1'이며, 상기 복수의 셀 각각에는 '0' 또는 '1'이 할당될 수 있다. 또한, 자동화 전개는 복수의 셀에 적어도 두 개의 값들 중 하나를 할당하는 과정을 말한다. 일 예로, 프로세서(430)는 복수의 셀 중 하나에 '0' 또는 '1'을 할당하고, 상기 복수의 셀 중 하나의 인접한 셀에 '0' 또는 '1'을 할당해 나가는 동작을 반복적으로 진행할 수 있다.

일 예로, 자동화 전개는 일차원 전개인 경우를 가정하면, 프로세서(430)는 아래의 수학식 1에 기초하여 일차원 전개를 수행할 수 있다.

다른 예로, 자동화 전개는 이차원 전개인 경우를 가정하면, 프로세서(430)는 아래의 수학식 2에 기초하여 이차원 전개를 수행할 수 있다.

프로세서(430)는 패턴을 생성함에 있어, 2차원 이미지에 포함되는 복수의 셀들의 행 또는 열에 설정된 초기 값을 이용할 수 있다. 일 예로, 행 또는 열이 5개의 셀로 구성되는 경우, 초기 값은 10010로 설정될 수 있다.

상술한 예에서, 이차원 전개는 일차원 전개를 이용할 수 있다. 또한, 본 발명의 다양한 실시 예들은, 이차원 전개 이상의 고차 전개에도 적용될 수 있음은 물론이다.

프로세서(430)는 2차원 이미지에 포함되는 하나의 셀의 값과, 하나의 셀에 이웃하는 두 개의 셀들의 값의 합에 기초하여, 하나의 셀에 이웃하는 다른 셀의 값을 결정하여 패턴을 생성할 수 있다.

프로세서(430)는 생성된 패턴을 투사하도록 프로젝터(410)를 제어할 수 있다. 또한, 프로세서(430)는 패턴이 반사된 이미지를 촬영하도록 촬영부(420)를 제어할 수 있다. 여기서, 프로세서(430)는 패턴 및 패턴이 반사된 이미지에 기초하여 3차원 환경 모델링을 위한 깊이(depth) 정보를 산출할 수 있다.

프로세서(430)는 패턴이 반사된 이미지에 포함되는 복수의 셀들의 행 또는 열의 셀 값에 기초하여 패턴을 생성할 수 있다. 또한, 프로세서(430)는 행 또는 열에 포함되는 하나의 셀의 값과, 하나의 셀의 이웃하는 두 개의 셀들의 값들에 기초하여, 하나의 셀에 이웃하는 다른 셀의 값을 결정할 수 있다. 또한, 프로세서(430)는 패턴이 반사된 이미지에 포함되는 복수의 셀들의 값과, 행 또는 열의 셀 값에 기초하여 생성된 패턴에 포함되는 복수의 셀들의 값을 비교하고, 그 비교 결과에 기초하여 깊이 정보를 산출할 수 있다.

깊이 정보는, 패턴에 포함되는 복수의 셀의 값과 및 패턴이 반사된 이미지에 포함되는 복수의 셀의 값의 일치 여부에 기초하여 산출될 수 있다.

프로세서(430)는 패턴이 반사된 이미지 중에서 손실된 영역을 판단할 수 있다. 이 경우, 프로세서(430)는 자동화 전개를 이용하여 손실된 영역에 대하여 패턴을 형성할 수 있다.

프로세서(430)는 패턴이 반사된 이미지에 포함된 하나의 행/열에 기초하여 생성된 제1 행/열과, 하나의 행/열과 인접한 제2 행/열 간의 매칭 여부에 기초하여, 자동화 전개를 진행할지 여부를 결정할 수 있다. 여기서, 매칭 여부는 제1 행/열과 제2 행/열 간의 해밍 거리(hamming distance)에 기초하여 결정될 수 있다.

이하에서는, 본원 발명과 관련되는 이론, 수학식과 구체적인 실시 예를 상세히 설명한다. 이하의 설명에서 명확히 적시하지 않더라도, 각 이론과 수학식, 구체적 실시 예 등은 프로세서에 의해 수행될 수 있음은 자명할 것이다.

먼저, 상술한 패턴은 유전적 패턴(genetic pattern)으로 명명될 수 있다. 이러한 유전적 패턴은 세포 자동화(cellular automata, 또는 세포 자동화 전개)에 의해 수행될 수 있다.

세포 자동화

본 발명의 일 실시 예에 따른 구조 광 패턴 생성을 위한 신규한 방법이 개시된다. 패턴을 생성하는 프로세스는 적외선 카메라 이미지와 동일한 해상도를 가지는 이차원 격자 상에서의 세포 자동화의 전개이다. 세포 자동화는 이미지 패턴을 구성하는 초기 셀(또는 점)의 초기 값 또는 초기 행 또는 열을 구성하는 셀의 초기 값에 기초하여 주변 셀들의 값을 결정하는 과정으로 정의될 수 있다. 여기서, 초기 값은 기설정되거나 외부로부터 입력받을 수 있다.

이러한, 세포 자동화 패턴 전개에 따른 결과는 국지적이고 전역적인 상관을 통한 일정한 이차원 패턴일 수 있으며, 패턴 전개에 따라 서브 픽셀 디스패리티 맵 재구성이 가능할 수 있다. 세포 자동화는 많은 단순한 구성요소들이 함께 작용하여 복잡한 동향 패턴들을 생성하는 시스템들의 수학적 모델들이다. 일차원 세포 자동화는 여러 방식이 있다.

본 발명의 일 실시 예에 따르면, 일차원 및 이차원 세포 자동화는 일반성을 제한하지 않고 더 높은 차원의 자동화를 사용할 수 있다. 여기서, 일차원 세포 자동화를 이차원 자동화로 확장하는 것이 더 높은 차원의 패턴 형성을 위해 개시된 본 발명의 원리들을 확장하는 데 있어 중요하다.

세포 자동화는 일반적인 사이트(또는, 셀)들의 격자로 구성된다. 각각의 사이트는 k 개의 가능한 값들(종들)을 가지며, 둘러싼 어떤 이웃의 사이트들의 값에 좌우되는 규칙에 따라 이산적인 시간 스텝들로 업데이트 된다. 일차원 세포 자동화 A1의 i 위치에서의 각 사이트의 값

(상기 수학식 1)은 가장 가까운 이웃들에만 좌우되고 그에 따라 다음 식에 따라 전개되는 규칙을 통해 결정된다:

2차원 세포 자동화를 위한 여러 개의 가능한 격자들 및 이웃 구조들이 존재한다. 다섯개의 이웃 셀의 세포 자동화가 상기 수학식 2에 따른 일차원 자동화를 통해 유사하게 전개된다.

또한, 총괄적 규칙들의 특별한 종류는 사이트의 값이 이웃 내 값들의 합에만 의존할 수 있다.

사이트의 값이 이웃들 및 자체 값의 합에 각각 의존하는 총괄 규칙들.

도 5a 및 5b는 본 발명의 다양한 실시 예에 따른 이차원 세포 자동화를 위해 고려되는 이웃 구조들을 도시한다.

도 5a 및 5b를 참조하면, 세포 자동화 전개 시, 중심 셀(41, 42)의 값은 그림자 셀들의 값들에 따라 좌우되는 규칙에 따라 업데이트된다. 도 5a와 같은 경우의 세포 자동화를 "다섯 이웃 스퀘어"이라 부르고, 도 5b와 같은 경우의 세포 자동화를 "아홉 이웃 스퀘어"라고 부른다. (이러한 이웃들은 종종 폰 뉴만 및 무어 이웃들이라고 각기 칭해진다.) 총괄적 세포 자동화 규칙들은 이웃 내 사이트들의 값들의 합에만 의존하는 중심 사이트의 값을 취한다. 외부 총괄 규칙들에서, 사이트들은 그들의 이전 값들 및 이웃 내 다른 사이트들의 값들의 합에 따라 업데이트된다. 일 예에 따르면, 삼각 및 육각형의 격자들 역시 가능하지만, 여기 주어진 예에서는 사용되지 않는다. 여기서, 다섯 이웃 스퀘어, 삼각, 및 육각 세포 자동화 규칙들은 모두, 일반적인 이웃 스퀘어 규칙들의 특별한 경우들이라고 간주될 수 있다.

도 6은 본 발명의 일 실시 예에 다른 세포 자동화 패턴 생성 방법의 흐름도이다.

먼저, 프로세서(430)는 세포 자동화 패턴을 구성하는 셀의 크기를 결정한다(S610). 일 예로, 세포 자동화 패턴을 구성하는 셀의 크기는 픽셀 단위로 결정될 수 있다. 예를 들어, 세포 자동화 패턴을 구성하는 셀의 크기는 1x1, 2x2, 3x3 (pixel x pixel)로 결정될 수 있다.

다음으로, 프로세서(430)는 세포 자동화 패턴 생성을 위한 규칙을 결정한다(S620). 상기 규칙은 이하 도 8에서 상세히 설명한다.

프로세서(430)는 초기 값을 설정하기 위한 행 또는 열을 선택한다(S630). 예를 들어, 프로세서(430)는 3x3 픽셀 크기의 셀로 구성된 2차원 이미지의 가장 왼 쪽 열을 상기 초기 값을 설정하기 위한 열로 설정할 수 있다. 여기서, 초기 값을 설정하기 위한 열은 상기 2차원 이미지를 구성하는 행 또는 열 중 임의의 적어도 하나로 결정될 수 있다.

프로세서(430)는 초기 값을 세팅할 수 있다(S640). 예를 들어, 상기 초기 값을 설정하기 위해 선택된 열이 10개의 셀로 구성되었다고 가정하면, 상기 초기 값은 0110011100로 결정될 수 있다. 여기서, 상기 결정된 초기 값의 각 자리 수는 각 셀에 대응된다.

프로세서(430)는 결정된 초기 값과 결정된 패턴 생성을 위한 규칙에 기초하여 결정된 초기 행 또는 열의 다음 행 또는 열의 셀 값을 결정한다(S650). 여기서, 초기 행 또는 열의 다음 행 또는 열은 초기 행 또는 열에 가장 인접한 행 또는 열일 수 있다.

상술한 과정(S610 내지 S650)은 2차원 이미지를 구성하는 모든 셀에 값을 설정할 때까지 반복될 수 있다.

상술한 과정(S610 내지 S650)은 순차적으로 수행될 수 있으나, 상술한 과정(S610 내지 S650)은 필수적으로 모두 수행되어야 하는 것은 아니다. 예를 들어, 초기 값이 설정된 경우, 초기 값을 설정하는 과정(S640)을 생략한 나머지 과정들만을 수행할 수 있다. 이하에서, 도 7 내지 17을 참조하여 세포 자동화 패턴을 생성하는 실시 예를 상세히 설명한다.

도 7은 본 발명의 일 실시 예에 따른 2차원 이미지를 도시한다.

프로세서(430)는 세포 자동화 패턴의 셀 크기를 결정할 수 있다.

도 7을 참조하면, 2차원 이미지(701)는 IMAGE_WIDTH의 폭과 IMAGE_HEIGHT의 높이로 설정된다. 또한, 2차원 이미지(701)는 복수의 셀을 포함한다. 일 예로, 이차원 이미지(701)는 동일한 크기를 가지는 셀들로 구성될 수 있다. 이 경우, 이차원 이미지(701)를 구성하는 하나의 셀(701-1)은 CELL_SIZE 값의 폭과 높이로 설정될 수 있다. 상술한 바와 같이 이차원 이미지(701)를 구성하는 하나의 셀(701-1)의 크기는 픽셀 단위로 설정될 수 있음은 물론이다.

프로세서(430)는 세포 자동화 패턴 생성을 위한 규칙을 설정할 수 있다. 세포 자동화 패턴 생성을 위한 규칙은 임의의 세 개의 연속하는 셀의 값(또는 상태, state)에 기초하여 상기 임의의 세 개의 연속하는 셀의 중심에 위치하는 셀에 인접하는 다른 셀의 값을 결정하는 방식일 수 있다. 여기서, 세 개의 연속하는 셀은 하나의 행 또는 열에 포함되어 연속되는 셀이다.

도 8은 본 발명의 일 실시 예에 다른 세포 자동화 패턴 생성을 위한 규칙을 도시한다.

본원의 실시예에 대한 설명을 용이하게 하기 위하여, 패턴 생성을 위한 규칙을 Rule #25로 명명한다. 세포 자동화 패턴 생성을 위한 규칙은 다른 이름으로 명명될 수 있음은 물론이다. 또한, 세포 자동화 패턴 생성을 위한 규칙은 다양할 수 있으며, 이하에서 설명되는 규칙으로 제한되지 않음은 물론이다.

도 8의 표 801을 참조하면, s0 및 s1은 2차원 이미지(701)에서 선택된 임의의 연속된 세 개의 셀의 중심에 위치하는 셀의 값이다. k0, k1, k2는 상기 중심에 위치하는 셀의 양 옆의 두 개의 셀의 값의 합이다. s0 및 s1와 k0, k1, k2에 따른 결과 값(801-1)은 상기 중심에 위치하는 셀에 인접한 셀의 값이다.

상기 s0 및 s1을 일반화하여 아래의 수학식 4의 s로 정의할 수 있다.

　

또한, 상기 정의된 s 값을 가지는 셀에 인접하는 두 개의 셀의 값들의 합을 아래의 수학식 5와 같이 k로 정의한다. 여기서, 상기 정의된 s 값을 가지는 셀과, 이에 인접하는 두 개의 셀은 하나의 행 또는 열에서 연속될 수 있다. 다른 예로, 상기 정의된 s 값을 가지는 셀과 기설정된 개수의 셀 만큼 떨어진 위치의 두 개의 셀의 값들의 합을 k로 정의할 수도 있다.

상기 결정된 s 및 k 값을 Rule # 25(801-1)에 대입한 결과는 아래의 수학식 6에 따라 산출될 수 있다.

예를 들어, 도 9를 참조하면, 프로세서(430)는 2차원 이미지(701)의 임의의 열에서 임의의 연속된 세 개의 셀 Cell(i-1), Cell(i) 및 Cell(i+1)을 선택할 수 있다. 여기서, 도 10을 참조하면, 임의의 연속된 세 개의 셀 Cell(i-1), Cell(i) 및 Cell(i+1) 각각은 참조번호 10-2, 10-1, 10-3에 대응되며, 임의의 연속된 세 개의 셀 Cell(i-1), Cell(i) 및 Cell(i+1)의 값은 각각 1, 0 및 0으로 설정될 수 있다. 이 경우, s 값은 0, k 값은 1과 0의 합인 1로 계산되고, 그 결과를 Rule # 25(801-1)에 대입하면 그 결과인

는 아래의 수학식 7과 같이 0이다.

여기서, 상기 결과 값 0은 셀(10-4)의 값으로 설정된다.

일 실시 예에 따르면, Rule # 25(801-1)는 아래의 수학식 8로 정의될 수 있다.

이하, 도 11 내지 18을 참조하여, 세포 자동생성에 기초한 패턴 생성 방법을 상세히 설명한다.

도 11은 본 발명의 일 실시 예에 따른 최초값 설정 방법을 설명하기 위한 도면이다.

본 발명의 일 실시 예에 따라, 2차원 평면은 가로 세로 9개 씩(9x9)의 셀로 구성된다고 가정한다. 여기서, 9x9는 오브젝트에 반사된 패턴을 감지하는 디텍터(detector)의 크기에 따라 결정될 수 있다.

도 11을 참조하면, 프로세서(430)는 2차원 평면을 구성하는 셀의 열 중 하나를 선택한다(111). 프로세서(430)는 선택된 셀의 열을 구성하는 각 셀에 초기 값으로 110101111을 설정할 수 있다(112). 도 12는 본 발명의 일 실시 예에 따른 초기값이 설정된 결과를 도시한다.

도 13 내지 17은 본 발명의 일 실시 예에 따른 세포 자동화의 세부 과정을 도시한다.

도 13은 본 발명의 일 실시 예에 따라, 2차원 이미지에서 선택된 열의 가장 상단의 셀(Rule #25의 s)(132)의 인덱스 i를 0으로 설정한 경우이다. 다시 말해, 프로세서(430)는 셀(132)과 셀(132)에 인접한 셀(131, 133)을 Rule #25를 적용하기 위한 초기 대상으로 결정하였다.

여기서, 연속된 3개의 셀(131-133)의 중간의 위치에 있는 셀(132)의 값(또는 상태)은 1이다. 또한, 셀(132)의 인접 셀(131, 133) 값의 합 k는 2이다. s 및 k를 Rule #25에 적용하면 업데이트되는 값(또는 state)은 0(135)이다.

도 14는 도 13의 다음 과정으로, 인덱스 i가 1인 경우를 도시한다. 본 발명의 일 실시 예에 따르면, 연속된 3개의 셀(141-143)의 중간의 위치에 있는 셀(142)의 값은 1이다. 또한, 셀(142)의 인접 셀(141, 143) 값의 합 k는 1이다. s 및 k를 Rule #25에 적용하면 업데이트되는 값은 1(145)이다.

도 15는 도 14의 다음 과정으로, 인덱스 i가 2인 경우를 도시한다. 본 발명의 일 실시 예에 따르면, 연속된 3개의 셀(151-153)의 중간의 위치에 있는 셀(152)의 값은 0이다. 또한, 셀(152)의 인접 셀(151, 153) 값의 합 k는 2이다. s 및 k를 Rule #25에 적용하면 업데이트되는 값은 1(154)이다.

도 16의 (a)는 본 발명의 일 실시 예에 따른, 초기 값이 설정된 열(161)에 기초하여 업데이트된 열(162)를 도시한다. 업데이트된 열(162)의 연속된 셀들은 값 011011000을 가진다. 또한, 프로세서(430)는 업데이트된 열(162)의 연속된 셀(162-1 내지 162-3)의 업데이트된 값에 기초하여 열(163)의 셀(163-1)의 값을 0으로 업데이트할 수 있다.

도 16의 (b)는 연속된 3개의 셀(162-4 내지 162-6)에 기초하여 셀(163-2)의 값을 업데이트 한 결과를, 도 16의 (c)는 연속된 3개의 셀(162-7 내지 162-9)에 기초하여 셀(163-3)의 값을 업데이트 한 결과를, 도 16의 (d)는 연속된 3개의 셀(162-10 내지 162-12)에 기초하여 셀(163-3)의 값을 업데이트 한 결과를 도시한다.

도 17은 도 13 내지 16d에 기초하여 상술한 실시 예에 따른 결과를 도시한다. 도 17을 참조하면, 2차원 이미지(191)에 포함된 모든 셀들의 값이 업데이트 되었음을 확인할 수 있다.

2차원 이미지(101)는 본 발명의 일 실시 예에 따른 세포 자동화를 실행하여 획득된 패턴이다. 세포 자동화를 이용하는 경우, 일정한 규칙에 의해 자가 패턴을 형성할 수 있기 때문에 메모리 자원과 통신 자원의 낭비를 막을 수 있다.

도 18은 본 발명의 일 실시 예에 따른 전자장 필터에 대한 피치 크기와 세포 자동생성을 위한 셀 크기를 결정 방법을 설명하기 위한 도면이다.

2차원 이미지의 크기를 나타내는 IMAGE_HEIGHT 및 IMAGE_WIDTH 파라미터가 기설정되어 있다고 가정한다.

시야각 파라미터 FOVc를 이용하는 디텍터의 렌즈 시스템의 각 해상도(ARESc)(182)는 아래의 수학식 9에 기초하여 결정된다.

또한, 시야각 파라미터 FOVp를 이용하는 필터의 각 해상도(ARESp)는 아래의 수학식 10에 기초하여 결정된다.

ARESc와 ARESp가 등가인 경우, 상기 수학식 9 및 수학식 10에 따라 전자장 필터를 위한 피치 크기(181)는 아래의 수학식 11에 기초하여 결정된다.

또한, 세포 자동화의 셀의 크기는 아래의 수학식 12에 기초하여 결정된다.

또한, 프로세서(430)는 필터 어레이의 피쳐(feature) (I, J)의 중심이

와 같도록, 필터 피치 크기에 따라 세포 자동화 셀의 위치를 매핑할 수 있다.

또한, 프로세서(430)는 직사각형 형태의 모서리에서 회절 이미지의 크기 수정에 따라 패턴의 형태를 디자인할 수 있다(183). 이 경우, 상기 모서리는 radius는

로 설정될 수 있다.

도 19는 본 발명의 일 실시 예에 따른 2차원 이미지를 도시한다.

도 19를 참조하면, 2차원 이미지(191)는 픽셀 구성이 고려된 이미지이다. 일 예로, 도 17의 좌측 상단의 첫 번째 셀(값은 1)은 4개의 픽셀(4x4)로 구성될 수 있다. 도 17의 좌측 상단의 첫 번째 셀의 값 1을 나타내기 위해, 2차원 이미지(191)의 각 픽셀(191-1 내지 191-2)은 모두 값 1을 가질 수 있다.

도 20은 본 발명의 다른 실시 예에 따른 2차원 이미지를 도시한다.

도 20을 참조하면, 2차원 이미지(201)는 좌 우 각각 18 픽셀들로 구성된다. 2차원 이미지(201)에 포함되는 4 개의 픽셀들은 하나의 셀을 표현하도록 구성될 수 있다. 예를 들어, 2차원 이미지(201)에 포함되는 4개의 픽셀들(201-1)은 도 17의 좌측 상단의 첫 번째 셀의 값 1을 표현할 수 있다. 다른 예로, 2차원 이미지(201)에 포함되는 4개의 다른 픽셀들(201-2)은 도 17의 좌측 상단의 셀로부터 좌측으로 두 번재 위치에 있는 셀의 값 0을 표현할 수 있다.

도 21은 본 발명의 일 실시 예에 따른 세포 자동화 패턴의 프로젝션 및 캡쳐 과정을 도시한다.

도 21은 전 영역의 깊이 디스패리티(disparity)가 0인 평면에 세포 자동화로 생성된 패턴(이하 세포 자동화 패턴)(211)을 프로젝션하는 경우의 예이다. 여기서, 깊이 디스패리티는 세포 자동화 패턴을 프로젝션하는 조광부와 평면까지의 거리로 정의될 수 있다.

도 21을 참조하면, 세포 자동화 패턴(211)은 세포 자동화로 생성된 패턴을 포함한다. 여기서, 세포 자동화 패턴(211)은 조광부에서 프로젝션된 광이 필터 또는 마스크를 통과하여 생성될 수 있다.

일 예로, 프로세서(430)는 조광부와 필터 또는 마스크를 이용하여 세포 자동화 패턴(211)은 전 영역의 깊이 디스패리티(disparity)가 0인 평면에 프로젝션 할 수 있다.

이 경우, 반사되는 세포 자동화 패턴(212)은 전 영역에서 깊이 디스패리티가 0을 갖기 때문에, 세포 자동화 패턴(211)와 동일한 패턴일 수 있다.

도 22는 본 발명의 다른 실시 예에 따른 세포 자동화 패턴의 프로젝션 및 캡쳐 과정을 도시한다.

도 22는 깊이 디스패리티가 0이 아닌 3차원 공간에 세포 자동화 패턴을 프로젝션하는 경우이다.

세포 자동화 패턴(221)을 프로젝션하는 조광부와, 세포 자동화 패턴(221)이 공간에 반사된 패턴을 촬영하는 카메라(또는 디텍터, 광 수용부)는 일정한 간격으로 이격될 수 있다. 예를 들어, 조광부와 카메라는 단말의 일 면에 일정한 간격을 두고 구비될 수 있다. 이에 따라, 세포 자동화 패턴(221)이 조광부에서 3차원 공간에 있는 오브젝트에 프로젝션되는 각도와 반사되어 카메라에 수용되는 각도는 상이하다. 이에 따라, 오브젝트에 반사된 세포 자동화 패턴(221)은 일정한 방향으로 쉬프트될 수 있다.

예로, 프로세서(430)는 세포 자동화 패턴(221)을 3차원 공간에 프로젝션 할 수 있다. 여기서, 세포 자동화 패턴(221)이 오브젝트에 반사되어 촬영된 패턴(222)은 일정방향으로(도 22는 parallax shift) 쉬프트 될 수 있다. 여기서, 세포 자동화 패턴(221)이 쉬프트된 영역(222-1)의 크기는 카메라와 오브젝트 간의 깊이 정보이다.

도 23은 본 발명의 일 실시 예에 따른 세포 자동화 패턴의 디코딩 방법의 흐름도이다.

먼저, 프로세서(430)는 프로젝션되어 반사되는 세포 자동화 패턴을 캡쳐한다(S2310). 또한, 프로세서(430)는 캡쳐된 세포 자동화 패턴을 클러스터링하여, 캡쳐된 세포 자동화 패턴을 구성하는 셀의 값을 결정한 다음, 세포 자동화 패턴을 인식한다(S2320, S2330). 예를 들어, 세포 자동화 패턴을 구성하는 셀의 값은 0 또는 1로 결정될 수 있다. 다른 예로, 세포 자동화 패턴을 구성하는 셀의 값은 0 이상의 정수 중에서 선택될 수 있다. 프로세서(430)는 클러스터링된 패턴의 수평 수직 연결 요소를 검색한다(S2340). 프로세서(430)는 수평 수직 연결 요소에 기초하여 깊이 디스패리티를 추정한다(S2350). 프로세서(430)는 추정된 깊이 디스패리티에 기초하여 오브젝트 세그먼테이션(segmentation)을 수행한다. 프로세서(430)는 3차원 맵을 생성한다(S2370).

도 24a 및 24b는 본 발명의 일 실시 예에 따른 클러스터링 방법을 도시한다.

도 24a의 좌측 패턴은 캡쳐된 세포 자동화 패턴의 일 예를 도시한다. 캡쳐된 세포 자동화 패턴은 픽셀의 값(0-255 또는 그 이상의 값)을 가진다.

프로세서(430)는 기설정된 크기의 클러스터 윈도우(CLUSTER_WINDOW)에 기초하여 클러스터링을 수행할 수 있다. 도 24a의 좌측 패턴을 참조하면, 프로세서(430)는 4x4로 설정된 클러스터 윈도우(2*CELL_SIZE*2*CELL_SIZE)에 기초하여 클러스터링을 수행한다.

도 24b를 참조하면, 프로세서(4300)는 클러스터 윈도우 내의 각 픽셀 값들을 클러스터링 알고리즘(예를 들어, K-means algorithm)을 이용하여 0 또는 1의 값으로 클러스터링할 수 있다.

도 24a의 우측 패턴은 클러스터링의 결과를 도시한다. 여기서, 클러스터 윈도우 내의 값들 중 일부(242)는 프로젝션된 세포 자동화 패턴의 값과 다른 값을 가질 수도 있다. 이러한 오류는 픽셀 블랜딩, 데이터 손실 등에서 유발될 수 있다.

도 25a 내지 25e는 본 발명의 일 실시 예에 따른 클러스터링의 결과를 도시한다.

도 25a는 셀 하나당 2x2 픽셀에 매핑된 세포 자동화 패턴이 캡쳐되어 클러스터된 결과이다. 일 예로, 4개의 픽셀 값들(252-254)은 1개의 셀에 매핑될 수 있다.

도 25b는 각 셀에 매핑되는 4개의 픽셀들 중 위 왼쪽에 위치한 픽셀들의 값만을 분류하여 도시하고, 도 25c는 각 셀에 매핑되는 4개의 픽셀들 중 위 오른쪽에 위치한 픽셀들의 값만을 도시하고, 도 25d는 각 셀에 매핑되는 4개의 픽셀들 중 아래 왼쪽에 위치한 픽셀들의 값만을 도시하고, 도 25e는 각 셀에 매핑되는 4개의 픽셀들 중 아래 오른쪽에 위치한 픽셀들의 값만을 도시한다.

도 26a 내지 26f는 본 발명의 일 실시 예에 따른 세포 자동화 패턴 인식 방법을 도시한다.

일 실시예에 따르면, 세포 자동화 패턴 인식 방법은 상술한 세포 자동화 패턴 생성 방식을 이용한다.

도 26a는 클러스터된 세포 자동화 패턴(261)을 도시한다. 클러스터된 세포 자동화 패턴(261)은 오브젝트에 의한 쉬프팅으로 셰도우(shadow) 영역을 포함할 수 있다(263).

프로세서(430)는 클러스터된 세포 자동화 패턴(261)과 초기 값에 기초하여 세포 자동화로 생성된 패턴을 비교하여 클러스터된 세포 자동화 패턴(261)을 인식할 수 있다.

일 예로, 프로세서(430)는 세포 자동화 패턴(261)의 첫 번째 열(261-1)에 클러스터된 값 110101111을 초기값으로 하여 세포 자동화를 진행할 수 있다. 여기서, 세포 자동화는 상술한 세포 자동화 패턴 생성의 예와 동일하다. 프로세서(430)는 자동화 패턴(261)의 첫 번째 열(261-1)의 값 1(261-2), 1(261-3), 1(261-4)을 Rule #25에 적용하여 값 0을 얻을 수 있다. 프로세서(430)는 얻어진 값 0(261-5)(메모리의 temporary array에 저장될 수 있음)과 클러스터된 값 0(262-6)을 비교할 수 있다.

다음으로, 도 26b에서, 프로세서(430)는 세포 자동화 패턴(261)의 첫 번째 열(261-1)의 값 1, 1, 0(하이라이트 처리된 영역)을 Rule #25에 적용하여 값 1(261-10)을 얻을 수 있다. 프로세서(430)는 얻어진 값 1(261-10)과 클러스터된 값 0(262-11)을 비교할 수 있다.

도 26c는 세포 자동화 패턴(261)의 첫 번째 열(261-1)의 값에 대해 상술한 과정을 반복하여 얻어진 결과 값(261-12) 도시한다.

도 26d는 결과 값(261-12)과 클러스터된 세포 자동화 패턴(261)의 두 번?? 열(261-13)을 비교하는 방법을 도시한다. 예를 들어, 프로세서(430)는 결과 값(261-12) 중 첫 번째 값 0과 두 번째 열(261-13)의 첫 번째 값 0이 같으므로 현재 열(261-14) 첫 번째 셀의 값을 0으로 설정한다.

다음으로, 도 26e와 같이, 프로세서(430)는 결과 값(261-12) 중 두 번째 값 1과 두 번째 열(261-13)의 두 번째 값이 같으므로 현재 열(261-14)의 두 번째 셀의 값을 0으로 설정한다.

도 26f는 도 26a 내지 26e에서 설명한 과정을 세포 자동화 패턴(261)의 8번째 열(261-15)까지 적용한 결과를 도시한다.

도 27은 본 발명의 일 실시 예에 따른 세포 자동화 패턴의 인덱스를 도시한다. 구체적으로, 도 27은 세포 자동화 패턴의 셀 인덱스에 대한 수직 분리 셋(271)과 수평 분리 셋(272)을 도시한다.

도 28은 본 발명의 일 실시 예에 따른 세포 자동화 패턴의 인덱스를 처리하는 방법을 도시한다. 구체적으로, 도 28은 본 발명의 일 실시 예에 따른 세포 자동화 패턴(273)의 첫 번째 열의 인덱스를 메모리 스택(stack)(274)에 순서대로 삽입하는 과정을 도시한다.

도 29a 내지 29h는 본 발명의 일 실시 예에 따른 수평 수직 연결 요소 검색 방법을 도시한다.

먼저, 도 29a를 참조하면, 프로세서(430)는 셀(271-1)의 순서 8을 스택(274)으로부터 얻는다. 또한, 프로세서(430)는 아래의 수학식 13에 기초하여, 셀(271-1)의 인덱스 i 값 72(8x9)를 얻을 수 있다.

프로세서(430)는 수직 분리 셋(271) 및 수평 분리 셋(272)로부터 인덱스 72를 가지는 셀(271-1, 271-2)을 검색한다. 또한, 프로세서(430)는 수직 분리 셋(271) 및 수평 분리 셋(272)에 대한 부모 인덱스(parent index)를 72로 정의한다. 프로세서(430)는 수직 분리 셋(271)의 인덱스 72의 셀부터 부모 인덱스 72의 셀까지 병합한다. 또한, 프로세서(430)는 수평 분리 셋(272)의 인덱스 72의 셀부터 인덱스 73(72+1)의 셀까지 병합한다.

프로세서(430)는 도 29a에서 했던 동작을 다음 셀에 대하여 반복할 수 있다. 도 29b를 참조하면, 프로세서(430)는 셀(271-1)의 순서 7을 스택(274)으로부터 얻는다. 또한, 프로세서(430)는 수학식 13에 기초하여, 셀(271-1)의 인덱스 i 값 63(7x9)를 얻을 수 있다. 프로세서(430)는 수직 분리 셋(271) 및 수평 분리 셋(272)로부터 인덱스 63를 가지는 셀(271-3, 271-4)을 검색한다. 또한, 프로세서(430)는 수직 분리 셋(271) 및 수평 분리 셋(272)에 대한 부모 인덱스(parent index)를 72로 정의한다. 프로세서(430)는 수직 분리 셋(271)의 인덱스 63의 셀부터 부모 인덱스 72의 셀까지 병합한다. 또한, 프로세서(430)는 수평 분리 셋(272)의 부모 인덱스 63의 셀부터 인덱스 64(63+1)의 셀까지 병합한다. 수직 분리 셋(271) 및 수평 분리 셋(272)의 첫 번째 열에 대한 상술한 과정을 완료한 결과는 도 29c에 도시된 바와 같다.

도 29d는 두 번째 열(Ci=1)의 첫 번째 셀부터 세 번째 셀까지의 수평수직 연결요소 검색 방법을 도하며, 도 29e는 두 번째 열(Ci=1)의 첫 번째 셀부터 세 번째 셀까지의 수평수직 연결 요소 검색의 결과를 도시한다.

도 29f는 세포 자동화 패턴(273)의 8번째 열(Ci=7)에 대한 수평수직 연결요소 검색 방법을 수행한 결과를 도시한다.

도 29g는 본 발명의 일 실시 예에 따른 수직 분리 셋(271) 및 수평 분리 셋(272)의 경계를 도시한다.

도 29h는 본 발명의 일 실시 예에 따른 세포 자동화 패턴(273)의 경계를 도시한다.

도 30a 내지 30h는 본 발명의 일 실시 예에 따른 수직 클러스터에 대한 디스패리티 추정 방법을 도시한다.

프로세서(430)는 프로젝션된 세포 자동화 패턴(이하, 오리지널 패턴)과 프로젝션된 세포 자동화 패턴이 반사되어 캡쳐된 세포 자동화 패턴(이하, 캡쳐된 패턴)의 디스패리티를 추정할 수 있다. 이하에서 설명되는 디스패리티 추정은 상술한 도 29h에서 설명한 세포 자동화 패턴의 경계에 위치한 셀을 제외한 나머지 모든 인식된 셀에 대하여 수행될 수 있다.

도 30a는 오리지널 패턴(301)과 쉬프트 되지 않은 캡쳐된 패턴(302)을 도시한다. 30a를 참조하면, 프로세서(430)는 오리지널 패턴(301)과 캡쳐된 패턴(302)의 모든 셀들의 차이를 계산할 수 있다. 일 예로, 프로세서(430)는 오리지널 패턴(301)의 첫 번째 셀(301-1)의 값 1과 캡쳐된 패턴(302)의 첫 번째 셀(302-1)의 값 1의 차이 값 0(303-1)을 기록(또는 저장)할 수 있다.

도 30b를 참조하면, 프로세서(430)는 상기 차이 값이 계산된 결과(303)에 기초하여 연결된 셀들의 클러스터(304)의 차이 값을 결정할 수 있다. 일 예로, 프로세서(430)는 상기 차이 값이 계산된 결과(303)의 첫 번째 열(303-1)이 연결되어 있는 경우, 상기 첫 번째 열의 셀의 값을 모두 합한 값을 클러스터(304)의 첫 번째 열(304-1)을 구성하는 셀들의 차이 값으로 설정할 수 있다. 이에 따라, 클러스터(304)의 첫 번째 열(304-1)을 구성하는 셀들의 차이 값은 0으로 설정될 수 있다.

도 30c를 참조하면, 프로세서(430)는 상기 차이 값이 계산된 결과(303)의 두 번째 열(303-2)에 대하여, 경계 셀들을 제외한 나머지 셀들의 값을 더하여 오리지널 패턴(301)과 캡쳐된 패턴(302) 간의 클러스터 차이 값을 결정할 수 있다.

도 30d를 참조하면, 프로세서(430)는 상기 차이 값이 계산된 결과(303)의 세 번째 열(303-3)에 대하여, 경계 셀들을 제외한 나머지 셀들의 값을 더하여 오리지널 패턴(301)과 캡쳐된 패턴(302) 간의 클러스터 차이 값을 결정할 수 있다.

도 30e를 참조하면, 프로세서(430)는 상기 차이 값이 계산된 결과(303)의 여섯 번째 열(303-4)에 대하여, 경계 셀들을 제외한 나머지 셀들의 값을 더하여 오리지널 패턴(301)과 캡쳐된 패턴(302) 간의 클러스터 차이 값을 결정할 수 있다.

도 30f를 참조하면, 프로세서(430)는 상기 차이 값이 계산된 결과(303)의 일곱 번째 열(303-5)에 대하여, 경계 셀들을 제외한 나머지 셀들의 값을 더하여 오리지널 패턴(301)과 캡쳐된 패턴(302) 간의 클러스터 차이 값을 결정할 수 있다.

도 30g를 참조하면, 프로세서(430)는 상기 차이 값이 계산된 결과(303)의 여덟 번째 열(303-6)에 대하여, 경계 셀들을 제외한 나머지 셀들의 값을 더하여 오리지널 패턴(301)과 캡쳐된 패턴(302) 간의 클러스터 차이 값을 결정할 수 있다.

도 30h는 오리지널 패턴(301)과 캡쳐된 패턴(302) 간의 클러스터 차이 값의 결과를 보여준다. 여기서, 연결된 셀들은 동일한 차이 값을 가진다.

도 31a 내지 31d는 본 발명의 일 실시 예에 따른 수평 클러스터에 대한 디스패리티 추정 방법을 도시한다.

도 31a는 오리지널 패턴(301)과 쉬프트 되지 않은 캡쳐된 패턴(302)을 도시한다.

도 31a를 참조하면, 프로세서(430)는 상기 차이 값이 계산된 결과(305)에 기초하여 연결된 셀들의 클러스터(306)의 차이 값을 결정할 수 있다. 일 예로, 프로세서(430)는 상기 차이 값이 계산된 결과(305)의 첫 번째 행(305-1)이 연결되어 있는 경우, 상기 첫 번째 행의 셀의 값을 모두 합한 값을 클러스터(306)의 첫 번째 행(305-1)을 구성하는 셀들에 대한 차이 값으로 설정할 수 있다. 이에 따라, 클러스터(304)의 첫 번째 행(305-1)을 구성하는 셀들의 차이 값은 0으로 설정될 수 있다.

도 31b를 참조하면, 프로세서(430)는 상기 차이 값이 계산된 결과(305)의 첫 번째, 세 번째, 다섯 번째, 일곱 번째, 아홉 번째 행에 대하여, 경계 셀들을 제외한 나머지 셀들의 값을 더하여 오리지널 패턴(301)과 캡쳐된 패턴(302) 간의 클러스터 차이 값을 결정할 수 있다.

도 31d는 오리지널 패턴(301)과 캡쳐된 패턴(302) 간의 클러스터 차이 값의 결과(307)를 보여준다. 여기서, 연결된 셀들은 동일한 차이 값을 가진다.

도 32a 및 32b는 본 발명의 일 실시 예에 따른 수직 클러스터 차이와 수평 클러스터 차이의 합을 결정하는 방법을 도시한다.

도 32a를 참조하면, 프로세서(430)는 수평 클러스터 차이 값의 결과(307)의 모든 행과 수직 클러스터 차이 값의 결과(304)의 모든 행들 간의 비교를 통해서 차이 값의 합을 결정할 수 있다. 여기서, 프로세서(430)는 연속된 셀들 중 경계 셀들에 대하여는 차이 값의 합 결정을 수행하지 않을 수 있다. 일 예로, 프로세서(430)는 수평 클러스터 차이 값의 결과(307)의 첫 번째 행과 수직 클러스터 차이 값의 결과(304)의 두 번째 열이 겹치는 셀(321-1)의 차이 값을 결정할 수 있다. 상기 겹치는 셀(321-1)의 값은 수평 클러스터 차이 값의 결과(307)의 첫 번째 행의 차이값 0과 수직 클러스터 차이 값의 결과(304)의 두 번째 열의 차이 값 0의 합일 수 있다.

도 32b를 참조하면, 프로세서(430)는 수평 클러스터 차이 값의 결과(307)의 여섯 번째 행의 차이값 2와 수직 클러스터 차이 값의 결과(304)의 여섯 번째 열의 차이값 2의 합인 4를, 수평 클러스터 차이 값의 결과(307)의 여섯 번째 행과 수직 클러스터 차이 값의 결과(304)의 여섯 번째 열이 겹치는 셀(321-1)의 차이 값으로 결정할 수 있다.

도 32c는 수평 클러스터 차이 값의 결과(307)의 모든 행과 수직 클러스터 차이 값의 결과(304)의 모든 열에 대해 상술한 차이 값의 합을 결정하는 과정을 수행한 결과 테이블(308)를 도시한다.

도 33a 및 33b는 본 발명의 일 실시 예에 따른 쉬프트 테이블 결정 방법을 도시한다

프로세서(430)는 도 32c의 결과 테이블(308)를 이용하여 쉬프트 테이블을 생성할 수 있다.

예를 들어, 도 33a를 참조하면, 프로세서(430)는 결과 테이블(308)의 모든 셀의 값과 값이 설정되지 않은(uncertainty) 초기 테이블(309)의 셀의 값을 비교하여 최소 차이값을 결정할 수 있다. 이 경우, 아래의 수학식 14가 이용될 수 있다.

여기서, 비교 대상이 되는 각 셀은 각 테이블의 동일 위치일 수 있다. 또한, 프로세서(430)는 특정 셀의 값이 설정되어 있지 않은 경우 해당 셀 값의 비교 결과를 0으로 결정할 수 있다.

일 예로, 프로세서(430)는 결과 테이블(308)의 셀(308-1)의 값과 초기 테이블(309)의 셀(309-1)의 값을 비교할 수 있다. 예를 들어, 초기 테이블(309)의 셀(309-1)의 값은 설정되지 않은 값이므로, 결과 테이블(308)의 셀(308-1)의 값 4와 테이블(309)의 셀(309-1)의 설정되지 않은 값에 대한 min (4,-)은 4로 결정될 수 있다. 한편, 프로세서(430)는 예를 들어, 도 29h에 도시된 경계 셀에 대하여는 셀의 값에 대한 비교 과정을 생략할 수 있다.

도 33b의 최소 셀 차이 값에 대한 테이블(310)은, 도 33a의 셀 값 비교 방식에 기초하여 결과 테이블(310)의 셀들의 값과 초기 테이블(311)의 셀들의 값들 중의 최소 값을 포함하고 있다. 여기서, 프로세서(430)는 최소 셀 차이 값에 대한 테이블(310)의 셀의 최소 차이 값이 변경된 경우 쉬프트 양을 업데이트할 수 있다. 일 예로, 프로세서(430)는 최소 셀 차이 값에 대한 테이블(310)의 셀(310-1)의 값 4가 변경되었다고 판단되는 경우, 현재 쉬프트 양에 대한 값 0(311-1)을 업데이트할 수 있다.

도 34a 내지 34g는 본 발명의 다른 실시 예에 따른 수직 클러스터에 대한 디스패리티 추정 방법을 도시한다.

이하에서, 도 30a 내지 30h에 대한 설명과 중복되는 부분에 대한 설명은 생략한다.

도 34a 내지 34g는 오리지널 패턴(341)과 1개의 캡쳐된 패턴이 1개의 셀 만큼 쉬프트된 패턴(342)을 도시한다.

도 34a를 참조하면, 프로세서(430)는 오리지널 패턴(341)의 첫 번째 열을 구성하는 셀들의 값과, 쉬프트된 패턴(342)의 두 번째 열을 구성하는 셀들의 값 간의 차이 값을 결정할 수 있다. 이 경우, 프로세서(430)는 오리지널 패턴(341)의 첫 번째 열을 구성하는 셀들과 쉬프트된 패턴(342)의 두 번째 열을 구성하는 셀들 중 동일한 행에 위치한 셀들 간의 차이 값을 결정할 수 있다. 또한, 프로세서(430)는 상기 결정된 차이 값을 테이블(343)의 첫 번째 줄(343-1)의 각 행에 기록할 수 있다.

도 34b와 같이, 프로세서(430)는 오리지널 패턴(341)의 두 번째 열을 구성하는 셀들의 값과 쉬프트된 패턴(342)의 세 번째 열을 구성하는 셀들의 값 간의 차이 값을 결정할 수 있다. 프로세서(430)는 그 결과를 테이블(343)의 두 번째 열(343-2)에 기록할 수 있다.

도 34c와 같이, 프로세서(430)는 오리지널 패턴(341)의 두 번째 여덟 번째 열을 구성하는 셀들의 값과 쉬프트된 패턴(342)의 아홉 번째 열을 구성하는 셀들의 값 간의 차이 값을 결정할 수 있다. 프로세서(430)는 그 결과를 테이블(343)의 여덟 번 째 열(343-3)에 기록할 수 있다.

도 34d의 테이블(345)는 도 34c의 테이블(343)의 아홉 번째 열의 위치를 테이블(345)의 첫 번째 열의 위치로 옮긴 것일 수 있다.

도 34e의 테이블(346)은 도 34d의 테이블(345)에 기초하여, 수직 클러스터들을 위한 차이 값을 축적한 결과를 포함한다. 여기서, 수직 클러스터들을 위한 차이 값을 축적하는 방법은 도 30a 내지 30h에 상세히 설명되어 있으므로 설명을 생략한다.

도 34f의 테이블(347)은 도 34d의 테이블(345)에 기초하여 수평 클러스터들을 위한 차이 값을 축적한 결과를 포함한다. 여기서, 수평 클러스터들을 위한 차이 값을 축적하는 방법은 도 31a 내지 31d에 상세히 설명되어 있으므로 설명을 생략한다.

프로세서(430)는 수직 클러스터 차이 값(346)의 모든 행과 수평 클러스터 차이 값의 결과(347)의 모든 행들 간의 비교를 통해서 차이 값의 합산을 수행할 수 있다. 상기 차이 값의 합산을 수행하는 과정은 도 32a 및 32b에서 상세히 설명하였으므로 여기서는 생략한다.

일 예로, 도 34g는 수직 클러스터 차이 값의 결과(346)와 수평 클러스터 차이 값의 결과(347)에 기초하여 얻어진 차이 값의 합의 결과값들을 포함하는 테이블(348)을 도시한다.

도 35a 및 35b는 본 발명의 다른 실시 예에 따른 쉬프트 테이블 결정 방법을 도시한다

프로세서(430)는 도 34g의 결과 테이블(348)을 이용하여 쉬프트 테이블을 생성할 수 있다.

예를 들어, 도 35a를 참조하면, 프로세서(430)는 결과 테이블(348)의 모든 셀의 값과 도 33a의 최소 셀 차이 값에 대한 테이블(310)의 모든 셀의 값을 비교하여 최소 차이값을 결정할 수 있다. 이 경우, 수학식 14가 이용될 수 있다. 여기서, 비교 대상이 되는 각 셀은 각 테이블의 동일 위치일 수 있다. 또한, 프로세서(430)는 특정 셀의 값이 설정되어 있지 않은 경우 해당 셀 값의 비교 결과를 0으로 결정할 수 있다.

일 예로, 프로세서(430)는 결과 테이블(348)의 셀(351-1)의 값 2와 최소 셀 차이 값에 대한 테이블(310)의 셀(310-11)의 값 4에 대하여 min(2, 4)는 2로 결정할 수 있다.

또한, 프로세서(430)는 예를 들어, 도 29h에 도시된 경계 셀에 대하여는 셀의 값에 대한 비교 과정을 생략할 수 있다.

도 35b의 최소 셀 차이 값에 대한 테이블(352)은, 도 35a의 셀 값 비교 방식에 기초하여 결과 테이블(348)의 셀들의 값과 도 33a의 최소 셀 차이 값에 대한 테이블(310)의 셀들의 값을 비교한 결과이다.

여기서, 프로세서(430)는 최소 셀 차이 값에 대한 테이블(352)의 셀의 최소 차이 값이 변경된 경우 쉬프트 양을 업데이트할 수 있다. 일 예로, 프로세서(430)는 최소 셀 차이 값에 대한 테이블(352)의 셀(352-1)의 값 2가 변경되었다고 판단되는 경우, 현재 쉬프트 양에 대한 값 1(353-1)을 업데이트할 수 있다.

도 36a 내지 36c는 본 발명의 또 다른 실시 예에 따른 쉬프트 테이블 결정 방법을 도시한다

도 36a는 캡쳐된 패턴이 2개의 셀 만큼 쉬프트된 경우, 수직 클러스터 차이 값의 결과와 수평 클러스터 차이 값의 결과에 기초하여 얻어진 차이 값의 합의 결과 값들을 포함하는 테이블(361)을 도시한다.

도 36b를 참조하면, 프로세서(430)는 테이블(361)의 모든 셀의 값과 도 35b의 최소 셀 차이 값에 대한 테이블(352)의 모든 셀의 값을 비교하여 최소 차이값을 결정할 수 있다. 이 경우, 수학식 14가 이용될 수 있다. 여기서, 비교 대상이 되는 각 셀은 각 테이블의 동일 위치일 수 있다. 또한, 프로세서(430)는 특정 셀의 값이 설정되어 있지 않은 경우 해당 셀 값의 비교 결과를 0으로 결정할 수 있다.

일 예로, 프로세서(430)는 테이블(362)의 셀(362-1)의 값 3과 최소 셀 차이 값에 대한 테이블(352)의 셀(352-11)의 값 2에 대하여 min(3, 2)는 2로 결정할 수 있다.

또한, 프로세서(430)는 예를 들어, 도 29h에 도시된 경계 셀에 대하여는 셀의 값에 대한 비교 과정을 생략할 수 있다.

도 36c의 최소 셀 차이 값에 대한 테이블(363)은, 도 36b의 셀 값 비교 방식에 기초하여 테이블(362)의 셀들의 값과 최소 셀 차이 값에 대한 테이블(352)의 셀들의 값을 비교한 결과이다.

여기서, 프로세서(430)는 최소 셀 차이 값에 대한 테이블(363)의 셀의 최소 차이 값이 변경된 경우 쉬프트 양을 업데이트할 수 있다. 일 예로, 프로세서(430)는 최소 셀 차이 값에 대한 테이블(363)의 셀(363-1)의 값 2가 변경되지 않았다고 판단 판단되는 경우, 현재 쉬프트 양에 대한 값을 셀(364-1)에 추가적으로 업데이트하지 않을 수 있다.

도 36c의 결과 테이블(363)은, 도 35a와 같은 셀 값 비교 방식에 기초하여, 결과 테이블(361)의 셀들의 값과 도 35a의 최소 셀 차이 값에 대한 테이블(310)의 셀들의 값을 비교한 결과이다.

여기서, 프로세서(430)는 최소 셀 차이 값에 대한 테이블(363)의 셀의 최소 차이 값이 변경된 경우 쉬프트 양을 업데이트할 수 있다. 일 예로, 프로세서(430)는 최소 셀 차이 값에 대한 테이블(363)의 셀(363-1)의 값 2가 변경되었다고 판단되는 경우, 현재 쉬프트 양에 대한 값 2(364-1)를 업데이트할 수 있다.

도 37a 내지 37c는 본 발명의 또 다른 실시 예에 따른 쉬프트 테이블 결정 방법을 도시한다.

도 37a는 캡쳐된 패턴이 3개의 셀 만큼 쉬프트된 경우, 수직 클러스터 차이 값의 결과와 수평 클러스터 차이 값의 결과에 기초하여 얻어진 차이 값의 합의 결과 값들을 포함하는 테이블(371)을 도시한다.

도 37b를 참조하면, 프로세서(430)는 테이블(361)의 모든 셀의 값과 도 36c의 최소 셀 차이 값에 대한 테이블(363)의 모든 셀의 값을 비교하여 최소 차이값을 결정할 수 있다. 이 경우, 수학식 14가 이용될 수 있다. 여기서, 비교 대상이 되는 각 셀은 각 테이블의 동일 위치일 수 있다. 또한, 프로세서(430)는 특정 셀의 값이 설정되어 있지 않은 경우 해당 셀 값의 비교 결과를 0으로 결정할 수 있다.

일 예로, 프로세서(430)는 테이블(372)의 셀(372-1)의 값 0과 최소 셀 차이 값에 대한 테이블(363)의 셀(363-1)의 값 2에 대하여 min(0, 2)는 0으로 결정할 수 있다.

또한, 프로세서(430)는 예를 들어, 도 29h에 도시된 경계 셀에 대하여는 셀의 값에 대한 비교 과정을 생략할 수 있다.

도 37c의 최소 셀 차이 값에 대한 테이블(373)은, 도 37b의 셀 값 비교 방식에 기초하여 테이블(372)의 셀들의 값과 최소 셀 차이 값에 대한 테이블(363)의 셀들의 값을 비교한 결과이다.

여기서, 프로세서(430)는 최소 셀 차이 값에 대한 테이블(373)의 셀의 최소 차이 값이 변경된 경우 쉬프트 양을 업데이트할 수 있다. 일 예로, 프로세서(430)는 최소 셀 차이 값에 대한 테이블(373)의 셀(373-1)의 값 0이 변경되었다고 판단되는 경우, 현재 쉬프트 양에 대한 값 3을 셀(374-1)에 업데이트할 수 있다.

한편, 프로세서(430)는 경계 셀을 처리할 수 있다.

프로세서(430)는 경계 셀을 처리하기 위해, 오리지널 패턴 및 쉬프트하여 클러스터된 패턴 간의 요소당 차이를 이용할 수 있다. 또한, 프로세서(430)는 모든 수직 클러스터들에 대한 각 셀의 축적된 차이를 이용할 수 있다. 또한, 프로세서(430)는 모든 수평 클러스터들에 대한 각 셀의 축적된 차이를 이용할 수 있다. 또한, 프로세서(430)는 경계 셀들을 제외한 모든 셀들에 대한 업데이트된 쉬프트를 이용할 수 있다. 또한, 프로세서는 타입(type) 1의 수평 경계 셀들, 타입 2의 수평 경계 셀들, 타입 1의 수직 경계 셀들, 타입 2의 수직 경계 셀들을 각각 또는 함께 처리할 수 있다.

경계 셀을 처리하는 예시는 이하 도 38a 내지 41e를 참조하여 설명한다.

도 38a 내지 38e는 본 발명의 일 실시 예에 따른 경계 셀 처리 방법의 예시를 도시한다.

도 38a 내지 38e는 타입 1의 수평 경계 셀들의 처리를 도시한다. 여기서, 타입 1 셀이란 수평 및 수직 연결들을 가지고, 셀의 인덱스가 수평 클러스터의 인덱스와 동일하며 그리고/또는 타입 1인 적어도 하나의 셀을 가지는 수직 클러스터 내부의 셀들로 정의될 수 있다.

도 38a 내지 38d는 셀 쉬프트가 없는 경우(0 cell shift), 셀 쉬프트가 1인 경우(1 cell shift), 셀 쉬프트가 2인 경우(2 cell shift) 및 셀 쉬프트가 3인 경우(1 cell shift)의 타입 1 및/또는 타입 2의 경계 셀들을 도시한다.

도 38e는 일 예에 따라, 인덱스에 의해 스스로의 수평 클러스터 및 수직 클러스터를 가질 수 있다. 또한, 테이블(381)의 셀(381-1)은 둘 이상의 쉬프트가 차이 0을 제공하는 경우에 발생된다. 하지만, 가장 큰 쉬프트가 적용될 수 있다.

도 39a 내지 39e는 본 발명의 다른 실시 예에 따른 경계 셀 처리 방법의 예시를 도시한다.

여기서, 도 38a 내지 38e에 대한 상술한 설명과 중복되는 설명은 생략한다.

도 39a 내지 39e는 타입 2의 수평 경계 셀들의 처리를 도시한다.

도 39a 내지 39d는 셀 쉬프트가 없는 경우(0 cell shift), 셀 쉬프트가 1인 경우(1 cell shift), 셀 쉬프트가 2인 경우(2 cell shift) 및 셀 쉬프트가 3인 경우(1 cell shift)의 타입 1 및/또는 타입 2의 경계 셀들을 도시한다.

도 39e는 일 예에 따라, 인덱스에 의한 스스로의 수평 클러스터 및 좌측 이웃 셀이 셀에 연결된 경우, 좌측 이웃 셀의 인덱스에 의한 수직 클러스터를 가진다.

도 40a 내지 40e는 본 발명의 또 다른 실시 예에 따른 경계 셀 처리 방법의 예시를 도시한다.

여기서, 도 38a 내지 39e에 대한 상술한 설명과 중복되는 설명은 생략한다.

도 40a 내지 40e는 타입 1의 수직 경계 셀들의 처리를 도시한다.

도 40a 내지 40d는 셀 쉬프트가 없는 경우(0 cell shift), 셀 쉬프트가 1인 경우(1 cell shift), 셀 쉬프트가 2인 경우(2 cell shift) 및 셀 쉬프트가 3인 경우(1 cell shift)의 타입 1 및/또는 타입 2의 경계 셀들을 도시한다. 여기서, 타입 1 셀은 수평 연결을 가지는 셀로 정의될 수 있다.

도 40e는 일 예에 따라, 수평 경계 셀들이 처리되면, 처리되는 셀을 포함할 수 있다.

인덱스에 의한 스스로의 수평 클러스터 및 좌측 이웃 셀이 셀에 연결된 경우, 좌측 이웃 셀의 인덱스에 의한 수직 클러스터를 가진다.

도 41a 내지 41e는 본 발명의 또 다른 실시 예에 따른 경계 셀 처리 방법의 예시를 도시한다.

여기서, 도 38a 내지 40e에 대한 상술한 설명과 중복되는 설명은 생략한다.

도 41a 내지 41e는 타입 2의 수직 경계 셀들의 처리를 도시한다.

도 41a 내지 41d는 셀 쉬프트가 없는 경우(0 cell shift), 셀 쉬프트가 1인 경우(1 cell shift), 셀 쉬프트가 2인 경우(2 cell shift) 및 셀 쉬프트가 3인 경우(1 cell shift)의 타입 1 및/또는 타입 2의 경계 셀들을 도시한다. 여기서, 타입 2 셀은 수평 연결이 없으나, 하나 또는 둘의 이웃 수직 클러스터를 가지는 것으로 정의될 수 있다.

도 40e를 참조하면, 프로세서(430)는 오리지널 패턴, 클러스터된 패턴, 이웃 클러스터 간의 차이를 최소화하는 최적의 쉬프트를 찾을 수 있다.

도 41e를 참조하면, 두 개의 클러스터들이 등가 차이 0을 제공하는 경우, 셀은 경계 셀로 세팅될 수 있다.

도 42는 본 발명의 일 실시 예에 따른 오브젝트 분할(object segmentation)을 도시한다.

오브젝트 분할은 오브젝트 중에서 동등한 깊이의 연결된 부분들을 나타내는데 이용된다. 분할 셋들(disjoint sets) 및 추정된 디스패리티 맵이 오브젝트 분할을 찾는데 이용된다. 오브젝트 분할은 세포 자동 패턴 인식 및 연결 요소 절차가 즉시 진행될 때 수행될 수 있다.

도 42를 참조하면, 사람 머리 형상의 오브젝트(421)의 이마 부분(421-1)은 수평 분할 셋(422)의 일부(422-1)에 대응될 수 있다.

도 43은 본 발명의 일 실시 예에 따른 오브젝트 분할 방법의 흐름도이다.

프로세서(430)는 수직 분할 셋 및 수평 분할 셋의 연결된 요소들을 판단한다. 또한, 프로세서(430)는 디스패리티 맵을 판단한다(S4310).

프로세서(430)는 수평 분할 셋 및 추정 디스패리티 맵으로부터 수평 클러스터를 이용하는 수직 분할 셋의 수직 클러스터들을 수정할 수 있다(S4320).

여기서, 수정 방향은 제1 셀 알고리즘으로부터 시작하여 좌우 및 상하로 이동한다. 또한, 현재 셀 및/또는 셀이 동등한 쉬프트를 가진다면, 수직 분할 셋의 현재 셀을 좌측 이웃 셀의 인덱스로 수정한다.

프로세서(430)는 수직 분할 셋을 메모리에 저장한다(S4330).

프로세서(430)는 디스패리티 맵의 변화에 따라 분할 셋을 수정한다(S4340).

도 44a 내지 44h는 본 발명의 일 실시 예에 따른 오브젝트 분할 방법을 설명하기 위한 도면이다.

도 44a는 본 발명의 일 실시 예에 따른 디스패리티 맵(441)을 도시한다. 도 44b는 본 발명의 일 실시 예에 따른 수직 분할 셋(442) 및 수평 분할 셋(443)을 도시한다.

프로세서(430)는 디스패리티 맵(441)과 수직 분할 셋(442) 및 수평 분할 셋(443)의 정보를 판단한다(또는 읽는다).

일 예로, 도 44c 및 44d를 참조하면, 프로세서(430)는 디스패리티 맵(441)의 적어도 두 번째 열의 디스패리티 정보에 기초하여 수직 분할 셋(442)의 적어도 두 번째 열의 인덱스 정보를 수정할 수 있다.

일 예로, 도 44e 및 44f를 참조하면, 프로세서(430)는 디스패리티 맵(441)의 여섯 번째 열의 디스패리티 정보에 기초하여 수직 분할 셋(442)의 여섯 번째의 적어도 하나의 셀(예를 들어, 442-1)의 정보를 수정할 수 있다. 또한, 프로세서(430)는 디스패리티 맵(441)의 일곱 번째 열의 디스패리티 정보에 기초하여 수직 분할 셋(442)의 일곱 번째의 적어도 하나의 셀(예를 들어, 442-1)의 정보를 수정할 수 있다.

도 44g 및 44h는 초기 분할 셋(44)과, 초기 분할 셋(444)으로부터 생성되는 최종 분할 셋(445)을 도시한다. 최종 분할 셋(445)은 오브젝트의 분할 영역들(445-1, 445-2)과 경계 셀 또는 패턴이 아닌 영역(445-2)를 포함할 수 있다.

상술한 도 44a 내지 44h에서 설명한 오브젝트 분할 방법은 셀이 2x2 픽셀 단위로 구성되는 경우에도 적용될 수 있음은 물론이다.

도 45a 내지 45f는 본 발명의 다른 실시 예에 따른 오브젝트 분할 방법을 설명하기 위한 도면이다.

도 45a 내지 45d는 본 발명의 일 실시 예에 따른 분할 셋(451, 452, 453, 454)을 도시한다.

본 발명의 일 실시 예에 따라 하나의 셀의 크기가 2x2 픽셀로 설정된다고 가정하면, 분할 셋(451)은 셀의 상-좌측의 픽셀들에 대한 인덱스 정보를, 분할 셋(452)은 셀의 상-우측의 픽셀들에 대한 인덱스 정보를, 분할 셋(453)은 셀의 하-좌측의 픽셀들에 대한 인덱스 정보를, 분할 셋(454)은 셀의 상-좌측의 픽셀들에 대한 인덱스 정보를 포함한다.

도 45e 및 45f는 본 발명의 일 실시 예에 따른 분할 셋(455, 455')을 도시한다.

본 발명의 일 실시 예에 따르면, 분할 셋(455)은 분할 셋(451, 452, 453, 454)의 인덱스 정보에 기초하여 작성될 수 있다. 분할 셋(455)은 자가-수정(self-repair)하는 셀(455-1)을 포함하고, 동일 영역에서의 합성(merge)되는 셀들(455-2)를 포함할 수 있다. 분할 셋(455')는 오브젝트 분할이 완료된 결과일 수 있다.

도 46a 내지 46c는 본 발명의 일 실시 예에 따른 삼각측량 방법을 도시한다.

도 46a를 참조하면, 프로세서(430)은 3차원 맵 포인트를 복원할 수 있다. 이를 위해, 프로세서(430)은 추정된 쉬프트 양, 감지부 (또는 카메라, 수광부) 렌즈 시스템의 파라미터들, 캘리브레이션 파라미터들을 이용할 수 있다.

여기서, 상술한 3차원 맵 포인트 복원은 삼각 측량법의 등식을 이용하여, 캡쳐된 세포 자동화 패턴의 각 픽셀들에 대한 X, Y, Z 값들을 계산하는 과정일 수 있다. X, Y, Z 값은 아래의 수학식 15에 기초하여 구해질 수 있다.

여기서, b는 조광부와 감지부 간의 베이스 라인(base line)이고,

는 오리지널 패턴과 캡쳐된 세포 자동화 패턴 간의 쉬프트 양이고, FOVch 및 FOVcv는 감지부 각도에 대응되는 시야(field of view) 값이고, Xp 및 Yp는 프로젝터의 주요 점과 관련된 캡쳐된 세포 자동화 패턴의 셀 좌표이다.

도 46b는 좌표 Xp 및 Yp에 대하여 설정된

를 도시한다.

도 46c는 수학식 15에 따라 얻어진 Z 값에 따른 깊이 정보를 포함하는 테이블(461)을 도시한다.

이상에서, 세포 자동화 패턴을 3차원 공간에 프로젝션하고, 3차원 공간에 반사되어 캡쳐된 세포 자동화 패턴을 이용하여 3차원 맵 포인트를 복원하는 과정을 다양한 도면을 참조하여 상세히 설명하였다.

이하에서는, 3차원 맵 포인트 복원 과정의 다양한 실시 예들을 설명한다. 이하의 실시 예들과 상술한 3차원 맵 포인트에 대한 실시 예들은 서로 독립되거나, 서로 조합되거나, 서로 보충될 수 있다.

도 47은 본 발명의 다양한 실시 예에 따른 세포 자동화 격자의 종류들을 도시한다.

도 48은 본 발명의 다양한 실시 예에 따른 직사각 격자에 대한 세포 자동화 규칙들의 예를 제시한다.

S 자가 조직 특성

이하에서, 세포 자동화 전개에 대해 상세히 설명한다. 세포 자동화는 각각의 사이트가 0나 1의 값을 가지도록(보통 확률 1/2) 랜덤하게 선택되는 무질서한 초기 상태들로부터 수행된다. 여기서, 무질서한 초기 상태들은 모든 가능한 구성들의 집합의 통상적 멤버들일 수 있다. 세포 자동화에 의해 생성되는 패턴들은 어떤 초기 상태를 가지고 획득된다. 이 패턴들의 구조는 세포 자동화에서의 자가 조직에 대한 표시일 수 있다.

세포 자동화는 통상적인 초기 구성들에서 시작할 수 있다. 또한, 세포 자동화는 네 종류의 자동화 전개 양태를 포함한다.

예를 들어, 세포 자동화 종류 1은 동기적 최종 상태들로 전개될 수 있다. 세포 자동화 종류 2는 분리된 주기적 구조들을 양산할 수 있다. 세포 자동화 종류 3은 혼돈의 양태를 보일 수 있으며, 비주기적 패턴들을 양산할 수 있다. 초기 상태들에 있어서의 작은 변화가 보통, 선형적으로 증가하는 변화 영역들로 이어질 수 있다. 세포 자동화 종류 4는 복잡한 국지적 전파 구조들을 보일 수 있다.

발명의 목표가 코딩된 공간 국지화를 통해 이차원 패턴을 생성하는 것이므로, 일차원 및 이차원 자동화의 종류 2가 본 발명에서 관심이 가는 것이다. 또한, 그러한 종류의 자동화(이차원 세포 오토마타의 경우)는 수 시간 후 정적인 상태를 취한다

따라서, 일차원 세포 자동화를 위해 수학식 1과 이차원 세포 자동화 전개를 위해 수학식 2를 사용하여, 일정한 이차원 패턴이 생성될 수 있다(도 49, 50 참조). 이차원 세포 자동화의 경우 수학식 2 가 수학식 1에 의해 생성되는 패턴에 적용될 수 있다.

규칙 코드

세포 자동화 전개는 규칙 넘버에 기초하여 수행될 수 있다. 본 발명의 일 실시 예에 다르면, 규칙 넘버의 베이스 2 디지트들이 세포 자동화 전개를 결정할 수 있다. 규칙 넘버의 마지막 비트는 셀의 모든 이웃들이 오프이고 해당 셀 역시 오프일 때의 셀의 상태를 특정할 수 있다. 마지막 비트의 다음 비트는 셀의 모든 이웃들이 오프이지고, 해당 셀은 온일 때의 셀의 상태를 특정할 수 있다.

또한, 각각의 앞선 비트들의 쌍은 점진적으로(총괄적) 보다 많은 이웃들이 블랙일 때 발생할 수 있는 것들을 특정할 수 있다. 일 예로, 비트들 2^0 및 2^1는 4개 이웃셀들 중 어느 것도 온이 아닌 경우 적용되고, 비트들 2^2 및 2^3는 1개 이웃셀이 온일 때 적용되고, 비트들 2^4 및 2^5는 2개 이웃셀들이 온일 때 적용되고, 비트들 2^6 및 2^7는 3개 이웃셀들이 온일 때 적용되며, 2^8 및 2^9는 4개의 모든 이웃셀들이 온일 때 적용될 수 있다. 일 예로, 규칙 614는 비트들 {1,0,0,1,1,0,0,1,1,0}에 해당할 수 있다.

5개 이웃의 외부 총괄 세포 자동화를 고려는 경우, 어떤 셀의 추후 상태는 4 개의 최근접 이웃들 (N, E, S, W) 및 셀 자체에 의해 결정될 수 있다. 단계 0에서 단계 1까지의 진행 시, 9 개의 셀들의 새로운 상태를 판단해야 한다. 제1셀(좌측 상위 코너)은 오프인 초기 상태를 가지며, 모든 이웃들은 오프이므로, 비트 2^0이 적용되어 새로운 상태가 오프임을 지시한다. 제2셀(최상위 행의 중간)은 오프인 초기 상태를 가지고 그 이웃들 중 하나(단계 0으로부터 원래 온인 셀)는 온이다. 한 이웃이 온이므로 비트들 2^2 및 2^3가 적용된다. 초기 상태가 오프이므로, 비트 2^2가 적용되어 새로운 상태가 온임을 지시한다. 원점에 있는 셀로 건너 뛰면, 어떤 이웃들도 온이 아니고 초기 상태는 온이므로, 비트 2^1이 적용되어 새로운 상태가 온임을 지시하도록 한다. 규칙 614에 대해 보다 구체적인 규칙의 내용이 기술될 수 있다. 셀의 상태는 다섯 셀들 중 홀수가 온일 때에만 온으로 바뀌거나 온 상태를 유지한다.

도 51은 본 개시의 일 실시 예에 따른 세포 자동화 전개를 도시한다. 도 51은 규칙 614에 의해 생성되는 전개 0 내지4 중 최초 다섯 개의 단계를 도시한다.

도 52는 본 발명의 일 실시 예에 따른 이차원 세포 자동화 규칙을 도시한다. 여기서, 세포 자동화는 "새로운 종류의 과학(New Kind of Science)"이라는 책의 Wolfram 용어에 따른 규칙 세트 736과 관련된다.

세포 자동화 전개를 위한 비동기 업데이트

세포 자동화는 J. 폰 뉴만과, 특히 자가 재생에 대한 폰 뉴만의 선구자적 연구에 의해, 자연스러운 물리 생물학적 현상들로 소개되었다. 세포 자동화는 각각이 가능한 값들의 유한 집합을 가지는, 도면 내 셀들의 n 차원 격자 상에서 결정되는 상호 연결되는 많은 수의 단순 동일 성분들을 포함하는 자동화의 특별한 종류이다. 세포 자동화는 이산적 시간 스텝들로 전개되고, 특정 셀에 의해 취해지는 값(국지적 상태)은 도면의 세포 자동화로서 알려진 함수

에 따라, 이전 시간 스텝 상의 그 이웃들의 셀 값들에 의해 영향을 받는다.

전역적 상태는 세포 자동화 시의 모든 자동화를 위한 국지적 상태들의 벡터라고 정의된다.

노드들이 집합 및 경계들의 집합 E인 그래프 G를 통해 세포 자동화 A를 소개할 것이다. 경계

는 무질서한 노드들의 쌍

이다. 노드의 이웃은 그래프 안에서 경계를 통해 그것에 바로 연결되는 집합이다. 또한 v'=nbhd(v)를 작성해야 하고, {v, v'}가 V에 포함되면 그것은 v의 이웃이라는 것이다.

여기서 결정론적 유한 세포 자동화 A는 상태들의 유한 집합 Q, 입력들의 유한 집합 X, 및 전환 함수

이다. 세포 자동화는 동일한 결정론적 유한 상태 자동화 및 다음과 같은 그래프 구조의 유한 또는 무한 네트워크이다:

1. 각각의 노드는 동일한 (유한한) 수의 이웃들을 가진다

2. 각각의 노드에서 이웃 노드들에 대해 고정된 순서를 가진다.

3. 노드 v의 다음 상태는 항상 동일한 함수

이며, 그에 따라 이웃 노드들에서의 정렬된 상태들의 리스트가 노드 v에서의 자동화 시에 입력된다.

노드 v의 이웃들의 상태들의 정렬된 리스트를

라고 표기한다. 본 발명의 세포 자동화는 어떤 N 차원 유클리드 공간 상에서, 예컨대 폰 뉴만이나 무어 이웃과 관련하여 이웃들을 포함하는 이차원 적외선 이미지의 정수 좌표들을 가진 픽셀들의 집합으로서 구현된다고 가정한다. 또한, 노드 v에서의 자동화가 상태

에 있고 모든 이웃들이 상태

에 있으면, 비동기 모드의 다음 전개 스텝에서 이 자동화의 상태는 계속

가 되도록, 국지적 유한 상태 자동화의 정지 상태

에 있는 것으로 보통 추정된다. 자동화 구성은 G라는 유한 서브 그래프의 노드들에서 자동화의 집합에 대한 국지적 상태 값들의 어떤 할당이다.

보통 세포 자동화는 모든 노드들에서 동시에(동기 모드) 이산적 단계로(전개 에포크) 유한 자동화의 상태를 업데이트하는데 필요하다. 따라서 모든 에포크 t>0에 대해, 에포크 t에서 각각의 노드 v가 어떤 상태

에 있는 경우, 다음 에포크 t+1에서 노드는 그 다음 상태

에 있게 되고, 그러한 다음 상태는 다음과 같다:

따라서, 국지적 업데이트 규칙은 자동화의 새로운 상태가 그것의 현재 상태 및 이웃들의 상태들의 유한 리스트에 따라서만 좌우된다는 것이다. 각각의 에포크에서 세포 자동화 A의 전역적 상태는 그것의 모든 노드들의 상태들

로 구성된다. 즉, 전역적 상태의 업데이트는 동기 모드로 수행된다. 여기서, 국지적 성분 자동화의 업데이트들은 동기 발생될 필요가 없다. 또한, 국지적 성분 자동화의 업데이트들 각각이 (국지적으로 이산적인) 시간이 지나면서 무한한 횟수로 그 다음 상태로 업데이트되는 경우, 비동기 자동화 네트워크에 대해 논의할 수 있다.

그래프 G 상의 각각의 동기적 자동화 A에 대한 일반적인 방법 및 Nehaniv의 이론을 따르면, 동일한 그래프 상에서 다른 세포 자동화 A'를 구축한다. 각각의 노드 v가

상태를 가지며 비동기적 업데이트 방법이 각각의 노드에 적용되는 경우, 그것은 비동기적일 것이다. 따라서 이론 A에 따라, 전역적 상태는 A'의 시공간 양태에 의해 온전하게 결정된다. 이러한 수학적 이론은 임의의 동기적 자동화 네트워크 상에서 수행될 수 있는 모든 계산치들은, 실제로 업데이트들이 나중에 어떻게 일어나는지에 대한 어떠한 제약도 없는 비동기적 자동화 네트워크의 계산으로부터 복구될 수 있다.

동기적 세포 자동화의 국지적 자동화로부터 비동기 세포 자동화 A'의 국지적 자동화를 구축할 수 있다. A의 국지적 자동화는 상태들

를 가지며,

는 정적이고 업데이트 함수

라고 가정한다. A'의 로컬 자동화의 상태들은

상태들

이다. 모든 이웃들은 이들 중 어느 것도 제3의 상태에 있지 않은 경우에 준비된다(0). 노드 v는 상태 (q, q', r)을 가지며 그 이웃들은 상태들

에 있다고 가정한다.

따라서 r=0인 경우 노드의 다음 상태는 다음과 같다:

그리고 r=1, 2인 경우 노드의 다음 상태는 다음과 같다:

세포 자동화의 자가 재생 특성

일반적으로 세포 재생의 자가 재생 특성은 소정 구성에 대한 동일한 패턴의 사본을 생성할 가능성이다. 이러한 세포 자동화의 특성은 인식 작업에 예정된 알고리즘들의 구축을 가능하게 한다. 세포 자동화 및 이미지 사이즈 MxN 픽셀들의 동기적 업데이트의 경우, 전체 패턴 중 일부(또는 현재의 자세)를 인식하기 위해 같은 수의 세포 자동화가 수행될 수 있다. 세포 자동화의 비동기적 업데이트의 경우, 인식은 현재의 위치 당 한 번씩 수행된다.

도 53은 본 발명의 일 실시 예에 따른 세포 자동화를 도시한다.

도 53에 따른 세포 자가생성(self-reproduction)은 세포 자동화 유한 상태(spatial code)(531) 단계, 세포 자동화 진화(evolution) 단계(532) 및 몇 번의 진화 후의 세포 자동화 일반 패턴 단계(533) 순으로 진행될 수 있다.

위에서 소개된 비동기 모드에 따르면 자가 재생은 주어진 자동화의 여러 사본들의 전개이다. 그러한 전개 프로세스들은 동기 모드 대신 동시에 발생된다. 따라서, 반사된 패턴을 가진 캡처된 이미지의 각각의 픽셀에서, 세포 자동화 전개는 이미지 변경의 수가 최소가 될 때까지 연속해서 변화하는 초기 공간 코드에서 시작된다. 캡처된 반사 패턴은 이미지이며, 그 변경은 픽셀 값이 패턴 픽셀에 해당하지 않는 경우 국지적 자동화 전개를 따라 발생한다.

도 54a 내지 54d는 본 발명의 다른 실시 예에 따른 세포 자동화를 도시한다.

도 54a 내지 54d는 격자의 상이한 위치들에서의 세포 자동화의 여러 사본들에 대한 비동기적 자가 재생을 도시한다.

구체적으로, 도 54a는 세포 자동화의 초기 상태들, 다른 초기 상태들은 세포 자동화 격자 상에서 코딩된 공간 정보일 수도 있다. 도 54b는 N 단계의 세포 자동화 전개 후를 보여준다. 도 54c는 n>N 단계의 세포 자동화 전개 후를 도시한다. 도 54 d는 n>>N 단계의 세포 자동화 전개 후를 도시한다.

세포 자동화의 자가 복구 특성

패턴이 투사된 후 반사되는 이미지(반사 패턴)는 일부분의 손실과 함께 캡처될 수 있다. 따라서, 세포 자동화 자가 복구는 저 반사도(블랙, 투명) 표면에서 비롯된 손실된 패턴의 이미지(스트립들, 스팟들 또는 도트들)을 복구하는 것이다. 복구 알고리즘의 입력은 손실 부분이나 잡음 부분을 가진 반사 패턴이다. 이때 초기화된 세포 자동화는 전체 패턴을 복구할 때까지 변화된다. 자체 복구 단계들이 디스패리티(disparity) 맵 개선을 위한 자가 재생의 결과 상에 적용된다.

도 55a 내지 도 55d는 본 발명의 다양한 실시 예에 따른 세포 자동화의 자체 복구를 도시한다.

도 55a에서 어두운 부분은 패턴의 손실 부분을 나타낸다. 도 55b에서 패턴이 볼(ball)의 어두운 영역에서 손실된다. 도 55c에서 세포 자동화의 N 회의 전개들 후의 복구가 도시된다. 도 55d는 복구가 완료된 패턴을 도시한다.

유전적 패턴 생성

일차원 세포 자동화에 의한 유전적 패턴의 생성은 모바일 기기의 메모리에서 초기 상태들 및 규칙들을 로딩하는 단계를 포함한다. 일차원 세포 자동화와 관련하여 초기 상태들은 세포 자동화의 모든 종들에 대해 랜덤하게 생성된 값들의 시퀀스를 포함하는 이미지의 행 또는 열(또는 같은 사이즈를 가지는 격자)로서 표현될 수 있다.

본 발명에서는 도 55a 내지 55d에 도시된 것과 같이 상기 자동화의 이차원 격자 상의 한 포인트로부터 일차원 자동화의 전개를 통한 생성을 제안한다. 격자의 기본 셀은 전력 소비 제한을 포함하는 투영 및 캡처링 어셈블리의 광학적 한계들에 따라, 하나의 픽셀 또는 더 넓은 너비를 가지도록 선택될 수 있다. 유전적 패턴 성장에 대한 전개 프로세스는 자동화 규칙에 대한 수학식 1을 이용하여 에포크(epoch)

가 될 때까지 계속된다. 에포크

는 독립적으로 선택될 수도 있으나, 본 발명에서 그것은 모든 상태들의 각각의 종들의 상태들이 등극선에 직교 방향으로 풀 격자 사이즈를 따라 완만히 분산된 값들을 가질 때의 세포 자동화의 상태들이다. 그것은 IR 카메라 및 IR 프로젝터 사이의 베이스라인 방위에 따라 좌우된다.

도 56는 본 발의 일 실시 예에 따른 세포 자동화를 위한 초기 상태들의 생성을 도시한다.

도 56에서, 패턴의 격자가 회전되어, 베이스라인 방향이 수직방향이다. 격자 사이즈는 640x480이다. 등극선 방향은 패턴 폭, 즉 적외선 이미지의 행들을 따른 방향이다.

이때, 에포크

로부터 전개된 모든 에포크들은 아래의 수학식 7로부터의 제로 디스패리티

과 관련된다.

여기서,

는 깊이 측정의 정밀도,

는 비례계수,

는 디스패리디 계측의 정밀도이다. 에포크는 IR 카메라 및 IR 프로젝터의 입체 교정 쌍 안에서 수행될 수 있다. 또한, 에포크는 IR 카메라의 원점

을 이용하여 조정될 수 있다. 각각의 에포크는 이러한 베이스라인의 방위에 대한 적외선 이미지 내 열 또는

(도면 참조) 열들로서 표현된다는 것을 알아야 한다.

도 57a 및 57b는 본 발명의 일 실시 예에 따른 초기 단계에서 생성된 패턴을 도시한다.

구체적으로, 도 57a는 일차원 세포 자동화를 이용하여 초기 에포크까지 생성된 패턴을 도시한다. 도 57b는 객체가 장면 안에 위치하는 경우 적외선 이미지 내 직사각 영역의 개략적 쉬프팅을 도시한다. 도 57b에서 세포 자동화 격자는 이미지 픽셀들(640x480)에 해당하는 셀들로 이루어진다. 베이스라인 방위는 여기서 수직방향이다.

이차원 세포 자동화에 의한 유전적 패턴의 생성은 일차원 자동화 적용 케이스에서와 유사하다. 차이는 차원수와 초기 상태 생성 방법에 있다. 초기 상태 생성은 도 56에 설명된 한 포인트로부터의 일차원 세포 자동화를 이용한 이차원 패턴 생성을 포함한다. 이 방법은 규칙의 수학식 2에 따라

사이즈의 직사각 셀들을 가진 이차원 격자 상에서의 이차원 이웃(5 또는 9 개의 이웃들)을 이용하여 이차원 세포 자동화를 전개한다. 전개는 위에서 설명한 바와 같이 세포 자동화 종류 2의 이차원 세포 자동화의 정지 상태를 검색하는 것까지 진행한다.

도 58은 본 발명의 다양한 실시 예에 따른 유전적 패턴을 도시한다.

도 58에서, 일차원 세포 자동화에 의해 생성되었던 유전적 패턴으로부터 이차원 격자(640x480) 상에서 이차원 세포 자동화를 통해 생성되는 유전적 패턴을 도시한다.

수학식 1이나 수학식 2를 이용하여 생성된 패턴은 기준 패턴이며, 진폭 정정과 같은 개선 수단을 포함하여 IR 프로젝터를 위한 투명한 바이너리 마스크를 구축하기 위해 사용된다. 이차원 세포 자동화의 실시예들의 경우, 초기 상태 패턴은 일차원 자동화에 의해 생성되며, 그것은 제로 디스패리티에 대한 지원 패턴이다.

종래의 매칭을 이용한 유전적 패턴의 실시예들

본 발명에 개시된 유전적 패턴은 상술한 것에 기반하는 의사 랜덤 비상관 준주기 및 특성 기반의 기존 선행 패턴들과는 다르다. 이차원 세포 자동화로 생성되는 유전적 패턴이, 세포 오포마타의 자가 조직 특성의 이용으로 인해 미니 패턴들(US 8,090,194 B2, "3D Geometric Modeling and Motion Capture Using Both Single and Dual Imaging" E. Golrdon, Mantis Vision Ltd (13/08/2007))의 주기적 그리드 조건을 만족할 때, 일차원 세포 자동화로 생성되는 유전적 패턴은 비상관 패턴의 필수 조건들에 부합하고 개신된 방법들 US 8,090,194 B2에 의해 활용될 수 있다.

도 59a 및 59b는 본 발명의 다양한 실시 예에 따른 매칭 영역을 도시한다.

도 59a 및 59b는 기준 및 반사 패턴들 간 오프셋들을 찾기 위한 매칭 영역들(171과 172)을 도시한다.

실제로 US 8,090,194 B2의 청구항들에 따른 방법은 캡처된 이미지를 처리하고, 교정 중 한번 캡처되었던 투영 패턴 및 기준 패턴을 가진 이미지에서 캡처된 여러 영역들(슬라이딩 윈도 방식 등) 상의 패턴 간 각각의 오프셋들을 찾고, 각각의 오프셋들에 따라 상기 영역들에 대한 각각의 거리들을 결정한다. 이 경우 생성된 디스패리티 맵들은 듀티 사이클 그레이 코드 및 n 중 변조와 같이 이용된 개선사항을 제외하면 최초에 개시된 것들과 유사할 것이다. 이때 매칭 프로세스는 반사된 기준 패턴으로부터 여러 영역들의 컨볼루션을 이용하여 수행될 수 있다. n 중 변조 없이 유전적 패턴이 생성된다는 사실과는 반대로, 공간 코드는 주파수 도메인에서의 푸리에 변환 해석을 이용하여 디코딩될 수 있다. 따라서 유전적 패턴에서 자가 조직되는 기하학적 프리미티브들은 구별 가능한 주파수의 피크들을 가진다.

다른 측면에서, 세포 자동화 종류 2의 이차원 세포 자동화는 주기적 그리드 상에서 구별 가능한 지속적 미니 패턴들을 가진다. 따라서, US 8,150,142 B2 ("Depth mapping Using Projected Patterns", B. Freedman, Prime Sense Ltd. (03/04/2012))의 청구항들에 따른 방법은 다음과 같이 기준 패턴과의 상관을 이용한 이미지 내 그리드의 포인트들에 대한 복조를 적용한다:

수학식 21은 반사 패턴 상의 상관 동작 및 국지적 영역 평균 모두에 대한 조합이 될 수 있다. US 8,150,142 B2의 상관(correlation)은 바이너리 배경에 의한 변조 결과 특성들의 이유로 선택되었고, 상기 상관은 적외선 이미지 내 각 픽셀에 대한 컨볼루션 대신 이하의 수학식 22과 같이 계산될 수 있다:

여기서,

는 픽셀 (i-2, j+2) 주변의 국지적 평균이다. 따라서, 이 매트릭스와 패턴과의 컨볼루션은 그리드의 포인트들에서 극한치를 제공할 것이다. 규칙, 예컨대 "736"을 이용한 유전적 패턴을 사용하고 상관(수학식 21)에 의해 유도됨으로써, 서브 픽셀 그리드 포인트들은 패턴의 구조에 따른 변조와 함께 유사한 상관 함수에 의해 검색될 수 있다.

도 60은 본 발명의 일 실시 예에 따른 패턴의 이미지 및 세포 자동화의 격자 간 대응관계를 도시한다.

2차원 세포 자동화는 직사각 격자 상에서 규정되고, 세포 자동화의 기본 셀은 사이즈

X

의 영역이며, 두 이웃 셀들의 쌍은 사이즈

X

및 다음을 가진다고 가정한다.

따라서, c = 1/4 (

+

)이면 격자 상의 자동화의 각 셀에 대한 수학식 24는 다음과 같이 규정된다:

여기서, 적외선 이미지에 걸친 이 함수의 극한 포인트들은 도면에서 도시한 것과 같은 그리드 상의 포인트들의 서브픽셀 위치들이다.

도 61a 및 61b는 본 발명의 일 실시 예에 따른 세포 자동화 격자의 계산된 그리드에 대한 물리적 그리드의 매핑을 도시한다.

도 61a 및 61b를 참조하면, 적외선 이미지 내 물리적 그리드(191) 상의 서브 픽셀 포인트들의 국지화 이후, 반사 패턴이 산출 평면의 일반 격자(192)로 매핑된다. 기준 및 매핑되고 반사된 패턴 사이의 상관관계들의 추가 매핑이 슬라이딩 윈도우 방식으로 컨볼루션되어 수행된다.

본 발명에서 상기 매핑은 세포 자동화 전개를 통해 수행되며, 이때 규칙들은 수학식 24로부터 검색된다. 국지적 평균 성분들은 다음과 같이 규칙을 구축하기 위해 사용되는 비가중 합들로 치환된다고 가정한다:

수학식 25으로부터의 그러한 규칙들의 구조는 유전적 패턴의 전역적 양태에 좌우된다. 이것이 그들의 설계가 유전적 패턴 생성에 사용되는 이차원 자동화의 각각의 정지 상태마다 각각 구축되는 이유이다.

알고리즘 근사화를 이용한 유전적 패턴의 실시 예들

본 발명의 일 실시 예에 따르면, 서브 픽셀 산출 평면 상에 반사 패턴을 매핑하기 위해 캡처된 적외선 이미지 내 각각의 셀의 픽셀 값들의 수많은 합들이 이용될 수 있다. 또한, 세포 자동화 규칙들은 전개 프로세스를 위해 이용될 수 있다. 또한, 컨볼루션 연산은 매칭 대응관계들의 개선을 위해 수행될 수 있다. 이에 따라, 전치 계산된 합 테이블들 및 근사화된 알고리즘들은 전력 소비를 감소시키는 역할을 한다. 아래의 '멀티미디어 신호 필터링 알고리즘의 근사화를 위한 방법'을 이용하여, 적외선 이미지의 세기들이 세포 자동화의 서브 픽셀 디스패리티 매칭을 위해 효과적으로 사전 계산될 수 있다.

한편, 멀티미디어 신호는 디지털 표현 안의 정보들에 보유되는 값들의 일차원 이상의 어레이이며, 그 위치는 하나의 고유한 정보에 해당한다. 예를 들어, 이미지는 픽셀들의 이차원 어레이이고, 여기서 픽셀은 j 번째 행 및 i 번째 열에 대응한다. 사운드는 음소들의 일차원 어레이이며, 여기서 음소는 i 번째 시점에 대응한다. 또한, 멀티미디어 신호의 각각의 부분은 이웃 부분들과 공간적 관계를 가진다. 그러한 관계는 해당 부분의 이웃으로 멀티미디어 신호의 그리드에 좌우된다. 예를 들어, 이미지는 이차원 직사각 그리드 상에서 규정되고, 이때, 노드들이 픽셀들에 위치하므로 각각의 픽셀은 그 주변의 이웃하는 8 개의 픽셀들을 가진다. 음소는 2 개의 이웃하는 값들 및 그 자체를 가진다. 컴퓨터 비전의 넓은 도메인 내에서, 다수의 멀티미디어 신호 처리 알고리즘들은 이웃 값들과 현재 부분의 값에 따라 원래 신호의 변환을 수행한다. 예를 들어, 가장 대표적인 예들이 이미지나 사운드 필터링 알고리즘들(그래디언트, 이미지 블러링, 사운드 변조, 잡음 제거 및 쌍방 필터링)이다. 나열된 기본 처리 알고리즘들은 기본 알고리즘들의 수십억 회의 실행 반복을 수반할 수 있는 AR/VR 콘텐츠 생성, 객체 인식, 분류 및 국지화와 같은 보다 복잡한 알고리즘들의 일부이다. 또한, 그러한 기본 알고리즘들의 성능은 많은 수의 이웃 값들의 읽기/쓰기(메모리 액세스) 및 이들의 조작(누적 및 곱) 실행을 수반한다. 이웃에 대한 상술한 연산들에 대해 가장 많이 사용되는 수학적 연산자가 콘볼루션이다. 일반적으로 이웃 관계들은 신호의 현재 부분에 대한 영향의 측정치(추정치, 계수)를 의미하는 값들의 어레이로서 표현된다. 보통 어레이 내 각각의 측정치를 가중치라 명명하고 가중치들의 어레이를 커널이라 명명한다(도 62 참조). 즉, 컨볼루션의 수학적 개념은 이웃의 가중 합으로 명명된다:

여기서, M, N은 이차원 커널의 폭과 높이이다. 예컨대 Mx1은 일차원 커널의 길이다.

도 62는 본 발명의 일 실시 예에 따른 컨볼루션을 도시한다.

도 62는 3x3 이차원 어레이 가중치들 1/9 (이차원 커널) 및 이차원 멀티미디어 신호(이미지)의 컨볼루션을 도시한다. 그 결과는 각각의 픽셀 값이 원래 이미지 내 픽셀의 이웃의 가중 합인 새로운 출력 이미지이며, 동일 값들의 연결성, 밀도, 또는 집중을 통해 가중치들에 의해 구성되는 미니 패턴들이라 명명되는 공간적 연결 그림들 또는 사진들을 제시한다.

커널의 가중치들은 변수로서, 결과적 신호에서 예상되는 효과 및 작업에 따라 좌우된다. 그러나, 소정 작업에 대한 정확한 커널을 고려할 경우, 그것은 프로그램 실행 중 일정하다. 예를 들어 도 40의 커널은 이미지의 블러링 전용이다. 어떤 커널들은 사용자의 사전 지식으로부터 구성되고, 다른 커널들은 반복적이거나 컨볼루션의 신경망들, Ada-boost 및 SVM 등과 같은 기계 학습 방식들을 통해 검색된다. 커널 안에서 모든 가중치들은 미니 패턴들이라 명명되는 어떤 공간적인 연결 그림들이나 사진들을 구축할 수 있다.

상기 '멀티미디어 신호 필터링 알고리즘의 근사화를 위한 방법'에서 컨볼루션의 근사 성능이 개시되며, 여기서 핵심 사상은 커널 내 상기 미니 패턴들의 집합인 커널들의 공간 구조를 이용하여 곱셈을 합산 연산들로 분할한다는 것이다. 그러한 분할은 상기 미니 패턴들과 같은 상기 공간 연결 구성들로 인해 이용 가능하게 된다. 또한, 커널 내 미티 패턴들의 수량이 K 개의 근사 구성요소들과 부합하고, 그 합은 상기 수학식 13에 근사하는 아래 형식의 선형 조합이 된다:

미니 패턴들은 커널 M x N의 부분들(가중치들)로 구성되므로, 한 커널에 대해 K

M x N이 된다. 가중치들을 미니 패턴으로 그룹화함에 따른 그러한 근사화는 많은 수의 커널들이 동일한 멀티미디어 신호에 적용될 경우 유용할 수 있다. 여기서, 알고리즘이 k 개의 커널들을 포함하므로 모든 커널들에 대해 k 개의 선형 조합들을 획득할 수 있다고 가정한다.

여기서, 미니 패턴이 단지 멀티미디어 신호의 부분들의 합이고, 미니 패턴들의 형식은 커널에만 좌우될 수 있다. 이것은 모든 K x K 형식들의 곱셈자들

이 주어진 커널들 k x M x N에 대한 모든 가능한 형식의 조합들임을 의미한다. 이때, 상기 미니 패턴들의 모든 가중치들이 동일하면, 곱셈자들

이, 원래 신호 안의 미니 패턴의 모든 부분들에 대한 합인 이차 합(수학식 29) 안에 들여질 수 있다. 그러한 합은 전체 커널(수학식 30)의 일부이며, 부분 합이다.

모든 가능한 M 개 형식들의 미니 커널들에 대한 테이블을 구축한다고 가정하면, 그 테이블은 M 개의 메모들을 가질 것이다. 테이블의 각각의 메모 안에는, 멀티미디어 신호 Row x Col의 부분들의 각각의 위치에 대한 소정 미니 패턴의 부분 합들(수학식 30)로 구성되는 새 이미지가 놓여진다.

상술한 내용과 관련된 이미지는 부분 합 이미지라고 칭해지며, 상술한 내용과 관련된 테이블은 부분 합 테이블이라 칭해진다. 이외에도 그러한 부분 합 이미지의 미니 패턴 합의 형식은 커널 내 오프셋을 포함할 수 있다. 따라서 미니 패턴들, 예컨대 서로 다른 오프셋을 가진 두 개의 서로 다른 커널들 안에 위치하는 2x1은 테이블 내 동일한 부분 합 이미지를 사용할 수 있다. 그런 다음 m회 만큼의

의 곱셈 대신, l 번째 커널마다 한 번씩 다른

이 곱해질 수 있다.

상기 미니 패턴들은 더 많은 커널들이 사용되어

이 될 때 부가적인 이점을 가져오는 여러 커널들 안에서 반복된다. 대부분의 커널들에 걸쳐 보다 많은 것들이 40%의 0들, 혹은 그 이상을 가진다. 예를 들어, 분류를 위한 컨볼루션 신경망은 직사각 이차원 패턴들에 대해 전력 소비 80% 감소를 가져오는 경우 1000 억개의 커널들을 가질 수도 있으며, 가속 레이트는 10배까지 높다. 가능한 미니 패턴들의 형식이 알려져 있고 그 수가 유한하고 적을 때 특별한 이점이 얻어진다. 이러한 경우는 멀티미디어 신호가 바이너리 값들 0/1, -1/1, 또는 1, 2, 2, 4..9를 가지는 경우 발생한다. 그러한 실시예의 예가 이진화 후의 유전적 패턴이다. 여기서 미니 패턴들은 알려져 있고, 자가 조직된 유전적 프리미티브들은 유한하며 그들의 형식들의 가변은 적다.

또한, 여러 커널들이 상술한 바와 같이 동일한 멀티미디어 신호(가령, 한 이미지)와 컨볼루션되는 이상적인 경우, 그 결과는 새로운 하나의 이미지로 누적된다. 그러한 커널들의 집합을 레이어(layer)라 칭한다. 그것은 객체, 말 및 손글씨의 인식, 분류 또는 국지화를 위한 머신 학습 기반 알고리즘들 안에서 일어난다. 그것은 보간 및 위치 추적을 위한 피라미드식 매칭 알고리즘들에 자주 사용된다. 그러한 경우의 독창성은 커널들의 컨볼빙 순서와 무관하다. 이들은 무작위로 선택될 수 있다. 이러한 목적으로 상기 '멀티미디어 신호 필터링 알고리즘의 근사화를 위한 방법'은 D+1 차원을 가진 다른 것으로 모든 커널들을 조합하는 것에 대해 개시하며, 이때 D는 커널들의 차원이다. 예를 들어, 이차원 커널들은 하나의 3차원 커널로 결합되고, 최적의 미니 패턴들은 도 21a 및 21b에 도시된 것과 같은 이차원이 아닌 3차원이다. 따라서, 상기 미니 패턴들은 입력 멀티미디어 신호의 부분들의 볼륨으로 구성된다. 이런 방식으로, K 미만의 여러 미니 패턴들이 얻어질 수 있기 때문에, 상기 미니 패턴들은 도 22a 및 22b에서 보듯이 전력 및 계산 횟수에 있어서 큰 이점을 취할 수 있다. 구조 광 카메라의 유전적 패널의 경우, 바이너리 표현이 사용되기 때문에 상기 3D 어레이는 매우 희박할 것이다.

컨볼루션 기반 접근 근사방식

컨볼루션 기반의 접근방식에 있어서, 핵심 사상은 유전적 패턴의 각각의 부분을 바이너리인 복수의 이차원 커널들로서 표현한다는 것이다. 따라서 개시된 알고리즘은 일반적인 경우의 합과 곱을 분리하기 위해 컨볼루션의 곱-합 연산들을 분할하는 것이다. 또한, 패턴의 바이너리 표현이 사용되는 경우 유전적 패턴을 가진 실시예들에서 곱셈이 강조된다. 그러한 분할은 3D 환경 재구축을 위한 매칭 프로세스 중의 전력 소비 및 계산상의 복잡도를 감소시킨다. 매칭을 해결하기 위해, 방법은 근사화, 부분 합들의 테이블 산출 및 가중화를 수행한다.

유전적 패턴의 커널 근사화는 윈도우 내 각각의 실제 값의 커널

의 공간 구조를 사용하여 정의된 커널 사이즈의 각각의 윈도우를 취급하여, 커널 내 근사적으로 동일한 값들을 가진 2차원 영역

내 부분 합들(수학식 27)의 동일한 선형 조합을 이용하여 그것을 재구성하도록 한다. 적외선 이미지로부터의 세기들을 이용하는 경우, 일반화 항목이 도입되어야 한다. 따라서 미니 패턴에 대한 상기 각각의 부분 합은 실제 값의 이미지(잡음, 패턴 변조, 깊이에 대한 세기의 의존도 등)로 인해 안에서 준 동일한 값들을 가진다. O가 커널 근사화 정확도라면, 출력 신호는 다음과 같다.

예를 들어, 도 63a는 실제 값에 대한 경우의 근사화에 대한 간략한 설명을, 와 도 63b는 바이너리에 대한 경우의 근사화에 대한 간략한 설명을 제공한다. 이하 도 63a 및 63b를 설명한다.

도 63a 및 63b는 본 발명의 일 실시 예에 따른 커널 근사화 개념을 도시한다.

도 63a는 연결된 구성요소의 공간 밀도 맵에 따라 3 개의 근사 영역 및 3 개의 가중치들을 가지고 근사화되는 실제 값의 커널 3x3이 주어지는 경우이고, 도 63b는 기준 유전적 패턴의 이진 표현이 주어진 경우로, 여기서 모든 셀들에 대해 1 셀을 쉬프트하는 윈도우 내 각각의 근사화 커널은 k 개의 연결 구성요소들 k=2(좌측), k=3(우측)을 가지고 근사화된다.

유전적 패턴의 각각의 커널의 동일한 선형 조합의 재구축은 최적 영역들

의 집합 및 세가 값들을 사용하는 경우 그 가중치들을 결정하는 것에 해당한다. 또한, 바이너리 값들을 사용하는 경우, k 개의 영역들

을 근사화하는 것은 윈도우 내에서 연결된 모든 k 개의 구성요소들이다.

2에서 13까지의 M 및 N을 가진 커널들의 유전적 패턴을 이용한 실시예들에서, 수학식 20의 양측의 평균 제곱 오차를 최소화하는 포괄적(exhaustive) 검색 또는 BFS 알고리즘들을 사용하여 해결된다. 따라서, 근사화 알고리즘은 커널 사이즈에 사용 가능한 모든 조합들을 아우른다. 그러한 검색은 원래의 커널과의 차이를 최소화하거나 근사화 정확도가 얻어지는 어떤 영역

도 존재하지 않는 경우 중단된다. 모든 윈도우들에 대한 부분 합들의 선형 조합들에 대해 검색된 집합은 매칭 알고리즘들의 근사화 성능을 위해 사용된다. 매칭 컨볼루션 A의 원래 성능은 도면이 도시한 것과 같이 많은 수의 포괄적 컨볼루션 연산들로 구성되고, 근사화 성능 A'는 실제 값

와 같은 각각의 영역

에 대한 중요 값들 및 부분 합들의 테이블

의 두 오프셋들을 가지고 가벼운 누적 연산을 수행한다. 알려진 이미지 사이즈는 모든 k 개의 영역들에 대한 부분 합 이미지들의 집합에 대한 오프셋들을 미리 산출하는데 사용된다. 이 이미지들은

라고 표기되는 하나의 부분 합 테이블 안에 누적된다.

그러한 전치 산출 후, 컨볼루션은 이하의 단계들에 따라 가중된 선형 조합을 산출한다:

1. 부분 합 산출(누적 연산들)

2. 가중화(곱셈 연산들)

3. 가중된 합들의 누적

도 64는 본 발명의 일 실시 예에 따른 컨볼루션 연산을 도시한다.

여기서, 컨볼루션 연산은, 곱셈-누적 단계들(상부) 및 별개의 곱셈 및 누적(하부)을 이용한다.

일반적으로 부분 합 테이블

은 유전적 패턴 내 윈도우의 각각의 근사화 미니 패턴에 해당하는 2차원 어레이들의 집합으로 구성된다. 이 어레이들은 연결된 구성요소에 따라 1x1, 1x2 ...,MxN 또는 그 이상의 보다 복잡한 것들과 같은 각각의 영역 구성을 위한 합들의 이미지들이다. 그러한 이미지의 각각의 위치에서, 입력 이미지의 합은 도 26이 도시한 것과 같이 미니 패턴에 대응한다.

가중화는 테이블

내 이미지의 미리 산출된 오프셋들에 따라 테이블로부터의 이미지들 중 하나와 상수

를 단순 곱한 것일 수 있다. 출력에 상응하는 가중된 부분 합의 누적이 수행될 수 있다. 바이너리 유전적 패턴에 있어서, 가중 계수들은 모두 1이다. 따라서, 그 결과는 한 번의 누적이다.

자가 재생 근사화

수학식 15 내지 17에 의해 소개된 비동기 모드에 따르면, 자가 재생은 주어진 규칙에 따라 초기 상태의 지원 패턴으로부터 주어진 자동화의 여러 사본들을 동시에 전개하는 것이다. 이차원 세포 자동화뿐 아니라 집합의 각각의 규칙이 3x3 셀들 또는

픽셀들의 캡처된 이미지의 사이즈를 가지는 커널로서 표현될 수 있는 다차원 세포 자동화를 고려하고, 이때 셀 값은

안의 모든 픽셀들의 누적 세기들을 이용하여 산출된다. 따라서, 외부의 총괄 세포 자동화(수학식 13)의 업데이트 상태 함수는 다음과 같은 패턴의 실제 값 표현에 대해 연결된 구성요소들(수학식 27)의 선형 조합을 통해 근사화될 수 있을 것이다:

그리고 이하의 식과 같은 바이너리 표현에 있어서, 근사화 오차는 0,

이다;

각각의 근사화 영역은 세포 자동화 격자 상의 위치 (i, j)에서의 셀

의 이웃에 있는 연결된 성분이다.

본 발명의 일 실시 예에 따르면, 캡처된 적외선 이미지가 먼저 부분 합 테이블

로 변환되고, 그런 다음 자동화 규칙의 연결된 성분에 대응하는 부분 합 이미지 상에서 수학식 34 및 35에 따른 근사화 규칙들을 이용하여 세포 자동화의 전개가 수행된다.

그리드 매핑 근사

규칙들(수학식 26)에 기초하여, 소개된 이차원 세포 자동화는 캡처된 이미지 내 물리적 서브 픽셀 그리드를 다음과 같이 산출되는 격자로 효율적으로 매핑하기 위해 근사화될 수 있다:

따라서, 본 발명의 일 실시 예에서 제1단계는 부분 합 테이블

산출이고, 그 후, 그리드 매핑의 근사화된 수행이 적용되어, 대응관계 매칭을 위한 자가 재생이나 픽셀 단위 컨볼루션 이전에 서브픽셀 국지화를 지원하도록 한다.

유전적 패턴으로부터 공간적 코드 해독

적외선 카메라는 반사된 유전적 패턴을 캡처하고, 그래서 얻어진 이차원 이미지가 해석되어 모바일 기기의 프로세서 상의 프로그램을 통해 처리된다. 프로그램은 캡처된 반사 패턴 및 생성된 기준 패턴의 매칭된 영역들 간 대응관계의 디스패리티 맵으로부터 깊이 정보를 재구축하는 삼각측량 기법을 이용할 수 있다. 디스패리티(불일치)는 다른 깊이에 자리하고 다른 시점들을 가지는 것으로 간주되는 동일한 객체가 등극선 방향을 따라 쉬프트하는 시차 효과로 인해 발생한다. 그러한 쉬프트는 깊이의 측정으로, 입체 카메라 교정 후 직교 방향을 따라서는 존재하지 않는다, 예컨대 쉬프트는 행을 따라 이루어지고 열을 따라서는 존재하지 않는다.

따라서, 행을 따라 패턴의 동일 부분들에 대한 매칭이 필요하다. 매칭된 영역들은 공간적 코드의 해독을 통해 결정된다. 해독 프로세스는 캡처된 패턴의 일부를 취하여, 각각의 새로운 전개 에포크가 반사 및 전개된 것들의 양호한 매칭을 가져올 때까지 그 부분으로부터 세포 자동화 전개를 하는 단계를 포함한다. 등극선 방향에 따라, 그러한 부분은 일차원의 경우 j 번째 행, i 번째 열, 또는 직교 방향으로 취해지는 그들의 서브 부분 및 이차원 이상의 경우 임의 형식의 영역일 수 있다. 매칭의 양호성에 대한 측정치는 공간의 길이를 가진 두 개의 바이너리 코드들의 해밍 거리이다. 해밍 거리는 바이너리 코드들에 대해 세포 자동화 전개를 이용해 생성되고 캡처된 이미지의 반사 패턴으로부터 산출될 수 있다.

일차원 세포 자동화 적용

본 발명의 일 실시 예에 따르면, 비가역성 제한 대신, 보다 일반적인 맥락에서 다차원 세포 자동화 자가 재생 특성이 사용될 수 있다. 도 58의 평면 테이블 상에 위치되어 왔던 단 하나의 직사각형 객체를 가진 환경 장면을 캡처할 수 있다. 그런 다음 적외선 이미지 내 객체의 직사각 영역은 등극선을 따라 쉬프트한다. 각각의 셀 위치의 공간적 코드에 대한 해독이 이차원의 이차원 패턴 안에서 수행된다. 세포 자동화 전개는 등극선 방향에 직교하는 방향을 따라 반사된 패턴의 모든 열들에 대해 수행된다.

에포크들까지의 모든 행들에 대해, 최소 쉬프트 발견이 수행된다. 따라서, 디스패리티는

이고, 이때,

는 에포크이고 i는 j 행의 기준 및 반사 패턴 간 해밍 거리가 i열에 대해 최소인 경우의 현재 열이다. 여기서, 각각의 에포크의 고유성이 이용된다. 이 예에서 테이블 표면과 관련된 모든 행들은 등극선을 따라 동일한 쉬프트(디스패리티)

를 갖으며, 이때,

는 테이블 깊이에서의 이차원 잡음이다. 그 외에도 알고리즘은 경계 및 음영 셀들을 표시하여 다음 단계들에서의 모호성을 제거하도록 한다. 그러한 디스패리티 맵은 홀들 및 아티팩트들과 같은 반균등 깊이 및 비매칭 면적을 가지는 영역들로 구성될 수 있다. 깊이를 가진 영역들은 픽셀 단위 정확도를 가진 장면의 재구성 또는 세그먼테이션(분할)을 위해 사용될 수도 있다.

보다 정확한 디스패리티 추정치를 검색하기 위해, 프로그램은 각각의 영역에서 열 단위 및 행 단위로 최초 추정된 새 패턴 형식을 구성한다. 이러한 구성 프로세스는 디스패리티의 추정 값들에 따라 각각의 매칭된 영역을 제로 디스패리티 위치로 백쉬프트하는 동작을 포함함으로써 그것이 유전적 기준 패턴과 관련될 수 있다. 검색된 새 패턴은 매칭되지 않거나 모호한 셀들 안에 홀들을 포함할 것이다. 프로그램이 구성된 패턴을 취한 후, 그로부터 자가 복구 프로세스를 인가한다. 자가 복구는 구성된 패턴으로부터의 전개를 의미하는 전역적 세포 자동화 전개를 포함한다. 수학식 15 내지 17에 따라 비동기 업데이팅 모드를 사용하여 개선 및 복구 프로세스가 수행될 수 있다. 이때, 비동기 모드 수학식 3에 의해 패턴 생성 및 초기 추정이 적용된다. 전역적 전개의 맥락은 기준 및 구성 패턴들 간 차이를 최소화하는 것이다. 따라서 각각의 셀에서의 전개는 홀들이나 아티팩트들과 같은 불충분하거나 손실된 정보를 비동기적으로 복구한다. 전체적인 기준 유전적 패턴에 의해 제공되는 전역적 제약사항들로 인해 그러한 개선이 가능하다. 선행 기술의 다른 유형의 알려진 패턴들은 그러한 특성을 갖지 않는다.

구성된 패턴의 복구 후, 매칭된 영역의 디스패리티 값이 패턴의 복구된 셀들로 할당된다. 그런 다음 모든 디스패리티들은 , 세포 자동화 격자의 해상도, 즉

픽셀들의 셀이나 픽셀에 의한 해상도를 가지는 하나의 디스패리티 맵 안으로 결합된다. 서브 픽셀 값들은 적외선 이미지의 물리적 평면으로의 격자 백 매핑 적용을 통해 획득된다. 따라서 포워드 매핑의 에러들이나 상기 설명 사항들에서 설명된 다른 왜곡들을 포함하는 서브 픽셀 디스패리티 맵이 획득된다. 그러한 에러들을 강조하기 위해, 그러한 에러 최적화 문제는, 불연속성이라는 제약사항들에 따라 모든 서브 픽셀 값들을 (실시예들이 IR 카메라의 IrW나 IrW-RGB 매트릭스를 이용하는 경우 텍스처나 컬러) 조정하기 위해 본 발명에서 이미 사용된 정적인 교정을 위한 레벤버그-마카르트(Levenberg -Marquardt) 비선형 최적화를 이용하여 해소될 수 있다.

이차원 세포 자동화 적용

이차원 세포 자동화에 의해 생성된 유전적 패턴의 해독은 일차원 세포 자동화 경우와 매우 유사하다. 차이는 행들(열들) 대신 영역에서의 상술한 기준 패턴 생성 및 자체 재생을 포함하는 것이다. 따라서, 초기 단계들에서, 프로그램은 일차원 세포 자동화(가령, 상술한 도면에서 설명된 것과 동일한 일차원 세포 자동화)의 전개를 이용하여 서포트하는 이차원 패턴을 생성한다. 이 패턴은 제로 디스패리티에 대한 서포트로서 사용된다. 이런 방식으로 각각의 셀 및 그 이웃에 대한 이차원 세포 자동화의 자체 재생을 초기화하기 위해 프로그램에 의해 서포트의 다양한 쉬프트들이 사용된다. 따라서, 프로그램은 디스패리티의 초기 추정치를 검색한다. 그런 다음, 프로그램은 각각의 영역에 대한 일차원 세포 자동화 경우와 관련하여 새로운 것을 생성하고 자가 복구를 수행한다. 픽셀 단위 디스패리티 맵의 초기 추정의 개선 후, 프로그램은 이차원 자동화의 자가 복구를 전역적으로 적용하여 홀들과 아티팩트들을 제거한다. 그런 다음 일차원 세포 자동화 경우와 유사하게, 밀집 서브 픽셀 디스패리티 맵을 얻기 위해 백 매핑 및 비선형 최적화가 적용된다.

도 65는 본 발명의 일 실시 예에 따른 유전적 패턴의 생성을 도시한다.

구체적으로, 도 65는 일차원 자동화에 의해 생성되었던 유전적 지원 패턴으로부터 이차원 세포 자동화 전개를 통한 유전적 패턴의 생성을 예시한다.

본 발명의 일 실시 예에 따르면, 양 종류-상태 업데이트 함수를 위한 수학식 33 내지 35는 일차원 이상의 세포 자동화를 위한 전개의 근사 성능을 가지는 부분 합 테이블에 적용될 수 있다. 그러한 근사화된 성능의 실시 예는 1 픽셀을 넘는 라인 사이즈를 가지는 유전적 패턴의 사용을 통한 밀집 깊이 재구성을 제공한다. 실제로

픽셀들의 셀 사이즈의 경우, 서브 픽셀 디스패리티 맵은 팩터

에 의한 원래의 IR 카메라 이미지보다 낮은 해상도를 가질 수 있다. 그리고, 셀들 간 중간 값들을 복구하기 위해, 컨볼루션 근사화가 수행될 수 있다. 이 경우, 컨볼루션 연산의 개수는 상술한 경우보다 오히려 적으므로, 초기 추정치가 사용되어 각각의 위치에 대해 가능한 커널들의 집합을 선택하도록 할 수 있다.

유전적 알고리즘

유전적 알고리즘을 통한 세포 자동화 전개

전개식 알고리즘들은 내츄럴 컴퓨팅의 하위 필드인 전개식 계산 필드의 알고리즘들을 위한 이름이다. 이것은 고차원 조합 또는 연속 검색 공간들에서의 검색 및 최적화 문제를 해결하기 위한 패러다임으로써 내추럴 전개의 원리를 이용하는 아이디어에 의해 영감을 받은 것이다. 가장 널리 알려진 예들이 유전적 알고리즘들, 유전적 프로그래밍, 전개 전략들, 및 전개식 프로그래밍이다.

전개식 알고리즘들의 모든 경우들에 대한 일반적 작동 원리는 연산자 변형에 대한 단순화된 구현, 재조합, 선택, 및 주어진 문제에 대한 후보 해법들(종종 개인들의 파퓰레이션이라고 부름)의 집합에 대한 최적화 전개를 수반하는 프로그램 루프에 기반한다. 이러한 일반적인 설정에서, 변형은 통상적으로 많은 변형보다 적은 변형을 선호하는 하나의 후보 해법에 대한 변형에 해당한다. 재조합은 둘 이상의 후보 해법들 사이의 구성요소들의 교환에 해당한다. 보다 열악한 후보 해법들 보다 다음 생성까지 보다 높은 확률로 증식시킬 보다 나은 후보 해법들을 선호함으로써 평균 적합도를 증가시키는 파퓰레이션들을 향한 전개식 프로세스를 드라이브한다. 적합도 평가를 통해 후보 해법과 관련된 양호성의 측정 산출이 의도된다, 즉 적합도 함수는 사용 가능한 최적화 문제의 객체 함수에 해당한다.

복잡한 알고리즘들의 파라미터들의 전개는 역 디자인 문제, 즉 타깃 디자인(매개변수화될 알고리즘의 동향)은 알려지지만 그것을 수행할 방법은 알려지지 않는 디자인 문제로 보여질 수도 있다. 세포 자동화(세포 자동화)의 역 디자인이 그러한 문제이다. 세포 자동화는 많은 분야에서 국지적 규칙들을 이용하여 전역적 양태를 생성하기 위해 사용된다. 원하는 양태를 디스플레이하는 규칙들의 발견은 특히 실제 세계의 문제들과 관련해 어려운 작업일 수 있다.

이하에서, 동기 업데이트 (수학식 1 및 2); 비동기 업데이트 (수학식 15 내지 17) 또는 근사화된 성능 (수학식 33 및 35) 에 따라 에포크

에서 에포크

까지 세포 자동화를 전개를 고려한다.

세포 자동화는 이차원 격자 상의 에포크

에서 상태들

을 가지고, 에포크

에서 상태들

를 가진다. 천이 규칙의 크기는 전력 소비 제한에 따라 가능할 때 더 클 것이다. 따라서 본 발명에서 유전적 알고리즘의 적합도 함수는

및 천이 규칙

에 의해 예측된 것 사이의 차이로서 도입될 수 있다. 세포 자동화 전개를 위한 성능의 근사화가 적용되기 때문에 개연성의 맥락에서 예측이라는 개념이 여기서 사용된다. 따라서, 유전적 알고리즘 GA는 세포 자동화 포워드 전개

정확한 근사화를 제공하는 최적의 해법이나 천이 규칙이 필요하다.

GA가 이 확률 값

를 만족하거나 최선의 성능을 만족하는 것을 찾기 위한 L 천이 규칙들(사이즈 9x9=81 비트들의 개개들)의 파퓰레이션을 전개하게 한다. 그것은 어떤 개별적인 것들을 살아있게 유지할지를 선택하기 위한 토너먼트 선택을 이용한다고 가정한다. 이것은 다음 세대를 결정하기 위해 파퓰레이션에 대한 '토너먼트들'을 실행하는 것을 포함한다. 매 토너먼트 q 개개의 것들이 세대 t로부터 무작위로 선택되며, 가장 높은 적합도를 가진 것이 세대 t+1에 대해 복사된다. 이것은 세대 t+1이 세대 t와 동일한 수의 개인들을 가질 때까지 반복된다.

선택 후, 세대 t+1 에 재조합이 적용된다. 재조합은 파퓰레이션의 부분집합에 대한 단일 포인트 크로스오버를 사용하고 확률적 비트 플립을 이용해 결과적인 개인들을 변형시킴으로써 행해진다. 크로스오버에 사용되는 개인들의 상대적 개수는 크로스오버 레이트 c로 표기된다. 변형은 확률 m을 가진 개인들의 모든 비트를 반전시켜 수행된다. 일 예로, 크로스오버 레이트는 추가 성능 근사화를 위해 최소미니 패턴들을 찾고자 하는 목적으로 작은 것이 선택될 수 있다. 파퓰레이션 내 모든 개인들이 개인들의 비트 코드의 1들의 개수에 대한 정규 분포를 이용하여 랜덤하게 초기화된다. 이것은 소정 수의 1들을 가진 개인들의 수가, 어떤 다른 수의 1들을 가진 개인들의 수와 대략 동일할 것임을 의미한다. 이것은 알고리즘이 알고리즘 시작 시 검색 공간의 특정 영역을 전문화하는 것을 방지한다. D 세대들 및 마지막 세대의 최선의 개인이 세포 자동화의 격자 상에서 셀 (i, j)의 소정 위치에 대한 최선의 답이라고 간주된 뒤에 종료된다. 이것은 알고리즘에 사용되는 적합도 함수가 확률적인 경우일 필요는 없으며, 그러한 모든 문제들이 하나의 문제로 결합될 수 있다. 따라서, 개인들의 수 L은 9x9셀들의 크기를 가진 격자 상의 셀들의 개수에 따라 선택되며, 이때 셀

이다.

적합도 함수의 평가는 각각의 셀에 각각 적용되는 천이 규칙 및 세포 자동화 규칙들을 통한 전개 간 평균 제곱 오차로서 수행되고, 이때 최선의 해법은 셀들의 모든 최적 해법들에 대한 소프트 맥스 함수에 의해 결정될 수 있다.

도 66은 본 발명의 일 실시 예에 따른 정적 자가 조직된 상태를 달성하기 위한 에포크 별 이차원 세포 자동화 전개를 도시한다.

도 67은 본 발명의 일 실시 예에 따른 유전적 알고리즘 GA를 이용하여 전역적 양태를 전개 시킴에 따른 이차원 세포 자동화의 단순화되거나 근사화된 성능을 도시한다.

GA는 이차원 격자의 모든 셀들에 대한 최적 천이 규칙들의 집합을 가져오며, 이것은 초기 상태에 직접 적용되어 최종 정지 상태 유전적 패턴을 생성한다. 즉, 수학식 12의 세포 자동화 규칙들은 다음 형식의 천이 규칙들로 대체될 수 있다:

유전적 알고리즘을 이용한 유전적 패턴의 실시 예

본 발명의 일 실시 예에 따르면, 세포 자동화의 전개의 원점 대신 천이 규칙들이 적용될 수 있다.

따라서, 자동화의 각 셀에 대한 동기적 업데이트(수학식 1 및 2) 및 비동기적 업데이트(수학식 1 내지 3)가 수학식 37로 대체된다. 상기 설명에 따르면, 이 방법은 셀 주변의 반사 패턴의 캡처된 이미지와 천이 규칙을 컨볼루션한다, 즉, 천이 규칙 매트릭스(수학식 37)의 부분 합

성분은 세포 자동화의 격자 상에서 현재 셀의 위치 (i, j)를 중심으로 한다. 격자 상의 셀들을 따라, 본 방법은 각각의 위치에 대응하는 천이 규칙

를 적용하고 이것을 L 회 반복한다, 이때, L은 셀들의 개수 및 천이 규칙들의 개수로서 도입된다. 유전적 패턴으로부터 공간적 코드를 디코딩하기 위해, 유전적 알고리즘을 이용하는 두 방식들이 가능하다. 첫 번째 방식은 다음과 같은 동기 및 비동기 모드들로 세포 자동화의 자가 재생을 위한 포워드 천이 규칙들을 이용하여 공간 코드를 디코딩하거나:

세포 자동화 규칙들이 가역적인 경우 반전 문제를 해소하는 것이다.

유전적 패턴은 커널로서 천이 규칙들의 근사화를 수행하고, 컨볼루션 기반 방식들 및 세포 자동화 전개 (수학식 34)에 대해 위에서 서술한 것과 동일한 방식으로 식들 (수학식 38) 또는 (수학식 39)을 컨볼빙하는 근사화된 기능을 수행한다. 따라서, 실제 값의 세기들을 이용한 세포 자동화 전개를 위한 유전적 패턴은 다음과 같다:

도 68에 도시된 것과 같은 바이너리 유전적 패턴에 대해:

도 68은 본 발명의 일 실시 예에 따른 컨볼루팅 커널로서의 근사화 중 천이 규칙 내 연결 성분을 도시한다.

따라서, 상기 '멀티미디어 신호 필터링 알고리즘의 근사화를 위한 방법'에 따른 천이 규칙의 집합은 한 레이어에 속하는 커널들의 집합으로서 표현될 수 있다. 또한, 천이 규칙들이 2차원이기 때문에 하나의 3차원 어레이 안에 결합될 수 있다. 그러한 어레이 안에서 커널들이 순열화되어 실제 값의 세기들 및 그에 따른 바이너리 유전적 패턴에 대한 미니 패턴이나 연결 성분들의 최소 개수를 찾도록 한다. 그런 방식으로 본 발명의 방법은 캡처된 이미지 내 유전적 패턴과 천이 규칙들의 컨볼빙을 위해 근사화된 기능을 수행할 수 있다.

다른 실시예

다중 뷰 캡처링에 따른 해상도 증가

일차원 및 이차원 세포 자동화를 이용한 상술한 암호화는 서브 픽셀 정밀도를 가진 적외선 이미지 해상도와 상응하는 깊이 포인트 클라우드 밀도를 제공한다. 깊이 해상도는 깊이의 이차 함수이다. 이것은 1 픽셀에서의 디스패리티가 다른 범위의 깊이를 커버한다는 것을 의미하며, 이것은 카메라로부터의 거리를 증가시킨다.

도 69는 본 발명의 포인트 클라우드 밀도 감소를 도시한다.

구체적으로, 도 69는 밀도가 항상 640x480 = 307200 포인트들일 때, 카메라까지의 거리 증가에 따라 포인트 클라우드의 밀도를 감소시키는 것을 도시한다.

이러한 종속관계를 없애기 위해 IR 프로젝터나 IR 카메라 렌즈는 자계 적용을 통해 광축을 중심으로 진동할 수 있다. 따라서, 카메라는 다양한 각도의 시점을 가지고 다양한 이미지들을 캡처할 수 있다. 상기 각도들이 작고 알려진 진동 차수여야 한다는 것이 중요하다. 따라서, 프로그램(또는 프로세서)은 깊이 정확도를 통계적으로 증가시키고 작업 영역을 따라 최대 거리까지 해상도를 증가시키도록 몇몇 프레임들을 처리할 수 있다. 따라서, 프로그램은 각각의 프레임에서 암호화 및 깊이 추정을 수행한다. 이때 알려진 렌즈 진동 각도들에 대응하는 회전 변환을 통해 모든 재구성된 포인트 클라우드들의 융합을 적용한다.

대안들 및 추가 실시예들

AR/VR 지향 모바일 기기

모바일 기기(상기 '멀티미디어 신호 필터링 알고리즘의 근사화를 위한 방법')에서 주장하는 근사화된 성능을 가진 3D 환경 재구성을 위한 시스템과 방법은 이하 '3차원 콘텐츠 생성'에 개시된 3D 콘텐츠 생성 및 카메라의 6DoF 위치 추적 및 견고한 바디 포즈 추정(이하 '위치 추적')을 위해 동시적 국지 영역 매핑을 수행할 수 있다. 이와 관련하여, 본 발명의 실시 예들은, 적외선 이미지 내 유전적 패턴을 감산하고, 인식된 음영들과 3D 환경 맵과 함께 객체들을 세그먼테이션하는 것을 포함하여 환경의 잉여 이미지를 이용하기 위해 사용될 수 있다. 6DOF UX 생성(이하 '3차원 콘텐츠 생성)을 위한 방법에 따라, 마지막 것이 영역 매핑 시 사용될 수 있고, 이때 카메라 및 프로젝터 간 베이스라인에 상응하는 엣지들을 가진 가상의 다면체의 꼭지점에서만 메모리에 키 프레임들을 저장할 수 있다. 또한, 개시된 복잡한 뷰 합성(이하 '위치 추적')을 통해 그러한 다면체의 볼륨 내 중간 포인트 클라우드들(맵)의 재구성 및 해상도 개선할 수 있다. 상기 '멀티미디어 신호 필터링 알고리즘의 근사화를 위한 방법'은 상기 '위치 추적'으로부터의 컨볼루션 신경망의 근사화를 위해 사용된다. 그러한 근사화된 성능은 VR/AR에서의 자연스러운 사용자 인터페이스를 위해 서브 픽셀 위치 추적 및 견고한 바디 포즈 추적을 위한 3D 보간에 사용될 수 있다.

도 70은 본 발명의 일 실시 예에 따른 3차원 이미지를 위한 깊이 정보를 산출하는 방법을 나타내는 흐름도이다.

본 발명의 일 실시 예에 따른 깊이(depth) 정보를 산출하는 방법은 2차원 이미지에 포함되는 적어도 하나의 셀의 값에 기초하여 패턴을 생성하는 과정(3710), 패턴을 투사하는 과정(3720), 패턴이 반사된 이미지를 촬영하는 과정(3730) 및 패턴이 반사된 이미지에 기초하여 깊이 정보를 산출하는 과정(3740)을 포함할 수 있다.

여기서, 패턴을 생성하는 과정은, 2차원 이미지에 포함되는 복수의 셀들 각각에 값을 설정하는 과정을 포함할 수 있다. 예를 들어, 복수의 셀들 각각에 설정되는 값은 0 또는 1일 수 있다.

또한, 2차원 이미지에 포함되는 적어도 하나의 셀의 값은 2차원 이미지에 포함되는 복수의 셀들의 행 또는 열에 설정된 초기 값일 수 있다.

그리고, 패턴을 생성하는 과정은 2차원 이미지에 포함되는 하나의 셀의 값과, 하나의 셀에 이웃하는 두 개의 셀들의 값들에 기초하여, 하나의 셀에 이웃하는 다른 셀의 값을 결정할 수 있다.

구체적으로, 패턴을 생성하는 과정은 2차원 이미지에 포함되는 하나의 셀의 값과, 하나의 셀에 이웃하는 두 개의 셀들의 값들의 합에 기초하여, 하나의 셀에 이웃하는 다른 셀의 값을 결정할 수 있다.

이 경우, 깊이 정보를 산출하는 과정은, 패턴이 반사된 이미지에 포함되는 복수의 셀들의 행 또는 열의 셀 값에 기초하여 패턴을 생성하는 과정을 포함할 수 있다.

또한, 행 또는 열의 셀 값에 기초하여 패턴을 생성하는 과정은 행 또는 열에 포함되는 하나의 셀의 값과, 하나의 셀의 이웃하는 두 개의 셀들의 값들에 기초하여, 하나의 셀에 이웃하는 다른 셀의 값을 결정하는 과정을 포함할 수 있다.

여기서, 깊이 정보를 산출하는 과정은 패턴이 반사된 이미지에 포함되는 복수의 셀들의 값과, 행 또는 열의 셀 값에 기초하여 생성된 패턴에 포함되는 복수의 셀들의 값을 비교하는 과정을 포함할 수 있다. 일 예로, 깊이 정보는 비교 과정의 결과에 기초하여 결정될 수 있다.

한편, 상술한 본 개시의 다양한 실시 예들에 따른 깊이 정보 산출 방법은 컴퓨터로 실행 가능한 프로그램 코드로 구현되어 다양한 비 일시적 판독 가능 매체(non-transitory computer readable medium)에 저장된 상태로 프로세서에 의해 실행되도록 각 서버 또는 기기들에 제공될 수 있다.

일 예로, 2차원 이미지에 포함되는 적어도 하나의 셀의 값에 기초하여 패턴을 생성하는 과정, 패턴을 투사하는 과정, 패턴이 반사된 이미지를 촬영하는 과정 및 패턴이 반사된 이미지에 기초하여 깊이 정보를 산출하는 과정을 수행하는 프로그램이 저장된 비일시적 판독 가능 매체(non-transitory computer readable medium)가 제공될 수 있다.

상술한 다양한 어플리케이션 또는 프로그램들은 CD, DVD, 하드 디스크, 블루레이 디스크, USB, 메모리카드, ROM 등과 같은 비일시적 판독 가능 매체에 저장되어 제공될 수 있다.

또한, 이상에서는 본 개시의 바람직한 실시 예에 대하여 도시하고 설명하였지만, 본 개시는 상술한 특정의 실시 예에 한정되지 아니하며, 청구범위에서 청구하는 본 개시의 요지를 벗어남이 없이 당해 발명이 속하는 기술분야에서 통상의 지식을 가진 자에 의해 다양한 변형실시가 가능한 것은 물론이고, 이러한 변형실시들은 본 개시의 기술적 사상이나 전망으로부터 개별적으로 이해되어져서는 안될 것이다.

단말: 400 프로젝터: 410
촬영부: 420 프로세서: 430

Claims (20)

1. 깊이(depth) 정보를 획득하는 방법으로서,
   2차원(2D) 이미지에 포함되는 복수의 셀들의 값에 기초하여 패턴을 생성하는 단계 ― 상기 패턴을 생성하는 단계는 상기 2D 이미지에 포함된 상기 복수의 셀들 중 제1 셀의 값 및 상기 제1 셀에 이웃한 두 셀들의 값들의 합에 기초하여, 상기 제1 셀에 이웃한 다른 셀의 값을 결정하는 단계를 포함함 ― ;
   3차원(3D) 공간에 배치된 오브젝트에 상기 패턴을 투사하는 단계 ― 상기 패턴은 상기 오브젝트로부터 반사됨 ― ;
   상기 반사된 패턴의 이미지를 촬영하는 단계 ― 상기 촬영된 이미지는 상기 반사된 패턴에 대응하는 값들을 갖는 복수의 픽셀들을 포함함 ― ; 및
   K-평균(K-means) 알고리즘을 이용하여, 상기 촬영된 이미지 내의 상기 복수의 픽셀들 중 클러스터 윈도우 내의 픽셀들의 값들의 각각을 제1 값 및 제2 값 중 하나로 변형하는 것에 기초하여, 상기 촬영된 이미지로부터의 패턴을 클러스터링하는 단계 ― 상기 클러스터 윈도우의 크기는 상기 클러스터링된 패턴의 셀 크기에 기초하여 설정됨 ― ;
   상기 클러스터링된 패턴 및 상기 생성된 패턴에 기초하여 상기 픽셀들의 차이(disparity)를 추정하는 것에 의해 상기 촬영된 이미지에 기초하여 상기 오브젝트의 상기 깊이 정보를 획득하는 단계를 포함하는,
   방법.
   
2. ◈청구항 2은(는) 설정등록료 납부시 포기되었습니다.◈

   제1 항에 있어서,
   상기 패턴을 생성하는 단계는,
   상기 2D 이미지에 포함되는 상기 복수의 셀들 각각에 값을 설정하는 단계를 포함하는,
   방법.
   
3. ◈청구항 3은(는) 설정등록료 납부시 포기되었습니다.◈

   제2 항에 있어서,
   상기 복수의 셀들 각각에 설정되는 값은 0 이상의 정수들 중에서 선택되는,
   방법.
   
4. 제1 항에 있어서,
   상기 2D 이미지에 포함되는 상기 제1 셀의 값은, 상기 2D 이미지에 포함되는 상기 복수의 셀들의 행 또는 열에 설정된 초기값인,
   방법.
   
5. 제1 항에 있어서,
   상기 깊이 정보를 획득하는 단계는,
   상기 촬영된 이미지에 포함된 복수의 셀들의 행 또는 열의 셀들의 값들에 기초하여 상기 클러스터링된 패턴을 생성하는 단계를 포함하는,
   방법.
   
6. 제5 항에 있어서,
   상기 행 또는 열의 셀들의 값들에 기초하여 상기 클러스터링된 패턴을 생성하는 단계는,
   상기 행 또는 열에 포함되는 하나의 셀의 값과, 상기 하나의 셀의 이웃하는 두 개의 셀들의 값들에 기초하여, 상기 하나의 셀에 이웃하는 다른 셀의 값을 결정하는 단계를 포함하는,
   방법.
   
7. 제5 항에 있어서,
   상기 깊이 정보를 획득하는 단계는,
   상기 촬영된 이미지에 포함되는 복수의 셀들의 값들과, 상기 행 또는 열의 셀들의 값들에 기초하여 생성된 패턴에 포함되는 복수의 셀들의 값들을 비교하는 단계를 포함하는,
   방법.
   
8. ◈청구항 8은(는) 설정등록료 납부시 포기되었습니다.◈

   제7 항에 있어서,
   상기 깊이 정보는 상기 비교의 결과에 기초하여 결정되는,
   방법.
   
9. 단말에 있어서,
   프로젝터;
   촬영부; 및
   상기 프로젝터 및 상기 촬영부에 연결된 적어도 하나의 프로세서를 포함하고, 상기 적어도 하나의 프로세서는:
   2차원(2D) 이미지에 포함된 복수의 셀들 중 제1 셀의 값 및 상기 제1 셀에 이웃한 두 셀들의 값들의 합에 기초하여, 상기 제1 셀에 이웃한 다른 셀의 값을 결정하는 것에 의해, 상기 2D 이미지에 포함되는 상기 복수의 셀들의 값에 기초하여 패턴을 생성하고,
   3차원(3D) 공간에 배치된 오브젝트에 상기 패턴을 투사하고 ― 상기 패턴은 상기 오브젝트로부터 반사됨 ― ;
   상기 반사된 패턴의 이미지를 촬영하고 ― 상기 촬영된 이미지는 상기 반사된 패턴에 대응하는 값들을 갖는 복수의 픽셀들을 포함함 ― ;
   K-평균(K-means) 알고리즘을 이용하여, 상기 촬영된 이미지 내의 상기 복수의 픽셀들 중 클러스터 윈도우 내의 픽셀들의 값들의 각각을 제1 값 및 제2 값 중 하나로 변형하는 것에 기초하여, 상기 촬영된 이미지로부터의 패턴을 클러스터링하고 ― 상기 클러스터 윈도우의 크기는 상기 클러스터링된 패턴의 셀 크기에 기초하여 설정됨 ― ;
   상기 클러스터링된 패턴 및 상기 생성된 패턴에 기초하여 상기 픽셀들의 차이(disparity)를 추정하는 것에 의해 상기 촬영된 이미지에 기초하여 상기 오브젝트의 깊이 정보를 획득하도록 구성되는,
   단말.
   
10. ◈청구항 10은(는) 설정등록료 납부시 포기되었습니다.◈

    제9 항에 있어서,
    상기 적어도 하나의 프로세서는,
    상기 2D 이미지에 포함되는 상기 복수의 셀들 각각에 값을 설정하여 상기 패턴을 생성하도록 구성되는,
    단말.
    
11. ◈청구항 11은(는) 설정등록료 납부시 포기되었습니다.◈

    제10 항에 있어서,
    상기 복수의 셀들 각각에 설정되는 값은 0 이상의 정수들 중에서 선택되는,
    단말.
    
12. 제9 항에 있어서,
    상기 2D 이미지에 포함되는 상기 제1 셀의 값은,
    상기 2D 이미지에 포함되는 상기 복수의 셀들의 행 또는 열에 설정된 초기 값인,
    단말.
    
13. 제9 항에 있어서,
    상기 적어도 하나의 프로세서는,
    상기 촬영된 이미지에 포함된 복수의 셀들의 행 또는 열의 셀들의 값들에 기초하여 상기 클러스터링된 패턴을 생성하도록 구성되는,
    단말.
    
14. 제13 항에 있어서,
    상기 적어도 하나의 프로세서는,
    상기 행 또는 열에 포함되는 하나의 셀의 값과, 상기 하나의 셀의 이웃하는 두 개의 셀들의 값들에 기초하여, 상기 하나의 셀에 이웃하는 다른 셀의 값을 결정하도록 구성되는,
    단말.
    
15. 제13 항에 있어서,
    상기 적어도 하나의 프로세서는,
    상기 촬영된 이미지에 포함되는 복수의 셀들의 값들과, 상기 행 또는 열의 셀들의 값들에 기초하여 생성된 패턴에 포함되는 복수의 셀들의 값들을 비교하도록 구성되는,
    단말
    
16. ◈청구항 16은(는) 설정등록료 납부시 포기되었습니다.◈

    제15 항에 있어서,
    상기 깊이 정보는, 상기 비교의 결과에 기초하여 결정되는,
    단말.
17. 삭제
18. 삭제
19. 삭제
20. 삭제

Images