sudoku grabber 2 Grid detection

Original Post

http://aishack.in/tutorials/sudoku-grabber-opencv-detection/

# 해당 포스트는 위 링크에서의 내용을 번역한것과 저의 작업환경 (라즈베리파이 Jessie && Opencv 3.3.1)에 의해 적절히 조합된것입니다. 좀 더 포괄적인 내용은 위 링크에서 확인할 수 있습니다. 이미지 전처리 내용은 대체적으로 개발환경에 관계없으므로, 큰 지장은 없습니다.

2 Grid detection

이 포스트에서, 우린 Sudoku Puzzle을 감지할것이다. 여기서 이미지에 대한 모든 전처리가 이루어진다:

이미지에서 nosie가 너무많이 감지되지 않게 필터링을 수행하고, 이미지 segmenting 또한 여기서 다뤄진다. 난 여기서 꽤 이상한 segmentation 방법을 사용했는데, 여러분이 꽤 관심을 가질 수도 있다. 이 포스트를 통해, 퍼즐의 상자를 이루는 선들을 얻게 될것이다.

시작하기

가장 먼저 수행해야하는 것은, IDE에서 새로운 프로젝트를 생성하는 것입니다. 저의 개발환경은 라즈베리파이 Jessie입니다.

그리고 OpenCV가 제공하는 C++ interface를 사용할 것입니다. 우선 여러분의 컴퓨터에는 최소한 OpenCV 3.0 이상이 설치되어있어야합니다.

OpenCV 사용법에 익숙치 않다면 다음의 링크를 참조하세요. 

- OpenCV with gcc and CMake

- OpenCV's C++ interface

우선 OpenCV library 파일을 프로젝트에 Link하고, 여러분의 main file에 다음을 추가하세요. 그 뒤, 퍼즐을 인식시키기 위해 정적인 이미지를 이용할 것입니다. 그 다음 소스에서는, 이미지를 로드합니다.

<스도쿠 퍼즐 이미지>

제대로 로드되었는지 다음과 같은 코드로 확인할 수 있습니다.

우리는 이미지를 grayscale mode로 로드했습니다. (imread 함수의 2번째 인자가 0임을 확인)

왜냐하면 색에 대한 정보는 필요가 없기 때문이죠. 그리고 다음에는, 같은 크기의 빈이미지를 생성했습니다. 이 이미지는 퍼즐의 바깥상자를 저장할것입니다.

이미지 전처리하기

이미지를 약간 Blur 처리할겁니다. 이건 노이즈를 조금 감소시키고, 상자 선을 뽑아내는데 더 쉽게 만들어줍니다.

이렇게 노이즈를 줄여주면, 이제 이미지를 threshold 할 수 있습니다. threshold란 이미지의 특정 영역을 인지해서 이미지로부터 분할(segmenting)하는 것입니다. 링크참조

이미지는 다양한 illumination level을 가질 수 있는데, adaptive threshold 알고리즘이 좋은 선택이 될 수 있습니다. - 더 자세한 내용은 원본 포스트 참조바람 -

다음의 소스코드를 통해 적용할 수 있습니다.

그 뒤, 우리가 경계에 대해 관심이 있고, 그게 검은색이므로 outerBox를 역변환 해주어야합니다. 그러면, 퍼즐의 경계가 하얗게 변합니다.

그리고 이 thresholding 작업은 연결된 부분(Connected Component)들을 분할 시킬수 있습니다. 그러므로 이를 보완하기위해서 dilate함수가 사용됩니다. 링크참조

 

가장 큰 blob 찾기 

#blob은 object라고 이해하면 될 듯

이 프로젝트에서, blob들을 찾기위해 라이브러리를 써도되지만, 저는 blob을 인지하는 작은 소스를 만들어보았습니다. 만약 라이브러리를 쓰고싶으면, cvBlobsLib를 써도됩니다.

저는, 먼저 floodfill 함수를 사용합니다. 이 함수는 픽셀에서 사각형을 리턴합니다. 

우선 우리가 이미지에서 가장 큰 부분을 차지하는게 퍼즐이라고 가정했으므로, 가장 큰 blob 또한 퍼즐이 되어야합니다.  퍼즐이 이미지에서 제일 크므로, 퍼즐의 테두리 상자 경계가 이미지 내의 상자중에선 가장 커야합니다. 그러므로, 우린 floodfill을 통해 그 테두리 상자의 위치를 찾고 저장할 수 있습니다.

Flood filling each blob (진행 중에)

함수에 대한 설명은 원문 포스트를 통해 참조해주세요. 어쨌든 이걸 수행하고 나면 다음과 같은 결과를 얻을 수 있다.

그리고 maxPt엔 가장 큰 blob의 위치가 담긴다. 이 지점부터 흰색으로 floodfill을 수행하면 가장 큰 지점을 흰색으로 하이라이트 할 수 있을 것이다. 다음의 코드를 통해 수행이 가능하다.

 

가장 큰 blob이 희므로, 다른것들은 까맣게 만들어줄 필요가 있다. 다음과 같은 명령어로 수행할 수 있다.

그 뒤, 이미지를 dilate 했으므로 다시 erode 함수를 통해 복구한다.

최종 결과는 다음과 같다.

선 찾기

이제부터, 우린 하나의 blob을 얻게되었는데. 이제는 선을 찾을 시간이 되었다. 이건 Hough transform을 통해 수행될 수 있다.

# Hough transform 링크 참조

OpenCV에서 제공이되므로, 다음과 같은 코드만 사용하면 된다.

자 이제, 우린 각각의 선을 그려볼건데. 아래의 결과가 괜찮은지 안괜찮은지 살펴보자. 참고로 소스는 다음과 같다. 우선 drawLine 함수를 정의한다.

이 함수는 정규화된 선을 취하며(x축의 각과 원래 선의 거리에 따라). 그리고 선이 만약 수직이면(기울기가 무한대이다), 그러면 선이 제대로 그려진거다. 그게 아니라면, 두 점을 찾아 선을 그린다. 결과의 그림은 다음과 같다.

 

보는 것과 같이 각 선들은 가능한 근사치들을 조금 많이 가지고 있다. 이런 상황은 원래 선이 두꺼울때 나타는 결과이다. (두꺼우니까 가능한 직선들이 여러개가 나타나는것이다.) 

그래서 이 선을 이용해 퍼즐이 어디에 위치하고 있나 찾는건 적절하지 않다. 그래서 다음 포스트에서는 이 문제를 해결할까 하는데, 좀 수학적인 이야기가 필요하다.  

요약

이번 포스트에서는, sudoku grabber의 절반을 구현해보았다. 물리적인 경계선을 감지했긴 했는데, 결과물을 바로 쓸 수 있는 상태는 아니다. 다음 포스트에서는 좀 수학적인 이야기를 해서 보완을 할 필요가 있다.

다음포스트 보기 Extracting the grid