Suggerisci un algoritmo per la corrispondenza del modello di colore con un set noto di grandi dimensioni

Question

Ho un requisito che richiama l'abbinamento di un set di campioni di valori di colore con un set di valori noto per trovare una corrispondenza esatta o corrispondenze entro una distanza accettabile . Non sono del tutto sicuro di quale algoritmo sarebbe più adatto per questo e sto cercando dei suggerimenti.

Ho pensato di utilizzare una query SQL perché penso che sarebbe un approccio semplice, tuttavia, idealmente questo sarebbe fatto in memoria sul server delle applicazioni o anche su una GPU per la massima velocità.

Esempio:

Diciamo ci viene data una serie di tre valori di colore RGB, due azzurri e un arancio:

Fascicolo di prova:

Colore 1: 81.177.206 (blu)

Colore 2: 36, 70, 224 (blu)

Colore 3: 255, 132, 0 (arancione)

Questo set di 3 valori di colore deve essere confrontato con un set di colori molto più ampio per vedere se questo set esiste al suo interno, con gli stessi esatti valori RGB per ciascuno dei 3 colori - o - se esiste un motivo qualsiasi in cui un valore RGB dei colori varia in misura accettabile. Supponiamo che uno qualsiasi dei componenti RGB possa avere un valore superiore o inferiore a 3 cifre.

Diciamo che il nostro grande insieme di valori di colore noto che Cercheremo contro si presenta così:

serie nota:

  Color 1   Color 2  Color 3 
Sample A: [25, 25, 25], [10, 10, 10], [100, 100, 100] 

Sample B: [125, 125, 125], [10, 10, 10], [200, 200, 200] 

Sample C: [13, 87, 255], [10, 10, 10], [100, 100, 100] 

Sample D: [67, 111, 0], [10, 10, 10], [200, 200, 200] 

Sample E: [255, 255, 255], [10, 10, 10], [100, 100, 100] 

Dato questo scenario, si potrebbe trovare a zero corrispondenze quando abbiamo esegui il nostro sample set contro di esso, perché nessuno dei colori conosciuti ha un Colore 1 che è ovunque vicino ai nostri valori di campionamento. Tuttavia, aggiungiamo un altro colore per il Set noto che sarebbe restituire una corrispondenza positiva:

Sample F: [81,177,206], [36, 70, 224], [255, 132, 0] 

Se Esempio F esisteva con questi valori nella serie nota, ci sarebbe un colpo positiva, perché è l'esatto RGB valori come Colore 1 nel nostro set di campioni.Inoltre, abbiamo bisogno di accettare un grado variabile di differenze nei valori RGB, quindi il seguente sarebbe anche tornare colpi positivi perché ogni valore RGB si trova a 3 cifre da valori di colore 1 del set di prova: colpisce

Positivo: (ricordate colore 1 è: 81.177.206)

Esempio F: , 177.206 (canale rosso è 1 cifra distanza)

Esempio F: 81, , (verde e blu canali 2 cifre lontane)

Esempio F: 82.179.208 (tutti e tre i canali all'interno 3 cifre di distanza)

Tuttavia, se la distanza è troppo grande, poi un match non sarebbe trovata. Qualsiasi componente RGB deve essere compreso tra 3 cifre per attivare un risultato positivo. Quindi, se il campione F sembrava come il seguente, avremmo non ottenere un risultato positivo perché la distanza è troppo grande:

colpi negativi:

Esempio F: , 177.206 (canale rosso è 4 cifre distanza)

Esempio F: 81, , 206 (canale verde è 7 cifre distanza)

Esempio F: 81.177, (il canale blu è a 6 cifre di distanza)

Finora abbiamo preso in considerazione solo il Colore 1 del Set di campioni. Tuttavia, il requisito richiede di prendere in considerazione l'intero set di campioni. Quindi se non è possibile trovare corrispondenze positive per Colore 1, allora non assumiamo alcuna corrispondenza e non consideriamo i colori 2 e 3 dal set di campioni.

Tuttavia, se troviamo un risultato positivo per Color 1, diciamo 80.177.206 che è appena 1 cifra fuori nel canale Rosso 80 vs 81, poi abbiamo facciamo continuare l'elaborazione di colore 2, e se troviamo una corrispondenza positiva per questo quindi elaboriamo Color 3 e così via.

Quali sono i tuoi suggerimenti per l'algoritmo più adatto a questo problema? Ho bisogno di qualcosa che permetta al set conosciuto di ridimensionarsi molto senza troppe prestazioni. Probabilmente ci saranno 1M + campioni nel Set noto su scala.

Ho pensato di utilizzare gli hashtables, uno per colore per creare il set noto. Così ho potuto testare una partita su Color 1 e, se trovato, testare l'hashtable per Color 2 e fermarmi quando non trovo più hit. Se avessi superato tutti i 3 colori/hashtables con colpi positivi, avrei una corrispondenza complessivamente positiva, altrimenti non lo farei. Tuttavia, questo approccio non consente la varianza necessaria in ciascuno dei canali RGB per ciascun colore. Ci sarebbero troppe combinazioni per consentire la costruzione di hashtables per contenere tutto.

Grazie in anticipo e grazie per aver letto fino in fondo!

Answer 1

Alla fine, dopo aver sperimentato con SQL e programmazione GPU (Cudafy), il più veloce, più facile, e la soluzione più debugable era semplicemente scorrere i dati usando Parallel.For(). Questo approccio ha prodotto 1,5 milioni di campioni elaborati (90 milioni di byte totali) in 18 ms.

Answer 2

Mantiene una lista ordinata. Ordinalo tre volte con un ordinamento stabile, prima con B, poi con G, poi con R. Questo lo lascia in ordine RGB. Dato il tuo input, trova gli indici per la prima e l'ultima R accettabili con una ricerca binaria.Quindi cerca quell'intervallo per G accettabili, quindi cerca l'intervallo nuovamente ridotto per B's. L'intera cosa dovrebbe essere O (lgN).

- A meno che non manchi qualcosa, questa soluzione viene generalizzata per abbinare un set di 3 colori, o 10 colori o k colori. Genera una serie di indici nel tuo elenco di set di colori. Per preparare, stabile ordina gli indici 3 * k volte come sopra. Per cercare, fai 3 * k ricerche binarie nell'ordine opposto.

(Ciò presuppone che i colori siano fissi in colonne. Se non lo sono, è ancora possibile utilizzare questo metodo, ma l'elenco di indici va a N * k size: ha bisogno di una voce per A1, A2, A3. Alla fine aggiungi un segno di spunta per ogni colonna.)

Answer 3

In base alla tua descrizione nella domanda e alla conversazione nei commenti, perché non utilizzare una semplice stored procedure e un tipo definito dall'utente? con indicizzazione corretta non dovrebbero esserci problemi di prestazioni. Supponendo che i set di colori che si desidera confrontare contiene più set di 3 colori, avrei probabilmente fare qualcosa di simile:

CREATE TABLE KnownColorSets (
    KC_1_R tinyint NOT NULL, 
    KC_1_G tinyint NOT NULL, 
    KC_1_B tinyint NOT NULL, 
    KC_2_R tinyint NOT NULL, 
    KC_2_G tinyint NOT NULL, 
    KC_2_B tinyint NOT NULL, 
    KC_3_R tinyint NOT NULL, 
    KC_3_G tinyint NOT NULL, 
    KC_3_B tinyint NOT NULL 
) 

CREATE TYPE CompareColorSet As TABLE 
(
    CC_1_R tinyint NOT NULL, 
    CC_1_G tinyint NOT NULL, 
    CC_1_B tinyint NOT NULL, 
    CC_2_R tinyint NOT NULL, 
    CC_2_G tinyint NOT NULL, 
    CC_2_B tinyint NOT NULL, 
    CC_3_R tinyint NOT NULL, 
    CC_3_G tinyint NOT NULL, 
    CC_3_B tinyint NOT NULL 
) 



CREATE PROCEDURE stpCompareColorSets 
(
    @Exists bit output, 
    @CompareColorSet dbo.CompareColorSet readonly 
) 
AS 
    DECLARE @MaxDiviation tinyint = 3 -- This may be taken from a General params table or added as a parameter to the stored procedure 
    SET @Exists = 0 
    IF EXISTS (
    SELECT 1 
    FROM KnownColorSets KC INNER JOIN 
    @CompareColorSet CC ON(
     KC_1_R BETWEEN CC_1_R - @MaxDiviation AND CC_1_R - @MaxDiviation 
     AND KC_1_G BETWEEN CC_1_G - @MaxDiviation AND CC_1_G - @MaxDiviation 
     AND KC_1_B BETWEEN CC_1_B - @MaxDiviation AND CC_1_B - @MaxDiviation 

     AND KC_2_R BETWEEN CC_2_R - @MaxDiviation AND CC_2_R - @MaxDiviation 
     AND KC_2_G BETWEEN CC_2_G - @MaxDiviation AND CC_2_G - @MaxDiviation 
     AND KC_2_B BETWEEN CC_2_B - @MaxDiviation AND CC_2_B - @MaxDiviation 

     AND KC_3_R BETWEEN CC_3_R - @MaxDiviation AND CC_3_R - @MaxDiviation 
     AND KC_3_G BETWEEN CC_3_G - @MaxDiviation AND CC_3_G - @MaxDiviation 
     AND KC_3_B BETWEEN CC_3_B - @MaxDiviation AND CC_3_B - @MaxDiviation 
    ) 
) 
    SET @Exists = 1