[Computer and Robot Vision] 공부

신나는 비가 오는 날이다.

연말이라 그런지 모두 휴가를 가서 연구실이 텅 비어있어서,

나 혼자 카페 음악을 틀고 공부하는 시간을 가지고 있는데,

이어폰을 안껴도 되어서 너무 좋다.

맨날 이렇게 노래 들으면서 기분 좋게 연구 하고 싶다. 헤헤

R. M. Haralick and L. G. Shapiro, “Computer and Robot Vision,” Volume I, Addison-Wesley, 1992

에 나온 일부분을 읽어보고 공부하는 시간을 가져볼 것이다.

https://www.amazon.com/Computer-Robot-Vision-Vol-1/dp/0201108771

책 구매는 위 아마존 링크에서 진행할 수 있고

https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=59542851

아래 알라딘 서점에서는 품절된 것을 보아하니, 판매 알림 신청을 해야 받을 수 있을 것 같다.

나는 운좋게도 학교 서양서 코너에서 이 책 한권을 찾을 수 있었다.

pdf는 있는지 없는지 모르고, 오래된 책이라 찾아볼 생각을 하지 않고 빌려서 보는 중이다.

 

먼저 나는 thresholding 부분과 labeling 부분을 읽어볼 것인데, 영어 실력이 원어민 수준이 아니라 오역이 있을 수 있으니,

혹시나 이 책을 읽기 전에 이 글을 찾은 독자분들은 원문을 꼭 읽어보기를 권한다.

1992년에 쓰여진 책이 맞나 싶을 정도로 깊이도 깊어서,

지금은 학교 도서관에서 책을 빌렸지만, 소장 욕구가 생겨서 중고로라도 구매 의사가 생기고 있다....

아 참고로 책은 vol1과 vol2로 분권이 되어있는데, vol2는 vol1을 기반으로 해서 더 어렵다. 참고하시길

 

오늘 내가 공부할 부분은 vol1, 2-3에 있는, connected components labelling이다.

 

- connected components labelling

0 또는 1의 값을 가진 픽셀들로 구성된 binary 영상이 있다고 하자.

이제 특정 픽셀에 대해서 그 픽셀 주변 값들과 픽셀간의 연관 관계에 의해서 어떤 결정을 내리는 방식이 있어야 한다.

connected components labelling은 그 픽셀간의 연관 관계에 의해서 이미지를 픽셀 단위로 처리하여 그룹핑하는 것을 말한다.

 

픽셀 간의 연관 관계에 대해서 예를 들자면

	1
1	1	1
	1

지금 위의 픽셀들의 연관 관계는 가운데 픽셀을 기준으로 하여 상하좌우의 4-connected된 지역만을 다루고 있다.

1	1	1
1	1	1
1	1	1

여기 픽셀들의 연관 관계는 그냥 가운데 픽셀을 기준으로 하여 8방으로 8-connected된 지역을 다루고 있다.

 

이 연관 관계는 결국 connected components labelling에 큰 영향을 주는데,

4-connected된 지역을 다룰 때는 다음과 같은 결과처럼 이미지를 분류하게 되고,

1	1	1	0	1	1	1
1	1	1	0	1	1	1
1	1	1	0	1	1	1
0	0	0	0	0	0	0
1	1	1	1	0	0	0
1	1	1	1	0	0	0
1	1	1	0	0	0	0

8-connected된 지역을 다룰 때는 다음과 같은 결과처럼 이미지를 분류하게 되고,

1	1	1	0	3	3	3
1	1	1	0	3	3	3
1	1	1	0	3	3	3
0	0	0	0	0	0	0
2	2	2	2	0	0	0
2	2	2	2	0	0	0
2	2	2	0	0	0	0

이렇게 분류 결과가 다르게 된다는 점이 있다.

(이 부분은 오역이 있을 수 있다. 내가 이해한 바를 정리하여 적어둔 것이니,

아래 명기해둔 부분이 사실이 아닐 수 있다는 점을 인지해주시길 바란다.)

빨간 부분을 주목해보자.

좀 논리가 이해가 안되는 부분이 있긴 한데, 여기서 0이 인식하는 인접면은 위 4-connected에서는 상하좌우이고,

아래 8-connected에서는 상하좌우대각선들까지이다.

그래서 우리는 4-connected에서는 대각선의 정보는 다루고 있지 않기 때문에,

0과 인접한 애들 중에서 같은 값을 가지고 있는 애들끼리 그냥 같은 값으로 분류를 하는 것이다.

그런데, 8-connected에서는 인접한 애들 사이에서도 같은 값을 가진 애들인지 아닌지를 분류할 수 있다.

사실 여기서는 위 지역과 아래 지역은 떨어져있다.

위 숫자 1그룹과 아래 숫자 2그룹은 어떤 픽셀을 잡아서도 서로 같은 영역이라고 속하게 할 수 없다,

그러므로, 다른 값으로 숫자를 명기할 수 있다.

그런데 사실 이렇게 하면 8-connected가 인접한 영역을 디테일하게 따질 수 있게 되는 것 같은데, 아래를 보면 조금 다르다는 것을 알 수 있다.

(사실 이 부분이 잘못 예시가 들어진 것 같다는 생각도 있다. 왜냐하면 이 경우는 두 1영역과 2영역에 대해서는 4-connected나,

8-connected모두 인접하지 않다는 것으로 인식되는 것이 맞다는 생각이 들기 때문에...)

 

이 때, 4-connected와 8-connected 영역을 혼용하여 사용할 수 있다고 한다.

예를 들어서 0의 값을 가진 픽셀에 대해서는 4-connected를 쓰고, 1의 값을 가진 픽셀에 대해서는 8-connected를 사용할 수 있는 것이다.

여기서 좀 나는 이해하는데 오래 걸렸는데,

0	0	0	0	0		a	a	a	a	a
0	0	1	0	0		a	a	1	a	a
0	1	0	1	0		a	2	b	3	a
0	0	1	0	0		a	a	4	a	a
0	0	0	0	0		a	a	a	a	a

먼저 0과 1의 값을 가진 픽셀에 대해서 모두 4-connected를 쓰게 되면 다음과 같이 인식한다고 한다.

그 이유는 먼저 빨간 부분에서 이미지를 읽을 때 1이라는 숫자가 존재한다는 것을 알게 된다.

이 때 이 1이라는 숫자는 위 a라는 픽셀을 기준으로 하여 새로운 숫자이기 때문에, 1이라는 숫자가 명명된다.

0	0	0	0	0		a	a	a	a	a
0	0	1	0	0		a	a	1	a	a
0	1	0	1	0		a	2	b	3	a
0	0	1	0	0		a	a	4	a	a
0	0	0	0	0		a	a	a	a	a

이제 이 부분을 보자.

여기서 두 영역이 마주쳤다.

그런데 이 때 두 영역은 둘 다 가운데 픽셀과 다른 1이라는 영역을 가지고 있다.

그런데, 이게 1 입장에서 상하좌우를 따졌을 때, 2라는 영역에 접근할 수 없다.

그리고 2 입장에서도 1 영역에 접근할 수 없게 되어있어서, 둘이 connect된 영역이 아닌,

다른 영역이라고 인식하게 된다.

그래서 이 경우, 1과 2로 숫자를 분리하여 적어준다.

0	0	0	0	0		a	a	a	a	a
0	0	1	0	0		a	a	1	a	a
0	1	0	1	0		a	2	b	3	a
0	0	1	0	0		a	a	4	a	a
0	0	0	0	0		a	a	a	a	a

마찬가지로, 1을 기준으로 했을 때, 사방이 모두 0으로 다 다른 숫자라는 것을 알 수 있다.

그래서 다른 숫자를 적어 주어야 하는데, 이 때, 다른 숫자를 적어줄 때,

b 기준에서 나머지 a영역은 인접한 영역이 안되고,

a 기준에서도 마찬가지로 인접한 영역에 들어오지 않기 때문에, b라는 새로운 영역으로 표기 해준다.

 

하지만, 8-connected영역의 경우, 대각선 영역까지도 인접한 영역으로 보기 때문에, 달라진다.

0	0	0	0	0		a	a	a	a	a
0	0	1	0	0		a	a	1	a	a
0	1	0	1	0		a	1	a	1	a
0	0	1	0	0		a	a	1	a	a
0	0	0	0	0		a	a	a	a	a

이 경우에는 모두가 1 또는 a로 표현될 수 있는데, 그 이유는 1 기준으로 상하좌우는 0, 대각선 아래쪽은 1이므로, 일단 1과 같은 값인 1들은 1로 표시해준다.

그리고 다른 값인 0들은 a로 표시해주는데, 이때, 1 아래쪽에 기존에 b라고 표시되어 있던 애 또한 a라고 표시해준다.

그 이유는 그 위치에서 상하좌우대각선의 인접한 영역을 기준으로 하였을 때, 보라색 영역처럼

대각선의 영역과 같은 값을 가지고 있으므로, 같은 영역이라고 인식하여 a라고 같이 명시할 수 있다.

이렇게 8-connected와 4-connected라고 표현함에 따라서 같은 binary 이미지를 다르게 표현할 수 있다.

 

뒷 내용을 더 정리해보자면,

부분적으로 processing을 하고, 그 부분이 연결되어 있다는 사실을 알게 되면, 같은 영역이라고 정의하는 방법에 대해서 나와있다.

그리고 iterative algorithm 이라는 라벨링 방식이 있는데, 그 방식은 쉽게 1이라고 표현된 부분을 찾아서 찾는 순서대로

번호를 매기는 방식이다.

그리고 classical algorithm의 경우, iterative algorithm의 변형 버전인데,

일단 같은 영역이라고 단순히 생각하는 부분끼리 인덱싱을 진행한다.

그리고 같은 영역을 가진 숫자들의 집합을 구해버리는 것이다.

 

이 방법의 알고리즘을 세세하게 파고들 필요는 없을 것 같아서 간단히 알아보자면,

 

1	1	1	0	1	1	1
1	1	1	0	1	1	1
1	1	1	0	1	1	1
0	0	0	0	0	0	0
1	1	1	1	0	0	0
1	1	1	1	0	0	0
1	1	1	0	0	0	0

원래 이런 영상들을 classical algorithm을 통해 아래와 같이 분류하였다고 해보자.

1	1	1	0	3	3	4
1	1	1	0	3	3	4
1	1	1	0	3	3	4
0	0	0	0	0	0	0
2	2	5	5	0	0	0
2	2	5	5	0	0	0
2	2	5	0	0	0	0

그러면 같은 분류를 가지는 숫자들의 집합은 A={1}, B={2,5}, C={3,4} 이렇게 되는 것이다.

이렇게 다른 숫자로 분류되었을 지라도 나중에 집합으로 같은 영역을 나타내는 숫자들의 모임값을 받게 되어 classification을 진행할 수 있다는 것이다.

이거는 한번 훑는 것으로도 인접한 영역을 알아보는데 좋은 방식이다.

그리고 그 외 DFS, 공간 효율적인 탐색방법, 가동 범위를 효율적으로 하는 탐색방법 등등이 있는데, 이거는 알고리즘에 관심있는 분들만 따로 읽어서 찾아보셨으면 한다.

이렇게 오늘 labelling에 대해서 알아보았다.