448 정보과학회논문지 : 소프트웨어및응용제 41 권제 6 호 (2014.6) 조도변화와바둑돌미세위치변화를고려한 CHT 기반의자동바둑기보시스템 (CHT-based Automatic Go Recording System under Illumination Change and Stone Dislocation) 박동진 전경구 (Dongjin Park) (Kyungkoo Jun) 요약본논문에서는영상처리를통해바둑대국의기보를자동으로기록하는시스템을개발한다. 자동바둑기보생성을위해두가지시도가있었다. 첫째는바둑판위의교차점들을검출하는방식이었다. 본논문에서는이와는차별성을지닌새로운방식을제안한다. 두번째방식은새로운바둑돌이놓이기전과후두영상의차이를이용하여위치를검출하였다. 하지만이방식은조도변화가있거나, 대국자의건드림에의해기존바둑돌들의위치가미세하게변할경우검출에어려움이있다. 이는바둑돌모양인원을검출하는방식이아닌차이가발생한픽셀개수를기준으로하기때문이다. 이러한문제점을극복하기위해본논문은바둑돌원형모양검출기반방식을제안한다. 원형검출을위해허프변환을이용하지만, 관련된계산량을감소시키는방법도제안한다. 자동기보시스템을구현하였으며, 기존방식과비교한결과문제점이해결되었음을확인하였다. 키워드 : 바둑자동기보, 허프변환, 조도변화, 바둑돌, 원검출 Abstract We develop an automatic go recording system by using digital image processing. An existing scheme finds the locations of stones by counting the different pixels between two images taken before and after placing a new stone. However it is susceptible to illumination change and stone dislocation by players. It is because the scheme does not consider the circular stone shape. The proposed system exploits the circular Hough transform for the stone detection but is able to limit the computational overhead. Through the experiments, we observed that the proposed scheme is superior to the existing one. Keywords: automatic go recording system, hough transform, illumination change, go stone, circle detection 1. 서론 기보는바둑이나장기를둔내용의기록이다. 여기에는대국자가바둑돌을놓은위치와순서를기록한다. 이 비회원 : 인천대학교임베디드시스템공학과 pdjman@incheon.ac.kr 비회원 : 인천대학교임베디드시스템공학과교수 kjun@incheon.ac.kr (Corresponding author임 ) 논문접수 : 2013년 12월 27일심사완료 : 2014년 4월 12일 CopyrightC2014 한국정보과학회 ː개인목적이나교육목적인경우, 이저작물의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. 정보과학회논문지 : 소프트웨어및응용제41권제6호 (2014.6) 러한기보를이용한복기는기억력향상에많은도움을준다. 일반적으로프로기사들의대국은제3자가수작업으로기록함으로써기보가작성된다. 최근온라인원격대국소프트웨어들은자동으로기보를생성하는기능을가지고있다. 하지만오프라인상에서행해지는일반인들의대국은기보작성이쉽지않다. 이러한오프라인대국의기보생성을자동화하기위한몇가지시도가있었다. [1] 에서는바둑판교점마다기계적인버튼을설치하여, 기보를생성하는시스템을구현하였다. [2] 에서는전기적인장치를이용하여, 바둑돌이놓여지는위치를감지하여자동으로기보를생성하는시스템을제안하였다. [1] 과 [2] 는별도제작된바둑판을이용하여대국을진행해야하는불편함때문에대중화되기는어렵다. 이러한문제를보완하고자 [3,4] 에서는영상
조도변화와바둑돌미세위치변화를고려한 CHT 기반의자동바둑기보시스템 449 처리기술을이용한방법을제안하고있다. 바둑판을촬영한영상을이용하여자동으로기보를생성한다. [3] 은대국영상속에서바둑판위의교차점들을찾아내고, 해당좌표의색상정보를이용해기보를작성한다. 바둑판은총 38개의줄들로이루어져있고, 361개의교차점을만든다. [3] 은이교차점들에서색상정보를추출해바둑돌이놓여있는지를, 놓여있다면흑돌인지백돌인지를구별한다. 그러기위해서는바둑판위의정확한교차점검출이최우선이다. [3] 은대국영상속에서 Canny Edge Detection[5] 을통해에지들을검출하고, 에지영상에서 Hough Transform (HT)[6] 을통해직선들을검출한다. 마지막으로검출한직선들에서교차점을계산해교차점위치를검출한다. [3] 과본논문이제안하는방식에는두가지차별성이있다. 첫번째로 [3] 은 HT를이용해직선을검출하지만, 본논문에서는 CHT를이용해원을검출한다. 두번째로 [3] 은바둑판위의교차점을통해바둑돌의위치를검출하지만, 본논문에서는바둑돌의원모양을검출해위치좌표를파악한다. [4] 는바둑돌을놓을때마다그위치를감지하기위해서전과후두영상간의차이를계산한다. 시간 에획득한 2차원영상을 라하고, 이영상의좌표 의픽셀값을 라하자. 이때 는원영상에서그레이스케일로변환된후, 노이즈제거를위해가우시안필터링이적용된상태라고가정하자. 시간 에놓인바둑돌의위치를검출하기위한 와 영상간의차이, 는각픽셀 에대해서다음과같이계산된다. for (1) 이때, 집합 를 와 간의픽셀값차이가있는 들의집합이라고하자. for (2) 이때, for (3) 하나의바둑돌이영상에서차지하는픽셀들의개수를 이라고하자. 바둑판을위에서촬영하는카메라의위치가고정되어있고, 바둑돌의크기가일정하다고가정한다면, 의값은실험으로구할수있다. 따라서 [4] 에서 에새로운바둑돌이놓였는지여부는, 다음식을만족하는양의정수 가존재할경우이다. (4) 과 간에값이변화된전체픽셀의개수 가 의 정수배일경우, 바둑돌 개가새로놓였다는것을의미한다. 그리고이들이놓인위치는 인픽셀들간의근접정도를고려하여계산한다. 이러한연속된영상간의차이를이용하면자동기보시스템을용이하게구현할수있다. 하지만, 우리는실험을통해서이방식이두가지심각한문제점을가지고있다는것을알았다. 첫번째는조도변화에취약하다는것이다. 과 영상간에조도변화가있을경우, 새로놓인바둑돌을제대로검출하지못한다. 두번째는바둑돌의작은위치변화에취약하다. 예를들어바둑을두는도중에대국자가바둑돌을건드려위치가조금씩바뀌는경우가발생한다. 이경우작은위치들의변화의합이식 (4) 를만족시킬때, 검출에오류가발생할수있다. 본논문은이러한조도변화와미세위치변화가허용되는상황에서도동작하는자동기보시스템을제안한다. 이러한변화에따른어려움을극복하기위해, 논문에서는원형모양검출에기반한방법을제안한다. 영상에서원모양과그위치들을검출하기때문에, 기존방식과달리조도나위치변화의영향을받지않는다. 이를위해 Circular Hough Transform (CHT)[7] 를사용한다. 또한 CHT의단점인과다한연산량을줄이는방법도제안한다. 본논문은이를이용해서구현한자동기보시스템과실험결과도제시한다. 논문은다음과같이구성된다. 2장에서는 CHT에기반한바둑돌검출방식을설명한다. 3장에서는이를이용해서구현한자동기보시스템의구현과실험결과를제시한다. 마지막으로 4장에서는논문을결론짓는다. 2. CHT 기반자동기보시스템대국이진행중인바둑판을동영상촬영하여자동기보를생성하는시스템에대해설명한다. 바둑돌이원형이라는점에착안하여 CHT를이용하여영상에서바둑돌의위치를검출한다. 이렇게추출된정보들을가공하여새로놓인바둑돌만을검출하여기보를생성하게된다. 논문에서는그림 1과같은자동기보시스템을구성한다. 바둑판을촬영하는카메라의위치가고정되어있다. 따라서바둑돌의크기가일정하다면, CHT를통해검출하는원들의지름을미리결정할수있다. 이는모든가능한원지름에범위에대해원형검출을시도하는데따른계산을피할수있다. 그림 2는자동기보시스템의동작순서를보여준다. 우선시스템은카메라를통해획득된영상에대한전체계산량을줄이기위해영상을축소한다. 이때개별바둑돌검출이가능한수준에서영상크기를넓이와높이비율을유지하면서축소한다. 원영상의넓이를, 높이를 라할때, 축소목표넓이를 로정하면, 해당높이 는아래와같다.
450 정보과학회논문지 : 소프트웨어 및 응용 제 41 권 제 6 호(2014.6) 돌의 지름을 고려하여 실험적으로 얻어졌다. 축소된 영상은 그래이스케일로 변환된다. 이 결과는 두 가지 용도로 쓰인다. 첫 번째는 바둑돌의 흑백여부를 가리기 위해 사용된다. 결과에 부가적으로 이진화 과정 을 적용하면 바둑돌의 흑과 백 여부를 쉽게 판별할 수 있다. 이진화 결과는 별도 보관되어 이후 과정에서 참조 된다. 두 번째 용도는 바둑돌 위치를 검출하기 위해 사 용된다. 원모양 검출을 위해 CHT를 적용하기 전에 가 우시안 필터링을 통해 노이즈를 제거한다. 이 과정에서 바둑판의 격자 무늬 모양이 대부분 제거된다. 이 결과에 Canny edge detection[5]과정을 수행하여 에지를 검출 한다. 이러한 에지들에 CHT가 적용된다. CHT는 영상 내에서 특정 모양을 투표방식을 통해 검출하는 방법이다. 투표는 형태를 모델링하는 파라미터 공간에 대해 이뤄지는 데, 투표 결과는 파라미터 공간을 그림 1 바둑 자동기보 시스템 균일하게 나눈 축적셀에 저장된다. 예를 들어, 2차원 파 Fig. 1 Automatic Go recording system 라미터 공간의 좌표 가 파라미터 와 에 해당한 다고 할 때, 해당하는 위치의 축적셀 는 이들 파 라미터에 대한 투표결과를 저장한다. 따라서 검출과정은 임계치 이상의 투표값을 갖는 축적셀에 해당하는 파라 미터들을 찾는 것이 된다. 본 논문에서는 별다른 혼동이 없는 한 를 와 동일하게 사용한다. CHT를 이용한 원 검출은 에 대해, 에지 추출된 픽셀좌표 를 이용하여 다음 방정식을 만족 시키는 원의 중심 와 반지름 를 구한다. sin cos (6) 이 때, 픽셀 에 해당하는 을 1씩 증가 시키고, 임계치 이상의 투표값을 갖는 축적셀에 해당하 는 원을 검출한 것으로 정한다. 대국이 진행될수록 놓인 바둑돌의 수가 증가한다. 이 에 따라 에지수가 늘어나 CHT 수행시간이 비례적으로 증가한다. 그러나 이미 위치 검출이 완료된 바둑돌에 대 해서 동일 연산과정이 반복되는 것은 효율적이지 않다. 따라서 이러한 불필요한 계산과정을 제거하기 위한 방 법을 제안한다. 이전 바둑돌 위치 검출에 사용된 영상을 이라 하고, 현재 영상을 라 할 때, 두 영상간의 차이 에 대해서 CHT를 적용한다. 본 논문에서는 를 차영상이라 하겠다. 그림 2 자동기보시스템의 순서도 Fig. 2 Flow chart of Automatic go recording system for (7) 에서는 이전 바둑돌들의 에지가 모두 제거되기 때문 (5) 에 새로 놓인 바둑돌의 에지만 남게 되어 CHT 연산량 이 대폭 감소하게 된다. 하지만 모든 기존 바둑돌들이 우리는 실험을 통해, 으로 설정했다. 이는 고정 제거되는 것은 아니다. 예를 들어 대국자의 건드림에 의 된 카메라와 바둑판 사이의 거리, 카메라 해상도, 바둑 해 미세하게 위치가 바뀐 바둑돌의 경우에는 완전히 제
조도변화와바둑돌미세위치변화를고려한 CHT 기반의자동바둑기보시스템 451 따라서, 제안시스템은키보드입력이주어질때마다바둑돌검출을시도한다. 3. 자동기보시스템성능평가 그림 3 필터링영상 Fig. 3 The filtering image 거되지않을수있다. 때문에 생성시필터링영상을사용해노이즈를제거할수있다. 그림 3은필터링영상으로써, 기존의검출된원들의누적영상이다. 생성시이필터링영상과겹치는부분또한영상에서지워준다. 에 CHT를적용하면바둑돌의중심좌표를검출할수있다. 검출된좌표가기존바둑돌인지를판별하기위해저장해놓은기보데이터와비교한다. 기보데이터는바둑돌이놓인시간순서에따라중심좌표, 흑백여부를리스트로저장한다. 비교결과새로운바둑돌로판별되면, 흑백여부를판별해야한다. 이를위해미리저장해놓은이진화결과를이용한다. 바둑돌의중심좌표에해당하는이진화영상의픽셀값을검사하여판별할수있다. 제안한방법은새로운바둑돌이놓이기전과후의에지영상 와 가필요하다. [4] 에서는대국자의손움직임을영상처리하여전과후를분별하였다. 이외에도가능한여러가지방법들이있다. 본논문에서는이러한분별이전체시스템의핵심부분과는거리가있다고생각하여, 별도의분별과정을두지않았다. 대신키보드입력신호를통해그시점을분별하도록하였다. 제안된자동기보시스템을구현하고, 성능을평가하기위한환경은그림 1과같다. 카메라를바둑판위 55cm 높이에고정했고, 픽셀로고정하였다. 이경우바둑돌의크기는 10 픽셀임을사전실험을통해계산하였다. 실험에서는바둑대신오목에대한기보를작성하였다. 바둑돌영상처리관점에서두게임간에큰차이가없으므로바둑기보작성과큰차이가없을것으로생각된다. 그림 4, 5, 6은제안시스템의동작순서에따른중간결과물영상들과최종작성된기보를보여준다. 그림 4 는웹캠으로부터입력받은영상을그래이스케일로변환한것이다. 이후바둑판격자무늬를제거하기위해가우시안필터링을적용한다. 필터링결과는흑백영상과큰차이가없으므로, 결과영상을따로삽입하지않았다. 그림 4 는필터링된영상에서차영상을생성한결과이고, 4(c) 는이진화를수행한영상이다. 차영상을획득함으로써새롭게추가된바둑돌에서만 CHT를적용할수있다. 그림 5는차영상에서 canny edge 검출을수행한영상이다. 그림 5에 CHT를수행하면서, 검출된원들의원점좌표를얻을수있다. 이원점좌표와그림 4(c) 의영상과매칭시켜, 해당원이흑돌인지백돌인지를구분한다. 그림 6은그림 4 에대해작성된기보결과를보여준다. 바둑돌이놓인순서대로번호가매겨져있고, 흑과백이배경색으로구분된것을볼수있다. 앞서 1장에서조도변화와바둑돌위치의미세변화에따른기존방식의문제점들을제기하였다. 여기서는인위적으로문제가발생하는상황을조성하고, 기존방식과제안시스템의결과를비교해보고자한다. (c) 그림 4 흑백영상, A 의차영상, (c) A 의이진화영상 Fig. 4 Gray Image, subtraction image of, (c) Binary image of
452 정보과학회논문지 : 소프트웨어및응용제 41 권제 6 호 (2014.6) 그림 5 Canny Edge 검출영상 Fig. 5 The Canny Edge detection image 그림 6 기보작성결과 Fig. 6 The resulting go record 첫번째실험에서는바둑돌을놓기전과후에조도를급격하게변화시켰다. 그림 7 와 7 는각각조도변화전과후의영상을보여준다. 새로운바둑돌의위치를쉽게볼수있도록사각형영역을표시하였다. 기존방식에따라두영상간의차이를구하고, 이진화과정을 거치면그림 8 와같은결과를얻는다. 8 는본논문의방식에따라얻은차영상이다. 표 1은실험에따른차영상의픽셀개수를수치화한것이다. 표 1에서 The general case의값은식 4에서 과같다. 기존방식의경우차영상의픽셀개수가 의배수가되는경우바둑돌을검출했다고판단한다. 하지만표 1의항목으로보면, 조도변화때문에 4720이라는픽셀수가계산됐고, 이는 의 16배수이다. 즉, 기존방법의경우 16개의바둑돌을검출하는오류가발생한다. 반면제안한시스템은차영상의크기가안정적이고, 덕분에더효율적으로 CHT를수행할수있다. 그결과그림 9와같이새로운바둑돌의위치를정확히검출하는것을볼수있다. 사각형영역은새로운바둑돌의위치를표시한다. 그림 9 는새로운바둑돌이놓이기전의영상이고, 그림 9 는조도변화가있는상황에서도새로운바둑돌의위치를정확히추출한것을보여준다. 제안시스템은원모양검출을이용하기때문에조도변화에영향을받지않는다. 두번째실험에서는바둑돌의미세위치변화에관한것이다. 그림 10 에서사각형으로표시된위치에대국자가바둑돌을놓으면서상, 좌, 우에위치한주변바둑돌을건드려위치이동이일어나도록했다. 그결과그림 10 와같은영상을얻게된다. 기존방식을사용해얻은차영상에서이진화한결과가그림 11 이다. 11 는제안하는방식으로얻은차영상이다. 11 의경우이동된주변바둑돌의영향으로반달모양의형상이나타났지만 11 에서는형상이많이사라짐을확인할수있다. 앞선실험과같은방식으로차영상의크기를표 1에나타냈다. 픽셀개수는 386이고, 이를 로나누면큰오차값을가진 1.3084라는몫을얻었다. 이번실험의경우오차값이커서식 (4) 를만족시키지못하므로, 기존방법에서는바둑돌을검출하지못한다. 이를통해 [4] 는미세위치 그림 7 조도변환전영상, 조도변환후영상 Fig. 7 Before image of illumination change, After image of illumination change
조도변화와바둑돌미세위치변화를고려한 CHT 기반의자동바둑기보시스템 453 그림 8 기존방식의차영상, 제안하는방식의차영상 Fig. 8 The subtraction image of past method, The subtraction image of proposed method 그림 9 제안한방식의검출영상. 검출전이미지, 검출이미지 Fig. 9 The detection image of proposed method. The image before detection, The detection image 그림 10 바둑돌미세위치변화실험. 변화전영상, 변화후영상 Fig. 10 The before and after image of stone dislocation by player. The image before dislocation, The image after dislocation
454 정보과학회논문지 : 소프트웨어및응용제 41 권제 6 호 (2014.6) 그림 11 기존방식의차영상, 제안하는방식의차영상 Fig. 11 The subtraction image of past method, The subtraction image of proposed method 그림 12 제안한방식의검출영상. 검출전이미지, 검출이미지 Fig. 12 The detection image of proposed method. The image before detection, The detection image 표 1 실험조건에기인한차영상의픽셀개수 Table 1 Experimental conditions caused as the number of pixels of subtraction image Experimental conditions The number of pixels of subtraction image The general condition 295 illumination change 4720 stone dislocation 386 illumination change of proposed method 553 stone dislocation of proposed method 260 변화에취약하다는것을확인할수있었다. 제안방식을사용할경우차영상픽셀개수도 260개로 CHT를빠르게수행할수있었고, 바둑돌을놓기전그림 12 와후의그림 12 와같이주변바둑돌위치변화에따른영향을받지않고, 정상적으로기보가작성 됐음을확인할수있다. 주변바둑돌의에지가원으로검출되어도, 기존위치와의차이가일정값이하면, 기존바둑돌로인식하여무시하기때문이다. 4. 결론본논문에서는영상처리를통해대국중인바둑의기보를자동으로기록하는시스템을개발하였다. 이시스템은기존방식과달리조도나바둑돌의미세위치변화에영향을받지않는다. 이는원형허프변환을통해원모양만을검출하기때문이다. 또한계산량이많은 CHT를고려하여, 에지영상의차를이용하여연산량을줄이는방법도제시하였다. 제안한방법을구현하여기보작성이가능함을보였고, 기존방식의문제점들도극복했음을확인했다. 향후연구에서는제안방법을이용하여전체적인자동기보시스템을구현하는것을목표로한다. 여기에는 GUI구축, 기보를축적및검색하는데이터베이스, 바둑연구를돕는복기시스템이있다.
조도변화와바둑돌미세위치변화를고려한 CHT 기반의자동바둑기보시스템 455 References [ 1 ] Ryu Cheni, "BADUK RECORD DEVICE," Korea. Patent, 20 0152326(1999.04.26) [2] Jeongseon Na, "Automatic Order Recording Badook Table," Korea. Patent, 20 0200127 (2000.08.07.) [3] A. Srisuphab, P. Silapachote, T. Chaivanichanan, W. Ratanapairojkul, W. Porncharoensub, "An application for the game of Go: Automatic live Go recording and searchable Go database," TENCON IEEE Region 10 Conference, pp.1-6, 2012. [4] Hoeyul Kim, Sihong Park and Seokhwan Jang, "Method and Device for Creating Paduk Record of Go," Korea. Patent, 10 0472102 (2005.02.04) [5] John Canny, "A computational approach to edge detection," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.8, no.6, pp.679-698, Nov. 1986. [6] R. O Duda and P. E Hart, "Use of Hough Transformation to Detect Line and Curves in Picture," Communications of the ACM, vol.15, no.1, pp.11-15, Jun. 1972. [7] D.H.Ballard, "Generalizing The Hough Transform To Detect Arbitrary Shapes," Pattern Recognition, vol.13, no.2, pp.111-122, 1981. 박동진 2014 년 2 월인천대학교임베디드시스템공학과학사. 2014 년 2 월 ~ 현재인천대학교임베디드시스템공학과석사과정 전경구 1996년 2월서강대학교전자계산학학사 1998년 5월 M.S. in Computer Science, Purdue Univ. 2001년 5월 Ph.D. in Computer Science, Purdue Univ. 2001 년 6월~2001년 12월 Ashley Laurent Inc. SW engineer. 2002년 1월~2004년 2월삼성전자책임연구원. 2004년 3월~인천대학교임베디드시스템공학과부교수