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

公開: 2022-03-11

連続平均量子化変換（SMQT）アルゴリズムは、データの編成または構造を明らかにし、ゲインやバイアスなどのプロパティを削除する非線形変換です。 The Successive Mean Quantization Transformというタイトルの論文では、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 11 11 11 11

    （各ベクトルの）平均以下の数値には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 10000 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 11 11
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 11

    分割するベクトルは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だけよりも明らかに優れています。

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で入手できます。