画像処理方法、画像処理装置、プログラム、及びプログラム記憶媒体
【課題】ラスタ画像からベクトル画像へ変換する際に行う関数近似において、変曲点の接線方向をそろえたい場合であっても、都度傾きの変化量を計算することによる処理を複雑化せずに簡易に行う。
【解決手段】変曲点の接線方向を適応的に判定して決定する。このとき、ラスタ画像から得られる座標点列からアンカ点と、その点の性質を表す属性を共に抽出し、変曲点に属する属性を持つアンカ点の接線方向を前後で揃える。
【解決手段】変曲点の接線方向を適応的に判定して決定する。このとき、ラスタ画像から得られる座標点列からアンカ点と、その点の性質を表す属性を共に抽出し、変曲点に属する属性を持つアンカ点の接線方向を前後で揃える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像処理技術に関するものであり、特にラスタ画像から特徴点を抽出し、関数近似を行うことでベクタ画像へ変換を行う画像処理技術に関する。
【背景技術】
【０００２】
近年、ディスプレイや印刷機器など解像度の異なる機器の混在化が進み、一つの画像情報を異なる解像度で表示する機会が増えてきている。ところが低解像度機器に適した画像を高解像度機器で表示しようとすると、機器の解像度を生かすことができず画質の劣化が目立ってしまう。このことからラスタ形式で表現された画像を、解像度に依存しないベクタ形式へ変換する、ベクトル化技術が必要となってきている。
【０００３】
ベクトル化技術の検討は以前からも行われており、例えば、二値画像を対象としたベクトル化手法が特許文献１で開示されている。この手法は二値画像の輪郭を、以下の条件を満たす点で分割し、分割区間に対してそれぞれベジェ曲線で近似を行う。
【０００４】
角点１：隣接する点列を結ぶベクトルの変化が鋭角となる点
角点２：連続する点と点との距離がある閾値より大きい場合の両端の点
変曲点：連続するベクトルの外積の符号が変化する点
座標点列の抽出処理として、例えば、特許文献２のような手法が開示されている。この手法によれば注目画素とその近傍画素の状態に基づいて、水平方向及び垂直方向の画素間ベクトルを検出し、これら画素間ベクトル同士の接続状態を判別して、画素間ベクトルの接続状態から画像データの座標点列を抽出するように動作する。画素の中心位置ではなく、画素の縁単位に座標点列を抽出することにより、１画素幅の細線に対しても有為な幅を持たせることが出来る座標点列抽出法である。
【０００５】
また２値画像のみならず、数色に及ぶ線画やイラスト画像を対象としたベクトル化手法が例えば、特許文献３で開示されている。この手法は、色領域間で共通な境界線を抽出し、関数近似を行うという処理フローで原理的に隙間が生じないカラー画像のベクトル化を実現している。ここでの座標点列抽出手法は特許文献２とは異なり、隣接する画素間で色が閾値以上異なる線を追跡することで抽出している。抽出後の座標点列から色領域間で共通する境界線を求め、色領域を出力する際に共通の関数近似結果を適用し、ベクトル化を行う。
【０００６】
また、近似処理を行う際、近似区間とのつながりを平滑にする近似手法として、例えば、特許文献４で開示されている。曲線式Ａで表現された複数の区間を統合し、その統合した区間をより高次の曲線式Ｂで近似し、表現することでデータ削減と文字輪郭線の滑らかさを維持・改善する手法である。この中で、統合した区間を分割点で区切り、区切られた区間を曲線式Ｂで近似を行っている。しかし区切られた区間で独立して近似を行うと、分割点の前後で滑らかさが失われてしまうので、２つの曲線が共通接線を持つように制御点の位置を修正することで、分割点前後での滑らかさを保持する手法を開示している。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００５−３１００７０号公報
【特許文献２】特許第３０２６５９２号
【特許文献３】特開２００６−０３１２４５号公報
【特許文献４】特開平０４−１１６６９０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら従来技術では近似処理を行う際に分割点前後で接線方向を揃えるか否かという判定は行っていなかった。このことから接線方向を揃える場合、全ての分割点で揃える処理を行うため、図１（ａ）を入力画像とすると図１（ｂ）に示すようにエッジ部が丸まってしまう。接線方向を揃えなかった場合は、全ての区間で独立して近似するため分割点での連続性は保証されず、図１（ｃ）に示すように曲線の途中角張ってしまう結果となる。
【０００９】
これを防止するには、接線方向を揃える区間とそうでない区間を適応的に判定すればよい。しかし、分割点を決定した後、接線方向を決定する段階で判定しようとすると、都度傾きの変化量を計算する必要があるため、前後数辺分の参照が再度必要となり、処理が複雑化する。
【課題を解決するための手段】
【００１０】
上記課題を解決するために、本発明に係る画像処理装置は以下の構成を備える。画像データの形状を表現する座標点列から、アンカ点を抽出するために予め定められた複数の抽出ルールに基づき、アンカ点の座標と当該アンカ点が予め定められた複数の属性のいずれに属するかとを決定し、前記アンカ点の座標と当該アンカ点の属性を含む情報を出力するアンカ点情報抽出手段と、着目アンカ点の前記属性および前記着目アンカ点から所定の範囲にあるアンカ点の座標に応じて前記着目アンカ点における接線方向を決定する接線方向決定手段と、前記着目アンカ点の接線方向及び座標からコントロール点座標を算出するコントロール点座標算出手段と、前記アンカ点の座標と前記コントロール点座標とを含む情報を出力するデータ出力手段とを有する。
【発明の効果】
【００１１】
本発明によれば、変曲点の接線方向を適応的に判定して決定する場合であっても、処理を複雑化せずに簡易に行うことができる。
【図面の簡単な説明】
【００１２】
【図１】接線方向をそろえるか否かの違いによるベクトル化結果を示す図。
【図２】本発明に係る画像処理装置のブロック構成図。
【図３】本発明に係る画像処理装置のメイン処理ブロック構成図。
【図４】実施形態１に係る画像処理装置のメイン処理を示すフローチャートの図。
【図５】二値画像における一画素と一画素より生成される座標点を示す図。
【図６】二値画像と二値画像より生成される座標点列例を示す図。
【図７】多値画像と多値画像より生成される座標点列例を示す図。
【図８】ベジェ曲線の概念を示す図。
【図９】着目点と周辺の座標点を示す図。
【図１０】実施形態１に係るアンカ点候補情報抽出処理を示すフローチャートの図。
【図１１】実施形態１に係るアンカ点候補判定処理を示すフローチャートの図。
【図１２】実施形態１に係るアンカ点候補判定処理を示すフローチャートの図。
【図１３】実施形態１に係るアンカ点候補情報抽出ルールの例を示す図。
【図１４】実施形態１に係るアンカ点決定処理を示すフローチャートの図。
【図１５】実施形態１に係る削減処理を示すフローチャートの図。
【図１６】実施形態１に係るコントロール点座標決定処理に関する説明図。
【図１７】実施形態１に係る接線方向決定処理を示すフローチャートの図。
【図１８】実施形態１に係る接線方向決定処理における接線方向例を示す図。
【図１９】実施形態２に係るアンカ点決定処理を示すフローチャートの図。
【図２０】実施形態１と実施形態３に係る座標点追跡の違いを示す図。
【図２１】実施形態３に係る着目点と周辺の座標点と中点を示す図。
【図２２】実施形態３に係るアンカ点候補情報抽出処理を示すフローチャートの図。
【図２３】実施形態３に係るアンカ点候補判定処理を示すフローチャートの図。
【図２４】実施形態３に係るアンカ点候補判定処理を示すフローチャートの図。
【図２５】実施形態３に係る屈曲点と変曲点の抽出ルールの例を示す図。
【図２６】入力画像と本発明を適用した際に得られるベクトル化結果を示す図。
【発明を実施するための形態】
【００１３】
＜実施形態１＞
以下、添付の図面を参照して本発明の実施の形態を説明する。ただし、この実施の形態に記載されている構成要素はあくまで例示であり、本発明の技術的範囲は、特許請求の範囲によって確定されるのであって、以下の個別の実施形態によって限定されるわけではない。
【００１４】
本実施形態の画像処理装置の構成例について、図２のブロック図を参照して説明する。図２において、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）７は装置全体を制御する。なお、以下に示す各処理フローは、特段の記載が無い限り、ＣＰＵ７によって実行される。ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）６は変更を必要としないプログラムやパラメータを格納する。ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）５は外部装置等から供給されるプログラムやデータを一時記憶する。スキャナ１は、文書等を光電走査して電子的な画像データを取得し、画像入出力Ｉ／Ｏ３はスキャナ１と画像処理装置を接続する。画像メモリ２は、スキャナ１で読み取られた画像データ等を保持する。外部記憶装置１２は固定して設置されたハードディスクやメモリカード、あるいは着脱可能なフレキシブルディスク（ＦＤ）やＣｏｍｐａｃｔ Ｄｉｓｋ（ＣＤ）等の光ディスク、磁気や光カード、ＩＣカード、メモリカード等のプログラム記憶媒体を含む。また、Ｉ／Ｏ１３はこれら外部記憶装置１２とコンピュータ装置との入出力を行う。Ｉ／Ｏ１５はユーザの操作を受け、データを入力するマウス等のポインティングデバイス１０やキーボード９等の入力デバイスとの入出力を行う。映像Ｉ／Ｏ１４は画像処理装置の保持するデータや供給されたデータを表示するためのディスプレイモニタ８との入出力を行う。通信Ｉ／Ｆ４は、インターネット等のネットワーク回線に接続するためのインタフェースである。システムバス１１は上述した各ユニットを通信可能に接続する。
【００１５】
［処理フロー］
以下、ＣＰＵ７上で実行されるプログラムにより本願発明を実現する処理手順を、図３のブロック図と図４のフローチャートを用いて説明する。
【００１６】
図４のフローチャートにおいて、Ｓ１００で処理を開始すると、処理対象となる画像領域を含む画像データを入力する。画像入力に関しては、スキャナ１にて読み取られた画像データを画像入出力Ｉ／Ｏ３を介して画像メモリ２に入力する。また、通信Ｉ／Ｆ４を介して、装置外部より処理対象となる画像領域を含む画像を入力してもよく、あるいは、外部記憶装置１２に予め記憶される画像データをＩ／Ｏ１３を介して読み込むものであってもよい。得られた入力画像データは、画像メモリ２上に保持される。以上の処理は図３における画像入力手段１０００を実現している。
【００１７】
次に読み取った画像データに対してＳ１１０で座標点列抽出処理を行う。ここで扱う画像データに含まれる１つの黒画素を図５に示す。図５で示すように、画像データにおける１画素は、４つの頂点を有し、垂直方向の向きを示す垂直ベクトルと水平方向の向きを示す水平ベクトルより構成される正方形として扱う。１画素を４つの頂点を有する正方形として扱い、複数の画素の集合である画像データのアウトラインを抽出すると、水平ベクトルと垂直ベクトルからなる座標点列がアウトラインデータとして得られる。このような座標点列の抽出方法は、種々提案されており、特に特許文献２で開示されている座標点列抽出方法を用いれば、画像一面より効率良くかつ高速に座標点列を抽出することが可能である。例えば、図６（ａ）で示す画像から抽出された座標点列は、図６（ｂ）に示すような、水平ベクトル、垂直ベクトルが交互に並ぶ構成となる座標点列となる。すなわち、座標点とは、水平ベクトル、または垂直ベクトルの方向が変化する点を意味する。
【００１８】
またこのとき、読み取った画像データが複数色に及ぶ場合は、特許文献３に記載されている座標点列追跡法を適用することができる。即ち、図７（ａ）に示したように、３色以上の色領域の交点が存在した時、交点において座標点列の分割を行い、図７（ｂ）で示したようにそれぞれを異なる座標点列として抽出する手法である。図７（ｂ）は、４つの座標点列が得られた場合の例である。本実施形態では座標点列を追跡した結果、始点と終点が同一の座標となるような座標点列を閉輪郭、始点と終点が異なった座標となる座標点列を開輪郭と呼称する。以上の処理は図３における座標点列抽出手段１１００を実現している。また、Ｓ１００とＳ１１０は合わせて図３における座標点列入力手段１００を実現している。
【００１９】
次にＳ１２０、Ｓ１３０、Ｓ１４０、Ｓ１５０では抽出した座標点列に対して関数近似処理を行う。本実施形態では置き換える関数として、３次ベジェ曲線を用いる。３次ベジェ曲線は図８に示すとおり、２つのアンカ点と２つのコントロール点から構成され、以下の式によって定義される。このとき図８において、黒丸はアンカ点ａ１，ａ２を、白丸はコントロール点ｃ１，ｃ２をそれぞれ示す。またｔは媒介変数であり０≦ｔ≦１とする。
【００２０】
よって３次ベジェ曲線を用いて関数近似を行うには、Ｓ１１０で得た座標点列を適切に区切るアンカ点の決定と、その間を構成する座標点列の形状を適切に近似するコントロール点の決定が必要となる。以下から本実施形態における関数近似処理のフローを説明する。
【００２１】
まずＳ１２０ではアンカ点候補情報抽出処理を行う。ここでは、Ｓ１１０で抽出した座標点列において着目している点と、その近傍の座標点のなすパターンが、あらかじめ定められた複数の抽出ルールで規約済みのパターンであった場合に、当該着目点をアンカ点の候補としアンカ点候補情報を出力する。Ｓ１２０では、図９に示すように現在着目している座標点列の点を着目点Ｐｉ（ｉ＝１，２，…ｎ）とし、着目点Ｐｉから見て座標点列追跡方向と逆方向の座標点をＰｉ−１、Ｐｉ−２…とし、座標点列追跡方向と順方向の座標点をＰｉ＋１、Ｐｉ＋２…とする。また、アンカ点候補情報とは、アンカ点の候補として抽出した座標と、その着目点Ｐｉ近傍のパターン特性を示す属性を指す。
【００２２】
図１０は、ＣＰＵ７によって実行される、Ｓ１２０で行われるアンカ点候補情報抽出処理のフローである。まずＳ１２１で、追跡する座標点列の初期点を設定し、該当の座標点を着目点とする。次にＳ１２２では着目点Ｐｉ自身をアンカ点候補とすべきか否かを判定する。
【００２３】
なお、本発明において、複数の閾値を用いて判定等を行っているが、閾値の設定に関しては、実験的に導いてもよいし、所定の式等に基づいて決定してもよい。また、閾値以上、閾値以内と記載している箇所があるが、設定した閾値の特性や必要に応じて、判定条件は調整してもよい（例えば、閾値より小さい、など）。
【００２４】
［着目点判定処理］
図１１は、ＣＰＵ７によって実行される、着目点判定処理の詳細な処理フローである。まずＳ１２２１で着目点の端点判定を行う。端点は図１３（ａ）に示したように開輪郭の着目座標点Ｐｉに対し、前、もしくは後に座標点が存在しない点である。端点と判定された場合は、Ｓ１２２２に遷移し、その着目点Ｐｉ自身の座標と、「端点」という属性を保持し、処理を終える。
【００２５】
Ｓ１２２１にて端点でないと判定された場合は、Ｓ１２２３の折点判定に遷移する。折点は図１３（ｂ）に示したように座標Ｐｉ−１、Ｐｉ＋１を参照点とし、着目点Ｐｉと参照点Ｐｉ−１、Ｐｉ＋１それぞれとがなす辺Ｐｉ−１Ｐｉと辺ＰｉＰｉ＋１の長さが共に閾値Ｔ１以上となる点とする。また、辺Ｐｉ−１Ｐｉと辺ＰｉＰｉ＋１は、向きが水平方向から垂直方向もしくは垂直方向から水平方向へ変化することとする。ここで言う辺の長さとは、座標間に内包される画素長を指す。このとき閾値Ｔ１は、一意に定めてもよいし、画像の大きさを加味して可変としてもよい。本実施形態ではＣを座標点列の外接矩形の外周の長さとして、閾値Ｔ１＝２＋Ｃ／３００としている。ただし、閾値Ｔ１は２≦Ｔ１≦６の範囲で限定をしている。折点と判定された場合は、Ｓ１２２２に遷移し、その着目点Ｐｉ自身の座標と、「折点」という属性を保持し、処理を終える。
【００２６】
Ｓ１２２３にて折点でないと判定された場合は、Ｓ１２２４に遷移する。Ｓ１２２４では現在着目している座標点が端点から数えて奇数点目か偶数点目かを判定する。すなわち、ｉが偶数か奇数かを判定する。ここで偶数点目であると判定された時はＳ１２２７へ遷移し、着目点Ｐｉ自身の座標のみを保持し、そのまま処理を終える。奇数点目と判定された場合はＳ１２２５へ遷移する。
【００２７】
Ｓ１２２５では屈曲点判定を行う。屈曲点は図１３（ｆ）に示したように座標Ｐｉ−２、Ｐｉ＋２を参照点とし、線分Ｐｉ−２Ｐｉと、線分ＰｉＰｉ＋２とがなす角度θを算出し、角度θが閾値Ｔ２以上となる点とする。本実施形態では閾値Ｔ２＝２５°としている。屈曲点と判定された場合は、Ｓ１２２２へ遷移し、その着目点Ｐｉ自身の座標と、「屈曲点」という属性を保持し、処理を終える。
【００２８】
Ｓ１２２５で屈曲点ではないと判定された場合は、Ｓ１２２６の変曲点判定へ遷移する。変曲点は図１３（ｇ）に示したように座標Ｐｉ−４、Ｐｉ−２、Ｐｉ＋２を参照点とし、線分Ｐｉ−４Ｐｉ−２の傾きαと、線分Ｐｉ−２Ｐｉの傾きβと、線分ＰｉＰｉ＋２の傾きγを算出する。そして、傾きの変化量となるβ‐α、γ‐βをそれぞれ算出し、この傾きの変化量同士の正負が入れ替わる点を変曲点とする。すなわち、傾きの変化量における連続したベクトル間において、その外積の符号が変化する点を変曲点とする。ただし、傾きの変化量β‐αの絶対値が閾値Ｔ３以下となる場合は、β‐αの絶対値が閾値Ｔ３以上の値を取るまで傾きαをとる線分をＰｉ−６Ｐｉ−４、Ｐｉ−８Ｐｉ−６…と遡らせて判定を行う。本実施形態では閾値Ｔ３＝１．０×１０−７としている。変曲点と判定された場合は、Ｓ１２２２へ遷移し、その着目点Ｐｉ自身の座標と、「変曲点」という属性を保持し、処理を終える。Ｓ１２２６で変曲点ではないと判定された場合は、Ｓ１２２７に移り、着目点Ｐｉ自身の座標のみを保持し、そのまま処理を終える。
【００２９】
［着目辺判定処理］
以上まででＳ１２２の着目点Ｐｉ自身のアンカ点候補判定は終えた。次に着目辺ＰｉＰｉ＋１上にアンカ点候補を取るべきか否かを判定するＳ１２３に移る。ここで、着目辺とは着目点Ｐｉと、その次に存在する座標点Ｐｉ＋１を結ぶ辺を指す。ここでアンカ点候補が抽出された場合は、その座標は着目辺上となるためＳ１１０で抽出した座標点列ＰｉＰｉ＋１の間に書き加える。図１２はその詳細な処理フローである。
【００３０】
まずＳ１２３１で着目辺ＰｉＰｉ＋１が直線保持辺か否かを判定する。直線保持辺は図１３（ｃ）、（ｄ）に示したように、判定するためにまず座標Ｐｉ−２、Ｐｉ−１、Ｐｉ＋１または座標Ｐｉ＋１、Ｐｉ＋２、Ｐｉ＋３を参照点とする。そして、ベクトルＰｉ−２Ｐｉ−１、ＰｉＰｉ＋１の長さ｜Ｐｉ−２Ｐｉ−１｜、｜ＰｉＰｉ＋１｜、またはベクトルＰｉＰｉ＋１、Ｐｉ＋２Ｐｉ＋３の長さ｜ＰｉＰｉ＋１｜、｜Ｐｉ＋２Ｐｉ＋３｜をそれぞれ算出する。そして、｜ＰｉＰｉ＋１｜が｜Ｐｉ−２Ｐｉ−１｜の閾値Ｔ４倍以上、または｜ＰｉＰｉ＋１｜が｜Ｐｉ＋２Ｐｉ＋３｜の閾値Ｔ４倍以上となり、かつ双方のベクトル方向が同一である辺を直線保持辺であるとする。つまり、直線保持辺は、近傍の辺に対し、一定の値以上の長さを有することとなる。直線保持辺であると判定された場合、Ｓ１２３２へ遷移する。そして、Ｔ５を閾値として、着目辺ＰｉＰｉ＋１上において、座標Ｐｉ、Ｐｉ＋１からそれぞれ距離｜ＰｉＰｉ＋１｜／Ｔ５だけ離れた位置にある点を２点決定し、その属性を「直線保持点」として保持し、処理を終える。このとき閾値Ｔ４、閾値Ｔ５は、所定の値として一意に定めてもよいし、画像の大きさを加味して可変としてもよい。本実施形態では閾値Ｔ４＝１０、閾値Ｔ５＝５としている。
【００３１】
Ｓ１２３１で着目辺ＰｉＰｉ＋１が直線保持辺でないと判定された場合は、Ｓ１２３３の頂点を含む辺判定の処理へ遷移する。頂点を含む辺は、図１３（ｅ）に示したように座標Ｐｉ−１、Ｐｉ＋１、Ｐｉ＋２を参照点とし、ベクトルＰｉ−１Ｐｉと、ベクトルＰｉ＋１Ｐｉ＋２の方向が逆行する辺であるとする。つまり、この例において、着目辺ＰｉＰｉ＋１が頂点を含む辺となる。着目辺ＰｉＰｉ＋１が頂点を含む辺であると判定された場合、Ｓ１２３４に移り、線分ＰｉＰｉ＋１の中点座標と、属性「頂点」を保持し、処理を終える。Ｓ１２３３で着目辺ＰｉＰｉ＋１が頂点を含む辺でないと判定された場合は、そのまま処理を終える。
【００３２】
以上まででＳ１２３の着目辺ＰｉＰｉ＋１のアンカ点候補判定は終えた。次にＳ１２４で、現在の着目点が追跡している座標点列の終点であるか否かを判定する。すなわち、すべての座標点に対し、アンカ点候補判定の処理が終了したか否かを判定する。終点ではないと判定された場合は、Ｓ１２５で着目点を座標点列上における次の座標点として、再度Ｓ１２２へ遷移する。終点であると判定された時はアンカ点候補情報抽出処理を終える。以上の処理は図３におけるアンカ点候補情報抽出手段１２００を実現している。
【００３３】
［アンカ点決定処理］
次に抽出したアンカ点候補情報に基づいてＳ１３０でアンカ点決定処理を行う。ここで、Ｓ１２０においてアンカ点候補として抽出された座標点列をＱｊ（ｊ＝１，２，…ｍ）と呼称する。そして着目点Ｑｊに対し、その前後の近傍の座標点Ｑｊ−２、Ｑｊ−１、Ｑｊ＋１、Ｑｊ＋２を参照点とする。そして、その参照点のうちいずれかにＳ１２０において抽出したアンカ点候補が２つ以上あった場合、各アンカ点候補の属性に応じて削減するか否かを決定する。またここでいう削減とは、Ｓ１２０でアンカ点候補として抽出した座標における属性を削除し、アンカ点候補ではない座標点の状態に戻すことを指す。ただし、属性「頂点」と「直線保持点」においては、Ｓ１２０で辺上に新たに書き加えた点であるので、削減する場合は元のＳ１１０で抽出した座標点列の状態に戻すために、属性だけでなく、その座標も削減することとする。
【００３４】
図１４は、ＣＰＵ７によって実行される、Ｓ１３０で行われるアンカ点決定処理の詳細なフローである。まずＳ１３１で、追跡する座標点列の初期点を設定し、該当の座標点を着目点Ｑｊとして、Ｓ１３２へ遷移する。Ｓ１３２では、着目点Ｑｊがアンカ点候補として抽出された点か否かを判定する。着目点Ｑｊがアンカ点候補として抽出された点でなかった場合は、Ｓ１３６へ遷移する。着目点Ｑｊがアンカ点候補として抽出された点であった時は、Ｓ１３３へ遷移する。Ｓ１３３では着目しているアンカ点候補Ｑｊに対し、前後の近傍の座標点が２点以内（Ｑｊ−２、Ｑｊ−１、Ｑｊ＋１、Ｑｊ＋２）である点を参照点とし、参照点内にアンカ点候補が存在するか否かを判定する。参照点内にアンカ点候補が存在しなかった場合は、Ｓ１３６へ遷移する。参照点内にアンカ点候補が存在した場合は、Ｓ１３４へ遷移する。
【００３５】
Ｓ１３４ではアンカ点候補同士の優先順位の比較を行う。ここで、アンカ点候補の優先順位は、アンカ点候補情報における属性に依存する。本実施形態ではアンカ点候補の優先順位を高いものから「折点」、「直線保持点」、「頂点」、「屈曲点」、「変曲点」とあらかじめ定義しておく。また「端点」は、近似処理を終えた後、各座標点列をつなぎ合わせる過程で必要な点であるため、例外として削減対象とはしない。着目アンカ点候補Ｑｊの優先順位が、参照点内に存在するアンカ点候補の優先順位よりも高い場合、Ｓ１３６へ移る。着目アンカ点候補Ｑｊの優先順位が、参照点内に存在するアンカ点候補の優先順位以下であった場合はＳ１３５に移る。
【００３６】
［削減処理］
Ｓ１３５ではアンカ点候補の削減処理を行う。すなわち、アンカ点候補が有する属性を削除することにより、アンカ点候補としての座標点を削減している。図１５は、ＣＰＵ７によって実行される削減処理の詳細なフローである。まずＳ１３５１では、着目アンカ点候補Ｑｊの属性が「変曲点」か否かを判定する。着目アンカ点候補Ｑｊの属性が「変曲点」であった場合、Ｓ１３５２へ遷移し、着目アンカ点候補Ｑｊの属性を削除し、処理を終える。着目アンカ点候補Ｑｊの属性が「変曲点」でなかった場合、Ｓ１３５３へ遷移する。Ｓ１３５３では、着目アンカ点候補Ｑｊの属性が「屈曲点」か否かを判定する。着目アンカ点候補Ｑｊの属性が「屈曲点」であった場合、Ｓ１３５４へ遷移し、参照点内のアンカ点候補が、当該着目アンカ点候補Ｑｊに隣接する参照点Ｑｊ−１、Ｑｊ＋１か否かを判定する。そして参照点Ｑｊ−１、Ｑｊ＋１がアンカ点候補であった場合はＳ１３５５へ遷移し、着目アンカ点候補Ｑｊの属性を削除して処理を終える。アンカ点の候補が隣接しない座標点であった場合はそのまま処理を終える。Ｓ１３５３にて着目アンカ点候補Ｑｊの属性が「屈曲点」でなかった場合、Ｓ１３５６へ遷移する。
【００３７】
Ｓ１３５６では、着目アンカ点候補Ｑｊの属性が「頂点」か否かを判定する。着目アンカ点候補Ｑｊの属性が「頂点」であった場合、Ｓ１３５７へ遷移し、着目アンカ点候補よりも優先度の高い属性を有するアンカ点候補が、当該着目アンカ点候補Ｑｊに隣接する参照点Ｑｊ−１、Ｑｊ＋１双方に存在するか否かを判定する。そして参照点Ｑｊ−１、Ｑｊ＋１双方に着目アンカ点候補Ｑｊよりも高い優先度の属性を有するアンカ点候補が存在した場合はＳ１３５８へ遷移し、着目アンカ点候補Ｑｊの属性と座標を削除し、処理を終える。隣接する参照点Ｑｊ−１、Ｑｊ＋１双方にアンカ点候補が存在しない場合はそのまま処理を終える。
【００３８】
Ｓ１３５６にて着目アンカ点候補Ｑｊの属性が「頂点」でなかった場合、Ｓ１３５９へ遷移する。Ｓ１３５９では、着目アンカ点候補Ｑｊの属性が「直線保持点」か否かを判定する。着目アンカ点候補Ｑｊの属性が「直線保持点」であった場合、必ず参照点Ｑｊ＋１は同じ「直線保持点」となる。よって次にＳ１３５１０へ遷移し、着目アンカ点候補よりも優先度の高い属性を有するアンカ点候補が参照点Ｑｊ−１、Ｑｊ＋２双方に存在するか否かを判定する。そして参照点Ｑｊ−１、Ｑｊ＋２双方に着目アンカ点候補よりも優先度の高い属性を有するアンカ点候補が存在した場合はＳ１３５１１へ遷移し、参照点Ｑｊ＋１に存在するアンカ点候補と、着目アンカ点候補Ｑｊの属性と座標を削除し、処理を終える。参照点Ｑｊ−１、Ｑｊ＋２双方にアンカ点候補が存在しない場合はそのまま処理を終える。着目アンカ点候補Ｑｊの属性が「直線保持点」でなかった場合、処理を終える。
【００３９】
ここまでで着目アンカ点候補を削除するか否かの判定を終えた。次にＳ１３６で、現在の着目点が追跡している座標点列の終点であるか否かを判定する。すなわち、すべてのアンカ点候補に対して本処理を適用したか否かを判定する。終点ではないと判定された場合は、Ｓ１３７で着目アンカ点候補を座標点列上における次のアンカ点候補に移し、再度Ｓ１３２へ遷移する。現在の着目アンカ点候補が終点であると判定された時はアンカ点決定処理を終える。以上の処理は図３におけるアンカ点決定手段１３００を実現している。また、Ｓ１２０とＳ１３０は、合わせてアンカ点情報抽出手段２００を実現している。
【００４０】
［アンカ点候補属性の目的と優先順位］
ここで、各アンカ点候補属性の目的と優先順位の理由について説明する。まず、「端点」は開輪郭における始端、及び終端を意味し、先にも述べたとおり近似処理を終えた後この点を基準に各座標点列をつなぎ合わせるので、削減は行わず、また優先順位の比較対象外とする。
【００４１】
次に「折点」は入力画像の座標点列における角張った部分を表現することを目的としている。「折点」画像において特徴的な点であり、削減による視覚的な変化はいずれのパターンでも大きい。このことからアンカ点候補中、１位の優先順位とし、削減は行わないこととする。
【００４２】
次に「直線保持点」は入力画像の座標点列におけるｘ方向、ｙ方向における直線部分の表現を目的としている。このため「直線保持点」は必ず２点隣り合う形で抽出する。この点を削減した場合、直線が曲線となってしまう場合があるため視覚的な変化が大きい。しかし、２点の「直線保持点」を直近で囲む形で「折点」が存在する場合は、その目的から「直線保持点」を削減しても視覚的な劣化は起こらない。このことからアンカ点候補の優先順位は全属性中、２位としている。
【００４３】
次に「頂点」は入力画像の座標点列におけるエッジや曲線の極値点を表現することを目的としている。このため「頂点」は削減することによる視覚的な変化が大きい。しかし、「頂点」を直近で囲む形で「折点」や「直線保持点」が存在する場合、「頂点」を削減しても視覚的な劣化は起こらない。このことからアンカ点候補の優先順位は全属性中、３位としている。
【００４４】
次に「屈曲点」は入力画像の座標点列における急峻な角度の変化を表現することを目的としている。しかし本実施形態における屈曲点の抽出は、着目点前後の角度のみを参照して判定を行っているため、入力画像に不規則なパターンが存在した場合過剰に抽出してしまう。また画像中の角度変化が大きい点を抽出しているため、削減した場合の影響は大きいものの、「頂点」や「折点」などの画像における代表的な特徴部に直近で存在した場合は削減を行っても画像の変化は目立たちにくい。このことからアンカ点候補の優先順位は全属性中、４位としている。
【００４５】
最後に「変曲点」は入力画像の座標点列において傾き変化量が入れ替わった点で近似区間を区切ることで、複雑なパターンの近似区間をなくすことを目的としている。しかし本実施形態における変曲点の抽出は、局所領域のみを参照して判定を行っているため、入力画像に不規則なパターンが存在した場合過剰に抽出してしまう。また、変曲点は曲線の途中に存在する点であり、他の属性のような特徴的な点を抽出した点ではないため、削減した場合の変化は視覚的に目立ちにくい。このことから、アンカ点候補の優先順位は全属性中、５位としている。
【００４６】
なお、アンカ点に付加される属性は、ここで挙げられたものに限定されるわけではなく、さらに細かく定義してもよい。また、処理を行う画像の特性に合わせて、上記の属性の一部のみを用いて処理を行ってもよい。
【００４７】
［コントロール点決定処理］
次にＳ１４０、Ｓ１５０で行うコントロール点決定処理について説明する。この処理では特許文献１で開示されている手法を適用することができる。すなわち、図１６に示すように、コントロール点ｃ１、ｃ２間を結ぶ線分ｃ１ｃ２は、アンカ点ａ１、ａ２を結ぶ線分ａ１ａ２と平行であると仮定する。そして線分ａ１ａ２から最も距離が離れた座標点列上の点Ｐｆと線分ａ１ａ２との距離をＤｆ、線分ａ１ａ２と線分ｃ１ｃ２との距離をＤｃとすると、Ｄｃ＝４／３Ｄｆの関係が成り立つゆえ、線分ｃ１ｃ２が一意に定まる。そして、アンカ点ａ１、ａ２における接線をそれぞれ決定し、接線方向と線分ｃ１ｃ２との交点をコントロール点ｃ１、ｃ２として一意に定める。このとき各アンカ点における接線方向は、Ｓ１４０の、接線方向決定処理によって行う。接線方向は３次ベジェ曲線で近似する上で、曲率を司る。このため各アンカ点において、アンカ点間で区切られた区間の座標点形状を鑑みて接線方向を決定する必要がある。本発明においてはこの接線方向の決定に、アンカ点候補情報抽出時に得た属性を利用して簡易に行うことを実現している。ここで、Ｓ１３０のアンカ点決定処理で得た座標点列をＲｋ（ｋ＝１，２，…ｌ）とし、座標点列追跡方向と逆方向の座標点をＲｋ−１、Ｒｋ−２…とし、座標点列追跡方向と順方向の座標点をＲｋ＋１、Ｒｋ＋２…と呼称することとする。
【００４８】
［接線方向決定処理］
図１７は、ＣＰＵ７によって実行される、Ｓ１４０で行われる接線方向決定処理の詳細なフローである。まずＳ１４１で接線方向を決定する対象となるアンカ点の属性を参照し、属性が「直線保持点」、もしくは「折点」であるか否かを判定する。アンカ点の属性が「直線保持点」、もしくは「折点」であった場合には、Ｓ１４２へ遷移し、それぞれ図１８（ｃ）、図１８（ｂ）で示したように、隣接する座標点Ｒｋ−１、Ｒｋ＋１の方向を接線方向とし、処理を終える。Ｓ１４１にて属性が「直線保持点」、もしくは「折点」でなかった場合にはＳ１４３へ遷移する。Ｓ１４３では、属性が「変曲点」であるか否かを判定する。属性が「変曲点」であった場合には、Ｓ１４４へ遷移し、図１８（ｆ）で示したように、アンカ点Ｒｋの前後２点先の座標点Ｒｋ−２、Ｒｋ＋２を結ぶ直線の傾きを求め、求めた傾きの平均を算出する。このとき傾きの平均は、閾値Ｔ６以内とする誤差の範囲内（第一の誤差）であっても良い。そして算出した傾きの平均に基づき、互いに向きが逆行する方向を接線方向とし、処理を終える。このとき互いの向きは正確に１８０度（すなわち、それぞれの接線が正反対の方向を向いている）としてもよいし、閾値Ｔ７以内とする誤差の範囲内（第二の誤差）であっても良い。。またここで言う閾値Ｔ６、Ｔ７の一例としてはＴ６＝０．１、Ｔ７＝１．０等を定義しうる。Ｓ１４３にて属性が「変曲点」でなかった場合にはＳ１４５へ遷移する。Ｓ１４５では接線方向を決定する対象となるアンカ点の前後二点先の座標点Ｒｋ−２、Ｒｋ＋２の方向を接線方向とし、処理を終える。以上の処理により、図３における接線方向決定手段１４００を実現している。
【００４９】
［接線方向］
ここで、各属性における接線方向について説明する。まず「折点」は入力画像の座標点列の角張った部分を表現するため、「折点」前後の近似区間で直交するように接線方向を取るのが好ましい。このことから、図１８（ｂ）に示したように「折点」に隣接する座標点の方向をそれぞれ接線方向とすれば接線方向を直交とすることができ、角張った表現が可能となる。
【００５０】
次に「直線保持点」は入力画像の座標点列の直線部分を保持しつつ隣接する近似区間に滑らかに接続するため「直線保持点」前後の接線方向は並行でかつ逆行する方向に取るのが好ましい。このことから図１８（ｃ）に示したように「直線保持点」に隣接する座標点の方向を接線方向とすれば、平行かつ逆行する形で接線方向を取ることができ、これにより直線を保持しつつ、滑らかに隣接する近似区間とつなげることが可能となる。
【００５１】
次に「頂点」は入力画像の座標点列のエッジや緩やかな曲線の極値点を表現するため、接線方向は「頂点」前後の近似区間における曲率を鑑みた方向であるのが好ましい。このことから図１８（ｄ）に示したように前後二点先の座標点の方向を接線方向とすれば、緩やかな「頂点」は緩やかな接線方向をとりつつ、急峻な「頂点」は急峻な角度の接線方向を取ることができ、緩やかな極点と急峻なエッジを表現することが可能となる。
【００５２】
次に「屈曲点」は入力画像の座標点列における角度の急峻な変化を表現するため、「屈曲点」前後の近似区間の曲率の変化を鑑みた接線方向であることが好ましい。このことから図１８（ｅ）に示したように前後二点先の座標点の方向を接線方向とすれば、「屈曲点」前後の近似区間で別々に接線方向を取ることができ、かつ曲率の変化を加味できるので急峻な角度の変化を表現することができる。
【００５３】
次に「変曲点」は曲線の途中で傾き変化量の正負が変化した点を取るため、前後の近似区間では接線方向を平行でかつ逆行する方向にとり、滑らかに接続するのが好ましい。このことから図１８（ｆ）に示したように前後二点先の座標点の方向をそれぞれ算出し、それらの傾きの平均となる方向にそれぞれ接線方向を取ることで、接線方向を平行でかつ逆行する方向に取ることができ、滑らかに曲線を接続することができる。
【００５４】
最後に「端点」は前後どちらかの座標点が存在しないゆえ、前後の近似区間の接続を鑑みなくてもよい。このため図１８（ａ）に示したように座標点が存在する座標点列状の二点先の座標点の方向を接線方向としておくことで、近似区間となる座標点列の曲率に準じた接線方向を取ることができる。
【００５５】
［コントロール点座標算出処理］
以上まででアンカ点における接線方向の決定ができた。次にＳ１５０でコントロール点座標算出処理を行う。ここではまず、アンカ点で分割された区間における座標点列に対し、アンカ点間を結ぶ線分ａ１ａ２から最も距離が離れた座標点Ｐｆを検索する。そして検出した座標点Ｐｆと線分ａ１ａ２までの距離Ｄｆを求める。この距離Ｄｆに基づき、線分ａ１ａ２に平行であり、かつ線分ａ１ａ２から距離Ｄｃ＝４／３×Ｄｆ離れた線分ｃ１ｃ２を導出する。そして導出した線分ｃ１ｃ２に対し、Ｓ１４０で決定した各アンカ点の接線方向との交点をコントロール点として決定する。このとき、アンカ点ａ１、ａ２間に他の座標点が存在しない、二つのアンカ点の接線方向が互いに逆行している、もしくは線分ａ１ａ２の長さを距離Ｄｆで除算した値が閾値Ｔ５以下である場合、該当区間は直線部であるとしコントロール点は出力しない。本実施形態において閾値Ｔ５＝３０とする。以上の処理により、図３におけるコントロール点座標算出手段１５００を実現している。また、Ｓ１４０とＳ１５０とによりコントロール点座標決定手段３００を実現している。
【００５６】
最後にＳ１６０では生成したデータを、同一の座標を有する「端点」同士を結合し、ベクトルデータとして出力する。この処理により、図３におけるデータ出力手段４００を実現している。以上の処理を行うことにより、最終的に図２６に示したベクトルデータが得られる。
【００５７】
＜実施形態２＞
実施形態１では、アンカ点決定処理において、着目アンカ点候補の前後の座標点二点以内に他のアンカ点候補が存在した場合に削減処理を行った。しかし、アンカ点候補に含まれる座標点数が３点以上離れている場合は、例え冗長なアンカ点候補が存在した場合でも削減することはできない。そこで本実施形態では、隣接するアンカ点候補の優先順位を比較し、その上で削減処理を行う。また、アンカ点候補同士を比較して削減を行った場合、削減した結果をアンカ点候補情報に上書きし、上書きした結果における隣接アンカ点候補を再度判定していくこととしている。このことにより、より広い範囲での削減処理が可能となり、データ量の削減に寄与することができる。
【００５８】
図１９は、ＣＰＵ７によって実行される本実施形態の処理フローである。まず、座標点列を追跡し、Ｓ２３１で初めのアンカ点候補を第一アンカ点候補として抽出する。次にＳ２３２で第一アンカ点候補からさらに座標点列を追跡し、次に検出されたアンカ点候補を第二アンカ点候補とする。次にＳ２３３で第一アンカ点候補と第二アンカ点候補が有する属性の優先順位の比較を行う。第二アンカ点候補の優先順位が低かった場合はＳ２３４へ遷移する。Ｓ２３４では第一アンカ点候補と第二アンカ点候補で区切られた区間の座標点列の形状を判定する。ここで形状を判定する要素として、例えば、座標点列の角度、長さ、座標点数、削減したアンカ点候補の数などが挙げられる。ここで削減を行うと判定された場合は、Ｓ２３６へ遷移し、第二アンカ点候補を削減してＳ２３２に戻る。削減を行わないと判定された場合、Ｓ２３８へ遷移する。
【００５９】
Ｓ２３３で第一アンカ点候補の優先順位が低かった、もしくは同一であった場合はＳ２３５へ遷移する。Ｓ２３５ではＳ２３４と同様に第一アンカ点候補と第二アンカ点候補で区切られた区間の座標点列の形状を判定する。ここで形状を判定する要素として、例えば、座標点列の角度、長さ、座標点数、削減したアンカ点候補の数などが挙げられる。ここで削減を行うと判定された場合は、Ｓ２３７へ遷移し、第一アンカ点候補を削減し、その後Ｓ２３８へ遷移する。また削減を行わないと判定された場合、Ｓ２３８へ遷移する。Ｓ２３８では現在第二アンカ点候補として着目している点を第一アンカ点候補とし、Ｓ２３２へ戻る。
【００６０】
以上の処理を、処理した座標点数が開輪郭、閉輪郭における総座標点数となるまで行う。この処理により座標点列の追跡方向に従って、次々にアンカ点候補を比較していくことができ、アンカ点候補間の座標点数に制限されることのないアンカ点決定処理を実行することができる。
【００６１】
＜実施形態３＞
実施形態１では、アンカ点候補情報抽出処理において、前ステップで抽出した座標点列に対して図９に示したように追跡を行い、アンカ点候補情報を抽出した。こうした場合、「変曲点」や「屈曲点」のように角度の変化を用いて抽出を行う属性は、座標点列の角度を算出する必要があることから、図２０（ａ）に示したように、一点おきに判定を行うようにしている。
【００６２】
しかしこのとき、同じ座標点列でも図２０（ａ）の座標点１を判定する場合と図２０（ａ）の座標点２を判定する場合では異なる抽出結果が得られてしまい、２つの場合で最終的な近似結果が一致しないことがある。これに対応するため、実施形態１における図４のＳ１２０のアンカ点候補情報抽出処理で、角度変化を用いてアンカ点候補情報の抽出を行う「変曲点」と「屈曲点」の判定を、図２０で示したような各座標点列間を結ぶ辺の中点を用いて行ってもよい。即ち、図１０のフローチャートで示した一連の処理フローを、図２２で示すフローチャートに沿って処理するように構成してもよい。尚、アンカ点候補情報抽出処理以外の処理は実施形態１と同様の処理を行えばよい。
【００６３】
ここでは、図２１に示すように現在着目している座標点列の点を着目点Ｐｉ（ｉ＝１，２，…ｎ）と呼称する。また、着目点Ｐｉから見て座標点列追跡方向と逆方向の座標点をＰｉ−１、Ｐｉ−２…とし、座標点列追跡方向と順方向の座標点をＰｉ＋１、Ｐｉ＋２…と呼称する。さらに座標点Ｐｉと座標点Ｐｉ＋１間を結ぶ辺の中点をＣｌ（ｌ＝１，２，…ｎ−１）と呼称する。そして、着目点Ｐｉから見て座標点列追跡方向と逆方向の座標点同士がなす中点をＣｌ−１、Ｃｌ−２…とし、座標点列追跡方向と順方向座標点同士がなす中点をＣｌ＋１、Ｃｌ＋２…と呼称することとする。
【００６４】
以下、本実施形態におけるアンカ点候補情報抽出処理の詳細を図２２に示すフローチャートを用いて述べる。まずＳ３２１で、追跡する座標点列の初期点を設定し、該当の座標点を着目点とする。次にＳ３２２では着目点Ｐｉ自身をアンカ点候補とすべきか否かを判定する。
【００６５】
図２３は、ＣＰＵ７によって実行される、着目点判定処理の詳細な処理フローである。まずＳ３２２１で着目点の端点判定を行う。この処理は実施形態１における図１１のＳ１２２１と同様のものでよい。端点と判定された場合は、Ｓ３２２２へ遷移し、その着目点Ｐｉ自身の座標と、「端点」という属性を保持して、処理を終える。Ｓ３２２１で端点でないと判定された場合は、Ｓ３２２３の折点判定へ遷移する。この処理は実施形態１における図１１のＳ１２２３と同様のものでよい。折点と判定された場合は、Ｓ３２２２に移り、その着目点Ｐｉ自身の座標と、「折点」という属性を保持し、処理を終える。Ｓ３２２３で折点でないと判定された場合は、Ｓ３２２４へ遷移する。そして、着目点Ｐｉ自身の座標のみを保持し、そのまま処理を終える。
【００６６】
ここまでの処理により、Ｓ３２２の着目点Ｐｉ自身のアンカ点候補判定は終えた。次に、図２２において、着目辺ＰｉＰｉ＋１上にアンカ点候補を取るべきか否かを判定するＳ３２３へ遷移する。図２４は、ＣＰＵ７によって実行される、着目辺判定処理の詳細な処理フローである。まずＳ３２３１で着目辺ＰｉＰｉ＋１が直線保持辺か否かを判定する。この処理は実施形態１における図１２のＳ１２３１と同様のものでよい。着目辺ＰｉＰｉ＋１が直線保持辺であると判定された場合、Ｓ３２３２へ遷移する。そして、実施形態１と同様に座標を２点取り、その属性を「直線保持点」として保持し、処理を終える。
【００６７】
Ｓ３２３１で着目辺ＰｉＰｉ＋１が直線保持辺でないと判定された場合は、Ｓ３２３３の頂点を含む辺判定へ遷移する。この処理は実施形態１における図１２のＳ１２３３と同様のものでよい。着目辺ＰｉＰｉ＋１が頂点を含む辺であると判定された場合、Ｓ３２３４へ遷移する。そして、線分ＰｉＰｉ＋１の中点座標と、属性「頂点」を保持し、処理を終える。Ｓ３２３３で着目辺ＰｉＰｉ＋１が頂点を含む辺でないと判定された場合は、Ｓ３２３５の屈曲点を含む辺判定へ遷移する。屈曲点を含む辺を判定するために、まず図２５（ａ）に示したように着目辺ＰｉＰｉ＋１の中点座標Ｃｌと、辺Ｐｉ−１Ｐｉの中点座標Ｃｌ−１と、辺ＰｉＰｉ＋１の中点座標Ｃｌ＋１を参照点とし、線分Ｃｌ−１Ｃｌと、線分ＣｌＣｌ＋１とがなす角度θを算出する。そして、角度θが閾値Ｔ８以上となる辺を屈曲点を含む辺とする。本実施形態では閾値Ｔ８＝２５°としている。着目辺ＰｉＰｉ＋１が屈曲点を含む辺であると判定された場合、Ｓ３２３４へ遷移する。そして、線分ＰｉＰｉ＋１の中点座標Ｃｌと、属性「屈曲点」を保持し、処理を終える。
【００６８】
Ｓ３２３５で着目辺ＰｉＰｉ＋１が屈曲点を含む辺でないと判定された場合は、Ｓ３２３６の変曲点を含む辺判定へ遷移する。変曲点を含む辺を判定するために、まず図２５（ｂ）に示したように、着目辺ＰｉＰｉ＋１の中点座標Ｃｌと、辺Ｐｉ−１Ｐｉの中点座標Ｃｌ−１と、辺Ｐｉ−２Ｐｉ−１の中点座標Ｃｌ−２と、辺ＰｉＰｉ＋１の中点座標Ｃｌ＋１を参照点とする。そして、線分Ｃｌ−２Ｃｌ−１の傾きαと、線分Ｃｌ−１Ｃｌの傾きβと、線分ＣｌＣｌ＋１の傾きγを算出する。そして、傾きの変化量となるβ‐α、γ‐βを算出し、この傾きの変化量同士の正負が入れ替わる点を変曲点とする。ただし、傾きの変化量β‐αの絶対値が閾値Ｔ９以下となる場合は、β‐αの絶対値が閾値Ｔ９以上の値を取るまで傾きαをとる線分をＣｌ−３Ｃｌ−２、Ｃｌ−４Ｃｌ−３…と遡らせて判定を行う。本実施形態では閾値Ｔ９＝１．０×１０−７としている。着目辺ＰｉＰｉ＋１が変曲点を含む辺であると判定された場合、Ｓ３２３４へ遷移する。そして、線分ＰｉＰｉ＋１の中点座標Ｃｌと、属性「変曲点」を保持し、処理を終える。Ｓ３２３６で着目辺ＰｉＰｉ＋１が変曲点を含む辺でないと判定された場合は、そのまま処理を終える。
【００６９】
ここまででＳ３２３の着目辺ＰｉＰｉ＋１のアンカ点候補判定は終えた。次に図２２におけるＳ３２４で、現在の着目点が追跡している座標点列の終点であるか否かを判定する。終点ではないと判定された場合は、Ｓ３２５で着目点を座標点列上における次の点に移し、再度Ｓ３２２へ移る。終点であると判定された時はアンカ点候補情報抽出処理を終える。
【００７０】
上記の処理をアンカ点候補情報抽出処理として実施することで、角度の変化を用いて抽出する変曲点や屈曲点を、着目点の偶数点目か奇数点目かという判定を必要とせず、入力した座標点列に一対一で対応したアンカ点抽出結果を得ることができる。
【００７１】
＜実施形態４＞
実施形態１では、アンカ点候補情報抽出処理において、アンカ点決定処理における優先順位の高いものから順番に抽出を行い、抽出したアンカ点候補は一意に決定された属性を保持していた。しかし、複数の属性の性質を持つ点の場合、重複して属性を保持してもよい。例えば、「屈曲点」と「変曲点」の属性を有する場合は優先順位を上げ、接線方向は「変曲点」の場合と同様とする、などその重複属性の組み合わせによって優先順位や接線方向の取り方を変えることで、さらに精度の高いベクトル化を実現することができる。
【００７２】
＜その他の実施形態＞
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【技術分野】
【０００１】
本発明は画像処理技術に関するものであり、特にラスタ画像から特徴点を抽出し、関数近似を行うことでベクタ画像へ変換を行う画像処理技術に関する。
【背景技術】
【０００２】
近年、ディスプレイや印刷機器など解像度の異なる機器の混在化が進み、一つの画像情報を異なる解像度で表示する機会が増えてきている。ところが低解像度機器に適した画像を高解像度機器で表示しようとすると、機器の解像度を生かすことができず画質の劣化が目立ってしまう。このことからラスタ形式で表現された画像を、解像度に依存しないベクタ形式へ変換する、ベクトル化技術が必要となってきている。
【０００３】
ベクトル化技術の検討は以前からも行われており、例えば、二値画像を対象としたベクトル化手法が特許文献１で開示されている。この手法は二値画像の輪郭を、以下の条件を満たす点で分割し、分割区間に対してそれぞれベジェ曲線で近似を行う。
【０００４】
角点１：隣接する点列を結ぶベクトルの変化が鋭角となる点
角点２：連続する点と点との距離がある閾値より大きい場合の両端の点
変曲点：連続するベクトルの外積の符号が変化する点
座標点列の抽出処理として、例えば、特許文献２のような手法が開示されている。この手法によれば注目画素とその近傍画素の状態に基づいて、水平方向及び垂直方向の画素間ベクトルを検出し、これら画素間ベクトル同士の接続状態を判別して、画素間ベクトルの接続状態から画像データの座標点列を抽出するように動作する。画素の中心位置ではなく、画素の縁単位に座標点列を抽出することにより、１画素幅の細線に対しても有為な幅を持たせることが出来る座標点列抽出法である。
【０００５】
また２値画像のみならず、数色に及ぶ線画やイラスト画像を対象としたベクトル化手法が例えば、特許文献３で開示されている。この手法は、色領域間で共通な境界線を抽出し、関数近似を行うという処理フローで原理的に隙間が生じないカラー画像のベクトル化を実現している。ここでの座標点列抽出手法は特許文献２とは異なり、隣接する画素間で色が閾値以上異なる線を追跡することで抽出している。抽出後の座標点列から色領域間で共通する境界線を求め、色領域を出力する際に共通の関数近似結果を適用し、ベクトル化を行う。
【０００６】
また、近似処理を行う際、近似区間とのつながりを平滑にする近似手法として、例えば、特許文献４で開示されている。曲線式Ａで表現された複数の区間を統合し、その統合した区間をより高次の曲線式Ｂで近似し、表現することでデータ削減と文字輪郭線の滑らかさを維持・改善する手法である。この中で、統合した区間を分割点で区切り、区切られた区間を曲線式Ｂで近似を行っている。しかし区切られた区間で独立して近似を行うと、分割点の前後で滑らかさが失われてしまうので、２つの曲線が共通接線を持つように制御点の位置を修正することで、分割点前後での滑らかさを保持する手法を開示している。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００５−３１００７０号公報
【特許文献２】特許第３０２６５９２号
【特許文献３】特開２００６−０３１２４５号公報
【特許文献４】特開平０４−１１６６９０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら従来技術では近似処理を行う際に分割点前後で接線方向を揃えるか否かという判定は行っていなかった。このことから接線方向を揃える場合、全ての分割点で揃える処理を行うため、図１（ａ）を入力画像とすると図１（ｂ）に示すようにエッジ部が丸まってしまう。接線方向を揃えなかった場合は、全ての区間で独立して近似するため分割点での連続性は保証されず、図１（ｃ）に示すように曲線の途中角張ってしまう結果となる。
【０００９】
これを防止するには、接線方向を揃える区間とそうでない区間を適応的に判定すればよい。しかし、分割点を決定した後、接線方向を決定する段階で判定しようとすると、都度傾きの変化量を計算する必要があるため、前後数辺分の参照が再度必要となり、処理が複雑化する。
【課題を解決するための手段】
【００１０】
上記課題を解決するために、本発明に係る画像処理装置は以下の構成を備える。画像データの形状を表現する座標点列から、アンカ点を抽出するために予め定められた複数の抽出ルールに基づき、アンカ点の座標と当該アンカ点が予め定められた複数の属性のいずれに属するかとを決定し、前記アンカ点の座標と当該アンカ点の属性を含む情報を出力するアンカ点情報抽出手段と、着目アンカ点の前記属性および前記着目アンカ点から所定の範囲にあるアンカ点の座標に応じて前記着目アンカ点における接線方向を決定する接線方向決定手段と、前記着目アンカ点の接線方向及び座標からコントロール点座標を算出するコントロール点座標算出手段と、前記アンカ点の座標と前記コントロール点座標とを含む情報を出力するデータ出力手段とを有する。
【発明の効果】
【００１１】
本発明によれば、変曲点の接線方向を適応的に判定して決定する場合であっても、処理を複雑化せずに簡易に行うことができる。
【図面の簡単な説明】
【００１２】
【図１】接線方向をそろえるか否かの違いによるベクトル化結果を示す図。
【図２】本発明に係る画像処理装置のブロック構成図。
【図３】本発明に係る画像処理装置のメイン処理ブロック構成図。
【図４】実施形態１に係る画像処理装置のメイン処理を示すフローチャートの図。
【図５】二値画像における一画素と一画素より生成される座標点を示す図。
【図６】二値画像と二値画像より生成される座標点列例を示す図。
【図７】多値画像と多値画像より生成される座標点列例を示す図。
【図８】ベジェ曲線の概念を示す図。
【図９】着目点と周辺の座標点を示す図。
【図１０】実施形態１に係るアンカ点候補情報抽出処理を示すフローチャートの図。
【図１１】実施形態１に係るアンカ点候補判定処理を示すフローチャートの図。
【図１２】実施形態１に係るアンカ点候補判定処理を示すフローチャートの図。
【図１３】実施形態１に係るアンカ点候補情報抽出ルールの例を示す図。
【図１４】実施形態１に係るアンカ点決定処理を示すフローチャートの図。
【図１５】実施形態１に係る削減処理を示すフローチャートの図。
【図１６】実施形態１に係るコントロール点座標決定処理に関する説明図。
【図１７】実施形態１に係る接線方向決定処理を示すフローチャートの図。
【図１８】実施形態１に係る接線方向決定処理における接線方向例を示す図。
【図１９】実施形態２に係るアンカ点決定処理を示すフローチャートの図。
【図２０】実施形態１と実施形態３に係る座標点追跡の違いを示す図。
【図２１】実施形態３に係る着目点と周辺の座標点と中点を示す図。
【図２２】実施形態３に係るアンカ点候補情報抽出処理を示すフローチャートの図。
【図２３】実施形態３に係るアンカ点候補判定処理を示すフローチャートの図。
【図２４】実施形態３に係るアンカ点候補判定処理を示すフローチャートの図。
【図２５】実施形態３に係る屈曲点と変曲点の抽出ルールの例を示す図。
【図２６】入力画像と本発明を適用した際に得られるベクトル化結果を示す図。
【発明を実施するための形態】
【００１３】
＜実施形態１＞
以下、添付の図面を参照して本発明の実施の形態を説明する。ただし、この実施の形態に記載されている構成要素はあくまで例示であり、本発明の技術的範囲は、特許請求の範囲によって確定されるのであって、以下の個別の実施形態によって限定されるわけではない。
【００１４】
本実施形態の画像処理装置の構成例について、図２のブロック図を参照して説明する。図２において、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）７は装置全体を制御する。なお、以下に示す各処理フローは、特段の記載が無い限り、ＣＰＵ７によって実行される。ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）６は変更を必要としないプログラムやパラメータを格納する。ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）５は外部装置等から供給されるプログラムやデータを一時記憶する。スキャナ１は、文書等を光電走査して電子的な画像データを取得し、画像入出力Ｉ／Ｏ３はスキャナ１と画像処理装置を接続する。画像メモリ２は、スキャナ１で読み取られた画像データ等を保持する。外部記憶装置１２は固定して設置されたハードディスクやメモリカード、あるいは着脱可能なフレキシブルディスク（ＦＤ）やＣｏｍｐａｃｔ Ｄｉｓｋ（ＣＤ）等の光ディスク、磁気や光カード、ＩＣカード、メモリカード等のプログラム記憶媒体を含む。また、Ｉ／Ｏ１３はこれら外部記憶装置１２とコンピュータ装置との入出力を行う。Ｉ／Ｏ１５はユーザの操作を受け、データを入力するマウス等のポインティングデバイス１０やキーボード９等の入力デバイスとの入出力を行う。映像Ｉ／Ｏ１４は画像処理装置の保持するデータや供給されたデータを表示するためのディスプレイモニタ８との入出力を行う。通信Ｉ／Ｆ４は、インターネット等のネットワーク回線に接続するためのインタフェースである。システムバス１１は上述した各ユニットを通信可能に接続する。
【００１５】
［処理フロー］
以下、ＣＰＵ７上で実行されるプログラムにより本願発明を実現する処理手順を、図３のブロック図と図４のフローチャートを用いて説明する。
【００１６】
図４のフローチャートにおいて、Ｓ１００で処理を開始すると、処理対象となる画像領域を含む画像データを入力する。画像入力に関しては、スキャナ１にて読み取られた画像データを画像入出力Ｉ／Ｏ３を介して画像メモリ２に入力する。また、通信Ｉ／Ｆ４を介して、装置外部より処理対象となる画像領域を含む画像を入力してもよく、あるいは、外部記憶装置１２に予め記憶される画像データをＩ／Ｏ１３を介して読み込むものであってもよい。得られた入力画像データは、画像メモリ２上に保持される。以上の処理は図３における画像入力手段１０００を実現している。
【００１７】
次に読み取った画像データに対してＳ１１０で座標点列抽出処理を行う。ここで扱う画像データに含まれる１つの黒画素を図５に示す。図５で示すように、画像データにおける１画素は、４つの頂点を有し、垂直方向の向きを示す垂直ベクトルと水平方向の向きを示す水平ベクトルより構成される正方形として扱う。１画素を４つの頂点を有する正方形として扱い、複数の画素の集合である画像データのアウトラインを抽出すると、水平ベクトルと垂直ベクトルからなる座標点列がアウトラインデータとして得られる。このような座標点列の抽出方法は、種々提案されており、特に特許文献２で開示されている座標点列抽出方法を用いれば、画像一面より効率良くかつ高速に座標点列を抽出することが可能である。例えば、図６（ａ）で示す画像から抽出された座標点列は、図６（ｂ）に示すような、水平ベクトル、垂直ベクトルが交互に並ぶ構成となる座標点列となる。すなわち、座標点とは、水平ベクトル、または垂直ベクトルの方向が変化する点を意味する。
【００１８】
またこのとき、読み取った画像データが複数色に及ぶ場合は、特許文献３に記載されている座標点列追跡法を適用することができる。即ち、図７（ａ）に示したように、３色以上の色領域の交点が存在した時、交点において座標点列の分割を行い、図７（ｂ）で示したようにそれぞれを異なる座標点列として抽出する手法である。図７（ｂ）は、４つの座標点列が得られた場合の例である。本実施形態では座標点列を追跡した結果、始点と終点が同一の座標となるような座標点列を閉輪郭、始点と終点が異なった座標となる座標点列を開輪郭と呼称する。以上の処理は図３における座標点列抽出手段１１００を実現している。また、Ｓ１００とＳ１１０は合わせて図３における座標点列入力手段１００を実現している。
【００１９】
次にＳ１２０、Ｓ１３０、Ｓ１４０、Ｓ１５０では抽出した座標点列に対して関数近似処理を行う。本実施形態では置き換える関数として、３次ベジェ曲線を用いる。３次ベジェ曲線は図８に示すとおり、２つのアンカ点と２つのコントロール点から構成され、以下の式によって定義される。このとき図８において、黒丸はアンカ点ａ１，ａ２を、白丸はコントロール点ｃ１，ｃ２をそれぞれ示す。またｔは媒介変数であり０≦ｔ≦１とする。
【００２０】
よって３次ベジェ曲線を用いて関数近似を行うには、Ｓ１１０で得た座標点列を適切に区切るアンカ点の決定と、その間を構成する座標点列の形状を適切に近似するコントロール点の決定が必要となる。以下から本実施形態における関数近似処理のフローを説明する。
【００２１】
まずＳ１２０ではアンカ点候補情報抽出処理を行う。ここでは、Ｓ１１０で抽出した座標点列において着目している点と、その近傍の座標点のなすパターンが、あらかじめ定められた複数の抽出ルールで規約済みのパターンであった場合に、当該着目点をアンカ点の候補としアンカ点候補情報を出力する。Ｓ１２０では、図９に示すように現在着目している座標点列の点を着目点Ｐｉ（ｉ＝１，２，…ｎ）とし、着目点Ｐｉから見て座標点列追跡方向と逆方向の座標点をＰｉ−１、Ｐｉ−２…とし、座標点列追跡方向と順方向の座標点をＰｉ＋１、Ｐｉ＋２…とする。また、アンカ点候補情報とは、アンカ点の候補として抽出した座標と、その着目点Ｐｉ近傍のパターン特性を示す属性を指す。
【００２２】
図１０は、ＣＰＵ７によって実行される、Ｓ１２０で行われるアンカ点候補情報抽出処理のフローである。まずＳ１２１で、追跡する座標点列の初期点を設定し、該当の座標点を着目点とする。次にＳ１２２では着目点Ｐｉ自身をアンカ点候補とすべきか否かを判定する。
【００２３】
なお、本発明において、複数の閾値を用いて判定等を行っているが、閾値の設定に関しては、実験的に導いてもよいし、所定の式等に基づいて決定してもよい。また、閾値以上、閾値以内と記載している箇所があるが、設定した閾値の特性や必要に応じて、判定条件は調整してもよい（例えば、閾値より小さい、など）。
【００２４】
［着目点判定処理］
図１１は、ＣＰＵ７によって実行される、着目点判定処理の詳細な処理フローである。まずＳ１２２１で着目点の端点判定を行う。端点は図１３（ａ）に示したように開輪郭の着目座標点Ｐｉに対し、前、もしくは後に座標点が存在しない点である。端点と判定された場合は、Ｓ１２２２に遷移し、その着目点Ｐｉ自身の座標と、「端点」という属性を保持し、処理を終える。
【００２５】
Ｓ１２２１にて端点でないと判定された場合は、Ｓ１２２３の折点判定に遷移する。折点は図１３（ｂ）に示したように座標Ｐｉ−１、Ｐｉ＋１を参照点とし、着目点Ｐｉと参照点Ｐｉ−１、Ｐｉ＋１それぞれとがなす辺Ｐｉ−１Ｐｉと辺ＰｉＰｉ＋１の長さが共に閾値Ｔ１以上となる点とする。また、辺Ｐｉ−１Ｐｉと辺ＰｉＰｉ＋１は、向きが水平方向から垂直方向もしくは垂直方向から水平方向へ変化することとする。ここで言う辺の長さとは、座標間に内包される画素長を指す。このとき閾値Ｔ１は、一意に定めてもよいし、画像の大きさを加味して可変としてもよい。本実施形態ではＣを座標点列の外接矩形の外周の長さとして、閾値Ｔ１＝２＋Ｃ／３００としている。ただし、閾値Ｔ１は２≦Ｔ１≦６の範囲で限定をしている。折点と判定された場合は、Ｓ１２２２に遷移し、その着目点Ｐｉ自身の座標と、「折点」という属性を保持し、処理を終える。
【００２６】
Ｓ１２２３にて折点でないと判定された場合は、Ｓ１２２４に遷移する。Ｓ１２２４では現在着目している座標点が端点から数えて奇数点目か偶数点目かを判定する。すなわち、ｉが偶数か奇数かを判定する。ここで偶数点目であると判定された時はＳ１２２７へ遷移し、着目点Ｐｉ自身の座標のみを保持し、そのまま処理を終える。奇数点目と判定された場合はＳ１２２５へ遷移する。
【００２７】
Ｓ１２２５では屈曲点判定を行う。屈曲点は図１３（ｆ）に示したように座標Ｐｉ−２、Ｐｉ＋２を参照点とし、線分Ｐｉ−２Ｐｉと、線分ＰｉＰｉ＋２とがなす角度θを算出し、角度θが閾値Ｔ２以上となる点とする。本実施形態では閾値Ｔ２＝２５°としている。屈曲点と判定された場合は、Ｓ１２２２へ遷移し、その着目点Ｐｉ自身の座標と、「屈曲点」という属性を保持し、処理を終える。
【００２８】
Ｓ１２２５で屈曲点ではないと判定された場合は、Ｓ１２２６の変曲点判定へ遷移する。変曲点は図１３（ｇ）に示したように座標Ｐｉ−４、Ｐｉ−２、Ｐｉ＋２を参照点とし、線分Ｐｉ−４Ｐｉ−２の傾きαと、線分Ｐｉ−２Ｐｉの傾きβと、線分ＰｉＰｉ＋２の傾きγを算出する。そして、傾きの変化量となるβ‐α、γ‐βをそれぞれ算出し、この傾きの変化量同士の正負が入れ替わる点を変曲点とする。すなわち、傾きの変化量における連続したベクトル間において、その外積の符号が変化する点を変曲点とする。ただし、傾きの変化量β‐αの絶対値が閾値Ｔ３以下となる場合は、β‐αの絶対値が閾値Ｔ３以上の値を取るまで傾きαをとる線分をＰｉ−６Ｐｉ−４、Ｐｉ−８Ｐｉ−６…と遡らせて判定を行う。本実施形態では閾値Ｔ３＝１．０×１０−７としている。変曲点と判定された場合は、Ｓ１２２２へ遷移し、その着目点Ｐｉ自身の座標と、「変曲点」という属性を保持し、処理を終える。Ｓ１２２６で変曲点ではないと判定された場合は、Ｓ１２２７に移り、着目点Ｐｉ自身の座標のみを保持し、そのまま処理を終える。
【００２９】
［着目辺判定処理］
以上まででＳ１２２の着目点Ｐｉ自身のアンカ点候補判定は終えた。次に着目辺ＰｉＰｉ＋１上にアンカ点候補を取るべきか否かを判定するＳ１２３に移る。ここで、着目辺とは着目点Ｐｉと、その次に存在する座標点Ｐｉ＋１を結ぶ辺を指す。ここでアンカ点候補が抽出された場合は、その座標は着目辺上となるためＳ１１０で抽出した座標点列ＰｉＰｉ＋１の間に書き加える。図１２はその詳細な処理フローである。
【００３０】
まずＳ１２３１で着目辺ＰｉＰｉ＋１が直線保持辺か否かを判定する。直線保持辺は図１３（ｃ）、（ｄ）に示したように、判定するためにまず座標Ｐｉ−２、Ｐｉ−１、Ｐｉ＋１または座標Ｐｉ＋１、Ｐｉ＋２、Ｐｉ＋３を参照点とする。そして、ベクトルＰｉ−２Ｐｉ−１、ＰｉＰｉ＋１の長さ｜Ｐｉ−２Ｐｉ−１｜、｜ＰｉＰｉ＋１｜、またはベクトルＰｉＰｉ＋１、Ｐｉ＋２Ｐｉ＋３の長さ｜ＰｉＰｉ＋１｜、｜Ｐｉ＋２Ｐｉ＋３｜をそれぞれ算出する。そして、｜ＰｉＰｉ＋１｜が｜Ｐｉ−２Ｐｉ−１｜の閾値Ｔ４倍以上、または｜ＰｉＰｉ＋１｜が｜Ｐｉ＋２Ｐｉ＋３｜の閾値Ｔ４倍以上となり、かつ双方のベクトル方向が同一である辺を直線保持辺であるとする。つまり、直線保持辺は、近傍の辺に対し、一定の値以上の長さを有することとなる。直線保持辺であると判定された場合、Ｓ１２３２へ遷移する。そして、Ｔ５を閾値として、着目辺ＰｉＰｉ＋１上において、座標Ｐｉ、Ｐｉ＋１からそれぞれ距離｜ＰｉＰｉ＋１｜／Ｔ５だけ離れた位置にある点を２点決定し、その属性を「直線保持点」として保持し、処理を終える。このとき閾値Ｔ４、閾値Ｔ５は、所定の値として一意に定めてもよいし、画像の大きさを加味して可変としてもよい。本実施形態では閾値Ｔ４＝１０、閾値Ｔ５＝５としている。
【００３１】
Ｓ１２３１で着目辺ＰｉＰｉ＋１が直線保持辺でないと判定された場合は、Ｓ１２３３の頂点を含む辺判定の処理へ遷移する。頂点を含む辺は、図１３（ｅ）に示したように座標Ｐｉ−１、Ｐｉ＋１、Ｐｉ＋２を参照点とし、ベクトルＰｉ−１Ｐｉと、ベクトルＰｉ＋１Ｐｉ＋２の方向が逆行する辺であるとする。つまり、この例において、着目辺ＰｉＰｉ＋１が頂点を含む辺となる。着目辺ＰｉＰｉ＋１が頂点を含む辺であると判定された場合、Ｓ１２３４に移り、線分ＰｉＰｉ＋１の中点座標と、属性「頂点」を保持し、処理を終える。Ｓ１２３３で着目辺ＰｉＰｉ＋１が頂点を含む辺でないと判定された場合は、そのまま処理を終える。
【００３２】
以上まででＳ１２３の着目辺ＰｉＰｉ＋１のアンカ点候補判定は終えた。次にＳ１２４で、現在の着目点が追跡している座標点列の終点であるか否かを判定する。すなわち、すべての座標点に対し、アンカ点候補判定の処理が終了したか否かを判定する。終点ではないと判定された場合は、Ｓ１２５で着目点を座標点列上における次の座標点として、再度Ｓ１２２へ遷移する。終点であると判定された時はアンカ点候補情報抽出処理を終える。以上の処理は図３におけるアンカ点候補情報抽出手段１２００を実現している。
【００３３】
［アンカ点決定処理］
次に抽出したアンカ点候補情報に基づいてＳ１３０でアンカ点決定処理を行う。ここで、Ｓ１２０においてアンカ点候補として抽出された座標点列をＱｊ（ｊ＝１，２，…ｍ）と呼称する。そして着目点Ｑｊに対し、その前後の近傍の座標点Ｑｊ−２、Ｑｊ−１、Ｑｊ＋１、Ｑｊ＋２を参照点とする。そして、その参照点のうちいずれかにＳ１２０において抽出したアンカ点候補が２つ以上あった場合、各アンカ点候補の属性に応じて削減するか否かを決定する。またここでいう削減とは、Ｓ１２０でアンカ点候補として抽出した座標における属性を削除し、アンカ点候補ではない座標点の状態に戻すことを指す。ただし、属性「頂点」と「直線保持点」においては、Ｓ１２０で辺上に新たに書き加えた点であるので、削減する場合は元のＳ１１０で抽出した座標点列の状態に戻すために、属性だけでなく、その座標も削減することとする。
【００３４】
図１４は、ＣＰＵ７によって実行される、Ｓ１３０で行われるアンカ点決定処理の詳細なフローである。まずＳ１３１で、追跡する座標点列の初期点を設定し、該当の座標点を着目点Ｑｊとして、Ｓ１３２へ遷移する。Ｓ１３２では、着目点Ｑｊがアンカ点候補として抽出された点か否かを判定する。着目点Ｑｊがアンカ点候補として抽出された点でなかった場合は、Ｓ１３６へ遷移する。着目点Ｑｊがアンカ点候補として抽出された点であった時は、Ｓ１３３へ遷移する。Ｓ１３３では着目しているアンカ点候補Ｑｊに対し、前後の近傍の座標点が２点以内（Ｑｊ−２、Ｑｊ−１、Ｑｊ＋１、Ｑｊ＋２）である点を参照点とし、参照点内にアンカ点候補が存在するか否かを判定する。参照点内にアンカ点候補が存在しなかった場合は、Ｓ１３６へ遷移する。参照点内にアンカ点候補が存在した場合は、Ｓ１３４へ遷移する。
【００３５】
Ｓ１３４ではアンカ点候補同士の優先順位の比較を行う。ここで、アンカ点候補の優先順位は、アンカ点候補情報における属性に依存する。本実施形態ではアンカ点候補の優先順位を高いものから「折点」、「直線保持点」、「頂点」、「屈曲点」、「変曲点」とあらかじめ定義しておく。また「端点」は、近似処理を終えた後、各座標点列をつなぎ合わせる過程で必要な点であるため、例外として削減対象とはしない。着目アンカ点候補Ｑｊの優先順位が、参照点内に存在するアンカ点候補の優先順位よりも高い場合、Ｓ１３６へ移る。着目アンカ点候補Ｑｊの優先順位が、参照点内に存在するアンカ点候補の優先順位以下であった場合はＳ１３５に移る。
【００３６】
［削減処理］
Ｓ１３５ではアンカ点候補の削減処理を行う。すなわち、アンカ点候補が有する属性を削除することにより、アンカ点候補としての座標点を削減している。図１５は、ＣＰＵ７によって実行される削減処理の詳細なフローである。まずＳ１３５１では、着目アンカ点候補Ｑｊの属性が「変曲点」か否かを判定する。着目アンカ点候補Ｑｊの属性が「変曲点」であった場合、Ｓ１３５２へ遷移し、着目アンカ点候補Ｑｊの属性を削除し、処理を終える。着目アンカ点候補Ｑｊの属性が「変曲点」でなかった場合、Ｓ１３５３へ遷移する。Ｓ１３５３では、着目アンカ点候補Ｑｊの属性が「屈曲点」か否かを判定する。着目アンカ点候補Ｑｊの属性が「屈曲点」であった場合、Ｓ１３５４へ遷移し、参照点内のアンカ点候補が、当該着目アンカ点候補Ｑｊに隣接する参照点Ｑｊ−１、Ｑｊ＋１か否かを判定する。そして参照点Ｑｊ−１、Ｑｊ＋１がアンカ点候補であった場合はＳ１３５５へ遷移し、着目アンカ点候補Ｑｊの属性を削除して処理を終える。アンカ点の候補が隣接しない座標点であった場合はそのまま処理を終える。Ｓ１３５３にて着目アンカ点候補Ｑｊの属性が「屈曲点」でなかった場合、Ｓ１３５６へ遷移する。
【００３７】
Ｓ１３５６では、着目アンカ点候補Ｑｊの属性が「頂点」か否かを判定する。着目アンカ点候補Ｑｊの属性が「頂点」であった場合、Ｓ１３５７へ遷移し、着目アンカ点候補よりも優先度の高い属性を有するアンカ点候補が、当該着目アンカ点候補Ｑｊに隣接する参照点Ｑｊ−１、Ｑｊ＋１双方に存在するか否かを判定する。そして参照点Ｑｊ−１、Ｑｊ＋１双方に着目アンカ点候補Ｑｊよりも高い優先度の属性を有するアンカ点候補が存在した場合はＳ１３５８へ遷移し、着目アンカ点候補Ｑｊの属性と座標を削除し、処理を終える。隣接する参照点Ｑｊ−１、Ｑｊ＋１双方にアンカ点候補が存在しない場合はそのまま処理を終える。
【００３８】
Ｓ１３５６にて着目アンカ点候補Ｑｊの属性が「頂点」でなかった場合、Ｓ１３５９へ遷移する。Ｓ１３５９では、着目アンカ点候補Ｑｊの属性が「直線保持点」か否かを判定する。着目アンカ点候補Ｑｊの属性が「直線保持点」であった場合、必ず参照点Ｑｊ＋１は同じ「直線保持点」となる。よって次にＳ１３５１０へ遷移し、着目アンカ点候補よりも優先度の高い属性を有するアンカ点候補が参照点Ｑｊ−１、Ｑｊ＋２双方に存在するか否かを判定する。そして参照点Ｑｊ−１、Ｑｊ＋２双方に着目アンカ点候補よりも優先度の高い属性を有するアンカ点候補が存在した場合はＳ１３５１１へ遷移し、参照点Ｑｊ＋１に存在するアンカ点候補と、着目アンカ点候補Ｑｊの属性と座標を削除し、処理を終える。参照点Ｑｊ−１、Ｑｊ＋２双方にアンカ点候補が存在しない場合はそのまま処理を終える。着目アンカ点候補Ｑｊの属性が「直線保持点」でなかった場合、処理を終える。
【００３９】
ここまでで着目アンカ点候補を削除するか否かの判定を終えた。次にＳ１３６で、現在の着目点が追跡している座標点列の終点であるか否かを判定する。すなわち、すべてのアンカ点候補に対して本処理を適用したか否かを判定する。終点ではないと判定された場合は、Ｓ１３７で着目アンカ点候補を座標点列上における次のアンカ点候補に移し、再度Ｓ１３２へ遷移する。現在の着目アンカ点候補が終点であると判定された時はアンカ点決定処理を終える。以上の処理は図３におけるアンカ点決定手段１３００を実現している。また、Ｓ１２０とＳ１３０は、合わせてアンカ点情報抽出手段２００を実現している。
【００４０】
［アンカ点候補属性の目的と優先順位］
ここで、各アンカ点候補属性の目的と優先順位の理由について説明する。まず、「端点」は開輪郭における始端、及び終端を意味し、先にも述べたとおり近似処理を終えた後この点を基準に各座標点列をつなぎ合わせるので、削減は行わず、また優先順位の比較対象外とする。
【００４１】
次に「折点」は入力画像の座標点列における角張った部分を表現することを目的としている。「折点」画像において特徴的な点であり、削減による視覚的な変化はいずれのパターンでも大きい。このことからアンカ点候補中、１位の優先順位とし、削減は行わないこととする。
【００４２】
次に「直線保持点」は入力画像の座標点列におけるｘ方向、ｙ方向における直線部分の表現を目的としている。このため「直線保持点」は必ず２点隣り合う形で抽出する。この点を削減した場合、直線が曲線となってしまう場合があるため視覚的な変化が大きい。しかし、２点の「直線保持点」を直近で囲む形で「折点」が存在する場合は、その目的から「直線保持点」を削減しても視覚的な劣化は起こらない。このことからアンカ点候補の優先順位は全属性中、２位としている。
【００４３】
次に「頂点」は入力画像の座標点列におけるエッジや曲線の極値点を表現することを目的としている。このため「頂点」は削減することによる視覚的な変化が大きい。しかし、「頂点」を直近で囲む形で「折点」や「直線保持点」が存在する場合、「頂点」を削減しても視覚的な劣化は起こらない。このことからアンカ点候補の優先順位は全属性中、３位としている。
【００４４】
次に「屈曲点」は入力画像の座標点列における急峻な角度の変化を表現することを目的としている。しかし本実施形態における屈曲点の抽出は、着目点前後の角度のみを参照して判定を行っているため、入力画像に不規則なパターンが存在した場合過剰に抽出してしまう。また画像中の角度変化が大きい点を抽出しているため、削減した場合の影響は大きいものの、「頂点」や「折点」などの画像における代表的な特徴部に直近で存在した場合は削減を行っても画像の変化は目立たちにくい。このことからアンカ点候補の優先順位は全属性中、４位としている。
【００４５】
最後に「変曲点」は入力画像の座標点列において傾き変化量が入れ替わった点で近似区間を区切ることで、複雑なパターンの近似区間をなくすことを目的としている。しかし本実施形態における変曲点の抽出は、局所領域のみを参照して判定を行っているため、入力画像に不規則なパターンが存在した場合過剰に抽出してしまう。また、変曲点は曲線の途中に存在する点であり、他の属性のような特徴的な点を抽出した点ではないため、削減した場合の変化は視覚的に目立ちにくい。このことから、アンカ点候補の優先順位は全属性中、５位としている。
【００４６】
なお、アンカ点に付加される属性は、ここで挙げられたものに限定されるわけではなく、さらに細かく定義してもよい。また、処理を行う画像の特性に合わせて、上記の属性の一部のみを用いて処理を行ってもよい。
【００４７】
［コントロール点決定処理］
次にＳ１４０、Ｓ１５０で行うコントロール点決定処理について説明する。この処理では特許文献１で開示されている手法を適用することができる。すなわち、図１６に示すように、コントロール点ｃ１、ｃ２間を結ぶ線分ｃ１ｃ２は、アンカ点ａ１、ａ２を結ぶ線分ａ１ａ２と平行であると仮定する。そして線分ａ１ａ２から最も距離が離れた座標点列上の点Ｐｆと線分ａ１ａ２との距離をＤｆ、線分ａ１ａ２と線分ｃ１ｃ２との距離をＤｃとすると、Ｄｃ＝４／３Ｄｆの関係が成り立つゆえ、線分ｃ１ｃ２が一意に定まる。そして、アンカ点ａ１、ａ２における接線をそれぞれ決定し、接線方向と線分ｃ１ｃ２との交点をコントロール点ｃ１、ｃ２として一意に定める。このとき各アンカ点における接線方向は、Ｓ１４０の、接線方向決定処理によって行う。接線方向は３次ベジェ曲線で近似する上で、曲率を司る。このため各アンカ点において、アンカ点間で区切られた区間の座標点形状を鑑みて接線方向を決定する必要がある。本発明においてはこの接線方向の決定に、アンカ点候補情報抽出時に得た属性を利用して簡易に行うことを実現している。ここで、Ｓ１３０のアンカ点決定処理で得た座標点列をＲｋ（ｋ＝１，２，…ｌ）とし、座標点列追跡方向と逆方向の座標点をＲｋ−１、Ｒｋ−２…とし、座標点列追跡方向と順方向の座標点をＲｋ＋１、Ｒｋ＋２…と呼称することとする。
【００４８】
［接線方向決定処理］
図１７は、ＣＰＵ７によって実行される、Ｓ１４０で行われる接線方向決定処理の詳細なフローである。まずＳ１４１で接線方向を決定する対象となるアンカ点の属性を参照し、属性が「直線保持点」、もしくは「折点」であるか否かを判定する。アンカ点の属性が「直線保持点」、もしくは「折点」であった場合には、Ｓ１４２へ遷移し、それぞれ図１８（ｃ）、図１８（ｂ）で示したように、隣接する座標点Ｒｋ−１、Ｒｋ＋１の方向を接線方向とし、処理を終える。Ｓ１４１にて属性が「直線保持点」、もしくは「折点」でなかった場合にはＳ１４３へ遷移する。Ｓ１４３では、属性が「変曲点」であるか否かを判定する。属性が「変曲点」であった場合には、Ｓ１４４へ遷移し、図１８（ｆ）で示したように、アンカ点Ｒｋの前後２点先の座標点Ｒｋ−２、Ｒｋ＋２を結ぶ直線の傾きを求め、求めた傾きの平均を算出する。このとき傾きの平均は、閾値Ｔ６以内とする誤差の範囲内（第一の誤差）であっても良い。そして算出した傾きの平均に基づき、互いに向きが逆行する方向を接線方向とし、処理を終える。このとき互いの向きは正確に１８０度（すなわち、それぞれの接線が正反対の方向を向いている）としてもよいし、閾値Ｔ７以内とする誤差の範囲内（第二の誤差）であっても良い。。またここで言う閾値Ｔ６、Ｔ７の一例としてはＴ６＝０．１、Ｔ７＝１．０等を定義しうる。Ｓ１４３にて属性が「変曲点」でなかった場合にはＳ１４５へ遷移する。Ｓ１４５では接線方向を決定する対象となるアンカ点の前後二点先の座標点Ｒｋ−２、Ｒｋ＋２の方向を接線方向とし、処理を終える。以上の処理により、図３における接線方向決定手段１４００を実現している。
【００４９】
［接線方向］
ここで、各属性における接線方向について説明する。まず「折点」は入力画像の座標点列の角張った部分を表現するため、「折点」前後の近似区間で直交するように接線方向を取るのが好ましい。このことから、図１８（ｂ）に示したように「折点」に隣接する座標点の方向をそれぞれ接線方向とすれば接線方向を直交とすることができ、角張った表現が可能となる。
【００５０】
次に「直線保持点」は入力画像の座標点列の直線部分を保持しつつ隣接する近似区間に滑らかに接続するため「直線保持点」前後の接線方向は並行でかつ逆行する方向に取るのが好ましい。このことから図１８（ｃ）に示したように「直線保持点」に隣接する座標点の方向を接線方向とすれば、平行かつ逆行する形で接線方向を取ることができ、これにより直線を保持しつつ、滑らかに隣接する近似区間とつなげることが可能となる。
【００５１】
次に「頂点」は入力画像の座標点列のエッジや緩やかな曲線の極値点を表現するため、接線方向は「頂点」前後の近似区間における曲率を鑑みた方向であるのが好ましい。このことから図１８（ｄ）に示したように前後二点先の座標点の方向を接線方向とすれば、緩やかな「頂点」は緩やかな接線方向をとりつつ、急峻な「頂点」は急峻な角度の接線方向を取ることができ、緩やかな極点と急峻なエッジを表現することが可能となる。
【００５２】
次に「屈曲点」は入力画像の座標点列における角度の急峻な変化を表現するため、「屈曲点」前後の近似区間の曲率の変化を鑑みた接線方向であることが好ましい。このことから図１８（ｅ）に示したように前後二点先の座標点の方向を接線方向とすれば、「屈曲点」前後の近似区間で別々に接線方向を取ることができ、かつ曲率の変化を加味できるので急峻な角度の変化を表現することができる。
【００５３】
次に「変曲点」は曲線の途中で傾き変化量の正負が変化した点を取るため、前後の近似区間では接線方向を平行でかつ逆行する方向にとり、滑らかに接続するのが好ましい。このことから図１８（ｆ）に示したように前後二点先の座標点の方向をそれぞれ算出し、それらの傾きの平均となる方向にそれぞれ接線方向を取ることで、接線方向を平行でかつ逆行する方向に取ることができ、滑らかに曲線を接続することができる。
【００５４】
最後に「端点」は前後どちらかの座標点が存在しないゆえ、前後の近似区間の接続を鑑みなくてもよい。このため図１８（ａ）に示したように座標点が存在する座標点列状の二点先の座標点の方向を接線方向としておくことで、近似区間となる座標点列の曲率に準じた接線方向を取ることができる。
【００５５】
［コントロール点座標算出処理］
以上まででアンカ点における接線方向の決定ができた。次にＳ１５０でコントロール点座標算出処理を行う。ここではまず、アンカ点で分割された区間における座標点列に対し、アンカ点間を結ぶ線分ａ１ａ２から最も距離が離れた座標点Ｐｆを検索する。そして検出した座標点Ｐｆと線分ａ１ａ２までの距離Ｄｆを求める。この距離Ｄｆに基づき、線分ａ１ａ２に平行であり、かつ線分ａ１ａ２から距離Ｄｃ＝４／３×Ｄｆ離れた線分ｃ１ｃ２を導出する。そして導出した線分ｃ１ｃ２に対し、Ｓ１４０で決定した各アンカ点の接線方向との交点をコントロール点として決定する。このとき、アンカ点ａ１、ａ２間に他の座標点が存在しない、二つのアンカ点の接線方向が互いに逆行している、もしくは線分ａ１ａ２の長さを距離Ｄｆで除算した値が閾値Ｔ５以下である場合、該当区間は直線部であるとしコントロール点は出力しない。本実施形態において閾値Ｔ５＝３０とする。以上の処理により、図３におけるコントロール点座標算出手段１５００を実現している。また、Ｓ１４０とＳ１５０とによりコントロール点座標決定手段３００を実現している。
【００５６】
最後にＳ１６０では生成したデータを、同一の座標を有する「端点」同士を結合し、ベクトルデータとして出力する。この処理により、図３におけるデータ出力手段４００を実現している。以上の処理を行うことにより、最終的に図２６に示したベクトルデータが得られる。
【００５７】
＜実施形態２＞
実施形態１では、アンカ点決定処理において、着目アンカ点候補の前後の座標点二点以内に他のアンカ点候補が存在した場合に削減処理を行った。しかし、アンカ点候補に含まれる座標点数が３点以上離れている場合は、例え冗長なアンカ点候補が存在した場合でも削減することはできない。そこで本実施形態では、隣接するアンカ点候補の優先順位を比較し、その上で削減処理を行う。また、アンカ点候補同士を比較して削減を行った場合、削減した結果をアンカ点候補情報に上書きし、上書きした結果における隣接アンカ点候補を再度判定していくこととしている。このことにより、より広い範囲での削減処理が可能となり、データ量の削減に寄与することができる。
【００５８】
図１９は、ＣＰＵ７によって実行される本実施形態の処理フローである。まず、座標点列を追跡し、Ｓ２３１で初めのアンカ点候補を第一アンカ点候補として抽出する。次にＳ２３２で第一アンカ点候補からさらに座標点列を追跡し、次に検出されたアンカ点候補を第二アンカ点候補とする。次にＳ２３３で第一アンカ点候補と第二アンカ点候補が有する属性の優先順位の比較を行う。第二アンカ点候補の優先順位が低かった場合はＳ２３４へ遷移する。Ｓ２３４では第一アンカ点候補と第二アンカ点候補で区切られた区間の座標点列の形状を判定する。ここで形状を判定する要素として、例えば、座標点列の角度、長さ、座標点数、削減したアンカ点候補の数などが挙げられる。ここで削減を行うと判定された場合は、Ｓ２３６へ遷移し、第二アンカ点候補を削減してＳ２３２に戻る。削減を行わないと判定された場合、Ｓ２３８へ遷移する。
【００５９】
Ｓ２３３で第一アンカ点候補の優先順位が低かった、もしくは同一であった場合はＳ２３５へ遷移する。Ｓ２３５ではＳ２３４と同様に第一アンカ点候補と第二アンカ点候補で区切られた区間の座標点列の形状を判定する。ここで形状を判定する要素として、例えば、座標点列の角度、長さ、座標点数、削減したアンカ点候補の数などが挙げられる。ここで削減を行うと判定された場合は、Ｓ２３７へ遷移し、第一アンカ点候補を削減し、その後Ｓ２３８へ遷移する。また削減を行わないと判定された場合、Ｓ２３８へ遷移する。Ｓ２３８では現在第二アンカ点候補として着目している点を第一アンカ点候補とし、Ｓ２３２へ戻る。
【００６０】
以上の処理を、処理した座標点数が開輪郭、閉輪郭における総座標点数となるまで行う。この処理により座標点列の追跡方向に従って、次々にアンカ点候補を比較していくことができ、アンカ点候補間の座標点数に制限されることのないアンカ点決定処理を実行することができる。
【００６１】
＜実施形態３＞
実施形態１では、アンカ点候補情報抽出処理において、前ステップで抽出した座標点列に対して図９に示したように追跡を行い、アンカ点候補情報を抽出した。こうした場合、「変曲点」や「屈曲点」のように角度の変化を用いて抽出を行う属性は、座標点列の角度を算出する必要があることから、図２０（ａ）に示したように、一点おきに判定を行うようにしている。
【００６２】
しかしこのとき、同じ座標点列でも図２０（ａ）の座標点１を判定する場合と図２０（ａ）の座標点２を判定する場合では異なる抽出結果が得られてしまい、２つの場合で最終的な近似結果が一致しないことがある。これに対応するため、実施形態１における図４のＳ１２０のアンカ点候補情報抽出処理で、角度変化を用いてアンカ点候補情報の抽出を行う「変曲点」と「屈曲点」の判定を、図２０で示したような各座標点列間を結ぶ辺の中点を用いて行ってもよい。即ち、図１０のフローチャートで示した一連の処理フローを、図２２で示すフローチャートに沿って処理するように構成してもよい。尚、アンカ点候補情報抽出処理以外の処理は実施形態１と同様の処理を行えばよい。
【００６３】
ここでは、図２１に示すように現在着目している座標点列の点を着目点Ｐｉ（ｉ＝１，２，…ｎ）と呼称する。また、着目点Ｐｉから見て座標点列追跡方向と逆方向の座標点をＰｉ−１、Ｐｉ−２…とし、座標点列追跡方向と順方向の座標点をＰｉ＋１、Ｐｉ＋２…と呼称する。さらに座標点Ｐｉと座標点Ｐｉ＋１間を結ぶ辺の中点をＣｌ（ｌ＝１，２，…ｎ−１）と呼称する。そして、着目点Ｐｉから見て座標点列追跡方向と逆方向の座標点同士がなす中点をＣｌ−１、Ｃｌ−２…とし、座標点列追跡方向と順方向座標点同士がなす中点をＣｌ＋１、Ｃｌ＋２…と呼称することとする。
【００６４】
以下、本実施形態におけるアンカ点候補情報抽出処理の詳細を図２２に示すフローチャートを用いて述べる。まずＳ３２１で、追跡する座標点列の初期点を設定し、該当の座標点を着目点とする。次にＳ３２２では着目点Ｐｉ自身をアンカ点候補とすべきか否かを判定する。
【００６５】
図２３は、ＣＰＵ７によって実行される、着目点判定処理の詳細な処理フローである。まずＳ３２２１で着目点の端点判定を行う。この処理は実施形態１における図１１のＳ１２２１と同様のものでよい。端点と判定された場合は、Ｓ３２２２へ遷移し、その着目点Ｐｉ自身の座標と、「端点」という属性を保持して、処理を終える。Ｓ３２２１で端点でないと判定された場合は、Ｓ３２２３の折点判定へ遷移する。この処理は実施形態１における図１１のＳ１２２３と同様のものでよい。折点と判定された場合は、Ｓ３２２２に移り、その着目点Ｐｉ自身の座標と、「折点」という属性を保持し、処理を終える。Ｓ３２２３で折点でないと判定された場合は、Ｓ３２２４へ遷移する。そして、着目点Ｐｉ自身の座標のみを保持し、そのまま処理を終える。
【００６６】
ここまでの処理により、Ｓ３２２の着目点Ｐｉ自身のアンカ点候補判定は終えた。次に、図２２において、着目辺ＰｉＰｉ＋１上にアンカ点候補を取るべきか否かを判定するＳ３２３へ遷移する。図２４は、ＣＰＵ７によって実行される、着目辺判定処理の詳細な処理フローである。まずＳ３２３１で着目辺ＰｉＰｉ＋１が直線保持辺か否かを判定する。この処理は実施形態１における図１２のＳ１２３１と同様のものでよい。着目辺ＰｉＰｉ＋１が直線保持辺であると判定された場合、Ｓ３２３２へ遷移する。そして、実施形態１と同様に座標を２点取り、その属性を「直線保持点」として保持し、処理を終える。
【００６７】
Ｓ３２３１で着目辺ＰｉＰｉ＋１が直線保持辺でないと判定された場合は、Ｓ３２３３の頂点を含む辺判定へ遷移する。この処理は実施形態１における図１２のＳ１２３３と同様のものでよい。着目辺ＰｉＰｉ＋１が頂点を含む辺であると判定された場合、Ｓ３２３４へ遷移する。そして、線分ＰｉＰｉ＋１の中点座標と、属性「頂点」を保持し、処理を終える。Ｓ３２３３で着目辺ＰｉＰｉ＋１が頂点を含む辺でないと判定された場合は、Ｓ３２３５の屈曲点を含む辺判定へ遷移する。屈曲点を含む辺を判定するために、まず図２５（ａ）に示したように着目辺ＰｉＰｉ＋１の中点座標Ｃｌと、辺Ｐｉ−１Ｐｉの中点座標Ｃｌ−１と、辺ＰｉＰｉ＋１の中点座標Ｃｌ＋１を参照点とし、線分Ｃｌ−１Ｃｌと、線分ＣｌＣｌ＋１とがなす角度θを算出する。そして、角度θが閾値Ｔ８以上となる辺を屈曲点を含む辺とする。本実施形態では閾値Ｔ８＝２５°としている。着目辺ＰｉＰｉ＋１が屈曲点を含む辺であると判定された場合、Ｓ３２３４へ遷移する。そして、線分ＰｉＰｉ＋１の中点座標Ｃｌと、属性「屈曲点」を保持し、処理を終える。
【００６８】
Ｓ３２３５で着目辺ＰｉＰｉ＋１が屈曲点を含む辺でないと判定された場合は、Ｓ３２３６の変曲点を含む辺判定へ遷移する。変曲点を含む辺を判定するために、まず図２５（ｂ）に示したように、着目辺ＰｉＰｉ＋１の中点座標Ｃｌと、辺Ｐｉ−１Ｐｉの中点座標Ｃｌ−１と、辺Ｐｉ−２Ｐｉ−１の中点座標Ｃｌ−２と、辺ＰｉＰｉ＋１の中点座標Ｃｌ＋１を参照点とする。そして、線分Ｃｌ−２Ｃｌ−１の傾きαと、線分Ｃｌ−１Ｃｌの傾きβと、線分ＣｌＣｌ＋１の傾きγを算出する。そして、傾きの変化量となるβ‐α、γ‐βを算出し、この傾きの変化量同士の正負が入れ替わる点を変曲点とする。ただし、傾きの変化量β‐αの絶対値が閾値Ｔ９以下となる場合は、β‐αの絶対値が閾値Ｔ９以上の値を取るまで傾きαをとる線分をＣｌ−３Ｃｌ−２、Ｃｌ−４Ｃｌ−３…と遡らせて判定を行う。本実施形態では閾値Ｔ９＝１．０×１０−７としている。着目辺ＰｉＰｉ＋１が変曲点を含む辺であると判定された場合、Ｓ３２３４へ遷移する。そして、線分ＰｉＰｉ＋１の中点座標Ｃｌと、属性「変曲点」を保持し、処理を終える。Ｓ３２３６で着目辺ＰｉＰｉ＋１が変曲点を含む辺でないと判定された場合は、そのまま処理を終える。
【００６９】
ここまででＳ３２３の着目辺ＰｉＰｉ＋１のアンカ点候補判定は終えた。次に図２２におけるＳ３２４で、現在の着目点が追跡している座標点列の終点であるか否かを判定する。終点ではないと判定された場合は、Ｓ３２５で着目点を座標点列上における次の点に移し、再度Ｓ３２２へ移る。終点であると判定された時はアンカ点候補情報抽出処理を終える。
【００７０】
上記の処理をアンカ点候補情報抽出処理として実施することで、角度の変化を用いて抽出する変曲点や屈曲点を、着目点の偶数点目か奇数点目かという判定を必要とせず、入力した座標点列に一対一で対応したアンカ点抽出結果を得ることができる。
【００７１】
＜実施形態４＞
実施形態１では、アンカ点候補情報抽出処理において、アンカ点決定処理における優先順位の高いものから順番に抽出を行い、抽出したアンカ点候補は一意に決定された属性を保持していた。しかし、複数の属性の性質を持つ点の場合、重複して属性を保持してもよい。例えば、「屈曲点」と「変曲点」の属性を有する場合は優先順位を上げ、接線方向は「変曲点」の場合と同様とする、などその重複属性の組み合わせによって優先順位や接線方向の取り方を変えることで、さらに精度の高いベクトル化を実現することができる。
【００７２】
＜その他の実施形態＞
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【特許請求の範囲】
【請求項１】
画像データの形状を表現する座標点列から、アンカ点を抽出するために予め定められた複数の抽出ルールに基づき、アンカ点の座標と当該アンカ点が予め定められた複数の属性のいずれに属するかとを決定し、前記アンカ点の座標と当該アンカ点の属性を含む情報を出力するアンカ点情報抽出手段と、
着目アンカ点の前記属性および前記着目アンカ点から所定の範囲にあるアンカ点の座標に応じて前記着目アンカ点における接線方向を決定する接線方向決定手段と、
前記着目アンカ点の接線方向及び座標からコントロール点座標を算出するコントロール点座標算出手段と、
前記アンカ点の座標と前記コントロール点座標とを含む情報を出力するデータ出力手段と
を有することを特徴とする画像処理装置。
【請求項２】
前記アンカ点情報抽出手段により決定されるアンカ点の属性は、
前記着目アンカ点の前後で、隣接するアンカ点への向きが水平方向から垂直方向もしくは垂直方向から水平方向へ変化する点である折点、
所定の長さを有する直線に含まれる点である直線保持点、
接線の傾きに対し極値の点となる頂点、
前記着目アンカ点の前後で、近傍のアンカ点となす接線の角度が所定の値以上の変化を伴う点である屈曲点、及び
前記着目アンカ点の前後で、前記アンカ点の群における連続するベクトルの外積の符号が変化する点である変曲点のうち少なくとも２つ以上を含むことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記接線方向決定手段は、前記着目アンカ点の属性が変曲点の場合には、接線方向を、所定の範囲におけるアンカ点と成す前後の辺の傾きの平均から第一の誤差の範囲内にある方向とし、当該前後の辺の成す角が１８０度から第二の誤差の範囲内にあるよう制御を行うことを特徴とする請求項１または２に記載の画像処理装置。
【請求項４】
前記接線方向決定手段は、前記着目アンカ点の属性が折点もしくは直線保持点の場合には、接線方向を、隣接する前後のアンカ点と成す方向とすることを特徴とする請求項１乃至３のいずれか一項に記載の画像処理装置。
【請求項５】
前記接線方向決定手段は、前記着目アンカ点の属性が頂点もしくは屈曲点の場合には、接線方向を、２点の距離に位置するアンカ点と成す方向とすることを特徴とする請求項１乃至４のいずれか一項に記載の画像処理装置。
【請求項６】
前記アンカ点情報抽出手段は、前記アンカ点の属性として、
折点は、接する前後の辺の長さがいずれも所定の長さ以上の点とし、
直線保持点は、長さが一定の値以上となる辺において、当該辺の端点それぞれから所定の距離に位置する点とし、
頂点は、隣接する座標点の接線において、傾きの正負が入れ替わった点とし、
屈曲点は、近傍のアンカ点候補となす接線の角度が所定の値以上に変化する点とし、
変曲点は、隣接する座標点との接線において、傾きの変化量の正負が入れ替わった点として
抽出することを特徴とする請求項２乃至５のいずれか一項に記載の画像処理装置。
【請求項７】
前記画像データを入力する画像入力手段と、
前記画像入力手段から入力された画像データにおける画像の形状を表現する座標点列を生成する座標点列抽出手段と
を更に有することを特徴とする請求項１乃至６のいずれか一項に記載の画像処理装置。
【請求項８】
画像処理装置のアンカ点情報抽出手段が、画像データの形状を表現する座標点列から、アンカ点を抽出するために予め定められた複数の抽出ルールに基づき、アンカ点の座標と当該アンカ点が予め定められた複数の属性のいずれに属するかとを決定し、前記アンカ点の座標と当該アンカ点の属性を含む情報を出力するアンカ点情報抽出工程と、
前記画像処理装置の接線方向決定手段が、着目アンカ点の前記属性および前記着目アンカ点から所定の範囲にあるアンカ点の座標に応じて前記着目アンカ点における接線方向を決定する接線方向決定工程と、
前記画像処理装置のコントロール点座標算出手段が、前記着目アンカ点の接線方向及び座標からコントロール点座標を算出するコントロール点座標算出工程と、
前記画像処理装置のデータ出力手段が、前記アンカ点の座標と前記コントロール点座標とを含む情報を出力するデータ出力工程と
を有することを特徴とする画像処理方法。
【請求項９】
コンピュータを、
画像データの形状を表現する座標点列から、アンカ点を抽出するために予め定められた複数の抽出ルールに基づき、アンカ点の座標と当該アンカ点が予め定められた複数の属性のいずれに属するかとを決定し、前記アンカ点の座標と当該アンカ点の属性を含む情報を出力するアンカ点情報抽出手段、
着目アンカ点の前記属性および前記着目アンカ点から所定の範囲にあるアンカ点の座標に応じて前記着目アンカ点における接線方向を決定する接線方向決定手段、
前記着目アンカ点の接線方向及び座標からコントロール点座標を算出するコントロール点座標算出手段、
前記アンカ点の座標と前記コントロール点座標とを含む情報を出力するデータ出力手段
として機能させることを特徴とするプログラム。
【請求項１０】
請求項９に記載のプログラムを記憶したプログラム記憶媒体。
【請求項１】
画像データの形状を表現する座標点列から、アンカ点を抽出するために予め定められた複数の抽出ルールに基づき、アンカ点の座標と当該アンカ点が予め定められた複数の属性のいずれに属するかとを決定し、前記アンカ点の座標と当該アンカ点の属性を含む情報を出力するアンカ点情報抽出手段と、
着目アンカ点の前記属性および前記着目アンカ点から所定の範囲にあるアンカ点の座標に応じて前記着目アンカ点における接線方向を決定する接線方向決定手段と、
前記着目アンカ点の接線方向及び座標からコントロール点座標を算出するコントロール点座標算出手段と、
前記アンカ点の座標と前記コントロール点座標とを含む情報を出力するデータ出力手段と
を有することを特徴とする画像処理装置。
【請求項２】
前記アンカ点情報抽出手段により決定されるアンカ点の属性は、
前記着目アンカ点の前後で、隣接するアンカ点への向きが水平方向から垂直方向もしくは垂直方向から水平方向へ変化する点である折点、
所定の長さを有する直線に含まれる点である直線保持点、
接線の傾きに対し極値の点となる頂点、
前記着目アンカ点の前後で、近傍のアンカ点となす接線の角度が所定の値以上の変化を伴う点である屈曲点、及び
前記着目アンカ点の前後で、前記アンカ点の群における連続するベクトルの外積の符号が変化する点である変曲点のうち少なくとも２つ以上を含むことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記接線方向決定手段は、前記着目アンカ点の属性が変曲点の場合には、接線方向を、所定の範囲におけるアンカ点と成す前後の辺の傾きの平均から第一の誤差の範囲内にある方向とし、当該前後の辺の成す角が１８０度から第二の誤差の範囲内にあるよう制御を行うことを特徴とする請求項１または２に記載の画像処理装置。
【請求項４】
前記接線方向決定手段は、前記着目アンカ点の属性が折点もしくは直線保持点の場合には、接線方向を、隣接する前後のアンカ点と成す方向とすることを特徴とする請求項１乃至３のいずれか一項に記載の画像処理装置。
【請求項５】
前記接線方向決定手段は、前記着目アンカ点の属性が頂点もしくは屈曲点の場合には、接線方向を、２点の距離に位置するアンカ点と成す方向とすることを特徴とする請求項１乃至４のいずれか一項に記載の画像処理装置。
【請求項６】
前記アンカ点情報抽出手段は、前記アンカ点の属性として、
折点は、接する前後の辺の長さがいずれも所定の長さ以上の点とし、
直線保持点は、長さが一定の値以上となる辺において、当該辺の端点それぞれから所定の距離に位置する点とし、
頂点は、隣接する座標点の接線において、傾きの正負が入れ替わった点とし、
屈曲点は、近傍のアンカ点候補となす接線の角度が所定の値以上に変化する点とし、
変曲点は、隣接する座標点との接線において、傾きの変化量の正負が入れ替わった点として
抽出することを特徴とする請求項２乃至５のいずれか一項に記載の画像処理装置。
【請求項７】
前記画像データを入力する画像入力手段と、
前記画像入力手段から入力された画像データにおける画像の形状を表現する座標点列を生成する座標点列抽出手段と
を更に有することを特徴とする請求項１乃至６のいずれか一項に記載の画像処理装置。
【請求項８】
画像処理装置のアンカ点情報抽出手段が、画像データの形状を表現する座標点列から、アンカ点を抽出するために予め定められた複数の抽出ルールに基づき、アンカ点の座標と当該アンカ点が予め定められた複数の属性のいずれに属するかとを決定し、前記アンカ点の座標と当該アンカ点の属性を含む情報を出力するアンカ点情報抽出工程と、
前記画像処理装置の接線方向決定手段が、着目アンカ点の前記属性および前記着目アンカ点から所定の範囲にあるアンカ点の座標に応じて前記着目アンカ点における接線方向を決定する接線方向決定工程と、
前記画像処理装置のコントロール点座標算出手段が、前記着目アンカ点の接線方向及び座標からコントロール点座標を算出するコントロール点座標算出工程と、
前記画像処理装置のデータ出力手段が、前記アンカ点の座標と前記コントロール点座標とを含む情報を出力するデータ出力工程と
を有することを特徴とする画像処理方法。
【請求項９】
コンピュータを、
画像データの形状を表現する座標点列から、アンカ点を抽出するために予め定められた複数の抽出ルールに基づき、アンカ点の座標と当該アンカ点が予め定められた複数の属性のいずれに属するかとを決定し、前記アンカ点の座標と当該アンカ点の属性を含む情報を出力するアンカ点情報抽出手段、
着目アンカ点の前記属性および前記着目アンカ点から所定の範囲にあるアンカ点の座標に応じて前記着目アンカ点における接線方向を決定する接線方向決定手段、
前記着目アンカ点の接線方向及び座標からコントロール点座標を算出するコントロール点座標算出手段、
前記アンカ点の座標と前記コントロール点座標とを含む情報を出力するデータ出力手段
として機能させることを特徴とするプログラム。
【請求項１０】
請求項９に記載のプログラムを記憶したプログラム記憶媒体。
【図２】
【図３】
【図４】
【図６】
【図１１】
【図１２】
【図１４】
【図１５】
【図１６】
【図１７】
【図１９】
【図２２】
【図２３】
【図２４】
【図２６】
【図１】
【図５】
【図７】
【図８】
【図９】
【図１０】
【図１３】
【図１８】
【図２０】
【図２１】
【図２５】
【図３】
【図４】
【図６】
【図１１】
【図１２】
【図１４】
【図１５】
【図１６】
【図１７】
【図１９】
【図２２】
【図２３】
【図２４】
【図２６】
【図１】
【図５】
【図７】
【図８】
【図９】
【図１０】
【図１３】
【図１８】
【図２０】
【図２１】
【図２５】
【公開番号】特開２０１１−２１０１５９（Ｐ２０１１−２１０１５９Ａ）
【公開日】平成２３年１０月２０日（２０１１．１０．２０）
【国際特許分類】
【出願番号】特願２０１０−７９４３８（Ｐ２０１０−７９４３８）
【出願日】平成２２年３月３０日（２０１０．３．３０）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２３年１０月２０日（２０１１．１０．２０）
【国際特許分類】
【出願日】平成２２年３月３０日（２０１０．３．３０）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]