2013-08-07

[MySQL] 計算漢明距離

之前寫了用 PHP 計算圖片的 hash code,接著要怎麼去搜尋相似的圖片呢?

資料庫是一個很好的選擇,首先建立一個簡單的 Table:
CREATE TABLE image_hash (
    id         INT(11) NOT NULL AUTO_INCREMENT,
    filepath   VARCHAR(256) NOT NULL,
    hash       BIGINT(20) UNSIGNED ZEROFILL NOT NULL,

    PRIMARY KEY  (id)
) ENGINE=MYISAM;


再來要怎麼將 hash code 寫進資料表呢?我們可以利用 b'010101' 的 bit 表示語法將 hash code 64位元字串存進 BIGINT 裡面。
INSERT INTO image_hash_info (filepath, hash)
    VALUES('/home/jax/12.jpg', b'10100111...');


資料已經備齊了,最重要的就是怎麼計算漢明距離了,MySQL 提供了 BIT_COUNT() 的函數,可以計算數字中位元 1 的個數,所以剩下的就是 XOR 的運算了。
SELECT BIT_COUNT(29), BIT_COUNT(b'101010');
       -- -> 4, 3


找尋與某一個 hash code 相似的圖片
SELECT * FROM image_hash
    WHERE BIT_COUNT(hash ^ b'1010011110...') <= 10


參考來源:
MySQL 5.0 Bit Functions

6 回應:

Lucien 提到...

這是第二次來這邊留言了,上ㄧ篇也是研究phash時用您的方法。您真的寫得很好,phash在破萬張的比對上顯得有些吃力,才想說用SQL來存...就找到你這邊來了。

胡忠晞 提到...

我在破千張就覺得有點慢了,還是有DB會好一點!

Lucien 提到...

請教一下, phash結果會隨windows跟liunx等環境因素有所不同嗎 ? 我自己的筆電跑一張圖的hash code 64位元字串速度很快(< 1秒),但丟到虛擬主機,1張圖就要5秒左右(那虛擬主機性能不錯的...)。重點是跑出來的結果還不相同,兩張圖的distance為2,雖然是可以接受, 但還是好奇為何會這樣 ?

胡忠晞 提到...

可能是縮圖函式造成的差異,你可以試試用 Imagick 做縮圖

$image = new Imagick($imagePath);
$image->thumbnailImage($width, $height);
$img = imagecreatefromstring($image->getImageBlob());

Lucien 提到...

後來證實為虛擬主機的Imagick縮圖過慢,網路看一下也有人有這問題,貌似版本問題。另外親自試了幾次,phash比較精確,但dhash容錯率比較高,如果是要找相似圖片,dhash感覺好些。另外在網路上也有看到不錯的方法與您分享, Libpuzzle可以讓php呼叫,不過我的虛擬主機不能擴增套件所以就沒試,但據說效果很好~推薦給您

胡忠晞 提到...

恩恩!找機會在來玩一玩!