GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 86.3% 176 / 0 / 204
Functions: 100.0% 9 / 0 / 9
Branches: 71.9% 69 / 0 / 96
libfprint/nbis/mindtct/ridges.c
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 50 int count_minutiae_ridges(MINUTIAE *minutiae,
94 unsigned char *bdata, const int iw, const int ih,
95 const LFSPARMS *lfsparms)
96 {
97 50 int ret;
98 50 int i;
99
100 50 print2log("\nFINDING NBRS AND COUNTING RIDGES:\n");
101
102 /* Sort minutia points on x then y (column-oriented). */
103
1/2
✓ Branch 4 → 5 taken 50 times.
✗ Branch 4 → 11 not taken.
 50 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 6 → 10 taken 50 times.
✗ Branch 6 → 11 not taken.
 50 if((ret = rm_dup_minutiae(minutiae))){
109 return(ret);
110 }
111
112 /* Foreach remaining sorted minutia in list ... */
113
2/2
✓ Branch 10 → 7 taken 3659 times.
✓ Branch 10 → 11 taken 50 times.
 3709 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 8 → 9 taken 3659 times.
✗ Branch 8 → 11 not taken.
 3659 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 3659 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 3659 int i, ret, *nbr_list, *nbr_nridges, nnbrs;
149
150
1/2
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 3659 times.
 3659 g_assert (lfsparms->max_nbrs > 0);
151
152 /* Find up to the maximum number of qualifying neighbors. */
153 3659 nbr_list = NULL;
154
1/2
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 8 taken 3659 times.
 3659 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 3659 print2log("NBRS FOUND: %d,%d = %d\n", minutiae->list[first]->x,
162 3659 minutiae->list[first]->y, nnbrs);
163
164 /* If no neighors found ... */
165
1/2
✓ Branch 9 → 10 taken 3659 times.
✗ Branch 9 → 24 not taken.
 3659 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 11 → 12 not taken.
✓ Branch 11 → 14 taken 3659 times.
 3659 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 3659 nbr_nridges = (int *)g_malloc(nnbrs * sizeof(int));
179
180 /* Foreach neighbor found and sorted in list ... */
181
2/2
✓ Branch 22 → 16 taken 17802 times.
✓ Branch 22 → 23 taken 3659 times.
 25120 for(i = 0; i < nnbrs; i++){
182 /* Count the ridges between the primary minutia and the neighbor. */
183 17802 ret = ridge_count(first, nbr_list[i], minutiae, bdata, iw, ih, lfsparms);
184 /* If system error ... */
185
1/2
✗ Branch 17 → 18 not taken.
✓ Branch 17 → 21 taken 17802 times.
 17802 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 17802 nbr_nridges[i] = ret;
195 }
196
197 /* Assign neighbor indices and ridge counts to primary minutia. */
198 3659 minutiae->list[first]->nbrs = nbr_list;
199 3659 minutiae->list[first]->ridge_counts = nbr_nridges;
200 3659 minutiae->list[first]->num_nbrs = nnbrs;
201
202 /* Return normally. */
203 3659 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 3659 int find_neighbors(int **onbr_list, int *onnbrs, const int max_nbrs,
227 const int first, MINUTIAE *minutiae)
228 {
229 3659 int ret, second, last_nbr;
230 3659 MINUTIA *minutia1, *minutia2;
231 3659 int *nbr_list, nnbrs;
232 3659 double *nbr_sqr_dists, xdist, xdist2;
233
234 /* Allocate list of neighbor minutiae indices. */
235 3659 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 3659 nbr_sqr_dists = (double *)g_malloc(max_nbrs * sizeof(double));
240
241 /* Initialize number of stored neighbors to 0. */
242 3659 nnbrs = 0;
243 /* Assign secondary to one passed current primary minutia. */
244 3659 second = first + 1;
245 /* Compute location of maximum last stored neighbor. */
246 3659 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 13 → 5 taken 62523 times.
✓ Branch 13 → 14 taken 745 times.
 63268 while(second < minutiae->num){
255 /* Assign temporary minutia pointers. */
256 62523 minutia1 = minutiae->list[first];
257 62523 minutia2 = minutiae->list[second];
258
259 /* Compute squared distance between minutiae along x-axis. */
260 62523 xdist = minutia2->x - minutia1->x;
261 62523 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 5 → 6 taken 44721 times.
✓ Branch 5 → 7 taken 17802 times.
 62523 if((nnbrs < max_nbrs) ||
266
2/2
✓ Branch 6 → 7 taken 41807 times.
✓ Branch 6 → 14 taken 2914 times.
 44721 (xdist2 < nbr_sqr_dists[last_nbr])){
267 /* Append or insert the new neighbor into the neighbor lists. */
268
1/2
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 12 taken 59609 times.
 59609 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 59609 second++;
284 }
285
286 /* Deallocate working memory. */
287 3659 g_free(nbr_sqr_dists);
288
289 /* If no neighbors found ... */
290
1/2
✗ Branch 15 → 16 not taken.
✓ Branch 15 → 18 taken 3659 times.
 3659 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 3659 *onbr_list = nbr_list;
298 3659 *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 59609 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 59609 double dist2;
336 59609 MINUTIA *minutia1, *minutia2;
337 59609 int pos, last_nbr;
338
339 /* Compute position of maximum last neighbor stored. */
340 59609 last_nbr = max_nbrs - 1;
341
342 /* Assigne temporary minutia pointers. */
343 59609 minutia1 = minutiae->list[first];
344 59609 minutia2 = minutiae->list[second];
345
346 /* Compute squared euclidean distance between minutia pair. */
347 119218 dist2 = squared_distance(minutia1->x, minutia1->y,
348 59609 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 3 → 4 taken 41807 times.
✓ Branch 3 → 5 taken 17802 times.
 59609 if((*nnbrs < max_nbrs) ||
354
2/2
✓ Branch 4 → 5 taken 17641 times.
✓ Branch 4 → 12 taken 24166 times.
 41807 (dist2 < nbr_sqr_dists[last_nbr])){
355
356 /* Find insertion point in neighbor lists. */
357 35443 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 6 → 7 not taken.
✓ Branch 6 → 9 taken 35443 times.
 35443 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 10 → 11 taken 35443 times.
✗ Branch 10 → 12 not taken.
 35443 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 35443 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 35443 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 35443 int i;
411
412
1/2
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 35443 times.
 35443 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 4 → 5 taken 35443 times.
✗ Branch 4 → 6 not taken.
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 8 taken 35443 times.
 35443 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 8 → 9 taken 17802 times.
✓ Branch 8 → 10 taken 17641 times.
 35443 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 17802 i = *nnbrs-1;
429 17802 (*nnbrs)++;
430 }
431 /* Otherwise, the neighbors lists are full ... */
432
1/2
✓ Branch 10 → 11 taken 17641 times.
✗ Branch 10 → 12 not taken.
 17641 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 17641 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 16 → 14 taken 45635 times.
✓ Branch 16 → 17 taken 35443 times.
 81078 while(i >= pos){
446 /* Shift the current neighbor down the list 1 positon. */
447 45635 nbr_list[i+1] = nbr_list[i];
448 45635 nbr_sqr_dists[i+1] = nbr_sqr_dists[i];
449 45635 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 35443 nbr_list[pos] = nbr_index;
455 35443 nbr_sqr_dists[pos] = nbr_dist2;
456
457 /* Return normally. */
458 35443 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 3659 int sort_neighbors(int *nbr_list, const int nnbrs, const int first,
481 MINUTIAE *minutiae)
482 {
483 3659 double *join_thetas, theta;
484 3659 int i;
485 3659 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 3659 join_thetas = (double *)g_malloc(nnbrs * sizeof(double));
490
491
2/2
✓ Branch 6 → 4 taken 17802 times.
✓ Branch 6 → 7 taken 3659 times.
 25120 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 35604 theta = angle2line(minutiae->list[nbr_list[i]]->y,
497 17802 minutiae->list[nbr_list[i]]->x,
498 17802 minutiae->list[first]->y,
499 17802 minutiae->list[first]->x);
500
501 /* Make sure the angle is positive. */
502 17802 theta += pi2;
503 17802 theta = fmod(theta, pi2);
504 17802 join_thetas[i] = theta;
505 }
506
507 /* Sort the neighbor indicies into rank order. */
508 3659 bubble_sort_double_inc_2(join_thetas, nbr_list, nnbrs);
509
510 /* Deallocate the list of angles. */
511 3659 g_free(join_thetas);
512
513 /* Return normally. */
514 3659 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 17802 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 17802 MINUTIA *minutia1, *minutia2;
540 17802 int i, ret, found;
541 17802 int *xlist, *ylist, num;
542 17802 int ridge_count, ridge_start, ridge_end;
543 17802 int prevpix, curpix;
544
545 17802 minutia1 = minutiae->list[first];
546 17802 minutia2 = minutiae->list[second];
547
548 /* If the 2 mintuia have identical pixel coords ... */
549
2/2
✓ Branch 2 → 3 taken 335 times.
✓ Branch 2 → 4 taken 17467 times.
 17802 if((minutia1->x == minutia2->x) &&
550
1/2
✓ Branch 3 → 4 taken 335 times.
✗ Branch 3 → 48 not taken.
 335 (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 5 → 6 taken 17802 times.
✗ Branch 5 → 48 not taken.
 17802 if((ret = line_points(&xlist, &ylist, &num,
557 17802 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 6 → 7 not taken.
✓ Branch 6 → 10 taken 17802 times.
 17802 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 17802 prevpix = *(bdata+(ylist[0]*iw)+xlist[0]);
572 17802 i = 1;
573 17802 found = FALSE;
574
2/2
✓ Branch 13 → 11 taken 43523 times.
✓ Branch 13 → 14 taken 48 times.
 43571 while(i < num){
575 43523 curpix = *(bdata+(ylist[i]*iw)+xlist[i]);
576
2/2
✓ Branch 11 → 12 taken 25769 times.
✓ Branch 11 → 14 taken 17754 times.
 43523 if(curpix != prevpix){
577 found = TRUE;
578 break;
579 }
580 25769 i++;
581 }
582
583 /* If opposite pixel not found ... then no ridges to count */
584
2/2
✓ Branch 14 → 15 taken 48 times.
✓ Branch 14 → 18 taken 17754 times.
 17802 if(!found){
585 48 g_free(xlist);
586 48 g_free(ylist);
587 48 return(0);
588 }
589
590 /* Ready to count ridges, so initialize counter to 0. */
591 17754 ridge_count = 0;
592
593 17754 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 43 → 20 taken 74429 times.
✗ Branch 43 → 44 not taken.
 74429 while(i < num){
598 /* If 0-to-1 transition not found ... */
599
2/2
✓ Branch 21 → 22 taken 9658 times.
✓ Branch 21 → 26 taken 64771 times.
 74429 if(!find_transition(&i, 0, 1, xlist, ylist, num, bdata, iw, ih)){
600 /* Then we are done looking for ridges. */
601 9658 g_free(xlist);
602 9658 g_free(ylist);
603
604 9658 print2log("\n");
605
606 /* Return number of ridges counted to this point. */
607 9658 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 64771 ridge_start = i;
612
613 64771 print2log(": RS %d,%d ", xlist[i], ylist[i]);
614
615 /* If 1-to-0 transition not found ... */
616
2/2
✓ Branch 28 → 29 taken 8096 times.
✓ Branch 28 → 33 taken 56675 times.
 64771 if(!find_transition(&i, 1, 0, xlist, ylist, num, bdata, iw, ih)){
617 /* Then we are done looking for ridges. */
618 8096 g_free(xlist);
619 8096 g_free(ylist);
620
621 8096 print2log("\n");
622
623 /* Return number of ridges counted to this point. */
624 8096 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 56675 ridge_end = i;
629
630 56675 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 56675 ret = validate_ridge_crossing(ridge_start, ridge_end,
640 xlist, ylist, num, bdata, iw, ih,
641 lfsparms->max_ridge_steps);
642
643 /* If system error ... */
644
1/2
✗ Branch 35 → 36 not taken.
✓ Branch 35 → 39 taken 56675 times.
 56675 if(ret < 0){
645 ✗ g_free(xlist);
646 ✗ g_free(ylist);
647 /* Return the error code. */
648 ✗ return(ret);
649 }
650
651 56675 print2log("; V%d ", ret);
652
653 /* If validation result is TRUE ... */
654
2/2
✓ Branch 40 → 41 taken 48986 times.
✓ Branch 40 → 42 taken 7689 times.
 56675 if(ret){
655 /* Then assume we have found a valid ridge crossing and bump */
656 /* the ridge counter. */
657 48986 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 139200 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 139200 int i, j;
702
703 /* Set previous index to starting position. */
704 139200 i = *iptr;
705 /* Bump previous index by 1 to get next index. */
706 139200 j = i+1;
707
708 /* While not one point from the end of the trajectory .. */
709
2/2
✓ Branch 7 → 3 taken 572704 times.
✓ Branch 7 → 8 taken 17754 times.
 590458 while(i < num-1){
710 /* If we have found the desired transition ... */
711
2/2
✓ Branch 3 → 4 taken 523356 times.
✓ Branch 3 → 6 taken 49348 times.
 572704 if((*(bdata+(ylist[i]*iw)+xlist[i]) == pix1) &&
712
2/2
✓ Branch 4 → 5 taken 121446 times.
✓ Branch 4 → 6 taken 401910 times.
 523356 (*(bdata+(ylist[j]*iw)+xlist[j]) == pix2)){
713 /* Adjust the position pointer to the location of the */
714 /* second pixel in the transition. */
715 121446 *iptr = j;
716
717 /* Return TRUE. */
718 121446 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 451258 i++;
723 451258 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 17754 *iptr = num;
730 17754 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 56675 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 56675 int ret;
764 56675 int feat_x, feat_y, edge_x, edge_y;
765 56675 int *contour_x, *contour_y, *contour_ex, *contour_ey, ncontour;
766
767 /* Assign edge pixel pair for contour trace. */
768 56675 feat_x = xlist[ridge_end];
769 56675 feat_y = ylist[ridge_end];
770 56675 edge_x = xlist[ridge_end-1];
771 56675 edge_y = ylist[ridge_end-1];
772
773 /* Adjust pixel pair if they neighbor each other diagonally. */
774 56675 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 113350 ret = trace_contour(&contour_x, &contour_y,
786 &contour_ex, &contour_ey, &ncontour,
787 max_ridge_steps,
788 56675 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 4 → 5 taken 56675 times.
✗ Branch 4 → 14 not taken.
 56675 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 5 → 6 taken 56675 times.
✗ Branch 5 → 14 not taken.
 56675 if(ret != IGNORE)
800 56675 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 7 → 8 taken 52749 times.
✓ Branch 7 → 14 taken 3926 times.
 56675 if((ret != IGNORE) &&
807 (ret != LOOP_FOUND)){
808
809 /* Now conduct contour trace scanning for edge neighbors counter- */
810 /* clockwise. */
811 52749 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 9 → 10 taken 52749 times.
✗ Branch 9 → 14 not taken.
 52749 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 10 → 11 taken 52749 times.
✗ Branch 10 → 14 not taken.
 52749 if(ret != IGNORE)
826 52749 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 12 → 13 taken 48986 times.
✓ Branch 12 → 14 taken 3763 times.
 52749 if((ret != IGNORE) &&
830 (ret != LOOP_FOUND)){
831 /* If we get here, assume we have a ridge crossing. */
832 48986 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