Frage Leistung von Delta E (CIE Lab) Berechnung und Sortierung in SQL


Ich habe eine Datenbanktabelle, in der jede Reihe eine Farbe ist. Mein Ziel: Bei einer Eingabefarbe den Abstand zu jeder Farbe in der DB-Tabelle berechnen und die Ergebnisse nach dieser Entfernung sortieren. Oder, als User Story angegeben: Wenn ich eine Farbe auswähle, möchte ich eine Liste der Farben sehen, die der von mir gewählten am ähnlichsten sind, wobei die besten Übereinstimmungen ganz oben in der Liste stehen.

Ich verstehe das, um dies zu tun, die verschiedenen Delta E (CIE Lab) Formeln sind die beste Wahl. Ich konnte keine nativen SQL-Implementierungen der Formeln finden, also schrieb ich meine eigenen SQL-Versionen von Delta E CIE 1976 und Delta E CIE 2000. Ich habe die Genauigkeit meiner SQL - Versionen der Formeln gegenüber den Ergebnissen der Python-Colormath Implementierungen.

Die 1976-Formel ist leicht zu schreiben, in SQL oder in jeder anderen Sprache, weil es eine einfache euklidische Abstandsberechnung ist. Es funktioniert sehr gut und schnell für Datasets jeder Größe (getestet in einer Farbtabelle mit 100.000 Zeilen und die Abfrage dauert weniger als 1 Sekunde).

Die Formel von 2000 ist dagegen sehr lang und komplex. Ich habe es in SQL implementiert, aber seine Leistung ist nicht groß: etwa 5 Sekunden für die Abfrage von 10.000 Zeilen und etwa 1 Minute für die Abfrage von 100.000 Zeilen.

Ich schrieb ein Beispiel-App heißt colesearchxt (in Python / Flask / Postgres), um mit meinen Implementierungen herumzuspielen (und ich Richten Sie eine Demo auf Heroku ein). Wenn Sie diese App ausprobieren, können Sie den Leistungsunterschied zwischen den Delta E-Abfragen 1976 und 2000 deutlich erkennen.

Dies ist das Schema für die Farbtabelle (für jede Farbe werden die jeweiligen RGB- und Lab-Darstellungen als drei numerische Werte gespeichert):

CREATE TABLE color (
    id integer NOT NULL,
    rgb_r integer,
    rgb_g integer,
    rgb_b integer,
    lab_l double precision,
    lab_a double precision,
    lab_b double precision
);

Dies sind einige Daten in der Tabelle (alle nur zufällige Farben, die von einem Skript in meiner App generiert werden):

INSERT INTO color (id, rgb_r, rgb_g, rgb_b, lab_l, lab_a, lab_b)
VALUES (902, 164, 214, 189, 81.6521019943304793,
        -21.2561872439361323, 7.08354581694699004);

INSERT INTO color (id, rgb_r, rgb_g, rgb_b, lab_l, lab_a, lab_b)
VALUES (903, 113, 229, 64, 81.7930860963098212,
        -60.5865728472875205, 66.4022741184551819);

INSERT INTO color (id, rgb_r, rgb_g, rgb_b, lab_l, lab_a, lab_b)
VALUES (904, 65, 86, 78, 34.6593864327796624,
        -9.95482220634028003, 2.02661293272071719);

...

Und das ist die Delta E CIE 2000 SQL-Funktion, die ich verwende:

CREATE OR REPLACE FUNCTION
DELTA_E_CIE2000(double precision, double precision,
                double precision, double precision,
                double precision, double precision,
                double precision, double precision,
                double precision)
RETURNS double precision
AS $$

WITH
    c AS (SELECT
            (CAST($1 AS VARCHAR) || ',' ||
            CAST($2 AS VARCHAR) || ',' ||
            CAST($3 AS VARCHAR) || ',' ||
            CAST($4 AS VARCHAR) || ',' ||
            CAST($5 AS VARCHAR) || ',' ||
            CAST($6 AS VARCHAR))
        AS lab_pair_str,
            (($1 + $4) /
                2.0)
        AS avg_lp,
            SQRT(
                POW($2, 2.0) +
                POW($3, 2.0))
        AS c1,
            SQRT(
                POW(($5), 2.0) +
                POW(($6), 2.0))
        AS c2),
    gs AS (SELECT
            c.lab_pair_str,
            (0.5 *
                (1.0 - SQRT(
                    POW(((c.c1 + c.c2) / 2.0), 7.0) / (
                        POW(((c.c1 + c.c2) / 2.0), 7.0) +
                        POW(25.0, 7.0)))))
        AS g
        FROM c
        WHERE c.lab_pair_str = (
            CAST($1 AS VARCHAR) || ',' ||
            CAST($2 AS VARCHAR) || ',' ||
            CAST($3 AS VARCHAR) || ',' ||
            CAST($4 AS VARCHAR) || ',' ||
            CAST($5 AS VARCHAR) || ',' ||
            CAST($6 AS VARCHAR))),
    ap AS (SELECT
            gs.lab_pair_str,
            ((1.0 + gs.g) * $2)
        AS a1p,
            ((1.0 + gs.g) * $5)
        AS a2p
        FROM gs
        WHERE gs.lab_pair_str = (
            CAST($1 AS VARCHAR) || ',' ||
            CAST($2 AS VARCHAR) || ',' ||
            CAST($3 AS VARCHAR) || ',' ||
            CAST($4 AS VARCHAR) || ',' ||
            CAST($5 AS VARCHAR) || ',' ||
            CAST($6 AS VARCHAR))),
    cphp AS (SELECT
            ap.lab_pair_str,
            SQRT(
                POW(ap.a1p, 2.0) +
                POW($3, 2.0))
        AS c1p,
            SQRT(
                POW(ap.a2p, 2.0) +
                POW($6, 2.0))
        AS c2p,
            (
                DEGREES(ATAN2($3, ap.a1p)) + (
                    CASE
                        WHEN DEGREES(ATAN2($3, ap.a1p)) < 0.0
                        THEN 360.0
                        ELSE 0.0
                        END))
        AS h1p,
            (
                DEGREES(ATAN2($6, ap.a2p)) + (
                    CASE
                        WHEN DEGREES(ATAN2($6, ap.a2p)) < 0.0
                        THEN 360.0
                        ELSE 0.0
                        END))
        AS h2p
        FROM ap
        WHERE ap.lab_pair_str = (
            CAST($1 AS VARCHAR) || ',' ||
            CAST($2 AS VARCHAR) || ',' ||
            CAST($3 AS VARCHAR) || ',' ||
            CAST($4 AS VARCHAR) || ',' ||
            CAST($5 AS VARCHAR) || ',' ||
            CAST($6 AS VARCHAR))),
    av AS (SELECT
            cphp.lab_pair_str,
            ((cphp.c1p + cphp.c2p) /
                2.0)
        AS avg_c1p_c2p,
            (((CASE
                WHEN (ABS(cphp.h1p - cphp.h2p) > 180.0)
                THEN 360.0
                ELSE 0.0
                END) +
              cphp.h1p +
              cphp.h2p) /
                2.0)
        AS avg_hp
        FROM cphp
        WHERE cphp.lab_pair_str = (
            CAST($1 AS VARCHAR) || ',' ||
            CAST($2 AS VARCHAR) || ',' ||
            CAST($3 AS VARCHAR) || ',' ||
            CAST($4 AS VARCHAR) || ',' ||
            CAST($5 AS VARCHAR) || ',' ||
            CAST($6 AS VARCHAR))),
    ts AS (SELECT
            av.lab_pair_str,
            (1.0 -
                0.17 * COS(RADIANS(av.avg_hp - 30.0)) +
                0.24 * COS(RADIANS(2.0 * av.avg_hp)) +
                0.32 * COS(RADIANS(3.0 * av.avg_hp + 6.0)) -
                0.2 * COS(RADIANS(4.0 * av.avg_hp - 63.0)))
        AS t,
            ((
                    (cphp.h2p - cphp.h1p) +
                    (CASE
                        WHEN (ABS(cphp.h2p - cphp.h1p) > 180.0)
                        THEN 360.0
                        ELSE 0.0
                        END))
                -
                (CASE
                    WHEN (cphp.h2p > cphp.h1p)
                    THEN 720.0
                    ELSE 0.0
                    END))
        AS delta_hlp
        FROM av
        INNER JOIN cphp
        ON av.lab_pair_str = cphp.lab_pair_str
        WHERE av.lab_pair_str = (
            CAST($1 AS VARCHAR) || ',' ||
            CAST($2 AS VARCHAR) || ',' ||
            CAST($3 AS VARCHAR) || ',' ||
            CAST($4 AS VARCHAR) || ',' ||
            CAST($5 AS VARCHAR) || ',' ||
            CAST($6 AS VARCHAR))),
    d AS (SELECT
            ts.lab_pair_str,
            ($4 - $1)
        AS delta_lp,
            (cphp.c2p - cphp.c1p)
        AS delta_cp,
            (2.0 * (
                SQRT(cphp.c2p * cphp.c1p) *
                SIN(RADIANS(ts.delta_hlp) / 2.0)))
        AS delta_hp,
            (1.0 + (
                (0.015 * POW(c.avg_lp - 50.0, 2.0)) /
                SQRT(20.0 + POW(c.avg_lp - 50.0, 2.0))))
        AS s_l,
            (1.0 + 0.045 * av.avg_c1p_c2p)
        AS s_c,
            (1.0 + 0.015 * av.avg_c1p_c2p * ts.t)
        AS s_h,
            (30.0 * EXP(-(POW(((av.avg_hp - 275.0) / 25.0), 2.0))))
        AS delta_ro,
            SQRT(
                (POW(av.avg_c1p_c2p, 7.0)) /
                (POW(av.avg_c1p_c2p, 7.0) + POW(25.0, 7.0)))
        AS r_c
        FROM ts
        INNER JOIN cphp
        ON ts.lab_pair_str = cphp.lab_pair_str
        INNER JOIN c
        ON ts.lab_pair_str = c.lab_pair_str
        INNER JOIN av
        ON ts.lab_pair_str = av.lab_pair_str
        WHERE ts.lab_pair_str = (
            CAST($1 AS VARCHAR) || ',' ||
            CAST($2 AS VARCHAR) || ',' ||
            CAST($3 AS VARCHAR) || ',' ||
            CAST($4 AS VARCHAR) || ',' ||
            CAST($5 AS VARCHAR) || ',' ||
            CAST($6 AS VARCHAR))),
    r AS (SELECT
            d.lab_pair_str,
            (-2.0 * d.r_c * SIN(2.0 * RADIANS(d.delta_ro)))
        AS r_t
        FROM d
        WHERE d.lab_pair_str = (
            CAST($1 AS VARCHAR) || ',' ||
            CAST($2 AS VARCHAR) || ',' ||
            CAST($3 AS VARCHAR) || ',' ||
            CAST($4 AS VARCHAR) || ',' ||
            CAST($5 AS VARCHAR) || ',' ||
            CAST($6 AS VARCHAR)))
SELECT
        SQRT(
            POW(d.delta_lp / (d.s_l * $7), 2.0) +
            POW(d.delta_cp / (d.s_c * $8), 2.0) +
            POW(d.delta_hp / (d.s_h * $9), 2.0) +
            r.r_t *
            (d.delta_cp / (d.s_c * $8)) *
            (d.delta_hp / (d.s_h * $9)))
    AS delta_e_cie2000
FROM          r
INNER JOIN    d
ON            r.lab_pair_str = d.lab_pair_str
WHERE         r.lab_pair_str = (
          CAST($1 AS VARCHAR) || ',' ||
          CAST($2 AS VARCHAR) || ',' ||
          CAST($3 AS VARCHAR) || ',' ||
          CAST($4 AS VARCHAR) || ',' ||
          CAST($5 AS VARCHAR) || ',' ||
          CAST($6 AS VARCHAR))

$$

LANGUAGE SQL
IMMUTABLE
RETURNS NULL ON NULL INPUT;

(Ich habe diese Funktion ursprünglich mit verschachtelten Unterabfragen von etwa 10 Ebenen geschrieben, aber ich habe sie dann neu geschrieben, um sie stattdessen zu verwenden WITH Statements, d. h. Postgres CTEs. Die neue Version ist viel besser lesbar und die Leistung ähnelt der alten Version. Du kannst sehen beide Versionen im Code.)

Nach dem Definieren der Funktion verwende ich sie in einer Abfrage wie folgt:

SELECT        c.rgb_r,
              c.rgb_g,
              c.rgb_b,
        DELTA_E_CIE2000(73.9206633504, -50.2996953437,
                        23.8259166281,
                        c.lab_l, c.lab_a, c.lab_b,
                        1.0, 1.0, 1.0)
    AS de2000
FROM          color c
ORDER BY      de2000
LIMIT         100;

Also, meine Frage: Gibt es irgendeinen Weg, wie ich die Leistung der. Verbessern könnte? DELTA_E_CIE2000 Funktion, um sie für nicht-triviale Datensätze in Echtzeit nutzbar zu machen? Oder ist es angesichts der Komplexität der Formel so schnell, wie es wird?

Aus den Tests, die ich in meiner Demo-App gemacht habe, würde ich sagen, dass für den Anwendungsfall einer einfachen Suche nach "ähnlichen Farben" auf einer Website der Unterschied in der Ergebnisgenauigkeit zwischen den Funktionen 1976 und 2000 tatsächlich vernachlässigbar ist. Das heißt, ich bin bereits zuversichtlich, dass für meine Bedürfnisse die Formel von 1976 "gut genug" ist. Allerdings liefert die 2000-Funktion etwas bessere Ergebnisse (abhängig davon, wo die Eingabefarbe im Lab-Bereich liegt), und ich bin wirklich neugierig, ob sie noch weiter beschleunigt werden könnte.


5
2017-08-04 00:31


Ursprung


Antworten:


Zwei Dinge: 1) Sie verwenden nicht die Datenbank in vollem Umfang und 2) Ihr Problem ist ein großartiges Beispiel für eine benutzerdefinierte PostgreSQL-Erweiterung. Hier ist der Grund.

Sie verwenden die Datenbank nur als Speicher und speichern Farben als Floats. Unabhängig von der Art der Abfrage muss die Datenbank in Ihrer aktuellen Konfiguration immer alle Werte prüfen (sequenzielle Suche durchführen). Dies bedeutet eine Menge IO und eine Menge Berechnung für einige zurückgegebene Matches. Sie versuchen, die nächsten N Farben zu finden, daher gibt es einige Möglichkeiten, wie Berechnungen für alle Daten vermieden werden können.

Einfache Verbesserung

Am einfachsten ist es, wenn Sie Ihre Berechnungen auf eine kleinere Datenmenge beschränken. Sie können davon ausgehen, dass der Unterschied größer ist, wenn die Komponenten mehr abweichen. Wenn Sie einen sicheren Unterschied zwischen den Komponenten finden können, wo die Ergebnisse immer unpassend sind, können Sie diese Farben vollständig ausschließen, indem Sie WHERE mit btree-Indizes verwenden. Aufgrund der Natur des L * a * b-Farbraums verschlechtert dies jedoch wahrscheinlich Ihre Ergebnisse.

Erstellen Sie zuerst die Indizes:

CREATE INDEX color_lab_l_btree ON color USING btree (lab_l);
CREATE INDEX color_lab_a_btree ON color USING btree (lab_a);
CREATE INDEX color_lab_b_btree ON color USING btree (lab_b);

Dann habe ich Ihre Abfrage so angepasst, dass sie eine WHERE-Klausel enthält, um nur die Farben zu filtern, wobei sich die einzelnen Komponenten um höchstens 20 unterscheiden.

Aktualisieren: Nach einem anderen Blick wird das Hinzufügen eines Limits von 20 sehr wahrscheinlich die Ergebnisse verschlechtern, da ich mindestens einen Punkt im Raum gefunden habe, wofür das gilt:

SELECT 
    c.rgb_r, c.rgb_g, c.rgb_b,
    DELTA_E_CIE2000(
        25.805780252087963, 53.33446637366859, -45.03961353720049, 
        c.lab_l, c.lab_a, c.lab_b,
        1.0, 1.0, 1.0) AS de2000
FROM color c 
WHERE 
    c.lab_l BETWEEN 25.805780252087963 - 20 AND 25.805780252087963 + 20 
    AND c.lab_a BETWEEN 53.33446637366859 - 20 AND 53.33446637366859 + 20 
    AND c.lab_b BETWEEN -45.03961353720049 - 20 AND -45.03961353720049 + 20 
ORDER BY de2000 ;

Ich habe den Tisch mit 100000 zufälligen Farben gefüllt und getestet:

Zeit ohne Indizes: 44006,851 ms

Zeit mit Indizes und Bereichsabfrage: 1293.092 ms

Sie können diese WHERE-Klausel hinzufügen delta_e_cie1976_query Auch bei meinen Zufallsdaten sinkt die Abfragezeit von ~ 110 ms auf ~ 22 ms.

BTW: Ich habe die Nummer 20 empirisch: Ich habe es mit 10 versucht, habe aber nur 380 Datensätze bekommen, was ein wenig zu niedrig scheint und vielleicht bessere Optionen ausschließt, da das Limit 100 ist. Mit 20 war der ganze Satz 2900 Zeilen und einer kann fair sein sicher, dass die engsten Übereinstimmungen da sein werden. Ich habe den DELTA_E_CIE2000- oder L * a * b * -Farbraum nicht im Detail untersucht, so dass der Schwellenwert möglicherweise entlang verschiedener Komponenten angepasst werden muss, damit er tatsächlich wahr ist, aber das Prinzip des Ausschlusses nicht interessanter Daten hält.

Schreiben Sie Delta E CIE 2000 in C um

Wie Sie bereits gesagt haben, ist Delta E CIE 2000 komplex und für die Implementierung in SQL ziemlich ungeeignet. Es verwendet derzeit ca. 0,4 ms pro Anruf auf meinem Laptop. Die Implementierung in C sollte dies erheblich beschleunigen. PostgreSQL weist den SQL-Funktionen Standardkosten wie 100 und C-Funktionen wie 1 zu. Ich schätze, das basiert auf echter Erfahrung.

Aktualisieren: Da dies auch einen meiner Jucklöcher zerkratzt, habe ich die Delta E-Funktionen aus dem Colormath-Modul in C als PostgreSQL-Erweiterung neu implementiert, verfügbar unter PGXN. Damit kann ich eine Beschleunigung von ca. 150x für CIE2000 sehen, wenn alle Datensätze aus der Tabelle mit 100k-Sätzen abgefragt werden.

Mit dieser C-Funktion erhalte ich Abfragezeiten zwischen 147 ms und 160 ms für 100k Farben. Mit extra WHERE beträgt die Abfragezeit ungefähr 20 ms, was für mich durchaus akzeptabel erscheint.

Beste, aber fortschrittliche Lösung

Da Ihr Problem jedoch die Suche nach N nächsten Nachbarn im 3-dimensionalen Raum ist, können Sie die K-Nächste-Nachbar-Indizierung verwenden, die sich in PostgreSQL befindet seit Version 9.1.

Damit das funktioniert, würden Sie L * a * b * -Komponenten in ein Würfel. Diese Erweiterung unterstützt noch nicht den Entfernungsoperator (Es ist in Arbeit), aber selbst wenn dies der Fall wäre, würde es Delta E-Abstände nicht unterstützen und Sie müssten es als C-Erweiterung neu implementieren.

Dies bedeutet die Implementierung der GiST-Index-Operator-Klasse (btree_gist PostgreSQL-Erweiterung in contrib tut dies), um Indexierung nach Delta E-Abständen zu unterstützen. Der gute Teil ist, Sie könnten dann verschiedene Operatoren für verschiedene Versionen von Delta E verwenden, z. <-> für Delta E CIE 2000 und <#> für Delta E CIE 1976 und Abfragen wären wirklich sehr schnell für kleine LIMIT auch mit Delta E CIE 2000.

Am Ende kann es darauf ankommen, was Ihre (geschäftlichen) Anforderungen und Einschränkungen sind.


6
2017-10-20 22:21