Skip to content

Instantly share code, notes, and snippets.

@kaja47
Last active April 9, 2021 19:53
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kaja47/a15289488eb9a8cdb006 to your computer and use it in GitHub Desktop.
Save kaja47/a15289488eb9a8cdb006 to your computer and use it in GitHub Desktop.
Perceptual hashing + locality-sensitive hashing example
package main
import (
"fmt"
"image"
"image/color"
"os"
"math"
"path/filepath"
_ "image/gif"
_ "image/png"
_ "image/jpeg"
"github.com/nfnt/resize"
)
type IdxHashPair struct {
Idx int
Hash uint64
}
func main() {
pattern := "/path/to/images/*"
fs, _ := filepath.Glob(pattern)
files := make([]string, 0, len(fs))
hashes := make([]uint64, 0, len(fs))
for _, fullPath := range fs {
reader, err := os.Open(fullPath)
if err != nil { continue }
img, _, err := image.Decode(reader)
if err != nil { continue }
hash := ImagePHash(img)
files = append(files, fullPath)
hashes = append(hashes, hash)
reader.Close()
}
// create LSH map
const Bands = 8
const BandBits = 8
const BandMask = (1 << BandBits) - 1
bands := [Bands][BandMask+1][]IdxHashPair {}
for idx, hash := range hashes {
for b := 0 ; b < Bands ; b++ {
h := hash << uint32(b*BandBits) & BandMask
bands[b][h] = append(bands[b][h], IdxHashPair { idx, hash })
}
}
// compute similarities
for idx, hash := range hashes {
for b := 0 ; b < Bands ; b++ {
h := hash << uint32(b*BandBits) & BandMask
for _, candidate := range bands[b][h] {
if idx <= candidate.Idx { continue }
diff := differentBits(hash, candidate.Hash)
if diff < 6 {
similarity := 1.0 - (float64(diff) / float64(64))
fmt.Printf("%s %s %d\n", files[idx], files[candidate.Idx], similarity)
}
}
}
}
}
/* based on http://pastebin.com/Pj9d8jt5 */
func ImagePHash(img image.Image) uint64 {
c := make([]float64, 32)
for i := 1; i < 32; i++ {
c[i] = 1
}
c[0] = 1 / math.Sqrt(2.0)
// Reduce size and reduce color
img = grayscale(resize.Resize(32, 32, img, resize.Bilinear))
vals := make([][]float64, 32)
for i := range vals {
vals[i] = make([]float64, 32)
}
bounds := img.Bounds()
for x := 0; x < bounds.Max.X; x++ {
for y := 0; y < bounds.Max.Y; y++ {
_, _, b, _ := img.At(x,y).RGBA()
vals[x][y] = float64(b)
}
}
/* Compute the DCT */
dctVals := applyDCT(vals, c)
// Reduce the DCT and compute the average value (excluding the first term)
total := 0.0
for x := 0; x < 8; x++ {
for y := 0; y < 8; y++ {
total += dctVals[x][y]
}
}
total -= dctVals[0][0]
avg := total / float64((8 * 8) - 1)
// Further reduce the DCT and create 64 bit hash
hash := uint64(0)
for x := 0; x < 8; x++ {
for y := 0; y < 8; y++ {
if !(x == 0 && y == 0) {
if dctVals[x][y] > avg {
hash = hash | (1 << (63-uint64(x*8+y)))
}
}
}
}
return hash
}
// DCT function stolen from http://stackoverflow.com/questions/4240490/problems-with-dct-and-idct-algorithm-in-java
func applyDCT(f [][]float64, c []float64) [][]float64 {
F := make([][]float64, 32)
for i := range F {
F[i] = make([]float64, 32)
}
cosines := [32][32]float64 {}
for a := 0; a < 32 ; a++ {
for b := 0; b < 32 ; b++ {
cosines[a][b] = math.Cos((float64(2*a+1) / float64(2*32)) * float64(b) * math.Pi)
}
}
for u := 0; u < 32; u++ {
for v := 0; v < 32; v++ {
sum := 0.0
for i := 0; i < 32; i++ {
for j := 0; j < 32; j++ {
aa := cosines[i][u]
bb := cosines[j][v]
sum += aa * bb * f[i][j]
}
}
sum *= (c[u]*c[v] / 4.0)
F[u][v] = sum
}
}
return F
}
func grayscale(img image.Image) image.Image {
bounds := img.Bounds()
gray := image.NewGray(img.Bounds())
for x := bounds.Min.X; x < bounds.Max.X; x++ {
for y := bounds.Min.Y; y < bounds.Max.Y; y++ {
gray.Set(x, y, color.GrayModel.Convert(img.At(x,y)))
}
}
return gray
}
func popcount(x uint64) uint64 {
x -= (x >> 1) & 0x5555555555555555
x = (x >> 2) & 0x3333333333333333 + x & 0x3333333333333333
x += x >> 4
x &= 0x0f0f0f0f0f0f0f0f
x *= 0x0101010101010101
return x >> 56
}
func differentBits(a, b uint64) uint64 {
return popcount(a ^ b)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment