JPS61156486A

JPS61156486A - 画像処理装置

Info

Publication number: JPS61156486A
Application number: JP59276461A
Authority: JP
Inventors: Masatoshi Okutomi; 正敏奥富; Tetsuo Sueda; 末田　哲夫; Michihiro Tokuhara; 徳原　満弘
Original assignee: Canon Inc
Current assignee: Canon Inc
Priority date: 1984-12-28
Filing date: 1984-12-28
Publication date: 1986-07-16

Abstract

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

Description

【発明の詳細な説明】〔技術分野〕本発明は手書文字、印字文字、その他あらゆるパターン
の認識が可能な画像処理装置に関するものである。

〔従来技術〕

従来からパターン認識について様々な提案がある０例え
ば、パターンの輪郭情報を用いてパターン認識を行う場
合、各輪郭点における輪郭線方向を第１図に示す１〜８
の方向コードに従って量子化したコードとして求められ
ていた。

しかし、この方法では、例えば第２図に示す様なパター
ンがあった場合、図の５１を始点とし、時計回りに輪郭
を追跡した時に得られる方向コードは、第３図に示す様
になり、本来連続的に変化する方向コードが、第３図の
Ａ、Ｂの部分（第２図のａ、ｂに対応）で示す様に、コ
ード上不連続になってしまい、認識する際に不都合を生
じる。　。

このことは、元のパターンが回転した場合等による開始
点の変化が、その後の認識を困難にするということを意
味し、処理時間の増大をもたらすという欠点があった。

〔目　的〕

以上の点に鑑み、本願発明は上記欠点を除去しパターン
の輪郭を連続したデータとしてとらえ、パターンの位置
ずれ、回転大きさの変化などに影響されない安定したパ
ターンの認識が可能な画像処理装置を提供することにあ
る。

〔実施例〕

以下、図面を参照し、本願発明についての詳細に説明す
る０本願でいう画像は文字、マーク、記号、絵等を示す
ものである。

第４図（ａ）、（ｂ）は本願発明の適用が可能な画像処
理装置の１例を示す図である。１はリーグ、２はＯＣＲ
，リーグ又はプリンタ等の制御部、３はプリンタ、４は
ディスプレイ付コンピュータで、各機器の制御指令を出
したり、所望のデータを表示させることが可能である。

５はキーボードである。

又、（ｂ）ではｌＯはハンディ型の画像処理装置本体で
、１１は光源、１２は読み取るべき原稿である。なお１
３は光学系で、光１ｉｔｌｌ及び原稿１２上のパターン
からの光を光電変換素子（例えば面状Ｃ０Ｄ）１４に導
く、１５は光電変換素子１４から出力データ処理及び／
又は出力を行う処理部である。なお、この様な構造に限
る必要はない。又、ディスク装置や、マイクロフィルム
、ワークステーション等を具備したシステムの一つであ
ってもよい。

次に前記処理部１５について、詳細に説明する。第５−
１図は前記処理部１５のブロック図である。１６は前処
理回路で入カバターンに対し、２値化、ノイズ除去等を
行う。次にＣＰＵ１７及びメモリ１８によってパターン
の特徴を抽出する。特徴抽出については、第５−２図の
破線内に示す流れとなる。つまり、１次特徴抽出を行う
ことにより該パターンの輪郭情報をコード化する。そし
てパターンあるいは抽出法によってはそのコードをその
まま用いる。又、更に２次特徴抽出により前記コード列
とは別の特徴を抽出してもよい、そして以上によって得
られた特徴について、メモリ１８等の辞書と照合したり
、あるいは類似度や相関を計算し、該パターンを判定し
てもよい。

更に上記特徴抽出を繰り返してもよいし、他の特徴抽出
を行い、その後パターンを決定してもよい。

次に、本発明の特徴抽出について、更に詳細に説明する
。１次特徴抽出では、まずパターンの輪郭を形成する画
素の中からあらかじめ定めた一定個数だけ抽出する。・
次いで、その抽出点に基づいて輪郭接線方向の方向差を
求め、順次それをコード化する。

輪郭点抽出のフローチャートを第６図に示す。

即ち、まず画像をラスクスキャンして最初にパターンに
当たる画素を求める等の方法により輪郭追跡開始点を求
めその位置を記憶する（ＳＴＥＰＩ）。次いで、輪郭上
例えば右隣りに隣接する輪郭点を求め（ＳＴＥＰ３）、
開始点からの距離文を求める（ＳＴＥＰ４）。開始点か
らの距離文は例えば以下の（１）、（１）’式に従って
積算していく。

隣接輪郭点が上下左右に位置する詩文＝見＋１　　　　　　　（１）隣接輪郭点が斜め方向に位置する詩文＝文＋１．４　　　　　　　（１）以上により、５ＴＥＰ６までで輪郭の一周の長さＬが求
まる。次いで、このしの値を元に、一定個数Ｎの輪郭点
抽出を行なう、まず、開始点を抽出点として選び（ＳＴ
ＥＰ８）、隣接輪郭点とその開始点からの輪郭長文を求
める（ＳＴＥＰＩＩ、１２）。ここで文の求め方は進む
毎に輪郭点を抽出ナベく、以下の条件を判定する（ＳＴ
ＥＰ　１３）。

ここで、Ｎはあらかじめ定められた抽出すべき輪郭点の
個数である。もし、（２）式が成り立てば５ＴＥＰ８に
戻って輪郭点を抽出し、成り立たない間は５ＴＥＰＩＩ
　、１２を繰り返す。

そして、Ｎ個の輪郭点が抽出されると終了する（ＳＴＥ
Ｐ　Ｉ　Ｏ）。

以上の方法を、例えば第７図に示すパターンに適用すれ
ば、図の斜線で示した画素（Ｓ１〜５２０）が抽出され
る。但し、Ｎ＝２０とし、輪郭追跡開始点はＳｌで、右
回りに輪郭を追跡した。

具体的に説明すると、第７図に示すパターンでは、パタ
ーンの全長Ｌ＝９８．６でＮ＝２０よテップ４において
式（１）、（１）’により説明した様に１つの画素の辺
を１、対角線を１．４として算出する。第７図の画素内
に示された数値はその距離である。つまり、Ｓｌから３
２点の画素（斜線で示す）に進むと距離は５．４となり
ステップ１３において５．４　＞　４．９３であること
から、該斜線を施こされた画素を抽出点としてＳ２とす
る。同様にして、次の抽出点までは、第７図に示す様に
、６．８　、７．８　、９．２と進み、次の斜線の施こ
された部分において立＝１０．６となり、第６図のステ
ップ１３において、１０．６　＞　４．９３　Ｘ　２と
なり、この画素を抽出点として（Ｓ３）抽出するのであ
る。以下同様にして第７図に示した抽出点５１〜Ｓ　２
０が抽出される。

次に、輪郭抽出点に基づいて輪郭接線方向の方向差を順
次求めコード化する０例えば輪郭抽出点が第８図に示す
様に並んでいる時、輪郭接線方向の方向差は図のαで、
それを例えば第９図に示す様に８方向に量子化し、コー
ド化する。ここで、常に最初の輪郭接線方向（第８図の
５ｉＳｉｔ１）をコード０の方向に一致させる。この様
に、輪郭接線方向の方向差をコード化することにより、
不当な不連続点が生じることなく、かつ輪郭を何度回っ
ても周期的に変化するコード列が得られる。−例として
、第２図のパターンの総ての輪郭点を用いて得られるコ
ード列を第１０図に示す、第３図と比較して明らかな様
に、不当な不連続点がなく、以後の識別処理に適してお
り、かつコードの開始点の変動などに対し安定である。

第７図に示したパターンに対し、以上詳述した処理を施
こした結果が第１１図である。図の（）で示したものが
コード列であるが、パターンの細かな凹凸に影響されず
に輪郭形状をよく表現しており、かつ長さも正規化され
ている。

次に、判定部では、まず次特徴抽出で得られたコード列
とあらかじめメモリに記憶しである標準コード列との非
線形マツチングを行なって、入カバターンと上記標準コ
ード列が属するカテゴリとの類似性を表わす距離Ｄ（類
似している程小さい値になる）を計算する。その計算式
を以下に示す。ある入カバターンのコード列を、ａｉｒ
　　　ａ２　−−−−−−、　　　ａＮ標準コード列をｃｌ、　　　ｃ２　−−−−−−、　　　ＣＮとした時
、次の斬化式を計算する但し、ｄ（Ｃｉ、ａｊ）＝ｌｃｉ−ａｊｌ＋ｆ（ｌｃｉ−ａｊ
ｌ）　　　（４）ここでｄ（ｃｉ、ａｊ）は標準コード
ｃｉと入力コードａｊ間の距離であり、ｆ（ｌｃｉ−ａ
Ｎ）は対応するコードのコード列上での位置ずれに対す
るペナルティに相当するもので、例えば第１２図の様に
定める。

そして、最終的に入カバターンとカテゴリ間の距＠ＤはＤ＝ｇ（Ｎ、Ｎ）　　　　　　　　　　　　（５）とし
て求まる。

例えば、第１１図に示した入カバターンによる入力コー
ドとある標準コードとが第１３図に示す様に対応付けら
れるとすれば（この対応付は（３）、　（４）式を最後
まで計算することにより求まる）、その時の各コード間
の距離ｄ　（ｃｉ　、　ａＤは、第１４図に示す様にな
り、その和はＤに等しい。

次に図面を参照し、Ｄの算出及びマツチングについて、
詳細に説明する。

第１１図に示した様に、入カバターンのコード列は、ａ
ｊ＝１．ｌ、１，０，０．−３．０，１，３，０，０゜
３．０，０，０．−２．−２．０，４，１．であること
は明らかである。一方の文字“２°゛の標準パターンの
コード列はｃｉ＝１．１．Ｏ，Ｏ，−２，０，０，３，
０，０゜２，０，０，０．−１．−１．０，３，１．１
とすると、Ｄの算出方法は第１５図に示す流れになる。

つまり、式（３）において、ｇ（１，１）＝ｄ（ｃ、ａ）　　は　ｃｌ＝１．ａ１＝
１　　よりｇ（１，１）＝Ｏｇ　（１、２）　＝ｄ　（ｃ４　、　ａｚ）　　は　ｃ
１＝ｌ、ａ２＝２　　よりｇ（１，２）＝ｄ（ｃｌ、ａ
ｚ）＋ｍｉｎ（ｇ（１，１））＝０．１同様にして、ｇ　（２，２）　＝ｄ　（ｃ２．ａｚ）　＋ｍｉｎ（ｇ
（１，２）　ｇ（２，１）　、ｇ（１，１））＝　Ｉ　
ｃ２−ａ２１＋ｆ　（Ｉ　ｃ２−ａｚ　ｌ）　＋ｍｉ　
ｎ　（０，１、０，１、０）　＝Ｏとなる。

なおｆ　（ｌｃｉ−ａｊｌ）は第１２図に示したｉとｊ
（対応サンプリング点）との対応に基づいたデータであ
る。以下、ｔ＋Ｊを１〜２０まで行うと、第１５図の右
上に示す様に１＝ｊ＝２０におけるｇ　（ｉ　、　ｊ）
の値Ｄ　＝　８．１と算出される。

一方、第７図に示した同一パターンに対して、標準パタ
ーンを“°３”の標準パターン（ｃｉ＝１．１．−２．
１，１，１，１，３，０．−１．−１．−１．０゜２．
０．−１．−１．０，３．１）に置き換えた場合は、第
１６図に示す結果となる。つまり３″の標準パターンを
用いた場合は１＝ｊ＝２０におけるｇ　（ｉ　、　ｊ）
の値りは１５．２と算出される。以上から明らかなよう
に第７図に示したパターンに対しては標準パターンの゛
３パより標準パターンの°２”の方が８．１　＜　１５
．２であることから距離が短かいという判定が可能とな
り、第７図に示したパターンは、２に判定される確度が
高くなるのである。

又、標準パターン“２”の各抽出された点と第７図に示
したパターンの各抽出点との対応は。

第１５図の太線の矢印に示されているようになり、結局
第１７図に示す様な対応となる０図から明らかなように
、それぞれの位置において無理な対応付けが成されてい
ないことがわかる。

又、必要であれば第６図に示した抽出点の選択条件を、
変えてずれた抽出点を複数回抽出し、更に精度を向上さ
せるようにしてもよい。以下、文字パターン“３”につ
いて、上述の抽出点をずらして、種々の距１！１０　（
式５）を求めより精度の高い認識が可能な方法について
説明する。

その場合の輪郭点抽出法を、第１８図に示す。

なお、詳細は第６図と同様なので省略する。ここでステ
ップ８、ステップ１６に示す８は、最初の輪郭抽出点か
らのオフセット量（最初の輪郭抽出点に比べどれだけず
れるかを指示する値）であり、０≦δくｌなる値である。（もし、δ＝０であれば、最初の輪郭抽
出点と一致する。）例えば、第１９−１図に示す様な入
カバターンがあった時、最初の輪郭抽出点と、さらにそ
れから求められる方向コードは、第１９−２図に示すよ
うになる。

それに対し、δ＝繕として輪郭抽出をやり直し、コード
列を求めると第１９−３図に示すようになる。つまり、
最初の抽出点の位置が、第１９−２図と見比べてわかる
通り、パターン外郭形状の凹凸が忠実にコードに反映さ
れており、（第１９−３図の「→」で示した箇所）、従
って、以後の処理によって正しく認識される確率が大幅
に増す０例えば、コード上で連なるマイナスのコードの
かたまりの数（パターンの凹の数に相当）を大分類に用
いるとすれば、第１５−２図では２個しか検出されない
が第１９−３図ではパターンの形状に忠実に３個検出さ
れており正確な認識が行われる可能性がはるかに高くな
る。（第１５−２図、第１５−３図のコード列上の↑印
参照）なお、δの値は局には限らず、例えば１１５　、
２１５　。

３１５．４１５といった具合に少しづつ変えながら輪郭
抽出を繰り返してもよく、より正確な認識が行なえるよ
うになる。

また、以上の一連の処理による判定結果は、そのまま認
識結果として出力してもよいし、また候補カテゴリとし
て記憶し、さらに別の認識処理に進むこともできる。

次に前述の第１９−２図、第１９−３図に示したパター
ンのコード列と文字“°３゛°の標準コードにより、距
離Ｄ（式５）を求める場合について説明する。抽出点を
変えるだけで、更に精度の高い認識が可能となる。第２
０図、第２１図は°゛３”９の標準コード列ｃｔ＝１，
１．−２．１，１゜１．１，３，０．−１．−１．−１
．０，２，０．−１．−１．０，３゜ｌと°“３パの入
カバターンコード列ａｊ＝ｌ、０゜１．０，０，０，１
，１，０，４，０．−２．−１．−１．０，０゜−１，
−２，０，３，との距離り及び抽出点をずらした場合°
“３°゛の入カバターンコード列”Ｊ＝Ｌ１＋Ｌ　　Ｌ
ｎＯ，１，１，ｌ、１，３，０．−１．−１．−１．２
．−１．−１゜−１，３，１との距離りを求める場合の
説明図である。

距離りの求め方は、第１５図及び第１６図において説明
したので詳細は省略する。結局距離りは１７．５→８と
より正確にパターンを認識することが可能となるわけで
ある。また、第２０図、第２１図↑印を観ることにより
、それぞれ第２２図の（ａ）、Ｃｂ）に示した様な各画
素の抽出を行っていることがわかる。

なお、この距離によりパターンの判定の補助として行う
必要はなく類似度やその他いかなる判定法でもよい。つ
まり以上は、基本的にはいわゆるダイナミック・プログ
ラミング（Ｄ　、　Ｐ）という手法を用いたのであるが
、コード上での位置ずれや多重対応を許すことにより、
例えば手書文字などの変形を吸収できる非線形マツチン
グを実現している。さらに、本発明では、第１２図に示
した様な、コード上での位置ずれを評価量（ペナルティ
）として加味することにより、変形を許しつつも不当な
対応付け（いわゆる合わせ過ぎ）を排除し、正確で高速
な認識を可能にしている。

そして、各標準コードに対して、パターンの類似性を表
わす距離りを計算し、例えば以下の条件に従って入カバ
ターンを判定する。すなわち、ある入カバターンに対し
て最も小さい距離りをＤｌ、次に小さい距離りをＤ２と
する時、次の■、■の条件を共に満たせば、上記入カバ
ターンがＤｌに対応するカテゴリに属すと判定し、それ
以外は対応するカテゴリが存在しないと判定する。

■　Ｄｉ＜Ｋｌ ■Ｄ２−ＤＩ＞Ｋ２又は、Ｄｌ　とＤ２に対応するカテ
ゴリが等しい、但し、Ｋｌ、に２は認識対象の変形の度合やカテゴリ相
互のまぎられしさなどにより、あらかじめ定められる定
数である。

また、上記判定結果は、そのまま認識結果として出力し
てもよいし、また候補カテゴリとして記憶しておき、さ
らに別の認識処理に進むこともできる。

前記実施例において、輪郭点の抽出法は第６図、第１８
図に示した方法に限られるものではなく、パターンの輪
郭形状の細かな凹凸やノイズなどになるべく影響されず
にパターンの形状の特徴を表わすような画素を一定個数
抽出する方法であれば後の処理に全く影響を及ぼすこと
なく適用できる。またコード付の第９図に示す０　七　
而　Ｉ＋　四　ｌｈ　　ユμ　　　矧　烏　占４　ｈ、
　１ヂ　円　１−−　　　　μ　Ｌｌ　　湘　講、く（
例えば第２３図の様に）又は粗くすることは効果的であ
る。

さらに、非線形マツチングを実行する斬化式％式％（但し、にはｋ＞１なる宝船という様に多重対応に対するペナルティ（ｋ）を付加し
たり、第１２図に示したコードの位置ずれに対するペナ
ルティを変えることで、変形に対する制約条件を変え、
さまざまな認識対象に適したマツチングを行なうことが
できる。

なお、以上説明した方法を繰り返してもよく、又、組み
合せてもよいことは言うまでもない。

次に以上説明した方法のハード構成の一例を第２４図に
示す、即ち、メモリー書込み回路ｌにより、入力原稿内
のあらかじめ指定される任意のエリアを入力装置１００
　（図ではディジタルコピーのリーダー）より読み込ん
でメインメモリー１０２に書込み、次いで前処理回路１
０３により、文字領域の切出しと２値化を行なう。更に
、１次、２次特徴抽出回路１０４では、輪郭追跡と輪郭
点抽出、更にそのコード化と必要に応じてコード列より
２次特徴を抽出する。そして、非線形マツチング回路１
０５により、入カバターンの各標準パターン（コード）
との相違度が計算される０以上の各回路をパイプライン
上に接続することにより、高速な認識速度が得られる。

また、制御用Ｃ０Ｐ、Ｕは、上記各回路を制御し、さら
に非線形マツチング回路１０５から得られた相違度値を
元に、最終認識効果を外部機器１０６に出力したり、場
合によっては、１次、２次特徴抽出回路１０４に対し、
再びコード化をやり直すことを指示したりする。

〔効果〕

以上、詳述したように本願発明によりパターンの輪郭点
を一定個数抽出し、それに基づいて輪郭接線方向の方向
差を求めてコード化し、上記コードと、あらかじめメモ
リに記憶しである標準コードとの非線形マツチングを行
なって、パターンの変形の度合を適格に加味した、該入
カバターンと上記標準コードが属するカテゴリとの類似
性を表わす距離を求め、上記入カバターンの認識を行な
うことにより、さまざまな認識対象に適し、かつ高速で
安定した認識装置を、簡単な構成で実現することが可能
となりた。

【図面の簡単な説明】

第１図は従来の方向コードを示す図、第２図はパターン
の一例を示す図、第３図は輪郭点と方向コードの関係を
示す図、第４図は本願発明の適用が可能な画像処理シス
テムの１例を示す図である。第５−１図は処理部のブロ
ック図。第５−２図はパターンの特徴抽出の流れを示す図、第６
図は１次特徴抽出部における輪郭点の抽出法を示す図、
第７図はパターンの１例とその輪郭抽出点を示す図、第
８図は輪郭抽出点と輪郭接線方向の方向差の関係を示す
図、第９図は本発明適用の各輪郭抽出点における方向コ
ードを示す図、第１Ｏ図は輪郭点と方向コードの関係を
示す図、第１１図は本発明による方向コードを示す図、
第１２図は非線形マツチングを行なってパターンの距離
を求める際に用いるコードの位置ずれに対するペナルテ
ィを示す図、第１３図はコードの対応付の例を示す図、
第１４図は第１３図の対応付に対するコード間の距離を
示す図、第１５図は第１１図に示した入カバターンのコ
ード列と文字２パの標準パターンのコード列との距離り
の算出方法の説明図、第１６図は第１１図に示した入カ
バターンのコード列と文字“°３゛の標準パターンのコ
ード列との距＃Ｄの算出方法の説明図、第１７図は標準
パターン２と入カバターンとの対応付を示す図、第１８
図は抽出点をずらして選択する場合のフローチャート、
第１９−１図は入カバターンの１例を示す図、第１９−
２図は第１９−１図に示した入カバターンのコード化の
例を示す図、第１９−３図は第１９−２図に示したコー
ド化＾Ｉｌｌ　ｌ＋ｊ−ｋ　Ｌギ督１■＾但人小１−に
′ル小１１壬す図、第２０図は第１９−２図に示したコ
ード列と文字“３゛の標準パターンのコード列との距離
りの算出方法を示す図、第２１図は第１９−３図に示し
たコード列と文字“３”の標準パターンのコード列との
距離りの算出方法を示す図、第２２図は第２０図、第２
１図に示した各パターンの対応付を示す図、第２３図は
細分化した方向コードを示す図、第２４図は本発明のシ
ステム制御ブロック図。１０６は制御用ＣＰＵ１０５は非線形マツチング回路１０４は特徴抽出回路

Claims

【特許請求の範囲】画像パターンの輪郭情報を所定方向に、追跡し輪郭点を
検出する検出手段、上記検出手段により検出された輪郭点の中から所定個数
選び出す抽出手段、上記抽出点に基いて輪郭接線方向の方向差を順次求め、
コード化する手段、上記コード化手段によってコード化されたコード列と標準コード列との非線形マツチングを行ない
上記画像パターンを認識する認識手段を有したことを特
徴とする画像処理装置。