2値画像の重みつき距離変換を行なう並列アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 1996-10-17
• タイトル: 2値画像の重みつき距離変換を行なう並列アルゴリズム
• タイトル / 言語: en
• タイトル: A parallel algorithm for weighted distance transforms of binary images
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 奈良先端科学技術大学院大学情報科学研究科
• 著者所属: 奈良先端科学技術大学院大学情報科学研究科
• 著者所属: 奈良先端科学技術大学院大学情報科学研究科
• 著者所属: 奈良先端科学技術大学院大学情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science Nara Institute of Science and Technology (NAIST)
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science Nara Institute of Science and Technology (NAIST)
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science Nara Institute of Science and Technology (NAIST)
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science Nara Institute of Science and Technology (NAIST)
• 著者名: 藤原, 暁宏; 井上, 美智子; 増澤, 利光; 藤原, 秀雄
• 著者名(英): Akihiro, Fujiwara; Michiko, Inoue; Toshimitsu, Masuzawa; Hideo, Fujiwara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 白黒2値画像の距離変換とは，各画素について最も近い黒画素までの距離を求める処理である．また，白黒2値画像の最近点変換とは，各画素について最も近い黒画素の座標を求める処理である．本稿では，重みつき距離を用いて，距離変換及び最近点変換を行なう並列アルゴリズムを示す．このアルゴリズムはn×nの入力画像に対して，EREW PRAM上ではO(og )時間，n^2/log nプロセッサで実行でき，common CRCW PRAM上では，O(og log )時間，n^2/log log nプロセッサで実行できる．また，p^2プロセッサのメッシュモデル，ハイパーキューブモデル上ではO(^2/p^2+)時間，O(^2/p^2+( log )/)時間でそれぞれ実行できる．これらの結果より，このアルゴリズムはPRAM，メッシュモデル(〓p〓√<n>），および，ハイパーキュープモデル(〓p〓n/log )上でコスト最適である．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The distance transform of a black and white binary image is an operation which computes, for each pixel, the distance to the nearest black pixel. The nearest feature transform of the image is also an operation which computes, for each pixel, the coordinates of the nearest black pixel. This paper presents a parallel algorithm for the weighted distance transform and the weighted nearest feature transform of an n×n binary image. We show that the algorithm runs in O(log n) time using n^2/log n processors on the EREW PRAM and in O(log log n) time using n^2/log log n processors on the common CRCW PRAM. We also show that the algorithm runs in O(n^2/p^2+n) time on a p×p mesh and in O(n^2/p^2+(n log p)/p) time on a p^2 processor hypercube (for 1〓p〓n). The algorithm is cost optimal on the PRAMs, on the mesh (for 1〓p〓√<n>) and on the hypercube (for 1〓p〓n/log n).
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1996, 号 100(1996-AL-054), p. 9-16, 発行日 1996-10-17
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会