入力画像シーケンスを安全に処理する方法及びシステム
方法は、入力画像シーケンスを安全に処理する。入力画像シーケンスがクライアントにおいて取得される。各入力画像中の画素は置換πに従ってランダムに置換されて、各入力画像について置換画像が生成される。各置換画像はサーバに転送され、サーバは置換画像から背景画像を保持する。サーバにおいて、各置換画像は背景画像と結合されて、各置換画像について対応する置換された動き画像が生成される。各置換された動き画像はクライアントに転送され、各置換された動き画像中の画素は逆置換π−１に従って並べ換えられて、各入力画像について対応する動き画像が回復される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはコンピュータビジョンに関し、特に画像及びビデオの安全なマルチパーティ処理に関する。
【背景技術】
【０００２】
全世界的な通信ネットワークが利用可能になったことで、一部のデータ処理業務をいくつかの理由で外部の企業に「外注」することが一般的に行われるようになった。例えば、処理をより低コストで行うことができるか、又は外部の企業がより良い計算資源又はより良い技術を有する。
【０００３】
データ処理を外注する際の問題の１つとして、他の企業による機密情報の不正使用がある。例えば、外部の企業に、監視ビデオ、又は機密スキャン文書の中身を知られることなく、それらのビデオ又は文書を多数処理してもらうことが望ましい。別の用途として、限られた電力資源及び計算資源を有する携帯電話によって取得した画像の複雑な分析を行うことが望ましい。
【０００４】
このような用途に対して、従来の暗号技術はデータを、輸送中にのみ保護し、別の企業による処理中には保護しない。ゼロ知識技法に頼ることはできる。しかし、ゼロ知識技法は計算集約的であることが知られている。このような技法を画像及びビデオストリーム等の大きなデータセットに適用することは、複雑度の低いデバイスにとって非実用的である。例えば、１枚の高解像度画像は数百万バイトを含み、ビデオの場合、画像は、３０フレーム毎秒以上のレートで生じ得る。
【０００５】
ゼロ知識又は安全なマルチパーティ計算は、Yao著「How to generate and exchange secrets」（Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, pp. 162-167, 1986）に初めて、特定の問題について記載された。後に、ゼロ知識技法は他の問題に拡張された（Goldreich他著「How to play any mental game - a completeness theorem for protocols with honest majority」（19th ACM Symposium on the Theory of Computing, pp 218-229, 1987））。しかし、それらの理論的構成概念は、実用に供するには依然として要求の高すぎるものであった。
【０００６】
それ以後、多くの安全化（secured）方法が記載されてきた（Chang他著「Oblivious Polynomial Evaluation and Oblivious Neural Learning」（Advances in Cryptology, Asiacrypt '01, Lecture Notes in Computer Science Vol. 2248, pages 369-384, 2001）、Clifton他著「Tools for Privacy Preserving Distributed Data Mining」（SIGKDD Explorations, 4(2):28-34, 2002）、Koller他著「Protected Interactive 3D Graphics Via Remote Rendering」（SIGGRAPH 2004）、Lindell他著「Privacy preserving data mining」（Advances in Cryptology - Crypto 2000, LNCS 1880, 2000）、Naor他著「Oblivious Polynomial Evaluation」（Proc. of the 31st Symp. on Theory of Computer Science (STOC), pp. 245-254, May 1, 999）、及びDu他著「Privacy-preserving cooperative scientific computations」（4th IEEE Computer Security Foundations Workshop, pp. 273-282, June 11, 2001））。問題の完全な論考（treatment）は、Goldreichの参考書「Foundations of Cryptography」（Cambridge University Press, 1998）に見出すことができる。
【０００７】
安全なマルチパーティ計算は多くの場合、正確さ、安全性、及びオーバーヘッドについて分析される。正確さは、安全なプロセスが理想解にどこまで近づくかを測定する。安全性は、マルチパーティのやりとりから得ることのできる情報量を測定する。オーバーヘッドは複雑度及び効率の測度である。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
クライアントコンピュータによって取得された画像及びビデオの、サーバコンピュータを用いた安全な処理を提供することが望ましい。さらに、クライアントコンピュータにおいて必要とされる計算資源を最小限に抑えることが望ましい。
【課題を解決するための手段】
【０００９】
［発明の開示］
［発明の概要］
本発明は、クライアントコンピュータによって生成された画像及びビデオの中身をサーバコンピュータのプロセスに明かすことなく、それらの画像を処理するシステム及び方法を提供する。さらに、サーバコンピュータの処理技法をクライアントコンピュータに対して安全に保つことが望ましい。
【００１０】
本発明は、ビジョン問題の解決にゼロ知識技法を適用する。すなわち、コンピュータビジョン処理は、処理される画像に対して「ブラインド（盲目的）」である。したがって、画像に対して操作を行う方法は、画像の内容又は処理結果を何も知ることがない。本方法は、監視ビデオの安全な処理、例えば背景モデリング、物体検出、及び顔認識を行うために用いることができる。
【００１１】
特に、本発明は、入力画像シーケンスを安全に処理する方法を提供する。入力画像シーケンスがクライアントにおいて取得される。各入力画像中の画素は置換πに従ってランダムに置換されて、各入力画像について置換画像が生成される。各置換画像はサーバに転送され、サーバは置換画像から背景画像を保持する。サーバにおいて、各置換画像は背景画像と結合されて、各置換画像について対応する置換された動き画像が生成される。各置換された動き画像はクライアントに転送され、各置換された動き画像中の画素は逆置換π−１に従って並べ換えられて、各入力画像について対応する動き画像が回復される。
【発明を実施するための最良の形態】
【００１２】
システムの概要
図１Ａに示すように、画像を安全に処理するシステム１００が例示的なセキュリティ用途に関して説明される。システム１００において、クライアントコンピュータ（クライアント）１０がネットワーク３０を介してサーバコンピュータ（サーバ）２０に接続される。利点として、クライアント１０は、限られた処理資源及び電力資源を有することができる（例えば、ラップトップ、低コストセンサ、又は携帯電話）。
【００１３】
クライアントは、画像シーケンス２０１、すなわち「秘密」ビデオを取得する。画像２０１は、プロセス２００、３００、及び４００を用いて処理される。これらのプロセスは共同して、実線によって示されるようにクライアントコンピュータ上で部分的に、また破線によって示されるようにサーバコンピュータ上で部分的に操作を行う。これはマルチパーティ処理として知られる。これらのプロセスは、画像２０１の内容がサーバに明かされず、且つサーバプロセス及びデータ２１がクライアントに明かされないように動作する。
【００１４】
クライアントは、マルチパーティ処理の結果を用いて、画像２０１中の「秘密」物体を検出することができる。同時に、クライアントは、サーバによって部分的に行われるプロセス２００、３００、及び４００の「秘密」部分、並びにサーバによって保持される秘密データ構造２１を知ることを防止される。
【００１５】
この処理は、基礎にある画像の内容が、サーバにおいて画像に対して操作を行うプロセスに明かされないため安全である。したがって、入力画像２０１は、単純なクライアントコンピュータによって取得されることができ、その一方で、安全な処理が、より高度なサーバコンピュータによって行われる。処理結果はサーバには無意味である。クライアントのみが「秘密」処理結果を回復することができる。したがって、本発明は、「ブラインドな」コンピュータビジョン処理を提供する。
【００１６】
図１Ｂに示すように、方法１０１は、３つの基本プロセス２００、３００、及び４００を含む。第１に、ビデオ２０１、すなわち画像の時間シーケンスを処理し、動き画像２０９を求める２００。動き画像はビデオ中の移動成分のみを含む。移動成分は「前景」としても知られ、残りの成分は静止「背景」モデルと呼ばれる。第２に、動き画像をさらに処理して、連結した前景成分３０９をラベリングする３００ことができる。第３に、連結成分を処理して、物体４０９を検出する４００ことができる。プロセス２００、３００、及び４００への入力画像は異なり得ることに留意すべきである。すなわち、各プロセスは、いかなる以前の処理又は後続の処理にも関係なく行うことができる。例えば、物体検出は、任意のタイプの入力画像に対して行うことができる。
【００１７】
この方法は全体として、小さいデータセットほど処理が複雑度を増すデータ削減又は「トリアージ」と考えることもできる。ビデオ中の全画素の全強度範囲に対して操作を行う最初のステップ２００は非常に単純且つ高速である。中間のステップ３００は、少しより複雑ではあるものの、大抵は、遥かに小さなデータセットである２進値すなわち０と１を格納する小さなタイルセットに対して操作を行う。最後のステップは、より複雑な操作を用いるが、元の画像内容のごく小部分のみを扱えばよい。したがって、本発明は、非常に大きなデータセットに対して非常に単純な技法を適用して、処理する必要があるデータ量を劇的に低減し、その一方でトリアージ中に、より複雑な処置を非常に小さなデータセットのために残しておく。
【００１８】
ブラインドな動き画像
図２Ａは、「秘密」ビデオの例示的な入力画像２０１を示す。この例示的なビデオは、一群の歩行者９９のいる街頭シーンのものである。
【００１９】
図２Ｂは、動き画像２０９を求める２００ステップを示す。ビデオ２０１の入力画像を、クライアントコンピュータ１０に接続されたカメラによって取得することができる。１つの利点として、クライアントコンピュータは、限られた処理資源を有することができる、例えば、クライアントは携帯電話に組み込まれる。
【００２０】
シーケンス中の各入力画像Ｉ中の画素をクライアントコンピュータによって、置換πを用いて擬似ランダムに空間的に置換して２１０、置換画像Ｉ’２０２を、Ｉ’＝πＩとなるように生成する。擬似ランダムとは、どの以前の値からも次の値を求めることができないが、乱数発生器は、おそらくはそのシード値を知っているため、必要であれば常にランダムな値の特定のシーケンスを再構成することができることを意味する。明らかに、置換画像中の画素の空間分布はランダムであり、元の入力画像は逆置換π−１を用いて、Ｉ＝π−１Ｉ’となるように並べ換えることによって回復することができる。
【００２１】
任意で、置換画像２０２をより大きなランダム画像２０３に埋め込んで、組み込み画像２０４を生成することができる。より大きなランダム画像２０３中の画素もまた、置換画像２０２の強度ヒストグラムがより大きなランダム画像の強度ヒストグラムと異なるように、擬似ランダムに生成する。さらに、ランダム画像中の画素の一部の強度値をランダムに変化させて、組み込み画像２０４中に「偽物の」動きを生成することができる。組み込まれる置換画像２０２のロケーション、サイズ及び向きもまた、入力画像ごとにランダムに変化させることができる。
【００２２】
組み込み画像２０４を、背景／前景モデリングアプリケーション２３０にアクセスできるサーバコンピュータ２０に転送する２２１。これは、任意の従来のモデリングアプリケーション、又はサーバしか知らない独自のプロセスとすることができる。１つの利点として、サーバは、クライアントコンピュータよりも大幅に多い処理資源を有する。転送は、ネットワーク３０、又は携帯用記憶媒体等の他の手段を介して行うことができる。
【００２３】
サーバ２０におけるアプリケーション２３０は、現在の背景画像Ｂ２０６を保持する。この背景画像は、各入力画像又は以前に処理された置換画像のセットから更新することができる。例えば、背景画像は、最後のＮ枚の入力画像、例えばＮ＝１０の平均を用いる。移動平均を用いることによって、シーンにおける急激な変化の影響又は他の短期的な影響を最小限に抑える。次に、結合すること、例えば現在の背景画像２０６から組み込み画像２０４を減算することによって、置換された動き画像Ｍ’２０５を生成する。特定の入力画素と背景画素の間の差が或る所定の閾値Θよりも大きい場合、その入力画素を動き画素とみなし、相応にラベリングする。したがって、置換された動き画像２０５は次のように表される。
【００２４】
【数１】
【００２５】
置換された動き画像Ｍ’２０５をクライアントコンピュータに転送する２３１。クライアントコンピュータは、必要に応じて組み込み部分を抽出する。次に、Ｍ＝π１（Ｍ’）に従って空間的な置換を元に戻すことによって抽出部分の画素を元の順序に並べ換え、移動成分２９９に関連する成分のみを有する動き画像Ｍ２０９を得る（図２Ｃを参照）。
【００２６】
背景及び動き画像は、格納されるデータ量を大幅に低減するために２値画像又は「マスク」画像とすることができることに留意すべきである。すなわち、動き画像中の或る画素は、移動していると見なされれば「１」であり、そうでなければ「０」である。「動き」画素の一部は雑音により誤っている可能性があることにも留意されたい。これらのアーティファクトを後述のように除去する。
【００２７】
正確さ
このプロセスは、画素ベースの背景減算が画素の空間的な順序に依存しないため、正確である。したがって、画素の順序を空間的に置換してもプロセスに影響はない。さらに、偽物の動き画素を組み込み画像に加えても、置換画像２０２中の偽物の画素と関心画素の間には相互作用がないため、プロセスに影響はない。
【００２８】
安全性
このプロセスは部分的に安全である。サーバは、入力画像２０１の内容を何も知ることができない。可能な置換数は多すぎて求められない。例えば、入力画像２０１がｎ個の画素を有し、組み込み画像がｃ＝２倍の大きさである場合、可能な置換数は
【００２９】
【数２】
【００３０】
となり、ｎは高解像度カメラの場合に１００万以上であり得る。
【００３１】
アプリケーション２３０を「知る」には、クライアントは、各画素の各入力及び出力を観察する必要がある。すなわち、クライアントは、クライアントとサーバの間のデータフローを分析する。しかしこれは、データセットのサイズにより非実用的になり得る。このプロセスは、サーバにおいて「秘密」データを一切必要としない。
【００３２】
複雑度及び効率
クライアントの複雑度及び通信オーバーヘッドは、入力画像のサイズにおいて線形である。所定のランダム順に従った画素の置換は問題にならない。並べ換えも同様に単純である。アプリケーション２３０の複雑度は置換に影響を受けない。
【００３３】
上記のプロセスは、本発明によるブラインドなコンピュータビジョンの特性のいくつかを示す。このプロセスは、従来のビジョン方法を画像に適用し、その一方で、画像の内容をサーバから隠す。サーバは、画像の正確な内容を判断することができないが、置換画像から何らかを知ることができる。例えば、画像のヒストグラムにより、画像が日中又は夜間のどちらに取得された可能性が高いかを判定することができる。サーバはまた、動き画素の数を計数して、画像中にどれだけ動きが存在するかを判断することができる。
【００３４】
この問題は、クライアントが置換画像を大きなランダム画像に組み込めば簡単に克服することができる。こうすることにより、サーバは、画像ヒストグラムから何も推測することができない。また、クライアントがランダム画素の一部をオンにして偽物の動き画素を生成する場合、サーバは、検出された動き画素が本物であるか偽物であるかさえ知ることができない。
【００３５】
サーバは、画素間の相関関係を経時的に観察して、それらの近接性を知るか、又は本物の動き画素と偽物の動き画素を区別することができることに留意すべきである。しかしクライアントは、偽物の動き画素を、本物の動き画素と同じ分布を有するように生成することができる。
【００３６】
このプロトコルの単純さは主に、各画素を個別に扱うことができ、よって空間的な順序は重要でないという事実によるものである。
【００３７】
次に、画像中の領域に対して操作を行う連結成分ラベリング等の安全なビジョンプロセスを説明する。
【００３８】
ブラインドな成分ラベリング
物体検出、物体追跡、又は物体及びパターン認識といった実際の用途において、動き画像２０９は、雑音及び誤った動き画素２９９を除去し（図２Ｃを参照）、単一の移動物体に関連する可能性が高い隣接画素を「連結」するためにさらなる処理を必要とする場合がある。入力画像は、任意の動き画像とすることができることに留意すべきである。
【００３９】
しかし、さらなる処理は、画素の空間的な順序に依存し得る。実際には、雑音が誤った動き画素を生じる恐れがあるため、動き画像２０９をきれいにする（clean）必要がある。残念ながら、置換は画像中の画素の空間的配置を破壊してしまい、連結成分が正しく機能しなくなってしまうため、入力画像中の画素を単純に置換することはもうできない。
【００４０】
フル画像に対して操作を行う拡張プロセスをまず説明し、次にタイルに対して操作を行う複雑度の低いプロセスを説明する。拡張プロセスは、入力画像をランダム画像の和集合に分割することによって機能する。ランダム画像は、いくつかの偽物のランダム画像とともにサーバに送られる。この場合、数十枚又は数百枚のランダム画像を用いて安全性を保証することができる。複雑度は、入力画像をタイルに分割することによって劇的に低減することができ、各タイルは個別の「画像」として扱われる。タイルがランダム順で送られる場合、サーバは、入力画像を復元するために二重の問題に直面する。
【００４１】
フル画像プロトコル
フル画像プロトコルは、入力画像をランダム画像の和集合として表現し、これらのランダム画像をランダム２値画像の大きな集合とともにサーバに送る。
【００４２】
サーバは、各画像に対して個別に連結成分ラベリングを行い、その結果をクライアントに送る。次に、クライアントは、それらの結果を結合して、ラベリングされた連結成分、すなわち可能な物体の最終結果を得る。
【００４３】
２値入力画像はＩ、例えば画像２０９であり、連結成分を有するラベリングされた画像３０９はＩ’、すなわち、連結成分ラベリングを行った後の画像Ｉである。複数のラベリングされた画像Ｈ１，．．．，Ｈｍがあり、各画像中の成分のラベルが例えば１から開始する場合、ラベリングされた画像のセットはＨ１バー，．．．，Ｈｍバーによって示され、各連結成分はｍ枚の画像すべてについて一意のラベルを有する。最後に、Ｉ（ｑ）は画像Ｉの画素位置ｑにおける値である。
【００４４】
フル画像を用いたブラインドな連結成分ラベリング
図３Ｅに示すように、サーバは、入力画像Ｉ２０９を有するとともに、連結成分ラベリングプロセス３００を有する。このプロセスの出力は、ラベリングされた連結成分画像Ｉバーである。サーバは、入力画像Ｉについて何ら知ることはない。
【００４５】
初めに、クライアントは、ｍ枚のランダム画像Ｈ１，．．．，Ｈｍを次のように生成する３７０。
【００４６】
【数３】
【００４７】
クライアントは、ｒ＞ｍ枚のランダム画像Ｕ１，．．．，Ｕｒ３７１をサーバに送り、秘密のｊ１，．．．，ｊｍの画像についてＵｊｉ＝Ｈｉであり、さらなる画像は偽物の画像である。
【００４８】
サーバは、画像Ｕごとに連結成分ラベリングを求め３７５、ラベリングした画像Ｕ１’，．．．，Ｕｒ’３７６をクライアントに送る。
【００４９】
クライアントは、画像Ｈ１’，．．．，Ｈｍ’を全てのラベリングされた画像にわたって固有のラベルでグローバルに再ラベリングし３８０、これらの画像をＨ’１バー，．．．，Ｈ’ｍバーによって示す。画素ｑごとに、Ｉ（ｑ）＝１となるように、Ｈ’１バー（ｑ），．．．，Ｈ’ｍバー（ｑ）が各画像の異なるラベルを表すものとする。次にクライアントは、グローバルラベリングされた画像から同値リスト｛Ｈ’ｉバー（Ｎｂｒ（ｑ））｝ｉｍ１を生成し、ここでＮｂｒ（ｑ）は各画素ｑの４つ又は８つの近傍画素のリストである。画素は、それらが動き画素であり、且つ互いに直に隣接する場合にのみ連結される。
【００５０】
サーバは、同値ラベルリスト３８１をスキャンし、同値類を判断し３８５、全てのラベルから同値類の代表値へのマッピング３８６を返す。
【００５１】
クライアントは、サーバから返されたマッピングに応じて各画像Ｈ１’バーを再ラベリングし３９０、全ての画素ｑについてＩバー（ｑ）＝ｍａｘ（｛Ｈｉ’バー（ｑ）｝ｉｍ１という最終結果を求め、それにより連結成分の最終画像３０９を形成する。
【００５２】
正確さ
このプロトコルは、各画像Ｈｉがサーバプロセスによって正確にラベリングされるため、正確である。さらに、Ｉ＝∪ｍｉ＝１ Ｈｉであるため、各画像Ｈｉは入力画像Ｉの動き又は「オン」画素の一部のみを含み、よって、元画像Ｉでは連結していない２つの領域を連結してしまうかもしれない偽の「オン」画素は付加されないことになる。
【００５３】
元画像Ｉ中の各連結成分は、複数のランダム画像Ｈｉにわたるいくつかの成分に分けることができるため、同一成分が複数のラベルを有し得る。しかし、全ての同値類について１つの代表値を計算する最終的なクライアントによる再ラベリングステップが、これに対処する。再ラベリングはまた、全てのランダム画像における全ての動き画素に対してラベルが１つしかないか、又は全くないことを保証する。
【００５４】
安全性
このプロトコルは、クライアントがサーバに複数の２値画像Ｕを送り、そのうちサブセットＨのみが入力画像を形成するため、安全である。適切なｒ及びｍについて、可能性の数
【００５５】
【数４】
【００５６】
は、求めるにはとても大きすぎる可能性がある。第２段階において、クライアントは、同値リストのリスト３８１を送る。クライアントは成分を既に再ラベリングしているため、サーバは新たなラベルを元画像と関連付けることができず、クライアントは安全化される。サーバは、安全化する必要があるいかなるプライベートデータも格納する必要がない。
【００５７】
複雑度及び効率
複雑度は、ｒに従って線形である。ランダム画像ごとに、サーバは連結成分ラベリングを行う。クライアントは、和集合をＩとするｍ枚のランダム画像と、付加的なｒ−ｍ枚の偽物のランダム画像とを生成する。
【００５８】
上記プロセスは、
【００５９】
【数５】
【００６０】
が大きければ安全である。例えば、ｒ＝１２８であり、ｍ＝６４である場合、
【００６１】
【数６】
【００６２】
の可能性を確認しなければならない。
【００６３】
タイルを用いたブラインドな連結成分ラベリング
この場合、図３Ａ〜図３Ｃに示すように、クライアントは各動き画像２０９を、重なり合う本物の画素タイルのセットＴｇ３１１に分割する３１０。明確にするために、タイルは一定の縮尺で示されていない。例えば、タイルは３×３画素であり、上下左右で１画素ずつ重なり合う。他のタイルサイズ及び重なりを用いることもできることに留意すべきである。しかし、タイルを大きくするほど、内容を判断し易くなる。さらに、クライアントは任意で、偽物の画素タイルＴｆ３２１を生成する３２０ことができる。
【００６４】
本物のタイル３１１及び偽物のタイル３２１は、擬似ランダム順でサーバに転送される。サーバは、各タイル中の、他の動き画素に「連結」した動き画素をローカルラベリングする３３０。或る画素は、少なくとも１つの他の動き画素に隣接している場合に連結していると言える。例えば、特定のタイル内で連結している第１の画素群の各画素にはラベルＧ１が付され、同一タイル内の第２の連結画素群の各画素にはラベルＧ２が付され、以下同様にラベリングされる。タイルごとに、ラベルはＧ１から再び開始する。すなわち、別のタイル内の第１の群及び第２の群もＧ１及びＧ２とラベリングされる。したがって、ラベル３３１は各タイルに対してローカルに一意である。
【００６５】
図３Ｃに３×３タイルについて示すように、動き画素（点描模様）３０１は、最高８つの隣接する動き画素を有し得る。なお、サーバは、タイルの一部が偽物であることも、タイルがランダムに空間的に順序付けされていることも知らない。単一の未連結画素及び非動き画素はラベリングされない。サーバは、動き画素の連結性を求める従来の又は独自のプロセスを用いることができる。
【００６６】
ラベリングされたタイル３３１はクライアントに転送される。クライアントは、偽物のタイルを廃棄し、連結画素がローカルラベリングされた動き画像を再構成する。クライアントは、「境界」画素をグローバルに一意のラベルにより再ラベリングする。これらの一意のラベルは擬似ランダムに生成することもできる。境界画素は、タイルの４つ又は８つの外側画素である。１画素分の重なりにより、境界画素は、サーバによって決定されるグローバルラベルが同じであるか又は異なる２つの隣接タイルに現れる可能性がある。
【００６７】
実際、図３Ａに示すように、タイル内の角の画素３０１は、最大４つの異なるラベルをサーバによって割り当てられる可能性がある。クライアントは、サーバによって２つの異なるラベルを付された隣接タイルの２つの境界画素が実際には同一画素であるかを判定することができ、よって一意のグローバルラベルと関連付けることができる。再ラベリング３４０により、一意のローカルラベル対のリスト３４１［Ｌ１（ｂｉ），Ｌ２（ｂｉ）］，．．．，［Ｌｋ−１（ｂｉ），Ｌｋ（ｂｉ）］が生成される。
【００６８】
クライアントは、リスト３４１をサーバに、さらに別の擬似ランダム順で転送する。サーバは、従来の又は独自の分類技法を用いて、それらの対を同値類３５１に分類する３５０。サーバは、独自の一意のラベルを各同値類３５１に割り当てる。
【００６９】
ラベリングされた同値類３５１はクライアントに転送される。クライアントは、これらのラベルを用いて、画素を連結画素の各セットについて一意のグローバルラベルにより再ラベリングし３６０、連結成分３０９を形成する（図３Ｄを参照）。
【００７０】
正確さ
このプロセスは、各タイルがサーバによって正確にローカルラベリングされるため、正確である。複数のタイルにわたって分散している連結画素は、タイル間に重なりがあるため、クライアントによって正確に融合される。同値類の判定３５０により、各連結画素群に一意のラベルが割り当てられることが保証される。
【００７１】
安全性
このプロセスは、ｐ個の本物のタイル及びｍ個の偽物のタイルについて、異なる可能性の数が
【００７２】
【数７】
【００７３】
と非常に大きいため安全である。３２０×２４０の画像の値ｍは約２０，０００タイルである。１００個の偽物のタイルを加える場合、置換される可能性の数は約Ｏ（２１４００）である。サーバが本物のタイルを検出できたとしても、多くの異なる画像のタイルヒストグラムが同じように見えるため、タイルの正確な空間的順序は分からないままである。タイル３１１、３２１のランダムな順序付けに対する対３４１のランダムな順序付けもまた、サーバが内容を分析することを極めて困難にする。
【００７４】
複雑度及び効率
ここでもまた、クライアントにおけるプロセスの複雑度は画像のサイズに対して線形である。画像をタイルに変換することは簡単である。
【００７５】
ブラインドな物体検出
最後のプロセス４００は物体検出である。物体検出は、図４Ａに示すように、スライド窓４０５を用いてラスタスキャン順に連結成分の画像３０９をスキャンする。スライド窓の各ロケーションにおいて、スライド窓の内容が物体を含むか否かの判定が行われる。
【００７６】
ニューラルネットワーク、サポートベクトルマシン、又はアダブースト等の多くの分類器を、加法モデル、又はカーネル関数の和、例えばラジアル基底関数、多項式関数、又はシグモイド関数として表現することができる。これらの関数は、前処理訓練段階中に求められる窓のドット積及びいくつかの原型パターンに対して操作を行う。
【００７７】
ゼロ知識法と機械学習技法の間には、ゼロ知識法が隠そうとするものであり、その一方で機械学習技法が推測しようとするものであるという点で自然な張力がある。本発明による方法では、クライアントは、サーバを用いて訓練画像をクライアントのためにラベリングし、後にそれらの訓練画像を用いて自身の分類器を訓練できるようにする。
【００７８】
以下では、クライアントは入力画像Ｉ４０１を有し、サーバは、畳み込みカーネルαｆ（ｘＴｙ）の形態の弱分類器（weak classifier）を有し、ここで、ｘは窓の内容であり、ｙは弱分類器であり、ｆは非線形関数であり、αは係数である。したがって、畳み込み演算を画像Ｉに適用し、次にその結果を分類器に渡す方法を説明すれば十分である。
【００７９】
弱分類は、画像を何らかのフィルタと畳み込み、次にその結果を何らかの非線形関数に通した結果に基づく。例えば、本明細書中に参照により援用されるP. Viola及びM. Jones著「Rapid Object Detection using a Boosted Cascade of Simple Features」（IEEE Conference on Computer Vision and Pattern Recognition, Hawaii, 2001）に記載されるように矩形フィルタを用いる。画像位置ごとに、スライド窓と矩形フィルタとのドット積を求める。畳み込み演算の結果を、アダブースト、又はサポートベクトルマシンにおけるカーネル関数、又はニューラルネットワークにおけるシグモイド関数等の非線形関数に通す。
【００８０】
要約すると、弱分類器は３つの構成要素、すなわち、ガウス関数、シグモイド関数等であり得る非線形関数ｆ（）、重み（アルファ）及び畳み込みカーネルｙを有する。画像をまず畳み込みカーネルｙと畳み込み、その結果を畳み込み画像として格納する。畳み込み画像中の各画素は、カーネルｙを、その画素を中心とする窓と畳み込んだ結果を含む。畳み込み画像中の画素を非線形関数ｆ（）に通し、アルファを乗算する。
【００８１】
ゼロ知識プロトコルは多くの場合、暗号化ベースのプロトコルと、代数ベースのプロトコルとに分類することができる。暗号化ベースのプロトコルでは、参加者（parties）は、公開−私有鍵暗号化等の標準的な技法を用いてデータを暗号化するため、他者（other parties）には情報が利用できない。これには、回避すべき高い計算コスト及び通信コストが伴う。
【００８２】
別法として、計算は速いが一部の情報を明かしてしまうかもしれない代数プロトコルを用いることができる。代数方法は、部分空間において操作を行うことによってベクトルを隠す。例えば、一方の参加者がベクトルｘ∈Ｒ４００を有する場合、プロトコルを行った後で、他方の参加者には、ｘが元の４００次元空間のうち一部の低次元部分空間、例えば１０次元部分空間にあることが分かる。
【００８３】
ブラインドな物体検出プロセス４００の１つの実施の形態では、クライアントの安全性のみが維持される。このプロトコルの変形は、クライアントがサーバを使用して、入力画像Ｉに対して従来の畳み込み、例えばエッジ検出又はローパスフィルタを、その画像の内容をサーバに明かさずに行う必要がある用途において有用であり得る。このプロセスを拡張して、後述のようにサーバの安全性も保護することができる。
【００８４】
ブラインドな畳み込み
図４Ｂに示すように、クライアントは、物体を検出すべき入力画像Ｉ４０１、例えば連結成分を有する画像３０９を有する。サーバは畳み込みカーネルｙを有する。この畳み込みカーネルｙを入力画像に適用して、物体に関連する画素がマーキングされた畳み込み画像Ｉ’を生成する。
【００８５】
より詳細には、クライアントは、ｍ枚のランダム画像Ｈ１，．．．，Ｈｍ４１１及び係数ベクトルａ＝［ａ１，．．．，ａｍ］４１２を生成し４１０、入力画像Ｉ４０１がＩ＝∪ｍｉ＝１ Ｈｊとなるようにする。
【００８６】
ランダム画像Ｈｉは、元画像Ｉを含む部分空間を形成する。例えば、ｍ＝１０である場合、元画像Ｉとは異なる９枚の画像を取得する。例えば、これらの９枚の画像はランダムな自然シーン又は街頭シーンである。９枚の画像及び元画像は、特に画像Ｉを含む部分空間を形成する。各画像Ｈｉは、これらの画像の一次結合となるように設定される。こうすることで、各画像Ｈｉは、全てのＨｉ画像の一次結合として表されているにもかかわらず無意味な画像に見える。
【００８７】
クライアントはランダム画像４１１をサーバに送る。
【００８８】
サーバは、ｍ枚の畳み込みランダム画像Ｈ’４２１を、｛Ｈ１’＝π１（Ｈ１＊ｙ｝ｉｍ１となるように求め４２０、ここで、＊は畳み込み演算子であり、π１は第１のランダム画素置換である。サーバは、ｍ枚の畳み込み画像｛Ｈｉ’｝ｉｍ１４２１をクライアントに送る。ここで、演算子＊は画像Ｈｉ内の全ての窓を畳み込みカーネルｙと畳み込む。これはＨ’＝Ｈ＊ｙとして表すことができ、ここで、ｙは例えばガウシアンカーネルであり、＊は畳み込み演算子である。
【００８９】
クライアントは、置換画像Ｉ’４０２を、Ｉ’＝π２（Σｍｉ＝１αｉＨ’ｉ）となるように求め４３０、ここでπ２は第２のランダム画素置換である。クライアントは置換画像Ｉ’４０２をサーバに送る。
【００９０】
サーバは、テスト画像Ｉバー４０３を、Ｉバー＝αｆ（Ｉ’）となるように求める４４０。
【００９１】
サーバは、テスト画像中に画素ｑが存在しＩバー（ｑ）＞０である場合に「真」（＋１）４４１をクライアントに返し、そうでない場合に「偽」（−１）４４２を返して、画像が物体を含むか否かを示す。
【００９２】
クライアントは次に、存在する画素ｑをテストして４５０、入力画像中に物体４０９があるかどうかを判定することができる。
【００９３】
正確さ
このプロトコルは、畳み込み画像の和が画像の和の畳み込みに等しいため、正確である。２つのランダム置換π１及びπ２により、いずれの参加者も入力から出力へのマッピングを有しないことが保証される。したがって、いずれの参加者も、他方の参加者の情報を解読するための制約セットを形成することができない。
【００９４】
しかし、クライアントは優位である。入力画像Ｉ４０１が１つの白い画素以外すべて黒である場合、クライアントは画像Ｈ１’４２１を分析して畳み込みカーネルｙの値を知ることができる。この問題は、以下のプロトコルにより修正することができる。
【００９５】
ブラインドでロケーションフリーな物体検出
このプロセスは、画像中に物体が現れるか否かを検出するが、その物体のロケーションは明かさない。このプロセスを拡張して、物体のロケーションも検出することができる。
【００９６】
図４Ｃに示すように、クライアントは入力画像Ｉ５０１を有し、サーバは、αｆ（ｘＴｙ）の形態の弱分類器を有する。サーバは、入力画像中の物体を検出するが、その物体のロケーションは検出しない。サーバは画像Ｉについて何も知ることがない。
【００９７】
クライアントは、ｍ枚のランダム画像Ｈ１，．．．，Ｈｍ５１１及び係数ベクトルａ＝［ａ１，．．．，ａｍ］５１２を、Ｉ＝Σｍｉ＝１αｉＨｊとなるように生成する５１０。
【００９８】
サーバは、ｐ個のランダムベクトルｇ１，．．．，ｇｐ５１６及び第２の係数ベクトルｂ＝［ｂ１，．．．，ｂｐ］５１７を、ｙ＝Σｐｊ＝１ｂｊｇｊとなるように生成する５１５。
【００９９】
クライアントはランダム画像５１１をサーバに送る。
【０１００】
サーバは、ｍｐ枚の畳み込み画像Ｈ’ｉｊ５２１を、｛｛Ｈ’ｉｊ＝π１（Ｈ１＊ｇｊ）｝ｊｐ１｝ｉｍ１となるように求め５２０、ここで、＊は畳み込み演算子であり、π１は第１のランダム画素置換である。畳み込み画像｛｛Ｈ’ｉｊ｝ｊｐ１｝ｉｍ１５２１はクライアントに送られる。
【０１０１】
クライアントは、置換画像Ｉ’ｊ５０２を、｛Ｉ’ｊ＝π２（Σｍｉ＝１αｉＨ’ｉｊ）｝ｐｊ＝１となるように求め５３０、ここでπ２は第２のランダム画素置換である。クライアントは置換画像５０２をサーバに送る。
【０１０２】
クライアントは、中間画像Ｉ”＝Σｐｊ＝１ｂｊＩ’ｊ及びテスト画像Ｉバー５０３を、Ｉバー＝αｆ（Ｉ”）となるように求める５４０。
【０１０３】
サーバは、テスト画像中に画素ｑが存在し、Ｉバー（ｑ）＞０である場合に「真」（＋１）５４１をクライアントに返し、そうでない場合に「偽」（−１）５４２を返す。
【０１０４】
クライアントは次に、存在する画素ｑをテストして５５０、入力画像中に物体５０９があるかどうかを判定することができる。
【０１０５】
正確さ
このプロトコルは、画像の和の畳み込みが畳み込み画像の和に等しいため、正確である。形式的には、Ｉ＊ｙ＝Ｉ”であることを示すことができる。π１及びπ２が恒等置換である場合、以下の導出式が成り立つ。
【０１０６】
【数８】
【０１０７】
なお、π１及びπ２がランダム置換であっても、上記の導出には影響しない。したがって、このプロトコルは正確である。
【０１０８】
安全性
このプロトコルは安全であり、この安全性は、画像及び分類器がそれぞれ定義される部分空間の階数を定義するｍ及びｐによって支配される。このプロセスは安全であることを証明することができる。
【０１０９】
サーバは、クライアントによって送られるｍ枚のランダム画像５１２が入力ランダム５０１。画像４１１の一次結合であることを知っている。ｍのサイズが大きくなるほど、クライアントの安全性が増す。
【０１１０】
ステップ５３０において、クライアントはｐ枚の画像５０２をクライアントに送る。クライアントが第２の置換π２を用いない場合、サーバは画像Ｉ’ｊ及びＨ’ｉｊを求めることができ、未知数は係数ａｉのみとなり、これは最小二乗法で回復することができる。しかし、第２の置換π２はサーバに、任意の所与のｊについて、ランダムＨｉｊ５１１画像及び置換画像Ｉ’ｊ中の画素からの正確なマッピングを選択することを強いる。これは、
【０１１１】
【数９】
【０１１２】
個の選択肢の中から１つを選択することに等しく、ここでｎは画像中の画素数である。例えば、ｎ＝３２０＊２４０＝７６８００であり、ｍ＝２０である場合、可能な選択は
【０１１３】
【数１０】
【０１１４】
通りとなる。
【０１１５】
ステップ５２０において、クライアントはｍｐ枚の畳み込み画像５２１をクライアントに送る。クライアントが画像Ｈ１を、白い画素を１つだけ有する黒い画像として設定する場合、クライアントは全てのｊについてｇｉの値を回復することができる。しかし、クライアントは係数ｂｊを知らないため、分類器ｙを回復することができない。
【０１１６】
ステップ５４０において、クライアントは真又は偽［＋１，−１］のみをクライアントに返し、画像中に物体が存在するか否かを示す。したがって、クライアントはこのステップにおいて係数ｂｊを知り得ない。
【０１１７】
複雑度及び効率
このプロトコルは、それぞれ入力画像Ｉ５０１及び分類器ｙを表すために使用されるランダム画像の数及びベクトル数であるｍｐに従って線形である。
【０１１８】
このプロセスを拡張して、二分探索法を用いてこのプロセスを部分画像に繰り返し適用することによって、入力画像中の物体の位置を特定することができる。画像中に物体が検出される場合、画像を２分割又は４分割し、このプロセスを各部分画像に適用して物体の正確なロケーションを絞り込む。分割は必要に応じて繰り返すことができる。こうして、クライアントは、複数の偽物の画像をサーバに送ることができる。その場合、サーバは、検出された物体が本物なのか偽物なのかを判定することができない。
【０１１９】
［発明の効果］
本発明はゼロ知識技法を画像処理方法に応用する。問題領域の知識を利用することによって、本発明は、そうした処理を大幅に加速し、画像及びビデオに関わる安全なマルチパーティ計算の問題に対して実用的な解決策をもたらすことができる。
【０１２０】
ブラインドなコンピュータビジョン、特にブラインドな背景モデリング、ブラインドな連結成分ラベリング、及びブラインドな物体検出についていくつかのプロセスを説明する。様々なプロセスを組み合わせることにより、実用的なブラインドなコンピュータビジョンシステムが得られる可能性がある。
【０１２１】
本発明を好ましい実施の形態の例として説明してきたが、本発明の精神及び範囲内で様々な他の適応形態及び修正形態を実施してもよいことが理解される。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲に入るそのような変形形態及び修正形態をすべて網羅することである。
【図面の簡単な説明】
【０１２２】
【図１Ａ】本発明による、画像を安全に処理するシステムのブロック図である。
【図１Ｂ】本発明による、画像を安全に処理する方法のフロー図である。
【図２Ａ】本発明による処理すべき画像である。
【図２Ｂ】本発明による、動き画像を生成するための安全な背景モデリングのフロー図である。
【図２Ｃ】本発明による動き画像である。
【図３Ａ】重なり合うタイルに分割された動き画像である。
【図３Ｂ】本発明による、タイルを用いた安全な成分ラベリングのフロー図である。
【図３Ｃ】本発明による、動き画像の３×３タイルである。
【図３Ｄ】本発明による、連結成分を有する動き画像である。
【図３Ｅ】本発明による、フル画像を用いた安全な成分ラベリングのフロー図である。
【図４Ａ】本発明による、スキャン窓を用いて安全に検出すべきオブジェクトを含む動き画像である。
【図４Ｂ】本発明による第１の物体検出方法のフロー図である。
【図４Ｃ】本発明による第２の物体検出方法のフロー図である。
【技術分野】
【０００１】
本発明は、包括的にはコンピュータビジョンに関し、特に画像及びビデオの安全なマルチパーティ処理に関する。
【背景技術】
【０００２】
全世界的な通信ネットワークが利用可能になったことで、一部のデータ処理業務をいくつかの理由で外部の企業に「外注」することが一般的に行われるようになった。例えば、処理をより低コストで行うことができるか、又は外部の企業がより良い計算資源又はより良い技術を有する。
【０００３】
データ処理を外注する際の問題の１つとして、他の企業による機密情報の不正使用がある。例えば、外部の企業に、監視ビデオ、又は機密スキャン文書の中身を知られることなく、それらのビデオ又は文書を多数処理してもらうことが望ましい。別の用途として、限られた電力資源及び計算資源を有する携帯電話によって取得した画像の複雑な分析を行うことが望ましい。
【０００４】
このような用途に対して、従来の暗号技術はデータを、輸送中にのみ保護し、別の企業による処理中には保護しない。ゼロ知識技法に頼ることはできる。しかし、ゼロ知識技法は計算集約的であることが知られている。このような技法を画像及びビデオストリーム等の大きなデータセットに適用することは、複雑度の低いデバイスにとって非実用的である。例えば、１枚の高解像度画像は数百万バイトを含み、ビデオの場合、画像は、３０フレーム毎秒以上のレートで生じ得る。
【０００５】
ゼロ知識又は安全なマルチパーティ計算は、Yao著「How to generate and exchange secrets」（Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, pp. 162-167, 1986）に初めて、特定の問題について記載された。後に、ゼロ知識技法は他の問題に拡張された（Goldreich他著「How to play any mental game - a completeness theorem for protocols with honest majority」（19th ACM Symposium on the Theory of Computing, pp 218-229, 1987））。しかし、それらの理論的構成概念は、実用に供するには依然として要求の高すぎるものであった。
【０００６】
それ以後、多くの安全化（secured）方法が記載されてきた（Chang他著「Oblivious Polynomial Evaluation and Oblivious Neural Learning」（Advances in Cryptology, Asiacrypt '01, Lecture Notes in Computer Science Vol. 2248, pages 369-384, 2001）、Clifton他著「Tools for Privacy Preserving Distributed Data Mining」（SIGKDD Explorations, 4(2):28-34, 2002）、Koller他著「Protected Interactive 3D Graphics Via Remote Rendering」（SIGGRAPH 2004）、Lindell他著「Privacy preserving data mining」（Advances in Cryptology - Crypto 2000, LNCS 1880, 2000）、Naor他著「Oblivious Polynomial Evaluation」（Proc. of the 31st Symp. on Theory of Computer Science (STOC), pp. 245-254, May 1, 999）、及びDu他著「Privacy-preserving cooperative scientific computations」（4th IEEE Computer Security Foundations Workshop, pp. 273-282, June 11, 2001））。問題の完全な論考（treatment）は、Goldreichの参考書「Foundations of Cryptography」（Cambridge University Press, 1998）に見出すことができる。
【０００７】
安全なマルチパーティ計算は多くの場合、正確さ、安全性、及びオーバーヘッドについて分析される。正確さは、安全なプロセスが理想解にどこまで近づくかを測定する。安全性は、マルチパーティのやりとりから得ることのできる情報量を測定する。オーバーヘッドは複雑度及び効率の測度である。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
クライアントコンピュータによって取得された画像及びビデオの、サーバコンピュータを用いた安全な処理を提供することが望ましい。さらに、クライアントコンピュータにおいて必要とされる計算資源を最小限に抑えることが望ましい。
【課題を解決するための手段】
【０００９】
［発明の開示］
［発明の概要］
本発明は、クライアントコンピュータによって生成された画像及びビデオの中身をサーバコンピュータのプロセスに明かすことなく、それらの画像を処理するシステム及び方法を提供する。さらに、サーバコンピュータの処理技法をクライアントコンピュータに対して安全に保つことが望ましい。
【００１０】
本発明は、ビジョン問題の解決にゼロ知識技法を適用する。すなわち、コンピュータビジョン処理は、処理される画像に対して「ブラインド（盲目的）」である。したがって、画像に対して操作を行う方法は、画像の内容又は処理結果を何も知ることがない。本方法は、監視ビデオの安全な処理、例えば背景モデリング、物体検出、及び顔認識を行うために用いることができる。
【００１１】
特に、本発明は、入力画像シーケンスを安全に処理する方法を提供する。入力画像シーケンスがクライアントにおいて取得される。各入力画像中の画素は置換πに従ってランダムに置換されて、各入力画像について置換画像が生成される。各置換画像はサーバに転送され、サーバは置換画像から背景画像を保持する。サーバにおいて、各置換画像は背景画像と結合されて、各置換画像について対応する置換された動き画像が生成される。各置換された動き画像はクライアントに転送され、各置換された動き画像中の画素は逆置換π−１に従って並べ換えられて、各入力画像について対応する動き画像が回復される。
【発明を実施するための最良の形態】
【００１２】
システムの概要
図１Ａに示すように、画像を安全に処理するシステム１００が例示的なセキュリティ用途に関して説明される。システム１００において、クライアントコンピュータ（クライアント）１０がネットワーク３０を介してサーバコンピュータ（サーバ）２０に接続される。利点として、クライアント１０は、限られた処理資源及び電力資源を有することができる（例えば、ラップトップ、低コストセンサ、又は携帯電話）。
【００１３】
クライアントは、画像シーケンス２０１、すなわち「秘密」ビデオを取得する。画像２０１は、プロセス２００、３００、及び４００を用いて処理される。これらのプロセスは共同して、実線によって示されるようにクライアントコンピュータ上で部分的に、また破線によって示されるようにサーバコンピュータ上で部分的に操作を行う。これはマルチパーティ処理として知られる。これらのプロセスは、画像２０１の内容がサーバに明かされず、且つサーバプロセス及びデータ２１がクライアントに明かされないように動作する。
【００１４】
クライアントは、マルチパーティ処理の結果を用いて、画像２０１中の「秘密」物体を検出することができる。同時に、クライアントは、サーバによって部分的に行われるプロセス２００、３００、及び４００の「秘密」部分、並びにサーバによって保持される秘密データ構造２１を知ることを防止される。
【００１５】
この処理は、基礎にある画像の内容が、サーバにおいて画像に対して操作を行うプロセスに明かされないため安全である。したがって、入力画像２０１は、単純なクライアントコンピュータによって取得されることができ、その一方で、安全な処理が、より高度なサーバコンピュータによって行われる。処理結果はサーバには無意味である。クライアントのみが「秘密」処理結果を回復することができる。したがって、本発明は、「ブラインドな」コンピュータビジョン処理を提供する。
【００１６】
図１Ｂに示すように、方法１０１は、３つの基本プロセス２００、３００、及び４００を含む。第１に、ビデオ２０１、すなわち画像の時間シーケンスを処理し、動き画像２０９を求める２００。動き画像はビデオ中の移動成分のみを含む。移動成分は「前景」としても知られ、残りの成分は静止「背景」モデルと呼ばれる。第２に、動き画像をさらに処理して、連結した前景成分３０９をラベリングする３００ことができる。第３に、連結成分を処理して、物体４０９を検出する４００ことができる。プロセス２００、３００、及び４００への入力画像は異なり得ることに留意すべきである。すなわち、各プロセスは、いかなる以前の処理又は後続の処理にも関係なく行うことができる。例えば、物体検出は、任意のタイプの入力画像に対して行うことができる。
【００１７】
この方法は全体として、小さいデータセットほど処理が複雑度を増すデータ削減又は「トリアージ」と考えることもできる。ビデオ中の全画素の全強度範囲に対して操作を行う最初のステップ２００は非常に単純且つ高速である。中間のステップ３００は、少しより複雑ではあるものの、大抵は、遥かに小さなデータセットである２進値すなわち０と１を格納する小さなタイルセットに対して操作を行う。最後のステップは、より複雑な操作を用いるが、元の画像内容のごく小部分のみを扱えばよい。したがって、本発明は、非常に大きなデータセットに対して非常に単純な技法を適用して、処理する必要があるデータ量を劇的に低減し、その一方でトリアージ中に、より複雑な処置を非常に小さなデータセットのために残しておく。
【００１８】
ブラインドな動き画像
図２Ａは、「秘密」ビデオの例示的な入力画像２０１を示す。この例示的なビデオは、一群の歩行者９９のいる街頭シーンのものである。
【００１９】
図２Ｂは、動き画像２０９を求める２００ステップを示す。ビデオ２０１の入力画像を、クライアントコンピュータ１０に接続されたカメラによって取得することができる。１つの利点として、クライアントコンピュータは、限られた処理資源を有することができる、例えば、クライアントは携帯電話に組み込まれる。
【００２０】
シーケンス中の各入力画像Ｉ中の画素をクライアントコンピュータによって、置換πを用いて擬似ランダムに空間的に置換して２１０、置換画像Ｉ’２０２を、Ｉ’＝πＩとなるように生成する。擬似ランダムとは、どの以前の値からも次の値を求めることができないが、乱数発生器は、おそらくはそのシード値を知っているため、必要であれば常にランダムな値の特定のシーケンスを再構成することができることを意味する。明らかに、置換画像中の画素の空間分布はランダムであり、元の入力画像は逆置換π−１を用いて、Ｉ＝π−１Ｉ’となるように並べ換えることによって回復することができる。
【００２１】
任意で、置換画像２０２をより大きなランダム画像２０３に埋め込んで、組み込み画像２０４を生成することができる。より大きなランダム画像２０３中の画素もまた、置換画像２０２の強度ヒストグラムがより大きなランダム画像の強度ヒストグラムと異なるように、擬似ランダムに生成する。さらに、ランダム画像中の画素の一部の強度値をランダムに変化させて、組み込み画像２０４中に「偽物の」動きを生成することができる。組み込まれる置換画像２０２のロケーション、サイズ及び向きもまた、入力画像ごとにランダムに変化させることができる。
【００２２】
組み込み画像２０４を、背景／前景モデリングアプリケーション２３０にアクセスできるサーバコンピュータ２０に転送する２２１。これは、任意の従来のモデリングアプリケーション、又はサーバしか知らない独自のプロセスとすることができる。１つの利点として、サーバは、クライアントコンピュータよりも大幅に多い処理資源を有する。転送は、ネットワーク３０、又は携帯用記憶媒体等の他の手段を介して行うことができる。
【００２３】
サーバ２０におけるアプリケーション２３０は、現在の背景画像Ｂ２０６を保持する。この背景画像は、各入力画像又は以前に処理された置換画像のセットから更新することができる。例えば、背景画像は、最後のＮ枚の入力画像、例えばＮ＝１０の平均を用いる。移動平均を用いることによって、シーンにおける急激な変化の影響又は他の短期的な影響を最小限に抑える。次に、結合すること、例えば現在の背景画像２０６から組み込み画像２０４を減算することによって、置換された動き画像Ｍ’２０５を生成する。特定の入力画素と背景画素の間の差が或る所定の閾値Θよりも大きい場合、その入力画素を動き画素とみなし、相応にラベリングする。したがって、置換された動き画像２０５は次のように表される。
【００２４】
【数１】
【００２５】
置換された動き画像Ｍ’２０５をクライアントコンピュータに転送する２３１。クライアントコンピュータは、必要に応じて組み込み部分を抽出する。次に、Ｍ＝π１（Ｍ’）に従って空間的な置換を元に戻すことによって抽出部分の画素を元の順序に並べ換え、移動成分２９９に関連する成分のみを有する動き画像Ｍ２０９を得る（図２Ｃを参照）。
【００２６】
背景及び動き画像は、格納されるデータ量を大幅に低減するために２値画像又は「マスク」画像とすることができることに留意すべきである。すなわち、動き画像中の或る画素は、移動していると見なされれば「１」であり、そうでなければ「０」である。「動き」画素の一部は雑音により誤っている可能性があることにも留意されたい。これらのアーティファクトを後述のように除去する。
【００２７】
正確さ
このプロセスは、画素ベースの背景減算が画素の空間的な順序に依存しないため、正確である。したがって、画素の順序を空間的に置換してもプロセスに影響はない。さらに、偽物の動き画素を組み込み画像に加えても、置換画像２０２中の偽物の画素と関心画素の間には相互作用がないため、プロセスに影響はない。
【００２８】
安全性
このプロセスは部分的に安全である。サーバは、入力画像２０１の内容を何も知ることができない。可能な置換数は多すぎて求められない。例えば、入力画像２０１がｎ個の画素を有し、組み込み画像がｃ＝２倍の大きさである場合、可能な置換数は
【００２９】
【数２】
【００３０】
となり、ｎは高解像度カメラの場合に１００万以上であり得る。
【００３１】
アプリケーション２３０を「知る」には、クライアントは、各画素の各入力及び出力を観察する必要がある。すなわち、クライアントは、クライアントとサーバの間のデータフローを分析する。しかしこれは、データセットのサイズにより非実用的になり得る。このプロセスは、サーバにおいて「秘密」データを一切必要としない。
【００３２】
複雑度及び効率
クライアントの複雑度及び通信オーバーヘッドは、入力画像のサイズにおいて線形である。所定のランダム順に従った画素の置換は問題にならない。並べ換えも同様に単純である。アプリケーション２３０の複雑度は置換に影響を受けない。
【００３３】
上記のプロセスは、本発明によるブラインドなコンピュータビジョンの特性のいくつかを示す。このプロセスは、従来のビジョン方法を画像に適用し、その一方で、画像の内容をサーバから隠す。サーバは、画像の正確な内容を判断することができないが、置換画像から何らかを知ることができる。例えば、画像のヒストグラムにより、画像が日中又は夜間のどちらに取得された可能性が高いかを判定することができる。サーバはまた、動き画素の数を計数して、画像中にどれだけ動きが存在するかを判断することができる。
【００３４】
この問題は、クライアントが置換画像を大きなランダム画像に組み込めば簡単に克服することができる。こうすることにより、サーバは、画像ヒストグラムから何も推測することができない。また、クライアントがランダム画素の一部をオンにして偽物の動き画素を生成する場合、サーバは、検出された動き画素が本物であるか偽物であるかさえ知ることができない。
【００３５】
サーバは、画素間の相関関係を経時的に観察して、それらの近接性を知るか、又は本物の動き画素と偽物の動き画素を区別することができることに留意すべきである。しかしクライアントは、偽物の動き画素を、本物の動き画素と同じ分布を有するように生成することができる。
【００３６】
このプロトコルの単純さは主に、各画素を個別に扱うことができ、よって空間的な順序は重要でないという事実によるものである。
【００３７】
次に、画像中の領域に対して操作を行う連結成分ラベリング等の安全なビジョンプロセスを説明する。
【００３８】
ブラインドな成分ラベリング
物体検出、物体追跡、又は物体及びパターン認識といった実際の用途において、動き画像２０９は、雑音及び誤った動き画素２９９を除去し（図２Ｃを参照）、単一の移動物体に関連する可能性が高い隣接画素を「連結」するためにさらなる処理を必要とする場合がある。入力画像は、任意の動き画像とすることができることに留意すべきである。
【００３９】
しかし、さらなる処理は、画素の空間的な順序に依存し得る。実際には、雑音が誤った動き画素を生じる恐れがあるため、動き画像２０９をきれいにする（clean）必要がある。残念ながら、置換は画像中の画素の空間的配置を破壊してしまい、連結成分が正しく機能しなくなってしまうため、入力画像中の画素を単純に置換することはもうできない。
【００４０】
フル画像に対して操作を行う拡張プロセスをまず説明し、次にタイルに対して操作を行う複雑度の低いプロセスを説明する。拡張プロセスは、入力画像をランダム画像の和集合に分割することによって機能する。ランダム画像は、いくつかの偽物のランダム画像とともにサーバに送られる。この場合、数十枚又は数百枚のランダム画像を用いて安全性を保証することができる。複雑度は、入力画像をタイルに分割することによって劇的に低減することができ、各タイルは個別の「画像」として扱われる。タイルがランダム順で送られる場合、サーバは、入力画像を復元するために二重の問題に直面する。
【００４１】
フル画像プロトコル
フル画像プロトコルは、入力画像をランダム画像の和集合として表現し、これらのランダム画像をランダム２値画像の大きな集合とともにサーバに送る。
【００４２】
サーバは、各画像に対して個別に連結成分ラベリングを行い、その結果をクライアントに送る。次に、クライアントは、それらの結果を結合して、ラベリングされた連結成分、すなわち可能な物体の最終結果を得る。
【００４３】
２値入力画像はＩ、例えば画像２０９であり、連結成分を有するラベリングされた画像３０９はＩ’、すなわち、連結成分ラベリングを行った後の画像Ｉである。複数のラベリングされた画像Ｈ１，．．．，Ｈｍがあり、各画像中の成分のラベルが例えば１から開始する場合、ラベリングされた画像のセットはＨ１バー，．．．，Ｈｍバーによって示され、各連結成分はｍ枚の画像すべてについて一意のラベルを有する。最後に、Ｉ（ｑ）は画像Ｉの画素位置ｑにおける値である。
【００４４】
フル画像を用いたブラインドな連結成分ラベリング
図３Ｅに示すように、サーバは、入力画像Ｉ２０９を有するとともに、連結成分ラベリングプロセス３００を有する。このプロセスの出力は、ラベリングされた連結成分画像Ｉバーである。サーバは、入力画像Ｉについて何ら知ることはない。
【００４５】
初めに、クライアントは、ｍ枚のランダム画像Ｈ１，．．．，Ｈｍを次のように生成する３７０。
【００４６】
【数３】
【００４７】
クライアントは、ｒ＞ｍ枚のランダム画像Ｕ１，．．．，Ｕｒ３７１をサーバに送り、秘密のｊ１，．．．，ｊｍの画像についてＵｊｉ＝Ｈｉであり、さらなる画像は偽物の画像である。
【００４８】
サーバは、画像Ｕごとに連結成分ラベリングを求め３７５、ラベリングした画像Ｕ１’，．．．，Ｕｒ’３７６をクライアントに送る。
【００４９】
クライアントは、画像Ｈ１’，．．．，Ｈｍ’を全てのラベリングされた画像にわたって固有のラベルでグローバルに再ラベリングし３８０、これらの画像をＨ’１バー，．．．，Ｈ’ｍバーによって示す。画素ｑごとに、Ｉ（ｑ）＝１となるように、Ｈ’１バー（ｑ），．．．，Ｈ’ｍバー（ｑ）が各画像の異なるラベルを表すものとする。次にクライアントは、グローバルラベリングされた画像から同値リスト｛Ｈ’ｉバー（Ｎｂｒ（ｑ））｝ｉｍ１を生成し、ここでＮｂｒ（ｑ）は各画素ｑの４つ又は８つの近傍画素のリストである。画素は、それらが動き画素であり、且つ互いに直に隣接する場合にのみ連結される。
【００５０】
サーバは、同値ラベルリスト３８１をスキャンし、同値類を判断し３８５、全てのラベルから同値類の代表値へのマッピング３８６を返す。
【００５１】
クライアントは、サーバから返されたマッピングに応じて各画像Ｈ１’バーを再ラベリングし３９０、全ての画素ｑについてＩバー（ｑ）＝ｍａｘ（｛Ｈｉ’バー（ｑ）｝ｉｍ１という最終結果を求め、それにより連結成分の最終画像３０９を形成する。
【００５２】
正確さ
このプロトコルは、各画像Ｈｉがサーバプロセスによって正確にラベリングされるため、正確である。さらに、Ｉ＝∪ｍｉ＝１ Ｈｉであるため、各画像Ｈｉは入力画像Ｉの動き又は「オン」画素の一部のみを含み、よって、元画像Ｉでは連結していない２つの領域を連結してしまうかもしれない偽の「オン」画素は付加されないことになる。
【００５３】
元画像Ｉ中の各連結成分は、複数のランダム画像Ｈｉにわたるいくつかの成分に分けることができるため、同一成分が複数のラベルを有し得る。しかし、全ての同値類について１つの代表値を計算する最終的なクライアントによる再ラベリングステップが、これに対処する。再ラベリングはまた、全てのランダム画像における全ての動き画素に対してラベルが１つしかないか、又は全くないことを保証する。
【００５４】
安全性
このプロトコルは、クライアントがサーバに複数の２値画像Ｕを送り、そのうちサブセットＨのみが入力画像を形成するため、安全である。適切なｒ及びｍについて、可能性の数
【００５５】
【数４】
【００５６】
は、求めるにはとても大きすぎる可能性がある。第２段階において、クライアントは、同値リストのリスト３８１を送る。クライアントは成分を既に再ラベリングしているため、サーバは新たなラベルを元画像と関連付けることができず、クライアントは安全化される。サーバは、安全化する必要があるいかなるプライベートデータも格納する必要がない。
【００５７】
複雑度及び効率
複雑度は、ｒに従って線形である。ランダム画像ごとに、サーバは連結成分ラベリングを行う。クライアントは、和集合をＩとするｍ枚のランダム画像と、付加的なｒ−ｍ枚の偽物のランダム画像とを生成する。
【００５８】
上記プロセスは、
【００５９】
【数５】
【００６０】
が大きければ安全である。例えば、ｒ＝１２８であり、ｍ＝６４である場合、
【００６１】
【数６】
【００６２】
の可能性を確認しなければならない。
【００６３】
タイルを用いたブラインドな連結成分ラベリング
この場合、図３Ａ〜図３Ｃに示すように、クライアントは各動き画像２０９を、重なり合う本物の画素タイルのセットＴｇ３１１に分割する３１０。明確にするために、タイルは一定の縮尺で示されていない。例えば、タイルは３×３画素であり、上下左右で１画素ずつ重なり合う。他のタイルサイズ及び重なりを用いることもできることに留意すべきである。しかし、タイルを大きくするほど、内容を判断し易くなる。さらに、クライアントは任意で、偽物の画素タイルＴｆ３２１を生成する３２０ことができる。
【００６４】
本物のタイル３１１及び偽物のタイル３２１は、擬似ランダム順でサーバに転送される。サーバは、各タイル中の、他の動き画素に「連結」した動き画素をローカルラベリングする３３０。或る画素は、少なくとも１つの他の動き画素に隣接している場合に連結していると言える。例えば、特定のタイル内で連結している第１の画素群の各画素にはラベルＧ１が付され、同一タイル内の第２の連結画素群の各画素にはラベルＧ２が付され、以下同様にラベリングされる。タイルごとに、ラベルはＧ１から再び開始する。すなわち、別のタイル内の第１の群及び第２の群もＧ１及びＧ２とラベリングされる。したがって、ラベル３３１は各タイルに対してローカルに一意である。
【００６５】
図３Ｃに３×３タイルについて示すように、動き画素（点描模様）３０１は、最高８つの隣接する動き画素を有し得る。なお、サーバは、タイルの一部が偽物であることも、タイルがランダムに空間的に順序付けされていることも知らない。単一の未連結画素及び非動き画素はラベリングされない。サーバは、動き画素の連結性を求める従来の又は独自のプロセスを用いることができる。
【００６６】
ラベリングされたタイル３３１はクライアントに転送される。クライアントは、偽物のタイルを廃棄し、連結画素がローカルラベリングされた動き画像を再構成する。クライアントは、「境界」画素をグローバルに一意のラベルにより再ラベリングする。これらの一意のラベルは擬似ランダムに生成することもできる。境界画素は、タイルの４つ又は８つの外側画素である。１画素分の重なりにより、境界画素は、サーバによって決定されるグローバルラベルが同じであるか又は異なる２つの隣接タイルに現れる可能性がある。
【００６７】
実際、図３Ａに示すように、タイル内の角の画素３０１は、最大４つの異なるラベルをサーバによって割り当てられる可能性がある。クライアントは、サーバによって２つの異なるラベルを付された隣接タイルの２つの境界画素が実際には同一画素であるかを判定することができ、よって一意のグローバルラベルと関連付けることができる。再ラベリング３４０により、一意のローカルラベル対のリスト３４１［Ｌ１（ｂｉ），Ｌ２（ｂｉ）］，．．．，［Ｌｋ−１（ｂｉ），Ｌｋ（ｂｉ）］が生成される。
【００６８】
クライアントは、リスト３４１をサーバに、さらに別の擬似ランダム順で転送する。サーバは、従来の又は独自の分類技法を用いて、それらの対を同値類３５１に分類する３５０。サーバは、独自の一意のラベルを各同値類３５１に割り当てる。
【００６９】
ラベリングされた同値類３５１はクライアントに転送される。クライアントは、これらのラベルを用いて、画素を連結画素の各セットについて一意のグローバルラベルにより再ラベリングし３６０、連結成分３０９を形成する（図３Ｄを参照）。
【００７０】
正確さ
このプロセスは、各タイルがサーバによって正確にローカルラベリングされるため、正確である。複数のタイルにわたって分散している連結画素は、タイル間に重なりがあるため、クライアントによって正確に融合される。同値類の判定３５０により、各連結画素群に一意のラベルが割り当てられることが保証される。
【００７１】
安全性
このプロセスは、ｐ個の本物のタイル及びｍ個の偽物のタイルについて、異なる可能性の数が
【００７２】
【数７】
【００７３】
と非常に大きいため安全である。３２０×２４０の画像の値ｍは約２０，０００タイルである。１００個の偽物のタイルを加える場合、置換される可能性の数は約Ｏ（２１４００）である。サーバが本物のタイルを検出できたとしても、多くの異なる画像のタイルヒストグラムが同じように見えるため、タイルの正確な空間的順序は分からないままである。タイル３１１、３２１のランダムな順序付けに対する対３４１のランダムな順序付けもまた、サーバが内容を分析することを極めて困難にする。
【００７４】
複雑度及び効率
ここでもまた、クライアントにおけるプロセスの複雑度は画像のサイズに対して線形である。画像をタイルに変換することは簡単である。
【００７５】
ブラインドな物体検出
最後のプロセス４００は物体検出である。物体検出は、図４Ａに示すように、スライド窓４０５を用いてラスタスキャン順に連結成分の画像３０９をスキャンする。スライド窓の各ロケーションにおいて、スライド窓の内容が物体を含むか否かの判定が行われる。
【００７６】
ニューラルネットワーク、サポートベクトルマシン、又はアダブースト等の多くの分類器を、加法モデル、又はカーネル関数の和、例えばラジアル基底関数、多項式関数、又はシグモイド関数として表現することができる。これらの関数は、前処理訓練段階中に求められる窓のドット積及びいくつかの原型パターンに対して操作を行う。
【００７７】
ゼロ知識法と機械学習技法の間には、ゼロ知識法が隠そうとするものであり、その一方で機械学習技法が推測しようとするものであるという点で自然な張力がある。本発明による方法では、クライアントは、サーバを用いて訓練画像をクライアントのためにラベリングし、後にそれらの訓練画像を用いて自身の分類器を訓練できるようにする。
【００７８】
以下では、クライアントは入力画像Ｉ４０１を有し、サーバは、畳み込みカーネルαｆ（ｘＴｙ）の形態の弱分類器（weak classifier）を有し、ここで、ｘは窓の内容であり、ｙは弱分類器であり、ｆは非線形関数であり、αは係数である。したがって、畳み込み演算を画像Ｉに適用し、次にその結果を分類器に渡す方法を説明すれば十分である。
【００７９】
弱分類は、画像を何らかのフィルタと畳み込み、次にその結果を何らかの非線形関数に通した結果に基づく。例えば、本明細書中に参照により援用されるP. Viola及びM. Jones著「Rapid Object Detection using a Boosted Cascade of Simple Features」（IEEE Conference on Computer Vision and Pattern Recognition, Hawaii, 2001）に記載されるように矩形フィルタを用いる。画像位置ごとに、スライド窓と矩形フィルタとのドット積を求める。畳み込み演算の結果を、アダブースト、又はサポートベクトルマシンにおけるカーネル関数、又はニューラルネットワークにおけるシグモイド関数等の非線形関数に通す。
【００８０】
要約すると、弱分類器は３つの構成要素、すなわち、ガウス関数、シグモイド関数等であり得る非線形関数ｆ（）、重み（アルファ）及び畳み込みカーネルｙを有する。画像をまず畳み込みカーネルｙと畳み込み、その結果を畳み込み画像として格納する。畳み込み画像中の各画素は、カーネルｙを、その画素を中心とする窓と畳み込んだ結果を含む。畳み込み画像中の画素を非線形関数ｆ（）に通し、アルファを乗算する。
【００８１】
ゼロ知識プロトコルは多くの場合、暗号化ベースのプロトコルと、代数ベースのプロトコルとに分類することができる。暗号化ベースのプロトコルでは、参加者（parties）は、公開−私有鍵暗号化等の標準的な技法を用いてデータを暗号化するため、他者（other parties）には情報が利用できない。これには、回避すべき高い計算コスト及び通信コストが伴う。
【００８２】
別法として、計算は速いが一部の情報を明かしてしまうかもしれない代数プロトコルを用いることができる。代数方法は、部分空間において操作を行うことによってベクトルを隠す。例えば、一方の参加者がベクトルｘ∈Ｒ４００を有する場合、プロトコルを行った後で、他方の参加者には、ｘが元の４００次元空間のうち一部の低次元部分空間、例えば１０次元部分空間にあることが分かる。
【００８３】
ブラインドな物体検出プロセス４００の１つの実施の形態では、クライアントの安全性のみが維持される。このプロトコルの変形は、クライアントがサーバを使用して、入力画像Ｉに対して従来の畳み込み、例えばエッジ検出又はローパスフィルタを、その画像の内容をサーバに明かさずに行う必要がある用途において有用であり得る。このプロセスを拡張して、後述のようにサーバの安全性も保護することができる。
【００８４】
ブラインドな畳み込み
図４Ｂに示すように、クライアントは、物体を検出すべき入力画像Ｉ４０１、例えば連結成分を有する画像３０９を有する。サーバは畳み込みカーネルｙを有する。この畳み込みカーネルｙを入力画像に適用して、物体に関連する画素がマーキングされた畳み込み画像Ｉ’を生成する。
【００８５】
より詳細には、クライアントは、ｍ枚のランダム画像Ｈ１，．．．，Ｈｍ４１１及び係数ベクトルａ＝［ａ１，．．．，ａｍ］４１２を生成し４１０、入力画像Ｉ４０１がＩ＝∪ｍｉ＝１ Ｈｊとなるようにする。
【００８６】
ランダム画像Ｈｉは、元画像Ｉを含む部分空間を形成する。例えば、ｍ＝１０である場合、元画像Ｉとは異なる９枚の画像を取得する。例えば、これらの９枚の画像はランダムな自然シーン又は街頭シーンである。９枚の画像及び元画像は、特に画像Ｉを含む部分空間を形成する。各画像Ｈｉは、これらの画像の一次結合となるように設定される。こうすることで、各画像Ｈｉは、全てのＨｉ画像の一次結合として表されているにもかかわらず無意味な画像に見える。
【００８７】
クライアントはランダム画像４１１をサーバに送る。
【００８８】
サーバは、ｍ枚の畳み込みランダム画像Ｈ’４２１を、｛Ｈ１’＝π１（Ｈ１＊ｙ｝ｉｍ１となるように求め４２０、ここで、＊は畳み込み演算子であり、π１は第１のランダム画素置換である。サーバは、ｍ枚の畳み込み画像｛Ｈｉ’｝ｉｍ１４２１をクライアントに送る。ここで、演算子＊は画像Ｈｉ内の全ての窓を畳み込みカーネルｙと畳み込む。これはＨ’＝Ｈ＊ｙとして表すことができ、ここで、ｙは例えばガウシアンカーネルであり、＊は畳み込み演算子である。
【００８９】
クライアントは、置換画像Ｉ’４０２を、Ｉ’＝π２（Σｍｉ＝１αｉＨ’ｉ）となるように求め４３０、ここでπ２は第２のランダム画素置換である。クライアントは置換画像Ｉ’４０２をサーバに送る。
【００９０】
サーバは、テスト画像Ｉバー４０３を、Ｉバー＝αｆ（Ｉ’）となるように求める４４０。
【００９１】
サーバは、テスト画像中に画素ｑが存在しＩバー（ｑ）＞０である場合に「真」（＋１）４４１をクライアントに返し、そうでない場合に「偽」（−１）４４２を返して、画像が物体を含むか否かを示す。
【００９２】
クライアントは次に、存在する画素ｑをテストして４５０、入力画像中に物体４０９があるかどうかを判定することができる。
【００９３】
正確さ
このプロトコルは、畳み込み画像の和が画像の和の畳み込みに等しいため、正確である。２つのランダム置換π１及びπ２により、いずれの参加者も入力から出力へのマッピングを有しないことが保証される。したがって、いずれの参加者も、他方の参加者の情報を解読するための制約セットを形成することができない。
【００９４】
しかし、クライアントは優位である。入力画像Ｉ４０１が１つの白い画素以外すべて黒である場合、クライアントは画像Ｈ１’４２１を分析して畳み込みカーネルｙの値を知ることができる。この問題は、以下のプロトコルにより修正することができる。
【００９５】
ブラインドでロケーションフリーな物体検出
このプロセスは、画像中に物体が現れるか否かを検出するが、その物体のロケーションは明かさない。このプロセスを拡張して、物体のロケーションも検出することができる。
【００９６】
図４Ｃに示すように、クライアントは入力画像Ｉ５０１を有し、サーバは、αｆ（ｘＴｙ）の形態の弱分類器を有する。サーバは、入力画像中の物体を検出するが、その物体のロケーションは検出しない。サーバは画像Ｉについて何も知ることがない。
【００９７】
クライアントは、ｍ枚のランダム画像Ｈ１，．．．，Ｈｍ５１１及び係数ベクトルａ＝［ａ１，．．．，ａｍ］５１２を、Ｉ＝Σｍｉ＝１αｉＨｊとなるように生成する５１０。
【００９８】
サーバは、ｐ個のランダムベクトルｇ１，．．．，ｇｐ５１６及び第２の係数ベクトルｂ＝［ｂ１，．．．，ｂｐ］５１７を、ｙ＝Σｐｊ＝１ｂｊｇｊとなるように生成する５１５。
【００９９】
クライアントはランダム画像５１１をサーバに送る。
【０１００】
サーバは、ｍｐ枚の畳み込み画像Ｈ’ｉｊ５２１を、｛｛Ｈ’ｉｊ＝π１（Ｈ１＊ｇｊ）｝ｊｐ１｝ｉｍ１となるように求め５２０、ここで、＊は畳み込み演算子であり、π１は第１のランダム画素置換である。畳み込み画像｛｛Ｈ’ｉｊ｝ｊｐ１｝ｉｍ１５２１はクライアントに送られる。
【０１０１】
クライアントは、置換画像Ｉ’ｊ５０２を、｛Ｉ’ｊ＝π２（Σｍｉ＝１αｉＨ’ｉｊ）｝ｐｊ＝１となるように求め５３０、ここでπ２は第２のランダム画素置換である。クライアントは置換画像５０２をサーバに送る。
【０１０２】
クライアントは、中間画像Ｉ”＝Σｐｊ＝１ｂｊＩ’ｊ及びテスト画像Ｉバー５０３を、Ｉバー＝αｆ（Ｉ”）となるように求める５４０。
【０１０３】
サーバは、テスト画像中に画素ｑが存在し、Ｉバー（ｑ）＞０である場合に「真」（＋１）５４１をクライアントに返し、そうでない場合に「偽」（−１）５４２を返す。
【０１０４】
クライアントは次に、存在する画素ｑをテストして５５０、入力画像中に物体５０９があるかどうかを判定することができる。
【０１０５】
正確さ
このプロトコルは、画像の和の畳み込みが畳み込み画像の和に等しいため、正確である。形式的には、Ｉ＊ｙ＝Ｉ”であることを示すことができる。π１及びπ２が恒等置換である場合、以下の導出式が成り立つ。
【０１０６】
【数８】
【０１０７】
なお、π１及びπ２がランダム置換であっても、上記の導出には影響しない。したがって、このプロトコルは正確である。
【０１０８】
安全性
このプロトコルは安全であり、この安全性は、画像及び分類器がそれぞれ定義される部分空間の階数を定義するｍ及びｐによって支配される。このプロセスは安全であることを証明することができる。
【０１０９】
サーバは、クライアントによって送られるｍ枚のランダム画像５１２が入力ランダム５０１。画像４１１の一次結合であることを知っている。ｍのサイズが大きくなるほど、クライアントの安全性が増す。
【０１１０】
ステップ５３０において、クライアントはｐ枚の画像５０２をクライアントに送る。クライアントが第２の置換π２を用いない場合、サーバは画像Ｉ’ｊ及びＨ’ｉｊを求めることができ、未知数は係数ａｉのみとなり、これは最小二乗法で回復することができる。しかし、第２の置換π２はサーバに、任意の所与のｊについて、ランダムＨｉｊ５１１画像及び置換画像Ｉ’ｊ中の画素からの正確なマッピングを選択することを強いる。これは、
【０１１１】
【数９】
【０１１２】
個の選択肢の中から１つを選択することに等しく、ここでｎは画像中の画素数である。例えば、ｎ＝３２０＊２４０＝７６８００であり、ｍ＝２０である場合、可能な選択は
【０１１３】
【数１０】
【０１１４】
通りとなる。
【０１１５】
ステップ５２０において、クライアントはｍｐ枚の畳み込み画像５２１をクライアントに送る。クライアントが画像Ｈ１を、白い画素を１つだけ有する黒い画像として設定する場合、クライアントは全てのｊについてｇｉの値を回復することができる。しかし、クライアントは係数ｂｊを知らないため、分類器ｙを回復することができない。
【０１１６】
ステップ５４０において、クライアントは真又は偽［＋１，−１］のみをクライアントに返し、画像中に物体が存在するか否かを示す。したがって、クライアントはこのステップにおいて係数ｂｊを知り得ない。
【０１１７】
複雑度及び効率
このプロトコルは、それぞれ入力画像Ｉ５０１及び分類器ｙを表すために使用されるランダム画像の数及びベクトル数であるｍｐに従って線形である。
【０１１８】
このプロセスを拡張して、二分探索法を用いてこのプロセスを部分画像に繰り返し適用することによって、入力画像中の物体の位置を特定することができる。画像中に物体が検出される場合、画像を２分割又は４分割し、このプロセスを各部分画像に適用して物体の正確なロケーションを絞り込む。分割は必要に応じて繰り返すことができる。こうして、クライアントは、複数の偽物の画像をサーバに送ることができる。その場合、サーバは、検出された物体が本物なのか偽物なのかを判定することができない。
【０１１９】
［発明の効果］
本発明はゼロ知識技法を画像処理方法に応用する。問題領域の知識を利用することによって、本発明は、そうした処理を大幅に加速し、画像及びビデオに関わる安全なマルチパーティ計算の問題に対して実用的な解決策をもたらすことができる。
【０１２０】
ブラインドなコンピュータビジョン、特にブラインドな背景モデリング、ブラインドな連結成分ラベリング、及びブラインドな物体検出についていくつかのプロセスを説明する。様々なプロセスを組み合わせることにより、実用的なブラインドなコンピュータビジョンシステムが得られる可能性がある。
【０１２１】
本発明を好ましい実施の形態の例として説明してきたが、本発明の精神及び範囲内で様々な他の適応形態及び修正形態を実施してもよいことが理解される。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲に入るそのような変形形態及び修正形態をすべて網羅することである。
【図面の簡単な説明】
【０１２２】
【図１Ａ】本発明による、画像を安全に処理するシステムのブロック図である。
【図１Ｂ】本発明による、画像を安全に処理する方法のフロー図である。
【図２Ａ】本発明による処理すべき画像である。
【図２Ｂ】本発明による、動き画像を生成するための安全な背景モデリングのフロー図である。
【図２Ｃ】本発明による動き画像である。
【図３Ａ】重なり合うタイルに分割された動き画像である。
【図３Ｂ】本発明による、タイルを用いた安全な成分ラベリングのフロー図である。
【図３Ｃ】本発明による、動き画像の３×３タイルである。
【図３Ｄ】本発明による、連結成分を有する動き画像である。
【図３Ｅ】本発明による、フル画像を用いた安全な成分ラベリングのフロー図である。
【図４Ａ】本発明による、スキャン窓を用いて安全に検出すべきオブジェクトを含む動き画像である。
【図４Ｂ】本発明による第１の物体検出方法のフロー図である。
【図４Ｃ】本発明による第２の物体検出方法のフロー図である。
【特許請求の範囲】
【請求項１】
入力画像シーケンスを安全に処理する方法であって、
クライアントにおいて、入力画像シーケンスを取得することであって、各入力画像は画素を含む、取得すること、
前記クライアントにおいて、各入力画像中の前記画素を置換πに従ってランダムに置換して、各入力画像について置換画像を生成すること、
各置換画像をサーバに転送すること、
前記サーバにおいて、前記置換画像から背景画像を保持すること、
前記サーバにおいて、各置換画像を前記背景画像と結合して、各置換画像について対応する置換された動き画像を生成すること、
各置換された動き画像を前記クライアントに転送すること、及び
前記クライアントにおいて、各置換された動き画像中の前記画素を逆置換π−１に従って並べ換えて、各入力画像について対応する動き画像を回復すること
を含む、入力画像シーケンスを安全に処理する方法。
【請求項２】
各入力画像について、該入力画像よりも大きなランダム画像を生成すること、及び
前記置換を行った後に、各入力画像を前記ランダム画像に組み込んで、前記置換画像を生成すること
をさらに含む、請求項１に記載の方法。
【請求項３】
前記置換は、各入力画像中の前記画素の擬似ランダムな空間的配置変えである、請求項１に記載の方法。
【請求項４】
前記置換画像の強度ヒストグラムは、前記より大きなランダム画像の強度ヒストグラムと異なる、請求項２に記載の方法。
【請求項５】
前記より大きなランダム画像中の前記画素の強度値はランダムに変更される、請求項２に記載の方法。
【請求項６】
前記組み込みのロケーションはランダムに変化する、請求項２に記載の方法。
【請求項７】
前記組み込みのサイズはランダムに変化する、請求項２に記載の方法。
【請求項８】
前記組み込みの向きはランダムに変化する、請求項２に記載の方法。
【請求項９】
前記保持することは、
以前に処理された置換画像のセットを平均して、前記背景画像を保持すること
をさらに含む、請求項１に記載の方法。
【請求項１０】
前記結合は、前記置換画像から前記背景画像を減算して各画素について差を求める、請求項１に記載の方法。
【請求項１１】
前記画素は、前記差が所定の閾値よりも大きい場合に動き画素としてラベリングされる、請求項１１に記載の方法。
【請求項１２】
前記動き画像及び前記背景画像は２値画像である、請求項１に記載の方法。
【請求項１３】
前記動き画像から雑音を除去すること
をさらに含む、請求項１に記載の方法。
【請求項１４】
入力画像シーケンスを安全に処理する方法であって、
各入力画像中の前記画素をランダムに置換して、各入力画像について置換画像を生成すること、
前記置換画像から背景画像を保持すること、
各置換画像を前記背景画像と結合して、各置換画像について対応する置換された動き画像を生成すること、及び
各置換された動き画像中の前記画素を並べ換えて、各入力画像について対応する動き画像を回復すること
を含む、入力画像シーケンスを安全に処理する方法。
【請求項１５】
入力画像シーケンスを安全に処理するシステムであって、
入力画像シーケンスを取得するように構成されるクライアントであって、各入力画像は画素を含み、
該クライアントは、
各入力画像中の前記画素を置換πに従ってランダムに置換して、各入力画像について置換画像を生成する手段と、
置換された動き画像中の画素を逆置換π−１に従って並べ換えて、各入力画像について対応する動き画像を回復する手段と
をさらに備え、
前記置換画像から背景画像を保持するように構成されるサーバであって、
該サーバは、
各置換画像を前記背景画像と結合して、各置換画像について前記対応する置換された動き画像を生成する手段
をさらに備える、
入力画像シーケンスを安全に処理するシステム。
【請求項１】
入力画像シーケンスを安全に処理する方法であって、
クライアントにおいて、入力画像シーケンスを取得することであって、各入力画像は画素を含む、取得すること、
前記クライアントにおいて、各入力画像中の前記画素を置換πに従ってランダムに置換して、各入力画像について置換画像を生成すること、
各置換画像をサーバに転送すること、
前記サーバにおいて、前記置換画像から背景画像を保持すること、
前記サーバにおいて、各置換画像を前記背景画像と結合して、各置換画像について対応する置換された動き画像を生成すること、
各置換された動き画像を前記クライアントに転送すること、及び
前記クライアントにおいて、各置換された動き画像中の前記画素を逆置換π−１に従って並べ換えて、各入力画像について対応する動き画像を回復すること
を含む、入力画像シーケンスを安全に処理する方法。
【請求項２】
各入力画像について、該入力画像よりも大きなランダム画像を生成すること、及び
前記置換を行った後に、各入力画像を前記ランダム画像に組み込んで、前記置換画像を生成すること
をさらに含む、請求項１に記載の方法。
【請求項３】
前記置換は、各入力画像中の前記画素の擬似ランダムな空間的配置変えである、請求項１に記載の方法。
【請求項４】
前記置換画像の強度ヒストグラムは、前記より大きなランダム画像の強度ヒストグラムと異なる、請求項２に記載の方法。
【請求項５】
前記より大きなランダム画像中の前記画素の強度値はランダムに変更される、請求項２に記載の方法。
【請求項６】
前記組み込みのロケーションはランダムに変化する、請求項２に記載の方法。
【請求項７】
前記組み込みのサイズはランダムに変化する、請求項２に記載の方法。
【請求項８】
前記組み込みの向きはランダムに変化する、請求項２に記載の方法。
【請求項９】
前記保持することは、
以前に処理された置換画像のセットを平均して、前記背景画像を保持すること
をさらに含む、請求項１に記載の方法。
【請求項１０】
前記結合は、前記置換画像から前記背景画像を減算して各画素について差を求める、請求項１に記載の方法。
【請求項１１】
前記画素は、前記差が所定の閾値よりも大きい場合に動き画素としてラベリングされる、請求項１１に記載の方法。
【請求項１２】
前記動き画像及び前記背景画像は２値画像である、請求項１に記載の方法。
【請求項１３】
前記動き画像から雑音を除去すること
をさらに含む、請求項１に記載の方法。
【請求項１４】
入力画像シーケンスを安全に処理する方法であって、
各入力画像中の前記画素をランダムに置換して、各入力画像について置換画像を生成すること、
前記置換画像から背景画像を保持すること、
各置換画像を前記背景画像と結合して、各置換画像について対応する置換された動き画像を生成すること、及び
各置換された動き画像中の前記画素を並べ換えて、各入力画像について対応する動き画像を回復すること
を含む、入力画像シーケンスを安全に処理する方法。
【請求項１５】
入力画像シーケンスを安全に処理するシステムであって、
入力画像シーケンスを取得するように構成されるクライアントであって、各入力画像は画素を含み、
該クライアントは、
各入力画像中の前記画素を置換πに従ってランダムに置換して、各入力画像について置換画像を生成する手段と、
置換された動き画像中の画素を逆置換π−１に従って並べ換えて、各入力画像について対応する動き画像を回復する手段と
をさらに備え、
前記置換画像から背景画像を保持するように構成されるサーバであって、
該サーバは、
各置換画像を前記背景画像と結合して、各置換画像について前記対応する置換された動き画像を生成する手段
をさらに備える、
入力画像シーケンスを安全に処理するシステム。
【図１Ａ】
【図１Ｂ】
【図２Ａ】
【図２Ｂ】
【図２Ｃ】
【図３Ａ】
【図３Ｂ】
【図３Ｃ】
【図３Ｄ】
【図３Ｅ】
【図４Ａ】
【図４Ｂ】
【図４Ｃ】
【図１Ｂ】
【図２Ａ】
【図２Ｂ】
【図２Ｃ】
【図３Ａ】
【図３Ｂ】
【図３Ｃ】
【図３Ｄ】
【図３Ｅ】
【図４Ａ】
【図４Ｂ】
【図４Ｃ】
【公表番号】特表２００８−５２３６４１（Ｐ２００８−５２３６４１Ａ）
【公表日】平成２０年７月３日（２００８．７．３）
【国際特許分類】
【出願番号】特願２００６−５４１５２９（Ｐ２００６−５４１５２９）
【出願日】平成１７年１２月６日（２００５．１２．６）
【国際出願番号】ＰＣＴ／ＪＰ２００５／０２２７２２
【国際公開番号】ＷＯ２００６／０６２２２０
【国際公開日】平成１８年６月１５日（２００６．６．１５）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【出願人】（５０６３４７０７８）
【出願人】（５０６３４７０８９）
【Ｆターム（参考）】
【公表日】平成２０年７月３日（２００８．７．３）
【国際特許分類】
【出願日】平成１７年１２月６日（２００５．１２．６）
【国際出願番号】ＰＣＴ／ＪＰ２００５／０２２７２２
【国際公開番号】ＷＯ２００６／０６２２２０
【国際公開日】平成１８年６月１５日（２００６．６．１５）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【出願人】（５０６３４７０７８）
【出願人】（５０６３４７０８９）
【Ｆターム（参考）】
[ Back to top ]