JPS5952362A - パタ−ン距離変換装置 - Google Patents
パタ−ン距離変換装置Info
- Publication number
- JPS5952362A JPS5952362A JP57163389A JP16338982A JPS5952362A JP S5952362 A JPS5952362 A JP S5952362A JP 57163389 A JP57163389 A JP 57163389A JP 16338982 A JP16338982 A JP 16338982A JP S5952362 A JPS5952362 A JP S5952362A
- Authority
- JP
- Japan
- Prior art keywords
- distance
- value
- ce1l
- point
- cells
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F15/00—Digital computers in general; Data processing equipment in general
- G06F15/76—Architectures of general purpose stored program computers
- G06F15/80—Architectures of general purpose stored program computers comprising an array of processing units with common control, e.g. single instruction multiple data processors
- G06F15/8007—Architectures of general purpose stored program computers comprising an array of processing units with common control, e.g. single instruction multiple data processors single instruction multiple data [SIMD] multiprocessors
Landscapes
- Engineering & Computer Science (AREA)
- Computer Hardware Design (AREA)
- Theoretical Computer Science (AREA)
- Computing Systems (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Image Analysis (AREA)
- Image Processing (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
この発明は、デジタル画像処理やパターン認識忙おける
パターン距離変換装置に関するものである。
パターン距離変換装置に関するものである。
デジタル画像処理やパターン認識の分野において、距離
変換は図形の細線化、圧縮と再生、構造解析、図形の分
離と計測などに広（用いられる重要な技術である。ｚ値
図形に対する距離変換は、最初、米国のＲ（Ｂ１６ｎｆ
ｅｌｄらによって提案さｔＬだ。
変換は図形の細線化、圧縮と再生、構造解析、図形の分
離と計測などに広（用いられる重要な技術である。ｚ値
図形に対する距離変換は、最初、米国のＲ（Ｂ１６ｎｆ
ｅｌｄらによって提案さｔＬだ。
まず、値″′Ｏ”、′１” を持つ２値図形をｆ（ｚ）
＝ｆ（ｘ、ｙ） で表わす。ここで、ｚ＝ｆ（ｘ＋ｙ
）は正方格子状に区切られた２次元上の１点である。
＝ｆ（ｘ、ｙ） で表わす。ここで、ｚ＝ｆ（ｘ＋ｙ
）は正方格子状に区切られた２次元上の１点である。
値”ｏ″の点を白点、値″１″の点を黒点と呼ぶ。
実施例では、ｆ （Ｚ） ＝ ０の点の距離を０”とし
、ｔ（ｚ＞＝ｘの各点からの０″点までの距離な求める
こと、すなわち白点からの距離変換を扱う。
、ｔ（ｚ＞＝ｘの各点からの０″点までの距離な求める
こと、すなわち白点からの距離変換を扱う。
次に、距離の伝播を行うため、ｕ （ｚ） ＊ ｖ
（ｚ）の２面、そのベクトル表示としてＷ（Ｚ）を導入
する。すなわち、 ｗ （ｚ） ＝ （ｕ （ｚ） −ｖ （ｚ） ）
−−（１）となる。ここで、Ｗ（Ｚ）はユークリッド
距離のぺ ４クトル表現であり、Ｚ＋Ｗ（Ｚ＞の位置に
点２までのユークリッド距離を最小とする白点が存在す
ることを意味する。ｕ （Ｚ） ＋ ｖ （ｚ）はその
Ｘ、７成分である。
（ｚ）の２面、そのベクトル表示としてＷ（Ｚ）を導入
する。すなわち、 ｗ （ｚ） ＝ （ｕ （ｚ） −ｖ （ｚ） ）
−−（１）となる。ここで、Ｗ（Ｚ）はユークリッド
距離のぺ ４クトル表現であり、Ｚ＋Ｗ（Ｚ＞の位置に
点２までのユークリッド距離を最小とする白点が存在す
ることを意味する。ｕ （Ｚ） ＋ ｖ （ｚ）はその
Ｘ、７成分である。
従って、ユークリッド距離ｄｏは成分ベクトルの絶対値
、すなわち、 ｄｏ （ｚ）＝ Ｉｗ（ｚ） １ −Ｖ／ｒ：（ｚ）”十ｖ （ｚ）” −−・−・・（２
）である。
、すなわち、 ｄｏ （ｚ）＝ Ｉｗ（ｚ） １ −Ｖ／ｒ：（ｚ）”十ｖ （ｚ）” −−・−・・（２
）である。
次に、点ｚ＝（ｘ、ｙ）から隣接しに点（近傍点）への
ベクトルとして、第１図に示すｓｌを導入する。ここで
Ｓ。は自分自身の点を表わし、Ｚ 十Ｓ Ｏ＝２である
。また、次式で定義される点２における近傍点の集合Ｓ
’ａ （ｚ） ＋ Ｓ’ｓ （ｚ）をそれぞれ２
の４近傍、８近傍と呼ぶ。
ベクトルとして、第１図に示すｓｌを導入する。ここで
Ｓ。は自分自身の点を表わし、Ｚ 十Ｓ Ｏ＝２である
。また、次式で定義される点２における近傍点の集合Ｓ
’ａ （ｚ） ＋ Ｓ’ｓ （ｚ）をそれぞれ２
の４近傍、８近傍と呼ぶ。
Ｓ’ａ （Ｚ） ” （Ｚ ＋ ８１１１ ＝Ｏｒ Ｌ
Ｌ ５ｒ ７ ）ｚ） ｒ 、Ｓａ （ｚンを用
いる。
Ｌ ５ｒ ７ ）ｚ） ｒ 、Ｓａ （ｚンを用
いる。
８４ （ｚ）＝Ｉｚ＋ｓ＋１ｔ＝ｏ、ｌ、ａ、ｓ、７
）この時もそれぞれ２の４近傍、８近傍と呼ぶ。
）この時もそれぞれ２の４近傍、８近傍と呼ぶ。
以上の表記方法のもとで、従来の４近傍距離ｄ４（２）
、および８近傍距離ｄｓ （ｚ）は次のように定義さ
れる。距離変換は局所並列演算の繰り返し、すなわち、
近傍点との相互作用を各点で繰り返すことによって実現
される。
、および８近傍距離ｄｓ （ｚ）は次のように定義さ
れる。距離変換は局所並列演算の繰り返し、すなわち、
近傍点との相互作用を各点で繰り返すことによって実現
される。
まず、繰り返しの時刻１＝０における初期値として、
ただし、Ｎは結果として求まる全ての短離より大きい正
の値である。一般に、格子点の分割数以上の値を用いれ
ば良い。
の値である。一般に、格子点の分割数以上の値を用いれ
ば良い。
次に、繰り返しの時刻ｔ＝１．２．３・・・・・・に対
して ”４ （Ｚ） ＝ｍ、 ｅ ｂ ＝ ｅ２戸ａｒ （
ｚ ＋ｓ、） ＋ ｌ５ｌｌ ）−（６１繰り返しの停
止条件は、全ての点２に対してｄ’ａ 、４ （ｚ）
＝ ｄ景（ｚ） ・・・・・・・・・・・・・・・・
・・・・・・・・（８）である。
して ”４ （Ｚ） ＝ｍ、 ｅ ｂ ＝ ｅ２戸ａｒ （
ｚ ＋ｓ、） ＋ ｌ５ｌｌ ）−（６１繰り返しの停
止条件は、全ての点２に対してｄ’ａ 、４ （ｚ）
＝ ｄ景（ｚ） ・・・・・・・・・・・・・・・・
・・・・・・・・（８）である。
このようにして求められた４近傍距離ｄ４ の例な第２
図に、８近傍距離ｄ８ の例を第３図に示す。
図に、８近傍距離ｄ８ の例を第３図に示す。
第２図、第３図において、各（ａ１図は中央の１点にの
み白点かありそれが拡散した例であり、各（ｂ）図は学
徒ｌＯの円の外側が全て白点でそれが円の内側に伝播さ
れた例である。この例からも明らかなように、４近傍距
離及び８近傍距離で伝播した場合、正方格子の持つ異方
性によって、かなり歪んだ距離が伝播される。そこで、
この対策として４近傍と８近傍な交互に用いて８角形状
の距離変換も提案されているが、それでも真の距離（以
下「ユークリッド距離」と称す）からのずれが依然とし
て存在する。
み白点かありそれが拡散した例であり、各（ｂ）図は学
徒ｌＯの円の外側が全て白点でそれが円の内側に伝播さ
れた例である。この例からも明らかなように、４近傍距
離及び８近傍距離で伝播した場合、正方格子の持つ異方
性によって、かなり歪んだ距離が伝播される。そこで、
この対策として４近傍と８近傍な交互に用いて８角形状
の距離変換も提案されているが、それでも真の距離（以
下「ユークリッド距離」と称す）からのずれが依然とし
て存在する。
この発明は、上述の点にかんがみてなされたもので、各
点での伝播情報を単に距離という単一の値（スカラー値
）とするのではなく、成分に分割（ベクトル値ンして、
格子点からの伝播によって抽出し、上記のような異方性
の全くない距離、すなわちユークリッド距離を得るパタ
ーン距離変換装置を提供することを目的とする。以下、
この発明の詳細な説明し、その一実施例を図面に基づい
て説明する。
点での伝播情報を単に距離という単一の値（スカラー値
）とするのではなく、成分に分割（ベクトル値ンして、
格子点からの伝播によって抽出し、上記のような異方性
の全くない距離、すなわちユークリッド距離を得るパタ
ーン距離変換装置を提供することを目的とする。以下、
この発明の詳細な説明し、その一実施例を図面に基づい
て説明する。
この発明の一実施例としての距離変換は以下のように表
わされる。
わされる。
まず、１＝０における初期値として、
ここで、Ｎは充分大きな正の整数である。
次に繰り返しの時刻ｔ＝１．２．３・・・・・・・・・
・・・に対して ｗ’（ｚ）＝ｗ’−’（ｚ＋ｓｊ）＋ｓｊ＋＋＋＋＋＋
＋・１＋＋・＋・＋＋＋＋ａｏ＞ここではｊは、 １ｗ’−’ （ｚ十ｓＪ）＋ｓｊ） Ｉ”＝ｍ ｉ
ｎ （１ｗ”（ｚ＋ｓ＋ ）＋ｓ、ｌ” ）ｓｔｅｓ
’ｓ （ｚ） ・・・・・・・・・・・・・・・αｌ）なる１あうち１
番番号の小さいものである。
・・・に対して ｗ’（ｚ）＝ｗ’−’（ｚ＋ｓｊ）＋ｓｊ＋＋＋＋＋＋
＋・１＋＋・＋・＋＋＋＋ａｏ＞ここではｊは、 １ｗ’−’ （ｚ十ｓＪ）＋ｓｊ） Ｉ”＝ｍ ｉ
ｎ （１ｗ”（ｚ＋ｓ＋ ）＋ｓ、ｌ” ）ｓｔｅｓ
’ｓ （ｚ） ・・・・・・・・・・・・・・・αｌ）なる１あうち１
番番号の小さいものである。
繰り返しの停止条件は、すべての点２に対して１ｗ’（
ｚンＩ＝１ｗｔ−’（ｚ）ｌ・・・・・・・・・・・・
・・・・・・・・・α２）である。
ｚンＩ＝１ｗｔ−’（ｚ）ｌ・・・・・・・・・・・・
・・・・・・・・・α２）である。
以上のように、この発明による距離変換においては、各
点での評価は距離ｄｅ （ｚ） ＝ Ｉｗ （ｚ） ｌ
で行いながら、伝播はベクトルＷ（Ｚ）で行うことによ
り、近傍系の持つ異方性を吸収している。
点での評価は距離ｄｅ （ｚ） ＝ Ｉｗ （ｚ） ｌ
で行いながら、伝播はベクトルＷ（Ｚ）で行うことによ
り、近傍系の持つ異方性を吸収している。
第４図はこの発明の距離変換による例を示す図である。
同図において、（ａ）、（ｂ）は第２図、第３図の（ａ
）、（ｂ）と同様、（ａ）は１点からの拡散を示し、（
ｂ）は円の内部への伝播を示す。第４図（ａ）。
）、（ｂ）と同様、（ａ）は１点からの拡散を示し、（
ｂ）は円の内部への伝播を示す。第４図（ａ）。
、（ｂ）Ｙ第２図（ａ）、（ｂ）、第３図（ａ）、（ｂ
）と比較すると異方性の除去が完全に行われていること
がわかる。
）と比較すると異方性の除去が完全に行われていること
がわかる。
第５図はこの発明の一実施例な示す距離変換装置のプμ
ツク図である。同図において、１は中央制御装置（以下
、ＣＰＵと称す）、２〜１７は２次元の各点毎に処理機
能を持つ回路（以下、Ｃｅ１ｌと称す）である。図にお
いては、縦横４×４のＣｅ１ｌが配列されズいるが、実
際のパターン処理においては画面の分割数だけ配列され
ているものＣｅ１ｌ Ｌ Ｉ ＣＳｔ Ｌ
Ｌ ｉ ＩＬ Ｉ Ｌ１４＋１５．１６．１７
を接続するバス（以下、Ｌ−ＢＵＳと称す）である。
ツク図である。同図において、１は中央制御装置（以下
、ＣＰＵと称す）、２〜１７は２次元の各点毎に処理機
能を持つ回路（以下、Ｃｅ１ｌと称す）である。図にお
いては、縦横４×４のＣｅ１ｌが配列されズいるが、実
際のパターン処理においては画面の分割数だけ配列され
ているものＣｅ１ｌ Ｌ Ｉ ＣＳｔ Ｌ
Ｌ ｉ ＩＬ Ｉ Ｌ１４＋１５．１６．１７
を接続するバス（以下、Ｌ−ＢＵＳと称す）である。
各Ｃｅ１ｌ と近傍のＣｅ１ｌ とは、第６図に示す
ように、それぞれ４本の線２１，２２．２３．２４でＣ
ｅ１ｌを構成するレジスタＥＲＸ、ＥＲＹ、ＥＷＸ、Ｅ
ＷＹが接続される構造となっている。ここで信号ＴＳＹ
ＮＣはＣＰＵ１から各Ｃｅ１ｌ ２〜１７に供給される
信号で、各Ｃｅ１ｌ ２〜ＩＴが実行すべき内容を指示
するための同期信号である。
ように、それぞれ４本の線２１，２２．２３．２４でＣ
ｅ１ｌを構成するレジスタＥＲＸ、ＥＲＹ、ＥＷＸ、Ｅ
ＷＹが接続される構造となっている。ここで信号ＴＳＹ
ＮＣはＣＰＵ１から各Ｃｅ１ｌ ２〜１７に供給される
信号で、各Ｃｅ１ｌ ２〜ＩＴが実行すべき内容を指示
するための同期信号である。
信号５ＲＵＮは各Ｃｅ１１２〜１７からＣＰＵ１へ供給
される信号で、演算結果が１時刻前に比べて変化した時
に１”になる信号である。Ｌ−ＢＵＳ２０には前記ＣＰ
Ｕ１から周辺のＣｅ１ｌ ２． ３゜４．５．６，９
，１０．１３，１４．１５．１６゜１７へ供給されるＣ
ｅ１ｌへのパターン・データ書込用信号が通り、データ
は最下行のＣｅ１１１４゜１５．１６．１７から順に上
の行へ転送する。Ｕ−ＢＵＳ１９は最下行のＣａ１ｌ
２．３．４．５からＣＰＵ１へ供給されるＣｅ１ｌから
のパターン・データ読出用信号が通り、データは最下行
のＣａ１１２．３，４．５から読み出される。
される信号で、演算結果が１時刻前に比べて変化した時
に１”になる信号である。Ｌ−ＢＵＳ２０には前記ＣＰ
Ｕ１から周辺のＣｅ１ｌ ２． ３゜４．５．６，９
，１０．１３，１４．１５．１６゜１７へ供給されるＣ
ｅ１ｌへのパターン・データ書込用信号が通り、データ
は最下行のＣｅ１１１４゜１５．１６．１７から順に上
の行へ転送する。Ｕ−ＢＵＳ１９は最下行のＣａ１ｌ
２．３．４．５からＣＰＵ１へ供給されるＣｅ１ｌから
のパターン・データ読出用信号が通り、データは最下行
のＣａ１１２．３，４．５から読み出される。
Ｌ−ＢＵＳ ２０は２つの機能を持つ。１つハ、各Ｃｅ
１ｌに初期値設定する時に、最下行のＣｅ１ｌ １４゜
１５．１６．１７を通してＣＰＵ１からのデータを転送
する。２つ目は、距離変換演算中に、周辺部のＣｅ１ｌ
２． ３． ４． ５． ６． ９． １０．１３゜
１４．１５，１６．１７に対して、境界値を与える。本
実施例では、第（９）式のＮを常に周辺部から与える。
１ｌに初期値設定する時に、最下行のＣｅ１ｌ １４゜
１５．１６．１７を通してＣＰＵ１からのデータを転送
する。２つ目は、距離変換演算中に、周辺部のＣｅ１ｌ
２． ３． ４． ５． ６． ９． １０．１３゜
１４．１５，１６．１７に対して、境界値を与える。本
実施例では、第（９）式のＮを常に周辺部から与える。
次に、Ｕ−ＢＵＳ１９は最下行のＣｅ１１２．３，４．
５からＣＰＵ１へのデータが通る。
５からＣＰＵ１へのデータが通る。
このバスを通して距離変換された結果がＣＰＵ１へ転送
される。
される。
同期信号ＴＳＹＮＣは、以下６種の信号に分けられる。
（１）ＴＳＹＮＣ（ＣＬＥＡＲ）、各Ｃｅ１ｌの初期化
のためリセットする機能を有する。
のためリセットする機能を有する。
（２１ＴｓＹＮｃ（ｔ）、距離変換の１時刻分の演算指
令（繰り返し時刻ｔ）する機能を有する。
令（繰り返し時刻ｔ）する機能を有する。
＋３１ＴＳＹＮＣ（ＳＨＩＦＴ）、データＹ１行上へ移
動（ＥＲＸ３→ＥＷＸ７．ＥＲＹ３→ＥｗＹ７）する機
能を有する。
動（ＥＲＸ３→ＥＷＸ７．ＥＲＹ３→ＥｗＹ７）する機
能を有する。
（４）ＴＳＹＮＣ（ＳＥＴＷ）、各Ｃｅ１１への書込（
ＥＲＸ３→ＥＲＸＯ，ＥＲＹ３→ＥＲＹＯ）機能を有す
る。
ＥＲＸ３→ＥＲＸＯ，ＥＲＹ３→ＥＲＹＯ）機能を有す
る。
（５）ＴＳＹＮＣ（ＳＥＴＲ）、各Ｃｅ１ｌからの読出
（ＥＲＸＯ→ＥＷＸ７．ＥＲＹＯ→１ＤＷＹ７）機能を
有する。
（ＥＲＸＯ→ＥＷＸ７．ＥＲＹＯ→１ＤＷＹ７）機能を
有する。
（６１ＴＳＹＮＣ（ＲＥＳＥＴ）、Ｃｏ １１の内容を
転送用レジスタへ入れる（ＥＲＸＯ→ＥＷＸｉ、。
転送用レジスタへ入れる（ＥＲＸＯ→ＥＷＸｉ、。
ＥＲＹＯ→ＥＷＹＩ ｌ＝１〜８）機能を有する。
次に各部の動作を距離変換の処理に沿って説明する。処
理は、大きり（１）初期値設定、（２）距離変換演算、
（３）結果の転送の３段階に分１テられる。（１）初期
値設定部では、ＣＰＵ１からの１画面分のデータを対応
する各Ｃｅ１ｌに転送する。（２）距離変換演算部では
、各Ｃｅ１ｌが、演算と近傍のＣａｌ １ との情報交
換を繰り返す事により、距離変換を行う。
理は、大きり（１）初期値設定、（２）距離変換演算、
（３）結果の転送の３段階に分１テられる。（１）初期
値設定部では、ＣＰＵ１からの１画面分のデータを対応
する各Ｃｅ１ｌに転送する。（２）距離変換演算部では
、各Ｃｅ１ｌが、演算と近傍のＣａｌ １ との情報交
換を繰り返す事により、距離変換を行う。
（３）最後に、求められた結果なＣＰＵ１へ転送する。
まず、初期値設定について詳しく＃１．明する。ここで
は、設定すべき図形を、ＣＰＵ１からＴ、 −ＢＵＳ２
０を通じ、Ｃｅ１ｌの最下行から順次上へ送る。
は、設定すべき図形を、ＣＰＵ１からＴ、 −ＢＵＳ２
０を通じ、Ｃｅ１ｌの最下行から順次上へ送る。
処理すべきパターンの大きさはＭＸＭとし、Ｃｅ１ｌも
Ｍ行Ｍ列に配列されているとする。この実施例では第５
図に示すように縦横４×４である。Ｌ−ＢＵＳ ２０は
ＣＰＵＩからのデータを選択的に周辺のＣｅ１ｌ ２ｔ
Ｌ ４＊ Ｌ Ｌ Ｌ １０＊Ｉ Ｌ１
４．１５，１６．１７のレジスタに送ることができる。
Ｍ行Ｍ列に配列されているとする。この実施例では第５
図に示すように縦横４×４である。Ｌ−ＢＵＳ ２０は
ＣＰＵＩからのデータを選択的に周辺のＣｅ１ｌ ２ｔ
Ｌ ４＊ Ｌ Ｌ Ｌ １０＊Ｉ Ｌ１
４．１５，１６．１７のレジスタに送ることができる。
この機能を用いて、最下行ｙ＝４の各Ｃｅ１ｆ １４
，１５．１６．１７のレジスタＥＲＸ３、ＥＲＹ３に最
下行ｙ＝１のそれぞれのＣｅ１１２．３，４．５に入る
べき内容をＬ−ＢＵＳ ２０を通じて逐次セットする。
，１５．１６．１７のレジスタＥＲＸ３、ＥＲＹ３に最
下行ｙ＝１のそれぞれのＣｅ１１２．３，４．５に入る
べき内容をＬ−ＢＵＳ ２０を通じて逐次セットする。
その内容は第（９）式で示されるように、白点の時間”
、黒点の時″Ｎ”である。ＥＲＸ３はＸ成分用、ＥＲＹ
３はｙ成分用レジスタであり、第（９）式に従って双方
に同じ値が入れられる。記号Ｘ、Ｙは他のレジスタに対
しても同様に用いられている。
、黒点の時″Ｎ”である。ＥＲＸ３はＸ成分用、ＥＲＹ
３はｙ成分用レジスタであり、第（９）式に従って双方
に同じ値が入れられる。記号Ｘ、Ｙは他のレジスタに対
しても同様に用いられている。
次に、同期信号ＴＳＹＮＣ（Ｓ ＩＨＦ’Ｔ ）により
ＥＲＸ３．ＥＲＹ３１７）内容ｖ−ｔ−レぞｔＬＥＷＸ
７゜ＥＷＹ７に移丁。結果的にＣｅ１ｌ １４． １
５，１６゜１７のＥＷＸ７．ＥＷＹ７の内容は、近傍点
との接続線２３．２４を通じて、それぞれ直上性のＣｅ
１ｌ １０．１１．１２．１３のＥＲＸ３．ＥＲＹ３
へ伝えられる。従って、ｙ＝Ｍ行の内容は１２Ｍ−１行
へ伝えられることになる。
ＥＲＸ３．ＥＲＹ３１７）内容ｖ−ｔ−レぞｔＬＥＷＸ
７゜ＥＷＹ７に移丁。結果的にＣｅ１ｌ １４． １
５，１６゜１７のＥＷＸ７．ＥＷＹ７の内容は、近傍点
との接続線２３．２４を通じて、それぞれ直上性のＣｅ
１ｌ １０．１１．１２．１３のＥＲＸ３．ＥＲＹ３
へ伝えられる。従って、ｙ＝Ｍ行の内容は１２Ｍ−１行
へ伝えられることになる。
次’に％Ｌ−ＢＵＳ ２ （１−通じてｙ＝２行のｃｅ
１１Ｂ、７，８．９に入るべき内容を、ｙ＝４行目の
それぞれのＣｅ１ｌ １４，１５．１６．１７のＥＲＸ
３．ＥＲＹ３にセットする。１行分のデータのセット終
了後、ＣＰＵＩからの同期信号Ｔ ５ＹＮＣ（ＳＨＩＦ
Ｔ）により、ｙ＝３行目の内容はｙ＝２行目に、ｙ＝４
行目の内容はｙ＝３行目へと１行上へ移動する。さらに
もう一度のＣＰＵ１か内容はＭ−１へと１行上へ移動し
、この動作なＭ−１回繰り返すと最初最下行７＝Ｍにセ
ットされた内容はＭ−１行だけ上のｙ＝１行に移動され
ることになる。このように、全体に初期値として入れる
べき値がそれぞれのＥＲＸ３． ＥＲＹ３に入っている
。ここで同期信号ＴＳＹＮＣ（ＳＥＴ）により、各Ｃｅ
１ｌの内部レジスタＥＲＸＯ，ＥＲＹＯにそれぞれＥＲ
Ｘ３．ＥＲＹ３のデータを移して初期値セットを終了す
る。
１１Ｂ、７，８．９に入るべき内容を、ｙ＝４行目の
それぞれのＣｅ１ｌ １４，１５．１６．１７のＥＲＸ
３．ＥＲＹ３にセットする。１行分のデータのセット終
了後、ＣＰＵＩからの同期信号Ｔ ５ＹＮＣ（ＳＨＩＦ
Ｔ）により、ｙ＝３行目の内容はｙ＝２行目に、ｙ＝４
行目の内容はｙ＝３行目へと１行上へ移動する。さらに
もう一度のＣＰＵ１か内容はＭ−１へと１行上へ移動し
、この動作なＭ−１回繰り返すと最初最下行７＝Ｍにセ
ットされた内容はＭ−１行だけ上のｙ＝１行に移動され
ることになる。このように、全体に初期値として入れる
べき値がそれぞれのＥＲＸ３． ＥＲＹ３に入っている
。ここで同期信号ＴＳＹＮＣ（ＳＥＴ）により、各Ｃｅ
１ｌの内部レジスタＥＲＸＯ，ＥＲＹＯにそれぞれＥＲ
Ｘ３．ＥＲＹ３のデータを移して初期値セットを終了す
る。
次に、繰り返し処理に先立ってＴＳＹＮＣ（ＲＥＳＥＴ
）信号により、ＥＲＸＯの内容を自分のＣｅ１ｌｎ８個
のＥＷＸＩ（＋＝１〜８）に、ＥＲＹＯの内容を自分の
Ｃｅ１ｌの８個のＥＷＹＩ（ｉ＝１〜８）に転送する。
）信号により、ＥＲＸＯの内容を自分のＣｅ１ｌｎ８個
のＥＷＸＩ（＋＝１〜８）に、ＥＲＹＯの内容を自分の
Ｃｅ１ｌの８個のＥＷＹＩ（ｉ＝１〜８）に転送する。
結果として、これらは近傍のセルのＥＲＸｉ、ＥＲＹＩ
へ送られる。
へ送られる。
次に、距離変換のための繰り返し演算について説明する
。第７図はＣｅ１ｌのグルツク回路図である。同図にお
いて二重線で示した１２１〜１２７は複数（ｌ＝１〜８
）のレジスタ間の結線をまとめて表わしているバスであ
る。
。第７図はＣｅ１ｌのグルツク回路図である。同図にお
いて二重線で示した１２１〜１２７は複数（ｌ＝１〜８
）のレジスタ間の結線をまとめて表わしているバスであ
る。
ｘ、ｙ両成分ｕ（ｚ） ｒ ｖ （ｚ）用内部レジス
タＥＲＸＯ３０，ＥＲＹＯ３１（図面ではそれぞれ左上
と右下に図示しているが同一のもの）の信号はそのまま
２乗和回路５Ｑ１１８０に入力される。２乗和回路５Ｑ
ｏ８０の出力は、それぞれの２乗和すなわち１ｖｒ（ｚ
）げ である。
タＥＲＸＯ３０，ＥＲＹＯ３１（図面ではそれぞれ左上
と右下に図示しているが同一のもの）の信号はそのまま
２乗和回路５Ｑ１１８０に入力される。２乗和回路５Ｑ
ｏ８０の出力は、それぞれの２乗和すなわち１ｖｒ（ｚ
）げ である。
次に、近傍Ｃｅｌ １からの値はレジスタＥＲＸｉ４８
〜５５．ＥＲＹｉ５６〜６３を通して入力される。それ
ぞれのレジスタの値に加減算回路ＡｓＸ１６４〜７１．
ＡＳＹｉ７２〜Ｔ９により第１表に示すように値が加減
される。すなわち第（１０）ＭＩＮ８９では、この９人
力うち最小の値（ｍ ｉ、ｎ （Ｉｗ’＝ （ｚ＋
ｓ＋）＋ｓ＋ ｌ”） ）Ｓ＋［ヨ＆（巳と） をもつｌのうちの一番小さい１の値、すなわち第（１１
）式のｊの値を出力し、ゲート回路Ｇ９０のゲート制御
信号及び回路ＣＬ９３への入力となる。
〜５５．ＥＲＹｉ５６〜６３を通して入力される。それ
ぞれのレジスタの値に加減算回路ＡｓＸ１６４〜７１．
ＡＳＹｉ７２〜Ｔ９により第１表に示すように値が加減
される。すなわち第（１０）ＭＩＮ８９では、この９人
力うち最小の値（ｍ ｉ、ｎ （Ｉｗ’＝ （ｚ＋
ｓ＋）＋ｓ＋ ｌ”） ）Ｓ＋［ヨ＆（巳と） をもつｌのうちの一番小さい１の値、すなわち第（１１
）式のｊの値を出力し、ゲート回路Ｇ９０のゲート制御
信号及び回路ＣＬ９３への入力となる。
第１表
回路ＣＬ９３は、入力が０の時０．入カが１以上の時１
に変える。この出力は信号５ＲＵＮとしてＣＰＵＩへ送
られる。
に変える。この出力は信号５ＲＵＮとしてＣＰＵＩへ送
られる。
一方、ゲート回路Ｇ９０への入力とじて、２乗和回路Ｓ
Ｑｈ （ｋ＝０〜８ ）８０〜８ ｇの入力と同様な
、９対の値が入力される。ゲート回路Ｇ９０では、最小
値検出器ＭＩＮ８９からの制御信号ｊにより、５番目の
入力対な出方側へ送る、つまりゲート回路Ｇ９０の出力
は、第（１０）式の左辺に相当する。これらの！、７両
成分成分号は、遅延回路ＤＥＬＸ９１．ＤＥＬＹ９２１
Ｃより、一定時間遅延され、内部レジスタＥＲＸＯ３０
，ＥＲＹＯ３１、及び、近傍Ｃｅ１ｌへのレジスタＥＷ
ＸＩ３２〜３９．ＥＷＹｉ４０〜４７に送られる。
Ｑｈ （ｋ＝０〜８ ）８０〜８ ｇの入力と同様な
、９対の値が入力される。ゲート回路Ｇ９０では、最小
値検出器ＭＩＮ８９からの制御信号ｊにより、５番目の
入力対な出方側へ送る、つまりゲート回路Ｇ９０の出力
は、第（１０）式の左辺に相当する。これらの！、７両
成分成分号は、遅延回路ＤＥＬＸ９１．ＤＥＬＹ９２１
Ｃより、一定時間遅延され、内部レジスタＥＲＸＯ３０
，ＥＲＹＯ３１、及び、近傍Ｃｅ１ｌへのレジスタＥＷ
ＸＩ３２〜３９．ＥＷＹｉ４０〜４７に送られる。
これにより！時刻分の動作が終了する。
繰り返し演算中は、周辺Ｃｅ１ｌの外側のレジスタは常
に充分大きな正の一定値Ｎに保たれている。
に充分大きな正の一定値Ｎに保たれている。
すなわち、第５図において、Ｌ−ＢＵＳ ２０の値がＮ
に保たれており、最下行のＣｅ１ｌ ２．３，４゜５の
レジスタＥＲＸ７．ＥＲＹ７．及び最下行のＣｅ１ｌ
１４，１５，１６．１７のレジスタＥＲＸ３、ＥＲＹ３
および最左列のＣｓ１ｌ ５． ９．１３゜１７のレ
ジスタＥＲＸ１．ＥＲＹ１および最左列のＣｅ１ｌ ２
． ６． １０．′１４のレジスタＥＲＸ５゜ＥＲＹ５
は常にＮになっている。
に保たれており、最下行のＣｅ１ｌ ２．３，４゜５の
レジスタＥＲＸ７．ＥＲＹ７．及び最下行のＣｅ１ｌ
１４，１５，１６．１７のレジスタＥＲＸ３、ＥＲＹ３
および最左列のＣｓ１ｌ ５． ９．１３゜１７のレ
ジスタＥＲＸ１．ＥＲＹ１および最左列のＣｅ１ｌ ２
． ６． １０．′１４のレジスタＥＲＸ５゜ＥＲＹ５
は常にＮになっている。
ＣＰＵ１では各Ｃｅ１ｌからバス１８を通っ曵供給され
る信号５ＲＵＮかＯｌすなわち、全ての点での距離の値
に変化がなくなった時、繰り返し演算を終了する。
る信号５ＲＵＮかＯｌすなわち、全ての点での距離の値
に変化がなくなった時、繰り返し演算を終了する。
最後に、各Ｃｅ１ｌ ２〜１７からＣＰＵ１へのデータ
転送は、初期データセラＦの時とは逆に、まず同期信号
ＴＳＹＮＣ（ＳＥＴＲ）ＶＣよりレジスタＥＲＸＯ３０
，ＥＲＹＯ３１の内容をレジスタＥＷＸ７３８．ＥＷＹ
７４６に移し、次にＵ−ＢＵＳ１９に出力されたデータ
のＣＰＵ１へのとり込みと同期信号ＴＳＹＮＣ（ＳＨＩ
ＦＴ）繰り返し忙より原炭上へ移動させたデータをＣＰ
Ｕ１へ送ることにより行う。
転送は、初期データセラＦの時とは逆に、まず同期信号
ＴＳＹＮＣ（ＳＥＴＲ）ＶＣよりレジスタＥＲＸＯ３０
，ＥＲＹＯ３１の内容をレジスタＥＷＸ７３８．ＥＷＹ
７４６に移し、次にＵ−ＢＵＳ１９に出力されたデータ
のＣＰＵ１へのとり込みと同期信号ＴＳＹＮＣ（ＳＨＩ
ＦＴ）繰り返し忙より原炭上へ移動させたデータをＣＰ
Ｕ１へ送ることにより行う。
なお、この発明の実施例としてのパターン距離変換方式
は、以下に述べるような変更、およびそれらの複合的な
変更は可能である。
は、以下に述べるような変更、およびそれらの複合的な
変更は可能である。
（１）上記実施例においては、各点にＣｅ１ｌを配列し
た構造を持っているが、演算装置がこれより少数、例え
ば１個で実現すること。
た構造を持っているが、演算装置がこれより少数、例え
ば１個で実現すること。
（２）上記実施例の伝播式において、正確なユークリッ
ド距離ではなく成分情報を得る事を主な目的として、８
近傍Ｓａ （Ｚ）ではなく４近傍Ｓ、 （ｚ）を用い
ること。
ド距離ではなく成分情報を得る事を主な目的として、８
近傍Ｓａ （Ｚ）ではなく４近傍Ｓ、 （ｚ）を用い
ること。
また、上記実施例においては、白地から黒地への距離の
伝播について説明したが、黒地から白地への伝播も行う
ことができる。さらに上記実施例では、濃度レベルが２
値の場合について扱ったが、多値の濃度レベルを持つ図
形に適用することもでき、例えば六角格子や三角格子等
正方格子以外の座標系にも適用できる。
伝播について説明したが、黒地から白地への伝播も行う
ことができる。さらに上記実施例では、濃度レベルが２
値の場合について扱ったが、多値の濃度レベルを持つ図
形に適用することもでき、例えば六角格子や三角格子等
正方格子以外の座標系にも適用できる。
以上説明したように、この発明に係るパターン距離変換
装置は、距離を表わすスカラー値をベクトル値に分解し
、記憶する手段と、評価はスカラー値で行いながら伝播
はベクトル値で行う演算手段とからなり、格子面の持つ
伝播経路に左右されることなくユークリッド距離と正確
に一致する距離伝播を行うようにしたので、二次元図形
に対する異方性のない距離変換が可能となる。また、各
点で単に距離のスカラー値が求められるばかりではなく
、その点がどの点に一番近いかという成分情報も得られ
るという効果がある。さらにこれらの効果な有すること
により、より広い範囲への距離変換技術への応用が期待
できるというすぐれた効果も有する。
装置は、距離を表わすスカラー値をベクトル値に分解し
、記憶する手段と、評価はスカラー値で行いながら伝播
はベクトル値で行う演算手段とからなり、格子面の持つ
伝播経路に左右されることなくユークリッド距離と正確
に一致する距離伝播を行うようにしたので、二次元図形
に対する異方性のない距離変換が可能となる。また、各
点で単に距離のスカラー値が求められるばかりではなく
、その点がどの点に一番近いかという成分情報も得られ
るという効果がある。さらにこれらの効果な有すること
により、より広い範囲への距離変換技術への応用が期待
できるというすぐれた効果も有する。
第１図は近傍点への方向ベクトルの定義と、正方格子座
標系を説明するための図、第２図（ａ）。 （ｂ）は従来の４近傍距離を示す図、第３図（ａ）。 （ｂ）は従来の８近傍距離を示す図、第４図（ａ）。 （ｂ）はこの発明に係るユークリッド距離を示す図で、
各図（ａ）は中央の１点のみに白点がある場合、各図（
ｂ）は円の外側が白点の場合を示す図、第５図は中央制
御装置ＣＰＵと各Ｃｅ１ｌ との配線図、第６図は各
Ｃｅｌｌと近傍Ｃｅ１ｌとの配線および接続用レジスタ
を示す図、第７図はＣｅ１ｌ のブロック回路図である
。 図中、１は中央制御装置、２〜１７はＣｅ１ｌである。 第１図 第２図 （ａ） 第３図 （ａ）
標系を説明するための図、第２図（ａ）。 （ｂ）は従来の４近傍距離を示す図、第３図（ａ）。 （ｂ）は従来の８近傍距離を示す図、第４図（ａ）。 （ｂ）はこの発明に係るユークリッド距離を示す図で、
各図（ａ）は中央の１点のみに白点がある場合、各図（
ｂ）は円の外側が白点の場合を示す図、第５図は中央制
御装置ＣＰＵと各Ｃｅ１ｌ との配線図、第６図は各
Ｃｅｌｌと近傍Ｃｅ１ｌとの配線および接続用レジスタ
を示す図、第７図はＣｅ１ｌ のブロック回路図である
。 図中、１は中央制御装置、２〜１７はＣｅ１ｌである。 第１図 第２図 （ａ） 第３図 （ａ）
Claims (1)
- パターン距離変換装置において、距離を表わすスカラー
値をベクトル値忙分解し記憶する手段と、評価はスカラ
ー値で行いながら伝播はベクトル値で行う演算手段とか
らなり、格子面の持つ伝播経路に左右されることなくユ
ークリッド距離と正確に一致する距離伝播を行うことを
特徴とするパターン距離変換装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP57163389A JPS5952362A (ja) | 1982-09-20 | 1982-09-20 | パタ−ン距離変換装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP57163389A JPS5952362A (ja) | 1982-09-20 | 1982-09-20 | パタ−ン距離変換装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS5952362A true JPS5952362A (ja) | 1984-03-26 |
| JPH0127464B2 JPH0127464B2 (ja) | 1989-05-29 |
Family
ID=15772953
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP57163389A Granted JPS5952362A (ja) | 1982-09-20 | 1982-09-20 | パタ−ン距離変換装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS5952362A (ja) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH10118367A (ja) * | 1996-10-18 | 1998-05-12 | Brother Ind Ltd | 画像データ処理装置及び刺繍データ処理装置 |
-
1982
- 1982-09-20 JP JP57163389A patent/JPS5952362A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPH0127464B2 (ja) | 1989-05-29 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4541114A (en) | Routing techniques using serial neighborhood image analyzing system | |
| JPH0233191B2 (ja) | ||
| US4845767A (en) | Image signal processor | |
| JPH055142B2 (ja) | ||
| Dubitzki et al. | Parallel region property computation by active quadtree networks | |
| US4799154A (en) | Array processor apparatus | |
| Mudge et al. | Cellular image processing techniques for VLSI circuit layout validation and routing | |
| JPH0127464B2 (ja) | ||
| Duff | Parallel processing techniques | |
| Ronse | A strong chord property for 4-connected convex digital sets | |
| Molitor | Constrained via minimization for systolic arrays | |
| EP0418949B1 (en) | Method of detecting an amplitude transient in a field of elements having a multivalent amplitude distribution, device suitable for performing the method, and video system including the device | |
| JP2557856B2 (ja) | Ｃａｄシステム | |
| CA1040315A (en) | Binary image processor | |
| CN117609672A (zh) | 一种离散数据点拟合曲线改进方法及系统 | |
| KR100236033B1 (ko) | 움직임 추정기의 절대 에러값 가산 방법 및 가산기 구조 | |
| SU1628069A1 (ru) | Устройство дл выделени пр молинейных элементов контура изображени | |
| RU1800462C (ru) | Устройство дл выполнени матричных операций | |
| Cortelazzo | The use of multiple criterion optimization in digital filter design | |
| JPH02126374A (ja) | 繰り返し型ラベリング方式 | |
| JPS59792A (ja) | 図形認識方式およびその装置 | |
| JPS6275884A (ja) | 文書パタ−ンの記述方法 | |
| Bazelow et al. | On the microprocessor solution of ordinary differential equations using integer arithmetic | |
| JPS59139475A (ja) | プリント板パタ−ン図の自動入力システムにおけるノイズ除去方式 | |
| ZHAO et al. | Properties of Circuits in a W-Graph |