Lovelyredsky

아래 동영상은 ByteArray.org에서 제작한 prototype입니다. 재밌는 아이디어 같아서 알고리즘을 분석해봤습니다.
ByteArray에서는 다음과 같이 설명했습니다. 하지만 너무 간단해서 쉽게 이해하긴 어렵습니다.

• Iterate the marker searching on each orientation, one by frame rendered (top red, top blue, top green, top red, top blue, …)
• If a marker is found, keep the searching on the corresponding orientation only
• When the marker is lost, iterate on the 3 orientation (point 1) until a marker is found

샘플 소스는 >원문에서 다운받을 수 있습니다. 이제 as source를 보면서 알고리즘을 확인해보겠습니다. 가장 핵심인 track함수를 보면

for (i = MARGIN;i < w - MARGIN;i++) {
	for (j = MARGIN;j < h - MARGIN;j++) {
 
		// 3 points
		// MARGIN 기준의 크기 삼각형에서 각 꼭지점의 픽셀값을 가져온다
		r=buffer.getPixel(i, j - MARGIN);
		g=buffer.getPixel(i - MARGIN / 2, j + MARGIN/2);
		b=buffer.getPixel(i + MARGIN / 2, j + MARGIN/2);
		...

위 부분은 maker를 detect하는 영역을 설정하는 것입니다. MARGIN(=6)값의 크기로 삼각형 모양을 만드는데, 이 영역을 좌상단부터 우하단까지 쭉 체크하면서 marker를 찾습니다. 잘 이해가 안가는 부분인데 간단하게 아래 이미지를 보면 됩니다. 삼각형의 세 꼭지점을 각각 r, g, b로 지정하고 있습니다. 이제 각 pixel의 color값을 가지고 marker를 찾아내는 것입니다.

그럼 이어서 마커를 찾아내는 부분의 logic을 보면,

for (i = MARGIN;i < w - MARGIN;i++) {
	for (j = MARGIN;j < h - MARGIN;j++) {
	...
	// Red color가 위에 위치했을 경우
	// (r & ftop)>>btop : r pixel에서 red값 추출
	// (g & ftop)>>btop : g pixel에서 red값 추출
	// (b & ftop)>>btop : b pixel에서 red값 추출
	// rg, rb : r pixel에서 red가 green, blue보다 더 큰 값을 가지는 지에 대한 계산값. 1보다 크면 r pixel에서 red가 g,b보다 크다
	// g pixel, b pixel에 대해서도 같은 계산을 수행하여 삼각형의 각 꼭지점이 red(top), green(left), blue(right)인지 확인한다
	rg = ((r & ftop)>>btop)/((g & ftop)>>btop);
	rb = ((r & ftop)>>btop)/((b & ftop)>>btop);
	gr = ((g & fleft)>>bleft)/((r & fleft)>>bleft);
	gb = ((g & fleft)>>bleft)/((b & fleft)>>bleft);
	br = ((b & fright)>>bright) / ((r & fright)>>bright);
	bg = ((b & fright)>>bright) / ((g & fright)>>bright);
 
	f=0;
 
	//r, g, b pixel이 orientation 조건에 모두 적합한가?
	if (rg>1 && rb>1 && gr>1 && gb>1 && br>1 && bg>1){
		// 6개 평가값의 평균을 증폭한다
		// SENSIBILITY : 민감도. 작으면 더 strict하게 감지한다.
		f=((rg+rb+gr+gb+br+bg)/6)*SENSIBILITY;
		// 기준보다 크면 255=0xff를, 아니면 0=0x00의 픽셀값을 리턴
		f = f > 255  ? 255 :f;
	}
 
	// score : 감지한 이미지를 그리는 canvas
	score.setPixel(i, j, (f<

주석을 보면 감이 잡히겠지만 다음과 같이 해석하면 됩니다. 우선 marker의 모양을 보면 red, greed, blue로 3등분되어 있습니다. 모양이 육각형인 것은 별 의미 없고 단지 잡기 편하기 위해서 정도로 보이구요.
그래서 소스를 보면 일단 red 색상이 위로 가도록 들었을 경우를 가정하고 생각을 해보면 bit 연산을 통해 r 픽셀의 red color값을 g, b 픽셀의 red color값으로 나눈 rg, rb값이 1보다 크다면,  r 픽셀이 g, b보다 red color값이 더 진한 것으로 판단할 수 있습니다.
그리고 g와 b에 대해서도 같은 방법으로 각각 계산을 합니다. 그래서 rg, rb, gr, gb, br, bg값이 모두 1보다 크다면 위 마커 이미지의 삼각형처럼 r, g, b 픽셀이 각각 red, green, blue 색상이 강한 삼각형을 구성하고 있다고 생각할 수 있게 되는 것입니다.

마지막으로  이렇게 삼각형이 구성된 경우를 필터링하기 위해 6개 값의 평균을 구하고 이를 SENSIBILITY값으로 증폭시킵니다. 실제 상황이라면 조명과 같은 빛의 조건이나 환경에 따라 이 값의 튜닝이 필요할 겁니다. 계산된 f값이 기준인 255보다 크다면 detect image(score)에 기록을 합니다. 기준값이 255도 임의로 정해진 것이고, 역시 조건에 따라 튜닝을 할 수 있습니다. 이 부분이 가장 핵심이라고 할 수 있는 marker의 감지에 대한 logic을 분석해봤습니다. 샘플 소스에서는 그 밖에도 detected image를 처리하는 logic도 찾아볼 수 있습니다.

그리고 다음의 source를 보면 red color가 위에 위치한 기준으로 삼각형을 체크했을 때 결과가 false라면, green, blue color값을 기준으로 순서대로 삼각형을 체크하면서 orientation을 결정하도록 되어 있습니다.

			if (!tracking) {
				// 감지가 안된 경우 top color의 기준을 red > green > blue의 순으로 순환하면서 검사하도록 설정 변경
				topTrack++;
				if (topTrack == 3)topTrack=0;
				setTrackOrientation(topTrack);
			}

굉장히 smart한 소스라고 생각됩니다. 성능을 위한 최적화도 상당히 고려되어 있구요. 샘플에서는 marker가 R, G, B 3가지 색상의 wheel이지만 다른 색을 추가한 marker도 가능합니다. 물론 색이 많아질 수록 marker의 인식에 대한 문제나 marker의 인식을 위한 삼각형의 크기 등을 고려한 튜닝이 필요하겠지요. 어쨌든 color wheel을 이용해서 이동/회전 등의 동작 인식이 가능한 interaction을 구성할 수 있겠습니다.

결과적으로 위의 로직을 간단히 정리한 것이 다음 이미지입니다. 처음 보면 뭔지 모르겠지만 위의 내용을 알고 보면 이해할 수 있을 겁니다.