WO2006006666A1

WO2006006666A1 - ディジタル画像の輪郭追跡による画像処理方法並びに画像処理装置

Info

Publication number: WO2006006666A1
Application number: PCT/JP2005/013026
Authority: WO
Inventors: Kazuo Toraichi; Tetsuo Sugiyama; Paul Wing Hing Kwan
Original assignee: Japan Science And Technology Agency
Priority date: 2004-07-14
Filing date: 2005-07-14
Publication date: 2006-01-19
Also published as: JP2006031245A

Abstract

　複数の色あるいは輝度を含む図形や画像でも精度の高い図形や画像を少ないデータ容量で、かつ、高速に処理できるディジタル画像の輪郭追跡手法を提案する。　画像処理装置によりディジタル画像の輪郭を追跡し画像領域を把握して輪郭情報を生成する画像処理方法であって、入力されたディジタル画像について、出発点の進行方向両端の画素の色と同じ画素の境界辺を追跡する輪郭追跡を行って輪郭線分を抽出する輪郭線分処理を行い、抽出された前記輪郭線分に関して分岐処理及び合成処理を行い、該輪郭線分の結合で決まる輪郭を形成して前記ディジタル画像の輪郭情報を生成する。

Description

明細書

ディジタル画像の輪郭追跡による画像処理方法並びに画像処理装置技術分野

[0001] 本発明は、画像処理方法並びに画像処理装置に係り、特に、計算機で処理されるディジタル画像処理に不可欠な図形や画像 (以下、特に区別する必要のな!、ときは単に画像)の領域の輪郭を高精度に把握し、画像の拡大、縮小に対しても隣接図形や画像との関係を適切に保つ、ディジタル画像の輪郭追跡による画像処理方法並びに画像処理装置に関する。

背景技術

[0002] 一般に、計算機 (マイクロコンピュータやディジタルデータ処理機器を含む)の上で、図形や画像はディジタルデータとして扱われる。このような計算機上で扱われるディジタル画像を処理する場合、図形や色領域の認識などに対して、図形や画像領域の輪郭を把握することが行われる。しかし、隣接する図形や画像領域の輪郭を把握する際、輪郭の把握の方法によっては、重複して輪郭線を把握し、図形や画像領域の拡大、縮小において適切な関係を保つことができない場合がある。

[0003] また、画像データは大きく分けてラスタ形式と関数形式に分けられる。ラスタ形式の画像は、格子状に規則正しく並んだ画素と呼ばれる色のついた点の集合として表される。これは、現代の CRTディスプレイや LCDなどに表示するのに適した形式である。しかし、拡大'縮小 '回転'平行移動などのァフィン変換操作を行うと画質が劣化してしまう問題がある。これに対し、関数形式は画像の中の図形や画像領域の特徴を関数によって表すため、単純な図形や画像領域を表現するのに適しており、ァフィン変換によって画質が劣化しな、と言う性質を持って、る。

[0004] ところが、関数形式で表した方が都合がよ!、図形や画像でも、スキャナやディジタルカメラなどの装置を通じて計算機に取り込んだ場合ラスタ形式になってしまうことが多い。従来、このようなラスタ形式の図形や画像は手動で適切な関数を割り当てて関数形式に変換する作業を行うが、熟練が必要であり多くの手間もかかる。そのため、これらのラスタ形式の図形や画像を自動的に関数形式に変換する必要が生じる。ラスタ形式の図形や画像を自動的に関数形式の図形や画像に変換する手法は従来でも提案されているが、後で述べるようにカラー図形や画像を扱う際に色の境界を適切に扱えない場合がある。

[0005] 一方、特許文献 1には、画像の領域の境界線を求める領域境界線抽出機構により、領域境界線を表現するための座標を設定するものにおいて、画素の 4隅を座標点とすることが開示されて、る。

[0006] なお、隣接する輪郭を把握する際、輪郭の把握の方法によっては、重複して輪郭線を把握し前記した画像データから抽出された輪郭線データから関数形式の図形や画像に変換する手法については、例えば特許文献 2に開示されている。

[0007] また、特許文献 3には、分割画像の縦横の境界において 1画素つまり 1ドットずつ重なるように領域分割することにより、境界線を共有するようにした技術が開示されている。

[0008] なお、ディジタル画像処理の分野ではな!/、が、境界線の共有に関する参考技術として、特許文献 4には、隣接する 2つの閉領域を一体化して 1つの閉領域とするものがある。すなわち、特許文献 4には、製品の金型などの曲面分割方法において、各境界線で囲まれた閉領域に関して、各領域の位相関係に基いて、隣接する 2つの閉領域を一体ィ匕して 1つの閉領域とする展開処理を自動的に行うようにした技術が開示されている。

[0009] 特許文献 1 :特開平 10— 145590号公報

特許文献 2 :特開 2001— 52187号公報

特許文献 3：特開平 6 - 348837号公報

特許文献 4:特開平 7— 44733号公報

発明の開示

発明が解決しょうとする課題

[0010] 図 10に、従来技術の関数形式により図形の輪郭を把握する一例を示す。

従来の一般的な手法では、 2値画像に対する輪郭追跡手法を多色画像に適用するため、図 10のように図形や画像中のある色や輝度が連続して現れる領域 (以降、色領域と記す)だけに注目し、その領域の中を図、外を地とみなし、 2値画像として輪郭追跡を行っていた。

しかし、この従来手法では、 2つの色領域が接する場所で輪郭線が 2重に取られてしまうことに起因する 2つの問題がある。 1つは、図 11のように、輪郭線の関数近似を行うと双方の領域の輪郭線の近似誤差によって領域が重なったり隙間が開いたりしてしまう場合がある事である。 2つめは、同じ輪郭線が 2回処理されることで、処理時間と格納効率が低下する事である。

[0011] 一方、前記特許文献 1に記載の方式は、カラー Z濃淡画像において、濃淡差を利用して領域抽出を行い、その領域の境界を関数近似により圧縮、復号ィ匕を行っている。濃淡差は、所定の差分以内の画素を同一領域内とし、差分が所定の値よりも大きいところを領域の境界としている。従って、特許文献 1記載の発明では、同一の領域と判断する濃淡差を入力し、画像を画素単位に水平方向（ラスタースキャン）に走査し、その濃淡差が所定値よりも大きいところを境界点として記憶しておき、全画像について境界点を抽出する。その後、境界点を繋ぐことで領域を決定する。

[0012] この特許文献 1記載の発明のように、画像を水平方向に走査し、その濃淡差が所定の値よりも大きいところを境界点とする方法では、境界線が水平方向の走査線と並行の場合にはこれを検出できない可能性がある。つまり、水平方向の画素の濃淡差のみを判定するため水平方向の濃淡差が無いと、境界線を検出できない。また、境界点を見出してもその境界点の繋がり方向が判らないため、別途、境界線の追跡が必要となる。

[0013] さらに、特許文献 1の発明では、 2つ以上の領域が接合する場合、その接合点を分割点と定義しているが、この分割点の抽出は、境界点を 2 * 2画素 (4画素で構成される）の窓関数で走査し、窓内の 4画素の色 (濃淡）が 3色以上となったところを分割点としている。この方式では、分割点の抽出に窓関数を用いて走査する必要があるため、処理に時間を要する。

[0014] 一方、 2つの領域が接する場所で輪郭線が 2重に取られないようにするために、特許文献 3に記載の方法は、境界で 1画素つまり 1ドットずつ重なるように領域分割する。しかし、この方法では、 1つの画素全体が境界の輪郭線を構成することになり、カラ一画像に適用した場合、 2つの色領域の輪郭線はいずれか 1つの色の画素で構成される。そのため、この画像を拡大処理したとき、拡大された画素による太い輪郭線が現れることなる。カラー画像にこのような太い輪郭線が現れるのは好ましくない。

[0015] また、特許文献 4に記載の方法では、隣接する 2つの閉領域を一体化して 1つの新たな閉領域を生成するために展開処理を行っており、仮にこの技術をディジタル画像の処理に適用した場合、元の画像の輪郭は維持されないことになる。

[0016] 本発明は、従来技術の問題点を改善し、特に複数の色あるいは輝度を含む図形や画像でも精度の高い図形や画像を少ないデータ容量で、かつ、高速に処理できるデイジタル画像の輪郭追跡手法を提案することを目的とする。

[0017] 本発明の他の目的は、元の画像の輪郭をきめ細力べ正確に維持し、再現し得るディジタル画像の輪郭追跡手法を提案することにある。

課題を解決するための手段

[0018] 上記従来技術の問題点を解決するため、本発明は、以下のような特徴を有する。

[0019] 本発明の 1つの特徴は、画像処理装置によりディジタル画像の輪郭を追跡し画像領域を把握して輪郭情報を生成するものにぉヽて、入力されたディジタル画像について、出発点の進行方向両端の画素の色と同じ関係の画素（あるいは色差が所定の値以上の画素)の境界辺を追跡する輪郭追跡を行って輪郭線分を抽出する輪郭線分処理を行！ヽ、抽出された前記輪郭線分に関して分岐処理及び合成処理を行ヽ、該輪郭線分の結合で決まる輪郭を形成して前記ディジタル画像の輪郭情報を生成することにある。

[0020] 本発明の他の特徴は、対象とする前記画像を含む領域の任意の点から、水平方向あるいは垂直方向に走査し、前記画像の左右あるいは上下の色が異なる画素点あるいは色差 (階調差)が所定の値以上ある画素点を見出し、その点を出発点として輪郭線分の追跡を行い、 3色以上の画素の会合点を探索し、該会合点を前記輪郭線分の端点の初期値とすることにある。

[0021] 本発明の他の特徴は、輪郭線を 3色以上あるいは 3種以上の輝度が会合する点で輪郭の追跡を一度打ち切り、 2色あるいは 2輝度の境界ごとに輪郭線を取ることで、隣接する 2つの領域が輪郭線データを共有できるようにすることにある。

発明の効果 [0022] 本発明によれば、色差 (濃淡差)を領域認識の基準として、与えられたディジタル画像について先ず画素間を追跡して輪郭線を取り、隣接する 2つの領域が輪郭線データを共有できるようにし、この輪郭線データに基づいて輪郭情報を生成する。輪郭線データが共有されることにより、異なる関数で近似されることも無くなり、拡大、縮小、移動などにおいて図形が離れるなどの従来手法の課題を解決し、データの処理効率 •格納効率の低下を防止出来る。

[0023] また、画素の境界辺を追跡して輪郭線を抽出するので、元の画像の輪郭を正確に維持し、再現し得る。したがって、画像の拡大等の処理を行っても、輪郭線は画素の境界辺に沿ったものとなり、きめの細かい画像が維持される利点がある。

発明を実施するための最良の形態

[0024] 以下、本発明の実施例を説明する。まず、本発明の基本的な構成を図 1及び図 2 で説明する。

本発明では、入力されたカラー画像データを 2次元のビットマップに配列する。一方、領域認識の基準となる色差 (濃淡差)を設定する。そして、このビットマップ配列されたディジタル画像データに関して、その色差 (濃淡差)が隣り合う画素間で同じ所を境界として追跡し、追跡の結果、閉領域が出来れば、その領域を一つの領域として認識する。輪郭線を 3色以上あるいは 3種以上の輝度が会合する点で輪郭の追跡を一度打ち切り、 2色あるいは 2輝度の境界ごとに輪郭線を取る。このような処理を繰り返すことで、図 1のように、隣接する 2つの領域が輪郭線データを共有できるようにする。また、図 2のように、 2領域の輪郭辺を共有するために、画像の輪郭線データは各画素の角を輪郭の座標値 (Χ= 1, Υ=0)、 (Χ= 1, Υ= 1)、 (Χ= 2, Υ= 1)、——、 (X=m, Υ=η)として用いる。

[0025] 本発明の理解を深めるために、より具体的な実施例を用いて説明する。

図 3は、本発明の対象となる図形処理や画像処理を行う画像処理装置の一構成例である。処理装置は、例えば CPUやメモリ、入出力手段などを有するコンピュータで構成され、メモリ上にプログラムをロードして実行させることにより、図形や画像処理に対する処理を行う機能を備えている。図 3にこの処理装置の機能をブロック的に表示する。 [0026] 図 3において、 100は画像データの入力部であり、画像データ (カラー図形、カラー写真や絵、カラー文書等)をイメージスキャナ一により読み取りディジタル情報として処理装置へ読み込む機能や、既にディジタル情報として記録媒体や他の処理装置等に保持されてヽる情報を直接ある、は通信ネットワークを介して処理装置へ読み込む機能を有して、る。 150は処理装置へ読み込まれたディジタル画像データを示す。

[0027] 200は輪郭追跡処理部であり、画素の辺の追跡処理、すなわち読み込まれたデータ 150の図形や画像の色領域の輪郭追跡を行う。 250はその処理結果である輪郭情報を示す。この輪郭情報 250は、例えば、画像の輪郭に関し、 X座標、 Y座標ごと〖こ輪郭に沿った座標値を表すデータ (X座標 = 1, 1, 2, 一， m、 Y座標 =0、 1, 1、一， n)を含んでいる。

[0028] 300は輪郭情報 250に基づき、輪郭すなわち色領域の境界を関数近似により関数化する関数近似処理部、 350はその処理結果として得られる図形や画像領域の輪郭を表す関数形式およびパラメータである。また、 400は、上記関数形式およびパラメータ 350により図形や画像を生成する画像処理部であり、その処理結果として処理図形や処理画像 450を生成する。 500は、表示装置やプリンタなどの出力部である。出力部 500には、処理図形や処理画像を記録媒体に記録しあるいはネットワークを介して他の処理装置へ送信する手段も含まれる。処理図形や処理画像 450の段階で記録媒体に記録して、利用することも考えられる。

[0029] なお、関数近似処理部 300や画像処理部 400の処理、すなわち画像データから抽出された輪郭線データを関数形式の図形や画像に変換処理につ！ヽては、例えば前記特許文献 2に開示された手法を用いることができる。よって、以下では、これらの処理についての詳細説明は省略する。

[0030] 図 4Aは、図 3の輪郭追跡処理部 200の具体的構成例を示す。 210は画像データの入力部であり、内部に図形データ、画像データを格納するメモリを含む。入力部 21 0は、読み込んだデータを 2次元のビットマップに配列する機能を持っており、画像データは 2次元のビットマップに配列される。 220は輪郭線追跡部であり、前記データ入力部のメモリの内容を読み出して、画素単位での輪郭線分の追跡を実施する。すなわち、ビットマップ配列された画像データに関して、その色差 (濃淡差)が隣り合う画素間で所定値以上の所を境界として追跡する。 230は輪郭線分結合分岐処理部であり、輪郭線分に分岐点があるときの処理および輪郭線分の結合処理を行う。 240 は領域輪郭形成部であり、輪郭線分の結合で決まる図形や画像を囲む領域の輪郭を形成し、輪郭情報 250を生成し、出力する。なお、輪郭追跡処理部 200の機能は、上記 210〜240で示した区分に限定されるものではなぐ全体として 1つあるいは複数のプログラムにより、実現される。例えば輪郭線追跡部 220と輪郭線分結合分岐処理部 230は、連続した一連の輪郭線追跡処理を行う単一のプログラムで構成してもよい。これらのプログラムは、記録媒体に保持されているものをコンピュータで読み取り、あるいは、コンピュータの記憶装置に保持されているものをメモリに読み出して実行される。

[0031] 図 4Bは、図 4Aの構成をより具体的に示した機能ブロック図であり、データ入力部 2 10は、 AD変換器 211、画像データ入力部 212、画像データ 2次元配列部 213、画像データメモリ格納機能 214を有している。 216は画像メモリである。 218は、画像の領域認識の基準となる画素の色の差あるいは輝度の差を与える濃淡差設定部である。例えば R, G, B各 8ビット 256階調、合計約 16万色余の色表現の範囲内で識別すべき色差 (濃淡差)を領域認識の基準として適宜設定する。具体的には、自然画像の R, G, B各色信号に対して、境界と認識される輝度階調差、例えば 50階調差あるいは 100階調差を与える。これにより、例えば、隣り合う画素の階調レベル差が設定された階調差以上のとき、その画素間が境界であると判断できる。輝度信号 (Y信号）に対しても同様である。

[0032] なお、本発明では、輪郭線を挟む画素の色関係、色差、階調差、輝度差を含めて、単に色差として説明する。なお、本発明で扱う画像としては、 2値画像、多色画像、自然画像があり、多色画像においてはダラディエーシヨン画像も含む。このような画像に対しての色差は色階調の差として現れることは言うまでもない。また、画像信号として、 RGB信号のほか、輝度信号（Y信号)と色差信号 (Cr, Cb信号)の組合せなどがあるが、本発明においては、これら全ての信号のレベルの差を色差として扱っている [0033] 輪郭線追跡部 220は、画像データ読出し部 221と、輪郭線分抽出部 222とを有している。なお、これらの各機能部は、 1つあるいは複数のプログラムにより、実現される

[0034] 輪郭線分処理では、画素の色が 3色、換言すると濃淡差設定部で設定された色差

(濃淡差)が 3つ以上で会合する点を輪郭線分の端点とする。また、輪郭追跡処理の出発点の進行方向両端の画素の色または色差と同じ関係の画素、あるいは所定の値以上の関係の画素の境界辺を追跡する。この輪郭線分の端点の初期値は、対象とする画像を含む領域の任意の点から、水平方向あるいは垂直方向に走査し、画像の左右あるいは上下の色が異なる画素点を見出し、その点を出発点として、輪郭線分の追跡を行う。そして、 3色以上の画素の会合点を探索し、該会合点を線分の端点の初期値とする。

[0035] 輪郭線追跡部 220はさらに、輪郭線分の端点で、分岐方向を未追跡方向と追跡済み方向として個々に登録するメモリ領域を有する。そして、このメモリ領域の未追跡方向を参照してその一つを輪郭追跡の開始端点として輪郭追跡を実施し、追跡完了時に追跡済み方向として前記メモリ領域に登録する。あるいは、新規な分岐点を見出したとき未追跡方向として前記メモリ領域に登録する。

[0036] 図 5は、多色画像の場合を示し、図 4Bの輪郭線分抽出部 222における輪郭追跡のアルゴリズム及び画素パターンを示す。輪郭追跡の原則は、出発点の画素における左右の画素の色あるいは輝度を記憶しておき（S501)、左右の画素の色あるいは輝度が同じであれば（画素パターン 514)、その画素の境界を追跡する（S507、 S508) 。進行方向の左右の色あるいは輝度が前記記憶して、る出発点の色あるいは輝度と異なる場合、すなわち 3色以上あるいは 3種以上の輝度が会合する点の場合、ー且輪郭追跡を終了する（S502)。進行方向の左右の色あるいは輝度が出発点の左の画素の色あるヽは輝度と同じであれば (画素パターン 512)右方向に進行方向を転換し（S505、 S506)、進行方向の左右の色あるいは輝度が出発点の右画素の色あるいは輝度と同じであれば (画素パターン 510)左に進行方向を転換して（S503、 S 504)、常に進行方向の左右の画素の色あるいは輝度が出発点の記憶されている色あるいは輝度と同じとなるように輪郭追跡を行う。このようにして追跡した輪郭線の出発点と終了点および線分番号あるいは線分名称を線分リストとしてメモリに登録しておく。

[0037] このようにして登録された線分は、追跡した画素の座標を用いて多項式関数で近似される（図 3、 300)。

[0038] 図 6は、図 5の輪郭追跡のアルゴリズム、すなわちある点に繋がる全ての輪郭線を追跡し、 3色以上あるいは 3種以上の模様が会合する点を分岐点として、新たにその点から輪郭追跡を行い、領域の輪郭線分を形成する方法の具体例を示す。この例は、橙領域（中央部）を左上側の緑領域と右側及び下側の青領域とで囲んだ 3色の矩形領域を多数持つ画像データを対象としている。なお、色差 (濃淡差)が 3つ以上ある画像データを含むものであれば、同様に処理される。この例では、図 6 (a)の黒丸点（1, 1)を出発点とし、最初の進行方向を上方向とする。そして、出発点の進行方向両端の画素の色と同じ関係の画素の境界辺、即ち、右側が橙、左側が緑の関係にある画素の境界辺を追跡し、図 6の（d)に至る。以下、ステップごとに詳細に説明する。

[0039] (1) 図 6の（a)に示すように、座標（1, 1)の点から上向きに追跡を開始したとする。 {初期位置 = (1, 1)、初期方向 =上}

(2) (1, 1)を現在位置とし、上を進行方向とする。

また、左右前方の色をそれぞれ「左色」「右色」としてメモリに記憶する。

[0040] {初期位置 = (1, 1)、初期方向 =上、右色 =橙、左色 =緑、

現在位置 = (1, 1)、進行方向 =上}

(3) 現在位置を輪郭線に追加し、進行方向が上なので画像に多重追跡防止印を付ける。（これらの情報をメモリに記憶する。メモリには、未追跡方向、追跡済み方向の記号を羅列する。 )

(4) 図 6の（b)に示すように、現在位置を進行方向に 1画素進める。

{初期位置 = (1, 1)、初期方向 =上、右色 =橙、左色 =緑、

現在位置 = (1, 2)、進行方向 =上}

(5) 現在位置から進行方向を見て左右前方の色をそれぞれ、「左次色」「右次色」とする。 [0041] {初期位置 = (1, 1)、初期方向 =上、右色 =橙、左色 =緑、

現在位置 = (1, 2)、進行方向 =上、右次色 =緑、左次色 =緑}

(6) 図 5のパターン 512を参照して、図 6の（c)に示すように、次の進行方向を右にする。

[0042] {初期位置 = (1, 1)、初期方向 =上、右色 =橙、左色 =緑、

現在位置 = (1, 2)、進行方向 =右、右次色 =緑、左次色 =緑}

(7) 現在の進行方向は初期方向に一致しないので、（3)に戻る。

[0043] (3- 2) 現在位置を輪郭線に追加する。（この情報をメモリに記憶する。）

(4- 2) 図 6の（d)に示すように、現在位置を進行方向に 1画素進める。

[0044] {初期位置 = (1, 1)、初期方向 =上、右色 =橙、左色 =緑、

現在位置 = (2, 2)、進行方向 =右、右次色 =緑、左次色 =緑}

(5- 2) 現在位置から進行方向を見て左右前方の色をそれぞれ、「左次色」「右次色」とする。

[0045] {初期位置 = (1, 1)、初期方向 =上、右色 =橙、左色 =緑、

現在位置 = (2, 2)、進行方向 =右、右次色 =青、左次色 =青}

(6- 2) 図 5のパターンを参照すると、右次色も左次色も右色でも左色でもないので追跡を停止し、（9)へ飛ぶ。

[0046] (9) 輪郭の分岐を検出したので分岐の方向（左、上、下）と分岐の数（3)を返して終了する。特に、今追跡した経路への分岐を先頭にして、時計回りに全ての分岐を列挙する。

[0047] 本発明によれば、濃淡差を持つ画素間を先ず追跡し、境界とその繋がりを認識している。境界が水平方向あるいは垂直方向であっても関係なく正確にこの境界が見出すことが可能である。また、方向を判断しながら追跡しているため、確実に境界を見出すことが可能となる。

[0048] また、本発明では、輪郭線の追跡過程で常に周囲の 4画素の濃淡差を判断しながら追跡を進行させている。従って、窓関数が必要なぐ窓関数による走査も必要がない。そのため、分割点の抽出と境界の抽出が同時に行われ、処理速度の向上が図られる。 [0049] また、本発明では、画素の境界辺を追跡して輪郭線を抽出するので、元の画像の輪郭を正確に維持し、再現し得る。したがって、画像の拡大等の処理を行っても、輪郭線は画素の境界辺に沿ったものとなり、きめの細かい画像が維持される利点がある

[0050] 次に、図 7は、輪郭線分結合分岐処理部 230の処理、すなわち、画素の境界を追跡して得られた輪郭線分に、分岐点があるときの処理および輪郭線分の結合処理を行う方法の具体例を示す図である。

[0051] まず、領域の外周の適当な 1点力輪郭を追跡する（S701)。

領域が一周して閉じているか判断し（S702)、閉じていれば終了する（S703)。閉じていない場合、終端と見つ力つた分岐を分岐リストに追加する（S704)。分岐リストが空になるまで以下を繰り返す (S705)。

分岐リストの 1つの要素を取り出して追跡する（S706)。終端が既に分岐リストにあれば (S707)、分岐リストから削除する（S708)。終端が分岐リストになければ (S709

)、新たに発見された分岐を分岐リストに追加する（S710)。

[0052] 図 7の処理手順をより具体的に説明するために、以下、図 8Aの例により図形の輪郭追跡について述べる。なお、図 8Aは、後で述べる図 9の領域輪郭形成処理の手順を示す図 8Bと共に、図形の輪郭追跡処理から領域輪郭形成処理間での処理を、連続した一連の処理として説明する。また、この例は、青と赤の 2色の領域及び白色の背景を持つ 3色の画像データを対象として、る。

[0053] (1)画像を走査し、画素の色が左右で異なる点を見つける。（図 8Aの（a)参照）

(2)見つけた点から輪郭の追跡を行う。

[0054] (3)分岐数が 0でないので次に進む。

[0055] 分岐数が 0となるのは他の領域の輪郭と接して、な、独立した領域の輪郭線を追跡した場合である。

[0056] (4)末端の分岐（図 8Aの (b)参照）をメモリ中の「未追跡分岐リスト」に、登録する（図 7のステップ 704に相当）。

[0057] {未追跡分岐リスト = {A, B, C} }

(5)未追跡分岐リストから分岐 Aを取り出して輪郭追跡をする（図 7のステップ 706に相当)。

[0058] {未追跡分岐リスト ={B, C}}

(6)追跡の開始点 Aと終了点 Dをメモリ中の「追跡済み分岐集合」に登録する。

[0059] {未追跡分岐リスト ={B, C}、追跡済み分岐集合 ={A, D}}

(7)追跡の終了点 Dは未追跡分岐リストにないので、発見された新しい分岐 E, Fを、未追跡分岐リストに追加する（図 8Aの（c)参照）、（図 7のステップ 709に相当）。

[0060] {未追跡分岐リスト ={B, C, E, F}、追跡済み分岐集合 ={A, D}}

(8)未追跡分岐リストは空ではないので、（5)に戻る。

[0061] (5)未追跡分岐リストから Bを取り出して輪郭追跡をする。（図 8Aの (d)参照）

{未追跡分岐リスト ={C, E, F}、追跡済み分岐集合 ={A, D}}

(6)追跡の開始点 Bと終了点 Eを追跡済み分岐集合に登録する。

[0062] {未追跡分岐リスト ={C, E, F}、追跡済み分岐集合 ={A, D, B, E}}

(7)追跡の終了点 Eは未追跡分岐リストに有るのでリストから削除する。

[0063] {未追跡分岐リスト ={C, F}、追跡済み分岐集合 ={A, D, B, E}}

(8)未追跡分岐リストは空ではな、ので（5)に戻る。

[0064] (5)未追跡分岐リストから Cを取り出して輪郭追跡をする。（図 8Aの (e)参照）

{未追跡分岐リスト ={F}、追跡済み分岐集合 ={A, D, B, E}}

(6)追跡の開始点 Cと終了点 Fを追跡済み分岐集合に登録する。（図 8Aの (f)参照

)

{未追跡分岐リスト ={F}、追跡済み分岐集合 ={A, D, B, E, C, F}}

(7)追跡の終了点 Fは未追跡分岐リストに有るのでリストから削除する。

[0065] {未追跡分岐リスト ={}、追跡済み分岐集合 ={A, D, B, E, C, F}}

(8)未追跡分岐リストが空なので次に進む。

[0066] 次に、図 9及び図 8Bにより、領域輪郭形成部 240の処理、すなわち上記輪郭線分結合分岐処理の結果を受けて、領域の輪郭を形成し輪郭情報 250を生成する処理の手順を説明する。

[0067] まず、図 9において、領域輪郭形成処理の手順を説明する。

最初に、全輪郭線分への順方向と逆方向のポインタのリストを作る（S901)。次に、以下の処理を、線分リストが空になるので反復する（S902)。

線分リストの 1つの要素を取り出して注目する（S903)。注目線分が最初に注目した線分に戻るまで、以下の（a)、（b)を反復する（S904)。

(a)注目して、る線分を線分リストから削除する（S905)。

[0068] (b)注目線分の終端の分岐で時計回りに最も近!、線分に注目する（S906)。

注目した順に線分を繋、で閉じた輪郭を作る (S907)。

[0069] 次に、上記図 9の処理手順を、図 8Bを用いてより具体的に説明する。

[0070] (9)新規の「領域 X」を定義する。（図 8Bの (a)参照）

{領域 X= { }、追跡済み分岐集合 = { A, B, C, D, E, F} }

(10)追跡済み分岐集合の中から Aを取り出し、注目する。

[0071] {領域 X= { }、追跡済み分岐集合 = {B, C, D, E, F}、注目 =A}

(11)注目してヽる分岐 Aから伸びる輪郭線分 ADを領域 Xに追加する。

[0072] {領域 X= {AD}、追跡済み分岐集合 = {B, C, D, E, F}、注目 =A}

(12)注目している分岐 Aから追跡した輪郭の終端の分岐で、反時計回りに最も近い分岐 Eに注目する。

[0073] {領域 X= {AD}、追跡済み分岐集合 = {B, C, D, F}、注目 =E}

(13)注目している分岐 Eが（10)で注目した Aと同一ではないので、（11)に戻る。

[0074] (11)注目してヽる分岐 Eカゝら伸びる輪郭線分 EBを領域 Xに追加する。

[0075] {領域 X= {AD, EB}、追跡済み分岐集合 = {B, C, D, F}、注目 =E}

(12)注目している分岐 E力追跡した輪郭の終端の分岐で、反時計回りに最も近い分岐 Aに注目する。

[0076] {領域 X= {AD, EB}、追跡済み分岐集合 = {B, C, D, F}、注目 =A}

(13)注目している分岐 Aが（10)で注目したものと同一なので次に進む。

[0077] (14)領域 Xを保存し、追跡済み分岐リストが空ではないので、（9)に戻る。

[0078] (9)新規の「領域 Y」を定義する。（図 8Βの (b)参照）

{領域 Y= U、追跡済み分岐集合 = {B, C, D, F} }

(10)追跡済み分岐集合力分岐 Βを取り出し、注目する。（図 8Βの (c)参照） {領域 Υ= { }、追跡済み分岐集合 = {C, D, F}、注目 =B} (11)注目して、る分岐 B力伸びる輪郭線分 BEを領域 Yに追加する。

[0079] {領域 Y= {BE}、追跡済み分岐集合 = {C, D, F}、注目 =B}

(12)注目している分岐 Bから追跡した輪郭の終端の分岐で、反時計回りに最も近い分岐 Fに注目する。

[0080] {領域 Y= {BE}、追跡済み分岐集合 = {C, D}、注目 =F}

(13)注目している分岐 Fが（10)で注目した Bと同一ではないので、（11)に戻る。

(11)注目して、る分岐 F力も伸びる輪郭線分 FCを領域 Yに追加する。

[0081] {領域 Y= {BE, FC}、追跡済み分岐集合 = {C, D}、注目 =F}

( 12)注目して、る分岐 Fから追跡した輪郭の終端の分岐で、反時計回りに最も近!ヽ分岐 Bに注目する。（図 8Bの（d)参照）

{領域 Y= {BE, FC}、追跡済み分岐集合 = {C, D}、注目 =B}

(13)注目している分岐 Bが（10)で注目したものと同一なので次に進む。

(14)領域 Yを保存し、追跡済み分岐リストが空でないので、（9)に戻る。

(9)新規の「領域 Z」を定義する。

[0082] {領域 Z= { }、追跡済み分岐集合 = {C, D} }

(10)追跡済み分岐集合力分岐 Cを取り出し、注目する。

[0083] {領域 Z= { }、追跡済み分岐集合 = {D}、注目 =C}

(11)注目している分岐 C力も伸びる輪郭線分 CFを領域 Zに追加する。（図 8Bの（e) 参照）

{領域 Z= {CF}、追跡済み分岐集合 = {D}、注目 =C}

( 12)注目して、る分岐 C力追跡した輪郭の終端の分岐で、反時計回りに最も近!ヽ分岐 Dに注目する。

[0084] {領域 Z= {CF}、追跡済み分岐集合 = { }、注目 =D}

(13)注目している分岐 Dが（10)で注目した Cと同一ではないので、（11)に戻る。

(11)注目している分岐 Dカゝら伸びる輪郭線分 DAを領域 Zに追加する。

[0085] {領域 Z= {CF, DA}、追跡済み分岐集合 = { }、注目 =D}

( 12)注目して、る分岐 Dから追跡した輪郭の終端の分岐で、反時計回りに最も近!ヽ分岐 Cに注目する。 (13)注目している分岐 Cが（10)注目したものと同一なので次に進む。

(14)領域 Zを保存し、追跡済み分岐リストが空なので次に進む。（図 8Bの (f)参照）

( 15)最初に登録した領域 Xは図形の外部を表すので破棄する。

(16) 図 7の処理の例（1)に戻る。

(1) 画像を最後まで走査して、追跡していない輪郭線が見付力もないため終了する

[0086] 以上の方法により、全ての領域は一つの輪郭線で囲まれ、且つ各輪郭線は隣接する領域に共有された線分として扱われる。このようにして生成された輪郭情報 250は、その後の処理における図形の拡大、縮小、移動などの処理において、領域が離れることなぐ従来手法の課題を完全に解決することができる。

[0087] 本発明によれば、ディジタル画像について、出発点の進行方向両端の画素の色と同じ関係の画素あるいは色差が所定値以上の画素の境界辺を追跡する輪郭追跡を行って輪郭線分を抽出する。そして、輪郭線を 3色以上が会合する点で輪郭の追跡を一度打ち切り、 2色の境界ごとに輪郭線を取ることで、隣接する 2つの領域が輪郭線データを共有できるようにする。輪郭線データが共有されることにより、異なる関数で近似されることも無くなり、データの処理効率 ·格納効率の低下を防止出来る。

[0088] また、画素の境界辺を追跡して輪郭線を抽出するので、元の画像の輪郭を正確に維持し、再現し得る。したがって、画像の拡大等の処理を行っても、輪郭線は画素の境界辺に沿ったものとなり、きめの細かい画像が維持される利点がある。

[0089] また、本発明では、輪郭線分の始端、終端、分岐点を端点として輪郭線分を抽出し、輪郭線分の接続状態を分岐点を経由しながら追跡し、閉ループを形成するか否かを判断して領域を抽出する。最外周の輪郭線は内周の領域の輪郭線と共通となる場合があり、その場合は輪郭線の内周側を採用する処理を行う。これにより、各領域は一本の輪郭線で囲まれた部分のみとなり、 2重に囲まれることはない。

[0090] また、本発明によれば、濃淡差を持つ画素間を先ず追跡し、特許文献 1で言う境界点とその繋がりを認識している。本発明によれば、濃淡差を持つ画素間を追跡するので、境界線が水平方向あるいは垂直方向であっても関係なく正確にこの境界線が見出すことが可能である。し力も方向を判断しながら追跡しているため、確実に境界を見出すことが可能となる。

[0091] また、本発明では、分割点の抽出と境界の抽出が同時に行われ、処理速度の向上が図られる。

図面の簡単な説明

[0092] [図 1]本発明に基く図形の輪郭追跡例の説明図である。

[図 2]本発明の基本となる座標点の取り方の説明図である。

[図 3]本発明の対象となる図形処理や画像処理を行う画像処理装置の一構成例を示す図である。

[図 4A]図 3の輪郭追跡処理部の具体的構成例を示す図である。

[図 4B]図 4Aの構成をより具体的に示した機能ブロック図である。

[図 5]図 4Bの輪郭線分抽出部における輪郭追跡のアルゴリズム及び画素パターンを示す図である。

[図 6]図 5の輪郭追跡の手順を示す図である。

[図 7]本発明の一実施例における輪郭線分結合分岐処理部の処理手順を示す図である。

[図 8A]図 7の輪郭追跡処理の手順をより具体的に説明する図である。

[図 8B]図 9の輪郭追跡処理の手順をより具体的に説明する図である。

[図 9]本発明の一実施例における領域輪郭形成処理の手順を説明する図である。

[図 10]従来技術における図形の輪郭追跡の説明図である。

[図 11]従来技術における課題の一例を示す図である。

符号の説明

[0093] 100…画像データの入力部、 150…図形データや画像データ、 200…輪郭追跡処理部、 210…入力部、 211〜AD変翻、 212…画像データ入力部、 213…画像データ 2次元配列部、 214…画像データメモリ格納機能、 216…画像メモリ、 218…濃淡差設定部、 220…輪郭線追跡部、 230…輪郭線分結合分岐処理部、 240· ··領域輪郭形成部、 250· ··輪郭情報、 300…関数近似処理部、 350…関数形式およびパラメータ、 400…画像処理部、 450…図形や画像、 500· ··出力部。

Claims

請求の範囲

[1] 画像処理装置によりディジタル画像の輪郭を追跡し画像領域を把握して輪郭情報を生成する画像処理方法であって、

入力されたディジタル画像について、出発点の進行方向両端の画素の色差と同じ画素の境界辺を追跡する輪郭追跡を行って輪郭線分を抽出する輪郭線分処理を行い、

抽出された前記輪郭線分に関して分岐処理及び合成処理を行!ヽ、該輪郭線分の結合で決まる輪郭を形成して前記ディジタル画像の輪郭情報を生成する、

ことを特徴とする画像処理方法。

[2] 請求項 1にお、て、前記輪郭線分処理にお!、て、前記画素の色が 3色以上で会合する点を前記輪郭線分の端点とする、ことを特徴とする画像処理方法。

[3] 請求項 1または 2において、対象とする前記画像を含む領域の任意の点から、水平方向あるいは垂直方向に走査し、前記画像の左右あるいは上下の色差が異なる画素点を見出し、その点を出発点として輪郭線分の追跡を行い、 3色以上の画素の会合点を探索し、該会合点を前記輪郭線分の端点の初期値とすることを特徴とする画像処理方法。

[4] 請求項 1な!、し 3の、ずれかにお 1、て、前記分岐処理は、輪郭線分の端点で、分岐方向を未追跡方向と追跡済み方向として個々〖こメモリ領域に登録し、

該メモリ領域の未追跡方向を参照してその一つを輪郭追跡の開始端点として輪郭追跡を実施し、

追跡完了時に追跡済み方向として前記メモリ領域に登録し、

新規な分岐点を見出したとき未追跡方向として前記メモリ領域に登録することを特徴とする画像処理方法。

[5] 請求項 4にお、て、前記輪郭線分合成処理は、追跡済みの輪郭線分を前記メモリ領域から読み出し、

異なる輪郭線分の同一端点を接合して輪郭の結合を行うことを特徴とする画像処理方法。

[6] 請求項 5において、輪郭の合成により閉領域が形成されたとき、その領域を一つの画像領域として前記メモリに登録することを特徴とする画像処理方法。

[7]

、て、与えられた前記画像の領域認識の基準となる画素の色の差ある、は輝度の差に基ヽて、前記輪郭線分処理を行うことを特徴とする画像処理方法。

[8] 請求項 1ないし 7のいずれかにおいて、前記輪郭追跡により生成された前記輪郭情報に基づき、画像領域の輪郭を近似して表す関数形式およびパラメータを生成し、該関数形式およびパラメータにより図形もしくは画像を生成することを特徴とする画像処理方法。

[9] 輪郭追跡部によりディジタル画像の輪郭を追跡し画像領域を把握して輪郭情報を生成する画像処理装置であって、

前記輪郭追跡部は、入力されたディジタル画像について、出発点の進行方向両端の画素の色差と同じ画素の境界辺を追跡して輪郭線分を抽出する輪郭線追跡処理部と、

抽出された前記輪郭線分に関して分岐処理及び合成処理を行!ヽ、該輪郭線分の結合で決まる輪郭を形成して前記ディジタル画像の輪郭情報を生成する領域輪郭形成部、とを備えていることを特徴とする画像処理装置。

[10] 請求項 9にお、て、前記輪郭線追跡処理部は、対象とする前記画像を含む領域の任意の点から、水平方向あるいは垂直方向に走査し、前記画像の左右あるいは上下の色が異なる画素点を見出し、その点を出発点として輪郭線分の追跡を行い、 3色以上の画素の会合点を探索し、該会合点を前記輪郭線分の端点の初期値とすることを特徴とする画像処理装置。

[11] 請求項 9または 10において、前記領域輪郭形成部は、分岐処理において、輪郭線分の端点で、分岐方向を未追跡方向と追跡済み方向として個々にメモリ領域に登録し、該メモリ領域の未追跡方向を参照してその一つを輪郭追跡の開始端点として輪郭追跡を実施し、追跡完了時に追跡済み方向として前記メモリ領域に登録し、新規な分岐点を見出したとき未追跡方向として前記メモリ領域に登録する機能を有することを特徴とする画像処理装置。

[12] 請求項 9ないし 11のいずれかにおいて、前記輪郭追跡により生成された前記輪郭情報に基づき画像領域の輪郭を近似して表す関数形式およびパラメータを生成する関数近似部と、該関数形式およびパラメータにより図形もしくは画像を生成する図形処理部とを備えて!/ヽることを特徴とする画像処理装置。

[13] コンピュータを備えた画像処理装置におヽて入力されたディジタル画像の輪郭を追跡し画像領域を把握し輪郭情報を生成するためのプログラムであって、

コンピュータに、

入力されたディジタル画像について、出発点の進行方向両端の画素の色差と同じ画素の境界辺を追跡する輪郭追跡を行って輪郭線分を抽出する輪郭線分処理を行う機能と、

抽出された前記輪郭線分に関して分岐処理及び合成処理を行!ヽ、該輪郭線分の結合で決まる輪郭を形成して前記ディジタル画像の輪郭情報を生成する機能、とを実現させるためのプログラム。

[14] コンピュータを備えた画像処理装置におヽて入力されたディジタル画像の輪郭を追跡し画像領域を把握し輪郭情報を生成するためのプログラムを保持した、コンビュータ読み取り可能な記録媒体であって、

コンピュータに、

抽出された前記輪郭線分に関して分岐処理及び合成処理を行!ヽ、該輪郭線分の結合で決まる輪郭を形成して前記ディジタル画像の輪郭情報を生成する機能、とを実現させるためのプログラムを記録した記録媒体。

[15] 請求項 1において、画像を水平方向あるいは垂直方向に走査し、隣り合う画素の色差が所定の色差となる 2つの画素を見出し、その 2つの画素の色関係（色および色差 )と同じにある水平方向、垂直方向の画素間を順次走査し、 3色以上の会合点となつたとき、その点を輪郭追跡の初期出発点とすることを特徴とする画像処理方法。