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

質問

画像データからユニークなIDを生成したいです。
データ元は、ファイル名やメタデータを含まない、画像データ本体のみという事にします。
可逆性は問わないので、元の画像を推測出来ても出来なくても、どちらでも構いません。
こだわりたいのは、同一データからは必ず同一IDになるということと、
別の画像から同一IDが生成される可能性を極力排除したいということです。

IDの形式や桁数はこだわりません。
色から生成したIDと画像サイズ値をセットにしたり、複数のアルゴリズムを組み合わせても構いません。
画像サイズによってIDの桁数が変化しても構いません。
桁数は少ない方がいいですが、それよりは別画像から同一IDになる事態を避ける事の方が優先です。

宜しくお願いします。

回答No.3

pringlez · ベストアンサー

あなたの言う「別の画像から同一IDが生成される可能性を極力排除したい」という言葉の意味があいまいでよくわかりません。「たまには衝突があってもいい」と言う意味なのか「絶対に衝突を許さない」という意味なのでしょうか、どちらですか。

普通に日本語を解釈すれば「完全に排除する必要はまったく無い」「たまに衝突しても何も問題ない」という意味のはずですが、No.1, No.2のお礼を見ると、普通の日本語として解釈した意味とあなたの要望はずれているようにも感じます。

日本語がずれておらず「たまには衝突があってもいい」ということならばハッシュ値を使う方法で十分でしょう。またハッシュを使えばまれに衝突するのはやむをえないでしょう。

「絶対に衝突を許さない」という意味ならばBase64でエンコードでもすればいいでしょう。長くはなりますが完全にユニークなIDとすることが可能ですよ。逆にそうでもしない限りは衝突を避けることは不可能です。

お礼

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

皆様本当に有り難うございました。

補足

ご回答有り難うございます！
大変本質的なご指摘です。

それでは、衝突の許容度は、画像の内容によって変化する事にします。

人の目で見てどれも同じような場合、例えば、全面ノイズ画像などの場合には、衝突して構いません。
逆に、お気に入りの場所で撮った思い出の一枚が、全くの別画像に化けることは絶対に避けたいということにします。

比較する対象は、1ビット単位のデータ値ではなく、あくまでも人間が見る為の画像です。

どうぞ宜しくお願いします！

回答No.4

chie65535

＞カリフォルニアでジョンさんが撮った写真と、ムンバイでアショークさんが撮った写真が同一IDになってしまう気がするのです。

ハッシュ値やCRC値は、確かに「異なるデータで同じ値が生成される場合がある」ので、単一のアルゴリズムでは、同一の値が出る可能性があります。

しかし、異なるアルゴリズムを複数用いた場合、例えば

データの先頭から正順に求めたCRC32値
データの先頭から正順に求めたハッシュ値
データの末尾から逆順に求めたCRC32値
データの末尾から逆順に求めたハッシュ値

の４つを用いた場合「同時に、４つとも、すべて同じ値になる可能性」は、ほぼゼロです。

それぞれが３２ビット値だった場合、４つとも全部一致してしまう確率は「１／（２の１２８乗）」です。

３２ビットが４つ、合計で１２８ビットなので「１／（２の１２８）乗」が「重複する確率」になります。

これは「１／340282366920938463463374607431768211456」になります。

つまり「画像が340282366920938463463374607431768211456枚以上あったら、１枚くらい重複するかも知れない」と言う確率です。

このくらいの確率なら「ほぼゼロ」と考えて差し支えありません。

心配なら、８つの方法を組み合わせて「３２ビット×８」にして、IDを256ビットにしてしまいましょう。

２５６ビットのIDが全部一致してしまう確率は「１／（2の256乗)」なので、確率は「１／115792089237316195423570985008687907853269984665640564039457584007913129639936」になります。

こう考えると「２５６ビットのハッシュ値１つで事足りる」ので、CRCは要らない事が判ります。

「２５６ビットのハッシュ値が重複してしまう確率」は「１／115792089237316195423570985008687907853269984665640564039457584007913129639936」ですからね。

お礼

有り難うございます！

自分はデザイン系出身でiOSアプリしか作った事がなく、
プロクラミン系の知識は皆無なので、
ものすごく確率が低いという事をわかりやすくご説明頂けて、とても安心しました。

ただ、'画像'というものの特性を生かしたアルゴリズムがもしあればとも思うので、
もう少し締め切らずに様子を見てみたいと思います。

回答No.2

chie65535

複数のアルゴリズムのCRC値と、複数のアルゴリズムのハッシュ値を求めて、それらを結合した値をIDとすれば良い。

例えば、画像を「単なるバイナリデータの羅列」と考えて、そのバイナリデータの羅列に対して

データの先頭から正順に求めたCRC32値
データの先頭から正順に求めたハッシュ値
データの末尾から逆順に求めたCRC32値
データの末尾から逆順に求めたハッシュ値

の４つを求めて、それらを「文字化」して、その「文字化した４つの文字列」を単純に連結した文字列をIDにする、など。

「CRC32関数」や「ハッシュ関数」は、googleなどで調べればすぐに見付かる筈です。

お礼

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

回答No.1

t_ohta

MD5とかSHAとか使ってハッシュ値を求める方法はどうでしょう。

お礼

早速のご回答ありがとうございます！
ハッシュ値とは知りませんでしたので、とても助かりました。
調べて検討してみたいと思います。
ただ、IDの衝突を避けるための仕掛けがもう一つあると安心できるのですが‥