(57)【特許請求の範囲】
【請求項１】
対象画像から線分を検出する画像処理装置において、
対象画像を二次元フーリエ変換する二次元フーリエ変換手段と、
二次元フーリエ変換後の対象画像における直線の傾きを検出して前記線分の傾きを推定する傾き推定手段と、
前記直線の各点の値を抽出する直線データ抽出手段と、
前記直線の各点の値を一次元逆フーリエ変換する一次元逆フーリエ変換手段と、
前記一次元逆フーリエ変換手段により変換されたデータより前記対象画像における線分の切片を推定する切片推定手段と、
前記対象画像、前記線分の傾きおよび前記線分の切片に基づいて前記線分の端点を推定する端点推定手段と
を備えることを特徴とする画像処理装置。
【請求項２】
対象画像から線分を検出する画像処理装置において、
対象画像を二次元フーリエ変換する二次元フーリエ変換手段と、
二次元フーリエ変換後の対象画像における直線の傾きを検出して前記線分の傾きを推定する傾き推定手段と、
前記二次元フーリエ変換後の対象画像における直線の各点の値を抽出する第１の直線データ抽出手段と、
前記二次元フーリエ変換後の対象画像における直線の各点の値を一次元逆フーリエ変換する一次元逆フーリエ変換手段と、
前記一次元逆フーリエ変換手段により変換されたデータより前記対象画像における線分の切片を推定する切片推定手段と、
前記線分の傾きおよび前記線分の切片に基づいて前記対象画像における直線の各点の値を抽出する第２の直線データ抽出手段と、
前記対象画像における直線の各点の値を一次元フーリエ変換する一次元フーリエ変換手段と、
前記一次元フーリエ変換手段により変換されたデータに基づいて前記対象画像における線分の端点を推定する端点推定手段と
を備えることを特徴とする画像処理装置。
【請求項３】
一次元フーリエ変換手段により変換されたデータに基づいて対象画像における線分の長さを推定する長さ推定手段を備え、
端点推定手段は、前記一次元フーリエ変換手段により変換されたデータおよび前記長さ推定手段により推定された前記線分の長さに基づいて前記対象画像における線分の端点を推定する
ことを特徴とする請求項２記載の画像処理装置。
【請求項４】
二次元フーリエ変換後の対象画像における線分の長さを推定する長さ推定手段を備え、
端点推定手段は、前記長さ推定手段により推定された前記線分の長さに基づいて前記対象画像における線分の端点を推定する
ことを特徴とする請求項１または請求項２記載の画像処理装置。
【請求項５】
所定の画像特性に基づいて対象画像に線分が存在する可能性があるか否かを判定する線分存在判定手段を備え、
前記線分存在判定手段により前記対象画像に線分が存在する可能性があると判定された場合のみ線分の傾き、切片および端点を推定する
ことを特徴とする請求項１から請求項４のうちのいずれか１項記載の画像処理装置。
【請求項６】
対象画像を所定の数の分割画像に分割する画像分割手段を備え、
各分割画像をそれぞれ前記対象画像として線分検出処理を行う
ことを特徴とする請求項１から請求項５のうちのいずれか１項記載の画像処理装置。
【請求項７】
対象画像を分割画像に分割する際の前記分割画像の数と大きさを設定する分割方法決定手段を備える
ことを特徴とする請求項６記載の画像処理装置。
【請求項８】
分割方法を入力する分割方法入力手段と、前記分割方法設定手段により設定された前記分割方法に基づいて対象画像を分割画像に分割する際の前記分割画像の数と大きさを設定する条件付分割方法決定手段とを備える
ことを特徴とする請求項６記載の画像処理装置。
【請求項９】
複数の線分として検出された線分を１つの線分に統合する線分統合手段を備える
ことを特徴とする請求項１から請求項８のうちのいずれか１項記載の画像処理装置。
【請求項１０】
対象画像を二値化する画像二値化手段を備え、
二値化後の対象画像に対して線分検出処理を行う
ことを特徴とする請求項１から請求項９のうちのいずれか１項記載の画像処理装置。
【請求項１１】
対象画像から線分を検出する画像処理方法において、
二次元フーリエ変換手段により、対象画像を二次元フーリエ変換するステップと、
傾き推定手段により、二次元フーリエ変換後の対象画像における直線の傾きを検出して前記線分の傾きを推定するステップと、
直線データ抽出手段により、前記直線の各点の値を抽出するステップと、
一次元逆フーリエ変換手段により、抽出した前記直線の各点の値を一次元逆フーリエ変換するステップと、
切片推定手段により、前記一次元逆フーリエ変換により変換されたデータより前記対象画像における線分の切片を推定するステップと、
端点推定手段により、前記対象画像、前記線分の傾きおよび前記線分の切片に基づいて前記線分の端点を推定するステップと
を備えることを特徴とする画像処理方法。
【請求項１２】
対象画像から線分を検出する画像処理方法において、
二次元フーリエ変換手段により、対象画像を二次元フーリエ変換するステップと、
傾き推定手段により、二次元フーリエ変換後の対象画像における直線の傾きを検出して前記線分の傾きを推定するステップと、
第１の直線データ抽出手段により、前記二次元フーリエ変換後の対象画像における直線の各点の値を抽出するステップと、
一次元逆フーリエ変換手段により、前記二次元フーリエ変換後の対象画像における直線の各点の値を一次元逆フーリエ変換するステップと、
切片推定手段により、一次元逆フーリエ変換後のデータより前記対象画像における線分の切片を推定するステップと、
第２の直線データ抽出手段により、前記線分の傾きおよび前記線分の切片に基づいて前記対象画像における直線の各点の値を抽出するステップと、
一次元フーリエ変換手段により、前記対象画像における直線の各点の値を一次元フーリエ変換するステップと、
端点推定手段により、一次元フーリエ変換後のデータに基づいて前記対象画像における線分の端点を推定するステップと
を備えることを特徴とする画像処理方法。
【請求項１３】
長さ推定手段により、一次元フーリエ変換後のデータに基づいて対象画像における線分の長さを推定するステップを備え、
端点推定手段により、前記一次元フーリエ変換後のデータおよび推定した前記線分の長さに基づいて前記対象画像における線分の端点を推定する
ことを特徴とする請求項１２記載の画像処理方法。
【請求項１４】
長さ推定手段により、二次元フーリエ変換後の対象画像における線分の長さを推定するステップを備え、
端点推定手段により、推定した前記線分の長さに基づいて前記対象画像における線分の端点を推定する
ことを特徴とする請求項１１または請求項１２記載の画像処理方法。
【請求項１５】
線分存在判定手段により、所定の画像特性に基づいて対象画像に線分が存在する可能性があるか否かを判定するステップを備え、
前記対象画像に線分が存在する可能性があると判定された場合のみ線分の傾き、切片および端点を推定する
ことを特徴とする請求項１１から請求項１４のうちのいずれか１項記載の画像処理方法。
【請求項１６】
画像分割手段により、対象画像を所定の数の分割画像に分割するステップを備え、
各分割画像をそれぞれ前記対象画像として線分検出処理を行う
ことを特徴とする請求項１１から請求項１５のうちのいずれか１項記載の画像処理方法。
【請求項１７】
分割方法決定手段により、対象画像を分割画像に分割する際の前記分割画像の数と大きさを設定するステップを備える
ことを特徴とする請求項１６記載の画像処理方法。
【請求項１８】
分割方法入力手段により、分割方法を入力するステップと、
条件付分割方法決定手段により、設定した前記分割方法に基づいて対象画像を分割画像に分割する際の前記分割画像の数と大きさを設定するステップとを備える
ことを特徴とする請求項１６記載の画像処理方法。
【請求項１９】
線分統合手段により、複数の線分として検出された線分を１つの線分に統合するステップを備える
ことを特徴とする請求項１１から請求項１８のうちのいずれか１項記載の画像処理方法。
【請求項２０】
画像二値化手段により、対象画像を二値化するステップを備え、
二値化後の対象画像に対して線分検出処理を行う
ことを特徴とする請求項１１から請求項１９のうちのいずれか１項記載の画像処理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は対象画像に含まれている線分の傾き、切片および端点を推定して線分を検出する画像処理装置および画像処理方法に関するものである。
【０００２】
【従来の技術】
図３０は従来の画像処理装置の構成を示すブロック図である。この従来の画像処理装置は、例えば「Ｌｏｃａｌｉｚｅｄ  Ｒａｄｏｎ  Ｔｒａｎｓｆｏｒｍ−Ｂａｓｅｄ  Ｄｅｔｅｃｔｉｏｎ  ｏｆ  Ｓｈｉｐ  Ｗａｋｅｓ  ｉｎ  ＳＡＲＩｍａｇｅｓ」（Ｃｏｐｅｌａｎｄら著、ＩＥＥＥ  Ｔｒａｎｓ．  Ｇｅｏｓｃｉ．  Ｒｅｍｏｔｅ  Ｓｅｎｓｉｎｇ、ＶＯＬ．３３、ＮＯ.１、第３５頁〜第４５頁、１９９５年１月）、「二次元フーリエ変換を用いたＩＳＡＲ運動補償方式」（山本ら著、信学技報ＳＡＮＥ９７−７０、１９９７年１０月）、および特開平６−３４５６３号公報に記載の技術に基づいて、実平面上の対象画像をフーリエ変換し、フーリエ平面上で直線の傾きから対象画像の傾きを推定し、また実平面上で切片と端点を推定して線分を検出するものである。
【０００３】
なお、対象画像を含むｘ軸およびｙ軸で張られる平面を実平面と呼び、対象画像をフーリエ変換した画像を変換画像と呼び、変換画像を含むｆｘ軸およびｆｙ軸で張られる平面をフーリエ平面と呼ぶ。
【０００４】
また、線分の傾きは実平面上での線分の傾きであり、線分の切片は線分を延長して座標軸に交わる点でのその座標値である。線分の端点は線分の両端の点であるが、線分の長さを所定の長さと仮定した場合には、端点はいずれか一方の端点、例えばｘ軸の値が小さいほうの端点とする。これらの傾き、切片および端点の３つのパラメータが推定されると、線分が一意に特定される。なお、実平面における直線は線分の拡張と考えることができる。
【０００５】
図３０において、１０１は対象画像のデータを供給され、その対象画像内の線分を検出する検出処理部であり、１０２は検出処理部１０１により検出された線分のデータ（線分の傾き、切片および端点のデータ）を格納する線分データ格納手段である。
【０００６】
検出処理部１０１において、１１１は対象画像を二次元フーリエ変換する二次元フーリエ変換手段であり、１１２は対象画像内の線分に対応するフーリエ平面での直線の傾き（−１／α）を検出して対象画像内の線分の傾きαを推定する傾き推定手段であり、１１３は対象画像におけるすべての線分を検出するように各部を制御する検出処理制御手段であり、１１４は傾き推定手段１１２による傾きデータと実平面上の対象画像のデータから線分の切片および端点を推定する切片／端点推定手段である。
【０００７】
なお、対象画像のデータは、原画像の大きさ、各画素の濃度値を含む配列データであり、フーリエ変換後の対象画像のデータである空間周波数データは、変換画像の大きさ、各画素における濃度値を含む配列データである。
【０００８】
また、一つの画像中に複数本の線分が存在することが考えられることから、各線分には番号または識別子が付される。そして各線分の傾き、切片および端点のデータは、その線分固有の番号または識別子に関連づけられる。以下、線分の番号に関連づけられた、傾きの値、切片の座標および端点の座標からなるデータを線分データと呼ぶ。
【０００９】
次に動作について説明する。
図３１は従来の画像処理装置の動作について説明するフローチャートであり、図３２は実平面上の線分の一例を示す図であり、図３３は実平面上の線分を二次元フーリエ変換したフーリエ平面上の直線の一例を示す図である。
【００１０】
まずステップＳＴ２０１において、検出処理部１０１の二次元フーリエ変換手段１１１は、対象画像のデータを供給されると、二次元フーリエ変換を実行し、生成したフーリエ平面上の空間周波数データ、すなわち変換画像のデータを傾き推定手段１１２に供給する。
【００１１】
このとき、図３２に示すように、実平面上において濃度値が一定値ｃであり、傾き、ｙ軸切片および端点のｘ座標がそれぞれα、βおよびｘｓである線分（ｃ×δ（ｙ−αｘ＋β）、ただしδ（）はＤｉｒａｃのデルタ関数）を含む直線を二次元フーリエ変換すると、変換後のフーリエ平面での直線Ｆ（ｆｘ，ｆｙ）は、式（１）に示すようになる。
【数１】
0003907905.tif 000002
【００１２】
図３３に示すように、実平面上の直線は、二次元フーリエ変換によりフーリエ平面上で原点を通る傾き（−１／α）の直線に変換されるため、フーリエ平面上の直線の傾き（−１／α）から実平面上の直線の傾きαを計算することができる。したがって傾き推定手段１１２は、ステップＳＴ２０２において、変換画像のデータから線分の傾きαを推定する。
【００１３】
傾き推定手段１１２は、例えばフーリエ平面上で、傾きが０ラジアンからπラジアンまでの原点を通る直線に沿って変換画像を線積分し、その積分値が最大値となったときの傾きをフーリエ平面上での傾き（−１／α）とし、その傾き（−１／α）から実平面上での線分の傾きαを計算する。あるいは、傾き推定手段１１２は各線積分の値に対して閾値処理を行ったり、角度ごとのパターンマッチングを行うことによりフーリエ平面上での傾き（−１／α）を求め、その傾き（−１／α）から実平面上での線分の傾きαを計算する。なお線積分の値は、対象とする線に対応する画素の濃度値の総和としてもよい。
【００１４】
なお、対象画像において線分が存在する場合には、変換画像上で原点を通る直線が少なくとも１本現れるが、存在しない場合には１本も現れない。さらに対象画像において傾きの異なる複数の線分が存在する場合には、複数の直線が変換画像に現れる。この場合、傾き推定手段１１２は、各線分に番号を付す。そして傾き推定手段１１２は、線分の傾きαを切片／端点推定手段１１４に供給するとともに線分データ格納手段１０２に格納させ、線分の本数Ｎを検出処理制御手段１１３に供給する。
【００１５】
検出処理制御手段１１３は、線分の本数Ｎまたは後述の１サイクル終了信号を受け取ると、ステップＳＴ２０３において、未処理の線分の本数ｐがゼロであるか否かを判断する。なお、未処理の線分の本数ｐの初期値は、検出された線分の本数Ｎとする。
【００１６】
検出処理制御手段１１３は、未処理の線分の本数ｐがゼロである場合には、検出終了信号を線分データ格納手段１０２に供給し、線分検出処理を終了する。一方、未処理の線分の本数ｐがゼロではない場合、検出処理制御手段１１３は、ステップＳＴ２０４において未処理の線分の本数ｐを１だけ減算し、次に処理する線分を指定する処理継続信号を切片／端点推定手段１１４に供給する。
【００１７】
切片／端点推定手段１１４は、処理継続信号を受け取ると、対象画像のデータと傾きαから、処理継続信号により指定される線分の切片および端点を推定する。このとき切片／端点推定手段１１４は、傾きαの、実平面上のすべての線分について線積分し、その積分値が最大である場合またはその積分値が所定の閾値を超えた場合に、その場合の線分の切片および端点を処理継続信号により指定される線分の切片および端点と推定し、線分データ格納手段１０２に供給する。
【００１８】
そして線分データ格納手段１０２は、ステップＳＴ２０６において、推定された傾き、切片および端点を線分の番号ごとに格納して、その後に、１サイクル終了信号を検出処理制御手段１１３に供給する。
【００１９】
以下、ステップＳＴ２０３からステップＳＴ２０６までの処理を、未処理の線分の本数ｐがゼロになるまで繰り返す。そして検出終了信号が供給されると、線分データ格納手段１０２は、格納している線分データを出力する。なお、線分が検出されなかった場合には、線分データとしてゼロまたは空が出力される。
【００２０】
なお、その他の従来の関連する技術としては、特開昭５９−１８８７４２号公報、特開平８−１２３９６５号公報、特開平１０−４９６８８号公報、特開平１０−１１６３４５号公報、特開平１０−１７１９９６号公報などに記載のものがある。
【００２１】
【発明が解決しようとする課題】
従来の画像処理装置および画像処理方法は以上のように構成されているので、フーリエ平面上で線分の傾きを検出した後、実平面上でのすべての線分についての切片と端点という２つのパラメータによる二次元空間で、実平面上に含まれる線分の切片と端点を探索しなければならず、実平面上に含まれる線分の切片と端点を迅速に推定することが困難であるなどの課題があった。
【００２２】
また、従来の画像処理装置および画像処理方法は以上のように構成されているので、線分の傾きのみに基づいて線分を探索した場合、対象画像上に同じ傾きの複数の線分を識別することが困難であるという課題があった。
【００２３】
さらに、従来の画像処理装置および画像処理方法は以上のように構成されているので、線分の切片、端点および線分の長さなどの情報を個別的に得ることが困難であるなどの課題があった。
【００２４】
この発明は上記のような課題を解決するためになされたもので、線分の傾き、切片および端点の３つのパラメータを各々独立に一次元空間で探索し、推定するようにして、線分の識別および線分検出を高速に実行することができる画像処理装置および画像処理方法を得ることを目的とする。
【００２５】
また、線分の傾き、切片および端点の３つのパラメータの他に線分の長さを推定することができる画像処理装置および画像処理方法を得ることを目的とする。
【００２６】
さらに、線分検出手法の種類や対象画像の特徴などに応じて、対象画像およびその対象画像を所定の方式で変換したデータのうちのいずれかに適したものから線分の各パラメータを適宜推定するようにして、処理すべきデータ量や処理時間などの観点から効率的に線分を検出することができる画像処理装置および画像処理方法を得ることを目的とする。
【００２７】
【課題を解決するための手段】
この発明に係る画像処理装置は、対象画像を二次元フーリエ変換する二次元フーリエ変換手段と、二次元フーリエ変換後の対象画像における直線の傾きを検出して線分の傾きを推定する傾き推定手段と、その直線の各点の値を抽出する直線データ抽出手段と、その直線の各点の値を一次元逆フーリエ変換する一次元逆フーリエ変換手段と、一次元逆フーリエ変換手段により変換されたデータより対象画像における線分の切片を推定する切片推定手段と、対象画像、線分の傾きおよび線分の切片に基づいて線分の端点を推定する端点推定手段とを備えるものである。
【００２８】
この発明に係る画像処理装置は、対象画像を二次元フーリエ変換する二次元フーリエ変換手段と、二次元フーリエ変換後の対象画像における直線の傾きを検出して線分の傾きを推定する傾き推定手段と、その直線の各点の値を抽出する第１の直線データ抽出手段と、その直線の各点の値を一次元逆フーリエ変換する一次元逆フーリエ変換手段と、一次元逆フーリエ変換手段により変換されたデータより対象画像における線分の切片を推定する切片推定手段と、線分の傾きおよび線分の切片に基づいて対象画像における直線の各点の値を抽出する第２の直線データ抽出手段と、その直線の各点の値を一次元フーリエ変換する一次元フーリエ変換手段と、一次元フーリエ変換手段により変換されたデータに基づいて対象画像における線分の端点を推定する端点推定手段とを備えるものである。
【００２９】
この発明に係る画像処理装置は、一次元フーリエ変換手段により変換されたデータに基づいて対象画像における線分の長さを推定する長さ推定手段を備え、一次元フーリエ変換手段により変換されたデータおよび長さ推定手段により推定された線分の長さに基づいて対象画像における線分の端点を推定するようにしたものである。
【００３０】
この発明に係る画像処理装置は、二次元フーリエ変換後の対象画像における線分の長さを推定する長さ推定手段を備え、長さ推定手段により推定された線分の長さに基づいて対象画像における線分の端点を推定するようにしたものである。
【００３１】
この発明に係る画像処理装置は、所定の画像特性に基づいて対象画像に線分が存在する可能性があるか否かを判定する線分存在判定手段を備え、線分存在判定手段により対象画像に線分が存在する可能性があると判定された場合のみ線分の傾き、切片および端点を推定するようにしたものである。
【００３２】
この発明に係る画像処理装置は、所定の画像特性に基づいて対象画像に線分が存在する可能性があるか否かを判定する線分存在判定手段と、線分存在判定手段により対象画像に線分が存在する可能性があると判定された場合のみ対象画像から線分を検出する検出処理部とを備えるものである。
【００３３】
この発明に係る画像処理装置は、対象画像を二次元フーリエ変換する二次元フーリエ変換手段と、二次元フーリエ変換後の対象画像における直線の傾きを検出して線分の傾きを推定する傾き推定手段と、対象画像および線分の傾きに基づいて線分の端点を推定する端点推定手段とを、線分存在判定手段により対象画像に線分が存在する可能性があると判定された場合のみ線分を検出する検出処理部に備えるものである。
【００３４】
この発明に係る画像処理装置は、対象画像を所定の数の分割画像に分割する画像分割手段を備え、各分割画像をそれぞれ対象画像として線分検出処理を行うようにしたものである。
【００３５】
この発明に係る画像処理装置は、対象画像を分割画像に分割する際の分割画像の数と大きさを設定する分割方法決定手段を備えるものである。
【００３６】
この発明に係る画像処理装置は、分割方法を入力する分割方法入力手段と、分割方法設定手段により設定された分割方法に基づいて対象画像を分割画像に分割する際の分割画像の数と大きさを設定する条件付分割方法決定手段とを備えるものである。
【００３７】
この発明に係る画像処理装置は、複数の線分として検出された線分を１つの線分に統合する線分統合手段を備えるものである。
【００３８】
この発明に係る画像処理装置は、対象画像を二値化する画像二値化手段を備え、二値化後の対象画像に対して線分検出処理を行うようにしたものである。
【００３９】
この発明に係る画像処理方法は、対象画像を二次元フーリエ変換するステップと、二次元フーリエ変換後の対象画像における直線の傾きを検出して線分の傾きを推定するステップと、その直線の各点の値を抽出するステップと、抽出した直線の各点の値を一次元逆フーリエ変換するステップと、一次元逆フーリエ変換により変換されたデータより対象画像における線分の切片を推定するステップと、対象画像、線分の傾きおよび線分の切片に基づいて線分の端点を推定するステップとを備えるものである。
【００４０】
この発明に係る画像処理方法は、対象画像を二次元フーリエ変換するステップと、二次元フーリエ変換後の対象画像における直線の傾きを検出して線分の傾きを推定するステップと、その直線の各点の値を抽出するステップと、その直線の各点の値を一次元逆フーリエ変換するステップと、一次元逆フーリエ変換後のデータより対象画像における線分の切片を推定するステップと、線分の傾きおよび線分の切片に基づいて対象画像における直線の各点の値を抽出するステップと、その直線の各点の値を一次元フーリエ変換するステップと、一次元フーリエ変換後のデータに基づいて対象画像における線分の端点を推定するステップとを備えるものである。
【００４１】
この発明に係る画像処理方法は、一次元フーリエ変換後のデータに基づいて対象画像における線分の長さを推定するステップを備え、一次元フーリエ変換後のデータおよび推定した線分の長さに基づいて対象画像における線分の端点を推定するようにしたものである。
【００４２】
この発明に係る画像処理方法は、二次元フーリエ変換後の対象画像における線分の長さを推定するステップを備え、推定した線分の長さに基づいて対象画像における線分の端点を推定するようにしたものである。
【００４３】
この発明に係る画像処理方法は、所定の画像特性に基づいて対象画像に線分が存在する可能性があるか否かを判定するステップを備え、対象画像に線分が存在する可能性があると判定された場合のみ線分の傾き、切片および端点を推定するようにしたものである。
【００４４】
この発明に係る画像処理方法は、所定の画像特性に基づいて対象画像に線分が存在する可能性があるか否かを判定するステップと、対象画像に線分が存在する可能性があると判定された場合のみ対象画像から線分を検出するステップとを備えるものである。
【００４５】
この発明に係る画像処理方法は、対象画像に線分が存在する可能性があると判定された場合のみ、対象画像を二次元フーリエ変換し、二次元フーリエ変換後の対象画像における直線の傾きを検出して線分の傾きを推定し、対象画像および線分の傾きに基づいて線分の端点を推定して線分を検出するようにしたものである。
【００４６】
この発明に係る画像処理方法は、対象画像を所定の数の分割画像に分割するステップを備え、各分割画像をそれぞれ対象画像として線分検出処理を行うようにしたものである。
【００４７】
この発明に係る画像処理方法は、対象画像を分割画像に分割する際の分割画像の数と大きさを設定するステップを備えるものである。
【００４８】
この発明に係る画像処理方法は、分割方法を入力するステップと、設定した分割方法に基づいて対象画像を分割画像に分割する際の分割画像の数と大きさを設定するステップとを備えるものである。
【００４９】
この発明に係る画像処理方法は、複数の線分として検出された線分を１つの線分に統合するステップを備えるものである。
【００５０】
この発明に係る画像処理方法は、対象画像を二値化するステップを備え、二値化後の対象画像に対して線分検出処理を行うようにしたものである。
【００５１】
【発明の実施の形態】
以下、この発明の実施の一形態を説明する。
実施の形態１．
図１はこの発明の実施の形態１による画像処理装置の構成を示すブロック図である。図において、１は対象画像のデータを供給され、その対象画像内の線分を検出する検出処理部であり、２は検出処理部１により検出された線分のデータ（線分の傾き、切片および端点のデータ）を格納する線分データ格納手段である。
【００５２】
検出処理部１において、１１は対象画像を二次元フーリエ変換する二次元フーリエ変換手段であり、１２は対象画像内の線分に対応するフーリエ平面での直線の傾きを検出してその線分の傾きを推定する傾き推定手段であり、１３は対象画像におけるすべての線分を検出するように各部を制御する検出処理制御手段である。
【００５３】
また、１４はフーリエ平面上で原点を通り、かつ傾き推定手段１２により推定された傾きαに対応する傾き（−１／α）を有する直線上の各点の値を抽出する直線データ抽出手段（第１の直線データ抽出手段）であり、１５は直線データ抽出手段１４により抽出された直線上の各点の値に対して一次元逆フーリエ変換を実行する一次元逆フーリエ変換手段であり、１６は一次元逆フーリエ変換手段１５により一次元逆フーリエ変換されて生成されたデータから線分の切片を推定する切片推定手段であり、１７は傾き推定手段１２により推定された傾きおよび切片推定手段１６により推定された切片に基づいて実平面上の対象画像において特定される直線上で、線分の端点を探索推定する端点推定手段である。
【００５４】
次に動作について説明する。
図２は実施の形態１による画像処理装置の動作を説明するフローチャートである。図３は切片の推定の方法について説明する図である。
【００５５】
まずステップＳＴ１において、検出処理部１の二次元フーリエ変換手段１１は、対象画像のデータを供給されると、二次元フーリエ変換を実行し、生成したフーリエ平面上の空間周波数データ、すなわち変換画像のデータを傾き推定手段１２および直線データ抽出手段１４に供給する。
【００５６】
このとき、図３２に示すように、実平面上において一定濃度値がｃであり、傾き、ｙ軸切片および端点のｘ座標がそれぞれα，βおよびｘｓである線分（ｃ×δ（ｙ−αｘ＋β）、ただしδ（）はＤｉｒａｃのデルタ関数）を含む直線を二次元フーリエ変換すると、変換後のフーリエ平面での直線Ｆ（ｆｘ，ｆｙ）は、式（１）に示すようになる。したがって図３３に示すように、実平面上の直線は、二次元フーリエ変換により、フーリエ平面上で原点を通る傾き（−１／α）の直線に変換されるため、フーリエ平面上の直線の傾き（−１／α）から実平面上の直線の傾きαを計算することができる。
【００５７】
そしてステップＳＴ２において、傾き推定手段１２は変換画像のデータから線分の傾きαを推定する。傾き推定手段１２は、例えばフーリエ平面上で、傾きが０ラジアンからπラジアンまでの原点を通る直線に沿って変換画像を線積分し、その積分値が最大値となったとき、またはその積分値が所定の閾値を超えたときの傾きをフーリエ平面上での傾き（−１／α）とし、その傾き（−１／α）から実平面上での線分の傾きαを計算する。あるいは、傾き推定手段１２は各線積分の値に対して閾値処理を行ったり、角度ごとのパターンマッチングを行うことによりフーリエ平面上での傾き（−１／α）を求め、その傾き（−１／α）から実平面上での線分の傾きαを計算する。
【００５８】
なお、対象画像において線分が存在する場合には、変換画像上で原点を通る直線が少なくとも１本現れるが、存在しない場合には１本も現れない。さらに対象画像において傾きの異なる複数の線分が存在する場合には、複数の直線が変換画像に現れる。この場合、傾き推定手段１２は、各線分に番号を付す。そして傾き推定手段１２は、線分の傾きαを直線データ抽出手段１４および端点推定手段１７に供給するとともに線分データ格納手段２に格納させ、線分の本数Ｎを検出処理制御手段１３に供給する。
【００５９】
検出処理制御手段１３は、線分の本数Ｎまたは後述の１サイクル終了信号を受け取ると、ステップＳＴ３において、未処理の線分の本数ｐがゼロであるか否かを判断する。なお、未処理の線分の本数ｐの初期値は、検出された線分の本数Ｎとする。
【００６０】
検出処理制御手段１３は、未処理の線分の本数ｐがゼロである場合には、検出終了信号を線分データ格納手段２に供給し、線分検出処理を終了する。一方、未処理の線分の本数ｐがゼロではない場合、検出処理制御手段１３は、ステップＳＴ４において未処理の線分の本数ｐを１だけ減算し、次に処理する線分を指定する処理継続信号を直線データ抽出手段１４に供給する。
【００６１】
直線データ抽出手段１４は、処理継続信号を受け取ると、ステップＳＴ５において、対象画像の空間周波数データおよび傾き推定手段１２による傾きαに基づいて、フーリエ平面上で原点を通り、かつ傾き（−１／α）を有する直線上の各点の値を抽出し、一次元の配列として一次元逆フーリエ変換手段１５に供給する。
【００６２】
なお、ステップＳＴ２における傾き推定処理において同時に直線の各点の値を一次元配列として保存しておき、ステップＳＴ５におけるフーリエ平面上の直線データの抽出を省略するようにしてもよい。
【００６３】
一次元逆フーリエ変換手段１５は、その直線上の値で構成される一次元配列を受け取ると、ステップＳＴ６において、その一次元配列に対して一次元逆フーリエ変換を行い、その変換結果を切片推定手段１６に供給する。
【００６４】
切片推定手段１６は、一次元逆フーリエ変換後のデータを受け取ると、ステップＳＴ７において、そのデータのピーク位置を検出することで切片を推定し、端点推定手段１７および線分データ格納手段２に供給する。
【００６５】
ここで、フーリエ平面（ｆｘ−ｆｙ平面）における所定の直線（ｆｘ＋αｆｙ＝０）上の各点での値に対して変数ｆｙで一次元逆フーリエ変換した結果ｈ（ｙ）は、式（２）に示すようになる。
【数２】
0003907905.tif 000003
【００６６】
この関数ｈ（ｙ）は、ｙの値が切片βと同一である際にピークを示す。したがって、例えば図３に示すように一次元逆フーリエ変換した結果のうちの最大値を示す場合の変数ｙの値が切片βとして推定される。
【００６７】
次に、ステップＳＴ８において、端点推定手段１７は、実平面での対象画像における線分の傾きαと切片βにより特定される実平面での直線上において線分を探索して端点を推定し、線分データ格納手段２に供給する。
【００６８】
なお、線分を特定するためには、通常、端点は二つ必要であるが、線分の長さを所定の長さと仮定しておき、一方の端点の座標のみを推定するようにして、探索するパラメータを削減するようにしてもよい。また、仮定する線分の長さを短くすることにより、複数の線分として曲線を近似的に検出することができる。
【００６９】
線分の長さが既知である場合および線分の長さが仮定されている場合、線分の探索の際には、実平面上で傾きαと切片βにより特定された直線上で、始点を順次移動させていき、各始点からその長さ分だけ線積分して、その積分値が最大となる始点を端点と推定する。
【００７０】
一方、線分の長さが未知である場合、線分の長さを所定の最小の長さとして同様に線積分を行い、その積分値が所定の閾値以上となる区間をすべて検出して、それらの区間を結合し、結合後の区間の端点を線分の端点と推定する。また、始点を順次移動させていき、所定の最小の長さの二倍程度の長さについてその線分の前半部分と後半部分の線積分をそれぞれ行った後に両者の差を計算し、その差がほぼゼロである場合には、線分がないか、両方とも線分上にあると判断し、その差がほぼゼロではない場合には、前半部分と後半部分との接続点付近に線分の端点があると判断し、その接続点を線分の端点と推定する。
【００７１】
そしてステップＳＴ９において、線分データ格納手段２は、推定された傾き、切片および端点を線分の番号ごとに線分データとして格納して、その後に１サイクル終了信号を検出処理制御手段１３に供給する。
【００７２】
以下、ステップＳＴ３からステップＳＴ９までの処理を、未処理の線分の本数ｐがゼロになるまで繰り返す。そして検出終了信号が供給されると、次の処理として今の場合、線分データ格納手段２が格納している線分データを出力する。なお、線分が検出されなかった場合には、線分データとしてゼロまたは空が出力される。
【００７３】
なお、上述の二次元フーリエ変換および一次元逆フーリエ変換は、ＦＦＴ（Ｆａｓｔ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ）アルゴリズムを使用して実行することができる。さらに専用プロセッサを用いることにより、二次元フーリエ変換および一次元逆フーリエ変換を高速に実行することができる。
【００７４】
ＦＦＴアルゴリズムを使用する場合、データ数が有限であり、位相の周期性により、一次元逆フーリエ変換後のデータにおいてピークが現れる際の変数ｙの値が真の切片βではないことがある。すなわち、対象画像の大きさをＭ×Ｎとし、ｊおよびｋを任意の整数とすると、真の切片β以外に、変数ｙの値がα×ｊ×Ｍ＋β＋ｋ×Ｎである場合にもピークが現れる。さらに、ピークの大きさは、画像中における線分の位置によって変化する。したがって真の切片βとは異なる値が検出されることを想定して、最初に、すべてのピークに対する変数ｙの値を複数の切片の候補として検出し、次に、それらの切片の候補に対して閾値処理やパターンマッチング処理を行い、真の切片βを推定する。
【００７５】
以上のように、この実施の形態１によれば、線分の傾きα、切片βおよび端点の３つのパラメータを各々独立に一次元空間で探索し、推定するようにしたので、線分の識別および線分検出を高速に実行することができるという効果が得られる。
【００７６】
実施の形態２．
図４はこの発明の実施の形態２による画像処理装置の構成を示すブロック図である。図において、２１は傾き推定手段１２および切片推定手段１６により推定された線分の傾きおよび切片によって定まる画像平面上の直線のデータを抽出する直線データ抽出手段（第２の直線データ抽出手段）であり、２２はその直線のデータを一次元フーリエ変換する一次元フーリエ変換手段であり、２３は一次元フーリエ変換手段２２により一次元フーリエ変換されたデータから線分の端点の位置を算出する端点推定手段である。なお、図２におけるその他の構成要素については実施の形態１によるものと同様であるので、その説明を省略する。
【００７７】
次に動作について説明する。
図５はこの発明の実施の形態２による画像処理装置の動作を説明するフローチャートである。図６は線分の濃度値の分布の一例を示す図であり、図７は線分の濃度値の分布を一次元フーリエ変換した後のデータの分布の一例を示す図であり、図８は図６に示す線分の濃度値の分布をｒだけ移動させた場合の線分の濃度値の分布を示す図である。
【００７８】
まず、ステップＳＴ１〜ステップＳＴ７において、実施の形態２による画像処理装置は実施の形態１による画像処理装置と同様に動作する。
【００７９】
そしてステップＳＴ１１において、直線データ抽出手段２１が傾き推定手段１２および切片推定手段１６により推定された線分の傾きおよび切片によって定まる画像平面上の直線のデータを抽出する。次にステップＳＴ１２において、一次元フーリエ変換手段２２がその直線のデータに対して一次元フーリエ変換を行う。なお、標本化定理に基づき、一次元フーリエ変換されるデータ数は画像サイズの２倍以上が望ましい。例えば線分部分の信号に揺らぎがなく対象画像に雑音がない場合には、直線の分布は図６に示すようになり、その場合の一次元フーリエ変換後のデータは図７に示すようになる。
【００８０】
そしてステップＳＴ１３において、一次元フーリエ変換手段２２により一次元フーリエ変換されたデータから端点推定手段２３が線分の端点の位置を算出する。このとき、フーリエ変換の推移定理により、図８に示す直線の部分がｒだけ移動して図６に示す直線の部分になったと考えると、両者のフーリエ変換の位相特性はｅｘｐ（−ｊ２πｒｆ）（ただし、ｊは虚数を表し、ｆは周波数を表す）だけ変化するので、その変化量から線分の中心であるｒを計算し、このｒと例えば予め設定されている線分の長さから端点が推定される。
【００８１】
そしてステップＳＴ９において、実施の形態１の場合と同様に、線分データ格納手段２は、推定された傾き、切片および端点を線分の番号ごとに線分データとして格納して、その後に１サイクル終了信号を検出処理制御手段１３に供給する。
【００８２】
以下、実施の形態１の場合と同様に未処理の線分の本数ｐがゼロになるまで上述の処理を繰り返す。そして検出終了信号が供給されると、次の処理として今の場合、線分データ格納手段２が格納している線分データを出力する。なお、線分が検出されなかった場合には、線分データとしてゼロまたは空が出力される。
【００８３】
以上のように、この実施の形態２によれば、実施の形態１による効果の他、画像平面上の線積分ではなく、線積分を空間周波数平面上に変換したデータから線分の端点を推定するようにしたので、線分の端点を推定するために必要なデータ量が低減され、そのデータを一時的に記憶するメモリの容量を低減することができ、装置の回路規模およびコストを低減することができるとともに、処理時間を低減することができるという効果が得られる。
【００８４】
実施の形態３．
図９はこの発明の実施の形態３による画像処理装置の構成を示すブロック図である。図において、３１は一次元フーリエ変換後のデータから線分の長さを推定する長さ推定手段であり、３２は一次元フーリエ変換手段２２により一次元フーリエ変換されたデータおよび長さ推定手段３１により推定された線分の長さから線分の端点の位置を算出する端点推定手段である。なお、図９におけるその他の構成要素については実施の形態２によるものと同様であるので、その説明を省略する。
【００８５】
次に動作について説明する。
図１０はこの発明の実施の形態３による画像処理装置の動作を説明するフローチャートである。
【００８６】
まずステップＳＴ１〜ステップＳＴ７、ステップＳＴ１１およびステップＳＴ１２において、実施の形態３による画像処理装置は実施の形態２による画像処理装置と同様に動作する。
【００８７】
そしてステップＳＴ２１において、長さ推定手段３１は一次元フーリエ変換後のデータから線分の長さを推定し、端点推定手段３２および線分格納手段２に供給する。このとき、一次元フーリエ変換後のデータの分布は例えば図７のようになり、極小点の間隔は線分方向の画像の大きさ（すなわち、線分を延長した直線と画像の辺との２つの交点の間の距離）をＭとするとＭ／Ｌに、極小点の個数はＬ個になることから、その極小点を検出してその極小点の位置から線分の長さＬが推定される。
【００８８】
次にステップＳＴ２２において、端点推定手段３２が一次元フーリエ変換手段２２により一次元フーリエ変換されたデータから線分の端点の位置を算出する。このとき、上述のｒと推定された線分の長さＬから線分の端点が推定される。
【００８９】
なお、端点推定手段３２は実施の形態２の場合と同様に一次元フーリエ変換手段２２により一次元フーリエ変換されたデータから線分の端点の位置を算出するようにしてもよい。
【００９０】
そしてステップＳＴ９において、線分データ格納手段２は、推定された傾き、切片および端点を線分の番号ごとに線分データとして格納して、その後に１サイクル終了信号を検出処理制御手段１３に供給する。
【００９１】
以下、実施の形態２の場合と同様に未処理の線分の本数ｐがゼロになるまで上述の処理を繰り返す。そして検出終了信号が供給されると、次の処理として今の場合、線分データ格納手段２が格納している線分データを出力する。なお、線分が検出されなかった場合には、線分データとしてゼロまたは空が出力される。
【００９２】
以上のように、この実施の形態３によれば、一次元フーリエ変換後のデータから線分の長さを推定するようにしたので、線分の長さが未知である場合にも正確に線分の端点を推定することができるという効果が得られる。
【００９３】
実施の形態４．
図１１はこの発明の実施の形態４による画像処理装置の構成を示すブロック図である。図において、４１は二次元フーリエ変換結果のデータから線分の長さを推定する長さ推定手段である。なお、図１１におけるその他の構成要素については実施の形態３によるものと同様であるので、その説明を省略する。
【００９４】
次に動作について説明する。
図１２はこの発明の実施の形態４による画像処理装置の動作を説明するフローチャートである。
【００９５】
まずステップＳＴ１およびステップＳＴ２において、実施の形態４による画像処理装置は実施の形態３による画像処理装置と同様に動作する。
【００９６】
次にステップＳＴ３１において、長さ推定手段４１が二次元フーリエ変換後のデータおよび線分の傾きから線分の長さを推定する。このとき、二次元フーリエ変換後の２次元のデータにおいて推定された線分の傾きの方向のデータの分布から、実施の形態３の場合と同様にして線分の長さが推定される。
【００９７】
そしてステップＳＴ３〜ステップＳＴ７、ステップＳＴ１１およびステップＳＴ１２において実施の形態４による画像処理装置は実施の形態３による画像処理装置と同様に動作する。その後、ステップＳＴ２２において、一次元フーリエ変換手段２２により一次元フーリエ変換されたデータから端点推定手段３２が線分の端点の位置を算出する。このとき、上述のｒと推定された線分の長さから線分の端点が推定される。
【００９８】
なお、端点推定手段３２は実施の形態２の場合と同様に一次元フーリエ変換手段２２により一次元フーリエ変換されたデータから線分の端点の位置を算出するようにしてもよい。
【００９９】
そしてステップＳＴ９において、線分データ格納手段２は、推定された傾き、切片および端点を線分の番号ごとに線分データとして格納して、その後に１サイクル終了信号を検出処理制御手段１３に供給する。
【０１００】
以下、実施の形態２の場合と同様に未処理の線分の本数ｐがゼロになるまで上述の処理を繰り返す。そして検出終了信号が供給されると、次の処理として今の場合、線分データ格納手段２が格納している線分データを出力する。なお、線分が検出されなかった場合には、線分データとしてゼロまたは空が出力される。
【０１０１】
以上のように、この実施の形態４によれば、一次元フーリエ変換後のデータから線分の長さを推定するようにしたので、線分の長さが未知である場合にも正確に線分の端点を推定することができるという効果が得られる。
【０１０２】
実施の形態５．
図１３はこの発明の実施の形態５による画像処理装置の構成を示すブロック図である。図において、５１は対象画像に線分が存在する可能性があるか否かを判定する線分存在判定手段である。なお、図１３におけるその他の構成要素については実施の形態１から実施の形態４のいずれかによるものと同様であるので、その説明を省略する。
【０１０３】
次に動作について説明する。
図１４はこの発明の実施の形態５による画像処理装置の動作を説明するフローチャートである。
【０１０４】
まずステップＳＴ５１において対象画像のデータを供給されると、線分存在判定手段５１は、対象画像に線分が存在する可能性があるか否かを判定する。このときの存在判定の方法としては、例えば対象画像の濃度値の平均や分散が所定の値以上である場合に線分が存在する可能性があると判定するといった対象画像の濃度値の平均や分散などの画像特性に基づいて閾値処理によって判定する方法、例えば対象画像を二値化した画像の濃度値の代数和が所定の値以上の場合に線分が存在する可能性があると判定するといった対象画像を二値化して判定する方法などがある。また、傾きが検出されたことが線分の存在の可能性を示すので、二次元フーリエ変換を実行し、二次元フーリエ変換後のデータからその傾きの方向の線分を検出することも考えられる。その場合、二次元フーリエ変換については傾きの検出の際の二次元フーリエ変換と兼ねることができる。
【０１０５】
また、対象画像を二値化する場合としては、閾値処理などによって対象画像の各画素を１と０に変換し、濃度値の総和が正の値である場合に線分が存在する可能性があると判定する方法、二値化後の濃度値が１である画素の近傍に濃度値が１である画素があり、かつ同一濃度値の画素の繋がりが確認される場合に線分が存在する可能性があると判定する方法などがある。
【０１０６】
次に、線分存在判定手段５１は、ステップＳＴ５２において線分が存在する可能性があると判定した場合には、ステップＳＴ５３において、実施の形態１から実施の形態４のいずれかと同様の線分検出処理を検出処理部１に実行させる。一方、線分が存在する可能性がないと判定した場合には、線分存在判定手段５１は、検出処理部１に検出終了信号を供給し、検出処理部１は線分検出処理を実行しない。
【０１０７】
以上のように、この実施の形態５によれば、対象画像の特性に基づいて線分の存在可能性を判定して、線分が存在する可能性がある場合にのみ線分検出処理を実行するようにしたので、線分のない対象画像の処理をスキップすることができ、効率的に線分検出処理を実行することができるという効果が得られる。
【０１０８】
実施の形態６．
図１５はこの発明の実施の形態６による画像処理装置の構成を示すブロック図である。図において、６１は線分存在判定手段５１と同様に対象画像に線分が存在する可能性があるか否かを判定する線分存在判定手段である。６２は線分存在判定手段６１により対象画像に線分が存在する可能性があると判定された場合にのみ、対象画像におけるすべての線分を検出するように各部を制御する検出処理制御手段である。６３は傾き推定手段１２により推定された線分の傾きに基づいて対象画像において線分の端点を探索する端点推定手段である。なお、図１５におけるその他の構成要素については実施の形態１によるものと同様であるので、その説明を省略する。
【０１０９】
次に動作について説明する。
図１６はこの発明の実施の形態６による画像処理装置の動作を説明するフローチャートである。
【０１１０】
まず、ステップＳＴ６１において線分存在判定手段６１が対象画像中の線分の存在可能性を判定し、ステップＳＴ６２において検出処理制御手段６２は線分存在判定手段６１により対象画像に線分が存在する可能性があると判定されたか否かを判断し、対象画像に線分が存在する可能性があると判定されないと判断した場合には線分検出処理を終了し、対象画像に線分が存在する可能性があると判定されたと判断した場合には対象画像におけるすべての線分を検出するように各部を制御する。
【０１１１】
そしてステップＳＴ１〜ステップＳＴ４において、実施の形態６による画像処理装置は実施の形態１による画像処理装置と同様に動作する。次にステップＳＴ６３において、端点推定手段６３は傾き推定手段１２により推定された線分の傾きに基づいて対象画像において線分の端点を探索し、線分の端点を推定する。
【０１１２】
そしてステップＳＴ９において、線分データ格納手段２は、推定された傾き、切片および端点を線分の番号ごとに線分データとして格納して、その後に１サイクル終了信号を検出処理制御手段６２に供給する。
【０１１３】
以下、実施の形態１の場合と同様に未処理の線分の本数ｐがゼロになるまで上述の処理を繰り返す。そして検出終了信号が供給されると、次の処理として今の場合、線分データ格納手段２が格納している線分データを出力する。なお、線分が検出されなかった場合には、線分データとしてゼロまたは空が出力される。
【０１１４】
以上のように、この実施の形態６によれば、線分が存在する可能性がある場合にのみ線分検出処理を実行するようにしたので、線分のない対象画像の処理をスキップすることができ、効率的に線分検出処理を実行することができるという効果が得られる。なお、この実施の形態６においては、切片を推定せずに傾きと端点から線分を規定するものであるが、例えば実施の形態１の場合のように切片を推定した後に端点を推定する場合に比べ処理時間がかかるが、例えば対象画像が雑音の多い画像である場合に従来の画像処理装置に比べ良好に線分を検出することができる。
【０１１５】
実施の形態７．
この発明の実施の形態７による画像処理装置は、実施の形態６による画像処理装置のうちの検出処理部１を変更したものである。実施の形態７による画像処理装置の検出処理部１は、実施の形態１〜実施の形態４における検出処理部１とは異なり、ＦＦＴの代わりにラドン変換、ハフ変換などの他の積分変換手法を使用した線分検出手法に基づいて対象画像から線分を検出する。
【０１１６】
以上のように、この実施の形態７によれば、対象画像に線分が存在するか否かを判定し、対象画像に線分が存在する場合のみ線分検出処理を実行するようにしたので、線分検出手法の種類に依らず、線分の存在しない対象画像については線分検出処理を実行しなくて済み、総合的に迅速に対象画像から線分を検出することができるという効果が得られる。
【０１１７】
実施の形態８．
図１７はこの発明の実施の形態８による画像処理装置の構成を示すブロック図である。図において、７１は対象画像を所定の形状のｎ個の分割画像に分割する画像分割手段である。なお、図１７におけるその他の構成要素については実施の形態１〜実施の形態７のいずれかによるものと同様であるので、その説明を省略する。
【０１１８】
次に動作について説明する。
図１８はこの発明の実施の形態８による画像処理装置の動作を説明するフローチャートである。
【０１１９】
まずステップＳＴ７１において、画像分割手段７１は、供給された対象画像を所定の形状のｎ個の分割画像に分割し、それらの分割画像を検出処理部１の二次元フーリエ変換手段１１に供給し、処理済みの分割画像をカウントする図示せぬカウンタｋの値を初期値１に設定する。
【０１２０】
なお、検出処理部１においてＦＦＴアルゴリズムを使用する場合には、変換精度の観点から、分割画像の一辺の長さができる限り２のべき乗になるように分割することが好ましい。また、後述のように、分割処理によって線分が分断されることが考えられるので、分割により線分が分断した際にもその分断を容易に検出できるように分割画像の縁の部分を互いにオーバーラップさせるようにしてもよい。
【０１２１】
次にステップＳＴ７２において、カウンタｋの値が分割画像の数ｎより大きいか否か、すなわちすべての分割画像についての処理が終了したか否かを例えば検出処理制御手段１３が判断する。
【０１２２】
ここでカウンタｋの値が分割画像の数ｎより大きくないと判断された場合、ステップＳＴ７３において、検出処理部１および線分データ格納手段２は、第ｋ番目の分割画像に対して線分の検出処理を実行する。なおステップＳＴ２３における線分の検出処理は、図２のステップＳＴ１〜ステップＳＴ９の処理と同様の処理である。これにより、第ｋ番目の分割画像についての線分データが線分データ格納手段２に格納される。
【０１２３】
そしてステップＳＴ７４においてカウンタｋの値を１だけ増加させた後、ステップＳＴ２２に戻り、すべての分割画像についての処理が終了するまで、次の分割画像についての処理を順次実行する。このようにすることにより、すべての分割画像についての処理が終了したときには、線分データ格納手段２にはｎ個の分割画像についての線分データが格納される。そしてすべての分割画像の検出処理が終わると全体の処理を終了する。
【０１２４】
以上のように、この実施の形態８によれば、対象画像を所定の数の分割画像に分割し、各分割画像に対して線分の検出処理を実行するようにしたので、分割画像の大きさに対する線分の長さが相対的に大きくなるため、信号対雑音比劣化に起因する線分検出の精度の劣化を低減することができるという効果が得られる。すなわち、フーリエ変換による画像処理では、実平面での線分の信号成分が、フーリエ平面での線分に対応する直線上に拡散されるため、一般的に信号対雑音比が劣化し、また画像の大きさに対して線分の長さが小さいほどその影響が大きくなるため、画像を分割することにより分割画像の大きさに対して線分の長さが相対的に大きくなり、信号対雑音比劣化の影響が軽減される。
【０１２５】
また、この実施の形態８によれば、分割処理することで、対象画像全体に処理に要する計算量が低減され、線分の検出処理を高速に実行することができるという効果が得られる。特にＦＦＴアルゴリズムの場合には、データ数すなわち画像の大きさが小さいほど高速であるので、効果的である。
【０１２６】
実施の形態９．
図１９はこの発明の実施の形態９による画像処理装置の構成を示すブロック図である。図において、７２は対象画像を分割画像に分割する際の分割画像の数と大きさを設定する分割方法決定手段である。なお、図１９におけるその他の構成要素については実施の形態８によるものと同様であるので、その説明を省略する。
【０１２７】
次に動作について説明する。
図２０はこの発明の実施の形態９による画像処理装置の動作を説明するフローチャートである。図２１および図２２は対象画像の分割方法の例を示す図である。
【０１２８】
ステップＳＴ７５において、分割方法決定手段７２は検出処理部１における線分検出手法や線分の長さなどの前提条件から最適となる分割方法を決定し、ステップＳＴ７１において、画像分割手段７１が対象画像をその分割方法に従って分割画像に分割する。
【０１２９】
例えば、画像平面において線積分処理によって線分を検出する場合、一般に積分効果により積分範囲が広いほど検出性能としては向上するが、処理時間やシステム条件の制約により積分範囲は最大で分割画像の大きさになる。また、対象画像の分割に起因する線分の分断などの影響も考えられる。
【０１３０】
そこで、例えば分割画像における線分部分の画素数の期待値に基づいて最適な分割方法を決定する。
【０１３１】
また、各分割画像をオーバーラップさせて、線分の分断の影響を軽減したり、前述の画素数の期待値を増加させる。ただし、オーバーラップさせる領域が増加すると、分割画像の数および各分割画像の画素数が増加して処理時間が増加するため、線分検出手法や検出条件などを考慮して決定することが望ましい。
【０１３２】
分割方法としては、例えば図２１に示すように線分の長さＬに基づいて各分割画像のサイズＷを決定する方法、例えば図２２に示すように隣接する分割画像同士をオーバーラップさせる方法などがある。
【０１３３】
例えば図２１に示すように対象画像を分割する場合、線分の長さをＬとし、分割画像の形状をＷ×Ｗの正方形とすると、その画像中における線分部分の画素数の期待値Ｎは式（３）に示すようになる。なお、式（３）から、Ｌ＝２Ｗのとき画素数の期待値Ｎが最大となる。
【数３】
0003907905.tif 000004
【０１３４】
また、図２２に示すように対象画像を分割する場合、各分割画像を画素数Ｃだけオーバーラップさせるとすると、線分部分の画素数の期待値Ｎは式（４）に示すようになる。
【数４】
0003907905.tif 000005
【０１３５】
各分割画像をオーバーラップさせるその他の分割方法としては、例えば、画像平面における画素値の分布ではなく、二次元フーリエ変換などの変換後の画素値の部分から分割方法を決定することなどが考えられる。例えば二次元フーリエ変換後の画素値から分割方法を決定する場合、対象画像の画像平面における線積分処理よりもやや検出性能が劣化することが考えられる。そこで、その劣化を抑制する方法を使用する。すなわち、分割画像における線分部分の画素数Ｎを比較すると式（５）に示すようになるので、式（６）に従って分割画像のサイズＷおよびオーバーラップする画素数Ｃを設定する。
【数５】
0003907905.tif 000006
【０１３６】
【数６】
0003907905.tif 000007
【０１３７】
さらにその他の分割方法としては、例えば濃度値の信号対雑音比や濃度値の分布などを考慮した分割方法などが考えられる。
【０１３８】
以上のように、この実施の形態９によれば、検出処理部１における線分検出手法や線分の長さなどの前提条件から最適となる分割方法を決定し、その分割方法に従って対象画像を分割するようにしたので、線分の検出性能を向上することができるという効果が得られる。
【０１３９】
実施の形態１０．
図２３はこの発明の実施の形態１０による画像処理装置の構成を示すブロック図である。図において、７３は分割方法を入力する分割方法入力手段であり、７２Ａは分割方法設定手段７３により設定された分割方法に基づいて対象画像を分割画像に分割する際の分割画像の数と大きさを設定する分割方法決定手段（条件付分割方法決定手段）である。なお、図２３におけるその他の構成要素については実施の形態８によるものと同様であるので、その説明を省略する。
【０１４０】
次に動作について説明する。
図２４はこの発明の実施の形態１０による画像処理装置の構成を示すブロック図である。
【０１４１】
まずステップＳＴ７６において、ユーザの操作により分割方法入力手段７３へ入力された分割方法の情報が分割方法決定手段７２Ａへ供給される。
【０１４２】
実施の形態９においては分割方法は固定されているが、実施の形態１０においては、例えば線分検出性能や処理時間を考慮してユーザが分割方法を適宜設定することができる。例えば二次元フーリエ変換を線分検出に使用する場合、検出性能と処理時間とがトレードオフの関係にあるため、どの程度の検出性能が必要か、もしくはどの程度の処理時間で線分を検出するかに応じて分割方法入力手段７３へ分割方法を入力することにより、必要に応じた特性で線分検出を実行することが可能である。またその場合、入力された分割方法での処理時間や検出性能を算出して表示し、ユーザによりそれが確認され、所定の操作がなされた場合に分割方法決定手段７２Ａへ分割方法の情報を供給するようにしてもよい。
【０１４３】
以上のように、この実施の形態１０によれば、分割方法を適宜入力、設定することを可能にしたので、処理時間などを考慮して検出性能について最適な処理を望まない場合に、所望の分割方法で線分検出処理を実行することができるという効果が得られる。
【０１４４】
実施の形態１１．
図２５はこの発明の実施の形態１１による画像処理装置の構成を示すブロック図である。図において、８１は実施の形態８〜実施の形態１０における、画像分割手段７１、画像分割手段７１と分割方法決定手段７２、並びに、画像分割手段７１と分割方法決定手段７２Ａと分割方法入力手段７３のいずれかで構成される画像分割部である。１−１〜１−ｍは、実施の形態１〜実施の形態１０のいずれかの検出処理部１と同様にそれぞれ構成され、分割画像についての線分の検出処理を並行して実行する複数の検出処理部である。
【０１４５】
次に動作について説明する。
図２６はこの発明の実施の形態１１による画像処理装置の動作を説明するフローチャートである。
【０１４６】
まずステップＳＴ８１において、画像分割部８１は、実施の形態８〜実施の形態１０のいずれかと同様にして、対象画像をｎ個の分割画像に分割する。そして画像分割部８１は、ｎ個の分割画像を、できる限り均等な数ずつｍ個の検出処理部１−１〜１−ｍに分散供給する。例えば分割画像の数ｎと検出処理部１−１〜１−ｍの数ｍが等しい場合には、検出処理部１−１〜１−ｍに分割画像が１つずつ供給され、分割画像の数ｎが検出処理部１−１〜１−ｍの数ｍのＫ倍である場合には、検出処理部１−１〜１−ｍに分散画像がＫ個ずつ供給される。
【０１４７】
次にステップＳＴ８２において、検出処理部１−１〜１−ｍは、供給された分割画像についての線分の検出処理を並行して実行する。そして、すべての検出処理部１−１〜１−ｍでの分割画像についての処理が終了したときには、線分データ格納手段２にはｎ個の分割画像についての線分データが格納される。そしてすべての分割画像の検出処理が終わると全体の処理を終了する。
【０１４８】
以上のように、この実施の形態１１によれば、対象画像を分割し、分割画像についての線分の検出処理を並列処理として実行するようにしたので、対象画像全体の線分検出処理を高速に実行することができるという効果が得られる。
【０１４９】
実施の形態１２．
図２７はこの発明の実施の形態１２による画像処理装置の構成を示すブロック図である。この発明の実施の形態１２による画像処理装置は、線分統合手段９１を追加したものである。図において、９１は１本の線分や曲線が複数の線分として検出されている場合に、それらの線分を１本の線分や１本の曲線に統合する線分統合手段である。
【０１５０】
次に動作について説明する。
図２８はこの発明の実施の形態１２による画像処理装置の動作を説明するフローチャートである。
【０１５１】
まずステップＳＴ９１において、検出処理部１が対象画像から線分を検出し、その線分のデータを線分データ格納手段２に格納させる。
【０１５２】
次にステップＳＴ９２において、線分統合手段９１が線分データ格納手段２から線分データを読み出し、その線分データに対して線分統合処理を実行し、処理後の線分データを線分データ格納手段２に格納させる。
【０１５３】
なお、線分統合処理では、線分データ（傾き、切片および端点）のうち、例えば１本の線分が複数本の線分として検出されているものや、１本の曲線が複数本の線分として検出されているものが選択され、それらの線分データを１本の線分データや同様の曲線データに統合される。また逆に複数本の線分が一本として検出された場合にはその線分データを分割するようにしてもよい。
【０１５４】
なお、統合処理としては、例えば数理形態学的演算（ｍｏｒｐｈｏｌｏｇｉｃａｌ  ｏｐｅｒａｔｉｏｎ）に基づいて線分に対して膨張（ｄｉｌａｔｉｏｎ）処理と侵食（ｅｒｏｓｉｏｎ）処理を行うことなどが考えられる。この場合、膨張処理により近接する線分を結合した後に、結合後の線分が侵食処理により収縮されて一本の線分とされる。
【０１５５】
以上のように、この実施の形態１２によれば、検出した線分データに対して線分統合処理を実行するようにしたので、対象画像に対する適切な線分データを取得することができるという効果が得られる。
【０１５６】
実施の形態１３．
図２９はこの発明の実施の形態１３による画像処理装置の構成を示すブロック図である。図において、９２は対象画像の各濃度値を、所定の閾値を基準として二値化し、二値化後の画像を対象画像として検出処理部１に供給する画像二値化手段である。なお、図２９におけるその他の構成要素については上記実施の形態によるものと同様であるのでその説明を省略する。
【０１５７】
次に動作について説明する。
上述の式（１）において濃度値を一定値ｃと仮定できるのは、雑音のない理想的な場合であり、例えばイメージセンサなどから得られる画像は、様々な分布特性をもつ信号からなり、また、様々な分布特性のノイズが含まれることから、検出が不正確になる可能性がある。そこで、実施の形態１３による画像処理装置では、前処理として対象画像を二値化する。
【０１５８】
すなわち、まず対象画像のデータが画像二値化手段９２に供給され、画像二値化手段９２は対象画像の各濃度値を、所定の閾値を基準として二値化し、二値化後の画像を対象画像として検出処理部１に供給する。
【０１５９】
以上のように、この実施の形態１３によれば、前処理として対象画像を二値化するようにしたので、対象画像の濃度値の分布特性やノイズによる線分の検出に対する影響を軽減することができるという効果が得られる。
【０１６０】
実施の形態１４．
この発明の実施の形態１４による画像処理装置は、上記実施の形態における、線分存在判定処理、分割処理、統合処理、二値化処理、並列処理などを任意に組み合わせたものである。
【０１６１】
例えば、分割処理を行うと、一本の線分が二本と検出されたり、同一の線分を異なる分割画像によって検出することなどが考えられる。そのため、検出後統合処理を行うことにより、各線分が分断された状態で検出されにくくなり正確に検出される。また、分割処理後、各分割画像に対して線分存在判定処理を行い、効率的な検出を行うこと、また、各分割画像に対して二値化処理を行うことで、検出性能を向上させることができる。
【０１６２】
以上のように、この実施の形態１４によれば、線分存在判定処理、分割処理、統合処理、二値化処理、並列処理などを任意に組み合わせるようにしているので、線分検出性能や処理時間などの前提条件や対象画像の特性に応じた線分検出処理を実行することができるという効果が得られる。
【０１６３】
【発明の効果】
以上のように、この発明によれば、対象画像を二次元フーリエ変換し、二次元フーリエ変換後の対象画像における直線の傾きを検出して対象画像内の線分の傾きを推定し、二次元フーリエ変換後の対象画像における直線の各点の値を一次元逆フーリエ変換し、一次元逆フーリエ変換により変換されたデータより対象画像における線分の切片を推定し、対象画像、線分の傾きおよび線分の切片に基づいて線分の端点を推定するように構成したので、線分の識別および線分検出を高速に実行することができるという効果がある。
【０１６４】
この発明によれば、対象画像を二次元フーリエ変換し、二次元フーリエ変換後の対象画像における直線の傾きを検出して線分の傾きを推定し、その直線の各点の値を抽出し、その直線の各点の値を一次元逆フーリエ変換し、一次元逆フーリエ変換後のデータより対象画像における線分の切片を推定し、線分の傾きおよび線分の切片に基づいて対象画像における直線の各点の値を抽出し、直線の各点の値を一次元フーリエ変換し、一次元フーリエ変換後のデータに基づいて対象画像における線分の端点を推定するように構成したので、線分の端点を推定するために必要なデータ量が低減され、そのデータを一時的に記憶するメモリの容量を低減することができ、装置の回路規模およびコストを低減することができるとともに、処理時間を低減することができるという効果がある。
【０１６５】
この発明によれば、一次元フーリエ変換後のデータに基づいて対象画像における線分の長さを推定し、一次元フーリエ変換後のデータおよび推定した線分の長さに基づいて対象画像における線分の端点を推定するように構成したので、線分の長さが未知である場合にも正確に線分の端点を推定することができるという効果がある。
【０１６６】
この発明によれば、二次元フーリエ変換後の対象画像における線分の長さを推定し、推定した線分の長さに基づいて対象画像における線分の端点を推定するように構成したので、線分の長さが未知である場合にも正確に線分の端点を推定することができるという効果がある。
【０１６７】
この発明によれば、所定の画像特性に基づいて対象画像に線分が存在する可能性があるか否かを判定し、対象画像に線分が存在する可能性があると判定された場合のみ線分の検出を実行するように構成したので、線分のない対象画像の処理をスキップすることができ、効率的に線分検出処理を実行することができるという効果がある。
【０１６８】
この発明によれば、対象画像を所定の数の分割画像に分割して、各分割画像をそれぞれ対象画像として処理するように構成したので、分割画像の大きさに対する線分の長さが相対的に大きくなるため、信号対雑音比劣化に起因する線分検出の精度の劣化を低減することができるという効果がある。
【０１６９】
また、分割処理することで対象画像全体に処理に要する計算量が低減され、線分の検出処理を高速に実行することができるという効果がある。
【０１７０】
さらに、分割画像についての線分の検出処理を並列処理として実行することができるので、その場合には、対象画像全体の線分検出処理を高速に実行することができるという効果がある。
【０１７１】
この発明によれば、対象画像を分割画像に分割する際の分割画像の数と大きさを設定するように構成したので、線分の検出性能を向上することができるという効果がある。
【０１７２】
この発明によれば、分割方法を入力し、設定した分割方法に基づいて対象画像を分割画像に分割する際の分割画像の数と大きさを設定するように構成したので、処理時間などを考慮して検出性能について最適な処理を望まない場合に、所望の分割方法で線分検出処理を実行することができるという効果がある。
【０１７３】
この発明によれば、複数の線分として検出された線分を１つの線分に統合するように構成したので、対象画像に対する適切な線分データを取得することができるという効果がある。
【０１７４】
この発明によれば、対象画像を二値化して、二値化後の対象画像について線分を検出するように構成したので、対象画像の濃度値の分布特性やノイズによる線分の検出に対する影響を軽減することができるという効果がある。
【図面の簡単な説明】
【図１】  この発明の実施の形態１による画像処理装置の構成を示すブロック図である。
【図２】  実施の形態１による画像処理装置の動作を説明するフローチャートである。
【図３】  切片の推定の方法について説明する図である。
【図４】  この発明の実施の形態２による画像処理装置の構成を示すブロック図である。
【図５】  この発明の実施の形態２による画像処理装置の動作を説明するフローチャートである。
【図６】  線分の濃度値の分布の一例を示す図である。
【図７】  線分の濃度値の分布を一次元フーリエ変換した後のデータの分布の一例を示す図である。
【図８】  図６に示す線分の濃度値の分布をｒだけ移動させた場合の線分の濃度値の分布を示す図である。
【図９】  この発明の実施の形態３による画像処理装置の構成を示すブロック図である。
【図１０】  この発明の実施の形態３による画像処理装置の動作を説明するフローチャートである。
【図１１】  この発明の実施の形態４による画像処理装置の構成を示すブロック図である。
【図１２】  この発明の実施の形態４による画像処理装置の動作を説明するフローチャートである。
【図１３】  この発明の実施の形態５による画像処理装置の構成を示すブロック図である。
【図１４】  この発明の実施の形態５による画像処理装置の動作を説明するフローチャートである。
【図１５】  この発明の実施の形態６による画像処理装置の構成を示すブロック図である。
【図１６】  この発明の実施の形態６による画像処理装置の動作を説明するフローチャートである。
【図１７】  この発明の実施の形態８による画像処理装置の構成を示すブロック図である。
【図１８】  この発明の実施の形態８による画像処理装置の動作を説明するフローチャートである。
【図１９】  この発明の実施の形態９による画像処理装置の構成を示すブロック図である。
【図２０】  この発明の実施の形態９による画像処理装置の動作を説明するフローチャートである。
【図２１】  対象画像の分割方法の例を示す図である。
【図２２】  対象画像の分割方法の例を示す図である。
【図２３】  この発明の実施の形態１０による画像処理装置の構成を示すブロック図である。
【図２４】  この発明の実施の形態１０による画像処理装置の構成を示すブロック図である。
【図２５】  この発明の実施の形態１１による画像処理装置の構成を示すブロック図である。
【図２６】  この発明の実施の形態１１による画像処理装置の動作を説明するフローチャートである。
【図２７】  この発明の実施の形態１２による画像処理装置の構成を示すブロック図である。
【図２８】  この発明の実施の形態１２による画像処理装置の動作を説明するフローチャートである。
【図２９】  この発明の実施の形態１３による画像処理装置の構成を示すブロック図である。
【図３０】  従来の画像処理装置の構成を示すブロック図である。
【図３１】  従来の画像処理装置の動作について説明するフローチャートである。
【図３２】  実平面上の線分の一例を示す図である。
【図３３】  実平面上の線分を二次元フーリエ変換したフーリエ平面上の直線の一例を示す図である。
【符号の説明】
１  検出処理部、１１  二次元フーリエ変換手段、１２  傾き推定手段、１４直線データ抽出手段（第１の直線データ抽出手段）、１５  一次元逆フーリエ変換手段、１６  切片推定手段、１７，２３，３２，６３  端点推定手段、２１直線データ抽出手段（第２の直線データ抽出手段）、２２  一次元フーリエ変換手段、３１，４１  長さ推定手段、５１，６１  線分存在判定手段、７１  画像分割手段、７２  分割方法決定手段、７２Ａ  分割方法決定手段（条件付分割方法決定手段）、７３  分割方法入力手段、９１  線分統合手段、９２  画像二値化手段。
【図１】
0003907905.tif 000008
【図２】
0003907905.tif 000009
【図３】
0003907905.tif 000010
【図４】
0003907905.tif 000011
【図５】
0003907905.tif 000012
【図６】
0003907905.tif 000013
【図７】
0003907905.tif 000014
【図８】
0003907905.tif 000015
【図９】
0003907905.tif 000016
【図１０】
0003907905.tif 000017
【図１１】
0003907905.tif 000018
【図１２】
0003907905.tif 000019
【図１３】
0003907905.tif 000020
【図１４】
0003907905.tif 000021
【図１５】
0003907905.tif 000022
【図１６】
0003907905.tif 000023
【図１７】
0003907905.tif 000024
【図１８】
0003907905.tif 000025
【図１９】
0003907905.tif 000026
【図２０】
0003907905.tif 000027
【図２１】
0003907905.tif 000028
【図２２】
0003907905.tif 000029
【図２３】
0003907905.tif 000030
【図２４】
0003907905.tif 000031
【図２５】
0003907905.tif 000032
【図２６】
0003907905.tif 000033
【図２７】
0003907905.tif 000034
【図２８】
0003907905.tif 000035
【図２９】
0003907905.tif 000036
【図３０】
0003907905.tif 000037
【図３１】
0003907905.tif 000038
【図３２】
0003907905.tif 000039
【図３３】
0003907905.tif 000040