NVIDIA Performance Primitives (NPP)  Version 10.0
Modules
Image Proximity
Statistical Operations

Primitives for computing the proximity measure between a source image and a template image. More...

Modules

 SqrDistanceFull_Norm
 Primitives for computing the normalized Euclidean distance between two images with full mode.
 
 SqrDistanceSame_Norm
 Primitives for computing the normalized Euclidean distance between two images with same mode.
 
 SqrDistanceValid_Norm
 Primitives for computing the normalized Euclidean distance between two images with valid mode.
 
 CrossCorrFull_Norm
 Primitives for computing the normalized cross correlation between two images with full mode.
 
 CrossCorrSame_Norm
 Primitives for computing the normalized cross correlation between two images with same mode.
 
 CrossCorrValid_Norm
 Primitives for computing the normalized cross correlation between two images with valid mode.
 
 CrossCorrValid
 Primitives for computing the cross correlation between two images with valid mode.
 
 CrossCorrFull_NormLevel
 Primitives for computing the normalized cross correlation coefficient between two images with full mode.
 
 CrossCorrSame_NormLevel
 Primitives for computing the normalized cross correlation coefficient between two images with same mode.
 
 CrossCorrValid_NormLevel
 Primitives for computing the normalized cross correlation coefficient between two images with valid mode.
 

Detailed Description

Primitives for computing the proximity measure between a source image and a template image.

General Introduction

There are basically two approaches to compute the proximity measure for template matching, Euclidean distance and the cross correlation.

  1. Euclidean distance computes the sum of the squared distance (SSD) between the corresponding pixels of the source image and the template image. The smaller the distance is, the more similar the source image and the template image is around the pixel. The anchor of the template image is used during the computations, which always lies in the gemotric center of the image. Given a source image $pSrc$ ( $W_s \times H_s$) and a template image $pTpl$ ( $W_t \times H_t$), the Euclidean distance $D_{st}(c,r)$ between two images at pixel in row $r$ and column $c$ is computed as ( $s$ stands for source image and $t$ for template image for short):

    \[D_{st}(c,r)=\sum_{j=0}^{H_t-1}\sum_{i=0}^{W_t-1}[pTpl(j,i)-pSrc(j+c-\frac{H_t}{2}, i+r-\frac{W_t}{2})]^2 \]

  2. Cross correlation computes the sum of the product between the corresponding pixels of the source image and the template image. The cross correlation $R_{st}(c,r)$ is calculated as:

    \[R_{st}(c,r)=\sum_{j=0}^{H_t-1}\sum_{i=0}^{W_t-1}[pTpl(j,i)\cdot pSrc(j+c-\frac{H_t}{2}, i+r-\frac{W_t}{2})] \]

    The larger the cross correlation value is, the more similar the source image and the template image is around the pixel.
  3. The cross correlation $R_{st}(c,r)$ is affected by the brightness of the images which may vary due to the lighting and exposure conditions. Therefore, NPP computes the cross correlation coefficient to circumvent this dependence. This is typically done at every step by subtracting the mean from every pixel value, i.e.,

    \[\tilde{R}_{st}(c,r)=\sum_{j=0}^{H_t-1}\sum_{i=0}^{W_t-1}[pTpl(j,i)-Mean_t]\cdot [pSrc(j+c-\frac{H_t}{2}, i+r-\frac{W_t}{2})-Mean_s] \]

NPP computes the normalized values of Euclidean distance, cross correlation and the cross correlation coefficient.

  1. The normalized Euclidean distance $\sigma_{st}(c,r)$ is defined as:

    \[\sigma_{st}(c,r) = \frac{D_{st}(c,r)}{\sqrt{R_{ss}(c,r)\cdot R_{tt}(\frac{H_t}{2},\frac{W_t}{2})}} \]

  2. The normalized cross correlation $\rho_{st}(c,r)$ is defined as:

    \[\rho_{st}(c,r) = \frac{R_{st}(c,r)}{\sqrt{R_{ss}(c,r)\cdot R_{tt}(\frac{H_t}{2},\frac{W_t}{2})}} \]

    The $R_{ss}(c,r)$ and $R_{tt}(\frac{H_t}{2}, \frac{W_t}{2}$ denote the auto correlation of the source image and the template image individually. They are defined as:

    \[R_{ss}(c,r)=\sum_{j=c-\frac{H_t}{2}}^{c+\frac{H_t}{2}}\sum_{i=r-\frac{W_t}{2}}^{r+\frac{W_t}{2}}pSrc(j, i) \]

    \[R_{tt}(\frac{H_t}{2},\frac{W_t}{2})=\sum_{j=0}^{H_t-1}\sum_{i=0}^{W_t-1}pTpl(j,i) \]

  3. Similarly, the normalized cross correlation coefficient $\gamma_{st}(c,r)$ is calculated as:

    \[\gamma_{st}(c,r) = \frac{\tilde{R}_{st}(c,r)}{\sqrt{\tilde{R}_{ss}(c,r)\cdot \tilde{R}_{tt}(\frac{H_t}{2},\frac{W_t}{2})}} \]

    The $\tilde{R}_{ss}(c,r)$ and $\tilde{R}_{tt}(\frac{H_t}{2}, \frac{W_t}{2}$ are defined as:

    \[\tilde{R}_{ss}(c,r)=\sum_{j=c-\frac{H_t}{2}}^{c+\frac{H_t}{2}}\sum_{i=r-\frac{W_t}{2}}^{r+\frac{W_t}{2}}[pSrc(j, i)-Mean_s] \]

    \[\tilde{R}_{tt}(\frac{H_t}{2},\frac{W_t}{2})=\sum_{j=0}^{H_t-1}\sum_{i=0}^{W_t-1}[pTpl(j,i)-Mean_t] \]

Categorizations

The Euclidean distance and the cross correlation are categorized into three types, full, same, and valid.

  1. Full mode indicates that the anchor of the template image starts from the outside of the source image, assuming the out-of-boundary pixels are zeor-padded. The size of the destination image is $(W_s + W_t - 1) \times (H_s + H_t - 1)$.
  2. Same mode means that the anchor of the template image starts from the top left pixel of the source image. All the out-of-boundary pixels are also zero-padded. The size of the destination image is the same as the source one, i.e., $W_s \times H_s$.
  3. Valid mode indicates that there are no out-of-boudnary readings from the source image. The anchor of the template image starts from the inside of the source image. The size of the destination image is $(W_s - W_t + 1) \times (H_s - H_t + 1)$.
Copyright © 2009-2017 NVIDIA Corporation