sudoku grabber 3 Extracting the grid

이전포스트 보기

Extracting the grid

이전 포스트에서는, 몇 몇 선을 찾긴했다. 근데 그 많은 선들은 퍼즐이 어디에 위치하고 있는지 찾기엔 적절하지 않았다. 그래서 이번 포스트에서는 좀 수학적인 이야기를 곁들어서 퍼즐이 정확히 어디에 위치하는지 찾아내볼것이다. 그리고 퍼즐의 왜곡을 없애서 퍼즐을 마치 바로 위에서 수직으로 보는 듯한 이미지로 만들것이다.

Merging lines

이미지의 물리적인 선은 원래 선과 관련된 "수학적인" 선을 가지는데, 이건 근처의 가능한 선들을 합침으로 인해 이 것을 보완할 수 있다.  아래는 이전 포스트에서 Hough transform을 통해서 얻은 결과물이다.

선을 합친다는건, 근처의 선들을 평균낸다는 것을 뜻한다. 그래서 특정 반경에 있는 선들은 결국엔 같이 합쳐질것이다. 우리는 선을 합칠 수 있는 함수를 만들어 볼것이다.  

이 함수는 다음과 같이 호출될것이다.

이전 포스트에서 HoughLines을 사용했고 결과는 위의 사진과 같았고, 따라서 mergeLine이 필요했다. 

mergeLine 함수는 brute force방식으로 접근하는데, 한 선을 중심으로 다른 모든 선을 비교해서 합칠만 하면 합친다는거다. 이건, 이중 for문으로 구현한다.

 함수는 다음과 같이 시작된다.

iterator를 통해 array lsit를 순회하는데 이걸 두번 겹쳐사용해서- nested loop(이중 for문)을 구현한다.

vector의 각 엘리먼트는 두 정보를 포함하고있는데 rho와 theat이다. 왜, rho와 theta를 저장할까?  그 질문은 여기서 대답할 수 있다.(클릭)

짧게말하면, 선은 rho와 theta로 정규화로 표현할 수 있고, openCV에서 제공하는 함수들은 종종 rho와 theta를 반환한다.

이렇게 합치는 과정을 통해, 몇 몇 선들이 합치게 될것이다. 이 과정에서 우린 이미 합쳐진 선들을 마킹해놓을 필요가 있는데 rho와 theta는 각각 0과 -100으로 설정될것이다. 왜 그럴까?

 rho는 직선까지의 거리(즉, 수직 선의 길이), theta는 이 수직 선과 x축의 각을 뜻한다.

rho =  x*cos(theta) + y*sin(theta) 이다. 절대 0이면서 -100일수가 없다. 따라서 rho와 theta를 각각 0과 -100으로 설정할것이다.

우선, 설정하는 것은 함수 마지막단에서 나올것이고, 이미 0과 -100이면 함수내용을 수행하지 않는다는 코드를 삽입할 것이다.

현재 vec2f의 0에는 rho와, 1에는 theta가 있는데, 우선 저장하여 사용할겁니다.

이 두 정보를 이용해서, 선 위의 두 점을 찾을 수 있다. 계산이 익숙치 않다. 어쨌든 찾는다..(ㅠ..ㅠ..)

theta 가 45*3.14 초과, 135*3.14 미만일때와, 그 반대일 때를 따로 처리해준다. 이게 또 어떻게 구하는지는...  나는 구면좌표계에 매우약한데, 친절한 지나가시는 행인분께서 이게 정확히 어떤 건지 댓글로 설명해주면좋겠음.. OTL...

어쨋든 이렇게 주 점을 찾은 뒤, 그 외의 점을 순회해본다. nested loop가 사용된다.

위와 같이 for문을 한개 더 넣는다.

그리고 주 선(current) 과 현재 순회하는 선(pos)과 같으면 넘긴다. (동일한 선을 합친다는 건 아무런 의미가 없다.)

그리고 주 선 rho와 부 선 rho의 차이(float absolute)가 20이하이고, 주 선 theta와 부 선 theta의 차이가 10/180이하이면 두 선은 합칠 수 있는 가능성이 있다. 

그리고 그 경우에만, rho와 theta를 저장한 뒤 pos 선 위의 두 점을 찾는다. 

그리고 충분히 가깝다면, 그 두선을 합친다. 그리고 pos 선의 상태를 불가능한 선의 위치 상태로 설정한다.

그리고 다음과 같이 메인 소스에서 사용되는데 결과는 다음 아래와 같다.

제일 좋은 선 찾기

이제부터는 위 가장자리와 아래 가장자리, 왼쪽 가장자리 오른쪽 가장자리와 가장 가까운 선들을 찾을건데, 이 선들이 이제 스도쿠 퍼즐의 경계선이 될 것이다. 우리는 이제 mergeLines 호출뒤에 다음과 같이 작성한다.

우리가 원하는 네 선의 변수를 생성하는데, 초기값은 위와 같이 과장되게 설정해주었다. 그다음 우리가 이전에 구했던 lines 벡터들을 순회한다. mergeLines 함수에서 이미 merge되었던 선들은 rho와 theta가 각각 0, -100으로 설정되었음을 기억하라. 이걸 사용해서 합쳐졌던 선들은 skip할것이다. 

이 수행이 끝난뒤에는, 우리는 가장 좋은 선들을 얻게될것이고, 이 선들을 시각화하려면 다음과 같은 수행을 하면된다.

이런 결과를 얻을 수 있다. 길고 긴, 길고 긴 수학 연산뒤에 드디어 4개의 선을 구했다. 

이제 네 선의 교차점을 연산해야한다. 선이 주어졌을 때 교차점을 연산하는  법 링크

먼저 각 선의 두 점을 찾은뒤, 수학적인 작업을 수행 한뒤에, 두 점이 어디서 교차하는지 구할 수 있다. 코드는 아래와 같다.

위 코드는 선에서 두 점을 찾는데, 우측선과 좌측선은 if 구문이 필요하다. 왜냐하면 두 선은 정확히 수직일 수 있고, 이건 기울기가 무한대일 수도 있다는 것을 뜻한다. 컴퓨터는 무한대를 표현할 수 없기 때문에, 조금 안전한 방법으로 작업을 수행이 필요하기에 if 처리가 필요한것이다.

이제 밑에서부터 진짜 교차점을 찾는다.

이제 교차점을 구했으니, 왜곡된 원근점을 수정할 수 있다. 이 작업은 스도쿠를 마치 위에서 쳐다보는 것과 같이 사진을 수정하는 작업이 주 목적이였다. (본 포스터의 젤 위에 적어놨었다.)

자. 먼저는 퍼즐의 가장 긴 변을 찾을것이다. 왜냐하면 새 이미지는 가장 긴 변의 제곱만큼의 넓이가 될 것이다. 

우선 가장 긴변을 찾은 뒤 maxLength에 저장한다. 그리고 제곱근을 수행하면 실제 길이를 구할 수 있다.

그 다음 source와 destination point를 생성한다. 

원 이미지의 스도쿠 퍼즐 왼쪽 상단 점은 새이미지의 (0, 0) 과 같아야하고..원 이미지의 스도쿠 퍼즐 우측 하단 점은 maxLength-1, maxLength-1 과 같아야한다.

그리고 우린 새 이미지를 만들고 undistortion을 수행하고, 수행된 이미지는 다음과 같다.

음.. 왜이렇게 뿌옇게 나올까... 그게 궁금하다. 블로그엔 아래처럼 깔끔하게 나오던데,. 알아봐야겠다.

뿌옇든 선명하든, 어쨋든 숫자 인식하는데 큰 차이는 없을것같다.(과연?, 문제가 될거같기도 하니까 이 문제도 해결하는 쪽으로 방안을 구해놔야할것같다.)

이것까지했으면, 이 새이미지에서 가로 길이를 9로 나누면 각 column이 될것이고 세로 길이를 9로 나누면 각 row가 될것이다. 그다음 숫자를 인식하면 어디 (i, j)에 어떤 숫자(1~9)가 들어가있는지 알게되겟지.

이 모든 작업이 우리가 수행하고 싶었던 일이였다. 

review를 해보자면, 이제까지 우리가 했던것은 

1 임의의 이미지에서 가장 큰 상자를 뽑아내기

2 가장 큰 상자의 네 선을 찾기

3 네 선의 교차점을 찾기

4 교차점을 각각 새이미지의 왼쪽상단 우측상단 좌측하단 우측하단에 맞추기.

였다.

이제 OpenCv에서 Digit Recognition을 주로 KNN 알고리즘을 수행해서 하는데, 

그러니까 숫자를 인식하는 머신러닝? 코드를작성할 것이다. 

하 쉽지않다 쉽지않다. python으로 작성했으면 라이브러리 뚝딱 먹방하는데, C++로도 짜보고싶기도하다. 그리고 solution도 C++이긴한데, 

문제는 내 작업환경이 raspberry pi인점과 솔루션이 windows 환경인 점이 다르므로, 또 다르게 적용되는게 있을까.. 도 신경써야하고, 어느정도 kNN 개념을 잡아야하기 때문에 이것만큼의 긴 포스트가 또 필요할 것같다.

나도 취업을 위해서라면, 이런 자기계발도 필요하긴하겠지. 나도 취업을 하고싶응게,,, 좋은데루. 

열심히해보자.

다음포스트보기

K-Nearest Neighbors for Machine Learning