Qual è il modo migliore per ottenere l'hash di una QPixmap?

Question

Sto sviluppando un'applicazione grafica usando Qt 4.5 e inserendo immagini in QPixmapCache, volevo ottimizzarlo in modo che se un utente inserisce un'immagine che è già nella cache, la utilizzerà.

In questo momento ogni immagine ha un ID unico che aiuta a ottimizzarsi sugli eventi di disegno. Tuttavia mi rendo conto che se potessi calcolare un hash dell'immagine potrei cercare nella cache per vedere se esiste già e usarlo (sarebbe utile di più per gli oggetti duplicati, ovviamente).

Il mio problema è che se si tratta di una QPixmap di grandi dimensioni, un calcolo hash rallenta le cose o esiste un modo più rapido?

Answer 1

Un paio di commenti su questo:

1. Se stai per generare una chiave hash / cache di una pixmap, potresti voler saltare QPixmapCache e utilizzare QCache direttamente . Ciò eliminerebbe un certo sovraccarico dell'uso di QStrings come chiavi (a meno che non si desideri utilizzare anche il percorso del file per individuare gli elementi)

2. A partire da Qt4.4, QPixmap ha un "hash" " valore associato (vedi QPixmap :: cacheKey () ). La documentazione afferma che "gli oggetti QPixmap distinti possono avere la stessa chiave di cache solo se si riferiscono allo stesso contenuto." Tuttavia, poiché Qt utilizza la copia di dati condivisi, ciò può applicarsi solo alle pixmap copiate e non a due distinte pixmap caricate dalla stessa immagine. Un po 'di test ti direbbe se funziona, e se lo fa, ti permetterebbe di ottenere facilmente un valore di hash.

3. Se vuoi davvero fare una cache buona e abbastanza veloce con la rimozione di duplicati, potresti voler esaminare la tua struttura di dati che ordina in base a dimensioni, profondità di colore, tipi di immagine e cose del genere. Quindi dovrai solo eseguire l'hashing dei dati dell'immagine effettiva dopo aver trovato lo stesso tipo di immagine con le stesse dimensioni, profondità di bit, ecc. Naturalmente, se i tuoi utenti aprono generalmente molte immagini con quelle cose uguali, non non aiuta affatto.

4. Prestazioni: non dimenticare le cose di benchmarking Qt aggiunte in 4.5, che ti permetterebbero di confrontare le tue varie idee di hashing e vedere quale funziona più velocemente. Non l'ho ancora verificato, ma sembra abbastanza pulito.

Answer 2

Nel caso in cui qualcuno dovesse riscontrare questo problema (e non abbia una terribile esperienza con le cose di hashing, in particolare qualcosa come un'immagine), ecco una soluzione MOLTO semplice che ho usato per eseguire l'hashing di QPixmaps e inserirle in una tabella di ricerca per un confronto successivo :

qint32 HashClass::hashPixmap(QPixmap pix)
{
    QImage image = pix.toImage();
    qint32 hash = 0;

    for(int y = 0; y < image.height(); y++)
    {
        for(int x = 0; x < image.width(); x++)
        {
            QRgb pixel = image.pixel(x,y);

            hash += pixel;
            hash += (hash << 10);
            hash ^= (hash >> 6);
        }
    }

    return hash;
}

Ecco la funzione di hashing stessa (puoi avere l'hash in un qint64 se desideri meno collisioni). Come puoi vedere, converto la pixmap in una QImage, ne percorro semplicemente le dimensioni ed eseguo un hash alla volta molto semplice su ogni pixel e restituisco il risultato finale. Esistono molti modi per migliorare questa implementazione (vedere le altre risposte a questa domanda), ma questa è l'essenza di base di ciò che deve essere fatto.

L'OP ha menzionato come avrebbe usato questa funzione di hashing per costruire una tabella di ricerca per confrontare successivamente le immagini. Ciò richiederebbe una funzione di inizializzazione della ricerca molto semplice - qualcosa del genere:

void HashClass::initializeImageLookupTable()
{
    imageTable.insert(hashPixmap(QPixmap(":/Image_Path1.png")), "ImageKey1");
    imageTable.insert(hashPixmap(QPixmap(":/Image_Path2.png")), "ImageKey2");
    imageTable.insert(hashPixmap(QPixmap(":/Image_Path3.png")), "ImageKey2");
// Etc...
}

Sto usando una QMap qui chiamata imageTable che dovrebbe essere dichiarata nella classe in quanto tale:

QMap<qint32, QString> imageTable;

Quindi, infine, quando vuoi confrontare un'immagine con le immagini nella tua tabella di ricerca (es .: " quale immagine, tra le immagini che so che può essere, è questa particolare immagine? "), sei solo chiama la funzione di hashing sull'immagine (che presumo sarà anche una QPixmap) e il valore di ritorno QString ti permetterà di capirlo. Qualcosa del genere funzionerebbe:

void HashClass::compareImage(const QPixmap& pixmap)
{
    QString value = imageTable[hashPixmap(pixmap)];
    // Do whatever needs to be done with the QString value and pixmap after this point.
}

Questo è tutto. Spero che questo aiuti qualcuno - mi avrebbe risparmiato un po 'di tempo, anche se ero felice di avere l'esperienza di capirlo.

Answer 3

I calcoli dell'hash dovrebbero essere piuttosto rapidi (da qualche parte sopra i 100 MB / s se non sono coinvolti I / O del disco) a seconda dell'algoritmo che si utilizza. Prima dell'hashing, potresti anche fare alcuni test rapidi per selezionare i potenziali candidati, ad es. le immagini devono avere la stessa larghezza e altezza, altrimenti è inutile confrontare i loro valori di hash.

Naturalmente, dovresti anche mantenere i valori di hash per le immagini inserite in modo da dover calcolare un hash solo per le nuove immagini e non dovrai calcolarlo di nuovo per le immagini memorizzate nella cache.

Se le immagini sono abbastanza diverse, forse sarebbe sufficiente non eseguire l'hashing dell'intera immagine ma di una miniatura più piccola o di una parte dell'immagine (ad esempio la prima e le ultime 10 righe), questo sarà più veloce, ma porterà a più le collisioni.

Answer 4

Suppongo che tu stia parlando di calcolare effettivamente un hash sui dati dell'immagine piuttosto che ottenere l'ID univoco generato da QT.
A seconda delle immagini, probabilmente non è necessario andare sull'intera immagine per calcolare un hash. Forse leggi solo i primi 10 pixel? prima riga di scansione?
Forse una selezione pseudo casuale di pixel dall'intera immagine? (con un seme noto in modo da poter ripetere la sequenza) Non dimenticare di aggiungere anche la dimensione dell'immagine all'hash.