Schlagen Sie einen Algorithmus für Farbmusterabgleich gegen eine große bekannte Menge

Question

Ich habe eine Anforderung, die eine Übereinstimmung mit einem Sample Set von Farbwerten mit einem bekannten Wertepaar, um entweder eine exakte Übereinstimmung oder Übereinstimmungen, die innerhalb einer akzeptablen Entfernung sind zu finden . Ich bin mir nicht ganz sicher, welcher Algorithmus dafür am besten geeignet wäre, und ich suche nach Vorschlägen.

Ich habe über eine SQL-Abfrage nachgedacht, da ich denke, dass dies ein direkter Ansatz wäre, aber idealerweise würde dies im Arbeitsspeicher auf dem Anwendungsserver oder sogar auf einer GPU für maximale Geschwindigkeit erfolgen.

Beispiel:

Lassen Sie uns sagen, dass wir einen Satz von drei RGB-Farbwerte, zwei Blues und eine Orange gegeben:

Probe Set:

Farbe 1: 81.177.206 (blau

)

Farbe 2: 36, 70, 224 (blau)

Farbe 3: 255, 132, 0 (orange)

Dieser Satz von 3 Farbwerten muss mit einem viel größeren Satz von Farbwerten verglichen werden, um zu sehen, ob dieser Satz mit exakt den gleichen RGB-Werten darin existiert jede der 3 Farben - oder - wenn irgendein Muster existiert, wo ein RGB-Wert der Farben um einen akzeptablen Grad variiert. Angenommen, eine der RGB-Komponenten kann bis zu drei Stellen höher oder niedriger sein.

Sagen wir unsere großen Satz von bekannten Farbwerte, die wir gegen sieht wie folgt suchen werden:

Bekannte Set:

  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] 

dieses Szenario gegeben, würden wir Null Matches finden, wenn wir Führen Sie unser Beispielset dagegen aus, da keine der bekannten Farben eine Farbe 1 aufweist, die irgendwo unseren Sample-Set-Werten entspricht. Lassen Sie sich jedoch eine andere Farbe auf den bekannten Satz hinzufügen, dass würde ein positives Spiel zurück:

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

Wenn Probe F mit diesen Werten in dem bekannten Satz existiert, würden wir einen positiven Erfolg bekommen, weil es die genaue RGB ist Werte als Farbe 1 in unserem Beispielsatz.Außerdem müssen wir einen unterschiedlichen Grad an Unterschieden in den RGB-Werten akzeptieren, so dass das folgende auch positive Treffer zurückgibt, da jeder RGB-Wert innerhalb von 3 Stellen von den Werten von Farbe 1 aus dem Probensatz liegt:

Positive Treffer: (erinnern Sie Farbe 1: 81.177.206)

Probe F: , 177.206 (roter Kanal 1 digit weg)

Probe F: 81, , (grüne und blaue Kanäle 2 Ziffern weg)

Probe F: 82.179.208 (alle drei Kanäle innerhalb von 3 Ziffern entfernt)

Wenn jedoch der Abstand zu groß ist, dann wäre eine Übereinstimmung nicht gefunden werden. Jede RGB-Komponente muss innerhalb von 3 Ziffern sein, um ein positives Ergebnis auszulösen. Also, wenn die Probe F wie folgt aus betrachtet, würden wir nicht ein positives Ergebnis erhalten, weil der Abstand zu groß ist:

Negative Treffer:

Probe F: , 177.206 (roter Kanal ist 4 Stellen entfernt)

Probe F: 81, 170 , 206 (grün Kanal 7 Stellen entfernt)

Probe F: 81.177, (blauer Kanal ist 6-stellig)

Bisher haben wir nur Farbe 1 aus dem Sample Set berücksichtigt. Die Anforderung erfordert jedoch die Berücksichtigung des gesamten Probensatzes. Wenn also keine positiven Übereinstimmungen für Farbe 1 gefunden werden können, nehmen wir an, dass es keine Übereinstimmung gibt, und berücksichtigen nicht die Farben 2 und 3 aus dem Stichprobensatz.

Wenn wir jedoch ein positives Ergebnis für Farbe 1 zu finden, die 80.177.206 lassen sagen, welche nur 1 Stelle aus ist im Roten Kanal 80 vs 81, dann wir weiterhin tun 2 Verarbeitung von Farbe, und wenn wir finden ein positives Spiel Dafür verarbeiten wir Farbe 3 und so weiter.

Was sind Ihre Vorschläge für den Algorithmus, der für dieses Problem am besten geeignet ist? Ich brauche etwas, das dem Known Set erlaubt, sehr groß zu skalieren, ohne zu viel Leistung zu haben. Es wird wahrscheinlich 1M + Samples im Bekannten Set im Maßstab geben.

Ich dachte über die Verwendung von Hashtables, eine pro Farbe, um das Bekannte Set zu konstruieren. Ich könnte also eine Übereinstimmung für Farbe 1 testen und, falls sie gefunden wird, die Hashtabelle für Farbe 2 testen und aufhören, wenn ich keine Treffer mehr finde. Wenn ich alle 3 Farben/Hashtables mit positiven Treffern durchhalte, hätte ich insgesamt eine positive Übereinstimmung, sonst würde ich nicht. Dieser Ansatz erlaubt jedoch nicht die Varianz, die in jedem der RGB-Kanäle für jede Farbe benötigt wird. Es würde zu viele Kombinationen geben, um die Erstellung von Hashtables zu ermöglichen.

Vielen Dank im Voraus und vielen Dank für das Lesen dieser weit unten!

Answer 1

Am Ende, nachdem er mit SQL und GPU-Programmierung (Cudafy) zu experimentieren, die schnellste, einfachste, und die meisten debuggable Lösung war, einfach durch die Daten mit Parallel.For() zu iterieren. Dieser Ansatz ergab 1,5 Millionen verarbeitete Samples (90M Gesamtbytes) in 18 ms.

Answer 2

Eine sortierte Liste behalten. Sortiere es dreimal mit einer stabilen Sortierung, zuerst mit B, dann mit G und dann mit R. Dies lässt es in RGB-Reihenfolge sortiert. Suchen Sie nach Ihrer Eingabe die Indizes für das erste und das letzte akzeptable R mit einer binären Suche.Suchen Sie dann diesen Bereich nach akzeptablen G-Werten und suchen Sie dann nach dem wieder reduzierten Bereich für B-Werte. Das Ganze sollte O (lgN) sein.

- Wenn ich etwas nicht vermisse, wird diese Lösung auf einen Satz von 3 Farben oder 10 Farben oder k Farben verallgemeinert. Generieren Sie ein Array von Indizes in Ihre Liste der Farbsätze. Zur Vorbereitung, sortiere die Indizes 3 * k mal wie oben. Um zu suchen, führen Sie 3 * k binäre Suchen in umgekehrter Reihenfolge durch.

(Dies setzt voraus, dass die Farben in Spalten fixiert sind. Wenn dies nicht der Fall ist, können Sie diese Methode verwenden, aber Ihre Indexliste geht in N * k Größe: Sie benötigt einen Eintrag für A1, A2, A3 Das Ende fügen Sie einen Scheck, dass Sie einen aus jeder Spalte gefunden haben.)

Answer 3

Basierend auf Ihrer Beschreibung in der Frage und der Konversation in den Kommentaren, warum nicht eine einfache gespeicherte Prozedur und einen benutzerdefinierten Typ verwenden? Bei richtiger Indizierung sollte es keine Performance-Probleme geben. Unter der Annahme, die Farbsets Sie mehrere Sätze von 3 Farben vergleichen wollen enthält, würde ich wahrscheinlich so etwas tun:

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