Binarisation d'images par analyse discriminante linéaire

Objectif de cet article

Comprendre l'analyse discriminante linéaire de Fisher et être capable de binariser les images en l'utilisant.

Environnement à utiliser

Analyse de discrimination linéaire de Fisher

Aperçu

• Une méthode pour trouver les paramètres d'une formule de discrimination linéaire qui classe les données.
• La formule discriminante linéaire est représentée par $ y = w ^ {T} x $. Où $ y $ est la classe, $ w $ le paramètre et $ x $ les données.
• $ w $ est invité à "augmenter la distance moyenne entre les classes et réduire la variance intraclasse".
• Il est également étroitement lié au classificateur optimal bayésien.
• En plus de la binarisation des images, il peut également être appliqué à la réduction de la dimension des données.

Fonction objective

Trouvez le paramètre $ w $ qui maximise la fonction ci-dessous.

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

• $ w $: paramètre discriminant linéaire.
• $ S_ {W} $: matrice de covariance intraclasse.
• $ S_ {B} $: matrice de covariance interclasse.
• $ T $: Translocation.

Matrice de covariance en classe

Chaque classe lorsque les données $ N $ sont classées en classes $ k $ de sorte que le nombre de données dans chaque classe est $ N_ {i} (i = 0, ..., k-1) $ Moyenne de la matrice de covariance de.

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

• $ S_ {i} $: Matrice de covariance de classe $ i $.

Matrice de covariance interclasse

Une matrice de covariance du vecteur moyen pour chaque classe.

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

• $ \ mu_ {i} $: Vecteur moyen de la classe $ i $.
• $ \ mu $: Le vecteur moyen de l'ensemble des données.

Relation entre la matrice de covariance de toutes les données, la matrice de covariance intraclasse et la matrice de covariance interclasse

La somme de la matrice de covariance intraclasse ($ S_ {W} ) et de la matrice de covariance interclasse ( S_ {W} ) est égale à la matrice de covariance ( S $) de toutes les données. Ci-après, la matrice de covariance de toutes les données sera appelée matrice de covariance totale.

\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-ème classe (un ensemble de données contenues dans).
• $ x_ {j} $: jème donnée.

Détermination des paramètres par lagrangien

Même si vous remplacez $ w $ dans la fonction objectif $ J (w) = \ frac {w ^ {T} S_ {B} w} {w ^ {T} S_ {W} w} $ par $ \ alpha w $ Puisque la valeur ne change pas, elle peut être remplacée par $ w ^ {T} S_ {W} w = 1 $, et le problème de trouver le paramètre $ w $ qui maximise $ J (w) $ est $ w ^ {T. On revient au problème de trouver $ w $ qui maximise $ w ^ {T} S_ {B} w $ sous la contrainte de} S_ {W} w = 1 $.

\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}

Convertissez cela en un problème de minimisation.

\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}

Ensuite, Lagrangien devient comme suit.

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

Différenciez $ L $ avec $ w $ et définissez-le sur $ 0 $ pour obtenir l'équation suivante. C'est ce qu'on appelle le problème des valeurs propres généralisées.

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

En supposant que $ S_ {W} $ est régulier, multipliez les deux côtés par sa matrice inverse $ S_ {W} ^ {-1} $ à partir de la gauche pour obtenir le problème habituel des valeurs propres.

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

Adoptez le vecteur propre correspondant à la plus grande des valeurs propres obtenues à la suite de la résolution du problème des valeurs propres généralisées comme $ w $. Ce critère de sélection est obtenu en considérant le double problème de ce problème d'optimisation.

Binarisation d'images à l'aide de l'analyse discriminante de Fisher

Aperçu

• Convertissez les images en échelle de gris en images en noir et blanc.
• Définissez le seuil $ t $ et classez ceux dont les valeurs de pixels sont inférieures à $ t $ en noir et ceux dont les valeurs de pixels sont plus grandes en blanc.
• Déterminer le seuil $ t $ basé sur l'analyse discriminante linéaire de Fisher. Ensuite, le seuil optimal peut être automatiquement sélectionné dans ce sens.
• Cette méthode suppose une image dans laquelle l'image originale est initialement exprimée en noir et blanc.

Fonction objective

La fonction objective $ J (w) $ de la formule discriminante de Fisher dans le chapitre précédent est la formule suivante utilisant la relation de distribution intraclasse, distribution interclasse et distribution totale, en notant que les données de l'image en échelle de gris sont unidimensionnelles. Obtenir. Notez que le paramètre $ w $ est unidimensionnel.

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

• $ \ sigma_ {W} $: distribution en classe.
• $ \ sigma_ {B} $: distribution interclasse.
• $ \ sigma $: distribution complète.

Déterminer le seuil

Puisque la variance totale $ \ sigma $ est constante, il suffit de déterminer le seuil $ t $ qui constitue $ \ sigma_ {B} $ qui maximise $ J (w) $.

$ \ Sigma_ {B} $ peut être calculé par l'équation suivante.

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

• $ N $: Nombre de pixels dans l'image entière
• $ N_ {0} $: nombre de pixels classés comme noirs
• $ N_ {1} $: Nombre de pixels classés comme blancs
• $ \ mu $: moyenne des valeurs de pixel pour l'image entière
• $ \ mu_ {0} $: moyenne des valeurs de pixels des pixels classés comme noirs
• $ \ mu_ {1} $: Moyenne des valeurs de pixels des pixels classés comme blancs

Si les valeurs de pixel minimum et maximum d'une image en niveaux de gris sont respectivement $ x_ {min} $ et $ x_ {max} $, alors $ x_ {min} \ leq t \ leq x_ {max} $. Calculez $ \ sigma_ {B} $ pour tous ces $ t $, trouvez celui qui maximise $ J (w) $ et utilisez-le comme seuil.

programme

# 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()

Le code source peut être trouvé sur Github.

Le résultat de l'exécution est comme indiqué dans la figure ci-dessous. L'image originale est [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) utilisé.

Les références

• Traitement d'image numérique (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.)
• Optimisation de base de l'ingénierie et son application (nouvelles mathématiques d'ingénierie) (Hiroshi Yabe) = 1211 & creativeASIN = 4901683349 & linkCode = as2 & tag = mpsamurai-22)