MagickWand and OCR

Posted on May 28, 2010 by diziet

The problem with photographs and OCR is they contain lots of noise and colour that is really not helpful.  Levels and Posterise alongside other tools in the GIMP or Photoshop help but they’re hardly automatic and can’t be compiled into code so I looked at ImageMagick.  It turns out it has a new simpler API called MagickWand.  One of the examples on the site is a Sigmoidal contrast enhancer, whatever that really does.  It helps,  I decided to take that code and call an adaptive threshold function in MagicWand that takes a number of pixels as a square to apply it’s algorithm to.  Thinking there would be a sweet spot where it occluded most of the noise but picked up on the grid and the pen strokes of the letters.  I was right.  It’s anywhere between 40 and 100 pixels as the sequence below shows, mouse over for a bit of info.

Now I just need to implement the idea I have, which as ever is cribbed.   We detect the grid and the boundaries of each cell.  Then we detect the edges of the contents of that cell and quarter it.  We should therefore have in 1/4’s our number.  By comparing the shape of each quarter to a database (nearest match?) we can determine the number.  I’ll post some images as examples below later.  You’ll note that these posts are very light on the math. 😛

Posted in Programming | Tagged , , , , , , | Comments Off on MagickWand and OCR

Candid Macro Casey

Posted on May 28, 2010 by diziet


Macro Casey, originally uploaded by Diziet.

This was taken a few weeks ago on a Sunday walk at Ashridge. This was the only shot where he’s not trying to lick either me or the camera.

Posted in Photography | Tagged , | 1 Comment

A strange bug moving from 64bit to 32bit.

Posted on May 27, 2010 by diziet

So I installed an SSH client on my iPhone today, TouchTerm (which so far I think is excellent, especially how it handles ctrl keys etc.), and the first thing I do? SSH to my server and compile the previously mentioned code. I load it and after changing the font to a fixed width one it all looks good. The puzzle loads, I hit ‘g’ to solve it and …. oh… it got part of the way through the recursive solution and stopped saying ‘Solution Found’. Except it hadn’t. I coded a refresh routine with vi on the phone to make sure it wasn’t a terminal or iphone issue, nope. It really had got part way in and decided the problem was fixed. How odd. The code was written in 64bit Intrepid running in VirtualBox on 64bit Win 7. The server was (it’s upgrading now) running 32bit Jaunty and is only a 32bit system anyhow.

Anyone? Strange strange bug. If the upgrade fixes it I will be surprised as the only external library of note is ncurses and it really isn’t an ncurses problem. My data structures are fairly boring:


struct _cell {
bool readonly;
int value;
};

struct _sudoku {
bool complete;
int iteration;
struct _cell cells[SUDOKU_VALUES][SUDOKU_VALUES];
};

And of that I only actually use the two dimensional array and the value. The readonly, complete and iteration fields are there in case I do implement weirder algorithms as they will be necessary then for distinguishing user input from generated across generations and keeping track of generations, so ancient incomplete ones can be culled as evolutionary dead ends. 🙂 Of course the second one is marked complete the program would end and display it. Anyhow I find the above problem odd, when the upgrades are complete I’ll check and if it persists drop it into gdb for a bit of an autopsy.

Posted in Programming | Tagged , , , , , | 2 Comments

It lives!

Posted on May 27, 2010 by diziet

Finally. Stripped out loads of code having realised that keeping a list of possible answers to each square is all well and good but the computational time spent maintaining it outweighs the benefits of just err.. well figuring it out each time you need to know. So

For some reason the above thumbs are truncated on the left. The clickable images are not.


diziet@ono-sendai:~/Programming/C/Sudoku$ time ./sudoku

real 0m4.071s
user 0m0.390s
sys 0m0.110s

in an ubuntu virtualbox instance on a windows7 box that’s watching a movie. 😛

Yay. What next? The backtrack algorithm I used is essentially a brute force. I may now implement my non brute force version to compare. Although I have a feeling I am painting a new room at the village hall tomorrow.

Now with added video?

Sudoku Solver

Posted in Programming | Tagged , , | Comments Off on It lives!

A short note on arrays and ncurses with a bit of a git.

Posted on May 26, 2010 by diziet

So ncurses operates on a y,x co-ordinate system.  All of it’s functions expect y first, for example:

getyx(y,x);

which gets the location of the cursor putting the values into y and x.  This sounds a bit counter intuitive to us, we are used to x then y. We think of going across the screen and then down.  So throughout my code I’ve thought of ncurses as counting down the screen then across and my code as counting across the screen and then down.  Which is right and the way I want it. Except when you declare an array as:

int fish[12][9];

You have 12 rows and 9 columns. It is also Y and then X. So a loop such as:


for(int x=0;x

Does go down and across. So although conceptually you are going across then down if you print the array out with the same logic via say printf("%d ",array[x][y]) you'll find you print down and across. I think.... 😛

So I have a sudoku puzzle where the first row at the start is effectively:

7 1

Yet my save routine saved out:


diziet@ono-sendai:~/Programming/C/Sudoku$ cat dm3.sud
0 0 0 0 7 1 0 8 3
0 0 0 0 0 0 2 5 0
0 1 0 0 0 3 4 0 0
7 0 3 5 0 0 0 0 0
0 0 0 0 0 8 9 1 0
0 0 0 9 0 0 0 0 0
0 0 0 0 6 0 1 0 8
1 6 0 0 0 4 0 0 0
0 4 0 0 2 0 3 0 0

So all of my loops have held the data going down and then across the array.   This is not a problem, it changes nothing really except it makes the save files look funny.   So I changed it all thus producing a patch from git with:

git format-patch origin/master

all because ncurses functions put y before x thus making me think it was odd. A snippet from the patch:


@@ -547,12 +547,12 @@ int display_sudoku(WINDOW *wi_sudoku, struct _sudoku *st_sudoku)

getyx(wi_sudoku,old_dy,old_dx);

- for(int x=0; x
+ for(int y=0; y
{
- for(int y=0; y
+ for(int x=0; xcells[x][y].value;
+ cell_value = st_sudoku->cells[y][x].value;

Ho hum.  At least now I can type in a potential sudoku once and keep loading it to test various ideas.  Of course we all know the backtracking algorithm will be the best but it's not the point of this entire exercise anyway.

Posted in Programming | Tagged , , , , | Comments Off on A short note on arrays and ncurses with a bit of a git.

I’m getting there.

Posted on May 26, 2010 by diziet

For a about three weeks, although only about 7 days work, I’ve been writing a small ncurses based sudoku solver.  The aim being rather obvious but the reasons more detailed.  I’ve not written anything in C with any true aim in mind for almost 7 years and not on a commercial basis for a decade (although this is not commercial).   The last program I wrote that worked as a Tsunami puzzle solver.  It populated 100 or so solutions randomly, scored them for efficiency against the criteria and bred (crossover, random mutation) the highest scorers to make another 100 until one scored 100%.   The code is now lost somewhere on a random server.  The main file was matrix.c++ which shows how long ago it was.

Anyway, back on topic, things are coming along nicely.  I have one algorithm almost working which is a very human approach.  The next to implement is a recursive backtracking algorithm and more fanciful things from there such as the sort of genetic approach mentioned above.  However to test the code I’ve been typing in the puzzles so now I am implementing a simple save and load feature. It had to be in there anyway according to the System Requirements document I wrote for it.

Posted in Programming | Tagged , , | Comments Off on I’m getting there.