JPH06101049B2 - 文字列検出方法 - Google Patents

Description

【発明の詳細な説明】 A.産業上の利用分野 本発明は、図やイラストを含む文書画像中の文字列を検
出する方式に関する。

B.従来技術 近年オフイスのさまざまな文書（マニユアルや設計図面
など）を（光フアイリングシステムにより）電子的に蓄
積・（フアクシミリにより）伝送することが可能になり
オフイスのペーパーレス化が進んでいる。しかしなが
ら、現在のところ文書は白黒の画像情報として扱われて
おり、イメージの切り貼り以上の高度な処理や、より効
率的な蓄積・伝送を行うためには、画像情報の構造化
（文字コード、グラフイツクコマンドを含むマルチメデ
イア情報への変換）が必要になる。画像情報の構造化処
理においては、図や絵を含む画像から文字列のみを抽出
する（文字列に外接する長方形の画像中での位置データ
を求める）作業が最初に行なわれることが多い。

例えば、CAD/CAMのための自動画面入力システムにおい
ては、最初に図面中の文字列と線図形とを分離したのち
それぞれを認識する必要があるし、新聞・雑誌等の画像
の領域分割（画像を文字、図表、写真等の領域に分解す
ること）において、ある領域内に文字列が存在するか否
かという情報は非常に有用である。また、これまで文字
のみが印刷されている文書を処理の対象としていたOCR
においても、ロゴや署名、アンダーライン程度は自動的
に無視して文字のみを認識するような機能が求められて
いる。

しかし、文字列抽出処理は画像全体を処理の対象とする
ため、かなり時間のかかる処理である。しかも、印刷英
数字の認識等がパソコン上のソフトウエアで行なわれる
ようになつている現状では文字列抽出もパソコン上で行
えるのが望ましく、高速な文字列抽出方式が求めらてい
る。この文字列抽出の過程は次のような二つのステツプ
にわけることができる。

１）画像中の文字列を検出する。

２）文字列の外接長方形の正確な位置と大きさを決定す
る。

ステップ１の文字列検出とは、画像を走査して文字列の
位置データに関するおおよその情報を得ることをいう。
ステツプ２では、ステツプ１で得られた情報（座標、大
きさなど）をもとにして処理を行うためほとんど時間は
かからない。したがつてCPUに負担のかかるのはステツ
プ１の文字列検出処理であり、画像情報の構造化のアプ
リケーシヨンがオフイスへ普及するためには、高価な専
用ハードウエアやホストコンピユータを必要としない高
速な文字列検出方式が不可欠である。

従来用いられていた文字列検出方法としては次のような
ものがある。（ただし、図面固有の知識を利用する方法
はここでは除外している。） （１）ヒストグラムを使う方法 画像を走査して黒画素数を数えそのヒストグラムから文
字列を検出する。文字だけの画像に対しては最もよく使
われている方法である。図や絵を含む画像に対しては走
査する範囲を変えて何度かヒストグラムをとりながら文
字列だけの領域をもとめる方法が提案されている。下記
の論文はこの方法を記述した文献の１例である。

Masuda、Hagita、Akiyama著“Approach to Smart Docum
ent Reader System".Proc.Conference CVPR、San Franc
isco、1985、pp.550-557 （２）図形の大きさに着目する方法 第12図に示すように、連結している黒画素を追跡し、連
結領域に外接する長方形（121、122、123）をもとめ
る。文字の黒画素連結領域は他の図形の黒画素連結領域
よりも小さいので外接長方形の大きさから文字を識別す
ることができる。多くのシステムで採用されている方法
である。下記の本はこの方法を記述した文献の１例であ
る。

Rosenfeld、Kak著“Digital Picture Processing"、Aca
demic Press、New York、1976 （３）図形の複雑さに着目する方法 黒画素の近傍において図形の複雑さを調べ文字を構成す
る画素であるか判定し、それらが集中している領域を文
字領域とする。図形の複雑さとして例えば近接線密度を
用いる場合には、画像中のすべての黒画素について、そ
の画素を中心として上下左右の四方向に走査を行ない画
素が白から黒にかわる回数を数え、複雑さの尺度とす
る。

第13図を例にとつて説明すると、現在着目している黒画
素131を中心として、領域132として表わされる範囲で走
査が行われる。走査範囲内で白が黒に変わるのは３回で
あり、したがつて、近接線密度は３となる。近接線密度
が高い黒画素は文字を構成する画素であると判断され
る。下記論文は、この方法を記載した文献の１例であ
る。

Kubota、Iwaki、Arakawa著、“Document Understanding
System"、7th ICPR、Montreal、1984、pp.612-614 （４）前処理を行つた画像から文字列を検出する方法 近接している黒画素領域の間の白画素を黒画素で置き換
えた画像を作り（この結果、文字列中の文字は連結され
一つの黒画素領域になる。）、その画像中の黒画素連結
領域の形や大きさから文字列であるか否かを判定する。
白画素を黒画素で置き換える方法としては連長フイルタ
リング処理がよく用いられている。連長フイルタリング
処理とは、第14図に示すように、まず画像をラスター走
査してある長さ以上の白ランを残して後はすべて黒画素
で置き換えた画像を作り、次いで主走査と副走査の方向
をいれかえてラスター走査を行ない同様の処理を行つた
後、二つの画像のAND演算をとる処理である。下記論文
は、この方法を記述した文献の１例である。

Wong、Casey、Wahl著、“Document Analysis System"、
IBM J.RES.DEVELOP Vol.26、No.6、pp.647-656、1982/1
1 また、これらの方法を組合せて用いたり、個々の文字の
切り出しや認識の結果をフイードバツクして最初の結果
を修正していくシステムもある。

C.発明が解決しようとする問題点 以下に速度および検出精度の面からみた従来方法の問題
点を述べる。

文字列検出の速度は、画像に対するアクセスの回数と画
像を処理する単位に大きく依存する。アクセスの回数は
ラスター走査１回、画像を処理する単位は汎用プロセツ
サのデータ処理の単位（バイト（8bit）やワード（16bi
t））と同じであること望ましい。

方法（１）では図や絵の領域を切分けるためには複数回
の走査が必要になり、その数は画像内の図や絵の領域の
数がふえるにつれ増加する。方法（２）では１回の走査
で連結領域の外接長方形をもとめることができる（ただ
し、途中結果を格納するのに複雑なデータ構造が必要に
なる。）。方法（３）では画像を１回走査する必要があ
るのに加えて、黒画素がある度にその上下左右（近接線
密度の場合）へのアクセスが生じる。方法（４）では、
前処理で３回、連結領域を調べるのに１回、計４回の走
査が必要になる。

処理の単位については、方法（１）ではテーブルルツク
アツプによるバイト（ワード）単位での処理が可能であ
る。方法（２）と方法（３）では画像を走査するとき１
ドツトずつ白か黒かを調べていく必要がある。方法
（４）では、前処理ではバイト（ワード）単位での処理
が可能であるが、連結領域を調べる処理はドツト単位に
なる。

したがつて方法（２）、（３）、（４）では画像データ
をビツト単位でハンドリングする必要が生じる。従来方
法でアクセスの回数と処理単位の最適な組合せを実現し
ているものは存在せず、十分な速度を達成するためには
エンジニアリング・ワークステーシヨンか専用のハード
ウエアが必要である。

文字列検出の精度を比較する場合、二つの基準が考えら
れる。一つは検出漏れがないかということ、もう一つは
余計な図形を文字列として検出しないかということであ
る。余計な検出は外接長方形の決定、個々の文字の切り
出し、認識の過程で用意に発見・修正ができるのでここ
では検出漏れについて述べる。

方法（１）ではヒストグラムの山と谷から文字列を検出
するので文字列がイラストの間に点在している場合には
全く検出できないことがある。

方法（２）と方法（４）では文字が他の図形と接触して
いる場合に問題が生じる。図形と接触している文字の外
接長方形は大きなものとなり文字ではないと判断されて
しまうからである。黒画素領域の境界を追跡し接触個所
を切りはなす方法（向田、鈴木、阿部著“境界追跡を用
いた流れ図中の文字と図形の分離−文字と図形が接して
いる場合”第28回情報処理学会全国大会 IN-4 1984/
3）も提案されているが非常に時間がかかる処理である
し、図形の一部分が切り離されてしまうおそれがある。

方法（４）では前処理によつて文字と他の図形が接触す
る頻度がますので検出漏れの可能性はさらに高くなる。

方法（３）では数字などの簡単な構造の文字の列に関す
る複雑度が低くなり、他の図形との識別が困難になる。

D.問題点を解決するための手段 多くの文書中に出現する文字列は次のような性質を持つ
ている。

１）文字はほぼ水平または垂直に書かれている。

２）水平の場合の文字の高さ、垂直の場合の文字の幅は
文字列中でほぼ一定。

３）ある文字列の上下左右には他の図形要素を隔てる白
ランが存在する。（必ずしも文字列の回りに白画素の連
結領域が存在するわけではない。）したがつて画像中の
個々の文字列領域を細長い長方形で近似的に表現するこ
とができる。文字列を検出するためにはこの長方形の上
下（水平に書かれている場合）・左右（垂直に書かれて
いる場合）の辺を検出すればよい。

好適な実施例では、辺の検出は、白ランにローバスフイ
ルタリングを行つて文字列領域内の空白を黒画素で埋め
た画像を考え、その画像内の黒画素連結領域の上下（左
右）の境界線分候補を求めることにより行う。

E.実施例 （Ｉ）アプリケーシヨン全体の概略 第１図に文字連検出のアプリケーシヨンの処理の概略を
示す。対象としたアプリケーシヨンは自動車の補修用部
品番号の入力システムである。このシステムは、第２図
にその一部を示すような補修用カタログの分解図（各部
品のイラストとその番号が印刷されている）をスキヤナ
ーより読みこみ、部品番号をあらわす文字列を抽出した
後、文字認識プログラムにより文字コードに変換する。
大きな画像（約640k bytes）中にイラストとともに点
在する文字列を抽出しなければならないため、従来は専
用ハードウエアかエンジニアリング・ワークステーシヨ
ンでなければ困難だとされていたアプリケーシヨンであ
る。

（II）文字列検出 以下に、文字列検出の実施例について説明する。

境界線分の検出 画像をラスター走査して、１ライン分ずつイメージを読
みこみ、ランレングス表現に変換する。このとき、黒ラ
ンと黒ランの間の白ランが短い場合には二つの黒ランを
連結して一つの黒ランとして、その位置データ（今の場
合は、始点位置と長さ）を発生し、記録しておく。これ
をグループ化ランレングス表現と呼ぶことにする。以後
の処理はこのグループ化ランレングス表現上で行なわ
れ、画像に対するアクセスは生じない。

第３図は、ライン・イメージのグループ化ランレングス
表現への変換を例示したものである。ここでは、長さが
20未満の白ラン3A、3B、3Cを無視している。理解を容易
にするために、第３図中では中間のランレングス表現も
記載したが、実際にはライン・イメージからグループ化
ランレングス表現が直接作られる。

グループ化ランレングス表現への変換は本来ならば１ド
ツトずつ調べて行わなければならない処理であるが、本
方式では、第４図に示す一連のステツプに従つて、バイ
トまたはワード単位での処理を可能にしている。グルー
プ化の際にはある長さ以下の白ランを無視してその左右
の黒ランとして表現しているが、その閾値はバイト長
（８）やワード長（16）よりも大きい。したがつて第５
図のように読みこまれた８または16ビツト長のデータが
複数の黒ランを含んでいても、黒ランの間に挟まれた白
ラン5A、5Bの長さを調べるまでもなく、それらは連結し
ているものとして処理できる。つまり、白ラン5A、5Bは
無視される。ランレングス表現に変換するためには左端
の黒ランの始点とそこから右端の黒ランの終点までの長
さがわかればよい。これらの値をバイトの場合は2⁸個、
ワードの場合は2¹⁶個のパターンに対して求めてテーブ
ルにしておき参照することにより、バイト（ワード）単
位で画像を読みこみ、あるバイト（ワード）の右端の白
ラン長と次のバイト（ワード）の左端の白ラン長を加算
して無視できる長さの白ランかどうかを判定し、グルー
プ化ランレングス表現に変換してゆくことができる。

連続する２ライン分のイメージがグループ化ランレング
ス表現に変換されたところで、これら２ラインに関する
黒ランの位置データを比較して、文字列領域（矩形）の
上下の境界候補となる黒ランを検出する。第６図に示す
ように、ある黒ランの上が白ランあればその黒ランは上
の境界候補の一部であるとし、逆に黒ランの下に白ラン
がある場合はその黒ランは下の境界候補の一部だと判断
する。

第７図に示す一連のステツプに従つて、ランレングスで
表現された黒ランの始点の位置と長さを比較することに
より、上下の境界候補を検出することができる。第７図
において、黒ランの位置データとは黒ランの始点の位置
と長さの組みを意味する。また、図中の処理で境界候補
をもとめるとは境界候補の始点と長さを計算することを
いう。具体的には、第8A図に示すように、黒ランＡとそ
の下の黒ランＢが重なつている場合は始点がmin（Ａの
始点、Ｂの始点）で長さがmax（Ａの始点、Ｂの始点）
−min（Ａの始点、Ｂの始点）であるようなラン、第8B
図に示すように黒ランＡとＢの重なりのない場合はＡと
Ｂのうち始点の値の小さいランそのものの位置データを
求めることになる。

境界候補の検出を画像全体に対して行うときはグループ
化ランレングス表現を記録しておく領域を２ライン分用
意しておき、ｉライン目とｉ＋１ライン目のデータの比
較が終わつたらｉ＋１ライン目のデータをｉライン目の
データのあつた領域に移し（実際にはポインタの付け替
えですむ）、ｉ＋１ライン目のデータをおいていた領域
にｉ＋２ライン目のイメージに対するグループ化ランレ
ングス表現をセツトすることにる。

境界候補の検出跡、第9A図ないし第9C図に示すように、
適当な閾値の範囲内で縦方向のずれや左右のとぎれをつ
なげる処理を行つてもよい。

文字列の検出 上境界候補すべてについて次の条件を満たす下境界候補
が存在するか調べる。

条件1:下境界候補が上境界候補の下にあり、Ｙ座標の差
がある範囲内（文字の高さの最小値と最大値の間）であ
る。ここで、Ｙ軸は副走査方向に対応する。

条件2:二つの境界線分候補の始点の位置と長さがある閾
値内で等しい。これらの条件が満たされたとき、二つの
境界線分候補のそれぞれの少なくとも一部を上下の端と
する文字列領域が存在すると判定する。

上境界候補と下境界候補の組合せに基づいて文字列領域
だと判断される矩形は、インプリメント（閾値）次第で
いかようにも変えることができる。このアプリケーシヨ
ンにおいては、第9C図に示される上下の境界候補の対を
例にとると、始点の位置と長さがある閾値内で等しいと
判断され、第10図に示す矩形101が文字列領域だと判定
される。そして、左上の頂点101Aの位置（XY座標）およ
び２辺101B、101Cの長さが矩形101の位置データとして
発生される。第11図に示すような上下の境界の対を例に
とると、矩形111が文字列領域だと判定され、その位置
データが発生される。

境界線分候補を上下の端とする長方形は必ずしも文字列
の外接長方形とはならないが前に述べたように文字列の
おおよその位置と大きささえわかつていれば個々の文字
の切り出し時または認識時にその補正を行うことは容易
である。

（ハ）その後の処理 第１図のアプリケーシヨンでは最初に文字列検出ルーチ
ンが画像を１回走差した後、検出した文字列の位置デー
タをテーブルにセツトする。システムはこのテーブルの
データにしたがつて文字列周辺のイメージをロードし、
文字列の正確な外接長方形をもとめ、個々の文字の切り
出しと認識を行う。文字列検出ルーチンがイラストの一
部を文字列として検出してしまうこともあるが、それら
は文字の切り出しや認識の過程でチエツクされリジエク
トされる。

なお、第１図に示す後処理ルーチンはアプリケーシヨン
固有の知識を利用して誤りの検出や回復を行うルーチン
である。

本実施例の長所を以下に述べる。

１）処理速度 本発明における画像へのアクセスはラスター走査１回分
ですみ、アクセスの単位もバイト（ワード）単位であ
る。したがつて従来方法のどれよりも速い処理が期待で
きる。実際にパソコン（CPUはインテル社の80286 8MHz
メモリーウエイト有り）上でＣ言語を用いてインプリメ
ンテーシヨンを行い、第２図にその約1/6を示す図面に
対して文字列検出を行つたところ37秒（イメージの入力
を除く）ですべての部品番号を検出することができた。
２）検出精度 本発明ではイラスト中の文字列や図形と接触している文
字列であつても問題なく検出することができる。短い白
ランを無視するため左右の図形と連結してしまう文字列
もあるが他の図形との接触のために上下の境界そのもの
がなくなつてしまうことはないからである。

３）圧縮データに対応可能 本発明はランレングス表現上で処理を行つており画像の
走査もラスタースキヤン１回ですむので、MH方式やMMR
方式により圧縮されたデータを処理することが容易であ
る。これは従来方法（１）、（３）、（４）には無い特
長である。

４）省メモリー 本発明で画像を走査するさいに必要になる作業領域は画
像１ライン分とランレングス表現２ライン分のみであ
る。また走査の過程で記録される境界線分候補は、ラン
レングス表現への変換、白ランを埋めて１本の黒ランで
表す、上下の境界となるランだけを残す、という３段階
の圧縮・ふるいが行なわれた結果であり、必要な主記憶
領域が少なくてすむ。

５）特定の大きさ（主に高さ）の文字列のみを検出の対
象にすることが可能。

いずれの方法であつても文字列の外接長方形が求まつて
しまえば特定の大きさの文字列を選ぶことは可能である
が、本発明では検出の過程において指定された範囲外の
大きさの文字列をふるいにかけることができる。このた
め、例えば見出しの文字列だけを検出する等の作業が他
の方式より高速に行える。

６）水平線分の検出が可能 文字列と同様に水平線分の検出を行うことができる（上
境界線分候補と下境界線分候補のＹ座標の左が閾値以下
であれば文字列ではなく水平線分と判断される）。
「ｙ」や「ｑ」と接触しているアンダーラインの検出が
可能であり、個々の文字の切り出しの際に有用な情報と
なる。

以上の説明は読取対象となる文字列（複数個の文字で構
成されている）が横方向（ラスター走査の主走査の方
向）に延びている場合について行つた。文字が縦に書か
れている場合には、前処理で画像を回転させる（90度単
位の回転を行う程度のハードウエアは、パソコンでも利
用可能になつてきている）、スキヤン時に図面を横にお
いて入力する等の工夫により、画像内において文字列の
延びる方向と該画像の主走査の方向とを一致させてやれ
ばよい。

一つの文字が他の文字と極端に離れて書かれている場合
については、上下の境界線分候補の組みを調べる際
（（II）のの部分）の閾値の決め方である程度対応で
きる。ただし、文字以外の図形を文字として検出してし
まう割合が高くなる。

原稿が様々な方向に延びる文字列を含む場合には本発明
は不利だが、実質的に一方向に延びる文字列のみを含む
原稿については本発明はきわめて有利である。

F.効果 本発明によれば、実質的に同一方向に延びる文字列のみ
を含む原稿を読取つて得られる画像の中の文字列領域
を、高速かつ高精度で検出することができる。しかも、
本発明は汎用パソコン上で容易にインプリメントができ
る。

【図面の簡単な説明】

第１図は、本発明を利用した部品番号入力システムの処
理の概略を示すフローチヤート、第２図は、本発明で処
理される図面の例、第３図は、グループ化ランレングス
表現を説明するための図、第４図はライン・イメージを
グループ化ランレングス表現に変換する処理を説明する
ためのフローチヤート、第５図は、バイト（またはワー
ド）内の黒ランにはさまれた白ランは無視して処理が行
えることを説明するための図、第６図は上境界・下境界
候補を説明するための図、第７図は、グループ化ランレ
ングス表面を比較して境界候補を検出する処理を説明す
るためのフローチヤート、第8A図および第8B図は、検出
される境界候補を２つの異なる場合について説明するた
めの図、第9A図ないし第9C図は、境界候補の上下のずれ
や左右のとぎれをつなげる処理を説明するための図、第
10図および第11図は文字列領域だと判断される矩形を説
明するための図である。 また、第12図、第13図、第14図はそれぞれ従来方法の
（２）、従来方法の（３）、連長フイルタリング処理を
説明するための図である。

Claims (1)

【特許請求の範囲】
1. 【請求項１】実質的に同一方向に延びる文字列のみを複
   数個含む原稿を読み取つて得られる画像の中の文字列領
   域を検出する方法であつて、 （ａ）上記画像において上記文字列の延びる方向を該画
   像の主走査方向と一致させて、上記原稿の画像データを
   画像メモリに記憶し、 （ｂ）上記画像メモリにアクセスして上記画像を走査す
   ることにより、各ラインごとに、該ライン中の黒ランの
   位置データを発生し、 （ｃ）上記画像中の隣接する２つのラインの対の何れに
   ついても、上記（ｂ）のステツプで得られた該２つのラ
   イン中の黒ランの位置データを比較し、後行ライン中の
   黒ランに先行ライン中の黒ランとは隣接しない部分があ
   れば、該部分を文字列領域の第１種の境界候補と判断し
   てその位置データを発生し、かつこれを記憶手段中のテ
   ーブルに記憶するとともに、先行ラインの黒ランに後行
   ライン中の黒ランとは隣接しない部分があれば、該部分
   を文字列領域の第２種の境界候補と判断してその位置デ
   ータを発生し、かつこれを上記テーブルに記憶し、 （ｄ）上記テーブルを参照して、上記主走査方向に関す
   る位置が共通する部分を持つ上記第１種の境界候補と第
   ２種の境界候補の対を決定し、対をなす境界候補のそれ
   ぞれの少なくとも一部を境界として持つ矩形領域を文字
   列領域と判断してその位置データを発生する ことを特徴とする文字列検出方法。