117 lines
4.6 KiB
Java
117 lines
4.6 KiB
Java
package main;
|
|
|
|
public class SimilarityBasedSearch {
|
|
|
|
/**
|
|
* Computes the mean value of a gray-scale image given as a 2D array
|
|
*
|
|
* @param image : a 2D double array, the gray-scale Image
|
|
* @return a double value between 0 and 255 which is the mean value
|
|
*/
|
|
public static double mean(double[][] image) {
|
|
|
|
assert image.length != 0 : "image contains no pixel";
|
|
double sum = 0;
|
|
|
|
for (int i = 0; i < image.length; i++) {
|
|
for (int j = 0; j < image[0].length; j++) {
|
|
sum += image[i][j];
|
|
}
|
|
}
|
|
|
|
return sum / ((double) image.length * image[0].length);
|
|
}
|
|
|
|
/**
|
|
* Computes the mean value of a part of an image
|
|
*
|
|
* @param matrix : a 2D array of double, the gray-scale image we want to calculate the mean value of a part
|
|
* @param row : a integer, the row-coordinate of the upper left corner of the pattern in the image.
|
|
* @param column : a integer, the column-coordinate of the upper left corner of the pattern in the image.
|
|
* @param width : a integer, the width of the window.
|
|
* @param height : a integer, the height of the window.
|
|
* @return a double, the mean value of the specified part of the input matrix
|
|
*/
|
|
static double windowMean(double[][] matrix, int row, int col, int width, int height) {
|
|
|
|
double[][] temp = new double[width][height];
|
|
|
|
for (int i = 0; i < width; i++) {
|
|
for (int j = 0; j < height; j++) {
|
|
temp[i][j] = matrix[i + row][j + col];
|
|
}
|
|
}
|
|
|
|
return mean(temp);
|
|
}
|
|
|
|
/**
|
|
* Computes the Normalized Cross Correlation of a gray-scale pattern if positioned
|
|
* at the provided row, column-coordinate in a gray-scale image
|
|
*
|
|
* @param row : a integer, the row-coordinate of the upper left corner of the pattern in the image.
|
|
* @param column : a integer, the column-coordinate of the upper left corner of the pattern in the image.
|
|
* @param pattern : an 2D array of doubles, the gray-scale pattern to find
|
|
* @param image : an 2D array of double, the gray-scale image where to look for the pattern
|
|
* @return a double, the Normalized Cross Correlation value at position (row, col) between the pattern and the part of
|
|
* the base image that is covered by the pattern, if the pattern is shifted by x and y.
|
|
* should return -1 if the denominator is 0
|
|
*/
|
|
public static double normalizedCrossCorrelation(int row, int col, double[][] pattern, double[][] image) {
|
|
|
|
assert image.length != 0 : "image contains no pixel";
|
|
assert pattern.length != 0 : "pattern contains no pixel";
|
|
double wmean = windowMean(image, row, col, pattern.length, pattern[0].length);
|
|
double m = mean(pattern);
|
|
double sum1 = 0, sum2 = 0, sum3 = 0;
|
|
|
|
for (int i = 0; i < pattern.length; i++) {
|
|
for (int j = 0; j < pattern[0].length; j++) {
|
|
sum1 += (image[row + i][col + j] - wmean) * (pattern[i][j] - m);
|
|
sum2 += (image[row + i][col + j] - wmean) * (image[row + i][col + j] - wmean);
|
|
sum3 += (pattern[i][j] - m) * (pattern[i][j] - m);
|
|
}
|
|
}
|
|
|
|
double result;
|
|
|
|
if ((Math.sqrt(sum2 * sum3)) == 0)
|
|
result = -1;
|
|
else
|
|
result = sum1 / (Math.sqrt(sum2 * sum3));
|
|
|
|
return result;
|
|
}
|
|
|
|
|
|
/**
|
|
* Compute the similarityMatrix between a gray-scale image and a gray-scale pattern
|
|
*
|
|
* @param pattern : an 2D array of doubles, the gray-scale pattern to find
|
|
* @param image : an 2D array of doubles, the gray-scale image where to look for the pattern
|
|
* @return a 2D array of doubles, containing for each pixel of a original gray-scale image,
|
|
* the similarity (normalized cross-correlation) between the image's window and the pattern
|
|
* placed over this pixel (upper-left corner)
|
|
*/
|
|
public static double[][] similarityMatrix(double[][] pattern, double[][] image) {
|
|
|
|
assert pattern.length != 0 : "pattern contains no pixel";
|
|
assert image.length != 0 : "image contains no pixel";
|
|
|
|
int W = image[0].length;
|
|
int w = pattern[0].length;
|
|
int H = image.length;
|
|
int h = pattern.length;
|
|
double[][] matrix = new double[H - h + 1][W - w + 1];
|
|
|
|
for (int i = 0; i < H - h + 1; i++) {
|
|
for (int j = 0; j < W - w + 1; j++) {
|
|
matrix[i][j] = normalizedCrossCorrelation(i, j, pattern, image);
|
|
}
|
|
}
|
|
|
|
return matrix;
|
|
}
|
|
|
|
}
|