[go: up one dir, main page]

JPH05166002A - ソース画像を分析する方法 - Google Patents

ソース画像を分析する方法

Info

Publication number
JPH05166002A
JPH05166002A JP4134588A JP13458892A JPH05166002A JP H05166002 A JPH05166002 A JP H05166002A JP 4134588 A JP4134588 A JP 4134588A JP 13458892 A JP13458892 A JP 13458892A JP H05166002 A JPH05166002 A JP H05166002A
Authority
JP
Japan
Prior art keywords
text
white
black
graphics
image
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Withdrawn
Application number
JP4134588A
Other languages
English (en)
Inventor
Zeira Azaf
アザフ・ゼイラ
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
SAITETSUKUSU CORP Ltd
Scitex Corp Ltd
Original Assignee
SAITETSUKUSU CORP Ltd
Scitex Corp Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by SAITETSUKUSU CORP Ltd, Scitex Corp Ltd filed Critical SAITETSUKUSU CORP Ltd
Publication of JPH05166002A publication Critical patent/JPH05166002A/ja
Withdrawn legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T7/00—Image analysis
    • G06T7/10—Segmentation; Edge detection
    • G06T7/12—Edge-based segmentation
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T7/00—Image analysis
    • G06T7/10—Segmentation; Edge detection
    • G06T7/194—Segmentation; Edge detection involving foreground-background segmentation
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V30/00—Character recognition; Recognising digital ink; Document-oriented image-based pattern recognition
    • G06V30/40—Document-oriented image-based pattern recognition
    • G06V30/41—Analysis of document content
    • G06V30/413—Classification of content, e.g. text, photographs or tables
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T2207/00—Indexing scheme for image analysis or image enhancement
    • G06T2207/10—Image acquisition modality
    • G06T2207/10004—Still image; Photographic image
    • G06T2207/10008—Still image; Photographic image from scanner, fax or copier
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T2207/00—Indexing scheme for image analysis or image enhancement
    • G06T2207/30—Subject of image; Context of image processing
    • G06T2207/30176—Document

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Artificial Intelligence (AREA)
  • Multimedia (AREA)
  • Image Analysis (AREA)
  • Character Input (AREA)

Abstract

(57)【要約】 （修正有） 【目的】入力されたソース画像データを分析してテキス
トデータ部とグラフィクスデータ部に分解して出力す
る。 【構成】入力画像を白，黒の２値データで表わし白と黒
の境界にあるピクセルを検出しこれを追跡することによ
り白又は黒領域の輪郭を得る。輪郭データを用い白又は
黒領域の形状を得、このデータをもとに対象物がテキス
トデータであるかグラフィックスデータであるか判別
し、それぞれ別に出力する。

Description

【発明の詳細な説明】
【０００１】
【発明の背景】この発明はテキストとグラフィックスと
を判別して、それによってテキストをグラフィックスか
ら分離するために、文書または他のソース画像を分析す
る方法に関する。
【０００２】テキストとグラフィックスとの判別は文書
を処理するときにしばしば本質的なことである。たとえ
ば、いくつかの文書処理応用はグラフィックス（または
テキスト）にのみ関与する。他の文書処理応用はテキス
トおよびグラフィックスに異なったプロセスを応用し、
かつしたがってテキスト、グラフィックスおよび中間調
の領域に画像を区分化しなければならない。
【０００３】テキストとグラフィックスとを判別するす
べての応用はその２つの間を識別する定義を要求する。
いくつかはテキストを列でグループ分けされた文字とし
て規定する一方で、孤立して現われる文字はグラフィッ
クスと考えられる。他のものはフォントまたはサイズに
かかわらずどこで現われようとテキストを文字として規
定する。後者の規定はより適切であるように見えるが、
誤分類という結果、たとえば円が文字「０」と誤分類さ
れ得るという結果をもたらす。どちらの定義が使われよ
うと、文献に提唱される大半のアルゴリズムははるかに
高価な真の文字認識を行なわず、むしろ分類のための単
純なヒューリスティックスを使用する。
【０００４】テキストがグラフィックスから判別される
２つの主要なアプローチがあり、それは「トップダウ
ン」および「ボトムアップ」である。「トップダウン」
アプローチにおいて、画像はさらに次の領域に区分され
る主要な領域にまず区分される。「ボトムアップ」アプ
ローチにおいて、画像は個々に接続された成分を決定す
るためにまず処理される。これらの成分は、文字として
識別されたとき、単語に、単語を文章に、等々とグルー
プ分けされる。トップダウンアプローチは知識に基づい
たものである。それはテキストおよびグラフィックスの
厳密に分離された領域からなる画像にのみ適切である。
グラフィックス領域内にあるテキスト単語はグラフィッ
クスとして分類される。一方ボトムアップアプローチは
より信頼性は高いが時間がかかる。したがって、２つの
アプローチは組合せて使用されるべきであり、まずトッ
プダウン方法がグラフィックス領域を検出して、それか
らボトムアップ方法がこれらの領域内のテキストを検出
するであろう。
【０００５】ラン長不鮮明アルゴリズム（ＲＬＳＡ）は
トップダウン方法の一例である。このアルゴリズムは画
像をテキストライン、グラフィックスおよび中間調画像
の主要領域に区分化して分類する。このアルゴリズム
は、もし隣接する０の数が予め規定されたしきい値より
少なければ０を１に置換える（０は白のピクセルに対応
し、かつ１は黒のピクセルに対応する）。この一次元的
動作はラインごとにおよび列ごとに二次元的ビットマッ
プ画像に適用される。２つの結果が局所ＡＮＤを各ピク
セル場所に適用することによってそれから結合される。
結果として生じる画像は印刷された材料がもとの画像上
に現われて不鮮明の効果を生み出すところではどこでも
黒のブロックを含む。ブロックはそれから統計的なパタ
ーン分類（たとえば、ブロックにおける黒のピクセルの
数、水平な白／黒遷移の数）を用いてテキストライン、
グラフィックスまたは中間調画像として分類される。
【０００６】ＲＬＳＡアルゴリズムは速度は速いが画像
のあるクラスに制限される。これらの画像にはスキュー
されたテキストラインは許容されないし、文字の寸法は
予め規定されたしきい値パラメータに適合しなければな
らず、そうしなければ、文字は（もしパラメータがあま
りに小さければ）孤立されたままであり、またはテキス
トラインは（もしパラメータがあまりに大きければ）結
合されるであろう。
【０００７】大まかな分類が「トップダウン」アルゴリ
ズムによって受理された後、グラフィックブロックは詳
細な分類を得るために「ボトムアップ」アルゴリズムに
よってさらに処理される。ボトムアップアルゴリズムは
個々に接続された成分を決定するためのプロセスで始ま
る。接続された成分検出を行なう数個のアルゴリズムが
既知である。これらのアルゴリズムは画像上の１つのラ
スタスキャンの間にできるだけ多くの情報を抽出するた
めにチェーンコード発生アルゴリズムに結合され得る。
かかる「結合された」アルゴリズムはラン長フォーマッ
トされた画像上で速く動作可能である（実行時は画像の
境界線の長さに大まかに比例する画像の「ラン」の数に
比例する）。かかるプロセスの終りに、以下の生の情報
が各接続された成分に対して利用可能であり、それは
（１）領域（接続された成分を形成するピクセルの
数）、（２）境界のチェーンコード記述（各境界につき
１つのチェーン）および（３）取囲んでいる接続された
成分および取囲まれた接続された成分の識別である。
【０００８】この生の情報はさらに処理されて他の属性
を導出することが可能であり、それは（４）取囲んでい
る長方形、（５）オイラー（Euler)の数（オイラー数＝
１− 形をなす穴（holes in shape）の数）、（６）周
囲長（境界の全長）および（７）包領域である。
【０００９】（４）−（７）の属性以外のより多くの形
状属性が（１）−（３）の情報から導出され得るが、属
性（４）−（７）は最小の効果で文字記号の判別をする
ために非常に貴重である。オイラーの数は付加的な努力
なしに利用可能である（オイラーの数＝２ − チェー
ンの数）。取囲んでいる長方形はチェーン上の１つのス
キャンで計算され得る。ペリメタ長はチェーンコードの
リンクの総数と大まかに等しい。よりよい推定が他の方
法で得られるが、この推定はかなり良い。包領域はまず
凸包多角形を発見して、それから単純なタスクであるそ
の多角形の領域を発見することによって計算され得る。
【００１０】局部形状特徴に従ってテキストを判別する
大半のアルゴリズムは上に挙げられた属性を使用する。
局部形状特徴に基づくアルゴリズムは２つの主要な欠点
を有し、それは（１）グラフィックスをテキストとして
誤分類し得る（円が「０」として分類され得る）こと
と、（２）変則の列を検出できない（たとえば、それら
は点線をグラフィックスとして検出できずに、その代わ
り各マイナス符号は文字記号として検出され、かつ全体
の列はテキストとして検出される）ことである。
【００１１】これらの欠点は既知のテキスト−ストリン
グ分離アルゴリズムで修理されたが、処理時間という高
い犠牲を払った。文字を列にクラスタリングするプロセ
スはその時間の大半を占める。アルゴリズムはハフ（Ho
ugh ）変換を使用して共通直線状成分を検出し、もしそ
れらがある統計上のパターンと一致すれば、それらを単
語および句にグループ分けする。アルゴリズムは変則の
列をグラフィックスとして分類することに成功するが、
パラメタ設定に敏感であり、誤った選択は１つのライン
に属する接続された成分が異なったセルにグループ分け
されること（不十分なグループ分け（ｕｎｄｅｒｇｒｏ
ｕｐｉｎｇ））を引起こすか、または数個の平行な列が
単一のセルにグループ分けされる（過度のグループ分
け）ことを引起こし得る。ハフ変換はまた一グループの
垂直成分を、これらの成分が水平なテキストラインの一
部であるにもかかわらず、垂直な列として誤って検出し
得る。
【００１２】他の困難な点は、（直線配向よりはむし
ろ）弧配向を有する列はテキストとして判別されないこ
とである。同じことが短い孤立された列（３より少ない
文字を含む列）に起こる。
【００１３】上述のアルゴリズムのすべてはフォントサ
イズの大きな変化を含む画像間をきちんと判別すること
ができない。さらにそれらは逆にされたテキストのブロ
ックを扱うことができない（逆にされたテキストは黒の
背景に対して白のテキストである）。
【００１４】
【発明の目的および概要】この発明の目的はグラフィッ
クスからテキストを分離するためにソース画像を分析す
るための、上の点の１つ以上で利点を有する新規の方法
を提供することである。
【００１５】この発明に従って、テキストをグラフィッ
クスから分離するためのソース画像を分析する方法が提
供され、テキストをグラフィックスから分離するために
ソース画像を分析する方法を含み、その方法は（ａ）黒
および白の対象物を含む２進の画像を得るためにソース
画像を走査してデジタル化するステップと、（ｂ）フィ
ルタされた２進画像を得るために２進画像からノイズを
フィルタして取除くステップと、（ｃ）フィルタされた
２進画像から黒の対象物と白の対象物の輪郭を抽出する
ステップと、（ｄ）対象物間の包含関係を評価してかか
る関係のツリーのような構造を発生するステップと、
（ｅ）各対象物の形状属性を得るために対象物を測定す
るために前記輪郭を利用するステップと、（ｆ）測定さ
れた形状属性および包含関係の発生されたツリーのよう
な構造に従ってグラフィックスまたはテキストとして対
象物の分類を行なうステップと、さらに（ｇ）対象物の
前記ソース画像と前記分類とを利用してそれぞれグラフ
ィックスおよびテキストを表わす出力を発生するステッ
プとを含む。
【００１６】以下に述べられるこの発明の好ましい実施
例のさらなる特徴に従って、ステップ（ｂ）において、
ノイズは黒のピクセルの膨張によってフィルタで取除か
れ、ステップ（ｅ）において、対象物はツリーのルーツ
にある対象物で始まるトップダウンシーケンスで測定さ
れ、およびステップ（ｃ）において、フィルタされた２
進画像から黒の対象物および白の対象物の輪郭を抽出す
ることは窓がラスタの態様でフィルタされた２進画像と
ともに巻込まれる単一の走査によって行なわれる。加え
て、窓はラインに沿って画像を走査し、かつ窓から見ら
れるパターンの型の表示および窓の中心の表示を戻し、
各型のパターンは異なって処理されて新しい対象物が開
始され、継続されまたは終えられるかどうかを決定し、
すべての対象物は平行に処理されている現在の走査ライ
ンと交差する。
【００１７】述べられた好ましい実施例において、最大
点に窓走査の間に遭遇する場合、それは新しい対象物の
開始点であると考えられるが、もし後に走査がそれは以
前に示された対象物の最大点であったことを示せば、新
しい対象物は以前に示された対象物のそれと合併され
る。
【００１８】この発明のさらなる特徴は以下の説明から
明らかであろう。この発明を添付の図面を参照して、例
によってのみここに説明する。
【００１９】
【好ましい実施例の説明】
【００２０】
【全体のシステム】図１はこの発明に従ってソース文書
２を分析してテキストをグラフィックスから分離するた
めの方法を絵で表わして例示し、テキストは文書４で出
力され、かつグラフィックスは文書６で出力される。例
の目的のために、かつこの方法の能力を示す目的のため
に、ソース文書２は、図２で拡大して示されるように、
異なったサイズ、配向およびフォントのグラフィックス
およびテキストを含む。
【００２１】このように、テキストおよびグラフィック
スの両方のソース画像を含むソース文書２はオプチカル
スキャナ８によって走査され、かつその出力は画像ディ
スク１２、メモリ１４およびＣＰＵ１６を含む一般に１
０で示される画像処理システムに送られる。画像処理シ
ステム１０は２つの文書４および６の形状でプロッタ１
８を経て処理情報を出力し、文書４は元の文書２のテキ
ストを含み、かつ文書６は元の文書２のグラフィックス
を含む。
【００２２】図３は一般にブロック２１−２７によって
示され、画像処理システム１０によって行なわれる７つ
の基本ステップ（ａ−ｇ）を例示するフロー図であり、
そのステップは （ａ） 黒および白の対象物を含む２進画像を得るため
にソース画像（文書２）を走査してデジタル化し（ブロ
ック２１）、（ｂ） フィルタされた２進画像を得るた
めに２進画像からノイズをフィルタして取除き（ブロッ
ク２２）、（ｃ）フィルタされた２進画像から黒の対象
物および白の対象物の輪郭を抽出し（ブロック２３）、
（ｄ） 対象物間の包含関係を評価してかかる関係のツ
リーのような構造を発生し（ブロック２４）、（ｅ）
各対象物の形状化された属性を得るために対象物を測定
するためにステップｃで検出された輪郭を利用し（ブロ
ック２５）、（ｆ） 測定された形状化された属性およ
びステップｄで得られた包含関係に従ってグラフィック
スまたはテキストとして対象物を分類し（ブロック２
６）、さらに（ｇ） 出力プロッタ１８を経て、それぞ
れテキスト（文書４）およびグラフィックス（文書６）
を表わす出力を発生する（ブロック２７）、というもの
である。
【００２３】以下は上のステップの各々のより詳細な説
明である。
【００２４】
【走査およびデジタル化（ブロック２１、図３）】この
ステップはソース画像の２進バージョンを得るために行
なわれる。このステップはソース画像のビットマップ表
示を含むディスクまたはテープ（たとえば画像ディスク
１２、図１）上の２進ファイルを生み出すためにオプチ
カルスキャナ、ＣＣＤ（電荷結合素子）スキャナなどに
よって実行され得る。ビットマップは各ビットが黒また
は白のピクセルに対応する状態でのビットの流れである
かまたはランにおいてコード化され得る。ラン長符号化
が使用されて、それによって黒（または白）のピクセル
のシーケンスがシーケンスの長さが色の次の遷移までで
ある状態で色によってコード化されると仮定される。走
査の典型的な解像度は５０ピクセル／ｍｍである。
【００２５】図４は走査およびデジタル化ステップを図
表で例示し、３１で示されるようなソース画像は、３２
で示されるようなソース画像のデジタル化されたビット
マップ表示に転換されることが理解されるであろう。図
４のソース画像３２のビットマップ表示は画像データ３
２ａおよびノイズ３２ｂを含むこともまた理解されるで
あろう。
【００２６】
【フィルタリングノイズ（ブロック２２，図３）】図１
の画像処理システム１０によって行なわれる第２のステ
ップは、図３のブロック図で示されるように、ノイズフ
ィルタレーション、つまり図４の３２で例示されるビッ
トマップ表示におけるノイズ信号３２ｂの除去である。
このステップはもし最も近い黒のピクセルからの距離が
予め規定されたしきい値以下であれば白のピクセルを黒
に変える膨張オペレータによって実行される。
【００２７】このステップは図５で特に示され、膨張前
の画像データは、４１で示されるように、一グループの
黒のピクセル４１ｂに非常に近く、かつ４２で示される
ように膨張ステップの後単一のグループ４２ａを形成す
るために吸収される多数の孤立された黒のピクセル４１
ａを含む。この動作は、黒のピクセルを広げ、かつそれ
ゆえに孤立されたピクセルを一体に接続して、黒の対象
物の周囲にある孤立された黒のピクセルの数を大幅に減
少させる。
【００２８】単純な膨張アルゴリズムは、その周囲のす
べての入力ピクセルの連合であるよに出力ピクセルを設
定してもよい。
【００２９】膨張された画像４２は中間であり、かつ黒
と白の対象物の領域に画像を大まかに分割するためにの
み使用される。プロセスの後半で、以下に述べられるよ
うに、これらの領域は分類分けされて、かつ元の画像の
ピクセルはそれらが存在するクラスに従って適当に彩色
される。
【００３０】膨張によるノイズフィルタレーションは２
つの利点を与え、それは（ａ）もとの対象物の基本の形
状属性を維持すること、および（ｂ）もとの画像の黒の
ピクセルがどのクラスに属するかについての後の決定を
容易にすることである。
【００３１】膨張は多くの方法で達成され得る。ビット
マップ上で行なわれるときは、それは単純なハードウェ
アまたはソフトウェアによって達成され得るが、ラン長
符号化された画像上で行なわれるときは、それはより複
雑である。
【００３２】好ましくは、ラン長符号化の利点を利用す
るために、図６および図７のフロー図で、かつまたこの
発明の詳細な説明の終りにある付録Ａで例示されるよう
に、以下のアルゴリズムに従って動作する特定の装置が
使用される。
【００３３】
【輪郭検出（ブロック２３）】このステップにおいて、
膨張によって得られた画像は対象物を分類してその輪郭
を抽出するために走査される。対象物の輪郭は黒と白の
ピクセルの間を分離する対象物の境界を追跡するライン
セグメントのチェーンとして規定される。もし対象物が
中実でなければ（つまりそれが穴を含んでいれば）、こ
れらの穴の輪郭も同様に抽出される。したがって、対象
物は１つより多い輪郭を有し得る。
【００３４】図１０は輪郭抽出ステップを例示し、６１
で示される黒の対象物は対象物６１の境界を追跡するラ
インセグメントのチェーンから構成される輪郭６２に転
換されることが理解されるであろう。
【００３５】輪郭を抽出するためのかかるチェーン発生
のための多くのアルゴリズムが既知である。いくつかの
アルゴリズムは順次のアプローチを使用し、それによっ
て輪郭は他の輪郭が追跡される前に始めから終りまで追
跡される。しかしながら、このアプローチは画像上の多
くの走査という結果になり、特に画像が多くの大きな対
象物を含むときにそうであるので、したがって相当な時
間期間がかかり得る。
【００３６】好ましくは、単一の走査アプローチがこの
発明の方法で使用される。このアプローチにおいて、２
ｘ２窓はラスター態様で画像とともに巻込まれる。ラス
ター走査はコンパクトなラン長コード化から再び利益を
得ることができる、なぜなら全体の画像の代わりに色遷
移の場所しか検査される必要はないからである。
【００３７】一走査アプローチの全体の考えは以下のと
おりである。窓は画像を走査しかつ窓から見られるパタ
ーンの型の表示および窓の中心の位置の表示を戻す。パ
ターンの各型は新しい対象物が開始され、継続されまた
は終えられるかどうかを決定するために別に処理され
る。現在の走査ラインによって交差されるすべての対象
物は平行に処理される。新しい対象物は常に最大点で始
まり、かつ最小点で終るが、すべての最大点が必ずしも
新しい対象物を開始させるまたはすべての最小点が常に
存在する対象物を終らせるわけではない。最小点には何
の問題もない、なぜならそれらに到達する時間までに
は、それらが真の終りの点であるか否かを決定するため
の十分な情報が既に手元にあるからである。しかしなが
ら、最大点には曖昧さという問題がある。最大点に遭遇
するときに、この点が存在する対象物の局部の最大であ
るかまたは新しい対象物の大域の最大であるかどうかは
必ずしも決定される訳ではない。
【００３８】述べられたプロセスにおいて、最大点は常
に新しい対象物の開始点であると考えられる。もし後に
それが存在する対象物の開始点でったことが発見されれ
ば、真のものと人工のものの２つの対象物は合併され
て、人工の対象物が削除される。
【００３９】各最大点で、２つのチェーンが下方向に開
始され、かつ各最小点で２つのチェーンが接続される。
したがって、輪郭は始めは１つより多いチェーンから構
成され、かつ対象物が終るときのみチェーンは適切に接
続されて１つの閉ループの輪郭を形成する。各輪郭に対
して、２つのポインタが接続されて輪郭の右手および左
手側上の２つの対象物を指す。これらのポインタは対象
物間の包含関係を後で抽出することが可能である。
【００４０】図１１は特定のケースを例示し、図におい
て輪郭１はチェーンＡ−Ｆからなり、輪郭２はチェーン
Ｇ−Ｈからなりかつ輪郭３はチェーンＩ−Ｊからなる。
対象物１（背景）は輪郭１および３によって境界を定め
られ、対象物２は輪郭１および２によって境界を定めら
れ、対象物３は輪郭２によって境界を定められ、かつ対
象物４は輪郭３によって境界を定められることが理解さ
れるであろう。
【００４１】図１２および図１３はこのステップのため
に使用され得るアルゴリズムの一例を例示し、かつ図１
４は図１３のブロック７１および７２の動作について詳
述し、かつ異なった状態に対する決定表を例示する。こ
の発明の詳細な説明の終りの付録Ｂはこの目的のための
アルゴリズムの一例を例示する。
【００４２】
【ツリー発生（ブロック２４）】このステップにおい
て、対象物間の包含関係が評価され、かつかかる関係の
ツリーのような構造が発生される。この関係は分類のと
きに利用される、なぜなら１つの対象物内に含まれる対
象物に関する情報を有することはそれを適当なクラスに
割当てるために時として重要であるからである。この関
係は以前のステップで生み出された対象物および輪郭の
データベースから容易に抽出され得る。必要なことはた
だ、各対象物からのポインタをそれを含む対象物、つま
りその先行物に設定することである。このようにして、
ツリーのような構造が形成される。先行物を何も有さな
い１つの対象物があり、これは通常は白の背景である。
【００４３】対象物の先行物は以下のように発見され得
る。輪郭は常に反時計回りに指向されると仮定して、ま
ず輪郭のどれが最も外側であるかを発見し（対象物はも
しそれが穴を含めば１つより多い輪郭を有することが思
い出される）、かつそれからポインタをこの輪郭の右側
上の対象物を指すように設定する。この対象物が先行物
である。
【００４４】図１５は包含関係を決定するステップを図
表で例示する。図１５のグラフ９２は画像９１から得ら
れたツリーのような構造である。
【００４５】
【対象物測定（ブロック２５）】これは各対象物の形状
属性を得るために対象物を測定することを含む。以下の
基本要素が用いられ、つまり（ａ）対象物の領域（ピク
セルで測定される）、（ｂ）輪郭の数、および（ｃ）各
輪郭の周囲長（ピクセルで測定される）である。これら
の基本要素から、以下のこと、つまり（ａ）延長、
（ｂ）包領域、（ｃ）包異常、（ｄ）黒／白比率、
（ｅ）オイラーの数および（ｆ）はっきりした角の数が
決定される。
【００４６】延長は対象物を形成するラインの幅と対象
物の全体の寸法との間の比率を測定する。延長は以下の
ように計算される：
【００４７】
【数１】
【００４８】ここでＡは対象物の領域であり、かつＰは
対象物のペリメタである。包は対象物の境界を定める凸
状の多角形である。所与の組のポイントに対する凸状の
包を計算する速いアルゴリズムがある。
【００４９】包異常は包の幅と高さとの間の比率であ
る。黒／白比率は包領域と対象物の領域との間の比率で
ある。
【００５０】オイラーの数は対象物における穴の数を示
す。それは１マイナス穴の数として規定される。
【００５１】はっきりした角の数は以下のように計算さ
れ、まず輪郭の多角形の近似が発生される。この近似は
数回発生され、各回により大きなエラーしきい値を有す
る。これは多角形セグメントの数がエラーしきい値の増
加に対して直線状に下降し続ける限り行なわれる。最後
の近似ははっきりした角の数の評価のために使用され
る。はっきりした角は９５度より少ない角度を有する近
似している多角形における角である。
【００５２】図１６は対象物測定ステップ（ｅ）におけ
る多角形近似動作を行なうために使用され得る１つのア
ルゴリズムを例示するフローチャートである。
【００５３】
【対象物分類（ブロック２６）】このステップは対象物
をグラフィックスまたはテキストとして分類することを
含む。このステップにおいて、対象物はボトムアップ態
様で横断され、かつ前のステップで測られた測定値に従
って、かつツリーの連続する対象物に与えられたクラス
に従って分類される。分類は１組の予め規定された規則
およびしきい値に従って行なわれる。アルゴリズムＣは
図１７および図１８のフロー図で例示されたような規則
およびしきい値の例である。
【００５４】
【出力発生（ブロック２７）】このステップは図１の文
書４および６によってそれぞれ例示されるようなテキス
トおよびグラフィックスを表わす出力を発生することを
含む。
【００５５】このステップにおいて、もとの画像が再び
読出されかつ異なった色で書戻される。白のピクセルは
白のままであるが、黒のピクセルはそれらが存する対象
物のクラスに従って変化する（各クラスは異なった色を
割当てられる）。２つの隣接する黒のピクセルは決して
異なった色に塗られない、なぜなら膨張動作がそれらが
異なった対象物と関連することを妨げ、したがって、そ
れらが異なったクラスかつ異なった色を有することを妨
げるからである。
【００５６】黒のピクセルが再び塗られた後、全体のプ
ロセスが白のピクセルに対して繰り返され得る。つま
り、もし様々な白の対象物間を判別することが必要であ
れば、図３のフローチャートのブロック２１−２７のス
テップが再び実行されなければならないが、今回はステ
ップ２（ブロック２２）、つまり膨張ステップは白のピ
クセルに対して行なわれるべきであって、黒のピクセル
に対して行なわれてはならない。
【００５７】出力発生の問題はそれが存在する対象物を
各黒のピクセルごとに発見するという問題に実際はな
る。この対象物は直接クラスを規定し、かつクラスはそ
のピクセルに対する新しい色を規定する。
【００５８】図１９で例示されるような出力発生のため
に使用され得る１つのアルゴリズムは、この発明の詳細
な説明の終わりにあるアルゴリズムＤにおいて例示され
る。
【００５９】この発明を１つの好ましい実施例に関連し
て説明してきたが、この発明の様々な修正および他の応
用が行なわれ得ることは理解されるであろう。
【００６０】図３のフロー図は順次に行なわれるステッ
プを例示しているが、かかるステップはパイプラインの
態様で行なわれ得るしかつ好ましくは行なわれる。この
ように、入力窓を経て走査する間、対象物の終りが決定
されるとすぐ、対象物の出力の処理が対象物の最も高い
ラインから開始され得る。
【００６１】
【付録Ａ】以下はラン長コード化された画像の膨張のた
めのアルゴリズムである。
【００６２】ｄ − 距離しきい値。 ラインi − 入力ライン数ｉ。
【００６３】ラインi ′ − 出力ライン数ｉ。 ストリップi − ２ｄ＋１のラインのバッチ（ライン
i-d ′．．．，ラインi+d ）．
【００６４】
【数２】
【００６５】パターンは同一の座標で始まりかつ終る２
ｄ＋１のラインセグメントを含むストリップにおけるス
ライスである（図８参照）。パターンはそのパターンを
構成するラインセグメントに沿う色遷移を何も含まない
最も広いスライスであるという意味において最大であ
る。Ｐk ［ｉ］はＰk におけるｉ′番目のラインセグメ
ントの色である（図９参照）。
【００６６】
【付録Ｂ】
入力：画像が与えられたラン長フォーマット。
【００６７】出力：対象物およびチェーンのリスト。 対象物は以下のものを含む： ａ．対象物の色を記述するカラーコード。
【００６８】ｂ．対象物の領域（ピクセルの数） ｃ．対象物の輪郭を分割するチェーンへのポインタ。
【００６９】チェーンは以下のものを含む： ａ．輪郭のセグメントを記述するチェーンコード。
【００７０】ｂ．チェーンの長さ（リンクの数） ｃ．チェーンの両側上の対象物へのポインタ。
【００７１】アルゴリズムは以下の変数を使用する： ｘ，ｙ − 現在の走査場所へのポインタ。
【００７２】ライン０，ライン１ − ２つの連続する
入力ラインの内容を保持する。 ｇチェーン − 「成長する」チェーンのリスト。
【００７３】チェーンｐ − ｇチェーンにおけるチェ
ーンへのポインタ。
【００７４】
【数３】
【００７５】ステップ１で、フレーミングプロセスは画
像が読出されるときに同時発生的に行なわれ得る（ステ
ップ４および７）。ステップ１０において、変数ｘは最
小ランオフセットの座標に進められ、このようにどのラ
ンもスキップされない。各ランは２回処理され、一度は
ライン０のメンバーとして、かつ一度はライン１のメン
バーとして処理される。
【００７６】
【付録Ｃ】以下は対象物分類のためのアルゴリズムであ
る。
【００７７】
【数４】
【００７８】
【表１】
【００７９】
【付録Ｄ】以下は出力発生のためのアルゴリズムであ
る。
【００８０】ｌ − ランの長さ。 ｃ − ランの色。
【００８１】ｘ，ｙ − 画像における座標。
【００８２】
【数５】
【００８３】ステップ１１において、ポイント（ｘ，
ｙ）を含む対象物がサーチされる。このサーチはもし輪
郭検出の段階で発見されたチェーンがこの段階で使用さ
れるために記録されれば、大幅に単純化され得る。これ
らのチェーンは常に最大点で始まり、かつ対になって下
方向に進展する。したがって、アルゴリズムはファイル
で下方向に進展しながら追跡することが可能であり、そ
の対のチェーンは特定のラインで活性であり、かつこの
知識を使って各対のチェーン間に広がる対象物を発見す
る。
【００８４】この知識はこのプロセスをパイプラインで
可能にするためにさえも使用され得る。出力発生は新し
い対象物が完全に発見されかつ分類される分類モジュー
ルからの信号によってトリガされるであろう。
【図面の簡単な説明】
【図１】この発明の方法の１つの応用を例示する全体の
絵で表わした図でありる。
【図２】（Ａ）、（Ｂ）および（Ｃ）は異なったサイ
ズ、配向およびフォントにおけるグラフィックスおよび
テキストを含む典型的な文書を例示し、かつこの発明に
従ってそれが処理される結果を例示する図である。
【図３】この発明に従ってテキストをグラフィックスか
ら分離するためにソース画像を分析する方法における主
要なステップを例示するフロー図である。
【図４】図３の図における走査およびデジタル化ステッ
プ（ａ）を例示する図である。
【図５】図３のフロー図のステップ（ｂ）に従ってノイ
ズをフィルタするための膨張方法を例示する図である。
【図６】図３のフロー図におけるステップ（ｂ）を行な
うための１つのアルゴリズムを例示するフロー図であ
る。
【図７】図３のフロー図におけるステップ（ｂ）を行な
うための１つのアルゴリズムを例示するフロー図であ
る。
【図８】ステップ（ｂ）を理解する際に役立つ図であ
る。
【図９】ステップ（ｂ）を理解する際に役立つ図であ
る。
【図１０】図３のフロー図における輪郭検出ステップ
（ｃ）を例示する図である。
【図１１】ステップ（ｃ）を行なう一例をより詳しく例
示する図である。
【図１２】ステップ（ｃ）を行なうために使用され得る
アルゴリズムを例示するフロー図である。
【図１３】ステップ（ｃ）を行なうために使用され得る
アルゴリズムを例示するフロー図である。
【図１４】どのようにして異なった状態が取扱われるか
を示す図１２および図１３のアルゴリズムにおいて使用
される決定表の図である。
【図１５】図３のフロー図におけるツリー発生ステップ
（ｄ）を例示する図である。
【図１６】図３の対象物測定ステップ（ｅ）における多
角形の近似を行なうために使用され得る１つのアルゴリ
ズムのフロー図である。
【図１７】図３の分類ステップ（ｆ）を行なう際に使用
され得る１つのアルゴリズムを例示するフロー図であ
る。
【図１８】図３の分類ステップ（ｆ）を行なう際に使用
され得る１つのアルゴリズムを例示するフロー図であ
る。
【図１９】図３の出力発生ステップ（ｇ）を行なうため
の１つのアルゴリズムを例示するフロー図である。
【符号の説明】
２ ソース文書 ４ 文書 ６ 文書 ８ オプチカルスキャナ １０ 画像処理システム １２ 画像ディスク １４ メモリ １６ ＣＰＵ １８ プロッタ

Claims (16)

    【特許請求の範囲】
  1. 【請求項１】 テキストをグラフィックスから分離する
    ためにソース画像を分析する方法であって、 （ａ） 黒および白の対象物を含む２進画像を得るため
    にソース画像を走査してデジタル化するステップと、 （ｂ） フィルタされた２進画像を得るために２進画像
    からノイズをフィルタして取除くステップと、 （ｃ） フィルタされた２進画像から黒の対象物および
    白の対象物の輪郭を抽出するステップと、 （ｄ） 対象物間の包含関係を評価して、かつかかる関
    係のツリーのような構造を発生するステップと、 （ｅ） 各対象物の形状属性を得るために対象物を測定
    するために前記輪郭を利用するステップと、 （ｆ） 測定された形状属性に従ってグラフィックスま
    たはテキストとして対象物の分類を行ない、かつそれか
    ら包含関係のツリーのような構造を発生するステップ
    と、さらに （ｇ） それぞれグラフィックスおよびテキストを表わ
    す出力を発生するために対象物の前記ソース画像および
    前記分類を利用するステップとを含む、方法。
  2. 【請求項２】 ステップ（ｂ）において、ノイズは黒の
    ピクセルの膨張によってフィルタで取除かれる、請求項
    １に記載の方法。
  3. 【請求項３】 ステップ（ｅ）において、対象物はツリ
    ーのルーツにある対象物で始まるトップダウンシーケン
    スで測定される、請求項１または２のいずれかに記載の
    方法。
  4. 【請求項４】 ステップ（ｃ）において、フィルタされ
    た２進画像から黒の対象物および白の対象物の輪郭を抽
    出することは窓がラスタ態様においてフィルタされた２
    進画像とともに巻込まれる単一の走査によって行なわれ
    る、請求項１ないし３のいずれか１つに記載の方法。
  5. 【請求項５】 窓はラインに沿って画像を走査し、かつ
    窓から見られるパターンの型の表示および窓の中心の表
    示を戻し、各型のパターンは別に処理されて新しい対象
    物が開始され、継続されまたは終えられるかどうかを決
    定し、すべての対象物は平行に処理されている現在の走
    査ラインと交差する、請求項４に記載の方法。
  6. 【請求項６】 窓走査の間に遭遇される最大点は新しい
    対象物の開始点であると考えられるが、もし後に走査が
    それが前に示された対象物の最大点であったことを示せ
    ば、新しい対象物は以前に示された対象物のそれと合併
    される、請求項５に記載の方法。
  7. 【請求項７】 ステップ（ｄ）において、ツリーのよう
    な構造は各対象物からのポインタをその先行物に設定す
    ることにより発生され、対象物の先行物は対象物輪郭の
    どれが最も外側のものであるかを決定することによっ
    て、かつそれからポインタをその輪郭の一方側上の対象
    物を指すように設定することによって発見される、請求
    項１ないし６のいずれか１つに記載の方法。
  8. 【請求項８】 ステップ（ｅ）において、対象物は各対
    象物の以下の形状属性、つまり対象物の領域、輪郭の数
    および各輪郭の周囲長を得るために測定される、請求項
    １ないし７のいずれか１つに記載の方法。
  9. 【請求項９】 ステップ（ｅ）において、以下の付加的
    な属性、つまり延長、包領域、包異常、黒／白比率、オ
    イラーの数、およびはっきりした角の数が測定された形
    状属性から決定される、請求項８に記載の方法。
  10. 【請求項１０】 はっきりした角の数は多角形のセグメ
    ントの数がエラーしきい値の増加に対して直線状に降下
    する限り、各発生がより大きなエラーしきい値を有する
    状態で、輪郭の数個の多角形の近似を発生することによ
    って、さらにはっきりした角が最後の多角形の近似が６
    ０度より少ない角を有するときに存在することを決定す
    ることによって決定される、請求項９に記載の方法。
  11. 【請求項１１】 ステップ（ｇ）において、グラフィッ
    クスおよびテキストを表わす発生された出力は異なった
    画像の形状である、請求項１ないし１０のいずれか１つ
    に記載の方法。
  12. 【請求項１２】 ステップ（ｇ）において、グラフィッ
    クスおよびテキストを表わす発生された出力は同一の画
    像の異なった色の形状である、請求項１ないし１０のい
    ずれか１つに記載の方法。
  13. 【請求項１３】 ソース画像は異なったサイズ、配向お
    よび／またはフォントのテキストを含む、請求項１ない
    し１０のいずれか１つに記載の方法。
  14. 【請求項１４】 ステップ（ａ）−（ｇ）は、ノイズが
    白のピクセルの膨張によってステップ（ｂ）でフィルタ
    で取除かれる場合を除き繰り返されて、その結果ソース
    画像の白の対象物は分離され、それによって黒の背景に
    対する白のテキストおよびグラフィックスの判別を与え
    る、請求項２に記載の方法。
  15. 【請求項１５】 ソース画像は黒のテキスト、白のテキ
    スト、黒のグラフィックス、白のグラフィックス、黒お
    よび白の背景ならびに黒および白のノイズを含む、請求
    項１ないし１０のいずれか１つに記載の方法。
  16. 【請求項１６】 実質的に添付の図面に関連して説明さ
    れかつ添付の図面に例示されたような、テキストをグラ
    フィックスから分離するためにソース画像を分析する方
    法。
JP4134588A 1991-05-28 1992-05-27 ソース画像を分析する方法 Withdrawn JPH05166002A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
IL098293 1991-05-28
IL9829391A IL98293A (en) 1991-05-28 1991-05-28 A method for distinguishing between text and graphics

Publications (1)

Publication Number Publication Date
JPH05166002A true JPH05166002A (ja) 1993-07-02

Family

ID=11062477

Family Applications (1)

Application Number Title Priority Date Filing Date
JP4134588A Withdrawn JPH05166002A (ja) 1991-05-28 1992-05-27 ソース画像を分析する方法

Country Status (3)

Country Link
EP (1) EP0516576A2 (ja)
JP (1) JPH05166002A (ja)
IL (1) IL98293A (ja)

Cited By (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2000062243A1 (fr) * 1999-04-14 2000-10-19 Fujitsu Limited Procede et dispositif d'extraction de chaines de caracteres utilisant un composant de base d'une image de document
JP2001195571A (ja) * 2000-01-14 2001-07-19 Sony Corp 画像処理装置および方法、並びに記録媒体
US8792719B2 (en) 2011-07-29 2014-07-29 Brother Kogyo Kabushiki Kaisha Image processing device determining attributes of regions
US8830529B2 (en) 2011-07-29 2014-09-09 Brother Kogyo Kabushiki Kaisha Image processing device for accurately identifying region in image without increase in memory requirement
US8837836B2 (en) 2011-07-29 2014-09-16 Brother Kogyo Kabushiki Kaisha Image processing device identifying attribute of region included in image
US8929663B2 (en) 2011-07-29 2015-01-06 Brother Kogyo Kabushiki Kaisha Image processing device identifying region in image as one of uniform region and nonuniform region

Families Citing this family (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0724229B1 (en) * 1994-12-28 2001-10-10 Canon Kabushiki Kaisha Image processing apparatus and method
US6389162B2 (en) 1996-02-15 2002-05-14 Canon Kabushiki Kaisha Image processing apparatus and method and medium
JP4454789B2 (ja) 1999-05-13 2010-04-21 キヤノン株式会社 帳票分類方法及び装置
US6738512B1 (en) * 2000-06-19 2004-05-18 Microsoft Corporation Using shape suppression to identify areas of images that include particular shapes
US7311256B2 (en) 2000-12-19 2007-12-25 Zih Corp. Barcode optical character recognition
US6832726B2 (en) 2000-12-19 2004-12-21 Zih Corp. Barcode optical character recognition
US7596270B2 (en) * 2005-09-23 2009-09-29 Dynacomware Taiwan Inc. Method of shuffling text in an Asian document image
US20160110599A1 (en) * 2014-10-20 2016-04-21 Lexmark International Technology, SA Document Classification with Prominent Objects

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE3128794A1 (de) * 1981-07-21 1983-05-05 Siemens AG, 1000 Berlin und 8000 München Verfahren zum auffinden und abgrenzen von buchstaben und buchstabengruppen oder woertern in textbereichen einer vorlage, die ausser textbereichen auch graphik-und/oder bildbereiche enthalten kann.

Cited By (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2000062243A1 (fr) * 1999-04-14 2000-10-19 Fujitsu Limited Procede et dispositif d'extraction de chaines de caracteres utilisant un composant de base d'une image de document
US6701015B2 (en) 1999-04-14 2004-03-02 Fujitsu Limited Character string extraction apparatus and method based on basic component in document image
JP2001195571A (ja) * 2000-01-14 2001-07-19 Sony Corp 画像処理装置および方法、並びに記録媒体
JP4547752B2 (ja) * 2000-01-14 2010-09-22 ソニー株式会社 画像処理装置および方法、並びに記録媒体
US8792719B2 (en) 2011-07-29 2014-07-29 Brother Kogyo Kabushiki Kaisha Image processing device determining attributes of regions
US8830529B2 (en) 2011-07-29 2014-09-09 Brother Kogyo Kabushiki Kaisha Image processing device for accurately identifying region in image without increase in memory requirement
US8837836B2 (en) 2011-07-29 2014-09-16 Brother Kogyo Kabushiki Kaisha Image processing device identifying attribute of region included in image
US8929663B2 (en) 2011-07-29 2015-01-06 Brother Kogyo Kabushiki Kaisha Image processing device identifying region in image as one of uniform region and nonuniform region

Also Published As

Publication number Publication date
IL98293A (en) 1994-04-12
EP0516576A3 (ja) 1994-01-12
EP0516576A2 (en) 1992-12-02
IL98293A0 (en) 1992-06-21

Similar Documents

Publication Publication Date Title
US5050222A (en) Polygon-based technique for the automatic classification of text and graphics components from digitized paper-based forms
JP4065460B2 (ja) 画像処理方法及び装置
US5410611A (en) Method for identifying word bounding boxes in text
Shafait et al. Performance comparison of six algorithms for page segmentation
Wang et al. Classification of newspaper image blocks using texture analysis
JP3308032B2 (ja) スキュー補正方法およびスキュー角検出方法およびスキュー補正装置およびスキュー角検出装置
CN101453575B (zh) 一种视频字幕信息提取方法
JP3950777B2 (ja) 画像処理方法、画像処理装置および画像処理プログラム
Yuan et al. Text extraction from gray scale document images using edge information
US6711292B2 (en) Block selection of table features
JP2002133426A (ja) 多値画像から罫線を抽出する罫線抽出装置
US6532302B2 (en) Multiple size reductions for image segmentation
EP0483343A1 (en) A polygon-based method for automatic extraction of selected text in a digitized document
JPH05166002A (ja) ソース画像を分析する方法
Liang et al. Document layout structure extraction using bounding boxes of different entitles
JPH05225378A (ja) 文書画像の領域分割システム
JP2001043313A (ja) 文字切出し方法
Sas et al. Three-stage method of text region extraction from diagram raster images
JPH1125222A (ja) 文字切り出し方法及び文字切り出し装置
Rahman et al. Text Information Extraction from Digital Image Documents Using Optical Character Recognition
Aparna et al. A complete OCR system development of Tamil magazine documents
Bai et al. Object Boundary Encoding—a new vectorisation algorithm for engineering drawings
JPS58197581A (ja) 文字図形認識方法とその装置
JPH0981743A (ja) 文字・図形処理装置及び文字・図形処理方法
CN111723804B (zh) 图文分离装置、图文分离方法及计算机可读取记录介质

Legal Events

Date Code Title Description
A300 Application deemed to be withdrawn because no request for examination was validly filed

Free format text: JAPANESE INTERMEDIATE CODE: A300

Effective date: 19990803