(57)【特許請求の範囲】
【請求項１】
多階調画像を閾値マトリックスを用いてハーフトーン化する画像処理装置であって、
あらかじめ定められた基本ドット配置点からドットの成長方向を所定の方法で決定することによって大域的な濃度成長を定めるとともに、前記基本ドット配置点から各ドットを中心とする円同士の重なり面積値に基づいてドットの優先順位を決定することによって局所的な濃度成長を定めてなる閾値マトリックスを格納する記憶手段と、
入力される多階調画像と前記記憶手段に格納された前記閾値マトリックスで与えられる閾値とを比較してハーフトーン化画像を得る比較手段と
を備えることを特徴とする画像処理装置。
【請求項２】
マトリックスサイズ、マトリックス縦方向分割成分およびマトリックス横方向分割成分からなる斜交格子パラメータにより斜交格子系が定義されており、各辺が接するようにして前記斜交格子系を並べたときに、平面上にｘ軸、ｙ軸に対してそれぞれ一定の角度を保ち、連続的な斜交格子をなすような格子点配置を前記閾値マトリックスの基本ドット配置点として使用する
ことを特徴とする請求項１記載の画像処理装置。
【請求項３】
多階調画像を閾値マトリックスを用いてハーフトーン化する画像処理方法であって、
あらかじめ定められた基本ドット配置点からドットの成長方向を所定の方法で決定することによって大域的な濃度成長を定めるとともに、前記基本ドット配置点から各ドットを中心とする円同士の重なり面積値に基づいてドットの優先順位を決定することによって局所的な濃度成長を定めてなる閾値マトリックスをあらかじめ用意し、
入力される多階調画像と前記閾値マトリックスで与えられる閾値とを比較してハーフトーン化画像を得る
ことを特徴とする画像処理方法。
【請求項４】
マトリックスサイズ、マトリックス縦方向分割成分およびマトリックス横方向分割成分からなる斜交格子パラメータにより斜交格子系が定義されており、各辺が接するようにして前記斜交格子系を並べたときに、平面上にｘ軸、ｙ軸に対してそれぞれ一定の角度を保ち、連続的な斜交格子をなすような格子点配置を前記閾値マトリックスの基本ドット配置点として使用する
ことを特徴とする請求項３記載の画像処理方法。
【請求項５】
多階調画像をハーフトーン化する際に用いる閾値マトリックスの作成方法であって、
あらかじめ定められた基本ドット配置点からドットの成長方向を所定の方法で決定することによって閾値マトリックスの大域的な濃度成長を定める大域的濃度決定工程と、
前記基本ドット配置点から各ドットを中心とする円同士の重なり面積値に基づいてドットの優先順位を決定することによって閾値マトリックスの局所的な濃度成長を定める局所的濃度決定工程と
を有することを特徴とする閾値マトリックスの作成方法。
【請求項６】
マトリックスサイズ、マトリックス縦方向分割成分およびマトリックス横方向分割成分からなる斜交格子パラメータにより斜交格子系が定義されており、各辺が接するようにして前記斜交格子系を並べたときに、平面上にｘ軸、ｙ軸に対してそれぞれ一定の角度を保ち、連続的な斜交格子をなすような格子点配置を前記閾値マトリックスの基本ドット配置点として使用する
ことを特徴とする請求項５記載の閾値マトリックスの作成方法。
【請求項７】
請求項５または６記載の閾値マトリックスの作成方法においてさらに、
前記大域的濃度決定工程で定められた前記大域的な濃度成長と前記局所的濃度決定工程で定められた前記局所的な濃度成長とから閾値マトリックス全体の閾値配置を決定する閾値配置決定工程を有する
ことを特徴とする閾値マトリックスの作成方法。
【請求項８】
前記大域的濃度決定工程では、あらかじめ定めた前記斜交格子パラメータによって閾値マトリックス内に前記斜交格子を形成し、各斜交格子点から閾値マトリックス内の基本ドット配置点を選択するとともに、その選択した各基本ドット配置点からそれぞれ対応する斜交格子点との距離に基づいた順序でドット成長させ、
前記局所的濃度決定工程では、全基本ドット配置点に各ドットを中心とする円同士の重なり面積値に基づく優先順位を与え、同時に各基本ドット配置点から所定量成長させた全点のうち成長数が等量である点をそれぞれまとめ、それぞれ前記重なり面積値に基づいた優先順位を与える
ことを特徴とする請求項５，６または７記載の閾値マトリックスの作成方法。
【請求項９】
前記大域的濃度決定工程では、あらかじめ定めた前記斜交格子パラメータによって閾値マトリックス内に格子点が整数座標値となる前記斜交格子を形成し、各斜交格子点から閾値マトリックス内に規則的に配置した基本ドット配置点を選択するとともに、その選択した各基本ドット配置点から所定の方向にドット成長させ、
前記局所的濃度決定工程では、全基本ドット配置点に各ドットを中心とする円同士の重なり面積値に基づく優先順位を与え、同時に各基本ドット配置点から所定量成長させた全点のうち成長数が等量である点をそれぞれまとめ、それぞれ前記重なり面積値に基づいた優先順位を与える
ことを特徴とする請求項５，６または７記載の閾値マトリックスの作成方法。
【請求項１０】
請求項７，８または９記載の閾値マトリックスの作成方法においてさらに、
前記閾値配置決定工程で閾値マトリックスの閾値を任意の順で与えた後に、あらかじめ定められた濃度範囲の閾値をとるドットをマトリックス内から選択し、その選択したドットに対して新たに前記重なり面積値に基づく優先順位を与え、選択した濃度における閾値を配置し直すことにより最終的な閾値マトリックスを作成する工程を有する
ことを特徴とする閾値マトリックスの作成方法。
【請求項１１】
前記閾値マトリックス内のドットの優先順位を決定するための前記重なり面積値は、各ドットを中心として理想半径値の円同士を仮想配置した際の円同士の交わり部分の面積総和として定められており、
前記理想半径値は、マトリックス内に所定数の等半径円を充填させて、各円の中心点をマトリックス内に均等に分布させるために理想的な三角格子配置を実現するための円の最大可能半径近似値として定義され、マトリックスサイズと円の数とを変数として定められている
ことを特徴とする請求項７，８，９または１０記載の閾値マトリックスの作成方法。
【請求項１２】
前記閾値マトリックス内のドットの優先順位を決定するための前記重なり面積値は、各ドットを中心として所定半径値の円同士を仮想配置した際の円同士の交わり部分の面積総和を理想半径値を含む所定範囲に含まれる半径値全てについて積分加算した値として定められており、
前記理想半径値は、マトリックス内に所定数の等半径円を充填させて、各円の中心点をマトリックス内に均等に分布させるために理想的な三角格子配置を実現するための円の最大可能半径近似値として定義され、マトリックスサイズと円の数とを変数として定められている
ことを特徴とする請求項７，８，９または１０記載の閾値マトリックスの作成方法。
【請求項１３】
前記閾値マトリックス内のドットの優先順位を決定する際に、あらかじめランダムもしくは所定の方法で対象ドットに優先順位を定めた後に、あらかじめ定めたドット選択順位にしたがって番号の異なる２つのドットを選択し番号を入れ換えた際に、２つの番号間の全ての値に対して前記重なり面積値が入れ換え前よりも良くなっていたら番号の入れ換えを行ったままにし、悪くなっていたら再び番号を入れ替えと元に戻すという処理を、全ての番号に関して２つのドットの入れ替えが一度も発生しなくなるまで行うことにより新たに番号付けし直す
ことを特徴とする請求項７，８，９または１０記載の閾値マトリックスの作成方法。
【請求項１４】
前記大域的濃度決定工程では、前記選択した各基本ドット配置点から所定の方向にドット成長させた際に、ドットの成長がライン型となるように斜交格子の配置から自動的に成長順序を決定する
ことを特徴とする請求項９記載の閾値マトリックスの作成方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像処理装置および画像処理方法、ならびにハーフトーン画像生成用閾値マトリックスの作成方法に関し、特に多階調画像をハーフトーン化（二値化）処理する画像処理装置およびその処理方法、ならびにそのハーフトーン化の際に用いる閾値マトリックスの作成方法に関する。
【０００２】
【従来の技術】
印刷の分野では、多階調画像をハーフトーン化（二値化）する際に、元画像を、予め保存してある閾値マトリックスでタイル状に覆い、画素値の比較を行って比較値の方が閾値よりも大きかったらドットをＯＮ（ＯＮドット／黒ドット）、小さかったらドットをＯＦＦ（ＯＦＦドット／白ドット）することで二値画像を得る一対一比較方式が古くから用いられている。そして、通常、閾値マトリックス内の閾値は網点を形成するように配置されている。
【０００３】
一対一比較方式によるハーフトーン画像は、処理負荷が軽く、また安定した出力が行えるという利点を持っているが、その反面、ドットの集合した網点で元画像を表現するために、分解能が落ちて輪郭のぼやけた画像になるという欠点も併せ持っている。通常印刷では、１００ｌｐｉ（１インチあたり１００個のドットが打たれている網点）程度では網点が目立ち分解能も低い。
【０００４】
そこで、出力解像度に応じて網点の数を増やし、分解能を高めることが行われるが、分解能が高くなると今度は、格子状の模様が見えやすくなり、ハーフトーンの濃度変化がパターンの変化として認識されやすくなるという欠点がある。したがって、ある程度分解能を高めた際にも、格子状模様の見えにくいような閾値マトリックスを作成することが求められる。
【０００５】
カラー出力用のスクリーンを作成する場合には、通常、Ｃ（シアン），Ｍ（マゼンタ），Ｙ（イエロー），Ｋ（ブラック）の４色分のスクリーンを作成しなくてはならない。この場合、４色分のスクリーンをすべて同じ角度、線数を持つ直交格子で作成し、ハーフトーンを掛けて出力すると、出力の際の微妙なずれのために、異なる色のドットの重なり具合がずれてしまうという、いわゆる色モアレが起こり、出力画像を醜くすることが知られている。
【０００６】
このため、カラー出力用には、微妙なずれが起こってもドットの重なり具合に安定性が得られる、各色の網点角度を変えたスクリーンが用いられる（各色の網点線数も要求に合うようにとる）。この際、異なる網点角度の干渉からモアレが発生するという別の問題が発生する。そこで、モアレがロゼッタパターンと呼ばれる、最も目立ちにくいパターンになるように、各色のスクリーン角度がそれぞれ選ばれる。例えば、Ｃ：１５度、Ｍ：７５度、Ｋ：４５度、Ｙ：０度などといった組み合わせがとられる。
【０００７】
【発明が解決しようとする課題】
以上のように、カラー出力用のスクリーンとしては、目標線数が得られ、さらに各色角度を変えてうまくロゼッタパターンが得られるものが必要になる。しかし、実際には例えば１５度や７５度などのように、非有理正接値（ｔａｎ値が分数で表されないもの）の網点格子では、網点格子点をマトリックス内に等間隔に並べることができず、厳密に目標角度を満たすことはできない。
【０００８】
この点に関しては、特開平３−１８７６７６号公報に記載されたスーパータイル方式を用いて、大きなサイズの閾値マトリックス内に形状の異なる小さなセルを配置していくことで、角度をより正確に再現することができる。この方式のスクリーンでは、先ず非有理正接値を有理正接値で近似し、次にこの有理正接値の角度を持つ正方形領域内に、目標線数を実現できるように網点格子を割り当てていく方式を用いている。
【０００９】
この際に、各網点核の配置はマトリックス内に均等でない場合があり、「セルサイズ不均一の問題」と呼ばれる、セルサイズが異なるためにハーフトーン画像にざらつきが現れるという問題が発生する。セルサイズ不均一の問題を解消しないと、出力画像にざらつきが発生して醜くなる。しかしながら、特に６００ｄｐｉなどの低解像度においては、ドットの僅かな偏りが出力画像に反映されるために、セルサイズ不均一の問題の解消は難しい。したがって、低解像度時のスクリーンとしては、有理正接値角度のものが望ましい。
【００１０】
直交網線スクリーンの別の問題点として、各色の目標線数を確保し、さらに各色の網点角度をロゼッタパターンが得られるように作成するには、マトリックスのサイズに大きな制約が掛かるという点がある。ハードウェアでスクリーン処理を行う際には、処理速度の点からスクリーンマトリックスサイズは２nであることが最も望ましい。しかし、各色で目的の網点線数と角度を満たすスクリーンを２nサイズで作成することは難しい。
【００１１】
ハーフトニング法の別の手法としてブルーノイズマスク法がある。ブルーノイズマスク法は、閾値マトリックス内に低周波成分をできる限り取り除き、ドットの分散を均一にさせたブルーノイズパターンを閾値として採用し、一対一比較を行って二値画像を得るという方式である。なお、ここで、ブルーノイズとは、ランダムノイズのうち低周波成分を取り除いた高周波成分からなるランダムノイズを意味する用語として使われている。従って、ブルーノイズパターンは幾何的な見地からは、空間内に均等かつ均質に分散したランダムパターンとみなすことができる。
【００１２】
ブルーノイズマスクの作成法としては、例えば文献「Ｐｒｏｃ．ＳＰＩＥ，１９１３，３３２−３４３（１９９３），Ｒ．Ｕｌｉｃｈｎｅｙ“Ｔｈｅ  Ｖｏｉｄ-ａｎｄ-ｃｌｕｓｔｅｒ  ｍｅｔｈｏｄ  ｆｏｒ  ｄｉｔｈｅｒ  ａｒｒａｙｇｅｎｅｒａｔｉｏｎ”」などが公知である。ブルーノイズマスク法で得られる画像は、微少ドットの増減によって濃淡が表現されているために、網点よりも分解能が高く、格子状模様が見えない。また、ドットがランダムに配置されているため、カラー出力の場合にモアレやロゼッタの心配はない。
【００１３】
しかし、ブルーノイズマスク法では、ドットがランダムであることに起因する局所的なざらつきと、ハーフトーン化の際に周期的にランダムパターンを繰り返して配置することから、マトリックスサイズを周期とする大域的なざらつきが現れやすく、画質の低下につながっている。したがって、ブルーノイズマスク法においては、閾値マトリックス内のドット配置に規則性を持たせたり、ドットの配置をより滑らかにすることが求められている。
【００１４】
また、網点形成によるハーフトーンとブルーノイズ性によるハーフトーンの双方の長所を生かすスクリーン処理も提案されているが、処理負荷が重くなるという問題があり、やはり処理自体は通常の一点比較方式であって、かつ網点とブルーノイズ（ランダムかつ均等均質な点の散らばり）の長所を活かした閾値マトリックス作成法が求められている。
【００１５】
【課題を解決するための手段】
上記課題を解決するために、本発明では、先ず、あらかじめ定められた基本ドット配置点からドットの成長方向を所定の方法で決定することによって閾値マトリックスの大域的な濃度成長を定め、次いで基本ドット配置点から各ドットを中心とする円同士の重なり面積値に基づいてドットの優先順位を決定することによって閾値マトリックスの局所的な濃度成長を定めることで、閾値マトリックスを作成する。そして、この閾値マトリックスを用いて多階調画像をハーフトーン化する。
【００１６】
上記の閾値マトリックスを平面内に繰り返し配置して多階調画像をハーフトーン化した際に、ドットの配置位置がマトリックス周期以下の長さの周期で規則的にかつ周期的に繰り返し、かつ各ドットの大きさおよび成長順序が平面上の各位置で不規則かつ一様になる。
【００１７】
【発明の実施の形態】
以下、本発明の実施の形態について図面を参照して詳細に説明する。
【００１８】
図１は、本発明の一実施形態に係る画像処理装置の構成の一例を示すブロック図である。図１において、本実施形態に係る画像処理装置１０は、描画部（色変換部）１１、二値化処理部１２および描画メモリ１３を有し、外部装置、例えばホストコンピュータ２０から入力される多値画像データに対して所定の処理を施し、その処理後の画像データを画像出力部（ＩＯＴ）３０に対して出力する。
【００１９】
この画像処理装置１０には、ホストコンピュータ２０から例えばＲ（赤）、Ｇ（緑）、Ｂ（青）の８ビットの画像データが入力される。この画像データは、描画部１１でＣ（シアン）、Ｍ（マゼンタ）、Ｙ（イエロー）、Ｋ（ブラック）の８ビットの画像データに色変換されて二値化処理部１２に供給される。この二値化処理部１２で二値化（ハーフトーン化）された画像データは、描画メモリ１３を経由して画像出力部３０に供給される。
【００２０】
二値化処理部１２は、多値画像データをハーフトーン化する処理部であり、図２に示すように、閾値マトリックス記憶部２１および比較部２２を有する構成となっている。閾値マトリックス記憶部２１には、閾値マトリックスがあらかじめ格納される。比較部２２は、入力される多値画像データと記憶部２１に格納されている閾値マトリックスから与えられる閾値データとを比較し、その比較結果に応じた二値化データを網点画像データとして出力する。
【００２１】
上記構成の画像処理装置１０において、二値化処理部１２でのハーフトーン化処理のために、閾値マトリックス記憶部２１にはあらかじめ閾値マトリックスが格納されることになるが、この閾値マトリックスの作成法が本発明の特徴とするところである。この閾値マトリックスは、通常、直交格子または斜交格子を用いて網点の核を生成し、この核から目標の網点形状に合わせた成長を行うことによって作成される。
【００２２】
ここで、空間座標に対して任意角度を持った直交格子を閾値マトリックスに利用したスクリーンが直交格子スクリーンと呼ばれ、格子の交わり角度が９０度以外のものを含む格子から作成されるスクリーン全般が斜交格子スクリーンと呼ばれている。直交格子スクリーンは、斜交格子スクリーンの特別な場合、即ち格子の交わり角度が９０度の場合である。このことから、斜交格子スクリーンは、直交格子スクリーンよりも幅広いスクリーンサイズ、角度、線数の条件を満たすことは明らかである。
【００２３】
以下、本発明において大域的な濃度成長及び局所的な濃度成長を適用させる直接の対象である斜交格子の、本発明固有の構成方法について詳しく説明する。斜交格子は、空間座標のｘ軸、ｙ軸に対して、それぞれ角度θと角度ωの平行直線で作成する。この場合、平行直線の線間隔は固定値をとらなくてはならないが、図３に示すように、それぞれの角度が異なる線間隔ｌ１，ｌ２をとることは可能である。本発明では、図３のような斜交格子を平面上に容易に作成するための方法を提供する。
【００２４】
ここでは先ず斜交格子を一般的に定義し、その性質について考える。以下の数の組み合わせに対して、斜交格子系Ｋ{(ｗ，ｈ),（ｘ１，ｙ１),（ｘ２，ｙ２)}を定義する。
(ｗ，ｈ),（ｘ１，ｙ１),（ｘ２，ｙ２)（ｗ，ｈ：実数，ｗ，ｈ＞０，ｘ１，ｘ２，ｙ１，ｙ２：整数，ｘ１，ｘ２≠０）
ｘ１＜０ならば、ｘ１とｙ１の正負をそれぞれ逆転したものを、ｘ１とｙ１に再度置き直す。ｘ２＜０ならば、ｘ２，ｙ２に関しても同様にする。
【００２５】
図４に示すように、横幅ｗ、縦幅ｈの長方形をとる。次に、ｙ１＞０の場合の整数対（ｘ１，ｙ１）に対応する平行直線群を定義する。長方形の左辺をｌ１，右辺をｌ２とし、左辺ｌ１の下端をｐ（１，０）、上端をｐ（１，ｘ１）、右辺ｌ２の下端をｐ（２，０）、上端をｐ（２，ｘ１）とする。左辺ｌ１をｘ１等分し、各等分点にｐ（１，０）から近い順に、ｐ（１，１），…，ｐ（１，ｘ１−１）と名前を与える。同様に、右辺ｌ２をｘ１等分し、各等分点にｐ（２，０）から近い順に、ｐ（２，１），…，ｐ（２，ｘ１−１）と名前を与える。
【００２６】
さらに、辺ｌ２を点ｐ（２，ｘ１）側に延長し、その延長線上で点ｐ（２，ｘ１）から距離（ｈ／ｘ１）・｜ｙ１｜だけ離れた点を補助点Ｑとする。補助点Ｑは、ｘ１＞ｙ１ならば、長方形の辺ｌ２上の点ｐ（２，｜ｙ１｜）に相当し、ｘ１＜ｙ１ならば、補助点Ｑは長方形外の延長線上にあることになる。図４（ａ）〜（ｃ）はｘ１＞ｙ１の場合について、同図（ｄ）〜（ｆ）はｘ１＜ｙ１の場合について、点の配置例をそれぞれ示している。
【００２７】
次に、点ｐ（１，０）と補助点Ｑとを結んだ際の線分の傾きと同じ傾きを持つ直線で、点ｐ（ｉ，ｊ）（ｉ＝１，２，ｊ＝０，…，ｘ１）を通る全ての直線を長方形内に形成する。以上により、整数対（ｘ１，ｙ１）に対応する平行直線群が形成される。ｙ１＜０の場合には、長方形の右辺をｌ１、左辺をｌ２として、同様の平行直線群を作成する。
【００２８】
整数対（ｘ２，ｙ２），ｙ２＞０に関しては、同じ長方形の、今度は上辺をｌ１、下辺をｌ２とし、上辺ｌ１の左端をｐ（１，０）、右端をｐ（１，ｘ２）、下辺ｌ２の左端をｐ（２，０）、右端をｐ（２，ｘ２）とし、上記と同様の平行直線群を作成する。ｙ２＜０の場合には、下辺をｌ１、上辺をｌ２とし、同様に作成する。以上により得られた長方形とその内部の平行直線群を、まとめて斜交格子系Ｋ{(ｗ，ｈ),（ｘ１，ｙ１),（ｘ２，ｙ２)}を定義する（以下、これを定義１と称する）。
【００２９】
斜交格子系Ｋ{(ｗ，ｈ),（ｘ１，ｙ１）,（ｘ２，ｙ２）}と斜交格子系
【数１】
0004010097.tif 000002
とは等しい（括弧内複号同順、括弧外複号任意）。さらに、斜交格子系Ｋ{(ｗ，ｈ),（ｙ２，−ｘ２),（ｙ１，−ｘ１)}も同じ斜交格子構造をとる（等しい）。また、上下反転、左右反転はともにＫ{(ｗ，ｈ),（ｘ１，−ｙ１),（ｘ２，−ｙ２)}で、９０度回転はＫ{(ｗ，ｈ),（ｘ２，ｙ２),（ｘ１，ｙ１)}となる。
【００３０】
２つの斜交格子系Ｋ{(ｗ，ｈ),（ｘ１，ｙ１),（ｘ２，ｙ２)}に関して、それぞれの左辺と右辺を接したものは斜交格子系Ｋ{(２ｗ，ｈ),（ｘ１，ｙ１),（２ｘ２，ｙ２)}と同じ構造になり、また下辺と上辺を接したものは、斜交格子系Ｋ{(ｗ，２ｈ),（２ｘ１，ｙ１),（ｘ２，ｙ２)}と同じ構造になる。したがって、斜交格子系Ｋ{(ｗ，ｈ),（ｘ１，ｙ１),（ｘ２，ｙ２)}で平面をタイル状に覆うことができ、平面上に斜交格子をすることができる。
【００３１】
斜交格子系Ｋ{(ｗ，ｈ),（ｘ１，ｙ１),（ｘ２，ｙ２)}に対して、上述したように得られる平面上の斜交格子の格子点となるような斜交格子系内の点を、斜交格子系の格子点と呼ぶものとする。但し、斜交格子系の長方形の上辺および右辺上にある点を除外する。また、長方形の下辺と左辺の交点を斜交格子系の原点と呼び、原点から下辺方向にｘ軸、左辺方向にｙ軸をとった際の（ｘ，ｙ）座標値を格子系内の座標と定義する。
【００３２】
斜交格子系Ｋ{(ｗ，ｈ),（ｘ１，ｙ１),（ｘ２，ｙ２)}に関して、次の４つの性質が成り立つ（以下、これを性質１と称する）。
（１）平行直線群の角度は、それぞれ平面のｘ軸、ｙ軸方向に対して以下で与えられる。
ｔａｎ-1（ｈｙ１／ｗｘ１），
ｔａｎ-1（ｗｙ２／ｈｘ２）
（２）平行直線群の平行直線間の距離は、それぞれ以下で与えられる。
ｗ・ｈ／√（ｗ2ｘ１2＋ｈ2ｙ１2），
ｗ・ｈ／√（ｈ2ｘ２2＋ｗ2ｙ２2）
（３）斜交格子系の格子点数は、ｘ１・ｘ２＋ｙ１・ｙ２で与えられる。
（４）以下の数が共に整数ならば、斜交格子系の全格子点は整数座標をとる。
ｗ・ｘ１／（ｘ１・ｘ２＋ｙ１・ｙ２），
ｈ・ｙ１／（ｘ１・ｘ２＋ｙ１・ｙ２）
なお、（３）の値は、長方形の面積を、斜交格子系内にある平行四辺形の面積で割ることによって得ることができる。
【００３３】
例えば、斜交格子系Ｋ{(７２，８４),（７，２),（４，−２)}は、図５に示すようになる。図５では、便宜的に格子点に黒点を付して示している。また、性質１の（１）〜（３）より、
・平行直線群の角度：ｔａｎ-1（１／３），ｔａｎ-1（−７／１２）
・平行直線間の距離：１１．３８４…，１６．５４５…
・格子点数        ：２４（図５の黒点に相当）
となり、性質１の（４）の数を計算すると、共に整数ゆえ、全格子点は整数座標をとる。
【００３４】
上述のようにして得られた斜交格子系は、先述した通り平面をタイルで覆うことができるため、スクリーンのマトリックスとして使用することが可能である。以下、この斜交格子系をそのまま斜交網点スクリーンに使用するための方法と、その際の性質、さらには斜交格子系によりマトリックス内に斜交格子点を配置し、配置した斜交格子点に対して大域的な濃度成長及び局所的な濃度成長を適用させて実際に閾値マトリックスを得る具体的なアルゴリズムについて述べる。
【００３５】
まず、斜交格子系を斜交網点スクリーンに使用するための方法と、その際の性質を説明する。斜交格子系Ｋ{(ｗ，ｈ),（ｘ１，ｙ１),（ｘ２，ｙ２)}を斜交スクリーンへ適用するために、先ず、横幅ｗ、縦幅ｈ（ｗ，ｈは正の整数）の空のスクリーンマトリックスを用意する。そして、斜交格子系Ｋ{(ｗ，ｈ),（ｘ１，ｙ１),（ｘ２，ｙ２)}内の格子点をこの空のスクリーンマトリックスへ写像する。この際に、斜交格子系の格子点が整数座標をとっている場合には、そのままマトリックス内に置き換えれば良いが、整数座標値をとらない場合には、格子点の座標値に最も近い整数座標をマトリックス内の格子点として採用する。
【００３６】
以上により、スクリーンマトリックス内に格子点が定められる。後は、この格子点から網点を成長させていき、最終的にスクリーンマトリックスを得る。
【００３７】
ここで、斜交格子系Ｋ{(ｗ，ｈ),（ｘ１，ｙ１),（ｘ２，ｙ２)}から、サイズがｗ×ｈの解像度ｄw ×ｄh ［dot/inch］用斜交網点スクリーンマトリックスを作成するとする。このとき、先の性質１から次のことが言える。すなわち、斜交格子系Ｋ{(ｗ，ｈ),（ｘ１，ｙ１),（ｘ２，ｙ２)}から、サイズｗ＊ｈの斜交スクリーンを作成し、解像度ｄw ×ｄh ［dot/inch］で出力するとき、出力されるスクリーンは以下の性質を持つ（以下、これを性質２と称する）。
【００３８】
・斜交格子角（単位：度）：
ｔａｎ-1（ｄw ・ｈ・ｙ１／ｄh ・ｗ・ｘ１），
ｔａｎ-1（ｄh ・ｗ・ｙ２／ｄw ・ｈ・ｘ２）
・線数（単位：線／inch）：
√（ｄh 2ｗ2ｘ１2＋ｄw 2ｈ2ｙ１2）／ｗ・ｈ，
√（ｄw 2ｈ2ｘ２2＋ｄh 2ｗ2ｙ２2）／ｗ・ｈ
・分解能（単位：dot／平方inch）：
ｄw ・ｄh （ｘ１・ｘ２＋ｙ１・ｙ２）／ｗ・ｈ
・全体での相当線数（単位：線／inch）：
√ｄw ・ｄh （ｘ１・ｘ２＋ｙ１・ｙ２）/ｗ・ｈ
【００３９】
このように、斜交スクリーンでは、一つのマトリックス内に異なる２つの角度と線数が含まれている。また、特に２つの線数の差が大きい場合には、直交スクリーンと単純に線数の比較ができなくなる場合がある。そのため、「１平行ｉｎｃｈあたりのドット量」の概念を、分解能を図る指標として導入し、この値の平方根をマトリックス全体での相当線数とする。
【００４０】
上記の式を用いれば、サイズｗ＊ｈの解像度ｄw ×ｄh [dot/inch]用斜交網点スクリーンを作成する際に、目的の網点角度、線数を満たすようにパラメータｘ１，ｘ２，ｙ１，ｙ２を選ぶことができる。また、性質１の（４）を用いれば、斜交格子系の格子点が全て整数座標値となるか否かを判断できる。斜交格子系の格子点が全て整数座標値であると、後ほど詳しく説明する大域的な濃度成長を全格子点で一意に定めることができるため、格子点が非整数座標値の場合と比較して、マトリックス全体の生成が行いやすく、出力画像が良好であるという性質がある。
【００４１】
また、より一般に、斜交格子系Ｋ{(ｗ，ｈ),（ｘ１，ｙ１),（ｘ２，ｙ２)}のパラメータを変動させて調べることにより、目的の網点角度、線数、スクリーンサイズを満たし、かつ整数座標をとるスクリーンマトリックスが存在するかどうかを調べることも可能である。このようにして、最適な条件をあらかじめ求めた上で、スクリーンマトリックスを作成することが可能である。
【００４２】
なお、性質２において、２つの斜交角に関する線数が共に全体での相当線数よりも大きくなる場合があるが、この場合には、擬似的に別の角度の格子が低線数で入ってくる場合があるので注意が必要である。一般には、２つの斜交角に関する２つの線数の間に、全体での相当線数が挟まれるような斜交格子系が好ましいと言える。
【００４３】
図５の斜交格子系Ｋ{(７２，８４),（７，２),（４，−２)}から２４００ｄｐｉ用７２×８４サイズ斜交スクリーンマトリックスを作成すると、
・斜交格子角度：ｔａｎ-1（１／３），ｔａｎ-1（−７／１２）
・線数：２１１，１４５［線／inch］
・分解能：２２８５７[dot／平方inch］
・全体での相当線数：１５１[線／inch］相当
となり、性質１の（４）の数を計算すると、共に整数ゆえ、全格子点は整数座標をとる。以上で、斜交格子系を斜交網点スクリーンに使用するための方法と、その際の性質に関する説明を終える。
【００４４】
続いて、実際に、上記の斜交格子を用いて斜交スクリーンを作成するアルゴリズム、つまり斜交格子系によりマトリックス内に斜交格子点を配置し、配置した斜交格子点に対して大域的な濃度成長及び局所的な濃度成長を適用させて実際に閾値マトリックスを得るアルゴリズムについて述べる。本アルゴリズムは、次の３ステップからなる。すなわち、斜交スクリーンを作成するには、図６のフローチャートに示すように、パラメータを準備する工程（ステップＳ１１）と、斜交格子系をマトリックス内に作成する工程（ステップＳ１２）と、マトリックス内に作成された斜交格子系の格子点から網点を大域的に成長させる大域的な濃度成長を定め、斜交格子系の格子点を局所的に成長させる局所的な濃度成長を定め、全階調を割り当てる工程（ステップＳ１３）の各処理を実行する。以下、各工程での処理について具体的に説明する。
【００４５】
先ず、パラメータを準備する工程（ステップＳ１１）では、斜交格子系のパラメータおよびスクリーンパラメータとして、以下の数を変数として導入する。
（１）マトリックスサイズ：ｗ＊ｈ
（２）斜交格子パラメータ１：ｘ１，ｙ１
（３）斜交格子パラメータ２：ｘ２，ｙ２
（４）スクリーンの全階調数：ｃｏｌＳ
（５）微調整パラメータ：（α１，α２）  （０＜α１，α２＜１）
（６）総格子点数：ｄｎ＝ｘ１＊ｘ２＋ｙ１＊ｙ２
（７）斜交格子周期１：ｇｃｄ（ｘ１，ｙ１）  （ｇｃｄ（ｘ，ｙ）は、ｘ，ｙの最大公約数）
（８）斜交格子周期２：ｇｃｄ（ｘ２，ｙ２）  （実際には使用しない）
（９）ドット間ステップ量１：（ｄｘ１，ｄｙ１）＝{(ｗ＊ｘ１)/ｄｎ，（ｈ＊ｙ１)/ｄｎ｝
（10）ドット間ステップ量２：（ｄｘ２，ｄｙ２）＝{(ｗ＊ｙ２)/ｄｎ，（ｈ＊ｘ２)/ｄｎ｝
（11）１階調あたりの総ドット数：ｄｓ＝（ｗ＊ｈ）／ｃｏｌＳ
【００４６】
ここで、ドット間ステップ量は、図７に示すように、斜交格子を構成する単位ベクトルに相当するベクトルである。先述した性質１の（４）の２つの数値は、ｄｘ１，ｄｙ１を意味している。
【００４７】
次に、斜交格子系をマトリックス内に作成する工程（ステップＳ１２）での処理について、図８のフローチャートを用いて説明する。
【００４８】
本工程においては、マトリックス内に斜交格子系Ｋ{(ｗ，ｈ),（ｘ１，ｙ１),（ｘ２，ｙ２)}の格子点を定めるに際し、先ず、ドット位置のカウント数Ｃを０にするとともに、仮ドット位置として（ｘ，ｙ）＝（−ｄｘ１−ｄｘ２＋α１，−ｄｙ１−ｄｙ２＋α２）を与え（ステップＳ２１）、次いでカウント数Ｃをインクリメントする（ステップＳ２２）。
【００４９】
次に、Ｃ−１がｄｎ／ｇｃｄ（ｘ１，ｙ１）で割り切れるか否かを判断し（ステップＳ２３）、割り切れないと判断した場合は、（ｘ，ｙ）＝{(ｘ＋ｗ＋ｄｘ１）％ｗ，（ｙ＋ｈ＋ｄｙ１）％ｈ）とし（ステップＳ２４）、次いでマトリックス内の{(ｉｎｔ）ｘ，（ｉｎｔ）ｙ｝座標を格子点として採用する（ステップＳ２５）。
【００５０】
また、ステップＳ２３で割り切れると判断した場合は、（ｘ，ｙ）＝（ｘ＋ｄｘ２，ｙ＋ｄｙ２）とし（ステップＳ２６）、しかる後ステップＳ２４に移行する。以上の一連の処理を、ステップＳ２７でＣ＝ｄｎ（１階調あたりの総ドット数）と判断するまで繰り返す。
【００５１】
上述した一連の処理により、第１番目のドット位置としては、仮ドット位置に（ｄｘ１，ｄｙ１）を加え、さらに（ｄｘ２，ｄｙ２）を加えた点、即ち点（α１，α２）を定める。第２番目のドット位置としては、第１番目のドット位置に（ｄｘ１，ｄｙ１）を加えた点を定める。一般には、第ｎ番目の点として、第ｎ−１番目の点に（ｄｘ１，ｄｙ１）を加えた点を定める。
【００５２】
但しこのとき、ｘ座標値がｗを上回った場合、周期環境の条件により、座標値からｗを減じた値を採用する（ｙ座標に関しても同じ）。また、格子点を定めて行く際に、ｄｎ／ｇｃｄ（ｘ１，ｙ１）個の格子点ごとに、（ｄｘ２，ｄｙ２）を座標値に加える（これは、既に定めた格子点の上に別の格子点が重なるのを防ぐための処理である）。この際にも、座標値が（ｗ，ｈ）を超したら、周期境界位置のドットに直す。
【００５３】
以上の処理により、マトリックス内にｄｎ個の格子点を得ることができる。この斜交格子系をマトリックス内に作成する手法は、概念的には、斜交格子系から直角三角形を作成し、その斜辺をｄｎ等分し、等分点の各座標をマトリックス内に埋め込んで、格子点とするというようなモデルで考えることができる。
【００５４】
例えば、斜交格子系Ｋ{(ｗ，ｗ),（３，１),（４，１)}、Ｋ{(ｗ，ｗ),（４，２),（４，１)}からマトリックスを得る際のアルゴリズムの概念について説明する。それぞれ、斜交格子の（３，１）成分、（４，２）成分方向への直角三角形を作成する。
【００５５】
斜交格子系Ｋ{(ｗ，ｗ),（３，１),（４，１)}の場合は、図９（Ａ）に示すように、底辺が３ｗとｗの直角三角形の斜辺を１３個（＝３＊４＋１＊１）に分割し、三角形の左下の点をマトリックスの左下の点として、各分割点を三角形の左下の点から順番にマトリックスに落とす。その際に、ｘ座標値がｗよりも大きくなったらその値からｗを減じる。このようにして、マトリックス上に格子点を作成する。一般には、ｙ座標がマトリックスの高さｈを超える場合があり、その場合は同じくその値からｈを減じる。
【００５６】
斜交格子系Ｋ{(ｗ，ｗ),（４，２),（４，１)}の場合は、図９（Ｂ）に示すように、底辺が４ｗと２ｗの直角三角形の斜辺を１８個（＝４＊４＋２＊１）に分割し、同様に分割点をマトリックスに落とす。この場合は、左下から数えて９番目（＝ｄｎ／ｇｃｄ（ｘ１，ｙ１）＝１８／２）の点までは、先程と同様にマトリックスに落とすことができるが、１０番目の点は１番目の点、即ち（０，０）と重なってしまう。
【００５７】
したがって、第１０番目の点をマトリックスに落とす際には、それぞれｘ，ｙ座標値にｄｘ２，ｄｙ２を加算して、位相をずらしたものを用いる。なお、ｄｘ２，ｄｙ２はもう一つの平行格子パラメータ（４，１）から得られる底辺４ｗ，ｗの直角三角形の斜辺を１８等分した際のステップ量に相当している。以降の点も同様に位相をずらして点を作成する（図９（Ｂ）の白点に相当）。このようにしてマトリックス上に格子点を作成する。
【００５８】
一般に、斜交格子系Ｋ{(ｗ，ｈ),（ｘ１，ｙ１),（ｘ２，ｙ２)}を作成する際に、直角三角形の概念を当てはめると、図１０に示すような三角形を用いることとなる。三角形の斜辺上にあるｄｎ＝ｘ１＊ｘ２＋ｙ１＊ｙ２個の格子点（格子点間隔（ｄｘ１，ｄｙ１））をマトリックス内に移して行く際には、ｄｎ／ｇｃｄ（ｘ１，ｙ１）個の格子点ごとに、以降の全格子点を（ｄｘ２，ｄｙ２）だけシフトして配置していく。
【００５９】
次に、マトリックス内に作成された斜交格子系の格子点から、網点の大域的な濃度成長と局所的な濃度成長を行い、全階調を割り当てる工程（ステップＳ１３）での処理について説明する。
【００６０】
この工程では、ステップＳ１２でマトリックス内に定められたｄｎ個の格子点からドットを成長させることによって全階調に対応する閾値を定める。１階調あたりのドット数ｄｓ分だけ各ドットを成長させながら、閾値を作成していく。通常のスクリーンでは、全階調数２５６にとる。
【００６１】
なお、本工程においては、黒ドットを徐々に成長させる方式について述べたが、スクリーン全体で黒ドットと白ドットの対称性を良くする、即ちハイライト部（低濃度部）とシャドー部（高濃度部）のドット配置特性を対称的にする方が、ハーフトーン化が安定することがある。
【００６２】
したがって、このようなスクリーンを作成する場合には、ステップＳ１２で得られた全ての黒ドット用の格子点を、{(ｄｘ１＋ｄｘ２)/２,(ｄｙ１＋ｄｙ２)/２｝＝{(ｗ・（ｘ１＋ｙ２)/２ｄｎ，ｈ・（−ｘ２＋ｙ１)/２ｄｎ｝だけシフトして、周期境界を考慮した位置に白ドット（ＯＦＦドット）発生用の格子点をｄｎ個作成する。このとき、黒ドットに対する白ドットの位置関係は、図１１に示すようになっている。このようにして、あらかじめ黒ドット、白ドット用の格子点をそれぞれｄｎ個用意して、黒ドット、白ドットを交互に成長させてゆけば良い。
【００６３】
例えば、斜交格子系Ｋ{(６４，３２),（８，８),（１２，４)}から６００ｄｐｉ用スクリーンを作成すると、
・格子点数ｄｎ：１２８
・斜交格子角度：ｔａｎ-1（１／２），ｔａｎ-1（２／３）
・線数：１６８，１３５［線／inch］
・分解能：２２５００[dot／平方inch］
・全体での相当線数：１５０[線／inch］相当
となり、性質１の（４）の数（ドット間ステップ量１）を計算すると、共に整数ゆえ、全格子点は整数座標をとる。
【００６４】
ここでは、通常のスクリーンで用いられる２５６階調のスクリーンを作成するとする。
・スクリーンの全階調数：ｃｏｌＳ＝２５６
・微調整パラメータ：（α１，α２）＝（０，０）（全格子点が整数座標ゆえ、微調整はしない）
【００６５】
上記パラメータから以下の数が算出される。
・斜交格子周期１：８
・斜交格子周期２：４
・ドット間ステップ量１：（ｄｘ１，ｄｙ１）＝（４，２）
・ドット間ステップ量２：（ｄｘ２，ｄｙ２）＝（２，３）
・１階調あたりの総ドット数：ｄｓ＝８
【００６６】
以上のパラメータから、ステップＳ１３での処理にしたがってスクリーンマトリックスを作成する。図１２に、斜交格子系Ｋ{(６４，３２),（８，８),（１２，４)}の格子点配置を示す。
【００６７】
ドット間距離パラメータ（ｄｘ１，ｄｙ１),（ｄｘ２，ｄｙ２）が共に整数値をとる場合、マトリックス内の格子点は規則的に並ぶ。このような場合は、次に述べる方法で網点を成長させると良好なドット配置が得られる。
【００６８】
先ず、ドット間距離パラメータ（ｄｘ１，ｄｙ１),（ｄｘ２，ｄｙ２）が整数値の場合の網線成長法について述べる。
【００６９】
既に述べたように、斜交格子系を用いたスクリーンの場合、角度ごとに異なる線数が現れる。仮に各ドットを網点状に成長させて行くと、やがて低線数方向にドットがつながり始め、主に低線数側が目立つようになる。そこで、高線数側にライン状に成長させるという方式を用いて、できるだけ高線数側が主体になるような成長法を採ることとする。
【００７０】
ドット間距離パラメータが整数値の場合、各網点の成長法はすべて同じにできる。したがって、決める必要があるのは、以下の２つである。
（１）ドットの大域的な濃度成長法（一つのドットに関して定めればあとはすべて同じ）
（２）各ドットの局所的な濃度成長順
上記（１）に関しては斜交格子系のパラメータに基づき、一例としてライン型になるようにし、上記（２）に関してはブルーノイズマスク的なランダムかつ均等均質な点の散らばりの概念を用いて（できるだけマトリックス全体で均一に成長させるようにする。以下に、（１），（２）の各アルゴリズムについて説明する。
【００７１】
（１）ドットの大域的な濃度成長法
斜交格子系Ｋ{(ｗ，ｈ),（ｘ１，ｙ１),（ｘ２，ｙ２)｝の（ｘ１，ｙ１）方向の格子をラインで結ぶ形でドット成長させる。斜交格子系内から一つの格子点Ａ＝（ａｘ，ａｙ）を選び、（ｘ１，ｙ１）方向に見て、つなぐ先の格子点Ｂ＝（ｂｘ，ｂｙ）を選ぶ。
【００７２】
先ず、図１３に示すように、点Ａと点Ｂとを結ぶ直線ｆ（ｘ）を作成し、
ｘ＝ａｘ＋ｑ，ａｘ＋１＋ｑ，ａｘ＋２＋ｑ，…，ｂｘ−１＋ｑ  （ｑ＝０．５）
に関して、点（ｘ，ｆ(x))を走査し、この点が含まれるドットに順番を０番から付けていく。ｘ＝ｂｘ−１＋ｑが終了したら、点Ａと点Ｃ＝（ｃｘ，ｃｙ）を直線で結び、この直線上で点Ａから距離αの地点を通るように直線ｆ（ｘ）を平行移動させる。
【００７３】
直線ＡＣと今平行移動させた直線ｆ（ｘ）の交点を始点として、先ほどと同様に、ｘ軸方向に１ずつ直線上を走査して番号を付けていく。このとき、既に番号がつれられたドットに関しては新たに番号付けを行わないようにする。全ての点を調べ終えたら、直線ｆ（ｘ）を再び点Ｃの方向にαだけ平行移動させて同様の走査を行う。
【００７４】
以上の走査は、番号付けされたドット数がｄｎ／２＝（ｘ１＊ｘ２＋ｙ１＊ｙ２）／２になったら一旦終了する。次に、白ドットに関しても同様の方法でドット成長をさせ、ｄｎ／２個のドットに番号付けをしていく。以上により、各ドットのライン型の大域的な濃度成長法が定められる。
【００７５】
なお、ドットの大域的な濃度成長法（１）においては、上記アルゴリズムを用いずに、好ましいドット成長法を任意に用いるようにしても良い。
【００７６】
（２）各ドットの局所的な濃度成長順
黒ドット、白ドットともに成長法則が定められたので、今度は、マトリックス内にあるｄｎ個のドットの成長する順番を決める必要がある。階調数ｃｏｌＳのマトリックスを作成する場合、各閾値はマトリックス内にｗ＊ｈ／ｃｏｌＳだけ定める。ｄｎ＝ｗ＊ｈ／ｃｏｌＳであれば網点の成長はたやすいが、そうでない場合には、マトリックス全体で濃度を調整する手法が必要になる。
【００７７】
そこで、先ずマトリックス内のｄｎ個の全黒ドットに、０からｄｎまでの順番を以下の法則を用いて割り振ってゆき、この順番と先のドットの成長法で定めた各網点の成長法を組み合わせて閾値決定を行う。このようにしてマトリックス内の格子点に順番を与えていく。マトリックス内の格子点全体の集合をＫとおく。また、マトリックス内には周期境界条件を付けて、ユークリッドの距離を入れておく。その具体的な処理手順について、図１４のフローチャートに沿って説明する。
【００７８】
先ず初めに、０からｄｎ−１までの閾値を決定していく順番をｐ（ｎ）（ｎ＝０，…，ｄｎ−１）で決める（ステップＳ３１）。ここで、ｐ:{０，…，ｄｎ−１｝→｛０，…，ｄｎ−１｝は一対一写像とする。次に、マトリックス内のｄｎ個の格子点に０からｄｎ−１までの番号を、同じ番号が重複しないようにランダムに与える（ステップＳ３２）。
【００７９】
閾値決定の一番はじめとして、ｎ＝０，チェック値Ｃｈ＝０とし（ステップＳ３３）、ｑ＝ｐ（ｎ）＋１とおく（ステップＳ３４）。続いて、閾値ｐ（ｎ）に対応する画素Ｐを選び、クラスター量Ｃｌ（Ｐ，ｐ（ｎ），ｑ）を測定する（ステップＳ３４）。その後、閾値ｑに対する画素Ｑを選び、ＰとＱの閾値を入れ換え（ステップＳ３６）、点Ｑのクラスター量Ｃｌ（Ｑ，ｐ（ｎ），ｑ）を測定する（ステップＳ３７）。なお、ここでクラスター量Ｃｌとは、画素Ｐの周囲にある閾値ｐからｑの範囲に含まれる閾値を伴った他の画素（ドット）が、Ｐの周りにどの程度密に集まっているかの指標である。クラスター量が小さいほどＰの周りに閾値ｐからｑの間に含まれる他の画素がまばらであり、大きいほど他の画素が密に存在することを意味する。クラスター量Ｃｌの詳しい数学的な定義は後述するが、本発明では、このように画素が密であるか否かの指標であるクラスター量を、各画素から等半径の円を描いた際の円同士の交わり部分の面積総和によって定めてゆく。つまり、この面積総和が大きいほど点が密集していることになり、クラスター量が増大するとするのである。
【００８０】
そして、画素Ｐのクラスター量Ｃｌ（Ｐ，ｐ（ｎ），ｑ）と画素Ｑのクラスター量Ｃｌ（Ｑ，ｐ（ｎ），ｑ）とを比較する（ステップＳ３８）。ここで、Ｃｌ（Ｐ，ｐ（ｎ），ｑ）＜Ｃｌ（Ｑ，ｐ（ｎ），ｑ）ならば、該閾値ｐは元の位置にある方が他の画素間との距離がより開いているということになるため、再びＰとＱの閾値を入れ換えて元の状態に戻す（ステップＳ３９）。その後、ｑ＝ｄｎ−１になったか否かを判断し（ステップＳ４０）、ｑ≠ｄｎ−１であれば、ｑ＝ｑ＋１とし（ステップＳ４１）、しかる後ステップＳ３５に戻って上述した一連の処理をｑ＝ｄｎ−１になるまで続ける。
【００８１】
ステップＳ３８でＣｌ（Ｐ，ｐ（ｎ），ｑ）≧Ｃｌ（Ｑ，ｐ（ｎ），ｑ）と判定した場合は、Ｑの方が良い閾値配置ということになるため、このままＱをＰに入れ換えてしまう。そして、一度でもＰとＱが入れ替わったならば、チェック値Ｃｈ＝１とする（ステップＳ４２）。ｑ＝ｄｎ−１となったら、続いてｎ＝ｄｎ−１になったか否かを判断する（ステップＳ４３）。ｎ≠ｄｎ−１であれば、ｎ＝ｎ＋１とし（ステップＳ４３）、しかる後ステップＳ３４に戻って上述した一連の処理をｎ＝ｄｎ−１となるまで繰り返す。
【００８２】
そして、ｎ＝ｄｎ−１になったならば、全閾値のより良い場所への再配置が終わったことになるが、ステップＳ４５でＣｈ＝１と判定した場合は、ステップＳ３３に戻り、再びｎ＝０として上述した一連の処理を繰り返す。Ｃｈ≠１、即ちＣｈ＝０の場合には、全ての閾値が動かなかったことになるため、収束状態とみなし、閾値決定のための一連の処理を終了する
【００８３】
上述した処理において、点Ｐ∈Ｋのクラスター量Ｃｌ（Ｐ，ｐ（ｎ），ｑ）は次で定める。以下において、ｄ（Ｐ，Ｑ）は点Ｐと点Ｑ間の距離を表し、ｖａｌ（Ｐ）は点Ｐの閾値を表す。
【００８４】
【数２】
0004010097.tif 000003
【００８５】
クラスター量Ｃｌ（Ｐ，ｐ（ｎ），ｑ）は、点Ｐにおいて濃度ｉをｐ（ｎ）からｑまで変化させたときの各閾値でのクラスター量ｃｌ（Ｐ，ｉ）の和で定められる。各閾値でのクラスター量ｃｌ（Ｐ，ｉ）は、マトリックス内の格子点のうち、閾値ｉ以下の点を中心に理想半径値ｒ（ｉ）の円を作成した際に、点Ｐを中心とする円と交わった円Ｑの、交わり面積ｆ（Ｐ，Ｑ，ｑ）の総和で定義する。
【００８６】
ここで、理想半径値ｒ（ｉ）は、サイズｗ＊ｈの周期境界を持った長方形内にｉ＋１個の同じ大きさの円を交わらないように詰め込み配置する際の、円半径の許容最大値の近似値である。なおこの近似値ｒ（ｉ）は、周知の事実である「平面上の最密円詰め込み状態は三角格子状配置（Ｈｅｘａｇｏｎａｌ  Ｐａｃｋｉｎｇ）に他ならない」ことを利用して、サイズｗ＊ｈ内にｉ＋１個の円を三角格子状に詰め込む際の円の半径値の最大値の近似値として算出した値である。図１５は、ｃｌ（Ｐ，ｉ）値の計算の概念図である。クラスター量Ｃｌ（Ｐ，ｐ（ｎ），ｑ）は、ｐ（ｎ）＜ｉ＜ｑなるｉに関してｃｌ（Ｐ，ｉ）を求めて総和をとったものである。つまり、最も理想的な状態として、ｗ＊ｈ長方形内に半径ｒ（ｉ）の円をｉ＋１個交わらないように詰め込む場合を想定し、この場合には、各円のクラスター量（円同士の交わり面積）ｃｌ（Ｐ，ｉ）はいずれも０となり、従って全体としてのクラスター量Ｃｌ（Ｐ，ｐ（ｎ），ｑ）も０となり、最も理想的な配置状態であるということになる。そして、クラスター量Ｃｌが増大するほど、各円同士の交わり部分の面積和が増大することとなり、円の配置状態が理想的な詰め込み状態から離れていることになる。なお、クラスター量Ｃｌがより小さくなると円同士の交わり部分の面積値が小さいことを意味するが、これは同時に円の中心点同士がお互いに離れていることを意味している。
【００８７】
ここにおいて、閾値ｐ（ｎ）とｑを入れ換えた際に、閾値ｐ（ｎ）とｑの間のクラスター量を計算する理由を述べる。図１６に示すように、閾値ｐ（ｎ）とｑを入れ換えた際に、実際のハーフトーンのパターンが変化するのは閾値ｐ（ｎ）とｑの間の領域のみである。そこで、この閾値ｐ（ｎ）とｑの間の全閾値に対して、閾値ｐ（ｎ）とｑを交換した際のドット配置の良さを測定して、和をとるという操作を行う。
【００８８】
ところで、上記のクラスター量ｃｌ（Ｐ，ｉ）の計算においては、白ドットと黒ドット別にクラスター量を測定する場合には、閾値の変形を行えば良い。その際に、理想半径値ｒ（ｉ＋１）も対象とするドットの個数に応じて変化させる。また、ｆ（Ｐ，Ｑ，ｉ）値は単純な円の重なり部分の面積を求める式であるが、ドット数が増大してくると、マトリックスが離散空間であることに起因して、ドット配置に強い制約が掛かってくる。
【００８９】
そのため、最適半径値よりも少し大きな値を用いるか、一定範囲内で積分したものをｆ（Ｐ，Ｑ，ｉ）に用いる方が良い場合があり、こうした値を利用することも可能である。このように、クラスター量の決定を行う関数は、マトリックスの離散的特性に応じて変形した方がより良い結果が得られる場合があり、適当な方法を採るようにする。
【００９０】
以上のようにして、マトリックス内に定義された格子点（網点）の局所的な濃度成長法（成長順）が定められ、ｄｎ個の各格子点には０からｄｎ−１までの番号が一意に割り当てられる。以降の処理では、これらを用いて最終的な閾値マトリックスの作成が行われる。
【００９１】
先ず、閾値マトリックス内の全点（ｘ，ｙ）に、先のドットの大域的な濃度成長法で定められた成長順番号ｐを振る。このとき、０からｗ＊ｈ／ｄｎ−１までの値がそれぞれｄｎ個割り振られることになる。次に、閾値マトリックス内の各格子点に先のドットの局所的な濃度成長順で定められた番号ｑを振り、各格子点の第１成長点から第ｗ＊ｈ／ｄｎ成長点までにもそれぞれ同じ番号ｑを振る。
【００９２】
この時点で、閾値マトリックス内の全点にはｐとｑの２種類の番号が割り与えられている。そこで、マトリックス内の全点に対して、新たにｐ＊ｄｎ＋ｑという番号を割り当て直す。これによって、閾値マトリックス内には０からｗ＊ｈ−１までの番号が一意に割り当てられる。最後に、閾値に割り当てられた値を階調数ｃｏｌＳで割った値の整数部分を最終的な閾値として採用する。こうして、階調数ｃｏｌＳの閾値マトリックスが得られる。
【００９３】
また、容易にわかるように、網点の大域的な濃度成長順の順序と網点の局所的な濃度成長順の順序から、閾値マトリックス内の全ての画素にユニークに優先順位を付けることができる。つまり、全部の画素を番号順に並べることができる。そこで、その番号順に適宜ドットを選択していくことで、閾値の数が異なるようなマトリックスを得ることも可能である。
【００９４】
次に、ドット間距離パラメータ（ｄｘ１，ｄｙ１),（ｄｘ２，ｄｙ２）が非整数値の場合の網線成長法について述べる。ドット間距離パラメータが非整数の場合、概念的には、Ａｄｏｂｅのスーパーセル方式スクリーンでのセルサイズ不均一の問題と同様の問題が発生するが、ここでは単純に、格子点が非整数座標となる場合の網点成長法について簡単に述べる。
【００９５】
先ず、斜交格子系からマトリックス内に格子点を作成する際には、斜交格子点に最も近い整数座標値をマトリックス内の格子点として採用する。次に、網点の大域的な濃度成長法に関しては、指数座標値をとる場合とは違って、各ドットをすべて均一の成長順にすることはできない。
【００９６】
そこで、先ず各ドットの２番目の成長点として、既に定めたマトリックス内の格子点以外で、斜交格子系の格子点に最も近い点をそれぞれ選び、以下３番目の成長点、４番目の成長点に関しても同様に、まだマトリックス内で選ばれていない点で、斜交格子系の格子点に最も近い点を選んでいく。こうして全ての点を選び終えたら、上記と同様の方法で網点の局所的な濃度成長順を決めて、最終的な閾値マトリックスを得ることができる。
【００９７】
最後に、好適な実施例として、斜交格子系Ｋ{(６４，６４),（１６，８),（１２，８)｝から、６００ｄｐｉ用スクリーンを作成する（高線数側線数は１６８で全体１５０線相当）場合について説明する。この場合、スクリーンの格子構造は、先述した斜交格子系Ｋ{(６４，３２),（８，８),（１２，４)｝から６００ｄｐｉ用スクリーンを作成する場合と全く同じものとなる。
【００９８】
本例の場合、ｄｎ＝２５６となるため、２５６個の全斜交格子点に対して局所的な濃度成長順ｑ（０からｄｎ−１＝２５５までの番号）与えて、更に各格子点共通に大域的な濃度成長順ｐ（０からｄｓ−１＝１５までの番号）を与えれば、全格子点にｐ＊２５６＋ｑの濃度成長順が定められ、マトリックス内の全点に対して０から６４ｘ６４−１＝４０９５までの番号が与えられる。最後にこの成長順を総階調数ｃｏｌＳ＝２５６で割れば、最終的に所望の０から２５５までの番号が与えられた閾値マトリックスが得られる。このように構成した閾値マトリックスは、１６階調おきに大域的な成長順によって定められた位置に格子点全点の点灯位置を移動し、各１６ｎ階調から１６（ｎ＋１）階調の間は、局所的な成長順によってマトリックス全体にわたってランダムかつ均一に定められた位置から１階調おきに徐々に点灯する、という性質を持つ。こうして作成されたマトリックスでハーフトーン化したグラデーションを図１７（Ｂ）に示す。図１７（Ａ）は、Ｈｏｍｏｇｅｎｅｏｕｓ型（等方規則的）に成長させた場合のマトリックスでハーフトーン化したグラデーションである。また、図１８（Ａ），（Ｂ）にはそれぞれ、これらスクリーンの１６階調までのドット配置を示している。残りの階調も、１６階調おきにこのパターンが繰り返される。
【００９９】
【発明の効果】
以上説明したように、本発明によれば、網点スクリーンで目的の線数、角度を満たすスクリーンを得る場合であっても、マトリックスのサイズに大きな制約がかかることはなく、しかも網点スクリーンで線数を高めても、格子状の模様が見えることもない。
【図面の簡単な説明】
【図１】  本発明の一実施形態に係る画像処理装置の構成の概略を示すブロック図である。
【図２】  二値化処理部の構成の一例を示すブロック図である。
【図３】  平面上に作成した斜交格子を示す図である。
【図４】  斜交格子系を作成する説明図である。
【図５】  斜交格子系Ｋ{(７２，８４),（７，２),（４，−２)｝を示す図である。
【図６】  斜交スクリーンを作成するアルゴリズムを示すフローチャートである。
【図７】  ドット間ステップ量を示す図である。
【図８】  斜交格子系をマトリックス内に作成する処理手順を示すフローチャートである。
【図９】  斜交格子系Ｋ{(ｗ，ｗ),（３，１),（４，１)}とＫ{(ｗ，ｗ),（４，２),（４，１)}の直角三角形表現の概念図である。
【図１０】  斜交格子系Ｋ{(ｗ，ｈ),（ｘ１，ｙ１),（ｘ２，ｙ２)}の直角三角形の概念図である。
【図１１】  黒ドット格子点に対する白ドット格子点の位置関係を示す図である。
【図１２】  斜交格子系Ｋ{(６４，３２),（８，８),（１２，４)}の格子点配置を示す図である。
【図１３】  ドットの大域的な濃度成長法の一例を示す説明図である。
【図１４】  各ドットの局所的な濃度成長順を決定する処理手順を示すフローチャートである。
【図１５】  クラスター量ｃｌ（Ｐ，ｉ）値の計算の概念図である。
【図１６】  閾値ｐ（ｎ）とｑを交換した際にパターンが変化する領域を示す図である。
【図１７】  ハーフトーン化したグラデーションを示す図であり、（Ａ）はＨｏｍｏｇｅｎｅｏｕｓ型（等方規則的）に成長させた場合を、（Ｂ）は本実施形態に係る場合をそれぞれ示している。
【図１８】  図１７（Ａ），（Ｂ）の場合における１６階調までのドット配置を示す図である。
【符号の説明】
１０…画像処理装置、１１…描画部（色変換部）、１２…二値化部、１３…描画メモリ、２０…ホストコンピュータ、２１…閾値マトリックス記憶部、２２…比較部、３０…画像出力部（ＩＯＴ）
【図１】
0004010097.tif 000004
【図２】
0004010097.tif 000005
【図３】
0004010097.tif 000006
【図４】
0004010097.tif 000007
【図５】
0004010097.tif 000008
【図６】
0004010097.tif 000009
【図７】
0004010097.tif 000010
【図８】
0004010097.tif 000011
【図９】
0004010097.tif 000012
【図１０】
0004010097.tif 000013
【図１１】
0004010097.tif 000014
【図１２】
0004010097.tif 000015
【図１３】
0004010097.tif 000016
【図１４】
0004010097.tif 000017
【図１５】
0004010097.tif 000018
【図１６】
0004010097.tif 000019
【図１７】
0004010097.tif 000020
【図１８】
0004010097.tif 000021