home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume11 / quadtree / part01 / README < prev    next >
Encoding:
Text File  |  1990-04-03  |  3.8 KB  |  100 lines
  1. QUADTREE IMAGES by Bob Glickstein
  2.  
  3. A ``quadtree'' is a means of encoding an image as a tree structure.
  4. Each node of the tree has up to four children.  The root node
  5. represents the entire image; its children represent the four quadrants
  6. of the entire image; their children represent the sixteen
  7. subquadrants; the children of those represent the sixty-four
  8. sub-subquadrants, and so on.
  9.  
  10. A leaf node corresponds to a single pixel, and is marked with the
  11. color of that pixel (in this implementation, black or white only).  If
  12. a non-leaf node has two or more children of the same color, then that
  13. color is stored in the parent and the children are deleted.  Thus, if
  14. an entire quadrant (subquadrant, sub-subquadrant, etc.) of the image
  15. is white, that information can be stored in a single quadtree node,
  16. and all of the children of that node can be removed.
  17.  
  18. For certain images, this encoding yields enormous savings in storage
  19. size.  Such images are typically line drawings or other bitmaps with
  20. several areas of solid black or white.  Images with a lot of dithering
  21. or stippling, such as scanned images, tend to yield little or no
  22. savings in space.
  23.  
  24. An amusing aspect of quadtrees is that they can be displayed according
  25. to a depth-first or a breadth-first traversal of the tree.  In a
  26. depth-first traversal, first the prodemonant color of the entire image
  27. is displayed; then the predominant color of the first quadrant is
  28. displayed; then the predominant color of the first subquadrant of the
  29. first quadrant, and so on.  The user can watch the quadrants and
  30. subquadrants being drawn.  A breadth-first traversal, however, is much
  31. more interesting.  Since it displays first the predominant color of
  32. the entire image, followed by the predominant colors of the four major
  33. quadrants, followed by the predominant colors or the sixteen
  34. subquadrants, and so on, the effect is one of a gradually resolving
  35. image with finer and finer detail at each step.
  36.  
  37. -----
  38.  
  39. Included are two programs, ras2qt and xqtdisp.
  40.  
  41. Ras2qt is a filter which reads a raster on the standard input and
  42. produces a quadtree on the standard output, as in:
  43.  
  44.     ras2qt < input.cmuwm > output.qt
  45.  
  46. The input raster is in CMU WM format.  Jeff Poskanzer's latest
  47. Portable Bitmap package (pbmplus, available on X11r4) includes filters
  48. for converting images to cmuwm format.
  49.  
  50.     (some sequence of filters) | pbmtocmuwm | ras2qt > output.qt
  51.  
  52. Expect ras2qt to spend several silent and intent seconds calculating
  53. and writing the quadtree.
  54.  
  55. Xqtdisp is a quadtree viewer for X11.  It can be used as:
  56.  
  57.     xqtdisp quadtree-file
  58.  
  59. in which case it will display the image depth-first; or as:
  60.  
  61.     xqtdisp -b quadtree-file
  62.  
  63. in which case it will display the image breadth-first.  In both cases,
  64. the program requires several seconds to parse the quadtree before
  65. creating a window for displaying the image.  The user will be prompted
  66. to press ENTER to begin displaying, and, when the traversal is
  67. completed, will again be asked to press ENTER to exit the program.
  68.  
  69. Xqtdisp requires a lot of memory, especially in the breadth-first
  70. case.  For breadth-first traversals of large (> 70k) quadtrees, it may
  71. be necessary to do an ``unlimit'' first (csh users only), as in:
  72.  
  73.     (unlimit; xqtdisp -b large-quadtree)
  74.  
  75. -----
  76.  
  77. This software was written by Bob Glickstein (bobg@andrew.cmu.edu).  It
  78. is in the public domain and may be freely copied, modified and
  79. distributed.  I provide no warranty for, and assume no responsibility
  80. for this software.  I'd like to hear from anyone with ideas or
  81. comments.
  82.  
  83. -----
  84.  
  85. Coming soon:
  86.  
  87.     - pbmtoqt
  88.     - qttopbm
  89.     - man pages
  90.     - sample quadtrees
  91.     - Faster execution
  92.  
  93. -----
  94.  
  95. Note that the routine QT_Bitmap_Read (in quadtree.c) makes an
  96. assumption about the byte order of your machine when reading the width
  97. and height of the raster.  You may need to modify this section if your
  98. machine does not store 32-bit integers in most-significant-byte-first
  99. order.
  100.