画像処理装置及び画像処理プログラム
【課題】グラフモデルを生成し、開図形と閉図形とを別々に抽出することで、線図形の大きさのばらつき、接触又は交差の制限を緩和して、線図形の抽出をする画像処理装置を提供する。
【解決手段】画像処理装置の抽出手段は、線図形を含む画像内の点に関する特徴及び線分を抽出し、グラフモデル生成手段は、前記抽出手段による結果に基づいて、グラフモデルを生成し、開図形抽出手段は、前記グラフモデル生成手段によって生成されたグラフモデルを解析することによって、端点を有する開図形を抽出し、閉図形抽出手段は、前記グラフモデル生成手段によって生成されたグラフモデルを解析することによって、端点を有しない閉図形を抽出する。
【解決手段】画像処理装置の抽出手段は、線図形を含む画像内の点に関する特徴及び線分を抽出し、グラフモデル生成手段は、前記抽出手段による結果に基づいて、グラフモデルを生成し、開図形抽出手段は、前記グラフモデル生成手段によって生成されたグラフモデルを解析することによって、端点を有する開図形を抽出し、閉図形抽出手段は、前記グラフモデル生成手段によって生成されたグラフモデルを解析することによって、端点を有しない閉図形を抽出する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置及び画像処理プログラムに関する。
【背景技術】
【０００２】
手書きされた文字を認識しようとする場合、複数の文字やその他図形等との接触があると認識率が低下するため、これらを分離することが求められている。
【０００３】
これに関連する技術として、例えば、特許文献１には、文字列画像全体の構造的な情報を用いて、接触文字数、接触の仕方に関係なく文字列を容易に認識することを目的とし、文字列認識処理では、まず、抽出された文字列画像を細線化して骨格線図形を生成し、次に、骨格線図形を複数の単純な部分曲線に分割し、次に、部分曲線を組み合わせて文字列の部分図形を生成し、該部分図形について文字認識を行い、次に、文字に認識された部分図形をノードとし、該ノードを重み付きのリンクで多様に結んでネットワークを構成し、最後に、ネットワークから最適解の経路を選び、そのノードの組合せを出力することが開示されている。
【０００４】
例えば、特許文献２には、文字画像から抽出したストロークが接触ストロークであるときの切断候補と切断回数を抑えて処理効率を向上させることを課題とし、文字列画像記憶部から入力した画像から初期ストローク抽出部で初期ストロークを抽出し、接触ストローク判断部で接触したストロークと判定したものだけ切断候補抽出部で切断候補箇所を抽出し、最適候補選択部で切断候補から切断箇所を選択し、ストローク情報更新部で接触ストロークを選択された箇所で切断して新しいストロークを生成し、文字切り出し候補生成部は、新しいストロークと非接触ストロークバッファに記憶されていた接触していないストロークとを組み合わせて文字切り出し候補を生成して出力することが開示されている。
【０００５】
また、例えば、特許文献３には、ノイズや線幅の変動の影響を受けず、またストロークが完全に交差している接触箇所があっても高い確率で正解を含む文字切り出し候補を生成でき、しかも候補数の増大を防ぐことができる文字切り出し候補生成装置を提供することを課題とし、文字列画像記憶部は光学的に走査された文字列画像を格納し、線分素抽出部はこの格納された文字列画像から特定の方向成分を持つ部分である線分素をモルフォロジー演算を使用して抽出し、ストローク作成部はこの抽出された線分素をマージして或る程度滑らかにつながる曲線部分であるストロークを作成し、最後に、文字切り出し候補作成部は作成されたストロークを組み合わせて文字切り出し候補を作成することが開示されている。
【特許文献１】特開平０６−０７６１１４号公報
【特許文献２】特開平１１−１４９５２１号公報
【特許文献３】特開平０９−２８８７１５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところで、文字画像の高さ又は接触位置を限定して線図形を抽出している場合は、それ以外の線図形の大きさ、接触又は交差がある場合は対処することができない。
本発明は、グラフモデルを生成し、開図形と閉図形とを別々に抽出することで、線図形の大きさのばらつき、接触又は交差の制限を緩和して、線図形の抽出をする画像処理装置及び画像処理プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
かかる目的を達成するための本発明の要旨とするところは、次の各項の発明に存する。
請求項１記載の発明は、線図形を含む画像内の点に関する特徴及び線分を抽出する抽出手段と、前記抽出手段による結果に基づいて、グラフモデルを生成するグラフモデル生成手段と、前記グラフモデル生成手段によって生成されたグラフモデルを解析することによって、端点を有する開図形を抽出する開図形抽出手段と、前記グラフモデル生成手段によって生成されたグラフモデルを解析することによって、端点を有しない閉図形を抽出する閉図形抽出手段を具備することを特徴とする画像処理装置である。
【０００８】
請求項２記載の発明は、前記抽出手段によって抽出された特徴点及び線分に基づいて、前記線分のうち偽線分を識別する偽線分識別手段を具備し、前記グラフモデル生成手段は、前記抽出手段及び前記偽線分識別手段による結果に基づいて、グラフモデルを生成することを特徴とする請求項１に記載の画像処理装置である。
【０００９】
請求項３記載の発明は、前記閉図形抽出手段は、前記グラフモデルを解析することによって、閉図形を抽出し、多角形近似を行った後に、閉図形の形状を認識することを特徴とする請求項１に記載の画像処理装置である。
【００１０】
請求項４記載の発明は、前記閉図形抽出手段は、抽出した閉図形のうち重複している図形を削除することを特徴とする請求項１又は３に記載の画像処理装置である。
【００１１】
請求項５記載の発明は、前記開図形抽出手段によって抽出された開図形及び前記閉図形抽出手段によって抽出された閉図形の合計が、前記画像内に含まれている図形の数と異なるか否かを判断する判断手段と、前記判断手段によって異なると判断された場合は、前記画像内の線分の接触している箇所に応じて、前記グラフモデルを変更し、前記開図形抽出手段又は前記閉図形抽出手段による処理を行わせる再処理手段をさらに具備することを特徴とする請求項１に記載の画像処理装置である。
【００１２】
請求項６記載の発明は、前記開図形抽出手段によって抽出された開図形又は前記閉図形抽出手段によって抽出された閉図形の形状が、前記画像内に含まれている図形の形状と異なるか否かを判断する判断手段と、前記判断手段によって異なると判断された場合は、前記画像内の線分の接触している箇所に応じて、前記グラフモデルを変更し、前記開図形抽出手段又は前記閉図形抽出手段による処理を行わせる再処理手段をさらに具備することを特徴とする請求項１に記載の画像処理装置である。
【００１３】
請求項７記載の発明は、コンピュータを、線図形を含む画像内の点に関する特徴及び線分を抽出する抽出手段と、前記抽出手段による結果に基づいて、グラフモデルを生成するグラフモデル生成手段と、前記グラフモデル生成手段によって生成されたグラフモデルを解析することによって、端点を有する開図形を抽出する開図形抽出手段と、前記グラフモデル生成手段によって生成されたグラフモデルを解析することによって、端点を有しない閉図形を抽出する閉図形抽出手段として機能させることを特徴とする画像処理プログラムである。
【発明の効果】
【００１４】
請求項１の画像処理装置によれば、線図形の大きさのばらつき、接触又は交差の制限を緩和して、線図形の抽出をすることができるようになる。
【００１５】
請求項２の画像処理装置によれば、線分の太さによって交差部分に発生しやすい偽線分を識別することができ、より正確な線図形の抽出を行うことができるようになる。
【００１６】
請求項３の画像処理装置によれば、形状を認識することによって、より正確な線図形の抽出をすることができるようになる。
【００１７】
請求項４の画像処理装置によれば、余分な線図形を抽出することを抑制することができるようになる。
【００１８】
請求項５の画像処理装置によれば、予め図形の数が判明している場合は、より正確に線図形を抽出することができるようになる。
【００１９】
請求項６の画像処理装置によれば、予め図形の形状が判明している場合は、より正確に線図形を抽出することができるようになる。
【００２０】
請求項７の画像処理プログラムによれば、線図形の大きさのばらつき、接触又は交差の制限を緩和して、線図形の抽出をすることができるようになる。
【発明を実施するための最良の形態】
【００２１】
以下、図面に基づき本発明を実現するにあたっての好適な一実施の形態の例を説明する。
図１は、本実施の形態の構成例についての概念的なモジュール構成図を示している。
なお、モジュールとは、一般的に論理的に分離可能なソフトウェア（コンピュータ・プログラム）、ハードウェア等の部品を指す。したがって、本実施の形態におけるモジュールはコンピュータ・プログラムにおけるモジュールのことだけでなく、ハードウェア構成におけるモジュールも指す。それゆえ、本実施の形態は、コンピュータ・プログラム、システム及び方法の説明をも兼ねている。ただし、説明の都合上、「記憶する」、「記憶させる」、これらと同等の文言を用いるが、これらの文言は、実施の形態がコンピュータ・プログラムの場合は、記憶装置に記憶させること、又は記憶装置に記憶させるように制御するの意である。また、モジュールは機能にほぼ一対一に対応しているが、実装においては、１モジュールを１プログラムで構成してもよいし、複数モジュールを１プログラムで構成してもよく、逆に１モジュールを複数プログラムで構成してもよい。また、複数モジュールは１コンピュータによって実行されてもよいし、分散又は並列環境におけるコンピュータによって１モジュールが複数コンピュータで実行されてもよい。なお、１つのモジュールに他のモジュールが含まれていてもよい。また、以下、「接続」とは物理的な接続の他、論理的な接続（データの授受、指示、データ間の参照関係等）を含む。
また、システム又は装置とは、複数のコンピュータ、ハードウェア、装置等がネットワーク（一対一対応の通信接続を含む）等の通信手段で接続されて構成されるほか、１つのコンピュータ、ハードウェア、装置等によって実現される場合も含まれる。
【００２２】
本実施の形態は、図１に示すように、前処理モジュール１１、線追跡抽出モジュール１２、形状解析抽出モジュール１３、後処理モジュール１４を有している。
前処理モジュール１１は、線追跡抽出モジュール１２と接続されており、対象となる画像を入力し、それに対して前処理を行い、線追跡抽出モジュール１２にその画像を渡す。
ここで、対象となる画像は、手書きで記入した複数の線図形を含む画像である。なお、その線図形には、紙文書にペンで手書きされたものの他に、電子ペン等で電子的に記入された線図形を含む画像（軌跡としての位置データ）であってもよい。また、紙文書の画像はスキャナ等の画像入力装置によって入力されたものである。より具体的には、例えば、学生・生徒等に対するテストの判定済みの答案用紙、回答が記入済みのアンケート用紙等に追記された手書きの線図形等の画像が該当する。
前処理としては、ノイズ除去処理と細線化処理等がある。ノイズ除去処理としては、例えば、孤立点の除去、かすれ線の補間、傾き補正等がある。細線化処理は、二値画像を幅１画素の線画像に変換する処理をいい、パターン認識等の前処理として用いられている処理（予め定められたパターンとのマッチングを行い、一致すればそのうちの定められた画素を削除する等）を用いる。
【００２３】
線追跡抽出モジュール１２は、前処理モジュール１１、形状解析抽出モジュール１３と接続されており、前処理モジュール１１から細線化処理された線図形の画像を受け取り、その中の線分を追跡して抽出することにより、開図形（端点がある図形）の抽出を行う。線追跡抽出モジュール１２の処理については、図３等を用いて後述する。
形状解析抽出モジュール１３は、線追跡抽出モジュール１２、後処理モジュール１４と接続されており、線追跡抽出モジュール１２によって開図形が抽出された画像を受け取り、残った線図形である閉図形（端点がない図形）の形状を解析する。解析結果を後処理モジュール１４へ渡す。形状解析抽出モジュール１３の処理については、図１０等を用いて後述する。
【００２４】
後処理モジュール１４は、形状解析抽出モジュール１３と接続されており、形状解析抽出モジュール１３から解析結果を受け取り、開図形及び閉図形の合計と予めわかっている線図形の数とを比較して、又は解析結果である線図形の形状と予めわかっている線図形の形状とを比較して、異なると判断した場合は、画像内の線分の接触している箇所に応じて、線追跡抽出モジュール１２又は形状解析抽出モジュール１３で用いるグラフモデルを変更し、線追跡抽出モジュール１２又は形状解析抽出モジュール１３による処理を再度行わせる制御を行う。なお、予めわかっている線図形の数又は形状とは、例えば、答案用紙、アンケート用紙等は、追記される手書きの記号の数、形状は予め定まっている場合があるので、これを利用するものである。後処理モジュール１４の処理については、図１３等を用いて後述する。なお、後処理モジュール１４による処理は、必ずしも行われなくてもよい。
つまり、本実施の形態は、前処理モジュール１１が受け付けた複数の線図形が含まれている画像を対象として、後処理モジュール１４は個別の線図形（画像又は形状、位置、数等）を出力することになる。
【００２５】
図２は、本実施の形態を含む全体の処理を示す説明図である。
本実施の形態は、例えば、学生・生徒等に対するテストの判定済みの答案用紙の採点、回答が記載済みのアンケート用紙の集計等に用いられるものである。そのために、手書きで追記された線図形を抽出する必要がある。
対象とする画像である受付画像２１として、例えば、学生・生徒等に対するテストの判定済みの答案用紙、回答が記入済みのアンケート用紙等が該当する。受付画像２１内には、追記された線図形として、例えば、図２に示すように円、三角形、チェック記号の手書き線図形が描画されており、それらは重なっている。
追記抽出モジュール２２は、受付画像２１から追記された線図形を抽出して追記画像２３を生成する。例えば、受付画像２１の原画像（つまり、追記されていない画像）との差分をとって追記画像２３を生成する。
一筆線分図形分離モジュール２４は、図１に示した構成を含んでおり、追記画像２３から一筆書きの線図形である一筆線分画像２５、２６、２７を分離する。なお、ここでは、一筆書きの線図形には、一筆書きされた線図形に限られず、これに類する線図形（例えば、「×」のように単純な図形等）も含まれる。また、逆に、たとえ一筆書きで描かれた２つの線図形（例えば円と三角形をつなげた線図形）であったとしても、これを分離した線図形（先の例では、円と三角形）として分離する。
【００２６】
図３は、前処理モジュール１１、線追跡抽出モジュール１２の構成例についての概念的なモジュール構成図である。
前処理モジュール３１は前処理モジュール１１に該当し、線追跡抽出モジュール１２は特徴点・線分抽出モジュール３２、偽線分抽出モジュール３３、グラフモデル構築モジュール３４、ノード解析モジュール３５、開図形抽出モジュール３６を有している。
前処理モジュール３１は、特徴点・線分抽出モジュール３２と接続されており、図１を用いて説明した前処理モジュール１１と同等のものである。
【００２７】
特徴点・線分抽出モジュール３２は、前処理モジュール３１、偽線分抽出モジュール３３と接続されており、前処理モジュール３１によって前処理された画像（複数の線図形が含まれている画像）内の点に関する特徴点及び線分を抽出する。
例えば、点に関する特徴点として、周囲３×３の画素又は５×５の画素を取り出して、予め端点・交差点・分岐点として定めた３×３の画素又は５×５の画素のパターンと比較して、一致するパターンを検出した場合に、その画素を端点・交差点・分岐点とする。
そして、残った画素間を追跡して接続し、線分とする。
【００２８】
偽線分抽出モジュール３３は、特徴点・線分抽出モジュール３２、グラフモデル構築モジュール３４と接続されており、特徴点・線分抽出モジュール３２によって抽出された特徴点及び線分に基づいて、線分のうち偽線分を抽出する。
【００２９】
図５を用いて、偽線分抽出モジュール３３の処理の例を説明する。
図５（Ａ）は、前処理モジュール３１が受け付けた画像であり、三角形と四角形とが交差している画像である。
図５（Ｂ）は、前処理モジュール３１によって細線化処理を施した画像である。図５（Ｂ）に示す対象線分５１の部分が、偽線分である。ここで、偽線分とは、線図形の接触又は交差の部分に発生する線分であって、本来は点で交わる部分が、細線化処理によって線分となっている部分のことをいう。
図５（Ｃ）は、図５（Ｂ）の対象線分５１の部分を、図５（Ａ）の対応する部分に重ね合わせて、かつ拡大して表示したものである。つまり、図５（Ｃ）内の交差している斜線で表されている幅のある線分（線分の輪郭５２で囲まれている部分）は、図５（Ａ）の線分であり、図５（Ｃ）内のその中心の線分（細線化線分５３、注目線分５４等）は、図５（Ｂ）の細線化処理した線分である。
【００３０】
偽線分抽出モジュール３３による処理の例は以下の通りである。
（１）細線化処理前の線分の線幅５５の平均を求める。
（２）線幅の平均に対して短い線分を抽出する。図５（Ｃ）の例では、注目線分５４が抽出される。これは、偽線分は、本来交差点等になるべき箇所に発生するものであるので、線分長が短いことを利用したものである。短い線分であるか否かの判断は、求めた線幅平均に定数を掛けたものとの比較等による。
（３）注目線分５４内の各画素と線分の輪郭５２との最短距離が大きい場合は、その線分を偽線分として抽出する。これは、偽線分は、線分が太い場所にできる傾向があることを利用したものである。最短距離が大きいか否かの判断は、閾値（予め定めたもの、平均の線幅の１／２等）との比較等による。
（４）さらに、線分の両端が奇数の分岐であり端点でない場合は、条件（閾値との比較等）をより厳しく（偽線分と判定しやすく）して、前記（２）、（３）の処理を行ってもよい。これは、交差点が偽線分となっている場合、偽線分の両端は分岐点となることを利用したものである。
（５）そして、抽出した偽線分の中心を、特徴点・線分抽出モジュール３２によって抽出された特徴点として変更する。また、その特徴点で線分が交差するよう、細線化図形を修正する。
【００３１】
グラフモデル構築モジュール３４は、偽線分抽出モジュール３３、ノード解析モジュール３５と接続されており、特徴点・線分抽出モジュール３２及び偽線分抽出モジュール３３による結果に基づいて、グラフモデルを生成する。
なお、偽線分抽出モジュール３３による処理を行わずに、グラフモデル構築モジュール３４は、特徴点・線分抽出モジュール３２による結果に基づいて、グラフモデルを生成するようにしてもよい。
グラフモデル構築モジュール３４の処理については、図６〜図９を用いて後述する。
【００３２】
ノード解析モジュール３５は、グラフモデル構築モジュール３４、開図形抽出モジュール３６と接続されており、グラフモデル構築モジュール３４によって生成されたグラフモデルに基づいて、各図形のノードを解析する。具体的には、図４に示したフローチャートのステップＳ４１２〜ステップＳ４２２で後述する。
【００３３】
開図形抽出モジュール３６は、ノード解析モジュール３５と接続されており、閉じていない線図形を抽出する。
なお、開図形抽出モジュール３６は、ノード解析モジュール３５による処理を行わずに、グラフモデル構築モジュール３４によって生成されたグラフモデルを解析することによって、開図形を抽出するようにしてもよい。
【００３４】
開図形抽出モジュール３６による処理の例は以下の通りである。
（１）奇数ノード（そのノードに接続している辺（エッジ）の数が奇数であるノード）を開始点とする。つまり、端点又は分岐点を開始点とする。
（２）細線化処理した画像上で追跡を行う。複数の分岐がある場合は、角度の変化が最も少ない（つまり、線分間によって構成される角が１８０度に近い）線分を追跡する。
（３）既に追跡を行った画素に到達したら終了する。開始点からこの終了した時点まで追跡した軌跡が開図形であり、これによって開図形を抽出する。
【００３５】
図４は、前処理モジュール１１と線追跡抽出モジュール１２が行う処理例を示すフローチャートである。
ステップＳ４０２では、前処理モジュール３１が、線図形が含まれている画像を受け付ける。
ステップＳ４０４では、前処理モジュール３１が、前述したように前処理（ノイズ除去処理、細線化処理）を行う。
ステップＳ４０６では、特徴点・線分抽出モジュール３２が、前述したように特徴点・線分の抽出処理を行う。
ステップＳ４０８では、偽線分抽出モジュール３３が、前述したように偽線分を抽出する。
ステップＳ４１０では、グラフモデル構築モジュール３４が、ステップＳ４０６、ステップＳ４０８による結果を用いてグラフモデルを生成する。この処理については、図６〜図９を用いて後述する。
【００３６】
ステップＳ４１２からステップＳ４２２までの処理は、ノード解析モジュール３５が行う処理である。
ステップＳ４１２では、ステップＳ４１０で生成したグラフモデルにおいて、各ノードに隣接する（辺によって接続する）ノード数を算出する。
ステップＳ４１４では、対象としているノードの隣接ノード数は３以上であるか否かを判断する。つまり、端点や屈曲点でないか否かを判断している。３以上である場合（分岐点や交差点である場合）はステップＳ４１８へ進み、３未満である場合（端点や屈曲点である場合）はステップＳ４１６へ進む。
ステップＳ４１６では、全てのノードを解析したか否かを判断する。全てのノードを解析した場合はＳ４２４へ進む。そうでない場合は、次のノードを対象としてステップＳ４１４へ戻る。
【００３７】
ステップＳ４１８では、ノードの数は偶数であるか否かを判断する。偶数である場合はステップＳ４２０へ進み、奇数である場合はステップＳ４２２へ進む。
ステップＳ４２０では、偶数ノードの解析を行う。つまり、対となる辺を発見することになる。次にステップＳ４１６へ進む。
ステップＳ４２２では、奇数ノードの解析を行う。つまり、対となる辺に加え、対とはならない辺を発見することになる。次にステップＳ４１６へ進む。
ステップＳ４２４とステップＳ４２６の処理は、開図形抽出モジュール３６が行う処理である。
ステップＳ４２４では、追跡を行っていない奇数ノードが存在するか否かを判断する。存在しない場合は終了（ステップＳ４２８）し、存在する場合はステップＳ４２６へ進む。
ステップＳ４２６では、開図形抽出モジュール３６が、前述したように開図形を抽出する。
【００３８】
図６〜図９を用いて、グラフモデル構築モジュール３４の処理について説明する。
図６（Ａ）は、前処理モジュール３１によって細線化処理が施された結果の細線化線図形６００を示している。この細線化線図形６００は手書きの「４」という文字である。ここで、座標系として、画像の左上を原点（０，０）とし、右にＸ軸、下にＹ軸を規定する。
図６（Ｂ）は、特徴点・線分抽出モジュール３２及び偽線分抽出モジュール３３によって抽出された特徴点（図内のａ、ｂ、ｃ、ｄ、ｅ）と線分であり、特徴点を頂点（ノード）ともいう。また、このノードをつなぐ線分を辺（エッジ）ともいう。
【００３９】
図７は、グラフモデル構築モジュール３４とノード解析モジュール３５が行う処理例を示すフローチャートである。なお、フローチャートの右側に点線で囲まれたものは、各ステップで出力（又は入力）するデータを示している。例えば、頂点はステップＳ７０２によって出力され、ステップＳ７０４で用いられるデータである。
ここで、線図形の頂点（特徴点）についてのデータを記憶する頂点情報テーブル８０、線図形の辺についてのデータを記憶する辺情報テーブル９０について説明する。図７に示すフローチャートは、頂点情報テーブル８０、辺情報テーブル９０内のセルを埋める処理である。図８は、頂点情報テーブル８０のデータ構造を示す説明図である。頂点情報テーブル８０は、頂点欄８１、Ｘ座標欄８２、Ｙ座標欄８３、接続先の頂点欄８４を有している。図９は、辺情報テーブル９０のデータ構造を示す説明図である。辺情報テーブル９０は、辺欄９１、ａｃ欄９２〜ｅｃ欄９５、選択した組となる辺欄９６を有しており、頂点ｃに接続する辺の分析のためのものである。ただし、ａｃ欄９２〜ｅｃ欄９５の数は、頂点ｃに接続する辺の数となる。
【００４０】
ステップＳ７０２では、頂点を抽出する。前段のモジュールの結果から、特徴点の座標を頂点情報テーブル８０のＸ座標欄８２、Ｙ座標欄８３に記憶させる。例えば、頂点ａのＸ座標は１０であり、Ｙ座標は１００であるので、頂点ａに対応するＸ座標欄８２、Ｙ座標欄８３に、それぞれ１０、１００を記憶させる。
【００４１】
ステップＳ７０４では、接続先を探索する。つまり、各頂点から線分を追跡して他の頂点を探索する。ここでは、ステップＳ７０２で抽出した頂点を用いて、そこに接続している線分を追跡して接続先の頂点を探索し、その結果を頂点情報テーブル８０の接続先の頂点欄８４に記憶させる。例えば、頂点ａの接続先として図６（Ｂ）の線図形を追跡すると頂点ｂ、ｃに辿り着くので、頂点ａに対応する接続先の頂点欄８４に、頂点ｂ、ｃを記憶させる。
【００４２】
ステップＳ７０６では、接続先を３つ以上持つ頂点の辺を抽出する。つまり、各頂点の接続先がステップＳ７０４で判明したので、これを利用して、辺を決定する。例えば、頂点ｃの接続先としては、頂点ａ、ｂ、ｃ、ｄがあるので、ａｃ、ｂｃ、ｄｃ、ｅｃの線分を辺として決定する。例えば、辺情報テーブル９０のａｃ欄９２〜ｅｃ欄９５（つまり、列の数）を決定することになる。
【００４３】
ステップＳ７０８では、辺を３以上持つ頂点で辺同士によって構成される角度を求める。例えば、辺ａｃと辺ｂｃのなす角度は１００度であるので、辺情報テーブル９０の辺ｂｃとａｃに対応するａｃ欄９２とｂｃ欄９３に１００を記憶させる。
【００４４】
ステップＳ７１０では、ステップＳ７０８で求めた角度を用いて、組となる辺を決定する。ここで組となる辺とは、対象としている辺と接続している辺であって、その辺とのなす角度が１８０度に近い辺（つまり、辺を追跡する場合に、対象としている辺から次の辺へと追跡すべき辺のことであり、手書きとして最も自然に接続していると考えられる辺のことである）のことである。例えば、辺ａｃとなす角度が１８０度に最も近いものは、１７５度の辺ｄｃであるので、これを辺情報テーブル９０の辺ａｃに対応する選択した組となる辺欄９６に記憶させる。
【００４５】
図１０は、形状解析抽出モジュール１３の構成例についての概念的なモジュール構成図である。
形状解析抽出モジュール１３は、グラフモデル構築モジュール１０１、閉曲線検出モジュール１０２、図形判断モジュール１０３、重複図形除去モジュール１０４を有している。
グラフモデル構築モジュール１０１は、閉曲線検出モジュール１０２と接続されており、前述のグラフモデル構築モジュール３４と同等のものである。
【００４６】
閉曲線検出モジュール１０２は、グラフモデル構築モジュール１０１、図形判断モジュール１０３と接続されており、グラフモデル構築モジュール１０１によって生成されたグラフモデルを解析することによって、端点を有しない閉図形（閉曲線、複数の線分で閉じた図形を形成しているもの）を検出する。ここでの閉図形の検出は、頂点情報テーブル８０を用いて、各点が閉曲線を構成するか否かについて、可能性のあるもの全てを探索して検出する。つまり、グラフの全探索によって、開始点から始めてその開始点に戻ってくる経路を求めることになる。
【００４７】
図形判断モジュール１０３は、閉曲線検出モジュール１０２、重複図形除去モジュール１０４と接続されており、閉図形の形状を判断する。つまり、図形判断モジュール１０３は、閉曲線検出モジュール１０２によって検出された閉図形に対して、多角形近似を行った後に、閉図形の形状を認識する。なお、多角形近似の処理は、必ずしも行わなくてもよい。図形判断モジュール１０３の処理については、図１１に示すフローチャートのステップＳ１１０６〜ステップＳ１１１８までの処理で説明する。
【００４８】
重複図形除去モジュール１０４は、図形判断モジュール１０３と接続されており、図形判断モジュール１０３が抽出した閉図形のうち重複している図形を削除する。なお、重複図形除去モジュール１０４による処理は、必ずしも行わなくてもよい。
【００４９】
重複図形除去モジュール１０４の処理について、図１２を用いて説明する。
図１２（Ａ）は、細線化処理が施された線図形１２０１である。図１２（Ｂ）は、図形判断モジュール１０３によって分離された線図形（円）１２０２、線図形（三角形（小））１２０３、線図形（三角形（大））１２０４である。図１２（Ａ）に示す線図形１２０１は、円と三角形が接触したものであるにもかかわらず、可能性のある閉図形をすべて抽出しているので、このように線図形（三角形（小））１２０３も抽出することになる。
【００５０】
重複図形除去モジュール１０４による処理の例は以下の通りである。
（１）画素数の多い順に閉図形をソートする。例えば、図１２（Ｂ）の場合、線図形（三角形（大））１２０４、線図形（円）１２０２、線図形（三角形（小））１２０３となる。
（２）順番に他図形と重複している画素数を調べ、重複した部分の割合が大きければ、その閉図形を削除する。割合が大であるか否かの判断は、閾値（予め定めたもの、その他の閉図形の重複率の平均等）との比較等による。例えば、図１２（Ｃ）に示すように、線図形（三角形（小））１２０３は三角形の２辺の部分が線図形（三角形（大））１２０４と重複しているので、重複している部分（図１２（Ｃ）の太線部分）が大きい。このとき、重複している図形同士の片方を削除するが、ソート順の低い方（全画素数が少ない方）を選択する。したがって、線図形（三角形（小））１２０３を削除の対象とする。
【００５１】
図１１は、形状解析抽出モジュール１３が行う処理例を示すフローチャートである。
ステップＳ１１０２では、グラフモデル構築モジュール１０１が、前述のグラフモデル構築モジュール３４と同様にグラフモデルを生成する。
ステップＳ１１０４では、閉曲線検出モジュール１０２が、前述したように閉図形を検出する。
【００５２】
ステップＳ１１０６では、図形判断モジュール１０３が、曲線を複数の直線で表す処理を行う。例えば、角点を検出してその間を直線で結ぶ方法などを使う。
ステップＳ１１０８では、図形判断モジュール１０３が、閉図形の線分の数が３であるか否かを判断する。３であれば、ステップＳ１１１８へ進み、それ以外であればステップＳ１１１０へ進む。
ステップＳ１１１０では、図形判断モジュール１０３が、閉図形の線分の数が４であり、かつ全ての角度が９０度に近いものであれば、ステップＳ１１１８へ進み、それ以外であればステップＳ１１１２へ進む。
【００５３】
ステップＳ１１１２では、図形判断モジュール１０３が、ジャギー（線図形のギザギザのこと）を除去する。
ステップＳ１１１４では、図形判断モジュール１０３が、ジャギーが除去された図形に対し多角形近似の処理を行う。ステップＳ１１０６と同様の処理を行ってもよいし、閾値を変更して処理を行ってもよい。
また、多角形近似の処理として２分割法による処理を行ってもよい。２分割法による処理の例は以下の通りである（「ディジタル画像処理」ＣＧ−ＡＲＴＳ協会出版、奥富 正敏著を参照）。
（１）線分列の始点と終点をつないだ線分に対して、各画素から距離を計算する。
（２）最大距離がある閾値（予め定めたもの、距離の平均等）以下である場合、その線分を採用する。そうでない場合は、その画素で画素列を分割し、分割された画素列で前記（１）の処理を再帰的に繰り返す。
（３）画素列の分割がない場合は、処理を終了する。
【００５４】
ステップＳ１１１６では、図形判断モジュール１０３が、閉図形の線分の数が６以上であり、かつ角（例えば、１００度以下の角）の数が２以下である場合はステップＳ１１１８へ進み、それ以外の場合は終了する（ステップＳ１１２２）。
ステップＳ１１１８では、図形判断モジュール１０３が、ステップＳ１１０８から進んできた場合はその閉図形は三角形であると判断し、ステップＳ１１１０から進んできた場合はその閉図形は長方形であると判断し、ステップＳ１１１６から進んできた場合はその閉図形は円であると判断する。そして、その閉図形を抽出する。
ステップＳ１１２０では、重複図形除去モジュール１０４が、前述したように重複している閉図形を削除する。
なお、このフローチャートでは、三角形、長方形、円の判断を行っているが、その他の図形の特徴を用いて判断するようにしてもよい。
【００５５】
図１３は、入力画像に含まれる線図形の形状又は数が既知の場合の処理例を示すフローチャートである。つまり、主に後処理モジュール１４の処理について説明する。後処理モジュール１４は、ステップＳ１３０８〜ステップＳ１３２０の処理を行う。
ステップＳ１３０２では、前処理モジュール１１が、前述したように前処理（ノイズ除去処理、細線化処理）を行う。
ステップＳ１３０４では、線追跡抽出モジュール１２が、前述したように線追跡抽出処理（開図形の抽出処理）を行う。
ステップＳ１３０６では、形状解析抽出モジュール１３が、前述したように形状解析抽出処理（閉図形の抽出処理）を行う。
ステップＳ１３０８では、ステップＳ１３０４及びステップＳ１３０６で抽出した図形の数の合計と予め設定されている図形の数との比較を行う。異なっていればステップＳ１３１０へ進み、それ以外の場合はステップＳ１３２０へ進む。さらに、ステップＳ１３０４及びステップＳ１３０６で抽出した図形の形状と予め設定されている図形の形状との比較を行う。異なっていればステップＳ１３１０へ進み、それ以外の場合はステップＳ１３２０へ進む。
【００５６】
ステップＳ１３１０では、接触ノード候補があるか否かを判断する。ある場合はステップＳ１３１２へ進み、ない場合はステップＳ１３１８へ進む。接触ノードで処理を誤っている場合が多いので、このような判断を行う。なお、接触ノードか否かは、角度で判断する。つまり、角度が１８０度に近いものが２つ存在するか否かによって判断する。
ここで、接触ノードについて、図１４を用いて説明する。図に示すように２つの円が接触したような図形の場合、４つの線分に分かれ、組となる線分の抽出（図７に示すフローチャートのステップＳ７１０）の際に、図に示す交差パス１４０２が選択される。この２つの線分のなす角度が１８０度に近いからである。しかし、この図形は本来２つの円が接触しているので、接触パス１４０１になるように、組となる辺を抽出すべきである。
【００５７】
ステップＳ１３１２では、ステップＳ１３１０で対象となったノードにおいて、再解析を行い、接触が考えられる組（ペア）を探索する。ここで、探索する対象は１８０度に近い２番目の候補から行うようにする。ステップＳ１３１２の処理では、辺情報テーブル９０の選択した組となる辺欄９６を変更する。
ステップＳ１３１４では、ステップＳ１３０４、ステップＳ１３０６の処理（つまり、線追跡抽出モジュール１２、形状解析抽出モジュール１３の処理）を再度実行する。
ステップＳ１３１６では、ステップＳ１３０８の処理を行う。つまり、再実行の結果が正しかったか否かの判断を行う。未だ異なっている場合はステップＳ１３１８へ進み、一致する場合はステップＳ１３２０へ進む。
ステップＳ１３１８では、接触ノードがなかった場合、又は再度実行した場合にあっても、予め設定されている図形の数又は形状が異なった場合であるので、処理ができなかった旨のエラー報告を行う。
ステップＳ１３２０では、その他の後処理を行う。例えば、線分幅を回復すること、欠損部分を補間すること、本実施の形態による処理結果を他の装置で使用させるためのデータの加工等である。
【００５８】
図１５は、入力画像に含まれる線図形の数が既知の場合の処理例を示すフローチャートである。図１３に示したフローチャートでは、数及び形状を予め設定した値と比較していたが（ステップＳ１３０８，Ｓ１３１６）、図１５では、線図形の数だけを比較の対象としている場合である。つまり、ステップＳ１５０８，Ｓ１５１６はそれぞれステップＳ１３０８，Ｓ１３１６と異なり、線図形の数だけを比較の対象としている。その他の各ステップの処理は、図１３に示したフローチャートにおける各ステップと同様である。
【００５９】
図１６は、後処理モジュール１４による処理を行わなかった場合の処理例を示すフローチャートである。つまり、図１３に示したフローチャートにおけるステップＳ１３０８以降を行わない場合である。ステップＳ１６０２〜ステップＳ１６０６の処理は、ステップＳ１３０２〜ステップＳ１３０６の処理と同様である。
【００６０】
図１７を参照して、本実施の形態のハードウェア構成例について説明する。図１７に示す構成は、例えばパーソナルコンピュータ（ＰＣ）などによって構成されるものであり、スキャナ等のデータ読み取り部１７１７と、プリンタなどのデータ出力部１７１８を備えたハードウェア構成例を示している。
【００６１】
ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）１７０１は、前述の実施の形態において説明した各種のモジュール、すなわち、前処理モジュール１１、線追跡抽出モジュール１２、形状解析抽出モジュール１３、後処理モジュール１４等の各モジュールの実行シーケンスを記述したコンピュータ・プログラムにしたがった処理を実行する制御部である。
【００６２】
ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）１７０２は、ＣＰＵ１７０１が使用するプログラムや演算パラメータ等を格納する。ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）１７０３は、ＣＰＵ１７０１の実行において使用するプログラムや、その実行において適宜変化するパラメータ等を格納する。これらはＣＰＵバスなどから構成されるホストバス１７０４により相互に接続されている。
【００６３】
ホストバス１７０４は、ブリッジ１７０５を介して、ＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ Ｃｏｍｐｏｎｅｎｔ Ｉｎｔｅｒｃｏｎｎｅｃｔ／Ｉｎｔｅｒｆａｃｅ）バスなどの外部バス１７０６に接続されている。
【００６４】
キーボード１７０８、マウス等のポインティングデバイス１７０９は、操作者により操作される入力デバイスである。ディスプレイ１７１０は、液晶表示装置又はＣＲＴ（Ｃａｔｈｏｄｅ Ｒａｙ Ｔｕｂｅ）などから成り、各種情報をテキストやイメージ情報として表示する。
【００６５】
ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）１７１１は、ハードディスクを内蔵し、ハードディスクを駆動し、ＣＰＵ１７０１によって実行するプログラムや情報を記録又は再生させる。ハードディスクは、受け付けられた画像、頂点情報テーブル８０、辺情報テーブル９０などが格納される。さらに、その他の各種のデータ処理プログラム等、各種コンピュータ・プログラムが格納される。
【００６６】
ドライブ１７１２は、装着されている磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリ等のリムーバブル記録媒体１７１３に記録されているデータ又はプログラムを読み出して、そのデータ又はプログラムを、インタフェース１７０７、外部バス１７０６、ブリッジ１７０５、及びホストバス１７０４を介して接続されているＲＡＭ１７０３に供給する。リムーバブル記録媒体１７１３も、ハードディスクと同様のデータ記録領域として利用可能である。
【００６７】
接続ポート１７１４は、外部接続機器１７１５を接続するポートであり、ＵＳＢ、ＩＥＥＥ１３９４等の接続部を持つ。接続ポート１７１４は、インタフェース１７０７、及び外部バス１７０６、ブリッジ１７０５、ホストバス１７０４等を介してＣＰＵ１７０１等に接続されている。通信部１７１６は、ネットワークに接続され、外部とのデータ通信処理を実行する。データ読み取り部１７１７は、例えばスキャナであり、ドキュメントの読み取り処理を実行する。データ出力部１７１８は、例えばプリンタであり、ドキュメントデータの出力処理を実行する。
【００６８】
なお、図１７に示すハードウェア構成は、１つの構成例を示すものであり、本実施の形態は、図１７に示す構成に限らず、本実施の形態において説明したモジュールを実行可能な構成であればよい。例えば、一部のモジュールを専用のハードウェア（例えば特定用途向け集積回路（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ：ＡＳＩＣ）等）で構成してもよく、一部のモジュールは外部のシステム内にあり通信回線で接続しているような形態でもよく、さらに図１７に示すシステムが複数互いに通信回線によって接続されていて互いに協調動作するようにしてもよい。また、複写機、ファックス、スキャナ、プリンタ、複合機（スキャナ、プリンタ、複写機、ファックス等のいずれか２つ以上の機能を有している画像処理装置）などに組み込まれていてもよい。
【００６９】
前記実施の形態において、図８、図９で示したデータ構造は、これらのデータ構造に限られず、他のデータ構造であってもよい。例えば、テーブル構造はリンク構造等であってもよい。また、データ項目は、これらに図示したものに限られず、他のデータ項目（例えば、線分長）を有していてもよい。
【００７０】
なお、説明したプログラムについては、記録媒体に格納して提供してもよく、また、そのプログラムを通信手段によって提供してもよい。その場合、例えば、前記説明したプログラムについて、「プログラムを記録したコンピュータ読み取り可能な記録媒体」の発明として捉えてもよい。
「プログラムを記録したコンピュータ読み取り可能な記録媒体」とは、プログラムのインストール、実行、プログラムの流通などのために用いられる、プログラムが記録されたコンピュータで読み取り可能な記録媒体をいう。
なお、記録媒体としては、例えば、デジタル・バーサタイル・ディスク（ＤＶＤ）であって、ＤＶＤフォーラムで策定された規格である「ＤＶＤ−Ｒ、ＤＶＤ−ＲＷ、ＤＶＤ−ＲＡＭ等」、ＤＶＤ＋ＲＷで策定された規格である「ＤＶＤ＋Ｒ、ＤＶＤ＋ＲＷ等」、コンパクトディスク（ＣＤ）であって、読出し専用メモリ（ＣＤ−ＲＯＭ）、ＣＤレコーダブル（ＣＤ−Ｒ）、ＣＤリライタブル（ＣＤ−ＲＷ）等、光磁気ディスク（ＭＯ）、フレキシブルディスク（ＦＤ）、磁気テープ、ハードディスク、読出し専用メモリ（ＲＯＭ）、電気的消去及び書換可能な読出し専用メモリ（ＥＥＰＲＯＭ）、フラッシュ・メモリ、ランダム・アクセス・メモリ（ＲＡＭ）等が含まれる。
そして、前記のプログラム又はその一部は、前記記録媒体に記録して保存や流通等させてもよい。また、通信によって、例えば、ローカル・エリア・ネットワーク（ＬＡＮ）、メトロポリタン・エリア・ネットワーク（ＭＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、インターネット、イントラネット、エクストラネット等に用いられる有線ネットワーク、あるいは無線通信ネットワーク、さらにこれらの組合せ等の伝送媒体を用いて伝送させてもよく、また、搬送波に乗せて搬送させてもよい。
さらに、前記のプログラムは、他のプログラムの一部分であってもよく、あるいは別個のプログラムと共に記録媒体に記録されていてもよい。また、複数の記録媒体に分割して
記録されていてもよい。また、圧縮や暗号化など、復元可能であればどのような態様で記録されていてもよい。
【図面の簡単な説明】
【００７１】
【図１】本実施の形態の構成例についての概念的なモジュール構成図である。
【図２】本実施の形態を含む全体の処理を示す説明図である。
【図３】線追跡抽出モジュールの構成例についての概念的なモジュール構成図である。
【図４】線追跡抽出モジュールが行う処理例を示すフローチャートである。
【図５】偽線分抽出モジュールが行う処理例を示す説明図である。
【図６】グラフモデル構築モジュールとノード解析モジュールが行う処理例を示す説明図である。
【図７】グラフモデル構築モジュールとノード解析モジュールが行う処理例を示すフローチャートである。
【図８】頂点情報テーブルのデータ構造を示す説明図である。
【図９】辺情報テーブルのデータ構造を示す説明図である。
【図１０】形状解析抽出モジュールの構成例についての概念的なモジュール構成図である。
【図１１】形状解析抽出モジュールが行う処理例を示すフローチャートである。
【図１２】重複図形除去モジュールが行う処理例を示す説明図である。
【図１３】入力画像に含まれる線図形の形状又は数が既知の場合の処理例を示すフローチャートである。
【図１４】線図形の接触の例を示す説明図である。
【図１５】入力画像に含まれる線図形の数が既知の場合の処理例を示すフローチャートである。
【図１６】後処理モジュールによる処理を行わなかった場合の処理例を示すフローチャートである。
【図１７】本実施の形態を実現するコンピュータのハードウェア構成例を示すブロック図である。
【符号の説明】
【００７２】
１１…前処理モジュール
１２…線追跡抽出モジュール
１３…形状解析抽出モジュール
１４…後処理モジュール
２１…受付画像
２２…追記抽出モジュール
２３…追記画像
２４…一筆線分図形分離モジュール
２５…一筆線分画像
２６…一筆線分画像
２７…一筆線分画像
３１…前処理モジュール
３２…特徴点・線分抽出モジュール
３３…偽線分抽出モジュール
３４…グラフモデル構築モジュール
３５…ノード解析モジュール
３６…開図形抽出モジュール
１０１…グラフモデル構築モジュール
１０２…閉曲線検出モジュール
１０３…図形判断モジュール
１０４…重複図形除去モジュール
【技術分野】
【０００１】
本発明は、画像処理装置及び画像処理プログラムに関する。
【背景技術】
【０００２】
手書きされた文字を認識しようとする場合、複数の文字やその他図形等との接触があると認識率が低下するため、これらを分離することが求められている。
【０００３】
これに関連する技術として、例えば、特許文献１には、文字列画像全体の構造的な情報を用いて、接触文字数、接触の仕方に関係なく文字列を容易に認識することを目的とし、文字列認識処理では、まず、抽出された文字列画像を細線化して骨格線図形を生成し、次に、骨格線図形を複数の単純な部分曲線に分割し、次に、部分曲線を組み合わせて文字列の部分図形を生成し、該部分図形について文字認識を行い、次に、文字に認識された部分図形をノードとし、該ノードを重み付きのリンクで多様に結んでネットワークを構成し、最後に、ネットワークから最適解の経路を選び、そのノードの組合せを出力することが開示されている。
【０００４】
例えば、特許文献２には、文字画像から抽出したストロークが接触ストロークであるときの切断候補と切断回数を抑えて処理効率を向上させることを課題とし、文字列画像記憶部から入力した画像から初期ストローク抽出部で初期ストロークを抽出し、接触ストローク判断部で接触したストロークと判定したものだけ切断候補抽出部で切断候補箇所を抽出し、最適候補選択部で切断候補から切断箇所を選択し、ストローク情報更新部で接触ストロークを選択された箇所で切断して新しいストロークを生成し、文字切り出し候補生成部は、新しいストロークと非接触ストロークバッファに記憶されていた接触していないストロークとを組み合わせて文字切り出し候補を生成して出力することが開示されている。
【０００５】
また、例えば、特許文献３には、ノイズや線幅の変動の影響を受けず、またストロークが完全に交差している接触箇所があっても高い確率で正解を含む文字切り出し候補を生成でき、しかも候補数の増大を防ぐことができる文字切り出し候補生成装置を提供することを課題とし、文字列画像記憶部は光学的に走査された文字列画像を格納し、線分素抽出部はこの格納された文字列画像から特定の方向成分を持つ部分である線分素をモルフォロジー演算を使用して抽出し、ストローク作成部はこの抽出された線分素をマージして或る程度滑らかにつながる曲線部分であるストロークを作成し、最後に、文字切り出し候補作成部は作成されたストロークを組み合わせて文字切り出し候補を作成することが開示されている。
【特許文献１】特開平０６−０７６１１４号公報
【特許文献２】特開平１１−１４９５２１号公報
【特許文献３】特開平０９−２８８７１５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところで、文字画像の高さ又は接触位置を限定して線図形を抽出している場合は、それ以外の線図形の大きさ、接触又は交差がある場合は対処することができない。
本発明は、グラフモデルを生成し、開図形と閉図形とを別々に抽出することで、線図形の大きさのばらつき、接触又は交差の制限を緩和して、線図形の抽出をする画像処理装置及び画像処理プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
かかる目的を達成するための本発明の要旨とするところは、次の各項の発明に存する。
請求項１記載の発明は、線図形を含む画像内の点に関する特徴及び線分を抽出する抽出手段と、前記抽出手段による結果に基づいて、グラフモデルを生成するグラフモデル生成手段と、前記グラフモデル生成手段によって生成されたグラフモデルを解析することによって、端点を有する開図形を抽出する開図形抽出手段と、前記グラフモデル生成手段によって生成されたグラフモデルを解析することによって、端点を有しない閉図形を抽出する閉図形抽出手段を具備することを特徴とする画像処理装置である。
【０００８】
請求項２記載の発明は、前記抽出手段によって抽出された特徴点及び線分に基づいて、前記線分のうち偽線分を識別する偽線分識別手段を具備し、前記グラフモデル生成手段は、前記抽出手段及び前記偽線分識別手段による結果に基づいて、グラフモデルを生成することを特徴とする請求項１に記載の画像処理装置である。
【０００９】
請求項３記載の発明は、前記閉図形抽出手段は、前記グラフモデルを解析することによって、閉図形を抽出し、多角形近似を行った後に、閉図形の形状を認識することを特徴とする請求項１に記載の画像処理装置である。
【００１０】
請求項４記載の発明は、前記閉図形抽出手段は、抽出した閉図形のうち重複している図形を削除することを特徴とする請求項１又は３に記載の画像処理装置である。
【００１１】
請求項５記載の発明は、前記開図形抽出手段によって抽出された開図形及び前記閉図形抽出手段によって抽出された閉図形の合計が、前記画像内に含まれている図形の数と異なるか否かを判断する判断手段と、前記判断手段によって異なると判断された場合は、前記画像内の線分の接触している箇所に応じて、前記グラフモデルを変更し、前記開図形抽出手段又は前記閉図形抽出手段による処理を行わせる再処理手段をさらに具備することを特徴とする請求項１に記載の画像処理装置である。
【００１２】
請求項６記載の発明は、前記開図形抽出手段によって抽出された開図形又は前記閉図形抽出手段によって抽出された閉図形の形状が、前記画像内に含まれている図形の形状と異なるか否かを判断する判断手段と、前記判断手段によって異なると判断された場合は、前記画像内の線分の接触している箇所に応じて、前記グラフモデルを変更し、前記開図形抽出手段又は前記閉図形抽出手段による処理を行わせる再処理手段をさらに具備することを特徴とする請求項１に記載の画像処理装置である。
【００１３】
請求項７記載の発明は、コンピュータを、線図形を含む画像内の点に関する特徴及び線分を抽出する抽出手段と、前記抽出手段による結果に基づいて、グラフモデルを生成するグラフモデル生成手段と、前記グラフモデル生成手段によって生成されたグラフモデルを解析することによって、端点を有する開図形を抽出する開図形抽出手段と、前記グラフモデル生成手段によって生成されたグラフモデルを解析することによって、端点を有しない閉図形を抽出する閉図形抽出手段として機能させることを特徴とする画像処理プログラムである。
【発明の効果】
【００１４】
請求項１の画像処理装置によれば、線図形の大きさのばらつき、接触又は交差の制限を緩和して、線図形の抽出をすることができるようになる。
【００１５】
請求項２の画像処理装置によれば、線分の太さによって交差部分に発生しやすい偽線分を識別することができ、より正確な線図形の抽出を行うことができるようになる。
【００１６】
請求項３の画像処理装置によれば、形状を認識することによって、より正確な線図形の抽出をすることができるようになる。
【００１７】
請求項４の画像処理装置によれば、余分な線図形を抽出することを抑制することができるようになる。
【００１８】
請求項５の画像処理装置によれば、予め図形の数が判明している場合は、より正確に線図形を抽出することができるようになる。
【００１９】
請求項６の画像処理装置によれば、予め図形の形状が判明している場合は、より正確に線図形を抽出することができるようになる。
【００２０】
請求項７の画像処理プログラムによれば、線図形の大きさのばらつき、接触又は交差の制限を緩和して、線図形の抽出をすることができるようになる。
【発明を実施するための最良の形態】
【００２１】
以下、図面に基づき本発明を実現するにあたっての好適な一実施の形態の例を説明する。
図１は、本実施の形態の構成例についての概念的なモジュール構成図を示している。
なお、モジュールとは、一般的に論理的に分離可能なソフトウェア（コンピュータ・プログラム）、ハードウェア等の部品を指す。したがって、本実施の形態におけるモジュールはコンピュータ・プログラムにおけるモジュールのことだけでなく、ハードウェア構成におけるモジュールも指す。それゆえ、本実施の形態は、コンピュータ・プログラム、システム及び方法の説明をも兼ねている。ただし、説明の都合上、「記憶する」、「記憶させる」、これらと同等の文言を用いるが、これらの文言は、実施の形態がコンピュータ・プログラムの場合は、記憶装置に記憶させること、又は記憶装置に記憶させるように制御するの意である。また、モジュールは機能にほぼ一対一に対応しているが、実装においては、１モジュールを１プログラムで構成してもよいし、複数モジュールを１プログラムで構成してもよく、逆に１モジュールを複数プログラムで構成してもよい。また、複数モジュールは１コンピュータによって実行されてもよいし、分散又は並列環境におけるコンピュータによって１モジュールが複数コンピュータで実行されてもよい。なお、１つのモジュールに他のモジュールが含まれていてもよい。また、以下、「接続」とは物理的な接続の他、論理的な接続（データの授受、指示、データ間の参照関係等）を含む。
また、システム又は装置とは、複数のコンピュータ、ハードウェア、装置等がネットワーク（一対一対応の通信接続を含む）等の通信手段で接続されて構成されるほか、１つのコンピュータ、ハードウェア、装置等によって実現される場合も含まれる。
【００２２】
本実施の形態は、図１に示すように、前処理モジュール１１、線追跡抽出モジュール１２、形状解析抽出モジュール１３、後処理モジュール１４を有している。
前処理モジュール１１は、線追跡抽出モジュール１２と接続されており、対象となる画像を入力し、それに対して前処理を行い、線追跡抽出モジュール１２にその画像を渡す。
ここで、対象となる画像は、手書きで記入した複数の線図形を含む画像である。なお、その線図形には、紙文書にペンで手書きされたものの他に、電子ペン等で電子的に記入された線図形を含む画像（軌跡としての位置データ）であってもよい。また、紙文書の画像はスキャナ等の画像入力装置によって入力されたものである。より具体的には、例えば、学生・生徒等に対するテストの判定済みの答案用紙、回答が記入済みのアンケート用紙等に追記された手書きの線図形等の画像が該当する。
前処理としては、ノイズ除去処理と細線化処理等がある。ノイズ除去処理としては、例えば、孤立点の除去、かすれ線の補間、傾き補正等がある。細線化処理は、二値画像を幅１画素の線画像に変換する処理をいい、パターン認識等の前処理として用いられている処理（予め定められたパターンとのマッチングを行い、一致すればそのうちの定められた画素を削除する等）を用いる。
【００２３】
線追跡抽出モジュール１２は、前処理モジュール１１、形状解析抽出モジュール１３と接続されており、前処理モジュール１１から細線化処理された線図形の画像を受け取り、その中の線分を追跡して抽出することにより、開図形（端点がある図形）の抽出を行う。線追跡抽出モジュール１２の処理については、図３等を用いて後述する。
形状解析抽出モジュール１３は、線追跡抽出モジュール１２、後処理モジュール１４と接続されており、線追跡抽出モジュール１２によって開図形が抽出された画像を受け取り、残った線図形である閉図形（端点がない図形）の形状を解析する。解析結果を後処理モジュール１４へ渡す。形状解析抽出モジュール１３の処理については、図１０等を用いて後述する。
【００２４】
後処理モジュール１４は、形状解析抽出モジュール１３と接続されており、形状解析抽出モジュール１３から解析結果を受け取り、開図形及び閉図形の合計と予めわかっている線図形の数とを比較して、又は解析結果である線図形の形状と予めわかっている線図形の形状とを比較して、異なると判断した場合は、画像内の線分の接触している箇所に応じて、線追跡抽出モジュール１２又は形状解析抽出モジュール１３で用いるグラフモデルを変更し、線追跡抽出モジュール１２又は形状解析抽出モジュール１３による処理を再度行わせる制御を行う。なお、予めわかっている線図形の数又は形状とは、例えば、答案用紙、アンケート用紙等は、追記される手書きの記号の数、形状は予め定まっている場合があるので、これを利用するものである。後処理モジュール１４の処理については、図１３等を用いて後述する。なお、後処理モジュール１４による処理は、必ずしも行われなくてもよい。
つまり、本実施の形態は、前処理モジュール１１が受け付けた複数の線図形が含まれている画像を対象として、後処理モジュール１４は個別の線図形（画像又は形状、位置、数等）を出力することになる。
【００２５】
図２は、本実施の形態を含む全体の処理を示す説明図である。
本実施の形態は、例えば、学生・生徒等に対するテストの判定済みの答案用紙の採点、回答が記載済みのアンケート用紙の集計等に用いられるものである。そのために、手書きで追記された線図形を抽出する必要がある。
対象とする画像である受付画像２１として、例えば、学生・生徒等に対するテストの判定済みの答案用紙、回答が記入済みのアンケート用紙等が該当する。受付画像２１内には、追記された線図形として、例えば、図２に示すように円、三角形、チェック記号の手書き線図形が描画されており、それらは重なっている。
追記抽出モジュール２２は、受付画像２１から追記された線図形を抽出して追記画像２３を生成する。例えば、受付画像２１の原画像（つまり、追記されていない画像）との差分をとって追記画像２３を生成する。
一筆線分図形分離モジュール２４は、図１に示した構成を含んでおり、追記画像２３から一筆書きの線図形である一筆線分画像２５、２６、２７を分離する。なお、ここでは、一筆書きの線図形には、一筆書きされた線図形に限られず、これに類する線図形（例えば、「×」のように単純な図形等）も含まれる。また、逆に、たとえ一筆書きで描かれた２つの線図形（例えば円と三角形をつなげた線図形）であったとしても、これを分離した線図形（先の例では、円と三角形）として分離する。
【００２６】
図３は、前処理モジュール１１、線追跡抽出モジュール１２の構成例についての概念的なモジュール構成図である。
前処理モジュール３１は前処理モジュール１１に該当し、線追跡抽出モジュール１２は特徴点・線分抽出モジュール３２、偽線分抽出モジュール３３、グラフモデル構築モジュール３４、ノード解析モジュール３５、開図形抽出モジュール３６を有している。
前処理モジュール３１は、特徴点・線分抽出モジュール３２と接続されており、図１を用いて説明した前処理モジュール１１と同等のものである。
【００２７】
特徴点・線分抽出モジュール３２は、前処理モジュール３１、偽線分抽出モジュール３３と接続されており、前処理モジュール３１によって前処理された画像（複数の線図形が含まれている画像）内の点に関する特徴点及び線分を抽出する。
例えば、点に関する特徴点として、周囲３×３の画素又は５×５の画素を取り出して、予め端点・交差点・分岐点として定めた３×３の画素又は５×５の画素のパターンと比較して、一致するパターンを検出した場合に、その画素を端点・交差点・分岐点とする。
そして、残った画素間を追跡して接続し、線分とする。
【００２８】
偽線分抽出モジュール３３は、特徴点・線分抽出モジュール３２、グラフモデル構築モジュール３４と接続されており、特徴点・線分抽出モジュール３２によって抽出された特徴点及び線分に基づいて、線分のうち偽線分を抽出する。
【００２９】
図５を用いて、偽線分抽出モジュール３３の処理の例を説明する。
図５（Ａ）は、前処理モジュール３１が受け付けた画像であり、三角形と四角形とが交差している画像である。
図５（Ｂ）は、前処理モジュール３１によって細線化処理を施した画像である。図５（Ｂ）に示す対象線分５１の部分が、偽線分である。ここで、偽線分とは、線図形の接触又は交差の部分に発生する線分であって、本来は点で交わる部分が、細線化処理によって線分となっている部分のことをいう。
図５（Ｃ）は、図５（Ｂ）の対象線分５１の部分を、図５（Ａ）の対応する部分に重ね合わせて、かつ拡大して表示したものである。つまり、図５（Ｃ）内の交差している斜線で表されている幅のある線分（線分の輪郭５２で囲まれている部分）は、図５（Ａ）の線分であり、図５（Ｃ）内のその中心の線分（細線化線分５３、注目線分５４等）は、図５（Ｂ）の細線化処理した線分である。
【００３０】
偽線分抽出モジュール３３による処理の例は以下の通りである。
（１）細線化処理前の線分の線幅５５の平均を求める。
（２）線幅の平均に対して短い線分を抽出する。図５（Ｃ）の例では、注目線分５４が抽出される。これは、偽線分は、本来交差点等になるべき箇所に発生するものであるので、線分長が短いことを利用したものである。短い線分であるか否かの判断は、求めた線幅平均に定数を掛けたものとの比較等による。
（３）注目線分５４内の各画素と線分の輪郭５２との最短距離が大きい場合は、その線分を偽線分として抽出する。これは、偽線分は、線分が太い場所にできる傾向があることを利用したものである。最短距離が大きいか否かの判断は、閾値（予め定めたもの、平均の線幅の１／２等）との比較等による。
（４）さらに、線分の両端が奇数の分岐であり端点でない場合は、条件（閾値との比較等）をより厳しく（偽線分と判定しやすく）して、前記（２）、（３）の処理を行ってもよい。これは、交差点が偽線分となっている場合、偽線分の両端は分岐点となることを利用したものである。
（５）そして、抽出した偽線分の中心を、特徴点・線分抽出モジュール３２によって抽出された特徴点として変更する。また、その特徴点で線分が交差するよう、細線化図形を修正する。
【００３１】
グラフモデル構築モジュール３４は、偽線分抽出モジュール３３、ノード解析モジュール３５と接続されており、特徴点・線分抽出モジュール３２及び偽線分抽出モジュール３３による結果に基づいて、グラフモデルを生成する。
なお、偽線分抽出モジュール３３による処理を行わずに、グラフモデル構築モジュール３４は、特徴点・線分抽出モジュール３２による結果に基づいて、グラフモデルを生成するようにしてもよい。
グラフモデル構築モジュール３４の処理については、図６〜図９を用いて後述する。
【００３２】
ノード解析モジュール３５は、グラフモデル構築モジュール３４、開図形抽出モジュール３６と接続されており、グラフモデル構築モジュール３４によって生成されたグラフモデルに基づいて、各図形のノードを解析する。具体的には、図４に示したフローチャートのステップＳ４１２〜ステップＳ４２２で後述する。
【００３３】
開図形抽出モジュール３６は、ノード解析モジュール３５と接続されており、閉じていない線図形を抽出する。
なお、開図形抽出モジュール３６は、ノード解析モジュール３５による処理を行わずに、グラフモデル構築モジュール３４によって生成されたグラフモデルを解析することによって、開図形を抽出するようにしてもよい。
【００３４】
開図形抽出モジュール３６による処理の例は以下の通りである。
（１）奇数ノード（そのノードに接続している辺（エッジ）の数が奇数であるノード）を開始点とする。つまり、端点又は分岐点を開始点とする。
（２）細線化処理した画像上で追跡を行う。複数の分岐がある場合は、角度の変化が最も少ない（つまり、線分間によって構成される角が１８０度に近い）線分を追跡する。
（３）既に追跡を行った画素に到達したら終了する。開始点からこの終了した時点まで追跡した軌跡が開図形であり、これによって開図形を抽出する。
【００３５】
図４は、前処理モジュール１１と線追跡抽出モジュール１２が行う処理例を示すフローチャートである。
ステップＳ４０２では、前処理モジュール３１が、線図形が含まれている画像を受け付ける。
ステップＳ４０４では、前処理モジュール３１が、前述したように前処理（ノイズ除去処理、細線化処理）を行う。
ステップＳ４０６では、特徴点・線分抽出モジュール３２が、前述したように特徴点・線分の抽出処理を行う。
ステップＳ４０８では、偽線分抽出モジュール３３が、前述したように偽線分を抽出する。
ステップＳ４１０では、グラフモデル構築モジュール３４が、ステップＳ４０６、ステップＳ４０８による結果を用いてグラフモデルを生成する。この処理については、図６〜図９を用いて後述する。
【００３６】
ステップＳ４１２からステップＳ４２２までの処理は、ノード解析モジュール３５が行う処理である。
ステップＳ４１２では、ステップＳ４１０で生成したグラフモデルにおいて、各ノードに隣接する（辺によって接続する）ノード数を算出する。
ステップＳ４１４では、対象としているノードの隣接ノード数は３以上であるか否かを判断する。つまり、端点や屈曲点でないか否かを判断している。３以上である場合（分岐点や交差点である場合）はステップＳ４１８へ進み、３未満である場合（端点や屈曲点である場合）はステップＳ４１６へ進む。
ステップＳ４１６では、全てのノードを解析したか否かを判断する。全てのノードを解析した場合はＳ４２４へ進む。そうでない場合は、次のノードを対象としてステップＳ４１４へ戻る。
【００３７】
ステップＳ４１８では、ノードの数は偶数であるか否かを判断する。偶数である場合はステップＳ４２０へ進み、奇数である場合はステップＳ４２２へ進む。
ステップＳ４２０では、偶数ノードの解析を行う。つまり、対となる辺を発見することになる。次にステップＳ４１６へ進む。
ステップＳ４２２では、奇数ノードの解析を行う。つまり、対となる辺に加え、対とはならない辺を発見することになる。次にステップＳ４１６へ進む。
ステップＳ４２４とステップＳ４２６の処理は、開図形抽出モジュール３６が行う処理である。
ステップＳ４２４では、追跡を行っていない奇数ノードが存在するか否かを判断する。存在しない場合は終了（ステップＳ４２８）し、存在する場合はステップＳ４２６へ進む。
ステップＳ４２６では、開図形抽出モジュール３６が、前述したように開図形を抽出する。
【００３８】
図６〜図９を用いて、グラフモデル構築モジュール３４の処理について説明する。
図６（Ａ）は、前処理モジュール３１によって細線化処理が施された結果の細線化線図形６００を示している。この細線化線図形６００は手書きの「４」という文字である。ここで、座標系として、画像の左上を原点（０，０）とし、右にＸ軸、下にＹ軸を規定する。
図６（Ｂ）は、特徴点・線分抽出モジュール３２及び偽線分抽出モジュール３３によって抽出された特徴点（図内のａ、ｂ、ｃ、ｄ、ｅ）と線分であり、特徴点を頂点（ノード）ともいう。また、このノードをつなぐ線分を辺（エッジ）ともいう。
【００３９】
図７は、グラフモデル構築モジュール３４とノード解析モジュール３５が行う処理例を示すフローチャートである。なお、フローチャートの右側に点線で囲まれたものは、各ステップで出力（又は入力）するデータを示している。例えば、頂点はステップＳ７０２によって出力され、ステップＳ７０４で用いられるデータである。
ここで、線図形の頂点（特徴点）についてのデータを記憶する頂点情報テーブル８０、線図形の辺についてのデータを記憶する辺情報テーブル９０について説明する。図７に示すフローチャートは、頂点情報テーブル８０、辺情報テーブル９０内のセルを埋める処理である。図８は、頂点情報テーブル８０のデータ構造を示す説明図である。頂点情報テーブル８０は、頂点欄８１、Ｘ座標欄８２、Ｙ座標欄８３、接続先の頂点欄８４を有している。図９は、辺情報テーブル９０のデータ構造を示す説明図である。辺情報テーブル９０は、辺欄９１、ａｃ欄９２〜ｅｃ欄９５、選択した組となる辺欄９６を有しており、頂点ｃに接続する辺の分析のためのものである。ただし、ａｃ欄９２〜ｅｃ欄９５の数は、頂点ｃに接続する辺の数となる。
【００４０】
ステップＳ７０２では、頂点を抽出する。前段のモジュールの結果から、特徴点の座標を頂点情報テーブル８０のＸ座標欄８２、Ｙ座標欄８３に記憶させる。例えば、頂点ａのＸ座標は１０であり、Ｙ座標は１００であるので、頂点ａに対応するＸ座標欄８２、Ｙ座標欄８３に、それぞれ１０、１００を記憶させる。
【００４１】
ステップＳ７０４では、接続先を探索する。つまり、各頂点から線分を追跡して他の頂点を探索する。ここでは、ステップＳ７０２で抽出した頂点を用いて、そこに接続している線分を追跡して接続先の頂点を探索し、その結果を頂点情報テーブル８０の接続先の頂点欄８４に記憶させる。例えば、頂点ａの接続先として図６（Ｂ）の線図形を追跡すると頂点ｂ、ｃに辿り着くので、頂点ａに対応する接続先の頂点欄８４に、頂点ｂ、ｃを記憶させる。
【００４２】
ステップＳ７０６では、接続先を３つ以上持つ頂点の辺を抽出する。つまり、各頂点の接続先がステップＳ７０４で判明したので、これを利用して、辺を決定する。例えば、頂点ｃの接続先としては、頂点ａ、ｂ、ｃ、ｄがあるので、ａｃ、ｂｃ、ｄｃ、ｅｃの線分を辺として決定する。例えば、辺情報テーブル９０のａｃ欄９２〜ｅｃ欄９５（つまり、列の数）を決定することになる。
【００４３】
ステップＳ７０８では、辺を３以上持つ頂点で辺同士によって構成される角度を求める。例えば、辺ａｃと辺ｂｃのなす角度は１００度であるので、辺情報テーブル９０の辺ｂｃとａｃに対応するａｃ欄９２とｂｃ欄９３に１００を記憶させる。
【００４４】
ステップＳ７１０では、ステップＳ７０８で求めた角度を用いて、組となる辺を決定する。ここで組となる辺とは、対象としている辺と接続している辺であって、その辺とのなす角度が１８０度に近い辺（つまり、辺を追跡する場合に、対象としている辺から次の辺へと追跡すべき辺のことであり、手書きとして最も自然に接続していると考えられる辺のことである）のことである。例えば、辺ａｃとなす角度が１８０度に最も近いものは、１７５度の辺ｄｃであるので、これを辺情報テーブル９０の辺ａｃに対応する選択した組となる辺欄９６に記憶させる。
【００４５】
図１０は、形状解析抽出モジュール１３の構成例についての概念的なモジュール構成図である。
形状解析抽出モジュール１３は、グラフモデル構築モジュール１０１、閉曲線検出モジュール１０２、図形判断モジュール１０３、重複図形除去モジュール１０４を有している。
グラフモデル構築モジュール１０１は、閉曲線検出モジュール１０２と接続されており、前述のグラフモデル構築モジュール３４と同等のものである。
【００４６】
閉曲線検出モジュール１０２は、グラフモデル構築モジュール１０１、図形判断モジュール１０３と接続されており、グラフモデル構築モジュール１０１によって生成されたグラフモデルを解析することによって、端点を有しない閉図形（閉曲線、複数の線分で閉じた図形を形成しているもの）を検出する。ここでの閉図形の検出は、頂点情報テーブル８０を用いて、各点が閉曲線を構成するか否かについて、可能性のあるもの全てを探索して検出する。つまり、グラフの全探索によって、開始点から始めてその開始点に戻ってくる経路を求めることになる。
【００４７】
図形判断モジュール１０３は、閉曲線検出モジュール１０２、重複図形除去モジュール１０４と接続されており、閉図形の形状を判断する。つまり、図形判断モジュール１０３は、閉曲線検出モジュール１０２によって検出された閉図形に対して、多角形近似を行った後に、閉図形の形状を認識する。なお、多角形近似の処理は、必ずしも行わなくてもよい。図形判断モジュール１０３の処理については、図１１に示すフローチャートのステップＳ１１０６〜ステップＳ１１１８までの処理で説明する。
【００４８】
重複図形除去モジュール１０４は、図形判断モジュール１０３と接続されており、図形判断モジュール１０３が抽出した閉図形のうち重複している図形を削除する。なお、重複図形除去モジュール１０４による処理は、必ずしも行わなくてもよい。
【００４９】
重複図形除去モジュール１０４の処理について、図１２を用いて説明する。
図１２（Ａ）は、細線化処理が施された線図形１２０１である。図１２（Ｂ）は、図形判断モジュール１０３によって分離された線図形（円）１２０２、線図形（三角形（小））１２０３、線図形（三角形（大））１２０４である。図１２（Ａ）に示す線図形１２０１は、円と三角形が接触したものであるにもかかわらず、可能性のある閉図形をすべて抽出しているので、このように線図形（三角形（小））１２０３も抽出することになる。
【００５０】
重複図形除去モジュール１０４による処理の例は以下の通りである。
（１）画素数の多い順に閉図形をソートする。例えば、図１２（Ｂ）の場合、線図形（三角形（大））１２０４、線図形（円）１２０２、線図形（三角形（小））１２０３となる。
（２）順番に他図形と重複している画素数を調べ、重複した部分の割合が大きければ、その閉図形を削除する。割合が大であるか否かの判断は、閾値（予め定めたもの、その他の閉図形の重複率の平均等）との比較等による。例えば、図１２（Ｃ）に示すように、線図形（三角形（小））１２０３は三角形の２辺の部分が線図形（三角形（大））１２０４と重複しているので、重複している部分（図１２（Ｃ）の太線部分）が大きい。このとき、重複している図形同士の片方を削除するが、ソート順の低い方（全画素数が少ない方）を選択する。したがって、線図形（三角形（小））１２０３を削除の対象とする。
【００５１】
図１１は、形状解析抽出モジュール１３が行う処理例を示すフローチャートである。
ステップＳ１１０２では、グラフモデル構築モジュール１０１が、前述のグラフモデル構築モジュール３４と同様にグラフモデルを生成する。
ステップＳ１１０４では、閉曲線検出モジュール１０２が、前述したように閉図形を検出する。
【００５２】
ステップＳ１１０６では、図形判断モジュール１０３が、曲線を複数の直線で表す処理を行う。例えば、角点を検出してその間を直線で結ぶ方法などを使う。
ステップＳ１１０８では、図形判断モジュール１０３が、閉図形の線分の数が３であるか否かを判断する。３であれば、ステップＳ１１１８へ進み、それ以外であればステップＳ１１１０へ進む。
ステップＳ１１１０では、図形判断モジュール１０３が、閉図形の線分の数が４であり、かつ全ての角度が９０度に近いものであれば、ステップＳ１１１８へ進み、それ以外であればステップＳ１１１２へ進む。
【００５３】
ステップＳ１１１２では、図形判断モジュール１０３が、ジャギー（線図形のギザギザのこと）を除去する。
ステップＳ１１１４では、図形判断モジュール１０３が、ジャギーが除去された図形に対し多角形近似の処理を行う。ステップＳ１１０６と同様の処理を行ってもよいし、閾値を変更して処理を行ってもよい。
また、多角形近似の処理として２分割法による処理を行ってもよい。２分割法による処理の例は以下の通りである（「ディジタル画像処理」ＣＧ−ＡＲＴＳ協会出版、奥富 正敏著を参照）。
（１）線分列の始点と終点をつないだ線分に対して、各画素から距離を計算する。
（２）最大距離がある閾値（予め定めたもの、距離の平均等）以下である場合、その線分を採用する。そうでない場合は、その画素で画素列を分割し、分割された画素列で前記（１）の処理を再帰的に繰り返す。
（３）画素列の分割がない場合は、処理を終了する。
【００５４】
ステップＳ１１１６では、図形判断モジュール１０３が、閉図形の線分の数が６以上であり、かつ角（例えば、１００度以下の角）の数が２以下である場合はステップＳ１１１８へ進み、それ以外の場合は終了する（ステップＳ１１２２）。
ステップＳ１１１８では、図形判断モジュール１０３が、ステップＳ１１０８から進んできた場合はその閉図形は三角形であると判断し、ステップＳ１１１０から進んできた場合はその閉図形は長方形であると判断し、ステップＳ１１１６から進んできた場合はその閉図形は円であると判断する。そして、その閉図形を抽出する。
ステップＳ１１２０では、重複図形除去モジュール１０４が、前述したように重複している閉図形を削除する。
なお、このフローチャートでは、三角形、長方形、円の判断を行っているが、その他の図形の特徴を用いて判断するようにしてもよい。
【００５５】
図１３は、入力画像に含まれる線図形の形状又は数が既知の場合の処理例を示すフローチャートである。つまり、主に後処理モジュール１４の処理について説明する。後処理モジュール１４は、ステップＳ１３０８〜ステップＳ１３２０の処理を行う。
ステップＳ１３０２では、前処理モジュール１１が、前述したように前処理（ノイズ除去処理、細線化処理）を行う。
ステップＳ１３０４では、線追跡抽出モジュール１２が、前述したように線追跡抽出処理（開図形の抽出処理）を行う。
ステップＳ１３０６では、形状解析抽出モジュール１３が、前述したように形状解析抽出処理（閉図形の抽出処理）を行う。
ステップＳ１３０８では、ステップＳ１３０４及びステップＳ１３０６で抽出した図形の数の合計と予め設定されている図形の数との比較を行う。異なっていればステップＳ１３１０へ進み、それ以外の場合はステップＳ１３２０へ進む。さらに、ステップＳ１３０４及びステップＳ１３０６で抽出した図形の形状と予め設定されている図形の形状との比較を行う。異なっていればステップＳ１３１０へ進み、それ以外の場合はステップＳ１３２０へ進む。
【００５６】
ステップＳ１３１０では、接触ノード候補があるか否かを判断する。ある場合はステップＳ１３１２へ進み、ない場合はステップＳ１３１８へ進む。接触ノードで処理を誤っている場合が多いので、このような判断を行う。なお、接触ノードか否かは、角度で判断する。つまり、角度が１８０度に近いものが２つ存在するか否かによって判断する。
ここで、接触ノードについて、図１４を用いて説明する。図に示すように２つの円が接触したような図形の場合、４つの線分に分かれ、組となる線分の抽出（図７に示すフローチャートのステップＳ７１０）の際に、図に示す交差パス１４０２が選択される。この２つの線分のなす角度が１８０度に近いからである。しかし、この図形は本来２つの円が接触しているので、接触パス１４０１になるように、組となる辺を抽出すべきである。
【００５７】
ステップＳ１３１２では、ステップＳ１３１０で対象となったノードにおいて、再解析を行い、接触が考えられる組（ペア）を探索する。ここで、探索する対象は１８０度に近い２番目の候補から行うようにする。ステップＳ１３１２の処理では、辺情報テーブル９０の選択した組となる辺欄９６を変更する。
ステップＳ１３１４では、ステップＳ１３０４、ステップＳ１３０６の処理（つまり、線追跡抽出モジュール１２、形状解析抽出モジュール１３の処理）を再度実行する。
ステップＳ１３１６では、ステップＳ１３０８の処理を行う。つまり、再実行の結果が正しかったか否かの判断を行う。未だ異なっている場合はステップＳ１３１８へ進み、一致する場合はステップＳ１３２０へ進む。
ステップＳ１３１８では、接触ノードがなかった場合、又は再度実行した場合にあっても、予め設定されている図形の数又は形状が異なった場合であるので、処理ができなかった旨のエラー報告を行う。
ステップＳ１３２０では、その他の後処理を行う。例えば、線分幅を回復すること、欠損部分を補間すること、本実施の形態による処理結果を他の装置で使用させるためのデータの加工等である。
【００５８】
図１５は、入力画像に含まれる線図形の数が既知の場合の処理例を示すフローチャートである。図１３に示したフローチャートでは、数及び形状を予め設定した値と比較していたが（ステップＳ１３０８，Ｓ１３１６）、図１５では、線図形の数だけを比較の対象としている場合である。つまり、ステップＳ１５０８，Ｓ１５１６はそれぞれステップＳ１３０８，Ｓ１３１６と異なり、線図形の数だけを比較の対象としている。その他の各ステップの処理は、図１３に示したフローチャートにおける各ステップと同様である。
【００５９】
図１６は、後処理モジュール１４による処理を行わなかった場合の処理例を示すフローチャートである。つまり、図１３に示したフローチャートにおけるステップＳ１３０８以降を行わない場合である。ステップＳ１６０２〜ステップＳ１６０６の処理は、ステップＳ１３０２〜ステップＳ１３０６の処理と同様である。
【００６０】
図１７を参照して、本実施の形態のハードウェア構成例について説明する。図１７に示す構成は、例えばパーソナルコンピュータ（ＰＣ）などによって構成されるものであり、スキャナ等のデータ読み取り部１７１７と、プリンタなどのデータ出力部１７１８を備えたハードウェア構成例を示している。
【００６１】
ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）１７０１は、前述の実施の形態において説明した各種のモジュール、すなわち、前処理モジュール１１、線追跡抽出モジュール１２、形状解析抽出モジュール１３、後処理モジュール１４等の各モジュールの実行シーケンスを記述したコンピュータ・プログラムにしたがった処理を実行する制御部である。
【００６２】
ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）１７０２は、ＣＰＵ１７０１が使用するプログラムや演算パラメータ等を格納する。ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）１７０３は、ＣＰＵ１７０１の実行において使用するプログラムや、その実行において適宜変化するパラメータ等を格納する。これらはＣＰＵバスなどから構成されるホストバス１７０４により相互に接続されている。
【００６３】
ホストバス１７０４は、ブリッジ１７０５を介して、ＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ Ｃｏｍｐｏｎｅｎｔ Ｉｎｔｅｒｃｏｎｎｅｃｔ／Ｉｎｔｅｒｆａｃｅ）バスなどの外部バス１７０６に接続されている。
【００６４】
キーボード１７０８、マウス等のポインティングデバイス１７０９は、操作者により操作される入力デバイスである。ディスプレイ１７１０は、液晶表示装置又はＣＲＴ（Ｃａｔｈｏｄｅ Ｒａｙ Ｔｕｂｅ）などから成り、各種情報をテキストやイメージ情報として表示する。
【００６５】
ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）１７１１は、ハードディスクを内蔵し、ハードディスクを駆動し、ＣＰＵ１７０１によって実行するプログラムや情報を記録又は再生させる。ハードディスクは、受け付けられた画像、頂点情報テーブル８０、辺情報テーブル９０などが格納される。さらに、その他の各種のデータ処理プログラム等、各種コンピュータ・プログラムが格納される。
【００６６】
ドライブ１７１２は、装着されている磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリ等のリムーバブル記録媒体１７１３に記録されているデータ又はプログラムを読み出して、そのデータ又はプログラムを、インタフェース１７０７、外部バス１７０６、ブリッジ１７０５、及びホストバス１７０４を介して接続されているＲＡＭ１７０３に供給する。リムーバブル記録媒体１７１３も、ハードディスクと同様のデータ記録領域として利用可能である。
【００６７】
接続ポート１７１４は、外部接続機器１７１５を接続するポートであり、ＵＳＢ、ＩＥＥＥ１３９４等の接続部を持つ。接続ポート１７１４は、インタフェース１７０７、及び外部バス１７０６、ブリッジ１７０５、ホストバス１７０４等を介してＣＰＵ１７０１等に接続されている。通信部１７１６は、ネットワークに接続され、外部とのデータ通信処理を実行する。データ読み取り部１７１７は、例えばスキャナであり、ドキュメントの読み取り処理を実行する。データ出力部１７１８は、例えばプリンタであり、ドキュメントデータの出力処理を実行する。
【００６８】
なお、図１７に示すハードウェア構成は、１つの構成例を示すものであり、本実施の形態は、図１７に示す構成に限らず、本実施の形態において説明したモジュールを実行可能な構成であればよい。例えば、一部のモジュールを専用のハードウェア（例えば特定用途向け集積回路（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ：ＡＳＩＣ）等）で構成してもよく、一部のモジュールは外部のシステム内にあり通信回線で接続しているような形態でもよく、さらに図１７に示すシステムが複数互いに通信回線によって接続されていて互いに協調動作するようにしてもよい。また、複写機、ファックス、スキャナ、プリンタ、複合機（スキャナ、プリンタ、複写機、ファックス等のいずれか２つ以上の機能を有している画像処理装置）などに組み込まれていてもよい。
【００６９】
前記実施の形態において、図８、図９で示したデータ構造は、これらのデータ構造に限られず、他のデータ構造であってもよい。例えば、テーブル構造はリンク構造等であってもよい。また、データ項目は、これらに図示したものに限られず、他のデータ項目（例えば、線分長）を有していてもよい。
【００７０】
なお、説明したプログラムについては、記録媒体に格納して提供してもよく、また、そのプログラムを通信手段によって提供してもよい。その場合、例えば、前記説明したプログラムについて、「プログラムを記録したコンピュータ読み取り可能な記録媒体」の発明として捉えてもよい。
「プログラムを記録したコンピュータ読み取り可能な記録媒体」とは、プログラムのインストール、実行、プログラムの流通などのために用いられる、プログラムが記録されたコンピュータで読み取り可能な記録媒体をいう。
なお、記録媒体としては、例えば、デジタル・バーサタイル・ディスク（ＤＶＤ）であって、ＤＶＤフォーラムで策定された規格である「ＤＶＤ−Ｒ、ＤＶＤ−ＲＷ、ＤＶＤ−ＲＡＭ等」、ＤＶＤ＋ＲＷで策定された規格である「ＤＶＤ＋Ｒ、ＤＶＤ＋ＲＷ等」、コンパクトディスク（ＣＤ）であって、読出し専用メモリ（ＣＤ−ＲＯＭ）、ＣＤレコーダブル（ＣＤ−Ｒ）、ＣＤリライタブル（ＣＤ−ＲＷ）等、光磁気ディスク（ＭＯ）、フレキシブルディスク（ＦＤ）、磁気テープ、ハードディスク、読出し専用メモリ（ＲＯＭ）、電気的消去及び書換可能な読出し専用メモリ（ＥＥＰＲＯＭ）、フラッシュ・メモリ、ランダム・アクセス・メモリ（ＲＡＭ）等が含まれる。
そして、前記のプログラム又はその一部は、前記記録媒体に記録して保存や流通等させてもよい。また、通信によって、例えば、ローカル・エリア・ネットワーク（ＬＡＮ）、メトロポリタン・エリア・ネットワーク（ＭＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、インターネット、イントラネット、エクストラネット等に用いられる有線ネットワーク、あるいは無線通信ネットワーク、さらにこれらの組合せ等の伝送媒体を用いて伝送させてもよく、また、搬送波に乗せて搬送させてもよい。
さらに、前記のプログラムは、他のプログラムの一部分であってもよく、あるいは別個のプログラムと共に記録媒体に記録されていてもよい。また、複数の記録媒体に分割して
記録されていてもよい。また、圧縮や暗号化など、復元可能であればどのような態様で記録されていてもよい。
【図面の簡単な説明】
【００７１】
【図１】本実施の形態の構成例についての概念的なモジュール構成図である。
【図２】本実施の形態を含む全体の処理を示す説明図である。
【図３】線追跡抽出モジュールの構成例についての概念的なモジュール構成図である。
【図４】線追跡抽出モジュールが行う処理例を示すフローチャートである。
【図５】偽線分抽出モジュールが行う処理例を示す説明図である。
【図６】グラフモデル構築モジュールとノード解析モジュールが行う処理例を示す説明図である。
【図７】グラフモデル構築モジュールとノード解析モジュールが行う処理例を示すフローチャートである。
【図８】頂点情報テーブルのデータ構造を示す説明図である。
【図９】辺情報テーブルのデータ構造を示す説明図である。
【図１０】形状解析抽出モジュールの構成例についての概念的なモジュール構成図である。
【図１１】形状解析抽出モジュールが行う処理例を示すフローチャートである。
【図１２】重複図形除去モジュールが行う処理例を示す説明図である。
【図１３】入力画像に含まれる線図形の形状又は数が既知の場合の処理例を示すフローチャートである。
【図１４】線図形の接触の例を示す説明図である。
【図１５】入力画像に含まれる線図形の数が既知の場合の処理例を示すフローチャートである。
【図１６】後処理モジュールによる処理を行わなかった場合の処理例を示すフローチャートである。
【図１７】本実施の形態を実現するコンピュータのハードウェア構成例を示すブロック図である。
【符号の説明】
【００７２】
１１…前処理モジュール
１２…線追跡抽出モジュール
１３…形状解析抽出モジュール
１４…後処理モジュール
２１…受付画像
２２…追記抽出モジュール
２３…追記画像
２４…一筆線分図形分離モジュール
２５…一筆線分画像
２６…一筆線分画像
２７…一筆線分画像
３１…前処理モジュール
３２…特徴点・線分抽出モジュール
３３…偽線分抽出モジュール
３４…グラフモデル構築モジュール
３５…ノード解析モジュール
３６…開図形抽出モジュール
１０１…グラフモデル構築モジュール
１０２…閉曲線検出モジュール
１０３…図形判断モジュール
１０４…重複図形除去モジュール
【特許請求の範囲】
【請求項１】
線図形を含む画像内の点に関する特徴及び線分を抽出する抽出手段と、
前記抽出手段による結果に基づいて、グラフモデルを生成するグラフモデル生成手段と、
前記グラフモデル生成手段によって生成されたグラフモデルを解析することによって、端点を有する開図形を抽出する開図形抽出手段と、
前記グラフモデル生成手段によって生成されたグラフモデルを解析することによって、端点を有しない閉図形を抽出する閉図形抽出手段
を具備することを特徴とする画像処理装置。
【請求項２】
前記抽出手段によって抽出された特徴点及び線分に基づいて、前記線分のうち偽線分を識別する偽線分識別手段
を具備し、
前記グラフモデル生成手段は、前記抽出手段及び前記偽線分識別手段による結果に基づいて、グラフモデルを生成する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記閉図形抽出手段は、前記グラフモデルを解析することによって、閉図形を抽出し、多角形近似を行った後に、閉図形の形状を認識する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項４】
前記閉図形抽出手段は、抽出した閉図形のうち重複している図形を削除する
ことを特徴とする請求項１又は３に記載の画像処理装置。
【請求項５】
前記開図形抽出手段によって抽出された開図形及び前記閉図形抽出手段によって抽出された閉図形の合計が、前記画像内に含まれている図形の数と異なるか否かを判断する判断手段と、
前記判断手段によって異なると判断された場合は、前記画像内の線分の接触している箇所に応じて、前記グラフモデルを変更し、前記開図形抽出手段又は前記閉図形抽出手段による処理を行わせる再処理手段
をさらに具備することを特徴とする請求項１に記載の画像処理装置。
【請求項６】
前記開図形抽出手段によって抽出された開図形又は前記閉図形抽出手段によって抽出された閉図形の形状が、前記画像内に含まれている図形の形状と異なるか否かを判断する判断手段と、
前記判断手段によって異なると判断された場合は、前記画像内の線分の接触している箇所に応じて、前記グラフモデルを変更し、前記開図形抽出手段又は前記閉図形抽出手段による処理を行わせる再処理手段
をさらに具備することを特徴とする請求項１に記載の画像処理装置。
【請求項７】
コンピュータを、
線図形を含む画像内の点に関する特徴及び線分を抽出する抽出手段と、
前記抽出手段による結果に基づいて、グラフモデルを生成するグラフモデル生成手段と、
前記グラフモデル生成手段によって生成されたグラフモデルを解析することによって、端点を有する開図形を抽出する開図形抽出手段と、
前記グラフモデル生成手段によって生成されたグラフモデルを解析することによって、端点を有しない閉図形を抽出する閉図形抽出手段
として機能させることを特徴とする画像処理プログラム。
【請求項１】
線図形を含む画像内の点に関する特徴及び線分を抽出する抽出手段と、
前記抽出手段による結果に基づいて、グラフモデルを生成するグラフモデル生成手段と、
前記グラフモデル生成手段によって生成されたグラフモデルを解析することによって、端点を有する開図形を抽出する開図形抽出手段と、
前記グラフモデル生成手段によって生成されたグラフモデルを解析することによって、端点を有しない閉図形を抽出する閉図形抽出手段
を具備することを特徴とする画像処理装置。
【請求項２】
前記抽出手段によって抽出された特徴点及び線分に基づいて、前記線分のうち偽線分を識別する偽線分識別手段
を具備し、
前記グラフモデル生成手段は、前記抽出手段及び前記偽線分識別手段による結果に基づいて、グラフモデルを生成する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記閉図形抽出手段は、前記グラフモデルを解析することによって、閉図形を抽出し、多角形近似を行った後に、閉図形の形状を認識する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項４】
前記閉図形抽出手段は、抽出した閉図形のうち重複している図形を削除する
ことを特徴とする請求項１又は３に記載の画像処理装置。
【請求項５】
前記開図形抽出手段によって抽出された開図形及び前記閉図形抽出手段によって抽出された閉図形の合計が、前記画像内に含まれている図形の数と異なるか否かを判断する判断手段と、
前記判断手段によって異なると判断された場合は、前記画像内の線分の接触している箇所に応じて、前記グラフモデルを変更し、前記開図形抽出手段又は前記閉図形抽出手段による処理を行わせる再処理手段
をさらに具備することを特徴とする請求項１に記載の画像処理装置。
【請求項６】
前記開図形抽出手段によって抽出された開図形又は前記閉図形抽出手段によって抽出された閉図形の形状が、前記画像内に含まれている図形の形状と異なるか否かを判断する判断手段と、
前記判断手段によって異なると判断された場合は、前記画像内の線分の接触している箇所に応じて、前記グラフモデルを変更し、前記開図形抽出手段又は前記閉図形抽出手段による処理を行わせる再処理手段
をさらに具備することを特徴とする請求項１に記載の画像処理装置。
【請求項７】
コンピュータを、
線図形を含む画像内の点に関する特徴及び線分を抽出する抽出手段と、
前記抽出手段による結果に基づいて、グラフモデルを生成するグラフモデル生成手段と、
前記グラフモデル生成手段によって生成されたグラフモデルを解析することによって、端点を有する開図形を抽出する開図形抽出手段と、
前記グラフモデル生成手段によって生成されたグラフモデルを解析することによって、端点を有しない閉図形を抽出する閉図形抽出手段
として機能させることを特徴とする画像処理プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２００９−６９９５３（Ｐ２００９−６９９５３Ａ）
【公開日】平成２１年４月２日（２００９．４．２）
【国際特許分類】
【出願番号】特願２００７−２３５２６０（Ｐ２００７−２３５２６０）
【出願日】平成１９年９月１１日（２００７．９．１１）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
【公開日】平成２１年４月２日（２００９．４．２）
【国際特許分類】
【出願日】平成１９年９月１１日（２００７．９．１１）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
[ Back to top ]