Re: [MacPerl] comparing image files

[Brian McNett <webmaster@mycoinfo.com>]

>I don't understand how this would work.  Let's say that the file is a
>pixrect, with 32 bits per pixel.  If I fold the rectangle around the
>midpoint, the first 32 bits of my bit string would be made up of 16 bits
>each from the first and last pixels of the image.  Not too definitive...
>
>So, I assume that I am totally misunderstanding you; could you try to
>go through this again, in a bit more detail?

Ooops, minor thinko!  I probably should have said 32 (bytes) for the 
truncated key.  I presume that most images won't have both the upper 
right and lower left corners with too many pixels in common.

Bit-interleaving is usually combined with quad-trees or oct-trees to 
search LARGE datasets for similarity.  Writing a k-d tree is a little 
tougher,  but rather than 2 to the k branches per node as in quad and oct 
trees, there are always 2 nodes per branch, which scales better for even 
larger searches.

Remember that to generate the keys, we're treating the data as a string 
of bits.  It doesn't really matter that the file is a JPEG, or a PICT, or 
a GIF, or TEXT, or what have you.  The bit depth per pixel probably 
shouldn't be a concern, but I did committ a think-o in my last post.

I haven't actually found a reference that describes how to DO bit 
interleaving yet, but it's USED everywhere, particularly in 
communications, doing things like time-division multiplexing and that 
sort of thing.  One reference that comes CLOSE to describing technique, 
mentions the possible use of Gray code.  It's been almost 17 years since 
I've touched on the topic, but IIRC Gray code has it's main advantage 
when dealing with ambiguous data, and is used a lot in I/O.

Some example code would make this whole discussion go easier, but I'm 
still scrambling for references.  I'll go grab a few MORE references, and 
post a follow-on to this.  Reducing the search problem to sorting a list 
of keys would make for a much faster match, IMO.  Similarity mapping is 
used frequently in GIS work, so I may have to pull out a few GIS 
references as well.

--B



# Fungal Parataxonomy                   Mycology Information (Mycoinfo)
# Webmaster, Staff Writer      **The World's First Mycology E-Journal**   
# <mailto:webmaster@mycoinfo.com>            <http://www.mycoinfo.com/> 
#
# First they ignore you. Then they laugh at you. Then they fight you.
# Then you win.                                     --Mohandas Gandhi


===== Want to unsubscribe from this list?
===== Send mail with body "unsubscribe" to macperl-request@macperl.org