# Individuals Identification Based on Palm Vein Matching under a Parallel Environment
## 3 Methodology
### Sparse Matching of Palm Vein Images  
To obtain the displacement matrices, it is necessary to find the correspondence between the veins images to be compared. For this, it is considered that the best correspondence for a point must present the most similar features. In this regard and different to [45] which is based on a dense matching algorithm, we propose using a sparse matching method combining a random search strategy with a coarse-to-fine scheme for optical flow with large displacements. Our method introduces the CPM algorithm proposed in [52] for palm vein identification. The key idea of CPM is that matching correspondences with larger patch size are often more discriminative. In addition, the proposed technique implements a fast approximate structure for the matching process, which finds the best correspondence of some seeds and it avoids finding the matching of every pixel, leading to a significant speed-up. In the following, we present the main characteristics of the matching process of our methodology. Formally in [52], CPM is defined for two images \(I_{1}\), \(I_{2}\subset\mathbb{R}^{2}\), and a collection of seeds \(\mathcal{S}=\{s_{m}\}\) at position \(\{p(s_{m})\}\), aiming to determine the flow of each seed as follows:  
\[f(s_{m})=\mathcal{M}(p(s_{m}))-p(s_{m})\in\mathbb{R}, \tag{4}\]  
where \(\mathcal{M}(p(s_{m}))\) is the corresponding matching position in \(I_{2}\) for seed \(s_{m}\) in \(I_{1}\), and the seeds are the cross points of the regular image grid with a spacing of \(d\) pixels, obtaining only one seed in every \(d\times d\) non-overlapping block. Hence, a neighbor system is obtained according to the spatial adjacency of the seeds on the image grid. CPM performs a neighborhood propagation and random search iteratively in an interleaved manner. Seeds are examined in scan order on odd iterations and in reverse scan order on even iterations. Then, flow values are propagated from neighbor seeds to current seed if they have already been examined in the current iteration, as the next equation:  
\[f(s_{m})=arg\min_{f(s_{i})}(C(f(s_{i}))),s_{i}\in\{s_{m}\}\cup\mathcal{N}_{m}, \tag{5}\]  
where \(C(f(\cdot))\) denotes the match cost between patch centered at \(p(s_{m})\) in \(I_{1}\) and patch centered at \(p(s_{m})+f(\cdot)\) in \(I_{2}\); and \(\mathcal{N}_{m}\) is the set of spatially adjacent seed neighbors of \(s_{m}\) that is already examined in current iterations. Afterward, a random search is performed for the current seed \(s_{m}\) by testing some candidate flow around the current best flow \(f(s_{m})\), at an exponentially decreasing scope started from a maximum search radius. As in [52], the ratio \(\alpha\) between the two consecutive search scopes is fixed to \(1/2\) and the matching process is performed for a fixed number of iteration \(n\). Another important improvement implemented by [PERSON] et al. [52] is the coarse-to-fine scheme for propagation, which is a simple but powerful hierarchical structure to handle the ambiguity of small patches. First, a pyramid with \(k\) levels is constructed for both \(I_{1}\) and \(I_{2}\) with a downsampling factor \(\eta=0.5\). Then, the matches are found for every seed \(\{s^{l}\}\) on the \(l\)th level of the pyramids for both images, where \(l\in\{0,1,\ldots,k-1\}\). It should be noted that the seeds on each level preserve the same neighboring relation as the finest level, and the number of seeds is the same on each level. After the construction of the pyramid, the algorithm propagates the flow of each seed from top to bottom on the pyramid with a random search. First, the flow of the seeds on the top level \(\{f(s^{k-1})\}\) is set randomly.