13 - Duplicate Image Detection

[feltnerm]

Attempt to detect duplicate image uploads client-side before upload.

Concerns are performance when iterating over the pixels of large (hi-res) image files, but that may be able to be mitigated by shrinking the image.

[rnicholus]

Let's consider creating a new repo that tackles this problem. We can also blog about using the new library with Fine Uploader on the Fine Uploader blog.

[rnicholus]

We need to define the API for this new module/library. Will schedule a meeting to discuss internally.

[rnicholus]

I think it is prudent to develop this as a new repo outside of Fine Uploader.

Here are my current thoughts on this library (subject to editing):

Use Cases

• Weed out duplicate images before sending (uploading) them, saving bandwidth
• Find similar images for the purposes of grouping and organization
• Identify an object in a source image, such as a face or a car, and find all images with that face or car

Features

• Entirely client-side
• Not dependent on Java, Flash, Silverlight, etc
• Efficiently determine which images are identical among a large set
• Efficiently determine which images are "similar" among a large set
• Allow duplication & similarity detection to be limited to a subsection of the image(s)

API

• Allow an array of <img>, <canvas>, or image Blobs to be passed in for analyzation. Promise fulfilled with an array, each element containing an array of detected identical/similar images.
• Allow images to be accumulated over time and then analyzation of all accumulated images to be triggered via a separate method. Return value the same as above.
• Acceptable hue variability can be defined. This is one vector that makes up the definition of "similar". For example, if an RGB variability of 10 is provided, then a pixel with respective RGB values of 15, 17, and 19 is effectively "similar" to pixel in the same location of another image with respective RGB values of 10, 18, and 23. Note that matching takes into account the entire pixel, so if one of the subpixels vary by more than the allowed variability, the two pixels are not similar.
• A minimum pixel match value. This is a second vector that defines "similar". For example, consider two 3-pixel images where 2 of the 3 pixels are identical or otherwise similar. A minimum match value of 66% or lower would make these two images "similar". A minimum match value of 67% or higher means they are not similar enough.
• If detection should be limited to subsections of an image, allow x, y, w, and h values to be passed that describe a sub-rectangle of the images to focus on. Similar or duplicate subsections can be reported in other images at that exact location, or at any location as long as the pattern represented by the source subsection is has a reasonably similar or identical match in one of the other images in the set.

Implementation/Algorithms

• Shrink images down to a smaller size, of say 100x100 (maintaining aspect ratio). This will make analyzation of the images more efficient, especially very large images.
• Build a tree of all accumulated image data. Each tree node relates to a subpixel value reported in the ImageData typed array. Each node will contain references to each image that is consistent with the image data at that point. Also, each of these references will also contain a backreference to the preview subpixel node for the current pixel (if the current subpixel is not the first subpixel in the current pixel). Duplicate and similar image detection may be quite efficient with this tree: O(n) seems possible where n is the number of pixels in the normalized image.
• Hue variability should probably be specified during construction. This will affect the subpixel "buckets" (tree nodes). For example, if a hue variability of 10 is specified, subpixels of the same color for each pixel will be grouped into 26 nodes: values 0-9, 10-19, 20-29, etc.

Questions

• Will normalizing the images (to a constant height/width maintaining aspect ratio) before analyzation negatively impact duplicate detection?
• How can we build the image data tree (described above) such that it is possible to only examine a sub-rectangle of the accumulated images without building a new tree. It would be nice to have one tree instead of building a specific tree given the dimensions and location of the desired sub-rectangle. This may be a bit challenging if we are looking for subsection patterns in a specific location. If we are looking for subsection pattern matches anywhere in any image contained in the set, this perhaps becomes much more complicated to efficiently execute.
• Will we need to compare the dimensions of the shrunken images first before looking at the image data tree? I suspect we may have to.
• How can we effectively build the image data tree to account for a specified minimum pixel match value? Hue variation seems straightforward, but I'm not yet sure how to properly organize accumulated ImageData to make similarity detection efficient.

[feltnerm]

Entirely client-side

This should be an end-goal, definitely. Might be an easy win to make a CommonJS exported function that deals with raw binary data (Uint8Array, Buffer, etc.), and then build client-side functionality (canvas->buffer, image tag->buffer, etc.) on top of that.

API

module.exports = function(threshold, image_1, image_2[, ..., image_n]) {

}

Implementation / Algorithms

Image Comparison

Perceptual Hash

A hashing function which will return hashes that are "close" to each other if the features of the hashed object are similar.

Histogram Matching

Not entirely sure what is going on here. Somehow the image data is transformed into a histogram (similar to Fourier transform maybe?). Then you can subtract histograms from each other to detect similarity/difference.

Haar Wavelet

Again, not really sure what this is, but I'm seeing it pop-up a lot on the literature surrounding dup. image detection.

Storing Results

k-d tree

Spinning off of the tree idea proposed by Ray, I found about a k-d tree (a k-dimensional tree). Since each pixel is composed of 4 "vectors" (R,G,B, and A) we would say each vector is a dimension in the k-d tree. Seems to have good efficiency.

Bloom Filter

A bloom filter could be used to store a set of the unique images from the user, and then we can test whether newly added images are within that set (within a certain probability of a false positive).

Pros: efficient Cons: can only detect if something is NOT in the set, or there in the set within a certain probability

/cc'ing @aswenson and @uriahcarpenter to see if they have any ideas :)

[feltnerm]

/cc'ing @nmall as well

[feltnerm]

i put together a simple jsbin that compares two images, pixel by pixel, in the browser. it's fairly speedy, surprisingly. obviously would slow down as more files are added. The comparison (right now) is only between two images, not against the set of all inputted images.

Feel free to edit and/or provide suggestions.

Since the image data is now in a more malleable form, I think next I'd like to create a way to experiment with different comparison algorithms and do some profiling of the different algos.

starting point?

[rnicholus]

It's possible that I'm missing something (I didn't have time to look over the code closely) but it seems like all of this can be done in a very small amount of code, and FileReader shouldn't be necessary.

To compare two images, pixel by pixel, all you need to do is:

1. Get an object URL for each Blob
2. Convert those to 2 <img> elements
3. Draw the <img> elements onto 2 <canvas> elements (you can resize them as part of this process).
4. Iterate over the ImageData for each image (from the canvas' associated RenderingContext) and stop when you reach the last subpixel or find a difference.

[feltnerm]

Ah yes, you're correct. I knew something was up when I was using FileReader. URL.createObjectUrl is what was needed to Blob -> <img>.

Updated, and removed unused code: http://jsbin.com/nosamu/23

[rnicholus]

Phew. Seems like a lot of work. Maybe in another repo, in another life.