JP2007052670A - 辺検出方法及び隅評価方法及び装置及びプログラム - Google Patents

Abstract

【課題】 撮影画像上の矩形領域の目標画像の四隅座標を処理能力の限られた携帯端末上で検出し、また、同時に処理時間を一定時間以内に収める。
【解決手段】 本発明は、撮影画像の中から矩形領域で囲まれた部分を検出する処理において、画像中から辺候補となる線分を多数検出し、それら線分の組み合わせについて、矩形を成す辺の接続関係や矩形の隅形状といった、複数の評価値を組み合わせて、総合的に評価を行う。
【選択図】 図１

Description

本発明は、辺検出方法及び隅評価方法及び装置及びプログラムに係り、特に、携帯電話などの処理能力の限られた端末上において、カメラなどの撮影画像の中から、ある矩形領域で囲まれた部分を、その四隅座標を判定することで正確に抜き出すための辺検出方法及び隅評価方法及び装置及びプログラムに関する。

特定の画像の中から直線を検出する手法としてハフ変換が知られている。ハフ変換では、まず、画像を二値化処理し、二値化画像の中で画素の値がある閾値を越える全ての画素をサンプリングする。次に、サンプリングした各画素について、その画素を通る全ての直線を考える。ここで、画像中にある原点を定めて、各画素を通る全ての直線について、原点との距離を計算する。角度と距離を軸とした極座標を考え、上記全ての直線を極座標上へ投票する。ここで、投票とは、距離が一致する直線が一本あれば、該当する座標の値を＋１することである。各点における投票数は、その数だけ同じ角度と原点からの距離をもつ直線が存在することを示しており、投票数が多いほど直線成分の強い直線であることがわかる。この処理により、投票数が多い方から直線を選ぶことで、画像中から強い直線成分を検出することが可能となる（例えば、特許文献１参照）。
P.V.C. Hough, “Method and means for recognizing complex patterns,” U.S. Patent 3069654

但し、上記のハフ変換では必ずしも必要とする直線だけが得られるわけではない。強い直線成分であればハフ変換による投票数が増え、弱い直線であれば投票数が減る。そのため、必要とする直線が絵柄に埋もれやすい場合や薄い場合などは投票数が減り、直線選別のための閾値を大きく下げることが必要である。閾値を下げることでより投票数の多い、はっきりとした直線が検出されてしまい、直線の選別が必要となる。この選別は、求める画像のパターンマッチングや人の目視などにより行われる場合が多く、確立された選別技術は存在しない。

ハフ変換は上記のように、直線検出には非常に有効な手法であり、デスクトップパーソナルコンピュータのような潤沢なリソースがあるならば、十分な性能が期待できる。しかし、プログラムサイズ、メモリ量、処理能力などの限られた携帯端末上で動作させる場合には、十分な性能を発揮するのは困難である。

また、得られた直線候補の選別におけるパターンマッチングなどでは、目標となるテンプレートを用意し、直線成分の組み合わせから、最適解を求めるという操作が必要である。この場合も複数の直線の組み合わせを求め、マッチングを行うためには、携帯端末のリソースは不足していると言える。

本発明は、上記の点に鑑みなされたもので、撮影画像上の矩形領域の四辺と四隅座標を処理能力の限られた携帯端末上で検出し、また、同時に処理時間を一定時間以内に収めることが可能な辺検出方法及び隅評価方法及び装置及びプログラムを提供することを目的とする。

図１は、本発明の原理を説明するための図である。

本発明（請求項１）は、画像中で四辺に囲まれた矩形領域の辺を検出する装置における辺検出方法であって、
画像入力手段において、入力された画像を取得する画像入力ステップ（ステップ1）と、
辺検出手段において、取得した画像中の矩形領域の辺を検出して、辺候補として記憶手段に格納する辺検出ステップ（ステップ２）と、
隅評価手段において、記憶手段から辺候補を取得し、該辺候補の交点を求め、記憶手段に格納し、該交点について矩形領域の隅を形成する組み合わせとなるかを判定し、隅評価結果として記憶手段に格納する隅評価ステップ（ステップ３）と、
検出結果出力手段において、記憶手段に格納されている隅評価結果に基づいて矩形領域の隅座標を出力する検出結果出力ステップ（ステップ４）と、を行う。

本発明（請求項２）は、請求項１の辺検出方法であって、
辺検出ステップ（ステップ２）において、
取得した画像に対し、フィルタ処理手段において、該画像の各縁上の任意の一点をフィルタ処理開始点とし、該フィルタ処理開始点から該画像の内側に向かって辺と直交する方向へフィルタ処理を行う。

また、本発明（請求項３）は、請求項１または２の辺検出方法であって、
辺検出ステップ（ステップ２）において、
フィルタ処理手段が、入力された画像の各縁上の辺探索開始点から該画像内部に向かい各ピクセル毎にフィルタ処理を行い、フィルタ出力値が閾値を超えた点を矩形領域の辺候補の辺探索開始点として検出する。

また、本発明（請求項４）は、請求項１乃至３の辺検出方法であって、
辺検出ステップ（ステップ２）において、
フィルタ処理手段により検出した辺探索開始点について、該辺探索開始点から、該フィルタ処理手段での探索方向と直交する方向へ向かい、色調変化が連続的に続くことを判定する。

また、本発明（請求項５）は、請求項１乃至４の辺検出方法であって、
辺検出ステップ（ステップ２）において、
辺探索開始点からフィルタ処理と直交する２方向へ辺探索を行った点の位置関係より、辺探索方向を示すベクトルを決定する。

また、本発明（請求項６）は、請求項１乃至５の辺検出方法であって、
辺検出ステップ（ステップ２）において、
フィルタ処理を行ったピクセルから、辺探索方向ベクトルの向きに隣接する１ピクセルとその周辺のピクセルについてフィルタ処理による判定を行い、該フィルタ処理が連続して数ピクセル続くまで繰り返す。

また、本発明（請求項７）は、請求項１乃至６の辺検出方法であって、
辺検出ステップ（ステップ２）において、
辺探索方向ベクトルの向きに向かい、数ピクセルおきに飛び飛びにフィルタ処理による判定を行う。

また、本発明（請求項８）は、請求項１乃至７の辺検出方法であって、
フィルタ処理による連続性が判定できなくなった部分を辺の端点として検出を行う。

また、本発明（請求項９）は、請求項１乃至８の辺検出方法であって、
辺の端点座標の定まった線分として辺を検出する。

本発明（請求項１０）は、隅評価方法であって、
記憶手段に格納されている辺候補を読み出して入力とし、交点計算手段において、全ての辺の組み合わせについて、辺の延長上も含めた交点を求める交点計算ステップと、
評価値計算手段において、交点を構成する辺と該交点について第１の評価値を求める評価値計算ステップと、
検出した辺から矩形を構成する四辺の組み合わせについて第２の評価値を求め、複数の評価値を組み合わせることで矩形の総合評価を行う評価ステップと、
を行う。

また、本発明（請求項１１）は、請求項１０の隅評価方法であって、
評価ステップにおいて、
辺端点及び交点と該交点を成す２本の辺の交点側の端点座標との距離について評価する。

また、本発明（請求項１２）は、請求項１０の隅評価方法であって、
評価ステップにおいて、
一つの交点を成す２本の辺について、片方の辺の端点がもう片方の辺の外側に位置するか、内側に位置するかという接続位置について評価する。

また、本発明（請求項１３）は、請求項１０の隅評価方法であって、
評価ステップにおいて、
交点計算ステップで求められた交点と該交点をなす２本の線分について、該交点を開始点として辺検出ステップと同様の辺探索を行い、矩形領域における隅位置と２本の辺の位置から、特定の方向へのみ探索が可能であるかについて評価する。

また、本発明（請求項１４）は、請求項１０の隅評価方法であって、
評価ステップにおいて、
画像の各外辺からそれぞれ辺候補を一本ずつ選択し、
選択された４本の辺候補によって形成される四辺形の面積を求める。

また、本発明（請求項１５）は、請求項１０の隅評価方法であって、
評価ステップにおいて、
選択された４本の辺からなる矩形領域の対角線の交わる点を矩形領域の重心座標間の距離の割合を評価する。

図２は、本発明の原理構成図である。

本発明（請求項１６）は、画像中で四辺に囲まれた矩形領域の辺を検出する辺検出装置であって、
入力された画像を取得する画像入力手段１０と、
取得した画像中の矩形領域の辺を検出して、辺候補として記憶手段１４に格納する辺検出手段１１と、
記憶手段１４から辺候補を取得し、該辺候補の交点を求め、記憶手段に格納し、該交点について矩形領域の隅を形成する組み合わせとなるかを判定し、隅評価結果として記憶手段に格納する隅評価手段１２と、
隅評価手段１２の隅評価結果に基づいて矩形領域の隅座標を出力する検出結果出力手段１３と、を有する。

また、本発明（請求項１７）は、請求項１６の辺検出装置であって、
辺検出手段１１は、
取得した画像に対し、該画像の各縁上の任意の一点をフィルタ処理開始点とし、該フィルタ処理開始点から該画像の内側に向かって辺と直交する方向へフィルタ処理を行うフィルタ手段を含む。

また、本発明（請求項１８）は、請求項１６または、１７の辺検出装置であって、
フィルタ処理手段は、
入力された画像の各縁上の辺探索開始点から該画像内部に向かい各ピクセルごとにフィルタ処理を行い、フィルタ出力値が閾値を超えた点を矩形領域の辺候補の辺探索開始点として検出する。

また、本発明（請求項１９）は、請求項１６乃至１８の辺検出装置であって、
辺検出手段１１は、
フィルタ処理手段で検出した辺探索開始点について、該辺探索開始点から、該フィルタ処理手段での探索方向と直交する方向へ向かい、色調変化が連続的に続くことを判定する辺探索手段を有する。

また、本発明（請求項２０）は、請求項１６乃至１９の辺検出装置であって、
辺検出手段１１の辺探索手段は、
辺探索開始点からフィルタ処理と直交する２方向へ辺探索を行った点の位置関係より、辺探索方向を示すベクトルを決定する探索方向ベクトル決定手段を有する。

また、本発明（請求項２１）は、請求項１６乃至２０の辺検出装置であって、
辺探索手段は、
フィルタ処理手段のフィルタ処理を行ったピクセルから、辺探索方向ベクトルの向きに隣接する１ピクセルとその周辺のピクセルについてフィルタ処理による判定を行い、該フィルタ処理が連続して数ピクセル続くまで繰り返す密探索手段を有する。

また、本発明（請求項２２）は、請求項１６乃至２１の辺検出装置であって、
辺探索手段は、
辺探索方向ベクトルの向きに向かい、数ピクセルおきに飛び飛びにフィルタ処理による判定を行う粗探索手段を有する。

また、本発明（請求項２３）は、請求項１６乃至２２の辺検出装置であって、
辺探索手段は、
フィルタ処理による連続性が判定できなくなった部分を辺の端点として検出を行う線分検出手段を有する。

また、本発明（請求項２４）は、請求項１６乃至２３の辺検出装置であって、
辺検出手段は、
辺の端点座標の定まった線分として辺を検出する手段を有する。

本発明（請求項２５）は、辺検出装置に用いられる隅評価装置であって、
記憶手段に格納されている辺候補を読み出して入力とし、全ての辺の組み合わせについて、辺の延長上も含めた交点を求める交点計算手段と、
交点を構成する辺と該交点について第１の評価値を求める評価値計算手段と、
辺検出装置で検出された辺から矩形を構成する四辺の組み合わせについて第２の評価値を求めることで矩形の総合評価を行う評価手段と、を有する。

また、本発明（請求項２６）は、請求項２５の隅評価装置であって、
評価手段は、
辺端点、交点計算手段で求めた交点と該交点を成す２本の辺の交点側の端点座標との距離について評価する手段を含む。

また、本発明（請求項２７）は、請求項２５の隅評価装置であって、
評価手段は、
一つの交点を成す２本の辺について、片方の辺の端点がもう片方の辺の外側に位置するか、内側に位置するかという接続位置について評価する辺接続位置関係評価手段を含む。

また、本発明（請求項２８）は、請求項２５の隅評価装置であって、
評価手段は、
交点計算手段で求めた交点と該交点を成す２本の線分について、該交点を開始点として、辺検出装置の辺探索手段と同様に辺探索を行い、矩形領域における隅位置と２本の辺の位置から、特定の方向へのみ探索が可能であるかについて評価する隅形状評価手段を含む。

また、本発明（請求項２９）は、請求項２５記載の隅評価装置であって、
評価値手段は、
画像の各外辺からそれぞれ辺候補を一本ずつ選択し、
選択された４本の辺候補によって形成される四辺形の面積を求める四辺形面積評価手段を含む。

また、本発明（請求項３０）は、請求項２５記載の隅評価装置であって、
評価手段は、
選択された４本の辺からなる矩形領域の対角線の交わる点を矩形領域の重心座標間の距離の割合を評価する四辺形重心評価手段を含む。

また、本発明（請求項３１）は、画像中で四辺に囲まれた矩形領域の辺を検出する辺検出プログラムであって、
コンピュータを、請求項１６乃至２４記載の辺検出装置として機能させるプログラムである。

本発明（請求項３２）は、隅を評価する隅評価プログラムであって、
コンピュータを、請求項２５乃至３０記載の隅評価装置として機能させるプログラムである。

本発明によれば、携帯電話などの処理能力が限られた携帯用端末上においても、撮影画像中にある任意の矩形領域を高速に、そして正確に検出することが可能である。

画像中から矩形領域を検出するためには、その矩形領域を構成する四辺を検出する必要がある。本発明では、一定の方向に連続して連なり、その周辺部とのコントラストが高い画素群を検出することで、画像の端から端までを突き抜ける直線を検出することが可能である。

また、それだけに留まらず、画素群の連続性が途切れる部分を判定することで、画像内部のある２点間のみを結ぶ線分をも検出可能である。

本発明では、線分（直線含む）検出漏れを防ぐため、辺検出手段におけるフィルタ処理の閾値を低く設定し、数多くの線分を検出している。検出した線分には必ず辺候補が含まれるため、この候補の中から求める矩形領域の辺を正確に判定できるように、精度の高い隅評価手段を実現した。

隅評価手段では、２本の線分の交点を求める矩形領域の隅と考えて、隅の座標と線分の端点座標の位置関係、２本の線分の交差状態、隅形状、四辺形の面積を合わせて評価することで求める矩形領域を構成する四辺を選択することが可能である。検出される隅座標は、ピクセル単位で検出され、正確な座標を得ることが可能である。

また、角が丸まっている四辺形なども、四辺の部分的な検出がなされていれば、四辺の接続関係から隅座標を仮想的に計算することで、矩形領域を検出可能である。

さらに、求める矩形領域のうち、一つの隅が画像外にある場合でも、四辺が部分的に検出されていれば、辺の延長上の隅座標を仮想的に計算することで、見えない隅座標を検出し、矩形領域を検出することが可能である。

本発明は、デスクトップパーソナルコンピュータのような処理能力の高い端末では当然実現可能であるが、携帯電話に代表されるような処理能力の低い端末でも動作可能であり、その処理速度も十分に速いことを特徴とする。そのため、矩形領域の抽出のための前処理として様々な機器への組み込みが可能となる。

携帯端末上にて動作可能なため、数多く出回っているカメラ付き携帯電話にも組み込み可能であり、今後カメラ付携帯電話の利用が変わる可能性を秘めている。矩形領域の収まっているモノを撮影すれば、その領域を自動的に検出できるため、リビングの椅子に座りながら、ＴＶ画面に向けてカメラ撮影することでＴＶの画面のみをキャプチャすることが可能である。例えば、番組毎に電子透かしが埋め込まれていれば、番組独自の情報をこれにより取得可能となる。

以下、図面と共に本発明の実施の形態を説明する。

本実施の形態では、カメラ付き携帯電話で電子透かし入り画像を撮影した場合について説明する。

図３は、本発明の一実施の形態における全体の動作のフローチャートであり、図４は、本発明の一実施の形態における実施イメージを示す。

まず、カメラ付き携帯電話のカメラモジュールから、電子透かしを埋め込んだ画像の撮影画像を取得し（ステップ１００）、撮影画像中の電子透かし入り画像領域の辺候補を検出する（ステップ２００）。辺候補の２本の組み合わせから導出される交点を画像の隅候補とし、各隅候補の座標について評価する（ステップ３００）。評価値の高い隅候補を構成する辺候補の組み合わせを、検出結果として出力する（ステップ４００）。

図５は、本発明の一実施の形態における用語を定義するための図である。同図は入力画像の例を示しており、当該入力画像において（ａ）の矢印は辺探索開始点探索、（ｂ）の矢印は密探索（辺探索）、（ｃ）の矢印は粗探索（辺探索）、（ｄ）の矢印は辺探索方向を示す。（ｅ）の点は、辺探索開始初期点、（ｆ）の点は辺探索開始点、（ｇ）の点は密探索終了点、（ｈ）の点は粗探索終了点、（ｉ）は辺探索途中の点であり、辺追跡点と呼ぶ。

図６は、本発明の一実施の形態における装置の基本構成を示す。

同図に示す装置は、画像入力部１０、辺検出部１１、隅評価部１２、検出結果出力部１３から構成される。なお、図示しないが、本装置は、メモリ等の記憶手段を有するものとする。

辺検出部１１は、カメラ付き携帯電話などで撮影された画像から、画像内にある電子透かし入り画像の辺を含む辺候補を検出し、メモリ（図示せず）に格納する。

図７は、本発明の一実施の形態における辺検出部の構成を示す。

辺検出部１１は、辺探索開始初期点決定部１１１、辺探索開始点探索部１１２、密探索部１１３、粗探索部１１４から構成される。

以下に、辺検出部１１の動作を説明する。

図８は、本発明の一実施の形態における辺検出部の処理のフローチャートである。

ステップ２０１） 辺検出部１１は、辺探索開始初期点決定部１１１へ入力された撮影画像を渡す。

ステップ２０２） 辺探索開始初期点決定部１１１は、入力画像の縁から一辺を選択する。

ステップ２０３） 辺探索開始初期点決定部１１１は、例えば、縁の中点を辺探索開始初期点と設定し、辺探索開始点座標を辺探索開始点探索部１１２へ渡す。本実施の形態では、画像の左辺が選択された場合について説明する。

ステップ２０４） 辺探索開始点探索部１１２は、ステップ２０３で決定した辺探索開始初期点から辺探索を開始する。辺探索開始点探索部１１２は、一画素ずつ画素の内側に向かって（この場合は右方向に）水平に辺探索開始点探索を行う。求める透かし入り画像が濃い色をしており、周辺部が白い画像であるなど、画像の縁の様にコントラストの大きい場所では大きいフィルタ出力が得られる。

ここで、辺探索開始点探索にて用いるフィルタについて説明する。図９は、本発明の一実施の形態における辺探索開始点探索部のフィルタを説明するための図である。同図では３×３の場合の例を示している。探索点座標をフィルタの中心と合わせて、フィルタ出力値を計算し、メモリ（図示せず）に格納する。図９（ａ）は、左側からの探索時に用いるフィルタであるが、例えば、上側からの探索であれば、同図（ｂ）に示すように右９０度回転したフィルタを用いる。但し、フィルタ形状は３×３に限らず、１×３や２×５の様な形状のフィルタでもよい。例えば、１×３であれば、（１，０，−１）というフィルタにすることが考えられる。また、白黒のような画像の輝度値変化を検出するフィルタに限らず、青黄のような色差の変化を検出するフィルタなども考えられる。また、画像に枠をつけた場合についても、例えば、フィルタを（１，０，１）などとすれば枠の検出が可能となる。

ステップ２０５） 画像の中心線まで辺探索開始点探索が続いた場合は、その縁についての探索は終了し、ステップ２１４にて入力画像の全ての縁について辺探索を行ったかどうかを判定する。まだ画像の中心線まで辿り着いていなければ、ステップ２０６へ移動し、辺探索開始点探索を続行する。

ステップ２０６） 現在のピクセルを中心ピクセルとして、フィルタ処理を行い、フィルタの出力をメモリ（図示せず）に格納する。メモリ（図示せず）に格納されているフィルタ出力がある閾値を超えた場合を辺検出とし、閾値を超えた座標を密探索部１１３へ送り、ステップ２０７へ処理を移す。フィルタの閾値は任意に設定でき、特に低く設定することにより、辺検出漏れを防ぐことが可能である。

ステップ２０７） 密探索部１１３は、ステップ２０６でエッジ検出した場合は、密探索を行う。辺探索開始点探索部１１２から受け取った座標を辺探索開始点とし、ステップ２０４の辺探索開始点探索と直交する方向（この場合は上下方向）に密探索を行う。本実施の形態では、上方向への密探索について説明する。エッジが左右に傾いている可能性があるので、密探索開始点から上方向へ１画素移動した点を中心とし、左右１画素の領域、合計３画素について辺探索開始点探索部１１２と同じフィルタを用いて密探索を行い、フィルタの出力をメモリ（図示せず）に格納する。メモリ（図示せず）のフィルタの出力が閾値を超えていて、かつ最も高い値の画素を次の密探索中心とする。フィルタ出力値が閾値を超えない場合は、その点で上方向への密探索を終了し、続いて辺探索開始点へ戻り、逆方向（この場合は下方向）への密探索を続ける。

ここでは、先に上方向へ探索、閾値を下回ったら、下方向へ探索としているが、辺探索開始点から上方向へ１ピクセル探索したら、次に下方向の探索を行い、また、上方向の探索と交互に進める方法などもある。

ステップ２０８） 密探索部１１３は、密探索による辺の追跡が、上下方向合わせて一定長以上続いた場合には密探索終了点とし、メモリ（図示せず）に格納し、ステップ２０９に移行し、そうでない場合はステップ２１３に移行する。

ステップ２０９） 上限密探索の途中の追跡点に基づいて得られる方向ベクトルを辺探索方向ベクトルとする。辺探索方向ベクトルの決定方法は、上下密探索終了点の二点を結ぶベクトルや辺追跡点から最小二乗近似から求まる直線の方向ベクトルから求めるといったことが考えられる。

ステップ２１０） 粗探索部１１４は、密探索部１１３でメモリ（図示せず）に格納された密探索終了点を粗探索開始点とし、ステップ２０９にて決定した辺方向探索ベクトルの向きに数ピクセルおきに飛び飛びに辺探索を行う（粗探索）。

ステップ２１１） 粗探索部１１４は、ステップ２１０の粗探索を続け、フィルタ出力値が閾値を下回った位置を、粗探索終了点とし、メモリ（図示せず）に格納する。

ステップ２１２） 予め各縁毎に辺探索にて検出する候補の上限数を決めておき、これまでの辺探索で検出したメモリ（図示せず）内の辺候補の数がその数に満たなければ、ステップ２１３に移行し、辺探索開始点に戻り再び辺探索を続ける。また、辺候補の数が上限数に達すれば、その辺における辺探索を終了する。

ステップ２１３） ステップ２０８において、密探索が一定長続かなかった場合は、文字などの短い線分の可能性や、求める矩形領域の辺ほどには長く続かない辺の可能性が高いため、途中で密探索は終了し、辺探索開始点に戻り、再び辺探索開始点探索を行う（ステップ２０４に移行する）。

ステップ２１４） 全ての縁について、上記の辺探索が終了していれば、辺探索は終了、まだ、探索を行っていない縁があれば、ステップ２０２に戻り、他の縁について辺探索を行う。

次に、隅評価部１２について説明する。

上記の辺検出部１１で撮影画像中の全ての辺候補を検出し、メモリ（図示せず）に格納した後は、隅評価部１２において辺候補の組み合わせについて評価し、正解の辺の組み合わせを求める。

図１０は、本発明の一実施の形態における隅評価部の構成を示す。

同図に示す隅評価部１２は、隅座標評価部１２１、四辺形面積評価部１２２、隅総合評価部１２３から構成される。

隅座標評価部１２１が、辺検出部１１で検出されメモリ（図示せず）に格納されている辺（辺候補）を読み出して、全ての辺についてその組み合わせを求め、その交点である隅について評価を行い、評価値をメモリ（図示せず）に格納する。

図１１は、本発明の一実施の形態における隅座標評価部の構成を示す。隅座標評価部１２１は、辺選択部１２１１、隅座標計算部１２１２、辺端点・隅位置評価部１２１３、辺接続位置関係評価部１２１４、隅形状評価部１２１５から構成される。

まず、辺選択部１２１１が、メモリ（図示せず）に格納されている辺候補から２本の辺を選択する。先の図５に示す通り、辺候補は入力画像の上下左右の縁からそれぞれ検出されているため、選択する辺は隣り合う縁同士（例えば、左と上）の組み合わせとする。

隅座標計算部１２１２は、辺選択部１２１１にて選択された２本の辺の交点を求め、メモリ（図示せず）に格納する。２本の辺は線分であるため、直接交わらない場合もあるが、その場合は仮想的に延長した際の交点を求める。

辺端点・隅位置評価部１２１３は、２辺の粗探索終了点座標と２辺から求まる隅座標の位置関係について評価し、評価値をメモリ（図示せず）に格納する。辺検出部１１の検出結果が正しい場合には、２辺の粗探索終了点座標と隅座標とは一致、もしくは、非常に距離が近い状態にあるはずである。逆に不正解の場合には、これらは離れていると考えられる。但し、正しい辺を検出していても途中で探索が途切れる場合もある。以上を考慮して、この２辺の組み合わせについて図１２に示すように評価の大小を考え、この評価値を“connect”とする。具体的な評価値は画像などの条件で異なるが、例えば、“5,3,1”といった評価値を与えることが考えられる。

辺接続位置関係評価部１２１４は、２辺の交点がそれぞれの線分の内側で交わっているか、外側で交わっているかを判定する。正解の辺同士の組み合わせであれば、２辺は各線分の外側にて交わる可能性が高いが、画像の内側にある線分などを選択した場合は、線分の途中で２辺が交わる可能性が高い。以上を考慮し、この２辺の組み合わせについて、図１３に示すように評価の大小を与え、評価値を“middle”とする。具体的な評価値は画像などの条件で異なるが、例えば、“5,1”といった評価値を与えることが考えられる。評価値は、メモリ（図示せず）に格納される。

隅形状評価部１２１５は、２辺の交点からその近傍にて辺探索をすることで、交点付近の矩形領域が隅の形状をしているかを確認する。矩形領域の隅から辺探索を開始した場合、矩形領域の縁に沿うＬ字型をした２方向へのみ辺探索を続けることが可能であり、３方向以上へ探索できる十字やＴ字で辺が交わっている場合は、矩形領域の隅である可能性は低いはずである。例えば、矩形領域の左下隅を考えた場合、右方向と上方向へは辺探索は可能であるが、左方向と下方向へは矩形領域が続いていないため、辺探索できないはずである。以上を考慮し、この２辺の組み合わせについて、図１４に示すように評価の大小を与え、評価値を“shape”とする。具体的な評価値は、画像などの条件で異なるが、例えば、“5,1”といった評価値を与えることが考えられる。評価値は、メモリ（図示せず）に格納される。

次に、隅評価部１２の四辺形評価部１２２について説明する。

隅座標評価部１２１が辺の組み合わせについて評価した後、四辺形評価部１２２が４辺の組み合わせについて評価し、評価値をメモリ（図示せず）に格納する。

図１５は、本発明の一実施の形態における四辺形評価部の構成を示す。

同図に示すように、四辺形評価部１２２は、四辺選択部１２２１、四辺形面積計算部１２２２及び、四辺形重心座標評価部１２２３で構成される。

まず、四辺形選択部１２２１が辺検出部１１で求められたメモリ（図示せず）に格納されている辺候補より、入力画像の上下左右から１辺ずつ計４本の辺候補を選択する。次に、四辺形面積計算部１２２２が、選択された４辺から交わる交点を求め、四辺形の面積と、カメラフレームに対する四辺形の面積比率αを求める。

また、四辺形重心座評価部１２２３は、選択された４辺からなる矩形領域の対角線の交わる点を矩形領域の重心座標とした時に、カメラフレームの対角線の半分の長さ（Ｌとする）に対する、カメラフレームと矩形領域の重心座標間の距離（Lengとする）の割合を評価する。

四辺形面積評価部１２２２は、以上の操作を全ての４辺の組み合わせについて行い、その結果をメモリ（図示せず）に格納する。

次に、隅評価部１２の隅総合評価部１２３について説明する。

隅総合評価部１２３が、隅座標評価部１２１と四辺形評価部１２２で求めた評価値を用いて、総合評価値を計算し、最適な辺の組み合わせを求め、メモリ（図示せず）に格納する。

図１６に示すように、カメラフレームに占める画像の面積が大きいほど、総合評価値を高く、面積が小さいほど低くする。また、図１７に示すように、カメラフレームの重心座標と矩形領域の重心座標が近い程評価値を高くする。例えば、総合評価値を
（connect＊middle＊shape）(１+α/100)(１+√Leng/L)
という計算式により計算する。但し、電子透かしの検出にはある程度の画素数が必要であるため、検出する矩形領域の面積に下限値を設け、αがある閾値（ＴＨ）よりも小さい場合には、総合評価値を０とする。

総合評価値の評価計算式は、この式に限定されるわけではなく、撮影条件や撮影対象などにより、最適な式は様々に変化し、和集合を組み合わせて、例えば、
（2*connect+middle+shape）(√α)(１+Leng/L)
といった式も考えられる。

なお、上記の個々の評価値についても、本実施の形態に限定されるものではない。評価値は高低の２段階と高中低の３段階だけではなく、５段階などの複数段階の評価や、離散的ではなく連続的な評価値、０−１に正規化された評価値などの重み付けを変化させることも考えられる。例えば、評価値“connect”であれば、隅座標と線分端点との距離を連続的な評価値で表現したり、評価値“shape”であれば、線分の交わり具合をＬ字、Ｔ字、十字と分けて評価することなどが考えられる。

また、隅評価部１２へは、辺検出部１１で検出した線分が入力されているが、ハフ変換で検出した直線や目視で検出した直線など、何らかの手法により得られた両端座標のわかる線であればよい。画像の端から端までの直線であった場合でも、画像の端の座標を線分の端点座標と考えればよく、これにより隅評価手法への適用が可能となる。さらに、評価値“middle”や“connect”を用いない評価式（例えば、“shape*α”など）によって判定を行うことなどにより、直線のみの組み合わせに対応することも考えられる。

次に、隅はみ出し画像例について説明する。

図１８は、本発明の一実施の形態におけるカメラフレームからはみ出した矩形領域の例を示す。同図に示すように、撮影対象画像の一つの隅がカメラフレームの外側に出てしまい、隅が欠けた状態の画像の場合もありうる。このとき、欠けた隅について評価値“shape”や“connect”は低い値となるが、評価値“middle”は通常の値を保つ。また、他の３つの隅の評価値や面積評価値が十分に高いことが考えられ、この組み合わせについて最も評価値が高い場合には、この欠けた隅を一つの隅として含めた矩形領域を検出することが可能である。

次に、角丸まり画像例について説明する。

図１９は、本発明の一実施の形態における角の丸まった矩形領域の例を示す。同図に示すように、矩形領域の隅が丸まっている場合は、辺検出部１１による辺の端点（粗探索終了点）は同図Ａの位置になる。この時、２辺の延長上における交点は同図中Ｂであるため、評価値“shape”や“connect”は低い評価値となる可能性が高い。しかし、他の３つの隅の評価値が十分に高い場合や、評価値“middle”や画面評価の結果が他の辺候補の組み合わせよりも十分に高い場合に、評価式によっては、この丸まった隅が最も評価値が高くなることが考えられる。これにより、隅が丸まった矩形領域や、あるいは角の欠けた多角形なども本方法により検出可能となる。

次に、多画像の例について説明する。

図２０は、本発明の一実施の形態における多画像中からの矩形領域抽出の例である。

同図に示すように、対象画像以外に他の画像が並んでいる場合など、求める矩形領域の辺以外に多数の辺候補がある場合について示す。辺検出部１１では、なるべく多くの辺候補を検出するので、図２０右側に示す太い線分を検出する。但し、画像右側の波打った線は、辺探索開始点探索において辺探索開始点を検出するが、その線が一定方向に連続して続かないため、辺候補としては検出されない。また、画像上部の幅の狭い矩形領域も、辺探索開始点の検出はされ、密探索が実行されるが、辺が連続して連なる距離が短いため、一定長の辺探索が続かず、辺候補として検出されることはない。

この画像の例では、辺検出部１１にて、求める矩形領域の外側にある、他の矩形領域の辺についても検出するので、検出した辺候補について隅評価部１２において評価が行われる。画像下側の辺を考えた場合、図２０に示すように、（１）（２）（３）と３つの候補がある。これらと組み合わせられる辺として、左側にはＡ，Ｂ，Ｃと３つの候補、右側にはａ，ｂ，ｃと３つの候補があり、これらの組み合わせから評価値を計算し、最適な組み合わせを求める。

図２０内の（１）の辺であれば、Ｂとｂの組み合わせが最も評価値が高くなるといえる。Ａやａを選んだ場合には、線分の粗探索終了座標とその交点座標が離れているため、評価値“connect”が低い値となる。Ｃやｃを選んだ場合には、評価値“connect”に加えて、２本の辺候補が線分の途中で交わるために、評価値“middle”も低い値となる。評価値“shpae”については、どの候補の選び方をしても、交点座標から最適なＬ字型の二方向への探索はできないため、低い値となる。（２）の場合も（１）と略同様にして、Ｂとｂの組み合わせが最も評価値が高くなると言える。（３）の場合は、Ｃとａの組み合わせが最も評価値が高くなる。

次に、（１）、（２）、（３）を比べた場合、（２）（３）は辺候補の粗探索終了点同士がくっついているため、評価値“connect”の値が最も高くなるといえる。また、評価値“shape”についても、交点からＬ字２方向へ探索可能なため、（１）より高い値となる。（２）と（３）を比較した場合、それぞれの矩形領域が囲む面積が（２）の方が大きいと言えるため、最終的に（２）、Ｂ，ｂの組み合わせが求める矩形領域と判定される。

逆に内側の矩形領域を取得したい場合には、面積による重み付けを変化させ、面積が小さくても評価値が高くなるようにしたり、面積に上限値を設定することなどが考えられる。

「片山淳、中村高雄、山室雅史、曽根原登：『電子透かし読み取りのためのｉアプリ高速コーナー検出アルゴリズム』、電子情報通信学会論文誌、Vol. J88-D-II, No.6, 2005」においては、撮影画像からの電子透かし読み取りのための矩形領域の隅検出を行っているが、撮影画像の総ピクセルに数％程度の画素しか参照しておらず、携帯端末上において実行可能であることが示されている。本発明における方法でも、辺検出、隅評価の部分では必要最小限の画素しか利用していないことから、携帯端末上において実行可能であるといえる。

また、本発明は、上記の図６に示す画像入力１０、辺検出部１１、隅評価部１２、検出結果出力部１３の動作をプログラムとして構築し、これらから構成される辺検出装置として利用されるコンピュータにインストールする、または、ネットワークを介して流通させることも可能である。

なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。

本発明は、上記の実施の形態のみに依存するものではなく、映像や他の様々なメディアなどにも適用できるものである。文字認識やパターン認識の前処理として、風景中の矩形領域を抽出（看板やＴＶの領域検出）するといった利用方法も考えられる。

本発明の原理を説明するための図である。 本発明の原理構成図である。 本発明の一実施の形態における全体の動作のフローチャートである。 本発明の一実施の形態における実施イメージである。 本発明の一実施の形態における用語を定義するための図である。 本発明の一実施の形態における装置の基本構成図である。 本発明の一実施の形態における辺検出部の構成図である。 本発明の一実施の形態における辺検出部の処理のフローチャートである。 本発明の一実施の形態における辺探索開始点探索部のフィルタを説明するための図である。 本発明の一実施の形態における隅評価部の構成図である。 本発明の一実施の形態における隅座標評価部の構成図である。 本発明の一実施の形態における辺端点・隅位置評価部の評価例である。 本発明の一実施の形態における辺接続位置関係評価部の評価例である。 本発明の一実施の形態における隅形状評価部の評価例である。 本発明の一実施の形態における四辺形評価部の構成図である。 本発明の一実施の形態における四辺形面積評価部の評価例である。 本発明の一実施の形態におけるカメラフレームの重心座標と矩形領域の重心座標との関係を示す図である。 本発明の一実施の形態におけるカメラフレームからはみ出した矩形領域の例である。 本発明の一実施の形態における角の丸まった矩形領域の例である。 本発明の一実施の形態における多画像中からの矩形領域抽出の例である。

符号の説明

１０ 画像入力手段、画像入力部
１１ 辺検出手段、辺検出部
１２ 隅評価手段、隅評価部
１３ 検出結果出力手段、検出結果出力部
１４ 記憶手段
１１１ 辺探索開始初期点決定部
１１２ 辺探索開始点探索部
１１３ 密探索部
１１４ 粗探索部
１２１ 隅座標評価部
１２２ 四辺形面積評価部
１２３ 隅総合評価部
１２１１ 辺選択部
１２１２ 隅座標計算部
１２１３ 辺端点・隅位置評価部
１２１４ 辺接続位置関係評価部
１２１５ 隅形状評価部
１２２１ 四辺選択部
１２２２ 四辺形面積計算部
１２２３ 四辺形重心座評価部

Claims (32)

1. 画像中で四辺に囲まれた矩形領域の辺を検出する装置における辺検出方法であって、
   画像入力手段において、入力された画像を取得する画像入力ステップと、
   辺検出手段において、取得した前記画像中の矩形領域の辺を検出して、辺候補として記憶手段に格納する辺検出ステップと、
   隅評価手段において、前記記憶手段から前記辺候補を取得し、該辺候補の交点を求め、記憶手段に格納し、該交点について矩形領域の隅を形成する組み合わせとなるかを判定し、隅評価結果として記憶手段に格納する隅評価ステップと、
   検出結果出力手段において、前記記憶手段に格納されている前記隅評価結果に基づいて矩形領域の隅座標を出力する検出結果出力ステップと、
   を行うことを特徴とする辺検出方法。
2. 前記辺検出ステップにおいて、
   取得した前記画像に対し、フィルタ処理手段において、該画像の各縁上の任意の一点をフィルタ処理開始点とし、該フィルタ処理開始点から該画像の内側に向かって辺と直交する方向へフィルタ処理を行う、請求項１記載の辺検出方法。
3. 前記辺検出ステップにおいて、
   フィルタ処理手段が、入力された前記画像の各縁上の辺探索開始点から該画像内部に向かい各ピクセル毎にフィルタ処理を行い、フィルタ出力値が閾値を超えた点を矩形領域の辺候補の辺探索開始点として検出する、請求項１または２記載の辺検出方法。
4. 前記辺検出ステップにおいて、
   フィルタ処理手段により検出した前記辺探索開始点について、該辺探索開始点から、該フィルタ処理手段での探索方向と直交する方向へ向かい、色調変化が連続的に続くことを判定する、請求項１乃至３のいずれか１項記載の辺検出方法。
5. 前記辺検出ステップにおいて、
   前記辺探索開始点からフィルタ処理と直交する２方向へ辺探索を行った点の位置関係より、辺探索方向を示すベクトルを決定する、請求項１乃至４のいずれか１項記載の辺検出方法。
6. 前記辺検出ステップにおいて、
   フィルタ処理を行ったピクセルから、辺探索方向ベクトルの向きに隣接する１ピクセルとその周辺のピクセルについてフィルタ処理による判定を行い、該フィルタ処理が連続して数ピクセル続くまで繰り返す、請求項１乃至５のいずれか１項記載の辺検出方法。
7. 前記辺検出ステップにおいて、
   辺探索方向ベクトルの向きに向かい、数ピクセルおきに飛び飛びにフィルタ処理による判定を行う、請求項１乃至６のいずれか１項記載の辺検出方法。
8. フィルタ処理による連続性が判定できなくなった部分を辺の端点として検出を行う、請求項１乃至７のいずれか１項記載の辺検出方法。
9. 辺の端点座標の定まった線分として辺を検出する、請求項１乃至８のいずれか１項記載の辺検出方法。
10. 隅評価方法であって、
    記憶手段に格納されている辺候補を読み出して入力とし、交点計算手段において、全ての辺の組み合わせについて、辺の延長上も含めた交点を求める交点計算ステップと、
    評価値計算手段において、前記交点を構成する辺と該交点について第１の評価値を求める評価値計算ステップと、
    検出した辺から矩形を構成する四辺の組み合わせについて第２の評価値を求め、複数の評価値を組み合わせることで矩形の総合評価を行う評価ステップと、
    を行うことを特徴とする隅評価方法。
11. 前記評価ステップにおいて、
    辺端点及び前記交点と該交点を成す２本の辺の交点側の端点座標との距離について評価する請求項１０記載の隅評価方法。
12. 前記評価ステップにおいて、
    一つの交点を成す２本の辺について、片方の辺の端点がもう片方の辺の外側に位置するか、内側に位置するかという接続位置について評価する請求項１０記載の隅評価方法。
13. 前記評価ステップにおいて、
    前記交点計算ステップで求められた前記交点と該交点をなす２本の線分について、該交点を開始点として前記辺検出ステップと同様の辺探索を行い、矩形領域における隅位置と２本の辺の位置から、特定の方向へのみ探索が可能であるかについて評価する請求項１０記載の隅評価方法。
14. 前記評価ステップにおいて、
    画像の各外辺からそれぞれ辺候補を一本ずつ選択し、
    選択された４本の辺候補によって形成される四辺形の面積を求める請求項１０記載の隅評価方法。
15. 前記評価ステップにおいて、
    選択された４本の辺からなる矩形領域の対角線の交わる点を矩形領域の重心座標間の距離の割合を評価する請求項１０記載の隅評価方法。
16. 画像中で四辺に囲まれた矩形領域の辺を検出する辺検出装置であって、
    入力された画像を取得する画像入力手段と、
    取得した前記画像中の矩形領域の辺を検出して、辺候補として記憶手段に格納する辺検出手段と、
    前記記憶手段から前記辺候補を取得し、該辺候補の交点を求め、記憶手段に格納し、該交点について矩形領域の隅を形成する組み合わせとなるかを判定し、隅評価結果として記憶手段に格納する隅評価手段と、
    前記隅評価手段の前記隅評価結果に基づいて矩形領域の隅座標を出力する検出結果出力手段と、
    を有することを特徴とする辺検出装置。
17. 前記辺検出手段は、
    取得した前記画像に対し、該画像の各縁上の任意の一点をフィルタ処理開始点とし、該フィルタ処理開始点から該画像の内側に向かって辺と直交する方向へフィルタ処理を行うフィルタ手段を含む請求項１６記載の辺検出装置。
18. 前記フィルタ処理手段は、
    入力された前記画像の各縁上の辺探索開始点から該画像内部に向かい各ピクセルごとにフィルタ処理を行い、フィルタ出力値が閾値を超えた点を矩形領域の辺候補の辺探索開始点として検出する、請求項１６または１７記載の辺検出装置。
19. 前記辺検出手段は、
    フィルタ処理手段で検出した前記辺探索開始点について、該辺探索開始点から、該フィルタ処理手段での探索方向と直交する方向へ向かい、色調変化が連続的に続くことを判定する辺探索手段を有する、請求項１５乃至１７のいずれか１項記載の辺検出装置。
20. 前記辺検出手段の前記辺探索手段は、
    前記辺探索開始点からフィルタ処理と直交する２方向へ辺探索を行った点の位置関係より、辺探索方向を示すベクトルを決定する探索方向ベクトル決定手段を有する、請求項１６乃至１９のいずれか１項記載の辺検出装置。
21. 前記辺探索手段は、
    前記フィルタ処理手段のフィルタ処理を行ったピクセルから、辺探索方向ベクトルの向きに隣接する１ピクセルとその周辺のピクセルについてフィルタ処理による判定を行い、該フィルタ処理が連続して数ピクセル続くまで繰り返す密探索手段を有する、請求項１６乃至２０のいずれか１項記載の辺検出装置。
22. 前記辺探索手段は、
    辺探索方向ベクトルの向きに向かい、数ピクセルおきに飛び飛びにフィルタ処理による判定を行う粗探索手段を有する、請求項１６乃至２１のいずれか１項記載の辺検出装置。
23. 前記辺探索手段は、
    フィルタ処理による連続性が判定できなくなった部分を辺の端点として検出を行う線分検出手段を有する、請求項１６乃至２２のいずれか１項記載の辺検出装置。
24. 前記辺検出手段は、
    辺の端点座標の定まった線分として辺を検出する手段を有する、請求項１６乃至２３のいずれか１項記載の辺検出装置。
25. 辺検出装置に用いられる隅評価装置であって、
    記憶手段に格納されている辺候補を読み出して入力とし、全ての辺の組み合わせについて、辺の延長上も含めた交点を求める交点計算手段と、
    前記交点を構成する辺と該交点について第１の評価値を求める評価値計算手段と、
    前記辺検出装置で検出された辺から矩形を構成する四辺の組み合わせについて第２の評価値を求めることで矩形の総合評価を行う評価手段と、
    を有することを特徴とする隅評価装置。
26. 前記評価手段は、
    辺端点、前記交点計算手段で求めた前記交点と該交点を成す２本の辺の交点側の端点座標との距離について評価する手段を含む、請求項２５記載の隅評価装置。
27. 前記評価手段は、
    一つの交点を成す２本の辺について、片方の辺の端点がもう片方の辺の外側に位置するか、内側に位置するかという接続位置について評価する辺接続位置関係評価手段を含む請求項２５記載の隅評価装置。
28. 前記評価手段は、
    前記交点計算手段で求めた前記交点と該交点を成す２本の線分について、該交点を開始点として、辺検出装置の辺探索手段と同様に辺探索を行い、矩形領域における隅位置と２本の辺の位置から、特定の方向へのみ探索が可能であるかについて評価する隅形状評価手段を含む請求項２５記載の隅評価装置。
29. 前記評価値手段は、
    画像の各外辺からそれぞれ辺候補を一本ずつ選択し、
    選択された４本の辺候補によって形成される四辺形の面積を求める四辺形面積評価手段を含む請求項２５記載の隅評価装置。
30. 前記評価手段は、
    選択された４本の辺からなる矩形領域の対角線の交わる点を矩形領域の重心座標間の距離の割合を評価する四辺形重心評価手段を含む請求項２５記載の隅評価装置。
31. 画像中で四辺に囲まれた矩形領域の辺を検出する辺検出プログラムであって、
    コンピュータを、
    前記請求項１６乃至２４記載の辺検出装置として機能させることを特徴とする辺検出プログラム。
32. 隅を評価する隅評価プログラムであって、
    コンピュータを、
    前記請求項２５乃至３０記載の隅評価装置として機能させることを特徴とする隅評価プログラム。

Images