[Python] Region Covariance: Verteilte Covarianzmatrix und Computer Vision

Das Papier "Region Covariance: Ein schneller Deskriptor für die Erkennung und Klassifizierung [^ 1]", das Probleme im Bereich der Computersicht wie Objekterkennung und Texturklassifizierung unter Verwendung einer Verteilungskovarianzmatrix als Merkmalsgröße behandelt. Zusammenfassung und einfache Implementierung in Python zur Objekterkennung.

Introduction

Die Auswahl von Merkmalen ist bei Erkennungs- und Klassifizierungsproblemen sehr wichtig. Tatsächlich werden RGB-Werte, Helligkeitswerte und ihre Farbverläufe häufig im Bereich der Bildverarbeitung verwendet. Diese Merkmale sind jedoch nicht robust gegenüber den Lichtverhältnissen und können je nach Bildgröße zu hochdimensionalen Merkmalen werden. Es gibt Probleme wie. Es gibt auch eine Methode, die ein Bildhistogramm verwendet. Wenn jedoch die Anzahl der Bins im Histogramm $ b $ und die Anzahl der Features $ d $ beträgt, beträgt die Dimension des Histogramms $ b ^ d $ und die Anzahl der Features Die Dimension nimmt exponentiell zu. Das Folgende ist ein Beispiel für $ b = 4, d = 3 $ mit RGB-Werten als Features. → →

Daher schlagen wir in diesem Artikel vor, die Verteilungs-Co-Verteilungsmatrix als Regionsdeskriptor des Bildes zu verwenden. Für die Anzahl der Merkmale $ d $ beträgt die Dimension der Varianz-Co-Dispersionsmatrix $ d \ mal d $, was den Vorteil hat, dass sie kleiner ist als wenn die Merkmale so verwendet werden, wie sie sind, oder wenn ein Histogramm verwendet wird. Darüber hinaus wird in diesem Artikel ein Suchalgorithmus für den nächsten Nachbarn vorgeschlagen, der eine verteilte, gemeinsam verteilte Matrix verwendet.

Covariance as a Region Descriptor

Sei $ I $ ein Helligkeitswertbild von $ W \ mal H $ oder ein RGB-Bild von $ W \ mal H \ mal 3 $. $ W \ times H \ times d $ dimensionales Merkmalsbild $ F $, das aus diesem Bild erhalten wurde

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

Lassen. Hier ist die Funktion $ \ phi $ eine Abbildung, die auf dem Helligkeitswert, dem RGB-Wert und der Filterantwort wie dem Gradienten basiert. Der $ d $ dimensionale Merkmalsvektor in der rechteckigen Region $ R \ Teilmenge F $ sei $ z_1, \ dots, z_n $, und die verteilte mitverteilte Matrix $ C_R $, die die Region $ R $ darstellt, sei.

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

Berechnen mit.

Wie oben erwähnt, ist die Dimension der verteilten, gemeinsam verteilten Matrix $ d \ mal d $, und da es sich um eine symmetrische Matrix handelt, hat sie $ \ frac12d (d + 1) $ unterschiedliche Werte. Dies ist niedriger als wenn die Merkmalsmenge unverändert verwendet wird ($ n \ times d $ dimension) oder wenn das Histogramm verwendet wird ($ b ^ d $ dimension).

Da $ C_R $ keine Informationen über die Reihenfolge und Anzahl der Merkmalspunkte enthält, verfügt es über ein Attribut, das abhängig von den Merkmalsmengen, aus denen die Matrix besteht, für Rotation und Skalierung unveränderlich ist. (Beispielsweise geht die Rotationsinvarianz verloren, wenn Gradienteninformationen in der Richtung $ x, y $ verwendet werden.)

Distance Calculation on Covariance Matrices

Die verteilte co-verteilte Matrix ist eine Menge positiver symmetrischer Matrizen mit konstantem Wert, nicht des euklidischen Raums.

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

Es gehört. Dies kann durch die Tatsache bestätigt werden, dass $ -C_R $ keine verteilte gemeinsam verteilte Matrix für die verteilte gemeinsam verteilte Matrix $ C_R $ sein kann. Wenn Sie also eine Suche nach dem nächsten Nachbarn unter Verwendung einer verteilten, gemeinsam verteilten Matrix durchführen, befindet sich die Entfernung nicht in der euklidischen Entfernung, sondern in $ \ mathcal {P} (d) $ (bezogen auf die Lee-Gruppe oder den Lehman-Hybrid).

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

Wird genutzt. Hier ist $ \ lambda_i (C_1, C_2) $ der verallgemeinerte Eigenwert von $ C_1, C_2 $ für den verallgemeinerten Eigenvektor $ x_i \ neq0 $.

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

Treffen.

Integral Images for Fast Covariance Computation

Ein integrales Bild wird verwendet, um die Varianz-Co-Dispersionsmatrix mit hoher Geschwindigkeit zu berechnen. Was ist ein integriertes Bild?

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

Dies ist die Summe der Pixelwerte, die oben links in dem in definierten interessierenden Pixel vorhanden sind. →

Die $ (i, j) $ -Komponente der Varianz-co-verteilten Matrix ist

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

Es wird berechnet von und es ist ersichtlich, dass die Summe der ersten und zweiten Ordnung von $ z_k $ erforderlich ist. Daher ist $ W \ mal H \ mal d $ dimensionales integriertes Bild $ P $ und $ W \ mal H \ mal d \ mal d $ dimensionales integriertes Bild $ Q $.

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

Definiert in. Außerdem werden die Werte des integrierten Bildes an einem Punkt $ (x, y) $ jeweils festgelegt.

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

Lassen.

Sei $ R (x ', y'; x '', y '') $ der rechteckige Bereich von $ (x ', y') $ oben links und $ (x '', y '') $ unten rechts. Dann ist die verteilte mitverteilte Matrix in diesem rechteckigen Bereich $ 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}

Kann mit berechnet werden.

Object Detection

In diesem Artikel sind die Bildmerkmale $ x, y $ Koordinaten von Pixeln, RGB-Werte von Bildern $ R (x, y), G (x, y), B (x, y) $ und Helligkeitswerte von Bildern $ I. Die Objekterkennung wird unter Verwendung von neun Absolutwerten der Gradienten erster und zweiter Ordnung von (x, y) $ durchgeführt. Die Gradienten erster und zweiter Ordnung werden mit den Filtern $ [-1, 0, 1], [-1, 2, -1] $ berechnet.

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}

Objekterkennungsverfahren

  1. Berechnen Sie die Dispersions-Co-Verteilungsmatrix aus dem Eingabebild nach Gleichung (4).
  2. Führen Sie eine Brute-Force-Suche am Zielbild mit 9 verschiedenen Fenstergrößen und Schrittgrößen durch und berechnen Sie die verteilte, gemeinsam verteilte Matrix für jedes Fenster.
  3. Erkennen Sie Fenster mit einem kleinen Abstand zwischen den nach Gleichung (1) berechneten verteilten, gemeinsam verteilten Matrizen.

In diesem Artikel werden fünf verteilte, gemeinsam verteilte Matrizen erstellt, um Objekte darzustellen, und fünf verteilte, gemeinsam verteilte Matrizen werden erneut für 1000 Fenster mit einem kleinen Abstand zwischen den verteilten, gemeinsam verteilten Matrizen berechnet. Daher wurde ein numerisches Experiment mit nur einem durchgeführt.

Numerisches Experiment

Der im linken Bild von Rosa umgebene Teil wurde als Eingabebild verwendet, und die Objekterkennung wurde an den beiden rechten Bildern mit unterschiedlichen Auflösungen durchgeführt.

Quellcode und kurzer Kommentar

Der Quellcode lautet wie folgt und das ausgeführte Notizbuch ist 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

Das Ausführungsergebnis und die Berechnungszeit betragen 6,22 s bzw. 19,7 s. Sie können es etwas schneller machen, indem Sie die Werte von "n_windows" und "step" ändern.

Recommended Posts

[Python] Region Covariance: Verteilte Covarianzmatrix und Computer Vision
[Python3] Speichern Sie die Mittelwert- und Kovarianzmatrix in json mit Pandas
Suchen und überprüfen Sie die inverse Matrix in Python
[Python] Matrixoperation
Einheitsmatrix und inverse Matrix: Lineare Algebra in Python <4>
Matrixberechnung und lineare Gleichungen: Lineare Algebra in Python <3>
[Python] So erstellen Sie eine Korrelationsmatrix und eine Heatmap
Textextraktion (Lese-API) mit Azure Computer Vision-API (Python3.6)
[Python] Komprimieren und dekomprimieren
Python- und Numpy-Tipps
[Python] Pip und Wheel
Python - Lesen Sie Daten aus einer numerischen Datendatei, um die verteilte, gemeinsam verteilte Matrix, Eigenwerte und Eigenvektoren zu finden
Python Iterator und Generator
Ruby, Python und Map
Implementierte Matrixfaktorisierung (Python)
Python-Eingabe und Ausgabe
Python und Ruby teilen sich
Python asyncio und ContextVar