インテグラルイメージを用いた主成分木による画像の最近傍探索の高速化  [in Japanese] An Accelerated Nearest Neighbor Image Search by Principal Component Tree using Integral Image  [in Japanese]

Search this Article

Author(s)

Abstract

事例に基く学習や認識において,最近傍探索は電要な基礎技術として位置づけられる.これまでにも,様々な最近傍探索アルゴリズムが提案されているが,数千から数万次元の画像データに対する効率の良い探索手法は存在しない.この問題に対し我々は,画像データの分布の偏りを利用し,kd-treeを主成分分析により得られる主軸を分割軸とするように改良した主成分木を提案している.しかし,この手法では探索時に入力画像と各分割軸との内積計算が必要であるため,十分な速度向上が達成できなかった.そこで本報告では,インテグラルイメージを利用して画像の内積計算を高速化し,それを用いて画像の最近傍探索を高速化する方法を提案する.

Nearest Neighbor (NN) search is essential for case/instance based reasoning. Most NN search methods proposed so far are based on NN candidate narrowing and these methods degenerates to brute force search in highdimensional space over 30D. For solving this problem, we have been proposed PC-tree that is modifed the kd-tree by replacing a space dividing axis by a principal axis of prototypes. However, the method achieved insufficient accelaration because the method required inner producets between an input image and each dividing axis. In this paper, we propose an accelerated inner products between images by using integral image and apply it to the nearest neighbor image search with PC-tree.

Journal

  • IEICE technical report

    IEICE technical report 106(470), 55-60, 2007-01-12

    The Institute of Electronics, Information and Communication Engineers

References:  8

Codes

  • NII Article ID (NAID)
    110006205216
  • NII NACSIS-CAT ID (NCID)
    AN10541106
  • Text Lang
    JPN
  • Article Type
    ART
  • ISSN
    09135685
  • NDL Article ID
    8639263
  • NDL Source Classification
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL Call No.
    Z16-940
  • Data Source
    CJP  NDL  NII-ELS 
Page Top