Identifying Duplicate Images

Identifying similar images and determining which are identical. 

So in this post I want to talk about how you can write a program that will be able to compare images against each other and determine if they're identical or very similar. Basicly the same thing tineye and google's reverse image search does. So if you've ever wondered how they work then this post might clear things up a bit. In a follow up post I also want to describe how we can apply a similar technique to identify duplicate videos.

The Trick?
There is no, one solution to the problem and every solution has its advantages and disadvantages,  the approach im going to be using is based off of the histogram of the images. A very simple yet very effective method, the draw back of it being false positives and it can only match images that are visually very similar. But it can identify images with varing qualities of:

• Resolution
• Rotation
• Filesize
• format
• compression
• quality

What we are going to do is, extract the distribution of colours that make up the image and plot the frequecy of those colours. Also known as a histogram, in short a histogram will show us how much of each colour value(0-255) in each colour range(RGB) is used in the image.

The histogram represents the frequency of each colour value.

Two images that are visually identical will have a very similar histogram(98%) depending resolution and other factors. However images can have they same histogram yet not be visually similar, but at least we are certain to find duplicates, and these false positive detection is a problem we can reduce.

As the figures above show that two identical looking images with different properties in both size and resolution share a near identical histogram.

The Algorithm

The algorithm in broken up into 3 main sections. 

1. Finding the images
2. Analysis
1. Load Images
2. Extract Colour Map
3. Generate Histogram
4. Normalise Histogram
3. Comparison

Step 1 - Finding the images

We can hardcode the locations of the images into the program, this is useful when just testing the analysis of the algorithm, but for practical purposes we want the program to be able find those images for us. To do this we will use another algorithm to recursively load each directory and subdirectory and find all the images, and add those to a list.

Select a Directory

public void LoadDirectory()
{  
 JFileChooser fileChooser = new JFileChooser();
 int result = fileChooser.showOpenDialog(null);
 
 if(result==JFileChooser.APPROVE_OPTION)
 {
  URL fileURL = null;
  try
  {
   fileURL = fileChooser.getSelectedFile().toURL();
   
   String _folderPath = fileURL.toString().substring(6);
   String[] folderPath = _folderPath.split("/");
   
   for(int i=0; i<folderPath.length-1; i++)
   {
    directory = directory+folderPath[i]+"/";
   } 
   
  }
  catch(Exception e)
  {}
 } 
 File folder = new File(directory);
 LoadSubDirectories(folder);
}

So the above snippet will allow us to pick a folder to start our search, and the last method called LoadSubDirectories(folder) will then load all the subdirectories in that folder 

Select Directory view

Load Subdirectories

public static int spc_count=-1;
private void LoadSubDirectories(File folder)
{    
    spc_count++;
  
    String spcs = "";
     
     for (int i = 0; i &lt spc_count; i++)
       spcs += " ";
     
     if(folder.isFile())
     {  
   String[] temp3 = folder.getName().split("\\.");
   
   if(
     temp3[1].equalsIgnoreCase("jpg")||
     temp3[1].equalsIgnoreCase("jpeg")
    )
   {                 
//Adds file location to ImageObject(my own class) you can just add
//absoluteFile parameter to an ArrayList
            ImageObject iObject = new ImageObject(folder.getAbsoluteFile());
   }   
     }
     else if (folder.isDirectory()) 
     {
       File[] listOfFiles = folder.listFiles();
       
       if(listOfFiles!=null) 
       {
  for (int i = 0; i &lt listOfFiles.length; i++)
   LoadSubDirectories(listOfFiles[i]);
       } 
     }
     
     spc_count--;

     if(spc_count==-1)
     {
  //Add logic of what to do when done searching 
     }   
}

This code will then load all the subdirectories and find all images ending with a jpg, jpeg and add those to a list, or in my case an ImageObject(own class), which I also use to store their features(histograms).

Step 2 - Analysis

In this step we are going to use the absolute addresses we found in step one to load those images and perform analysis on them. To perform analysis on the images we are going to have to do a few things
1. Load the image into the program
2. Extract the colour map
3. Generate Histogram
4. Normalise Histogram

2.1 - Loading the image

for(ImageObject listIfImages : iObject)

BufferedImage image = null;
try
{
//now this does use my class(ImageObject) to store and 
//load the images But all you have to do is replace
//iObject.toString() with the absolute path.toString()
//of the image 

image = ImageIO.read(new File(iObject.toString()));  

        Imager.process(image);//my class that processes the image

//Just storing the histograms into the image object, 
//so that I can save and load it to disk
//easier so that I don't have to process an 
//image more than once.
iObject.redHisto = Imager.getRedHisto();
iObject.greenHisto = Imager.getGreenHisto();
iObject.blueHisto = Imager.getBlueHisto();
}
catch(Exception e)
{}

So in my ImageProcessor Class I will have an a method that takes a buffered image. 2 - Extract the Colour map

2.2 - Extract Colour Map

public final void process(BufferedImage _image)
{   
 width = _image.getWidth(this);
 height = _image.getHeight(this);
 
 final int[] rawPixels = new int[width * height]; 
 PixelGrabber grabber = new PixelGrabber
 (
  _image,
  0,
  0,
  width,
  height,
  rawPixels,
  0,
  width
 );
  
 try
 {  
  grabber.grabPixels();
 }
 catch(Exception e)
 {}
 
 final int[][] pixels = new int[width][height];
 
 alpha = new int[width][height];  
 red = new int[width][height];
 green = new int[width][height];
 blue = new int[width][height];
   
int offset = 0;

//This double for loop is where the colour map gets made
//This colour map will be used to generate the histogram
//Note that is section can take the longest and might cause
//Java virtual machine to crash due too large images if this 
//happens do the following select the project:
//properties->Run/Debug Settings-> {class of main method}  
//(x)=Arguments->VM arguments->-Xmx1024m
for (int i = 0, n=width; i < n; i++) 
{
 for (int j = 0, m=height; j < m; j++) 
 { 
     pixels[i][j] = rawPixels[offset];
     // extract the 4 fields
     alpha[i][j] = (pixels[i][j] >> 24) & 0xff;
     red[i][j]   = (pixels[i][j] >> 16) & 0xff;
     green[i][j] = (pixels[i][j]  >>  8) & 0xff;
     blue[i][j]  = pixels[i][j]  & 0xff;
     
     offset++;
 }
}

redHisto = this.createHistogram(red);
greenHisto = this.createHistogram(green);
blueHisto = this.createHistogram(blue);
alphaHisto = this.createHistogram(alpha);

return feature;
}

In case you missed the comment in the middle if your JVM bombs out due to a memory error do the following: Right click on the project and select properties. Click Run/Debug Settings and select the class where your main method is located and click edit, select the (x)=Arguments tab and enter in the VM arguments text area: -Xmx1024

Solving JVM memory problem

2.3 - Generate Histogram

To actually generate a histogram from the colourmap is ridiculously simple

/**@_colorMap created an array of type int that represent 

 *the histogram of that colour
 * @histogram the array returned
**/
private final int[] createHistogram(int[][] _colorMap)
{
 int[] histogram = new int[256];
 
 for(int i=0, n=width; i<n; i++)
 {
  for(int j=0, m=height; j<m; j++)
  {
   histogram[_colorMap[i][j]]++;
  }
 }  
 return histogram;
}

So what this code snippet above does is create a histogram from the colormap that is parsed through. A new array of type int and size of 256(0-255) is created, each array index will then be the corresponding colour value. Such that all instances of red-145 will be stored in histogram[145]. So the trick is that we access the the Array with the value of the _colormap[i][j] and just increment that index.

We then simple return that array, which now represents that colour's histogram.

2.4 - Normalise Histogram

Since we want to compare images of all sizes you have to realise that larger versions of images will have larger value in the histogram array, but relatively speaking those histograms will be near identical. This we need normalise the histogram so that ALL histograms will have the same upper limit. Now you can scale the histogram right after you've generated it and just before you returned it, or you can do it during comparison.

I did mine during comparison so that I could save a raw copy of the histogram since during normalisation certain data is lost. Of course this is slightly slower since I would have to regenerate the histogram each time.

I'm no mathematician so there probably exists a more elegant solution than mine. But in short we going to find the largest value in the histogram and see how close it is to our limit, then divide or multiple all the values by the difference depending on if its larger or smaller;

private int[] normaliseHistogram(int[] _histo)
{
 double scaler=0.0;
 int largestValue=0;
 
 //Normalise all values relative to 255
 int limit = 255;
 
 //Finding Largest Value
 for(int i=0; i<_histo.length; i++)
 {
  if(_histo[i] > largestValue)
   largestValue = _histo.length;
 }
 
 //Calculate the scaler value
 scaler = largestValue/limit;
 
 for(int i=0; i< _histo.length; i++)
 {
  //If scaler is larger than 1 we devide all value by it
  if(scaler > 1)
  {
   _histo[i] =  (int) (_histo[i]/scaler);
  }
  else //if histo smaller than 1 we multiple all the values
  {
   _histo[i] = (int)(_histo[i]*scaler);
  }
 }
 
 return _histo;
}

Step 3 - Comparison

And only one thing left to do and that compare the histograms with each other. So to compare to histograms with each other.

public double compareHistogram(ImageObject _image1, ImageObject _image2, int _color)
{
 int tempHistImage1 = _image1.getHisto(_color);
 int tempHistImage2 = _image2.getHisto(_color);
 
 for(int i=0; i<256; i++)
 {
  double diff = 0;

  TotalIntervals++;
  
  if(temp1>=temp2)
  {
   diff += temp2/temp1*100;    
  }
  else 
  {
   diff += temp1/temp2*100; 
  }
 }
 return diff;
}

Note that this method takes in two ImageObjects again this is my own class I use to represent the data of each image such as there histograms, all I do with these objects is extract there histograms so I can use them. In this code snippet I compare the red histograms with each other, this code will have to be done for both green and blue.
Now all that’s left is to establish the threshold and see if it passes it, if it does then the images are a match.

histogramThreshold = 80.0;

if(compareHistogram(image1, image2, 1)>histogramThreshold)
 return true;

My final program

The image above is of my program that uses the same algorithm as above with some modification, including faster matching and reduced false positives. As well has the ability to find duplicate videos.

Java simple threading library

Simple threading in Java using JavaCP library

In this post I'm going to talk about a simple way to achieve multi threading and parallel computation using a simple library I've assembled based off of the work of Weimin Xiao and the rest at this stack overflow post.

I take no credit in any of the code written in the library it self(the code below is mine) I merely just assembled a simple library and have used it to successfully achieve embarrassingly thread execution. If you're not familiar with embarrassing threading, it is threading tasks that in no way affect the outcome of each other. E.g having to process a large library of files, this task can be easily threaded by having each task processed in a separate thread. Which is primarily what I've used it for in processing Photos and videos to find perceptually similar content. I'll discuss video and photo matching algorithm in a later post.

1. Where to get the library? here,
2. How to use the library?

1. Place the JavaCP.jar anywhere you want we you can find it.
2. In your IDE(eclipse etc..) add the JavaCP.jar as a library

• In ecplise this is done by right clicking on the project root folder in the package explorer window and selecting properties
• In the properties window select Java Build Path
• Select the Libraries tab
• Click on Add External JARs, navigate to where you placed the JavaCP.jar and select ok.

The library is now ready to be used.
The library is able to thread 2 different things. ForEach Loops and concurrent method execution.

In your program import the library

//Import the library
import JavaCP.*;

Example code to run Tasks

//Using it to execute Multiple methods concurrently
//The number of threads created depends on the number of cores available
Parallel.Tasks(new Task []
{
 
 //task-1
 new Task() {public void run()
 {
  loops.runLoop(1000000000);
 }},
   
 //task-2
 new Task() {public void run()
 {
  loops.runLoop(1000000000);
 }},
 
 new Task() {public void run()
 {
  loops.runLoop(1000000000);
 }},
 
 new Task() {public void run()
 {
  loops.runLoop(1000000000);
 }}
});

In this example the method loops.runLoop(int _value) will be executed multiple times along side other instance of the loops.runLoop(int _value).

A more practical use would be something like this, where each method as to do something time consuming since creating threads themselves are taxing.

Parallel.Tasks(new Task []
{
 //task-1
 new Task() {public void run()
 {
  feature[0] = Variance(red,0);   
 }},
   
 //task-2
 new Task() {public void run()
 {
  feature[1] = Kurtosis(red,0);
 }},   
 //task-3
 new Task() {public void run()
 {
  feature[2] = Variance(green,1);
 }}, 

 //task-4
 new Task() {public void run()
 {
  feature[3] = Kurtosis(green,1);
 }}, 
 //task-5 
 new Task() {public void run()
 {
  feature[4] = Variance(blue,2);
 }},
 //task-6
 new Task() {public void run()
 {
  feature[5] = Kurtosis(blue,2);
 }} 
});

The local array feature[] stores the result of the method execution. So what about ForEach loops? Well they will look a bit different following the next type of structure

Parallel.ForEach(arrayListName, new LoopBody()
{
 public void run(String _objectNameofItemInArray) 
 {
          //code of what must happen to the object
  objectNameofItemInArray.invokeMethod();
 }
}

such that it could look like this example

ArrayList listOfFiles = new ArrayList()

Parallel.ForEach(listOfFiles, new LoopBody()
{

 public void run(ImageObject p) 
 {
  p.process();
 }
}

//In ImageObject class there is a method called process()

public class ImageObject
{
  public ImageObject(){} //Default constructor

  public void process()
  { 
    //ToDo add method logic
  }
}

In this example listOfFiles is an ArrayList of type ImageObject which has a method called process. Threads will be created and multiple ImageObject will then be processed concurrently. There you go a simple way to achieve a basic level of multi threading. Both code snippets are from a project I created to identify duplicate videos and photos.

X264 - Motion Estimation Method- Comparison

Last time we looked at the effects of the various subpixel estimation complexity, today we will be looking at how the motion estimation method(MeM) impacts the filesize(all measured in KB), quality and performance(average FPS) according to CRF18 of x264.

There are a total of 5 methods these are in order of complexity:

• Diamond(dia) - The most simplest method, checking motion vectors at one pixel up, left, down and right and picking the best candidate, this process repeats until it can't find a better motion vector
• Hexagon(Hex) - Work similarly like Diamond but consists of a range-2 and 6 surrounding points, more efficient than diamond with little performance impact.
• Uneven multi-hexagon(Uhm) - While slower than Hex, it is able to avoid missing harder-to-find motion vectors. The Me-Range parameter controls its search radius.
• Exhaustive(Esa) - An optimised intelligent search of the complete motion vector space within Me-Range. Mathematically equivalent to brute force but faster, but still slower than Uhm.
• Transformed exhaustive(Tesa) - is an algorithm which attempts to approximate the effect of running a Hadamard transform comparison at each motion vector; like exhaustive.

So now that we are more familiar with MeM lets see how it performs.


Futurama SD

The top graph shows the FileSize(Graph area) in KB as well as the performance(line) of each of the different methods. As you can see the relationship between compression and performance takes a turn for the worst with Esa and Tesa.

The bottom graph represents the difference in percentage for speed and compression compared to the default(medium) setting. Here we can see that with Esa for 29.5% performance reduction we get a measly 2.56% extra compression and Tesa does even worse. Uhm compresses better with a slight performance hit of 6.71% slower. Of course will have to see if this translates into any visual artefacts

Still Frame

Diamond

Hexagon

Uhm

Esa

Tesa

Even though I can see a VERY slight difference between the different methods, I cannot say that one looks better than the other. 


Smaller Motion Detail

Diamond

Hexagon

Uhm

Esa

Tesa

Again I can notice a difference between the methods but cannot say which is actually higher quality than the rest.

Reel Steel SD
 

So moving onto live action video, we can see that the same trend repeats it self with esa and tesa performing very poorly when compared to dia, hex and uhm.


Still Frame

Diamond

Hexagon

Uhm

Esa

Tesa

As with Futurama its difficult to tell which is better quality.


Smaller Motion Detail

Diamond

Hexagon

Uhm

Esa

Tesa

  .

 

 

And yet again the frame quality is too consistent to say which is better. Maybe we'll see a bigger deference with HD videos

 

Reel Steel HD 

So looking at HD video we see that esa and tesa performs worse than Uhm and is significantly slower. Hexagon seems like a good default method.


Still Frame 

Diamond

Hexagon

Uhm

Esa

Tesa

 

 

 

 

 

 

 

 

 

Yet again with MeM and with HD I can hardly see any difference let alone which is higher quality   

Smaller Motion Detail

Diamond

Hexagon

Uhm

Esa

Tesa

 

So yet a again its almost impossible to tell which is which and which is better than the other.

Conclusion

Well as you can see visually there isn`t much of a difference, in terms of compression Uhm did consistently better than hexagon or diamond, and esa, tesa also performed better except at HD videos. Regarding performance Esa and Tesa took a massive performance hit, with Uhm only being slightly slower.

Recommended
Hexagon - Performed consistently close to the others.
Uhm - A slight compression gain at a margin performance loss.


 Navigation

1. Introduction
2. Presets
3. Subme  
4. Motion estimation method

X264 - Subme - Comparison

x264 Settings Comparison Part : 2 - Sub Pixel Motion Estimation

Subme define the subpixel estimation complexity. Higher values are better the question is by how much and what is the trade off.

Levels 1-5 control the subpixel refinement strength.
Level 6 enables RDO(Rate–distortion optimization) for mode decision, with level 8 enabling RDO for motion vectors and intra prediction modes. RDO levels are significantly slower than the rest.

Values available:
0 - Full pixel Only.
1 - Quater pixel(QPel) SAD 1 iteration
2 - Quater pixel SAD 2 iteration
3 - Half pixel(Hpel) on MB then QPel
4 - QPel Always
5 - Multi QPel + bi - directional motion estimation
6 - Rate Distortion(RD) on I/P
7 - RD on all frames(Default, Medium)
8 - RDO on I/P frames
9 - RDO on all frames
10 - QP-RD(Requires trellis=2, aq-mode(Adaptive Quantization Mode )>0 )*
11 - Full RD(No early termination)*

*Update found out that Subme10,11 requires other settings, as noted in post previously, will update post with new data.

Futurama SD

 Ok so lets take a look at the performance of sub pixel motion estimation

As you can see from the above graphs subme:0-3 shows significant performance improvement, with 0 and 1 have a noticeable adverse affect on compression, whilst 2-3 having better compression. However and this is important subme lower than 4 does have visible artefacts and I would not recommend any setting lower than 5.

We can also see no difference in subme 9,10,11 these values might require other additional settings for them to take effect. Safe settings are 5-8.

So lets take a look at the screenshots where you can decide for yourself.
Still Frame   

Subme=0

Subme=1

Subme=2

Subme=3

Subme=4

Subme=5

Subme=6

Subme=7(Medium)

 

Subme=8

Subme=9

Most of the still frames have similar quality, looking closely higher subme retains more detail.

Smaller Motion Detail

Subme=7(Medium)

Subme=0

Subme=1

Subme=2

Subme=3

Subme=4

Subme=5

Subme=6

Subme=8

Subme=9

 

 

 

It is difficult to see the difference between subme settings and animation type videos, however the higher settings do introduce less artfefacts and the image quality is consistently cleaner. 

Real Steel SD

 

As you can see the trend is similar to that of the previous one, with Subme 0-3 consitently faster at a loss of compression and 9,10,11 being identical.

 

Still Frame

subme=0

subme=1

subme=2

subme=3

subme=4

subme=5

subme=6

subme=8

subme=9

 

 

 

subme=7(Medium)

 

 

 

 

 

 

 

 

Looking at non animation type videos we can clearly see a visible difference between the subme settings with subme:0,1,2 retaining significantly less finer detail than the higher settings. From subme=7 is becomes a lot harder to notice the loss of fine detail.