(57)【要約】【課題】画像を構成する画素を追跡したときに隙間や角点のずれの発生を防止することができる画像処理装置、方法およびプログラムを提供する。【解決手段】画像処理装置には、入力画像に対応する画素列に対してつながりを考慮した点列の追跡を行う点列追跡部１２０と、点列追跡部１２０によって追跡された画素列に含まれる接合点を抽出する接合点抽出部１３０と、接合点抽出部１３０によって抽出された接合点を境界として画素列を複数のセグメントに分割するセグメント分割部１４０と、セグメント分割部１４０によって分割されたセグメント毎に関数化処理を行う関数化処理部１５０とが備わっている。【選択図】        図１
2005004509.tif 000002
【特許請求の範囲】
【請求項１】
画像の入力を行う画像入力手段と、
前記画像入力手段によって入力された画像に対応する画素列に対して、つながりを考慮した追跡を行う点列追跡手段と、
前記点列追跡手段によって追跡された前記画素列に対して関数化処理を行う関数化処理手段と、
を備えることを特徴とする画像処理装置。
【請求項２】
請求項１において、
前記点列追跡手段によって追跡された前記画素列に含まれる接合点を抽出する接合点抽出手段と、
前記接合点抽出手段によって抽出された接合点を境界として、前記画素列を複数のセグメントに分割するセグメント分割手段と、
をさらに備え、前記関数化処理手段は、前記セグメント分割手段によって分割されたセグメント毎に、前記画素列に対して関数化処理を行うことを特徴とする画像処理装置。
【請求項３】
請求項１または２において、
前記関数化処理手段によって関数化処理された結果を用いて、指定倍率の画像を生成して出力する出力画像生成手段をさらに備えることを特徴とする画像処理装置。
【請求項４】
請求項１〜３のいずれかにおいて、
前記点列追跡手段は、最初に前記画素列の端点を探し、この端点を追跡の開始点として前記画素列の追跡を行うことを特徴とする画像処理装置。
【請求項５】
請求項４において、
前記点列追跡手段は、追跡中の着目画素に隣接する未探索の画素がない場合であっても、さらにその隣接画素に隣接する未探索の画素が存在する場合には、これらの隣接画素と未探索の画素を用いて前記画素列の追跡を行うことを特徴とする画像処理装置。
【請求項６】
請求項４または５において、
前記点列追跡手段は、隣接する複数の画素の一つを開始点として前記画素列の点列の追跡を行ったときに、この開始点と追跡されたそれ以後の画素列とが不自然なつながりを有するときに、この開始点の画素を前記複数の画素の他の画素に差し替えることにより前記画素列に自然なつながりを持たせることを特徴とする画像処理装置。
【請求項７】
請求項４〜６のいずれかにおいて、
前記点列追跡手段は、追跡中の着目画素に隣接する未探索の複数の画素が存在するときに、それぞれの画素から所定の距離まで追跡を継続した場合に到達する複数の画素を探索し、前記着目画素の前後で追跡の向きの変化が最小となる画素を新たな探索点として選択することを特徴とする画像処理装置。
【請求項８】
画像の入力を行う第１のステップと、
入力された画像に対応する画素列に対して、つながりを考慮した追跡を行う第２のステップと、
追跡された前記画素列に対して関数化処理を行う第３のステップと、
を有することを特徴とする画像処理方法。
【請求項９】
請求項８において、
前記第２のステップにおいて追跡された前記画素列に含まれる接合点を抽出する第４のステップと、
抽出された前記接合点を境界として、前記画素列を複数のセグメントに分割する第５のステップと、
をさらに有し、前記第３のステップにおける関数化処理は、前記第５のステップにおいて分割されたセグメント毎に行われることを特徴とする画像処理方法。
【請求項１０】
請求項８または９において、
前記第３のステップにおいて関数化処理された結果を用いて、指定倍率の画像を生成して出力する第６のステップをさらに有することを特徴とする画像処理方法。
【請求項１１】
請求項８〜１０のいずれかにおいて、
前記第２のステップにおいて、最初に前記画素列の端点を探し、この端点を追跡の開始点として前記画素列の追跡を行うことを特徴とする画像処理方法。
【請求項１２】
請求項１１において、
前記第２のステップにおいて、追跡中の着目画素に隣接する未探索の画素がない場合であっても、さらにその隣接画素に隣接する未探索の画素が存在する場合には、これらの隣接画素と未探索の画素を用いて前記画素列の追跡を行うことを特徴とする画像処理方法。
【請求項１３】
請求項１１または１２において、
前記第２のステップにおいて、隣接する複数の画素の一つを開始点として前記画素列の点列の追跡を行ったときに、この開始点と追跡されたそれ以後の画素列とが不自然なつながりを有するときに、この開始点の画素を前記複数の画素の他の画素に差し替えることにより前記画素列に自然なつながりを持たせることを特徴とする画像処理方法。
【請求項１４】
請求項１１〜１３のいずれかにおいて、
前記第２のステップにおいて、追跡中の着目画素に隣接する未探索の複数の画素が存在するときに、それぞれの画素から所定の距離まで追跡を継続した場合に到達する複数の画素を探索し、前記着目画素の前後で追跡の向きの変化が最小となる画素を新たな探索点として選択することを特徴とする画像処理方法。
【請求項１５】
コンピュータを、
画像の入力を行う画像入力手段と、
前記画像入力手段によって入力された画像に対応する画素列に対して、つながりを考慮した追跡を行う点列追跡手段と、
前記点列追跡手段によって追跡された前記画素列に対して関数化処理を行う関数化処理手段と、
して機能させるための画像処理プログラム。
【請求項１６】
請求項１５において、
コンピュータを、さらに、
前記点列追跡手段によって追跡された前記画素列に含まれる接合点を抽出する接合点抽出手段と、
前記接合点抽出手段によって抽出された前記接合点を境界として、前記画素列を複数のセグメントに分割するセグメント分割手段と、
前記セグメント分割手段によって分割されたセグメント毎に、前記画素列に対して関数化処理を行う前記関数化処理手段と、
して機能させるための画像処理プログラム。
【請求項１７】
請求項１５または１６において、
コンピュータを、さらに、前記関数化処理手段によって関数化処理された結果を用いて、指定倍率の画像を生成して出力する出力画像生成手段として機能させるための画像処理プログラム。
【請求項１８】
請求項１５〜１７のいずれかにおいて、
前記点列追跡手段は、最初に前記画素列の端点を探し、この端点を追跡の開始点として前記画素列の追跡を行うことを特徴とする画像処理プログラム。
【請求項１９】
請求項１８において、
前記点列追跡手段は、追跡中の着目画素に隣接する未探索の画素がない場合であっても、さらにその隣接画素に隣接する未探索の画素が存在する場合には、これらの隣接画素と未探索の画素を用いて前記画素列の追跡を行うことを特徴とする画像処理プログラム。
【請求項２０】
請求項１８または１９において、
前記点列追跡手段は、隣接する複数の画素の一つを開始点として前記画素列の点列の追跡を行ったときに、この開始点と追跡されたそれ以後の画素列とが不自然なつながりを有するときに、この開始点の画素を前記複数の画素の他の画素に差し替えることにより前記画素列に自然なつながりを持たせることを特徴とする画像処理プログラム。
【請求項２１】
請求項１８〜２０のいずれかにおいて、
前記点列追跡手段は、追跡中の着目画素に隣接する未探索の複数の画素が存在するときに、それぞれの画素から所定の距離まで追跡を継続した場合に到達する複数の画素を探索し、前記着目画素の前後で追跡の向きの変化が最小となる画素を新たな探索点として選択することを特徴とする画像処理プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、入力画像を構成する画素列を追跡した後に関数化処理する画像処理装置、方法およびプログラムに関する。
【０００２】
【従来の技術】
パーソナルコンピュータとそれを取り巻くさまざまなデバイスの普及により、デジタル画像の解像度変換の必要性が高まっている。従来、一般的なＪＰＥＧ、ＧＩＦ、ＰＮＧに代表されるピクセル符号化方式では、拡大時にジャギーノイズを生じるなど、画質が劣化してしまうため、関数符号化方式が提案された。画像の輪郭を追跡し、それを関数近似することによって、ピクセル符号化画像を関数符号化画像へ自動的に変換する手法の研究も行われている（例えば、特許文献１参照。）。
【０００３】
例えば、文字、イラスト、ロゴマークといった画像をフルーエンシ関数系により高精度に関数化することができる。フルーエンシ情報理論では、信号の滑らかさの基準を示す連続微分可能性に基づいたパラメータｍを用いて信号空間を類別している。ｍ次のフルーエンシ関数は、（ｍ−２）回のみ連続微分可能な（ｍ−１）次の区分的多項式から構成されている。画像関数近似では、輪郭線はその形状によった種類の関数を用いて近似される。ｍ＝２、ｍ＝３、ｍ＝∞のフルーエンシ関数はそれぞれ、直線、自由曲線、円弧を表現するのに用いられる。
【０００４】
【特許文献１】
特開２００１−４７７９６号公報（第４−１２頁、図１−１１）
【０００５】
【発明が解決しようとする課題】
しかし、これらの輪郭線を関数近似する手法には、細い線分が線幅一定で再現されないという問題がある。この間題を解決する手法のひとつとして、地図や回路図など細い線分を含む図面画像では、その芯線を関数化する方法が考えられる。しかし、従来手法における点列追跡法は厚みのある物体の輪郭を対象としているため、線幅１画素の線分を含む画像の関数化で十分な精度を得ることは難しかった。
【０００６】
線幅１画素の点列の追跡においては、厚みのある物体の輪郭追跡では出現し得なかったパターンが出現するため、関数近似後の復号拡大画像において、線分の途切れを生じてしまうのである。
輪郭線の追跡方法は大きく２つに分類でき、１．画素の辺を追跡する方法、２．画素の中心を追跡する方法があげられる。しかし、いずれの方法でも、関数近似後の拡大画像の精度に重大な問題が生じる。
【０００７】
図１７〜図２３は、線幅１画素で構成された二値画像の具体例を示す図である。図１７に示す画像を入力として、１．画素の辺を追跡する方法、２．画素の中心を追跡する方法を用いて、その結果得られた点列を関数化した。その関数化画像の一部分であるａ、ｂ、ｃのそれぞれを５倍に拡大したものが図１８〜図２３である。
【０００８】
まず、１．画素の辺を追跡する方法について考察する。この方法では、画素の両端が別の辺として２回追跡されることになる。このため、それが１つの線分であっても、線分の両端が違う関数で近似されてしまうことがあるため、図１８〜図２０のように、その線幅は一定とはならない。また、十字路においても４つの角点の位置関係にずれが生じてしまう問題がある。
【０００９】
次に、２．画素の中心を追跡する方法について考察する。まず、点列は反時計回りのチェーンコード法に従って探索されるため、図２１や図２２のように、分岐点や、交差点において点列が人間の知覚に違和感を持つ方向に追跡されてしまう。このため、等倍復号時には隙間は生じないものの、拡大すると隙間が生じるとともに、線分の連続の不自然さが顕在化される。また、図２４のような入力画像に対して、図２５のように追跡されるため、画像の拡大時に中央の線分の両端に隙間が生じてしまう問題もあった。
【００１０】
本発明は、このような点に鑑みて創作されたものであり、その目的は、画像を構成する画素を追跡したときに隙間や角点のずれの発生を防止することができる画像処理装置、方法およびプログラムを提供することにある。
【００１１】
【課題を解決するための手段】
上述した課題を解決するために、本発明の画像処理装置は、画像の入力を行う画像入力手段と、画像入力手段によって入力された画像に対応する画素列に対して、つながりを考慮した追跡を行う点列追跡手段と、点列追跡手段によって追跡された画素列に対して関数化処理を行う関数化処理手段とを備えている。また、本発明の画像処理方法は、画像の入力を行う第１のステップと、入力された画像に対応する画素列に対して、つながりを考慮した追跡を行う第２のステップと、追跡された画素列に対して関数化処理を行う第３のステップとを有している。また、本発明の画像処理プログラムは、コンピュータを、画像の入力を行う画像入力手段と、画像入力手段によって入力された画像に対応する画素列に対して、つながりを考慮した追跡を行う点列追跡手段と、点列追跡手段によって追跡された画素列に対して関数化処理を行う関数化処理手段として機能させる。このように、つながりを考慮した画素列の追跡を行うことにより、分岐点や交差点における隙間や角点のずれの発生を防止することができる。
【００１２】
また、上述した点列追跡手段によって追跡された画素列に含まれる接合点を抽出する接合点抽出手段と、接合点抽出手段によって抽出された接合点を境界として、画素列を複数のセグメントに分割するセグメント分割手段とをさらに備え、関数化処理手段は、セグメント分割手段によって分割されたセグメント毎に、画素列に対して関数化処理を行うことが望ましい。これにより、セグメント毎に比較的簡単な関数を用いて関数化処理することが可能になる。
【００１３】
また、上述した関数化処理手段によって関数化処理された結果を用いて、指定倍率の画像を生成して出力する出力画像生成手段をさらに備えることが望ましい。これにより、原画像を拡大した際に生じる隙間や角点のずれの発生を有効に防止することが可能になる。
【００１４】
また、上述した点列追跡手段は、最初に画素列の端点を探し、この端点を追跡の開始点として画素列の追跡を行うことが望ましい。これにより、本来は連続する画素列の途中で途切れて隙間が生じることを防止することが可能になる。
また、上述した点列追跡手段は、追跡中の着目画素に隣接する未探索の画素がない場合であっても、さらにその隣接画素に隣接する未探索の画素が存在する場合には、これらの隣接画素と未探索の画素を用いて画素列の追跡を行うことが望ましい。これにより、分岐点や交差点において探索済みの画素を重複して追跡することができるため、交差点等における隙間の発生を確実に防止することが可能になる。
【００１５】
また、上述した点列追跡手段は、隣接する複数の画素の一つを開始点として画素列の点列の追跡を行ったときに、この開始点と追跡されたそれ以後の画素列とが不自然なつながりを有するときに、この開始点の画素を複数の画素の他の画素に差し替えることにより画素列に自然なつながりを持たせることが望ましい。これにより、一の画素列の端部が他の画素列と接続される場合の不自然なつながりを防止することができる。
【００１６】
また、上述した点列追跡手段は、追跡中の着目画素に隣接する未探索の複数の画素が存在するときに、それぞれの画素から所定の距離まで追跡を継続した場合に到達する複数の画素を探索し、着目画素の前後で追跡の向きの変化が最小となる画素を新たな探索点として選択することが望ましい。これにより、複数の画素列が交差している場合であっても、交差するそれぞれの画素列について追跡を行うことが可能になり、画素列の前後の関係が自然となる追跡を行うことができる。
【００１７】
【発明の実施の形態】
以下、本発明を適用した一実施形態の画像処理装置について、図面に基づいて詳細に説明する。
図１は、一実施形態の画像処理装置の構成を示す図である。図１に示すように、本実施形態の画像処理装置は、画像処理演算部１００、スキャナ２００、キーボード２１０、マウス２１２、ディスプレイ装置２２０、プリンタ２３０を含んで構成されている。
【００１８】
スキャナ２００は、紙に印刷された回路図面等の被写体を光学的に読み取って、白黒の二値画像を生成する。この生成された二値画像は、画像処理演算部１００に入力される。キーボード２１０およびマウス２１２は、画像処理演算部１００に対して利用者が各種の操作指示を行うために用いられる。例えば、スキャナ２００を用いた画像取込の操作指示や、その後の関数化処理の演算開始指示、関数化処理された画像データから原画像への復元指示、復元の際の拡大倍率等がキーボード２１０やマウス２１２を用いて行われる。
【００１９】
ディスプレイ装置２２０は、各種の操作画面や、取り込んだ画像および関数化処理された画像データを用いて原画像を復元した結果等を表示する。プリンタ２３０は、復元された原画像を所定サイズの紙に印刷する。
画像処理演算部１００は、入力画像に対して関数化処理を行うとともに、この関数化されたデータに基づいて画像を生成する処理を行う。このために、画像処理演算部１００は、画像格納部１１０、点列追跡部１２０、接合点抽出部１３０、セグメント分割部１４０、関数化処理部１５０、出力画像生成部１６０を備えている。この画像処理演算部１００は、ＣＰＵ、ＲＯＭ、ＲＡＭおよびハードディスク装置を備えたコンピュータによって実現することが可能であり、ＲＯＭ、ＲＡＭあるいはハードディスク装置に格納された画像処理プログラムをＣＰＵで実行することにより、点列追跡部１２０、接合点抽出部１３０、セグメント分割部１４０、関数化処理部１５０、出力画像生成部１６０の各機能が実現される。また、画像格納部１１０は、主にハードディスク装置によって実現される。
【００２０】
画像格納部１１０は、スキャナ２００を用いて読み取られた原画像に対応する画像データや、関数化処理等を行うために必要な中間データ、関数化処理によって得られた関数化データ等を格納する。
点列追跡部１２０は、所定のルールに従って入力画像を構成する画素列に対して、つながりを考慮した追跡処理を行う。本実施形態では、線幅が１画素の入力画像を処理の対象としており、線幅が複数画素の画像が入力された場合には、前処理を行って線幅を１画素にする処理が行われる。
【００２１】
接合点抽出部１３０は、点列追跡部１２０による追跡によって得られた画素列の中から接合点を抽出する。ここで、接合点とは、その前後で画素列の傾向が変化する画素である。例えば直線と自由曲線との接続点となる画素や、自由曲線と円弧との接続点となる画素などが接合点となる。
【００２２】
セグメント分割部１４０は、接合点抽出部１３０によって抽出された接合点を用いて、点列追跡部１２０によって追跡された点列（画素列）を複数のセグメントに分割する。関数化処理部１５０は、セグメント分割部１４０によって複数に分割された各セグメント毎に関数化処理を行う。例えば、各セグメントは、直線、自由曲線、円弧のいずれかの関数を用いて近似される。
【００２３】
出力画像生成部１６０は、関数化処理部１５０によって得られた関数化データを用いて原画像を生成する。この原画像生成では倍率を指定することができ、原画像を指定された倍率で拡大した画像が生成される。
上述したスキャナ２００が画像入力手段に、点列追跡部１２０が点列追跡手段に、接合点抽出部１３０が接合点抽出手段に、セグメント分割部１４０がセグメント分割手段に、関数化処理部１５０が関数化処理手段に、出力画像生成部１６０が出力画像生成手段にそれぞれ対応する。
【００２４】
本実施形態の画像処理装置はこのような構成を有しており、次にその動作を説明する。
図２は、本実施形態の画像処理装置の動作手順を示す流れ図である。画像格納部１１０は、スキャナ２００を用いて読み取られた画像が入力されると（ステップ１００）、この入力画像データを格納する。
【００２５】
次に、点列追跡部１２０は、入力画像の画素列に対して、つながりを考慮した追跡を行う（ステップ１０１）。この追跡処理の詳細については後述する。
次に、接合点抽出部１３０は、追跡された画素列を用いて、関数化処理を行う対象となる各セグメントの接続点としての接合点を抽出する（ステップ１０２）。セグメント分割部１４０は、抽出された接合点間の画素列を複数のセグメントに分割する（ステップ１０３）。関数化処理部１５０は、分割されたセグメント毎に、関数化処理（関数近似処理）を行う（ステップ１０４）。例えば、直線、自由曲線、円弧のいずれかの関数を用いて各セグメントが関数化処理される。出力画像生成部１６０は、倍率が指定されると（ステップ１０５）、関数化処理された結果を用いて、元の画像をこの指定された倍率で拡大して復元する処理を行う。このようにして復元された画像がディスプレイ装置２２０の画面に表示されたり、プリンタ２３０から記録紙に印刷される（ステップ１０６）。
【００２６】
次に、点列追跡部１２０によって行われる画素列（点列）の追跡処理の詳細について説明する。
点列追跡部１２０によって、つながりを考慮した点列追跡を行う際の要求仕様として、以下の４つを考えるものとする。
【００２７】
（１）復号画像の線幅が一定となること、
（２）十字路における４つの角点が正確に平行四辺形を形づくること、
（３）分岐点、交差点における点列の連続性が人間の知覚に自然であること、
（４）画素データ上での連続性を関数化処理後も保持すること。
【００２８】
一般に、地図や回路図といった図面画像は、ロゴマークやイラストなどの画像と比べて、細い線分を多く含んでいるといえる。このため、これらの地図や回路図等の画像を関数化処理の対象とする場合には、要求仕様として（１）と（２）を含めるか否かは、復号画像の精度を大きく左右する。
【００２９】
また、（３）の要求仕様は、関数化処理において近似関数の種類を決定する際に大きく影響する。分岐点、交差点を含む直線を、そこで途切れさせずに全体として１本の直線と判断するためには、関数化処理の前処理において１本の線分として点列追跡がなされている必要があるからである。
【００３０】
さらに、関数化処理された画像の拡大時に線分の分岐点、交差点で隙間を生じさせないためには、図２４に示した原画像に対しては、図３に示すような追跡が行われることが望ましい。また、図２３に示したように線分の途中で途切れてしまう問題も解決する必要がある。そこで、（４）の要求仕様が必要となる。
【００３１】
本実施形態では、上述した要求仕様（１）、（２）を満たすために、入力画像を構成する画素の中心を追跡する方法を採用する。
また、要求仕様（３）を満たすために、点列の分岐点、交差点における連続性を考慮する工夫を施す。点列が分岐する場合に、追跡中の現在点（着目画素）から考えられるいくつかの進行方向を候補として抽出し、その中からデジタル曲率を用いて進行方向を決定する。例えば、図４に示すように、矢印方向から画素Ｐ０  へ追跡を行ってきた場合に、Ｋ個前の画素Ｐ−Ｋと、予測されるＮ個のＫ個後の画素｛ＰＫｎ｝Ｎｎ＝１の中から最適な進行画素｛ＰＫｎ｝を決定する。
【００３２】
また、要求仕様（４）を満たすために、連続でない線分同士の連続性を考慮する。追跡済みの点列情報から再追跡可能な点を割り出し、ある線分の端点が別の線分の画素列に隣接するとき、そこに隙間が生じないようにする。画素列の分岐点、交差点においては、その点を重複して点列リストにあげることを許容することでこれを実現する。
【００３３】
次に、要求仕様（３）を満たすために行われる点列の分岐点、交差点における連続性を考慮した点列追跡法と、（４）を満たすために行われる線分同士の接続性を考慮した点列追跡法について詳述する。但し、前者の点列追跡法は、後者の点列追跡法の手法の一部を利用するため、（Ａ）線分同士の接続性を考慮した点列追跡法、（Ｂ）点列の分岐点、交差点における連続性を考慮した点列追跡法の順で説明を行うものとする。
【００３４】
（Ａ）線分同士の接続性を考慮した点列追跡法
点列追跡部１２０による点列追跡処理の対象となる入力画像Ｉは、線幅１画素で描かれたコンテンツで構成される二値画像とする。画像中の点ｘ＝（ｉ，ｊ）に対して、Ｉ（ｘ）は０または１の値を持つ。まず、入力画像Ｉと同じ大きさの二次元配列Ｆを用意する。初期設定として、画像中の全ての点ｘに対してＦ（ｘ）の値を１とする。以後、この二次元配列Ｆは、未探索点を表すフラグとして用いられる。また、画素ｘ０  の近傍の画素を、図５を用いて次式のように定義する。
【００３５】
ｎ［８］（ｘ０）＝｛ｘｃ；ｃ∈Ｓ｝、    Ｓ＝｛１，２，３，４，５，６，７，８｝  …（１）
ここで、ｃを方向コードと呼ぶ。
Ｉ、Ｆを用いて、画像中の点列を以下のように探索する。
▲１▼入力画像Ｉを図６に示すように最下位ラインから順に走査する。以後、この走査をモードＡの走査方法と呼ぶ。入力画像Ｉ中に端点がある場合は、その端点から点列の追跡を開始する。ここでいう端点とは、任意の画像ｘ０  においてＩ（ｘ０  ）＝１で、図５に示すｘ０  の周囲についてΣＩ（ｘｃ  ）＝１となる点のことである。端点がない場合には、走査モードＡで最初にＩ（ｘ０  ）＝１となる点を追跡の開始点とする。
【００３６】
探索点（着目画素）ｔ０  をｔ０  ＝ｘ０  とする。点列番号ａをａ＝０とする。点列リストＵａ  にｔ０  を追加する。方向コードリストＣａ  に０を追加する。
▲２▼ｔ０  に対して、８連結のチェーンコード法（図５に示す点ｘ１  →ｘ２  →ｘ３  →ｘ４  →ｘ５  →ｘ６  →ｘ７  →ｘ８  の順に探索していく方法）を用いて反時計回りに、
【００３７】
【数１】
2005004509.tif 000003
【００３８】
となるｔｃ  を探索していく。（ａ）は、現在の探索点ｔ０  の周囲にある未探索の点を見つけるための条件である。また、（ｂ）は、現在の探索点ｔ０  の周囲にある探索済みの点であっても、さらにその周囲に未探索の点が存在する場合には再度この探索済みの点を新たな探索点として設定するための条件である。（ａ）または（ｂ）の条件を満たす点を発見した場合は、以下の▲３▼に進む。また、ｎ［８］（ｘ０  ）が（ａ）、（ｂ）のいずれの条件も満たさない場合には▲４▼に進む。
【００３９】
▲３▼ｔｃ  を点列リストＵｃ  に追加して、その点を新たな探索点ｔ０  とする。また、この新たな探索点ｔ０  に対応する方向コードｃを方向コードリストＣａ  に追加する。その後、Ｆ（ｔ０  ）＝０として、▲２▼に戻る。
▲４▼点列の探索を終了する。画像中の全ての点ｘに対してＦ（ｘ）＝０であれば、入力画像中の全てのＩ（ｘ）＝１である画素の追跡が完了したので、点列追跡部１２０による処理が終了する。そうでないときには、ａ＝ａ＋１として新たな点列リストＵａ  と方向コードリストＣａ  を用意する。
【００４０】
画像を走査モードＡで走査して、
【００４１】
【数２】
2005004509.tif 000004
【００４２】
となる点があればその点ｘ０  を新たな追跡の開始点とする。また、この条件を満たす点がなければ、走査モードＡで最初にＩ（ｘ０  ）＝１となるｘ０  を新たな追跡の開始点とする。ｔ０  ＝ｘ０  とするとともに、点列リストＵａ  にｔ０  を、方向コードリストＣａ  に０を追加して▲２▼に戻る。
【００４３】
以上の▲１▼〜▲４▼の手順を繰り返すことにより、Ｉ（ｘ）＝１となる全ての画素の追跡が行われる。また、上記の▲１▼〜▲４▼の手順を繰り返すことにより、点列の分岐点、交差点は、複数回それぞれが別々の点列リスト中に格納される。これにより、関数化画像拡大時の線分の分岐点、交差点において生じるおそれのある隙間を防いでいる。但し、これではまだ十分ではなく、図７に示すような不自然な追跡を許してしまうことになる。そこで、本実施形態では、▲４▼にさらに以下に示す工夫が加えられている。
【００４４】
新たな探索を始めるときに、
【００４５】
【数３】
2005004509.tif 000005
【００４６】
となる点が隣接してＮ個存在する場合、それらの集合をＳ｛ｓｎ｝Ｎｎ＝１とする。その中の１点を開始点としたＭ点の点列の追跡が終わったとき、点列Ｕａ｛ｕｍ｝Ｍｍ＝１中のｕ２  、ｕ３  と自然なつながりをもつｓｎ  をｕ１  と差し替える。点列Ｕａ｛ｕｍ｝Ｍｍ＝１と対応する方向コードＣａ｛ｃｍ｝Ｍｍ＝１を用いて、ｕ２  から（ｃ３  ＋４）％８の方向にあるｓｎ  をｕ１  とする。但し、演算子％は、除算の余りを表す。ｕ２  から（ｃ３  ＋４）％８の方向にｓｎ  がない場合はｄを１、２、３と増加させながら、ｕ２  から（ｃ３  ＋４）％８±ｄの方向のあるｓｎ  をｕ１  とする。このようにすることで、図２４に示す入力画像に対して、図３に示すような追跡を行うことが可能になる。
【００４７】
（Ｂ）点列の分岐点、交差点における連続性を考慮した点列追跡法
次に、上述した手法に、分岐点、交差点における点列の連続性保持のための対応策を加える。具体的には、点列追跡の途中で分岐点、交差点に差し掛かったときに、その後の追跡方向を決定する方法について詳しく説明する。
【００４８】
図８は、交差点における追跡方向の決定方法の説明図である。図８に示す矢印の方向に探索が進み、現在の探索点ｔ０  が“＊”の位置にきたとき、すなわち、
【００４９】
【数４】
2005004509.tif 000006
【００５０】
であるときに、点列追跡部１２０は、以下のアルゴリズムを実行する。
▲１▼“＊”を中心に距離Ｋまで、“＊”からの距離Ｌ（ｘ）をｔ０  の周辺のＩ（ｘ）＝１である点ｘについて、ラベルづけする。ここでの距離とは、８近傍距離である（図５に示した点ｘ０  からその周辺の各点ｘ１  〜ｘ８  のそれぞれまでの距離を１とする）。
【００５１】
▲２▼Ｐ０  ＝ｔ０  とする。ｔ０  がｕＭ  として点列リストＵに格納されているとき、Ｌ（ｘ）＝１かつｘｕＭ−１  である点をＰ１  として、そのときの“＊”からＰ１  への方向コードをＤとする。
▲３▼Ｐ１  からＤまたは、Ｄ±１の方向にあり、Ｌ（ｘ）＝２である点をＰ２  とする。このように、Ｐｋ  からＤまたは、Ｄ±１の方向にあり、Ｌ（ｘ）＝ｋ＋１である点をＰｋ＋１  とする。
【００５２】
▲４▼▲３▼のルールで、Ｐ１  となり得る全ての点から、考えられるすべての可能性を探索する。発見されたＮ個のＰＫ  を｛ＰＫＮ｝Ｎｎ＝１とする。
図９は、▲２▼〜▲４▼に対応する擬似コードを示す図である。
以上のように再帰的手法を用いて全ての｛ＰＫｎ｝Ｎｎ＝１を発見する。図８の例では、ＰＫ１  とＰＫ２  が｛ＰＫｎ｝Ｎｎ＝１に登録される。Ｄまたは、Ｄ±１の方向のみにしか探索は進めないというルールからＰＫ３は登録されない。
【００５３】
次に、この｛ＰＫｎ｝Ｎｎ＝１を用いて、
▲５▼線分Ｐ０  ＰＫｎと線分Ｐ０  Ｐ−Ｋのなす角の余弦
Ｑｎ＝ａＫｎ・ｂＫ／（│ａＫｎ││ｂＫ│）、  （ｎ＝１，２，…，Ｎ）
を求める。ただし、Ｐｋ  ＝（ｘｋ，ｙｋ）として、
ａＫｎ＝（ｘＫｎ−ｘ０，ｙＫｎ−ｙ０）
ｂＫ＝（ｘ−Ｋ−ｘ０，ｙ−Ｋ−ｙ０）
とする。ここで、記号「・」はベクトルの内積を表す。
【００５４】
▲６▼Ｑｎ  を最小にするＰＫｎ  を新たな探索点ｔ０  として、「（Ａ）線分同士の接続性を考慮した点列追跡法」で説明した点列の探索を再開する。
Ｐ０  からｔ０  までの通過点について点列リストＵａ  、方向コードリストＣａ  、未探索点フラグＦを整理する。但し、Ｑｎ  ＝Ｑｍ  かつＰＫｎ≠ＰＫｍ  となるＰＫｍ  が別に存在する場合は、Ｐ０  でその点列の探索を終了する。
【００５５】
上記の手法により、分岐点、交差点においても点列の前後関係が自然となる点列追跡がなされる。図８の例では、ＰＫ１が新たな探索点として選ばれる。
上述した「（Ａ）線分同士の接続性を考慮した点列追跡法」で説明した手法により、点列の分岐点、交差点を複数回通過する点列追跡を行うことが可能である。よって、図８において、一度矢印のような下から上への点列の追跡が行われた後に、左から右への追跡があった場合にも、横方向の点列の前後関係を保持することができる。これにより、その関数化画像は拡大しても、十字の形状を正確に再現することが可能となる。
【００５６】
図１０〜図１２は、図１７に示した黒画素点列を本実施形態の画像処理装置によって追跡した後、その点列を関数近似し、５倍に拡大した部分的な図である。図１０〜図１２に示した各部分において、セグメント点列の接続点においても図２１〜図２３にみられたような隙間を生じることはない。また、分岐点、交差点における点列の連続性を保持した拡大画像が得られており、従来手法における問題が解決されていることがわかる。図１７に示した入力画像に対する点列追跡は、右下の端点から開始され、入力画像中の線分の全体は１つの点列として抽出された。この点列中に交差点となる画素は各２回ずつあげられている。
【００５７】
図１３〜図１６は、本実施形態の画像処理装置による処理を地図画像に適用した例の説明図である。図１３には原画が示されている。また、図１４には本実施形態の画像処理装置で処理された結果が、図１５には従来手法で処理された結果が、図１６には比較のためにＢＭＰ形式の画像が、それぞれ２倍に拡大されて示されている。図１５に示した従来手法による結果では点列のつながりに隙間が生じているが、図１４に示した本実施形態の手法による結果では人間の知覚に自然な関数化が行われていることがわかる。また、図１６に示したＢＭＰ形式の画像のようなジャギーノイズが生じない。以上のことより、本実施形態の手法は、近似関数決定の前処理として、線幅１画素の線分を含む図面画像の点列追跡手法として有効であることがわかる。
【００５８】
なお、本発明は上記実施形態に限定されるものではなく、本発明の要旨の範囲内において種々の変形実施が可能である。上述した実施形態では、スキャナ２００を用いて画像入力を行ったが、その他の入力装置（例えばデジタルカメラ）を用いたり、光磁気ディスク等に格納された画像データを読み込むことにより入力するようにしてもよい。
【００５９】
【発明の効果】
上述したように、本発明によれば、つながりを考慮した画素列の追跡を行うことにより、分岐点や交差点における隙間や角点のずれの発生を防止することができる。
【図面の簡単な説明】
【図１】一実施形態の画像処理装置の構成を示す図である。
【図２】本実施形態の画像処理装置の動作手順を示す流れ図である。
【図３】入力画像に対する画素追跡の好ましい例を示す図である。
【図４】画素追跡の概要を示す図である。
【図５】周辺画素の定義の説明図である。
【図６】入力画像の走査順番を示す図である。
【図７】入力画像に対する画素追跡の好ましくない例を示す図である。
【図８】交差点における追跡方向の決定方法の説明図である。
【図９】画素追跡のアルゴリズムに対応する擬似コードを示す図である。
【図１０】図１７に示した黒画素点列を本実施形態の画像処理装置によって追跡した後、その点列を関数近似し、５倍に拡大した部分的な図である。
【図１１】図１７に示した黒画素点列を本実施形態の画像処理装置によって追跡した後、その点列を関数近似し、５倍に拡大した部分的な図である。
【図１２】図１７に示した黒画素点列を本実施形態の画像処理装置によって追跡した後、その点列を関数近似し、５倍に拡大した部分的な図である。
【図１３】本実施形態の画像処理装置による処理を地図画像に適用した例の説明図である。
【図１４】本実施形態の画像処理装置による処理を地図画像に適用した例の説明図である。
【図１５】本実施形態の画像処理装置による処理を地図画像に適用した例の説明図である。
【図１６】本実施形態の画像処理装置による処理を地図画像に適用した例の説明図である。
【図１７】線幅１画素で構成された二値画像の具体例を示す図である。
【図１８】線幅１画素で構成された二値画像の具体例を示す図である。
【図１９】線幅１画素で構成された二値画像の具体例を示す図である。
【図２０】線幅１画素で構成された二値画像の具体例を示す図である。
【図２１】線幅１画素で構成された二値画像の具体例を示す図である。
【図２２】線幅１画素で構成された二値画像の具体例を示す図である。
【図２３】線幅１画素で構成された二値画像の具体例を示す図である。
【図２４】入力画像の具体例を示す図である。
【図２５】入力画像に対する画素追跡の従来例を示す図である。
【符号の説明】
１００  画像処理装置
１１０  画像格納部
１２０  点列追跡部
１３０  接合点抽出部
１４０  セグメント分割部
１５０  関数化処理部
１６０  出力画像生成部
２００  スキャナ
２１０  キーボード
２１２  マウス
２２０  ディスプレイ装置
２３０  プリンタ
【図１】
2005004509.tif 000007
【図２】
2005004509.tif 000008
【図３】
2005004509.tif 000009
【図４】
2005004509.tif 000010
【図５】
2005004509.tif 000011
【図６】
2005004509.tif 000012
【図７】
2005004509.tif 000013
【図８】
2005004509.tif 000014
【図９】
2005004509.tif 000015
【図１０】
2005004509.tif 000016
【図１１】
2005004509.tif 000017
【図１２】
2005004509.tif 000018
【図１３】
2005004509.tif 000019
【図１４】
2005004509.tif 000020
【図１５】
2005004509.tif 000021
【図１６】
2005004509.tif 000022
【図１７】
2005004509.tif 000023
【図１８】
2005004509.tif 000024
【図１９】
2005004509.tif 000025
【図２０】
2005004509.tif 000026
【図２１】
2005004509.tif 000027
【図２２】
2005004509.tif 000028
【図２３】
2005004509.tif 000029
【図２４】
2005004509.tif 000030
【図２５】
2005004509.tif 000031