Step 1 : Capture the Sudoku by taking a photo

Process to find grid and numbers

In step 1, there are 2 main difficulties :

• create the bitmap with the right size
• manage the camera

To set the bitmap with the right size, you need to consider the virtual memory size of Android phone; typically, this size is 16 megabytes; some Android phones with a camera having 8 Megapixels can have 24 megabytes of virtual memory. Suppose we take a photo with the dimension 2048X1536 (width X height) which is often the default dimension set by the Android phone when you do not specify yourself the size needed. The memory taken is 2048 X 1536 X 4 = 12 megabytes. Rapidly, your program is out of memory.

So, what is the right size for the  bitmap? If this size it too high, there is not enough memory and it takes too much time to  extract the grid and numhers. If this size is too low, the program does not take a lot of memory, takes less time but the size is often not enough large to capture all the numbers. After many tests, we chose 512 for the width and height of the bitmap.

Now, the camera. We can set the camera with the class Parameters like this :

camera = Camera.open();

Camera.Parameters parameters = camera.getParameters();

//  . . . set rotation, orientation, preview size, picture size, . . .

camera.setParameters(parameters);

Some of the parameters can be set in different manners when the program runs on different Android versions. Our goal is that our program must run on Android version 1.5 or over. So, we do not want to use method specific to a version. Besides, some parameters are not taken in charge by some Android phones. So, we decided not to set any camera parameters.

The program could receive a photo with the dimension 2048X1536 which is too high. So, before converting a photo to a bitmap, we have to query the dimension of the photo in order to decrease the bitmap size. Here is the code to query the dimension and to create the bitmap taking into account the width and height of 512 for the resulting bitmap :

BitmapFactory.Options options = new BitmapFactory.Options();

options.inJustDecodeBounds = true;

bitmap = BitmapFactory.decodeByteArray(data, 0, data.length, options);

options.inJustDecodeBounds = false;

options.inSampleSize = options.outHeight / 512;

bitmap = BitmapFactory.decodeByteArray(data, 0, data.length, options);

The bitmap dimension is now 1024X768 which takes a lot less memory that is around 3 megabytes.

Here are 2 points concerning "outHeight / 512" :

• we use options.outHeight instead of options.outWidth because the photo is still in landscape mode; the photo on Android phone is always taken in landscape mode; we have to rotate it (more later on how to rotate the photo)
• the result of  options.outHeight / 512 is 3 and the height obtained is 768; it shoud have been 512;but Android always chooses a number immediately below a power of 2 which is 2 in our casespan>

Next, we must shrink the bitmap from 1024X768 to 512X512. We will crop the bitmap from 1024X768 to 768X768 and resize it from 768X768 to 512X512. Here is he code to do that :

int destWidth = 512;

int destHeight = 512;

int origWidth = bitmap.getHeight(); // to crop the bitmap

int origHeight = bitmap.getHeight();

Bitmap bmwork = Bitmap.createBitmap(destWidth, destHeight, Bitmap.Config.RGB_565);

Rect destRect = new Rect(0, 0, destWidth, destHeight);

Rect origRect = new Rect(0, 0, origWidth, origHeight);

Canvas canvas = new Canvas(bmwork);

canvas.drawBitmap(bitmap, origRect, destRect, null); // to resize the bitmap

The last transformation is to rotate the bitmap like this :

Matrix matrix = new Matrix();

matrix.setRotate(90);

bitmap = Bitmap.createBitmap(bmwork, 0, 0, 512, 512, matrix, true);

The bitmap is now ready. We start a thread to find the grid and the numbers.

Display

Meanwhile, we display the resulting bitmap giving time to the user to check if the photo is satisfactory.

Here are the screen shots of some photos :