dhashを生成するライブラリ作った

先日参加した勉強会でdhashというものを初めて知りました。

読んでみると、すごく簡単なアルゴリズムで画像の類似度を計算していたので「これ、JSで書けるんじゃない？」と気軽に思ったのが地獄の始まりでした。

dhashってなに？

画像の類似度を計算するためのハッシュアルゴリズムです。
特徴としては以下のようです。

誤検知がほとんどない
高速(aHashやpHashと比べて)

なぜ作ろうと思ったのか

InstagramとかGoogle Photoみたいなサービスで、すでに登録してある画像を機械学習などを利用せずに検出できるだけでもメリットとしては大きそう。
また、類似度計算の性質上、バリデーションの用途で使われやすそうだがほとんどがバックエンド用で書かれているため、フロントエンド用に書けば通信のコスト減らせるくない？と思った。

dhashってどう作るの？

dhashの生成手順は以下です。

画像を9x8にリサイズします。
グレースケールに変換します。
右隣と比較して現在の値が小さければ1、それ以外は0として扱います。(右端は計算しない)
bitとして扱います。

日本語の詳しい内容もあって、アルゴリズムの概要自体はとてもわかりやすかったです。
この生成手順は情報元？を参考にしたものだが、実際に実装してみたらそんなに簡単にはいきませんでした。

ハマったポイント

ハマったポイントは以下です。

JSで64bitは簡単に扱えないよ
リサイズアルゴリズムが不明だよ
グレースケールアルゴリズムが不明だよ

JSで64bitを簡単には扱えないよ

JSでよくある2進数 -> 16進数の変換方法が以下です。

1 2	// 1 parseInt('1', 2).toString(16);

おわかりかもしれませんが、一旦Number型にしているので大きな数値を扱う時は桁が溢れて違う数値になります。

1 2	// 40000000000000 parseInt('111111111111111111111111111111111111111111111111111111', 2).toString(16);

これは、4文字づつの配列にして16進数に変換するようにしました。

const array = '111111111111111111111111111111111111111111111111111111';
const chunk = 4;
const chunkedArray = [...Array(Math.ceil(array.length / chunk)).keys()]
    .map(index => array.slice(index * chunk, (index * chunk) + chunk));
console.log(chunkedArray.map(row => parseInt(row.join(''), 2).toString(16)).join(''));

リサイズアルゴリズムが不明だよ

世の中には、リサイズアルゴリズムが複数あります。
PythonのPillowでサポートされているアルゴリズムでも6種類あります。
どれかわかりませんでしたが、結果としてはLanczosにしました。
ライブラリとして実装する上で、他のライブラリとハッシュ値が異なると非常に使いにくいものになってしまいます。

私のアプローチは以下です。

何も考えずブラウザにリサイズさせてみる。
ライブラリ探す。
JSから逃げる。
リサイズアルゴリズムを自前で実装する。
ライブラリ探す。(再度)

ブラウザにリサイズさせてみる。

ブラウザで以下のように実装しました。

const image = new Image();
const canvas = document.createElement('canvas');
image.width = 9;
image.height = 8;
image.onload = () => {
	const ctx = canvas.getContext('2d');
	ctx.drawImage(image, 0, 0, image.width, image.height);
	const colorMap = ctx.getImageData(0, 0, image.width, image.height);
};
image.src = './test.png';

似たようなハッシュ値は確かに取れますが、ブラウザによって結果が変わります。
これは、drawImageの第7,8引数でリサイズしても、一緒です。
変わるとしたらCSSの image-rendering プロパティで多少の違いはあれど、意図した結果は得られませんでした。

ライブラリを探す。

まずは、ハッシュ値が他のライブラリと異なっては困るので、Pythonのimagehashを読むところから始めました。
ここで
imagehashのdhashの実装を見て初めて Lanczos という補正アルゴリズムでリサイズされているか知りました。
どうやら Pillowでは ANTIALIAS -> Lanczos のようです。
そのためimagehashでは Lanczos を利用していることが伺えます。

JSではLanczosをサポートしているライブラリとしてfabricというものが見つかったので試してみましたが、意図した結果は得られませんでした。
そもそも Lanczos とはどんなアルゴリズムなのか知る必要があると思いこのサイトを読みました。

調べていく中で、ソースが付属しているフリーソフトなどを見かける機会もあったが、座標（距離）の小数部を丁寧に処理していないために、Lanczos関数の値が正確に計算できていない物もあった。
たとえLanczos関数を使ったとしても、距離の計算が雑では高品質な画像は得られない。

とあり、なるほど。
浮動小数点に弱いJSで頑張ろうとするあたりがダメなんじゃないか？
と思うようになりました。

JSから逃げる。

次のアプローチとして、JSが苦手な土俵をわざわざJSで戦う必要はないなと思ったので、WebAssemblyを使おうと思いました。
今回はImageMagickのWebAssemblyのプロジェクトを利用することにしました。

意図通りの結果を得ることはできました。🎉
ブラウザ上でImageMagickが動くことに感動しました。OSSに感謝。
しかし、以下が問題です。

wasmとjsファイルをコピーする必要がある。
バグっている。(ちょっと書き換えれば治る。issue作成済み。)

リサイズアルゴリズムを自前で実装する。

TypeScriptにはbigintもあるし、浮動小数点を扱うためのライブラリも数多く出ているので、それらを使ってリサイズしてみることにしました。
ちなみに、TypeScript DeepDiveにも書いてある通りパフォーマンスに影響を及ぼす可能性が高いが、この際正しい結果が得られるのであれば無視します( 過程や…！方法なぞ…！どうでもよいのだァーッ)。
このあたりで、正直自分の思考が正気ではないのを感じましたが、後には引けない(お盆を全て潰して娘が泣いている隣でコードを書く)状況でしたので諦めませんでした。

頑張って書いた結果、意図通りの結果を得ることはできませんでした。

また、256x256を9x8にリサイズするので12sもかかる有様でした。

ライブラリを探す。

一つ前のステップでリサイズアルゴリズムを実装して思ったのが、JSで Lanczos と謳われているものはほとんど同じようなコードでした。
その点を踏まえてGitHubで Lanczos で検索して片っ端から自分の実装と似ていないライブラリを探しているとStar数やFork数は少ないが自分とは異なる方法でLanczosのリサイズを実装しているライブラリを見つけました。

このライブラリで、実装してみた結果意図通りの結果を得ることができました。
しかも、高速で256x256を9x8で60msぐらいでリサイズすることができました。

正直、Lanczosでこの速度はcrazyだと思います。
なぜ、こんなに速いのか、なぜ正しい結果が得られるのかは後でちゃんとロジックを読んでみようと思います。
OSSに感謝。

グレースケールアルゴリズムが不明だよ

グレースケールもリサイズと同じでいっぱいありました。

Pythonのimagehashを参考にするとITU-R 601-2 lumaとなっていました。

ご丁寧に計算式までドキュメントに記載されていますのでこのまま流用しました。

まとめ

dhashを作りたい時は以下の手順で作ります。

画像を9x8にリサイズします。(Lanczos lobs 3)
グレースケールに変換します。(ITU-R 601-2 luma)
右隣と比較して現在の値が小さければ1、それ以外は0として扱います。(右端は計算しない)
bitとして扱います。

また、この情報は、とりあえずimagehashを参考にしただけで別の正しいdhashの仕様とかあれば教えてください。
余談ですが、imagehashで生成したハッシュは情報元？の画像をハッシュ化しても同じハッシュ値にはなりませんでした。😭

あと、こんな感じの新しい知見に触れられる勉強会はNFUGです。

良かったこと

画像縮小アルゴリズムやグレースケールのアルゴリズムとかが勉強になった。
途中でJSをやめてWebAssemblyに逃げたのは良いアプローチだと思った。
難しいアルゴリズムでも実装してみれば割と理解が深まると思った。

良くなかったこと

指針を決めずに作り始めたので、どのアルゴリズムにするかの判断が遅くなった。
openにしたくないモジュールまでopenにしてしまっている。
ロジックを理解していないままライブラリを使った。
Canvasのテストがめんどくさすぎてテストが雑になってしまった。

次にやりたいこと

ライブラリのロジックを理解する。
WebGLでLanczosをサポートしてそうなのでやってみる。
WebAssemblyをつかって何か書いてみる。