Delta E(CIE Lab)在SQL中的性能计算和排序

Question

Delta E(CIE Lab)在SQL中的性能计算和排序

Jaz*_*aza 5 algorithm postgresql colors query-performance flask

我有一个数据库表,其中每一行都是一种颜色.我的目标:给定输入颜色,计算它与DB表中每种颜色的距离,并按该距离对结果进行排序.或者,作为用户故事说明:当我选择一种颜色时,我希望看到与我选择的颜色最相似的颜色列表,其中最接近的匹配位于列表顶部.

据我所知,为了做到这一点,各种Delta E(CIE Lab)公式是最佳选择.我无法找到公式的任何本机SQL实现,所以我编写了自己的SQL版本的Delta E CIE 1976和Delta E CIE 2000.我根据python-colormath实现生成的结果验证了公式的SQL版本的准确性.

1976年的公式很容易用SQL或任何其他语言编写,因为它是一个简单的欧几里德距离计算.对于我来说,它对任何大小的数据集执行得很好而且快速(在具有100,000行的颜色表上测试它,并且查询花费不到1秒).

相比之下,2000年的公式非常漫长而复杂.我设法在SQL中实现它,但它的性能不是很好:查询10,000行大约需要5秒,查询100,000行大约需要1分钟.

我写了一个名为colorsearchtest的示例应用程序(在Python/Flask/Postgres中),以解决我的实现问题(我在Heroku上设置了一个演示).如果您试用这个应用程序,您可以清楚地看到1976年和2000年Delta E查询之间的性能差异.

这是颜色表的模式(对于每种颜色,它存储相应的RGB和Lab表示,作为三个数值):

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

Run Code Online (Sandbox Code Playgroud)

这是表格中的一些数据(所有颜色都是随机颜色,由我的应用程序中的脚本生成):

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

...

Run Code Online (Sandbox Code Playgroud)

这是我正在使用的Delta E CIE 2000 SQL函数:

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;

Run Code Online (Sandbox Code Playgroud)

(我最初使用大约10级深度的嵌套子查询编写了这个函数,但我重新编写了它而不是使用WITH语句,即Postgres CTE.新版本更具可读性,性能类似于旧版本.你可以看到代码中的两个版本.)

定义函数后,我在这样的查询中使用它:

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;

Run Code Online (Sandbox Code Playgroud)

所以,我的问题是:有什么方法可以提高DELTA_E_CIE2000函数的性能,使其可以实时用于非平凡的数据集？或者,考虑到公式的复杂性,它的速度是否会达到最快？

从我在我的演示应用程序中完成的测试中,我会说,对于网站上简单的"相似颜色"搜索的用例,1976和2000函数之间的结果准确性差异实际上可以忽略不计.也就是说,我已经确信,根据我的需要,1976年的公式"足够好".但是,2000函数确实会返回稍微好一些的结果(很大程度上取决于输入颜色在Lab空间中的位置),而且我真的很好奇它是否可以进一步加速.

Answer 1

hru*_*ske 6

两件事:1)您没有充分利用数据库2)您的问题是自定义PostgreSQL扩展的一个很好的例子.这就是原因.

您只使用数据库作为存储,将颜色存储为浮点数.在当前配置中,无论查询类型如何,数据库始终都必须检查所有值(进行顺序扫描).这意味着很多IO和许多返回匹配的计算很多.您正在尝试找到最接近的N种颜色,因此有一些可能性可以避免对所有数据执行计算.

简单的改进

最简单的方法是将计算限制在较小的数据子集中.如果组件差异更大,您可以假设差异会更大.如果您可以在结果总是不合适的组件之间找到安全差异,则可以使用带有btree索引的范围WHERE完全排除这些颜色.但是,由于L*a*b颜色空间的性质,这可能会使您的结果恶化.

首先创建索引:

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

Run Code Online (Sandbox Code Playgroud)

然后我调整了您的查询以包含一个WHERE子句来仅过滤颜色,其中任何组件的差异最多为20.

更新:再看看,添加20的限制很可能会使结果恶化,因为我发现空间中至少有一个点,这是真的:

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 ;

Run Code Online (Sandbox Code Playgroud)

我用你的脚本在表格中填充了100000种随机颜色并进行了测试:

没有索引的时间:44006,851毫秒

索引和范围查询的时间:1293,092 ms

您也可以添加此WHERE子句delta_e_cie1976_query,在我的随机数据上,它将查询时间从~110 ms减少到~22 ms.

顺便说一句:我从经验上得到了数字20:我尝试了10,但只得到了380条记录,这看起来有点低,可能会排除一些更好的选项,因为限制为100.有20个全套是2900行,一个可以公平确保最接近的匹配将在那里.我没有详细研究DELTA_E_CIE2000或L*a*b*颜色空间,因此阈值可能需要沿着不同的组件进行调整才能实现真实,但排除非感兴趣数据的原则仍然存在.

用C重写Delta E CIE 2000

正如您已经说过的,Delta E CIE 2000很复杂,并且不适合在SQL中实现.它目前在我的笔记本电脑上每次通话使用大约0.4毫秒.用C语言实现它应该可以大大提高速度.PostgreSQL为SQL函数分配默认成本为100,C函数为1.我猜这是基于实际经验.

更新:由于这也划伤了我的一个痒,我从C中的colormath模块重新实现了Delta E函数作为PostgreSQL扩展,可在PGXN上获得.有了这个,我可以看到CIE2000在用100k记录查询表中的所有记录时加速大约150x.

使用此C函数,对于100k颜色,我的查询时间介于147毫秒和160毫秒之间.使用额外的WHERE,查询时间约为20毫秒,这对我来说似乎是可以接受的.

最好但是先进的解决方案

但是,由于你的问题是三维空间中的N最近邻搜索,你可以使用自9.1版以来在PostgreSQL中的K-Nearest-Neighbor Indexing .

为此,您需要将L*a*b*组件放入多维数据集中.此扩展程序尚不支持距离操作员(它正在工作中),但即使这样,它也不支持Delta E距离,您需要将其重新实现为C扩展.

这意味着实现GiST索引操作符类(contrib中的btree_gist PostgreSQL扩展这样做)以支持根据Delta E距离进行索引.好的部分是你可以为不同版本的Delta E使用不同的运算符,例如.<->对于Delta E CIE 2000和<#>Delta E CIE 1976,即使使用Delta E CIE 2000,对于小LIMIT来说查询也非常快.

最后,它可能取决于您(业务)的要求和约束.

归档时间：	10 年，4 月前
查看次数：	1509 次
最近记录：	7 年，11 月前