如何通過SQL查詢中的相似性來查找圖像？

Question

我要處理的圖像建立比方說，每一個裏面9個區域，然後找到每個區域的平均顏色，然後將其保存到一個char場這樣的：

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，一個選項可能是將每個平均顏色值放入一個單獨的列。

Answer 1

我會建議使用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) 

Answer 2

實際上，從它的聲音中，你正試圖做一個序列對齊的形式。對於有一系列的算法被用來比較基因序列：

Sequence Alignment

Answer 3

我認爲你正在尋找這樣的事情...

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

注意色差右邊...

Color Difference: 1.84568861095 

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

如果有大量的併發用戶，在1000多行上運行此查詢肯定會終止您的服務器。

Answer 4

好了，你的表圖片都有一個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 

這可能是相當有效的，你也來試試吧。

Answer 5

更「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）所需的任何細節。

這是恕我直言的一個更清潔的數據庫設計（如果以後使用更多的區域等，完全適合）。

Answer 6

問題在我看來不是序列比較問題，但地理之一。

我想你想在第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地理點。然後，兩幅圖像之間的差異將是三個（地理）距離的總和。