如何通过SQL查询中的相似性来查找图像？

我要处理的图像建立比方说，每一个里面9个区域，然后找到每个区域的平均颜色，然后将其保存到一个char场这样的：如何通过SQL查询中的相似性来查找图像？

255,255,255,255,255,255,107,195,305

然后查找所有图片类似于给定图像，我必须计算每对颜色（对同一区域进行比较）之间的距离，例如：

这些图像之间的差异是1：

255,255,255,255,255,255,107,195,305 
255,255,255,255,255,255,107,195,304

这些之间的差图像是3：

255,255,255,255,255,255,105,195,305 
255,255,255,255,255,255,107,195,304

我的问题是如何执行这样的查询，并按相似性排序？该字段只是一个字符串，值之间用逗号分隔。

这样的查询可能会很快吗？或者我应该寻找一种不同的方法？我们正在谈论成千上万的图像

编辑：作为@therealsix，一个选项可能是将每个平均颜色值放入一个单独的列。

来源

2011-04-08 HappyDeveloper

我可以理解在查询中做这件事的唯一方法是超越丑陋，而且非常保证效率低下。在我看来，这可能是一个合理的查询，如果这在9个独立的列。 – therealsix 2011-04-08 03:41:42

是的，这是我第一次想到，我忘了提及它。它看起来迄今为止是最好的选择。谢谢 – HappyDeveloper 2011-04-08 04:01:34

查看我刚发布的答案。所有在服务器上的mysql都完成了。 – Wes 2011-04-08 04:14:26

我会建议使用mysql函数来比较你的随机给定的图像。首先让我们创建一个简单的示例表

DROP TABLE IF EXISTS images; 

CREATE TABLE images (
    id   INTEGER AUTO_INCREMENT PRIMARY KEY, 
    rgb_values VARCHAR(255) 
);

现在让我们定义我们将在我们的查询中使用的函数。第一个允许使用拆就任何分隔字符串，并通过指数获得所需的元素回：

DROP FUNCTION SPLIT_STR; 

CREATE FUNCTION SPLIT_STR(
    x VARCHAR(255), 
    delim VARCHAR(12), 
    pos INT 
) 
RETURNS VARCHAR(255) 
RETURN 
    REPLACE(SUBSTRING(SUBSTRING_INDEX(x, delim, pos), 
    LENGTH(SUBSTRING_INDEX(x, delim, pos -1)) + 1), 
    delim, '') 
;

接下来，我们定义一个函数来计算你想这个问题根据您的算法的图像差（或任何ALGO使用）：

DROP FUNCTION IMAGE_DIFF; 

CREATE FUNCTION IMAGE_DIFF(
    from_val VARCHAR(255), 
    to_val VARCHAR(255) 
) 
RETURNS INTEGER(4) 
RETURN 
    ABS((SPLIT_STR(to_val, ',', 1) - SPLIT_STR(from_val, ',',1))) + 
    ABS((SPLIT_STR(to_val, ',', 2) - SPLIT_STR(from_val, ',',2))) + 
    ABS((SPLIT_STR(to_val, ',', 3) - SPLIT_STR(from_val, ',',3))) + 
    ABS((SPLIT_STR(to_val, ',', 4) - SPLIT_STR(from_val, ',',4))) + 
    ABS((SPLIT_STR(to_val, ',', 5) - SPLIT_STR(from_val, ',',5))) + 
    ABS((SPLIT_STR(to_val, ',', 6) - SPLIT_STR(from_val, ',',6))) + 
    ABS((SPLIT_STR(to_val, ',', 7) - SPLIT_STR(from_val, ',',7))) + 
    ABS((SPLIT_STR(to_val, ',', 8) - SPLIT_STR(from_val, ',',8))) + 
    ABS((SPLIT_STR(to_val, ',', 9) - SPLIT_STR(from_val, ',',9))) 
;

让我们创建一些示例数据：

INSERT INTO images(rgb_values) VALUES ("237,128,73,69,35,249,199,183,178"); 
INSERT INTO images(rgb_values) VALUES ("39,212,164,170,202,49,93,77,145"); 
INSERT INTO images(rgb_values) VALUES ("28,242,83,167,92,161,115,38,108"); 
INSERT INTO images(rgb_values) VALUES ("72,81,73,2,77,109,177,204,120"); 
INSERT INTO images(rgb_values) VALUES ("165,149,106,248,39,26,167,237,139"); 
INSERT INTO images(rgb_values) VALUES ("183,40,156,131,120,19,71,88,69"); 
INSERT INTO images(rgb_values) VALUES ("138,136,112,36,69,245,130,196,24"); 
INSERT INTO images(rgb_values) VALUES ("1,194,153,107,16,102,164,154,74"); 
INSERT INTO images(rgb_values) VALUES ("172,161,17,179,140,244,23,219,115"); 
INSERT INTO images(rgb_values) VALUES ("166,151,48,62,154,227,44,21,201"); 
INSERT INTO images(rgb_values) VALUES ("118,73,212,180,150,64,254,177,68"); 
INSERT INTO images(rgb_values) VALUES ("119,220,226,254,14,175,123,11,134"); 
INSERT INTO images(rgb_values) VALUES ("118,93,238,31,77,36,105,151,216"); 
INSERT INTO images(rgb_values) VALUES ("123,108,177,136,9,24,119,175,88"); 
INSERT INTO images(rgb_values) VALUES ("11,207,12,215,215,80,101,213,143"); 
INSERT INTO images(rgb_values) VALUES ("132,158,46,188,7,245,241,126,214"); 
INSERT INTO images(rgb_values) VALUES ("167,238,186,86,109,164,219,199,238"); 
INSERT INTO images(rgb_values) VALUES ("216,93,139,246,153,39,226,152,143"); 
INSERT INTO images(rgb_values) VALUES ("98,229,7,203,230,224,57,154,252"); 
INSERT INTO images(rgb_values) VALUES ("7,95,145,120,35,6,116,240,64"); 
INSERT INTO images(rgb_values) VALUES ("45,194,172,223,96,168,18,4,215"); 
INSERT INTO images(rgb_values) VALUES ("243,161,214,235,134,190,207,63,127"); 
INSERT INTO images(rgb_values) VALUES ("74,189,249,85,148,169,65,3,81"); 
INSERT INTO images(rgb_values) VALUES ("46,113,191,20,108,139,60,249,6"); 
INSERT INTO images(rgb_values) VALUES ("153,246,189,175,5,125,9,197,160"); 
INSERT INTO images(rgb_values) VALUES ("202,248,23,59,81,175,197,180,114"); 
INSERT INTO images(rgb_values) VALUES ("73,136,252,137,222,197,118,64,69"); 
INSERT INTO images(rgb_values) VALUES ("172,224,251,32,154,175,201,33,14"); 
INSERT INTO images(rgb_values) VALUES ("141,126,112,12,45,214,243,127,49"); 
INSERT INTO images(rgb_values) VALUES ("116,155,23,205,62,235,111,136,205");

，然后使用我们的新定义的函数对要使用比较形象运行一个查询：

mysql> SELECT id 
    ->  , image_diff(rgb_values, '255,191,234,123,85,23,255,255,255') rgb_diff 
    -> FROM images 
    -> ORDER BY 2 DESC; 
+----+----------+ 
| id | rgb_diff | 
+----+----------+ 
| 19 |  1150 | 
| 10 |  1148 | 
| 3 |  1122 | 
| 27 |  1094 | 
| 9 |  1070 | 
| 15 |  1069 | 
| 23 |  1061 | 
| 21 |  1059 | 
| 7 |  1034 | 
| 12 |  1024 | 
| 24 |  1022 | 
| 30 |  1016 | 
| 29 |  989 | 
| 28 |  962 | 
| 2 |  947 | 
| 4 |  933 | 
| 16 |  893 | 
| 6 |  885 | 
| 8 |  875 | 
| 20 |  848 | 
| 25 |  835 | 
| 26 |  815 | 
| 1 |  777 | 
| 22 |  758 | 
| 14 |  745 | 
| 11 |  706 | 
| 18 |  683 | 
| 5 |  656 | 
| 13 |  645 | 
| 17 |  494 | 
+----+----------+ 
30 rows in set (0.01 sec)

来源

2011-04-08 04:11:28 Wes

image_diff？你是否建议你将其定义为一个函数？ – therealsix 2011-04-08 04:18:19

@therealsix是的，我确实说过，作为我的回应的第一行，并提供了所有功能的代码作为例子。 – Wes 2011-04-08 04:20:09

抱歉，不知道我是如何错过的。 – therealsix 2011-04-08 04:25:18

实际上，从它的声音中，你正试图做一个序列对齐的形式。对于有一系列的算法被用来比较基因序列：

Sequence Alignment

来源

2011-04-08 03:33:20 Thomas

Google上有一个SQL实现。 – 2011-04-08 03:37:34

@webarto - 的确，我为SQL Server编写了一个。我只是没有把它改写成MySQL。一旦你知道使用正确的工具，有很多选择。 – Thomas 2011-04-08 03:44:09

就像他们在我的国家所说的那样，没有工具就没有工匠:)关心分享你的功能吗？ – 2011-04-08 03:54:34

我认为你正在寻找这样的事情...

http://kodisha.net/color-names/?color=FD464A

注意色差右边...

Color Difference: 1.84568861095

http://en.wikipedia.org/wiki/Color_difference

如果有大量的并发用户，在1000多行上运行此查询肯定会终止您的服务器。

来源

2011-04-08 03:38:55

好了，你的表图片都有一个id和9个单独的颜色fields- COLOR1通过色彩9

SELECT a.id, b.id, (ABS(a.color1 - b.color) + ABS(a.color2 + b.color2) + ABS(a.color3 + b.color3) + ...) AS difference 
FROM images AS a 
JOIN images AS b 
WHERE a.id > b.id 
ORDER BY difference

这可能是相当有效的，你也来试试吧。

来源

2011-04-08 04:24:36 therealsix

当原始点比较单个图像节点与db中的所有其他图像时，这不会计算所有可能的“差异”吗？ – Wes 2011-04-08 16:38:49

@韦斯 - 是你的权利。 – therealsix 2011-04-09 13:31:40

更“SQLey”的方式来做到这一点，可能是使用了更规范化的数据库的方法，用2个表：

Image(ImageID int, ... other columns as required ...) 
ImageZone(ImageID int, ZoneIndex int, ColourValue int, ...)

所以对于你的榜样，你可能有

ImageID ZoneIndex ColourValue 
------- --------- ----------- 
    1   1   255 
    1   2   255 
    ... 
    1   9   304 
    2   1   255 
    ... 
    2   9   305

然后，为了获得距离，像（我是一个SQL Server的家伙，但这应该很容易转换到MySQL）：

SELECT 
    Candidate.ImageID, 
    Candidate.ImageFile, /* or whatever... */ 
    Scores.Difference 
FROM 
(
    SELECT 
     Original.ImageID AS OriginalID, 
     Candidate.ImageID AS CandidateID, 
     SUM(ABS(Original.ColourValue - Candidate.ColourValue)) AS Difference 
    FROM ImageZone AS Original 
    INNER JOIN ImageZone AS Candidate 
    ON (Original.ImageID <> Candidate.ImageID) 
    ON (Original.ZoneIndex = Candidate.ZoneIndex) 
) AS Scores 
INNER JOIN Image AS Candidate ON (Scores.CandidateID = Candidate.ImageID) 
WHERE Scores.OriginalID = 1 /* or the image ID you want to look up */ 
ORDER BY Difference

所以内部查询创建用于每一个候选区的行，例如，（O =原，C =候选）：

O.ImageID O.ZoneIndex O.ColourValue C.ImageID C.ZoneIndex C.ColourValue 
--------- ----------- ------------- --------- ----------- ------------- 
    1   1   255   2   1   255 
    ... then ... 
    1   9   305   2   9   304 
    1   1   255   3   1   99 
    ... then ... 
    99   9   100   98   9   99

其随后聚集成总差异：

OriginalID CandidateID Difference 
---------- ----------- ---------- 
    1   2   1 
    1   3   10 
    ... 
    99   98   500

您然后选择从这个虚拟表中，只有OriginalID是1的地方，然后将它重新加入到原始Image表中，以获得最低“差异”分数（在本例中为2）所需的任何细节。

这是恕我直言的一个更清洁的数据库设计（如果以后使用更多的区域等，完全适合）。

来源

2011-04-08 05:21:38 Cowan

这将是有趣的，看到这个解释计划，并将其与仅使用一个表格产品的简单计划进行比较。我的猜测是执行计算的编译函数更有效的动态表子查询，但我可能是错的。 – Wes 2011-04-08 16:40:42

问题在我看来不是序列比较问题，但地理之一。

我想你想在第9维点集中找到附近的点。

检查本文就如何空间数据库使用R树为集群的高效搜索（如点附近的这是你想要什么。）：Incremental Distance Join Algorithms for Spatial Databases（点击“网页快照”链接）

房地产问题是我知道没有支持9维的空间数据库。只有我能想到的破解将是地理三重点的三倍（A，B，C）。

为了让我的观点更加清楚。让我们来看看你的数据：

这些图像之间的差为3：

255,255,255,255,255,255,105,195,305 
255,255,255,255,255,255,107,195,304

我们可以看一下上面的两行的2分（让我们称之为a和b）在9维世界中。

这9个数字是它们的坐标（a1,a2,...,a9和b1,b2,...,b9）。

而“差异”是他们的距离：Sum(|ai-bi|)。定义距离的方法有很多，这是常用的方法之一。这不是欧几里德距离，但它是相似的。而且它的计算速度稍快。

现在，如果您真的要拥有数千或数百万的图像，计算所有数百万（或万亿）的距离将会是一个非常缓慢的过程。如果你只需要一次比较一个，而不是几千个，我想你已经有两个答案，那就没问题。

但是，如果你真的想找到类似的图像，并有很多（如成千上万）的存储，空间数据库使用R树或其他索引会更好。 R树不是什么神奇的东西，它只是专门用于这种多维数据的索引。

如果您找不到支持这么多维度的空间数据库，我不确定您将如何创建自己的解决方案。

一个想法是将9个数字拆分为3个三元组。每个三元组都是一个三维点。所以，你的每个图像都将被存储为三个3D地理点。然后，两幅图像之间的差异将是三个（地理）距离的总和。

来源

2011-04-08 09:14:49

我没有看到区别。我只比较一个图像中的每个点，以及另一个图像中的相似点。 – HappyDeveloper 2011-04-08 12:45:46

@快乐开发者：看我的编辑。 – 2011-04-08 13:45:31

我很想阅读文章，但链接不起作用：提供的文档标识符与我们存储库中的任何文档不匹配。无论如何，你为什么说我们在这里有9个维度？我认为我们可以将所有可能的颜色放在一个立方体中（3维） – HappyDeveloper 2011-04-09 03:09:03

如何通过SQL查询中的相似性来查找图像？

回答

相关问题