Logan Buesching

Hanzi Recognizer is a project that has been born out of CS490t at Purdue University by myself and Nathan Hobbs. The information below is current as of 11/24/2007.

Features

When you draw a Chinese character in the drawing panel, and look it up, it gives 5 of the closest matches. For each character, it also informs the user of the definition, pronunciation, main radical and main radical definition.

High Level Implementation Details

The stroke recognition and scoring algorithm isn’t the greatest, but it is based upon JavaDict, a 10 year old Java 1.2 program. A stroke is defined as pen down until pen up. What it does, is it turns a single stroke into a number. The number represents the direction the stroke was made. When you make a multiple direction stroke (Like drawing a capital L), it is registered as two directional strokes.

Directional strokes:
         7   8   9
          \  |  /
        4 ---5--- 6
          /  |  \
         1   2   3

So an L would be considered a 26 stroke. Currently then, it scores the given stroke against every stroke in the database, with the lowest score being the best match.

We then have a Unistrok file that contains how to draw every character. This file looks similar to:

6c34 | 61 2 1 3

Where it is [unicode | strokes].

To Do

Currently, we need a better scoring algorithm. If there are too many or too few strokes drawn, then we just arbitrarily give it a bad score. This can be improved through implementing an edit distance algorithm.

Allowing for characters to be searched by pronunciation or radical.

It takes a long time to load. This is a side effect of the fact that our characters are stored unsorted, therefore it takes O(n) time to search for a character. In itself that’s not slow, but doing that 50,000 times is slow. We need to sort the characters as we store them and search with a binary search (or hash and search in O(1)).

Nate just implemented some basic speech functionality. We need to get some speakers to speak the pronunciations and implement this.

Currently we are creating our own XML file format to store the characters so we don’t have to get information from 3 different databases. This file can be rebuilt as the others are updated, and itself would cut down on the load times by almost a full order of magnitude.

We need to add more support for more variants of radicals and simplified / traditional characters. Currently, there are many places where we (seemingly) arbitrarily choose to display either a traditional or simplified variant.

References

Unihan Database

CEDict

Today I finished up some of the coding for the my Rubix Cube project using Direct X and LINQ. Luke Hoersten and Nate Hobbs were my partners in developing the program. All of us worked on coming up with designing a sufficient data structure. I worked on implementing the data structure and the user interface / Direct X stuff. Luke focused on refactoring the code, and coming up with parts of the solving algorithm. Nate worked on parts of the solving algorithm.

Previous Posts

I have outlined some problems we had while developing the application and also some design decisions that were made to include LINQ. The way our program solves it is that it goes about it the way that a human would.

Solving the cube

The program starts with trying to solve the bottom layer, then solve the middle layer, then finally the top layer. Luke would be able to give a much better explanation of how it worked. It was suggested by our professor that we create a tree by attempting every move, then for every move try every move, etc… This we thought would not be a great way to solve it for two reasons. The first being that there are 18 possible moves to make on a cube, and if you want to try and go n levels deep, it would have to compute 18ⁿ states. Not only that, but it would have to store every state, score them, then take the path with the best score. To go 6 levels deep, you need to compute 34 million different states, for 7 levels deep, you need to compute 612 million states. Computers are good, but they aren’t that good.

This would not be completely terrible, if you had a smart heuristic for scoring. If every time you computed every one of those states, you were guaranteed to get closer to the solution, then you would only be spending time solving it, and time a computer has. The heuristic that was presented was to find proximity of where a block is to where it should be. This is not the greatest either because what happens when you are almost finished solving it, and you have only one or two cubes out of place (or oriented wrong). You have to end up messing up your cube really bad in order to solve it, and if you’re algorithm doesn’t go deep enough, you won’t find your solution because your current state will always be better than where you are going.

The Program

Basically, here is the outline of the program:

Block.cs – A tiny block within the rubix cube. The rubix cube contains 27 of these blocks.
Cube.cs – The cube structure, contains helper functions to orient and move sides of the cube.
Solver.cs – The class that solves the rubix cube.
UI.cs – Handles the DirectX and drawing of the rubix cube.

We haven’t formally licensed the program, but I’m sure Luke and Nate wouldn’t mind if we say it’s GPL’d. Basically give us credit for whatever you do with it and don’t sell it.

URL: Rubix Cube in C# using LINQ
Alternatively, you can also check out the Mercurial sources at: Luke’s Mercurial Sources

In CS 490T I am working on a team with two others creating a Rubix Cube project, one being Luke. We have have been struggling to find a nice, clean, object oriented way to represent the cube, but I believe that we have found a good solution. We are going to have a Cube class with methods that rotate sides of the cube. This class will have one property, a collection of Blocks. A single block has six properties: front, left, right, bottom, top, back. The way we will rotate the block will be by specifying a face (top, left, etc…) and a direction, clockwise or counter clockwise. Class outline is below.

Class Cube {
 Block blocks[20];
 rotate(Face, Direction);
}

Class Block {
 Color top;
 Color bottom;
 Color left;
 Color right;
 Color front;
 Color back;
}

The way that you can represent the position of the block is which faces are defined. If a color is not present in the block, then the color will not be defined. Such as the top middle piece will only have the top property not set to null. This way, you can know which position a block is in by knowing which sides have colors defined. So the position of the block with the top, left and front defined is the block in the upper left corner closest to you.

 ______
|\\_\\_\\_\\
|\\|X| | |
|\\| | | |
 \\|_|_|_|

I belive that this Rubix cube has many valid uses for LINQ. One such way defined below.

We were going to do a lot of nasty if statements like

if (top!=null) { //some block on top
 if (front !=null) { //some front block
  if (left !=null) { //top front left
  } else { //top front right
  }
  etc...
}

But instead, with LINQ, we can do the following:

SELECT * FROM blocks WHERE top!=NULL AND front!=NULL AND left!=NULL;

And that will do all the work for us.

I was thinking about other ways to use LINQ, such as the actual updates when a move is done.

UPDATE blocks SET top=(SELECT color FROM blocks WHERE...) WHERE ...

This will update all the block colors for a given move. This may or may not be simpler than a lot of if/else if’s with manual updating.