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
151
152
153
154
155
   /* Find up to the maximum number of qualifying neighbors. */
   if((ret = find_neighbors(&nbr_list, &nnbrs, lfsparms->max_nbrs,
                           first, minutiae))){
      free(nbr_list);
      return(ret);
   }
156

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

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

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

Bastien Nocera's avatar
Bastien Nocera committed
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
   /* 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);
192
193
      }

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

Bastien Nocera's avatar
Bastien Nocera committed
198
199
200
201
202
203
204
   /* 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);
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
}

/*************************************************************************
**************************************************************************
#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
227
int find_neighbors(int **onbr_list, int *onnbrs, const int max_nbrs,
228
229
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
                   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
317
318
319
320
321
322
#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.
323
324

   Input:
Bastien Nocera's avatar
Bastien Nocera committed
325
326
327
328
329
330
331
      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
332
333
      minutiae - list of minutiae
   Output:
Bastien Nocera's avatar
Bastien Nocera committed
334
335
336
      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
337
   Return Code:
Bastien Nocera's avatar
Bastien Nocera committed
338
339
      Zero      - successful completion
      Negative  - system error
340
**************************************************************************/
Bastien Nocera's avatar
Bastien Nocera committed
341
342
343
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)
344
{
Bastien Nocera's avatar
Bastien Nocera committed
345
346
347
   double dist2;
   MINUTIA *minutia1, *minutia2;
   int pos, last_nbr;
348

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

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

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

Bastien Nocera's avatar
Bastien Nocera committed
360
361
362
363
364
   /* 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])){
365

Bastien Nocera's avatar
Bastien Nocera committed
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
      /* 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
389
390
391
392
393

}

/*************************************************************************
**************************************************************************
Bastien Nocera's avatar
Bastien Nocera committed
394
395
396
397
#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
398
399

   Input:
Bastien Nocera's avatar
Bastien Nocera committed
400
401
402
403
404
405
406
407
      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
408
   Output:
Bastien Nocera's avatar
Bastien Nocera committed
409
410
411
      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
412
   Return Code:
Bastien Nocera's avatar
Bastien Nocera committed
413
414
      Zero      - successful completion
      Negative  - system error
Daniel Drake's avatar
Daniel Drake committed
415
**************************************************************************/
Bastien Nocera's avatar
Bastien Nocera committed
416
417
418
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
419
{
Bastien Nocera's avatar
Bastien Nocera committed
420
   int i;
Daniel Drake's avatar
Daniel Drake committed
421

Bastien Nocera's avatar
Bastien Nocera committed
422
423
424
425
426
427
428
429
430
   /* 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
431

Bastien Nocera's avatar
Bastien Nocera committed
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
   /* 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
451

Bastien Nocera's avatar
Bastien Nocera committed
452
453
454
455
456
457
   /* 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
458
459
   }

Bastien Nocera's avatar
Bastien Nocera committed
460
461
462
463
464
465
466
   /* 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
467
468
469
470
}

/*************************************************************************
**************************************************************************
Bastien Nocera's avatar
Bastien Nocera committed
471
472
473
474
475
#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
476
477

   Input:
Bastien Nocera's avatar
Bastien Nocera committed
478
479
480
481
482
483
      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
484
   Return Code:
Bastien Nocera's avatar
Bastien Nocera committed
485
486
      Zero     - successful completion
      Negative - system error
Daniel Drake's avatar
Daniel Drake committed
487
**************************************************************************/
Bastien Nocera's avatar
Bastien Nocera committed
488
489
int sort_neighbors(int *nbr_list, const int nnbrs, const int first,
                   MINUTIAE *minutiae)
Daniel Drake's avatar
Daniel Drake committed
490
{
Bastien Nocera's avatar
Bastien Nocera committed
491
492
493
   double *join_thetas, theta;
   int i;
   static double pi2 = M_PI*2.0;
Daniel Drake's avatar
Daniel Drake committed
494

Bastien Nocera's avatar
Bastien Nocera committed
495
496
497
498
499
500
501
   /* 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
502

Bastien Nocera's avatar
Bastien Nocera committed
503
504
505
506
507
508
509
510
511
   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);
512

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

   /* 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);
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
}

/*************************************************************************
**************************************************************************
#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
547
int ridge_count(const int first, const int second, MINUTIAE *minutiae,
548
549
550
551
552
553
                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
554
   int ridge_count, ridge_start, ridge_end;
555
556
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
   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
603
   ridge_count = 0;
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618

   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
619
         return(ridge_count);
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
      }
      /* 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
636
         return(ridge_count);
637
638
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
      }
      /* 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
669
         ridge_count++;
670
671
672
673
674
675
676
677
678
679
680
681
682
      }

      /* 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
683
   return(ridge_count);
684
685
686
687
}

/*************************************************************************
**************************************************************************
Bastien Nocera's avatar
Bastien Nocera committed
688
689
690
691
#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).
692
693

   Input:
Bastien Nocera's avatar
Bastien Nocera committed
694
695
696
697
698
699
700
701
702
      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
703
   Output:
Bastien Nocera's avatar
Bastien Nocera committed
704
      iptr  - points to location where 2nd pixel in pair is found
705
   Return Code:
Bastien Nocera's avatar
Bastien Nocera committed
706
707
      TRUE  - pixel pair transition found
      FALSE - pixel pair transition not found
708
**************************************************************************/
Bastien Nocera's avatar
Bastien Nocera committed
709
710
711
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)
712
{
Bastien Nocera's avatar
Bastien Nocera committed
713
   int i, j;
Daniel Drake's avatar
Daniel Drake committed
714

Bastien Nocera's avatar
Bastien Nocera committed
715
716
717
718
   /* 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
719

Bastien Nocera's avatar
Bastien Nocera committed
720
721
722
723
724
725
726
727
   /* 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
728

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

Bastien Nocera's avatar
Bastien Nocera committed
738
739
740
741
742
   /* 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);
743
744
745
746
}

/*************************************************************************
**************************************************************************
Bastien Nocera's avatar
Bastien Nocera committed
747
748
749
750
751
752
#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.
753
754

   Input:
Bastien Nocera's avatar
Bastien Nocera committed
755
756
757
758
759
760
761
762
763
764
      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
765
   Return Code:
Bastien Nocera's avatar
Bastien Nocera committed
766
767
768
      TRUE        - ridge crossing VALID
      FALSE       - ridge corssing INVALID
      Negative    - system error
769
**************************************************************************/
Bastien Nocera's avatar
Bastien Nocera committed
770
771
772
773
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)
774
775
{
   int ret;
Bastien Nocera's avatar
Bastien Nocera committed
776
777
   int feat_x, feat_y, edge_x, edge_y;
   int *contour_x, *contour_y, *contour_ex, *contour_ey, ncontour;
778

Bastien Nocera's avatar
Bastien Nocera committed
779
780
781
782
783
   /* 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];
784

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

Bastien Nocera's avatar
Bastien Nocera committed
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
   /* 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
806
      return(ret);
807

Bastien Nocera's avatar
Bastien Nocera committed
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
   /* 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. */
832
         return(ret);
Bastien Nocera's avatar
Bastien Nocera committed
833
834
835
836
837
838
839
840
841
842
843
844

      /* 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);
845
      }
Bastien Nocera's avatar
Bastien Nocera committed
846
      /* Otherwise, second trace returned IGNORE or ridge start found. */
847
   }
Bastien Nocera's avatar
Bastien Nocera committed
848
   /* Otherwise, first trace returned IGNORE or ridge start found. */
Daniel Drake's avatar
Daniel Drake committed
849

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