Libpuzzle Indicizzazione milioni di immagini?

Question

è relativo alla libray libpuzzle per php (http://libpuzzle.pureftpd.org/project/libpuzzle) di Mr. Frank Denis. Sto cercando di capire come indicizzare e memorizzare i dati nel mio database mysql. La generazione del vettore non è assolutamente un problema.

Esempio:

# Compute signatures for two images 
$cvec1 = puzzle_fill_cvec_from_file('img1.jpg'); 
$cvec2 = puzzle_fill_cvec_from_file('img2.jpg'); 

# Compute the distance between both signatures 
$d = puzzle_vector_normalized_distance($cvec1, $cvec2); 

# Are pictures similar? 
if ($d < PUZZLE_CVEC_SIMILARITY_LOWER_THRESHOLD) { 
    echo "Pictures are looking similar\n"; 
} else { 
    echo "Pictures are different, distance=$d\n"; 
} 

Questo è tutto chiaro per me - ma ora come faccio a lavorare quando ho una grande quantità di immagini> 1.000.000? Calcolo il vettore e lo memorizzo con il nome file nel database? Come trovare le immagini simili ora? Se immagazzino ogni vettore nel mysql devo aprire ogni record e calcolare la distanza con la funzione puzzle_vector_normalized_distance. Che le procedure prende un sacco di tempo (aperto ogni voce del database - ha messo gettare la funzione, ...)

ho letto il readme dal libaray di puzzle lib e trovato il seguente:

Funzionerà con un database che ha milioni di immagini?

Una tipica firma di immagine richiede solo 182 byte, utilizzando le funzioni di compressione/decompressione integrate .

firme simili condividono "parole" identiche, vale a dire. sequenze identiche di valori nelle stesse posizioni. Usando gli indici composti (parola + posizione), l'insieme di possibili vettori simili è drammaticamente ridotto a e, nella maggior parte dei casi, non viene calcolata la distanza vettoriale necessaria a .

L'indicizzazione tramite parole e posizioni facilita inoltre la suddivisione dei dati in più tabelle e server.

Quindi sì, la libreria Puzzle non è certo incompatibile con i progetti che devono indicizzare milioni di immagini.

Inoltre ho trovato questa descrizione sul indexing:

------------------------ INDEXING ----- -------------------

Come trovare rapidamente immagini simili, se sono milioni di record?

La carta originale ha una risposta semplice ma efficace.

Taglia il vettore in parole a lunghezza fissa. Per esempio, prendiamo in considerazione il seguente vettore:

[abcdefghijklmnopqrstu vwxyz]

Con una lunghezza di parola (K) di 10, è possibile ottenere le seguenti parole:

[abcdefghij] trovato alla posizione 0 [bcdefghijk] trovato in posizione 1 [cdefghijkl] trovato in posizione 2 ecc fino alla posizione N-1

Poi, indicizzare il vettore con un indice composto di (parola + posizione).

Anche con milioni di immagini, K = 10 e N = 100 dovrebbero essere sufficienti per avere pochissime voci che condividono lo stesso indice.

Ecco uno schema di database di esempio molto semplice:

+-----------------------------+ 
| signatures | 
+-----------------------------+ 
| sig_id | signature | pic_id | 
+--------+-----------+--------+ 

+--------------------------+ 
| words | 
+--------------------------+ 
| pos_and_word | fk_sig_id | 
+--------------+-----------+ 

io consiglierei scissione almeno tabella "parole" in molteplici tavoli e/o server.

Per impostazione predefinita (lambas = 9) le firme sono lunghe 544 byte. Per salvare lo spazio di archiviazione , è possibile comprimerli a 1/3 delle loro dimensioni originali tramite la funzione puzzle_compress_cvec(). Prima dell'uso, devono essere decompressi con puzzle_uncompress_cvec().

Penso che la compressione sia la causa sbagliata, quindi devo decomprimere ogni vettore prima di confrontarlo.

La mia domanda è ora - qual è il modo di gestire milioni di immagini e come confrontarle in modo rapido ed efficiente. Non capisco come il "taglio del vettore" dovrebbe aiutarmi con il mio problema.

Mille grazie - forse posso trovare qualcuno qui che sta lavorando con libaray libpuzzle.

Cheers.

Answer 1

Ho sperimentato con libpuzzle in precedenza - sono arrivato fino a te. Non ha davvero inizio su una corretta implementazione. Era anche poco chiaro come esattamente farlo. (E abbandonato il progetto per mancanza di tempo - così abbiamo mangiato veramente ostiniamo con esso)

In ogni caso, guardando ora, cercherà di offrire la mia comprensione - forse tra di noi siamo in grado di lavorare fuori :)

query utilizzano un 2 processo palco -

1. prima si utilizza il parole tavolo.
   1. prendere l'immagine di "riferimento" e calcolare la sua firma.
   2. funzionato sue parole componenti,
   3. consultare il parole tabella per trovare tutte le possibili corrispondenze. Questo può utilizzare gli "indici" dei motori di database per query efficienti.
   4. compila un elenco di tutti i sig_id. (Otterrà alcuni duplicati in 3.)
2. quindi consultare le firme tavolo
   1. prelevare e decomprimere tutto il possibile dal firme (perché avete una lista pre-filtrato il numero dovrebbe essere relativamente piccolo)
   2. utilizzare puzzle_vector_normalized_distance per calcolare una distanza effettiva.
   3. ordinare e classificare i risultati come richiesto

(cioè di utilizzare solo la compressione sulle firme tavolo. Parole rimane compresso, in modo possono eseguire query veloci su di esso)

Il parole tabella è una forma di indice invertito. Infatti ho in mente di usare https://stackoverflow.com/questions/tagged/sphinx invece della tabella del database delle parole, perché è stato progettato specificamente come indice invertito molto veloce.

... in teoria ...

Answer 2

Quindi, diamo uno sguardo alla esempio che danno e cercare di espandersi.

Supponiamo di avere una tabella che memorizza le informazioni relative a ciascuna immagine (percorso, nome, descrizione, ecc.). In tale tabella, includerai un campo per la firma compressa, calcolato e archiviato all'inizio della compilazione del database. Definiamo quel tavolo così:

CREATE TABLE images (
    image_id INTEGER NOT NULL PRIMARY KEY, 
    name TEXT, 
    description TEXT, 
    file_path TEXT NOT NULL, 
    url_path TEXT NOT NULL, 
    signature TEXT NOT NULL 
); 

Quando inizialmente calcolare la firma, si sta anche andando a calcolare un numero di parole dalla firma:

// this will be run once for each image: 
$cvec = puzzle_fill_cvec_from_file('img1.jpg'); 
$words = array(); 
$wordlen = 10; // this is $k from the example 
$wordcnt = 100; // this is $n from the example 
for ($i=0; $i<min($wordcnt, strlen($cvec)-$wordlen+1); $i++) { 
    $words[] = substr($cvec, $i, $wordlen); 
} 

Ora potete mettere queste parole in un tavolo, definito così:

CREATE TABLE img_sig_words (
    image_id INTEGER NOT NULL, 
    sig_word TEXT NOT NULL, 
    FOREIGN KEY (image_id) REFERENCES images (image_id), 
    INDEX (image_id, sig_word) 
); 

Ora si inserisce in quella tabella, anteponendo l'indice posizione in cui è stata trovata la parola, in modo da sapere quando una parola corrisponde a quello che ha trovato nella stessa plac e nella firma:

// the signature, along with all other data, has already been inserted into the images 
// table, and $image_id has been populated with the resulting primary key 
foreach ($words as $index => $word) { 
    $sig_word = $index.'__'.$word; 
    $dbobj->query("INSERT INTO img_sig_words (image_id, sig_word) VALUES ($image_id, 
     '$sig_word')"); // figure a suitably defined db abstraction layer... 
} 

I Suoi dati perciò inizializzate, si può afferrare le immagini con corrispondenti parole in modo relativamente semplice:

// $image_id is set to the base image that you are trying to find matches to 
$dbobj->query("SELECT i.*, COUNT(isw.sig_word) as strength FROM images i JOIN img_sig_words 
    isw ON i.image_id = isw.image_id JOIN img_sig_words isw_search ON isw.sig_word = 
    isw_search.sig_word AND isw.image_id != isw_search.image_id WHERE 
    isw_search.image_id = $image_id GROUP BY i.image_id, i.name, i.description, 
    i.file_path, i.url_path, i.signature ORDER BY strength DESC"); 

si potrebbe migliorare la query con l'aggiunta di una clausola HAVING che richiede un minimo strength, riducendo ulteriormente il set di corrispondenza.

Non garantisco che questa sia la configurazione più efficiente, ma dovrebbe essere approssimativamente funzionale per realizzare ciò che stai cercando.

Fondamentalmente, suddividere e memorizzare le parole in questo modo consente di eseguire una verifica della distanza approssimativa senza dover eseguire una funzione specializzata sulle firme.

Answer 3

Ho realizzato un progetto DEMO libpuzzle su GitHub: https://github.com/alsotang/libpuzzle_demo.

Il progetto utilizza il modo in cui Jason ha proposto sopra.

Lo schema del database mostra su: https://github.com/alsotang/libpuzzle_demo/blob/master/schema.sql

---

e io vi darò maggiori informazioni sulla firma di libpuzzle.

Ora abbiamo le due immagini, e mi permetta di calcolare la loro firma.

le linee dispari è per un'immagine 1 (quella di sinistra), e le linee pari è per un'immagine 2.

Si possono trovare che nella maggior parte dei casi, il numero nella stessa posizione è lo stesso.

....

---

il mio inglese è così povero, così non posso esprimere la mia mente continua ... Penso che chiunque Chi vuole milioni indice delle immagini dovrebbe ispezionare il mio repo GitHub di DEMO libpuzzle ..

Answer 4

Sto anche lavorando su libpuzzle in php e sto avendo qualche dubbio su come generare le parole dalle firme dell'immagine. Jasons risposta di cui sopra sembra giusto ma ho un problema con questa parte:

// this will be run once for each image: 
 
$cvec = puzzle_fill_cvec_from_file('img1.jpg'); 
 
$words = array(); 
 
$wordlen = 10; // this is $k from the example 
 
$wordcnt = 100; // this is $n from the example 
 
for ($i=0; $i<min($wordcnt, strlen($cvec)-$wordlen+1); $i++) { 
 
    $words[] = substr($cvec, $i, $wordlen); 
 
}

Il vettore di firma è lunga 544 lettere e con la creazione di sopra delle parole siamo sempre utilizzando solo il primo 110 lettere di esso. Significa che stiamo indicizzando per conto del terzo superiore del contenuto dell'immagine, se ho capito bene.

Se andate a leggere l'articolo originale (An Image Signature for any kind of Image) su cui si basa sulla libpuzzle, spiegano che le parole devono essere generati "... forse non contigui e sovrapposti". Non sono sicuro se significano non contigui e non sovrapposti, o non contigui e sovrapposti ... Ma se significano non sovrapposti, suppongo che le parole debbano essere sparse per tutto il vettore della firma. Avrebbe anche più senso, poiché il vettore viene creato valutando le regioni dell'immagine da sinistra a destra, dall'alto verso il basso. E diffondere parole attraverso l'intero vettore significherebbe che stai considerando l'intera immagine piuttosto solo la parte superiore di essa (se generi tutte le parole dall'inizio del vettore).

Mi piacerebbe sentire come voi ragazzi capite questo.