(57)【要約】本発明は、カメラ対応装置を用いた背景シーンにおけるビデオディスプレイからのビデオ信号の検出、インデックス作成、及び比較のための方法を開示する。方法は、カメラ対応（ＣＥＮ）装置をビデオ信号面に向けるステップと、ＣＥＮ装置上で、背景シーンにおけるビデオ信号面の位置を検出するステップと、検出されたビデオ信号面から少なくとも１つのフレームを抽出するステップと、を含む。好適には、本方法は、少なくとも１つの抽出されたフレームから少なくとも１つの画像を取得するステップと、少なくとも１つの画像から少なくとも１つのコンパクト符号を算出するステップと、少なくとも１つのコンパクト符号をデータベースに記憶されている少なくとも1つの記憶されたコンパクト符号と比較するステップと、少なくとも１つのコンパクト符号と少なくとも１つの記憶されたコンパクト符号との間に少なくとも１つの一致が発見されたか否かを判定するステップと、を更に含む。
2014512128.tif 000002
【特許請求の範囲】
【請求項１】
背景シーンからビデオ信号カメラキャプチャ（ＶＳＣＣ）を取得するための方法であって、
（ａ）装置ビデオ信号面にカメラ対応〈ＣＥＮ〉装置を向けるステップと、
（ｂ）装置前記ＣＥＮ装置で、前記背景シーンにおける前記ビデオ信号面の位置を検出するステップと、
（ｃ）前記検出されたビデオ信号面から少なくとも１つのフレームを抽出するステップと、
を含む、方法。
【請求項２】
（ｄ）装置前記ＣＥＮ装置に、前記検出されたビデオ信号面の少なくとも１つの図形標識を表示するステップ
を更に含む、請求項１に記載の方法。
【請求項３】
（ｄ）前記抽出するステップ中に、前記少なくとも１つのフレームの少なくとも１つの個別のカラー画像を、それぞれが個別の閾値を有する少なくとも２つの個別のチャネルに分割するステップと、
（ｅ）前のフレームによる前のチャネル及び前の閾値が、少なくとも１つの四角形を検出することに成功したか否かを判定するステップと、
（ｆ）前記判定するステップが成功であった場合、ステップ（ｈ）にスキップするステップと、
（ｇ）少なくとも１つの新たな個別チャネルか、又は個別の異なる閾値を有する前記前のチャネルである、個別の新たな閾値を有する少なくとも１つの代替の個別チャネルを選択するステップと、
（ｈ）前記前のチャネル及び前記前の閾値を用いて、又は前記少なくとも１つの代替の個別チャネル及び前記個別の閾値を用いて、前記少なくとも２つのチャネルのうちの１つにおいて、少なくとも１つの四角形を検出するステップと、
（ｉ）前記少なくとも１つの四角形を検出するステップが成功であった場合、どのチャネルが成功であったかの指標、及び個別の成功した閾値を記憶するステップと、
（ｊ）前記少なくとも１つの四角形を検出するステップが成功ではなかった場合、前記（ｇ）〜（ｉ）のステップを反復するステップと、
（ｋ）検出された四角形の各々の個別座標を提供するステップと、
を更に含む、請求項１に記載の方法。
【請求項４】
前記少なくとも１つの四角形を検出するステップが、
（ｉ）前記カラー画像の中から、少なくとも１つの連結成分を検出するステップと、
（ｉｉ）前記少なくとも１つの連結成分の各々の輪郭を、少なくとも１つの第１ポリゴンで近似するステップと、
（ｉｉｉ）前記少なくとも１つの第１ポリゴンが凸四角形であるか否かを判定するステップと、
（ｉｖ）前記少なくとも１つの第１ポリゴンが凸四角形である場合に、前記記憶するステップへと進むステップと、
（ｖ）前記少なくとも１つの第１ポリゴンが凸四角形ではない場合に、前記少なくとも１つの連結成分の凸包を探し出すステップと、
（ｖｉ）前記凸包の各々を、少なくとも１つの第２ポリゴンで近似するステップと、
（ｖｉｉ）前記記憶するステップへと進むステップと、
を含む、請求項３に記載の方法。
【請求項５】
前記判定するステップが、最初の一致が発見されると終了する、請求項３に記載の方法。
【請求項６】
（ｄ）前記少なくとも１つの抽出されたフレームから、少なくとも１つの画像を取得するステップと、
（ｅ）前記少なくとも１つの画像から、少なくとも１つのコンパクト符号を算出するステップと、
（ｆ）前記少なくとも１つのコンパクト符号を、データベース中の少なくとも１つの記憶されたコンパクト符号と比較するステップと、
（ｇ）前記少なくとも１つのコンパクト符号と前記少なくとも１つの記憶されたコンパクト符号との間に少なくとも１つの一致が発見されたか否かを判定するステップと、
を更に含む、請求項１に記載の方法。
【請求項７】
前記判定するステップが、最初の一致が発見されると終了する、請求項６に記載の方法。
【請求項８】
（ｉ）前記比較するステップ及び前記判定するステップの実行のために、前記データベースを前記ＣＥＮ装置に記憶させるステップ
を更に含む、請求項６に記載の方法。
【請求項９】
前記少なくとも１つの一致を提供するために、前記比較するステップ及び前記判定するステップが、前記少なくとも１つのコンパクト符号をリモート・エンティティに伝送することによって実行される、請求項６に記載の方法。
【請求項１０】
（ｄ）少なくとも２つの前記抽出されたフレームからビデオを生成するステップと、
（ｅ）前記ビデオから、少なくとも１つのコンパクト・ビデオ符号を算出するステップと、
（ｆ）前記少なくとも１つのコンパクト・ビデオ符号を、データベース中の少なくとも１つの記憶された符号と比較するステップと、
（ｇ）前記少なくとも１つのコンパクト・ビデオ符号と前記少なくとも１つの記憶された符号との間に少なくとも１つの一致が発見されたか否かを判定するステップと、
を更に含む、請求項１に記載の方法。
【請求項１１】
（ｄ）前記少なくとも１つのフレームが少なくとも１つのカラー画像であるか否かを判定するステップと、
（ｅ）前記少なくとも１つのフレームが少なくとも１つのカラー画像ではない場合に、前記初期化するステップにスキップするステップと、
（ｆ）前記少なくとも１つのフレームが少なくとも１つのカラー画像である場合に、前記少なくとも１つのカラー画像を少なくとも１つのグレースケール画像に変換するステップと、
（ｇ）前記少なくとも１つのグレースケール画像のために、少なくとも１つの初期値が空の符号列を初期化するステップと、
（ｈ）前記少なくとも１つのグレースケール画像に少なくとも１つのスケール・レベル「Ｌ」を設定するステップと、
（ｉ）前記少なくとも１つのグレースケール画像を、少なくとも１つの部分画像を含む、少なくとも１つのＬ×Ｌの矩形区画に分割するステップと、
（ｊ）前記少なくとも１つの部分画像に対する少なくとも１つの画像符号列を生成するステップと、
（ｋ）前記少なくとも１つの画像符号列を前記少なくとも１つの初期値が空の初期値が空の符号列に加えるステップと、
（ｌ）前記少なくとも１つのスケール・レベルＬの全ての値について、前記ステップ（ｈ）〜（ｊ）を反復するステップと、
（ｍ）前記少なくとも１つのスケール・レベルＬの最大スケール・レベルにおいて処理を行い、完全な符号列を提供するステップと、
を更に含む、請求項１に記載の方法。
【請求項１２】
前記少なくとも１つの画像符号列を生成するステップが、
（ｉ）前記少なくとも１つの部分画像の左半分における左ピクセル総和が、前記少なくとも1つの部分画像の右半分における右ピクセル総和よりも小さいか否かを判定するステップと、
（ｉｉ）前記左総和が前記右総和よりも小さい場合に、前記少なくとも１つの画像符号列に１ビットを加えるステップと、
（ｉｉｉ）前記左総和が前記右総和よりも大きい又は等しい場合に、前記少なくとも１つの画像符号列に０ビットを加えるステップと、
（ｉｖ）前記少なくとも１つの部分画像の上半分における個別の上ピクセル総和、及び前記少なくとも１つの部分画像の上半分における個別の下ピクセル総和のそれぞれについて、前記ステップ（ｉ）〜（ｉｉｉ）を反復するステップと、
（ｖ）前記少なくとも１つの部分画像の左上４分の１及び右下４分の１における個別の第１の対角ピクセル総和、並びに前記少なくとも１つの部分画像の右上４分の１及び左下４分の１における個別の第２の対角ピクセル総和のそれぞれについて、前記ステップ（ｉ）〜（ｉｉｉ）を反復するステップと、
（ｖｉ）前記少なくとも１つの部分画像の中央水平部における個別の中央水平部ピクセル総和、並びに前記少なくとも１つの部分画像の左水平部及び右水平部における個別の側面水平部ピクセル総和のそれぞれについて、前記ステップ（ｉ）〜（ｉｉｉ）を反復するステップと、
（ｖｉｉ）前記少なくとも１つの部分画像の中央垂直部における個別の中央垂直部ピクセル総和、並びに前記少なくとも１つの部分画像の上部垂直部及び下部垂直部における個別の側面垂直部ピクセル総和のそれぞれについて、前記ステップ（ｉ）〜（ｉｉｉ）を反復するステップと、
を含む、請求項１１に記載の方法。
【請求項１３】
（ｄ）前記抽出するステップ中に、前記少なくとも１つのフレームから少なくとも１つのグレースケール・フレームを取得するステップと、
（ｅ）少なくとも２つの垂直端部セグメント及び少なくとも１つの水平端部セグメント、又は少なくとも１つの垂直端部セグメント及び少なくとも２つの水平端部セグメントを検出するステップと、
（ｆ）前記垂直端部セグメントから、画像中心の上側に１つの終点を、及び画像中心の下側に１つの終点を有するセグメントのみを選択するステップと、
（ｇ）少なくとも１つの選択された垂直セグメントを黒色画像上に描画するステップと、
（ｈ）前記垂直端部セグメントからセグメントを選択するステップとは無関係に、前記水平端部セグメントから、画像中心の左側に１つの終点を、及び画像中心の右側に１つの終点を有するセグメントのみを選択するステップと、
（ｉ）少なくとも１つの選択された水平セグメントを前記黒色画像上に描画するステップと、
（ｊ）前記少なくとも１つの選択された垂直セグメントと前記少なくとも１つの選択された水平セグメントを接続するために、前記黒色画像に対して形態学的拡張を実行するステップと、
（ｋ）前記黒色画像から少なくとも１つの四角形を抽出するステップと、
を更に含む、請求項１に記載の方法。
【請求項１４】
前記黒色画像から少なくとも１つの四角形を抽出するステップが、
（ｉ）前記黒色画像の中から、少なくとも１つの連結成分を検出するステップと、
（ｉｉ）前記少なくとも１つの連結成分の輪郭の各々を、少なくとも１つの第１ポリゴンで近似するステップと、
（ｉｉｉ）前記少なくとも１つの第１ポリゴンが凸四角形であるか否かを判定するステップと、
（ｉｖ）前記少なくとも１つの第１ポリゴンが凸四角形である場合に、前記少なくとも１つの第１ポリゴンを記憶するステップと、
（ｖ）前記少なくとも１つの第１ポリゴンが凸四角形ではない場合に、前記少なくとも１つの連結成分の凸包を探し出すステップと、
（ｖｉ）前記凸包の各々を、少なくとも１つの第２ポリゴンで近似するステップと、
（ｖｉｉ）前記少なくとも１つの第２ポリゴンが凸四角形であるか否かを判定するステップと、
（ｖｉｉｉ）前記少なくとも１つの第２ポリゴンが凸四角形である場合に、前記少なくとも１つの第２ポリゴンを記憶するステップと、
（ｉｘ）前記少なくとも１つの第２ポリゴンが凸四角形ではない場合に、
（ｘ）前記少なくとも１つの第２ポリゴンが三角形であるか否かを判定するステップと、
（ｘｉ）前記少なくとも１つの第２ポリゴンが三角形である場合に、前記三角形の１つの角が９０度に近いものであるか否かを判定するステップと、
（ｘｉｉ）前記角が９０度に近いものである場合に、前記三角形の斜辺の中点が前記黒色画像の画像中心に近いものであるか否かを判定するステップと、
（ｘｉｉｉ）前記斜辺の中点が前記画像中心に近いものである場合に、四角形を完成させるために、前記少なくとも１つの第２ポリゴンに第４の点を付加するステップと、
（ｘｉｖ）検出された四角形の各々の個別座標を提供するステップと、
を含む、請求項１３に記載の方法。
【請求項１５】
背景シーンからのビデオ信号カメラキャプチャ（ＶＳＣＣ）のＶＳＣＣ符号を、ビデオストリームから生成され遠隔サーバ上に存在するリアルタイム符号と比較するための方法であって、
（ａ）前記ビデオストリームから関連メタデータを抽出するステップと、
（ｂ）前記ビデオストリームに対応する関連ソース・メタデータを、前記ビデオストリーム以外の少なくとも１つの情報源から取得するステップと、
（ｃ）前記ビデオストリームから、少なくとも１つのコンパクト・サーバ符号を算出するステップと、
（ｄ）前記少なくとも１つのコンパクト・サーバ符号をデータベース中に記憶させるステップと、
を含む、方法。
【請求項１６】
前記記憶させるステップが、前記少なくとも１つのコンパクト・サーバ符号を、前記関連メタデータ及び／又は前記関連ソース・メタデータと共に前記データベース中に記憶させることを含む、請求項１５に記載の方法。
【請求項１７】
（ｅ）少なくとも１つのコンパクト・クライアント符号を有するクライアント要求を受信したときに、前記少なくとも１つのコンパクト・クライアント符号を、前記データベース中の少なくとも１つの記憶されたコンパクト・サーバ符号と比較するステップと、
（ｆ）前記少なくとも１つのコンパクト・クライアント符号と前記少なくとも１つの記憶されたコンパクト・サーバ符号との間に少なくとも１つの一致が発見されたか否かを判定するステップと、
（ｇ）前記少なくとも１つの一致を提供することにより、前記クライアント要求に応じるステップと、
を更に含む、請求項１５に記載の方法。
【請求項１８】
前記関連メタデータ及び／又は前記関連ソース・メタデータが、ビデオコンテンツ・チャネル、ビデオコンテンツ番組、番組の形式、番組の詳細、キャストの詳細、サブタイトル、関連広告、関連プロモーション、視聴者活動、視聴者コメント、視聴者評価、視聴の統計、クイズ用のコンテンツ、投票用のコンテンツ、及びコールトゥアクション用のコンテンツからなる群から選択される、請求項１５に記載の方法。
【請求項１９】
背景シーンからビデオ信号カメラキャプチャ（ＶＳＣＣ）を取得するための装置であって、
（ａ）前記装置上で、背景シーンにおけるビデオ信号面の位置を検出するためのカメラモジュールと、
（ｂ）処理モジュールであって、
（ｉ）前記検出されたビデオ信号面から少なくとも１つのフレームを抽出し、
（ｉｉ）前記少なくとも１つの抽出されたフレームから少なくとも１つの画像を取得し、
（ｉｉｉ）前記少なくとも１つの画像から少なくとも１つのコンパクト符号を算出するための
処理モジュールと、を備える装置。
【請求項２０】
背景シーンからビデオ信号カメラキャプチャ（ＶＳＣＣ）を取得するためのシステムであって、
（ａ）少なくとも１つのコンパクト・クライアント符号を有する少なくとも１つのクライアント要求を受信するためのサーバ・プロセッサと、
（ｂ）コンパクト・ビデオ・プロバイダ符号を生成するためのコンパクト符号ジェネレータと、
（ｃ）メタデータ・プロバイダからのメタデータを割り当てるためのメタデータ割り当てモジュールと、
（ｄ）前記コンパクト・ビデオ・プロバイダ符号を記憶するためのビデオ・インデックス・リポジトリと、
（ｅ）前記少なくとも１つのコンパクト・クライアント符号を、前記ビデオ・インデックス・リポジトリ内の少なくとも１つの記憶されたコンパクト・ビデオ・プロバイダ符号と比較するためのリアルタイム・コンパレータと、
（ｆ）前記少なくとも１つのコンパクト・クライアント符号と前記少なくとも1つの記憶されたコンパクト・ビデオ・プロバイダ符号との間に少なくとも１つの一致が発見されたか否かを判定するための分析モジュールと、
（ｇ）前記少なくとも１つの一致を提供することにより前記クライアント要求に応じるための要求実現モジュールと、
を備える装置。
【請求項２１】
非一時的なコンピュータ可読媒体であって、前記非一時的なコンピュータ可読媒体上に実装されたコンピュータ可読コードが、
（ａ）カメラ対応（ＣＥＮ）装置上で、背景シーンにおけるビデオ信号面の位置を検出するためのプログラムコードと、
（ｂ）前記検出されたビデオ信号面から少なくとも１つのフレームを抽出するためのプログラムコードと、
（ｃ）前記少なくとも１つの抽出されたフレームから少なくとも１つの画像を取得するためのプログラムコードと、
（ｄ）前記少なくとも１つの画像から少なくとも１つのコンパクト符号を算出するためのプログラムコードと、
を備える、非一時的なコンピュータ可読媒体。
【請求項２２】
非一時的なコンピュータ可読媒体であって、前記非一時的なコンピュータ可読媒体上に実装されたコンピュータ可読コードが、
（ａ）少なくとも１つのコンパクト・クライアント符号を有する少なくとも１つのクライアント要求を受信するためのプログラムコードと、
（ｂ）コンパクト・ビデオ・プロバイダ符号を生成するためのプログラムコードと、
（ｃ）メタデータ・プロバイダからのメタデータを割り当てるためのプログラムコードと、
（ｄ）前記コンパクト・ビデオ・プロバイダ符号を記憶するためのプログラムコードと、
（ｅ）前記少なくとも1つのコンパクト・クライアント符号を、前記ビデオ・インデックス・リポジトリ内の少なくとも１つの記憶されたコンパクト・ビデオ・プロバイダ符号と比較するためのプログラムコードと、
（ｆ）前記少なくとも１つのコンパクト・クライアント符号と前記少なくとも１つの記憶されたコンパクト・ビデオ・プロバイダ符号との間に少なくとも１つの一致が発見されたか否かを判定するためのプログラムコードと、
（ｇ）前記少なくとも１つの一致を提供することにより前記クライアント要求に応じるためのプログラムコードと、
を備える、非一時的なコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願の相互参照］
本特許出願は、２０１１年３月３１日に出願された米国特許仮出願第６１／４６９，８７５号の優先権を主張し、その総体が参照により本明細書に組み込まれる。
【０００２】
本発明は、カメラ対応装置を用いた、背景シーンにおけるビデオディスプレイからのビデオ信号の検出、インデックス作成、及び比較のための装置、システム、方法、及び媒体に関する。
【背景技術】
【０００３】
対話型マルチメディア、ソーシャルネットワーキングの出現、及びカメラ対応スマートフォンや他のモバイル機器が広く普及するのに伴い、電子機器の消費者は、テクノロジーを利用して自身の日常の体験を知人（友人、血縁者、仕事上の仲間等）と共有するための新たな方法を探し求めてきた。ツイートやブログは、マルチユーザ・オンラインゲームやフォーラムと同様に、こうした方法の一例である。
【０００４】
こうした動向に対応するため、デジタルコンテンツの提供者及びモバイル機器の製造業者は、統合プラットフォームを、従来のメディア（音楽、ラジオ、及びテレビジョン等）の流通及びアクセスに結び付けるための手段を探してきた。テレビ放映されるコンテンツの分野においては、ユーザの視聴の好みを予定に組み込むためのオンラインＴＶガイド及びインターフェースが一般的となっている。しかしながら、装置がユーザの視聴しているものを知るためには、ユーザによるキーボード又はタッチパネルによる入力が必要であるという点により、個人のＴＶ視聴活動を共有することは今もなお制限されている。
【０００５】
カメラ対応装置を用いた、背景シーンにおけるビデオディスプレイからのビデオ信号の検出、インデックス作成、及び比較のための装置、システム、方法、及び媒体を得ることは、望ましいことである。とりわけ、そのようなシステム、方法、及び媒体は、上述の制限を解消するものであろう。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の目的は、カメラ対応装置を用いた背景シーンにおけるビデオディスプレイからのビデオ信号の検出、インデックス作成、及び比較のための装置、システム、方法、及び媒体を提供することにある。
【課題を解決するための手段】
【０００７】
明確を期するために、以下、一部の用語を、本明細書における使用のために特に定義する。本明細書において、「ビデオ」という用語は、進行中のシーンを表す一連の静止画の電子的な処理及び再構成の技術を指すために用いられる。本明細書において、「ビデオ信号」という用語は、テレビ受像機、コンピュータスクリーン、ビデオモニター／ディスプレイ、又は、例えば会議室におけるプレゼンテーション、教室における教育、ホームシアターにおける鑑賞、及び他のライブイベントなどにおける、ビデオプロジェクターを使用するプロジェクションスクリーン上に提示されるビデオを指すために用いられる。
【０００８】
本明細書において、「背景シーン」という用語は、カメラ対応（ＣＥＮ）装置によってキャプチャされた画像（又は一連の画像）に含まれる任意の視覚要素を指すために用いられる。例えば、公園の画像の背景シーンには、ベンチ、ブランコ、噴水、人々、芝生、及び雲、並びに電話機、携帯ゲーム機、携帯メディア機器が含まれうる。
【０００９】
本明細書において、「ビデオ信号カメラキャプチャ」及び「ＶＳＣＣ」という用語は、リアルタイムで背景シーンにおけるビデオ信号を表示する検出面（ｄｅｔｅｃｔｅｄ  ｓｕｒｆａｃｅ）を指すために用いられる。例えば、ビデオ信号カメラキャプチャは、リビングルーム、会議室、又は屋外空間の背景シーンから得られうるものであり、この中では、ビデオディスプレイは、ビデオディスプレイ上のビデオ信号の表示された面を検出するためのシーンの一要素である、
【００１０】
本明細書において、「システム」という一般用語は、ＣＥＮ又は他の装置上で（全部又は一部が）実行される、又は、例えばバックオフィスシステム若しくはクラウドベースサービスなどの遠隔システム上で（全部又は一部が）実行される、ソフトウェア（例えば、処理又は方法の実行）、ファームウェア、ハードウェアを含む、本発明の任意の実装を指すために用いられる。
【００１１】
更に、本明細書において、「例示的」という言葉は、実施形態及び／又は実装の例を指すために用いられ、必ずしもより望ましい使用例を伝えることを意図してはいないことに留意されたい。同様に、本明細書において、「好適」という言葉は、想定される各種の実施形態及び／又は実装からの一例を指すために用いられるものであって、必ずしもより望ましい使用例を伝えることを意図してはいない。したがって、上述より、本明細書において「例示的」及び「好適」は、多様な実施形態及び／又は実装に適用されうることが理解される。
【００１２】
本発明の実施形態は、ＣＥＮ装置のユーザが、ただ装置のカメラをテレビ受像機又はビデオディスプレイに向けることによって、自身が視聴しているビデオ番組を伝えることを可能とする。本システムは、とりわけ、どのようなチャンネル、番組が視聴されているか、及びどのような種類の番組（テーマ別コンテンツ、プロモーション、又は広告など）が視聴されているかを数秒の間に検出し、文脈的な関連のあるコンテンツ及びサービスをユーザの装置に送信する。
【００１３】
本発明の一部の実施形態は、ユーザが、彼らの視聴活動及びコンテンツに対するコメントをソーシャルネットワーク上で共有することを可能とする。こうした実施形態は、ＣＥＮ装置によってキャプチャされた背景シーン中のビデオ信号面から画像を抽出して、自動でクロップされた画像の取得を可能とする。使用の一例として、本発明の一部の実施形態は、同じ又は別の番組コンテンツを視聴している他者との共有のために、ユーザが自動でクロップされた画像に対してテキストによるコメントを付加することを可能とする。更なる実施形態は、ユーザが、彼らが視聴している特定の番組に対して他のユーザが投稿した全てのコメントを見ることを可能とする。他の実施形態においては、ユーザは、他のユーザとの共有のために、番組に対する自身の感情を象徴するアイコンを添付することができる。
【００１４】
追加的な実施形態において、ユーザは、そのユーザが視聴している特定の番組又はチャンネルに対して他のユーザが投稿した全てのコメントを見ることが可能である。一部の実装において、本システムは、特定のテレビ番組に関連するコメントの自動検索及び集約を実行し、最も関連する、及び関心を引くコメントを選択し、選択されたコメントをユーザに表示する。
【００１５】
本発明の一部の実施形態は、リアルタイムの視聴統計をユーザに提供する。例えば、こうした実施形態において、本システムは、ＴＶの視聴者に対して、その地域で視聴可能な各チャンネルを視聴している本システムのユーザの割合をいつでも提供することができる。視聴率は、円グラフ又は他のグラフ表現として提示されることが可能であり、ユーザは、例えば「全てのユーザ」、「ソーシャルネットワークを通して繋がったフレンド」又は「類似のプロフィールを有する他のユーザ」を選択することによって、その割合にフィルターにかけることが可能である。
【００１６】
更なる実施形態において、本システムは、視聴されている番組において以前にどんなことが起こったかの（例えば、数フレーズの）簡潔な概要を装置上に表示する。一部の実施形態において、この概要は、次のようなやり方で生成される。
１．以下のａ及び／又はｂを介して番組のオーディオ・トラックの複写（ｔｒａｎｓｃｒｉｐｔｉｏｎ）をリアルタイムで自動的に検索する。
ａ．テレビ放送のデジタル・ストリームに組み込まれたサブタイトルのキャプチャ
ｂ．以下のｉ及び／又はｉｉを含む、テレビ局のオーディオ・トラックの分析
ｉ．話者の特定及び分類
ｉｉ．番組において話されたことのリアルタイム複写のための、スピーチ・トゥ・テキスト処理のためのオーディオ・トラックの分析、及び／又は、
２．複写からの、コンテンツの要約のために最も重要なコンテンツ断片の抽出のための、（参照コーパスにおける全般的な分布に照らした、文中の各単語の相対的重要性の判断のための）統計的分析及び言語モデルの使用。
【００１７】
本発明の他の実施形態は、放送されている番組のコンテンツから自動的に生成される、文脈に即した「クイズ」又は「投票」を可能とする。こうした実施形態の好適な実装において、ユーザは、番組が放送されている間にキャプチャされた複写から自動的に生成されるクイズ又は投票に参加することができる。使用の一例として、本システムは、番組のリアルタイム複写から関連する短い文を選び出し、ユーザがその短い文の発言者である番組の登場人物を当てる必要のあるクイズを作り出す。別の使用例は、ユーザが、番組の任意の登場人物の独白又は会話に評価を与え、及び／又は、感情の属性を持ったアイコンを添付して、ソーシャルネットワーク上でその評価を共有することを含む。
【００１８】
本発明の他の実施形態は、ＣＥＮ装置上に表示された放送コンテンツ上に重ね合わされた（又はこれに近接して提示された）関連コンテンツのリアルタイム・オーバーレイを作り出すことによる、拡張現実の一様式を可能とする。例えば、番組が放送されている間に、ＴＶ番組を視聴している視聴者に対して、番組の詳細、人物の配役、クリック可能なバナー、役者の詳細、及び番組の拡張となる他の追加要素が提示されうる。こうした拡張現実オーバーレイは、放送に対応して時間と共に変化する。
【００１９】
本発明の他の実施形態は、ＴＶ広告の認識を可能とし、装置に即時のコールトゥアクションのためのオプションを提供する。こうした実施形態の好適な実装において、本システムは、放送されているコマーシャルをリアルタイムで特定し、装置上でユーザにコールトゥアクションのサービスを提供する。こうしたコールトゥアクション・サービスの例は、以下のものを含む。
１．ユーザに「クリック・アンド・コール」、詳細な連絡先の登録、又は追加情報を受け取るためのＥメールの送信の能力を提供する、同じ広告主からのオファー。
２．ユーザにクリック・アンド・コール、詳細な連絡先の登録、又は追加情報を受け取るためのＥメールの送信の能力を提供するコマーシャルで宣伝された製品又は製品カテゴリーを提示する、他の企業からのオファー。
３．ユーザの装置の位置の特定に基づき視聴者個人向けに設定された、上記サービスの地域限定オファー。
４．コマーシャルで宣伝された広告主、製品、又は製品カテゴリーに関連するプロモーション、クーポン、及び／又は電子商取引のオファーの装置上でのオファーの検索。
５．団体割引を受けるための、同じ製品又は製品カテゴリーを探す他のユーザとの共同購入の繋がり。
６．ユーザ・プロフィール、時刻、位置、並びにユーザ及び／又は装置によって提供されるその他の文脈的情報に対してコールトゥアクション・サービスがマップされた使用統計。
【００２０】
本発明の他の実施形態は、ＶＳＣＣ配信のトリガーとなる、動き反応カメラキャプチャ（Ａｃｔｉｏｎ−Ｒｅｓｐｏｎｓｅ  Ｃａｍｅｒａ−Ｃａｐｔｕｒｅ）（ＡＲＣＣ）を可能とする。ＡＲＣＣは、装置に対する関連コンテンツの配信のトリガーとして用いられるＶＳＣＣに対する（装置のセンサーの変化に基づく）ユーザの反応又は応答を含む。例えば、ＣＥＮ装置は、ＶＳＣＣを介して画像を検出する。ゲームの一部として、ユーザは、配信される次のコンテンツを始動させるために、課題の遂行を求められる。遂行される課題の例としては、装置のタッチスクリーンのタップ、加速度計、ジャイロスコープ、又は他の動作センサーを有する装置のシェイク、選挙における投票、及びクイズへの回答が含まれる。装置がビデオ信号面の特定領域に向けられる必要がある場合、又は装置がビデオ配信コンテンツ内の特定のオブジェクト（例えば、顔、形状及び色、ロゴ）を検出する必要がある場合にも、同様のプロセスが適用される。
【００２１】
本発明の実施形態は、例えば、１６：９又は４：３の幾何学的な比などといった、ビデオ信号面（又はスクリーン・フレーム）の特有の識別子を利用する。本発明の実施形態は、高速なＶＳＣＣ検出の実行が可能であり、これがリアルタイム実装を可能とする。更なる実施形態は、ビデオ信号面を有する背景シーンのキャプチャの間の、ユーザによるＣＥＮ装置の揺動又は移動に起因する画像のジッタを、キャプチャ安定化処理を介して補正することが可能である。
【００２２】
したがって、本発明によれば、背景シーンからビデオ信号カメラキャプチャ（ＶＳＣＣ）を取得するための方法であって、（ａ）カメラ対応（ＣＥＮ）装置をビデオ信号面に向けるステップと、（ｂ）装置前記ＣＥＮ装置で、前記背景シーンにおける前記ビデオ信号面の位置を検出するステップと、（ｃ）前記検出されたビデオ信号面から少なくとも１つのフレームを抽出するステップと、を含む方法が初めて提供される。
【００２３】
好適には、本方法は、（ｄ）装置前記ＣＥＮ装置で、前記検出されたビデオ信号面の少なくとも１つの図形標識を表示するステップを更に含む。
【００２４】
好適には、本方法は、（ｄ）前記抽出するステップ中に、少なくとも１つのフレームの少なくとも１つの個別のカラー画像を、それぞれが個別の閾値を有する少なくとも２つの個別のチャネルに分割するステップと、（ｅ）前のフレームによる前のチャネル及び前の閾値が、少なくとも１つの四角形を検出することに成功したか否かを判定するステップと、（ｆ）前記判定するステップが成功であった場合、ステップ（ｈ）にスキップするステップと、（ｇ）個別の新たな閾値を有する少なくとも１つの代替の個別チャネルを選択するステップであって、少なくとも１つの代替の個別チャネルが、少なくとも１つの新たな個別チャネルか、又は個別の異なる閾値を有する前記前のチャネルである、選択するステップと、（ｈ）前記前のチャネル及び前記前の閾値を用いて、又は少なくとも１つの代替の個別チャネル及び前記個別の閾値を用いて、少なくとも２つのチャネルのうちの１つにおいて、少なくとも１つの四角形を検出するステップと、（ｉ）前記少なくとも１つの四角形を検出するステップが成功であった場合、どのチャネルが成功であったかの指標、及び個別の成功した閾値を記憶するステップと、（ｊ）前記少なくとも１つの四角形を検出するステップが失敗であった場合、前記（ｇ）〜（ｉ）のステップを反復するステップと、（ｋ）検出された四角形の各々の個別座標を提供するステップと、を更に含む。
【００２５】
最も好適には、前記少なくとも１つの四角形を検出するステップは、（ｉ）前記カラー画像の中から、少なくとも１つの連結成分を検出するステップと、（ｉｉ）少なくとも１つの連結成分の輪郭を、少なくとも１つの第１ポリゴンで近似するステップと、（ｉｉｉ）少なくとも１つの第１ポリゴンが凸四角形であるか否かを判定するステップと、（ｉｖ）少なくとも１つの第１ポリゴンが凸四角形である場合に、前記記憶するステップへと進むステップと、（ｖ）少なくとも１つの第１ポリゴンが凸四角形ではない場合に、少なくとも１つの連結成分の凸包を探し出すステップと、（ｖｉ）凸包の各々を、少なくとも１つの第２ポリゴンで近似するステップと、（ｖｉｉ）前記記憶するステップへと進むステップと、を含む。
【００２６】
最も好適には、前記判定するステップは、最初の一致が発見されると終了する。
【００２７】
好適には、本方法は、（ｄ）少なくとも１つの抽出されたフレームから、少なくとも１つの画像を取得するステップと、（ｅ）少なくとも１つの画像から、少なくとも１つのコンパクト符号（ｓｉｇｎａｔｕｒｅ）を算出するステップと、（ｆ）少なくとも１つのコンパクト符号を、データベース中の少なくとも１つの記憶されたコンパクト符号と比較するステップと、（ｇ）少なくとも１つのコンパクト符号と少なくとも１つの記憶されたコンパクト符号との間に少なくとも１つの一致が発見されたか否かを判定するステップと、を更に含む。
【００２８】
最も好適には、前記判定するステップは、最初の一致が発見されると終了する。
【００２９】
最も好適には、本方法は、（ｉ）前記比較するステップ及び前記判定するステップの実行のために、前記データベースを前記ＣＥＮ装置に記憶させるステップを更に含む。
【００３０】
最も好適には、少なくとも１つの一致を提供するために、前記比較するステップ及び前記判定するステップは、少なくとも１つのコンパクト符号をリモート・エンティティに転送することによって実行される。
【００３１】
好適には、本方法は、（ｄ）少なくとも２つの抽出されたフレームからビデオを生成するステップと、（ｅ）前記ビデオから、少なくとも１つのコンパクト・ビデオ符号を算出するステップと、（ｆ）少なくとも１つのコンパクト・ビデオ符号を、データベース中の少なくとも１つの記憶された符号と比較するステップと、（ｇ）少なくとも１つのコンパクト・ビデオ符号と少なくとも１つの記憶された符号との間に少なくとも１つの一致が発見されたか否かを判定するステップと、を更に含む。
【００３２】
好適には、本方法は、（ｄ）少なくとも１つのフレームが少なくとも１つのカラー画像であるか否かを判定するステップと、（ｅ）少なくとも１つのフレームが少なくとも１つのカラー画像ではない場合に、初期化するステップにスキップするステップと、（ｆ）少なくとも１つのフレームが少なくとも１つのカラー画像である場合に、少なくとも１つのカラー画像を少なくとも１つのグレースケール画像に変換するステップと、（ｇ）少なくとも１つのグレースケール画像のために、少なくとも１つの初期値が空の符号列を初期化するステップと、（ｈ）少なくとも１つのグレースケール画像に少なくとも１つのスケール・レベル「Ｌ」を設定するステップと、（ｉ）少なくとも１つのグレースケール画像を、少なくとも１つの部分画像を含む、少なくとも１つのＬ×Ｌの矩形区画に分割するステップと、（ｊ）少なくとも１つの部分画像に対する少なくとも１つの画像符号列を生成するステップと、（ｋ）少なくとも１つの画像符号列を、少なくとも１つの初期値が空の符号列に加えるステップと、（ｌ）少なくとも１つのスケール・レベルＬの全ての値について、前記ステップ（ｈ）〜（ｊ）を反復するステップと、（ｍ）少なくとも１つのスケール・レベルＬの最大スケール・レベルにおいて処理を行い、完全な符号列を提供するステップと、を更に含む。
【００３３】
好適には、前記少なくとも１つの画像符号列を生成するステップは、（ｉ）少なくとも１つの部分画像の左半分における左ピクセル総和が、少なくとも１つの部分画像の右半分における右ピクセル総和よりも小さいか否かを判定するステップと、（ｉｉ）前記左総和が前記右総和よりも小さい場合に、少なくとも１つの画像符号列に１ビットを加えるステップと、（ｉｉｉ）前記左総和が前記右総和よりも大きい又は等しい場合に、少なくとも１つの画像符号列に０ビットを加えるステップと、（ｉｖ）少なくとも１つの部分画像の上半分における個別の上ピクセル総和、及び少なくとも１つの部分画像の上半分における個別の下ピクセル総和のそれぞれについて、前記ステップ（ｉ）〜（ｉｉｉ）を反復するステップと、（ｖ）少なくとも１つの部分画像の左上４分の１及び右下４分の１における個別の第１の対角ピクセル総和、並びに少なくとも１つの部分画像の右上４分の１及び左下４分の１における個別の第２の対角ピクセル総和のそれぞれについて、前記ステップ（ｉ）〜（ｉｉｉ）を反復するステップと、（ｖｉ）少なくとも１つの部分画像の中央水平部における個別の中央水平部ピクセル総和、並びに少なくとも１つの部分画像の左水平部及び右水平部における個別の側面水平部ピクセル総和のそれぞれについて、前記ステップ（ｉ）〜（ｉｉｉ）を反復するステップと、（ｖｉｉ）少なくとも１つの区画の中央垂直部における個別の中央垂直部ピクセル総和、並びに少なくとも１つの区画の上部垂直３分の１及び下部垂直部における個別の側面垂直部ピクセル総和のそれぞれについて、前記ステップ（ｉ）〜（ｉｉｉ）を反復するステップと、を含む。
【００３４】
好適には、本方法は、（ｄ）前記抽出するステップ中に、少なくとも１つのフレームから少なくとも１つのグレースケール・フレームを取得するステップと、（ｅ）少なくとも２つの垂直端部セグメント及び少なくとも１つの水平端部セグメント、又は少なくとも１つの垂直端部セグメント及び少なくとも２つの水平端部セグメントを検出するステップと、（ｆ）前記垂直端部セグメントから、画像中心の上側に１つの終点を、及び画像中心の下側に１つの終点を有するセグメントのみを選択するステップと、（ｇ）少なくとも１つの選択された垂直セグメントを黒色画像上に描画するステップと、（ｈ）前記垂直端部セグメントからセグメントを選択するステップとは無関係に、前記水平端部セグメントから、画像中心の左側に１つの終点を、及び画像中心の右側に１つの終点を有するセグメントのみを選択するステップと、（ｉ）少なくとも１つの選択された水平セグメントを前記黒色画像上に描画するステップと、（ｊ）少なくとも１つの選択された垂直セグメントと少なくとも１つの選択された水平セグメントを接続するために、前記黒色画像に対して形態学的拡張を実行するステップと、（ｋ）前記黒色画像から少なくとも１つの四角形を抽出するステップと、を更に含む。
【００３５】
最も好適には、前記黒色画像から少なくとも１つの四角形を抽出するステップは、（ｉ）前記黒色画像の中から、少なくとも１つの連結成分を検出するステップと、（ｉｉ）少なくとも１つの連結成分の各々の輪郭を、少なくとも１つの第１ポリゴンで近似するステップと、（ｉｉｉ）少なくとも１つの第１ポリゴンが凸四角形であるか否かを判定するステップと、（ｉｖ）少なくとも１つの第１ポリゴンが凸四角形である場合に、少なくとも１つの第１ポリゴンを記憶するステップと、（ｖ）少なくとも１つの第１ポリゴンが凸四角形ではない場合に、少なくとも１つの連結成分の凸包を探し出すステップと、（ｖｉ）凸包の各々を、少なくとも１つの第２ポリゴンで近似するステップと、（ｖｉｉ）少なくとも１つの第２ポリゴンが凸四角形であるか否かを判定するステップと、（ｖｉｉｉ）少なくとも１つの第２ポリゴンが凸四角形である場合に、少なくとも１つの第２ポリゴンを記憶するステップと、（ｉｘ）少なくとも１つの第２ポリゴンが凸四角形ではない場合に、（ｘ）少なくとも１つの第２ポリゴンが三角形であるか否かを判定するステップと、（ｘｉ）少なくとも１つの第２ポリゴンが三角形である場合に、前記三角形の１つの角が９０度に近いものであるか否かを判定するステップと、（ｘｉｉ）前記角が９０度に近いものである場合に、前記三角形の斜辺の中点が前記黒色画像の画像中心に近いものであるか否かを判定するステップと、（ｘｉｉｉ）前記斜辺の中点が前記画像中心に近いものである場合に、四角形を完成させるために、少なくとも１つの第２ポリゴンに第４の点を付加するステップと、（ｘｉｖ）検出された四角形の各々の個別座標を提供するステップと、を含む。
【００３６】
本発明によれば、背景シーンからのビデオ信号カメラキャプチャ（ＶＳＣＣ）のＶＳＣＣ符号を、ビデオストリームから生成され遠隔サーバ上に存在するリアルタイム符号と比較するための方法であって、（ａ）前記ビデオストリームから関連メタデータを抽出するステップと、（ｂ）前記ビデオストリームに対応する関連ソース・メタデータを、前記ビデオストリーム以外の少なくとも１つの情報源から取得するステップと、（ｃ）前記ビデオストリームから、少なくとも１つのコンパクト・サーバ符号を算出するステップと、（ｄ）少なくとも１つのコンパクト・サーバ符号をデータベース中に記憶させるステップと、を含む方法が初めて提供される。
【００３７】
好適には、前記記憶させるステップは、少なくとも１つのコンパクト・サーバ符号を、前記関連メタデータ及び／又は前記関連ソース・メタデータと共に前記データベース中に記憶させることを含む。
【００３８】
好適には、本方法は、（ｅ）少なくとも１つのコンパクト・クライアント符号を有するクライアント要求を受信したときに、少なくとも１つのコンパクト・クライアント符号を、前記データベース中の少なくとも１つの記憶されたコンパクト・サーバ符号と比較するステップと、（ｆ）少なくとも１つのコンパクト・クライアント符号と少なくとも１つの記憶されたコンパクト・サーバ符号との間に少なくとも１つの一致が発見されたか否かを判定するステップと、（ｇ）少なくとも１つの一致を提供することにより、前記クライアント要求に応じるステップと、を更に含む。
【００３９】
好適には、前記関連メタデータ及び／又は前記関連ソース・メタデータは、ビデオコンテンツ・チャネル、ビデオコンテンツ番組、番組の形式、番組の詳細、キャストの詳細、サブタイトル、関連広告、関連プロモーション、視聴者活動、視聴者コメント、視聴者評価、視聴の統計、クイズ用のコンテンツ、投票用のコンテンツ、及びコールトゥアクション用のコンテンツからなる群から選択される。
【００４０】
本発明によれば、背景シーンからビデオ信号カメラキャプチャ（ＶＳＣＣ）を取得するための装置であって、（ａ）前記装置上で、背景シーンにおけるビデオ信号面の位置を検出するためのカメラモジュールと、（ｂ）処理モジュールであって、（ｉ）前記検出されたビデオ信号面から少なくとも１つのフレームを抽出し、（ｉｉ）少なくとも１つの抽出されたフレームから少なくとも１つの画像を取得し、（ｉｉｉ）少なくとも１つの画像から少なくとも１つのコンパクト符号を算出するための処理モジュールと、を備える装置が初めて提供される。
【００４１】
本発明によれば、背景シーンからビデオ信号カメラキャプチャ（ＶＳＣＣ）を取得するためのシステムであって、（ａ）少なくとも１つのコンパクト・クライアント符号を有する少なくとも１つのクライアント要求を受信するためのサーバ・プロセッサと、（ｂ）コンパクト・ビデオ・プロバイダ符号を生成するためのコンパクト符号ジェネレータと、（ｃ）メタデータ・プロバイダからのメタデータを割り当てるためのメタデータ割り当てモジュールと、（ｄ）前記コンパクト・ビデオ・プロバイダ符号を記憶するためのビデオ・インデックス・リポジトリと、（ｅ）少なくとも１つのコンパクト・クライアント符号を、前記ビデオ・インデックス・リポジトリ内の少なくとも１つの記憶されたコンパクト・ビデオ・プロバイダ符号と比較するためのリアルタイム・コンパレータと、（ｆ）少なくとも１つのコンパクト・クライアント符号と少なくとも１つの記憶されたコンパクト・ビデオ・プロバイダ符号との間に少なくとも１つの一致が発見されたか否かを判定するための分析モジュールと、（ｇ）少なくとも１つの一致を提供することにより前記クライアント要求に応じるための要求実現モジュールと、を備える装置が初めて提供される。
【００４２】
本発明によれば、非一時的なコンピュータ可読媒体であって、前記非一時的なコンピュータ可読媒体上に実装されたコンピュータ可読コードが、（ａ）カメラ対応（ＣＥＮ）装置上で、背景シーンにおけるビデオ信号面の位置を検出するためのプログラムコードと、（ｂ）前記検出されたビデオ信号面から少なくとも１つのフレームを抽出するためのプログラムコードと、（ｃ）少なくとも１つの抽出されたフレームから少なくとも１つの画像を取得するためのプログラムコードと、（ｄ）少なくとも１つの画像から少なくとも１つのコンパクト符号を算出するためのプログラムコードと、を備える、非一時的なコンピュータ可読媒体が初めて提供される。
【００４３】
本発明によれば、非一時的なコンピュータ可読媒体であって、前記非一時的なコンピュータ可読媒体上に実装されたコンピュータ可読コードが、（ａ）少なくとも１つのコンパクト・クライアント符号を有する少なくとも１つのクライアント要求を受信するためのプログラムコードと、（ｂ）コンパクト・ビデオ・プロバイダ符号を生成するためのプログラムコードと、（ｃ）メタデータ・プロバイダからのメタデータを割り当てるためのプログラムコードと、（ｄ）前記コンパクト・ビデオ・プロバイダ符号を記憶するためのプログラムコードと、（ｅ）少なくとも１つのコンパクト・クライアント符号を、前記ビデオ・インデックス・リポジトリ内の少なくとも１つの記憶されたコンパクト・ビデオ・プロバイダ符号と比較するためのプログラムコードと、（ｆ）少なくとも１つのコンパクト・クライアント符号と少なくとも１つの記憶されたコンパクト・ビデオ・プロバイダ符号との間に少なくとも１つの一致が発見されたか否かを判定するためのプログラムコードと、（ｇ）少なくとも１つの一致を提供することにより前記クライアント要求に応じるためのプログラムコードと、を備える、非一時的なコンピュータ可読媒体が初めて提供される。
【００４４】
これらの実施形態、及び更なる実施形態は、以下の詳細な説明及び実施例によって明らかとなるであろう。
【００４５】
本発明は、例示のみを目的として、以下の通りの添付図面を参照して本明細書において説明される。
【図面の簡単な説明】
【００４６】
【図１】本発明の好適な実施形態に係る、背景シーンからビデオ信号カメラキャプチャ（ＶＳＣＣ）を取得するための主要処理ステップの簡略化されたフローチャートである。
【図２】本発明の好適な実施形態に係る、カメラ対応（ＣＥＮ）装置上でＶＳＣＣのコンパクト画像符号を算出するための主要処理ステップの簡略化されたフローチャートである。
【図３】本発明の好適な実施形態に係る、ＣＥＮ装置上でＶＳＣＣのコンパクト・ビデオ符号を算出するための主要処理ステップの簡略化されたフローチャートである。
【図４】本発明の好適な実施形態に係る、ＣＥＮ装置上でＶＳＣＣの符号を他の符号と比較するための主要処理ステップの簡略化されたフローチャートである。
【図５】本発明の好適な実施形態に係る、ＶＳＣＣの符号を遠隔サーバ内のビデオストリームのためにリアルタイムで生成された一群のコンパクト符号と比較するための主要処理ステップの簡略化されたフローチャートである。
【図６】本発明の好適な実施形態に係る、バックオフィス比較を実行するための主要処理ステップの簡略化されたフローチャートである。
【図７】本発明の好適な実施形態に係る、テレビ受像機又はビデオディスプレイからビデオ信号面を検出するための主要処理ステップの簡略化されたフローチャートである。
【図８】本発明の好適な実施形態に係る、テレビ受像機又はビデオディスプレイから四角形を検出するための主要処理ステップの簡略化されたフローチャートである。
【図９】本発明の好適な実施形態に係る、背景シーンからＶＳＣＣを取得するためのシステム・アーキテクチャの簡略化された概念図である。
【図１０】本発明の好適な実施形態に係る、画像からコンパクト符号を生成するための主要処理ステップの簡略化されたフローチャートである。
【図１１】本発明の好適な実施形態に係る、部分画像からコンパクト符号を生成するための主要処理ステップの簡略化されたフローチャートである。
【図１２】本発明の別の実施形態に係る、テレビ受像機又はビデオディスプレイからビデオ信号面を検出するための主要処理ステップの簡略化されたフローチャートである。
【図１３】本発明の別の実施形態に係る、テレビ受像機又はビデオディスプレイから四角形を検出するための主要処理ステップの簡略化されたフローチャートである。
【発明を実施するための形態】
【００４７】
本発明は、カメラ対応装置を用いた、背景シーンにおけるビデオディスプレイからのビデオ信号の検出、インデックス作成、及び比較のための装置、システム、方法、及び媒体に関する。本発明による、このような装置、方法、及び媒体の原理及び作用は、添付の詳細な説明及び図面を参照することでより理解されよう。
【００４８】
以下、図面を参照すると、図１は、本発明の好適な実施形態に係る、背景シーンからビデオ信号カメラキャプチャ（ＶＳＣＣ）を取得するための主要処理ステップの簡略化されたフローチャートである。この処理は、ユーザが、ビデオ信号を有する面が存在する背景シーン（例えば、部屋又は空間）に対してＣＥＮ装置を向けるところから開始する（ステップ２）。ＣＥＮ装置は、ビデオ信号を有する面を含む空間をキャプチャする。システムは、カメラキャプチャ出力から、ビデオ信号面の位置を検出する（ステップ４）。
【００４９】
次いでシステムは、システムがカメラキャプチャ出力の範囲内でビデオ信号を検出したことをユーザに通知するために、検出されたビデオ信号面の上に図形標識を表示する（ステップ６）。システムは、検出されたビデオ信号面からビデオ信号のフレームを抽出する（ステップ８）。抽出されたフレームから、システムは、適正サイズにクロップされた固定画像を生成することができる。その後、この抽出されたフレームは更なる処理のために使用されることが可能である（ステップ１０）。
【００５０】
図２は、本発明の好適な実施形態に係る、ＣＥＮ装置上でＶＳＣＣのコンパクト画像符号を算出するための主要処理ステップの簡略化されたフローチャートである。この処理は、図１のＶＳＣＣ処理において説明されたとおり、システムがＣＥＮ装置（例えば、スマートフォン、タブレットＰＣ、及び他の種類のカメラを有する装置）を用いてビデオ信号面を検出及び抽出するところから開始する。システムが抽出されたフレームを生成すると、そのフレームから画像を取得することが可能となる（ステップ２０）。システムは画像の視覚的特徴からコンパクト符号を局所的に（すなわち、ＣＥＮ装置内で）算出し、（元の画像よりもファイルサイズが遥かに小さい）コンパクト符号でビデオを表現する（ステップ２２）。
【００５１】
こうしたコンパクト符号を生成するための例示的実施形態は、図１０及び図１１を参照して説明される。かかる実施形態において、符号の比較は、よく知られたビット列の間のハミング距離（すなわち、２つのビット列の間における異なるビットの数）を用いて実行される。ハミング距離が大きいほど、ビット列間の一致は悪くなる。
【００５２】
ビデオ信号面のコンパクト符号は、表現されたビデオコンテンツを説明すること、インデックスを付けること、特定すること、提示すること、比較すること、及び／又は他のビデオ又はビジュアルコンテンツと一致させることを可能とする。次いで、システムはそのコンパクト符号を（局所的に、又は遠隔で利用可能な）データベース内の符号と比較する（ステップ２４）。
【００５３】
システムは、一致する符号を検索する（ステップ２６）。一致が検出された場合、装置上で実行中のアプリケーションへの通知がトリガされる（ステップ２８）。一致が検出されない場合、抽出されたフレームから新たな画像を取得するために、処理がステップ２０へと戻される。
【００５４】
多様な候補が生成されるフレームにおいて、符号は候補の各々について算出されうるものであり、マッチングは全ての候補符号に対して実行されることに留意されたい。符号の比較も同様に、ビデオ信号面から算出されたフィンガープリント符号の各々を、データベース内に記憶された全ての符号と比較することによって実行されることが可能である。これが、データベース内の符号の数と共に線形に増大するマッチング時間をもたらす。本発明の別の実装において、欲張り法によるマッチングスキームが、非常に優れた結果をもたらす。かかるスキームにおいては、十分に近接した一致が発見されると、それ以上の符号の比較は行われない。
【００５５】
図３は、本発明の好適な実施形態に係る、ＣＥＮ装置上でＶＳＣＣのコンパクト・ビデオ符号を算出するための主要処理ステップの簡略化されたフローチャートである。この処理は、システムが図１のＶＳＣＣ処理によって生成された抽出フレームからビデオを生成することから開始する（ステップ３０）。システムは、生成されたビデオからコンパクト・ビデオ符号を局所的に算出し、（生成されたビデオよりもファイルサイズが遥かに小さい）コンパクト・ビデオ符号でビデオを表現する（ステップ３２）。
【００５６】
次いで、システムは、そのコンパクト・ビデオ符号を（局所的に、又は遠隔で利用可能な）データベース内の符号と比較する（ステップ３４）。システムは、一致する符号を検索する（ステップ３６）。一致が検出された場合、装置上で実行中のアプリケーションへの通知がトリガされる（ステップ３８）。一致が検出されない場合、新たな抽出フレームのセットからビデオを生成するために、処理がステップ３０へと戻される。
【００５７】
多様な候補が生成されるフレームにおいて、符号は候補の各々について算出されうるものであり、マッチングは全ての候補符号に対して実行される。符合の比較も同様に、ビデオ信号面から算出されたフィンガープリント符号の各々を、データベース内に記憶された全ての符号と比較することによって実行されることが可能である。これが、データベース内の符号の数と共に線形に増大するマッチング時間をもたらす。本発明の別の実装において、欲張り法によるマッチングスキームが、非常に優れた結果をもたらす。かかるスキームにおいては、十分に近接した一致が発見されると、それ以上の符号の比較は行われない。
【００５８】
図４は、本発明の好適な実施形態に係る、ＣＥＮ装置上でＶＳＣＣの符号を他の符号と比較するための主要処理ステップの簡略化されたフローチャートである。この処理は、システムがＣＥＮ装置上でコンパクト符号を記憶することから開始する（ステップ４０）。システムは、図１のＶＳＣＣ処理において説明されたとおり、ＣＥＮ装置を用いてビデオ信号面を検出し、抽出する（ステップ４２）。システムは、図３のビデオ符号の処理において説明されたとおり、コンパクト・ビデオ符号を算出する（ステップ４４）。
【００５９】
システムは、最近生成されたコンパクト・ビデオ符号を、装置上に局所的に記憶された他のコンパクト・ビデオ符号と比較する（ステップ４６）。システムは、一致する符号を検索する（ステップ４８）。一致が発見された場合、装置上で実行中のアプリケーションへの通知がトリガされる（ステップ５０）。選択的に、リスト内の符号一致からのメタデータが検索される（ステップ５２）。一致が検出されない場合、処理がステップ４２へと戻される。
【００６０】
多様な候補が生成されるフレームにおいて、符号は候補の各々について算出されうるものであり、マッチングは全ての候補符号に対して実行される。符合の比較も同様に、ビデオ信号面から算出されたフィンガープリント符号の各々を、データベース内に記憶された全ての符号と比較することによって実行されることが可能である。これが、データベース内の符号の数と共に線形に増大するマッチング時間をもたらす。本発明の別の実装において、欲張り法によるマッチングスキームが、非常に優れた結果をもたらす。かかるスキームにおいては、十分に近接した一致が発見されると、それ以上の符号の比較は行われない。
【００６１】
図５は、本発明の好適な実施形態に係る、ＶＳＣＣの符号を、遠隔サーバ内のビデオストリームのためにリアルタイムで生成された一群のコンパクト符号と比較するための主要処理ステップの簡略化されたフローチャートである。この処理ステップの説明において、例示的なビデオストリームとしてＴＶ配信が用いられる。この処理は、ＴＶ配信（又は他のビデオストリーム）を取得することによって開始する（ステップ６０）。システムは、ＴＶ配信から関連メタデータを抽出する（ステップ６２）。次いで、システムは、ＴＶ配信に対応する関連メタデータを他の情報源から抽出する（ステップ６４）。
【００６２】
例えば、こうした関連メタデータは、電子番組ガイド、時間、番組のタイトル、サムネイル画像、番組の詳細、サブタイトル、ビデオ配信の視覚的及び音声的コンテンツにおけるオブジェクトの検出（例えば、顔、ビデオ内に表示される文章、特定のオブジェクト、製品表示、ロゴ、キーワード、プロモーション、コマーシャル、及びジングル）を含むことが可能である。
【００６３】
ＴＶ配信からフィンガープリント符号が算出され（ステップ６６）、選択的に、そのフィンガープリント符号に関連メタデータが追加される（ステップ６８）。その後、フィンガープリント符号は関連メタデータと共にデータベース内に記憶される（ステップ７０）。その後、システムは、この処理をステップ６２に戻って繰り返す。
【００６４】
図６は、本発明の好適な実施形態に係る、バックオフィス比較を実行するための主要処理ステップの簡略化されたフローチャートである。システムは、はじめに、ビデオ配信から（例えば、デジタルビデオ・テレビ放送、ケーブルＴＶ，衛星ＴＶ，オンライン・ストリーミング・チャンネル、ＤＶＤ，又は任意の他のビデオ源から）ビデオ信号を受信する。この処理は、システムが比較のためのクライアントからの要求を受信することから開始する（ステップ８０）。
【００６５】
次いで、システムは、（図３の処理を介して）装置上で生成されたコンパクト・ビデオ符号を、（図５の処理を介して）関連メタデータを含むビデオ配信から算出されたフィンガープリント符号と共に算出する（ステップ８４）。システムは装置に対してメタデータを送信し、要求からの符号がデータベース内の符号と比較される（ステップ８６）。システムは一致する符号を検索する（ステップ８８）。一致が発見された場合、フィンガープリント符号に対応する関連メタデータがクライアントに送信される（ステップ９０）。一致が発見されない場合、「一致なし」の通知メッセージがクライアントに送信される（ステップ９２）。
【００６６】
図７は、本発明の好適な実施形態に係る、テレビ受像機又はビデオディスプレイからビデオ信号面を検出するための主要処理ステップの簡略化されたフローチャートである。図７は、ビデオ信号面の検出及び抽出のための例示的な実施形態を表す。同じ結果を得るために他のアプローチが実装されうることに留意されたい。
【００６７】
この処理は、システムが、図１のＶＳＣＣ処理において説明されたとおり、ＣＥＮ装置を用いてビデオ信号面を検出及び抽出することから開始する（ステップ１００）。カラー画像は複数チャネルに分割される（ステップ１０２）。システムは、前のフレームに対する検出が成功であったかどうかを判定する（ステップ１０４）。検出が成功ではなかった場合、新たなチャネル及び閾値が選択される（ステップ１０６）。システムは、フレーム内で四角形の検出を試み（ステップ１０８）、四角形が検出されたか否かを確認する（ステップ１１０）。ステップ１０８における四角形の抽出は、１つ以上の候補四角形を生成しうることに留意されたい。
【００６８】
四角形が検出されない場合、システムは、新たなチャネル及び閾値を選択するかどうかを決定する（ステップ１１２）。システムは、ステップ１０６へと戻るか、又は「四角形は発見されず」のメッセージを返す（ステップ１１４）。ステップ１０４におけるフレーム検出が成功であった場合、システムは、前のフレームから記憶されたチャネル及び閾値を使用し（ステップ１１６）、処理はステップ１０８へと続く。ステップ１１０において四角形が検出された場合、システムは、成功したチャネル及び閾値を記憶し（ステップ１１８）、四角形の座標を返す（ステップ１２０）。
【００６９】
図８は、本発明の好適な実施形態に係る、テレビ受像機又はビデオディスプレイから四角形を検出するための主要処理ステップの簡略化されたフローチャートである。図８は、四角形の検出のための例示的な実施形態を表す。同様の結果を得るために他のアプローチが実装されうることに留意されたい。図１２及び図１３は、ＴＶ又はビデオディスプレイに対応する四角形の抽出のための別の実施形態を提供する。
【００７０】
図８の処理は、システムが選択されたカラー・チャネル「Ｃ」及び閾値「Ｔ」を取得することから開始する（ステップ１３０）。チャネルＣは閾値Ｔで閾値処理され（ステップ１３２）、得られた二値画像における連結成分（例えば、画像処理の文献で用いられるような、接触し隣接する前景ピクセルのクラスター）が検出される（ステップ１３４）。次いで、全ての連結成分が反復して処理され（ステップ１３６）、各連結成分の輪郭がポリゴンで近似される（ステップ１３８）。ステップ１３８は、１つ以上の候補ポリゴンを生成しうる。
【００７１】
次いで、システムは、ポリゴンが凸四角形であるか否かを判定する（ステップ１４０）。ポリゴンが凸四角形ではない場合、システムは、連結成分の（計算幾何学で用いられるような）凸包を探し出し（ステップ１４２）、その凸包をポリゴンで近似する（ステップ１４４）。システムは、そのポリゴンが凸四角形であるか否かを確認する（ステップ１４６）。そのポリゴンが凸四角形ではない場合、システムは、処理ループの中に連結成分が残っているか否かを確認する（ステップ１４８）。処理ループ中に連結成分が残っている場合、処理はステップ１３８へと戻る。
【００７２】
ステップ１４０又はステップ１４６において、ポリゴンが凸四角形である場合、システムは、検出された四角形を記憶し（ステップ１５０）、「欲張り法」（すなわち、最初に検出された凸四角形のみの検索）がアクティブであるかどうかを判定する（ステップ１５２）。欲張り法がアクティブではない場合、処理はステップ１４８へと続く。欲張り法がアクティブである場合、又はステップ１４８において処理ループ中に連結成分が残っていない場合、システムは、任意の発見された四角形の座標を返す（ステップ１５４）。
【００７３】
図９は、本発明の好適な実施形態に係る、背景シーンからＶＳＣＣを取得するためのシステム・アーキテクチャの簡略化された概念図である。放送局１６０（例えば、ＴＶ、ケーブル、及び衛星）は、バックオフィスシステム１６６に対して、送信信号Ａ及びＢのそれぞれを介して、ビデオ配信１６２（例えば、ＤＶＢ−Ｔ、ＡＴＳＣ、及びＴＶ）及びメタデータ１６４（例えば、電子番組ガイド、及びサブタイトル）を伝送する。バックオフィスシステム１６６は、コンパクト符号を算出及び記憶するためのコンパクト符号ジェネレータ１６８、関連メタデータを割り当てるためのメタデータ割り当てモジュール１７０、種々のデータベース（例えば、番組インデックス・データベース１７４、アド・インデックス・データベース１７６、及び視聴者／ビネット・インデックス・データベース１７８）を有するビデオ・インデックス・リポジトリ１７２、及び、リアルタイム・コンパレータ１８０を含む。ビネットとは、映画の予告編などの短いビデオクリップである。
【００７４】
背景シーン１８２におけるビデオディスプレイ１８１は、放送局１６０のコンテンツを表示する。ＣＥＮ装置１８４は、送信信号Ｃを介して、ビデオディスプレイ１８１を含む背景シーン１８２をキャプチャする。ＣＥＮ装置１８４は、表示されたコンテンツを検出し、コンテンツからフレームを抽出し、フレームのコンパクト符号を算出する。その後、ＣＥＮ装置１８４は、送信信号Ｄを介して、コンパクト符号をリアルタイム・コンパレータ１８０に送信する。
【００７５】
図９における、ビデオディスプレイ１８１及びＣＥＮ装置１８４のディスプレイの拡大図は、コンテンツのキャプチャされた画像をフレームへと処理するためにビデオディスプレイ１８１から検出され、ＣＥＮ装置１８４上の背景シーン１８２から抽出された四角形１８６を示す。次いで、リアルタイム・コンパレータ１８０が割り当てられた関連メタデータをＣＥＮ装置１８４に伝送し、この関連メタデータは、画像と結合されて、ソーシャルネットワークにおいてユーザの知人と共有されることが可能である。
【００７６】
図１０は、本発明の好適な実施形態に係る、画像からコンパクト符号を生成するための主要処理ステップの簡略化されたフローチャートである。この処理は、システムがＣＥＮ装置からフレームを取得し（ステップ１９０）、そのフレームがカラー画像であるか否かを判定することから開始する（ステップ１９２）。フレームがカラー画像である場合、システムはそのフレームをグレースケール画像に変換する（ステップ１９４）。そのフレームがカラー画像ではない場合、又はフレームをグレースケール画像へと変換した後、システムは空の符号列「Ｓ」を初期化する（ステップ１９６）。
【００７７】
次いで、システムは、スケール・レベル「Ｌ」を１に設定し（ステップ１９８）、画像をＬ×Ｌの矩形部分画像に分割し（ステップ２００）、全ての部分画像を反復的に処理し（ステップ２０２）、部分画像の各々に対して符号列「Ｋ」を生成し（ステップ２０４）、ＳにＫを付加する（ステップ２０６）。次いで、システムは、処理ループの中に部分画像が残っているか否かを判定する（ステップ２０８）。処理ループ中に部分画像が残っている場合、処理はステップ２０４へと戻る。処理ループ中に部分画像が残っていない場合、システムは、Ｌが使用のための最大スケール・レベルに等しいかどうかを確認する（ステップ２１０）。Ｌが最大スケール・レベルに等しいものではない場合、システムは、Ｌに１を加え（ステップ２１２）、ステップ２００に戻る。Ｌが最大スケール・レベルに等しい場合、システムは、完全な符号列Ｓを返す（ステップ２１４）。
【００７８】
使用のための最大スケール・レベルは、入力画像の解像度及びキャプチャの際に関心を引かれた細部の量に基づいて選択されることが可能である。一部の例示的な実装においては、最大スケール・レベルが６のときに非常に優れた結果が得られた。
【００７９】
（図５に関して説明されたように）フィンガープリント符号が遠隔サーバに送信されるときは常に、フィンガープリント符号は送信の前に符号化されうることに留意されたい。この符号化は所望のプラットフォームに応じて決まり、様々な利点をもたらす。一例として、図１０に関して説明されたようなビットの二進列の場合を考える。可能な送信符号化は、圧縮、文字列表現（縮小された文字セット、例えばＡＮＳＩ  ＡＳＣＩＩの１２８文字中の６４又は８５文字を用いるものであり、人間に解読可能かつプラットフォーム独立の形式でコンパクトに表現されうる）、又はＸＭＬ若しくはＪＳＯＮなどのテキストベースのデータ形式を含みうるが、これらに限定されるものではない。また、テキストベースのデータ形式の場合、その文字符号化は、選択された形式に特有の特殊文字を回避しうる。選択的に、プラットフォーム依存又はプラットフォーム独立のいずれかでありうる二進符号化も用いられうる。
【００８０】
図１１は、本発明の好適な実施形態に係る、部分画像からコンパクト符号を生成するための主要処理ステップの簡略化されたフローチャートである。この処理は、システムが部分画像領域を取得し（ステップ２２０）、空の符号列「Ｋ」を初期化することから開始する（ステップ２２２）。次いで、システムは、左半分のピクセル総和が右半分のピクセル総和よりも小さいかどうかを判定する（ステップ２２４）。
【００８１】
左半分のピクセル総和が右半分のピクセル総和よりも小さいものではない場合、システムはＫに０ビットを付加し（ステップ２２６）、ステップ２３０へと続く。左半分のピクセル総和が右半分のピクセル総和よりも小さい場合、システムはＫに１ビットを付加し（ステップ２２８）、ステップ２３０へと続く。
【００８２】
次いで、システムは、上半分のピクセル総和が下半分のピクセル総和よりも小さいかどうかを判定する（ステップ２３０）。上半分のピクセル総和が下半分のピクセル総和よりも小さいものではない場合、システムはＫに０ビットを付加し（ステップ２３２）、ステップ２３６へと続く。上半分のピクセル総和が下半分のピクセル総和よりも小さい場合、システムはＫに１ビットを付加し（ステップ２３４）、ステップ２３６へと続く。
【００８３】
次いで、システムは、左上４分の１及び右下４分の１のピクセル総和が右上４分の１及び左下４分の１のピクセル総和よりも小さいかどうかを判定する（ステップ２３６）。左上４分の１及び右下４分の１のピクセル総和が右上４分の１及び左下４分の１のピクセル総和よりも小さいものではない場合、システムはＫに０ビットを付加し（ステップ２３８）、ステップ２４２へと続く。左上４分の１及び右下４分の１のピクセル総和が右上４分の１及び左下４分の１のピクセル総和よりも小さい場合、システムはＫに１ビットを付加し（ステップ２４０）、ステップ２４２へと続く。
【００８４】
次いで、システムは、水平３分の１の中央部のピクセル総和が水平３分の１の左部及び右部のピクセル総和よりも小さいかどうかを判定する（ステップ２４２）。水平３分の１の中央部のピクセル総和が水平３分の１の左部及び右部のピクセル総和よりも小さいものではない場合、システムはＫに０ビットを付加し（ステップ２４４）、ステップ２４８へと続く。水平３分の１の中央部のピクセル総和が水平３分の１の左部及び右部のピクセル総和よりも小さい場合、システムはＫに１ビットを付加し〈ステップ２４６〉、ステップ２４８へと続く。
【００８５】
次いで、システムは、垂直３分の１の中央部のピクセル総和が垂直３分の１の上部及び下部のピクセル総和よりも小さいかどうかを判定する（ステップ２４８）。垂直３分の１の中央部のピクセル総和が垂直３分の１の上部及び下部のピクセル総和よりも小さいものではない場合、システムはＫに０ビットを付加し（ステップ２５０）、ステップ２５４へと続く。垂直３分の１の中央部のピクセル総和が垂直３分の１の上部及び下部のピクセル総和よりも小さい場合、システムはＫに１ビットを付加し（ステップ２５２）、二進ビット列である符号列Ｋを返す（ステップ２５４）。
【００８６】
図１２は、本発明の好適な実施形態に係る、テレビ受像機又はビデオディスプレイからビデオ信号面を検出するための主要処理ステップの簡略化されたフローチャートである。この処理は、システムが装置からグレースケール・フレームを取得し（ステップ２６０）、垂直端部セグメント（ステップ２６２）及び水平端部セグメント（ステップ２６４）を検出することから開始する。ステップ２６２及びステップ２６４、並びに後続の接続処理ステップは、（どれか１つが最初に実行されるように）連続的に、又は同時に実行されることが可能である。
【００８７】
次いで、システムは、画像中心の上側及び下側に１つずつの終点を有する垂直端部セグメントのみを選択し（ステップ２６６）、画像中心の左側及び右側に１つずつの終点を有する水平端部セグメントのみを選択する（ステップ２６８）。次いで、システムは、選択された垂直セグメントを黒色画像「Ｉ」上に描画し（ステップ２７０）、選択された水平セグメントを画像Ｉ上に描画する（ステップ２７２）。次いで、システムは、セグメントの線を接続するために形態学的拡張を実行し（ステップ２７４）、四角形を抽出する（ステップ２７６）。ステップ２７６は、１つ以上の候補四角形を生成しうる。ステップ２７６の四角形抽出のための詳細な処理フローは、以下に図１３に関連して説明される。
【００８８】
図１３は、本発明の別の実施形態に係る、テレビ受像機又はビデオディスプレイから四角形を検出するための主要処理ステップの簡略化されたフローチャートである。この処理は、システムが、図１２に関連して説明された選択された端部と共に二値画像を取得することから開始する（ステップ２８０）。システムは、この二値画像中の連結成分を検出し（ステップ２８２）、全ての連結成分を反復的に処理し（ステップ２８４）、連結成分の輪郭をポリゴンで近似する（ステップ２８６）。ステップ２８６は、１つ以上の候補ポリゴンを生成しうる。
【００８９】
次いで、システムは、ポリゴンが凸四角形であるかどうかを判定する（ステップ２８８）。ポリゴンが凸四角形である場合、処理はステップ３０４へと続く。ポリゴンが凸四角形ではない場合、システムは各連結成分の輪郭の凸包を探し出し（ステップ２９０）、その凸包をポリゴンで近似する（ステップ２９２）。
【００９０】
次いで、システムは、そのポリゴンが凸四角形であるかどうかを判定する（ステップ２９４）。そのポリゴンが凸四角形である場合、処理はステップ３０４へと続く。そのポリゴンが凸四角形ではない場合、システムはそのポリゴンが三角形であるかどうかを判定する（ステップ２９６）。そのポリゴンが三角形ではない場合、処理はステップ３０６へと続く。そのポリゴンが三角形である場合、システムは、角のうちの１つが９０度に近いものであるかどうかを判定する（ステップ２９８）。９０度に近い角がない場合、処理はステップ３０６へと続く。
【００９１】
角の１つが９０度に近いものである場合、システムは、斜辺の中点が画像中心に近いものであるかどうかを判定する（ステップ３００）。斜辺の中点が画像中心に近いものではない場合、処理はステップ３０６へと続く。斜辺の中点が画像中心に近いものである場合、システムは、四角形（例えば、平行四辺形）を完成させるために第４の点を付加し（ステップ３０２）、検出された四角形を記憶する（ステップ３０４）。
【００９２】
次いで、システムは、処理ループの中に連結成分が残っているかどうかを判定する（ステップ３０６）。処理ループ中に連結成分が残っている場合、処理はステップ２８６へと戻る。処理ループ中に連結成分が残っていない場合、システムは任意の発見された四角形の座標を返す（ステップ３０８）。
【００９３】
本発明の一部の実装において、サブリニア・マッチングを提供することが可能である。ツリー型のデータ構造は、対数時間検索及びマッチングを提供可能である。二進ビット列符号の場合、文献に説明されるような適切な候補（例えば、ハミング距離及びメトリック・ツリー（オンライン資料Ｗｉｋｉｐｅｄｉａの「Ｍｅｔｒｉｃ＿ｔｒｅｅ」の下のリストを参照されたい））を用いて距離メトリックが実装されることが可能である。他の実装においては、カバー・ツリー・データ構造が非常に優れた結果をもたらした（オンライン資料Ｗｉｋｉｐｅｄｉａの「Ｃｏｖｅｒ＿ｔｒｅｅ」の下のリストの、−Ａｌｉｎａ  Ｂｅｙｇｅｌｚｉｍｅｒ，  Ｓｈａｍ  Ｋａｋａｄｅ，  ａｎｄ  Ｊｏｈｎ  Ｌａｎｇｆｏｒｄ，  Ｃｏｖｅｒ  Ｔｒｅｅｓ  ｆｏｒ  Ｎｅａｒｅｓｔ  Ｎｅｉｇｈｂｏｒ，  ＩＣＭＬ  ２００６を参照されたい）。
【００９４】
限られた数の実施形態に関連して本発明が説明されたが、本発明の多くの変形、修正、及び他の応用が行われうることが理解されよう。
【図１】
2014512128.tif 000003
【図２】
2014512128.tif 000004
【図３】
2014512128.tif 000005
【図４】
2014512128.tif 000006
【図５】
2014512128.tif 000007
【図６】
2014512128.tif 000008
【図７】
2014512128.tif 000009
【図８】
2014512128.tif 000010
【図９】
2014512128.tif 000011
【図１０】
2014512128.tif 000012
【図１１】
2014512128.tif 000013
【図１２】
2014512128.tif 000014
【図１３】
2014512128.tif 000015
【国際調査報告】
2014512128.tif 000016