[Python] Covariance de région: matrice de covariance distribuée et vision par ordinateur

L'article "Region Covariance: A fast descriptor for detection and classification [^ 1]" qui aborde les problèmes dans le domaine de la vision par ordinateur tels que la détection d'objets et la classification de texture en utilisant une matrice de covariance de distribution comme quantité de caractéristiques. Résumé et implémentation simple en Python pour la détection d'objets.

Introduction

La sélection des fonctionnalités est très importante dans les problèmes de détection et de classification. En fait, les valeurs RVB, les valeurs de luminosité et leurs gradients sont souvent utilisés dans le domaine de la vision par ordinateur, mais ces caractéristiques ne sont pas robustes aux conditions d'éclairage et peuvent devenir des caractéristiques de grande dimension en fonction de la taille de l'image. Il y a des problèmes tels que. Il existe également une méthode qui utilise un histogramme d'image, mais si le nombre de cases dans l'histogramme est $ b $ et le nombre d'entités est $ d $, la dimension de l'histogramme est $ b ^ d $, et le nombre d'entités La dimension augmente de façon exponentielle. Voici un exemple de $ b = 4, d = 3 $ avec des valeurs RVB comme caractéristiques. → →

Par conséquent, dans cet article, nous proposons d'utiliser la matrice de co-distribution de distribution comme descripteur de région de l'image. Pour le nombre d'entités $ d $, la dimension de la matrice de variance-co-dispersion est $ d \ fois d $, ce qui a l'avantage d'être plus petite que lorsque les entités sont utilisées telles quelles ou qu'un histogramme est utilisé. De plus, cet article propose un algorithme de recherche du plus proche voisin qui utilise une matrice distribuée co-distribuée.

Covariance as a Region Descriptor

Soit $ I $ une image de valeur de luminosité de $ W \ fois H $ ou une image RVB de $ W \ fois H \ fois 3 $. $ W \ fois H \ fois d $ image caractéristique dimensionnelle $ F $ obtenue à partir de cette image

F(x, y) = \phi(I, x, y)

Laisser. Ici, la fonction $ \ phi $ est un mappage basé sur la valeur de luminosité, la valeur RVB et la réponse du filtre telle que le dégradé. Soit le vecteur de caractéristiques dimensionnelles $ d $ dans l'aire rectangulaire $ R \ sous-ensemble F $ $ z_1, \ dots, z_n $, et la matrice distribuée co-distribuée $ C_R $ représente l'aire $ R $.

C_R = \frac{1}{n-1}\sum_{k=1}^n(z_k - \mu)(z_k - \mu)^\top,\quad \mu=\frac1n\sum_{k=1}^n z_k

Calculez avec.

Comme mentionné ci-dessus, la dimension de la matrice distribuée co-distribuée est $ d \ fois d $, et comme il s'agit d'une matrice symétrique, elle a $ \ frac12d (d + 1) $ valeurs différentes. C'est moins que lorsque la quantité d'entités est utilisée telle quelle ($ n \ fois d $ dimension) ou lorsque l'histogramme est utilisé ($ b ^ d $ dimension).

De plus, étant donné que $ C_R $ ne dispose pas d'informations sur l'ordre et le nombre de points caractéristiques, il a un attribut qui est invariant à la rotation et à l'échelle en fonction des quantités d'entités qui composent la matrice. (Par exemple, l'invariance de rotation est perdue lors de l'utilisation des informations de gradient dans la direction $ x, y $)

Distance Calculation on Covariance Matrices

La matrice distribuée co-distribuée est un ensemble de matrices symétriques à valeur constante positive, et non un espace euclidien.

\mathcal{P}(d) := \left\{X\in\mathbb{R}^{d\times d}\mid X=X^\top,X\succ O\right\}

Il appartient à. Ceci peut être confirmé par le fait que $ -C_R $ ne peut pas être une matrice distribuée co-distribuée pour la matrice distribuée co-distribuée $ C_R $. Par conséquent, lors d'une recherche du plus proche voisin à l'aide d'une matrice distribuée co-distribuée, la distance n'est pas sur la distance euclidienne mais sur $ \ mathcal {P} (d) $ (lié au groupe de Lee ou hybride de Lehman).

\rho(C_1, C_2) = \sqrt{\sum_{i=1}^d \ln^2\lambda_i(C_1, C_2)} \tag{1}

Est utilisé. Ici, $ \ lambda_i (C_1, C_2) $ est la valeur propre généralisée de $ C_1, C_2 $, pour le vecteur propre généralisé $ x_i \ neq0 $.

\lambda_i C_1 x_i - C_2 x_i = 0, \quad i=1, \dots, d

Rencontrer.

Integral Images for Fast Covariance Computation

Une image intégrale est utilisée pour calculer la matrice de variance-co-dispersion à grande vitesse. Qu'est-ce qu'une image intégrée?

\text{Integral Image }(x', y') = \sum_{x<x' ,y<y'}I(x, y)

Il s'agit de la somme des valeurs de pixel existant dans le coin supérieur gauche du pixel d'intérêt défini dans. →

La composante $ (i, j) $ de la matrice de variance co-distribuée est

\begin{align}
C_R(i, j) &= \frac{1}{n-1}\sum_{k=1}^n (z_k(i) - \mu(i))(z_k(j) - \mu(j))\\
&= \frac{1}{n-1}\left[\sum_{k=1}^n z_k(i)z_k(j) - \mu(i)\sum_{k=1}^n z_k(j) - \mu(j)\sum_{k=1}^n z_k(i) + n\mu(i)\mu(j)\right]\\
&= \frac{1}{n-1}\left[\sum_{k=1}^n z_k(i)z_k(j) - \frac1n\sum_{k=1}^n z_k(i)\sum_{k=1}^n z_k(j)\right]\\
\end{align}

Il est calculé par, et on peut voir que la somme des premier et deuxième ordres de $ z_k $ est requise. Par conséquent, $ W \ fois H \ fois d $ image intégrée dimensionnelle $ P $ et $ W \ fois H \ fois d \ fois d $ image intégrée dimensionnelle $ Q $, respectivement.

\begin{align}
P(x',y',i) &= \sum_{x<x', y<y'}F(x, y, i), \quad i=1, \dots, d \tag{2}\\
Q(x',y',i, j) &= \sum_{x<x', y<y'}F(x, y, i)F(x, y, j), \quad i, j=1, \dots, d \tag{3}
\end{align}

Défini dans. De plus, les valeurs de l'image intégrée en un point $ (x, y) $ sont définies respectivement.

\begin{align}
p_{x, y} &= \left[P(x, y, 1), \dots, P(x, y, d)\right]^\top\\
Q_{x, y} &= 
\begin{pmatrix}
Q(x, y, 1, 1) & \cdots & Q(x, y, 1, d)\\
\vdots & \ddots & \vdots\\
Q(x, y, d, 1) & \cdots & Q(x, y, d, d)
\end{pmatrix}
\end{align}

Laisser.

Soit la zone rectangulaire de $ (x ', y') $ en haut à gauche et $ (x '', y '') $ en bas à droite $ R (x ', y'; x '', y '') $. Ensuite, la matrice distribuée co-distribuée dans cette région rectangulaire est $ n = (x '' - x ') \ cdot (y' '- y') $.

\begin{align}
C_{R(x', y'; x'', y'')} = \frac{1}{n-1}\left[Q_{x'', y''} + Q_{x', y'} - Q_{x'', y'} - Q_{x', y''}\\ 
-\frac1n(p_{x'', y''} + p_{x', y'} - p_{x'', y'} - p_{x', y''})(p_{x'', y''} + p_{x', y'} - p_{x'', y'} - p_{x', y''})^\top\right] \tag{4}
\end{align}

Peut être calculé avec.

Object Detection

Dans cet article, les quantités de caractéristiques de l'image sont les coordonnées $ x, y $ du pixel, la valeur RVB de l'image $ R (x, y), G (x, y), B (x, y) $ et la valeur de luminosité de l'image $ I. La détection d'objet est effectuée à l'aide de neuf valeurs absolues des gradients de premier et de second ordre de (x, y) $. Les gradients du premier et du second ordre sont calculés à l'aide des filtres $ [-1, 0, 1], [-1, 2, -1] $.

F(x, y) = \left[x, y, R(x, y), G(x, y), B(x, y), \left|\frac{\partial I(x, y)}{\partial x}\right|, \left|\frac{\partial I(x, y)}{\partial y}\right|, \left|\frac{\partial^2 I(x, y)}{\partial x^2}\right|, \left|\frac{\partial^2 I(x, y)}{\partial y^2}\right|\right]^\top \tag{5}

Procédure de détection d'objets

  1. Calculez la matrice de co-distribution de dispersion à partir de l'image d'entrée par l'équation (4).
  2. Effectuez une recherche par force brute sur l'image cible en utilisant 9 tailles de fenêtre et tailles de pas différentes, et calculez la matrice distribuée co-distribuée pour chaque fenêtre.
  3. Détecter les fenêtres avec une petite distance entre les matrices co-distribuées distribuées calculées par l'équation (1).

Dans l'article, cinq matrices co-distribuées distribuées sont créées pour représenter des objets, et cinq matrices co-distribuées distribuées sont calculées à nouveau pour 1000 fenêtres avec une petite distance entre les matrices co-distribuées distribuées. Par conséquent, une expérience numérique a été réalisée avec un seul.

Expérience numérique

La partie entourée de rose dans l'image de gauche a été utilisée comme image d'entrée, et la détection d'objet a été effectuée sur les deux images de droite avec des résolutions différentes.

Code source et bref commentaire

Le code source est le suivant, et le bloc-notes exécuté est Github.

from typing import List, Tuple
from itertools import product

import cv2
import numpy as np
from scipy.linalg import eigh
from tqdm import tqdm


def calc_distance(x: np.ndarray, y: np.ndarray) -> float:
    w = eigh(x, y, eigvals_only=True)
    return np.linalg.norm(np.log(w) ** 2)


class RegionCovarianceDetector:
    """
    Object Detector Using Region Covariance

    Parameters
    ----------
    coord : bool, optional (default=True)
        Whether use coordinates as features or not.

    color : bool, optional (default=True)
        Whether use color channels as features or not.

    intensity : bool, optional (default=False)
        Whether use intensity as feature or not.

    kernels : a list of np.ndarray, optional (default=None)
        Filters applied to intensity image. If None, no filters are used.

    ratio : float, optional (default=1.15)
        Scaling factor between two consecutive scales of the search window size and step size.

    step : int, optional (default=3)
        The minimum step size.

    n_windows : int, optional (default=9)
        The number of scales of the windows.

    eps : float, optional (default=1e-16)
        Small number to keep covariance matrices in SPD.

    Attributes
    ----------
    object_shape_ : (int, int)
        The object's shape.

    object_covariance_ : np.ndarray, shape (n_features, n_features)
        Covariance matrix of the object.
    """

    def __init__(
            self,
            coord: bool = True,
            color: bool = True,
            intensity: bool = False,
            kernels: List[np.ndarray] = None,
            ratio: float = 1.15,
            step: int = 3,
            n_windows: int = 9,
            eps: float = 1e-16
    ):
        self.coord = coord
        self.color = color
        self.intensity = intensity
        self.kernels = kernels
        self.ratio = ratio
        self.step = step
        self.n_windows = n_windows
        self.eps = eps

        self.object_shape_ = None
        self.object_covariance_ = None

    def _extract_features(self, img: np.ndarray) -> List[np.ndarray]:
        """
        Extract image features.

        Parameters
        ----------
        img : np.ndarray, shape (h, w, c)
            uint8 RGB image

        Returns
        -------
        features : a list of np.ndarray
            Features such as intensity, its gradient and so on.
        """
        h, w, c = img.shape[:3]
        intensity = cv2.cvtColor(img, cv2.COLOR_BGR2HSV)[:, :, 2] / 255.
        features = list()

        # use coordinates
        if self.coord:
            features.append(np.tile(np.arange(w, dtype=float), (h, 1)))
            features.append(np.tile(np.arange(h, dtype=float).reshape(-1, 1), (1, w)))

        # use color channels
        if self.color:
            for i in range(c):
                features.append(img[:, :, i].astype(float) / 255.)

        # use intensity
        if self.intensity:
            features.append(intensity)

        # use filtered images
        if self.kernels is not None:
            for kernel in self.kernels:
                features.append(np.abs(cv2.filter2D(intensity, cv2.CV_64F, kernel)))

        return features

    def _calc_integral_images(self, img: np.ndarray) -> Tuple[np.ndarray, np.ndarray]:
        """
        Calculate integral images.

        Parameters
        ----------
        img : np.ndarray, shape (h, w, c)
            uint8 RGB image

        Returns
        -------
        P : np.ndarray, shape (h+1, w+1, n_features)
            First order integral images of features.

        Q : np.ndarray, shape (h+1, w+1, n_features, n_features)
            Second order integral images of features.
        """
        h, w = img.shape[:2]
        features = self._extract_features(img)
        length = len(features)

        # first order integral images
        P = cv2.integral(np.array(features).transpose((1, 2, 0)))

        # second order integral images
        Q = cv2.integral(
            np.array(list(map(lambda x: x[0] * x[1], product(features, features)))).transpose((1, 2, 0))
        )
        Q = Q.reshape(h + 1, w + 1, length, length)
        return P, Q

    def _calc_covariance(self, P: np.ndarray, Q: np.ndarray, pt1: Tuple[int, int], pt2: Tuple[int, int]) -> np.ndarray:
        """
        Calculate covariance matrix from integral images.

        Parameters
        ----------
        P : np.ndarray, shape (h+1, w+1, n_features)
            First order integral images of features.

        Q : np.ndarray, shape (h+1, w+1, n_features, n_features)
            Second order integral images of features.

        pt1 : (int, int)
            Left top coordinate.

        pt2 : (int, int)
            Right bottom coordinate.

        Returns
        -------
        covariance : np.ndarray, shape (n_features, n_features)
            Covariance matrix.
        """
        x1, y1 = pt1
        x2, y2 = pt2
        q = Q[y2, x2] + Q[y1, x1] - Q[y1, x2] - Q[y2, x1]
        p = P[y2, x2] + P[y1, x1] - P[y1, x2] - P[y2, x1]
        n = (y2 - y1) * (x2 - x1)
        covariance = (q - np.outer(p, p) / n) / (n - 1) + self.eps * np.identity(P.shape[2])
        return covariance

    def fit(self, img: np.ndarray):
        """
        Calculate the object covariance matrix.

        Parameters
        ----------
        img : np.ndarray, shape (h, w, c)
            uint8 RGB image

        Returns
        -------
        : Fitted detector.
        """
        h, w = img.shape[:2]
        P, Q = self._calc_integral_images(img)

        # normalize about coordinates
        if self.coord:
            for i, size in enumerate((w, h)):
                P[:, :, i] /= size
                Q[:, :, i] /= size
                Q[:, :, :, i] /= size

        # calculate covariance matrix
        self.object_covariance_ = self._calc_covariance(P, Q, (0, 0), (w, h))
        self.object_shape_ = (h, w)
        return self

    def predict(self, img: np.ndarray) -> Tuple[Tuple[int, int], Tuple[int, int], float]:
        """
        Compute object's position in the target image.

        Parameters
        ----------
        img : np.ndarray, shape (h, w, c)
            uint8 RGB image

        Returns
        -------
        pt1 : (int, int)
            Left top coordinate.

        pt2 : (int, int)
            Right bottom coordinate.

        score : float
            Dissimilarity of object and target covariance matrices.
        """
        tar_h, tar_w = img.shape[:2]
        obj_h, obj_w = self.object_shape_
        P, Q = self._calc_integral_images(img)

        # search window's shape and step size
        end = (self.n_windows + 1) // 2
        start = end - self.n_windows
        shapes = [(int(obj_h * self.ratio ** i), int(obj_w * self.ratio ** i)) for i in range(start, end)]
        steps = [int(self.step * self.ratio ** i) for i in range(self.n_windows)]

        distances = list()
        for shape, step in tqdm(zip(shapes, steps)):
            p_h, p_w = shape
            p_P, p_Q = P.copy(), Q.copy()

            # normalize about coordinates
            if self.coord:
                for i, size in enumerate((p_w, p_h)):
                    p_P[:, :, i] /= size
                    p_Q[:, :, i] /= size
                    p_Q[:, :, :, i] /= size

            distance = list()
            y1, y2 = 0, p_h
            while y2 <= tar_h:
                dist = list()
                x1, x2 = 0, p_w
                while x2 <= tar_w:
                    # calculate covariance matrix
                    p_cov = self._calc_covariance(p_P, p_Q, (x1, y1), (x2, y2))

                    # jump horizontally
                    x1 += step
                    x2 += step

                    # calculate dissimilarity of two covariance matrices
                    dist.append(calc_distance(self.object_covariance_, p_cov))

                # jump vertically
                y1 += step
                y2 += step
                distance.append(dist)
            distances.append(np.array(distance))

        # choose the most similar window
        min_indices = list(map(np.argmin, distances))
        min_index = int(np.argmin([dist.flatten()[i] for i, dist in zip(min_indices, distances)]))
        min_step = steps[min_index]
        min_shape = shapes[min_index]
        min_indice = min_indices[min_index]
        b_h, b_w = distances[min_index].shape

        pt1 = ((min_indice % b_w) * min_step, (min_indice // b_w) * min_step)
        pt2 = (pt1[0] + min_shape[1], pt1[1] + min_shape[0])
        score = distances[min_index].flatten()[min_indice]
        return pt1, pt2, score

Le résultat de l'exécution et le temps de calcul sont respectivement de 6,22 s et 19,7 s. Vous pouvez le rendre un peu plus rapide en modifiant les valeurs de n_windows et step.

Recommended Posts

[Python] Covariance de région: matrice de covariance distribuée et vision par ordinateur
[Python3] Enregistrez la matrice de moyenne et de covariance dans json avec les pandas
Rechercher et vérifier la matrice inverse en Python
[Python] Opération de matrice
Matrice unitaire et matrice inverse: Algèbre linéaire en Python <4>
Calcul matriciel et équations linéaires: Algèbre linéaire en Python <3>
[Python] Comment créer une matrice de corrélation et une carte thermique
Extraction de texte (API de lecture) avec l'API Azure Computer Vision (Python3.6)
[python] Compresser et décompresser
Astuces Python et Numpy
[Python] pip et roue
Python --Lisez des données à partir d'un fichier de données numériques pour trouver des matrices, des valeurs propres et des vecteurs propres distribués co-distribués
Itérateur et générateur Python
Ruby, Python et carte
Mise en œuvre de la factorisation matricielle (python)
entrée et sortie python
Python et Ruby se séparent
Python asyncio et ContextVar