(57)【要約】  本発明は、画像認識をリアルタイムで行うことを可能にし、かつ非常に少ない先験的情報だけで、またはそれどころか如何なる先験的情報もなしで、的確で信頼性の高い対象認識を実施することができる画像処理装置に関する。このために、計算機関によって、それぞれ２つの輪郭点の間の結合確率が、点の互いに対する間隔を考慮して確定される。更に、少なくとも１つの分類器が企図されており、この分類器は、計算された結合確率の集合から、その中の１つが事前に決定された中心の輪郭点であるところの少なくとも３つの近隣の輪郭点の間の起こりうる結合に関する少なくとも３つの結合確率を備えた部分集合を選び出し、かつそれぞれの部分集合に関し、結合が、中心点の近隣にある２つの点を結合しない限りにおいて、中心の輪郭点の近隣にあり、近隣の輪郭点への起こりうる結合を最低の結合確率で有する輪郭点を選び捨て、これに続いて、選び捨てられていない輪郭点を、中心点への残った結合を特徴づけるコネクタと共に、輪郭点リストに登録する。
2010503936.tif 000002
【特許請求の範囲】
【請求項１】
１つまたは複数の画像メモリと、ハードウェアの形での、画像データをセグメント化するための集積された機構と、同様にハードウェアの形での、輪郭点を決定および処理するための集積された機構とを備えた画像処理装置であって、その際、輪郭点を決定および処理するための前記機構が、少なくとも１つの集積されたハードウェア・ユニットを含んでおり、前記ハードウェア・ユニットが、画像メモリ内に格納されたデジタル画像データを走査し、かつ輪郭点をサブピクセル精度で確定し、かつ連続するリストデータとしてメモリ内に格納するように構成されており、かつその際、前記画像処理装置が計算ユニットを有しており、前記計算ユニットが、メモリ内に格納されたリストデータを基に、計算機関によって、それぞれ２つの輪郭点の間の結合確率を、点の互いに対する間隔を考慮して確定するように構成されており、かつその際、集積された画像処理装置内に少なくとも１つの分類器が企図されており、前記分類器が、計算された結合確率の集合から、その中の１つが事前に決定された中心の輪郭点であるところの少なくとも３つの近隣の輪郭点の間の起こりうる結合に関する少なくとも３つの結合確率を備えた部分集合を選び出し、かつそれぞれの部分集合に関し、結合が、中心点の近隣にある２つの点を結合しない限りにおいて、中心の輪郭点の近隣にあり、近隣の輪郭点への起こりうる結合を最低の結合確率で有する輪郭点を選び捨て、これに続いて、選び捨てられていない輪郭点を、中心点への残った結合を特徴づけるコネクタと共に、輪郭点リストに登録する、画像処理装置。
【請求項２】
前記分類器が、中心点の近隣にある輪郭点の集合から、それぞれ、中心の輪郭点および更なる２つの輪郭点によるトリプルに関する結合確率のトリプルを、割り当てられた結合確率で形成し、前記結合確率のうちの最低の結合確率を確定し、かつそれぞれ、中心点の近隣にあり、前記トリプル内で最低の結合確率を備えた結合が出ている輪郭点を、中心点の近隣にある輪郭点の近傍集合から選び捨てるように構成される、請求項１に記載の画像処理装置。
【請求項３】
結合確率に変調を印加するための計算機構を含んでおり、その際、前記変調が、ピクセル間隔より小さい、輪郭点のポジション変位に相当する、請求項１または２に記載の画像処理装置。
【請求項４】
計算機構によって、結合確率の計算前に、変調を印加するため、それぞれピクセル座標が変更される、請求項３に記載の画像処理装置。
【請求項５】
画像メモリ内に格納されたデジタル画像データを走査し、かつ輪郭点をサブピクセル精度で確定し、かつ連続するリストデータとしてメモリ内に格納するように構成されている集積された計算ユニットが、輪郭点のポジションのほかに少なくとも１つの更なる輪郭点属性を計算し、かつ連続するリストデータ内に保存するように構成される、請求項１乃至４のいずれか１項に記載の画像処理装置。
【請求項６】
集積された計算ユニットが、１つの輪郭点のために１つの属性ベクトルを少なくとも２４ビットの長さ、好ましくは少なくとも３６ビットの長さで生成し、かつ連続するリストデータ内に保存するように構成される、請求項１乃至５のいずれか１項に記載の画像処理装置。
【請求項７】
メモリ内に格納されたリストデータを基に、計算機関によって、それぞれ２つの輪郭点の間の結合確率を確定するように構成されている前記計算ユニットが、輪郭点の間の結合確率を、輪郭点の間隔および少なくとも１つの更なる属性に基づいて算定するように構成される、請求項１乃至６のいずれか１項に記載の画像処理装置。
【請求項８】
前記計算ユニットが、輪郭点の間の結合確率を、輪郭点の間隔に基づき、ならびにコントラスト、色、および方向といった属性の少なくとも１つに基づき算定するように構成される、請求項７に記載の画像処理機構。
【請求項９】
画像データをセグメント化するための機構が、輪郭点を決定および処理するための機構によって準備された輪郭点を含むリストデータを基に輪郭の頂点を決定するための機構を備えており、その際、輪郭の頂点を決定するための前記機構が、以下のアルゴリズム：
・１つの輪郭の相次ぐ輪郭点の集合の各点ｐに対し、点（ｐ−，ｐ，ｐ＋）によるトリプルを形成し、その際、前記点ｐ−、ｐ＋は、前記輪郭に沿った両方向において前記点ｐから間隔をあけた輪郭点を表す、
・前記点に対し、条件
（ｉ）ｄ２ｍｉｎ≦｜ｐ−ｐ＋｜２≦ｄ２ｍａｘ、
（ｉｉ）ｄ２ｍｉｎ≦｜ｐ−ｐ−｜２≦ｄ２ｍａｘ、
および
（ｉｉｉ）α≦αｍａｘ
が満たされるかどうかをテストし、その際、ｄ２ｍｉｎ、ｄ２ｍａｘ、およびαｍａｘは設定された所定のパラメータであり、かつその際、開き角度αには以下が適用され、
【数１】
2010503936.tif 000010
この場合、ａは前記点ｐとｐ＋の間隔を表し、ｂは前記点ｐとｐ−の間隔を表し、かつｃは前記点ｐ＋とｐ−の間隔を表しており、その際、ｐの両側で近隣にある一連の点に対して、条件（ｉ）、（ｉｉ）、および（ｉｉｉ）がテストされる、
・テストされた、全ての条件（ｉ）、（ｉｉ）、および（ｉｉｉ）を満たす点（ｐ−，ｐ，ｐ＋）による前記トリプルの集合から、最小の開き角度αまたはそれを基に導き出された大きさを選び出し、かつ前記点ｐに割り当てる、
・点ｐに対し、条件（ｉ）、（ｉｉ）、および（ｉｉｉ）が満たされており、かつより小さな開き角度αを有する近隣の点ｐ’が存在する場合、点ｐを選び捨てる、
を実施するための機構を含むことを特徴とする請求項１乃至８のいずれか１項に記載の画像処理装置。
【請求項１０】
輪郭の頂点を決定するための機構が、トリプル（ｐ，ｐ＋，ｐ−）を輪郭点ｐ＋、ｐ−によって次々に形成し、かつ条件（ｉ）、（ｉｉ）、および（ｉｉｉ）を満たすことに基づきテストするように形成されており、前記輪郭点ｐ＋、ｐ−が、輪郭点ｐから輪郭に沿って漸進的により遠くに離れていくことを特徴とする請求項９に記載の画像処理装置。
【請求項１１】
輪郭の頂点を決定するための機構が、トリプル（ｐ，ｐ＋，ｐ−）に対し、条件（ｉ）、（ｉｉ）、および（ｉｉｉ）の１つが満たされないとすぐに、所与の輪郭点ｐに対する条件（ｉ）、（ｉｉ）、および（ｉｉｉ）のテストを中断するように形成されることを特徴とする請求項９または１０のいずれか１項に記載の画像処理装置。
【請求項１２】
輪郭の頂点を決定するための機構内で、パラメータｄ２ｍｉｎが、ｄ２ｍｉｎ≧４での値を設定されることを特徴とする請求項９乃至１１のいずれか１項に記載の画像処理装置。
【請求項１３】
輪郭の頂点を決定するための機構内で、パラメータαｍａｘが、αｍａｘ≦１６０°での値を設定されることを特徴とする請求項９乃至１２のいずれか１項に記載の画像処理装置。
【請求項１４】
輪郭の頂点を決定するための機構が、所与の輪郭点ｐに対し、輪郭に沿ったそれぞれの側で最高７つの輪郭点を、条件（ｉ）、（ｉｉ）、および（ｉｉｉ）のテストのために考慮に入れるように形成されることを特徴とする請求項９乃至１３のいずれか１項に記載の画像処理装置。
【請求項１５】
画像処理装置が、リアルタイム画像処理のために構成されることを特徴とする請求項１乃至１４のいずれか１項に記載の画像処理装置。
【請求項１６】
装置が、デュアル・ポートＲＡＭメモリと、前記デュアル・ポートＲＡＭメモリからのリストデータの格納および読み出しを同時にするための機構とを備えることを特徴とする請求項１乃至１５のいずれか１項に記載の画像処理装置。
【請求項１７】
コネクタを含む輪郭点リストを、特性の少なくとも１つに関してフィルタリングするように構成された形態学的フィルタの計算機構を含んでおり：
・最高３つの輪郭点による鎖での輪郭点を消去する、
・最高３つの輪郭点を備えており、より長い鎖と片側で結合されている鎖にのみ属する輪郭点を消去する、
・鎖のスタート点およびエンド点が共に全体の一部をなす輪郭点を形成する輪郭点を、輪郭点リスト内で特徴づける、
・少なくとも２つの鎖の分岐点を形成する輪郭点を、輪郭点リスト内で特徴づける、
請求項１乃至１６のいずれか１項に記載の画像処理装置。
【請求項１８】
輪郭点に対しランク・ベクトルを生成するための機構であり、コネクタ構造を含む輪郭点リストを読み出し、かつそれぞれ中心点から出てコネクタを介して、全ての近隣点のコネクタ構造を読み込み、かつ近隣点および中心点自体の分岐数を内容として含むランク・ベクトルを生成する前記機構を特徴とする請求項１乃至１７のいずれか１項に記載の画像処理装置。
【請求項１９】
メモリ内に格納されたリストデータを基に、計算機関によって、それぞれの２つの輪郭点の間の結合確率を、点の互いに対する間隔を考慮して確定するように構成されている計算ユニットが、それぞれ、１つの中心の輪郭点に対し、中心の輪郭点を含めた輪郭点の間の起こりうる結合に関する結合確率を確定するように構成されており、前記輪郭点が、中心点から、デジタル画像のラスタに関し最大で２〜２．５ピクセル離れている、請求項１乃至１８のいずれか１項に記載の画像処理装置。
【請求項２０】
分類器が、それぞれの選び出された中心の輪郭点のための選び捨てを、少なくとも１回は、中心点の近隣にある選び捨てられていない輪郭点の集合に対して繰り返すように構成される、請求項１乃至１９のいずれか１項に記載の画像処理装置。
【請求項２１】
分類器が、結合が中心点の近隣にある２つの点を結合しない限りにおいて、それぞれ中心の輪郭点の近隣にあり、近隣の輪郭点への起こりうる結合を最低の結合確率で有する輪郭点を選び捨てる選び出し過程を、それぞれの選び出された中心の輪郭点のために、更なる輪郭点が選び捨てられ得なくなるまで繰り返すように構成される、請求項１乃至２０のいずれか１項に記載の画像処理装置。
【請求項２２】
メモリ内に格納されたリストデータを基に、計算機関によって、それぞれ２つの輪郭点の間の結合確率を確定するように構成されている計算ユニット、その前に接続されており、周辺域の近隣の点だけを漸次的に読み出すことによって、選び出された中心の輪郭点の近隣にある輪郭点のリストデータを、それぞれ中心の輪郭点の周辺域の走査の際に得られる順序に相応に出力するソート機構、を含む、請求項１乃至２１のいずれか１項に記載の画像処理装置。
【請求項２３】
画像メモリ内に格納されたデジタル画像データを走査し、かつ輪郭点をサブピクセル精度で確定し、かつ連続するリストデータとしてメモリ内に格納するように構成されている前記計算ユニットが、画像データのラスタ内の各輪郭点に対し、最高１つの輪郭点をサブピクセル精度で確定するように構成される、請求項１乃至２２のいずれか１項に記載の画像処理装置。
【請求項２４】
前記分類器が、近隣の輪郭点のインデックスおよび近隣の輪郭点に対する結合確率を含むコネクタを、輪郭点リスト内に登録する、請求項１乃至２３のいずれか１項に記載の画像処理装置。
【請求項２５】
輪郭点リストを、配列された順序で、配列された一連の輪郭点として読み出すための機構を含んでおり、その際、相次ぐリスト登録が、輪郭に沿った相次ぐ輪郭点に属する、請求項１乃至２４のいずれか１項に記載の画像処理装置。
【請求項２６】
１つの輪郭に属する輪郭点の集合を基に、前記輪郭のコントラスト割付を計算し、かつ閾値と比較するための機構を特徴とする請求項１乃至２５のいずれか１項に記載の画像処理装置。
【請求項２７】
前記機構が、コントラスト割付を１つの輪郭に属する輪郭点の集合の属性として保存することを特徴とする請求項２６に記載の画像処理装置。
【請求項２８】
輪郭のコントラスト割付を計算するための装置が、輪郭点に対し
・輪郭点の画像周辺域内でその方向に沿って局所的に最大のコントラストが生じる走査方向を算定すること、ならびに
・輪郭点に属するコントラスト値が累算の際に加算されるか、または減算されるかを提示するカウント方向を、輪郭点での輪郭の走査方向および方向ベクトルに依存して確定すること、および
・個々の輪郭点のコントラスト値を、累算のための前記輪郭点のカウント方向に相応に加算または減算すること、
を特徴とする請求項２６または２７のいずれか１項に記載の画像処理装置。
【請求項２９】
前記機構が、最高で１６方向までに数を制限した様々な可能な方向から、それぞれの走査方向を選び出すことを特徴とする請求項２８に記載の画像処理装置。
【請求項３０】
輪郭点の集合が、以下の条件
ａ）輪郭の長さが、所定の値、好ましくは１０ピクセルより小さく、かつ輪郭のスタート点もエンド点も度数１を有しており、つまり更なる輪郭の構成要素ではない、
ｂ）輪郭の長さが、所定の値、好ましくは１０ピクセルより小さく、かつ輪郭のスタート点かエンド点が度数＞２を有している、
ｃ）スタート点およびエンド点が同一であり、かつ輪郭の長さが、所定の値、好ましくは１０ピクセルより小さい、
ｄ）コントラスト割付の数値が所定の値より小さい、
の少なくとも１つを満たす場合に、共通の輪郭に属する輪郭点の集合を選び捨てるデータフィルタ機構を特徴とする請求項１乃至２９のいずれか１項に記載の装置。
【請求項３１】
１つまたは複数の画像メモリと、画像データから輪郭点を確定するための少なくとも１つの集積されたハードウェア・ユニットと、輪郭点を確定するための前記集積されたハードウェア・ユニットの後に接続された、１つの輪郭に属する輪郭点の間の結合を確定するためのハードウェア・ユニットと、結合を確定するための前記ハードウェア・ユニットの後に接続された、輪郭点から出ている近隣の輪郭点への輪郭結合の数を決定するための形態学的プロセッサと、ならびに輪郭点について、およびその更なる輪郭点への結合についてのデータから、画像データの輪郭を描く対象を作成するセグメント化のための機構とを備えた画像処理装置であって、その際、１つの輪郭に属する輪郭点の間の結合を確定するための前記ハードウェア・ユニットに対しては、１つまたは複数の画像メモリを除き、輪郭を描く対象へと画像データを処理するためのメモリ全体のうち最高２０％のメモリまたはメモリ領域が割り当てられており、かつその際、画像データをセグメント化するための前記機構、好ましくは輪郭の頂点を決定するための機構が、輪郭点を含むリストデータを備えており、その際、輪郭の頂点を決定するための前記機構が、以下のアルゴリズム：
・１つの輪郭の相次ぐ輪郭点の集合の各点ｐに対し、点（ｐ−，ｐ，ｐ＋）によるトリプルを形成し、その際、前記点ｐ−、ｐ＋は、輪郭に沿った両方向において点ｐから間隔をあけた輪郭点を表す、
・前記点に対し、条件
（ｉ）ｄ２ｍｉｎ≦｜ｐ−ｐ＋｜２≦ｄ２ｍａｘ、
（ｉｉ）ｄ２ｍｉｎ≦｜ｐ−ｐ−｜２≦ｄ２ｍａｘ、
および
（ｉｉｉ）α≦αｍａｘ
が満たされるかどうかをテストし、その際、ｄ２ｍｉｎ、ｄ２ｍａｘ、およびαｍａｘは設定された所定のパラメータであり、かつその際、開き角度αには以下が適用され、
【数２】
2010503936.tif 000011
この場合、ａは前記点ｐとｐ＋の間隔を表し、ｂは前記点ｐとｐ−の間隔を表し、かつｃは前記点ｐ＋とｐ−の間隔を表しており、その際、ｐの両側で近隣にある一連の点に対して、条件（ｉ）、（ｉｉ）、および（ｉｉｉ）がテストされる、
・テストされた、全ての条件（ｉ）、（ｉｉ）、および（ｉｉｉ）を満たす点（ｐ−，ｐ，ｐ＋）による前記トリプルの集合から、最小の開き角度αまたはそれを基に導き出された大きさを選び出し、かつ点ｐに割り当てる、
・点ｐに対し、条件（ｉ）、（ｉｉ）、および（ｉｉｉ）が満たされており、かつより小さな開き角度αを有する近隣の点ｐ’が存在する場合、点ｐを選び捨てる、
を実施するための機構を含んでいる、特に請求項１に記載の集積された画像処理装置。
【請求項３２】
申込用紙認識のために形成された、請求項１乃至３１のいずれか１項に記載の画像処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全般的には画像処理のための装置および方法に関する。本発明は特に、画像データから輪郭点を確定し、かつこの輪郭点に基づき、共に全体の一部をなす輪郭点を、更なる処理のために対象へと統合するセグメント化を行う、画像処理のための方法および装置に関する。
【背景技術】
【０００２】
非常に様々な技術の適用に関し、今日では、自動的な対象認識を実現するために画像処理システムが用いられる。例えば産業ロボットは、対象ならびにその体勢およびポジションをロボットに認識させ得る処理済み画像データに基づき、頻繁に自分の進む方向を確認する。ただしこれまでは、信頼性の高い対象認識を保証するために、認識すべき対象についての大量の「先験的」知識を必要とした。これに伴い、それぞれの技術の使用分野に特異的に合わせて作られたソフトウェアによる解決策もしばしば提供されている。このようなアプローチは、非常に労力を要し、かつ相応に高価であることが明らかである。またこの場合はたびたび、技術の転換に続いてやたらと時間のかかる学習プロセスも行われ、この学習プロセスによって、選び出した対象を認識するためのシステムを訓練する。もう１つの更なる欠点は、画像認識のためにメモリ集約的で複雑な計算が必要なことである。したがってこのやり方では、リアルタイム認識はほとんど実現不可能である。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
このため本発明の課題は、画像認識をリアルタイムで行うことを可能にし、かつ非常に少ない先験的情報だけで、またはそれどころか如何なる先験的情報もなしで、的確で信頼性の高い対象認識を実施可能な技術的解決策を提供することである。この課題は、独立請求項に提示したような装置および方法によって、非常に意外にも簡単なやり方で既に解決される。本発明の有利な実施形態および変形形態は、それぞれの従属請求項に提示されている。
【課題を解決するための手段】
【０００４】
このため、ハードウェアの形での、画像データをセグメント化するための集積された機構と、同様にハードウェアの形での、輪郭点を決定および処理するための集積された機構とを備えた画像処理装置は、画像データをセグメント化するための機構が、輪郭点を決定および処理するための機構によって準備されたリストデータを基に輪郭の頂点を決定するための機構を備えることを特徴とし、その際、この輪郭の頂点を決定するための機構は、以下のアルゴリズム：
・１つの輪郭の相次ぐ輪郭点の集合の各点ｐに対し、点（ｐ−，ｐ，ｐ＋）によるトリプルを形成し、その際、点ｐ−、ｐ＋は、輪郭に沿った両方向において点ｐから間隔をあけた輪郭点を表す、
・これらの点に対し、条件
（ｉ）ｄ２ｍｉｎ≦｜ｐ−ｐ＋｜２≦ｄ２ｍａｘ、
（ｉｉ）ｄ２ｍｉｎ≦｜ｐ−ｐ−｜２≦ｄ２ｍａｘ、
および
（ｉｉｉ）α≦αｍａｘ
が満たされるかどうかをテストし、その際、ｄ２ｍｉｎ、ｄ２ｍａｘ、およびαｍａｘは設定された所定のパラメータであり、かつその際、開き角度αには以下が適用され、
【０００５】
【数１】
2010503936.tif 000003
この場合、ａは点ｐとｐ＋の間隔を表し、ｂは点ｐとｐ−の間隔を表し、かつｃは点ｐ＋とｐ−の間隔を表しており、その際、ｐの両側で近隣にある一連の点に対して、条件（ｉ）、（ｉｉ）、および（ｉｉｉ）がテストされる、
・全ての条件（ｉ）、（ｉｉ）、および（ｉｉｉ）を満たす点（ｐ−，ｐ，ｐ＋）によるテストされたトリプルの集合から、最小の開き角度αまたはそれを基に導き出された大きさを選び出し、かつ点ｐに割り当てる、
・点ｐに対し、条件（ｉ）、（ｉｉ）、および（ｉｉｉ）が満たされており、かつより小さな開き角度αを有する近隣の点ｐ’が存在する場合、点ｐを選び捨てる、
を実施するための機構を含んでいる。
【０００６】
その際、近隣の点ｐ’は、点ｐの周りの輪郭に沿った所定の周辺域内に配置された点と解される。例えば条件として、
｜ｐ２−ｐ’ ２｜≦ｄ２ｍａｘ
を設定することができる。
【０００７】
パラメータｄ２ｍａｘの設定により、強く湾曲した輪郭の場合に、遠く離れた点の間の小さな開き角度を誤って割り当てることが回避される。パラメータｄ２ｍｉｎは、輪郭または輪郭点を走査する解像度を提示している。更に、効果的な走査を実現するための｜ｐ−ｐ＋｜２に関する有利な許容領域は、ｄｍａｘ≧ｄｍｉｎ＋１、例えばｄｍａｘ＝ｄｍｉｎ＋２が設定される場合に達成される。パラメータｄｍａｘ、ｄｍｉｎ、およびαｍａｘは、ハードウェアによって固定的に予め定められている必要はなく、むしろ画像処理装置は、パラメータの少なくとも１つを選択可能または変更可能に設定するようにも形成され得る。
【０００８】
本発明によるアルゴリズムは、特に簡単で効果的に、ハードウェア内、好ましくはＦＰＧＡモジュールまたはＡＳＩＣモジュール内で実行可能であることが判明している。特に、必要なメモリも比較的小さい。まとめるとこれは、直線セグメントの間の対象頂点の非常に高速な認識を生じさせ、かつこれらの点を使用して、広範囲のセグメント化を可能にする。特にこの場合、頂点の間の結合も高速に形成することができ、かつ更に処理することができる。
【０００９】
トリプルまたは点ｐ＋、ｐ−の選び出しのために、様々な選び出し規則を用いることができる。ただし、トリプル（ｐ，ｐ＋，ｐ−）が輪郭点ｐ＋、ｐ−によって次々に形成され、かつ条件（ｉ）、（ｉｉ）、および（ｉｉｉ）を満たすことに基づきテストされ、この輪郭点ｐ＋、ｐ−が、輪郭点ｐから輪郭に沿って漸進的により遠くに離れていく場合が、とりわけ加算器およびマルチプレクサの必要な数に関しても、特に効果的である。その際、十分な精度での頂点決定の計算速度に関しては、トリプル（ｐ，ｐ＋，ｐ−）に対し、条件（ｉ）、（ｉｉ）、および（ｉｉｉ）の１つが満たされないとすぐに、所与の輪郭点ｐに対する条件（ｉ）、（ｉｉ）、および（ｉｉｉ）のテストを中断する場合が、更に有利である。
【００１０】
更に、誤りの少ないセグメント化のためには、画像解像度および画像コントラストに対する多数の条件に関して、輪郭の頂点を決定するための機構内で、パラメータｄ２ｍｉｎがｄ２ｍｉｎ≧４での値を設定される場合が有利であることが実証されている。更にパラメータαｍａｘに関しては、αｍａｘ≦１６０°の値が有利である。
【００１１】
条件（ｉ）〜（ｉｉｉ）が、多数の近隣の輪郭点に対して満たされたままでは、輪郭点ｐに関する最小の開き角度を決定するための計算労力が増大する。そのため、頂点分析の計算労力および速度に関しては、輪郭の頂点を決定するための機構が、所与の輪郭点ｐに対し、輪郭に沿ったそれぞれの側で最高７つの輪郭点を、条件（ｉ）、（ｉｉ）、および（ｉｉｉ）のテストのために考慮に入れるように形成される場合が有利である。言い換えると、輪郭点ｐ＋、ｐ−がそれぞれ、点ｐから７つ離れた輪郭点である場合にテストが中断される。
【００１２】
本発明は、１つまたは複数の画像メモリと、少なくとも１つの集積されたハードウェア・ユニットとを備えた好ましくは集積された画像処理装置を、対象セグメント化から独立させて企図しており、この画像処理装置は、画像メモリ内に格納されたデジタル画像データを走査し、かつ輪郭点をサブピクセル精度で確定し、かつ連続するリストデータとしてメモリ内に格納するように構成されている。この画像処理装置は更に計算ユニットを有しており、この計算ユニットは、メモリ内に格納されたリストデータを基に、計算機関によって、それぞれ２つの輪郭点の間の結合確率を、点の互いに対する間隔を考慮して確定するように構成されている。そのうえ、以下に分類器と称する少なくとも１つの計算ユニットが企図されており、この計算ユニットは、計算された結合確率の集合から、その中の１つが事前に決定された中心の輪郭点であるところの少なくとも３つの近隣の輪郭点の間の起こりうる結合に関する少なくとも３つの結合確率を備えた部分集合を選び出し、かつそれぞれの部分集合に関し、結合が、中心点の近隣にある２つの点を結合しない限りにおいて、中心の輪郭点または中心点の近隣にあり、近隣の輪郭点への起こりうる結合を最低の結合確率で有する輪郭点を選び捨て、これに続いて、選び捨てられていない輪郭点を、中心点への残った結合を特徴づけるコネクタと共に、輪郭点リストに登録する。
【００１３】
更に本発明は、画像データ内の関連のある輪郭を確定するための方法を企図しており、この方法は、特に上述のような画像処理装置において実施可能であり、この画像処理装置では、画像データから輪郭点を確定し、かつ輪郭点の、近隣の輪郭点に対する起こりうる結合の結合確率を算定し、かつその際、そのような結合確率の集合から、少なくとも２つの輪郭点と、近隣の選び出された中心の輪郭点との間の起こりうる結合に関する少なくとも３つの結合確率を備えた１つまたは複数の部分集合を分析し、かつ結合が、中心点の近隣にある２つの点を結合しない限りにおいて、それぞれ中心の輪郭点の近隣にあり、別の点の１つに対する起こりうる結合を最低の結合確率で有する輪郭点を選び捨て、かつ部分集合のこの分析の終了後、中心点への、１つの輪郭に属する結合を特徴づけるコネクタを含む輪郭データを、電子メモリ内のリストに登録する。このコネクタはその後、輪郭点がこのコネクタに基づき、対象処理および対象認識に用いられる輪郭セグメントへと統合されることによって、更に処理され得る。
【００１４】
本発明の意味において近隣の輪郭点とは、例えば直接的に互いに境を接するピクセルにある輪郭点と解されるのではなく、むしろ中心点の周りの所定の周辺域内での全ての輪郭点である。これは例えば、それぞれの考察される中心点をその中心に備えた５×５の周辺域であり得る。その場合、この輪郭点の集合を近傍とも称する。
【００１５】
その際、画素に対するサブピクセル精度での輪郭点の位置の確定は、その画素および更なる周辺の画素の位置を基に、計算によって行われる。
【００１６】
それぞれ、中心点への最低の結合確率を有する輪郭点を集合から選び捨てる本発明による選び出し過程は、メモリを非常に少なくしか必要としないという利点を提供する。特に、連続するリストデータに基づき処理を行うことができる。このために必要なメモリ要求量の少なさは、用いるべきハードウェアの使用を少なくし、それどころかリアルタイムでの処理を可能にする。これに加え、上述のプロセスはその単純さにより、容易にハードウェア・モジュール内で、費用のかかるソフトウェアおよび周辺装置の接続なしに実行することができる。このため本発明による装置は非常に単純に、非常にコンパクトな集積されたハードウェアの画像処理装置として実施することができる。必要なメモリを減らすためには、特に連続するリストデータの形の輪郭点を更に処理することも、特に有利である。このリストデータは、有意な輪郭点の画素座標および周辺域の属性だけを、したがって輪郭認識に有意なデータだけを含んでいることが好ましい。それに応じてデータ量はこのやり方で、画像の元データに対して最低限まで減らされる。選び捨ては、それぞれ考察された中心点と共に同じ輪郭に属する輪郭点を確定するという目標を有している。
【００１７】
更なる処理のために、中心点に対して最低の結合確率を備えた輪郭点を選び捨てることによって輪郭点を選び出すステップは、次のように具体的に示すこともできる。中心点の周りでグループ化された輪郭点の集合（近傍候補）は、輪郭点の間の結合確率を線分によって示すことにより、平面において具象的に分かり易く示すことができ、その際、線分の長さは間接的に結合確率に比例している。こうして、中心点および中心点の近隣にある少なくとも２つの更なる輪郭点を頂点として含む多角形が形成される。続いて、中心点の近隣にある点のうち、多角形の更なる１つの点への最長の結合が出ている点が取り除かれる。この方法はその後、ある程度の数の輪郭点が残っており、また点の配置に応じて場合によっては中心点を含めて２つの点だけが残っており、かつ要素の更なる消去が起こる多角形を形成できなくなるまで、近隣の輪郭点の数に応じて、中心点の近隣にある全ての輪郭点のために繰り返され得る。
【００１８】
分類器のこの選び出し過程は、中心点の近傍の輪郭点または中心点の近隣にある輪郭点の集合から、それぞれ、中心点および更なる２つの輪郭点によるトリプルとしての部分集合が、割り当てられた結合確率で形成され、かつ帰属の結合が、中心の輪郭点の近隣にある２つの輪郭点を結合しない限りにおいて、好ましくは結合確率のための３つの比較器によって最低確率を確定し、かつそれぞれ、中心点の近隣にあり、トリプル内で最低の結合確率を備えた結合が出ている輪郭点が、中心点の近隣にある輪郭点の近傍集合から選び捨てられる場合に、少ない算術演算および少ないハードウェアの使用で、特に効果的に実施することができる。
【００１９】
分類器が選び捨ての後に近傍内に残したコネクタは、輪郭点リストに登録され、かつその際、近隣の輪郭点のインデックスおよび近隣の輪郭点への結合確率ならびに更なる近傍情報（方向ＤＩＲ、コントラストｃｏｎｔ、色）を含むことができる。
【００２０】
輪郭点が再び、結合確率によって修正された座標で平面上に配置されたとして考察される場合、この手続が、輪郭点のトリプルを形成することに相応し、それに応じてこの輪郭点の結合が三角形を形成する。こうして三角形における最長の辺が決定され、かつ中心点の近隣にあり、最長の辺が出ている輪郭点が消去される。
【００２１】
選び捨て過程または残っている輪郭点の選び出し過程が、選び捨てられていない輪郭点の集合に対し、好ましくは少なくとも１回繰り返される。画像処理装置、特に、選び出された中心の輪郭点に対し少なくとも２つの輪郭点を結合するための少なくとも３つの要素からそれぞれ最低の結合確率を備えた結合を選び捨てる分類器は、特に、中心の輪郭点の近隣にある更なる輪郭点が消去または選び捨てられ得なくなるまで、それぞれの選び出された中心の輪郭点のために、最低の結合確率での起こりうる結合を備えた輪郭点を選び捨てる選び出し過程を繰り返すように構成することができる。
【００２２】
ところで、特に好ましいように、それぞれ輪郭点のトリプルまたは帰属の起こりうる結合に関する結合確率のトリプルを形成し、かつこの部分集合が輪郭点の１番近い近隣点だけ、またはこれらの点の間の結合確率だけを含むように形成されるような輪郭点の適切な読み出し順序に注意を払う場合、１番近い近隣の輪郭点の間の起こりうる結合に関する結合確率のトリプルの全てに対して選び捨てをちょうど１回繰り返すことが、少なくとも大多数の場合に、それぞれ考察された中心点と同じ輪郭に属さない全ての輪郭点を選び捨てるのに十分であることが判明している。
【００２３】
低い結合確率を備えた輪郭点を選び捨てることによる輪郭点の選び出しの際、場合によっては多義性が生じる可能性があり、この多義性は、例えば輪郭点のトリプルの場合、それぞれ中心点への結合に関して、それぞれ最長の結合または最低の結合確率があるにもかかわらず、結合確率のための分類器がどの輪郭点をも選び捨てないということを引き起こす。これは特に、点が、結合確率によって修正された座標で二等辺三角形またはそれどころか正三角形を形成する場合である。この場合は確かに、全ての輪郭点が引き継がれ得るであろうが、ただし意外にも、輪郭点の、ピクセル間隔より小さいポジション変位に相当する変調を結合確率に印加すると、アーチファクト分が減らされたかなりより良い近傍定義が行われることが判明している。
【００２４】
確かにこの場合、結合確率に関するデータが変更され、これは実際に、関連する輪郭に属する輪郭点についての誤った経路決定にも至り得るが、ただしこれは、あり得る誤った決定が平均において無効化されるので、無害であることが判明している。その際、変調の簡単な好ましい実現は、輪郭点のピクセル座標の変更である。ただし同様に、分類器内で結合確率を計算して、その後この結合確率に変調を印加することも可能であろう。
【００２５】
最も簡単な場合、輪郭点の結合確率は、これらの点の互いに対する間隔に基づき確定することができる。２つの輪郭点が互いから遠く離れれば離れるほど、その結合確率は小さくなる。ただし、輪郭点の更なる属性を捕捉し、かつ結合確率の計算内に一緒に組み込むことが好ましい。
【００２６】
その際特に、輪郭点の間の結合確率のための計算機関が、輪郭点の間隔に基づき、ならびにコントラスト、色、および方向といった属性の少なくとも１つに基づき算定する場合が有利であることが実証されている。このために本発明の一変形形態に基づき、メモリ内に格納されたリストデータを基に輪郭点の間の結合確率を確定するように構成されている計算ユニットが、輪郭点の間の結合確率を、輪郭点の間隔に基づき、ならびにコントラスト、色、および方向といった属性の少なくとも１つに基づき算定することが企図される。例えば１つまたは複数の属性に基づき、この属性値の関数の値を算定し、かつこの関数の値が、関数の種類に応じて閾値を超える、または下回る場合にのみ、結合確率を計算することができる。
【００２７】
その際、属性は例えば、輪郭点プロセッサから出力される平均的な点方向であり得る（１つの走査方向においてグレー値コントラストが最大になる）。平均的な点方向は、１つのコネクタに属する両方の輪郭点の方向ベクトルの和として定義され、かつ一般的には、コネクタ自体の方向に垂直な方向に良く近似している。２つの輪郭点が、輪郭に対して類似の方向を有する場合、相応に結合確率が、つまり両方の点が実際に共通の輪郭に属する確率が上昇する。更なる特徴は、平均的な点方向とコネクタ方向の間の角度である。この角度は、特に簡単なやり方では両方のベクトルのスカラー積を介して計算することができ、かつ結合確率に算入され得る。
【００２８】
コントラストは特に、輪郭点の近隣にあり、輪郭線によって分割されている領域の明るさの差であり得る。２つの輪郭点が、そのような類似のコントラストを有する場合、相応に、両方の輪郭点が共通の輪郭線上にある確率が上昇する。コントラストが逆である場合、たいていは細い線であり、この細い線の、一般的に平行に、僅かな間隔をあけて走っている輪郭は結合されてはならず、つまりこの場合には、結合確率はゼロに設定される。
【００２９】
そのため本発明のこの実施形態に基づき、画像メモリ内に格納されたデジタル画像データを走査し、かつ輪郭点をサブピクセル精度で確定し、かつ連続するリストデータとしてメモリ内に格納するように構成されている集積された計算ユニットは、輪郭点のポジションのほかに少なくとも１つの更なる輪郭点属性を計算し、かつ連続するリストデータ内に保存するように構成することができる。好ましくは、集積された計算ユニットによって１つの輪郭点のために１つの属性ベクトルが少なくとも２４ビットの長さ、好ましくは少なくとも３６ビットの長さで生成され、かつ連続するリストデータ内に保存される。その際、メモリ内に格納されたリストデータを基に輪郭点の間の結合確率を確定するように構成されている計算ユニットは、輪郭点の間の結合確率を、輪郭点の間隔および少なくとも１つの更なる属性に基づいて算定することができる。
【００３０】
更に好ましくは、高速で、少しのメモリしか必要とせずに画像データを処理することができるように、特に画像データから輪郭点およびコネクタを確定するためにそれぞれ１ピクセルより大きい幅、好ましくは少なくとも１６ピクセルの幅、特に好ましくは２６または３２ピクセルの幅を有する複数の帯状部において、画像データを読み出す。その際、画像データが、１ピクセルより多く、好ましくは少なくとも４ピクセル分、特に好ましくは少なくとも８ピクセル分重なっている帯状部において次々に読み出されることが好ましい。この重なりに基づき、確かに場合によってはコネクタが重なり領域内で二重に計算されるが、しかしこの追加的な多重労力は、個々の確定された輪郭がより容易に、およびより誤りなく再び組み立てられ得ることによって過分に補償される。
【００３１】
更に好ましくは、画像処理装置がリアルタイム画像処理のために構成される。これは、画像転送中に、輪郭を描く対象の完全な確定が行われることを意味する。このリアルタイム処理は特に、輪郭点に対するコネクタの非常に簡単な計算によっても可能である。
【００３２】
このようなリアルタイム処理を可能にするため、装置が、デュアル・ポートＲＡＭメモリと、このデュアル・ポートＲＡＭメモリからのリストデータの格納および読み出しを同時にするための機構とを有することが更に特に好ましい。このメモリは、非常に短いアクセス時間を可能にするだけでなく、特に、様々な画像処理のためのプロセスが、同時に同じメモリ内のデータにアクセスすることも可能にする。第１のプロセスがメモリ内にリストデータを書き込んでいる一方で同時に、既にもう１つのプロセスがリストデータを再びメモリから読み取ることが可能である。ただし、例えばＦＰＧＡ上でのそのようなメモリは、一般的に非常に小さい。典型的には、メモリは４キロバイトの領域を提供する。その際、最初にメモリ内で画像全体または画像領域をマッピングする代わりにリストデータを処理することが、このような小さなメモリへの制限をも可能にする。
【００３３】
コネクタを含むリストデータの形成の後に接続されたプロセスとして、形態学的フィルタが企図されることが好ましい。形態学的フィルタという概念は、この関連においてはフィルタ演算の平滑化作用を特徴づけるために使用され、もっとも実際には、この境界領域においては位相幾何学的な特性も活用される。
【００３４】
こうして本発明のこの実施形態に基づき、画像処理装置は形態学的フィルタの計算機構を有しており、この計算機構は、コネクタを含む輪郭点リストを、特性の少なくとも１つに関してフィルタリングするよう構成されており：
・最高３つの輪郭点による鎖での輪郭点を消去する、
・最高３つの輪郭点を備えており、より長い鎖と片側で結合されている鎖にのみ属する輪郭点を消去する、
・鎖のスタート点およびエンド点が共に全体の一部をなす輪郭点を形成する輪郭点を、輪郭点リスト内で特徴づける、
・少なくとも２つの鎖の分岐点を形成する輪郭点を、輪郭点リスト内で特徴づける。
【００３５】
そのうえ、対象セグメントへのコネクタの連結を容易にするため、本発明のもう１つの変形形態に基づき、輪郭点に対しランク・ベクトルを生成するための機構が企図されており、この機構は、コネクタ構造を含む輪郭点リストを読み出し、かつそれぞれ中心点から出てコネクタを介して、全ての近隣点のコネクタ構造を読み込み、かつ近隣点および中心点自体の分岐数を内容として含むランク・ベクトルを生成する。その際、このコネクタ構造は、輪郭点リストへのコネクタの登録に対して時間的に遅延して走査される。この時間的な遅延は、コネクタを含むリストデータが登録され、かつランク・ベクトルの形成のために読み出されもする当該のデュアル・ポートＲＡＭ内に既にデータが存在しているようにするために企図される。続いてランク・ベクトルを、表またはブール関数を介して、好ましくはスカラー・ポテンシャル関数に基づきマッピングすることができ、かつアーチファクトをポテンシャル関数によって選び捨てることができる。後のセグメント化を容易にするため、配列された一連の輪郭点として、配列された順序で輪郭点リストを読み出すための機構を企図することができ、その際、相次ぐリスト登録は、輪郭に沿って相次ぐ輪郭点に属している。この機構は、共に全体の一部をなす輪郭点を、特にそれぞれの輪郭点リスト内に保存されたコネクタに基づき確定することができる。
【００３６】
このような配列された輪郭点のリストは、本発明の意味において「チェーン」とも称する。そのため、セグメント化プロセスにおいて生成されるチェーンは、スタート点から出てエンド点に達する配列された一連の輪郭点を表している。その際、輪郭点のそれぞれには、言及したように、前に接続されたプロセスによって走査方向および走査方向に沿ったコントラストといった属性を当てがうことができる。
【００３７】
その際、チェーンの有意性を評価するため、チェーンまたは１つの輪郭に属する輪郭点の集合全般のコントラスト割付を計算することが有意義である。チェーンは、コントラスト割付の数値が所与の閾値を超えている場合に有意として評価される。特に、チェーンまたは１つの輪郭に属する輪郭点の集合の更なる処理を、この評価に依存して行うことができる。チェーンまたは集合が有意として評価されると、このチェーンまたは集合は引き続き使用され、そうでない場合、とりわけ低すぎるコントラスト割付の場合、このチェーンまたは輪郭点集合は切り捨てられる。言い換えると、低すぎるコントラスト割付を備えたチェーンが、本発明による装置の相応の機構によって選び捨てられる。この選び捨ては、すぐに行わなくてもよい。いずれにせよこのコントラスト割付も、チェーンまたは共通の輪郭に属する輪郭点の集合の属性として保存することが特に有利である。
【００３８】
コントラスト割付の計算は、１つの輪郭点に対しそれぞれ１つの走査方向を算定することによって、特に有利に行うことができる。この走査方向は、コントラストの正負符号には依存せず、この方向に沿って、画像周辺域内で局所的に最大のコントラストが生じる。更にこの走査方向は、輪郭点の周りの周辺域内でのコントラストの移り変わりが厳密に最大である方向でなくてもよい。むしろそれぞれの走査方向は、計算労力を制限するため、狭く制限した数の可能な方向から選び出すことができる。例えば最高１６方向、好ましくは８方向、またはそれどころか特に好ましくは４方向だけの可能な方向を使用することができ、それに応じて、この方向は相応に少ないビット数で表すことができる。この場合、１つの輪郭もしくは割り当てられたチェーンまたは輪郭点の集合のコントラスト割付を計算するため、個々の輪郭点のコントラスト値を、その輪郭点のカウント方向に相応して累算することができる。カウント方向は、輪郭点での輪郭の走査方向および方向ベクトルに依存して確定され、かつ輪郭点に属しており、それ自体が正負符号をもつコントラスト値が、累算の際に加算されるか、または減算されるかを提示している。
【００３９】
方向ベクトルも、走査方向と同様に、少ない方向または少ない可能性に制限され得ることが有利である。走査方向の場合と同様に、最高１６方向、例えば８方向または４方向だけの、方向ベクトルのための様々な可能な方向を、カウント方向の計算のために使用することができる。
【００４０】
本発明の変形形態では、コントラストの乏しいチェーンの選び捨てが、以下に「チェーン・フィルタ」とも称されるデータフィルタ機構によって行われる。この機構は、輪郭点の集合が、以下の条件
ａ）輪郭の長さが、所定の値、好ましくは１０ピクセルより小さく、かつ輪郭のスタート点もエンド点も度数１を有しており、つまり更なる輪郭の構成要素ではない、
ｂ）輪郭の長さが、所定の値、好ましくは１０ピクセルより小さく、かつ輪郭のスタート点かエンド点が度数＞２を有している、
ｃ）スタート点およびエンド点が同一であり、かつ輪郭の長さが、所定の値、好ましくは１０ピクセルより小さい、
ｄ）コントラスト割付の数値が所定の値より小さい、
の少なくとも１つを満たす場合に、共通の輪郭に属する輪郭点の集合を選び捨てる。
【００４１】
これに応じてフィルタリングは、累算されたコントラストに基づいてだけでなく、特に構造の大きさのような更なる基準に基づいても行われる。
【００４２】
このチェーン・フィルタによって、ノイズなどのアーチファクトにより発生し、かつ有意義な構造を描かない輪郭に属するチェーンまたはチェーン・セグメントが選び捨てられるべきである。このチェーン・フィルタは、上述の形態学的フィルタによって説明されたフィルタリングを補う。
【００４３】
輪郭点の間の結合の、アーチファクトの少ない確定は、選び出された中心の輪郭点の周辺域が小さいことによって既に機能することが判明している。こうして、輪郭点の起こりうる結合に関する結合確率がそれぞれ、１つの輪郭点から、デジタル画像のラスタに関し最大で２〜２．５ピクセル離れているような中心の輪郭点を含めた更なる輪郭点に対してのみ算定される場合に、輪郭点の間の結合の信頼性の高い確定を行うことができる。
【００４４】
コネクタの計算のためには、ほぼ独占的に、それぞれ１番近い近隣の輪郭点のみが有意である。このため選び捨てのために、輪郭点の集合、特にトリプルの集合の形成が巧みに行われる場合には既に、計算ステップを節減することができる。このため本発明の一変形形態に基づき、輪郭点の間の起こりうる結合に関する結合確率を計算するための計算ユニットの前に接続されたソート機構が企図され、このソート機構は、周辺域の近隣の点だけを漸次的に読み出すことによって、選び出された中心の輪郭点の近隣にある輪郭点のリストデータを、それぞれ中心の輪郭点の周辺域の走査の際に得られる順序に相応に出力する。これが、例えば通常の画像書式における画像データとの相違点である。本発明ではデータが行ごとに配列されている。この場合、行内では確かに、画像ファイルの相次ぐデータは、確かに相次ぐ画素に属しており、つまり近隣の画素にも属しており、ただしこれは行の終わりでは当てはまらなくなる。ここでは、行の最後の点から、遠く離れた次の行の最初の点へのジャンプが行われる。
【００４５】
一見すると、用いられたサブピクセル精度での輪郭点の確定、または用いられたサブピクセル・ラスタは、余剰的または不必要な情報を含むと思われ、したがって以降の計算を遅くする、またはより複雑にすると思われる。ただし、例えば追加的な点が計算されるのではなく、むしろ画像データのラスタ内の各輪郭点に対して最高１つの輪郭点がサブピクセル精度で確定されることが好ましい。
【００４６】
既に上で論じたように、本発明はきわめて倹約的なメモリ使用を可能にする。このため本発明のもう１つの観点に基づき、本発明による装置は、１つまたは複数の画像メモリと、画像データから輪郭点を確定するための少なくとも１つの集積されたハードウェア・ユニットと、この輪郭点を確定するための集積されたハードウェア・ユニットの後に接続された、１つの輪郭に属する輪郭点の間の結合を確定するためのハードウェア・ユニットと、この結合を確定するためのハードウェア・ユニットの後に接続された、輪郭点から出ている近隣の輪郭点への輪郭結合の数を決定するための形態学的プロセッサと、ならびに輪郭点について、およびその更なる輪郭点への結合についてのデータから、画像データの輪郭を描く対象を作成するセグメント化のための機構とを備えた、集積された画像処理装置としても実現可能であり、その際、１つの輪郭に属する輪郭点の間の結合を確定するためのハードウェア・ユニットに対しては、１つまたは複数の画像メモリを除き、輪郭を描く対象へと画像データを処理するためのメモリ全体のうち最高２０パーセントのメモリまたはメモリ領域が割り当てられている。
【００４７】
以下に本発明を、例示的実施形態に基づき、および添付した図面に関連して、更に詳しく説明する。その際、同じ符号は、同じまたは類似の部分を示している。
【図面の簡単な説明】
【００４８】
【図１】集積されたリアルタイム画像処理システム（ＩＥＢＶＳ）のアーキテクチャ図である。
【図２】輪郭点リストのグラフィック表示を示す図である。
【図３】輪郭点、コネクタ、および点方向を備えた輪郭の一領域の概略図である。
【図４】輪郭点を読み出すための配列原理図である。
【図５】ソート機構の配線図である。
【図６】１つの輪郭点の５×５周辺域内にある輪郭点の例示的分布図である。
【図７】計算例を示す図であり、サブピクセル・ラスタにおける近隣の輪郭点の配置を示す。
【図８】計算例を示す図であり、オリジナル・ラスタにおける輪郭点の位置を示す。
【図９】計算例を示す図であり、Ａ乃至Ｃは輪郭点の座標値および間隔を含む表を示す。
【図１０】コネクタを確定するためのＳＮＮＣ（「統計的最近傍分類器（Ｓｔａｔｉｓｔｉｃａｌ  Ｎｅａｒｅｓｔ  Ｎｅｉｇｈｂｏｕｒｈｏｏｄ  Ｃｌａｓｓｉｆｉｅｒ）」）を示す図である。
【図１１】サブピクセル・ラスタにおける近隣の輪郭点の更なる配置を示す図である。
【図１２】輪郭点と、選び捨てによって確定された結合とを備えた画像の比較的大きな部分図である。
【図１３】ＳＮＮＣによって更なる処理のために保存されたデータのデータ構造を示す図である。
【図１４】ランク・ベクトルを生成するための形態学的フィルタの機構のブロック配線図である。
【図１５】形態学的フィルタリング後の輪郭点リストのデータ構造の一例を示す図である。
【図１６】３以上のランクを備えた特異点のデータを保存するための輪郭点リストのデータ構造の一例を示す図である。
【図１７】配列された一連の輪郭点として、配列された順序で輪郭点リストを読み出すための機構を示す図である。
【図１８】輪郭のコントラスト割付を確定するための、走査方向を記入されたチェーンの輪郭点を示す図である。
【図１９】可能な走査方向の集合の一例を示す図である。
【図２０】コントラスト累算器のための例示的実施形態を示す図である。
【図２１】画像処理のためのプロセスの位相位置およびメモリ要求量を示す図である。
【図２２】輪郭点を備えた輪郭の一部、および頂点を決定するためのパラメータを示す図である。
【図２３】輪郭点を備えた輪郭の一部、および頂点を決定するためのパラメータを示す図である。
【発明を実施するための形態】
【００４９】
図１は、集積されたリアルタイム画像処理システムＩＥＢＶＳの形の、本発明に基づく装置１の構造またはアーキテクチャを示している。このＩＥＢＶＳは、画像インターフェイスを含んでおり、この画像インターフェイスに、１つまたは複数の画像ソース３、例えばＣＣＤカメラを接続することができ、かつこの画像インターフェイスは、画像データをデジタル画像として画像メモリ４内に格納する。この画像メモリ４に、集積されたハードウェア・ユニットの形の輪郭点プロセッサ５がアクセスし、このハードウェア・ユニットは、画像メモリ４内に格納されたデジタル画像のデータを走査し、かつ輪郭点をサブピクセル精度で確定し、かつ連続するリストデータとしてメモリ内に格納するように構成されている。この輪郭点プロセッサ５は、輪郭点の座標および選び出された特徴をリスト形式で供給する。特徴とは、例えば境を接する領域のグレー値または色、コントラスト、もしくは方向である。
【００５０】
座標は、「関心領域（Ｒｅｇｉｏｎｓ  ｏｆ  Ｉｎｔｅｒｅｓｔ）」内、例えば水平に配置された帯状部内で、サブピクセル精度で出力される。普遍妥当に画像を処理するため、好ましくは最初にセグメント化、つまり均質な特徴を備えた領域への画像の区分けが行われることが有利であり、続いてこの特徴の解釈が行われる。
【００５１】
図２は、輪郭点リストのグラフィック表示を示している。鮮明な輪郭、例では欠陥のあるデータマトリクスコードの鮮明な輪郭のほかに、たいていは低コントラストでの多くの点が見られ、この多くの点は、様々な表面欠陥に基づき、またはノイズにより発生し得る。そこで以降の処理ユニットの課題は、個々の領域の間にある輪郭の構造を、配列された順序で、連結された一連の点として、ハードウェアによりリアルタイムで描くことであり、それによりこの一連の点が、次のステップでソフトウェアまたは更なるハードウェアにより、デジタルの幾何学的対象、特に線分、円、多項式などによって近似され、かつその後、認識され得る。
【００５２】
つまり本発明の課題は特に、まず輪郭点の近傍が統計的最近傍分類器７（ＳＮＮＣ）内で規定されることによって解決される。このＳＮＮＣ７は、メモリ内に格納されたリストデータを基に、計算機関によって、輪郭点の間の結合確率を、点の互いに対する間隔を考慮して確定する計算ユニットと、計算された結合確率の集合から、その中の１つが事前に決定された中心の輪郭点であるところの少なくとも３つの近隣の輪郭点の間の起こりうる結合に関する少なくとも３つの結合確率を備えた部分集合を選び出し、かつそれぞれの部分集合に関し、結合が、中心点の近隣にある２つの点を結合しない限りにおいて、中心の輪郭点の近隣にあり、近隣の輪郭点への起こりうる結合を最低の結合確率で有する輪郭点を選び捨て、これに続いて、選び捨てられていない輪郭点を、中心点への残った結合を特徴づけるコネクタと共に、輪郭点リストに登録する分類器とを含んでいる。その後、このデータはメモリ９内に登録される。このメモリ９は、特に好ましくはデュアル・ポートＲＡＭである。
【００５３】
続いて、メモリ９を読み出す形態学的フィルタ１１によって、有意な輪郭の選び出し、および有意でない欠陥の抑制が行われる。第３のステップでは、輪郭が、配列された順序で、連結された対象または「チェーン」として読み出される。その後この鎖に基づき、更なるハードウェア・ユニットによってセグメント化が行われる。装置１内でのプロセス進行は、マイクロコントローラ１５によって制御される。
【００５４】
このように複雑な構造を、リアルタイムという条件で回路内に集積するためには、厳密なパイプライン処理を企図することが好ましい。Ｌ２キャッシュの十分な支援を備えたハードウェア・プラットフォーム上で働き、かつ即時に異なるデータ構造へのアクセスを実施し得る既知のソフトウェア解決策とは違い、他方のこのやり方では、例えば図１に示したメモリ１のようなデュアル・ポートＲＡＭの形の小さな高速のＳＲＡＭ領域を使用し得るので、複雑な集積化の際にメモリ・サイズに対する制限を受け入れ得ることが有利である。更にこの場合、パイプラインのコンセプトが、労力のかかる探索プロセスおよび配列プロセスまたは補正プロセスの場合に制限を課すので、個々の部分ステップの処理品質に関する要求は拡張される。高速の内蔵ＳＲＡＭの典型的なメモリ・サイズは、好ましくは４〜１６キロバイトである。
【００５５】
更に達成可能な集積度は特に、これもまた実現すべき処理ステップ数に依存する損失電力によって決定される。それぞれのプロセス内でのデータフローが最低限の特に有利な解決策は、輪郭点を表すためにコンパクトなリスト書式が使用される場合に生じ、なぜなら階層構造の信号処理には、それぞれ厳密に決定された部分構造へのアクセスしか必要なく、そのため労力のかかる、グレー値データまたは色データを備えた画像アレイへのアクセスを回避できるからである。
【００５６】
統計的最近傍プロセッサ７（ＳＮＮＣ）の課題は、輪郭点を輪郭へと結合することである。中心点Ｐ［ｉ］に関する点Ｐ［ｊ］の近傍を規定するため、まず点集合の結合確率Ｐｃｏｎｎ［ｉ，ｊ］を計算し、その後、分類する。
【００５７】
簡単で信頼できる分類器は、間隔である。
【００５８】
【数２】
2010503936.tif 000004
【００５９】
Ｐｃｏｎｎ［ｉ，ｊ］が閾値を超えている場合、点は近傍ＮＢＤに属している。更なる近傍マトリクスは、Ｐｃｏｎｎ［ｉ，ｊ］を、走査方向ＤＩＲおよび／またはコントラストｃｏｎｔから作られたマトリクスで補うことによって作られる。これにより例えば、更に離れている同じ方向の点を的確に結合することができ、しかしながら垂直にあるノイズ点は結合されない。
【００６０】
前に接続された輪郭点プロセッサによって、局所的なコントラストｃｏｎｔおよび方向情報ＤＩＲといった更なる情報が用意されているので、結合決定のための閾値Ｐが、これらのパラメータの関数としてはっきり示され、かつ以下の関数に基づく表および／またはＡＬＵとして実施されることにより、決定を明らかに改善することができる。
【００６１】
【数３】
2010503936.tif 000005
【００６２】
上に提示した関係式において、Δｘ、Δｙは、結合のベクトル表示の成分を表しており、かつｘＤＩＲ、ｙＤＩＲ−は、平均的な点方向の成分を表している。関数ｆの独立変数は、角度αが９０°の場合に最大になる。
【００６３】
図３は、分かり易くするため輪郭１６の一領域を示しており、この輪郭上には輪郭点２６がある。１番近い近隣の輪郭点２６の間の結合２４は破線として記入されている。輪郭点２６の平均的な点方向２２は矢印として示されている。平均的な点方向は、例えば矢印の傍に提示した数字によって特徴づけることができる。図３に示した例では、輪郭点２６は、ここで使用された８方向の可能な点方向のうちの３方向を、数字０〜７に相応して有している。図３に基づき明らかであるように、角度αはそれぞれ、平均的な点方向２２と、２つの輪郭点２６の間の結合２４とで囲まれた角度である。
【００６４】
計算された確率Ｐｃｏｎｎ［ｉ、ｊ］が閾値「Ｔｈｒｅｓｈｏｌｄ」より大きければ、結合が作られる。
【００６５】
一般的には、連続する輪郭における各中心点は、１つだけ前および後の点を、使用したラスタのピッチから生じる程度の間隔をあけて有している。しかしながらこの相対的に狭い定義は、実際には、輪郭が破れ、かつ分割された対象として保存されることを招き、それによって後の処理の際に、取るに足らなくない労力を生じさせる。このためＳＮＮＣの課題はとりわけ、走査ラスタの画素間隔より大きい程度の間隔を有する輪郭点を結合することにもある。
【００６６】
最良の程度は具体的な条件に依存しているが、２〜２．５ピクセルの間隔値が、輪郭品質のかなりの改善を生じさせることが実証されている。ただしこれに対する代償は、リアルタイムで処理される近傍のためのあり得る候補数の上昇である。
【００６７】
したがってＳＮＮＣ７は、近傍ＮＢＤ内で位相幾何学的に有意な近隣点を確定するという課題を有する。こうしてこの課題は本発明によれば、集合ＮＢＤから、中心点Ｐｉと、ＮＢＤからの更なる２つの点Ｐｊ１およびＰｊ２の任意の組合せとから成るトリプルが形成され、かつ結合確率
Ｐｔｒｉｐｌｅｔ＝｛Ｐｃｏｎｎ［ｉ，ｊ１］，Ｐｃｏｎｎ［ｊ１，ｊ２］，Ｐｃｏｎｎ［ｉ，ｊ２］｝
が計算されることによって解決される。つまり、上に提示したトリプルまたはトリプレットは、選び出された１つの中心の輪郭点とそれぞれ２つの近隣の点のと間の全ての結合の間の結合確率を備えたベクトルを表しており、その際、近隣の点として、ピクセルの最高２〜２．５倍の間隔内にある全ての点が考慮される。
【００６８】
結合確率Ｐｃｏｎｎ［ｊ１，ｊ２］が、所定の閾値「Ｔｈｒｅｓｈｏｌｄ」より上にあると規定されると、その後このトリプルが分析され、かつ最低確率を備えた結合が消去される。そのうえハードウェアの実現化は、まず三角形を確定する効率の良いソート機を企図している。ただしテスト条件の結果、外側の多角形上でのそれぞれ最短の間隔での三角形、または輪郭点のうち１番近い近隣点だけが有意である。このため配列原理を適用することによって演算を節減することができる。
【００６９】
図４は、選び出された中心の輪郭点の近隣にある輪郭点のリストデータが、適切なソート機構によってどのように読み出されるかを図解している。一時的に選び出された中心の輪郭点は「ＣＰ」で表されている。輪郭点は、サブピクセル精度で格納されており、画素ごとに最大１つの登録が存在する。このため上述の三角形は、近隣点を例えば時計回りで連続的に走査することによって生成することができる。数字１〜２４は、５×５の周辺域内での、リストデータを備えた輪郭点の読み出し順序を表現している。つまり輪郭点またはそのリストデータは、ピクセル内に提示した数字によるような順序で、中心点に対し最大２ピクセルの間隔での周辺域の画像領域から読み出され、かつ輪郭点のリストデータがこの順序に相応に読み出される。それに応じてまず「１」で表されたピクセルが読み出され、その後「２」で表されたピクセルが読み出され、そのように更に、この周辺域の最後のピクセル「２４」まで読み出される。つまり、中心点の周辺域の近隣の点だけが漸次的に読み出される。
【００７０】
このようなソート機構１７の実施形態は図５に示されている。アドレス指定のために、例えば輪郭点のインデックス（アドレス）のためのシフトレジスタが、デュアル・ポートＲＡＭ内で使用される。ピクセルに対し、輪郭点として肯定的な決定が与えられた場合は常に、この輪郭点が、すぐ後に続くアドレスをデュアル・ポートＲＡＭ内で取得し、このアドレスもまた、インデックス（アドレスの一部）としてシフトレジスタ内に送り込まれる。すぐ後に続く画素が輪郭点でない場合は、ゼロがシフトレジスタ内に登録される。ｎ×ｍ、例えば５×２４の長さを備えたシフトレジスタは、このため１２０のインデックスを保存することができる。輪郭点がたまにしかないことにより、少ないビット数、例えば６〜８ビットのワード幅で十分である。
【００７１】
中心の輪郭点の５×５周辺域内における輪郭点の分布に関する一例を図６が示している。記号「Ｉｎｄｅｘ」での登録は、当該のピクセルが輪郭点であることを表示している。局所的な５×５の周辺域は、既知のやり方において、相応のレジスタでの抽出によって作られる。つまりこのレジスタは、適切に接続されたマルチプレクサ１９の入力部２０を介し、レジスタ２３の出力部で図４に示した順序が生じるように読み出される。このプロセスは、中心点ＣＰがゼロとは異なる場合、つまり分析すべき近傍がレジスタセット内に表示され、点ＣＰが輪郭点である場合に、正確にスタートされる。
【００７２】
マルチプレクサ１９の出力値がゼロとは異なる場合は常に、インデックスが出力レジスタ２３に送られ、この出力レジスタは、直接的に、デュアル・ポートＲＡＭからデータをアドレス指定する。マルチプレクサ１９の出力値がゼロと異なるかどうかは、出力レジスタ２３に作用するコンパレータ２１によって確定される。
【００７３】
連続的に進行する輪郭検出プロセスからソート・プロセスを切り離すために、典型的には８〜１２の輪郭点のための更なるＦＩＦＯバッファまたはレジスタを、出力データフロー内に挿入することができ、この場合このＦＩＦＯバッファまたはレジスタは、近傍に属する輪郭点を何回か繰り返して読み出すこともでき、これによりソート・プロセスに必要な全ての輪郭点組合せを準備することができる。更に原則的には、このソート・プロセスを、例えば２つ以上のマルチプレクサを並列に接続することによる並列化によって、加速させることができる。
【００７４】
図６の例において示したインデックスを含むレイアウトは、以下に図７、図８、図９Ａ〜図９Ｃに基づき説明する、共通の輪郭に属する輪郭点の間のコネクタを計算するための計算例の周辺域に相応する。
【００７５】
図７には、まず中心の輪郭点２５および近隣の輪郭点２６の位置が、輪郭の起こりうる結合２７と共に、サブピクセル・ラスタにおいて示されている。その際、グラフの軸には、画素のインデックスが付されている。図８は、同じ点を画像データのオリジナル・ラスタにおいて示している。図８に基づき、オリジナル・ラスタにおいては、中心点と共に１つの輪郭に属する有意な近隣の輪郭点が、明らかにより不適切に認識され、グラフを形成する可能性があることが明らかになる。
【００７６】
この例では、コネクタが１／４ピクセルのサブピクセル精度で計算されている。この例は、簡単であるという理由から、相関的な結合確率に関する尺度としての間隔を用いて具体的に示されている。左の表（図９Ａ）には、上部に示した輪郭点配置のサブピクセル座標（カラムＸ、Ｙ）が示されている。この表は、中心点ＣＰで始まる。「Ｆｉｅｌｄ」で表されたカラムには、図６に示した周辺域に対する図４に基づく走査から明らかになるような輪郭点のサブピクセル座標が登録されている。つまりこの例では、デュアル・ポートＲＡＭ内で、以下の輪郭点順序がアドレス指定される：ＣＰ、７、９、１３、１８、１９、２２、２４、７。これに加え、中心点の周辺域の全ての輪郭点の主方向２９ならびに点方向３０が記入されている。
【００７７】
サブピクセル座標を基に、図９Ｂの表内でリストアップされているような、中心点に対する相対的な間隔［Ｘｒｅｌ，Ｙｒｅｌ］が計算される。これを基に再び中心点に対する間隔ｐが計算される。インデックス７、９、１３、１８、１９、２２、２４、７を備えたピクセルは多角形を形成しており、その多角形の中央に中心点ＣＰがある。多角形の辺［Ｘ＿Ｐｏｌｙ，Ｙ＿Ｐｏｌｙ］は、中心点への結合によって三角形を形成し、それは例えば三角形＜ＣＰ，「Ｆｉｅｌｄ」７，「Ｆｉｅｌｄ」９＞である。この三角形において１番長い辺は、長さが８，６０２サブピクセルであり、したがって長さ５，３８５および３，６０６の両方のほかの辺より長く、これによりこの１番長い辺は３つの輪郭点の中で最低の結合確率を持つ。このため１番長い辺が、結合すべき輪郭点のリストから消去される。この演算は、全ての三角形に対して実施される。その際、更に２つの点が消去され、つまり全部で３つの点が消去される。この選び捨てプロセスには、特にインデックス９、１８、および２４を備えた輪郭点が該当する。４つの選び捨てられていないコネクタが残り、その際、１つのコネクタが多角形の始まりと終わりを結合する。残っている輪郭点が図９Ｃの表にリストアップされている。その後、残っているコネクタまたは輪郭点に対し、選び捨て過程が繰り返される。この繰り返された選び捨ての際、更にまたインデックス１２を備えた輪郭点または図９Ｃの表内にリストアップされたの最初の輪郭点が消される。
【００７８】
このコネクタは、分析の最後に調べられるべきであり、その際、更に１つのコネクタが消される。その後、図７において３つのコネクタ２８が残り、このコネクタはリストデータ内に保存される。それに応じて、この例における計算の結果として、輪郭点としての中心点から更なる３つの残っている点に対するコネクタが、中心点が属する１つまたは複数の輪郭を表すことになる。それに応じてＳＮＮＣ７は、上で図７、図９Ａ〜図９Ｃに基づき説明したこのフィルタまたは選び捨て過程の実施によって、輪郭点リストからの輪郭点のどれが中心点と結合されているかという情報を取得する。
【００７９】
図７、図９Ａ〜図９Ｃに示した例では、結合確率に関する非常に簡単な分類器に基づく選び捨ての方法を、つまり輪郭点の互いに対する間隔にのみ依存する分類器を説明した。しかし輪郭点の間の有意な結合の認識は、分類器の計算のために輪郭点の更なる属性を用いる場合、更に著しく改善させることができる。ここでは特に、輪郭点の方向および／またはコントラストを使用することが考えられる。この方向は例えば、輪郭が決定されるべき画像データにおけるエッジに垂直な方向ベクトルであり得る。その際、簡略的に、可能な方向の数を少なくした方向情報、例えば８方向の可能な方向が、属性として輪郭点プロセッサ５によって確定および保存されてもよい。その際、コネクタの方向は、中心点ｉと近傍の外側の点ｊの１つとの間の結合ベクトルから明らかである。その後、この両方の方向提示に基づき、保存された平均的な点方向とコネクタとの間の角度αを確定することができる。その後、結合確率に関する分類器として、角度αの関数、例えばその正弦関数または余弦関数、および点の間隔の関数などを立てることができる。
【００８０】
更に、コントラストに富んだ輪郭をコントラストの乏しい輪郭に対して優先させるため、例えば結合要素を平均的な点コントラストの数値で乗算することが結合確率の分類のために使用されることにより、結合確率をコントラストの程度と結びつけることができる。これは特に、全体的にコントラストが乏しい場合または細い線の場合に有利である。
【００８１】
図１０は、コネクタを確定するためのＳＮＮＣ７の回路図を示している。この図に基づき、ＳＮＮＣ７の機能方法を更に詳しく説明することができる。ソート機構により、輪郭点を必要な順序でアドレス指定することができる。ＳＮＮＣのデータ入力部７１では、座標、コントラスト、および点方向についての情報［ｘ、ｙ、ｃｏｎｔ、ＤＩＲ］が存在しており、このデータが、３２ビットのワード幅でのレジスタ７２、７３、７４に読み込まれる。
【００８２】
こうして、以下に「Ｃａｌｃ  Ｐｃｏｎｎ」と称され、更に以下でもっと正確に説明される計算ユニット７５が、三角形の３つの輪郭点の間の結合確率を計算する。このために、中心点がアドレスデコードによって選び出される。図１０に示した例の場合、中心点のデータはレジスタ７４にロードされている。新たに入ってくる輪郭点は、両方のレジスタ７２および７３に読み込まれる。結合確率の３つの可能な組合せが、コンパレータ７６１、７６２、７６３、および後ろに接続されたデコーダ７７によって分析される。中心点と多角形上の両方の点の１つとの間の結合確率が最低の結合確率である場合、または中心点への結合がない場合、当該の結合は消去され、これは、中心点の近隣にある両方の輪郭点のうちのそれぞれの輪郭点が、出力部７８または７９で、ビットＥＮ＿ＣＬＫ＿ＲＧ１を設定されるか、ビットＥＮ＿ＣＬＫ＿ＲＧ２を設定されるかに応じて、当該の結合が消去される。考察された３つの点のインデックスは、データに並列に保存されている。消去されていない点のインデックスがシフトレジスタに伝送され、このために、中心点に対するインデックスの差が計算され、かつすぐ後に続くクロックで保存される。
【００８３】
計算ユニットＣａｌｃ  Ｐｃｏｎｎ７５１、７５２、７５３が、図５のレジスタ出力部２３によってアドレス指定された一連の輪郭点を、その属性と共に受け取り、かつ結合確率を計算し、かつ互いの間での結合における確率をコンパレータ７６１、７６２、７６３で比較し、かつデコーダ７７内でそれぞれの分析したトリプルに関して消去すべき結合を決定する。出力部では、結合の消去を制御する信号ＥＮ  ＣＬＫ  ＲＧ１およびＥＮ  ＣＬＫ  ＲＧ２が、輪郭点Ｐ１およびＰ２に対して供給される。続いて、更なるトリプルが分析される。十分な数のトリプルを処理した後、マーキングされていない結合が残り、結果としてこの結合がコネクタであり、このコネクタは、近隣の輪郭点のインデックス、および輪郭点ｉの、中心点ＣＰとの結合確率、ならびにすぐ後に続く近隣点ｉ＋１との結合確率を含んでいる。
【００８４】
ただし結合確率の計算の際に多義性が生じる可能性があり、この多義性は、二等辺三角形または正三角形によって現れる。形態学的欠陥（例えば輪郭における小さな三角形）を、複雑な論理なしで回避するため、分類器のコンパレータに変調を印加するための計算機構が加えられ得ることが有利であり、例えば、完全には規定どおりでないラスタの押し込みを生成する擬似確率幾何学的ノイズの形の変調を印加する。このために、表を介して周縁のノイズ部分を加え、例えば中心点に対する相対的な間隔Δｘおよび／またはΔｙに関する座標差に対し、ピクセル間隔の１０％を加える。
【００８５】
図１１は、デジタル画像の別の部位の画像データから取得された、サブピクセル・ラスタにおける近隣の輪郭点の更なる配置を示している。この例の場合、図７に示した周辺域とは異なり、２つだけの有意なコネクタ２８が、起こりうる結合２７からの選び捨てによって確定されている。
【００８６】
図１２は、輪郭点と、選び捨てによって確定された結合とを備えた画像の比較的大きな部分を表している。見易くするために結合２８だけが示されている。この図から分かるように、互いに並んだコネクタ２８は、デジタル画像内での輪郭の進路を明らかにする。図１２には、２つの部分３１、３２が円によってマーキングされている。部分３１は、中心点から出る分岐を備えた、図７に示した周辺域から確定された３つのコネクタ２８を特徴づけている。部分３２は、図１１に示した周辺域のコネクタ２８を特徴づけている。破線の円は、図７に記入された全ての輪郭点の周辺域による領域を表示している。その際、図１２に基づき、分岐が発生する場合より図１１に示した連続した輪郭の場合の方が頻繁に起こることが明らかになる。
【００８７】
そのうえ図１２に基づき、選び捨てのこの簡単な方法が、少しのアーチファクトしか含まない輪郭線の認識に至ることが明らかになる。そのほかの点では、例えば更にまだ分離している短い線または輪郭線から出ている短い線が予想されるであろう。図１２に示した画像では、そのような短い線３３は１つしか認識され得ない。
【００８８】
図１３は、ＳＮＮＣ７によって、更なる処理のために好ましくは更なるデュアル・ポートＲＡＭ内に保存されたデータのデータ構造を示しており、このデータは、コネクタ、またはそれぞれの点の更なる輪郭点への結合についての情報を含んでいる。近隣点との結合についての情報は、以下に「ＬｉｎｋＩｎｆｏ」とも称される。
【００８９】
中心点ｉのインデックスがアドレスを形成し、このアドレスの下で、ＬｉｎｋＩｎｆｏがデュアル・ポートＲＡＭ内に保存される（更に下を参照）。許可された輪郭点（ＥＮ＝１）がそれぞれ、更なるインデックスｊ（ポインタ）を供給し、この差
ＬＩＮＫ［ｎ］＝ｊｎ−ｉ
が、ＬＩＮＫとして表される。ＬＩＮＫを把握した上で、中心点により、輪郭点リスト内の全ての近隣点からアドレス指定することができる。ＳＮＮＣの構造に基づき、中心点ごとに最大４つのＬＩＮＫが発生する可能性があり、５つ以上の近隣点は、複数の近傍に分解される。マスクＭＡＳＫは、当該のＬＩＮＫが設定されているか否かを提示する。これに並行して、輪郭点プロセッサによって同じメモリ内に属性が保存されており、このため座標ならびにグレー値および必要の際には色情報が用意されている。
【００９０】
以下に、図１に概略的に示した形態学的フィルタ１１をより詳しく説明する。
【００９１】
こうして一義的に結合された輪郭点は、まだ対象として読み出すことはできず、なぜなら２つの前提条件が欠けているからである。第一に、輪郭のスタート点およびエンド点がまだ定義されておらず、第二に、対象セグメント化のためのリソースを不要に害するであろう多数のアーチファクトがまだ存在している。このため、点をコネクタに基づき対象へと１つにまとめる前に、近隣の点の形態が、形態学的フィルタ１１によって調べられる。つまり形態学的フィルタ１１は、コネクタを含む輪郭点リストを、特性の少なくとも１つに関してフィルタリングするよう構成されており：
・最高３つの輪郭点による鎖での輪郭点を消去する、
・最高３つの輪郭点を備えており、より長い鎖と片側で結合されている鎖にのみ属する輪郭点を消去する、
・鎖のスタート点およびエンド点が共に全体の一部をなす輪郭点を形成する輪郭点を、輪郭点リスト内で特徴づける、
・少なくとも２つの鎖の分岐点を形成する輪郭点を、輪郭点リスト内で特徴づける、
・同時発生を補正する、および
・二重のリンクを実施する。
【００９２】
これらの関数の実施のためにまず、フィルタ１１内で実行される、以下に「ＲａｎｋＦｉｌｔｅｒ」と称する関数が用いられる。この関数によって、輪郭点のためのランク・ベクトルが形成される。このために、図１３に示したデータ構造の輪郭点リストをコネクタ構造と共に読み出し、かつそれぞれ中心点から出てコネクタを介して、全ての近隣点のコネクタ構造を読み込み、かつ近隣点および中心点自体の分岐数を内容として含むランク・ベクトルを生成する。つまりこのＲａｎｋＦｉｌｔｅｒは、１つの輪郭点から出る結合の数を決定し、ここではマスクＭＡＳＫの設定されたビットの総和を形成することによって決定される。このため４回の分岐はランク４、ＭＡＳＫ＝１１１１Ｂを有するであろうし、例えば図１１に示した中心点のような鎖要素はランク２および一般的にＭＡＳＫ＝００１１Ｂを有するであろう。
【００９３】
ＲａｎｋＦｉｌｔｅｒは、ＭＡＳＫを介して許可された近隣のＬＩＮＫをアドレス指定し、かつこれにより近傍のそれぞれの輪郭点に対してランクを決定する。そのように確定されたランクから、近隣点の分岐数についての構造情報を含むランク・ベクトルが形成される。
【００９４】
点の連結が、全ての方向から呼び出され得るので、既に読み取られた点のためのマーキングによる二重のリンクが有意義である。このために、アドレス指定された近隣点の４つの可能なポジションのうちのどのポジションで、出発点への逆のリンクが保存されているかを提示するリンク・アドレスＬｉｎｋＡｄｒが生成される。ＬｉｎｋＡｄｒは、形態学的フィルタリングの実施後に保存される。
【００９５】
近隣点へのリンクおよび中心点に戻る逆のリンクのシーケンシャルな順番が、常にポインタ差ゼロを生じさせるので、相対的に簡単に、コンパレータを介してこのアドレスを見つけることができる。結果的に、近隣の結合された輪郭点のインデックスを見つけること、および連結された輪郭点を高速で読み出すことを、１回だけのアクセスで可能にする構造が得られる。
【００９６】
ランク・フィルタ３５の、好ましくは形態学的フィルタ１１の構成要素としての特に有利な実現化が図１４に示されている。ランク・フィルタ３５によって、デュアル・ポートＲＡＭ９から、図１３にも示したようなデータ構造３７を基に、まずデュアル・ポートＲＡＭ内のアドレスＰｔｒ［０］を備えた中心点のＬｉｎｋＩｎｆｏが、ランク・フィルタの入力レジスタ内に読み取られる。続いてＬＩＮＫ１〜４がマルチプレクサ３９を介してアドレス指定され、アドレスＰｔｒ［１．．４］が加算によって計算され、かつ順番に呼び出される。マスクＭＡＳＫの割り当てられたビット上でゼロによって特徴づけられた必要ないＬＩＮＫは飛ばすことができる。相対的に保存されたＬＩＮＫに対し、中心点のポインタ・アドレスが加算器４５によって加算され、続いてリストが直接的にアドレス指定され得る。このやり方で、ＬｉｎｋＩｎｆｏが読み込まれる。形態学的フィルタ１１または実行されたランク・フィルタ３５の、接続されているコンパレータ４０、４１、４２、４３が、Ｐｔｒ［ｉ］でアドレス指定された輪郭点のＬＩＮＫを、中心点のＬＩＮＫ［ｉ］と比較する。４（３）つのコンパレータが、当該のＬＩＮＫを比較する。ペアの１つが互いに相補的である場合に当該のコンパレータ４０、４１、４２、４３が信号ＣＭＰ＿ＬＩＮＫ［１．．４］を生成することにより、これを基にデコーダ４４によってＬｉｎｋＡｄｒがデコードされ得る。
【００９７】
同じプロセス内で、ランクＲＡＮＫ［１．．４］も確定することができ、かつマスク・ビットを加算器４６で加算することによりランク・ベクトル＜ＲＡＮＫ［１］，ＲＡＮＫ［２］，ＲＡＮＫ［３］，ＲＡＮＫ［４］＞へと編成することができる。このランク・ベクトルは、形態学的フィルタ内で、それまで有効と判断されていた結合の更なる許可についての二分決定で処理され、かつ構造ＭＡＳＫ内に保存される。
【００９８】
更に形態学的フィルタにより、上述のように結合された輪郭における欠陥が取り除かれ、この欠陥は、特に高い解像度および／または感度の際、一連の小さなアーチファクトを発生させ、このアーチファクトは、その配置に基づき対象へとセグメント化されるであろう。これは以降の処理ステップの能率のために不利である。このため形態学的フィルタによって、既に対象セグメント化の前に、比較的小さな欠陥を取り除く。
【００９９】
以下に、形態学的フィルタ１１の関数の作動方法を説明する。この関数は、以下に「ＭｏｒｐｈＦｉｌｔｅｒ」と称する。ランクおよびＬｉｎｋＡｄｒの計算後、単純なフィルタを実現することができる。これに関し、まず１〜２つの輪郭点を備えた邪魔な小さい構造「アペンディクス」を消去する。そのようなアペンディクスは、例えば図１２中の短い線３３である。このような構造は、その近隣点（括弧で括られた）の分岐数で認識され、例えば以下のランク・ベクトル：＜１，３，０，０＞で認識される。このランク・ベクトルを備えた輪郭点は、ランク３の特異点を介して主輪郭と結合されている。この点は消去されるべきであり、主輪郭の特異性または分岐部位はランク２に戻されるべきである。この演算は、以下のメイプル・プログラムコードによって具体的に示すことができる：
ｉｆ  ＲａｎｋＶｅｃｔｏｒ＝［１，３，０，０］  ｔｈｅｎ
ＭＡＳＫ［Ｐｔｒ［１］，ＬｉｎｋＡｄｒ［Ｐｔｒ［０］，１］］：＝０：    ＭＡＳＫ［Ｐｔｒ［０］，１］：＝０：
ＭＡＳＫ［Ｐｔｒ［０］，２］：＝０：  ｅｎｄ：
【０１００】
中心点は、ランク１を有しており、かつＲａｎｋＶｅｃｔｏｒ内の第１の桁である。中心点のＬＩＮＫ［１］は、ランク３を備えた輪郭点を指している。この場合にＬｉｎｋＡｄｒ［Ｐｔｒ［０］，１］は、ランク３を備えた輪郭点上のどこで中心点への逆のＬＩＮＫを見つけることができるかを提示している。Ｐｔｒ［１］は、ランク３を備えた輪郭点をアドレス指定し、つまり演算
ＭＡＳＫ［Ｐｔｒ［１］，ＬｉｎｋＡｄｒ［Ｐｔｒ［０］，１］］：＝０：
が、孤立した輪郭点へのＬＩＮＫを消去し、ランクを３から２に減らす。このため特異点はその後、連結されたリストの通常の構成要素のように振る舞い、つまり分岐を発生させない。以降の処理のために２つの対象が発生することはほとんどなく、２つの有効な比較的長い対象を１つの対象へと統合することは省略される。
【０１０１】
更なる例は、ランク・ベクトル＜２，３，１，０＞を備えた輪郭点である。このランク・ベクトルは、２つの輪郭点を備えたアペンディクスである。両方の輪郭点は、ランク２の結合および特異点を介して主輪郭と結合しているか、またはランク３の分岐と結合している。このようなアペンディクスは、以下のメイプル・コードに類似する関数を実施するフィルタによって消去することができる。
ｉｆ  ＲａｎｋＶｅｃｔｏｒ＝［２，３，１，０］  ｔｈｅｎ
ｉｆ    ＬｉｎｋＡｄｒ［Ｐｔｒ［２］，１］＝１  ｔｈｅｎ  Ｌ：＝２
ｅｌｓｅ  Ｌ：＝１：  ｅｎｄ：
ＭＡＳＫ［Ｐｔｒ［１］，ＬｉｎｋＡｄｒ［Ｐｔｒ［０］，Ｌ］］：＝０：ＭＡＳＫ［Ｐｔｒ［０］，１］：＝０：
ＭＡＳＫ［Ｐｔｒ［０］，２］：＝０：ＭＡＳＫ［Ｐｔｒ［２］，１］：＝０：
ｅｎｄ：
【０１０２】
ランク１を備えたエッジ点は、ＬＩＮＫ［２］、ＬｉｎｋＡｄｒ［Ｐｔｒ［２］，１］であり、Ｐｔｒ［０］（これはエッジから見て次の点である）への逆のＬＩＮＫを示している。Ｐｔｒ［０］がランク２を有しているので、別のＬＩＮＫ（Ｌ）が、ランク３を備えた主輪郭の特異点Ｐｔｒ［１］を示さなければならない。したがって関数ＭＡＳＫ［Ｐｔｒ［１］，ＬｉｎｋＡｄｒ［Ｐｔｒ［０］，Ｌ］］：＝０：が、Ｐｔｒ［１］のＰｔｒ［０］へのＬＩＮＫを消去し、かつランクを３から２に減らし、この結合を消去する。
【０１０３】
これに類似して、取り違え＜２，１，３，０＞もフィルタリングすることができる。
【０１０４】
関数「ＭｏｒｐｈＦｉｌｔｅｒ」は、ランク・ベクトルの分析により、セグメント化のために重要な更なる情報を供給することができる：
・チェーンのスタート点およびエンド点の分類、
・結合された特異点の分類、
・ランク３以上の特異点の分類。
【０１０５】
このために、ランク・ベクトルを表またはブール論理を介して目的関数にマッピングする。これは、輪郭点リストのＬｉｎｋＩｎｆｏ内で、相応のビットの設定によってマーキングされる。これに関し、ＭｏｒｐｈＦｉｌｔｅｒによるフィルタリングの後に、図１５に示したコネクタに関するデータ構造が示されることが特に有利である。ランク２の輪郭点に対しては、最大３つのＬＩＮＫが必要とされ、なぜならアペンディクスからの切り離しはランク３の点に対してのみ許可されるからである。
【０１０６】
図１３でのビットに対して追加されて含まれているビットは以下を意味する：
Ｃ：    ｃｏｎｔｉｎｕｅ（セグメント化のための１ビット）、
Ｓ：    スタート点／エンド点（１ビット）、
ＭＡＳＫ１：    ＭＡＳＫのビット０〜２に相応、
ＬｉｎｋＡｄｒ：    上述のＬｉｎｋＡｄｒ［０〜２］に相応しており、４つ目は必要ない。
【０１０７】
情報を後で読み取る際、ＭＡＳＫのランク（ランク＝２）がデコードされることにより、図１５に示した書式が認識される。
【０１０８】
ランク３以上を備えた特異点は、図１６に示したデータ構造でコード化することができる。これに関し、登録ＣＯＮＮ３３は、ランク３または４の特異点の結合に関するコネクタ・マトリクスを表している。情報を後で読み取る際、ＭＡＳＫのランク（ランク＞２）がデコードされることにより、図１６に示した書式が認識される。
【０１０９】
この追加情報は、セグメント化の時点で使用される。このためＭｏｒｐｈＦｉｌｔｅｒは、この構造をＲＡＭ内に保存する。
【０１１０】
このように準備された輪郭点リストの情報は、メモリから直接的に、配列された順序で、以下に「チェーン」とも称される配列された一連の輪郭点として読み出すことができ、このため相次ぐリスト登録は、輪郭に沿った相次ぐ輪郭点に属している。
【０１１１】
その際、チェーンは、以下にＧｅｔＮｅｘｔＣＰと称される構造によって確定される。ＧｅｔＮｅｘｔＣＰは、中心点のＬｉｎｋＩｎｆｏを、ＭｏｒｐｈＦｉｌｔｅｒに対して遅延されたプロセス内で読み取る。この遅延は、典型的には８カラムであり、ただしより大きなメモリの場合は、より大きく選択してもよい。ＣｈａｉｎＲｅａｄＯｕｔは、入ってくる輪郭点を、スタート点およびエンド点に基づきスキャンする。スタート点およびエンド点は、図１５に示したデータ構造の場合、ランク（ＭＡＳＫ）＝２およびＳ＝１という特徴を有する。
【０１１２】
そのような点が見つけ出された場合、両方の近隣点のＬｉｎｋＩｎｆｏが評価され、特異点が探索される（ランク１、または３、４）。Ｓ＝１を備えた近隣点が１つしか見つけられない場合、この近隣点がスタート点として判定される。このスタート点は、チェーンの第１の代表点を形成する。更に次の点へのリンクを生成する。チェーンの全ての要素が新たなセグメント番号を取得し、このセグメント番号は、結合された点集合の全ての更なる代表点にも受け継がれる。２つの特異点が近隣にある場合、第１の見つけられた点が使用され、残りの点は、自動的に明らかである。「Ｃｏｎｔｉｎｕｅ」ビットが設定されている場合、チェーン構成が続行される。
【０１１３】
ＧｅｔＮｅｘｔＣＰは、まずＭＡＳＫに基づき、デコーダ内で保管された表によって定義される認識範囲を確定する。この表は、アクセスされ得る近隣点の数およびポジションを供給する。輪郭点リスト内のＬｉｎｋＩｎｆｏを基に、近隣点へのポインタおよび両方のＬＩＮＫのアドレスを計算する。
【０１１４】
ＧｅｔＮｅｘｔＣＰ構造５０の可能な構成が、図１７に示されている。ＭＡＳＫ、Ｃ、ＭＡＳＫ１、Ｓ、およびＬｉｎｋＡｄｒといった登録を備えており、より正確には図１５に示したデータ構造に相応するデータ構造５１が、チェーンへのリンクを制御する。デコーダ５２内には前述の表が保管されている。
【０１１５】
スタート点（Ｓ＝１）がアドレス指定された場合、このスタート点はランク２を有しており、したがって２つの近隣点を有している。この場合に、デコーダ５２は両方の可能なリンクを選び出し、ランク２に相応しない近隣点とのリンクをデコードし、かつこの輪郭点に対し、値ＰＴＲ＿Ｓｔａｒｔを生成することによってチェーンのスタート点を設定する。もう１つのリンクは、マルチプレクサ５３および加算器５４を介して、新たなポインタＰＴＲ＿ｎｅｗとして次へ渡される。
【０１１６】
Ｓ＝０が見つかる場合、つまり輪郭点がスタート点またはエンド点ではない場合は、リンクを１つだけ選び出す。この選び出しは、マスク・ビットＭＡＳＫ１を介して制御される。新たなポインタＰＴＲ＿ｎｅｗが生成されることにより、自動的に、属するマスク・ビットの設定が戻され、これにより同じ輪郭点が繰り返しアドレス指定されることはない。リンクされた輪郭点は、セグメント番号を割り振られる。この状態以降、ＬｉｎｋＩｎｆｏはもう必要なくなるので、これに対してデータワードのＬｏｗ部分が使用され得る。
【０１１７】
このプロセス中、ポインタ・アドレスは常に監視されている。信号ｏｕｔ＿ｏｆ＿ｒａｎｇｅがくると、つまり許可されたインデックスが、所定の下限または上限を出ると、プロセスが中断される。相応の輪郭点にＣビット（ｃｏｎｔｉｎｕｅ）が設定され、かつセグメント番号が保存される。読み出しを繰り返した際にポインタが許可された領域内にある場合は、プロセスを続行することができる。プロセスの終わりには、各セグメントに対し配列された一連のポインタが生じている。相応の輪郭点属性は、ポインタに相関して保存されているので、属性を直接的に読み出すことができる。
【０１１８】
更に、チェーンの処理の際には以下の例外的な場合が生じ得る：
１．チェーンの両方のスタート点が処理され、これにより異なってインデックスされた２つのセグメントがぶつかる（同時発生）、
２．対象がスタート点を有していない（例えば円または閉じた輪郭の場合）か、またはスタート点が、その時点の走査ポジションよりずっと先にあり、そのためスタート点が捕捉され得ないので、どのスタート点も処理されない、
３．輪郭が、画像の境界線と交差している（エッジ点）。
【０１１９】
第１の場合には、２つの異なるセグメント番号を備えたチェーンが互いに出くわし、ただしこれらのチェーンは互いの中には進行せず、なぜならマスク・ビットがそれを阻止するからである。ランク＝２で中断が生じるというテストによって、装置はそれがいわゆる同時発生であることを認識し得る。同時発生点の当該のランク２は、セグメントを互いに結合する特異点のように扱われ、違いは、この場合にだけ対象が１つしか存在しないことである。
【０１２０】
第２の場合は、チェーンの読み出し後に、これまで処理されていないタイプ＜２，２，２，ｘ＞の近傍を分析するという更なるテストを実施し、かつその後、スタート点を発生させる。更なる処理は上述のように行われる。
【０１２１】
相次ぐ帯状部の間に発生し得るエッジ点は、ランク２を備えた同時発生点のように扱われ、続いて相互参照される。
【０１２２】
輪郭点プロセッサは、第１のポートを介して、属性を付与した輪郭点の進行するデータフローを供給し、最悪の場合、非常に細かく解像されたグレー値画像では、ピクセルの約２０〜２５％が輪郭点として保存される。
【０１２３】
以下に、そのような量の輪郭点も処理し得る、１ｋ×３６ビットの通常の小さなデュアル・ポートＲＡＭに関する実現化を説明する。このデュアル・ポートＲＡＭにより、５１２の輪郭点を備えた画像抽出部を、付加情報および属性も含めて一時記憶させることができ、これは、例においては最小で７０×２６ピクセルの大きさのピクセルブロックに相当する。輪郭点プロセッサは、画像データを複数の帯状部において読み出し、この帯状部はそれぞれ１ピクセルより大きい幅、好ましくは少なくとも１６ピクセルの幅、特に好ましくは２６または３２ピクセルの幅を有している。以下の例では、２６ピクセルの高さの帯状部が、蛇行状に画像幅全体に亘って読み取られ、続いて次の帯状部が続く。このデータは、リストとして保存され、属性において座標が保持される。
【０１２４】
輪郭点プロセッサ５は、輪郭点の保存によって開始される。５カラムが入ってくると、ＳＮＮＣ７が働きを開始することができ、輪郭点プロセッサ５はその間更に進行している。
【０１２５】
最大のポインタ・アドレスが厳密に計算され得る。これに関し、各カラム・ジャンプの際にアドレス・インデックスが保存され、かつ５カラム遅延して読み出され、実際には、メモリが十分に大きいので、−３２などの一定のオフセットでも十分である。ＳＮＮＣ７は、デュアル・ポートＲＡＭからまず５×５の近傍を読み出し、かつ当該の輪郭点の属性をレジスタセット内に保存する。
【０１２６】
形態学的フィルタ１１のプロセスＭｏｒｐｈＦｉｌｔｅｒは、できあがって保存およびフィルタリングされたリンクを必要とし、したがってＳＮＮＣ７によるデータ処理に対して３カラムの安全間隔が保たれる。
【０１２７】
これに対しセグメント化プロセスはもっと大きな間隔を必要とする。その理由は、より計算集約的な輪郭追跡方法だからである。輪郭の面倒な組立てを回避するには、輪郭をできるだけ大きい長さで欠陥なくたどり得るべきである。このための典型的な値は８カラムである。その前の演算から、スタート点または設定されたＣｏｎｔｉｎｕｅビットが見つかった場合は常に、ＧｅｔＮｅｘｔＣＰ構造５０が駆動される。
【０１２８】
このための制御は、メモリ帯域幅を節約するため、デュアル・ポートＲＡＭではなく、分離された単純なシフトレジスタ構造を介して実現されるのが有用であろう。
【０１２９】
ＳＮＮＣは、輪郭点プロセッサ５が保存した後、約３カラムの処理後にそのプロセスを完了する。したがってＭｏｒｐｈＦｉｌｔｅｒのために必要な情報は、輪郭点プロセッサ５による約６カラムの処理の後に提供される。
【０１３０】
こうして前処理された輪郭データは、ＩＥＢＶＳ１の主メモリ内に書き戻され、続いてマイクロコントローラによってフォーマットされ、かつ以降の処理プロセスのために引き継がれ得る。
【０１３１】
以下に、例えば画像データ内のノイズによって発生し得るアーチファクトを認識し、かつ相応のチェーンを除去する、チェーンの更なるフィルタリングを説明する。
【０１３２】
これに関しチェーンは、スタート点から始まってエンド点に達する配列された一連の輪郭点の形を有しており、その際、前に接続されたプロセスによって属性が割り振られている。コントラストのほかに走査方向も属性として保存されている。
【０１３３】
チェーンの有意性を評価するには、コントラスト割付を計算することが有意義である。コントラスト割付の数値が所与の閾値を超えている場合、チェーンは有意として評価される。このために、個々の輪郭点のコントラスト値を輪郭点のカウント方向に相応に累算する。図１８には、点Ｐ０〜Ｐ８によるチェーン・セグメントが示されており、その走査方向が矢印によって特徴づけられている。
【０１３４】
各輪郭点には、図１９に示した４つの走査方向Ｄｉｒ０、Ｄｉｒ１、Ｄｉｒ２、Ｄｉｒ３の１つが割り当てられている。それぞれの走査方向に沿って、局所的に最大限のコントラストが生じる。以下の表１は、輪郭点およびその走査方向をリストアップしており、そのほかのカラムは後で説明する。
【０１３５】
【表１】
2010503936.tif 000006
【０１３６】
表２には、チェーンの輪郭点の走査方向Ｄｉｒ０〜Ｄｉｒ３と、方向ベクトル［Δｘ，Δｙ］との間の差角が評価されている。
【０１３７】
【表２】
2010503936.tif 000007
【０１３８】
ここで使用した、図１８に示したように左上に座標原点を備えた座標系に関し、走査方向Ｄｉｒ０〜Ｄｉｒ３は：
Ｄｉｒ０＝［１，０］、
Ｄｉｒ１＝［１，−１］、
Ｄｉｒ２＝［０，−１］、
Ｄｉｒ３＝［−１，−１］、
として生じる。
【０１３９】
表２内のカラム「カウント方向」は、その時点の輪郭点のコントラスト貢献が正のカウント方向になるために満たすべき条件を説明している。チェーンの書式設定の際、コントラスト割付がハードウェアによって累算され、これはまず、方向Ｄｉｒおよびベクトル［Δｘ，Δｙ］＝［Ｐｉ＋１  −Ｐｉ］から、正負符号を計算することによって行われる。各輪郭点に対し、Δｘ、Δｙ、Δｘ＋Δｙ、およびΔｘ−Δｙの正負符号を決定し、かつその正負符号を表２に基づく条件と結びつける。表１には、図１８に基づくチェーン・セグメントに関し、Δｘ、Δｙ、および確定されたカウント方向が登録されている。最後の点Ｐ８に対しては方向ベクトル［Δｘ，Δｙ］が定義されておらず、このためＰ７の方向ベクトルが使用される。
【０１４０】
図２０は、輪郭または帰属のチェーンのコントラスト割付を決定するためのコントラスト累算器８０のハードウェアの実現化を示している。２つのコンパレータ８１、８２および２つの加算器８３、８４から成る第１のステージは、項Δｘ、Δｙ、Δｘ＋Δｙ、およびΔｘ−Δｙの正負符号を決定する。小さなローカルメモリ８５（ＬＵＴ）または等価論理回路が、有意な正負符号を、その時々の輪郭点の方向Ｄｉｒ０、．．．、Ｄｉｒ３に相応にデコードする。続いて累算器８６内で、コントラスト値Ｃｏｎｔｉが正負符号方向に加算され、これにより輪郭のエンド点では、累算器８６により、個々のコントラスト値の総和としてのコントラスト割付Σｃｏｎｔを取り出すことができ、かつ輪郭の属性として保存することができる。このためコントラスト割付Σｃｏｎｔは、輪郭から見た左右のグレー値および／または色度の差の積分に対する優れた近似を示しており、したがって輪郭要素の重要性を表している。
【０１４１】
このコントラスト割付は、引き続きアーチファクトのフィルタリングのためのチェーン・フィルタ内で使用される。このフィルタ内では更に、チェーン処理によって既に知られているスタート点およびエンド点の度数ならびにチェーン上の輪郭点の数が使用される。これらの特徴はチェーン属性と称され、分類される。チェーン・フィルタの分類器は、前述の特徴に基づき、その時々のチェーン・セグメントが有意義な構造であるか、またはノイズなどの理由で発生したアーチファクトであるかを決定するという課題を有している。引き続き、更なる処理ステップにおけるデータ・ボリュームを減らすため、このアーチファクトまたは帰属のチェーンが消去される。
【０１４２】
表３は、ノイズを抱えたチェーンを抑制するための簡単な分類器の条件をリストアップしている。ここに記載した条件を満たす全てのチェーン・セグメントは、欠陥として分類および消去される。
【０１４３】
総括的なコントラストで表された組合せに対してそれぞれ、長さおよびコントラスト割付から成る関数が計算され、その後、それぞれのチェーンを、位相幾何学的フィルタ内で更に処理し得るように量子化する。
【０１４４】
【表３】
2010503936.tif 000008
【０１４５】
第１の条件によって、輪郭の長さが所定の値より小さく、ここでは特に１０ピクセルより小さく、その際、輪郭のスタート点もエンド点も度数１を有するチェーンが選び捨てられる。それに応じて、ここでは非常に短い孤立した輪郭が存在している。
【０１４６】
第２行および第３行に基づく条件では、同様に小さな輪郭が除去され、この場合は輪郭の一端が更なる輪郭と結合している。それに応じて、ここでは別の輪郭での短い分岐が問題となる。
【０１４７】
チェーンのスタート点とエンド点が同一である場合、このチェーンは、例えば円のような閉じた曲線を表している。このような曲線が小さすぎる場合、その曲線は、表の第４の条件に基づき除去され、その際、特にここでもまた最高で１０ピクセルの広がりをもつ輪郭のチェーンが消去される。
【０１４８】
最後の４つの条件は、コントラスト絶対値を総和した輪郭点のコントラスト割付が３２０より小さい輪郭に関する。この例で、コントラストの有意性を評価する際に輪郭の長さも一緒に考慮に入れ得ることが有利であると判明する。コントラストの弱い輪郭が比較的長い場合、コントラストが弱いにもかかわらず、コントラストを累算した数値は閾値を超えることができ、かつこの輪郭または帰属のチェーンは有意と評価することができ、選び捨てることはできない。
【０１４９】
図２１は、画像データのセグメント化までの画像処理のための、上述のプロセスの位相位置およびメモリ要求量を示している。メモリ全体６０は、輪郭点を確定するためのメモリ領域６１と、ＳＮＮＣ７によって使用されるメモリ領域６２と、形態学的フィルタ１１のためのメモリ領域６３と、セグメント化のための明らかにより大きなメモリ領域６４とに区分けされている。その際、１つの輪郭に属する輪郭点の間の結合を確定するためのハードウェア・ユニットとしてのＳＮＮＣ７には、１つまたは複数の画像メモリは別として、輪郭を描いている対象へと画像データを処理するためのメモリ全体のうち最高２０％の大きさのメモリまたはメモリ領域が割り当てられている。
【０１５０】
以下に、輪郭の一部を輪郭点と共に示している図２２および図２３に基づき、どのように、対象セグメント化の構成要素として確定された輪郭点データを基に、輪郭の頂点を決定するかを説明する。輪郭点２６を備えた輪郭２６の一部が示されている。図１に示した基本構成のセグメント化ユニット１３によって実施された、輪郭１６の曲率、特に頂点の決定のための方法は、輪郭１６の輪郭点２６の１つの点ｐに対し、点（ｐ−，ｐ，ｐ＋）によるトリプルを形成することを基礎とし、その際、点ｐ−、ｐ＋は、輪郭に沿った両方向において点ｐから間隔をあけた輪郭点を表している。
【０１５１】
図２２に示した例でのような、湾曲して延びる輪郭１６の場合、これらの点（ｐ−，ｐ，ｐ＋）は、長さａ、ｂ、ｃの辺による三角形を形成している。
【０１５２】
これらの点に対し、条件
（ｉ）ｄ２ｍｉｎ≦｜ｐ−ｐ＋｜２≦ｄ２ｍａｘ、
（ｉｉ）ｄ２ｍｉｎ≦｜ｐ−ｐ−｜２≦ｄ２ｍａｘ、
および
（ｉｉｉ）α≦αｍａｘ
が満たされるかどうかを、所定のパラメータとしてのｄ２ｍｉｎ、ｄ２ｍａｘ、およびαｍａｘでテストする。開き角度αは以下によって与えられ、
【０１５３】
【数４】
2010503936.tif 000009
この場合、ａは点ｐとｐ＋の間隔を表し、ｂは点ｐとｐ−の間隔を表し、かつｃは点ｐ＋とｐ−の間隔を表している。図２２に基づき、１８０°に近い非常に大きな角度αの場合は、どちらかと言えば、点ｐが２つの直線セグメントの間の頂点であると予測すべきでないことが分かる。輪郭での非常に小さな曲率が既に角として解釈されることを回避するため、角度αｍａｘを相応に選択することができる。実際にはたいてい１６０°より小さい角度、例えばαｍａｘ＝１５０°が適している。
【０１５４】
条件（ｉ）〜（ｉｉｉ）が、点ｐに１番近い近隣点に対して、その後、点ｐに２番目に近い近隣点に対してテストされ、そのように更に次々にテストされる。その際、点（ｐ−，ｐ，ｐ＋）のトリプルに関し、条件（ｉ）、（ｉｉ）、（ｉｉｉ）の１つが満たされない場合、このテストは中断される。条件（ｉ）〜（ｉｉｉ）を満たす輪郭点ｐでのトリプルの開き角度αのうち、最小の開き角度が選び出され、かつ点ｐに割り当てられる。
【０１５５】
条件（ｉ）〜（ｉｉｉ）のテストが中断されると、輪郭１６に沿った次の近隣点が点ｐとして選び出され、かつこの方法が繰り返される。中断は、１つにはトリプルに対して条件（ｉ）〜（ｉｉｉ）が満たされない場合、または所定の数の近隣の輪郭点２６が調べられた場合に行われ得る。後者の場合には、点ｐの両側の７つの点２６でのトリプルを調べた後でテストが中断されることが好ましい。要求に応じて、調べるべきトリプルの最大数をより少なく定めることもできる。
【０１５６】
所与の輪郭点ｐに対し、条件（ｉ）〜（ｉｉｉ）を満たすトリプルを確定できない場合、この点は最初から選び捨てられ、かつ頂点の決定の際にはもう考慮されない。
【０１５７】
点ｐに対し、条件（ｉ）、（ｉｉ）、および（ｉｉｉ）を満たし、かつより小さな開き角度α’を有する近隣の点ｐ’が存在する場合、第２の過程において更なる選び捨てが行われる。これは図２３に示されている。示した例の場合、特に、点ｐ’でのトリプルの開き角度α’が点ｐでのトリプルの開き角度αより小さい。この第２の過程によって、対象の角を表している強く湾曲した輪郭領域に、密に近接する複数の頂点が確定されることが回避される。
【産業上の利用可能性】
【０１５８】
上述のような本発明は、パターン認識を実現するため、例えばコンパクトな装置内で実行することができる。とりわけ、このやり方で画像データ内のラスタまたは入力フィールドを変形に関係なく認識することができ、かつ割り当てることができる。これは例えばハンディな装置で、記入済みの宝くじ券のような申込用紙を高速で認識および評価することを可能にする。認識は、仮に申込用紙が折れ目または湾曲を有していてさえ、仮に画像が例えばハンドスキャナによって角度をあけて記録され、かつ相応に歪められているとしても、うまくいく。記入済みの申込用紙の認識は特に本発明に適しており、なぜなら申込用紙の所定の部位のデータが登録され、これにより簡単な認識を行うことができ、それどころか費用のかかるソフトウェアにサポートされた評価なしで行うことができる。ここでは完全にハードウェアの形で、パイプライン処理および対象セグメント化によって、そうでなければ、例えば宝くじ券上のラスタのようなパターンの、非常に複雑な割当ておよび識別を実現することができる。
【０１５９】
本発明が上述の例示的実施形態に制限されるのではなく、むしろ多種多様なやり方において変形可能であることは当業者には明らかである。特に、例示的実施形態の特徴を互いに組み合わせることもできる。
【図１】
2010503936.tif 000012
【図２】
2010503936.tif 000013
【図３】
2010503936.tif 000014
【図４】
2010503936.tif 000015
【図５】
2010503936.tif 000016
【図６】
2010503936.tif 000017
【図７】
2010503936.tif 000018
【図８】
2010503936.tif 000019
【図９】
2010503936.tif 000020
【図１０】
2010503936.tif 000021
【図１１】
2010503936.tif 000022
【図１２】
2010503936.tif 000023
【図１３】
2010503936.tif 000024
【図１４】
2010503936.tif 000025
【図１５】
2010503936.tif 000026
【図１６】
2010503936.tif 000027
【図１７】
2010503936.tif 000028
【図１８】
2010503936.tif 000029
【図１９】
2010503936.tif 000030
【図２０】
2010503936.tif 000031
2010503936.tif 000032
【図２１】
2010503936.tif 000033
【図２２】
2010503936.tif 000034
【図２３】
2010503936.tif 000035
【国際調査報告】
2010503936.tif 000036
2010503936.tif 000037
2010503936.tif 000038
2010503936.tif 000039
2010503936.tif 000040
2010503936.tif 000041
2010503936.tif 000042
2010503936.tif 000043
2010503936.tif 000044
2010503936.tif 000045
2010503936.tif 000046
2010503936.tif 000047
2010503936.tif 000048
2010503936.tif 000049
2010503936.tif 000050
2010503936.tif 000051