Distance transform (python 구현)

Distance transform

---

 

머신비전, 영상처리 분야에서 Distance transform 알고리즘에 대해 알아보겠습니다.

 

 

 

0.Overview

---

Distance transform은 아래와 같이 다양하게 불립니다.

 

the distance function, chamfering algorithm or chamfering

 

Distnace transform은

아래의 그림들과 같이

바이너리 이미지의 subset에 대해서

각 픽셀이 어느 정도 떨어져 있는지를 알려줍니다.

 

 

 

아래 그림의 binary image의 subset은 0입니다.

따라서 변환 결과를 보면, subset이 아닌 곳(binary image에서 1이었던 곳)이

바로 subset에 대해 어느 정도 떨어져 있는지 알려주는 것입니다.

 

 

[출처] https://en.wikipedia.org/wiki/Distance_transform

 

 

 

위와 달리 아래 그림의 binary image의 subset은 1입니다.

그리고 변환 결과를 보면, subset이 아닌 곳(binary image에서 0이었던 곳)의 값은

subset에 대해 어느정도 떨어져 있는지 알려주는 것입니다.

 

2번째 그림(Figure 2.9)같은 경우는

장애물에서 어느정도 떨어졌는지 알 수 있는 지도라고도 생각하실 수 있습니다.

 

 

Sonka, Milan, Vaclav Hlavac, and Roger Boyle. Image processing, analysis, and machine vision. 4th ed. Cengage Learning, 2014. p20.

 

 

 

위의 어느정도 떨어져 있는지에 대한 계산방법은

Euclidean distance(De), City block distance(D4), Chessboard distance(D8)이 있으며,

아래 그림은 이에 대한 식과 그림입니다.

 

Sonka, Milan, Vaclav Hlavac, and Roger Boyle. Image processing, analysis, and machine vision. 4th ed. Cengage Learning, 2014. p17.

 

 

이외에도 여러 가지 distance metrics가 많이 있습니다.

 

 

 

1. 알고리즘

---

Sonka, Milan, Vaclav Hlavac, and Roger Boyle. Image processing, analysis, and machine vision. 4th ed. Cengage Learning, 2014. p20.

 

간단하게 설명하면,

1. 변환하려는 이미지와 같은 사이즈 이미지에

subset은 0으로, 나머지는 Nmax로 초기화합니다.

2. Figure 2.10의 첫 번째 마스크를 사용하여

위에서 아래로, 왼쪽에서 오른쪽으로 위 식을 이용해 값을 변경합니다.

3. Figure 2.10의 두 번째 마스크를 사용하여

아래에서 위로, 오른쪽에서 왼쪽으로 위 식을 이용해 값을 변경합니다.

4. 만약 Nmax의 값이 남아있다면 2, 3의 과정을 반복합니다.

 

 

 

2. python 구현

---

 

사용한 라이브러리는 위와 같습니다.

 

 

---

사용할 이미지입니다.

 

 

---

 

위에서 설명한 Distance metrics에 관한 함수입니다.

 

D 함수의 경우,

입력을 distance metrics type을 받아와

한가운데 픽셀에 대한 distance를 3x3 metrics로 return 합니다.

 

 

---

 

Figure 2.10의 마스크를 3x3 행렬로 구현하였고,

알고리즘의 2, 3 과정의 식은 3x3 행렬에서 최솟값을 가져오는 것으로 구현을 했습니다.

 

 

---

위의 그림은 각 distance metrics에 따른 결과입니다.

 

차이가 육안으로 보기 쉽지 않아 동영상을 추가합니다.

짧은 동영상을 보면 아주 약간의 차이가 있음을 알 수 있습니다.

 

[출처] : youtu.be/-r9dua5pBA0

 

---

 

 

해당 소스는 아래의 링크에서 보실 수 있습니다.

 

github.com/jstar0525/MachineVision/tree/main/Distance%20transform

jstar0525/MachineVision