私は画像処理で少し遊んでいて、色の量子化がどのように機能するかを読むことにしました。少し読んだ後、Modified Median Cut Quantizationアルゴリズムを見つけました。
私はLeptonica ライブラリの C 実装のコードを読んでいて、少し奇妙だと思うものに出会いました。
ここで強調したいのは、私はこの分野の専門家ではなく、数学の専門家ではないということです。したがって、これはすべて、アルゴリズムの実装が間違っているということではなく、すべてを理解していないことが原因であると予測しています。まったく。
アルゴリズムは、vboxが最大軸に沿って分割され、次のロジックを使用して分割されるべきであると述べています。
最大の軸は、(母集団による) 中央値のピクセルでビンを見つけ、長い方の辺を選択し、その辺の中央で分割することによって分割されます。単純に中央値ピクセルのビンを短辺に配置することもできますが、細分割の初期段階では、高密度クラスターの一部として同じ vbox に低密度クラスター (細分割では考慮されない) を配置する傾向があります。将来の中央値ベースのサブディビジョンであっても、中央値の vbox 色でそれを打ち負かすクラスター。ここで使用されるアルゴリズムは、初期のサブディビジョンで特に重要であり、可視であるが人口が少ないカラー クラスターに独自の vbox を与えるのに役立ちます。これは高密度クラスターの細分化にはほとんど影響せず、最終的には vbox 内の人口がほぼ等しくなります。
議論のために、分割の過程にある vbox があり、赤い軸が最大であると仮定しましょう。レプトニカ アルゴリズムの 01297 行で、コードは次のように表示されます。
- 赤の可能なすべての緑と青のバリエーションを反復します
- 反復ごとに、赤軸に沿って見つかったピクセル (人口)の総数に追加されます
- 赤ごとに、現在の赤と前の赤の母集団を合計し、赤ごとに累積値を保存します。
注：「赤」と言うとき、反復によってカバーされる軸に沿った各点を意味します。実際の色は赤ではなく、ある程度の赤が含まれている場合があります
説明のために、赤い軸に沿って 9 つの「ビン」があり、それらの人口が次のとおりであると仮定します。
4 8 20 16 1 9 12 8 8
すべての赤いビンの反復後、partialsum配列には、上記のビンの次のカウントが含まれます。
4 12 32 48 49 58 70 78 86
合計の値は 86 になります。
それが完了したら、実際の中央値カットを実行します。赤い軸の場合、これは行 01346 で実行されます。
ビンを反復処理し、累積合計を確認します。そして、これがアルゴリズムの説明から私を突き飛ばす部分です。total/2より大きい値を持つ最初のビンを探します。
total/2は、中央値ではなく平均値より大きい値を持つビンを探していることを意味しませんか? 上記のビンの中央値は49になります
43または49を使用すると、ボックスの分割方法に大きな影響を与える可能性がありますが、アルゴリズムは一致した値があった場所の大きい側の中心に移動します。
私を少し困惑させるもう1つのことは、紙が中央値を持つビンを特定する必要があることを指定しているが、偶数のビンがある場合の処理方法について言及していないことです..中央値は(a +の結果になりますb)/2であり、ビンのいずれかにその人口数が含まれているとは限りません。したがって、選択したビンの大きい側の中心で分割が実際にどのように行われるかにより、無視できるいくつかの近似が行われていることがわかります。
少し長くなってしまったら申し訳ありませんが、数日間私を夢中にさせているので、できる限り徹底したかったのです;）