주 메뉴 열기

쾌속행진산법

(빠른 행진 방법에서 넘어옴)

쾌속행진산법(快速行进算法, 영어: fast marching method)[1]제임스 세티안이 만든 방법으로, 다음의 아이코날 방정식경계값 문제를 해결하는 수치적 방법이다:

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

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

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

알고리즘편집

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

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

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

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

같이 보기편집

외부 링크편집

참고 문헌편집

  1. J.A. Sethian. A Fast Marching Level Set Method for Monotonically Advancing Fronts, Proc. Natl. Acad. Sci., 93, 4, pp.1591--1595, 1996. [1]