講演抄録/キーワード |
講演名 |
2015-06-19 14:10
FPGAを用いた2次元画像の高速凸包計算 ○監物香保里・金澤健治・森 大和(筑波大)・相部範之(SUSUBOX)・安永守利(筑波大) RECONF2015-7 |
抄録 |
(和) |
本稿では,FPGAを用いた2次元画像における凸包計算の高速化手法について述べる.凸包とは,有限な点の集合$P(p_1, p_2, ..., p_n)$における,集合$P$の全ての点を含む最小の凸多角形である.凸包計算は画像処理やコンピュータビジョン,設計自動化など,多くの分野に応用される計算幾何の問題であり,既に幾つかのアルゴリズムや高速化手法が提案されている.しかし,これらの手法は与えられる点が既知であるという条件のもとで評価されており,与えられる点が未知である実際のシステムにおいては期待した性能が得られないと考えられる.そこで,我々は2次元画像において,その画像内の点の座標の検知とその凸包計算を同時に行うことで,実際のシステムにおいても有効な高速化手法を提案する.また,この手法をFPGAおよびGPU上で実装し,評価および比較を行う.更に,この手法を用いた応用例として,チップマウンタ上の表面実装部品の画像認識システムについて述べる. |
(英) |
Given a set of points, a convex hull is the smallest convex polygon containing all the points. In this paper, we describe a high-speed method for calculating the convex hull of 2D images based on Andrew's monotone chain algorithm. In our method, (1) all the points on a line in a given image are acquired in parallel, (2) only the points that can compose the convex hull are selected, and (3) the convex hull is concurrently built from the selected points during the previous steps. These three steps are successively executed until processing all lines in the image. We evaluate the performance of its FPGA and GPU implementation, and describe a detection method of surface-mounted devices as its application. |
キーワード |
(和) |
FPGA / GPU / 凸包 / 画像処理 / / / / |
(英) |
FPGA / GPU / convex hull / image processing / / / / |
文献情報 |
信学技報, vol. 115, no. 109, RECONF2015-7, pp. 35-40, 2015年6月. |
資料番号 |
RECONF2015-7 |
発行日 |
2015-06-12 (RECONF) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
査読に ついて |
本技術報告は査読を経ていない技術報告であり,推敲を加えられていずれかの場に発表されることがあります. |
PDFダウンロード |
RECONF2015-7 |