Retrieval of On-line Hand-Drawn Sketches

reading

文献情報

(Link to the entry on the ACM Digital Libary)
Anoop M. Namboodiri and Anil K. Jain (2004): Retrieval of On-line Hand-Drawn Sketches.
In Proc. of the 17th International Conference on Pattern Recognition (ICPR '04)

Approach

  • グラフマッチングは NP 完全問題なので、そのままでは計算困難
  • そこで、ある description に変換する
    • 部分一致も検知できるようにする
    • 具体的には、隣接行列の固有値を使う
    • 行列は、topological information と geometric information の2種類
    • サブグラフについても descriptor を作る
  • 画像を図形として認識するのに CALI [5, 6] というライブラリを使う
  • クエリ生成には Calligraphic Interface [12] を使う
  • 多次元インデックス構造として NB-Tree [8, 9] (Naive-bayes tree) を使う
  • 手書きクエリと、DB に保管されている既知の全画像との類似度を計算するのに、以下の3段階のステップを踏む
    1. topology で検索する (descriptor を KNN にかけて近傍の descriptor を探す）
    2. geometry で refine する (またKNN?)
    3. 類似アルゴリズムの適用 (descriptor のユークリッドノルムを計算してそれを比較）

単純化

  • Douglas-Pecker algorithm [3] で手書き画像を単純化する（fig. 4 のように、ポリゴン数を減らす）

評価

  • 30の画像に対して、3種の異なる simplification heuristics を試してみたところ、だいたいポリゴンを8割方削減できることがわかった
  • 魚の画像DBから100個持ってきて、そのうち5つをクエリとして使うことにする。ユーザには事前実験で、似ていると思う10の画像を選んでもらう。この10画像を「選ぶべき画像」（正解データ）とする。
  • だいたい recall = precision = 50% くらい
  • 968個のクリップアートを処理するのに必要となった計算時間とインデックスサイズ
    • 計算機: AMD Duron 1.3GHz, 448MB RAM, Windows XP
    • 学習: 7分55秒（1枚あたり 0.49 秒）
    • インデックスサイズ:
    • 検索: 1-2秒

メモ

  • [1] と [16] が survey.
  • [4] spatial relationship の survey.
  • この論文のウリは、scalability と complexity に対応していること
  • 結局類似検索はどうやっているのか陽に記述されていないのが気持ち悪い。たぶん固有値ベクトルをKNNで探索してる→ランクの異なる画像同士はどう比較するのか？