이미지 포레스트 변환

Image foresting transform


디지털 이미지 처리의 관행상 알렉상드르 X.Falao, Jorge Stolfi 및 Roberto de Alencar Lotufo는 IFT(Image Foresting Transform)를 사용하여 2-D, 3-D 이미지 [1]및 동영상 처리에 시간을 절약할 수 있다는 것을 개발 및 입증했습니다.

이력

1959년 Dijkstra는 균형 힙 데이터[1][3] 구조를 사용하여 1957년[1][2] Moore와[1][4] 1958년 Bellman이 제시한 알고리즘을 개선하여 일반 그래프에서 경로 비용을 계산했습니다.버킷 정렬 기술은 10년 [1][5]후 다이얼 알고리즘이 개선되는 방법입니다.그 이후로 알고리즘은 여러 가지 방법으로 수정되고 수정되었습니다.Falcao, Stolfi 및 Lotufo가 개선한 [1]것은 이 버전입니다.

정의

이 변환은 Dijkstra의 최단 경로 알고리즘의 조정된 버전으로, 둘 이상의 입력과 디지털 이미지 처리 [1][2]연산자의 최대화에 최적화되어 있습니다.변환은 이미지 내의 픽셀을 그래프로 만듭니다.이러한 포인트간의 접속은, 표시되는 패스의 「비용」입니다.비용은 픽셀 간 경로의 특징(예: 그레이 스케일, 색상, 구배)을 검사하여 계산됩니다.트리는 오퍼레이터가 정한 적용비용이 같거나 가까운 픽셀을 연결하여 만듭니다.변환의 견고성에는 비용이 많이 들고 처리 중인 코드와 데이터에 많은 스토리지 공간을 사용합니다.변환이 완료되면 이전 버전, 비용 및 라벨이 반환됩니다.디지털 화상 처리에 사용되는 대부분의 오퍼레이터는 이 세 가지 정보를 사용하여 최적화할 수 있습니다.

최적화

알고리즘에 의해 결정된 디지털 화상 처리 오퍼레이터에 따라 그 오퍼레이터가 무엇을 사용하는지에 따라 최적화를 위해 추가로 조정할 수 있습니다.또한 경로 재계산을 제거하여 알고리즘을 최적화할 수도 있습니다.이 작업은 외부 참조 테이블을 사용하여 계산된 경로를 추적함으로써 수행됩니다."백워드 아크"는 양방향 경로의 비용을 비교하여 더 비싼 경로를 제거함으로써 제거할 수 있습니다.또한 알고리즘이 일부 경로에 대해 무한대를 반환하는 경우도 있습니다.이 경우 한계값을 무한대를 대체하도록 설정할 수 있습니다. 그렇지 않으면 경로가 제거되고 추가 계산에 사용되지 않습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b c d e f g h i j Falcao, A.X. Stolfi, J. de Alencar Lotufo, R. : "이미지 포레스트링 트랜스폼: 이론, 알고리즘 및 응용 프로그램", IEEE TRANSIONS ON PATTANGE AND PATTANCE AND MACHINGE INTELITIONS, VOL 26, NO.1, 2004년 1월
  2. ^ a b E.W. Dijkstra, "그래프 연결의 두 가지 문제에 관한 메모", Numerische Mathik, vol.1, 페이지 269-271, 1959
  3. ^ E.F. 무어, "미로를 통과하는 최단 경로", 프로.동정.전환 이론, 285-292페이지, 1959년 4월
  4. ^ R. Bellman, "루팅 문제에 대하여", 응용수학계간, 제16권, 87-90페이지, 1958.
  5. ^ R.B. 다이얼, "토폴로지 순서를 가진 가장 짧은 경로 포레스트", 통신.ACM, 제12권, 제11호, 페이지 632-633, 1969년 11월