Java Image Comparison / Motion Detection

I've recently purchased a wireless security camera which is very conveniently smaller than a cubic inch. Well the imagination runs wild once you've got this device,... Who can I spy on? What can I monitor? What does the domestic worker actually do when I'm at work?.. and so the list continues.

I played around in java's JMF for a day and soon had a small app that recorded one still frame per second. Now I could review the recorded images when getting home at the end of the day. Hovever, 1 frame per second equates to 36000 images over the 10 hour work day that I'm not at home! I don't really want to record motion video - yet. I'm still happy with working with images,.. albeit a lot of them. So now I've got a haystack of images, and presumably somewhere inside of them is the needle of interesting footage.

I searched pretty hard for a Java image comparison class or library and could not find anything. Just a whole bunch of forum posts declaring how advanced the topic can get. So sleeves up, I created my own rudimentary ImageCompare class. (Download Link). It's not bulletproof, and its not lightspeed, but for my purposes it's done the job perfectly.

The class breaks up the images into smaller regions and compares the brightness of each corresponding region. If any particular pair of regions are vastly different then something must have changed in that part of the image.

How to use:

// Create a compare object specifying the 2 images for comparison.
ImageCompare ic = new ImageCompare("c:\\test1.jpg", "c:\\test2.jpg");
// Set the comparison parameters.
// (num vertical regions, num horizontal regions, sensitivity, stabilizer)
ic.setParameters(8, 6, 5, 10);
// Display some indication of the differences in the image.
ic.setDebugMode(2);
// Compare.
ic.compare();
// Display if these images are considered a match according to our parameters.
System.out.println("Match: " + ic.match());
// If its not a match then write a file to show changed regions.
if (!ic.match()) saveJPG(ic.getChangeIndicator(), "c:\\changes.jpg");

The setParameters() accepts four parameters.

1. The number of vertical columns in the comparison grid.
2. The number of horizontal rows in the comparison grid.
3. A threshold value. If the difference in brightness exceeds this then the region is considered different.
4. A stabilization factor. In future I will calculate this automatically since it is proportional to parameters 1 and 2.

setDebugMode() is completely optional and only really usefull while designing your parameters.

After running compare(), match() will hold the result.

Example:
The above code was run on the following two images:




The console output looked like this:

|0,0,0,0,0,0,1,0|
|0,0,0,0,0,0,0,1|
|0,0,0,0,0,0,0,3|
|0,0,0,0,0,1,1,8|
|0,0,0,0,0,0,0,8|
|0,0,0,0,0,1,0,0|
Match: false

... and the image output (changes.jpg) looked like this:



On my todo list:

• Provide an array/vector of changed regions, or number of changed regions.
• Heuristically determine a stabilizing factor, thus not having to specifying one.
• Allow for the input of area vectors before comparison for the purpose of excluding or only checking these areas.
• I'd also like to integrate this into a more real time solution that then exposes events and the like.

What you see here is a very alpha stage development. Take it and use it if you like, but do so at your own risk,.. or frustration. I'll try post some updates to this code as and when significant changes have been made.

Follow-up post: http://mindmeat.blogspot.com/2008/11/java-image-comparison.html

Google Treasure Hunt - Question 3 & 4

I grouped my solutions to questions 3 and 4 together for two reasons.
a) Life is short - I'm saving time.
b) Question 3 didn't involve me writing a program to solve it and there's not much to talk about anyway.

The competition can be found here: http://treasurehunt.appspot.com/

Question 3

A packet is sent out from host H with a destination of 41.196.52.48. Which nodes does the packet pass through on its way to the destination? (include start and final node in your answer)

They then provide you with a diagram and a routing table.

Personally I thought writing a program for this would be more labor than automation. So I pulled out the local handy spreadsheet application and pasted in the routing table. Then node by node, traced the path of the packet going through the network. My solution passed through 8 or 9 nodes to reach its destination. Waiting the 8 hours for my confirmation was more challenging than the question.

Question 4

Find the smallest number that can be expressed as
the sum of 3 consecutive prime numbers,
the sum of 23 consecutive prime numbers,
the sum of 999 consecutive prime numbers,
the sum of 1489 consecutive prime numbers,
and is itself a prime number.

For example, 41 is the smallest prime number that can be expressed as
the sum of 3 consecutive primes (11 + 13 + 17 = 41) and
the sum of 6 consecutive primes (2 + 3 + 5 + 7 + 11 + 13 = 41).

A funny story here: This question, if my calculations were correct, was released around 11:15pm GMT, around 01:15am in Durban ZA where I live. I couldn't wait for morning so I set my clock for 01:30am to specially get up and read the question. The funny thing about this is the next day someone said to me; 'I bet there are people that get up in the middle of the night to solve these things'. I just kept quiet.

Well I slept on it -literally- and made this Java app the next day.
To run:

java.exe GoogleQ4 40 1489 999 23 3

The first argument is the certainty factor for testing primes. The rest of the arguments are obviously the parameters from the question.
For the parameters quoted above my program gave the following output: (I haven't verified this result..)

********************************************
9491851 -> computed in 141 seconds.
********************************************

A further explanation of my logic:
Now I'm no mathematician so I'm not aware of any direct formula to solve this puppy; So I'll resort to a mechanism of over complicated logic. I visualized this problem as a set of 'Slide Rule Thing-a-ma-gigs' sliding over the prime number set.


The example in the image above doesn't balance but use it to visualize this process:
1) Drag the first slide to its next offset.
2) Calculate the slides new total. (All the numbers it hovers over)
3) Move to the next slide above it.
4) Drag this slide from an offset where the slides total will be smaller than the previous slides total, to somewhere where the slides total is greater. If a matching total is found then we can recurse to steps 3 and 4 for all our other slides.
5) When a similar total is found for all slides then we have our answer.

The method I have used requires a lot of array manipulation. I figure it makes sense to enter your arguments greatest to smallest as this will greatly reduce the amount of work the machine will have to do.

Other things that might help to speed up the slide rule machine:
- The use of vectors or linked lists (something not fixed array based) would probably help.
- A better algorithm to position the initial offset of each slide when recursing to that next slide. Originally I just started each slide from 2 everytime. gasp!. After a while I realized I was moving every slide 1000 odd positions before it was even close to solving the answer. Currently it starts the next slide where the previous left off.

Well thats all there is to my solution. Probably not the best, but I got the answer right first time. Whoopee.

Google Treasure Hunt 2008 - Question 2

This is a continuation of my solutions to Google's treasure hunt. My post on question 1 can be found here.

The Question:

Here is a random zip archive for you to download:
GoogleTreasureHunt08_123456123456123456.zip

Unzip the archive, then process the resulting files to obtain a numeric result. You'll be taking the sum of lines from files matching a certain description, and multiplying those sums together to obtain a final result. Note that files have many different extensions, like '.pdf' and '.js', but all are plain text files containing a small number of lines of text.

Sum of line 2 for all files with path or name containing foo and ending in .xml
Sum of line 4 for all files with path or name containing mno and ending in .pdf
Hint: If the requested line does not exist, do not increment the sum.

Multiply all the above sums together and enter the product below.

Well this question begs for a [program,script,bash stmt] to be written. It doesn't even begin to make sense to do this manually..

Here's my Java source: http://b22222.com/files/GoogleQuestion2.java
One just needs to modify the set of rules and the location of the unzipped folder.

I just posted my answer for question 3; I have to wait 8 hours for the result! Oh well, fingers crossed.

Happy Googling!

Google Treasure Hunt 2008

So Google is running a treasure hunt. 1 puzzle a week for 4 weeks. I love puzzles.

The first puzzle they have up goes something like this:

A robot is located at the top-left corner of a 52 x 52 grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. How many possible unique paths are there?

For a while I tried to picture the mechanics of this problem in my head. It was too much,.. I would soon get lost trying to keep track of a dozen different paths and shapes all at once. So i resorted to paper. Not too long and I was having good progress. I would draw grids with numbers in each cell representing how many paths could be made from that cell to the bottom right. The trick was to start small.

I drew grids for 2x2 and 3x3. I still couldnt work out the pattern,.. Then I drew 2x3 and 3x2 grids; Bingo.



Overlay/Imageine a 3x2 and 2x3 grid at the bottom-right of the grid above; To work out the total number of paths from the last missing cell (of 3x3) is simply all paths available in both the 2x3 and 3x2 grids. Still dont understand,..
Simply put: The number of unique paths from any cell to the finish is equal to the sum of, the number of paths from the cell on the right, and the cell below it.

Here is the Java source I used to calculate my grid (55 x 60). My answer was 696940125414123253093858308567840.

I would be interested in looking over the mathematical formula that calculates this directly incase anyone happens to know it.

Happy treasure hunting!

PS: My code calculates the map upside down and other way around... In other words, the robot is going from bottom right to top left. Not the same as the picture above.

BR cleaner VS other cleaners

I've always got a bit of a mess on my hands when I'm finished CSS'ing an HTML form. With all the different forces shaping form development I sometimes find it difficult to get a form to look exactly the same in every browser, and to look pretty when degraded out of CSS.

Traditionally I've used divs or spans as a 'cleaner' element to clear the floats above it. I don't know where I learned this common trick, but for as long as I can remember now I've used the cleaner class and some empty divs round around the form to try correct line breaks and the form layout.

Completely randomely I tried something different today. I used a line break element as my cleaner. omg - Why have I never done this before? Now my line breaks act as line breaks when
CSS fails, and then they act as cleaners with CSS enabled. So far its been too good to be true,.. literally; I'm waiting to see why I haven't seen this elsewhere - Waiting to see where it breaks.

Here's a demo of what my cleaners now look like:

<style>
br {
    display: none;
}
.cln {
    display: block;
    clear: both;
}
</style>
... blah blah fish paste ...
<div>My floated left element</div>
<div>My floated right element</div>
<br class="cln" />
<div>The rest of my content</div>

Some last notes:
I hide all line breaks by default because they are really there only for graceful degradation. If the client has CSS enabled then I don't want extra line breaks mucking up my presentation. On the other hand, when CSS is enabled then the linebreaks with the 'cln' class will be displayed and, simply put, line break over the above floated elements.