Presentation 2015-06-19
High Speed Calculation of Convex Hull in 2D Images using FPGA
Kahori Kemmotsu, Kenji Kanazawa, Yamato Mori, Noriyuki Aibe, Moritoshi Yasunaga,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) 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.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) FPGA / GPU / convex hull / image processing
Paper # RECONF2015-7
Date of Issue 2015-06-12 (RECONF)

Conference Information
Committee RECONF
Conference Date 2015/6/19(2days)
Place (in Japanese) (See Japanese page)
Place (in English) Kyoto University
Topics (in Japanese) (See Japanese page)
Topics (in English) the 10th anniversary celebration of RECONF: Reconfigurable Systems, etc.
Chair Minoru Watanabe(Shizuoka Univ.)
Vice Chair Masato Motomura(Hokkaido Univ.) / Yuichiro Shibata(Nagasaki Univ.)
Secretary Masato Motomura(Toshiba) / Yuichiro Shibata(Univ. of Tsukuba)
Assistant Kazuya Tanikagawa(Hiroshima City Univ.) / Takefumi Miyoshi(e-trees.Japan)

Paper Information
Registration To Technical Committee on Reconfigurable Systems
Language JPN
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) High Speed Calculation of Convex Hull in 2D Images using FPGA
Sub Title (in English)
Keyword(1) FPGA
Keyword(2) GPU
Keyword(3) convex hull
Keyword(4) image processing
1st Author's Name Kahori Kemmotsu
1st Author's Affiliation University of Tsukuba(Univ. of Tsukuba)
2nd Author's Name Kenji Kanazawa
2nd Author's Affiliation University of Tsukuba(Univ. of Tsukuba)
3rd Author's Name Yamato Mori
3rd Author's Affiliation University of Tsukuba(Univ. of Tsukuba)
4th Author's Name Noriyuki Aibe
4th Author's Affiliation SUSUBOX Co., Ltd.(SUSUBOX)
5th Author's Name Moritoshi Yasunaga
5th Author's Affiliation University of Tsukuba(Univ. of Tsukuba)
Date 2015-06-19
Paper # RECONF2015-7
Volume (vol) vol.115
Number (no) RECONF-109
Page pp.pp.35-40(RECONF),
#Pages 6
Date of Issue 2015-06-12 (RECONF)