Regularised shortest-path extraction
[cite]10.1016/S0167-8655(97)00076-7[/cite]
1. Introduction
- 이미지에서 shortest path를 찾는 방법으로 Amini가 제안한 dynamic programming 방법이 있음
- 하지만 smoothness에 대한 constraint를 줄 수가 없음
- 이 논문에서 constraint를 추가한 식으로 더 나은 성능을 내보고자 함
2. Ordinary shortest-path extraction
- 기존 shortest-path extraction에 대한 설명
- 모든 지점에 대하여 최소 누적 cost를 순차적으로 계산한 뒤, 이를 탐색하여 경로를 결정 (Forward pass, Back-tracking)
- 계산 복잡도는 O(Qmn), Q = 2p+1, p는 경로의 이동 가능한 order, m은 이미지 세로, n은 이미지 가로 크기
3. Regularised shortest-path extraction
- 기존 shortest-path 식에 경로의 roughness를 반영한 항을 추가
- roughness는 Amini et al., Gruen and Li, Merlet and Zerubia 의 방법을 사용하였음(이전 픽셀과 다음 픽셀의 진행 방향이 바뀐 정도의 제곱을 이용)
- roughness항에 regularisation constant를 추가하여 smoothness정도를 조절 가능
- 계산 복잡도는 O(Q^2mn) (기존 방법과는 달리 2번째 전 픽셀까지 계산하여야 하기 때문)
4. Pixel subdivision
- 픽셀이 discrete하기 때문에 45도가 아닌 각도로 일정하게 진행하는 방향이 오히려 45도보다 roughness가 높게 나올 수 있음
- 때문에 픽셀을 subpixel로 나누어 계산 하여 이를 해결
5. Conclusion
- roughness를 반영한 항 추가
- roughness계산을 정확히 하기 위해 subdivision 방법을 사용할 수 있음