画像からユニークなIDを生成するアルゴリズム

2014/09/24 13:16

このQ&Aのポイント

画像データからユニークなIDを生成する方法について
同一データからは必ず同一IDになる仕組みと別の画像から同一IDが生成される可能性を排除する方法について
色や画像サイズ値、複数のアルゴリズムを組み合わせることも考慮可能な方法

BindNet
お礼率100% (4/4)

その他（プログラミング・開発）
回答数4
ありがとう数18

みんなの回答 （4）
専門家の回答

質問者が選んだベストアンサー

ベストアンサー

pringlez
ベストアンサー率36% (598/1630)

2014/09/24 15:08 回答No.3

あなたの言う「別の画像から同一IDが生成される可能性を極力排除したい」という言葉の意味があいまいでよくわかりません。「たまには衝突があってもいい」と言う意味なのか「絶対に衝突を許さない」という意味なのでしょうか、どちらですか。普通に日本語を解釈すれば「完全に排除する必要はまったく無い」「たまに衝突しても何も問題ない」という意味のはずですが、No.1, No.2のお礼を見ると、普通の日本語として解釈した意味とあなたの要望はずれているようにも感じます。日本語がずれておらず「たまには衝突があってもいい」ということならばハッシュ値を使う方法で十分でしょう。またハッシュを使えばまれに衝突するのはやむをえないでしょう。「絶対に衝突を許さない」という意味ならばBase64でエンコードでもすればいいでしょう。長くはなりますが完全にユニークなIDとすることが可能ですよ。逆にそうでもしない限りは衝突を避けることは不可能です。

質問者

お礼 2014/09/24 21:03

他のサイトで、画像の全体の色味情報として、数ピクセル程度まで縮小した画像、画像に含まれる形状の情報として、輪郭追跡より求めた曲線データ、これらを数値化したものにハッシュ値を加えた、三要素をIDとする案が出てきましたので、これにて質問を締め切りたいと思います。皆様本当に有り難うございました。

質問者

補足 2014/09/24 15:24

ご回答有り難うございます！大変本質的なご指摘です。それでは、衝突の許容度は、画像の内容によって変化する事にします。人の目で見てどれも同じような場合、例えば、全面ノイズ画像などの場合には、衝突して構いません。逆に、お気に入りの場所で撮った思い出の一枚が、全くの別画像に化けることは絶対に避けたいということにします。比較する対象は、1ビット単位のデータ値ではなく、あくまでも人間が見る為の画像です。どうぞ宜しくお願いします！

その他の回答 (3)

chie65536（@chie65535）
ベストアンサー率44% (8740/19838)

2014/09/24 15:30 回答No.4

＞カリフォルニアでジョンさんが撮った写真と、ムンバイでアショークさんが撮った写真が同一IDになってしまう気がするのです。ハッシュ値やCRC値は、確かに「異なるデータで同じ値が生成される場合がある」ので、単一のアルゴリズムでは、同一の値が出る可能性があります。しかし、異なるアルゴリズムを複数用いた場合、例えばデータの先頭から正順に求めたCRC32値データの先頭から正順に求めたハッシュ値データの末尾から逆順に求めたCRC32値データの末尾から逆順に求めたハッシュ値の４つを用いた場合「同時に、４つとも、すべて同じ値になる可能性」は、ほぼゼロです。それぞれが３２ビット値だった場合、４つとも全部一致してしまう確率は「１／（２の１２８乗）」です。３２ビットが４つ、合計で１２８ビットなので「１／（２の１２８）乗」が「重複する確率」になります。これは「１／340282366920938463463374607431768211456」になります。つまり「画像が340282366920938463463374607431768211456枚以上あったら、１枚くらい重複するかも知れない」と言う確率です。このくらいの確率なら「ほぼゼロ」と考えて差し支えありません。心配なら、８つの方法を組み合わせて「３２ビット×８」にして、IDを256ビットにしてしまいましょう。２５６ビットのIDが全部一致してしまう確率は「１／（2の256乗)」なので、確率は「１／115792089237316195423570985008687907853269984665640564039457584007913129639936」になります。こう考えると「２５６ビットのハッシュ値１つで事足りる」ので、CRCは要らない事が判ります。「２５６ビットのハッシュ値が重複してしまう確率」は「１／115792089237316195423570985008687907853269984665640564039457584007913129639936」ですからね。

質問者

お礼 2014/09/24 15:49

有り難うございます！自分はデザイン系出身でiOSアプリしか作った事がなく、プロクラミン系の知識は皆無なので、ものすごく確率が低いという事をわかりやすくご説明頂けて、とても安心しました。ただ、'画像'というものの特性を生かしたアルゴリズムがもしあればとも思うので、もう少し締め切らずに様子を見てみたいと思います。

chie65536（@chie65535）
ベストアンサー率44% (8740/19838)

2014/09/24 13:38 回答No.2

複数のアルゴリズムのCRC値と、複数のアルゴリズムのハッシュ値を求めて、それらを結合した値をIDとすれば良い。例えば、画像を「単なるバイナリデータの羅列」と考えて、そのバイナリデータの羅列に対してデータの先頭から正順に求めたCRC32値データの先頭から正順に求めたハッシュ値データの末尾から逆順に求めたCRC32値データの末尾から逆順に求めたハッシュ値の４つを求めて、それらを「文字化」して、その「文字化した４つの文字列」を単純に連結した文字列をIDにする、など。「CRC32関数」や「ハッシュ関数」は、googleなどで調べればすぐに見付かる筈です。

質問者

お礼 2014/09/24 14:42

早速のご回答ありがとうございます！ハッシュ値やチェックサムなど、目から鱗が落ちました。これで殆ど行けそうな感じなので、調べて検討してみたいと思います。ただ、もうひとひねり、IDの衝突を避けるための仕掛けをプラスできると安心なのですが‥ カリフォルニアでジョンさんが撮った写真と、ムンバイでアショークさんが撮った写真が同一IDになってしまう気がするのです。