大津の二値化法

大津の二値化法とは、コンピュータビジョンや画像処理において、自動画像しきい値処理を行うために使用される手法。その名は大津展之にちなむ。最も単純な形式では、アルゴリズムはピクセルをforegroundとbackgroundの2つのクラスに分ける1つの強度しきい値を返す。このしきい値はクラス内の強度分散を最小化することにより、または同等にクラス間の分散を最大化することにより決定される。大津の二値化はフィッシャーの判別分析の1次元の離散に相当するものであり、ジェンクス最適化法に関連しており、強度ヒストグラムで行われる大域最適なK平均法と同等である。マルチレベルのしきい値処理へ拡大することは最初の論文で説明されており、以降計算効率の高い実装が提案されている。

1. 大津の二値化
---------

アルゴリズムは、2つのクラスの分散の加重和として定義されるクラス内分散を最小化するしきい値を探す。

加重とはしきい値により分けられた2つのクラスの確率であり、とはこれら2つのクラスの分散である。

クラスの確率はヒストグラムの個のビンから計算される。

2つのクラスでは、クラス内分散を最小化することはクラス間分散を最大化することと同じである。

これはクラス確率とクラス平均で表され、クラス平均、およびは、

である。以上の関係は以下のように簡単に確かめることができる。

クラス確率とクラス平均は、繰り返し計算することができる。このアイデアは効果的なアルゴリズムを生む。

1.1. アルゴリズム
-----------

各強度レベルのヒストグラムと確率を計算する。
との初期値を設定する。
最大強度までの全ての考えうるしきい値で次のステップを行う。
とを更新する。
を計算する。
望ましいしきい値はが最大となる値である。

1.2. MATLABまたはOctaveでの実装
------------------------

histogramCountsはさまざまなグレーレベルのグレースケール画像の256画素のヒストグラムである。levelは画像のしきい値  である。

function level = otsu total = sum; % total number of pixels in the image %% OTSU automatic thresholding top = 256; sumB = 0; wB = 0; maximum = 0.0; sum1 = dot; for ii = 1:top wF = total - wB; if wB > 0 && wF > 0 mF =  / wF; val = wB * wF *  - mF) *  - mF); if  level = ii; maximum = val; end end wB = wB + histogramCounts; sumB = sumB +  * histogramCounts; end end

MatlabにはImage Processing Toolboxに組み込み関数graythreshとmultithreshがあり、それぞれ大津の手法とマルチ大津の手法で実装されている。

1.3. Pythonでの実装
---------------

この実装にはNumPyライブラリが必要である def compute_otsu_criteria:

create the thresholded imagethresholded_im = np.zeros thresholded_im[im >= th] = 1

compute weightsnb_pixels = im.size nb_pixels1 = np.count_nonzero weight1 = nb_pixels1 / nb_pixels weight0 = 1 - weight1

if one the classes is empty, eg all pixels are below or above the threshold, that threshold will not be considered
in the search for the best thresholdif weight1 == 0 or weight0 == 0: return np.nan

find all pixels belonging to each classval_pixels1 = im[thresholded_im == 1] val_pixels0 = im[thresholded_im == 0]

compute variance of these classesvar0 = np.var if len > 0 else 0 var1 = np.var if len > 0 else 0

return weight0 * var0 + weight1 * var1

im = # load your image as a numpy array.

For testing purposes, one can use for example im = np.random.randint)
testing all thresholds from 0 to the maximum of the imagethreshold_range = range+1) criterias = [compute_otsu_criteria for th in threshold_range]

best threshold is the one minimizing the Otsu criteriabest_threshold = threshold_range[np.argmin]

<WtXmlEndTag />OpenCVやScikit-imageなどの画像処理専用のPythonライブラリは、アルゴリズムの組み込み実装を提案する。

2. 限界とバリエーション
-------------

大津の方法は、ヒストグラムが2つのピークの間に深く鋭い谷を持つ二峰性分布を有するときにうまく機能する。

他の全ての大域的なしきい値処理と同様に、ノイズが大きく、対象のサイズが小さく、明暗が不均一で、クラス内の分散がクラス間の分散よりも大きい場合にパフォーマンスが低下する。このような場合、大津の方法を局所的に適用することが開発されている。

さらに、大津の方法の数学的根拠は、画像のヒストグラムを分散が等しくサイズが等しい2つの正規分布の混合としてモデル化する。しかし、大津のしきい値処理はこれらの仮定を満たさない場合でも満足のいく結果をもたらす可能性がある。同様に統計検定は、動作の仮定が完全に満たされていない場合でも正しく実行される。しかし、これらの仮定から生じる深刻な逸脱を無くすために、Kittler-Illingworthの方法などの大津の方法のいくつかのバリエーションが提案されている。

2.1. ノイズの多い画像に対するバリエーション
------------------------

大津の方法の限界に対処するためにさまざまな拡張が開発されてきた。人気のある拡張の1つは、ノイズの多い画像のオブジェクトセグメンテーションのタスクに適した2次元大津の方法である。ここでは、特定のピクセルの強度値をそのすぐ近傍の平均強度と比較することでセグメンテーション結果を改良する。

各ピクセルで、近傍の平均グレーレベル値が計算される。与えられたピクセルのグレーレベルを個の離散値に分割し、平均グレーレベルも同じ個の値に分割する。その後、ピクセルのグレーレベルと近傍の平均のペアが形成される。各ペアは個の考えうる2次元ビンの1つに属する。ペアの出現の総数を画像のピクセルの総数で割ったものは、2次元ヒストグラムで同時確率密度関数を定義する。

そして、2次元大津の方法は、2次元ヒストグラムに基づいて次のように開発されている。

2つのクラスの確率は、次のように表せる。

2つのクラスの強度平均ベクトルと合計平均ベクトルは次のように表せる。

ほとんどの場合、非対角の確率はわずかであるため、次のことを簡単に確認することができる。

クラス間離散行列は次のように定義される。

離散行列のトレースは次のように表される。

ここで

1次元の大津の方法と同様に、最適なしきい値は、を最大化することで取得される。

2.1.1. アルゴリズム
-------------

とは、1次元の大津の方法と同様に繰り返し取得される。との値は、の最大値を取得するまで変更される。つまり、

max,s,t = 0; for ss: 0 to L-1 do for tt: 0 to L-1 do evaluate tr; if tr > max max = tr; s = ss; t = tt; end if end for end for return s,t;

を評価するために、高速再起動的プログラミングアルゴリズムを使用して時間パフォーマンスを向上させることができることに留意してください。しかし、動的プログラミングのアプローチを使用しても、2次元大津の方法は依然として時間計算量が非常に複雑である。したがって、計算コストを削減するために多くの研究が行われてきた。

合計領域テーブルを使用して3つのテーブルを作製する場合は、を合計し、を合計し、を合計し、その時のランタイムの複雑性は, O)の最大値である。しきい値に関して粗い解像度のみが必要な場合はN_binsを減らすことができることに注意してください。

:en:Summed-area table参照

2.1.2. Matlabでの実装
-----------------

関数の入力と出力

histsは、グレースケール値と近傍平均グレースケール値のペアのの2次元ヒストグラムである。

totalは、所与の画像のペアの数である。これは各方向の2次元ヒストグラムのビンの数により決まる。

thresholdは取得されたしきい値である。

function threshold = otsu_2D maximum = 0.0; threshold = 0; helperVec = 0:255; mu_t0 = sum.*hists)); mu_t1 = sum.*hists)); p_0 = zeros; mu_i = p_0; mu_j = p_0; for ii = 1:256 for jj = 1:256 if jj == 1 if ii == 1 p_0 = hists; else p_0 = p_0 + hists; mu_i = mu_i+*hists; mu_j = mu_j; end else p_0 = p_0+p_0-p_0+hists; % THERE IS A BUG HERE. INDICES IN MATLAB MUST BE HIGHER THAN 0. ii-1 is not valid mu_i = mu_i+mu_i-mu_i+*hists; mu_j = mu_j+mu_j-mu_j+*hists; end

if  == 0) continue; end if  == total) break; end tr = -p_0*mu_t0)^2 + -p_0*mu_t1)^2)/*));

if  threshold = ii; maximum = tr; end end end end<WtXmlEndTag />

2.2. 不平衡な画像に対するバリエーション
----------------------

画像のクラスのグレーレベルは正規分布とみなすことができるが、サイズや分散が等しくない場合、大津のアルゴリズムの仮定は満たされない。Kittler-Illingworthのアルゴリズムはこのような場合を処理するための大津の方法のバリエーションである。このアルゴリズムを数学的に説明する方法はいくつかある。それらの1つは、試験される各しきい値について結果の2値画像の正規分布のパラメータがデータが与えられた最尤推定により推定されたことを考慮することである。

このアルゴリズムは大津の方法よりも優れているように見えることがあるが、推定される新しいパラメータが導入されるためアルゴリズムが過剰パラメータ化されて不安定になる可能性がある。大津の方法からの仮定が少なくとも部分的に有効であると考えられる多くの場合において、オッカムの剃刀に従ってKittler-Illingworthのアルゴリズムよりも大津の方法を優先する方が好ましい場合がある。

3. 出典
-----

4. 外部リンク
--------

[1] as GIMP-plugin using Script-Fu 
[2] – covers the Otsu method
[3] using Otsu's method to do the threshold
[4] with a working example and Java implementation
[5] in ITK
[6] – a straightforward C# implementation with explanation
[7]
[8]