Skip to content

Image Comparison

I recently came across a couple of blog posts on image comparison algorithms shared by Dr. Neal Krawetz. One of them, titled "Kind Of Like That", describes the "dHash" algorithm which generates a perceptual hash based on gradients in the image. With more than 200k family photos to wrangle, I wrote up a PowerShell implementation to find similar images and it works surprisingly well!

Coastline Bluff

After almost 20 years of taking pictures and videos with our smart phones, our family photos and videos are scattered between the Google and Apple clouds. In order to make sure all these memories are safe, no matter what happens with our cloud accounts over time, I downloaded everything, and will be following a 3-2-1 backup strategy. That means there will be at least three copies, on two different storage mediums, with one copy offsite.

So many duplicates

While trying out a self-hosted instance of PhotoPrism and indexing over 60k files so far, I noticed that a lot of our photos are duplicates. Many of them are exact duplicates and those are easy to find using a traditional SHA hash, but most duplicates are...

  • resized versions of the original
  • edited to add a border or to change the colors in some way
  • very similar images taken within the same second or two, and not duplicates at all

I'm sure I have enough storage available to just back them all up, but the percentage of wasted space is somewhere around 40% and it just didn't sit well with me. Plus, with so many duplicates, it's frustrating to scroll through the library in apps like PhotoPrism. Tagging faces gets old quickly when you keep seeing the same face in the same photo repeated over and over.

The algorithm

I searched around online to see what my options were in terms of tools, or maybe existing .NET or Python libraries, and that's when I came across one of Dr. Neal Krawetz' blog posts. It's a short and interesting read, and my first introduction to a "perceptual hash". If you're interested, please do go check out his blog!

I hear and use the word "hash" on a regular basis, and have used all kinds of cryptographic hashes over the years including md5, bcrypt, and the various sha's. But these are fundamentally different algorithms with almost polar opposite goals. The kind of hashs I was familar with were designed to produce wildly different results from two sets of data if even a single bit was different between them. The resulting hashes were either the same, indicating that the inputs were very likely the same (collisions happen, but they're hard to find), or they were different, indicating that the inputs were definitely different. There should be no way to measure how similar two inputs are based on their SHA hashes. If you could, the algorithm would be too weak to use for any kind of security or privacy on the web.

In contrast, a perceptual hash like dHash will, by design, produce the same or similar hash when given two images that are nearly identical. And since each bit in the 64bit hash represents a part of the image, you can calculate the hamming distance between two hashes to determine how many of the 64bits in the two hashes are different. Fewer differences indicate a higher likelihood that the hashes are from the same or similar images.

Here's a quick summary of the dHash algorithm:

  1. Reduce the size to 9x8 pixels. Don't worry about the original image size or aspect ratio.
  2. Convert to grayscale because we only care about the "brightness" of each pixel.
  3. Compare each pixel's brightness to the neighbor on the right. This is why the image is resized to 9x8 - we need 8 bits per row.
  4. Assign a bit value of "1" if the current pixel is brighter than the neighbor on the right.

You will end up with one byte per row, and 8 rows, for a total of 64 bits. Convert the array of bytes to a hexadecimal string and you have your dHash.

Examples

Nearly identical

These photos of my daughter at the river are nearly identical to the untrained eye, but the raw files are very different. In the following table you'll find a side-by-side comparison of what appears to be the same image, and their dHashes along with a SHA1. For fun, you'll also find the 9x8 grayscale versions from which the dHashes were derived.

The hamming distance between the dHash values from these images is 2, which means two out of the 64 bits of the hash were different, so as you would expect, the hash comparison shows that the images have a strong visual similarity.

Photo 1 Photo 2
Photo 1 Photo 2
dHash 1 dHash 2
dHash: 41304c4be436784c dHash: 41204c49e436784c
SHA1: 80187EB0E86F2FCDE82E60D7CD53BB0B1B1FF686 SHA1: 5BC13493BB94536C3EAE794A924C1D9A00D207D6

Image filter applied

In this next example, the first image is the original and the second has been "color enhanced". We can see that the images are definitely different, but we can also see that they're most likely the same image with different colors. Once again, when we compare the dHashes, we get a difference of 2. Since that is well under 10, we can be fairly confident that the images are similar.

Photo 3 Photo 4
Photo 3 Photo 4
dHash 3 dHash 4
dHash: 60606040587c5c7c dHash: 60606040d87c5d7c
SHA1: BDE8B4AB0DC4E28D4DA72A982E4B99159E72EA9C SHA1: C624DC07813ABBC07E286665AF7A41941F19F9AF

Very different cats

Okay in this last example, just to demonstrate that the algorithm doesn't consider all images similar, here are two very different cats because... internet. The dHash comparison returns a value of 20.

Photo 5 Photo 6
Photo 5 Photo 6
dHash 5 dHash 6
dHash: 564e7c6cee3f526e dHash: 54ccace8e8cbe67e
SHA1: 51E2DFE65974C86740C314E7883D22C163D3EA1B SHA1: A58DBDAA875B5FC311BBB35A74748E68550CFC12

Code

Here's the code so far. The idea was that the cmdlets should work similar to the way the Get-FileHash cmdlet works, so the output of Get-PerceptHash is a [PSCustomObject] with an Algorithm, Hash, and Path property. When I get around to it, I think I'll implement additional perception hashes incuding aHash and pHash as described by Dr. Neal Krawetz, but for now only the dHash algorithm is implemented here.

Later, I'll post an update with another potential use-case for this - comparison of video surveillance images for the purpose of checking whether a camera has been obscured or moved. I'm not sure the reliability is good enough to use on it's own, but I'm thinking it should be relatively easy to do multiple types of perception hashes and edge detection to produce a sort of composite hash for better accuracy.

Download

PerceptHash.psm1
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
using namespace System.IO
using namespace System.Management.Automation

function Get-DHash {
    <#
    .SYNOPSIS
    Computes the dHash value for the provided image.
    .DESCRIPTION
    The `Get-DHash` cmdlet computes the dHash value for the provided image. The dHash is a 64-bit representation of the
    image, returned as a hexadecimal string. The dHash values for two images can be compared using Compare-DHash, and
    the resulting value represents the number of bits that are different between the two images, or the
    "Hamming distance".
    The dHash is computed using the following algorithm. See the blog post referenced in the notes for more information.
    1. Convert the image to grayscale.
    2. Resize the image to 9x8.
    3. For each of the 8 rows in the resulting image, check if each pixel is brighter than the neighbor to the right. If
       it is, that bit is set to 1.
    4. Convert the 8 resulting bytes to a hexadecimal string.
    .PARAMETER Path
    Specifies the path to an image file.
    .PARAMETER Bytes
    Specifies an array of bytes representing an image.
    .PARAMETER OutFile
    For diagnostic purposes, you may provide a path to save the resized, grayscale representation of the provided image created for dHash calculation.
    .PARAMETER ColorMatrix
    Optionally you may provide a custom ColorMatrix used to create a grayscale representation of the source image.
    .EXAMPLE
    $dhash1 = Get-DHash ./image1.jpg
    $dhash2 = Get-DHash ./image2.jpg
    Compare-DHash $dhash1 $dhash2
    Computes the dHash values for two different images, and then compares the
    dHash values. The result is the number of bits that do not match between the
    two difference-hashes.
    .NOTES
    The inspiration for the dHash concept and these functions comes from a blog
    post by Dr. Neal Krawetz on [The Hacker Factor Blog](https://www.hackerfactor.com/blog/index.php?/archives/529-Kind-of-Like-That.html).
    #>
    [CmdletBinding(DefaultParameterSetName = 'Path')]
    [OutputType([string])]
    param (
        [Parameter(Mandatory, Position = 0, ValueFromPipeline, ValueFromPipelineByPropertyName, ParameterSetName = 'Path')]
        [string]
        $Path,

        [Parameter(Mandatory, Position = 0, ValueFromPipelineByPropertyName, ParameterSetName = 'LiteralPath')]
        [Alias('PSPath')]
        [Alias('LP')]
        [string]
        $LiteralPath,

        [Parameter(Mandatory, Position = 0, ParameterSetName = 'Stream')]
        [System.IO.Stream]
        $InputStream,

        # Saves a copy of the grayscale, resized reference image used for calculating dHash for diagnostic purposes.
        [Parameter(ParameterSetName = 'Path')]
        [Parameter(ParameterSetName = 'LiteralPath')]
        [Parameter(ParameterSetName = 'Stream')]
        [string]
        $OutFile,

        [Parameter(ParameterSetName = 'Path')]
        [Parameter(ParameterSetName = 'LiteralPath')]
        [Parameter(ParameterSetName = 'Stream')]
        [float[]]
        $ColorMatrix = @(0.299, 0.587, 0.114)
    )

    begin {
        Add-Type -AssemblyName System.Drawing
    }

    process {
        if ($PSCmdlet.ParameterSetName -ne 'Stream') {
            if (-not [string]::IsNullOrWhiteSpace($Path)) {
                $LiteralPath = (Resolve-Path -Path $Path).ProviderPath
            } else {
                $LiteralPath = (Resolve-Path -LiteralPath $LiteralPath).ProviderPath
            }
            foreach ($filePath in $LiteralPath) {
                try {
                    $null = Resolve-Path -LiteralPath $filePath -ErrorAction Stop
                    $stream = [file]::Open($filePath, [filemode]::Open, [fileaccess]::Read, [fileshare]::Read)
                    $params = @{
                        InputStream = $stream
                        ColorMatrix = $ColorMatrix
                    }
                    if (-not [string]::IsNullOrWhiteSpace($OutFile)) {
                        $params.OutFile = $OutFile
                    }
                    Get-DHash @params
                } catch {
                    Write-Error -ErrorRecord $_
                } finally {
                    if ($stream) {
                        $stream.Dispose()
                    }
                }
            }
            return
        }
        try {
            $dHash = [byte[]]::new(8)
            $src = [drawing.image]::FromStream($InputStream)
            $dst = ConvertTo-DHashImage -Image $src
            for ($y = 0; $y -lt $dst.Height; $y++) {
                $byte = [byte]0
                for ($x = 0; $x -lt ($dst.Width - 1); $x++) {
                    $thisPixel = $dst.GetPixel($x, $y).GetBrightness()
                    $nextPixel = $dst.GetPixel($x + 1, $y).GetBrightness()
                    $thisPixelIsBrighter = [byte]($thisPixel -gt $nextPixel)
                    $byte = $byte -shl 1
                    $byte = $byte -bor $thisPixelIsBrighter
                }
                $dHash[$y] = $byte
            }
            ConvertTo-HexString -InputObject $dHash

            if ($PSCmdlet.MyInvocation.BoundParameters.ContainsKey('OutFile')) {
                $OutFile = $ExecutionContext.SessionState.Path.GetUnresolvedProviderPathFromPSPath($OutFile)
                $dst.Save($OutFile, [System.Drawing.Imaging.ImageFormat]::Jpeg)
            }
        } finally {
            $src, $dst | Where-Object { $null -ne $_ } | ForEach-Object {
                $_.Dispose()
            }
        }
    }
}

function Compare-DHash {
    <#
    .SYNOPSIS
    Compares the provided dHash strings and returns the difference as an integer between 0 and 64.
    .DESCRIPTION
    The `Compare-DHash` cmdlet compares the provided dHash strings and returns the difference as an
    integer between 0 and 64.
    .PARAMETER DHash1
    Specifies a case-insensitive dHash string with 16 hexadecimal characters.
    .PARAMETER DHash2
    Specifies a case-insensitive dHash string with 16 hexadecimal characters.
    .EXAMPLE
    $dhash1 = Get-DHash ./image1.jpg
    $dhash2 = Get-DHash ./image2.jpg
    Compare-DHash $dhash1 $dhash2
    Computes the dHash values for two different images, and then compares the
    dHash values. The result is the number of bits that do not match between the
    two difference-hashes.
    .NOTES
    The inspiration for the dHash concept and these functions comes from a blog
    post by Dr. Neal Krawetz on [The Hacker Factor Blog](https://www.hackerfactor.com/blog/index.php?/archives/529-Kind-of-Like-That.html).
    #>
    [CmdletBinding()]
    [OutputType([int])]
    param (
        [Parameter(Mandatory, Position = 0)]
        [string]
        $DHash1,

        [Parameter(Mandatory, Position = 1)]
        [string]
        $DHash2
    )

    process {
        $difference = 0;
        for ($index = 0; $index -lt 8; $index++) {
            $byte1 = [convert]::ToByte($DHash1.SubString($index * 2, 2), 16)
            $byte2 = [convert]::ToByte($DHash2.SubString($index * 2, 2), 16)
            $xor = $byte1 -bxor $byte2
            for ($bit = 8; $bit -gt 0; $bit--) {
                $difference += $xor -band 1
                $xor = $xor -shr 1
            }
        }
        $difference
    }
}

function ConvertFrom-HexString {
    [CmdletBinding()]
    [OutputType([byte[]])]
    param (
        [Parameter(Mandatory, Position = 0, ValueFromPipeline)]
        [string]
        $InputObject
    )

    process {
        $bytes = [byte[]]::new($InputObject.Length / 2)
        for ($index = 0; $index -lt $bytes.Length; $index++) {
            $bytes[$index] = [convert]::ToByte($InputObject.SubString($index * 2, 2), 16)
        }
        Write-Output $bytes -NoEnumerate
    }
}

function ConvertTo-HexString {
    [CmdletBinding()]
    [OutputType([string])]
    param (
        [Parameter(Mandatory, Position = 0)]
        [byte[]]
        $InputObject
    )

    process {
        [string]::Join('', ($InputObject | ForEach-Object { $_.ToString('x2') }))
    }
}

function ConvertTo-DHashImage {
    <#
    .SYNOPSIS
    Returns a grayscale 9x8 resolution image based on the input image.
    .DESCRIPTION
    The `ConvertTo-DHashImage` cmdlet returns a grayscale 9x8 resolution image
    based on the input image.
    .PARAMETER Image
    Specifies the input image.
    .PARAMETER ColorMatrix
    Optionally specifies the RGB values to use in the ColorMatrix used for grayscale conversion.
    .EXAMPLE
    [System.Drawing.Image]::FromFile('C:\path\to\image.jpg') | ConvertTo-DHashImage
    Create a new System.Drawing.Image object from image.jpg, and produce a grayscale 9x8 representation of it.
    #>
    [CmdletBinding()]
    [OutputType([System.Drawing.Image])]
    param (
        [Parameter(Mandatory, ValueFromPipeline, Position = 1)]
        [System.Drawing.Image]
        $Image,

        [Parameter()]
        [float[]]
        $ColorMatrix = @(0.299, 0.587, 0.114)
    )

    process {
        $r = $ColorMatrix[0]
        $g = $ColorMatrix[1]
        $b = $ColorMatrix[2]
        $grayScale = [float[][]]@(
            [float[]]@($r, $r, $r, 0, 0),
            [float[]]@($g, $g, $g, 0, 0),
            [float[]]@($b, $b, $b, 0, 0),
            [float[]]@( 0, 0, 0, 1, 0),
            [float[]]@( 0, 0, 0, 0, 1)
        )

        try {
            $dst = [drawing.bitmap]::new(9, 8)
            $dstRectangle = [drawing.rectangle]::new(0, 0, $dst.Width, $dst.Height)
            $graphics = [drawing.graphics]::FromImage($dst)
            $graphics.CompositingMode = [drawing.drawing2d.compositingmode]::SourceOver
            $graphics.CompositingQuality = [drawing.drawing2d.CompositingQuality]::HighQuality
            $graphics.InterpolationMode = [drawing.drawing2d.InterpolationMode]::HighQualityBicubic
            $graphics.PixelOffsetMode = [drawing.drawing2d.PixelOffsetMode]::None
            $imgAttr = [drawing.imaging.imageattributes]::new()
            $imgAttr.SetWrapMode([drawing.drawing2d.wrapmode]::Clamp)
            $imgAttr.SetColorMatrix([drawing.imaging.colormatrix]::new($grayScale))
            $graphics.DrawImage($Image, $dstRectangle, 0, 0, $Image.Width, $Image.Height, [drawing.graphicsunit]::Pixel, $imgAttr)
            $dst
        } finally {
            $imgAttr, $graphics | Where-Object { $null -ne $_ } | ForEach-Object {
                $_.Dispose()
            }
        }
    }
}

function Get-PerceptHash {
    [CmdletBinding(DefaultParameterSetName = 'Path')]
    [OutputType([pscustomobject])]
    param(
        [Parameter(Mandatory, ValueFromPipeline, ValueFromPipelineByPropertyName, Position = 0, ParameterSetName = 'Path')]
        [string[]]
        $Path,

        [Parameter(Mandatory, ValueFromPipelineByPropertyName, Position = 0, ParameterSetName = 'LiteralPath')]
        [Alias('PSPath')]
        [Alias('LP')]
        [string[]]
        $LiteralPath,

        [Parameter(Mandatory, Position = 0, ParameterSetName = 'Stream')]
        [System.IO.Stream]
        $InputStream,

        [Parameter(Position = 1, ParameterSetName = 'Path')]
        [Parameter(Position = 1, ParameterSetName = 'LiteralPath')]
        [Parameter(Position = 1, ParameterSetName = 'Stream')]
        [ValidateSet('aHash', 'dHash', 'pHash', IgnoreCase = $true)]
        [string]
        $Algorithm = 'dHash'
    )

    process {
        if ($Algorithm -ne 'dHash') {
            throw "Sorry, the $Algorithm algorithm is not yet implemented. Try dHash instead."
        }
        if ($PSCmdlet.ParameterSetName -ne 'Stream') {
            if ($Path.Count -gt 0) {
                $LiteralPath = (Resolve-Path -Path $Path).ProviderPath
            } else {
                $LiteralPath = (Resolve-Path -LiteralPath $LiteralPath).ProviderPath
            }
            foreach ($filePath in $LiteralPath) {
                try {
                    $null = Resolve-Path -LiteralPath $filePath -ErrorAction Stop
                    $stream = [file]::Open($filePath, [filemode]::Open, [fileaccess]::Read, [fileshare]::Read)
                    Get-PerceptHash -InputStream $stream -Algorithm $Algorithm
                } catch {
                    Write-Error -ErrorRecord $_
                } finally {
                    if ($stream) {
                        $stream.Dispose()
                    }
                }
            }
            return
        }
        [pscustomobject]@{
            PSTypeName  = 'PerceptHash'
            Algorithm = $Algorithm
            Hash      = Get-DHash -InputStream $stream
            Path      = $filePath
        }
    }
}

function Compare-PerceptHash {
    <#
    .SYNOPSIS
    Compares the provided perception hashes and returns the difference as an integer.
    .DESCRIPTION
    The `Compare-PerceptHash` cmdlet compares the provided perception hashes and
    returns the difference as an integer. A value of 10 or less indicates strong
    visual similarity. A value of 0 indicates very strong visual similarity, though
    because the comparison is based on highly compressed versions of the original
    images, a value of 0 does not guarantee the images are the same.

    .PARAMETER ReferenceHash
    Specifies a case-insensitive hexadecimal string.

    .PARAMETER DifferenceHash
    Specifies a case-insensitive hexadecimal string.

    .EXAMPLE
    $dhash1 = Get-PerceptHash ./image1.jpg
    $dhash2 = Get-PerceptHash ./image2.jpg
    $dhash1, $dhash2 | Compare-PerceptHash

    Computes the dHash values for two different images, and then compares the
    dHash values. The result is the number of bits that do not match between the
    two difference-hashes.

    .NOTES
    The inspiration for the dHash concept and these functions comes from a blog
    post by Dr. Neal Krawetz on [The Hacker Factor Blog](https://www.hackerfactor.com/blog/index.php?/archives/529-Kind-of-Like-That.html).
    #>
    [CmdletBinding(DefaultParameterSetName = 'default')]
    [OutputType([int])]
    param (
        [Parameter(Mandatory, ValueFromPipeline, ValueFromPipelineByPropertyName, ParameterSetName = 'InputObject')]
        [Alias('Hash')]
        [string[]]
        $InputObject,

        [Parameter(Mandatory, Position = 0, ParameterSetName = 'default')]
        [string]
        $ReferenceHash,

        [Parameter(Mandatory, Position = 1, ParameterSetName = 'default')]
        [string]
        $DifferenceHash
    )

    process {
        foreach ($hash in $InputObject) {
            if ($PSCmdlet.ParameterSetName -eq 'InputObject') {
                if ([string]::IsNullOrWhiteSpace($ReferenceHash)) {
                    $ReferenceHash = $hash
                    continue
                } elseif ([string]::IsNullOrWhiteSpace($DifferenceHash)) {
                    $DifferenceHash = $hash
                    continue
                } else {
                    throw "Too many hashes have been provided for comparison. Please provide only two hashes at a time."
                }
            }
        }
    }

    end {
        try {
            $difference = 0;
            for ($index = 0; $index -lt 8; $index++) {
                $byte1 = [convert]::ToByte($ReferenceHash.SubString($index * 2, 2), 16)
                $byte2 = [convert]::ToByte($DifferenceHash.SubString($index * 2, 2), 16)
                $xor = $byte1 -bxor $byte2
                for ($bit = 8; $bit -gt 0; $bit--) {
                    $difference += $xor -band 1
                    $xor = $xor -shr 1
                }
            }
            $difference
        } catch {
            Write-Error -ErrorRecord $_
        }
    }
}

Export-ModuleMember -Function Get-PerceptHash, Compare-PerceptHash

Comments