Fingerprint.java

package cs107;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Provides tools to compare fingerprint.
 */
public class Fingerprint {

	/**
	 * The number of pixels to consider in each direction when doing the linear
	 * regression to compute the orientation.
	 */
	public static final int ORIENTATION_DISTANCE = 16;

	/**
	 * The maximum distance between two minutiae to be considered matching.
	 */
	public static final int DISTANCE_THRESHOLD = 5;

	/**
	 * The number of matching minutiae needed for two fingerprints to be considered
	 * identical.
	 */
	public static final int FOUND_THRESHOLD = 20;

	/**
	 * The distance between two angle to be considered identical.
	 */
	public static final int ORIENTATION_THRESHOLD = 20;

	/**
	 * The offset in each direction for the rotation to test when doing the
	 * matching.
	 */
	public static final int MATCH_ANGLE_OFFSET = 2;

	/**
	 * Returns an array containing the value of the 8 neighbours of the pixel at
	 * coordinates <code>(row, col)</code>.
	 * <p>
	 * The pixels are returned such that their indices corresponds to the following
	 * diagram:<br>
	 * ------------- <br>
	 * | 7 | 0 | 1 | <br>
	 * ------------- <br>
	 * | 6 | _ | 2 | <br>
	 * ------------- <br>
	 * | 5 | 4 | 3 | <br>
	 * ------------- <br>
	 * <p>
	 * If a neighbours is out of bounds of the image, it is considered white.
	 * <p>
	 * If the <code>row</code> or the <code>col</code> is out of bounds of the
	 * image, the returned value should be <code>null</code>.
	 *
	 * @param image array containing each pixel's boolean value.
	 * @param row   the row of the pixel of interest, must be between
	 *              <code>0</code>(included) and
	 *              <code>image.length</code>(excluded).
	 * @param col   the column of the pixel of interest, must be between
	 *              <code>0</code>(included) and
	 *              <code>image[row].length</code>(excluded).
	 * @return An array containing each neighbours' value.
	 */
	
	
	 public static boolean[] getNeighbours(boolean[][] image, int row, int col) {
		 
		  assert (image != null); // special case that is not expected 
	                          
		  // if the coordinates of the pixel fall outside the image
		  if (row < 0 || row > image.length - 1 || col < 0 || col > image[0].length - 1) {
			  return null;
		  }
		  
		  boolean[] neighbours = new boolean[8];
		  int neighbourRow;
		  int neighbourCol;
		  
		  // instructions to access 8 neighbours
		  int[][] operators = {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
		
		  for (int i = 0; i < 8; ++i) {

			  neighbourRow = row + operators[i][0];
			  neighbourCol = col + operators[i][1];
			  
			  // check if coordinates of neighbouring pixel is outside the image or not
			  if (neighbourRow < 0 || neighbourRow > image.length - 1 || neighbourCol < 0 || neighbourCol > image[0].length - 1) {
				  neighbours[i] = false;
			  } else {
				  neighbours[i] = image[neighbourRow][neighbourCol];
			  }
		  }
		  return neighbours;
	  }
	
	/**
	 * Computes the number of black (<code>true</code>) pixels among the neighbours
	 * of a pixel.
	 *
	 * @param neighbours array containing each pixel value. The array must respect
	 *                   the convention described in
	 *                   {@link #getNeighbours(boolean[][], int, int)}.
	 * @return the number of black neighbours.
	 */
	public static int blackNeighbours(boolean[] neighbours) {

		assert (neighbours.length == 8);
		
		int blackNeighbours = 0;
		
		for (boolean entry : neighbours) {
			if (entry) {
				++blackNeighbours;
			}
		}
		
		return blackNeighbours;
	}

	/**
	 * Computes the number of white to black transitions among the neighbours of
	 * pixel.
	 *
	 * @param neighbours array containing each pixel value. The array must respect
	 *                   the convention described in
	 *                   {@link #getNeighbours(boolean[][], int, int)}.
	 * @return the number of white to black transitions.
	 */
	public static int transitions(boolean[] neighbours) {
		
		// making a copy of neighbours and adding the pixel P0 at the end of the new list
		boolean[] prolongedNeighbours = new boolean[9];
		for (int i=0; i<neighbours.length; ++i) {
			prolongedNeighbours[i] = neighbours[i];
		}
		prolongedNeighbours[8] = neighbours[0];

		//counting transitions
		int transitions = 0;
		for (int i=0; i<8; ++i) {
			if (!prolongedNeighbours[i] && prolongedNeighbours[i+1]) {
				++transitions;
			}
		}
		
		return transitions;
	}
	
	/**
	 * Returns <code>true</code> if the images are identical and false otherwise.
	 *
	 * @param image1 array containing each pixel's boolean value.
	 * @param image2 array containing each pixel's boolean value.
	 * @return <code>True</code> if they are identical, <code>false</code>
	 *         otherwise.
	 */
	public static boolean identical(boolean[][] image1, boolean[][] image2) {
		
		assert (image1 != null && image2 != null);
		
		// if the images are of different sizes, they cannot be identical
		if (image1.length != image2.length || image1[0].length != image2[0].length) {
			return false;
		}
		
		// else we check pixel by pixel
		for (int i = 0; i < image1.length; ++i) {
			for (int j = 0; j < image1[0].length; ++j ) {
				
				if (image1[i][j] != image2[i][j]) {
					return false;
				}
			}
		}
		
		return true;
	}
	
	/**
	 * Internal method used by {@link #thin(boolean[][])}.
	 *
	 * @param image array containing each pixel's boolean value.
	 * @param step  the step to apply, Step 0 or Step 1.
	 * @return A new array containing each pixel's value after the step.
	 */
	public static boolean[][] thinningStep(boolean[][] image, int step) {
		
		assert (step == 2 || step == 1);
		
		//create a new image to have passed through step 1 and 2
		boolean[][] thinImage = new boolean[image.length][image[0].length];
		for (int i = 0; i < image.length; ++i) {
			for (int j = 0; j < image[0].length; ++j) {
				thinImage[i][j] = image[i][j];
			}
		}
		
		//check requirements for each pixel of the original image
		for (int i = 0; i < image.length; ++i) {
			for (int j = 0; j < image[0].length; ++j) {
				
				///requirements
				//req2
				boolean[] neighbors = getNeighbours(image, i, j);
				
				assert (neighbors != null);
				
				//get blackNeighbors and transitions 
				int blackNeighbors = blackNeighbours(neighbors);
				int transitions = transitions(neighbors);
				
				//req1 and 3-6
				boolean req1 = (image[i][j] == true);
				boolean req3 = (blackNeighbors >=2 && blackNeighbors <= 6);
				boolean req4 = (transitions == 1 );
				boolean req5 = !neighbors[0] || !neighbors[2] || !neighbors[4];
				boolean req6 = !neighbors[2] || !neighbors[4] || !neighbors[6];
				boolean req5_2 = !neighbors[0] || !neighbors[2] || !neighbors[6];
				boolean req6_2 = !neighbors[0] || !neighbors[4] || !neighbors[6];
				
				//checking requirements for the pixel
				if (req1 && req3 && req4 && req5 && req6 && step == 1) {
					thinImage[i][j] = false;
				} else if (req1 && req3 && req4 && req5_2 && req6_2 && step == 2) {
					thinImage[i][j] = false;
				}
			}
		} 
		
		return thinImage;
	}

	
	
	/**
	 * Compute the skeleton of a boolean image.
	 *
	 * @param image array containing each pixel's boolean value.
	 * @return array containing the boolean value of each pixel of the image after
	 *         applying the thinning algorithm.
	 */
	public static boolean[][] thin(boolean[][] image) {
		
		//assigning the original image to temp and declaring two intermediate variables
		boolean[][] temp = image;
		boolean[][] image1;
		boolean[][] image2;
		int n = 0;
		
		do {
			image1 = thinningStep(temp, 1);
			image2 = thinningStep(image1, 2);
			if ( !identical(temp, image2) ) {
				temp = image2;
			} else {
				++n;
			}
		} while (n == 0);
		return image2;	
	}

	/**
	 * Computes all pixels that are connected to the pixel at coordinate
	 * <code>(row, col)</code> and within the given distance of the pixel.
	 *
	 * @param image    array containing each pixel's boolean value.
	 * @param row      the first coordinate of the pixel of interest.
	 * @param col      the second coordinate of the pixel of interest.
	 * @param distance the maximum distance at which a pixel is considered.
	 * @return An array where <code>true</code> means that the pixel is within
	 *         <code>distance</code> and connected to the pixel at
	 *         <code>(row, col)</code>.
	 */
	public static boolean[][] connectedPixels(boolean[][] image, int row, int col, int distance) {
		
		// create the connectedPixels array and add in the given minutia
		boolean [][] connectedPixels = new boolean[image.length][image[0].length];
		connectedPixels[row][col] = true;
		
		boolean pixelFound = false;
		// we will i and j as the iterators inside the loop
		int i = 0; 
		int j = 0;
		
		while( !pixelFound ) {
			
			boolean pixel = image[i][j];
			boolean [] neighbours = getNeighbours(connectedPixels, i, j);
			int blackNeighbours = blackNeighbours(neighbours);
			
			//requirements
			boolean req1 = pixel == true;
			boolean req2 = blackNeighbours > 0;
			boolean req3 = i <= row+distance && j <= col+distance && i >= row-distance && j >= col-distance;
			boolean req4 = connectedPixels[i][j] == false; //if the pixel is already black, then we skip over it
			
			// if a pixel meets the requirements it is added to connectedPixels
			if (req1 && req2 && req3 && req4) {
				connectedPixels[i][j] = pixel;
				i=0;
				j=0;
				
			} else { //iteration over each row i and column j
				++j;
				if (j == image[0].length) {
					j=0;
					++i;
					if(i == image.length) {
						pixelFound = true;
					}
				}
			}
		}
		
		return connectedPixels;
	}
	
	/**
	 * Computes the slope of a minutia using linear regression.
	 *
	 * @param connectedPixels the result of
	 *                        {@link #connectedPixels(boolean[][], int, int, int)}.
	 * @param row             the row of the minutia.
	 * @param col             the col of the minutia.
	 * @return the slope.
	 */
	public static double computeSlope(boolean[][] connectedPixels, int row, int col) {
		
		double sumXY = 0;
		double sumXX = 0;
		double sumYY = 0;
		double a = 0;
		
		// recursively define sumXX, sumXY and sumYY
		for (int i = 0; i < connectedPixels.length; ++i) {
			for (int j = 0; j < connectedPixels[0].length; ++j) {
				
				if (connectedPixels[i][j]) {
					
					int x = j - col;
					int y = row - i;
					
					sumXY += x*y;
					sumXX += x*x;
					sumYY += y*y;
				}
			}
		}
		
		if (sumXX >= sumYY) {
			if (sumXX == 0) { // if the slope is vertical
				a = Double.POSITIVE_INFINITY;
			}
			a = sumXY / sumXX;
		} else {
			a = sumYY/ sumXY;																					
		} 
		
		return a ;
	}

	/**
	 * Computes the orientation of a minutia in radians.
	 * 
	 * @param connectedPixels the result of
	 *                        {@link #connectedPixels(boolean[][], int, int, int)}.
	 * @param row             the row of the minutia.
	 * @param col             the col of the minutia.
	 * @param slope           the slope as returned by
	 *                        {@link #computeSlope(boolean[][], int, int)}.
	 * @return the orientation of the minutia in radians.
	 */
	public static double computeAngle(boolean[][] connectedPixels, int row, int col, double slope) {
		
		int above = 0;
		int below = 0;
		double inverseSlope = -1/slope;
		
		//for each pixel, check if it is above or below the perpendicular to the slope 
		for (int i = 0; i < connectedPixels.length; ++i) {
			for (int j = 0; j < connectedPixels[0].length; ++j) {
				
				int x = j - col;
				int y = row - i;
				
				if ( y >= inverseSlope*x && connectedPixels[i][j] == true && i != row && j != col) {
					++above;
				} else if ( y < inverseSlope*x && connectedPixels[i][j] == true && i != row && j != col) {
					++below;
				}
			}
		}
		
		//calculate initial angle
		double angle = Math.atan(slope);
		
		//refine angle through conditions
		if ((angle > 0 && below > above) || (angle < 0 && below < above) ) {
			angle += Math.PI;
		} else if (slope == Double.POSITIVE_INFINITY && above > below) {
			angle = Math.PI/2;
		} else if (slope == Double.POSITIVE_INFINITY && above < below) {
			angle = -Math.PI/2;
		}
		
		return angle;
	}
	
	/**
	 * Computes the orientation of the minutia that the coordinate <code>(row,
	 * col)</code>.
	 *
	 * @param image    array containing each pixel's boolean value.
	 * @param row      the first coordinate of the pixel of interest.
	 * @param col      the second coordinate of the pixel of interest.
	 * @param distance the distance to be considered in each direction to compute
	 *                 the orientation.
	 * @return The orientation in degrees.
	 */
	public static int computeOrientation(boolean[][] image, int row, int col, int distance) {
		
		boolean [][] connectedPixels = connectedPixels(image, row, col, distance);
		double slope = computeSlope(connectedPixels, row, col);
		double angle = computeAngle(connectedPixels, row, col, slope);
		
		double angleDeg =  Math.round(Math.toDegrees(angle));
		
		// if angle is negative, add 360
		if (angleDeg < 0) {
			angleDeg += 360;
		}
		
		return (int) angleDeg;
	}

	
	
	/**
	 * Extracts the minutiae from a thinned image.
	 *
	 * @param image array containing each pixel's boolean value.
	 * @return The list of all minutiae. A minutia is represented by an array where
	 *         the first element is the row, the second is column, and the third is
	 *         the angle in degrees.
	 * @see #thin(boolean[][])
	 */
	public static List<int[]> extract(boolean[][] image) {
		
		List<int[]> minutiae = new ArrayList<int[]>();
		
		for (int i = 1; i < image.length-1; ++i) {
			for (int j = 1; j < image[0].length-1; ++j) {
				
				boolean pixel = image[i][j];
				boolean[] neighbours = getNeighbours(image, i ,j);
				int transitions = transitions(neighbours);
				int[] minutia = new int[3];
				
				// we check if the pixel meets the requirements for being a minutia
				if (pixel && (transitions == 1 || transitions == 3) ) {
					int angle = computeOrientation(image, i, j, ORIENTATION_DISTANCE);
					minutia[0] = i;
					minutia[1] = j;
					minutia[2] = angle;
					minutiae.add(minutia);
				}
			}
		}
		
		return minutiae;
	}
	
	/**
	 * Applies the specified rotation to the minutia.
	 *
	 * @param minutia   the original minutia.
	 * @param centerRow the row of the center of rotation.
	 * @param centerCol the col of the center of rotation.
	 * @param rotation  the rotation in degrees.
	 * @return the minutia rotated around the given center.
	 */
	public static int[] applyRotation(int[] minutia, int centerRow, int centerCol, int rotation) {
		
		int col = minutia[1];
		int row = minutia[0];
		int orientation = minutia[2];
		double rotationRad = Math.toRadians(rotation);
		
		int x = col - centerCol;
		int y = centerRow - row;
		int newX = (int) (x * Math.cos(rotationRad) - y*Math.sin(rotationRad));
		int newY = (int) (x*Math.sin(rotationRad) + y*Math.cos(rotationRad));
		int newRow =  centerRow- newY;
		int newCol =  newX + centerCol;
		int newOrientation = (int) (orientation + rotation)%360;
		
		int[] newMinutia = {newRow, newCol, newOrientation};
				
		return newMinutia;
	}

	/**
	 * Applies the specified translation to the minutia.
	 *
	 * @param minutia        the original minutia.
	 * @param rowTranslation the translation along the rows.
	 * @param colTranslation the translation along the columns.
	 * @return the translated minutia.
	 */
	public static int[] applyTranslation(int[] minutia, int rowTranslation, int colTranslation) {
		
		int row = minutia[0];
		int col = minutia[1];
		int orientation = minutia[2];
		
		int newRow = row - rowTranslation;
		int newCol = col - colTranslation;
		int newOrientation = orientation;
		
		int[] newMinutia = {newRow, newCol, newOrientation};
		
		return newMinutia;
	}

	/**
	 * Computes the row, column, and angle after applying a transformation
	 * (translation and rotation).
	 *
	 * @param minutia        the original minutia.
	 * @param centerCol      the column around which the point is rotated.
	 * @param centerRow      the row around which the point is rotated.
	 * @param rowTranslation the vertical translation.
	 * @param colTranslation the horizontal translation.
	 * @param rotation       the rotation.
	 * @return the transformed minutia.
	 */
	public static int[] applyTransformation(int[] minutia, int centerRow, int centerCol, int rowTranslation,
			int colTranslation, int rotation) {
		
		//rotating and translating the given minutia
		int[] rotatedMinutia = applyRotation(minutia, centerRow, centerCol, rotation);
		int[] transformedMinutia = applyTranslation(rotatedMinutia, rowTranslation, colTranslation);
			
		return transformedMinutia;
	}

	/**
	 * Computes the row, column, and angle after applying a transformation
	 * (translation and rotation) for each minutia in the given list.
	 *
	 * @param minutiae       the list of minutiae.
	 * @param centerCol      the column around which the point is rotated.
	 * @param centerRow      the row around which the point is rotated.
	 * @param rowTranslation the vertical translation.
	 * @param colTranslation the horizontal translation.
	 * @param rotation       the rotation.
	 * @return the list of transformed minutiae.
	 */
	public static List<int[]> applyTransformation(List<int[]> minutiae, int centerRow, int centerCol,
			int rowTranslation, int colTranslation, int rotation) {
		
		List<int[]> transformedMinutiae = new ArrayList<int[]>();
		  
		for (int[] minutia : minutiae) {
			transformedMinutiae.add(applyTransformation(minutia, centerRow, centerCol, rowTranslation, colTranslation, rotation));
		}
		  
		return transformedMinutiae;
	}

	/**
	 * Counts the number of overlapping minutiae.
	 *
	 * @param minutiae1      the first set of minutiae.
	 * @param minutiae2      the second set of minutiae.
	 * @param maxDistance    the maximum distance between two minutiae to consider
	 *                       them as overlapping.
	 * @param maxOrientation the maximum difference of orientation between two
	 *                       minutiae to consider them as overlapping.
	 * @return the number of overlapping minutiae.
	 */
	public static int matchingMinutiaeCount(List<int[]> minutiae1, List<int[]> minutiae2, int maxDistance,
			int maxOrientation) {
		
		int matchingMinutiaeCount = 0;
		
		for (int[] m1 : minutiae1) {
			for (int[] m2 : minutiae2) {
				
				//euclidian distance between minutia1 and 2
				double euclidianDistance = Math.sqrt( Math.pow((m1[0]-m2[0]), 2.0) + Math.pow(m1[1]-m2[1], 2.0) );
				
				//requirements
				boolean req1 = euclidianDistance <= maxDistance;
				boolean req2 = Math.abs(m2[2]-m1[2]) <= maxOrientation;
				
				if (req1 && req2) {
					++matchingMinutiaeCount;
				}
			}
		}
		
		return matchingMinutiaeCount;
	}

	/**
	 * Compares the minutiae from two fingerprints.
	 *
	 * @param minutiae1 the list of minutiae of the first fingerprint.
	 * @param minutiae2 the list of minutiae of the second fingerprint.
	 * @return Returns <code>true</code> if they match and <code>false</code>
	 *         otherwise.
	 */
	public static boolean match(List<int[]> minutiae1, List<int[]> minutiae2) {
		
		for (int[] m1 : minutiae1) {
			for(int[] m2 : minutiae2) {
				
				int centerRow = m1[0];
				int centerCol = m1[1];
				int rowTranslation = m2[0] - m1[0];
				int colTranslation = m2[1] - m1[1];
				int rotation = m2[2] - m1[2];
				
				// we check the number of matching minutiae for every angle in the interval defined by the given angle offset
				for(int r = rotation - MATCH_ANGLE_OFFSET; r <= rotation + MATCH_ANGLE_OFFSET; ++r) {
					
					List<int[]> minutiae2Transformed = applyTransformation(minutiae2, centerRow, centerCol, rowTranslation, colTranslation, r);
					int matchCount = matchingMinutiaeCount(minutiae1, minutiae2Transformed, DISTANCE_THRESHOLD, ORIENTATION_THRESHOLD);
					
					if (matchCount >= FOUND_THRESHOLD) {
						  return true;
					}
				}
			}	
		}
		
		return false;
	}
}