線画の彩色方法及びプログラム
【課題】
濃淡を含む線画の彩色に際して基線を認識し、その基線からはみ出すことなく彩色する。
【解決手段】
本発明の方法は、線画を含むある領域に対するストロークを受け付けるステップ（Ｓ３０２）と、ストロークされた領域を二値化表現に変換し、線画を構成する線を細線化するステップ（Ｓ３０３）と、グループを定めるステップ（Ｓ３０４）と、始点及び終点を定めるステップ（Ｓ３０４−２）と、枝を削除するステップ（Ｓ３０６）と、コストを求めるステップ（Ｓ３０７）と、前記コストに基づいて、最小コストの線を探索するステップ（Ｓ３０８〜Ｓ３１２−２）と、選択範囲化するステップ（Ｓ３１３）と、彩色するステップ（Ｓ３１４）とを含む。
濃淡を含む線画の彩色に際して基線を認識し、その基線からはみ出すことなく彩色する。
【解決手段】
本発明の方法は、線画を含むある領域に対するストロークを受け付けるステップ（Ｓ３０２）と、ストロークされた領域を二値化表現に変換し、線画を構成する線を細線化するステップ（Ｓ３０３）と、グループを定めるステップ（Ｓ３０４）と、始点及び終点を定めるステップ（Ｓ３０４−２）と、枝を削除するステップ（Ｓ３０６）と、コストを求めるステップ（Ｓ３０７）と、前記コストに基づいて、最小コストの線を探索するステップ（Ｓ３０８〜Ｓ３１２−２）と、選択範囲化するステップ（Ｓ３１３）と、彩色するステップ（Ｓ３１４）とを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、線画における基線を認識し、それに基づいて彩色する線画の彩色方法及びプログラムに関する。
【背景技術】
【０００２】
漫画やアニメーション、イラストなど、一色の線だけで描かれた画である線画に対して彩色を施すことが一般に行われている。図１（ａ）に線画の一例として線画１を示している。我が国で製作された漫画などの白黒の線画に対して、海外向けに彩色することが頻繁に行われている。
【０００３】
ここで、線の色が均一ではなく濃淡を含んでいる場合には、フィルツールなどで直接塗りつぶすことができないという問題がある。例えば図１（ａ）の部分１１を拡大した様子を示す図１（ｂ）、及び図１（ａ）の部分１２を拡大した様子を示す図１（ｃ）からわかるように、線が繋がっておらず隙間が存在している場合には、領域が線により隔てられていないとフィルツールが認識し、ユーザが意図しない部分まで彩色されてしまうことがある。
【０００４】
このような問題を避けるべく、線画に彩色すべき範囲を作成して、その範囲内を塗りつぶすという方法が知られている。しかし、基線とトーンが混在する画像では、線画のみを抽出して彩色すべき範囲を作成することが困難であるという問題がある。また、仮に線画のみを抽出して彩色すべき範囲を作成できたとしても、彩色の作業は通常マウスなどのポインティングデバイスを用いて手作業で行われるため、彩色すべき範囲をはみ出して彩色してしまうという問題がある。色のはみ出た箇所を見つけて修正するには、細い箇所まで目で確認しながら修正する必要があり、効率的ではない。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明の目的は、線画を彩色する際に基線を認識して、その基線からはみ出すことなく彩色できる方法及びコンピュータプログラムを提供することである。
【課題を解決するための手段】
【０００６】
上記課題を解決するため、本発明の方法は、線画を含むある領域に対するストロークを受け付けるストローク受付ステップと、ストロークされた前記領域にある線画を二値化表現に変換し、線画を構成する線を細線化する細線生成ステップと、生成された細線であって互いに接続しているものの集まりを１つのグループと定めるグループ化ステップと、グループに属するピクセルであって、前記ストロークが開始された個所に近いピクセルを始点と定める始点決定ステップと、グループに属するピクセルであって、前記ストロークが終了された個所に近いピクセルを終点と定める終点決定ステップと、グループに属する細線であって終端を含むものを他の細線と交差するところまで削除する削除ステップと、グループに属する細線のコストを求めるコスト計算ステップであって、ここで、前記コストは、二値化表現変換後の細線に含まれるピクセル数を含むいくつかの変数に基づいて計算されるものである、ステップと、前記コストに基づいて、前記始点と前記終点とを結ぶ経路を探索する経路探索ステップと、探索された経路を前記細線生成ステップにより細線化する前の状態に戻して選択範囲とする選択範囲化ステップと、選択範囲化された選択範囲により隔てられた複数の領域のうちの一の領域をある色で彩色する彩色ステップとを含む。
【０００７】
別の実施形態で、前記方法は、前記グループ化ステップにより複数のグループが定められた場合には、該グループ化ステップの後であって、かつ前記削除ステップの前に、前記複数のグループの各々に外接する外接矩形の周囲長と該外接矩形間の距離とを含むいくつかの変数に基づいて、グループ間を接続する線を生成する接続線生成ステップをさらに含み、前記削除ステップは、接続線により接続されていないグループを削除し、生成された接続線を削除しないものとすることができる。
【０００８】
別の実施形態で、前記経路探索ステップは、最小のコストを有する経路を選択するサブステップを含む。
【０００９】
上記問題を解決するため、本発明のコンピュータプログラムは、線画をメモリに読み込む画像読込手段と、前記線画を含むある領域に対するストロークを受け付けるための入力手段と、ストロークされた前記領域にある線画を二値化表現に変換し、線画を構成する線を細線化する細線生成手段と、生成された細線であって互いに接続しているものの集まりを１つのグループと定め、グループに属するピクセルであって、前記ストロークが開始された個所に近いピクセルを始点と定めるとともに、グループに属するピクセルであって、前記ストロークが終了された個所に近いピクセルを終点と定めるグループ化手段と、グループに属する細線であって終端を含むものを他の細線と交差するところまで削除する枝削除手段と、グループに属する細線のコストを求めるコスト計算手段であって、二値化表現変換後の細線に含まれるピクセル数を含むいくつかの変数に基づいてコストを計算するコスト計算手段と、前記コストに基づいて、前記始点と前記終点とを結ぶ経路を探索する経路探索手段と、探索された経路を前記細線生成手段が細線化する前の状態に戻して選択範囲化する手段と、選択範囲化された選択範囲により隔てられた複数の領域のうちの一の領域をある色で彩色する手段とをコンピュータに実現させる。
【００１０】
別の実施形態で、前記コンピュータプログラムは、前記グループ化手段が複数のグループを定めた場合には、前記複数のグループの各々に外接する外接矩形の周囲長と該外接矩形間の距離とを含むいくつかの変数に基づいて、グループ間を接続する線を生成する接続線生成手段をコンピュータにさらに実現させ、接続線により接続されていないグループを削除し、生成された接続線を削除しないように前記枝削除手段をコンピュータに実現させることができる。
【００１１】
別の実施形態で、前記経路探索手段は、最小のコストを有する経路を選択することができる。
【発明の効果】
【００１２】
本発明によれば、濃淡を含む線画に適した彩色方法及びコンピュータプログラムを提供することができる。この方法又はコンピュータプログラムにより、効率的に線画に彩色できるとともに、細かい箇所まで目で確認しながら修正するという今までの作業の手間が省け、なおかつ作業品質の向上を実現することができる。
【発明を実施するための最良の形態】
【００１３】
次に、線画における基線を認識し、それに基づいて彩色する本発明の方法を実施する一つの形態について図面を参照しながら説明する。
【００１４】
まず、図２（ａ）は、線画２を示している。図２（ａ）によれば、線が部分的に途切れていて隙間のあることがわかる。説明の都合上、線画２が図１（ａ）の部分１１あるいは部分１２に対応するものとする。
【００１５】
図３は、線画における基線を認識し、それに基づいて彩色する本発明の方法のフローチャートを示している。まず、ステップＳ３０１から開始し、ステップＳ３０２において線画２をなぞるオペレータの操作を受け付ける。この「なぞる」ことを「ストロークする」とも呼ぶ。ストロークは、マウスなどのポインティングデバイスを用いて行うことができる。図２（ａ）の矢印Ｓは、ストロークの方向と軌跡を表している。このステップＳ３０２によりストロークされた領域を領域３で示している。このストロークされた領域３において基線を認識する流れを以下に説明する。
【００１６】
ステップＳ３０３では、ストロークされた領域３に含まれる濃淡を含んだ線画２を二値化表現に変換、つまり、白と黒の二値での表現に変換して、線画を構成する線を基本的に個々のピクセルが一列につながった細線へと変換、つまり細線化する。細線化後の線画２ａを図２（ｃ）に示している。二値化表現への変換及び細線化は、通常の方法により行うことができる。
【００１７】
次にステップＳ３０４にて、グループ化を行う。ここでグループ化とは、生成された一本以上の細線であって、互いに接続しているものがあれば１つのグループとし、接続しているものがなければ細線１本を１つのグループと定めることである。このステップＳ３０４により定められたグループを図２（ｄ）に示している。図２（ｄ）によれば、ＧＲ１、ＧＲ２、ＧＲ３、２０１、２０５、２０６、２０７、２０８、２０９、２１０の各グループが存在している。
【００１８】
ステップＳ３０４−２では、あるグループに属するピクセルであって、ステップＳ３０２でストロークが開始された個所に近いピクセルを始点と定め、該グループ又は他のグループに属するピクセルであって前記ストロークを終了した個所に近いピクセルを終点と定める。図２（ｅ）に始点Ｐ及び終点Ｑを示している。ここで、始点ＰはグループＧＲ１に属しており、終点ＱはグループＧＲ３に属している。
【００１９】
ステップＳ３０４−３では、グループが複数存在するか否かが判断される。グループが複数存在すると判断された場合には、ステップＳ３０５に進み、グループ間を接続する接続線を生成する。
【００２０】
接続線を生成するステップＳ３０５について図４に示すフローチャートを参照しながら説明する。ステップＳ３０５は、図４のステップＳ４０１〜Ｓ４２６の各ステップを含む。まず、ステップＳ４０１から開始し、ステップＳ４０２においてグループ間の距離の最大許容値Ｋを設定する。最大許容値Ｋはユーザの入力により任意に設定することができる。
【００２１】
次にステップＳ４０３において各グループに外接する外接矩形を求める。本実施例では図２（ｄ）に示したグループＧＲ１、ＧＲ２、ＧＲ３、２０１、２０５、２０６、２０７、２０８、２０９、２１０の各グループについて外接矩形を求める。
【００２２】
ステップＳ４０４では、ステップＳ３０４−２で定められた始点を含むグループを接続元グループＸと定める。本実施例では、始点Ｐを含むグループＧＲ１を接続元グループＸと定める。
【００２３】
ステップＳ４０５では、接続元グループＸ以外のグループを未接続グループ群と定める。本実施例では、グループＧＲ２、ＧＲ３、２０１、２０５、２０６、２０７、２０８、２０９、２１０を未接続グループ群と定める。
【００２４】
ステップＳ４０６では、未接続グループ群に属するグループの外接矩形の周囲長をそのグループの優先度とする。周囲長が大きいほど優先度が高いものとする。ただし、ステップＳ３０４−２で定められた終点を含むグループは、そのグループの外接矩形の周囲長に関わらず、優先度最高とする。本実施例では、終点Ｑを含むグループＧＲ３が最高の優先度を有する。
【００２５】
ステップＳ４０７では、未接続グループ群のうち、接続元グループＸとの最短距離をまだ計算していないグループであって、優先度の最も高いグループを接続先グループＹと定める。
【００２６】
ステップＳ４０８では、接続先グループＹが存在するか否かが判断される。存在すると判断された場合にはステップＳ４１０に進む。その一方でＹが存在しないと判断された場合にはステップＳ４０９に進み、エラー処理を行って接続線生成処理を終了する。
【００２７】
ステップＳ４１０では、接続元グループＸの外接矩形と接続先グループＹの外接矩形の最短距離を求めて、その値が最大許容値Ｋ以下か否かが判断される。Ｋ以下であればステップＳ４１１に進む一方、その他の場合にはステップＳ４０７に戻る。
【００２８】
ステップＳ４１１では、接続元グループＸの細線を構成する各ピクセルからの距離が最大許容値Ｋ以内にある、接続元グループＹに含まれる細線を構成するピクセルを探し、両ピクセル間の距離を求める。距離が最小となるピクセルの組み合わせを探し、距離の最小値をＶ１とする。
【００２９】
ステップＳ４１２ではＶ１がＫ以下であるか否かが判断される。Ｋ以下であればステップＳ４１３に進み、その他の場合はステップＳ４０７に戻る。
【００３０】
ステップＳ４１３では、接続先グループＹを未接続グループ群から除外する。
【００３１】
ステップＳ４１４では、接続先グループＹが終点を含むか否かが判断される。Ｙが終点を含むグループであればステップＳ４２６に進み、接続線生成処理を終了する。その他の場合には、ステップＳ４１５に進む。
【００３２】
ステップＳ４１５では、未接続グループ群のうち、Ｘとの最短距離をまだ計算していないグループであって、優先度が最も高いグループを中間グループＺとする。
【００３３】
ステップＳ４１６では、中間グループＺが存在するか否かが判断される。存在しない場合にはステップＳ４２４に進み、接続元グループＸと接続先グループＹとの距離が最小となる部分に、ＸとＹとを接続する接続線を生成する。その後、後述するステップＳ４２５に進む。
【００３４】
ステップＳ４１６において中間グループＺが存在すると判断された場合にはステップＳ４１７に進む。ステップＳ４１７では、Ｘの外接矩形とＺの外接矩形との間の第１の最短距離、及びＹの外接矩形とＺの外接矩形との間の最短距離がともにＶ１以下であるか否かが判断される。第１及び第２の最短距離がいずれもＶ１以下の場合には、ステップＳ４１８に進む。これに対し、第１及び第２の最短距離のうち少なくとも一方がＶ１より大きい場合には、ステップＳ４１５に戻る。
【００３５】
ステップＳ４１８では、Ｘに含まれる細線を構成するピクセルとＺに含まれる細線を構成するピクセルと間の距離の最小値をＶ２とする。
【００３６】
ステップＳ４１９では、Ｙに含まれる細線を構成するピクセルとＺに含まれる細線を構成するピクセルとの間の距離の最小値をＶ３とする。
【００３７】
ステップＳ４２０では、Ｖ２とＶ３との和がＶ１以下であるか否かが判断される。Ｖ１以下の場合にはステップＳ４２１に進み、その他の場合にはステップＳ４１５に戻る。
【００３８】
ステップＳ４２１では、Ｚを未接続グループ群から除外する。そして、ステップＳ４２２ではＸからＺまでの距離が最小となる部分にＸとＺとを接続する接続線を生成する。
【００３９】
ステップＳ４２３では、ＺからＹまでの距離が最小となる部分にＺとＹとを接続する接続線を生成する。
【００４０】
ステップＳ４２５ではＹを接続元グループＸとして、ステップＳ４０７に戻る。最終的にステップＳ４２６で接続線生成処理を終了する。
【００４１】
以上のように、ステップＳ４０１〜Ｓ４２６を含むステップＳ３０５において接続線が生成される。本実施例では、図２（ｅ）に示すように、始点Ｐを含むグループＧＲ１とグループＧＲ２とを接続する接続線２０２が生成される。さらに、グループＧＲ２とグループ２０１を接続する接続線２０３を生成し、終点Ｑを含むグループＧＲ３とグループ２０１を接続する接続線２０４を生成する。
【００４２】
一方で、ステップＳ３０４−３においてグループが１つしかないと判断された場合には、接続線を生成する必要がないため、ステップＳ３０５をスキップして後述のステップＳ３０６に進む。
【００４３】
ステップＳ３０６では、接続線により接続されていないグループを削除する。図２（ｅ）で言えば、グループ２０５〜２１０を削除する。さらに、いずれかのグループに属する細線であって終端を含むものを他の細線と交差するところまで削除する。図２（ｅ）について言えば、部分２１１〜２１６を削除する。なお、始点Ｐ及び終点Ｑについては終端とは判断せず、したがって削除も行われない。部分２０５〜２１６をまとめて「枝」とも呼ぶ。
以上のようにして、図２（ｅ）から枝が削除された後の細線２ｂを図２（ｆ）に示している。
【００４４】
ステップＳ３０７では、細線２ｂのコストを求める。以下、図５（ａ）〜（ｄ）を参照してコストの求め方の一例を説明する。
【００４５】
コストを求めるにあたり、いくつかのパラメータを導入する。まず、ステップＳ３０３において線の二値化を行い、線を片側から１ビット（点）づつ幅を狭くしてゆき、その回数のカウントを行いながら細線化を行う。両側とも細線になるまでの幅を狭くするカウントを行い、両側の数値の平均カウントの切り上げを行う。その細線化されるまでの各点のカウントを、回数線の各ビット（点）に属性として持たせる。細線の各ビットが持つカウント数の総数をＷとする。また、細線の長さをＮとする。
【００４６】
ステップＳ３０５において定まった始点Ｐから終点Ｑまでの距離をＲとする。始点Ｐ及び終点Ｑを図５（ｂ）に示している。
【００４７】
細線２ａを始点Ｐから順にたどるときに、ピクセルに沿って縦又は横にたどるときの長さＬ１を１．０とし、斜めにたどるときの長さＬ２を１．５とする。この様子を図５（ｃ）に示している。このようにして得られる細線２ａの長さをＬとする。
【００４８】
細線２ａの始点Ｐから４ピクセル毎に１ピクセルを抽出し、抽出点とする。図５（ｄ）に抽出点Ｔ１及びＴ２を示している。そして、ある抽出点（例えばＴ２）について、その直前の抽出点（Ｔ１）からの方向を抽出点Ｔ２における細線の方向ＥＴ２と定める。
【００４９】
抽出点に最も近いストローク軌跡Ｓ上の点を最近点とし、その抽出点と最近点との距離（ピクセル数）を求める。全ての抽出点における距離の総和をＤとする。図５（ｄ）には、抽出点Ｔ２の最近点ＣＴ２と、抽出点Ｔ２と最近点ＣＴ２との距離ＦＴ２を示している。
【００５０】
さらに、最近点におけるストロークの方向（画像上の入力手段の動きの接線方向）と、抽出点における細線の方向（抽出点における細線の接線の方向）の角度差の絶対値を求める。図５（ｄ）には、最近点ＣＴ２におけるストロークの方向ＧＴ２を示している。これにより、ストロークの方向ＧＴ２と細線の方向ＥＴ２との角度差の絶対値が得られる。この角度差の絶対値を抽出点毎に求め、それらの総和をＡとする。さらに、抽出点の総ピクセル数をＭとする。
【００５１】
以上のパラメータを用いて、細線を始点ＰからたどるときのコストＣＰが以下の式から得られる。
【数１】
式（１）の第１項「１００Ｎ／Ｗ」は、Ｎを分子に持ち、Ｗを分母に持つ。つまり、細線化前の状態において太い線ほど小さい値となる。したがって、太い線ほどコストＣＰの値は小さくなる。これにより、後述するステップＳ３０９〜Ｓ３１２を反復してコストの小さい線を探すことが、すなわち太い線を探すこととなり、太い線が基線と認識されやすくなる。
【００５２】
また、細線を終点ＱからたどるときのコストＣＱは以下の式から得られる。
【数２】
式（２）と式（１）との相違点は、式（２）が第４項「＋１８０」を有しているという点である。すなわち、終点からたどるときのコストＣＱは常に値１８０が加算され、始点からたどるときのコストＣＰよりも大きい値となる。これにより、後述するステップＳ３０９〜Ｓ３１１を反復してコストの小さい線を探すことが、始点方向からたどる経路を探すこととなる。つまり、逆方向からたどる経路、すなわち終点からたどる経路は基線と認識されにくくなる。
【００５３】
以上のように、パラメータＷ，Ｎ，Ｒ，Ｌ，Ｄ，Ａ，Ｍを用いてコストを求めることができる。なお、上記式（１）、式（２）ともに経験則から得られる式であって、一例に過ぎない。コストは他の式でも求めることができる。ステップＳ３０７で求められた、始点ＰからたどるときのコストＣＰを図２（ｇ）に示している。
【００５４】
ステップＳ３０８では、始点から終点までの任意の一の経路を基準経路と定めて、経路全体のコストを求める。基準経路の例を図２（ｈ）の符号Ｒ１で示している。この基準経路Ｒ１全体のコストは２１５（＝８＋１０＋２０＋１８＋３２＋１７＋１１０）である。
【００５５】
ステップＳ３０９では、ステップＳ３０８で定めた基準経路以外の経路を一つ選んで選択経路とし、その選択経路全体のコストを求める。選択経路の例を図２（ｉ）の符号Ｒ２で示している。この選択経路Ｒ２全体のコストは２１３（＝８＋１０＋２０＋２０＋５＋７＋６＋２＋３＋５＋１７＋１１０）である。
【００５６】
ステップＳ３１０では、ステップＳ３０８で求めた基準経路Ｒ１の総コストと選択経路Ｒ２の総コストとを比較し、選択経路のコストの方が小さいか否かを判断する。本実施形態では、選択経路の総コスト（「２１３」）が基準経路の総コスト（「２１５」）よりも小さいため、後述するステップＳ３１１に進む。一方で、選択経路の総コストが基準経路の総コストよりも小さくない場合は、ステップＳ３１１をスキップして後述するステップＳ３１２に進む。
【００５７】
ステップＳ３１１では、ステップＳ３１０において基準経路のコストよりも小さいコストを有すると判断された選択経路を基準経路に置き換える。本実施形態では、Ｒ２のコストがＲ１のコストよりも小さいため、基準経路をＲ１に代えてＲ２とする。
【００５８】
ステップＳ３１２では、始点Ｐと終点Ｑとを結ぶ経路が他にあるか否かを判断する。他に経路が存在する場合には、ステップＳ３１２−２に進み、複数の経路のコストを算出し、コストの低いものを選択し、コストを最小化する。そしてステップＳ３１３に進む。他に経路が存在しない場合には、ステップＳ３１２−２をスキップしてステップＳ３１３に進む。
【００５９】
ステップＳ３１３では、最小コストの線をステップＳ３０３の細線化を行う前の状態に戻して、選択範囲とする。図２（ｊ）に選択範囲２ｃを示している。
さらに、図１（ａ）の線画１における部分１１及び１２にそれぞれ対応する選択範囲を図６に部分１１ａ及び１２ａとして示している。
【００６０】
ステップＳ３１４では、選択範囲により隔てられた領域の一方をある色で彩色する。本実施形態で定められた選択範囲２ｃにより隔てられた領域の一方をある色で彩色する様子を図２（ｋ）に示している。ここで、符号３０１はカーソルを表しており、符号３０２はマウスなどのポインティングデバイスのドラッグ操作により作られる小円である。この小円３０２の領域内であって、選択範囲２ｃにより隔てられた領域３０２１をある色で彩色することができる。さらに、小円３０２の領域内であって、選択範囲２ｃにより隔てられた別の領域３０２２は、ユーザが彩色を意図しない部分であるとして、彩色をしないことができる。
【００６１】
このようにして、大まかにマウスを操作しても、選択範囲により隔てられた領域の一方のみをある色で彩色することができる。
なお、彩色した結果を描画するレイヤー（描画先レイヤー）は、選択範囲が存在するレイヤー（参照レイヤー）とは別のレイヤーとすることができる。
【００６２】
最後に、ステップＳ３１５で手順を終了する。このようにして塗りつぶされた様子を図２（ｌ）に示している。図２（ｌ）からわかるように、ドラッグした範囲５００のうち、符号５００１で示した領域のみが彩色されており、符号５００２で示した領域は彩色されていない。
【００６３】
次に、本発明のコンピュータプログラムの一つの形態について図面を参照しながら説明する。
【００６４】
図７は、本発明のコンピュータプログラムを実行するコンピュータシステム６を示している。図６に示しているように、コンピュータシステム６は、マウスやキーボードなどの入力手段６１１と、ディスプレイなどの表示手段６１２と、メモリ６１３などの記憶手段とを備えている。このコンピュータシステム６は、画像読込手段６２１と、細線生成手段６２２と、グループ化手段６２３と、接続線生成手段６２４と、枝削除手段６２５と、コスト計算手段６２６と、経路探索手段６２７と、選択範囲化する手段６２８と、彩色する手段６２９とをさらに備えている。
【００６５】
図８は、本発明のコンピュータプログラムの処理のフローチャートを示している。以下、本発明のコンピュータプログラムを図２（ａ）に示した線画２に対して適用する流れを説明する。
【００６６】
まず、ステップＳ７０１から開始し、ステップＳ７０２において画像読込手段６２１が線画２をメモリ６１３に読み込む。次にステップＳ７０３において、入力手段６１１が線画２をストロークするオペレータの操作を受け付ける。図２（ａ）の矢印Ｓは、ストロークの方向と軌跡を表している。このステップＳ７０３によりストロークされた領域を領域３で示している。このストロークされた領域３において基線を認識する流れを以下に説明する。
【００６７】
ステップＳ７０４では、細線生成手段６２２が、ストロークされた領域３に含まれる濃淡を含んだ線画２を二値化表現に変換、つまり、白と黒の二値での表現に変換して、線画を構成する線を基本的に個々のピクセルが一列につながった細線へと変換、つまり細線化する。細線化後の細線２ａを図２（ｃ）に示している。二値化表現への変換及び細線化は、通常の方法により行うことができる。
【００６８】
次にステップＳ７０５にて、グループ化手段６２３がグループ化を行う。ここでグループ化とは、生成された一本以上の細線であって、互いに接続しているものがあれば１つのグループとし、接続しているものがなければ細線１本を１つのグループと定めることである。このステップＳ７０５により定められたグループを図２（ｄ）に示している。図２（ｄ）によれば、ＧＲ１、ＧＲ２、ＧＲ３、２０１、２０５、２０６、２０７、２０８、２０９、２１０の各グループが存在している。
【００６９】
ステップＳ７０５−２では、グループ化手段６２３が、ステップＳ７０３でストロークを開始した個所に最も近い線上の点を始点と定め、ストロークを終了した個所に最も近い線上の点を終点と定めて、メモリ６１３に保存する。図２（ｅ）に始点Ｐ及び終点Ｑを示している。ここで、始点ＰはグループＧＲ１に属しており、終点ＱはグループＧＲ３に属している。
【００７０】
ステップＳ７０５−３でグループ化手段６２３は、グループが複数存在するか否かを判断する。グループが複数存在すると判断された場合には、ステップＳ７０６に進み、各グループ間を接続する接続線を接続線生成手段６２４が生成する。ステップＳ７０６は、図４に示したステップＳ４０１〜Ｓ４２６の各ステップを含んでいる。本実施例では図２（ｅ）に示すように、ステップＳ７０６において始点Ｐを含むグループＧＲ１と始点Ｐ及び終点Ｑのいずれも含まないグループＧＲ２とを接続する接続線２０２を接続線生成手段６２４が生成する。さらに、グループＧＲ２とグループ２０１を接続する接続線２０３と、終点Ｑを含むグループＧＲ３とグループ２０１を接続する接続線２０４とを接続線生成手段６２４が生成する。
【００７１】
一方で、ステップＳ７０５−３においてグループが１つしかないと判断された場合には、接続線を生成する必要がないため、ステップＳ７０６をスキップして後述のステップＳ７０７に進む。
【００７２】
ステップＳ７０７では、枝削除手段６２５が、接続線により接続されていないグループを削除する。図２（ｅ）で言えば、手段６２５はグループ２０５〜２１０を削除する。さらに、手段６２５はいずれかのグループに属する細線であって終端を含むものを他の細線と交差するところまで削除する。図２（ｅ）について言えば、手段６２５が部分２１１〜２１６を削除する。なお、手段６２５は、始点Ｐ及び終点Ｑについては終端と判断せず、したがって削除も行わない。部分２０５〜２１６をまとめて「枝」とも呼ぶ。
以上のようにして、図２（ｅ）から枝が削除された後の細線２ｂを図２（ｆ）に示している。
【００７３】
ステップＳ７０８では、コスト計算手段６２６が細線２ｂのコストを求める。以下、図５（ａ）〜（ｄ）を参照してコストの求め方の一例を説明する。
【００７４】
コストを求めるにあたり、いくつかのパラメータを導入する。まず、ステップＳ３０３において線の二値化を行い、線を片側から１ビット（点）づつ幅を狭くしてゆき、その回数のカウントを行いながら細線化を行う。両側とも細線になるまでの幅を狭くするカウントを行い、両側の数値の平均カウントの切り上げを行う。その細線化されるまでの各点のカウントを、回数線の各ビット（点）に属性として持たせる。細線の各ビットが持つカウント数の総数をＷとする。また、細線の長さをＮとする。
【００７５】
コスト計算手段６２６が、ステップＳ７０６において定まった始点Ｐから終点Ｑまでの距離をＲとしてメモリ６１３に保存する。始点Ｐ及び終点Ｑを図５（ｂ）に示している。
【００７６】
細線２ａを始点Ｐから順にたどるときに、ピクセルに沿って縦又は横にたどるときの長さＬ１を１．０とし、斜めにたどるときの長さＬ２を１．５とする。この様子を図５（ｃ）に示している。コスト計算手段６２６は、このようにして得られる細線２ａの長さをＬとしてメモリ６１３に保存する。
【００７７】
次に、コスト計算手段６２６は、細線２ａの始点Ｐから４ピクセル毎に１ピクセルを抽出し、抽出点としてメモリ６１３に保存する。図５（ｄ）に抽出点Ｔ１及びＴ２を示している。そして、コスト計算手段６２６は、ある抽出点（例えばＴ２）について、その直前の抽出点（Ｔ１）からの方向を抽出点Ｔ２における細線の方向ＥＴ２と定めてメモリ６１３に保存する。
【００７８】
コスト計算手段６２６は、抽出点に最も近いストローク軌跡Ｓ上の点を最近点として、その抽出点と最近点との距離（ピクセル数）を求める。コスト計算手段６２６は、全ての抽出点における距離の総和をＤとしてメモリ６１３に保存する。図５（ｄ）には、抽出点Ｔ２の最近点ＣＴ２と、抽出点Ｔ２と最近点ＣＴ２との距離ＦＴ２を示している。
【００７９】
さらに、コスト計算手段６２６は、最近点におけるストロークの方向（画像上の入力手段の動きの接線方向）と、抽出点における細線の方向（抽出点における細線の接線の方向）の角度差の絶対値を求める。図５（ｄ）には、最近点ＣＴ２におけるストロークの方向ＧＴ２を示している。これにより、ストロークの方向ＧＴ２と細線の方向ＥＴ２との角度差の絶対値が得られる。コスト計算手段６２６は、この角度差の絶対値を抽出点毎に求め、それらの総和をＡとしてメモリ６１３に保存する。さらに、コスト計算手段６２６は抽出点の総ピクセル数をＭとしてメモリ６１３に保存する。
【００８０】
以上のパラメータを用いて、コスト計算手段６２６は、細線を始点ＰからたどるときのコストＣＰを式（１）から求める。式（１）の第１項「１００Ｎ／Ｗ」は、Ｎを分子に持ち、Ｗを分母に持つ。つまり、細線化前の状態において太い線ほど小さい値となる。したがって、太い線ほどコストＣＰの値は小さくなる。これにより、後述するステップＳ７１０〜Ｓ７１３を反復してコストの小さい線を探すことが、すなわち太い線を探すこととなり、太い線が基線と認識されやすくなる。
【００８１】
また、コスト計算手段６２６は、細線を終点ＱからたどるときのコストＣＱを式（２）から求める。式（２）と式（１）との相違点は、式（２）が第４項「＋１８０」を有しているという点である。すなわち、終点からたどるときのコストＣＱは常に値１８０が加算され、始点からたどるときのコストＣＰよりも大きい値となる。これにより、後述するステップＳ７１０〜Ｓ７１２を反復してコストの小さい線を探すことが、始点方向からたどる経路を探すこととなる。つまり、逆方向からたどる経路、すなわち終点からたどる経路は基線と認識されにくくなる。
【００８２】
以上のように、パラメータＷ，Ｎ，Ｒ，Ｌ，Ｄ，Ａ，Ｍを用いて、コスト計算手段６２６はコストを求めることができる。なお、上記式（１）、式（２）ともに経験則から得られる式であって、一例に過ぎない。コストは他の式でも求めることができる。ステップＳ７０８で求められた、始点ＰからたどるときのコストＣＰを図２（ｇ）に示している。
【００８３】
ステップＳ７０９では、経路探索手段６２７が、始点から終点までの任意の一の経路を基準経路と定めて、経路全体のコストを求めメモリ６１３に保存する。基準経路の例を図２（ｈ）の符号Ｒ１で示している。この基準経路Ｒ１全体のコストは２１５（＝８＋１０＋２０＋１８＋３２＋１７＋１１０）である。
【００８４】
ステップＳ７１０では、経路探索手段６２７が、ステップＳ７０９で定めた基準経路以外の経路を一つ選んで選択経路とし、その選択経路全体のコストを求めメモリ６１３に保存する。選択経路の例を図２（ｉ）の符号Ｒ２で示している。この選択経路Ｒ２全体のコストは２１３（＝８＋１０＋２０＋２０＋５＋７＋６＋２＋３＋５＋１７＋１１０）である。
【００８５】
ステップＳ７１１では、経路探索手段６２７が、ステップＳ７０９で求めた基準経路Ｒ１の総コストと選択経路Ｒ２の総コストとを比較し、選択経路のコストの方が小さいか否かを判断する。本実施形態では、選択経路の総コスト（「２１３」）が基準経路の総コスト（「２１５」）よりも小さいため、後述するステップＳ７１２に進む。一方で、選択経路の総コストが基準経路の総コストよりも小さくない場合は、ステップＳ７１２をスキップして後述するステップＳ７１３に進む。
【００８６】
ステップＳ７１２では、経路探索手段６２７が、ステップＳ７１１において基準経路のコストよりも小さいコストを有すると判断された選択経路を基準経路に置き換えてメモリ６１３に保存する。本実施形態では、経路探索手段６２７は、Ｒ２のコストがＲ１のコストよりも小さいため、基準経路をＲ１に代えてＲ２としてメモリ６１３に保存する。
【００８７】
ステップＳ７１３では、始点Ｐと終点Ｑとを結ぶ経路が他にあるか否かを経路探索手段６２７が判断する。他に経路が存在する場合、ステップＳ７１３−２に進み、経路探索手段６２７が複数の経路のコストを算出し、コストの低いものを選択し、コストを最小化する。そしてステップＳ７１４に進む。他に経路が存在しない場合には、ステップＳ３１２−２をスキップしてステップＳ３１３に進む。
【００８８】
ステップＳ７１４では、選択範囲化する手段６２８が、最小コストの線をステップＳ７０４の細線化を行う前の状態に戻して、選択範囲とし、メモリ６１３に保存する。図２（ｊ）に選択範囲２ｃを示している。
さらに、図１（ａ）の線画１における部分１１及び１２にそれぞれ対応する選択範囲を図６に部分１１ａ及び１２ａとして示している。
【００８９】
ステップＳ７１５では、彩色する手段６２９が、選択範囲により隔てられた領域の一方をある色で彩色してメモリ６１３に保存する。本実施形態で定められた選択範囲２ｃにより隔てられた領域の一方をある色で彩色する様子を図２（ｋ）に示している。ここで、符号３０１はカーソルを表しており、符号３０２は入力手段６１１のドラッグ操作により作られる小円である。この小円３０２の領域内であって、選択範囲２ｃにより隔てられた領域３０２１をある色で彩色することができる。さらに、小円３０２の領域内であって、選択範囲２ｃにより隔てられた別の領域３０２２は、ユーザが彩色を意図しない部分であるとして、彩色をしないことができる。
【００９０】
このようにして、大まかにマウスを操作しても、選択範囲により隔てられた領域の一方のみをある色で彩色することができる。
なお、彩色する手段６２９は、選択範囲が存在するレイヤー（参照レイヤー）とは別のレイヤーである彩色した結果を描画するレイヤー（描画先レイヤー）に描画してメモリ６１３に保存することができる。
【００９１】
最後に、ステップＳ７１６で手順を終了する。このようにして塗りつぶされた様子を図２（ｌ）に示している。図２（ｌ）からわかるように、ドラッグした範囲５００のうち、符号５００１で示した領域のみが彩色されており、符号５００２で示した領域は彩色されていない。
【００９２】
本発明の方法及びコンピュータプログラムによれば、塗りあふれ及び塗り残しのいずれもなく線画を彩色することができ、彩色された線画を効率的に製作することができる。
【図面の簡単な説明】
【００９３】
【図１】本発明方法の処理対象となる線画の一例を示す平面図である。
【図２Ａ】本発明の彩色方法により、図１の線画の塗り残し領域が塗りつぶされる過程を示す説明図である。
【図２Ｂ】本発明の彩色方法により、図１の線画の塗り残し領域が塗りつぶされる過程を示す説明図である。
【図３】本発明の彩色方法の手順の一例を示すフローチャートである。
【図４】接続線を生成する手順の一例を示すフローチャートである。
【図５】コストを求める過程についての説明図である。
【図６】本発明の彩色方法により彩色された線画の平面図である。
【図７】本発明のコンピュータプログラムを実行するコンピュータシステム６のブロック図である。
【図８】本発明のコンピュータプログラムの処理手順の一例を示すフローチャートである。
【符号の説明】
【００９４】
１ 線画
１１，１２ 線画１の一部分
１１ａ，１２ａ 選択範囲
２ 線画
２ａ 細線
２ｂ 枝が削除された細線
２ｃ 選択範囲
２０１ 線
２０２〜２０４ 接続線
２１１〜２１６ 枝
３ ストロークされた領域
３０１ カーソル
３０２ 小円
３０２１，３０２２ 領域
５００ ドラッグ領域
５００１、５００２ 領域
６ コンピュータシステム
６１１ 入力手段
６１２ 表示手段
６１３ メモリ
６２１ 画像読込手段
６２２ 細線生成手段
６２３ グループ化手段
６２４ 接続線生成手段
６２５ 枝削除手段
６２６ コスト計算手段
６２７ 経路探索手段
６２８ 選択範囲化する手段
６２９ 彩色する手段
ＧＲ１〜ＧＲ３、２０５〜２１０ グループ
Ｐ 始点
Ｑ 終点
Ｒ１，Ｒ２ 経路
Ｓ ストロークの軌跡
【技術分野】
【０００１】
本発明は、線画における基線を認識し、それに基づいて彩色する線画の彩色方法及びプログラムに関する。
【背景技術】
【０００２】
漫画やアニメーション、イラストなど、一色の線だけで描かれた画である線画に対して彩色を施すことが一般に行われている。図１（ａ）に線画の一例として線画１を示している。我が国で製作された漫画などの白黒の線画に対して、海外向けに彩色することが頻繁に行われている。
【０００３】
ここで、線の色が均一ではなく濃淡を含んでいる場合には、フィルツールなどで直接塗りつぶすことができないという問題がある。例えば図１（ａ）の部分１１を拡大した様子を示す図１（ｂ）、及び図１（ａ）の部分１２を拡大した様子を示す図１（ｃ）からわかるように、線が繋がっておらず隙間が存在している場合には、領域が線により隔てられていないとフィルツールが認識し、ユーザが意図しない部分まで彩色されてしまうことがある。
【０００４】
このような問題を避けるべく、線画に彩色すべき範囲を作成して、その範囲内を塗りつぶすという方法が知られている。しかし、基線とトーンが混在する画像では、線画のみを抽出して彩色すべき範囲を作成することが困難であるという問題がある。また、仮に線画のみを抽出して彩色すべき範囲を作成できたとしても、彩色の作業は通常マウスなどのポインティングデバイスを用いて手作業で行われるため、彩色すべき範囲をはみ出して彩色してしまうという問題がある。色のはみ出た箇所を見つけて修正するには、細い箇所まで目で確認しながら修正する必要があり、効率的ではない。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明の目的は、線画を彩色する際に基線を認識して、その基線からはみ出すことなく彩色できる方法及びコンピュータプログラムを提供することである。
【課題を解決するための手段】
【０００６】
上記課題を解決するため、本発明の方法は、線画を含むある領域に対するストロークを受け付けるストローク受付ステップと、ストロークされた前記領域にある線画を二値化表現に変換し、線画を構成する線を細線化する細線生成ステップと、生成された細線であって互いに接続しているものの集まりを１つのグループと定めるグループ化ステップと、グループに属するピクセルであって、前記ストロークが開始された個所に近いピクセルを始点と定める始点決定ステップと、グループに属するピクセルであって、前記ストロークが終了された個所に近いピクセルを終点と定める終点決定ステップと、グループに属する細線であって終端を含むものを他の細線と交差するところまで削除する削除ステップと、グループに属する細線のコストを求めるコスト計算ステップであって、ここで、前記コストは、二値化表現変換後の細線に含まれるピクセル数を含むいくつかの変数に基づいて計算されるものである、ステップと、前記コストに基づいて、前記始点と前記終点とを結ぶ経路を探索する経路探索ステップと、探索された経路を前記細線生成ステップにより細線化する前の状態に戻して選択範囲とする選択範囲化ステップと、選択範囲化された選択範囲により隔てられた複数の領域のうちの一の領域をある色で彩色する彩色ステップとを含む。
【０００７】
別の実施形態で、前記方法は、前記グループ化ステップにより複数のグループが定められた場合には、該グループ化ステップの後であって、かつ前記削除ステップの前に、前記複数のグループの各々に外接する外接矩形の周囲長と該外接矩形間の距離とを含むいくつかの変数に基づいて、グループ間を接続する線を生成する接続線生成ステップをさらに含み、前記削除ステップは、接続線により接続されていないグループを削除し、生成された接続線を削除しないものとすることができる。
【０００８】
別の実施形態で、前記経路探索ステップは、最小のコストを有する経路を選択するサブステップを含む。
【０００９】
上記問題を解決するため、本発明のコンピュータプログラムは、線画をメモリに読み込む画像読込手段と、前記線画を含むある領域に対するストロークを受け付けるための入力手段と、ストロークされた前記領域にある線画を二値化表現に変換し、線画を構成する線を細線化する細線生成手段と、生成された細線であって互いに接続しているものの集まりを１つのグループと定め、グループに属するピクセルであって、前記ストロークが開始された個所に近いピクセルを始点と定めるとともに、グループに属するピクセルであって、前記ストロークが終了された個所に近いピクセルを終点と定めるグループ化手段と、グループに属する細線であって終端を含むものを他の細線と交差するところまで削除する枝削除手段と、グループに属する細線のコストを求めるコスト計算手段であって、二値化表現変換後の細線に含まれるピクセル数を含むいくつかの変数に基づいてコストを計算するコスト計算手段と、前記コストに基づいて、前記始点と前記終点とを結ぶ経路を探索する経路探索手段と、探索された経路を前記細線生成手段が細線化する前の状態に戻して選択範囲化する手段と、選択範囲化された選択範囲により隔てられた複数の領域のうちの一の領域をある色で彩色する手段とをコンピュータに実現させる。
【００１０】
別の実施形態で、前記コンピュータプログラムは、前記グループ化手段が複数のグループを定めた場合には、前記複数のグループの各々に外接する外接矩形の周囲長と該外接矩形間の距離とを含むいくつかの変数に基づいて、グループ間を接続する線を生成する接続線生成手段をコンピュータにさらに実現させ、接続線により接続されていないグループを削除し、生成された接続線を削除しないように前記枝削除手段をコンピュータに実現させることができる。
【００１１】
別の実施形態で、前記経路探索手段は、最小のコストを有する経路を選択することができる。
【発明の効果】
【００１２】
本発明によれば、濃淡を含む線画に適した彩色方法及びコンピュータプログラムを提供することができる。この方法又はコンピュータプログラムにより、効率的に線画に彩色できるとともに、細かい箇所まで目で確認しながら修正するという今までの作業の手間が省け、なおかつ作業品質の向上を実現することができる。
【発明を実施するための最良の形態】
【００１３】
次に、線画における基線を認識し、それに基づいて彩色する本発明の方法を実施する一つの形態について図面を参照しながら説明する。
【００１４】
まず、図２（ａ）は、線画２を示している。図２（ａ）によれば、線が部分的に途切れていて隙間のあることがわかる。説明の都合上、線画２が図１（ａ）の部分１１あるいは部分１２に対応するものとする。
【００１５】
図３は、線画における基線を認識し、それに基づいて彩色する本発明の方法のフローチャートを示している。まず、ステップＳ３０１から開始し、ステップＳ３０２において線画２をなぞるオペレータの操作を受け付ける。この「なぞる」ことを「ストロークする」とも呼ぶ。ストロークは、マウスなどのポインティングデバイスを用いて行うことができる。図２（ａ）の矢印Ｓは、ストロークの方向と軌跡を表している。このステップＳ３０２によりストロークされた領域を領域３で示している。このストロークされた領域３において基線を認識する流れを以下に説明する。
【００１６】
ステップＳ３０３では、ストロークされた領域３に含まれる濃淡を含んだ線画２を二値化表現に変換、つまり、白と黒の二値での表現に変換して、線画を構成する線を基本的に個々のピクセルが一列につながった細線へと変換、つまり細線化する。細線化後の線画２ａを図２（ｃ）に示している。二値化表現への変換及び細線化は、通常の方法により行うことができる。
【００１７】
次にステップＳ３０４にて、グループ化を行う。ここでグループ化とは、生成された一本以上の細線であって、互いに接続しているものがあれば１つのグループとし、接続しているものがなければ細線１本を１つのグループと定めることである。このステップＳ３０４により定められたグループを図２（ｄ）に示している。図２（ｄ）によれば、ＧＲ１、ＧＲ２、ＧＲ３、２０１、２０５、２０６、２０７、２０８、２０９、２１０の各グループが存在している。
【００１８】
ステップＳ３０４−２では、あるグループに属するピクセルであって、ステップＳ３０２でストロークが開始された個所に近いピクセルを始点と定め、該グループ又は他のグループに属するピクセルであって前記ストロークを終了した個所に近いピクセルを終点と定める。図２（ｅ）に始点Ｐ及び終点Ｑを示している。ここで、始点ＰはグループＧＲ１に属しており、終点ＱはグループＧＲ３に属している。
【００１９】
ステップＳ３０４−３では、グループが複数存在するか否かが判断される。グループが複数存在すると判断された場合には、ステップＳ３０５に進み、グループ間を接続する接続線を生成する。
【００２０】
接続線を生成するステップＳ３０５について図４に示すフローチャートを参照しながら説明する。ステップＳ３０５は、図４のステップＳ４０１〜Ｓ４２６の各ステップを含む。まず、ステップＳ４０１から開始し、ステップＳ４０２においてグループ間の距離の最大許容値Ｋを設定する。最大許容値Ｋはユーザの入力により任意に設定することができる。
【００２１】
次にステップＳ４０３において各グループに外接する外接矩形を求める。本実施例では図２（ｄ）に示したグループＧＲ１、ＧＲ２、ＧＲ３、２０１、２０５、２０６、２０７、２０８、２０９、２１０の各グループについて外接矩形を求める。
【００２２】
ステップＳ４０４では、ステップＳ３０４−２で定められた始点を含むグループを接続元グループＸと定める。本実施例では、始点Ｐを含むグループＧＲ１を接続元グループＸと定める。
【００２３】
ステップＳ４０５では、接続元グループＸ以外のグループを未接続グループ群と定める。本実施例では、グループＧＲ２、ＧＲ３、２０１、２０５、２０６、２０７、２０８、２０９、２１０を未接続グループ群と定める。
【００２４】
ステップＳ４０６では、未接続グループ群に属するグループの外接矩形の周囲長をそのグループの優先度とする。周囲長が大きいほど優先度が高いものとする。ただし、ステップＳ３０４−２で定められた終点を含むグループは、そのグループの外接矩形の周囲長に関わらず、優先度最高とする。本実施例では、終点Ｑを含むグループＧＲ３が最高の優先度を有する。
【００２５】
ステップＳ４０７では、未接続グループ群のうち、接続元グループＸとの最短距離をまだ計算していないグループであって、優先度の最も高いグループを接続先グループＹと定める。
【００２６】
ステップＳ４０８では、接続先グループＹが存在するか否かが判断される。存在すると判断された場合にはステップＳ４１０に進む。その一方でＹが存在しないと判断された場合にはステップＳ４０９に進み、エラー処理を行って接続線生成処理を終了する。
【００２７】
ステップＳ４１０では、接続元グループＸの外接矩形と接続先グループＹの外接矩形の最短距離を求めて、その値が最大許容値Ｋ以下か否かが判断される。Ｋ以下であればステップＳ４１１に進む一方、その他の場合にはステップＳ４０７に戻る。
【００２８】
ステップＳ４１１では、接続元グループＸの細線を構成する各ピクセルからの距離が最大許容値Ｋ以内にある、接続元グループＹに含まれる細線を構成するピクセルを探し、両ピクセル間の距離を求める。距離が最小となるピクセルの組み合わせを探し、距離の最小値をＶ１とする。
【００２９】
ステップＳ４１２ではＶ１がＫ以下であるか否かが判断される。Ｋ以下であればステップＳ４１３に進み、その他の場合はステップＳ４０７に戻る。
【００３０】
ステップＳ４１３では、接続先グループＹを未接続グループ群から除外する。
【００３１】
ステップＳ４１４では、接続先グループＹが終点を含むか否かが判断される。Ｙが終点を含むグループであればステップＳ４２６に進み、接続線生成処理を終了する。その他の場合には、ステップＳ４１５に進む。
【００３２】
ステップＳ４１５では、未接続グループ群のうち、Ｘとの最短距離をまだ計算していないグループであって、優先度が最も高いグループを中間グループＺとする。
【００３３】
ステップＳ４１６では、中間グループＺが存在するか否かが判断される。存在しない場合にはステップＳ４２４に進み、接続元グループＸと接続先グループＹとの距離が最小となる部分に、ＸとＹとを接続する接続線を生成する。その後、後述するステップＳ４２５に進む。
【００３４】
ステップＳ４１６において中間グループＺが存在すると判断された場合にはステップＳ４１７に進む。ステップＳ４１７では、Ｘの外接矩形とＺの外接矩形との間の第１の最短距離、及びＹの外接矩形とＺの外接矩形との間の最短距離がともにＶ１以下であるか否かが判断される。第１及び第２の最短距離がいずれもＶ１以下の場合には、ステップＳ４１８に進む。これに対し、第１及び第２の最短距離のうち少なくとも一方がＶ１より大きい場合には、ステップＳ４１５に戻る。
【００３５】
ステップＳ４１８では、Ｘに含まれる細線を構成するピクセルとＺに含まれる細線を構成するピクセルと間の距離の最小値をＶ２とする。
【００３６】
ステップＳ４１９では、Ｙに含まれる細線を構成するピクセルとＺに含まれる細線を構成するピクセルとの間の距離の最小値をＶ３とする。
【００３７】
ステップＳ４２０では、Ｖ２とＶ３との和がＶ１以下であるか否かが判断される。Ｖ１以下の場合にはステップＳ４２１に進み、その他の場合にはステップＳ４１５に戻る。
【００３８】
ステップＳ４２１では、Ｚを未接続グループ群から除外する。そして、ステップＳ４２２ではＸからＺまでの距離が最小となる部分にＸとＺとを接続する接続線を生成する。
【００３９】
ステップＳ４２３では、ＺからＹまでの距離が最小となる部分にＺとＹとを接続する接続線を生成する。
【００４０】
ステップＳ４２５ではＹを接続元グループＸとして、ステップＳ４０７に戻る。最終的にステップＳ４２６で接続線生成処理を終了する。
【００４１】
以上のように、ステップＳ４０１〜Ｓ４２６を含むステップＳ３０５において接続線が生成される。本実施例では、図２（ｅ）に示すように、始点Ｐを含むグループＧＲ１とグループＧＲ２とを接続する接続線２０２が生成される。さらに、グループＧＲ２とグループ２０１を接続する接続線２０３を生成し、終点Ｑを含むグループＧＲ３とグループ２０１を接続する接続線２０４を生成する。
【００４２】
一方で、ステップＳ３０４−３においてグループが１つしかないと判断された場合には、接続線を生成する必要がないため、ステップＳ３０５をスキップして後述のステップＳ３０６に進む。
【００４３】
ステップＳ３０６では、接続線により接続されていないグループを削除する。図２（ｅ）で言えば、グループ２０５〜２１０を削除する。さらに、いずれかのグループに属する細線であって終端を含むものを他の細線と交差するところまで削除する。図２（ｅ）について言えば、部分２１１〜２１６を削除する。なお、始点Ｐ及び終点Ｑについては終端とは判断せず、したがって削除も行われない。部分２０５〜２１６をまとめて「枝」とも呼ぶ。
以上のようにして、図２（ｅ）から枝が削除された後の細線２ｂを図２（ｆ）に示している。
【００４４】
ステップＳ３０７では、細線２ｂのコストを求める。以下、図５（ａ）〜（ｄ）を参照してコストの求め方の一例を説明する。
【００４５】
コストを求めるにあたり、いくつかのパラメータを導入する。まず、ステップＳ３０３において線の二値化を行い、線を片側から１ビット（点）づつ幅を狭くしてゆき、その回数のカウントを行いながら細線化を行う。両側とも細線になるまでの幅を狭くするカウントを行い、両側の数値の平均カウントの切り上げを行う。その細線化されるまでの各点のカウントを、回数線の各ビット（点）に属性として持たせる。細線の各ビットが持つカウント数の総数をＷとする。また、細線の長さをＮとする。
【００４６】
ステップＳ３０５において定まった始点Ｐから終点Ｑまでの距離をＲとする。始点Ｐ及び終点Ｑを図５（ｂ）に示している。
【００４７】
細線２ａを始点Ｐから順にたどるときに、ピクセルに沿って縦又は横にたどるときの長さＬ１を１．０とし、斜めにたどるときの長さＬ２を１．５とする。この様子を図５（ｃ）に示している。このようにして得られる細線２ａの長さをＬとする。
【００４８】
細線２ａの始点Ｐから４ピクセル毎に１ピクセルを抽出し、抽出点とする。図５（ｄ）に抽出点Ｔ１及びＴ２を示している。そして、ある抽出点（例えばＴ２）について、その直前の抽出点（Ｔ１）からの方向を抽出点Ｔ２における細線の方向ＥＴ２と定める。
【００４９】
抽出点に最も近いストローク軌跡Ｓ上の点を最近点とし、その抽出点と最近点との距離（ピクセル数）を求める。全ての抽出点における距離の総和をＤとする。図５（ｄ）には、抽出点Ｔ２の最近点ＣＴ２と、抽出点Ｔ２と最近点ＣＴ２との距離ＦＴ２を示している。
【００５０】
さらに、最近点におけるストロークの方向（画像上の入力手段の動きの接線方向）と、抽出点における細線の方向（抽出点における細線の接線の方向）の角度差の絶対値を求める。図５（ｄ）には、最近点ＣＴ２におけるストロークの方向ＧＴ２を示している。これにより、ストロークの方向ＧＴ２と細線の方向ＥＴ２との角度差の絶対値が得られる。この角度差の絶対値を抽出点毎に求め、それらの総和をＡとする。さらに、抽出点の総ピクセル数をＭとする。
【００５１】
以上のパラメータを用いて、細線を始点ＰからたどるときのコストＣＰが以下の式から得られる。
【数１】
式（１）の第１項「１００Ｎ／Ｗ」は、Ｎを分子に持ち、Ｗを分母に持つ。つまり、細線化前の状態において太い線ほど小さい値となる。したがって、太い線ほどコストＣＰの値は小さくなる。これにより、後述するステップＳ３０９〜Ｓ３１２を反復してコストの小さい線を探すことが、すなわち太い線を探すこととなり、太い線が基線と認識されやすくなる。
【００５２】
また、細線を終点ＱからたどるときのコストＣＱは以下の式から得られる。
【数２】
式（２）と式（１）との相違点は、式（２）が第４項「＋１８０」を有しているという点である。すなわち、終点からたどるときのコストＣＱは常に値１８０が加算され、始点からたどるときのコストＣＰよりも大きい値となる。これにより、後述するステップＳ３０９〜Ｓ３１１を反復してコストの小さい線を探すことが、始点方向からたどる経路を探すこととなる。つまり、逆方向からたどる経路、すなわち終点からたどる経路は基線と認識されにくくなる。
【００５３】
以上のように、パラメータＷ，Ｎ，Ｒ，Ｌ，Ｄ，Ａ，Ｍを用いてコストを求めることができる。なお、上記式（１）、式（２）ともに経験則から得られる式であって、一例に過ぎない。コストは他の式でも求めることができる。ステップＳ３０７で求められた、始点ＰからたどるときのコストＣＰを図２（ｇ）に示している。
【００５４】
ステップＳ３０８では、始点から終点までの任意の一の経路を基準経路と定めて、経路全体のコストを求める。基準経路の例を図２（ｈ）の符号Ｒ１で示している。この基準経路Ｒ１全体のコストは２１５（＝８＋１０＋２０＋１８＋３２＋１７＋１１０）である。
【００５５】
ステップＳ３０９では、ステップＳ３０８で定めた基準経路以外の経路を一つ選んで選択経路とし、その選択経路全体のコストを求める。選択経路の例を図２（ｉ）の符号Ｒ２で示している。この選択経路Ｒ２全体のコストは２１３（＝８＋１０＋２０＋２０＋５＋７＋６＋２＋３＋５＋１７＋１１０）である。
【００５６】
ステップＳ３１０では、ステップＳ３０８で求めた基準経路Ｒ１の総コストと選択経路Ｒ２の総コストとを比較し、選択経路のコストの方が小さいか否かを判断する。本実施形態では、選択経路の総コスト（「２１３」）が基準経路の総コスト（「２１５」）よりも小さいため、後述するステップＳ３１１に進む。一方で、選択経路の総コストが基準経路の総コストよりも小さくない場合は、ステップＳ３１１をスキップして後述するステップＳ３１２に進む。
【００５７】
ステップＳ３１１では、ステップＳ３１０において基準経路のコストよりも小さいコストを有すると判断された選択経路を基準経路に置き換える。本実施形態では、Ｒ２のコストがＲ１のコストよりも小さいため、基準経路をＲ１に代えてＲ２とする。
【００５８】
ステップＳ３１２では、始点Ｐと終点Ｑとを結ぶ経路が他にあるか否かを判断する。他に経路が存在する場合には、ステップＳ３１２−２に進み、複数の経路のコストを算出し、コストの低いものを選択し、コストを最小化する。そしてステップＳ３１３に進む。他に経路が存在しない場合には、ステップＳ３１２−２をスキップしてステップＳ３１３に進む。
【００５９】
ステップＳ３１３では、最小コストの線をステップＳ３０３の細線化を行う前の状態に戻して、選択範囲とする。図２（ｊ）に選択範囲２ｃを示している。
さらに、図１（ａ）の線画１における部分１１及び１２にそれぞれ対応する選択範囲を図６に部分１１ａ及び１２ａとして示している。
【００６０】
ステップＳ３１４では、選択範囲により隔てられた領域の一方をある色で彩色する。本実施形態で定められた選択範囲２ｃにより隔てられた領域の一方をある色で彩色する様子を図２（ｋ）に示している。ここで、符号３０１はカーソルを表しており、符号３０２はマウスなどのポインティングデバイスのドラッグ操作により作られる小円である。この小円３０２の領域内であって、選択範囲２ｃにより隔てられた領域３０２１をある色で彩色することができる。さらに、小円３０２の領域内であって、選択範囲２ｃにより隔てられた別の領域３０２２は、ユーザが彩色を意図しない部分であるとして、彩色をしないことができる。
【００６１】
このようにして、大まかにマウスを操作しても、選択範囲により隔てられた領域の一方のみをある色で彩色することができる。
なお、彩色した結果を描画するレイヤー（描画先レイヤー）は、選択範囲が存在するレイヤー（参照レイヤー）とは別のレイヤーとすることができる。
【００６２】
最後に、ステップＳ３１５で手順を終了する。このようにして塗りつぶされた様子を図２（ｌ）に示している。図２（ｌ）からわかるように、ドラッグした範囲５００のうち、符号５００１で示した領域のみが彩色されており、符号５００２で示した領域は彩色されていない。
【００６３】
次に、本発明のコンピュータプログラムの一つの形態について図面を参照しながら説明する。
【００６４】
図７は、本発明のコンピュータプログラムを実行するコンピュータシステム６を示している。図６に示しているように、コンピュータシステム６は、マウスやキーボードなどの入力手段６１１と、ディスプレイなどの表示手段６１２と、メモリ６１３などの記憶手段とを備えている。このコンピュータシステム６は、画像読込手段６２１と、細線生成手段６２２と、グループ化手段６２３と、接続線生成手段６２４と、枝削除手段６２５と、コスト計算手段６２６と、経路探索手段６２７と、選択範囲化する手段６２８と、彩色する手段６２９とをさらに備えている。
【００６５】
図８は、本発明のコンピュータプログラムの処理のフローチャートを示している。以下、本発明のコンピュータプログラムを図２（ａ）に示した線画２に対して適用する流れを説明する。
【００６６】
まず、ステップＳ７０１から開始し、ステップＳ７０２において画像読込手段６２１が線画２をメモリ６１３に読み込む。次にステップＳ７０３において、入力手段６１１が線画２をストロークするオペレータの操作を受け付ける。図２（ａ）の矢印Ｓは、ストロークの方向と軌跡を表している。このステップＳ７０３によりストロークされた領域を領域３で示している。このストロークされた領域３において基線を認識する流れを以下に説明する。
【００６７】
ステップＳ７０４では、細線生成手段６２２が、ストロークされた領域３に含まれる濃淡を含んだ線画２を二値化表現に変換、つまり、白と黒の二値での表現に変換して、線画を構成する線を基本的に個々のピクセルが一列につながった細線へと変換、つまり細線化する。細線化後の細線２ａを図２（ｃ）に示している。二値化表現への変換及び細線化は、通常の方法により行うことができる。
【００６８】
次にステップＳ７０５にて、グループ化手段６２３がグループ化を行う。ここでグループ化とは、生成された一本以上の細線であって、互いに接続しているものがあれば１つのグループとし、接続しているものがなければ細線１本を１つのグループと定めることである。このステップＳ７０５により定められたグループを図２（ｄ）に示している。図２（ｄ）によれば、ＧＲ１、ＧＲ２、ＧＲ３、２０１、２０５、２０６、２０７、２０８、２０９、２１０の各グループが存在している。
【００６９】
ステップＳ７０５−２では、グループ化手段６２３が、ステップＳ７０３でストロークを開始した個所に最も近い線上の点を始点と定め、ストロークを終了した個所に最も近い線上の点を終点と定めて、メモリ６１３に保存する。図２（ｅ）に始点Ｐ及び終点Ｑを示している。ここで、始点ＰはグループＧＲ１に属しており、終点ＱはグループＧＲ３に属している。
【００７０】
ステップＳ７０５−３でグループ化手段６２３は、グループが複数存在するか否かを判断する。グループが複数存在すると判断された場合には、ステップＳ７０６に進み、各グループ間を接続する接続線を接続線生成手段６２４が生成する。ステップＳ７０６は、図４に示したステップＳ４０１〜Ｓ４２６の各ステップを含んでいる。本実施例では図２（ｅ）に示すように、ステップＳ７０６において始点Ｐを含むグループＧＲ１と始点Ｐ及び終点Ｑのいずれも含まないグループＧＲ２とを接続する接続線２０２を接続線生成手段６２４が生成する。さらに、グループＧＲ２とグループ２０１を接続する接続線２０３と、終点Ｑを含むグループＧＲ３とグループ２０１を接続する接続線２０４とを接続線生成手段６２４が生成する。
【００７１】
一方で、ステップＳ７０５−３においてグループが１つしかないと判断された場合には、接続線を生成する必要がないため、ステップＳ７０６をスキップして後述のステップＳ７０７に進む。
【００７２】
ステップＳ７０７では、枝削除手段６２５が、接続線により接続されていないグループを削除する。図２（ｅ）で言えば、手段６２５はグループ２０５〜２１０を削除する。さらに、手段６２５はいずれかのグループに属する細線であって終端を含むものを他の細線と交差するところまで削除する。図２（ｅ）について言えば、手段６２５が部分２１１〜２１６を削除する。なお、手段６２５は、始点Ｐ及び終点Ｑについては終端と判断せず、したがって削除も行わない。部分２０５〜２１６をまとめて「枝」とも呼ぶ。
以上のようにして、図２（ｅ）から枝が削除された後の細線２ｂを図２（ｆ）に示している。
【００７３】
ステップＳ７０８では、コスト計算手段６２６が細線２ｂのコストを求める。以下、図５（ａ）〜（ｄ）を参照してコストの求め方の一例を説明する。
【００７４】
コストを求めるにあたり、いくつかのパラメータを導入する。まず、ステップＳ３０３において線の二値化を行い、線を片側から１ビット（点）づつ幅を狭くしてゆき、その回数のカウントを行いながら細線化を行う。両側とも細線になるまでの幅を狭くするカウントを行い、両側の数値の平均カウントの切り上げを行う。その細線化されるまでの各点のカウントを、回数線の各ビット（点）に属性として持たせる。細線の各ビットが持つカウント数の総数をＷとする。また、細線の長さをＮとする。
【００７５】
コスト計算手段６２６が、ステップＳ７０６において定まった始点Ｐから終点Ｑまでの距離をＲとしてメモリ６１３に保存する。始点Ｐ及び終点Ｑを図５（ｂ）に示している。
【００７６】
細線２ａを始点Ｐから順にたどるときに、ピクセルに沿って縦又は横にたどるときの長さＬ１を１．０とし、斜めにたどるときの長さＬ２を１．５とする。この様子を図５（ｃ）に示している。コスト計算手段６２６は、このようにして得られる細線２ａの長さをＬとしてメモリ６１３に保存する。
【００７７】
次に、コスト計算手段６２６は、細線２ａの始点Ｐから４ピクセル毎に１ピクセルを抽出し、抽出点としてメモリ６１３に保存する。図５（ｄ）に抽出点Ｔ１及びＴ２を示している。そして、コスト計算手段６２６は、ある抽出点（例えばＴ２）について、その直前の抽出点（Ｔ１）からの方向を抽出点Ｔ２における細線の方向ＥＴ２と定めてメモリ６１３に保存する。
【００７８】
コスト計算手段６２６は、抽出点に最も近いストローク軌跡Ｓ上の点を最近点として、その抽出点と最近点との距離（ピクセル数）を求める。コスト計算手段６２６は、全ての抽出点における距離の総和をＤとしてメモリ６１３に保存する。図５（ｄ）には、抽出点Ｔ２の最近点ＣＴ２と、抽出点Ｔ２と最近点ＣＴ２との距離ＦＴ２を示している。
【００７９】
さらに、コスト計算手段６２６は、最近点におけるストロークの方向（画像上の入力手段の動きの接線方向）と、抽出点における細線の方向（抽出点における細線の接線の方向）の角度差の絶対値を求める。図５（ｄ）には、最近点ＣＴ２におけるストロークの方向ＧＴ２を示している。これにより、ストロークの方向ＧＴ２と細線の方向ＥＴ２との角度差の絶対値が得られる。コスト計算手段６２６は、この角度差の絶対値を抽出点毎に求め、それらの総和をＡとしてメモリ６１３に保存する。さらに、コスト計算手段６２６は抽出点の総ピクセル数をＭとしてメモリ６１３に保存する。
【００８０】
以上のパラメータを用いて、コスト計算手段６２６は、細線を始点ＰからたどるときのコストＣＰを式（１）から求める。式（１）の第１項「１００Ｎ／Ｗ」は、Ｎを分子に持ち、Ｗを分母に持つ。つまり、細線化前の状態において太い線ほど小さい値となる。したがって、太い線ほどコストＣＰの値は小さくなる。これにより、後述するステップＳ７１０〜Ｓ７１３を反復してコストの小さい線を探すことが、すなわち太い線を探すこととなり、太い線が基線と認識されやすくなる。
【００８１】
また、コスト計算手段６２６は、細線を終点ＱからたどるときのコストＣＱを式（２）から求める。式（２）と式（１）との相違点は、式（２）が第４項「＋１８０」を有しているという点である。すなわち、終点からたどるときのコストＣＱは常に値１８０が加算され、始点からたどるときのコストＣＰよりも大きい値となる。これにより、後述するステップＳ７１０〜Ｓ７１２を反復してコストの小さい線を探すことが、始点方向からたどる経路を探すこととなる。つまり、逆方向からたどる経路、すなわち終点からたどる経路は基線と認識されにくくなる。
【００８２】
以上のように、パラメータＷ，Ｎ，Ｒ，Ｌ，Ｄ，Ａ，Ｍを用いて、コスト計算手段６２６はコストを求めることができる。なお、上記式（１）、式（２）ともに経験則から得られる式であって、一例に過ぎない。コストは他の式でも求めることができる。ステップＳ７０８で求められた、始点ＰからたどるときのコストＣＰを図２（ｇ）に示している。
【００８３】
ステップＳ７０９では、経路探索手段６２７が、始点から終点までの任意の一の経路を基準経路と定めて、経路全体のコストを求めメモリ６１３に保存する。基準経路の例を図２（ｈ）の符号Ｒ１で示している。この基準経路Ｒ１全体のコストは２１５（＝８＋１０＋２０＋１８＋３２＋１７＋１１０）である。
【００８４】
ステップＳ７１０では、経路探索手段６２７が、ステップＳ７０９で定めた基準経路以外の経路を一つ選んで選択経路とし、その選択経路全体のコストを求めメモリ６１３に保存する。選択経路の例を図２（ｉ）の符号Ｒ２で示している。この選択経路Ｒ２全体のコストは２１３（＝８＋１０＋２０＋２０＋５＋７＋６＋２＋３＋５＋１７＋１１０）である。
【００８５】
ステップＳ７１１では、経路探索手段６２７が、ステップＳ７０９で求めた基準経路Ｒ１の総コストと選択経路Ｒ２の総コストとを比較し、選択経路のコストの方が小さいか否かを判断する。本実施形態では、選択経路の総コスト（「２１３」）が基準経路の総コスト（「２１５」）よりも小さいため、後述するステップＳ７１２に進む。一方で、選択経路の総コストが基準経路の総コストよりも小さくない場合は、ステップＳ７１２をスキップして後述するステップＳ７１３に進む。
【００８６】
ステップＳ７１２では、経路探索手段６２７が、ステップＳ７１１において基準経路のコストよりも小さいコストを有すると判断された選択経路を基準経路に置き換えてメモリ６１３に保存する。本実施形態では、経路探索手段６２７は、Ｒ２のコストがＲ１のコストよりも小さいため、基準経路をＲ１に代えてＲ２としてメモリ６１３に保存する。
【００８７】
ステップＳ７１３では、始点Ｐと終点Ｑとを結ぶ経路が他にあるか否かを経路探索手段６２７が判断する。他に経路が存在する場合、ステップＳ７１３−２に進み、経路探索手段６２７が複数の経路のコストを算出し、コストの低いものを選択し、コストを最小化する。そしてステップＳ７１４に進む。他に経路が存在しない場合には、ステップＳ３１２−２をスキップしてステップＳ３１３に進む。
【００８８】
ステップＳ７１４では、選択範囲化する手段６２８が、最小コストの線をステップＳ７０４の細線化を行う前の状態に戻して、選択範囲とし、メモリ６１３に保存する。図２（ｊ）に選択範囲２ｃを示している。
さらに、図１（ａ）の線画１における部分１１及び１２にそれぞれ対応する選択範囲を図６に部分１１ａ及び１２ａとして示している。
【００８９】
ステップＳ７１５では、彩色する手段６２９が、選択範囲により隔てられた領域の一方をある色で彩色してメモリ６１３に保存する。本実施形態で定められた選択範囲２ｃにより隔てられた領域の一方をある色で彩色する様子を図２（ｋ）に示している。ここで、符号３０１はカーソルを表しており、符号３０２は入力手段６１１のドラッグ操作により作られる小円である。この小円３０２の領域内であって、選択範囲２ｃにより隔てられた領域３０２１をある色で彩色することができる。さらに、小円３０２の領域内であって、選択範囲２ｃにより隔てられた別の領域３０２２は、ユーザが彩色を意図しない部分であるとして、彩色をしないことができる。
【００９０】
このようにして、大まかにマウスを操作しても、選択範囲により隔てられた領域の一方のみをある色で彩色することができる。
なお、彩色する手段６２９は、選択範囲が存在するレイヤー（参照レイヤー）とは別のレイヤーである彩色した結果を描画するレイヤー（描画先レイヤー）に描画してメモリ６１３に保存することができる。
【００９１】
最後に、ステップＳ７１６で手順を終了する。このようにして塗りつぶされた様子を図２（ｌ）に示している。図２（ｌ）からわかるように、ドラッグした範囲５００のうち、符号５００１で示した領域のみが彩色されており、符号５００２で示した領域は彩色されていない。
【００９２】
本発明の方法及びコンピュータプログラムによれば、塗りあふれ及び塗り残しのいずれもなく線画を彩色することができ、彩色された線画を効率的に製作することができる。
【図面の簡単な説明】
【００９３】
【図１】本発明方法の処理対象となる線画の一例を示す平面図である。
【図２Ａ】本発明の彩色方法により、図１の線画の塗り残し領域が塗りつぶされる過程を示す説明図である。
【図２Ｂ】本発明の彩色方法により、図１の線画の塗り残し領域が塗りつぶされる過程を示す説明図である。
【図３】本発明の彩色方法の手順の一例を示すフローチャートである。
【図４】接続線を生成する手順の一例を示すフローチャートである。
【図５】コストを求める過程についての説明図である。
【図６】本発明の彩色方法により彩色された線画の平面図である。
【図７】本発明のコンピュータプログラムを実行するコンピュータシステム６のブロック図である。
【図８】本発明のコンピュータプログラムの処理手順の一例を示すフローチャートである。
【符号の説明】
【００９４】
１ 線画
１１，１２ 線画１の一部分
１１ａ，１２ａ 選択範囲
２ 線画
２ａ 細線
２ｂ 枝が削除された細線
２ｃ 選択範囲
２０１ 線
２０２〜２０４ 接続線
２１１〜２１６ 枝
３ ストロークされた領域
３０１ カーソル
３０２ 小円
３０２１，３０２２ 領域
５００ ドラッグ領域
５００１、５００２ 領域
６ コンピュータシステム
６１１ 入力手段
６１２ 表示手段
６１３ メモリ
６２１ 画像読込手段
６２２ 細線生成手段
６２３ グループ化手段
６２４ 接続線生成手段
６２５ 枝削除手段
６２６ コスト計算手段
６２７ 経路探索手段
６２８ 選択範囲化する手段
６２９ 彩色する手段
ＧＲ１〜ＧＲ３、２０５〜２１０ グループ
Ｐ 始点
Ｑ 終点
Ｒ１，Ｒ２ 経路
Ｓ ストロークの軌跡
【特許請求の範囲】
【請求項１】
線画を含むある領域に対するストロークを受け付けるストローク受付ステップと、
ストロークされた前記領域にある線画を二値化表現に変換し、線画を構成する線を細線化する細線生成ステップと、
生成された細線であって互いに接続しているものの集まりを１つのグループと定めるグループ化ステップと、
グループに属するピクセルであって、前記ストロークが開始された個所に近いピクセルを始点と定める始点決定ステップと、
グループに属するピクセルであって、前記ストロークが終了された個所に近いピクセルを終点と定める終点決定ステップと、
グループに属する細線であって終端を含むものを他の細線と交差するところまで削除する削除ステップと、
グループに属する細線のコストを求めるコスト計算ステップであって、ここで、前記コストは、二値化表現変換後の細線に含まれるピクセル数を含むいくつかの変数に基づいて計算されるものである、ステップと、
前記コストに基づいて、前記始点と前記終点とを結ぶ経路を探索する経路探索ステップと、
探索された経路を前記細線生成ステップにより細線化する前の状態に戻して選択範囲とする選択範囲化ステップと、
選択範囲化された選択範囲により隔てられた複数の領域のうちの一の領域をある色で彩色する彩色ステップと
を含む、線画における基線を認識し、それに基づいて彩色する方法。
【請求項２】
前記グループ化ステップにより複数のグループが定められた場合には、該グループ化ステップの後であって、かつ前記削除ステップの前に、前記複数のグループの各々に外接する外接矩形の周囲長と該外接矩形間の距離とを含むいくつかの変数に基づいて、グループ間を接続する線を生成する接続線生成ステップをさらに含み、
前記削除ステップは、接続線により接続されていないグループを削除し、生成された接続線を削除しないものである、請求項１に記載の方法。
【請求項３】
前記経路探索ステップは、最小のコストを有する経路を選択するサブステップを含むものである、請求項１に記載の方法。
【請求項４】
線画をメモリに読み込む画像読込手段と、
前記線画を含むある領域に対するストロークを受け付けるための入力手段と、
ストロークされた前記領域にある線画を二値化表現に変換し、線画を構成する線を細線化する細線生成手段と、
生成された細線であって互いに接続しているものの集まりを１つのグループと定め、グループに属するピクセルであって、前記ストロークが開始された個所に近いピクセルを始点と定めるとともに、グループに属するピクセルであって、前記ストロークが終了された個所に近いピクセルを終点と定めるグループ化手段と、
グループに属する細線であって終端を含むものを他の細線と交差するところまで削除する枝削除手段と、
グループに属する細線のコストを求めるコスト計算手段であって、二値化表現変換後の細線に含まれるピクセル数を含むいくつかの変数に基づいてコストを計算するコスト計算手段と、
前記コストに基づいて、前記始点と前記終点とを結ぶ経路を探索する経路探索手段と、
探索された経路を前記細線生成手段が細線化する前の状態に戻して選択範囲化する手段と、
選択範囲化された選択範囲により隔てられた複数の領域のうちの一の領域をある色で彩色する手段と
をコンピュータに実現させる、線画における基線を認識し、それに基づいて彩色するためのコンピュータプログラム。
【請求項５】
前記グループ化手段が複数のグループを定めた場合には、前記複数のグループの各々に外接する外接矩形の周囲長と該外接矩形間の距離とを含むいくつかの変数に基づいて、グループ間を接続する線を生成する接続線生成手段をコンピュータにさらに実現させ、
接続線により接続されていないグループを削除し、生成された接続線を削除しないように前記枝削除手段をコンピュータに実現させる請求項４に記載のコンピュータプログラム。
【請求項６】
前記経路探索手段が、最小のコストを有する経路を選択するものである、請求項４に記載のコンピュータプログラム。
【請求項１】
線画を含むある領域に対するストロークを受け付けるストローク受付ステップと、
ストロークされた前記領域にある線画を二値化表現に変換し、線画を構成する線を細線化する細線生成ステップと、
生成された細線であって互いに接続しているものの集まりを１つのグループと定めるグループ化ステップと、
グループに属するピクセルであって、前記ストロークが開始された個所に近いピクセルを始点と定める始点決定ステップと、
グループに属するピクセルであって、前記ストロークが終了された個所に近いピクセルを終点と定める終点決定ステップと、
グループに属する細線であって終端を含むものを他の細線と交差するところまで削除する削除ステップと、
グループに属する細線のコストを求めるコスト計算ステップであって、ここで、前記コストは、二値化表現変換後の細線に含まれるピクセル数を含むいくつかの変数に基づいて計算されるものである、ステップと、
前記コストに基づいて、前記始点と前記終点とを結ぶ経路を探索する経路探索ステップと、
探索された経路を前記細線生成ステップにより細線化する前の状態に戻して選択範囲とする選択範囲化ステップと、
選択範囲化された選択範囲により隔てられた複数の領域のうちの一の領域をある色で彩色する彩色ステップと
を含む、線画における基線を認識し、それに基づいて彩色する方法。
【請求項２】
前記グループ化ステップにより複数のグループが定められた場合には、該グループ化ステップの後であって、かつ前記削除ステップの前に、前記複数のグループの各々に外接する外接矩形の周囲長と該外接矩形間の距離とを含むいくつかの変数に基づいて、グループ間を接続する線を生成する接続線生成ステップをさらに含み、
前記削除ステップは、接続線により接続されていないグループを削除し、生成された接続線を削除しないものである、請求項１に記載の方法。
【請求項３】
前記経路探索ステップは、最小のコストを有する経路を選択するサブステップを含むものである、請求項１に記載の方法。
【請求項４】
線画をメモリに読み込む画像読込手段と、
前記線画を含むある領域に対するストロークを受け付けるための入力手段と、
ストロークされた前記領域にある線画を二値化表現に変換し、線画を構成する線を細線化する細線生成手段と、
生成された細線であって互いに接続しているものの集まりを１つのグループと定め、グループに属するピクセルであって、前記ストロークが開始された個所に近いピクセルを始点と定めるとともに、グループに属するピクセルであって、前記ストロークが終了された個所に近いピクセルを終点と定めるグループ化手段と、
グループに属する細線であって終端を含むものを他の細線と交差するところまで削除する枝削除手段と、
グループに属する細線のコストを求めるコスト計算手段であって、二値化表現変換後の細線に含まれるピクセル数を含むいくつかの変数に基づいてコストを計算するコスト計算手段と、
前記コストに基づいて、前記始点と前記終点とを結ぶ経路を探索する経路探索手段と、
探索された経路を前記細線生成手段が細線化する前の状態に戻して選択範囲化する手段と、
選択範囲化された選択範囲により隔てられた複数の領域のうちの一の領域をある色で彩色する手段と
をコンピュータに実現させる、線画における基線を認識し、それに基づいて彩色するためのコンピュータプログラム。
【請求項５】
前記グループ化手段が複数のグループを定めた場合には、前記複数のグループの各々に外接する外接矩形の周囲長と該外接矩形間の距離とを含むいくつかの変数に基づいて、グループ間を接続する線を生成する接続線生成手段をコンピュータにさらに実現させ、
接続線により接続されていないグループを削除し、生成された接続線を削除しないように前記枝削除手段をコンピュータに実現させる請求項４に記載のコンピュータプログラム。
【請求項６】
前記経路探索手段が、最小のコストを有する経路を選択するものである、請求項４に記載のコンピュータプログラム。
【図３】
【図４】
【図７】
【図８】
【図１】
【図２Ａ】
【図２Ｂ】
【図５】
【図６】
【図４】
【図７】
【図８】
【図１】
【図２Ａ】
【図２Ｂ】
【図５】
【図６】
【公開番号】特開２０１０−２０４５８（Ｐ２０１０−２０４５８Ａ）
【公開日】平成２２年１月２８日（２０１０．１．２８）
【国際特許分類】
【出願番号】特願２００８−１７８９９５（Ｐ２００８−１７８９９５）
【出願日】平成２０年７月９日（２００８．７．９）
【出願人】（５９６０２１５６２）株式会社セルシス (22)
【Ｆターム（参考）】
【公開日】平成２２年１月２８日（２０１０．１．２８）
【国際特許分類】
【出願日】平成２０年７月９日（２００８．７．９）
【出願人】（５９６０２１５６２）株式会社セルシス (22)
【Ｆターム（参考）】
[ Back to top ]