分割統治法に基づいた線形時間・画像連結要素ラベリング・アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
近年のハードウェア価格の低下とともに, 種々のアーキテクチャをもつ並列画像処理装置が開発され, それらの上で動作する数多くの並列画像処理アルゴリズムが提案されている. 本稿では, 従来から高速アルゴリズム設計法の一つとして知られている分割統治法を並列画像処理アルゴリズム設計に適用し, 完全並列型プロセッサの一種と考えられるメモリ付きセルラオートマトン上で, 線形時間で動作する連結要素ラベリング・アルゴリズムを提案する. 連結要素のラベリングは, 本来逐次的な性質ゆえにその並列化が困難なものと考えられてきた. 本演算に関しては, 自明な面積時間アルゴリズムが知られているだけで, 線形時間アルゴリズムの存在については, 理論的にも興味ある未解決問題として残されていたものである. 時間計算量の減少とともに, プロセッサ当りのハードウェア量が増大し, 実用化という観点からはさらに改良を重ねる必要がある.
- 一般社団法人情報処理学会の論文
- 1984-07-15
著者
関連論文
- 2次元リングアレイ上での最適時間一斉射撃アルゴリズムに関する考察
- セルオートマトン理論の再構築とNatural Computingへの応用
- 1次元リング結合セルラーオートマトンのための4状態一斉射撃アルゴリズム
- 正方形アレイのための一般化一斉射撃アルゴリズムについて
- 1状態および2状態1ビット通信セルラ・オートマトンの数列生成能力について
- 3次元セルラーオートマトン上での一斉射撃アルゴリズムの設計(理論,回路,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- Balzerによる最適時間一斉射撃アルゴリズムの正当性について
- B105 2次元セルラオートマトン上での同期アルゴリズム(ロジック,アルゴリズム)
- B104 1ビットセルオートマトン上での数列生成問題(ロジック,アルゴリズム)
- 1方向再帰性を有する線形時間一斉射撃アルゴリズムの設計と実装
- A-12-3 1 方向再帰性を有する最適時間一斉射撃アルゴリズムの設計と実装
- Early Bird問題に関する一考察
- Balzerによる最適時間一斉射撃アルゴリズムの正当性について
- 1状態1ビット通信セルラ・オートマトンの数列生成能力について(光カオス,一般)
- 2状態1ビット通信セルラ・オートマトンで生成可能な2次多項式数列について
- 1ビット通信セルラ・オートマトン上での非正則数列生成アルゴリズムについて(セッション2)
- 2次元1ビット通信セルラーオートマトン上での最適時間一斉射撃アルゴリズムの設計(グラフ,ペトリ,ニューラルネット及び一般)
- 2次元1ビット通信セルラーオートマトン上での最適時間一斉射撃アルゴリズムの設計(グラフ,ペトリ,ニューラルネット及び一般)
- 1ビット通信セルラーオートマトン上での一斉射撃アルゴリズム
- 1ビット通信セルラーオートマトン上での素数列生成アルゴリズム
- 実時間数列生成アルゴリズムの1ビット通信セルラ・オートマトン上での実装について
- 有限要素法を用いた摩擦音発生時の声道内呼気流の推定
- 2値図形の並列収縮アルゴリズムに関する考察
- 単位時間あたりのセル間通信量を1ビットに制限した2次元セルラ・オートマトンによる2値図形の連結性判定のための線形時間アルゴリズム
- 単位時間あたりのセル間通信量を1ビットに制限したセルラ・オートマトンによる数列の実時間生成と連結性判定アルゴリズム
- セル間通信量を1ビットに制限した2次元セルラ・オートマトンによる連結図形の線形時間認識について
- VPMT:分散メモリ型並列計算機のための並列プログラム可視化システム
- ハイパーキューブアルゴリズムの可視化に関する研究
- VPMT:分散メモリ型並列計算機のための並列プログラム可視化システム
- 星野 力 (著), "誰がどうやってコンピュータを創ったのか?", 共立出版, 158p, 2200円, 1995, ISBN4-320-02742-6
- セルラオートマトン
- VPMT : 分散メモリ型並列計算機のための並列プログラム可視化システム
- VPMT: 分散メモリ型並列計算機のための並列プログラム可視化システム
- 疎結合並列計算機上でのプロセッサ・ファームの効果的実装法
- 並列計算機(トランスピュータ・システム)における動作モニタの開発とその有効性
- トランスピュータ並列計算機による生物集団の行動パターンシミュレーション
- SIMD上の並列アルゴリズム (並列アルゴリズムの現状と動向)
- 小特集「並列アルゴリズムの現状と動向」の編集にあたって
- シストリック・アーキテクチャとそのアルゴリズム(パラレル・アルゴリズム)
- プレフィクス計算のための並列アルゴリズム (コンピュ-タと情報処理)
- ハイパ-キュ-ブ結合並列計算機上でのデ-タ・ル-ティング・アルゴリズム (コンピュ-タと情報処理)
- ブロードキャスト機能を備えた網目結合並列計算機のためのアルゴリズムに関する最近の研究
- 実時間シストリック・コンボルバの設計について
- シストリック・アレイによる線形時間限定セルラ・オ-トマンの模倣
- 1ビット・セルラオートマトンにおける最適時間一斉射撃アルゴリズムの実現
- 最適時間一斉射撃アルゴリズムの1ビット・セルラ・オートマトン上での実現
- 一斉射撃を用いた並列・データ・ルーティング・アルゴリズム
- Waksmanの一斉射撃アルゴリズムに対する最適化遷移規則集合の正当性について
- A.Waksmanの一斉射撃アルゴリズムに関する一考察
- A. Waksmanの一斉射撃アルゴリズムに関する一考察
- 2次元正方形アレイ上での最適時間一斉射撃アルゴリズムの設計
- D-1-10 2次元セルラーオートマトン上での最適時間一般化一斉射撃アルゴリズムの設計(D-1. コンピュテーション)
- D-1-9 2次元最適時間一斉射撃アルゴリズムの実装について(D-1. コンピュテーション)
- 2次元アレイ上での最適時間一斉射撃アルゴリズムの設計
- 2次元アレイ上での最適時間一斉射撃アルゴリズムの設計
- 多将軍一斉射撃問題について
- 一斉射撃問題の一般化に関する考察
- 2次元長方形セルラーオートマトン上での最適時間一斉射撃アルゴリズムの設計と実装
- 2次元一斉射撃アルゴリズムのための新しい設計手法
- 2次元一般化一斉射撃アルゴリズムについて
- 2次元セルラオートマトン上での一斉射撃アルゴリズム
- D-1-1 2次元セルラオートマトン上での一般化一斉射撃アルゴリズムの設計と実装
- 6 状態 3n ステップ一斉射撃アルゴリズムの設計と実装
- パラレルプログラミングを始めてみませんか(番外編)可視化情報を用いた並列アルゴリズム教育の試み
- 繰り返し論理回路による高速数列生成アルゴリズム
- ピラミッド・コンピュ-タに関する最近の研究
- 2次元リングアレイ上での最適時間一斉射撃アルゴリズムに関する考察
- 3次元セルラーオートマトン上での一斉射撃アルゴリズムの設計(理論,回路,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 3次元セルラーオートマトン上での一斉射撃アルゴリズムの設計(理論,回路,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- A-009 正方形一斉射撃アルゴリズムの実現に関する考察(A分野:モデル・アルゴリズム・プログラミング)
- 2次元セルラーオートマトン上における最適時間一斉射撃アルゴリズムの設計(グラフ,ペトリ,ニューラルネット及び一般)
- 2次元セルラーオートマトン上における最適時間一斉射撃アルゴリズムの設計(グラフ,ペトリ,ニューラルネット及び一般)
- シストリック計算幾何アルゴリズムに関する最近の研究
- 2次元セルラーオートマトン上における最適時間一斉射撃アルゴリズムの設計と実装
- マルチビット最適時間一斉射撃アルゴリズムの設計(NLP一般)
- A-12-7 通信量を1ビットに制限した小さな自己複製セルラーオートマトンの構成(A-12.コンカレント工学,一般セッション)
- 2次元セルラーオートマトン上での最適時間一斉射撃アルゴリズムの設計(一般,コンカレントシステム及び一般)
- セルラーオートマトン上での耐故障性自己増殖モデルの設計
- 1ビット通信セルラーオートマトン上での自己増殖機能の実現
- 最適実時間シストリック・多項式除算アルゴリズム
- シストリック・アレイ
- 分割統治法に基づいた線形時間・画像連結要素ラベリング・アルゴリズム
- セルラ計算機のための最適時間・並列アドレス設定アルゴリズム
- パイプイン・アドレス設定法
- シストリック・アレイにより模倣可能なSIMD並列計算機のあるクラス
- 状態変化回数を1回に限定したセルラオートマトンと有限オートマトンとの等能力性
- 2次元セルラ・オートマトン上の一斉射撃問題に関する研究
- 2次元セルラ・オートマトン上の一斉射撃問題に関する研究
- 2次元セルラ・オートマトン上の一斉射撃問題に関する研究
- 2次元最適時間同期アルゴリズム
- 多次元最適時間FSSPアルゴリズム
- ゼブラマッピングを利用した2次元一斉射撃アルゴリズムの実装(学生セッション)