粒子フィルターアルゴリズムは、ビデオシーケンス内のオブジェクトの追跡に使用されることで知られています。各反復で、アルゴリズムはオブジェクトの動きに関する仮説（またはサンプル）を生成します。新しい仮説を生成するために、凝縮アルゴリズムの最初のステップにはサンプルの選択が含まれます。このWebページで提供される例は、ベースを選択するために二分探索を使用する選択ステップの実装を示しています。サンプル; 関数をサポートするコメントはpick_base_sample()それを説明します
このルーチンを使用すると、凝縮O（NlogN）が作成されます。ここで、Nはサンプルの数です。アルゴリズムはO（N）であり、おそらくわずかに効率的であるため、決定論的にベースサンプルを選択する方がおそらく良いでしょうが、このルーチンは、概念を単純にするため、および公開された文献によりよくマッピングされるため、ここに保持されます。
決定論的にベースサンプルを選択することはどういう意味ですか？決定論的にベースサンプルを選択する方法は？
凝縮アルゴリズムは、複数のサンプルを使用して現在の推定状態を表します。各サンプルには、関連付けられた重みがあります（サンプルが正しい確率を推定します）。
選択ステップでは、このセットからN個のサンプルが選択されます（置換を使用するため、同じサンプルが複数回表示される可能性があります）。
選択手順を説明するために、サンプルを一連の線分として描画することを想像してください。各線分の幅をそのサンプルの重みと等しくします。
たとえば、サンプルA（重み0.1）、B（重み0.3）、およびC（重み0.6）があるとします。
私たちは描くでしょう：
ABBBCCCCCC
通常のランダム選択プロセスでは、この線に沿ってランダムなポイントを選択し、その位置にどのサンプルが表示されるかを確認してサンプルを描画します。このアプローチで認識される問題は、重みを保持するためにツリーデータ構造を使用するときに、特定の場所にどのサンプルが表示されるかを判断するためにO（logN）操作が必要になることです。（実際には、これが実装の主な処理のボトルネックになるとは思いませんが）
別の決定論的（基本的に「再現可能」で「乱数を含まない」と考える）アプローチは、同じ線に沿ってN個の規則的な間隔の点を選択することによってサンプルを選択することです。これの利点は、これを行うためのアルゴリズムがO（NlogN）ではなくO（N）の時間を要することです。
（決定論的アルゴリズムは、これまでに見られた総重量を追跡しながらすべてのサンプルをループすることです。総重量が次の一定間隔のポイントに達するたびに、新しいサンプルを収集します。これには、サンプルの1回のパスのみが必要です。O（ N））。