Attachment 114321 Details for Bug 89523 – 0001-nbis-add-one-more-step-of-false-minutia-removal.patch

[patch] 0001-nbis-add-one-more-step-of-false-minutia-removal.patch

0001-nbis-add-one-more-step-of-false-minutia-removal.patch (text/plain), 8.67 KB, created by Vasily Khoruzhick on 2015-03-15 13:34:54 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Vasily Khoruzhick

Created: 2015-03-15 13:34:54 UTC

Size: 8.67 KB

patch

obsolete

>From a22f15d9d04da066231af19dbf1e7275204dacae Mon Sep 17 00:00:00 2001
>From: Vasily Khoruzhick <anarsoul@gmail.com>
>Date: Sun, 15 Mar 2015 16:13:32 +0300
>Subject: [PATCH 1/3] nbis: add one more step of false minutia removal
>
>Remove convex hull contour and close points for scanners with small sensor
>size.
>---
> libfprint/Makefile.am               |  3 +-
> libfprint/nbis/include/lfs.h        |  8 ++++
> libfprint/nbis/mindtct/convexhull.c | 66 +++++++++++++++++++++++++++
> libfprint/nbis/mindtct/globals.c    |  4 ++
> libfprint/nbis/mindtct/remove.c     | 90 +++++++++++++++++++++++++++++++++++++
> 5 files changed, 170 insertions(+), 1 deletion(-)
> create mode 100644 libfprint/nbis/mindtct/convexhull.c
>
>diff --git a/libfprint/Makefile.am b/libfprint/Makefile.am
>index b86d0f8..1af1291 100644
>--- a/libfprint/Makefile.am
>+++ b/libfprint/Makefile.am
>@@ -89,7 +89,8 @@ NBIS_SRC = \
> 	nbis/mindtct/ridges.c \
> 	nbis/mindtct/shape.c \
> 	nbis/mindtct/sort.c \
>-	nbis/mindtct/util.c
>+	nbis/mindtct/util.c \
>+	nbis/mindtct/convexhull.c
> 
> libfprint_la_CFLAGS = -fvisibility=hidden -I$(srcdir)/nbis/include $(LIBUSB_CFLAGS) $(GLIB_CFLAGS) $(CRYPTO_CFLAGS) $(AM_CFLAGS)
> libfprint_la_LDFLAGS = -version-info @lt_major@:@lt_revision@:@lt_age@
>diff --git a/libfprint/nbis/include/lfs.h b/libfprint/nbis/include/lfs.h
>index 49aad84..4148f8b 100644
>--- a/libfprint/nbis/include/lfs.h
>+++ b/libfprint/nbis/include/lfs.h
>@@ -236,6 +236,8 @@ typedef struct lfsparms{
>    int    pores_steps_bwd;
>    double pores_min_dist2;
>    double pores_max_ratio;
>+   int    remove_convex_hull_pts;
>+   int    min_ch_distance;
> 
>    /* Ridge Counting Controls */
>    int    max_nbrs;
>@@ -585,6 +587,9 @@ typedef struct lfsparms{
> /* contour points to be considered a pore.                               */
> #define PORES_MAX_RATIO          2.25
> 
>+/* Points which are closer than this distance will be removed */
>+#define CONVEX_HULL_PTS_DISTANCE 10
>+
> 
> /***** RIDGE COUNTING CONSTANTS *****/
> 
>@@ -728,6 +733,9 @@ extern void contour_limits(int *, int *, int *, int *, const int *,
> extern void fix_edge_pixel_pair(int *, int *, int *, int *,
>                      unsigned char *, const int, const int);
> 
>+/* convexhull.c */
>+extern int ch2d(MINUTIA **P, int n);
>+
> /* detect.c */
> extern int get_minutiae(MINUTIAE **, int **, int **, int **,
>                  int **, int **, int *, int *,
>diff --git a/libfprint/nbis/mindtct/convexhull.c b/libfprint/nbis/mindtct/convexhull.c
>new file mode 100644
>index 0000000..a0a0350
>--- /dev/null
>+++ b/libfprint/nbis/mindtct/convexhull.c
>@@ -0,0 +1,66 @@
>+/*
>+ * Ken Clarkson wrote this.  Copyright (c) 1996 by AT&T..
>+ * Permission to use, copy, modify, and distribute this software for any
>+ * purpose without fee is hereby granted, provided that this entire notice
>+ * is included in all copies of any software which is or includes a copy
>+ * or modification of this software and in all copies of the supporting
>+ * documentation for such software.
>+ * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
>+ * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
>+ * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
>+ * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
>+ */
>+
>+#include <stdlib.h>
>+#include <lfs.h>
>+
>+static int ccw(MINUTIA **minutia, int i, int j, int k)
>+{
>+    int a = minutia[i]->x - minutia[j]->x,
>+        b = minutia[i]->y - minutia[j]->y,
>+        c = minutia[k]->x - minutia[j]->x,
>+        d = minutia[k]->y - minutia[j]->y;
>+    return a*d - b*c <= 0;	   /* true if points i, j, k counterclockwise */
>+}
>+
>+
>+static int cmpl(const void *a, const void *b)
>+{
>+    int v;
>+    v = (*(MINUTIA **)a)->x - (*(MINUTIA **)b)->x;
>+    if (v>0) return 1;
>+    if (v<0) return -1;
>+
>+    v = (*(MINUTIA **)b)->y - (*(MINUTIA **)a)->y;
>+    if (v>0) return 1;
>+    if (v<0) return -1;
>+
>+    return 0;
>+}
>+
>+static int cmph(const void *a, const void *b)
>+{
>+    return cmpl(b, a);
>+}
>+
>+static int make_chain(MINUTIA ** V, int n, int (*cmp)(const void*, const void*))
>+{
>+    int i, j, s = 1;
>+    MINUTIA *t;
>+
>+    qsort(V, n, sizeof(MINUTIA *), cmp);
>+    for (i=2; i<n; i++) {
>+        for (j=s; j>=1 && ccw(V, i, j, j-1); j--){}
>+        s = j+1;
>+        t = V[s]; V[s] = V[i]; V[i] = t;
>+    }
>+    return s;
>+}
>+
>+int ch2d(MINUTIA **P, int n)
>+{
>+    int u = make_chain(P, n, cmpl);         /* make lower hull */
>+    if (!n) return 0;
>+    P[n] = P[0];
>+    return u+make_chain(P+u, n-u+1, cmph);  /* make upper hull */
>+}
>diff --git a/libfprint/nbis/mindtct/globals.c b/libfprint/nbis/mindtct/globals.c
>index da85aab..463361a 100644
>--- a/libfprint/nbis/mindtct/globals.c
>+++ b/libfprint/nbis/mindtct/globals.c
>@@ -129,6 +129,8 @@ LFSPARMS g_lfsparms = {
>    PORES_STEPS_BWD,
>    PORES_MIN_DIST2,
>    PORES_MAX_RATIO,
>+   FALSE, /* not removing convex hull points by default */
>+   CONVEX_HULL_PTS_DISTANCE,
> 
>    /* Ridge Counting Controls */
>    MAX_NBRS,
>@@ -213,6 +215,8 @@ LFSPARMS g_lfsparms_V2 = {
>    PORES_STEPS_BWD,
>    PORES_MIN_DIST2,
>    PORES_MAX_RATIO,
>+   FALSE, /* not removing convex hull points by default */
>+   CONVEX_HULL_PTS_DISTANCE,
> 
>    /* Ridge Counting Controls */
>    MAX_NBRS,
>diff --git a/libfprint/nbis/mindtct/remove.c b/libfprint/nbis/mindtct/remove.c
>index 029a0bc..949425e 100644
>--- a/libfprint/nbis/mindtct/remove.c
>+++ b/libfprint/nbis/mindtct/remove.c
>@@ -1350,6 +1350,91 @@ static int remove_overlaps(MINUTIAE *minutiae,
>    return(0);
> }
> 
>+
>+/*************************************************************************
>+**************************************************************************
>+#cat: remove_convex_hull_pts - Takes a list of true and false minutiae and
>+#cat:                attempts to detect and remove those false minutiae that
>+#cat:                belong to convex hull
>+
>+   Input:
>+      minutiae  - list of true and false 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
>+   Output:
>+      minutiae  - list of pruned minutiae
>+   Return Code:
>+      Zero     - successful completion
>+      Negative - system error
>+**************************************************************************/
>+
>+static int remove_convex_hull_pts(MINUTIAE *minutiae,
>+                    unsigned char *bdata, const int iw, const int ih,
>+                    const LFSPARMS *lfsparms)
>+{
>+    MINUTIA **temp_lst;
>+    int i, j, prev_i, num, ret, *to_remove;
>+
>+    if (!lfsparms->remove_convex_hull_pts)
>+        return(0);
>+
>+    /* extra position is used by algorithm */
>+    temp_lst = calloc(minutiae->num + 1, sizeof(MINUTIA *));
>+    for (i = 0; i < minutiae->num; i++) {
>+        temp_lst[i] = minutiae->list[i];
>+    }
>+
>+    num = ch2d(temp_lst, minutiae->num);
>+    to_remove = calloc(minutiae->num, sizeof(int));
>+    prev_i = num - 1;
>+    for (i = 0; i < num; i++) {
>+        for (j = 0; j < minutiae->num; j++) {
>+            int dist, x0, x1, y0, y1, x, y;
>+            if (to_remove[j])
>+                continue;
>+            if ((minutiae->list[j] == temp_lst[i]) ||
>+                (minutiae->list[j] == temp_lst[prev_i])) {
>+                to_remove[j] = 1;
>+                continue;
>+            }
>+            x0 = temp_lst[prev_i]->x;
>+            x1 = temp_lst[i]->x;
>+            y0 = temp_lst[prev_i]->y;
>+            y1 = temp_lst[i]->y;
>+            x = minutiae->list[j]->x;
>+            y = minutiae->list[j]->x;
>+
>+            dist = ((y0 - y1) * x + (x1 - x0) * y + (x0 * y1 - x1 * y0))
>+                 / (int)sqrt((x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0));
>+            if (dist < 0)
>+                dist = -dist;
>+            if (dist < lfsparms->min_ch_distance) {
>+                to_remove[j] = 1;
>+            }
>+
>+        }
>+        prev_i = i;
>+    }
>+    free(temp_lst);
>+
>+    for (i = minutiae->num - 1; i >= 0; i--) {
>+        /* If the current minutia index is flagged for removal ... */
>+        if (to_remove[i]){
>+            /* Remove the minutia from the minutiae list. */
>+            if((ret = remove_minutia(i, minutiae))){
>+                free(to_remove);
>+                return(ret);
>+            }
>+        }
>+    }
>+
>+    free(to_remove);
>+
>+    return (0);
>+}
>+
> /*************************************************************************
> **************************************************************************
> #cat: remove_pores_V2 - Attempts to detect and remove minutia points located on
>@@ -2104,6 +2189,11 @@ int remove_false_minutia_V2(MINUTIAE *minutiae,
>       return(ret);
>    }
> 
>+   /* 11. Remove convex hull points */
>+   if((ret = remove_convex_hull_pts(minutiae, bdata, iw, ih, lfsparms))) {
>+      return (ret);
>+   }
>+
>    return(0);
> }
> 
>-- 
>2.3.2
>

Actions: View | Splinter Review

Attachments on bug 89523: 114318 | 114319 | 114320 | 114321 | 114324 | 114325 | 128865

Use of freedesktop.org services, including Bugzilla, is subject to our Code of Conduct. How we collect and use information is described in our Privacy Policy.