휴가 기간에 뭐를 하며 보낼까 고민하던 중 Template matching이라는 재밌는 녀석을 알게 되었고 이에 필요한 자료를 읽어보며 시간을 보내게 되었습니다.
그러던 중 Template matching을 어이없는 곳에 이용해 보게 되었는데요. 바로 World of Warcraft 즉, 와우라 불리는 온라인 게임의 자동 낚시에 응용해 보게 되었습니다.
건설적으로 이용할 데도 많은데 하필 게임내 낚시를 자동화하는데 이용했냐 싶겠지만 어디까지나 Template matching을 테스트해 보기 위한 하나의 샘플 작업이었습니다.
이 Template matching에 대해 조금 자세히 알아보겠습니다.
Template matching은 간단히 말해서 하나의 Template Image를 입력된 Source Image에서 찾아내는 것을 말하며 얼굴인식, 물체 인식, 자동차 번호판 인식 등 다양하게 응용되는 분야입니다. 저는 이 중에서 물체 인식에 해당하는 낚시찌를 찾는 데 사용했지만 말이죠. ^^;;;
이를 구현하는데는 여러 가지 방법이 존재하는데 그중에서 관계 맵(Correlation map)을 생성해서 찾는 방법이 가장 일반적인 듯합니다. 이 분야는 처음 접하는 거라 사전 지식이 많지 않네요.
Normalized Cross Correlation(이하 NCC)은 정규화된 상호 연관성을 찾는 방식으로, 입력된 이미지와 찾고자 하는 이미지간의 밝기의 선형적인 차이 및 기하학 적인 유사도를 측정하는 방식이라고 합니다.
재밌는 것은 이 NCC 값의 특징은 화소들의 밝기의 곱 또는 합의 경우에도 불변한다는 것입니다.
이러한 특징을 갖는 NCC의 공식은 아래와 같습니다.
언뜻 복잡해 보이지만 사실 내용은 간단합니다. I는 원본 이미지, T는 Template 이미지를 의미하며 각각의 픽셀에 대해 위의 수식을 대입하여 나온 Result(R) 값이 Template과 Source이미지 사이의 원하는 해당 픽셀의 관계 값이 되는 것입니다.
실제로 이 수식을 적용하여 코딩을 해 보면 R(x, y) 즉, x, y에 해당하는 결과 값은 -1 ~ 1 사이의 실수 값으로 계산되어 나옵니다. 이것을 우리가 알아보기 편하도록 8bit 밝기의 값(256단계의 값)으로 변환하면 관계 맵(Corrleation map) 이미지를 얻게 되는 것이죠.
그럼 보기 편하도록 와우의 낚시를 이용해서 계산되어 나온 관계맵을 이미지로 보도록 하겠습니다.
아래의 이미지가 게임 화면에서 찾아야 하는 Template Image인 낚시찌가 되겠습니다.
그리고 이 Template Image를 검색할 Source image는 아래와 같습니다.
Template Image인 낚시찌가 게임 화면에서 얻어온 Source Image 안에 있는 낚시찌와 크기가 다른 것을 알 수 있습니다. 밝기도 물론 다릅니다. 이런 상황에서도 NCC를 적용하면 낚시찌의 위치를 찾아낼 수 있는데요. 이 두 개의 이미지를 위에서 알아본 NCC 수식을 이용해서 관계 맵을 생성해 보면 아래와 같은 관계 맵을 얻을 수 있습니다.
여기서 알아 두어야 할 것은 Source Image의 넓이와 높이를 각각 W, H라고 하고, Template Image의 넓이와 높이를 각각 w, h라고 했을때 관계 맵의 넓이와 높이 w', h'은 w' = W-w+1. h' = H-h+1로 계산하여 사용합니다. 이론적인 부분은 그렇다 치고, 이렇게 나온 관계 맵은 아까 설명한 대로 -1 ~ 1 사이의 실수 값이므로 이를 사람이 눈으로 보기 편하도록 0~255단계의 음영 값으로 변환하여 픽셀 별로 적용을 하면 위와 같은 관계 맵 이미지가 생성됩니다.
이 관계맵에서 가장 밝은 부분(Max값)이 Template Image와 가장 돈독한(?) 관계를 형성하는 곳인데요. 즉, 관계 맵에서 가장 큰 값(Max값)을 갖는 곳의 좌표가 Template Image와 일치하는 지점입니다.
이 관계맵을 3차원 그래프로 표현해 보면 더 확실히 알 수 있습니다. 하지만... 아쉽게도 엑셀의 차트가 지원하는 최대 크기가 255x255인 관계로 관계 맵을 255, 255 크기로 잘라서 차트로 만들어 보았습니다.
차트에서 보는것 처럼 가장 피크가 높은 곳이 이미지 우하단의 밝은 하얀 부분이며 그 위치가 Template Image와 가장 유사한 지점이 되겠습니다.
문제는 이론대로 함수를 제작해서 테스트를 해보니 속도가 너무 느려 실제로 적용하기 힘들 지경이었습니다. Template Image의 크기가 10x10 pixel이고 Source Image의 크기가 100x100 pixel이라고 가정한다면 관계 맵을 생성하기 위한 연산 횟수는 10x10x100x100 = 1,000,000번의 연산을 거쳐야만 합니다.
위의 그림 처럼 모든 픽셀을 비교하여야 하기 때문인데, 비교 자체야 빠르게 처리할 수 있지만 Template Image 밑에 위치한 Source Image와의 관계도를 계산하기 위해서는 많은 시간이 소요됩니다. 하지만 속도를 올리기 위한 다양한 방법론은 여러 가지가 존재하니 편한 것으로 적용하면 되겠습니다.
이렇게 해서 Template matching의 적용은 끝이 났습니다. 이제는 와우의 게임 화면을 캡춰하여 얻은 Source Image에서 낚시찌의 위치를 찾을 수 있게 되었습니다.
이제는 찾은 위치의 낚시찌에서 물고기가 낚였는지를 판단해야 하는 일이 남았는데요. 와우의 낚시찌를 보면 상하좌우로 출렁출렁 거리며 움직이다가 물고기가 입질을 하는 순간 찌가 물속으로 들어가며 물보라가 치는데 이때 빠르게 마우스 오른쪽 버튼으로 낚시찌를 클릭해야 낚시가 성공하게 됩니다. 이것이 와우의 낚시 방법입니다.
참 간단합니다. 물론 사람이 하면 간단하다는 거죠 ^^;
그럼 이제 물고기가 입질하는 순간을 어떻게 알아 내느냐가 새로운 문제가 되겠습니다.
다양한 방법을 시도해 볼 수 있겠는데 간편하게 시도해 볼 수 있는 낚시찌의 특정 픽셀들의 움직임 변화를 통계 내어 가장 많은 이동양을 가진 때를 입질 한 순간으로 인식하는 방법이 있겠습니다.
이렇게 구현해도 일반적인 상황에서 작동은 잘 하는데요. 문제는 이 방법으로 구현했을 때 3D 게임이다 보니 게임 내 낮과 밤 또, 주변 환경에 따른 Diffuse값이 변하게 되는데 픽셀 비교로는 평균값을 얻기가 수월치 않으며 정확도도 떨어지더군요. 낚시가 잘 되는 지역이 있는가 하면 인식률이 현저히 떨어지는 지역도 발생했습니다.
그래서 이번에는 물체의 특징점을 추출하여 특징점의 갯수 변화를 통해 입질 여부를 판단하도록 해 보았습니다.
아래의 애니메이션은 와우의 낚시찌 움직임을 보여주는 것입니다.
보시는 것처럼 상하좌우로 움직이다가 물속으로 들어가며 물이 튀기는 바로 그때가 물고기의 입질이 발생한 시점입니다.
이 영상에서 낚시찌의 특징점을 추출하여 보면 아래와 같이 특징점들의 변화를 추적해 볼 수 있습니다.
애니메이션 끝부분에서 물이 튀어오를때 수많은 특징점들이 발생하는 것을 알 수 있습니다. 이 시점을 입질 한 시점으로 판단하고 적용해도 될 것입니다. 즉, 특징점의 변화량이 가장 클 때 낚싯대를 당기면 되는 것이죠.
이렇게 구현해서 테스트해 본 결과 낚시 성공률은 와우의 월드 전지역에서 98% 이상의 성공률을 보여줬습니다. 여러 명이 근처에서 낚시를 할 때 다른 사람의 낚시찌에 대한 처리를 하지 않았기 때문에 발생하는 오류 등으로 100% 성공은 되지 않네요.
아래 이미지는 지금까지 설명했던 내용을 실제로 구현한 프로그램입니다. 게임 화면을 얻어와서 낚시찌의 위치를 찾고 특징점의 변화량을 측정하여 낚시대를 당기는 기능을 하는 자동 낚시 프로그램으로 정해진 횟수만큼 자동으로 낚시를 하는 것이죠. 낚시찌를 찾는데(Template matching) 소요되는 시간은 평균 38ms 였습니다.
Template matching을 구현해 보기 위한 하나의 예제로 탄생한 자동 낚시 프로그램. 빈대 잡으려고 초가삼간 태우는 겪이랄까요. 훌륭한 방법론을 엉뚱한 곳에 적용해 보았습니다만 Template matching에 대해 이해하고 간단한 예제를 통해 구현해 보려던 목적은 달성한 거 같습니다.
여담이지만 와우의 자동 낚시 프로그램은 인터넷에서 쉽게 구할 수 있더군요. 성공률이 30%도 안되는 것부터 90% 이상의 성공률을 보이며 다양한 기능이 내장된 프로그램도 있었습니다.
게임 내 작은 부분이지만 자동화된 툴을 사용하는 것은 게임의 재미를 해치는 방법 중 하나입니다. 사용은 개인의 몫이지만 책임이 따르는 행동이라는 것도 잊지 말아야겠습니다.
이렇게 샘플 작업을 통해 Template matching에 대해 맛보기 정도로 구현 방식에 대해 이해한 정도가 되었네요.
이 내용을 좀 더 발전 시켜서 얼굴 인식 쪽으로 짬날 때 작업을 해보고 싶어 졌습니다.
