[PYTHON] Binarisierung von Bildern mittels linearer Diskriminanzanalyse

Ziel dieses Artikels

Verstehen Sie die lineare Diskriminanzanalyse von Fisher und können Sie Bilder damit binärisieren.

Umgebung zu verwenden

Fisher's lineare Diskriminierungsanalyse

Überblick

• Eine Methode zum Ermitteln der Parameter einer linearen Unterscheidungsformel, die Daten klassifiziert.
• Die lineare Diskriminanzformel wird durch $ y = w ^ {T} x $ dargestellt. Dabei ist $ y $ die Klasse, $ w $ der Parameter und $ x $ die Daten.
• $ w $ wird gebeten, "den durchschnittlichen Abstand zwischen Klassen zu vergrößern und die Varianz innerhalb der Klasse zu verringern".
• Es ist auch eng mit dem Bayes'schen Optimalklassifikator verwandt.
• Zusätzlich zur Binärisierung von Bildern kann sie auch zur Reduzierung von Datendimensionen angewendet werden.

Zielfunktion

Suchen Sie den Parameter $ w $, der die folgende Funktion maximiert.

\begin{equation}
J(w) = \frac{w^{T}S_{B}w}{w^{T}S_{W}w}
\end{equation}

• $ w $: Linearer Diskriminanzparameter.
• $ S_ {W} $: Intraclass-Kovarianzmatrix.
• $ S_ {B} $: Kovarianzmatrix zwischen Klassen.
• $ T $: Translokation.

Kovarianzmatrix in der Klasse

Jede Klasse, wenn $ N $ Daten in $ k $ Klassen klassifiziert sind, so dass die Anzahl der Daten in jeder Klasse $ N_ {i} (i = 0, ..., k-1) $ ist Durchschnitt der Kovarianzmatrix von.

\begin{equation}
S_{W}=\sum_{i=0}^{k-1}\frac{N_{i}}{N}S_{i}
\end{equation}

• $ S_ {i} $: Kovarianzmatrix der Klasse $ i $.

Kovarianzmatrix zwischen Klassen

Eine Kovarianzmatrix des mittleren Vektors für jede Klasse.

\begin{equation}
S_{B}=\sum_{i=0}^{k-1}\frac{N_{i}}{N}(\mu_{i}-\mu)^{T}(\mu_{i}-\mu)
\end{equation}

• $ \ mu_ {i} $: Durchschnittlicher Vektor der Klasse $ i $.
• $ \ mu $: Der durchschnittliche Vektor der gesamten Daten.

Beziehung zwischen der Kovarianzmatrix aller Daten, der Intraclass-Kovarianzmatrix und der Interclass-Kovarianzmatrix

Die Summe der Intraclass-Kovarianzmatrix ($ S_ {W} ) und der Interclass-Kovarianzmatrix ( S_ {W} ) entspricht der Kovarianzmatrix ( S $) aller Daten. Im Folgenden wird die Kovarianzmatrix aller Daten als Gesamtkovarianzmatrix bezeichnet.

\begin{align}
S_{W} + S_{B} &=\sum_{i=0}^{k-1}\frac{N_{i}}{N}S_{i}+\sum_{i=0}^{k-1}\frac{N_{i}}{N}(\mu_{i}-\mu)^{T}(\mu_{i}-\mu)\\
&=\frac{1}{N}\sum_{i=0}^{k-1}(N_{i}(\sum_{j \in C_{i}}\frac{x_{j}^{T}x_{j}}{N_{i}}-\mu_{i}^{T}\mu_{i})+N_{i}\mu_{i}^{T}\mu_{i})-\mu^{T}\mu\\
&=\frac{1}{N}\sum_{i=0}^{k-1}(\sum_{j \in C_{i}}x_{j}^{T}x_{j})-\mu^{T}\mu\\
&=\frac{1}{N}\sum_{l=0}^{N-1}x_{l}^{T}x_{l}-\mu^{T}\mu\\
&=S
\end{align} 

• $ C_ {i} $: i-te Klasse (eine Menge von Daten, die in enthalten sind).
• $ x_ {j} $: j-te Daten.

Parameterbestimmung durch Lagrange

Selbst wenn Sie $ w $ in der Zielfunktion $ J (w) = \ frac {w ^ {T} S_ {B} w} {w ^ {T} S_ {W} w} $ durch $ \ alpha w $ ersetzen Da sich der Wert nicht ändert, kann er durch $ w ^ {T} S_ {W} w = 1 $ ersetzt werden, und das Problem beim Finden des Parameters $ w $, der $ J (w) $ maximiert, ist $ w ^ {T. } Es kommt auf das Problem an, $ w $ zu finden, das $ w ^ {T} S_ {B} w $ unter der Bedingung S_ {W} w = 1 $ maximiert.

\begin{equation}
argmax_{w}(w^{T}S_{B}w),
\hspace{3mm}subject\hspace{3mm}to\hspace{3mm}
w^{T}S_{W}w=1
\end{equation}

Konvertieren Sie dies in ein Minimierungsproblem.

\begin{equation}
argmin_{w}(-\frac{1}{2}w^{T}S_{B}w),
\hspace{3mm}subject\hspace{3mm}to\hspace{3mm}
w^{T}S_{W}w=1
\end{equation}

Dann wird Lagrangian wie folgt.

\begin{equation}
L=-\frac{1}{2}w^{T}S_{B}w+\frac{1}{2}\lambda (w^{T}S_{W}w - 1)
\end{equation}

Differenziere $ L $ mit $ w $ und setze es auf $ 0 $, um die folgende Gleichung zu erhalten. Dies wird als verallgemeinertes Eigenwertproblem bezeichnet.

\begin{equation}
S_{B}w=\lambda S_{W}w
\end{equation}

Angenommen, $ S_ {W} $ ist regulär, multiplizieren Sie beide Seiten mit der inversen Matrix $ S_ {W} ^ {-1} $ von links, um das übliche Eigenwertproblem zu erhalten.

\begin{equation}
S_{W}^{-1}S_{B}w=\lambda w
\end{equation}

Nehmen Sie den Eigenvektor an, der dem größten der Eigenwerte entspricht, die als Ergebnis der Lösung des verallgemeinerten Eigenwertproblems erhalten wurden, als $ w $. Dieses Auswahlkriterium wird erhalten, indem das doppelte Problem dieses Optimierungsproblems betrachtet wird.

Binarisierung von Bildern unter Verwendung der Fisher-Diskriminanzanalyse

Überblick

• Konvertieren Sie Graustufenbilder in Schwarzweißbilder.
• Stellen Sie den Schwellenwert $ t $ ein und klassifizieren Sie diejenigen mit Pixelwerten kleiner als $ t $ in Schwarz und diejenigen mit größeren Pixelwerten in Weiß.
• Bestimmen Sie den Schwellenwert $ t $ basierend auf der linearen Diskriminanzanalyse von Fisher. In diesem Sinne kann dann automatisch der optimale Schwellenwert ausgewählt werden.
• Diese Methode setzt ein Bild voraus, in dem das Originalbild ursprünglich in Schwarzweiß ausgedrückt wird.

Zielfunktion

Die Zielfunktion $ J (w) $ der Diskriminanzformel von Fisher im vorherigen Kapitel ist die folgende Formel unter Verwendung der Beziehung zwischen Verteilung innerhalb der Klasse, Verteilung zwischen Klassen und Gesamtverteilung, wobei zu beachten ist, dass die Daten des Graustufenbildes eindimensional sind. Bekommen. Beachten Sie, dass der Parameter $ w $ eindimensional ist.

\begin{equation}
J(w) = \frac{\sigma_{B}}{\sigma_{W}}=\frac{\sigma_{B}}{\sigma -\sigma_{B}}
\end{equation}

• $ \ sigma_ {W} $: Verteilung in der Klasse.
• $ \ sigma_ {B} $: Verteilung zwischen Klassen.
• $ \ sigma $: Vollständige Verteilung.

Schwellenwert bestimmen

Da die Gesamtvarianz $ \ sigma $ konstant ist, reicht es aus, den Schwellenwert $ t $ zu bestimmen, der $ \ sigma_ {B} $ ausmacht und $ J (w) $ maximiert.

$ \ Sigma_ {B} $ kann durch die folgende Gleichung berechnet werden.

\begin{equation}
\sigma_{B}=\frac{N_{0}}{N}(\mu_{0}-\mu)^2 + \frac{N_{1}}{N}(\mu_{1}-\mu)^{2}
\end{equation}

• $ N $: Anzahl der Pixel im gesamten Bild
• $ N_ {0} $: Anzahl der als schwarz klassifizierten Pixel
• $ N_ {1} $: Anzahl der als weiß klassifizierten Pixel
• $ \ mu $: Durchschnitt der Pixelwerte für das gesamte Bild
• $ \ mu_ {0} $: Durchschnitt der Pixelwerte der als schwarz klassifizierten Pixel
• $ \ mu_ {1} $: Durchschnitt der Pixelwerte der als weiß klassifizierten Pixel

Wenn die minimalen und maximalen Pixelwerte eines Graustufenbildes $ x_ {min} $ bzw. $ x_ {max} $ sind, dann $ x_ {min} \ leq t \ leq x_ {max} $. Berechnen Sie $ \ sigma_ {B} $ für alle diese $ t $, finden Sie diejenige, die $ J (w) $ maximiert, und verwenden Sie sie als Schwellenwert.

Programm

# This file is part of "Junya's self learning project about digital image processing."
#
# "Junya's self learning project about digital image processing"
# is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# "Junya's self learning project about digital image processing"
# is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with Foobar.  If not, see <http://www.gnu.org/licenses/>.
#
# (c) Junya Kaneko <[email protected]>

from PIL import Image
import numpy as np
from matplotlib import pyplot as plt


def discriminant_analysis(image):
    _image = image.reshape(image.shape[0] * image.shape[1])
    ave = np.average(_image)
    t = j0 = 0
    for _t in range(np.min(_image) + 1, np.max(_image) + 1):
        blacks = _image[_image < _t]
        whites = _image[_image >= _t]
        sigma_b = len(blacks) * np.power(np.average(blacks) - ave, 2) /len(_image) + len(whites) * np.power((np.average(whites) - ave), 2) / len(_image)
        j1 = sigma_b / (np.var(_image) - sigma_b)
        if j0 < j1:
            t = _t
            j0 = j1
    return t


if __name__ == '__main__':
    image = np.array(Image.open('img/test.jpg').convert('L'), dtype=np.uint8)
    bin_image = np.array(image)
    t = discriminant_analysis(image)

    for i in range(image.shape[0]):
        for j in range(image.shape[1]):
            bin_image[i, j] = 255 if image[i, j] >= t else 0

    plt.subplot(1, 2, 1)
    plt.title('Original')
    plt.imshow(image, cmap='Greys_r')

    plt.subplot(1, 2, 2)
    plt.title('Binary')
    plt.imshow(bin_image, cmap='Greys_r')

    plt.show()

Der Quellcode finden Sie unter Github.

Das Ausführungsergebnis ist in der folgenden Abbildung dargestellt. Das Originalbild ist [Letter Wiki](http://ja.characters.wikia.com/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB: % E4% B8% 89% E4% BD% 93% E7% BF% 92% E5% AD% 97% E3% 83% BB% E6% A5% B7 -% E6% 88% 91.jpg) benutzt.

Verweise

• Digitale Bildverarbeitung (CG-ARTS Association)
• Dimensionality Reduction (Javier Hernandez Rivera)
• Penalized linear discriminant analysis (Daniela M. Witten et al.)
• Fisher's Linear Discriminant Analysis (Max Welling)
• A Threshold Selection Method from Gray-Level Histograms (Nobuyuki Otu)
• Introduction to Linear Optimization (Dimitris Bertsimas et al.)
• Grundlegende technische Optimierung und ihre Anwendung (neue technische Mathematik) (Hiroshi Yabe) = 1211 & creativeASIN = 4901683349 & linkCode = as2 & tag = mpsamurai-22)