Society of Robots - Robot Forum

Software => Software => Topic started by: lemontree on April 29, 2008, 08:47:54 AM

Title: Walsh Hadamard Transform, O'Connor Transform
Post by: lemontree on April 29, 2008, 08:47:54 AM
I have put some code relating to the Walsh Hadamard and O'Connor transforms (various programming languages) here:
http://code.google.com/p/lemontree/downloads/list (http://code.google.com/p/lemontree/downloads/list)
You can have a look.  Anyway the WHT is very fast, I can do 1,400 65536-point transforms per second on my cheap laptop.
Fast enough for processing real time video.  There is also code for a EDAX genetic algorithm to find the minimum of some function.
Sean O'Connor
Title: Re: Walsh Hadamard Transform, O'Connor Transform
Post by: hgordon on April 29, 2008, 11:36:00 AM
Years ago (in 1990), I wrote a version of JPEG encode/decode using the WHT in place of the DCT (discrete cosine transfer).  At the time, the state-of-the-art PC was run 20MHz 80286 or 16MHz 80386, so computing cycles really counted.  I actually didn't change the quantization or huffman tables, so the implementation was suboptimal, but it was REALLY fast, and the difference in file size between JPEG's using DCT vs WHT was less than 20% for comparable quality.  I think I still have that code saved somewhere.
Title: Re: Walsh Hadamard Transform, O'Connor Transform
Post by: lemontree on April 30, 2008, 03:24:24 AM
I was personally shocked when I first got 1000 65536-point WH transforms per second using the SSE assembly language instructions on a home pc.  You can actually do the transform on a Nvidia CUDA enabled graphics card about 30 times faster again, there is source code on their web-site.
At the moment I am looking at using the OCT (which combines the WHT with randomly selected permutations to transform image or sound data into the Normal or Gaussian distribution) for Hash tables and Bloom filters.
That sounds very complex but it is not really.  Basically I am using the OCT as a very fast and controllable hashing function for large data sets.  You can also use the OCT for Genetic algorithms and a few other things.
Anyway I have provided BASIC code that should be understandable enough for those that have a bit of maths.
I am interested in fast, simple algorithms for AI.  I do think there is plenty of room for some smart young kid to combine simple algorithms into high power AI.  I am old now by the way.   

Title: Re: Walsh Hadamard Transform, O'Connor Transform
Post by: hgordon on April 30, 2008, 10:49:32 AM
I am old now by the way.   
Okay - that's funny.  We'll have to compare notes.
Title: Re: Walsh Hadamard Transform, O'Connor Transform
Post by: lemontree on April 30, 2008, 06:00:10 PM
"You did get old already."-wife
Which is better than than what my old landlady once said to me. "Have a good weekend - If that is possible for you."
I always have a great time, thanks very much:P
I only recently found out about Bloom Filters
http://en.wikipedia.org/wiki/Bloom_filter (http://en.wikipedia.org/wiki/Bloom_filter)
I seems like they would be great things for teaching a small robot a few tricks.
I wish there was a cook-book collection of simple AI algorithms, It would be very useful for everyone.
Perhaps I will try to put one together. Maybe, maybe, maybe.
 
Title: Re: Walsh Hadamard Transform, O'Connor Transform
Post by: hgordon on April 30, 2008, 07:21:04 PM
I only recently found out about Bloom Filters
http://en.wikipedia.org/wiki/Bloom_filter (http://en.wikipedia.org/wiki/Bloom_filter)
I seems like they would be great things for teaching a small robot a few tricks.
I wish there was a cook-book collection of simple AI algorithms, It would be very useful for everyone.
Perhaps I will try to put one together. Maybe, maybe, maybe.
The Bloom filters look interesting.

There definitely seems to be a need for introductory literature for robotics a.i.  I'm surprised that there aren't many useful texts beyond Braitenberg's Vehicles, though this seems to be in the process of changing.  For neural nets, Evolutionary Robotics is good, and they have software, but there's no tutorial to put the text and the code together.  For Python, Bryn Mawr and Georgia Tech are doing some interesting work which has taken the form of an intro robotics course - http://wiki.roboteducation.org/Introduction_to_Computer_Science_via_Robots . I think within another 2-3 years, this approach will be widespread in universities.
Title: Re: Walsh Hadamard Transform, O'Connor Transform
Post by: lemontree on May 03, 2008, 05:19:21 AM
I have just put x86 assembly language code on my google code site.  There are a couple of simple demos and a timing demo.

http://code.google.com/p/lemontree/downloads/list

The assembly language code is embedded in Freebasic which should make it easy to use, or easy to inline with another language ie c.
You will require a cpu that has SSE 3, otherwise it's a no go.