在 SQL 中实现卷积

Question

我有一个 table d 字段 x, y, f，（PK 是 x,y）并且想实现卷积，其中一个新列 c，被定义为给定任意内核的卷积（2D）。在过程语言中，这很容易定义（见下文）。我相信可以使用 JOIN 在 SQL 中定义它，但我在这样做时遇到了麻烦。

在程序语言中，我会这样做：

def conv(x, y):
     c = 0
     # x_ and y_ are pronounced "x prime" and "y prime", 
     # and take on *all* x and y values in the table; 
     # that is, we iterate through *all* rows
     for all x_, y_
         c += f(x_, y_) * kernel(x_ - x, y_ - y)
     return c

kernel 可以是任意函数。在我的例子中，它是 1/k^(sqrt(x_dist^2, y_dist^2))，kernel(0,0) = 1。

出于性能原因，我们不需要查看每个 x_, y_。我们可以在距离 < 阈值的地方过滤它。

我认为这可以使用笛卡尔乘积连接、聚合 SQL SUM 以及 WHERE 子句来完成。

在 SQL 中执行此操作的另一个挑战是 NULL。天真的实现会将它们视为零。我想做的是将内核视为加权平均值，而忽略 NULL。也就是说，我将使用一个函数 wkernel 作为我的内核，并将上面的代码修改为：

def conv(x, y):
     c = 0
     w = 0
     for all x_, y_  
         c += f(x_, y_) * wkernel(x_ - x, y_ - y)
         w += wkernel(x_ - x, y_ - y)
     return c/w

这将使 NULL 工作得很好。

澄清一下：您不能进行部分观察，其中 x=NULL 且 y=3。但是，您可能缺少观察结果，例如没有 x=2 和 y=3 的记录。我指的是 NULL，因为整个记录都丢失了。我上面的程序代码可以很好地处理这个问题。

我相信以上可以在 SQL 中完成（假设 wkernel 已经实现为一个函数），但我不知道如何做。我正在使用 Postgres 9.4。

样本table:

 Table d
 x  | y  | f
 0  | 0  | 1.4
 1  | 0  | 2.3
 0  | 1  | 1.7
 1  | 1  | 1.2

输出（只显示一行）：

 x  | y  | c
 0  | 0  | 1.4*1 + 2.3*1/k + 1.7*1/k + 1.2*1/k^1.414

卷积https://en.wikipedia.org/wiki/Convolution是整个图像处理和信号处理中使用的标准算法，我相信它可以在SQL中完成，这对于我们现在的大数据集来说非常有用使用。

Answer 1

我假定了一个函数wkernel，例如：

create or replace function wkernel(k numeric, xdist numeric, ydist numeric)
returns numeric language sql as $$
  select 1. / pow(k, sqrt(xdist*xdist + ydist*ydist))
$$;

以下查询提供了您想要的但不限于关闭值：

select d1.x, d1.y, SUM(d2.f*wkernel(2, d2.x-d1.x, d2.y-d1.y)) AS c
from d d1 cross join d d2 
group by d1.x, d1.y;

 x | y |            c            
---+---+-------------------------
 0 | 0 | 3.850257072695778143380
 1 | 0 | 4.237864186319019036455
 0 | 1 | 3.862992722666908108145
 1 | 1 | 3.725299918145074500610
(4 rows)

有一些任意限制：

select d1.x, d1.y, SUM(d2.f*wkernel(2, d2.x-d1.x, d2.y-d1.y)) AS c
from d d1 cross join d d2
where abs(d2.x-d1.x)+abs(d2.y-d1.y) < 1.1
group by d1.x, d1.y;

 x | y |            c            
---+---+-------------------------
 0 | 0 | 3.400000000000000000000
 1 | 0 | 3.600000000000000000000
 0 | 1 | 3.000000000000000000000
 1 | 1 | 3.200000000000000000000
(4 rows)

为加权平均分：

select d1.x, d1.y, SUM(d2.f*wkernel(2, d2.x-d1.x, d2.y-d1.y)) / SUM(wkernel(2, d2.x-d1.x, d2.y-d1.y)) AS c
from d d1 cross join d d2
where abs(d2.x-d1.x)+abs(d2.y-d1.y) < 1.1
group by d1.x, d1.y;

现在谈谈缺少的信息。在下面的代码中，请将 2 替换为要考虑的最大距离。

想法如下：我们找到所考虑图像的边界，并生成可能需要的所有信息。在您的示例中，最大范围为 1，我们需要所有对 (x, y) 满足 (-1 <= x <= 2) 和 (-1 <= y <= 2).

查找边界并确定范围=1 和 k=2（将此关系称为 cfg）：

SELECT MIN(x), MAX(x), MIN(y), MAX(y), 1, 2
FROM d;

 min | max | min | max | ?column? | ?column? 
-----+-----+-----+-----+----------+----------
   0 |   1 |   0 |   1 |        1 |        2

正在生成一组完整的值（称此关系已完成）：

SELECT x.*, y.*, COALESCE(f, 0)
FROM cfg
CROSS JOIN generate_series(minx - scope, maxx + scope) x
CROSS JOIN generate_series(miny - scope, maxy + scope) y
LEFT JOIN d ON d.x = x.* AND d.y = y.*;

 x  | y  | coalesce 
----+----+----------
 -1 | -1 |        0
 -1 |  0 |        0
 -1 |  1 |        0
 -1 |  2 |        0
  0 | -1 |        0
  0 |  0 |      1.4
  0 |  1 |      1.7
  0 |  2 |        0
  1 | -1 |        0
  1 |  0 |      2.3
  1 |  1 |      1.2
  1 |  2 |        0
  2 | -1 |        0
  2 |  0 |        0
  2 |  1 |        0
  2 |  2 |        0
(16 rows)

现在我们只需要使用之前给出的查询以及 cfg 和完成的关系来计算值。请注意，我们不计算边界值的卷积：

SELECT d1.x, d1.y, SUM(d2.f*wkernel(k, d2.x-d1.x, d2.y-d1.y)) / SUM(wkernel(k, d2.x-d1.x, d2.y-d1.y)) AS c
FROM cfg cross join completed d1 cross join completed d2
WHERE d1.x BETWEEN minx AND maxx
  AND d1.y BETWEEN miny AND maxy
  AND abs(d2.x-d1.x)+abs(d2.y-d1.y) <= scope
GROUP BY d1.x, d1.y;

 x | y |            c            
---+---+-------------------------
 0 | 0 | 1.400000000000000000000
 0 | 1 | 1.700000000000000000000
 1 | 0 | 2.300000000000000000000
 1 | 1 | 1.200000000000000000000
(4 rows)

合二为一，这给出了：

WITH cfg(minx, maxx, miny, maxy, scope, k) AS (
  SELECT MIN(x), MAX(x), MIN(y), MAX(y), 1, 2
  FROM d
), completed(x, y, f) AS (
  SELECT x.*, y.*, COALESCE(f, 0)
  FROM cfg
  CROSS JOIN generate_series(minx - scope, maxx + scope) x
  CROSS JOIN generate_series(miny - scope, maxy + scope) y
  LEFT JOIN d ON d.x = x.* AND d.y = y.*
)
SELECT d1.x, d1.y, SUM(d2.f*wkernel(k, d2.x-d1.x, d2.y-d1.y)) / SUM(wkernel(k, d2.x-d1.x, d2.y-d1.y)) AS c
FROM cfg cross join completed d1 cross join completed d2
WHERE d1.x BETWEEN minx AND maxx
  AND d1.y BETWEEN miny AND maxy
  AND abs(d2.x-d1.x)+abs(d2.y-d1.y) <= scope
GROUP BY d1.x, d1.y;

希望对您有所帮助:-)

在 SQL 中实现卷积

Implementing Convolution in SQL

sql

postgresql

image-processing

convolution