JPH03179575A - 境界追跡装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明は、２値画像における対象物と背景との境界を追
跡する装置に関する。

［従来の技術］ 従来の境界追跡の方式としては、特開昭５７−１５７３
６９号公報に記載のものが知られている。

この方式は、第１２図に示すように、境界線上の現在の
境界点Ｐ、の一つ前の境界点Ｐ、−１から見た現在の境
界点ｐ、の存在方向〔以下、この方向を「入力方向」と
いう。図示例においては、矢印（イ〉で示す方向が境界
点Ｐ、への入力方向である。］を基準として、現在の境
界点Ｐｔを取り囲む８近傍画素の状態を一定方向に順に
〔図中矢印（ロ）方向に■→■の順に〕検索し、初めて
見付けたＮＪの点（対称物を示す点であり、この例では
■の点）を次の境界点Ｐｉ□とし、現在の境界点Ｐ、か
ら見た次の境界点ＰＩｈ、の存在方向〔以下、この方向
を「出力方向」という。図示例においては、矢印（ハ）
で示す方向が出力方向である。〕を決める。そして、こ
の操作を繰り返して、Ｐ　ｊ−１、Ｐ　ｌ　、Ｐ　ｔ＊
＋　、・・・・・・の座標点を順次境界線上の点として
収集する、というものである。

なお、８近傍画素を順に検索する際の開始点は、人力方
向の右または左１３５度後方の画素である。

第１２図の例、及び後述する本発明の実施例においては
、すべて入力方向を基準にして左１３５度後方の画素を
検索開始点とし、右回りに検索するものとする。そして
、その検索の順位を■〜■の符号で示す。したがって、
第１２図の例のように■の点で初めてｒＮが見付かった
場合は、その後の順位の■や■等の点で「１」が存在し
たとしても、優先順位の小さい■の点が境界線上の点と
なる。

［発明が解決しようとする課題］ ところで、上記従来の境界追跡方式においては、境界点
を次々に進めていくたびに、その都度、境界点を取り囲
む８近傍画素の情報を１つずつ調べている。したがって
、特に図形が複雑で大きい場合には、処理時間が非常に
多くかかるという問題がある。

本発明は、上記事情を考慮し、処理の高速化を図ること
のできる境界追跡装置を提供することを目的とする。

［課題を解決するための手段］ 本発明の境界追跡装置の処理上の特徴を先に述べると、
この装置においては、予め各画素毎の近傍情報を蓄積し
、ある境界線上の画素（境界点）に注目したらすぐその
注目画素の近傍の情報を取り出せるようにしておく。そ
して、現在注目している境界点への入力方向が決定した
ら、蓄積した近傍情報群の中からその境界点の近傍の情
報を取り出し、その近傍の情報と上記の入力方向の情報
とに基づいて、即座に出力方向を演算して出力する。そ
してこれを繰り返すことにより、境界点の座標を収集す
る。

このような処理を実行するために、本発明の装置は、（
ａ）２値画像の各画素を取り囲む近傍画素の状態をひと
まとまりの近傍情報として、それぞれ注目している画素
に対応したアドレスに記憶する近傍情報メモリと、（ｂ
）この近傍情報メモリから読み出した現在の境界点の近
傍情報と、現在の境界点の一つ前の境界点から見た現在
の境界点の存在方向（入力方向）の情報と、の２つの情
報を入力することにより、現在の境界点から見た次の境
界点の存在方向く出力方向）を出力する演算回路と、を
備えたことを特徴としている。

ここで、上記演算回路としては、例えば入力方向の情報
と、近傍画素の情報とをアドレス人力としたＲＯＭを用
いることができる。その場合は、ＲＯＭのアドレス毎に
出力方向のパターンを記憶させておけばよい。

［作用］ 上記装置の作用を述べる。

今、処理対象領域の各画素の近傍画素の状態は、予め近
傍情報メモリに収集蓄積されているものとする。そして
現在、境界追跡の過程で、境界線上のある点Ｐ、に注目
しているとする。そうするとこの時点で、前回の処理の
結果、現在の境界点への入力方向が与えられる。すなわ
ち、現在注目している境界点Ｐ１の一つ前の境界点Ｐ、
−１から見た現在の境界点の存在方向（前回の出力方向
）が与えられる。そして、この入力方向の情報は演算回
路に入力される。同時に、現在の境界点の近傍情報が近
傍情報メモリから読み出されて、この情報も演算回路に
入力される。

そうすると、入力された２つの情報に基づいて、１対１
の関係で出力方向が演算結果として出てくる。そして、
これを順次繰り返すことにより、出力方向の情報から境
界点の座標が収集される。

［実施例コ 以下、本発明の一実施例を図面を参照しながら説明する
。

第１図は本発明の一実施例の境界追跡装置を含む画像処
理システムのブロック図である。符号１で示すものは、
マイクロコンピュータを中心にして構成された画像処理
制御装置であり、データ入出力端子Ｉ１０．制御信号出
力端子Ｓ、クロック端子ＣＬＫを少なくとも有している
。この画像処理制御装置１の中には、２値画像データを
記憶する２値画像メモリが含まれている。なお、この実
施例における画像は、２５６×２５６の画素行列により
構成されている。

また、符号２で示すものは、各画素毎の近傍画素の情報
を格納するための近傍情報メモリである。

このメモリ２には、境界追跡処理を行う前の段階におい
て、近傍情報が収集蓄積されている。

ここで、近傍情報の格納のされ方を具体的に述べると、
第２図に斜線で示す第１行、第１列の注目画素（＋、ｊ
〉の８近傍画素ｎ０〜ｎ７の２値データが、ひとまとま
りの２進数として、第３図に示すように、近傍情報メモ
リ２の（ｉｘ２５６＋ｊ）番地のアドレスに記憶されて
いる。この場合のアドレス（ｉＸ２５６＋ｊ）は、注目
画素の座標（ｉ、ｊ）に対応している。なお、この明細
書においては、近傍情報メモリ２に格納されている上記
のひとまとまりの近傍情報を、「近傍情報ベクトル」と
呼ぶ。

上記近傍情報メモリ１は、ＲＡＭで構成されている。こ
のＲＡＭのアドレス入力は、第１図に示すように１６ビ
ツトあり、上位アドレス（８ビ・ノド）と下位アドレス
（８ビツト）に分割され、それぞれ独立にカウントアツ
プ、カウントダウンができるようになっている。そして
、上位アドレスが「行」に対応した行アドレス、下位ア
ドレスが「列」に対応した列アドレスになっている。

上位アドレス入力端子（Ａ１．〜Ａ１１）には、行アド
レスを指定するための８ビツトの行カウンタ３が接続さ
れている。また、下位アドレス入力端子（Ａ、〜ＡＯ）
には、列アドレスを指定するための８ビツトの列カウン
タ４が接続されている。両カウンタ３．４は、アップ／
ダウンカウンタであり、デコーダ５からの制御信号によ
り、画像処理制御装置１からのクロック入力に応じてカ
ウントアツプまたはカウントダウンする。

また、両カウンタ３．４は、画像処理制御装置１の制御
信号端子Ｓによってロード入力が加えられることにより
、画像処理制御装置ｌの指定する初期値を、データバス
１００を介して′初期セ・ノドすることができる。すな
わち、両カウンタ３．４は、データ端子に入力される各
８ビ・ｙトの初期アドレスデータを取り込むことができ
る。

また、本システムは、上記の要素の他に、３ビツトのレ
ジスタ６、及び演算回路としての機能をｌすＲＯＭ７を
有する。レジスタ６は、後述する入力方向の情報を一時
的に格納してお（もので、任意のデータのセットが可能
であり、またクリアモ可能である。このレジスタ６のデ
ータ入力端子はＲＯＭ７のデータ出力端子に接続されて
いる。

また、こ′のレジスタ６の３ビツトの出力端子は、ＲＯ
Ｍ７の上位アドレス入力端子に接続されている。ＲＯＭ
７のアドレスは　Ａ　、。〜Ａ０の１１ピツトあり、上
位の３ビツト（ＡＩ０〜Ａ、）がレジスタ６に接続され
、下位の８ビ・ノド（Ａ７〜Ａ、）が近傍情報メモリ（
ＲＡＭ）２のデータ出力端子Ｄ７〜Ｄ、に１対ｌの関係
で接続されている。

この場合のＲＯＭ７は、上述した入力方向の情報と近傍
の情報との２つの情報をアドレス情報として、「出力方
向のデータ」を出力する機能を有している。以下、この
ＲＯＭ７の詳細を説明する。

まず、このＲＯＭ　７を作る際に設けた約束事から述べ
る。

（ｉ）「方向」について。

本システムにおいては、人力あるいは出力の８つの方向
を、第４図に示すように「０」〜「７」の８つの数字で
コード化している。図中の０内の数字は、上記「０」〜
「７」の数字を２進化したコードであり、ＲＯＭ７では
このコードを採用している。そして、ＲＯＭ７の上位ア
ドレスは、上記の８つの入力方向に対応させて（０００
）〜（１１１）まで設定されている。

（ｉｉ）アドレスとメモリ内容の関係について。

本発明は、近傍画素の内容をひとつひとつ検索するもの
ではないが、次のような検索の原理を応用している。

近傍画素を検索する際には、入力方向によって画素の検
索順位が決定する。第５図（ア）〜（り）は、人力方向
別の近傍画素の検索順位を示している。例えば、入力方
向がｒｏ　（０００）］であれば、第５図（ア）で示す
■→■の順に８つの近傍画素を検索する。そして、初め
てｒＮが見付かった点が次の境界点となり、出力方向が
決まる。

ここで、注意すべきことは、入力方向によって、８つの
近傍画素の検索の順位が異なることである。

例えば、入力方向がｒｏ　（０００）Ｊの場合は、図（
ア）に示すように、近傍画素をｎ０→ｎｌ−１−ｎ。

→ｎ４→ｎ７→ｎ６→ｎ、→ｎ３の順に検索する。また
、人力方向がｒ７（１１１）Ｊの場合は、近傍画素をｎ
ｌ＋ｎ、→ｎ４→ｎ７→ｎ、→ｎ、→ｎ３→ｎ。

の順に検索する。その他は、第５図に示す通りである。

次に、入力方向毎に、初めてＩｌｌが見付かった位置に
応じて出力方向がどのようになるのかを調べてみると、
第６図、第７図に例示するような対応表が得られる。第
６図は入力方向が「０（０００）」の場合、第７図は入
力方向がｒ７（１１１）」の場合である。

これらの対応表に示されるように、人力方向が決定した
場合、「８近傍画素のデータ」と、「「１」か初めて見
付かった位置」と、「出力方向」と、は相互に対応した
関係にある。すなわち、近傍画素のデータにより、どの
位置で初めて「１」が見付かったかがわかり、それによ
り出力方向が決定するのである。

そこで、このＲＯＭ７においては、「入力方向」を上位
アドレス、「近傍情報ベクトル」を下位アドレスにそれ
ぞれ設定し、各アドレス毎に出力方向のパターンを格納
している。そうすることにより、人力方向と近傍情報と
がわかれば、それらのデータをアドレスに入力すること
により、該アドレスに格納されている出力方向のデータ
が出力されることになる。

ちなみに、ＲＯＭ７の内容は、第８図に示すようになっ
ている。ＲＯＭ７の上位アドレスは「人力方向」に対応
し、下位アドレスは「近傍情報ベクトル」に対応してい
る。そして、「１」が見付かった位置に対応させて、Ｒ
ＯＭ７の内容である「出力方向」のデータが格納されて
いる。

ここで、ＲＯＭ７のアドレスは、入力方向と近傍情報ベ
クトルのすべての組み合わせに対応している。そして、
各アドレスに出力方向のデータが記憶されている。なお
、第６図、第７図において、「アドレスの数」という項
目は、例えば■の位置で「１」が初めて見付かる場合の
、近傍情報ベクトルの種類が２７個あることを示してい
る。そして、図表中のｒｘＪ印は、ｌでも０でもいずれ
であってもよいことを示している。

以上のように、このＲＯＭ７には、予め出力方向ツバタ
ーンが格納されており、入力方向のデータと近傍情報ベ
クトルをアドレスに入力すれば、自動的にＲＯＭ７は、
出力方向のデータ（３ビツトの方向２進コード）を出力
する。

そして、このＲＯＭ７の出力はデコーダ５に入力されて
、カウンタ３．４への入力信号にデコードされる。その
デコード内容は、第９図に示す通りである。例えば、出
力方向がｒＯ（０００）Ｊであれば、列カウンタ４のみ
１カウントアツプする。出力方向がｒｌ（００１）Ｊで
あれば、行カウンタ３をｌカウントダウンし、列カウン
タ４を１カウントアツプする。出力方向がｒ７（１１１
）Ｊであれば、行カウンタ３、列カウンタ４を共に１ず
つカウントアツプする。

そして、カウンタ３．４で新たに指定された次の境界点
のアドレス（座標データ）は、データバス１００を介し
て画像処理制御装置ｌに送られるようになっている。

次に、本画像処理システムの処理動作を順を追って説明
する。

（１）本システムにおいては、まず画像処理制御装置ｌ
により、予め画面上の対象領域の各画素毎の近傍情報を
収集し、収集したデータをデータバスｌＯＯを通して近
傍情報メモリ２に書き込む。

（２）画像処理制御装置１において、公知の処理手法を
用いて、境界線上の追跡開始点を求める。

（３）画像処理制御装置１により、データバス１００上
に追跡開始点の座標データを乗せ、同時に行カウンタ３
、列カウンタ４にロード入力を加えることにより、両カ
ウンタ３．４に、追跡開始点のアドレスデータ（行アド
レス及び列アドレス）を取り込む。同時にレジスタ６に
クリアをかけ、レジスタ６の内容をｒｏｏｏＪとする。

つまり、「人力方向」の初期値を無条件にｒＯＪにする
のである。

（４）これより、境界追跡処理が始まる。

（４−１）行カウンタ３、及び列カウンタ４によりアド
レスが指定されている状態で、近傍情報メモリ２に読み
出し信号を与えることにより、近傍情報メモリ２から現
在の境界点の近傍情報ベクトル（現在の境界点の近傍情
報）が出力され、この出力データはＲＯＭ７の下位アド
レスに人力される。同時に、レジスタ６から出力される
「入力方向のデータ」がＲＯＭ７の上位アドレスに入力
される。そして、これら２つの情報により、ＲＯＭ７の
アドレスが決まる。

（４−２）この状態で、ＲＯＭ７から、指定されたアド
レスに格納された内容、すなわち「出力方向のデータ」
が出力される。

（４−３）この「出力方向のデータ」は、レジスタ６に
クロック信号を与えることでレジスタ６に格納される。

レジスタ６に格納されたデータは、次の処理時の入力方
向データとして用いられるものである。また、ＲＯＭ７
からの出力データはデコーダ５に入力され、ここでデコ
ードされ、デコードされた信号により行カウンタ３、列
カウンタの内容が更新される。

（４−４）新たに更新された行カウンタ３、列カウンタ
４の内容は、データバスＩ００を通って画像処理制御装
置ｌ側に送られ、新たに探索した境界点座標として収集
される。

（４−５）また、両カウンタ３．４の内容は、近傍情報
メモリ２のアドレスに入力される。この状態で、近傍情
報メモリ２に読みだし信号を加えることにより、近傍情
報メモリ２は近傍情報ベクトルをＲＯＭ７の下位アドレ
スに入力する。

（４−６）また、レジスタ６は（４−３）で示すように
、前回の「出力方向のデータ」を保持しており、このデ
ータを次の境界点の「入力方向のデータ」としてＲＯＭ
７の上位アドレスに入力する。ＲＯＭ７は、上記２つの
情報によって決まるアドレスに従って、「出力方向のデ
ータ」を出力する。

（４−７）以下、これを繰り返すことにより境界点の座
標が、カウンタ３．４からの出力信号として画像処理制
御装置１内の所定のメモリに収集され、このことで境界
追跡が行われる。そして、最初の境界点に達したら処理
を終える。

次に、第１０図の具体例を用いて上記の処理内容をより
詳しく説明する。

ここで、第１０図に示す図形の境界線上の追跡開始点（
第１行、第３列の画素）−をＰ。、そしてそれに続く境
界線上の点をＰｌ、Ｐ２、Ｐｌ、Ｐ４、Ｐ５とすると、
各点Ｐ。−Ｐ、の近傍情報ベクトルは、近傍情報メモリ
２に第１１図に示すように格納されている。

この例において、点Ｐ。から順次境界点を追跡していく
過程を述べると次のようになる。

（１）まず、追跡開始点Ｐ０の行アドレスｉ、列アドレ
スｊを、それぞれ行カウンタ３、列カウンタ４に初期設
定する。そうすると、近傍情報メモリ２からＰｏのアド
レス（ｉｘ２５６＋ｊ）に対応した近傍情報ベクトル（
００００１１１１）が読み出され、このデータがＲＯＭ
７の下位アドレスにセットされる８また。無条件にレジ
スタ６に初期入力方向をｒｏ　（０００）Ｊと初期設定
すると、この値がＲＯＭ７の上位アドレスにセットされ
る。

入力方向が（ＯＯＯ）であり、近傍情報ベクトルが（０
０００１１１１）であるということは、第８図に示すよ
うに、ＲＯＭ　７の（Ａ）で示すアドレスに相当する。

したがって、■の位置に初めて「１」が現れたことにな
る。ＲＯＭ７には、この入力方向（０００）、近傍情報
ベクトル（００００１１１１）をアドレスとする位置に
、■の出力方向、すなわち（ＯＯＯ）が予め格納されて
いる。したがって、ＲＯＭ７からは、出力方向データ（
ＯＯＯ）が出力される。

（２）ＲＯＭ７から出力された出力方向データ（０００
）は、レジスタ６に取り込まれ、ＲＯＭ７の上位アドレ
ス（次の境界点Ｐ、の入力方向）となる。また、出力方
向データ（０００）はデコーダ５に取り込まれ、第９図
に示すように、列カウンタを１インクリメントする。こ
の操作により、自白ン々Ｑ　　ＡＬ７１千十山々ｌ十　
−一！１つハマＶ＋。

スの１Ｘ２５６＋（ｊ＋１）となり、図において点Ｐ、
を指すことになる。こうして、点Ｐ、の座標のデータが
画像処理制御装置Ｉに送られる。

（３）次に、現在の境界点をＰ、として（１）と同様の
操作が行われる。カウンタ３．４によす点Ｐ、のアドレ
スが指定されており、近傍情報メモリ２のアドレス１ｘ
２５６＋　（ｊ＋１）から近傍情報ベクトル（０００１
０１１１）が読み出されて、そのデータがＲＯＭ７の下
位アドレスにセットされる。また、ＲＯＭ７の上位アド
レスには、レジスタ６により（０００）がセットされる
。

入力方向（ＯＯＯ）であり、近傍情報ベクトルが（００
０１０１１１）であるということは、第８図に示すよう
に、ＲＯＭ７の（Ｂ）で示すアドレスに相当する。した
がって、■の位置に初めて「１」が現れたことになる。

ＲＯＭ７には、この入力方向（０００）、近傍情報ベク
トル（０００１０１１１）をアドレスとする位置に、■
の出力方向、すなわちｒ７（１１１）Ｊが予め格納され
ている。したがって、ＲＯＭ７からは、出力方向のデー
タ（１１１ンが出力される。

（４）上記（２）と同様に、ＲＯＭ７から出力された出
力方向データ（１１１）は、レジスタ６に取り込まれ、
ＲＯＭ７の上位アドレス（次の境界点Ｐｔの人力方向）
となる。また、出力方向データ（１１１）はデコーダ５
に取り込まれ、第９図に示すように、行カウンタ３及び
列カウンタ４の内容を共に１インクリメントする。この
操作により、カウンタ３．４の示す内容は、近傍情報メ
モリ２のアドレスの（ｉ＋１）ｘ２５６＋　（ｊ＋２）
となり、図において点Ｐ、を指すことになる。

こうして、点Ｐ、・の座標データが画像処理制御装置１
に送られる。

（５）上記（１）と同様に、近傍情報メモリ２のアドレ
ス（ｉ＋１）Ｘ２５６＋　（ｊ＋２）から近傍情報ベク
トル（１００１１１１１）が読み出され、ＲＯＭ７の下
位アドレスにセットされる。

また、レジスタ６によりＲＯＭ７の上位アドレスには（
１１１）がセットされる。

入力方向が（１１１）であり、近傍情報ベクトルが（１
００１１１１１）であるということは、第８図に示すよ
うにＲＯＭ７の（Ｃ）で示すアドレスに相当する。した
がって、■の位置に初めて「１」が現れたことになる。

ＲＯＭ７には、この人力方向（１１１）、近傍情報ベク
トル（１００１１１１１）をアドレスとする位置に、■
の出力方向、即ち（０００）が予め格納されている。し
たがって、ＲＯＭ７からは出力方向データ（０００）が
出力される。

（６）以上のような操作を繰り返して新しい境界点を探
索していき、始めの境界点に戻ったら処理を終了する。

以上説明したように、本画像処理システムによれば、予
め収集しておいた近傍情報を使って能率良く境界追跡処
理を行うことができる。

なお、上記実施例においては、近傍画素を検索する方向
を右回りに設定しているが、左回りに設定してもよいこ
とは勿論である。

また、上記実施例においては、出力方向を演算＋２開す
欠１−１プＤ八Ｌｆｔ−内ｈ＾磯八亡−；１Ｊ、よζＲ
ＯＭ以外の演算手段を用いてもよい。

［発明の効果］ 本発明の境界追跡装置によれば、前回の境界点から現在
の境界点への入力の方向と現在の境界点の近傍画素の状
態とに基づいて、演算回路が出力方向を算出するので、
境界点を進めるたびにその都度、近傍画素を１つずつ調
べるといった面倒な処理を行う必要がなくなり、その結
果、境界追跡の処理時間を短縮して処理の高速化を図る
ことができる。

【図面の簡単な説明】

第１図は本発明の一実施例を含む画像処理システムのブ
ロック図、第２図はある画素（斜線部）を取り囲む近傍
画素（ｎｏ−”−＝ｎ？）の説明図、第３図は近傍情報
メモリ２内への近傍情報の格納のされ方を示す図、第４
図は本画像処理システムにおいて決められている方向符
号を示す図である。 また、第５図〜第７図はＲＯＭ（演算回路）７の内容を
説明するために供する図表であって、第位を示す図、第
６図及び第７図はある入力方向における近傍画素データ
と出力方向の対応図である。 また、第８図はＲＯＭ７の内容の一部を示す図、第９図
はデコーダ５による出力方向データのデコード内容を示
す図、第１０図は具体的な境界追跡例の説明図、第１１
図は同側における近傍情報メモリの内容を示す図である
。 さらに、第１２図は従来の境界追跡の方式を説明するた
めの図である。 １・・・・・・画像処理制御装置、２・・・・・・近傍
情報メモリ（ＲＡＭ）　、３・・・・・・行カウンタ、
４・・・・・・列カウンタ、５・・・・・・デコーダ、
６・・・・・・レジスタ、７・・・・・・ＲＯＭ（演算
回路）。

Claims (1)

1. 【特許請求の範囲】 ２値画像における対象物と背景との境界を追跡する装置
   において、 上記２値画像の各画素を取り囲む近傍画素の状態をひと
   まとまりの近傍情報として、それぞれ注目している画素
   に対応したアドレスに記憶する近傍情報メモリと、 この近傍情報メモリから読み出した現在の境界点の近傍
   情報と、現在の境界点の一つ前の境界点から見た現在の
   境界点の存在方向の情報と、を入力することにより、現
   在の境界点から見た次の境界点の存在方向を出力する演
   算回路と、 を備えたことを特徴とする境界追跡装置。