MSER ( Maximally stable extremal regions )

Vlfeat's MSER Implementation

VLFeat에서 MSER에 대한 설명 : http://www.vlfeat.org/api/mser-fundamentals.html

VLFeat의 경우, 노드의 Parent만 알고있기 때문에, Child를 알 수 없다.  Extremal Region을 빠르게 그리기 위해, 새로운 데이터 구조( Data Structure)가 필요했다. 그래서, VLFeat 코드 분석 후 새로운 데이터 구조로 MSER를 구현하였다. 다음은 새로 만든 데이터 구조를 1차원 신호에 적용한 예이다. 각 노드에는 Parent와 Shortcut,Child, Next의 링크가 존재한다. Parent는 나의 부모 노드를 가르킨다. Next 노드는 같은 레벨의 값을 가진 경우, 연결된다. child는 자신의 값보다 작은 경우를 연결할 때 자식 노드로 연결된다. - 여기서 child 노드는 1차원이라 최대 2개가 될 수 있지만, 영상의 경우, 최대 8개의 child를 가질 수 있음을 주의해야한다. perm은 bin sort를 이용해서 구한 배열이다. MSER의 알고리즘을 정리하면,         1. Bin sort를 수행하여 intensity 값이 낮은 순으로 정렬한다.         2. 트리를 생성한다.         3. Extremal Region 후보를 찾는다.         4. 강건한 Extremal Region을 골라낸다.         5. 크기 등의 조건을 통해, 불필요한 Extremal Region은 제거한다.

- 구현 결과

다음과 같은 영상을 얻을 수 있다.

같은 색의 연결된 경우 하나의 Extremal Region을 나타낸다.

중요한 것은 상위의 Extremal Region은 하위의 Extremal Region을 포함하기 때문에,

A색으로 표현된 것이 다른 색들을 감싸고 있다면 A색의 내부는 모두 하나의 Extremal Region이다.

Linear Time Maximally Stable Extremal Regions

2.2 Basic Algorithm 알고리즘은 다음과 같은 데이터 구조를 필요로 한다. 1) Binary Mask : 방문한 화소인지를 판단하기 위함. 2) Priority queue of boundary pixels : 방문한 화소들 중, 레벨값이 낮은 값부터 처리하기 위한 큐 3) Stack C : 컴포넌트의 정보를 포함한다. 컴포넌트의 정보는 픽셀 값, 1차-2차 모멘트 등과 같은 정보를 포함하며, 스택의 최대 크기는 gray-level의 수 일 것이다. ※ 개념 - 알고리즘의 기본 개념을 설명하자면, 시작 위치부터 이웃 화소들을 검사하며 현재 화소보다 이웃 화소의 레벨값이 낮은 경우 스택에 push하면서 local minimum을 따라간다. - 로컬미니멈 방향으로 진행 도중, 현재 화소값보다 높은 이웃화소를 만난다면, 스택의 정보를 이용하여 이웃 화소 레벨값까지 트리를 생성한다. - 이를 반복하면서 트리를 생성한다. - 해당 코드의 경우에는, 현재 화소와 이웃화소의 레벨이 같은 경우 별도로 노드를 생성하지 않는다.   - 아마도, 좌표가 중요한 것이 아니라, 모멘트와 영역의 크기만을 구하기 때문인 듯 하다. - 위의 그림은 스택 구조와 원리는 설명하는 그림이다. 그림과 같이 수도꼭지에서 물이 떨어지는 위치가 시작 위치라고 가정하자. 초기에 스택은 비어 있을 것이다. 따라서 스택에 처음 만나는 값을 노드를 만들고, 스택에 저장한다. 그 다음으로 만나는 구간인 1번과 2번 사이에서는 이전 보다 레벨이 낮다. 따라서 단지 스택에 추가할 것이다.  - 그리고 3번을 만난다. 3번은 2번보다 레벨이 높다. 따라서, 3번을 부모로 하고, 2번은 3번 자식으로 트리를 구성한다. 4번도 3번보다 레벨이 높다. 따라서 4번을 부모로 하고, 3번은 4번의 자식으로 트리를 구성한다.  - 그리고, 다시 5번까지는 레벨값이 낮아지기때문에 스택에 추가만 수행한다. - 논문에 나온 위의 그림을 시간 순으로 살펴보자 a) 1번~ 2번 구간까지 진행되면서 스택에 추가만 될 것이다. b) 3번이 입력되면 2번은 3번의 자식으로 트리가 구성된다. 따라서 스택에는 2번은 존재하지 않는다. c) 4번이 입력되면, 다시 3번이 4번의 자식으로 트리가 구성된다. d) 5번은 다시 현재 레벨값보다 낮아지므로 스택에 추가만 된다. e) 6번은 5번보다 레벨이 높으므로 5번은 6번의 자식으로 트리를 구성한다. - 따라서 위의 그림은 중간 과정은 생략하고 (e) 상태의 그림을 보여주는 것으로 이해하면 된다. 결론, 사실 알고리즘은 구현은 매우 심플하다. 하지만, 이걸 이해하는데는 엄청난 노력이 필요할 듯 하다. 너무 헷갈린다. 어쨋든 알고리즘의 철학을 정리해보면 다음과 같다. 1) 로컬 미니멈 방향으로 따라간다. 2) 현재 레벨값보다 낮다면 스택에 추가한다. 3) 현재 레벨값보다 크다면 스택을 이용해서 트리를 구성한다. 아마 이러한 과정을 2차원 확장하면 상상이 되지 않는다.  구현 관점에서 중요한 데이터 구조를 정리하면, 1) binary mask : 방문 여부를 판단하기 위해 2) priority queue : 처리해야할 후보 화소들 중에 가장 레벨이 낮은 화소를 먼저 처리하기 위해 사용함      - 예를 들어, 현재화소보다 이웃 화소들이 모두 레벨이 높다면, 그중에서 가장 낮은 레벨을 갖는 이웃을 먼저 처리하기위함.      - 또 다른 이유로는, 다음에 검사할 화소를 좀 더 빠르게 찾기 위함. 3) stack : 레벨과 연결성을 모두 고려하여 트리를 생성하기 위함.      - 스택은 노드의 포인트만 가지고 있음      - 스택의 크기는 최대 257이하이다. ( gray level(256:0~255) + dummy(1) )

위의 예제로 든 1차원 데이터에 따른 알고리즘 결과 비교

Linear time algorithm

<그림 5>

원래 알고리즘에서 수정한 결과 ( 영역 표현을 위함 )

<그림 6>

그림 5와 6의 차이는

- 그림 5의 경우 노드가 상대적으로 적지만, extremal stable region을 찾아도, 그 영역을 이루는 화소들을 알 수 없다.

이러한 문제를 해결하기 위해, 그림 6과 유사하게 링크를 하나 더 만들었다.

아래 그림 7과 같이, 기존 구조와 같으나, eqnext라는 링크를 하나 더 추가하여 레벨값이 같고 연결된 경우에는 dummy node로 연결하였다. 따라서 child node 중에서 extremal stable region을 선택하면 해당 영역을 나타내는 영역을 시각화 할 수 있다.

<그림 7> 그림 5의 구조에서 dummy node 추가한 데이터 구조

구현 결과 영상

연산 속도 비교 ( 1280 * 720 영상 )

알고리즘	연산 시간	비고
Original MSER	167.720 ms
Original MSER(D)	284.788 ms
Linear time MSER	44.561 ms	불필요한 노드를 만들지 않기 때문
Linear time MSER (D)	57.832 ms