Výkon výpočtu a třídění Delta E (CIE Lab) v SQL

Dvě věci:1) nepoužíváte databázi v plném rozsahu a 2) váš problém je skvělým příkladem pro vlastní rozšíření PostgreSQL. Zde je důvod.

Databázi používáte pouze jako úložiště, barvy ukládáte jako plovoucí. Ve vaší aktuální konfiguraci, bez ohledu na typ dotazu, bude muset databáze vždy zkontrolovat všechny hodnoty (provést sekvenční skenování). To znamená hodně IO a hodně kalkulace pro málo vrácených zápasů. Pokoušíte se najít nejbližších N barev, takže existuje několik možností, jak se vyhnout provádění výpočtů na všech datech.

Jednoduché vylepšení

Nejjednodušší je omezit výpočty na menší podmnožinu dat. Můžete předpokládat, že rozdíl bude větší, pokud se komponenty budou lišit více. Pokud můžete najít bezpečný rozdíl mezi komponentami, kde jsou výsledky vždy nevhodné, můžete tyto barvy zcela vyloučit pomocí rozsahu WHERE s indexy btree. Vzhledem k povaze barevného prostoru L*a*b to však pravděpodobně zhorší vaše výsledky.

Nejprve vytvořte indexy:

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);

Poté jsem váš dotaz upravil tak, aby obsahoval klauzuli WHERE pro filtrování pouze barev, kde se kterákoli z komponent liší nejvýše o 20.

Aktualizace: Po dalším pohledu přidání limitu 20 velmi pravděpodobně zhorší výsledky, protože jsem našel alespoň jeden bod v prostoru, pro který to platí.:

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 ;

Naplnil jsem tabulku 100 000 náhodnými barvami pomocí vašeho skriptu a otestoval:

Čas bez indexů:44006,851 ms

Čas s indexy a dotazem na rozsah:1293 092 ms

Tuto klauzuli WHERE můžete přidat do delta_e_cie1976_query také u mých náhodných dat zkrátí dobu dotazu z ~110 ms na ~22 ms.

BTW:Empiricky jsem dostal číslo 20:Zkoušel jsem to s 10, ale dostal jsem jen 380 záznamů, což se zdá trochu málo a mohlo by to vyloučit některé lepší možnosti, protože limit je 100. S 20 byla celá sada 2900 řádků a jeden může být docela jisté, že tam budou nejbližší zápasy. Nestudoval jsem podrobně barevný prostor DELTA_E_CIE2000 nebo L*a*b*, takže práh může vyžadovat úpravu podél různých složek, aby to skutečně bylo pravdivé, ale princip vyloučení nezajímavých dat platí.

Přepište Delta E CIE 2000 v C

Jak jste již řekli, Delta E CIE 2000 je složitý a poměrně nevhodný pro implementaci v SQL. V současné době používá na mém notebooku asi 0,4 ms na hovor. Jeho implementace v C by to měla výrazně urychlit. PostgreSQL přiřadí výchozí cenu funkcím SQL jako 100 a funkcím C jako 1. Hádám, že je to založeno na skutečných zkušenostech.

Aktualizace: Protože to také poškrábalo jedno z mých svědění, znovu jsem implementoval funkce Delta E z modulu colormath v C jako rozšíření PostgreSQL, dostupné na PGXN . Díky tomu vidím u CIE2000 zrychlení asi 150x při dotazování na všechny záznamy z tabulky se 100 000 záznamy.

S touto funkcí C získám časy dotazů mezi 147 ms a 160 ms pro 100 000 barev. S extra WHERE je doba dotazu asi 20 ms, což se mi zdá docela přijatelné.

Nejlepší, ale pokročilé řešení

Protože je však vaším problémem vyhledávání N nejbližšího souseda v 3-rozměrném prostoru, můžete použít indexování K-Nearest-Neighbor Indexing, které je v PostgreSQL od verze 9.1 .

Aby to fungovalo, vložili byste komponenty L*a*b* do kostka . Toto rozšíření zatím nepodporuje operátora vzdálenosti ( pracuje se na tom ), ale i kdyby ano, nepodporoval by vzdálenosti Delta E a museli byste jej znovu implementovat jako rozšíření C.

To znamená implementaci třídy indexového operátora GiST (btree_gist rozšíření PostgreSQL v contrib to dělá), aby podporoval indexování podle vzdáleností Delta E. Dobré na tom je, že pak můžete použít různé operátory pro různé verze Delta E, např. <-> pro Delta E CIE 2000 a <#> pro Delta E CIE 1976 a dotazy by byly opravdu opravdu rychlé pro malý LIMIT i s Delta E CIE 2000.

Nakonec to může záviset na tom, jaké jsou vaše (obchodní) požadavky a omezení.