(57)【要約】【課題】複数の図形を含む画像からそれぞれの図形を適切に抽出することのできる画像処理装置、画像処理装置の制御方法、および画像処理装置の制御プログラムを提供する。【解決手段】画像処理装置としての画像形成装置は、画像から抽出した輪郭上の任意の点を開始点として、抽出した輪郭を走査することにより、輪郭上の分岐点および開始点を検索する（Ｓ１０５）。画像形成装置は、分岐点を発見した場合に、その分岐点の位置と、その分岐点から分岐した複数の経路とを記憶する（Ｓ１１０）。画像形成装置は、分岐点を発見した場合に、最も右側の経路を走査する経路として選択する（Ｓ１１１）。画像形成装置は、開始点を発見した場合に、走査した軌跡により構成された図形を抽出し（Ｓ１１５）、走査の際に発見した分岐点を新たな開始点とし、新たな開始点とした分岐点から分岐した複数の経路のうち、未走査の経路を走査する（Ｓ１２１）。【選択図】図４
2015060441.tif 000002
【特許請求の範囲】
【請求項１】
複数の図形を含む画像からそれぞれの図形を抽出する画像処理装置であって、
前記複数の図形の各々の輪郭を前記画像から抽出する輪郭抽出手段と、
前記輪郭抽出手段にて抽出した輪郭上の任意の点を開始点として、前記輪郭抽出手段にて抽出した輪郭を走査することにより、輪郭上の分岐点および前記開始点を検索する第１の走査手段と、
前記第１の走査手段にて分岐点を発見した場合に、発見した分岐点の位置と、発見した分岐点から分岐した複数の経路とを記憶する記憶手段と、
前記第１の走査手段にて分岐点を発見した場合に、発見した分岐点から分岐した複数の経路のうち進行方向に向かって特定の位置に存在する経路を、前記第１の走査手段にて走査する経路として選択する選択手段と、
前記第１の走査手段にて開始点を発見した場合に、前記第１の走査手段にて走査した軌跡により構成された図形を抽出する図形抽出手段と、
前記図形抽出手段にて図形を抽出した場合に、前記第１の走査手段にて発見した分岐点を新たな開始点とし、前記新たな開始点とした分岐点から分岐した複数の経路のうち、未走査経路を走査する第２の走査手段とを備えた、画像処理装置。
【請求項２】
抽出する図形が無くなった場合に、前記輪郭抽出手段にて抽出した輪郭のうち図形として抽出されなかった輪郭を線分として抽出する線分抽出手段をさらに備えた、請求項１に記載の画像処理装置。
【請求項３】
前記第１の走査手段にて分岐点を発見した後であって前記開始点を発見する前に、前記第１の走査手段にて発見した分岐点を再び発見した場合に、前記第１の走査手段にて走査した軌跡により構成された図形を破棄する破棄手段をさらに備えた、請求項１または２に記載の画像処理装置。
【請求項４】
前記第１の走査手段にて分岐点を発見した後であって前記開始点を発見する前に、前記第１の走査手段にて発見した分岐点を再び発見した場合に、前記第１の走査手段にて発見した複数の分岐点のうち、前記第１の走査手段にて始めに発見した分岐点を新たな開始点とし、前記新たな開始点とした分岐点から分岐した複数の経路のうち、前記第１の走査手段にて走査した経路とは異なる経路を走査する第３の走査手段をさらに備えた、請求項１〜３のいずれかに記載の画像処理装置。
【請求項５】
前記第２の走査手段は、前記第１の走査手段にて発見した複数の分岐点のうち、前記第１の走査手段にて始めに発見した分岐点を新たな開始点として走査する、請求項１〜４のいずれかに記載の画像処理装置。
【請求項６】
前記第２の走査手段は、
前記第１の走査手段にて、始めに発見した分岐点が未走査経路を有していない場合に、前記第１の走査手段にて発見した複数の分岐点の中に、未走査経路を有している分岐点があるか否かを判別する経路判別手段と、
前記経路判別手段にて、前記第１の走査手段にて発見した複数の分岐点の中に、未走査経路を有している分岐点があると判別した場合に、前記第１の走査手段にて発見した、未走査経路を有している分岐点のうち、前記第１の走査手段にて最も早く発見した分岐点を新たな開始点として、未走査経路を走査する第１の未走査経路走査手段とを備えた、請求項１〜５のいずれかに記載の画像処理装置。
【請求項７】
前記第２の走査手段は、
前記経路判別手段にて、前記第１の走査手段にて発見した複数の分岐点の中に、未走査経路を有している分岐点が無いと判別した場合に、前記第１の走査手段による走査よりも前に行った走査のうち、未走査経路を有している分岐点を発見した最新の走査を特定する特定手段と、
前記特定手段にて特定した走査の際に発見した、未走査経路を有している分岐点を新たな開始点として、未走査経路を走査する第２の未走査経路走査手段とを備えた、請求項６に記載の画像処理装置。
【請求項８】
前記記憶手段にて記憶した分岐点から分岐した複数の経路のうち、前記図形抽出手段にて抽出した図形を構成する経路を消去する第１の消去手段と、
前記記憶手段にて記憶した位置のうち、経路が全て消去された分岐点の位置を消去する第２の消去手段とをさらに備えた、請求項１〜７のいずれかに記載の画像処理装置。
【請求項９】
複数の図形を含む画像からそれぞれの図形を抽出する画像処理装置の制御方法であって、
前記複数の図形の各々の輪郭を前記画像から抽出する輪郭抽出ステップと、
前記輪郭抽出ステップにて抽出した輪郭上の任意の点を開始点として、前記輪郭抽出ステップにて抽出した輪郭を走査することにより、輪郭上の分岐点および前記開始点を検索する第１の走査ステップと、
前記第１の走査ステップにて分岐点を発見した場合に、発見した分岐点の位置と、発見した分岐点から分岐した複数の経路とを記憶する記憶ステップと、
前記第１の走査ステップにて分岐点を発見した場合に、発見した分岐点から分岐した複数の経路のうち進行方向に向かって特定の位置に存在する経路を、前記第１の走査ステップにて走査する経路として選択する選択ステップと、
前記第１の走査ステップにて開始点を発見した場合に、前記第１の走査ステップにて走査した軌跡により構成された図形を抽出する図形抽出ステップと、
前記図形抽出ステップにて図形を抽出した場合に、前記第１の走査ステップにて発見した分岐点を新たな開始点とし、前記新たな開始点とした分岐点から分岐した複数の経路のうち、未走査経路を走査する第２の走査ステップとを備えた、画像処理装置の制御方法。
【請求項１０】
複数の図形を含む画像からそれぞれの図形を抽出する画像処理装置の制御プログラムであって、
前記複数の図形の各々の輪郭を前記画像から抽出する輪郭抽出ステップと、
前記輪郭抽出ステップにて抽出した輪郭上の任意の点を開始点として、前記輪郭抽出ステップにて抽出した輪郭を走査することにより、輪郭上の分岐点および前記開始点を検索する第１の走査ステップと、
前記第１の走査ステップにて分岐点を発見した場合に、発見した分岐点の位置と、発見した分岐点から分岐した複数の経路とを記憶する記憶ステップと、
前記第１の走査ステップにて分岐点を発見した場合に、発見した分岐点から分岐した複数の経路のうち進行方向に向かって特定の位置に存在する経路を、前記第１の走査ステップにて走査する経路として選択する選択ステップと、
前記第１の走査ステップにて開始点を発見した場合に、前記第１の走査ステップにて走査した軌跡により構成された図形を抽出する図形抽出ステップと、
前記図形抽出ステップにて図形を抽出した場合に、前記第１の走査ステップにて発見した分岐点を新たな開始点とし、前記新たな開始点とした分岐点から分岐した複数の経路のうち、未走査経路を走査する第２の走査ステップとをコンピューターに実行させる、画像処理装置の制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置、画像処理装置の制御方法、および画像処理装置の制御プログラムに関し、より特定的には、複数の図形を含む画像からそれぞれの図形を抽出する画像処理装置、画像処理装置の制御方法、および画像処理装置の制御プログラムに関する。
【背景技術】
【０００２】
画像形成装置を始めとする画像処理装置は、原稿をスキャンすることなどにより得られた画像（スキャンデータ）を、マイクロソフトオフィス（登録商標）などのオフィスソフトのファイル形式に変換する画像処理機能を有している。この画像処理機能には、図の編集能力に課題があることが知られている。すなわち、画像処理装置は、常に画像全体を一枚の画像として変換するため、変換対象となる画像が複数の図形を含んでいる場合であっても、変換後の画像において図形毎に編集（たとえば色、大きさ、形状、位置などの変更）を行うことができないという課題があった。
【０００３】
上記課題を解決するためには、複数の図形の各々を編集可能な状態に分離（分解）して画像から抽出する必要がある。複数の図形を含む画像から図形を抽出する方法には、主に次の３つの方法がある。
【０００４】
第１の方法は、ラベリングにより図形を抽出する方法である。第１の方法は、画像内の任意の注目画素と、注目画素に隣接する隣接画素とを比較し、注目画素と隣接画素とが同じ色であれば同じ図形（同じ領域）と判断し、異なる色であれば異なる図形（異なる領域）であると判断する方法である。第１の方法には、いくつかの問題が存在する。
【０００５】
抽出対象となる画像が、複数のボックスと、複数のボックスの各々を接続する矢印（線）とで構成されたフローチャートであり、ブロックおよび線は同一色である場合を想定する。この場合、第１の方法では、同一色であるブロックと矢印とを分離して抽出することはできなかった。
【０００６】
また、抽出対象となる画像に含まれる図形の外枠に、図形内部とは別の色が施されている場合、第１の方法では、図形内部と、図形の外枠とが別々の図形として抽出されていた。
【０００７】
第２の方法は、輪郭追跡という方法である。第２の方法は、画像内の図形の輪郭を走査することにより得られた閉曲線を図形として抽出する方法である。第２の方法では、抽出対象となる画像が互いに隣接した複数の図形を含んでいる場合、複数の図形をひとまとまりの図形として見た場合の輪郭のみを走査する結果、複数の図形の各々を分離して抽出することはできなかった。
【０００８】
第２の方法における、複数の図形の各々を分離して抽出することはできないという問題を解決し得る技術は、たとえば下記特許文献１および２などに開示されている。
【０００９】
下記特許文献１には、画像処理装置によりディジタル画像の輪郭を追跡し画像領域を把握して輪郭情報を生成する画像処理方法が開示されている。この画像処理方法では、入力されたディジタル画像について、出発点の進行方向両端の画素の色と同じ画素の境界辺を追跡する輪郭追跡を行って輪郭線分を抽出する輪郭線分処理を行い、抽出された輪郭線分に関して分岐処理及び合成処理を行い、輪郭線分の結合で決まる輪郭を形成してディジタル画像の輪郭情報を生成する。
【００１０】
下記特許文献２には、交点抽出部が、入力画像から抽出した罫線同士の交点を抽出し、記憶部が、交点に属する各罫線に沿ってこの交点からそれぞれ遠ざかるまたは近づく向きの腕ベクトルと、この腕ベクトルが経路探索に用いられたか否かを示すフラグとを含んだ交点情報を記憶する枠線認識装置が開示されている。この枠線認識装置では、枠線抽出部が、所定の交点を始点として腕ベクトルの向きに従った経路探索を行うことによって閉じた経路が検出された場合に、この閉じた経路を枠線として抽出し、閉じた経路の検出に用いられた腕ベクトルに対応するフラグを使用済みへ更新し、すべてのフラグが使用済みへ更新された場合に、経路探索を終了させるように枠線認識装置を構成する。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２００６−３１２４５号公報
【特許文献２】特開２０１２−６４０９８号公報
【発明の概要】
【発明が解決しようとする課題】
【００１２】
特許文献１の技術は、画像の色情報を利用して各図形の境界（色境界）を認識し、この境界を走査することにより得られる閉曲線を図形として抽出するものである。特許文献１の技術では、３色が交わる画素（分岐点）に走査点が到達した場合には、現在検出中の図形と同じ色の方向に進むことによって、図形を抽出している。しかし、この抽出方法には、画像に含まれる図形の外枠に図形内部とは別の色が施されている場合、図形内部と、図形の外枠とが別々の図形として抽出されるという問題があった。
【００１３】
特許文献２の技術では、経路検索を行う前に全画素を調査し、全ての罫線の交点（分岐点）とこれに付随する進路とを保持しておく必要がある。このため、メモリ量が膨大になるという問題があった。加えて、検出に必要な分岐点として罫線の交点を用いるため、たとえば円形の図形などの罫線が無い図形の場合には図形を抽出することができないという問題があった。
【００１４】
本発明は、上記課題を解決するためのものであり、その目的は、複数の図形を含む画像からそれぞれの図形を適切に抽出することのできる画像処理装置、画像処理装置の制御方法、および画像処理装置の制御プログラムを提供することである。
【課題を解決するための手段】
【００１５】
本発明の一の局面に従う画像処理装置は、複数の図形を含む画像からそれぞれの図形を抽出する画像処理装置であって、複数の図形の各々の輪郭を画像から抽出する輪郭抽出手段と、輪郭抽出手段にて抽出した輪郭上の任意の点を開始点として、輪郭抽出手段にて抽出した輪郭を走査することにより、輪郭上の分岐点および開始点を検索する第１の走査手段と、第１の走査手段にて分岐点を発見した場合に、発見した分岐点の位置と、発見した分岐点から分岐した複数の経路とを記憶する記憶手段と、第１の走査手段にて分岐点を発見した場合に、発見した分岐点から分岐した複数の経路のうち進行方向に向かって特定の位置に存在する経路を、第１の走査手段にて走査する経路として選択する選択手段と、第１の走査手段にて開始点を発見した場合に、第１の走査手段にて走査した軌跡により構成された図形を抽出する図形抽出手段と、図形抽出手段にて図形を抽出した場合に、第１の走査手段にて発見した分岐点を新たな開始点とし、新たな開始点とした分岐点から分岐した複数の経路のうち、未走査経路を走査する第２の走査手段とを備える。
【００１６】
上記画像処理装置において好ましくは、抽出する図形が無くなった場合に、輪郭抽出手段にて抽出した輪郭のうち図形として抽出されなかった輪郭を線分として抽出する線分抽出手段をさらに備える。
【００１７】
上記画像処理装置において好ましくは、第１の走査手段にて分岐点を発見した後であって開始点を発見する前に、第１の走査手段にて発見した分岐点を再び発見した場合に、第１の走査手段にて走査した軌跡により構成された図形を破棄する破棄手段をさらに備える。
【００１８】
上記画像処理装置において好ましくは、第１の走査手段にて分岐点を発見した後であって開始点を発見する前に、第１の走査手段にて発見した分岐点を再び発見した場合に、第１の走査手段にて発見した複数の分岐点のうち、第１の走査手段にて始めに発見した分岐点を新たな開始点とし、新たな開始点とした分岐点から分岐した複数の経路のうち、第１の走査手段にて走査した経路とは異なる経路を走査する第３の走査手段をさらに備える。
【００１９】
上記画像処理装置において好ましくは、第２の走査手段は、第１の走査手段にて発見した複数の分岐点のうち、第１の走査手段にて始めに発見した分岐点を新たな開始点として走査する。
【００２０】
上記画像処理装置において好ましくは、第２の走査手段は、第１の走査手段にて、始めに発見した分岐点が未走査経路を有していない場合に、第１の走査手段にて発見した複数の分岐点の中に、未走査経路を有している分岐点があるか否かを判別する経路判別手段と、経路判別手段にて、第１の走査手段にて発見した複数の分岐点の中に、未走査経路を有している分岐点があると判別した場合に、第１の走査手段にて発見した、未走査経路を有している分岐点のうち、第１の走査手段にて最も早く発見した分岐点を新たな開始点として、未走査経路を走査する第１の未走査経路走査手段とを備える。
【００２１】
上記画像処理装置において好ましくは、第２の走査手段は、経路判別手段にて、第１の走査手段にて発見した複数の分岐点の中に、未走査経路を有している分岐点が無いと判別した場合に、第１の走査手段による走査よりも前に行った走査のうち、未走査経路を有している分岐点を発見した最新の走査を特定する特定手段と、特定手段にて特定した走査の際に発見した、未走査経路を有している分岐点を新たな開始点として、未走査経路を走査する第２の未走査経路走査手段とを備える。
【００２２】
上記画像処理装置において好ましくは、記憶手段にて記憶した分岐点から分岐した複数の経路のうち、図形抽出手段にて抽出した図形を構成する経路を消去する第１の消去手段と、記憶手段にて記憶した位置のうち、経路が全て消去された分岐点の位置を消去する第２の消去手段とをさらに備える。
【００２３】
本発明の他の局面に従う画像処理装置の制御方法は、複数の図形を含む画像からそれぞれの図形を抽出する画像処理装置の制御方法であって、複数の図形の各々の輪郭を画像から抽出する輪郭抽出ステップと、輪郭抽出ステップにて抽出した輪郭上の任意の点を開始点として、輪郭抽出ステップにて抽出した輪郭を走査することにより、輪郭上の分岐点および開始点を検索する第１の走査ステップと、第１の走査ステップにて分岐点を発見した場合に、発見した分岐点の位置と、発見した分岐点から分岐した複数の経路とを記憶する記憶ステップと、第１の走査ステップにて分岐点を発見した場合に、発見した分岐点から分岐した複数の経路のうち進行方向に向かって特定の位置に存在する経路を、第１の走査ステップにて走査する経路として選択する選択ステップと、第１の走査ステップにて開始点を発見した場合に、第１の走査ステップにて走査した軌跡により構成された図形を抽出する図形抽出ステップと、図形抽出ステップにて図形を抽出した場合に、第１の走査ステップにて発見した分岐点を新たな開始点とし、新たな開始点とした分岐点から分岐した複数の経路のうち、未走査経路を走査する第２の走査ステップとを備える。
【００２４】
本発明のさらに他の局面に従う画像処理装置の制御プログラムは、複数の図形を含む画像からそれぞれの図形を抽出する画像処理装置の制御プログラムであって、複数の図形の各々の輪郭を画像から抽出する輪郭抽出ステップと、輪郭抽出ステップにて抽出した輪郭上の任意の点を開始点として、輪郭抽出ステップにて抽出した輪郭を走査することにより、輪郭上の分岐点および開始点を検索する第１の走査ステップと、第１の走査ステップにて分岐点を発見した場合に、発見した分岐点の位置と、発見した分岐点から分岐した複数の経路とを記憶する記憶ステップと、第１の走査ステップにて分岐点を発見した場合に、発見した分岐点から分岐した複数の経路のうち進行方向に向かって特定の位置に存在する経路を、第１の走査ステップにて走査する経路として選択する選択ステップと、第１の走査ステップにて開始点を発見した場合に、第１の走査ステップにて走査した軌跡により構成された図形を抽出する図形抽出ステップと、図形抽出ステップにて図形を抽出した場合に、第１の走査ステップにて発見した分岐点を新たな開始点とし、新たな開始点とした分岐点から分岐した複数の経路のうち、未走査経路を走査する第２の走査ステップとをコンピューターに実行させる。
【発明の効果】
【００２５】
本発明によれば、複数の図形を含む画像からそれぞれの図形を適切に抽出することのできる画像処理装置、画像処理装置の制御方法、および画像処理装置の制御プログラムを提供することができる。
【図面の簡単な説明】
【００２６】
【図１】本発明の第１の実施の形態における画像形成装置の構成を示すブロック図である。
【図２】本発明の第１の実施の形態において、画像形成装置が行う図形の抽出方法を説明する第１の図である。
【図３】本発明の第１の実施の形態において、画像形成装置が行う図形の抽出方法を説明する第１の図である。
【図４】本発明の第１の実施の形態における画像形成装置の動作を示すフローチャートである。
【図５】本発明の第２の実施の形態において、画像形成装置が行う図形の抽出方法を説明する第１の図である。
【図６】本発明の第２の実施の形態において、画像形成装置が行う図形の抽出方法を説明する第１の図である。
【図７】本発明の第２の実施の形態において、画像形成装置が行う図形の抽出方法を説明する第１の図である。
【図８】本発明の第２の実施の形態における画像形成装置の動作を示すフローチャートである。
【図９】本発明の第３の実施の形態において、画像形成装置が行う図形の抽出方法を説明する第１の図である。
【図１０】本発明の第３の実施の形態において、画像形成装置が行う図形の抽出方法を説明する第２の図である。
【図１１】本発明の第３の実施の形態における、図４のステップＳ１１９の開始点決定処理のサブルーチンである。
【図１２】本発明の第４の実施の形態において、画像形成装置が行う図形の抽出方法を説明する第１の図である。
【図１３】本発明の第４の実施の形態において、画像形成装置が行う図形の抽出方法を説明する第２の図である。
【図１４】本発明の第４の実施の形態において、画像形成装置が行う図形の抽出方法を説明する第３の図である。
【図１５】本発明の第４の実施の形態において、画像形成装置が行う図形の抽出方法を説明する第４の図である。
【図１６】本発明の第４の実施の形態における画像形成装置の動作を示すフローチャートである。
【図１７】本発明の第１〜第４の実施の形態において抽出される図形を模式的に示す図である。
【発明を実施するための形態】
【００２７】
以下、本発明の実施の形態について、図面に基づいて説明する。
【００２８】
以下の実施の形態においては、画像処理装置が、スキャナー機能、ファクシミリ機能、複写機能、プリンターとしての機能、データ通信機能、およびサーバー機能を備えたＭＦＰ（Ｍｕｌｔｉｆｕｎｃｔｉｏｎ  Ｐｅｒｉｐｈｅｒａｌ）である場合について説明する。画像処理装置は、たとえば電子写真方式や静電記録方式などによって画像形成を行うＭＦＰ以外の画像形成装置であってもよく、たとえばファクシミリ装置、複写機、またはプリンターなどであってもよい。画像処理装置は、画像形成装置以外のものであってもよく、たとえばＰＣ（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ）、携帯電話、またはスキャナー装置などであってもよい。
【００２９】
［第１の実施の形態］
【００３０】
始めに、本実施の形態における画像形成装置の構成について説明する。
【００３１】
図１は、本発明の第１の実施の形態における画像形成装置の構成を示すブロック図である。
【００３２】
図１を参照して、本実施の形態における画像形成装置１は、スキャナー機能、ファクシミリ機能、複写機能、プリンターとしての機能、データ通信機能、およびサーバー機能を備えるＭＦＰである。画像形成装置１は、制御部１０と、固定記憶部２０と、画像読取部３０と、画像形成部４０と、ネットワークＩ／Ｆ５０と、操作パネル６０とを含んでいる。
【００３３】
制御部１０は、固定記憶部２０、画像読取部３０、画像形成部４０、ネットワークＩ／Ｆ５０、および操作パネル６０の各々と接続されている。制御部１０は、スキャンジョブ、コピージョブ、メール送信ジョブ、およびプリントジョブなどの各種ジョブについて、画像形成装置１全体の制御を行う。
【００３４】
固定記憶部２０は、たとえばＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）であり、画像読取部３０で読み取った画像や、ネットワークＩ／Ｆ５０を通じて外部機器から受信した画像などの各種情報を記憶する。
【００３５】
画像読取部３０は、原稿の画像を読み取ることにより、用紙に画像を形成する。
【００３６】
画像形成部４０は、用紙に画像を形成する。画像形成部４０は、おおまかに、トナー像形成部、定着装置、および用紙搬送部などで構成される。画像形成部４０は、たとえば電子写真方式で用紙に画像を形成する。トナー像形成部は、いわゆるタンデム方式で４色の画像を合成し、用紙にカラー画像を形成する。トナー像形成部は、Ｃ（シアン）、Ｍ（マゼンタ）、Ｙ（イエロー）、Ｋ（ブラック）の各色について設けられた感光体と、感光体からトナー像が転写（１次転写）される中間転写ベルトと、中間転写ベルトから用紙に画像を転写（２次転写）する転写部などで構成される。定着装置は、加熱ローラーおよび加圧ローラーを有する。定着装置は、加熱ローラーと加圧ローラーとでトナー像が形成された用紙を挟みながら搬送し、その用紙に加熱および加圧を行なう。これにより、定着装置は、用紙に付着したトナーを溶融させて用紙に定着させ、用紙に画像を形成する。用紙搬送部は、給紙ローラー、搬送ローラー、およびそれらを駆動するモーターなどで構成されている。用紙搬送部は、用紙を給紙カセットから給紙して、画像形成装置１の筐体の内部で搬送する。また、用紙搬送部は、画像が形成された用紙を画像形成装置１の筐体から排紙トレイなどに排出する。
【００３７】
ネットワークＩ／Ｆ５０は、画像形成装置１と、画像形成装置１とネットワークを通じて接続された外部機器との間の通信を行う。
【００３８】
操作パネル６０は、ユーザーに対して各種情報を表示し、ユーザーからの各種操作を受け付ける。
【００３９】
制御部１０は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、およびＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）などからなっている。ＣＰＵは、ＲＯＭに記憶された制御プログラムを実行する。ＲＡＭは、ＣＰＵのワークエリアとなる。制御部１０は、画像記憶部１０１と、前処理部１０２と、輪郭走査部１０３と、分岐点記憶部１０４と、進路選択部１０５と、図形判定部１０６と、図形記憶部１０７などを含んでいる。
【００４０】
画像記憶部１０１は、図形抽出の対象となる画像を固定記憶部に保存する。
【００４１】
前処理部１０２は、固定記憶部に保存した画像から図形の輪郭を抽出することにより、画像を走査可能な状態に変換する。
【００４２】
輪郭走査部１０３は、前処理部１０２で抽出した輪郭を走査することにより、輪郭上の分岐点および開始点を検索する。輪郭走査部１０３は、連続した画素を追跡するだけであるので、図形形状には依存せずに輪郭を走査可能である。
【００４３】
分岐点記憶部１０４は、輪郭走査部１０３が分岐点を発見した場合に、その分岐点の位置（座標）と、その分岐点から分岐した複数の経路とを固定記憶部２０に記憶する。分岐点記憶部１０４は、輪郭走査部１０３による走査の際に分岐点を発見した場合に、その分岐点を発見した順番を固定記憶部２０に記憶することが好ましい。また分岐点記憶部１０４は、輪郭走査部１０３が走査を開始する際の開始点を固定記憶部２０に記憶する。
【００４４】
進路選択部１０５は、輪郭走査部１０３が分岐点を発見した場合に、その分岐点から分岐した複数の経路（分岐点を構成する複数の経路）のうち、進行方向に向かって特定の位置に存在する経路（一定の方向に存在する経路）を、走査する経路として選択する。また進路選択部１０５は、輪郭の走査を再開する場合に開始点となる分岐点および走査する経路を選択する。進路選択部１０５は、進行方向に向かって常に特定の位置に存在する経路を選択するものであればよい。
【００４５】
図形判定部１０６は、輪郭走査部１０３が開始点または分岐点を発見した場合に、分岐点記憶部１０４が記憶した分岐点の位置に基づいて、輪郭走査部１０３が走査した軌跡により構成された図形が閉曲線（閉ループ、閉領域）であるか否かを判定する。具体的には、輪郭走査部１０３が走査の際に開始点を再び発見した場合、図形判定部１０６は、走査した軌跡により構成された図形が閉曲線であると判定する。一方、輪郭走査部１０３が走査の際に分岐点を発見した後であって開始点を発見する前に、走査にて既に発見した分岐点を再び発見した場合、図形判定部１０６は、走査した軌跡により構成された図形が線分（開ループ）と閉曲線との組合せであると判定する。
【００４６】
図形記憶部１０７は、所定の場合に、走査した軌跡により構成された図形を抽出し、抽出した図形を固定記憶部２０に記憶する。
【００４７】
画像形成装置は、互いに隣接する複数の図形を含む画像からそれぞれの図形を抽出する。次に、本実施の形態において、画像形成装置が行う図形の抽出方法について説明する。
【００４８】
図２および図３は、本発明の第１の実施の形態において、画像形成装置が行う図形の抽出方法を説明する図である。なお、以降の図においては、画像に含まれる図形の色の違いを太線のハッチングの種類によって示し、画像から抽出された図形を細線のハッチングによって示すことがある。
【００４９】
図２（ａ）を参照して、図形抽出の対象となる画像ＩＭは、互いに隣接した図形ＦＧ１およびＦＧ２を含んでいる。図形ＦＧ１およびＦＧ２の各々は、正方形の形状を有している。図形ＦＧ１の内部はたとえば緑色であり、図形ＦＧ２の内部はたとえば青色である。図形ＦＧ１およびＦＧ２の外枠はたとえば赤色である。
【００５０】
図２（ｂ）を参照して、画像形成装置１は、固定記憶部２０などから画像ＩＭを入手すると、前処理部１０２を用いて画像ＩＭから各図形の輪郭ＯＬを抽出することにより、画像を走査可能な状態に変換する。画像形成装置１は、たとえば隣接する画素同士の明度差や色差などに基づいて図形ＦＧ１およびＦＧ２の各々のエッジを抽出し、エッジに対して細線化を施すことにより、各図形の輪郭ＯＬを抽出する。輪郭ＯＬは線状であり、連続した画素で構成される。細線化とは、線幅を１画素にする手法を意味する。
【００５１】
次に画像形成装置１は、進路選択部１０５を用いて選択した開始点ＳＴ１から、図２中右方向に向かって輪郭ＯＬの１回目の走査を開始する。画像形成装置１は、輪郭走査部１０３を用いて走査を行うことにより、輪郭ＯＬ上の分岐点および開始点ＳＴ１を検索する。画像形成装置１は、分岐点記憶部１０４を用いて、開始点ＳＴ１を固定記憶部２０に記憶する。
【００５２】
１回目の走査の際の開始点の位置および開始点からの進行方向は任意である。１回目の走査の際、開始点の近傍には未走査の画素しか存在しないので、画像読取部３０による画像の主走査方向（たとえば主走査方向が図２中左から右へ向かう方向であり、副走査方向が図２中上から下へ向かう方向である場合には、図２中右方向）を、輪郭走査部１０３による進行方向として選択してもよい。また、走査開始時の進行方向を右方向とした場合には、その後の分岐点において、分岐点から分岐した複数の経路のうち、進行方向に向かって最も右側の位置に存在する経路を常に選択してもよい。走査開始時の進行方向を左方向とした場合には、その後の分岐点において、分岐点から分岐した複数の経路のうち、進行方向に向かって最も左側の位置に存在する経路を常に選択してもよい。
【００５３】
以降の実施の形態では、走査開始時の開始点からの進行方向を右方向とし、その後発見した分岐点において、分岐点から分岐した複数の経路のうち、進行方向に向かって最も右側の位置に存在する経路を常に選択するものとする。この場合には、最小単位の図形が時計回りに走査されることにとなる。
【００５４】
図２（ｃ）を参照して、画像形成装置１は、輪郭ＯＬの走査の際に分岐点Ｐ１１を発見する。この場合画像形成装置１は、分岐点記憶部１０４を用いて、分岐点Ｐ１１の位置と、分岐点Ｐ１１から分岐した経路Ｌ１１ＡおよびＬ１１Ｂとを固定記憶部２０に記憶する。このとき、画像形成装置１は、分岐点Ｐ１１から分岐した経路のうち走査済の経路Ｌ１１Ｃを、経路Ｌ１１ＡおよびＬ１１Ｂとともに固定記憶部２０に記憶してもよいし、経路Ｌ１１Ｃを記憶しなくてもよい。
【００５５】
輪郭ＯＬの走査の際に分岐点Ｐ１１を発見した場合、画像形成装置１は、進路選択部１０５を用いて、経路Ｌ１１ＡおよびＬ１１Ｂのうち、進行方向に向かって最も右側の位置に存在する経路である経路Ｌ１１Ａを、走査する経路として選択する。
【００５６】
図２（ｄ）を参照して、画像形成装置１は、輪郭ＯＬの走査の際に分岐点Ｐ１２を発見する。この場合画像形成装置１は、分岐点Ｐ１２の位置と、分岐点Ｐ１２から分岐した経路Ｌ１２ＡおよびＬ１２Ｂとを固定記憶部２０に記憶する。また、画像形成装置１は、経路Ｌ１２ＡおよびＬ１２Ｂのうち、進行方向に向かって最も右側の位置に存在する経路である経路Ｌ１２Ａを、走査する経路として選択する。
【００５７】
図２（ｅ）を参照して、画像形成装置１は、輪郭ＯＬの走査の際に開始点ＳＴ１を発見する。この場合画像形成装置１は、図形判定部１０６を用いて、輪郭走査部１０３が走査した軌跡により構成された図形が閉曲線であると判定する。
【００５８】
図３（ａ）を参照して、走査した軌跡により構成された図形が閉曲線である場合、画像形成装置１は、図形記憶部１０７を用いて、走査した軌跡により構成された図形ＦＧ５１を抽出し、固定記憶部２０に記憶する。これにより、１回目の走査が終了する。
【００５９】
図３（ｂ）を参照して、画像形成装置１は、図形を抽出した場合において、固定記憶部２０に記憶した経路の中に未走査経路が残っているときは、２回目の走査を行う。画像形成装置１は、１回目の走査において発見した分岐点のうち任意の分岐点を新たな開始点とし、その分岐点から分岐した複数の経路のうち、未走査経路を走査する。ここでは、分岐点Ｐ１１を新たな開始点ＳＴ２として、未走査経路である経路Ｌ１１Ｂに沿って（図３中右方向に向かって）輪郭ＯＬの２回目の走査を開始する。
【００６０】
図３（ｃ）を参照して、画像形成装置１は、輪郭ＯＬの走査の際に分岐点Ｐ１２を発見した後（分岐点Ｐ１２の位置、および分岐点Ｐ１２から分岐した経路は、固定記憶部２０に既に記憶されているので、新たに記憶させない）、画像形成装置１は、輪郭ＯＬの走査の際に開始点ＳＴ２を発見する。この場合画像形成装置１は、図形判定部１０６を用いて、輪郭走査部１０３が走査した軌跡により構成された図形が閉曲線であると判定する。
【００６１】
図３（ｄ）を参照して、画像形成装置１は、図形記憶部１０７を用いて、走査した軌跡により構成された図形ＦＧ５２を抽出し、固定記憶部２０に記憶する。これにより、２回目の走査が終了する。
【００６２】
図形ＦＧ５２の抽出後、固定記憶部２０に記憶した経路の中には図形を抽出できる経路が残っていない。この場合画像形成装置１は、抽出する図形が無くなったと判断し、図形として抽出していない輪郭が存在する場合には、それを線分として抽出する。以上により、図形の抽出が完了する。
【００６３】
図４は、本発明の第１の実施の形態における画像形成装置の動作を示すフローチャートである。
【００６４】
図４を参照して、操作パネル６０または外部機器などを通じて画像から図形を抽出する指示を受け付けると、制御部１０は、画像から各図形の輪郭を抽出し（Ｓ１０１）、開始点を設定する（Ｓ１０３）。続いて制御部１０は、開始点から任意の方向に輪郭の走査を開始し（Ｓ１０５）、走査の際に分岐点を発見したか否かを判別する（Ｓ１０７）。
【００６５】
ステップＳ１０７において、分岐点を発見したと判別した場合（Ｓ１０７でＹＥＳ）、制御部１０は、発見した分岐点が、固定記憶部２０に既に記憶した分岐点であるか否かを判別する（Ｓ１０９）。
【００６６】
ステップＳ１０９において、固定記憶部２０に既に記憶した分岐点であると判別した場合（Ｓ１０９でＹＥＳ）、制御部１０は、発見した分岐点から分岐した複数の経路のうち、進行方向に向かって最も右側（右端）の位置に存在する経路を選択し（Ｓ１１１）、ステップＳ１０７の処理へ進む。
【００６７】
ステップＳ１０９において、固定記憶部２０に既に記憶した分岐点でないと判別した場合（Ｓ１０９でＮＯ）、制御部１０は、発見した分岐点の位置および発見した分岐点から分岐した経路を固定記憶部２０に記憶し（Ｓ１１０）、ステップＳ１１１の処理へ進む。
【００６８】
ステップＳ１０７において、分岐点を発見しないと判別した場合（Ｓ１０７でＮＯ）、制御部１０は、開始点を発見したか否かを判別する（Ｓ１１３）。
【００６９】
ステップＳ１１３において、開始点を発見しないと判別した場合（Ｓ１１３でＮＯ）、制御部１０はステップＳ１０７の処理へ進む。一方、ステップＳ１１３において、開始点を発見したと判別した場合（Ｓ１１３でＹＥＳ）、制御部１０は、走査した軌跡により構成された図形が閉曲線であると判定する。この場合制御部１０は、走査した軌跡により構成された図形を抽出し、固定記憶部２０に記憶し、その回の走査を終了する（Ｓ１１５）。次に制御部１０は、固定記憶部２０に記憶した経路の中に未走査経路が残っているか否かを判別する（Ｓ１１７）。
【００７０】
ステップＳ１１７において、固定記憶部２０に記憶した経路の中に未走査経路が残っていると判別した場合（Ｓ１１７でＹＥＳ）、制御部１０は、開始点を移動する処理である開始点決定処理を行う（Ｓ１１９）。本実施の形態では、開始点決定処理として、制御部１０は、直近で終了した走査において発見した任意の分岐点を開始点に決定する。次に制御部１０は、決定した開始点から未走査経路に沿って次の走査を開始し（Ｓ１２１）、ステップＳ１０７の処理へ進む。
【００７１】
ステップＳ１１７において、固定記憶部２０に記憶した経路の中に未走査経路が残っていないと判別した場合（Ｓ１１７でＮＯ）、制御部１０は、図形として抽出していない輪郭があれば、それを線分として抽出し（Ｓ１２３）、処理を終了する。
【００７２】
［第２の実施の形態］
【００７３】
図５〜図７は、本発明の第２の実施の形態において、画像形成装置が行う図形の抽出方法を説明する図である。
【００７４】
図５（ａ）を参照して、図形抽出の対象となる画像ＩＭは、互いに隣接した図形ＦＧ１、線分ＦＧ２、図形ＦＧ３、および図形ＦＧ４を含んでいる。図形ＦＧ１は、正方形の形状を有している。図形ＦＧ３およびＦＧ４は、長方形の形状を有している。図形ＦＧ１およびＦＧ３の内部はたとえば緑色であり、図形ＦＧ４の内部はたとえば青色である。線分ＦＧ２はたとえば赤色であり、図形ＦＧ１、ＦＧ３、およびＦＧ４の外枠はたとえば赤色である。
【００７５】
図５（ｂ）を参照して、画像形成装置１は、固定記憶部２０などから画像ＩＭを入手すると、画像ＩＭから各図形の輪郭ＯＬを抽出することにより、画像を走査可能な状態に変換する。
【００７６】
図５（ｃ）を参照して、画像形成装置１は、任意の開始点ＳＴ１から、図５中右方向に向かって輪郭ＯＬの１回目の走査を開始する。画像形成装置１は、開始点ＳＴ１を固定記憶部２０に記憶する。
【００７７】
画像形成装置１は、輪郭ＯＬの走査の際に分岐点Ｐ１１を発見し、分岐点Ｐ１１の位置と、分岐点Ｐ１１から分岐した経路Ｌ１１ＡおよびＬ１１Ｂとを固定記憶部２０に記憶する。また、画像形成装置１は、経路Ｌ１１ＡおよびＬ１１Ｂのうち、進行方向に向かって最も右側の位置に存在する経路である経路Ｌ１１Ａを、走査する経路として選択する。
【００７８】
画像形成装置１は、輪郭ＯＬの走査の際に開始点ＳＴ１を発見する。この場合画像形成装置１は、輪郭走査部１０３が走査した軌跡により構成された図形が閉曲線であると判定する。
【００７９】
図５（ｄ）を参照して、画像形成装置１は、走査した軌跡により構成された図形ＦＧ５１を抽出し、固定記憶部２０に記憶する。これにより、１回目の走査が終了する。
【００８０】
続いて画像形成装置１は、未走査経路を有する任意の分岐点である分岐点Ｐ１１を開始点ＳＴ２として、未走査経路である経路Ｌ１１Ｂに沿って（図５中右方向に向かって）輪郭ＯＬの２回目の走査を開始する。
【００８１】
図６（ａ）を参照して、画像形成装置１は、輪郭ＯＬの走査の際に分岐点Ｐ２１を発見する。この場合画像形成装置１は、分岐点Ｐ２１の位置と、分岐点Ｐ２１から分岐した経路Ｌ２１ＡおよびＬ２１Ｂとを固定記憶部２０に記憶する。また、画像形成装置１は、経路Ｌ２１ＡおよびＬ２１Ｂのうち、進行方向に向かって最も右側の位置に存在する経路である経路Ｌ２１Ａを、走査する経路として選択する。
【００８２】
図６（ｂ）を参照して、画像形成装置１は、輪郭ＯＬの走査の際に分岐点Ｐ２２を発見する。この場合画像形成装置１は、分岐点Ｐ２２の位置と、分岐点Ｐ２２から分岐した経路Ｌ２２ＡおよびＬ２２Ｂとを固定記憶部２０に記憶する。また、画像形成装置１は、経路Ｌ２２ＡおよびＬ２２Ｂのうち、進行方向に向かって最も右側の位置に存在する経路である経路Ｌ２２Ａを、走査する経路として選択する。
【００８３】
図６（ｃ）を参照して、画像形成装置１は、輪郭ＯＬの走査の際に分岐点Ｐ２３を発見する。この場合画像形成装置１は、分岐点Ｐ２３の位置と、分岐点Ｐ２３から分岐した経路Ｌ２３ＡおよびＬ２３Ｂとを固定記憶部２０に記憶する。また、画像形成装置１は、経路Ｌ２３ＡおよびＬ２３Ｂのうち、進行方向に向かって最も右側の位置に存在する経路である経路Ｌ２３Ａを、走査する経路として選択する。
【００８４】
図６（ｄ）を参照して、輪郭ＯＬの走査の際に分岐点Ｐ２１を再び発見する。このように、２回目の走査にて分岐点を発見した後であって開始点を発見する前に、２回目の走査で発見した分岐点を再び発見した場合、２回目の走査の際の図形の走査方向が狙いの方向とは逆方向（反時計回り）になり、最小単位で図形を抽出できていない状態にある。これは、走査の開始点が閉曲線上ではなく線分上に存在していることに起因している。この場合画像形成装置１は、図形判定部１０６を用いて、２回目に走査した軌跡により構成された図形が線分と閉曲線との組合せであると判定し、２回目の走査を終了し、２回目に走査した軌跡により構成された図形を破棄する。また画像形成装置１は、２回目の走査の際に新たに走査した経路を未走査経路に戻す。
【００８５】
なお、走査にて分岐点を発見した後であって開始点を発見する前に、２回目の走査の際に発見した分岐点を再び発見した場合、画像形成装置１は、上述以外の特定の処理（たとえばユーザーへの通知や、線分と閉曲線との分離など）を行ってもよい。
【００８６】
図７（ａ）を参照して、分岐点Ｐ２１を再び発見した場合、画像形成装置１は、２回目の走査の際に発見した複数の分岐点のうち始めに発見した分岐点である分岐点Ｐ２１を新たな開始点ＳＴ３として、経路Ｌ２１Ｂに沿って３回目の走査を開始する。経路Ｌ２１Ｂは、分岐点Ｐ２１の未走査の経路Ｌ２１ＡおよびＬ２１Ｂのうち、２回目の走査の際に走査した経路Ｌ２１Ａとは異なる経路である。
【００８７】
図７（ｂ）を参照して、画像形成装置１は、輪郭ＯＬの走査の際に分岐点Ｐ２３およびＰ２２を発見した後（分岐点Ｐ２３およびＰ２２の位置、ならびに分岐点Ｐ２３およびＰ２２から分岐した経路は、固定記憶部２０に既に記憶されているので、新たに記憶させない）、開始点ＳＴ３を発見する。この場合画像形成装置１は、走査した軌跡により構成された図形が閉曲線であると判定する。
【００８８】
図７（ｃ）を参照して、画像形成装置１は、走査した軌跡により構成された図形ＦＧ５２を抽出し、固定記憶部２０に記憶する。これにより、３回目の走査が終了する。
【００８９】
図７（ｄ）を参照して、画像形成装置１は、図形を抽出した場合において、未走査経路を有する任意の分岐点である分岐点Ｐ２３を新たな開始点ＳＴ４として、未走査経路である経路Ｌ２１Ｃに沿って（図７中右方向に向かって）輪郭ＯＬの４回目の走査を開始する。
【００９０】
図７（ｅ）を参照して、画像形成装置１は、輪郭ＯＬの走査の際に開始点ＳＴ４を発見する。この場合画像形成装置１は、走査した軌跡により構成された図形が閉曲線であると判定する。
【００９１】
画像形成装置１は、走査した軌跡により構成された図形ＦＧ５３を抽出し、固定記憶部２０に記憶する。これにより、４回目の走査が終了する。
【００９２】
図形ＦＧ５３の抽出後、固定記憶部２０に記憶した経路の中には図形を抽出できる経路が残っていない。この場合画像形成装置１は、抽出する図形が無くなったと判断し、図形として抽出していない輪郭である分岐点Ｐ１１と分岐点Ｐ２１とを結ぶ直線を線分ＦＧ５４として抽出する。以上により、図形の抽出が完了する。
【００９３】
図８は、本発明の第２の実施の形態における画像形成装置の動作を示すフローチャートである。
【００９４】
図８を参照して、このフローチャートは、ステップＳ１０９の処理の後に実行する処理が、図４に示す第１の実施の形態の場合のフローチャートと異なっている。
【００９５】
ステップＳ１０９において、発見した分岐点が、固定記憶部２０に既に記憶した分岐点であると判別した場合（Ｓ１０９でＹＥＳ）、制御部１０は、発見した分岐点が、現在の（今回の）走査で既に発見した分岐点であるか否かを判別する（Ｓ２０１）。
【００９６】
ステップＳ２０１において、現在の走査で既に発見した分岐点であると判別した場合（Ｓ２０１でＹＥＳ）、制御部１０は、今回走査した軌跡により構成された図形が線分と閉曲線との組合せであると判定し、今回走査した軌跡により構成された図形を破棄し、今回の走査を終了する（Ｓ２０３）。続いて制御部１０は、直近で終了した走査の際に発見した複数の分岐点のうち始めに発見した分岐点に開始点を移動し（Ｓ２０５）、次の走査を開始し（Ｓ２０７）、ステップＳ１０７の処理へ進む。
【００９７】
ステップＳ２０１において、現在の走査で既に発見した分岐点でないと判別した場合（Ｓ２０１でＮＯ）、制御部１０はステップＳ１１１の処理へ進む。
【００９８】
なお、本実施の形態の画像形成装置の構成および上述以外の動作については、第１の実施の形態の場合と同様であるので、その説明は繰り返さない。
【００９９】
［第３の実施の形態］
【０１００】
図９および図１０は、本発明の第３の実施の形態において、画像形成装置が行う図形の抽出方法を説明する図である。
【０１０１】
図９（ａ）を参照して、図形抽出の対象となる画像ＩＭは、互いに隣接した図形ＦＧ１、ＦＧ２、およびＦＧ３を含んでいる。図形ＦＧ１、ＦＧ２、およびＦＧ３の各々は、正方形の形状を有している。図形ＦＧ１の内部はたとえば赤色であり、図形ＦＧ２の内部はたとえば緑色であり、図形ＦＧ３の内部はたとえば青色である。図形ＦＧ１、ＦＧ２、およびＦＧ３の外枠はたとえば黒色である。
【０１０２】
図９（ｂ）を参照して、画像形成装置１は、固定記憶部２０などから画像ＩＭを入手すると、画像ＩＭから各図形の輪郭ＯＬを抽出することにより、画像を走査可能な状態に変換する。
【０１０３】
画像形成装置１は、任意の開始点ＳＴ１から、図９中右方向に向かって輪郭ＯＬの１回目の走査を開始する。画像形成装置１は、開始点ＳＴ１を固定記憶部２０に記憶する。
【０１０４】
図９（ｃ）を参照して、画像形成装置１は、輪郭ＯＬの走査の際に分岐点Ｐ１１、Ｐ１２、およびＰ１３を発見し、分岐点Ｐ１１、Ｐ１２、およびＰ１３の各々の位置と、分岐点Ｐ１１、Ｐ１２、およびＰ１３の各々から分岐した経路とを固定記憶部２０に記憶する。また、画像形成装置１は、分岐点Ｐ１１、Ｐ１２、およびＰ１３の各々において、進行方向に向かって最も右側の位置に存在する経路を走査する経路として選択する。
【０１０５】
画像形成装置１は、輪郭ＯＬの走査の際に開始点ＳＴ１を発見する。この場合画像形成装置１は、輪郭走査部１０３が走査した軌跡により構成された図形が閉曲線であると判定する。
【０１０６】
図９（ｄ）を参照して、画像形成装置１は、走査した軌跡により構成された図形ＦＧ５１を抽出し、固定記憶部２０に記憶する。これにより、１回目の走査が終了する。
【０１０７】
続いて画像形成装置１は、１回目の走査の際に発見した分岐点Ｐ１１、Ｐ１２、およびＰ１３のうち、１回目の走査の際に始めに発見した分岐点Ｐ１１を、２回目の走査の開始点ＳＴ２とする。画像形成装置１は、分岐点Ｐ１１から分岐した経路のうち未走査経路である経路Ｌ１１Ａに沿って、２回目の走査を開始する。
【０１０８】
なお画像形成装置は、１回目の走査の際に始めに発見した分岐点が未走査経路を有していない場合において、１回目の走査の際に発見した分岐点の中に未走査経路を有している分岐点があるときは、１回目の走査の際に発見した未走査経路を有している分岐点のうち、１回目の走査の際に最も早く発見した分岐点を新たな開始点として、２回目の走査を行ってもよい。
【０１０９】
さらに画像形成装置１は、今回の走査（直近で終了した走査）の際に発見した分岐点の中に、未走査経路を有している分岐点が無い場合に、今回の走査よりも前に行った走査の中から、未走査経路を有している分岐点を発見した最新の走査を特定し、特定した走査の際に発見した、未走査経路を有している分岐点を新たな開始点として、次の走査を行ってもよい。
【０１１０】
図１０（ａ）を参照して、画像形成装置１は、輪郭ＯＬの走査の際に分岐点Ｐ２１およびＰ１２を発見し、分岐点Ｐ２１の位置と、分岐点Ｐ２１から分岐した経路とを固定記憶部２０に記憶する（分岐点Ｐ１２の位置、および分岐点Ｐ１２から分岐した経路は、固定記憶部２０に既に記憶されているので、新たに記憶させない）。また、画像形成装置１は、分岐点Ｐ２１およびＰ１２の各々において、進行方向に向かって最も右側の位置に存在する経路を、走査する経路として選択する。
【０１１１】
画像形成装置１は、輪郭ＯＬの走査の際に開始点ＳＴ２を発見する。この場合画像形成装置１は、図形判定部１０６を用いて、輪郭走査部１０３が走査した軌跡により構成された図形が閉曲線であると判定する。
【０１１２】
図１０（ｂ）を参照して、画像形成装置１は、走査した軌跡により構成された図形ＦＧ５２を抽出し、固定記憶部２０に記憶する。これにより、２回目の走査が終了する。
【０１１３】
続いて画像形成装置１は、２回目の走査の際に発見した分岐点Ｐ２１およびＰ１２のうち、２回目の走査の際に始めに発見した分岐点Ｐ２１を、３回目の走査の開始点ＳＴ３とする。画像形成装置１は、分岐点Ｐ２１から分岐した経路のうち未走査経路である経路Ｌ２１Ａに沿って、３回目の走査を開始する。
【０１１４】
図１０（ｃ）を参照して、画像形成装置１は、輪郭ＯＬの走査の際に分岐点Ｐ１３およびＰ１２を発見した後（分岐点Ｐ１３およびＰ１２の位置、ならびに分岐点Ｐ１３およびＰ１２の各々から分岐した経路は、固定記憶部２０に既に記憶されているので、新たに記憶させない）、開始点ＳＴ３を発見する。この場合画像形成装置１は、走査した軌跡により構成された図形が閉曲線であると判定する。
【０１１５】
画像形成装置１は、走査した軌跡により構成された図形ＦＧ５３を抽出し、固定記憶部２０に記憶する。これにより、３回目の走査が終了する。
【０１１６】
図形ＦＧ５３の抽出後、固定記憶部２０に記憶した経路の中には図形を抽出できる経路が残っていない。この場合画像形成装置１は、抽出する図形が無くなったと判断し、図形として抽出していない輪郭が存在する場合には、それを線分として抽出する。以上により、図形の抽出が完了する。
【０１１７】
図１１は、本発明の第３の実施の形態における、図４のステップＳ１１９の開始点決定処理のサブルーチンである。
【０１１８】
図１１を参照して、本実施の形態では、開始点決定処理として次の処理を行う。制御部１０は、今回の走査（直近で終了した走査）の際に始めに発見した分岐点が未走査経路を有しているか否かを判別する（Ｓ３０１）。
【０１１９】
ステップＳ３０１において、今回の走査の際に始めに発見した分岐点が未走査経路を有していると判別した場合（Ｓ３０１でＹＥＳ）、制御部１０は、今回の走査の際に始めに発見した分岐点を新たな開始点に決定し（Ｓ３０３）、リターンする。
【０１２０】
ステップＳ３０１において、今回の走査の際に始めに発見した分岐点が未走査経路を有していないと判別した場合（Ｓ３０１でＮＯ）、制御部１０は、今回の走査の際に発見した複数の分岐点の中に、未走査経路を有している分岐点があるか否かを判別する（Ｓ３０５）。
【０１２１】
ステップＳ３０５において、今回の走査の際に発見した複数の分岐点の中に、未走査経路を有している分岐点があると判別した場合（Ｓ３０５でＹＥＳ）、制御部１０は、
今回の走査の際に発見した、未走査経路を有している分岐点のうち、今回の走査の際に最も早く発見した分岐点を新たな開始点に決定し（Ｓ３０７）、リターンする。
【０１２２】
ステップＳ３０５において、今回の走査の際に発見した複数の分岐点の中に、未走査経路を有している分岐点が無いと判別した場合（Ｓ３０５でＮＯ）、制御部１０は、今回の走査よりも前に行った走査のうち、未走査経路を有している分岐点を発見した最新の走査を特定する（Ｓ３０９）。続いて制御部１０は、特定した走査の際に発見した、未走査経路を有している分岐点を新たな開始点に決定し（Ｓ３１１）、リターンする。
【０１２３】
なお、本実施の形態の画像形成装置の構成および上述以外の動作については、第１の実施の形態の場合と同様であるので、その説明は繰り返さない。
【０１２４】
［第４の実施の形態］
【０１２５】
図１２〜図１５は、本発明の第４の実施の形態において、画像形成装置が行う図形の抽出方法を説明する図である。なお図１２（ｂ）および（ｃ）、図１３（ｂ）および（ｃ）、図１４（ｂ）および（ｃ）、ならびに図１５（ｂ）および（ｃ）は、固定記憶部２０に記憶されている情報を模式的に示している。
【０１２６】
図１２（ａ）を参照して、ここでは、画像形成装置１が、互いに隣接した４つの正方形からなる輪郭ＯＬを画像から抽出した場合を想定する。画像形成装置１は、任意の開始点ＳＴ１から、図１２中右方向に向かって輪郭ＯＬの１回目の走査を開始する。画像形成装置１は、輪郭ＯＬの走査の際に分岐点Ｐ１１、Ｐ１２、およびＰ１３を発見し、その後開始点ＳＴ１を発見する。
【０１２７】
分岐点Ｐ１３を発見した後であって開始点ＳＴ１を発見する前には、固定記憶部２０には、図１２（ｂ）に示すように、開始点ＳＴ１の位置の情報と、分岐点Ｐ１１、Ｐ１２、およびＰ１３の各々の位置の情報と、分岐点Ｐ１１、Ｐ１２、およびＰ１３の各々から分岐した経路Ｌ１１Ａ、Ｌ１１Ｂ、Ｌ１２Ａ、Ｌ１２Ｂ、Ｌ１３Ａ、およびＬ１３Ｂの情報とが記憶されている。
【０１２８】
画像形成装置１は、開始点ＳＴ１を発見すると、走査した軌跡により構成された図形が閉曲線であると判定し、走査した軌跡により構成された図形ＦＧ５１を抽出し、固定記憶部２０に記憶する。これにより、１回目の走査が終了する。画像形成装置１は、図形ＦＧ５１を抽出した場合に、図１２（ｃ）に示すように、固定記憶部２０に記憶した経路の情報うち、図形ＦＧ５１を構成する経路である経路Ｌ１１Ａ、Ｌ１２Ａ、およびＬ１３Ａの情報を消去する。また画像形成装置１は、図形ＦＧ５１を抽出した場合に、図形ＦＧ５１を抽出した走査の開始点ＳＴ１の位置の情報を消去してもよい。
【０１２９】
図１３（ａ）を参照して、次に画像形成装置１は、分岐点Ｐ１１を開始点ＳＴ２として、図１３中右方向に向かって（経路Ｌ１１Ｂに沿って）輪郭ＯＬの２回目の走査を開始する。画像形成装置１は、輪郭ＯＬの走査の際に分岐点Ｐ２１、Ｐ２２、およびＰ１２を発見し、その後開始点ＳＴ２を発見する。
【０１３０】
分岐点Ｐ２２を発見した後であって開始点ＳＴ２を発見する前には、固定記憶部２０には、図１３（ｂ）に示すように、開始点ＳＴ２の位置の情報と、分岐点Ｐ２１およびＰ２２の各々の位置の情報と、分岐点Ｐ２１およびＰ２２の各々から分岐した経路Ｌ２１Ａ、Ｌ２１Ｂ、Ｌ２２Ａ、およびＬ２２Ｂの情報とが新たに記憶されている（経路Ｌ２２Ａと経路Ｌ１２Ｂとは同一の経路である）。
【０１３１】
画像形成装置１は、走査した軌跡により構成された図形が閉曲線であると判定し、走査した軌跡により構成された図形ＦＧ５２を抽出し、固定記憶部２０に記憶する。これにより、２回目の走査が終了する。画像形成装置１は、図形ＦＧ５２を抽出した場合に、図１３（ｃ）に示すように、固定記憶部２０に記憶した経路の情報うち、図形ＦＧ５２を構成する経路である経路Ｌ１１Ｂ、Ｌ２１Ａ、Ｌ２２Ａ、およびＬ１２Ｂの情報を消去する。また画像形成装置１は、未走査経路を有さなくなった分岐点（経路が全て消去された分岐点）である分岐点Ｐ１１およびＰ１２の位置の情報を消去してもよい。さらに画像形成装置１は、図形ＦＧ５２を抽出した場合に、図形ＦＧ５２を抽出した走査の開始点ＳＴ２の位置の情報を消去してもよい。
【０１３２】
図１４（ａ）を参照して、次に画像形成装置１は、分岐点Ｐ２１を開始点ＳＴ３として、図１４中右方向に向かって（経路Ｌ２１Ｂに沿って）輪郭ＯＬの３回目の走査を開始する。画像形成装置１は、輪郭ＯＬの走査の際に分岐点Ｐ３１およびＰ２２を発見し、その後開始点ＳＴ３を発見する。
【０１３３】
分岐点Ｐ３１を発見した後であって開始点ＳＴ３を発見する前には、固定記憶部２０には、図１４（ｂ）に示すように、開始点ＳＴ３の位置の情報と、分岐点Ｐ３１の位置の情報と、分岐点Ｐ３１から分岐した経路Ｌ３１ＡおよびＬ３１Ｂの情報とが新たに記憶されている（経路Ｌ３１Ａと経路Ｌ２２Ｂとは同一の経路である）。
【０１３４】
画像形成装置１は、走査した軌跡により構成された図形が閉曲線であると判定し、走査した軌跡により構成された図形ＦＧ５３を抽出し、固定記憶部２０に記憶する。これにより、３回目の走査が終了する。画像形成装置１は、図形ＦＧ５３を抽出した場合に、図１４（ｃ）に示すように、固定記憶部２０に記憶した経路の情報うち、図形ＦＧ５３を構成する経路である経路Ｌ２１Ｂ、Ｌ３１Ａ、およびＬ２２Ｂの情報を消去する。また画像形成装置１は、未走査経路を有さなくなった分岐点Ｐ２１およびＰ２２の位置の情報を消去してもよい。さらに画像形成装置１は、図形ＦＧ５３を抽出した場合に、図形ＦＧ５３を抽出した走査の開始点ＳＴ３の位置の情報を消去してもよい。
【０１３５】
図１５（ａ）を参照して、次に画像形成装置１は、分岐点Ｐ３１を開始点ＳＴ４として、図１５中左方向に向かって（経路Ｌ３１Ｂに沿って）輪郭ＯＬの４回目の走査を開始する。画像形成装置１は、輪郭ＯＬの走査の際に分岐点Ｐ１３、Ｐ１２、およびＰ２２を発見し、その後開始点ＳＴ４を発見する。
【０１３６】
４回目の走査を開始してから開始点ＳＴ４を発見する前には、固定記憶部２０には、図１５（ｂ）に示すように、開始点ＳＴ４の位置の情報が新たに記憶されている。
【０１３７】
画像形成装置１は、走査した軌跡により構成された図形が閉曲線であると判定し、走査した軌跡により構成された図形ＦＧ５４を抽出し、固定記憶部２０に記憶する。これにより、４回目の走査が終了する。画像形成装置１は、図形ＦＧ５４を抽出した場合に、図１５（ｃ）に示すように、固定記憶部２０に記憶した経路の情報うち、図形ＦＧ５３を構成する経路である経路Ｌ３１ＢおよびＬ１３Ｂの情報を消去する。また画像形成装置１は、未走査経路を有さなくなった分岐点Ｐ１３およびＰ３１の位置の情報を消去してもよい。さらに画像形成装置１は、図形ＦＧ５４を抽出した場合に、図形ＦＧ５４を抽出した走査の開始点ＳＴ４の位置の情報を消去してもよい。その結果、固定記憶部２０に記憶されている未走査経路の情報は無くなる。以上により、図形の抽出が完了する。
【０１３８】
図１６は、本発明の第４の実施の形態における画像形成装置の動作を示すフローチャートである。
【０１３９】
図１６を参照して、このフローチャートは、ステップＳ１１５の処理の後であってステップＳ１１７の処理の前に、ステップＳ４０１の処理を実行する点において、図４に示す第１の実施の形態の場合のフローチャートと異なっている。
【０１４０】
ステップＳ１１５の処理に続いて、ステップＳ４０１において、制御部１０は、走査済の経路の情報、および未走査経路を有さなくなった分岐点の位置の情報を消去し（Ｓ４０１）、ステップＳ１１７の処理へ進む。
【０１４１】
なお、本実施の形態の画像形成装置の構成および上述以外の動作については、第１の実施の形態の場合と同様であるので、その説明は繰り返さない。
【０１４２】
［実施の形態の効果］
【０１４３】
第１〜第４の実施の形態によれば、画像形成装置は、新たな分岐点を発見した場合、その分岐点から分岐した複数の経路のうち進行方向に向かって特定の位置（方向）に存在する経路を常に選択するので、一つの図形の輪郭を時計回り（または反時計回り）に走査することができ、最小単位で図形を抽出することができる。加えて、図形を抽出した場合に、前回発見した分岐点を新たな開始点とし、新たな開始点とした分岐点から分岐した複数の経路のうち、未走査経路を走査するので、別の図形についても最小単位で抽出することができる。その結果、複数の図形を含む画像からそれぞれの図形を適切に抽出することができる。
【０１４４】
図１７は、本発明の第１〜第４の実施の形態において抽出される図形を模式的に示す図である。
【０１４５】
図１７（ａ）を参照して、画像ＩＭが、互いに隣接する２つの閉曲線の図形ＦＧ１１およびＦＧ１２を含んでいる場合には、画像形成装置１は、図形ＦＧ６１およびＦＧ６２を画像ＩＭから抽出する。
【０１４６】
図１７（ｂ）を参照して、画像ＩＭが２つの閉曲線の図形ＦＧ１３および図形ＦＧ１５と、図形ＦＧ１３およびＦＧ１５を接続する線分ＦＧ１４とを含んでいる場合には、画像形成装置１は、図形ＦＧ６３、線分ＦＧ６４、および図形ＦＧ６５を画像ＩＭから抽出する。
【０１４７】
図１７（ｃ）を参照して、画像ＩＭが閉曲線の図形ＦＧ１６と、図形ＦＧ１６に内包された閉曲線の図形ＦＧ１７とを含んでいる場合には、画像形成装置１は、図形ＦＧ６６およびＦＧ６７を画像ＩＭから抽出する。
【０１４８】
また、走査の開始位置が閉曲線上ではなく線分上に存在している場合、図形の走査方向が狙いの方向とは逆方向（反時計回り）になり、最小単位で図形を抽出することができなくなることがある。特に第２の実施の形態では、走査にて分岐点を発見した後であって開始点を発見する前に、今回の走査の際に発見した分岐点を再び発見した場合には、今回走査した軌跡により構成された図形を破棄する。そして、破棄した走査の際に発見した複数の分岐点のうち始めに発見した分岐点である分岐点を新たな開始点として次の走査を開始する。これにより、画像に含まれる図形が、線分と閉曲線との組合せにより構成されている場合であっても、線分と閉曲線とを分離して抽出することができる。
【０１４９】
また、図形を抽出した後、次の走査を開始する場合には、適切な分岐点を開始点として選択しないと、図形の走査方向が狙いの方向とは逆方向（反時計回り）になり、最小単位で図形を抽出することができなくなることがある。複数の図形が互いに隣接している場合には、複数の図形全体の外輪郭のみを走査し、その結果、互いに分離されていない状態で複数の図形を一度に抽出するおそれもある。特に第３の実施の形態では、今回の走査の際に始めに発見された分岐点を開始点として、次の走査が開始される。今回の走査の際の開始点が複数の図形全体の外輪郭上に存在している場合には、今回の走査の際に始めに発見された分岐点もまた、図形の外輪郭上に存在している。したがって、第３の実施の形態によれば、常に図形の外輪郭上を開始点として走査を開始することができ、図形の走査方向が狙いの方向とは逆方向になるのを抑止することができる。
【０１５０】
さらに、第４の実施の形態によれば、図形を抽出する度に、走査済（選択済）の経路の情報を削除するので、全ての分岐後の経路を記憶しておく場合に比べて、固定記憶部の記憶領域の空き容量を増やすことができる。その結果、図形の抽出のために事前に確保しておくべき記憶領域の容量を少なくすることができる。
【０１５１】
［その他］
【０１５２】
上述の実施の形態は互いに組み合わせられてもよい。たとえば、第２の実施の形態の構成である、走査にて分岐点を発見した後であって開始点を発見する前に、走査の際に発見した分岐点を再び発見した場合に、走査した軌跡により構成された図形を破棄する構成と、第４の実施の形態の構成である、図形を抽出した場合にその図形を構成する経路を削除する構成とを組み合わせてもよい。また、第３の実施の形態の構成である、走査の際に始めに発見された分岐点を開始点として、次の走査を開始する構成と、第４の実施の形態の構成である、図形を抽出した場合にその図形を構成する経路の情報を消去する構成とを組み合わせてもよい。
【０１５３】
上述の実施の形態における処理は、ソフトウェアにより行なっても、ハードウェア回路を用いて行なってもよい。また、上述の実施の形態における処理を実行するプログラムを提供することもできるし、そのプログラムをＣＤ−ＲＯＭ、フレキシブルディスク、ハードディスク、ＲＯＭ、ＲＡＭ、メモリカードなどの記録媒体に記録してユーザーに提供することにしてもよい。プログラムは、ＣＰＵなどのコンピューターにより実行される。また、プログラムはインターネットなどの通信回線を介して、装置にダウンロードするようにしてもよい。
【０１５４】
上述の実施の形態は、すべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【符号の説明】
【０１５５】
１  画像形成装置
１０  制御部
２０  固定記憶部
３０  画像読取部
４０  画像形成部
５０  ネットワークＩ／Ｆ
６０  操作パネル
１０１  画像記憶部
１０２  前処理部
１０３  輪郭走査部
１０４  分岐点記憶部
１０５  進路選択部
１０６  図形判定部
１０７  図形記憶部
ＦＧ１，ＦＧ２，ＦＧ３，ＦＧ４，ＦＧ１１，ＦＧ１２，ＦＧ１３，ＦＧ１４，ＦＧ１５，ＦＧ１６，ＦＧ１７，ＦＧ５１，ＦＧ５２，ＦＧ５３，ＦＧ５４，ＦＧ６１，ＦＧ６２，ＦＧ６３，ＦＧ６４，ＦＧ６５，ＦＧ６６，ＦＧ６７  図形または線分
ＩＭ  画像
Ｌ１１Ａ，Ｌ１１Ｂ，Ｌ１１Ｃ，Ｌ１２Ａ，Ｌ１２Ｂ，Ｌ１３Ａ，Ｌ１３Ｂ，Ｌ２１Ａ，Ｌ２１Ｂ，Ｌ２１Ｃ，Ｌ２２Ａ，Ｌ２２Ｂ，Ｌ２３Ａ，Ｌ２３Ｂ，Ｌ３１Ａ，Ｌ３１Ｂ  経路
ＯＬ  輪郭
Ｐ１１，Ｐ１２，Ｐ１３，Ｐ２１，Ｐ２２，Ｐ２３，Ｐ３１  分岐点
ＳＴ１，ＳＴ２，ＳＴ３，ＳＴ４  開始点
【図１】
2015060441.tif 000003
【図２】
2015060441.tif 000004
【図３】
2015060441.tif 000005
【図４】
2015060441.tif 000006
【図５】
2015060441.tif 000007
【図６】
2015060441.tif 000008
【図７】
2015060441.tif 000009
【図８】
2015060441.tif 000010
【図９】
2015060441.tif 000011
【図１０】
2015060441.tif 000012
【図１１】
2015060441.tif 000013
【図１２】
2015060441.tif 000014
【図１３】
2015060441.tif 000015
【図１４】
2015060441.tif 000016
【図１５】
2015060441.tif 000017
【図１６】
2015060441.tif 000018
【図１７】
2015060441.tif 000019