(57)【要約】  様々な実施形態は、幾何学に基づくワーク実行の優先順位付けのためのコンピューティングデバイスのプロセッサにより実行される方法を含み得る。プロセッサは、画像などのイベントを受信し得る。プロセッサは、イベントに境界形状を重畳して、境界形状の外側にあるイベントの廃棄領域を特定し得る。プロセッサは、ワーキング境界形状内にあるイベントのワーク領域を特定し得る。デバイスは、イベントの特定されたワーク領域の各々に対する取消し尤度を決定し得る。プロセッサは、計算された取消し尤度に基づいて、特定されたワーク領域の各々に削減重みを割り当て得る。プロセッサは、次いで、割り当てられた削減重みに基づく順序で、特定されたワーク領域の各々をワークアイテムとして実行ワークリストに追加し得る。ワークアイテムは、削減重みの優先の順序で処理され得る。
2019519015.tif 000002
【特許請求の範囲】
【請求項１】
コンピューティングデバイス上での幾何学に基づくワーク実行の優先順位付けのための方法であって、
前記コンピューティングデバイスのプロセッサによって、第1の画像を取得するステップと、
前記プロセッサによって、前記第1の画像にデフォルトの境界形状を重畳して、ワーキング境界形状を初期化し、前記ワーキング境界形状の外側にある廃棄領域を特定するステップと、
前記プロセッサによって、前記ワーキング境界形状内にあるワーク領域を特定するステップと、
前記プロセッサによって、前記特定されたワーク領域の各々に対する取消し尤度を決定するステップと、
前記プロセッサによって、前記取消し尤度を使用して前記特定されたワーク領域の各々に対する削減重みを決定するステップと、
前記プロセッサによって、前記決定された削減重みに少なくとも一部基づく順序で、前記特定されたワーク領域の各々と関連付けられるワークアイテムを実行ワークリストに追加するステップとを備える、方法。
【請求項２】
前記プロセッサによって、第2の画像を取得するステップと、
前記プロセッサによって、前記ワーキング境界形状の場所を更新するステップと、
前記プロセッサによって、前記第2の画像に前記更新されたワーキング境界形状を重畳して、前記更新されたワーキング境界形状の外側にある前記廃棄領域への更新を特定するステップと、
前記プロセッサによって、いずれかのワークアイテムが前記廃棄領域と重複するワーク領域と関連付けられるかどうかを決定するステップと、
前記プロセッサによって、前記ワークアイテムが前記廃棄領域と重複すると決定したことに応答してワークアイテムを取り消すステップと、
前記プロセッサによって、前記更新されたワーキング境界形状内にある前記ワーク領域を更新するステップと、
前記プロセッサによって、前記更新されたワーク領域の各々に対する取消し尤度を決定するステップと、
前記プロセッサによって、前記取消し尤度に少なくとも一部基づいて前記特定されたワーク領域の各々への削減重みを決定するステップと、
前記プロセッサによって、前記決定された削減重みに少なくとも一部基づく順序で、前記特定されたワーク領域の各々と関連付けられるワークアイテムを前記実行ワークリストに追加するステップとをさらに備える、請求項1に記載の方法。
【請求項３】
前記更新されたワーク領域の各々に対する前記取消し尤度を決定するステップが、
前記プロセッサによって、前記取得された画像の焦点が動いている方向を決定するステップと、
前記プロセッサによって、前記決定された動きの方向に少なくとも一部基づいて、前記取消し尤度を決定するステップとを備える、請求項2に記載の方法。
【請求項４】
取消し尤度が、動きの方向に最も近い前記ワーク領域に対する取消し尤度が動きの前記方向から最も遠い前記ワーク領域に対する前記取消し尤度より低くなるように決定される、請求項3に記載の方法。
【請求項５】
前記プロセッサによって、最後に更新されたワーキング境界形状内にある各々の取得された画像の部分から合成画像を生成するステップをさらに備える、請求項2に記載の方法。
【請求項６】
前記合成画像がパノラマである、請求項5に記載の方法。
【請求項７】
前記合成画像が仮想現実レンダリングである、請求項5に記載の方法。
【請求項８】
前記プロセッサによって、前記ワーキング境界形状の前記重畳の場所に対して前記第1の画像上での更新されたワーキング境界形状の重畳の場所を比較することに少なくとも一部基づいて、前記ワーク領域の各々の前記取消し尤度を再決定するステップと、
前記プロセッサによって、前記取消し尤度に少なくとも一部基づいて、前記ワーク領域に対する更新された削減重みを決定するステップと、
前記プロセッサによって、前記実行ワークリストの中の前記ワークアイテムについて決定された前記更新された削減重みに少なくとも一部基づいて、前記実行ワークリストの中の前記ワークアイテムの順序を調整するステップとをさらに備える、請求項1に記載の方法。
【請求項９】
前記プロセッサによって、前記実行ワークリストの中の各ワークアイテムに対するワークスコアを決定するステップと、
前記プロセッサによって、前記ワークスコアに基づいて第2のプロセッサ上で実行すべきワークアイテムを決定するステップとをさらに備え、
前記ワークスコアが、前記ワークアイテムの前記決定された削減重み、前記ワークアイテムのサイズ、前記ワークアイテムの形状、および他のワークアイテムとの処理要素の共通性のうちの1つまたは複数に少なくとも一部基づいて決定される、請求項1に記載の方法。
【請求項１０】
前記プロセッサによって、各ワークアイテムが各処理装置に関する処理の適合性を示す複数のワークスコアを有するように、前記コンピューティングデバイスの1つ1つのプロセッサについて、前記実行ワークリストの中の各ワークアイテムに対するワークスコアを決定するステップをさらに備える、請求項9に記載の方法。
【請求項１１】
前記実行ワークリストの中の各ワークアイテムに対するワークスコアを決定するステップがさらに、前記ワークアイテムの起動オーバーヘッド、前記ワークアイテムを処理することと関連付けられる電池の消耗、前記ワークアイテムを取り消すことの容易さ、および前記プロセッサの利用率からなる群から選択される少なくとも1つのメンバーに少なくとも一部基づく、請求項9に記載の方法。
【請求項１２】
前記取消し尤度が、画像の中心からのワーク領域の距離に少なくとも一部基づく、請求項1に記載の方法。
【請求項１３】
前記特定されたワーク領域の各々に対する前記取消し尤度を決定するステップが、
前記プロセッサによって、タイムアウト時間長を決定するステップと、
前記プロセッサによって、後続の画像が前記タイムアウト時間長を超える期間の間ワーク領域内にない尤度を決定するステップとを備える、請求項1に記載の方法。
【請求項１４】
前記プロセッサによって、後続の画像が前記タイムアウト時間長を超える期間の間前記ワーク領域内にない前記尤度を決定するステップが、1つまたは複数のカルマンフィルタを実行して前記後続の画像の場所を予測するステップを備える、請求項13に記載の方法。
【請求項１５】
複数のワーキング境界形状がある、請求項1に記載の方法。
【請求項１６】
前記第1の画像が仮想現実ビュー空間のビューポートである、請求項1に記載の方法。
【請求項１７】
前記更新されたワーキング境界形状内にある前記ワーク領域を更新するステップが、
前記プロセッサによって、前記更新されたワーキング境界形状内にある1つまたは複数の新しいワーク領域を特定するステップと、
前記プロセッサによって、前記更新されたワーキング境界形状内に収まるように前記ワーク領域の境界を変更するステップとを備える、請求項2に記載の方法。
【請求項１８】
幾何学に基づくワーク実行の優先順位付けのために構成されるコンピューティングデバイスであって、
1つまたは複数のプロセッサを備え、前記1つまたは複数のプロセッサが、
第1の画像を取得し、
前記第1の画像にデフォルトの境界形状を重畳して、ワーキング境界形状を初期化し、前記ワーキング境界形状の外側にある廃棄領域を特定し、
前記ワーキング境界形状内にあるワーク領域を特定し、
前記特定されたワーク領域の各々に対する取消し尤度を決定し、
前記取消し尤度を使用して前記特定されたワーク領域の各々に対する削減重みを決定し、
前記決定された削減重みに少なくとも一部基づく順序で、前記特定されたワーク領域の各々と関連付けられるワークアイテムを実行ワークリストに追加する
ように構成される、コンピューティングデバイス。
【請求項１９】
前記1つまたは複数のプロセッサがさらに、
第2の画像を取得し、
前記ワーキング境界形状の場所を更新し、
前記第2の画像に前記更新されたワーキング境界形状を重畳して、前記更新されたワーキング境界形状の外側にある前記廃棄領域への更新を特定し、
いずれかのワークアイテムが前記廃棄領域と重複するワーク領域と関連付けられるかどうかを決定し、
前記ワークアイテムが前記廃棄領域と重複すると決定したことに応答してワークアイテムを取り消し、
前記更新されたワーキング境界形状内にある前記ワーク領域を更新し、
前記更新されたワーク領域の各々に対する取消し尤度を決定し、
前記取消し尤度に少なくとも一部基づいて前記特定されたワーク領域の各々に対する削減重みを決定し、
前記決定された削減重みに少なくとも一部基づく順序で、前記特定された前記ワーク領域の各々と関連付けられるワークアイテムを前記実行ワークリストに追加する
ように構成される、請求項18に記載のコンピューティングデバイス。
【請求項２０】
前記1つまたは複数のプロセッサがさらに、
前記取得された画像の焦点が動いている方向を決定することと、
前記決定された動きの方向に少なくとも一部基づいて、前記取消し尤度を決定することと
によって、前記更新されたワーク領域の各々に対する前記取消し尤度を決定するように構成される、請求項19に記載のコンピューティングデバイス。
【請求項２１】
前記1つまたは複数のプロセッサがさらに、動きの方向に最も近い前記前記ワーク領域に対する取消し尤度が動きの前記方向から最も遠い前記ワーク領域に対する前記取消し尤度より低くなるように前記取消し尤度を決定するように構成される、請求項20に記載のコンピューティングデバイス。
【請求項２２】
前記1つまたは複数のプロセッサがさらに、
最後の更新されたワーキング境界形状内にある各々の取得された画像の部分から合成画像を生成するように構成される、請求項19に記載のコンピューティングデバイス。
【請求項２３】
前記1つまたは複数のプロセッサがさらに、
前記ワーキング境界形状の前記重畳の場所に対して前記第1の画像上での更新されたワーキング境界形状の重畳の場所を比較することに少なくとも一部基づいて、前記ワーク領域の各々の前記取消し尤度を再決定し、
前記再決定された取消し尤度に少なくとも一部基づいて、前記ワーク領域に対する更新された削減重みを決定し、
前記実行ワークリストの中の前記ワークアイテムについて決定された前記更新された削減重みに少なくとも一部基づいて、前記実行ワークリストの中の前記ワークアイテムの順序を調整するように構成される、請求項18に記載のコンピューティングデバイス。
【請求項２４】
前記1つまたは複数のプロセッサがさらに、
前記実行ワークリストの中の各ワークアイテムに対するワークスコアを決定し、
前記決定されたワークスコアに少なくとも一部基づいて、第2のプロセッサ上で実行すべきワークアイテムを決定するように構成され、
前記ワークスコアが、前記ワークアイテムの前記決定された削減重み、前記ワークアイテムのサイズ、前記ワークアイテムの形状、および他のワークアイテムとの処理要素の共通性のうちの1つまたは複数に少なくとも一部基づいて決定される、請求項18に記載のコンピューティングデバイス。
【請求項２５】
前記1つまたは複数のプロセッサがさらに、各ワークアイテムが各処理装置に関する処理の適合性を示す複数のワークスコアを有するように、前記コンピューティングデバイスの1つ1つのプロセッサについて、前記実行ワークリストの中の各ワークアイテムに対するワークスコアを決定するように構成される、請求項24に記載のコンピューティングデバイス。
【請求項２６】
前記1つまたは複数のプロセッサがさらに、
タイムアウト時間長を決定することと、
後続の画像が前記タイムアウト時間長を超える期間の間ワーク領域内にない尤度を決定することと
によって、前記特定されたワーク領域の各々に対する前記取消し尤度を決定するように構成される、請求項18に記載のコンピューティングデバイス。
【請求項２７】
前記1つまたは複数のプロセッサがさらに、
前記更新されたワーキング境界形状内にある1つまたは複数のワーク領域を特定することと、
前記更新されたワーキング境界形状内に収まるように前記ワーク領域の境界を変更することと
によって、前記更新されたワーキング境界形状内にある前記ワーク領域を更新するように構成される、請求項19に記載のコンピューティングデバイス。
【請求項２８】
幾何学に基づくワーク実行の優先順位付けのために構成されるコンピューティングデバイスであって、
第1の画像を取得するための手段と、
前記第1の画像にデフォルトの境界形状を重畳して、ワーキング境界形状を初期化し、前記ワーキング境界形状の外側にある廃棄領域を特定するための手段と、
前記ワーキング境界形状内にあるワーク領域を特定するための手段と、
前記特定されたワーク領域の各々に対する取消し尤度を決定するための手段と、
前記取消し尤度を使用して前記特定されたワーク領域の各々に対する削減重みを決定するための手段と、
前記決定された削減重みに少なくとも一部基づく順序で、前記特定されたワーク領域の各々と関連付けられるワークアイテムを実行ワークリストに追加するための手段とを備える、コンピューティングデバイス。
【請求項２９】
幾何学に基づくワーク実行の優先順位付けのための動作をプロセッサに実行させるプロセッサ実行可能命令を記憶した非一時的プロセッサ可読媒体であって、前記動作が、
第1の画像を取得することと、
前記第1の画像にデフォルトの境界形状を重畳して、ワーキング境界形状を初期化し、前記ワーキング境界形状の外側にある廃棄領域を特定することと、
前記ワーキング境界形状内にあるワーク領域を特定することと、
前記特定されたワーク領域の各々に対する取消し尤度を決定することと、
前記取消し尤度を使用して前記特定されたワーク領域の各々に対する削減重みを決定することと、
前記決定された削減重みに少なくとも一部基づく順序で、前記特定されたワーク領域の各々と関連付けられるワークアイテムを実行ワークリストに追加することと
を備える、非一時的プロセッサ可読媒体。
【請求項３０】
第2の画像を取得することと、
前記ワーキング境界形状の場所を更新することと、
前記第2の画像に前記更新されたワーキング境界形状を重畳して、前記更新されたワーキング境界形状の外側にある前記廃棄領域への更新を特定することと、
いずれかのワークアイテムが前記廃棄領域と重複するワーク領域と関連付けられるかどうかを決定することと、
前記ワークアイテムが前記廃棄領域と重複すると決定したことに応答してワークアイテムを取り消すことと、
前記更新されたワーキング境界形状内にある前記ワーク領域を更新することと、
前記更新されたワーク領域の各々に対する取消し尤度を決定することと、
前記取消し尤度に少なくとも一部基づいて前記特定されたワーク領域の各々に対する削減重みを決定することと、
前記決定された削減重みに少なくとも一部基づく順序で、前記特定された前記ワーク領域の各々と関連付けられるワークアイテムを前記実行ワークリストに追加することと
をさらに備える動作を前記プロセッサに実行させるプロセッサ実行可能命令を記憶した、請求項29に記載の非一時的プロセッサ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、その内容全体が参照により本明細書に組み込まれる、2016年3月31日に出願された「Geometric Work Scheduling with Dynamic and Probabilistic Work Trimming」と題する米国仮出願第62/316,235号の米国特許法第119条(e)に基づく優先権の利益を主張するものである。
【背景技術】
【０００２】
画像を撮影してビデオコンテンツを記録するためにモバイルデバイスのカメラを使用することは、より多数のアプリケーションがマルチメディアコンテンツを利用するようになるにつれて、またはマルチメディアコンテンツをユーザが共有することを可能にするにつれて、増え続けている。コンピュータの処理リソースに多大な要求を課す、画像処理および画像生成の多くの用途がある。2つの例は、ユーザが携帯電話をパンしてパノラマ画像を生成する間に画像フレームをつなぎ合わせること、および仮想現実のイメージングである。両方の技法が、単一の画像の産物を生成するために、複数の、場合によっては多数の画像の処理を必要とする。高速な画像処理を行うのに必要な処理能力を減らし、視覚的な遅延を減らすために、画像データ(キャプチャまたはレンダリングされた)を効率的に処理する方法、または前処理する方法が望ましい。これは特に、処理および電力のリソースが限られていることがあるスマートフォンなどのモバイルデバイスに当てはまる。
【発明の概要】
【課題を解決するための手段】
【０００３】
様々な実施形態は、コンピューティングデバイス上で幾何学に基づくワークの優先順位付けのための方法と、方法を実施するためのデバイスと、方法の動作をプロセッサに実行させるように構成される命令を含む非一時的プロセッサ可読記憶媒体とを含み得る。様々な実施形態は、第1の画像を取得するステップと、第1の画像にデフォルトの境界形状を重畳して、ワーキング境界形状を初期化し、ワーキング境界形状の外側にある廃棄領域を特定するステップとを含み得る。様々な実施形態はさらに、ワーキング境界形状内にあるワーク領域を特定するステップと、特定されたワーク領域の各々に対する取消し尤度を決定するステップと、取消し尤度を使用して特定されたワーク領域の各々に対する削減重みを決定するステップと、決定された削減重みに少なくとも一部基づく順序で、特定されたワーク領域の各々と関連付けられるワークアイテムを実行ワークリストに追加するステップとを含み得る。
【０００４】
いくつかの実施形態はさらに、第2の画像を取得するステップと、ワーキング境界形状の場所を更新するステップと、第2の画像に更新されたワーキング境界形状を重畳して、更新されたワーキング境界形状の外側にある廃棄領域への更新を特定するステップと、いずれかのワークアイテムが廃棄領域と重複するワーク領域と関連付けられるかどうかを決定するステップとを含み得る。そのような実施形態はさらに、ワークアイテムが廃棄領域と重複すると決定したことに応答してワークアイテムを取り消すステップと、更新されたワーキング境界形状内にあるワーク領域を更新するステップとを含み得る。そのような実施形態はさらに、更新されたワーク領域の各々に対する取消し尤度を決定するステップと、取消し尤度に少なくとも一部基づいて特定されたワーク領域の各々の削減重みを決定するステップと、決定された削減重みに少なくとも一部基づく順序で、特定されたワーク領域の各々と関連付けられるワークアイテムを実行ワークリストに追加するステップとを含み得る。
【０００５】
そのような実施形態では、更新されたワーク領域の各々に対する取消し尤度は、取得された画像の焦点が動いている方向を決定するステップと、決定された動きの方向に少なくとも一部基づいて取消し尤度を決定するステップとを含み得る。そのような実施形態では、取消し尤度は、動きの方向に最も近いワーク領域に対する取消し尤度が動きの方向から最も遠くにあるワーク領域に対する取消し尤度より低くなるように決定され得る。
【０００６】
いくつかの実施形態は、最後の更新されたワーキング境界形状内にある各々の取得された画像の部分から合成画像を生成するステップを含み得る。いくつかの実施形態において、合成画像はパノラマであり得る。いくつかの実施形態において、合成画像は仮想現実レンダリングであり得る。
【０００７】
いくつかの実施形態はさらに、ワーキング境界形状の重複の場所に対して第1の画像上での更新されたワーキング境界形状の重複の場所を比較することに少なくとも一部基づいて、ワーク領域の各々の取消し尤度を再決定するステップと、取消し尤度に少なくとも一部基づいて、ワーク領域に対する更新された削減重みを決定するステップと、実行ワークリストの中のワークアイテムについて決定された更新された削減重みに少なくとも一部基づいて、実行ワークリストの中のワークアイテムの順序を調整するステップとを含み得る。
【０００８】
いくつかの実施形態はさらに、実行ワークリストの中の各ワークアイテムに対するワークスコアを決定するステップと、ワークスコアに基づいて第2のプロセッサ上で実行すべきワークアイテムを決定するステップとを含み得る。そのような実施形態では、ワークスコアは、ワークアイテムの決定された削減重み、ワークアイテムのサイズ、ワークアイテムの形状、および他のワークアイテムとの処理要素の共通性のうちの1つまたは複数に少なくとも一部基づいて決定され得る。そのような実施形態はさらに、各ワークアイテムが各処理装置に関する処理の適合性を示す複数のワークスコアを有し得るように、コンピューティングデバイスの1つ1つのプロセッサについて、実行ワークリストの中の各ワークアイテムに対するワークスコアを決定するステップを含み得る。他のそのような実施形態では、実行ワークリストの中の各ワークアイテムに対するワークスコアを決定するステップはさらに、ワークアイテムの起動オーバーヘッド、ワークアイテムを処理することと関連付けられる電池の消耗、ワークアイテムを取り消すことの容易さ、およびプロセッサの利用率からなる群から選択される少なくとも1つのメンバーに少なくとも一部基づき得る。
【０００９】
いくつかの実施形態では、取消し尤度は、画像の中心からのワーク領域の距離に少なくとも一部基づき得る。
【００１０】
いくつかの実施形態では、特定されたワーク領域の各々に対する取消し尤度を決定するステップは、タイムアウト時間長を決定するステップと、後続の画像がタイムアウト時間長を超える期間の間ワーク領域内にない尤度を決定するステップとを含み得る。そのような実施形態では、プロセッサによって、後続の画像がタイムアウト時間長を超える期間の間ワーク領域内にない尤度を決定するステップは、1つまたは複数のカルマンフィルタを実行して後続の画像の場所を予測するステップを含み得る。
【００１１】
いくつかの実施形態では、複数のワーキング境界形状があり得る。
【００１２】
いくつかの実施形態において、第1の画像は仮想現実ビュー空間のビューポートであり得る。
【００１３】
いくつかの実施形態では、更新されたワーキング境界形状内にあるワーク領域を更新するステップは、更新されたワーキング境界形状内にある1つまたは複数の新しいワーク領域を特定するステップと、更新されたワーキング境界形状内に収まるようにワーク領域の境界を変更するステップとを含み得る。
【００１４】
さらなる実施形態は、上で要約された方法の動作を実行するようにプロセッサ実行可能命令によって構成された1つまたは複数のプロセッサを有する通信デバイスを含み得る。さらなる実施形態は、上で要約された方法の機能を実行するための手段を有する通信デバイスを含み得る。さらなる実施形態は、通信デバイスのプロセッサに上で要約された方法の動作を実行させるように構成されたプロセッサ実行可能命令が記憶された非一時的プロセッサ可読記憶媒体を含み得る。
【００１５】
本明細書に組み込まれ、本明細書の一部を構成する添付の図面は、方法およびデバイスの例示的な実施形態を示す。上記の全般的な説明および下記の発明を実施するための形態とともに、図面は、開示される実施形態を限定するのではなく、方法およびデバイスの特徴を説明するのに役立つ。
【図面の簡単な説明】
【００１６】
【図１】様々な実施形態とともに使用するのに適したコンピューティングデバイスを示すブロック図である。
【図２】様々な実施形態による幾何学的なワークスケジューリングのための実施形態の方法を示すプロセスフロー図である。
【図３】様々な実施形態による、3次元空間への検出されたイベントのマッピングを示す図である。
【図４】キャプチャされたフレームをつなぎ合わせてパノラマ画像を作成するための従来の方法を示す図である。
【図５】キャプチャされたフレームをつなぎ合わせてパノラマ画像を作成するための従来の方法を示す図である。
【図６】様々な実施形態による、画像をワーク領域へと分割して各領域をコンピューティングデバイス上の優先順位付けられた実行ワークリストに挿入するための実装形態を示すブロック図である。
【図７】様々な実装形態による、コンピューティングデバイス上で実施される幾何学に基づくワークの優先順位付け方法におけるワークフローの概要を示すブロック図である。
【図８】様々な実施形態による、幾何学に基づく領域の廃棄または保持の尤度を決定するための動き追跡を示すブロック図である。
【図９】様々な実施形態による、画像処理アプリケーションにおけるワーク処理の幾何学に基づく優先順位付けのための方法を示すプロセスフロー図である。
【図１０】様々な実施形態による、複数の処理装置にわたってワーク領域に基づいて優先順位付けられるワークの実行のための方法を示すプロセスフロー図である。
【図１１】仮想現実環境における幾何学的なワークスケジューリングを実施するための一般的な方法を示すプロセスフロー図である。
【図１２】いくつかの実施形態による、コンピュータゲームにおける幾何学的なワークスケジューリングの実施を示す図である。
【発明を実施するための形態】
【００１７】
添付の図面を参照して、様々な実施形態が詳細に説明される。可能な限り、同じまたは同様の部分を指すために図面全体を通して同じ参照番号が使用される。特定の例および実装形態に対してなされる参照は、説明が目的であり、特許請求の範囲を限定することを意図していない。
【００１８】
本明細書では、「コンピューティングデバイス」という用語は、種々のコンピュータおよびコンピューティングデバイス、デジタルカメラ、デジタルビデオ記録デバイスのうちの任意の1つまたはすべてを指すために使用され、これらの非限定的な例は、スマートデバイス、ウェアラブルスマートデバイス、デスクトップコンピュータ、ワークステーション、サーバ、携帯電話、スマートフォン、ウェアラブルコンピューティングデバイス、パーソナルまたはモバイルマルチメディアプレーヤ、携帯情報端末(PDA)、ラップトップコンピュータ、タブレットコンピュータ、スマートブック、パームトップコンピュータ、ワイヤレス電子メール受信機、マルチメディアインターネット対応携帯電話、ワイヤレスゲームコントローラ、モバイルロボット、ならびにプログラム可能なプロセッサおよびメモリを含む同様の個人向け電子デバイスを含む。
【００１９】
本明細書では、「幾何学的に境界を区切られた領域」という用語は、N次元空間内での任意の空間的なマッピングを指すために使用される。幾何学的に境界を区切られた領域は、「ワーク領域」にマッピングされた実行可能なワークアイテムと、「廃棄領域」にマッピングされた実行される可能性の低いワークアイテムまたは冗長なワークアイテムと、「削減領域」にマッピングされた潜在的に実行可能なワークアイテムまたは廃棄可能なワークアイテムと関連付けられる削減重みとを含み得る。
【００２０】
本明細書では、「パノラマ」という用語は、複数の画像またはビデオファイルの合成(たとえば、つなぎ合わせ)を通じて生成される任意の合成画像またはビデオを指すために使用される。画像およびビデオファイルは、コンピューティングデバイスカメラ、スキャニングデバイス、または、コンピューティングデバイスと通信している他の画像およびビデオキャプチャデバイスによってキャプチャされ得る。各画像またはビデオの複数の部分が、元の構成要素画像より大きい次元を有する拡張された画像を作成するために、他の画像またはビデオとつなぎ合わされ得る。パノラマは、軸の次元が拡張された画像またはビデオを含み得る。
【００２１】
概略的に、様々な実施形態および実装形態は、コンピューティングデバイス上で幾何学に基づくワーク実行の優先順位付けのための方法と、そのような方法を実施するコンピューティングデバイスと、そのような方法を実施するプロセッサ実行可能命令を記憶する非一時的プロセッサ可読媒体とを含み得る。様々な実装形態は、コンピューティングデバイスのプロセッサによって、コンピューティングデバイス上で実行されるアプリケーション内でのキーイベントの発生を検出することを含み得る。プロセッサは、キーイベントを、N次元空間内の幾何学的に境界を区切られた第1のワーク領域にマッピングし得る。プロセッサは次いで、第1のワーク領域をデフォルトの境界領域と比較して、ワーキング境界領域を初期化し、第1のワーク領域の中かつデフォルトの境界領域の外にある1つまたは複数の廃棄領域を特定し得る。方法は、ワーキング境界領域内にある1つまたは複数のワーク領域を特定するステップを含むことがあり、第1のワーク領域の特定されたワーク領域の各々に対する取消し尤度を決定し得る。方法はさらに、プロセッサによって、計算された取消し尤度に基づいて、特定されたワーク領域の各々に対する削減重みを決定するステップを含み得る。様々な実装形態は、プロセッサによって、特定されたワーク領域の各々を、実行の準備ができているワークアイテムとして提出することを含み得る。
【００２２】
様々な実装形態は、現在実行の準備ができているワークアイテムの一部またはすべてを選択および/または優先順位付けし、決定された優先順位に基づいて選択されたワークアイテムの実行を開始するための、方法を含み得る。プロセッサは、準備ができているワークアイテムと関連付けられる削減重み、ワークアイテムを実行することが可能なプロセッサの利用可能な数およびタイプ(CPUコアおよびGPUなど)、ならびにワークアイテム自体の追加の特性(ワークアイテムの幾何学的形状およびデフォルトの境界領域内でのワークアイテムの位置など)に基づいて、選択および優先順位付けを実行し得る。説明されるように、様々な実装形態は、すべての準備ができているワークアイテムを直ちに実行しなくてよい。今後のキーイベントの発生および後続の分析が、1つまたは複数の廃棄領域の特定をもたらし得る。これらの廃棄領域は、以前のキーイベントの検出に応答してプロセッサによって前に提出された準備ができているワークアイテムのワーク空間と、空間(すなわち、ワークアイテムおよび廃棄領域がマッピングされるN次元空間)において重複することがある。そのような重複が検出される場合、ワークアイテムは実行されずに廃棄され得る。加えて、様々な実装形態において、今後のキーイベントの発生および分析により、プロセッサが新しいワーク領域(すなわち、ワークアイテム)および対応する削減重みを特定するようになり得る。新たに特定されたワーク領域に重複する以前のキーイベントの発生の結果として実行のために提出されるものを含む、実行の準備ができているワークアイテムの削減重みは、新たに特定されたワーク領域(たとえば、ワークアイテム)と関連付けられる削減重みに変更され得る。最後に、様々な実装形態において、プロセッサは、更新された削減重みに基づいて、現在準備ができているワークアイテムのすべての中から、ワークアイテムを選択して優先順位付け得る。
【００２３】
いくつかの実装形態は、キャプチャされた写真もしくはビデオ、またはレンダリングされた画像の受信などによって、第1の画像を取得することを含み得る。そのような実装形態は、第1の画像にデフォルトの境界形状を重畳して、ワーキング境界形状を初期化し、ワーキング境界形状の外側にある第1の画像の第1の廃棄領域を特定するステップを含み得る。いくつかの実装形態はさらに、ワーキング境界形状内にある第1の画像のワーク領域を特定するステップを含み得る。そのような領域は、長方形、超平面、3次元、または他の幾何学的形状であってよく、任意の軸方向、半径方向、または球面方向を向いていてよい。いくつかの実施形態は、第1の画像の特定されたワーク領域の各々に対する取消し尤度を計算すること、または別様に決定することを含み得る。取消し尤度は、ワーク領域が廃棄され最終的な産物を作成する際に使用されない尤度、またはワーク領域が保持され最終的な産物において使用される尤度のいずれかを表し得る。いくつかの実施形態は、計算された取消し尤度に基づいて、特定されたワーク領域の各々に削減重みを割り当てることを含み得る。削減重みは、所定の尺度での数または百分率であり得るが、ワーク領域の保持または取消しの数学的に正確な確率を表さないことがある。いくつかの実施形態は、割り当てられた削減重みに基づく順序で、特定されたワーク領域の各々をワークアイテムとして実行ワークリストに追加することを含み得る。これらの動作は後続の画像またはビデオが取得されるにつれて繰り返されてよく、重複領域(たとえば、廃棄領域)はワークリストから廃棄または除去されてよい。実行ワークリストは、1つ1つの画像が受信され分析されると、および/または、プロセッサが新しいワークアイテムに取り掛かることが可能になるたびに、並び替えられ、または再び優先順位付けられ得る。
【００２４】
様々な実装形態において、コンピューティングデバイスは、各画像内の特定されたワーク領域に基づいて、イベント、ビデオ、および画像(キャプチャまたはレンダリングされた)の処理を優先順位付ける方法を実施し得る。コンピューティングデバイスは、パノラマ、ビデオセグメント、またはアプリケーションAPIコールなどの、最終的なワークの産物を生成する際に、特定されたワーク領域が廃棄される(たとえば、削減される、取り消される、または決して使用されない)尤度または廃棄されない尤度(すなわち、出現する確率)を決定し得る。削減重みは、最終的なパノラマの生成において領域が保持および/または利用される尤度を示すために、特定されたワーク領域の各々に割り当てられ得る。ワーク領域および/またはその関連するワークアイテムは、割り当てられた削減重みに基づいて、個別に、または集団で実行ワークリストに追加され得る。削減重みは新しいイベントが検出される(たとえば、画像がキャプチャされる)につれて再評価されてよく、実行ワークリストは、様々なワーク領域の実行の優先順位の変化を考慮するように並び替えられてよい。したがって、取り消されるまたは廃棄される可能性が最も低いと見なされるワーク領域は、処理リソースが利用可能になるとすぐに、処理されるべき実行ワークリストの前面に継続的に移され得る。このようにして、様々な実装形態は、キャプチャされた画像の前処理およびそれらの領域を一緒につなぎ合わせるための処理などの、アプリケーションのワークロードのかなりの部分の前処理を、画像キャプチャの完了の前に可能にし得る。
【００２５】
様々な実施形態および実装形態は、最終的な産物または動作に必要である確率的な尤度に従って処理され得る幾何学的領域へとあらゆる種類のワークを分割するための、一般的な方法、デバイス、および非一時的プロセッサ可読媒体に記憶されたプロセッサ実行可能命令に関する。様々な実施形態が、例示的な実装形態を提供するために、全般に、かつ画像処理および仮想現実への適用の特定の例を参照して説明される。
【００２６】
様々な実施形態では、コンピューティングデバイスは、1つまたは複数のプロセッサにわたってアプリケーションのワークロードを分割し得る。ワークは、処理効率を上げるために、かつ最終的な産物を生成することまたはアプリケーション動作を実行することに必要な消費電力を減らすために、分離されスケジューリングされ得る。
【００２７】
ある例として、コンピューティングデバイス上で実行されるアプリケーションは、複数の画像を間欠的にキャプチャすることができ、画像を一緒につなぎ合わせてパノラマ画像を形成することができる。アクティブな画像キャプチャセッションの間、コンピューティングデバイスは、画像がキャプチャされるにつれてキャプチャされた画像のワーク領域を特定し得る。コンピューティングデバイスは、1つまたは複数の幾何学的な形状の境界を入来するキャプチャされた画像/フレームに適用して、画像の別々の領域を特定し得る。たとえば、コンピューティングデバイスは、キャプチャされた画像を、画像の中心部分が最大のスライスを含み画像の周縁に近づくにつれて次第により小さなスライスを含むように、長方形のスライスへと分割し得る。コンピューティングデバイスは、ワークを特定された領域の各々と関連付けることができ、各領域が最終的な産物から廃棄されるべき尤度に基づいて、ワークを実行ワークリスト(すなわち、処理キュー)へと挿入することができる。ワーク領域が最終的なパノラマ産物から廃棄される、または取り消される尤度は、領域に割り当てられた削減重みによって示され得る。各ワーク領域に割り当てられる削減重みは、新しい画像がキャプチャされて現在の画像と比較されるにつれて、更新され得る。
【００２８】
様々な実施形態では、コンピューティングデバイスは、最終的な処理された画像(たとえば、合成パノラマビュー)において最も使用される可能性が低い(すなわち、最も廃棄される可能性が高い)ワーク領域を決定し得る。代替的な実施形態において、コンピューティングデバイスは代わりに、最終的な処理された画像において保持される可能性が最も高いワーク領域を決定し得る。これらの領域は次いで、最終的な産物において保持される決定された尤度と矛盾しない順序で、実行ワークリスト(すなわち、ワーク処理キュー)に割り当てられ得る。たとえば、キャプチャされた画像の周縁に近い領域はワーク処理キューにおいて最後にあることがあり、それは、キャプチャされた画像のそのような領域は、画像のパノラマシーケンスが撮られるときのカメラの垂直方向のぶれ(上および下)により、最終的な産物(たとえば、合成パノラマ画像)から切り取られる可能性が最も高いからである。
【００２９】
様々な実装形態において、コンピューティングデバイスは、ワーク領域(たとえば、デフォルトの境界形状)を使用して取り消されるべき処理ワークを決定し得る。ワーク領域(たとえば、デフォルトの境界形状)が入来するキャプチャされた画像に適用された後で、コンピューティングデバイスは、重複する、交差する、損傷した、または別様に不要な領域を検出するために、受信された画像の一部またはすべてを比較し得る。処理リソースを節約するために、コンピューティングデバイスは、最終的な産物から後で切り取られるであろう画像の処理およびレンダリングに処理リソースを費やすのではなく、最終的な産物において使用される可能性が低いと見なされるワークを取り消し、または別様に廃棄し得る。取り消された領域は処理されず、結果として、最終的な産物からなくなる。
【００３０】
動き、ぶれ、速さ、方向などに関する情報も、保持または廃棄の尤度に基づいてワーク領域の処理をさらに優先順位付けるために使用される。たとえば、コンピューティングデバイスによって収集される加速度計データが、頭の動きに基づいてヘッドマウント仮想現実ディスプレイにレンダリングされる可能性が最も高いフレーム中のワーク領域を特定するために使用され得る。廃棄領域と関連付けられるワークアイテムの取消しは、処理要件を大きく下げ、不可欠な領域のより高速な前処理を可能にし得るので、ジッタとして知覚される視覚的な影響を減らすことができる。別の例として、加速度データおよび/またはフレームごとの垂直方向のずれの分析が、ユーザがカメラをパンする際の上方または下方へのぶれが原因でパノラマにおいて保持される可能性が最も高いフレーム内のワーク領域を、優先順位付けられた処理のために特定するために使用され得る。したがって、カメラが上にパンしている場合、下端のスライスは優先されない。
【００３１】
様々な実装形態は、特定された処理の類似性に基づく、コンピューティングデバイスの複数の処理装置にわたるワークの優先順位付けられたスケジューリングを可能にし得る。コンピューティングデバイスは、n次元空間にアプリケーションの処理ワークをマッピングすることができ、「n」はアプリケーションプログラミングインターフェース(API)コールの数である。n次元空間の領域は、同様の処理の需要を有するものとして特定されるワークのクラスタを有し得る。たとえば、同様のタイプの画像または同じ標的のビデオを処理する必要があるビデオ編集ソフトウェアアプリケーションは、同様の処理の需要を有するものとして特定され得る。特定された領域と関連付けられるワークは、中央処理装置または画像処理装置などの処理装置に集合的に割り当てられ得る。したがって、異なるアプリケーションの同様のワークが、処理の冗長性を減らすためにグループとして実行をスケジューリングされ得る。異なる処理装置へのワークの割当ては、処理ワークのサイズおよび複雑さに依存し得る。たとえば、画像処理装置は優先度の高いタスクを比較的大量に処理することと関連付けられるワークを割り当てられることがあり、それは、GPUキューからタスクを取り消すことまたは削除することがリソース集約的であり得るからである。
【００３２】
特定された類似する領域または最終的な産物において使用/保持される可能性が最も高い領域に基づいて、ワークを前処理し、スケジューリングし、優先順位付けることによって、様々な実装形態が、画像を処理してつなぎ合わせること、音を処理すること、(たとえば、仮想現実アプリケーションにおいて)画像をレンダリングすることなどに必要な時間および処理リソースを減らすことができる。
【００３３】
様々な実装形態は、キャプチャされた画像(たとえば、パノラマへのつなぎ合わせ)またはレンダリングされているフレーム(たとえば、仮想現実ディスプレイ)において、ワーク領域の特定を使用することを含み得る。特定されたワーク領域は、その幾何学的領域が最終的な産物において保持される決定された尤度/確率、ならびに、それに従ったキャプチャされた画像およびソフトウェアアプリケーションのためのワーク処理のスケジューリング/優先順位付けでタグ付けされ、またはそれらと関連付けられ得る。したがって、様々な実装形態は、領域の保持または廃棄の尤度に基づいて、キャプチャされた/レンダリングされた画像のワーク領域の処理を優先順位付け得る。領域は次いで、保持される可能性が低い領域が最後に処理されるように処理をスケジューリングされ得るので、処理が開始する前に取り消されることがある。
【００３４】
様々な実装形態は、保持または廃棄の尤度を決定するために使用され得る情報を提供するアクティブな画像幾何学および/または他のデータ(たとえば、加速度計)に基づく、ワーク領域の画像処理の動的な再優先順位付けを可能にし得る。ワークは、キャプチャまたはレンダリングされた画像のある幾何学的領域が不要であるものとして特定されるときに処理キューから取り消されることがあり、これにより、保持される可能性が低い領域の優先順位を下げることを活用する。性能をさらに上げるために、ワークは、n次元空間内の類似性が特定された幾何学的領域に基づいて、複数の処理装置にまたがってスケジューリングされ得る。このようにして、様々な実装形態は、最終的なパノラマにおいて保持される可能性が高い画像領域の予測に基づく、キャプチャされた画像のつなぎ合わせの前処理を可能にし得る。
【００３５】
図1は、様々な実施形態とともに使用するのに適したコンピューティングデバイス100を示す。コンピューティングデバイス100は、バス105を介して電気的に結合され得る(または適宜、別様に通信し得る)ハードウェア要素を備えるように図示されている。ハードウェア要素は、限定はされないが、1つもしくは複数の汎用プロセッサおよび/または1つもしくは複数の専用プロセッサ(デジタル信号処理チップ、グラフィカルアクセラレーションプロセッサなど)を含む1つまたは複数のプロセッサ110、タッチスクリーン115を含み、限定はされないが、1つまたは複数のカメラ、1つまたは複数のデジタルビデオレコーダ、マウス、キーボード、キーパッド、マイクロフォンなどをさらに含む1つまたは複数の入力デバイス、ならびに限定はされないが、外部出力デバイス、ディスプレイデバイス、スピーカ116、プリンタなどに結合するためのインターフェース120(たとえば、ユニバーサルシリアルバス(USB))を含む1つまたは複数の出力デバイスを含み得る。
【００３６】
コンピューティングデバイス100はさらに、不揮発性メモリ125などの1つまたは複数の非一時的記憶デバイスをさらに含むことがあり(かつ/またはそれと通信していることがあり)、これは、限定はされないが、ローカルおよび/もしくはネットワークアクセス可能記憶装置を含むことがあり、かつ/または、限定はされないが、ディスクドライブ、ドライブアレイ、光記憶デバイス、プログラム可能、フラッシュ更新可能などであり得るランダムアクセスメモリ(「RAM」)および/もしくは読取り専用メモリ(「ROM」)などの、ソリッドステート記憶デバイスを含み得る。そのような記憶デバイスは、限定はされないが、様々なファイルシステム、データベース構造などを含む、任意の適切なデータストアを実装するように構成され得る。
【００３７】
コンピューティングデバイス100は、通信サブシステム130も含むことがあり、通信サブシステム130は、限定はされないが、モデム、ネットワークカード(ワイヤレスまたは有線)、赤外線通信デバイス、(Bluetooth(登録商標)デバイス、802.11デバイス、Wi-Fiデバイス、WiMAXデバイス、セルラー通信設備などの)ワイヤレス通信デバイスおよび/またはチップセットなどを含むことがある。通信サブシステム130は、ネットワーク、他のデバイス、および/または本明細書において説明される任意の他のデバイスとデータが交換されることを可能にし得る。コンピューティングデバイス(たとえば、100)は、上で説明されたように、RAMデバイスまたはROMデバイスを含み得る揮発性メモリ135をさらに含み得る。メモリ135は、オペレーティングシステム140およびアプリケーションソフトウェア(アプリケーション)145、ならびにオペレーティングシステム140およびアプリケーション145の実行をサポートするデータの形式で、プロセッサ実行可能命令を記憶し得る。コンピューティングデバイス100は、モバイルデバイスまたは非モバイルコンピューティングデバイスあってよく、ワイヤレスネットワーク接続および/または有線ネットワーク接続を有することがある。
【００３８】
コンピューティングデバイス100は、使い捨てまたは充電式の電池などの、プロセッサ110に結合された電源122を含み得る。充電式の電池は、コンピューティングデバイス100の外部の電源から充電電流を受け取るために、周辺デバイス接続ポートにも結合され得る。
【００３９】
コンピューティングデバイス100は、加速度計、気圧計、温度計などの、様々な外部条件センサを含み得る。そのような外部センサは、取得された画像およびビデオが画像から画像またはビデオからビデオへと変化するかどうか、およびどのように変化するかの決定において使用され得る情報を提供するために、コンピューティングデバイス100によって使用され得る。
【００４０】
図2は、様々な実施形態および実装形態に従った、任意のアプリケーションにおけるワーク処理の幾何学に基づく優先順位付けのための方法200の処理フロー図を示す。方法200は、コンピューティングデバイス(たとえば、100)で実施され、通信サブシステム(たとえば、130)およびメモリ(たとえば、125)と通信しているプロセッサ(たとえば、110)によって行われ得る。
【００４１】
ブロック202において、コンピューティングデバイスは、アプリケーション初期化シーケンス、アプリケーションを実行するための要求、アプリケーション設定の変更、パノラマつぎ合わせアプリケーションにおける新しいキー画像フレームの受信、またはビデオゲーム内の風景の変化などの、キーイベントを検出し得る。キーイベントは、コンピューティングデバイスのプロセッサによって検出され得る。キーイベントは、任意のアプリケーションプログラミングインターフェース(API)コールであり得る。また、キーイベントは、コンピューティングデバイスの通信サブシステム(たとえば、130)によって受信される、または仮想現実シミュレーション、ビデオゲーム、もしくは画像処理アプリケーションなどのソフトウェアアプリケーションのランタイムの間にプロセッサによって生成される、要求であり得る。
【００４２】
ブロック204において、コンピューティングデバイスは、キーイベントをN次元空間にマッピングし得る。いくつかの実装形態では、アプリケーションプログラマが、「N」がワーク領域の境界を定義するのに必要な要素の数を表すように、ソフトウェア開発の間に「N」を定義し得る。たとえば、2次元のグラフィクス処理アプリケーションでは、ワーク領域(たとえば、キャプチャされた画像の境界を区切られた領域)を定義するために、垂直および水平(x,y)座標しか必要ではないことがある。仮想現実ゲーム環境では、ワーク領域の境界を定義するために、垂直方向、水平方向、および深度または時間などの、3次元が必要であり得る。幾何学的なスケジューリングを受けるワークがAPIコールを含む実装形態は、処理要件、サイズ、実行時間長、メモリ割振りなどの、ワークの境界を定義するために任意の数の座標を必要とし得る。プロセッサは、N次元空間内でのキーイベントの場所を表すNタプルの各要素に対して、キーイベントの座標「値」を評価し得る。各キーイベントは、それと関連付けられる複数のワークアイテムを有し得るので、ワークアイテムと関連付けられる幾何学的に境界を区切られた領域のN次元空間への複数のマッピングを有し得る。
【００４３】
ワーク領域(ワークアイテムの境界を定義するために、または、あらゆる囲まれたワークアイテムを廃棄すべき領域を特定するために、または囲まれたワークアイテムに対する新しい削減重みを適用すべき領域を特定するために使用されるものなど)は、1つまたは複数の境界(たとえば、周縁、表面など)によって画定される、囲まれたエリア、体積などであり得る。各領域は、長方形、超平面、球面などを含み得る。長方形の領域は、一般にA1≦x1≦B1,A2≦x2≦B2,…AN≦xN≦BNとして定義することができ、ここで「A」および「B」はアプリケーションプログラマによって設定される境界定数である。超平面ワーク領域は、空間のある体積を閉じ込める複数の不等式によって定義され得る。そのような領域は、
【００４４】
【数１】
2019519015.tif 000003
【００４５】
によって定義することができ、「a」および「b」はi次の不等式と関連付けられる定数である。さらなる例では、球面ワーク領域は、
【００４６】
【数２】
2019519015.tif 000004
【００４７】
によって定義することができ、「a」および「b」はi次の不等式と関連付けられる定数である。
【００４８】
様々な実装形態において、N次元空間、ワーク領域境界、およびワーク領域形状はすべて、アプリケーションプログラマによって定義され、または実行の間にランダムに選択され洗練され得る。ワーク領域は、N次元空間内のイベントを表すNタプルを囲みそこに中心がある、空間的な体積であり得る。ワーク領域エリア/体積などは、すべてのワーク領域にわたって等しく、または同様であり得る。同様に、各ワーク領域は同じ幾何学的形状を有し得る。したがって、検出されたイベントと関連付けられるすべての実行可能なワークは、イベントのワークアイテムを記述する決定されたNタプルを使用してN次元空間にマッピングされることが可能であり、Nタプルと等しいまたは同様の形状および分布の関連するワーク領域境界を有し得る。たとえば、3次元空間は、3タプル(x,y,t)によって表される点の周りに中心がある球面の、長方形の、または多面体の形状のワーク領域を有し得る。いくつかの実装形態では、プログラマは、検出されたイベントのタイプに基づいてワーク領域の異なる形状およびサイズを指定し得る(すなわち、異なるカテゴリのイベントがワーク領域の異なる形状およびサイズと関連付けられ得る)。他の実装形態では、ワーク領域(すなわち、ワーク領域、廃棄領域および削減領域)の特性は、コンピューティングデバイスによってランダムに選択され、様々な実装形態の実行の間に調整され得る。
【００４９】
ブロック206において、コンピューティングデバイスのプロセッサは、第1のワーク領域(たとえば、新しく検出されたイベントのワーク領域)の境界をデフォルトの境界領域の境界と比較し得る。プロセッサは、アプリケーションに対して一般的な次元を有する長方形または球面の境界領域などの、デフォルトの境界領域をメモリ(たとえば、125)に記憶し得る。ワーク領域の形状およびサイズのように、デフォルトの境界ワーク領域の次元および境界は、アプリケーションプログラマによって決定され得る。プロセッサは、このデフォルトの境界領域を第1のワーク領域と比較して、第1のワーク領域のいずれかの部分がデフォルトの境界領域の境界の外にあるかどうかを決定し得る。デフォルトの境界領域の外にある第1のワーク領域のあらゆる部分が、廃棄領域として分類され得る。同様に、プロセッサ(たとえば、110)は、1つまたは複数の削減領域を、第1のワーク領域およびデフォルトの境界領域内にあるが、削減領域内のワーク領域と関連付けられるワークアイテムがワーク処理の完結の前に廃棄される可能性が高くなるような空間的関係を有する領域として、決定し得る。
【００５０】
廃棄領域は、幾何学的スケジューラのランタイム環境(たとえば、幾何学的スケジューリングランタイム環境522)によって維持されるメモリ(たとえば、125)に記憶されているデータ構造内の廃棄領域と重複する、様々なワーク領域の中の、それにリンクされる、またはそれと関連付けられる、メモリに記憶され得る。ワーキング境界領域がどのように更新されるかに応じて、廃棄領域と重複するワーク領域は、処理ワークリスト(すなわち、実行ワークリスト)から取り消され得る。
【００５１】
ブロック208において、コンピューティングデバイス(たとえば、100)のプロセッサ(110)は、第1のワーク領域内の複数のより小さいワーク領域を特定し得る。より小さいワーク領域は、サブセクションまたは断片へのワーク領域の分割につながる、長方形、超平面、立方体、または任意の他の形状であり得る。様々な実装形態において、より小さいワーク領域は、中心領域および複数の外側領域を含み得る。中心領域は大半のエリアまたは体積を占有することがあり、それは、各ワーク領域の中心領域が、検出されたイベントと関連付けられるワークの処理を産生する際に最終的に保持される可能性が最も高いからである。外側領域は、中心領域から外向きに延びることがあり、第1のワーク領域の幾何学的特性に適合するように、次元が減少し、または形状/次元が完全に変化することがある。複数のワーク領域への画像分割の例が図3に示されている。
【００５２】
ブロック210において、プロセッサは、第1のワーク領域の特定されたより小さいワーク領域の各々に対する取消し尤度を決定(たとえば、計算)し得る。取消し尤度は、第1のワーク領域の中心からの距離、または各々のより小さいワーク領域の中心から廃棄領域の境界までの距離のうちの、1つまたは複数に基づいて計算され得る。したがって、取消し尤度は、関連するワークが削減される尤度が高いような、廃棄領域の十分近くにある、または第1のワーク領域の中心から十分離れているより小さいワーク領域に対しては、高いことがある。様々な実施形態において、取消し尤度は、アプリケーションプログラマによって指示されるような他の空間的関係によって決定され得る。たとえば、特定のアプリケーションの特性は、ワーク領域内で斜向かいにある削減領域へのより高い取消し尤度の割当てを、または取消し尤度が異なるワーク領域の間で重複する削減領域の数に基づいて決定され得ることを、保証し得る。取消し尤度の計算は、アプリケーション固有であることがあり、アプリケーションごとに異なることがある。
【００５３】
ブロック212において、プロセッサは、計算された取消し尤度に基づいて、特定されたより小さいワーク領域の各々への削減重みを決定し得る。取消し尤度は、近似値であってよく、保持または廃棄の確率の正確な計算を表す必要はない。削減重みは、ワーク領域が廃棄または保持される尤度の英数字による表現であり得る。たとえば、優先の順序を示すために、文字A〜Zが使用され得る。同様に、数字のランキングがより小さいワーク領域に割り当てられ得る。したがって、削減重みは、廃棄または保持の尤度、ならびに関連するより小さいワーク領域の実行優先順位の両方を示すために生成され得る。
【００５４】
ブロック214において、プロセッサは、ワーク領域の各々と関連付けられるワークアイテムを実行ワークへと追加し、または別様に挿入し得る。各ワーク領域は、領域と関連付けられる複数のワークアイテムを有し得る。ワークアイテムは、画像のチャンク、オーディオファイルのスニペット、プリントジョブの処理、コンピューティングデバイス(たとえば、100)の1つまたは複数のプロセッサ(たとえば、110)のリソースを必要とする他のタスクなどの、処理ワークの「ブロック」であり得る。実行ワークリスト内のワークアイテムの順序は、各ワーク領域に割り当てられる削減重みに基づき得る。すなわち、各ワークアイテムは、それが属するワーク領域の削減重みを有するものと見なされ得る。より優先順位が高いワークアイテム(すなわち、廃棄される、取り消される、または削減される可能性が最も低いワークアイテム)が、実行ワークリスト内で最初に配置され得る。いくつかの実装形態では、実行ワークリストは、複数のプロセッサにより利用されることがあり、または単一のプロセッサにより利用されることがある。マルチプロセッサの実装形態では、各プロセッサは、それと関連付けられる別個の実行ワークリストを有し得る。
【００５５】
ブロック216において、プロセッサは、別の(すなわち、第2のまたは後続の)イベントの発生または開始を検出し得る。第2のおよび後続のイベントは、ブロック202を参照して論じられたものと同様の方式で検出され得る。
【００５６】
ブロック218において、プロセッサは、特徴的なNタプルを決定し、所定の形状および次元を有する関連するワーク領域を生成することによって、第2のまたは後続のイベントをN次元空間にマッピングし得る。第2のイベントは、ブロック204を参照して論じられたものと同様の方式でマッピングされ得る。
【００５７】
ブロック220において、プロセッサは、様々なワーク領域の廃棄領域および削減領域を更新し得る。この動作において、プロセッサは、既存の廃棄領域および削減領域のいずれかの部分が、任意のより小さいワーク領域である第1のワーク領域と、第2のまたは後続のワーク領域の両方と共通であるかどうかを決定し得る。第2のワーク領域がN次元空間内の第1のワーク領域と正確に軸方向に揃っていない場合、それぞれのワーク領域の境界の間にオフセットが存在し得る。任意の廃棄領域および削減領域の次元が次いで、アプリケーション固有の更新規則に従って修正され得る。更新された廃棄領域および削減領域は、新しいイベントが検出され、新しいイベントのワーク領域が廃棄領域および削減領域の境界の現在のインスタンスと、または代替的にはすべての以前のワーク領域の境界と比較されるたびに、更新され得る。したがって、更新された廃棄領域および削減領域は、任意の所与の時間において、すべてのマッピングされたワーク領域の共通の共有される領域の部分と重複し得る。
【００５８】
ブロック222において、プロセッサは、更新された廃棄領域および削減領域を第2の画像と比較することができ、任意の重複する領域の半分(たとえば、第2のワーク領域と関連付けられる部分)を廃棄領域として分類することができる。
【００５９】
ブロック224において、プロセッサは、実行ワークリスト内の任意のアクティブなワークアイテムが、第2のワーク領域の廃棄領域と重複するワーク領域と関連付けられるかどうかを決定し得る。各々の新しいイベントに対して、新しいイベントの廃棄領域は、今度は廃棄領域として分類されるワーク領域と関連付けられる任意のワークアイテムの処理を遅らせるために、または削除するために、既存のワークアイテムと比較され得る。プロセッサは、この決定を、新しく検出されたイベントの廃棄領域に対する以前に検出されたイベントのワーク領域の単純な比較によって果たし得る。
【００６０】
ブロック226において、プロセッサは、第2のワーク領域または後続のワーク領域の廃棄領域と重複する、ワーク領域と関連付けられるあらゆるワークアイテムを取り消し得る。ワークを取り消すために、プロセッサ(たとえば、110)は単に、ワークリストおよびあらゆる関連する処理キューからワークアイテムを削除し得る。
【００６１】
プロセッサは再び、ブロック208においてワーク領域を特定し、ブロック210において各ワーク領域に対する取消し尤度を計算し、ブロック212において削減重みを各ワーク領域に割り当て得る。
【００６２】
ブロック214において、プロセッサは、第1のワーク領域と第2のワーク領域の両方の削減重みに基づいて、ワーク領域を実行ワークリストに追加し得る。したがって、第2のワーク領域のワークアイテムは、実行ワークリストへと散りばめられることが可能であり、第1のワーク領域のワークアイテムと優先順位を共有し、それより優先順位が低く、またはそれより優先順位が高いことがある。幾何学に基づくワークアイテムの取得および優先順位付けは、すべてのイベントが検出され、すべてのワークアイテムがスケジューリングされるまで続き得る。
【００６３】
図3は、N次元の空間におけるイベントマッピング300の例を示す。示されるイベントマッピング300において、コンピューティングデバイス(たとえば、コンピューティングデバイス(たとえば、100))は、水平(たとえば、x)、垂直(たとえば、y)、および時間(たとえば、t)の座標を含む、特徴的な三つ組に基づいて、第1のイベントを第1のワーク領域304にマッピングしている。第1のワーク領域304は、軽量な線の境界によって定義される長方形の形状を有する。デフォルトの境界領域302は、それぞれの境界の空間的関係を比較するために、第1のワーク領域に重畳される。デフォルトの境界領域内にある第1のワーク領域304のすべての部分が、初期化されたワーキング境界領域に含まれ、これは後続のワーク領域と比較され得る。デフォルトの境界領域302の下側の境界(すなわち、最も下の表面/平面)の下にある第1のワーク領域304の部分が、廃棄領域306として分類され得る。新しいイベントが検出されるにつれて、新しいワーク領域を3次元空間にマッピングすることができ、後続の比較を通じて重複および除外の新しいエリアを決定することができる。
【００６４】
様々な実装形態において、第1のワーク領域の数学的な中心は、ワークイベントを特徴付けるNタプルであり得る。より小さなワーク領域(図示されず)が、取消し尤度に基づいて、第1のワーク領域304内で定義され、削減重みを割り当てられ得る。図2を参照して論じられるように、取消し尤度は、第1のワーク領域304の中心からの距離、または第1のワーク領域のある領域から廃棄領域306の境界までの距離であり得る。距離は、p-ノルムまたはマハラノビス距離などの、既知の方法を使用して計算され得る。いくつかの実装形態では、様々なワーク領域はより大きいクラスタ内のサブクラスタと類似していることがあり、クラスタ重み付け技法が取消し尤度を計算するために適用されることがある。
【００６５】
方法200の説明のための例は、画像処理、パノラマ生成のための画像のつなぎ合わせ、ゲームエンジンの動作、3次元ボクセル処理、マシンビジョン処理、および仮想現実アプリケーションを含む。図4〜図11は、パノラマ画像生成および仮想現実シーン管理のために、特定のアプリケーションに幾何学的なワークスケジューリングのための方法200を適用することを開示する。様々な実施形態および実装形態の適用の範囲は、これらの活動に限定されず、例は説明を目的に与えられる。
【００６６】
図4は、パノラマをレンダリングするための画像処理の従来の方法を示す。示される従来の画像つなぎ合わせ技法400では、コンピューティングデバイス(たとえば、コンピューティングデバイス(たとえば、100))は、可変の程度の垂直または水平の場所のずれを有する複数の画像フレーム402〜410を受信する。コンピューティングデバイスは、画像処理動作を開始する前に、すべての画像フレームが受信されるまで待機し得る。コンピューティングデバイス(たとえば、100)は、端から端の方式でフレーム402〜410を揃え、次いで、最大の中心エリアが得られるまでフレーム402〜410の場所を調整し得る。そのような技法では、コンピューティングデバイス(たとえば、100)は、すべてのフレーム402〜410に対する最大の共有される垂直距離を囲むグローバルに同期された境界ボックスを描き得る。コンピューティングデバイス(たとえば、100)は、フレームの余剰領域、たとえば、グローバルに同期された境界ボックス内にない各フレームの部分を削減することができる。したがって、コンピューティングデバイスは、削減されたフレーム412〜420から完結したパノラマを作成することの一部として、削減すべき領域を決定する前に、各画像フレーム402〜410を受信し、それを完全に処理する。そのような技法は、パノラマつぎ合わせの計算の開始を大きく遅らせ、利用可能なリソースの非効率な使用につながり、このとき、リソースはフレームのすべてが到着するまで最初はアイドリング状態で残され、次いでリソースは、後続のつぎ合わせ時間を最小化するための試みにおいて最大限に負荷を課され、これらのすべてが視覚的な遅延の発生につながり得る。
【００６７】
図5は、画像処理の別の従来の方法の図を示す。図5に示される従来の画像つなぎ合わせ技法500では、コンピューティングデバイス(たとえば、コンピューティングデバイス(たとえば、100))は、可変の程度の垂直または水平の場所のずれを有する複数の画像フレーム502〜510を受信する。コンピューティングデバイスは、フレームがキャプチャされるにつれて、画像フレーム502〜510の部分を取り消し、または削減することを始め得る。新しいフレームがキャプチャされるとき、新しいフレームは、削除される以前のフレームまたは突き出した部分と比較される。たとえば、図5において、画像フレーム512は、すべての受信されたフレームによって共有される中心共有領域と、灰色および黒で示されている2つの突き出した領域とを含む。第2のフレームを受信すると、コンピューティングデバイス(たとえば、100)は、画像フレーム512を産生するために、画像フレームの灰色領域からの削除を開始し得る。同様に、次の画像フレームを受信すると、コンピューティングデバイス(たとえば、100)は、フレーム516〜520が処理され最終的な画像が作成されるまで、フレーム514などを作成するために、以前のフレームから黒い影付きの領域を除去することを開始し得る。そのような技法は前処理動作を組み込むことによって処理速度を上げるが、これらの技法は、最終的に廃棄される画像フレームの領域の冗長な処理が原因の処理リソースの消費を大きくは減らさない。
【００６８】
図6は、様々な実施形態および実装形態による、画像フレームおよび得られる実行ワークリストの幾何学的な分割のブロック図を示す。様々な実装形態は、得られた画像フレームをコンピューティングデバイス(たとえば、100)のプロセッサ(たとえば、110)によって複数のワーク領域に分割することを含み得る。様々な実装形態において、画像フレーム600は、複数のワーク領域602〜610へと分割され得る。各ワーク領域602〜610は、特定のワーク領域に対する取消し尤度を表す削減重み(たとえば、a-e)を割り当てられ得る。様々な実装形態において、コンピューティングデバイスのプロセッサは、それぞれの削減重みに基づく順序で、ワーク領域602〜610を実行ワークリストに追加し、または別様に挿入し得る。
【００６９】
様々な実装形態において、ワーク領域602〜610は、各々の新しく得られた画像フレーム600に対して特定され得る。ワーク領域は、デフォルトで長方形であることがあり、また、パラレラポイド、超平面、立方体、球、円、多角形、多面体なども含み得る。
【００７０】
各画像フレーム600はNタプル(x1, x2, …, xN)として表現することができ、ここでNはワーク領域602〜610の数である。実行中のアプリケーションが画像処理アプリケーションである実装形態では、ワーク領域602〜610は、境界線によって描かれる画像フレーム600の領域として容易に視覚化され得る。しかしながら、処理のためのワークアイテムがデータまたはAPIコールである実装形態では、ワーク領域はn次元クラスタであり得る。
【００７１】
様々な実施形態において、コンピューティングデバイス(たとえば、100)のプロセッサ(たとえば、110)は、任意のアクティブなワークアイテム(すなわち、処理されるのを待機しているワーク領域)が現在のワーキング画像フレーム600に対する新しく特定されたワーク領域602〜610と重複するかどうかを決定し得る。そのような領域は、様々な数学的表現によって表され得る。たとえば、長方形の領域は、一般にA1≦x1≦B1,A2≦x2≦B2,…AN≦xN≦BNとして定義することができ、ここで「A」および「B」はアプリケーションプログラマによって設定される境界定数である。超平面ワーク領域は、空間のある体積を閉じ込める複数の不等式によって定義され得る。そのような領域は、
【００７２】
【数３】
2019519015.tif 000005
【００７３】
によって定義することができ、「a」および「b」はi次の不等式と関連付けられる定数である。さらなる例では、球面ワーク領域は、
【００７４】
【数４】
2019519015.tif 000006
【００７５】
によって定義することができ、「a」および「b」はi次の不等式と関連付けられる定数である。
【００７６】
コンピューティングデバイスのプロセッサは、ワーク領域602〜610を分析し、各領域に対する取消し尤度を計算し得る。各取消し尤度は、特定のワーク領域601〜610が廃棄される尤度、または代替的に、最終的な産物(たとえば、パノラマまたは仮想現実レンダリング)を生成する際に使用するために保持される尤度であり得る。領域Rの取消し尤度は、削減重みLによって表現することができ、削減重みは、領域Rが最終的な産物の処理のために廃棄または保持される尤度の英数字によるインジケータであり得る。
【００７７】
ワーク領域の数および関係は、リンクされるリストもしくは空間的に区分される木、Bounding Volume Hierarchy(BVH)、四分木、八分木、またはKd-木などの、データ構造において追跡され得る。たとえば、ワーク領域602〜610は、N次元空間内でのそれらのマッピングされる場所に基づいて一番上のレベルの木ノードにおいて連続的に記憶され得るが、2番目のレベルの木ノードは、N次元空間内の異なる場所を有するワーク領域602〜610の集団を含む。3番目のレベルの木ノードはさらに、動きの方向、画像フレーム600の中心からの距離、または他の場所/次元の基準によって集団を分割し得る。そのような木データ構造の使用は、対数ベースのルックアップ時間と、取消し(または保持)尤度が更新され領域が廃棄されるにつれて、記憶されているデータを高速に再構築することとを可能にし得る。さらなる例では、ワーク領域608が次の画像フレームのいずれの領域とも重複しないと決定される場合、ワーク領域608は廃棄され得る。したがって、領域(すなわち、領域「d」)に関するデータは木から除去されてよく、関連するポインタは新しいノードに向け直される。
【００７８】
いくつかの実装形態では、削減重みa〜eを有するワーク領域602〜610は一番上のレベルの木ノードにおいて連続的に記憶され得るが、2番目のレベルの木ノードは、同様のまたは等価な削減重みを有するワーク領域602〜610の集団を含み、たとえば、aは第1のノードに含まれることがあり、bおよびdは第2のノードに含まれることがあり、cおよびeは第3のノードに含まれることがある。3番目のレベルの木ノードはさらに、動きの方向、画像フレーム600の中心からの距離、または他の基準によって集団を分割し得る。
【００７９】
様々な実装形態において、コンピューティングデバイスのプロセッサは、1つまたは複数の画像フレーム600のワーク領域602〜610を実行ワークリストに追加し得る。そのような実行ワークリストは、反復空間、または他の処理キューであり得る。いくつかの実装形態では、実行ワークリストは、複数の処理装置(たとえば、CPU、GPU、および/またはDSP)により利用される単一の処理キューであり得る。他の実装形態では、実行ワークリストは、ワークアイテムが実行ヒープの一番上に到達するにつれてワークアイテムを優先順位付けてアイテムを処理装置に渡す、分類キューであり得る。いくつかの実装形態では、実行ワークリストは、最高の優先順位のアイテムが実行のために最初に除去される、優先ヒープとして実装され得る。様々な実装形態において、優先順位付けは、削減尤度の降順で実行されてよく、すなわち、最も削減尤度が低いアイテムが最初に実行のために除去され得る。いくつかの実装形態では、ワークアイテムの幾何学的形状などの追加の態様を、優先順位に対して考慮することができる。
【００８０】
図6に示されるように、ワーク領域602〜610と関連付けられるワークアイテムは、取り消されるべき最低の尤度を有する(すなわち、最も使用される可能性が高い)ワークアイテムが、実行のために最初にヒープから取り除かれるような方式で、実行ワークリストに追加または挿入され得る。逆に、高い取消しの尤度と関連付けられるワークアイテムは、実行ワークリストの終わりの近くに配置され得るので、これらのアイテムの処理を遅らせる。取り消される可能性が高いワークアイテムの処理を、それらをワークリストの一番下に置くことで遅らせることは、ワークアイテムが処理される前に廃棄される尤度を上げ、これにより、不必要であることが判明する処理をなくす。様々な実装形態において、1つまたは複数のプロセッサ(たとえば、110)は、画像フレームがまだキャプチャされている間に、ビデオがまだ記録されている間に、またはAPIコールがまだ行われている間に、ワークアイテムの実行を開始し得る。したがって、様々な実装形態は、無駄なワークを最小限にするためにアプリケーション固有の知識を使用しながら、事前の(upfront)並行性を最大化し、決定依存性を断つために、ワークを推測で実行し得る。
【００８１】
図7は、様々な実装形態による、幾何学に基づくワークの優先順位付け処理のランタイム環境を通じたワークフローのブロック図を示す。一般環境720とアプリケーション固有の動作710、712、714の両方を有する、幾何学的なワークスケジューリング計画700が示されている。様々な実施形態は、コンピューティングデバイス(たとえば、100)において、画像フレーム、ビデオセグメント、アプリケーションAPIコールのセット、または1つまたは複数のプロセッサ(たとえば、110)を介して実行されるべき他の処理ワークを受信すること、または別様に取得することを含み得る。
【００８２】
様々な実装形態では、一般環境720は、非アプリケーション固有動作を制御および維持することができ、特定されたワーク領域(たとえば、ワーク領域402〜410)についての情報を追跡するデータ構造を維持することができる。図4に関して論じられるように、一般環境720は、たとえば、特定されたワーク領域を追跡するデータ構造を維持する、ランタイム幾何学的スケジューリング環境722を含み得る。点線のボックス730および732の各々が、取得された画像フレーム、ビデオセグメント、アプリケーションコールのグループ、または他の処理ワークセットの視覚的な表現を提供する。各々の点線のボックス730、732は、いくつかの構成要素ワーク領域およびそれらの関連する削減重みを含み得る。様々な実施形態は、空間的に区分された木または同様のデータ構造にこの情報を記憶することができる。幾何学的スケジューリングランタイム環境は、削減重みが修正されてワークアイテムが完成または廃棄されるにつれて、これらのデータ構造を維持して更新することができる。様々な実装形態において、一般環境720はスケジューリングループ724も管理することができ、これは、1つまたは複数のプロセッサ(たとえば、110)による実行のために個々のワークアイテムをスケジューリングする。
【００８３】
ブロック710において、コンピューティングデバイス(たとえば、100)のプロセッサ(たとえば、110)は、新しいワークアイテムを生成し得る。図4および図6に関して論じられるように、プロセッサ(たとえば、110)は、画像、ビデオ、APIコールのグループ、または他の処理ワークセットを取得すること、境界形状(たとえば、バウンディングボックス)を取得されたアイテムに適用して境界形状内にあたるワーク領域を特定すること、各ワーク領域に対する取消し尤度を決定すること、および取消し尤度に基づいて各ワーク領域に削減重みを割り当てることによって、新しいワークアイテムを生成し得る。削減重みが割り当てられている得られたワーク領域は、ワークアイテムと見なされ得る。各ワークアイテムはさらに、N次元空間内のワークアイテムの中心(すなわち、関連するワーク領域の中心)、ワークアイテムの次元(すなわち、関連するワーク領域の次元)という情報を含み得る。ワークアイテムは任意選択で、特定の処理装置(たとえば、GPU)上でのワークアイテムの実行と関連付けられる性能乗数、および特定の処理装置上での実行に基づく電力効率の増大を示す電力乗数に関する情報を含み得る。さらに、ワークアイテムは、廃棄要求がワークアイテムに対して行われる場合に何をすべきかを一般環境720に命令する、アプリケーション固有のコールバック関数(たとえば、廃棄動作)を含み得る。
【００８４】
親ソフトウェアアプリケーションのランタイムの間の任意の時間において、コンピューティングデバイス(たとえば、100)のプロセッサ(たとえば、110)は、新しいワークアイテム710を生成することができ、+ワークコールなどのAPIコールを一般環境に対して行うことができる。幾何学的スケジューリングランタイム環境は、新しいワークアイテムを受信することができ、親画像、ビデオセグメント、APIコールグループ、または他の処理ワークセットに属する他のワークアイテムと関連付けて新しいワークアイテムを記憶することができる。様々な実装形態において、幾何学的スケジューリングランタイム環境はさらに、同様のワークアイテムの効率的な実行のために異なる処理装置に送信され得る処理グループを形成するために、様々な画像、ビデオセグメント、APIコールグループ、または他の処理ワークセットにわたる共通の要素を関する情報を保持して追跡することができる。
【００８５】
親ソフトウェアアプリケーションのランタイムの間の任意の時間において、コンピューティングデバイス(たとえば、100)のプロセッサ(たとえば、110)は、1つまたは複数の廃棄領域712と重複するワークアイテムを廃棄し得る。図7を参照して論じられるように、コンピューティングデバイス(たとえば、100)のプロセッサ(たとえば、110)は、最終的な産物の作成に不要であると見なされる、画像、ビデオ、APIコールグループなどの領域を、廃棄し、取り消し、または削減し得る。コンピューティングデバイスは、受信された画像フレームともはや重複しない任意のワーク領域(たとえば、402〜410における突き出しているワーク領域)を廃棄し得る。
【００８６】
不要なワーク領域と関連付けられるワークアイテムを廃棄することは、手動でまたは自動的に行われ得る。手動の廃棄を利用する実装形態は、アプリケーション側で実行される、またはユーザコードにより別様に管理される、廃棄機能を含む。そのような実装形態では、廃棄コールが親ソフトウェアアプリケーションによって一般環境720に対して行われた後で、返された応答はワークアイテムの現在のステータス(たとえば、未実行、実行中、完了)を含み得る。ワークアイテムの生成に際してワークアイテムとともにパッケージングされ得るアプリケーション「コールバック」関数が、すでに完了したあらゆるワークを「元通りにする」ために実行され得る。たとえば、すでに処理が完了している画像の部分が廃棄され、それらの画素がコンピューティングデバイスのメモリから削除される。このようにして、ソフトウェアアプリケーションは、廃棄されたワークアイテムが扱われるべき方法を記述し得る。この手法は、ソフトウェアアプリケーションの処理および電力消費の需要の知識に基づいてどのように最良に処理リソースを利用するかについての判断を、アプリケーション開発者が行うことを可能にし得る。たとえば、ある特定のアプリケーションは、ワークアイテムが未実行である場合にのみそのワークアイテムを取り消すように、かつすでに実行中のまたは完了したワークアイテムはそのままにするように、プロセッサ(たとえば、110)に命令する手動の廃棄動作を含み得る。逆に、他のソフトウェアアプリケーションは、多くの必要とされる処理リソースを節約し、メモリからあらゆる完了した廃棄ワークアイテムを直ちに削除するために、あらゆる実行中のワークを直ちに停止するようにコンピューティングデバイスに命令することがある。
【００８７】
様々な実装形態において、自動的な廃棄は、実行中のソフトウェアアプリケーションの知識が一般環境720に知られているときに実施され得る。たとえば、画像およびビデオ処理アプリケーションは、冗長なワーク領域の自動的な廃棄によく適していることがあり、それは、コンピューティングデバイス(たとえば、100)のプロセッサ(たとえば、110)が処理ワーク(すなわち、画像またはビデオ)のタイプおよび内容を容易に特定できるからである。さらに、コンピューティングデバイス(たとえば、100)のプロセッサ(たとえば、110)は、画像またはビデオの複数のセグメントにまたがる領域的な重複があるかどうかを迅速に決定し得る。図7を参照して論じられる実装形態は、自動廃棄機能を含むがそれに限定されない。
【００８８】
ブロック714において、コンピューティングデバイス(たとえば、100)のプロセッサ(110)は、アクティブなワークアイテムと関連付けられる削減重みを更新し得る。新しいワークアイテムが生成されるとき、関連する画像、ビデオセグメント、APIコールグループなどによって共有される共通の次元を定義するワーキング境界形状(たとえば、バウンディングボックス)の次元および場所が、調整され得る。したがって、以前はワーキング境界形状内にあった画像またはビデオのセグメントの部分が、もはやワーキング境界形状内にないことがある。逆に、以前は廃棄領域として示されていた画像またはビデオの領域が、今ではワーキング境界形状の周縁の中にあることがある。別の例では、ワーキング境界ボックスの外縁に沿って以前は位置していたワーク領域が、今ではワーキング境界ボックスの中心の中にあることがあり、それにより、そのワーク領域が廃棄される尤度が低下する。様々な実装形態において、取消し尤度の再評価がソフトウェアアプリケーション側で行われることがあり、関連するAPIコールが、空間的に区分された木/データ構造内のデータを更新するために一般環境720に対して行われることがある。
【００８９】
様々な実装形態において、コンピューティングデバイス(たとえば、100)のプロセッサ(たとえば、110)は、ワークアイテムの処理を実行するためにスケジューリングループ724を実施し得る。プロセッサは、ランタイム幾何学的スケジューリング環境722によって管理される実行ヒープを参照し、ヒープから「最も取り消される可能性の低い」ワークアイテムを抜くことができ、たとえば、プロセッサは実行ワークリストの中の最初のワークアイテムを選択することができる。図7を参照して論じられるように、プロセッサ(たとえば、110)は、管理プロセッサ上で単一のワークアイテムを実行することができ、または、複数の処理装置(たとえば、CPU、GPU、およびDSP)にわたる実行のためにヒープから1つまたは複数のワークアイテムを抜くことができる。クロスプロセッサ実行を利用する実装形態では、各処理装置に対するワークのキューイングについての決定は、各ワークアイテムのワークスコアに基づき得る。ワークスコアは、特定の処理装置による実行に対する各ワークアイテムの適格性を示し得る。ワークアイテムが完了すると、そのステータスが、ワークアイテム処理が完了したことを示すために、ランタイム幾何学的スケジューリング環境722により維持されるデータ構造内で更新され得る。
【００９０】
図8は、様々な実施形態および実相形態による、キャプチャされた画像フレームの動きの追跡800のブロック図を示す。様々な実装形態は、コンピューティングデバイス(たとえば、100)のプロセッサ(たとえば、110)によって、取得された画像フレームの動きの方向を追跡することを含み得る。様々な実装形態において、コンピューティングデバイスは、加速度計または場所の変化を検知するように構成される他のセンサを有し得る。画像キャプチャデバイス(たとえば、カメラ)が動くにつれて、取得された画像フレーム802〜810内に示される要素が、互いに対してシフトし得る。たとえば、ユーザがカメラで写真を撮りカメラを放物線状の軌跡で動かすと、キャプチャされた画像フレームは図8に示されるように揃えられ得る。
【００９１】
様々な実装形態において、各々の新しい画像フレーム802〜810がキャプチャされるにつれて、画像フレームの共通の共有される次元を定義するワーキング境界形状(たとえば、バウンディングボックス)が修正される(すなわち、更新される)。カメラが上の方向に動くにつれて、ワーキング境界形状の周縁も上に動き、最高の画像(たとえば、画像フレーム806)の下端の下に位置する領域が削除される。したがって、最高の画像フレームの下端の下に位置するワーク領域は、以前はワーキング境界形状の周縁の中に含まれていた可能性があるが、今では周縁の外にある可能性があるので、廃棄領域として再分類される可能性がある。同様に、画像フレーム808および810が取得され分析されるにつれて、ワーキング境界形状の上側境界は、最低の画像フレーム(たとえば、画像フレーム810)の上端まで下げられ得る。
【００９２】
図9は、様々な実施形態および実装形態に従って、画像処理アプリケーションにおけるワーク処理の幾何学に基づく優先順位付けのための方法900の処理フロー図を示す。方法900は、コンピューティングデバイス(たとえば、100)で実施され、通信サブシステム(たとえば、130)およびメモリ(たとえば、125)と通信しているプロセッサ(たとえば、110)によって行われ得る。
【００９３】
ブロック902において、コンピューティングデバイスは第1の画像を取得し得る。第1の画像は、コンピューティングデバイスのプロセッサと通信しているカメラを介して取得され得る。第1の画像はさらに、レンダリングされた画像であることがあり、コンピューティングデバイスの通信サブシステム(たとえば、130)によって取得され、または仮想現実シミュレーションなどのソフトウェアアプリケーションのランタイムの間にプロセッサによって生成されることがある。
【００９４】
ブロック904において、コンピューティングデバイスのプロセッサは、第1の画像に境界形状を重畳し得る。プロセッサは、パノラマ画像に対して一般的な次元を有する長方形のボックス境界などの、デフォルトの境界形状をメモリ(たとえば、125)に記憶し得る。プロセッサは、第1の画像の任意の部分がデフォルトの境界形状の周縁の外にあるかどうかを決定するために、取得された第1の画像にこのデフォルトの境界形状を重畳し得る。デフォルトの境界形状の外にある第1の画像のあらゆる部分が、廃棄領域として分類され得る。廃棄領域は、幾何学的スケジューラのランタイム環境(たとえば、ランタイム幾何学的スケジューリング環境)によって維持されるメモリ(たとえば、125)に記憶されているデータ構造内の画像フレームに関連して記憶され得る。図5および図6を参照して論じられるように、廃棄領域は、境界形状がどのように更新されるかに応じて、処理を取り消され得る。
【００９５】
ブロック906において、コンピューティングデバイス(たとえば、100)のプロセッサ(110)は、デフォルト境界ボックス内の複数のワーク領域を特定し得る。ワーク領域は、断片への画像の分割につながる、長方形、超平面、立方体、または任意の他の形状であり得る。様々な実装形態において、ワーク領域は、中心領域および複数の外側領域を含み得る。中心領域は大半のエリアまたは体積を占有することがあり、それは、各画像の中心領域が、最終的なパノラマ画像を作成する際に保持される可能性が最も高いからである。外側領域は、中心領域から外向きに延びることがあり、取得された画像の幾何学的特性に適合するように、次元が減少し、または形状/次元が完全に変化することがある。複数のワーク領域への画像分割の例が図4に示されている。
【００９６】
ブロック908において、プロセッサは、特定されたワーク領域の各々に対する取消し尤度を計算し得る。取消し尤度は、第1の画像の中心からの距離、第1の画像に重畳されるときの境界形状の中心からの距離、または画像キャプチャデバイスの動きの予想される方向のうちの1つまたは複数に基づいて計算され得る。取消し尤度は、近似値であってよく、保持または廃棄の確率の正確な計算を表す必要はない。
【００９７】
仮想現実アプリケーションを含む実装形態では、取消し尤度は、各ワーク領域に割り当てられる時間長に基づき得る。この時間長は、仮想現実の視野がワーク領域と重複することが予想されない時間を表し得る。時間長が長い場合、仮想現実ビューポートがその時間長の期間の満了の前に領域と重複する可能性が低いので、取消し尤度は高いことがある。
【００９８】
ブロック910において、プロセッサは、計算された取消し尤度に基づいて、特定されたワーク領域の各々に削減重みを割り当て得る。削減重みは、ワーク領域が廃棄または保持される尤度の英数字による表現であり得る。たとえば、優先の順序を示すために、文字A〜Zが使用され得る。同様に、数字のランキングがワーク領域に割り当てられ得る。したがって、削減重みは、廃棄または保持の尤度、ならびに関連するワーク領域の実行優先順位の両方を示すために生成され得る。
【００９９】
ブロック912において、プロセッサは、ワークアイテムとしてワーク領域を実行ワークリストへと追加し、または別様に挿入し得る。実行ワークリスト内のワークアイテムの順序は、各ワーク領域に割り当てられる削減重みに基づき得る。より優先順位が高いワークアイテム(すなわち、廃棄される、取り消される、または削減される可能性が最も低いワークアイテム)が、実行ワークリスト内で最初に配置され得る。いくつかの実装形態では、実行ワークリストは、複数のプロセッサにより利用されることがあり、または単一のプロセッサにより利用されることがある。マルチプロセッサの実装形態では、各プロセッサは、それと関連付けられる別個の実行ワークリストを有し得る。
【０１００】
ブロック914において、プロセッサは、第2の画像または追加の画像(たとえば、第3の画像、第4の画像、第5の画像など)を取得し得る。第2の画像は、ブロック902を参照して論じられたものと同様の方式で取得され得る。
【０１０１】
ブロック916において、プロセッサはワーキング境界形状を更新し得る。すなわち、プロセッサは、ワーキング境界形状が第1の画像と第2の画像の両方に適合するかどうかを決定し得る。第2の画像が第1の画像と正確に軸方向に揃っていない場合、画像フレーム間でオフセットが存在し得る。ワーキング境界ボックスの次元は次いで、境界形状の周縁の中に空の空間がないように修正され得る。この修正された境界形状は、更新されたワーキング境界形状と呼ばれ得る。新しい画像が取得されるたびに、更新されたワーキング境界形状は再び更新され得る。したがって、更新されたワーキング境界形状は、任意の所与の時間において、すべての取得された画像の共通の共有される領域と重複し得る。更新されたワーキング境界形状の外にある画像のあらゆる部分が、廃棄領域として分類され得る。
【０１０２】
ブロック918において、プロセッサは、第2の画像に更新されたワーキング境界形状を重畳することができ、廃棄領域に属するものとして更新されたワーキング境界形状の外にある領域を分類することができる。したがって、廃棄領域のサイズは、新しい画像が取得されるたびに増大または減少し得る。
【０１０３】
ブロック920において、プロセッサは、実行ワークリスト内の任意のアクティブなワークアイテムが、廃棄領域と重複するワーク領域と関連付けられるかどうかを決定し得る。取得された各々の新しい画像に対して、廃棄領域は、今では廃棄領域として分類される領域と重複するあらゆるワークアイテムの処理を遅らせるために、または削除するために、ワークアイテムと比較され得る。プロセッサは、この決定を、廃棄領域に対するワーク領域の単純な比較によって果たし得る。ブロック922において、プロセッサは廃棄領域と重複するあらゆるワークアイテムを取り消し得る。
【０１０４】
プロセッサは再び、ブロック906においてワーク領域を特定し、ブロック908において各ワーク領域に対する取消し尤度を計算し、ブロック910において削減重みを各ワーク領域に割り当て得る。
【０１０５】
ブロック912において、プロセッサは、第1の画像と第2の画像の両方の削減重みに基づいて、ワーク領域を実行ワークリストに追加し得る。したがって、第2の画像のワークアイテムは、実行ワークリストへと散りばめられることが可能であり、第1の画像のワークアイテムと優先順位を共有し、それより優先順位が低く、またはそれより優先順位が高いことがある。幾何学に基づくワークアイテムの取得および優先順位付けは、すべての画像が取得され、すべてのワークアイテムがスケジューリングされるまで続き得る。第2の画像および後続の画像のためのワーク領域を特定することは、現在の更新されたワーキング境界形状に基づいて新しいワーク領域を特定すること、および/または、更新されたワーキング境界形状の境界の一部に適合するように既存のワーク領域の境界を変更することを含み得る。
【０１０６】
図10は、様々な実施形態および実施形態による、複数の処理装置にわたってワーク領域に基づいて優先順位付けられるワークの実行のための方法1000のプロセスフロー図を示す。方法1000は、コンピューティングデバイス(たとえば、100)で実施され、通信サブシステム(たとえば、130)およびメモリ(たとえば、125)と通信しているプロセッサ(たとえば、110)によって行われ得る。
【０１０７】
ブロック1002において、コンピューティングデバイスは、各ワークアイテムのワークスコアを計算し得る。ワークスコアは各々の利用可能な処理装置に固有であり得るので、各ワークアイテムは複数のワークスコアを有し、これは、利用可能な処理装置の各々での処理におけるそのワークアイテムの適格性を示す。ワークスコアは、たとえば、ワークアイテムと関連付けられるワーク領域のサイズおよび/または形状、ワークアイテムの処理を完了するのに必要な電池の寿命、ならびにワークアイテムの削減重みを含む、いくつかの起動要因のうちの1つまたは複数を使用して計算され得る。たとえば、大きいおよび/または長方形のワーク領域と関連付けられるワークアイテムは、画像処理装置(GPU)上での処理によく適していることがあり、GPUはかなりの大きさの、予想通りの形状の画像領域の処理によく適していることがある。しかしながら、GPUは、不規則な形状のワーク領域または多数の小さいワークアイテムには、非効率なプロセッサであり得る。同様に、中央処理装置(CPU)は、高い取消しの尤度を示す削減重みを有するワークアイテムの処理に最も適していることがあり、それは、CPU上で実行を開始したワークアイテムを取り消すことは、デジタルシグナルプロセッサ(DSP)またはGPU上で取り消すことより簡単であり得るからである。
【０１０８】
ブロック1004において、プロセッサは、ワークアイテムのワークスコアに基づいてワークアイテムを処理装置に割り当て得る。ブロック1004の動作は、ワークアイテムが割り当てられるべき処理装置を決定するために実施され得るいくつかの動作を含み得る。
【０１０９】
ブロック1006において、プロセッサは、ワークアイテムが各々の利用可能な処理装置(たとえば、110)に対する計算されたワークスコアを有するかどうかを決定し得る。
【０１１０】
ワークアイテムが各々の利用可能な処理装置に対するワークスコアを有しない(すなわち、ブロック1006=「No」)と決定したことに応答して、プロセッサは、ブロック1008において、ワークアイテムに対する起動要因を決定し、計算し、または探すことができる。ブロック1010において、プロセッサはワークアイテムのワークスコアを計算することができ、それは、ワークスコアが欠けているこのワークアイテムが、その特定のプロセッサに関係するものであるからである。決定ブロック1006において、プロセッサは再び、ワークアイテムが各処理装置に対するワークスコアを有するかどうかを決定し得る。様々な実装形態において、起動要因は、特定のタイプのプロセッサ上でのワークアイテムの起動オーバーヘッド(たとえば、ワークアイテムを起動するのに必要な処理リソース)、特定のプロセッサ上でワークを処理することと関連付けられる電池の消耗および/または熱応答、特定のプロセッサまたはプロセッサタイプのキューからワークを取り消すことの容易さ、およびワークアイテムの「形状」に基づくプロセッサの利用率を含み得る。
【０１１１】
各々の利用可能な処理装置に対するワークアイテムと関連付けられるワークスコアがある(すなわち、ブロック1006=「Yes」)と決定したことに応答して、プロセッサは、ブロック1012において、ワークアイテムと関連付けられる最良のワークスコアを決定することができる。これは、最高のスコア、最低のスコア、または0に最も近いスコアであり得る。プロセッサは、ワークアイテムと関連付けられるワークスコアの単純な数学的比較によって最良のワークスコアを決定し得る。
【０１１２】
ブロック1014において、プロセッサは、ワークアイテムが最も適している(すなわち、最良のワークスコアを有する)処理装置の反復空間または実行キューにワークアイテムを割り当て得る。プロセッサ(たとえば、110)は、すべてのワークが完了して最後の画像が作成されるまで、ワークアイテムを異なる処理装置に割り当て続け得る。
【０１１３】
様々な実装形態において、プロセッサ固有のワークスコアの計算は、特定のタイプのプロセッサ上でのワークアイテムの起動オーバーヘッド(たとえば、ワークアイテムを起動するのに必要な処理リソース)、特定のプロセッサ上でワークを処理することと関連付けられる電池の消耗および/または熱応答、特定のプロセッサまたはプロセッサタイプのキューからワークを取り消すことの容易さ、およびワークアイテムの「形状」に基づくプロセッサの利用率のうちの1つまたは複数に基づき得る。
【０１１４】
仮想現実およびゲームへの適用を含む実装形態では、物理的な動きを受ける画像フレームのリアルタイムの生成は、かなりの処理リソースを必要とする。十分高速に画像フレームを生成できないことは、視覚的な遅延またはジッタにつながり得る。そのような視覚的な影響はしばしば、仮想現実のユーザを不快にさせ、または目に疲労および不快さを引き起こす。様々なタイプのゲームおよび仮想現実への適用においては、多数のワールドオブジェクト、およびオブジェクト(たとえば、衝突、粉砕、煙と火のエフェクト)を含むゲーム内でのアクションがあり得る。これらのアクションおよびオブジェクトの一部は、対話型ユーザには見えないことがある。ユーザに見えるようになる可能性が高いオブジェクトおよびアクションのみの効率的な処理を可能にすることによって、様々な実施形態および実装形態は、遅延およびジッタの影響を減らすので、ゲームおよび仮想現実のユーザに対する全体的なユーザ体験を改善し得る。様々な実装形態は、粉砕の映像およびビュー内での衝突に対処するのに特に適していることがあり、このとき、最終的な「新しい」映像を得るためにワールドオブジェクトのすべてが処理されなければならないとは限らない。様々な実装形態では、すべてのワールド(すなわち、ゲーム内またはビュー内)オブジェクトが、ゲームの世界を表す2次元または3次元画像により占有されると見なされ得る。したがって、様々な実施形態および実装形態は、ある時間枠内にユーザにより見られる可能性が高い画像の領域にワーク処理が限定されることを可能にする。オブジェクトおよびアクションは、ある時間長の中で視聴されない場合、タイムアウトし得る(すなわち、無関係になり得る)。タイムアウト時間長は、オブジェクトおよびアクションの性質に基づいてあらかじめ決められ得る。対応するタイムアウトの前にユーザによって見られる可能性が高い画像の領域内にあるオブジェクトおよびアクションの処理は、コンピューティングデバイスの1つまたは複数のプロセッサにより優先順位付けられ得る。逆に、他のオブジェクトおよびアクション(すなわち、時間枠の間に見られる可能性が最も低いもの)の処理は、完全に遅らされ、またはスキップされ得る。
【０１１５】
仮想現実への適用では、新しいオブジェクトがユーザの視野内に定期的に現れることがあり、新しいアクションが開始することがある(たとえば、粉砕する、2つのオブジェクトの衝突の後に弾む、衝突の後に炎上するなど)。そのような時間において、プロセッサは、所定の関心のある領域内にあるオブジェクトおよびアクションの処理を制限するために、領域のうちのいずれが関心の対象かについての新しい決定を行うことができる。
【０１１６】
図11は、仮想現実ゲームアプリケーションにおけるワーク処理の幾何学に基づく優先順位付けのための方法1100の処理フロー図を示す。方法1100は、コンピューティングデバイス(たとえば、100)で実施され、通信サブシステム(たとえば、130)およびメモリ(たとえば、125)と通信しているプロセッサ(たとえば、110)によって行われ得る。
【０１１７】
ブロック1102において、コンピューティングデバイスは、アプリケーションから画像フレームを取得し得る。プロセッサ(たとえば、110)は、1つまたは複数のカルマンフィルタ技法の使用などの、任意の標準的な動き予測技法を使用して、ユーザのビューポートの動きの予想される方向および予想される場所を計算し得る。動きの方向は、ビューポート(すなわち、仮想現実視野)が特定の領域に到達しない時間の予測される長さを計算するために使用され得る。この時間長「t」は取得された画像に割り当てられ得るので、画像の座標表現は(x,y,t)であり得る。
【０１１８】
ブロック1104において、コンピューティングデバイスは新しいキーイベントを検出し得る。プロセッサ(たとえば、110)は、ブロック1106においてイベントの性質を決定し得る。イベントは、たとえば、画面上の衝突、定期的な場所の更新、およびシーンの変化を含み得る。グラフィクス処理の実装形態(たとえば、仮想現実ビュー区間への適用)におけるキーイベントは、衝突、粉砕、シーンの変化、および視野への他の実質的な変更などの、ビューポートの再構成または並べ替えをもたらすイベントであり得る。
【０１１９】
イベントが衝突である場合、プロセッサ(たとえば、110)は、ブロック1116において、取得された画像の境界を決定し、粉砕パターン(たとえば、ワーク領域)を決定し、方法200および900に従って各ワーク形状または領域に対する削減重みを決定し得る。
【０１２０】
ブロック1118において、プロセッサ(たとえば、110)は、ワーク形状または領域と関連付けられるワークアイテムを処理のためにワークリストに登録し得る。その時間長「t」がワークアイテムの処理の前にタイムアウトするワークアイテムは、ワークリストおよびあらゆる関連するプロセッサキューから除去され得る。コンピューティングデバイスは次いで、以下で説明されるようにブロック1114の動作を実行し得る。
【０１２１】
イベントが定期的な場所の更新である場合、ブロック1108において、コンピューティングデバイスは、ビューポート内の風景への定期的な更新を実行し得る。方法200および900に従って、プロセッサ(たとえば、110)は、ワーキング境界形状または領域を更新することができ、各アクティブ領域(すなわち、「t」が満了していない領域)に対して「t」を再計算することができる。「t」の再評価は、様々なワーク領域に対する削減重みの修正をもたらし得る。いくつかの場合、時間長「t」の再評価は、ワークアイテムの廃棄をもたらし得る。
【０１２２】
ブロック1110において、コンピューティングデバイスは、時間長がタイムアウトしたワークアイテムを廃棄し得る。さらに、コンピューティングデバイス(たとえば、100)のプロセッサ(たとえば、110)は、時間長がタイムアウトすると、ワーキング境界形状または領域の時間成分をリセットし得る。コンピューティングデバイスは次いで、以下で説明されるようにブロック1114の動作を実行し得る。
【０１２３】
検出されたイベントが、全体の視野が変化するシーンの変更である場合、ブロック1112において、コンピューティングデバイスは、ワークリストの中のすべてのワークアイテムを廃棄し、デフォルトの境界形状または領域をリセットし得る。以前にキューに入れられていた画像セグメント(たとえば、ワークアイテム)がもはや現在のシーンに適用可能ではないので、関連するワークアイテムの処理の必要はないことがある。したがって、プロセッサ(たとえば、110)は、削減重みとは無関係にすべてのワークアイテムを廃棄し得る。
【０１２４】
ブロック1114において、コンピューティングデバイスは、アクションのために残っているイベントがあるかどうかを決定し得る。イベントが存在する場合(すなわち、ブロック1114=「Yes」)、プロセッサ(たとえば、110)は、ブロック1106において残っているイベントの性質を再び決定し得る。
【０１２５】
残っているイベントがない場合(すなわち、ブロック1114=「No」)、コンピューティングデバイスは、「K」個の最良のワークアイテムをワークリストから選択することができ、ブロック1120において1つまたは複数のプロセッサを介してそれらのワークアイテムを処理することができる。プロセッサは、すべての画像が処理されるまで、またはアプリケーションが終了するまで、画像を取得することおよび予測される動きを計算することを続け得る。
【０１２６】
様々な実装形態において、ソフトウェアアプリケーションは、廃棄領域(すなわち、その中のすべてのワークアイテムが廃棄され得る幾何学的な形状の領域)を構築することと、境界領域(すなわち、その中のすべてのワークアイテムが廃棄のための更新された尤度に基づいて新しい削減重みを割り当てられ得る幾何学的な形状の領域)を構築することのために、異なる戦略を使用し得る。アプリケーション固有の境界決定戦略を利用できることで、多様なタイプおよび使用法のソフトウェアアプリケーションが、ワークアイテムの幾何学的スケジューリングのための様々な実装形態および実施形態を利用することが可能になり得る。
【０１２７】
廃棄領域および境界領域は、パノラマ画像-処理ソフトウェアアプリケーションにおける新しい「キー画像フレーム」の到着などの「キーイベント」にソフトウェアアプリケーションが遭遇すると、再計算され得る。キー画像フレームを処理するのに必要なワークの評価により、ワーキング境界ボックスの形状が形状またはサイズの変化(縮小)を受けることがある。以前のワーキング境界形状と更新されたワーキング境界形状との間の幾何学的な形状の領域は、そのようなパノラマ処理ソフトウェアアプリケーションによる評価の間に廃棄領域になり得る。
【０１２８】
様々な実装形態および実施形態において、更新されたワーキング境界形状から見た廃棄領域の位置は、廃棄領域に最も近い更新されたワーキング境界形状内の領域が後続のキーイベントの到着の際に廃棄される可能性がより高くなったことを示し得る。逆に、ワーキング境界形状内にあり、廃棄領域から最も遠くに位置する幾何学的に形状が区切られた領域は、後続のキーイベントの到着に際して廃棄される可能性がより低いことがある。そのような実装形態では、すべての幾何学的に境界が区切られた領域の削減重みが、それぞれのソフトウェアアプリケーションによって利用される境界決定計画に従って更新され得る。
【０１２９】
様々な実装形態は、コンピュータゲーム、仮想現実、拡張現実、複合現実、コンピュータビジョン、リアルタイムカメラ画像処理などの、広範なカテゴリのソフトウェアアプリケーションのための幾何学的ワークスケジューリングを含み得る。
【０１３０】
いくつかの実装形態では、ワーキング境界形状が利用され得る。ソフトウェアアプリケーションは、過剰に大きな形状へと初期化され新しいキーイベントの処理の結果として縮小し続け得る、ワーキング境界形状を維持し得る。キーイベント更新の間にワーキング境界形状の内部からワーキング境界形状の外部へと移った幾何学的に境界が区切られた領域が、廃棄領域になる。
【０１３１】
廃棄領域の近接度は、更新されたワーキング境界形状内の尤度更新領域の形状/位置を決定し得る。すなわち、ワーキング境界形状内にあり、しかしワーキング境界形状の周縁/外部の近くに位置する幾何学的に境界を区切られた領域は、「更新される可能性が高い」と見なされることがあり、それは、そうした領域の場所により、そうした領域の削減重みが新しいキーイベントの処理に際して更新を必要とする(または廃棄領域に移され得る)可能性がより高くなるからである。後続のキーイベントの特性を予測するための追加のソフトウェアアプリケーション固有の機能(たとえば、位置および形状の特性を予測するために動き予測技法を使用すること)がさらに、尤度更新領域の決定を助け得る。
【０１３２】
様々な実装形態において、所定の領域の境界が利用され得る。ソフトウェアアプリケーションは、大きな幾何学的空間をいくつかの領域へ先験的に分割し得る。各々の所定の領域、または幾何学的に隣接する所定の領域の集合体が、廃棄領域または尤度更新領域になり得る。たとえば、仮想現実ゲームソフトウェアアプリケーションは、等しいサイズの所定の領域へとヘッドセットビュー空間の全体を事前に分割し得る。ソフトウェアアプリケーションは、次の「T」ミリ秒内にヘッドセットにより見られる可能性が低いものとして、1つまたは複数の所定の領域を廃棄するために、頭部追跡動き予測(たとえば、カルマンフィルタ)を使用し得る。ソフトウェアアプリケーションは、ユーザがほとんど確実にその結果を見ないであろうすべてのワークアイテムを廃棄すると決めることができ、次のTミリ秒において見られる可能性がより高いまたは低いものとして、ヘッドセットの現在のビューの場所に最も近い所定の領域を更新することができる。尤度更新領域の削減重みは、それに従って調整され得る。
【０１３３】
様々な実装形態において、境界計画は焦点領域戦略を利用し得る。ソフトウェアアプリケーションと対話するユーザの注意は、仮想現実への適用における完全な360度のビュー空間内のヘッドセットビュー、または従来のコンピュータゲームにおけるより大きい世界のビュー空間内の画面空間ビューなどの、大きな幾何学的空間のうちの限られた部分に、ある時間の間集中することがある。焦点は、ソフトウェアアプリケーションの機能によって、または、ユーザが仮想現実ヘッドセットをどれだけ速く動かせるかなどの、物理的な制約によって定義され得る。廃棄領域および尤度更新領域は、現在の焦点領域へのそれぞれの近接度、ならびに、所与の時間枠内に現在の焦点領域を超える/囲むより大きな領域へユーザの焦点が入る尤度の予測に基づいて、決定され得る。廃棄領域および尤度更新領域の形状およびサイズは、あらかじめ決定される戦略とは対照的に、各キーイベントの後で動的に決定され得る。
【０１３４】
複雑なソフトウェアアプリケーションは、複数のフィーチャおよび機能にわたって幾何学的スケジューリングを一緒に実施するために、混種の戦略を利用し得る。幾何学的スケジューリング空間は、物理的なビュー空間だけではなく、時間などの他の次元、およびゲームキャラクタのヒットポイントなどのアプリケーション固有の次元からなり得る。廃棄領域および尤度更新領域は、アプリケーションおよび幾何学的スケジューリングを受けるフィーチャの性質に基づいて、次元の部分集合またはすべてにわたるように選ばれ得る。
【０１３５】
図12は、ワーク処理の幾何学に基づく優先順位付けを実施する、コンピュータゲームのコンピュータゲームスクリーンショット1200の図を示す。スクリーンショット1200において図示されるコンピュータゲームは、方法200、1000、および1100の一部またはすべてを利用することができ、コンピューティングデバイス(たとえば、100)で実施され、通信サブシステム(たとえば、130)およびメモリ(たとえば、125)と通信しているプロセッサ(たとえば、110)によって行われ得る。
【０１３６】
様々な実装形態において、コンピュータゲームは、ワークアイテムの幾何学的スケジューリングの複数の実施形態を利用し得る。図9および図11を参照して論じられるように、幾何学的スケジューリングは、処理速度および効率を改善できるような方式で、グラフィクス/画像処理を扱うために使用され得る。示されるスクリーンショット1200において、複数のプレーヤーキャラクタ1202〜1210が、プレーヤーではない敵のドラゴン1212とゲームの戦闘を行うことがある。
【０１３７】
1つまたは複数のプロセッサ(たとえば、プロセッサ110、複数のプロセッサ、および/またはGPU)は、戦闘シーンをレンダリングし、ユーザ入力が受け取られ戦闘が進行するにつれてキャラクタ1202〜1210の画像およびドラゴン1212の動きを更新し得る。ある所与の時点におけるプレーヤーキャラクタ1202〜1210のうちのいずれか1人に表示される具体的なスクリーンショットは、ドラゴン1212および周辺環境に関してプレーヤーの見晴らしの利く点に依存する。様々な分類のプレーヤーキャラクタ1202〜1210が、ドラゴン1212に近い可能性がより高いことがあり、他の分類のプレーヤーキャラクタ1202〜1210より動く可能性が高いこともまたは低いこともある。たとえば、示されるスクリーンショット1200において、戦士のプレーヤーキャラクタ1202は、ソフトウェアアプリケーションに知られているように、ドラゴン1212に近接して立っている可能性が高いことがあるが、プレーヤーキャラクタ1206〜1210の「隊列」から離れたより良い位置にドラゴン1212を置くために、動き回る可能性が高いことがある。したがって、コンピュータゲームソフトウェアアプリケーションは、ドラゴンから遠くにある周辺環境の部分が廃棄される可能性が高いと決定し得る。すなわち、ドラゴン1212が戦士のプレーヤーキャラクタ1202のビューの焦点領域であることがあり、ドラゴン1212の焦点領域から遠くにある領域は、ドラゴン1212からの距離が大きくなるにつれて廃棄される可能性がより高くなる。しかしながら、戦士のプレーヤーキャラクタ1202がドラゴン1212に近接してよく動くので、焦点領域内の領域の削減重み(すなわち、取消しの尤度)は、その外側に近い領域であっても、低いことがある。
【０１３８】
逆に、プレーヤーキャラクタの隊列1206〜1210は、ドラゴン1212から長い距離を保ち得るが、あまり頻繁には動き回らないことがある。そのようなプレーヤーキャラクタ1206〜1210は、大きな焦点領域(たとえば、よりパノラマのビュー)を有し得るので、小さい廃棄領域を有し得る。しかしながら、これらのキャラクタは比較的動かないので、視野の外側に近い領域が廃棄される尤度は高いことがある(たとえば、高い削減重み)。同時に、武装した神聖なプレーヤーキャラクタ1204はよく動くことがあり、概ね少し離れて立ち得るので、ソフトウェアアプリケーションがその視野内の領域のたくさんの廃棄を実行することが難しくなる。
【０１３９】
ワークアイテムの幾何学的スケジューリングの別の例では、コンピュータゲームは、キューに入れられるべきワークおよび廃棄される可能性が高いワークを決定するために、ドラゴン1212の人工知能エンジンを監視し得る。スクリーンショット1200に示されるように、敵のステータスインジケータ1214は、ドラゴン1212の残りのヒットポイント(HP)についての情報を提供することができ、この場合は230,000ポイントのうちの10,000ポイントが残っている。プレーヤーキャラクタ1202〜1210の各攻撃が、残っている数字からポイントを削り得る。
【０１４０】
ドラゴン1212のアクションキュー1216は、ドラゴンにより実行される今度の攻撃(すなわち、コンピュータゲームソフトウェアアプリケーションにより行われるべき機能)を図示する。示される例では、「クリーブ(cleave)」および「テールホイップ(tail whip)」などの機能がそれぞれ20秒および45秒の一定の間隔で発生し、これらが標準的な低処理コストの機能であることを示唆する。しかしながら、「フレームブレス(flame breath)」機能は別の2分間の間発生することが予定されていないので、これがプレーヤーキャラクタ1202〜1210へのより破壊的な攻撃である可能性があり、したがってより多くの画像およびAIの処理が必要であり得ることを示唆する。
【０１４１】
たとえば、「フレームブレス」攻撃の処理は、炎の視覚的表現の処理、ドラゴンの体全体の動き、攻撃を受けるプレーヤーキャラクタのそれに応答した動き、ならびにプレーヤーキャラクタ1202〜1210の数字およびドラゴン1212の数字の更新を含み得る。しかしながら、「フレームブレス」の実行を準備する際のこれらのワークアイテムの負荷および前処理は、ドラゴン1212が次の2分以内に死ねば不要であり無駄になる。
【０１４２】
ワークアイテムの不要なキューイングおよび前処理を減らすために、コンピュータゲームソフトウェアアプリケーションは、ドラゴン1212のHPと、プレーヤーキャラクタ1202〜1210により毎秒当たり生み出される平均のドラゴン1212に対する攻撃の値のダメージ毎秒(DPS)率とを監視し得る。コンピューティングデバイスは次いで、「残りの戦闘時間」(たとえば、ドラゴンが無力化されるまでの時間)の可変の目標を計算し得る。コンピュータゲームソフトウェアアプリケーションは、この予測される時間枠をAIワークキューと比較することができ、時間枠の満了により近い、または時間枠の外側にある機能はより発生する可能性が低いと決定することができる。機能(たとえば、ドラゴンの攻撃)が廃棄される尤度は、時間が経つにつれて、かつHPまたはDPS率が変化するにつれて、変化し得る。コンピューティングデバイスは、この情報を使用して、プロセッサワークリスト内のワークアイテムを組織化することができるので、予測される「残りの戦闘時間」が2分の時間枠より短い尤度が高い場合、「フレームブレス」攻撃をキューイングすることを避けることができる。
【０１４３】
幾何学的ワークスケジューリングのそのような実装形態は、すべての非プレーヤーキャラクタ、アクション、APIコール、および、さらに自動的なプレーヤーキャラクタ1202〜1210のアクションに適用され得る。幾何学的ワークスケジューリングの実装形態は、ゲーム内の「遅延」(すなわち、遅いフレームの更新またはジッタを伴う遷移)を減らすことができ、プレーヤーの入力に対する応答性を高めることができるので、全体的なユーザ体験を改善する。
【０１４４】
上記の方法の説明およびプロセス流れ図は、単に説明のための例として提供され、様々な実施形態の動作が提示された順序で実行されなければならないことを要求または暗示するものではない。当業者によって諒解されるように、上記の実施形態における動作の順序は、任意の順序で実行されてもよい。「その後」、「次いで」、「次に」などの単語は、動作の順序を限定するものではなく、これらの単語は単に、方法の説明を通して読者を導くために使用される。さらに、たとえば、冠詞「a」、「an」または「the」を使用する、単数形での請求項要素へのいかなる言及も、その要素を単数形に限定するものとして解釈されるべきではない。
【０１４５】
「第1の」および「第2の」という用語は、ある契約と関連付けられるデータ送信および異なる契約と関連付けられるデータ受信を説明するために本明細書で使用されるが、そのような識別子は便宜上のものにすぎず、様々な実施形態を特定の順序、シーケンス、ネットワークまたはキャリアのタイプに限定するものではない。
【０１４６】
本明細書で開示された実施形態に関して説明された様々な例示的な論理ブロック、モジュール、回路、およびアルゴリズム動作は、電子ハードウェア、コンピュータソフトウェア、またはその両方の組合せとして実装され得る。ハードウェアおよびソフトウェアのこの互換性を明確に示すために、様々な例示的な構成要素、ブロック、モジュール、回路および動作は、概してそれらの機能に関して上で説明された。そのような機能がハードウェアとして実装されるのか、またはソフトウェアとして実装されるのかは、具体的な適用例および全体的なシステムに課される設計制約で決まる。当業者は、説明された機能を具体的な適用例ごとに様々な方法で実装し得るが、そのような実装の決定は、特許請求の範囲からの逸脱を引き起こすものとして解釈されるべきではない。
【０１４７】
本明細書で開示される態様に関して説明された様々な例示的な論理、論理ブロック、モジュール、および回路を実装するために使用されるハードウェアは、汎用プロセッサ、デジタル信号プロセッサ(DSP)、特定用途向け集積回路(ASIC)、フィールドプログラマブルゲートアレイ(FPGA)もしくは他のプログラマブル論理デバイス、個別ゲートもしくはトランジスタ論理、個別ハードウェア構成要素、または本明細書で説明した機能を実行するように設計されたそれらの任意の組合せを用いて、実施または実行され得る。汎用プロセッサはマイクロプロセッサであってよいが、代替として、プロセッサは、任意の従来のプロセッサ、コントローラ、マイクロコントローラ、またはステートマシンであってよい。プロセッサはまた、コンピューティングデバイスの組合せ(たとえば、DSPとマイクロプロセッサとの組合せ、複数のマイクロプロセッサ、DSPコアと連携した1つもしくは複数のマイクロプロセッサ、または任意の他のそのような構成)として実装され得る。代替的に、いくつかの動作または方法は、所与の機能に特有の回路によって実行され得る。
【０１４８】
1つまたは複数の例示的な態様では、説明された機能は、ハードウェア、ソフトウェア、ファームウェア、またはそれらの任意の組合せで実装され得る。ソフトウェアで実装される場合、機能は、非一時的コンピュータ可読媒体または非一時的プロセッサ可読媒体上に1つまたは複数の命令またはコードとして記憶され得る。本明細書で開示される方法またはアルゴリズムの動作は、非一時的コンピュータ可読記憶媒体上または非一時的プロセッサ可読記憶媒体上に常駐し得るプロセッサ実行可能ソフトウェアモジュールの中で具現化され得る。非一時的コンピュータ可読記憶媒体またはプロセッサ可読記憶媒体は、コンピュータまたはプロセッサによってアクセスされ得る任意の記憶媒体であってよい。限定ではなく例として、そのような非一時的コンピュータ可読またはプロセッサ可読媒体は、RAM、ROM、EEPROM、FLASHメモリ、CD-ROMもしくは他の光ディスクストレージ、磁気ディスクストレージもしくは他の磁気記憶デバイス、または命令もしくはデータ構造の形態で所望のプログラムコードを記憶するために使用され得るとともにコンピュータによってアクセスされ得る任意の他の媒体を含み得る。本明細書で使用するディスク(disk)およびディスク(disc)は、コンパクトディスク(disc)(CD)、レーザーディスク(登録商標)(disc)、光ディスク(disc)、デジタル多用途ディスク(disc)(DVD)、フロッピーディスク(disk)、およびBlu-ray(登録商標)ディスク(disc)を含み、ディスク(disk)は通常、データを磁気的に再生し、ディスク(disc)は、レーザーを用いてデータを光学的に再生する。上記の組合せも、非一時的コンピュータ可読媒体およびプロセッサ可読媒体の範囲に含まれる。追加として、方法またはアルゴリズムの動作は、コンピュータプログラム製品に組み込まれ得る、非一時的プロセッサ可読媒体および/またはコンピュータ可読媒体上のコードおよび/または命令の1つまたは任意の組合せまたはセットとして存在し得る。
【０１４９】
開示される実施形態の前述の説明は、任意の当業者が特許請求の範囲を製作または使用することを可能にするために提供される。これらの実施形態への様々な修正が当業者には容易に明らかになり、本明細書において定義される一般原理は、特許請求の範囲から逸脱することなく他の実施形態に適用され得る。したがって、本開示は、本明細書において示される実施形態に限定されるものではなく、以下の特許請求の範囲ならびに本明細書において開示された原理および新規の特徴に一致する最大の範囲を与えられるべきである。
【符号の説明】
【０１５０】
100  コンピューティングデバイス
105  バス
110  プロセッサ
115  タッチスクリーン
116  スピーカ
120  インターフェース
122  電源
125  不揮発性メモリ
130  通信サブシステム
135  揮発性メモリ
140  オペレーティングシステム
145  アプリケーション
200  方法
300  イベントマッピング
302  デフォルトの境界領域
304  第1のワーク領域
306  廃棄領域
400  画像つなぎ合わせ技法
402  フレーム、画像フレーム、ワーク領域
404  フレーム、画像フレーム、ワーク領域
406  フレーム、画像フレーム、ワーク領域
408  フレーム、画像フレーム、ワーク領域
410  フレーム、画像フレーム、ワーク領域
412  フレーム
414  フレーム
416  フレーム
418  フレーム
420  フレーム
500  画像つなぎ合わせ技法
502  画像フレーム
504  画像フレーム
506  画像フレーム
508  画像フレーム
510  画像フレーム
512  画像フレーム
514  フレーム
516  フレーム
518  フレーム
520  フレーム
600  画像フレーム
602  ワーク領域
604  ワーク領域
606  ワーク領域
608  ワーク領域
610  ワーク領域
700  幾何学的なワークスケジューリング計画
710  新しいワークアイテムを生成する
712  領域を廃棄する
714  ワークアイテムの削減重みを更新する
722  ランタイム幾何学的スケジューリング環境
724  スケジューリングループ
802  画像フレーム
804  画像フレーム
806  画像フレーム
808  画像フレーム
810  画像フレーム
900  方法
1000  方法
1100  方法
1200  コンピュータゲームスクリーンショット
1202  プレーヤーキャラクタ
1204  プレーヤーキャラクタ
1206  プレーヤーキャラクタ
1208  プレーヤーキャラクタ
1210  プレーヤーキャラクタ
1212  ドラゴン
1214  ステータスインジケータ
【図１】
2019519015.tif 000007
【図２】
2019519015.tif 000008
【図３】
2019519015.tif 000009
【図４】
2019519015.tif 000010
【図５】
2019519015.tif 000011
【図６】
2019519015.tif 000012
【図７】
2019519015.tif 000013
【図８】
2019519015.tif 000014
【図９】
2019519015.tif 000015
【図１０】
2019519015.tif 000016
【図１１】
2019519015.tif 000017
【図１２】
2019519015.tif 000018
【国際調査報告】
2019519015.tif 000019
2019519015.tif 000020
2019519015.tif 000021