First of all, I’ve to admit that I never solve a single Sudoku puzzle by hand, or pen and pencil. Secondly, I did not write the Sudoku solver in Scilab, it is done by Michael Baudin and the module is available in Scilab atoms portal. (see : https://atoms.scilab.org/toolboxes/sudoku/0.1.1).
This tutorial is the extension from previous post : Perspective Transformation – A Manual Way and we are going to used the transformed image in this tutorial.
The image above is the result of the previous post. If you do not want to run the previous tutorial and want to jump direct into this, just right click and save the above image as “sudoku2.jpg”. We will move on from there.
Step 1: Image Pre-Processing
Our first task is to pre-process the image so that we could obtain a nice binary image for following operations. What we are going to do in this step could be summarized as:
a. Convert the image to grayscale image and then invert the image. In image processing, we always have the objects with lighter color than background.
b. Using Morphological operation – Erosion, we “wipe out” the objects (the digits and the lines) to produce a background image.
c. Subtract the background from the image to obtain an image with uniform background.
d. Convert the image to binary.
e. Labeled the detected objects.
Scilab codes are shown below:
////////////////////////////// // Step 1: Image Preprocessing ////////////////////////////// // Import and process image S=imread('sudoku2.jpg'); S_gray = rgb2gray(S); S_inv = 255-S_gray; // Background subtraction to get better binary se = imcreatese('ell',9,9) ; S_c = imerode(S_inv,se); SS = imsubtract(S_inv,S_c); Sb = im2bw(SS,imgraythresh(SS)); // Label the detected objects [S_label n] = imlabel(Sb); // Visualize all stages of Preprocessing subplot(231);imshow(S); title('Original Image'); subplot(232);imshow(S_gray);title('Grayscale Image'); subplot(233);imshow(S_inv);title('Inverse Image'); subplot(234);imshow(SS);title('After Backgroud Subtraction'); subplot(235);imshow(Sb);title('Binary Image'); subplot(236);imshow(S_label,hsvcolormap(n));title('Labeled Image');
Step 2: Features Extraction
The feature that we are going to extract is a very simple feature set, some call it as spatial feature. Basically it just resize each object to a 70 by 50 matrix, each pixel could be only either ‘1’ or ‘0’ (true or false) as it is binary image.
The ‘1’s or ‘0’s are then grouped into 10×10 matrices, which form a 7 x 5 matrix, with each pixel value be the total number of ‘1’s divide by 100 in that group. Figure below visualize this concept.
At the end, we will have a matrix of 7×5 with each pixel in the range of 0 to 1.
What are we going to perform in the following codes are:
a. Find the properties of the detected objects in the image.
b. Extract those objects which are likely the numbers, by referring to the size.
c. For each detected numbers, perform the feature extraction process as describe above.
////////////////////////////// // Step 2: Features Extraction ////////////////////////////// // Find objects properties [A, BB, ctr] = imblobprop(S_label) A_num_ave = median(A); // Extract the components which are likely the numbers base on their size. ind = find(A>A_num_ave*0.5&A<A_num_ave*1.5); obj_BB = BB(:,ind); obj_ctr = ctr(:,ind); A_ctr = A(:,ind); // Show the detected numbers imshow(S); imrects(BB(:,ind),[255 0 0]); // Initialization of variables of lists mynum = list(); mynum7050 = list(); mynum75 = list(); // Computer the spatial features, first resize each subimage to 70x50, and then find the average for each 10x10 matrix to produce 7x5 deff('y=mymean(x)','y = mean(x)'); drawlater(); for cnt = 1:size(ind,2) mynum(cnt) = imcrop(Sb,obj_BB(:,cnt)); mynum7050(cnt) = imresize(mynum(cnt),[70,50]); mynum75(cnt) = imblockproc(mynum7050(cnt).*1,[10 10],'mymean'); // uncomment following line if you have installed Scilab Neural Network module //subplot(4,6,cnt);plotchar(mynum75(cnt)); end drawnow();
Following figure will be available if you’ve installed Scilab Neural Network module and un-commented the line in the loop. The numbers are not arranged according to the proper location yet.
Step 3 : Digits Recognition with Linear Regression
We are going to recognize the digits that we detected previously by using a very simple technique -> Linear Regression. Following are the template we are using, and the same feature extractions used to extract the features from the template. The idea is simple, find the linear regression of each detected digits with all digits in the template, and the one with the least error would be the highest possible digit!
In order to simplified the step, the template could be downloaded from this link in Scilab data format, there are extracted from the image below.
The recognition steps involve:
a. Load the template “sudoku_template” , and the data is saved in variable “P”, with 35×9 matrix. Each column consists of the feature of each digits.
b. Perform linear regression for each detected objects with the template, and find the least error index.
c. Plot the recognized digits on the original image.
////////////////////////////// // Step 3: Recognition with Linear Regression ////////////////////////////// // Load the template load('sudoku_template'); //https://drive.google.com/file/d/0By-S7f6vJow8NnctaHB4OWcxSEk/view?usp=sharing // uncomment following lines if you have installed Scilab Neural Network module //drawlater(); //for cnt = 1:9 // subplot(3,3,cnt) // plotchar(matrix(P(:,cnt),[7,5])); //end //drawnow(); // Perform linear regression to recognize each detected digits imshow(S); offset = sz(1)/9/2; sz = size(S); set(gca(), "font_size", 5.5,"font_foreground",5) for cnt = 1:size(mynum) y = reglin(P',mynum75(cnt)(:)'); [maxV,maxI] = max(y); r(cnt) = maxI; xnumb(obj_ctr(1,cnt)-offset/2,sz(1)-obj_ctr(2,cnt)-offset,r(cnt)); end
Step 4 : Solving the Sudoku Puzzle!
By the time of this post drafted, the Sudoku module is not available for Scilab 6 directly with atomsInstall yet. You would need to download the source and recompile it for Scilab 6 (with some source edit). If you can’t wait, kindly leave your message below and I could sent it to you.
What are we going to do in this final step are:
a. Locate the center of each cell in the Sudoku Puzzle
b. Match the cells filled with the digits with the grid, in order to construct the sudoku problem matrix.
c. Use the sudoku module to solve the problem
d. Plot the result on the image.
////////////////////////////// // Step 4: Solving the Sudoku! ////////////////////////////// // Finding the center of each cell, forming a grid of all locations. loc1 = sz(1)/9/2:sz(1)/9:sz(1); loc2 = loc1($:-1:1); [xx,yy] = meshgrid(loc1,loc2), // Find the shortest distance between the detected digits with the grid above, and map the detected digits to the proper locations. for cnt = 1:size(obj_ctr,2) rms = sqrt(mean((repmat(obj_ctr(:,cnt)',81,1) - [xx(:),sz(1)-yy(:)]).^2,'c')) [minV,minI] = min(rms); sudoku_matrix(minI) = r(cnt); end sudoku_matrix = matrix(sudoku_matrix,[9,9]); // Solve the Sudoku puzle and plot the result. answer = sudoku_solve(sudoku_matrix); set(gca(), "font_size", 5.5,"font_foreground",2); xnumb(xx(:)-offset/2,yy(:)-offset,answer(1)(:));
Similar example using scicv would be posted on scilab.io soon.
Main reference sources: