(57)【特許請求の範囲】
【請求項１】
ビットマップ画像からエッジ座標情報をライン順に抽出するエッジ座標抽出回路と、
コンピュータプログラムを実行することにより、前記エッジ座標抽出回路で抽出されたエッジ座標情報に基づき、前記ビットマップ画像をベクタデータに変換する変換手段と、
を含み、
前記変換手段による前記ベクタデータへの変換はソフトウェア処理であり、前記エッジ座標抽出回路による前記エッジ座標情報の抽出はハードウェア処理であり、
前記エッジ座標抽出回路による前記エッジ座標情報の抽出処理が前記ビットマップ画像の２ライン分終了した時点から、前記変換手段による前記ベクタデータへの変換処理を開始し、その後、前記抽出処理と前記変換処理とを並列に実行することを特徴とする画像処理装置。
【請求項２】
前記エッジ座標情報は、ライン毎のエッジ位置情報及びエッジ数情報であることを特徴とする請求項１記載の画像処理装置。
【請求項３】
前記ビットマップ画像は二値ビットマップ画像であり、
前記エッジ座標抽出回路は、前記二値ビットマップ画像のエッジ座標情報を抽出し、
前記変換手段は、前記コンピュータプログラムを実行することにより、前記エッジ座標抽出回路で抽出されたエッジ座標情報に基づき、前記二値ビットマップ画像をベクタデータに変換することを特徴とする請求項１記載の画像処理装置。
【請求項４】
前記変換手段により変換されたベクタデータに基づき、ＯＣＲ処理を行うＯＣＲ手段を更に有することを特徴とする請求項１記載の画像処理装置。
【請求項５】
前記エッジ座標情報とは、画素間の濃度変化点の座標に関する情報であることを特徴とする請求項１記載の画像処理装置。
【請求項６】
前記ベクタデータは、前記ビットマップ画像内の画像オブジェクトの輪郭を示すデータであることを特徴とする請求項１記載の画像処理装置。
【請求項７】
前記エッジ座標抽出回路は、
前記ビットマップ画像から、連続するｎビットのデータを抽出する抽出手段と、
前記抽出手段により抽出されたｎビットデータから、エッジ位置情報及びエッジ数情報を同時にデコードするデコード手段と、
前記デコード手段によって導き出した、前記ｎビットデータ毎のエッジ位置情報及びエッジ数情報を結合して、１ライン毎のエッジ位置情報及びエッジ数情報を導き出すデータ結合手段と、
を有することを特徴とする請求項１に記載の画像処理装置。
【請求項８】
ビットマップ画像を処理する画像処理方法であって、
エッジ座標抽出回路が、前記ビットマップ画像からエッジ座標情報をライン順に抽出するエッジ座標抽出工程と、
ＣＰＵにコンピュータプログラムを実行させることにより、ＣＰＵが、前記エッジ座標抽出工程で抽出されたエッジ座標情報に基づき、前記ビットマップ画像をベクタデータに変換する変換工程と、
を含み、
前記エッジ座標抽出回路による前記エッジ座標情報の抽出処理が前記ビットマップ画像の２ライン分終了した時点から、前記ＣＰＵによる前記ベクタデータへの変換処理を開始し、その後、前記抽出処理と前記変換処理とを並列に実行することを特徴とする画像処理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、入力したビットマップ画像を処理する画像処理装置及び画像処理方法に関する。
【０００２】
【従来の技術】
従来、ＰｏｓｔＳｃｒｉｐｔやＬＩＰＳ,ＰＣＬ等のページ記述言語(ＰＤＬ)を処理するプリンタや複合機システムは、バンドバッファもしくはページバッファ等のフレームバッファを持ち、フレームバッファに描画オブジェクトをレンダリングする処理が行われていた。この場合、フレームバッファからその描画オブジェクトの周辺の画像を読み出し、描画オブジェクトと合成した上でフレームバッファに書き戻す作業を、描画オブジェクトすべてについて行っていた。このため、フレームバッファであるメモリに対して、多量のリード・モディファイ・ライトの処理を行う必要があった。従って、プリンタの解像度が高い場合や、カラープリンタにおいて高い階調で出力する場合、レンダリングの時間が非常に長くなるという問題が生じていた。これを解決するために、描画オブジェクトの輪郭情報と、描画オブジェクトの上下関係をあらわすレイヤー情報から、直接最終ピクセルを生成する、レンダリングの方法が、特開2000-137825号公報において提案されている。この方法は、オブジェクトの輪郭情報から、あるピクセル位置に存在するオブジェクトを認識し、つづいてそれらのオブジェクトの上下関係からどのオブジェクトが最上層に存在するかを判断し、最後に最上層に存在するオブジェクトの色情報から、現在注目しているピクセルがどの色かを判断することで、１ピクセル毎にピクセルデータを生成する。そのため、レンダリング時にメモリへのリード・モディファイ・ライトを多量に行う必要がなく、解像度や諧調が増えても、レンダリング時間があまり長くならない。
【０００３】
【発明が解決しようとする課題】
しかしながら、上記従来技術では、あるページをレンダリングする前に、あらかじめそのページに存在するオブジェクトの輪郭情報を得ておく必要がある。そのページに文字が多く含まれる場合には、文字のフォントオブジェクトに関する輪郭情報を得ておく必要がある。ところが、文字は種類が多く、また輪郭も複雑なため、輪郭抽出処理に時間がかかるという問題が生じる。
【０００４】
また、通常のビットマップフォントは２値ビットマップ画像であり、２値ビットマップ画像から輪郭を抽出する処理は、ビット操作となるため、通常のＣＰＵで処理するには多くのサイクル数を要する処理となり、高速に処理することが困難であるという問題が生じる。
【０００５】
また、この輪郭抽出処理に関する問題は、上記レンダリング処理に限らず、ＯＣＲ処理におけるラスタ−ベクタ処理を実行する際にも生じるものである。
【０００６】
すなわち、スキャナからスキャンした画像にＯＣＲをかける場合、ラスタ−ベクタ処理を行っている。ラスタ−ベクタ処理の前半では、ラスタ画像の各画素を検索し、濃度の変化点（エッジ）の座標を求める処理を行い、処理の後半ではエッジの座標から複数エッジ間の関係を推論する事によってベクタを生成する。従来、この座標を求める処理を含め、ラスタ−ベクタ処理のすべての処理をＣＰＵによるソフトウェア処理で行っていた。
【０００７】
ＯＣＲでは、処理すべきラスタ画像は２値ビットマップ画像である場合が多い。２値ビットマップ画像の各画素を検索する処理では、ビット操作を多量に行う必要があり、通常のＣＰＵではビット操作のために多くのサイクルを消費する。これにより、ソフトウェア処理ではラスタ−ベクタ処理に長い時間を要するという問題が生じる。
【０００８】
本発明は、上述した問題点を解決するためのものであり、ラスタ−ベクタ処理を高速に行うことのできる画像処理装置及び画像処理方法を提供することを目的とする。
【０００９】
上記目的を達成するため、本発明に係る装置にあっては、ビットマップ画像からエッジ座標情報をライン順に抽出するエッジ座標抽出回路と、コンピュータプログラムを実行することにより、前記エッジ座標抽出回路で抽出されたエッジ座標情報に基づき、前記ビットマップ画像をベクタデータに変換する変換手段と、を含み、前記変換手段による前記ベクタデータへの変換はソフトウェア処理であり、前記エッジ座標抽出回路による前記エッジ座標情報の抽出はハードウェア処理であり、前記エッジ座標抽出回路による前記エッジ座標情報の抽出処理が前記ビットマップ画像の２ライン分終了した時点から、前記変換手段による前記ベクタデータへの変換処理を開始し、その後、前記抽出処理と前記変換処理を並列に実行することを特徴とする。
【００１０】
上記目的を達成するため、本発明に係る方法にあっては、ビットマップ画像を処理する画像処理方法であって、エッジ座標抽出回路が、前記ビットマップ画像からエッジ座標情報をライン順に抽出するエッジ座標抽出工程と、ＣＰＵにコンピュータプログラムを実行させることにより、ＣＰＵが、前記エッジ座標抽出工程で抽出されたエッジ座標情報に基づき、前記ビットマップ画像をベクタデータに変換する変換工程と、を含み、前記エッジ座標抽出回路による前記エッジ座標情報の抽出処理が前記ビットマップ画像の２ライン分終了した時点から、前記ＣＰＵによる前記ベクタデータへの変換処理を開始し、その後、前記抽出処理と前記変換処理とを並列に実行することを特徴とする。
【００２１】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を説明する。
【００２２】
（第１の実施形態）
本実施の形態では、ビットマップ−エッジ座標変換を行うデコーダを用いたエッジ座標抽出回路を構成し、ラスタ−ベクタ処理の前半を高速化する。更に、処理の後半をＣＰＵ上のソフトウェアで実行する際に、処理の前半とオーバラップさせて並列処理を行う事により、ラスタ−ベクタ処理を短時間に行う。
【００２３】
＜構成＞
図１は第１の実施形態の構成を示したブロック図である。スキャナ１０６においてスキャンされた画像は、スキャナインタフェース１０７を介してマルチファンクションコントローラ１１１の内部に取り込まれる。取り込まれた画像が多値画像であればイメージプロセッサ１１０にて二値化し、二値画像であればそのままクロスバースイッチ１０４を介して、メインメモリ１０３に格納される。二値化された画像にＯＣＲ処理を施すためにＣＰＵ１０２はエッジ座標抽出回路１０１を起動し、ラスタ−ベクタ変換処理を開始する。エッジ座標抽出回路１０１が起動されると、リードＤＭＡＣ１０１ａがメインメモリ１０３から二値画像を取得し、データセレクタ１０１ｂへと送る。
【００２４】
データセレクタ１０１ｂは、二値画像をバイト単位のストリームに変換してビットマップ−座標デコーダ１０１ｃへと送る。ビットマップ−座標デコーダ１０１ｃは入力された１バイトの二値画像が持つエッジ数と複数のエッジのｘ座標を並列にデコードし、その結果をデータ結合部１０１ｄ（ｘ座標データ結合回路）へ送る。データ結合部１０１ｄは、ビットマップ−座標デコーダ１０１ｃから受け取ったエッジのｘ座標をデータバッファに蓄積し、また当該ラインのエッジ数を積算する。データ結合部１０１ｄは、メモリへ転送可能な情報量だけエッジのｘ座標がデータバッファに蓄積された時点で、エッジのｘ座標のリストをｘ座標ライトＤＭＡＣ１０１ｆへ転送し、ｘ座標ライトＤＭＡＣ１０１ｆは当該データをメインメモリ１０３の所定のアドレスへ格納する。
【００２５】
ビットマップ−座標デコーダ１０１ｃはｘ方向のバイト数をカウントしており、ラインの終端まで到達した時点でラインの終了をデータ結合部１０１ｄへと報せる。ライン終了情報を受け取ったデータ結合部１０１ｄは、積算した当該ラインのエッジ数と、当該ラインの先頭のエッジ座標データを格納したアドレスの情報をデータ結合部１０１ｅ（ｙ座標データ結合回路）へと転送する。データ結合部１０１ｅはデータバッファにライン毎のエッジ数と格納アドレスを蓄積し、メモリ転送が可能となった時点でライン毎のエッジ数と格納アドレスをｙ座標ライトＤＭＡＣ１０１ｇへ転送する。ｙ座標ライトＤＭＡＣ１０１ｇは更に当該データをメインメモリ１０３の所定のアドレスへ格納する。
【００２６】
ビットマップ−座標デコーダ１０１ｃはｙ方向のライン数をカウントしており、二値画像の最終ラインの最終バイトまで到達した時点で、ラインの終了と共に処理の終了をデータ結合部１０１ｄへと報せる。処理終了情報を受け取ったデータ結合部１０１ｄは、データバッファに蓄積したｘ座標データをすべてｘ座標ライトＤＭＡＣ１０１ｆに送ると共に、積算した当該ラインのエッジ数と、当該ラインの先頭のエッジ座標データを格納したアドレスの情報をデータ結合部１０１ｅへと、処理終了情報と共に転送する。終了情報を受け取ったデータ結合部１０１ｅは、データバッファに格納されたライン毎のエッジ数と格納アドレスを、ｙ座標ライトＤＭＡＣ１０１ｇへ転送し、ｙ座標ライトＤＭＡＣ１０１ｇは当該データをメインメモリ１０３の所定のアドレスへ格納し処理を終了する。
【００２７】
エッジ座標抽出回路１０１が処理を開始し、２ライン分の処理が終了した時点から、ＣＰＵ１０２はラスタ−ベクタ変換処理の後半処理をエッジ座標抽出回路１０１の処理とは並列に開始する。
【００２８】
ＣＰＵ１０２は、エッジ座標抽出回路１０１が出力したエッジ座標情報を元に、隣接したライン間の各エッジの関連性を調べ、ベクタを生成していく。エッジ座標抽出回路１０１とＣＰＵ１０２が処理を終了すると、二値画像がどのような輪郭を持った画像オブジェクトから成っているかが明らかになり、この情報を元にＯＣＲ処理を行う。ＯＣＲ処理が行われるとスキャナ１０６でスキャンした画像がどのような方向を向いた文字を持っているかが判別できるため、この情報を元としてＮ-ｕｐのページ結合の処理を行い、結合されたページ画像がプリンタインタフェース１０９を介してプリンタエンジン１０８に送られ、プリントアウトされる。
【００２９】
また、ホストコンピュータ１００からネットワークインタフェース１０５を介してマルチファンクションコントローラ１１１にダウンロードされたビットマップフォントデータは、前述のラスタ−ベクタ処理を行う事により、描画オブジェクトとしてＰＤＬ描画処理に用いられる。
【００３０】
図２は本実施の形態のエッジ座標抽出回路が生成するデータ形式を示した模式図である。元となる二値画像２０１を、エッジ座標抽出回路１０１にかけると、各ライン毎のエッジのｘ座標のリスト２０２が、ｘ座標ライトＤＭＡＣ１０１ｆによってメインメモリ１０３に書き込まれる。そして、同時に、各ライン毎のエッジ数２０３と、リスト２０２におけるライン先頭を示す行のアドレス（ポインタ）２０４とからなるリスト２０５が、ｙ座標ライトＤＭＡＣ１０１ｇによってメインメモリ１０３に書き込まれる。
【００３１】
図３は本実施の形態のエッジ座標抽出回路１０１のデータパスを示したブロック図である。
【００３２】
データリードＤＭＡＣ１０１ａがメモリから取得した二値画像データは、ビットマップレジスタ３０１に格納され、当該ビットマップデータはデータセレクタ３０２によってバイト単位に分割されてバイトレジスタ３０３に格納される。バイトレジスタ３０３に格納された８ビットのバイトデータは、インバータ３１７に送られる。インバータ３１７では、レジスタ３１６に格納された値に応じて、バイトデータを反転する。
【００３３】
レジスタ３１６には１つ前（左側）のバイトのＬＳＢが保持されている。この値が１であれば、バイトデータの右端の画素が濃度を有していることになる。従って、この場合には、トータルでのエッジ数が奇数になり、エッジでない座標がエッジと認識される可能性がある。そこで、エッジ位置及びエッジ数を調整するため、インバータ３１７において反転した上でビットマップ−座標デコーダ３０４に入力する。
【００３４】
ビットマップ−座標デコーダ３０４には、８ビットのバイトデータが示す値と、エッジ位置情報及びエッジ数情報とを対応させて格納したルックアップテーブル（図４〜図９）が用意されており、バイトデータからエッジ位置情報及びエッジ数情報とに同時にデコードする。
【００３５】
例えば、図２においては、０行目の最初のバイトデータは、１６進数で０３であり、ＬＳＢは１である。従って、レジスタ３１６は、この値１を次のバイトデータがバイトレジスタ３０３から出力されるまで保持している。続くバイトデータは、１６進数で８０であり、これがレジスタ３０３に保持されると、インバータ３１７は、レジスタ３１６が１であるから、８０を７fに変換する。これにより、エッジデコーダ３０４はエッジ数１、エッジ位置１を出力することになり、連続するバイトデータ間で適正に調整が行われる。
【００３６】
ビットマップ−座標デコーダ３０４によってデコードされた、バイトデータ内に含まれるエッジ数と全てのエッジの位置の座標情報は、エッジ数レジスタ３０６と下位エッジｘ座標レジスタ３０５に格納される。ビットマップ−座標デコーダ１０１ｃはｘ方向のバイトカウンタ３０７を持っており、これがエッジの上位ｘ座標となる。
【００３７】
下位エッジｘ座標レジスタ３０５はバレルシフタ３１１によってシフトされ上位ｘ座標カウンタ３０７の出力とビット結合されてｘ座標データ結合レジスタ３１２に格納される。
【００３８】
バイト内のエッジ数はエッジ数カウンタ３１３に入力され、ライン内のエッジ数をカウントするのに用いられる。ライン内エッジ数の下位ビットと現在バイトのエッジ数であるエッジ数レジスタ３０６の出力がデコーダ３１４に入力され、バレルシフタ３１１のシフト量と、ｘ座標データ結合レジスタ３１２のロード信号が生成される。
【００３９】
このバレルシフタ３１１の動作について、図２（ａ）の画像を例にとり説明する。０ライン目の最初のバイトは１６進数で０３である。デコーダ３０４によってエッジ位置がデコードされ、図４においてバイトデータ（byte  data）が３の行に示すように、エッジ位置情報（edge  position）として値"６,０,０,０,０,０,０,０"が下位エッジｘ座標レジスタ３０５へ格納される。最初のバイトであるため、デコーダ３１４が出力するデコード量は０であるから、最初のエッジ位置である６が、上位ｘ座標カウンタ３０７の値０と結合されて、エッジ位置が６となり、左端のレジスタ３１２に保持される。
【００４０】
０ライン目の続くバイトは８０であるが、前バイトのＬＳＢビットが１であったために、インバータ３１７によって７fに変換され、デコーダ３０４によって、値"１,０,０,０,０,０,０,０"が下位エッジｘ座標レジスタ３０５に格納される。０ライン目の積算エッジ数が最初のバイトで１になっていたため、デコーダ３１４が１セグメントのシフトをバレルシフタ３１１に指示し、左から４つの値をレジスタ３１２に出力する。つまり、値"１,０,０,０,０,０,０,０"は値"０,１,０,０"となってバレルシフタ３１１から出力される。
【００４１】
上位ｘ座標カウンタ３０７は最初のバイトの処理によって１にカウントアップされているため、バレルシフタの出力"０,１,０,０"の１と結合されて二進数１００１、十進で９の値がレジスタ３１２の左から２番目のレジスタに格納される。これにより図２の２０４の最初の行に相当する"６,９"の値が生成される。
【００４２】
図２では説明を容易にするために１ライン１６画素の画像を表したが、ここで示されるエッジ座標抽出回路１０１は、より現実的に、１ラインが２32画素で構成される画像を扱うものである。従って、最終的にレジスタ３１２には、３２ビットのエッジ座標が格納される。
【００４３】
ｘ座標データ結合レジスタ３１２が満杯になると、結合された座標データはｘ座標ライトＤＭＡＣ１０１ｆに送られ、エッジ座標データ２０４としてメインメモリ１０３に格納される。エッジ座標データ２０４の格納アドレスはアドレスカウンタ３１５によってカウントされ、ラインの先頭のアドレスはデータ結合部１０１ｅに送られる。
【００４４】
また、１回の出力でバレルシフタ３１１からレジスタ３１２に出力できない場合には、満杯になったレジスタ３１２からライトＤＭＡＣ１０１ｆに座標データが送られた後に、バレルシフタ３１１に残った値を適宜シフトしてレジスタ３１２に送る。
【００４５】
ビットマップ−座標デコーダ１０１ｃは上位ｘ座標カウンタ３０７の値とラインの長さのバイト数をライン終了比較器３０８によって比較しており、上位ｘ座標カウンタ３０７の値がライン終了まで達したところでライン終了信号がライン終了レジスタ３０９に保持される。ライン終了情報が発生すると、アドレスカウンタ３１５の値とラインエッジ数カウンタ３１３の値がｙ座標データ結合回路１０１ｅへ送られる。ビットマップ−座標デコーダ１０１ｃはまたｙ方向のラインカウンタ３１０を持っており、ライン終了レジスタ３０９の情報をカウントしつつ、ビットマップ画像の総ライン数と比較している。ライン数が最終に達すると処理終了信号を発生し、ライトＤＭＡＣ１０１ｆ,１０１ｇに保持したデータ全てをメモリ１０３へ書き出すように指示し、全体の処理を終了させる。
【００４６】
図４〜図９は本実施の形態のビットマップ−座標デコーダ３０４の入出力を示した真理値表である。本実施の形態はＭＳＢ側がビットマップの左端としており、０が白、１が黒、背景が白としているため、例えばバイトレジスタ３０３の出力が０ｘ０６の場合には、エッジ数の出力が２、第１エッジの位置（下位ｘ座標）が５、第２エッジの位置（下位ｘ座標）が７をデコードし、第３エッジ以降の値に無効を示す０がデコードされ、これらのデータがエッジ数レジスタ３０６、下位ｘ座標レジスタ３１１へと格納される。
【００４７】
なお、図４〜図９で示したテーブルは、あくまで例示的なものに過ぎず、バイトデータの値とエッジ座標情報及びエッジ数情報とを対応させて格納したテーブルであれば、如何なるテーブルも本発明に適用することができる。
【００４８】
以上説明したように、本実施形態によれば、ラスタ−ベクタ処理の前半部分に当たるエッジ抽出処理を高速に行うことが可能となり、さらにエッジ同士の関連を導出してベクタ変換する処理をＣＰＵ上のソフトウェアで並列に行うことによって、ラスタ−ベクタ処理を短時間に行うことが可能となる。
【００４９】
（第２の実施形態）
既に述べたように、特開2000-137825号公報において、描画オブジェクトの輪郭情報と、描画オブジェクトの上下関係をあらわすレイヤー情報から、直接最終ピクセルを生成する、レンダリングの方法が、提案されている。
【００５０】
この方法は、オブジェクトの輪郭情報からどのオブジェクトが存在するかを判断し、つづいてオブジェクトの上下関係からどのオブジェクトが表面に存在するからを判断し、最後に表面に存在するオブジェクトの色情報から、現在注目しているピクセルがどの色かを判断することで、ピクセルを生成することを、１ピクセル毎に行う。そのため、レンダリング時にメモリへのリード・モディファイ・ライトを多量に行う必要がなく、解像度や諧調が増えても、レンダリング時間が飛躍的に長くなることはない。
【００５１】
この方法では、レンダリング処理前に、あらかじめオブジェクトの輪郭情報を得ておく必要がある。通常プリントする文章では文字が多く含まれるが、文字のフォントオブジェクトに対しても輪郭情報を得ておく必要がある。
【００５２】
本実施の形態では、ビットマップ−エッジ座標変換を行うデコーダを用いたエッジ座標抽出回路を構成し、輪郭情報の抽出処理の前半を高速化する。更に、処理の後半をＣＰＵ上のソフトウェアで実行する際に、処理の前半とオーバラップさせて並列処理を行う事により、輪郭情報の抽出処理を短期間に行う。
【００５３】
＜構成＞
図１０は第２の実施形態の構成を示したブロック図である。ホストコンピュータ１０００によって生成されたプリント情報が、ネットワークを解してマルチファンクションコントローラ１０１１へと送られる。ネットワークインターフェース１００５によって受信されたプリント情報は、クロスバースイッチ１００４を介して一度メインメモリ１００３へ格納される。続いてＣＰＵ１００２はメインメモリ１００３へ格納されたプリント情報の解析を開始し、描画オブジェクトの輪郭情報、レイヤー情報、色情報等を、ディスプレイリストとしてメインメモリ１００３の別の領域に生成していく。描画オブジェクトが文字であった場合には、フォントキャッシュを検索し、キャッシュヒットした場合にはフォントキャッシュ内に登録されている輪郭情報をディスプレイリストに追加し、キャッシュミスした場合にはビットマップフォントメインメモリ１００３の別の領域に生成し、続く輪郭情報抽出処理に移行する。
【００５４】
ビットマップフォントの輪郭情報を抽出するために、まずＣＰＵ１００２はエッジ座標抽出回路１００１にビットマップフォントが格納されたメモリアドレスを与え、これを起動する。エッジ座標抽出回路１００１が起動されると、リードＤＭＡＣ１００１ａがメインメモリ１００３より、前出のビットマップフォント画像を取得し、データセレクタ１００１ｂへと送る。
【００５５】
データセレクタ１００１ｂは、ビットマップフォント画像をバイト単位のストリームに変換してビットマップ−座標デコーダ１００１ｃへと送る。ビットマップ−座標デコーダ１００１ｃは入力された１バイトのビットマップ画像が持つエッジ数と複数のエッジのｘ座標を並列にデコードし、その結果をデータ結合部１００１ｄ（ｘ座標データ結合回路）へ送る。データ結合部１００１ｄはビットマップ−座標デコーダ１００１ｃから受け取ったエッジのｘ座標をデータバッファに蓄積し、また当該ラインのエッジ数を積算する。データ結合部１００１ｄは、メモリへ転送可能な情報量だけエッジのｘ座標がデータバッファに蓄積された時点で、エッジのｘ座標のリストをｘ座標ライトＤＭＡＣ１０１ｆへ転送し、ｘ座標ライトＤＭＡＣ１００１ｆは当該データをメインメモリ１００３の所定のアドレスへ格納する。
【００５６】
ビットマップ−座標デコーダ１００１ｃはｘ方向のバイト数をカウントしており、ラインの終端まで到達した時点でラインの終了をデータ結合部１００１ｄへと報せる。ライン終了情報を受け取ったデータ結合部１００１ｄは、積算した当該ラインのエッジ数と、当該ラインの先頭のエッジ座標データを格納したアドレスの情報をデータ結部１００１ｅ（ｙ座標データ結合回路）へと転送する。データ結合部１００１ｅはデータバッファにライン毎のエッジ数と格納アドレスを蓄積し、メモリ転送が可能となった時点でライン毎のエッジ数と格納アドレスをｙ座標ライトＤＭＡＣ１００１ｇへ転送する。ｙ座標ライトＤＭＡＣ１００１ｇは更に当該データをメインメモリ１００３の所定のアドレスへ格納する。
【００５７】
ビットマップ−座標デコーダ１００１ｃはｙ方向のライン数をカウントしており、ビットマップ画像の最終ラインの最終バイトまで到達した時点で、ラインの終了と共に処理の終了をデータ結合部１００１ｄへと報せる。処理終了情報を受け取ったデータ結合部１００１ｄは、データバッファに蓄積したｘ座標データをすべてｘ座標ライトＤＭＡＣ１００１ｆに送ると共に、積算した当該ラインのエッジ数と、当該ラインの先頭のエッジ座標データを格納したアドレスの情報をデータ結合部１００１ｅへと、処理終了情報と共に転送する。終了情報を受け取ったデータ結合部１００１ｅは、データバッファに格納されたライン毎のエッジ数と格納アドレスを、ｙ座標ライトＤＭＡＣ１００１ｇへ転送し、ｙ座標ライトＤＭＡＣ１００１ｇは当該データをメインメモリ１００３の所定のアドレスへ格納し処理を終了する。
【００５８】
エッジ座標抽出回路１００１が処理を開始し、２ライン分の処理が終了した時点から、ＣＰＵ１００２はエッジ座標から輪郭情報を抽出する処理をエッジ座標抽出回路１００１の処理とは並列に開始する。
【００５９】
ＣＰＵ１００２はエッジ座標抽出回路１００１が出力したエッジ座標情報を元に、隣接したライン間の各エッジの関連性を調べ、ベクタを生成していく。エッジ座標抽出回路１００１とＣＰＵ１００２が処理を終了すると、ビットマップフォントの輪郭情報が得られる。ＣＰＵ１００２はこの輪郭情報をフォントキャッシュに登録するとともに、ディスプレイリストへも登録する。
【００６０】
こうして１ページ分のディスプレイリストが生成されると、ＣＰＵ１００２はこのディスプレイリストを元にレンダリング処理を行い、プリントすべき画像をメインメモリ１００３へ生成する。生成された画像はクロスバースイッチ１００４、画像処理回路１０１０を介してプリンタインターフェース１００９より、プリントエンジン１００８へと送られる。プリントエンジン１００８では、受信した画像を記録媒体である紙に記録し、最終的なプリントアウトが得られる。
【００６１】
図１１は本実施の形態のエッジ座標抽出回路が生成するデータ形式を示した模式図である。元となるビットマップ画像１１０１を、エッジ座標抽出回路１００１にかけると、各ライン毎のエッジのｘ座標のリスト１１０２が、ｘ座標ライトＤＭＡＣ１００１ｆによってメインメモリ１００３に書き込まれる。そして、同時に、各ライン毎のエッジ数１１０３と、リスト１１０２におけるライン先頭を示す行のアドレス（ポインタ）１１０４とからなるリスト１１０５が、ｙ座標ライトＤＭＡＣ１００１ｇによってメインメモリ１００３に書き込まれる。
【００６２】
図１２は本実施の形態のエッジ座標抽出回路１００１のデータパスを示したブロック図である。
【００６３】
データリードＤＭＡＣ１０１ａがメモリから取得したビットマップ画像データは、ビットマップレジスタ１２０１に格納され、当該ビットマップデータはデータセレクタ１２０２によってバイト単位に分割されてバイトレジスタ１２０３に格納される。バイトレジスタ１２０３に格納されたビットマップデータは、インバータ１２１７に送られる。インバータ１２１７では、レジスタ１２１６に格納された値に応じて、バイトデータを反転する。
【００６４】
レジスタ１２１６には１つ前（左側）のバイトのＬＳＢが保持されている。この値が１であれば、バイトデータの右端の画素が濃度を有していることになる。従って、この場合には、トータルでのエッジ数が奇数になり、エッジでない座標がエッジと認識される可能性がある。そこで、エッジ位置及びエッジ数を調整するため、インバータ１２１７において反転した上でビットマップ−座標デコーダ１２０４に入力する。
【００６５】
ビットマップ−座標デコーダ１２０４には、８ビットのバイトデータが示す値と、エッジ位置情報及びエッジ数情報とを対応させて格納したルックアップテーブル（図４〜図９）が用意されており、バイトデータからエッジ位置情報及びエッジ数情報とに同時にデコードする。
【００６６】
ビットマップ−座標デコーダ１２０４によってデコードされた、バイトデータ内に含まれるエッジ数と全てのエッジの位置の座標情報は、エッジ数レジスタ１２０６と下位エッジｘ座標レジスタ１２０５に格納される。ビットマップ−座標デコーダ１００１ｃはｘ方向のバイトカウンタ１２０７を持っており、これがエッジの上位ｘ座標となる。
【００６７】
下位エッジｘ座標レジスタ１２０５はバレルシフタ１２１１によってシフトされ上位ｘ座標カウンタ１２０７の出力とビット結合されてｘ座標データ結合レジスタ１２１２に格納される。
【００６８】
バイト内のエッジ数はエッジ数カウンタ１２１３に入力され、ライン内のエッジ数がカウントするのに用いられる。ライン内エッジ数の下位ビットと現在バイトのエッジ数であるエッジ数レジスタ１２０６の出力がデコーダ１２１４に入力され、バレルシフタ１２１１のシフト量と、ｘ座標データ結合レジスタ１２１２のロード信号が生成される。
【００６９】
このバレルシフタ１２１１の動作は、第１の実施形態において、図２（ａ）の画像を例に説明したものと同様であるので、その詳細な説明は省略する。
【００７０】
ｘ座標データ結合レジスタ１２１２が満杯になると、結合された座標データはｘ座標ライトＤＭＡＣ１００１ｆに送られ、エッジ座標データ１１０４としてメインメモリ１００３に格納される。エッジ座標データ１１０４の格納アドレスはアドレスカウンタ１２１５によってカウントされ、ラインの先頭のアドレスはデータ結合部１００１ｅに送られる。
【００７１】
また、１回の出力でバレルシフタ１２１１からレジスタ１２１２に出力できない場合には、満杯になったレジスタ１２１２からライトＤＭＡＣ１００１ｆに座標データが送られた後に、バレルシフタ１２１１に残った値を適宜シフトしてレジスタ１２１２に送る。
【００７２】
ビットマップ−座標デコーダ１００１ｃは上位ｘ座標カウンタ１２０７の値とラインの長さのバイト数をライン終了比較器１２０８によって比較しており、上位ｘ座標カウンタ１２０７の値がライン終了まで達したところでライン終了信号がライン終了レジスタ１２０９に保持される。ライン終了情報が発生すると、アドレスカウンタ１２１５の値とラインエッジ数カウンタ１２１３の値がｙ座標データ結合回路１００１ｅへ送られる。ビットマップ−座標デコーダ１００１ｃはまたｙ方向のラインカウンタ１２１０を持っており、ライン終了レジスタ１２０９の情報をカウントしつつ、ビットマップ画像の総ライン数と比較している。ライン数が最終に達すると処理終了信号を発生し、ライトＤＭＡＣ１００１ｆ,  １００１ｇに保持したデータ全てをメモリ１００３へ書き出すように指示し、全体の処理を終了させる。
【００７３】
＜ソフトウェア処理＞
図１３は本実施の形態の輪郭抽出処理のソフトウェアシーケンスを示したフローチャートである。なお本フローチャートの処理は、メインメモリ１００３に予め格納されているプログラムに基づき、ＣＰＵ１００２が実行する。
【００７４】
はじめに、エッジ座標抽出回路１００１が生成するエッジ情報を格納するメモリ領域を確保し（Ｓ１３０１）、続いてエッジ座標抽出回路１００１に必要なビットマップフォントが格納されたアドレス等のパラメータを設定し（Ｓ１３０２）、エッジ座標抽出回路１００１を起動してエッジ座標抽出処理を開始する（Ｓ１３０３）。
【００７５】
次にエッジ座標抽出回路１００１が２ライン以上の処理を終えたかを判断し（Ｓ１３０４）、まだ処理を終えていなければ２ライン以上の処理を終えるまで待ち、２ライン以上の処理を終えていれば、注目ラインを２ライン目に指定し、エッジ座標抽出処理と並列にエッジ座標から輪郭情報を生成する処理を開始する（Ｓ１３０５）。
【００７６】
エッジ座標から輪郭情報を生成する処理は、注目エッジの初期値が主走査の原点方向にあることを前提に、まず注目ラインの未処理エッジ数が０かを判断する（Ｓ１３０６）。
【００７７】
ステップＳ１３０６において、未処理エッジ数が０よりも大きい場合には、注目エッジが前ラインから注目ラインへ移った際の傾きを計算し、輪郭情報に付加する（Ｓ１３０７）。次に注目エッジを主走査方向に進め（Ｓ１３０８）、ステップＳ１３０６に戻り、再度未処理エッジ数が０かを判断する。
【００７８】
ステップＳ１３０６において、未処理エッジ数が０で合った場合には、つぎに注目ラインを１進め、注目エッジを主走査原点方向に戻す（Ｓ１３０９）。次にビットマップすべてのラインに対して処理を行ったか、すなわち、残りライン数が０であるかを判断し（Ｓ１３１０）、ラインが残っている場合には次にエッジ抽出回路１００１が注目ラインの処理を終えているかを判断し（Ｓ１３１１）、注目ラインの処理を終えていない場合には処理が進むのを待ち、注目ラインの処理が終えている場合には、ステップＳ１３０６に戻り、また未処理エッジ数の判断を行う。もしビットマップフォントのすべてのラインに対して処理を終えたならば、処理は終了である。
【００７９】
本実施形態において、ビットマップ−座標デコーダ１２０４の入出力を示した真理値表は、第１の実施形態で示した図４〜９の真理値表と同一である。本実施の形態はＭＳＢ側がビットマップの左端としており、０が白、１が黒、背景が白としているため、例えばバイトレジスタ１２０３の出力が０ｘ０６の場合には、エッジ数の出力が２、第１エッジの位置（下位ｘ座標）が５、第２エッジの位置（下位ｘ座標）が７をデコードし、第３エッジ以降の値に無効を示す０がデコードされ、これらのデータがエッジ数レジスタ１２０６、下位ｘ座標レジスタ１２０３へと格納される。
【００８０】
なお、本実施形態では、第１の実施形態と同様に、図４〜図９で示したテーブルを用いたが、これらは、あくまで例示的なものに過ぎず、レンダリング処理のために別途設定した専用のテーブルを適用してもよい。
【００８１】
以上説明したように、本実施形態によれば、オブジェクトの輪郭情報生成処理の前半部分にあたるエッジ抽出処理を高速に行うことが可能となり、さらにエッジ同士の関連を導出して輪郭情報を生成する処理をＣＰＵ上のソフトウェアで並列に行うことによって、オブジェクトの輪郭情報生成処理を短時間に行うことが可能となる。
【００８２】
特に、文字が多く含まれる文書のレンダリングを行う場合においても、フォントオブジェクト単位で高速な輪郭抽出処理ができるので、高速なプリント処理が実行可能となる。
【００８３】
【発明の効果】
本発明によれば、エッジ抽出処理を高速に行うことのできる画像処理装置及び画像処理方法を提供することができる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態の構成を示したブロック図である。
【図２】本発明の第１の実施形態のエッジ座標抽出回路が生成するデータ形式を示した模式図である。
【図３】本発明の第１の実施形態のエッジ座標抽出回路のデータパスを示したブロック図である。
【図４】本発明の実施形態のデコーダ回路の動作の真理値表を示す図である。
【図５】本発明の実施形態のデコーダ回路の動作の真理値表を示す図である。
【図６】本発明の実施形態のデコーダ回路の動作の真理値表を示す図である。
【図７】本発明の実施形態のデコーダ回路の動作の真理値表を示す図である。
【図８】本発明の実施形態のデコーダ回路の動作の真理値表を示す図である。
【図９】本発明の実施形態のデコーダ回路の動作の真理値表を示す図である。
【図１０】本発明の第２の実施形態の構成を示したブロック図である。
【図１１】本発明の第２の実施形態のエッジ座標抽出回路が生成するデータ形式を示した模式図である。
【図１２】本発明の第２の実施形態のエッジ座標抽出回路のデータパスを示したブロック図である。
【図１３】本発明の第２の実施形態の輪郭抽出処理のソフトウェアシーケンスを示したフローチャートである。
【符号の説明】
１０１ : エッジ座標抽出回路
１０１ａ : リードＤＭＡＣ
１０１ｂ : データセレクタ
１０１ｃ : ビットマップ−座標デコーダ
１０１ｄ : ｘ座標データ結合回路
１０１ｅ : ｙ座標データ結合回路
１０１ｆ : ｘ座標データライトＤＭＡＣ
１０１ｇ : ｙ座標データライトＤＭＡＣ
１０２ : ＣＰＵ
１０３ : メモリ
１０４ : クロスバー回路
１０５ : ネットワークインタフェース
１０６ : スキャナ
１０７ : スキャナインタフェース
１０８ : プリンタ
１０９ : プリンタインタフェース
１１０ : イメージ処理回路
１１１ : マルチファンクションコントローラ
２０１ : ビットマップ画像
２０２ : エッジのｘ座標
２０３ : ライン内のエッジ数
２０４ : ラインの先頭へのポインタ
３０１ : ビットマップデータバッファ
３０２ : バイトセレクタ
３０３ : バイトバッファ
３０４ : ビットマップ−座標デコーダ
３０５ : 下位 ｘ 座標レジスタ
３０６ : エッジ数レジスタ
３０７ : 上位 ｘ 座標カウンタ
３０８ : ライン終了比較器
３０９ : ライン終了フラグレジスタ
３１０ : ライン数カウンタ
３１１ : バレルシフタ
３１２ : ｘ座標データ結合レジスタ
３１３ : ラインエッジ数カウンタ
３１４ : デコーダ
３１５ : アドレスカウンタ
【図１】
0004164272.tif 000002
【図２】
0004164272.tif 000003
【図３】
0004164272.tif 000004
【図４】
0004164272.tif 000005
【図５】
0004164272.tif 000006
【図６】
0004164272.tif 000007
【図７】
0004164272.tif 000008
【図８】
0004164272.tif 000009
【図９】
0004164272.tif 000010
【図１０】
0004164272.tif 000011
【図１１】
0004164272.tif 000012
【図１２】
0004164272.tif 000013
【図１３】
0004164272.tif 000014