(57)【特許請求の範囲】
【請求項１】
図形を直線の連続として表現する点列からなるベクトルデータである粗輪郭ベクトルデータを獲得する獲得手段と、
前記獲得された粗輪郭ベクトルデータに対して、前記点列を関数近似するための区間に分割するための分割点を設定して、関数近似区間の設定を行なう関数近似区間設定手段と、
前記設定された関数近似区間毎に前記点列を関数近似する関数近似処理手段と、
前記関数近似された関数近似区間毎の近似誤差を算出する区間内近似精度算出手段と、
前記算出された近似誤差に基づいて、複数の前記関数近似区間の中から、前記算出された近似誤差が最大となる関数近似区間を、近似精度の向上を図るべき関数近似区間として同定する分割対象区間同定手段と、
前記分割対象区間同定手段にて同定された前記近似精度の向上を図るべき関数近似区間を区間分割することにより、該近似精度の向上を図るべき関数近似区間においてさらに複数の関数近似区間を設定する区間分割手段と、
これまでに得られた、前記分割点が設定された粗輪郭ベクトルデータおよび各関数近似区間の近似誤差の情報を少なくとも含むデータのデータ量が既定のデータ量に達したか否かの判定と、処理を開始してからの経過時間を測定し、該測定された経過時間が既定の時間を超えたか否かの判定との少なくとも一方の判定を行う判定手段と、を備え、
前記判定手段が、前記データ量が前記既定のデータ量に達したと判定するか、又は、前記経過時間が前記既定の時間を超えたと判定するまでは、前記区間分割手段で区間分割することにより設定した関数近似区間に対する前記関数近似処理手段による関数近似処理と、前記区間内近似精度算出手段による近似誤差の算出処理と、前記分割対象区間同定手段による関数近似区間の同定処理と、当該同定された関数近似区間に対する前記区間分割手段による分割処理とを繰り返すことを特徴とする画像処理装置。
【請求項２】
前記判定手段は、更に、前記分割対象区間同定手段で同定された前記近似精度の向上を図るべき関数近似区間の近似誤差が、既定の閾値を超えるか否かの判定を行い、
前記判定手段が、前記データ量が前記既定のデータ量に達したと判定するか又は前記経過時間が前記既定の時間を超えたと判定するまでで、且つ、前記分割対象区間同定手段で同定された前記近似精度の向上を図るべき関数近似区間の近似誤差が、前記既定の閾値を超えていると判定した場合に、前記区間分割手段は、前記近似精度の向上を図るべき関数近似区間を区間分割することにより、該近似精度の向上を図るべき関数近似区間においてさらに複数の関数近似区間を設定することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記獲得手段は、
ベクトル化対象とする２値画像を獲得する２値画像獲得手段と、
前記２値画像から該２値画像に含まれる図形の境界から、前記粗輪郭ベクトルデータを抽出する粗輪郭抽出手段と
を有することを特徴とする請求項１または２に記載の画像処理装置。
【請求項４】
前記関数近似は、３次のベジェ曲線による近似であることを特徴とする請求項１乃至３のいずれかに記載の画像処理装置。
【請求項５】
獲得手段が、図形を直線の連続として表現する点列からなるベクトルデータである粗輪郭ベクトルデータを獲得する獲得工程と、
関数近似区間設定手段が、前記獲得された粗輪郭ベクトルデータに対して、前記点列を関数近似するための区間に分割するための分割点を設定して、関数近似区間の設定を行なう関数近似区間設定工程と、
関数近似処理手段が、前記設定された関数近似区間毎に前記点列を関数近似する関数近似処理工程と、
区間内近似精度算出手段が、前記関数近似された関数近似区間毎の近似誤差を算出する区間内近似精度算出工程と、
分割対象区間同定手段が、前記算出された近似誤差に基づいて、複数の前記関数近似区間の中から、前記算出された近似誤差が最大となる関数近似区間を、近似精度の向上を図るべき関数近似区間として同定する分割対象区間同定工程と、
判定手段が、これまでに得られた、前記分割点が設定された粗輪郭ベクトルデータおよび各関数近似区間の近似誤差の情報を少なくとも含むデータのデータ量が既定のデータ量に達したか否かの判定と、処理を開始してからの経過時間が既定の時間を超えたか否かの判定との少なくとも一方を行う判定工程と、
区間分割手段が、前記判定工程で、前記データ量が前記既定のデータ量に達したと判定するか、又は、前記経過時間が前記既定の時間を越えたと判定するまでは、前記分割対象区間同定工程で同定された前記近似精度の向上を図るべき関数近似区間において新たな分割点を設定することにより、前記近似精度の向上を図るべき関数近似区間において更に複数の関数近似区間を設定する区間分割工程と、
制御手段が、前記判定工程で前記データ量が前記既定のデータ量に達したと判定するか、又は、前記経過時間が前記既定の時間を超えたと判定するまでは、前記区間分割工程で区間分割することにより設定した関数近似区間に対して前記関数近似処理工程での関数近似処理と、前記区間内近似精度算出工程での近似誤差の算出処理と、前記分割対象区間同定工程での関数近似区間の同定処理と、当該同定された関数近似区間に対する前記区間分割工程での分割処理とを繰り返すように制御する制御工程と、
を有することを特徴とする画像処理方法。
【請求項６】
前記判定工程では、更に、前記分割対象区間同定工程で同定された前記近似精度の向上を図るべき関数近似区間の近似誤差が、既定の閾値を超えるか否かの判定を行い、
前記区間分割工程では、前記判定工程で、前記データ量が前記既定のデータ量に達したと判定するか又は前記経過時間が前記既定の時間を超えたと判定するまでで、且つ、前記分割対象区間同定工程で同定された前記近似精度の向上を図るべき関数近似区間の近似誤差が前記既定の閾値を超えていると判定した場合に、前記近似精度の向上を図るべき区間を区間分割することにより、該近似精度の向上を図るべき関数近似区間においてさらに複数の関数近似区間を設定することを特徴とする請求項５に記載の画像処理方法。
【請求項７】
前記獲得工程では、
ベクトル化対象とする２値画像を獲得する２値画像獲得工程と、
前記２値画像から該２値画像に含まれる図形の境界から、前記粗輪郭ベクトルデータを抽出する粗輪郭抽出工程と
を有することを特徴とする請求項５または６に記載の画像処理方法。
【請求項８】
前記関数近似は、３次のベジェ曲線による近似であることを特徴とする請求項５乃至７のいずれかに記載の画像処理方法。
【請求項９】
コンピュータ装置が実行可能なプログラムであって、前記プログラムを実行するコンピュータ装置を、前記請求項１乃至４のいずれかに記載の画像処理装置として機能させることを特徴とするプログラム。
【請求項１０】
コンピュータにより読み出し可能な、請求項９に記載のプログラムを格納した記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置および画像処理方法に関し、より詳細には、図形の輪郭や芯線を関数近似する画像処理装置および画像処理方法に関するものである。
【背景技術】
【０００２】
近年、ペーパーレス化への要求が高まり、既存の画像データを電子化して再利用することが頻繁に行われるようになってきた。従来、画像データの再利用は、画像データを２値化処理した後にベクトル化技術を用いてベクトルデータに変換し、このベクトルデータをＣＡＤソフト等で使用するという形で行われてきている。
【０００３】
一方、近年、オフィス環境においても環境問題が重要視され、その問題の解決策の一つとして、オフィスでのペーパーレス化が急速に進んでいる。このペーバーレス化を実現する方法として、紙文書をスキャナより読み取り、電子データに変換して情報を格納する方法が挙げられる。しかしながら、紙文書は電子データとして保存可能であるが、ファイル自体がイメージ情報であるので、紙文書自体を再利用することはできないという問題もある。また、電子データとして記憶媒体上に蓄積させる場合であっても、高画質での保存を望めば電子データのファイルサイズも大きくなるなど、記憶するイメージ情報の画質と、その電子データを格納するための記憶領域の容量とのトレードオフの問題も生じる。
【０００４】
このトレードオフとなる２つの問題を同時に解決する方法として、読取られた画像を文字領域、写真画像領域、線画領域、表領域等のオブジェクト毎に分割し、それぞれをベクトル化処理して、電子化される画像データの容量を軽減する方法が挙げられる。この場合、文字、線画、表などの領域は２値画像領域として２値化処理してアウトライン化処理によりベクトル化（以下、「アウトラインベクトル化」）することで、データ量を削減し、高画質で再利用可能な電子文書を生成することが可能になる。
【０００５】
２値画像のベクトル化に関しては、出願人は既に特許文献１を提案している。この特許文献１では以下のような構成が開示されている。
【０００６】
すなわち、注目画素と、その近傍画素の状態により、予め定められた位置を輪郭線を構成する点とし、近傍画素の状態により該輪郭線を構成する点の接続方向を決定する工程を実行する。次いで、上記輪郭線を構成する点と、該輪郭線を構成する他の点との接続状態を判断する工程を実行する。次いで、上記注目画素の位置をラスタ走査順に画像データ上を更新し、注目画素毎に近傍画素の状態に基づいて上記工程を実行し、輪郭点を抽出する。以上の構成において、画像データにおける注目画素と、その近傍画素の状態を保持し、この注目画素をラスタ走査順に取り出し、その注目画素とその近傍画素の状態に基づいて、水平方向及び垂直方向の画素間ベクトルを検出する。これら画素間ベクトル同士の接続状態を判別して、この判別された画素間ベクトルの接続状態をもとに、画像データの輪郭を抽出するように動作する。このような方法が特許文献１において提案されている。
【０００７】
特許文献１に記載の方法は、画像の中の全ての輪郭線を１回のラスタ走査順だけで抽出でき、かつ、全画像データを記憶するための画像メモリを必要としないため、メモリの容量を少なくできる効果を有している。また、入力画像の画素の中心位置ではなく、画素の縁単位に輪郭を抽出することによって、１画素巾の細線に対しても有為な幅を有する輪郭線抽出法である。更に、原画中の画素の４方向に連結した連結画素領域の輪郭線を抽出するのみならず、８方向に連結した画素領域も抽出可能であることが紹介されている。
【０００８】
さらに、出願人は特許文献２において、特許文献１に開示されるベクトル抽出ルールのモジュール化により効率的な輪郭点抽出が可能であることを開示している。
【０００９】
また、一方で、出願人は既に特許文献３を提案している。この特許文献３において、２値画像の輪郭情報を用いて高画質な変倍画像を得る画像処理装置を紹介している。該提案は、２値画像からアウトラインベクトルを抽出し、該抽出したアウトラインベクトル表現の状態で所望の倍率（任意）で滑らかに変倍されたアウトラインベクトルを作成し、該滑らかに変倍されたアウトラインベクトルから２値画像を再生成する。これによって、所望の倍率（任意）で変倍された高画質のデジタル２値画像を得るようにするものである。ここで、２値画像からアウトラインベクトルを抽出する方法としては、一例として、上述の、特許文献１や特許文献２で開示される方法が用いられる。
【００１０】
さらに、出願人は既に特許文献４を提案している。この特許文献４においては、２値画像の輪郭情報を直線のみならず、２次や３次のベジェ（Bezier）曲線近似をすることで、より少ないデータ量で高画質な変倍画像を表現する輪郭情報を関数近似する処理手法と処理装置を開示している。２値画像からアウトラインベクトルを抽出し、該抽出したアウトラインベクトル表現の状態で、特許文献４の方法で滑らかに関数近似されたアウトラインベクトルを用いても、やはり所望の倍率（任意）で変倍された高画質のデジタル２値画像を得ることができる。ここで、２値画像からアウトラインベクトルを抽出する方法としては、上述の、特許文献１や特許文献２で開示される方法を用いることができる。
【００１１】
２図(a)〜(d)は、上記の２値画像のアウトラインベクトル処理の流れによる一連の処理経過の例を示す図である。すなわち、２値画像からアウトラインベクトルを抽出し、該抽出したアウトラインベクトル表現を滑らかに関数近似したアウトラインベクトルを用いて所望の倍率（任意）で変倍された高画質のデジタル２値画像を得る一連の流れでのデータの様子を表している。
【００１２】
２図(a)は、入力される２値画像の一例を示している。２図(b)は、２図(a)の２値画像から、特許文献１または２による方法で抽出される輪郭ベクトルデータを輪郭画像として描画して可視化したものである。２図(c)は、同抽出された輪郭ベクトルデータを特許文献４による方法で滑らかに関数近似して得られるアウトラインベクトルを描画して可視化したものである。２図(d)は、同平滑化（関数近似）されたベクトルを中塗りして得られる所望の倍率（任意）で変倍された高画質のデジタル２値画像の例である。
【００１３】
先述のように、ペーパーレス化への要求が高まりのもと、ビジネス文書においても、既存の画像データを電子化して再利用することが望まれている。とりわけ、原図を所望とされる変倍率を反映した形で変倍するような再利用の形態に対しては、上述の特許文献１または２と特許文献４により、実現が可能である。すなわち、オリジナル文書中の２値図形の輪郭（アウトライン）ベクトルを抽出して、２次元形状を任意の拡大縮小率で変倍することで、その実現が可能である。
【００１４】
アウトラインベクトル化による電子文書は、上述の如く、２値画像より得られる輪郭線を抽出し、得られた輪郭線の曲線部をベジェ曲線等の曲線関数により関数近似することで求められる。ここで、ベジェ曲線等の曲線関数により関数近似をする場合、一般的に輪郭線上の点列と、ベジェ曲線の誤差を求め、曲線の最適化を行う必要があるので、膨大な繰り返し演算が必要となり、多大な処理時間を要することになる。
【００１５】
この処理時間を短縮化する近似計算として、輪郭点間を曲線で補間する方法も考えられているが、輪郭点データに対しそのまま曲線補間を行えば、補間点数の増加を招き、アウトラインベクトル化処理の圧縮効果が薄くなるという問題も生じる。また、直線近似などにより補間点数を減らす処理を行った場合、直線近似のための処理時間の増加を招くことになる。すなわち、アウトラインベクトル化によりデータ量を削減することは可能であるが、そのための近似計算においては、演算量が多くなり多大な演算時間が必要となる。従って、アウトラインベクトル化を行いつつ演算時間の短縮化を図る場合であっても、データ量の軽減効果が十分得られないという問題が生じる。
【００１６】
そこで、上述の特許文献４における、輪郭ベクトルの平滑化（関数近似）は、基本的に、ベジェ曲線等の曲線関数により関数近似をする区間を定めるアンカーポイントの決定を次のように行っている。すなわち、注目する辺ベクトルの前後に連なる一連の辺ベクトルの向きや長さの組み合わせをもとに決定している。特許文献４では、このアンカーポイントによって分割された区間内の輪郭点列をベジェ曲線で近似ように構成する。これによって、それまで一般に行なわれてきた、輪郭線上の点列とベジェ曲線の誤差を求め曲線の最適化を行うための膨大な繰り返し演算を不要とし、それまでの従来技術のような多大な処理時間を要すことのないアウトラインベクトル化処理を可能としている。
【００１７】
特許文献４によれば、ベクトル平滑化（関数近似）の流れは、以下の如きである。まず、粗輪郭データと称して、２値のラスター画像のデータより抽出された、水平ベクトル、垂直ベクトルが交互に並ぶ構成となる輪郭データを入力とし、粗輪郭上の線分より接線線分を抽出する。抽出された接線線分よりアンカーポイントを抽出する。そして、抽出されたアンカーポイント間の単数または複数の線分群として構成されるグループに直線をあてはめ、あるいは、2次もしくは３次ベジェ曲線をあてはめベジェ曲線近似を行い、直線、あるいは、2次もしくは3次のベジェ曲線により置きかえていく。
【００１８】
ここで、アンカーポイントとして定めた点をもとに、アンカーポイント間にある輪郭点を１つのグループとして関数近似している方法は、関数近似法としての基本的な手法である。また、アンカーポイントは、その間が、2次もしくは３次ベジェ曲線、及び直線のいずれに関数近似されたとしても、アンカーポイント自体の位置（座標値）は、変化しないという特徴をもつ。
【００１９】
特許文献４によれば、接線線分とするベクトルの抽出の条件として、  
［１］注目するベクトルの前後のベクトルの向きが互いに逆向きであるもの  
［２］抽出済みの主接線線分に隣接し、ベクトルの長さL1がL1≧θ4を満たすもの  
［３］ベクトルの長さL2がL2≧θ5を満たすもの  
等の条件が開示されている。ここで、θ4、θ5は予め定める定数である。
【００２０】
また、アンカーポイントの抽出に関して、抽出された接線線分上に新たな点を抽出し、それをアンカーポイントとする。アンカーポイントは接線線分の端２つに対しそれぞれ抽出される。よって、基本的には、一つの接線線分に対し２つのアンカーポイントが抽出されるが、該２つのアンカーポイントが一致した場合には一つのアンカーポイントのみ抽出されることになる。２つのアンカーポイントが抽出される場合は、アンカーポイントに挟まれた部位は自動的にオブジェクト上の直線となる。接線線分上の一方の端に対するアンカーポイント抽出方法としては、注目する接線線分であるベクトルに隣接するベクトルが接線線分であれば、この隣接する側の端点をアンカーポイントとする。隣接する線分が接線線分で無い場合、さらにその隣、即ち、着目する接線線分のベクトルV2（その長さを|V2|と表す）の２本前の線分のベクトルV1（その長さを|V1|と表す）から、V2ベクトル上端点よりa|V1|離れた点をアンカーポイントとする。
【００２１】
また、かくして定めた区間上の輪郭点列の関数近似に関しては、以下の様に行なわれることが特許文献４に開示されている。  
まず、図８（特許文献４の図１９に相当）に示すように、ベジェ曲線等の曲線関数により関数近似をする区間上の輪郭点列であるＮ個の点をそれぞれｐ１，ｐ２，…，ｐＮとする。このとき、これら点列の始点ｐ１、終点ｐＮはアンカーポイントである。ここで、アンカーポイントｐ１、ｐＮを結ぶ線分ｐ１ｐＮより最も距離の離れている曲線上の点ｐｆを求める。関数近似処理を簡易に行うため、コントロールポイントを結ぶ線分Ｃ１Ｃ２が線分ｐ１ｐＮに対して平行となるように近似する。そして、点ｐｆと線分ｐ１ｐＮとの距離をＬとすると、点Ｃ１、Ｃ２より線分ｐ１ｐＮへの距離が（４／３）×Ｌとなるように、Ｃ１、Ｃ２を求める。
【００２２】
即ち、ｐｆの座標値が（ｐfx，ｐfy）であった場合、ｐ１、ｐＮの各座標値（ｐ1x，ｐ1y）、（ｐNx，ｐNy）とｐ１における接線ベクトルｐ１Ｃ１（ｐcx，ｐcy）を用いると、Ｃ１の座標値（Ｃ1x，Ｃ1y）は、
Ｃ1x＝Ｋ×ｐfx＋ｐ1x  
Ｃ1y＝Ｋ×ｐfy＋ｐ1y  
Ｋ＝（３ｐ1x−４ｐfx）（ｐNy−ｐ1y）＋（ｐNx−ｐ1x）（４ｐfy−３ｐ1y）  
＋ｐ1x（ｐNy−ｐ1y）−ｐ1y（ｐNx−ｐ1x）  
/（３（ｐNy−ｐ1y）ｐcx＋３（ｐNx−ｐ1x）ｐcy）  
となり、ｐｆの座標値より一意に決定することができる。また、Ｃ２についても、Ｃ１と同様に求めることが可能である。  
尚、上述の分割点が、曲線近似におけるアンカーポイントとなる。また、アンカーポイントにおける接線ベクトルは、区分曲線への分割時に、複数の線分の組み合わせにより、パターンマッチング的に方向ベクトルを抽出して、これをもってアンカーポイントにおける接線ベクトルとする。
【００２３】
このようなことが特許文献４には開示されているのである。
【００２４】
かくして、上述の特許文献４では、それまで一般に行なわれてきた、輪郭線上の点列とベジェ曲線の誤差を求め曲線の最適化を行うための膨大な繰り返し演算を不要とした処理が開示されている。すなわち、それまでの従来技術のような多大な処理時間を要すことのないアウトラインベクトル化処理を開示している。
【００２５】
【特許文献１】特許第３０２６５９２号明細書
【特許文献２】特開平０５−１０８８２３号公報
【特許文献３】特許第３０４９６７２号明細書
【特許文献４】特開２００５−３４６１３７号公報
【発明の開示】
【発明が解決しようとする課題】
【００２６】
ところで、昨今のデジタル複写機は、画像通信、画像蓄積、画像複写、画像プリント等の複数の機能を有するデジタル複合機となっている。このデジタル複合機は、文書画像読み取りスキャナ部、デジタルプリンタ部、デジタル画像データ処理部、データ送受信部、データ蓄積管理部等の各部分よりシステム構成される。このようなデジタル複合機に上述の電子文書の生成機能をもたせることで、オフィス環境の改善に大きく寄与することが期待される。
【００２７】
このようなデジタル複合機に上述の電子文書の生成機能をもたせることを考えると、装置コストや、処理時間等には、実用面からの要請による上限が必要となる。より少ないデータ量で、かつ、高速な処理が可能で、生成される関数の近似精度が高いベクトル化が望まれるが、これらの間には、トレードオフがある。即ち、アンカーポイントを増やしてデータ量をふやせば関数近似する各区間をより短く設定することが可能となり、一般的により精度の高い関数近似が可能になる傾向がある。また、処理時間を増やせば、関数近似の精度の比較的悪い部分の精度を上げるための処理を行なうことも可能となる。
【００２８】
上記特許文献４に開示された輪郭ベクトルの平滑化（関数近似）は、それまでの従来技術のような多大な処理時間を要すことのないアウトラインベクトル化処理を可能としている点で優れており、非常に有用な技術である。すなわち、上記輪郭ベクトルの平滑化（関数近似）により、輪郭線上の点列とベジェ曲線の誤差を求め曲線の最適化を行うための膨大な繰り返し演算が不要となり、従来技術のような多大な処理時間を要すことのないアウトラインベクトル化処理が可能となる。しかしながら、上述の如きトレードオフを考慮したデータ量、処理時間、近似精度の最適化機構を有するものではなかった。
【００２９】
本発明は、上述した従来例の状況に鑑みなされたものである。その目的は、比較的高速な処理の範囲で、データ量の許す範囲でBezier（ベジエ）近似精度を向上させ、既定の処理時間内でBezier近似精度を向上させる画像処理装置および画像処理方法を提供することにある。すなわち、本発明の目的は、装置構成や処理時間の点で実用上妥当とされる制限内で、従来に比し近似精度の向上した関数近似に基づくベクトル化処理を可能とする処理構成を提案することにある。
【課題を解決するための手段】
【００３０】
このような課題を解決するために、本発明は画像処理装置であって、図形を直線の連続として表現する点列からなるベクトルデータである粗輪郭ベクトルデータを獲得する獲得手段と、前記獲得された粗輪郭ベクトルデータに対して、前記点列を関数近似するための区間に分割するための分割点を設定して、関数近似区間の設定を行なう関数近似区間設定手段と、前記設定された関数近似区間毎に前記点列を関数近似する関数近似処理手段と、前記関数近似された関数近似区間毎の近似誤差を算出する区間内近似精度算出手段と、前記算出された近似誤差に基づいて、複数の前記関数近似区間の中から、前記算出された近似誤差が最大となる関数近似区間を、近似精度の向上を図るべき関数近似区間として同定する分割対象区間同定手段と、前記分割対象区間同定手段にて同定された前記近似精度の向上を図るべき関数近似区間を区間分割することにより、該近似精度の向上を図るべき関数近似区間においてさらに複数の関数近似区間を設定する区間分割手段と、これまでに得られた、前記分割点が設定された粗輪郭ベクトルデータおよび各関数近似区間の近似誤差の情報を少なくとも含むデータのデータ量が既定のデータ量に達したか否かの判定と、処理を開始してからの経過時間を測定し、該測定された経過時間が既定の時間を超えたか否かの判定との少なくとも一方の判定を行う判定手段と、を備え、前記判定手段が、前記データ量が前記既定のデータ量に達したと判定するか、又は、前記経過時間が前記既定の時間を超えたと判定するまでは、前記区間分割手段で区間分割することにより設定した関数近似区間に対する前記関数近似処理手段による関数近似処理と、前記区間内近似精度算出手段による近似誤差の算出処理と、前記分割対象区間同定手段による関数近似区間の同定処理と、当該同定された関数近似区間に対する前記区間分割手段による分割処理とを繰り返すことを特徴とする。
【００３１】
また、本発明は、画像処理方法であって、獲得手段が、図形を直線の連続として表現する点列からなるベクトルデータである粗輪郭ベクトルデータを獲得する獲得工程と、関数近似区間設定手段が、前記獲得された粗輪郭ベクトルデータに対して、前記点列を関数近似するための区間に分割するための分割点を設定して、関数近似区間の設定を行なう関数近似区間設定工程と、関数近似処理手段が、前記設定された関数近似区間毎に前記点列を関数近似する関数近似処理工程と、区間内近似精度算出手段が、前記関数近似された関数近似区間毎の近似誤差を算出する区間内近似精度算出工程と、分割対象区間同定手段が、前記算出された近似誤差に基づいて、複数の前記関数近似区間の中から、前記算出された近似誤差が最大となる関数近似区間を、近似精度の向上を図るべき関数近似区間として同定する分割対象区間同定工程と、判定手段が、これまでに得られた、前記分割点が設定された粗輪郭ベクトルデータおよび各関数近似区間の近似誤差の情報を少なくとも含むデータのデータ量が既定のデータ量に達したか否かの判定と、処理を開始してからの経過時間が既定の時間を超えたか否かの判定との少なくとも一方を行う判定工程と、区間分割手段が、前記判定工程で、前記データ量が前記既定のデータ量に達したと判定するか、又は、前記経過時間が前記既定の時間を越えたと判定するまでは、前記分割対象区間同定工程で同定された前記近似精度の向上を図るべき関数近似区間において新たな分割点を設定することにより、前記近似精度の向上を図るべき関数近似区間において更に複数の関数近似区間を設定する区間分割工程と、制御手段が、前記判定工程で前記データ量が前記既定のデータ量に達したと判定するか、又は、前記経過時間が前記既定の時間を超えたと判定するまでは、前記区間分割工程で区間分割することにより設定した関数近似区間に対して前記関数近似処理工程での関数近似処理と、前記区間内近似精度算出工程での近似誤差の算出処理と、前記分割対象区間同定工程での関数近似区間の同定処理と、当該同定された関数近似区間に対する前記区間分割工程での分割処理とを繰り返すように制御する制御工程と、を有することを特徴とする。
【発明の効果】
【００３２】
本発明によれば、装置構成や処理時間の点で実用上妥当とされる制限内で、従来に比し近似精度の向上した関数近似に基づくベクトル化処理を可能とする処理構成処理を実現することが可能となる。
【発明を実施するための最良の形態】
【００３３】
以下、図面を参照して本発明の実施形態を詳細に説明する。なお、以下で説明する図面で、同一機能を有するものは同一符号を付け、その繰り返しの説明は省略する。  
本発明の一実施形態では、画像処理装置は、図名を直線の連続として表現する点列からなるベクトルデータ（粗輪郭ベクトルデータとも呼ぶ）を獲得する。この方法としては例えば、２値画像獲得手段によりベクトル化対象とする２値画像を獲得し、粗輪郭抽出手段にて、２値画像獲得手段により得られた２値画像から、これに含まれる図形の境界を関数近似処理前のベクトルとして抽出する。この関数近似処理前のベクトルを、粗輪郭、もしくは、粗輪郭ベクトルとも称する。
【００３４】
関数近似区間設定（アンカーポイント設定）手段では、粗輪郭抽出手段において得られた粗輪郭上の点列を高次の関数としてのベジェ曲線等の曲線関数により関数近似するための区間に分割するための分割点（アンカーポイント）の設定を行なう。関数近似処理（コントロールポイント算出）手段では、関数近似区間設定（アンカーポイント設定）手段で設定された関数近似区間毎にベジェ曲線等の曲線関数により関数近似をする。区間内近似精度算出（区間内誤差分値、区間内最大誤差値）手段では、関数近似処理（コントロールポイント算出）手段でベジェ曲線等の曲線関数により関数近似された関数近似区間毎の近似精度を算出する。
【００３５】
分割対象区間同定手段は、区間内近似精度算出（区間内誤差分値、区間内最大誤差値）手段で算出された関数近似区間毎の近似精度から近似精度の向上を図るべき区間を同定する。区間分割手段は、分割対象区間同定手段において同定された近似精度の向上を図るべき区間を複数の関数近似区間に分割する。分割された複数の関数近似区間は、それぞれ関数近似処理（コントロールポイント算出）手段でベジェ曲線等の曲線関数により関数近似される。
【００３６】
画像処理装置は、上記各手段に加えて、後述する、データ量判定手段および処理時間計測判定手段の少なくとも一方を備えている。
【００３７】
データ量判定手段は、上記分割されて得られた複数の関数近似区間のそれぞれの関数近似結果により分割される前の関数近似区間での関数近似結果を置き換えることにより生成されるデータ量が既定のデータ量に達するか否かを判定する。既定のデータ量に達しない場合には、画像処理装置は、上記分割されて得られた複数の関数近似区間のそれぞれの関数近似結果により分割される前の関数近似区間での関数近似結果を置き換える。さらに、区間内近似精度算出（区間内誤差分値、区間内最大誤差値）手段により上記複数の関数近似区間のそれぞれの関数近似結果に対する近似精度を改めて算出する。そして、分割対象区間同定手段により、次に近似精度の向上を図るべき区間を同定させる。そうではない場合には、置き換え、近似精度の改めての算出、及び、次に近似精度の向上を図るべき区間の同定は行なわず、一連のベクトル化処理を終了させる。
【００３８】
処理時間計測判定手段は、それまでの処理時間を測定し、これが既定の時間を超えたか否かを判定する。既定の時間を超えた場合には、画像処理装置は、一連のベクトル化処理を終了させる。そうではない場合、即ち、既定の時間を超えない間は、上記次に近似精度の向上を図るべき区間に対して区間分割、分割区間の関数近似以降の処理を繰り返すものである。
【００３９】
（第１の実施形態）
図１は、本実施形態を実施する画像処理装置を実現する機器構成例を示す図である。同図において、符号５１８は、系のバスを表している。
【００４０】
符合１は画像を入力するスキャナである。符号２は画像メモリであり、符号３は画像入出力Ｉ／Ｏである。２値画像獲得手段としての２値画像獲得部７は、スキャナ１、画像メモリ２、および画像入出力Ｉ／Ｏ３を備えている。画像メモリ２は画像入出力Ｉ／Ｏ３を介して、スキャナ１で読み取られた２値化前の多値画像（原稿画像）を保持する。また、画像メモリ２は、上記２値画像を予め定められる閾値を用いて２値化する等の公知の２値化法に基づき２値化された後の２値画像データを保持する。
【００４１】
粗輪郭抽出手段としての粗輪郭抽出部５は、後述するＣＰＵ５１９、ＲＯＭ６と共に、２値画像獲得部７により得られた２値画像から、これに含まれる図形の境界を関数近似処理前のベクトル（粗輪郭、もしくは、粗輪郭ベクトルとも称する）として抽出する。符号５０は、入力画像ラスター走査部であり、画像入出力Ｉ／Ｏ３を介して信号線５００より２値画像獲得部７にて得られた２値画像データを順次入力する。符号５１３と符号５１４とは、３×３の９画素で構成される走査窓の各画素の状態を入力する入力ポートである。
【００４２】
符号４は、ネットワーク等を経由して、システムの外部と通信する通信Ｉ／Ｆである。符号５１９はCPUである。符号５２０はRAMで、ワーキングメモリである。符号６はROMで、後に説明する手順に沿ってＣＰＵ５１９で実行されるプログラムや予め定められるパラメータやデータ等を格納している。これらのＣＰＵ５１９やＲＡＭ５２０、ＲＯＭ６により、関数近似区間設定（アンカーポイント設定）手段や関数近似処理（コントロールポイント算出）手段が実現される。また、区間内近似精度算出（区間内誤差分値、区間内最大誤差値）手段、分割対象区間同定手段、区間分割手段、データ量判定手段、処理時間計測判定手段等も実現される。符号５２１はハードディスク装置５２２とのI/O（入出力回路）である。符号８は、タイマ回路であり、ＣＰＵ５１９によりコントロールされることで処理時間計測判定手段を構成する。ＣＰＵ５１９は、２値画像獲得部７、粗輪郭抽出部５、タイマー回路８といった、図１に示した画像処理装置の各構成を統括的に制御する。
【００４３】
以下、図３に示すフローチャートに基づき、本実施形態を実施する画像処理装置の動作を説明する。  
同図において、処理を開始すると、画像処理装置は以下のように動作する。ステップＳ１０では、２値画像獲得部７は、操作者から図示せぬ入力操作部（例えば、キーボードや各種ボタン）を介して一連の動作開始の指示を受けて、上述のスキャナ１、画像入出力Ｉ／Ｏ３、公知の２値化法に基づき画像メモリ２上に２値画像を生成する。すなわち、上記動作開始の指示に応じて、スキャナ１は、原稿を読み取ることによって、原稿画像を取得する。次いで、２値画像獲得部７は、スキャナ１から原稿画像を取得し、該原稿画像に対して２値化処理を行って、ベクトル化対象となる２値画像を獲得し、画像メモリ２に保存する。
【００４４】
次にステップＳ２０では、上述の粗輪郭抽出部５を起動し、ステップ１０にて得られた２値画像に基づいて粗輪郭ベクトルデータを生成してＲＡＭ５２０上に格納する。以下、主として、図４〜図７を用いて粗輪郭抽出部５での動作と処理内容を説明する。
【００４５】
本実施形態では、図５に示すように、２値画像における注目画素101と、その近傍の８個の画素の状態を見て処理を進めるもので、注目画素をラスタ走査し、１画素毎にずらしながら画像全体の処理を逐次行なってゆく。図５において、×は注目画素101を表しており、“0”及び“2”で示された位置は、主走査方向に対し注目画素101と同じ位置にあり、副走査方向のそれぞれ１ラスタ前の画素（０）及び１ラスタ先の画素（２）を示す。“1”及び“3”で示された位置は、注目画素101と同一のラスタ上にあり、それぞれ１画素前の画素（３）及び１画素先の画素（１）を示している。更に、“A”及び“B”は、主走査方向に１画素先の位置にあり、それぞれ１ラスタ前及び１ラスタ先の位置にある画素を示す。“C”及び“D”は、主走査方向の１画素前の位置にある画素で、それぞれ１ラスタ先及び１ラスタ前の位置にある画素を示す。
【００４６】
図４は、図１における粗輪郭抽出部５の構成例をより詳細に示している。同図において、図１と同様に符号５０は入力画像ラスター走査部であり、画像入出力Ｉ／Ｏ３を介して信号線５００より２値画像データを順次入力する。
【００４７】
符号501は、信号線500により、２値画像獲得部７から入力される画像データ（２値画像）をやりとりするための入力制御（インターフェース）部であり、この信号線500よりラスタ走査形式で順次２値画像データが入力されてくる。符号502はラッチで、入力制御回路501より入力された画像データを、図示しない画素同期クロックに同期して１画素づつ順次更新しながら保持する。次の画素同期クロックにて、ラッチ502は次の画素データを入力制御回路501より入力する。この時、既に保持していた画素データは、その画素同期クロックに同期してラッチ503にラッチされて、保持される。同様にラッチ503に保持されていた画素データは、次の画素同期クロックにて、ラッチ504に保持される。
【００４８】
符号505及び506はそれぞれ１ラスタ分の画素データを保持するFIFO（ファーストイン・ファーストアウト・メモリ）である。FIFO505は、ラッチ504の出力を順次、画素同期クロックに同期して取り込み、１ラスタ前のデータをラッチ507へ出力する。同様に、FIFO506も、ラッチ509の出力を取り込み、ラッチ510に１ラスタ前の画素データを出力する。ラッチ507,508,509及びラッチ510,511,512は共に上記ラッチ502,503,504と全く同様に動作する。
【００４９】
このようにして、ラッチ502,503,504,507,508,509,510,511及び512に記憶された９個の画素は、図５に示した９（３×３）画素よりなる領域の画素データを記憶していることになる。即ち、これらラッチのデータは、ラッチ502から512に向って順にそれぞれ図５の“B”,“2”,“C”,“1”,“×”,“3”,“A”,“0”,“D”に対応している。
【００５０】
符号５１３と５１４は、３×３の９画素で構成される走査窓の各画素の状態を入力する入力ポートである。入力ポート513,514は共にCPU519の入力ポートで、入力ポート513は、ラッチ510,502,504,512のデータを、即ち、それぞれ図５における“A”,“B”,“C”,“D”の位置のデータをCPU519に入力する。同様に、入力ポート514はラッチ511,507,503,509,508のデータ、即ち、“0”,“1”,“2”,“3”,“×”の位置のデータとして入力する。
【００５１】
符号515は、主走査方向の画素位置を示す主走査カウンタであり、図示しない副走査同期信号によりリセットされ、画素同期信号によりカウントアツプする。符号516は、副走査方向の画素位置を示す副走査カウンタで、図示しないページ同期信号によりリセットされ、副走査同期信号によりカウントアツプされる。符号517は入出力制御用の入出力ポートであり、入出力制御回路501に対し、画素データ入力の実行及び保留を指示する信号、及び入出力制御回路501よりCPU519への画素データ更新を知らせる信号等を保持する。符号521は、ハードディスク522の入出力制御装置である。入出力制御ポート517、主走査カウンタ515、副走査カウンタ516、入力ポート513,514、メモリ520、ディスクI/O521はバス518を介してCPU519に接続されている。
【００５２】
こうして、CPU519は入出力制御ポート517を介して、画素データの更新を行い、主走査カウンタ515及び副走査カウンタ516を介して、注目画素の画素位置（i,j）を知ることができる。また、入力ポート513及び514を介して、注目画素及びその近傍の８方向の画素の状態を知ることができる。
【００５３】
このようにして注目画素の処理が終了すると、CPU519は入出力制御ポート517を介して９個のラッチに記憶される画素データの更新を指示し、同時に画素データの更新完了の信号をリセットする。入出力制御回路501は、この更新の指示を受けると、画素データの更新指示の信号をクリアするとともに、後段のラッチにラッチされる画素データを更新し、この更新が終了すると入出力制御ポート517に、更新完了の信号を出力する。
【００５４】
CPU519は、更新指示の出力後、入出力制御ポート517より更新完了の信号が入力されるのを監視している。この更新完了の信号が入力されると、新たに９個のラッチに記憶された画素データに関する処理を実行し、以下同様にこれを繰り返すものである。また、入力制御回路501は、画像領域の最終画素を注目画素として処理し終った際に、入出力制御ポート517に終了信号を出力する。
【００５５】
次に注目画素及びその近傍の８画素の状態に応じた、それぞれの場合の処理を説明する。  
ＣＰＵ519は、注目画素が白画素である場合は、その処理を終了してラスタ走査を１画素分進め、注目画素位置を更新する。
【００５６】
これら輪郭ベクトルの始点・終点位置は、主走査方向及び副走査方向共に、画素と画素の中間の位置にあるものとする。また、主走査方向及び副走査方向共に、画素のある位置は正整数で示され、画素位置を２次元の座標で表現をする。但し、ここでは小数の表現を避けるために便宜上、以降の画素位置を偶数のみで表現することにし、始点、終点の位置を奇数の整数で表現することにする。即ち、ｍ画素×n画素の画像は、2m×2nの正の偶数（整数）の座標表現で表わすものとする。このように、主走査方向をｘ座標、副走査方向をｙ座標とした２次元座標であらわすとき、これ以降２値画像は、以下のようになる。すなわち、それぞれがｍ画素よりなるｎラスタで構成されるm×n画素（m,nは正の整数）でなるものとし、第ｊ番目のラスタの第ｉ番目の画素位置を（2i,2j）（i,jは正の整数で、ｉ≦m,j≦ｎ）で表現するものとする。また、主走査方向（ｘ座標）は左から右に向かう方向が正の方向であり、副走査方向（ｙ座標）は上から下に向かう向きが正の方向である。
【００５７】
以下、粗輪郭抽出処理に関し、粗輪郭抽出部５、及び、ＲＯＭ６に保持されるプログラムによるＣＰＵ５１９の一連の動作を図６のフローチャートに沿ってさらに説明を加える。本実施形態における粗輪郭抽出部５は、基本的には特許文献１の開示する粗輪郭抽出動作で構成することができる。
【００５８】
図６は、本実施形態の画像処理装置のCPU519による輪郭抽出処理の全体の流れを示すフローチヤートである。これは、特許文献１の第２２図に開示されるフローチャートでる。
【００５９】
まずステップS1にて、２値画像データからベクトル列を抽出する。そして、各ベクトルの始点の座標及びこのベクトルに流入してくる（このベクトルの始点の座標が終点となっている）ベクトル、流出してゆく（このベクトルの終点の座標が始点となっている）ベクトルを出力する。この出力は、特許文献１に準じて（特許文献１の図23及び図24に示すテーブルを踏襲して）行われる。
【００６０】
次にステップS2に進み、特許文献１の図23及び図24に示すテーブルに準ずる不図示のテーブルから流入及び流出ベクトルの項目番号を辿る。これにより、図７（特許文献１の図25に準ずる）に示すような画像中の総輪郭線ループ数、各輪郭線ループ毎の輪郭線ループ上の総点数、輪郭線ループ上の各点のｘ座標、ｙ座標を記憶したテーブルを作成する。次にステップS3に進み、ディスクI/O521を介して、このテーブル情報ファイル形式でハードディスク522に記憶して、一連の動作を終了する。
【００６１】
かくして、図３のステップＳ２０の粗輪郭抽出を終えると、ＣＰＵ519は、生成された粗輪郭ベクトルデータをハードディスク522に格納する。粗輪郭ベクトルデータは、例えば、図７に示したような形式として表現でき、本実施形態では、この形式で出力されるものとする。なお、このときハードディスク522に格納された粗輪郭ベクトルデータは、関数近似処理前のベクトルである。
【００６２】
このようにして、画像処理装置は、ステップＳ１０にて取得された２値画像に基づいて、該２値画像に含まれる図形の境界を、関数近似処理前のベクトルとして抽出することができる。
【００６３】
ステップＳ３０では、ＣＰＵ519は、関数近似区間設定手段として機能し、ハードディスク522に保持される粗輪郭ベクトルデータに対して該粗輪郭ベクトルデータをベジェ関数近似するためのアンカーポイントを設定する。ＣＰＵ519は、該アンカーポイントの設定により関数近似区間を設定することができる。
【００６４】
これは、例えば上述した特許文献４に開示される方法で求めることができる。即ち、まず、粗輪郭ベクトルデータと称して、２値のラスター画像のデータより抽出された、水平ベクトル、垂直ベクトルが交互に並ぶ構成となる粗輪郭ベクトルデータから一輪郭線ループ分の粗輪郭ベクトルデータを入力する。上述の接線線分とするベクトルの抽出の条件[1]〜［3］等の規則に基づき粗輪郭上の線分より接線線分を抽出する。抽出された接線線分の端２つに対しそれぞれアンカーポイントを抽出する。接線線分上の一方の端に対しては、注目する接線線分であるベクトルに隣接するベクトルが接線線分であれば、この隣接する側の端点をアンカーポイントとする。隣接する線分が接線線分で無い場合には、さらにその隣、即ち、着目する接線線分のベクトルV2（長さを|V2|と表す）の２本前の線分のベクトルV1（長さを|V1|と表す）から、V2 ベクトル上端点より a|V1| 離れた点をアンカーポイントとする。但し、ひとつの接線成分のそれぞれの端のアンカーポイントが一致した場合には一つのアンカーポイントのみ抽出する。かくして、一輪郭線ループ分の粗輪郭データにおける全てのアンカーポイントを抽出すると、ステップＳ４０へ進む。
【００６５】
ステップＳ４０では、ＣＰＵ519は、粗輪郭ベクトルデータ中の未処理の輪郭線ループに処理対象を移す。  
ステップＳ５０では、ＣＰＵ519は、ステップＳ４０で未処理の輪郭線ループが見つからなかった場合にステップＳ６０に処理を進ませる。そうではない場合には、ステップＳ３０に処理を戻し、ステップＳ４０で見つかった未処理の輪郭線ループに対して、上記ステップＳ３０の処理を行なわせる。
【００６６】
かくして、ステップＳ３０からステップＳ５０までの処理は、アンカーポイント設定の処理が全ての輪郭線ループに対して完了するまで繰り返され、完了するとステップＳ６０に進むこととなる。尚、ステップＳ３０からステップＳ５０までの処理で得られたアンカーポイントが設定された粗輪郭ベクトルデータ（以降、“アンカーポイント設定済粗輪郭”と称する）は、例えば、図１０のような形式でＲＡＭ５２０上に保持されるものとする。  図１０において、画像中の総輪郭線ループ数ａがデータ領域の先頭に格納され、その直後に第１番目の輪郭線ループ（第１輪郭線ループ）に対するデータが格納されている。第１番目の輪郭線ループのデータの先頭には、第１番目の輪郭線ループ中の関数近似対象区間（単に、関数近似区間とも言う）、即ち、ループ上で相隣り合う２つのアンカーポイントに挟まれる区間の総数α1が格納されている。その次には、第１番目の輪郭線ループの第１番目の区間中にある輪郭点の総数β11が格納されている。このβ11については、後に説明を加える。その次に、第１番目の輪郭線ループ中の第１番目の区間（第１区間）の第１番目の輪郭点の座標値が格納されている。この第１番目の輪郭点は、当該関数近似区間を定める２つのアンカーポイントのうちの最初のアンカーポイント（図８でのｐ１に相当する）である。このデータ以降には、当該関数近似区間内の輪郭点の座標値がループ上での並び順にあわせて順じ格納されている。
【００６７】
尚、当該関数近似区間を定めるもうひとつのアンカーポイント（図８でのｐＮに相当する）は、実は、同じ輪郭線ループ状の次に繋がる関数近似対象区間の最初のアンカーポイントでもある。従って、当該関数近似区間内（即ち、ここでは、第１区間内）の輪郭点のデータとしては座標値を格納せずに次に繋がる第２区間内の最初のアンカーポイントとして座標値を格納する形式でデータを生成している。つまり、第１区間内の輪郭点データとしては、この関数近似区間を定める最初のアンカーポイントから同関数近似区間を定める最後のアンカーポイントの直前の輪郭点までの座標値を格納している。図１０の例では、第１番目の輪郭線ループの第１の関数近似区間には、最初のアンカーポイントから、この区間を定める最後のアンカーポイトの直前の輪郭点までで、β11個の輪郭点があることを表している。そしてこれが、上述の第１番目の輪郭線ループの第１番目の区間中にある輪郭点の総数の意味するところである。
【００６８】
さて、その次には、この時点ではまだ求められてはいない、この関数近似区間でのアンカーポイント間を結ぶ線分より最も距離の離れている同区間中の点（図８の“ｐｆ”）を特定する情報を格納する領域がある。該特定する情報は、ここでは第１区間内の２番目の点からβ11番目の点のいずれかを表す番号である。これに続いて、やはりこの時点ではまだ求められてはいない、この関数近似区間に対する２つのコントロールポイントＣ１、および、Ｃ２の座標値を格納する領域がある。ちなみに、これらｐｆ、Ｃ１、Ｃ２については、後のステップＳ６０において求められる。
【００６９】
さらに、その次に、同輪郭線ループ中の次の関数近似区間（この場合、第１輪郭線ループの第２関数近似区間）のデータ領域の先頭位置を与えるポインタの値（アドレス情報）をもつ。以降、第１近似区間に対するデータ列と全く同様に、第１輪郭線ループの第２関数近似区間のデータ、第３関数近似区間のデータ、…、第α1関数近似区間のデータの順に並び、第１輪郭線ループに関するデータを形成するものである。この際、第１輪郭線ループのデータ域の最後に第２輪郭線ループに関するデータ域の先頭位置を与えるポインタの値（アドレス情報）を格納する領域をもつ。この領域は、この輪郭線ループが当該アンカーポイント設定済粗輪郭の最後の輪郭線ループである場合には不要である。以降、第２輪郭線ループに関するデータ領域が、上述した第１輪郭線領域のデータ領域と全く同様に続く。さらに、当該アンカーポイント設定済粗輪郭に存在する最後の輪郭線ループの分の領域まで続いて、当該アンカーポイント設定済粗輪郭データが構成されている。
【００７０】
尚、ステップＳ５０の処理が全ての輪郭線ループに対して完了してステップＳ６０に進む際には、上述の図７に示された粗輪郭ベクトルデータは以降の処理では不要なため、この時点でハードディスク５２２から削除することも可能である。
【００７１】
さて、ステップＳ６０では、ＣＰＵ519は、関数近似処理（コントロールポイント算出）手段として機能し、ステップＳ３０にて設定された関数近似区間毎に高次の関数（ベジェ曲線等の曲線関数）による関数近似を行い、コントロールポイントを算出する。すなわち、ＣＰＵ519は、ＲＡＭ５２０上に上述の図１０の形式で保持されている、ステップＳ３０からステップＳ５０までの処理で得られたアンカーポイント設定済粗輪郭の一輪郭線ループ分を入力する。次いで、ループ上で相隣り合う２つのアンカーポイントに挟まれる区間（以降、“関数近似対象区間”と称する）に対してコントロールポイントを求める。そして、当該区間を2次もしくは３次ベジェ曲線、及び直線をあてはめ、当該輪郭線ループ上の全ての関数近似対象区間に対して、ベジェ曲線近似を行い、3次もしくは2次のベジェ曲線により置きかえていく。
【００７２】
これは、例えば上述した特許文献４に開示される方法で求めることができる。即ち、まず、一ループ分のアンカーポイント設定済粗輪郭データを入力し、当該ループ上に繋がる順に関数近似対象区間を、順次着目する関数近似対象区間とし、かくして定めた関数近似対象区間上の輪郭点列であるＮ個の点をそれぞれｐ１，ｐ２，…，ｐＮとする。このとき、これら点列の始点ｐ１、終点ｐＮはアンカーポイントである。先に述べた図８は、このときの１例を示している。同図において、黒丸で示されたのが、各輪郭点を表している。
【００７３】
ここで、アンカーポイントｐ１、ｐＮを結ぶ線分ｐ１ｐＮより最も距離の離れている曲線上の点ｐｆを求める。そして、このときの、点ｐｆと線分ｐ１ｐＮとの距離をＬとする。関数近似処理を簡易に行うため、求めるコントロールポイントをＣ１，Ｃ２としたとき、この２つのコントロールポイントを結ぶ線分Ｃ１Ｃ２が線分ｐ１ｐＮに対して平行となるように近似するものとする。そして、点Ｃ１、Ｃ２より線分ｐ１ｐＮへの距離が（４／３）×Ｌとなるように、即ち、互いに平行な線分Ｃ１Ｃ２と線分ｐ１ｐＮ間の距離が（４／３）×Ｌとなるように、Ｃ１、Ｃ２を求める。
【００７４】
ｐｆの座標値が（ｐfx，ｐfy）であった場合、ｐ１、ｐＮの各座標値（ｐ1x，ｐ1y）、（ｐNx，ｐNy）とｐ１における接線ベクトルｐ１Ｃ１（ｐcx，ｐcy）を用いると、Ｃ１の座標値（Ｃ1x，Ｃ1y）は、  
Ｃ1x＝Ｋ×ｐfx＋ｐ1x  
Ｃ1y＝Ｋ×ｐfy＋ｐ1y  
Ｋ＝（３ｐ1x−４ｐfx）（ｐNy−ｐ1y）＋（ｐNx−ｐ1x）（４ｐfy−３ｐ1y）  
＋ｐ1x（ｐNy−ｐ1y）−ｐ1y（ｐNx−ｐ1x）  
/（３（ｐNy−ｐ1y）ｐcx＋３（ｐNx−ｐ1x）ｐcy）  
となり、ｐｆの座標値より一意に決定することができる。また、Ｃ２についても、Ｃ１と同様に求めることができる。
【００７５】
このとき、アンカーポイントｐ１、ｐＮと、これらの間に定められるコントロールポイントＣ１、Ｃ２の４点で定まる３次ベジェ曲線が最も線分ｐ１ｐＮより離れる点までの線分ｐ１ｐＮからの距離は、点ｐｆまでの距離Ｌと等しくなる。
【００７６】
尚、ここでアンカーポイントｐ１、ｐＮにおける接線ベクトルは、特許文献４に開示されるように、以下のように求められる。すなわち、区分曲線への分割時に、アンカーポイントを定める際の接線線分とその付近の複数の線分の組み合わせにより、パターンマッチング的に方向ベクトルを抽出して、これをもってアンカーポイントにおける接線ベクトルとする。
【００７７】
ステップＳ６０で求めた、当該関数近似対象区間（関数近似区間）でのアンカーポイント間を結ぶ線分より最も距離の離れている同区間中の点（図８の“ｐｆ”）を特定する情報は、上述した図１０に示した該当領域に格納される。同様に、２つのコントロールポイントＣ１、および、Ｃ２の座標値についても、上述した図１０に示したそれぞれの該当領域に格納されるものである。
【００７８】
かくして、ステップＳ６０にてコントロールポイント設定（関数近似処理）を終えると、ステップＳ７０に進む。
【００７９】
ステップＳ７０では、ＣＰＵ519は、区間内近似精度算出手段として機能し、ステップＳ６０で関数近似処理を終えた区間の区間内の近似誤差（近似精度）を算出する。図９は、この様子を説明する図である。同図において、アンカーポイントｐ１、ｐＮとこれらの間に定められるコントロールポイントＣ１、Ｃ２、即ち、ｐ１、Ｃ１、Ｃ２、ｐＮの４点で定まる３次Bezier（ベジェ）曲線を破線Ｌdで示している。ここで、ｐ１、ｐＮの各座標値をそれぞれ（ｐ1x，ｐ1y）、（ｐNx，ｐNy）、Ｃ１、Ｃ２の座標値をそれぞれ（Ｃ1x，Ｃ1y）、（Ｃ2x，Ｃ2y）とする。このとき、Ｌdの軌跡は、軌跡Ｌd上の任意の点Ｐld（Ｐldx,Ｐldy）を媒介変数ｔ（0≦ｔ≦1）を用いて、  
Ｐldx =ｐ1x (1 - t)3 + 3 Ｃ1x (1 - t)2 t + 3 Ｃ2x (1 - t) t2 +ｐNx t3 ・・・(1)  
Ｐldy =ｐ1y (1 - t)3 + 3 Ｃ1y (1 - t)2 t + 3 Ｃ2y (1 - t) t2 +ｐNy t3 ・・・(2)  
のように表現することができる。
【００８０】
このときステップＳ６０で求めた、アンカーポイントｐ１、ｐＮを結ぶ線分ｐ１ｐＮより最も距離の離れている曲線上の点ｐｆ（ｐfx，ｐfy）との関係に着目すると、次のようになる。すなわち、２つのコントロールポイントを結ぶ線分Ｃ１Ｃ２が線分ｐ１ｐＮに対して平行となるように、かつ、互いに平行な線分Ｃ１Ｃ２と線分ｐ１ｐＮ間の距離が（４／３）×Ｌとなるように、Ｃ１、Ｃ２を求めている。よって、t = 1 / 2 のとき、線分ｐ１ｐＮより最も離れる距離（距離Ｌ）となる点Ｐd（Ｐdx,Ｐdy）となる。図９において、ＤdとＤfとは、それぞれ、点Ｐdと点ｐｆからの線分ｐ１ｐＮまでの距離を表しており、
Ｄd = Ｄf = Ｌ  
である。
【００８１】
しかしながら、接線方向（接線ベクトルｐ１Ｃ１や接線ベクトル、ｐ２Ｃ２）のとり方等により、必ずしも、点Ｐd と 点Ｐf が完全に一致するとは限らず、誤差が発生する。図９では、この誤差をΔx と表している。即ち、  
（Δx）2 =（Ｐdx - ｐfx）2 + （Ｐdy - ｐfy）2 ・・・(3)  
Δx =ＳＱＲＴ（（Ｐdx - ｐfx）2 + （Ｐdy - ｐfy）2 ）・・・(4)  
（但し、ＳＱＲＴ（ｋ）は、ｋの平方根の意）  
である。  
ここで、上述したように、Ｐdx、Ｐdy は、それぞれ、(1)式、(2)式に t = 1 / 2 を代入して求めることが可能である。
【００８２】
計算を単純化するため、点ｐ１が座標系の原点、即ち、(0,0)であり、点ｐＮも x 軸上にあるものとし、その座標値を(ｐNx, 0)、とする。さらに、点Ｃ１を( Ｃ1x, (4 / 3) Ｌ)、点Ｃ１を( Ｃ2x, (4 / 3) Ｌ)として、点Ｐd（Ｐdx,Ｐdy）を、上記の(1)式、(2)式より求めてみると、  
Ｐdx = (3 /8) (Ｃ1x + Ｃ2x) + (1 /8) ｐNx  
Ｐdy = (3 /8) (Ｃ1y + Ｃ2y) = (3 /8) ((4 / 3) Ｌ + (4 / 3) Ｌ) = Ｌ  
となり、確かに、線分ｐ１ｐＮより距離（距離Ｌ）となっていることがわかる。
【００８３】
尚、一般的には、(1)式、(2)式に t = 1 / 2 を代入すると、  
Ｐdx = (1 /8)ｐ1x + (3 /8) (Ｃ1x + Ｃ2x) +(1 /8)ｐNx  ・・・(5)  
Ｐdy = (1 /8)ｐ1y + (3 /8) (Ｃ1y + Ｃ2y) +(1 /8)ｐNy  ・・・(6)  
となる。
【００８４】
さて、ステップＳ７０では、ＣＰＵ519は、ステップＳ６０にて求められた４点、ｐ１、Ｃ１、Ｃ２、ｐＮの座標値から(5)式、(6)式より点Ｐdの座標値（Ｐdx,Ｐdy）を求める。さらに、ＣＰＵ519は、ステップＳ６０にて求められた点ｐｆの座標値（ｐfx，ｐfy）とから、(3)式により（Δx）2 を求める。この（Δx）2 をもって、ステップＳ７０で求める区間内誤差値とする。この他にもΔxをもって、区間内誤差値としてもよい。このようにして、画像処理装置は、ステップＳ６０にて３次ベジェ曲線にて関数近似された関数近似区間毎の区間内誤差値（近似精度）を算出することができる。
【００８５】
尚、ステップＳ７０で算出された区間内誤差値は、後述するように、基本的には、ステップＳ７０で処理した順に、ＲＡＭ５２０上に保持されていくものとする。  
かくして、ステップＳ７０にて区間内誤差値の算出を終えると、ステップＳ８０に進む。
【００８６】
ステップＳ８０では、ＣＰＵ519は、処理中である一輪郭線ループ分のアンカーポイント設定済粗輪郭中における未処理の関数近似対象区間に処理対象を移す。もし、当該、一輪郭線ループ分のアンカーポイント設定済粗輪郭中に未処理の関数近似対象区間が存在しない場合には、未処理のアンカーポイント設定済粗輪郭ループ中における未処理の関数近似対象区間に処理対象を移す。
【００８７】
ステップＳ９０では、ＣＰＵ519は、ステップＳ８０でアンカーポイント設定済粗輪郭中に未処理の輪郭線ループが見つからなかった場合にステップＳ１００に処理を進ませる。そうではない場合には、ステップＳ６０に処理を戻し、ステップＳ８０で見つかった未処理の輪郭線ループに対して、上記ステップＳ６０の処理を行なわせる。
【００８８】
かくして、ステップＳ６０からステップＳ９０までの処理は、区間内誤差値の算出処理がアンカーポイント設定済粗輪郭中の全ての輪郭線ループに対して完了するまで繰り返され、完了するとステップＳ１００に進むこととなる。尚、区間内誤差値の算出処理がなされた結果としてのデータは、例えば、図１２のような形式でＲＡＭ５２０上に保持されるものとする。すなわち、図１２に示すように、ステップＳ７０で処理した順に従い、各輪郭線ループ毎に、当該輪郭線ループ状の区間順に並べて格納する等により、各区間とその区間の区間内誤差値の対応がつく形で、保持されるものとする。
【００８９】
図１２では、画像中の総輪郭線ループ数ａに続いて、第１番目の輪郭線ループのデータ域から順に第ａ番目の輪郭線ループのデータ域までが順次並んでいる。第１番目の輪郭線ループのデータ域には、第１番目の輪郭線ループ中の総近似区間数α1が格納されている。続いて同輪郭線ループ中の第１番目の関数近似区間の区間内誤差値と次の（即ち、第２番目の）関数近似区間の誤差値が格納される領域へのポインタ（アドレス情報）が格納されている。これに続き、第２番目の関数近似区間の区間内誤差値と、次の（即ち、第３番目の）関数近似区間の誤差値が格納される領域へのポインタ（アドレス情報）とが順番に格納されている。
【００９０】
以下同様に、この輪郭線ループ中の最後の関数近似区間の区間内誤差値が格納され、次の（即ち、第２番目の）輪郭線ループのデータが格納される領域へのポインタ（アドレス情報）が並んでいて、ここまでで、第１番目の輪郭線ループのデータ域が構成されている。以降、同様に、第ａ番目の輪郭線ループのデータ域が構成されている。但し、最後の輪郭線ループの最後の関数近似区間の区間内誤差値が格納されている領域に続くポインタ（アドレス情報）領域には、便宜上、第１番目の輪郭線ループのデータが格納される領域へのポインタ（アドレス情報）を格納している。
【００９１】
ステップＳ１００では、ＣＰＵ519は、ステップＳ７０で求めた区間内誤差値をそれぞれの区間に対するデータのポインタ情報を用いて順にサーチしながら、それらの中で、最大の値をもつものを求め、どの区間の区間内誤差が最大かを同定する。すなわち、ＣＰＵ519は、分割対象区間同定手段として機能し、ステップＳ７０にて得られた関数近似区間毎の区間内誤差値から、最大の区間内誤差値（区間内最大誤差値）を有する関数近似区間（最大誤差区間）を同定する。ここで、区間内誤差値が最大であるということは、該区間内誤差値を低減することが望ましいことを意味する。そこで、本ステップにより、区間内最大誤差値に対応する関数近似区間を同定することにより、最も誤差低減が望まれる関数近似区間を抽出することができる。
【００９２】
さて、上記区間内誤差値は、関数近似区間内の誤差をパラメータ化したものであるので近似精度に対応している。そして、区間内誤差値を低減するということは、近似精度を向上することと同義となる。従って、本実施形態の画像処理装置は、区間内最大誤差値に対応する関数近似区間である最大誤差区間を同定することにより、近似精度の向上を図るべき関数近似区間を同定することができる。
【００９３】
なお、最大の誤差値をもつ区間が複数存在する場合には、ＣＰＵ519は、それらの中でサーチ順の最初の区間を最大誤差区間とする。そして、ステップＳ１１０へ進む。
【００９４】
ステップＳ１１０では、ＣＰＵ519は、処理時間計測判定手段として機能し、タイマー回路８にアクセスして、処理時間にまだ余裕があるか否かを判断し、まだ余裕がある場合にはステップＳ１２０に進み、そうではない場合には、ステップＳ１７０に進む。
【００９５】
尚、このタイマ回路８は、詳述は避けるが、公知のカウンタ回路や時計等の経過時間を測定可能なもので構成することができる。例えば、図３の一連の処理の開始時に初期化され、予め定められた処理時間（規定の処理時間）に相当する値を初期化時にセットされると、不図示の一定周期を刻むクロックで１ずつ減算を開始し、0になった時点で減算動作を停止するカウンタ回路を用いれば良い。この構成では、前述のステップＳ１１０で、ＣＰＵ519は、このタイマ回路のカウントが０になっているか否かを判断することで、現在が規定の処理時間（予め定められた処理時間）内であるか否かの判定を行なうことができる。例えば、このカウンタの初期値は、予め定められた処理時間が５秒であり、かつ、カウンタの減算クロックがこのカウンタに１秒に１２０００回入るものであるとすると、上述の初期化時に６００００の値をセットすればよいわけである。
【００９６】
なお、上記規定の処理時間（予め定められた処理時間）は、所望に応じてユーザが設定できるようにしても良い。この場合は、ユーザが入力操作部（不図示）を操作して所望の時間を入力し、該入力を受け付けたＣＰＵ519が、該入力された時間に応じてカウンタの初期値を設定するようにすれば良い。
【００９７】
このように、本ステップにおいてＣＰＵ519は、タイマー回路８による経時測定結果に基づいて、処理を開始してからの経過時間（処理時間）が規定の処理時間を越えたか否かを判断する。そして、処理時間が規定の処理時間を越えた場合は、一連の近似精度向上処理（後述するステップＳ１４０〜Ｓ１６０）を行わず、一連のベクトル化処理を終了する。一方、処理時間が規定の処理時間を越えていない場合は、一連の近似精度向上処理を行う。従って、規定の処理時間内であれば、より精度を向上させるための一連の近似精度向上処理を行うことができるので、処理時間の点で実用上妥当とされる制限内で、近似精度をより向上することができる。
【００９８】
次にステップＳ１２０では、ステップＳ１００で求められた区間内最大誤差値が、予め定める閾値（例えば、４）を越える値であるか否かを判断し、超える場合にはステップＳ１３０に進み、そうではない場合にはステップＳ１７０に進む。上述のように、区間内最大誤差値に対応する関数近似区間は、複数の関数近似区間の中で近似精度の向上を図るべき区間であるので、上記予め定める閾値は、規定の近似精度の許容値となる。
【００９９】
本実施形態では、区間内最大誤差値が予め定める閾値（近似精度の許容値）を超える場合にのみ、一連の近似精度向上処理を行うので、ユーザが許容している近似精度の範囲内であれば、これ以上の近似精度向上処理を行う必要が無くなる。よって、近似精度の点から実用上妥当とされる範囲内で出力することができる。また、規定の処理時間内であっても、最低限求められる近似精度が達成された時点で出力処理へと切換えることができるので、ユーザが許容する近似精度を保ちつつ、処理時間の短縮を図ることができる。
【０１００】
ステップＳ１３０では、ＣＰＵ519は、データ量判定手段として機能し、既に生成した図１０や図１２に示したアンカーポイント設定済粗輪郭データや各関数近似区間の誤差値の情報のデータ量が既に、既定のデータ量に達しているか否かを判定する。この規定のデータ量は、許容値となるデータ量であり、例えば、５ＭＢと設定されている。ＣＰＵ519は、上記許容値にまだ達していない場合にはステップＳ１４０に進む。そうではない場合、即ち、既に、既定の許容値となるデータ量（例えば、５ＭＢ）に達している場合には、ＣＰＵ519は、ステップＳ１７０に進む。
【０１０１】
ここで、図１０に示したアンカーポイント設定済粗輪郭データのデータ量（データ容量）Ｄ1は、以下のようになる。ここで、簡単のために、図１０中の全ての要素をそれぞれ４バイトで構成するものとする。このような要素は、画像中の総輪郭線ループ数、各輪郭ループ中の総区間数、各区間内の各点の座標値（x座標とｙ座標の組み合わせ）、Ｐｆとなる点の番号を含む。また、上記要素は、コントロールポイントの座標値（x座標とｙ座標の組み合わせ）、次の区間のデータ領域へのポインタ（アドレス情報）等を含む。すなわち、データ量Ｄ1は、  
Ｄ1＝４×（ＳＵＭ（β1 1 ，β1 2 ，・・・，β 1 α1）＋ＳＵＭ（β2 1 ，β2 2 ，・・・，β 2 α2）＋・・＋ＳＵＭ（βa 1 ，βa 2 ，・・・，β a αa）＋４×ＳＵＭ（α1，α2，・・・，αa）＋ａ＋１）  
バイトの容量となる。
【０１０２】
また、図１２に示した各関数近似区間の誤差値の情報のデータ量Ｄ2は、以下のようになる。ここで、Ｄ1と同様に、簡単のために、図１２中の全ての要素をそれぞれ４バイトで構成するものとする。このような要素は、画像中の総輪郭線ループ数、各輪郭ループ中の総区間数、各区間の区間内誤差値、次の区間のデータ領域へのポインタ（アドレス情報）等を含む。すなわち、データ量Ｄ2は、  
Ｄ2＝４×（２×ＳＵＭ（α1，α2，・・・，αa）＋ａ＋１）  
バイトの容量となる。
【０１０３】
ただし、ＳＵＭ（  ，  ，・・・，  ）は、（  ）内の全要素の総和を意味する。
【０１０４】
即ち、ステップＳ１３０では、ＣＰＵ519は、  
Ｄ＝Ｄ1＋Ｄ2＝  
＝４×（ＳＵＭ（β1 1 ，β1 2 ，・・・，β 1 α1）＋ＳＵＭ（β2 1 ，β2 2 ，・・・，β 2 α2）＋・・・＋ＳＵＭ（βa 1 ，βa 2 ，・・・，β a αa）＋６×ＳＵＭ（α1，α2，・・・，αa）＋２×ａ＋２）  
が、５Ｍ、即ち、５×２20＝５２４２８８０未満か否かを判定する。ＣＰＵ519は、生成されたデータ量Ｄが、規定のデータ量（例えば、５ＭＢ）未満であればステップＳ１４０に進み、そうではない場合、即ち、既に、既定のデータ量（例えば、５ＭＢ）に達している場合にはステップＳ１７０に進むものである。
【０１０５】
このように、本ステップにおいてＣＰＵ519は、これまでに得られた、アンカーポイント設定済粗輪郭データおよび各関数近似区間の誤差値の情報を少なくとも含むデータのデータ量（生成されたデータ量Ｄ）が規定のデータ量に達したか否かを判断する。そして、生成されたデータ量Ｄが規定のデータ量を越えた場合は、一連の近似精度向上処理（後述するステップＳ１４０〜Ｓ１６０）を行わず、一連のベクトル化処理を終了する。一方、生成されたデータ量が規定のデータ量を越えていない場合は、一連の近似精度向上処理を行う。よって、本処理によって生成されたデータ量Ｄが許される範囲内にある場合は、さらに近似精度を高める処理に続くことができる。よって、許容されたデータ量内において、近似精度を最大限まで高めることができる。
【０１０６】
次にステップＳ１４０では、ＣＰＵ519は、区間分割手段として機能し、ステップＳ１００で求められた最大誤差区間を区間分割して、該最大誤差区間においてさらに複数の関数近似区間を設定する。すなわち、ＣＰＵ519は、上記も止められた最大誤差区間を、ステップＳ６０で求められているその区間のアンカーポイントｐ１、ｐＮを結ぶ線分ｐ１ｐＮより最も距離の離れている曲線上の点ｐｆで二分する。次いで、点ｐ１と点ｐｆをその区間のアンカーポイントとする前半の区間と、点ｐｆと点ｐＮをその区間のアンカーポイントとする後半の区間とに分割する。そして、ＣＰＵ519は、第２の関数近似処理手段として機能し、前半の区間と後半の区間のそれぞれに対して、ステップＳ６０と同様の処理を行う。すなわち、分割後のそれぞれの区間に、その区間の二つのアンカーポイントを結ぶ線分より最も距離の離れている曲線上の点（以降、『再遠点』と称する）と２つのコントロールポイントを定める。
【０１０７】
このとき、図１０で示したアンカーポイント設定済粗輪郭データは、図１１（ａ）〜（ｃ）の様に変更される。即ち、同図において、分割されるのが、第ｉ番目のループの第ｊ番目の関数近似区間である場合、分割前のこの区間のデータを図１１(a)に表記する。そして、分割後の前半の区間のデータを図１１(b)に、後半の区間のデータを図１１(c)に表している。
【０１０８】
図１１(b)は、点ｐ１から点ｐｆの直前までの点と、新たに求められた最遠点と２つのコントロールポイントの座標値と、本ステップで新たにＲＡＭ５２０に確保される後半の区間のデータを格納するデータ領域の先頭アドレスへのポインタ領域とを含む。これは図１１(a)のデータそのものを書き換えることで生成される。
【０１０９】
図１１(c)は、点ｐｆと点ｐＮをその区間のアンカーポイントとする点ｐｆから点ｐＮの直前までの点のそれぞれの座標値と、新たに求められた最遠点と２つのコントロールポイントの座標値とを含む。さらに、元々の図１１(a)のデータの最後にあった分割前の第ｊ＋１区間のデータ領域先頭へのポインタ（アドレス情報）の値を分割後の第ｊ＋２区間のデータ領域先頭へのポインタ（アドレス情報）の値としてもつポインタ領域を含む。なお、上記ｊ＋１区間は、本ステップ以降では第ｊ＋２区間となる。
【０１１０】
このとき、このステップで新たにＲＡＭ５２０に確保される後半の区間のデータを格納するデータ領域のデータ量ΔＤ1は、もとの区間の最遠点（点ｐｆ）から点ｐＮの直前までの点の数をεとすると、  
ΔＤ1＝４×（ε＋５）  
バイトとなる。
【０１１１】
ステップＳ１４０の処理を終えると、ステップＳ１５０に進む。ステップＳ１５０では、ＣＰＵ519は、第２の区間内近似精度算出手段として機能し、ステップＳ１４０で生成された２つの関数近似区間（前半の区間、後半の区間）のそれぞれに対して、ステップＳ７０と全く同様にしてそれぞれの区間内誤差値を算出する。ＣＰＵ519は、算出されたそれぞれの区間内誤差値のうち、前半の区間の区間内誤差値を、もともとの第ｉ番目のループの第ｋ番目の関数近似区間用の区間内誤差値の格納領域に格納する。そして、後半の関数近似区間用の区間内誤差値の格納領域は、このステップで新たにＲＡＭ５２０上に確保される。
【０１１２】
この際、元々の第ｉ番目ループの第ｋ番目の関数近似区間用の次の関数近似区間（即ち、第ｋ＋１番目）の区間内誤差値領域へのポインタ（アドレス情報）領域には、後半の関数近似区間用の区間内誤差値の格納領域へのポインタ（アドレス情報）の値を格納する。この後半の関数近似区間用の区間内誤差値の格納領域へのポインタ（アドレス情報）の値は、このステップで新たにＲＡＭ５２０上に確保されるものである。一方、新たにＲＡＭ５２０上に確保される後半の関数近似区間用の次の関数近似区間の区間内誤差値領域へのポインタ（アドレス情報）領域には、次の値が格納される。すなわち該ポインタ（アドレス情報）領域には、、元々の図１３(a)における第ｋ＋１番目（新たには第ｋ＋２番目となる）の区間内誤差値領域へのポインタ（アドレス情報）の値を格納する。
【０１１３】
この様子を図１３（ａ）および（ｂ）に示す。即ち、同図において、分割されるのが、第ｉ番目のループの第ｊ番目の関数近似区間である場合、分割前のこの区間の区間内誤差値のデータを図１３(a)に表記する。分割後の区間内誤差値のデータを図１３(b)に表している。このステップで新たにＲＡＭ５２０上に確保されるデータ領域のデータ量ΔＤ2は、  
ΔＤ2＝４×２＝８  
バイトとなる。
【０１１４】
ステップＳ１５０の処理を終えると、ステップＳ１６０に進む。ステップＳ１６０では、ＣＰＵ519は、ステップＳ１００と全く同様に、第２の分割対象区間同定手段として機能し、ステップＳ１５０にて更新された区間内誤差値から、最大の区間内誤差値を有する関数近似区間を同定する。すなわち、改めて、ステップＳ１５０で更新された全ての区間内誤差値をそれぞれの区間に対するデータのポインタ情報を用いて順にサーチしながら、それらの中で、最大の値をもつものを求め、どの区間の区間内誤差が最大かを同定する。最大の誤差値をもつ区間が複数存在する場合には、それらの中でサーチ順の最初の区間を最大誤差区間とする。そして、ステップＳ１１０へ戻る。
【０１１５】
以降、ステップＳ１１０、ステップＳ１２０、ステップＳ１３０のいずれかでステップＳ１７０へ分岐することになるまでの間、ステップＳ１１０〜ステップＳ１６０の処理を繰り返すことになる。但し、ステップＳ１３０でチェックするデータ量は、ステップＳ１１０〜ステップＳ１６０の処理を繰り返すたびに、上述のΔＤ1とΔＤ2を加えた値ΔＤ、即ち  
ΔＤ＝ΔＤ1＋ΔＤ2 
＝４×（ε＋５）＋８  
＝４×ε＋２８  
バイトずつ増えた値を新たな生成されたデータ量Ｄとして用いて判断をするものである。（Ｄ←Ｄ＋ΔＤ）
【０１１６】
さて、ステップＳ１７０では、ＣＰＵ519は、それまでに求めた各輪郭線ループの各関数近似区間のアンカーポイントとコントロールポイントのそれぞれのデータを、所定の装置や装置外へと出力する。すなわち、該データを、上記図１０、及び図１２の形式で保持されたアンカーポイント設定済粗輪郭データ中をポインタ情報を用いて順にサーチしながら公知の所望のデータ形式にて、I/O５２１を介してハードディスク５２２へ出力する。あるいは、通信I/F４を介して装置外へ出力するものである。なお、上記公知の所望のデータ形式としては、例えば、ＳＶＣ（Scarable Vector Graphics）等を用いることができる。
【０１１７】
このように本実施形態では、ステップＳ１１０のようなデータ量判定処理、およびステップＳ１３０のような処理時間計測判定処理を行っている。
【０１１８】
データ量判定処理においては、生成されたデータ量Ｄが、許容値となる規定のデータ量に達したと判断されるまでは、一連の近似精度向上処理（後述するステップＳ１４０〜Ｓ１６０）を行うと判断する。この判断に基き、上記近似精度向上処理として、ステップＳ１００またはＳ１５０で同定された区間内最大誤差値（近似精度の向上を図るべき関数近似区間）を分割し、該分割で生じたそれぞれの区間の関数近似処理と近似精度の算出処理とを行うことができる。
【０１１９】
同様に、処理時間計測判定処理を行う場合、処理時間が許容値となる規定の処理時間を越えたと判断するまでは、上記一連の近似精度向上処理を行うと判断する。
【０１２０】
よって、許容されるデータ量の範囲内、および許容される処理時間において、近似精度を最大限まで高めることができる。
【０１２１】
（第２の実施形態）  
上述した、図１０、図１１、図１２、図１３に示したデータ形式は、一例にすぎず、これに限らない。また、第１の実施形態で説明した図３のステップS１７０で出力するベクトルデータの形式もこれに限らない。即ち、図１０の輪郭線中ループ数（ａ）の後の輪郭線ループ毎のデータを、その輪郭線中の区間数のデータ（αi）に続けて各関数近似区間のデータをアンカーポイントｐ１と２つのコントロールポイントＣ１、Ｃ２のみで構成する。そして、出現する関数近似区間の並び順に（即ちαi個の区間分）、纏めて詰めた形式とするようにしてももちろん良い。この場合のベクトルデータの形式を図１４に示す。
【０１２２】
（第３の実施形態）  
上述の実施形態では、２値画像は、スキャナ１で読み込まれた画像を２値化して得られるとして説明を進めてきたが、これに限るものではない。例えば、通信Ｉ／Ｆ４を介してネットワーク等を経由して、システムの外部（ネットワークに接続されたスキャナやＰＣ）より入力されたものでも良いのはもちろんである。
【０１２３】
また、上述した実施形態では、上述した画像処理装置を、デジタル複写機、ネットワークに接続されたプリンタ、ＰＣなどで実現することができる。
【０１２４】
（第４の実施形態）  
上述のステップＳ１４０においては、図１１(a)に表記した分割前の関数近似区間のデータを、図１１(b)に表記した分割後のデータの前半と、図１１(c)に表した後半のデータに分けることを述べた。この際、図１１(b)は、点ｐ１から点ｐｆの直前までの点と、新たに求められた最遠点と２つのコントロールポイントの座標値を含む。そしてさらに、このステップで新たにＲＡＭ５２０に確保される後半の区間のデータを格納するデータ領域の先頭アドレスへのポインタ領域を含む。従って、もとの図１１(a)のデータそのものを書き換えることで生成すると、点ｐｆから点ｐＮの直前までの点のそれぞれの座標値を格納していたデータ領域が不要となる。
【０１２５】
そこで、ステップＳ１４０では、この不要となった領域を詰めて不要な領域が散在しないようにデータを移動されるように構成しても良い。即ち、一旦は上述のステップＳ１４０の動作の様に図１１(c)のデータを生成した後，図１１(b)を生成後に不要となったもとの図１１(a)のデータ領域の後半部分には、ε点分のデータ領域が存在する。よって、もとの図１１(a)のデータ領域に続いたデータ領域部分を、このε点分のデータ領域分だけ順じ詰めてＲＡＭ５２０上に配置しなおすようにしても良い。このようにすると、データの移動と、移動させたデータ領域分に相当する分だけポインタ（アドレス情報）格納領域の値を全て書き換える必要とが生じて、それだけ処理時間が遅くはなる。しかしながら、ＲＡＭ５２０上に無駄に散在するデータ領域が不要となるため、処理途中でメモリ領域をより有効に使用できるというメリットが生じる。
【０１２６】
また、この場合には、ステップで新たにＲＡＭ５２０に確保されるデータ領域のデータ量ΔＤ1は、  
ΔＤ1＝４×（ε＋５−ε）  
＝２０  
バイトとなる。
【０１２７】
（第５の実施形態）  
これまで、処理時間とデータ量を両方チェックしながら本発明の実施形態の説明を進めてきたが、これに限るものではなく、いずれか一方のチェックのみでも良いのはもちろんである。  すなわち上述では、ステップＳ１１０にて処理時間に余裕が有るか否かを、ステップＳ１３０にて生成されたデータ量が許容された範囲内であるか否かを判断しているが、ステップＳ１１０およびステップＳ１３０のいずれか一方のみを行うようにしても良い。
【０１２８】
即ち、データ量のチェックを行なわず、処理時間のチェックのみを行なう場合には、図３のフローチャートにおけるステップＳ１３０を行なわず、上述のステップＳ１２０の処理の後にステップＳ１３０に進んでいた部分をステップＳ１４０に進むようにすればよい。この場合には、処理時間には制限を設けずに、処理途中で生じるデータ領域として使用可能なメモリ容量に制限がある場合において、従来に比して近似精度の向上した関数近似の実現が可能となる。また、処理時間のチェックを行なわず、データ量のチェックのみを行なう場合には、以下のようにすれば良い。すなわち、図３のフローチャートにおけるステップＳ１１０を行なわず、上述のステップＳ１００やステップＳ１６０の処理の後にステップＳ１３０に進んでいた部分をステップＳ１２０に進むようにすればよい。この場合には、処理途中で生じるデータ領域として使用可能なメモリ容量は十分に確保されているが、処理時間には制限がある場合において、従来に比して近似精度の向上した関数近似の実現が可能となる。
【０１２９】
（第６の実施形態）  
上述の実施形態の説明では、ステップＳ７０で求める区間内誤差値として（Δx）2 を用いたが、これに限るものではない。この他にも、例えば、上述の(4)式で得られるΔxをもって、区間内誤差値としてもよい。また、精度的には最適とはいえないが、｜Ｐdx - ｐfx｜ + ｜Ｐdy - ｐfy｜をもって区間内誤差値としてもよく、この場合には誤差値の計算速度の向上が期待できる。
【０１３０】
（その他の実施形態）  
本発明は、複数の機器（例えばコンピュータ、インターフェース機器、リーダ、プリンタなど）から構成されるシステムに適用することも、１つの機器からなる装置（複合機、プリンタ、ファクシミリ装置など）に適用することも可能である。
【０１３１】
前述した実施形態の機能を実現するように前述した実施形態の構成を動作させるプログラムを記憶媒体に記憶させ、該記憶媒体に記憶されたプログラムをコードとして読み出し、コンピュータにおいて実行する処理方法も上述の実施形態の範疇に含まれる。即ちコンピュータ読み取り可能な記憶媒体も実施例の範囲に含まれる。また、前述のコンピュータが実行可能なコンピュータプログラムが記憶された記憶媒体はもちろんそのコンピュータプログラム自体も上述の実施形態に含まれる。
【０１３２】
かかる記憶媒体としてはたとえばフロッピー（登録商標）ディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ―ＲＯＭ、磁気テープ、不揮発性メモリカード、ＲＯＭを用いることができる。
【０１３３】
また前述の記憶媒体に記憶されたプログラム単体で処理を実行しているものに限らず、他のソフトウエア、拡張ボードの機能と共同して、ＯＳ上で動作し前述の実施形態の動作を実行するものも前述した実施形態の範疇に含まれる。
【図面の簡単な説明】
【０１３４】
【図１】本発明の一実施形態を実施する画像処理装置を実現する機器構成例を示す図である。
【図２】従来の、２値画像のアウトラインベクトル処理の流れによる一連の処理経過の例を示す図である。
【図３】本発明の一実施形態を実施する画像処理装置における処理の一連の流れを説明するフローチャートである。
【図４】図１における粗輪郭抽出部５の構成例をより詳細に示す図である。
【図５】本発明の一実施形態に係る、２値画像における注目画素と、その近傍画素の状態を見て処理を進める様子を示す図である。
【図６】本発明の一実施形態における輪郭抽出処理の全体の流れを示すフローチヤートである。
【図７】本発明の一実施形態に係る粗輪郭ベクトルデータの形式の一例を示す図である。
【図８】従来の、関数近似対象区間の一例を示す図である。
【図９】本発明の一実施形態に係る、関数近似処理を終えた関数近似対象区間の区間内の近似誤差を示す図である。
【図１０】本発明の一実施形態に係るアンカーポイント設定済粗輪郭データの形式の一例を示す図である。
【図１１】（ａ）〜（ｃ）は、本発明の一実施形態に係る、最大誤差区間を分割した際のアンカーポイント設定済粗輪郭データ更新の一例を示す図である。
【図１２】本発明の一実施形態に係る、各関数近似区間の誤差値のデータ形式の一例を示す図である。
【図１３】（ａ）および（ｂ）は、本発明の一実施形態に係る、最大誤差区間を分割した際の関数近似区間の誤差値のデータ更新の一例を示す図である。
【図１４】本発明の一実施形態に係るステップS１７０で出力するベクトルデータの形式を示す図である。
【符号の説明】
【０１３５】
１      スキャナ
２      画像メモリ
３      画像入出力Ｉ／Ｏ
４      通信Ｉ／Ｆ
５      粗輪郭抽出部
６      ROM
７      ２値画像獲得部
５０    入力画像ラスター走査部
５１８  バス
５１９  CPU
５２０  RAM
５２１  Ｉ／Ｏ
５２２  ハードディスク装置
【図１】
0005137679.tif 000002
【図２】
0005137679.tif 000003
【図３】
0005137679.tif 000004
【図４】
0005137679.tif 000005
【図５】
0005137679.tif 000006
【図６】
0005137679.tif 000007
【図７】
0005137679.tif 000008
【図８】
0005137679.tif 000009
【図９】
0005137679.tif 000010
【図１０】
0005137679.tif 000011
【図１１】
0005137679.tif 000012
【図１２】
0005137679.tif 000013
【図１３】
0005137679.tif 000014
【図１４】
0005137679.tif 000015