JP5724341B2 - 画像処理装置及び画像処理プログラム - Google Patents

Description

本発明は、画像処理装置及び画像処理プログラムに関する。

画像から線分を抽出する処理に関する技術がある。
これに関連する技術として、例えば、特許文献１には、２値画像データ上の指定した線分のみを高速に部分消去したり、指定した線分のみを高速に検出しベクトル化処理できる方法を提供することを課題とし、画面上で消去線分の開始，終了点を指定すると、位置関係から線分追跡方向を求め、黒ランの探索方向を縦か横か決定し、開始点を含む一定領域内の画素データを探索し、端末処理を行い追跡線分の幅に相当する黒ランを検出する開始点処理を行い、この黒ランを起点に既検出黒ランと直交方向に連結した連結黒ランを検出し既検出黒ランを消去する逐次追跡消去処理を繰り返し、終了点を検出すると終了点処理を行い、途中でランレングスが急変すると交差点処理を開始し、ランレングスが元の値になると交差点区間の線分の消去及び復旧を一括行い、逐次追跡消去処理に戻り、交差点処理の間に終了点があれば中断して終了点処理を行うことが開示されている。

また、例えば、特許文献２には、２値図面イメージから線分が傾いていたり、途中で多少曲っていたり、途中で途切れていたりしても、線分を抽出できるようにすることを課題とし、ランデータ抽出手段は２値図面イメージを縦方向及び横方向で走査してランデータ群を抽出し、指示点検出手段は開始指示点及び終了指示点の位置を検出し、ランデータ選択手段は開始指示点、終了指示点間の傾きに応じて縦方向及び横方向のランデータ群の一方を選択し、開始ラン検出手段は選択されたランデータ群からラン長が規定値以下で開始指示点からの距離が最小のランデータを検出して開始ランとし、ラントレース手段は開始ランから終了指示点への方向につながるランデータを終了指示点の位置までトレースして得られたランデータのつながりを線分とすることが開示されている。

また、例えば、非特許文献１には、線要素を追跡し統合することで線を抽出するものであり、この追跡処理は、ある線要素につづく線要素を予測する予測処理と、予測された線要素に基づいて画素ランから線要素を観測する観測処理と、予測された線要素と観測された線要素に基づいて真の線要素を求める修正処理から成ることが開示されている。

特開平１０−０４９６８８号公報 特開平０８−０１６７８２号公報

Ａ． Ｌｅｍａｉｔｒｅ， Ｊ．Ｃａｍｉｌｌｅｒａｐｐ， "Ｔｅｘｔ Ｌｉｎｅ Ｅｘｔｒａｃｔｉｏｎ ｉｎ Ｈａｎｄｗｒｉｔｔｅｎ Ｄｏｃｕｍｅｎｔ ｗｉｔｈ Ｋａｌｍａｎ Ｆｉｌｔｅｒ Ａｐｐｌｉｅｄ ｏｎ Ｌｏｗ Ｒｅｓｏｌｕｔｉｏｎ Ｉｍａｇｅ，" Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｓｅｃｏｎｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄｏｃｕｍｅｎｔ Ｉｍａｇｅ Ａｎａｌｙｓｉｓ ｆｏｒ Ｌｉｂｒａｒｉｅｓ （ＤＩＡＬ’０６）， ２００６

本発明は、線ではない画像を線であると誤って抽出してしまうことを防止するようにした画像処理装置及び画像処理プログラムを提供することを目的としている。

かかる目的を達成するための本発明の要旨とするところは、次の各項の発明に存する。
請求項１の発明は、線の可能性がある画像に関する情報であって、線を構成し得る矩形の画素塊である線要素を示す情報の集合を受け付ける線情報受付手段と、前記線情報受付手段によって受け付けられた線要素を示す情報と線の追跡方向に基づいて、線の開始点から末尾点まで追跡を行うことによって線を抽出する線抽出手段と、前記線抽出手段によって抽出された線の末尾点を開始点とし、前記線の追跡方向を反転させ、前記線抽出手段へ該開始点と線の追跡方向を渡す反転手段と、前記反転手段による処理を行わせるか否かを判別する判別手段と、を具備し、前記判別手段は、前記線抽出手段又は前記反転手段による処理の回数を計数し、該回数と予め定められた回数とを比較することによって、該反転手段による処理を行わせるか否かを判別することを特徴とする画像処理装置である。

請求項２の発明は、前記判別手段は、前記線抽出手段の前回の処理による線の開始点又は末尾点と該線抽出手段の今回の処理による線の末尾点又は開始点とを比較することによって、前記反転手段による処理を行わせるか否かを判別することを特徴とする請求項１に記載の画像処理装置である。

請求項３の発明は、前記判別手段は、前記線抽出手段によって抽出された線の特徴量に基づいて、前記反転手段による処理を行わせるか否かを判別することを特徴とする請求項１に記載の画像処理装置である。

請求項４の発明は、前記線抽出手段は、文字列を含む画像から文字列の方向を線の追跡方向として、線を抽出することを特徴とする請求項１から３のいずれか一項に記載の画像処理装置である。

請求項５の発明は、前記線抽出手段は、枠線を含む画像から枠線の方向を線の追跡方向として、線を抽出することを特徴とする請求項１から３のいずれか一項に記載の画像処理装置である。

請求項６の発明は、コンピュータを、線の可能性がある画像に関する情報であって、線を構成し得る矩形の画素塊である線要素を示す情報の集合を受け付ける線情報受付手段と、前記線情報受付手段によって受け付けられた線要素を示す情報と線の追跡方向に基づいて、線の開始点から末尾点まで追跡を行うことによって線を抽出する線抽出手段と、前記線抽出手段によって抽出された線の末尾点を開始点とし、前記線の追跡方向を反転させ、前記線抽出手段へ該開始点と線の追跡方向を渡す反転手段と、前記反転手段による処理を行わせるか否かを判別する判別手段、として機能させ、前記判別手段は、前記線抽出手段又は前記反転手段による処理の回数を計数し、該回数と予め定められた回数とを比較することによって、該反転手段による処理を行わせるか否かを判別することを特徴とする画像処理プログラムである。

請求項１の画像処理装置によれば、本構成を有していない場合に比較して、判別処理の時間を削減できる。

請求項２、３の画像処理装置によれば、本構成を有していない場合に比較して、判別処理の精度を高めることができる。

請求項４の画像処理装置によれば、文字列とともに用いられる線を抽出することができる。

請求項５の画像処理装置によれば、枠線を含む画像からその枠線を抽出することができる。

請求項６の画像処理プログラムによれば、本構成を有していない場合に比較して、判別処理の時間を削減できる。

第１の実施の形態の構成例についての概念的なモジュール構成図である。 対象とする画像の例を示す説明図である。 スキャナ等で読み取られた画像の例を示す説明図である。 線抽出の例を示す説明図である。 ノイズがある線画像から線を抽出した例を示す説明図である。 往復処理の例を示す説明図である。 往復処理の例を示す説明図である。 往復処理の例を示す説明図である。 受け付けた画像の例を示す説明図である。 受け付けた画像から抽出した線要素の例を示す説明図である。 線要素の例を示す説明図である。 複数画素にまたがる線要素の例を示す説明図である。 予測と観測による線要素の統合処理の例を示す説明図である。 往復処理の例を示す説明図である。 反転処理の例を示す説明図である。 反転処理の例を示す説明図である。 反転処理の例を示す説明図である。 第２の実施の形態の構成例についての概念的なモジュール構成図である。 第３の実施の形態の構成例についての概念的なモジュール構成図である。 第４の実施の形態の構成例についての概念的なモジュール構成図である。 本実施の形態を実現するコンピュータのハードウェア構成例を示すブロック図である。

以下、図面に基づき本発明を実現するにあたっての好適な各種の実施の形態の例を説明する。
図１は、第１の実施の形態の構成例についての概念的なモジュール構成図を示している。
なお、モジュールとは、一般的に論理的に分離可能なソフトウェア（コンピュータ・プログラム）、ハードウェア等の部品を指す。したがって、本実施の形態におけるモジュールはコンピュータ・プログラムにおけるモジュールのことだけでなく、ハードウェア構成におけるモジュールも指す。それゆえ、本実施の形態は、それらのモジュールとして機能させるためのコンピュータ・プログラム（コンピュータにそれぞれの手順を実行させるためのプログラム、コンピュータをそれぞれの手段として機能させるためのプログラム、コンピュータにそれぞれの機能を実現させるためのプログラム）、システム及び方法の説明をも兼ねている。ただし、説明の都合上、「記憶する」、「記憶させる」、これらと同等の文言を用いるが、これらの文言は、実施の形態がコンピュータ・プログラムの場合は、記憶装置に記憶させる、又は記憶装置に記憶させるように制御するの意である。また、モジュールは機能に一対一に対応していてもよいが、実装においては、１モジュールを１プログラムで構成してもよいし、複数モジュールを１プログラムで構成してもよく、逆に１モジュールを複数プログラムで構成してもよい。また、複数モジュールは１コンピュータによって実行されてもよいし、分散又は並列環境におけるコンピュータによって１モジュールが複数コンピュータで実行されてもよい。なお、１つのモジュールに他のモジュールが含まれていてもよい。また、以下、「接続」とは物理的な接続の他、論理的な接続（データの授受、指示、データ間の参照関係等）の場合にも用いる。
また、システム又は装置とは、複数のコンピュータ、ハードウェア、装置等がネットワーク（一対一対応の通信接続を含む）等の通信手段で接続されて構成されるほか、１つのコンピュータ、ハードウェア、装置等によって実現される場合も含まれる。「装置」と「システム」とは、互いに同義の用語として用いる。もちろんのことながら、「システム」には、人為的な取り決めである社会的な「仕組み」（社会システム）にすぎないものは含まない。「予め定められた」とは、対象としている処理の前に定まっていることをいい、本実施の形態による処理が始まる前はもちろんのこと、本実施の形態による処理が始まった後であっても、対象としている処理の前であれば、そのときの状況・状態に応じて、又はそれまでの状況・状態に応じて定まることの意を含めて用いる。
また、各モジュールによる処理毎に又はモジュール内で複数の処理を行う場合はその処理毎に、対象となる情報を記憶装置から読み込み、その処理を行った後に、処理結果を記憶装置に書き出すものである。したがって、処理前の記憶装置からの読み込み、処理後の記憶装置への書き出しについては、説明を省略する場合がある。なお、ここでの記憶装置としては、ハードディスク、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、外部記憶媒体、通信回線を介した記憶装置、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）内のレジスタ等を含んでいてもよい。

第１の実施の形態である画像処理装置は、対象とする画像から線であるパタン（画像）を抽出するものであって、図１の例に示すように、線抽出モジュール１１０、往復判別モジュール１２０、反転処理モジュール１３０を有している。

まず、第１の実施の形態の対象とする画像１０６について説明する。
図２は、対象とする画像の例を示す説明図である。この画像内には、線である画像（パタン）と線でない画像がある。
図３は、図２に例示した画像をスキャナ等で読み取った画像（画素データ）の例を示す説明図である。このとき、スキャナ等での読み取りノイズ、点線、破線、線でないパタン等の影響により、抽出しようとする線は、対象としている画像において、必ずしも、直線とみなせる１つの領域として現れない。具体的には、線に対して、つぶれ、欠け等が発生する。

図４は、線抽出の例を示す説明図である。
線を、線の方向と交差する方向（例えば、直交）に連なる画素ランに対応する領域の集合と捉える。以下では、この領域を線要素とよぶ。
第１の実施の形態は、図４の例に示すように、抽出しようとする線に対応する画素ラン（すなわち、観測された線要素）を検出し、統合するものである。画素ランを統合した結果が線の画像となる。
また、これら画素ランに基づいて、真の線要素（すなわち、修正された線要素）を生成してもよい。例えば、図４では、点線で示した観測線要素４１１〜４２８は画像内の観測された線要素であり、灰色の矩形で示した修正線要素４５１〜４６８は観測線要素４１１等に基づいて修正された線要素である。例えば、観測線要素４１１と修正線要素４５１は同じであるが、観測線要素４１２は下に移動して修正線要素４５２となり、観測線要素４１４は上に移動して修正線要素４５４となり、観測線要素４２２と観測線要素４２５の間に観測された線要素はないが、修正線要素４６３と修正線要素４６４を追加している。

画像１０６には、線として抽出すべき画像であるが、その線には、曲り、欠け、つぶれ、線どうしの交差等が発生し得る。さらに、曲り、欠け等の位置は必ずしも既知でない。なお、点線、破線は欠けに含まれるとする。
図５は、ノイズがある線画像から線を抽出した例を示す説明図である。図５（ａ）の例に示す線には交差がある。
いま、対象とする画像１０６として図５（ａ）の例に示す線から、図５（ｂ）の例に示す線を抽出しようとする。
前述の特許文献１、特許文献２、非特許文献１に記載の技術を用いて図５（ａ）の例から線を抽出するとき、開始点探索走査５１０の最初の黒画素を開始線要素５２０とした場合、線抽出の始点を誤って与えることとなってしまう。そして、図５（ｃ）の例に示すように、線抽出方向５３０に線追跡を行って線を抽出することになるので、図５（ｄ）の例に示すように、誤った線を抽出することになる。

本実施の形態による処理の概要を説明する。
図６は、本実施の形態による往復処理の例を示す説明図である。図６（ａ）の例に示す線は、図５（ａ）の例に示した線と同じものであり、交差がある線である。線追跡の始点を開始点探索走査６１０Ａ、６１０Ｂ、６１０Ｃと順に探索し、最初に発見した黒画素を始点とする。これは前述の方法と同じである。したがって、誤った始点（開始線要素６２０）から線追跡を行うことになる。したがって、図６（ｂ）の例に示すように、線抽出方向６３０に線追跡を行うので、いったんは誤った線抽出を行うことになる。ここで、図６（ｂ）における、抽出された線の終点（末尾線要素６４０）を始点として、再度線抽出を行う。すなわち、往復する。具体的には、図６（ｂ）の例に示す末尾線要素６４０を図６（ｃ）の例に示す開始線要素６５０とし、そこから線抽出方向６６０に線追跡を行う。なお、線追跡の処理において、交差が発生している場合は、それまでに追跡してきた線の方向に基づいて、その方向の線を選択して追跡を行うようにする。すると、この２回目の線抽出によって、図６（ｃ）の例に示すように、より直線である方向へ追跡が進むことから、分岐点６７０において誤りが修正されることになる。よって、正しい線抽出が行われ、結果として、図６（ｄ）の例に示すような正しい線が抽出されることになる。

図７は、本実施の形態による往復処理の例を示す説明図である。
線抽出の始点の探索が図６の例とは異なる。つまり、図７（ａ）の例に示すように開始点探索走査７１０Ａ、７１０Ｂ、７１０Ｃ、７１０Ｄの間隔が広い（走査が粗い、具体的には走査の間隔を予め定められた値とする）ため、線抽出の始点が開始線要素７２０となり、線の端点ではない。この点から線抽出方向７３０に線追跡を行うことになるため、図７（ｂ）の例に示すように、いったんは誤った線抽出を行うことになる。ここで、往復する。具体的には、図７（ｂ）の例に示す末尾線要素７４０を図７（ｃ）の例に示す開始線要素７５０とし、そこから線抽出方向７６０に線追跡を行う。すると、正しい線抽出が行われ、結果として図７（ｄ）の例に示すような正しい線が抽出されることになる。すなわち、図７（ａ）の例に示すように、線抽出の始点の探索の精度が粗くなったとしても線抽出が行われる。なお、処理全体の高速化を図る場合に、このような処理（始点探索の間隔を予め定められた間隔以上にあけて行う処理）を行ってもよい。線抽出の始点の探索の高速化が図れるためである。また、線抽出の距離が長くなる（すなわち、線要素の個数が多くなる）ため、追跡が進むにつれ直進性が高まり、その直進性を利用して、前述したような交差に対応した線抽出を行い得るようになる。

図８は、本実施の形態による往復処理の例を示す説明図である。
図８（ａ）の例に示す線は、２つの交差があり、欠けがある線である。図８（ａ）の例に示すように、開始点探索走査８１０Ａ、８１０Ｂ、８１０Ｃと開始点の探索を行って、誤った始点（開始線要素８２０）から線抽出を行う。この場合、始点が誤っており、図８（ｂ）の例に示すように線抽出方向８３０に線追跡を行う。また、欠けが発生している分岐点（欠け）８４０において、誤った方向へ線抽出を進め、末尾線要素８５０まで追跡している。これは、この時点の線抽出の直進性が、分岐点（欠け）８４０の欠けを直進するに足りないため発生した誤りである。ここで、往復する。具体的には、図８（ｂ）の例に示す末尾線要素８５０を図８（ｃ）の例に示す開始線要素８６０とし、そこから線抽出方向８７０に線追跡を行う。すると、図８（ｃ）の例に示すように、より直線である方向へ追跡が進むことから、分岐点８８０において誤りが修正される。ただし、分岐点（欠け）８４０の誤りが残るため、誤った線抽出を行っていることになる。ここで、図８（ｄ）の例に示すように、線抽出方向８９５へさらに往復を行う。すると、この時点の線抽出の直進性が、分岐点（欠け）８４０の欠けを直進するに足る場合（つまり、図８（ｃ）の例に示すように、分岐点８８０で直線方向に進み開始線要素８９０に到達することによって、分岐点８８０から開始線要素８９０までの分だけ直進性が増加していることになり、その直進性の値が分岐点（欠け）８４０の欠け部分を修正するだけの値以上である場合）、分岐点（欠け）８４０の誤りが修正されることとなる。すると、図８（ｄ）の例に示すような線抽出が行われ、図８（ｅ）の例に示すような線が抽出される。なお、ここで、直進性とは、追跡している直線部分の距離をいい、その距離が予め定められた値以上であれば、欠け部分があった場合は直進してその欠け部分を埋め、交差部分があった場合はその直線を延長する方向の線を選択する。また、直進性とは、追跡している線における直線部分の距離の割合としてもよく、その割合が予め定められた値以上であれば、欠け部分があった場合は直進してその欠け部分を埋め、交差部分があった場合はその直線を延長する方向の線を選択するようにしてもよい。

次に、線要素について説明する。
図９は、受け付けた画像の例を示す説明図である。受け付けた画像９００は、背景画素９１０、パタン画素９２０に分かれ、パタン画素９２０は画素ラン９３０等によって構成されている。この画像９００から水平な線を抽出する例を示す。
図１０は、受け付けた画像から抽出した線要素の例を示す説明図である。パタン画素９２０は、線要素１０４０等の集合によって構成されている。ここで、線要素とは、線を構成し得る矩形の画素塊、又は前述の画素ランに対応する領域である。「線要素を示す情報」としては、例えば、線要素を描画するための情報があり、具体的には、その線要素を描画する位置、その線要素の大きさである。

図１１は、線要素１１１０の例を示す説明図である。ここでの線要素は、線の方向（図１１では進行方向）と交差する方向（図１１では位置方向）に連なる画素ランに対応する領域の１つである。
ある線が、複数の線要素で構成されているとき、例えば、ｋ番目の線要素は以下の情報を持つ。
ｓ_ｋ ： 線要素のサイズ
Ｐ_ｋ ： 線要素の位置
ｓ_ｋは、線要素の形状に関する情報であり、線の方向と交差（例えば、直交）する方向の長さである、つまり、線の太さに対応する情報である。
Ｐ_ｋは、位置に関する情報であり、水平方向の線であれば、画像上のｙ方向の位置に対応する情報である。必要によって、画像上のｘ方向の位置を含めるようにしてもよい。
追跡方向とは、水平方向の線であれば、ｘ方向であり、正負のうちのいずれかで表せる。このとき、メモリ効率の改善を図るために、追跡方向と線要素のインデックス（ｋ）を同じものとして処理してもよい。つまり、追跡方向に線要素のインデックスの順番が昇順に並んでいる場合は、インデックスの順番が増加する方向に進めば追跡方向に進むことになり、インデックスの順番が減少する方向に進めば追跡方向とは逆の方向に進むことになる。追跡方向に線要素のインデックスの順番が降順に並んでいる場合は、インデックスの順番が減少する方向に進めば追跡方向に進むことになり、インデックスの順番が増加する方向に進めば追跡方向とは逆の方向に進むことになる。

図１１の例にも示すように、実際に画像から観測される線要素は、１画素が最小単位となる。しかし、線要素の持つ情報の最小単位は、必ずしも１画素ではなく、１画素以下の単位であってもよい。例えば、得られた線要素に基づいて、１画素以下の単位で、真の線要素を求めるようにしてもよい。又は、途切れ部分の線要素を補完するといった、修正の処理を含む線抽出のように、観測された線要素がない状態から線要素を生成することをしてもよい。図１０の例では、左から１０個目の線要素と１１個目の線要素の間には、欠けが生じているが、これを埋めて修正することを行ってもよい。

なお、線要素は、図１２の例に示すように、複数画素にまたがるものであってもよい。例えば、観測線要素は１画素であり、修正線要素は複数画素であってもよい。矩形内を斜線で示した観測線要素１２１１〜１２２８は画像内の観測された線要素であり、灰色の矩形で示した修正線要素１２５１〜１２５９は観測線要素１２１１等に基づいて修正された線要素である。例えば、観測線要素１２１１と観測線要素１２１２の組は上に延長して（この部分の線の太さを太くして）修正線要素１２５１となり、観測線要素１２２０と観測線要素１２２２の間に観測された線要素はないが、修正線要素１２５６として生成されている。

線抽出モジュール１１０は、往復判別モジュール１２０、反転処理モジュール１３０と接続されている。線抽出モジュール１１０は、線の可能性がある画像１０６に関する情報であって、線を構成し得る矩形の画素塊である線要素を示す情報の集合を受け付け、その線要素を示す情報と線の追跡方向に基づいて、線の開始点から末尾点まで追跡を行うことによって線を抽出する。
例えば、線抽出モジュール１１０は、予測、観測との繰り返しにより、逐次、線要素を求め、これらを統合する。まず、始点に対応する線要素を含む線要素の集合と追跡方向である（線要素，追跡方向）１０８を受け付ける。線要素の集合内には、いずれが始点に対応する線要素であるかが判明するようになっている。例えば、線要素のインデックス（ｋ）が０であるものを始点の線要素としてもよい。そして、その始点から始めて連続している線要素を辿ることによって、線追跡を行い、予測した線要素と観測した線要素が合致すれば統合（観測した線要素を線の一部とすること）し、合致しない場合は修正処理を行って、終点まで追跡したときは、抽出した線として線情報１１２を往復判別モジュール１２０に渡す。なお、ここでの合致とは、予測した線要素と観測した線要素の値が完全同一である場合のみならず、その値の差が予め定められた値未満である場合も含む。

図１３は、線抽出モジュール１１０が行う予測と観測による線要素の統合処理の例を示す説明図である。線要素のインデックスをｋとして、ｋ番目の線要素をｅ_ｋとする。そして、始点である線要素ｅ_０とし、線要素の集合｛ｅ_０，・・・，ｅ_ｋ−１｝と追跡方向を受け付ける。
そして、予測を行う。すなわち，ｅ_ｋの予測値Ｅ_ｋを算出する。予測は、線要素の集合｛ｅ_０，・・・，ｅ_ｋ−１｝（又は、その一部であってもよい）と追跡方向に基づいて、予測値Ｅ_ｋを算出する。なお、線要素が追跡方向の情報を保持してもよい。例えば、Ｐ_ｋ＝ｐ_ｋ−１＋σｐ_ｋ−１等の計算を行い、つづく線要素に対する変化量σｐ_ｋ−１を用いてもよい。例えば、変化量σｐ_ｋ−１として、ｓ_ｋが±α、ｐ_ｋが＋β以下等がある。
次に、観測を行う。すなわち、ｅ_ｋを抽出する。観測は、予測値Ｅ_ｋに基づいて、画像１０６からｅ_ｋを抽出する。すなわち、予測値Ｅ_ｋとの差異が十分に小さいｅ_ｋが観測されたとき、ｅ_ｋを統合する。ここで差異とは、観測値ｅ_ｋと予測値Ｅ_ｋの前述のｓ_ｋとｐ_ｋの値の差異が、予め定められた値未満であることを指す。線抽出は，以上の処理を終点（観測値の予め定められた範囲内に線要素がない場合の線要素）まで繰り返す。また、線抽出の処理として、非特許文献１に記載の技術を利用してもよい。
なお、線抽出モジュール１１０が受け付ける（線要素，追跡方向）１０８は、最初の抽出処理の場合は、開始点の探索処理によって抽出された始点における開始線要素と予め定められた追跡方向が少なくともあり、２回目以降の抽出処理（往復処理）の場合は、反転処理モジュール１３０から受け取った（線要素，追跡方向）１０８である。

往復判別モジュール１２０は、線抽出モジュール１１０、反転処理モジュール１３０と接続されている。往復判別モジュール１２０は、線抽出モジュール１１０から線情報１１２を受け取って、反転処理モジュール１３０による処理を行わせるか否かを判別する。そして、予め定められた条件を満たす場合（反転処理モジュール１３０による処理を行わせない場合）は、抽出した線として線情報１２４を出力する。線情報１２４出力するとは、例えば、ハードディスク等の記憶媒体に記憶すること、他の画像処理装置へ渡すこと等が含まれる。他の画像処理装置は、例えば、線情報１２４により表される線を最終的に線として採用するか否かを判別するようにしてもよいし、線情報１２４を用いて線のみの画像を生成する等の処理を行ってもよいし、図１９、図２０の例を用いて後述する処理を行うようにしてもよい。

また、往復判別モジュール１２０は、線抽出モジュール１１０又は反転処理モジュール１３０による処理の回数を計数し、その回数と予め定められた回数とを比較することによって、反転処理モジュール１３０による処理を行わせるか否かを判別するようにしてもよい。
また、往復判別モジュール１２０は、線抽出モジュール１１０の前回の処理による線の開始点又は末尾点と往復判別モジュール１２０の今回の処理による線の末尾点又は開始点とを比較することによって、反転処理モジュール１３０による処理を行わせるか否かを判別するようにしてもよい。比較対象の組み合わせは、前回の処理による線の開始点と今回の処理による線の末尾点、前回の処理による線の末尾点と今回の処理による線の開始点となる。そして、いずれか一方の組み合わせの比較をして判別してもよいし、両方の組み合わせの比較を行って判別するようにしてもよい。特に、前回の処理による線の開始点と今回の処理による線の末尾点とを比較することを採用すると、無駄な比較は発生しない。この判別処理のために、もちろんのことながら、前回の処理による線の開始点と末尾点を記憶する。
また、往復判別モジュール１２０は、線抽出モジュール１１０によって抽出された線の特徴量に基づいて、反転処理モジュール１３０による処理を行わせるか否かを判別するようにしてもよい。
なお、これらの判別処理の２つ以上を組み合わせて行ってもよい。

往復判別モジュール１２０の処理について詳述する。
往復判別モジュール１２０は、線情報１１２が予め定められた条件を満たすか否かによって、反転処理モジュール１３０に反転処理を行わせるか否かを判別する。
この判別処理では、往復回数ｔｕｒｎを参照する。往復回数ｔｕｒｎとは、抽出している線について、過去に往復を行った回数である。具体的には、線抽出モジュール１１０又は反転処理モジュール１３０が行った処理の回数である。そして、予め定められた値に満たない場合、反転処理を行う。そのために、変数として往復回数ｔｕｒｎを保持する。

また、直前に抽出した線との関係を参照してもよい。なお、直前に抽出した線とは、現在抽出している線に、開始線要素を与えた線を指す。ゆえに、往復回数ｔｕｒｎ＝０では、直前に抽出した線はないため、これを参照しない。具体的には、直前に抽出した線の始点である線要素の位置ｐ_０ ^ｐｒｅと、現在抽出している線の終点である線要素の位置ｐ_Ｎ−１との距離が、予め定められた値以上であれば、反転処理を行う。このように端点の合致による往復判別の概要を図１４の例に示す。図１４（ａ）の例に示すように、開始点探索走査１４１０Ａ、１４１０Ｂ、１４１０Ｃによって抽出された開始線要素Ｐ_０１４１５から線抽出方向１４２０へ線追跡する。なお、このとき往復回数は０である。そして、図１４（ｂ）の例に示すように、線抽出方向１４２０の末尾点である開始線要素Ｐ_０１４３０を開始点として、線抽出方向１４３５へ線追跡し、末尾線要素Ｐ_Ｎ１−１１４４０まで辿る。ここで、前回の開始線要素Ｐ_０１４１５と今回の末尾線要素Ｐ_Ｎ１−１１４４０の距離は予め定められた値以上であるので、反転処理を行う。なお、このとき往復回数は１である。次に、図１４（ｃ）の例に示すように、図１４（ｂ）の例における末尾線要素Ｐ_Ｎ１−１１４４０を開始線要素Ｐ_０１４５０として、前回開始線要素Ｐ_０ ^ｐｒｅ１４４５へ線追跡し、末尾線要素Ｐ_Ｎ２−１１４６０まで辿る。ここで、前回の開始線要素Ｐ_０１４３０と今回の前回末尾線要素Ｐ_０ ^ｐｒｅ１４６５の距離は予め定められた値以上であるので、反転処理を行う。なお、このとき往復回数は２である。次に、図１４（ｄ）の例に示すように、図１４（ｃ）の例における末尾線要素Ｐ_Ｎ２−１１４６０を開始線要素Ｐ_０１４７０として、線抽出方向１４８０へ線追跡し、末尾線要素Ｐ_Ｎ３−１１４８５まで辿る。なお、このとき往復回数は３である。ここで、前回の開始線要素Ｐ_０１４５０（前回開始線要素Ｐ_０ ^ｐｒｅ１４９０）と今回の末尾線要素Ｐ_Ｎ３−１１４８５の距離は予め定められた値未満であるので、反転処理は行わずに開始線要素Ｐ_０１４７０から末尾線要素Ｐ_Ｎ３−１１４８５までの線を線情報１２４として出力する。このように、始点と終点の一対一対応を検出することで、往復回数の閾値θ_ｔｕｒｎによらずに、線抽出を行うことになる。この処理は、ｐ_０ ^ｐｒｅを保持する。ただし、Ｎ_ｎは、ｎ回の往復による線抽出で得られた線要素の個数である。

また、線の特徴量を参照してもよい。具体的には、線の長さ、太さ、線の傾き等がある。これら線の特徴量が予め定められた条件を満たさない場合、往復処理を行わず、線を出力する。特徴量の観点から、適切でない線を抽出した場合（予め定められた特徴量を満たす線でない場合）、往復処理を中断することで、誤った線抽出を回避するようにしてもよい。線の特徴量は、線抽出モジュール１１０又は往復判別モジュール１２０が算出すればよい。

反転処理モジュール１３０は、往復判別モジュール１２０、線抽出モジュール１１０と接続されている。反転処理モジュール１３０は、線抽出モジュール１１０によって抽出された線の末尾点を開始点とし、前回の線抽出モジュール１１０が線を抽出するときに用いた線の追跡方向を反転させ、線抽出モジュール１１０へその開始点と線の追跡方向を渡す。反転処理モジュール１３０が渡す線の追跡方向は、もちろんのことながら、前回の線抽出モジュール１１０が線を抽出するときに用いた線の方向を反転させた方向である。つまり、次回の線抽出モジュール１１０が線を抽出するときは、前回の線を抽出するときの追跡方向とは逆の方向へ追跡することになり、線を往復することになる。ただし、ここでの往復とは、前回の開始点の方向へ追跡することにはなるが、その結果、必ずしも前回の開始点が末尾点になるとは限らないことは前述した通りである。

反転処理モジュール１３０の処理について詳述する。
反転処理モジュール１３０は、今回の線抽出モジュール１１０の処理で抽出した線の終点である線要素を、次の線抽出モジュール１１０の処理の開始のための線要素として、線抽出モジュール１１０へ出力する。また、追跡方向を反転し、次の線抽出モジュール１１０での線抽出の追跡方向として、線抽出モジュール１１０へ出力する。
線がＮ個の線要素である集合｛ｅ_０，・・・，ｅ_Ｎ−１｝とする。この線に反転処理を行うとする。
反転処理は、線の終点である線要素ｅ_Ｎ−１に基づいて、次の線抽出の開始のための線要素ｅ’_０を出力する。
この具体例を図１５に示す。図１５の例は、左から右へ線要素１５１１、１５１２、１５１３、１５１４、１５１５（ｅ_Ｎ−１）と追跡（追跡方向：ｄ）し、反転処理を行った結果、線要素１５１５を始点（ｅ’_０）として追跡方向を表す値ｄの正負が反転している。

開始のための線要素の出力について、線要素の持つ情報に、つづく線要素への変化量がある場合、この値も反転する。この変化量とは追跡方向に該当する。図１５の例は全体の追跡方向であるが、個々の線要素に次の線要素への追跡方向を付加したものである。
具体的には、変化量が微分値であれば、値の正負を反転すればよい。また、変化量が角度であれば、π［ｒａｄ］を加減算すればよい。これらの具体例を図１６、図１７に示す。図１６の例において、変化量δＰ_Ｎ−２１６２１、変化量δＰ_Ｎ−１１６２２、変化量δＰ’_０１６２３はつづく線要素への変化量を表す。変化量δＰ’_０１６２３に変化量δＰ_Ｎ−１１６２２の正負を反転した−δＰ_Ｎ−１を設定することが、追跡方向の反転に対応する。また、図１７の例において、角度ω_Ｎ−２１７２１、角度ω_Ｎ−１１７２２、角度ω’_０１７２３はつづく線要素への角度を表す。角度ω’_０１７２３に角度ω_Ｎ−１１７２２にπ［ｒａｄ］を加算したもの（ω_Ｎ−１＋π）を設定することが、追跡方向の反転に対応する。
また、反転した場合は、より対象の線に適応した線抽出を行うために、線抽出モジュール１１０の線抽出で参照するパラメータを更新してもよい。

図１８は、第２の実施の形態の構成例についての概念的なモジュール構成図である。第２の実施の形態である画像処理装置は、開始線要素の探索処理を含み、対象とする画像から線であるパタン（画像）を抽出するものであって、図１８の例に示すように、開始線要素探索モジュール１８１０、線抽出モジュール１１０、往復判別モジュール１２０、反転処理モジュール１３０を有している。なお、第１の実施の形態と同種の部位には同一符号を付し重複した説明を省略する。

開始線要素探索モジュール１８１０は、線抽出モジュール１１０と接続されている。開始線要素探索モジュール１８１０は、画像１０６に基づいて（線要素，追跡方向）１０８を線抽出モジュール１１０へ出力するものである。もし、開始のための線要素が抽出されない場合、無効信号である無効情報１８２０を出力し、処理を終了する。図７（ａ）の例に示したように、間隔を広くした（具体的には走査の間隔を予め定められた値とする）走査であってもよいし、連続する画素毎に走査するようにしてもよい。
また、開始線要素探索モジュール１８１０は、細線化処理、エッジ抽出処理等を行って、端点を抽出し、その端点を用いて線要素を抽出するようにしてもよい。
なお、線抽出モジュール１１０は、開始線要素探索モジュール１８１０、往復判別モジュール１２０、反転処理モジュール１３０と接続されており、最初の線追跡処理においては開始線要素探索モジュール１８１０から受け付けた（線要素，追跡方向）１０８を用い、２回目以降の線追跡処理において反転処理モジュール１３０から受け付けた（線要素，追跡方向）１０８を用いる。

図１９は、第３の実施の形態の構成例についての概念的なモジュール構成図である。
画像受付モジュール１９１０、文字列抽出モジュール１９２０、画像処理モジュール１９３０、文字認識モジュール１９４０、出力モジュール１９５０を有している。
画像受付モジュール１９１０は、文字列抽出モジュール１９２０と接続されており、文字列を含む画像を受け付ける。画像内には、下線、取り消し線等が含まれていてもよい。
文字列抽出モジュール１９２０は、画像受付モジュール１９１０、画像処理モジュール１９３０と接続されており、画像受付モジュール１９１０によって受け付けられた画像から文字列を抽出し、その文字列の方向と画像を画像処理モジュール１９３０に渡す。文字列の抽出は、既存の技術を用いてもよい。例えば、縦方向、横方向に黒画素のヒストグラムをとり、その分布から縦書き、横書きの方向を抽出してもよい。その文字列の方向を線の方向として、線の可能性がある画像を抽出する。

画像処理モジュール１９３０は、文字列抽出モジュール１９２０、文字認識モジュール１９４０と接続されており、前述の第１の実施の形態の画像処理装置、第２の実施の形態の画像処理装置のいずれかが該当する。つまり、文字列抽出モジュール１９２０から渡された文字列の方向を線の追跡方向として、線を抽出する。
文字認識モジュール１９４０は、画像処理モジュール１９３０、出力モジュール１９５０と接続されており、画像処理モジュール１９３０によって画像から線として判別された画像を削除して、文字画像だけとなった画像を文字認識する。
出力モジュール１９５０は、文字認識モジュール１９４０と接続されており、文字認識モジュール１９４０による文字認識結果を出力する。

図２０は、第４の実施の形態の構成例についての概念的なモジュール構成図である。
画像受付モジュール２０１０、枠線方向指定モジュール２０２０、画像処理モジュール２０３０、帳票処理モジュール２０４０、出力モジュール２０５０を有している。
画像受付モジュール２０１０は、枠線方向指定モジュール２０２０と接続されており、枠線を含む画像を受け付ける。例えば、帳票の画像を受け付ける。
枠線方向指定モジュール２０２０は、画像受付モジュール２０１０、画像処理モジュール２０３０と接続されており、画像受付モジュール２０１０によって受け付けられた画像から枠線の方向を抽出し、その枠線の方向と画像を画像処理モジュール２０３０に渡す。例えば、帳票に主に用いられている垂直方向の線、水平方向の線をそれぞれ試すようにしてもよい。具体的には、垂直方向又は水平方向に連なる線のいずれが多いかによって、枠線の方向を抽出してもよい。また、垂直方向及び水平方向に連なる画素の数がいずれも予め定められた値以上である場合は、枠線の方向として垂直方向、水平方向の両方を抽出してもよい。

画像処理モジュール２０３０は、枠線方向指定モジュール２０２０、帳票処理モジュール２０４０と接続されており、前述の第１の実施の形態の画像処理装置、第２の実施の形態の画像処理装置のいずれかが該当する。つまり、枠線方向指定モジュール２０２０によって抽出された枠線の方向を線の追跡方向として、線を抽出する。
帳票処理モジュール２０４０は、画像処理モジュール２０３０、出力モジュール２０５０と接続されており、画像処理モジュール２０３０によって画像から線として判別された線画像の位置から帳票内の欄を判別して、その欄内にある文字画像を文字認識して、欄と文字認識結果を対応付けるようにしてもよい。
出力モジュール２０５０は、帳票処理モジュール２０４０と接続されており、帳票処理モジュール２０４０による帳票処理結果を出力する。

図２１を参照して、本実施の形態の画像処理装置のハードウェア構成例について説明する。図２１に示す構成は、例えばパーソナルコンピュータ（ＰＣ）などによって構成されるものであり、スキャナ等のデータ読み取り部２１１７と、プリンタなどのデータ出力部２１１８を備えたハードウェア構成例を示している。

ＣＰＵ２１０１は、前述の実施の形態において説明した各種のモジュール、すなわち、線抽出モジュール１１０、往復判別モジュール１２０、反転処理モジュール１３０、開始線要素探索モジュール１８１０、文字列抽出モジュール１９２０、画像処理モジュール１９３０、文字認識モジュール１９４０、枠線方向指定モジュール２０２０、画像処理モジュール２０３０、帳票処理モジュール２０４０等の各モジュールの実行シーケンスを記述したコンピュータ・プログラムにしたがった処理を実行する制御部である。

ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）２１０２は、ＣＰＵ２１０１が使用するプログラムや演算パラメータ等を格納する。ＲＡＭ２１０３は、ＣＰＵ２１０１の実行において使用するプログラムや、その実行において適宜変化するパラメータ等を格納する。これらはＣＰＵバスなどから構成されるホストバス２１０４により相互に接続されている。

ホストバス２１０４は、ブリッジ２１０５を介して、ＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ Ｃｏｍｐｏｎｅｎｔ Ｉｎｔｅｒｃｏｎｎｅｃｔ／Ｉｎｔｅｒｆａｃｅ）バスなどの外部バス２１０６に接続されている。

キーボード２１０８、マウス等のポインティングデバイス２１０９は、操作者により操作される入力デバイスである。ディスプレイ２１１０は、液晶表示装置又はＣＲＴ（Ｃａｔｈｏｄｅ Ｒａｙ Ｔｕｂｅ）などがあり、各種情報をテキストやイメージ情報として表示する。

ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）２１１１は、ハードディスクを内蔵し、ハードディスクを駆動し、ＣＰＵ２１０１によって実行するプログラムや情報を記録又は再生させる。ハードディスクには、受け付けた画像、線要素の情報などが格納される。さらに、その他の各種のデータ処理プログラム等、各種コンピュータ・プログラムが格納される。

ドライブ２１１２は、装着されている磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリ等のリムーバブル記録媒体２１１３に記録されているデータ又はプログラムを読み出して、そのデータ又はプログラムを、インタフェース２１０７、外部バス２１０６、ブリッジ２１０５、及びホストバス２１０４を介して接続されているＲＡＭ２１０３に供給する。リムーバブル記録媒体２１１３も、ハードディスクと同様のデータ記録領域として利用可能である。

接続ポート２１１４は、外部接続機器２１１５を接続するポートであり、ＵＳＢ、ＩＥＥＥ１３９４等の接続部を持つ。接続ポート２１１４は、インタフェース２１０７、及び外部バス２１０６、ブリッジ２１０５、ホストバス２１０４等を介してＣＰＵ２１０１等に接続されている。通信部２１１６は、ネットワークに接続され、外部とのデータ通信処理を実行する。データ読み取り部２１１７は、例えばスキャナであり、ドキュメントの読み取り処理を実行する。データ出力部２１１８は、例えばプリンタであり、ドキュメントデータの出力処理を実行する。

なお、図２１に示す画像処理装置のハードウェア構成は、１つの構成例を示すものであり、本実施の形態は、図２１に示す構成に限らず、本実施の形態において説明したモジュールを実行可能な構成であればよい。例えば、一部のモジュールを専用のハードウェア（例えば特定用途向け集積回路（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ：ＡＳＩＣ）等）で構成してもよく、一部のモジュールは外部のシステム内にあり通信回線で接続しているような形態でもよく、さらに図２１に示すシステムが複数互いに通信回線によって接続されていて互いに協調動作するようにしてもよい。また、複写機、ファックス、スキャナ、プリンタ、複合機（スキャナ、プリンタ、複写機、ファックス等のいずれか２つ以上の機能を有している画像処理装置）などに組み込まれていてもよい。

なお、前述の各種の実施の形態を組み合わせてもよく（例えば、ある実施の形態内のモジュールを他の実施の形態内に追加する、入れ替えをする等も含む）、また、各モジュールの処理内容として背景技術で説明した技術を採用してもよい。

なお、説明したプログラムについては、記録媒体に格納して提供してもよく、また、そのプログラムを通信手段によって提供してもよい。その場合、例えば、前記説明したプログラムについて、「プログラムを記録したコンピュータ読み取り可能な記録媒体」の発明として捉えてもよい。
「プログラムを記録したコンピュータ読み取り可能な記録媒体」とは、プログラムのインストール、実行、プログラムの流通などのために用いられる、プログラムが記録されたコンピュータで読み取り可能な記録媒体をいう。
なお、記録媒体としては、例えば、デジタル・バーサタイル・ディスク（ＤＶＤ）であって、ＤＶＤフォーラムで策定された規格である「ＤＶＤ−Ｒ、ＤＶＤ−ＲＷ、ＤＶＤ−ＲＡＭ等」、ＤＶＤ＋ＲＷで策定された規格である「ＤＶＤ＋Ｒ、ＤＶＤ＋ＲＷ等」、コンパクトディスク（ＣＤ）であって、読出し専用メモリ（ＣＤ−ＲＯＭ）、ＣＤレコーダブル（ＣＤ−Ｒ）、ＣＤリライタブル（ＣＤ−ＲＷ）等、ブルーレイ・ディスク（Ｂｌｕ−ｒａｙ Ｄｉｓｃ（登録商標））、光磁気ディスク（ＭＯ）、フレキシブルディスク（ＦＤ）、磁気テープ、ハードディスク、読出し専用メモリ（ＲＯＭ）、電気的消去及び書換可能な読出し専用メモリ（ＥＥＰＲＯＭ（登録商標））、フラッシュ・メモリ、ランダム・アクセス・メモリ（ＲＡＭ）等が含まれる。
そして、前記のプログラム又はその一部は、前記記録媒体に記録して保存や流通等させてもよい。また、通信によって、例えば、ローカル・エリア・ネットワーク（ＬＡＮ）、メトロポリタン・エリア・ネットワーク（ＭＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、インターネット、イントラネット、エクストラネット等に用いられる有線ネットワーク、あるいは無線通信ネットワーク、さらにこれらの組み合わせ等の伝送媒体を用いて伝送させてもよく、また、搬送波に乗せて搬送させてもよい。
さらに、前記のプログラムは、他のプログラムの一部分であってもよく、あるいは別個のプログラムと共に記録媒体に記録されていてもよい。また、複数の記録媒体に分割して
記録されていてもよい。また、圧縮や暗号化など、復元可能であればどのような態様で記録されていてもよい。

１１０…線抽出モジュール
１２０…往復判別モジュール
１３０…反転処理モジュール
１８１０…開始線要素探索モジュール
１９１０…画像受付モジュール
１９２０…文字列抽出モジュール
１９３０…画像処理モジュール
１９４０…文字認識モジュール
１９５０…出力モジュール
２０１０…画像受付モジュール
２０２０…枠線方向指定モジュール
２０３０…画像処理モジュール
２０４０…帳票処理モジュール
２０５０…出力モジュール

Claims (6)

1. 線の可能性がある画像に関する情報であって、線を構成し得る矩形の画素塊である線要素を示す情報の集合を受け付ける線情報受付手段と、
   前記線情報受付手段によって受け付けられた線要素を示す情報と線の追跡方向に基づいて、線の開始点から末尾点まで追跡を行うことによって線を抽出する線抽出手段と、
   前記線抽出手段によって抽出された線の末尾点を開始点とし、前記線の追跡方向を反転させ、前記線抽出手段へ該開始点と線の追跡方向を渡す反転手段と、
   前記反転手段による処理を行わせるか否かを判別する判別手段と、
   を具備し、
   前記判別手段は、前記線抽出手段又は前記反転手段による処理の回数を計数し、該回数と予め定められた回数とを比較することによって、該反転手段による処理を行わせるか否かを判別する
   ことを特徴とする画像処理装置。
2. 前記判別手段は、前記線抽出手段の前回の処理による線の開始点又は末尾点と該線抽出手段の今回の処理による線の末尾点又は開始点とを比較することによって、前記反転手段による処理を行わせるか否かを判別する
   ことを特徴とする請求項１に記載の画像処理装置。
3. 前記判別手段は、前記線抽出手段によって抽出された線の特徴量に基づいて、前記反転手段による処理を行わせるか否かを判別する
   ことを特徴とする請求項１に記載の画像処理装置。
4. 前記線抽出手段は、文字列を含む画像から文字列の方向を線の追跡方向として、線を抽出する
   ことを特徴とする請求項１から３のいずれか一項に記載の画像処理装置。
5. 前記線抽出手段は、枠線を含む画像から枠線の方向を線の追跡方向として、線を抽出する
   ことを特徴とする請求項１から３のいずれか一項に記載の画像処理装置。
6. コンピュータを、
   線の可能性がある画像に関する情報であって、線を構成し得る矩形の画素塊である線要素を示す情報の集合を受け付ける線情報受付手段と、
   前記線情報受付手段によって受け付けられた線要素を示す情報と線の追跡方向に基づいて、線の開始点から末尾点まで追跡を行うことによって線を抽出する線抽出手段と、
   前記線抽出手段によって抽出された線の末尾点を開始点とし、前記線の追跡方向を反転させ、前記線抽出手段へ該開始点と線の追跡方向を渡す反転手段と、
   前記反転手段による処理を行わせるか否かを判別する判別手段、
   として機能させ、
   前記判別手段は、前記線抽出手段又は前記反転手段による処理の回数を計数し、該回数と予め定められた回数とを比較することによって、該反転手段による処理を行わせるか否かを判別する
   ことを特徴とする画像処理プログラム。

Images