一般の人々の「ぼかし」は、デジタル画像処理におけるぼかし効果です。 それ自体、およびインターフェースアニメーションのコンポーネント、またはより複雑な派生エフェクト（bloom / focusBlur / motionBlur）として非常に効果的です。 このすべてで、額の正直なブルースはかなり遅いです。 また、多くの場合、ターゲットプラットフォームに組み込まれた実装には、多くの要望が残されています。 スピードが悲しいか、アーティファクトが目を傷つけます。 この状況により、特定の条件に適したより良いまたは悪い多くの妥協した実装が生じます。 優れた信頼性と最高の速度を備えたオリジナルの実装で、ハードウェアへの依存度が最も低いものがあなたを待っています。 いってらっしゃい！
（ラプラスぼかし-提案された元のアルゴリズム名）
今日、私の内部デモシーンは私を蹴り、6ヶ月前に書かなければならなかった記事を書くことを強制しました。 アマチュアとして、余暇には、オリジナルのエフェクトアルゴリズムを開発するために、非常に高速なプロセッサ命令（シフトとマスク）の使用を特徴とする「ほぼガウスブルー」アルゴリズムを一般に提供したいと思います。
Habrで記事を書くという私の伝統に従い、JSを最も人気のある言語として例を挙げますが、信じられないかもしれませんが、アルゴリズムのラピッドプロトタイピングの目的には非常に便利です。 さらに、JSでこれを効果的に実装する機能には、型付き配列がありました。 私のあまり強力ではないラップトップでは、フルスクリーン画像は30fpsの速度で処理されます（ワーカーのマルチスレッド化は関係していませんでした）。
クールな数学の免責事項
私は自分が基本的な数学に十分に精通していないと考えているため、帽子を脱いでいるとすぐに言います。 しかし、私は常に基本的なアプローチの一般的な精神に導かれています。 したがって、近似に対する私のやや「観測的な」アプローチをごまかす前に、アルゴリズムのビット複雑度の計算に注意してください。これは、ご想像のとおり、古典的な多項式近似法によって取得できます。 そうだった？ すぐにそれらを近似したいですか？ 浮動小数点演算が必要であることを考えると、それらはシングルビットシフトよりもかなり遅くなります。これについては最後に説明します。 一言で言えば、理論原理主義に急ぐことはせず、私が問題を解決する文脈を忘れないでください。
この説明は、結果につながった私の考えや推測の経過を説明するために、むしろここにあります。 興味がある人のために：
元のガウス関数：
g（x）= a * e **（-（（xb）** 2）/ c）、ここで
および-振幅（チャネルごとに8ビットがある場合、それは256 =）
eはオイラー定数〜2.7
b-xのグラフシフト（必要なし= 0）
c-〜w / 2.35として関連付けられたグラフの幅に影響するパラメーター
プライベート関数（除算による乗算の置換で削除された指数からのマイナス）：
g（x）= 256 / e **（x * x / c）
ダーティ近似アクションを開始しましょう：
パラメーターcは半値幅に非常に近く、8に設定されていることに注意してください（これは、各8ビットチャネルを1つずつシフトできるステップ数が原因です）。
eを2で大まかに置き換えますが、これは境界ではなく「ベル」の曲率に影響することに注意してください。 実際、それは2 / e回に影響しますが、驚いたことに、この誤差はパラメーターcを補正するため、境界条件はまだ整然としており、誤差はグラフィックのわずかに不正確な「正規分布」にしか現れません。アルゴリズムでは、これはグラデーションカラートランジションのダイナミクスに影響しますが、目で確認することはほとんど不可能です。
だから今私たちの機能は次のとおりです。
gg（x）= 256/2 **（x * x / 8）またはgg（x）= 2 **（8-x * x / 8）
指数（x * x / 8）は、低位のabs（x）の関数と同じ値[0-8]の範囲を持っているため、後者は置換の候補であることに注意してください。 gg（x）= 256 /（2 ** abs（x））でグラフがどのように変化するかを見て、推測をすばやく確認します。
GaussBlur対LaplasBlur：
偏差は大きすぎるようです。さらに、滑らかさを失った関数はピークになりました。 でもね
まず、ぼかしによって得られる勾配の滑らかさは、確率密度関数（ガウス関数）ではなく、その積分（分布関数）に依存することを忘れないでください。 当時、私はこの事実を知りませんでしたが、実際には、確率密度関数（ガウス）に関して「破壊的な」近似を実行したため、分布関数は非常に類似したままでした。
それは：
次のようになりました：
既製のアルゴリズムから取った証明は一致します：
（先を見て、Gausian x5に対するアルゴリズムのぼかしエラーはわずか3％だったと言います）。
そのため、ラプラス分布関数にかなり近づきました。 誰が考えていただろうが、彼らは画像を97％悪くすることはできない。
証明、ガウスブラーx5とラプラスブラーx7の違い：
（これは黒いイメージではありません！エディターで学習できます）
この変換の前提により、反復フィルタリングによって値を取得するという考えに進むことができました。これを最初に減らすことを計画していました。
特定のアルゴリズムを説明する前に、先に進んでその唯一の欠点をすぐに説明しておけば正直です（ただし、実装は速度を落とすことで修正できます）。 ただし、このアルゴリズムはせん断演算を使用して実装されており、2のべき乗が制限されています。 したがって、オリジナルはx7（テストではGausian x5に最も近い）をぼかします。 実装のこの制限は、8ビットカラーでは、ステップごとに1ビットずつフィルタードライブの値をシフトするため、ポイントからの効果は最大8ステップで終了するという事実に関連しています。 また、プロポーションと追加機能によりわずかに遅いバージョンを実装しました。これにより、1.5の素早い除算が実装されます（半径は15になります）。 しかし、このアプローチをさらに適用すると、エラーが増加し、速度が低下するため、そのように使用することはできません。 一方、x15はすでに十分に違いがあることに気付かないほど十分であることに注意してください。結果は元の画像またはダウンサンプリングされた画像から取得されます。 そのため、この方法は、限られた環境で並外れた速度が必要な場合に非常に適しています。
そのため、アルゴリズムの中核は単純であり、同じタイプの4つのパスが実行されます。
1.ドライブtの値の半分（最初はゼロに等しい）が次のピクセルの値の半分に加算され、結果がそれに割り当てられます。 この方法で画像行の最後まで続けます。 すべての行に対して。
最初のパスが完了すると、画像は一方向にぼやけます。
2. 2番目のパスまでに、すべてのラインに対して反対方向に同じことを行います。
水平方向に完全にぼやけた画像が得られます。
3-4。 次に、同じことを垂直に行います。
できた！
最初は、スタックを介したバックブラーの実装で2パスアルゴリズムを使用しましたが、理解が難しく、優雅ではなく、現在のアーキテクチャでは遅くなることが判明しました。 おそらく、ワンパスアルゴリズムはマイクロコントローラーでより高速になり、さらに結果を段階的に出力する機能もプラスになります。
現在の4方向の実装方法では、ブラーアルゴリズムに関する以前の第一人者のHabréを調べました。 habr.com/post/151157私はこの機会に彼に私の連帯と深い感謝を表明します。
しかし、ハッキングはそこで終わりませんでした。 次に、1つのプロセッサ命令で3つのカラーチャネルすべてを計算する方法について説明します。 実際には、2で除算するときに使用されるビットシフトを使用すると、結果ビットの位置を非常に適切に制御できます。 唯一の問題は、チャネルの下位ビットが隣接する上位ビットにスライドすることですが、問題を修正するよりも、精度をいくらか落としてリセットすることができます。 また、記載されているフィルター式によると、ドライブの値の半分と次のセルの値の半分を加算しても（放電したビットのリセットの対象となります）オーバーフローは発生しないため、心配する必要はありません。 そして、すべての数字を同時に計算するためのフィルター式は次のようになります。
buf32 [i] = t =（（（t >> 1）＆0x7F7F7F）+（（buf32 [i] >> 1）＆0x7F7F7F）;
ただし、もう1つ追加する必要があります。この式の精度の損失は非常に大きく、画像の明るさは視覚的に大幅にジャンプすることが実験的にわかっています。 失われたビットは最も近い整数に丸められ、破棄されないことが必要であることが明らかになりました。 整数演算でこれを行う簡単な方法は、除算の前に除数の半分を追加することです。 除数2があるため、すべての桁に定数1x010101を追加する必要があります。 ただし、追加する場合は、オーバーフローの発生に注意する必要があります。 そのため、このような修正を使用して次のセルの値の半分を計算することはできません。 （白い色がある場合、オーバーフローが発生するため、修正しません）。 しかし、主な間違いはドライブの複数の分割によって行われたことが判明したので、修正することができます。 実際、そのような修正を行っても、ドライブの値は254を超えないためです。しかし、0x010101に追加された場合、オーバーフローは保証されません。 そして、補正付きのフィルター式は次の形式を取ります。
buf32 [i] = t =（（（（（0x010101 + t）>> 1）＆0x7F7F7F）+（（buf32 [i] >> 1）＆0x7F7F7F）;
実際、式は補正を非常にうまく実行するため、このアルゴリズムを画像に繰り返し適用すると、アーティファクトは2番目の10パスでのみ表示され始めます。 （ガウスブラーを繰り返してもそのようなアーティファクトが生成されないという事実ではありません）。
さらに、多くのパスを持つ素晴らしいプロパティがあります。 （これは私のアルゴリズムではなく、正規分布の「正規性」によるものです）。 Laplace Bluraの2回目のパスでは、確率密度関数（すべてが正しければ）は次のようになります。
おわかりのように、これはすでにガウスに非常に近いものです。
経験的に、大きな半径の修正を使用することはペアで許可されることがわかりました。 上記のプロパティは、最後のパスがより正確な場合にエラーを補正します（最も正確なのは、ここで説明するx7ブラーアルゴリズムです）。
デモ
ラップ
d
クールな数学者へのアピール：
このようなフィルターを分離して使用するのがどれだけ正しいかを知るのは興味深いことですが、対称的な分布図があるかどうかはわかりません。 目の不均一性は見えませんが。
upd：ここでは、コメンテーターが親切に提示し、他のKhabrovitesから見つけた便利なリンクを作成します。
1. SSEのパワーに基づいたインテルウィザードの動作-software.intel.com/en-us/articles/iir-gaussian-blur-filter-implementation-using-intel-advanced-vector-extensions（vladimirovichに感謝）
2.「高速画像畳み込み」トピックの理論的基礎+正直なGausian bluerに関連するいくつかのカスタムアプリケーション-blog.ivank.net/fastest-gaussian-blur.html（Groxに感謝）
提案、コメント、建設的な批判は大歓迎です！