| 講演名 | 2010-05-19 制約されたメモリ上での2値画像処理の技法 浅野 哲夫, べレグ セルゲイ, ブゼール リリアン, カークパトリック デビッド, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 画像処理における基本的な処理には様々なものがある.たとえば,2つの画素が同じ連結成分に属するかどうかを判定する問題や,任意に指定した連結成分に属するすべての画素を列挙する問題や,2つの2値図形が同じかどうかを判定する問題などを挙げることができる.作業用のメモリを十分に取ることができるなら,これらの問題に対して効率のよいアルゴリズムを考えることは難しくない.本論文では,2値画像に関するこれらの基本的な問題に対して作業用メモリが限定されている場合にも効率の良いアルゴリズムを提案する.本論文では入力2値画像は読み出し専用のビット配列で与えられるものと仮定し,さらに作業用には定数個のポインタあるいはカウンタしか使えないものとする.このような厳しい制約の下でも,本論文のアルゴリズムの計算時間はO(a+b log b)である.ただし,αは画像の面積(画素数)であり,bはすべての連結成分の周囲長の総和である. |
| 抄録(英) | Many elementary image processing tasks, such as determining if two specified pixels belong to the same connected component (or, more generally, determining the nesting structure of their associated components), reporting all of the pixels in each component, and determining if two patterns, specified by points on their external boundary, form an exact match, have rather straightforward solutions whose running time is linear in the size of the image. However, such solutions typically require working space proportional to the size or complexity of the image. In this paper we develop efficient solutions to several such basic image processing problems on binary images, with additional constraints on working space. Our algorithms can be implemented with read-only input, using only a constant number of pointers and counters, and run in O(a+b log b) time where a denotes the area (number of pixels) of the image and b is a measure of its complexity (specifically, the total length of boundaries of all of its connected components). |
| キーワード(和) | |
| キーワード(英) | constant-work-space algorithm / computational geometry / binaru image / image processing / component |
| 資料番号 | COMP2010-12 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2010/5/12(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 制約されたメモリ上での2値画像処理の技法 |
| サブタイトル（和） | |
| タイトル（英） | Binary Image Processing with Limited Storage |
| サブタイトル（和） | |
| キーワード(1)（和/英） | / constant-work-space algorithm |
| 第 1 著者 氏名（和/英） | 浅野 哲夫 / Tetsuo ASANO |
| 第 1 著者 所属（和/英） | 北陸先端科学技術大学院大学情報科学研究科 Graduate School of Information Sciences, JAIST |
| 第 2 著者 氏名（和/英） | べレグ セルゲイ / Sergey BEREG |
| 第 2 著者 所属（和/英） | テキサス州立大学ダラス校計算機科学科 Department of Computer Science, University of Texas at Dallas |
| 第 3 著者 氏名（和/英） | ブゼール リリアン / Lilian BUZER |
| 第 3 著者 所属（和/英） | パリ東大学:LABINFO-IGM Universite Paris-Est:LABINFO-IGM |
| 第 4 著者 氏名（和/英） | カークパトリック デビッド / David KIRKPATRICK |
| 第 4 著者 所属（和/英） | ブリティッシュコロンビア大学計算機科学科 Department of Computer Science, University of British Columbia |
| 発表年月日 | 2010-05-19 |
| 資料番号 | COMP2010-12 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | 37 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |