go_away

Author Topic: Walsh Hadamard Transform, O'Connor Transform  (Read 4100 times)

0 Members and 1 Guest are viewing this topic.

Offline lemontreeTopic starter

  • Jr. Member
  • **
  • Posts: 38
  • Helpful? 0
Walsh Hadamard Transform, O'Connor Transform
« 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
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

Offline hgordon

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 373
  • Helpful? 7
Re: Walsh Hadamard Transform, O'Connor Transform
« Reply #1 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.
« Last Edit: April 29, 2008, 11:38:43 AM by hgordon »
Surveyor Corporation
  www.surveyor.com

Offline lemontreeTopic starter

  • Jr. Member
  • **
  • Posts: 38
  • Helpful? 0
Re: Walsh Hadamard Transform, O'Connor Transform
« Reply #2 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.   


Offline hgordon

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 373
  • Helpful? 7
Re: Walsh Hadamard Transform, O'Connor Transform
« Reply #3 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.
Surveyor Corporation
  www.surveyor.com

Offline lemontreeTopic starter

  • Jr. Member
  • **
  • Posts: 38
  • Helpful? 0
Re: Walsh Hadamard Transform, O'Connor Transform
« Reply #4 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
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.
 

Offline hgordon

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 373
  • Helpful? 7
Re: Walsh Hadamard Transform, O'Connor Transform
« Reply #5 on: April 30, 2008, 07:21:04 PM »
I only recently found out about Bloom Filters
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.
Surveyor Corporation
  www.surveyor.com

Offline lemontreeTopic starter

  • Jr. Member
  • **
  • Posts: 38
  • Helpful? 0
Re: Walsh Hadamard Transform, O'Connor Transform
« Reply #6 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.



 


Get Your Ad Here

data_list