スタッフBLOG

おはようございます。本日の当番、プログラマのM.L.Kです。
（LはLocateのLです。Locate&Divide!）

前回のブログでは、メディアン・カット法を実装してみました。今回もしつこくメディアンでカットしていきます。

さて、早速ですが前回の実装を利用して減色してみましょう。
ＲＧＢ全てのチャンネルを含んだ２５６色への減色ということもありますし、もう少しカラフルな画像のほうが世間受けしそう、という（イヤらしい）思惑から、新しい画像を用意しました。

赤青緑に黄色と、いいカンジに各色が含まれていて、サンプルとしてはうってつけな画像ですね。

というわけで、減色結果は以下のようになりました。

うぇ、なんじゃこりゃ。
予想以上に、ひどい出来です。
まあ、長年プログラミングなぞやっていますと、一番に疑うのは自分のコードなのですが（タテマエ）、さすがに衆目に晒す事情、バグチェックはきちんと行った（つもりな）ので、単純なバグではなさそう。ムムム。

というワケで、１２８色までの減色過程を見てみると…。

あ～、何となく分かっちゃいました。
どうも、極端な値を重視した分割が行われてしまっているようですねぇ。

確か、メディアン・カットのアルゴリズムは、各チャンネルを押し並べて、最も大きな差を持っているグループを分割する、ということになっていたハズ。
その説明に従って、各チャンネル毎の最大値と最小値の差だけを比べていたのですが、どうもそれだけでは駄目なようです。

何が駄目なのか、端的に説明するとこんなカンジ？

0　64　65　66　67　68　69　70　71　72　73　74　75　76　77　78
　　　　　　　　　　　　　　　↓
0　64　65　66　67　68　69　70｜71　72　73　74　75　76　77　78
　　　　　　　　　　　　　　　↓
0　64　65　66｜67　68　69　70｜71　72　73　74　75　76　77　78
　　　　　　　　　　　　　　　↓
0　64｜65　66｜67　68　69　70｜71　72　73　74　75　76　77　78
　　　　　　　　　　　　　　　↓
0｜64｜65　66｜67　68　69　70｜71　72　73　74　75　76　77　78

各グループを中央値で分割するためもあって、最大値と最小値の差では、極端な外れ値を含むグループばかりが、分割の対象として選ばれる結果となっているようです。

望まれるのは、

0｜64　65　66｜67　68　69　70｜71　72　73　74｜75　76　77　78

といったカンジの分割なんですが…。

どうやら分割を判断するための“差（Difference）”の定義を見直す必要がありそうですね。

前回のブログの８０行目を、以下のようなコードに修正してみました。

#if 1
　　int iDifference = 0;
　　for( int j = pStats->iTop; j <= pStats->iBottom; j++)
　　{
　　　　int iIndex = pIndecies[j];
　　　　unsigned char* pElement = (unsigned char*)&pSrcImage[iIndex];
　　　　int iDifferenceTemp = (int)pElement[i] - iMedian;
　　　　iDifference += abs(iDifferenceTemp);
　　}
#else
　　int iDifference = iMax - iMin;
#endif

各データのＲＧＢそれぞれのチャンネルの値について、中央値からの差を求めて、その値の絶対値を足し合わせています。
ちなみに、絶対値を使うのは、中央値よりも大きい値と、中央値よりも小さい値とでは、その差の符号が逆になるので、そのまま足し合わせると、差自体が相殺されてしまうからです。

というわけで、減色の結果です。

うはっ。劇的に良くなっちゃいました。
さて、新しい実装によって表現された“差”とは一体なんだったのでしょうか？

修正前の“差”である最大値と最小値の差を、修正後のコードの計算に準じて表現すると、次のようになります。

　最大値－最小値　＝（最大値－中央値）－（最小値－中央値）
　　　　　　　　　＝｜最大値－中央値｜＋｜最小値－中央値｜

つまり、修正前の“差”は、最大値と最小値それぞれと中央値との差のみを取り上げたものであるのに対して、修正後の“差”は、全てのデータの値と中央値との差を考慮したものとなっているのです。

こうすることによって、データが沢山含まれるグループほど“差”の値が大きくなる傾向を持つので、分割対象として選ばれやすくなり、結果、極端な外れ値を含むグループに分割が偏ってしまう事態を、減らすことができます。

ただ、これだとあまりにも数の論理が強く働き過ぎるため、頻度が低いながらも画像の特徴となり得る色の情報を無視してしまう、という欠点もありそうですが…。

このあたり、どういう定義で“差”を表現して分割対象を選ぶのか、更なる工夫のしどころですね。

まあ、今回は思いの外うまく減色できたので、その結果を眺めてニヤニヤすることにし…、んん？？

なんか、シミみたいなのがあるじゃん！

なんなのこの、肌年齢に限界が来ちゃった、みたいなのは！

…というわけで、次回、シミ対策します。