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!
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.
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.
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:
Reduce the size to 9x8 pixels. Don't worry about the original image size or aspect ratio.
Convert to grayscale because we only care about the "brightness" of each pixel.
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.
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.
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.
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.
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.
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.
usingnamespaceSystem.IOusingnamespaceSystem.Management.AutomationfunctionGet-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-AssemblyNameSystem.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($filePathin$LiteralPath){try{$null=Resolve-Path-LiteralPath$filePath-ErrorActionStop$stream=[file]::Open($filePath,[filemode]::Open,[fileaccess]::Read,[fileshare]::Read)$params=@{InputStream=$streamColorMatrix=$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$srcfor($y=0;$y-lt$dst.Height;$y++){$byte=[byte]0for($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-shl1$byte=$byte-bor$thisPixelIsBrighter}$dHash[$y]=$byte}ConvertTo-HexString-InputObject$dHashif($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()}}}}functionCompare-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-lt8;$index++){$byte1=[convert]::ToByte($DHash1.SubString($index*2,2),16)$byte2=[convert]::ToByte($DHash2.SubString($index*2,2),16)$xor=$byte1-bxor$byte2for($bit=8;$bit-gt0;$bit--){$difference+=$xor-band1$xor=$xor-shr1}}$difference}}functionConvertFrom-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}}functionConvertTo-HexString{[CmdletBinding()][OutputType([string])]param([Parameter(Mandatory,Position=0)][byte[]]$InputObject)process{[string]::Join('',($InputObject|ForEach-Object{$_.ToString('x2')}))}}functionConvertTo-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()}}}}functionGet-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-gt0){$LiteralPath=(Resolve-Path-Path$Path).ProviderPath}else{$LiteralPath=(Resolve-Path-LiteralPath$LiteralPath).ProviderPath}foreach($filePathin$LiteralPath){try{$null=Resolve-Path-LiteralPath$filePath-ErrorActionStop$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=$AlgorithmHash=Get-DHash-InputStream$streamPath=$filePath}}}functionCompare-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($hashin$InputObject){if($PSCmdlet.ParameterSetName-eq'InputObject'){if([string]::IsNullOrWhiteSpace($ReferenceHash)){$ReferenceHash=$hashcontinue}elseif([string]::IsNullOrWhiteSpace($DifferenceHash)){$DifferenceHash=$hashcontinue}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-lt8;$index++){$byte1=[convert]::ToByte($ReferenceHash.SubString($index*2,2),16)$byte2=[convert]::ToByte($DifferenceHash.SubString($index*2,2),16)$xor=$byte1-bxor$byte2for($bit=8;$bit-gt0;$bit--){$difference+=$xor-band1$xor=$xor-shr1}}$difference}catch{Write-Error-ErrorRecord$_}}}Export-ModuleMember-FunctionGet-PerceptHash,Compare-PerceptHash
