(57)【要約】【課題】画像内のオブジェクトを検出する方法および装置。【解決手段】画像内の略矩形のオブジェクトを検出する方法は、画像内の検出されたコーナーに基づいて画像内の候補矩形を判定するステップと、弁別ファクタの組に基づいて候補矩形をランク付けするステップと、ランク付けされた候補矩形に基づいて画像内のオブジェクトを検出するステップと、を有している。【選択図】図１
2008171417.tif 000002
【特許請求の範囲】
【請求項１】
画像内の略矩形のオブジェクトを検出する方法であって、
前記画像内の検出されたコーナーに基づいて前記画像内の候補矩形を判定するステップ
と、
弁別ファクタの組に基づいて前記候補矩形をランク付けするステップと、
前記ランク付けされた候補矩形に基づいて前記画像内のオブジェクトを検出するステッ
プとを含むことを特徴とする画像内の略矩形のオブジェクトを検出する方法。
【請求項２】
前記ランク付けするステップの前に、選択された候補矩形を破棄するステップを更に含
むことを特徴とする請求項１に記載の画像内の略矩形のオブジェクトを検出する方法。
【請求項３】
選択された候補矩形は、高位にランク付けされた候補矩形と閾値である量を上回ってオ
ーバーラップしている場合に、破棄されることを特徴とする請求項２に記載の画像内の略
矩形のオブジェクトを検出する方法。
【請求項４】
前記ランク付けするステップの前に、近接する候補矩形をマージするステップを更に含
むことを特徴とする請求項３に記載の画像内の略矩形のオブジェクトを検出する方法。
【請求項５】
前記弁別ファクタの組は、前記候補矩形に近接したピクセルと関連付けられた少なくと
もエッジ及び色情報に基づいていることを特徴とする請求項４に記載の画像内の略矩形の
オブジェクトを検出する方法。
【請求項６】
前記ランク付けするステップの前に、前記候補矩形の境界を調節するステップを更に含
むことを特徴とする請求項４に記載の画像内の略矩形のオブジェクトを検出する方法。
【請求項７】
前記調節するステップにおいて、前記候補矩形を定義している前記コーナーの位置を前
記候補矩形を取り囲んでいる近傍部分内において調節することを特徴とする請求項６に記
載の画像内の略矩形のオブジェクトを検出する方法。
【請求項８】
前記判定するステップは、
前記画像のバックグラウンド色を推定するステップと、
前記推定されたバックグラウンド色に基づいて前記オブジェクトの境界を画しているエ
ッジを検出するステップと、
前記エッジを調べることにより、コーナーを表す交差しているエッジを検出するステッ
プと、
矩形の頂点を定義しているコーナーをグループ化することにより、前記候補矩形を判定
するステップと、を含むことを特徴とする請求項１に記載の画像内の略矩形のオブジェク
トを検出する方法。
【請求項９】
前記ランク付けするステップの前に、前記候補矩形の境界を調節するステップを更に含
むことを特徴とする請求項８に記載の画像内の略矩形のオブジェクトを検出する方法。
【請求項１０】
前記ランク付けするステップの前に、選択された候補矩形を破棄するステップを更に含
むことを特徴とする請求項９に記載の画像内の略矩形のオブジェクトを検出する方法。
【請求項１１】
選択された候補矩形は、高位にランク付けされた候補矩形と閾値である量を上回ってオ
ーバーラップしている際に、破棄されることを特徴とする請求項１０に記載の画像内の略
矩形のオブジェクトを検出する方法。
【請求項１２】
前記ランク付けするステップの前に、近接する候補矩形をマージするステップを更に含
むことを特徴とする請求項１１に記載の画像内の略矩形のオブジェクトを検出する方法。
【請求項１３】
画像内のバックグラウンド色を推定する方法であって、
前記画像のそれぞれのスキャンラインを類似した色のラインセグメントにセグメント化
するステップと、
前記類似した色のラインセグメントを色によってグループ化するステップと、
前記グループの前記ラインセグメントに沿ったエッジピクセルに基づいて前記バックグ
ラウンド色を推定するステップと、を含むことを特徴とする画像内のバックグラウンド色
を推定する方法。
【請求項１４】
前記グループ化するステップにおいて、閾値である長さを上回る類似した色のラインセ
グメントのみをグループ化することを特徴とする請求項１３に記載の画像内のバックグラ
ウンド色を推定する方法。
【請求項１５】
前記推定するステップは、エッジピクセルの数及び強度に基づいて実行されることを特
徴とする請求項１４に記載の画像内のバックグラウンド色を推定する方法。
【請求項１６】
前記推定するステップは、
閾値であるラインセグメント数を具備した前記類似した色のラインセグメントのグルー
プを判定するステップと、
それぞれの前記類似した色のラインセグメントのグループの平均色を候補バックグラウ
ンド色として指定するステップと、
それぞれの候補バックグラウンド色ごとに、その候補バックグラウンド色を表す前記グ
ループの前記ラインセグメントに沿ってエッジピクセルを検出し、且つ、前記エッジピク
セルによって定義されたエッジの強度を算出するステップと、
エッジピクセルカウント及びエッジ強度に基づいて前記候補バックグラウンド色の中の
１つを前記バックグラウンド色として選択するステップと、を含むことを特徴とする請求
項１５に記載の画像内のバックグラウンド色を推定する方法。
【請求項１７】
請求項１に記載の画像内の略矩形のオブジェクトを検出する方法を実行するプログラム
コードを有するコンピュータプログラムを含むことを特徴とするコンピュータ可読媒体。
【請求項１８】
請求項１３に記載の画像内のバックグラウンド色を推定する方法を実行するプログラム
コードを有するコンピュータプログラムを含むことを特徴とするコンピュータ可読媒体。
【請求項１９】
画像内の略矩形のオブジェクトを検出する装置であって、
前記画像を保存するメモリと、
前記メモリと通信している処理構造であって、前記画像内の検出されたコーナーに基づ
いて前記画像を処理することにより、候補矩形を判定し、弁別ファクタの組に基づいて前
記候補矩形をランク付けすると共に、前記ランク付けされた候補矩形から前記画像内のオ
ブジェクトを判定する処理構造と、
を含むことを特徴とする画像内の略矩形のオブジェクトを検出する装置。
【請求項２０】
前記処理構造は、前記ランク付けするステップの前に、画像を更に処理することにより
、選択された候補矩形の破棄、近接する候補矩形のマージ、及び候補矩形の調節の中の少
なくとも１つを実行することを特徴とする請求項１９に記載の画像内の略矩形のオブジェ
クトを検出する装置。
【請求項２１】
前記処理構造は、前記画像を処理することにより、選択された候補矩形を破棄し、近接
する候補矩形をマージすると共に、候補矩形を調節することを特徴とする請求項２０に記
載の画像内の略矩形のオブジェクトを検出する装置。
【請求項２２】
画像内のバックグラウンド色を推定する装置であって、
前記画像を保存するメモリと、
前記メモリと通信している処理構造であって、前記画像を処理することにより、前記画
像のそれぞれのスキャンラインを類似した色のラインセグメントにセグメント化し、前記
類似した色のラインセグメントを色によってグループ化すると共に、前記グループの前記
ラインセグメントに沿ったエッジピクセルに基づいてバックグラウンド色を推定する処理
構造と、を含むことを特徴とする画像内のバックグラウンド色を推定する装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、画像処理に関するものであり、更に詳しくは、画像内のオブジェク
トを検出する方法及び装置に関するものである。
【背景技術】
【０００２】
紙の文書、写真、及び／又は（例えば、デビット及びクレジットカードを含む）その他
のオブジェクトの画像をキャプチャすると共に、キャプチャした画像を電子ファイルに変
換するスキャナについては、当技術分野において周知である。このようなスキャナは、様
々な一般的且つ特定の使用法を具備しているが、最も一般的には、記録を統合し、ペーパ
ーレス作業環境を生成すると共に／又は、情報の電子的な伝送を円滑に実行するべく使用
されている。
【０００３】
スキャナは、その設計及び精巧度において様々なものが存在しているが、一般的には、
すべてのスキャナは、細長い光源と、スキャン対象であるオブジェクトの表面から反射さ
れた光を受光する格子状又は列状のセンサを有している。センサからのデータは、スキャ
ナソフトウェアの制御下において動作するプロセッサによって収集され、且つ、通常は、
ＪＰＥＧ、ＢＭＰ、又はＧＩＦフォーマットを有するデジタル画像ファイルとしてメモリ
内に保存される。スキャナがコンピュータ或いはローカル又はワイドエリアネットワーク
に対して結合されている場合には、デジタル画像ファイルは、通常、保存及び／又は更な
る処理のために、コンピュータ及び／又はネットワーク装置に対して供給されることにな
る。
【０００４】
いくつかの状況においては、スキャニングプロセスにおいて、複数のオブジェクトをス
キャナベッド上に配置した後にスキャンすることにより、結果的に複数のオブジェクトを
含む単一の画像を取得している。例えば、いくつかの写真をスキャナベッド上に配置した
後にスキャンすることにより、すべての写真を含む単一の画像を生成する。複数のオブジ
ェクトを有する画像を更に処理する必要がある場合には、画像内の個々のオブジェクトを
検出及び分離できるように画像を処理することが望ましいことが理解されよう。画像内の
オブジェクトを検出する多数の技法が考案されていることは、驚くに当たらない。
【０００５】
例えば、Ｓａｍｂｏｎｓｕｇｉ他に付与された米国特許第６３３５９８５号明細書は、
３つの矩形を設定することによって３つの時間的に連続したフレームを取り囲む方法につ
いて開示している。現在のフレームと第１基準フレームの間、並びに、現在のフレームと
第２基準フレームの間のフレーム間の差に基づいて差分画像を取得している。バックグラ
ウンド領域を多角形において個別に判定し、且つ、残りの領域をオブジェクト領域候補と
して選択している。オブジェクト領域候補間における交差部を取得することにより、現在
のフレーム内のオブジェクト領域を抽出することが可能である。
【０００６】
Ｚｈｏｕに付与された米国特許第６８９８３１６号明細書は、デジタル画像内の画像エ
リアを検出する方法について開示している。この方法においては、バックグラウンドエリ
アを表している第１画像領域とフォアグラウンドエリアを表している第２画像領域を画像
内において識別している。デジタル画像のピクセル値を使用することにより、勾配値を演
算している。勾配値に基づいたストロークのリストを定義し、且つ、ストロークのリスト
をマージしている。ストロークのリストを使用することにより、コーナーのリストを定義
し、且つ、コーナーのリストとストロークのリストを使用することにより、画像エリアの
境界を画している画像エリア矩形を定義している。画像エリア矩形を使用することにより
、デジタル画像からフォアグラウンドエリアを抽出するための境界ボックスを定義するこ
とが可能である。
【０００７】
Ｈｅｒｌｅｙに付与された米国特許出願公開第２００４／０１４６１９８号明細書は、
デジタル画像データを処理するためのオブジェクト検出及び抽出システムならびに方法に
ついて開示している。単一の画像内に含まれているオブジェクトを分離することにより、
これらのオブジェクトを個別のオブジェクトとして見なすことができるようにしている。
このオブジェクト検出及び抽出方法は、既知の形状の１つ又は複数のオブジェクト（矩形
オブジェクトなど）を含む画像を取得し、オブジェクトの数を、それらのサイズ、向き、
及び位置と共に見出している。具体的には、このオブジェクト検出及び抽出方法は、１つ
又は複数のオブジェクトを含む画像内のそれぞれのピクセルを分類することにより、ピク
セル分類データを取得している。画像関数を定義することによってピクセル分類データを
処理し、且つ、画像関数内の不一致又はギャップに基づいて画像をサブ画像に分割してい
る。サブ画像のそれぞれを処理することにより、それぞれのオブジェクトごとに、サイズ
及び向きを判定している。
【０００８】
Ｃｈｅｌｌａｐｉｌｌａ他に付与された米国特許出願公開第２００４／０１８１７４９
号明細書は、電子画像から電子フォームに入力するコンピュータ実装された方法及び装置
について開示している。まず、電子画像内のオブジェクトのサイズ、向き、及び位置を、
そのオブジェクトに対応する画像内のピクセルからの情報要素と共に識別している。電子
フォームのフィールドを、識別された情報要素と共に、グラフィカルユーザーインターフ
ェイスを通じてユーザーに対して表示している。情報要素を、タグが付加された異なる情
報タイプのグループに解析している。タグが付加されたグループによって電子フォームの
フィールドの中の少なくともいくつかのものに入力することにより、入力済みのフォーム
を生成している。これらの入力済みのフィールドは、グラフィカルユーザーインターフェ
イスを通じて編集可能である。
【０００９】
Ｊｏｎｅｓ他に付与された米国特許出願公開第２００４／０２５８３１３号明細書は、
画像内の特定のオブジェクトを検出する方法について開示している。この方法においては
、画像プレーンとの関係における任意のオブジェクトの向きを判定し、且つ、判定された
向きに従って、複数の向き及びオブジェクト固有のクラシファイアの中の１つを選択して
いる。選択された向き及びオブジェクト固有のクラシファイアにより、任意のオブジェク
トを特定のオブジェクトとして分類している。
【００１０】
Ｆｅｓｑｕｅｔ他に付与された米国特許出願公開第２００５／０１０５７６６号明細書
は、郵便ソート設備内において単一の郵便物及び複数のオーバーラップしている郵便物を
検出する方法について開示している。この方法においては、前方から観察した郵便物を表
す画像を分析し、且つ、実質的に一定の高さのアウトラインを具備した物品を認識するべ
くアウトライン抽出プロセスをそれぞれの画像に対して適用している。
【００１１】
Ａｒａｄｈｙｅ他に付与された米国特許出願公開第２００５／０１８０６３２号明細書
は、３次元シーンの画像内における視野の歪み、回転、及び／又はスケールの影響を補正
するためのシンボルの訂正及び認識装置及びこれに付随する方法について開示している。
この方法は、共通プレーン内に位置している基準領域を認識対象のシンボルと共に見出し
ている。基準領域は、仮定された（例えば、既知の又は標準的な）形状及び寸法を具備し
た平面的なオブジェクトの画像を表している。その形状内の少なくとも４つの容易に検出
可能な対応ポイントを見出している。次いで、シンボルの変換済みの画像を生成するべく
、仮定された基準領域の寸法に従って共通プレーンの画像を３次元において訂正している
。
【００１２】
Ｔｒｉｆｏｎｏｖ他に付与された米国特許出願公開第２００５／０１８０６３５号明細
書は、まず、画像内のサーチ領域を識別することにより、画像内の境界を判定する方法に
ついて開示している。サーチ領域内の画像の勾配をサーチ領域内の複数のカラー領域と共
に判定している。画像の勾配及び複数のカラー領域に基づいて境界を表しているアクティ
ブな輪郭線を生成している。
【００１３】
【特許文献１】米国特許第６８９８３１６号明細書
【非特許文献１】Ｃ．Ｊｕｎｇ他著の「Rectangle Detection Based On A Windowed Hough Transform」（Proceedings of the XVII Brazilian Symposium on Computer Graphics and Image Processing;1530-1834;2004）
【非特許文献２】Ｙ．Ｚｈｕ他著の「Automatic Particle Detection Through Efficient Hough Transforms」（IEEE Trans.on Medical Imaging;22(9);1053-1062;2003）
【非特許文献３】Ｚ．Ｙｕ他著の「Detecting Circular And Rectangular Particles Based On Geometric Feature Detection In Electron Micrographs」（Journal of Structural Biology;145,168-180;2004）
【非特許文献４】Ｃ．Ｈｅｒｌｅｙ著の「Recursive Method To Extract Rectangular Objects From Scans」（ICIP,vol.3 no.pp.III-989-92,14-17;2003）
【非特許文献５】Ｃ．Ｈｅｒｌｅｙ著の「Recursive Method To Detect And Segment Multiple Rectangular Objects In Scanned Images」（Technical report MSR-TR-2004-01,Microsoft Research;2004）
【非特許文献６】Ｃ．Ｈｅｒｅｌｙ著の「Efficient Inscribing Of Noisy Rectangular Objects In Scanned Images」（ICIP,Vol.4,2399-2402,24-27;2004）
【発明の開示】
【発明が解決しようとする課題】
【００１４】
前述の参考文献は、画像内のオブジェクトを検出する様々な方法及びシステムについて
開示しているが、改善が望ましい。従って、画像内のオブジェクトを検出する新しい方法
及び装置を提供することが、本発明の１つの目的である。
【課題を解決するための手段】
【００１５】
従って、一態様においては、画像内の略矩形のオブジェクトを検出する方法が提供され
ており、この方法は、画像内の検出されたコーナーに基づいて画像内の候補矩形を判定す
るステップと、弁別ファクタの組に基づいて候補矩形をランク付けするステップと、ラン
ク付けされた候補矩形に基づいて画像内のオブジェクトを検出するステップと、を有して
いる。
【００１６】
一実施例においては、ランク付けステップの前に、選択済みの候補矩形を破棄している
。選択済みの候補矩形は、高位にランク付けされた候補矩形と閾値である量を上回ってオ
ーバーラップしている場合に、破棄される。ランク付けステップの前に、近接した候補矩
形をマージすることが可能であり、且つ、候補矩形の境界を調節することが可能である。
【００１７】
一実施例においては、判定ステップは、画像のバックグラウンド色を推定するステップ
と、推定されたバックグラウンド色に基づいてオブジェクトの境界を画しているエッジを
検出するステップと、エッジを調べることによってコーナーを表す交差しているエッジを
検出するステップと、矩形の頂点を定義しているコーナーをグループ化することによって
候補矩形を判定するステップと、を有している。一実施例における弁別ファクタの組は、
候補矩形に近接したピクセルと関連付けられたエッジ及び色情報に基づいたものである。
【００１８】
別の態様によれば、画像内のバックグラウンド色を推定する方法が提供されており、こ
の方法は、画像のそれぞれのスキャンラインを類似した色のラインセグメントにセグメン
ト化するステップと、類似した色のセグメントを色によってグループ化するステップと、
グループのラインセグメントに沿ったエッジピクセルに基づいてバックグラウンド色を推
定するステップと、を有している。
【００１９】
一実施例においては、グループ化するステップにおいて、閾値である長さを上回る類似
した色のラインセグメントのみをグループ化している。推定ステップは、エッジピクセル
の数及び強度に基づいて実行されている。推定ステップは、閾値であるラインセグメント
数を具備した類似した色のラインセグメントのグループを判定するステップと、それぞれ
の類似した色のラインセグメントのグループの平均色を候補バックグラウンド色として指
定するステップと、それぞれの候補バックグラウンド色ごとに、その候補バックグラウン
ド色を表すグループのラインセグメントに沿ってエッジピクセルを検出するステップと、
エッジピクセルによって定義されたエッジの強度を算出するステップと、エッジピクセル
カウント及びエッジ強度に基づいて、候補バックグラウンド色の中の１つをバックグラウ
ンド色の推定値として選択するステップと、を有している。
【００２０】
更に別の態様によれば、画像内のオブジェクトを検出する装置が提供されており、この
装置は、画像を保存するメモリと、このメモリと通信している処理構造であって、画像を
処理することにより、画像内の検出されたコーナーに基づいて候補矩形を判定し、弁別フ
ァクタの組に基づいて候補矩形をランク付けすると共に、ランク付けされた候補矩形から
画像内のオブジェクトを判定する処理構造と、を有している。
【００２１】
更に別の態様によれば、画像内のバックグラウンド色を推定する装置が提供されており
、この装置は、画像を保存するメモリと、このメモリと通信している処理構造であって、
画像を処理することにより、それぞれのスキャンラインを類似した色のラインセグメント
にセグメント化し、類似した色のラインセグメントを色によってグループ化すると共に、
これらのグループのラインセグメントに沿ったエッジピクセルに基づいてバックグラウン
ド色を推定する処理構造と、を有している。
【００２２】
［適用例１］前述の課題を解決するため、画像内の略矩形のオブジェクトを検出する方
法は、前記画像内の検出されたコーナーに基づいて前記画像内の候補矩形を判定するステ
ップと、弁別ファクタの組に基づいて前記候補矩形をランク付けするステップと、前記ラ
ンク付けされた候補矩形に基づいて前記画像内のオブジェクトを検出するステップとを含
むことを要旨とする。
【００２３】
［適用例２］また、画像内の略矩形のオブジェクトを検出する方法は、前記ランク付け
するステップの前に、選択された候補矩形を破棄するステップを更に含むことをその要旨
とする。
【００２４】
［適用例３］また、画像内の略矩形のオブジェクトを検出する方法は、選択された候補
矩形は、高位にランク付けされた候補矩形と閾値である量を上回ってオーバーラップして
いる場合に、破棄されることをその要旨とする。
【００２５】
［適用例４］また、画像内の略矩形のオブジェクトを検出する方法は、前記ランク付け
するステップの前に、近接する候補矩形をマージするステップを更に含むことをその要旨
とする。
【００２６】
［適用例５］また、画像内の略矩形のオブジェクトを検出する方法は、前記弁別ファク
タの組は、前記候補矩形に近接したピクセルと関連付けられた少なくともエッジ及び色情
報に基づいていることをその要旨とする。
【００２７】
［適用例６］また、画像内の略矩形のオブジェクトを検出する方法は、前記ランク付け
するステップの前に、前記候補矩形の境界を調節するステップを更に含むことをその要旨
とする。
【００２８】
［適用例７］また、画像内の略矩形のオブジェクトを検出する方法は、前記調節するス
テップにおいて、前記候補矩形を定義している前記コーナーの位置を前記候補矩形を取り
囲んでいる近傍部分内において調節することをその要旨とする。
【００２９】
［適用例８］また、画像内の略矩形のオブジェクトを検出する方法は、前記判定するス
テップは、前記画像のバックグラウンド色を推定するステップと、前記推定されたバック
グラウンド色に基づいて前記オブジェクトの境界を画しているエッジを検出するステップ
と、前記エッジを調べることにより、コーナーを表す交差しているエッジを検出するステ
ップと、矩形の頂点を定義しているコーナーをグループ化することにより、前記候補矩形
を判定するステップと、を含むことをその要旨とする。
【００３０】
［適用例９］また、画像内の略矩形のオブジェクトを検出する方法は、前記ランク付け
するステップの前に、前記候補矩形の境界を調節するステップを更に含むことをその要旨
とする。
【００３１】
［適用例１０］また、画像内の略矩形のオブジェクトを検出する方法は、前記ランク付
けするステップの前に、選択された候補矩形を破棄するステップを更に含むことをその要
旨とする。
【００３２】
［適用例１１］また、画像内の略矩形のオブジェクトを検出する方法は、選択された候
補矩形は、高位にランク付けされた候補矩形と閾値である量を上回ってオーバーラップし
ている際に、破棄されることをその要旨とする。
【００３３】
［適用例１２］また、画像内の略矩形のオブジェクトを検出する方法は、前記ランク付
けするステップの前に、近接する候補矩形をマージするステップを更に含むことをその要
旨とする。
【００３４】
［適用例１３］また、画像内のバックグラウンド色を推定する方法は、前記画像のそれ
ぞれのスキャンラインを類似した色のラインセグメントにセグメント化するステップと、
前記類似した色のラインセグメントを色によってグループ化するステップと、前記グルー
プの前記ラインセグメントに沿ったエッジピクセルに基づいて前記バックグラウンド色を
推定するステップと、を含むことをその要旨とする。
【００３５】
［適用例１４］また、画像内のバックグラウンド色を推定する方法は、前記グループ化
するステップにおいて、閾値である長さを上回る類似した色のラインセグメントのみをグ
ループ化することをその要旨とする。
【００３６】
［適用例１５］また、画像内のバックグラウンド色を推定する方法は、前記推定するス
テップは、エッジピクセルの数及び強度に基づいて実行されることをその要旨とする。
【００３７】
［適用例１６］また、画像内のバックグラウンド色を推定する方法であって、前記推定
するステップは、閾値であるラインセグメント数を具備した前記類似した色のラインセグ
メントのグループを判定するステップと、それぞれの前記類似した色のラインセグメント
のグループの平均色を候補バックグラウンド色として指定するステップと、それぞれの候
補バックグラウンド色ごとに、その候補バックグラウンド色を表す前記グループの前記ラ
インセグメントに沿ってエッジピクセルを検出し、且つ、前記エッジピクセルによって定
義されたエッジの強度を算出するステップと、エッジピクセルカウント及びエッジ強度に
基づいて前記候補バックグラウンド色の中の１つを前記バックグラウンド色として選択す
るステップと、を含むことをその要旨とする。
【００３８】
［適用例１７］また、コンピュータプログラムを含むコンピュータ可読媒体は、適用例
１に記載の前記方法を実行するプログラムコードを含むことをその要旨とする。
【００３９】
［適用例１８］また、コンピュータプログラムを含むコンピュータ可読媒体は、適用例
１３に記載の前記方法を実行するプログラムコードを含むことをその要旨とする。
【００４０】
［適用例１９］また、画像内の略矩形のオブジェクトを検出する装置であって、前記画
像を保存するメモリと、前記メモリと通信している処理構造であって、前記画像内の検出
されたコーナーに基づいて前記画像を処理することにより、候補矩形を判定し、弁別ファ
クタの組に基づいて前記候補矩形をランク付けすると共に、前記ランク付けされた候補矩
形から前記画像内のオブジェクトを判定する処理構造と、を含むことをその要旨とする。
【００４１】
［適用例２０］また、画像内の略矩形のオブジェクトを検出する装置は、前記処理構造
は、前記ランク付けするステップの前に、画像を更に処理することにより、選択された候
補矩形の破棄、近接する候補矩形のマージ、及び候補矩形の調節の中の少なくとも１つを
実行することをその要旨とする。
【００４２】
［適用例２１］また、画像内の略矩形のオブジェクトを検出する装置は、前記処理構造
は、前記画像を処理することにより、選択された候補矩形を破棄し、近接する候補矩形を
マージすると共に、候補矩形を調節することをその要旨とする。
【００４３】
［適用例２２］また、画像内のバックグラウンド色を推定する装置は、前記画像を保存
するメモリと、前記メモリと通信している処理構造であって、前記画像を処理することに
より、前記画像のそれぞれのスキャンラインを類似した色のラインセグメントにセグメン
ト化し、前記類似した色のラインセグメントを色によってグループ化すると共に、前記グ
ループの前記ラインセグメントに沿ったエッジピクセルに基づいてバックグラウンド色を
推定する処理構造と、を含むことをその要旨とする。
【発明を実施するための最良の形態】
【００４４】
以下、添付の図面を参照し、実施例について更に詳しく説明することとする。まず、図
１を参照すれば、入力デジタル画像内のオブジェクトを検出する装置が示されており、こ
れは、全体として装置２０によって識別されている。この実施例においては、装置２０は
、例えば、パーソナルコンピュータ又はその他の好適な処理装置などの処理構造によって
実施されている。装置２０は、処理ユニット２４、ＲＡＭ（Random Access Memory）２８
、不揮発性メモリ３２、通信インターフェイス３６、入力インターフェイス４０、及び出
力インターフェイス４４を有しており、これらは、いずれも、ローカルバス４８上におけ
る通信状態にある。処理ユニット２４は、不揮発性メモリ３２内に保存されているオブジ
ェクト検出アプリケーションを実行している。装置２０は、通信インターフェイス３６を
介してネットワーク又はサーバーに結合可能である。入力インターフェイス４０は、ユー
ザーによるオブジェクト検出アプリケーションとのやり取りを実現するべく、キーパッド
、マウス、及び／又はその他の入力装置を有している。又、入力インターフェイス４０は
、オブジェクト検出のための分析対象となる画像をキャプチャするべく、スキャナをも包
含可能である。出力インターフェイス４４は、オブジェクト検出の結果を視覚的に提示す
ると共に、オブジェクト検出アプリケーションの設定を表示することによってユーザーに
よるそれらの調節を実現するディスプレイを有している。
【００４５】
図２は、入力デジタル画像内のオブジェクトを検出するべく、オブジェクト検出アプリ
ケーションを実行した際に装置２０によって実行される概略的なステップを示している。
この実施例においては、装置２０は、それぞれの入力画像を処理することにより、入力画
像内の略矩形の写真の存在を検出している。まず、入力画像のバックグラウンド領域の色
を推定し、且つ、入力画像内の写真の輪郭を描いているエッジを検出している（ステップ
Ｓ１１０）。次いで、検出されたエッジに沿ったエッジピクセルをグループ化することに
より、ラインセグメントを形成し、且つ、形成されたラインセグメントをリスト内に入力
している（ステップＳ１２０）。次いで、リスト内のラインセグメントをグループ化する
ことにより、直角のコーナーを形成し、且つ、候補矩形の頂点を定義している直角のコー
ナーのグループを判定している（ステップＳ１３０）。次いで、略一致している候補矩形
をマージしている（ステップＳ１４０）。次いで、残りの候補矩形を評価することにより
、真の候補矩形と偽の候補矩形を弁別し、且つ、真の候補矩形をランク付けしている（ス
テップＳ１５０）。次いで、高位にランク付けされた候補矩形とオーバーラップしている
低位にランク付けされた候補矩形を破棄している。（ステップＳ１６０）。次いで、残り
の候補矩形のラインセグメントを使用することにより、ステップＳ１２０において生成さ
れたラインセグメントリストを補完している（ステップＳ１７０）。所望のレベルの信頼
性を具備する入力画像内の写真に対応した候補矩形が判定されるまで、ステップＳ１３０
からステップＳ１７０までの間を反復的に実行している（ステップＳ１８０）。
【００４６】
この実施例においては、入力画像のバックグラウンド領域が略均一な色を有しており、
且つ、入力画像内の写真の境界が、画像のバックグラウンド内のエッジと識別可能な違い
を具備しており、この結果、写真の輪郭を描いているエッジが入力画像内のその他のエッ
ジとの関係において強力であるものと仮定されている。これらの仮定を利用すると共に、
入力画像内の写真の概略サイズ、形状、及び数が付与された場合に、入力画像内のそれぞ
れの写真の境界を正確に推定することが可能である。
【００４７】
ステップＳ１１０においては、低レベルな画像の特徴の発見的な調査に基づいた５ステ
ップの単一パスの方法を使用することにより、バックグラウンド領域色を推定している。
具体的には、まず、入力画像のスキャンライン（即ち、ピクセル行及びピクセル列）を均
一に着色されたセグメントにセグメント化している。次いで、エッジの検出を実行し、且
つ、このエッジ情報を使用することによって候補バックグラウンド領域色を表すラインセ
グメント色を選択している。次いで、エッジ情報をスキャンラインセグメント化情報と組
み合わせることにより、いずれの候補バックグラウンド領域色が真のバックグラウンド領
域色であるのかを判定している。以下、図３〜図５を参照し、前述の方法に関する更なる
詳細について説明することとする。
【００４８】
まず、図３を参照すれば、ステップＳ１１０におけるバックグラウンド領域色の推定及
びエッジの検出において実行されるステップが更に詳しく示されている。まず、入力画像
のスキャンラインを略同一の色のラインセグメントにパーティション化している（ステッ
プＳ３１０）。多数の長いバックグラウンド色のラインセグメントが存在するものと仮定
することにより、閾値を上回る長さを具備したラインセグメントを判定し、且つ、これら
を色によってグループ化している（ステップＳ３１２）。次いで、閾値を上回る数のライ
ンセグメントを具備したラインセグメントのグループを判定し（ステップＳ３１４）、こ
れらのラインセグメントのグループと関連付けされた色を候補バックグラウンド領域色と
して指定している（ステップＳ３１６）。それぞれの候補バックグラウンド領域色ごとに
、入力画像内のバックグラウンド領域と写真の間の境界上の関連付けられたラインセグメ
ントグループのラインセグメントに沿ったエッジピクセルを検出している（ステップＳ３
１８）。次いで、エッジピクセルによって定義されたエッジの強度を算出している（ステ
ップＳ３２０）。次いで、指定された範囲内のエッジピクセルカウントを具備し、且つ、
その平均エッジ強度が最大であるラインセグメントグループと関連付けられた色となるよ
うに、真のバックグラウンド領域色を判定している（ステップＳ３２２）。
【００４９】
次に、図４及び図５を参照し、ステップＳ３１０におけるスキャンラインの類似した色
のラインセグメントへのパーティション化について説明することとする。図４は、ピクセ
ルｋ1〜ｋ3を有する模範的なスキャンライン４００を示している。図示されているように
、この例におけるスキャンライン４００は、それぞれ、ピクセルｋ2及びピクセルｋ2＋１
によって分離された個別の色を有する２つのラインセグメントｓ1及びラインセグメント
ｓ2を具備している。ラインセグメントｓ1は、ピクセルｋ1〜ｋ2を有しており（ｓ1＝［
ｋ1，ｋ2］）、ラインセグメントｓ2は、ピクセルｋ2＋１〜ｋ3を有している（ｓ2＝［ｋ
2＋１，ｋ3］）。それぞれのピクセルｋの赤、緑、青（ＲＧＢ）の色ベクトルをｃｏｌｏ
ｒ（ｋ）によって表している。ラインセグメントｓ1及びラインセグメントｓ2上のピクセ
ルｋの色は、平均色Ｃsを中心として正規分布しているものと仮定されている。又、色の
標準偏差σは、ラインセグメントｓ1の平均色Ｃ1とラインセグメントｓ2の平均色Ｃ2の間
の差よりも格段に小さいものと仮定されている。
【００５０】
ラインセグメントｓ1及びラインセグメントｓ2における平均色Ｃ1及び平均色Ｃ2は、そ
れぞれ、次の式（１）及び式（２）によって表現される。
【００５１】
【数１】
2008171417.tif 000003
【００５２】
ラインセグメントｓ1及びラインセグメントｓ2における標準偏差σ1及び標準偏差σ2は
、次の式（３）及び式（４）によって表現される。
【００５３】
【数２】
2008171417.tif 000004
【００５４】
ラインセグメントｓ1及びラインセグメントｓ2の色ベクトルは、次の式（５）及び式（
６）に従って分布している。
【００５５】
【数３】
2008171417.tif 000005
ここで、ｋ1＜ｋ2＜ｋ3であり、Ｃ1≠Ｃ2であり、σi〜Ｎ（０，σ）であり、且つ、
【００５６】
【数４】
2008171417.tif 000006
である。
【００５７】
ラインセグメントの色の変化を検出するべく、次の式（７）によるスパン平均関数に基
づいてスパン値ΣSPAN（［ｉ，ｊ］）を定義している。
【００５８】
【数５】
2008171417.tif 000007
【００５９】
式（７）から、スパン差ΔSPAN＝ΣSPAN（［ｋ1，ｊ＋１］）−ΣSPAN（［ｋ1，ｊ］）
は、ｊ＜ｋ2において、ゼロベクトルを中心として対称に分布していることがわかる。又
、スパン差ΔSPANは、ｊ≧ｋ2においては、ｋ1（Ｃ2−Ｃ1）／ｊ2を中心として対称に分
布している。この結果、ｊ≧ｋ2において、スパン差ΔSPANは、ゼロから発散している。
【００６０】
従って、以上ことから、大きな非ゼロのスパン差ΔSPANを識別することにより、それぞ
れのスキャンラインに沿った色の変化を検出することが可能であることが理解されよう。
次に、図５を参照すれば、スキャンラインの調査においてそれに沿った色の変化を検出す
るべく実行されるステップが示されている。まず、ピクセルｉにおいて始まり、且つ、ピ
クセルｊにおいて終了しているスキャンライン上においてラインセグメントｓを指定して
いる（即ち、ｓ＝［ｉ，ｊ］である）（ステップＳ５００）。次いで、式（７）に従って
、ｊ＝ｉ＋１においてスパン値ΣSPAN（［ｉ，ｊ］）を算出している（ステップＳ５０５
）。次いで、スパン差ΔSPAN＝ΣSPAN（［ｉ，ｊ］）−ΣSPAN（［ｉ，ｊ−１］）を算出
し（ステップＳ５１０）、且つ、偏差σを推定している（ステップＳ５１５）。次いで、
現在のスパン差ΔSPANを以前の反復において算出されたスパン差ΔSPANと比較することに
より、この差がステップＳ５１５において演算された偏差σを上回っているかどうかを判
定している（ステップＳ５２０）。差が偏差σを上回っている場合には、カウントを増分
することになる（ステップＳ５２５）。次いで、チェックすることにより、カウントが閾
値に到達しているかどうかを判定している（ステップＳ５３０）。この例においては、閾
値は３に等しい。ステップＳ５３０において、カウントが閾値に等しくない場合には、ラ
インセグメントの最終ピクセル位置ｊを増分し（ステップＳ５３５）、本プロセスは、次
に反復のためにステップＳ５０５に戻ることになる。ステップＳ５３０において、カウン
トが閾値に到達している場合には、最終ピクセル位置ｊ−２（即ち、差が最初に偏差σを
上回っていると判定された最終ピクセル位置）においてスキャンラインに沿った色の変化
を検出することになる（ステップＳ５４０）。この最終ピクセル位置は、スキャンライン
に沿った次のラインセグメントの開始点を指定すると共に以前のラインセグメントの終点
をマーキングしている。この時点において、カウントをゼロ化すると共に（ステップＳ５
４５）、本プロセスは、ステップＳ５００に戻り、ここで、次のラインセグメントを指定
することになる。ステップＳ５２０において、差が偏差σを上回っていない場合には、カ
ウントをゼロ化することになる（ステップＳ５５０）。次いで、次の反復のためにステッ
プＳ５０５に戻る前に、最終ピクセル位置ｊをステップＳ５３５において増分している。
【００６１】
【表１】
2008171417.tif 000008
【００６２】
表１は、前述のラインセグメント色の変化の検出方法の擬似コード実装である。スキャ
ンラインに沿った色の変化を検出することによって雑音に起因した偽の色の変化の検出を
回避するには、３つの連続した非ゼロのスパン差ΔSPANが必要である。この非ゼロのスパ
ン差ΔSPANの数は、偽の色の変化の検出をほとんど伴わない正確な結果をもたらすことが
判明している。この方式におけるスキャンラインに沿った色の変化の検出により、雑音に
起因して誤りを生成し易いコムフィルタソリューションの使用と関連した欠点が克服され
る。
【００６３】
候補バックグラウンド領域色を指定する際には、バックグラウンド領域色が、多数の長
い類似した色のラインセグメントによって表されるものと仮定されている。ステップＳ３
１２において類似した色のラインセグメントを分類するべく、３つの等しいサイズのアレ
イ、即ち、投票アレイ、色アレイ、及び分散アレイを設定している。それぞれのアレイの
対応するセルをそれぞれのラインセグメントの平均色に対して割り当てている。この実施
例においては、色は、２４ビットのＲＢＧであり、且つ、（［Ｒ／１６］，［Ｇ／１６］
，［Ｂ／１６］）によって表現されるものと仮定している。閾値である長さよりも長いそ
れぞれのラインセグメントごとに、ラインセグメント内のピクセルの数（「ｖｏｔｅｓ（
投票数）」）を判定し、これをそのラインセグメントの平均色に対応した投票アレイのセ
ルに入力している。
【００６４】
更には、閾値である長さよりも長いそれぞれのラインセグメントごとに、次の式（８）
に従ってポイント推定値を算出すると共に、次の式（９）に従って色拡散推定値を算出し
ている。
【００６５】
【数６】
2008171417.tif 000009
【００６６】
算出されたポイント推定値をラインセグメントの平均色に対応した色アレイのセルに入
力し、且つ、算出された色拡散推定値をラインセグメントの平均色に対応した分散アレイ
のセルに入力している。表２は、前述の手順の擬似コード実装である。
【００６７】
【表２】
2008171417.tif 000010
【００６８】
閾値である長さを上回るすべてのラインセグメントの処理と、投票、色、及び分散アレ
イのセルの入力が完了したら、閾値を上回る数のラインセグメントを具備したラインセグ
メントグループを判定し（ステップＳ３１４）、且つ、これらのラインセグメントグルー
プから、投票アレイの最高位の１０個の入力済みのセルを選択している。これらの選択さ
れた投票アレイのセルと関連付けられたラインセグメントグループの平均色を候補バック
グラウンド領域色として指定している（ステップＳ３１６）。色アレイの対応したセル内
のポイント推定値と分散アレイの対応したセル内の色拡散推定値を投票アレイセル内の投
票値によって除算することにより、選択された投票アレイのセルのそれぞれの平均色ベク
トル及び分散を算出している。次いで、選択された投票アレイのセルと関連付けられたラ
インセグメントグループの平均色を調べてエイリアシングを識別している。選択された投
票アレイのそれぞれのセルは、２６個の隣接セルを具備している。エイリアシングの識別
においては、選択された投票アレイのそれぞれのセルと関連付けられたラインセグメント
グループの平均色をその隣接する投票アレイのそれぞれのセルと関連付けられたラインセ
グメント平均色と比較することにより、色が同一であるかどうかを判定している。隣接す
るセル内の中心に位置する２つの色Ｃは、次式が成立する場合に、同一の色であると見な
されている。
【００６９】
【数７】
2008171417.tif 000011
ここで、Ｃ（ｃｅｌｌx）は、ｃｅｌｌxの平均色ベクトルであり、σは、色成分の標準
偏差であり、βは、パラメータであって、この例においては、０．７である。
【００７０】
投票アレイのセルがその隣接する投票アレイのセルの中の１つと同一の色であると判定
された際に、平均ラインセグメント色に対応した３つのアレイのそれぞれのセルをマージ
している。セルのマージは、次式に従って実行している。
【００７１】
【数８】
2008171417.tif 000012
【００７２】
セルのマージが完了したら、候補バックグラウンド領域色を、それらの候補バックグラ
ウンド領域色を表すラインセグメントグループと関連付けられた投票アレイのセル内の投
票値に基づいて、順番にランク付けしている。最高位の投票値と関連付けられた候補バッ
クグラウンド領域色が、真の候補バックグラウンド領域色となる可能性が最も高いと見な
されている。低位の投票値と関連付けられた候補バックグラウンド領域色は、真の候補バ
ックグラウンド領域色となる可能性が低いと見なされている。次いで、まず、最高位にラ
ンク付けされた候補バックグラウンド領域色から始めて、それぞれの候補バックグラウン
ド領域色を表すラインセグメントグループと関連付けられた画像ピクセルを処理している
（ステップＳ３１８）。このステップにおいては、候補バックグラウンド領域色を表すグ
ループ内のラインセグメントに対応した画像ピクセルを識別している。具体的には、画像
のピクセルｐは、次式が成立する場合に、バックグラウンド領域色Ｃを有するものと判定
されている。
【００７３】
【数９】
2008171417.tif 000013
この実施例においては、パラメータδは、良好な性能をもたらすことが判明した１０に
等しくなっている。
【００７４】
候補バックグラウンド領域色に対応した画像ピクセルの識別が完了したら、エッジの検
出を実行し、且つ、入力画像に対応したエッジマップを生成している。エッジピクセルは
、それらと左側の最も近いピクセル又は下側の最も近いピクセルの間に逆の状態（バック
グラウンド又は非バックグラウンド）を具備するものとして定義されている。具体的には
、候補バックグラウンド領域色Ｃが付与された場合に、ピクセルｐは、次式が成立した場
合に、エッジピクセルであると見なされている。
【００７５】
【数１０】
2008171417.tif 000014
ここで、ピクセルｐlは、ピクセルｐの左側のピクセルであり、ピクセルｐbは、ピクセ
ルｐの下側のピクセルである。
【００７６】
従って、ピクセルｐがエッジピクセルであると見なされるためには、次の条件の中の１
つが真でなければならない。
ピクセルｐは、バックグラウンド領域色を有しているが、ピクセルｐlは、有していな
い。
ピクセルｐlは、バックグラウンド領域色を有しているが、ピクセルｐは、有していな
い。
ピクセルｐは、バックグラウンド領域色を有しているが、ピクセルｐbは、有していな
い。
ピクセルｐbは、バックグラウンド領域色を有しているが、ピクセルｐは、有していな
い。
【００７７】
図９（ａ）及び図９（ｂ）は、その内部に２つの矩形写真を具備した入力画像とエッジ
検出の結果として生成された対応するエッジマップを示している。前述のプロセスは、バ
ックグラウンド色を有する及びバックグラウンド色を有していない領域の間の境界上にお
いてのみエッジが検出されることを保証している。非エッジピクセルにはゼロのエッジ強
度を割り当てている。残りのエッジピクセルについては、次の式（１０）に従ってピクセ
ルのエッジ強度を算出している（ステップＳ３２０）。
【００７８】
【数１１】
2008171417.tif 000015
この結果、すべての有意なエッジを識別可能なエッジ強度の非線形推定が得られること
になる。この実施例においては、パラメータΔは、１２７に等しい。この値は、良好な性
能をもたらすことが判明している。
【００７９】
候補バックグラウンド領域色を表すそれぞれのラインセグメントグループの画像ピクセ
ルを前述の方式において処理した後に、エッジピクセルの数とそれぞれの候補バックグラ
ウンド領域色と関連付けられたエッジピクセルの平均強度を使用することにより、真のバ
ックグラウンド領域色を判定している。入力画像が２つを上回る数の標準サイズの写真を
その内部に具備している際には、バックグラウンド領域色のラインセグメントは、短くな
ると共に数が少なくなる傾向を有している。この結果、ラインセグメント情報のみを使用
した場合には、信頼性が低くなる。真のバックグラウンド領域色を選択する際には、エッ
ジピクセル数及び強度情報を信頼できることが判明している。真のバックグラウンド領域
色を判定するには、まず、予想されるエッジピクセルカウント値に最も近いエッジピクセ
ルカウントを具備するラインセグメントグループによって表された候補バックグラウンド
領域色Ｘを選択している。例えば、７９×１０９の画像の場合には、予想されるエッジピ
クセルカウントは、５００に等しい。選択された候補バックグラウンド領域色Ｘにおいて
、選択された候補バックグラウンド領域色Ｘのエッジピクセルカウントの２００以内のエ
ッジピクセルカウントを具備すると共に最高の平均エッジ強度を具備したラインセグメン
トグループによって表される候補バックグラウンド領域色を、真のバックグラウンド領域
色として判定している。
【００８０】
【表３】
2008171417.tif 000016
表３は、前述の手順の擬似コード実装である。このようにして、連続的であり、且つ、
予想されたサイズのシャープな境界エッジを形成するバックグラウンド領域の高度に多元
的な色を真のバックグラウンド領域色として選択している。
【００８１】
ステップＳ１２０におけるラインセグメントを形成するためのエッジピクセルのグルー
プ化は、エッジピクセルとしてのその特徴によって（この場合には、エッジ強度によって
）ラインセグメント上のピクセルに対して重み付けする変形ＴＬＳ（Total Least Square
）法を使用して実現されている。ポイントの組からラインセグメントを判定する非変形Ｔ
ＬＳ法は、楕円をポイントの組に対して統計的にフィッティングし、楕円の長軸に対する
楕円の短軸の比率が閾値を下回っている際に楕円の長軸をラインセグメントとして指定す
るステップに類似している。０．３に等しい閾値が有効であることが証明されている。変
形ＴＬＳ法は、楕円の長軸軸から離れた小さな重みを有するピクセルのコストが、重みが
大きい場合よりも小さいという点が異なっている。このピクセルの相対的に弱い固有値は
、楕円軸の比率を示している。
【００８２】
ステップＳ１２０におけるエッジピクセルのラインセグメントへのグループ化の際には
、まず、空間的に接続されたエッジピクセルの小さなグループを選択している（この場合
には、８つのエッジピクセルである）。前述の変形ＴＬＳ法を使用することにより、エッ
ジピクセルをラインセグメントに対してフィッティングしている。この方法においては、
エッジピクセルの座標の重み付けされた共分散行列のメイジャー固有ベクトルを演算して
いる。重み付けされた共分散行列のマイナー固有値が閾値を上回る時点まで、ラインセグ
メントに近接し、且つ、これに沿って位置している隣接ピクセルをグループに追加してい
る。このプロセスは、ＭｃＬａｕｇｈｌｉｎ他著の「The Hough Transform Versus the U
pWrite」（IEEE Trans.On PAMI,Vol.20,No 4,April 1998）という名称の出版物に開示さ
れているものに類似しており、この内容は、本引用により、本明細書に包含される。
【００８３】
ステップＳ１３０においてコーナーを検出する際には、グループ内のラインセグメント
を調べることにより、閾値である距離内のラインセグメントのペアを検出している。この
実施例においては、閾値である距離は、２５ピクセルである。それぞれの検出されたライ
ンセグメントのペアごとに、ラインセグメントを調べることにより、ラインセグメントが
略直角を形成しているかどうか（従って、コーナーを表しているかどうか）を判定してい
る。この実施例においては、コーナーを表していると見なされるためには、ペアのライン
セグメントが、直角（９０度）の１／１０ラジアン以内に位置していなければならない。
ラインセグメントがコーナーを表していると考えられる場合には、それらのラインセグメ
ントの実際の又は推定された交差部に、コーナーを仮定している。このコーナーに対して
、次式に従い、ラインセグメントペアの間の角度の二等分線に関連したコーナーの向きを
割り当てている。
【００８４】
【数１２】
2008171417.tif 000017
【００８５】
これらの複数の角度は、入力画像が最大４枚の写真をその内部に具備しており、４枚の
写真が１つの検出されたコーナーの近傍において出会っているという可能性を考慮したも
のである。
【００８６】
図６に示されているように、ステップＳ１４０においては、まず、検出されたコーナー
を使用することにより、候補矩形を判定しているステップＳ７１０。コーナーのペアの向
きが反対である場合に、候補矩形を判定している。多くの例においては、入力画像内にお
いて複数の候補矩形を判定している。候補矩形の判定が完了したら、選択された候補矩形
をマージして複写を除去している（ステップＳ７２０）。この例においては、２つの候補
矩形の対応する頂点における最大距離差が２ピクセルである場合に、候補矩形が複写であ
ると判定している。
【００８７】
検出されたコーナーによって定義された候補矩形は、不正確である可能性があるため、
候補矩形を調節している（ステップＳ７３０）。候補矩形の調節においては、図７に示さ
れているように、候補矩形８１０の周りに、近傍部分８２０を設定している。この近傍部
分８２０の内部において、サーチを実行することにより、候補矩形の辺の調節済みの最良
の位置を見出している。このサーチは、候補矩形の辺近傍のエッジ強度、候補矩形の直ぐ
外側のピクセルの非バックグラウンデッドネス（non-backgroundedness）の尺度と候補矩
形の直ぐ内側のピクセルのバックグラウンデッドネス（backgroundedness）の尺度の間の
差、及び候補矩形の辺に跨る色エッジの強度に基づいたものである。
【００８８】
まず、それぞれの候補矩形の辺ごとに、３つの統計値としての第１統計値Ｓ１、第２統
計値Ｓ２、及び第３統計値Ｓ３を判定している。まず、エッジ検出の結果として生成され
たエッジマップを次の形態のガウスカーネルによって不鮮明化することにより、結果的に
得られる不鮮明化されたエッジマップＢＥＭ（ｘ，ｙ）を取得している。
【００８９】
【数１３】
2008171417.tif 000018
【００９０】
不鮮明化されたエッジマップは、第１統計値Ｓ１を定義している。結果的に得られた不
鮮明化されたエッジマップＢＥＭ（ｘ，ｙ）のピクセルは、候補矩形の辺が（ｘ，ｙ）の
近傍を通過する尤度を表している。図９（ｃ）は、不鮮明化が完了した後の図９（ｂ）の
エッジマップを示している。
【００９１】
ピクセルｐの非バックグラウンデッドネスを次の式（１１）に従って算出している。
【００９２】
【数１４】
2008171417.tif 000019
ここで、ｐｉｘｅｌ（ｉ）は、ｉ番目のＲＧＢ色ピクセルのコンポーネントであり、ｃ
（ｉ）は、バックグラウンド領域のｉ番目のＲＧＢ色のコンポーネントであり、σiは、
バックグラウンド領域色のｉ番目の標準偏差のコンポーネントである。
【００９３】
それぞれの候補矩形の辺ごとに、候補矩形の直ぐ外側及び直ぐ内側のピクセルのペア（
ａ，ｂ）の非バックグラウンデッドネススコアの平均差を判定することにより、第２統計
値Ｓ２を提供している。
【００９４】
次いで、すべてのピクセルのペア（ａ，ｂ）のデルタの平均を判定することにより、第
３統計値Ｓ３を定義しているが、ここで、デルタは、次のように定義されている。
【００９５】
【数１５】
2008171417.tif 000020
【００９６】
この実施例における前述の第１統計値Ｓ１、第２統計値Ｓ２、及び第３統計値Ｓ３は、
線分描画／追跡用のＢｒｅｓｅｎｈａｍのアルゴリズムに基づいた整数計算アルゴリズム
を使用して演算されている。
【００９７】
それぞれの候補矩形の辺について演算された３つの統計値により、ローカルサーチを実
行し、それぞれの候補矩形の辺の最良の場所を判定している。このプロセスにおいては、
Ｏ（Ｓ１，Ｓ２，Ｓ３）＝Ｓ１＋８Ｓ２＋１６Ｓ３という形態の目的関数を最適化してい
る。例えば、図８は、座標格子上における候補矩形の辺を示しており、この場合には、単
純化のために、辺は、ｘ軸に対して平行な状態において示されている。ローカルサーチに
おいては、反復的なサーチアルゴリズムを利用することにより、候補矩形の辺を移動させ
る必要があるかどうかを判定している。
【００９８】
サーチアルゴリズムに従って、４つの変数ｐ１〜ｐ４を次のように定義している。
【００９９】
【数１６】
2008171417.tif 000021
【０１００】
図７の候補矩形の辺を参照すれば、変数ｐ１がゼロを大幅に上回っている場合には、こ
の状況は、エッジｂがエッジｃのものよりも強力であることを意味していることから、コ
ーナーポイントｃ１を上方に移動させて目的関数Ｏを最適化する必要がある。変数ｐ２が
ゼロを大幅に上回っている場合には、この状況は、エッジｄがエッジｃのものよりも強力
であることを意味していることから、コーナーポイントｃ１を下方に移動させて目的関数
Ｏを最適化する必要がある。変数ｐ３がゼロを大幅に上回っている場合には、この状況は
、エッジｂがエッジｃのものよりも強力であることを意味していることから、コーナーポ
イントｃＮを上方に移動させて目的関数Ｏを最適化する必要がある。変数ｐ４がゼロを大
幅に上回っている場合には、この状況は、エッジｄがエッジｃのものよりも強力であるこ
とを意味していることから、コーナーポイントｃＮを下方に移動させて目的関数Ｏを最適
化する必要がある。前述の条件に基づいて、反復的な手順を実行することにより、矩形の
辺の端部を定義するコーナーポイントをプルアップ又はプルダウンして矩形の辺の位置を
調節している。
【０１０１】
【表４】
2008171417.tif 000022
表４は、この手順の擬似コード実装である。矩形の辺の位置の変化に伴って、或いは、
１０回の反復が完了する時点まで、候補矩形について反復を実行する。調節済みの候補矩
形の生成が完了したら、候補矩形の隣接する辺の間の角度を調べることにより、それらが
５度超だけ直角から逸脱していないことを保証している。調節済みの矩形を形成する隣接
している辺のいずれかが５度超だけ逸脱している場合には、未調節の候補矩形を使用する
。
【０１０２】
代替肢として、トレーニングされた機械学習プロセスを介して正確な矩形エッジを導出
することも可能である。機械学習プロセスは、変数として、前述の入力（即ち、矩形の辺
に跨った非バックグラウンドネス差）及び関連するエッジ強度を使用することが可能であ
る。
【０１０３】
候補矩形のそれぞれの調節が完了したら、候補矩形をランク付けしている（ステップＳ
７４０）。ランク付けステップにおいては、候補矩形に近接したピクセルと関連付けられ
た少なくともエッジ及び色情報に基づいた弁別ファクタを使用している。この実施例にお
いては、
（i）候補矩形上又はこの近傍に配置された強力なエッジポイント
（ii）候補矩形の内部に位置するラインセグメントの長さの二乗合計
（iii）候補矩形内部のバックグラウンド色を有していないピクセルの数
（iv）候補矩形内部のエッジピクセルの数及び強度
（v）候補矩形のエリア
（vi）候補矩形が画像を超えて延長している際に画像エッジが候補矩形を切り捨ててい
るバックグラウンド色を有していないピクセルの数
という弁別ファクタを使用して候補矩形を検証している。
【０１０４】
不鮮明化されたエッジマップＢＥＭ（ｘ，ｙ）により、ファクタ（i）を判定すること
が可能である。ファクタ（ii）は、候補矩形内のピクセル行上のピクセルのＣｏｌｏｒ 
Ｓｃｏｒｅを使用して判定される。ＮｘＭからＮに計算の数を低減する蓄積行アレイ法を
使用している。ファクタ（iv）及び（vi）は、Ｃｏｌｏｒ Ｓｃｏｒｅをエッジ強度によ
って置換することにより、ファクタ（ii）に類似した方式において算出されている。ファ
クタ（iii）及び（v）の判定については、前述の説明から明らかである。
【０１０５】
次いで、候補矩形のそれぞれごとに前述の６つのファクタを使用することにより、次の
統計値の表５を算出している。
【０１０６】
【表５】
2008171417.tif 000023
【０１０７】
表５の統計値は、離散型の適応ブースティング（Ａｄａ Ｂｏｏｓｔ）を使用してブー
ストされる決定木の切り株の機械学習クラシファイアと共に使用されている。Ａｄａ Ｂ
ｏｏｓｔ法は、弱いクラシファイアのシーケンスを学習し、弱いクラシファイアを線形で
組み合わせて単一の強力なクラシファイアを構築することにより、インジケータとして機
能する弱いクラシファイアの能力をブーストしている。すべての反復ステップにおいて、
「弱い学習者」関数（即ち、ランダムチャンスよりもわずかに良好であるに過ぎない精度
を具備しているもの）をデータによってトレーニングしている。次いで、弱い学習者の出
力を（弱い学習者の精度に比例した）なんらかの強度において学習済みの関数に対して追
加している。次いで、弱い学習者関数の将来の反復が、同一のエラーが回避される更に大
きな確率を具備することになるように、データを再重み付け又はブーストしている。
【０１０８】
既知のセグメントを具備した人工的に生成された画像サンプルから得られた特徴を使用
してクラシファイアを事前トレーニングすることにより、次の式（１２）の定数（ｑ，ｒ
）を得ている。
【０１０９】
【数１７】
2008171417.tif 000024
【０１１０】
このタイプのクラシファイアは、通常、不信任分類（non-confidence classification
）のために使用されているが、このクラシファイアの出力スコアは、候補矩形のランクの
有用な尺度を提供している。
【０１１１】
以上に続いて、矩形の境界に跨ったバックグラウンド及び非バックグラウンドピクセル
間の差ｓ２と矩形の境界に跨った色エッジの強度ｓ３を判定している。次いで、次の式（
１３）に従って、それぞれの候補矩形のスコアを算出している。
【０１１２】
【数１８】
2008171417.tif 000025
ここで、ａ及びｂは定数であり、この実施例においては、これらは、それぞれ、０．０
０４及び０．００２に等しい。次いで、候補矩形をスコアによってランク付けしている。
ランク付けステップが完了したら、候補矩形を調べることにより、いずれかの候補矩形が
オーバーラップしているかどうかを判定している。２つのオーバーラップしている候補矩
形において、高位にランク付けされた候補矩形が低位にランク付けされた候補矩形と３０
％を上回ってオーバーラップしている場合には、低位にランク付けされた候補矩形を破棄
する。前述のように、ランク付けされた候補矩形が入力画像内の写真を表す時点まで、ス
テップＳ１３０からステップＳ１７０までの間を反復的に実行する。
【０１１３】
このオブジェクト検出アプリケーションは、スタンドアロンのデジタル画像ツールとし
て稼動可能であり、或いは、その他の利用可能なデジタル画像処理アプリケーションに内
蔵することにより、向上した機能をそれらのデジタル画像処理アプリケーションに対して
提供することも可能である。ソフトウェアアプリケーションは、ルーチン、プログラム、
オブジェクトコンポーネント、データ構造などを含むプログラムモジュールを包含するこ
とが可能であり、且つ、コンピュータ可読媒体内に保存されたコンピュータ可読プログラ
ムコードとして実施可能である。このコンピュータ可読媒体は、データを保存することが
でき、且つ、その後に、そのコンピュータシステムによって判読可能である任意のデータ
ストレージ装置であってよい。コンピュータ可読媒体の例は、例えば、読み出し専用メモ
リ、ランダムアクセスメモリ、ハードディスクドライブ、磁気テープ、ＣＤ−ＲＯＭ、及
びその他の光データストレージ装置を含んでいる。又、コンピュータ可読プログラムコー
ドを、結合されたコンピュータシステムを含むネットワーク上に分散させることにより、
分散方式でコンピュータ可読プログラムコードを保存及び実行できるようにすることも可
能である。
【０１１４】
以上、特定の実施例について説明したが、当業者であれば、添付の請求項によって定義
されているその精神及び範囲を逸脱することなしに、変形及び変更を実施することが可能
であることを理解するであろう。
【図面の簡単な説明】
【０１１５】
【図１】画像内のオブジェクトを検出する装置の概略ブロックダイアグラム。
【図２】画像内のオブジェクトを検出するべく、オブジェクト検出アプリケーションを実行する際に図１の装置によって実行される概略的なステップを示すフローチャート。
【図３】バックグラウンド色の推定及びエッジの検出において実行されるステップを示すフローチャート。
【図４】スキャンラインの一部。
【図５】スキャンラインに沿った色の変化を検出するべく実行されるステップを示すフローチャート。
【図６】候補矩形の検出において実行されるステップを示すフローチャート。
【図７】候補矩形及びその近傍部分。
【図８】候補矩形の辺の正規化された表現。
【図９】（ａ）は、２つの矩形写真の画像であり、（ｂ）及び（ｃ）は、（ａ）の画像に対応するエッジ及び不鮮明化されたエッジのマップ。
【符号の説明】
【０１１６】
２４…処理ユニット、２８…ＲＡＭ、３２…不揮発性メモリ、３６…通信インターフェ
イス、４０…入力インターフェイス、４４…出力インターフェイス。
【図１】
2008171417.tif 000026
【図２】
2008171417.tif 000027
【図３】
2008171417.tif 000028
【図４】
2008171417.tif 000029
【図５】
2008171417.tif 000030
【図６】
2008171417.tif 000031
【図７】
2008171417.tif 000032
【図８】
2008171417.tif 000033
【図９】
2008171417.tif 000034