1 /*
2 * Image management functions for libfprint
3 * Copyright (C) 2007 Daniel Drake <dsd@gentoo.org>
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
14 *
15 * You should have received a copy of the GNU Lesser General Public
16 * License along with this library; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
18 */
19
20 #include <sys/types.h>
21 #include <errno.h>
22 #include <stdio.h>
23 #include <string.h>
24
25 #include <glib.h>
26
27 #include "fp_internal.h"
28 #include "nbis/include/bozorth.h"
29 #include "nbis/include/lfs.h"
30
31 /** @defgroup img Image operations
32 * libfprint offers several ways of retrieving images from imaging devices,
33 * one example being the fp_dev_img_capture() function. The functions
34 * documented below allow you to work with such images.
35 *
36 * \section img_fmt Image format
37 * All images are represented as 8-bit greyscale data.
38 *
39 * \section img_std Image standardization
40 * In some contexts, images you are provided through libfprint are raw images
41 * from the hardware. The orientation of these varies from device-to-device,
42 * as does the color scheme (black-on-white or white-on-black?). libfprint
43 * provides the fp_img_standardize function to convert images into standard
44 * form, which is defined to be: finger flesh as black on white surroundings,
45 * natural upright orientation.
46 */
47
fpi_img_new(size_t length)48 struct fp_img *fpi_img_new(size_t length)
49 {
50 struct fp_img *img = g_malloc0(sizeof(*img) + length);
51 fp_dbg("length=%zd", length);
52 img->length = length;
53 return img;
54 }
55
fpi_img_new_for_imgdev(struct fp_img_dev * imgdev)56 struct fp_img *fpi_img_new_for_imgdev(struct fp_img_dev *imgdev)
57 {
58 struct fp_img_driver *imgdrv = fpi_driver_to_img_driver(imgdev->dev->drv);
59 int width = imgdrv->img_width;
60 int height = imgdrv->img_height;
61 struct fp_img *img = fpi_img_new(width * height);
62 img->width = width;
63 img->height = height;
64 return img;
65 }
66
fpi_img_is_sane(struct fp_img * img)67 gboolean fpi_img_is_sane(struct fp_img *img)
68 {
69 /* basic checks */
70 if (!img->length || !img->width || !img->height)
71 return FALSE;
72
73 /* buffer is big enough? */
74 if ((img->length * img->height) < img->length)
75 return FALSE;
76
77 return TRUE;
78 }
79
fpi_img_resize(struct fp_img * img,size_t newsize)80 struct fp_img *fpi_img_resize(struct fp_img *img, size_t newsize)
81 {
82 return g_realloc(img, sizeof(*img) + newsize);
83 }
84
85 /** \ingroup img
86 * Frees an image. Must be called when you are finished working with an image.
87 * \param img the image to destroy. If NULL, function simply returns.
88 */
fp_img_free(struct fp_img * img)89 API_EXPORTED void fp_img_free(struct fp_img *img)
90 {
91 if (!img)
92 return;
93
94 if (img->minutiae)
95 free_minutiae(img->minutiae);
96 if (img->binarized)
97 free(img->binarized);
98 g_free(img);
99 }
100
101 /** \ingroup img
102 * Gets the pixel height of an image.
103 * \param img an image
104 * \returns the height of the image
105 */
fp_img_get_height(struct fp_img * img)106 API_EXPORTED int fp_img_get_height(struct fp_img *img)
107 {
108 return img->height;
109 }
110
111 /** \ingroup img
112 * Gets the pixel width of an image.
113 * \param img an image
114 * \returns the width of the image
115 */
fp_img_get_width(struct fp_img * img)116 API_EXPORTED int fp_img_get_width(struct fp_img *img)
117 {
118 return img->width;
119 }
120
121 /** \ingroup img
122 * Gets the greyscale data for an image. This data must not be modified or
123 * freed, and must not be used after fp_img_free() has been called.
124 * \param img an image
125 * \returns a pointer to libfprint's internal data for the image
126 */
fp_img_get_data(struct fp_img * img)127 API_EXPORTED unsigned char *fp_img_get_data(struct fp_img *img)
128 {
129 return img->data;
130 }
131
132 /** \ingroup img
133 * A quick convenience function to save an image to a file in
134 * <a href="http://netpbm.sourceforge.net/doc/pgm.html">PGM format</a>.
135 * \param img the image to save
136 * \param path the path to save the image. Existing files will be overwritten.
137 * \returns 0 on success, non-zero on error.
138 */
fp_img_save_to_file(struct fp_img * img,char * path)139 API_EXPORTED int fp_img_save_to_file(struct fp_img *img, char *path)
140 {
141 FILE *fd = fopen(path, "w");
142 size_t write_size = img->width * img->height;
143 int r;
144
145 if (!fd) {
146 fp_dbg("could not open '%s' for writing: %d", path, errno);
147 return -errno;
148 }
149
150 r = fprintf(fd, "P5 %d %d 255\n", img->width, img->height);
151 if (r < 0) {
152 fp_err("pgm header write failed, error %d", r);
153 return r;
154 }
155
156 r = fwrite(img->data, 1, write_size, fd);
157 if (r < write_size) {
158 fp_err("short write (%d)", r);
159 return -EIO;
160 }
161
162 fclose(fd);
163 fp_dbg("written to '%s'", path);
164 return 0;
165 }
166
vflip(struct fp_img * img)167 static void vflip(struct fp_img *img)
168 {
169 int width = img->width;
170 int data_len = img->width * img->height;
171 unsigned char rowbuf[width];
172 int i;
173
174 for (i = 0; i < img->height / 2; i++) {
175 int offset = i * width;
176 int swap_offset = data_len - (width * (i + 1));
177
178 /* copy top row into buffer */
179 memcpy(rowbuf, img->data + offset, width);
180
181 /* copy lower row over upper row */
182 memcpy(img->data + offset, img->data + swap_offset, width);
183
184 /* copy buffer over lower row */
185 memcpy(img->data + swap_offset, rowbuf, width);
186 }
187 }
188
hflip(struct fp_img * img)189 static void hflip(struct fp_img *img)
190 {
191 int width = img->width;
192 unsigned char rowbuf[width];
193 int i, j;
194
195 for (i = 0; i < img->height; i++) {
196 int offset = i * width;
197
198 memcpy(rowbuf, img->data + offset, width);
199 for (j = 0; j < width; j++)
200 img->data[offset + j] = rowbuf[width - j - 1];
201 }
202 }
203
invert_colors(struct fp_img * img)204 static void invert_colors(struct fp_img *img)
205 {
206 int data_len = img->width * img->height;
207 int i;
208 for (i = 0; i < data_len; i++)
209 img->data[i] = 0xff - img->data[i];
210 }
211
212 /** \ingroup img
213 * \ref img_std "Standardizes" an image by normalizing its orientation, colors,
214 * etc. It is safe to call this multiple times on an image, libfprint keeps
215 * track of the work it needs to do to make an image standard and will not
216 * perform these operations more than once for a given image.
217 * \param img the image to standardize
218 */
fp_img_standardize(struct fp_img * img)219 API_EXPORTED void fp_img_standardize(struct fp_img *img)
220 {
221 if (img->flags & FP_IMG_V_FLIPPED) {
222 vflip(img);
223 img->flags &= ~FP_IMG_V_FLIPPED;
224 }
225 if (img->flags & FP_IMG_H_FLIPPED) {
226 hflip(img);
227 img->flags &= ~FP_IMG_H_FLIPPED;
228 }
229 if (img->flags & FP_IMG_COLORS_INVERTED) {
230 invert_colors(img);
231 img->flags &= ~FP_IMG_COLORS_INVERTED;
232 }
233 }
234
235 /* Based on write_minutiae_XYTQ and bz_load */
minutiae_to_xyt(struct fp_minutiae * minutiae,int bwidth,int bheight,unsigned char * buf)236 static void minutiae_to_xyt(struct fp_minutiae *minutiae, int bwidth,
237 int bheight, unsigned char *buf)
238 {
239 int i;
240 struct fp_minutia *minutia;
241 struct minutiae_struct c[MAX_FILE_MINUTIAE];
242 struct xyt_struct *xyt = (struct xyt_struct *) buf;
243
244 /* FIXME: only considers first 150 minutiae (MAX_FILE_MINUTIAE) */
245 /* nist does weird stuff with 150 vs 1000 limits */
246 int nmin = min(minutiae->num, MAX_FILE_MINUTIAE);
247
248 for (i = 0; i < nmin; i++){
249 minutia = minutiae->list[i];
250
251 lfs2nist_minutia_XYT(&c[i].col[0], &c[i].col[1], &c[i].col[2],
252 minutia, bwidth, bheight);
253 c[i].col[3] = sround(minutia->reliability * 100.0);
254
255 if (c[i].col[2] > 180)
256 c[i].col[2] -= 360;
257 }
258
259 qsort((void *) &c, (size_t) nmin, sizeof(struct minutiae_struct),
260 sort_x_y);
261
262 for (i = 0; i < nmin; i++) {
263 xyt->xcol[i] = c[i].col[0];
264 xyt->ycol[i] = c[i].col[1];
265 xyt->thetacol[i] = c[i].col[2];
266 }
267 xyt->nrows = nmin;
268 }
269
fpi_img_detect_minutiae(struct fp_img * img)270 int fpi_img_detect_minutiae(struct fp_img *img)
271 {
272 struct fp_minutiae *minutiae;
273 int r;
274 int *direction_map, *low_contrast_map, *low_flow_map;
275 int *high_curve_map, *quality_map;
276 int map_w, map_h;
277 unsigned char *bdata;
278 int bw, bh, bd;
279 GTimer *timer;
280
281 if (img->flags & FP_IMG_STANDARDIZATION_FLAGS) {
282 fp_err("cant detect minutiae for non-standardized image");
283 return -EINVAL;
284 }
285
286 /* Remove perimeter points from partial image */
287 g_lfsparms_V2.remove_perimeter_pts = img->flags & FP_IMG_PARTIAL ? TRUE : FALSE;
288
289 /* 25.4 mm per inch */
290 timer = g_timer_new();
291 r = get_minutiae(&minutiae, &quality_map, &direction_map,
292 &low_contrast_map, &low_flow_map, &high_curve_map,
293 &map_w, &map_h, &bdata, &bw, &bh, &bd,
294 img->data, img->width, img->height, 8,
295 DEFAULT_PPI / (double)25.4, &g_lfsparms_V2);
296 g_timer_stop(timer);
297 fp_dbg("minutiae scan completed in %f secs", g_timer_elapsed(timer, NULL));
298 g_timer_destroy(timer);
299 if (r) {
300 fp_err("get minutiae failed, code %d", r);
301 return r;
302 }
303 fp_dbg("detected %d minutiae", minutiae->num);
304 img->minutiae = minutiae;
305 img->binarized = bdata;
306
307 free(quality_map);
308 free(direction_map);
309 free(low_contrast_map);
310 free(low_flow_map);
311 free(high_curve_map);
312 return minutiae->num;
313 }
314
fpi_img_to_print_data(struct fp_img_dev * imgdev,struct fp_img * img,struct fp_print_data ** ret)315 int fpi_img_to_print_data(struct fp_img_dev *imgdev, struct fp_img *img,
316 struct fp_print_data **ret)
317 {
318 struct fp_print_data *print;
319 struct fp_print_data_item *item;
320 int r;
321
322 if (!img->minutiae) {
323 r = fpi_img_detect_minutiae(img);
324 if (r < 0)
325 return r;
326 if (!img->minutiae) {
327 fp_err("no minutiae after successful detection?");
328 return -ENOENT;
329 }
330 }
331
332 /* FIXME: space is wasted if we dont hit the max minutiae count. would
333 * be good to make this dynamic. */
334 print = fpi_print_data_new(imgdev->dev);
335 item = fpi_print_data_item_new(sizeof(struct xyt_struct));
336 print->type = PRINT_DATA_NBIS_MINUTIAE;
337 minutiae_to_xyt(img->minutiae, img->width, img->height, item->data);
338 print->prints = g_slist_prepend(print->prints, item);
339
340 /* FIXME: the print buffer at this point is endian-specific, and will
341 * only work when loaded onto machines with identical endianness. not good!
342 * data format should be platform-independent. */
343 *ret = print;
344
345 return 0;
346 }
347
fpi_img_compare_print_data(struct fp_print_data * enrolled_print,struct fp_print_data * new_print)348 int fpi_img_compare_print_data(struct fp_print_data *enrolled_print,
349 struct fp_print_data *new_print)
350 {
351 int score, max_score = 0, probe_len;
352 struct xyt_struct *pstruct = NULL;
353 struct xyt_struct *gstruct = NULL;
354 struct fp_print_data_item *data_item;
355 GSList *list_item;
356
357 if (enrolled_print->type != PRINT_DATA_NBIS_MINUTIAE ||
358 new_print->type != PRINT_DATA_NBIS_MINUTIAE) {
359 fp_err("invalid print format");
360 return -EINVAL;
361 }
362
363 if (g_slist_length(new_print->prints) != 1) {
364 fp_err("new_print contains more than one sample, is it enrolled print?");
365 return -EINVAL;
366 }
367
368 data_item = new_print->prints->data;
369 pstruct = (struct xyt_struct *)data_item->data;
370
371 probe_len = bozorth_probe_init(pstruct);
372 list_item = enrolled_print->prints;
373 do {
374 data_item = list_item->data;
375 gstruct = (struct xyt_struct *)data_item->data;
376 score = bozorth_to_gallery(probe_len, pstruct, gstruct);
377 fp_dbg("score %d", score);
378 max_score = max(score, max_score);
379 list_item = g_slist_next(list_item);
380 } while (list_item);
381
382 return max_score;
383 }
384
fpi_img_compare_print_data_to_gallery(struct fp_print_data * print,struct fp_print_data ** gallery,int match_threshold,size_t * match_offset)385 int fpi_img_compare_print_data_to_gallery(struct fp_print_data *print,
386 struct fp_print_data **gallery, int match_threshold, size_t *match_offset)
387 {
388 struct xyt_struct *pstruct;
389 struct xyt_struct *gstruct;
390 struct fp_print_data *gallery_print;
391 struct fp_print_data_item *data_item;
392 int probe_len;
393 size_t i = 0;
394 int r;
395 GSList *list_item;
396
397 if (g_slist_length(print->prints) != 1) {
398 fp_err("new_print contains more than one sample, is it enrolled print?");
399 return -EINVAL;
400 }
401
402 data_item = print->prints->data;
403 pstruct = (struct xyt_struct *)data_item->data;
404
405 probe_len = bozorth_probe_init(pstruct);
406 while ((gallery_print = gallery[i++])) {
407 list_item = gallery_print->prints;
408 do {
409 data_item = list_item->data;
410 gstruct = (struct xyt_struct *)data_item->data;
411 r = bozorth_to_gallery(probe_len, pstruct, gstruct);
412 if (r >= match_threshold) {
413 *match_offset = i - 1;
414 return FP_VERIFY_MATCH;
415 }
416 list_item = g_slist_next(list_item);
417 } while (list_item);
418 }
419 return FP_VERIFY_NO_MATCH;
420 }
421
422 /** \ingroup img
423 * Get a binarized form of a standardized scanned image. This is where the
424 * fingerprint image has been "enhanced" and is a set of pure black ridges
425 * on a pure white background. Internally, image processing happens on top
426 * of the binarized image.
427 *
428 * The image must have been \ref img_std "standardized" otherwise this function
429 * will fail.
430 *
431 * It is safe to binarize an image and free the original while continuing
432 * to use the binarized version.
433 *
434 * You cannot binarize an image twice.
435 *
436 * \param img a standardized image
437 * \returns a new image representing the binarized form of the original, or
438 * NULL on error. Must be freed with fp_img_free() after use.
439 */
fp_img_binarize(struct fp_img * img)440 API_EXPORTED struct fp_img *fp_img_binarize(struct fp_img *img)
441 {
442 struct fp_img *ret;
443 int height = img->height;
444 int width = img->width;
445 int imgsize = height * width;
446
447 if (img->flags & FP_IMG_BINARIZED_FORM) {
448 fp_err("image already binarized");
449 return NULL;
450 }
451
452 if (!img->binarized) {
453 int r = fpi_img_detect_minutiae(img);
454 if (r < 0)
455 return NULL;
456 if (!img->binarized) {
457 fp_err("no minutiae after successful detection?");
458 return NULL;
459 }
460 }
461
462 ret = fpi_img_new(imgsize);
463 ret->flags |= FP_IMG_BINARIZED_FORM;
464 ret->width = width;
465 ret->height = height;
466 memcpy(ret->data, img->binarized, imgsize);
467 return ret;
468 }
469
470 /** \ingroup img
471 * Get a list of minutiae detected in an image. A minutia point is a feature
472 * detected on a fingerprint, typically where ridges end or split.
473 * libfprint's image processing code relies upon comparing sets of minutiae,
474 * so accurate placement of minutia points is critical for good imaging
475 * performance.
476 *
477 * The image must have been \ref img_std "standardized" otherwise this function
478 * will fail.
479 *
480 * You cannot pass a binarized image to this function. Instead, pass the
481 * original image.
482 *
483 * Returns a list of pointers to minutiae, where the list is of length
484 * indicated in the nr_minutiae output parameter. The returned list is only
485 * valid while the parent image has not been freed, and the minutiae data
486 * must not be modified or freed.
487 *
488 * \param img a standardized image
489 * \param nr_minutiae an output location to store minutiae list length
490 * \returns a list of minutiae points. Must not be modified or freed.
491 */
fp_img_get_minutiae(struct fp_img * img,int * nr_minutiae)492 API_EXPORTED struct fp_minutia **fp_img_get_minutiae(struct fp_img *img,
493 int *nr_minutiae)
494 {
495 if (img->flags & FP_IMG_BINARIZED_FORM) {
496 fp_err("image is binarized");
497 return NULL;
498 }
499
500 if (!img->minutiae) {
501 int r = fpi_img_detect_minutiae(img);
502 if (r < 0)
503 return NULL;
504 if (!img->minutiae) {
505 fp_err("no minutiae after successful detection?");
506 return NULL;
507 }
508 }
509
510 *nr_minutiae = img->minutiae->num;
511 return img->minutiae->list;
512 }
513
514 /* Calculate squared standand deviation */
fpi_std_sq_dev(const unsigned char * buf,int size)515 int fpi_std_sq_dev(const unsigned char *buf, int size)
516 {
517 int res = 0, mean = 0, i;
518
519 if (size > (INT_MAX / 65536)) {
520 fp_err("%s: we might get an overflow!", __func__);
521 return -EOVERFLOW;
522 }
523
524 for (i = 0; i < size; i++)
525 mean += buf[i];
526
527 mean /= size;
528
529 for (i = 0; i < size; i++) {
530 int dev = (int)buf[i] - mean;
531 res += dev*dev;
532 }
533
534 return res / size;
535 }
536
537 /* Calculate normalized mean square difference of two lines */
fpi_mean_sq_diff_norm(unsigned char * buf1,unsigned char * buf2,int size)538 int fpi_mean_sq_diff_norm(unsigned char *buf1, unsigned char *buf2, int size)
539 {
540 int res = 0, i;
541 for (i = 0; i < size; i++) {
542 int dev = (int)buf1[i] - (int)buf2[i];
543 res += dev * dev;
544 }
545
546 return res / size;
547 }
548