２年前に書いたこのブログエントリの続きのような内容です：
類似画像検索とカラーヒストグラム


類似画像検索を実現するアルゴリズムを調べています。上記のブログエントリでは「カラーヒストグラム」と呼ばれる比較的簡単な方法を紹介しました。今回は Average Hash と呼ばれる方法を紹介します。


まず、この方法は名前に "Hash" というキーワードがついています。一般的なハッシュ（ハッシュ値、ハッシュ関数）では入力値が少しでも異なっていると出力値が全然別の値になる、という特徴があり、その特徴をいかしてパスワード（のハッシュ）を安全に保存したり、ブロックチェーンに応用されたりしています。

ただ今回紹介する Average Hash アルゴリズムで使われるハッシュはその点で意味合いが少し異なり、入力されたデータが似ていた場合に似た値を返すようなハッシュ関数を定義します。このようなハッシュ関数を使って、用意された画像のハッシュ値をあらかじめ求めておきます。そして類似画像を探したい画像についても同じハッシュ関数でハッシュ値を求め、そのハッシュ値が似ている画像は入力データが似ているはずと判断して回答の候補とする、という考え方に基づいた類似画像検索アルゴリズムです。つまり画像として類似しているかどうかを、比較演算が容易なハッシュ値の差で判断しよう、というものです。


より具体的にアルゴリズムを紹介します。例えばハッシュ関数を以下のように定義したとします：

• 画像のバイナリデータをハッシュ関数の入力値とする
• ｎｘｎ　のサイズを持つ整数配列がハッシュ関数の出力値とする。なおｎは整数値とする
• ハッシュ関数内ではまず画像を正規化する。具体的には入力画像を縦ｎピクセル、横ｎピクセルにリサイズし（画素数はｎｘｎ）、更にグレースケール変換する
• 次にｎｘｎにグレースケールされた画像の各ピクセルの色の濃さ（0～255）を調べ、その値の平均値 avg を求める
• 再度ｎｘｎにグレースケールされた画像の各ピクセルの色の濃さを調べ、その値が avg 以上であればそのピクセルの値は 1 、avg 未満であれば 0 とみなす。これをｎｘｎピクセル分求めて配列にする
• この配列をハッシュ関数の出力値とする

これだけだと理解しにくいと思ったのでもう少し詳しく順を追って説明します。なお以下の例では n = 16 の例を紹介します。

ハッシュ関数への入力データを以下の画像とします（ちなみにいらすとや様からの画像で、元のサイズは 737x800 ピクセルです）：




ハッシュ関数ではこの入力画像をまず 16x16 にリサイズし、かつグレースケール化して正規化します。この時点で画像のピクセル数は (16x16=)256 です：



この (16x16=)256 個のピクセルを左上から１つずつ取り出して RGB 値を調べます。この値は 0 から 255 の間の整数値で、0 に近いほど黒っぽく、255 に近いほど白っぽいことを意味しています。実際には 16 行ありますが、最初の３行はこのような感じでした：



こうして 256 個のピクセルの RGB 値の平均値 avg を求めます。この例では avg = 198.763 であったとします。

改めて 256 個のピクセルの RGB 値をこの avg と比較します。ピクセルの RGB 値が avg 以上だった場合は 1 、avg 未満だった場合は 0 とみなしていきます：



この avg と比較した結果を画像の左上から順に並べて配列にします（下図では16個ごとに改行して実際の２次元イメージに近い形にしていますが、実際は改行せずに１次元配列とみなします）：



この配列がハッシュ値となります。なんとなく元画像の中で白っぽい部分を 1 、黒っぽい部分を 0 とした結果になっていることがわかります。また、このハッシュアルゴリズムだと元画像が似ていると関数実行結果のハッシュ値も似る、ということが理解しやすいと思います。しかもハッシュ値は整数 256 個の配列なので類似性の判断も容易です。

なお、別のこちらの画像（サイズは 470x628）で同じアルゴリズムを実行すると、



結果はこのようになりました：



どのような画像に対してもまず同じサイズのグレースケール画像に変換しています（つまりグレースケールになった状態での類似性を調べるアルゴリズムです）。また各ピクセルを「その画像の各ピクセルの明るさの平均値よりも明るいか暗いか」で 0 または 1 に変換しています。これによって画像そのものが明るいものだったり暗いものだったりする要素を取り除き、その画像の中での明るい部分と暗い部分に分けるようにしています。そしてその結果がどれだけ似ているのか／似ていないのかを整数配列の類似度という比較的簡単な方法で調べられるようにしている、という特徴があることがわかりますね。


このアルゴリズムを使ってあらかじめ用意した画像の Average Hash 値を調べておきます。そして類似した画像を調べたい画像データが送られてきた場合にまず同じアルゴリズムで 256 個の１次元配列である Average Hash 値を求めれば、「0 と 1 が一致している数が多いほど似ている」と判断できることになります。

この方法であれば（実行パフォーマンスの様子を見ながらではありますが）ｎの値を大きくしたり、Hash 値を 0 か 1 にするのではく RGB 値をそのまま使って nxn 次元のユークリッド距離を求めることでより精度の高い類似画像検索が可能になります。あるいは別の応用としてグレースケールの手続きを省略して、カラー画像のまま比較することも可能です。


という、類似画像検索のアルゴリズムの１つを紹介しました。そんなに難しい数学知識を必要とせず、比較的理解も実装も応用もしやすいアルゴリズムだと思っています。

タグ ：

#similar

#image

#average

#hash

#averagehash

僕自身はオープンソース製品である Hyperledger Fabric や Hyperledger Composer を使ったブロックチェーンプラットフォームや、その対応アプリケーションを業務で開発する機会が多くあります。

ありがたいことに実際に作る機会も多いのですが、「作る」という決断に到達する前に方針を変更することも少なくありません。よくある理由としては「（現行の）ブロックチェーンに向かない要件」であるというケースです。パフォーマンス要件だったり、検索機能の要件だったり、現在のブロックチェーンでは本格運用に向かないケースが前提になっていたりすると、そのことを伝えた上で「それでも作るかどうか」を判断していただいています。そして「作らずに検討し直す」と判断されることもある、という意味です。

でも、これはブロックチェーンを使いたいと思いながらも「現在のブロックチェーン技術」では向かない、と判断されたからです。需要としては存在していることも意味しています。

そんな場面を多く見ている中で「だったらブロックチェーンといえるかどうかはともかく、同じような仕組みで耐改竄性を高めながら、この要件も満たせるようなデータストアの仕組みを作れないか？」と考えるようになりました。それが今回紹介するものです。


【「ブロックチェーン」の定義】
まず最初に、以下で紹介するアプリケーションは「ブロックチェーン」と呼べるものかどうかと言われると、私個人的には「呼べないのではないか」と考えています。これは「ブロックチェーンの定義」をどのようにするか、という問題にも関わってくるのですが、ここでは１つの目安として、JBA（"Japan Blockchain Association" 日本ブロックチェーン協会）が定義した以下の２つの定義を満たすものをブロックチェーンと定義するものとします：

・ビザンチン障害を含む不特定多数のノードを用い、時間の経過とともにその時点の合意が覆る確率が0へ収束するプロトコル、またはその実装をブロックチェーンと呼ぶ。
・電子署名とハッシュポインタを使用し改竄検出が容易なデータ構造を持ち、且つ、当該データをネットワーク上に分散する多数のノードに保持させることで、高可用性及びデータ同一性等を実現する技術を広義のブロックチェーンと呼ぶ。

（参照）
http://jba-web.jp/archives/2011003blockchain_definition





要するに「ブロックチェーンとは『ブロック』が『チェーン』のようにつながって格納される仕組み」というゆるい定義ではなく（注　私個人的にはこれがブロックチェーンの定義でもいいと思ってます）、「ハッシュポインタを用いて接続し、データを複数のノード上に分散して保持し、かつその複数ノードが耐ビザンチン障害性を持っている実装」のことを「ブロックチェーン」と定義する、ということです。　そしてこの定義の上で考えた場合、以下で紹介するものはブロックチェーンではない、ということになることを予め伝えておきます。

自分の考えは、上記のものだと耐ビザンチン障害性をもたせるためのコンセンサスアルゴリズムに問題が発生したり（最近だと「51%攻撃」と呼ばれる手法が話題になりました）、そのためにトランザクションのパフォーマンスを高く実現するのが難しかったりする、と思っています。なのでこの要件が必須でないケースでは、この条件を確保しないことでパフォーマンスや検索機能など他の要件機能を向上させることができるのではないかと考えました。


【色々出てきている】
現状のブロックチェーンにはパフォーマンス遅延や電力消費など当初は想定していなかったことが問題になっていることもあって、それらの苦手部分に対処した新しい仕組みも生まれています（それらが上記ブロックチェーンの定義を満たしているかどうかはともかく）。例えば全参加者のコンセンサスを得る上でのパフォーマンス遅延を解決するために、ランダムに選ばれた一部参加者のコンセンサスを得るように改良したものも出ているようです：
ブロックチェーンを超える？ハッシュグラフ（Hashgraph）とは？


【作ってみようと思ったもの】
今回、自分は以下４つの特徴を持つようなデータストアシステムを新たに開発してみようと思いました：
（１）ハッシュポインタを利用した、改竄検出が容易なブロックチェーンの仕組みはそのまま取り入れる
（２）データは中央集権管理型とする。これによりコンセンサスアルゴリズムや耐ビザンチン障害性の問題を発生させなくした上で、トランザクションパフォーマンスの向上を実現する
（３）データそのものは分散データストアに格納して（格納可能にして）高可用性を実現する。つまり単なる１ピア運用とは異なる
（４）バイナリデータやファイル添付を含む大きなレコードのデータストアへの格納や全文検索機能、データを読み書きするための REST API を標準装備する


（２）の時点で上記ブロックチェーンの定義を満たさなくなっています（ブロックチェーンは非中央管集権管理型）。（３）ただ単に１ピアにデータを格納するのではなく、論理的な１データストアが実際には複数のロケーションに分散できるようにしており、これにより特定ロケーションが単一障害点とはならないようにします。そして（４）ブロックチェーンが比較的苦手とする巨大オブジェクトの格納や検索機能もこのシステムでは標準装備することを目標としています。加えて標準で REST API を準備することで（導入すればすぐ使えるようになって）導入時の負担軽減も実現するつもりです。





【作っているもの】
上記仕組みを実現するためのソフトウェア（というかプラットフォームというか、API 群というか・・）を開発中です。まだ開発中ですが Github にて MIT ライセンスで公開しています：
https://github.com/dotnsf/hashchainsolo


上記の事情もあり、開発コード名には「ブロックチェーン」は含めず「ハッシュチェーンソロ」という表現にしました。レコードのブロックをチェーンのようにつなげていくものではあるのですが、上述の定義を満たすようなものではなく（むしろそこを犠牲にしている）、自分も「ブロックチェーン」という表現にこだわるわけではないので「ハッシュチェーン」という表現にしたかったのですが、これはこれで別の意味に使われており、ややこしいことになりそうだったので（ブロックチェーンだと単一ピアに相当する設計になるという意味で）「ハッシュチェーンソロ」と命名しています。某○icrosoft Office 365 Solo の影響とかではありませんｗ

インフラとして、分散データストアには IBM Cloudant を採用しています。Apache CouchDB をベースとした NoSQL 型のマネージド DBaaS で、容量・トランザクションパフォーマンスに制約があるものの無料プランを選択することもできるので、「とりあえず動作確認してみる」ためのハードルは低く実現できると思っています。一方でプランを見直して容量やパフォーマンスを変えたり、要件によってはプライベートクラウド版やオンプレミスソフトウェア版を使うことも可能です。またこの Cloudant 自体がバイナリ（添付ファイル）格納や検索インデックスといった機能を内包しているので、ブロックチェーンでいうところの「ステート DB」に相当する仕組みや外部ファイルシステム等がなくても各種データを格納することができ、上述の４つの特徴を兼ね備えた単独の仕組みを比較的作りやすいと思っています。

＃現時点では実装していない余談ですが、IBM Cloudant をデータストアに使っていることで、携帯版の PouchDB と組み合わせてモバイルプラットフォームへの移植も想定しやすい設計にしています。

ハッシュポインタを使って耐改ざん性を高める部分は全てスクラッチで実装しています。タイムスタンプと nonce を併用してマイニングを行い、特定条件（変更可）を満たした時だけハッシュを採用できるようにしています。

2018/Jun/30 の現時点での開発状況は「とりあえず一通りの REST API は動くようになっている」レベルです。時間を見つけてぼちぼちと改良中です。


【Call for Code】
この製品で Call for Code に参加予定です。自然災害の支援を目的としたソリューションのコンテストで、ブロックチェーンを使う事例は多く存在すると思いますが、そのブロックチェーン技術の選択肢の１つとして、既存技術では難しいものも場合によっては解決できる、と思っていて、その実装として提供・参加予定です。




 

タグ ：

#blockchain

#hashchain

#hash

#chain

#solo

#cloudant