WebAssembly と dHash による軽量な画像重複判定の実装

この記事について

• 画像の重複排除や類似検索で用いられる「知覚ハッシュ（Perceptual Hash, 略して pHash）」という手法に興味を持ったのでクラウド上で簡単に実装してみました。
• pHashは「見た目の近さを64ビット程度のビット列で要約する」方法で、代表的な方式には　pHash / dHash / aHash　がありますが、今回は計算が速く実装が簡単な dHash（64ビット）を採用します。
• 比較方法としては、dHashで取得した 64ビット のハッシュ同士の違っているビット数（= ハミング距離）を計算し、距離 ≤ 閾値（DEDUP_THRESHOLD）なら同じ画像、それ以外は別の画像として扱います。（距離は XOR の結果に含まれる 1 の数＝ハミング距離で求めます。）
• dHash の実装はできるだけ高速になるよう Rust で書いた処理を WebAssembly（Wasm）にコンパイルし Node.js から呼び出す形にします。
• なお、本記事内の実装では imgfp = image fingerprint（知覚ハッシュを使った指紋）の略称をモジュール名として用いています。

構成について

• アーキテクチャは S3 → EventBridge → Lambda（Node.js＋Rust→Wasm）→ DynamoDB で実装します。

ビルド環境

• Node.js v20.12.2
• Rust 1.89.0
• wasm-pack 0.13.1

セットアップ（Wasm コンパイル & TypeScript ビルド）

1) ディレクトリ構成

.
├── functions/indexer/{Makefile,src/{handler.ts,common.ts}}
├── layers/imgfp-wasm/nodejs/node_modules/imgfp/pkg/{imgfp.js,imgfp_bg.wasm,package.json}
├── template.yaml
└── wasm/{Cargo.toml,src/lib.rs}

2) Wasm（Rust→wasm-pack）をビルドして Layer に配置

Rust コードを Wasm にコンパイルして Layer に配置するために、wasm/ ディレクトリで以下を実行します。

cd wasm

# コンパイル先の環境をWebAssemblyに指定
rustup target add wasm32-unknown-unknown

# wasm-pack をインストール（未インストールの場合）
cargo install wasm-pack --locked

# ビルドして Layer 階層へ出力
wasm-pack build --release --target nodejs \
  --out-dir ../layers/imgfp-wasm/nodejs/node_modules/imgfp/pkg

出力先は後述の template.yaml の layer と一致させています。

3) SAM でビルド & デプロイ（Makefile を利用）

今回は TypeScript で Node.js の処理を実装したので、template.yaml の関数 IndexerFunction に BuildMethod: makefile を指定し、Makefile で TypeScript のビルドを実行するようにしました。

template.yaml

IndexerFunction:
  Type: AWS::Serverless:Function
  Properties:
    CodeUri: functions/indexer/
    Handler: dist/handler.handler
    Layers: [ !Ref WasmLayer ]
    ~~~ 略 ~~~
  Metadata:
    BuildMethod: makefile

Makefile

.PHONY: build clean build-IndexerFunction clean-IndexerFunction

build:
    npm ci || npm i
    npx tsc -p tsconfig.json

build-IndexerFunction: build
    npm prune --omit=dev || true
    mkdir -p $(ARTIFACTS_DIR)
    cp -r dist $(ARTIFACTS_DIR)/
    cp -r node_modules $(ARTIFACTS_DIR)/
    cp package.json $(ARTIFACTS_DIR)/

clean:
    rm -rf node_modules dist
clean-IndexerFunction: clean

template.yaml について

環境変数

同じ画像とみなす閾値として環境変数 DEDUP_THRESHOLD を用意します。（この値以下なら重複画像と判定)

Environment:
  Variables:
    DEDUP_THRESHOLD: 6   

Layer

前提として、前述の wasm-pack build により layer 配下は下記のようになっています。

├── layers
│   └── imgfp-wasm
│       └── nodejs
│           └── node_modules
│               └── imgfp
│                   └── pkg #下記がコマンドにより生成
│                        ├── imgfp.d.ts
│                        ├── imgfp.js
│                        ├── imgfp_bg.wasm
│                        ├── imgfp_bg.wasm.d.ts
│                        └── package.json

template.yamlの layer では下記のように ContentUriに layers/imgfp-wasm/ を指定します。 SAM ビルド時に /opt/nodejs/node_modules/ が自動生成されるため、ローカルの layer もこれに合わせて構成しておくと、デプロイ後に imgfp 配下がそのままコピーされ、lambda 実行環境から通常のモジュールのように読み込めるようになります。

WasmLayer:
  Type: AWS::Serverless::LayerVersion
  Properties:
    LayerName: imgfp-wasm
    ContentUri: layers/imgfp-wasm/ 
    CompatibleRuntimes: [ nodejs20.x ]

DynamoDB

後述の処理では 64ビット の dHash を 16ビット×4 に分割して hashPart0〜3 として登録します。それらをGSIに設定しました。

MediaTable:
  Type: AWS::DynamoDB::Table
  Properties:
    BillingMode: PAY_PER_REQUEST
    TableName: MediaTable
    AttributeDefinitions:
      - { AttributeName: assetId,   AttributeType: S }
      - { AttributeName: createdAt, AttributeType: N }
      - { AttributeName: hashPart0,   AttributeType: S }
      - { AttributeName: hashPart1,   AttributeType: S }
      - { AttributeName: hashPart2,   AttributeType: S }
      - { AttributeName: hashPart3,   AttributeType: S }
    KeySchema:
      - { AttributeName: assetId,   KeyType: HASH }
      - { AttributeName: createdAt, KeyType: RANGE }
    GlobalSecondaryIndexes:
      - IndexName: GSI_hashPart0
        KeySchema:
          - { AttributeName: hashPart0, KeyType: HASH }
          - { AttributeName: createdAt, KeyType: RANGE }
        Projection: { ProjectionType: ALL }
      - IndexName: GSI_hashPart1
        KeySchema:
          - { AttributeName: hashPart1, KeyType: HASH }
          - { AttributeName: createdAt, KeyType: RANGE }
        Projection: { ProjectionType: ALL }
      - IndexName: GSI_hashPart2
        KeySchema:
          - { AttributeName: hashPart2, KeyType: HASH }
          - { AttributeName: createdAt, KeyType: RANGE }
        Projection: { ProjectionType: ALL }
      - IndexName: GSI_hashPart3
        KeySchema:
          - { AttributeName: hashPart3, KeyType: HASH }
          - { AttributeName: createdAt, KeyType: RANGE }
        Projection: { ProjectionType: ALL }

Wasm（Rust）の実装について

画像を dHash に変換する wasm/src/lib.rs の実装について紹介します。

wasm-bindgen アトリビュートをつけることで Rust を Wasm 化した際に、JS から呼び出せる関数としてエクスポートされます。

実装の詳細はコメントをご確認ください。

use wasm_bindgen::prelude::*;
use image::{load_from_memory, imageops::FilterType};

// JSから呼び出せるようにwasm_bindgenでエクスポート
#[wasm_bindgen]
pub fn dhash_from_bytes(bytes: &[u8]) -> String {
    // load_from_memoryで画像をデコードしてgrayscaleでグレースケールにする
    let img = load_from_memory(bytes).expect("decode").grayscale();

    // dHash の差分比較用に 9×8 に縮小
    // リサイズアルゴリズム(FilterType)は任意。（今回は高品質というLanczos3にしました。）
    let img9x8 = image::imageops::resize(&img, 9, 8, FilterType::Lanczos3);　

    // 隣接する画素（x と x+1）の輝度差でビット列を作る
    // 64 ビットのハッシュを初期値0で用意
    let mut hash: u64 = 0;
    // 二重ループ (y=0..8, x=0..8) で縦8行、横8列の差分を走査する
    for y in 0..8 {
        for x in 0..8 {
            // get_pixelでピクセルをRGBAとして取得する
            // grayscale済みなのでR=G=Bに同じ明るさの値（輝度）がコピーされ、Aは255になる
            // R([0])を取れば、そのピクセルの輝度値として扱える
            let p = img9x8.get_pixel(x, y)[0];
            let q = img9x8.get_pixel(x + 1, y)[0];
            // 末尾に空きビット0を追加
            hash <<= 1;
            // 真なら末尾を1に変更、偽ならそのまま
            if p > q { hash |= 1; }
        }
    }
    // 返り値は `"0x........"` の16進文字列にする
    format!("0x{hash:016x}")
}

Lambdaの実装について

functions/indexer/src/の実装について紹介します

下記の流れで処理を実行します。
1. S3 にアップロードされた画像を Wasm 経由で dHash に変換
2. 64ビット ハッシュを 16ビット×4 に分割し、それぞれの値に対応する GSI を検索して候補を取得
3. 候補に対してハミング距離を算出し、閾値以下なら重複と判定して削除
4. 重複でなければインデックスを書き込む

functions/indexer/src/handler.ts

import { S3Client, GetObjectCommand, DeleteObjectCommand } from "@aws-sdk/client-s3";
import { DynamoDBClient } from "@aws-sdk/client-dynamodb";
import { DynamoDBDocumentClient, PutCommand, QueryCommand } from "@aws-sdk/lib-dynamodb";
import * as wasm from "imgfp/pkg/imgfp.js";  // WasmをLayerから取得
import { splitBands, hamming64, requireEnv, streamToBuffer } from "./common.js";

const s3 = new S3Client({});
const ddb = DynamoDBDocumentClient.from(new DynamoDBClient({}));
const TABLE_NAME = requireEnv("TABLE_NAME");
// dHashのハミング距離の閾値
const DEDUP_T = Number(process.env.DEDUP_THRESHOLD ?? 6);

// Wasm初期化
let wasmInited = false;
async function ensureWasm() {
  if (wasmInited) return;
  if (typeof (wasm as any).default === "function") await (wasm as any).default();
  wasmInited = true;
}

export const handler = async (event: any) => {
  await ensureWasm();

  // バケット名とキーの特定
  const bucket = event?.detail?.bucket?.name as string | undefined;
  const keyRaw = event?.detail?.object?.key as string | undefined;
  if (!bucket || !keyRaw) { console.error("Unsupported event", event); return { statusCode: 400 }; }
  const key = decodeURIComponent(String(keyRaw).replace(/\+/g, " "));

  // 画像取得
  const { Body, ETag, ContentType, ContentLength } = await s3.send(
    new GetObjectCommand({ Bucket: bucket, Key: key })
  );
  const buf = await streamToBuffer(Body);

  // dHash を 16ビット×4 に分割
  const pHash64 = (wasm as any).dhash_from_bytes(new Uint8Array(buf));
  const { b0, b1, b2, b3 } = splitBands(pHash64);

  // GSI×4に並列クエリを投げる
  // KeyConditionExpressionで "hashPartX = :v" の完全一致検索をする
  const bands: [string, string, string][] = [
    ["GSI_hashPart0", "hashPart0", b0],
    ["GSI_hashPart1", "hashPart1", b1],
    ["GSI_hashPart2", "hashPart2", b2],
    ["GSI_hashPart3", "hashPart3", b3],
  ];
  const pages = await Promise.all(bands.map(([IndexName, keyAttr, v]) =>
    ddb.send(new QueryCommand({
      TableName: TABLE_NAME,
      IndexName,
      KeyConditionExpression: `${keyAttr} = :v`,
      ExpressionAttributeValues: { ":v": v },
      ProjectionExpression: "assetId, pHash64, s3Key, createdAt",
      Limit: 100, ScanIndexForward: false
    }))
  ));

  // 4クエリの結果を assetId で重複排除してマージする
  // 同じレコードが複数のGSIでヒットする可能性があるのでMapに入れて重複削除
  const candidateMap = new Map<string, any>();
  for (const p of pages) for (const it of (p.Items ?? [])) candidateMap.set(it.assetId, it);

  // 候補から最も近い重複を探す処理
  const dup = [...candidateMap.values()]
    // 既存レコードのハッシュ（it.pHash64）と、今回の画像のハッシュ（pHash64）を比較。
    .map(it => ({ it, dist: hamming64(it.pHash64, pHash64) }))
    // 類似度が高い(閾値以下)のレコードのみにフィルタ
    .filter(x => x.dist <= DEDUP_T)
    // ハミング距離の小さい順に並べ、一番近い1件を取り出す
    .sort((a, b) => a.dist - b.dist)[0];

  if (dup) {
    // 重複していた場合は S3 から新規オブジェクトを削除
    await s3.send(new DeleteObjectCommand({ Bucket: bucket, Key: key }));
    // ハミング距離をdistとして出力
    console.log("DEDUP: deleted", { key, dupOf: dup.it.assetId, dist: dup.dist });
    return { statusCode: 200 };
  }

  // 未重複の場合はインデックスを登録
  const item = {
    assetId: (ETag || key).replaceAll('"', ""),
    createdAt: Date.now(),
    s3Key: key,
    mime: ContentType || "application/octet-stream",
    size: ContentLength ?? buf.length,
    pHash64, hashPart0: b0, hashPart1: b1, hashPart2: b2, hashPart3: b3
  };
  await ddb.send(new PutCommand({ TableName: TABLE_NAME, Item: item }));
  console.log("Registered:", item.assetId);
  return { statusCode: 200 };
};

functions/indexer/src/common.ts

export function requireEnv(name: string): string {
  const v = process.env[name];
  if (!v) throw new Error(`Env ${name} is required`);
  return v;
}

// 64ビットハッシュを16ビット×4に分割
export function splitBands(hex64: string) {
  const s = hex64.startsWith("0x") ? hex64.slice(2) : hex64;
  return {
    b0: "0x" + s.slice(0, 4),
    b1: "0x" + s.slice(4, 8),
    b2: "0x" + s.slice(8, 12),
    b3: "0x" + s.slice(12, 16),
  };
}

// 64ビット同士のハミング距離を計算
// ビットの違いで類似度を測る
// 完全一致なら0、完全不一致なら64になる
export function hamming64(aHex: string, bHex: string): number {
  const a = BigInt(aHex);
  const b = BigInt(bHex);
  let x = a ^ b; // XORで異なるビットが1の数列を作る
  let c = 0; //　カウンタ
  while (x) {
    c += Number(x & 1n);　// xの最下位ビットが1ならカウントを+1
    x >>= 1n;　// 右シフトして次のビットを調べる
  }
  return c;
}

// ストリームを一つのBufferにまとめる
export async function streamToBuffer(stream: any): Promise<Buffer> {
  const chunks: any[] = [];
  for await (const c of stream) chunks.push(c);
  return Buffer.concat(chunks);
}

動作確認とログ

1)　1回目の画像が登録されることを確認

aws s3 cp ./test.png "s3://$BUCKET/test/test.png"
aws logs tail /aws/lambda/imgfp-indexer --since 2m --follow

登録されているログが確認できました。

INFO Registered: 25c9674ed8db798a2a8b17c1f3671218

2) 同じ画像を再アップし削除（DEDUP）されることを確認

aws s3 cp ./test.png "s3://$BUCKET/test/test-dup.png"
aws logs tail /aws/lambda/imgfp-indexer --since 2m --follow

削除されているログが確認できました。

INFO DEDUP: deleted {
  key: 'test/test-dup.png',
  dupOf: '25c9674ed8db798a2a8b17c1f3671218',
  dist: 0
}

3) 彩度を落とした同一画像が登録されるかを確認

aws s3 cp ./test-2.png "s3://$BUCKET/test/test-2.png"
aws logs tail /aws/lambda/imgfp-indexer --since 2m --follow

登録されているログが確認できました。
DEDUP_THRESHOLD:6 では別画像として判定されているようです。

INFO    Registered: ffdef329a759806bac21630cf30a0bde

4) 閾値を変更し、同じ彩度落ち画像で 削除（DEDUP） になることを確認

画像を削除した上で、今度はDEDUP_THRESHOLDを 10 に変更して試してみます。閾値を上げることで同一画像として判定され削除される想定です。

template.yaml

Environment:
  Variables:
    DEDUP_THRESHOLD: 10

aws s3 cp ./test-2.png "s3://$BUCKET/test/test-2.png"
aws logs tail /aws/lambda/imgfp-indexer --since 2m --follow

削除されているログが確認できました。dist（ハミング距離）は 8 となっており、
閾値 6 のときは別画像、閾値 10 に上げると同一画像として判定されることが確認できます。

INFO    DEDUP: deleted {
  key: 'test/test-2.png',
  dupOf: '25c9674ed8db798a2a8b17c1f3671218',
  dist: 8
}

感想

Hash とハミング距離を使った重複判定をシンプルに実装することができました。少しのコードで同一画像かどうかを判定できるのは面白いところだと思います。 AI を使った画像解析の話などよく耳にしますが、その前処理や軽量なフィルタリング用途として利用できそうだと感じました。

また、以前 Python＋Wasmtime を使ってみたときに比べると、Node.js ランタイムは Wasm 実行を標準でサポートしているため、統合までの流れがかなり楽でした。実際に比較してみて扱いやすさを確認できました。