sudoku grabber in Opencv

Original Post

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

나의 작은 프로젝트를 위한 번역본

OpenCV를 활용한 sudoku solver. (quick and fun proejct)

시작에 앞서

카메라를 이용해 soduku puzzle을 인지하고 문제를 푸는 프로그램을 만들어볼까한다.

이 주제는 꽤 많은 것들을 다룰것이다: geometric transformations, character recognition. logic, 등등.

이 포스트는 Sudoku Grabber가 어떻게 동작하는가에 대해 전반적으로 살펴볼것이다.

Recognizing Sudoku Puzzle 

스도쿠 퍼즐을 인식하기위해서, 이미지 전처리를 제공하는 간단한 툴들을 사용할것이다.

Character recognition, detecting lines, fixing skewed picters, 등등이다.

우리가 전체적으로 구현할것들에 대해 여기서 약간 풀어보겠다.

 

일단, 다음과 같은 어떤 이미지가 있다고 하자.

우리가 제일먼저 해야할 것은 퍼즐을 인지하는것이다. 그런데, 이건 절대 쉬운일이 아니다. 다음을 고려해보자.

- 스도쿠 안의 작은 상자의 선은 가늘며, 그래서 인지하기 힘들 수 있다.
- 선이 완전하지 않을 수 있다.
- 스도쿠의 큰 상자는 다른 요소들과 유사한 색을 가지고 있어 구별이 필요하다.

이 모든 것들을 해소하려면, 다음과 같은 가정이 필요하다. 

1 "퍼즐은 이미지에서 가장 큰 원소이다."

이건, 꽤 안전한 가정인데, 왜냐하면 여러분이 해당 프로그램을 사용할 때 스도쿠퍼즐을 사진에서 작게나오게 찍을리가 없기 때문이다.

또 다른 가정이 하나 더 필요한데, 

2 "퍼즐의 큰 상자 테두리가 항상 두꺼운 검은색이여야만한다."

 위의 사진에서, 3*3 상자또한 굵은 선을 가지고 있다. 이건 꼭 필수사항은 아닌데, 그냥 젤 바깥선은 반드시 굵은 선을 가지고 있어야만 한다.

step 1. Segmenting the Sudoku Puzzle

젤 먼저 해야할 것은 thresholding을 이용하여 퍼즐이미지를 분할하는것이다. 

# thresholding에 관한 내용은 여기서 참조가능하다. 클릭

이 작업뒤에는 우린 다음과 같은 검은 퍼즐 사진을 얻을  수있다.

물론, 이 작업엔 또 다른 전처리 작업이 포함되긴한다. noise를 줄인다던가, 어떤 morphological operation이라던가, 등등.

#morphological operation 참조

이 부분에 대해선 구현할 때, 좀 더 디테일하게 살펴볼 예정이다.

step 2. Detecting the puzzle blob 

아직 우린 이미지에서 선을 감지하진못한다. 이 위 이미지에는 이상치들이 많은데, 퍼즐 바깥에는 위와 오른쪽에 글자들과 숫자들이 있다. 그리고 또 다른 선들이 있다.

그러므로 우리는, 여기서, "퍼즐은 이미지에서 가장 큰 원소다."라는 가정이 사용한다. 우리는 이미지내의 모든 object들의 크기를 검사한다. 그리고, 퍼즐의 상자만이 사진에서 젤 큰 면적을 차지한다.

가장 큰 영역을 차지하는 object를 선택하게되면, 우린 다음과 같은 결과물을 얻을 수 있다.

자, 다음에는 이 noise 없는 이미지에서 선들을 인식시켜 볼것이다.

우선, 여기까지 구현을 다음 포스트에서 볼수있다.

post 2. Grid detection 바로가기

step 3. Locating the puzzle

우린 이미지에서 선을 찾기위해 Hough transform을 쓸 수 있다. # Hough transform 참조

수식으로 선을 반환하는데, 이 단계를 거치고나면, 정확히 어디에 선이 위치하고 있는지 알 수 있게된다.

이 선들이 다필요한건아니고, 각 꼭지점들의 선만을 가져갈거다. 그리고 그건 수식으로 표현한 선이기 때문에, 교차점 또한 구할 수 있다. 그리고 이건 퍼즐의 네 꼭지점이 될것이고. 우린 정확히 퍼즐이 어디에 위치하고 있는지 알게된다.

우리의 예제파일로는, 다음과 같은 결과를 얻게된다.

네 꼭지점이 꼭 정확하지는 않다. 하지만 거의 근사하고, 이 정도로 충분하다.

step 4. fixing the image and accessing each cell

우린 네 코너를 얻게 되었으니까, 이 코너를 이미지에 새로 맞추어보면 - 다음과 같은 새 이미지를 얻을 수 있다.

 

이 작업 후에는, 퍼즐을 9*9 상자로 나눌 수 있는데. 이렇게 나누고 나면은 각 칸은 거의 근사하게 원 퍼즐의 상자와 일치할 것이다. 이 칸이 반드시 일치하지는 않지만, 원래 스도쿠가 제대로 그려진 것 이라면 충분히 납득할만한 분할이 될것이다. 

post 3. Extracting the grid