| 講演名 | 2017-07-26 ボロノイ図とユークリッド距離マップ計算のGPU実装 本田 啓朗(広島大), 本田 巧(広島大), 山元 晨之介(広島大), 中野 浩嗣(広島大), 伊藤 靖朗(広島大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿ではGPU上でシンプルかつ高速に動作する完全ボロノイ図，連結ボロノイ図，ユークリッド距離マップ生成のアルゴリズムとそれらのGPU実装を提案する．提案アルゴリズムでは，最初に完全ボロノイ図と連結ボロノイ図の両方の性質を持つボロノイ図を作成し，その後完全または連結ボロノイ図に変換する．また，完全ボロノイ図からユークリッド距離マップを自明な方法で変換する．このアルゴリズムをGeForce GTX~1080に実装し，性能を評価した．その結果，入力が複数枚の$2Ktimes2K$の2値画像におけるユークリッド距離マップ生成の計算スループットにおいて，既存のGPU実装より2.08倍，単一コアのCPUとしてIntel Core i7-4790を用いた逐次処理と比較して172倍の高速化を達成した． |
| 抄録(英) | The main contribution of this paper is to present simple and fast parallel algorithms for computing complete/connected Voronoi map and the Euclidean distance map and implement them in the GPU. Our parallel algorithm first computes the mixed Voronoi map, which is a mixture of complete/connected Voronoi maps, and then converts it into the complete/connected Voronoi map. After that, the complete Voronoi map is converted into Euclidean distance map in obvious way. We have implemented on GeForce GTX1080. The throughput of our GPU implementation for computing the Euclidean distance maps of $2Ktimes2K$ binary images is up to 2.08 times larger than previously published best GPU implementation, and up to 172 times larger than CPU implementation using Intel Core i7-4790. |
| キーワード(和) | ボロノイ図 / ユークリッド距離マップ / GPU / CUDA |
| キーワード(英) | Voronoi Map / Euclidean distance map / GPU / CUDA |
| 資料番号 | CPSY2017-18 |
| 発行日 | 2017-07-19 (CPSY) |
| 研究会情報 | |
| 研究会 | CPSY / DC / IPSJ-ARC |
|---|---|
| 開催期間 | 2017/7/26(から3日開催) |
| 開催地（和） | 秋田アトリオンビル（秋田） |
| 開催地（英） | Akita Atorion-Building (Akita) |
| テーマ（和） | 並列／分散／協調とディペンダブルコンピューティングおよび一般 |
| テーマ（英） | Parallel, Distributed and Cooperative Processing |
| 委員長氏名（和） | 中野 浩嗣(広島大) / 井上 美智子(奈良先端大) |
| 委員長氏名（英） | Koji Nakano(Hiroshima Univ.) / Michiko Inoue(NAIST) |
| 副委員長氏名（和） | 入江 英嗣(東大) / 三吉 貴史(富士通研) / 福本 聡(首都大東京) |
| 副委員長氏名（英） | Hidetsugu Irie(Univ. of Tokyo) / Takashi Miyoshi(Fujitsu) / Satoshi Fukumoto(Tokyo Metropolitan Univ.) |
| 幹事氏名（和） | 大川 猛(宇都宮大) / 高前田 伸也(北大) / 吉村 正義(京都産大) / 金子 晴彦(東工大) |
| 幹事氏名（英） | Takeshi Ohkawa(Utsunomiya Univ.) / Shinya Takameda(Hokkaido Univ.) / Masayoshi Yoshimura(Kyoto Sangyo Univ.) / Haruhiko Kaneko(Tokyo Inst. of Tech.) |
| 幹事補佐氏名（和） | 伊藤 靖朗(広島大) / 津邑 公暁(名工大) / 新井 雅之(日大) |
| 幹事補佐氏名（英） | Yasuaki Ito(Hiroshima Univ.) / Tomoaki Tsumura(Nagoya Inst. of Tech.) / Masayuki Arai(Nihon Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Computer Systems / Technical Committee on Dependable Computing / Special Interest Group on System Architecture |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ボロノイ図とユークリッド距離マップ計算のGPU実装 |
| サブタイトル（和） | |
| タイトル（英） | A GPU Implementation of Computing the Voronoi Map and the Euclidean Distance Map |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ボロノイ図 / Voronoi Map |
| キーワード(2)（和/英） | ユークリッド距離マップ / Euclidean distance map |
| キーワード(3)（和/英） | GPU / GPU |
| キーワード(4)（和/英） | CUDA / CUDA |
| 第 1 著者 氏名（和/英） | 本田 啓朗 / Hiroaki Honda |
| 第 1 著者 所属（和/英） | 広島大学(略称：広島大) Hiroshima University(略称：Hiroshima Univ.) |
| 第 2 著者 氏名（和/英） | 本田 巧 / Takumi Honda |
| 第 2 著者 所属（和/英） | 広島大学(略称：広島大) Hiroshima University(略称：Hiroshima Univ.) |
| 第 3 著者 氏名（和/英） | 山元 晨之介 / Shinnosuke Yamamoto |
| 第 3 著者 所属（和/英） | 広島大学(略称：広島大) Hiroshima University(略称：Hiroshima Univ.) |
| 第 4 著者 氏名（和/英） | 中野 浩嗣 / Koji Nakano |
| 第 4 著者 所属（和/英） | 広島大学(略称：広島大) Hiroshima University(略称：Hiroshima Univ.) |
| 第 5 著者 氏名（和/英） | 伊藤 靖朗 / Yasuaki Ito |
| 第 5 著者 所属（和/英） | 広島大学(略称：広島大) Hiroshima University(略称：Hiroshima Univ.) |
| 発表年月日 | 2017-07-26 |
| 資料番号 | CPSY2017-18 |
| 巻番号（vol） | vol.117 |
| 号番号（no） | CPSY-153 |
| ページ範囲 | pp.13-18(CPSY), |
| ページ数 | 6 |
| 発行日 | 2017-07-19 (CPSY) |