Go言語を使って類似画像を検索する

こんにちは！エンジニアの後藤です。

今回はGo言語による類似画像の検索手法についてお話ししたいと思います。

代表的な画像検索技術について

まずは画像検索について。大きく分けて「TBIR」と「CBIR」があります。

TBIR

テキストをメタデータとした検索手法です。

ユーザーが入力したワードと画像のテキストデータを比較して、マッチした一覧を表示させる手法です。

例えば、電子書籍の検索などが挙げられます。

CBIR

画像の内容をメタデータとした検索手法です。

色や形といった画像の特徴をベースに検索するため、TBIRのようにあらかじめ画像に対してテキストデータを付与する必要はありません。

例えば、Googleの画像検索（こちらは正確に言えばTBIRとCBIRとの併用だと思いますが）などが挙げられます。

類似画像検索アルゴリズム

今回はCBIRに注目し、画像をハッシュ化してその特徴をベースに検索する手法を紹介したいと思います。

Average Hash

輝度値の平均を求め、平均より大きい場合は “1”、小さい場合は “0” として64ビットのハッシュ値を算出するという手法です。

実装手順

１. 画像を8x8にリサイズする。

２. 画像をグレースケール化する。

import (
	"image"
	_ "image/gif"
	_ "image/jpeg"
	_ "image/png"
"github.com/disintegration/gift"
)
// GetImage width, heightにリサイズし、グレースケール化したImageを返す
func GetImage(src image.Image, width, height int) image.Image {
	gi := gift.New(gift.Resize(width, height, gift.LinearResampling), gift.Grayscale())
	dst := image.NewRGBA(gi.Bounds(src.Bounds()))
	gi.Draw(dst, src)
	return dst
}
３. 輝度値の平均を求める。

４. 平均より大きい場合は "1"、小さい場合は "0" として64ビットのハッシュ値を求める。
// GetHash Imageのハッシュ値を返す
func GetHash(src image.Image) uint64 {
	srcBounds := src.Bounds()
var (
		pixels    []uint64
		sumPixels uint64
		maxY      = srcBounds.Max.Y
		maxX      = srcBounds.Max.X
	)
	for i := 0; i < maxY; i++ {
		for j := 0; j < maxX; j++ {
			r, g, b, _ := src.At(j, i).RGBA()
			// r,g,bの平均値を算出する（グレースケール化しているので pixels := uint64(r) でも構いません）
			pixel := uint64(math.Floor(float64((r + g + b)) / float64(3)))	
			// pixelの合計値（平均値を求める際に使用します）
			sumPixels += pixel
		
			pixels = append(pixels, pixel)
		}
	}
var (
		hash uint64
		one  uint64 = 1
		
		// 輝度値の平均を求める
		average     = uint64(math.Floor(float64(sumPixels) / float64((maxY * maxX))))
	)
	for _, pixel := range pixels {
		// ピクセルが平均値より大きいかどうかチェックする
		if pixel > average {
			hash |= one
		}
		one = one << 1
	}
return hash
}
５. ハミング距離を使って、得られた画像のハッシュ値を比較する。（ハミング距離については後ほど解説します）
// GetDistance ハッシュ間のハミング距離を返す
func GetDistance(hash1, hash2 uint64) int {
	distance := 0
var i, k uint64
	for i = 0; i < 64; i++ {
		k = (1 << i)
		if (hash1 & k) != (hash2 & k) {
			distance++
		}
	}
return distance
}
６. 閾値を決めて、類似画像かどうか判断する。
ハミング距離が小さいければ小さいほど類似画像であることになるので、閾値を決める必要があります。

ここは各サービスの性質に沿って決めるべきなので、一概には言えませんが「0~10」であれば類似画像とみなすのが良いと思います。
const threshold = 10
// IsSimilar 画像が類似しているかどうかを返す
func IsSimilar(src1, src2 image.Image) bool {
	hash1 := GetHash(src1)
	hash2 := GetHash(src2)
distance := GetDistance(hash1, hash2)
	if distance < threshold {
		return true
	}
return false
}
ハミング距離
等しい文字数を持つ二つの文字列の中で、対応する位置にある異なった文字の個数のことです。

例えば 1011101 と 1001001 の間のハミング距離は 2 となります。
Difference Hash
「Average Hash」とは異なる手法で注目されている簡易的な類似画像検索アルゴリズムをもう一つ紹介します。

「Difference Hash」は そのピクセルの輝度値が隣接するピクセルの輝度値より大きい場合は "1"、小さい場合は "0" として64ビットのハッシュ値を算出する手法です。
実装手順
１. 画像を9x8にリサイズする。（8x8ではありません！）

２. 画像をグレースケール化する。

３. そのピクセルの輝度値が隣接するピクセルの輝度値より大きい場合は "1"、小さい場合は "0" として64ビットのハッシュ値を求める。
// GetHash Imageのハッシュ値を返す
func GetHash(src image.Image) uint64 {
	srcBounds := src.Bounds()
var (
		hash uint64
		one  uint64 = 1
		maxY        = srcBounds.Max.Y
		maxX        = srcBounds.Max.X
	)
	for i := 0; i < maxY; i++ {
		lr, lg, lb, _ := src.At(0, i).RGBA()
		left := uint64(math.Floor(float64((lr + lg + lb)) / float64(3)))
		for j := 1; j < maxX; j++ {
			rr, rg, rb, _ := src.At(j, i).RGBA()
			right := uint64(math.Floor(float64((rr + rg + rb)) / float64(3)))
			
			// 隣接するピクセルの輝度値より大きいかどうかチェックする
			if left > right {
				hash |= one
			}
left = right
			one = one << 1
		}
	}
return hash
}
４. ハミング距離を使って、得られた画像のハッシュ値を比較する。

５. 閾値を決めて、類似画像かどうか判断する。
テスト
用意した各画像のハッシュを算出し、ハミング距離を使ってテストしてみましょう。
類似判定の閾値は "10" とします。
同じ画像で比較した場合

結果
Average Hash: 0

Difference Hash: 0
Average Hash と Difference Hash ともにハミング距離が閾値を下回っているので、類似画像と判定できます。
スケールを下げた画像と比較した場合

結果
Average Hash: 0

Difference Hash: 0
Average Hash と Difference Hash ともにハミング距離が閾値を下回っているので、類似画像と判定できます。
ぼやけた画像と比較した場合

結果
Average Hash: 1

Difference Hash: 1
Average Hash と Difference Hash ともにハミング距離が閾値を下回っているので、類似画像と判定できます。
反転画像と比較した場合

結果
Average Hash: 38

Difference Hash: 37
Average Hash と Difference Hash ともにハミング距離が閾値を超えているので、類似画像とは判定できません。
テキスト入りの画像と比較した場合

結果
Average Hash: 9

Difference Hash: 1
Average Hash と Difference Hash ともにハミング距離が閾値を下回っているので、類似画像と判定できます。
異なる画像で比較した場合

結果
Average Hash: 39

Difference Hash: 39
Average Hash と Difference Hash ともにハミング距離が閾値を超えているので、類似画像とは判定できません。
考察
反転（回転）した画像に関しては「Average Hash」や「Difference Hash」は有効ではないことが分かりました。「Average Hash」と「Difference Hash」の性能ですが、テキスト入り画像のハミング距離を見ると「Difference Hash」の方が良さそうです。プロダクトにアルゴリズムを採用する際は、対象の画像をたくさん用意してテストする必要があります。
最後に
ここまで類似画像検索の一部手法について解説してきました。実装自体は簡単なのでコードを書いて動かしてみると楽しいと思います。ハッシュを使った類似画像検索は、実際のサービスにも使われています。「Iconfinder」では「Difference Hash」を採用しているようでした。
Detecting duplicate images using Python
大切なのはサービスの性質に合わせて手法を決めることです。最初はざっくりした実装で良いので、テストをガンガン回しながら最適なアルゴリズムに改善していけば良いものが出来上がってきます。次回は別の手法を解説します！
ではまた！
資料リンク
http://www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-It.html
http://www.hackerfactor.com/blog/index.php?/archives/529-Kind-of-Like-That.html

https://ja.wikipedia.org/wiki/ハミング距離