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

## はじめに

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

https://qiita.com/RyoWakabayashi/private/9525d17bd9d7c0b12fc8

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

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

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

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

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

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

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

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

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

https://qiita.com/RyoWakabayashi/items/7f3e2c288259f6a0a955

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

https://qiita.com/RyoWakabayashi/items/76f9248757a488ac251e

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

SQL　だけ見たい方は[こちら](#類似画像検索用-sql-の実行)

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

https://github.com/RyoWakabayashi/elixir-learning/blob/main/livebooks/vix/dhash_with_db.livemd

## 参考記事

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

https://qiita.com/souten21kobayashi/items/8bcfad497910431ab573

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

## セットアップ

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

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

```elixir
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"}
])
```

## 画像の準備

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

```elixir
# 元画像
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)
```

![スクリーンショット 2023-11-01 20.39.37.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/6fd0d0c2-c77a-7748-fa5e-53ebf57ede98.png)

## ハッシュの計算

各画像の dHash を計算します

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

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

```elixir
[
  %{
    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 に接続するためのモジュールを用意します

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

### 秘密情報の設定

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

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

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

![スクリーンショット 2023-10-31 11.58.19.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/6c7fb00a-75b0-b38e-e06c-4c50c5e448ce.png)

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

![スクリーンショット 2023-10-31 12.00.02.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/2050fdb2-fe66-b6b3-a08a-aa6c8e24b15b.png)

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

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

```elixir
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 を指定しています

```elixir
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 と重複しない値にしてください

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

## DB への登録

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

```elixir
defmodule ImageSchema do
  use Ecto.Schema

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

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

```elixir
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>>]
```

実行結果
```elixir
{7, nil}
```

7 件挿入できました

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

```elixir
Repo.all(ImageSchema)
```

実行結果
```elixir
[
  %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 を実行します

```elixir
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, [])
```

実行結果
```elixir
{: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` です

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

### ハミング距離の計算

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

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

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

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

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

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

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

https://www.postgresql.jp/document/15/html/functions-bitstring.html

## 結果の視覚化

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

```elixir
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)
```

![スクリーンショット 2023-11-01 21.40.49.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/3a7e60bb-46af-d3a4-e48a-d5fd6e1bfe6e.png)

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

## まとめ

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

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