[ 번역 ] Terrain Synthesis from Digital Elevation Models

원문 : http://www.howardzzh.com/research/terrain/

주의 : 허락받고 번역한 것이 아니므로 언제든 내려갈 수 있습니다.

주의 : 번역이 개판이므로 이상하면 원문을 참조하십시오.

주의 : "feature" 를 "특징"이라고 번역했는데 뭔가 어색할 때가 있습니다. 그냥 마음속으로 "특징"을 "feature" 라고 읽으시기 바랍니다.

주의 : Appendix 는 번역하지 않았습니다. 원문을 참조하세요.

 

Terrain Synthesis from Digital Elevation Models

 

Howard Zhou, Jie Sun, Greg Turk, Member, IEEE, and James M. Rehg, Member, IEEE

 

Abstract -- 이 논문에서 우리는 지형 합성을 위한 예제 기반( example-based, 역주 : 이 "예제" 라는 표현은 "본보기", "기준" 등의 의미로 사용되는 것 같습니다. 그런 느낌으로 이해해 주시기 바랍니다. ) 시스템을 제공합니다. 우리의 접근법에서 샘플 지형으로부터의 ( 하이트 필드( height field )로 표현되는 ) 패치( patch )들은 새로운 지형을 생성하는데 사용됩니다. 이러한 합성은 사용자가 스케치한 특징( feature ) 맵으로부터 생성되는데, 그 맵은 결과로 나오는 합성된 지형에서 어느 부분이 특징적인지를 지정하게 됩니다. 우리의 시스템은 큰 규모의 곡선적인 특징( 산등성이와 골짜기 )들을 강조하게 됩니다. 왜냐하면 그러한 특징들이 대부분의 지형에서 주요한 가시적 요소들이기 때문입니다. 예제 하이트 필드와 사용자의 스케치 맵은 모두 기하영역의 기법을 사용해 분석됩니다. 시스템은 예제 데이터로부터 사용자의 스케치에서 찾을 수 있는 특징과 일치하는 패치를 찾습니다. 그 패치들은 그래프 컷( graph cut )과 푸아송 편집( Poisson editing, 역주 : [ poisson image editing ] 참조 )을 사용해 서로 합쳐집니다. 패치들이 합성된 지형에 배치되는 순서는 특징 트리에 대한 넓이 우선 탐색( breadth-first traversal, 역주 : [ Data Structure - Breadth First Traversal ] 참조 )에 의해서 결정됩니다. 그리고 이는 표준 래스터-스캔 배치( raster-scan placement ) 순서에 있어서 개선된 결과를 산출하게 됩니다.

 

Index Terms - Terrain synthesis, Digital Elevation Models, terrain analysis, texture synthesis.

 

1. INTRODUCTION

 

 

지형 함성을 가능하게 해 주는 수많은 애플리케이션들이 존재합니다. 그리고 보통은 그 ㅈ지형은 씬에서 주요 가시 요소가 됩니다. 그런 애플리케이션은 풍경( landscape ) 디자인,  비행 시뮬레이션, 응급 대응 훈련, 전장 시뮬레이션, 장편 극영화 특수 효과, 컴퓨터 게임들을 포함하고 있습니다. 수년 동안 그래픽스 연구자들은 합성 지형을 생성하기 위한 효율적인 기법들을 개발하는 데 있어 주목할 만한 발전을 해 왔습니다. 이전의 지형 합성은 프랙탈( fractal ) 모델과 물리적인 침식( erosion ) 모델을 사용해 사실적으로 보이는 지형을 만드는데 초점을 맞춰 왔습니다.

 

컴퓨팅 파워와 지형 가시화 기법에 대한 개발 수준이 급격하게 성장하면서, 좀 더 사실적인 지형에 대한 요구가 꽤 증가되어 왔습니다. 게다가 지형 모델링 애플리케이션의  사용자들은 새로운 지형을 창조하는 데 있어 더 많은 제어권을 원하게 되었습니다. 그러나 현재 지형 합성 기법들은 몇 가지 제약을 가지고 있습니다. 먼저 이 기법들은 사용자에게 원하는 지형의 특징을 배치하는 데 있어서 적은 제어권을 제공하거나 아예 제공하고 있지 않습니다. 다음으로 이러한 기법들에서 제어 파라미터를 사용하는 것은 그랜드 캐년( Grand Canyon )과 같은 기하학적 특징을 가진 지형과 같은 원하는 스타일의 지형을 생성하기 어렵게 만듭니다.

 

그림 2a 와 2b 는 좀 유명한 상업 소프트웨어에 의해 제공되는 프랙탈 및 침식 지형의 예를 보여주고 있습니다. 그것들은 흑백 고도 맵( intensity-coded elevation map )처럼 출력되고 있습니다. 이러한 스타일의 지형들은 그림 2c 와 2d 에 나와 있는 자연적인 지형들과는 매우 다릅니다.

 

우리는 새로운 예제 기반 지형 합성 기법을 제시하는데, 이는 지형 특징 배치와 지형 스타일에 대해 사용자가 직관적으로 제어할 수 있어야 하는 필요성에 대해 다룹니다. 우리의 기법은 예제 기반 텍스쳐 합성으로부터 패치를 매칭하고 배치하는 하는 기술을 이용합니다. 우리 접근법에서 사용자가 스케치한 지형 특징 맵( 스케치 맵이라 불림 )과 실제 지형 데이터( 예제 하이트 필드라 불림 )는 원하는 지형의 스타일을 포함하고 있습니다. 예제 하이트 필드는 디지털 고도 모델( Digital Elevation Map, DEM ) 형식입니다. 이는 US Geological Survey 에서 온라인으로 이용할 수 있습니다. 다음으로 우리 시스템은 자동적으로 실제 지형 데이터의 가시적 스타일을 보존하면서 스케치 맵의 특징 제약들을 만족시켜주는 새로운 하이트 필드를 생성하게 됩니다. 우리 접근법을 통한 합성 결과는 그림 1 에 나와 있습니다.

 

그림 1. Flathead National Forest Mountain Range( 위쪽 이미지 ) 와 Grand Canyon( 아래쪽 이미지 )의 DEM 을 사용해 합성된 지형들.

 

그림 2. 현재의 기법들로 생성된 지형의 예제들. ( a ) Terragen 에 의해 1024 x 1025 해상도로 생성된 프랙탈 지형( ridged multi-Perlin ). ( b ) Bryce 에 의해 1024 x 1024 로 생성된 침식 지형. 각각은 두 개의 실제 고도 맵들과 비교됨: ( c ) 몬타나의 Flathead National Forest 산맥의 1/3 각초( arcsecond )( 10 m ) DEM. ( d ) 켄터키의 Vernon 산의 1/3 각초( 10 m ) DEM. ( DEMs courtesy of the US Geological Survey ).

 

스케치 맵은 사용자에게 합성 과정을 제어하는 데 있어 쉽고 직관적인 방법을 제공합니다. 각 맵은 그림 10a 의 중앙에 있는 이미지에서의 분기점( bifurcation point )과 같은 중요한 지형 특징의 위치를 지정하게 됩니다. 사실 브러쉬의 너비와 픽셀 강도는 별로 중요치 않습니다. 왜냐하면 그것들은 더 어두운 픽셀은 더 낮은 고도를 가리키고 더 밝은 픽셀은 더 높은 고도를 가리킨다는 단순한 원칙을 따르기 때문입니다. 이 연구에서 우리의 목표는 가시적으로 주목할만한 지형을 생성하는 것입니다. 우리는 합성된 지형이 기하학적으로 정확한가에 대한 개별적인 이슈에 대해서는 다루지 않을 것입니다.

 

우리 알고리즘의 시작점은 스케치 맵과 예제 하이트 필드에서 중요한 지형 특징을 식별하는 것입니다. 우리 시스템은 큰 규모의 곡선적인 특징들에 집중하는데, 그런 것들로는 강, 계곡, 산등성이같은 것들이 있습니다. 왜냐하면 그러한 것들이 보통 대규모 지형에서는 ( 그림 2c 와 2d 에서 보이는 것처럼 ) 중요한 가시적 요소이기 때문입니다. 스케치 맵의 지형구조와 예제 하이트 필드에의 지형구조는 보통 서로 다르며 공간적으로 큰 큐모에서 매칭시키는 것은 거의 정확하지 않습니다. 그러나 우리는 적은 규모에서 볼 때는 그렇지 않다는 것을 발견했습니다. 계곡의 분기 영역이나 직선 영역과 같은  공통적인 지형 특징들은 양쪽 맵에서 모두 찾아볼 수 있습니다. 그러므로, 우리 알고리즘은 스케치 맵을 작은 패치 영역으로 분할하고 예제 하이트 필드에서 구조적인 특징이 일치하는 부분을 검색합니다.

 

스케치 맵에서 구조 정보를 추출하는 것은 그것의 단순함 때문에 직관적입니다. 반대로 실제 지형 하이트 필드에서 산등성이나 계곡과 같은 구조 정보를 추출하는 것은 어려울 수 있습니다. 여기에서 우리는 기하 영역의 연구를 이요합니다. 특히 우리는 하이트 필드로부터 산등성이 및 계곡의 축과 같은 구조 정보를 추출하기 위해 Chan et al. [1] 에 의해 개발된 윤곽 인식( Profile recognition ) 및 폴리곤 분열 알고리즘( Polygon breaking Algorithm, PPA )을 사용합니다.

 

일단 중요한 구조적 지형 특징이 추출되고 나면, 우리 알고리즘은 다음과 같은 단계들을 밝게 됩니다: 첫 번째로 스케치 맵과 예제 하이트 필드에서 패치 영역을 매칭하고 정렬하기 위해서 곡선적 지형 특징들이 제약으로서 사용됩니다. 두 번째로 이러한 특징들은 이웃 패치 영역 사이의 경계가 겹치는 곳을 따라 매칭을 하기 위한 제약으로 사용됩니다. 패치는 가중치화된 점수 결합( weighted combination of scores )을 기반으로 선택되는데, 그 점수는 패치와 그것의 이웃들 사이의 적합도( goodness-of-fit ) 및 요청된 패치의 변형량( amount of deformation )을 가늠하게 됩니다. 패치 배치의 순서는 사용자 스케치 맵으로부터 생성된 특징 트리에 대한 넓이 우선 탐색에 의해 결정됩니다. 각 패치는 가시적 분절을 최소화하기 위해서 graph-cut seam finding 과 Poisson seam removal 의 조합을 사용해 출력 맵에 배치됩니다.

 

이 논문은 다음과 같은 기법들에 공헌을 했습니다:

 

• 합성된 지형 특징들을 스케치 기반으로 지정해서 사용자가 함성 결과 전반을 직관적으로 제어할 수 있도록 해 주는 기법.
• 큰 규모의 곡선적 지형 특징들을 매칭하고 배치하기 위한 특징 기반 접근법. 이는 큰 지형 데이터베이스들을 효율적으로 만들 수 있도록 해 줬으며, 합성 과정에서 중요한 가시적 요소들을 보존해 줍니다.
• 표준 래스터-스캔 오더링의 대안으로서 사용되는 트리기반 오더링( tree-ordered ) 패치 배치 알고리즘. 이는 사용자 입력과 매칭되는 지형 구조를 더욱 신뢰성있게 재구축하는 결과를 산출합니다.
• 서로 다른 유형의 지형들 사이에서의 전이를 합성하고 여러 개의 DEM 들을 사용해서 단일한 합성된 출력물을 만드는 기능.

 

우리는 예전의 텍스쳐 합성 기법들로부터 이 연구에 대한 영감을 얻었습니다. 그 연구들에 대해 다음 섹션에서 리뷰하도록 하겠습니다.

 

2. RELATED WORK

 

합성된 지형을 생성하는 두 개의 주요 접근법이 존재합니다: 프랙탈 풍경 모델링과 물리적 침식 시뮬레이션. 프랙탈 풍경 모델링은 Mandelbrot 의 개척적인 연구[2] 로 거슬러 올라 갑니다. 그 이후로 다양한 확률적( stochastic ) 하위분할 기술들이 소개되었습니다. Fournier et al. [3] 은 프랙탈 서피스를 생성하기 위해 random midpoint displacement 기법을 소개했습니다. Voss [4] 는 fractional Brownian surfce 에 successive random displacement 를 추가했습니다. Miller [5] 는 프랙탈 지형을 생성하기 위한 square-square 하위분할 스키마와 하이트 필드를 렌더링하기 위한 병렬 처리 알고리즘을 제안했습니다. Lewis [6] 는 일반화된 확률적 하위분할을 제안했습니다. Szeliski 와 Terzopoulos [7] 는 결정론적 스플라인( deterministic spline )과 확률적 프랙탈들을 제약있는 프랙탈들로 결합함으로써 사용자의 제어권 문제를 다뤘습니다. 최근의 프랙탈 기반 접근법은 [8] 과 [9] 에 소개되어 있습니다.

 

물리적 침식 시뮬레이션은 풍경 공식에 대한 모델과 지형학( geomorphologic ) 커뮤니티로부터의 하천 침식( stream erosion )에 기반해 지형 디테일( detail )을 합성하는 것에 대한 대안적 접근법입니다. 그것은 보통 거친 하이트 필드가 생성된 후의 개선( refinement ) 단계로서 사용되었습니다. Kelly et al. [10] 은 처음으로 하도망( stream netowrk )에 의한 침식을 시뮬레이션 함으로써 자연스런 지형을 근사계산하는 기법을 소개했습니다. 나중에 Musgrave et al. [11] 은 프랙탈 모델링 접근법과 침식 시뮬레이션 접근법을 하나의 프레임웤으로 결합했습니다. [12], [13], [14], [15], [16] 에 예시된 최근의 물리적 침식 기술들은 물리적 모델링 관점과 계산적 효율성을 모두 증진시키는데 초첨을 맞춰왔습니다. 적절히 튜닝된 파라미터들을 사용함으로써 이 기법들은 사실적으로 보이는 지형들을 생성할 수 있습니다.

 

프랙탈 기술과 물리적 침식 기술들은 모두 절차적인( procedural ) 개선을 통해 지형 디테일을 추가합니다. 이는 보통 비직관적인 파라미터 튜닝을 포함하게 됩니다. 최근에 Brosz et al [17] 은 현존하는 DEM 데이터로부터 고해상도 지형 디테일을 추출하고 mutiresolution analysis 를 통해 그것을 저해상도 지형에 적용하려고 시도했습니다. 경험적으로 볼 때 그들의 기법은 꽤 세부화된 소스 및 타깃 지형을 모두 요구하며, 사용자가 임의의 지형을 생성할 수 있는 자유도를 제공하지 않습니다.

 

사용자에게 합성된 지형 전반에 대한 더욱 직관적인 제어를 제공하기 위해서, 이미지 기반 대안들이 Lewis [18] 및 Perlin 과 Velho [19] 에 의해 제안되었습니다. 이 작업들에서, 지형은 텍스쳐 유형으로서 사용되며( viewed ) 사용자 제어는 텍스쳐에 대한 직접적인 조작을 통해서 제공되었습니다. 그러나 사용자가 사실적이고 자연스러운 하이트 필드를 손으로 그리는 것은 너무 어렵기 때문에, 이 기법들은 보통 사실적인 디테일이 부족해진다는 문제점을 겪게 되었습니다.

 

2.1. Commercial Software

 

우리는 우리의 기법과 비슷한 접근법을 사용하는 지형 합성을 위한 상업 소프트웨어를 발견하지 못했습니다. 간단히 네 개의 주요 상업 시스템들을 리뷰하겠습니다; Mojoworld, Terragen, World Machine, Bryce. 이것들은 최신 기법을 대표합니다. Mojoworld 와 Terragen 은 둘 다 프랙탈 합성 엔진을 가지고 있는데, 그 엔진은 지형을 절차적으로 생성하니다. 그 결과는 매우 조밀( compact )합니다. 왜냐하면 그것들은 그때그때( on the fly ) 생성되기 때문입니다. 반면에 WorldMachine 은 사실적으로 느껴지는 지형을 합성하기 위해서 그것의 절차적 모양( shape )과 노이즈 생성기의 상단에 기하적 침식을 제공합니다.이런 모든 시스템들에서 합성 결과에 대한 제어는 생성 과정에서 전역 파라미터들을 변경함으로써 가능합니다. 그러나 독특하고 사실적인 지형 타입을 생성하기 위해서 이러한 파라미터들을 설정하는 것은 어렵습니다. 더우기 이 시스템들은 주요 지형 특징을 사용자가 지정해서 배치하는 것을 지원하지 않습니다. Bryce 는 프랙탈 합성 엔진과 침식 합성 엔진을 모두 지원하면서 페인팅 접근 방식을 사용해 사용자가 하이트 필드를 직접적으로 수정할 수 있도록 합니다( 기본적으로 [18] 의 기법에 프랙탈 노이즈를 추가한 것 ). 그림 2c 와 2d 는 그런 상업 시스템들에 의해 생성된 예제 지형들입니다. 그러나 이러한 제품들 중의 어떤 것도 Grand Canyon 스타일과 같은 특정 스타일로 지형을 합성하는 것이 불가능합니다.

 

2.2. Texture Synthesis

 

이미지 기반 텍스쳐 합성은 주어진 예제 이미지로부터 픽셀을 그림으로써 임의의 큰 텍스쳐 패치를 생성하는 절차를 의미합니다. 지난 몇 십년 동안, 합성된 텍스쳐의 품질은 2D 와 3D 영역에서 지속적으로 발전해 왔습니다. 이는 nonparametric neighborhood-based 기법인 [21], [22], [23] 에 대한 픽셀 기반 기법들을 발전시킴으로써 이루어졌습니다 [20]. [24], [25], [26], [27], [28], [29], [30], [31] 에서 예시된 가장 최근의 패치 기반 기술들은 두 개의 공통적인 단계를 가지고 있습니다: 1) 칸텍스트( context ) 영역과 가장 유사한 이웃들을 단순한 텍스쳐에서 검색합니다. 그리고 2) ( 부분적으로 ) 합성된 출력 텍스쳐에 패치나 픽셀을 결합( merge )합니다. Dynamic programming [24] 와 graph cuts [26] 가 패치 결합 단계를 최적화하기 위해 사용되었습니다. 우리는 지형 데이터의 유일한 특징을 다루는 검색-결합 전략을 사용합니다.

 

최근에 Zhang et al. [32] 는 임의의 서피스에서 다양한 텍스쳐를 점진적으로( progressively ) 합성하기 위해 특징 기반 왜곡( feature-based warping ) 기법과 블렌딩( blending ) 기법을 소개했습니다. 그들의 연구에서 특징 텍스톤 마스크( feature texton mask )는 수작업을 통해 추출됩니다. Wu 와 Yu [27] 는 패치 기반 텍스쳐 합성을 이끌어 내기 위해서 고수준 특징으로서의 입력 텍스쳐에서 추출된 엣지( edge )를 사용합니다. 우리는 이 앞선 연구들을 두 가지 방식으로 발전시킵니다. 첫 번째로 우리는 원하는 지형 특징을 사용자가 스케칭하는 것을 지원하기 위해서 곡선적 특징들을 사용하며 큰 지형 데이터 셋에서 패치를 매칭하기 위한 효율적인 검색 방식을 사용합니다. 두 번째로 다양한 범위의 스타일로 된 큰 DEM 으로부터 산등성이와 계곡을 신뢰성있게 추출할 수 있는 특징 분석 기술을 소개합니다. 우리는 표준 엣지 검색 기법들이 이 작업을 위해서는 부적절하다는 것에 대해서 설명할 것입니다.

 

 

Hertzmann et al [25] 는 이미지 유추( analogies ) 프레임웤을 소개했습니다. 이는 texture-by-numbers 접근법을 통해 지형 이미지를 합성하는데 사용될 수 있습니다. 이 연구는 새로운 지형 하이트 필드를 직접적으로 합성하지 않습니다. 하이트 필드 합성을 위한 그 애플리케이션은 지형 스타일을 특화하는 산등성이나 계곡과 같은 확장된 구조를 보존하는 지역적 이웃 매칭( local-neighborhood matching ) 접근법을 보장하기 어렵습니다. [30] 은 drag-and-drop features 와 synthesis magnification 을 포함하는 GPU 기반 텍스쳐 합성 기법을 제시했습니다. 이 기법들은 지형 하이트 맵 상에서 산을 재배치하는데 사용되었습니다. 이 연구와는 대조적으로 우리의 관심은 원하는 사용자 스케치를 사용해서 확장된 지형 특징을 매칭함으로써 특정 스타일로 온전한 지형 이미지를 자동적으로 생성하는 데 있습니다. 그러므로 우리는 자동 특징 추출 및 매칭을 완전하게 지원합니다.

 

우리의 지형 합성을 위한 예제 기반 접근법이 최근의 패치 기반 기법들의 성공에 영감을 받았기는 하지만, 지형 합성은 하이트 필드 상에서 단순히 텍스쳐 합성을 하는 것이 아닙니다. 지형 생성 문제는 세 가지 주요 방식에서 전통적인 텍스쳐 합성과는 구분될 수 있습니다. 첫째로 광범위한 지형 유형들이 ( 산등성이 및 계곡과 같은 ) 전역 특징들의 조합에 의해서 특화될 수 있는데, 이 특징들은 입력 지형 맵으로부터 신뢰성있게 추출될 수 있습니다. 반면에 범용 이미지 텍스쳐들을 위해서는 그러한 수비게 식별가능한 전역 특징이 존재하지 않습니다. 둘째로 다양한 범위의 애플리케이션에 있어 유용하기 위해서는 지형 합성은 반드시 전역적으로 제어되어야 합니다. 그리고 ( 보통 기가픽셀 이상인 ) 큰 지형 데이터 셋은 반드시 사용자의 제약을 만족시킬 수 있도록 검색되어야 합니다. 이는 작은 입력 텍스쳐 패치를 같은 지역적 강도( local intensity ) 구조를 가지고 있는 더 큰 출력 이미지로 "키우는" 기본적인 텍스쳐 합성 문제와는 대조되는 부분입니다. 셋째로 텍스쳐 합성을 위한 많은 최근의 cut-and-merge 기술들은 이미지 텍스쳐들이 많은 자연스러운 분계선들( boundaries )을 포함한다는 사실을 이용한다는 것입니다. 그 분계선들은 텍스쳐 엘리먼트들을 결합하는 곳을 따라서 좋은 경계( good seam )를 제공하게 됩니다. 반면에 지형 데이터는 자연스러운 경계가 존재하지 않습니다. 더우기 두 개의 인접한 패치들에서 하이트 필드 사이에 존재하는 불일치는 즉각적으로 눈에 띄게 될 것입니다. 높이 차를 제거하기 위해서 블러링( blurring )을 사용하는 것은 매우 잘 보이는 아티팩트를 산출하게 됩니다. 우리는, 최근의 graph-cut 기법과 Poisson seam removal 기법을 결합해서, 지형 패치를 결합( merge )하는 문제를 다루는 방법을 보여 줄 것입니다.

 

3. FEATURE EXTRACTION

 

이섹션에서 우리는 예제 하이트 필드와 사용자의 스케치 맵으로부터 지형 특징을 추출하기 위한 기법에 대해서 기술할 것입니다. 우리는 지형 특징 이라는 개념을 강, 계곡, 산등성이와 같은 대규모의 곡선적 특징들을 가리키기 위해 사용합니다. 그러한 지형 특징들은 지형의 전체적인 외형( layout )을 특화합니다. 그림 3a 는 예제 하이트 필드를 보여 주는데, 이는 Grand Canyon 의 일부를 포함하며 쉐이딩된 입체 지도( shaded relief map )으로 표시됩니다. 이 예제는 큰 규모의 곡선적 구조( 본류 강바닥 )과 풍부한 이차 구조( 협곡의 가파른 면 및 다른 특징들 )을 모두 보여 줍니다. 우리의 목적은 주요 구조를 원하는 스케치 모양과 매칭시키는 것인데, 이 때 이 데이터 내에 표현된 풍부한 디테일들이 보존되어야 합니다.

 

그림 3. 특징 추출 메서드의 비교. ( a )  쉐이딩된 입체 지도로 출력된 Grand Canyon 하이트 필드. ( b ) Canny 엣지 검출기에 의해 추출된 특징. ( c ) PPA 에 의해 검출된 특징.

 

지형 특징이 엣지 검출을 통해 식별될 수도 있을 것 같습니다. 그러나 더 정밀하게 검토해 보면 복잡한 지형 데이터에 엣지 검출을 적용하는 것에는 몇 가지 문제가 있습니다. 먼저 지형 특징들은 하이트 필드에 대한 지역적 극값들( local extrema )에 의해 특화되는 반면, 엣지 검출 기법은 이미지의 극대값( maximal derivatives )에 기반하고 있습니다( 역주 : [ Application of Derivatives ] 참조 ). 결과적으로 지형 데이터에 대한 엣지 검출 애플리케이션을 사용하면 그것은 지역 높이값의 다양함 때문에 그림 3b 에서 볼 수 있는 것처럼 겉으로 보기에는 그럴싸한 특징들을 산출합니다^[각주:1]. 또한 지형 데이터는 특화된 분기 구조를 가지는데 이는 표준 엣지 검출 알고리즘에 의해 정확하게 다뤄질 수가 없습니다( 예를 들어, 그림 3b 의 오른쪽 아래 코너를 확인해 보십시오 ).

 

우리는 대규모 지형 특징들을 식별하기 위해서 지형학 문헌에 의존합니다. 특히 우리 작업을 위해 Chang et al. [1] 에 의해 개발된 PPA 를 받아 들였습니다. 우리는 이 섹션에서 그 기법에 대해 간단히 요약할 것이며 세부 사항에 대해서 알고자 하는 독자들은 그들의 논문을 읽어 보시기 바랍니다.

 

그림 4. Chang 의 PPA. ( a ) 외곽선 인식( profile recognition ). ( b ) 타깃 연결( target connection ). ( c ) 폴리곤 분열( polygon breaking ). ( d ) 분기 제거( branch reduction ).

 

 

PPA 는 산등성이나 계곡을 추출할 수 있습니다. 여기에서 우리는 산등성이 검색에 대해서만 다룰 것입니다. 이를 적절히 수정하면 계곡도 검색할 수 있습니다. 먼저 각 그리드 포인트( 하이트 필드의 픽셀 )를 방문해서 그것이 산등성이가 될 수 있는 것인지를 판단합니다. 여덟개의 바깥쪽으로 향하는 패스에서 그리드 포인트들이 검사됩니다( 그림 4a 에서 노란 점들 ). 그리고 이 패스들을 따라가다가, 현재 점의 높이에서 중앙 포인트의 높이를 뺐을 때 문턱값^[각주:2]보다 더 아래로 떨어지면( 역주 : 더 큰 차이가 나면 ), 중앙 포인트를 후보로 마킹합니다. 이러한 모든 후보들은 다른 인접 후보들과 세그먼트로 연결됩니다( 그림 4b 의 붉은 원 ). 한 세그먼트가 다른 세그먼트를 가로지르면, 더 낮은 고도를 가진 세그먼트가 취소됩니다( 그림 4b 에서 점선으로 된 세그먼트들 ). 그리고 나서 닫힌 폴리곤에 대해서 가장 중요하지 않은 세그먼트들( 그림 4c 에 보이는 것처럼 가장 낮은 높이를 가지는 남은 세그먼트 )을 반복적으로 제거함으로써 폴리곤들이 모수석 라인( 역주 : 잔가지가 많은 나무 모양 라인 ) 패턴으로 분열됩니다. 이 처리는 더 이상 닫힌 폴리곤이 없을 때까지 계속됩니다. 폴리곤 분열 처리가 끝나면, 더 짧은 가지들이 제거됩니다( 그림 4d 에서 점선으로 된 세그먼트 ).

 

예제 지형에 대한 PPA 의 출력이 그림 3c 에 나와 있습니다( 역주 : 왜 ridge 를 검색한다고 하면서 valley 를 검색했는지... ). 계곡의 축들은 하이트 필드에서 중요한 곡선적 특징들을 인간이 인지하는 것과 일치한다는 데 주목하십시오. 우리 시스템은 PPA 를 사용해서 예제 하이트 필드와 사용자 스케치 맵의 특징들을 식별하게 됩니다. 스케치 맵의 단색값들은 고도 값으로 취급됩니다. PPA 의 출력은 산등성이나 계곡을 따라가는 긴 체인( chain )을 형성하는 연결된 라인 세그먼트의 집합입니다. 이 세그먼트 체인들은 사용자의 스케치와 주어진 하이트 필드의 영역 사이에서 특징 매칭을 위한 기저입니다. 세그먼트 체인이 식별되고 나면, 그것들은 두 개의 특징 유형을 형성하기 위해서 분석될 것입니다: 고립된( isolated ) 특징과 곡선적인 ( 패스 ) 특징. 고립된 특징 은 분기점이거나 끝점입니다. 곡선적 특징 은 고립된 특징들을 잇는 긴 세그먼트 체인입니다.

 

PPA 의 핵심 속성은 ( 일반적으로 숲인, 역주 : 숲은 연결이 끝어진 비순환 그래프를 의미 ) 트리를 형성하는 특징을 추출하는 것입니다. 왜냐하면 모든 닫힌 폴리곤들은 분석 절차에서 분열되기 때문입니다. 이 속성은 합성을 하는 동안 패치의 배치 순서를 결정하기 위해서 트리 순회를 사용할 수 있도록 해 줍니다. 이에 대해서 다음 섹션에 다룰 것입니다.

 

4. FEATURE-BASED PATCH MATCHING AND PLACEMENT

 

우리의 합성 프로세스는 예제 하이트 필드로부터 패치를 추출함으로써 새로운 하이트 필드를 만들고, 그것을 사용자 스케치에 의해 표현된 하이트 필드 출력에 배치합니다. 보통 패치 크기는 80 x 80 픽셀입니다( 이는 예제 지형 데이터의 스케일과 사용자가 원하는 결과의 디테일에 의해 결정됩니다 ). 패치 선택과 배치는 두 단계로 이루어집니다: feature patch matching 및 placment 와 nonfeature patch placement 입니다.

 

그림 5. 각 feature 유형에 대한 지형 패치들의 예. ( a ), ( b ), ( c ) 는 각각 분기점 패치, 끝점 패치, 경로 패치입니다. ( d ), ( e ), ( f ) 는 feature 추출 이후의 관련 패치들입니다. 경계 색상은 그림 6b 에서의 feature 유형을 의미합니다.

 

그림 6. 패치 배치 순서를 설명. ( a ) 예제 스케치 맵. ( b ) PPA 분석에 의해 반환된 트리 구조. 분기점 feature 와 끝점 feature 는 경로 feature 와 연결됩니다. ( c ) 루트 패치가 먼저 배치됩니다. ( d ) 너비 우선 탐색은 부가적인 패치들에 대한 배치를 돕습니다. ( e ) 트리 탐색이 완료되면, nonfeature 패치들을 배치하기 시작합니다. ( f ) 최종 결과입니다.

 

 

첫 번째 단계인 feature matching 및 placement 는 스케치 맵의 분기점( branch point )과 끝점( endpoint )인 isolated feature 와 curvilinear feature( path ) 인 nonisolated feature 를 모두 배치합니다. 그림 5 에서는 이러한 유형의 feature 들의 예를 보여 줍니다. 이러한 feature 들과 일치하는 패치를 찾고 이 패치들을 출력 하이트 필드에 배치합니다.

 

만약 우리가 PPA 로부터 추출한 isolated feature 들을 노드로 취급하고 curvilinear feature( path ) 들은 그래프의 edge 로 취급한다면, 이 그래프는 비순환( acyclic )임을 보장받을 수 있습니다. 우리 알고리즘은 너비 우선 검색 순서를 사용해 패치 영역들을 일치시키고 정렬시킵니다. 먼저 isolated feature( 만약 제공된다면 일반적으로 브랜치 )들을 루트로 선택합니다. 그리고 나서 그래프에서 한 번에 하나의 edge 를 탐색해 내려가는 데 모든 edge 들이 루트로부터 이어질 때까지 계속합니다. 이 프로세스는 그림 6c, 6d, 6e 에 설명되어 있습니다. 이는 전통적인 텍스쳐 합성 기법과는 좀 다르다는 것에 주의해야 합니다. 전통적인 기법들은 rigid patch placement order( 예를 들어 왼쪽에서 오른쪽, 위에서 아래 )를 따릅니다.

 

마지막으로, 하이트 필드에서 아직 채워지지 않은 모든 영역들은 어떤 명확한 feature 도 포함하고 있지 않은 입력으로부터의 영역을 사용해서 채워집니다. 최종 결과는 그림 6f 에 나와 있습니다. 두 가지 단계들은 모두 배치를 위해 몇 가지 후보 패치들을 고려해야 합니다. 그리고 사용하기 위해 선택된 패치는 적어도 사용자의 스케치와 어울리는 것이어야 하며 이미 배치된 패치들과 어울려야 합니다( 패치 배치는 출력 하이트 필드에 침착되어야 할( deposited ) 픽셀을 선택하기 위해서 graph-cut 알고리즘을 실행하며, 이에 대해서는 섹션 5.1 에서 설명할 것입니다 ). 섹션 4.1 과 4.2 에서는 매칭 및 배치 연산에 대해서 좀 더 세부적으로 설명할 것입니다.

 

4.1. Feature Patch Matching and Placment

 

위에서 설명했듯이 사용자 스케치의 isolated feature 들은 세그먼트 그래프에서 branch point 이거나 endpoint 입니다. 그림 6b 는 세 개의 분기점와 5 개의 끝점을 가집니다. 시스템은 사용자의 스케치 맵을 분석하고 그러한 모든 isolated feature 들을 식별합니다. 한 번에 하나씩 그러한 각각의 isolated feature 가 검사되며, 후보 매칭들의 리스트는 예제 하이트 필드의 isolated feature 들로부터 형성됩니다. 분기점과 끝점에 대해 순서대로 살펴 보도록 합시다.

 

4.1.1. Branch Points

 

분기점 매칭의 경우, 분기점들의 차수( degree, 혹은 밸런스( valence ) )가 일치해야만 하며 진출( outgoing ) 세그먼트 체인의 각도( angle )는 반드시 비슷해야 합니다. 각도 매칭의 품질을 결정하기 위해서는, d 개의 이용가능한 alignment( 노선? ) 만이 d 차수를 가진 분기점에 대해서 고려되어야만 합니다. 예를 들어 그림 5d 에서 보이는 것처럼 3 차수의 브랜치 패치는 3 개의 alignment 들인 ( 1, 2, 3 ) -> ( 1, 2, 3 ), ( 2, 3, 1 ), ( 3, 1, 2 ) 을 가집니다( 이 패치들의 미러 이미지는 새로운 패치로 취급되며 그것의 alignment 는 독립된 프로세스입니다 ). 일반적으로 주어진 예제 하이트 필드에는 그러한 분기점들이 많이 존재하지 않으므로, 모든 후보 매칭들에 대한 검사는 극단적으로 빠릅니다.

 

사용자 스케치와의 피팅( fit )을 위해 후보 패치들에 대한 왜곡( warping )을 수행하려면, 첫 번째 제어점 집합 {P_i} 가 그 패치들을 위해 식별되어야만 합니다. 이 제어점들은 분기점 자체의 위치로 구성되며, 부가적으로 각 진출 경로가 패치에 새겨진 원과 접촉( intersect )하는 위치( 그림 5d 참조 )가 추가됩니다. 예를 들어 세 개의 분기를 가지는 패치는 총 4 개의 제어점을 가지게 됩니다. 스케치 맵으로부터의 패치를 위해 그것과 관련한 제어점 집합 {P'_i} 도 정의됩니다. 이제 우리는 제어점 {P_i} 를 {P'_i}  에 매핑하는 연속적인 좌표 변환을 필요로 하며, 그것은 찌그러짐( distortion )을 최소화해 줄 것입니다. 우리는 이 목적을 달성하기 위해 thin-plate spline( TPS ) interpolation [33] 을 사용합니다. 왜냐하면 그것은 적은 제약을 사용하고 integral bending norm 에 의해 측정된 것처럼 왜곡을 최소화합니다. 우리는 두 개의 개별적인 TPS 함수를 사용해 좌표 변환을 형성하는데, 그 변환은 원본 하이트 필드의 모든 위치를 왜곡된( warped ) 하이트 필드의 보간된 위치로 매핑합니다. 가장 낮은 변형( deformation ) 에너지를 가진 최상의 k 분기점 패치들은 앞으로의 매칭을 위한 후보가 됩니다.

 

 

4.1.2. Endpoints

 

끝점 매칭은 직관적입니다. 왜냐하면 모든 끝점들은 비슷한 curvilinear feature 들을 가지기 때문입니다: 상대적으로 짧은 세그먼트 체인이 끝점에서 나옵니다. 이는 쉽게 정렬될 수 있습니다. 그러므로 이 경우에는 모든 끝점 패치들을 왜곡없이 앞으로의 매칭을 위한 후보로 선택합니다( 그림 5e ).

 

 

4.1.3. Path Features

 

그림 7. ( a ) 경로를 따라 고르게 샘플링된 점에서 저장된 경로에 대해 수직인 Height profile 들. 두 경로가 만나는 점 P 에서의 Height profile 은 P2 와 P3 에서 저장된 profile 과 선형적으로 보간됩니다. ( b ) P3 에서 저장된 5-point height profile 의 예.

 

우리의 모든 curvilinear feature 들은 ( PPA 로부터 나온 ) 라인 세그먼트 체인인데, 그것은 두 개의 isolated feature 들 사이를 연결합니다. 우리 시스템은 사용자 스케치의 라인 세그먼트 체임을 순회하는 동안에 curvilinear feature 들을 따라 일치하는 패치들을 검색합니다. 시스템은 이 체인들을 따라 패치의 1/2 크기만큼을 이동합니다. 그리고 각 이동 단계마다 패치를 내려 놓는 것이죠. 분기 패치와 마찬가지로 curvilinear feature 를 따라 가는데 있어서의 후보 패치들은 사용자 스케치와 일치하도록 변형됩니다. 후보 패치에는 항상 p₀, p₁, p₂ 라는 세 개의 제어점이 존재합니다( 그림 5f ). 그리고 왜곡을 결정하는 사용자 스케치에는 세 개의 관련 점들인 P'₀, P'₁, P'₂ 가 존재합니다. 외부 제어점인 p₁ 과 p₂ 는 패스가 패치에 새겨진 서클을 가로지는 곳에 위치합니다. 중간의 p₀ 은 패치 내의 체인의 중심점입니다. 이는 분기 패치의 중앙 제어점과 유사합니다.

 

모든 후보 패치들은 매칭 기준의 조합을 고려해서 순위가 매겨집니다. 가장 좋은 후보 패치가 출력 하이트 필드에 합성됩니다. 우리는 다음과 같은 비용 개념을 사용합니다:

 

• C_d. 이는 TPS 왜곡( [33] 을 확인하세요 )으로부터의 변형 에너지를 의미합니다. 변형 에너지는 후보 패치 지형 구조가 스케치 맵의 제약과 얼마만큼이나 일치하는지를 측정합니다. TPS 왜곡은 ( 제어점이 한 라인상에 존재해서 폐기되는 경우를 제외하고는 ) 대부분의 경우에 패치를 원하는 구성으로 왜곡할 수 있습니다. 하지만 대규모 변형은 거슬리는 찌그러짐을 만들어낼 수 있으며, 여기에서는 패널티를 부여 받습니다.
• C_g. 이는 graph-cut 점수( Appendix A 참조 )를 의미합니다. Graph-cut seam 비용은 후보 패치가 이미 머지된 패치들과 겹치는 영역에서 얼마나 어울리는지를 지시합니다( graph-cut 은 자동적으로 하나의 패치가 다중의 패치와 겹치는 경우를 제어하며 그 겹침이 해제될 수 있습니다 ). 높은 graph-cut 점수는 그 seam 이 더 심해서 Possion editing 에 의해서 제거되기 힘들다는 것을 의미합니다.
• C_f. 이는 feature 차이점( dissimilarity ) 비용을 의미합니다. 차이점 비용은 만나는 경로들을 따라서 존재하는 feature 들이 얼마나 일치하는지를 측정합니다^[각주:3]. 우리는 curvilinear 경로를 고르게 샘플링하고, 각 샘플 포인트에서 그 경로의 방향과 직각인 coarse height profile 을 저장합니다( 현재 우리 구현에서는 7-point profile 을 사용합니다 )( 그림 7 ). 그 경로가 P 에서 다른 경로와 만날 때, P 에서의 height profile 은 가장 가까운 이웃인 P2 와 P3 에서 저장된 profile 들과 선형적으로 보간됩니다. 경로가 만나는 곳에서의 height profile 은 sum of squared differences( SSD ) 를 사용해 비교됩니다.
• C_is. 이는 사용자가 지정한 제약( 들 )을 의미합니다. height 제약이나 path smoothness 제약 등이 있습니다.

 

전체 비용은 전체 매칭 비용들의 선형 결합입니다.

 

.

 

α 는 가중치일 뿐만 아니라 그 비용을 위한 normalization 계수( coefficient )이기도 하다는 데 주의하시기 바랍니다. 우리의 현재 시스템에서 우리는 대부분의 테스트 케이스에 다음과 같은 값을 사용합니다.

 

 

 

이 계수를 변경하면 특정 매칭 기준이 강조되며, 다른 합성 결과를 산출하게 됩니다. Curvilinear feature 매칭과 너비우선 탐색 순으로의 배치를 마치고 나면, 출력 하이트 필드는 그림 6e 에서 보이는 것 중 하나와 비슷하게 보일 것입니다.

 

그림 8 은 그림 10a 의 스케치 맵과 그림 10b 의 예제 하이트 맵을 사용하여 만들어진 래스터-스캔 순서 패치 배치와 트리-순서 패치 배치를 비교한 것을 보여 줍니다. λ 심볼의 내부 구조는 래스터 스캔 결과에서는 잘못 해석됩니다( 그림 8a ). 이는 행 기반 스캔이 서클의 경계를 즉각적으로 lock on 해서 앞으로의 매칭에 대한 제약을 생성하기 때문입니다. 그 제약은 내부의 좋은 매칭들을 방해하게 됩니다. 그림 8b 는 가장 어려운 요소( center branch point )가 가장 먼저 매칭될 때 λ 와 서클이 모두 복제( reproduce )될 수 있음을 보여 줍니다.

 

그림 8. ( a ) 래스터-스캔 패치 배치 순서를 사용해 만들어진 합성. ( b ) 트리 순회를 사용해서 만들어진 합성.

 

4.2. Nonfeature Patch Placment

 

Isolated feature 와 curvilinear feature 들이 배치되고 나면, 출력 하이트 필드의 빈 영역들은 특별한 feature 를 가지지 않는 공간들입니다. 이 영역을 채우는 실행가능한 방법은 이미 배치되어 있는 픽셀들과 어울리는 패치를 복사하는 것입니다. 이를 위해 우리 시스템은 이미 채워진 영역들로부터 "성장시켜" 나갑니다. 특히, coarsely spaced increments 내의 정방형 패치 위치들은( 예를 들어 수평적이나 수직으로 매 100 pixel ) 이미 합성된 하이트 필드와 겹쳐진 지역에 대한 영역과 관련해 내림차순으로 채워집니다. 시스템은 겹쳐진 지역의 SSD 에 기반해, 패치와 이미 합성된 하이트 필드 사이의 고품질 매칭을 검색하며, k 개의 후보들을 선택합니다. 그리고 나서 머징( merging )중인 곳의 SSD 점수와 graph-cut 비용의 결합( combination )에 따라 최적의 매칭을 찾습니다. 최적의 패치가 배치되고, 시스템은 겹친 지역을 찾기 위해 하이트필드를 계속해서 순회합니다. 출력 맵의 모든 피셀이 채워지면 이 과정이 끝나게 됩니다.

 

이미 합성된 출력 하이트 필드와의 최적의 매칭을 찾기 위한 SSD 기반 검색은 Fast Fourier Transformations( FFTs ) [ 34 ], [ 35 ] 에 의해 가속화될 수 있습니다. FFT 기반 접근을 사용하면, 매칭 비용은 O( n log( n ) ) 시간으로 계산될 수 있으며, 여기에서 n 은 소스 하이트 필드의 픽셀 개수입니다. 이는 SSD 구현이 O( n² ) 의 시간이 걸린다는 점과 대조됩니다.

 

5. PATCH MERGING

 

그림 9. 패치 배치 및 Seam 제거에 대한 설명. ( a ) 패치 매칭은 graph-cut 을 통해 식별됩니다. ( b ) 배치 배치는 seam 을 산출합니다. ( c ) Possion seam remover 는 최종 결과를 산출합니다.

 

우리 시스템은 두 개의 기법을 사용해 출력 하이트 필드에 배치된 패치들 사이의 부드러운 전이( transition )를 보장합니다. 첫 번째 기법은 graph-cut 기술입니다 [ 26 ], [ 36 ]. 이것은 이미 배치된 픽셀들과 배치되고 있는 지역으로부터의 픽셀들 사이에서 good seam 들을 검색합니다. 두 번째 기법은 현존하는 pixel 과 새롭게 배치되고 있는 패치의 픽셀 사이에서 더욱 완만한( gentle ) 전이를 생성하기 위해서 Poisson equation [ 37 ] 을 사용합니다.

 

5.1. Graph-Cut Optimal Seam Finder

 

Graph-cut 알고리즘은 패치들 간의 겹친 지역에서 seam 을 찾아내는데, 그것은 어떤 픽셀이 최종 이미지에서 유지되어야 하는지를 결정하게 됩니다. 이는 max-flow/min-cut 그래프 문제를 해결함으로써 수행됩니다. 이는 cut 을 가로지르는 mismatched elevation 에 대한 비용을 최소화합니다. 그래프에서 edge 는 인접 픽셀들 간의 연결을 표현하며, 그것들은 높이차에 기반한 가중치를 부여받습니다. 일부 패치의 경우에, 우리는 주어진 패치로부터 branch feature 패치의 중앙 픽셀들과 같은 특정 그룹의 픽셀들이 포함되기를 원할 것입니다. 이는 특정 edge 의 가중치를 무한대로 높게 설정함으로써 수행될 수 있습니다.

 

앞에서 언급했듯이 graph-cut 알고리즘으로부터 최종 seam 의 비용이 시스템에 의해 사용됩니다. 시스템은 주어진 feature 를 표현하기 위해 여러 후보 패치 중 하나를 선택하기 위해 이를 사용합니다. Seam 을 검색하기 위해서 graph-cut 알고리즘을 사용하는 방법에 대한 세부사항은 [ 26 ] 에서 찾아 볼 수 있습니다.

 

5.2. Poisson Seam Remover

 

시스템이 graph-cut 을 사용해 출력 맵에 새로운 패치들을 배치하고 나면, seam 을 따라 불연속성이 가시화될 것입니다( 그림 9b ). 우리는 이를 개선하기 위해서 seam 들에서 gradient value 들을 인위적으로( artificially ) 설정합니다. 우리는 Poisson equation 을 사용함으로써 이를 수행하는데, 그것은 Perez et al. 이 색상 이미지에서 seam 을 가로질러 pixel 을 매칭시키는 방식 [ 37 ] 과 유사합니다.

 

우리의 고도( elevation ) 조정 단계는 겹친 지역( 일반적으로 패치 크기의 1/3 )에서의 먼저 elevation value 를 gradient value 로 변환합니다. 그리고 나서 seam 을 가로지르는 gradient value 들은 인위적으로 0 으로 설정됩니다. 마지막으로 Poisson equation 을 사용해 이 인접 gradient value 들에 대한 최적의 elevation 집합을 찾습니다. 이 작업의 결과는 새로운 elevation 집합인데, 이는 seam 을 더욱 부드럽게 만들어 줍니다( 그림 9c ). 우리 시스템은 그러한 elevation 조정을 지역적으로 수행합니다. 이는 배치된 패치 당 한 번만 그 메서드가 호출된다는 의미입니다. Elevation 조정을 지역적으로 수행하면, 엄청난 양의 행렬 연산을 수행해야 하는 상황을 피할 수 있습니다. 더 세부적인 내용은 Appdendix B 에서 확인하시기 바랍니다.

 

6. TERRAIN SYNTHESIS RESULTS

 

우리는 그림 1, 10, 11, 12, 13, 15 에서 보이는 결과를 산출하기 위해 US Geological Survey terrain data 로부터 만든 DEM 을 사용했습니다. 데이터의 원점, 해상도, 크기들이 표 1 에 기술되어 있습니다.

 

우리의 예제 하이트 필드는 1,200 x 1,200 에서 4,097 x 4,097 의 범위를 가지고 있으며, 16 비트 하이트 해상도를 가집니다. 이렇게 큰 지형 맵들은 전통적인 텍스쳐 합성 접근법에서는 심각한 검색 문제를 발생시킵니다. 80 x 80 크기를 가지는 패치를 사용하면, 4,000 x 4,000 크기의 맵의 경우 약 16 million( 1600 만 ) 개의 가능한 매칭들이 존재하게 됩니다. 그러나 우리의 feature 기반 분석의 결과로서( 역주 : 앞에서 이야기한 PPA 를 의미하는 듯 ), 우리는 채워져야 할 후보 위치에 대한 매칭을 600 개 수준으로 필터링할 수 있었습니다. 이는 계산 비용을 엄청나게 줄여 줬습니다. 우리의 기법은 대략 5 분에서 6 분 정도의 시간을 소비해 대표적인( ? ) 지형을 합성할 수 있었습니다. Intel Pentinum 4 2.0 GHz 프로세서와 2 Gbyte 메모리를 사용했습니다. 모든 결과들은 Planetside 사의 Terragen 지형 렌더링 시스템을 사용해서 렌더링되었습니다. 지형 지오메트리에 매핑될 텍스쳐로는 ( 높이와 기울기에 의해 결정된 ) 절차적 텍스쳐를 사용했습니다.

 

그림 10 과 그림 11 은 우리의 지형 합성 접근법을 사용해서 같은 스케치 맵으로부터 다양한 출력을 뽑아 내는 것을 보여 줍니다. 그림 10d 는 Mount Jackson 의 지형과 그림 10a 에서 보여준 스케치 맵을 사용해서 만든 ( 1,000 x 1,000 ) 합성 결과를 보여 줍니다. 이 결과가 많은 패치들로부터 생성되기는 했지만, 내부의 λ 와 외부의 서클이 끊기지 않는 산등성이를 형성하고 있습니다. 또한 커튼같이 접히는 특징들이 산의 측면을 따라 잘 보이고 있습니다. 그림 10h 는 Grand Canyon 지형을 사용한 ( 2,000 x 2,000 ) 합성 결과를 보여 줍니다. 이 예제를 위해 그림 10e 의 스케치 맵을 사용했는데, 그것은 그림 10a 의 역( inverse )입니다.  그래서 산등성이 대신에 계곡이 선택됩니다. 여기에서 λ 와 서클은 Colorado River 와 만나는 조각( piece )으로부터 형성됩니다. 그런데 아직 seam 위치는 검출되지 않았습니다. 사용자 스케치가 영향을 주기는 하지만, 이 지형은 원본 데이터의 풍부한 침식 형태( water-carved feature )를 보존합니다. 그림 11d 는 Mount Vernon 지형에 대한 ( 1,000 x 1,000 ) 합성 결과를 보여 줍니다. 그림 11h 는 Flathead National Forest mountain 지역을 사용한 ( 2,000 x 2,0000 ) 합성 결과를 보여 줍니다. 그럼 12d 는 Mount Vernon 지형과 중국어로 "물" 이라고 그려진 사용자 스케치를 사용한 결과를 보여 줍니다. 이 결과들은 우리 시스템이 매우 다양한 유형의 지형과 매우 다양한 특성들을 처리하면서도 입력 스케치 맵의 핵심 feature 를 유지하는 능력을 가졌음을 보여 줍니다. 그림 15 는 Grand Canyon 과 Flathead range 의 합성 결과에 대한 클로즈업( close-up ) 뷰를 제공합니다. 그림 13a 는 Crand Canyon 높이 맵을 렌더링한 것을 보여 줍니다. 우리는 스케치 맵을 획득하기 위해 이 맵으로부터 PPA 를 사용해 협곡 feature 를 추출했습니다. Puget Sound DEM 스타일로 스케치를 합성함으로써, 우리는 그림 13b 에서 보여 주듯이 Grand Canyon 에 대한 ( 4,000 x 2,000 ) "산맥" 버전을 획득했습니다.

 

표 1.

 

 

그림 10. 하프라이프( half-life ) 심볼을 사용한 다중 지형 합성 결과. ( a ) 사용자 스케치. ( b ) Mount Jackson. ( c ) 합성 결과. ( d ) Colorado 의 Mound Jackson 의 elevation map 으로부터 합성된 지형을 렌더링함. ( e ) 사용자 스케치. ( f ) Grand Canyon. ( g ) 합성 결과. ( h ) Grand Canyon 의 elevation map 으로부터 합성된 지형을 렌더링함.

 

그림 11. 하프라이프( half-life ) 심볼을 사용한 다중 지형 합성 결과. ( a ) 사용자 스케치. ( b ) Mount Vernon. ( c ) 합성 결과. ( d ) Kentucky 의 Mound Vernon 의 elevation map 으로부터 합성된 지형을 렌더링함. ( e ) 사용자 스케치. ( f ) Flathead 산맥. ( g ) 합성 결과. ( h ) Montana 의 Flathead National Forest 산맥( mountain range )의 elevation map 으로부터 합성된 지형을 렌더링함

 

그림 12. 중국어로 "물" 이라 쓰여진 스케치를 사용한 지형 합성. ( a ) 사용자 스케치. ( b ) Mount Vernon. ( c ) 합성 결과. ( d ) Kentucky 의 Mound Vernon 의 elevation map 으로부터 합성된 지형을 렌더링함.

 

그림 13. Grand Canyon 을 산맥으로 바꿈. Grand Canyon DEM 으로부터 추출된 feature 를 사용자 스케치로서 사용하는데, 이를 Puget-Sound 스타일 산맥의 elevation map 으로부터 Grand Canyon 의 구조를 따르는 산맥을 합성하기 위해서 사용함.

 

6.1. Synthesis with Multiple Terrain Style

 

 

그림 14. 다중 elevation map 들로부터 합성된 중간계의 3D 맵. ( a ) 중간계 맵. ( b ) 수계( water system )가 마스킹된 사용자 스케치. ( c ) 합성 결과. ( d ) 다중 elevation map 들로부터 합성된 지형을 렌더링.

 

표 2.

 

 

 

그림 14 에서는 더 큰 예제를 보여 줍니다. 그것은 여러 종류의 지형 스타일을 사용하는 중간계( Middle Earth )에 대한 3D 맵을 생성하는 것을 보여 줍니다. 단순한 스케치맵( 그림 14b )은 사용자에 의해서 생성되었는데, 중간계( 그림 14a )에 대해 아티스트가 렌더링한 맵으로부터 추출된 것입니다. 사용자는 다양한 지형 스타일을 스케치 맵의 각 부분에 설정할 수 있습니다( 표 2 ). 이 예제에서 사용자는 먼저 Mordor 의 Mount Doom 의 위치에 Mout St. Helen 을 배치했습니다( 지역적 특징 ). 다음으로 우리 시스템은 나머지 지형( 3,470 x 2,996 )을 자동으로 합성했고 그것을 Mount Doom 과 연속적으로 머지했습니다. 사용자 스케치는 다양한 산맥들과 하곡( river valley )들을 포함한다는데 주목하십시오( Mordor 의 북서쪽 코너 근처의 죽음의 늪( Dead Marshes ). 해안( coast ), 호수( lake ), 강( river ) 등은 단순한 마스크를 사용해 생성됩니다. 그것은 원본 맵으로부터 추출되었습니다. 합성된 하이트 맵( 그림 14c )은 Planetside 의 Terragen 지형 렌더링 시스템을 사용해 렌더링되었으며, 아트적인 느낌을 주기 위해 절차적 텍스쳐와 마스킹된 텍스쳐들이 사용되었습니다. 이 예제는 우리 시스템이 다중의 지형 스타일들을 하나의 합성 지형으로 결합하고 그것들을 seam 없이 블렌딩할 수 있는 능력을 가지고 있음을 보여 줍니다.

 

http://www.computer.org/tvcg/archves.html 에서 ( DivX 로 인코딩된 ) 동영상을 보시기 바랍니다. http://www.cc.gatech.edu/howardz/terrain 에 가면 추가적인 결과들을 확인하실 수 있습니다.

 

7. CONCLUSION

 

우리는 예제 기반 텍스쳐 합성 기법이 지형 합성의 영역에서 성공적으로 수용될 수 있음을 입증했습니다. 그 결과는 사용자가 제어 가능한 합성된 지형에서의 새로운 수준의 가시적 현실성입니다. 우리의 접근법은 geomorphology community 로부터 가지고 온 분석 기법을 사용해 하이트필드로부터 유용한 지형 특성을 추출할 수 있다는 사실에 영향을 받았습니다.

 

우리는 트리 순서에 기반한( tree-ordered ) 패치 배치 알고리즘을 소개했는데, 그것은 feature 트리에 대한 너비 우선 탐색에 기반합니다. 우리의 결과는 이 배치 기법이 표준 래스터-스캔 배치 순서보다 우월함을 입증합니다.

 

우리는 다양한 스타일의 지형을 합성하면서도 주요 지형 특징의 위치들에 대한 제어를 유지할 수 있다는 것을 증명했습니다. 우리 시스템은 원하는 지형 특성을 지정하기 위해 직관적인 스케치 기반 인터페이스에 기반합니다. 우리는 우리 기법이 지형 합성에 있어서 예제 기반 접근법을 온전하게 사용하는 첫 번째 시스템이라고 확신합니다.

 

우리 기법은 예제 기반 기법들과 동일한 제약들을 가지고 있습니다. 특히 최종 합성의 품질은 이용가능한 지형 데이터의 풍성함( richness )에 의존합니다. 만약 사용자가 원하는 지형 특성을 예제 하이트필드에서 찾지 못했다면, 그것은 원하는 결과를 산출하지 못할 것입니다. 예를 들어, 중요한 curvilinear feature 들이 거의 없는 사막으로부터 지형 데이터를 가지고 왔다면, 우리 기법은 형편없게 동작할 것입니다. 또한 curvilinear feature pattern 이 극단적으로 복잡해도 형편없게 동작할 것입니다. 추가적인 이슈는 패치 크기를 지정할 필요가 있다는 것입니다. 그것은 예제 지형의 해상도 및 스케일에 의존합니다.

 

우리는 우리의 현재 기법을 몇 가지 방향으로 확장할 계획을 가지고 있습니다. 먼저 스케치 맵에 부가적인 제약들을 도입함으로써 합성된 지형 전반에 대해 사용자가 더 많은 제어를 할 수 있도록 하는 데 관심을 가지고 있습니다. 예를 들어 우리는 특정 위치에서 원하는 elevation 을 지정할 수 있는 기능을 제공할 계획을 가지고 있습니다. 이는 matcher 와 함께 Poisson solver 를 제약함으로써 수행될 수 있습니다. 또한 우리는 현재 C0 연속성을 적용( enforcement )하고 있는데 이를 C1 연속성을 적용하는 연구를 하고 있습니다. 우리는 렌더링을 위해 elevation 과 texture map 의 joint synthesis 를 연구하고 있으며, 지형 합성에 대한 상호적인 제어( interactive control )에 대해서 연구하고 있습니다.

 

그림 15. Grand Canyon( 위쪽 )과 Flathead National Foreset 산맥( 아래쪽 )으로부터 합성된 지형에 대한 클로즈업 뷰.

 

APPENDIX A

GRAPH_CUT SEAM FINDING

 

생략. 원문 참조.

 

APPENDIX B

POSSION SEAM REMOVAL

 

생략. 원문 참조.

 

ACKNOWLEDGEMENTS

 

생략. 원문 참조.

 

REFERENCES

 

[1] Y.-C. Chang, G.-S. Song, and S.-K. Hsu, “Automatic Extraction of Ridge and Valley Axes Using the Profile Recognition and Polygon-Breaking Algorithm,” Computer and Geosciences, vol. 24, no. 1, pp. 83-93, 1998.
[2] B.B. Mandelbrot, The Fractal Geometry of Nature. W.H. Freeman,1982.
[3] A. Fournier, D. Fussel, and L. Carpenter, “Computer Rendering of Stochastic Models,” Comm. ACM, vol. 25, no. 6, pp. 371-384, 1982.
[4] R.F. Voss, “Random Fractal Forgeries,” Fundamental Algorithms for Computer Graphics, R.A. Earnshaw, ed., 1985.
[5] G.S.P. Miller, “The Definition and Rendering of Terrain Maps,”Proc. 13th Ann. Conf. Computer Graphics and Interactive Techniques (SIGGRAPH ’86), vol. 20, no. 4, pp. 39-48, 1986.
[6] J.P. Lewis, “Generalized Stochastic Subdivision,” ACM Trans.Graphics, vol. 6, no. 3, pp. 167-190, 1987.
[7] R. Szeliski and D. Terzopoulos, “From Splines to Fractals,” Proc. 16th Ann. Conf. Computer Graphics and Interactive Techniques (SIGGRAPH ’89), pp. 51-60, 1989.
[8] D.S. Ebert, F.K. Musgrave, D. Peachy, K. Perlin, and S. Worley, Texturing and Modeling: A Procedural Approach. Morgan Kaufmann, 2002.
[9] C. Dachsbacher, Interactive Terrain Rendering: Towards Realism with Procedural Models and Graphics Hardware, http://www.opus.ub.uni-erlangen.de/opus/volltexte/2006/354/, 2006.
[10] A.D. Kelley, M.C. Malin, and G.M. Nielson, “Terrain Simulation Using a Model of Stream Erosion,” Proc. 15th Ann. Conf. Computer Graphics and Interactive Techniques (SIGGRAPH ’88), pp. 263-268,1988.
[11] F.K. Musgrave, C.E. Kolb, and R.S. Mace, “The Synthesis and Rendering of Eroded Fractal Terrains,” Proc. 16th Ann. Conf. Computer Graphics and Interactive Techniques (SIGGRAPH ’89), vol. 23, no. 3, pp. 41-50, 1989.
[12] P. Roudier and B.P.M. Perrin, “Landscapes Synthesis Achieved through Erosion and Deposition Process Simulation,” Computer Graphics Forum, vol. 12, no. 3, p. 375, Aug. 1993.
[13] N. Chiba, K. Muraoka, and K. Fujita, “An Erosion Model Based on Velocity Fields for the Visual Simulation of Mountain Scenery,”J. Visualization and Computer Animation, vol. 9, no. 4, pp. 185-194, 1998.
[14] K. Nagashima, “Computer Generation of Eroded Valley and Mountain Terrains,” The Visual Computer, vol. 13, nos. 9-10, pp. 456-464, 1997.
[15] B. Benes and R. Forsbach, “Layered Data Representation for Visual Simulation of Terrain Erosion,” Proc. 17th Spring Conf. Computer Graphics (SCCG ’01), p. 80, 2001.
[16] B. Neidhold, M. Wacker, and O. Deussen, “Interactive Physically Based Fluid and Erosion Simulation,” Proc. Eurographics Workshop Natural Phenomena, 2005.
[17] J. Brosz, F.F. Samavati, and M.C. Sousa, “Terrain Synthesis By-Example,” Proc. First Int’l Conf. Computer Graphics Theory and Applications (GRAPP ’06), 2006.
[18] J.-P. Lewis, “Texture Synthesis for Digital Painting,” Proc. 11th Ann. Conf. Computer Graphics and Interactive Techniques (SIGGRAPH ’84), pp. 245-252, 1984.
[19] K. Perlin and L. Velho, “Live Paint: Painting with Procedural Multiscale Textures,” Proc. 22nd Ann. Conf. Computer Graphics and Interactive Techniques (SIGGRAPH ’95), pp. 153-160, 1995.
[20] D.J. Heeger and J.R. Bergen, “Pyramid-Based Texture Analysis/Synthesis,” Proc. 22nd Ann. Conf. Computer Graphics and Interactive Techniques (SIGGRAPH ’95), pp. 229-238, 1995.
[21] A.A. Efros and T.K. Leung, “Texture Synthesis by Non-Parametric Sampling,” Proc. Int’l Conf. Computer Vision, pp. 1033-1038, 1999.
[22] L.-Y. Wei and M. Levoy, “Fast Texture Synthesis Using Tree-Structured Vector Quantization,” Proc. 27th Ann. Conf. Computer Graphics and Interactive Techniques (SIGGRAPH ’00), pp. 479-488, 2000.
[23] M. Ashikhmin, “Synthesizing Natural Textures,” Proc. Symp. Interactive 3D Graphics, pp. 217-226, 2001.
[24] A.A. Efros and W.T. Freeman, “Image Quilting for Texture Synthesis and Transfer,” Proc. 28th Ann. Conf. Computer Graphics and Interactive Techniques (SIGGRAPH ’01), pp. 341-346, 2001.
[25] A. Hertzmann, C.E. Jacobs, N. Oliver, B. Curless, and D.H. Salesin, “Image Analogies,” Proc. 28th Ann. Conf. Computer Graphics and Interactive Techniques (SIGGRAPH ’01), pp. 327-340, 2001.
[26] V. Kwatra, A. Scho¨ dl, I. Essa, G. Turk, and A. Bobick, “Graphcut Textures: Image and Video Synthesis Using Graph Cuts,” ACM Trans. Graphics, Proc. 30th Int’l Conf. Computer Graphics and Interactive Techniques (SIGGRAPH ’03), vol. 22, no. 3, pp. 277-286, 2003.
[27] Q. Wu and Y. Yu, “Feature Matching and Deformation for Texture Synthesis,” ACM Trans. Graphics, Proc. 31st Int’l Conf. Computer Graphics and Interactive Techniques (SIGGRAPH ’03), vol. 23, no. 3, pp. 364-367, 2004.
[28] P. Bhat, S. Ingram, and G. Turk, “Geometric Texture Synthesis,”Proc. Eurographics Symp. Geometry Processing, 2004.
[29] A. Lagae, O. Dumont, and P. Dutre´, “Geometry Synthesis by Example,” Shape Modeling Int’l, 2005.
[30] S. Lefebvre and H. Hoppe, “Parallel Controllable Texture Synthesis,” ACM Trans. Graphics, Proc. 32nd Int’l Conf. Computer Graphics and Interactive Techniques (SIGGRAPH ’05), pp. 777-786, Aug. 2005.

[31] S. Lefebvre and H. Hoppe, “Appearance-Space Texture Synthesis,”ACM Trans. Graphics, Proc. 33rd Int’l Conf. Computer Graphics and Interactive Techniques (SIGGRAPH ’06), vol. 25, no. 3, pp. 541-548, 2006.
[32] J. Zhang, K. Zhou, L. Velho, B. Guo, and H.-Y. Shum, “Synthesis of Progressively-Variant Textures on Arbitrary Surfaces,” ACM Trans. Graphics, vol. 22, no. 3, pp. 295-302, 2003.
[33] F.L. Bookstein, “Principal Warps: Thin-Plate Splines and the Decomposition of Deformations,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 11, no. 6, pp. 567-585, 1989.
[34] C. Soler, M.-P. Cani, and A. Angelidis, “Hierarchical Pattern Mapping,” ACM Trans. Graphics, vol. 21, no. 3, pp. 673-680, July 2002.
[35] S.L. Kilthau, M.S. Drew, and T. Mo¨ ller, “Full Search Content Independent Block Matching Based on the Fast Fourier Transform,”Proc. IEEE Int’l Conf. Image Processing (ICIP ’02), pp. 669-672, 2002.
[36] Y. Boykov, O. Veksler, and R. Zabih, “Fast Approximate Energy Minimization via Graph Cuts,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 23, no. 11, pp. 1222-1239, Nov. 2001.
[37] P. Pe´rez, M. Gangnet, and A. Blake, “Poisson Image Editing,”ACM Trans. Graphics, Proc. 30th Int’l Conf. Computer Graphics and Interactive Techniques (SIGGRAPH ’03), vol. 22, no. 3, pp. 313-318, 2003.

 

저자 소개 생략. 원문 참조.

1. 다양한 스케일을 사용해서 엣지를 검출해도 이 문제를 쉽게 해결할 수 없습니다. 왜냐하면 인지적으로 볼 때 중요한 지형 구조들이 스케일을 변경했을 때 유지된다는 보장을 할 수 없기 때문입니다. [본문으로]
2. 우리는 일반적으로 이 문턱값을 입력 하이트 필드의 높이 범위의 절반 정도로 잡습니다. [본문으로]
3. Graph-cut 비용은 겹침( overlaping )에 대한 전체적 품질을 측정하지만, 그것은 겹치는 영역에 존재하는 모든 픽셀의 가중치를 동일하게 설정합니다. Feature 차이점 측정을 graph-cut 알고리즘에 통합하기는 힘듭니다; 그러므로 feature 를 강조하기 위해 개별적인 feature 차이점 비용 개념이 우리 시스템에 구현되었습니다. [본문으로]