(57)【特許請求の範囲】
【請求項１】
多次元に配置された画素を有する画像に含まれる線成分を抽出するための装置であって、
前記画像の各画素の値に応じて活性状態・非活性状態としたセルラオートマトンの各セルごとに、注目セルの周囲セルから受けた入力の状態と、注目セルの現在の状態とに基づいて、注目セルから周囲セルに対して出力すべき次の状態を算出するとともに、注目セルの現在の状態と、周囲セルから受けた入力の状態とに基づいて、注目セルの次の状態を算出して、セルの状態を多次元で示すコンフィギュレーション・パターンを生成し記録する処理を繰り返し行うパターン生成手段と、
パターン生成手段によって記録された、基準時点(q)の前後所定回数分(q-k,..,q-1,t,q+1,...,q+l)のコンフィギュレーション・パターンに基づいて、時間経過とともに、所定の向きの仮想線上のセルに沿って活性状態の出現位置が移動した部分を検出し、当該部分の基準時点(q)における仮想線上のセルを注目セルとし、前記所定の向きの仮想線の一部であることを示す一次フラグを当該注目セルに記録して、一次フラグの配置を多次元で示す一次フラグパターンを生成し記録する処理を、基準時点(q)を順次ずらせて行う一次検出手段と、
一次検出手段によって記録された一次フラグパターンにおいて、一方向きの一次フラグと反対向きの一次フラグの双方が記録されているセルを検出し、線分の一部であることを示すマークを当該セルに記録する線分検出手段と、
を備えた線分抽出装置。
【請求項２】
多次元に配置された画素を有する画像に含まれる線成分を抽出するための装置をコンピュータによって実現するための線分抽出プログラムであって、
前記画像の各画素の値に応じて活性状態・非活性状態としたセルラオートマトンの各セルごとに、注目セルの周囲セルから受けた入力の状態と、注目セルの現在の状態とに基づいて、注目セルから周囲セルに対して出力すべき次の状態を算出するとともに、注目セルの現在の状態と、周囲セルから受けた入力の状態とに基づいて、注目セルの次の状態を算出して、セルの状態を多次元で示すコンフィギュレーション・パターンを生成し記録する処理を繰り返し行うパターン生成手段と、
パターン生成手段によって記録された、基準時点(q)の前後所定回数分(q-k,..,q-1,q,q+1,...,q+l)のコンフィギュレーション・パターンに基づいて、時間経過とともに、所定の向きの仮想線上のセルに沿って活性状態の出現位置が移動した部分を検出し、当該部分の基準時点(q)における仮想線上のセルを注目セルとし、前記所定の向きの仮想線の一部であることを示す一次フラグを当該注目セルに記録して、一次フラグの配置を多次元で示す一次フラグパターンを生成し記録する処理を、基準時点(q)を順次ずらせて行う一次検出手段と、
一次検出手段によって記録された一次フラグパターンにおいて、一方向きの一次フラグと反対向きの一次フラグの双方が記録されているセルを検出し、線分の一部であることを示すマークを当該セルに記録する線分検出手段と、
をコンピュータによって実現するための線分抽出プログラム。
【請求項３】
請求項２の線分抽出プログラムにおいて、
前記パターン生成手段、一次検出手段の少なくとも一つは、処理対象である前記画像において前記注目セルを中心とする所定範囲のセルの全てが非活性状態である場合には、当該注目セルについての処理を行わないことを特徴とする線分抽出プログラム。
【請求項４】
請求項２または３の線分抽出プログラムにおいて、
前記パターン生成手段、一次検出手段、線分検出手段による処理は順次繰り返して行われるものであり、
処理対象である前記画像の黒の画素の数と、線分検出手段によって今回新たに線分の一部であるとされたセルの数との関係が所定の条件を満たした場合には、処理を停止させる停止手段をさらに備えていることを特徴とする線分抽出プログラム。
【請求項５】
請求項２〜４のいずれかの線分抽出プログラムにおいて、
線分検出手段によって線分と判断されたセルのうち、処理対象である前記画像の対応する画素が黒でないセルは、最終的に線分でないと判断するノイズ除去手段をさらに備えていることを特徴とする線分抽出プログラム。
【請求項６】
請求項２〜５のいずれかの線分抽出プログラムにおいて、
前記線分検出手段は、抽出した線分の方向も記録することを特徴とする線分抽出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、画像データに含まれる線分を抽出するための装置に関するものである。
【背景技術】
【０００２】
画像に含まれる線分を検出するため、発明者は既に、二次元セルラオートマトンを用いた装置を提案している（特許文献１、２、３）。これら装置によれば、テンプレートや画像オペレータを用いた従来の線分検出よりも迅速にかつ正確に線分を検出することができる。
【０００３】
【特許文献１】特開平６−１２４３４８号公報
【０００４】
【特許文献２】特開平６−５２３１５号公報
【０００５】
【特許文献３】特開平６−５２３０６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
発明者の提案した上記技術は、従来技術に比べると迅速であり正確であるという特徴を有しているが、それでもなお、線分検出にノイズが含まれることがあった。また、処理対象である画像の特質によっては、必ずしも処理が迅速ではないという問題もあった。
【０００７】
そこで、この発明は、上記のような問題点を解決し、処理を正確化ないしは迅速化した線分抽出装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
以下、この発明の独立した各側面を示す。
【０００９】
(1)(3)この発明に係る線分抽出装置は、多次元に配置された画素を有する画像に含まれる線成分を抽出するための装置であって、前記画像の各画素の値に応じて活性状態・非活性状態としたセルラオートマトンの各セルごとに、注目セルの周囲セルから受けた入力の状態と、注目セルの現在の状態とに基づいて、注目セルから周囲セルに対して出力すべき次の状態を算出するとともに、注目セルの現在の状態と、周囲セルから受けた入力の状態とに基づいて、注目セルの次の状態を算出して、セルの状態を多次元で示すコンフィギュレーション・パターンを生成し記録する処理を繰り返し行うパターン生成手段と、パターン生成手段によって記録された、基準時点(q)の前後所定回数分(q-k,..,q-1,t,q+1,...,q+l)のコンフィギュレーション・パターンに基づいて、時間経過とともに、所定の向きの仮想線上のセルに沿って活性状態の出現位置が移動した部分を検出し、当該部分の基準時点(q)における仮想線上のセルを注目セルとし、前記所定の向きの仮想線の一部であることを示す一次フラグを当該注目セルに記録して、一次フラグの配置を多次元で示す一次フラグパターンを生成し記録する処理を、基準時点(q)を順次ずらせて行う一次検出手段と、一次検出手段によって記録された一次フラグパターンにおいて、一方向きの一次フラグと反対向きの一次フラグの双方が記録されているセルを検出し、線分の一部であることを示すマークを当該セルに記録する線分検出手段とを備えている。
【００１０】
したがって、迅速でありながら正確な線の抽出を行うことができる。
【００１１】
(2)(6)この発明に係る線分抽出装置は、多次元に配置された画素を有する画像に含まれる線成分を抽出するための装置であって、前記画像の各画素の値に応じて活性状態・非活性状態としたセルラオートマトンの各セルごとに、注目セルの周囲セルから受けた入力の状態と、注目セルの現在の状態とに基づいて、注目セルから周囲セルに対して出力すべき次の状態を算出するとともに、注目セルの現在の状態と、周囲セルから受けた入力の状態とに基づいて、注目セルの次の状態を算出して、セルの状態を多次元で示すコンフィギュレーション・パターンを生成し記録する処理を繰り返し行うパターン生成手段と、パターン生成手段によって記録された、基準時点(q)の前後所定回数分(q-k,..,q-1,q,q+1,...,q+l)のコンフィギュレーション・パターンに基づいて、時間経過とともに、所定の向きの仮想線上のセルに沿って活性状態の出現位置が移動した部分を検出し、当該部分の基準時点(q)における仮想線上のセルを注目セルとし、前記所定の向きの仮想線の一部であることを示す一次フラグを当該注目セルに記録して、一次フラグの配置を二次元で示す一次フラグパターンを生成し記録する処理を、基準時点(q)を順次ずらせて行う一次検出手段と、一次検出手段によって記録された、基準時点(r)の前後所定回数分(r-p,..,r-1,r,r+1,...,r+u)の一次フラグパターンに基づいて、時間経過とともに、所定の向きの仮想線上のセルに沿って一次フラグの出現位置が移動した部分のうち、当該所定の向きと一次フラグの示す所定の向きが一致するものを検出し、当該部分の基準時点(r)における仮想線上のセルを注目セルとし、前記所定の向きの仮想線の一部であることを示す二次フラグを当該注目セルに記録して、二次フラグの配置を二次元で示す二次フラグパターンを記録する処理を、基準時点(r)を順次ずらせて行う二次検出手段と、二次検出手段によって記録された二次フラグパターンにおいて、一方向きの二次フラグと反対向きの二次フラグの双方が記録されているセルを検出し、線分の一部であることを示すマークを当該セルに記録する線分検出手段とを備えている。
【００１２】
したがって、ノイズを排除して、より正確に線分の抽出を行うことができる。
【００１３】
(4)この発明に係る線分抽出プログラムは、パターン生成手段、一次検出手段の少なくとも一つは、処理対象である前記画像において注目セルを中心とする所定範囲のセルの全てが非活性状態である場合には、当該注目セルについての処理を行わないことを特徴としている。
【００１４】
したがって、有意な結果が得られる可能性が少ない部分における処理を省略して、処理の迅速性と正確性の両立を図ることができる。
【００１５】
(5)この発明に係る線分抽出プログラムは、パターン生成手段、一次検出手段、線分検出手段による処理は順次繰り返して行われるものであり、処理対象である前記画像の黒の画素の数と、線分検出手段によって今回新たに線分の一部であるとされたセルの数との関係が所定の条件を満たした場合には、処理を停止させる停止手段をさらに備えていることを特徴としている。
【００１６】
したがって、新たに検出される線分の数に応じて、自律的に処理を完了させることができる。
【００１７】
(7)この発明に係る線分抽出プログラムは、パターン生成手段、一次検出手段、二次検出手段の少なくとも一つは、前記注目セルを中心とする所定範囲のセルの全てが非活性状態である場合には、当該注目セルについての処理を行わないことを特徴としている。
【００１８】
したがって、有意な結果が得られる可能性が少ない部分における処理を省略して、処理の迅速性と正確性の両立を図ることができる。
【００１９】
(8)この発明に係る線分抽出プログラムは、パターン生成手段、一次検出手段、二次検出手段、線分検出手段による処理は順次繰り返して行われるものであり、処理対象である前記画像の黒の画素の数と、線分検出手段によって今回新たに線分の一部であるとされたセルの数との関係が所定の条件を満たした場合には、処理を停止させる停止手段をさらに備えていることを特徴としている。
【００２０】
したがって、新たに検出される線分の数に応じて、自律的に処理を完了させることができる。
【００２１】
(9)この発明に係る線分抽出プログラムは、線分検出手段によって線分と判断されたセルのうち、処理対象である前記画像の対応する画素が黒でないセルは、最終的に線分でないと判断するノイズ除去手段を、コンピュータによって実現することを特徴としている。
【００２２】
したがって、迅速に検出ノイズを排除することができる。
【００２３】
(10)この発明に係る線分抽出プログラムは、線分検出手段が、抽出した線分の方向も記録することを特徴としている。
【００２４】
したがって、線分抽出だけでなくその方向も示すことが可能である。
【００２５】
この発明において、「多次元に配置された」とは、二次元平面に配置された場合や三次元空間・四次元空間などの多次元空間に配置された場合を含む概念である。
【００２６】
(11)(12)この発明に係る線分抽出装置は、多次元に配置された画素を有する画像に含まれる線成分を抽出するための装置であって、前記画像の各画素の値に応じて活性状態・非活性状態としたセルラオートマトンの各セルごとに、注目セルの周囲セルから受けた入力の状態と、注目セルの現在の状態とに基づいて、注目セルから周囲セルに対して出力すべき次の状態を算出するとともに、注目セルの現在の状態と、周囲セルから受けた入力の状態とに基づいて、注目セルの次の状態を算出して、セルの状態を多次元で示すコンフィギュレーション・パターンを生成し記録する処理を繰り返し行うパターン生成手段と、パターン生成手段によって記録された一連のコンフィギュレーション・パターンにおいて、活性状態または非活性状態にあるセルの移動を検出し、当該移動に基づいて線分の判断を行う線分判断手段とを備えている。
【００２７】
したがって、正確な線の抽出を行うことができる。
【００２８】
(13)(14)この発明に係るパターン生成装置は、多次元に配置された画素を有する画像に含まれる線成分を抽出するために用いるコンフィギュレーションパターンを生成するための装置であって、前記画像の各画素の値に応じて活性状態・非活性状態とした各セルごとに、注目セルの現在の状態と、周囲セルから受けた入力の状態とに基づいて、注目セルの次の状態を算出して、セルの状態を多次元で示すコンフィギュレーション・パターンを生成し記録する処理を繰り返し行うパターン生成手段を備え、前記パターン生成手段は、前記注目セルに対する周囲セルからの入力を、当該注目セルから当該周囲セルに対する出力の状態と当該周囲セルの状態とに基づいて生成することを特徴としている。
【００２９】
したがって、線分の抽出が可能な時系列によるコンフィギュレーション・パターンの生成が可能である。
【００３０】
「パターン生成手段」とは、コンフィギュレーションパターンを生成する手段をいい、実施形態においては、図１１ａのステップＳ４がこれに対応する。
【００３１】
「一次検出手段」とは、一連のコンフィギュレーションパターンに基づいて、活性状態または非活性状態セルの動きを検出するものであり、実施形態においては、図１１ａのステップＳ５がこれに対応する。
【００３２】
「二次検出手段」とは、一連の一次フラグパターンに基づいて、一次フラグの存在するセルまたは存在しないセルの動きを検出するものであり、実施形態においては、図１１ａのステップＳ６がこれに対応する。
【００３３】
「線分検出手段」とは、コンフィギュレーションパターンから直接的に、またはコンフィギュレーションパターンに基づいて得られた一次フラグまたは二次フラグに基づいて線分を検出するものをいい、実施形態においては、図１１ａのステップＳ７がこれに対応する。
【００３４】
「停止手段」とは、フラグまたは線分の検出状況に応じて処理を停止するものをいい、実施形態においては、図１１ｂのステップＳ８がこれに対応する。
【００３５】
「ノイズ除去手段」とは、抽出された線分からノイズと思われる部分を取り除く処理をするものをいい、実施形態では、図１１ｂのステップＳ１０がこれに対応する。
【００３６】
「線分判断手段」とは、コンフィギュレーションパターンから直接的に、またはコンフィギュレーションパターンに基づいて得られたフラグ等に基づいて線分を検出するものをいう。実施形態では、一次検出手段、二次検出手段、線分検出手段が、線分判断手段に対応する。
【００３７】
「セルラオートマトン」とは、配列されたセルの状態を決定するモデルである。時刻ｔにおける各セルの状態が、少なくとも、それより前の時刻における当該セルの状態と周囲のセルの状態を考慮して決定されるものをいう。
【００３８】
たとえば、実施形態において示したように、時刻ｔにおける各セルの状態を、時刻ｔ−１における当該セルの状態と周囲のセルから受けた入力の状態に基づいて決定するようにしてもよい。ここで、周囲のセルから受けた入力は、周囲の各セルからみれば出力にあたることになる。各セル（当該セル）は、次のようにして他のセルに対する出力の状態を決定する。時刻ｔ−１において当該セルが他のセルから受けた入力の状態と、時刻ｔ−１における当該セルの現在の状態とに基づいて、当該セルから他のセルに対して時刻ｔに出力すべき状態を算出する。
【００３９】
したがって、実施形態に示す場合においても、時刻ｔにおける注目セルの状態を決定するために、時刻ｔ−１における周囲セルからの入力が用いられており、時刻ｔ−１における周囲セルからの入力の状態を決定するために、時刻ｔ−１における周囲セルの状態が用いられている。したがって、実施形態においても、間接的にではあるが、時刻ｔにおける注目セルの状態は、時刻ｔ−１における当該セルの状態と周囲のセルの状態に基づいて決定されるということができる。
【００４０】
実施形態に示す上記の手法は、発明者が独自に考案したものであるが、この明細書では、セルラオートマトンの一種であるとした。
【００４１】
「コンフィギュレーション・パターン」とは、上記の意味におけるセルラオートマトンによって生成されるセルのパターン（一次元配列、二次元配列または多次元配列など）をいう。
【００４２】
「プログラム」とは、ＣＰＵにより直接実行可能なプログラムだけでなく、ソース形式のプログラム、圧縮処理がされたプログラム、暗号化されたプログラム等を含む概念である。
【発明を実施するための形態】
【００４３】
１．全体構成
図１に、この発明の一実施形態による線分抽出装置の機能ブロック図を示す。パターン生成手段２は、処理対象である二値の原画像ＯＲＧを受ける。たとえば、図２Ａに示すように、原画像ＯＲＧは、Ｉ列Ｊ行の画素を有しているものとする。各画素は、「１」の部分が黒、「０」の部分が白を示している。パターン生成手段２は、原画像ＯＲＧの各画素の「１」「０」を「活性状態」「非活性状態」に対応付ける。
【００４４】
(1)コンフィギュレーション・パターンの生成
パターン生成手段２は、セルラオートマトンにしたがって、各セル（画素に対応）ごとに次の状態を決定する。各セルにおける次の状態ａt+1(i,j)は、注目セルの現在の状態ａt(i,j)と周囲セル（たとえば注目セルの周り８つのセル）からの入力の状態ｂt(i,j)(m,n)に基づいて決定される(図２Ｂ参照）。なお、ここで、ｉ、ｊはセルの位置を示している。
【００４５】
図から明らかであるが、ｂt(i,j)(0,-1)は注目セルの上に隣接する周囲セルからの入力の状態、ｂt(i,j)(1,-1)は注目セルの右上に隣接する周囲セルからの入力の状態・・・ｂt(i,j)(-1,-1)は注目セルの左上に隣接する周囲セルからの入力の状態を表している。なお、周囲セルからの入力の状態ｂt(i,j)(m,n)がどのようにして決定されるかについては、後述する。
【００４６】
パターン生成手段２は、全てのセルについて次の状態ａt+1(i,j)が「活性状態」であるか「非活性状態」であるかを決定し、次の時間におけるパターンＡt+1（コンフィギュレーション・パターンという）を生成する。生成されたコンフィギュレーション・パターンＡt+1は、記録部１０に記録される。
【００４７】
なお、上記処理において、パターン生成手段２は、注目セルから周囲セルに対する次の出力ｃt+1(i,j)(m,n)（周囲セルにとっては入力ｂt+1(i,j)(-m,-n)となる）を、注目セルの現在の状態ａt(i,j)と周囲セルからの入力ｂt(i,j)(m,n)とに基づいて決定する。
【００４８】
パターン生成手段２は、生成したコンフィギュレーション・パターンＡt+1に基づいて、上記と同様にして、さらに次のコンフィギュレーション・パターンＡt+2を生成し記録する。したがって、記録部１０には、図３ａ、図３ｃ、図３ｅ・・・図３ｕの上段に示すように、Ａ0から順次、Ａ1Ａ2Ａ3・・・というように、コンフィギュレーションパターンが記録されることになる。図３において、黒色で示した部分が「活性」状態のセルである。なお、Ａ0は原画像である。
【００４９】
(2)一次フラグパターンの生成
一次検出手段４は、記録部１０に記録された所定時点ｑのコンフィギュレーションパターンＡqの前後所定個のコンフィギュレーションパターンＡq--2からＡq-+2までを用いて、「活性状態」にあるセルが、時間経過とともに所定の向きの仮想線上に移動したことを検出し、線分検出のための一次検出フラグを注目セルに立てる。
【００５０】
この処理を、図４を用いて説明する。図４Ｃは、所定時点ｑにおけるコンフィギュレーション・パターンＡqの注目セルを中心とする５×５のセルを示したものである。図中、黒色で示す部分は「活性状態」を表している。図４Ａ、図４Ｂは、所定時点ｑより２つ前の時点ｑ−２、１つ前の時点ｑ−１におけるコンフィギュレーション・パターンＡq-2、Ａq-1の対応するセルを示している。図４Ｄ、図４Ｅは、所定時点ｔより１つ後の時点ｑ＋１、２つ後の時点ｑ＋２におけるコンフィギュレーション・パターンＡq+1、Ａq+2の対応するセルを示している。
【００５１】
一次検出手段４は、時間経過とともに図４Ａから図４Ｅに示すように、「活性状態」が右下に向かう斜めの仮想線ＩＬにそって移動したかどうかを判断する。つまり、Ａq-2Ａq-1ＡqＡq+1Ａq+2において、それぞれ、図４Ａ〜図４Ｅに黒色で示す部分が「活性状態」にあるという条件を満足するかどうかを判断する。この実施形態では、図４Ａ〜図４Ｅの５つのうち、３つ以上で条件を満足していれば、一次検出手段４は、注目セル（図４Ｃの中央のセル）が仮想線ＩＬの一部を構成すると推定する。そして、一次フラグを記録するための領域（ｉ列、ｊ行のセルに対応）の、注目セル（図４Ｃの中央のセル）に対応するセルに一次フラグを立てる。なお、この一次フラグｐｆは、当該セルが仮想線ＩＬの一部であると判断されたことを示すだけでなく、図５に示すように、仮想線ＩＬの向きも表すようにしている。
【００５２】
なお、上記では右下に向かう仮想線ＩＬについて説明したが、上、右上、右、右下、下、左下、左、左上の８方向全てについて検討しフラグを立てる。
【００５３】
さらに、一次検出手段４は、全てのセルを順次注目セルとして上記処理を行う。これにより、一次フラグを記録するための領域には、一次フラグパターンＰＦtが記録されることになる。
【００５４】
一次検出手段４は、上記のようにして一次フラグパターンを算出し記録する処理を、所定時間ｑを移動させながら実行する。これにより、記録部１０には、各時点ごとの一次フラグパターンが記録されていく。図３ａ、図３ｃ、図３ｅ・・・図３ｕの中段と下段に、上段のコンフィギュレーション・パターンに基づいて得られた一次フラグパターンを示す。なお、表示の都合上、下、右、右下、右上の一次フラグパターンは中段に示し、上、左、左上、左下の一次フラグパターンは下段に分けて示した。
【００５５】
(3)二次フラグパターンの生成
次に、図１の二次検出手段６は、記録部１０に記録された所定時点ｒの一次フラグパターンＰＦrの前後所定個の一次フラグパターンＰＦr-2からＰＦr+2までを用いて、一次フラグが立っているセルが、時間経過とともに所定の向きの仮想線上に移動したことを検出し、線分検出のための二次検出フラグを注目セルに立てる。
【００５６】
その処理は、上記の一次フラグの場合と同様であり、線分の一部であると推定されると、二次フラグを記録するための領域に二次フラグが記録されていく。ただし、図６に示すように、一次フラグの向きと、一次フラグの移動の向き（仮想線の向き）が一致している場合にのみ、二次フラグを立てるようにしている。なお、この二次フラグｓｆは、当該セルが仮想線ＩＬの一部であると判断されたことを示すだけでなく、図８に示すように、仮想線ＩＬの向きも表すようにしている。この点は、一次フラグと同様である。なお、図７に示すように、一次フラグの移動が検出された場合であっても、それが一次フラグの向きと一致していない場合には、二次フラグは立てない。
【００５７】
二次検出手段６は、上記のようにして二次フラグを算出し記録する処理を、所定時間ｔを移動させながら実行する。記録部１０には、各時点ごとに生成された二次フラグが、一つの二次フラグパターンＳＦとして蓄積されていく。なお、一次フラグパターンは、その時間的な移動を検出する必要があったので、各時点ごとにパターンを生成したが、二次フラグパターンは、その時間的な移動を検出する必要はないので、各時点に発生した二次フラグを一つにまとめてパターンとして記録しておけばよい。
【００５８】
図３ｂ、図３ｄ、図３ｆ・・・図３ｖの上段と中段に、図３ａ、図３ｃ、図３ｅ・・・図３ｕの一次フラグパターンに基づいて得られた二次フラグパターンＳＦを示す。なお、これらの図では、表示の都合上、その時刻において新たに生成されたフラグのみを示している。
【００５９】
(4)線分検出
次に、線分検出手段８は、記録された二次フラグパターンＳＦに基づいて、同一のセルにおいて反対向きの二次フラグが立っているセルを検出する。そして、線分マークを記録するための領域に線分マークを記録していく。たとえば、二次フラグパターンＳＦが図９Ａのようであれば、図９Ｂに示すように、左上向きの二次フラグと、右下向きの二次フラグとが揃っているセルについてのみ、線分マークｒｌを記録する。なお、線分検出手段８は、上向きの二次フラグと下向きの二次フラグが揃っているセル、右上向きの二次フラグと左下向きの二次フラグが揃っているセル、右向きの二次フラグと左向きの二次フラグが揃っているセルについても同様の検出を行う。なお、線分マークｒｌは、図９Ｂに表されるように線分の方向も示している。
【００６０】
このようにして、線分パターンＲＬが生成され、線分抽出結果として出力される。図３ｂ、図３ｄ、図３ｆ・・・図３ｖの下段に、抽出された線分マーカパターンを示す。図３ｖから明らかなように、図３ａの原画像（コンフィギュレーションパターンＡ0）の線分が適切に抽出されている。
【００６１】
２．ハードウエア構成
図１０に、図１に示す線分抽出装置をＣＰＵを用いて実現した場合のハードウエア構成を示す。ＣＰＵ１８には、メモリ１２、ディスプレイ１４、キーボード／マウス１６、ハードディスク２０、ＣＤ−ＲＯＭドライブ２２が接続されている。メモリ１２は、バッファ領域やワークエリアとして用いられる。ハードディスク２０には、オペレーティングシステム（ＯＳ）２４、線分抽出プログラム２６などが記録されている。線分抽出プログラム２６は、ＯＳ２４と協働してその機能を発揮する。これらプログラムは、ＣＤ−ＲＯＭドライブ２２を介して、ＣＤ−ＲＯＭ２８に記録されていたものを、ハードディスク２０にインストールしたものである。
【００６２】
３．線分抽出プログラム
図１１に、ハードディスク２０に記録された線分抽出プログラム２６のフローチャートを示す。ＣＰＵ１８は、上述の(1)コンフィギュレーション・パターンの生成、(2)一次フラグ・パターンの生成、(3)二次フラグ・パターンの生成、(4)線分パターンの生成を実行する。
【００６３】
ＣＰＵ１８は、まずｔを０に設定する（ステップＳ１）。次に、原画像をハードディスク２０に記録し、これを二値化する（ステップＳ２）。次に、ＣＰＵ１８は、この二値化原画像を時刻ｔ＝０のコンフィギュレーション・パターンＡ0として、コンフィギュレーション・バッファ（メモリ１２に確保した領域）に記録する（ステップＳ３）。
【００６４】
(1)コンフィギュレーションパターンＡの生成
次に、ＣＰＵ１８は、時刻ｔ＝１のコンフィギュレーション・パターンＡ1を生成し、コンフィギュレーション・バッファに記録する（ステップＳ４）。コンフィギュレーション・パターンの生成処理の詳細を、図１２に示す。
【００６５】
ＣＰＵ１８は、まず、ｉ＝２、ｊ＝２とする（ステップＳ４１、Ｓ４２）。次に、２列２行の位置にあるセルを注目セルとする（ステップＳ４３）。図１３の斜線のセルが注目セルである。ＣＰＵ１８は、コンフィギュレーション・パターンＡ0（つまり二値化原画像）において、注目セルを中心とする５×５のセルが全て「非活性」であるか否かを判断する（ステップＳ４４）。つまり、ａ0(0,0)、ａ0(1,0)、ａ0(2,0)、ａ0(3,0)、ａ0(4,0)、ａ0(0,1)、ａ0(1,1)、・・・ａ0(2,4)、ａ0(3,4)、ａ0(4,4)が、全て「非活性」であるかを判断する。なお、ｉ＝２、ｊ＝２から処理を開始したのは、ｉ＝２、ｊ＝２より小さい列行では、ステップＳ４４の処理が実行できないからである。
【００６６】
コンフィギュレーション・パターンＡ0のａ0(0,0)、ａ0(1,0)、ａ0(2,0)、ａ0(3,0)、ａ0(4,0)、ａ0(0,1)、ａ0(1,1)、・・・ａ0(2,4)、ａ0(3,4)、ａ0(4,4)が全て「非活性」であれば、この注目セルに対する処理は行わず、次のセルに対する処理に移る。つまり、二値化原画像においてこのような条件を満たすセルであれば、以降の各時点においてもステップＳ４５、Ｓ４６の処理は行わない。
【００６７】
一方、いずれかが「活性」であれば、ＣＰＵ１８は、注目セルの次の状態ａ1(2,2)を決定する処理を行う（ステップＳ４５）。
【００６８】
ＣＰＵ１８は、表１にしたがって次の状態ａ1(2,2)を決定する。
【００６９】
【表１】
0005202099.tif 000002
【００７０】
ここで、周囲セルからの入力は、図２Ｂに示すとおりである。周囲セルからの入力は、「抑制」（数値で表すと−１）、「興奮」（数値で表すと１）二つの値をとりうる。なお、時刻ｔ＝０においては、周囲セルからの入力は、全て一律に「抑制」に設定されている。
【００７１】
表１から明らかであるが、周囲セルからの入力の状態ｂ0(2,2)(0-1)、ｂ0(2,2)(1,-1)、ｂ0(2,2)(1,0)、ｂ0(2,2)(1,1)、ｂ0(2,2)(0,1)、ｂ0(2,2)(-1,1)、ｂ0(2,2)(-1,0)、ｂ0(2,2)(-1,1)のうち、「抑制」状態にあるものの数がしきい値Ｓ（たとえば４）以上の場合には、注目セルの現在の状態ａ0(2,2)を変更して次の状態ａ1(2,2)とする。つまり、「非活性」であれば「活性」に、「活性」であれば「非活性」にする。一方、周囲セルからの入力の状態のうち、「抑制」状態にあるものの数がしきい値Ｓ未満の場合には、注目セルの現在の状態ａ0(2,2)をそのまま維持して次の状態ａ1(2,2)とする。
【００７２】
ＣＰＵ１８は、決定した注目画素の次の状態ａ1(2,2)を、時刻ｔ＝１のためのコンフィギュレーション・バッファに記録する。
【００７３】
次に、ＣＰＵ１８は、注目セルの上下左右斜めにある８つの周囲セルに対して、時刻ｔ＝１に出力する内容を決定する（ステップＳ４６）。ＣＰＵ１８は、この決定を表２に示すようにして行う。
【００７４】
【表２】
0005202099.tif 000003
【００７５】
たとえば、図１４に示すように、列行ｉｊに位置する注目セルの右上に隣接する周囲セルに対する次の出力ｃt+1(i,j)(1,-1)は、当該右上のセルからの現在の入力ｂt(i,j)(1,-1)と注目セルの現在の状態ａt(i,j)とによって決定される。他の周囲セルについても同様である。ＣＰＵ１８は、このようにして決定した周囲セルへの次の出力をバッファＣt+1に記録する（図１５参照）。
【００７６】
次に、ＣＰＵ１８はｊを＋１して、ｉ＝２、ｊ＝３のセルを注目セルとし（ステップＳ４３）、ステップＳ４４以下を実行する。これにより、ｉ＝２、ｊ＝３のセルの次の状態ａ1(2,3)が決定され、ｔ＝１のコンフィギュレーション・バッファに記録される。また、周囲セルへの次の出力が算出されて図１５のバッファに記録される。
【００７７】
以上を繰り返して、右端（正確には右端から３番目）のセルまで繰り返すと、ＣＰＵ１８は、次に、ｉを＋１する。これにより、次の行のセルが注目セルとなる。以下、処理を繰り返すと、ｔ＝０のコンフィギュレーション・パターンの全てのセルについて上記の処理が終了する。
【００７８】
ＣＰＵ１８は、出力バッファＣt+1の内容に基づいて、図１６に示す入力バッファＢt+1を生成する（ステップＳ４７）。なお、入力バッファＢt+1は、出力するセルを中心として記述されていた出力バッファＣt+1の内容を、入力を受けるセルを中心として構成し直したものである。
【００７９】
以上のようにして、コンフィギュレーション・パターンＡ1が生成される。図３ａの上段にコンフィギュレーション・パターンＡ0（二値化原画像）を、図３ｃの上段にコンフィギュレーション・パターンＡ1を示す。
【００８０】
次に、ＣＰＵ１８は、時系列に蓄積されたコンフィギュレーション・パターンに基づいて一次フラグパターンの生成を実行する（図１１ａステップＳ５）。一次フラグパターンは、図４にて説明したように、図４Ａ〜図４Ｅのうち３つ以上の条件が満足されれば生成される。したがって、少なくとも、３つのコンフィギュレーション・パターンが蓄積されていなければ、一次フラグが生成されることはない。図３ａの中段・下段において一次フラグが生成されていないのはこのためである。
【００８１】
次に、ＣＰＵ１８は、時系列に蓄積された一次フラグパターンに基づいて二次フラグパターンの生成を実行する（図１１ａステップＳ６）。二次フラグパターンは、図６にて説明したように、図６Ａ〜図６Ｅのうち３つ以上の条件が満足されれば生成される。したがって、少なくとも、３つの一次フラグパターンが蓄積されていなければ、二次フラグが生成されることはない。図３ｂの上段・中段において二次フラグが生成されていないのはこのためである。
【００８２】
次に、ＣＰＵ１８は、二次フラグパターンに基づいて、線分の検出を実行する（図１１ａステップＳ７）。二次フラグが生成されていない段階では、線分が検出されることはない。図３ｂの下段において線分マークが生成されていないのはこのためである。
【００８３】
以上のようにして、時刻ｔ＝０に対する処理を終了すると、ＣＰＵ１８は、ステップＳ８（この処理については後述する）を経て、ステップＳ９に進み、ｔに１を加える。つまり、ｔ＝１とする。
【００８４】
ＣＰＵ１８は、ｔ＝１として、ステップＳ４以下の処理を再び実行する。コンフィギュレーションパターンの生成では、表１に基づいて各注目セルの次の状態ａ2を決定する。また、表２に基づいて各注目セルから周囲セルに対し次に出力する状態ｃ2を決定する。この時、ＣＰＵ１８は、図１２のステップＳ４７にて生成したバッファＢ1に基づいて、周囲セルからの入力ｂ1を参照する。
【００８５】
ｔ＝２におけるコンフィギュレーション・パターンＡ2は、図３ｅの上段に示すようになる。
【００８６】
図１１ａ、ｂの処理が繰り返されると、増加した各時刻ｔに対して、コンフィギュレーション・パターンＡ3Ａ4Ａ５が次々と生成され、バッファに記録されていく。
【００８７】
(2)一次フラグパターンＰＦの生成
ＣＰＵ１８は、上記のようにしてコンフィギュレーション・パターンＡ0Ａ1Ａ2・・・を生成し記録しつつ、一次フラグパターンの生成を行う（図１１ａステップＳ５）。一次フラグパターン生成の処理を、図１７に示す。
【００８８】
ＣＰＵ１８は、一次フラグ検出のための基準時点ｑを決定する。この実施形態では、現在のｔから２を減じた時点を基準時点ｑとしている。ＣＰＵ１８は、まず、基準時点ｑにおける注目セルが、下向き仮想線の一部であると推定できるかどうかを判断する（ステップＳ５１）。
【００８９】
図１７のステップＳ５１に示すように、ＣＰＵ１８は、基準時点ｑより２つ前の時点ｑ−２から、基準時点ｑより２つ後の時点ｑ＋２までのコンフィギュレーション・パターンＡq-2Ａq-1ＡqＡq+1Ａq+2について判断を行う。下向き仮想線の推定処理のフローチャートを図１８に示す。
【００９０】
ＣＰＵ１８は、まず、基準時点ｑのコンフィギュレーション・パターンＡqにおいてｉ＝２、ｊ＝２に位置するセルを注目セルとする（ステップＳ５１３）。次に、二値化原画像において注目セルを中心とする５×５のセルが全て「非活性」かどうかを判断する（ステップＳ５１４）。全て非活性なら、処理による有意な結果が得られる可能性が少ないので、この注目セルについての処理を行わない（図１２のステップＳ４４と同じ）。
【００９１】
いずれか一つでも「活性」であれば、ＣＰＵ１８は、ｍを−２から２まで１つずつ変化させて、ステップＳ５１７、Ｓ５１８を実行する。ｍ＝−２であれば、ステップＳ５１７において、コンフィギュレーション・パターンＡq-2 （つまり、基準時点ｑより２つ前のパターン）について、列ｉ、行ｊ−２に位置するセル（つまり、図１７のステップＳ５１のｑ−２において黒く塗りつぶしたセル）が、「活性」であるか否かを判断する。「活性」であれば、ＣＯＵＮＴに１を加える（ステップＳ５１８）。上記処理を、ｍを変えて実行することにより、コンフィギュレーション・パターンＡq-1 （つまり、基準時点ｑより１つ前のパターン）について、列ｉ、行ｊ−１に位置するセル（つまり、図１７のステップＳ５１のｑ−１において黒く塗りつぶしたセル）、・・・コンフィギュレーション・パターンＡq+2 （つまり、基準時点ｑより２つ後のパターン）について、列ｉ、行ｊ＋２に位置するセル（つまり、図１７のステップＳ５１のｑ＋２において黒く塗りつぶしたセル）が、「活性」であるか否かが判断され、ＣＯＵＮＴに活性と判断された数が記録されることになる。
【００９２】
ＣＰＵ１８は、ＣＯＵＮＴの数が所定のしきい値（ここでは３）以上であれば、時点ｑの一次フラグバッファの注目セルに下向きの一次フラグｐｆを記録する（ステップＳ５２１）。このように、一次フラグｐｆは、その仮想線の方向も併せて記録される。一次フラグはｐｆは、たとえば、図５のように一次フラグバッファＰＦqに記録される（なお、図５においては、右下の一次フラグが示されている）。
【００９３】
上記のようにして、一つの注目セルについての処理が終了すると、次のセルを注目セルとして同様の処理を行う。そして、全てのセルについて処理するまで、これを繰り返し、下向き仮想線の一次フラグ検出が終了する。
【００９４】
図１７のステップＳ５２〜Ｓ５８は、仮想線の向きが異なるだけであり、処理手法はステップＳ５１と同様である。
【００９５】
上記のようにして、一次フラグパターンＰＦqが生成される。図１１ａのステップＳ４〜Ｓ９の処理が繰り返され、ｔが増加していくと、時系列の一次フラグパターンＰＦq ＰＦq+1 ＰＦq+2 ・・・が生成され記録されることになる。一連の一次フラグパターンを、図３ｅ、図３ｇ・・・図３ｕの中段・下段に示す。
【００９６】
なお、上記では１つの時点に対して「活性」を検出すべきセルを１つとしている。しかし、１つの時点に対して複数の検出対象セルを設定し、いずれかのセルが「活性」であれば条件を満たすというようにしてもよい。たとえば、ｑ−２とｑ＋２において、図１７の×で示すセルも検出対象セルとすることができる。これによれば、わずかに傾きの異なる線も検出可能となる。
【００９７】
(3)二次フラグパターンＳＦの生成
ＣＰＵ１８は、上記のようにして一次フラグパターンＰＦ2ＰＦ3ＰＦ4・・・を生成し記録しつつ、二次フラグパターンＳＦの生成を行う（図１１ａステップＳ６）。
【００９８】
ＣＰＵ１８は、二次フラグ検出のための基準時ｒｑを決定する。この実施形態では、現在のｔから４を減じた時点を基準時点ｒとしている。ＣＰＵ１８は、まず、基準時点ｒにおける注目セルが、下向き仮想線の一部であると推定できるかどうかを判断する（ステップＳ６１）。同様に、他の向きの仮想線の一部であると推定できるかどうかも判断する（ステップＳ６２〜６８）。
【００９９】
二次フラグパターンＳＦ生成処理のフローチャートを図１９に示す。図１９から明らかなように、二次フラグｓｆの検出手法は、一次フラグｐｆの検出手法と同様である。ただし、二次フラグｓｆの検出においては、一次フラグの向きと、仮想線の向きとが一致しているかどうかも判断する点が異なっている。
【０１００】
図２０に、下向き仮想線の推定の処理フローチャートのうち、一次フラグ検出（図１８）と異なる点を示す。ステップＳ６１７ａにおいて、ＰＦr-m のｉ列ｊ＋ｍ行のセルに一次フラグが立っているかどうかを判断する。一次フラグが立っていれば、次に、そのフラグの向きと、仮想線の向き（ここでは下向き）が一致しているかどうかを判断する（ステップＳ６１７ｂ）。一致していれば、条件を満足するとして、ＣＯＵＮＴに１を加える（ステップＳ６１８）。したがって、二次フラグｓｆの検出においては、検出対象セルにフラグが立っていても、その方向が仮想線の方向と一致していなければ二次フラグは立たないことになる（図７の例を参照）。
【０１０１】
ＣＯＵＮＴがしきい値（ここでは３）を超えると、ＣＰＵ１８は、二次フラグバッファの注目セルに下向きの二次フラグを記録する（図１８のステップＳ５２１に対応する）。なお、一次フラグバッファは、時系列にて各基準時点ごとに設けられていたが、二次フラグバッファは１つでよく、各基準時点にて生成された二次フラグを次々と記録していけばよい。
【０１０２】
上記では、下向きの二次フラグ検出について説明したが、他の向きの二次フラグについての検出処理も同様である。
【０１０３】
図３ｊ、図３ｌ・・・図３ｖの上段・中段に、二次フラグバッファに記録された二次フラグパターンＳＦの変化を示す。なお、表示の都合上、これらの図では、その時刻に生成された新たな二次フラグのみを示している。
【０１０４】
(4)線分マークパターンの生成
ＣＰＵ１８は、上記のように二次フラグｓｆを時間経過とともに生成して二次フラグパターンＳＦを変化させつつ、線分マークパターンの検出処理を実行する（図１１ａステップＳ７）。
【０１０５】
ＣＰＵ１８は、記録された二次フラグパターンＳＦの各画素について、反対向きの二次フラグが立っているものを探し出す。たとえば、図９Ａにおいては、「左上向き」と「右下向き」の二次フラグがそろって記録されているセルが、５つある。ＣＰＵ１８は、これを検出すると、線分マークパターンバッファの当該セルに対して線分マークｒｌを記録する（図９Ｂ参照）。なお、この実施形態では、線分の方向も含めて線分マークｒｌが記録される。これによって、検出された線分が、いずれの方向の線の一部であるかを明確にすることができる。
【０１０６】
以上のようにして、時間経過とともに、線分マークパターンバッファに線分マークが記録されていき、線分パターンが生成されることになる。
【０１０７】
(5)処理ストップ
ＣＰＵ１８は、上記の処理を繰り返す中で、自らの判断により、処理を完了させるようにしている。これが、ステップＳ８の処理である。この実施形態では、時刻ｔ＝０からｔを増やしていき、初めて線分マークが検出された時点以降について、ステップＳ８の判断を行う。
【０１０８】
ステップＳ８では、今回の時点において新たに生成された線分マークの数を計数する。この数が、コンフィギュレーションパターンＡ0に含まれる活性セルの数（つまり、二値化原画像の黒画素の数）に対して、所定の割合（たとえば、１％など）より小さければ処理を終了する。これは、新たに生成される線分マークが少ないということは、概ね必要な線の検出は完了したと考えられるからである。
【０１０９】
なお、上記の条件を満たさない場合であっても、予め設定したｔの回数を繰り返した場合には終了する。
【０１１０】
(6)ノイズの除去
処理ストップ条件が満たされると、ＣＰＵ１８は、記録された線分マークパターンＲＬのノイズ除去処理を行う（ステップＳ１０）。この実施形態では、線分マークパターンＲＬの線分マークｒｌが記録された各セルについて、対応するコンフィギュレーション・パターンＡ0のセルが「活性」であるか否かを判断する。「活性」であれば、線分マークパターンＲＬの当該セルの線分マークｒｌはそのまま残す。対応するコンフィギュレーション・パターンＡ0のセルが「非活性」であれば、線分マークパターンＲＬの当該セルの線分マークｒｌを削除する。この場合、当該線分マークが対応する二値化原画像の画素は黒でないので、ノイズである可能性が高いからである。
【０１１１】
(7)結果の表示
ＣＰＵ１８は、ノイズ除去した線分マークパターンをハードディスク２０に記録するとともに、ディスプレイ１４に表示する（ステップＳ１１）。この際、ＣＰＵ１８は、たとえば、線分マークの方向によって、色を変えて表示するようにしてもよい。
【０１１２】
４．その他の実施形態
(1)上記実施形態においては、二次フラグに基づいて線分マークの検出を行っている。このようにしたのは、ノイズの生成を抑えるためである。しかし、画像の種類（縦横の線の多い画像など）によっては、二次フラグ検出を行わずに、一次フラグに基づいて線分マークの検出を行うようにしてもよい。また、三次フラグ（二次フラグに基づいて検出するフラグ）等を設け、これらに基づいて線分マークの検出を行うようにしてもよい。
【０１１３】
(2)上記実施形態では、一次フラグ、二次フラグの検出のために５つの時点のパターンを用いている。しかし、４つ以下、６つ以上のパターンに基づいて検出を行うようにしてもよい。また、一次フラグと二次フラグによって、検出に用いるパターンの数を変えてもよい。たとえば、一次フラグを５つの時点のコンフィギュレーションパターンによって検出し、二次フラグを３つの時点の一次フラグパターンによって検出するようにしてもよい。画像の種類によってこのようにすることにより、ノイズを抑えつつ処理の迅速化を図ることができる。
【０１１４】
(3)上記実施形態では、各処理の段階において、二値化原画像において注目画素の周りが「非活性」セルだけであるかどうかを判断し、処理を省略している（図１２のステップＳ４４など）。しかし、全ての処理に先立って、上記の条件を満たすセルを予め注目セルから外すようにしてもよい。
【０１１５】
(4)上記実施形態では、図１７に示すように、検出対象セルを５つの各時点ごとに一つとしている。しかし、５つの時点とも複数の検出対象セルを設定し、各時点において、複数の検出対象セルの全てが「活性」でなければ、条件を満足しないというようにすることもできる（あるいは、複数の検出対象セルの所定数以上が「活性」でなければ、条件を満足しないとしてもよい）。そして、条件を満足した時点の数がしきい値以上であれば、複数セルに（基準時点における検出対象セルの位置にフラグを立てる）一次フラグを立てるようにする。これによって、太さのある線を迅速に検出することができる。二次フラグについても同様である。
【０１１６】
(5)上記実施形態では、図６に示すようにして二次フラグの判定を行っている。しかし、図２１に示すように、対象セルを含む周囲のセル数個（ここでは９個）のうちいずれかに方向の合致する一次フラグがあれば条件を満足すると判断するようにしてもよい。そして、条件を満足するタイミングが、しきい値以上あれば、二次フラグを立てるようにする。
【０１１７】
特に、早いタイミングにて表れる一次フラグは線分検出において重要性が高いので、上記のようにしてできるだけ線分検出につなげることが好ましい。たとえば、ｔが所定の時刻（たとえばｔ＝１０）までは、図２１の手法によって二次フラグを検出し、それ以降は図６の手法によって二次フラグを検出するようにしてもよい、
(6)上記実施形態では、ステップＳ８のストップ条件として、二値化原画像の黒画素の数と、新たに検出された線分マークの数との比率を用いている。しかし、新たに検出された線分マーク数の変化の傾きを用いてもよい。
【０１１８】
(7)上記実施形態では、反対方向の二次フラグが立ったセルについて線分マークを記録している。しかし、一方向のみの二次フラグが立っているセルについて線分マークを記録するようにしてもよい。
【０１１９】
(8)上記実施形態では、二次元空間における画像について線分検出を行ったが、多次元空間についても同様にして線分検出を行うことができる。たとえば、三次元空間であれば、注目セルの周囲セルが２６個になり、仮想線の向きが２４個に増えるものの、基本的な処理内容は同じである。
【０１２０】
(9)上記実施形態では、元の画像の黒部分を活性状態、白部分を非活性状態として検出を行ったが、元の画像の白部分を活性状態、黒部分を非活性状態としてもよい。
【０１２１】
(10)上記実施形態では、線分マークパターンバッファの各セルに、検出された線分マークを次々と記録しておくようにしている。したがって、１つのセルにおいて、複数の方向の線分マークが記録される場合もあることになる。しかし、既に線分マークが記録されたセルに対しては、それ以上、線分マークを記録しないようにしてもよい。
【０１２２】
(11)上記実施形態では、８つの周囲セルからの入力を受けて注目セルの状態を決定するようにしている。しかし、特定の周囲セルだけに着目して注目セルの状態を決定してもよく、任意の数のセルからの入力に着目して注目セルの状態を決定するようにしてもよい。
【０１２３】
(12)上記実施形態では、出力先の周囲セル一つの状態に着目して、当該周囲セルに対する出力を決定するようにしている。しかし、他の周囲セルの状態も考慮してもよい。
【０１２４】
(13)上記実施形態では、注目セルの現在の状態と、周囲セルから受けた入力の状態とに基づいて、注目セルの次の状態を算出するようにしており、周囲セルからの入力は、注目セルが当該周囲セルに対して出力した現在の状態と、当該周囲セルの現在の状態とに基づいて決定される。
【０１２５】
しかし、周囲セルからの入力は、周囲セルの現在の状態そのものとしてもよい。つまり、伝統的なセルラオートマトンを用いるようにしてもよい。
【０１２６】
(14)上記実施形態では、ソフトウエアを用いて図１の機能を実現したが、その一部または全部をハードウエアによって実現するようにしてもよい。
【０１２７】
５．実施例
上記実施形態による線分抽出プログラムを用いて、画像から線分を抽出する処理を行った例を、図２２〜図２５に示す。図２２Ａは元の画像を、図２２Ｂは元の画像を二値化処理した画像を、図２２Ｃは線分抽出結果を示す。図２３、図２４、図２５においても同様である。ＣＰＵとしてCentrino（商標）Duo(クロック周波数1.8GHz）を使用したパーソナルコンピュータを用いた。線分抽出プログラムの処理は、上述の実施形態のとおりのものを用いた。ただし、二次フラグの検出処理において、ｔ＝１０までは図２１に示す検出方法にて行い、ｔ＝１１以降は、図６に示す検出方法にて行った。
【０１２８】
図２６の上段に、図２４Ｂの二値化画像を再掲する。中段左は、この二値化画像の一を拡大して示すものである。中段右は、上記実施形態にしたがって線分検出を行った結果につき、前記拡大部分に対応する線分マークを示したものである。下段は、中段右の線分マークを、更に拡大して示したものである。下段の図から明らかなように、線分の有無および方向が検出されている。
【０１２９】
図２５から分かるように、極めて細い線（空間周波数の高い線）であっても、適切に検出可能であることが分かった。
【図面の簡単な説明】
【０１３０】
【図１】この発明の一実施形態による線分検出装置の機能ブロック図である。
【図２】図２Ａは原画像を示し、図２Ｂは周囲セルからの入力を示す図である。
【図３ａ】ｔ＝０における、コンフィギュレーションパターン（原画像）、一次フラグパターンＰＦを示す図である。
【図３ｂ】ｔ＝０における、二次フラグパターンＳＦ、線分マーカパターンを示す図である。
【図３ｃ】ｔ＝１における、コンフィギュレーションパターン（原画像）、一次フラグパターンＰＦを示す図である。
【図３ｄ】ｔ＝１における、二次フラグパターンＳＦ、線分マーカパターンを示す図である。
【図３ｅ】ｔ＝２における、コンフィギュレーションパターン（原画像）、一次フラグパターンＰＦを示す図である。
【図３ｆ】ｔ＝２における、二次フラグパターンＳＦ、線分マーカパターンを示す図である。
【図３ｇ】ｔ＝３における、コンフィギュレーションパターン（原画像）、一次フラグパターンＰＦを示す図である。
【図３ｈ】ｔ＝３における、二次フラグパターンＳＦ、線分マーカパターンを示す図である。
【図３ｉ】ｔ＝４における、コンフィギュレーションパターン（原画像）、一次フラグパターンＰＦを示す図である。
【図３ｊ】ｔ＝４における、二次フラグパターンＳＦ、線分マーカパターンを示す図である。
【図３ｋ】ｔ＝５における、コンフィギュレーションパターン（原画像）、一次フラグパターンＰＦを示す図である。
【図３ｌ】ｔ＝５における、二次フラグパターンＳＦ、線分マーカパターンを示す図である。
【図３ｍ】ｔ＝６における、コンフィギュレーションパターン（原画像）、一次フラグパターンＰＦを示す図である。
【図３ｎ】ｔ＝６における、二次フラグパターンＳＦ、線分マーカパターンを示す図である。
【図３ｏ】ｔ＝７における、コンフィギュレーションパターン（原画像）、一次フラグパターンＰＦを示す図である。
【図３ｐ】ｔ＝７における、二次フラグパターンＳＦ、線分マーカパターンを示す図である。
【図３ｑ】ｔ＝８における、コンフィギュレーションパターン（原画像）、一次フラグパターンＰＦを示す図である。
【図３ｒ】ｔ＝８における、二次フラグパターンＳＦ、線分マーカパターンを示す図である。
【図３ｓ】ｔ＝９における、コンフィギュレーションパターン（原画像）、一次フラグパターンＰＦを示す図である。
【図３ｔ】ｔ＝９における、二次フラグパターンＳＦ、線分マーカパターンを示す図である。
【図３ｕ】ｔ＝１０における、コンフィギュレーションパターン（原画像）、一次フラグパターンＰＦを示す図である。
【図３ｖ】ｔ＝１０における、二次フラグパターンＳＦ、線分マーカパターンを示す図である。
【図４】一次フラグの検出処理を説明するための図である。
【図５】一次フラグの記録例を示す図である。
【図６】二次フラグの検出処理を説明するための図である。
【図７】二次フラグの検出処理を説明するための図である。
【図８】二次フラグの記録例を示す図である。
【図９】線分マーカフラグの検出処理を説明するための図である。
【図１０】一実施形態による線分抽出装置をＣＰＵを用いて実現した場合のハードウエア構成である。
【図１１ａ】線分抽出プログラムのフローチャートである。
【図１１ｂ】線分抽出プログラムのフローチャートである。
【図１２】コンフィギュレーションパターン生成処理のフローチャートである。
【図１３】原画像の状態に基づく処理の省略を説明するための図である。
【図１４】周囲セルへの出力の算出を示す図である。
【図１５】周囲セルへの出力を一次記憶するバッファの内容を示す図である。
【図１６】周囲セルからの入力を一次記憶するバッファの内容を示す図である。
【図１７】一次フラグパターンＰＦ生成処理のフローチャートである。
【図１８】下向き仮想線に関する一次フラグの生成処理のフローチャートである。
【図１９】二次フラグパターンＰＦ生成処理のフローチャートである。
【図２０】下向き仮想線に関する二次フラグの生成処理のフローチャートである。
【図２１】二次フラグ検出処理の他の例を示す図である。
【図２２】本発明の一実施形態による線分抽出プログラムによって線分を抽出した結果を示す図である。
【図２３】本発明の一実施形態による線分抽出プログラムによって線分を抽出した結果を示す図である。
【図２４】本発明の一実施形態による線分抽出プログラムによって線分を抽出した結果を示す図である。
【図２５】本発明の一実施形態による線分抽出プログラムによって線分を抽出した結果を示す図である。
【図２６】線分抽出された結果を詳しく示す図である。
【符号の説明】
【０１３１】
２・・・パターン生成手段
４・・・一次検出手段
６・・・二次検出手段
８・・・線分検出手段
【図１】
0005202099.tif 000004
【図２】
0005202099.tif 000005
【図３ａ】
0005202099.tif 000006
【図３ｂ】
0005202099.tif 000007
【図３ｃ】
0005202099.tif 000008
【図３ｄ】
0005202099.tif 000009
【図３ｅ】
0005202099.tif 000010
【図３ｆ】
0005202099.tif 000011
【図３ｇ】
0005202099.tif 000012
【図３ｈ】
0005202099.tif 000013
【図３ｉ】
0005202099.tif 000014
【図３ｊ】
0005202099.tif 000015
【図３ｋ】
0005202099.tif 000016
【図３ｌ】
0005202099.tif 000017
【図３ｍ】
0005202099.tif 000018
【図３ｎ】
0005202099.tif 000019
【図３ｏ】
0005202099.tif 000020
【図３ｐ】
0005202099.tif 000021
【図３ｑ】
0005202099.tif 000022
【図３ｒ】
0005202099.tif 000023
【図３ｓ】
0005202099.tif 000024
【図３ｔ】
0005202099.tif 000025
【図３ｕ】
0005202099.tif 000026
【図３ｖ】
0005202099.tif 000027
【図４】
0005202099.tif 000028
【図５】
0005202099.tif 000029
【図６】
0005202099.tif 000030
【図７】
0005202099.tif 000031
【図８】
0005202099.tif 000032
【図９】
0005202099.tif 000033
【図１０】
0005202099.tif 000034
【図１１ａ】
0005202099.tif 000035
【図１１ｂ】
0005202099.tif 000036
【図１２】
0005202099.tif 000037
【図１３】
0005202099.tif 000038
【図１４】
0005202099.tif 000039
【図１５】
0005202099.tif 000040
【図１６】
0005202099.tif 000041
【図１７】
0005202099.tif 000042
【図１８】
0005202099.tif 000043
【図１９】
0005202099.tif 000044
【図２０】
0005202099.tif 000045
【図２１】
0005202099.tif 000046
【図２２】
0005202099.tif 000047
【図２３】
0005202099.tif 000048
【図２４】
0005202099.tif 000049
【図２５】
0005202099.tif 000050
【図２６】
0005202099.tif 000051