# A Novel Discriminating and Relative Global Spatial Image Representation with Applications in CBIR
## 3 Proposed Methodology
### The Proposed Relative Global Spatial Image Representation (RGSIR)  
In the BoVW model the final image representation is created by mapping identical image patches to the same visual word. In [20], [PERSON] et al. capture the spatial information by modeling the global relationship between identical visual word pairs (PIWs). Their approach exhibits invariance to translation and scaling but is sensitive to rotation [20; 37], since the relative relationship between PIWs is computed with respect to the x-axis. [PERSON] et al. [37] propose an approach to acquire rotation invariance by computing angles between Triplets of Identical Visual Words (TIWs). Although the approach of [37] acquires rotation invariance, it significantly increases computation complexity due to the increase in the number of possible triplet combinations. For instance, if the number of identical visual words is 30, the number of distinct pair combinations is 435 and the number of possible distinct triplet combinations is 4060.  
This paper proposes a novel approach to acquiring spatial information for transformation invariance by computing the global geometric relationship between pairs of identical visual words. This is accomplished by extracting the spatial distribution of these pairs with respect to a centroid in an image as shown in Figure 2.  
Hence we define the set of all pairs (PW) of identical visual words related to a visual word \(w_{i}\) as:  
\[PW_{i}=\{(a,b)|(d_{a},d_{b})\in D_{i}^{2},d_{a}\
eq d_{b}\} \tag{4}\]  
Figure 2: Angle between identical visual word pairs with respect to the centroid.  
where \(a(x_{1},y_{1})\) and \(b(x_{2},y_{2})\) are the spatial locations of the descriptors \(d_{a}\) and \(d_{b}\), respectively. Since the \(i\)th histogram bin signifies the descriptor \(d_{i}\), its value determines the total occurrences of the word \(w_{i}\). The cardinality of the set \(PW_{i}\) is \({}^{b_{i}}C_{2}\). The centroid \(c=(x,y)\) of an image \(Im\) of size \(R\times C\) is calculated as  
\[x=\frac{1}{\mid Im\mid}\sum_{i=1}^{\mid Im\mid}x_{i},\ \ y=\frac{1}{\mid Im\mid}\sum_{i=1}^{ \mid Im\mid}y_{i} \tag{5}\]  
where \(Im=\{(x_{i},y_{i})\mid 1\leq x_{i}\leq R,1\leq y_{i}\leq C\}\) and \(\mid Im\mid\) is the number of elements in \(Im\). Let \(r_{ab}\) be the Euclidean distance between \(a\) and \(b\), then  
\[r_{ab}=\sqrt{(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}} \tag{6}\]  
Similarly, the Euclidean distances of \(a\) and \(b\) from c are calculated as  
\[r_{ca}=\sqrt{(x_{1}-x)^{2}+(y_{1}-y)^{2}}\] \[r_{cb}=\sqrt{(x_{2}-x)^{2}+(y_{2}-y)^{2}}\]  
Using the Law of cosines, we have  
\[\theta=\arccos\left(\frac{(r_{ca})^{2}+(r_{cb})^{2}-(r_{ab})^{2}}{2(r_{ca})(r_ {cb})}\right) \tag{7}\]  
where \(\theta=\angle acb\).  
The \(\theta\) angles obtained are then concatenated to create the histogram representation with bins equally distributed between 0-180\({}^{\circ}\). The optimal number of bins used for histogram representation is determined empirically. The \(RGSIR_{i}\) represents the spatial distribution for a particular visual word \(w_{i}\). The \(RGSIR_{i}\) obtained from all the visual words in an image are concatenated to create the global image representation. A bin replacement technique is used to transform the BoVW representation to RGSIR. This is achieved by replacing each bin of the BoVW histogram with the associated \(RGSIR_{i}\) related to a particular \(w_{i}\). To add the spatial information while keeping the frequency information intact, the sum of all bins of \(RGSIR_{i}\) is normalized to the size of the bin \(bin_{i}\) of the BoVW histogram that is being replaced. The image representation for RGSIR is hence formulated as:  
\[RGSIR=(\alpha_{1}RGSIR_{1},\alpha_{2}RGSIR_{2},.....,\alpha_{K}RGSIR_{K}) \tag{8}\]  
where \(\alpha_{i}\), the coefficient of normalization, is given by \(\alpha_{i}=\frac{bin_{i}}{||RGSIR_{i}||}\). If the size of the visual vocabulary is \(K\) and the number of histogram bins is \(H\), then the dimensions of RGSIR are \(K\times H\).