| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2010-09-29 11:10 2値画像上で連結成分を消去するその場でのアルゴリズム ○浅野哲夫（北陸先端大）  COMP2010-26 |
|
| 抄録 | （和） | 2値画像が与えられたとき，雑音成分を除去することは 基本的な操作の一つである．この操作を一般化すると， 2値画像上で指定された連結成分の画素をすべてフリップ する（画素値を$1$から$0$に交換する）ことになる． 本論文では，スタックやキューなどの余分のデータ構造を 一切使わずに$O(n \log n)$時間で任意の連結成分を 除去するアルゴリズムを提案する．ただし，$n$は除去 すべき連結成分の画素数である． 入力の2値画像は読み書きができる普通のビット配列で あるが，各画素に対して$1$ビットしか使えないので， 入力の配列を作業用に用いることは難しい． 画素をフリップすると連結成分の形状も変化するが， この変化のためにアルゴリズムの設計は容易ではない． ここで提案する方法は，最初に連結成分の穴を画素の フリップによってすべて連結にした後で，構造を 変えないように画素のフリップを行うというものである． |
| （英） | Removing noises in a given binary image is one of common operations. A generalization of the operation is to erase an arbitrarily specified component by reversing pixel values in the component. This paper shows that this operation is done without using any data structure like a stack or queue, or more exactly using only constant extra memory (of $O(\log n)$ bits for an image of $n$ pixels) in $O(m \log m)$ time for a component consisting of $m$ pixels. This is an in-place algorithm, but the image matrix cannot be used as work space since it has just one bit for each pixel. Whenever we flip a pixel value in a target component, the component shape is also deformed, which causes some difficulty. An idea for our constant work space algorithm is a deformation of a component which keeps its connectivity. |
|
| キーワード | （和） | / / / / / / / |
| （英） | constant work space algorithm / in-place algorithm / binary image / component / connectivity / / / | |
| 文献情報 | 信学技報, vol. 110, no. 214, COMP2010-26, pp. 17-23, 2010年9月. | |
| 資料番号 | COMP2010-26 | |
| 発行日 | 2010-09-22 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2010-26 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2010-09-29 - 2010-09-29 |
| 開催地（和） | 長岡技術科学大学 |
| 開催地（英） | Nagaoka Univ. of Tech. |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2010-09-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 2値画像上で連結成分を消去するその場でのアルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | In-place algorithm for Erasing a Component in a Binary Image |
| サブタイトル（英） | |
| キーワード(1)（和/英） | / constant work space algorithm |
| キーワード(2)（和/英） | / in-place algorithm |
| キーワード(3)（和/英） | / binary image |
| キーワード(4)（和/英） | / component |
| キーワード(5)（和/英） | / connectivity |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 浅野 哲夫 / Tetsuo Asano / |
| 第1著者 所属（和/英） | 北陸先端科学技術大学院大学 (略称： 北陸先端大) JAIST (略称： JAIST) |
| 講演者 | 第1著者 |
| 発表日時 | 2010-09-29 11:10:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2010-26 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | no.214 |
| ページ範囲 | pp.17-23 |
| ページ数 | 7 |
| 発行日 | 2010-09-22 (COMP) |
[研究会発表申込システムのトップページに戻る]