再び、判別分析法による閾値の自動計算について(1)
以前、画像を二値化するときの閾値の計算で算出する「判別分析法」（またの名を「大津の二値化」）なるものについて学びました。
そのとき参考にしたのは「実践画像処理入門
「実践画像処理入門」のP68から始まる説明によると、判別分析法では以下の手順にしたがって閾値を求めるとなっています。
- 画素数と濃度からクラス内分散とクラス間分散というものを算出し、その2つから分離度を計算する
- 上の過程を 0x01～0xFE までの全階調について施す
- 求められた254個の分離度の中から一番大きなものを求め、そのときの階調を閾値とする
これを実行すると、ステップ 1. で、画素数と濃度を求めるために256回、クラス内分散とクラス間分散を求めるために256回、ステップ 2. で254回のループが発生します。
ステップ 1. とステップ 2. は二重ループになっており、ステップ 1. が内側、ステップ 2. が外側です。
ステップ 1. では break 的にループがカットされる場合もあるんですが、ステップ 1、2. を合わせると最大で 254 * (256 + 256) = 130,048 回という、如何なものか、な回数のループが発生するんですよ、これが。
前回そのコード書いたときも、そのあまりにも多過ぎるループ回数は気になってはいましたが、画素数と濃度を求めてからでないと2つの分散が求められないので、ループを圧縮することができませんでした。
最近ネットでいろいろ資料を漁っていたら、「大津の二値化画像」というページに行き当たりました。
そこに示されたコードでは、閾値を求めるのに 256 + 256 + 256 + 256 = 1,024 回しかループをおこなっていません。以前組んだコードのループ回数 130,048 回に比べると何と 1 / 127。
何でこんなにループを少なくできるんだとコードを読んでみるに、OtsuThreshold 関数内にある4つのループはそれぞれ以下のことをしています。
- ヒストグラム配列をすべて足して総画素数を算出する
- ヒストグラム配列の各値を総画素数で割った値に置き換える
- 長さ 256 の二つの配列 w_mo、u_mo に値を格納する
- 0x00 ～ 0xFF の全階調で分散を計算する、その際、最大の分散値のときの階調を待避する
ステップ 1. は ActionScript の場合、BitmapData.width * BitmapData.height を使えば良いことが分かるので、考慮すべきループではありません。
ステップ 2. は配列内の値を、画素数から総画素数を1としたときの割合に変換しています。これもステップ 1. 同様、特に注視すべきループではないです。
残り2つのループですが、ステップ 4. のループが、以前組んだコードにおいて二重ループの外側に該当する部分であることが分ります。となると、ステップ 3. が二重ループの内側のループに該当するのかな。
二重ループから2つの一重ループになるってことは乗算から加算になるわけで、そりゃループ数も激減しようというもの。
でもこのステップ 3. は一体何をやってるんだ？ 何でループ内ループを外に出せるんだ？ 以下次回。
Comments
Tell me what you're thinking...
and oh, if you want a pic to show with your comment, go get a gravatar!