(57)【特許請求の範囲】
【請求項１】
デジタル画像上で指定された点が閉領域を形成する図形内にあるか否かを判定する画像処理方法であって、前記図形の閉ループを追跡する追跡点の方向を、前記追跡点から右の水平方向、左の水平方向、上方向、下方向、斜め右上の方向、斜め左上の方向、斜め右下の方向、斜め左下の方向の内の何れかの方向に分類し、前記上方向、斜め右上の方向、斜め左上の方向に対して、追跡点の方向データとして値１を付与し、前記左右の水平方向に対して、追跡点の方向データとして値０を付与し、前記下方向、斜め右下の方向、斜め左下の方向に対して、追跡点の方向データとして値−１を付与し、前記図形の閉ループを追跡する追跡点が、前記指定された点を端点とする半直線と前記図形とが接する接点、前記図形の角を含む、前記半直線と前記図形との交点であるか否かを判定し、交点と判定されたとき、前記交点における方向データと前記交点より一つ前の追跡点における方向データとを加算し、全ての交点について前記加算した総和が負であるとき、前記指定された点は前記図形内にあると判定し、前記加算した総和が０以上であるとき、前記指定された点は前記図形外にあると判定することを特徴とする画像処理方法。
【請求項２】
デジタル画像上で指定された点が閉領域を形成する図形内にあるか否かを判定する画像処理装置であって、前記図形の閉ループを追跡する追跡点の方向を、前記追跡点から右の水平方向、左の水平方向、上方向、下方向、斜め右上の方向、斜め左上の方向、斜め右下の方向、斜め左下の方向の内の何れかの方向に分類し、前記上方向、斜め右上の方向、斜め左上の方向に対して、追跡点の方向データとして値１を付与し、前記左右の水平方向に対して、追跡点の方向データとして値０を付与し、前記下方向、斜め右下の方向、斜め左下の方向に対して、追跡点の方向データとして値−１を付与し、前記図形の閉ループを追跡する追跡点が、前記指定された点を端点とする半直線と前記図形とが接する接点、前記図形の角を含む、前記半直線と前記図形との交点であるか否かを判定し、交点と判定されたとき、前記交点における方向データと前記交点より一つ前の追跡点における方向データとを加算し、全ての交点について前記加算した総和が負であるとき、前記指定された点は前記図形内にあると判定し、前記加算した総和が０以上であるとき、前記指定された点は前記図形外にあると判定する手段を備えたことを特徴とする画像処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、エリア処理機能を有するデジタル複写機などにおいて、ユーザによって指定された点が図形の内側にあるのか外側にあるのかを判定する画像処理方法および装置に関する。
【０００２】
【従来の技術】
デジタル複写機などの画像処理装置においては、従来から、原稿の任意の領域（エリア）を指定し、指定されたエリアの内側または外側の画像を加工処理（例えば、指定したエリア内の色を他の色に変えるなど）することが行われている。
【０００３】
このとき、指定した点が図形の内側にあるのか外側にあるのかを判定する必要がある。このような判定方法として、例えば特開平７−７８１９２号公報に記載された方法がある。この方法では、判定対象となる点から半直線を延ばし、半直線と図形との交点の数を求め、その数を基に判定対象となる点がその図形の内側にあるか外側にあるかを判定している。
【０００４】
【発明が解決しようとする課題】
しかし、上記した方法では、交点が図形と接していたり、交点が図形の角になるような場合は半直線の方向を変えて、再び交点を求め、その交点が図形と接してなく、かつ交点が図形の角とならない方向になるまで、その方向を変えて交点を求める処理を続けなければならず、判定に要する時間がかかるという問題がある。
【０００５】
本発明の目的は、交点が接点である場合や交点が図形の角である場合も含めて交点計算を行い、指定された点が図形の内側か外側かを精度よく判定する画像処理方法および装置を提供することにある。
【０００６】
【課題を解決するための手段】
前記目的を達成するために、請求項１記載の発明では、デジタル画像上で指定された点が閉領域を形成する図形内にあるか否かを判定する画像処理方法であって、前記図形の閉ループを追跡する追跡点の方向を、前記追跡点から右の水平方向、左の水平方向、上方向、下方向、斜め右上の方向、斜め左上の方向、斜め右下の方向、斜め左下の方向の内の何れかの方向に分類し、前記上方向、斜め右上の方向、斜め左上の方向に対して、追跡点の方向データとして値１を付与し、前記左右の水平方向に対して、追跡点の方向データとして値０を付与し、前記下方向、斜め右下の方向、斜め左下の方向に対して、追跡点の方向データとして値−１を付与し、前記図形の閉ループを追跡する追跡点が、前記指定された点を端点とする半直線と前記図形とが接する接点、前記図形の角を含む、前記半直線と前記図形との交点であるか否かを判定し、交点と判定されたとき、前記交点における方向データと前記交点より一つ前の追跡点における方向データとを加算し、全ての交点について前記加算した総和が負であるとき、前記指定された点は前記図形内にあると判定し、前記加算した総和が０以上であるとき、前記指定された点は前記図形外にあると判定することを特徴としている。
【０００７】
請求項２記載の発明では、デジタル画像上で指定された点が閉領域を形成する図形内にあるか否かを判定する画像処理装置であって、前記図形の閉ループを追跡する追跡点の方向を、前記追跡点から右の水平方向、左の水平方向、上方向、下方向、斜め右上の方向、斜め左上の方向、斜め右下の方向、斜め左下の方向の内の何れかの方向に分類し、前記上方向、斜め右上の方向、斜め左上の方向に対して、追跡点の方向データとして値１を付与し、前記左右の水平方向に対して、追跡点の方向データとして値０を付与し、前記下方向、斜め右下の方向、斜め左下の方向に対して、追跡点の方向データとして値−１を付与し、前記図形の閉ループを追跡する追跡点が、前記指定された点を端点とする半直線と前記図形とが接する接点、前記図形の角を含む、前記半直線と前記図形との交点であるか否かを判定し、交点と判定されたとき、前記交点における方向データと前記交点より一つ前の追跡点における方向データとを加算し、全ての交点について前記加算した総和が負であるとき、前記指定された点は前記図形内にあると判定し、前記加算した総和が０以上であるとき、前記指定された点は前記図形外にあると判定する手段を備えたことを特徴としている。
【０００８】
【発明の実施の形態】
以下、本発明の一実施例を図面を用いて具体的に説明する。
図１は、本発明の実施例の構成を示す。図において、画像入力部１は、読み取った原稿をデジタル画像信号に変換する。色補正部６は、表色系の画像データ（ＲＧＢ）を印字系の画像データ（ＹＭＣＫ）に変換する。画像出力部７では、出力機器に応じた階調処理を施し、プリンタ等の出力機器に画像を出力させる。
また、最大値算出部２は、入力された画像データ（ＲＧＢ）から最大の信号ＭＡＸ（ＲＧＢ）を算出する。２値化部３は、ＭＡＸ（ＲＧＢ）に対し、所定の閾値で２値化を行い、太らせ処理を行った後、芯線化を行い、より精度の良い追跡ができるように前処理をする。閉ループ追跡部４は、ポインタデバイスなどによりユーザから指定された点から時計周りにループを追跡し、追跡終了後に、ユーザが指定した点がエリアの内外かを判定する。エリア処理部５では、閉ループ認識された部分にどの処理を施すかをタッチパネルなどでユーザに知らせ、ユーザから指示された処理を行い、色補正部６に送る。
【０００９】
図２は、追跡方向データである。時計周りに追跡するよう、追跡データの数値の若い方向に追跡を行う。
【００１０】
図３は、内外判定用方向データである。上方向（図２の方向２、３、４）を１、水平方向（図２の方向１、５）を０、下方向（図２の方向６、７、８）を−１と定義する。
【００１１】
図４は、閉ループ追跡部の処理フローチャートである。以下、図４を参照しながら動作を説明する。
【００１２】
内外判定データ（ｓｕｍｈｏｕｋｏｕ）を０にセットする（ステップ１０１）。次いで、指定点から主走査方向（Ｘ方向）の負の方に移動し、初めて領域に突き当たった点を追跡開始点とする（ステップ１０２）。
【００１３】
続いて、追跡点が交点であるか否かを判定する（ステップ１０３）。ここで、交点は、追跡点と指定点との副走査方向の座標Ｙが同じ場合で、かつその点のＸ座標が指定点のＸ座標よりも大きい場合とする。図５は、指定点、追跡開始点、交点を示す。また、図６は、指定点が領域の内側にある場合の例を示す。図６を用いて処理動作を説明する。
【００１４】
ステップ１０２で追跡開始点が得られ、この追跡点はステップ１０３の判定の結果、交点ではないので、ステップ１０５に進む。ステップ１０５では、方向データが最小座標となる方向に追跡を行う。つまり、追跡開始点では、追跡方向が「３」と「７」があるが、追跡データの少ない「３」の方向に追跡していく。そして、ステップ１０６の追跡が完了するまで、ステップ１０３以下の処理を繰り返す。
【００１５】
例えば、追跡点２１では、追跡方向が「２」となり、また追跡点２２では、最小座標となる方向データは「４」であるが、これは追跡開始点に戻る反時計方向であるので、時計方向である追跡方向「８」の方向に追跡していく。以下同じ方向を進み、最初の交点に至る（ステップ１０３）。ステップ１０４では、交点の演算を行う。交点では、交点での内外判定方向データ（ベクトル）＋交点の一つ前の追跡点での内外判定方向データ（ベクトル）＝ｓｕｍｈｏｕｋｏｕを求める。
【００１６】
これを図５を用いて説明する。交点１２での追跡方向データは「８」であるので、その内外判定用方向データは−１（ｈｏｕｋｏｕ）となる。また、交点１２の一つ前の追跡点１１での追跡方向データは「２」であるので、その内外判定用方向データは１（ｐｒｅｈｏｕｋｏｕ）となる。従って、交点１２のｓｕｍｈｏｕｋｏｕは−１＋１＝０となる。図６の例では、５個の交点があるので、各交点において上記した演算を行い、その和を加算していく。
【００１７】
追跡中、和の値を加算し、追跡が完了すると（ステップ１０６）、ステップ１０７では総和の符号で指定点の内外判定を行う。つまり、ｓｕｍｈｏｕｋｏｕ（総和）が≧０のとき、外側にあると判定し、＜０のとき内側にあると判定する。図６の例では、ｓｕｍｈｏｕｋｏｕ＝−２であるから、指定点が領域の内側にあると判定される。図７の例は、指定点が外側にある場合の各交点での演算を示し、ｓｕｍｈｏｕｋｏｕは０以上となっている。
【００１８】
閉ループ追跡部４での追跡結果、つまり内外判定結果がエリア処理部５に与えられる。エリア処理部５はユーザに対して内外判定結果を図示しない表示手段などによって通知する。ユーザは、該通知によって指定点が領域の内側にあることを確認すると、エリア処理部５に対してエリア処理（例えば、領域内の指定色でペイントするなど）を指示する。エリア処理された画像データは色補正部６で印字などの出力系の画像データに変換され、プリンタなどの画像出力部７から出力される。
【００１９】
なお、上記した追跡アルゴリズムの簡単なソースプログラムを以下に記述する。交点の追跡コードをｃｏｄｅ、交点の一つ前の追跡コードをｂｅｆｏｒｅ  ｃｏｄｅとする。現在の追跡点の座標を（ｘ，ｙ）とし、ユーザによる指定点の座標を（ｐｏｉｎｔ  ｘ，ｐｏｉｎｔ  ｙ）とする。関数ｃａｌｃｕｐｄｏｗｎ（  ）は、図２の追跡方向データを、図３の内外判定用方向データに変換するものである。
【００２０】
0003577191.tif 000002
また、上記したプログラムをＣＤ−ＲＯＭなどに記憶しておき、該プログラムをＣＤ−ＲＯＭから読み出し、汎用のプロセッサ上で実行することにより、マウスなどで指定された点が所定の領域の内側にあるのか外側にあるのかを判定することも可能である。
【００２１】
【発明の効果】
以上、説明したように、本発明によれば、閉領域を形成する図形を追跡完了すると同時に、図形と半直線との交点が接点である場合や交点が図形の角である場合も含めて、指定され点が図形の内か外かを精度よく判定することができる。これにより、閉領域を形成する図形に対して、ユーザが図形の内側の点を指定したとき、閉領域追跡に要する時間と、前記図形における指定点の内外判定に要する時間が短縮される。従って、例えば、閉領域の内部をユーザが指定し、前記領域の内部をエリア加工（ペイント／シングルカラー／色変換など）する場合に要する時間が大幅に短縮される。また、図形を２値化するとき、太らせ処理と芯線化処理を加えているので、カスレをはじめとする低品質な閉領域を形成する図形に対しても、内外判定をより精度よく行うことができる。
【図面の簡単な説明】
【図１】本発明の実施例の構成を示す。
【図２】追跡方向データを示す。
【図３】内外判定用方向データを示す。
【図４】本発明の閉ループ追跡部の処理フローチャートである。
【図５】交点での演算を説明する図である。
【図６】指定された点が領域の内側にある例を示す。
【図７】指定された点が領域の外側にある例を示す。
【符号の説明】
１  画像入力部
２  最大値算出部
３  ２値化部
４  閉ループ追跡部
５  エリア処理部
６  色補正部
７  画像出力部
【図１】
0003577191.tif 000003
【図２】
0003577191.tif 000004
【図３】
0003577191.tif 000005
【図４】
0003577191.tif 000006
【図５】
0003577191.tif 000007
【図６】
0003577191.tif 000008
【図７】
0003577191.tif 000009