(57)【特許請求の範囲】
【請求項１】
距離マッピングによってランレングス符号化された画像データの形式で存在する印刷頁の色境界にトラッピングフレーム（３）を発生するための方法であって、
ランレングス（６）は同一の色の画素のシーケンスを表す、
距離マッピングによってランレングス符号化された画像データの形式で存在する印刷頁の色境界にトラッピングフレーム（３）を発生するための方法において、
前記ランレングス（６）を画素のマトリクスに復号化することなしに、別の色（２）を有する領域（７）までの前記ランレングス（６）の距離が決定され、
ランレングス（６）は開始点Ａから終了点Ｅまでの画素のシーケンスを記述し、
前記別の色（２）を有する領域（７）までの開始点Ａ及び終了点Ｅの間隔を表す間隔ベクトルＤＡ及びＤＥが決定され、
前記ランレングス（６）の距離はこれらの間隔ベクトルに基づいて決定され、
前記トラッピングフレーム（３）はもとめられた距離に基づいて次のように発生される、すなわち、
２つの間隔ベクトル（ＤＡ；ＤＥ）の絶対値の距離（｜ＤＡ｜；｜ＤＥ｜）がトラッピング幅ｗより小さいか又は等しい場合には、前記ランレングス（６）は発生される前記トラッピングフレーム（３）に所属し、又は、
前記２つの間隔ベクトル（ＤＡ；ＤＥ）のうちの一方だけの前記絶対値の距離（｜ＤＡ｜；｜ＤＥ｜）が前記トラッピング幅ｗより小さいか又は等しい場合には、発生される前記トラッピングフレーム（３）に所属する部分区間（Ｌｕ）が前記ランレングス（６）から分割され、又は、
前記２つの間隔ベクトル（ＤＡ；ＤＥ）の前記絶対値の距離（｜ＤＡ｜；｜ＤＥ｜）が前記トラッピング幅ｗより大きい場合には、前記ランレングス（６）は発生される前記トラッピングフレーム（３）に所属しないことを特徴とする、距離マッピングによってランレングス符号化された画像データの形式で存在する印刷頁の色境界にトラッピングフレーム（３）を発生するための方法。
【請求項２】
ランレングス（６）の開始点（Ａ）及び終了点（Ｅ）に対して間隔ベクトル（ＤＡ；ＤＥ）が決定され、
現在注目するランレングス（Ｌ０）の間隔ベクトルに対して隣接するランレングスの間隔ベクトルとの比較から新たな値（ＤＡ＿ｎｅｕ；ＤＥ＿ｎｅｕ）が計算され、
前記新たな値の絶対値の間隔（｜ＤＡ＿ｎｅｕ｜；｜ＤＥ＿ｎｅｕ｜）が従来の値の絶対値の間隔（｜ＤＡ＿ａｌｔ｜；｜ＤＥ＿ａｌｔ｜）よりも小さい場合には、前記新たな値（ＤＡ＿ｎｅｕ；ＤＥ＿ｎｅｕ）は前記現在注目するランレングス（Ｌ０）の間隔ベクトル（ＤＡ＿ａｌｔ；ＤＥ＿ａｌｔ）の従来の値と置き換えられることを特徴とする、請求項１記載の方法。
【請求項３】
ランレングス（６）は画像データの最初のスキャンにおいて列毎に上から下へと及び各列において左から右へと処理され、現在注目するランレングス（Ｌ０）の間隔ベクトル（ＤＡ；ＤＥ）は同一の列及びその上にある列の隣接するランレングス（Ｌ１；Ｌ２；Ｌ３；Ｌ４）の間隔ベクトル（ＤＡ；ＤＥ）と比較され、
前記ランレングス（６）は画像データの第２のスキャンにおいて列毎に下から上へと及び各列において右から左へと処理され、前記現在注目するランレングス（Ｌ０）の前記間隔ベクトル（ＤＡ；ＤＥ）は同一の列及びその上にある列の隣接するランレングス（Ｌ５；Ｌ６；Ｌ７；Ｌ８）の間隔ベクトル（ＤＡ；ＤＥ）と比較されることを特徴とする、請求項１又は２記載の方法。
【請求項４】
現在注目するランレングス（Ｌ０）の間隔ベクトル（ＤＡ；ＤＥ）は隣接するランレングス（Ｌ１；Ｌ２；Ｌ３；Ｌ４）乃至は（Ｌ５；Ｌ６；Ｌ７；Ｌ８）の各間隔ベクトル（ＤＡ；ＤＥ）と比較されることを特徴とする、請求項１〜３のうちの１項記載の方法。
【請求項５】
間隔ベクトル（ＤＡ；ＤＥ）はｘ成分及びｙ成分から成り、
比較されるランレングスが異なる色を有する場合には、現在注目するランレングス（Ｌ０）の間隔ベクトルの新しい値の成分（ＤＡｘ＿ｎｅｕ；ＤＡｙ＿ｎｅｕ；ＤＥｘ＿ｎｅｕ；ＤＥｙ＿ｎｅｕ）に対して、ｘ成分に対する列方向の及びｙ成分に対する列方向に垂直の比較される開始点（Ａ）乃至は終了点（Ｅ）の間隔が使用されるか、又は、
比較されるランレングスが同じ色を有する場合には、ｘ成分に対する列方向の及びｙ成分に対する列方向に垂直の比較される開始点（Ａ）乃至は終了点（Ｅ）の間隔が比較される隣接するランレングス（Ｌ１；Ｌ２；Ｌ３；Ｌ４）乃至は（Ｌ５；Ｌ６；Ｌ７；Ｌ８）の間隔ベクトルの成分（ＤＡｘ；ＤＡｙ；ＤＥｘ；ＤＥｙ）に加算されることによって、現在注目するランレングス（Ｌ０）の間隔ベクトルの新しい値の成分（ＤＡｘ＿ｎｅｕ；ＤＡｙ＿ｎｅｕ；ＤＥｘ＿ｎｅｕ；ＤＥｙ＿ｎｅｕ）が計算されることを特徴とする、請求項１〜４のうちの１項記載の方法。
【請求項６】
最初のスキャンにおける隣接するランレングス（Ｌ２；Ｌ３）との間の境界の下の現在注目するランレングス（Ｌ０）は乃至は第２のスキャンにおける隣接するランレングス（Ｌ６；Ｌ７）の間の境界の上の現在注目するランレングス（Ｌ０）は分割されることを特徴とする、請求項１〜５のうちの１項記載の方法。
【請求項７】
隣接するランレングス（Ｌ２；Ｌ３）乃至は（Ｌ６；Ｌ７）の少なくとも１つの間隔ベクトル（ＤＡ；ＤＥ）の絶対値の距離（｜ＤＡ｜；｜ＤＥ｜）がトラッピング幅ｗより小さいか又は等しい場合にのみ、現在注目するランレングス（Ｌ０）は分割されることを特徴とする、請求項６記載の方法。
【請求項８】
距離マッピングの間に、現在注目するランレングス（Ｌ０）の色が比較される隣接するランレングス（Ｌ１；Ｌ２；Ｌ３；Ｌ４）乃至は（Ｌ５；Ｌ６；Ｌ７；Ｌ８）の色に対してトラッピングされるべきかどうかが検査され、
当該色境界に対してトラッピングフレーム（３）が発生されるべきではない場合には、現在注目するランレングス（Ｌ０）は、あたかも比較されるランレングスが前記現在注目するランレングス（Ｌ０）と同じ色を有するかのように処理されることを特徴とする、請求項１〜７のうちの１項記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ランレングスは同一の色の画素のシーケンスを表す、距離マッピングによってランレングス符号化された画像データの形式で存在する印刷頁の色境界にトラッピングフレームを発生するための方法に関する。
【０００２】
【従来の技術】
本発明は再現技術におけるディジタル処理の領域に関係し、さらに印刷頁の色境界にトラッピングフレームを発生するための方法に関する。このようなトラッピングフレームは印刷機でレジスタエラーにより発生された障害、すなわちエラーの低減のために使用され、このエラーは印刷色が正確にぴったりと重ね印刷されずに、少し互いにずれてしまうことによって生じる。
【０００３】
再現技術では印刷頁のための印刷原稿が生成され、これらの印刷原稿はテキスト、グラフィックオブジェクト及び画像のようなあらゆる印刷すべき要素を含む。印刷原稿の電子的な作製の場合にはこれらの要素がディジタルデータの形式で存在する。例えば、画像がスキャナにおいて画素毎に及び列毎に走査され、各画素が色成分に分解され、これらの成分の色値がディジタル化されることによって、画像のデータが発生される。テキスト及びグラフィックオブジェクトのデータは一般にテキスト処理及びキャラクタプログラム（Zeichenprogramme）によって直接コンピュータにおいて発生される。後で使用される出力プロセス、例えばカラープリンタにおける出力又は従来の印刷機における印刷に応じて、頁要素のためのデータは色成分、赤、緑及び青（ＲＧＢ）又は４色印刷の印刷色、シアン、マゼンタ、黄、黒（ＣＭＹＫ）で発生され、格納される。印刷色はカラープリンタ乃至は印刷機において相互に重ねて印刷素材（例えば紙）に印刷される。
【０００４】
後続の作業工程においてディジタル化されたテキスト、グラフィックオブジェクト及び画像は処理ステーションで目視によりカラーモニタにおいて多様なやり方でレイアウトの設定に従って処理され、例えば色彩的に訂正されるか又は配置及び形において変更され、最後に印刷頁に組み合わされる。印刷頁データは次いで出力に適したデータフォーマットに、例えば頁記述言語ポストスクリプトに変換され格納される。この場合、印刷色ＣＭＹＫ毎に別個の印刷頁データが生成され、これら別個の印刷頁データは色分解データと呼ばれる。色分解データはフィルムレコーダ乃至はプレートレコーダによって高い解像度でフィルム材料に又は直接刷版に記録される。ディジタル印刷機もあり、このディジタル印刷機は刷版なしで作動する。この場合、色分解データは直接ディジタル印刷機に伝送され、そこで印刷素材に印刷される。
【０００５】
印刷技術における問題は印刷機におけるレジスタエラー、すなわち紙が次々に走行する印刷機械において印刷色が正確にぴったりと重ね印刷されず、少し互いにずれてしまうことによって生じるエラーである。これらのエラーを簡単な例において説明しよう。この簡単な例では黒い背景面に赤い円が印刷される。図１のａ及びｂは色分解Ｙ及びＭを示し、これらの色分解の重ね印刷から甘い円が生じ、図１のｃは黒い背景面の色分解Ｋを示し、この黒い背景面において円の面は空白にされている。図２は、色分解Ｙ、Ｍ及びＫが印刷機で正確に重ね印刷された場合の印刷結果を示す。色分解Ｙ及びＭは色分解Ｋの空白にされた円面を完全に充填している。図３は印刷機においてレジスタエラーが生じた場合の印刷結果を示す。この例では色分解Ｋが色分解Ｙ及びＭに対して右上方にずれており、この結果、色分解Ｙ及びＭは色分解Ｋの空白にされた円面をもはや完全には充填しておらず、印刷されていないストリップ１が生じている。印刷されていないストリップ１は紙の色を有し、すなわち通常は白であるので、この印刷されていないストリップは赤色と黒色との間で非常に目立ち、目障りと感じられる。色分解のずれによってストリップ２も生じ、このストリップ２において３つの色分解Ｙ、Ｍ及びＫの全てが重なり合って印刷されている。ここでは比較的明るい印刷色Ｙ及びＭが暗い印刷色Ｋの上に印刷されるので、ストリップ２も同様に暗く、印刷結果において目障りではない。図３でははっきり示すために色分解の非常に大きなずれが示されている。しかし、実際の印刷動作において生じるような比較的僅かなずれの場合でもこれによって生じる印刷されていないストリップは非常に目障りであり、このエラーを除去又は低減するための対策を実施しなくてはならない。
【０００６】
レジスタエラーによる上記の目障りな効果の除去乃至は低減のための方法は印刷機における刷版レジスタ乃至は紙ガイドのより正確な閉ループ制御である。しかし、これは面倒で高価であり、改善された閉ループ制御は比較的古い印刷機には増備できない。
【０００７】
第２の方法は再現技術における色分解データの準備の際のいわゆる過充填（Ueberfuellen)（英語ではトラッピング(trapping)）である。この場合、いくつかの色分解における所定の色境界においてトラッピングフレーム（Ueberfuellrahmen）が発生され、他の色分解においてはトラッピングフレームは発生されない。トラッピングによって、印刷機におけるレジスタエラーの際でも色分解におけるグラフィックオブジェクトの十分に大きなオーバーラップが存在することが保証される。この結果、目障りな印刷されていないストリップは生じ得ない。どの色分解に対して及びどの色境界に対してトラッピングフレームを発生させなければならないか及びどの色分解に対して及びどの色境界に対してトラッピングフレームを発生させてはならないかは、グラフィックオブジェクトのすぐ周囲の色に対するこのグラフィックオブジェクト内部の色に依存する。この場合、一般的なルールは、比較的明るい色は比較的暗い色に対してトラッピングされるということである。これによって輪郭の決まった比較的暗い色の輪郭は変化されず、グラフィックオブジェクトの形は色分解のオーバーラップにもかかわらず重ね印刷において主観的には保持されたままである。
【０００８】
図４は図１の例の色分解Ｙに対するトラッピングフレーム３を示し、このトラッピングフレームはトラッピング幅ｗの円形リングである。色分解Ｙ及びＭの円がトラッピングフレーム３によって拡大されても、色分解Ｋの円面の空白部分が拡大されない場合には、色分解のずれがあっても目障りなストリップは生じ得ない。トラッピングフレーム３のトラッピング幅ｗは、予期すべき最大のずれが被覆されるような、すなわち、予期すべき最大のずれが使用される印刷機の品質及び使用期間に依存するような大きさに選択される。
【０００９】
従来技術によれば、印刷頁においてまず最初にどのようなグラフィックオブジェクトがそこに含まれているか及びこれらのグラフィックオブジェクトがどこで互いに隣接しているかを分析することによってトラッピングフレームが発生される。オブジェクトのタイプ及び色境界の両側の色に依存して、オブジェクトのうちのどれがその輪郭のどの部分においてトラッピングフレームを持つのか及びどのような色をトラッピングフレームが得るのかが決定される。グラフィックオブジェクトとはこの場合任意のやり方で色値によって充填されている任意の形の面であると解釈する。最も簡単なケースでは面は均等に一定の色で充填されている。しかし、この面は色変化を含み得る、すなわち所定の色領域における色の連続的な変化を含み得る。グラフィックオブジェクトは走査された画像データ又は様々な色値のパターンをも含み得る。色充填の種類はグラフィックオブジェクトのタイプ、例えば「均一な色の面」（例えばグラフィック、テキスト）、「色変化」又は「画像」を決定する。
【００１０】
特許文献ＵＳ５１１３２４９には従来技術によりトラッピングフレームを発生するためのこのような方法が記述されている。そこではグラフィックオブジェクトのタイプは「エリアタイプ」と呼ばれ、色境界の両側に存在する「エリアタイプ」に依存してトラッピングフレームが発生されなければならないかどうか、両方の「エリアタイプ」のうちのどちらがこれによって拡張されるべきか、トラッピングフレームはどんな色を保持するべきかが決定される。
【００１１】
従来技術による方法では印刷頁におけるグラフィックオブジェクトのタイプ及びその境界がもとめられなければならない。印刷頁がオブジェクト志向の頁記述言語、例えばポストスクリプトで定義されている場合、これは頁記述の分析によって行われる。このような方法は特許文献ＵＳ５２９５２３６に記述されている。印刷頁がオブジェクト志向の頁記述ではなく、画素のマトリクスとして存在している場合、グラフィックオブジェクト及びその境界はパターン識別の方法によってもとめられなければならない。このような方法は非常に計算コストがかかる。
【００１２】
トラッピングフレーム自体の計算によって従来技術の方法では更なる計算コストが生じる。どのオブジェクトをトラッピングすべきかを決定した後で、所定のトラッピング幅を有するフレームをオブジェクトの輪郭に対して計算しなくてはならない。この場合、グラフィックオブジェクトの輪郭は一般に一連のベクトルとして表される。グラフィックオブジェクトがその境界の一部分において１つの色に囲まれ、その境界の他の部分において他の色によって囲まれている場合、一般には境界のこれらの部分に対してだけトラッピングフレームが計算される。これらの部分に対しては互いに隣接する色のためにトラッピングフレームが必要である。印刷頁データがベクトルによる記述で表されておらず、画素のマトリクスとして表されている場合、まず最初に色境界にある輪郭画素がもとめられなければならない。次いで、これらの輪郭画素を結ぶベクトルに基づいてトラッピングフレームが計算される。
【００１３】
特許文献ＤＥ１９７３５３８０には距離マッピングに基づくトラッピングフレームの計算のための方法が記述されている。この方法は、印刷頁データが画素マトリクスとして表されていることを前提とする。距離マッピングによって例えばオブジェクトの外側の各画素に対して間隔ベクトルが決定され、この間隔ベクトルはオブジェクトの縁部の最も近くにある画素までの間隔を示す。このオブジェクトに対するトラッピングフレームを、その間隔ベクトルが絶対値においてトラッピング幅ｗよりも小さいか又は等しい全ての画素が形成する。距離マッピングを計算するための方法は、例えば専門文献 P.-E. Danielsson :“Euclidian Distance Mapping”, Computer Graphics and Image Processing Vol.14, p.227-248 (1980) に記述されている。
【００１４】
距離マッピングの方法を次に簡単な例で説明する。図５ａは背景面５にオブジェクト４を有する画素マトリクスを示す。オブジェクト４及び背景面５は異なる色を有し、適用すべきトラッピングルールに従ってオブジェクト４の周りにトラッピングフレームが発生される。図５ｂは間隔ベクトルＤ（ｘ,ｙ）の所属の距離マトリクスを示し、距離マッピングの開始時にオブジェクト４内部の画素には間隔ベクトルＤ（０,０）が割り当てられており、背景面５の画素には最大間隔ベクトルが、この例ではＤ（ｘ,ｙ）＝（９,９）が割り当てられている。間隔ベクトルＤ（ｘ,ｙ）の第１の成分はｘ成分であり、第２の成分はｙ成分である。距離マトリクスの周囲の外側には最大間隔ベクトルＤ（ｘ,ｙ）＝（９,９）の仮の縁部が存在する。さて、最初のスキャンにおいて画素オペレータＦ１が距離マトリクスの各画素に適用され、距離マトリクスが列毎に上から下へと及び各列において画素から画素へとスキャンされる。図６ａは画素オペレータＦ１の形を示す。この画素オペレータは瞬時に計算すべき画素Ｐ及び隣接画素Ｎ１、Ｎ２、Ｎ３、Ｎ４、Ｎ５から成り、これらの隣接画素は画素Ｐの左側、右側、上側に存在する。隣接画素の間隔ベクトルＤ（Ｎ１）、Ｄ（Ｎ２）、Ｄ（Ｎ３）、Ｄ（Ｎ４）、Ｄ（Ｎ５）からｘ及びｙ成分に対する所定のインクリメントの加算によってそれぞれ現在注目する画素Ｐに対する新しい間隔ベクトルが計算される。インクリメントは現在注目する画素Ｐに対する隣接画素Ｎ１、Ｎ２、Ｎ３、Ｎ４、Ｎ５の相対的な位置から生じる。１つ又は複数のこのように計算された間隔ベクトルのｘ成分及び/又はｙ成分が現在注目する間隔ベクトルＤ（Ｐ）の相応の成分よりも小さい場合にだけ、現在注目する間隔ベクトルの成分は新たに計算された間隔ベクトルのそれぞれ最も小さい成分によって置き換えられる。
【００１５】
【数１】
0003871040.tif 000002
【００１６】
第２のスキャンでは画素オペレータＦ２が距離マトリクスの各画素に適用され、距離マトリクスが列毎に下から上へと及び各列において画素から画素へとスキャンされる。図６ｂは画素オペレータＦ２の形を示す。この画素オペレータＦ２は瞬時に計算すべき画素Ｐ及び隣接画素Ｎ４、Ｎ５、Ｎ６、Ｎ７、Ｎ８から成り、これらの隣接画素は画素Ｐの左側、右側、下側に存在する。画素オペレータＦ２の計算は式（１）と類似している。
【００１７】
【数２】
0003871040.tif 000003
【００１８】
図７ａはこれら２つの画素オペレータＦ１及びＦ２のスキャンの後の計算された距離マトリクスを示す。オブジェクト４の近傍にはｘ成分及びｙ成分の小さい値を有する間隔ベクトルが生じ、オブジェクト４から離れるに従って、これらの成分は大きくなる。間隔ベクトルのｘ及びｙ成分から間隔の絶対値｜Ｄ｜が計算される。
【００１９】
【数３】
0003871040.tif 000004
【００２０】
図７ｂは間隔の絶対値｜Ｄ｜を示す。この場合、トラッピングフレーム３は、｜Ｄ｜≦ｗを有する画素によって形成される。図７ｂでは例としてトラッピング幅ｗ＝２のトラッピングフレーム３が示されている。
【００２１】
再現技術においてトラッピングフレームは主にテキスト及び例えば図面又は色付きの面のようなグラフィック要素に対して生成される。相応の画像データは非常に高い解像度、例えば１０００画素/ｃｍ及び１０００ライン/ｃｍで与えられ、この結果、輪郭の十分に良好な縁部シャープネスを保証する。データ量を低減するために、グラフィック/テキスト画像データは通常はランレングス符号化されたデータフォーマットで格納され、この場合、列における同じ色の画素のシーケンスはランレングス符号によって記述される。ランレングス符号は例えばランレングスにおける画素の色分解値ＣＭＹＫを示す４バイト長の色指定及びランレングスにおける画素の数を示す２バイト長のランレングスから構成される。このような符号化によってグラフィック/テキスト画像データは大幅に圧縮される。達成可能な圧縮率はグラフィック/テキスト画像データにおける色変化の個数及び密度に依存するが、大抵の場合は１００〜２００のオーダである。この高いデータ圧縮の及びこれに結びついたメモリロケーションの節約及び処理時間の節約のために、グラッフィック/テキスト画像データは再現システムにおいてランレングス符号化されたデータフォーマットで格納される。
【００２２】
距離マッピングによりトラッピングフレームを決定するための上記の方法は、画素マトリクスの形式で表される画像データによってしか実施できないという欠点を有する。それゆえ、ランレングス符号化されたグラフィック/テキスト画像データはこの方法による処理の前に伸長され、画素マトリクスに変換されなければならない。ＤＩＮ  Ａ４頁及び解像度１０００画素/ｃｍにおいて、２１×２９.７×１０００×１０００＝６２３,７００,０００画素の画素マトリクスが生じる。各画素に対する４バイトの色符号化（ＣＭＹＫ）によって２,４９４,８００,０００バイトのデータ量が生じ、このデータ量は少しずつハードディスクからコンピュータの作業メモリにロードされ、この方法によって処理され、再び格納されなければならない。この場合、距離マッピングの計算のために各画素はその８個の隣接画素と比較されなければならない。すなわち、必要な比較の数は大きい画素数に相応して非常に大きい。付加的な時間が画素マトリクスへの伸長及びトラッピングフレームにより補足された画像データのランレングスフォーマットへの後続の圧縮のために使用される。明らかに、従来技術による距離マッピングの方法が効率的に使用できないほど、高い解像度のグラフィック/テキスト画像データに対する処理時間は大きい。
【００２３】
【発明が解決しようとする課題】
本発明の課題は、距離マッピングによるトラッピングフレームの発生のための公知の方法の欠点を回避し、改善された方法を提示することであり、この改善された方法によって、ランレングス符号化されたグラフィック/テキスト画像データを予め伸長して画素マトリクスに変換する必要なしに、距離マッピングが直接これらのランレングス符号化されたグラフィック/テキスト画像データによって実施できるようにすることである。
【００２４】
【課題を解決するための手段】
上記課題は、ランレングスを画素のマトリクスに復号化することなしに、別の色を有する領域までのランレングスの距離が決定され、ランレングスは開始点から終了点までの画素のシーケンスを記述し、別の色を有する領域までの開始点及び終了点の間隔を表す間隔ベクトルが決定され、ランレングスの距離はこれらの間隔ベクトルに基づいて決定され、トラッピングフレームはもとめられた距離に基づいて次のように発生される、すなわち、２つの間隔ベクトルの絶対値の距離がトラッピング幅ｗより小さいか又は等しい場合には、ランレングスは発生されるトラッピングフレームに所属し、又は、２つの間隔ベクトルのうちの一方だけの絶対値の距離がトラッピング幅ｗより小さいか又は等しい場合には、発生されるトラッピングフレームに所属する部分区間がランレングスから分割され、又は、２つの間隔ベクトルの絶対値の距離がトラッピング幅ｗより大きい場合には、ランレングスは発生されるトラッピングフレームに所属しないことによって解決される。
【００２５】
【発明の実施の形態】
この改善された方法は相当少ないメモリロケーションしか必要とせず、処理時間の明らかな低減を可能にする。こうして計算された距離マッピングに基づいてトラッピングフレームが決定される。
【００２６】
本発明の方法によって間隔ベクトルはそれぞれランレングスの開始点及び終了点に対して決定され、隣接するランレングスの間隔ベクトルに依存して更新される。図８は色１の領域にあるランレングス６を示す。ランレングス６は開始点Ａから終了点Ｅまでの同じ色の画素のシーケンスを記述する。間隔ベクトルＤＡは他の色２の最も近くにある領域までのこの開始点Ａの最短の間隔を記述する。同様に、間隔ベクトルＤＥは他の色２の最も近くにある領域までのこの終了点Ｅの最短の間隔を記述する。これらの間隔ベクトルはそれぞれｘ成分とｙ成分とを有する。これらの成分はここでは間隔ベクトルＤＡに対しては（ＤＡｘ,ＤＡｙ）、間隔ベクトルＤＥに対しては（ＤＥｘ,ＤＥｙ）によって示される。絶対値の距離は例えばこれらの成分からユークリッド距離として計算される。
【００２７】
【数４】
0003871040.tif 000005
【００２８】
しかし、より簡単な距離尺度を選択することもできる。例えば、
｜ＤＡ｜＝ＤＡｘ＋ＤＡｙ
｜ＤＥ｜＝ＤＥｘ＋ＤＥｙ                                （５）
本発明の有利な実施形態によれば、各間隔ベクトル毎にｘ及びｙの成分のほかに所属のランレングスの色及び間隔ベクトルがそこまでの間隔を示すところの隣接色が格納される。これらの色は色分解値の指定によって、例えばＣＭＹＫ及び場合によっては第５の及び更に別の色分解に対する付加的な色分解値によって格納される。４個より多くの色分解によって印刷される場合には、有利には色を色テーブルに示されるインデックス値として格納する。色テーブルには相応のインデックスの下に全ての所属の色分解値が格納されている。
【００２９】
列毎に上から下への及び各列において左から右へのランレングスにより記述された画像データの最初のスキャンにおいて、各ランレングスは５個の隣接するランレングスと比較される。図９ａは瞬時に処理されるランレングスＬ０及び隣接するランレングスＬ１、Ｌ２、Ｌ３、Ｌ４、Ｌ５の相対的な位置を示す。ランレングスＬ１は列において現在注目するランレングスＬ０の直ぐ前にあるランレングスである。ランレングスＬ２は前の列において現在注目するランレングスＬ０の左側から始まっているランレングスである。ランレングスＬ３は前の列において現在注目するランレングスＬ０の上にあるランレングスである。ランレングスＬ４は前の列において現在注目するランレングスＬ０の右側で終わっているランレングスである。ランレングスＬ５は同じ列において現在注目するランレングスＬ０に続いているランレングスである。列毎に下から上への及び各列において右から左へのランレングスにより記述された画像データの第２のスキャンにおいて、現在注目するランレングスＬ０は５個の隣接するランレングスＬ１、Ｌ５、Ｌ６、Ｌ７、Ｌ８と比較される。図９ｂは第２のスキャンにおいて瞬時に処理されるランレングスＬ０及び隣接するランレングスＬ１、Ｌ５、Ｌ６、Ｌ７、Ｌ８の相対的な位置を示す。以下においては最初のスキャンだけを詳しく記述する。第２のスキャンは同じやり方でこれに対して鏡像対称的に行われる。
【００３０】
ランレングスの配置において現在注目するランレングスＬ０が５個よりも少ない隣接するランレングスを有する場合がある。図１０ａは４個の隣接するランレングスを有する配置を示し、この配置においてはランレングスＬ２とＬ３が一致している。図１０ｂはたった３個の隣接するランレングスを有する配置を示し、この配置においてはランレングスＬ２、Ｌ３及びＬ４が一致している。これらの場合、現在注目するランレングスＬ０は低減された個数の隣接するランレングスと比較される。
【００３１】
最初のスキャンの開始時に、全ての間隔ベクトルの成分は最大値にセットされる。２つの隣接するランレングスの２つの間隔ベクトルの比較の際に、まず最初に、これら２つのランレングスが同じ色を有するか又は異なる色を有するかが検査される。これら２つのランレングスが異なる色を有する場合、ランレングスＬ０の処理される間隔ベクトルは隣接するランレングスの比較される開始点乃至は終了点までの実際の間隔に相応して新たにセットされ、相応の隣接色が間隔ベクトルにおいて格納される。図１１はこれを例において表している。隣接するランレングスＬ０及びＬ１は異なる色を有し、これは図１１において異なるハッチングによって示されている。ランレングスＬ０の開始点Ａ（Ｌ０）とランレングスＬ１の終了点Ｅ（Ｌ１）が互いに比較される。終了点Ｅ（Ｌ１）から見れば開始点Ａ（Ｌ０）は同一の列においてＥ（Ｌ１）の右側の画素である。間隔ベクトルＤＡ（Ｌ０）の成分はそれゆえこの例ではＤＡｘ（Ｌ０）＝１、ＤＡｙ（Ｌ０）＝０にセットされる。
【００３２】
隣接するランレングスが同じ色を有する場合、ランレングスＬ０の処理される間隔ベクトルに対して、隣接するランレングスの比較される開始点乃至は終了点の間隔ベクトル及びこれら２つの点の実際の間隔から新しい間隔ベクトルが計算される。図１２はこれを例において表している。現在注目するランレングスＬ０及び隣接するランレングスＬ２ならびに隣接色の領域７が示されている。ランレングスＬ０の開始点Ａ（Ｌ０）とランレングスＬ２の開始点Ａ（Ｌ２）とが互いに比較される。間隔ベクトルＤＡ（Ｌ０）は成分ＤＡｘ＿ａｌｔ（Ｌ０）及びＤＡｙ＿ａｌｔ（Ｌ０）を有し（図１２には図示されていない）、間隔ベクトルＤＡ（Ｌ２）は成分ＤＡｘ（Ｌ２）及びＤＡｙ（Ｌ２）を有する。開始点Ａ（Ｌ２）から見れば開始点Ａ（Ｌ０）は次の列においてＡ（Ｌ２）からｋ画素だけ右側にある。ここから次のような成分を有する新しい間隔ベクトルＤＡ＿ｎｅｕ（Ｌ０）が計算される。
【００３３】
ＤＡｘ＿ｎｅｕ（Ｌ０）＝ＤＡｘ（Ｌ２）＋ｋ
ＤＡｙ＿ｎｅｕ（Ｌ０）＝ＤＡｙ（Ｌ２）＋１                （６）
新しい間隔ベクトルの絶対値の距離｜ＤＡ＿ｎｅｕ（Ｌ０）｜が古い間隔ベクトルの絶対値の距離｜ＤＡ＿ａｌｔ（Ｌ０）｜より小さい場合、古い成分は新しく計算された成分によって置き換えられる。
【００３４】
現在注目するランレングスＬ０を隣接するランレングスＬ１、Ｌ２、Ｌ３、Ｌ４、Ｌ５と比較する際に、開始点Ａ（Ｌ０）及び終了点Ｅ（Ｌ０）が隣接するランレングスの全ての開始点及び終了点と比較される。すなわち、次のように比較される。
【００３５】
【数５】
0003871040.tif 000006
【００３６】
毎回、新たに計算された間隔ベクトルの絶対値の距離が古い間隔ベクトルの絶対値の距離より小さいかどうかが検査され、イエスの場合には、新たに計算されたｘ及びｙ成分が使用される。さらに隣接色として最短距離にある色がエントリされる。その後、現在注目するランレングスＬ０の次のランレングスが次の現在注目するランレングスとされ、この過程が繰り返される。
【００３７】
現在注目するランレングスＬ０の間隔ベクトルＤＡ（Ｌ０）及びＤＥ（Ｌ０）が隣接するランレングスＬ１、Ｌ２、Ｌ３、Ｌ４、Ｌ５の間隔ベクトルに基づいて新たに決定される前に、場合によっては現在注目するランレングスＬ０が部分区間に分解されなければならない。図１３ａは例においてなぜこれが必要なのかを表している。現在注目するランレングスＬ０は列ｉに図示され、隣接するランレングスＬ１、Ｌ２、Ｌ３、Ｌ４、Ｌ５は列ｉ−１及びｉにあり、ならびに、その下にある２つのさらに別のランレングスＬｒ及びＬｓは列ｉ＋１にある。さらに隣接色の領域７が図示され、この隣接色までの隣接するランレングスのいくつかの間隔ベクトルが図示されている。この例では、間隔ベクトルＤＥ（Ｌ２）及びＤＡ（Ｌ３）は間隔ベクトルＤＡ（Ｌ２）、ＤＥ（Ｌ１）、ＤＥ（Ｌ３）、ＤＡ（Ｌ４）、ＤＥ（Ｌ４）よりもこの隣接色まで近い距離を有する。この状況では図１２に基づいて説明された計算規則に従って新しい最短間隔ベクトルＤＡ＿ｎｅｕ（Ｌ０）が間隔ベクトルＤＥ（Ｌ１）に基づいて新たに計算され、新しい最短間隔ベクトルＤＥ＿ｎｅｕ（Ｌ０）が間隔ベクトルＤＡ（Ｌ４）に基づいて新たに計算される。これらの他の所与の間隔ベクトルに基づいて新たに計算された間隔ベクトルは長くなってしまい、それゆえ棄却されてしまう。この結果として間隔ベクトルＤＥ（Ｌ２）及びＤＡ（Ｌ３）のより短い距離に関する情報は失われてしまい、次の列ｉ＋１のランレングスＬｒ及びＬｓの処理の際にもはや考慮されなくなってしまう。図１３ａの例が示しているように、間隔ベクトルＤＥ（Ｌ２）及びＤＡ（Ｌ３）に基づいて計算されれば、ランレングスＬｒ及びＬｓの新たに計算された間隔ベクトルに対してより短い距離が得られるだろう。これらの間隔ベクトルはＬｒ及びＬｓの隣接するランレングスには所属しないので、ここに説明された方法によってはこれは不可能である。
【００３８】
それゆえ、本発明の方法では間隔ベクトルの新たな計算の前に現在注目するランレングスＬ０をこの現在注目するランレングスＬ０の上にある列の隣接するランレングスＬ２とＬ３との間の接合部が存在するｘ座標において分割する。図１３ｂはこの分割を示している。本来のランレングスＬ０の左側で分割された部分区間は新しい現在注目するランレングスＬ０となる。残りの部分区間はＬ０に続く新たなランレングスＬ５として処理される。この分割の後で新しいランレングスＬ０に対して隣接するランレングスＬ２とＬ３とがまとめられ、本来のランレングスＬ３は新しいランレングスＬ４になる。この分割によって次のことが保証される。すなわち、隣接色に対して最短距離を有する列ｉ−１の間隔ベクトルが現在注目するランレングスに対する間隔ベクトルの計算の際に考慮され、次の列ｉ＋１においても更新される。有利には、ランレングスＬ０の分割は、ランレングスＬ２及びＬ３の関連する間隔ベクトルのうちの少なくとも１つがトラッピング幅ｗより小さいか又は等しい隣接色までの距離を有する場合にのみ行われる。この場合にだけこれらの間隔ベクトルはトラッピングフレームの後ほどの決定に寄与する。ランレングスＬ０の分割に対するこのような規準によってランレングスの度が過ぎる不必要な細かい分割が回避される。さらに処理時間は節約される。ランレングスＬ０の分割は、列ｉ−１においてランレングスＬ２とＬ３とが境を接するｘ座標において正確に行われる必要はない。Ｌ０の分割がＬ２とＬ３との境界の近傍で行われるならば、後ほど決定すべきトラッピングフレームのための十分な距離マッピングも得られる。
【００３９】
ランレングス符号化された画像データの上から下への最初のスキャン及び次いで下から上への第２のスキャンにおいて本来のランレングス及び分割により新たに生じたランレングスの間隔ベクトルが上記のやり方で新たに計算された後で、距離マッピングは完了され、これらの間隔ベクトルはそれぞれ最も近くにある隣接色までの最短距離を有する。次いで、この距離マッピングに基づいて、トラッピングフレームが決定される。このために、どの色がどの他の色に対してトラッピングされるべきかを示す格納されたトラッピングルールに基づいて、各ランレングス毎に、ランレングスがこのランレングスにおいてエントリされた隣接色に対してトラッピングされるべきかどうかが検査される。イエスの場合、間隔ベクトルＤＡ（Ｌ０）及びＤＥ（Ｌ０）に基づいて、ランレングス全体がトラッピングフレームに所属するのか、又は、このランレングスの一部分がトラッピングフレームに所属するのか、又は、このランレングスはそもそもトラッピングフレームに寄与しないのかが判定される。このために次のようなケース区別が行われる：
（ａ）｜ＤＡ（Ｌ０）｜≦ｗ かつ ｜ＤＥ（Ｌ０）｜≦ｗ ⇒ ランレングス全体がトラッピングフレームに所属する
（ｂ）｜ＤＡ（Ｌ０）｜≦ｗ かつ ｜ＤＥ（Ｌ０）｜＞ｗ ⇒ ランレングスの左側の部分がトラッピングフレームに所属する
（ｃ）｜ＤＡ（Ｌ０）｜＞ｗ かつ ｜ＤＥ（Ｌ０）｜≦ｗ ⇒ ランレングスの右側の部分がトラッピングフレームに所属する
（ｄ）｜ＤＡ（Ｌ０）｜＞ｗ かつ ｜ＤＥ（Ｌ０）｜＞ｗ ⇒ ランレングスはトラッピングフレームに所属しない
ケース（ａ）では、ランレングスの色はトラッピングルールに従って生じるトラッピング色によって置き換えられる。ケース（ｂ）及び（ｃ）では、ランレングスの左側の部分乃至は右側の部分がトラッピングフレームに所属する。トラッピングフレームを決定するためにこの場合ランレングスはトラッピングフレームに所属する部分区間Ｌｕとトラッピングフレームに所属しない部分区間とに分割される。図１４はケース（ｃ）のこれを例で示している。ランレングスＬ０が示されており、このランレングスＬ０の間隔ベクトルＤＡ（Ｌ０）は隣接色の領域７に対して距離｜ＤＡ（Ｌ０）｜＞ｗを有し、さらにこのランレングスＬ０の間隔ベクトルＤＥ（Ｌ０）はこの隣接色に対して距離｜ＤＥ（Ｌ０）｜≦ｗを有する。このランレングスＬ０の右側端部において部分区間Ｌｕが分割される。この部分区間Ｌｕはトラッピングフレームの部分となり、トラッピング色を得る。分割位置は、この場合、間隔ベクトルＤＥ（Ｌ０）の終了点から部分区間Ｌｕの開始点までの新しい間隔ベクトルＤＡｕ（Ｌｕ）が距離｜ＤＡｕ（Ｌｕ）｜＝ｗを有するように決定される。ランレングスＬ０の残りの部分区間はトラッピングフレームに所属せず、その本来の色を保持する。
【００４０】
本発明の方法の更に別の実施形態では、距離マッピングの間にすでにトラッピングルールに従って現在注目するランレングスＬ０の色が別の色の隣接するランレングスに対してトラッピングされるべきかどうかが検査されることによって、処理が加速される。この色の組み合わせに対してトラッピングが発生されるべきではない場合には、現在注目するランレングスＬ０は、あたかも全ての隣接するランレングスがこの現在注目するランレングスと同じ色を有するかのように処理される。こうして、距離≦ｗを有する比較的少ない間隔ベクトルが生じる。すなわち現在注目するランレングスＬ０を図１３ｂ又は図１４に従って部分区間に分解する必要性はより少なくなる。
【図面の簡単な説明】
【図１】  印刷例における色分解Ｙ、Ｍ及びＫの概略図を示す。
【図２】  印刷機におけるレジスタエラーなしの色分解Ｙ、Ｍ、Ｋの重ね印刷の概略図を示す。
【図３】  印刷機におけるレジスタエラーを有する色分解Ｙ、Ｍ、Ｋの重ね印刷の概略図を示す。
【図４】  色分解Ｙに対するトラッピングフレームの概略図を示す。
【図５】  ａは背景面におけるオブジェクトを有する画素マトリクスの概略図を示す。ｂは距離マッピングの開始時の間隔ベクトルのマトリクスの概略図を示す。
【図６】  ａは画素オペレータＦ１を示す。ｂは画素オペレータＦ２を示す。
【図７】  ａは距離マッピング終了後の間隔ベクトルのマトリクスの概略図を示す。ｂは距離マッピング終了後の間隔絶対値のマトリクスの概略図を示す。
【図８】  間隔ベクトルＤＡ及びＤＥを有するランレングスの概略図を示す。
【図９】  ａは最初のスキャンに対する現在注目するランレングスＬ０及び隣接するランレングスＬ１、Ｌ２、Ｌ３、Ｌ４、Ｌ５の概略図を示す。ｂは第２のスキャンに対する現在注目するランレングスＬ０及び隣接するランレングスＬ１、Ｌ５、Ｌ６、Ｌ７、Ｌ８の概略図を示す。
【図１０】  ａは現在注目するランレングスＬ０及び３つの隣接するランレングスを有する配置を示す。ｂは現在注目するランレングスＬ０及び２つの隣接するランレングスを有する配置を示す。
【図１１】  隣接するランレングスの間の色の変わり目における間隔ベクトルＤＡ（Ｌ０）の決定のための例を示す。
【図１２】  隣接するランレングスの間の色の変わり目がない場合の間隔ベクトルＤＡ（Ｌ０）の決定のための例を示す。
【図１３】  ａは現在注目するランレングスＬ０の分割を説明するための例を示す。ｂは現在注目するランレングスＬ０の分割の後のランレングスの配置を示す。
【図１４】  現在注目するランレングスＬ０のトラッピングフレームに所属する部分区間Ｌｕの分割を示す。
【符号の説明】
１  印刷されていないストリップ
２  ストリップ
３  トラッピングフレーム
４  オブジェクト
５  背景面
６  ランレングス
Ｌ０  現在注目するランレングス
Ｌ１〜Ｌ８、Ｌｒ、Ｌｓ  隣接するランレングス
ＤＡ（Ｌ０）等々  間隔ベクトル
ｗ  トラッピング幅
Ｆ１  画素オペレータ
Ｆ２  画素オペレータ
【図１】
0003871040.tif 000007
【図２】
0003871040.tif 000008
【図３】
0003871040.tif 000009
【図４】
0003871040.tif 000010
【図５】
0003871040.tif 000011
【図６】
0003871040.tif 000012
【図７】
0003871040.tif 000013
【図８】
0003871040.tif 000014
【図９】
0003871040.tif 000015
【図１０】
0003871040.tif 000016
【図１１】
0003871040.tif 000017
【図１２】
0003871040.tif 000018
【図１３】
0003871040.tif 000019
【図１４】
0003871040.tif 000020