Od pohledu dobrý, aneb jak najít skoro stejné obrázky mezi dvěma miliony souborů za méně než deset minut

A tenhle znáte: „Proč je Pentium rychlejší než 486? 486 počítá, ale Pentium jen odhaduje.“ Přestože jde o nejapný vtip o chybě v prvních Pentiích z počítačového pravěku, má v sobě zrnko pravdy: Odhad může být mnohem rychlejší než přesný výpočet.

Odhad, pokud chci, aby byl k něčemu dobrý, není vůbec jednoduchou záležitostí. Nestačí jen vyprodukovat nějaké hausnumero, ale přibližnou odpověď, která má jasně definovanou chybu. Mezi algoritmy, které dělají právě tohle patří kromě klasických velkých jmen jako Bloomfilter, HyperLogLog, Count-min Skech, MinHash a SimHash, patří také perceptuální hashe určené k detekci téměř shodných obrázků.

Všechny zmíněné algoritmy se spoléhají na hashovací funkce, ale některé (MinHash, SimHash a perceptuální hashe o kterých to dneska celé je) jinak než je běžně známé.

Klasické kryptografické hashe, jako je MD5, SHA1 a jejich kamarádi, jsou navrženy tak, že změna jednoho bitu vstupu v ideálním případě znamená změnu poloviny bitů výstupu. Nekryptografické hashe, běžně používané v programování, nemají tuto vlastnost. Typicky jde aspoň o univerzální hash nebo o nějaký k-nezávislý hash. Otisk je přesto výsledkem divokých permutací vstupních dat a neměl by zachovávat jejich korelace. Perceptuální hash je přesně opačný – jde o takový otisk obrázku, který zachovává korelace vstupních dat – když jsou si obrázky na vstupu podobné, budou si s největší pravděpodobností podobné i jejich otisky a míra podobnosti obrázků odpovídá podobnosti hashů.

Algoritmus je jednoduchý:

  1. Zmenším obrázek například na 32×32 pixelů (dělám to kvůli zrychlení následujících výpočtů a ne pro redukci vysokých frekvencí)
  2. Převedu na odstíny šedi (opět kvůli zrychlení následujících kro­ků)
  3. Spočítám 32×32 diskrétní kosinovou transformaci (DCT)
  4. Zredukuji DCT a nechám si jen prvních 8×8 hodnot (kromě té úplně první, která by rozhodila průměr). Tyto hodnoty reprezentují nejnižší frekvence obrázku, tedy ty, které popisují hrubou strukturu.
  5. Spočítám průměrnou hodnotu těchto frekvencí
  6. Vytvořím finální hash o délce 64 bitů – daný bit má hodnotu 1, když je korespondující frekvence vyšší než průměr, 0, pokud je menší

Takto získám perceptuální hash obrázku, kterému nevadí změny barevnosti, světlosti (kvůli tomu, že zaznamenávám rozdíl proti průměru) a ani určité úpravy obrázku samotného. Nejnižší frekvence zaznamenávají nejhrubší kontury a rozdělení světel a stínů a jsou proto odolné vůči změnám v detailech.

Když pak chci porovnat, jak jsou si dva obrázky podobné, spočítám Hammingovu vzdálenost mezi jejich perceptuálními hashi. Výsledkem je počet bitů, ve kterých se oba hashe liší. Když se neliší v žádném bitu, jde o dva vizuálně téměř identické obrázky. Možná byl jednou uložen jako jpg a podruhé jako png. Když se liší jen pár bitů (±5) jde nejspíš o jeden a tentýž obrázek s drobnými úpravami, když se liší ve více bitech, jde s největší pravděpodobností o rozdílné obrázky.

Zkusmo jsem si perceptuální hashování napsal v jazyce Go (respektive bezostyšně ukradl přepsal tohle z Javy). Kompletní kód je k vidění v samostatném gistu.

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
}

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++ {
          sum += cosines[i][u] * cosines[j][v] * f[i][j]
        }
      }
      sum *= (c[u]*c[v] / 4.0)
      F[u][v] = sum
    }
  }
  return F
}

Jak je vidět, jde o pár řádků kódu a výsledky jsou překvapivě přesné.

(nebo, nebo, nebo)

Přesto nejde o neomylný algoritmus. Kód si pohrává s pravděpodobnostmi a někdy, když se plete, bývají výsledky veselé. Zvlášť, když zvýším toleranci podobnosti.

Teď už zbývá jen vyřešit, jak to dělat rychle, když chci projít v titulku zmíněné dva miliony obrázků pod deset minut.

Samotné porovnání p-hashů se může zdát jako dostatečně rychlé. V ideálním případě jde o pouhé 2 instrukce: xor a popcnt + něco málo okolo.1 Přesto, pokud chci porovnat všechny hashe se všemi ostatními, musím udělat kvadratické množství práce a velké číslo se umocněním na druhou bohužel nezmenší.

Naštěstí můžu všechno znatelně urychlit pomocí postupu známého jako locality-sensitive hashing (LSH) – další z metod, která si hraje s pravděpodobnostmi a obětuje něco málo přesnosti ve prospěch masivního zrychlení.

LSH využívá hashe zachovávající lokalitu (podobné věci mají podobné hashe) a snaží se položky rozdělit do skupin, kdy v každé skupině jsou položky, které si můžou být podobné, ale nejsou tam ty, které jsou očividně rozdílné.

V tomto případě zkonstruuji LSH pro Hammingovu vzdálenost tak, že 64 bitů hashe rozsekám na 8 pruhů (band) po 8 bitech a každý hash přiřadím do skupiny (bucket) určenou bity každého pruhu.

To znamená, že když prvních osm bitů hashe má hodnotu 0xFF, v prvním pruhu ho přiřadím do bucketu 0xFF, když má druhých 8 bitů 0x0A, v druhém pruhu spadne do skupiny 0x0A a tak dále.

Celé to funguje na jednoduchém předpokladu: Pokud jsou si dva hashe velice podobné, s největší pravděpodobností se shodují v bitech jednoho nebo více pruhů.2 Když chci najít všechny hashe podobné hashi A, vezmu jeho prvních 8 bitů, podívám se do odpovídajícího bucketu prvního pruhu a spočítám podobnost jen s těmito kandidáty, pak vezmu dalších osm bitů a spočítám podobnost s těmito kandidáty. To udělám jednou pro každý pruh a mám výsledné podobné hashe. Protože jde o pravděpodobnostní metodu, může se stát, že některé skutečně podobné hashe to přeskočí, protože se vždy o jeden bit lišily ve všech pruzích a proto skončily v odlišných bucketech a vůbec nebyly vybráni jako kandidáti. Pokud se zajímám o velice podobné hashe, je tato šance velice malá. Pokud chci v takto vytvořeném LSH najít hashe lišící se v méně než 8 bitech, je garantováno, že všechny dostanu, protože se aspoň v jednom pruhu musí shodovat.

S LSH, kdy mám 8 pruhů po 8 bitech, mi musím udělat jen 8/256 práce – 32× méně, protože se musím podívat do 8 bucketů (jeden v každém pruhu) a spočítat podobnosti ve všemi kandidáty, kterých je 1/256. Pokud to nestačí, můžu tyto dva parametry zvolit podle toho, jak je třeba: když chci víc přesnosti zvolím menší šířku pruhu (12×5 bitů), pokud chci více rychlosti, zvolím širší pruhy (6×10 bitů).

No a s tímto „zlepšovákem“ dokážu bez větších problémů porovnat ony dva miliony obrázků pod 10 minut.

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

To je všechno. Záhada vyřešena.


Protože tuto techniku používám na několika místech (například pro detekci podobných článků na devblozích, tady, na téhle maličkosti a na mnoha dalších místech), tak jsem si proto napsal vlastní knihovnu nazvanou prozaicky sketches, která obsahuje implementaci PHashe, skečů, LSH, ALS, FunkSVD nebo DBSCAN clusterování a dalších nesouvisejících vě­cí.


Dále k tématu:


Pozn:

  1. V Go se bohužel k popcnt bez tanečků v assembleru nedá dostat a tak je třeba si napsat utilitu, která dělá to samé, ale potřebuje o něco víc instrukcí.
  2. Pravděpodobnost, že LSH odhalí dva kandidáty je 1 – (1 – pn)b, kde p je podobnost mezi dvěma kandidáty, n šířka pruhu a b je počet pruhů. Pomocí tohoto vztahu můžu najít hodnoty n a p, které budou fungovat pro požadovaný práh podobnosti.

Flattr this!

This entry was posted in Algo, DS. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *