# Invariant Feature Encoding for Contact Handprints Using Delaunay Triangulated Graph
## 3 Proposed Method
### Delaunay-Triangle-Graph (DTG) Algorithm
#### 3.1.2 Extension of Sub-Graph  
In this phase, the matched triplets in two images are chosen as base triangle pairs and located as reference triangles. Each base triangle is then expanded by adding neighboring triangles by comparing the neighboring triangles' spatial locality information with the previous matched triplets. This process formed a certain number of sub-graphs in a disjoint manner. Here the triangles may or may not share a pair of edges or pair of minutiae for the alignment of images. This is a validation process of the previously matched triangles. At the beginning, the first _base-triangle_ pair is selected as an initial reference location to proceed as follows:  
* **Task A--Computation of orientation and distance information between the pair of base-triangles. ** Initial reference location is identified by selecting the _base-triangles_ in template and test images. The features of three minutiae between first and second base triangles are computed as shown in Equation (2). A similar process is followed in test image as well. \[\phi_{n}=or_{n}-or_{m}\text{ and }\phi_{n}^{\prime}=or_{n}^{\prime}-or_{m}^{\prime}\] (2) \[or_{n}\text{--orientation of }n\text{th minutiae in the first base triplet in template ($n=1$, 2$, 3)}.\] \[or_{n}^{\prime}\text{--orientation of }n\text{th minutiae in the first base triplet in query image.}\] \[or_{n}^{\prime}\text{--orientation of }n\text{th minutiae in the second base triplet in query image.}\]  
A distance between \(n\)th and \(m\)th minutiae (where \(m=n\)) in the first and second base triangles in template image is computed as \(Dis_{n}\). A similar process is followed in the query image and the distance is \(Dis_{n}^{\prime}\). Since distance feature can be affected by skin stretch, a distance ratio is used for further computation. * **Task B--Computation of distance ratio and orientation difference between template and probe. ** \[DRat_{n}=Dis_{n}/Dis_{n}^{\prime}\] \[\phi_{D}if_{n}=\phi_{n}-\phi_{n}^{\prime}\] (3) \[(DRat_{n})\text{--Ratio of two distances between the base triangles acquired from template and test images.}\] \[(\phi_{D}if_{n})\text{--Orientation difference between the base triangles acquired from template and test images.}\]To form a sub-graph, a minutia node in the second base triangle was added to the nodes of the first base triangle if \(\phi_{D}if_{n}<\theta\), \(Dstat_{n}<d\). Trial and error experiments were used to empirically determine the values for \(d\) and \(\theta\). The above two steps are significantly different from the existing past minutiae-triangle-based work. The majority of them used distance and orientation of minutiae in a triangle as features. The triangle matching was one-one or one-one graph matching with a centralized minutiae. The validation of those final matched triangles is completely ignored. The relative information about the neighboring triangles of a previously matched triangle is comparatively ignored. Here, we have used such information and utilized the distance ratio between two base triangles in order to overcome the scale change and distortion. * **Iteration of Tasks A and B** The processes of A and B were repeated until computing the relational information between the first base triangle and the remaining \((N-1)\) triangles. This process generates a sub-graph with fewer or more triangles based on the matching images from different individuals or the same individual. * **Iteration of Tasks A, B, and C** For the continuation of the above process, the second base triangle was located as initial reference point. The process was repeated to finalize that the \(N\)th base triangle was referenced. Sub-graphs were generated through this process, as shown in Figure 5, where one triplet is the base triangle or reference location and the other triangles are related triangles with the base in each graph, and they match with their counter part. Figure 5: Phase 2: graphs generated in template image and their matching counterparts in test image are shown.