(57)【特許請求の範囲】
【請求項１】
２値画像中から図形を抽出する方法であって、
抽出対象である図形の白画素部分にマイナスの重み値、黒画素部分にプラスの重み値を与え、
前記図形の基準点を中心に１８０度回転したテンプレートＡを作成し、
前記テンプレートＡの重み値の符号を正負反転させたテンプレートＢを作成し、
２値画像の上を１画素ずつ移動しながら、２値画像中の画素に前記テンプレートＡまたはＢの基準点を重ね、
該画素が黒画素の場合は投票画像にテンプレートＡの重み値を、該画素が白画素の場合は投票画像にテンプレートＢの重み値を投票値として加算していき、
前記投票画像中で投票値が極大となる部分を抽出対象である前記図形の基準点の位置として抽出することを特徴とする図形抽出方法。
【請求項２】
請求項１に記載の図形抽出方法において、前記投票画像中で投票値が極小となる部分を、白黒反転した抽出対象の基準点が存在する位置として抽出することを特徴とする図形抽出方法。
【請求項３】
請求項１または２に記載の図形抽出方法において、
前記テンプレートＡの重み値を２倍にしたテンプレートＡ’を作成し、
２値画像の上を１画素ずつ移動しながら、２値画像中の全ての画素に前記テンプレートＢの基準点を重ねて投票画像にテンプレートＢの重み値を投票値として加算していくことで第１の投票画像を作成し、
２値画像中の黒画素のみに前記テンプレートＡ’の基準点を重ねて第１の投票画像にテンプレートＡ’の重み値を投票値として加算していくことで第２の投票画像を作成し、
第２の投票画像中で投票値の合計が極大となる部分を抽出対象である図形の基準点の位置、極小となる部分を白黒反転した抽出対象の基準点の位置として抽出することを特徴とする図形抽出方法。
【請求項４】
請求項１または２または３に記載の図形抽出方法において、
前記テンプレートＢの各点に与えられた重み値を合計して合計値Ｓを求め、
投票画像の全ての点に予め投票値として前記合計値Ｓを与えて第１の投票画像を作成し、
２値画像中の黒画素のみに前記テンプレートＡ’の基準点を重ねて前記第１の投票画像にテンプレートＡ’の重み値を投票値として加算していき前記第２の投票画像を作成し、
前記第２の投票画像中で投票値の合計が極大となる部分を抽出対象である図形の基準点の位置、極小となる部分を白黒反転した抽出対象の基準点の位置として抽出することを特徴とする図形抽出方法。
【請求項５】
請求項３または４に記載の図形抽出方法において、
共通の抽出対象を、大きさの同じ様々な２値画像から抽出する場合、一度作成した前記第１の投票画像を共通的に使用することを特徴とする図形抽出方法。
【請求項６】
請求項１乃至５のいずれか１項に記載の図形抽出方法において、重み値０の部分を持つテンプレートを作成することを特徴とする図形抽出方法。
【請求項７】
請求項６に記載の図形抽出方法において、
抽出対象とする図形の黒画素部分と白画素部分との境界に、重み値０の部分を持つテンプレートを作成することを特徴とする図形抽出方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、２値画像中からテンプレートを用いて図形（画像パターン）を抽出する方法に関するものである。
【０００２】
【従来の技術】
従来、２値画像中から図形を抽出する方法として、一般Ｈｏｕｇｈ変換「森俊二、坂倉拇子：画像認識の基礎〔ＩＩ〕、Ｐａｇｅ１１−１４、オーム社、１９９０」がある。この方法は、抽出対象図形の黒画素部分に重み値を与えたテンプレートを作成し、このテンプレートを用いて画像中から抽出対象図形と類似した図形を抽出するものである。
【０００３】
【発明が解決しようとする課題】
しかし、この種の従来の方法は、黒画素部分の類似性のみに基いて抽出対象図形に類似した図形の抽出を行い、白画素部分の類似性を考慮しないため、以下の二つの問題がある。
【０００４】
第１の問題は、抽出対象図形の白画素部分が一部黒画素となっているような、抽出対象図形と区別すべき類似した図形を間違えて抽出してしまうことである。例えば「Ｌ」字型を抽出対象図形とする場合には、図１０の（ａ），（ｂ）に示すように、抽出対象図形に類似しない図形が画像中から抽出される。図１０において、１０００は２値画像例、１０１０は抽出対象図形、１０２０は間違って抽出された図形、１０３０は正しく抽出された図形である。
【０００５】
第２の問題は、白黒が反転している抽出対象図形は、テンプレートを作り直さねば抽出できないことである。従って２値画像中に、抽出対象図形と白黒反転した抽出対象図形が混在する場合、一度の処理で両方を抽出することができない。
【０００６】
なお、画像上の雑音や歪みの発生による誤検出を解決する方法を、本願出願人は、既に提案している（特開平１１−３２８３９０号公報）。この方法は、抽出対象図形の特徴を重み値によって表現する第１のテンプレートを使用して図形抽出処理を行い、この抽出処理結果から正しく抽出された部分領域と誤って抽出された画像の部分領域から類似した図形との差を強調する第２のテンプレートを作成し、この第２のテンプレートを用いて図形抽出処理を行う。しかしながら、この方法においては、第１の問題については、２つのテンプレートを用いて２回の抽出処理をすることになり、処理が複雑になる。また、第２の問題を解決できるものでない。
【０００７】
本発明の目的は、抽出対象図形の黒画素部分と白画素部分の両方の類似性に着目することにより、上記問題を解決する図形抽出方法を提供することにある。
【０００８】
【課題を解決するための手段】
本発明は、抽出対象図形の白画素部分と黒画素部分の両方に注目し、図形の白画素部分にマイナスの重み値、黒画素部分にプラスの重み値を与え、図形の基準点を中心に１８０度回転したテンプレートＡと、該テンプレートＡの重み値の符号を正負反転させたテンプレートＢの二つのテンプレートを作成し、これら２つのテンプレートを用いて図形を抽出することを最も主要な特徴とする。
【０００９】
これにより、従来方法で多数発生していた類似図形の誤った抽出を無くし、また白黒反転した抽出対象を一度の処理で抽出することができるようにしたもので、以下の方法を特徴とする。
【００１０】
２値画像中から図形を抽出する方法であって、
抽出対象である図形の白画素部分にマイナスの重み値、黒画素部分にプラスの重み値を与え、前記図形の基準点を中心に１８０度回転したテンプレートＡを作成し、前記テンプレートＡの重み値の符号を正負反転させたテンプレートＢを作成し、２値画像の上を１画素ずつ移動しながら、２値画像中の画素に前記テンプレートＡまたはＢの基準点を重ね、該画素が黒画素の場合は投票画像にテンプレートＡの重み値を、該画素が白画素の場合は投票画像にテンプレートＢの重み値を投票値として加算していき、前記投票画像中で投票値が極大となる部分を抽出対象である前記図形の基準点の位置として抽出することを特徴とする。
【００１１】
また、前記投票画像中で投票値が極小となる部分を、白黒反転した抽出対象の基準点が存在する位置として抽出することを特徴とする。
【００１２】
また、前記テンプレートＡの重み値を２倍にしたテンプレートＡ’を作成し、２値画像の上を１画素ずつ移動しながら、２値画像中の全ての画素に前記テンプレートＢの基準点を重ねて投票画像にテンプレートＢの重み値を投票値として加算していくことで第１の投票画像を作成し、２値画像中の黒画素のみに前記テンプレートＡ’の基準点を重ねて第１の投票画像にテンプレートＡ’の重み値を投票値として加算していくことで第２の投票画像を作成し、第２の投票画像中で投票値の合計が極大となる部分を抽出対象である図形の基準点の位置、極小となる部分を白黒反転した抽出対象の基準点の位置として抽出することを特徴とする。
【００１３】
また、前記テンプレートＢの各点に与えられた重み値を合計して合計値Ｓを求め、投票画像の全ての点に予め投票値として前記合計値Ｓを与えて第１の投票画像を作成し、２値画像中の黒画素のみに前記テンプレートＡ’の基準点を重ねて前記第１の投票画像にテンプレートＡ’の重み値を投票値として加算していき前記第２の投票画像を作成し、前記第２の投票画像中で投票値の合計が極大となる部分を抽出対象である図形の基準点の位置、極小となる部分を白黒反転した抽出対象の基準点の位置として抽出することを特徴とする。
【００１４】
また、共通の抽出対象を、大きさの同じ様々な２値画像から抽出する場合、一度作成した前記第１の投票画像を共通的に使用することを特徴とする。
【００１５】
また、重み値０の部分を持つテンプレートを作成することを特徴とする。
【００１６】
また、抽出対象とする図形の黒画素部分と白画素部分との境界に、重み値０の部分を持つテンプレートを作成することを特徴とする。
【００１７】
【発明の実施の形態】
（第１の実施形態）
本実施形態は、抽出対象図形と区別すべき類似した図形が多数存在している２値画像中から正しい図形を抽出する場合である。
【００１８】
図１に、本実施形態の処理手順を示す。１００はイメージ入力装置によって得る白及び黒の２値で表される２値画像、２００はテンプレートＡの作成処理、３００はテンプレートＢの作成処理、４００は２値画像中からの図形抽出処理、５００は図形抽出結果である。
【００１９】
本実施形態および後に説明する他の実施形態における図形抽出方法は、例えばコンピュータとその入出力装置によって実現され、コンピュータには２値画像や作成されたテンプレートＡ，Ｂおよび抽出結果等のデータを内部メモリや外部記憶装置に書き込み・読み出しができるようにし、必要とする図形抽出処理をアプリケーションプログラムとして搭載する。
【００２０】
図１において、２値画像１００は、スキャナ、ファクシミリ、カメラ等のイメージ入力装置によって、白及び黒の２値で表される画像である。
【００２１】
テンプレートＡの作成処理２００は、図形を抽出するためのテンプレートＡを作成する処理である。テンプレートＡの作成方法には２つの方法がある。
【００２２】
最初の方法は、予め決められた抽出対象図形の形状の関数に基づいて作成する方法である。例えば、ｘ，ｙ座標上の円を抽出する場合には、円の半径をｒとして、
【００２３】
【数１】
ｘ２＋ｙ２＝ｒ２
なる式でテンプレートＡを作成する。
【００２４】
もう１つの方法は、実際の２値画像中から抽出対象となる図形を切出し、これに基づいて作成する方法である。図２は、該方法によって「Ｌ」字型のテンプレートＡを作成する手順の説明図であり、同図の（ａ）に示す２１０は２値画像であり、（ａ）中および（ｂ）に示す２２０は抽出対象である「Ｌ」字型の画像、（ｃ）に示す２３０は基準点を中心に１８０度回転して作成したテンプレートＡである。
【００２５】
まず、２値画像２１０中からマニュアル操作によって抽出対象２２０を切出す。そして切出された抽出対象の白画素部分にマイナスの重み値、黒画素部分にプラスの重み値を与え、さらに基準点を中心に１８０度回転させ、テンプレートＡを作成する。基準点の取り方は任意でよいが、この場合は図形の中心を基準点とする。テンプレートに与える重み値も任意でよいが、計算コストが小さくなるように、マイナスの重み値を−１、プラスの重み値を１としてテンプレートを作成する方法が好ましい。
【００２６】
また、重み値０の部分をテンプレートに加えることで、抽出処理においてその部分の類似性を無視することができる。これを利用し、２値画像中から類似した２種類の図形を抽出する場合、これら２種類の図形の相違部分を重み値０としたテンプレートを作成し、相違点を無視した抽出処理を行うことで、１つのテンプレートで同時に両方の図形を抽出できる。
【００２７】
また、抽出対象である図形の黒画素部分と白画素部分との境界に、重み値０の部分を適当な幅で加えたテンプレートを作成することで、抽出対象である図形の多少のぶれ、傾斜、雑音などに対して影響され難い図形抽出を行うことができる。例として、このようにして作成した長方形を抽出するためのテンプレートを、図２の（ｄ）に２４０として示す。
【００２８】
次に、テンプレートＢ作成処理３００は、テンプレートＡの重み値の符号を正負反転させ、テンプレートＢを作成する処理である。図３にテンプレートＡ作成処理で作成されたテンプレート２３０からテンプレートＢ作成処理で作成されたテンプレート３１０を示す。
【００２９】
図形抽出処理４００は、作成したテンプレートＡ，Ｂを用い、２値画像中から抽出対象となる図形を抽出する処理である。図４は、図形抽出処理４００の処理手順図であり、４１０は２値画像、４２０はテンプレートＡ，４３０はテンプレートＢ，４４０は投票処理、４５０は投票画像、４６０は図形位置検索処理、５００は図形抽出結果である。
【００３０】
投票処理４４０は、２値画像４１０の上を１画素ずつ移動しながら２値画像中の画素にテンプレートＡ，Ｂの基準点を重ね、該画素が黒画素の場合はテンプレートＡの重み値を、該画素が白画素の場合はテンプレートＢの重み値を投票画像４５０に投票値として加算していく処理である。以下の説明では、２値画像４１０として図２で示した２値画像２１０を用いる。図５の（ａ）に投票画像４５０での投票結果を示す。
【００３１】
図形位置検索処理４６０は、投票画像４５０を用いて抽出対象図形の位置を検索する処理である。投票画像において、投票値の大きい部分はテンプレートと類似した図形の存在する位置を表す。そこで、投票画像のうち、投票値が一定値以下で雑音とみなせる部分を排除したのち、投票値が極大となる位置を検索することにより、抽出対象である図形の基準点が存在する位置を決定できる。
【００３２】
この様な方法で決定された位置に、抽出対象図形を重ねて表示すると、図５の（ｂ）に示すように、図形抽出結果５００が得られる。
【００３３】
以上説明した図形抽出処理４００は、一般Ｈｏｕｇｈ変換を用いた従来の図形抽出方法を拡張した手法であり、テンプレートに白画素部分を含め、黒画素部分だけでなく自画素部分の類似度も考慮することにより、抽出対象の白画素部分が一部黒画素となっているような、抽出対象と区別すべき類似した図形を除外することができる。
【００３４】
（第２の実施形態）
本実施形態は、白黒反転した抽出対象図形の抽出方法である。
【００３５】
図６は、イメージ入力装置の設定などが原因で、抽出対象の白黒が反転している２値画像４１１の例である。２値画像４１１に対して第１の実施形態と同様に、図形抽出処理４００を施すと、図７の（ａ）に示す投票画像４６１が得られる。投票画像４６１のうち、投票値が最小の部分はテンプレートＢとの類似度が大きい場所である。そこで、投票画像のうち、投票値が一定値以上で雑音とみなせる部分を排除したのち、投票値が極小となる位置を検索することにより、白黒反転した抽出対象の基準点が存在する位置を決定できる。
【００３６】
この様な方法で決定された位置に、抽出対象図形を重ねて表示すると、図７の（ｂ）に示すように、図形抽出結果５０１が得られる。
【００３７】
また、投票値が極大となる位置と、極小となる位置を同時に検索することで、抽出対象図形と白黒反転している抽出対象図形を同時に抽出することもできる。
【００３８】
（第３の実施形態）
本実施形態は、抽出対象または白黒反転した抽出対象の、簡易かつ高速な抽出方法である。
【００３９】
図８に図形抽出処理の手順を示す。８１０は２値画像、８２０はテンプレートＢ，８３０は第１の投票処理、８４０は第１の投票画像、８５０はテンプレートＡ’、８６０は第２の投票処理、８７０は第２の投票画像、８８０は図形位置検索処理、５００は図形抽出結果である。
【００４０】
２値画像８１０、テンプレート８２０は、第１の実施形態または第２の実施形態で説明したものと同様である。
【００４１】
第１の投票処理８３０は、２値画像８１０の上を１画素ずつ移動しながら２値画像中の画素にテンプレートＢの基準点を重ね、投票画像８４０にテンプレートＢの重み値を投票値として加算していく処理である。以下の説明では、２値画像８１０として図２で示した２値画像２１０を用いる。図９の（ａ）に第１の投票画像８４０を示す。
【００４２】
テンプレートＡ’になるテンプレート８５０は、テンプレートＡの重み値を２倍にして作成したテンプレートである。図９の（ｂ）にテンプレート８５０の例を示す。
【００４３】
第２の投票処理８６０は、２値画像中の黒画素のみにテンプレートＡ’（８５０）の基準点を重ね、第１の投票画像８４０にテンプレートＡ’の重み値を投票値として加算する処理である。この処理の結果、第２の投票画像８７０が作成される。
【００４４】
第１の投票処理８３０は、第１または第２の実施形態と異なり画像中の全画素にテンプレートＢの基準点を重ねて投票を行うため、画像中の黒画素に対しては第１または第２の実施形態とは正負逆の重み値が投票されている。そこで第２の投票処理に、テンプレートＡの２倍の重み値を持つテンプレートＡ’を用いることで、作成される第２の投票画像８７０は第１または第２の実施形態で作成される投票画像４６０または４６１と同じものとなる。
【００４５】
図形位置検索処理８８０、図形抽出結果５００は第１または第２の実施形態と同様のため、その説明を省略する。
【００４６】
また、上記第１の投票処理８３０において２値画像中のある一点に注目すると、この点にはテンプレートＢを構成する全ての点が重なり、投票画像にはテンプレートＢ各点の重み値が合計される。従って、テンプレートＢの各点に与えられた重み値を合計して合計値Ｓを求め、投票画像の全ての点に予め投票値としてＳを与えることで、より簡易かつ高速に第１の投票画像８４０を得ることができる。ただし、２値画像の端の部分では、合計値Ｓと実際に投票して得られる投票値が異なる場合があるため、注意が必要となる。
【００４７】
例えば、基準点がテンプレートの中心である場合、２値画像の幅をＷ、高さをＨ、テンプレートの幅をＷｔ、高さをＨｔとした時、以下のいずれかの条件を満たす部分
【００４８】
【数２】
ｘ＜Ｗｔ／２
ｘ＞Ｗ−Ｗｔ／２
ｙ＜Ｈｔ／２
ｙ＞Ｈ−Ｈｔ／２
では、合計値Ｓと実際の投票値が異なる場合がある。この問題が正確な図形抽出に悪影響を与える場合には、この部分でのみ実際の投票処理を行うなどの補正方法を適用できる。
【００４９】
ここで、共通の抽出対象図形を大きさが同じ様々な２値画像から抽出する場合、第１の投票画像８４０は共通的に使用可能である。従って、第１の投票画像を一度作成した後、これをメモリなど記憶媒体上に記憶しておくことで第１の投票処理８３０を省略して第２の投票処理８６０へ進むことができ、簡易かつ高速な図形抽出処理が可能となる。
【００５０】
【発明の効果】
以上説明してきたように、本発明では、図形の白画素部分にマイナスの重み値、黒画素部分にプラスの重み値を与え、図形の基準点を中心に１８０度回転して作成したテンプレートＡと、テンプレートＡの重み値の符号を正負反転させたテンプレートＢの二つのテンプレートを用い、黒画素部分と白画素部分の両方の類似性に基いて抽出対象とする図形を抽出するため、類似図形の誤抽出が解決され、また白黒反転した抽出対象を一度の処理で抽出することができる。
【００５１】
また、テンプレートＢを用い予め全ての画素に対して投票を行う方法や、テンプレートＢ各点の重み値を合計し、合計値を投票画像の各点に与える方法などにより、上記図形抽出方法を簡易かつ高速に行うことが可能となる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態の処理手順図。
【図２】「Ｌ」字型図形を抽出するためのテンプレートＡの作成手順図。
【図３】テンプレートＢの例。
【図４】図形抽出処理の詳細な処理手順図。
【図５】投票処理した画像と図形抽出結果の例。
【図６】本発明の第２の実施形態が抽出処理対象とする白黒反転の２値画像例。
【図７】投票処理した画像と図形抽出結果の例。
【図８】本発明の第３の実施形態の処理手順図。
【図９】第１の投票処理による画像とテンプレートＡ’の例。
【図１０】従来方法の問題点の説明図。
【符号の説明】
２００…テンプレートＡ作成処理
３００…テンプレートＢ作成処理
４００…図形抽出処理
４４０…投票処理
４５０…投票画像
４６０、８８０…図形位置検索処理
８３０…第１の投票処理
８６０…第２の投票処理
【図１】
0003598039.tif 000002
【図２】
0003598039.tif 000003
【図３】
0003598039.tif 000004
【図４】
0003598039.tif 000005
【図５】
0003598039.tif 000006
【図６】
0003598039.tif 000007
【図７】
0003598039.tif 000008
【図８】
0003598039.tif 000009
【図９】
0003598039.tif 000010
【図１０】
0003598039.tif 000011