講演抄録/キーワード |
講演名 |
2006-03-16 13:15
事例ベース対象追跡・認識のための近さ優先探索グラフの対話的構築アルゴリズム ○坂平星弘・和田俊和・坂垣内洵也・加藤丈和(和歌山大) |
抄録 |
(和) |
我々は,対象の様々な見えを蓄積した画像データベースを用いた対象追跡・認識法を提案している.このアルゴリズムでは,近さ優先探索グラフ(NFTG)と呼ばれるデータ構造を用いた擬似的な最近傍探索が行われるが,このNFTGを構築するためには,画像データ間の距離を全て計算しておく必要があるため,データ数を$N$,画像の次元数を$d$とした場合,$O(dN^2)$の計算が必要となり,対話的に対象のデータを追加していく用途には適さない.本報告では,対象の見えを反映したNFTGを即座に計算するアルゴリズムを提案する. |
(英) |
We have proposed an image retrieval based object tracking and recognition method. In this method, nearest neighbor (NN) search within an image database is performed for the object image extracted from input frame. For this search, we have proposed an approximate NN search algorithm based on Nearest First Traversing Graph (NFTG), which utilizes the previous search result as the starting point of the next search. However, the computational complexity of this graph construction is $O(dN^2)$, where N and d are the number of images in the database and the dimensionality of each image data respectively. This construction algorithm is not suitable for the interactive application that stores user specified object images one by one. In this paper, we propose an incremental tree construction algorithm whose complexity is $O(dN)$ for storing a single object image. Through the experiments, we confirmed the effectiveness of our new graph construction algorithm. |
キーワード |
(和) |
近さ優先探索 / NFTG / 対象追跡と認識 / 逐次グラフ構成 / / / / |
(英) |
Nearest First Traversing / NFTG / Object Tracking and Recognition / Incremental graph construction / / / / |
文献情報 |
信学技報, vol. 105, no. 673, PRMU2005-245, pp. 85-92, 2006年3月. |
資料番号 |
PRMU2005-245 |
発行日 |
2006-03-09 (PRMU) |
ISSN |
Print edition: ISSN 0913-5685 |
PDFダウンロード |
|