GCC Code Coverage Report

Directory: ./
File: libfprint/nbis/mindtct/contour.c
Date: 2024-05-04 14:54:39
Exec Total Coverage
Lines: 298 330 90.3%
Functions: 12 12 100.0%
Branches: 91 118 77.1%
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: CONTOUR.C
49 AUTHOR: Michael D. Garris
50 DATE: 05/11/1999
51 UPDATED: 10/04/1999 Version 2 by MDG
52 UPDATED: 03/16/2005 by MDG
53
54 Contains routines responsible for extracting and analyzing
55 minutia feature contour lists as part of the NIST Latent
56 Fingerprint System (LFS).
57
58 ***********************************************************************
59 ROUTINES:
60 allocate_contour()
61 free_contour()
62 get_high_curvature_contour()
63 get_centered_contour()
64 trace_contour()
65 search_contour()
66 next_contour_pixel()
67 start_scan_nbr()
68 next_scan_nbr()
69 min_contour_theta()
70 contour_limits()
71 ***********************************************************************/
72
73 #include <stdio.h>
74 #include <lfs.h>
75
76 /*************************************************************************
77 **************************************************************************
78 #cat: allocate_contour - Allocates the lists needed to represent the
79 #cat: contour of a minutia feature (a ridge or valley-ending).
80 #cat: This includes two lists of coordinate pairs. The first is
81 #cat: the 8-connected chain of points interior to the feature
82 #cat: and are called the feature's "contour points".
83 #cat: The second is a list or corresponding points each
84 #cat: adjacent to its respective feature contour point in the first
85 #cat: list and on the exterior of the feature. These second points
86 #cat: are called the feature's "edge points". Don't be confused,
87 #cat: both lists of points are on the "edge". The first set is
88 #cat: guaranteed 8-connected and the color of the feature. The
89 #cat: second set is NOT guaranteed to be 8-connected and its points
90 #cat: are opposite the color of the feature. Remeber that "feature"
91 #cat: means either ridge-ending (black pixels) or valley-ending
92 #cat: (white pixels).
93
94 Input:
95 ncontour - number of items in each coordinate list to be allocated
96 Output:
97 ocontour_x - allocated x-coord list for feature's contour points
98 ocontour_y - allocated y-coord list for feature's contour points
99 ocontour_ex - allocated x-coord list for feature's edge points
100 ocontour_ey - allocated y-coord list for feature's edge points
101 Return Code:
102 Zero - lists were successfully allocated
103 Negative - system (allocation) error
104 **************************************************************************/
105 273597 int allocate_contour(int **ocontour_x, int **ocontour_y,
106 int **ocontour_ex, int **ocontour_ey, const int ncontour)
107 {
108 273597 int *contour_x, *contour_y, *contour_ex, *contour_ey;
109
110
1/2
✓ Branch 0 taken 273597 times.
✗ Branch 1 not taken.
 273597 ASSERT_SIZE_MUL(ncontour, sizeof(int));
111
112 /* Allocate contour's x-coord list. */
113 273597 contour_x = (int *)g_malloc(ncontour * sizeof(int));
114
115 /* Allocate contour's y-coord list. */
116 273597 contour_y = (int *)g_malloc(ncontour * sizeof(int));
117
118 /* Allocate contour's edge x-coord list. */
119 273597 contour_ex = (int *)g_malloc(ncontour * sizeof(int));
120
121 /* Allocate contour's edge y-coord list. */
122 273597 contour_ey = (int *)g_malloc(ncontour * sizeof(int));
123
124 /* Otherwise, allocations successful, so assign output pointers. */
125 273597 *ocontour_x = contour_x;
126 273597 *ocontour_y = contour_y;
127 273597 *ocontour_ex = contour_ex;
128 273597 *ocontour_ey = contour_ey;
129
130 /* Return normally. */
131 273597 return(0);
132 }
133
134 /*************************************************************************
135 **************************************************************************
136 #cat: free_contour - Deallocates the lists used to represent the
137 #cat: contour of a minutia feature (a ridge or valley-ending).
138 #cat: This includes two lists of coordinate pairs. The first is
139 #cat: the 8-connected chain of points interior to the feature
140 #cat: and are called the feature's "contour points".
141 #cat: The second is a list or corresponding points each
142 #cat: adjacent to its respective feature contour point in the first
143 #cat: list and on the exterior of the feature. These second points
144 #cat: are called the feature's "edge points".
145
146 Input:
147 contour_x - x-coord list for feature's contour points
148 contour_y - y-coord list for feature's contour points
149 contour_ex - x-coord list for feature's edge points
150 contour_ey - y-coord list for feature's edge points
151 **************************************************************************/
152 273597 void free_contour(int *contour_x, int *contour_y,
153 int *contour_ex, int *contour_ey)
154 {
155 273597 g_free(contour_x);
156 273597 g_free(contour_y);
157 273597 g_free(contour_ex);
158 273597 g_free(contour_ey);
159 273597 }
160
161 /*************************************************************************
162 **************************************************************************
163 #cat: get_high_curvature_contour - Takes the pixel coordinate of a detected
164 #cat: minutia feature point and its corresponding/adjacent edge
165 #cat: pixel and attempts to extract a contour of specified length
166 #cat: of the feature's edge. The contour is extracted by walking
167 #cat: the feature's edge a specified number of steps clockwise and
168 #cat: then counter-clockwise. If a loop is detected while
169 #cat: extracting the contour, the contour of the loop is returned
170 #cat: with a return code of (LOOP_FOUND). If the process fails
171 #cat: to extract a contour of total specified length, then
172 #cat: the returned contour length is set to Zero, NO allocated
173 #cat: memory is returned in this case, and the return code is set
174 #cat: to Zero. An alternative implementation would be to return
175 #cat: the incomplete contour with a return code of (INCOMPLETE).
176 #cat: For now, NO allocated contour is returned in this case.
177
178 Input:
179 half_contour - half the length of the extracted contour
180 (full-length non-loop contour = (half_contourX2)+1)
181 x_loc - starting x-pixel coord of feature (interior to feature)
182 y_loc - starting y-pixel coord of feature (interior to feature)
183 x_edge - x-pixel coord of corresponding edge pixel
184 (exterior to feature)
185 y_edge - y-pixel coord of corresponding edge pixel
186 (exterior to feature)
187 bdata - binary image data (0==while & 1==black)
188 iw - width (in pixels) of image
189 ih - height (in pixels) of image
190 Output:
191 ocontour_x - x-pixel coords of contour (interior to feature)
192 ocontour_y - y-pixel coords of contour (interior to feature)
193 ocontour_ex - x-pixel coords of corresponding edge (exterior to feature)
194 ocontour_ey - y-pixel coords of corresponding edge (exterior to feature)
195 oncontour - number of contour points returned
196 Return Code:
197 Zero - resulting contour was successfully extracted or is empty
198 LOOP_FOUND - resulting contour forms a complete loop
199 Negative - system error
200 **************************************************************************/
201 3716 int get_high_curvature_contour(int **ocontour_x, int **ocontour_y,
202 int **ocontour_ex, int **ocontour_ey, int *oncontour,
203 const int half_contour,
204 const int x_loc, const int y_loc,
205 const int x_edge, const int y_edge,
206 unsigned char *bdata, const int iw, const int ih)
207 {
208 3716 int max_contour;
209 3716 int *half1_x, *half1_y, *half1_ex, *half1_ey, nhalf1;
210 3716 int *half2_x, *half2_y, *half2_ex, *half2_ey, nhalf2;
211 3716 int *contour_x, *contour_y, *contour_ex, *contour_ey, ncontour;
212 3716 int i, j, ret;
213
214 /* Compute maximum length of complete contour */
215 /* (2 half contours + feature point). */
216 3716 max_contour = (half_contour<<1) + 1;
217
218 /* Initialize output contour length to 0. */
219 3716 *oncontour = 0;
220
221 /* Get 1st half contour with clockwise neighbor trace. */
222
2/2
✓ Branch 1 taken 167 times.
✓ Branch 2 taken 3549 times.
 3716 if((ret = trace_contour(&half1_x, &half1_y, &half1_ex, &half1_ey, &nhalf1,
223 half_contour, x_loc, y_loc, x_loc, y_loc, x_edge, y_edge,
224 SCAN_CLOCKWISE, bdata, iw, ih))){
225
226 /* If trace was not possible ... */
227
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 167 times.
 167 if(ret == IGNORE)
228 /* Return, with nothing allocated and contour length equal to 0. */
229 return(0);
230
231 /* If 1st half contour forms a loop ... */
232
1/2
✓ Branch 0 taken 167 times.
✗ Branch 1 not taken.
 167 if(ret == LOOP_FOUND){
233 /* Need to reverse the 1st half contour so that the points are */
234 /* in consistent order. */
235 /* We need to add the original feature point to the list, so */
236 /* set new contour length to one plus length of 1st half contour. */
237 167 ncontour = nhalf1+1;
238 /* Allocate new contour list. */
239
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 167 times.
 167 if((ret = allocate_contour(&contour_x, &contour_y,
240 &contour_ex, &contour_ey, ncontour))){
241 /* If allcation error, then deallocate memory allocated to */
242 /* this point in this routine. */
243 ✗ free_contour(half1_x, half1_y, half1_ex, half1_ey);
244 /* Return error code. */
245 ✗ return(ret);
246 }
247
248 /* Otherwise, we have the new contour allocated, so store the */
249 /* original feature point. */
250 167 contour_x[0] = x_loc;
251 167 contour_y[0] = y_loc;
252 167 contour_ex[0] = x_edge;
253 167 contour_ey[0] = y_edge;
254
255 /* Now store the first half contour in reverse order. */
256
2/2
✓ Branch 0 taken 1180 times.
✓ Branch 1 taken 167 times.
 1347 for(i = 1, j = nhalf1-1; i < ncontour; i++, j--){
257 1180 contour_x[i] = half1_x[j];
258 1180 contour_y[i] = half1_y[j];
259 1180 contour_ex[i] = half1_ex[j];
260 1180 contour_ey[i] = half1_ey[j];
261 }
262
263 /* Deallocate the first half contour. */
264 167 free_contour(half1_x, half1_y, half1_ex, half1_ey);
265
266 /* Assign the output pointers. */
267 167 *ocontour_x = contour_x;
268 167 *ocontour_y = contour_y;
269 167 *ocontour_ex = contour_ex;
270 167 *ocontour_ey = contour_ey;
271 167 *oncontour = ncontour;
272
273 /* Return LOOP_FOUND for further processing. */
274 167 return(LOOP_FOUND);
275 }
276
277 /* Otherwise, return the system error code from the first */
278 /* call to trace_contour. */
279 return(ret);
280 }
281
282 /* If 1st half contour not complete ... */
283
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3549 times.
 3549 if(nhalf1 < half_contour){
284 /* Deallocate the partial contour. */
285 ✗ free_contour(half1_x, half1_y, half1_ex, half1_ey);
286 /* Return, with nothing allocated and contour length equal to 0. */
287 ✗ return(0);
288 }
289
290 /* Otherwise, we have a complete 1st half contour... */
291 /* Get 2nd half contour with counter-clockwise neighbor trace. */
292 /* Use the last point from the first contour trace as the */
293 /* point to test for a loop when tracing the second contour. */
294
2/2
✓ Branch 0 taken 217 times.
✓ Branch 1 taken 3332 times.
 3549 if((ret = trace_contour(&half2_x, &half2_y, &half2_ex, &half2_ey, &nhalf2,
295 3549 half_contour, half1_x[nhalf1-1], half1_y[nhalf1-1],
296 x_loc, y_loc, x_edge, y_edge,
297 SCAN_COUNTER_CLOCKWISE, bdata, iw, ih))){
298
299 /* If 2nd trace was not possible ... */
300
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 217 times.
 217 if(ret == IGNORE){
301 /* Deallocate the 1st half contour. */
302 ✗ free_contour(half1_x, half1_y, half1_ex, half1_ey);
303 /* Return, with nothing allocated and contour length equal to 0. */
304 ✗ return(0);
305 }
306
307 /* If non-zero return code is NOT LOOP_FOUND, then system error ... */
308
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 217 times.
 217 if(ret != LOOP_FOUND){
309 /* Deallocate the 1st half contour. */
310 ✗ free_contour(half1_x, half1_y, half1_ex, half1_ey);
311 /* Return system error. */
312 ✗ return(ret);
313 }
314 }
315
316 /* If 2nd half NOT a loop AND not complete ... */
317
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3332 times.
 3332 if((ret != LOOP_FOUND) && (nhalf2 < half_contour)){
318 /* Deallocate both half contours. */
319 ✗ free_contour(half1_x, half1_y, half1_ex, half1_ey);
320 ✗ free_contour(half2_x, half2_y, half2_ex, half2_ey);
321 /* Return, with nothing allocated and contour length equal to 0. */
322 ✗ return(0);
323 }
324
325 /* Otherwise we have a full 1st half contour and a 2nd half contour */
326 /* that is either a loop or complete. In either case we need to */
327 /* concatenate the two half contours into one longer contour. */
328
329 /* Allocate output contour list. Go ahead and allocate the */
330 /* "max_contour" amount even though the resulting contour will */
331 /* likely be shorter if it forms a loop. */
332
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 3549 times.
 3549 if((ret = allocate_contour(&contour_x, &contour_y,
333 &contour_ex, &contour_ey, max_contour))){
334 /* If allcation error, then deallocate memory allocated to */
335 /* this point in this routine. */
336 ✗ free_contour(half1_x, half1_y, half1_ex, half1_ey);
337 ✗ free_contour(half2_x, half2_y, half2_ex, half2_ey);
338 /* Return error code. */
339 ✗ return(ret);
340 }
341
342 /* Set the current contour point counter to 0 */
343 3549 ncontour = 0;
344
345 /* Copy 1st half contour into output contour buffers. */
346 /* This contour was collected clockwise, so it's points */
347 /* are entered in reverse order of the trace. The result */
348 /* is the first point in the output contour if farthest */
349 /* from the starting feature point. */
350
2/2
✓ Branch 0 taken 49686 times.
✓ Branch 1 taken 3549 times.
 53235 for(i = 0, j = nhalf1-1; i < nhalf1; i++, j--){
351 49686 contour_x[i] = half1_x[j];
352 49686 contour_y[i] = half1_y[j];
353 49686 contour_ex[i] = half1_ex[j];
354 49686 contour_ey[i] = half1_ey[j];
355 49686 ncontour++;
356 }
357
358 /* Deallocate 1st half contour. */
359 3549 free_contour(half1_x, half1_y, half1_ex, half1_ey);
360
361 /* Next, store starting feature point into output contour buffers. */
362 3549 contour_x[nhalf1] = x_loc;
363 3549 contour_y[nhalf1] = y_loc;
364 3549 contour_ex[nhalf1] = x_edge;
365 3549 contour_ey[nhalf1] = y_edge;
366 3549 ncontour++;
367
368 /* Now, append 2nd half contour to permanent contour buffers. */
369
2/2
✓ Branch 0 taken 48441 times.
✓ Branch 1 taken 3549 times.
 51990 for(i = 0, j = nhalf1+1; i < nhalf2; i++, j++){
370 48441 contour_x[j] = half2_x[i];
371 48441 contour_y[j] = half2_y[i];
372 48441 contour_ex[j] = half2_ex[i];
373 48441 contour_ey[j] = half2_ey[i];
374 48441 ncontour++;
375 }
376
377 /* Deallocate 2nd half contour. */
378 3549 free_contour(half2_x, half2_y, half2_ex, half2_ey);
379
380 /* Assign outputs contour to output ponters. */
381 3549 *ocontour_x = contour_x;
382 3549 *ocontour_y = contour_y;
383 3549 *ocontour_ex = contour_ex;
384 3549 *ocontour_ey = contour_ey;
385 3549 *oncontour = ncontour;
386
387 /* Return the resulting return code form the 2nd call to trace_contour */
388 /* (the value will either be 0 or LOOP_FOUND). */
389 3549 return(ret);
390 }
391
392 /*************************************************************************
393 **************************************************************************
394 #cat: get_centered_contour - Takes the pixel coordinate of a detected
395 #cat: minutia feature point and its corresponding/adjacent edge
396 #cat: pixel and attempts to extract a contour of specified length
397 #cat: of the feature's edge. The contour is extracted by walking
398 #cat: the feature's edge a specified number of steps clockwise and
399 #cat: then counter-clockwise. If a loop is detected while
400 #cat: extracting the contour, no contour is returned with a return
401 #cat: code of (LOOP_FOUND). If the process fails to extract a
402 #cat: a complete contour, a code of INCOMPLETE is returned.
403
404 Input:
405 half_contour - half the length of the extracted contour
406 (full-length non-loop contour = (half_contourX2)+1)
407 x_loc - starting x-pixel coord of feature (interior to feature)
408 y_loc - starting y-pixel coord of feature (interior to feature)
409 x_edge - x-pixel coord of corresponding edge pixel
410 (exterior to feature)
411 y_edge - y-pixel coord of corresponding edge pixel
412 (exterior to feature)
413 bdata - binary image data (0==while & 1==black)
414 iw - width (in pixels) of image
415 ih - height (in pixels) of image
416 Output:
417 ocontour_x - x-pixel coords of contour (interior to feature)
418 ocontour_y - y-pixel coords of contour (interior to feature)
419 ocontour_ex - x-pixel coords of corresponding edge (exterior to feature)
420 ocontour_ey - y-pixel coords of corresponding edge (exterior to feature)
421 oncontour - number of contour points returned
422 Return Code:
423 Zero - resulting contour was successfully extracted or is empty
424 LOOP_FOUND - resulting contour forms a complete loop
425 IGNORE - contour could not be traced due to problem starting
426 conditions
427 INCOMPLETE - resulting contour was not long enough
428 Negative - system error
429 **************************************************************************/
430 22446 int get_centered_contour(int **ocontour_x, int **ocontour_y,
431 int **ocontour_ex, int **ocontour_ey, int *oncontour,
432 const int half_contour,
433 const int x_loc, const int y_loc,
434 const int x_edge, const int y_edge,
435 unsigned char *bdata, const int iw, const int ih)
436 {
437 22446 int max_contour;
438 22446 int *half1_x, *half1_y, *half1_ex, *half1_ey, nhalf1;
439 22446 int *half2_x, *half2_y, *half2_ex, *half2_ey, nhalf2;
440 22446 int *contour_x, *contour_y, *contour_ex, *contour_ey, ncontour;
441 22446 int i, j, ret;
442
443
1/2
✓ Branch 0 taken 22446 times.
✗ Branch 1 not taken.
 22446 g_assert (half_contour > 0);
444
445 /* Compute maximum length of complete contour */
446 /* (2 half contours + feature point). */
447 22446 max_contour = (half_contour<<1) + 1;
448
449 /* Initialize output contour length to 0. */
450 22446 *oncontour = 0;
451
452 /* Get 1st half contour with clockwise neighbor trace. */
453 22446 ret = trace_contour(&half1_x, &half1_y, &half1_ex, &half1_ey, &nhalf1,
454 half_contour, x_loc, y_loc, x_loc, y_loc, x_edge, y_edge,
455 SCAN_CLOCKWISE, bdata, iw, ih);
456
457 /* If system error occurred ... */
458
1/2
✓ Branch 0 taken 22446 times.
✗ Branch 1 not taken.
 22446 if(ret < 0){
459 /* Return error code. */
460 return(ret);
461 }
462
463 /* If trace was not possible ... */
464
2/2
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 22425 times.
 22446 if(ret == IGNORE)
465 /* Return IGNORE, with nothing allocated. */
466 return(IGNORE);
467
468 /* If 1st half contour forms a loop ... */
469
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 22424 times.
 22425 if(ret == LOOP_FOUND){
470 /* Deallocate loop's contour. */
471 1 free_contour(half1_x, half1_y, half1_ex, half1_ey);
472 /* Return LOOP_FOUND, with nothing allocated. */
473 1 return(LOOP_FOUND);
474 }
475
476 /* If 1st half contour not complete ... */
477
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 22424 times.
 22424 if(nhalf1 < half_contour){
478 /* Deallocate the partial contour. */
479 ✗ free_contour(half1_x, half1_y, half1_ex, half1_ey);
480 /* Return, with nothing allocated and contour length equal to 0. */
481 ✗ return(INCOMPLETE);
482 }
483
484 /* Otherwise, we have a complete 1st half contour... */
485 /* Get 2nd half contour with counter-clockwise neighbor trace. */
486 /* Use the last point from the first contour trace as the */
487 /* point to test for a loop when tracing the second contour. */
488 44848 ret = trace_contour(&half2_x, &half2_y, &half2_ex, &half2_ey, &nhalf2,
489 22424 half_contour, half1_x[nhalf1-1], half1_y[nhalf1-1],
490 x_loc, y_loc, x_edge, y_edge,
491 SCAN_COUNTER_CLOCKWISE, bdata, iw, ih);
492
493 /* If system error occurred on 2nd trace ... */
494
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 22424 times.
 22424 if(ret < 0){
495 /* Deallocate loop's contour. */
496 ✗ free_contour(half1_x, half1_y, half1_ex, half1_ey);
497 /* Return error code. */
498 ✗ return(ret);
499 }
500
501 /* If 2nd trace was not possible ... */
502
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 22424 times.
 22424 if(ret == IGNORE){
503 /* Deallocate the 1st half contour. */
504 ✗ free_contour(half1_x, half1_y, half1_ex, half1_ey);
505 /* Return, with nothing allocated and contour length equal to 0. */
506 ✗ return(IGNORE);
507 }
508
509 /* If 2nd trace forms a loop ... */
510
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 22400 times.
 22424 if(ret == LOOP_FOUND){
511 /* Deallocate 1st and 2nd half contours. */
512 24 free_contour(half1_x, half1_y, half1_ex, half1_ey);
513 24 free_contour(half2_x, half2_y, half2_ex, half2_ey);
514 /* Return LOOP_FOUND, with nothing allocated. */
515 24 return(LOOP_FOUND);
516 }
517
518 /* If 2nd half contour not complete ... */
519
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 22400 times.
 22400 if(nhalf2 < half_contour){
520 /* Deallocate 1st and 2nd half contours. */
521 ✗ free_contour(half1_x, half1_y, half1_ex, half1_ey);
522 ✗ free_contour(half2_x, half2_y, half2_ex, half2_ey);
523 /* Return, with nothing allocated and contour length equal to 0. */
524 ✗ return(INCOMPLETE);
525 }
526
527 /* Otherwise we have a full 1st half contour and a 2nd half contour */
528 /* that do not form a loop and are complete. We now need to */
529 /* concatenate the two half contours into one longer contour. */
530
531 /* Allocate output contour list. */
532
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 22400 times.
 22400 if((ret = allocate_contour(&contour_x, &contour_y,
533 &contour_ex, &contour_ey, max_contour))){
534 /* If allcation error, then deallocate memory allocated to */
535 /* this point in this routine. */
536 ✗ free_contour(half1_x, half1_y, half1_ex, half1_ey);
537 ✗ free_contour(half2_x, half2_y, half2_ex, half2_ey);
538 /* Return error code. */
539 ✗ return(ret);
540 }
541
542 /* Set the current contour point counter to 0 */
543 22400 ncontour = 0;
544
545 /* Copy 1st half contour into output contour buffers. */
546 /* This contour was collected clockwise, so it's points */
547 /* are entered in reverse order of the trace. The result */
548 /* is the first point in the output contour if farthest */
549 /* from the starting feature point. */
550
2/2
✓ Branch 0 taken 156800 times.
✓ Branch 1 taken 22400 times.
 179200 for(i = 0, j = nhalf1-1; i < nhalf1; i++, j--){
551 156800 contour_x[i] = half1_x[j];
552 156800 contour_y[i] = half1_y[j];
553 156800 contour_ex[i] = half1_ex[j];
554 156800 contour_ey[i] = half1_ey[j];
555 156800 ncontour++;
556 }
557
558 /* Deallocate 1st half contour. */
559 22400 free_contour(half1_x, half1_y, half1_ex, half1_ey);
560
561 /* Next, store starting feature point into output contour buffers. */
562 22400 contour_x[nhalf1] = x_loc;
563 22400 contour_y[nhalf1] = y_loc;
564 22400 contour_ex[nhalf1] = x_edge;
565 22400 contour_ey[nhalf1] = y_edge;
566 22400 ncontour++;
567
568 /* Now, append 2nd half contour to permanent contour buffers. */
569
2/2
✓ Branch 0 taken 156800 times.
✓ Branch 1 taken 22400 times.
 179200 for(i = 0, j = nhalf1+1; i < nhalf2; i++, j++){
570 156800 contour_x[j] = half2_x[i];
571 156800 contour_y[j] = half2_y[i];
572 156800 contour_ex[j] = half2_ex[i];
573 156800 contour_ey[j] = half2_ey[i];
574 156800 ncontour++;
575 }
576
577 /* Deallocate 2nd half contour. */
578 22400 free_contour(half2_x, half2_y, half2_ex, half2_ey);
579
580 /* Assign outputs contour to output ponters. */
581 22400 *ocontour_x = contour_x;
582 22400 *ocontour_y = contour_y;
583 22400 *ocontour_ex = contour_ex;
584 22400 *ocontour_ey = contour_ey;
585 22400 *oncontour = ncontour;
586
587 /* Return normally. */
588 22400 return(0);
589 }
590
591 /*************************************************************************
592 **************************************************************************
593 #cat: trace_contour - Takes the pixel coordinate of a detected minutia
594 #cat: feature point and its corresponding/adjacent edge pixel
595 #cat: and extracts a contour (up to a specified maximum length)
596 #cat: of the feature's edge in either a clockwise or counter-
597 #cat: clockwise direction. A second point is specified, such that
598 #cat: if this point is encounted while extracting the contour,
599 #cat: it is to be assumed that a loop has been found and a code
600 #cat: of (LOOP_FOUND) is returned with the contour. By independently
601 #cat: specifying this point, successive calls can be made to
602 #cat: this routine from the same starting point, and loops across
603 #cat: successive calls can be detected.
604
605 Input:
606 max_len - maximum length of contour to be extracted
607 x_loop - x-pixel coord of point, if encountered, triggers LOOP_FOUND
608 y_loop - y-pixel coord of point, if encountered, triggers LOOP_FOUND
609 x_loc - starting x-pixel coord of feature (interior to feature)
610 y_loc - starting y-pixel coord of feature (interior to feature)
611 x_edge - x-pixel coord of corresponding edge pixel (exterior to feature)
612 y_edge - y-pixel coord of corresponding edge pixel (exterior to feature)
613 scan_clock - direction in which neighboring pixels are to be scanned
614 for the next contour pixel
615 bdata - binary image data (0==while & 1==black)
616 iw - width (in pixels) of image
617 ih - height (in pixels) of image
618 Output:
619 ocontour_x - x-pixel coords of contour (interior to feature)
620 ocontour_y - y-pixel coords of contour (interior to feature)
621 ocontour_ex - x-pixel coords of corresponding edge (exterior to feature)
622 ocontour_ey - y-pixel coords of corresponding edge (exterior to feature)
623 oncontour - number of contour points returned
624 Return Code:
625 Zero - resulting contour was successfully allocated and extracted
626 LOOP_FOUND - resulting contour forms a complete loop
627 IGNORE - trace is not possible due to state of inputs
628 Negative - system error
629 **************************************************************************/
630 244934 int trace_contour(int **ocontour_x, int **ocontour_y,
631 int **ocontour_ex, int **ocontour_ey, int *oncontour,
632 const int max_len, const int x_loop, const int y_loop,
633 const int x_loc, const int y_loc,
634 const int x_edge, const int y_edge,
635 const int scan_clock,
636 unsigned char *bdata, const int iw, const int ih)
637 {
638 244934 int *contour_x, *contour_y, *contour_ex, *contour_ey, ncontour;
639 244934 int cur_x_loc, cur_y_loc;
640 244934 int cur_x_edge, cur_y_edge;
641 244934 int next_x_loc, next_y_loc;
642 244934 int next_x_edge, next_y_edge;
643 244934 int i, ret;
644
645 /* Check to make sure that the feature and edge values are opposite. */
646 244934 if(*(bdata+(y_loc*iw)+x_loc) ==
647
2/2
✓ Branch 0 taken 244668 times.
✓ Branch 1 taken 266 times.
 244934 *(bdata+(y_edge*iw)+x_edge))
648 /* If not opposite, then the trace will not work, so return IGNORE. */
649 return(IGNORE);
650
651 /* Allocate contour buffers. */
652
1/2
✓ Branch 1 taken 244668 times.
✗ Branch 2 not taken.
 244668 if((ret = allocate_contour(&contour_x, &contour_y,
653 &contour_ex, &contour_ey, max_len))){
654 /* If allocation error, return code. */
655 return(ret);
656 }
657
658 /* Set pixel counter to 0. */
659 ncontour = 0;
660
661 /* Set up for finding first contour pixel. */
662 cur_x_loc = x_loc;
663 cur_y_loc = y_loc;
664 cur_x_edge = x_edge;
665 cur_y_edge = y_edge;
666
667 /* Foreach pixel to be collected on the feature's contour... */
668
2/2
✓ Branch 0 taken 3363262 times.
✓ Branch 1 taken 228258 times.
 3591520 for(i = 0; i < max_len; i++){
669 /* Find the next contour pixel. */
670
1/2
✓ Branch 1 taken 3363262 times.
✗ Branch 2 not taken.
 3363262 if(next_contour_pixel(&next_x_loc, &next_y_loc,
671 &next_x_edge, &next_y_edge,
672 cur_x_loc, cur_y_loc,
673 cur_x_edge, cur_y_edge,
674 scan_clock, bdata, iw, ih)){
675
676 /* If we trace back around to the specified starting */
677 /* feature location... */
678
4/4
✓ Branch 0 taken 179237 times.
✓ Branch 1 taken 3184025 times.
✓ Branch 2 taken 16410 times.
✓ Branch 3 taken 162827 times.
 3363262 if((next_x_loc == x_loop) && (next_y_loc == y_loop)){
679 /* Then we have found a loop, so return what we */
680 /* have traced to this point. */
681 16410 *ocontour_x = contour_x;
682 16410 *ocontour_y = contour_y;
683 16410 *ocontour_ex = contour_ex;
684 16410 *ocontour_ey = contour_ey;
685 16410 *oncontour = ncontour;
686 16410 return(LOOP_FOUND);
687 }
688
689 /* Otherwise, we found another point on our feature's contour, */
690 /* so store the new contour point. */
691 3346852 contour_x[i] = next_x_loc;
692 3346852 contour_y[i] = next_y_loc;
693 3346852 contour_ex[i] = next_x_edge;
694 3346852 contour_ey[i] = next_y_edge;
695 /* Bump the number of points stored. */
696 3346852 ncontour++;
697
698 /* Set up for finding next contour pixel. */
699 3346852 cur_x_loc = next_x_loc;
700 3346852 cur_y_loc = next_y_loc;
701 3346852 cur_x_edge = next_x_edge;
702 3346852 cur_y_edge = next_y_edge;
703 }
704 /* Otherwise, no new contour point found ... */
705 else{
706 /* So, stop short and return the number of pixels found */
707 /* on the contour to this point. */
708 ✗ *ocontour_x = contour_x;
709 ✗ *ocontour_y = contour_y;
710 ✗ *ocontour_ex = contour_ex;
711 ✗ *ocontour_ey = contour_ey;
712 ✗ *oncontour = ncontour;
713
714 /* Return normally. */
715 ✗ return(0);
716 }
717 }
718
719 /* If we get here, we successfully found the maximum points we */
720 /* were looking for on the feature contour, so assign the contour */
721 /* buffers to the output pointers and return. */
722 228258 *ocontour_x = contour_x;
723 228258 *ocontour_y = contour_y;
724 228258 *ocontour_ex = contour_ex;
725 228258 *ocontour_ey = contour_ey;
726 228258 *oncontour = ncontour;
727
728 /* Return normally. */
729 228258 return(0);
730 }
731
732 /*************************************************************************
733 **************************************************************************
734 #cat: search_contour - Walk the contour of a minutia feature starting at a
735 #cat: specified point on the feature and walking N steps in the
736 #cat: specified direction (clockwise or counter-clockwise), looking
737 #cat: for a second specified point. In this code, "feature" is
738 #cat: consistently referring to either the black interior edge of
739 #cat: a ridge-ending or the white interior edge of a valley-ending
740 #cat: (bifurcation). The term "edge of the feature" refers to
741 #cat: neighboring pixels on the "exterior" edge of the feature.
742 #cat: So "edge" pixels are opposite in color from the interior
743 #cat: feature pixels.
744
745 Input:
746 x_search - x-pixel coord of point being searched for
747 y_search - y-pixel coord of point being searched for
748 search_len - number of step to walk contour in search
749 x_loc - starting x-pixel coord of feature (interior to feature)
750 y_loc - starting y-pixel coord of feature (interior to feature)
751 x_edge - x-pixel coord of corresponding edge pixel
752 (exterior to feature)
753 y_edge - y-pixel coord of corresponding edge pixel
754 (exterior to feature)
755 scan_clock - direction in which neighbor pixels are to be scanned
756 (clockwise or counter-clockwise)
757 bdata - binary image data (0==while & 1==black)
758 iw - width (in pixels) of image
759 ih - height (in pixels) of image
760 Return Code:
761 NOT_FOUND - desired pixel not found along N steps of feature's contour
762 FOUND - desired pixel WAS found along N steps of feature's contour
763 **************************************************************************/
764 99699 int search_contour(const int x_search, const int y_search,
765 const int search_len,
766 const int x_loc, const int y_loc,
767 const int x_edge, const int y_edge,
768 const int scan_clock,
769 unsigned char *bdata, const int iw, const int ih)
770 {
771 99699 int cur_x_loc, cur_y_loc;
772 99699 int cur_x_edge, cur_y_edge;
773 99699 int next_x_loc, next_y_loc;
774 99699 int next_x_edge, next_y_edge;
775 99699 int i;
776
777 /* Set up for finding first contour pixel. */
778 99699 cur_x_loc = x_loc;
779 99699 cur_y_loc = y_loc;
780 99699 cur_x_edge = x_edge;
781 99699 cur_y_edge = y_edge;
782
783 /* Foreach point to be collected on the feature's contour... */
784
2/2
✓ Branch 0 taken 889403 times.
✓ Branch 1 taken 83678 times.
 973081 for(i = 0; i < search_len; i++){
785 /* Find the next contour pixel. */
786
1/2
✓ Branch 1 taken 889403 times.
✗ Branch 2 not taken.
 889403 if(next_contour_pixel(&next_x_loc, &next_y_loc,
787 &next_x_edge, &next_y_edge,
788 cur_x_loc, cur_y_loc,
789 cur_x_edge, cur_y_edge,
790 scan_clock, bdata, iw, ih)){
791
792 /* If we find the point we are looking for on the contour... */
793
4/4
✓ Branch 0 taken 62384 times.
✓ Branch 1 taken 827019 times.
✓ Branch 2 taken 46363 times.
✓ Branch 3 taken 16021 times.
 889403 if((next_x_loc == x_search) && (next_y_loc == y_search)){
794 /* Then return FOUND. */
795 return(FOUND);
796 }
797
798 /* Otherwise, set up for finding next contour pixel. */
799 873382 cur_x_loc = next_x_loc;
800 873382 cur_y_loc = next_y_loc;
801 873382 cur_x_edge = next_x_edge;
802 873382 cur_y_edge = next_y_edge;
803 }
804 /* Otherwise, no new contour point found ... */
805 else{
806 /* So, stop searching, and return NOT_FOUND. */
807 return(NOT_FOUND);
808 }
809 }
810
811 /* If we get here, we successfully searched the maximum points */
812 /* without finding our desired point, so return NOT_FOUND. */
813 return(NOT_FOUND);
814 }
815
816 /*************************************************************************
817 **************************************************************************
818 #cat: next_contour_pixel - Takes a pixel coordinate of a point determined
819 #cat: to be on the interior edge of a feature (ridge or valley-
820 #cat: ending), and attempts to locate a neighboring pixel on the
821 #cat: feature's contour. Neighbors of the current feature pixel
822 #cat: are searched in a specified direction (clockwise or counter-
823 #cat: clockwise) and the first pair of adjacent/neigboring pixels
824 #cat: found with the first pixel having the color of the feature
825 #cat: and the second the opposite color are returned as the next
826 #cat: point on the contour. One exception happens when the new
827 #cat: point is on an "exposed" corner.
828
829 Input:
830 cur_x_loc - x-pixel coord of current point on feature's
831 interior contour
832 cur_y_loc - y-pixel coord of current point on feature's
833 interior contour
834 cur_x_edge - x-pixel coord of corresponding edge pixel
835 (exterior to feature)
836 cur_y_edge - y-pixel coord of corresponding edge pixel
837 (exterior to feature)
838 scan_clock - direction in which neighboring pixels are to be scanned
839 for the next contour pixel
840 bdata - binary image data (0==while & 1==black)
841 iw - width (in pixels) of image
842 ih - height (in pixels) of image
843 Output:
844 next_x_loc - x-pixel coord of next point on feature's interior contour
845 next_y_loc - y-pixel coord of next point on feature's interior contour
846 next_x_edge - x-pixel coord of corresponding edge (exterior to feature)
847 next_y_edge - y-pixel coord of corresponding edge (exterior to feature)
848 Return Code:
849 TRUE - next contour point found and returned
850 FALSE - next contour point NOT found
851 **************************************************************************/
852 /*************************************************************************/
853 4252665 int next_contour_pixel(int *next_x_loc, int *next_y_loc,
854 int *next_x_edge, int *next_y_edge,
855 const int cur_x_loc, const int cur_y_loc,
856 const int cur_x_edge, const int cur_y_edge,
857 const int scan_clock,
858 unsigned char *bdata, const int iw, const int ih)
859 {
860 4252665 int feature_pix, edge_pix;
861 4252665 int prev_nbr_pix, prev_nbr_x, prev_nbr_y;
862 4252665 int cur_nbr_pix, cur_nbr_x, cur_nbr_y;
863 4252665 int ni, nx, ny, npix;
864 4252665 int nbr_i, i;
865
866 /* Get the feature's pixel value. */
867 4252665 feature_pix = *(bdata + (cur_y_loc * iw) + cur_x_loc);
868 /* Get the feature's edge pixel value. */
869 4252665 edge_pix = *(bdata + (cur_y_edge * iw) + cur_x_edge);
870
871 /* Get the nieghbor position of the feature's edge pixel in relationship */
872 /* to the feature's actual position. */
873 /* REMEBER: The feature's position is always interior and on a ridge */
874 /* ending (black pixel) or (for bifurcations) on a valley ending (white */
875 /* pixel). The feature's edge pixel is an adjacent pixel to the feature */
876 /* pixel that is exterior to the ridge or valley ending and opposite in */
877 /* pixel value. */
878 4252665 nbr_i = start_scan_nbr(cur_x_loc, cur_y_loc, cur_x_edge, cur_y_edge);
879
880 /* Set current neighbor scan pixel to the feature's edge pixel. */
881 4252665 cur_nbr_x = cur_x_edge;
882 4252665 cur_nbr_y = cur_y_edge;
883 4252665 cur_nbr_pix = edge_pix;
884
885 /* Foreach pixel neighboring the feature pixel ... */
886
1/2
✓ Branch 1 taken 10265901 times.
✗ Branch 2 not taken.
 14518566 for(i = 0; i < 8; i++){
887
888 /* Set current neighbor scan pixel to previous scan pixel. */
889 10265901 prev_nbr_x = cur_nbr_x;
890 10265901 prev_nbr_y = cur_nbr_y;
891 10265901 prev_nbr_pix = cur_nbr_pix;
892
893 /* Bump pixel neighbor index clockwise or counter-clockwise. */
894 10265901 nbr_i = next_scan_nbr(nbr_i, scan_clock);
895
896 /* Set current scan pixel to the new neighbor. */
897 /* REMEMBER: the neighbors are being scanned around the original */
898 /* feature point. */
899 10265901 cur_nbr_x = cur_x_loc + g_nbr8_dx[nbr_i];
900 10265901 cur_nbr_y = cur_y_loc + g_nbr8_dy[nbr_i];
901
902 /* If new neighbor is not within image boundaries... */
903
1/2
✓ Branch 0 taken 10265901 times.
✗ Branch 1 not taken.
 10265901 if((cur_nbr_x < 0) || (cur_nbr_x >= iw) ||
904
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10265901 times.
 10265901 (cur_nbr_y < 0) || (cur_nbr_y >= ih))
905 /* Return (FALSE==>Failure) if neighbor out of bounds. */
906 return(FALSE);
907
908 /* Get the new neighbor's pixel value. */
909 10265901 cur_nbr_pix = *(bdata + (cur_nbr_y * iw) + cur_nbr_x);
910
911 /* If the new neighbor's pixel value is the same as the feature's */
912 /* pixel value AND the previous neighbor's pixel value is the same */
913 /* as the features's edge, then we have "likely" found our next */
914 /* contour pixel. */
915
2/2
✓ Branch 0 taken 4256029 times.
✓ Branch 1 taken 6009872 times.
 10265901 if((cur_nbr_pix == feature_pix) && (prev_nbr_pix == edge_pix)){
916
917 /* Check to see if current neighbor is on the corner of the */
918 /* neighborhood, and if so, test to see if it is "exposed". */
919 /* The neighborhood corners have odd neighbor indicies. */
920
2/2
✓ Branch 0 taken 1439387 times.
✓ Branch 1 taken 2816642 times.
 4256029 if(nbr_i % 2){
921 /* To do this, look ahead one more neighbor pixel. */
922 1439387 ni = next_scan_nbr(nbr_i, scan_clock);
923 1439387 nx = cur_x_loc + g_nbr8_dx[ni];
924 1439387 ny = cur_y_loc + g_nbr8_dy[ni];
925 /* If new neighbor is not within image boundaries... */
926
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1439387 times.
 1439387 if((nx < 0) || (nx >= iw) ||
927
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1439387 times.
 1439387 (ny < 0) || (ny >= ih))
928 /* Return (FALSE==>Failure) if neighbor out of bounds. */
929 return(FALSE);
930 1439387 npix = *(bdata + (ny * iw) + nx);
931
932 /* If the next neighbor's value is also the same as the */
933 /* feature's pixel, then corner is NOT exposed... */
934
2/2
✓ Branch 0 taken 1436023 times.
✓ Branch 1 taken 3364 times.
 1439387 if(npix == feature_pix){
935 /* Assign the current neighbor pair to the output pointers. */
936 1436023 *next_x_loc = cur_nbr_x;
937 1436023 *next_y_loc = cur_nbr_y;
938 1436023 *next_x_edge = prev_nbr_x;
939 1436023 *next_y_edge = prev_nbr_y;
940 /* Return TRUE==>Success. */
941 1436023 return(TRUE);
942 }
943 /* Otherwise, corner pixel is "exposed" so skip it. */
944 else{
945 /* Skip current corner neighbor by resetting it to the */
946 /* next neighbor, which upon the iteration will immediately */
947 /* become the previous neighbor. */
948 3364 cur_nbr_x = nx;
949 3364 cur_nbr_y = ny;
950 3364 cur_nbr_pix = npix;
951 /* Advance neighbor index. */
952 3364 nbr_i = ni;
953 /* Advance neighbor count. */
954 3364 i++;
955 }
956 }
957 /* Otherwise, current neighbor is not a corner ... */
958 else{
959 /* Assign the current neighbor pair to the output pointers. */
960 2816642 *next_x_loc = cur_nbr_x;
961 2816642 *next_y_loc = cur_nbr_y;
962 2816642 *next_x_edge = prev_nbr_x;
963 2816642 *next_y_edge = prev_nbr_y;
964 /* Return TRUE==>Success. */
965 2816642 return(TRUE);
966 }
967 }
968 }
969
970 /* If we get here, then we did not find the next contour pixel */
971 /* within the 8 neighbors of the current feature pixel so */
972 /* return (FALSE==>Failure). */
973 /* NOTE: This must mean we found a single isolated pixel. */
974 /* Perhaps this should be filled? */
975 return(FALSE);
976 }
977
978 /*************************************************************************
979 **************************************************************************
980 #cat: start_scan_nbr - Takes a two pixel coordinates that are either
981 #cat: aligned north-to-south or east-to-west, and returns the
982 #cat: position the second pixel is in realtionship to the first.
983 #cat: The positions returned are based on 8-connectedness.
984 #cat: NOTE, this routine does NOT account for diagonal positions.
985
986 Input:
987 x_prev - x-coord of first point
988 y_prev - y-coord of first point
989 x_next - x-coord of second point
990 y_next - y-coord of second point
991 Return Code:
992 NORTH - second pixel above first
993 SOUTH - second pixel below first
994 EAST - second pixel right of first
995 WEST - second pixel left of first
996 **************************************************************************/
997 4252665 int start_scan_nbr(const int x_prev, const int y_prev,
998 const int x_next, const int y_next)
999 {
1000
2/2
✓ Branch 0 taken 2928804 times.
✓ Branch 1 taken 1323861 times.
 4252665 if((x_prev==x_next) && (y_next > y_prev))
1001 return(SOUTH);
1002
2/2
✓ Branch 0 taken 1710022 times.
✓ Branch 1 taken 1218782 times.
 2928804 else if ((x_prev==x_next) && (y_next < y_prev))
1003 return(NORTH);
1004
2/2
✓ Branch 0 taken 977633 times.
✓ Branch 1 taken 732389 times.
 1710022 else if ((x_next > x_prev) && (y_prev==y_next))
1005 return(EAST);
1006
1/2
✓ Branch 0 taken 977633 times.
✗ Branch 1 not taken.
 977633 else if ((x_next < x_prev) && (y_prev==y_next))
1007 977633 return(WEST);
1008
1009 /* Added by MDG on 03-16-05 */
1010 /* Should never reach here. Added to remove compiler warning. */
1011 return(INVALID_DIR); /* -1 */
1012 }
1013
1014 /*************************************************************************
1015 **************************************************************************
1016 #cat: next_scan_nbr - Advances the given 8-connected neighbor index
1017 #cat: on location in the specifiec direction (clockwise or
1018 #cat: counter-clockwise).
1019
1020 Input:
1021 nbr_i - current 8-connected neighbor index
1022 scan_clock - direction in which the neighbor index is to be advanced
1023 Return Code:
1024 Next neighbor - 8-connected index of next neighbor
1025 **************************************************************************/
1026 11705288 int next_scan_nbr(const int nbr_i, const int scan_clock)
1027 {
1028 11705288 int new_i;
1029
1030 /* If scanning neighbors clockwise ... */
1031
2/2
✓ Branch 0 taken 8011600 times.
✓ Branch 1 taken 3693688 times.
 11705288 if(scan_clock == SCAN_CLOCKWISE)
1032 /* Advance one neighbor clockwise. */
1033 8011600 new_i = (nbr_i+1)%8;
1034 /* Otherwise, scanning neighbors counter-clockwise ... */
1035 else
1036 /* Advance one neighbor counter-clockwise. */
1037 /* There are 8 pixels in the neighborhood, so to */
1038 /* decrement with wrapping from 0 around to 7, add */
1039 /* the nieghbor index by 7 and mod with 8. */
1040 3693688 new_i = (nbr_i+7)%8;
1041
1042 /* Return the new neighbor index. */
1043 11705288 return(new_i);
1044 }
1045
1046 /*************************************************************************
1047 **************************************************************************
1048 #cat: min_contour_theta - Takes a contour list and analyzes it locating the
1049 #cat: point at which the contour has highest curvature
1050 #cat: (or minimum interior angle). The angle of curvature is
1051 #cat: computed by searching a majority of points on the contour.
1052 #cat: At each of these points, a left and right segment (or edge)
1053 #cat: are extended out N number of pixels from the center point
1054 #cat: on the contour. The angle is formed between the straight line
1055 #cat: connecting the center point to the end point on the left edge
1056 #cat: and the line connecting the center point to the end of the
1057 #cat: right edge. The point of highest curvature is determined
1058 #cat: by locating the where the minimum of these angles occurs.
1059
1060 Input:
1061 angle_edge - length of the left and right edges extending from a
1062 common/centered pixel on the contour
1063 contour_x - x-coord list for contour points
1064 contour_y - y-coord list for contour points
1065 ncontour - number of points in contour
1066 Output:
1067 omin_i - index of contour point where minimum occurred
1068 omin_theta - minimum angle found along the contour
1069 Return Code:
1070 Zero - minimum angle successfully located
1071 IGNORE - ignore the contour
1072 Negative - system error
1073 **************************************************************************/
1074 3549 int min_contour_theta(int *omin_i, double *omin_theta,
1075 const int angle_edge, const int *contour_x,
1076 const int *contour_y, const int ncontour)
1077 {
1078 3549 int pleft, pcenter, pright;
1079 3549 double theta1, theta2, dtheta;
1080 3549 int min_i;
1081 3549 double min_theta;
1082
1083 /* If the contour length is too short for processing... */
1084
1/2
✓ Branch 0 taken 3549 times.
✗ Branch 1 not taken.
 3549 if(ncontour < (angle_edge<<1)+1)
1085 /* Return IGNORE. */
1086 return(IGNORE);
1087
1088 /* Intialize running minimum values. */
1089 3549 min_theta = M_PI;
1090 /* Need to truncate precision so that answers are consistent */
1091 /* on different computer architectures when comparing doubles. */
1092 3549 min_theta = trunc_dbl_precision(min_theta, TRUNC_SCALE);
1093 3549 min_i = -1;
1094
1095 /* Set left angle point to first contour point. */
1096 3549 pleft = 0;
1097 /* Set center angle point to "angle_edge" points into contour. */
1098 3549 pcenter = angle_edge;
1099 /* Set right angle point to "angle_edge" points from pcenter. */
1100 3549 pright = pcenter + angle_edge;
1101
1102 /* Loop until the right angle point exceeds the contour list. */
1103
2/2
✓ Branch 0 taken 51990 times.
✓ Branch 1 taken 3549 times.
 55539 while(pright < ncontour){
1104 /* Compute angle to first edge line (connecting pcenter to pleft). */
1105 103980 theta1 = angle2line(contour_x[pcenter],contour_y[pcenter],
1106 51990 contour_x[pleft],contour_y[pleft]);
1107 /* Compute angle to second edge line (connecting pcenter to pright). */
1108 103980 theta2 = angle2line(contour_x[pcenter],contour_y[pcenter],
1109 51990 contour_x[pright],contour_y[pright]);
1110
1111 /* Compute delta between angles accounting for an inner */
1112 /* and outer distance between the angles. */
1113 51990 dtheta = fabs(theta2 - theta1);
1114
2/2
✓ Branch 0 taken 16482 times.
✓ Branch 1 taken 35508 times.
 51990 dtheta = min(dtheta, (M_PI*2.0)-dtheta);
1115 /* Need to truncate precision so that answers are consistent */
1116 /* on different computer architectures when comparing doubles. */
1117
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16482 times.
 51990 dtheta = trunc_dbl_precision(dtheta, TRUNC_SCALE);
1118
1119 /* Keep track of running minimum theta. */
1120
2/2
✓ Branch 0 taken 17274 times.
✓ Branch 1 taken 34716 times.
 51990 if(dtheta < min_theta){
1121 17274 min_i = pcenter;
1122 17274 min_theta = dtheta;
1123 }
1124
1125 /* Bump to next points on contour. */
1126 51990 pleft++;
1127 51990 pcenter++;
1128 51990 pright++;
1129 }
1130
1131 /* If no minimum found (then contour is perfectly flat) so minimum */
1132 /* to center point on contour. */
1133
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 3535 times.
 3549 if(min_i == -1){
1134 14 *omin_i = ncontour>>1;
1135 14 *omin_theta = min_theta;
1136 }
1137 else{
1138 /* Assign minimum theta information to output pointers. */
1139 3535 *omin_i = min_i;
1140 3535 *omin_theta = min_theta;
1141 }
1142
1143 /* Return successfully. */
1144 return(0);
1145 }
1146
1147 /*************************************************************************
1148 **************************************************************************
1149 #cat: contour_limits - Determines the X and Y coordinate limits of the
1150 #cat: given contour list.
1151
1152 Input:
1153 contour_x - x-coord list for contour points
1154 contour_y - y-coord list for contour points
1155 ncontour - number of points in contour
1156 Output:
1157 xmin - left-most x-coord in contour
1158 ymin - top-most y-coord in contour
1159 xmax - right-most x-coord in contour
1160 ymax - bottom-most y-coord in contour
1161 **************************************************************************/
1162 2980 void contour_limits(int *xmin, int *ymin, int *xmax, int *ymax,
1163 const int *contour_x, const int *contour_y, const int ncontour)
1164 {
1165 /* Find the minimum x-coord from the list of contour points. */
1166 2980 *xmin = minv(contour_x, ncontour);
1167 /* Find the minimum y-coord from the list of contour points. */
1168 2980 *ymin = minv(contour_y, ncontour);
1169 /* Find the maximum x-coord from the list of contour points. */
1170 2980 *xmax = maxv(contour_x, ncontour);
1171 /* Find the maximum y-coord from the list of contour points. */
1172 2980 *ymax = maxv(contour_y, ncontour);
1173 2980 }
1174
1175 /*************************************************************************
1176 **************************************************************************
1177 #cat: fix_edge_pixel_pair - Takes a pair of pixel points with the first
1178 #cat: pixel on a feature and the second adjacent and off the feature,
1179 #cat: determines if the pair neighbor diagonally. If they do, their
1180 #cat: locations are adjusted so that the resulting pair retains the
1181 #cat: same pixel values, but are neighboring either to the N,S,E or W.
1182 #cat: This routine is needed in order to prepare the pixel pair for
1183 #cat: contour tracing.
1184
1185 Input:
1186 feat_x - pointer to x-pixel coord on feature
1187 feat_y - pointer to y-pixel coord on feature
1188 edge_x - pointer to x-pixel coord on edge of feature
1189 edge_y - pointer to y-pixel coord on edge of feature
1190 bdata - binary image data (0==while & 1==black)
1191 iw - width (in pixels) of image
1192 ih - height (in pixels) of image
1193 Output:
1194 feat_x - pointer to resulting x-pixel coord on feature
1195 feat_y - pointer to resulting y-pixel coord on feature
1196 edge_x - pointer to resulting x-pixel coord on edge of feature
1197 edge_y - pointer to resulting y-pixel coord on edge of feature
1198 **************************************************************************/
1199 59166 void fix_edge_pixel_pair(int *feat_x, int *feat_y, int *edge_x, int *edge_y,
1200 unsigned char *bdata, const int iw, const int ih)
1201 {
1202 59166 int dx, dy;
1203 59166 int px, py, cx, cy;
1204 59166 int feature_pix;
1205
1206 /* Get the pixel value of the feature. */
1207 59166 feature_pix = *(bdata + ((*feat_y) * iw) + (*feat_x));
1208
1209 /* Store the input points to current and previous points. */
1210 59166 cx = *feat_x;
1211 59166 cy = *feat_y;
1212 59166 px = *edge_x;
1213 59166 py = *edge_y;
1214
1215 /* Compute detlas between current and previous point. */
1216 59166 dx = px - cx;
1217 59166 dy = py - cy;
1218
1219 /* If previous point (P) is diagonal neighbor of */
1220 /* current point (C)... This is a problem because */
1221 /* the contour tracing routine requires that the */
1222 /* "edge" pixel be north, south, east, or west of */
1223 /* of the feature point. If the previous pixel is */
1224 /* diagonal neighbor, then we need to adjust either */
1225 /* the positon of te previous or current pixel. */
1226
4/4
✓ Branch 0 taken 35774 times.
✓ Branch 1 taken 23392 times.
✓ Branch 2 taken 25691 times.
✓ Branch 3 taken 10083 times.
 59166 if((abs(dx)==1) && (abs(dy)==1)){
1227 /* Then we have one of the 4 following conditions: */
1228 /* */
1229 /* *C C* */
1230 /* 1. P* 2. P* 3. *P 4. *P */
1231 /* *C C* */
1232 /* */
1233 /* dx = -1 -1 1 1 */
1234 /* dy = 1 -1 -1 1 */
1235 /* */
1236 /* Want to test values in positions of '*': */
1237 /* Let point P == (px, py) */
1238 /* p1 == '*' positon where x changes */
1239 /* p2 == '*' positon where y changes */
1240 /* */
1241 /* p1 = px+1,py px+1,py px-1,py px-1,py */
1242 /* p2 = px,py-1 px,py+1 px,py+1 px,py-1 */
1243 /* */
1244 /* These can all be rewritten: */
1245 /* p1 = px-dx,py */
1246 /* p2 = px,py-dy */
1247
1248 /* Check if 'p1' is NOT the value we are searching for... */
1249
2/2
✓ Branch 0 taken 10471 times.
✓ Branch 1 taken 15220 times.
 25691 if(*(bdata+(py*iw)+(px-dx)) != feature_pix)
1250 /* Then set x-coord of edge pixel to p1. */
1251 px -= dx;
1252 /* Check if 'p2' is NOT the value we are searching for... */
1253
2/2
✓ Branch 0 taken 4811 times.
✓ Branch 1 taken 5660 times.
 10471 else if(*(bdata+((py-dy)*iw)+px) != feature_pix)
1254 /* Then set y-coord of edge pixel to p2. */
1255 py -= dy;
1256 /* Otherwise, the current pixel 'C' is exposed on a corner ... */
1257 else{
1258 /* Set pixel 'C' to 'p1', which also has the pixel */
1259 /* value we are searching for. */
1260 4811 cy += dy;
1261 }
1262
1263 /* Set the pointers to the resulting values. */
1264 25691 *feat_x = cx;
1265 25691 *feat_y = cy;
1266 25691 *edge_x = px;
1267 25691 *edge_y = py;
1268 }
1269
1270 /* Otherwise, nothing has changed. */
1271 59166 }
1272