<영상처리> 비트맵으로 스도쿠 읽고 풀기

2016학년도 시각개론 과제로 A4용지 한장이 나왔다.
과제 내용은 다음과 같다.

1. 스캔을 한다음 horizontal projection과 vertical projection을 한다음 숫자를 뽑아낸다.
2. pattern matching 방법을 이용하여 그 숫자를 인식한다.
3. SUDOKU의 나머지 숫자들을 채운다.

이 과제를 수행하면서 내가 배우고, 구현해야 할 것은 다음과 같았다.

1. bmp파일로부터 header들을 떼어내고 raw data를 얻기.
2. horizontal projection과 vertical projection을 해서 규칙성을 이용해 테이블에서 숫자를 따내기.
3. tempalte match 방법을 이용하여 떼어온 숫자를 인식한다.
4. SUDOKU를 알고리즘으로 풀어내기.

input은 위와 같은 스도쿠 500*500 단색 2진 비트맵으로 휴대폰으로 사진을 찍어서 그림판에서 크기조정을 해줬다.

완성된 과제의 수행 결과는 다음과 같다.

먼저 horizontal projection의 결과를 프린팅한다. (x, y) 중 x는 상단부터 센 픽셀의 index이다.
의미있는 검정색은 1, 흰색은 0으로 계산되었으며 y는 한 행을 모두 더한 projection 값이다.
자세히 보면 처음 시작때는 칠해진 픽셀이 없으므로 0이고 곧 나오는 두꺼운 선에서 488까지 올라가는것을 볼 수 있다.
vertical projection값도 프린트해서 함께 비교해보면 공통적으로 선분이 나오는 경우 projection값이 400을 넘어감을 알 수 있었다.
따라서 400이상인경우 선분으로 간주, 선 굵기를 고려해서 10픽셀을 건너 뛰어서 글자에 가까이 가는 방식을 취했다.
이 때 선을 뛰어 넘으면서 현재 커서가 어디에 위치하는지를 알 수 있다.
한줄이 통째로 비게되면 세로선분때문에 30~35사이의 값이 나오게 되는데 만약 글자가 존재하면 이 값이 40이상으로 올라간다.
이에 착안하여 projection값이 연속되게 40이 넘어가는 경우 글자로 간주했다.
이 과정을 horizontal과 vertical 모두에 적용하여 글자 영역을 따내서 다음의 처리를 진행했다.

bmp파일에서 프로젝션을 통해 추출한 숫자로 인식된 영역이 다음과 같다.
한칸 씩, 한 글자씩 인식해낸다.

직접 만든 template의 모양이다.

template와 추출한 숫자를 비교해서 매칭된 비트들의 모습이다.
사실 이 과정에서 상당히 시간을 많이 소모했다. 예를들어 6을 인식해야하는데
추출된 글자가 template의 6보다는 8에 더 많이 매칭되어 인식오류가 자꾸 생겼다.
처음에는 template을 자꾸 수정해주면서 해결하려고 했지만 별로 의미가 없다는 것을 깨닫고 예외상황을 따로 처리해주기로 했다.
최종적으로는 숫자6의 horizontal projection값이 8에 비해 일정치 않다는 것에 착안하여
인식된 숫자가 8일경우 horizontal projection값을 한번더 검사해서 확실시 해줬다.
비슷한 다른 여러 인식 오류도 앞의 경우처럼 projection값으로 해결 가능했다.

위의 과정을 계속하여 인식한 스도쿠를 출력하고 이후에 간단한 스도쿠 풀이 알고리즘으로 풀어낸 결과를 출력한다.

느낀점

txt파일이 아닌 다른 header가 있는 파일을 다뤄보는게 처음이라 bmp를 읽어들이는데도 한참이 걸렸다.
template를 만드는데도 오랜시간 노력이 필요했다. 하지만 처음부터 끝까지 프로젝트라고 생각하고 열심히 했기에 기억에 남을 것 같다.
많이 부족하고 조잡한 코딩을 선보였지만 끝내 해냈다는 것이 뿌듯하다. 더 열심히 공부해야겠다.

참조한 블로그
- 스도쿠 풀이 알고리즘 http://sunnyholic.com/81
- bmp파일 읽기 http://www.soulfree.net/182

*소스코드 : https://onedrive.live.com/redir?resid=4FEDA092E8180CD3!8901&authkey=!ANla9qY3CI4W9CA&ithint=file%2czip