じゅんメーリングリスト[Jun 4172]の記事で提示された、 「かたちの特徴を数にする」という問題の考察。
Smalltalkers' Salon Mailing List のアーカイブ経由で [Jun 4172]の内容のコピーが見られます。
向きや大きさの違いとは無関係に、二次元形状の類似度を計算する方法を考えた。 それをSmalltalk(VisualWorks + Jun)で実装して、どんな感じなのかみてみた。
きょうび、図形をコンピュータで描いたり保存したり、複雑な仕事に応用したりは日常的なこと。 回転したり、拡大したり、色をつけたりも自由自在で便利だよね。 だけど、図形の比較はコンピュータは苦手。
「外接円視点対中心深度戦略」を説明する。
長いから、外深法とでも呼ぶかな。
かたちの周囲を一周して、中心だけを注視する。 中心までの距離を測れば、波が得られる。
かたち同士の大きさの違いを捨てて忘れるには、 最小包含円（かたちに外接する円の中で最小のもの）との比率でかたちをみればよい。
波になってしまえば、波同士の比較もいろんな方法があるだろう。 例えば波高の差とか、二乗平均平方根(Root Mean Square)なんてのはすぐできるだろう。
内側から外へ向かって見て外殻までの高さを得ようとすると困ることがある。
力ずくの方法。 他のかたちと比較するときに、片方のかたちを少しずつ色々な向きに回転させてみて、一番ぴったりくるところを探す。
かたちの上に(中や外でもいい)にeye catcher(目を引く魅力的な点や特徴的な点)の印をいくつかつける。 他に似た形があったとすると、このeye catcherの位置も似ているはず。 eye catcherの位相を合わせると、かたちがよく合うはず。
多角形なら頂点なんかは魅力的な点といっていいだろう。
2節で示したアイデアがどれだけ意味があるか、計算した特性値がどれだけかたちを妥当に表現できるか、2次元図形に関してのみ実装して動かしてみた。
Jun(for Smalltalk) のバージョン662以降をinstallした上で、 Katachi-2006Jan28.st をfile inする。
コードのコピーや改変や頒布などは自由にしてください。 （packageには明記しそびれてますが、MITライセンスのような気分で使ってください。）
かたちに由来する波を表現するのは、 Katachi2dWaveの(サブクラスの)インスタンス。
右側が元のかたち。かたちを囲うのが最小包含円。 かたちに入っている青い縦線が、波の原点に対応する。 青い縦線を左に回転させて包含円から外殻までの距離を調べると、右側の波が得られる。
右側が波。横軸はかたちの周囲１周に対応。縦軸は、0から2(包含円の半径の倍)まで。 0は包含円に接していることを示し、 1ならば中心付近で視線がかたちの外殻にぶつかることを意味し、 2は凹みが激しくて中心を越えた包含円の反対側にかたちの外殻があることを意味する。
他のかたちとの間で、最適な回転を施し、類似度を計算する。 類似度は1から0までの間。 現在は、ふたつの波の高さの差の二乗平均平方根(RMS)を計算している。 すなわち、(波高の差)^2を１周分積分して平均し、その平方根を類似度としている。
例えば正三角形と正四角形の類似度を得るなら、以下のようにする。
(Katachi2dPolygonWave regularPolygon: 3) similarTo: (Katachi2dPolygonWave regularPolygon: 4)
これを評価すると、以下の2要素配列が得られる。
#(0.88614492553622d 0.083333333333333d)
最初の要素が類似度である。 後の要素は、最適回転:どの程度回転した場合に最も類似するかを示す。 上の例で言えば、 similarTo:で指定したかたち(正方形)は、 それを0.083周左回りに回転した場合に自分(正三角形)と最も似ていて、 その状況で0.886という類似度が計算されたことを意味する。
複数のかたちに対してお互いの類似度を示すとともに、 実際に最適回転をかたちに施して表示する。
Katachi2dCircleWave
Katachi2dNullWave
Katachi2dReverseCircleWave
Katachi2dHalfCircumference
かたち同士の類似度を提示することができた。向きや大きさも捨てられたので、相似な図形を同一視できている。 「これとあれが同じ形である」([Jun 4172])ことは、ある程度はこのアイデアで示すことができる。 (違いがあっても無視されてしまう部分もある。)
線対称な図形も同一視したいなら、波をreverseすればよい。
[Jun 4172]での当初の題である、 かたちに対してその特徴を示す数量を得るという目的は果たせていない。 円や棒といった特定のかたちとの比較という意味でなら、特徴量を簡易に得られている。
半円周とcupが遠いなど、直感と合わない例がある。 そもそも、 ここで得た「類似度」と称する怪しげな数値の妥当性(似てるという人の感覚との近さ)を どのように検証したらいいのか不明。
波の比較の計算に二乗平均平方根ではない別な戦略があるだろうか？
よく似た形の間の類似度(1.0近辺)は良好だが、大きく違う形の類似度は何を表現しているのかちょっと怪しいかな。こんなもんなのかも。
多角形だけじゃなく、手書きの形や、一般の形状imageで類似度の比較をしたいな。 その時には、waveletを応用して波の形のぎざぎざをとったりすることになるんだろうな。
三次元への拡張には壁がある。 波を扱うのに、 ２次元になる位相の領域をXY平面に取って緯度経度で扱いたくなるが、 これは筋が悪い方法だという予感が強くする。 メルカトル図法での歪みと同様の影響が波に出るはず。 波であること(サンプル点が互いに隣接している---中間の補完ができる)へのこだわりは捨てて、 単なるサンプル点の集合にすべきか？でもそうするとWaveletの応用は見込みがない。
じゅんメーリングリストとは、 Smalltalkの3Dクラスライブラリ に関する登録制のメーリングリスト。