画像の dHash を PostgreSQL に登録し、 SQL で類似画像を検索する

はじめに

前回の記事で、 Elixir Image を使った dHash による類似画像の検索を実装しました

類似画像の検索が一度きりなら、以下のような流れで処理をすれば問題ありません

• 対象となる全画像の dHash を計算する
• 画像の全組み合わせについて dHash 同士のハミング距離を計算する
• ハミング距離が ２0 以下の画像同士を類似画像とする

しかし、画像が日々蓄積されていき、それを毎日チェックするような場合、毎回全画像の dHash を計算するのは時間の無駄です

画像が追加された時点で dHash を計算し、それをデータベースに保存して使用した方が効率的でしょう

また、ハミング距離を計算するために全画像の dHash をデータベースから取得するのも無駄が多いように感じます

できれば SQL でハミング距離を計算し、類似画像だけを取得したいです

今回の記事では以下のような処理を Livebook 上で実装します

• 対象となる全画像の dHash を計算する
• 画像毎に dHash の値をデータベースに登録する
• SQL の WHERE 句でハミング距離を計算し、近い組み合わせだけを取得する

また、データベースには PostgreSQL を使います
Livebook と PostgreSQL をコンテナで立ち上げる手順については以下の記事を参考にしてください

データベース操作には Ecto を使用します
Livebook 上での Ecto 使用については以下の記事を参考にしてください

本記事では Elixir + Livebook で実装していますが、 SQL 自体は PostgreSQL で使えるものなので、 Python などで同じことを考えている方も是非参考にしてください

SQL　だけ見たい方はこちら

実装したノートブックはこちら

参考記事

本記事の執筆にあたり、 @souten21kobayashi さんの記事を参考にしました

@souten21kobayashi さんの記事では MySQL を使っているので、 PostgreSQL との違いなども含めて読んでいただけると幸いです

セットアップ

必要なモジュールをインストールします

今回は dHash の計算に必要なものと、 DB 操作に必要なものをインストールしています

Mix.install([
  {:ecto, "~> 3.10"},
  {:ecto_sql, "~> 3.10"},
  {:jason, "~> 1.4"},
  {:postgrex, "~> 0.17.3"},
  {:image, "~> 0.38"},
  {:req, "~> 0.3"},
  {:kino, "~> 0.11"}
])

画像の準備

前回の記事と同じように元画像と、少し変化させた画像、別画像を準備します

# 元画像
original_img =
  "https://www.elixirconf.eu/assets/images/drops.svg"
  |> Req.get!()
  |> Map.get(:body)
  |> Image.from_binary!()

# グレースケール
gray_img = Image.to_colorspace!(original_img, :bw)

# リサイズ
resized_img = Image.resize!(original_img, 0.5)

# 回転
rotated_img = Image.rotate!(original_img, 45)

# 切り取り
cropped_img = Image.crop!(original_img, 0.07, 0.07, 0.9, 0.9)

# 文字追加
text_img = Image.Text.text!("Elixir", text_fill_color: :purple)
with_text_img = Image.compose!(original_img, text_img, x: 300, y: 100)

# 別画像
other_img =
  "https://hexdocs.pm/phoenix/assets/logo.png"
  |> Req.get!()
  |> Map.get(:body)
  |> Image.from_binary!()

img_list =
  [
    %{name: "original_img", image: original_img},
    %{name: "gray_img", image: gray_img},
    %{name: "resized_img", image: resized_img},
    %{name: "rotated_img", image: rotated_img},
    %{name: "cropped_img", image: cropped_img},
    %{name: "with_text", image: with_text_img},
    %{name: "other", image: other_img}
  ]

img_list
|> Enum.map(fn %{name: name, image: img} ->
  Kino.Layout.grid([name, img], columns: 1)
end)
|> Kino.Layout.grid(columns: 4)

ハッシュの計算

各画像の dHash を計算します

img_list =
  Enum.map(img_list, fn %{image: img}=map ->
    Map.merge(map, %{dhash: Image.dhash(img) |> elem(1)})
  end)

結果は以下のようになります

[
  %{
    name: "original_img",
    image: %Vix.Vips.Image{ref: #Reference<0.2507745200.1059192849.55375>},
    dhash: <<56, 126, 207, 217, 253, 103, 103, 124>>
  },
  %{
    name: "gray_img",
    image: %Vix.Vips.Image{ref: #Reference<0.2507745200.1059192849.55376>},
    dhash: <<56, 126, 207, 217, 253, 103, 103, 124>>
  },
    image: %Vix.Vips.Image{ref: #Reference<0.2507745200.1059192849.55380>},
    dhash: <<56, 126, 207, 217, 253, 103, 103, 124>>
  },
  %{
    name: "rotated_img",
    image: %Vix.Vips.Image{ref: #Reference<0.2507745200.1059192849.55381>},
    dhash: <<0, 30, 62, 127, 123, 126, 124, 0>>
  },
  %{
    name: "cropped_img",
    image: %Vix.Vips.Image{ref: #Reference<0.2507745200.1059192849.55382>},
    dhash: <<126, 239, 223, 185, 236, 215, 199, 124>>
  },
    %{
    name: "with_text",
    image: %Vix.Vips.Image{ref: #Reference<0.2507745200.1059192849.55392>},
    dhash: <<56, 127, 207, 217, 253, 103, 103, 124>>
  },
  %{
    name: "other",
    image: %Vix.Vips.Image{ref: #Reference<0.2507745200.1059192849.55393>},
    dhash: <<248, 127, 127, 127, 63, 60, 14, 0>>
  }
]

dHash はグレースケール化やリサイズが影響しないため、先頭の3つは全く同じ値になっています

DB の準備

DB 接続用モジュールの定義

Ecto で PostgreSQL に接続するためのモジュールを用意します

defmodule Repo do
  use Ecto.Repo,
    otp_app: :my_notebook,
    adapter: Ecto.Adapters.Postgres
end

秘密情報の設定

DB接続のパスワードは秘密情報なので、 Livebook の秘密情報に登録しておきます

Livebook の左メニュー南京錠🔒のアイコンをクリックすると、 SECRETS のメニューが表示されます

+ New secrets をクリックしてください

表示されたモーダルの Name に DB_PASSWORD 、 Value にパスワードの値を入力し、 + Add をクリックします

これによって、 DB のパスワードは LB_DB_PASSWORD という環境変数に格納されました

Repo を子プロセスとして起動し、 DB に接続します

opts = [
  hostname: "postgres_for_livebook",
  port: 5432,
  username: "postgres",
  password: System.fetch_env!("LB_DB_PASSWORD"),
  database: "postgres"
]

Kino.start_child({Repo, opts})

{:ok, #PID<0.2572.0>} というような結果が表示されれば接続できています

テーブルの作成

image テーブル作成の Migration を定義します

dHash は 64 桁のビット配列なので、 bit 型のサイズ 64 を指定しています

defmodule Migrations.CreateImageTable do
  use Ecto.Migration

  def change do
    create table(:image) do
      add(:name, :string)
      add(:dhash, :bit, size: 64)
    end
  end
end

Migration を適用します

第2引数のバージョン番号は他で実行した Migration と重複しない値にしてください

Ecto.Migrator.up(Repo, 11, Migrations.CreateImageTable)

DB への登録

DB 操作用のモジュールを定義します

defmodule ImageSchema do
  use Ecto.Schema

  schema "image" do
    field(:name, :string)
    field(:dhash, :binary)
  end
end

画像名と dHash を image テーブルに追加します

img_list
|> Enum.map(fn map ->
  Map.delete(map, :image)
end)
|> then(&Repo.insert_all(ImageSchema, &1))

実行時ログ

12:02:09.298 [debug] QUERY OK db=3.8ms queue=3.4ms idle=1863.0ms
INSERT INTO "image" ("name","dhash") VALUES ($1,$2),($3,$4),($5,$6),($7,$8),($9,$10),($11,$12),($13,$14) ["original_img", <<56, 126, 207, 217, 253, 103, 103, 124>>, "gray_img", <<56, 126, 207, 217, 253, 103, 103, 124>>, "resized_img", <<56, 126, 207, 217, 253, 103, 103, 124>>, "rotated_img", <<0, 30, 62, 127, 123, 126, 124, 0>>, "cropped_img", <<126, 239, 223, 185, 236, 215, 199, 124>>, "with_text", <<56, 127, 207, 217, 253, 103, 103, 124>>, "other", <<248, 127, 127, 127, 63, 60, 14, 0>>]

実行結果

{7, nil}

7 件挿入できました

データを確認してみましょう

Repo.all(ImageSchema)

実行結果

[
  %ImageSchema{
    __meta__: #Ecto.Schema.Metadata<:loaded, "image">,
    id: 1,
    name: "original_img",
    dhash: <<56, 126, 207, 217, 253, 103, 103, 124>>
  },
  %ImageSchema{
    __meta__: #Ecto.Schema.Metadata<:loaded, "image">,
    id: 2,
    name: "gray_img",
    dhash: <<56, 126, 207, 217, 253, 103, 103, 124>>
  },
  %ImageSchema{
    __meta__: #Ecto.Schema.Metadata<:loaded, "image">,
    id: 3,
    name: "resized_img",
    dhash: <<56, 126, 207, 217, 253, 103, 103, 124>>
  },
  %ImageSchema{
    __meta__: #Ecto.Schema.Metadata<:loaded, "image">,
    id: 4,
    name: "rotated_img",
    dhash: <<0, 30, 62, 127, 123, 126, 124, 0>>
  },
  %ImageSchema{
    __meta__: #Ecto.Schema.Metadata<:loaded, "image">,
    id: 5,
    name: "cropped_img",
    dhash: <<126, 239, 223, 185, 236, 215, 199, 124>>
  },
  %ImageSchema{
    __meta__: #Ecto.Schema.Metadata<:loaded, "image">,
    id: 6,
    name: "with_text",
    dhash: <<56, 127, 207, 217, 253, 103, 103, 124>>
  },
  %ImageSchema{
    __meta__: #Ecto.Schema.Metadata<:loaded, "image">,
    id: 7,
    name: "other",
    dhash: <<248, 127, 127, 127, 63, 60, 14, 0>>
  }
]

きちんと登録できています

ちなみに psql からテーブルの内容を確認すると以下のようになります

postgres=# SELECT * FROM image;
 id |     name     |                              dhash
----+--------------+------------------------------------------------------------------
  1 | original_img | 0011100001111110110011111101100111111101011001110110011101111100
  2 | gray_img     | 0011100001111110110011111101100111111101011001110110011101111100
  3 | resized_img  | 0011100001111110110011111101100111111101011001110110011101111100
  4 | rotated_img  | 0000000000011110001111100111111101111011011111100111110000000000
  5 | cropped_img  | 0111111011101111110111111011100111101100110101111100011101111100
  6 | with_text    | 0011100001111111110011111101100111111101011001110110011101111100
  7 | other        | 1111100001111111011111110111111100111111001111000000111000000000
(7 rows)

ビット配列なことが分かりやすいですね

類似画像検索用 SQL の実行

いよいよ類似画像検索用 SQL を実行します

query =
  """
  SELECT
    src.name as src_name,
    dst.name as dst_name,
    bit_count(src.dhash # dst.dhash) as humming_distance
  FROM
    image AS src
  INNER JOIN
    image AS dst
  ON
    src.id < dst.id
  AND
    bit_count(src.dhash # dst.dhash) < 20
  ORDER BY
    humming_distance ASC
  """

{:ok, result} = Ecto.Adapters.SQL.query(Repo, query, [])

実行結果

{:ok,
 %Postgrex.Result{
   command: :select,
   columns: ["src_name", "dst_name", "humming_distance"],
   rows: [
     ["original_img", "resized_img", 0],
     ["original_img", "gray_img", 0],
     ["gray_img", "resized_img", 0],
     ["gray_img", "with_text", 1],
     ["original_img", "with_text", 1],
     ["resized_img", "with_text", 1],
     ["cropped_img", "with_text", 15],
     ["resized_img", "cropped_img", 16],
     ["gray_img", "cropped_img", 16],
     ["original_img", "cropped_img", 16],
     ["rotated_img", "other", 18]
   ],
   num_rows: 11,
   connection_id: 88,
   messages: []
 }}

確かにハミング距離が 20 未満の類似画像だけが抽出されたようです

回転画像と別画像もギリギリ類似画像として誤判定されていますが、その辺りは閾値調整で対応可能です

ポイントを確認してみましょう

自己結合

INNER JOIN で同じテーブル同士を結合することで、すべての組み合わせを探索しています

同じ画像同士の距離は必ず 0 になり、順番を入れ替えてもハミング距離は変わらないため、結合条件は src.id < dst.id です

...
    image AS src
  INNER JOIN
    image AS dst
  ON
    src.id < dst.id
 ...

ハミング距離の計算

bit_count(A # B) でハミング距離が計算できます

# が排他的論理和（XOR）の演算子で、 bit_count が 1 の個数なので、ハミング距離の定義そのものです

その他、ビット演算子は以下のようなものが使えます

演算子	演算内容
`
&	論理積(AND)
`	`
#	排他的論理和(XOR)
~	否定(NOT)
<<	左シフト
>>	右シフト

また、ビット演算用関数は以下のようなものがあります

関数	演算内容
bit_count	1 の個数を取得
bit_length	ビット数を取得
length	ビット数を取得
octet_length	バイト数を取得
overlay	指定した範囲の値を置換
position	指定したビット配列の位置を取得
substring	指定した範囲のビット配列を取得
get_bit	指定した位置のビットを取得
set_bit	指定した位置のビットを上書き

PostgreSQL でのビット演算の詳細については以下のドキュメントを参照してください

結果の視覚化

類似画像同士を並べて、確かに類似しているか確認しましょう

result.rows
|> Enum.map(fn [src_img_name, dst_img_name, distance] ->
  src_img = Enum.find(img_list, fn map -> map.name == src_img_name end) |> Map.get(:image)
  dst_img = Enum.find(img_list, fn map -> map.name == dst_img_name end) |> Map.get(:image)

  [
    distance,
    Kino.Layout.grid([src_img, dst_img], columns: 2)
  ]
  |> Kino.Layout.grid(columns: 1)
end)
|> Kino.Layout.grid(columns: 4)

一番最後のハミング距離 18 の組み合わせ以外は、確かに類似画像と言えそうです

まとめ

XOR 演算子の # と bit_count の組み合わせにより、 SQL でハミング距離を計算することができました

Livebook を使うことで、類似画像を簡単に並べて表示でき、確認作業も楽になります