Semantic Video Analysis

There’s an interesting article over at the Economist.com about semantic video analysis – using computers to try to recognise what a picture or video is about.

To a microprocessor, a photograph of James Bond might as well depict a cat in a tree. That can make tracking down a video on the web or searching through a film archive a painstaking task, unless someone has written a full and accurate description of each item being examined. Anyone who has tried to find a clip on YouTube will know how rare that is.

Well, researchers from Queen Mary (University of London) have made some progress. They say their computer programme can now tell the difference between water and a human being and can sometimes identify more complex images such as a person lying on a beach. It works by a similarity algorithm: the programme has to be input with many tagged images of water and human skin. It then looks for similarities in colour and shape.

What I think is really interesting is how they used an evolutionary algorithm. I blogged about these a week ago and they seem to be popping up everywhere.

Once the computer has identified the colours, textures, colour-distributions and horizontal lines in the groups with the most blocks, those blocks are subjected to a mathematical algorithm called the Pareto Archived Evolution Strategy. This uses the principles of evolutionary biology (generating a lot of slightly different variations, selecting the best among them, and then using that to generate another set of variations, and so on) to reach what is, if all has gone well, the right answer.

In other words, the computer tries to determine the rules which would allow you to most accurately detect whatever you want (and presumably with as few false positives as possible). This is useful – for example with water, the colour and texture could allow you to determine it was water. The shape wouldn’t help at all. Similarly, the size and shape would allow you to detect a mobile phone but the colour would be no use.

The programme also tries to look at the context of the image – objects which routinely appear together. It’s an interesting piece of work. I really wish there was a way of automatically tagging photos of everybody on Facebook through face detection.

Evolving the perfect website through natural selection

The Daily Telegraph covers an experiment to breed the perfect web page design through Darwinian natural selection.

Matthew Hockenberry and Ernesto Arroyo of Creative Synthesis, a non-profit organisation in Cambridge, Massachusetts, have created evolutionary software that alters colours, fonts and hyperlinks of pages in response to what seems to grab the attention of the people who click on the site.

Evolutionary algorithms have in the past been used to design aircraft wings and boat hulls. Because there are so many competiting and contributing factors to how well a certain design works, a human designer won’t find that optimum design which works the best. The idea of using an evolutionary algorithm is you start off with thousands of random and different designs. Each design then undergoes a form of natural selection – for aircraft wings, each design would be loaded into a computer model. The best designs are then “breeded” together to create the next generation of aircraft wings. This process is repeated thousands of times to produce an optimum wing.

The software treated each feature as a βgeneβ that was randomly changed as a page was refreshed.

After evaluating what seemed to work, it killed the genes associated with lower scoring features β say the link in an Arial font that was being ignored – and replaced them with those from higher scoring ones say, Helvetica.

Evolutionary algorithms are certainly a useful addition to the toolbox of engineers. There are of course limitations. Creationists sometimes argue “what use is half an eye?” as a refute to Darwinian natural selection. In this example, half an eye is still better than no eye at all: you might be able to see but you won’t get a sharp picture.

But at least you won’t walk into a wall. But say… why haven’t humans evolved wheels? “What use is half a wheel?” is a good question, and there isn’t a use for half a wheel. If any organism did evolve half a wheel, it would be selected against and therefore natural selection would never lead to a whole wheel.

I think this illustrates well why evolutionary algorithms can never be the end all; we’ll still need human input and design. But it’s great as a way to refine a design.

Read the experiment write up at Creative Synthesis and have a look at the end result.

Software Bugs

A really interesting article in The Economist’s Technology Quarterly this week about how computer programmers use a range of tools to try and cut down on the number of bugs. “An industry rule of thumb is that a bug which costs \$1 to fix on the programmer’s desktop costs \$100 to fix once it is incorporated into a build, and thousands of dollars if it is identified only after the software has been deployed in the field.”

Music in Python

I was learning C but I got a little bit distracted and spontaneously decided to start writing music in Python code. It’s no Beethoven or Mozart… in fact it’s just Yankee Doodle played through the WinSound library. It only works on Windows. The first argument to the Winsound.Beep function is the frequency of the note; the second is the length of the note. The song plays through your computer’s built in buzzer.

Code follows:

`import winsound;beatlength = 300;winsound.Beep(262, beatlength) # Cwinsound.Beep(262, beatlength) # Cwinsound.Beep(294, beatlength) # Dwinsound.Beep(330, beatlength) # Ewinsound.Beep(262, beatlength) # Cwinsound.Beep(330, beatlength) # Ewinsound.Beep(294, 2*beatlength) # D (double length)winsound.Beep(262, beatlength) # Cwinsound.Beep(262, beatlength) # Cwinsound.Beep(294, beatlength) # Dwinsound.Beep(330, beatlength) # Ewinsound.Beep(262, 2*beatlength) # C (double length)winsound.Beep(247, 2*beatlength) # B (double length)winsound.Beep(262, beatlength) # Cwinsound.Beep(262, beatlength) # Cwinsound.Beep(294, beatlength) # Dwinsound.Beep(330, beatlength) # Ewinsound.Beep(349, beatlength) # Fwinsound.Beep(330, beatlength) # Ewinsound.Beep(294, beatlength) # Dwinsound.Beep(262, beatlength) # Cwinsound.Beep(247, beatlength) # Bwinsound.Beep(196, beatlength) # Gwinsound.Beep(220, beatlength) # Awinsound.Beep(247, beatlength) # Bwinsound.Beep(262, 2*beatlength) # C (double length)winsound.Beep(262, 2*beatlength) # C (double length)`

Now just to give the computer some artificial intelligence and I can create my own top 10 hit…

PHP Fractal Generator

I was bored so I thought I’d write a PHP script to generate fractals (like you do). The Mandlebrot set is probably the most well-known fractal so I chose to write a script to generate fractals using the Mandlebrot set:

This is a 500×500 fractal plotted for x (real) values between -1.5 and 0.5 and y (imaginary) values between -1 and 1.

How it Works

The mathematics behind the mandlebrot set involve:

• complex numbers (x+yi)
• argand diagram
• limits

A complex numbers consists of a real component and an imaginary component. i is the square root of -1. A complex number could look like 3+2i, where 3 is the real component and 2 is the imaginary component.

An argand diagram is like a two dimensional number line. With normal real numbers, we can plot them on a one dimension number line, with negative infinity on one end, and positive infinity on the other end. Because complex numbers have an imaginary component too, we need a two-dimensional plane to plot the number.

The Mandlebrot set involves iterating through a sequence:

In words: the first value in the sequence is 0. To find the next value in the sequence, we square the current value and add the complex number (which is the variable). Depending on the input, the sequence will either tend towards infinity or it will remain bounded and oscillate/repeat. If the sequence remains bounded, then it is inside the Mandlebrot set. On my script, I’ve marked these pixels as black.

For those values outside the Mandlebrot set, we use colour to denote how long it takes to reach infinity (in fact we use a shortcut and stop when |z| > 2).

Quadratics come in when we square a complex number – you can just square them as you would with any other quadratic. However, i^2 = -1.

Conclusion

I think it’s pretty amazing how we can generate infinitely complex patterns using such simple mathematics. There is probably only about 10 lines of mathematics in the script; the rest is all PHP/image stuff.

A few notes:

• The script is pretty server intensive. The source code I’ve provided is configured to produce a 100×100 image by default. This took 2 minutes to execute on my machine, but 5 seconds on my friends machine. Both of them are roughly the same spec. Your mileage may vary.
• If you try to generate an image with too many pixels, your PC may crash. You have been warned π
• Try changing the x/y min/max values to zoom or to pan.
• Feel free to hack the script, rip it apart or do whatever you want with it. It’s public domain.

Finding Primes

I’ve been getting into Project Euler a little bit more recently. I found this puzzle really interesting:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

My Original Solver

To my knowledge, there isn’t anyway of telling if a number is prime except from dividing it by all the numbers between 1 and the number and seeing if they are factors. So I implemented the following in Python:

`# Python Script to find 1001th prime number# Original Methodimport datetimestart = datetime.datetime.utcnow()print '\nOriginal Method'i = 0n = 1while i < 1001:    n = n + 1    fail = 0    for j in range(2,n):        if n % j == 0:            fail = 1    if fail == 0:        i = i + 1        #print str(i) + '. ' + str(n)        if i == 1001:            print 'The 1001st prime number is ' + str(n)print 'Time Taken: '+str(datetime.datetime.utcnow() - start)       `

Note the script above calculates the 1001st prime rather than the 10001st prime as the challenge states. When I used a similar script to find the 10,001st prime it took quite a long time on my computer so using the 1,001st to benchmark makes it a lot easier.

Unscientific testing gives the following output after 3 runs (around 21 seconds to solve):

`Original MethodThe 1001st prime number is 7927Time Taken: 0:00:18.344000Original MethodThe 1001st prime number is 7927Time Taken: 0:00:21.047000Original MethodThe 1001st prime number is 7927Time Taken: 0:00:25.078000 `

Stopping

I noticed in the above code that even when the script finds a factor of a number, it’d still continue searching every number above that to see if they were factors. I put in a check:

`    for j in range(2,n):        if fail == 0:            if n % j == 0:                fail = 1 `

This gave the following output after 3 runs:

`Original Method + Factor StopThe 1001st prime number is 7927Time Taken: 0:00:09.547000Original Method + Factor StopThe 1001st prime number is 7927Time Taken: 0:00:11.813000Original Method + Factor StopThe 1001st prime number is 7927Time Taken: 0:00:13.750000`

This halved the time it took to find the 1001st prime number.

Square Roots

With the remaining prime numbers, the script was still searching every single number between 1 and that number in order to determine whether it was a factor. For example with 13, there is no point in checking whether 8, 9, 10, 11 or 12 are factors because they would have to be multiplied by a number between 1 and 2 to get 13 and obviously there are no integers between 1 and 2.

After thinking about it, I realised that there was no point in searching any of the numbers greater than the square root of the number. With the number 12, this means you only have to search up to 3.46 (ceil to 4). Sure, 6 is a factor but you need to multiply it by 2 to make 12. Any factor above the square root of the number will have to be multiplied by a factor smaller than the square root to make the number.

I changed the script so it’d only search numbers up to the square root:

`    n = n + 1    fail = 0    for j in range(2,(n**0.5)+1):        if fail == 0:`

This had a drastic effect on the time required:

`Stop at square root methodThe 1001st prime number is 7927Time Taken: 0:00:00.313000Stop at square root methodThe 1001st prime number is 7927Time Taken: 0:00:00.516000Stop at square root methodThe 1001st prime number is 7927Time Taken: 0:00:00.453000 `

From 21 seconds to 0.4 seconds – a speed up of 5000%.

The square root method managed to calculate the 10,001st prime in 11 seconds – a far cry from the 20 minutes or so required using the original script.

Project Euler

Project Euler is a really nice and interesting set of mathematical and programming puzzles. It’s a nice way to practice maths skills, developing algorithms and solving puzzles.

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems. Please be warned that the problems are challenging and you are unlikely to make much progress if you have no knowledge of programming.

You’ll have to create an account so that the website can track your progress but you can look at the puzzles without registering. There is quite a large range of puzzles – it’ll mainly require maths skills but programming is important.

I chose to develop my solutions in Python even though I have a lot more experience with PHP. I did this for two reasons – I wanted to practice Python and Python is much better suited to doing many of the tasks. For example, Python will happily calculate 1001^1001 and give you the full solution. Other programming languages will probably freak out and give you a partial solution or no solution.

I signed up earlier today and I’ve solved 8 puzzles with a current rating of 3% genius. Let me know how you get on

Building on Platforms

When writing a script or a program you’ll probably develop it on a platform – you could develop it using a certain programming language, for a specific operating system or by using a certain API. The stability and future of the platform is important.

I can think of three specific examples where this has affected me:

• Invision Board used to be a free PHP forum software. The developers said it’d always be free (or implied it). It was a fantastic script so was a perfect platform for building a whole site or community on. For such reasons, I begun the IPB SDK project. After spending probably over a year writing the script (which essentially meant writing a whole bulletin board based around IPB), debugging and supporting it, it went paid meaning myself and others could no longer use it or develop it. This was really frustrating and was a bad platform choice.
• Messenger Plus Live! has been trying to establish itself as a platform for Messenger related scripts and plugins, especially with the recent addition of the scripting API. I experimented a little with the scripting and produced some scripts but I’m reluctant to develop any more scripts on the platform because of the inclusion of the spyware sponsor program. Of course it’s optional and it funds the development of Plus!, but I don’t really want to develop software on a plugin which has the option to install spyware. For an end-user application, it’s acceptable but as a platform to run other people’s stuff it’s not.
• Companies like Alexa and Google have released open Web APIs which can allow you to interact with their product but they do not guarantee they will be free once they leave the beta. This is a bit frustrating especially if you spend ages developing a script on a platform and then suddenly discover no one can use it any more because they decided to take the API offline.

It’s important that platforms have a clear direction and are preferably open source and free. The World Wide Web is a great platform for information and products as it’ll always be there and it’ll always be free and accessible to everyone. Firefox and XULRunner are a fantastic framework for web-enabled applications as it’s open source and free, and many people have it. Languages such as PHP, Python and Perl are great as they’re cross-platform and free unlike proprietary languages such as Visual Basic.

Sudoku Solver

I was bored and had a bit of time this morning so I thought I’d practise Python a little and try to write a program to solve Sudoku. I find writing programs like these quite interesting and quite a nice way to learn a language, and unlike copying scripts out of books, the script you produce will be semi-useful. I decided to do it in Python as I’ve not done Python in years and it was kinda rusty.

I’m using a pretty slow and crappy algorithm:

• Load the sudoku puzzle into a multi-dimensional dictionary – the top left square is referenced by [0][0], the bottom right by [8][8].
• Loop through all the squares starting with the top left square and working across. When a blank square is found, try to solve it by:
• Firstly creating a list of all possible values (numbers between 1 and 9)
• Removing the values of known squares on the same row
• Removing the values of known squares in the same column
• Removing the values of known squares in the 3×3 square.
• If there is only one possible solution, fill it in.
• Once it has reached the end, it’ll start another pass beginning at the top left corner again. Some extra squares may be able to be solved now as additional squares have been solved making it possible to solve other squares.
• When all squares have been solved or no further squares have been solved, stop and print the result.

This algorithm is probably pretty slow and won’t always solve the puzzle – it can’t guess and there are some more complicated ways to solve Sudokus which the script doesn’t implement. But for the sake of creating a basic, working Sudoku solver, it does pretty well.

I used the following input (x denotes an unknown square):

`91x7xxxxxx326x9x8xxx7x8x9xxx86x3x17x3xxxxxxx6x51x2x84xxx9x5x3xxx2x3x149xxxxxx2x61 `

It came back with the completed Sudoku in about a second:

`918745632532619784647283915286534179394178256751926843169457328825361497473892561 `

If you want a copy of the source, grab it here. You’ll have to change the path in it around line 13 so it points to your sudoku.txt file. Make sure your sudoku.txt file is formatted correctly with each row of the sudoku on it’s own line and unknown squares designated by an x.

• If you want a proper Sudoku Solver which works properly, there are tons on Google