home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2472 < prev    next >
Encoding:
Internet Message Format  |  1992-08-25  |  1.8 KB
  1. Path: sparky!uunet!dtix!darwin.sura.net!wupost!cs.utexas.edu!torn!watserv2.uwaterloo.ca!watmath!thinkage!atbowler
  2. From: atbowler@thinkage.on.ca (Alan Bowler)
  3. Newsgroups: comp.programming
  4. Subject: Re: Morphology and Convolution
  5. Keywords: morphology,convolution,aaaaargh
  6. Message-ID: <1992Aug26.002016.13961@thinkage.on.ca>
  7. Date: 26 Aug 92 00:20:16 GMT
  8. References: <1992Aug25.160119.28049@linus.mitre.org>
  9. Organization: /etc/organization
  10. Lines: 22
  11.  
  12. In article <1992Aug25.160119.28049@linus.mitre.org> bdickens@el_padre.mitre.org (Brian Dickens) writes:
  13. >I am trying to perform convolution on a rectangular matrix of numbers.  I have a program
  14. >which does basically what I want to do, but it does it 20 times faster than my program.  There
  15. >is a rather straightforward brute force algorithm to do it, which I'm using, but I think there
  16. >might be a better way.
  17. >
  18. >I have two input matrices... one of bytes, and one of floating point numbers.  The floating
  19. >point numbers are used as a sliding window over the data, and for each square on the data,
  20. >the corresponding number on the floating point window is multiplied by the data value, and
  21. >the results of all these multiplications are summed up and stored in the output matrix.
  22. >
  23. >The concept is much like local averaging, but more flexible, because the priorities of each
  24. >square can be adjusted.
  25.  
  26. You want to look at using a Fast Fourier transform.  You do a forward
  27. transform on both the input, and the fixed numbers.  do a point by
  28. point multiply (N operations) and then do a reverse transform.  Since
  29. the fixed numbers are constant, you only need to do the forward
  30. transform on them.  I once worked on a integer version of this,
  31. but given the speed of modern floating point hardware, and all integer
  32. version is not worth the hassles it intoduces.  A good time time
  33. series analysis library may have all the stuff you need.
  34.