잔불변형

Grassfire transform

이미지 처리에서, 풀파이어 변환은 픽셀에서 지역의 경계까지의 거리를 계산하는 것이다.지역의 골격이나 내축과 같은 설명자를 산출하기 위해 이미지 영역의 테두리에 "불 지르기"라고 설명할 수 있다.Harry Blum은 1967년에 이 개념을 도입했다.[1]

동기

한 지역의 골격은 그 지역의 대칭성뿐만 아니라 하위 부분, 수축, 돌기와 같은 것들을 묘사하기 때문에 유용한 설명자가 될 수 있다.[2]그것은 또한 지역의 내부를 경계 형태와 연관시키는 방법을 제공한다.풀불 변환에서, 해골은 "화재"가 만나는 지역의 지점에서 형성된다.문헌에서 이것은 충족 파형의 중심지로 설명된다.[2]

풀파이어 변환의 결과를 설명자로 사용하는 또 다른 장점은 변환불능이라는 것이다.접촉 파형에 의해 내축이나 골격이 생성되는 시기에 대한 정보를 보관한다고 가정하면 외부를 방사하여 골격을 복원할 수 있다.[1]

예제 알고리즘

아래 알고리즘은 한 지역의 경계로부터 맨해튼 거리를 계산하기 위한 간단한 두 개의 패스 방법이다.물론 잔디 불 변환을 수행하기 위한 몇 가지 다른 알고리즘이 있다. 

  을 위해 각각 배를 젓다 에 이미지 남겨진 로 맞다     을 위해 각각 칼럼을 세우다 에 이미지 맨 위의 로 밑바닥의       만일 (화소 , is 에 지역) {         세트 화소 로 1 + 최소의 가치를 매기다 의 그 북쪽의 그리고 서쪽의 이웃들       } 다른 {         세트 화소 로 영       }     }   }    을 위해 각각 배를 젓다 맞다 로 남겨진     을 위해 각각 칼럼을 세우다 밑바닥의 로 맨 위의       만일 (화소 , is 에 지역) {         세트 화소 로 분(가치를 매기다 의 그 화소,1 + 최소의 가치를 매기다 의 그 남쪽의 그리고 동쪽의 이웃들)       } 다른 {         세트 화소 로 영       }     }   }

아래는 이러한 변혁의 결과물이다.가장 강렬한 선들이 골격을 구성하고 있다는 점을 유념해야 한다.

소스 이미지
결과 이미지

적용들

다양한 컴퓨팅 문제에 맞게 풀파이어 변환을 추상화할 수 있다.이미지의 맥락을 넘어 임의의 기능으로 확장될 수 있다는 것이 증명되었다.[3]여기에는 Viterbi 알고리즘에 의해 처리되는 것과 같은 에너지 최소화 문제, 최대 제품 믿음 전파, 자원 할당 및 최적 제어 방법에서의 애플리케이션이 포함된다.[3]

배경을 지역으로 설정해 지역 간 거리를 계산하는 데도 사용할 수 있다.

참고 항목

참조

  1. ^ a b Blum, Harry (1967). "A transformation for extracting new descriptors of shape". In Wathen-Dunn, Weiant (ed.). Models for the Perception of Speech and Visual Form (PDF). Cambridge, Massachusetts: MIT Press. pp. 362–380.
  2. ^ a b Leymarie, F; Levine, M.D (1992). "Simulating the grassfire transform using an active contour model". IEEE Transactions on Pattern Analysis and Machine Intelligence. 14: 56–75. doi:10.1109/34.107013.
  3. ^ a b Felzenszwalb, Pedro F; Huttenlocher, Daniel P (2012). "Distance Transforms of Sampled Functions". Theory of Computing. 8: 415–28. CiteSeerX 10.1.1.88.1647. doi:10.4086/toc.2012.v008a019.