画像処理装置、画像処理方法、及びコンピュータプログラム
【課題】 多値画像に対して、色領域間を隔てる画素境界の頂点境界線を高速に抽出する。
【解決手段】 所定サイズの画素マトリクス（ウィンドウ）で多値画像をラスター走査し、当該画素マトリクス内の複数画素の状態に応じて、異なる値を有する画素間の境界を形成する輪郭を区分する色交点であるか否かの判定と、当該異なる値をもつ画素間の境界を形成する輪郭点の抽出とを行う。そして、その求めた色交点と輪郭点とを用いて、色交点ごとに区分した輪郭線で構成される輪郭情報を生成する
【解決手段】 所定サイズの画素マトリクス（ウィンドウ）で多値画像をラスター走査し、当該画素マトリクス内の複数画素の状態に応じて、異なる値を有する画素間の境界を形成する輪郭を区分する色交点であるか否かの判定と、当該異なる値をもつ画素間の境界を形成する輪郭点の抽出とを行う。そして、その求めた色交点と輪郭点とを用いて、色交点ごとに区分した輪郭線で構成される輪郭情報を生成する
【発明の詳細な説明】
【技術分野】
【０００１】
多値画像から、異なる色領域間を隔てる境界（画素境界の頂点境界線）を高速に漏れなく、所定の順番通りに抽出する画像処理装置、画像処理方法、コンピュータプログラムに関する。
【背景技術】
【０００２】
画像のベクトル化に関連する技術は文字を対象としたものからスタートし、輪郭情報の抽出方法（特許文献１）や座標点列の関数近似方法（特許文献２）が提案された。さらに一般的なイラスト画像へと対象が広がり、線画像に対するベクトル化（特許文献３）や、カラー画像に対するベクトル化（特許文献４）等、様々な種類の画像にベクトル化処理を施す技術が提案されている。
【０００３】
ベクトル化されたデータは、所望のサイズに変倍してもジャギーの無いスムーズな輪郭表現が可能である。色数が少ないイラスト画像をベクトルデータに変換した場合は、データサイズの削減効果も有し、コンピュータでの編集処理等が容易となる利点もある。
【０００４】
また、文字や線画像といった種類の画像は２値画像、あるいは単色画像（文字や線の部分が単色で構成され且つそれ以外の部分は背景の白地である画像）として扱えるものが多い。このような画像に対しては、色連結領域毎に抽出した輪郭（文字や線画像の輪郭）を関数近似すれば好ましいベクトル化結果を得ることができる。なお、色連結領域（色領域）とは、同色と判断される連結画素により構成される領域（同色画素が繋がっている領域）である。一方、イラストは２色より多い複数色で構成されるものが多く、複数の色領域間の境界線の扱い方が問題となる。例えば２値画像での処理と同様に、多色画像から検出した色領域それぞれの輪郭を関数近似すると、隣接する色領域それぞれの輪郭が個別に近似されることになる。この場合、近似誤差によって、隣接する色領域間に共通の境界線部分に対して、２つの異なる近似曲線が得られてしまい、隙間や重なりが生じる問題があった。この様子を図３に示す。図３（ａ）は入力画像から色領域それぞれの輪郭形状を抽出した例を示している。背景の白地部分の領域を数えないものとすると、他の色領域に隣接する（他領域との境界線を持つ）色領域が３つ存在している。図３（ｂ）は、図３（ａ）の輪郭情報を色領域毎に個別に関数近似した場合の処理結果を示しており、色領域間に隙間や重なりが生じている。
【０００５】
上記の問題を踏まえ、色領域間に隙間を生じさせないベクトル化法が提案されている。特許文献５では色差が一定以上ある画素同士の境界を輪郭として追跡し、色領域の交点（以降、『色交点』と称する）に突き当たる度に分岐して探索を繰り返し行う。色領域の交点間で区切られた部分輪郭それぞれを関数近似の処理単位とし、関数近似後のデータを再度つなぎ合わせて各色領域のベクトルデータを生成するため、境界線に共通の関数近似結果が適用され隙間や重なりが原理的に生じない。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特登録３０２６５９２
【特許文献２】特登録４３７８２０８
【特許文献３】特開２００７−２９３８２９
【特許文献４】特開２００６−３４４０６９
【特許文献５】特開２００６−０３１２４５
【非特許文献】
【０００７】
【非特許文献１】鳥脇著“画像理解のためのディジタル画像処理（２）”初版３刷，ＩＳＢＮ４−７８５６−２００４−８，昭晃堂，１９９３年４月２０日発行，Ｐ．６６−Ｐ．７９
【発明の概要】
【発明が解決しようとする課題】
【０００８】
非特許文献１は、色領域の境界線を追跡することにより、色領域の境界線を抽出する。境界線は異なる色領域各々を図形と考えた場合に、当該図形の内部の点と外部の点との境界の集合を指す。境界線の追跡方法としては、非特許文献１の６８ページに記載されているように、画素追跡型、辺追跡型、頂点追跡型が知られている。ここでは、画像中で隣接する色領域間に隙間のない共通の輪郭線が定義されるという点で頂点追跡型に絞って話を進める。頂点追跡による境界線追跡法としては、特許文献５による境界線追跡が知られている。これによれば、抽出対象である色領域の探索開始点を探した後、抽出対象を右側または左側に決めて色境界をたどっていく。色交点にぶつかったらこれまで抽出した境界線を記録し、新たな抽出を開始する。こうして全ての境界線が抽出し終わるまで追跡を繰り返し行うというものである。
【０００９】
この方法にはいくつかの問題点がある。まず色交点に遭遇した時の探索順（複数ある時にどれを優先するか）が何通りか存在する。抽出順の選び方によっては境界線を並べて輪郭を再構成することが難しくなったり、抽出漏れが起きやすくなったりする。また追跡の方向が領域形状によって変わるため、メモリ上の画素情報を参照する際にキャッシュが効かず、処理速度が低下することも起こりうる。
【００１０】
なお、本出願人は、上述したような境界線を順に追跡していく方法を用いずに、境界線を抽出する方法として、以下の手法を考えている。本出願人が提案している特願２０１０−２３４０１２では、まず、ラスター走査で各色領域毎に境界線を構成する最小単位となる線素のテーブルを作成後、当該テーブルを走査して輪郭を抽出する。そして、抽出した色領域の輪郭をたどることで、隣接する他の色領域とで構成される色交点を検知し、輪郭を色交点ごとに分割する。この方法は、境界線の抽出漏れや境界線の再構成順序の問題を解決することができ、ラスター走査とテーブル走査で高速に輪郭を抽出する方法である。しかしながら、色交点も考慮した境界線を求めるには、抽出した輪郭を再度辿りなおすために、追跡と同じように輪郭を２度探索することになり、さらなる改良の余地が残されていた。
【課題を解決するための手段】
【００１１】
そこで、本発明では、線素を構成する輪郭点を抽出する際に色交点をも検知し、色交点情報を輪郭点情報と共に記録することで境界線を抽出するように構成する。
すなわち、本発明の画像処理装置は、所定サイズの画素マトリクスで多値画像をラスター走査し、当該画素マトリクス内の複数画素の状態に応じて、異なる値を有する画素間の境界を形成する輪郭を区分する色交点であるか否かの判定と、当該異なる値をもつ画素間の境界を形成する輪郭点の抽出とを行う色交点判定・輪郭点抽出手段と、前記色交点判定・輪郭点抽出手段で判定された色交点と抽出された輪郭点とを用いて、当該色交点ごとに区分した輪郭線で構成される輪郭情報を生成する輪郭情報再構成手段と、を有することを特徴とする。
【発明の効果】
【００１２】
１回のラスター走査で輪郭点と色交点とを取得するようにしたので、各領域の輪郭を示す輪郭情報（境界線）の生成を高速に行うことができる。
【図面の簡単な説明】
【００１３】
【図１】本実施形態における情報処理装置のメイン処理ブロック図。
【図２】本実施形態における情報処理装置のブロック図。
【図３】関数近似によって色領域に重なりや隙間が生じる例を説明する図。
【図４】本実施形態におけるフローチャート。
【図５】３×３の画素マトリクスでの画像からラスター走査を説明する図。
【図６】注目ベクトルと、その流入ベクトル、流出ベクトルとの関係を示す図。
【図７】一点のみで構成されるラベルのベクトル情報テーブルによる記録を示す図。
【図８】３×３の画素マトリクスの中心画素とその上下左右の４近傍画素を表す図。
【図９】ケース１から１６の各場合の色交点判定・輪郭点抽出処理を説明する図。
【図１０】色交点判定を伴わない輪郭点の抽出を説明する図。
【図１１】色交点判定を伴う輪郭点の抽出を説明する図。
【図１２】色交点判定を伴う輪郭点抽出時の色交点判定を説明する図。
【図１３】色交点判定し、色交点の場合のみ輪郭点を抽出する処理を説明する図。
【図１４】ステップＳ１２００での処理の流れを、具体例を元にして説明する図。
【図１５】具体例の場合での流入ベクトル未定水平ベクトルテーブル、流出ベクトル未定水平ベクトルテーブル、流入ベクトル未定垂直ベクトルテーブル、流出ベクトル未定垂直ベクトルテーブルの４種のテーブルの状態を表す図。
【図１６】２×２のウィンドウ走査で起こりえる４画素のパターンを示す図。
【発明を実施するための形態】
【００１４】
［実施例１］
本実施形態の画像処理装置の構成例について、図２のブロック図を参照して説明する。画像処理装置は、汎用のコンピュータを用いて実現することが可能である。図２において、ＣＰＵ７は装置全体を制御するプロセッサである。ＲＯＭ６は変更を必要としないプログラムやパラメータを格納するメモリである。ＲＡＭ５は外部装置等から供給されるプログラムやデータを一時記憶するメモリである。スキャナ１は、文書等を光電走査して電子的な画像データを得る。入出力Ｉ／Ｏ３はスキャナ１と画像処理装置とを接続するインタフェースである。画像メモリ２はスキャナ１で読み取られた画像データ等を保持する。外部記憶装置１２は固定して設置されたハードディスクやメモリカード、光ディスク等の記憶媒体である。また、Ｉ／Ｏ１３は外部記憶装置１２と画像処理装置とを接続するインタフェースである。Ｉ／Ｏ１５は、マウス等のポインティングデバイス１０やキーボード９等の入力デバイスと画像処理装置を接続するインタフェースである。映像Ｉ／Ｏ１４は、画像処理装置の保持するデータや供給されたデータを表示するためのディスプレイ８と画像処理装置とを接続するインタフェースである。通信Ｉ／Ｆ４は、インターネット等のネットワーク回線（不図示）に接続するためのインタフェースである。システムバス１１は各ユニットを通信可能に接続するバスである。
【００１５】
以下、ＣＰＵ７上で実行されるプログラムにより本発明を実現する処理手順を、図１のブロック図と図４のフローチャートを用いて説明する。
【００１６】
ステップＳ１０００で処理を開始すると、処理対象となる画像領域を含む画像データを入力する。画像入力に関しては、スキャナ１にて読み取られた画像データを画像入出力Ｉ／Ｏ３を介して画像メモリ２に入力する。また、通信Ｉ／Ｆ４を介して、装置外部より前記処理対象となる画像領域を含む画像を入力してもよく、あるいは、外部記憶装置１２に予め記憶される画像データをＩ／Ｏ１３を介して読み込むものであってもよい。得られた入力画像は、画像メモリ２上に保持される。
【００１７】
スキャナなどの入力手段を用いた場合、入力画像にノイズが重畳され、代表色の特定が難しいことが起こりうる。この場合、色領域分割処理を行うことで、近い画素値を持つ画素が同じ色情報となるようにまとめるようにするのが望ましい。そこでステップＳ１０００ではＣＰＵ７が入力画像に対して色領域分割処理を施すことで、上記問題を解消することができる。ここでの色領域分割処理については、本発明が適用可能であれば、いずれの方法を用いてもよい。例えば特許文献４で開示されている手法では、入力画像中の画素から色情報を元にクラスタを構成し、類似するクラスタやノイズと思われるクラスタを統合することでスキャンノイズを除去する。本実施形態においては、このような方法を適用することで、スキャン画像入力等で生じるノイズ除去している。以上の処理は図１における画像入力手段１０１を実現している。
【００１８】
次にステップＳ１０００で読み取った画像データに対して、ステップＳ１１００でラベリング処理（領域番号（ラベル）付与処理）を行うことにより、画像データ中の同色と判断される領域に同一の領域番号を付与して、色領域を抽出する。ラベリング処理は、８連結接続で考える場合、上下左右斜めの８方向のいずれかで隣接（連結）する同じ画素値を有する画素集合に同一の番号を付与する処理である。ここでは各色領域を後処理で識別できるようにするための番号（以下、領域番号）を、各色領域を構成する各画素に付与する。ラベリング処理（領域番号（ラベル）付与処理）された画像を、ラベル画像と呼ぶこととする。ラベリング処理では後で行う輪郭抽出処理と同じ連結状態となるラベリング処理を行う必要がある。本実施形態では、８連結接続で輪郭を抽出する例を用いて説明するので、ラベリング処理も８連結接続として処理し、上下左右斜め方向のいずれかで隣接する同じ画素値を有する画素集合に同一の番号を付与することになる。なお、ステップＳ１１００の処理は図１における領域番号付与手段１０２を実現している。
【００１９】
ステップＳ１２００では、ステップ１１００で得られたラベル画像を入力画像として、図５（ａ）に示すような３×３の画素マトリクス状ウィンドウの中心（同図中「ｘ」で表示）を着目画素として、図５（ｂ）に示すように入力画像の左上からラスター走査を行なう。そして、各ラベル領域毎にそのラベル領域の輪郭を構成する水平方向の線素と垂直方向の線素の切り替わる位置を、それぞれの線素の始点（以降、単に輪郭点とも称する）として抽出する処理を行う。加えて、それら輪郭点が色交点であるか否かの判定する色交点判定処理を行う。それら線素上に存在する可能性のある色交点の存在判定の結果、色交点が存在する場合には、その位置に色交点である輪郭点の抽出処理を行う。尚、抽出される垂直・水平方向の線素を、それぞれ垂直ベクトル、水平ベクトルと呼ぶ。また、線素上に存在が判定された色交点も、当該線素が水平の場合には新たな水平ベクトルの始点となり、同様に当該線素が垂直な場合には垂直ベクトルの始点となる。輪郭点抽出処理、輪郭点の色交点判定、線素上での色交点判定と色交点である位置での輪郭点抽出処理を総称して、色交点判定・輪郭点抽出処理と呼ぶ。
【００２０】
本実施形態では、水平ベクトルと垂直ベクトルは進行方向に対して、着目画素の属するラベル領域が右側に来るよう抽出される。この結果、抽出される外輪郭（輪郭抽出対象のラベル領域を外側から取り囲む輪郭）は時計回りとなる。また、内輪郭（輪郭抽出対象のラベル領域領域に周囲を取り囲まれる孔の境界に沿って、当該ラベル領域が右側に来るように抽出される内部の輪郭）は反時計回りとなる。座標系については、特許文献１での説明と同様に、本実施例では、入力画像の各画素の座標値を、主走査方向をｘ軸（右向きが正方向）、副走査方向をｙ軸（下向きが正方向）とし、それぞれ整数値で表現するものとして話を進める。また、抽出される線素の始点や色交点の座標値は、画素と画素の中間の位置に抽出されるので、これらの座標値を整数値として扱うため、当該座標値を２倍にした値を対象座標として抽出する。即ち、ｍ画素×ｎ画素の画像は、２ｍ×２ｎの正の偶数（整数）の座標表現で表し、抽出される線素の始点や色交点の座標値が、整数値（奇数）となるようにして説明する。以降、第ｊ番目のラスタの第ｉ番目の画素位置を（２ｉ，２ｊ）（ｉ，ｊは正の整数で、ｉ≦ｍ，ｊ≦ｎ）で表現する。
【００２１】
抽出した垂直ベクトルの始点や水平ベクトルの始点の情報には、それぞれに流入元となるベクトルの始点と、流出先となるベクトルの始点の情報への接続情報を付して記録する。以降、流入元となるベクトルの始点を単に流入元、流出先となるベクトル始点を流出先と称し、流入元となるベクトルを流出ベクトル、流出先となるベクトルを流出先と称する。着目しているベクトルの始点は、流入ベクトルの終点でもあり、かつ、流出ベクトルの始点は、着目しているベクトルの終点でもある。この様子を図６に一例として示した。同図は、注目ベクトルが水平ベクトルである場合を表記していて、６１が注目ベクトル、６２が注目ベクトル６１の始点であり、かつ、流入ベクトル６３の終点でもある。６４が流入ベクトル６３の始点（流入元）、６５が流出ベクトル、６６が流出ベクトル６５の始点（流出先）であり、かつ、注目ベクトル６１の終点でもある。ここで、垂直ベクトルの始点を白抜き三角印、水平ベクトルの始点を白抜き丸印で表記した。
【００２２】
これらのベクトルはラベルごとに１つのベクトル情報テーブルに記録して管理する。例として、図７に、注目するラベルが一点（１画素）のみで構成されるラベルである場合の前記ベクトル情報テーブルによる記録を示した。図７（ａ）は、一点のみで構成されるラベルを中心にその周囲８画素を含めて３×３のラベル画像を表現しており、周囲８画素は中心画素のラベルとは異なるラベルをもつ画素である。同ラベルは、水平ベクトル（ｒ）、垂直ベクトル（ｒ＋２）、水平ベクトル（ｒ＋３）、垂直ベクトル（ｒ＋１）の４本の線素で囲まれている。同図（ｂ）は、この様子を記録したベクトル情報テーブルである。図７（ｂ）のテーブルにおいて、各ベクトルは横一行で１本の線素を表現している。ベクトルカウンタ欄は、抽出された順にカウントアップされながら定まるベクトル番号（ベクトルインデックスやテーブルインデックスとも称すことがある）である。ベクトル番号は、基本的に、輪郭点、もしくは、色交点として抽出された順に昇順に定められる番号である。図７（ａ）の状態の説明におけるｒ，ｒ＋１，ｒ＋２，ｒ＋３も、抽出された順に定められるベクトル番号ではあるが、このベクトル番号をもって、各ベクトルを特定するベクトルの名称としても用いるものとする。なお、説明の便宜上、ベクトル番号の初期値としてｒを用いたが、初期値が０から始まるものとすると、これらベクトル番号は、０、１、２、３となる。始点欄は、Ｘ座標欄とＹ座標欄から構成され、それぞれ、各ベクトルの始点のＸ座標値とＹ座標値を格納する。図７（ｂ）では、中心の画素の座標値が（２ｉ，２ｊ）であったとして、各ベクトルの始点の座標値を記載してある。流入ベクトル欄は、当該ベクトル番号のベクトルの流入元となるベクトルのベクトル番号が格納される。同様に、流出ベクトル欄は、流出先となるベクトルのベクトル番号が格納される。色交点フラグ欄は、同ベクトル番号のベクトルが色交点である場合には“ＴＲＵＥ”が、色交点ではない場合には“ＦＡＬＳＥ”がはいるフラグ領域である。未使用フラグ欄は、ステップＳ１３００の輪郭情報再構成処理で参照するフラグ領域であり、これに関しては、追ってさらに説明を加える。
【００２３】
３×３のウィンドウでは、図８に示したように、３×３のウィンドウの中心である着目画素と着目画素の上下左右の４近傍画素に着目し、着目画素の周辺での輪郭ベクトルの始点や色交点の抽出、及び、それらの局所的な接続関係を求める。まず、着目画素Ｐ０が輪郭抽出対象のラベル領域の画素である場合にはＲ０＝１とした上で、着目画素Ｐ０と、図７に示すＰ１、Ｐ２、Ｐ３、Ｐ４の４近傍の各画素とを比較し、着目画素の所属ラベルと所属ラベルが一致した画素の位置Ｐｋ（ｋ＝１，２，３，４）の値Ｒｋを１とし、一致しない画素位置ではＲｋを０とする。そして、これらＲ０、Ｒ１、Ｒ２、Ｒ３に係数をかけて定義する以下の式によりＲを求める。
【００２４】
Ｒ＝Ｒ０＋１×Ｒ１＋２×Ｒ２＋４×Ｒ３＋８×Ｒ４
尚、着目画素Ｐ０が輪郭抽出対象のラベル領域の画素である場合には、４近傍画素の状態にかかわらず、Ｒ＝０とする。
【００２５】
上記Ｒは、着目画素と着目画素の上下左右の４近傍画素の所属ラベルの状態によって、０〜１６の値を持つのに対応させて、それぞれの場合をケース０からケース１６で区別する。各ケースに応じて所定の色交点判定・輪郭点抽出処理を行う。ケース０では、色交点判定・輪郭点抽出は全くなされない。
【００２６】
ケース１〜ケース１６の場合の色交点判定・輪郭点抽出処理を図９に示した。図９においては、中心画素のラベルに対して、その左右上下の４画素がそれぞれ同じラベルか否かで表現してあり、同４画素のうち、中心画素のラベルと同じラベルの画素は中心画素と同じ塗りつぶしパターンで表記し、そうでないものは塗りつぶしていない。尚、図９における中心画素の左上、左下、右上、右下の位置にある画素は、ケース１〜１６のいずれに属するかを分類する上では関わりをもたない非注目画素であることから、図９ではどんなラベルを持つ画素かによらず塗りつぶしのない状態で表記してある。図９（ａ）から図９（ｐ）までの１６種類の３×３のウィンドウの状態にあわせて、それぞれ、ａからｐまでのアルファベット順に、ケース１からケース１６の処理内容をケース番号の昇順に対応させて表記してある。図９において、白抜き丸印は、色交点であるか否かの判断をすることなしに、色交点ではない水平ベクトルの始点の抽出処理をする輪郭点候補位置である。白抜き三角印は、色交点であるか否かの判断をすることなしに、色交点ではない垂直ベクトルの始点の抽出処理をする輪郭点候補位置である。横向き矢印を伴った黒塗り丸印は、色交点であるか否かの判断を伴う水平ベクトルの始点の抽出処理をする輪郭点候補位置である。縦向き矢印を伴った黒塗り三角印は、色交点であるか否かの判断を伴う垂直ベクトルの始点の抽出処理をする輪郭点候補位置である。矢印の伴わない黒塗り丸印は、色交点か否かを判定し、色交点である場合には、色交点である水平ベクトルの始点を抽出する候補位置である。矢印の伴わない黒塗り三角印は、色交点であるか否かを判定し、色交点である場合には、色交点である垂直ベクトルの始点を抽出する候補位置である。実線矢印は、この矢印の位置にベクトルが抽出される場合には、流出先となる抽出済みのベクトルが存在するものを意味している。破線矢印は、この矢印の位置にベクトルが抽出された場合、流出先となるべきベクトルが、まだ抽出されていない状態、即ち、流出先が未定の状態で抽出されることになるベクトルであることを意味している。尚、以降、水平、垂直共に、ベクトルの始点の抽出のことを、単に、ベクトルの抽出と表現することがある。
【００２７】
図１０を用いて、色交点であるか否かの判断を伴わない輪郭点の抽出を説明する。図１０は、ケース１６での処理内容を示す図であり、中心画素のラベルと、その上下左右の４画素のラベルは全て同じ状態にある。図１０（ａ）は、図１０内で改めてケース１６のパターンを示すために、図９（ｐ）を再掲したものである。
【００２８】
まず、図１０（ｂ）に示すように、中心画素（座標値が（２ｉ，２ｊ）であるとする）の左上に垂直ベクトルの始点が存在するか否かを判定する。即ち、中心画素の左上の画素（座標値は（２ｉ−２，２ｊ−２））が、中心画素のラベルと同じラベルであるか否かを判定し、異なる場合には、図１０（ｃ）に示すように中心画素の左上の位置（座標値は（２ｉ−１，２ｊ−１））に垂直ベクトルを抽出する。同じ場合には、図１０（ｄ）に示すように、同位置にベクトルは抽出されない。
【００２９】
次に、図１０（ｅ）に示すように、中心画素の左下に水平ベクトルの始点が存在するか否かを判定する。即ち、中心画素の左下の画素（座標値は（２ｉ−２，２ｊ＋２））が、中心画素のラベルと同じラベルであるか否かを判定し、異なる場合には、図１０（ｆ）に示すように中心画素の左下の位置（座標値は（２ｉ−１，２ｊ＋１））に水平ベクトルを抽出する。同じ場合には、同図（ｇ）に示すように、同位置にベクトルは抽出しない。
【００３０】
次に、図１０（ｈ）に示すように、中心画素の右上に水平ベクトルの始点が存在するか否かを判定する。即ち、中心画素の右上の画素（座標値は（２ｉ＋２，２ｊ−２））が、中心画素のラベルと同じラベルであるか否かを判定し、異なる場合には、図１０（ｉ）に示すように中心画素の右上の位置（座標値は（２ｉ＋１，２ｊ−１））に水平ベクトルを抽出する。同じ場合には、図１０（ｊ）に示すように、同位置にベクトルは抽出しない。
【００３１】
さらに、図１０（ｋ）に示すように、中心画素の右下に垂直ベクトルの始点が存在するか否かを判定する。即ち、中心画素の右下の画素（座標値は（２ｉ＋２，２ｊ＋２））が、中心画素のラベルと同じラベルであるか否かを判定し、異なる場合には、図１０（ｌ）に示すように中心画素の右下の位置（座標値は（２ｉ＋１，２ｊ＋１））に垂直ベクトルを抽出する。同じ場合には、図１０（ｍ）に示すように、同位置にベクトルは抽出しない。
【００３２】
以上、図１０を用いて、ケース１６での処理内容と、色交点であるか否かの判断を伴わない輪郭点の抽出について説明した。
【００３３】
ここで、ベクトルを抽出した際のベクトル情報テーブル上でのデータの扱いについて、さらに説明を加える。注目するラベル領域（中心画素の属するラベル領域）に対する（図７（ｂ）を用いて、上述した形式の）ベクトル情報テーブルにおいて、それまで既に見つけられていたベクトル情報の次の行に相当するテーブル領域にベクトル情報を追記する。
【００３４】
まず、該当行のベクトルカウンタ欄に、抽出された順に応じたベクトル番号を書き込む。
【００３５】
次に、抽出されたベクトルの座標値（Ｘ座標値、Ｙ座標値）を、始点のＸ座標値とＹ座標値の欄に書き込む。
【００３６】
流入ベクトル欄と流出ベクトル欄については、図１０（ｌ）のケースのように、抽出したベクトルの流出先や流入元が、まだ走査されていない領域（以降、未走査領域とも称する）方向にある場合と、図１０（ｃ）のように、既に走査し終えた領域（以降、既走査領域とも称する）方向にある場合とで扱いが異なる。未走査領域方向に流入元や流出先がある場合には、前述のベクトル情報テーブルとは別に、流入ベクトルが未定のベクトルの情報を管理するテーブルと流出ベクトルが未定のベクトル情報を管理するテーブルとをそれぞれ別途用いて処理する。垂直ベクトル用の流入ベクトル未定のベクトルを管理するテーブルを、流入ベクトル未定垂直ベクトルテーブルと称する。また、垂直ベクトル用の流出ベクトル未定のベクトルを管理するテーブルを、流出ベクトル未定垂直ベクトルテーブルと称する。水平ベクトル用にも同様に、流入ベクトル未定水平ベクトルテーブルと流出ベクトル未定水平ベクトルと称するテーブルをそれぞれ用いる。それぞれのテーブルには、該当するベクトル番号を検出した順に格納していくものとする。図１０（ｌ）のケースの場合には、ベクトル情報テーブルの流入ベクトル欄には、その時点では何も記録せず、流入ベクトル未定垂直ベクトルテーブルに、ベクトル情報ベクトル上でのベクトル番号を追記して同テーブルを更新する。同様に、ベクトル情報テーブルの流出ベクトル欄には、その時点では何も記録せず、流出ベクトル未定垂直ベクトルテーブルに、ベクトル情報ベクトル上でのベクトル番号を追記して同テーブルを更新する。尚、図１０（ｉ）で示される水平ベクトルを抽出する場合の流出ベクトル欄も同様に、その時点では何も記入せず、流出ベクトル未定水平ベクトルにそのベクトル番号を追記して同テーブルを更新する。図１０（ｆ）で示される水平ベクトルが抽出される際は、その時点では流入ベクトル欄に何も記入せず、流入ベクトル未定水平ベクトルテーブルにそのベクトル番号を記入して同テーブルを更新する。
【００３７】
一方、上述の図１０（ｃ）の垂直ベクトルの様に、流入元や流出先が既走査領域方向にある場合は、上記の流入ベクトルが未定のベクトルの情報を管理するテーブルや流出ベクトルが未定のベクトル情報を管理するテーブル参照して、その流入元や流出先を定める。
【００３８】
流入元が既走査領域方向にある垂直ベクトルの流入元は、流出先が未定の水平ベクトルである。よって、このような垂直ベクトルの流入元を定める場合には、流出ベクトル未定水平ベクトルテーブルを参照する。このテーブルに格納されているベクトル番号をもつベクトルの中で、当該垂直ベクトルの始点と同じＹ座標値を持つベクトルを該当するラベルのベクトル情報テーブルから探し出す。ベクトル情報テーブルの当該垂直ベクトルの流入ベクトル欄に、得られた水平ベクトルのベクトル番号を記入し、それまで未定であったその水平ベクトルの流出ベクトル欄に、当該垂直ベクトルのベクトル番号を記載する。また、流出ベクトル未定水平ベクトルテーブルからその水平ベクトルのベクトル番号を削除して同テーブルを更新する。
【００３９】
次に、当該垂直ベクトルの様に、流出先が既走査方向にある垂直ベクトルの流出先を定める場合を説明する。流出先が既走査領域方向にある垂直ベクトルの流出先は、流入元が未定の水平ベクトルか、または、後述する色交点位置に抽出された垂直ベクトルの中で流入元が未定のものである。よって、このような垂直ベクトルの流出先を定める場合には、流入ベクトル未定水平ベクトルテーブルと流入ベクトル未定垂直ベクトルテーブルの両方を参照する。これらテーブルに格納されているベクトル番号をもつベクトルの中で、当該垂直ベクトルの始点と同じＸ座標値を持つベクトルを該当するラベルのベクトル情報テーブルから探し出す。複数見つかった場合には、そのＹ座標値が当該垂直ベクトルのＹ座標値よりも小さいものの中で最も大きなＹ座標値をもつもの（即ち、既走査領域の中で最も近くにある流入元未定の輪郭点）を選ぶ。ベクトル情報テーブルの当該垂直ベクトルの流出ベクトル欄に、得られた水平、もしくは、垂直ベクトルのベクトル番号を記入し、それまで未定であったそのベクトルの流入ベクトル欄に、当該垂直ベクトルのベクトル番号を記載する。また、得られたベクトルの番号が記載されていた、流入ベクトル未定水平ベクトルテーブル、もしくは、流入ベクトル未定垂直ベクトルテーブルからそのベクトルのベクトル番号を削除して同テーブルを更新する。
【００４０】
尚、図１０（ｉ）で示される水平ベクトルの様に、流入元が既走査領域方向にある水平ベクトルの流入元は、流出先が未定の垂直ベクトルである。よって、このような水平ベクトルの流入元を定める場合には、流出ベクトル未定垂直ベクトルテーブルを参照する。このテーブルに格納されているベクトル番号をもつベクトルの中で、当該水平ベクトルの始点と同じＸ座標値を持つベクトルを該当するラベルのベクトル情報テーブルから探し出す。ベクトル情報テーブルの当該水平ベクトルの流入ベクトル欄に、得られた垂直ベクトルのベクトル番号を記入し、それまで未定であったその垂直ベクトルの流出ベクトル欄に、当該水平ベクトルのベクトル番号を記載する。また、流出ベクトル未定垂直ベクトルテーブルからその垂直ベクトルのベクトル番号を削除して同テーブルを更新する。
【００４１】
次に、図１０（ｆ）で示される水平ベクトルの様に、流出先が既走査方向にある水平ベクトルの流出先を定める場合を説明する。流出先が既走査領域方向にある水平ベクトルの流出先は、流入元が未定の垂直ベクトルか、または、後述する色交点位置に抽出された水平ベクトルの中で流入元が未定のものである。よって、このような水平ベクトルの流出先を定める場合には、流入ベクトル未定水平ベクトルテーブルと流入ベクトル未定垂直ベクトルテーブルの両方を参照する。これらテーブルに格納されているベクトル番号をもつベクトルの中で、当該水平ベクトルの始点と同じＹ座標値を持つベクトルを該当するラベルのベクトル情報テーブルから探し出す。万が一、複数見つかる場合には、そのＸ座標値が当該水平ベクトルのＸ座標値よりも小さいものの中で最も大きなＸ座標値をもつもの（即ち、既走査領域の中で最も近くにある流入元未定の輪郭点）を選ぶ。ベクトル情報テーブルの当該水平ベクトルの流出ベクトル欄に、得られた水平、もしくは、垂直ベクトルのベクトル番号を記入し、それまで未定であったそのベクトルの流入ベクトル欄に、当該水平ベクトルのベクトル番号を記載する。また、得られたベクトルの番号が記載されていた、流入ベクトル未定水平ベクトルテーブル、もしくは、流入ベクトル未定垂直ベクトルテーブルからそのベクトルのベクトル番号を削除して同テーブルを更新する。
【００４２】
色交点フラグ欄には、追記中のベクトルが色交点である場合には、ＴＲＵＥを記録し、色交点ではない場合にＦＡＬＳＥを記録する。ケース１６では、色交点となる輪郭点はそもそも発生しないパターンであり、色交点であるか否かの判断は不要であった。このため、上述の図１０（ｃ）、図１０（ｆ）、図１０（ｉ）、図１０（ｌ）で抽出される輪郭点は、色交点ではないため、いずれの場合も色交点フラグ欄はＦＡＬＳＥを記録する。
【００４３】
未使用フラグ欄は、ステップＳ１２００では、ＴＲＵＥを記録する。同欄は、ステップＳ１３００の輪郭情報再構成処理で参照するフラグ領域であり、追ってさらに説明を加える。
【００４４】
次に、図１１と図１２を用いて、色交点であるかの判断（色交点判定）を伴う輪郭点の抽出とその色交点判定を説明する。
【００４５】
図１１は、ケース１での処理内容を示す図であり、中心画素のラベルと、その上下左右の４画素のラベルは全て異なる状態にある。図１１（ａ）は、図１１内で改めてケース１のパターンを示すために、図９（ａ）を再掲したものである。
【００４６】
まず、図１１（ｂ）に示すように、中心画素（座標値が（２ｉ，２ｊ）であるとする）の左上の位置（座標値は（２ｉ−１，２ｊ−１））に水平ベクトルの始点を抽出する。この水平ベクトルは、中心画素の上の画素が中心画素とはことなるラベルをもつので、流出先は未定のベクトルであるが、中心画素とその左上、上、左の４画素でなる２×２の領域の各画素のラベルの状態により、流入元が未定か確定するかは異なるものとなる。また、中心画素とその左上、上、左の４画素でなる２×２の領域の各画素のラベルの状態により、中心画素の左上の位置の水平ベクトルが、色交点となるか否かも異なる。図１１（ｃ）と図１１（ｄ）はともに、中心画素とその左上の画素のラベルが異なる場合をあらわしている。これらの場合には、当該水平ベクトルの流入ベクトルも未走査領域にあることになるので、流入ベクトルも流出ベクトルも未定の水平ベクトルとなる。一方、図１１（ｅ）と図１１（ｆ）はともに、中心画素とその左上の画素のラベルが同じ場合をあらわしている。これらの場合には、当該水平ベクトルの流入ベクトルは既走査領域に存在することになるので、流入ベクトルは確定していて、流出ベクトルは未走の水平ベクトルとなる。尚、当該水平ベクトルが、流入ベクトルも流出ベクトルも未定の水平ベクトルであっても、色交点である場合とない場合とがあり得る。この様子を図１１（ｃ）と図１１（ｄ）に示した。図１１（ｃ）は、当該水平ベクトルの始点が色交点ではない場合であり、白抜き丸印で表わした。図１１（ｄ）は、当該水平ベクトルの始点が色交点の場合であり、右上がり斜線で塗りつぶした丸印で表わした。また、該水平ベクトルが、流入ベクトルは確定していて、流出ベクトルは未走の水平ベクトルの場合も同様に、色交点である場合とない場合とがあり得る。この様子を図１１（ｅ）と図１１（ｆ）に示した。図１１（ｅ）は、当該水平ベクトルの始点が色交点ではない場合であり、白抜き丸印で表わした。図１１（ｆ）は、当該水平ベクトルの始点が色交点の場合であり、右上がり斜線で塗りつぶした丸印で表わした。
【００４７】
この位置（中心画素の左上の位置）の水平ベクトルの始点の色交点判定について、図１２（ａ）〜（ｆ）を用いて説明する。図１２（ａ）自体は図９（ｅ）、即ち、ケース５の状態をもとに表記したものであるが、中心画素の左上の位置の水平ベクトルの始点の色交点判定という意味では、図１１（ｂ）で表わされる、ケース１の中の同位置と同じ処理を行うものである。さて、図１２（ａ）に示す様に、中心画素とその左上、上、左の４画素でなる２×２の領域の各画素のラベルの状態により、色交点判定が行われる。図１２（ｂ）〜（ｄ）は、いずれも中心画素とその左上の画素のラベルが異なる場合を示している。これらの場合には、２×２の中の残り２画素（中心画素の上の画素と左の画素）のラベルも調べる。
【００４８】
中心画素以外の３画素が全て同一のラベルである場合（図１２（ｂ））は、２色の領域でしか接していない状態なので、色交点ではない輪郭点と判断する。
【００４９】
また、中心画素の上と左が同一のラベルで、左上の画素はこれらとは異なるラベルの場合（不図示）には、上と左の画素が８連結状態にあり、中心画素と左上の画素は非連結の状態にある。この場合は、当該水平ベクトルの始点位置では２色の領域でしか接していない状態にあるものとみなし、色交点ではない輪郭点とする。
【００５０】
また、図１２（ｃ）に示す様に、中心画素の左上と左の画素が同ラベルで、残りの１画素（上の画素）が中心画素とも他の２画素とも異なるラベルの場合には、３色の領域で接しているので色交点である輪郭点とする。
【００５１】
また、中心画素の左上と上の画素が同ラベルで、残りの１画素（左の画素）が注目画素とも他の２画素とも異なるラベルの場合（不図示）にも、３色の領域で接しているので色交点である輪郭点とする。即ち、注目画素以外の３画素のうち、縦または横につながる２画素が同ラベルで、残りの１画素が注目画素とも他の２画素とも異なるラベルの場合には、色交点である輪郭点とする。
【００５２】
また、図１２（ｄ）に示す様に、中心画素以外の３画素がいずれも互いに異なるラベルである場合には、４色の領域が接する交点となっているので、色交点とする。
【００５３】
図１２（ｅ）と（ｆ）は、中心画素と左上の画素のラベルが同じ場合、即ち、３×３の９画素領域中における２×２の４画素領域の中で、中心画素とその対角画素のラベルが同じ場合を示している。残りの２画素が、中心画素のラベルとは異なるラベルながら、同ラベルとなっている場合（図１２（ｅ））は、どちらの対角画素の組も８連結状態にあり、この場合にはどちらの連結状態も同等に扱う意味で、色交点とする。一方、図１２（ｆ）に示す様に、残りの２画素が互いに異なるラベルである場合、先に述べた不図示の場合同様、中心画素と左上の画素が８連結状態にあり、上と左の画素は非連結の状態にある。当該水平ベクトルの始点位置では２色の領域でしか接していない状態にあるものとみなし、色交点ではない輪郭点とする。
【００５４】
さて、ここまで図１１（ｂ）〜（ｆ）と図１２（ａ）〜（ｆ）を用いて、中心画素の左上の位置における、色交点であるかの判断（色交点判定）を伴う輪郭点の抽出とその色交点判定を説明した。一方、中心画素の左下の位置における色交点判定を伴う輪郭点の抽出と色交点判定も、流入元と流出先の扱いを含めて、抽出されるベクトルが垂直ベクトルの始点になる点とその位置が中心画素の左下であることを考慮する必要はあるものの、同様の処理内容となる。図１１（ｇ）〜（ｋ）と図１２（ｇ）〜（ｌ）が中心画素の左下の位置における色交点判定を伴う輪郭点の抽出と色交点判定を説明する図ではあるが、不図示の場合も含めて容易に適用可能であるため、これらを用いた詳述は省略する。以下、同様に、中心画素の右上の位置における色交点判定を伴う輪郭点の抽出と色交点判定は、図１１（ｌ）〜（ｐ）と図１２（ｍ）〜（ｒ）が中心画素の右上の位置における色交点判定を伴う輪郭点の抽出と色交点判定を説明する図である。抽出されるベクトルが垂直ベクトルの始点で、位置が中心画素の右上であることを考慮する必要はあるものの、不図示の場合も含めて容易に適用可能であるため、これらを用いた詳述は省略する。中心画素の右下の位置における色交点判定を伴う輪郭点の抽出と色交点判定は、図１１（ｑ）〜（ｕ）と図１２（ｓ）〜（ｘ）が中心画素の右下の位置における色交点判定を伴う輪郭点の抽出と色交点判定を説明する図である。抽出されるベクトルが水平ベクトルの始点で、位置が中心画素の右下であることを考慮する必要はあるものの、不図示の場合も含めて容易に適用可能であるため、これらを用いた詳述は省略する。
【００５５】
次に、図９の中の表記にあった、矢印を伴わない黒塗り丸印の位置での処理と、矢印を伴わない黒塗り三角印の位置での処理とを、図１３を用いて説明する。矢印の伴わない黒塗り丸印の位置での処理とは、色交点か否かを判定し、色交点である場合には、色交点である水平ベクトルの始点を抽出する処理である。矢印の伴わない黒塗り三角印の位置での処理とは、色交点であるか否かを判定し、色交点である場合には、色交点である垂直ベクトルの始点を抽出する処理である。
【００５６】
図１３（ａ）と図１３（ｅ）は、ケース１１（図９（ｋ））での処理に対応した図である。
【００５７】
図１３（ａ）は、中心画素とその左の画素が同ラベルで、中心画素の上の画素は中心画素と異なるラベルの場合に発生する処理を説明している。中心画素（座標値が（２ｉ，２ｊ）であるとする）の左上の位置（座標値は（２ｉ−１，２ｊ−１））が色交点であるか否かを判定し、色交点であるときのみ、水平ベクトルの始点を抽出する。中心画素の左上を中心とした２×２の４画素領域の画素パターンが、図１３（ｄ）に示す様に、中心画素とその左の画素以外の２画素が互いに異なるラベルで、かつ、中心画素の対角画素である左上の画素も中心画素とは異なるラベルである場合にのみ、左上の位置（座標値は（２ｉ−１，２ｊ−１））に色交点である水平ベクトルの始点を抽出する。この水平ベクトルは、流入元は既走査領域にあるので確定され、流出先は未走査領域にあるので未定となる。なお、図１３（ｂ）は、中心画素の対角位置が中心画素のラベルとは異なるラベルではあるものの、中心画素の上の画素と同じラベルである場合を示している。また、図１３（ｃ）は、中心画素とその左の画素以外の２画素が互いに異なるラベルではあるものの、中心画素の対角位置の画素が中心画素と同じラベルである場合を示している。図１３（ｂ）や図１３（ｃ）の場合には、中心画素の左上の位置は色交点ではなく、輪郭点は抽出されない。
【００５８】
図１３（ｅ）は、中心画素とその右の画素が同ラベルで、中心画素の下の画素は中心画素と異なるラベルの場合に発生する処理を説明している。中心画素（座標値が（２ｉ，２ｊ）であるとする）の右下の位置（座標値は（２ｉ＋１，２ｊ＋１））が色交点であるか否かを判定し、色交点であるときのみ、水平ベクトルの始点を抽出する。中心画素の右下を中心とした２×２の４画素領域の画素パターンが、図１３（ｈ）に示す様に、中心画素とその右の画素以外の２画素が互いに異なるラベルで、かつ、中心画素の対角画素である右下の画素も中心画素とは異なるラベルである場合にのみ、右下の位置（座標値は（２ｉ＋１，２ｊ＋１））に色交点である水平ベクトルの始点を抽出する。この水平ベクトルは、流入元は未走査領域にあるので未定となり、流出先は既走査領域にあるので確定される。なお、図１３（ｆ）は、中心画素の対角位置が中心画素のラベルとは異なるラベルではあるものの、中心画素の下の画素と同じラベルである場合を示している。図１３（ｇ）は、中心画素とその右の画素以外の２画素が互いに異なるラベルではあるものの、中心画素の対角位置の画素が中心画素と同じラベルである場合を示している。図１３（ｆ）や図１３（ｇ）の場合には、中心画素の右下の位置は色交点ではなく、輪郭点は抽出されない。
【００５９】
図１３（ｉ）と図１３（ｍ）は、ケース６（図９（ｆ））での処理に対応した図である。
【００６０】
図１３（ｉ）は、中心画素とその下の画素が同ラベルで、中心画素の左の画素は中心画素と異なるラベルの場合に発生する処理を説明している。中心画素（座標値が（２ｉ，２ｊ）であるとする）の左下の位置（座標値は（２ｉ−１，２ｊ＋１））が色交点であるか否かを判定し、色交点であるときのみ、垂直ベクトルの始点を抽出する。中心画素の左下を中心とした２×２の４画素領域の画素パターンが、図１３（ｌ）に示す様に、中心画素とその下の画素以外の２画素が互いに異なるラベルで、かつ、中心画素の対角画素である左下の画素も中心画素とは異なるラベルである場合にのみ、左下の位置（座標値は（２ｉ−１，２ｊ＋１））に色交点である垂直ベクトルの始点を抽出する。この垂直ベクトルは、流入元は未走査領域にあるので未定となり、流出先は既走査領域にあるので確定される。なお、図１３（ｊ）は、中心画素の対角位置が中心画素のラベルとは異なるラベルではあるものの、中心画素の左の画素と同じラベルである場合を示している。また、図１３（ｋ）は、中心画素とその下の画素以外の２画素が互いに異なるラベルではあるものの、中心画素の対角位置の画素が中心画素と同じラベルである場合を示している。図１３（ｊ）や図１３（ｋ）の場合には、中心画素の左下の位置は色交点ではなく、輪郭点は抽出されない。
【００６１】
図１３（ｍ）は、中心画素とその上の画素が同ラベルで、中心画素の右の画素は中心画素と異なるラベルの場合に発生する処理を説明している。中心画素（座標値が（２ｉ，２ｊ）であるとする）の右上の位置（座標値は（２ｉ＋１，２ｊ−１））が色交点であるか否かを判定し、色交点であるときのみ、垂直ベクトルの始点を抽出する。中心画素の右上を中心とした２×２の４画素領域の画素パターンが、図１３（ｐ）に示す様に、中心画素とその上の画素以外の２画素が互いに異なるラベルで、かつ、中心画素の対角画素である右上の画素も中心画素とは異なるラベルである場合にのみ、右上の位置（座標値は（２ｉ＋１，２ｊ−１））に色交点である垂直ベクトルの始点を抽出する。この垂直ベクトルは、流入元は既走査領域にあるので確定され、流出先は未走査領域にあるので未定となる。尚、図１３（ｎ）は、中心画素の対角位置が中心画素のラベルとは異なるラベルではあるものの、中心画素の右の画素と同じラベルである場合を示している。図１３（ｏ）は、中心画素とその上の画素以外の２画素が互いに異なるラベルではあるものの、中心画素の対角位置の画素が中心画素と同じラベルである場合を示している。図１３（ｎ）や図１３（ｏ）の場合には、中心画素の右上の位置は色交点ではなく、輪郭点は抽出されない。
【００６２】
先にも述べたが、色交点と判断された輪郭点に対応するベクトル情報テーブル中の色交点フラグ欄には、ＴＲＵＥを記録し、色交点ではない場合にＦＡＬＳＥを記録する。
【００６３】
尚、上述の図１０は図９（ｐ）に示したケース１６の処理、また、上述の図１１は図９（ａ）に示したケース１の処理、図１３（ａ）と図１３（ｅ）は図９（ｋ）に示したケース１１の処理、図１３（ｉ）と図１３（ｍ）は図９（ｆ）に示したケース６の処理に対応している。それ以外のケースは、これまで説明した、中心画素の左上、左下、右上、右下での、色交点であるか否かの判断を伴わない輪郭点の抽出処理、色交点判定を伴う輪郭点の抽出処理、色交点判定をして色交点の場合のみ輪郭点を抽出する処理の組合せで構成される。例えば、図９（ｂ）に示したケース２の場合は、中心画素の左下での色交点判定を伴う輪郭点の抽出処理と、同右上での色交点判定をして色交点の場合のみ輪郭点を抽出する処理、同右下での色交点判定を伴う輪郭点の抽出処理で構成される。また、図９（ｄ）に示したケース４では、中心画素の左下での色交点判定を伴う輪郭点の抽出処理と、同右上での色交点であるか否かの判断を伴わない輪郭点の抽出処理、同右下での色交点判定をして色交点の場合のみ輪郭点を抽出する処理で構成される。といった具合である。これ以外のケースに関しても、同様に処理を行えば構成可能であるため、これらに関する詳述は省略する。尚、各ケースにおいて構成に必要となる、中心画素の左上、左下、右上、右下での処理（ケースによって、存在しない位置もある）の順番は、ラスター走査の順における未走査領域と抽出した輪郭点の流入元と流出先の扱いを一貫させる必要がある。このため、本実施例では、左上、左下、右上、右下（ケースにより、処理が存在しない位置は、左記の順を飛ばす）の順に行うものとする。
【００６４】
以上により、ステップＳ１２００における色交点判定・輪郭点抽出処理の説明を終える。ステップＳ１２００における、ベクトル情報テーブルや流入ベクトル未定水平ベクトルテーブル、流入ベクトル未定垂直ベクトルテーブル、流出ベクトル未定水平テーブル、流出ベクトル未定垂直テーブルは、ＲＡＭ５上に不図示の領域として確保されるものである。なお、ステップＳ１２００の処理は図１における色交点判定・輪郭点抽出手段１０３を実現している。とりわけ、上記において、図１２及び図１３に基いて説明した色交点判定は、図１における色交点判定手段１０３１を実現しており、図１０、図１１及び図１３に基いて説明した輪郭点抽出処理は、図１における輪郭点抽出手段１０３２を実現している。
【００６５】
ステップＳ１２００での処理の流れを、図１４と図１５を用いて、具体例を元にして、さらに説明を加える。
【００６６】
図１５は上述した、流入ベクトル未定水平ベクトルテーブル、流出ベクトル未定水平ベクトルテーブル、流入ベクトル未定垂直ベクトルテーブル、流出ベクトル未定垂直ベクトルテーブルの４種のテーブルの状態を表している。それぞれのテーブルは、あらかじめＲＡＭ５上に十分な領域が確保されているものとする。また、それぞれの領域は、それぞれ連続したメモリ領域として構成されていて、先頭領域から発生順にそれぞれのテーブルに該当する未定のベクトル番号を格納するものとする。それぞれの領域において、有効データの次である最終尾の位置には、最終尾であることを示すマーカーとして「−１」を格納しておく。データを付け加えるには、このマーカーの位置に新たなベクトル番号を上書きし、その次の領域に改めてマーカーを書き込む。あるデータを削除する際には、削除するデータの次の有効データからマーカーまでを、削除するデータの位置から順に１つずつシフトするように書き写していくものとする。
【００６７】
さて、図１４（ａ）の１４０で示されるようなラベル画像にステップＳ１２００の処理を行うと、色領域１（ラベル番号が１の領域）に対しては、図１４（ｂ）で示されるベクトル情報テーブルが得られることになる。図１４（ａ）における、Ａ（０）、Ｂ（１）、Ｃ（２）、Ｄ（３）、Ｅ（４）、Ｆ（５）の６点が、それぞれ、図１４（ｂ）のベクトル番号（ベクトルカウンタ欄の値）０、１、２、３、４，５の６本のベクトルに対応する。図１４（ａ）のラベル画像１４０をラスター走査すると、Ａ（０）、Ｂ（１）、Ｃ（２）、Ｄ（３）、Ｅ（４）、Ｆ（５）で示される位置の順に輪郭点が抽出されていくことになるからである。
【００６８】
すなわち、ラベル画像の左上からラスター走査を開始すると、３×３の画素マトリクスのウィンドウが、図１４（ａ）の１４００で示される位置に来た時、図９（ｇ）に示したケース７の状態となる。このときの中心画素の左上の位置に交点判定を伴う輪郭点抽出処理が行われ、図１２（ｂ）で示した状態であることから、図１４（ａ）におけるＡ（０）の位置に、ベクトル番号０として、色交点ではない輪郭点（水平ベクトルの始点）が抽出される。このベクトルは、この時点では流入ベクトルも流出ベクトルも未定であるから、図１５（ａ）に示す様に、流入ベクトル未定水平ベクトルテーブルと流出ベクトル未定水平ベクトルテーブルに、ベクトル番号０が追記されることになる。
【００６９】
ラスター走査を進めると、次に、図１４（ａ）の１４０１で示される位置に来た時、図９（ｍ）に示したケース１３の状態となる。このときの中心画素の右上の位置に交点判定を伴う輪郭点抽出処理が行われ、図１２（ｎ）で示した状態であることから、図１４（ａ）におけるＢ（１）の位置に、ベクトル番号１として、色交点ではない輪郭点（垂直ベクトルの始点）が抽出される。このベクトルは、流出ベクトルは未定ながら、流入ベクトルは既走査領域にあるので、流出ベクトル未定水平ベクトルテーブルを探索することにより、ベクトル番号０が流入ベクトルであることが判明する。よって、上述したように、ベクトル情報テーブルのベクトル番号１の流入ベクトル欄とベクトル番号０流出ベクトル欄の記載を行う。図１５（ｂ）に示す様に、流出ベクトル未定水平ベクトルテーブルからベクトル番号０を削除するとともに、流出ベクトル未定垂直ベクトルテーブルに、ベクトル番号１を追記する。
【００７０】
次に、図１４（ａ）の１４０２で示される位置に来た時、図９（ｆ）に示したケース６の状態となる。このときの中心画素の右上の位置に交点判定結果に基く輪郭点抽出処理が行われ、図１３（ｐ）で示した状態であることから、図１４（ａ）におけるＣ（２）の位置に、ベクトル番号２として、色交点である輪郭点（垂直ベクトルの始点）が抽出される。このベクトルも、流出ベクトルは未定ながら、流入ベクトルは既走査領域にあるので、流出ベクトル未定垂直テーブルを探索することにより、ベクトル番号１が流入ベクトルであることが判明する。よって、上述したように、ベクトル情報テーブルのベクトル番号２の流入ベクトル欄とベクトル番号１流出ベクトル欄の記載を行う。図１５（ｃ）に示す様に、流出ベクトル未定垂直ベクトルテーブルからベクトル番号１を削除した上で、ベクトル番号２を追記する。
【００７１】
次に、図１４（ａ）の１４０３で示される位置に来た時、図９（ｄ）に示したケース４の状態となる。このときの中心画素の左下の位置に交点判定を伴う輪郭点抽出処理が行われ、図１２（ｈ）で示した状態であることから、図１４（ａ）におけるＤ（３）の位置に、ベクトル番号３として、色交点ではない輪郭点（垂直ベクトルの始点）が抽出される。このベクトルは、流入ベクトルは未定ながら、流出ベクトルは既走査領域にあるので、上述のように、流入ベクトル未定水平ベクトルテーブルと流入ベクトル未定垂直ベクトルテーブルの両方を探索することにより、ベクトル番号０が流出ベクトルであることが判明する。よって、上述したように、ベクトル情報テーブルのベクトル番号３の流出ベクトル欄とベクトル番号０流入ベクトル欄の記載を行う。図１５（ｄ）に示す様に、流入ベクトル未定水平ベクトルテーブルからベクトル番号０を削除するとともに、流入ベクトル未定垂直ベクトルテーブルに、ベクトル番号３を追記する。さらに、このケース４の状態では、中心画素の右下の位置に交点判定結果に基く輪郭点抽出処理が行われ、図１３（ｈ）で示した状態であることから、図１４（ａ）におけるＥ（４）の位置に、ベクトル番号４として、色交点である輪郭点（水平ベクトルの始点）が抽出される。このベクトルは、流入ベクトルは未定ながら、流出ベクトルは既走査領域にあるので、上述のように、流入ベクトル未定水平ベクトルテーブルと流入ベクトル未定垂直ベクトルテーブルの両方を探索することにより、ベクトル番号３が流出ベクトルであることが判明する。よって、上述したように、ベクトル情報テーブルのベクトル番号４の流出ベクトル欄とベクトル番号３流入ベクトル欄の記載を行う。図１５（ｅ）に示す様に、流入ベクトル未定垂直ベクトルテーブルからベクトル番号３を削除するとともに、流入ベクトル未定水平ベクトルテーブルに、ベクトル番号４を追記する。
【００７２】
次に、図１４（ａ）の１４０４で示される位置に来た時、図９（ｊ）に示したケース１０の状態となる。このときの中心画素の右下の位置に交点判定を伴う輪郭点抽出処理が行われ、不図示ながら、図１２（ｕ）の様に、中心画素以外の３画素のうち、縦または横につながる２画素が同ラベルで、残りの１画素が中心画素とも他の２画素とも異なるラベルなので、色交点である輪郭点である。よって、図１４（ａ）におけるＦ（５）の位置に、ベクトル番号５として、色交点である輪郭点（水平ベクトルの始点）が抽出される。このベクトルは、流入ベクトルも流入ベクトルも既走査領域にある。まず、流出ベクトル未定垂直ベクトルテーブルを探索することにより、ベクトル番号２が流入ベクトルであることが判明する。よって、上述したように、ベクトル情報テーブルのベクトル番号５の流入ベクトル欄とベクトル番号２流出ベクトル欄の記載を行う。図１５（ｆ）に示す様に、流出ベクトル未定垂直ベクトルテーブルからベクトル番号２を削除する。そして、流入ベクトル未定水平ベクトルテーブルと流入ベクトル未定垂直ベクトルテーブルの両方を探索することにより、ベクトル番号４が流出ベクトルであることが判明する。図１５（ｆ）に示す様に、流入ベクトル未定水平ベクトルテーブルからベクトル番号４を削除する。
【００７３】
かくして、図１４（ａ）の１４０で示されるようなラベル画像の色領域１（ラベル番号が１の領域）に対して、図１４（ｂ）で示されるベクトル情報テーブルが得られることになる。
【００７４】
さて、これまで述べてきた、ステップＳ１２００の輪郭点・色交点抽出処理は、ラベル画像のラベル毎に順次にベクトル情報を抽出することが可能である。この方式では、ラベル画像中の全てのラベル領域の処理には、ラベル数に相当する回数分だけラベル画像を繰り返しラスター走査し、上記の処理を繰り返すことになる。このとき、ラベル画像中で、各ラベル領域の存在する範囲をあらかじめ矩形領域として求めておき、ラベル毎に、それぞれの存在する矩形領域（ラベル画像の部分領域となる）のみにラスター走査の範囲を限定すれば、処理時間を短縮することができる。
【００７５】
一方で、ラベル画像を一回走査するだけで、ラベル画像中に出現する全てのラベルの輪郭ベクトル情報を抽出することも可能である。この場合は、ラベル画像中に出現する全てのラベル分だけ、各々のラベル領域用に別々にベクトル情報テーブルと流入ベクトルや流入ベクトルが未定のベクトルの情報を管理するテーブル類を用意する。その上で、ラスター走査時に逐次、中心画素が属するラベルのテーブル類を使い分けて処理を進めるようにする。上述の走査を繰り返す場合に比し、ラベル数分の十分なメモリ容量を要すものの、一回のラスター走査で、全てのラベルに対して、それぞれ別々の独立したベクトル情報テーブル中に、それぞれのラベル領域の輪郭ベクトルデータを抽出することができる。
【００７６】
次にステップＳ１３００では、ステップＳ１２００で抽出したベクトル情報テーブル上のベクトル情報から、色領域（ラベル領域）を色交点間で区切られた部分輪郭の集まりで表現された輪郭情報に再構成する。
【００７７】
ベクトル情報テーブルをベクトル番号の昇順に未使用フラグを参照しながら、未処理（未処理フラグがＴＲＵＥ）かつ、色交点（色交点フラグがＴＲＵＥ）であるベクトルを探し、該当するベクトルが見つかった場合には、このベクトルから処理を開始する。このベクトルを第１の区分輪郭線の始点とするともに第一の区分輪郭線の第１点目の輪郭点とし、当該ベクトルの未使用フラグをＦＡＬＳＥに変更する。次に、このベクトルの流出ベクトルを参照して、同区分輪郭線の次の輪郭点とする。もし、この輪郭点が色交点でなければ、当該ベクトルの未使用フラグをＦＡＬＳＥに変更し、このベクトルの流出ベクトルを参照して同様の処理を続ける。一方、同輪郭点が色交点（色交点フラグがＴＲＵＥ）であった場合は、この輪郭点をもって同区分輪郭線の終了点とする。もし、この色交点の未使用フラグが既にＦＡＬＳＥとなっていた場合には、抽出中の輪郭の開始座標に戻ったということであり、１つの閉ループの抽出が完了となる。もし、この輪郭点の未使用フラグが未だＴＲＵＥの場合には、この輪郭点を次の区分輪郭線の始点とし、この新しい区分曲線の第１点目の輪郭点とする。このベクトルの未使用フラグをＦＡＬＳＥに変更してから、前の区分輪郭線と同様に、流出ベクトルを参照して同区分輪郭線上の次の輪郭点を求める動作を続ける。１つの閉ループの抽出が完了した場合には、再度、未処理（未処理フラグがＴＲＵＥ）かつ、色交点（色交点フラグがＴＲＵＥ）であるベクトルを探して残りの閉ループを探す。もし、テーブル内に色交点フラグがＴＲＵＥであるベクトルが見つからなかった場合は、テーブル内で最初に見つかる未処理のベクトルから処理を開始する。流出ベクトルのベクトル番号をたどり、出現するｘｙ座標を順に記録していけば輪郭座標を再構成することができる。そうして輪郭情報の再構成を続け、抽出中の輪郭の開始座標に戻れば１つの閉ループの抽出が完了となる。未処理のベクトルが無くなるまで処理を続けると外輪郭・内輪郭合わせた輪郭座標を全て抽出することができる。抽出された輪郭情報は、ラベル単位で情報を持つこととする。
【００７８】
図１４（ａ）から求められる図１４（ｂ）のベクトル情報テーブルを基に、ステップＳ１３００の処理で輪郭情報を再構成すると、図１４（ｃ）のように、色領域（ラベル番号が１の領域）を色交点間で区切られた部分輪郭の集まりで表現した輪郭情報が得られる。図１４（ｄ）は、図１４（ｃ）の輪郭情報が、ラベル番号１の領域の輪郭を構成することを示すデータ形式の例を示している。
【００７９】
このようにして抽出される色交点で区間分割された境界線（分割境界線）データを、区間ごとに関数近似することにより、それぞれの色領域の隣接箇所での重なり・隙間のないベクトルデータを生成することができる。
【００８０】
以上、ステップＳ１３００の輪郭情報再構成処理を説明した。尚、このステップＳ１３００の処理は、図１における輪郭情報再構成手段を実現している。
【００８１】
上述したように、本発明では、ラベリングされたラベル画像をラスター走査し、各ラベル領域の輪郭を構成する線素を、ウィンドウを用いて抽出する。抽出した線素は線素の始点となる座標情報とともに流出先・流出元を関連付けたうえでテーブルに登録しておく。また線素の始点が色領域間の色交点にあたる場合、色交点情報である旨も合わせて記録する。画像全体を走査し終えた後に、テーブルを参照して線素をつなぎ合わせる。この時、色交点情報を持つ箇所でつなぎ合わせるデータを分けることで境界線を抽出することができる。したがって、テーブルには線素が再構成されるべき順番で漏れなく登録されるため、抽出できる境界線も特定領域の輪郭再構成に適した順番で、漏れなく抽出することができる。１回の画像全面に対するラスター走査とテーブル走査で境界線が抽出できるため、処理も高速である。また、線素の抽出と色交点判定はウィンドウをラスター走査順にずらしながら行うため、追跡による境界線抽出のように、領域形状によって追跡の方向が変わることがなく、メモリキャッシュが効きやすくなり処理速度の低下防止に効果がある。また、色領域の形状によらず、画像全体に対する１回のラスター走査とテーブル走査で境界線を抽出できる。
【００８２】
［実施例２］
ウィンドウのサイズは３×３でなくてもよく、２×２でも可能である。２×２のウィンドウ走査で起こりえる２×２内の４画素のパターンを図１６（ａ）、図１６（ｄ）、図１６（ｇ）、図１６（ｋ）、図１６（ｏ）に示した。図１６（ａ）と図１６（ｄ）は、４画素内に２種類のラベルの画素が存在する場合である。図１６（ｇ）、図１６（ｋ）は、４画素内に３種類のラベルの画素が存在する場合である。図１６（ｏ）は、４画素内に４種類のラベルの画素が存在する場合である。尚、４画素内に１種類のラベルの画素しか存在しない場合には、輪郭点は抽出されることがないので、表記していない。基本的には、これらのパターンの９０°、１８０°、２７０°の回転したパターンがあり得るが、図１６（ａ）、図１６（ｄ）、図１６（ｇ）、図１６（ｋ）、図１６（ｏ）の場合を示せば、それらの回転パターンの場合は、容易に構成可能であるため、これらに関する詳述は省略する。以下、図１６（ａ）、図１６（ｄ）、図１６（ｇ）、図１６（ｋ）、図１６（ｏ）の場合を説明する。
【００８３】
実施例１の３×３のウィンドウ走査での説明の中で、ラベル画像を一回走査するだけで、ラベル画像中に出現する全てのラベルの輪郭ベクトル情報を抽出する場合を述べた。その中で、ラベル画像中に出現する全てのラベル分だけ、各々のラベル領域用に別々にベクトル情報テーブルと流入ベクトルや流入ベクトルが未定のベクトルの情報を管理するテーブル類を用意することを説明した。２×２のウィンドウ走査においても、同様である。
【００８４】
さて、図１６（ａ）のパターンの場合には、図１６（ｂ）と図１６（ｃ）に示したように、２種類のラベルのそれぞれに、一点ずつ、色交点ではない輪郭点を抽出する。図１６（ｄ）のパターンの場合には、図１６（ｅ）と図１６（ｆ）で示したように、２種類のラベルのそれぞれに、２点ずつ、色交点である輪郭点を抽出する。図１６（ｇ）のパターンの場合には、図１６（ｈ）、図１６（ｉ）、図１６（ｊ）で示したように、３種類のラベルのそれぞれに対応させて、それぞれに色交点である輪郭点を１点ずつ抽出する。図１６（ｋ）のパターンの場合には、図１６（ｌ）、図１６（ｍ）、図１６（ｎ）で示したように、３種類のラベルのうち、４画素中に一画素しか存在しないラベルに対しては、色交点ではない輪郭点を１点ずつ抽出し（図１６（ｌ）と図１６（ｍ）に相当）、４画素中の斜め方向に隣接している２画素に同じラベルが存在しているラベル（図１６（ｎ）に相当）には、色交点ではない輪郭点を２点抽出する。また、図１６（ｏ） のパターンの場合には、図１６（ｐ）、図１６（ｑ）、図１６（ｒ） 、図１６（ｓ）で示したように、のそれぞれに対応させて、それぞれに色交点である輪郭点を１点ずつ抽出する。
【００８５】
このように、構成すれば、２×２のウィンドウ走査でも、３×３のウィンドウ走査で得られる輪郭情報と全く同等な輪郭情報を抽出することが可能である。
【００８６】
一回のラスター走査で、ラベル画像中の全てのラベル領域の輪郭情報を抽出するためには、３×３の場合には、実施例１で述べた様に、中心画素のラベルについてのみを抽出すればよい。これに対し、２×２の場合には、ウィンドウ内４画素内に出現するラベル全てについての上を抽出しながら行う必要がある点が大きく異なる。
【００８７】
また、２×２の２×２のウィンドウ走査の場合でも、一回の走査では、上記の輪郭点抽出のうち、ある一つのラベルに対応する輪郭点のみを該当する一つのラベルのテーブル領域のみに抽出する様に構成してすることも可能である。画像中に存在するラベルの数の回数、輪郭抽出するラベルを切り替えながら、同様なラスター走査を繰り返せば、２×２のウィンドウ走査によっても、ラベル毎の輪郭情報抽出が可能である。この場合には、ベクトル情報テーブルと流入ベクトルや流入ベクトルが未定のベクトルの情報を管理するテーブル類用のメモリ領域をあらかじめ全てのラベル分確保する必要はなくなる。
【００８８】
（その他の実施例）
以上本発明にかかる実施形態を説明したが、実施形態の処理の多くは、情報処理装置上で実行されるコンピュータプログラムによるものであるので、当然、本発明はかかるコンピュータプログラムをもその範疇とする。通常、コンピュータプログラムは５のＲＡＭや６のＲＯＭ、またはＣＤ−ＲＯＭ等のコンピュータ可読記憶媒体に格納されていて、それをコンピュータにセットし、システムにコピーもしくはインストールすることで実行可能になる。従って、かかるコンピュータ可読記憶媒体も当然に本発明の範疇に入る。
【００８９】
また、本発明は、以下の処理を実行することによっても実現される。その処理は、上述した実施例の機能を実現させるソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【技術分野】
【０００１】
多値画像から、異なる色領域間を隔てる境界（画素境界の頂点境界線）を高速に漏れなく、所定の順番通りに抽出する画像処理装置、画像処理方法、コンピュータプログラムに関する。
【背景技術】
【０００２】
画像のベクトル化に関連する技術は文字を対象としたものからスタートし、輪郭情報の抽出方法（特許文献１）や座標点列の関数近似方法（特許文献２）が提案された。さらに一般的なイラスト画像へと対象が広がり、線画像に対するベクトル化（特許文献３）や、カラー画像に対するベクトル化（特許文献４）等、様々な種類の画像にベクトル化処理を施す技術が提案されている。
【０００３】
ベクトル化されたデータは、所望のサイズに変倍してもジャギーの無いスムーズな輪郭表現が可能である。色数が少ないイラスト画像をベクトルデータに変換した場合は、データサイズの削減効果も有し、コンピュータでの編集処理等が容易となる利点もある。
【０００４】
また、文字や線画像といった種類の画像は２値画像、あるいは単色画像（文字や線の部分が単色で構成され且つそれ以外の部分は背景の白地である画像）として扱えるものが多い。このような画像に対しては、色連結領域毎に抽出した輪郭（文字や線画像の輪郭）を関数近似すれば好ましいベクトル化結果を得ることができる。なお、色連結領域（色領域）とは、同色と判断される連結画素により構成される領域（同色画素が繋がっている領域）である。一方、イラストは２色より多い複数色で構成されるものが多く、複数の色領域間の境界線の扱い方が問題となる。例えば２値画像での処理と同様に、多色画像から検出した色領域それぞれの輪郭を関数近似すると、隣接する色領域それぞれの輪郭が個別に近似されることになる。この場合、近似誤差によって、隣接する色領域間に共通の境界線部分に対して、２つの異なる近似曲線が得られてしまい、隙間や重なりが生じる問題があった。この様子を図３に示す。図３（ａ）は入力画像から色領域それぞれの輪郭形状を抽出した例を示している。背景の白地部分の領域を数えないものとすると、他の色領域に隣接する（他領域との境界線を持つ）色領域が３つ存在している。図３（ｂ）は、図３（ａ）の輪郭情報を色領域毎に個別に関数近似した場合の処理結果を示しており、色領域間に隙間や重なりが生じている。
【０００５】
上記の問題を踏まえ、色領域間に隙間を生じさせないベクトル化法が提案されている。特許文献５では色差が一定以上ある画素同士の境界を輪郭として追跡し、色領域の交点（以降、『色交点』と称する）に突き当たる度に分岐して探索を繰り返し行う。色領域の交点間で区切られた部分輪郭それぞれを関数近似の処理単位とし、関数近似後のデータを再度つなぎ合わせて各色領域のベクトルデータを生成するため、境界線に共通の関数近似結果が適用され隙間や重なりが原理的に生じない。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特登録３０２６５９２
【特許文献２】特登録４３７８２０８
【特許文献３】特開２００７−２９３８２９
【特許文献４】特開２００６−３４４０６９
【特許文献５】特開２００６−０３１２４５
【非特許文献】
【０００７】
【非特許文献１】鳥脇著“画像理解のためのディジタル画像処理（２）”初版３刷，ＩＳＢＮ４−７８５６−２００４−８，昭晃堂，１９９３年４月２０日発行，Ｐ．６６−Ｐ．７９
【発明の概要】
【発明が解決しようとする課題】
【０００８】
非特許文献１は、色領域の境界線を追跡することにより、色領域の境界線を抽出する。境界線は異なる色領域各々を図形と考えた場合に、当該図形の内部の点と外部の点との境界の集合を指す。境界線の追跡方法としては、非特許文献１の６８ページに記載されているように、画素追跡型、辺追跡型、頂点追跡型が知られている。ここでは、画像中で隣接する色領域間に隙間のない共通の輪郭線が定義されるという点で頂点追跡型に絞って話を進める。頂点追跡による境界線追跡法としては、特許文献５による境界線追跡が知られている。これによれば、抽出対象である色領域の探索開始点を探した後、抽出対象を右側または左側に決めて色境界をたどっていく。色交点にぶつかったらこれまで抽出した境界線を記録し、新たな抽出を開始する。こうして全ての境界線が抽出し終わるまで追跡を繰り返し行うというものである。
【０００９】
この方法にはいくつかの問題点がある。まず色交点に遭遇した時の探索順（複数ある時にどれを優先するか）が何通りか存在する。抽出順の選び方によっては境界線を並べて輪郭を再構成することが難しくなったり、抽出漏れが起きやすくなったりする。また追跡の方向が領域形状によって変わるため、メモリ上の画素情報を参照する際にキャッシュが効かず、処理速度が低下することも起こりうる。
【００１０】
なお、本出願人は、上述したような境界線を順に追跡していく方法を用いずに、境界線を抽出する方法として、以下の手法を考えている。本出願人が提案している特願２０１０−２３４０１２では、まず、ラスター走査で各色領域毎に境界線を構成する最小単位となる線素のテーブルを作成後、当該テーブルを走査して輪郭を抽出する。そして、抽出した色領域の輪郭をたどることで、隣接する他の色領域とで構成される色交点を検知し、輪郭を色交点ごとに分割する。この方法は、境界線の抽出漏れや境界線の再構成順序の問題を解決することができ、ラスター走査とテーブル走査で高速に輪郭を抽出する方法である。しかしながら、色交点も考慮した境界線を求めるには、抽出した輪郭を再度辿りなおすために、追跡と同じように輪郭を２度探索することになり、さらなる改良の余地が残されていた。
【課題を解決するための手段】
【００１１】
そこで、本発明では、線素を構成する輪郭点を抽出する際に色交点をも検知し、色交点情報を輪郭点情報と共に記録することで境界線を抽出するように構成する。
すなわち、本発明の画像処理装置は、所定サイズの画素マトリクスで多値画像をラスター走査し、当該画素マトリクス内の複数画素の状態に応じて、異なる値を有する画素間の境界を形成する輪郭を区分する色交点であるか否かの判定と、当該異なる値をもつ画素間の境界を形成する輪郭点の抽出とを行う色交点判定・輪郭点抽出手段と、前記色交点判定・輪郭点抽出手段で判定された色交点と抽出された輪郭点とを用いて、当該色交点ごとに区分した輪郭線で構成される輪郭情報を生成する輪郭情報再構成手段と、を有することを特徴とする。
【発明の効果】
【００１２】
１回のラスター走査で輪郭点と色交点とを取得するようにしたので、各領域の輪郭を示す輪郭情報（境界線）の生成を高速に行うことができる。
【図面の簡単な説明】
【００１３】
【図１】本実施形態における情報処理装置のメイン処理ブロック図。
【図２】本実施形態における情報処理装置のブロック図。
【図３】関数近似によって色領域に重なりや隙間が生じる例を説明する図。
【図４】本実施形態におけるフローチャート。
【図５】３×３の画素マトリクスでの画像からラスター走査を説明する図。
【図６】注目ベクトルと、その流入ベクトル、流出ベクトルとの関係を示す図。
【図７】一点のみで構成されるラベルのベクトル情報テーブルによる記録を示す図。
【図８】３×３の画素マトリクスの中心画素とその上下左右の４近傍画素を表す図。
【図９】ケース１から１６の各場合の色交点判定・輪郭点抽出処理を説明する図。
【図１０】色交点判定を伴わない輪郭点の抽出を説明する図。
【図１１】色交点判定を伴う輪郭点の抽出を説明する図。
【図１２】色交点判定を伴う輪郭点抽出時の色交点判定を説明する図。
【図１３】色交点判定し、色交点の場合のみ輪郭点を抽出する処理を説明する図。
【図１４】ステップＳ１２００での処理の流れを、具体例を元にして説明する図。
【図１５】具体例の場合での流入ベクトル未定水平ベクトルテーブル、流出ベクトル未定水平ベクトルテーブル、流入ベクトル未定垂直ベクトルテーブル、流出ベクトル未定垂直ベクトルテーブルの４種のテーブルの状態を表す図。
【図１６】２×２のウィンドウ走査で起こりえる４画素のパターンを示す図。
【発明を実施するための形態】
【００１４】
［実施例１］
本実施形態の画像処理装置の構成例について、図２のブロック図を参照して説明する。画像処理装置は、汎用のコンピュータを用いて実現することが可能である。図２において、ＣＰＵ７は装置全体を制御するプロセッサである。ＲＯＭ６は変更を必要としないプログラムやパラメータを格納するメモリである。ＲＡＭ５は外部装置等から供給されるプログラムやデータを一時記憶するメモリである。スキャナ１は、文書等を光電走査して電子的な画像データを得る。入出力Ｉ／Ｏ３はスキャナ１と画像処理装置とを接続するインタフェースである。画像メモリ２はスキャナ１で読み取られた画像データ等を保持する。外部記憶装置１２は固定して設置されたハードディスクやメモリカード、光ディスク等の記憶媒体である。また、Ｉ／Ｏ１３は外部記憶装置１２と画像処理装置とを接続するインタフェースである。Ｉ／Ｏ１５は、マウス等のポインティングデバイス１０やキーボード９等の入力デバイスと画像処理装置を接続するインタフェースである。映像Ｉ／Ｏ１４は、画像処理装置の保持するデータや供給されたデータを表示するためのディスプレイ８と画像処理装置とを接続するインタフェースである。通信Ｉ／Ｆ４は、インターネット等のネットワーク回線（不図示）に接続するためのインタフェースである。システムバス１１は各ユニットを通信可能に接続するバスである。
【００１５】
以下、ＣＰＵ７上で実行されるプログラムにより本発明を実現する処理手順を、図１のブロック図と図４のフローチャートを用いて説明する。
【００１６】
ステップＳ１０００で処理を開始すると、処理対象となる画像領域を含む画像データを入力する。画像入力に関しては、スキャナ１にて読み取られた画像データを画像入出力Ｉ／Ｏ３を介して画像メモリ２に入力する。また、通信Ｉ／Ｆ４を介して、装置外部より前記処理対象となる画像領域を含む画像を入力してもよく、あるいは、外部記憶装置１２に予め記憶される画像データをＩ／Ｏ１３を介して読み込むものであってもよい。得られた入力画像は、画像メモリ２上に保持される。
【００１７】
スキャナなどの入力手段を用いた場合、入力画像にノイズが重畳され、代表色の特定が難しいことが起こりうる。この場合、色領域分割処理を行うことで、近い画素値を持つ画素が同じ色情報となるようにまとめるようにするのが望ましい。そこでステップＳ１０００ではＣＰＵ７が入力画像に対して色領域分割処理を施すことで、上記問題を解消することができる。ここでの色領域分割処理については、本発明が適用可能であれば、いずれの方法を用いてもよい。例えば特許文献４で開示されている手法では、入力画像中の画素から色情報を元にクラスタを構成し、類似するクラスタやノイズと思われるクラスタを統合することでスキャンノイズを除去する。本実施形態においては、このような方法を適用することで、スキャン画像入力等で生じるノイズ除去している。以上の処理は図１における画像入力手段１０１を実現している。
【００１８】
次にステップＳ１０００で読み取った画像データに対して、ステップＳ１１００でラベリング処理（領域番号（ラベル）付与処理）を行うことにより、画像データ中の同色と判断される領域に同一の領域番号を付与して、色領域を抽出する。ラベリング処理は、８連結接続で考える場合、上下左右斜めの８方向のいずれかで隣接（連結）する同じ画素値を有する画素集合に同一の番号を付与する処理である。ここでは各色領域を後処理で識別できるようにするための番号（以下、領域番号）を、各色領域を構成する各画素に付与する。ラベリング処理（領域番号（ラベル）付与処理）された画像を、ラベル画像と呼ぶこととする。ラベリング処理では後で行う輪郭抽出処理と同じ連結状態となるラベリング処理を行う必要がある。本実施形態では、８連結接続で輪郭を抽出する例を用いて説明するので、ラベリング処理も８連結接続として処理し、上下左右斜め方向のいずれかで隣接する同じ画素値を有する画素集合に同一の番号を付与することになる。なお、ステップＳ１１００の処理は図１における領域番号付与手段１０２を実現している。
【００１９】
ステップＳ１２００では、ステップ１１００で得られたラベル画像を入力画像として、図５（ａ）に示すような３×３の画素マトリクス状ウィンドウの中心（同図中「ｘ」で表示）を着目画素として、図５（ｂ）に示すように入力画像の左上からラスター走査を行なう。そして、各ラベル領域毎にそのラベル領域の輪郭を構成する水平方向の線素と垂直方向の線素の切り替わる位置を、それぞれの線素の始点（以降、単に輪郭点とも称する）として抽出する処理を行う。加えて、それら輪郭点が色交点であるか否かの判定する色交点判定処理を行う。それら線素上に存在する可能性のある色交点の存在判定の結果、色交点が存在する場合には、その位置に色交点である輪郭点の抽出処理を行う。尚、抽出される垂直・水平方向の線素を、それぞれ垂直ベクトル、水平ベクトルと呼ぶ。また、線素上に存在が判定された色交点も、当該線素が水平の場合には新たな水平ベクトルの始点となり、同様に当該線素が垂直な場合には垂直ベクトルの始点となる。輪郭点抽出処理、輪郭点の色交点判定、線素上での色交点判定と色交点である位置での輪郭点抽出処理を総称して、色交点判定・輪郭点抽出処理と呼ぶ。
【００２０】
本実施形態では、水平ベクトルと垂直ベクトルは進行方向に対して、着目画素の属するラベル領域が右側に来るよう抽出される。この結果、抽出される外輪郭（輪郭抽出対象のラベル領域を外側から取り囲む輪郭）は時計回りとなる。また、内輪郭（輪郭抽出対象のラベル領域領域に周囲を取り囲まれる孔の境界に沿って、当該ラベル領域が右側に来るように抽出される内部の輪郭）は反時計回りとなる。座標系については、特許文献１での説明と同様に、本実施例では、入力画像の各画素の座標値を、主走査方向をｘ軸（右向きが正方向）、副走査方向をｙ軸（下向きが正方向）とし、それぞれ整数値で表現するものとして話を進める。また、抽出される線素の始点や色交点の座標値は、画素と画素の中間の位置に抽出されるので、これらの座標値を整数値として扱うため、当該座標値を２倍にした値を対象座標として抽出する。即ち、ｍ画素×ｎ画素の画像は、２ｍ×２ｎの正の偶数（整数）の座標表現で表し、抽出される線素の始点や色交点の座標値が、整数値（奇数）となるようにして説明する。以降、第ｊ番目のラスタの第ｉ番目の画素位置を（２ｉ，２ｊ）（ｉ，ｊは正の整数で、ｉ≦ｍ，ｊ≦ｎ）で表現する。
【００２１】
抽出した垂直ベクトルの始点や水平ベクトルの始点の情報には、それぞれに流入元となるベクトルの始点と、流出先となるベクトルの始点の情報への接続情報を付して記録する。以降、流入元となるベクトルの始点を単に流入元、流出先となるベクトル始点を流出先と称し、流入元となるベクトルを流出ベクトル、流出先となるベクトルを流出先と称する。着目しているベクトルの始点は、流入ベクトルの終点でもあり、かつ、流出ベクトルの始点は、着目しているベクトルの終点でもある。この様子を図６に一例として示した。同図は、注目ベクトルが水平ベクトルである場合を表記していて、６１が注目ベクトル、６２が注目ベクトル６１の始点であり、かつ、流入ベクトル６３の終点でもある。６４が流入ベクトル６３の始点（流入元）、６５が流出ベクトル、６６が流出ベクトル６５の始点（流出先）であり、かつ、注目ベクトル６１の終点でもある。ここで、垂直ベクトルの始点を白抜き三角印、水平ベクトルの始点を白抜き丸印で表記した。
【００２２】
これらのベクトルはラベルごとに１つのベクトル情報テーブルに記録して管理する。例として、図７に、注目するラベルが一点（１画素）のみで構成されるラベルである場合の前記ベクトル情報テーブルによる記録を示した。図７（ａ）は、一点のみで構成されるラベルを中心にその周囲８画素を含めて３×３のラベル画像を表現しており、周囲８画素は中心画素のラベルとは異なるラベルをもつ画素である。同ラベルは、水平ベクトル（ｒ）、垂直ベクトル（ｒ＋２）、水平ベクトル（ｒ＋３）、垂直ベクトル（ｒ＋１）の４本の線素で囲まれている。同図（ｂ）は、この様子を記録したベクトル情報テーブルである。図７（ｂ）のテーブルにおいて、各ベクトルは横一行で１本の線素を表現している。ベクトルカウンタ欄は、抽出された順にカウントアップされながら定まるベクトル番号（ベクトルインデックスやテーブルインデックスとも称すことがある）である。ベクトル番号は、基本的に、輪郭点、もしくは、色交点として抽出された順に昇順に定められる番号である。図７（ａ）の状態の説明におけるｒ，ｒ＋１，ｒ＋２，ｒ＋３も、抽出された順に定められるベクトル番号ではあるが、このベクトル番号をもって、各ベクトルを特定するベクトルの名称としても用いるものとする。なお、説明の便宜上、ベクトル番号の初期値としてｒを用いたが、初期値が０から始まるものとすると、これらベクトル番号は、０、１、２、３となる。始点欄は、Ｘ座標欄とＹ座標欄から構成され、それぞれ、各ベクトルの始点のＸ座標値とＹ座標値を格納する。図７（ｂ）では、中心の画素の座標値が（２ｉ，２ｊ）であったとして、各ベクトルの始点の座標値を記載してある。流入ベクトル欄は、当該ベクトル番号のベクトルの流入元となるベクトルのベクトル番号が格納される。同様に、流出ベクトル欄は、流出先となるベクトルのベクトル番号が格納される。色交点フラグ欄は、同ベクトル番号のベクトルが色交点である場合には“ＴＲＵＥ”が、色交点ではない場合には“ＦＡＬＳＥ”がはいるフラグ領域である。未使用フラグ欄は、ステップＳ１３００の輪郭情報再構成処理で参照するフラグ領域であり、これに関しては、追ってさらに説明を加える。
【００２３】
３×３のウィンドウでは、図８に示したように、３×３のウィンドウの中心である着目画素と着目画素の上下左右の４近傍画素に着目し、着目画素の周辺での輪郭ベクトルの始点や色交点の抽出、及び、それらの局所的な接続関係を求める。まず、着目画素Ｐ０が輪郭抽出対象のラベル領域の画素である場合にはＲ０＝１とした上で、着目画素Ｐ０と、図７に示すＰ１、Ｐ２、Ｐ３、Ｐ４の４近傍の各画素とを比較し、着目画素の所属ラベルと所属ラベルが一致した画素の位置Ｐｋ（ｋ＝１，２，３，４）の値Ｒｋを１とし、一致しない画素位置ではＲｋを０とする。そして、これらＲ０、Ｒ１、Ｒ２、Ｒ３に係数をかけて定義する以下の式によりＲを求める。
【００２４】
Ｒ＝Ｒ０＋１×Ｒ１＋２×Ｒ２＋４×Ｒ３＋８×Ｒ４
尚、着目画素Ｐ０が輪郭抽出対象のラベル領域の画素である場合には、４近傍画素の状態にかかわらず、Ｒ＝０とする。
【００２５】
上記Ｒは、着目画素と着目画素の上下左右の４近傍画素の所属ラベルの状態によって、０〜１６の値を持つのに対応させて、それぞれの場合をケース０からケース１６で区別する。各ケースに応じて所定の色交点判定・輪郭点抽出処理を行う。ケース０では、色交点判定・輪郭点抽出は全くなされない。
【００２６】
ケース１〜ケース１６の場合の色交点判定・輪郭点抽出処理を図９に示した。図９においては、中心画素のラベルに対して、その左右上下の４画素がそれぞれ同じラベルか否かで表現してあり、同４画素のうち、中心画素のラベルと同じラベルの画素は中心画素と同じ塗りつぶしパターンで表記し、そうでないものは塗りつぶしていない。尚、図９における中心画素の左上、左下、右上、右下の位置にある画素は、ケース１〜１６のいずれに属するかを分類する上では関わりをもたない非注目画素であることから、図９ではどんなラベルを持つ画素かによらず塗りつぶしのない状態で表記してある。図９（ａ）から図９（ｐ）までの１６種類の３×３のウィンドウの状態にあわせて、それぞれ、ａからｐまでのアルファベット順に、ケース１からケース１６の処理内容をケース番号の昇順に対応させて表記してある。図９において、白抜き丸印は、色交点であるか否かの判断をすることなしに、色交点ではない水平ベクトルの始点の抽出処理をする輪郭点候補位置である。白抜き三角印は、色交点であるか否かの判断をすることなしに、色交点ではない垂直ベクトルの始点の抽出処理をする輪郭点候補位置である。横向き矢印を伴った黒塗り丸印は、色交点であるか否かの判断を伴う水平ベクトルの始点の抽出処理をする輪郭点候補位置である。縦向き矢印を伴った黒塗り三角印は、色交点であるか否かの判断を伴う垂直ベクトルの始点の抽出処理をする輪郭点候補位置である。矢印の伴わない黒塗り丸印は、色交点か否かを判定し、色交点である場合には、色交点である水平ベクトルの始点を抽出する候補位置である。矢印の伴わない黒塗り三角印は、色交点であるか否かを判定し、色交点である場合には、色交点である垂直ベクトルの始点を抽出する候補位置である。実線矢印は、この矢印の位置にベクトルが抽出される場合には、流出先となる抽出済みのベクトルが存在するものを意味している。破線矢印は、この矢印の位置にベクトルが抽出された場合、流出先となるべきベクトルが、まだ抽出されていない状態、即ち、流出先が未定の状態で抽出されることになるベクトルであることを意味している。尚、以降、水平、垂直共に、ベクトルの始点の抽出のことを、単に、ベクトルの抽出と表現することがある。
【００２７】
図１０を用いて、色交点であるか否かの判断を伴わない輪郭点の抽出を説明する。図１０は、ケース１６での処理内容を示す図であり、中心画素のラベルと、その上下左右の４画素のラベルは全て同じ状態にある。図１０（ａ）は、図１０内で改めてケース１６のパターンを示すために、図９（ｐ）を再掲したものである。
【００２８】
まず、図１０（ｂ）に示すように、中心画素（座標値が（２ｉ，２ｊ）であるとする）の左上に垂直ベクトルの始点が存在するか否かを判定する。即ち、中心画素の左上の画素（座標値は（２ｉ−２，２ｊ−２））が、中心画素のラベルと同じラベルであるか否かを判定し、異なる場合には、図１０（ｃ）に示すように中心画素の左上の位置（座標値は（２ｉ−１，２ｊ−１））に垂直ベクトルを抽出する。同じ場合には、図１０（ｄ）に示すように、同位置にベクトルは抽出されない。
【００２９】
次に、図１０（ｅ）に示すように、中心画素の左下に水平ベクトルの始点が存在するか否かを判定する。即ち、中心画素の左下の画素（座標値は（２ｉ−２，２ｊ＋２））が、中心画素のラベルと同じラベルであるか否かを判定し、異なる場合には、図１０（ｆ）に示すように中心画素の左下の位置（座標値は（２ｉ−１，２ｊ＋１））に水平ベクトルを抽出する。同じ場合には、同図（ｇ）に示すように、同位置にベクトルは抽出しない。
【００３０】
次に、図１０（ｈ）に示すように、中心画素の右上に水平ベクトルの始点が存在するか否かを判定する。即ち、中心画素の右上の画素（座標値は（２ｉ＋２，２ｊ−２））が、中心画素のラベルと同じラベルであるか否かを判定し、異なる場合には、図１０（ｉ）に示すように中心画素の右上の位置（座標値は（２ｉ＋１，２ｊ−１））に水平ベクトルを抽出する。同じ場合には、図１０（ｊ）に示すように、同位置にベクトルは抽出しない。
【００３１】
さらに、図１０（ｋ）に示すように、中心画素の右下に垂直ベクトルの始点が存在するか否かを判定する。即ち、中心画素の右下の画素（座標値は（２ｉ＋２，２ｊ＋２））が、中心画素のラベルと同じラベルであるか否かを判定し、異なる場合には、図１０（ｌ）に示すように中心画素の右下の位置（座標値は（２ｉ＋１，２ｊ＋１））に垂直ベクトルを抽出する。同じ場合には、図１０（ｍ）に示すように、同位置にベクトルは抽出しない。
【００３２】
以上、図１０を用いて、ケース１６での処理内容と、色交点であるか否かの判断を伴わない輪郭点の抽出について説明した。
【００３３】
ここで、ベクトルを抽出した際のベクトル情報テーブル上でのデータの扱いについて、さらに説明を加える。注目するラベル領域（中心画素の属するラベル領域）に対する（図７（ｂ）を用いて、上述した形式の）ベクトル情報テーブルにおいて、それまで既に見つけられていたベクトル情報の次の行に相当するテーブル領域にベクトル情報を追記する。
【００３４】
まず、該当行のベクトルカウンタ欄に、抽出された順に応じたベクトル番号を書き込む。
【００３５】
次に、抽出されたベクトルの座標値（Ｘ座標値、Ｙ座標値）を、始点のＸ座標値とＹ座標値の欄に書き込む。
【００３６】
流入ベクトル欄と流出ベクトル欄については、図１０（ｌ）のケースのように、抽出したベクトルの流出先や流入元が、まだ走査されていない領域（以降、未走査領域とも称する）方向にある場合と、図１０（ｃ）のように、既に走査し終えた領域（以降、既走査領域とも称する）方向にある場合とで扱いが異なる。未走査領域方向に流入元や流出先がある場合には、前述のベクトル情報テーブルとは別に、流入ベクトルが未定のベクトルの情報を管理するテーブルと流出ベクトルが未定のベクトル情報を管理するテーブルとをそれぞれ別途用いて処理する。垂直ベクトル用の流入ベクトル未定のベクトルを管理するテーブルを、流入ベクトル未定垂直ベクトルテーブルと称する。また、垂直ベクトル用の流出ベクトル未定のベクトルを管理するテーブルを、流出ベクトル未定垂直ベクトルテーブルと称する。水平ベクトル用にも同様に、流入ベクトル未定水平ベクトルテーブルと流出ベクトル未定水平ベクトルと称するテーブルをそれぞれ用いる。それぞれのテーブルには、該当するベクトル番号を検出した順に格納していくものとする。図１０（ｌ）のケースの場合には、ベクトル情報テーブルの流入ベクトル欄には、その時点では何も記録せず、流入ベクトル未定垂直ベクトルテーブルに、ベクトル情報ベクトル上でのベクトル番号を追記して同テーブルを更新する。同様に、ベクトル情報テーブルの流出ベクトル欄には、その時点では何も記録せず、流出ベクトル未定垂直ベクトルテーブルに、ベクトル情報ベクトル上でのベクトル番号を追記して同テーブルを更新する。尚、図１０（ｉ）で示される水平ベクトルを抽出する場合の流出ベクトル欄も同様に、その時点では何も記入せず、流出ベクトル未定水平ベクトルにそのベクトル番号を追記して同テーブルを更新する。図１０（ｆ）で示される水平ベクトルが抽出される際は、その時点では流入ベクトル欄に何も記入せず、流入ベクトル未定水平ベクトルテーブルにそのベクトル番号を記入して同テーブルを更新する。
【００３７】
一方、上述の図１０（ｃ）の垂直ベクトルの様に、流入元や流出先が既走査領域方向にある場合は、上記の流入ベクトルが未定のベクトルの情報を管理するテーブルや流出ベクトルが未定のベクトル情報を管理するテーブル参照して、その流入元や流出先を定める。
【００３８】
流入元が既走査領域方向にある垂直ベクトルの流入元は、流出先が未定の水平ベクトルである。よって、このような垂直ベクトルの流入元を定める場合には、流出ベクトル未定水平ベクトルテーブルを参照する。このテーブルに格納されているベクトル番号をもつベクトルの中で、当該垂直ベクトルの始点と同じＹ座標値を持つベクトルを該当するラベルのベクトル情報テーブルから探し出す。ベクトル情報テーブルの当該垂直ベクトルの流入ベクトル欄に、得られた水平ベクトルのベクトル番号を記入し、それまで未定であったその水平ベクトルの流出ベクトル欄に、当該垂直ベクトルのベクトル番号を記載する。また、流出ベクトル未定水平ベクトルテーブルからその水平ベクトルのベクトル番号を削除して同テーブルを更新する。
【００３９】
次に、当該垂直ベクトルの様に、流出先が既走査方向にある垂直ベクトルの流出先を定める場合を説明する。流出先が既走査領域方向にある垂直ベクトルの流出先は、流入元が未定の水平ベクトルか、または、後述する色交点位置に抽出された垂直ベクトルの中で流入元が未定のものである。よって、このような垂直ベクトルの流出先を定める場合には、流入ベクトル未定水平ベクトルテーブルと流入ベクトル未定垂直ベクトルテーブルの両方を参照する。これらテーブルに格納されているベクトル番号をもつベクトルの中で、当該垂直ベクトルの始点と同じＸ座標値を持つベクトルを該当するラベルのベクトル情報テーブルから探し出す。複数見つかった場合には、そのＹ座標値が当該垂直ベクトルのＹ座標値よりも小さいものの中で最も大きなＹ座標値をもつもの（即ち、既走査領域の中で最も近くにある流入元未定の輪郭点）を選ぶ。ベクトル情報テーブルの当該垂直ベクトルの流出ベクトル欄に、得られた水平、もしくは、垂直ベクトルのベクトル番号を記入し、それまで未定であったそのベクトルの流入ベクトル欄に、当該垂直ベクトルのベクトル番号を記載する。また、得られたベクトルの番号が記載されていた、流入ベクトル未定水平ベクトルテーブル、もしくは、流入ベクトル未定垂直ベクトルテーブルからそのベクトルのベクトル番号を削除して同テーブルを更新する。
【００４０】
尚、図１０（ｉ）で示される水平ベクトルの様に、流入元が既走査領域方向にある水平ベクトルの流入元は、流出先が未定の垂直ベクトルである。よって、このような水平ベクトルの流入元を定める場合には、流出ベクトル未定垂直ベクトルテーブルを参照する。このテーブルに格納されているベクトル番号をもつベクトルの中で、当該水平ベクトルの始点と同じＸ座標値を持つベクトルを該当するラベルのベクトル情報テーブルから探し出す。ベクトル情報テーブルの当該水平ベクトルの流入ベクトル欄に、得られた垂直ベクトルのベクトル番号を記入し、それまで未定であったその垂直ベクトルの流出ベクトル欄に、当該水平ベクトルのベクトル番号を記載する。また、流出ベクトル未定垂直ベクトルテーブルからその垂直ベクトルのベクトル番号を削除して同テーブルを更新する。
【００４１】
次に、図１０（ｆ）で示される水平ベクトルの様に、流出先が既走査方向にある水平ベクトルの流出先を定める場合を説明する。流出先が既走査領域方向にある水平ベクトルの流出先は、流入元が未定の垂直ベクトルか、または、後述する色交点位置に抽出された水平ベクトルの中で流入元が未定のものである。よって、このような水平ベクトルの流出先を定める場合には、流入ベクトル未定水平ベクトルテーブルと流入ベクトル未定垂直ベクトルテーブルの両方を参照する。これらテーブルに格納されているベクトル番号をもつベクトルの中で、当該水平ベクトルの始点と同じＹ座標値を持つベクトルを該当するラベルのベクトル情報テーブルから探し出す。万が一、複数見つかる場合には、そのＸ座標値が当該水平ベクトルのＸ座標値よりも小さいものの中で最も大きなＸ座標値をもつもの（即ち、既走査領域の中で最も近くにある流入元未定の輪郭点）を選ぶ。ベクトル情報テーブルの当該水平ベクトルの流出ベクトル欄に、得られた水平、もしくは、垂直ベクトルのベクトル番号を記入し、それまで未定であったそのベクトルの流入ベクトル欄に、当該水平ベクトルのベクトル番号を記載する。また、得られたベクトルの番号が記載されていた、流入ベクトル未定水平ベクトルテーブル、もしくは、流入ベクトル未定垂直ベクトルテーブルからそのベクトルのベクトル番号を削除して同テーブルを更新する。
【００４２】
色交点フラグ欄には、追記中のベクトルが色交点である場合には、ＴＲＵＥを記録し、色交点ではない場合にＦＡＬＳＥを記録する。ケース１６では、色交点となる輪郭点はそもそも発生しないパターンであり、色交点であるか否かの判断は不要であった。このため、上述の図１０（ｃ）、図１０（ｆ）、図１０（ｉ）、図１０（ｌ）で抽出される輪郭点は、色交点ではないため、いずれの場合も色交点フラグ欄はＦＡＬＳＥを記録する。
【００４３】
未使用フラグ欄は、ステップＳ１２００では、ＴＲＵＥを記録する。同欄は、ステップＳ１３００の輪郭情報再構成処理で参照するフラグ領域であり、追ってさらに説明を加える。
【００４４】
次に、図１１と図１２を用いて、色交点であるかの判断（色交点判定）を伴う輪郭点の抽出とその色交点判定を説明する。
【００４５】
図１１は、ケース１での処理内容を示す図であり、中心画素のラベルと、その上下左右の４画素のラベルは全て異なる状態にある。図１１（ａ）は、図１１内で改めてケース１のパターンを示すために、図９（ａ）を再掲したものである。
【００４６】
まず、図１１（ｂ）に示すように、中心画素（座標値が（２ｉ，２ｊ）であるとする）の左上の位置（座標値は（２ｉ−１，２ｊ−１））に水平ベクトルの始点を抽出する。この水平ベクトルは、中心画素の上の画素が中心画素とはことなるラベルをもつので、流出先は未定のベクトルであるが、中心画素とその左上、上、左の４画素でなる２×２の領域の各画素のラベルの状態により、流入元が未定か確定するかは異なるものとなる。また、中心画素とその左上、上、左の４画素でなる２×２の領域の各画素のラベルの状態により、中心画素の左上の位置の水平ベクトルが、色交点となるか否かも異なる。図１１（ｃ）と図１１（ｄ）はともに、中心画素とその左上の画素のラベルが異なる場合をあらわしている。これらの場合には、当該水平ベクトルの流入ベクトルも未走査領域にあることになるので、流入ベクトルも流出ベクトルも未定の水平ベクトルとなる。一方、図１１（ｅ）と図１１（ｆ）はともに、中心画素とその左上の画素のラベルが同じ場合をあらわしている。これらの場合には、当該水平ベクトルの流入ベクトルは既走査領域に存在することになるので、流入ベクトルは確定していて、流出ベクトルは未走の水平ベクトルとなる。尚、当該水平ベクトルが、流入ベクトルも流出ベクトルも未定の水平ベクトルであっても、色交点である場合とない場合とがあり得る。この様子を図１１（ｃ）と図１１（ｄ）に示した。図１１（ｃ）は、当該水平ベクトルの始点が色交点ではない場合であり、白抜き丸印で表わした。図１１（ｄ）は、当該水平ベクトルの始点が色交点の場合であり、右上がり斜線で塗りつぶした丸印で表わした。また、該水平ベクトルが、流入ベクトルは確定していて、流出ベクトルは未走の水平ベクトルの場合も同様に、色交点である場合とない場合とがあり得る。この様子を図１１（ｅ）と図１１（ｆ）に示した。図１１（ｅ）は、当該水平ベクトルの始点が色交点ではない場合であり、白抜き丸印で表わした。図１１（ｆ）は、当該水平ベクトルの始点が色交点の場合であり、右上がり斜線で塗りつぶした丸印で表わした。
【００４７】
この位置（中心画素の左上の位置）の水平ベクトルの始点の色交点判定について、図１２（ａ）〜（ｆ）を用いて説明する。図１２（ａ）自体は図９（ｅ）、即ち、ケース５の状態をもとに表記したものであるが、中心画素の左上の位置の水平ベクトルの始点の色交点判定という意味では、図１１（ｂ）で表わされる、ケース１の中の同位置と同じ処理を行うものである。さて、図１２（ａ）に示す様に、中心画素とその左上、上、左の４画素でなる２×２の領域の各画素のラベルの状態により、色交点判定が行われる。図１２（ｂ）〜（ｄ）は、いずれも中心画素とその左上の画素のラベルが異なる場合を示している。これらの場合には、２×２の中の残り２画素（中心画素の上の画素と左の画素）のラベルも調べる。
【００４８】
中心画素以外の３画素が全て同一のラベルである場合（図１２（ｂ））は、２色の領域でしか接していない状態なので、色交点ではない輪郭点と判断する。
【００４９】
また、中心画素の上と左が同一のラベルで、左上の画素はこれらとは異なるラベルの場合（不図示）には、上と左の画素が８連結状態にあり、中心画素と左上の画素は非連結の状態にある。この場合は、当該水平ベクトルの始点位置では２色の領域でしか接していない状態にあるものとみなし、色交点ではない輪郭点とする。
【００５０】
また、図１２（ｃ）に示す様に、中心画素の左上と左の画素が同ラベルで、残りの１画素（上の画素）が中心画素とも他の２画素とも異なるラベルの場合には、３色の領域で接しているので色交点である輪郭点とする。
【００５１】
また、中心画素の左上と上の画素が同ラベルで、残りの１画素（左の画素）が注目画素とも他の２画素とも異なるラベルの場合（不図示）にも、３色の領域で接しているので色交点である輪郭点とする。即ち、注目画素以外の３画素のうち、縦または横につながる２画素が同ラベルで、残りの１画素が注目画素とも他の２画素とも異なるラベルの場合には、色交点である輪郭点とする。
【００５２】
また、図１２（ｄ）に示す様に、中心画素以外の３画素がいずれも互いに異なるラベルである場合には、４色の領域が接する交点となっているので、色交点とする。
【００５３】
図１２（ｅ）と（ｆ）は、中心画素と左上の画素のラベルが同じ場合、即ち、３×３の９画素領域中における２×２の４画素領域の中で、中心画素とその対角画素のラベルが同じ場合を示している。残りの２画素が、中心画素のラベルとは異なるラベルながら、同ラベルとなっている場合（図１２（ｅ））は、どちらの対角画素の組も８連結状態にあり、この場合にはどちらの連結状態も同等に扱う意味で、色交点とする。一方、図１２（ｆ）に示す様に、残りの２画素が互いに異なるラベルである場合、先に述べた不図示の場合同様、中心画素と左上の画素が８連結状態にあり、上と左の画素は非連結の状態にある。当該水平ベクトルの始点位置では２色の領域でしか接していない状態にあるものとみなし、色交点ではない輪郭点とする。
【００５４】
さて、ここまで図１１（ｂ）〜（ｆ）と図１２（ａ）〜（ｆ）を用いて、中心画素の左上の位置における、色交点であるかの判断（色交点判定）を伴う輪郭点の抽出とその色交点判定を説明した。一方、中心画素の左下の位置における色交点判定を伴う輪郭点の抽出と色交点判定も、流入元と流出先の扱いを含めて、抽出されるベクトルが垂直ベクトルの始点になる点とその位置が中心画素の左下であることを考慮する必要はあるものの、同様の処理内容となる。図１１（ｇ）〜（ｋ）と図１２（ｇ）〜（ｌ）が中心画素の左下の位置における色交点判定を伴う輪郭点の抽出と色交点判定を説明する図ではあるが、不図示の場合も含めて容易に適用可能であるため、これらを用いた詳述は省略する。以下、同様に、中心画素の右上の位置における色交点判定を伴う輪郭点の抽出と色交点判定は、図１１（ｌ）〜（ｐ）と図１２（ｍ）〜（ｒ）が中心画素の右上の位置における色交点判定を伴う輪郭点の抽出と色交点判定を説明する図である。抽出されるベクトルが垂直ベクトルの始点で、位置が中心画素の右上であることを考慮する必要はあるものの、不図示の場合も含めて容易に適用可能であるため、これらを用いた詳述は省略する。中心画素の右下の位置における色交点判定を伴う輪郭点の抽出と色交点判定は、図１１（ｑ）〜（ｕ）と図１２（ｓ）〜（ｘ）が中心画素の右下の位置における色交点判定を伴う輪郭点の抽出と色交点判定を説明する図である。抽出されるベクトルが水平ベクトルの始点で、位置が中心画素の右下であることを考慮する必要はあるものの、不図示の場合も含めて容易に適用可能であるため、これらを用いた詳述は省略する。
【００５５】
次に、図９の中の表記にあった、矢印を伴わない黒塗り丸印の位置での処理と、矢印を伴わない黒塗り三角印の位置での処理とを、図１３を用いて説明する。矢印の伴わない黒塗り丸印の位置での処理とは、色交点か否かを判定し、色交点である場合には、色交点である水平ベクトルの始点を抽出する処理である。矢印の伴わない黒塗り三角印の位置での処理とは、色交点であるか否かを判定し、色交点である場合には、色交点である垂直ベクトルの始点を抽出する処理である。
【００５６】
図１３（ａ）と図１３（ｅ）は、ケース１１（図９（ｋ））での処理に対応した図である。
【００５７】
図１３（ａ）は、中心画素とその左の画素が同ラベルで、中心画素の上の画素は中心画素と異なるラベルの場合に発生する処理を説明している。中心画素（座標値が（２ｉ，２ｊ）であるとする）の左上の位置（座標値は（２ｉ−１，２ｊ−１））が色交点であるか否かを判定し、色交点であるときのみ、水平ベクトルの始点を抽出する。中心画素の左上を中心とした２×２の４画素領域の画素パターンが、図１３（ｄ）に示す様に、中心画素とその左の画素以外の２画素が互いに異なるラベルで、かつ、中心画素の対角画素である左上の画素も中心画素とは異なるラベルである場合にのみ、左上の位置（座標値は（２ｉ−１，２ｊ−１））に色交点である水平ベクトルの始点を抽出する。この水平ベクトルは、流入元は既走査領域にあるので確定され、流出先は未走査領域にあるので未定となる。なお、図１３（ｂ）は、中心画素の対角位置が中心画素のラベルとは異なるラベルではあるものの、中心画素の上の画素と同じラベルである場合を示している。また、図１３（ｃ）は、中心画素とその左の画素以外の２画素が互いに異なるラベルではあるものの、中心画素の対角位置の画素が中心画素と同じラベルである場合を示している。図１３（ｂ）や図１３（ｃ）の場合には、中心画素の左上の位置は色交点ではなく、輪郭点は抽出されない。
【００５８】
図１３（ｅ）は、中心画素とその右の画素が同ラベルで、中心画素の下の画素は中心画素と異なるラベルの場合に発生する処理を説明している。中心画素（座標値が（２ｉ，２ｊ）であるとする）の右下の位置（座標値は（２ｉ＋１，２ｊ＋１））が色交点であるか否かを判定し、色交点であるときのみ、水平ベクトルの始点を抽出する。中心画素の右下を中心とした２×２の４画素領域の画素パターンが、図１３（ｈ）に示す様に、中心画素とその右の画素以外の２画素が互いに異なるラベルで、かつ、中心画素の対角画素である右下の画素も中心画素とは異なるラベルである場合にのみ、右下の位置（座標値は（２ｉ＋１，２ｊ＋１））に色交点である水平ベクトルの始点を抽出する。この水平ベクトルは、流入元は未走査領域にあるので未定となり、流出先は既走査領域にあるので確定される。なお、図１３（ｆ）は、中心画素の対角位置が中心画素のラベルとは異なるラベルではあるものの、中心画素の下の画素と同じラベルである場合を示している。図１３（ｇ）は、中心画素とその右の画素以外の２画素が互いに異なるラベルではあるものの、中心画素の対角位置の画素が中心画素と同じラベルである場合を示している。図１３（ｆ）や図１３（ｇ）の場合には、中心画素の右下の位置は色交点ではなく、輪郭点は抽出されない。
【００５９】
図１３（ｉ）と図１３（ｍ）は、ケース６（図９（ｆ））での処理に対応した図である。
【００６０】
図１３（ｉ）は、中心画素とその下の画素が同ラベルで、中心画素の左の画素は中心画素と異なるラベルの場合に発生する処理を説明している。中心画素（座標値が（２ｉ，２ｊ）であるとする）の左下の位置（座標値は（２ｉ−１，２ｊ＋１））が色交点であるか否かを判定し、色交点であるときのみ、垂直ベクトルの始点を抽出する。中心画素の左下を中心とした２×２の４画素領域の画素パターンが、図１３（ｌ）に示す様に、中心画素とその下の画素以外の２画素が互いに異なるラベルで、かつ、中心画素の対角画素である左下の画素も中心画素とは異なるラベルである場合にのみ、左下の位置（座標値は（２ｉ−１，２ｊ＋１））に色交点である垂直ベクトルの始点を抽出する。この垂直ベクトルは、流入元は未走査領域にあるので未定となり、流出先は既走査領域にあるので確定される。なお、図１３（ｊ）は、中心画素の対角位置が中心画素のラベルとは異なるラベルではあるものの、中心画素の左の画素と同じラベルである場合を示している。また、図１３（ｋ）は、中心画素とその下の画素以外の２画素が互いに異なるラベルではあるものの、中心画素の対角位置の画素が中心画素と同じラベルである場合を示している。図１３（ｊ）や図１３（ｋ）の場合には、中心画素の左下の位置は色交点ではなく、輪郭点は抽出されない。
【００６１】
図１３（ｍ）は、中心画素とその上の画素が同ラベルで、中心画素の右の画素は中心画素と異なるラベルの場合に発生する処理を説明している。中心画素（座標値が（２ｉ，２ｊ）であるとする）の右上の位置（座標値は（２ｉ＋１，２ｊ−１））が色交点であるか否かを判定し、色交点であるときのみ、垂直ベクトルの始点を抽出する。中心画素の右上を中心とした２×２の４画素領域の画素パターンが、図１３（ｐ）に示す様に、中心画素とその上の画素以外の２画素が互いに異なるラベルで、かつ、中心画素の対角画素である右上の画素も中心画素とは異なるラベルである場合にのみ、右上の位置（座標値は（２ｉ＋１，２ｊ−１））に色交点である垂直ベクトルの始点を抽出する。この垂直ベクトルは、流入元は既走査領域にあるので確定され、流出先は未走査領域にあるので未定となる。尚、図１３（ｎ）は、中心画素の対角位置が中心画素のラベルとは異なるラベルではあるものの、中心画素の右の画素と同じラベルである場合を示している。図１３（ｏ）は、中心画素とその上の画素以外の２画素が互いに異なるラベルではあるものの、中心画素の対角位置の画素が中心画素と同じラベルである場合を示している。図１３（ｎ）や図１３（ｏ）の場合には、中心画素の右上の位置は色交点ではなく、輪郭点は抽出されない。
【００６２】
先にも述べたが、色交点と判断された輪郭点に対応するベクトル情報テーブル中の色交点フラグ欄には、ＴＲＵＥを記録し、色交点ではない場合にＦＡＬＳＥを記録する。
【００６３】
尚、上述の図１０は図９（ｐ）に示したケース１６の処理、また、上述の図１１は図９（ａ）に示したケース１の処理、図１３（ａ）と図１３（ｅ）は図９（ｋ）に示したケース１１の処理、図１３（ｉ）と図１３（ｍ）は図９（ｆ）に示したケース６の処理に対応している。それ以外のケースは、これまで説明した、中心画素の左上、左下、右上、右下での、色交点であるか否かの判断を伴わない輪郭点の抽出処理、色交点判定を伴う輪郭点の抽出処理、色交点判定をして色交点の場合のみ輪郭点を抽出する処理の組合せで構成される。例えば、図９（ｂ）に示したケース２の場合は、中心画素の左下での色交点判定を伴う輪郭点の抽出処理と、同右上での色交点判定をして色交点の場合のみ輪郭点を抽出する処理、同右下での色交点判定を伴う輪郭点の抽出処理で構成される。また、図９（ｄ）に示したケース４では、中心画素の左下での色交点判定を伴う輪郭点の抽出処理と、同右上での色交点であるか否かの判断を伴わない輪郭点の抽出処理、同右下での色交点判定をして色交点の場合のみ輪郭点を抽出する処理で構成される。といった具合である。これ以外のケースに関しても、同様に処理を行えば構成可能であるため、これらに関する詳述は省略する。尚、各ケースにおいて構成に必要となる、中心画素の左上、左下、右上、右下での処理（ケースによって、存在しない位置もある）の順番は、ラスター走査の順における未走査領域と抽出した輪郭点の流入元と流出先の扱いを一貫させる必要がある。このため、本実施例では、左上、左下、右上、右下（ケースにより、処理が存在しない位置は、左記の順を飛ばす）の順に行うものとする。
【００６４】
以上により、ステップＳ１２００における色交点判定・輪郭点抽出処理の説明を終える。ステップＳ１２００における、ベクトル情報テーブルや流入ベクトル未定水平ベクトルテーブル、流入ベクトル未定垂直ベクトルテーブル、流出ベクトル未定水平テーブル、流出ベクトル未定垂直テーブルは、ＲＡＭ５上に不図示の領域として確保されるものである。なお、ステップＳ１２００の処理は図１における色交点判定・輪郭点抽出手段１０３を実現している。とりわけ、上記において、図１２及び図１３に基いて説明した色交点判定は、図１における色交点判定手段１０３１を実現しており、図１０、図１１及び図１３に基いて説明した輪郭点抽出処理は、図１における輪郭点抽出手段１０３２を実現している。
【００６５】
ステップＳ１２００での処理の流れを、図１４と図１５を用いて、具体例を元にして、さらに説明を加える。
【００６６】
図１５は上述した、流入ベクトル未定水平ベクトルテーブル、流出ベクトル未定水平ベクトルテーブル、流入ベクトル未定垂直ベクトルテーブル、流出ベクトル未定垂直ベクトルテーブルの４種のテーブルの状態を表している。それぞれのテーブルは、あらかじめＲＡＭ５上に十分な領域が確保されているものとする。また、それぞれの領域は、それぞれ連続したメモリ領域として構成されていて、先頭領域から発生順にそれぞれのテーブルに該当する未定のベクトル番号を格納するものとする。それぞれの領域において、有効データの次である最終尾の位置には、最終尾であることを示すマーカーとして「−１」を格納しておく。データを付け加えるには、このマーカーの位置に新たなベクトル番号を上書きし、その次の領域に改めてマーカーを書き込む。あるデータを削除する際には、削除するデータの次の有効データからマーカーまでを、削除するデータの位置から順に１つずつシフトするように書き写していくものとする。
【００６７】
さて、図１４（ａ）の１４０で示されるようなラベル画像にステップＳ１２００の処理を行うと、色領域１（ラベル番号が１の領域）に対しては、図１４（ｂ）で示されるベクトル情報テーブルが得られることになる。図１４（ａ）における、Ａ（０）、Ｂ（１）、Ｃ（２）、Ｄ（３）、Ｅ（４）、Ｆ（５）の６点が、それぞれ、図１４（ｂ）のベクトル番号（ベクトルカウンタ欄の値）０、１、２、３、４，５の６本のベクトルに対応する。図１４（ａ）のラベル画像１４０をラスター走査すると、Ａ（０）、Ｂ（１）、Ｃ（２）、Ｄ（３）、Ｅ（４）、Ｆ（５）で示される位置の順に輪郭点が抽出されていくことになるからである。
【００６８】
すなわち、ラベル画像の左上からラスター走査を開始すると、３×３の画素マトリクスのウィンドウが、図１４（ａ）の１４００で示される位置に来た時、図９（ｇ）に示したケース７の状態となる。このときの中心画素の左上の位置に交点判定を伴う輪郭点抽出処理が行われ、図１２（ｂ）で示した状態であることから、図１４（ａ）におけるＡ（０）の位置に、ベクトル番号０として、色交点ではない輪郭点（水平ベクトルの始点）が抽出される。このベクトルは、この時点では流入ベクトルも流出ベクトルも未定であるから、図１５（ａ）に示す様に、流入ベクトル未定水平ベクトルテーブルと流出ベクトル未定水平ベクトルテーブルに、ベクトル番号０が追記されることになる。
【００６９】
ラスター走査を進めると、次に、図１４（ａ）の１４０１で示される位置に来た時、図９（ｍ）に示したケース１３の状態となる。このときの中心画素の右上の位置に交点判定を伴う輪郭点抽出処理が行われ、図１２（ｎ）で示した状態であることから、図１４（ａ）におけるＢ（１）の位置に、ベクトル番号１として、色交点ではない輪郭点（垂直ベクトルの始点）が抽出される。このベクトルは、流出ベクトルは未定ながら、流入ベクトルは既走査領域にあるので、流出ベクトル未定水平ベクトルテーブルを探索することにより、ベクトル番号０が流入ベクトルであることが判明する。よって、上述したように、ベクトル情報テーブルのベクトル番号１の流入ベクトル欄とベクトル番号０流出ベクトル欄の記載を行う。図１５（ｂ）に示す様に、流出ベクトル未定水平ベクトルテーブルからベクトル番号０を削除するとともに、流出ベクトル未定垂直ベクトルテーブルに、ベクトル番号１を追記する。
【００７０】
次に、図１４（ａ）の１４０２で示される位置に来た時、図９（ｆ）に示したケース６の状態となる。このときの中心画素の右上の位置に交点判定結果に基く輪郭点抽出処理が行われ、図１３（ｐ）で示した状態であることから、図１４（ａ）におけるＣ（２）の位置に、ベクトル番号２として、色交点である輪郭点（垂直ベクトルの始点）が抽出される。このベクトルも、流出ベクトルは未定ながら、流入ベクトルは既走査領域にあるので、流出ベクトル未定垂直テーブルを探索することにより、ベクトル番号１が流入ベクトルであることが判明する。よって、上述したように、ベクトル情報テーブルのベクトル番号２の流入ベクトル欄とベクトル番号１流出ベクトル欄の記載を行う。図１５（ｃ）に示す様に、流出ベクトル未定垂直ベクトルテーブルからベクトル番号１を削除した上で、ベクトル番号２を追記する。
【００７１】
次に、図１４（ａ）の１４０３で示される位置に来た時、図９（ｄ）に示したケース４の状態となる。このときの中心画素の左下の位置に交点判定を伴う輪郭点抽出処理が行われ、図１２（ｈ）で示した状態であることから、図１４（ａ）におけるＤ（３）の位置に、ベクトル番号３として、色交点ではない輪郭点（垂直ベクトルの始点）が抽出される。このベクトルは、流入ベクトルは未定ながら、流出ベクトルは既走査領域にあるので、上述のように、流入ベクトル未定水平ベクトルテーブルと流入ベクトル未定垂直ベクトルテーブルの両方を探索することにより、ベクトル番号０が流出ベクトルであることが判明する。よって、上述したように、ベクトル情報テーブルのベクトル番号３の流出ベクトル欄とベクトル番号０流入ベクトル欄の記載を行う。図１５（ｄ）に示す様に、流入ベクトル未定水平ベクトルテーブルからベクトル番号０を削除するとともに、流入ベクトル未定垂直ベクトルテーブルに、ベクトル番号３を追記する。さらに、このケース４の状態では、中心画素の右下の位置に交点判定結果に基く輪郭点抽出処理が行われ、図１３（ｈ）で示した状態であることから、図１４（ａ）におけるＥ（４）の位置に、ベクトル番号４として、色交点である輪郭点（水平ベクトルの始点）が抽出される。このベクトルは、流入ベクトルは未定ながら、流出ベクトルは既走査領域にあるので、上述のように、流入ベクトル未定水平ベクトルテーブルと流入ベクトル未定垂直ベクトルテーブルの両方を探索することにより、ベクトル番号３が流出ベクトルであることが判明する。よって、上述したように、ベクトル情報テーブルのベクトル番号４の流出ベクトル欄とベクトル番号３流入ベクトル欄の記載を行う。図１５（ｅ）に示す様に、流入ベクトル未定垂直ベクトルテーブルからベクトル番号３を削除するとともに、流入ベクトル未定水平ベクトルテーブルに、ベクトル番号４を追記する。
【００７２】
次に、図１４（ａ）の１４０４で示される位置に来た時、図９（ｊ）に示したケース１０の状態となる。このときの中心画素の右下の位置に交点判定を伴う輪郭点抽出処理が行われ、不図示ながら、図１２（ｕ）の様に、中心画素以外の３画素のうち、縦または横につながる２画素が同ラベルで、残りの１画素が中心画素とも他の２画素とも異なるラベルなので、色交点である輪郭点である。よって、図１４（ａ）におけるＦ（５）の位置に、ベクトル番号５として、色交点である輪郭点（水平ベクトルの始点）が抽出される。このベクトルは、流入ベクトルも流入ベクトルも既走査領域にある。まず、流出ベクトル未定垂直ベクトルテーブルを探索することにより、ベクトル番号２が流入ベクトルであることが判明する。よって、上述したように、ベクトル情報テーブルのベクトル番号５の流入ベクトル欄とベクトル番号２流出ベクトル欄の記載を行う。図１５（ｆ）に示す様に、流出ベクトル未定垂直ベクトルテーブルからベクトル番号２を削除する。そして、流入ベクトル未定水平ベクトルテーブルと流入ベクトル未定垂直ベクトルテーブルの両方を探索することにより、ベクトル番号４が流出ベクトルであることが判明する。図１５（ｆ）に示す様に、流入ベクトル未定水平ベクトルテーブルからベクトル番号４を削除する。
【００７３】
かくして、図１４（ａ）の１４０で示されるようなラベル画像の色領域１（ラベル番号が１の領域）に対して、図１４（ｂ）で示されるベクトル情報テーブルが得られることになる。
【００７４】
さて、これまで述べてきた、ステップＳ１２００の輪郭点・色交点抽出処理は、ラベル画像のラベル毎に順次にベクトル情報を抽出することが可能である。この方式では、ラベル画像中の全てのラベル領域の処理には、ラベル数に相当する回数分だけラベル画像を繰り返しラスター走査し、上記の処理を繰り返すことになる。このとき、ラベル画像中で、各ラベル領域の存在する範囲をあらかじめ矩形領域として求めておき、ラベル毎に、それぞれの存在する矩形領域（ラベル画像の部分領域となる）のみにラスター走査の範囲を限定すれば、処理時間を短縮することができる。
【００７５】
一方で、ラベル画像を一回走査するだけで、ラベル画像中に出現する全てのラベルの輪郭ベクトル情報を抽出することも可能である。この場合は、ラベル画像中に出現する全てのラベル分だけ、各々のラベル領域用に別々にベクトル情報テーブルと流入ベクトルや流入ベクトルが未定のベクトルの情報を管理するテーブル類を用意する。その上で、ラスター走査時に逐次、中心画素が属するラベルのテーブル類を使い分けて処理を進めるようにする。上述の走査を繰り返す場合に比し、ラベル数分の十分なメモリ容量を要すものの、一回のラスター走査で、全てのラベルに対して、それぞれ別々の独立したベクトル情報テーブル中に、それぞれのラベル領域の輪郭ベクトルデータを抽出することができる。
【００７６】
次にステップＳ１３００では、ステップＳ１２００で抽出したベクトル情報テーブル上のベクトル情報から、色領域（ラベル領域）を色交点間で区切られた部分輪郭の集まりで表現された輪郭情報に再構成する。
【００７７】
ベクトル情報テーブルをベクトル番号の昇順に未使用フラグを参照しながら、未処理（未処理フラグがＴＲＵＥ）かつ、色交点（色交点フラグがＴＲＵＥ）であるベクトルを探し、該当するベクトルが見つかった場合には、このベクトルから処理を開始する。このベクトルを第１の区分輪郭線の始点とするともに第一の区分輪郭線の第１点目の輪郭点とし、当該ベクトルの未使用フラグをＦＡＬＳＥに変更する。次に、このベクトルの流出ベクトルを参照して、同区分輪郭線の次の輪郭点とする。もし、この輪郭点が色交点でなければ、当該ベクトルの未使用フラグをＦＡＬＳＥに変更し、このベクトルの流出ベクトルを参照して同様の処理を続ける。一方、同輪郭点が色交点（色交点フラグがＴＲＵＥ）であった場合は、この輪郭点をもって同区分輪郭線の終了点とする。もし、この色交点の未使用フラグが既にＦＡＬＳＥとなっていた場合には、抽出中の輪郭の開始座標に戻ったということであり、１つの閉ループの抽出が完了となる。もし、この輪郭点の未使用フラグが未だＴＲＵＥの場合には、この輪郭点を次の区分輪郭線の始点とし、この新しい区分曲線の第１点目の輪郭点とする。このベクトルの未使用フラグをＦＡＬＳＥに変更してから、前の区分輪郭線と同様に、流出ベクトルを参照して同区分輪郭線上の次の輪郭点を求める動作を続ける。１つの閉ループの抽出が完了した場合には、再度、未処理（未処理フラグがＴＲＵＥ）かつ、色交点（色交点フラグがＴＲＵＥ）であるベクトルを探して残りの閉ループを探す。もし、テーブル内に色交点フラグがＴＲＵＥであるベクトルが見つからなかった場合は、テーブル内で最初に見つかる未処理のベクトルから処理を開始する。流出ベクトルのベクトル番号をたどり、出現するｘｙ座標を順に記録していけば輪郭座標を再構成することができる。そうして輪郭情報の再構成を続け、抽出中の輪郭の開始座標に戻れば１つの閉ループの抽出が完了となる。未処理のベクトルが無くなるまで処理を続けると外輪郭・内輪郭合わせた輪郭座標を全て抽出することができる。抽出された輪郭情報は、ラベル単位で情報を持つこととする。
【００７８】
図１４（ａ）から求められる図１４（ｂ）のベクトル情報テーブルを基に、ステップＳ１３００の処理で輪郭情報を再構成すると、図１４（ｃ）のように、色領域（ラベル番号が１の領域）を色交点間で区切られた部分輪郭の集まりで表現した輪郭情報が得られる。図１４（ｄ）は、図１４（ｃ）の輪郭情報が、ラベル番号１の領域の輪郭を構成することを示すデータ形式の例を示している。
【００７９】
このようにして抽出される色交点で区間分割された境界線（分割境界線）データを、区間ごとに関数近似することにより、それぞれの色領域の隣接箇所での重なり・隙間のないベクトルデータを生成することができる。
【００８０】
以上、ステップＳ１３００の輪郭情報再構成処理を説明した。尚、このステップＳ１３００の処理は、図１における輪郭情報再構成手段を実現している。
【００８１】
上述したように、本発明では、ラベリングされたラベル画像をラスター走査し、各ラベル領域の輪郭を構成する線素を、ウィンドウを用いて抽出する。抽出した線素は線素の始点となる座標情報とともに流出先・流出元を関連付けたうえでテーブルに登録しておく。また線素の始点が色領域間の色交点にあたる場合、色交点情報である旨も合わせて記録する。画像全体を走査し終えた後に、テーブルを参照して線素をつなぎ合わせる。この時、色交点情報を持つ箇所でつなぎ合わせるデータを分けることで境界線を抽出することができる。したがって、テーブルには線素が再構成されるべき順番で漏れなく登録されるため、抽出できる境界線も特定領域の輪郭再構成に適した順番で、漏れなく抽出することができる。１回の画像全面に対するラスター走査とテーブル走査で境界線が抽出できるため、処理も高速である。また、線素の抽出と色交点判定はウィンドウをラスター走査順にずらしながら行うため、追跡による境界線抽出のように、領域形状によって追跡の方向が変わることがなく、メモリキャッシュが効きやすくなり処理速度の低下防止に効果がある。また、色領域の形状によらず、画像全体に対する１回のラスター走査とテーブル走査で境界線を抽出できる。
【００８２】
［実施例２］
ウィンドウのサイズは３×３でなくてもよく、２×２でも可能である。２×２のウィンドウ走査で起こりえる２×２内の４画素のパターンを図１６（ａ）、図１６（ｄ）、図１６（ｇ）、図１６（ｋ）、図１６（ｏ）に示した。図１６（ａ）と図１６（ｄ）は、４画素内に２種類のラベルの画素が存在する場合である。図１６（ｇ）、図１６（ｋ）は、４画素内に３種類のラベルの画素が存在する場合である。図１６（ｏ）は、４画素内に４種類のラベルの画素が存在する場合である。尚、４画素内に１種類のラベルの画素しか存在しない場合には、輪郭点は抽出されることがないので、表記していない。基本的には、これらのパターンの９０°、１８０°、２７０°の回転したパターンがあり得るが、図１６（ａ）、図１６（ｄ）、図１６（ｇ）、図１６（ｋ）、図１６（ｏ）の場合を示せば、それらの回転パターンの場合は、容易に構成可能であるため、これらに関する詳述は省略する。以下、図１６（ａ）、図１６（ｄ）、図１６（ｇ）、図１６（ｋ）、図１６（ｏ）の場合を説明する。
【００８３】
実施例１の３×３のウィンドウ走査での説明の中で、ラベル画像を一回走査するだけで、ラベル画像中に出現する全てのラベルの輪郭ベクトル情報を抽出する場合を述べた。その中で、ラベル画像中に出現する全てのラベル分だけ、各々のラベル領域用に別々にベクトル情報テーブルと流入ベクトルや流入ベクトルが未定のベクトルの情報を管理するテーブル類を用意することを説明した。２×２のウィンドウ走査においても、同様である。
【００８４】
さて、図１６（ａ）のパターンの場合には、図１６（ｂ）と図１６（ｃ）に示したように、２種類のラベルのそれぞれに、一点ずつ、色交点ではない輪郭点を抽出する。図１６（ｄ）のパターンの場合には、図１６（ｅ）と図１６（ｆ）で示したように、２種類のラベルのそれぞれに、２点ずつ、色交点である輪郭点を抽出する。図１６（ｇ）のパターンの場合には、図１６（ｈ）、図１６（ｉ）、図１６（ｊ）で示したように、３種類のラベルのそれぞれに対応させて、それぞれに色交点である輪郭点を１点ずつ抽出する。図１６（ｋ）のパターンの場合には、図１６（ｌ）、図１６（ｍ）、図１６（ｎ）で示したように、３種類のラベルのうち、４画素中に一画素しか存在しないラベルに対しては、色交点ではない輪郭点を１点ずつ抽出し（図１６（ｌ）と図１６（ｍ）に相当）、４画素中の斜め方向に隣接している２画素に同じラベルが存在しているラベル（図１６（ｎ）に相当）には、色交点ではない輪郭点を２点抽出する。また、図１６（ｏ） のパターンの場合には、図１６（ｐ）、図１６（ｑ）、図１６（ｒ） 、図１６（ｓ）で示したように、のそれぞれに対応させて、それぞれに色交点である輪郭点を１点ずつ抽出する。
【００８５】
このように、構成すれば、２×２のウィンドウ走査でも、３×３のウィンドウ走査で得られる輪郭情報と全く同等な輪郭情報を抽出することが可能である。
【００８６】
一回のラスター走査で、ラベル画像中の全てのラベル領域の輪郭情報を抽出するためには、３×３の場合には、実施例１で述べた様に、中心画素のラベルについてのみを抽出すればよい。これに対し、２×２の場合には、ウィンドウ内４画素内に出現するラベル全てについての上を抽出しながら行う必要がある点が大きく異なる。
【００８７】
また、２×２の２×２のウィンドウ走査の場合でも、一回の走査では、上記の輪郭点抽出のうち、ある一つのラベルに対応する輪郭点のみを該当する一つのラベルのテーブル領域のみに抽出する様に構成してすることも可能である。画像中に存在するラベルの数の回数、輪郭抽出するラベルを切り替えながら、同様なラスター走査を繰り返せば、２×２のウィンドウ走査によっても、ラベル毎の輪郭情報抽出が可能である。この場合には、ベクトル情報テーブルと流入ベクトルや流入ベクトルが未定のベクトルの情報を管理するテーブル類用のメモリ領域をあらかじめ全てのラベル分確保する必要はなくなる。
【００８８】
（その他の実施例）
以上本発明にかかる実施形態を説明したが、実施形態の処理の多くは、情報処理装置上で実行されるコンピュータプログラムによるものであるので、当然、本発明はかかるコンピュータプログラムをもその範疇とする。通常、コンピュータプログラムは５のＲＡＭや６のＲＯＭ、またはＣＤ−ＲＯＭ等のコンピュータ可読記憶媒体に格納されていて、それをコンピュータにセットし、システムにコピーもしくはインストールすることで実行可能になる。従って、かかるコンピュータ可読記憶媒体も当然に本発明の範疇に入る。
【００８９】
また、本発明は、以下の処理を実行することによっても実現される。その処理は、上述した実施例の機能を実現させるソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【特許請求の範囲】
【請求項１】
所定サイズの画素マトリクスで多値画像をラスター走査し、当該画素マトリクス内の複数画素の状態に応じて、異なる値を有する画素間の境界を形成する輪郭を区分する色交点であるか否かの判定と、当該異なる値をもつ画素間の境界を形成する輪郭点の抽出とを行う色交点判定・輪郭点抽出手段と、
前記色交点判定・輪郭点抽出手段で判定された色交点と抽出された輪郭点とを用いて、当該色交点ごとに区分した輪郭線で構成される輪郭情報を生成する輪郭情報再構成手段と
を有することを特徴とする画像処理装置。
【請求項２】
前記色交点判定・輪郭点抽出手段は、
前記画素マトリクス内の複数画素の状態に応じて、異なる値をもつ画素間の境界を形成する輪郭を区分すべき点である色交点であるか否かを判定する色交点判定手段と、
前記画素マトリクス内の複数画素の状態と、前記色交点判定手段の判定結果とに応じて、異なる値をもつ画素間の境界を形成する輪郭点を抽出する輪郭点抽出手段と
を有することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記色交点とは、３種以上の異なる値を持つ画素が会合する点、または、複数の色が会合する点で且つ斜め方向の隣接する画素が同じ値でかつ左右方向及び上下方向に隣接する画素が異なる色である点、のいずれかを満たす点である、請求項１または２に記載の多値画像の画像処理装置。
【請求項４】
前記画素マトリクスは、３画素×３画素サイズのマトリクスであることを特徴とする請求項１乃至３のいずれか１項に記載の画像処理装置。
【請求項５】
前記色交点判定・輪郭点抽出手段は、前記画素マトリクスに含まれる３画素×３画素における中心画素の値と同じ値を有する画素の領域の輪郭を構成する輪郭点を抽出することを特徴とする請求項４に記載の画像処理装置。
【請求項６】
前記画素マトリクスは、２画素×２画素サイズのマトリクスであることを特徴とする請求項１乃至３のいずれか１項に記載の画像処理装置。
【請求項７】
入力画像に対して、同色であると判定した画素ごとに同じ領域番号が付与することにより、前記多値画像を生成する領域番号付与手段を更に有することを特徴とする請求項１乃至６のいずれか１項に記載の画像処理装置。
【請求項８】
前記入力画像は、スキャン入力された画像に対してノイズ除去を行った後の画像であることを特徴とする請求項７に記載の画像処理装置。
【請求項９】
前記輪郭情報再構成手段で生成された前記色交点ごとに区分した輪郭線で構成される輪郭情報に対して、当該区分された輪郭線ごとに関数近似を行う関数近似手段を更に有することを特徴とする請求項１乃至８のいずれか１項に記載の画像処理装置。
【請求項１０】
抽出手段が、所定サイズの画素マトリクスで多値画像をラスター走査し、当該画素マトリクス内の複数画素の状態に応じて、異なる値を有する画素間の境界を形成する輪郭を区分する色交点であるか否かの判定と、当該異なる値をもつ画素間の境界を形成する輪郭点の抽出とを行う色交点判定・輪郭点抽出ステップと、
輪郭情報再構成手段が、前記色交点判定・輪郭点抽出ステップで判定された色交点と抽出された輪郭点とを用いて、当該色交点ごとに区分した輪郭線で構成される輪郭情報を生成する輪郭情報再構成ステップと
を有することを特徴とする画像処理方法。
【請求項１１】
コンピュータを、
所定サイズの画素マトリクスで多値画像をラスター走査し、当該画素マトリクス内の複数画素の状態に応じて、異なる値を有する画素間の境界を形成する輪郭を区分する色交点であるか否かの判定と、当該異なる値をもつ画素間の境界を形成する輪郭点の抽出とを行う色交点判定・輪郭点抽出手段、
前記色交点判定・輪郭点抽出手段で判定された色交点と抽出された輪郭点とを用いて、当該色交点ごとに区分した輪郭線で構成される輪郭情報を生成する輪郭情報再構成手段、
として機能させるためのコンピュータプログラム。
【請求項１２】
請求項１１に記載のコンピュータプログラムを格納した、コンピュータ読み取り可能な記憶媒体。
【請求項１】
所定サイズの画素マトリクスで多値画像をラスター走査し、当該画素マトリクス内の複数画素の状態に応じて、異なる値を有する画素間の境界を形成する輪郭を区分する色交点であるか否かの判定と、当該異なる値をもつ画素間の境界を形成する輪郭点の抽出とを行う色交点判定・輪郭点抽出手段と、
前記色交点判定・輪郭点抽出手段で判定された色交点と抽出された輪郭点とを用いて、当該色交点ごとに区分した輪郭線で構成される輪郭情報を生成する輪郭情報再構成手段と
を有することを特徴とする画像処理装置。
【請求項２】
前記色交点判定・輪郭点抽出手段は、
前記画素マトリクス内の複数画素の状態に応じて、異なる値をもつ画素間の境界を形成する輪郭を区分すべき点である色交点であるか否かを判定する色交点判定手段と、
前記画素マトリクス内の複数画素の状態と、前記色交点判定手段の判定結果とに応じて、異なる値をもつ画素間の境界を形成する輪郭点を抽出する輪郭点抽出手段と
を有することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記色交点とは、３種以上の異なる値を持つ画素が会合する点、または、複数の色が会合する点で且つ斜め方向の隣接する画素が同じ値でかつ左右方向及び上下方向に隣接する画素が異なる色である点、のいずれかを満たす点である、請求項１または２に記載の多値画像の画像処理装置。
【請求項４】
前記画素マトリクスは、３画素×３画素サイズのマトリクスであることを特徴とする請求項１乃至３のいずれか１項に記載の画像処理装置。
【請求項５】
前記色交点判定・輪郭点抽出手段は、前記画素マトリクスに含まれる３画素×３画素における中心画素の値と同じ値を有する画素の領域の輪郭を構成する輪郭点を抽出することを特徴とする請求項４に記載の画像処理装置。
【請求項６】
前記画素マトリクスは、２画素×２画素サイズのマトリクスであることを特徴とする請求項１乃至３のいずれか１項に記載の画像処理装置。
【請求項７】
入力画像に対して、同色であると判定した画素ごとに同じ領域番号が付与することにより、前記多値画像を生成する領域番号付与手段を更に有することを特徴とする請求項１乃至６のいずれか１項に記載の画像処理装置。
【請求項８】
前記入力画像は、スキャン入力された画像に対してノイズ除去を行った後の画像であることを特徴とする請求項７に記載の画像処理装置。
【請求項９】
前記輪郭情報再構成手段で生成された前記色交点ごとに区分した輪郭線で構成される輪郭情報に対して、当該区分された輪郭線ごとに関数近似を行う関数近似手段を更に有することを特徴とする請求項１乃至８のいずれか１項に記載の画像処理装置。
【請求項１０】
抽出手段が、所定サイズの画素マトリクスで多値画像をラスター走査し、当該画素マトリクス内の複数画素の状態に応じて、異なる値を有する画素間の境界を形成する輪郭を区分する色交点であるか否かの判定と、当該異なる値をもつ画素間の境界を形成する輪郭点の抽出とを行う色交点判定・輪郭点抽出ステップと、
輪郭情報再構成手段が、前記色交点判定・輪郭点抽出ステップで判定された色交点と抽出された輪郭点とを用いて、当該色交点ごとに区分した輪郭線で構成される輪郭情報を生成する輪郭情報再構成ステップと
を有することを特徴とする画像処理方法。
【請求項１１】
コンピュータを、
所定サイズの画素マトリクスで多値画像をラスター走査し、当該画素マトリクス内の複数画素の状態に応じて、異なる値を有する画素間の境界を形成する輪郭を区分する色交点であるか否かの判定と、当該異なる値をもつ画素間の境界を形成する輪郭点の抽出とを行う色交点判定・輪郭点抽出手段、
前記色交点判定・輪郭点抽出手段で判定された色交点と抽出された輪郭点とを用いて、当該色交点ごとに区分した輪郭線で構成される輪郭情報を生成する輪郭情報再構成手段、
として機能させるためのコンピュータプログラム。
【請求項１２】
請求項１１に記載のコンピュータプログラムを格納した、コンピュータ読み取り可能な記憶媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【公開番号】特開２０１３−１１４６５５（Ｐ２０１３−１１４６５５Ａ）
【公開日】平成２５年６月１０日（２０１３．６．１０）
【国際特許分類】
【出願番号】特願２０１１−２６３４２２（Ｐ２０１１−２６３４２２）
【出願日】平成２３年１２月１日（２０１１．１２．１）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２５年６月１０日（２０１３．６．１０）
【国際特許分類】
【出願日】平成２３年１２月１日（２０１１．１２．１）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]