[ 질문 공유용 ] dead-end detection 에 대한 질문

알림 : 이 문서는 주위 분들에게 질문을 하기 위해서 작성되었습니다. 구현이 완전히 끝나면 따로 문서를 공유할 계획입니다.

---

제가 이번에 [ Terrain Synthesis from Digital Elevation Models ] 라는 논문의 내용을 구현해 보려고 하고 있습니다.

 

이것은 세 가지 단계로 이루어져 있습니다; profile recognition, polygon breaking, branch reduction. 이것은 [ Profile-recognition & Polygon-breaking Algorithm( PPA ) ] 를 사용합니다.

현재 저는 profile recognition 까지 구현을 한 상태입니다. 아래 그림은 valley 에 대한 profile 덩어리를 보여주고 있습니다: target-connection, cross-line removal, parallel-line removal 까지 수행한 상태입니다.

 

 

이제 polygon breaking 을 적용할 차례인데요, 닫힌 폴리곤에서 중요하지 않은 라인 세그먼트를 배제하면서 중심 라인은 보존하는 단계입니다. 즉 일종의 thinning 알고리즘입니다. 저자의 경우에는 [ k x k thinning ] 의 4 가지 원칙을 지켰다고 이야기하더군요. 5 번째는 branch reduction 을 통해서 해결한다고 합니다.

어쨌든 닫힌 폴리곤의 중요하지 않은 라인 세그먼트라는 것은, valley 를 찾는 경우에는 가장 높은 elevation 을 가진 세그먼트이고, ridge 를 찾는 경우에는 가장 낮은 elevation 을 가진 세그먼트입니다.

그냥 삼각형이나 사각형인 경우에는 문제가 쉽게 해결이 됩니다. loop 를 돌기도 편하죠. 하지만 아래 그림에서 붉은 색으로 보이는 복잡한 모양의 닫힌 폴리곤같은 경우를 만나면 머리가 좀 아파집니다.

전에 처음 시도했을 때는 Brute-force 기법을 사용해서 재귀함수를 만들었습니다. 그랬더니 라인이 너무 많아 stack-overflow 가 발생하더군요. 

그리고 그 다음에 시도했을 때는 stack algorithm 을 사용해 라인 세그먼트를 쌓아 가다가 시작 세그먼트와 만나는 닫힌 폴리곤이 형성되면 그 중에서 가장 적절하지 않은 세그먼트를 배제하는 방법을 취했습니다. 이 방식은 매우 시간이 오래 걸렸습니다. 게다가 뭘 잘못했는지 중간에 맘에 안드는 결과가 나오는 곳이 있더군요.

[ A Visual Basic program for ridge axis picking on DEM data using the Profile-Recognition and Polygon-Breaking Algorithm ] 에서는 [ 4. Polygon-breaking ] 섹션에서 "dead-end detection" 이라는 것에 대해서 언급합니다. 

A technique of "dead-end detection" has been designed in this paper to preempt many unnecessary tracing steps: when the segment tracing process encounters a dead-end of a branch, all the segments in this branch are marked as "route disabled". The tracing process then regresses to the root of the dead-end branch and the system flags the branch to be avoided for future tracings.

여기에서 branch 가 모양을 의미하는 건지 tree 의 branch 를 의미하는 건지 모호하고 branch 의 dead-end 라는 의미도 모호하네요. 이 문서에서 tree 자료구조에 대한 언급도 없었구요. 전체적으로 "dead-end detection" 알고리즘을 이해하기 어렵습니다. 자료구조를 어떻게 잡아야 할지도 모르겠구요.

 

현재 제 구현에서는 각 샘플포인트가 다음과 같이 정의되어 있습니다.

private class Point { public Int32 OffsetX; public Int32 OffsetY; public Int32 Elevation; public Boolean IsCandidate; public Point[] Neighbors = new Point[ 8 ]; // 8 items, clockwise connected neighbors from top-left. }

 

기존에 stack 방식의 구현을 했을 때는 Point 자료구조에서 Line 이라는 자료구조를 뽑아 내서 그것들을 기준으로 polygon breaking 을 처리했었습니다.

 

어쨌든 여기에서 좀 막막한 감이 있는데 polygon breaking 알고리즘 및 자료구조에 대해서 이해가 가는 분이 계시면 저에게 가르침을 주시면 감사드리겠습니다.

 

추가 : 제 구현 코드는 다음과 같습니다 : WpfApplication1.zip

 

---

해결!

 

그래프의 관점에서 이를 설명할 수 있습니다. 물론 너비우선탐색을 적용하면 트리구조라 해도 상관이 없습니다. 그냥 보이는 대로 폴리곤의 라인 세그먼트를 생각도 되구요.

 

하지만 어떠한 관점에서 구현하든지 앞에서 언급했듯이 재귀 함수를 구현할 수는 없습니다. 저같은 경우에는 재귀없이 깊이우선탐색을 하기 위해 stack 을 사용했습니다.

 

세그먼트를 높이 순으로 sorting 하기 때문에 한 번이라도 closed 상태가 되면 가장 불필요한 세그먼트는 시작 세그먼트라 할 수 있습니다. 저는 이 시작 세그먼트가 가장 불필요하다는 전제를 까먹고 구현하다가 고생을 했던 것이죠. 패스의 끝점( End point )에 도달하면 이전 분기로 롤백하면서 기존에 지나왔던 세그먼트를 정리하고 그 중에서 가장 불필요한 세그먼트의 높이를 기록해야 한다고 생각했습니다. 그것이 머리와 구현을 복잡하게 만들었던 것입니다. 이미 시작 세그먼트가 가장 불필요한 세그먼트라는 전제가 있는데 말이죠. 물론 이런 전제가 아니라도 알고리즘은 충분히 복잡합니다. 실수의 여지가 엄청나게 많죠.

 

어쨌든 시작 세그먼트가 포함되었던 closed polygon 은 닫힌 상태가 깨집니다. 만약 closed polygon 이 아니었고 endpoint 에 도달했다면 그 역시 닫힌 상태가 깨진 것이죠. 즉 closed polygon 이었든 그렇지 않았든 시작 세그먼트를 경유하려고 시도하는 모든 테스트는 더 이상 필요하지 않은 것이죠. 즉 이 시작 세그먼트를 경유하면 막다른 길( dead-end )로 가게 되어버리는 것입니다. 이런 시작 세그먼트에는 IsDeadEnded 라는 플래그를 설정해 둡니다. 그러면 다음 탐색시에 이 세그먼트를 테스트할 필요가 없습니다. 이런 식으로 세그먼트를 하나씩 제거하다가 보면 점점 탐색 속도가 빨라지게 됩니다.

 

제가 dead-end detection 없이 brute-force 로 탐색을 해 봤는데 100 x 100 이미지를 처리하는데 20 분 가까이 기다려도 끝이 나지 않았습니다. Dead-end detection 을 도입하니 3 초 안에 끝나더군요. 알고리즘 최적화의 무서움을 새삼 느꼈습니다.

 

나중에 전체 PPA 기법에 대해 따로 정리해 보도록 하겠습니다.

 

결과는 다음과 같습니다. Cyan 색상이 최종 결과입니다. 아직 branch reduction 부분이 완벽하지 않네요. 연구를 좀 더 해 봐야 할 것 같습니다.

 

 

비교대상을 만들어 주신( VB 코드를 구해서 C# 코드로 컨버팅해서 공유해 주신 ) 오석주 TD 님께 감사드립니다. 제가 제 구현에 확신을 가지고 계속 작업하는데 많은 도움을 주었습니다. 코드 흐름 자체는 잘못된 것이 아니라는 확신을 가지고 작업할 수 있었습니다.

 

원래 구현자는 배열을 여러 개 만들어서 플래그를 설정하면서 작업을 하더군요. VB 6.0 시절이라 그런지 개체지향프로그래밍에는 익숙하지 않은 것 같았습니다. 아니면 성능때문에 일부러 그렇게 한 것일지도 모르죠. 배열이 하도 복잡해서 제대로 이해를 하지는 못했지만 주석의 흐름으로 봤을 때 비슷한 방향으로 구현하고 있다는 것을 알 수 있었습니다.

 

앞으로 합성 구현이 남았는데 관련 논문의 양을 보니 가슴이 답답해 지네요( OTL ).