Otsu methodu

Bilgisayarla görme ve görüntü işlemede, otomatik görüntü eşikleme yapmak için Nobuyuki Otsu (大津展之 Ōtsu Nobuyuki) tarafından oluşturulan Otsu methodu kullanılmaktadır.^[1] En basit haliyle, algoritma pikselleri ön plan ve arka plan olmak üzere iki sınıfa ayıran tek bir yoğunluk eşiği döndürmektedir. Bu eşik, sınıf içi yoğunluk varyansını en aza indirerek veya eşdeğer olarak, sınıflar arası varyansı maksimize ederek belirlenmektedir.^[2] Otsu'nun yöntemi, Fisher's Discriminant Analysis'in tek boyutlu ayrık bir analoğudur. Jenks optimizasyon yöntemiyle ilgilidir ve yoğunluk histogramında gerçekleştirilen global olarak en uygun k-ortalamalara eşdeğerdir.^[3] Çok seviyeli eşiklemenin genişletilmesi orijinal belgede açıklanmıştır ve o zamandan beri hesaplama açısından verimli uygulamalar önerilmiştir.^[2][4][5]

Algoritma, iki sınıfın ağırlıklı bir toplamı olarak tanımlanan sınıf içi varyansı en aza indiren eşiği kapsamlı bir şekilde arar.

${\displaystyle \sigma _{w}^{2}(t)=\omega _{0}(t)\sigma _{0}^{2}(t)+\omega _{1}(t)\sigma _{1}^{2}(t)}$

${\displaystyle \omega _{0}}$ ve ${\displaystyle \omega _{1}}$ ağırlıkları, ${\displaystyle t}$ eşiği ile ayrılan iki sınıfın olasılıklarıdır. ${\displaystyle \sigma _{0}^{2}}$ ve ${\displaystyle \sigma _{1}^{2}}$ bu iki sınıfın varyanslarıdır.

${\displaystyle \omega _{0,1}(t)}$ sınıf olasılığı, histogramın ${\displaystyle L}$ kutularından aşağıdaki gibi hesaplanır:

${\displaystyle {\begin{aligned}\omega _{0}(t)&=\sum _{i=0}^{t-1}p(i)\\[4pt]\omega _{1}(t)&=\sum _{i=t}^{L-1}p(i)\end{aligned}}}$

2 sınıf için, sınıf içi varyansı en aza indirmek, sınıflar arası varyansı en üst düzeye çıkarmakla eşdeğerdir.^[2]

${\displaystyle {\begin{aligned}\sigma _{b}^{2}(t)&=\sigma ^{2}-\sigma _{w}^{2}(t)=\omega _{0}(\mu _{0}-\mu _{T})^{2}+\omega _{1}(\mu _{1}-\mu _{T})^{2}\\&=\omega _{0}(t)\omega _{1}(t)\left[\mu _{0}(t)-\mu _{1}(t)\right]^{2}\end{aligned}}}$

Bu, ${\displaystyle \omega }$ sınıf olasılıkları cinsinden ifade edilir. Sınıf ${\displaystyle \mu }$ anlamına gelir. Burada sınıf ${\displaystyle \mu _{0}(t)}$, ${\displaystyle \mu _{1}(t)}$ ve ${\displaystyle \mu _{T}}$ anlamına gelir.

${\displaystyle {\begin{aligned}\mu _{0}(t)&={\frac {\sum _{i=0}^{t-1}ip(i)}{\omega _{0}(t)}}\\[4pt]\mu _{1}(t)&={\frac {\sum _{i=t}^{L-1}ip(i)}{\omega _{1}(t)}}\\\mu _{T}&=\sum _{i=0}^{L-1}ip(i)\end{aligned}}}$

Aşağıdaki ilişkiyi bunlarla açıklayabiliriz:

${\displaystyle {\begin{aligned}\omega _{0}\mu _{0}+\omega _{1}\mu _{1}&=\mu _{T}\\\omega _{0}+\omega _{1}&=1\end{aligned}}}$

Sınıf olasılıkları ve sınıf ortalamaları yinelemeli olarak hesaplanabilir. Bu fikir etkili bir algoritma sağlamaktadır.

1. Her yoğunluk seviyesinin histogramı ve olasılıkları hesaplanır.
2. İlk ${\displaystyle \omega _{i}(0)}$ ve ${\displaystyle \mu _{i}(0)}$ ayarlanır.
3. Adım adım ${\displaystyle t=1,\ldots }$ tüm olası eşikler maksimum yoğunluk için hesaplanır.
   1. ${\displaystyle \omega _{i}}$ ve ${\displaystyle \mu _{i}}$ güncellenir.
   2. ${\displaystyle \sigma _{b}^{2}(t)}$ hesaplanır.
4. İstenen eşik maksimum ${\displaystyle \sigma _{b}^{2}(t)}$ değerine karşılık gelir.

histogramSayacı farklı gri düzeylerinde (8 bitlik görüntüler için tipik) bir gri tonlamalı görüntünün 256 elemanlı bir histogramıdır.

function seviye = otsu(histogramSayacı)
total = sum(histogramSayacı); % görüntüdeki toplam piksel sayısı
%% OTSU otomatik eşiklemesi
top = 256;
toplamB = 0;
wB = 0;
maksimum = 0.0;
toplam1 = dot(0:top-1, histogramSayacı);
for ii = 1:top
    wF = total - wB;
    if wB > 0 && wF > 0
        mF = (toplam1 - toplamB) / wF;
        val = wB * wF * ((toplamB / wB) - mF) * ((toplamB / wB) - mF);
        if ( val >= maksimum )
            seviye = ii;
            maksimum = val;
        end
    end
    wB = wB + histogramSayacı(ii);
    toplamB = toplamB + (ii-1) * histogramSayacı(ii);
end
end

Matlab, sırasıyla Otsu methodu ve Multi Otsu methoduyla uygulanan Görüntü İşleme Araç Kutusu'nda graythresh() ve multithresh() yerleşik fonksiyonlarına sahiptir.

Otsu methodunda, histogramın iki modlu dağılıma sahip olduğu ve iki tepe arasında derin ve keskin bir vadiye sahip olduğu varsayılabilirse, nispeten iyi bir performans sergilemektedir. Ancak nesne alanı, arka plan alanıyla karşılaştırıldığında nesne alanı küçükse, histogram artık iki modluluk göstermez.^[6] Ve nesnenin varyansları ve arka plan yoğunlukları, ortalama farkla karşılaştırıldığında büyükse veya görüntü, ek gürültü tarafından ciddi şekilde bozulursa, gri seviye histogramının keskin vadisi bozulmaktadır. Ardından, Otsu'nun yöntemiyle belirlenen olası yanlış eşik, segmentasyon hatasıyla sonuçlanmaktadır. (Burada nesne boyutunu, nesne alanının tüm görüntü alanına oranı ve ortalama farkı, nesnenin ve arka planın ortalama yoğunluklarının farkı olarak tanımlıyoruz)

Ampirik sonuçlar, nesne segmentasyonu için kullanılan global eşikleme tekniklerinin performansının (Otsu algoritması dahil) küçük nesne boyutu, ön plan ve arka plan pikselleri arasındaki küçük ortalama fark, nesneye ait olan ve nesneye ait olan piksellerin büyük varyansları ile sınırlı olduğunu göstermektedir.^[7]

Otsu methodunun sınırlamalarını ele almak için çeşitli uzantılar geliştirilmiştir. Bir popüler uzantı, gürültülü görüntülerde nesne bölütleme görevi için daha iyi performans gösteren iki boyutlu Otsu methodudur. Burada, segmentasyon sonuçlarını iyileştirmek için belirli bir pikselin yoğunluk değeri, yakın komşuluğunun ortalama yoğunluğu ile karşılaştırılmaktadır.^[8]

Her pikselde, komşuların ortalama gri seviye değeri hesaplanır. Verilen pikselin gri seviyesi ${\displaystyle L}$ kadar ayrık değerlere bölünür ve ortalama gri seviyesi de aynı ${\displaystyle L}$ değerlerine bölünür. Ardından bir çift oluşturulur: ${\displaystyle (i,j)}$ her pikselin gri seviyesi ve komşuların ortalaması. Her çift, ${\displaystyle L\times L}$ olası 2 boyutlu kutulardan birine aittir . Her bir ${\displaystyle (i,j)}$ çiftinin toplam sayısı ${\displaystyle f_{ij}}$ fonksiyonu olarak verilir. ${\displaystyle N}$ görüntüsündeki toplam piksel sayısına bölünür, 2 boyutlu bir histogramda birleşik olasılık kütle fonksiyonunu tanımlar:

${\displaystyle P_{ij}={\frac {f_{ij}}{N}},\qquad \sum _{i=0}^{L-1}\sum _{j=0}^{L-1}P_{ij}=1}$

2 boyutlu Otsu methodu, 2 boyutlu histograma dayalı olarak aşağıdaki gibi geliştirilmiştir.

İki sınıfın olasılıkları şu şekilde gösterilebilir:

${\displaystyle {\begin{aligned}\omega _{0}&=\sum _{i=0}^{s-1}\sum _{j=0}^{t-1}P_{ij}\\\omega _{1}&=\sum _{i=s}^{L-1}\sum _{j=t}^{L-1}P_{ij}\end{aligned}}}$

İki sınıfın yoğunluk ortalama değer vektörleri ve toplam ortalama vektör aşağıdaki gibi ifade edilebilir:

${\displaystyle {\begin{aligned}\mu _{0}&=[\mu _{0i},\mu _{0j}]^{T}=\left[\sum _{i=0}^{s-1}\sum _{j=0}^{t-1}i{\frac {P_{ij}}{\omega _{0}}},\sum _{i=0}^{s-1}\sum _{j=0}^{t-1}j{\frac {P_{ij}}{\omega _{0}}}\right]^{T}\\\mu _{1}&=[\mu _{1i},\mu _{1j}]^{T}=\left[\sum _{i=s}^{L-1}\sum _{j=t}^{L-1}i{\frac {P_{ij}}{\omega _{1}}},\sum _{i=s}^{L-1}\sum _{j=t}^{L-1}j{\frac {P_{ij}}{\omega _{1}}}\right]^{T}\\\mu _{T}&=[\mu _{Ti},\mu _{Tj}]^{T}=\left[\sum _{i=0}^{L-1}\sum _{j=0}^{L-1}iP_{ij},\sum _{i=0}^{L-1}\sum _{j=0}^{L-1}jP_{ij}\right]^{T}\end{aligned}}}$

Çoğu durumda köşegen dışı olasılık ihmal edilebilir, bu nedenle doğrulaması kolaydır:

${\displaystyle \omega _{0}+\omega _{1}\cong 1}$

${\displaystyle \omega _{0}\mu _{0}+\omega _{1}\mu _{1}\cong \mu _{T}}$

Sınıflar arası ayrık matris şu şekilde tanımlanır:

${\displaystyle S_{b}=\sum _{k=0}^{1}\omega _{k}[(\mu _{k}-\mu _{T})(\mu _{k}-\mu _{T})^{T}]}$

Ayrık matrisin izi şu şekilde ifade edilebilir:

${\displaystyle {\begin{aligned}&\operatorname {tr} (S_{b})\\[4pt]={}&\omega _{0}[(\mu _{0i}-\mu _{Ti})^{2}+(\mu _{0j}-\mu _{Tj})^{2}]+\omega _{1}[(\mu _{1i}-\mu _{Ti})^{2}+(\mu _{1j}-\mu _{Tj})^{2}]\\[4pt]={}&{\frac {(\mu _{Ti}\omega _{0}-\mu _{i})^{2}+(\mu _{Tj}\omega _{0}-\mu _{j})^{2}}{\omega _{0}(1-\omega _{0})}}\end{aligned}}}$

${\displaystyle \mu _{i}=\sum _{i=0}^{s-1}\sum _{j=0}^{t-1}iP_{ij}}$

${\displaystyle \mu _{j}=\sum _{i=0}^{s-1}\sum _{j=0}^{t-1}jP_{ij}}$

Tek boyutlu Otsu methoduna benzer şekilde, optimal eşik ${\displaystyle (s,t)}$, ${\displaystyle \operatorname {tr} (S_{b})}$maksimize edilerek elde edilir.

${\displaystyle s}$ ve ${\displaystyle t}$ tek boyutlu Otsu methoduna benzer şekilde yinelemeli olarak elde edilmektedir. ${\displaystyle s}$ ve ${\displaystyle t}$ değerleri, maksimum ${\displaystyle \operatorname {tr} (S_{b})}$ elde edilene kadar değiştirilir.

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

${\displaystyle \operatorname {tr} (S_{b})}$ fonksiyonunu değerlendirmek ve zaman performansını iyileştirmek için hızlı bir özyinelemeli dinamik programlama algoritması kullanılabilir.^[9] Bununla birlikte, dinamik programlama yaklaşımıyla bile, 2d Otsu methodu hala büyük zaman karmaşıklığına sahiptir. Bu nedenle, hesaplama maliyetini azaltmak için birçok araştırma yapılmıştır.^[10]

${\displaystyle P_{ij}}$, ${\displaystyle i*P_{ij}}$ ve ${\displaystyle j*P_{ij}}$ üzerinde toplamalar yapılarak 3 tablo oluşturulur. Çalışma zamanı karmaşıklığı maksimum (O(N_pixels), O(N_bins*N_bins)) olur. Eşik açısından yalnızca kaba çözünürlük gerekiyorsa, N_bins azaltılabilir.

Fonksiyon giriş ve çıkışları:

hists; gri tonlamalı değer ve komşu ortalama gri tonlamalı değer çiftinin ${\displaystyle 256\times 256}$ 2D histogramıdır.

total; verilen görüntüdeki çiftlerin sayısıdır. 2D histogramın her bir yöndeki kutularının sayısı ile belirlenir.

threshold; elde edilen eşik değeridir.

function threshold = otsu_2D(hists, total)
maximum = 0.0;
threshold = 0;
helperVec = 0:255;
mu_t0 = sum(sum(repmat(helperVec',1,256).*hists));
mu_t1 = sum(sum(repmat(helperVec,256,1).*hists));
p_0 = zeros(256);
mu_i = p_0;
mu_j = p_0;
for ii = 1:256
    for jj = 1:256
        if jj == 1
            if ii == 1
                p_0(1,1) = hists(1,1);
            else
                p_0(ii,1) = p_0(ii-1,1) + hists(ii,1);
                mu_i(ii,1) = mu_i(ii-1,1)+(ii-1)*hists(ii,1);
                mu_j(ii,1) = mu_j(ii-1,1);
            end
        else
            p_0(ii,jj) = p_0(ii,jj-1)+p_0(ii-1,jj)-p_0(ii-1,jj-1)+hists(ii,jj);
            mu_i(ii,jj) = mu_i(ii,jj-1)+mu_i(ii-1,jj)-mu_i(ii-1,jj-1)+(ii-1)*hists(ii,jj);
            mu_j(ii,jj) = mu_j(ii,jj-1)+mu_j(ii-1,jj)-mu_j(ii-1,jj-1)+(jj-1)*hists(ii,jj);
        end

        if (p_0(ii,jj) == 0)
            continue;
        end
        if (p_0(ii,jj) == total)
            break;
        end
        tr = ((mu_i(ii,jj)-p_0(ii,jj)*mu_t0)^2 + (mu_j(ii,jj)-p_0(ii,jj)*mu_t1)^2)/(p_0(ii,jj)*(1-p_0(ii,jj)));

        if ( tr >= maximum )
            threshold = ii;
            maximum = tr;
        end
    end
end
end

• Implementation of Otsu's thresholding method 8 Mart 2021 tarihinde Wayback Machine sitesinde arşivlendi.
• Lecture notes on thresholding 17 Şubat 2016 tarihinde Wayback Machine sitesinde arşivlendi.
• A plugin for ImageJ 4 Kasım 2015 tarihinde Wayback Machine sitesinde arşivlendi.
• A full explanation of Otsu's method 18 Ekim 2015 tarihinde Wayback Machine sitesinde arşivlendi.
• Implementation of Otsu's method 24 Ekim 2015 tarihinde Wayback Machine sitesinde arşivlendi.
• Otsu Thresholding in C# 4 Ocak 2012 tarihinde Wayback Machine sitesinde arşivlendi.
• Otsu's method using MATLAB 26 Ekim 2015 tarihinde Wayback Machine sitesinde arşivlendi.
• Otsu Thresholding with scikit-image in Python 9 Mart 2021 tarihinde Wayback Machine sitesinde arşivlendi.