영상처리 4방향 윤곽선 추적 알고리즘

4방향 윤곽선 추적 알고리즘은 내가 영상처리를 공부하기 시작하고 처음 배운 알고리즘이다. 실력이 부족한 탓에 많이 고생했던 기억이 있다. 4방향 윤곽선 추적 알고리즘은 2*2 마스크를 이용하여 정해진 규칙에 의해 객체의 외곽선을 타고 돌면서 이동한 좌표의 정보를 저장한다. 이때 저장된 정보가 해당 객체의 윤곽선이 된다.

4방향의 규칙은 아래 표와같다

	A	B	X	Y
전진	1	0	A	B
우측	0	1	B	Y
우측	1	1	A	X
좌측	0	0	X	A

표에서 1과 0의 뜻은 이진화된 영상에서 Gray 값이 0인 검정색을 1,  255 값인 흰색을 0 이라고 한 것이다

마스크는 이미지가 저장된 배열의 첫 픽셀(0 ,0)에서 시작하며, 마스크에서 현재 픽셀을 가르키는 것은 

아래 마스크 그림에서 X이다. 객체를 만날 때까지 좌측에서 우측으로 위에서 아래로 이동한다

A	B
X	Y

위와 같은 2*2마스크의 X가 0 값(이진화 영상에서 검은색 픽셀)을 만날 경우 마스크의 X를 기준으로 A , B 의 좌표를 조건으로 방향을 바꾼다. 예를 들어 처음 0값을 만난 좌표가 x =2 , y =2 라고 했을 때,

1,2	1,3
2,2	2,3

처음 모양의 마스크에서 A의 좌표는 x =1, y =2   B의 좌표는 x =1 y =3 과 같다.

A,B의 좌표를 검사하여 0이면 1, 255면 0의 값을 구하고, A = 0 B = 0 의 결과가 나오면 위에 표의 규칙에 의해

X의 좌표는 X로 Y의 좌표는 A로 바꾼다. (예시의 방향에서 A,B가 0,0이면, 마스크는 좌측으로 회전한다.)

마스크는 다음과 같이 움직이게된다.

B	Y
A	X

여기서 중요한 포인트가있는데 바로 방향성이다. 즉 처음마스크 모양의 방향이 0방향이라고 할 때

현재 마스크는 왼쪽으로 90도 움직인 모양이므로 방향이 0방향에서 1방향으로 바꼇다 라고 할 수 있다

방향에 따라서 A , B의 좌표가 달라지기 때문에 방향에 따라서 A , B 의 좌표의 조건을 바꿔서

검사해야 한다. 이런 식으로 마스크는 객체를 타고 돌다 처음 좌표로 돌아오면 추적을 멈춘다.

이 알고리즘을 완성하기 위해서는 여러 가지 예외 처리를 생각해봐야한다. 

외곽선을 타고 도는 마스크의 종료조건이나 최외곽 픽셀이 있을 경우 배열의 범위를 넘어서는 조건검사로 인한 실행오류등. 많은 생각을 해봐야 하는 알고리즘이고, 그 만큼 픽셀 단위 연산을 하는 영상처리에 대한 이해와 알고리즘 공부에 많은 도움이 된다.