straightening an image of horizontal lines

I’m working on a mobile app for photographing sheet music and then playing it.

When I first approached this, I considered using a Hough transform, which is a mathematical tool for finding lines in an image. It produces a matrix based on MC space (the tangent and y offsets of the lines).

I could then use the matrix to figure out what was being shown on the sheet.

That method is very computationally expensive.

After considering it, trying it, then abandoning it, a better solution came to me while I was thinking about something totally different.

Sheet music is composed of mostly horizontal lines, while everything that is not a horizontal line is part of the notation itself.

So, all I need to do is first locate the horizontal lines, and everything else will be easy to find.

The first problem, then, is how to make sure that the sheet itself is level.

How I ended up doing this was to measure mean difference of the average colours of each ‘y’ coordinate of the image, and try offsetting one side of the sheet up and down until I reached the maximum mean difference.

This is easier to understand visually.

Let’s consider this image:

As a human, we find it easy to spot the skew and fix it, but a computer is not so intuitive.

Here is the same image with the “x” coordinates of each “y” coordinate averaged out (motion-blurred, basically)

That’s a simple average of the “x” coordinates, and there already appears to be a pattern.

Next we shift/skew one side of the image up or down a few pixels and test it again. In my tests, I use a naive “brute-force” test of all offsets from -15 to +15. Here are blurs of a -11 offset and a +11 offset:


-11

+11

Obviously, the right one is the -11 one. But how do we tell a computer what the “obvious” solution is?

Well, the right answer is probably to come up with a way to measure which one is more “noisy”, but I couldn’t think of a simple way to do that.

Instead, what I did was to measure the average colour in the each image, use that average to find the mean difference in each image (how far from the average “gray” each line is), and the one we are looking for is the one with the highest mean difference.

Having found the right offset (-11), we then simply shift the pixels in the image by that much (in Y and X space), and end up with these images:


original image

straightened

The next task is to fix skewing, but it will use basically the same technique.

demo

souls

I was just watching a clip of Ricky Gervais being bewildered by a Christian.

The girl in the clip talks about a soul wafting its way to Heaven to go play with the ghosts of friends, pets, etc.

I’ve a number of problems with this.

Rewarding a soul with heaven for whatever it does during life is stupid. Life has been likened to a bird flying through endless night, then very briefly flying through a lit room, and out the other side into endless night again. The idea that the eternity of journey /after/ that brief visit to life is judged by what you do during life is preposterous.

If a soul exists, and controls the body, then it must somehow be connected to the body in order to control its actions. In return, it is logical that the body can affect the soul. This implies that a soul is affected by physical laws, yet there is no evidence that a soul has ever been detected using physical tools.

If there is exactly one soul per human being, then this implies that souls can be created to match the need for them, and are created by the simple act of men and women having sex with each other. To say otherwise is to imply that the creation of a soul somehow causes men and women to have sex with each other to create a body for the soul to live in.

I don’t understand the need for a soul anyway. According to common theology, only humans have souls, yet the rest of the animal kingdom appears to get along just fine without souls. What are they needed for?

the awe of programming

“A few weeks into the class, there was a moment where I finally understood recursion. It felt so satisfying that my next thoughts went something like: ‘Wow, that’s awesome. I like that. I think I like computer science.'” – from betabeat.com

I can tell you that I know /exactly/ how she felt. I first “got” recursion (a programming method) after a summer scholarship in DCU, waaay back when I was in secondary school. It was really an awesome moment – understanding the possibilities of it felt like becoming one with the universe. It /really/ felt like that.

It felt “awesome”, and I mean that literally; I was in awe that such a simple concept could create such amazingly powerful solutions.

I’ve used recursion quite a lot over the years. In fact, only yesterday, I wrote a TSP algorithm that uses depth-first recursion to find the shortest distance between a number of points on a map. I’ve also used it for generating flow charts for food industry applications, creating breadcrumbs in website navigation, and for solving other seemingly unrelated problems.

As a father of two kids, I would love to have them take up my own path and become programmers, but I also know that you can’t “teach” the feeling of satisfaction/enlightenment that you get when you finally solve a tricky problem, and that feeling is very important to get early on if a child is to feel an urge to carry on.

Jareth (my son) doesn’t know it yet, but he’s getting Lego Mindstorms this year for Christmas. I already know he’s going to be a good programmer, based on his problem solving skills in some games, and some of the technic creations he’s built. Hopefully Mindstorms will let him have his own “ah hah!” moments early on, encouraging him to go deeper into programming as he gets older.