著者

櫻井敦史 平田 富夫

出版者

情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.41, no.12, pp.3344-3351, 2000-12-15

被引用文献数

1

---

モルフォロジー演算は画像の特徴抽出やノイズ除去など 様々な画像処理に用いられる基本的処理である. 2値画像入力に対するその時間計算量は, 入力画像のサイズを $n?times n$, フィルタのサイズを $r?times r$ とすると? $O(n^2r^2)$ となり,処理時間がフィルタサイズに大きく依存する. しかし距離変換を用いることで処理時間がフィルタサイズに依存しな いモルフォロジー演算を行うことが可能である. 本研究ではフィルタ形状のあるクラスに対しては, $O(n^2)$ 時間でモルフォロジー演算ができることを示す. このクラスに入るフィルタ形状の例をあげると,円,長円形, 正三角形,長方形,台形などであり, 画像処理で用いられるフィルタのほとんどが含まれる.Mathematical morphology is used for feature extractionand noise elimination in image processing.Morphological operation for a binary image of size $n\times n$with a filter of size $r\times r$ is performed in $O(n^2r^2)$ time,and thus the computation time depends heavily on the filter size.By using distance transformation,morphological operation can be donein time independent of the filter size.In this paper,we show that morphological operation can be donein $O(n^2)$ time for some class of filter shapes.This class contains most of filter shapes which appear in image processing,such as circle, rectangle, equilateral triangle, trapezoid, etc.

著者

櫻井敦史 平田 富夫

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.41, no.12, pp.3344-3351, 2000-12-15

---

モルフォロジー演算は画像の特徴抽出やノイズ除去など 様々な画像処理に用いられる基本的処理である. 2値画像入力に対するその時間計算量は, 入力画像のサイズを $n?times n$, フィルタのサイズを $r?times r$ とすると? $O(n^2r^2)$ となり,処理時間がフィルタサイズに大きく依存する. しかし距離変換を用いることで処理時間がフィルタサイズに依存しな いモルフォロジー演算を行うことが可能である. 本研究ではフィルタ形状のあるクラスに対しては, $O(n^2)$ 時間でモルフォロジー演算ができることを示す. このクラスに入るフィルタ形状の例をあげると,円,長円形, 正三角形,長方形,台形などであり, 画像処理で用いられるフィルタのほとんどが含まれる.

著者

謝旭珍 柳浦睦憲 小野 孝夫 平田 富夫

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2007, no.66, pp.31-38, 2007-07-03

---

グラフの均等辺彩色とは,多重無向グラフと色数が与えれたとき,任意の頂点と任意の2色に対して,その頂点に接続する辺のうちそれぞれの色で塗られているものの本数の差が高々2であるような辺彩色である.与えられたグラフの頂点数を$n$,辺数を$m$とし,色数を$k$とする.謝らは,任意の多重グラフを$O(m2/k)$時間で均等辺彩色するアルゴリズムを提案した.本論文では,彼らのアルゴリズムに変更を加え,初期辺彩色をランダムに与える場合の実行時間を解析する.そして,任意の定数$\varepsilon >0$に対し,実行時間が高い確率で$O(n^{1/2} m^{3/2+\varepsilon })$となることを示す.それは,グラフが密で$k$が小さいときには,既存のアルゴリズムよりも速くグラフを均等辺彩色できることを示す結果である.Given a multigraph $G=(V,E)$ with $n$ vertices and $m$ edges and a color set${\cal C}=\{1,2,\ldots,k\}$, the nearly equitable edge coloring is an assignment of given colors to edges in $G$ such that, among the edges incident to each vertex, the numbers of edges colored with any two colors differ by at most two. Xie~et~al. presented an algorithm to solve this problem in $O(m2/k)$ time. In this paper, we investigate the running time of a modified version of their algorithm in which the initial edge coloring is generated randomly. The new time complexity is proved to be $O(n^{1/2} m^{3/2+\varepsilon })$for arbitrarily small constant $\varepsilon >0$with high probability for sufficiently large $n$,which is better than Xie at al.'s original algorithm when the graph is dense and $k$ is small.

著者

加藤 敏洋 平田 富夫 斉藤 豊文 吉瀬 謙二

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-II, 情報・システム, II-情報処理 (ISSN:09151923)

巻号頁・発行日

vol.78, no.12, pp.1750-1757, 1995-12-25

被引用文献数

11

---

本論文では,サイズがN×Nの2値画像のユークリッド距離変換をO(N^2)時間で実行するアルゴリズムを与える.距離変換とは,入力として与えられた2値画像の各画素についてそこから最も近い0画素への距離を求める処理で,ディジタル画像処理における基本的な処理である.このアルゴリズムは,4近傍距離や8近傍距離などユークリッド距離以外の他の距離についてもアルゴリズム中の距離関数を置き換えるだけで距離変換が実行でき,その意味で一般的な距離変換アルゴリズムとなっている.また,p(1≦p≦N)台のプロセッサを用意すればO(N^2/p)時間の並列アルゴリズムが得られ,これまでの並列アルゴリズムより効率が良い.

著者

宮澤 雅史 曽培峰 磯 直行 平田 富夫

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2002, no.103, pp.43-49, 2002-11-08

---

ユークリッド距離変換はパターン認識やモルフォロジーフィルターなど画像処理の様々な分野で応用されている。本論文ではユークリッド距離変換のための、シストリックアレイを用いたハードウェアアルゴリズムを提案する。計算時間の効率化と乗算器などのハードウェア資源を削減するための工夫をし、サイズ$N ?times N$の2値画像に対しクロック数$3N-1$でユークリッド距離変換処理を実行する。そのために必要なハードウェア量は$O(N^2)$である。The Euclidean distance transform is applied in various fields of image processing, such as pattern recognition and morphological filter.In this paper, we propose a hardware algorithm using a systolic array that performs Euclidean distance transform. It is designed so that hardware resources, such as multipliers and comparators, are reduced and processing speed is efficient. It performs Euclidean distance transform for an input of $N \times N$ binary image in $3N-1$ clocks, and the size of the required hardware resources is $O(N^2)$.