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