0xDEADBEEF

phash.go

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)
}