# Heterogeneous Image Matching via a Novel Feature Describing Model
## 2 Fundamentals
### SIFT and PCA-SIFT  
Based on the scale space and the difference space, the original Scale-Invariant Feature Transform (SIFT) can be described as four main steps. 1. Scale-space peaks selection. The extreme points in the DoG (difference of Gaussian) space are detected by comparing the pixels in a \(3\times 3\times 3\) neighborhood, named non-maximum suppression. Let \(D(x)\) and \(U_{r}(x)\) denote the DoG function and \(r\)-neighborhood of \(x\); then,  
\[\textit{EPTs}=\{x,D(x)\geq D(y)\forall y\in U_{1}(x)\}. \tag{5}\]  
2. Keypoint localization. Taylor expansion and principle curvature are both applied to check the detected extreme points again and then keypoints can be located. Let \(H\) denote the Hessian of DoG function \(D(x)\); then,  
\[\textit{KPTs}=\{x\in\textit{EPTs},\ |-(\frac{\partial^{2}D}{\partial x^{2}})^{ -1}\frac{\partial D}{\partial x}|<0.5\wedge|D(x)|<0.03\wedge\frac{\textit{Tr}( H)^{2}}{|H|}<\frac{(r+1)^{2}}{r})\}.\] (6) Generally, set \(r=10\). 3. Orientation assignment. To achieve rotation invariance, eight-direction statistics is applied on the gradient field of \(A(x)\), the local patch centered at \(x\). Then, the orientation can be computed by searching the maximal direction of the histogram. \[\theta(A)=\text{argminhist8}(\theta_{k},\
abla A),\ k=1,2,\ldots,8. \tag{7}\]  
Here, hist8\((\theta_{k},\
abla A)\) means the value in \([\theta_{k}-\frac{\pi}{8},\theta_{k}+\frac{\pi}{8})\) when the histogram was carried out on a local gradient patch \(\
abla A(x)\). \(\theta_{k}\) is one of the eight uniform directions. 4. Keypoint descriptor. Then, eight direction statistics is applied on each subarea after the local gradient field has been rotated by \(\theta_{0}\) and divided into \(4\times 4\) sub-areas. Let \(B(i,j)\) denote the subareas of rotated \(A(x)\); then, a 128-dimensional descriptor can be obtained by arranging them as follows:  
\[F_{SIFT}=\big{[}\text{hist8}(\theta_{k},\
abla B_{i,j})\big{]}_{4\times 4 \times 8}. \tag{8}\]The PCA-SIFT is similar to the SIFT in many details and they only differ in Step 4. It can be summarized as follows. 1. An eigenspace of the image gradient fields is pre-computed. The gradient fields on a \(41\times 41\) patch centered at the keypoint can be rearranged to a \(2\times 39\times 39=3042\)-dimensional vector. In addition, it is normalized to unit magnitude for reducing the unexpected impact of variations in illumination. Such about 21,000 patches will be collected and then principle component analysis is processed. The first 20 components will be selected to generate the projection matrix for any other observation. Let \(C\) denote the normalized version of collected patches; then, the projection matrix for any path can be computed as  
\[M_{proj}=\left[v_{1},v_{2},\cdots,v_{20}\right]. \tag{9}\]  
Here, \(C^{T}Cv_{i}=\lambda_{i}v_{i},\ i=1,2,\cdots,d\) and \(\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{d}\). 2. A simplified descriptor is used on the eigenspace. A 3042-dimensional vector \(z\) on a given image patch centered at \(x\) will be computed and normalized, and then projected into the pre-computed feature space as denoted by Equation (10). A 20-dimensional vector can be used to describe the feature point. Figure 2 shows some keypoints and patches of the Lena image. Figure 2b shows the gradient filed on the yellow patch. Figure 2c shows the pre-computed feature space to be dimension reduced:  
\[F_{PCA-SIFT}=zM_{proj}. \tag{10}\]  
After then, the Euclidean distance can be used to determine whether the two vectors mean the same keypoint in different images. In more detail, a proper threshold \(\rho_{0}\) is presented for the ratio between the best and second-best match as in the SIFT. Let \(I_{a}\) and \(I_{b}\) be the two images, \(x\in I_{a}\) and \(x\in I_{b}\) are keypoints, and then the matching between \(x\) and \(y\) can be determined based on PCA-SIFT features \(F_{PCA-SIFT}(x)\) and \(F_{PCA-SIFT}(y)\)  
\[IsMatch(x,y)=\left\{ \begin{array}{ll}1,&\rho>\rho_{0},\\ 0,&\rho\leq\rho_{0}.\end{array} \right.