841 lines
33 KiB
C
841 lines
33 KiB
C
/*******************************************************************************
|
|
|
|
License:
|
|
This software and/or related materials was developed at the National Institute
|
|
of Standards and Technology (NIST) by employees of the Federal Government
|
|
in the course of their official duties. Pursuant to title 17 Section 105
|
|
of the United States Code, this software is not subject to copyright
|
|
protection and is in the public domain.
|
|
|
|
This software and/or related materials have been determined to be not subject
|
|
to the EAR (see Part 734.3 of the EAR for exact details) because it is
|
|
a publicly available technology and software, and is freely distributed
|
|
to any interested party with no licensing requirements. Therefore, it is
|
|
permissible to distribute this software as a free download from the internet.
|
|
|
|
Disclaimer:
|
|
This software and/or related materials was developed to promote biometric
|
|
standards and biometric technology testing for the Federal Government
|
|
in accordance with the USA PATRIOT Act and the Enhanced Border Security
|
|
and Visa Entry Reform Act. Specific hardware and software products identified
|
|
in this software were used in order to perform the software development.
|
|
In no case does such identification imply recommendation or endorsement
|
|
by the National Institute of Standards and Technology, nor does it imply that
|
|
the products and equipment identified are necessarily the best available
|
|
for the purpose.
|
|
|
|
This software and/or related materials are provided "AS-IS" without warranty
|
|
of any kind including NO WARRANTY OF PERFORMANCE, MERCHANTABILITY,
|
|
NO WARRANTY OF NON-INFRINGEMENT OF ANY 3RD PARTY INTELLECTUAL PROPERTY
|
|
or FITNESS FOR A PARTICULAR PURPOSE or for any purpose whatsoever, for the
|
|
licensed product, however used. In no event shall NIST be liable for any
|
|
damages and/or costs, including but not limited to incidental or consequential
|
|
damages of any kind, including economic damage or injury to property and lost
|
|
profits, regardless of whether NIST shall be advised, have reason to know,
|
|
or in fact shall know of the possibility.
|
|
|
|
By using this software, you agree to bear all risk relating to quality,
|
|
use and performance of the software and/or related materials. You agree
|
|
to hold the Government harmless from any claim arising from your use
|
|
of the software.
|
|
|
|
*******************************************************************************/
|
|
|
|
|
|
/***********************************************************************
|
|
LIBRARY: LFS - NIST Latent Fingerprint System
|
|
|
|
FILE: RIDGES.C
|
|
AUTHOR: Michael D. Garris
|
|
DATE: 08/09/1999
|
|
UPDATED: 03/16/2005 by MDG
|
|
|
|
Contains routines responsible for locating nearest minutia
|
|
neighbors and counting intervening ridges as part of the
|
|
NIST Latent Fingerprint System (LFS).
|
|
|
|
***********************************************************************
|
|
ROUTINES:
|
|
count_minutiae_ridges()
|
|
count_minutia_ridges()
|
|
find_neighbors()
|
|
update_nbr_dists()
|
|
insert_neighbor()
|
|
sort_neighbors()
|
|
ridge_count()
|
|
find_transition()
|
|
validate_ridge_crossing()
|
|
***********************************************************************/
|
|
|
|
#include <stdio.h>
|
|
#include <lfs.h>
|
|
#include <log.h>
|
|
|
|
/*************************************************************************
|
|
**************************************************************************
|
|
#cat: count_minutiae_ridges - Takes a list of minutiae, and for each one,
|
|
#cat: determines its closest neighbors and counts the number
|
|
#cat: of interveining ridges between the minutia point and
|
|
#cat: each of its neighbors.
|
|
|
|
Input:
|
|
minutiae - list of minutiae
|
|
bdata - binary image data (0==while & 1==black)
|
|
iw - width (in pixels) of image
|
|
ih - height (in pixels) of image
|
|
lfsparms - parameters and thresholds for controlling LFS
|
|
Output:
|
|
minutiae - list of minutiae augmented with neighbors and ridge counts
|
|
Return Code:
|
|
Zero - successful completion
|
|
Negative - system error
|
|
**************************************************************************/
|
|
int count_minutiae_ridges(MINUTIAE *minutiae,
|
|
unsigned char *bdata, const int iw, const int ih,
|
|
const LFSPARMS *lfsparms)
|
|
{
|
|
int ret;
|
|
int i;
|
|
|
|
print2log("\nFINDING NBRS AND COUNTING RIDGES:\n");
|
|
|
|
/* Sort minutia points on x then y (column-oriented). */
|
|
if((ret = sort_minutiae_x_y(minutiae, iw, ih))){
|
|
return(ret);
|
|
}
|
|
|
|
/* Remove any duplicate minutia points from the list. */
|
|
if((ret = rm_dup_minutiae(minutiae))){
|
|
return(ret);
|
|
}
|
|
|
|
/* Foreach remaining sorted minutia in list ... */
|
|
for(i = 0; i < minutiae->num-1; i++){
|
|
/* Located neighbors and count number of ridges in between. */
|
|
/* NOTE: neighbor and ridge count results are stored in */
|
|
/* minutiae->list[i]. */
|
|
if((ret = count_minutia_ridges(i, minutiae, bdata, iw, ih, lfsparms))){
|
|
return(ret);
|
|
}
|
|
}
|
|
|
|
/* Return normally. */
|
|
return(0);
|
|
}
|
|
|
|
/*************************************************************************
|
|
**************************************************************************
|
|
#cat: count_minutia_ridges - Takes a minutia, and determines its closest
|
|
#cat: neighbors and counts the number of interveining ridges
|
|
#cat: between the minutia point and each of its neighbors.
|
|
|
|
Input:
|
|
minutia - input minutia
|
|
bdata - binary image data (0==while & 1==black)
|
|
iw - width (in pixels) of image
|
|
ih - height (in pixels) of image
|
|
lfsparms - parameters and thresholds for controlling LFS
|
|
Output:
|
|
minutiae - minutia augmented with neighbors and ridge counts
|
|
Return Code:
|
|
Zero - successful completion
|
|
Negative - system error
|
|
**************************************************************************/
|
|
int count_minutia_ridges(const int first, MINUTIAE *minutiae,
|
|
unsigned char *bdata, const int iw, const int ih,
|
|
const LFSPARMS *lfsparms)
|
|
{
|
|
int i, ret, *nbr_list, *nbr_nridges, nnbrs;
|
|
|
|
g_assert (lfsparms->max_nbrs > 0);
|
|
|
|
/* Find up to the maximum number of qualifying neighbors. */
|
|
nbr_list = NULL;
|
|
if((ret = find_neighbors(&nbr_list, &nnbrs, lfsparms->max_nbrs,
|
|
first, minutiae))){
|
|
if (nbr_list != NULL)
|
|
g_free(nbr_list);
|
|
return(ret);
|
|
}
|
|
|
|
print2log("NBRS FOUND: %d,%d = %d\n", minutiae->list[first]->x,
|
|
minutiae->list[first]->y, nnbrs);
|
|
|
|
/* If no neighors found ... */
|
|
if(nnbrs == 0){
|
|
/* Then no list returned and no ridges to count. */
|
|
return(0);
|
|
}
|
|
|
|
/* Sort neighbors on delta dirs. */
|
|
if((ret = sort_neighbors(nbr_list, nnbrs, first, minutiae))){
|
|
g_free(nbr_list);
|
|
return(ret);
|
|
}
|
|
|
|
/* Count ridges between first and neighbors. */
|
|
/* List of ridge counts, one for each neighbor stored. */
|
|
nbr_nridges = (int *)g_malloc(nnbrs * sizeof(int));
|
|
|
|
/* Foreach neighbor found and sorted in list ... */
|
|
for(i = 0; i < nnbrs; i++){
|
|
/* Count the ridges between the primary minutia and the neighbor. */
|
|
ret = ridge_count(first, nbr_list[i], minutiae, bdata, iw, ih, lfsparms);
|
|
/* If system error ... */
|
|
if(ret < 0){
|
|
/* Deallocate working memories. */
|
|
g_free(nbr_list);
|
|
g_free(nbr_nridges);
|
|
/* Return error code. */
|
|
return(ret);
|
|
}
|
|
|
|
/* Otherwise, ridge count successful, so store ridge count to list. */
|
|
nbr_nridges[i] = ret;
|
|
}
|
|
|
|
/* Assign neighbor indices and ridge counts to primary minutia. */
|
|
minutiae->list[first]->nbrs = nbr_list;
|
|
minutiae->list[first]->ridge_counts = nbr_nridges;
|
|
minutiae->list[first]->num_nbrs = nnbrs;
|
|
|
|
/* Return normally. */
|
|
return(0);
|
|
}
|
|
|
|
/*************************************************************************
|
|
**************************************************************************
|
|
#cat: find_neighbors - Takes a primary minutia and a list of all minutiae
|
|
#cat: and locates a specified maximum number of closest neighbors
|
|
#cat: to the primary point. Neighbors are searched, starting
|
|
#cat: in the same pixel column, below, the primary point and then
|
|
#cat: along consecutive and complete pixel columns in the image
|
|
#cat: to the right of the primary point.
|
|
|
|
Input:
|
|
max_nbrs - maximum number of closest neighbors to be returned
|
|
first - index of the primary minutia point
|
|
minutiae - list of minutiae
|
|
Output:
|
|
onbr_list - points to list of detected closest neighbors
|
|
onnbrs - points to number of neighbors returned
|
|
Return Code:
|
|
Zero - successful completion
|
|
Negative - system error
|
|
**************************************************************************/
|
|
int find_neighbors(int **onbr_list, int *onnbrs, const int max_nbrs,
|
|
const int first, MINUTIAE *minutiae)
|
|
{
|
|
int ret, second, last_nbr;
|
|
MINUTIA *minutia1, *minutia2;
|
|
int *nbr_list, nnbrs;
|
|
double *nbr_sqr_dists, xdist, xdist2;
|
|
|
|
/* Allocate list of neighbor minutiae indices. */
|
|
nbr_list = (int *)g_malloc(max_nbrs * sizeof(int));
|
|
|
|
/* Allocate list of squared euclidean distances between neighbors */
|
|
/* and current primary minutia point. */
|
|
nbr_sqr_dists = (double *)g_malloc(max_nbrs * sizeof(double));
|
|
|
|
/* Initialize number of stored neighbors to 0. */
|
|
nnbrs = 0;
|
|
/* Assign secondary to one passed current primary minutia. */
|
|
second = first + 1;
|
|
/* Compute location of maximum last stored neighbor. */
|
|
last_nbr = max_nbrs - 1;
|
|
|
|
/* While minutia (in sorted order) still remian for processing ... */
|
|
/* NOTE: The minutia in the input list have been sorted on X and */
|
|
/* then on Y. So, the neighbors are selected according to those */
|
|
/* that lie below the primary minutia in the same pixel column and */
|
|
/* then subsequently those that lie in complete pixel columns to */
|
|
/* the right of the primary minutia. */
|
|
while(second < minutiae->num){
|
|
/* Assign temporary minutia pointers. */
|
|
minutia1 = minutiae->list[first];
|
|
minutia2 = minutiae->list[second];
|
|
|
|
/* Compute squared distance between minutiae along x-axis. */
|
|
xdist = minutia2->x - minutia1->x;
|
|
xdist2 = xdist * xdist;
|
|
|
|
/* If the neighbor lists are not full OR the x-distance to current */
|
|
/* secondary is smaller than maximum neighbor distance stored ... */
|
|
if((nnbrs < max_nbrs) ||
|
|
(xdist2 < nbr_sqr_dists[last_nbr])){
|
|
/* Append or insert the new neighbor into the neighbor lists. */
|
|
if((ret = update_nbr_dists(nbr_list, nbr_sqr_dists, &nnbrs, max_nbrs,
|
|
first, second, minutiae))){
|
|
g_free(nbr_sqr_dists);
|
|
g_free(nbr_list);
|
|
return(ret);
|
|
}
|
|
}
|
|
/* Otherwise, if the neighbor lists is full AND the x-distance */
|
|
/* to current secondary is larger than maximum neighbor distance */
|
|
/* stored ... */
|
|
else
|
|
/* So, stop searching for more neighbors. */
|
|
break;
|
|
|
|
/* Bump to next secondary minutia. */
|
|
second++;
|
|
}
|
|
|
|
/* Deallocate working memory. */
|
|
g_free(nbr_sqr_dists);
|
|
|
|
/* If no neighbors found ... */
|
|
if(nnbrs == 0){
|
|
/* Deallocate the neighbor list. */
|
|
g_free(nbr_list);
|
|
*onnbrs = 0;
|
|
}
|
|
/* Otherwise, assign neighbors to output pointer. */
|
|
else{
|
|
*onbr_list = nbr_list;
|
|
*onnbrs = nnbrs;
|
|
}
|
|
|
|
/* Return normally. */
|
|
return(0);
|
|
}
|
|
|
|
/*************************************************************************
|
|
**************************************************************************
|
|
#cat: update_nbr_dists - Takes the current list of neighbors along with a
|
|
#cat: primary minutia and a potential new neighbor, and
|
|
#cat: determines if the new neighbor is sufficiently close
|
|
#cat: to be added to the list of nearest neighbors. If added,
|
|
#cat: it is placed in the list in its proper order based on
|
|
#cat: squared distance to the primary point.
|
|
|
|
Input:
|
|
nbr_list - current list of nearest neighbor minutia indices
|
|
nbr_sqr_dists - corresponding squared euclidean distance of each
|
|
neighbor to the primary minutia point
|
|
nnbrs - number of neighbors currently in the list
|
|
max_nbrs - maximum number of closest neighbors to be returned
|
|
first - index of the primary minutia point
|
|
second - index of the secondary (new neighbor) point
|
|
minutiae - list of minutiae
|
|
Output:
|
|
nbr_list - updated list of nearest neighbor indices
|
|
nbr_sqr_dists - updated list of nearest neighbor distances
|
|
nnbrs - number of neighbors in the update lists
|
|
Return Code:
|
|
Zero - successful completion
|
|
Negative - system error
|
|
**************************************************************************/
|
|
int update_nbr_dists(int *nbr_list, double *nbr_sqr_dists,
|
|
int *nnbrs, const int max_nbrs,
|
|
const int first, const int second, MINUTIAE *minutiae)
|
|
{
|
|
double dist2;
|
|
MINUTIA *minutia1, *minutia2;
|
|
int pos, last_nbr;
|
|
|
|
/* Compute position of maximum last neighbor stored. */
|
|
last_nbr = max_nbrs - 1;
|
|
|
|
/* Assigne temporary minutia pointers. */
|
|
minutia1 = minutiae->list[first];
|
|
minutia2 = minutiae->list[second];
|
|
|
|
/* Compute squared euclidean distance between minutia pair. */
|
|
dist2 = squared_distance(minutia1->x, minutia1->y,
|
|
minutia2->x, minutia2->y);
|
|
|
|
/* If maximum number of neighbors not yet stored in lists OR */
|
|
/* if the squared distance to current secondary is less */
|
|
/* than the largest stored neighbor distance ... */
|
|
if((*nnbrs < max_nbrs) ||
|
|
(dist2 < nbr_sqr_dists[last_nbr])){
|
|
|
|
/* Find insertion point in neighbor lists. */
|
|
pos = find_incr_position_dbl(dist2, nbr_sqr_dists, *nnbrs);
|
|
/* If the position returned is >= maximum list length (this should */
|
|
/* never happen, but just in case) ... */
|
|
if(pos >= max_nbrs){
|
|
fprintf(stderr,
|
|
"ERROR : update_nbr_dists : illegal position for new neighbor\n");
|
|
return(-470);
|
|
}
|
|
/* Insert the new neighbor into the neighbor lists at the */
|
|
/* specified location. */
|
|
if(insert_neighbor(pos, second, dist2,
|
|
nbr_list, nbr_sqr_dists, nnbrs, max_nbrs))
|
|
return(-471);
|
|
|
|
/* Otherwise, neighbor inserted successfully, so return normally. */
|
|
return(0);
|
|
}
|
|
/* Otherwise, the new neighbor is not sufficiently close to be */
|
|
/* added or inserted into the neighbor lists, so ignore the neighbor */
|
|
/* and return normally. */
|
|
else
|
|
return(0);
|
|
|
|
}
|
|
|
|
/*************************************************************************
|
|
**************************************************************************
|
|
#cat: insert_neighbor - Takes a minutia index and its squared distance to a
|
|
#cat: primary minutia point, and inserts them in the specified
|
|
#cat: position of their respective lists, shifting previously
|
|
#cat: stored values down and off the lists as necessary.
|
|
|
|
Input:
|
|
pos - postions where values are to be inserted in lists
|
|
nbr_index - index of minutia being inserted
|
|
nbr_dist2 - squared distance of minutia to its primary point
|
|
nbr_list - current list of nearest neighbor minutia indices
|
|
nbr_sqr_dists - corresponding squared euclidean distance of each
|
|
neighbor to the primary minutia point
|
|
nnbrs - number of neighbors currently in the list
|
|
max_nbrs - maximum number of closest neighbors to be returned
|
|
Output:
|
|
nbr_list - updated list of nearest neighbor indices
|
|
nbr_sqr_dists - updated list of nearest neighbor distances
|
|
nnbrs - number of neighbors in the update lists
|
|
Return Code:
|
|
Zero - successful completion
|
|
Negative - system error
|
|
**************************************************************************/
|
|
int insert_neighbor(const int pos, const int nbr_index, const double nbr_dist2,
|
|
int *nbr_list, double *nbr_sqr_dists,
|
|
int *nnbrs, const int max_nbrs)
|
|
{
|
|
int i;
|
|
|
|
g_assert (pos >= 0);
|
|
|
|
/* If the desired insertion position is beyond one passed the last */
|
|
/* neighbor in the lists OR greater than equal to the maximum ... */
|
|
/* NOTE: pos is zero-oriented while nnbrs and max_nbrs are 1-oriented. */
|
|
if((pos > *nnbrs) ||
|
|
(pos >= max_nbrs)){
|
|
fprintf(stderr,
|
|
"ERROR : insert_neighbor : insertion point exceeds lists\n");
|
|
return(-480);
|
|
}
|
|
|
|
/* If the neighbor lists are NOT full ... */
|
|
if(*nnbrs < max_nbrs){
|
|
/* Then we have room to shift everything down to make room for new */
|
|
/* neighbor and increase the number of neighbors stored by 1. */
|
|
i = *nnbrs-1;
|
|
(*nnbrs)++;
|
|
}
|
|
/* Otherwise, the neighbors lists are full ... */
|
|
else if(*nnbrs == max_nbrs)
|
|
/* So, we must bump the last neighbor in the lists off to make */
|
|
/* room for the new neighbor (ignore last neighbor in lists). */
|
|
i = *nnbrs-2;
|
|
/* Otherwise, there is a list overflow error condition */
|
|
/* (shouldn't ever happen, but just in case) ... */
|
|
else{
|
|
fprintf(stderr,
|
|
"ERROR : insert_neighbor : overflow in neighbor lists\n");
|
|
return(-481);
|
|
}
|
|
|
|
/* While we havn't reached the desired insertion point ... */
|
|
while(i >= pos){
|
|
/* Shift the current neighbor down the list 1 positon. */
|
|
nbr_list[i+1] = nbr_list[i];
|
|
nbr_sqr_dists[i+1] = nbr_sqr_dists[i];
|
|
i--;
|
|
}
|
|
|
|
/* We are now ready to put our new neighbor in the position where */
|
|
/* we shifted everything down from to make room. */
|
|
nbr_list[pos] = nbr_index;
|
|
nbr_sqr_dists[pos] = nbr_dist2;
|
|
|
|
/* Return normally. */
|
|
return(0);
|
|
}
|
|
|
|
/*************************************************************************
|
|
**************************************************************************
|
|
#cat: sort_neighbors - Takes a list of primary minutia and its neighboring
|
|
#cat: minutia indices and sorts the neighbors based on their
|
|
#cat: position relative to the primary minutia point. Neighbors
|
|
#cat: are sorted starting vertical to the primary point and
|
|
#cat: proceeding clockwise.
|
|
|
|
Input:
|
|
nbr_list - list of neighboring minutia indices
|
|
nnbrs - number of neighbors in the list
|
|
first - the index of the primary minutia point
|
|
minutiae - list of minutiae
|
|
Output:
|
|
nbr_list - neighboring minutia indices in sorted order
|
|
Return Code:
|
|
Zero - successful completion
|
|
Negative - system error
|
|
**************************************************************************/
|
|
int sort_neighbors(int *nbr_list, const int nnbrs, const int first,
|
|
MINUTIAE *minutiae)
|
|
{
|
|
double *join_thetas, theta;
|
|
int i;
|
|
static double pi2 = M_PI*2.0;
|
|
|
|
/* List of angles of lines joining the current primary to each */
|
|
/* of the secondary neighbors. */
|
|
join_thetas = (double *)g_malloc(nnbrs * sizeof(double));
|
|
|
|
for(i = 0; i < nnbrs; i++){
|
|
/* Compute angle to line connecting the 2 points. */
|
|
/* Coordinates are swapped and order of points reversed to */
|
|
/* account for 0 direction is vertical and positive direction */
|
|
/* is clockwise. */
|
|
theta = angle2line(minutiae->list[nbr_list[i]]->y,
|
|
minutiae->list[nbr_list[i]]->x,
|
|
minutiae->list[first]->y,
|
|
minutiae->list[first]->x);
|
|
|
|
/* Make sure the angle is positive. */
|
|
theta += pi2;
|
|
theta = fmod(theta, pi2);
|
|
join_thetas[i] = theta;
|
|
}
|
|
|
|
/* Sort the neighbor indicies into rank order. */
|
|
bubble_sort_double_inc_2(join_thetas, nbr_list, nnbrs);
|
|
|
|
/* Deallocate the list of angles. */
|
|
g_free(join_thetas);
|
|
|
|
/* Return normally. */
|
|
return(0);
|
|
}
|
|
|
|
/*************************************************************************
|
|
**************************************************************************
|
|
#cat: ridge_count - Takes a pair of minutiae, and counts the number of
|
|
#cat: ridges crossed along the linear trajectory connecting
|
|
#cat: the 2 points in the image.
|
|
|
|
Input:
|
|
first - index of primary minutia
|
|
second - index of secondary (neighbor) minutia
|
|
minutiae - list of minutiae
|
|
bdata - binary image data (0==while & 1==black)
|
|
iw - width (in pixels) of image
|
|
ih - height (in pixels) of image
|
|
lfsparms - parameters and thresholds for controlling LFS
|
|
Return Code:
|
|
Zero or Positive - number of ridges counted
|
|
Negative - system error
|
|
**************************************************************************/
|
|
int ridge_count(const int first, const int second, MINUTIAE *minutiae,
|
|
unsigned char *bdata, const int iw, const int ih,
|
|
const LFSPARMS *lfsparms)
|
|
{
|
|
MINUTIA *minutia1, *minutia2;
|
|
int i, ret, found;
|
|
int *xlist, *ylist, num;
|
|
int ridge_count, ridge_start, ridge_end;
|
|
int prevpix, curpix;
|
|
|
|
minutia1 = minutiae->list[first];
|
|
minutia2 = minutiae->list[second];
|
|
|
|
/* If the 2 mintuia have identical pixel coords ... */
|
|
if((minutia1->x == minutia2->x) &&
|
|
(minutia1->y == minutia2->y))
|
|
/* Then zero ridges between points. */
|
|
return(0);
|
|
|
|
/* Compute linear trajectory of contiguous pixels between first */
|
|
/* and second minutia points. */
|
|
if((ret = line_points(&xlist, &ylist, &num,
|
|
minutia1->x, minutia1->y, minutia2->x, minutia2->y))){
|
|
return(ret);
|
|
}
|
|
|
|
/* It there are no points on the line trajectory, then no ridges */
|
|
/* to count (this should not happen, but just in case) ... */
|
|
if(num == 0){
|
|
g_free(xlist);
|
|
g_free(ylist);
|
|
return(0);
|
|
}
|
|
|
|
/* Find first pixel opposite type along linear trajectory from */
|
|
/* first minutia. */
|
|
prevpix = *(bdata+(ylist[0]*iw)+xlist[0]);
|
|
i = 1;
|
|
found = FALSE;
|
|
while(i < num){
|
|
curpix = *(bdata+(ylist[i]*iw)+xlist[i]);
|
|
if(curpix != prevpix){
|
|
found = TRUE;
|
|
break;
|
|
}
|
|
i++;
|
|
}
|
|
|
|
/* If opposite pixel not found ... then no ridges to count */
|
|
if(!found){
|
|
g_free(xlist);
|
|
g_free(ylist);
|
|
return(0);
|
|
}
|
|
|
|
/* Ready to count ridges, so initialize counter to 0. */
|
|
ridge_count = 0;
|
|
|
|
print2log("RIDGE COUNT: %d,%d to %d,%d ", minutia1->x, minutia1->y,
|
|
minutia2->x, minutia2->y);
|
|
|
|
/* While not at the end of the trajectory ... */
|
|
while(i < num){
|
|
/* If 0-to-1 transition not found ... */
|
|
if(!find_transition(&i, 0, 1, xlist, ylist, num, bdata, iw, ih)){
|
|
/* Then we are done looking for ridges. */
|
|
g_free(xlist);
|
|
g_free(ylist);
|
|
|
|
print2log("\n");
|
|
|
|
/* Return number of ridges counted to this point. */
|
|
return(ridge_count);
|
|
}
|
|
/* Otherwise, we found a new ridge start transition, so store */
|
|
/* its location (the location of the 1 in 0-to-1 transition). */
|
|
ridge_start = i;
|
|
|
|
print2log(": RS %d,%d ", xlist[i], ylist[i]);
|
|
|
|
/* If 1-to-0 transition not found ... */
|
|
if(!find_transition(&i, 1, 0, xlist, ylist, num, bdata, iw, ih)){
|
|
/* Then we are done looking for ridges. */
|
|
g_free(xlist);
|
|
g_free(ylist);
|
|
|
|
print2log("\n");
|
|
|
|
/* Return number of ridges counted to this point. */
|
|
return(ridge_count);
|
|
}
|
|
/* Otherwise, we found a new ridge end transition, so store */
|
|
/* its location (the location of the 0 in 1-to-0 transition). */
|
|
ridge_end = i;
|
|
|
|
print2log("; RE %d,%d ", xlist[i], ylist[i]);
|
|
|
|
/* Conduct the validation, tracing the contour of the ridge */
|
|
/* from the ridge ending point a specified number of steps */
|
|
/* scanning for neighbors clockwise and counter-clockwise. */
|
|
/* If the ridge starting point is encounted during the trace */
|
|
/* then we can assume we do not have a valid ridge crossing */
|
|
/* and instead we are walking on and off the edge of the */
|
|
/* side of a ridge. */
|
|
ret = validate_ridge_crossing(ridge_start, ridge_end,
|
|
xlist, ylist, num, bdata, iw, ih,
|
|
lfsparms->max_ridge_steps);
|
|
|
|
/* If system error ... */
|
|
if(ret < 0){
|
|
g_free(xlist);
|
|
g_free(ylist);
|
|
/* Return the error code. */
|
|
return(ret);
|
|
}
|
|
|
|
print2log("; V%d ", ret);
|
|
|
|
/* If validation result is TRUE ... */
|
|
if(ret){
|
|
/* Then assume we have found a valid ridge crossing and bump */
|
|
/* the ridge counter. */
|
|
ridge_count++;
|
|
}
|
|
|
|
/* Otherwise, ignore the current ridge start and end transitions */
|
|
/* and go back and search for new ridge start. */
|
|
}
|
|
|
|
/* Deallocate working memories. */
|
|
g_free(xlist);
|
|
g_free(ylist);
|
|
|
|
print2log("\n");
|
|
|
|
/* Return the number of ridges counted. */
|
|
return(ridge_count);
|
|
}
|
|
|
|
/*************************************************************************
|
|
**************************************************************************
|
|
#cat: find_transition - Takes a pixel trajectory and a starting index, and
|
|
#cat: searches forward along the trajectory until the specified
|
|
#cat: adjacent pixel pair is found, returning the index where
|
|
#cat: the pair was found (the index of the second pixel).
|
|
|
|
Input:
|
|
iptr - pointer to starting pixel index into trajectory
|
|
pix1 - first pixel value in transition pair
|
|
pix2 - second pixel value in transition pair
|
|
xlist - x-pixel coords of line trajectory
|
|
ylist - y-pixel coords of line trajectory
|
|
num - number of coords in line trajectory
|
|
bdata - binary image data (0==while & 1==black)
|
|
iw - width (in pixels) of image
|
|
ih - height (in pixels) of image
|
|
Output:
|
|
iptr - points to location where 2nd pixel in pair is found
|
|
Return Code:
|
|
TRUE - pixel pair transition found
|
|
FALSE - pixel pair transition not found
|
|
**************************************************************************/
|
|
int find_transition(int *iptr, const int pix1, const int pix2,
|
|
const int *xlist, const int *ylist, const int num,
|
|
unsigned char *bdata, const int iw, const int ih)
|
|
{
|
|
int i, j;
|
|
|
|
/* Set previous index to starting position. */
|
|
i = *iptr;
|
|
/* Bump previous index by 1 to get next index. */
|
|
j = i+1;
|
|
|
|
/* While not one point from the end of the trajectory .. */
|
|
while(i < num-1){
|
|
/* If we have found the desired transition ... */
|
|
if((*(bdata+(ylist[i]*iw)+xlist[i]) == pix1) &&
|
|
(*(bdata+(ylist[j]*iw)+xlist[j]) == pix2)){
|
|
/* Adjust the position pointer to the location of the */
|
|
/* second pixel in the transition. */
|
|
*iptr = j;
|
|
|
|
/* Return TRUE. */
|
|
return(TRUE);
|
|
}
|
|
/* Otherwise, the desired transition was not found in current */
|
|
/* pixel pair, so bump to the next pair along the trajector. */
|
|
i++;
|
|
j++;
|
|
}
|
|
|
|
/* If we get here, then we exhausted the trajector without finding */
|
|
/* the desired transition, so set the position pointer to the end */
|
|
/* of the trajector, and return FALSE. */
|
|
*iptr = num;
|
|
return(FALSE);
|
|
}
|
|
|
|
/*************************************************************************
|
|
**************************************************************************
|
|
#cat: validate_ridge_crossing - Takes a pair of points, a ridge start
|
|
#cat: transition and a ridge end transition, and walks the
|
|
#cat: ridge contour from thre ridge end points a specified
|
|
#cat: number of steps, looking for the ridge start point.
|
|
#cat: If found, then transitions determined not to be a valid
|
|
#cat: ridge crossing.
|
|
|
|
Input:
|
|
ridge_start - index into line trajectory of ridge start transition
|
|
ridge_end - index into line trajectory of ridge end transition
|
|
xlist - x-pixel coords of line trajectory
|
|
ylist - y-pixel coords of line trajectory
|
|
num - number of coords in line trajectory
|
|
bdata - binary image data (0==while & 1==black)
|
|
iw - width (in pixels) of image
|
|
ih - height (in pixels) of image
|
|
max_ridge_steps - number of steps taken in search in both
|
|
scan directions
|
|
Return Code:
|
|
TRUE - ridge crossing VALID
|
|
FALSE - ridge corssing INVALID
|
|
Negative - system error
|
|
**************************************************************************/
|
|
int validate_ridge_crossing(const int ridge_start, const int ridge_end,
|
|
const int *xlist, const int *ylist, const int num,
|
|
unsigned char *bdata, const int iw, const int ih,
|
|
const int max_ridge_steps)
|
|
{
|
|
int ret;
|
|
int feat_x, feat_y, edge_x, edge_y;
|
|
int *contour_x, *contour_y, *contour_ex, *contour_ey, ncontour;
|
|
|
|
/* Assign edge pixel pair for contour trace. */
|
|
feat_x = xlist[ridge_end];
|
|
feat_y = ylist[ridge_end];
|
|
edge_x = xlist[ridge_end-1];
|
|
edge_y = ylist[ridge_end-1];
|
|
|
|
/* Adjust pixel pair if they neighbor each other diagonally. */
|
|
fix_edge_pixel_pair(&feat_x, &feat_y, &edge_x, &edge_y,
|
|
bdata, iw, ih);
|
|
|
|
/* Trace ridge contour, starting at the ridge end transition, and */
|
|
/* taking a specified number of step scanning for edge neighbors */
|
|
/* clockwise. As we trace the ridge, we want to detect if we */
|
|
/* encounter the ridge start transition. NOTE: The ridge end */
|
|
/* position is on the white (of a black to white transition) and */
|
|
/* the ridge start is on the black (of a black to white trans), */
|
|
/* so the edge trace needs to look for the what pixel (not the */
|
|
/* black one) of the ridge start transition. */
|
|
ret = trace_contour(&contour_x, &contour_y,
|
|
&contour_ex, &contour_ey, &ncontour,
|
|
max_ridge_steps,
|
|
xlist[ridge_start-1], ylist[ridge_start-1],
|
|
feat_x, feat_y, edge_x, edge_y,
|
|
SCAN_CLOCKWISE, bdata, iw, ih);
|
|
/* If a system error occurred ... */
|
|
if(ret < 0)
|
|
/* Return error code. */
|
|
return(ret);
|
|
|
|
/* Otherwise, if the trace was not IGNORED, then a contour was */
|
|
/* was generated and returned. We aren't interested in the */
|
|
/* actual contour, so deallocate it. */
|
|
if(ret != IGNORE)
|
|
free_contour(contour_x, contour_y, contour_ex, contour_ey);
|
|
|
|
/* If the trace was IGNORED, then we had some sort of initialization */
|
|
/* problem, so treat this the same as if was actually located the */
|
|
/* ridge start point (in which case LOOP_FOUND is returned). */
|
|
/* So, If not IGNORED and ridge start not encounted in trace ... */
|
|
if((ret != IGNORE) &&
|
|
(ret != LOOP_FOUND)){
|
|
|
|
/* Now conduct contour trace scanning for edge neighbors counter- */
|
|
/* clockwise. */
|
|
ret = trace_contour(&contour_x, &contour_y,
|
|
&contour_ex, &contour_ey, &ncontour,
|
|
max_ridge_steps,
|
|
xlist[ridge_start-1], ylist[ridge_start-1],
|
|
feat_x, feat_y, edge_x, edge_y,
|
|
SCAN_COUNTER_CLOCKWISE, bdata, iw, ih);
|
|
/* If a system error occurred ... */
|
|
if(ret < 0)
|
|
/* Return error code. */
|
|
return(ret);
|
|
|
|
/* Otherwise, if the trace was not IGNORED, then a contour was */
|
|
/* was generated and returned. We aren't interested in the */
|
|
/* actual contour, so deallocate it. */
|
|
if(ret != IGNORE)
|
|
free_contour(contour_x, contour_y, contour_ex, contour_ey);
|
|
|
|
/* If trace not IGNORED and ridge start not encounted in 2nd trace ... */
|
|
if((ret != IGNORE) &&
|
|
(ret != LOOP_FOUND)){
|
|
/* If we get here, assume we have a ridge crossing. */
|
|
return(TRUE);
|
|
}
|
|
/* Otherwise, second trace returned IGNORE or ridge start found. */
|
|
}
|
|
/* Otherwise, first trace returned IGNORE or ridge start found. */
|
|
|
|
/* If we get here, then we failed to validate a ridge crossing. */
|
|
return(FALSE);
|
|
}
|