JPH06259548A

JPH06259548A - 実時間連結性アルゴリズムシステム

Info

Publication number: JPH06259548A
Application number: JP5226657A
Authority: JP
Inventors: Jr Robert C Gardemal; ロバート・シー・ガーデマル・ジュニア; Kurt J Otto; クルト・ジェイ・オットー; Gregory A Roberts; グレゴリー・エイ・ロバーツ
Original assignee: Loral Aerospace Corp; Lockheed Martin Aerospace Corp
Current assignee: Lockheed Martin Tactical Systems Inc
Priority date: 1992-08-20
Filing date: 1993-08-20
Publication date: 1994-09-16
Anticipated expiration: 2010-12-18
Also published as: EP0585035A3; TW234168B; DE69327756T2; US5384860A; JPH07118009B2; AU662832B2; AU4475193A; EP0585035A2; IL106708A; DE69327756D1; EP0585035B1

Abstract

(57)【要約】【目的】連結性アルゴリズムの実施装置を提供する。【構成】ディジタル化像内のピクセルの空間的関係を
表わす複数の逐次遅延ディジタル化ビデオ信号を発生す
る逐次遅延線アレイを備えており、これらの信号が、ス
レッショルド回路により発生される遅延された主題ピク
セルコントラスト信号とともに大きさコンパレータアレ
イに結合され、コンパレータアレイにビデオ信号と主題
ピクセルコントラスト信号との比較を表わす複数の結果
信号を生じさせる。結果信号は閉鎖路チェック回路に結
合され、この回路で、閉鎖路上の各ピクセルが取り囲ま
れた主題ピクセルセルから予定された強度レベルだけ強
度が異なる、主題ピクセルの回りのすべての予定された
状態の閉鎖路を同時に識別する。【効果】連結性アルゴリズムが、像内の各ピクセル上
で実時間で効率的に実施できる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、連結性アルゴリズムの
実施に関し、特定すると連結性アルゴリズムを像の各ピ
クセル上で実時間で効率的に実施せしめる新規なハード
ウェアアーキテクチャに関する。

【０００２】

【従来技術】地形のような不均一なシーンのフォワード
ルッキングインフラレッド(FLIR)作像においては、背景
の温度よりも相当高いまたは低い温度を有する点ターゲ
ットが、FLIR作像において従来使用されているターゲッ
ト検出アルゴリズムにより検出されないことがしばしば
あることが従来の出願に論述されている。従来のターゲ
ット検出アルゴリズムはまた、多くの背景クラッター点
をターゲットとして過って記録することもある。この種
のターゲット検出アルゴリズムは、前縁−後縁検出およ
び最小二乗(LMS) 濾波を含む。一次元LMS フィルタは、
前縁−後縁検出の場合にそうであるように、背景対象の
縁部で過ったターゲット指示として生じ、二つの直行一
次元LMS フィルタを使用してさえ、なお角部上で過った
ターゲット指示を生ずることがあり得る。明瞭な表示の
ためにターゲット点を隔絶するためには、関係する対象
の空間的延長および空間的接続を実時間で決定すること
が必要であることが分かった。これは難しい計算術であ
る。

【０００３】本発明者等は、この文献または類似の問題
を一般的に処理する数例の文献を承知している。これら
の文献として、下記のものがある。

【０００４】米国特許第4,005,415 号。この発明は、レ
ーダの視野内にある全ターゲットに関して検出、分類お
よび追跡機能を遂行する、信号処理回路およびプログラ
ムされた汎用ディジタルコンピュータより成る自動化レ
ーダデータ処理システムを開示している。この信号処理
回路は、生のレーダビデオ信号を受信し、ターゲットの
すぐ近傍におけるノイズ、クラッターまたは電子的対策
信号からスレッショルドを誘導し、信号対雑音比および
大きさに関して検出基準を満足させる到来信号のみを通
す適応ビデオプロセッサを具備する。信号処理回路は、
コンピュータ装置において誘導され記憶されるターゲッ
トトラックデータと対話でき、適応ビデオプロセッサに
より任意のターゲットに加えられる特定の信号処理が、
そのターゲットの追跡状態にしたがって最適化されるよ
うになされている。

【０００５】米国特許第4,233,387 号。この文献は、二
次元量子化画像を試験し、任意の対象が設定された最小
の距離より近いか否かを決定する装置を開示している。
量子化された画像は、対象の存在または不存在に応答し
て０または１が割り当てられた増分領域を有する。相互
に結合された論理的セルので、画像内の別個の対象の存
在を識別する。配列の寸法は、対象間の容認し得る最小
の距離に対応する。上述の装置は、基本的ディジタル論
理要素のみを含み、画像情報をコンピュータプログラム
を使用しないで処理する。

【０００６】米国特許第4,489,388 号は、ターゲットに
対して発生されレジスタに記憶される角度、距離および
ターゲット方位角の大きさデータを選択するためのプロ
ットジェネレータを開示している。ジェネレータは、セ
ンサ信号データの受信でデータを発生するためのビデオ
プロセッサを備える。この文献は、レーダが覆う範囲を
多数の距離−方位角帯域に分割し、角帯域に対して処理
されるべき標準的プロット数を設定し、かつ各アンテナ
の回転ごとに最大数のプロットが中央プロセッサのによ
り処理されることを許容することに基礎を置く装置を開
示している。しかして、この標準的プロット数は、ター
ゲットアプローチルートに関する帯域の位置に依存す
る。

【０００７】米国特許第4,593,406 号。この文献に開示
される発明は、形状および概略位置が既知である根本的
または基本的対象の中心を確かめるためのコンピュータ
化方法および点位置づけシステムを含む。この技術は、
対象の像を得、試験的中心を選択し、中心に対して予定
された関係を有する点の軌跡を生成することを含む。こ
のような点の軌跡は円を含もう。各四分円内の対象に重
なる点の数が得られ、四分円当りのこれらの点の計数値
が比較される。この比較から、試験的中心の相対位置を
調節するために、エラー信号が提供される。これは、試
験的中心が予め定められた精度範囲内において幾何的中
心に重なるまで反復される。

【０００８】米国特許第4,685,143 号。この文献は、自
動像処理および認識方式において縁部マップの構成およ
び分析により像を認識することを開示している。通常多
量の情報を記憶しておく必要性がある欠点を克服するた
め、この文献に記載される技術は、縁部マップから縁部
スペクトルを計算する。縁部スペクトルは、それが誘導
される縁部マップよりもよりもさらに凝縮された形式で
有用な情報を含んでおり、そしてこれが、数種の特徴検
出器の任意のもので処理され、例えば、縁部マップが像
の識別において有用な相互に直行する縁部または他の構
造的詳細を含んでいるかどうかを決定する。

【０００９】米国特許第4,736,439 号。この文献は、局
部的平均に基づく適応量子化を使用する像の変換または
予確認処理を開示する。この文献に開示される像与処理
技術は、中央の濾波による像の世処理を含んでおり、そ
してこの処理にあっては、ラスタ走査から得られるよう
な、マトリクスにより表されるディジタル化像の１また
は複数列のピクセルの中央値が、個々のピクセル値から
減算され、低および高周波数ノイズが濾波される。

【００１０】米国特許第4,742,557 号。この文献は、走
査プロセスにおいてピックアップされた望ましくない背
景情報およびノイズを含む走査データフィールドから関
係のある特性情報を抽出するための方法およびシステム
を開示する。この文献の装置は、グレイレベル比較のみ
ならず、地勢的特徴（特性ピクセルの幾何的分布）の比
較を使用し、各個々のチェックのためスレッショルドを
適応的に調節する。しかして、このスレッショルドは、
特性情報の考察からカットオフを決定する。

【００１１】上述の文献に開示され利用される技術と比
較して、前記特許出願に開示される発明は連結性アルゴ
リズムを利用するが、この発明にあっては、作像電子回
路で、潜在的ターゲット対象の重心の回りに閉鎖路を形
成するピクセルのピクセル強度を試験する。試験回路
は、ピクセルが閉鎖路の一部であるようにするため、ピ
クセル強度が重心の強度から予定された態様で異なるこ
とを要求する。もしも、閉鎖路のいずれのピクセルも重
心から予定された距離を越えないうちにこのような閉鎖
路を描くことができれば、潜在的ターゲット対象は、真
のターゲットとして識別され、真のターゲットとして表
示できる。

【００１２】

【発明の課題】従来、連結性アルゴリズムは、予め濾波
されたピクセルサブセットを汎用プロセッサで処理する
ことによってのみ実時間ビデオデータ上に遂行できた。
この手法は、かなりの量のハードウェアとソフトウェア
を必要とした。プレフィルタを通過しなかったターゲッ
トは検出できなかった。本発明のハードウェアアーキテ
クチャおよび実施例は、これらの問題を排除し、基本的
連結性アルゴリズムを向上させる二三の特徴を有する。

【００１３】従来技術の上述の要因および条件の特徴を
考慮に入れて、本発明の主たる目的は、新規にして改良
された連結性アルゴリズムシステム提供することであ
る。

【００１４】本発明の特定の目的は、連結性アルゴリズ
ムを像の各ピクセル上で実時間で効率的に実施せしめる
連結性アルゴリズムシステムを提供することである。

【００１５】本発明の特定の目的は、予め濾波されたピ
クセルサブセットを汎用プロセッサで処理することな
く、連結性アルゴリズムを実時間ビデオデータ上で遂行
せしめる連結性アルゴリズムシステムを提供することで
ある。

【００１６】本発明のさらに他の目的は、FLIRポッドビ
デオ作像におけるターゲットの自動検出のため基本的タ
ーゲット検出／クラッター拒絶を行なうことによって、
高性能軍用航空機の空対空および空対地の役割をともに
向上せしめる連結性アルゴリズムシステムを提供するこ
とである。

【００１７】本発明のさらに特定の目的は、汎用プロセ
ッサの手法で実時間ビデオ作像において各ピクセルを試
験するに必要とされるであろうよりもずっと少ないハー
ドウェアとソフトウェアしか必要としない連結性アルゴ
リズムシステムを提供することである。

【００１８】

【課題を解決するための手段】本発明の１具体例におい
ては、ラスタ走査ディジタル化ターゲット内の主題のピ
クセルを取り囲む閉鎖路上の各ピクセルが予定された強
度レベルだけ主題のピクセルの強度から強度が異なる場
合、連結性アルゴリズムが、この主題のピクセルが関係
のあるピクセルであり潜在的ターゲットの一部であるこ
とを宣言する。

【００１９】本システムは、時間信号、スレッショルド
信号およびディジタル化ビデオ信号入力を備えており、
時間信号およびディジタル化ビデオ信号入力に結合され
て、ディジタル化像におけるピクセルの空間的関係を表
わす複数の逐次遅延ディジタル化ビデオ信号を発生する
ための逐次遅延線アレイを備える。本発明はまた、スレ
ッショルド信号入力および複数の逐次遅延ディジタル化
ビデオ信号の中央の信号に結合され、遅延された主題ピ
クセルセルコントラスト信号を発生するためのスレッシ
ョルド回路を備える。時間信号入力、スレッショルド回
路手段、ディジタル化ビデオ信号入力および逐次遅延線
アレイ手段には、主題ピクセルコントラスト信号に関す
るビデオ信号の比較を表わす複数の結果信号を同時に発
生するための大きさコンパレータアレイが結合されてい
る。本発明はさらに、時間信号入力およびコンパレータ
アレイに結合され、主題ピクセルの回りのすべての予定
された状態の閉鎖路を同時に識別するための閉鎖路チェ
ック回路を備える。時間信号入力および閉鎖路チェック
回路にはターゲット位置ジェネレータが結合されてお
り、上述の予定された状態を有する閉鎖路信号と関連す
るターゲット位置信号を発生する。本発明はさらに、タ
ーゲット位置ジェネレータに結合されたターゲットメモ
リ手段を備えており、これがターゲット位置信号に応答
して、関係するピクセルの位置を表わす連結性出力信号
を発生する。

【００２０】

【実施例】本発明の種々の目的および利点は、図面を参
照して行なった以下の詳細な説明と関連して行った以下
の説明から容易に明らかとなろう。

【００２１】上述のように、連結性アルゴリズムは、基
本的に、主題ピクセルの回りの任意の閉鎖路（任意の形
状の）が見出され、閉鎖路上の各ピクセルが主題のピク
セルよりも所定のスレッショルド値だけ暗ければ、ピク
セルが潜在的正のコントラストターゲットの一部である
と説明する。同様に、負のコントラストターゲットは、
閉鎖炉内のすべてのピクセルよりも所定のスレッショル
ドだけ暗くなければならない。ターゲットピクセルを検
出する最高の可能性をもたせるためには、選ばれた閉鎖
路は、予定の強度レベルだけ相違する強度より成るピク
セルの回りを蛇行することができねばならない。閉鎖路
の形状は、固定でも任意でもよい。本発明の第１の実施
例は、固定形状の閉鎖路での実施である。

【００２２】図面特に図１を参照すると、ラスタ走査デ
ィジタル化像またはピクセルアレイ１１が示されている
が、このピクセルアレイにおいては、５ピクセル×５ピ
クセルより成る方形路１３が定められており、方形路１
３の中心に主題ピクセル１５が存在する。例えば、４×
９ピクセルの路が選ばれたなら、主題のピクセルは、1/
2 ピクセルだけ垂直にオフセットされたであろう。もし
も、主題のピクセル１５が、閉鎖路１３上の全ピクセル
よりも強度が所与のスレッショルドだけ大きければ、主
題のピクセル１５は、潜在ターゲットの一部であると宣
言され得よう。図１のピクセルアレイ１１を観察するこ
とによって、多くの固定形路が閉鎖路１３の５×５の方
形に類似の態様で形成され得ることが分かろう。これら
の閉鎖路の一つが連結性アルゴリズムの条件を満足する
かどうかを知る鍵は、後述のように、これらのピクセル
がスレッショルド偏倚された主題ピクセルに較べて大き
さが如何であるかということである。

【００２３】多くの可能な閉鎖路を実時間でチェックす
るために、図１のアレイ１１内のすべてのピクセルが、
主題のピクセル１５と１ピクセルクロックまたは周期で
比較されることが必要である。これは、本発明のこの実
施例においては、ディジタル化ビデオの８本の線を遅延
し、それを現在の線とともに大きさコンパレータアレイ
に送ることにより遂行される。例えば、図２において例
示される連結性アルゴリズムシステムにおいて、システ
ムは、時間信号線２５に結合された時間信号入力２３、
関連するビデオ信号線２９をもつディジタル化ビデオ信
号入力２７、スレッショルド信号入力３１、逐次遅延線
アレイ３３、および大きさコンパレータアレイ３５を含
む。

【００２４】入力２７に結合される信号は、ラスタ走査
誘導実時間ディジタル化像ピクセル信号列であり、入力
３１に結合されるスレッショルド信号は、信号対雑音比
を最大化し、クラッタの拒絶を改善するように適合され
た、および／またはターゲットサイズや像認識のために
選択された、経験的に誘導された最適化ｄｃ，階段状、
または滑らかな波形信号とし得る。これは、例えば、パ
イロットにより所望の感度を提供するように手動的に変
えることができる。

【００２５】大きさコンパレータのＮ本の線がある場
合、遅延線アレイ３３は、各々逐次接続されたＮ−１本
の従来形式の遅延線要素３７を含む。すなわち、かかる
１要素の出力端子３９は、次の逐次の要素３７の入力端
子４１に接続されている。かくして、５×５の方形配列
の場合、Ｎ＝４であり、４の遅延線要素がある。４×９
の方形の場合、Ｎ＝９であり、８の遅延線要素があるこ
とに成る。

【００２６】主題ピクセル１５は、中心（Ｎ／２）の
「主題ピクセル」線４３からサンプルされ、コントラス
ト回路５１に結合される。コントラスト回路５１は加算
／減算要素５３およびコントラスト回路遅延要素５５を
含む。また、コントラスト回路５１には、スレッショル
ド信号入力３１から結合された予定された大きさの上述
のスレッショルド信号が入力される。主題ピクセル強度
が閉鎖路上の全ピクセルより大きい正のコントラスト状
況の場合、スレッショルド信号はサンプルされた信号か
ら減算され、遅延要素５５により遅延される。このコン
トラスト信号は、回路５１の出力５９からスレッショル
ド偏倚主題線５７に供給される。主題ピクセル１５がサ
ンプルアレイの中心にあるとき、サンプルされた信号は
主題ピクセルと一致するように遅延される。主題ピクセ
ルが閉鎖路上のピクセルより大きさが小さいとき（負コ
ントラスト）、スレッショルド信号は、加算／減算要素
５３において主題ピクセルの大きさに加算される。

【００２７】この実施例においては、図３に詳細に示さ
れるように、コンパレータアレイ３５は、図１のピクセ
ルアレイ１１内のピクセル行Ａ−Ｉおよびピクセル列１
−１５に対応して、１５の従来形式のレジスタ６１の５
行より成る。ここでは、簡単にするため、１行のレジス
タのみを例示してある。図３の上部に見られるように、
各行の各レジスタ６１の出力６３は、バケツリレー態様
でその行の次のレジスタ６１に供給される。各レジスタ
の出力はまた、レジスタ出力線６３を介して、関連する
従来形式の大きさコンパレータ要素６５に結合される。
しかして、該コンパレータ要素は、その関連するレジス
タ出力を線５７上の主題ピクセルのスレッショルド偏倚
信号と比較する。全コンパレータの結果は、比較出力線
６９上において比較結果信号６７として同時に得られ
る。

【００２８】図２に示されかつ図４に詳細に例示される
ように、線６９上を搬送される結果信号６７は、ＡＮＤ
ゲート７１アレイ（一つのみを示してある）に結合され
る。アレイ７１の各ＡＮＤゲートは、各々異なる閉鎖方
形路を定義する異なる一組の比較アレイ要素から結果信
号を受信する。換言すると、各ＡＮＤゲート２３に対す
る入力は、特定の閉鎖路をチェックするに必要とされる
全比較結果である。５×５の閉鎖路（または窓）の場
合、閉鎖路１３内の全部で１６のピクセル（暗ピクセ
ル）の比較結果がＡＮＤゲートアレイ７１の従来形式の
ＡＮＤゲート７３に結合される。すべての入力がディジ
タル１であると、主題ピクセル１５は、閉鎖路１３の全
ピクセルより少なくともスレッショルド偏倚比較信号レ
ベル分だけ異なり、主題ピクセルは、潜在ターゲットの
一部であると考えることができる。これは、例えば、タ
ーゲット位置ジェネレータ８１（図２および図５参照）
内の従来形式のＯＲゲートの関連する入力に結合される
ＡＮＤゲートアレイ出力線７５上にディジタル１とし
て、窓状態信号上に指示されることになる。

【００２９】上述のように、例えば、図１のピクセルア
レイで定義され得る多くの固定閉鎖路が存在する。この
とき、各定義される閉鎖路がＡＮＤゲートアレイ７３の
異なるものに結合されれば、多くの閉鎖路は同時的にチ
ェックできることは明らかであるはずである。全ＡＮＤ
ゲートの出力すなわち窓状態信号は、ついで従来形式の
ＯＲゲートとで一緒にＯＲ結合され、主題ピクセル１５
が閉鎖路のいずれかにあったかを決定できる。このよう
なピクセルが検出されれば、像内のその位置が、従来形
式の行および列カウンタから、ターゲット位置ジェネレ
ータ出力線９３を介して、斯界において周知の形式のタ
ーゲットデータメモリモジュール９１に記憶され得る。
ついで、メモリモジュール９１は、記憶されたターゲッ
トメモリ出力線９５を介して記憶されたターゲットデー
タを従来形式のシステムプロセッサ（図示せず）に結合
する。

【００３０】ターゲット位置ジェネレータ８１の一部お
よび関連する要素が図５に示されている。ジェネレータ
８１は、Ｙの入力のＯＲゲートを具備しており、その入
力は、ＡＮＤ窓アレイ７１内の各窓からＡＮＤゲート結
果出力線７５に結合されている。もしもいずれかの窓結
果信号が１であると、ＯＲゲート出力線８５は信号をＡ
ＮＤゲート８７の入力に供給する。しかして、該ＡＮＤ
ゲートの他方の入力は、線９３上にメモリ書込み出力を
供給するため、線２５を介してクロック時間信号に結合
されている。この主題ピクセル位置は、位置カウンタ出
力線１０３を介して、システム２１内の従来形式のピク
セル位置カウンタ回路１０１によりターゲットデータメ
モリ９１に供給される。

【００３１】図６に例示される本発明の他の実施例を参
照する。ここでは、本発明は、商業的に入手できるマル
チプル、遅延線集積回路(IC)チップ２０１を使用して実
施され、これが７×５の比較アレイとしての５個の棚卸
しの現場プログラム可能なゲートアレイ２２１(EPGA)す
なわち論理セルアレイに適当に結合される。論理セルア
レイ２２１は、３１窓のＡＮＤアレイである単一のEPGA
に結合され、該EPGAは、ターゲット位置ジェネレータ２
６１として使用される単一のFPGAに結合される。ターゲ
ット位置ジェネレータ２６１の出力は、従来形式の３２
ビットVME バス２８３接続された出力を有する従来形式
のターゲットデータFIFO281 に供給される。

【００３２】本発明の好ましい実施例においては、さら
に他の単一のEPGAが遅延中心（主題ピクセルの）線２９
３と、スレッショルド入力線３１’とに結合されてお
り、上述の第１の実施例のコントラスト回路５１に動作
が一部類似のスレッショルド減算器／VME バスコンパチ
ブルインターフェースとして動作する。この構造は、16
MHz ピクセルレートで実施され、十分に試験され、優れ
たターゲット検出器であることが分かった。全装置は１
枚のVME バスコンパチブルボードに適合した。第２のこ
の種のボードを第１のVME ボードと一緒に使用して、正
および負のコントラストターゲットを判別できる。すな
わち、第２のボードは、スレッショルド加算器／VME イ
ンターフェースとして単一のEPGAを利用する。

【００３３】本発明の他の実施例が図７に示してある。
図６の実施例と同様に、この実施例は１対の従来形式の
遅延線集積回路３０１を合体しているが、この集積回路
チップの出力は、１３×１９の比較アレイ部分３２３と
４８窓のＡＮＤアレイ部分３２５を含む注文製のマスク
プログラムドゲートアレイ３２１に結合される。このゲ
ートアレイ３２１からの出力は、外部EPGAターゲット位
置ジェネレータ３４１からの出力とともに、商業的に入
手し得るターゲットデータFIFO３６１に結合される。し
かして、該ターゲットデータFIFO３６１は標準ＶＭＥに
出力される。このゲートアレイは、制御ピン（図示せ
ず）を高くまたは低く繋ぐことで正または負コントラス
トターゲットのいずれかを検出するゲートアレイを構成
する特徴を含む。かくして、同じ像内の両形式のターゲ
ットを検出するために、この種の二つのゲートアレイが
必要となる。このゲートアレイの実施例は、20MHz ピク
セルレートで試験して成功を納めた。

【００３４】上述の固定閉鎖路の実施例は、強度でな
く、特定のターゲットの特徴を検出基準に包含すること
を可能にする。例えば、小閉鎖路または窓を選択するこ
とによって、検出プロセスにおいて大ターゲットを排除
し得る。他方、小さい窓を捨て大きい窓を通るようにピ
クセルに要求すると、大きなターゲットについて選択で
きる。ターゲットが通過する最小の窓を決定すると、タ
ーゲットの大きさの決定を補助できる。窓形状はまた、
所望のターゲットの判別を補助するのにも使用できる。
例えば、長い狭い窓は、横向き配向を有する解像可能な
爆撃機について判別できる。

【００３５】本発明の他の側面として、上述の固定路技
術の代わりに任意路の使用も包含される。小ピクセルア
レイには、全可能路を試験するために固定路が使用でき
る。各可能路には、ＡＮＤゲートが単に割り当てられ
る。この手法は、アレイの大きさが増すにつれ、急に過
度に多数のＡＮＤゲートを招来する。

【００３６】図８，図９および図１０は、主題ピクセル
を取り巻く閉鎖路上の各ピクセルが主題ピクセルの強度
から予定されたスレッショルドレベルだけ強度が異なる
任意路が存在するか否かを見いだすハードウェア技術を
示している。この手法は、図２に示されるシステムのＡ
ＮＤゲートアレイ７１の代わりに任意路セルアレイ７
１’を使用することしか必要としない。

【００３７】任意路の実施例７１’は５×５のピクセル
アレイに対して記述されているが、この方式は任意寸法
のアレイに拡張できることを理解された。また、図８に
おいて、簡単にする目的で、後述されるセル構造体は、
対応するピクセルと同じ位置を占めることに留意された
い。

【００３８】この実施例では、図８において円４０５と
して示される標準「セル」回路は、アレイのスタート点
セルを除くすべてに割り当てられる。各標準セル回路４
０５は、入力４０９および出力４１１を有する少なくと
も一つのＡＮＤゲート４０７と、入力４１５およびＡＮ
Ｄゲート入力４０９の一つに結合された出力４１７を有
するＯＲゲート４１３とを具備する。ＡＮＤゲート入力
４０９の他方は、対応する大きさコンパレータ出力線６
９からの到来する関連する比較結果信号６７に結合され
る。

【００３９】任意の標準セル回路４０５に対するＯＲゲ
ート入力４１５の数は、それに結合される近隣のセル回
路ＡＮＤゲート出力の数に対応する。例えば、標準セル
４０５Ａ（図９に代表される）は、近傍のセル４０５Ｂ
および４０５Ｃからの入力を有し、近隣のセル４０５Ｄ
への単一の出力を有する。他の標準セルは、１または複
数の近隣セル入力および１または複数の近隣セル出力を
有してよく、そして図９に概略線で示されるように、追
加のＡＮＤゲートおよびＯＲゲートを必要とするかもし
れない。

【００４０】図８に見られるように、主題ピクセル４２
１はアレイ４０１の中心にあり、「スタート点」セルと
して知られるものがダイアモンド形状セル４２３により
表されている。しかして、このダイアモンド形状セル
は、図１０に回路でより詳細に例示されている。この図
で、セル４２３は入力５１３と、ＡＮＤゲート５１９の
２入力５１７の一つに接続された出力５１５とを有する
ＯＲゲート５１１を具備するものとして示されている。
近傍の標準セル４０５からの出力は、ＯＲゲート入力５
１３に結合されているが、非常に重要なことは、このス
タート点セルと関連する大きさコンパレータ出力線６９
からの比較結果信号６９が、ＡＮＤゲート入力５１９の
他方に結合され、そしてこのセルから近隣の標準セルの
入力に結合されるということである。このように、スタ
ート点セルのセル間状態出力は、その比較結果信号であ
る。また、標準セル回路と異なり、ゲート５１９の出力
５２５に得られるＡＮＤゲート出力は、線７５を経て、
ターゲット位置ジェネレータ８１の関連する入力のみに
結合される。

【００４１】各ピクセルクロックにて、スタート点セル
の状態は、接続ネットに伝搬する。正コントラスト状態
においては、もしもスタート点セル４２３が、主題ピク
セルのレベルよりもスレッショルドレベルだけ低いセル
間出力レベル（その到来比較結果信号６７）を有すれ
ば、該セルは、ディジタル１をそれに接続された１また
は複数のセルに通す。そうでなければ、該セルはディジ
タル０を通す。１が標準セルに通され、そのセルの対応
するピクセルが主題ピクセルよりもスレッショルドレベ
ルだけ低いレベルを有すれば、そのときだけ、そのセル
はディジタル１をその出力に接続されるセルに通す。や
はり、この論理に対する機構は図９に示されている。

【００４２】閉鎖路がスタート点セル４２３を含むアレ
イに存在すれば（すなわち、主題ピクセル４１５の強度
レベルが路内の全ピクセルのそれよりもスレッショルド
レベルだけ大きい）、スタート点セルからの１が主題ピ
クセル４２１の回りを完全に伝搬し、スタート点セルの
入力５１３に戻る。この点にて、スタート点セルはその
出力７５からディジタル１を生じ、主題ピクセル４２１
は潜在ターゲットの一部であると宣言でき、固定ピクセ
ル路の実施例との関連において説明したように、像内の
このピクセル位置がターゲットデータメモリモジュール
９１に記憶される。

【００４３】任意のスタート点セルと関連してセル間接
続のネットが存在する。このネットは、スタート点セル
で始まる任意の閉鎖路を見出すに必要とされるアレイ内
の最小数のセル間接続を表わす。例えば方形ピクセルア
レイにＮ列のピクセルが存在する場合、主題ピクセルの
回りの閉鎖路を識別するために実施されるべき(N-1)/2
のネットが存在することになる。かくして、例えば、図
８に示される５×５のアレイの場合、必要とされる(5-
1)2すなわち２のネットが存在し、セル４０５Ｅ（破線
ダイヤモンド）が第２のネットに対するスタート点セル
となろう。この場合、セル４２３は、標準セル（破線
円）として実施されることになろう。

【００４４】ノイズピクセルの回りの閉鎖路を蛇行する
ことがあり得るから、任意路技術はノイズの多い背景に
おいて非常に低コントラストターゲットを見出すのにも
っとも適合している。この感度の犠牲は、信号を多レベ
ルの論理要素中を伝搬させねばならないということであ
る。このため、実際のシステムを実施するに際して高速
度のゲートアレイの使用が強制される。他方、固定路方
法に対しては、より少ないレベルの論理要素しか必要と
されず、このため緩速で、低廉化の手段の使用が許容さ
れる。

【００４５】上述の説明から、ラスタ走査ディジタル化
像内の主題のピクセルを取り囲む閉鎖路上の各ピクセル
が、主題のピクセルの強度から予定された強度レベル異
なっている場合、この主題ピクセルが、潜在ターゲット
の一部であるがゆえに関係するピクセルであることを宣
言する新規にして改良された実時間連結性アルゴリズム
システムが開示されたことが理解されるはずである。

【００４６】上述の実施例は、本発明の諸原理の応用を
表わす多くの特定の実施例のあるものを例示しているに
過ぎないことを理解されたい。技術に精通したものであ
れば、本発明の技術思想から逸脱することなく種々の他
の変形を容易に思いつくことができよう。

【図面の簡単な説明】

【図１】ピクセルアレイを表わすマトリクスを例示する
線図である。

【図２】本発明に従う連結性アルゴリズムシステムの概
略ブロック図である。

【図３】図２に例示されるコンパレータアレイの一部を
示す概略線図である。

【図４】図２のＡＮＤゲートの一部を表わす部分的に絵
図で描いた概略線図である。

【図５】図２のターゲット位置ジェネレータの一部を示
す概略線図である。

【図６】本発明の他の実施例である現場でプログラム可
能なゲートアレイ装置のブロック図である。

【図７】本発明の他の実施例であるマスクプログラムド
ゲートアレイ装置を表わす。

【図８】本発明の他の実施例である任意路技術で利用さ
れ得る５×５のセルアレイを例示する線図である。

【図９】本発明の任意路での実施例において標準セルを
構成するためのハードウェア技術を例示する概略線図で
ある。

【図１０】本発明の任意路での実施例においてスタート
点セルを構成するためのハードウェア技術を例示する概
略線図である。

【符号の説明】

１１ラスタ走査ディジタル化像またはピクセルアレイ１３方形路１５主題ピクセル２３時間信号入力２５時間信号線２７ディジタル化ビデオ信号入力２９ビデオ信号線３１スレッショルド信号入力３３逐次遅延線アレイ３５大きさコンパレータアレイ３７遅延線アレイ４３主題ピクセル線５１コントラスト回路５３加算器／減算器要素５５遅延要素６１レジスタ６７比較結果信号７１ＡＮＤゲートアレイ７３ＡＮＤゲート８１ターゲット位置ジェネレータ９１ターゲットデータメモリモジュール

─────────────────────────────────────────────────────

【手続補正書】

【提出日】平成５年１１月２４日

【手続補正１】

【補正対象書類名】明細書

【補正対象項目名】特許請求の範囲

【補正方法】変更

【補正内容】

【特許請求の範囲】

【請求項１】ラスタ走査ディジタル化像内の主題ピク
セルを取り囲む閉鎖路上の各ピクセルが主題ピクセルの
強度から予定さえれた強度レベルだけ強度が異なる場
合、該主題ピクセルが潜在ターゲットの一部であること
を宣言する実時間連結性アルゴリズムシステムにおい
て、時間信号入力、スレッショルド信号入力およびディジタ
ル化ビデオ信号入力と、該時間信号入力およびディジタル化ビデオ信号入力に結
合され、ディジタル化像内のピクセルの空間的関係を表
わす複数の逐次遅延されたディジタル化ビデオ信号を発
生するための逐次遅延線アレイ手段と、前記スレッショルド信号入力、および前記の複数の逐次
遅延ディジタル化ビデオ信号の中央の信号に結合され、
遅延された主題ピクセルコントラスト信号を発生するた
めのコントラスト回路と、前記時間信号入力、前記コントラスト回路、前記ディジ
タル化ビデオ信号入力および前記逐次遅延線アレイ手段
に結合され、異なる閉鎖路に対して、前記ビデオ信号と
前記主題ピクセルコントラスト信号との比較を各々表わ
す複数の結果信号を同時に発生するための大きさコンパ
レータアレイ手段と、前記時間信号入力および前記コンパレータアレイ手段に
結合され、前記閉鎖路上の各ピクセルが、取り囲まれた
主題ピクセルから予定された強度レベルだけ強度が異な
る、前記主題ピクセルの回りのすべての予定された状態
の閉鎖路を同時に識別するための閉鎖路チェック回路
と、前記時間信号入力および前記閉鎖路チェック回路に結合
され、前記の予定された状態を有する閉鎖路信号のみと
関連するターゲット位置信号を発生するためのターゲッ
ト位置ジェネレータと、該ターゲット位置ジェネレータに結合され、関係するピ
クセルの位置を表わす連結性出力信号を発生するターゲ
ットデータメモリ手段とを備えることを特徴とする実時
間連結性アルゴリズムシステム。

───────────────────────────────────────────────────── フロントページの続き (72)発明者グレゴリー・エイ・ロバーツアメリカ合衆国カリフォルニア州コスタメサ、グルノーブル・レイン353

Claims

【特許請求の範囲】

【請求項１】ラスタ走査ディジタル化像内の主題ピクセ
ルを取り囲む閉鎖路上の各ピクセルが主題ピクセルの強
度から予定さえれた強度レベルだけ強度が異なる場合、
該主題ピクセルが潜在ターゲットの一部であることを宣
言する実時間連結性アルゴリズムシステムにおいて、時間信号入力、スレッショルド信号入力およびディジタ
ル化ビデオ信号入力と、該時間信号入力およびディジタル化ビデオ信号入力に結
合され、ディジタル化像内のピクセルの空間的関係を表
わす複数の逐次遅延されたディジタル化ビデオ信号を発
生するための逐次遅延線アレイ手段と、前記スレッショルド信号入力、および前記の複数の逐次
遅延ディジタル化ビデオ信号の中央の信号に結合され、
遅延された主題ピクセルコントラスト信号を発生するた
めのコントラスト回路と、前記時間信号入力、前記コントラスト回路、前記ディジ
タル化ビデオ信号入力および前記逐次遅延線アレイ手段
に結合され、異なる閉鎖路に対して、前記ビデオ信号と
前記主題ピクセルコントラスト信号との比較を各々表わ
す複数の結果信号を同時に発生するための大きさコンパ
レータアレイ手段と、前記時間信号入力および前記コンパレータアレイ手段に
結合され、前記閉鎖路上の各ピクセルが、取り囲まれた
主題ピクセルから予定された強度レベルだけ強度が異な
る、前記主題ピクセルの回りのすべての予定された状態
の閉鎖路を同時に識別するための閉鎖路チェック回路
と、前記時間信号入力および前記閉鎖路チェック回路に結合
され、前記の予定された状態を有する閉鎖路信号のみと
関連するターゲット位置信号を発生するためのターゲッ
ト位置ジェネレータと、該ターゲット位置ジェネレータに結合され、関係するピ
クセルの位置を表わす連結性出力信号を発生するターゲ
ットデータメモリ手段とを備えることを特徴とする実時
間連結性アルゴリズムシステム。
【請求項２】前記逐次遅延線アレイ手段が、逐次接続
遅延線要素を備え、該遅延線要素の第１のものの入力が
前記ディジタル化ビデオ信号入力に結合され、前記各遅
延線要素の出力が前記大きさコンパレータアレイ手段の
関連する出力に結合されている請求項１記載の実時間連
結性アルゴリズムシステム。
【請求項３】前記大きさコンパレータ手段がＮ本の線
を備え、前記逐次遅延線アレイ手段がN-1 本の遅延線要
素を備える請求項２記載の実時間連結性アルゴリズムシ
ステム。
【請求項４】前記逐次遅延線アレイ手段がN/2 主題ピ
クセル出力線を備える請求項３記載の実時間連結性アル
ゴリズムシステム。
【請求項５】前記コントラスト回路が、加算器／減算
器要素とコントラスト回路遅延要素と備えており、前記
加算器／減算器要素の入力が、前記スレッショルド信号
入力と、前記複数の逐次遅延ディジタル化ビデオ信号の
前記中央の信号とに結合され、前記コントラスト回路遅
延要素の出力が、前記大きさコンパレータアレイ手段の
入力に結合されている請求項１記載の実時間連結性アル
ゴリズムシステム。
【請求項６】前記大きさコンパレータアレイ手段が、
各行に複数の行レジスタを含む複数の行を備え、前記複
数の行の各々における前記レジスタの各々の出力が、前
記レジスタの逐次の次のものの入力に結合され、前記大
きさコンパレータアレイ手段が複数の大きさコンパレー
タ要素を備え、前記各コンパレータ要素が、前記レジス
タの異なるものの前記出力と、前記の遅延された主題ピ
クセルのコントラスト信号とに結合され、前記コンパレ
ータ要素が前記複数の結果信号を発生する出力を有して
いる請求項１記載の実時間連結性アルゴリズムシステ
ム。
【請求項７】前記閉鎖路チェック回路が、前記主題ピ
クセルの回りのすべての予定された状態の閉鎖方形路を
同時に識別するための閉鎖路アレイ手段を備えている請
求項１記載の実時間連結性アルゴリズムシステム。
【請求項８】前記方形窓アレイ手段が、一組の入力、
および出力を各々有するＡＮＤゲートアレイを備え、複
数組の前記入力の各々が、異なる一組の前記比較要素の
関連するものに結合され、異なる複数組の前記比較要素
の各々が前記の予定された状態の閉鎖方形路の異なる一
つを定める請求項７記載の実時間連結性アルゴリズムシ
ステム。
【請求項９】前記閉鎖路チェック回路が、前記主題ピ
クセルの回りのすべての予定された状態の任意路を同時
に識別するための任意路アレイ手段を備えている請求項
１記載の実時間連結性アルゴリズムシステム。
【請求項１０】前記任意路アレイ手段が、スタート点
セルと前記主題ピクセルの回りに配された近隣標準セル
とを含み、ディジタル「１」が、前記スタート点セルか
ら前記標準セルの前記主題ピクセルの回りのものを通
り、前記スタート点に戻るときのみ、ディジタル「１」
が前記セルの外に出力され、前記標準セルのみが、関連
する結果信号がディジタル１であるとき、前記「１」を
伝搬する請求項９記載の実時間連結性アルゴリズムシス
テム。
【請求項１１】前記各標準セルが、２入力と近隣セル
出力を有する少なくとも一つのＡＮＤゲートと、少なく
とも一つの近傍セル入力および前記ＡＮＤゲート入力の
一つに結合された出力を有する少なくとも一つのＯＲゲ
ートを備え、前記入力の他方が、前記標準セルにより代
表されるピクセル位置に対応する前記結果信号の一つに
結合される請求項１０記載の実時間連結性アルゴリズム
システム。
【請求項１２】前記スタート点セルが２入力および前
記ターゲット位置ジェネレータの関連する入力に結合さ
れた出力を有するＡＮＤゲートを備え、かつ近隣セル入
力、および前記２ＡＮＤゲート入力の一つに結合された
出力を有するＯＲゲートを備え、前記入力の他方が、前
記スタート点セルにより代表されるピクセル位置に対応
する前記結果信号に結合され、前記スタート点セルがさ
らに、それに対する前記結果信号入力を構成する近隣セ
ル出力を備える請求項１０記載の実時間連結性アルゴリ
ズムシステム。
【請求項１３】前記スタート点セルと関連するセル間
連結ネットが存在し、該ネットが、スタート点セルを含
む閉鎖セル路を限定するに必要とされるピクセルアレイ
内の最小数のセル間結合を表わす請求項１０記載の実時
間連結性アルゴリズムシステム。
【請求項１４】最大の閉鎖セル路が、Ｎ列を有する方
形ピクセルアレイにより定められ、前記任意路アレイ手
段内に(N-1)/2 の前記ネットが存在する請求項１３記載
の実時間連結性アルゴリズムシステム。