GCC Code Coverage Report

Directory: ./
File: libfprint/nbis/mindtct/ridges.c
Date: 2024-05-04 14:54:39
Exec Total Coverage
Lines: 171 201 85.1%
Functions: 9 9 100.0%
Branches: 67 94 71.3%
Line Branch Exec Source
1 /*******************************************************************************
2
3 License:
4 This software and/or related materials was developed at the National Institute
5 of Standards and Technology (NIST) by employees of the Federal Government
6 in the course of their official duties. Pursuant to title 17 Section 105
7 of the United States Code, this software is not subject to copyright
8 protection and is in the public domain.
9
10 This software and/or related materials have been determined to be not subject
11 to the EAR (see Part 734.3 of the EAR for exact details) because it is
12 a publicly available technology and software, and is freely distributed
13 to any interested party with no licensing requirements. Therefore, it is
14 permissible to distribute this software as a free download from the internet.
15
16 Disclaimer:
17 This software and/or related materials was developed to promote biometric
18 standards and biometric technology testing for the Federal Government
19 in accordance with the USA PATRIOT Act and the Enhanced Border Security
20 and Visa Entry Reform Act. Specific hardware and software products identified
21 in this software were used in order to perform the software development.
22 In no case does such identification imply recommendation or endorsement
23 by the National Institute of Standards and Technology, nor does it imply that
24 the products and equipment identified are necessarily the best available
25 for the purpose.
26
27 This software and/or related materials are provided "AS-IS" without warranty
28 of any kind including NO WARRANTY OF PERFORMANCE, MERCHANTABILITY,
29 NO WARRANTY OF NON-INFRINGEMENT OF ANY 3RD PARTY INTELLECTUAL PROPERTY
30 or FITNESS FOR A PARTICULAR PURPOSE or for any purpose whatsoever, for the
31 licensed product, however used. In no event shall NIST be liable for any
32 damages and/or costs, including but not limited to incidental or consequential
33 damages of any kind, including economic damage or injury to property and lost
34 profits, regardless of whether NIST shall be advised, have reason to know,
35 or in fact shall know of the possibility.
36
37 By using this software, you agree to bear all risk relating to quality,
38 use and performance of the software and/or related materials. You agree
39 to hold the Government harmless from any claim arising from your use
40 of the software.
41
42 *******************************************************************************/
43
44
45 /***********************************************************************
46 LIBRARY: LFS - NIST Latent Fingerprint System
47
48 FILE: RIDGES.C
49 AUTHOR: Michael D. Garris
50 DATE: 08/09/1999
51 UPDATED: 03/16/2005 by MDG
52
53 Contains routines responsible for locating nearest minutia
54 neighbors and counting intervening ridges as part of the
55 NIST Latent Fingerprint System (LFS).
56
57 ***********************************************************************
58 ROUTINES:
59 count_minutiae_ridges()
60 count_minutia_ridges()
61 find_neighbors()
62 update_nbr_dists()
63 insert_neighbor()
64 sort_neighbors()
65 ridge_count()
66 find_transition()
67 validate_ridge_crossing()
68 ***********************************************************************/
69
70 #include <stdio.h>
71 #include <lfs.h>
72 #include <log.h>
73
74 /*************************************************************************
75 **************************************************************************
76 #cat: count_minutiae_ridges - Takes a list of minutiae, and for each one,
77 #cat: determines its closest neighbors and counts the number
78 #cat: of interveining ridges between the minutia point and
79 #cat: each of its neighbors.
80
81 Input:
82 minutiae - list of minutiae
83 bdata - binary image data (0==while & 1==black)
84 iw - width (in pixels) of image
85 ih - height (in pixels) of image
86 lfsparms - parameters and thresholds for controlling LFS
87 Output:
88 minutiae - list of minutiae augmented with neighbors and ridge counts
89 Return Code:
90 Zero - successful completion
91 Negative - system error
92 **************************************************************************/
93 48 int count_minutiae_ridges(MINUTIAE *minutiae,
94 unsigned char *bdata, const int iw, const int ih,
95 const LFSPARMS *lfsparms)
96 {
97 48 int ret;
98 48 int i;
99
100 48 print2log("\nFINDING NBRS AND COUNTING RIDGES:\n");
101
102 /* Sort minutia points on x then y (column-oriented). */
103
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 if((ret = sort_minutiae_x_y(minutiae, iw, ih))){
104 return(ret);
105 }
106
107 /* Remove any duplicate minutia points from the list. */
108
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 if((ret = rm_dup_minutiae(minutiae))){
109 return(ret);
110 }
111
112 /* Foreach remaining sorted minutia in list ... */
113
2/2
✓ Branch 0 taken 3447 times.
✓ Branch 1 taken 48 times.
 3495 for(i = 0; i < minutiae->num-1; i++){
114 /* Located neighbors and count number of ridges in between. */
115 /* NOTE: neighbor and ridge count results are stored in */
116 /* minutiae->list[i]. */
117
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 3447 times.
 3447 if((ret = count_minutia_ridges(i, minutiae, bdata, iw, ih, lfsparms))){
118 ✗ return(ret);
119 }
120 }
121
122 /* Return normally. */
123 return(0);
124 }
125
126 /*************************************************************************
127 **************************************************************************
128 #cat: count_minutia_ridges - Takes a minutia, and determines its closest
129 #cat: neighbors and counts the number of interveining ridges
130 #cat: between the minutia point and each of its neighbors.
131
132 Input:
133 minutia - input minutia
134 bdata - binary image data (0==while & 1==black)
135 iw - width (in pixels) of image
136 ih - height (in pixels) of image
137 lfsparms - parameters and thresholds for controlling LFS
138 Output:
139 minutiae - minutia augmented with neighbors and ridge counts
140 Return Code:
141 Zero - successful completion
142 Negative - system error
143 **************************************************************************/
144 3447 int count_minutia_ridges(const int first, MINUTIAE *minutiae,
145 unsigned char *bdata, const int iw, const int ih,
146 const LFSPARMS *lfsparms)
147 {
148 3447 int i, ret, *nbr_list, *nbr_nridges, nnbrs;
149
150
1/2
✓ Branch 0 taken 3447 times.
✗ Branch 1 not taken.
 3447 g_assert (lfsparms->max_nbrs > 0);
151
152 /* Find up to the maximum number of qualifying neighbors. */
153 3447 nbr_list = NULL;
154
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 3447 times.
 3447 if((ret = find_neighbors(&nbr_list, &nnbrs, lfsparms->max_nbrs,
155 first, minutiae))){
156 ✗ if (nbr_list != NULL)
157 ✗ g_free(nbr_list);
158 ✗ return(ret);
159 }
160
161 3447 print2log("NBRS FOUND: %d,%d = %d\n", minutiae->list[first]->x,
162 3447 minutiae->list[first]->y, nnbrs);
163
164 /* If no neighors found ... */
165
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3447 times.
 3447 if(nnbrs == 0){
166 /* Then no list returned and no ridges to count. */
167 return(0);
168 }
169
170 /* Sort neighbors on delta dirs. */
171
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 3447 times.
 3447 if((ret = sort_neighbors(nbr_list, nnbrs, first, minutiae))){
172 ✗ g_free(nbr_list);
173 ✗ return(ret);
174 }
175
176 /* Count ridges between first and neighbors. */
177 /* List of ridge counts, one for each neighbor stored. */
178 3447 nbr_nridges = (int *)g_malloc(nnbrs * sizeof(int));
179
180 /* Foreach neighbor found and sorted in list ... */
181
2/2
✓ Branch 1 taken 16762 times.
✓ Branch 2 taken 3447 times.
 23656 for(i = 0; i < nnbrs; i++){
182 /* Count the ridges between the primary minutia and the neighbor. */
183 16762 ret = ridge_count(first, nbr_list[i], minutiae, bdata, iw, ih, lfsparms);
184 /* If system error ... */
185
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16762 times.
 16762 if(ret < 0){
186 /* Deallocate working memories. */
187 ✗ g_free(nbr_list);
188 ✗ g_free(nbr_nridges);
189 /* Return error code. */
190 ✗ return(ret);
191 }
192
193 /* Otherwise, ridge count successful, so store ridge count to list. */
194 16762 nbr_nridges[i] = ret;
195 }
196
197 /* Assign neighbor indices and ridge counts to primary minutia. */
198 3447 minutiae->list[first]->nbrs = nbr_list;
199 3447 minutiae->list[first]->ridge_counts = nbr_nridges;
200 3447 minutiae->list[first]->num_nbrs = nnbrs;
201
202 /* Return normally. */
203 3447 return(0);
204 }
205
206 /*************************************************************************
207 **************************************************************************
208 #cat: find_neighbors - Takes a primary minutia and a list of all minutiae
209 #cat: and locates a specified maximum number of closest neighbors
210 #cat: to the primary point. Neighbors are searched, starting
211 #cat: in the same pixel column, below, the primary point and then
212 #cat: along consecutive and complete pixel columns in the image
213 #cat: to the right of the primary point.
214
215 Input:
216 max_nbrs - maximum number of closest neighbors to be returned
217 first - index of the primary minutia point
218 minutiae - list of minutiae
219 Output:
220 onbr_list - points to list of detected closest neighbors
221 onnbrs - points to number of neighbors returned
222 Return Code:
223 Zero - successful completion
224 Negative - system error
225 **************************************************************************/
226 3447 int find_neighbors(int **onbr_list, int *onnbrs, const int max_nbrs,
227 const int first, MINUTIAE *minutiae)
228 {
229 3447 int ret, second, last_nbr;
230 3447 MINUTIA *minutia1, *minutia2;
231 3447 int *nbr_list, nnbrs;
232 3447 double *nbr_sqr_dists, xdist, xdist2;
233
234 /* Allocate list of neighbor minutiae indices. */
235 3447 nbr_list = (int *)g_malloc(max_nbrs * sizeof(int));
236
237 /* Allocate list of squared euclidean distances between neighbors */
238 /* and current primary minutia point. */
239 3447 nbr_sqr_dists = (double *)g_malloc(max_nbrs * sizeof(double));
240
241 /* Initialize number of stored neighbors to 0. */
242 3447 nnbrs = 0;
243 /* Assign secondary to one passed current primary minutia. */
244 3447 second = first + 1;
245 /* Compute location of maximum last stored neighbor. */
246 3447 last_nbr = max_nbrs - 1;
247
248 /* While minutia (in sorted order) still remian for processing ... */
249 /* NOTE: The minutia in the input list have been sorted on X and */
250 /* then on Y. So, the neighbors are selected according to those */
251 /* that lie below the primary minutia in the same pixel column and */
252 /* then subsequently those that lie in complete pixel columns to */
253 /* the right of the primary minutia. */
254
2/2
✓ Branch 0 taken 57953 times.
✓ Branch 1 taken 642 times.
 58595 while(second < minutiae->num){
255 /* Assign temporary minutia pointers. */
256 57953 minutia1 = minutiae->list[first];
257 57953 minutia2 = minutiae->list[second];
258
259 /* Compute squared distance between minutiae along x-axis. */
260 57953 xdist = minutia2->x - minutia1->x;
261 57953 xdist2 = xdist * xdist;
262
263 /* If the neighbor lists are not full OR the x-distance to current */
264 /* secondary is smaller than maximum neighbor distance stored ... */
265
2/2
✓ Branch 0 taken 41191 times.
✓ Branch 1 taken 16762 times.
 57953 if((nnbrs < max_nbrs) ||
266
2/2
✓ Branch 0 taken 38386 times.
✓ Branch 1 taken 2805 times.
 41191 (xdist2 < nbr_sqr_dists[last_nbr])){
267 /* Append or insert the new neighbor into the neighbor lists. */
268
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 55148 times.
 55148 if((ret = update_nbr_dists(nbr_list, nbr_sqr_dists, &nnbrs, max_nbrs,
269 first, second, minutiae))){
270 ✗ g_free(nbr_sqr_dists);
271 ✗ g_free(nbr_list);
272 ✗ return(ret);
273 }
274 }
275 /* Otherwise, if the neighbor lists is full AND the x-distance */
276 /* to current secondary is larger than maximum neighbor distance */
277 /* stored ... */
278 else
279 /* So, stop searching for more neighbors. */
280 break;
281
282 /* Bump to next secondary minutia. */
283 55148 second++;
284 }
285
286 /* Deallocate working memory. */
287 3447 g_free(nbr_sqr_dists);
288
289 /* If no neighbors found ... */
290
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3447 times.
 3447 if(nnbrs == 0){
291 /* Deallocate the neighbor list. */
292 ✗ g_free(nbr_list);
293 ✗ *onnbrs = 0;
294 }
295 /* Otherwise, assign neighbors to output pointer. */
296 else{
297 3447 *onbr_list = nbr_list;
298 3447 *onnbrs = nnbrs;
299 }
300
301 /* Return normally. */
302 return(0);
303 }
304
305 /*************************************************************************
306 **************************************************************************
307 #cat: update_nbr_dists - Takes the current list of neighbors along with a
308 #cat: primary minutia and a potential new neighbor, and
309 #cat: determines if the new neighbor is sufficiently close
310 #cat: to be added to the list of nearest neighbors. If added,
311 #cat: it is placed in the list in its proper order based on
312 #cat: squared distance to the primary point.
313
314 Input:
315 nbr_list - current list of nearest neighbor minutia indices
316 nbr_sqr_dists - corresponding squared euclidean distance of each
317 neighbor to the primary minutia point
318 nnbrs - number of neighbors currently in the list
319 max_nbrs - maximum number of closest neighbors to be returned
320 first - index of the primary minutia point
321 second - index of the secondary (new neighbor) point
322 minutiae - list of minutiae
323 Output:
324 nbr_list - updated list of nearest neighbor indices
325 nbr_sqr_dists - updated list of nearest neighbor distances
326 nnbrs - number of neighbors in the update lists
327 Return Code:
328 Zero - successful completion
329 Negative - system error
330 **************************************************************************/
331 55148 int update_nbr_dists(int *nbr_list, double *nbr_sqr_dists,
332 int *nnbrs, const int max_nbrs,
333 const int first, const int second, MINUTIAE *minutiae)
334 {
335 55148 double dist2;
336 55148 MINUTIA *minutia1, *minutia2;
337 55148 int pos, last_nbr;
338
339 /* Compute position of maximum last neighbor stored. */
340 55148 last_nbr = max_nbrs - 1;
341
342 /* Assigne temporary minutia pointers. */
343 55148 minutia1 = minutiae->list[first];
344 55148 minutia2 = minutiae->list[second];
345
346 /* Compute squared euclidean distance between minutia pair. */
347 55148 dist2 = squared_distance(minutia1->x, minutia1->y,
348 minutia2->x, minutia2->y);
349
350 /* If maximum number of neighbors not yet stored in lists OR */
351 /* if the squared distance to current secondary is less */
352 /* than the largest stored neighbor distance ... */
353
2/2
✓ Branch 0 taken 38386 times.
✓ Branch 1 taken 16762 times.
 55148 if((*nnbrs < max_nbrs) ||
354
2/2
✓ Branch 0 taken 16921 times.
✓ Branch 1 taken 21465 times.
 38386 (dist2 < nbr_sqr_dists[last_nbr])){
355
356 /* Find insertion point in neighbor lists. */
357 33683 pos = find_incr_position_dbl(dist2, nbr_sqr_dists, *nnbrs);
358 /* If the position returned is >= maximum list length (this should */
359 /* never happen, but just in case) ... */
360
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 33683 times.
 33683 if(pos >= max_nbrs){
361 ✗ fprintf(stderr,
362 "ERROR : update_nbr_dists : illegal position for new neighbor\n");
363 ✗ return(-470);
364 }
365 /* Insert the new neighbor into the neighbor lists at the */
366 /* specified location. */
367
1/2
✓ Branch 1 taken 33683 times.
✗ Branch 2 not taken.
 33683 if(insert_neighbor(pos, second, dist2,
368 nbr_list, nbr_sqr_dists, nnbrs, max_nbrs))
369 return(-471);
370
371 /* Otherwise, neighbor inserted successfully, so return normally. */
372 return(0);
373 }
374 /* Otherwise, the new neighbor is not sufficiently close to be */
375 /* added or inserted into the neighbor lists, so ignore the neighbor */
376 /* and return normally. */
377 else
378 return(0);
379
380 }
381
382 /*************************************************************************
383 **************************************************************************
384 #cat: insert_neighbor - Takes a minutia index and its squared distance to a
385 #cat: primary minutia point, and inserts them in the specified
386 #cat: position of their respective lists, shifting previously
387 #cat: stored values down and off the lists as necessary.
388
389 Input:
390 pos - postions where values are to be inserted in lists
391 nbr_index - index of minutia being inserted
392 nbr_dist2 - squared distance of minutia to its primary point
393 nbr_list - current list of nearest neighbor minutia indices
394 nbr_sqr_dists - corresponding squared euclidean distance of each
395 neighbor to the primary minutia point
396 nnbrs - number of neighbors currently in the list
397 max_nbrs - maximum number of closest neighbors to be returned
398 Output:
399 nbr_list - updated list of nearest neighbor indices
400 nbr_sqr_dists - updated list of nearest neighbor distances
401 nnbrs - number of neighbors in the update lists
402 Return Code:
403 Zero - successful completion
404 Negative - system error
405 **************************************************************************/
406 33683 int insert_neighbor(const int pos, const int nbr_index, const double nbr_dist2,
407 int *nbr_list, double *nbr_sqr_dists,
408 int *nnbrs, const int max_nbrs)
409 {
410 33683 int i;
411
412
1/2
✓ Branch 0 taken 33683 times.
✗ Branch 1 not taken.
 33683 g_assert (pos >= 0);
413
414 /* If the desired insertion position is beyond one passed the last */
415 /* neighbor in the lists OR greater than equal to the maximum ... */
416 /* NOTE: pos is zero-oriented while nnbrs and max_nbrs are 1-oriented. */
417
2/4
✓ Branch 0 taken 33683 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 33683 times.
 33683 if((pos > *nnbrs) ||
418 (pos >= max_nbrs)){
419 ✗ fprintf(stderr,
420 "ERROR : insert_neighbor : insertion point exceeds lists\n");
421 ✗ return(-480);
422 }
423
424 /* If the neighbor lists are NOT full ... */
425
2/2
✓ Branch 0 taken 16762 times.
✓ Branch 1 taken 16921 times.
 33683 if(*nnbrs < max_nbrs){
426 /* Then we have room to shift everything down to make room for new */
427 /* neighbor and increase the number of neighbors stored by 1. */
428 16762 i = *nnbrs-1;
429 16762 (*nnbrs)++;
430 }
431 /* Otherwise, the neighbors lists are full ... */
432
1/2
✓ Branch 0 taken 16921 times.
✗ Branch 1 not taken.
 16921 else if(*nnbrs == max_nbrs)
433 /* So, we must bump the last neighbor in the lists off to make */
434 /* room for the new neighbor (ignore last neighbor in lists). */
435 16921 i = *nnbrs-2;
436 /* Otherwise, there is a list overflow error condition */
437 /* (shouldn't ever happen, but just in case) ... */
438 else{
439 ✗ fprintf(stderr,
440 "ERROR : insert_neighbor : overflow in neighbor lists\n");
441 ✗ return(-481);
442 }
443
444 /* While we havn't reached the desired insertion point ... */
445
2/2
✓ Branch 0 taken 43276 times.
✓ Branch 1 taken 33683 times.
 76959 while(i >= pos){
446 /* Shift the current neighbor down the list 1 positon. */
447 43276 nbr_list[i+1] = nbr_list[i];
448 43276 nbr_sqr_dists[i+1] = nbr_sqr_dists[i];
449 43276 i--;
450 }
451
452 /* We are now ready to put our new neighbor in the position where */
453 /* we shifted everything down from to make room. */
454 33683 nbr_list[pos] = nbr_index;
455 33683 nbr_sqr_dists[pos] = nbr_dist2;
456
457 /* Return normally. */
458 33683 return(0);
459 }
460
461 /*************************************************************************
462 **************************************************************************
463 #cat: sort_neighbors - Takes a list of primary minutia and its neighboring
464 #cat: minutia indices and sorts the neighbors based on their
465 #cat: position relative to the primary minutia point. Neighbors
466 #cat: are sorted starting vertical to the primary point and
467 #cat: proceeding clockwise.
468
469 Input:
470 nbr_list - list of neighboring minutia indices
471 nnbrs - number of neighbors in the list
472 first - the index of the primary minutia point
473 minutiae - list of minutiae
474 Output:
475 nbr_list - neighboring minutia indices in sorted order
476 Return Code:
477 Zero - successful completion
478 Negative - system error
479 **************************************************************************/
480 3447 int sort_neighbors(int *nbr_list, const int nnbrs, const int first,
481 MINUTIAE *minutiae)
482 {
483 3447 double *join_thetas, theta;
484 3447 int i;
485 3447 static double pi2 = M_PI*2.0;
486
487 /* List of angles of lines joining the current primary to each */
488 /* of the secondary neighbors. */
489 3447 join_thetas = (double *)g_malloc(nnbrs * sizeof(double));
490
491
2/2
✓ Branch 1 taken 16762 times.
✓ Branch 2 taken 3447 times.
 23656 for(i = 0; i < nnbrs; i++){
492 /* Compute angle to line connecting the 2 points. */
493 /* Coordinates are swapped and order of points reversed to */
494 /* account for 0 direction is vertical and positive direction */
495 /* is clockwise. */
496 33524 theta = angle2line(minutiae->list[nbr_list[i]]->y,
497 16762 minutiae->list[nbr_list[i]]->x,
498 minutiae->list[first]->y,
499 16762 minutiae->list[first]->x);
500
501 /* Make sure the angle is positive. */
502 16762 theta += pi2;
503 16762 theta = fmod(theta, pi2);
504 16762 join_thetas[i] = theta;
505 }
506
507 /* Sort the neighbor indicies into rank order. */
508 3447 bubble_sort_double_inc_2(join_thetas, nbr_list, nnbrs);
509
510 /* Deallocate the list of angles. */
511 3447 g_free(join_thetas);
512
513 /* Return normally. */
514 3447 return(0);
515 }
516
517 /*************************************************************************
518 **************************************************************************
519 #cat: ridge_count - Takes a pair of minutiae, and counts the number of
520 #cat: ridges crossed along the linear trajectory connecting
521 #cat: the 2 points in the image.
522
523 Input:
524 first - index of primary minutia
525 second - index of secondary (neighbor) minutia
526 minutiae - list of minutiae
527 bdata - binary image data (0==while & 1==black)
528 iw - width (in pixels) of image
529 ih - height (in pixels) of image
530 lfsparms - parameters and thresholds for controlling LFS
531 Return Code:
532 Zero or Positive - number of ridges counted
533 Negative - system error
534 **************************************************************************/
535 16762 int ridge_count(const int first, const int second, MINUTIAE *minutiae,
536 unsigned char *bdata, const int iw, const int ih,
537 const LFSPARMS *lfsparms)
538 {
539 16762 MINUTIA *minutia1, *minutia2;
540 16762 int i, ret, found;
541 16762 int *xlist, *ylist, num;
542 16762 int ridge_count, ridge_start, ridge_end;
543 16762 int prevpix, curpix;
544
545 16762 minutia1 = minutiae->list[first];
546 16762 minutia2 = minutiae->list[second];
547
548 /* If the 2 mintuia have identical pixel coords ... */
549
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16762 times.
 16762 if((minutia1->x == minutia2->x) &&
550 (minutia1->y == minutia2->y))
551 /* Then zero ridges between points. */
552 return(0);
553
554 /* Compute linear trajectory of contiguous pixels between first */
555 /* and second minutia points. */
556
1/2
✓ Branch 1 taken 16762 times.
✗ Branch 2 not taken.
 16762 if((ret = line_points(&xlist, &ylist, &num,
557 minutia1->x, minutia1->y, minutia2->x, minutia2->y))){
558 return(ret);
559 }
560
561 /* It there are no points on the line trajectory, then no ridges */
562 /* to count (this should not happen, but just in case) ... */
563
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16762 times.
 16762 if(num == 0){
564 ✗ g_free(xlist);
565 ✗ g_free(ylist);
566 ✗ return(0);
567 }
568
569 /* Find first pixel opposite type along linear trajectory from */
570 /* first minutia. */
571 16762 prevpix = *(bdata+(ylist[0]*iw)+xlist[0]);
572 16762 i = 1;
573 16762 found = FALSE;
574
2/2
✓ Branch 0 taken 40577 times.
✓ Branch 1 taken 12 times.
 40589 while(i < num){
575 40577 curpix = *(bdata+(ylist[i]*iw)+xlist[i]);
576
2/2
✓ Branch 0 taken 23827 times.
✓ Branch 1 taken 16750 times.
 40577 if(curpix != prevpix){
577 found = TRUE;
578 break;
579 }
580 23827 i++;
581 }
582
583 /* If opposite pixel not found ... then no ridges to count */
584
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 16750 times.
 16762 if(!found){
585 12 g_free(xlist);
586 12 g_free(ylist);
587 12 return(0);
588 }
589
590 /* Ready to count ridges, so initialize counter to 0. */
591 16750 ridge_count = 0;
592
593 16750 print2log("RIDGE COUNT: %d,%d to %d,%d ", minutia1->x, minutia1->y,
594 minutia2->x, minutia2->y);
595
596 /* While not at the end of the trajectory ... */
597
1/2
✓ Branch 1 taken 71471 times.
✗ Branch 2 not taken.
 71471 while(i < num){
598 /* If 0-to-1 transition not found ... */
599
2/2
✓ Branch 1 taken 8840 times.
✓ Branch 2 taken 62631 times.
 71471 if(!find_transition(&i, 0, 1, xlist, ylist, num, bdata, iw, ih)){
600 /* Then we are done looking for ridges. */
601 8840 g_free(xlist);
602 8840 g_free(ylist);
603
604 8840 print2log("\n");
605
606 /* Return number of ridges counted to this point. */
607 8840 return(ridge_count);
608 }
609 /* Otherwise, we found a new ridge start transition, so store */
610 /* its location (the location of the 1 in 0-to-1 transition). */
611 62631 ridge_start = i;
612
613 62631 print2log(": RS %d,%d ", xlist[i], ylist[i]);
614
615 /* If 1-to-0 transition not found ... */
616
2/2
✓ Branch 1 taken 7910 times.
✓ Branch 2 taken 54721 times.
 62631 if(!find_transition(&i, 1, 0, xlist, ylist, num, bdata, iw, ih)){
617 /* Then we are done looking for ridges. */
618 7910 g_free(xlist);
619 7910 g_free(ylist);
620
621 7910 print2log("\n");
622
623 /* Return number of ridges counted to this point. */
624 7910 return(ridge_count);
625 }
626 /* Otherwise, we found a new ridge end transition, so store */
627 /* its location (the location of the 0 in 1-to-0 transition). */
628 54721 ridge_end = i;
629
630 54721 print2log("; RE %d,%d ", xlist[i], ylist[i]);
631
632 /* Conduct the validation, tracing the contour of the ridge */
633 /* from the ridge ending point a specified number of steps */
634 /* scanning for neighbors clockwise and counter-clockwise. */
635 /* If the ridge starting point is encounted during the trace */
636 /* then we can assume we do not have a valid ridge crossing */
637 /* and instead we are walking on and off the edge of the */
638 /* side of a ridge. */
639 109442 ret = validate_ridge_crossing(ridge_start, ridge_end,
640 xlist, ylist, num, bdata, iw, ih,
641 54721 lfsparms->max_ridge_steps);
642
643 /* If system error ... */
644
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 54721 times.
 54721 if(ret < 0){
645 ✗ g_free(xlist);
646 ✗ g_free(ylist);
647 /* Return the error code. */
648 ✗ return(ret);
649 }
650
651 54721 print2log("; V%d ", ret);
652
653 /* If validation result is TRUE ... */
654
2/2
✓ Branch 0 taken 47949 times.
✓ Branch 1 taken 6772 times.
 54721 if(ret){
655 /* Then assume we have found a valid ridge crossing and bump */
656 /* the ridge counter. */
657 47949 ridge_count++;
658 }
659
660 /* Otherwise, ignore the current ridge start and end transitions */
661 /* and go back and search for new ridge start. */
662 }
663
664 /* Deallocate working memories. */
665 ✗ g_free(xlist);
666 ✗ g_free(ylist);
667
668 ✗ print2log("\n");
669
670 /* Return the number of ridges counted. */
671 ✗ return(ridge_count);
672 }
673
674 /*************************************************************************
675 **************************************************************************
676 #cat: find_transition - Takes a pixel trajectory and a starting index, and
677 #cat: searches forward along the trajectory until the specified
678 #cat: adjacent pixel pair is found, returning the index where
679 #cat: the pair was found (the index of the second pixel).
680
681 Input:
682 iptr - pointer to starting pixel index into trajectory
683 pix1 - first pixel value in transition pair
684 pix2 - second pixel value in transition pair
685 xlist - x-pixel coords of line trajectory
686 ylist - y-pixel coords of line trajectory
687 num - number of coords in line trajectory
688 bdata - binary image data (0==while & 1==black)
689 iw - width (in pixels) of image
690 ih - height (in pixels) of image
691 Output:
692 iptr - points to location where 2nd pixel in pair is found
693 Return Code:
694 TRUE - pixel pair transition found
695 FALSE - pixel pair transition not found
696 **************************************************************************/
697 134102 int find_transition(int *iptr, const int pix1, const int pix2,
698 const int *xlist, const int *ylist, const int num,
699 unsigned char *bdata, const int iw, const int ih)
700 {
701 134102 int i, j;
702
703 /* Set previous index to starting position. */
704 134102 i = *iptr;
705 /* Bump previous index by 1 to get next index. */
706 134102 j = i+1;
707
708 /* While not one point from the end of the trajectory .. */
709
2/2
✓ Branch 0 taken 536514 times.
✓ Branch 1 taken 16750 times.
 553264 while(i < num-1){
710 /* If we have found the desired transition ... */
711
2/2
✓ Branch 0 taken 489415 times.
✓ Branch 1 taken 47099 times.
 536514 if((*(bdata+(ylist[i]*iw)+xlist[i]) == pix1) &&
712
2/2
✓ Branch 0 taken 117352 times.
✓ Branch 1 taken 372063 times.
 489415 (*(bdata+(ylist[j]*iw)+xlist[j]) == pix2)){
713 /* Adjust the position pointer to the location of the */
714 /* second pixel in the transition. */
715 117352 *iptr = j;
716
717 /* Return TRUE. */
718 117352 return(TRUE);
719 }
720 /* Otherwise, the desired transition was not found in current */
721 /* pixel pair, so bump to the next pair along the trajector. */
722 419162 i++;
723 419162 j++;
724 }
725
726 /* If we get here, then we exhausted the trajector without finding */
727 /* the desired transition, so set the position pointer to the end */
728 /* of the trajector, and return FALSE. */
729 16750 *iptr = num;
730 16750 return(FALSE);
731 }
732
733 /*************************************************************************
734 **************************************************************************
735 #cat: validate_ridge_crossing - Takes a pair of points, a ridge start
736 #cat: transition and a ridge end transition, and walks the
737 #cat: ridge contour from thre ridge end points a specified
738 #cat: number of steps, looking for the ridge start point.
739 #cat: If found, then transitions determined not to be a valid
740 #cat: ridge crossing.
741
742 Input:
743 ridge_start - index into line trajectory of ridge start transition
744 ridge_end - index into line trajectory of ridge end transition
745 xlist - x-pixel coords of line trajectory
746 ylist - y-pixel coords of line trajectory
747 num - number of coords in line trajectory
748 bdata - binary image data (0==while & 1==black)
749 iw - width (in pixels) of image
750 ih - height (in pixels) of image
751 max_ridge_steps - number of steps taken in search in both
752 scan directions
753 Return Code:
754 TRUE - ridge crossing VALID
755 FALSE - ridge corssing INVALID
756 Negative - system error
757 **************************************************************************/
758 54721 int validate_ridge_crossing(const int ridge_start, const int ridge_end,
759 const int *xlist, const int *ylist, const int num,
760 unsigned char *bdata, const int iw, const int ih,
761 const int max_ridge_steps)
762 {
763 54721 int ret;
764 54721 int feat_x, feat_y, edge_x, edge_y;
765 54721 int *contour_x, *contour_y, *contour_ex, *contour_ey, ncontour;
766
767 /* Assign edge pixel pair for contour trace. */
768 54721 feat_x = xlist[ridge_end];
769 54721 feat_y = ylist[ridge_end];
770 54721 edge_x = xlist[ridge_end-1];
771 54721 edge_y = ylist[ridge_end-1];
772
773 /* Adjust pixel pair if they neighbor each other diagonally. */
774 54721 fix_edge_pixel_pair(&feat_x, &feat_y, &edge_x, &edge_y,
775 bdata, iw, ih);
776
777 /* Trace ridge contour, starting at the ridge end transition, and */
778 /* taking a specified number of step scanning for edge neighbors */
779 /* clockwise. As we trace the ridge, we want to detect if we */
780 /* encounter the ridge start transition. NOTE: The ridge end */
781 /* position is on the white (of a black to white transition) and */
782 /* the ridge start is on the black (of a black to white trans), */
783 /* so the edge trace needs to look for the what pixel (not the */
784 /* black one) of the ridge start transition. */
785 109442 ret = trace_contour(&contour_x, &contour_y,
786 &contour_ex, &contour_ey, &ncontour,
787 max_ridge_steps,
788 54721 xlist[ridge_start-1], ylist[ridge_start-1],
789 feat_x, feat_y, edge_x, edge_y,
790 SCAN_CLOCKWISE, bdata, iw, ih);
791 /* If a system error occurred ... */
792
1/2
✓ Branch 0 taken 54721 times.
✗ Branch 1 not taken.
 54721 if(ret < 0)
793 /* Return error code. */
794 return(ret);
795
796 /* Otherwise, if the trace was not IGNORED, then a contour was */
797 /* was generated and returned. We aren't interested in the */
798 /* actual contour, so deallocate it. */
799
1/2
✓ Branch 0 taken 54721 times.
✗ Branch 1 not taken.
 54721 if(ret != IGNORE)
800 54721 free_contour(contour_x, contour_y, contour_ex, contour_ey);
801
802 /* If the trace was IGNORED, then we had some sort of initialization */
803 /* problem, so treat this the same as if was actually located the */
804 /* ridge start point (in which case LOOP_FOUND is returned). */
805 /* So, If not IGNORED and ridge start not encounted in trace ... */
806
2/2
✓ Branch 0 taken 51312 times.
✓ Branch 1 taken 3409 times.
 54721 if((ret != IGNORE) &&
807 (ret != LOOP_FOUND)){
808
809 /* Now conduct contour trace scanning for edge neighbors counter- */
810 /* clockwise. */
811 51312 ret = trace_contour(&contour_x, &contour_y,
812 &contour_ex, &contour_ey, &ncontour,
813 max_ridge_steps,
814 xlist[ridge_start-1], ylist[ridge_start-1],
815 feat_x, feat_y, edge_x, edge_y,
816 SCAN_COUNTER_CLOCKWISE, bdata, iw, ih);
817 /* If a system error occurred ... */
818
1/2
✓ Branch 0 taken 51312 times.
✗ Branch 1 not taken.
 51312 if(ret < 0)
819 /* Return error code. */
820 return(ret);
821
822 /* Otherwise, if the trace was not IGNORED, then a contour was */
823 /* was generated and returned. We aren't interested in the */
824 /* actual contour, so deallocate it. */
825
1/2
✓ Branch 0 taken 51312 times.
✗ Branch 1 not taken.
 51312 if(ret != IGNORE)
826 51312 free_contour(contour_x, contour_y, contour_ex, contour_ey);
827
828 /* If trace not IGNORED and ridge start not encounted in 2nd trace ... */
829
2/2
✓ Branch 0 taken 3363 times.
✓ Branch 1 taken 47949 times.
 51312 if((ret != IGNORE) &&
830 (ret != LOOP_FOUND)){
831 /* If we get here, assume we have a ridge crossing. */
832 return(TRUE);
833 }
834 /* Otherwise, second trace returned IGNORE or ridge start found. */
835 }
836 /* Otherwise, first trace returned IGNORE or ridge start found. */
837
838 /* If we get here, then we failed to validate a ridge crossing. */
839 return(FALSE);
840 }
841