メッシュ·画像上での単純で空間効率的な階層的クラスタリング法

摘要

メッシュ·画像上での階層的クラスタリングの標準的な手法では，クラスター融合後にクラスターの接続構造および優先順序付きキューの更新処理が必要になる．一方，quadric error metric (QEM) やtopological persistence などの単調に増加するコスト関数を用いた階層的クラスタリングに対しては，コストの遅延計算とunion-find データ構造を利用することで，それらの処理を必要としない単純で空間効率的なアルゴリズムを設計することができる[3, 1]．このアルゴリズムは，単調に増加しないコスト関数を用いた階層的クラスタリングに対しても適用出来るが，正しい結果を得ることはできない．本研究では，単調には増加しないがreducibility property という良い性質を持ったコスト関数を用いた階層的クラスタリングに対して，このアルゴリズムにより質の良い結果が得られることを示す．