(57)【特許請求の範囲】
【請求項１】
画像の輪郭を抽出する方法であって、
(a) 前記画像において濃度値の最大値を示す画素から降順に１画素ずつ注目画素を抽出する工程と、
(b) 前記注目画素の周囲の複数の輪郭辺が既成輪郭線に包含されていない場合には、前記複数の輪郭辺からなる輪郭線を新規輪郭線として設定し、当該新規輪郭線の接続状態を示す輪郭線接続情報を生成するとともに、前記注目画素の前記複数の輪郭辺のうちのいずれか１つを選択した当該新規輪郭線の開始辺と、前記注目画素の濃度値を当該新規輪郭線の有効濃度範囲の開始濃度とした開始濃度値とを含む輪郭線管理情報を生成する工程と、
(c) 前記注目画素の前記複数の輪郭辺のうちのいずれかが既成輪郭線に包含されている場合には、当該既成輪郭線についての前記輪郭線接続情報を更新する工程と、
(d) 前記更新によって前記注目画素のいずれかの前記輪郭辺が包含されていた少なくとも１つの既成輪郭線が消滅する場合、又は抽出すべき注目画素が無くなった場合には、前記既成輪郭線についての前記輪郭線管理情報に対して前記注目画素の濃度値を前記既成輪郭線の有効濃度範囲の終了濃度を示す終了濃度値として追加する工程と、
を有することを特徴とする画像の輪郭抽出方法。
【請求項２】
請求項１に記載の画像の輪郭抽出方法において、
前記画像における同一の濃度値を示す画素を前記注目画素として、前記(a)ないし(d)工程を繰り返し行うことによって生成／更新された前記輪郭線接続情報を出力することを特徴とする画像の輪郭抽出方法。
【請求項３】
請求項１に記載の画像の輪郭抽出方法において、
(e) 前記(a)ないし(d)工程を繰り返し行うことによって生成された前記輪郭線管理情報を記憶する工程と、
所定の濃度値の輪郭線を抽出する際に、
(f) 前記輪郭線管理情報に含まれる前記開始濃度値と前記終了濃度値とによって示される前記有効濃度範囲に基づいて前記所定の濃度値の輪郭線を特定し、当該輪郭線についての前記輪郭線管理情報から前記開始辺を取得する工程と、
(g) 前記開始辺から所定の規則に従って輪郭辺を順次抽出していく工程と、
を有することを特徴とする画像の輪郭抽出方法。
【請求項４】
請求項１ないし請求項３のいずれかに記載の画像の輪郭抽出方法において、
前記(a)ないし(d)工程に先立って行う工程として、
(h) 前記画像を構成する全ての画素についての画素情報を記録する記録領域を確保する工程と、
(i) 前記画像を構成する全ての画素を検索し、濃度値ごとの画素数をカウントする工程と、
(j) 前記カウントの結果に基づいて、各濃度値ごとに当該濃度値未満の累積画素数を求める工程と、
(k) 前記画像を構成する画素を１画素ずつ抽出する工程と、
(l) 前記(k)工程において抽出された画素の濃度値を検出し、当該濃度値に対応する前記累積画素数を取得し、当該累積画素数の値に対応する前記記録領域の位置に前記抽出された画素を特定する前記画素情報を記録するとともに、当該累積画素数の値を更新する工程と、
を有し、
前記(k)から(l)工程を前記画像を構成する全ての画素について行うまで繰り返し行うことを特徴とする画像の輪郭抽出方法。
【請求項５】
画像の輪郭を抽出する装置であって、
(a) 前記画像において濃度値の最大値を示す画素から降順に１画素ずつ注目画素を抽出する注目画素抽出手段と、
(b) 前記注目画素の周囲の複数の輪郭辺が既成輪郭線に包含されていない場合には、前記複数の輪郭辺からなる輪郭線を新規輪郭線とし、当該新規輪郭線の接続状態を示す輪郭線接続情報を生成するとともに、前記注目画素の前記複数の輪郭辺のうちのいずれか１つを選択した当該新規輪郭線の開始辺と、前記注目画素の濃度値を当該新規輪郭線の有効濃度範囲の開始濃度とした開始濃度値とを含む輪郭線管理情報を生成する輪郭線情報生成手段と、
(c) 前記輪郭線接続情報と前記輪郭線管理情報とを記憶する記憶手段と、
(d) 前記注目画素の前記複数の輪郭辺のうちのいずれかが既成輪郭線に包含されている場合には、当該既成輪郭線について前記記憶手段に記憶されている前記輪郭線接続情報を更新するとともに、当該更新によって前記注目画素のいずれかの前記輪郭辺が包含されていた少なくとも１つの既成輪郭線が消滅する場合、又は抽出すべき注目画素が無くなった場合には、前記既成輪郭線についての前記記憶手段に記憶されている前記輪郭線管理情報に対して前記注目画素の濃度値を前記既成輪郭線の有効濃度範囲の終了濃度を示す終了濃度値として追加更新する更新手段と、
を備えることを特徴とする画像の輪郭抽出装置。
【請求項６】
コンピュータによって画像の輪郭を抽出するためのプログラムを記録した記録媒体であって、
コンピュータに、
(a) 前記画像において濃度値の最大値を示す画素から降順に１画素ずつ注目画素を抽出する手順、
(b) 前記注目画素の周囲の複数の輪郭辺が既成輪郭線に包含されていない場合には、前記複数の輪郭辺からなる輪郭線を新規輪郭線として設定し、当該新規輪郭線の接続状態を示す輪郭線接続情報を生成するとともに、前記注目画素の前記複数の輪郭辺のうちのいずれか１つを選択した当該新規輪郭線の開始辺と、前記注目画素の濃度値を当該新規輪郭線の有効濃度範囲の開始濃度とした開始濃度値とを含む輪郭線管理情報を生成する手順、
(c) 前記注目画素の前記複数の輪郭辺のうちのいずれかが既成輪郭線に包含されている場合には、当該既成輪郭線についての前記輪郭線接続情報を更新する手順、
(d) 前記更新によって前記注目画素のいずれかの前記輪郭辺が包含されていた少なくとも１つの既成輪郭線が消滅する場合、又は抽出すべき注目画素が無くなった場合には、前記既成輪郭線についての前記輪郭線管理情報に対して前記注目画素の濃度値を前記既成輪郭線の有効濃度範囲の終了濃度を示す終了濃度値として追加する手順、
を実行させるための画像の輪郭抽出プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、画像の輪郭抽出方法およびその装置並びにコンピュータによって画像の輪郭を抽出するためのプログラムを記録した記録媒体に関する。
【０００２】
【従来の技術】
コンピュータで画像を処理する際に、画像の輪郭を抽出することがある。抽出した画像の輪郭は、輪郭内の画像に回転、拡大、縮小などの変換処理を施したり、輪郭内の画像を所望の色で塗りつぶしたり、輪郭内の画像を他の画像と合成したり下降したりする処理に利用される。
【０００３】
ここで、画像の輪郭を抽出する方法としては、特開平５−２４２２４６号公報に開示された方法がある。この方法では、画像を主走査方向に沿った１ラインごとに走査していき、各走査において主走査方向に沿った輪郭線を抽出していくように構成されている。そして、主走査方向に検出された２本の輪郭線の端点が一致すれば、それらを副走査方向に連結して１本の輪郭線を形成していく。このような処理を全画像についての各ラインごとに行うことによって所望の輪郭を抽出する。
【０００４】
【発明が解決しようとする課題】
ところが、上記のような従来の画像の輪郭抽出方法では、異なる濃度値についての輪郭線をいくつか抽出する際に、全画像領域を１ラインごとに走査していき１本の輪郭線を抽出する処理を各濃度値について行わなければならず、輪郭抽出に要する時間が長いという問題があった。
【０００５】
この発明は、上記課題に鑑みてなされたものであって、任意の濃度値についての輪郭抽出の処理を効率的に行い、処理時間を短縮する画像の輪郭抽出方法、装置、およびそのプログラムを記録した記録媒体を提供することを目的とする。
【０００６】
【課題を解決するための手段】
上記目的を達成するために、請求項１に記載の発明は、画像の輪郭を抽出する方法であって、(a) 前記画像において濃度値の最大値を示す画素から降順に１画素ずつ注目画素を抽出する工程と、(b) 前記注目画素の周囲の複数の輪郭辺が既成輪郭線に包含されていない場合には、前記複数の輪郭辺からなる輪郭線を新規輪郭線として設定し、当該新規輪郭線の接続状態を示す輪郭線接続情報を生成するとともに、前記注目画素の前記複数の輪郭辺のうちのいずれか１つを選択した当該新規輪郭線の開始辺と、前記注目画素の濃度値を当該新規輪郭線の有効濃度範囲の開始濃度とした開始濃度値とを含む輪郭線管理情報を生成する工程と、(c) 前記注目画素の前記複数の輪郭辺のうちのいずれかが既成輪郭線に包含されている場合には、当該既成輪郭線についての前記輪郭線接続情報を更新する工程と、(d) 前記更新によって前記注目画素のいずれかの前記輪郭辺が包含されていた少なくとも１つの既成輪郭線が消滅する場合には、消滅する前記既成輪郭線についての前記輪郭線管理情報に対して前記注目画素の濃度値を前記既成輪郭線の有効濃度範囲の終了濃度を示す終了濃度値として追加する工程とを有している。
【０００７】
請求項２に記載の発明は、請求項１に記載の画像の輪郭抽出方法において、前記画像における同一の濃度値を示す画素を前記注目画素として、前記(a)ないし(d)工程を繰り返し行うことによって生成／更新された前記輪郭線接続情報を出力することを特徴としている。
【０００８】
請求項３に記載の発明は、請求項１に記載の画像の輪郭抽出方法において、(e) 前記(a)ないし(d)工程を繰り返し行うことによって生成された前記輪郭線管理情報を記憶する工程と、所定の濃度値の輪郭線を抽出する際に、(f) 前記輪郭線管理情報に含まれる前記開始濃度値と前記終了濃度値とによって示される前記有効濃度範囲に基づいて前記所定の濃度値の輪郭線を特定し、当該輪郭線についての前記輪郭線管理情報から前記開始辺を取得する工程と、(g) 前記開始辺から所定の規則に従って輪郭辺を順次抽出していく工程とを有することを特徴としている。
【０００９】
請求項４に記載の発明は、請求項１ないし請求項３のいずれかに記載の画像の輪郭抽出方法において、前記(a)ないし(d)工程に先立って行う工程として、(h) 前記画像を構成する全ての画素についての画素情報を記録する記録領域を確保する工程と、(i) 前記画像を構成する全ての画素を検索し、濃度値ごとの画素数をカウントする工程と、(j) 前記カウントの結果に基づいて、各濃度値ごとに当該濃度値未満の累積画素数を求める工程と、(k) 前記画像を構成する画素を１画素ずつ抽出する工程と、(l) 前記(k)工程において抽出された画素の濃度値を検出し、当該濃度値に対応する前記累積画素数を取得し、当該累積画素数の値に対応する前記記録領域の位置に前記抽出された画素を特定する前記画素情報を記録するとともに、当該累積画素数の値を更新する工程とを有し、前記(k)から(l)工程を前記画像を構成する全ての画素について行うまで繰り返し行うことを特徴としている。
【００１０】
請求項５に記載の発明は、画像の輪郭を抽出する装置であって、(a) 前記画像において濃度値の最大値を示す画素から降順に１画素ずつ注目画素を抽出する注目画素抽出手段と、(b) 前記注目画素の周囲の複数の輪郭辺が既成輪郭線に包含されていない場合には、前記複数の輪郭辺からなる輪郭線を新規輪郭線とし、当該新規輪郭線の接続状態を示す輪郭線接続情報を生成するとともに、前記注目画素の前記複数の輪郭辺のうちのいずれか１つを選択した当該新規輪郭線の開始辺と、前記注目画素の濃度値を当該新規輪郭線の有効濃度範囲の開始濃度とした開始濃度値とを含む輪郭線管理情報を生成する輪郭線情報生成手段と、(c) 前記輪郭線接続情報と前記輪郭線管理情報とを記憶する記憶手段と、(d) 前記注目画素の前記複数の輪郭辺のうちのいずれかが既成輪郭線に包含されている場合には、当該既成輪郭線について前記記憶手段に記憶されている前記輪郭線接続情報を更新するとともに、当該更新によって前記注目画素のいずれかの前記輪郭辺が包含されていた少なくとも１つの既成輪郭線が消滅する場合には、消滅する前記既成輪郭線についての前記記憶手段に記憶されている前記輪郭線管理情報に対して前記注目画素の濃度値を前記既成輪郭線の有効濃度範囲の終了濃度を示す終了濃度値として追加更新する更新手段とを備えている。
【００１１】
請求項６に記載の発明は、コンピュータによって画像の輪郭を抽出するためのプログラムを記録した記録媒体であって、コンピュータに、(a) 前記画像において濃度値の最大値を示す画素から降順に１画素ずつ注目画素を抽出する手順、(b) 前記注目画素の周囲の複数の輪郭辺が既成輪郭線に包含されていない場合には、前記複数の輪郭辺からなる輪郭線を新規輪郭線として設定し、当該新規輪郭線の接続状態を示す輪郭線接続情報を生成するとともに、前記注目画素の前記複数の輪郭辺のうちのいずれか１つを選択した当該新規輪郭線の開始辺と、前記注目画素の濃度値を当該新規輪郭線の有効濃度範囲の開始濃度とした開始濃度値とを含む輪郭線管理情報を生成する手順、(c) 前記注目画素の前記複数の輪郭辺のうちのいずれかが既成輪郭線に包含されている場合には、当該既成輪郭線についての前記輪郭線接続情報を更新する手順、(d) 前記更新によって前記注目画素のいずれかの前記輪郭辺が包含されていた少なくとも１つの既成輪郭線が消滅する場合には、消滅する前記既成輪郭線についての前記輪郭線管理情報に対して前記注目画素の濃度値を前記既成輪郭線の有効濃度範囲の終了濃度を示す終了濃度値として追加する手順を実行させるための画像の輪郭抽出プログラムが記録されている。
【００１２】
【発明の実施の形態】
＜１．発明の概要＞
上述した従来の画像の輪郭抽出方法は、主走査方向と副走査方向とからなる画像平面において主走査方向に沿った１ラインごとの輪郭抽出処理を副走査方向に走査するものであった。
【００１３】
これに対して、この発明における画像の輪郭抽出方法は、画像を構成する画素のうち最大の濃度値を示すものから順次に１画素ずつ抽出し、新規に輪郭線を生成したり、既成の輪郭線を更新したりするものである。
【００１４】
ここで、１つの画素とその隣接する画素との境界となる線を輪郭辺と呼ぶことにすると、一般に１つの画素は４つの輪郭辺を有している。
【００１５】
そこで、最大の濃度値から順次抽出された画素（以下、「注目画素」という。）の４つの輪郭辺のうちのいずれもかが既に生成された既成輪郭線に含まれているか否かを判定し、いずれの輪郭辺も既成輪郭線に含まれていない場合には注目画素の４つの輪郭辺からなる輪郭線を新たに生成する一方、いずれかの輪郭辺が既成輪郭線に含まれている場合にはその輪郭内に当該注目画素が含まれるように既成輪郭線を更新する。
【００１６】
図１は、このような輪郭線の生成／更新の概念を示す図である。図１では、２×２の４画素ＰＡ〜ＰＤを例示しており、画素ＰＡの濃度値はＬＶ４であり、画素ＰＢの濃度値はＬＶ３であり、画素ＰＣの濃度値はＬＶ２であり、画素ＰＤの濃度値はＬＶ１である。ここで、各濃度値の関係は、ＬＶ１＜ＬＶ２＜ＬＶ３＜ＬＶ４である。まず、最大の濃度値であるＬＶ４を抽出すると画素ＰＡが抽出される。そして、図１（ａ）に示すように画素ＰＡの４つの輪郭辺が新規輪郭線Ｅａとして生成される。次に、図１（ｂ）に示すように濃度値ＬＶ３の画素ＰＢが抽出される。画素ＰＢの４つの輪郭辺のうち画素ＰＡに接する輪郭辺は既に輪郭線Ｅａに含まれているので、輪郭線Ｅａを更新して輪郭線Ｅｂを生成する。次に、図１（ｃ）に示すように濃度値ＬＶ２の画素ＰＣが抽出される。画素ＰＣの４つの輪郭辺のうち画素ＰＡに接する輪郭辺は既に輪郭線Ｅｂに含まれているので、輪郭線Ｅｂを更新して輪郭線Ｅｃを生成する。最後に、図１（ｄ）に示すように濃度値ＬＶ１の画素ＰＤが抽出される。画素ＰＤの４つの輪郭辺のうち画素ＰＢとＰＣとに接する２つの輪郭辺は既に輪郭線Ｅｃに含まれているので、輪郭線Ｅｃを更新して輪郭線Ｅｄを生成する。
【００１７】
この処理過程においては、４つの画素ＰＡ〜ＰＤを１画素ずつ処理する間に、濃度値ごとに存在する全ての輪郭線Ｅａ〜Ｅｄが抽出されている。従って、各濃度値ごとの輪郭線が抽出された際にその輪郭線を出力するようにすれば、全画像領域についての画素ごとの処理を１回だけ行えば全ての濃度値についての輪郭線を得ることができる。
【００１８】
また、このような処理過程において新規輪郭線が生成される際には、その輪郭線を後に追跡することができるように、新規輪郭線を構成する輪郭辺のうちから１つの輪郭辺を開始辺として設定しておく。このため、上記の処理が進むにつれて輪郭線が更新されたとしても、開始辺より所定のルール（規則）に基づいて輪郭を追跡することにより所定の濃度値の輪郭線を容易に抽出することができる。
【００１９】
以下、このような処理を実現するための詳細な構成について説明する。
【００２０】
＜２．装置の構成＞
図２は、この発明の一実施例としての画像の輪郭抽出装置１００の構成を示すブロック図である。図２に示すように、この輪郭抽出装置１００は、前処理部１０と注目画素抽出部２０と輪郭辺判定部３０と輪郭線形成部４０とメモリ５０と輪郭抽出部６０と記憶部７０とを備えている。
【００２１】
記憶部７０は画像をデータとして保存しておくためのものであり、前処理部１０は記憶部７０から画像を読み出し、その画像に対して前処理を施す部分である。なお、前処理では、枠付き画像の生成と輪郭辺番号の割付と濃度値に基づく画素のソーティングとが行われるがこれらの処理の詳細については後述する。
【００２２】
注目画素抽出部２０は、画像を構成する複数の画素のうちから濃度値の最も高い画素から順に注目画素を１画素ずつ順次抽出する。
【００２３】
そして、輪郭辺判定部３０においては、注目画素の４つの輪郭辺のうちのいずれかが既に生成されている輪郭線に含まれているか否かを判定し、その結果を輪郭線形成部４０に伝える。輪郭辺の判定にあたっては、メモリ５０に格納されている輪郭線接続情報ＤＣを参照する。輪郭線は複数の輪郭辺が連続的に接続されたものであり、輪郭線接続情報ＤＣには輪郭線を形成する複数の輪郭辺の接続状態が既述されているため、この輪郭線接続情報ＤＣを参照することにより注目画素の４つの輪郭辺のうちのいずれかが既に生成されている輪郭線に含まれているか否かを判定することができる。
【００２４】
図３は、輪郭線接続情報ＤＣを説明する図である。例えば、図３（ａ）に示すように画素ＰＡが注目画素として抽出された場合であって画素ＰＡの周囲にある４つの輪郭辺ａ，ｂ，ｃ，ｄによって新規輪郭線が形成されたとき、輪郭線接続情報ＤＣは図３（ｂ）に示すような状態に記述される。図３（ｂ）の輪郭線接続情報ＤＣより、輪郭辺ａは輪郭辺ｂに、輪郭辺ｂは輪郭辺ｃに、輪郭辺ｃは輪郭辺ｄに、輪郭辺ｄは輪郭辺ａにそれぞれ接続していることが判る。そして、これら輪郭辺ａ，ｂ，ｃ，ｄによって形成される輪郭線の輪郭線番号は「１」である。
【００２５】
そして、図３（ａ）に示す画素ＰＢが注目画素として抽出されたとき、図３（ｂ）の輪郭線接続情報ＤＣを参照すれば画素ＰＢの周囲にある４つの輪郭辺ｂ，ｅ，ｆ，ｇのうち輪郭辺ｂは既に輪郭線番号「１」の輪郭線に含まれていることが判る。従って、輪郭線接続情報ＤＣを参照すれば注目画素の各輪郭辺の使用状態を判定することができる。なお、１つの輪郭辺が同時に複数の輪郭線に含まれるということはあり得ない。
【００２６】
輪郭線形成部４０は輪郭線情報生成部４０ａと輪郭線情報更新部４０ｂとを備えており、輪郭辺判定部３０において注目画素の４つの輪郭辺のうちのいずれもが既に生成されている輪郭線に含まれていないと判定されたときは、輪郭線情報生成部４０ａが動作して新規輪郭線の生成処理を行う一方、注目画素の４つの輪郭辺のうちのいずれかが既に生成されている輪郭線に含まれていると判定されたときは、輪郭線情報更新部４０ｂが動作して既成輪郭線の更新処理を行う。この更新処理には、後述するように輪郭線の分離と統合と消滅との処理がある。
【００２７】
輪郭線情報生成部４０ａは、新規輪郭線を生成すると、その輪郭線の接続状態を輪郭線接続情報ＤＣに記述するとともに、輪郭線管理情報ＤＭを生成し、メモリ５０に格納する。
【００２８】
輪郭線情報更新部４０ｂは、既成輪郭線を更新した際に、輪郭線接続情報ＤＣに記述されている輪郭線の接続状態を更新する。
【００２９】
また、輪郭線情報更新部４０ｂは、更新によって既成輪郭線の少なくとも１つが消滅したときに、その消滅した輪郭線についての輪郭線管理情報ＤＭの終了濃度値の欄に現在の注目画素の濃度値より１つ高い濃度値を格納する。ここで、更新によって既成輪郭線の少なくとも１つが消滅する場合は、輪郭線管理情報ＤＭに登録されている開始辺が注目画素を追加したことにより有効でなくなってしまう場合と２以上の輪郭線の統合によって１つの輪郭線のみが残り、他の輪郭線が消滅する場合とを含んでいる。また、さらに、輪郭線情報更新部４０ｂは、次に抽出すべき注目画素が無くなったときには、輪郭線管理情報ＤＭにおいて終了濃度値が未だ格納されていないものについて終了濃度値として「０」を格納する。なお、このように終了濃度値を格納する処理を終了処理という。
【００３０】
上述の輪郭線接続情報ＤＣは輪郭線そのものであるので、輪郭線情報生成部４０ａと輪郭線情報更新部４０ｂとにおいて輪郭線接続情報ＤＣに新規接続状態を記述した際又は輪郭線接続情報ＤＣを更新した際にその輪郭線接続情報ＤＣを出力すれば、輪郭線出力となる。
【００３１】
例えば、画像の濃度値が０〜２５５の２５６階調である場合であって濃度値が１２６の輪郭線を抽出したい場合は、濃度値２５５の画素から順次注目画素を抽出していき、それぞれの濃度値についての輪郭線を形成させていく。そして濃度値が１２６である画素の全てについての処理が終了すると、輪郭線接続情報ＤＣに所望の輪郭線が形成されたこととなるため、それを出力すればよい。そして、この場合は、濃度値が１２５以下である画素の抽出処理は行わなくてもよいので効率的な輪郭抽出となっている。
【００３２】
しかしながら、この実施の形態では、一度全画像について１画素ごとの輪郭線形成を行っておけば、再度輪郭線を抽出しようとする際には全画像について１画素ごとの輪郭線形成を行う必要がないようにするために、輪郭線管理情報ＤＭをメモリ５０に格納する。
【００３３】
ここで、輪郭線管理情報ＤＭについて説明する。図４は、輪郭線管理情報ＤＭを説明する図である。なお、図４（ａ）に示す各画素内の数字は各画素の濃度値を示している。
【００３４】
例えば、図４（ａ）に示すように画素ＰＡが注目画素として抽出された場合であって画素ＰＡの周囲にある４つの輪郭辺ａ，ｂ，ｃ，ｄによって新規輪郭線が形成されたとき、輪郭線管理情報ＤＭは図４（ｂ）に示すような状態に記述される。輪郭線管理情報ＤＭの輪郭線番号には、既存の輪郭線番号と重複しない番号が付与される。また、開始辺番号には、新規に生成された輪郭線を後に抽出する際に抽出開始点となる輪郭辺（すなわち、開始辺）の番号が格納される。
【００３５】
開始辺としては、注目画素に隣接する画素のうち最小の濃度値を示す画素と共有している輪郭辺、若しくは、注目画素に隣接する画素のうち注目画素の濃度値と最も差の大きい濃度値を有する画素と共有している輪郭辺を選択することが好ましい。この理由は、開始辺の有効となる有効濃度範囲を最も大きくすることができるからである。従って、図４（ａ）のような濃度値の場合、開始辺として輪郭辺ａが決定される。
【００３６】
開始濃度値には、注目画素ＰＡの濃度値「９」が格納される。また、終了濃度値には、輪郭線番号「１」の輪郭線が更新されて消滅するとき、すなわち開始辺が無効となるときの注目画素の濃度値よりも１つ高い濃度値が格納される。
【００３７】
輪郭辺の数には、輪郭線番号「１」の輪郭線を構成する輪郭辺の数が格納される。図４（ａ）の例の場合であると、輪郭線は４つの輪郭辺ａ，ｂ，ｃ，ｄによって構成されているので、輪郭辺の数は「４」となっている。
【００３８】
このような輪郭線管理情報ＤＭをメモリ５０に保持しておくことにより、後に任意の濃度値の輪郭線を抽出する場合は、輪郭抽出部６０が輪郭線管理情報ＤＭの開始濃度値と終了濃度値とによって輪郭線の開始辺が有効な有効濃度範囲を知ることができ、輪郭線抽出の対象となる濃度値が有効濃度範囲内に存在する開始辺を全て取得することができる。そして輪郭抽出部６０が、それらの開始辺から所定のルールに基づいて輪郭抽出を行っていけば適切に画像の輪郭抽出を行うことができる。
【００３９】
すなわち、図２の装置において、メモリ５０内に輪郭線管理情報ＤＭが未だ格納されていないときは、前処理部１０と注目画素抽出部２０と輪郭辺判定部３０と輪郭線形成部４０とが機能して、各濃度値ごとの輪郭線を形成していくに伴って輪郭線管理情報ＤＭと輪郭線接続情報ＤＣとをメモリ５０に逐次格納していくように構成されている。また、輪郭線形成部４０は輪郭線接続情報ＤＣを生成／更新する際にそれを出力すれば輪郭線出力を行うことができる。
【００４０】
一方、メモリ５０内に輪郭線管理情報ＤＭが既に格納されているときは、輪郭抽出部６０が機能して、メモリ５０内の輪郭線管理情報ＤＭを読み出して輪郭線ごとに登録されている開始辺より所定のルールに基づいて輪郭抽出を行うように構成されており、輪郭抽出部６０が抽出した輪郭線を出力する。
【００４１】
＜３．前処理＞
前処理部１０において行われる前処理について説明する。
【００４２】
まず、第１の前処理として枠付き画像の生成が行われる。図５は、枠付き画像の生成を説明する図である。図５（ａ）は輪郭抽出の対象となる原画像を示しており、図５（ｂ）は枠付き画像を生成する際の中間段階を示しており、図５（ｃ）は原画像に対して生成される枠付き画像を示している。図５においては、原画像は、５×４の２０画素によって構成される例を示しており、各画素内の数字はその画素の濃度値を示している。なお、以下においては、図５（ａ）に示すような原画像についての処理を一例として説明することとする。
【００４３】
前処理部１０は、図５（ａ）の原画像に対してその周囲を１画素分だけ広げた画像領域を確保する（図５（ｂ））。その結果、原画像の周囲に分布することとなる全ての画素に対して濃度値０を格納する。このようにして図５（ｃ）に示すように７×６の４２画素からなる枠付き画像を生成する。
【００４４】
このような枠付き画像を生成する理由は、原画像の全ての輪郭辺について同一の処理を施すことができるようにし、処理効率を向上させるためである。図５（ａ）に示す原画像の外周部に位置する各輪郭辺は、他の画素と接していないため、濃度値比較を行うことができない。従って、原画像に含まれる全ての輪郭辺について濃度値比較を行うことができるようにするために枠付き画像を生成する。なお、図５（ａ）に示す原画像の外周部に位置する各輪郭辺については他の輪郭辺とは異なる例外処理を行うようにする場合、枠付き画像を生成することは不要である。
【００４５】
次に、第２の前処理として枠付き画像の含まれる各輪郭辺に対して輪郭辺番号の割付処理が行われる。図６は、輪郭辺番号の割付を説明する図である。枠付き画像において主走査方向Ｘにｎ個の画素が存在するとすると、１ライン目の左端の画素の下辺には０番を付与し、右辺には１番を付与する。そして、１ライン目の２番目の画素の下辺、右辺、３番目の画素の下辺、右辺というように順次番号を付与していく。主走査方向Ｘにはｎ個の画素が存在するため、２ライン目の左端の画素の下辺には（２ｎ）番を付与することとなり、右辺には（２ｎ＋１）番を付与することとなる。以下同様に、そして、２ライン目の２番目の画素の下辺、右辺、３番目の画素の下辺、右辺というように順次番号を付与していき、全てのラインについて輪郭辺番号を付与する。
【００４６】
このようにして図５（ｃ）のような７×６の枠付き画像について輪郭辺番号を割り付けると図７のようになる。なお、図７において太線は原画像部分を示している。従って、この輪郭辺番号の割付によって、原画像の輪郭抽出に必要な全ての輪郭辺に固有の番号が付与されたこととなる。ここで、図７に示すように枠付き画像の上端に位置する各輪郭辺と、左端に位置する各輪郭辺とには輪郭辺番号は割り付けられないがこれらの輪郭辺が原画像の輪郭となることはあり得ないので問題ない。
【００４７】
また、原画像に対してのみ輪郭辺番号の割付を行う場合は、原画像の上端および左端に位置する輪郭辺に対して輪郭辺番号を付与するために例外処理を行わなければならないので時間がかかるが、上記のように枠付き画像に対して輪郭辺番号の割付を行う場合は、例外処理を行わずとも原画像に含まれる全ての輪郭辺に対して番号が付与されるため、効率的に輪郭辺番号を付与することができ、処理時間を短縮することができる。
【００４８】
次に、第３の前処理として原画像を構成する画素を濃度値に基づいてソートする処理が行われる。濃度値に基づいたソートを行うのは、注目画素抽出部２０が濃度値の高い画素から順次注目画素を抽出することができるようにするためである。従って、原画像を構成する画素のうちから濃度値の高い順に１つの画素を抽出することができるようにソートすることができる手法であればよいため、公知となっている種々のソート方法を適用することができる。
【００４９】
しかしながら、公知となっている種々のソート方法は、判断処理やデータの入れ替え処理が多用されるためソートに時間がかかる。
【００５０】
そこで、この実施の形態では、効率的にソートを行うために以下に示すようなソート方法を適用することが好ましい。
【００５１】
まず、ソート処理を行うに先立って、枠付き画像の各画素に対して座標値を設定する。一般に画像平面内の各画素に座標値を設定する場合は、主走査方向Ｘの位置と副走査方向Ｙの位置とによって現すＸＹ座標系が使用されるが、この場合はＸ座標とＹ座標との２つの値を管理しなければならない。そこで、この実施の形態では、枠付き画像が主走査方向Ｘにｎ個の画素を有するとすると、「（Ｙ座標）×（ｎ個）＋（Ｘ座標）」によって導かれる１つの値を座標値とする。すなわち、枠付き画像の主走査方向Ｘに沿って順次１つの番号を付与していくことにより各画素に対して座標値を設定する。このようにして図５（ｃ）に示す枠付き画像について座標値を設定すると、各画素の座標値は図８に示すようになる。なお、図８において各画素の数字は座標値であり、濃度値の表示は省略している。また、図８における太線は原画像部分を示している。
【００５２】
次に、実際のソート処理に移る。はじめに、原画像に含まれる全ての画素を検索し、濃度値ごとの画素数をカウントする。図５に示す原画像について濃度値ごとの画素数をカウントすると、図９に示すようなカウント結果が得られる。このカウント結果を前処理部１０は内部に設けられている図示しないメモリなどに一時的に格納する。
【００５３】
そして、図９に示すカウント結果に基づいて、各濃度値ごとに、当該濃度値未満の濃度値を示す累積画素数を導く。例えば、図９のカウント結果より、濃度値１の累積画素数は濃度値０の画素数であるため０個となり、濃度値２の累積画素数は濃度値０〜１の画素数の和であるため２個となり、濃度値３の累積画素数は濃度値０〜２の画素数の和であるため５個となる。このようにして各濃度値について累積画素数を求ると、図１０のようになる。
【００５４】
そして、次に、ソートデータを格納するバッファ領域を原画像を構成する画素数分だけ確保する。図５に示す原画像の場合は２０個の画素を有するので、２０個分のバッファ領域を確保する。そして、原画像を構成する画素のうちから座標値順に１画素抽出し、その濃度値を検出する。
【００５５】
図５の原画像の場合、図１１に示すように濃度値２の画素が最初に抽出される。この抽出した画素の濃度値２に対応する累積画素数は２であるため、バッファ領域の２に対応する格納位置、すなわちメモリアドレス２の位置に抽出した画素の座標値を格納する。図１１の場合、抽出した濃度値２の画素の座標値は８であるため（図８参照）、メモリアドレス２の位置に座標値８が格納される。そして、バッファ領域に座標値を格納すると、濃度値２の累積画素数２に対して１を加算することにより、濃度値２の累積画素数を３に変更する。
【００５６】
次に、図１２に示すように濃度値９の画素が抽出される。この抽出した画素の濃度値９に対応する累積画素数は１９であるため、バッファ領域の１９に対応する格納位置、すなわちメモリアドレス１９の位置に抽出した画素の座標値を格納する。図１２の場合、抽出した濃度値９の画素の座標値は９であるため（図８参照）、メモリアドレス１９の位置に座標値９が格納される。そして、バッファ領域に座標値を格納すると、濃度値９の累積画素数１９に対して１を加算することにより、濃度値９の累積画素数を２０に変更する。
【００５７】
以下、原画像を構成する画素のうちから座標値順に１画素する毎に同様の処理を繰り返し行う。そして、原画像を構成する全ての画素についての処理が終了すると、各濃度値ごとの累積画素数とバッファ領域とは、図１３に示すような状態となる。
【００５８】
図１３（ｂ）に示すバッファ領域には、メモリアドレスの小さい方から順に、濃度値の小さい画素の座標値が格納されている。例えば、メモリアドレス０，１には濃度値１の画素の座標値が格納されており、メモリアドレス２〜４には濃度値２の画素の座標値が格納されている。従って、上記のような処理を行うことにより、バッファ領域内に原画像を構成する画素を濃度値に基づいてソートされた結果が格納されていることとなる。
【００５９】
上記のようなソート方法を適用すると、２つの画素の濃度値を比較する判断処理やデータの入れ替え処理を行うことなくソートすることができるのでソートに要する時間を短縮することができる。
【００６０】
このようにバッファ領域内に濃度値に基づいたソート結果を格納しておくと注目画素抽出部２０が濃度値の高い画素から順次注目画素を抽出する際には、バッファ領域の最大のメモリアドレスの位置から順次座標値を取得してその座標値の画素を抽出していけばよく、効率的な処理ができる。
【００６１】
＜４．輪郭線管理情報などの生成と更新＞
次に、注目画素抽出部２０が濃度値の高い画素から順次注目画素を抽出していき、輪郭線管理情報と輪郭線接続情報とを生成したり、更新したりする処理について説明する。
【００６２】
注目画素抽出部２０は、図１３（ｂ）のようなソート結果に基づいて濃度値の高い画素から順次注目画素を抽出する。そして、注目画素の周囲にある４つの輪郭辺の輪郭辺番号を求める。図１３（ｂ）に示すように、ソート結果には画素の座標値が格納されているため、この座標値より注目画素の４つの輪郭辺の番号を求める。例えば、注目画素の座標値をＰとし、枠付き画像の主走査方向Ｘにｎ個の画素が存在するとし、注目画素の上側、右側、下側、左側にあるそれぞれの輪郭辺番号をＮＵ、ＮＲ、ＮＤ、ＮＬとすると、
上側の輪郭辺番号：ＮＵ＝（Ｐ−ｎ）×２
右側の輪郭辺番号：ＮＲ＝（Ｐ×２）＋１
下側の輪郭辺番号：ＮＤ＝（Ｐ×２）
左側の輪郭辺番号：ＮＬ＝（Ｐ×２）−１
で求めることができる。そして、注目画素抽出部２０は、注目画素についての４つの輪郭辺番号を輪郭辺判定部３０に送る。
【００６３】
輪郭辺判定部３０は、メモり５０内の輪郭線接続情報ＤＣを参照し、注目画素の輪郭辺番号が既に生成されている輪郭線に含まれているか否かを判定する。
【００６４】
そして、メモリ５０内に輪郭線接続情報ＤＣが未だ格納されていない場合、又は輪郭線接続情報ＤＣを参照した結果、注目画素の４つの輪郭辺のいずれもが既成輪郭線に含まれていないと判定した場合は、輪郭線情報生成部４０ａに注目画素の４つの輪郭辺からなる輪郭線を生成するように指令する。これにより、輪郭線情報生成部４０ａは、注目画素の周囲にある４つの輪郭辺からなる新規輪郭線を生成し、メモリ５０の輪郭線接続情報ＤＣにその新規輪郭線の接続状態を記述するとともに、新規輪郭線の開始辺などを求めて輪郭線管理情報ＤＭに記述する。
【００６５】
一方、輪郭線接続情報ＤＣを参照した結果、注目画素の４つの輪郭辺のいずれかが既成輪郭線に含まれていると判定した場合は、輪郭線情報更新部４０ｂに輪郭線接続情報ＤＣと輪郭線管理情報ＤＭとを更新するよう指令する。
【００６６】
輪郭線情報更新部４０ｂが輪郭線接続情報ＤＣと輪郭線管理情報ＤＭとを更新する処理について説明する。図１４は、注目画素の４つの輪郭辺が１つの既成輪郭線に含まれている場合を示す図である。なお、図１４において斜線を施した画素は注目画素であり、細線は各輪郭辺であり、太線は輪郭線に含まれている輪郭辺を示している。図１４（ａ）に示すように注目画素の４つの輪郭辺ａ，ｂ，ｃ，ｄのうち、輪郭辺ｄは既成輪郭線Ｅ１に含まれている。このような状態で注目画素を追加すると、図１４（ｂ）の太線に示すように既成輪郭線Ｅ１が更新される。
【００６７】
図１５は、図１４（ａ）の輪郭線Ｅ１を図１４（ｂ）の輪郭線Ｅ１に更新する過程を示す図である。なお、図１５（ａ）〜（ｅ）において左図はメモリ５０に格納される輪郭線接続情報ＤＣであり、右図は注目画素の４つの輪郭辺から輪郭線が形成されると仮想した場合にメモリ５０に一時的に格納される注目画素の輪郭辺の仮想接続状態である。
【００６８】
まず、図１４（ａ）に示す注目画素が抽出されたときは、輪郭線Ｅ１の輪郭線接続情報ＤＣと仮想接続情報とは図１５（ａ）となる。すなわち、輪郭線Ｅ１の接続状態は「ｅ→ｄ→ｆ→ｇ」となっている。また、注目画素の４つの輪郭辺のつながりは、「ａ→ｂ→ｃ→ｄ→ａ」となっている。
【００６９】
そして、今回注目画素を追加することによって輪郭辺ｄは輪郭線Ｅ１に含まれないようになる。そのため、輪郭線接続情報ＤＣにおいて輪郭辺ｄを次の輪郭辺（接続先）としている輪郭辺ｅについての次の輪郭辺番号を更新することとなる。つまり、仮想接続状態を参照すると、輪郭辺ｄは輪郭辺ａに接続するため、輪郭辺ｅについての次の輪郭辺番号はａに書き換えられる。この結果、輪郭線Ｅ１の輪郭線接続情報ＤＣと仮想接続情報とは図１５（ｂ）となる。
【００７０】
また、今回注目画素を追加することによって輪郭辺ｄは輪郭線Ｅ１に含まれないようになるため、仮想接続情報において輪郭辺ｄを次の輪郭辺（接続先）としている輪郭辺ｃについての次の輪郭辺番号を更新することとなる。つまり、輪郭線接続情報ＤＣを参照すると、輪郭辺ｄは輪郭辺ｆに接続するため、輪郭辺ｃについての次の輪郭辺番号はｆに書き換えられる。この結果、輪郭線Ｅ１の輪郭線接続情報ＤＣと仮想接続情報とは図１５（ｃ）となる。
【００７１】
そして、今回注目画素を追加することによって輪郭辺ｄは輪郭線Ｅ１に含まれないようになるため、輪郭辺接続情報ＤＣから輪郭辺ｄについての接続状態を消去する。この結果、輪郭線Ｅ１の輪郭線接続情報ＤＣと仮想接続情報とは図１５（ｄ）となる。
【００７２】
そして、仮想接続情報うちから輪郭辺ｄを除く輪郭辺ａ，ｂ，ｃについての接続状態を輪郭線接続情報ＤＣに書き写すことにより、輪郭線Ｅ１の輪郭線接続情報ＤＣと仮想接続情報とは図１５（ｅ）のようになる。図１５（ｅ）の輪郭線接続情報ＤＣでは、図１４（ｂ）の太線に示すような輪郭線Ｅ１の接続状態が記述されていることとなる。従って、ここまでの処理が行われると、仮想接続情報はメモリ５０から消去されてもよい。
【００７３】
次に、注目画素の４つの輪郭辺が２以上の既成輪郭線に含まれている場合は、上記の処理とほぼ同様であるが、異なる部分もある。例えば、図１６は、注目画素の４つの輪郭辺が３つの既成輪郭線に含まれている場合を示す図である。なお、図１５において斜線を施した画素は注目画素であり、細線は各輪郭辺であり、太線は輪郭線に含まれている輪郭辺を示している。図１４（ａ）では、輪郭辺ｅ，ｄ，ｆ，ｇは輪郭線Ｅ１に含まれており、輪郭辺ｔ，ａ，ｓは輪郭線Ｅ２に含まれており、輪郭辺ｍ，ｃ，ｎは輪郭線Ｅ３に含まれている。また、輪郭線Ｅ１において各輪郭辺は「ｅ→ｄ→ｆ→ｇ」の順で接続されており、輪郭線Ｅ２において各輪郭辺は「ｔ→ａ→ｓ」の順で接続されており、輪郭線Ｅ３において各輪郭辺は「ｍ→ｃ→ｎ」の順で接続されている。このような状態で斜線で示した注目画素を追加すると、図１４（ｂ）の太線に示すように輪郭線Ｅ２，Ｅ３が輪郭線Ｅ１に統合されて消滅する。
【００７４】
輪郭線を統合する際に、輪郭線情報更新部４０ｂは各輪郭線Ｅ１，Ｅ２，Ｅ３の輪郭線管理情報ＤＭを参照し、各輪郭線を構成する輪郭辺の数を取得する（図４（ｂ）参照）。そして、最も輪郭辺の数が大きい輪郭線のみを残し、他の輪郭線は消滅させる。例えば、図１６（ａ）において最も輪郭辺の数が大きい輪郭線がＥ１であったとすると、輪郭線の更新の結果、図１６（ｂ）に示すように輪郭線Ｅ１のみが残り、他の輪郭線Ｅ２，Ｅ３については消滅している。
【００７５】
図１７は、図１６（ａ）の状態における輪郭線接続情報などを示している。なお、図１７（ａ）は輪郭線接続情報ＤＣであり、図１７（ｂ）は注目画素の４つの輪郭辺から輪郭線が形成されると仮想した場合にメモリ５０に一時的に格納される注目画素の輪郭辺の仮想接続状態であり、図１７（ｃ）は輪郭線管理情報ＤＭである。図１７（ｃ）において、開始辺番号と開始濃度値との欄には各輪郭線Ｅ１〜Ｅ３が生成された際にそれぞれ輪郭辺の番号と注目画素の濃度値とが格納されているが、ここでは便宜上これらの値を「−」で表示している。
【００７６】
図１６（ａ）において斜線で示した注目画素を追加することによって輪郭辺ａ，ｃ，ｄは輪郭線に含まれないこととなる。このため、図１７（ａ）の輪郭線接続情報ＤＣにおいて輪郭辺ａを次の輪郭辺（接続先）としている輪郭辺ｔについての次の輪郭辺番号を更新することとなる。つまり、図１７（ｂ）の仮想接続状態を参照すると、輪郭辺ａは輪郭辺ｂに接続するため、輪郭辺ｔについての次の輪郭辺番号はｂに書き換えられる。
【００７７】
次に、図１７（ｃ）より輪郭線Ｅ１の輪郭辺の数が最も大きいため、輪郭線Ｅ２，Ｅ３は消滅する。従って、図１７（ａ）の輪郭線接続情報ＤＣにおける所属輪郭線番号Ｅ２，Ｅ３は全てＥ１に書き換えられる。
【００７８】
次に、輪郭辺ａは輪郭線に含まれないこととなるため、図１７（ｂ）の仮想接続状態において輪郭辺ａを次の輪郭辺（接続先）としている輪郭辺ｄについての次の輪郭辺番号を更新することとなる。つまり、輪郭線接続情報ＤＣを参照すると、輪郭辺ａは輪郭辺ｓに接続するため、輪郭辺ｄについての次の輪郭辺番号はａからｓに書き換えられる。そして、輪郭辺ｄも輪郭線に含まれないこととなるため、図１７（ａ）の輪郭線接続情報ＤＣにおいて輪郭辺ｄを次の輪郭辺（接続先）としている輪郭辺ｅについての次の輪郭辺番号を更新することとなる。つまり、仮想接続状態を参照すると、先程、輪郭辺ｄは輪郭辺ｓに接続するようにかきえられているため、輪郭辺ｅについての次の輪郭辺番号はｄからｓに書き換えられる。
【００７９】
次に、輪郭辺ｃは輪郭線に含まれないこととなるため、図１７（ａ）の輪郭線接続情報ＤＣにおいて輪郭辺ｃを次の輪郭辺（接続先）としている輪郭辺ｍについての次の輪郭辺番号を更新することとなる。つまり、仮想接続状態を参照すると、輪郭辺ｃは輪郭辺ｄに接続するため、輪郭辺ｍについての次の輪郭辺番号はｃからｄに書き換えられる。しかし、輪郭辺ｄも輪郭線に含まれないこととなるため、輪郭線接続情報ＤＣにおいて輪郭辺ｄが接続する輪郭辺ｆを輪郭辺ｍについての次の輪郭辺番号とする。
【００８０】
次に、輪郭辺ｃは輪郭線に含まれないこととなるため、図１７（ｂ）の仮想接続状態において輪郭辺ｃを次の輪郭辺としている輪郭辺ｂについての次の輪郭辺番号を更新することとなる。つまり、輪郭線接続情報ＤＣを参照すると、輪郭辺ｃは輪郭辺ｎに接続するため、仮想接続状態の輪郭辺ｂについての次の輪郭辺番号はｃからｎに書き換えられる。
【００８１】
次に、輪郭辺ｄは輪郭線に含まれないこととなるため、図１７（ａ）の輪郭線接続情報ＤＣにおいて輪郭辺ｄを次の輪郭辺（接続先）としている輪郭辺ｅについての次の輪郭辺番号を仮想接続状態を参照してｄからｓに更新する。また、輪郭辺ｃは輪郭線に含まれないこととなるため、図１７（ａ）の輪郭線接続情報ＤＣにおいて輪郭辺ｃを次の輪郭辺としている輪郭辺ｍについての次の輪郭辺番号をｃからｆに更新する。なお、この処理は既に一度行われているが、ここでもう一度同様の処理を行うことにより、注目画素の４つの輪郭辺ａ，ｂ，ｃ，ｄの接続状態を書き換える処理がどの輪郭辺から開始されてても同様の結果が得られるようになっている。
【００８２】
そして次に、輪郭辺ａ，ｃ，ｄは輪郭線に含まれないこととなるため、図１７（ａ）の輪郭線接続情報ＤＣにおいて輪郭辺ａ，ｃ，ｄについての接続情報を消去する。そして、仮想接続状態の輪郭辺ｂのみについての接続状態を輪郭線接続情報ＤＣに書き込む。また、この処理により輪郭線Ｅ２，Ｅ３は消滅するため、輪郭線管理情報ＤＭにおいて輪郭線Ｅ２，Ｅ３についての終了濃度値の欄に注目画素の濃度値よりも１つ高い濃度値を書き込むとともに、これらの輪郭線についての輪郭辺の数を０にして、輪郭線Ｅ２，Ｅ３についての有効濃度範囲を確定させ、輪郭線Ｅ２，Ｅ３について終了処理を行う。また、輪郭線管理情報ＤＭにおいて輪郭線Ｅ１についての輪郭辺の数を更新する。なお、この処理が行われると、注目画素の仮想接続状態はメモリ５０から消去される。
【００８３】
このような処理の結果、メモリ５０に格納されている輪郭線接続情報ＤＣは図１８（ａ）に示すようになり、輪郭線管理情報ＤＭは図１８（ｂ）に示すようになる。すなわち、これらの情報は、図１６（ｂ）に示したような輪郭線Ｅ１が生成された状態を示している。上記のような処理の結果、輪郭線Ｅ１は輪郭辺１６個よりなる輪郭線に更新され、輪郭線Ｅ２，Ｅ３は終了処理が行われて消滅している。
【００８４】
次に、注目画素の４つの輪郭辺のうちの２以上の輪郭辺が同一の輪郭線に含まれている場合について説明する。まず、上記のような処理を行う前に、注目画素の４つの輪郭辺が所属している輪郭線番号を取得し、注目画素の４つの輪郭辺のうち同一の輪郭線に含まれている輪郭辺番号を取得する。そして、注目画素の輪郭辺のうち同一の輪郭線に含まれている輪郭辺の接続状態が連続しているか否かを判定する。同一の輪郭線に含まれている輪郭辺の接続状態が連続していれば、上記のような通常の処理を行えば輪郭線は適切に更新される。しかし、同一の輪郭線に含まれている輪郭辺の接続状態が連続していない場合は、輪郭線の内部にホールが形成されるため、そのホールについて新たに輪郭線が生成されることとなる。
【００８５】
例えば、図１９（ａ）〜（ｄ）の左図に示すような輪郭線が形成されているときに斜線で示した画素を注目画素として抽出すると、右図に示すような輪郭線が生成される。なお、図１９（ａ）〜（ｄ）において丸印は各輪郭線の開始辺を示している。上述したような輪郭線接続情報ＤＣの更新処理を行った結果、既成輪郭線の内側に新たに閉ループを形成するホール状の輪郭線が生成されている場合は、その輪郭線に対して開始辺と開始濃度値と輪郭線個数とを求めて輪郭線管理情報ＤＭに登録することが行われる。このような処理を行うことにより、輪郭線が分離して新たな輪郭線が生成された場合であっても適切に対応することができる。
【００８６】
次に、注目画素の４つの輪郭辺のうち既成輪郭線の開始辺として設定されている輪郭辺が存在する場合について説明する。まず、注目画素の４つの輪郭辺のうち既成輪郭線Ｅ１の開始辺として設定されている輪郭辺が存在すると判断すると、輪郭線管理情報ＤＭに新規輪郭線Ｅ２の情報を書き込む領域を確保し、その領域に既成輪郭線Ｅ１の内容をコピーする。そして輪郭線Ｅ２についての輪郭線管理情報ＤＭに対して注目画素の濃度値よりも１つ高い濃度値を終了濃度値に書き込み、輪郭辺の数を０にすることにより、輪郭線Ｅ２について終了処理を施す。そして、既成輪郭線Ｅ１についての輪郭線管理情報ＤＭの開始濃度値の欄に注目画素の濃度値を上書きするとともに、開始辺を注目画素の４つの輪郭辺以外の輪郭辺から抽出して上書きする。このような処理を行うことにより、注目画素の４つの輪郭辺のうち既成輪郭線の開始辺として設定されている輪郭辺が存在する場合であっても良好に輪郭線情報を更新することができる。
【００８７】
ただし、図２０の左図に示すように注目画素の４つの輪郭辺の全てが同一の既成輪郭線に含まれている場合は、注目画素の４つの輪郭辺のうち既成輪郭線の開始辺として設定されている輪郭辺が存在する場合であっても上記のような処理を行う必要がなく、単にその既成輪郭線について終了処理を施せばよい。これにより、図２０の右図に示すような適切な輪郭線に更新される。
【００８８】
以上の説明では、輪郭線情報更新部４０ｂが輪郭線接続情報ＤＣと輪郭線管理情報ＤＭとを更新する処理を概念的に示した。ここで、上記の処理内容をさらに判りやすくするために、図５に示した原画像と枠付き画像とに対して上記の処理を施した場合の処理過程をみていくこととする。図２１〜図３０は、各濃度値ごとの輪郭線を抽出していく際の輪郭線管理情報ＤＭと輪郭線接続情報ＤＣとを示す図である。なお、図２１〜図３０の（ａ）において、各画素の数字は原画像部分の画素ごとの濃度値を示しており、枠部分の濃度値０については濃度値を省略している。また、以下の説明においては、各画素の輪郭辺を参照するのに図７に示した輪郭辺番号を用い、各画素を参照するのに図８に示した座標値を用いることとする。
【００８９】
まず、注目画素抽出部２０は、図１３（ｂ）のようにソートされたバッファ領域から濃度値の最大の画素であるメモリアドレス１９の座標値９を取得する。図８の座標値を参照すると、図２１（ａ）のように濃度値９の画素が注目画素として抽出されたこととなる。図２１（ａ）に示すように注目画素の４つの輪郭辺は既成輪郭線に含まれていないため、注目画素の４つの輪郭辺からなる輪郭線を生成し、輪郭線管理情報ＤＭと輪郭線接続情報ＤＣにその情報が記述される。
【００９０】
輪郭線管理情報ＤＭにおいて、注目画素の４つの輪郭辺によって新規に生成された輪郭線は最初に生成された輪郭線であるため、輪郭線番号は１となる。また、注目画素の４つの輪郭辺を介して存在する隣接画素のうち座標値２（注目画素の上側）の画素の濃度値が０であるため注目画素の上側の輪郭辺が開始辺となる。この輪郭辺の輪郭辺番号は４であるため、開始辺番号には４が格納される。また、このときの注目画素の濃度値は９であるため開始濃度値には９が格納され、輪郭辺の数には４が格納される。
【００９１】
輪郭線接続情報ＤＣにおいては、注目画素の４つの輪郭辺によって形成される輪郭線の接続状態が記述され、各輪郭辺の所属輪郭線番号には１が格納される。
【００９２】
次に、注目画素抽出部２０は、図１３（ｂ）のバッファ領域のメモリアドレス１８，１７の座標値２２，１８を取得してこれらの画素を注目画素とし、濃度値８についての輪郭線形成を行うと、図２２に示すようになる。図２２（ａ）に示すように、濃度値８の２つの画素の各輪郭辺は既に生成された濃度値９の輪郭線に含まれていないため、それぞれの画素について新規輪郭線が形成される。そして、輪郭線管理情報ＤＭと輪郭線接続情報ＤＣとは、それぞれ図２２（ｂ），（ｃ）に示すようになる。なお、座標値２２の画素が先に注目画素として処理されるため、座標値２２の画素の４つの輪郭辺によって形成される輪郭線の輪郭線番号が２となり、座標値１８の画素の４つの輪郭辺によって形成される輪郭線の輪郭線番号が３となっている。
【００９３】
次に、注目画素抽出部２０は、図１３（ｂ）のバッファ領域のメモリアドレス１６〜１３に格納されている各座標値を順次取得してこれらの画素を注目画素とし、濃度値７についての輪郭線形成を行うと、図２３に示すようになる。図２３（ａ）に示すように、濃度値７の４画素のうち座標値１６の画素の上側の輪郭辺は既に生成された濃度値９の輪郭線（輪郭線番号１）に含まれているため、輪郭線番号１についての輪郭線接続情報ＤＣと輪郭線管理情報ＤＭとが更新される。また、それ以外の画素についての各輪郭辺は既成輪郭線に含まれていないため、それぞれの画素について新規輪郭線が形成される。この結果、輪郭線管理情報ＤＭと輪郭線接続情報ＤＣとは、それぞれ図２３（ｂ），（ｃ）に示すようになる。
【００９４】
次に、注目画素抽出部２０は、図１３（ｂ）のバッファ領域のメモリアドレス１２に格納されている座標値３０を取得してこの画素を注目画素とし、濃度値６についての輪郭線形成を行うと、図２４に示すようになる。図２４（ａ）に示すように、濃度値６の画素の４つの輪郭辺のうち右側の輪郭辺は既に生成された濃度値７の輪郭線（輪郭線番号５）に含まれているため、輪郭線番号５についての輪郭線接続情報ＤＣと輪郭線管理情報ＤＭとが更新される。この結果、輪郭線管理情報ＤＭと輪郭線接続情報ＤＣとは、それぞれ図２４（ｂ），（ｃ）に示すようになる。
【００９５】
次に、注目画素抽出部２０は、図１３（ｂ）のバッファ領域のメモリアドレス１１，１０に格納されている座標値３２，２４を取得してこれらの画素を注目画素とし、濃度値５についての輪郭線形成を行うと、図２５に示すようになる。図２５（ａ）に示すように、濃度値５の２画素のうち座標値２４の画素の下側の輪郭辺は既に生成された輪郭線（輪郭線番号５）に含まれている。また、座標値３２の画素については、左側の輪郭辺が既に生成された輪郭線（輪郭線番号５）に含まれているとともに、右側の輪郭辺が既に生成された輪郭線（輪郭線番号４）に含まれている。ここで、輪郭線番号４と５との輪郭辺の数を比較すると輪郭線番号４の方が小さいので、輪郭線番号４の輪郭線は輪郭線番号５の輪郭線に統合される。この結果、輪郭線番号４についての輪郭線管理情報ＤＭには終了処理が施されて終了濃度値の欄に濃度値６が記入されるとともに、輪郭辺の数が０に更新される。また、輪郭線番号５についての輪郭線管理情報ＤＭと輪郭線接続情報ＤＣとが更新される。この結果、濃度値５の２画素は輪郭線番号５の輪郭線内に含まれることとなり、輪郭線管理情報ＤＭと輪郭線接続情報ＤＣとは、それぞれ図２５（ｂ），（ｃ）に示すようになる。
【００９６】
次に、注目画素抽出部２０は、図１３（ｂ）のバッファ領域のメモリアドレス９〜７に格納されている座標値２９，１７，１１を取得してこれらの画素を順次注目画素とし、濃度値４についての輪郭線形成を行うと、図２６に示すようになる。図２６（ａ）に示すように、座標値２９の画素の右側の輪郭辺は輪郭線番号５の輪郭線に含まれており、上側の輪郭辺は輪郭線番号２の輪郭線に含まれている。従って、輪郭線番号２の輪郭線は輪郭線番号５の輪郭線に統合されて消滅する。また、座標値１７の画素の右側の輪郭辺は輪郭線番号３の輪郭線に含まれており、下側の輪郭辺は輪郭線番号５の輪郭線に含まれており、左側の輪郭辺は輪郭線番号１の輪郭線に含まれている。従って、輪郭線番号１と３の輪郭線は輪郭線番号５の輪郭線に統合されて消滅する。また、座標値１１の画素の右側の輪郭辺は輪郭線番号６の輪郭線に含まれており、下側の輪郭辺は先に統合されて生成された輪郭線番号５の輪郭線に含まれている。従って、輪郭線番号６の輪郭線は輪郭線番号５の輪郭線に統合されて消滅する。このようにして濃度値４の３画素が注目画素として処理されると、輪郭線管理情報ＤＭと輪郭線接続情報ＤＣとは、それぞれ図２６（ｂ），（ｃ）に示すようになる。
【００９７】
次に、注目画素抽出部２０は、図１３（ｂ）のバッファ領域のメモリアドレス６，５に格納されている座標値２５，１５を取得してこれらの画素を順次注目画素とし、濃度値３についての輪郭線形成を行うと、図２７に示すようになる。図２７（ａ）に示すように、座標値２５の画素の上側、下側、左側の輪郭辺は輪郭線番号５の輪郭線に含まれている。従って、座標値２５の画素が輪郭線番号５の輪郭線に含まれるように輪郭線番号５の輪郭線が更新される。また、座標値１５の画素の右側、下側の輪郭辺は輪郭線番号５の輪郭線に含まれているが、その接続状態は連続していない。このため、座標値１５の画素を輪郭線番号５の輪郭線内に含まれるように更新する処理は、分離処理となって輪郭線番号５の輪郭線の内側に新規輪郭線（輪郭線番号７）が形成される。このようにして濃度値３の２画素が注目画素として処理されると、輪郭線管理情報ＤＭと輪郭線接続情報ＤＣとは、それぞれ図２７（ｂ），（ｃ）に示すようになる。
【００９８】
次に、注目画素抽出部２０は、図１３（ｂ）のバッファ領域のメモリアドレス４〜２に格納されている座標値２３，１９，８を取得してこれらの画素を順次注目画素とし、濃度値２についての輪郭線形成を行うと、図２８に示すようになる。図２８（ａ）に示すように、座標値２３の画素の全ての輪郭辺は輪郭線番号７の輪郭線に含まれているとともに、その輪郭線の開始辺が含まれている。従って、輪郭線番号７の輪郭線に対して終了処理を行う。また、座標値１９の画素の上側、左側の輪郭辺は輪郭線番号５の輪郭線に含まれているため、輪郭線番号５についての輪郭線接続情報ＤＣと輪郭線管理情報ＤＭとが更新される。また、座標値８の画素の右側、下側の輪郭辺は輪郭線番号５の輪郭線に含まれているため、輪郭線番号５についての輪郭線接続情報ＤＣと輪郭線管理情報ＤＭとが更新される。この結果、輪郭線管理情報ＤＭと輪郭線接続情報ＤＣとは、それぞれ図２８（ｂ），（ｃ）に示すようになる。
【００９９】
次に、注目画素抽出部２０は、図１３（ｂ）のバッファ領域のメモリアドレス１，０に格納されている座標値２６，１０を取得してこれらの画素を順次注目画素とし、濃度値１についての輪郭線形成を行うと、図２９に示すようになる。図２９（ａ）に示すように、座標値２６の画素の右側を除く輪郭辺は輪郭線番号５の輪郭線に含まれているため、輪郭線番号５についての輪郭線接続情報ＤＣと輪郭線管理情報ＤＭとが更新される。また、座標値１０の画素の上側を除く輪郭辺は輪郭線番号５の輪郭線に含まれているため、輪郭線番号５についての輪郭線接続情報ＤＣと輪郭線管理情報ＤＭとが更新される。この結果、輪郭線管理情報ＤＭと輪郭線接続情報ＤＣとは、それぞれ図２９（ｂ），（ｃ）に示すようになる。
【０１００】
最後に、濃度値０についての処理であるが、濃度値０を輪郭抽出する際の閾値とする場合、抽出される輪郭線は原画像の外周部となる。従って、濃度値０については特に注目画素を抽出して１画素ごとに輪郭線を形成する処理を行わずとも原画像の外周部を接続した輪郭線を出力すればよい。そして、濃度値０については各輪郭線についての輪郭線管理情報ＤＭに対して終了処理を施すこととなる。この終了処理が施された結果を、図３０に示している。
【０１０１】
以上説明した処理を簡単に説明すると次のようになる。画像において濃度値の最大値を示す画素から降順に１画素ずつ注目画素を抽出していく。そして、注目画素の周囲の４つの輪郭辺が既成輪郭線に包含されていない場合には、４つの輪郭辺からなる輪郭線を新規輪郭線として設定し、当該新規輪郭線の接続状態を示す輪郭線接続情報を生成する。また、このとき、新規輪郭線の開始辺と、注目画素の濃度値を新規輪郭線の有効濃度範囲の開始濃度とした開始濃度値とを含む輪郭線管理情報を生成する。一方、注目画素の４つの輪郭辺のうちのいずれかが既成輪郭線に包含されている場合には、その既成輪郭線についての輪郭線接続情報と輪郭線管理情報とを更新する。そして、その更新によって注目画素のいずれかの輪郭辺が包含されていた少なくとも１つの既成輪郭線が消滅する場合には、消滅する既成輪郭線についての輪郭線管理情報に対して注目画素の濃度値を既成輪郭線の有効濃度範囲の終了濃度を示す終了濃度値として格納することによって終了処理を行う。
【０１０２】
このような処理を行うことにより、同一の濃度値を示す画素が全て注目画素として処理された際、輪郭線接続情報ＤＣにはその濃度値の輪郭線が格納されていることとなる。従って、例えば、濃度値８についての輪郭線を出力したい場合には、濃度値８を示す全ての画素が注目画素として処理された際に、輪郭線接続情報ＤＣを出力すれば所望する濃度値８の輪郭線が得られ、濃度値７以下の画素については処理することを要しない。また、全ての濃度値についての輪郭線を出力したい場合には、各濃度値を示す全ての画素の処理が行われる度に輪郭線接続情報ＤＣを出力していけば原画像を構成する全ての画素を１回ずつ抽出して処理するだけで全ての濃度値の輪郭線を得ることができる。
【０１０３】
なお、この実施の形態では、各濃度値ごとに輪郭線を形成していく際に、輪郭線管理情報ＤＭを生成／更新していくため、最終的に濃度値１までの上記処理が終了した場合は、輪郭線接続情報ＤＣをメモリ５０から消去したとしても、輪郭線管理情報ＤＭを記憶しておけば、後に任意の濃度値についての輪郭線を抽出することができる。
【０１０４】
＜５．輪郭線抽出＞
次に、上記のような注目画素を１画素ずつ抽出しつつ、輪郭線を形成させていく処理を行った後に、輪郭線管理情報ＤＭに基づいて各濃度値ごとの輪郭線を抽出する処理について説明する。この処理は、図２の輪郭抽出部６０において行われる。
【０１０５】
輪郭抽出部６０では、メモリ５０に格納されている輪郭線管理情報ＤＭを参照し、抽出すべき濃度値において有効な輪郭線の開始辺を求め、その開始辺より所定のルール（規則）に基づいて輪郭を追跡することにより所定の濃度値の輪郭線を抽出する。
【０１０６】
ここで、輪郭線を抽出する際のルールについて説明する。図３１は、開始辺の進行方向を特定するルールを示す図である。開始辺は主走査方向Ｘ（すなわち、横方向）に沿って位置する場合と副走査方向Ｙ（すなわち、縦方向）に沿って位置する場合とがある。そして、１つの開始辺が特定されると、その開始辺の進行方向を決定する。例えば、開始辺を挟んで存在する２つの画素の濃度値をａ，ｂとすると、開始辺が縦方向に位置する場合であって右側の画素の濃度値ａが左側の画素の濃度値ｂより小さい場合、又は開始辺が横方向に位置する場合であって上側の画素の濃度値ａが下側の画素の濃度値ｂより小さい場合は、図３１（ａ）に示すように、上方向又は右方向に開始辺の進行方向が設定される。これに対し、開始辺が縦方向に位置する場合であって右側の画素の濃度値ａが左側の画素の濃度値ｂより大きい場合、又は開始辺が横方向に位置する場合であって上側の画素の濃度値ａが下側の画素の濃度値ｂより大きい場合は、図３１（ｂ）に示すように、下方向又は左方向に開始辺の進行方向が設定される。
【０１０７】
次に、図３２は、輪郭線を追跡形成する際に進行方向を特定するルールを示す図である。図３２（ａ）には既に進行方向が確定した矢印を示している。ここで、抽出すべき濃度値をａとし、矢印前方の左側の画素の濃度値をｂとし、矢印前方の右側の画素の濃度値をｃとすると、「ａ≦ｂかつａ≦ｃ」であれば図３２（ｂ）に示すように進路を左方向にとり、「ａ＞ｂかつａ≦ｃ」であれば図３２（ｃ）に示すように進路を直進方向にとり、「ａ＞ｃ」であれば図３２（ｄ）に示すように進路を右方向にとる。このようなルールを設定すると、輪郭抽出の際の進行方向に対して右側には抽出すべき濃度値よりも大きい又は等しい画素が常に得られるとともに、左側には抽出すべき濃度値よりも小さい画素が常に得られる。従って、上記のようなルールに基づいて輪郭辺を辿っていけば、所望の濃度値の輪郭線を抽出することができる。
【０１０８】
実際に、図５の原画像について得られた輪郭線管理情報ＤＭに基づいて濃度値３の輪郭線を抽出する例を以下に示す。まず、図５の原画像について得られた図３０（ｂ）の輪郭線管理情報ＤＭにおいて各輪郭線ごとの有効濃度範囲を示すと図３３に示すようになる。図３３において有効濃度範囲に濃度値３を含んでいるものは輪郭線番号５と７である。従って、輪郭線番号５，７について図３０（ｂ）の輪郭線管理情報ＤＭを参照すると、それぞれの開始辺番号は６２，４５である。この開始辺を図７のように割り付けられた輪郭辺番号から特定し、開始辺より上記ルールに基づいて輪郭辺を辿っていくと、図３４に示すようになる。図３４（ａ）は輪郭辺番号６２の開始辺から抽出される輪郭線であり、図３４（ｂ）は輪郭辺番号４５の開始辺から抽出される輪郭線である。そして、図３４（ａ）と（ｂ）とに示す２つの輪郭線を合わせると、所望の濃度値３の輪郭線が得られることとなる。
【０１０９】
輪郭抽出部６０は、このようにして開始辺より輪郭線の抽出を行って輪郭線出力を行う。従って、輪郭抽出部６０が輪郭線出力を行う場合は、画素ごとに画像を走査する必要がなく、効率的に輪郭線の出力を行うことができる。すなわち、輪郭線管理情報ＤＭを一度生成しておけば、それを利用することにより、任意の濃度値についての輪郭抽出の処理を効率的に行うことができ、処理時間を短縮することができる。
【０１１０】
＜６．処理シーケンス＞
次に、上述した輪郭線接続情報ＤＣと輪郭線管理情報ＤＭとを生成／更新する処理をコンピュータなどによって行う場合の処理シーケンスについて説明する。図３５ないし図３８は、コンピュータなどによって濃度値ごとの輪郭線形成を行う処理シーケンスを示すフローチャートである。
【０１１１】
まず、ステップＳ１０において、原画像に対する前処理を行う。すなわち、この前処理においては上述のような枠付き画像の生成と輪郭辺番号の割付と濃度値に基づく画素のソーティングとが行われる。
【０１１２】
次に、ステップＳ１１において注目画素の抽出が行われる。注目画素の抽出は、ステップＳ１０のソート結果に基づいて最大の濃度値を示す画素から順次濃度値の降順に１画素ずつ行われる。
【０１１３】
そして、ステップＳ１２では、ステップＳ１１において抽出された注目画素の４つの輪郭辺が既成輪郭線に含まれているか否かを判定する。この判定は、既に生成されている輪郭線接続情報ＤＣを参照することによって行われる。そして、注目画素の４つの輪郭辺のうちいずれもが既成輪郭線に含まれていない場合は「ＮＯ」と判断されてステップＳ１３に進み、注目画素の４つの輪郭辺のうちいずれかが既成輪郭線に含まれている場合は「ＹＥＳ」と判断されてステップＳ１４に進む。
【０１１４】
ステップＳ１３に進んだ場合は、注目画素の４つの輪郭辺で構成される新規輪郭線を生成し、この新規輪郭線について輪郭線接続情報ＤＣと輪郭線管理情報ＤＭとを生成する。そして、ステップＳ１３の処理が行われると後述するステップＳ４１に進むこととなる（接続子Ａ）。
【０１１５】
また、ステップＳ１４に進んだ場合は、輪郭線接続情報ＤＣに基づいて注目画素の輪郭辺が含まれている輪郭線を示す所属輪郭線番号を取得する。このとき、注目画素の４つの輪郭辺のうち２以上の輪郭辺が既成輪郭線に含まれている場合は、それぞれの所属輪郭線番号を取得する。そして、ステップＳ１４の処理が行われるとステップＳ１５に進む。
【０１１６】
そして、ステップＳ１５では、ステップＳ１４において取得された所属輪郭線番号を検証し、注目画素の４つの輪郭辺のうち同一の輪郭線に含まれる輪郭辺が存在するか否かを判定する。すなわち、注目画素の４つの輪郭辺のうち既成輪郭線に含まれている２以上の輪郭辺のそれぞれについて所属輪郭線番号を取得した際に、同一の所属輪郭線番号を示す輪郭辺が存在する場合は「ＹＥＳ」と判断され、それ以外の場合は「ＮＯ」と判断される。「ＹＥＳ」と判断された場合は、ステップＳ１６に進み、既成輪郭線に含まれている輪郭辺の接続状態をメモリなどに記憶保存し、ステップＳ１７に進む。また、「ＮＯ」と判断された場合は、そのままステップＳ１７に進む。
【０１１７】
ステップＳ１７では、注目画素の４つの輪郭辺のうちに既成輪郭線の開始辺として登録されている輪郭辺が存在するか否かを判定する。この判定は、既に生成されている輪郭線管理情報ＤＭを参照し、注目画素の４つの輪郭辺の輪郭辺番号が既成輪郭線の開始辺番号として登録されているか否かを検証することによって行われる。そして、既成輪郭線の開始辺として登録されている輪郭辺が存在する場合は「ＹＥＳ」と判断されてステップＳ１８に進み、既成輪郭線の開始辺として登録されている輪郭辺が存在する場合は「ＮＯ」と判断されてステップＳ２１に進む（接続子Ｃ）。
【０１１８】
ステップＳ１８では、注目画素の輪郭辺を含む既成輪郭線が注目画素の４つの輪郭辺のみから構成されているか否かを判断する。ここで「ＮＯ」と判断された場合はステップＳ１９に進み、「ＹＥＳ」と判断された場合はステップＳ２０に進む。
【０１１９】
開始辺が注目画素の輪郭辺に含まれている場合は、その輪郭線の開始辺を更新することが必要となる。この理由は、注目画素を処理することによって注目画素の輪郭辺に含まれる開始辺は無効となるからである。このため、開始辺が注目画素の輪郭辺に含まれている場合は、新規輪郭線を生成し、その新規輪郭線がそれ以前の輪郭線の輪郭線接続情報ＤＣを引き継ぐ。新規輪郭線についての輪郭線管理情報ＤＭには、開始辺が登録されていないので新規輪郭線上の１つの輪郭辺（但し、注目画素に接していない輪郭辺）を選択して開始辺とする。また、新規輪郭線についての開始濃度値を注目画素の濃度値とする。そして、それ以前の輪郭線に対しては終了処理を施すこととなる。ところが、実際には、引き継いだ新規輪郭線の情報を変更することは効率が悪いので、この実施の形態では、ステップＳ１９において、つぎのような処理が行われる。
【０１２０】
輪郭線管理情報ＤＭに新規輪郭線の情報を書き込む領域を確保し、その領域に無効となる開始辺が登録されているそれ以前の輪郭線の内容をコピーする（ただし、輪郭線番号は異なる）。そしてコピーされた輪郭線管理情報ＤＭに対して注目画素の濃度値よりも１つ高い濃度値を終了濃度値に書き込むとともに輪郭辺の数を０にすることにより、生成した新規輪郭線について終了処理を施す。一方、無効となる開始辺が登録されている既成輪郭線についての輪郭線管理情報ＤＭの開始濃度値の欄に現在の注目画素の濃度値を上書きするとともに、開始辺を注目画素の４つの輪郭辺以外の輪郭辺から抽出して上書きする。このような処理を行うことにより、無効となる開始辺が登録されている輪郭線の内容を引き継いで、効率的に新たに有効となる開始辺を設定することができる。そして、この結果、注目画素の４つの輪郭辺のうち既成輪郭線の開始辺として設定されている輪郭辺が存在する場合であっても良好に輪郭線情報を更新することができる。そして、ステップＳ１９の処理が行われると、次に、ステップＳ２１に進む（接続子Ｃ）。
【０１２１】
また、開始辺が注目画素の輪郭辺に含まれている場合であって、その輪郭線が注目画素の４つの輪郭辺のみから構成されている場合は、例えば、図２０に示すような場合である。この場合は、注目画素の４つの輪郭辺のみからなる輪郭線に対して終了処理を施せばよい。従って、ステップＳ２０においては、注目画素の輪郭辺を含んでいる輪郭線に対して終了処理を施す。そして、ステップＳ２０の処理が行われると、後述するステップＳ４１に進む（接続子Ａ）。
【０１２２】
次に、ステップＳ２１において、輪郭線管理情報ＤＭを参照し、注目画素の輪郭辺が含まれている輪郭線のうちで輪郭辺の数が最も大きいものを求め、その輪郭線の輪郭線番号を取得する。
【０１２３】
そして、ステップＳ２２で、輪郭線接続情報ＤＣにおいて注目画素の輪郭辺を含んでいる輪郭線の所属輪郭線番号を、ステップＳ２１で取得した輪郭線番号に書き換える。次に、ステップＳ２３において、注目画素の４つの輪郭辺の仮想接続状態を生成し、それを保持しておく。
【０１２４】
そして、ステップＳ２４において注目画素の４つの輪郭辺のうち既成輪郭線に含まれている輪郭辺を１つ選出し、ステップＳ２５において輪郭線接続情報ＤＣを参照して選出した輪郭辺を次の輪郭辺番号に登録している輪郭辺を検出する。そして、ステップＳ２６において仮想接続状態からステップＳ２４で選出された輪郭辺の接続先となつ次の輪郭辺を検出する。そして、ステップＳ２７では、ステップＳ２６で検出された輪郭辺が既成輪郭線に含まれているか否かを判定し、含まれていない場合は「ＮＯ」となってステップＳ２８に進み、含まれている場合は「ＹＥＳ」となってステップＳ２９に進む。
【０１２５】
ステップＳ２８では、ステップＳ２５で検出された輪郭辺の次の輪郭辺番号にステップＳ２６で検出された輪郭辺番号を格納する。一方、ステップＳ２９では、輪郭線接続情報ＤＣを参照し、ステップＳ２６で検出された輪郭辺の接続先となる次の輪郭辺を検出し、この輪郭辺をステップＳ２５で検出された輪郭辺の次の輪郭辺とする。
【０１２６】
そして、ステップＳ３０においては、輪郭線接続情報ＤＣを参照し、ステップＳ２４で選出した輪郭辺の接続先となっている輪郭辺を検出する。また、ステップＳ３１においては、仮想接続状態を参照し、ステップＳ２４で選出した輪郭辺を次の輪郭辺として登録している輪郭辺を検出する。
【０１２７】
そして、ステップＳ３２においては、ステップＳ３１で検出した輪郭辺が既成輪郭辺に含まれているか否かを判定し、含まれていない場合は「ＮＯ」となってステップＳ３３に進み、含まれている場合は「ＹＥＳ」となってステップＳ３４に進む。
【０１２８】
ステップＳ３３では、ステップＳ３１で検出された輪郭辺の次の輪郭辺番号にステップＳ３０で検出された輪郭辺番号を格納する。一方、ステップＳ３４では、輪郭線接続情報ＤＣを参照し、ステップＳ３１で検出された輪郭辺を次の輪郭辺としている輪郭辺を検出し、この輪郭辺の次の輪郭辺として登録されている輪郭辺をステップＳ３０で検出された輪郭辺とする。
【０１２９】
上記のステップＳ２４〜Ｓ３４の処理で既成輪郭線に含まれている注目画素の１つの輪郭辺について輪郭辺の接続状態の更新処理が終了したこととなる。そして、ステップＳ３５において注目画素の４つの輪郭辺のうち他に既成輪郭線に含まれている輪郭辺があるか否かを判定し、「ＹＥＳ」の場合はその輪郭辺について再び同様の処理を行うべくステップＳ２４に戻り（接続子Ｅ）、「ＮＯ」の場合はステップＳ３６に進む（接続子Ｆ）。
【０１３０】
そして、ステップＳ３６においては、上記ステップＳ１６において記憶した輪郭辺の接続状態があるか否かを判定する。記憶した接続状態がある場合は「ＹＥＳ」となってステップＳ３７に進み、記憶した接続状態がない場合は「ＮＯ」となってステップＳ４１に進む。
【０１３１】
ステップＳ３７では、記憶している接続状態を読み出して、同一輪郭線に含まれている２つの輪郭辺を抽出する。そして、ステップＳ３８でこれら２つの輪郭辺の接続状態が連続しているか否かを判定する。連続していない場合は、例えば、図１９に示したように既成輪郭線の内側にホール状の輪郭線が形成されるので、ステップＳ３９に進む。一方、連続している場合はホール状の輪郭線は形成されないのでステップＳ４０に進む。
【０１３２】
ステップＳ３９では、既成輪郭線の内側に形成されるホール状の輪郭線に対して開始辺を登録し、新規輪郭線として設定する。そして、ステップＳ４０に進む。
【０１３３】
ステップＳ４０では、同一輪郭線に含まれている２つの輪郭辺を抽出する際に他の組み合わせがあるか否かを判定し、他の組み合わせがある場合はそれらの輪郭辺についてホール状輪郭線が形成されるか否かを検査するために、再びステップＳ３７に戻る。また、他の組み合わせがない場合は、「ＮＯ」となってステップＳ４１に進む。
【０１３４】
上記ステップＳ１１〜Ｓ４０の処理によって抽出された注目画素についての処理が終了したこととなり、ステップＳ４１においては次に注目画素として処理すべき画素が存在するか否かを、ソート結果のメモリアドレスに基づいて判定し、次の画素がある場合には「ＹＥＳ」となってステップＳ１１に戻る（接続子Ｇ）。また、全ての画素についての処理が終了したときは「ＮＯ」となってステップＳ４２に進む。
【０１３５】
ステップＳ４２では、抽出すべき注目画素が無くなったので、この時点で輪郭線管理情報ＤＭにおいて終了濃度値が格納されていない全ての輪郭線に対して終了濃度値「０」を格納する。つまり、終了処理が施されていない全ての輪郭線に対して終了処理を施す。この終了処理が行われるとステップＳ４３に進む。
【０１３６】
そして、ステップＳ４３において上記の処理によって生成／更新された輪郭線管理情報ＤＭを保存することにより処理シーケンスが終了する。
【０１３７】
上記のような処理を行うことにより、各濃度値ごとの輪郭線を抽出することができる輪郭線管理情報ＤＭが得られる。また、上記のような処理過程において各濃度値ごとの輪郭線を出力させる場合は、ステップＳ１１において注目画素を抽出したときに、その注目画素の濃度値を調べて前回の濃度値と異なっていれば、その時点の輪郭線接続情報ＤＣを出力するように構成すればよい。
【０１３８】
以上、この実施の形態で説明したような処理形態で画像の輪郭抽出を行えば、任意の濃度値についての輪郭抽出の処理を効率的に行うことができ、処理時間を短縮することができることはもはや明らかである。
【０１３９】
＜７．変形例＞
上記の処理においては、主として濃度値が０〜９の１０階調の画像に対する処理を例示して説明したが、これに限定するものではなく、この発明は任意の階調数の画像に対して適用可能であることは言うまでもない。
【０１４０】
次に、上記の説明においては、既成輪郭線の内側にホール状輪郭線が新たに形成されることを検出するために、輪郭辺の接続状態が連続するか否かを検出していた。しかし、これ以外に単に画像のパターン検出からホール状輪郭線が新たに形成されるか否かを検出することもできる。
【０１４１】
次に、上記実施の形態で説明した図２の画像の輪郭抽出装置１００を構成する各処理部を、表示部、キーボード、ＣＰＵ、メモリ等を備える一般的なコンピュータが所定のプログラムを実行することによって実現するものであってもよい。この場合、原画像は磁気ディスクなどに格納しておき、コンピュータ内部のＣＰＵが図３５ないし図３８に示した各手順を行う画像の輪郭抽出プログラムを実行することによって、各濃度値ごとの輪郭線が順次形成されていくとともに、メモリ内には輪郭線接続情報ＤＣと輪郭線管理情報ＤＭとが順次生成／更新されていく。そして、コンピュータが上述のような処理を行うことによって、コンピュータによる輪郭抽出処理の時間が短縮される。なお、コンピュータが実行する輪郭抽出プログラムは、ＣＤ−ＲＯＭやフレキシブルディスクなどの可搬性の記録媒体若しくはコンピュータ内設の磁気ディスクなどの固定の記録媒体に記録保存されており、コンピュータのＣＰＵがこれらの記録媒体から輪郭抽出プログラムを読み取って実行するものであってもよい。
【０１４２】
【発明の効果】
以上説明したように、請求項１に記載の発明によれば、画像において濃度値の最大値を示す画素から降順に１画素ずつ注目画素を抽出して、輪郭線接続情報と輪郭線管理情報とを更新していく過程において各濃度値ごとの輪郭線が形成されていく。このため、異なる濃度値についての輪郭線をいくつか抽出する際にも、画像を構成する全ての画素を注目画素として抽出して行う処理を１回だけ行えばよい。従って、任意の濃度値についての輪郭抽出の処理を効率的に行うことができ、処理時間を短縮することができる。また、輪郭線管理情報に開始辺を含ませるため、後に任意の濃度値の輪郭抽出を行う場合に輪郭線管理情報を用いることができる。
【０１４３】
請求項２に記載の発明によれば、画像における同一の濃度値を示す画素が注目画素として処理されれば、その濃度値の輪郭線が得られるため、輪郭抽出の処理を効率的に行うことができ、処理時間を短縮することができる。
【０１４４】
請求項３に記載の発明によれば、記憶された輪郭線管理情報に基づいて所定の濃度値の輪郭線を抽出することができるため、改めて注目画素を抽出しつつ輪郭線接続情報を生成する必要はない。従って、輪郭抽出の処理を効率的に行うことができ、処理時間を短縮することができる。
【０１４５】
請求項４に記載の発明によれば、効率的に画像を構成する画素を濃度値の降順若しくは昇順に並べ換えることができる。この結果、輪郭抽出の処理を効率的に行うことができ、処理時間を短縮することができる。
【０１４６】
請求項５に記載の発明によれば、画像において濃度値の最大値を示す画素から降順に１画素ずつ注目画素を抽出して、輪郭線接続情報と輪郭線管理情報とを更新していく過程において各濃度値ごとの輪郭線が形成されていく。このため、異なる濃度値についての輪郭線をいくつか抽出する際にも、画像を構成する全ての画素を注目画素として抽出して行う処理を１回だけ行えばよい。従って、任意の濃度値についての輪郭抽出の処理を効率的に行うことができ、処理時間を短縮することができる。
【０１４７】
請求項６に記載の発明によれば、コンピュータが、所定の画像の輪郭抽出プログラムを実行することにより、画像の輪郭抽出をコンピュータが効率的に行うことができ、処理時間を短縮することができる。
【図面の簡単な説明】
【図１】この発明における輪郭線の生成／更新の概念を示す図である。
【図２】この発明の一実施例としての画像の輪郭抽出装置の構成を示すブロック図である。
【図３】輪郭線接続情報を説明する図である。
【図４】輪郭線管理情報を説明する図である。
【図５】枠付き画像の生成を説明する図である。
【図６】輪郭辺番号の割付を説明する図である。
【図７】７×６の枠付き画像について輪郭辺番号を示す図である。
【図８】７×６の枠付き画像における各画素の座標値を示す図である。
【図９】原画像について濃度値ごとの画素数をカウントした結果を示す図である。
【図１０】各濃度値ごとの累積画素数を示す図である。
【図１１】濃度値に基づくソート処理を示す図である。
【図１２】濃度値に基づくソート処理を示す図である。
【図１３】ソート処理が行われた各濃度値ごとの累積画素数とバッファ領域とを示す図である。
【図１４】注目画素の４つの輪郭辺が１つの既成輪郭線に含まれている場合を示す図である。
【図１５】図１４（ａ）の輪郭線Ｅ１を図１４（ｂ）の輪郭線Ｅ１に更新する過程を示す図である。
【図１６】注目画素の４つの輪郭辺が３つの既成輪郭線に含まれている場合を示す図である。
【図１７】図１６（ａ）の状態における輪郭線接続情報などを示している図である。
【図１８】輪郭線接続情報の一例を示す図である。
【図１９】ホール状の輪郭線が形成される場合の一例を示す図である。
【図２０】輪郭線が消滅する場合の一例を示す図である。
【図２１】各濃度値ごとの輪郭線を抽出していく際の輪郭線管理情報と輪郭線接続情報とを示す図である。
【図２２】各濃度値ごとの輪郭線を抽出していく際の輪郭線管理情報と輪郭線接続情報とを示す図である。
【図２３】各濃度値ごとの輪郭線を抽出していく際の輪郭線管理情報と輪郭線接続情報とを示す図である。
【図２４】各濃度値ごとの輪郭線を抽出していく際の輪郭線管理情報と輪郭線接続情報とを示す図である。
【図２５】各濃度値ごとの輪郭線を抽出していく際の輪郭線管理情報と輪郭線接続情報とを示す図である。
【図２６】各濃度値ごとの輪郭線を抽出していく際の輪郭線管理情報と輪郭線接続情報とを示す図である。
【図２７】各濃度値ごとの輪郭線を抽出していく際の輪郭線管理情報と輪郭線接続情報とを示す図である。
【図２８】各濃度値ごとの輪郭線を抽出していく際の輪郭線管理情報と輪郭線接続情報とを示す図である。
【図２９】各濃度値ごとの輪郭線を抽出していく際の輪郭線管理情報と輪郭線接続情報とを示す図である。
【図３０】各濃度値ごとの輪郭線を抽出していく際の輪郭線管理情報と輪郭線接続情報とを示す図である。
【図３１】開始辺の進行方向を特定するルールを示す図である。
【図３２】輪郭線を追跡形成する際に進行方向を特定するルールを示す図である。
【図３３】輪郭線管理情報において各輪郭線ごとの有効濃度範囲を示す図である。
【図３４】開始辺よりルールに基づいて輪郭辺を辿っていく過程を示す図である。
【図３５】コンピュータなどによって濃度値ごとの輪郭線形成を行う処理シーケンスを示すフローチャートである。
【図３６】コンピュータなどによって濃度値ごとの輪郭線形成を行う処理シーケンスを示すフローチャートである。
【図３７】コンピュータなどによって濃度値ごとの輪郭線形成を行う処理シーケンスを示すフローチャートである。
【図３８】コンピュータなどによって濃度値ごとの輪郭線形成を行う処理シーケンスを示すフローチャートである。
【符号の説明】
１０  前処理部
２０  注目画素抽出部
３０  輪郭辺判定部
４０  輪郭線形成部
４０ａ  輪郭線情報生成部
４０ｂ  輪郭線情報更新部
５０  メモリ
６０  輪郭抽出部
７０  記憶部
ＤＭ  輪郭線管理情報
ＤＣ  輪郭線接続情報
【図１】
0003679619.tif 000002
【図２】
0003679619.tif 000003
【図３】
0003679619.tif 000004
【図４】
0003679619.tif 000005
【図５】
0003679619.tif 000006
【図６】
0003679619.tif 000007
【図７】
0003679619.tif 000008
【図８】
0003679619.tif 000009
【図９】
0003679619.tif 000010
【図１０】
0003679619.tif 000011
【図１１】
0003679619.tif 000012
【図１２】
0003679619.tif 000013
【図１３】
0003679619.tif 000014
【図１４】
0003679619.tif 000015
【図１５】
0003679619.tif 000016
【図１６】
0003679619.tif 000017
【図１７】
0003679619.tif 000018
【図１８】
0003679619.tif 000019
【図１９】
0003679619.tif 000020
【図２０】
0003679619.tif 000021
【図２１】
0003679619.tif 000022
【図２２】
0003679619.tif 000023
【図２３】
0003679619.tif 000024
【図２４】
0003679619.tif 000025
【図２５】
0003679619.tif 000026
【図２６】
0003679619.tif 000027
【図２７】
0003679619.tif 000028
【図２８】
0003679619.tif 000029
【図２９】
0003679619.tif 000030
【図３０】
0003679619.tif 000031
【図３１】
0003679619.tif 000032
【図３２】
0003679619.tif 000033
【図３３】
0003679619.tif 000034
【図３４】
0003679619.tif 000035
【図３５】
0003679619.tif 000036
【図３６】
0003679619.tif 000037
【図３７】
0003679619.tif 000038
【図３８】
0003679619.tif 000039