JPS6190276A - 距離変換回路 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、ディジタル画像処理における距離変換回路に
関づる。

（従来の技術） ディジタル画像処理の分野においては、画像内の各画素
につきその背景画面からの距離を求めること（距離変換
）が行われる。第１１図は距臼１変換画像例を示す歯で
ある。画像中の数字は周囲の背隈データＯからの距離を
示している。図のＪ８合４と３の点にイれぞれ頂点があ
り、この点の位置と、距な［データはこの画像を特徴づ
ける有用な情報となっている。従来、このような距離変
換は画像データが記憶された画像メモリとコンピュータ
を用い、画像メモリから読出しだ画像データにソフトウ
ェア上の演算処理を行い、その演算結果を再び画像メモ
リに出込むという操作を？１っていた。

（発明が解決しようと７−る問題点） 前）ホしたように、従来の距ｒＪＩ変換は各画Ｊ２、ご
とにソフトウエア上の１ｇ１ｔ　Ｏ処理を行つＣいるＩ
、＝め、処理に極めて長時間を苅していた。

本発明はこのよう４１点に鑑み−（なされたしのであっ
て、その目的は第１に演蓮処理をハードで構成すること
によりディジタル画１象処理にお（プる距離変換演算を
ビデオレートのら々倍のオーダ０行うことのできる高速
の距離変換回路を実現Ｊることにあり、第２に距離変換
動作に加えて中み付けされた距離変換動作も行える距１
イ１変挽回路を実現することにあり、第３にｙ１離変換
動作に加えて画；′に演算も行える距離変換回路を実現
することにあり、第４に距離変換動作に加えて画像の骨
１１９点ｂ　ｖ＞出することができる距離変換演算を実
現ツることにある。

（問題点を解決するための手段） 前記した問題点を解決づる第１の発明は画（象データが
格納された画像メモリを４方向にラスタスキャンし、そ
れぞれの方向の場合において、ビデオクロックの前半で
読出したデータと１クロック前に画像メモリに書込まれ
たデーに定数にを加えた値とを比較し、小さい方のデー
タをビデオクロックの後半で画像メモリに書込む操作を
行うようにしたことを特徴とするものであり、第２の発
明は画像データが格納された画像メモリを４方向にラス
タスキャンし、それぞれの方向の場合において、同期ク
ロックの前半で読出したデータと１クロック前に画像メ
モリに書込まれたデータに濃淡画像の濃度値に応じた定
数にを加えた値とを比較し、小さい方のデータを同期ク
ロックの後半で画像メモリに書込む操作を行うようにし
たことを特徴とするものであり、第３の発明は画像デー
タが格納された画像メモリを４方向にラスタスキャンし
、それぞれの方向の場合において、ビデオクロックの前
半で読出したデータと１クロック前に画像メモリに占込
まれたデータに定数にを加えた値とを比較し、小さい方
のデータをビデオクロックの後半で画像メモリに占込む
操作を行うと共に、前記２つの比較データの画像ｉ１ｉ
　ｎも行うことができるように構成したことを特ｉＬ＋
とするものであり、第４の発明は画像データが格納され
た画像メモリを４方向にラスタスキ１７ンし、それぞれ
の方向の場合において、ビデオクロックの前半で読出し
たデータと１クロック前に画像メモリに書込まれたデー
タに定数にを加えた値とを比較し、小さい方のデータを
ビデＡり［コックの後半で画像メモリに書込む操作を行
うと共に、前記比較の結果を２値化データとして各方向
ごとにメモリに記憶しておき、各メモリの記憶データの
論理積をとることにより画像の骨格点も算出できるよう
に構成したことを特徴としている。

（実施例） 以下、図面を参照して本発明の実施例を詳細に説明する
。

第１図は、本発明の一実施例を承す（構成ブロック図で
ある。図において、１ｔＪ：￥：業域として１両面分の
領域の濃淡画像データが格納されている画（／１：メモ
リ、２は該画像メ七り１を４方向にラスタスキャンづる
ラスタスキ１ン回路である。４方向は、第２図に示すよ
うに右、左、下、上の４方向として定義される。ラスタ
スキャン回路２は、第２図に示すような方向にラスタス
キャンするためのアドレスを画像メモリ１に与えるよう
になっている。なお、画像メモリ１のデータの読出しと
書込みはビデ副クロック１周期の前半部と後半部を使っ
て行われる。

３は画像メモリ１から読出されたデータをビデオクロッ
クによって一時的に保持するトランスベアシン１〜ラツ
チ、４は画像メモリ１へ書込むための画像データをビデ
オクロックにより一時的に保持するレジスタ、５は該レ
ジスタ４の出力データに１を加締するインクリメンタで
ある。６はトランスペアレントラッチ３の出力Ｐとイン
クリメンタ５の出力Ｑの大小を比較するコンパレータ、
７はＰデータとＱデータを受け、コンパレータ６からの
制御信号によって何れか一方を選択してデータバスＤＢ
にのせるマルチプレクサである。該マルチプレクサ７は
、Ｐ＜ＱのときにはＰを、Ｐ２ＯのときにはＱを出力す
るようになっている。該マルチプレクサ７には、ビデオ
クロックか出力状態制御信号として人力されており、ビ
デオクロックが′Ｏ“′のとぎにイネーブル状態゛′１
°°のときにディスエーブル状態となるように構成され
ている。

インクリメンタ５としては、ＡＬＵ（算術論理演算ユニ
ット）の＋Ｍ能や、ＲＯｌｖｌまたはＲＡ　Ｍによるル
ックアップテーブル（ＬＵＴ）で実現することができ、
コンパレータ６はＡＬＵの減Ｑ成能や専用のコンパレー
タで実現することができる、また、マルチプレクサ７は
３ステート出力のマルチプレクサＩＣや、２組の３ステ
ートバツフアで実現することができ、４方向ラスタスキ
ャン回路２は左右方向と上下方向に対応する２組のアッ
プダウンカウンタとクロックの流れを切換える付加回路
を用いて実現することができる。このように構成された
回路の動作を第３図に示すタイミングチャートを参照し
ながら説明すれば、以下のどＪ３りである。

第３図において、（イ）はビデオクロックを、（ロ）は
データバスＤＢ上の入出力データＤＩ１０を、くハ）（
よＰデータの状態を、く二）はＱデータの状態をそれぞ
れ示す。以下の説明においては、第４図に示づような左
右方向への距離変換の場合を例にとって説明する。図に
おいて、（ａ＞は物体と背景画を示す図、（ｂ）は右方
向への変換を示１図、（Ｃ）は左方向への変換を示す図
である。また、横軸はＸ方向の位置を縦軸は距離を表わ
している。＜ａ）において、Ａは物体の存在領域をＢは
背景領域を示す。まｌζ、（ｂ）または（Ｃ）の下方に
矢印と共に示された記号ＰまたはＱは選択されｌζデー
タを示している。

最初、距離変換すべき物体と背景に対応して、ｌｉ！！
ｉ像メモリ１に２５５とＯをそれぞれデータとして書込
む。第４図（ａ）の場合を例にとって説明すれば、物体
存在領域Ａ内の各画素に対しては全て２５５を書込み、
背景領域Ｂ内の各画素に対しては全てＯを書込む。なお
、物体存在領域内のデータを２５５としたのは、取扱う
画像データのピッ１〜故を８ビツトとしたことに対応し
ｌζものである。次に、画像メモリ１に記憶されている
画像データを、第３図（イ）に示寸ビデＡクロックの前
半部（時刻ｔ１〜ｔ２）で続出づ。

この結果、データバスＤＢ上には、第３図（ロ）に示す
ようにアクセス時間だけ遅れて読出しデータが確立する
。確立されたデータは、時刻ｔ２におけるビデオクロッ
クの立下りでトランスペアレントラッチ３にラッチされ
る。このラッチされたデータが、１１訂述したデータＰ
となる（第３図（ハ））。

一方、前述した読出し動作を行う直前のデータバスＤＢ
上にはその前の書込み石−ドで画像メモリ１に書込まれ
ｌζデータ（直前データ）がのっている。この直前デー
タは、時刻ｔ１におけるビデオクロックの立上りでレジ
スタ４に取込まれる。

取込まれたデータは、続くインクリメンタ５に入り、該
インクリメンタで＋１される。インクリメンタ５の出力
が前述したデータＱとなる。第４図（ａ）の場合を例に
とれば図に示すようにＢ部分は背景画であるからＩ　Ｑ
　Ｉ！、この値に１を加えた値“１″がＱデータとなる
。△の部分の左端では、画像メモリ１から読出されてト
ランスペアレントラッチ３にラッチされたデータＰは、
物体の存在領域（Ａ）内のデータであるから２５５　”
　、直前のデータに１を加えたデータＱは、直前のデー
タが背景領域Ｂ内のデータであるから“０°”、これに
１を加えＩｃ値がデータＱであるからＱの値は“１″と
なる。

コンパレータ６は読出したデータＰと直前の書込みデー
タに１を加えたデータＱとを比較する。

そして、比較結果によるセレクト信号Ｓをマルチプレク
サ７に送′る。マルチプレクサ７はデータＰとデータＱ
のうち、コンパレータ６からのセレクト信ＭＳにより小
さい方のデータを出力する。第４図（ａ）の場合を例に
とるど、Ａの部分の左端ではデータＰが’２５５”、デ
ータＱが１″であるからこの場合はデータＱ（＝１＞が
セレクトされる。マルチプレクサ７でセレクトされたデ
ータ（ここではＱ）は、データバスＤＢ上に出力される
。データバスＤＢ上に出力されたデータが第３図（ロ）
に承す’　ＩＪ込みデータとなる。

このｔｌ込みデータＱは、第３図（イ）に承りように続
くビデオクロックの後半部の時刻ｔ３における立上りに
よってレジスタ４に書込まれる。一方、時刻ｔ３〜ｔ４
は、同時に画像メモリ１に対しては、読出しモードとし
て芸能し、画像メモリ１から次の番地の画像データ（こ
こで【よ２５５）が所定のアクレスＩｆｆ間経過後読出
されて、第３図（ｂ）に示すようにデータバスＤＢにの
る１、データバスＤＢ上に確立した読出しデータは、ビ
デオクロックの時刻ｔ４における立下りでトランスペア
レントラッチ３に書込まれて第３図（ハ）に示すデータ
Ｐとなって、コンパレータ６及びマルチプレクサ７に与
えられる。

一方、レジスタ４には、前述したようにその直前の書込
みデータＱ（＝１＞が洛納されその値は、続くインクリ
メンタ５で＋１されて°゛２″となる。

この“２′′になった値が第３図（ニ）に示づデータＱ
として再びコンパレータ６及びマルチプレクサ７に与え
られる。コンパレータ６はデータＰ（＝２５５＞とデー
タＱ（＝２＞を比較し、その比較の結果によりセレクト
信号Ｓをマルチプレクサ７に与える。マルチプレクサ７
は、セレクト信号Ｓによって小さい方のデータＱをセレ
クトしてデータバスＤＢにのせる。データバスＤＢ上に
確立したデータＱ（ｌ込みデータ）は時刻ｔ５における
ビデオクロックの立上りで画像メモリ１に書込まれる。

なお、マルチプレクサ７は、画像メモリ１からの続出し
データと自己の出力データ同志が直接繋がらないよう、
ビデオクロックの後半のみデータバス上に書込みデータ
を出力している。

第１図に示す回路は、データの読出し、データの比較、
データの書込みという第４図に示すような繰返しのアル
ゴリズムを１画面全体について行う。この場合において
、画面メモリ１のアドレスは４方向ラスタスキャン回路
２により、第２図に示す４方向について各方向１回ずつ
行う。方向の順序は任意であってよい。また、各走査方
向とも、走査ラインの順序は任意であってよい。例えば
、右方向の走査において、第２図では各走査ラインは上
から下へと移行しているが、逆に下から上でも或いは全
くランダムであってもかまわない。変換時間は、１方向
の画面走査に要する時間を　１／６０秒とすると、その
４倍のＬ／１５秒で仝１５向の距離変換を終了する。従
来のソフトウェア演諒による方式に比較して、極めて高
速に距離変換を行うことができる。

第５図は、距離変換アルゴリズムの適用例を示す図であ
る。（イ）は変換前の原形、（ホ）は距離変換終了後の
画象を示し、（ロ）〜（ニ）１よ変換の過程を示してい
る。（ホ）を見ると明らかなように、背景からの距離が
遠ざかるにつれて膣が大きくなり、等高検に類似の距離
変換画像が形成されていることがわかる。

第６図は、本発明の第２の実施例を示す構成ブロック図
である。図に示１”回路は、データバスを入力専用バス
ＤＢ＋　と出力専用バスＤＢ２に分８！ｔしたものであ
る。このようにすると、データバス上の読出しデータと
書込みデータの所突を避けるためのマルチプレクサ７の
出力コントロールが不要になる。

第７図は、本発明の第３の実施例を示す構成ブロック図
である。図に示す回路は、第１図のインクリメンタ５を
加算回路５′で実現し、関数が＋１だけでなく、加（１
回路５−に入力される濃淡画像データの値りにより、１
クロック前に書込まれた画像データが十にされるように
し、濃度重み付きの距離変換回路を実現したものである
。図に示す回路によれば、加算回路５−に加えられる値
には濃淡画像の濃度値に応じて変化するようになってい
る。従って、澗淡画也データが図に示すように領域によ
って１ｌｉａｒｔＫが異なっている場合でも最適な濃度
重み付きの距離変換を行うことができる。

第８図は、本発明の第４の実施例を示す構成ブロック図
である。図に示す回路は、距離変換回路を汎用の画像演
算器としても使用できるように構成したものである。図
に示す回路は、第１図に示す−コンバレータ６を算術論
理演算ユニット２１で買換し、咋術論理演算ユニット２
１にコンパレート−機能をもたせたものである。２２は
、算術論理演算ユニット２１の演算出力Ｆを受ける３ス
テートバツフ？で、その出力はマルチブレクリ′７と同
様、データバスＤＢに接続されている。このように構成
されｌζ回路の動作を説明すれば、以下のとおりである
。

先ず、図に示づ回路を距離変換回路として用いる場合は
、３ステートバツフア２２の出力をディスエーブル状態
にしておき、算術論理演算ユニット２１をコンパレータ
として用いる。データ［〕とデータＱの比較結果は、セ
レクト化ｇ　３としてマルチプレク４ｆ　７に入る。該
マルチプレクサ７は、セレクト信号Ｓを受けて、データ
ＰとデータＱの何れか一方を選択してデータバスＤＢ上
に出力する。その他の動作については、第１図に承り実
施例と同様であるので説明は省略する。

°　次に、図に示す回路を画像演算器として用いる場合
は、３スアートバツフア２２の出力をイネーブル状態に
、マルチプレクサ７の出力をディスエ′　−プル状態に
しておき、算術論理演算ユニット２１を演算器として用
いる。データＰとデータＱは、諒術論理演亦ユニット２
１に入り、該算術論理演算ユニット２１で所定の演算処
理が行われる。演算の結果は出力Ｆとして取出され、３
ステートバツフア２２を介してデータバスＤＢに出力さ
れる。

データバスＤＢ上に確立された処理画像データは、画他
メモリ１に書込まれる。、なお、３ステートバツフア２
２の出力は、画像メモリ１にｉＩ込む場合に用いる他、
曲の用途に利用できるようにバス等に出力してもよい。

第９図は、本発明の第５の実施例を示ず構成図である。

図に示す回路は、第８図に示す実施例と同様、距離変換
回路を汎用の画像演紳器としても使用できるように構成
したものである。図に示す回路は、第１図に示すマルチ
プレクサ７を論理演算−１ニツト２１で置換し、算術論
理演障ユニット２１にマルチプレクサ機能をもたせたも
のである。

２３は、コンパレータ６の出力と関数指定信号Ｆｕｎｃ
を受け、算術論理演算ユニット２１に関数セレクト信号
ＳＬＴを与える関数指定制御回路である。篩術論ｙｆ！
演算ユニット２１の出力Ｆは、３ステートバツフア２２
を介してデータバスＤ　（３に接続されている。このよ
うに構成されｌζ回路の動作を説明すれば、以下のとお
りである。

先ず、図に示９回路を距離変換回路として用いる場合は
、算術論理演算ユニット２１はｌｌｌ１故指定制御回路
２３からの関ｖｌｔ？レクトイを号ＳＬＴによりマルチ
ブレフナとして動作する。そして、算術論理演算ユニッ
ト２１は、データト）及びデータＱのうち小さい方のデ
ータをデータバスＤＢ上に出力する１、その他の動作に
ついて（よ、第１図に示す実施例と同様であるので、説
明は省略する。

次に、図に示す回路を画像演の器として用いる場合はコ
ンパレータ６の動作は無視され、関数指定制御回路２３
は関数指定信号Ｆｕｎｃを受けて、Ｃ■１理演亦ユニッ
ト２１に関数セレクト化＞５．　ＳＬＴを与える。０術
論理演等ユニット２１は、データＰ及びデータＱを入力
して、関数セレクト信号Ｓ　Ｌ−Ｔに従った所定の演算
処理を行う。演算の結果は、３ステートバツフア２２を
介してデータバスＤＢに出力される。データバスＩ）　
Ｂ上に確立された処理画像データは、画（象メモリ１に
書込まれる。

なお、第８図、第９図における実施例においては、イン
クリメンタとしてルックアップテーブル５′を用い、＋
１の加算だけではなく、定数倍、２乗、絶対（ぽ１等、
種々の゛１人力変換関数として動作させることができる
。

第１０図は、本発明の第６の実施例を示を構成ブロック
図である。図に示づ回路は、コンパレータ６の比較結果
を、別途設置〕だ２１ｉｉｊ画像メモリ３１に占込める
ようにして、距離変換された画像データから骨格点も求
めることができるようにしたものである。ここで骨格点
とは、「その点の距離変換データが、隣接する点のどの
データよりも小さくない」という条ｅトを満たす点をい
う。画像メモリは、４方向ラスタスキャン回路２（図示
せず）により４方向にスキャンされる。２圃画像メモリ
３１は、スキャン方向に対応してＢ　Ｍ　ｏから８Ｍ３
までの内分割されたメモリから構成されている。

図に示す実施例においては、インクリメンタ５（第１図
）の代わりにルックアップテーブル（１−０丁）３２を
用いている。コンパレータ６（ま、Ｐ′：Ｑのときに’
ｏ”、ｐ≧Ｑのとぎに“１″なる信号＄−を出力づる。

このように構成された回路の動作を説明すれは、以下の
とおりである。

まず、前述の操作により距離変換を行う１．この時、Ｌ
ＵＴ３２の関数は＋１９画像メモリ１はリードモディフ
ァイライト（Ｗ　Ｅ　＋ｔビデオクロックにより制御さ
れる）で動作させる。次に、ＬＵＴ３２の関数を×１１
画像メ〔す１を読出しモードに切換えて骨格点を求める
。即ら、１！）られた！［’！　Ｈｔｌｊｌ変換画像の
入った画像メ七り１を４方向にスギセンして読出し、現
在の点のデータＰと１つ前の点のデータＱをコンパレー
タ６で比較し、この比較結果（Ｏまたは１）をスキャン
方向毎に２値画象メモリＢ　Ｍ　ｏ〜Ｂ　Ｍ　３に９１
込む。そしてこの４面のデータの論理積をとり、結果が
１の点が骨格点を示すことになる。なお、このとき、マ
ルチブレフナ７はディスエーブル状態である。

また、Ｌ　Ｕ　Ｔ　３２について、関数を→−１（距離
変換時）から×１（骨格点抽出時）への切換えは、関数
テーブルの内容を書換えてもよいし、＋１用と×１用の
１３ｔｌ数を予め別のページに占込んでおいて、ページ
指定を切換えるようにしてもよい。また、ルックアップ
テーブルの代わりに＋１と×１の両方の演掠が可能なｐ
術論理演算ユニット（ＡＬＵ）を用いてもよい。図にお
いては、説明を分かりやす（するため、２値画像メモリ
３１としては４画面公示したが、順次論理積をとってそ
の結果を占込むリードモディファイライトを２１直画像
メモリ３１に対して行えば１画面分だ１プで済ませるこ
とができる。

前述の説明（特に第１図の実施例）においては、データ
Ｑとして１クロック１ｎのデータに＋１を加締してデー
タＱと覆る場合を例にとったが、本発明はこれに限る必
要はなく加算するＩｊ’ｆは任意の定数Ｒであってよい
。また、距離変換づ゛べぎ物体の数も１個である必要は
なく、任意の故であってよい。また、回路全体の同期を
とる同期クロックは、ビデオクロックに限る必要はなく
、各回路要ＺＱのデータ遅延を考慮して会適なスピード
のクロックを使用してもよい。

（発明の効果） 以上詳細に説明したように、本箱１の発明によれば距離
変換アルゴリズムを、ラスタスＷｔ−ンにＪ、る繰返し
演算に分解し、この演（πを専用のハードウェアで実現
することにより、従来コンビ１−タ（ノイマン形）で多
大の時間を要していた距離変換動作が、ビデオレート（
１／６０秒）の４倍の時間、即ら、１　、／　１５秒で
行うことができる。更に本発明によれば、第１の発明に
若干の回路を付加するだけで高速路ρＪ１変換に加えて
、１口度重み何さの距離変換や、汎用の画像演いや骨格
点の抽出等を行うことのできる距離変換回路を実現する
ことができる。

【図面の簡単な説明】

第１図は本発明の一実施例を示す］ｉ１１成ブロック図
、第２図はスキャン方向を示寸図、第３図は各部の動作
を示づタイミングチャート、第４ジ１（よ距離変換アル
ゴリズムを説明づるための図、第５図は距トミ１変換ア
ルゴリズムの適用例を示す図、第６図乃至第１０図は本
発明の他の実施例を示す図、第１１図は距離変換された
画倣例を示づ図である。 １・・・画像メモリ ２・・・４ｈ向クラスタスキ１Ｐン路 ３・・・トーランスペアレントラツチ ４・・・レジスタ　　　　　５・・・インクリメンタ５
′・・・ｊＪロｃネ回路　　　　６・・・コンパレータ
７・・・マルチプレクサ ２１・・・算トドｉ論理演算ユニット ２２・・・３ステートバツフア ２３・・・関数指定制御回路 ３１・・・２１直画像メモリ　３２・・・ＬＵＴＢ　ｌ
’ＶＩ　ｏ〜ＢＭ！・・・メモリＤＢ、ＤＢ＋　、ＤＢ
２・・・データバス篇２図 諮６回 ５′；加曽回路

Claims (4)

【特許請求の範囲】
1. （１）画像データが格納された画像メモリを４方向にラ
   スタスキャンし、それぞれの方向の場合において、同期
   クロックの前半で読出したデータと１クロック前に画像
   メモリに書込まれたデータに定数にを加えた値とを比較
   し、小さい方のデータを同期クロックの後半で画像メモ
   リに書込む操作を行うようにしたことを特徴とする距離
   変換回路。
2. （２）画像データが格納された画像メモリを４方向にラ
   スタスキャンし、それぞれの方向の場合において、同期
   クロックの前半で読出したデータと１クロック前に画像
   メモリに書込まれたデータに濃淡画像の濃度値に応じた
   定数にを加えた値とを比較し、小さい方のデータを同期
   クロックの後半で画像メモリに書込む操作を行うように
   したことを特徴とする距離変換回路。
3. （３）画像データが格納された画像メモリを４方向にラ
   スタスキャンし、それぞれの方向の場合において、同期
   クロックの前半で読出したデータと１クロック前に画像
   メモリに、書込まれたデータに定数にを加えた値とを比
   較し、小さい方のデータを同期クロックの後半で画像メ
   モリに書込む操作を行うと共に、前記２つの比較データ
   の画像演算も行うことができるように構成したことを特
   徴とする距離変換回路。
4. （４）画像データが格納された画像メモリを４方向にラ
   スタスキャンし、それぞれの方向の場合において、同期
   クロックの前半で読出したデータと１クロック前に画像
   メモリに書込まれたデータに定数にを加えた値とを比較
   し、小さい方のデータを同期クロックの後半で画像メモ
   リに書込む操作を行うと共に、前記比較の結果を２値化
   データとして各方向ごとにメモリに記憶しておき、各メ
   モリの記憶データの論理積をとることにより画像の骨格
   点も算出できるように構成したことを特徴とする距離変
   換回路。