1 /*******************************************************************************
2
3 License:
4 This software was developed at the National Institute of Standards and
5 Technology (NIST) by employees of the Federal Government in the course
6 of their official duties. Pursuant to title 17 Section 105 of the
7 United States Code, this software is not subject to copyright protection
8 and is in the public domain. NIST assumes no responsibility whatsoever for
9 its use by other parties, and makes no guarantees, expressed or implied,
10 about its quality, reliability, or any other characteristic.
11
12 Disclaimer:
13 This software was developed to promote biometric standards and biometric
14 technology testing for the Federal Government in accordance with the USA
15 PATRIOT Act and the Enhanced Border Security and Visa Entry Reform Act.
16 Specific hardware and software products identified in this software were used
17 in order to perform the software development. In no case does such
18 identification imply recommendation or endorsement by the National Institute
19 of Standards and Technology, nor does it imply that the products and equipment
20 identified are necessarily the best available for the purpose.
21
22 *******************************************************************************/
23
24 /***********************************************************************
25 LIBRARY: LFS - NIST Latent Fingerprint System
26
27 FILE: SHAPE.C
28 AUTHOR: Michael D. Garris
29 DATE: 05/11/1999
30 UPDATED: 03/16/2005 by MDG
31
32 Contains routines responsible for creating and manipulating
33 shape stuctures as part of the NIST Latent Fingerprint System (LFS).
34
35 ***********************************************************************
36 ROUTINES:
37 alloc_shape()
38 free_shape()
39 shape_from_contour()
40 sort_row_on_x()
41 ***********************************************************************/
42
43 #include <stdio.h>
44 #include <stdlib.h>
45 #include <lfs.h>
46
47 /*************************************************************************
48 **************************************************************************
49 #cat: alloc_shape - Allocates and initializes a shape structure given the
50 #cat: the X and Y limits of the shape.
51
52 Input:
53 xmin - left-most x-coord in shape
54 ymin - top-most y-coord in shape
55 xmax - right-most x-coord in shape
56 ymax - bottom-most y-coord in shape
57 Output:
58 oshape - pointer to the allocated & initialized shape structure
59 Return Code:
60 Zero - Shape successfully allocated and initialized
61 Negative - System error
62 **************************************************************************/
alloc_shape(SHAPE ** oshape,const int xmin,const int ymin,const int xmax,const int ymax)63 static int alloc_shape(SHAPE **oshape, const int xmin, const int ymin,
64 const int xmax, const int ymax)
65 {
66 SHAPE *shape;
67 int alloc_rows, alloc_pts;
68 int i, j, y;
69
70 /* Compute allocation parameters. */
71 /* First, compute the number of scanlines spanned by the shape. */
72 alloc_rows = ymax - ymin + 1;
73 /* Second, compute the "maximum" number of contour points possible */
74 /* on a row. Here we are allocating the maximum number of contiguous */
75 /* pixels on each row which will be sufficiently larger than the */
76 /* number of actual contour points. */
77 alloc_pts = xmax - xmin + 1;
78
79 /* Allocate the shape structure. */
80 shape = (SHAPE *)malloc(sizeof(SHAPE));
81 /* If there is an allocation error... */
82 if(shape == (SHAPE *)NULL){
83 fprintf(stderr, "ERROR : alloc_shape : malloc : shape\n");
84 return(-250);
85 }
86
87 /* Allocate the list of row pointers. We now this number will fit */
88 /* the shape exactly. */
89 shape->rows = (ROW **)malloc(alloc_rows * sizeof(ROW *));
90 /* If there is an allocation error... */
91 if(shape->rows == (ROW **)NULL){
92 /* Deallocate memory alloated by this routine to this point. */
93 free(shape);
94 fprintf(stderr, "ERROR : alloc_shape : malloc : shape->rows\n");
95 return(-251);
96 }
97
98 /* Initialize the shape structure's attributes. */
99 shape->ymin = ymin;
100 shape->ymax = ymax;
101 /* The number of allocated rows will be exactly the number of */
102 /* assigned rows for the shape. */
103 shape->alloc = alloc_rows;
104 shape->nrows = alloc_rows;
105
106 /* Foreach row in the shape... */
107 for(i = 0, y = ymin; i < alloc_rows; i++, y++){
108 /* Allocate a row structure and store it in its respective position */
109 /* in the shape structure's list of row pointers. */
110 shape->rows[i] = (ROW *)malloc(sizeof(ROW));
111 /* If there is an allocation error... */
112 if(shape->rows[i] == (ROW *)NULL){
113 /* Deallocate memory alloated by this routine to this point. */
114 for(j = 0; j < i; j++){
115 free(shape->rows[j]->xs);
116 free(shape->rows[j]);
117 }
118 free(shape->rows);
119 free(shape);
120 fprintf(stderr, "ERROR : alloc_shape : malloc : shape->rows[i]\n");
121 return(-252);
122 }
123
124 /* Allocate the current rows list of x-coords. */
125 shape->rows[i]->xs = (int *)malloc(alloc_pts * sizeof(int));
126 /* If there is an allocation error... */
127 if(shape->rows[i]->xs == (int *)NULL){
128 /* Deallocate memory alloated by this routine to this point. */
129 for(j = 0; j < i; j++){
130 free(shape->rows[j]->xs);
131 free(shape->rows[j]);
132 }
133 free(shape->rows[i]);
134 free(shape->rows);
135 free(shape);
136 fprintf(stderr,
137 "ERROR : alloc_shape : malloc : shape->rows[i]->xs\n");
138 return(-253);
139 }
140
141 /* Initialize the current row structure's attributes. */
142 shape->rows[i]->y = y;
143 shape->rows[i]->alloc = alloc_pts;
144 /* There are initially ZERO points assigned to the row. */
145 shape->rows[i]->npts = 0;
146 }
147
148 /* Assign structure to output pointer. */
149 *oshape = shape;
150
151 /* Return normally. */
152 return(0);
153 }
154
155 /*************************************************************************
156 **************************************************************************
157 #cat: free_shape - Deallocates a shape structure and all its allocated
158 #cat: attributes.
159
160 Input:
161 shape - pointer to the shape structure to be deallocated
162 **************************************************************************/
free_shape(SHAPE * shape)163 void free_shape(SHAPE *shape)
164 {
165 int i;
166
167 /* Foreach allocated row in the shape ... */
168 for(i = 0; i < shape->alloc; i++){
169 /* Deallocate the current row's list of x-coords. */
170 free(shape->rows[i]->xs);
171 /* Deallocate the current row structure. */
172 free(shape->rows[i]);
173 }
174
175 /* Deallocate the list of row pointers. */
176 free(shape->rows);
177 /* Deallocate the shape structure. */
178 free(shape);
179 }
180
181 /*************************************************************************
182 **************************************************************************
183 #cat: sort_row_on_x - Takes a row structure and sorts its points left-to-
184 #cat: right on X.
185
186 Input:
187 row - row structure to be sorted
188 Output:
189 row - row structure with points in sorted order
190 **************************************************************************/
sort_row_on_x(ROW * row)191 static void sort_row_on_x(ROW *row)
192 {
193 /* Conduct a simple increasing bubble sort on the x-coords */
194 /* in the given row. A bubble sort is satisfactory as the */
195 /* number of points will be relatively small. */
196 bubble_sort_int_inc(row->xs, row->npts);
197 }
198
199 /*************************************************************************
200 **************************************************************************
201 #cat: shape_from_contour - Converts a contour list that has been determined
202 #cat: to form a complete loop into a shape representation where
203 #cat: the contour points on each contiguous scanline of the shape
204 #cat: are stored in left-to-right order.
205
206 Input:
207 contour_x - x-coord list for loop's contour points
208 contour_y - y-coord list for loop's contour points
209 ncontour - number of points in contour
210 Output:
211 oshape - points to the resulting shape structure
212 Return Code:
213 Zero - shape successfully derived
214 Negative - system error
215 **************************************************************************/
shape_from_contour(SHAPE ** oshape,const int * contour_x,const int * contour_y,const int ncontour)216 int shape_from_contour(SHAPE **oshape, const int *contour_x,
217 const int *contour_y, const int ncontour)
218 {
219 SHAPE *shape;
220 ROW *row;
221 int ret, i, xmin, ymin, xmax, ymax;
222
223 /* Find xmin, ymin, xmax, ymax on contour. */
224 contour_limits(&xmin, &ymin, &xmax, &ymax,
225 contour_x, contour_y, ncontour);
226
227 /* Allocate and initialize a shape structure. */
228 if((ret = alloc_shape(&shape, xmin, ymin, xmax, ymax)))
229 /* If system error, then return error code. */
230 return(ret);
231
232 /* Foreach point on contour ... */
233 for(i = 0; i < ncontour; i++){
234 /* Add point to corresponding row. */
235 /* First set a pointer to the current row. We need to subtract */
236 /* ymin because the rows are indexed relative to the top-most */
237 /* scanline in the shape. */
238 row = shape->rows[contour_y[i]-ymin];
239
240 /* It is possible with complex shapes to reencounter points */
241 /* already visited on a contour, especially at "pinching" points */
242 /* along the contour. So we need to test to see if a point has */
243 /* already been stored in the row. If not in row list already ... */
244 if(in_int_list(contour_x[i], row->xs, row->npts) < 0){
245 /* If row is full ... */
246 if(row->npts >= row->alloc){
247 /* This should never happen becuase we have allocated */
248 /* based on shape bounding limits. */
249 fprintf(stderr,
250 "ERROR : shape_from_contour : row overflow\n");
251 return(-260);
252 }
253 /* Assign the x-coord of the current contour point to the row */
254 /* and bump the row's point counter. All the contour points */
255 /* on the same row share the same y-coord. */
256 row->xs[row->npts++] = contour_x[i];
257 }
258 /* Otherwise, point is already stored in row, so ignore. */
259 }
260
261 /* Foreach row in the shape. */
262 for(i = 0; i < shape->nrows; i++)
263 /* Sort row points increasing on their x-coord. */
264 sort_row_on_x(shape->rows[i]);
265
266 /* Assign shape structure to output pointer. */
267 *oshape = shape;
268
269 /* Return normally. */
270 return(0);
271 }
272
273