(57)【要約】【課題】円筒状画像を展開した矩形の画像データに従来の方法によるラベリングを施したあとで領域の隣接関係を調べるような処理時間とメモリ領域を必要とする処理をせずにラベリングを円滑に行う。【解決手段】本発明は、円筒状の画像において対象画素が接続部分にある場合でも近傍画素を参照する機能と、ラスター走査時に領域内の画素が未検出領域の最初の画素か、起検出領域の第二以降の未検出境界線に隣接する画素か、それ以外の領域内の画素かを判定する手段と、境界線追跡をしながら所定の規則に従ってラベル付けを行う手段と、例外的に検出されない境界線を検出する手段とを備えている。本発明によれば、まず領域の第一境界が追跡され、この領域内の画素についてラベル番号が付されると共に、第二以降の境界がある場合にはその境界が追跡されて同様に領域内の画素についてラベル番号が付され、全ての領域内の画素にラベル番号が付される。【選択図】　　　　図１
2004038720.tif 000002
【特許請求の範囲】
【請求項１】
矩形のマップ上に格子状に記録され仮想的に両端が隣接関係にある円筒状のトポロジーを持つ画像データにおいて、共通の特徴を有し且つ相互に連結された画素群を一つの領域として特定し、それぞれの領域に割り当てられたラベル番号をそれぞれの領域の画素に付与するラベリング処理を行う画像処理方法において、
画像の同一主走査線上における両端の画素同士が連結状態であるようにみなし、
それぞれの画素が、ラベリングされるべき領域の走査順序における最初の画素である第一の状態か、領域の第二以降の境界線と主走査方向に隣接し走査順序で最初に現れる画素である第二の状態か、あるいは領域内のそれ以外の画素である第三の状態かを走査順序に従って判定し、
該判定により第一の状態であると判定された画素を起点としてその領域の第一境界の画素を起点の画素に至るまで追跡し、追跡した画素の内、領域外の画素が主走査方向の逆方向あるいは副走査方向の逆方向に位置する画素にラベル番号を付し、
前記判定により前記第二の状態であると判定された画素を起点として第二以降の境界の画素を起点の画素に至るまで追跡し、追跡した画素の内、領域外の画素が主走査方向の逆方向あるいは副走査方向の逆方向に位置する画素にラベル番号を付し、
前記判定にて前記第三の状態であると判定された画素に同一領域内で既にラベル番号が付与された画素と同一のラベル番号を付与し
画像の両端が接続され円柱状のトポロジーを有する場合に検出できない円周方向に一周し一度も主走査と交わらない境界線を検出して境界線情報に追加する、ことから成る画像処理方法。
【請求項２】
矩形のマップ上に格子状に記録され仮想的に両端が隣接関係にある円筒状のトポロジーを持つ画像データにおいて、共通の特徴を有し且つ相互に連結された画素群を一つの領域として特定し、それぞれの領域に割り当てられたラベル番号をそれぞれの領域の画素に付与するラベリング処理を行う画像処理装置において、
画像の同一主走査線上における両端の画素同士が連結状態であるようにみなす近傍画素参照手段と、
それぞれの画素が、ラベリングされるべき領域の走査順序における最初の画素である第一の状態か、領域の第二以降の境界線と主走査方向に隣接し走査順序で最初に現れる画素である第二の状態か、あるいは領域内のそれ以外の画素である第三の状態かを走査順序に従って判定する判定手段と、
該判定手段により第一の状態であると判定された画素を起点としてその領域の第一境界の画素を起点の画素に至るまで追跡し、追跡した画素の内、領域外の画素が主走査方向の逆方向あるいは副走査方向の逆方向に位置する画素にラベル番号を付す第一境界追跡手段と、
前記判定手段により前記第二の状態であると判定された画素を起点として第二以降の境界の画素を起点の画素に至るまで追跡し、追跡した画素の内、領域外の画素が主走査方向の逆方向あるいは副走査方向の逆方向に位置する画素にラベル番号を付す第二以降境界追跡手段と、
前記判定手段にて前記第三の状態であると判定された画素に同一領域内で既にラベル番号が付与された画素と同一のラベル番号を付与するラベル番号複写手段と、
画像の両端が接続され円柱状のトポロジーを有する場合に検出できない円周方向に一周し一度も主走査と交わらない境界線を検出して境界線情報に追加する手段と
を備えたことを特徴とする画像処理装置。
【請求項３】
矩形のマップ上に格子状に記録され仮想的に両端が隣接関係にある円筒状のトポロジーを持つ画像データにおいて、共通の特徴を有し且つ相互に連結された画素群を一つの領域として特定し、それぞれの領域に割り当てられたラベル番号をそれぞれの領域の画素に付与するラベリング処理を行う画像処理プログラムにおいて、
画像の同一主走査線上における両端の画素同士が連結状態であるようにみなし、
それぞれの画素が、ラベリングされるべき領域の走査順序における最初の画素である第一の状態か、領域の第二以降の境界線と主走査方向に隣接し走査順序で最初に現れる画素である第二の状態か、あるいは領域内のそれ以外の画素である第三の状態かを走査順序に従って判定し、
該判定により第一の状態であると判定された画素を起点としてその領域の第一境界の画素を起点の画素に至るまで追跡し、追跡した画素の内、領域外の画素が主走査方向の逆方向あるいは副走査方向の逆方向に位置する画素にラベル番号を付し、
前記判定により前記第二の状態であると判定された画素を起点として第二以降の境界の画素を起点の画素に至るまで追跡し、追跡した画素の内、領域外の画素が主走査方向の逆方向あるいは副走査方向の逆方向に位置する画素にラベル番号を付し、
前記判定にて前記第三の状態であると判定された画素に同一領域内で既にラベル番号が付与された画素と同一のラベル番号を付与し
画像の両端が接続され円柱状のトポロジーを有する場合に検出できない円周方向に一周し一度も主走査と交わらない境界線を検出して境界線情報に追加する、各手順を実行させるための画像処理プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像データから画像処理に必要な構造を抽出し、より高度な情報処理を行うための前段階の処理となるラベリング処理を、円筒状の連続性がある画像データを対象にした場合も効率的に行えるようにする画像処理方法および装置、並びにプログラムに関する。
【０００２】
【従来の技術】
画像データ内の構造を抽出することは画像処理において重要な処理の一つである。データ構造は、画像を島状の特徴が連続した領域に分割し、おのおのの計量的な特徴量や相互の位置関係を抽出することで行う。この前段階の処理として、分割された領域についてそれぞれに固有の番号（ラベル）をつけ、画像の画素から領域番号が参照できるようなラベル画像を作成することが必要となる。この処理はラベリングと呼ばれる。格子状の画素配列を持つ画像を対象にした場合、領域内の４−近傍（画像上の上下左右）を連続とした条件の場合には領域外の点の連続条件は８−近傍（画像上の上下左右及び斜め左上、右上、左下、右下）となり、逆に領域内の点が８−近傍で連続であれば領域外の点は４−近傍で連続になる。以降では、４−近傍の連続条件を「４−連結」、８−近傍の連続条件を「８−連結」と呼ぶことにする。
【０００３】
従来、このような目的のためには、以下に示すような手法が採られていた。
その第１はたとえば総研出版の「コンピュータ画像処理入門」に示されている手法であり、端的には画像上を順次ラスター走査してラベリングされていない画素をまず見つけ出し、この画素に隣接していてしかも未だラベリングされていない画素に順次ラベリングを拡大してゆく手法である。
【０００４】
具体的には図５ａに示す如き３領域５１、５２、５３が存在する画面を考え、領域５１，５２，５３を構成する画素には‘０’が、領域５１，５２，５３外の画素には、‘−１’がそれぞれ予め与えられているものとする。なお、図５ｃは図５ａの画面を上述の‘０’または‘−１’のデータで表示した模式図である。
【０００５】
まず画面を、図５ａに矢符にて示す如く画面の左上隅から右方向へ主走査が、上から下方向へ副走査がそれぞれ行われ、この走査の順にラスター走査し、未だラベル番号が割り当てられていない画素（‘０’の画素）を見つけ出す。図５ａの例では領域５１の最上端ラインにおける左端の画素、即ち図５ｃに下線を付して示した‘０’の画素（第５ラインの第７画素）が最初に見つけられる。そして一旦ラスター走査を停止し、この画素に未使用のラベル番号（１以上）を割り当てる。次にこの画素の８−近傍の８画素の内の‘０’の画素で未だラベル番号が付されていない画素にも同一のラベル番号を付与する。更にそれらの画素における８−近傍の画素の中で‘０’の画素で未だラベル番号が付されていない画素にも同一のラベル番号を付与する。なお、この例では領域内は８−連結であり、領域外は４−連結である。
【０００６】
以上の処理を新たにラベル番号を付与することが可能な画素が無くなるまで順次反復すると、一つの島状の領域５１を構成する総ての画素に同一のラベル番号を割り当てることが出来る。この処理は図５ｂに示す如く、ちょうど領域５１の一つの画素から順にラベル番号が領域内へ伝播してゆくような状態でラベリングの処理が実行される。
【０００７】
このようにして一つの領域５１のラベリング処理が終了すると、再度ラスター走査が行われ、次の‘０’，の画素を見つけ出す。図５ａの例では領域５２の最上端ラインにおける左端の画素が見つけ出される。以下、前述の領域５１の場合と同様の処理が反復されて領域５２のラベリング処理が行われ、更に領域５３のラベリング処理も行われる。
【０００８】
最後にラスター走査が画面の右下端に至った時点で全体の処理が完了する。なお、図５ｄは領域５１にラベル番号Ａが、領域５２にＢが、同５３にＣがそれぞれ割り当てられて処理が終了した状態を示している。
【０００９】
第２の手法は、たとえば「スパイダーマニュアル」（株式会社情報技術コンソーシアム刊）に示されている手法であり、端的には、画素それぞれに順次的に新規のラベル番号またはその画素と隣り合っていて既にラベル番号が割当て済みの画素と同一のラベル番号を割り当てる手法である。
具体的には、画面をラスター走査して‘０’の画素、即ちラベリングされるべき領域内であり且つ未だラベル番号が割り当てられていない画素を見つけて処理対象の画素とし、図６ａに示す如く、‘０’の値を有する処理対象画素（図上で下線を付して示す）の８−近傍の画素総てが‘−１’か‘０’のいずれかの画素であればその画素に新たなラベル番号Ｎ（１以上）を割り当てる。同時に別途用意してある作業用メモリのＮ番地にラベル番号値Ｎを書き込んでおく。
【００１０】
一方図６ｂに示す如く、処理対象画素の８−近傍の画素総てが‘−１’か‘１’以上の値Ｋの画素である場合、即ち処理対象画素が領域外の画素及び同一のラベル番号Ｋが既に割り当てられている画素に囲まれている頓合には、その処理対象画素は既にラベル番号Ｋが割り当てられている画素と同一の領域に含まれるべき画素であるから、そのラベル番号Ｋを処理対象画素にも割り当てる。
【００１１】
更に図６ｃに示す如く、処理対象画索の８−近傍の画素が異なった１以上の値Ｋ１〜Ｋｎ（図示例ではＫ１及びＫ２）を有する画素である場合、即ち処理対象画素が領域外の画素及び異なるラベル番号Ｋ１〜Ｋｎが既に割り当てられている画素に囲まれている場合には、その内の最小の値、即ち最小のラベル番号を求め、これをＫｓとする。そして処理対象画素にラベル番号としてＫｓを付つと共に、作業用メモリのＫ１〜Ｋｎ番地の記憶内容を総てＫｓに書換える。
【００１２】
以上のような処理は、図６ｃの例に即して具体的に説明すると、下線が付された処理対象画素は既にラベル番号Ｋ１及びＫ２が割り当てられている二つの画素に挟まれた画素であるが、実際にはラベル番号Ｋ１、Ｋ２が付された三つの画素と処理対象画素とは連続しており、総て同一の領域に属していることになるので、一方のより小さいラベル番号に総一する処理が行われるということである。
このような処理が行われると、一旦割り当てられたラベル番号が他のより小さいラベル番号に統合されることになるため、メモリに記憶されているラベル番号に空番が生じる。従って、ラスター走査が終了した時点で、空番を埋めるように作業用メモリに記憶されているラベル番号値を整理して図７のように書き換える。
【００１３】
そして、この段階では画像上の各領域に含まれる画素には確定したラベル番号自体が書き込まれているのではなく、図７の左側に示されているような作業用メモリの番地が書き込まれており、従って同一の領域内の画素に異なる番号が書き込まれている場合もある。そこで上述の如き飛び番号を整理した後、再度ラスター走査を行い、１以上の値を有する画素、即ち領域内に含まれる画素それぞれにその画素の値に対応する作業用メモリの番地の記憶内容、つまり図７の右側に示されているように各番地の記憶内容を整理した後のラベル番号を書き込む。この処理により、各領域の画素には１から連番でラベル番号が割り当てられることになる。以上でこの手法によるラベリングの処理が完了する。
【００１４】
その第３は特許１８５７４９９号（特公平５−７０８７４号公報）において説明されている方法で、ラスター走査で未検出の領域の境界線を見つけ、境界線を追跡しながらその一部の画素にラベル番号をつけ、境界線から離れた画素については境界線付近につけたラベル番号をラスター走査しながら伝播する方法である。ここでは、領域内部が４−連結の場合について述べる。
具体的には、ラスター走査を行いつつ、まず図９の条件のどれかにあてはまる領域内部のラベル付けがされていない画素を探す。ここで、下線を引いた０はラベル付けされていない対象画素、−１は領域外の画素、Ｋはすでにラベル付けがされた画素で、その値は１以上の整数Ｋということを意味する。ラスター走査で遭遇するラベル付けがされていない画素はこの三通りのいずれかになる。
【００１５】
図９ａの場合、対象画素は未検出領域の最初の画素であるので、対象画素から外周境界線の追跡を行う。このとき、追跡の経路にある画素に、追跡と同時に図２６に示した規則に従って、入力方向と出力方向の組み合わせによってラベル付けを行う。ラベル付けする番号は既存の領域番号の最も大きなものをＮとするとＮ＋１になる。なお、入力および出力方向の番号は図１０に示した方向である。また、この例では領域外の画素を常に左に見るように、時計回りに追跡するものとする。図２６で○になっている部分は必ずラベル付けされる画素で、×はラベル付けしてはいけない画素、空白はどちらでも構わないことを意味する。外周境界の追跡は最初の画素で終了する。
【００１６】
図９ｂの場合、対象画素は既知の領域（領域番号Ｋで表される）内に存在する未検出の内側境界の隣接画素である。このような内側境界は、領域内に無い場合もあるし、複数個存在する場合もある。ここにおいては、この内側境界を今度は反時計回りに追跡する。内側境界であるので、この場合も領域外の画素を左に見て進むことになる。ここでも、図２６に示した規則に従って領域番号Ｋのラベル付けを行う。
図９ｃの場合、対象画素は領域Ｋ内の画素であるので、この画素にラベルＫをつける。
【００１７】
図８ａ〜ｅに示したのが、この過程を示した模式図である。図８ａが領域１を検出した時点、同ｂが外周の追跡の結果、境界線の一部にラベル付けがされた時点、同ｃがラスター走査によるラベル付けが進み、内側境界線を検出した時点、同ｄが内側境界線を追跡してラベル付けをおこなった時点、同ｅが全てのラベル付けが完了した時点である。
【００１８】
上で述べたのは領域内が４−連結、領域外が８−連結という領域の定義の際に用いられる方法の一つであるが、同様にして領域内が８−連結、領域外が４−連結の場合にも同じアルゴリズムが適用可能である。この際には、ラスター走査時の判定状態は図１１のようになり、境界線追跡時のラベル付け条件は図１２のようになる。
上述した方法は、先に述べた第１、第２の方法に比べて高速性が期待でき、余分なメモリ領域も必要としない。また、境界線の情報が必要な場合には、ラベリングと同時に境界線情報を得ることが可能である。
【００１９】
【発明が解決しようとする課題】
ところで、前述の第１の手法では、ラスター走査により新たに領域が見出された場合に実行されるラベル番号の伝播の処理が非常に複稚であり、一般的な逐次型コンピュータではその処理時間が長大になり、また実際の適用に際してはハードウェア的に実施する場合にもまたソフトウェア的に実施する場合にも非常に複雑になるという難点がある。
【００２０】
また第２の手法では、処理実行中にしばしば作業用メモリの総てを調べる必要が生じるため処理時間が相当程度長時間化し、また最大限画像メモリと同容量の作業用メモリが必要であり、更にラスター走査を２回行う必要がある等、処理時間が長大化する問題がある。
【００２１】
第３の手法では、これらの点で上記二つの方法よりも優れており、一般的な画像を対象とする場合には問題なく処理できる。
しかし、画像が左右の端が接続された円筒状のトポロジーを持つような画像である場合、取り扱いが困難になる。円筒状の画像データは、例えば対象物体を回転させながらスリット光を照射するような三次元データ入力装置によって得られるもので、ちょうど矩形の画像データの両端をつないで連続にしたもので表現される。計算機の記憶装置内などで記録されている状態では、矩形の画像と同様の形態で表現されているが、参照する際には右端のデータと同じ主走査線にある左端のデータが隣り合うものとして扱う。
【００２２】
円筒状の画像データを矩形の状態でまずラベリングし、その後に連結部分の領域の接続関係を調べる方法がありうる。しかし、この方法は、ちょうど第２の従来方法の図７を用いた領域番号のつけなおしが必要になる。これは第２の従来方法の部分でも説明したように、プログラムの実行時間や作業メモリを増大させるという問題がある。
従って、円筒画像のままラベリングを行うことが望ましいが、その場合、左右の画像の連結部分における４−近傍あるいは８−近傍の画素の参照が問題となる。記憶されている配列ではこれらのデータは隣接関係にあるようなアドレスで記録されていない。従って、何らかの方法で簡単に接続部分をまたがった近傍画素を参照できるようにする必要がある。
【００２３】
また、第３の方法における問題の一つは、ラスター走査における判定条件である。すなわち、図９ａに示す領域の外周追跡開始状態と図９ｃに示す領域内状態である。これらは、いずれも主走査方向の逆方向である左隣の画素が同一領域内の画素である場合にそこにはすでに領域番号のラベルがつけられているという仮定に基づいている。しかし、円筒状画像の場合、これは必ずしも成り立たない。円筒画像の接合部においては、左隣の画素はラスター走査の主走査における最後の画素であるので、そこが領域内部画素であり、かつ領域番号が未定義となる場合がある。従って、図９に示された判定条件では不十分である。
【００２４】
第３の方法におけるもう一つの問題点は、境界線追跡時のラベル付けの条件である。円筒状の画像においては、矩形の画像と異なり、領域の境界線が連結部を横切る場合が存在する。そのような場合、図１３に示すように従来方法ではラベルが図２６に示された条件によってはラベル付けされない場合が出てくる。
さらに、ある主走査線（水平線）と一致する第二以降の境界線がある場合、この境界線はラベリング処理では追跡されない。ラベリング自体には影響がないが、境界線情報を同時に取得する際には、問題がある。
【００２５】
本発明では、上述の第３の従来手法を改良して円筒状画像にも適用できるようなアルゴリズムを実現することを目的とする。これにより、円筒状画像を展開した矩形の画像データに従来の方法によるラベリングを施したあとで領域の隣接関係を調べるような処理時間とメモリ領域を必要とする処理をせずにラベリングを円滑に行うことができる。
【００２６】
【課題を解決するための手段】
本発明は、円筒状の画像において対象画素が接続部分にある場合でも近傍画素を参照する機能と、ラスター走査時に領域内の画素が未検出領域の最初の画素か、起検出領域の第二以降の未検出境界線に隣接する画素か、それ以外の領域内の画素かを判定する手段と、境界線追跡をしながら所定の規則に従ってラベル付けを行う手段と、例外的に検出されない境界線を検出する手段とを備えている。
【００２７】
本発明は、画像メモリ上に二次元配列として記録された円筒状画像データに対して、４−近傍あるいは８−近傍の隣接画素を参照する際に対象画素が接続部分にある場合には接続部分をまたがって参照する機能と、ラベリング処理を行う際に、ラスター走査の過程でラベル付けされていない領域内の画素が検出されたときに、ある領域内の画素のうちで最初の画素である第１の状態か、第二以降の境界線上の画素である第２の状態か、それ以外の第３の状態かを判定する改良された手段と、前記判定手段により第１の状態であると判定された画素を起点として領域の第一境界線を起点の画素に至るまで追跡し、追跡した境界線の画素について主走査方向の逆方向あるいは副走査方向の逆方向に領域外の画素がある場合にラベル付けを行う改良された第一境界追跡手段と、前記判定手段により第２の状態であると判定された画素を起点として第二以降の境界線を起点に至るまで追跡し、追跡した境界線の画素について主走査方向の逆方向あるいは副走査方向の逆方向に領域外の画素がある場合にラベル付けを行う改良された第ｎ境界追跡手段と、前記判定手段により第３の状態であると判定された画素を主走査方向の逆方向あるいは副走査方向の逆方向の画素と同一のラベル付けを行うラベル書き込み手段と、境界線の情報を必要とする際に円柱状の画像データの円周方向に一回転する第ｎ境界線を検出する手段とを備えたことを特徴とする。
【００２８】
本発明によれば、まず領域の第一境界が追跡され、この領域内の画素についてラベル番号が付されると共に、第二以降の境界がある場合にはその境界が追跡されて同様に領域内の画素についてラベル番号が付され、全ての領域内の画素にラベル番号が付される。そして境界線情報が必要な場合には境界線情報が得られる。
【００２９】
【発明の実施の形態】
以下、本考案をその実施例を示す図面に基づいて詳述する。なお、以下の実施例は、領域内部は４−連結、領域外は８−連結とする。領域内部が８−連結で領域外が４−連結の場合は後述する。また、ラスター走査の順序は、主走査が画面の左から右へ向かい、副走査が上から下へ行われるものとする。
【００３０】
用語の表記は次に示すものを使う。最初に発見される境界線を第一境界線、第二以降の境界線を第ｎ境界線と呼ぶ。これは、円筒状の画像においては、最初に発見される境界が必ずしも外周と呼ぶのにふさわしくないためである。主走査方向の位置のパラメータをｃｏｌ、副走査方向の座標を　ｒｏｗ　とし、それぞれ、０　≦　ｃｏｌ　≦　ＣＭＡＸ−１　、０　≦　ｒｏｗ　≦　ＲＭＡＸ−１　の値を持つものとする。すなわち、画素の個数は、主走査方向に　ＣＭＡＸ桁、副走査方向に　ＲＭＡＸ行である。
【００３１】
図１は本発明の実施例における処理のアルゴリズムを示したフローチャートであり、ソフトウェアあるいはハードウェアにより実現される。図１は、ラベリング処理を示している。対象とする画像は、輝度など所定の条件のもとに、領域外の画素は−１、領域内部の画素は０の値によって初期化されている。これをラスター走査によりすべての画素を調べていく。領域数Ｎは０に初期化する。
ラスター走査の過程で、領域内で値が０の画素を発見すると、そこでラスター走査を止めて、画素状態の判定を行う。このとき、図１４の判定条件を用いる。すなわち、上隣の画素値が−１でかつ左隣の画素値が−１の場合（ａ）あるいは０の場合（ｄ）は第１の状態、上隣の画素値が０より大（領域番号）でかつ左隣の画素値が−１である場合（ｂ）は第２の状態、左隣の画素値が０より大（領域番号）（ｃ）あるいは左隣の画素値が０でかつ上隣の画素値が０より大（領域番号）（ｅ）の場合は第３の状態とする。これは、従来方法である図９にｄおよびｅを追加したものである。
【００３２】
この変更の効果を表した例が図１５である。ここでは、図の視認性のために０は省略している。ラスター走査は右へ向かう走査が主走査で、下へ向かう走査が副走査であるので、矩形の領域の第一境界線を発見する最初の画素は、Ａで表した（ｃｏｌ，ｒｏｗ）＝（０，３）の画素である。しかし、左隣の画素ａ（１９，３）はラスター走査の順番では後方であるので、まだ領域番号はつけられておらず、この状態は第３の従来方法における図９のどの場合にも該当しない。しかし、ここで境界の検出をする必要があるので、この状態を第１の状態に追加する必要がある。また、同様に、画素Ｂ（０，６）においては第３の状態であるが、左隣はまだ領域番号が指定されていない領域内部画素であるので、領域番号を複写できない。この場合は、画素ｂ’（０，５）が領域内部画素であればそこはラスター走査の前方に位置し、すでに領域番号がつけられているので、番号の複写が可能である。同様の問題が画素Ｃにおいてもおきる。この場合、近傍に領域番号を持つ画素が存在しなくなるので、後述する追跡時にラベルを付与することで対応する。
【００３３】
この隣接画素の画素値を参照する際には、図２に示した近傍画素参照機能のサブルーチンによって連結部をまたがった参照を行う。ここでは、まず４−近傍の座標を求め、次にそれが矩形画像の範囲から外れている場合に接続部分をまたがった参照と解釈し、横方向の座標出力値　ｃ１　の値を補正している。
【００３４】
第１の状態であった場合には、新しい領域を発見したことを意味するので、領域数Ｎを１増やし、その画素を起点にして領域Ｎの第一境界の追跡を行う。以下の説明では、領域の外側の画素を常に左側にみるような追跡方法について述べる。追跡時は、進行方向から向かって左側から時計回りの隣接画素の値を調べ、そこが領域内であれば、進行する。すなわち、ある追跡中の画素に進行してきた方向番号をｄ０　とすると、次の進行方向番号は、（ｄ０＋３）％４，　ｄ０，　（ｄ０＋１）％４，　（ｄ０＋２）％４　の順に調べ、最初に進行可能であった方向である。なお、上で方向番号と呼ぶものは図１０における方向番号を示し、％は剰余を意味する演算子である。起点においては、上隣の画素が領域外であることは自明なので、０、１、２の順に領域内の画素であるかどうかを試し、最初に領域内の画素であった方向に進む。
【００３５】
以上のように領域の境界線を追跡し、注目画素が起点に戻り、さらに進行方向も起点における進行方向となったときに一周を完了したものとして追跡を終了する。
この追跡の過程で、主走査方向の反対方向（方向番号２）および副走査方向の反対方向（方向番号３）に領域外の画素がある場合に、ラベル番号を画素に付与する。これにより、この後のラスター走査において、状態３の画素が隣接した画素から値を複写することにより領域番号の伝播を可能にする。このための条件が、図２８に示した入力方向と出力方向の対応表によって与えられる。ここで、○あるいは◎の記号はラベルを付与する状態、×はラベルを付与しない状態、空白はどちらでもよいことを示す。このうち、◎は本発明において改良された条件を示している。これは、従来法における図２６においては空白であった部分であるので、従来法と上位互換性を保っている。
【００３６】
図１３が、図２６から図２８への変更の必要性を示した図である。図１３ａ〜ｃのように、円筒画像の連結部でｃｏｌ＝ＣＭＡＸ−１の画素からｃｏｌ＝０の画素に、０方向に追跡が進み、その後３以外の方向に進む場合、図１３で太枠により囲った画素には、従来方法によってはラベルがつかない。これは、本発明で改良された図１４の判定方法によっても不可能である。すなわち、追跡時にラベルの付与がされなければ、ラスター走査時に付与する必要が生じるが、いずれの場合も上隣の画素は領域外であり、左隣の連結部をまたがった画素は、ラスター走査において注目している画素より後ろであるので、ラベル番号を持たないからである。すなわち、上隣が境界線、左隣が領域内の画素である場合、換言すれば入力方向が０で出力方向が０〜３の場合はラベル付与が必要になる。幸いなことに、これら全ての入出力方向の組み合わせは、図２６における空白の状態であるので、ここを○に変更しても第ｎ境界線の検出には影響しない。そこで、これらの場合を変更することで、円筒画像にも対応し、互換性のある処理が可能となる。
【００３７】
以上の追跡時のラベル付け処理は、第ｎ境界線の追跡時にも同様に行う。ラスター走査において、第２の状態になった場合には、既存の領域Ｋにおける未検出の境界線を発見したことを意味するので、この境界線の回りをやはり領域外を進行方向の左側に見るように進み、第１境界線と同様にラベル付けを行う。このとき、判定条件より左隣の画素が領域外であり、かつ上隣の画素が領域内であることは自明であるので、起点における進行方向は必ず３の方向になる。
【００３８】
第ｎ境界線の判定条件を満たす最初の隣接画素が必ず発見されるためには、以前に検出された境界線の追跡時にこの画素がラベル付けされないようにしなければいけない。第２の状態の画素を他の境界線が通過する場合は、図１６の３通りのみである。従って、これらの場合には追跡時にラベル付けをしてはならず、それが図２８の×に対応している。
ラスター走査において、第３の状態になった場合は、隣にすでにラベル付けがされた画素が存在している状態である。従って、ラベル番号を複写するだけでよい。ただし、上で述べたように、円筒画像の連結部では、左隣がラスター走査で順番が後方となる画素であり、領域番号が未定義の場合があるので、そのような場合には、確実にラスター走査で前方の画素である上隣の画素から複写する。
【００３９】
図１３を使って具体的なラベル付けの過程の説明を行う。以下の図面では、視認性をよくするために未定義の領域番号０は空白として表している。ラスター走査によってまず図１７の画素Ａ（０，３）が領域内の画素として検出される。そこで、状態の判定を行うと、ここは図１４ｄの条件を満たすため、第１の状態である。そこで、領域数Ｎを増加して１にし、Ａを起点にして第一境界線を追跡する。
図１８に示したのが、境界追跡によるラベル付けの結果で、ラベルのつけられた画素には太字で領域番号１が書き込まれている。また、領域追跡した経路には陰影をつけてある。
【００４０】
この後、図１９に示すように画素Ｂ（０，４）において次のラベル付けされていない領域内画素が検出される。この画素では、上に領域番号１、左が未定義の領域内画素であるため、図１４ｅの状態であり、第３の状態であると判定される。従って、上隣の画素の領域番号を複写して領域番号を１とする。Ｂの右につながる陰影をつけた画素および画素Ｃ（１３，４）およびその右側の陰影をつけた画素においては、左隣の画素が常に領域番号を持つため、図１４ｃの状態となり、これも第３の状態であると判定され、領域番号１が次々と複写されていく。ｒｏｗ＝５から１２行までは同様に第３の状態であることによる領域番号の複写が繰り返される。
【００４１】
図２０は、１２行目までのラベル付けが終わった状態を示す。この段階で新たにラベル付けされた画素の番号を太字でしめしてある。次に検出される未定義の画素はＤ（２，１３）である。ここでは、左隣が−１，上隣が領域番号１であるので、図１４ｂの状態となり、第２の状態であると判定される。
【００４２】
図２１は、画素Ｄを起点にして第二境界を追跡してラベル付けをした結果である。この追跡によって新たにラベル付けされた画素には太字の１が書かれている。追跡経路内には以前のラスター走査によってラベル番号を付与された画素もあるが、それは太字でない文字で表されている。この後、第１３行、第１４行の画素について、ラスター走査によるラベル付けが行われていき、それは画素Ｅ（１５，１５）に至るまで続く。
画素Ｅでは、図１４ａの状態となるので、ここで新しい領域が検出される。領域数Ｎは増加して２となり、画素Ｅには領域番号２が与えられ、その隣の画素も境界線追跡の過程で領域番号２が与えられる。
【００４３】
図２２は、上述の処理までが完了した様子を示す。この後、ラスター走査により、未定義の画素Ｆ（０，１６）が検出され、画素Ｂと同様にここから領域番号１の複写が始まり、領域の最後まで到達する。図２３は、以上の処理が完了して領域番号がすべての領域内画素に付与された様子を示す。
以上の処理によってラベリングは終了するが、　ｒｏｗ＝１７の境界線は追跡されていない。境界線の情報を必要とする場合には、ここで改めて追跡されなかった境界線を探す必要はない。例えば、図３にある列属性記録ルーチンのように、横２縦ＲＭＡＸ個の要素をもつテーブルを用意し、初期値を０にしておく。ラスター走査時に平行して領域内の画素か領域外の画素かを記録する。ラベル付けが全て終了したあとで、図４に示すような判定ルーチンにより領域画素のみの列のあとに領域外画素のみの列が存在するかどうかを確認する。図１３の例の場合、その結果は図２４のようになり、図３の判定ルーチンの条件を満たすものは図中の陰影をつけた部分のみであり、求める境界線は第１７行にあることがわかる。なお、領域内が８−連結で、領域外が４−連結の場合には、ラスター走査時の判定条件と境界線追跡時のラベル付与規則を変更することにより、同様の手法で処理が可能である。図２５に示すのがラスター走査時の判定条件であり、図２９に示すのが境界線追跡時のラベル付け規則である。それぞれ、図１１および図２７を円筒画像用に敷衍したものである。
【００４４】
図２５ａ〜ｃは図１１ａ〜ｃと同じものであるが、第１の状態の判定条件として同ｄが、第３の状態の判定条件として同ｅ、ｆが追加されている。いずれも、円筒画像の接合部分　ｃｏｌ　＝＝　０　において発生する状況に対応している。図２９は、図２７の空白部分に新たな○を追加したもので、その意味は４−連結の場合と変わらない。
また、図２における近傍画素参照のアルゴリズムも影響を受けるが、変える部分はオフセットテーブル　ｏｆｆ＿ｃ　および　ｏｆｆ＿ｒ　のみである。それぞれの配列の要素を８個にし、図１２の方向番号を反映した値にすることで対応できる。
【００４５】
また、上記実施例では、主走査方向が画面の左から右へ、副走査方向が上から下へという場合について説明したが、他の方向に走査する場合でも、本発明の手法は適宜対応可能である。境界線の追跡方向も、領域外を左に見て時計回りに回るか、反時計回りに回るかは本質ではない。その都度回り方によって使う表を変えれば同様の処理は可能である。
【００４６】
【発明の効果】
以上のように、本発明によれば、従来法の手法の判定条件とラベル付け規則を変更するだけで、ラベリング処理の対象を矩形の画像から円筒画像に敷衍できる。領域の連続性の条件は４−連結の場合だけでなく、８−連結の場合も取り扱いが可能である。
【図面の簡単な説明】
【図１】本発明のラベリング処理を示すフローチャートである。
【図２】ラベリング処理の過程で必要な近傍画素を円筒画像において参照するサブルーチンのフローチャートである。
【図３】列情報記録サブルーチンのフローチャートである。
【図４】円周状の境界線を検出するサブルーチンのフローチャートである。
【図５】（ａ）は第一の従来手法におけるラスター走査の様子を示す模式図、（ｂ）は領域番号の伝播の状態を示す模式図、（ｃ）は画像の初期データを表した模式図、（ｄ）はラベル付けされた画像の状態を示す模式図である。
【図６】第二の従来手法を示す模式図である。
【図７】第二の従来手法に基づくメモリ内容を説明する図である。
【図８】第三の従来手法における処理の過程を示した模式図である。
【図９】第三の従来手法において領域が４−連結の場合のラスター走査時の判定条件を説明するための図である。
【図１０】４−近傍の方向番号を示す図である。
【図１１】第三の従来手法において領域が８−連結の場合のラスター走査時の判定条件を説明するための図である。
【図１２】８−近傍の方向番号を示す図である。
【図１３】円筒状の画像における第三の従来手法の不具合を示す模式図である。
【図１４】本発明手法における領域が４−連結の場合のラスター走査時の判定条件を説明するための図である。
【図１５】判定条件の増加を説明する模式図である。
【図１６】本発明手法において領域が４−連結の場合の境界線追跡時にラベル付けしてはならない場合の模式図である。
【図１７】本発明手法において領域が４−連結の場合での処理例を示す第１の模式図である。
【図１８】図１７の第１の模式図よりも処理が進んだ第２の模式図である。
【図１９】図１８の第２の模式図よりも処理が進んだ第３の模式図である。
【図２０】図１９の第３の模式図よりも処理が進んだ第４の模式図である。
【図２１】図２０の第４の模式図よりも処理が進んだ第５の模式図である。
【図２２】図２１の第５の模式図よりも処理が進んだ第６の模式図である。
【図２３】図２２の第６の模式図よりも処理が進んだ第７の模式図である。
【図２４】図１３の例の場合に追跡されない境界線を発見する例である。
【図２５】本発明手法において領域が８−連結の場合でのラスター走査時の判定条件である。
【図２６】図９に示した第三の従来手法におけるラベル付けを説明するための図である。
【図２７】本発明手法におけるラベル付けを説明するための図である。
【図２８】状態３の画素が隣接した画素から値を複写するための条件を与えるための対応表である。
【図２９】境界線追跡時のラベル付け規則である。
【図１】
2004038720.tif 000003
【図２】
2004038720.tif 000004
【図３】
2004038720.tif 000005
【図４】
2004038720.tif 000006
【図５】
2004038720.tif 000007
【図６】
2004038720.tif 000008
【図７】
2004038720.tif 000009
【図８】
2004038720.tif 000010
【図９】
2004038720.tif 000011
【図１０】
2004038720.tif 000012
【図１１】
2004038720.tif 000013
【図１２】
2004038720.tif 000014
【図１３】
2004038720.tif 000015
【図１４】
2004038720.tif 000016
【図１５】
2004038720.tif 000017
【図１６】
2004038720.tif 000018
【図１７】
2004038720.tif 000019
【図１８】
2004038720.tif 000020
【図１９】
2004038720.tif 000021
【図２０】
2004038720.tif 000022
【図２１】
2004038720.tif 000023
【図２２】
2004038720.tif 000024
【図２３】
2004038720.tif 000025
【図２４】
2004038720.tif 000026
【図２５】
2004038720.tif 000027
【図２６】
2004038720.tif 000028
【図２７】
2004038720.tif 000029
【図２８】
2004038720.tif 000030
【図２９】
2004038720.tif 000031