Sketch Processing Update

Today I have 3 exciting new developments for you, along with the usual enthralling updates!

We'll start with the bit most of you will just want to see. The video.

Fun Colours

After developing the application to its current state with little more than the odd pure red, green or blue line to keep my brain awake, I decided it was time for some bright colors!

Technically the real reason behind all this, was to have a simple way of identifying different properties by colour coding the line segments based on specific properties such as how curved they are.

Last year I spent a few weeks writing low level colour manipulation algorithms for mobile phones, so I knew that a HSV to RGB converter would provide me with the ability to transform the parameter to an angle (Hue), and pump out nice rainbow colours.

This diagram is a good representation of HSV colour space:
(H: Hue, S: Saturation, V: Value )



I found a simple HSV -> RGB conversion function online, which was using floating point numbers. Again, after my work on mobiles last year I have accustomed to avoiding floats where possible, so I rewrote the function with bit shifted fixed point numbers to save some processing speed.

The result was lovely, but in the end I decided just to use the colours for the input stroke, with the colours cycling based on the input point ID.

Slider Bars

Developing on a really low-level platform like the DS means you are constantly having to write your own little classes to do the most basic of tasks.

Think of a button for example. You would think it'd be pretty straight forward, right? No.

Anyway, as annoying as a solid button system was to implement, a slider bar was all the more frustrating (actually, that's a lie, I quite enjoyed building it!). The toggle buttons simply link to a Boolean value which is altered as they are pressed, reflecting the current state of the button (toggled = true, and untoggled = false).

I started with my screen object class which had a "Touched" and "Released" inherited functions which were passing in a bool of whether the stylus was inside them or not. This was fine for the buttons, but when you want a slider which needs to know where abouts within the itself the stylus is, more information is required. This meant rewriting the function from the top, with the stylus co-ords being passed in, and the root object calculating and passing down whether it was inside or not.

This worked well and the rest quickly fell into place, and I added a linked a linked variable with min and max values acting as the effected value.

I was using my first slider as a multiplier for the calculation of the Beziér control points (see the next chunk of text), but these were generated when the sketch was processed (only once at the end of the stroke input). To rebuild them I had to press the "A button" which ran a little function that reprocessed the stroke.

Unfortunately whenever the slider was adjusted I had to rebuild the stroke manually. This is when I decided to get my head around function pointers.

They turned out to be surprisingly straight-forward and I quickly added a function pointer to the slider that would run whichever function you specify whenever the slider value was altered. I was really impressed with the result, and it makes the application much more interesting to use. :)

Beziér Curves

The final stage of the Stroke Approximation technique is to identify the curved areas of the stroke and represent them with Beziér curves. To identify the curved areas, a ratio is calculated for each line segment of the final hybrid fit polyline. l2:l1.

l2 is the distance along the original stroke from one point on the polyline to the next, and l1 is the distance directly between the two points.

Curved areas will obviously have a higher ratio than the more accurately represented straighter segments. The identified curved segments can then be removed from the polyline and represented with Beziér curves.

Beziér curves are a represented by a start point, an end point and a number of control points. The more control points a curve has, the more complex it becomes. The number of control points denotes the "order" of the curve, representing its mathematical complexity. A cubic curve (as seen below) has two control points.



Generating the Beziér curves to represent the curved ares of the sketch is a matter of finding an empirical value that best fits the user's drawing style. This is the multiplier that the slider adjusts.

To render a bezier curve it is best to represent it as a polyline when you have limited rendering capabilities available. This means we need to work out several points along the curve and use them as the polyline representation of the Beziér representation of the polyline representation of the original stroke! This is starting to get crazy!

Basically you need to boil down the of the curve by calculating sub curves using the control points, until a curve with 1 control point remains. this will give you the coordinate required at a chosen percentage along the original curve.

I won't go into the maths too deep at this point as I doubt anyone will even read this far, but there are some really interesting overlaps with Fibonacci series here which I may look into more at a later point!

If you want to have a play with an insane Java Applet of a cubic Beziér curve, I recommend checking out this site.

This image was just too cool to leave out. :)

Sorting Algorithms

During the development of my Sketch Processing application I reached a stage where the processing of each stroke was starting to take amounts of time noticable to the naked eye. At this point As the application was at an early stage of its life, my concerns were that if I was getting slowdown already then I had much worse to come.

Generally the processing was taking around seemingly exponential lengths of time in comparison to the number of points in the input.

After a quick time profiling addition to the code I was able to break down the processing in order to find if there was one chunk of code eating up my processing time. It soon became apparent that sorting the curvature and speed data (float arrays equal in size to the number of input points) was accounting for around 98.5% of the processing for an input of 200 points (around 2 seconds to process!).

I was relieved to find it was just a sorting algorithm that was the nuisance as I knew plenty about them and knew there would be a quicker solution available.

After reading through my basic and frankly terrible original sorting process, I realised that I'd written a type of Insertion Sort algorithm(one of the slower types of sort).

Some quick googling revealed a nice selection of algorithms and explained how there were basically 2 groups of comparison sorts. Fast, and slow.

These handy graphs show the variations in speed between the two groups, O(n^2) and O(n log n).





You can see that the slow algorithm graph has a vertical scale measured in hudreds of secionds whereas the fast algorithm graph has a vertical scale measured in tenths of seconds. This is clearly a huge difference.

Some more research helped me identify the Comb Sort as a reasonable solution. It acts in a similar way to the Bubble Sort, a relatively slow algorithm, however instead of comparing adjacent values, an initial gap of the data length is used and reduced by 1/(~1.3) each recursion over the data. This "combs" through the data and eliminates the comparison of a large portion of the unneccessary comparison, making the algorithm nearly as fast as a Quick Sort, whilst retaining the simplicity of a Bubble Sort.

Once the Comb Sort was applied, I recorded increases in speed of around 100 times, bringing the total processing time back down to unnoticable speeds.

Success!

This is like a "Eureka moment" for me right now; I have just successfully finished writing my first sketch processing algorithm on for the DS app.

The current system is using a basic feature point identification system, similar to the initial stages of Stroke Approximation.

I haven't timed the process yet but the output seems as instant as could be, which is good news. Woo!

Here's a screen shot of it processing a star I drew. Black squares are the identified feature points.

Sketch Processing Progress

After a week of doing very little work on my sketch processing project, I decided to get some more coding done. Well it is now 6:25am and a lng way past my intended bedtime, but progress is good. I started by fixing a few bugs from my last coding session and quickly got back into the swing of the code. I started to put together some code to generate a set of curvature data from the initial stroke information.

In comparison to XNA and C#, the biggest problem with programming on the Nintendo DS is that there is almost no help from the IDE, every error takes about 10 times longer to debug and the actual writing of the code is so much more tedious. Anyway, my point is that with something like C#, all the functionality is at your fingertips allowing you to quickly print to the screen or output information to a console window or to a file. The lack of all this on the DS means debugging or writing new and specifically math-intensive code, becomes all the more difficult.

So I had put together this basic code, but without some tests I wasn't confident it would be getting the correct output data, and without break-points or any decent interface, I was working blind.

So instead of continuing as I was, I decided to create a simple C# app that loaded some pre-written stroke data from a text file (created by copying values from the screen of the DS app), and processed the data with almost the same code that was running on the DS. This was I could visualise, debug and check the code effectively, and reflect any changes in the DS code afterwards.

I basically ended up writing a nice little app that drew a representation of how the stroke would be seen on the DS screen, a dynamically sized curvature graph of the data with a mean cut-off line, data values, feature point identification and labeled, zoomed views of identified corners.

All in all the tool is quite useful and I will be using it for analysis on data taken directly from the DS app to visualise the information as image files, graphs and much more. All these can then be used in my report as evidence of the data and processing.

I also updated some of the GL rendering code on the DS app, but still need to fix some of the timer code.

So overall, quite good progress. Now I must get to sleep before the sun comes up and I'll fix the spelling and grammar mistakes in this when I wake up.

Sketch Processing in Games

Sketch Processing is the system of taking input data from an a device such as a touchpad and transforming the original raw data into a chosen output.

I am currently undertaking a project in which I am attemptng to implement several sketch processing techniques in a Nintendo DS application in order to analyse the possibilities and extents of the technologies within a gaming environment.

So far I have researched and analysed existing techniques spanning the subject and chosen a few to implement in my DS application.

I will be looking into:

• Stroke Approximation with Average Based Filtering.
  
• Scale Space Filtering.
• Least Square Fit Fluid Sketching.
• $1 Recognizer.

In further blogs I intend to go into more detail on each of these techniques.