Organizing and visually duplicating images

Question

This algorithm is supposed to organize and visually duplicate images. I compare 2 images at a time; 1 is the first index image of the directory and another for comparing every other image in the directory. If there are duplicates of the first index image, all of the duplicates will be moved to a new folder that is named after the original folder.

It is working fine but the performance time is approximately 5 minutes and 29 seconds. I am dealing with 1090 images.

For example, if 2.png had 5 visually duplicated images, they would be moved to the path file called:

C:\Users\user\Downloads\CaptchaCollection\Large\Duplicates\2

What this code is supposed to do:

1. Copy all the images from another directory to:

   C:\Users\user\Downloads\CaptchaCollection\Large\

   This is because I want to back up my raw images just in case I lose them

2. Collects the amount of images there are in the directory.

3. Selects the first index and then compares it with all other images in the directory.

4. If they are equal they are moved to a new folder.

5. When this is done the original is moved to the Sorted folder.

6. Then a new first index will be selected and the loop goes on until everything is finished. At the end of the inner loop, it will recalculate the amount files in the directory.

7. Move the last file into the Sorted folder.

8. Check for any empty folders.

9. Recursively deletes them.

10. (Not involved in sorting) Pretty much logs everything into a text file.

private bool compare(Bitmap bmp1, Bitmap bmp2)
{
    bool equals = true; // sets it to true first

    Rectangle rect = new Rectangle(0, 0, bmp1.Width, bmp1.Height);
    BitmapData bmpData1 = bmp1.LockBits(rect, ImageLockMode.ReadOnly, bmp1.PixelFormat);
    BitmapData bmpData2 = bmp2.LockBits(rect, ImageLockMode.ReadOnly, bmp2.PixelFormat);

    unsafe
    {
        byte* ptr1 = (byte*)bmpData1.Scan0.ToPointer();
        byte* ptr2 = (byte*)bmpData2.Scan0.ToPointer();
        int width = rect.Width * 3; // for 24bpp pixel data

        for (int y = 0; equals && y < rect.Height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                if (*ptr1 != *ptr2)
                {
                    equals = false;
                    break;
                }
                ptr1++;
                ptr2++;
            }
            ptr1 += bmpData1.Stride - width;
            ptr2 += bmpData2.Stride - width;
        }
    }

    // unlocks the bits
    bmp1.UnlockBits(bmpData1);
    bmp2.UnlockBits(bmpData2);

    // disposes the image
    bmp1.Dispose();
    bmp2.Dispose();

    return equals; // returns if they're same or not
}

private void sort(object sender, EventArgs e)
{
    // testing time
    Stopwatch w = new Stopwatch();
    w.Start();

    // file paths
    string sourceDir = @"C:\Users\user\Documents\Original";

    string copiedOriginal = @"C:\Users\user\Downloads\CaptchaCollection\Large\";
    string duplicatePath = copiedOriginal + "Duplicates\\";
    string movedOriginal = copiedOriginal + "Sorted\\";

    // creates a log
    FileStream outputFileStream = new FileStream(copiedOriginal + "log.txt", FileMode.Create, FileAccess.Write);
    StreamWriter writer = new StreamWriter(outputFileStream);

    // Copy picture files. 
    foreach (string f in Directory.GetFiles(sourceDir, "*.png"))
    {
        // Remove path from the file name. 
        string fName = f.Substring(sourceDir.Length + 1);

        // Use the Path.Combine method to safely append the file name to the path. 
        // Will overwrite if the destination file already exists.
        File.Copy(Path.Combine(sourceDir, fName), Path.Combine(copiedOriginal, fName), true);
    }

    // creates the folders for the sorting
    Directory.CreateDirectory(duplicatePath);
    Directory.CreateDirectory(movedOriginal);

    // makes sure only n.png is counted
    var files = Directory.GetFiles(copiedOriginal)
                            .Select(nameWithExtension => Path.GetFileNameWithoutExtension(nameWithExtension))
                            .Where(name => { int number; return int.TryParse(name, out number); })
                            .Select(name => int.Parse(name))
                            .OrderBy(number => number).ToArray();

    // will move if there is more than 1 file.
    while (files.Length > 1)
    {
        // creates an individual folder based on the original image's name assosiated with the duplicated images
        string duplicateOfFolder = Directory.CreateDirectory(duplicatePath + files[0].ToString()).FullName;

        // sorting inner loop
        for (int j = 1; j < files.Length; j++)
        {
            // creates 2 images objects for it to run
            Bitmap im1 = new Bitmap(copiedOriginal + files[0].ToString() + ".png");
            Bitmap im2 = new Bitmap(copiedOriginal + files[j].ToString() + ".png");

            // if they are the same
            if (compare(im1, im2))
            {
                // moves the duplicates to the file that was linked to the them
                File.Move(copiedOriginal + files[j].ToString() + ".png", duplicateOfFolder + "\\" + files[j].ToString() + ".png");

                // logs the moves
                writer.WriteLine(files[j].ToString() + ".png" + " is a duplicate of " + files[0].ToString() + ".png");
            }
        }

        // logs that it has finished all duplicates associated 
        writer.WriteLine(files[0].ToString() + ".png " + "has had its duplicates removed.");

        // moves the non-duplicated file to the sorted folder
        File.Move(copiedOriginal + files[0].ToString() + ".png", movedOriginal + files[0].ToString() + ".png");

        // recalculates the length of the directory
        files = Directory.GetFiles(copiedOriginal)
                            .Select(nameWithExtension => Path.GetFileNameWithoutExtension(nameWithExtension))
                            .Where(name => { int number; return int.TryParse(name, out number); })
                            .Select(name => int.Parse(name))
                            .OrderBy(number => number).ToArray();
    }

    // moves the non-duplicated file to the sorted folder
    File.Move(copiedOriginal + files[0].ToString() + ".png", movedOriginal + files[0].ToString() + ".png");

    // deletes and logs any empty folders that were created in this process
    processDirectory(duplicatePath);
    writer.WriteLine(deletedDirectories);

    // finished the timing
    w.Stop();
    writer.WriteLine(w.Elapsed);

    // closes the log.txt file
    writer.Close();
    outputFileStream.Close();
}

private static void processDirectory(string startLocation)
{
    foreach (var directory in Directory.GetDirectories(startLocation))
    {
        // recursively calls itself
        processDirectory(directory);

        // if it is empty it will delete
        if (Directory.GetFiles(directory).Length == 0 && Directory.GetDirectories(directory).Length == 0) 
        {
            Directory.Delete(directory, false); // deletes
            deletedDirectories += Path.GetFileName(directory) + " , "; // logs the deleted directories
        }
    }
}

Results after every test (2nd test and later):

• 00:05:33.5252512
• 00:05:27.4010562

Answer 1

The algorithm as described is O(n^2) worst case. Assuming that there are n images and no two images are equal then the first one gets compared against n-1, the second one against n-2, ... etc. so you have 1/2 * n * (n + 1) comparisons.

A way around this is by calculating a checksum with low enough collision probability on each image - SHA256 comes to mind but there are a whole heap of others in the .NET framework which will fit the bill.

Then the algorithm becomes (pseudo LINQ):

var equivalentImages = allImages.Select(i => Tuple.Create(HashImage(i), FullPath(i)))
                                .GroupBy(t => t.Item1);

This way you only need to process the data of each image once and then group them by the hash.

A few remarks to your code:

1. Instead of disposing bmp1 and bmp2 manually you should use a using block. This means they will get disposed even if any of the code in between throws an exception.

2. Similar Streams are IDisposable so again you should wrap them in a using block.

3. It is not overly clear that the writer is used for logging purposes until you read the code. I would abstract it behind an ILogger interface which I would pass in. It makes it much clearer that the messages are used for logging and removes the responsibility of managing the log file out of the function (Single Responsibility Principle). In fact you should have a look at log4net which provides a whole heap more flexibility in terms of logging targets and filtering. In case your project should grow this will make things a bit easier.

Update

A very simple example use (loosely based on the MSDN example for copying the bitmap data):

public byte[] HashImage(string fileName)
{
    using (var image = new Bitmap(fileName))
    {
        var sha256 = SHA256.Create();

        var rect = new Rectangle(0, 0, image.Width, image.Height);
        var data = image.LockBits(rect, ImageLockMode.ReadOnly, image.PixelFormat);

        var dataPtr = data.Scan0;

        var totalBytes = (int)Math.Abs(data.Stride) * data.Height;
        var rawData = new byte[totalBytes];
        System.Runtime.InteropServices.Marshal.Copy(dataPtr, rawData, 0, totalBytes);

        image.UnlockBits(data);

        return sha256.ComputeHash(rawData);
    }
}

Update 2: To complete the example (based on your pastebin, note I changed the method above to accept a filename rather than a Bitmap directly)

private Tuple<int, string> GetIndexedImage(string fileName)
{
    var baseFileName = Path.GetFileNameWithoutExtension(fileName);
    int index;
    if (int.TryParse(baseFileName, out index))
    {
        return Tuple.Create(index, fileName);
    }
    return null;
}

private void button1_Click(object sender, EventArgs e)
{
    string original = @"C:\Users\user\Documents\CaptchaCollection\";

    var equivalentImages = Directory.GetFiles(original)
                                    .Select(f => GetIndexedImage(f)) // build tuples (index, fileName) or null if parsing failed
                                    .Where(t => t != null)           // ignore all invalid ones
                                    .OrderBy(t => t.Item1)           // order by index
                                    .Select(t => Tuple.Create(HashImage(t.Item2), t.Item2)) // create new tuple (hash, fileName)
                                    .GroupBy(t => t.Item1);          // group by Hash

    // print groups
    foreach (var group in equivalentImages)
    {
        Console.WriteLine("All images with hash: {0}", HashToString(group.Key));
        foreach (var t in group)
        {
            Console.WriteLine("\t{0}", t.Item2);
        }
    }
    
}

private string HashToString(byte[] hash)
{
    var builder = new StringBuilder();
    foreach (var b in hash)
    {
        builder.AppendFormat("{0:x2}", b);
    }
    return builder.ToString();
}

Note:

• Unless the hashes collided (very unlikely) or there is a subtle bug I've missed (possible) all image within each group should have the same content and you can do your file moving.
• You probably don't want to hard-code the directory and rather pass it in from external.