apeescape2.com
  • メイン
  • モバイル
  • データサイエンスとデータベース
  • 設計プロセス
  • Webフロントエンド
データサイエンスとデータベース

最適化された連続平均量子化変換

逐次平均量子化変換(SMQT)アルゴリズムは、データの編成または構造を明らかにし、ゲインやバイアスなどのプロパティを削除する非線形変換です。タイトルの論文で 連続平均量子化変換 、SMQTは「音声処理と画像処理に適用されます」。画像に適用されたときのアルゴリズムは、「画像の細部への漸進的な焦点として見ることができます」。

最適化された連続平均量子化変換アルゴリズム

運営予算または資本予算に関して正しい説明は次のうちどれですか。
最適化された連続平均量子化変換アルゴリズム つぶやき

タイトルの別の論文によると ハイダイナミックレンジ画像用のSMQTベースのトーンマッピング演算子 、「詳細が強調された画像」が生成されます。このペーパーでは、この変換を画像に適用する2つの手法について説明します。



  1. 各ピクセルの輝度にSMQTを適用します。これは、各ピクセルのRGBから輝度を取得する式を示しています。

  2. RGBの各チャネルにSMQTを個別に適用します-チャネルR、G、およびBに個別に適用します。

次の図は、2つの手法の結果を示しています。

ソース: ハイダイナミックレンジ画像用のSMQTベースのトーンマッピング演算子


2番目の手法を夜のブルーインシアターの写真に適用することで、アルゴリズムが画像の詳細を徐々にズームし、元々暗闇に隠されていた詳細を明らかにする方法を確認できます。

この記事では、このアルゴリズムがどのように機能するかを詳しく見て、実際の画像処理アプリケーションでアルゴリズムのパフォーマンスを大幅に向上させる簡単な最適化について説明します。

SMQTアルゴリズム

元の論文では、アルゴリズムは抽象的な方法で説明されています。 SMQTをよりよく理解するために、いくつかの簡単な例を見ていきます。

次のベクトルがあるとします(配列のように考えることができます)。

32 48 60 64 59 47 31 15 4 0 5 18

カラー画像の場合、それぞれが特定のカラーチャネル(RGB)を表し、ベクトルの各要素が対応するピクセルの強度を表す3つの別個のベクトルと考えることができます。

SMQTアルゴリズムの適用に関連する手順は次のとおりです。

  1. ベクトルの平均を計算します。この場合は29.58です。

  2. ベクトルを2つに分割し、左半分に29.58以下の数値を残し、右半分に大きい数値を残します。

    15 4 0 5 18 32 48 60 64 59 47 31
    0 0 0 0 0 1 1 1 1 1 1 1

    2行目は、値ごとに作成するコードです。 29.58以下の値はコードで0を取得し、29.58より大きい数値は1を取得します(これはバイナリです)。

  3. これで、結果の両方のベクトルが、同じルールに従って、再帰的に個別に分割されます。この例では、最初のベクトルの平均は(15 + 4 + 0 + 5 + 18)/ 5 = 8.4であり、2番目のベクトルの平均は(32 + 48 + 60 + 64 + 59 + 47 + 31)/です。 7 = 48.7。これらの2つのベクトルのそれぞれは、さらに2つのベクトルに分割され、平均との比較に応じて、コードの2番目のビットがそれぞれに追加されます。結果は次のとおりです。

    4 0 5 15 18 32 47 31 48 60 64 59
    00 00 00 01 01 10 10 10 十一 十一 十一 十一

    (各ベクトルの)平均以下の数値には0が追加され、平均より大きい数値には1が追加されたことに注意してください。

  4. このアルゴリズムは再帰的に繰り返されます。

    0 4 5 15 18 32 31 47 48 60 64 59
    000 001 001 010 011 100 100 101 110 111 111 111
    0 4 5 15 18 31 32 47 48 60 59 64
    0000 0010 0011 0100 0110 1000 1001 1010 1100 1110 1110 1111
    0 4 5 15 18 31 32 47 48 59 60 64
    00000 00100 00110 01000 01100 10,000 10010 10100 11000 11100 11101 11110

    この時点で、すべてのベクトルには1つの要素しかありません。したがって、連続するすべてのステップで0が追加されます。これは、数値が常にそれ自体と等しいためです(0の条件は、数値が平均、つまりそれ自体以下でなければならないことです)。

これまでのところ、L = 5の量子化レベルがあります。 L = 8を使用する場合は、各コードに3つの0を追加する必要があります。各コードをバイナリから整数(L = 8の場合)に変換した結果は次のようになります。

0 4 5 15 18 31 32 47 48 59 60 64
0 32 48 64 96 128 144 160 192 224 232 240

最終的なベクトルは昇順で並べ替えられます。出力ベクトルを取得するには、入力ベクトルの元の値をそのコードで置き換える必要があります。

32 48 60 64 59 47 31 15 4 0 5 18
144 192 232 240 224 160 128 64 32 0 48 96

結果のベクトルに注意してください:

  • ゲインは削除されました。元のゲインは低ゲインで、範囲は0〜64でした。現在、ゲインは0〜240で、これはほぼ8ビット範囲全体です。元のベクトルのすべての要素に2などの数値を掛けても、すべてを2で割っても、出力ベクトルはほぼ同じになるため、ゲインが削除されると言われています。その範囲は、宛先ベクトルのほぼ全範囲になります(L = 8の場合は8ビット)。入力ベクトルに2を掛けると、出力ベクトルは実際には同じになります。これは、各ステップで、平均より下または上にあった同じ数値が引き続きその下または上にあり、同じ0または1を追加するためです。出力に。 15のような奇数は丸める必要があり、計算が異なる可能性があるため、除算した場合にのみ、結果はほぼ同じになり、完全に同じになるわけではありません。暗い画像から、全範囲を使用して、ピクセルが暗い色(0)から明るい色(240)までの範囲の画像に移行しました。
  • この例では完全に観察することはできませんが、バイアスは削除されます。これは、最小値が0であるため、バイアスがないためです。実際にバイアスがあった場合は、削除されています。任意の数「K」を取得して入力ベクトルの各要素に追加した場合、各ステップの平均の上下の数の計算は変化しません。出力は同じままです。これはまた、明るすぎて暗い色から明るい色までの範囲の画像になることができない画像を作成します。
  • 詳細が強調された画像があります。再帰的なステップごとに、実際に詳細を拡大し、それらの詳細を可能な限り明らかにすることによって出力を構築していることに注意してください。また、この手法を各RGBチャネルに適用するため、各色の元のトーンに関する情報は失われますが、可能な限り多くの詳細を明らかにします。

RGBピクセルのベクトルのような画像が与えられ、各ポイントはRの場合は8ビット、Gの場合は8ビット、Bの場合は8ビットです。そこから各色に1つずつ、合計3つのベクトルを抽出し、各ベクトルにアルゴリズムを適用できます。次に、これら3つの出力ベクトルからRGBベクトルを再度形成し、Bruin Theatreの1つと同様に、SMQTで処理された画像を取得します。

複雑

アルゴリズムでは、量子化(L)のレベルごとに、最初のパスでN個の要素を検査して各ベクトルの平均を求め、2番目のパスでこれらのN個の要素のそれぞれを対応する平均と比較する必要があります。各ベクトルを順番に分割するため。最後に、N個の要素をそれらのコードで置き換える必要があります。したがって、アルゴリズムの複雑さはO((L * 2 * N)+ N)= O((2 * L + 1)* N)、つまりO(L * N)です。

ソース: ハイダイナミックレンジ画像用のSMQTベースのトーンマッピング演算子


論文から抽出されたグラフは、O(L * N)の複雑さと一致しています。 Lが低いほど、ほぼ線形の方法で処理が高速になります(1秒あたりのフレーム数が多くなります)。処理速度を向上させるために、この論文はLの値を下げることを提案しています。「レベルLを低く選択することは、処理速度を下げる直接的な方法ですが、画質は低下します」。

改善

ここでは、画質を低下させることなく速度を向上させる方法を見つけます。変換プロセスを分析し、より高速なアルゴリズムを見つけます。これについてより完全な視点を得るために、繰り返し番号を使用した例を見てみましょう。

16 25 31 31 25 16 7 1 1 7
16 16 7 1 1 7 25 31 31 25
0 0 0 0 0 0 1 1 1 1
7 1 1 7 16 16 25 25 31 31
00 00 00 00 01 01 10 10 十一 十一
1 1 7 7 16 16 25 25 31 31
000 000 001 001 010 010 100 100 110 110

ベクトルはこれ以上分割できず、目的のLに到達するまでゼロを追加する必要があります。

簡単にするために、例に示すように、入力を0から31に、出力を0から7(L = 3)にできると仮定します。

最初のベクトルの平均を計算すると(16 + 25 + 31 + 31 + 25 + 16 + 7 + 1 + 1 + 7)/ 10 = 16は、最後のベクトル全体の平均を計算するのと同じ結果になることに注意してください。異なる順序の要素を持つまったく同じベクトル:(1 + 1 + 7 + 7 + 16 + 16 + 25 + 25 + 31 + 31)/ 10 = 16。

2番目のステップでは、各ベクトルを再帰的に計算する必要があります。したがって、最初の6つの要素である灰色の入力の平均((16 + 16 + 7 + 1 + 1 + 7)/ 6 = 8)と、最後の4つの要素である空白の入力の平均を計算します。 ((25 + 31 + 31 + 25)/ 4 = 28):

16 16 7 1 1 7 25 31 31 25

最後のベクトル、つまり完全に順序付けられたベクトルを使用した場合、結果は同じであることに再度注意してください。最初の6つの要素には((1 + 1 + 7 + 7 + 16 + 16)/ 6 = 8)があり、最後の4つの要素には((25 + 25 + 31 + 31)/ 4 = 28)があります。 。単なる加算なので、被加数の順序は重要ではありません。

1 1 7 7 16 16 25 25 31 31

同じことが次のステップにも当てはまります。

7 1 1 7 16 16 25 25 31 31

計算は最後のベクトルと同じです:((7 + 1 + 1 + 7)/ 4 = 4)は((1 + 1 + 7 + 7)/ 4 = 4)に等しくなります。

そして、同じことが残りのベクトルとステップにも当てはまります。

平均の計算は、間隔内の要素の値の合計を間隔内の要素の数で割ったものです。これは、これらすべての値を事前に計算し、この計算をL回繰り返さないようにすることができることを意味します。

FastSMQTアルゴリズムと呼ぶものを例に適用する手順を見てみましょう。

  1. 以下に示すように、32列と3行のテーブルを作成します。テーブルの最初の行はテーブルのインデックス(0から31)を表し、テーブルをコーディングするときに含める必要はありません。ただし、例をわかりやすくするために明示的に示されています。

  2. 各値の頻度を数えて、N個の要素を繰り返します。この例では、要素1、7、16、25、および31の頻度はすべて2です。他のすべての要素の頻度は0です。このステップの複雑さはO(N)です。

  3. 周波数ベクトルが入力されたので、そのベクトル(入力ベクトルではなく周波数ベクトル)を反復する必要があります。 N個の要素を繰り返すことはもうありませんが、R(Rは2 ^ Lの範囲にあります)、この場合は32(0から31)です。ピクセルを処理する場合、Nは数百万(メガピクセル)になる可能性がありますが、Rは通常256(各色に1つのベクトル)です。この例では32です。テーブルの次の2行を同時に入力します。これらの行の最初の行(表の2番目)には、これまでの頻度の合計が含まれます。 2番目(表の3番目)には、これまでに表示されたすべての要素の値の合計が含まれます。

    この例では、1に到達すると、これまでに2つの1が表示されているため、テーブルの2行目に2を配置します。また、1 + 1 = 2であるため、テーブルの3行目に2を配置します。7になるまで、次の各位置にこれら2つの値を書き込み続けます。数値7が2回表示されるため、2を加算します。これまでに4つの数値(1、1、7、7)が表示されたため、2行目のアキュムレータ。そして、3番目の行に7 + 7 = 14を追加すると、1 + 1 + 7 + 7 = 16であるため、2 + 14 = 16になります。これらの要素の反復が完了するまで、このアルゴリズムを続行します。このステップの複雑さはO(2 ^ L)であり、この場合はO(32)であり、RGBピクセルを操作する場合はO(256)です。

    私 0 1 2 ..。 6 7 8 ..。 15 16 17 ..。 24 25 26 ..。 30 31
    n 0 2 0 ..。 0 2 0 ..。 0 2 0 ..。 0 2 0 ..。 0 2
    n-累積 0 2 2 ..。 2 4 4 ..。 4 6 6 ..。 6 8 8 ..。 8 10
    和 0 2 2 ..。 2 16 16 ..。 16 48 48 ..。 48 98 98 ..。 98 160
  4. 次のステップは、頻度が0の要素を含む列をテーブルから削除することです。例をより明確にするために、2番目の行も関連性がなくなったため、削除します。

    私 1 7 16 25 31
    n 2 4 6 8 10
    和 2 16 48 98 160
  5. 最後の(完全に順序付けられた)ベクトルを使用して各ステップの計算を実行でき、結果は同じままであることに注意してください。ここで、この表には、すべての事前計算がすでに行われた最後のベクトルがあることに注意してください。

    基本的に、この小さなベクトルに対してSMQTアルゴリズムを実行する必要がありますが、最初に使用した元のベクトルに対して実行するのとは異なり、これははるかに簡単です。

    拡張現実と複合現実の違い

    まず、すべてのサンプルの平均を計算する必要があります。 sum [31] / n [31] = 160/10 = 16で簡単に見つけることができます。したがって、テーブルを2つのベクトルに分割し、それぞれのバイナリコードの記述を開始します。

    私 1 7 16 25 31
    n 2 4 6 8 10
    和 2 16 48 98 160
    コード 0 0 0 1 1

    ここで、各ベクトルを再度分割します。最初のベクトルの平均は次のとおりです。sum[16] / n [16] = 48/6 =8。2番目のベクトルの平均は次のとおりです。(sum [31] – sum [16])/(n [31] – n [16])=(160 – 48)/(10 – 6)= 112/4 = 28。

    私 1 7 16 25 31
    n 2 4 6 8 10
    和 2 16 48 98 160
    コード 00 00 01 10 十一

    分割するベクトルは1つだけ残っています。平均は次のとおりです。sum[7] / n [7] = 16/4 = 4。

    私 1 7 16 25 31
    n 2 4 6 8 10
    和 2 16 48 98 160
    コード 000 001 010 100 110

    ご覧のとおり、元のアルゴリズムに従った場合、各要素のコードは同じです。また、N個の要素を持つベクトルよりもはるかに小さいベクトルでSMQTを実行し、平均を見つけるために必要なすべての値を事前に計算したので、結果のベクトルを計算するのは簡単で高速です。

    このステップの複雑さはO(L *(2 ^ L))であり、L = 8の場合、実際の画像処理のニーズでは、O(8 *(256))= O(2048)=定数です。

  6. 最後のステップは、N個の要素を繰り返し、各要素のコードで要素を置き換えることです:element [i] = code [i]。複雑さはO(N)です。 FastSMQTの複雑さは、O(N)+ O(2 ^ L)+ O(L *(2 ^ L))+ O(N)= O(2 * N)+ O((L + 1)*(2 ^ L))= O(N + L *(2 ^ L))。

並列処理

両方のアルゴリズムを並列化できますが、複数のベクトルを変換する必要がある場合は、コアごとに1つのアルゴリズムを実行する方が効率的です。たとえば、画像を処理する場合、これら3つの計算のそれぞれを並列化する代わりに、異なるコアで各RGBチャネルを処理できます。

SMQTアルゴリズムを並列化するために、ベクトルを2つに分割する場合、コアが使用可能な場合は、新しいコアで各サブベクトルを処理できます(実際には、現在のコアで1つのサブベクトル、新しいコアでもう1つのサブベクトル)。これは、使用可能なコアの総数に達するまで再帰的に実行できます。コードによる値の置換は、に対して並行して実行することもできます。

FastSMQTアルゴリズムも並列化できます。最初のステップでは、入力ベクトルを使用可能なコアの数に分割する必要があります(C)。これらのパーツごとに周波数カウントのベクトルを1つ作成し、並行して入力する必要があります。次に、これらのベクトルの値を1つの結果の周波数ベクトルに追加します。並列化できる次のステップは、値をコードで置き換える最後のステップです。これは、に対して並行して実行できます。

複雑さの比較

元のSMQTアルゴリズムの全体的な複雑さはO((2 * L + 1)* N)であり、これはO(L * N)です。

FastSMQTの複雑さは、O(N)+ O(2 ^ L)+ O(L *(2 ^ L))+ O(N)= O(2 * N)+ O((L + 1)*(2 ^ L))= O(N + L *(2 ^ L))。

Lが固定されているとすると、複雑さは両方ともO(N)になります。ただし、FastSMQTの場合、Nを乗算する定数ははるかに小さく、処理時間に大きな違いがあります。

次のグラフは、画像処理の場合であるL = 8のSMQTアルゴリズムとFastSMQTアルゴリズムの両方のパフォーマンスを比較しています。グラフは、N個の要素の処理にかかる時間(ミリ秒単位)を示しています。 L = 8の場合のSMQTの複雑さ(定数を含む)はO(17 * N)であるのに対し、FastSMQTの場合はO(2 * N + 2304)であることに注意してください。

Nが大きいほど、SMQTがイメージを処理するのに時間がかかります。一方、FastSMQTの場合、成長ははるかに遅くなります。

Nの値がさらに大きい場合、パフォーマンスの違いははるかに明白です。

ここで、SMQTは特定の画像を処理するのに最大数秒かかりますが、FastSMQTは依然として「数ミリ秒」ゾーン内にあります。

複数のコア(この場合は2つ)がある場合でも、FastSMQTはSMQTだけよりも明らかに優れています。

SQLServerのパフォーマンスチューニングのベストプラクティス

FastSMQTはLに依存しません。一方、SMQTはLの値に線形依存します。たとえば、N = 67108864の場合、SMQTの実行時間はLの値の増加とともに増加しますが、FastSMQTは次のことを行いません。

結論

すべての最適化手法がすべてに適用できるわけではありません アルゴリズム 、およびアルゴリズムのパフォーマンスを改善するための鍵は、アルゴリズムがどのように機能するかについての洞察の中に隠されていることがよくあります。このFastSMQTアルゴリズムは、値を事前計算する可能性と平均計算の性質を利用します。その結果、元のSMQTよりも高速な処理が可能になります。速度はLの増分の影響を受けませんが、メモリ使用量が2 ^ Lであるため、Lを通常の8より大きくすることはできません。これは、8の場合は許容可能な256(度数分布表の列数)ですが、パフォーマンスは向上します。明らかな実用上の利点があります。

この速度の向上により、MiddleMatterはアルゴリズムを iOSアプリケーション (と Androidアプリケーション )暗い場所で撮影された写真やビデオを改善します。この改善により、アプリケーションでビデオ処理を実行することが可能になりました。 ios デバイス。

SMQTおよびFastSMQTアルゴリズムのC ++コードは次のとおりです。 GitHubで入手可能 。

AnsiblePlaybookでElasticStackを自動的に更新する

技術

AnsiblePlaybookでElasticStackを自動的に更新する
Pythonと財務–スプレッドシートをパワーアップ

Pythonと財務–スプレッドシートをパワーアップ

財務プロセス

人気の投稿
PHPおよびMySQLでのUTF-8エンコーディングのガイド
PHPおよびMySQLでのUTF-8エンコーディングのガイド
ミニチュートリアル–設計プロセス全体でFigmaの機能を活用
ミニチュートリアル–設計プロセス全体でFigmaの機能を活用
ACRAとCloudantを使用した自動Androidクラッシュレポート
ACRAとCloudantを使用した自動Androidクラッシュレポート
デザインにおけるAIの現在と未来(インフォグラフィック付き)
デザインにおけるAIの現在と未来(インフォグラフィック付き)
UIとUX:ユーザーインターフェイスデザインの重要なガイド
UIとUX:ユーザーインターフェイスデザインの重要なガイド
 
開発者向けのトップ10フロントエンドデザインルール
開発者向けのトップ10フロントエンドデザインルール
ソフトウェア統合の合理化:ApacheCamelチュートリアル
ソフトウェア統合の合理化:ApacheCamelチュートリアル
2019年のベンチャーキャピタル業界の状況(インフォグラフィック付き)
2019年のベンチャーキャピタル業界の状況(インフォグラフィック付き)
マーケットプレイスオペレーション担当副社長
マーケットプレイスオペレーション担当副社長
挑戦的なM&A市場で最大の価値のためにビジネスを売る
挑戦的なM&A市場で最大の価値のためにビジネスを売る
人気の投稿
  • 資金調達の成功報酬
  • 外国為替リスクの主な種類は何ですか
  • フレームワークを構築する方法
  • デザイン思考は________のプロセスを提供することができます。
  • 資本予算は、財務および経理担当者の関心事にすぎません。
  • scorpとccorpの違い
  • フルスタックJavaScriptとは
カテゴリー
トレンド ライフスタイル リモートの台頭 その他 設計プロセス ブランドデザイン 財務プロセス 製品ライフサイクル 仕事の未来 アジャイル

© 2021 | 全著作権所有

apeescape2.com