CV2011. 8. 10. 00:57

살펴보기..

openCV에 신기하게도 라벨링이 없는듯하다.


라벨링 (Labeling) 이란  바이너리 이미지 ( 0과 1만 있는 이미지)

로 처리하는 과정 중에서 독립된 개체를 찾아서 라벨을 붙여주는 알고리즘이다.


여기서 배경 (back ground) 는 0

전경 (fore ground) 는 0이 아닌 것 으로 정의한다.


라벨링 형태는 여러가지가 있는데

4-connected,  8-connected ,...

등 연결 형태에 따라 전경은 달라진다.

 



둘의 차이는 간단하다.

4-connected 의 경우는 상하좌우 4개중에 하나가 전경이면 그놈과 하나로 연결되어 있다고 보는것이다.

8-connected 의 경우는 상하좌우 & 대각선 4방향 까지 연결되어 있다고 보는 것이다.

이 두개는 매우 중요한 이슈인데 이후, hole (전경에 의해 둘러싸여 버린 0인 지역) 까지 찾게 될때

hole 자체를 4-connected 냐 8-connected 냐 어떻게 따지느냐에 따라서 매우 달라지게 된다.

이외에도 이미지 픽셀 배열이 벌집 모양 (육각형)인 경우도 있고, 연결 형태는 상당히 많다.

여기서는 4-connected 위주로 볼것이다.



재귀 알고리즘 ( flood fill labeling )


흔히 라벨링에 대해서 구글링, 검색을 하게 되면 이 알고리즘이 나올 것이다.

이는 그림판의 fill (페인트통 쏟는 모양 버튼) 과 똑같은 알고리즘으로서 

만일 현재 1번 라벨을 붙이려고 한다면

전경인 픽셀에 대해서 라벨을 찍고

상하좌우 4방향에 대해 다시 재귀 호출하는 형태의 간단한 알고리즘이다.


다만 이미지의 크기는 상당히 크므로 픽셀 연결이 많으면  스택 오버플로가 날 여지가 있어서

실제로 구현은 대개 자료구조 스택을 만들고 나서 이를 사용한다.

이는 매우 간단한 방식이고 상식선에서 사용할 수 있겠다.




2-pass labeling 알고리즘


재귀적인 방식은 스택 오버헤드와 중복 호출이 발생한다.

하지만 생각보다 간단한 알고리즘으로 이미지를 2번만 스캔하여 라벨링을 하는 것이 가능하다.

굉장히 빠르게 라벨링을 하게 되는 것이다.


1-pass



전경의 각 픽셀을 래스터 스캔한다.

이때 좌 방향의 픽셀과 상 방향의 픽셀을 살펴서 두개 다

기존 라벨이 아니라면 (배경이였다면), 새로운 라벨을 붙인다.




상단 픽셀은 기존 라벨이 없었지만 , 좌측 픽셀엔 라벨 1이 붙어 있으므로

연결 시킨다 , 즉 좌측이든 상단이든 두개의 픽셀에 대해서 라벨이 하나 붙어 있다면

해당 라벨로 찍어준다.





계속 래스터 스캔하면서 해당 작업을 반복한다.

좌측 픽셀이 라벨이 아니지만 상단 픽셀이 라벨 2가 붙어있으므로 해당 픽셀을 라벨 2 붙인다.




그렇다면 좌측과 상단 모두 라벨이 붙어 있는 경우인데 라벨이 다른 경우 어떻게 처리를 해줘야 할까???



이런 경우는  두개의 라벨 (3 과 4 라벨) 이 서로 같다는 표식을 테이블에 남긴다.

(3 = 4)


이렇게 1-pass 과정을 래스터방식으로  한번 스캔하게 되면

각기 다른 라벨과 테이블이 만들어진다.

이젠 테이블 정보를 이용해서 (3 과 4 라벨은 같은 라벨이다) 

최종 라벨링을 한다.




2-pass


하지만 이런 경우가 생길수 있다.

 

테이블이 연쇄적으로 되는 경우  테이블 안에서 또 반복하게 될 수도 있다.

즉 라벨 1과 똑같은것이나 마찬가지인 라벨들이 총 몇개나 있는지 세야하는 반복이 발생하는 것이다.

따라서 이러한 오버헤드를 줄이기 위해서 넉넉한 메모리를 잡고

인덱스로 참조하게 하여 O(1) 시간에 테이블을 이용한 라벨링이 가능하다. 


 
즉 pass-1 과정에서 기록된 라벨들은 인덱스인 것이고 실제 값은  테이블에 들어가 있는 형태인 것이다. 

따라서 pass2 과정에서는 pass1 라벨들을 래스터 스캔하면서 인덱스로 하여 테이블에 저장된 값을

pass2 에 라벨링한다. 테이블에 저장된 값은 두개의 라벨(인덱스)이 같을 경우에

각각의 인덱스에 해당되는 테이블 값 두개를 같게 만들어준다. ( 1-pass 과정에서)




2-pass 과정에서

인덱스를 참조해서 테이블에 저장된 값을 그대로 쓰게 되는 것이다.


다만 이 경우는 서로 다른 라벨로 구분하기만 하면 될때 이고

라벨의 번호가 중간에 건너뛸 가능성이 있다.


위쪽 화살표는 테이블의 값이 변경되는 곳이 어디인가를 나타낸다.

테이블의 값은  라벨1 과 라벨 3으로써  구분이 되긴하지만 건너뛰게 되었으므로

2-pass를 거치고 나서도 정확히 몇개가 생성되었는지 파악 못할 가능성이 있다.


라벨의 번호도 순차적으로 붙는것이 좋아 보인다. 따라서

테이블을 2개를 둔다.


빨간 네모가 현재 래스터 스캔하고 있는 픽셀이라고 할때

2-pass 과정에서 어떻게  테이블을 참조하여 값을 집어 넣는 것인지 과정을 보이는 것이다.


그 다음 픽셀은 다음과 같은 과정을 거치게 된다.

 

마치 더블 포인터 같은 느낌으로 이해하면 될 것이다.




실제 코드를 작성해 보았다.

opencv 가 필요하다.


input 이미지가 binary 임을 가정해야 하지만

threshold 값으로 짤랐다. 밝기 값이  threshold 이상이여야만 전경(fore ground) 인 것이다. 

table1, table2 는 int 형 1차원 배열이다.

인덱싱을 위한 배열로서 외부에서 메모리를 잡고 인자로 넘겨준다.

이 두개 인자의 크기는 최대 이미지 크기의 절반일 것이다. (체스판의 경우) 

따로 범위 체크를 하지 않으므로 메모리는 신중하게 해야 한다.


pass1, pass2 도 int 형 1차원 배열이다. 

요놈들의 배열 크기는 이미지 크기와 같아야 한다. (img->width * img->height)

pass2 에 라벨링 최종 결과가 담기며

각 원소에 접근하려면

pass2 [ y * img->width + x]

같은 식으로 접근한다. 



위 코드의 실행 결과


실험이미지는 다음과 같다.

 



요 이미지를 가지고 위 코드를 수행하게 되면 다음과 같은 결과가 나온다.



즉 라벨에 따라서 6개의 색을 순환하면서 칠하게 된다.

pass2 배열에 순전히 라벨 값들이 기록되어 있으므로 

이는 대충 아무렇게나 응용하면 된다.
 
Posted by 멍충한아싸

댓글을 달아 주세요

  1. 양반

    헐... 좋은 글이네요.

    2011.08.10 04:02 [ ADDR : EDIT/ DEL : REPLY ]
  2. ksdskd9

    좋은 자료 감사합니다.

    2012.02.15 13:08 [ ADDR : EDIT/ DEL : REPLY ]
  3. 감동...

    와....정말 감사합니다

    2012.06.17 01:23 [ ADDR : EDIT/ DEL : REPLY ]
  4. histro

    2-pass labeling 알고리즘 관련 논문 좀 알수있을까요?

    2012.06.20 15:25 [ ADDR : EDIT/ DEL : REPLY ]
  5. 허허

    우분투에서도 잘되는가보군요

    2013.03.16 19:18 [ ADDR : EDIT/ DEL : REPLY ]
  6. 냉면

    덕분에 많이 알아갑니다. 감사합니다!!

    2013.03.26 07:47 [ ADDR : EDIT/ DEL : REPLY ]
  7. parkinje

    사랑합니다

    2013.11.27 14:43 [ ADDR : EDIT/ DEL : REPLY ]
  8. 굳굳

    좋은자료, 감사합니다.. 배워갑니닷

    2014.07.25 15:51 [ ADDR : EDIT/ DEL : REPLY ]
  9. 으잉?

    안돼요

    2015.07.09 18:05 [ ADDR : EDIT/ DEL : REPLY ]