Trovare i pixel che rendono unica un'immagine all'interno di un elenco, puoi migliorare la forza bruta?

Question

Supponiamo che io ho una lista di stringhe dove ogni stringa è

• esattamente lungo 4 caratteri e
• unico all'interno della lista.

Per ciascuna di queste stringhe desidero identificare la posizione dei caratteri all'interno della stringa che rendono la stringa univoca.

Così, per una lista di tre stringhe

abcd 
abcc 
bbcb 

Per la prima stringa voglio identificare il personaggio in 4 ° posizione d dal d non compare nel 4 ° posizione in qualsiasi altra stringa.

Per la seconda stringa, desidero identificare il carattere in 4a posizione c.

Per la terza corda che voglio identificare il personaggio in 1a posizione b e il personaggio in 4a posizione, anche b.

Questo potrebbe essere sinteticamente rappresentato come

abcd -> ...d 
abcc -> ...c 
bbcb -> b..b 

Se si considera lo stesso problema, ma con una lista di numeri binari

0101 
0011 
1111 

Poi il risultato che voglio sarebbe

0101 -> ..0. 
0011 -> .0.. 
1111 -> 1... 

Restare con il tema binario Posso usare XOR per identificare quali bit sono univoci entro due numeri binari dal

0101^0011 = 0110 

che posso interpretare nel senso che in questo caso il 2 ° e 3 ° bit (lettura da sinistra a destra) sono uniche tra questi due numeri binari. Questa tecnica potrebbe essere una falsa pista a meno che in qualche modo non possa essere estesa alla lista più grande.

Un approccio a forza bruta consisterebbe nel controllare ciascuna stringa a turno e per ogni stringa per scorrere le sezioni verticali del resto delle stringhe nell'elenco.

Così, per la lista

abcd 
abcc 
bbcb 

Vorrei iniziare con

abcd 

e scorrere fette verticali di

abcc 
bbcb 

dove sarebbero queste fette verticali

a | b | c | c 
b | b | c | b 

o in forma di lista, "ab", "bb", "cc", "cb".

Questo si tradurrebbe in quattro confronti

a : ab -> . (a is not unique) 
b : bb -> . (b is not unique) 
c : cc -> . (c is not unique) 
d : cb -> d (d is unique) 

o conciso

abcd -> ...d 

Forse è un pio desiderio, ma ho la sensazione che ci dovrebbe essere una soluzione elegante e generale che si applicherebbe a un elenco arbitrariamente grande di stringhe (o numeri binari). Ma se c'è non sono ancora riuscito a vederlo.

Spero di utilizzare questo algoritmo per ricavare le firme minime da una raccolta di immagini uniche (bitmap) al fine di identificare in modo efficiente tali immagini in un momento futuro. Se l'efficienza futura non fosse una preoccupazione, userei un semplice hash di ogni immagine.

Riesci a migliorare la forza bruta?

Modifica L'approccio che sto riscaldando a sta costruendo una mappa di pixel per immagini

sprawl[Tuple<x=10, y=33,color=f1fefd>] => { 
    image17, 
    image23, 
    ... 
} 

sprawl[Tuple<x=10, y=34,color=f1fef0>] => { 
    image11 
    ... 
} 

e quindi utilizzando quella mappa per identificare il set minimo di pixel di firma per ogni immagine.

Se un pixel (identificato da x, y, colore) fa riferimento a una sola immagine, ho trovato una perfetta (minima) firma per quell'immagine.

È più complicato se un'immagine non ha pixel univoci, ma poiché so che tutte le immagini sono uniche nell'elenco dovrei essere in grado di combinare due o più riferimenti di pixel (ma il meno possibile) per dedurre l'immagine.

Aggiornamento

ho lavorato su un algoritmo per questo. Il mio problema è molto simile a this one e ho scritto il mio algoritmo come answer to that question. Questo aggiornamento è per segnalare l'attenzione di chiunque segua ancora (vedo cinque segnalibri). Sto lavorando su questo in isolamento, quindi qualsiasi feedback è benvenuto, anche se solo per osservare che non mi sono reso chiaro!

Answer 1

È possibile generare un array bidimensionale che conterrà il numero di volte in cui ciascun carattere appare in ciascuna posizione (0-3). Ad esempio, arr[1,3] conterrà il numero di volte in cui la cifra/carattere 1 viene visualizzata nell'ultima posizione.

Quindi per ogni stringa s, passare sopra tutti i caratteri nella stringa.Quelli che appaiono solo una volta in quella posizione secondo l'array sono i caratteri unici per quella stringa. In altre parole, se arr[s[i], i]==1 la stringa s è univoca nella posizione i.

Questo vi darà la soluzione in tempo lineare, mentre l'algoritmo che avete dato richiederà un tempo quadratico.

Answer 2

Se l'obiettivo è identificare le immagini in un secondo momento, è possibile creare un hash molto rapido dell'immagine selezionando punti predefiniti da utilizzare come pixel di identità.

per esempio, si potrebbe avere una struttura (di classe, struct, non importa in quale lingua) come segue:

structure ImageHash { 
    int x_pixels, y_pixels; 
    u_long hash; 
    void createHash(Image img) { 
     x_pixels = img.x_pixels; 
     y_pixels = img.y_pixels; 
     for(int i = 1; i < 5; i++) { 
      int x = x_pixels/i; 
      for(int j = 1; j < 5; j++) { 
       int y = y_pixels/j; 
       int r = img.getPixelRed(x,y); 
       int g = img.getPixelGreen(x,y); 
       int b = img.getPixelBlue(x,y); 
       hash = (hash * 31)^(r^g^b); 
      } 
     } 
    } 
} 

Questa sorta di "hash incompleta" vi permetterà di identificare possibili identità, e poi puoi fare il costoso confronto completo con parsimonia se necessario.

Espandi l'hash incompleto se necessario.

Answer 3

Questo problema può essere risolto da trie o albero di prefisso.

Vedi Trie - Wikipedia, the free encyclopedia

Per i 3 stringhe nel tuo esempio:

abcd 
abcc 
bbcb 

sarà trasformato in un albero trie (dove^indica la radice dell'albero):

^--a-b-c-d 
\  \ 
    \  c 
    \ 
    b-b-c-b 

Il percorso per il nodo in cui si dirama è il prefisso comune. Il nodo dopo l'ultimo punto di diramazione è ciò che rende unica una particolare stringa. In questo caso, sono d, c, b.

Suppongo che l'ordine della stringa non sia importante per te, che confronti tutte le stringhe per trovare l'unicità, non solo la stringa adiacente.

La complessità deve essere O (n x m). Ma questo sarà probabilmente influenzato dal dominio dei personaggi nella tua stringa.