funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

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

1. 11. 2016 — k47

A tenhle znáte: „Proč je Pen­tium rych­lejší než 486? 486 počítá, ale Pen­tium jen od­ha­duje.“ Přes­tože jde o nejapný vtip o chybě v prv­ních Pen­ti­ích z po­čí­ta­čo­vého pra­věku, má v sobě zrnko pravdy: Odhad může být mnohem rych­lejší než přesný vý­po­čet.

Odhad, pokud chci, aby byl k něčemu dobrý, není vůbec jed­no­du­chou zá­le­ži­tostí. Ne­stačí jen vy­pro­du­ko­vat nějaké haus­nu­mero, ale při­bliž­nou od­po­věď, která má jasně de­fi­no­va­nou chybu. Mezi al­go­ritmy, které dělají právě tohle patří kromě kla­sic­kých vel­kých jmen jako Blo­om­fil­ter, Hy­per­Lo­gLog, Count-min Skech, MinHashSi­mHash, patří také per­cep­tu­ální hashe určené k de­tekci téměř shod­ných ob­rázků.

Všechny zmí­něné al­go­ritmy se spo­lé­hají na ha­sho­vací funkce, ale ně­které (MinHash, Si­mHash a per­cep­tu­ální hashe o kte­rých to dneska celé je) jinak než je běžně známé.

Kla­sické kryp­to­gra­fické hashe, jako je MD5, SHA1 a jejich ka­ma­rádi, jsou na­vr­ženy tak, že změna jed­noho bitu vstupu v ide­ál­ním pří­padě zna­mená změnu po­lo­viny bitů vý­stupu. Ne­kryp­to­gra­fické hashe, běžně po­u­ží­vané v pro­gra­mo­vání, nemají tuto vlast­nost. Ty­picky jde aspoň o uni­ver­zální hash nebo o nějaký k-ne­zá­vislý hash. Otisk je přesto vý­sled­kem di­vo­kých per­mu­tací vstup­ních dat a neměl by za­cho­vá­vat jejich ko­re­lace. Per­cep­tu­ální hash je přesně opačný – jde o takový otisk ob­rázku, který za­cho­vává ko­re­lace vstup­ních dat – když jsou si ob­rázky na vstupu po­dobné, budou si s nej­větší prav­dě­po­dob­ností po­dobné i jejich otisky a míra po­dob­nosti ob­rázků od­po­vídá po­dob­nosti hashů.

Al­go­rit­mus je jed­no­du­chý:

  1. Zmen­ším ob­rá­zek na­pří­klad na 32x32 pixelů (dělám to kvůli zrych­lení ná­sle­du­jí­cích vý­po­čtů a ne pro re­dukci vy­so­kých frek­vencí)
  2. Pře­vedu na od­stíny šedi (opět kvůli zrych­lení ná­sle­du­jí­cích kroků)
  3. Spo­čí­tám 32x32 dis­krétní ko­si­no­vou trans­for­maci (DCT)
  4. Zre­du­kuji DCT a nechám si jen prv­ních 8x8 hodnot (kromě té úplně první, která by roz­ho­dila průměr). Tyto hod­noty re­pre­zen­tují nej­nižší frek­vence ob­rázku, tedy ty, které po­pi­sují hrubou struk­turu.
  5. Spo­čí­tám prů­měr­nou hod­notu těchto frek­vencí
  6. Vy­tvo­řím fi­nální hash o délce 64 bitů – daný bit má hod­notu 1, když je ko­re­spon­du­jící frek­vence vyšší než průměr, 0, pokud je menší

Takto získám per­cep­tu­ální hash ob­rázku, kte­rému nevadí změny ba­rev­nosti, svět­losti (kvůli tomu, že za­zna­me­ná­vám rozdíl proti prů­měru) a ani určité úpravy ob­rázku sa­mot­ného. Nej­nižší frek­vence za­zna­me­ná­vají nej­hrubší kon­tury a roz­dě­lení světel a stínů a jsou proto odolné vůči změnám v de­tai­lech.

Když pak chci po­rov­nat, jak jsou si dva ob­rázky po­dobné, spo­čí­tám Ha­m­min­govu vzdá­le­nost mezi jejich per­cep­tu­ál­ními hashi. Vý­sled­kem je počet bitů, ve kte­rých se oba hashe liší. Když se neliší v žádném bitu, jde o dva vi­zu­álně téměř iden­tické ob­rázky. Možná byl jednou uložen jako jpg a po­druhé jako png. Když se liší jen pár bitů (±5) jde nej­spíš o jeden a tentýž ob­rá­zek s drob­nými úpra­vami, když se liší ve více bitech, jde s nej­větší prav­dě­po­dob­ností o roz­dílné ob­rázky.

Zkusmo jsem si per­cep­tu­ální ha­sho­vání napsal v jazyce Go (re­spek­tive bez­o­styšně ukradl pře­psal tohle z Javy). Kom­pletní kód je k vidění v sa­mo­stat­né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ře­kva­pivě přesné.

(nebo, nebo, nebo)

Přesto nejde o ne­o­mylný al­go­rit­mus. Kód si po­hrává s prav­dě­po­dob­nostmi a někdy, když se plete, bývají vý­sledky veselé. Zvlášť, když zvýším to­le­ranci po­dob­nosti.

Teď už zbývá jen vy­ře­šit, jak to dělat rychle, když chci projít v ti­tulku zmí­něné dva mi­li­ony ob­rázků pod deset minut.

Sa­motné po­rov­nání p-hashů se může zdát jako do­sta­tečně rychlé. V ide­ál­ním pří­padě jde o pouhé 2 in­strukce: xorpopcnt + něco málo okolo.1 Přesto, pokud chci po­rov­nat všechny hashe se všemi ostat­ními, musím udělat kva­d­ra­tické množ­ství práce a velké číslo se umoc­ně­ním na druhou bo­hu­žel ne­zmenší.

Na­štěstí můžu všechno zna­telně urych­lit pomocí po­stupu zná­mého jako lo­ca­lity-sensi­tive ha­shing (LSH) – další z metod, která si hraje s prav­dě­po­dob­nostmi a obě­tuje něco málo přes­nosti ve pro­spěch masiv­ního zrych­lení.

LSH vy­u­žívá hashe za­cho­vá­va­jící lo­ka­litu (po­dobné věci mají po­dobné hashe) a snaží se po­ložky roz­dě­lit do skupin, kdy v každé sku­pině jsou po­ložky, které si můžou být po­dobné, ale nejsou tam ty, které jsou oči­vidně roz­dílné.

V tomto pří­padě zkon­stru­uji LSH pro Ha­m­min­govu vzdá­le­nost tak, že 64 bitů hashe roz­se­kám na 8 pruhů (band) po 8 bitech a každý hash při­řa­dím do sku­piny (bucket) ur­če­nou bity kaž­dého pruhu.

To zna­mená, že když prv­ních osm bitů hashe má hod­notu 0xFF, v prvním pruhu ho při­řa­dím do bucketu 0xFF, když má dru­hých 8 bitů 0x0A, v druhém pruhu spadne do sku­piny 0x0A a tak dále.

Celé to fun­guje na jed­no­du­chém před­po­kladu: Pokud jsou si dva hashe velice po­dobné, s nej­větší prav­dě­po­dob­ností se sho­dují v bitech jed­noho nebo více pruhů.2 Když chci najít všechny hashe po­dobné hashi A, vezmu jeho prv­ních 8 bitů, po­dí­vám se do od­po­ví­da­jí­cího bucketu prv­ního pruhu a spo­čí­tám po­dob­nost jen s těmito kan­di­dáty, pak vezmu dal­ších osm bitů a spo­čí­tám po­dob­nost s těmito kan­di­dáty. To udělám jednou pro každý pruh a mám vý­sledné po­dobné hashe. Pro­tože jde o prav­dě­po­dob­nostní metodu, může se stát, že ně­které sku­tečně po­dobné hashe to pře­skočí, pro­tože se vždy o jeden bit lišily ve všech pru­zích a proto skon­čily v od­liš­ných bucke­tech a vůbec nebyly vy­bráni jako kan­di­dáti. Pokud se za­jí­mám o velice po­dobné hashe, je tato šance velice malá. Pokud chci v takto vy­tvo­ře­ném LSH najít hashe lišící se v méně než 8 bitech, je ga­ran­to­váno, že všechny do­stanu, pro­tože se aspoň v jednom pruhu musí sho­do­vat.

S LSH, kdy mám 8 pruhů po 8 bitech, mi musím udělat jen 8/256 práce – 32x méně, pro­tože se musím po­dí­vat do 8 bucketů (jeden v každém pruhu) a spo­čí­tat po­dob­nosti ve všemi kan­di­dáty, kte­rých je 1/256. Pokud to ne­stačí, můžu tyto dva pa­ra­me­try zvolit podle toho, jak je třeba: když chci víc přes­nosti zvolím menší šířku pruhu (12x5 bitů), pokud chci více rych­losti, zvolím širší pruhy (6x10 bitů).

No a s tímto „zlep­šo­vá­kem“ dokážu bez vět­ších pro­blémů po­rov­nat ony dva mi­li­ony ob­rá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.


Pro­tože tuto tech­niku po­u­ží­vám na ně­ko­lika mís­tech (na­pří­klad pro de­tekci po­dob­ných článků na dev­blo­zích, tady, na téhle ma­lič­kosti a na mnoha dal­ších mís­tech), tak jsem si proto napsal vlastní kni­hovnu na­zva­nou pro­za­icky sket­ches, která ob­sa­huje im­ple­men­taci PHashe, skečů, LSH, ALS, FunkSVD nebo DBSCAN cluste­ro­vání a dal­ších ne­sou­vi­se­jí­cích věcí.


Dále k tématu:


Pozn:

  1. V Go se bo­hu­žel k popcnt bez ta­nečků v as­sem­bleru nedá dostat a tak je třeba si napsat uti­litu, která dělá to samé, ale po­tře­buje o něco víc in­strukcí.
  2. Prav­dě­po­dob­nost, že LSH odhalí dva kan­di­dáty je 1 – (1 – pn)b, kde p je po­dob­nost mezi dvěma kan­di­dáty, n šířka pruhu a b je počet pruhů. Pomocí tohoto vztahu můžu najít hod­noty np, které budou fun­go­vat pro po­ža­do­vaný práh po­dob­nosti.
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články