빠른 행진 방법

빠른 행진 방법(빠른行进方法, )J.A. Sethian. A Fast Marching Level Set Method for Monotonically Advancing Fronts, Proc. Natl. Acad. Sci., 93, 4, pp.1591--1595, 1996. 은 제임스 세티안이 만든 방법으로, 다음의 아이코날 방정식의 경계값 문제를 해결하는 수치적 방법이다:




특히, 이런 문제는 닫힌 표면의 진화를 점 에서 전파 표면으로 가는 법 방향의 속도 와 시간 에 관한 함수로 설명한다. 속도 함수는 결정되어 있고, 파면이 점 을 통과하는 시간은 방정식을 풀어서 얻을 수 있다. 대신에, 는 점 에서 시작해서 에 도달하는 최소 시간으로 생각할 수 있다. 빠른 행진 방법은 "아는 정보"에서 시작해서 해법을 만들어 나가는 문제(즉, 경계값 문제)의 최적 제어 해석의 이점을 이용한다.

알고리즘은 데이크스트라 알고리즘과 유사하고 정보가 시작 영역에서 바깥으로 뻗어나간다는 점을 이용한다. 이 문제는 레벨 셋 방법의 특수한 경우이다. 더 일반적인 알고리즘이 있지만 일반적으로 더 느리다.

평면이 아닌(삼각화된) 영역으로의 확장은 다음을 표면 와 에 대해서 해결하는 것으로, 론 킴멜과 제임스 세티안이 고안해냈다:

알고리즘

처음에는, 영역이 메쉬로 이산화되었다고 가정한다. 이 메쉬의 점을 꼭짓점으로 부를 것이다. 각각의 꼭짓점 은 대응하는 값인 을 가진다.

이 알고리즘은 데이크스트라 알고리즘과 거의 비슷하지만 꼭짓점의 값을 계산하는 방법은 다르다. 데이크스트라 알고리즘에서 꼭짓점의 값은 인접한 하나의 꼭짓점만 의존해서 계산하지만, 에서 PDE를 풀 때는 에서 개의 인접한 꼭짓점을 사용한다.

꼭짓점은 각각 멂(far) (방문하지 않음), 고려 중(considered) (방문했으며 시험적인 값을 부여함), 그리고 완료 됨(accepted) (방문했으며 영구적인 값을 부여함)의 라벨이 붙는다.

 모든 꼭짓점 에 의 값을 부여하고 멂 라벨을 붙이고, 인 모든 꼭짓점에 대해서 로 설정하고 의 라벨을 완료 됨으로 설정한다.
 모든 먼 꼭짓점 에 대해서, 의 새 값을 계산하기 위해 아이코날 업데이트 공식을 사용한다. 이면, 으로 의 라벨을 고려 중으로 설정한다.
 가 고려 중인 꼭짓점 중 가장 작은 의 값을 가지는 꼭짓점이라면 에는 완료 됨의 라벨을 붙인다.
 의 모든 완료되지 않은 인접한 꼭짓점 에 대해서, 시험적 값 을 계산한다.
 이라면 로 설정한다. If 의 라벨이 멂이였다면, 라벨을 고려 중으로 갱신한다.
 만약 고려 중인 꼭짓점이 있다면, 3단계로 되돌아간다. 그렇지 않으면 종료한다.

 같이 보기 
 레벨집합 방법
 빠른 스위핑 방법
 벨먼-포드 알고리즘

 외부 링크 
 Dijkstra-like Methods for the Eikonal Equation J.N. Tsitsiklis, 1995
 The Fast Marching Method and its Applications by James A. Sethian
 Multi-Stencils Fast Marching Methods
 Multi-Stencils Fast Marching Matlab Implementation 
 Implementation Details of the Fast Marching Methods
 Generalized Fast Marching method by Forcadel et al. [2008] for applications in image segmentation.
 Python Implementation of the Fast Marching Method
See Chapter 8 in Design and Optimization of Nano-Optical Elements by Coupling Fabrication to Optical Behavior 

 각주 

분류:수치미분방정식