This site is being phased out.

Pixcavator image search

From Mathematics Is A Science
Jump to navigationJump to search

PxSearch stands for "Pixcavator image search" and is based on this software. It is an image-to-image search engine.

The distribution of sizes of objects can be used in image search. In other words we match images based on their busyness.

The analysis follows our algorithm for Grayscale Images.

Testing

The count of objects is not significantly affected by rotations. The output for the original 640×480 fingerprint in this image is 3121 dark and 1635 light objects. For the rotated version, it is 2969-1617. By considering only objects with area above 50 pixels, the results are improved to 265-125 and 259-124, respectively. Typically visual image search engines don't recognize rotated images, even though one can think of many examples of images that make just as much sense rotated:

See Images appropriate for analysis and Examples of image analysis.

Stretching the image does not affect the number of objects. The distribution of objects with respect to area is affected but in an entirely predictable way. Shrinking makes objects merge. If the goal, however, is to count and analyze large features, limited shrinking of the image does not affect the outcome.

The counting is also stable under “salt-and-pepper” noise or mild blurring. This is not surprising. After all, what the algorithm is designed to compute corresponds to human perception. The only case when there is a mismatch is when the size, or the contrast of the object, or its connection to another object are imperceptible to the human eye.

PxSearch.JPG

Features

This test program adds an image to the collection, along with a few of its versions (rotated, blurred, etc). The total of 8 images are analyzed for each image you add to the collection. This feature is needed to help you see when the algorithm works well and when it does not. The idea is that these versions of the image have to appear near the top when you search for similar images. The appropriate image have to be of good quality, with several larger objects, little pixelation, noise etc. Faces, simple landscapes, some medical images work. Fingerprints don't. But I think many would work if the thumbnails were larger.

PxSearch computes distributions of objects of each size. Those are called "signatures". The matching is also very simple. To match two images, their signatures are compared by means of the weighted sum of differences. The end result is that the images are matched based on a quantifiable similarity. In particular, copies of the image are found even if they are distorted etc. A good application could be in copyright filtering [1].

The main difference from some common approaches to image matching is that Pixcavator Search takes into account some global features (see a remark on local vs. global here).

cellAnalyst can also be thought of as a visual image search engine. The difference is that its search is based on concrete data collected from the image: cells quantity, sizes, shapes, and locations, rather than the distributions.

Some details

We focus on the goal of finding modified versions of the original. The executable is accompanied by a small collection of images (download here, 7.2 MB). The system consists of the following modules:

  • the collection of images that can be extended;
  • the database containing “signatures” of images, images’ origins, and other data;
  • the image analysis unit (produces the signatures);
  • the matching unit (matches the signatures);
  • user interface (uploads an image, searches for similar images in the collection, displays the matches as a list);

For every image to be added, first the image is converted to grayscale and then shrunk so that the larger dimension is 150. Then several of its secondary versions are created, analyzed, and added to the collection and their data is added to the database, total of 8:

  1. original
  2. rotation, 5 degrees
  3. rotation, 45 degrees
  4. Gaussian blur
  5. salt and pepper noise
  6. stretch, 5%
  7. shrink, 5%
  8. crop from all sides, 5%

The entry in the database for each image contains the information about its origin:

  • date and time,
  • the filename of the original image,
  • the way the image was produced from the original (shrinking, rotation, etc),
  • the signature of the image.

A signature is a sequence of 126 integers which is the output of image analysis: it is essentially the distribution of sizes of objects found in the image.

Suppose the signature of the two images are {An} and {Bn}. Move along these sequences and compute the absolute value of the differences of n-th entries. The result is a distance formula as the “weighted 1-norm metric”:

D = Σ Cn |An - Bn|.

If the distance is less then some threshold the two images are matched.

PxSearch-screenshot.jpg

A search is deemed successful if most of the versions of the query image are at the top of the list. This is the case for images that are “good” in the sense that they have clear pattern (based on shapes not color). However, this standard is hard to quantify as it is dependent on the collection. Since the collection I used for testing was small (4500 images), I had to find a way to evaluate the quality of searches that is independent of the size of the collection, as much as possible. So, the quality score for a given image was

(average distance to its 7 versions) / (average distance to all images) * 100.

For another way to evaluate the quality of the search, see Precision and recall.

Case study

This study was conducted in 2009 for a company that is “working in the online social media sector and are looking for an accurate image analysis solution that allows us to compare a reference photo to a large dataset of photos to determine if the reference photo is duplicated in the larger dataset.”

The full title of the report is "Image-to-image search with Pixcavator (PxSearch): a case study". It was written by Dr. Ash Pahwa and myself and is presented here with minor modifications.

The first version of PxSearch was created in 2007. Using that version, initially the search results with the collection had 4-5 good hits (i.e., the transformed version of the original) at the top and then some bad hits. Some of the good matches weren't even visible. After the upgrades, the results became 10 out of 10 or close. This improvement made this, more extensive, study possible. The results are OK, even though the collections are still very small. The company eventually went with another vendor, it’s still an interesting document.

Since 2009, there has been no work going on but, hopefully, this project will be one of the summer projects for the REU site.

Incidentally, I don’t like the term “reverse image search” popularized by TinEye. If the image search that we are used to at Google etc is “direct image search” (text-to-image) then the “reverse image search” is supposed to search for text based on images. Not only this isn’t what we are talking about, but also the problem hasn’t been even remotely solved (see this pathetic list: Visual image search engines). This is the reason I prefer “image-to-image search” to describe this application.


A related example of image analysis is here: Inspecting semiconductor wafers. See also Other software projects.