home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / compress / research / 98 < prev    next >
Encoding:
Text File  |  1992-07-28  |  1.9 KB  |  35 lines
  1. Newsgroups: comp.compression.research
  2. Path: sparky!uunet!utcsri!torn!watserv1!marconi.waterloo.edu!praetzel
  3. From: praetzel@marconi.waterloo.edu (Eric Praetzel)
  4. Subject: Re: Algorithm for finding set bits in a bit-string.
  5. Message-ID: <Bs3yBx.7AA@watserv1.uwaterloo.ca>
  6. Sender: news@watserv1.uwaterloo.ca
  7. Organization: University of Waterloo
  8. References: <1992Jul26.010325.9885@infonode.ingr.com> <MOSS.92Jul25222337@ibis.cs.umass.edu>
  9. Date: Tue, 28 Jul 1992 16:40:45 GMT
  10. Lines: 23
  11.  
  12. In article <MOSS.92Jul25222337@ibis.cs.umass.edu> moss@cs.umass.edu writes:
  13. >The "find first set bit" operation was recently discussed at length in
  14. >comp.arch, and could be relevant, especially if the one bits are sparse.  If
  15.   An interesting application is to locate point sources on a CCD scaned image.
  16. In a virtual reality case here the sources of IR light are 4 LED emitters
  17. mounted on the back of the helmet that holds 2 cameras.  The LEDs are not in
  18. one plane so location of full spatial postion is possible.  By using a run
  19. length encoding the 300 * 400 CCD map can be "compressed" and processed so
  20. that when the data is read by the program most of the background 0's have
  21. been compressed into a # representing the count.
  22.   The result is that in real time (60 Hz) the computer (with a very limited
  23. input bandwidth) can take in the compressed image, find the sources, refine
  24. their location to about 1/3000 (center extraction) and do it in real time.
  25. This is the only real world application I know of where data compression 
  26. actually aided in processing of the data.
  27.   And getting back around to square one.  All that this thing is, is a 
  28. glorified set bit searcher  :-)
  29.   As for S/W solutions, the best would be an array (assuming its a smallish
  30. 8 or maby 10 bit #) but that can vary depending upon architecture.  If its
  31. a bigger number then just divide it into byte sized pieces and work your way
  32. up thru the bytes.  This may or may not be faster than bit shift/test carry.
  33.   - Eric 
  34.  
  35.