Tuesday, March 25, 2003
      ( 8:24 AM ) Matt  

Storage Continued

Instead of storing every single wavelet moment in the database, we could store unique identifiers for every moment. Three integers would suffice; one to identify the image, and two for the x and y locations.

Efficient access is much more important than efficient storage. One way to store the data for efficient retrival is in a tree. The usual sorts of trees don't lend themselves well to this application. Usually trees are good when you know the exact value (key) you are looking for, or when there is some order which can be imposed on the keys. Neither is the case for wavelet moments.

Here's what I propose. The wavelet moments are all stored in the leaves of the tree. At each non-leaf node is stored the average of all wavelet moments below it, as well as the greatest (pythagrean) distance between the average and leaves below it.

To find the closest wavelet moment to a given moment, the tree is searched. Let d be the distance from our desired moment to the average, and r be the maximum distance for that node. Then we know that the closest moment under this node is no further than sqrt(r^2+d^2), and no closer than max(0, d-r). If you don't believe me, you can try it out by drawing some pictures.

There is no need to limit the branching factor of this tree to two. In fact, performance is much better with relatively high branching factors. In addition, the number of leaves from the last node could be fairly large too. If the tree is constructed well, then all of these nodes will have similar wavelet moments, and their unique IDs may be very compressable, especially if they are sorted.

# -

Comments: Post a Comment

Dreams I have...

Powered by Blogger
Feel free to e-mail me.

free hit counter