> There are two
> square (2-dimensional) arrays whose elements contain 0 or 1; each array
> represents a black and white image, where 0 is a black pixel and 1 is a
> white pixel. Given two such arrays, produce a number (on some scale, such
> as 0% to 100%, or 0.0 to 1.0) which estimates how close those images are
> to each other, in terms of "looking the same".
This will no doubt be a disappointing reply.
What you are describing is the general problem of image registration.
In your case, you are registering the binary transform of two images.
Unfortunately, there is no known method of determining translation,
rotation, scale and image similarity without brute force computation.
i.e. you compare your images by rotating, translating and scaling one
image and find its difference from the 2nd image. You iterate this
process until you can't find a better match (i.e. your optimization
process has converged.) Then, you may use your method of getting
the similarity from the image difference.
Feature extraction, as you suggested, is feasible but it requiresQuote:> may even perform some degree of feature analysis
> (as a person looking at two pictures would be able to say (for example)
> "well, picture A has the same kind of pattern with circles in it as B, but
> it is a little smaller and off to the left").
the kind of images you'll be looking at so that you can program
to look for the inherent features specifically. (Examples are using
transform and intensity tensors for these purposes.) However, finding
correspondence between similar features on different images will be a
Here's a possible NON-BRUTE FORCE scheme but it will ONLY WORK if you
the following assumption. Otherwise, you need a brute force scheme. (If
can figure out an alternative, please let me know, thanks!)
ASSUMPTION: The binarized object in your images (i.e. the collection of
voxels) is NOT cropped by the image edges.
The idea is to use a principal component analysis and align the 2 images
their principal axes. Then, you can take the difference of the
1. calculate the covariance matrix for each image:
C = [ Sum(Xi - X)(Xi - X) Sum(Xi - X)(Yi - Y) ]
[ Sum(Xi - X)(Yi - Y) Sum(Yi - Y)(Yi - Y) ]
where (Xi,Yi) = coordinates of each '1' voxel
(X, Y ) = average position of all '1' voxels
i.e. the centroid or center of mass
2. find the eigenvectors and eigenvalues of C. You can find routines to
this in Numerical Recipes for C.
3. the eigenvectors are the new X and Y axes that are "aligned" with
binaried object. (Just plot them and you'll see). The eigenvalues
the spread (i.e. square of the size) of the object along the new X
Y axes (i.e. eigenvalues = size^2 of the projection onto the new X
and Y axes).
4. Translate one image so that the centroid of its binarized object
the centroid of the second image.
5. Scale one image with respect to the other based on ratios of the
6. Then, rotate one image so that its eigenvector with the larger
aligned with the eigenvector with the larger eigenvalue of the 2nd
7. Compare this translated, scaled, and rotated version of one image
with the other
(original) image to determine the similarity.
8. NOW, because an eigenvector V is equivalent to an eigenvector -V
(i.e. +'ve = -'ve),
the new X and Y axes could be flipped to -X and -Y, so you have to
To check, rotate ADDITIONALLY the rotated image by 180 degrees and do
image comparison again. Pick the higher similarity value as the true
value. The smaller value is when the 2 images are rotated by 180
This is the fastest method for image registration, but it doesn't work
too well unless
the mass distribution of your objects are similar. Otherwise, you have
to resort to
brute force methods. Do a search on "image registration".
Hope this helps!
Biomedical Magnetic Resonance Laboratory
University of Illinois at Urbana-Champaign