8

写真のギャラリー (すべて JPEG) を取得し、可能な各ペア間の類似性スコアを与えるアプリケーションがあります。どの時点でも、1 つのペアのみを選択でき、その類似度スコアが表示されます。

2 つの画像を比較するアルゴリズムには、特定のパフォーマンス コストがかかるため、ペアを比較するのに数秒かかります。

2枚選択時：

  1. ペアが一度も比較されていない場合、スコアは「まだスコアが付けられていません」と表示されます。ユーザーが「スコア」ボタンをクリックすると、計算するスコアをキューに入れるスレッドにペアが送信されます。例: http://db.tt/gb1Yk6yx
  2. ペアが現在計算待ちのキューにある場合、スコア フィールドには「Computing...」と表示されます。例: http://db.tt/OvS1qGP3
  3. ペアが比較された場合、ペアに付けられたスコアが表示されます。例: http://db.tt/m2OQGybW

例 (バッチを実行する場合): http://db.tt/iD67SdCp

スコアが一度も計算されていない場合、ユーザーが [スコア] をクリックすると、フィールドが [計算中...] に切り替わり、計算が完了するとスコアが表示されます。

スコアのフィールドに何かを表示する前に、2 つのペアが選択されると、添付されたビットマップが HashMap に送信され、それらの 2 つのビットマップにスコアが添付されているかどうかが確認されます。スコアがない場合、ジョブはキューに送信されます。

スコアがキャッシュに存在するかどうかを知るには、結果のキーを使用してキャッシュを検索できるように、ペアをハッシュする方法を見つける必要があります。それが私の問題です。意味をなすために、2 つのビットマップのハッシュは高速である必要があります。それ以外の場合は、別の計算レイヤーを追加するだけです。しかし、これまでのところ、2 つのビットマップをハッシュする方法は、それらをバイト配列で送信し、MD5 チェックサムを取得することです。このような：

private Long getHashKey(Bitmap first, Bitmap second){

    // TODO this IS costly, it render useless the cache optimization.
    // also, it doesn't detect that comp(A,B) is the same as comp(B,A).
    // much work to do here.

    if(D) Profiling.start(TAG, "getHashKey");

    ByteArrayOutputStream stream = new ByteArrayOutputStream();
    first.compress(Bitmap.CompressFormat.JPEG, 100, stream);

    byte[] firstArray = stream.toByteArray();
    second.compress(Bitmap.CompressFormat.JPEG, 100, stream);

    byte[] secondArray = stream.toByteArray();
    byte[] bitmapBuffer = new byte[firstArray.length + secondArray.length];

    System.arraycopy(firstArray, 0, bitmapBuffer, 0, firstArray.length);

    System.arraycopy(secondArray, 0, bitmapBuffer, 
            firstArray.length, secondArray.length);

    Adler32 md5Hash = new Adler32();
    md5Hash.update(bitmapBuffer);
    long hashKey = md5Hash.getValue();

    if(D) Profiling.stop();

    return hashKey;
}

しかし、私が行ったプロファイリングによると、このメソッドの実行には約 53 ミリ秒かかり、UI で非常に不快な遅延が発生します。より詳細なプロファイリングでは、計算時間の約 95% がcompressメソッドで行われていることがわかりました。ただし、ビットマップをバックアップするバイトを取得する別の方法は見つかりませんでした。

05-26 17:56:13.220: D/Profiling(9458): Profile for ImageCompareActivity.getHashKey:
05-26 17:56:13.220: D/Profiling(9458): >          Count : 1996 calls
05-26 17:56:13.220: D/Profiling(9458): >  Total runtime : 105765140 us
05-26 17:56:13.220: D/Profiling(9458): >    Avg runtime : 52988 us

Bitmap をハッシュする方法が非常に野蛮であることはわかっています。しかし、ハッシュ関数と、ファイルを一意に識別するためにビットマップのどの部分を使用できるかについては、あまり知りません。これらのビットマップを最終的にデータベースに送信したいので、ファイル名などを使用したくありません。

【追記1】 Object.hashCode()について知りませんでした。今、私はこのようにメソッドを変更しました：

private Integer getHashKey(Bitmap first, Bitmap second){

    if(D) Profiling.start(TAG, "getHashKey");

    Integer hashKey = new Integer(
            1013 * (first.hashCode()) ^ 1009 * (second.hashCode()) ); 

    if(D) Profiling.stop();

    return hashKey;
}

これは平均して約 18 秒間実行されます。

4

2 に答える 2

1

これがハッシュに関する最近の質問です。Adlerは、おそらくJREに組み込まれている最速の方法です。ハッシュを事前に計算して画像と一緒に、またはデータベースに保存することを検討しましたか？

于 2012-05-26T15:51:25.687 に答える