ridges.c 33.4 KB
Newer Older
1
2
/*******************************************************************************

Bastien Nocera's avatar
Bastien Nocera committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
License:
This software and/or related materials was developed at the National Institute
of Standards and Technology (NIST) by employees of the Federal Government
in the course of their official duties. Pursuant to title 17 Section 105
of the United States Code, this software is not subject to copyright
protection and is in the public domain.

This software and/or related materials have been determined to be not subject
to the EAR (see Part 734.3 of the EAR for exact details) because it is
a publicly available technology and software, and is freely distributed
to any interested party with no licensing requirements.  Therefore, it is
permissible to distribute this software as a free download from the internet.

Disclaimer:
This software and/or related materials was developed to promote biometric
standards and biometric technology testing for the Federal Government
in accordance with the USA PATRIOT Act and the Enhanced Border Security
and Visa Entry Reform Act. Specific hardware and software products identified
in this software were used in order to perform the software development.
In no case does such identification imply recommendation or endorsement
by the National Institute of Standards and Technology, nor does it imply that
the products and equipment identified are necessarily the best available
for the purpose.

This software and/or related materials are provided "AS-IS" without warranty
of any kind including NO WARRANTY OF PERFORMANCE, MERCHANTABILITY,
NO WARRANTY OF NON-INFRINGEMENT OF ANY 3RD PARTY INTELLECTUAL PROPERTY
or FITNESS FOR A PARTICULAR PURPOSE or for any purpose whatsoever, for the
licensed product, however used. In no event shall NIST be liable for any
damages and/or costs, including but not limited to incidental or consequential
damages of any kind, including economic damage or injury to property and lost
profits, regardless of whether NIST shall be advised, have reason to know,
or in fact shall know of the possibility.

By using this software, you agree to bear all risk relating to quality,
use and performance of the software and/or related materials.  You agree
to hold the Government harmless from any claim arising from your use
of the software.
41
42
43

*******************************************************************************/

Bastien Nocera's avatar
Bastien Nocera committed
44

45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/***********************************************************************
      LIBRARY: LFS - NIST Latent Fingerprint System

      FILE:    RIDGES.C
      AUTHOR:  Michael D. Garris
      DATE:    08/09/1999
      UPDATED: 03/16/2005 by MDG

      Contains routines responsible for locating nearest minutia
      neighbors and counting intervening ridges as part of the
      NIST Latent Fingerprint System (LFS).

***********************************************************************
               ROUTINES:
                        count_minutiae_ridges()
                        count_minutia_ridges()
                        find_neighbors()
                        update_nbr_dists()
                        insert_neighbor()
                        sort_neighbors()
                        ridge_count()
                        find_transition()
                        validate_ridge_crossing()
***********************************************************************/

#include <stdio.h>
#include <lfs.h>
#include <log.h>

/*************************************************************************
**************************************************************************
Bastien Nocera's avatar
Bastien Nocera committed
76
77
78
79
#cat: count_minutiae_ridges - Takes a list of minutiae, and for each one,
#cat:                determines its closest neighbors and counts the number
#cat:                of interveining ridges between the minutia point and
#cat:                each of its neighbors.
80
81

   Input:
Bastien Nocera's avatar
Bastien Nocera committed
82
83
84
85
86
      minutiae  - list of minutiae
      bdata     - binary image data (0==while & 1==black)
      iw        - width (in pixels) of image
      ih        - height (in pixels) of image
      lfsparms  - parameters and thresholds for controlling LFS
87
   Output:
Bastien Nocera's avatar
Bastien Nocera committed
88
      minutiae  - list of minutiae augmented with neighbors and ridge counts
89
   Return Code:
Bastien Nocera's avatar
Bastien Nocera committed
90
91
      Zero     - successful completion
      Negative - system error
92
**************************************************************************/
Bastien Nocera's avatar
Bastien Nocera committed
93
94
95
int count_minutiae_ridges(MINUTIAE *minutiae,
                      unsigned char *bdata, const int iw, const int ih,
                      const LFSPARMS *lfsparms)
96
{
Bastien Nocera's avatar
Bastien Nocera committed
97
   int ret;
98
99
   int i;

Bastien Nocera's avatar
Bastien Nocera committed
100
   print2log("\nFINDING NBRS AND COUNTING RIDGES:\n");
101

Bastien Nocera's avatar
Bastien Nocera committed
102
103
104
   /* Sort minutia points on x then y (column-oriented). */
   if((ret = sort_minutiae_x_y(minutiae, iw, ih))){
      return(ret);
105
106
   }

Bastien Nocera's avatar
Bastien Nocera committed
107
108
109
   /* Remove any duplicate minutia points from the list. */
   if((ret = rm_dup_minutiae(minutiae))){
      return(ret);
110
111
   }

Bastien Nocera's avatar
Bastien Nocera committed
112
113
114
115
116
117
118
119
120
   /* Foreach remaining sorted minutia in list ... */
   for(i = 0; i < minutiae->num-1; i++){
      /* Located neighbors and count number of ridges in between. */
      /* NOTE: neighbor and ridge count results are stored in     */
      /*       minutiae->list[i].                                 */
      if((ret = count_minutia_ridges(i, minutiae, bdata, iw, ih, lfsparms))){
         return(ret);
      }
   }
Daniel Drake's avatar
Daniel Drake committed
121

122
123
124
125
126
127
   /* Return normally. */
   return(0);
}

/*************************************************************************
**************************************************************************
Bastien Nocera's avatar
Bastien Nocera committed
128
129
130
#cat: count_minutia_ridges - Takes a minutia, and determines its closest
#cat:                neighbors and counts the number of interveining ridges
#cat:                between the minutia point and each of its neighbors.
131
132

   Input:
Bastien Nocera's avatar
Bastien Nocera committed
133
134
135
136
137
      minutia   - input minutia
      bdata     - binary image data (0==while & 1==black)
      iw        - width (in pixels) of image
      ih        - height (in pixels) of image
      lfsparms  - parameters and thresholds for controlling LFS
138
   Output:
Bastien Nocera's avatar
Bastien Nocera committed
139
      minutiae  - minutia augmented with neighbors and ridge counts
140
   Return Code:
Bastien Nocera's avatar
Bastien Nocera committed
141
142
      Zero     - successful completion
      Negative - system error
143
**************************************************************************/
Bastien Nocera's avatar
Bastien Nocera committed
144
145
146
int count_minutia_ridges(const int first, MINUTIAE *minutiae,
                      unsigned char *bdata, const int iw, const int ih,
                      const LFSPARMS *lfsparms)
147
{
Bastien Nocera's avatar
Bastien Nocera committed
148
   int i, ret, *nbr_list, *nbr_nridges, nnbrs;
149

Bastien Nocera's avatar
Bastien Nocera committed
150
   /* Find up to the maximum number of qualifying neighbors. */
151
   nbr_list = NULL;
Bastien Nocera's avatar
Bastien Nocera committed
152
153
   if((ret = find_neighbors(&nbr_list, &nnbrs, lfsparms->max_nbrs,
                           first, minutiae))){
154
155
      if (nbr_list != NULL)
         free(nbr_list);
Bastien Nocera's avatar
Bastien Nocera committed
156
157
      return(ret);
   }
158

Bastien Nocera's avatar
Bastien Nocera committed
159
160
   print2log("NBRS FOUND: %d,%d = %d\n", minutiae->list[first]->x,
              minutiae->list[first]->y, nnbrs);
161

Bastien Nocera's avatar
Bastien Nocera committed
162
163
164
165
166
   /* If no neighors found ... */
   if(nnbrs == 0){
      /* Then no list returned and no ridges to count. */
      return(0);
   }
167

Bastien Nocera's avatar
Bastien Nocera committed
168
169
170
171
172
   /* Sort neighbors on delta dirs. */
   if((ret = sort_neighbors(nbr_list, nnbrs, first, minutiae))){
      free(nbr_list);
      return(ret);
   }
173

Bastien Nocera's avatar
Bastien Nocera committed
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
   /* Count ridges between first and neighbors. */
   /* List of ridge counts, one for each neighbor stored. */
   nbr_nridges = (int *)malloc(nnbrs * sizeof(int));
   if(nbr_nridges == (int *)NULL){
      free(nbr_list);
      fprintf(stderr, "ERROR : count_minutia_ridges : malloc : nbr_nridges\n");
      return(-450);
   }

   /* Foreach neighbor found and sorted in list ... */
   for(i = 0; i < nnbrs; i++){
      /* Count the ridges between the primary minutia and the neighbor. */
      ret = ridge_count(first, nbr_list[i], minutiae, bdata, iw, ih, lfsparms);
      /* If system error ... */
      if(ret < 0){
         /* Deallocate working memories. */
         free(nbr_list);
         free(nbr_nridges);
         /* Return error code. */
         return(ret);
194
195
      }

Bastien Nocera's avatar
Bastien Nocera committed
196
197
      /* Otherwise, ridge count successful, so store ridge count to list. */
      nbr_nridges[i] = ret;
198
199
   }

Bastien Nocera's avatar
Bastien Nocera committed
200
201
202
203
204
205
206
   /* Assign neighbor indices and ridge counts to primary minutia. */
   minutiae->list[first]->nbrs = nbr_list;
   minutiae->list[first]->ridge_counts = nbr_nridges;
   minutiae->list[first]->num_nbrs = nnbrs;

   /* Return normally. */
   return(0);
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
}

/*************************************************************************
**************************************************************************
#cat: find_neighbors - Takes a primary minutia and a list of all minutiae
#cat:               and locates a specified maximum number of closest neighbors
#cat:               to the primary point.  Neighbors are searched, starting
#cat:               in the same pixel column, below, the primary point and then
#cat:               along consecutive and complete pixel columns in the image
#cat:               to the right of the primary point.

   Input:
      max_nbrs - maximum number of closest neighbors to be returned
      first    - index of the primary minutia point
      minutiae - list of minutiae
   Output:
      onbr_list - points to list of detected closest neighbors
      onnbrs    - points to number of neighbors returned
   Return Code:
      Zero      - successful completion
      Negative  - system error
**************************************************************************/
Bastien Nocera's avatar
Bastien Nocera committed
229
int find_neighbors(int **onbr_list, int *onnbrs, const int max_nbrs,
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
                   const int first, MINUTIAE *minutiae)
{
   int ret, second, last_nbr;
   MINUTIA *minutia1, *minutia2;
   int *nbr_list, nnbrs;
   double *nbr_sqr_dists, xdist, xdist2;

   /* Allocate list of neighbor minutiae indices. */
   nbr_list = (int *)malloc(max_nbrs * sizeof(int));
   if(nbr_list == (int *)NULL){
      fprintf(stderr, "ERROR : find_neighbors : malloc : nbr_list\n");
      return(-460);
   }

   /* Allocate list of squared euclidean distances between neighbors */
   /* and current primary minutia point.                             */
   nbr_sqr_dists = (double *)malloc(max_nbrs * sizeof(double));
   if(nbr_sqr_dists == (double *)NULL){
      free(nbr_list);
      fprintf(stderr,
              "ERROR : find_neighbors : malloc : nbr_sqr_dists\n");
      return(-461);
   }

   /* Initialize number of stored neighbors to 0. */
   nnbrs = 0;
   /* Assign secondary to one passed current primary minutia. */
   second = first + 1;
   /* Compute location of maximum last stored neighbor. */
   last_nbr = max_nbrs - 1;

   /* While minutia (in sorted order) still remian for processing ... */
   /* NOTE: The minutia in the input list have been sorted on X and   */
   /* then on Y.  So, the neighbors are selected according to those   */
   /* that lie below the primary minutia in the same pixel column and */
   /* then subsequently those that lie in complete pixel columns to   */
   /* the right of the primary minutia.                               */
   while(second < minutiae->num){
      /* Assign temporary minutia pointers. */
      minutia1 = minutiae->list[first];
      minutia2 = minutiae->list[second];

      /* Compute squared distance between minutiae along x-axis. */
      xdist = minutia2->x - minutia1->x;
      xdist2 = xdist * xdist;

      /* If the neighbor lists are not full OR the x-distance to current */
      /* secondary is smaller than maximum neighbor distance stored ...  */
      if((nnbrs < max_nbrs) ||
         (xdist2 < nbr_sqr_dists[last_nbr])){
         /* Append or insert the new neighbor into the neighbor lists. */
         if((ret = update_nbr_dists(nbr_list, nbr_sqr_dists, &nnbrs, max_nbrs,
                          first, second, minutiae))){
            free(nbr_sqr_dists);
            return(ret);
         }
      }
      /* Otherwise, if the neighbor lists is full AND the x-distance   */
      /* to current secondary is larger than maximum neighbor distance */
      /* stored ...                                                    */
      else
         /* So, stop searching for more neighbors. */
         break;

       /* Bump to next secondary minutia. */
       second++;
   }

   /* Deallocate working memory. */
   free(nbr_sqr_dists);

   /* If no neighbors found ... */
   if(nnbrs == 0){
      /* Deallocate the neighbor list. */
      free(nbr_list);
      *onnbrs = 0;
   }
   /* Otherwise, assign neighbors to output pointer. */
   else{
      *onbr_list = nbr_list;
      *onnbrs = nnbrs;
   }

   /* Return normally. */
   return(0);
}

/*************************************************************************
**************************************************************************
Bastien Nocera's avatar
Bastien Nocera committed
319
320
321
322
323
324
#cat: update_nbr_dists - Takes the current list of neighbors along with a
#cat:               primary minutia and a potential new neighbor, and
#cat:               determines if the new neighbor is sufficiently close
#cat:               to be added to the list of nearest neighbors.  If added,
#cat:               it is placed in the list in its proper order based on
#cat:               squared distance to the primary point.
325
326

   Input:
Bastien Nocera's avatar
Bastien Nocera committed
327
328
329
330
331
332
333
      nbr_list - current list of nearest neighbor minutia indices
      nbr_sqr_dists - corresponding squared euclidean distance of each
                 neighbor to the primary minutia point
      nnbrs    - number of neighbors currently in the list
      max_nbrs - maximum number of closest neighbors to be returned
      first    - index of the primary minutia point
      second   - index of the secondary (new neighbor) point
334
335
      minutiae - list of minutiae
   Output:
Bastien Nocera's avatar
Bastien Nocera committed
336
337
338
      nbr_list - updated list of nearest neighbor indices
      nbr_sqr_dists - updated list of nearest neighbor distances
      nnbrs    - number of neighbors in the update lists
339
   Return Code:
Bastien Nocera's avatar
Bastien Nocera committed
340
341
      Zero      - successful completion
      Negative  - system error
342
**************************************************************************/
Bastien Nocera's avatar
Bastien Nocera committed
343
344
345
int update_nbr_dists(int *nbr_list, double *nbr_sqr_dists,
                      int *nnbrs, const int max_nbrs,
                      const int first, const int second, MINUTIAE *minutiae)
346
{
Bastien Nocera's avatar
Bastien Nocera committed
347
348
349
   double dist2;
   MINUTIA *minutia1, *minutia2;
   int pos, last_nbr;
350

Bastien Nocera's avatar
Bastien Nocera committed
351
352
   /* Compute position of maximum last neighbor stored. */
   last_nbr = max_nbrs - 1;
353

Bastien Nocera's avatar
Bastien Nocera committed
354
355
356
   /* Assigne temporary minutia pointers. */
   minutia1 = minutiae->list[first];
   minutia2 = minutiae->list[second];
357

Bastien Nocera's avatar
Bastien Nocera committed
358
359
360
   /* Compute squared euclidean distance between minutia pair. */
   dist2 = squared_distance(minutia1->x, minutia1->y,
                            minutia2->x, minutia2->y);
361

Bastien Nocera's avatar
Bastien Nocera committed
362
363
364
365
366
   /* If maximum number of neighbors not yet stored in lists OR */
   /* if the squared distance to current secondary is less      */
   /* than the largest stored neighbor distance ...             */
   if((*nnbrs < max_nbrs) ||
      (dist2 < nbr_sqr_dists[last_nbr])){
367

Bastien Nocera's avatar
Bastien Nocera committed
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
      /* Find insertion point in neighbor lists. */
      pos = find_incr_position_dbl(dist2, nbr_sqr_dists, *nnbrs);
      /* If the position returned is >= maximum list length (this should */
      /* never happen, but just in case) ...                             */
      if(pos >= max_nbrs){
         fprintf(stderr,
         "ERROR : update_nbr_dists : illegal position for new neighbor\n");
         return(-470);
      }
      /* Insert the new neighbor into the neighbor lists at the */
      /* specified location.                                    */
      if(insert_neighbor(pos, second, dist2,
                         nbr_list, nbr_sqr_dists, nnbrs, max_nbrs))
         return(-471);

      /* Otherwise, neighbor inserted successfully, so return normally. */
      return(0);
   }
   /* Otherwise, the new neighbor is not sufficiently close to be       */
   /* added or inserted into the neighbor lists, so ignore the neighbor */
   /* and return normally.                                              */
   else
      return(0);
Daniel Drake's avatar
Daniel Drake committed
391
392
393
394
395

}

/*************************************************************************
**************************************************************************
Bastien Nocera's avatar
Bastien Nocera committed
396
397
398
399
#cat: insert_neighbor - Takes a minutia index and its squared distance to a
#cat:               primary minutia point, and inserts them in the specified
#cat:               position of their respective lists, shifting previously
#cat:               stored values down and off the lists as necessary.
Daniel Drake's avatar
Daniel Drake committed
400
401

   Input:
Bastien Nocera's avatar
Bastien Nocera committed
402
403
404
405
406
407
408
409
      pos       - postions where values are to be inserted in lists
      nbr_index - index of minutia being inserted
      nbr_dist2 - squared distance of minutia to its primary point
      nbr_list  - current list of nearest neighbor minutia indices
      nbr_sqr_dists - corresponding squared euclidean distance of each
                  neighbor to the primary minutia point
      nnbrs     - number of neighbors currently in the list
      max_nbrs  - maximum number of closest neighbors to be returned
Daniel Drake's avatar
Daniel Drake committed
410
   Output:
Bastien Nocera's avatar
Bastien Nocera committed
411
412
413
      nbr_list - updated list of nearest neighbor indices
      nbr_sqr_dists - updated list of nearest neighbor distances
      nnbrs    - number of neighbors in the update lists
Daniel Drake's avatar
Daniel Drake committed
414
   Return Code:
Bastien Nocera's avatar
Bastien Nocera committed
415
416
      Zero      - successful completion
      Negative  - system error
Daniel Drake's avatar
Daniel Drake committed
417
**************************************************************************/
Bastien Nocera's avatar
Bastien Nocera committed
418
419
420
int insert_neighbor(const int pos, const int nbr_index, const double nbr_dist2,
                    int *nbr_list, double *nbr_sqr_dists,
                    int *nnbrs, const int max_nbrs)
Daniel Drake's avatar
Daniel Drake committed
421
{
Bastien Nocera's avatar
Bastien Nocera committed
422
   int i;
Daniel Drake's avatar
Daniel Drake committed
423

Bastien Nocera's avatar
Bastien Nocera committed
424
425
426
427
428
429
430
431
432
   /* If the desired insertion position is beyond one passed the last     */
   /* neighbor in the lists OR greater than equal to the maximum ...      */
   /* NOTE: pos is zero-oriented while nnbrs and max_nbrs are 1-oriented. */
   if((pos > *nnbrs) ||
      (pos >= max_nbrs)){
      fprintf(stderr,
              "ERROR : insert_neighbor : insertion point exceeds lists\n");
      return(-480);
   }
Daniel Drake's avatar
Daniel Drake committed
433

Bastien Nocera's avatar
Bastien Nocera committed
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
   /* If the neighbor lists are NOT full ... */
   if(*nnbrs < max_nbrs){
      /* Then we have room to shift everything down to make room for new */
      /* neighbor and increase the number of neighbors stored by 1.      */
      i = *nnbrs-1;
      (*nnbrs)++;
   }
   /* Otherwise, the neighbors lists are full ... */
   else if(*nnbrs == max_nbrs)
      /* So, we must bump the last neighbor in the lists off to make */
      /* room for the new neighbor (ignore last neighbor in lists).  */
      i = *nnbrs-2;
   /* Otherwise, there is a list overflow error condition */
   /* (shouldn't ever happen, but just in case) ...       */
   else{
      fprintf(stderr,
              "ERROR : insert_neighbor : overflow in neighbor lists\n");
      return(-481);
   }
Daniel Drake's avatar
Daniel Drake committed
453

Bastien Nocera's avatar
Bastien Nocera committed
454
455
456
457
458
459
   /* While we havn't reached the desired insertion point ... */
   while(i >= pos){
      /* Shift the current neighbor down the list 1 positon. */
      nbr_list[i+1] = nbr_list[i];
      nbr_sqr_dists[i+1] = nbr_sqr_dists[i];
      i--;
Daniel Drake's avatar
Daniel Drake committed
460
461
   }

Bastien Nocera's avatar
Bastien Nocera committed
462
463
464
465
466
467
468
   /* We are now ready to put our new neighbor in the position where */
   /* we shifted everything down from to make room.                  */
   nbr_list[pos] = nbr_index;
   nbr_sqr_dists[pos] = nbr_dist2;

   /* Return normally. */
   return(0);
Daniel Drake's avatar
Daniel Drake committed
469
470
471
472
}

/*************************************************************************
**************************************************************************
Bastien Nocera's avatar
Bastien Nocera committed
473
474
475
476
477
#cat: sort_neighbors - Takes a list of primary minutia and its neighboring
#cat:               minutia indices and sorts the neighbors based on their
#cat:               position relative to the primary minutia point.  Neighbors
#cat:               are sorted starting vertical to the primary point and
#cat:               proceeding clockwise.
Daniel Drake's avatar
Daniel Drake committed
478
479

   Input:
Bastien Nocera's avatar
Bastien Nocera committed
480
481
482
483
484
485
      nbr_list - list of neighboring minutia indices
      nnbrs    - number of neighbors in the list
      first    - the index of the primary minutia point
      minutiae - list of minutiae
   Output:
      nbr_list - neighboring minutia indices in sorted order
Daniel Drake's avatar
Daniel Drake committed
486
   Return Code:
Bastien Nocera's avatar
Bastien Nocera committed
487
488
      Zero     - successful completion
      Negative - system error
Daniel Drake's avatar
Daniel Drake committed
489
**************************************************************************/
Bastien Nocera's avatar
Bastien Nocera committed
490
491
int sort_neighbors(int *nbr_list, const int nnbrs, const int first,
                   MINUTIAE *minutiae)
Daniel Drake's avatar
Daniel Drake committed
492
{
Bastien Nocera's avatar
Bastien Nocera committed
493
494
495
   double *join_thetas, theta;
   int i;
   static double pi2 = M_PI*2.0;
Daniel Drake's avatar
Daniel Drake committed
496

Bastien Nocera's avatar
Bastien Nocera committed
497
498
499
500
501
502
503
   /* List of angles of lines joining the current primary to each */
   /* of the secondary neighbors.                                 */
   join_thetas = (double *)malloc(nnbrs * sizeof(double));
   if(join_thetas == (double *)NULL){
      fprintf(stderr, "ERROR : sort_neighbors : malloc : join_thetas\n");
      return(-490);
   }
Daniel Drake's avatar
Daniel Drake committed
504

Bastien Nocera's avatar
Bastien Nocera committed
505
506
507
508
509
510
511
512
513
   for(i = 0; i < nnbrs; i++){
      /* Compute angle to line connecting the 2 points.             */
      /* Coordinates are swapped and order of points reversed to    */
      /* account for 0 direction is vertical and positive direction */
      /* is clockwise.                                              */
      theta = angle2line(minutiae->list[nbr_list[i]]->y,
                         minutiae->list[nbr_list[i]]->x,
                         minutiae->list[first]->y,
                         minutiae->list[first]->x);
514

Bastien Nocera's avatar
Bastien Nocera committed
515
516
517
518
      /* Make sure the angle is positive. */
      theta += pi2;
      theta = fmod(theta, pi2);
      join_thetas[i] = theta;
Daniel Drake's avatar
Daniel Drake committed
519
   }
Bastien Nocera's avatar
Bastien Nocera committed
520
521
522
523
524
525
526
527
528

   /* Sort the neighbor indicies into rank order. */
   bubble_sort_double_inc_2(join_thetas, nbr_list, nnbrs);

   /* Deallocate the list of angles. */
   free(join_thetas);

   /* Return normally. */
   return(0);
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
}

/*************************************************************************
**************************************************************************
#cat: ridge_count - Takes a pair of minutiae, and counts the number of
#cat:               ridges crossed along the linear trajectory connecting
#cat:               the 2 points in the image.

   Input:
      first     - index of primary minutia
      second    - index of secondary (neighbor) minutia
      minutiae  - list of minutiae
      bdata     - binary image data (0==while & 1==black)
      iw        - width (in pixels) of image
      ih        - height (in pixels) of image
      lfsparms  - parameters and thresholds for controlling LFS
   Return Code:
      Zero or Positive - number of ridges counted
      Negative         - system error
**************************************************************************/
Bastien Nocera's avatar
Bastien Nocera committed
549
int ridge_count(const int first, const int second, MINUTIAE *minutiae,
550
551
552
553
554
555
                unsigned char *bdata, const int iw, const int ih,
                const LFSPARMS *lfsparms)
{
   MINUTIA *minutia1, *minutia2;
   int i, ret, found;
   int *xlist, *ylist, num;
Bastien Nocera's avatar
Bastien Nocera committed
556
   int ridge_count, ridge_start, ridge_end;
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
   int prevpix, curpix;

   minutia1 = minutiae->list[first];
   minutia2 = minutiae->list[second];

   /* If the 2 mintuia have identical pixel coords ... */
   if((minutia1->x == minutia2->x) &&
      (minutia1->y == minutia2->y))
      /* Then zero ridges between points. */
     return(0);

   /* Compute linear trajectory of contiguous pixels between first */
   /* and second minutia points.                                   */
   if((ret = line_points(&xlist, &ylist, &num,
                        minutia1->x, minutia1->y, minutia2->x, minutia2->y))){
      return(ret);
   }

   /* It there are no points on the line trajectory, then no ridges */
   /* to count (this should not happen, but just in case) ...       */
   if(num == 0){
      free(xlist);
      free(ylist);
      return(0);
   }

   /* Find first pixel opposite type along linear trajectory from */
   /* first minutia.                                              */
   prevpix = *(bdata+(ylist[0]*iw)+xlist[0]);
   i = 1;
   found = FALSE;
   while(i < num){
      curpix = *(bdata+(ylist[i]*iw)+xlist[i]);
      if(curpix != prevpix){
         found = TRUE;
         break;
      }
      i++;
   }

   /* If opposite pixel not found ... then no ridges to count */
   if(!found){
      free(xlist);
      free(ylist);
      return(0);
   }

   /* Ready to count ridges, so initialize counter to 0. */
Bastien Nocera's avatar
Bastien Nocera committed
605
   ridge_count = 0;
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620

   print2log("RIDGE COUNT: %d,%d to %d,%d ", minutia1->x, minutia1->y,
                                               minutia2->x, minutia2->y);

   /* While not at the end of the trajectory ... */
   while(i < num){
      /* If 0-to-1 transition not found ... */
      if(!find_transition(&i, 0, 1, xlist, ylist, num, bdata, iw, ih)){
         /* Then we are done looking for ridges. */
         free(xlist);
         free(ylist);

         print2log("\n");

         /* Return number of ridges counted to this point. */
Bastien Nocera's avatar
Bastien Nocera committed
621
         return(ridge_count);
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
      }
      /* Otherwise, we found a new ridge start transition, so store */
      /* its location (the location of the 1 in 0-to-1 transition). */
      ridge_start = i;

      print2log(": RS %d,%d ", xlist[i], ylist[i]);

      /* If 1-to-0 transition not found ... */
      if(!find_transition(&i, 1, 0, xlist, ylist, num, bdata, iw, ih)){
         /* Then we are done looking for ridges. */
         free(xlist);
         free(ylist);

         print2log("\n");

         /* Return number of ridges counted to this point. */
Bastien Nocera's avatar
Bastien Nocera committed
638
         return(ridge_count);
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
      }
      /* Otherwise, we found a new ridge end transition, so store   */
      /* its location (the location of the 0 in 1-to-0 transition). */
      ridge_end = i;

      print2log("; RE %d,%d ", xlist[i], ylist[i]);

      /* Conduct the validation, tracing the contour of the ridge  */
      /* from the ridge ending point a specified number of steps   */
      /* scanning for neighbors clockwise and counter-clockwise.   */
      /* If the ridge starting point is encounted during the trace */
      /* then we can assume we do not have a valid ridge crossing  */
      /* and instead we are walking on and off the edge of the     */
      /* side of a ridge.                                          */
      ret = validate_ridge_crossing(ridge_start, ridge_end,
                                    xlist, ylist, num, bdata, iw, ih,
                                    lfsparms->max_ridge_steps);

      /* If system error ... */
      if(ret < 0){
         free(xlist);
         free(ylist);
         /* Return the error code. */
         return(ret);
      }

      print2log("; V%d ", ret);

      /* If validation result is TRUE ... */
      if(ret){
         /* Then assume we have found a valid ridge crossing and bump */
         /* the ridge counter.                                        */
Bastien Nocera's avatar
Bastien Nocera committed
671
         ridge_count++;
672
673
674
675
676
677
678
679
680
681
682
683
684
      }

      /* Otherwise, ignore the current ridge start and end transitions */
      /* and go back and search for new ridge start.                   */
   }

   /* Deallocate working memories. */
   free(xlist);
   free(ylist);

   print2log("\n");

   /* Return the number of ridges counted. */
Bastien Nocera's avatar
Bastien Nocera committed
685
   return(ridge_count);
686
687
688
689
}

/*************************************************************************
**************************************************************************
Bastien Nocera's avatar
Bastien Nocera committed
690
691
692
693
#cat: find_transition - Takes a pixel trajectory and a starting index, and
#cat:               searches forward along the trajectory until the specified
#cat:               adjacent pixel pair is found, returning the index where
#cat:               the pair was found (the index of the second pixel).
694
695

   Input:
Bastien Nocera's avatar
Bastien Nocera committed
696
697
698
699
700
701
702
703
704
      iptr  - pointer to starting pixel index into trajectory
      pix1  - first pixel value in transition pair
      pix2  - second pixel value in transition pair
      xlist - x-pixel coords of line trajectory
      ylist - y-pixel coords of line trajectory
      num   - number of coords in line trajectory
      bdata - binary image data (0==while & 1==black)
      iw    - width (in pixels) of image
      ih    - height (in pixels) of image
705
   Output:
Bastien Nocera's avatar
Bastien Nocera committed
706
      iptr  - points to location where 2nd pixel in pair is found
707
   Return Code:
Bastien Nocera's avatar
Bastien Nocera committed
708
709
      TRUE  - pixel pair transition found
      FALSE - pixel pair transition not found
710
**************************************************************************/
Bastien Nocera's avatar
Bastien Nocera committed
711
712
713
int find_transition(int *iptr, const int pix1, const int pix2,
                    const int *xlist, const int *ylist, const int num,
                    unsigned char *bdata, const int iw, const int ih)
714
{
Bastien Nocera's avatar
Bastien Nocera committed
715
   int i, j;
Daniel Drake's avatar
Daniel Drake committed
716

Bastien Nocera's avatar
Bastien Nocera committed
717
718
719
720
   /* Set previous index to starting position. */
   i = *iptr;
   /* Bump previous index by 1 to get next index. */
   j = i+1;
Daniel Drake's avatar
Daniel Drake committed
721

Bastien Nocera's avatar
Bastien Nocera committed
722
723
724
725
726
727
728
729
   /* While not one point from the end of the trajectory .. */
   while(i < num-1){
      /* If we have found the desired transition ... */
      if((*(bdata+(ylist[i]*iw)+xlist[i]) == pix1) &&
         (*(bdata+(ylist[j]*iw)+xlist[j]) == pix2)){
         /* Adjust the position pointer to the location of the */
         /* second pixel in the transition.                    */
         *iptr = j;
Daniel Drake's avatar
Daniel Drake committed
730

Bastien Nocera's avatar
Bastien Nocera committed
731
732
         /* Return TRUE. */
         return(TRUE);
733
      }
Bastien Nocera's avatar
Bastien Nocera committed
734
735
736
737
      /* Otherwise, the desired transition was not found in current */
      /* pixel pair, so bump to the next pair along the trajector.  */
      i++;
      j++;
738
739
   }

Bastien Nocera's avatar
Bastien Nocera committed
740
741
742
743
744
   /* If we get here, then we exhausted the trajector without finding */
   /* the desired transition, so set the position pointer to the end  */
   /* of the trajector, and return FALSE.                             */
   *iptr = num;
   return(FALSE);
745
746
747
748
}

/*************************************************************************
**************************************************************************
Bastien Nocera's avatar
Bastien Nocera committed
749
750
751
752
753
754
#cat: validate_ridge_crossing - Takes a pair of points, a ridge start
#cat:               transition and a ridge end transition, and walks the
#cat:               ridge contour from thre ridge end points a specified
#cat:               number of steps, looking for the ridge start point.
#cat:               If found, then transitions determined not to be a valid
#cat:               ridge crossing.
755
756

   Input:
Bastien Nocera's avatar
Bastien Nocera committed
757
758
759
760
761
762
763
764
765
766
      ridge_start - index into line trajectory of ridge start transition
      ridge_end   - index into line trajectory of ridge end transition
      xlist       - x-pixel coords of line trajectory
      ylist       - y-pixel coords of line trajectory
      num         - number of coords in line trajectory
      bdata       - binary image data (0==while & 1==black)
      iw          - width (in pixels) of image
      ih          - height (in pixels) of image
      max_ridge_steps  - number of steps taken in search in both
                         scan directions
767
   Return Code:
Bastien Nocera's avatar
Bastien Nocera committed
768
769
770
      TRUE        - ridge crossing VALID
      FALSE       - ridge corssing INVALID
      Negative    - system error
771
**************************************************************************/
Bastien Nocera's avatar
Bastien Nocera committed
772
773
774
775
int validate_ridge_crossing(const int ridge_start, const int ridge_end,
                            const int *xlist, const int *ylist, const int num,
                            unsigned char *bdata, const int iw, const int ih,
                            const int max_ridge_steps)
776
777
{
   int ret;
Bastien Nocera's avatar
Bastien Nocera committed
778
779
   int feat_x, feat_y, edge_x, edge_y;
   int *contour_x, *contour_y, *contour_ex, *contour_ey, ncontour;
780

Bastien Nocera's avatar
Bastien Nocera committed
781
782
783
784
785
   /* Assign edge pixel pair for contour trace. */
   feat_x = xlist[ridge_end];
   feat_y = ylist[ridge_end];
   edge_x = xlist[ridge_end-1];
   edge_y = ylist[ridge_end-1];
786

Bastien Nocera's avatar
Bastien Nocera committed
787
788
789
   /* Adjust pixel pair if they neighbor each other diagonally. */
   fix_edge_pixel_pair(&feat_x, &feat_y, &edge_x, &edge_y,
                       bdata, iw, ih);
790

Bastien Nocera's avatar
Bastien Nocera committed
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
   /* Trace ridge contour, starting at the ridge end transition, and */
   /* taking a specified number of step scanning for edge neighbors  */
   /* clockwise.  As we trace the ridge, we want to detect if we     */
   /* encounter the ridge start transition.  NOTE: The ridge end     */
   /* position is on the white (of a black to white transition) and  */
   /* the ridge start is on the black (of a black to white trans),   */
   /* so the edge trace needs to look for the what pixel (not the    */
   /* black one) of the ridge start transition.                      */
   ret = trace_contour(&contour_x, &contour_y,
                       &contour_ex, &contour_ey, &ncontour,
                       max_ridge_steps,
                       xlist[ridge_start-1], ylist[ridge_start-1],
                       feat_x, feat_y, edge_x, edge_y,
                       SCAN_CLOCKWISE, bdata, iw, ih);
   /* If a system error occurred ... */
   if(ret < 0)
      /* Return error code. */
Daniel Drake's avatar
Daniel Drake committed
808
      return(ret);
809

Bastien Nocera's avatar
Bastien Nocera committed
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
   /* Otherwise, if the trace was not IGNORED, then a contour was */
   /* was generated and returned.  We aren't interested in the    */
   /* actual contour, so deallocate it.                           */
   if(ret != IGNORE)
      free_contour(contour_x, contour_y, contour_ex, contour_ey);

   /* If the trace was IGNORED, then we had some sort of initialization */
   /* problem, so treat this the same as if was actually located the    */
   /* ridge start point (in which case LOOP_FOUND is returned).         */
   /* So, If not IGNORED and ridge start not encounted in trace ...     */
   if((ret != IGNORE) &&
      (ret != LOOP_FOUND)){

      /* Now conduct contour trace scanning for edge neighbors counter- */
      /* clockwise.                                                     */
      ret = trace_contour(&contour_x, &contour_y,
                          &contour_ex, &contour_ey, &ncontour,
                          max_ridge_steps,
                          xlist[ridge_start-1], ylist[ridge_start-1],
                          feat_x, feat_y, edge_x, edge_y,
                          SCAN_COUNTER_CLOCKWISE, bdata, iw, ih);
      /* If a system error occurred ... */
      if(ret < 0)
         /* Return error code. */
834
         return(ret);
Bastien Nocera's avatar
Bastien Nocera committed
835
836
837
838
839
840
841
842
843
844
845
846

      /* Otherwise, if the trace was not IGNORED, then a contour was */
      /* was generated and returned.  We aren't interested in the    */
      /* actual contour, so deallocate it.                           */
      if(ret != IGNORE)
         free_contour(contour_x, contour_y, contour_ex, contour_ey);

      /* If trace not IGNORED and ridge start not encounted in 2nd trace ... */
      if((ret != IGNORE) &&
         (ret != LOOP_FOUND)){
         /* If we get here, assume we have a ridge crossing. */
         return(TRUE);
847
      }
Bastien Nocera's avatar
Bastien Nocera committed
848
      /* Otherwise, second trace returned IGNORE or ridge start found. */
849
   }
Bastien Nocera's avatar
Bastien Nocera committed
850
   /* Otherwise, first trace returned IGNORE or ridge start found. */
Daniel Drake's avatar
Daniel Drake committed
851

Bastien Nocera's avatar
Bastien Nocera committed
852
853
   /* If we get here, then we failed to validate a ridge crossing. */
   return(FALSE);
854
}