KR102670714B1 - Gpu를 기반으로 한 결정 트리를 이용한 대응점 탐색 방법 - Google Patents

Abstract

본 발명은 GPU를 기반으로 한 결정 트리를 이용한 대응점 탐색 방법에 관한 것이다. 상기 대응점 탐색 방법은, (a) 영상을 입력받고, 입력 영상에 대한 채널을 검사하고, 영상 채널별로 데이터를 분리하는 단계; (b) 입력 영상내 모든 픽셀에 대하여 이미지 픽셀 패치에 대한 기술자(Descriptor)를 계산하는 단계; (c) 결정 트리 연산을 수행하여 각 픽셀에 대한 결정 트리 인덱스(pixel forest index)를 획득하는 단계; (d) 각 픽셀에 대해 획득된 결정 트리 인덱스들을 정렬하는 단계; (e) 결정 트리의 리프 노드에서 하나의 같은 결정 트리 인덱스를 갖는 픽셀들을 대응점으로 판단하는 단계; (f) 대응점으로 판단된 픽셀들에 대한 정보를 출력하는 단계;를 구비한다. 본 발명의 대응점 탐색 방법은 GPU를 기반으로 하여 병렬 연산 처리되는 것이 바람직하다.

Description

GPU를 기반으로 한 결정 트리를 이용한 대응점 탐색 방법{Method for matching correspondence by using decision forest based on GPU}

본 발명은 영상간의 대응점 탐색 방법에 관한 것으로서, 더욱 구체적으로는 GPU를 기반으로 한 병렬 처리를 통해, 실시간으로 영상간의 대응점을 탐색함으로써 향상된 성능을 제공하고 학습 기반으로 결정 트리를 생성하여 대응점을 탐색하도록 하는 대응점 탐색 방법에 관한 것이다.

영상의 물체의 움직임을 분석하거나 영상의 구조에 대한 정보를 획득하기 위하여 대응점 탐색에 대한 많은 연구가 진행되었다. 이러한 연구는 광학 흐름(Optical Flow) 및 스테레오 매칭의 응용 연구 분야에서 핵심 기반 기술로 볼 수 있다. 특히, 다시점 영상의 3D 복원 및 실시간 4D 복원을 비롯하여 다양하게 개발되고 있는 증강 현실 및 가상 현실 환경에서도 대응점 정보의 탐색이 요구되고 있다.

대응점 탐색 방법은 크게 픽셀의 특징점을 이용하는 방법과 시공간 경사를 이용하는 방법이 있다. 상기 픽셀의 특징점을 이용한 대응점 탐색 방법은, 특징점을 구하는 다양한 방법이 이용되는데, 영상간의 특징점에 대해 기술자를 연산하고 대응되는 픽셀을 탐색하여 대응점에 대한 정보를 얻게 된다. 상기 시공간 경사를 이용한 대응점 탐색 방법은, 영상 간 밝기 분포가 일정하다는 가정하에 프레임간의 수평, 수직, 시간에 대한 변화를 연산하여 최적화시켜 추정이 가능하다.

전술한 바와 같이, 영상의 물체의 움직임을 분석하거나 영상의 구조에 대한 정보를 획득하기 위한 대응점 탐색 방법은 다양한 알고리즘들이 상용되며, 일반적으로 대응점 탐색 및 광학 흐름 추정은 픽셀 단위로 일정 거리내에서 탐색한다. 하지만, Global Patch Collidar 알고리즘(“The Global Patch Collidar”, Shenlong Wang 외 4인, CVPR 2016, 이하 GPC 라 함)은 전체 픽셀에 대하여 기술자를 비교하여 높은 정확도를 제공한다. 이때 각 영상의 모든 픽셀은 기술자 정보에 대해 결정 트리로 분류되고 대응되는 영상간의 대응점을 탐색한다.

대응점 정보는 실시간 3D 복원, 증강 현실 등의 연구의 기반 정보로 데이터 처리의 속도가 중요하다. 종래의 GPC 알고리즘이 구현된 기술에서는 영상의 크기가 작은 경우에는 실시간성이 보장되지만, HD 화질 이상의 영상에서는 실시간 시스템에 사용할 수 없다는 문제점이 있다. 기존의 기술은 표 1가 같이 GPC 알고리즘 내부 연산이 순차적 연산이 주로 이루어지기 때문에 Full HD급 영상에 대해서는 대응점에 대한 정확도는 높으나 데이터 연산 속도가 굉장히 느리다는 단점이 발생하게 된다. 이는 대응점 정보를 실시간으로 처리하지 못하는 문제를 발생하게 된다.

한국등록특허공보 제 10-1853060호 한국등록특허공보 제 10-0924411호

전술한 문제점을 해결하기 위한 본 발명은 GPU를 기반으로 하여 병렬 연산 처리함으로써, 고해상도 영상들에 대해서도 실시간으로 대응점을 검출할 수 있도록 하는 결정 트리를 이용한 대응점 탐색 방법을 제공하는 것을 목적으로 한다.

전술한 목적을 달성하기 위한 본 발명의 특징에 따른 결정 트리를 이용한 대응점 탐색 방법은, (a) 영상을 입력받고, 입력 영상에 대한 채널을 검사하고, 영상 채널별로 데이터를 분리하는 단계; (b) 입력 영상내 모든 픽셀에 대하여 이미지 픽셀 패치에 대한 기술자(Descriptor)를 계산하는 단계; (c) 학습을 통해 결정 트리(Decision Forest)를 생성하기 위한 결정 트리 연산을 수행하여 각 픽셀에 대한 결정 트리 인덱스(pixel forest index)를 획득하는 단계; (d) 각 픽셀에 대해 획득된 결정 트리 인덱스들을 정렬하는 단계; (e) 결정 트리의 리프 노드에서 하나의 같은 결정 트리 인덱스를 갖는 픽셀들을 대응점으로 판단하는 단계; (f) 대응점으로 판단된 픽셀들에 대한 정보를 출력하는 단계;를 구비한다.

본 발명의 전술한 특징에 따른 대응점 탐색 방법에 있어서, 상기 대응점 탐색 방법은 GPU를 기반으로 하여 병렬 연산 처리되는 것이 바람직하다.

본 발명의 전술한 특징에 따른 대응점 탐색 방법에 있어서, 상기 (b) 단계는, 입력 영상의 행에 대하여 적분 영상을 생성하고, 생성된 행에 대한 적분 영상을 이용하여 열에 대한 적분 영상을 생성하여, 입력 영상에 대한 적분 영상을 생성하는 것이 바람직하다.

본 발명의 전술한 특징에 따른 대응점 탐색 방법에 있어서, 상기 (c) 단계에서의 결정 트리 연산은, 입력 영상의 픽셀 단위로 병렬 처리하여 각 픽셀들에 대하여 결정 트리 인덱스를 부여하는 것이 바람직하다.

본 발명의 전술한 특징에 따른 대응점 탐색 방법에 있어서, 상기 대응점 탐색 방법은 각 픽셀에 대하여, 상기 (b) 단계에서 18개의 특징점 기술자 벡터를 획득하고 상기 (c) 단계에서 5개의 결정 트리 인덱스를 획득하여, 각 픽셀에 대하여 18개의 특징점 기술자 벡터와 5개의 결정 트리 인덱스로 구성된 픽셀 데이터를 구성하는 것이 바람직하다.

본 발명의 전술한 특징에 따른 대응점 탐색 방법에 있어서, 상기 (d) 단계는, 각 픽셀에 대해 획득된 결정 트리 인덱스들을 정렬하기 위하여, 인덱스 테이블을 생성하고 각 픽셀의 결정 트리 인덱스의 순으로 결정 트리 인덱스를 저장하는 것이 바람직하다.

본 발명에 따른 대응점 탐색 방법은 GPU를 기반으로 하여 병렬 처리 연산하여 입력 영상들에 대한 대응점을 탐색함으로써, 고해상도 영상에 대해서도 실시간으로 대응점 탐색을 가능하게 한다.

도 1은 본 발명의 바람직한 실시예에 따른 결정 트리를 이용한 대응점 탐색 방법을 순차적으로 도시한 흐름도이다.
도 2는 종래의 방식에 따른 CPU를 기반으로 한 순차 연산과 본 발명에 따른 GPU를 기반으로 한 병렬 연산을 설명하기 위하여 도시한 모식도이다.
도 3의 (a)는 종래의 방법에 따른 데이터 정렬 방법이며, (b)는 본 발명에 따른 인덱스 테이블을 이용한 데이터 정렬 방법이다.
도 4의 (a)는 종래의 방식에 따라 입력 영상에 대한 CPU를 기반으로 한 대응점 탐색 결과이며, (b)는 본 발명에 따라 입력 영상에 대한 GPU를 기반으로 한 대응점 탐색 결과이다.

본 발명에 따른 결정 트리를 이용한 대응점 탐색 방법은 GPU를 기반으로 하여 병렬 처리 연산하여 입력 영상들에 대한 대응점을 탐색함으로써, 고해상도 영상에 대해서도 실시간으로 대응점 탐색을 가능케 하는 것을 특징으로 한다.

이하, 첨부된 도면을 참조하여 본 발명의 바람직한 실시예에 따른 결정트리를 이용한 대응점 탐색 방법에 대하여 구체적으로 설명한다. 본 발명에 따른 대응점 탐색 방법은 GPU를 기반으로 하여 병렬 연산 처리한 것을 특징으로 한다.

도 1은 본 발명의 바람직한 실시예에 따른 결정 트리를 이용한 대응점 탐색 방법을 순차적으로 도시한 흐름도이다.

도 1을 참조하면, 본 발명에 따른 대응점 탐색 방법은 먼저 영상들을 입력받고, 입력 영상에 대한 채널을 검사하고, 데이터 자료형을 조정하고, 영상 채널별로 데이터를 분리한다(단계 100).

도 2는 종래의 방식에 따른 CPU를 기반으로 한 순차 연산과 본 발명에 따른 GPU를 기반으로 한 병렬 연산을 설명하기 위하여 도시한 모식도이다. 도 2의 (a)는 종래의 CPU기반의 순차 연산을 설명하는 것으로서, 모든 인덱스를 순차적으로 나열하고 순차적으로 수행하며, (b)는 본 발명에 따른 GPU 기반의 병렬 연산을 설명하는 것으로서, 각 인덱스를 블록으로 나누고 이를 각 Thread로 나누어 병렬 연산하게 된다.

다음, 입력 영상내 모든 픽셀에 대하여 이미지 픽셀 패치에 대한 특징점 기술자(Descriptor)를 계산한다(단계 110). 각 픽셀에 대한 특징점 기술자 계산은 DCT 기법으로 적분 영상에 대하여 수행하여 각 픽셀에 대해 18개의 특성값을 구하게 된다.

적분 영상을 생성하는 과정은 중복되는 계산이 많기 때문에 병렬 처리 연산의 수행을 위하여 영상의 행과 열에 대한 적분을 따로 수행한다. 적분 영상을 생성하기 위하여, 수학식 1을 이용하여 먼저 행에 대한 적분 영상을 계산하며, 이렇게 계산된 행에 대한 적분 영상을 이용하여 수학식 2를 이용하여 열에 대한 적분 영상을 계산함으로써, 전체 영상에 대한 적분 영상을 완성하여 중복 계산을 최소화시키는 것이 바람직하다.

학습을 통해 결정 트리(Decision Forest)를 생성하기 위한 상기 결정 트리 연산을 수행하여 각 픽셀에 대한 결정 트리 인덱스(pixel forest index)를 획득한다(단계 120). 상기 결정 트리 연산은 픽셀 단위로 병렬 처리가 가능하고, 상기 결정 트리에 대한 연산을 통해, 각 픽셀들은 결정 트리 인덱스를 부여받게 된다. 각 픽셀 데이터는 18개의 특징점 기술자와 5개의 결정 트리 인덱스로 구성된다.

각 픽셀에 대해 획득된 결정 트리 인덱스들을 정렬한다(단계 130). 도 3은 본 발명의 바람직한 실시예에 따른 대응점 탐색 방법에 있어서, 본 발명에 따른 데이터 정렬 방법을 종래의 방법과 비교하여 설명하기 위한 모식도이다. 도 3의 (a)는 종래의 방법에 따른 데이터 정렬 방법이며, (b)는 본 발명에 따른 인덱스 테이블을 이용한 데이터 정렬 방법이다.

도 3의 (a)를 참조하면, 종래의 데이터 정렬 방법은, 결정 트리 인덱스를 기준으로 데이터를 정렬시키는데, 이때 전체 데이터의 교체가 일어나게 된다. 하지만, 도 3의 (b)를 참조하면, 본 발명에 따른 방법은 데이터 정렬의 연산량을 줄이기 위하여, 결정 트리 인덱스 테이블을 생성하고, 인덱스 테이블에 각 픽셀의 결정 트리 인덱스의 순으로 저장하여 사용함으로써, 데이터 교체없이 데이터를 정렬할 수 있게 된다.

다음, 결정 트리의 리프 노드에서 하나의 같은 결정 트리 인덱스를 갖는 픽셀들을 대응점으로 판단한다(단계 140). 대응점으로 판단된 픽셀들에 대한 정보를 출력한다(단계 150).

전술한 구성을 갖는 본 발명에 따른 대응점 탐색 방법에 의한 두 영상간의 대응점 탐색에 대한 연산 속도는 표 2와 같다. 테스트한 영상의 크기는 1080×1920 이다.

표 2는 GPC 알고리즘을 종래의 CPU 기반의 순차 연산과 본 발명의 GPU 기반의 병렬 연산으로 실험을 진행하여 연산 속도를 비교한 것이다.

도 4의 (a)는 종래의 방식에 따라 입력 영상에 대한 CPU를 기반으로 한 대응점 탐색 결과이며, (b)는 본 발명에 따라 입력 영상에 대한 GPU를 기반으로 한 대응점 탐색 결과이다. 도 4를 참조하면, 정확도 측면에서는 본 발명과 종래의 방법과 같은 결과를 보이며, 연산 속도는 표 2를 통해 약 7배 더 빠름을 알 수 있다. 본 발명은, 단순한 픽셀 정보를 이용한 연산의 경우에 병렬 처리로 연산 속도를 극대화시켰으며, 픽셀 간 정보를 순차적으로 처리하는 연산의 경우에는 병렬 처리 연산으로 인한 연산 속도 이득의 한계를 확인할 수 있다.

전술한 구성을 갖는 본 발명에 의해 다시점 영상의 3D 복원 및 실시간 4D 복원을 비롯하여 다양하게 개발되고 있는 증강 현실 및 가상 현실 환경에서의 대응점 정보를 실시간 시스템에서 획득할 수 있게 된다. 특히, 본 발명은, 이미지 패치 기반의 학습된 Random Forest 를 이용한 GPC 알고리즘을 GPU 기반의 병렬 처리 시스템으로 구현한다.

이상에서 본 발명에 대하여 그 바람직한 실시예를 중심으로 설명하였으나, 이는 단지 예시일 뿐 본 발명을 한정하는 것이 아니며, 본 발명이 속하는 분야의 통상의 지식을 가진 자라면 본 발명의 본질적인 특성을 벗어나지 않는 범위에서 이상에 예시되지 않은 여러 가지의 변형과 응용이 가능함을 알 수 있을 것이다. 그리고, 이러한 변형과 응용에 관계된 차이점들은 첨부된 청구 범위에서 규정하는 본 발명의 범위에 포함되는 것으로 해석되어야 할 것이다.

Claims (6)

1. (a) 영상을 입력받고, 입력 영상에 대한 채널을 검사하고, 영상 채널별로 데이터를 분리하는 단계;
   (b)입력 영상에 대한 적분 영상을 생성하고, 적분 영상을 이용하여 입력 영상내 모든 픽셀에 대하여 이미지 픽셀 패치에 대한 기술자(Descriptor)를 계산하는 단계;
   (c) 학습을 통해 결정 트리(Decision Forest)를 생성하기 위한 결정 트리 연산을 수행하여, 각 픽셀에 대하여 결정 트리 인덱스(pixel forest index)를 획득하는 단계;
   (d) 각 픽셀에 대해 획득된 결정 트리 인덱스들을 정렬하는 단계;
   (e) 결정 트리의 리프 노드에서 하나의 같은 결정 트리 인덱스를 갖는 픽셀들을 대응점으로 판단하는 단계; 및
   (f) 대응점으로 판단된 픽셀들에 대한 정보를 출력하는 단계;를 구비하고,
   상기 (b) 단계는, 입력 영상의 행에 대하여 적분 영상을 생성하고, 생성된 행에 대한 적분 영상을 이용하여 열에 대한 적분 영상을 생성하여, 입력 영상에 대한 적분 영상을 생성하는 것을 특징으로 하며,
   상기 (c) 단계에서의 결정 트리 연산은, 입력 영상의 픽셀 단위로 병렬 처리하여 각 픽셀들에 대하여 결정 트리의 인덱스를 부여하는 것을 특징으로 하며,
   각 픽셀에 대하여 (b) 단계에서 18개의 특징점 기술자 벡터를 획득하고 상기 (c) 단계에서 5개의 결정 트리 인덱스를 획득하여, 18개의 특징점 기술자 벡터와 5개의 결정 트리 인덱스로 구성된 픽셀 데이터를 구성하는 것을 특징으로 하는 결정 트리를 이용한 대응점 탐색 방법.
2. 제1항에 있어서, 상기 대응점 탐색 방법은 GPU를 기반으로 하여 병렬 연산 처리되는 것을 특징으로 하는 결정 트리를 이용한 대응점 탐색 방법.
3. 삭제
4. 삭제
5. 삭제
6. 제1항에 있어서, 상기 (d) 단계는
   각 픽셀에 대해 획득된 결정 트리 인덱스들을 정렬하기 위하여, 인덱스 테이블을 생성하고 각 픽셀의 결정 트리 인덱스의 순으로 결정 트리 인덱스를 저장하는 것을 특징으로 하는 결정 트리를 이용한 대응점 탐색 방법.