Question title says it all.
Given an array
float[][][] arr;
with dimensions width=w, height=h and depth=d, find all local maximums and minimums. (indexing should be done arr[depth][height][width])
A local extrema is found when it is bigger/smaller than all of it's 26 neighbours.
The end goal of this method is as a building block for an implementation of SIFT (
here's a link to the original paper if you want to see where this array comes from)
What I have tried:
All code examples provided here are made in Java, however if you are more comfortable with languages such as c,c++ and c# you may submit answers using these instead.
I've tried 2 different solutions both giving wildly different answers and at a surface level neither seems to get me the correct answer...
The answers I have here assumes a point (x,y,z) is given in this 3D array. where
Image adj[3] = {arr[z-1],arr[z],arr[z+1]};
The getPixel function merely returns the pixel value located at (x,y) inside the 2D slice of the 3D array.
private boolean isExtrema(int x, int y, BufferedImage low, BufferedImage curr, BufferedImage high) {
BufferedImage[] adj = {low,curr,high};
float value = adj[1].getPixel(x, y);
float sign = Math.signum(value - adj[0].getPixel(x,y));
value *= sign;
boolean isExtrema = true;
isExtrema &= adj[0].getPixel(x - 1, y - 1) * sign < value;
isExtrema &= adj[0].getPixel(x - 1, y) * sign < value;
isExtrema &= adj[0].getPixel(x - 1, y + 1) * sign < value;
isExtrema &= adj[0].getPixel(x, y - 1) * sign < value;
isExtrema &= adj[0].getPixel(x, y) * sign < value;
isExtrema &= adj[0].getPixel(x,y + 1) * sign < value;
isExtrema &= adj[0].getPixel(x + 1, y - 1) * sign < value;
isExtrema &= adj[0].getPixel(x + 1, y) * sign < value;
isExtrema &= adj[0].getPixel(x + 1, y + 1) * sign < value;
isExtrema &= adj[1].getPixel(x - 1, y - 1) * sign < value;
isExtrema &= adj[1].getPixel(x - 1, y) * sign < value;
isExtrema &= adj[1].getPixel(x - 1, y + 1) * sign < value;
isExtrema &= adj[1].getPixel(x, y - 1) * sign < value;
isExtrema &= adj[1].getPixel(x, y + 1) * sign < value;
isExtrema &= adj[1].getPixel(x + 1, y - 1) * sign < value;
isExtrema &= adj[1].getPixel(x + 1, y) * sign < value;
isExtrema &= adj[1].getPixel(x + 1, y + 1) * sign < value;
isExtrema &= adj[2].getPixel(x - 1, y - 1) * sign < value;
isExtrema &= adj[2].getPixel(x - 1, y) * sign < value;
isExtrema &= adj[2].getPixel(x - 1, y + 1) * sign < value;
isExtrema &= adj[2].getPixel(x, y - 1) * sign < value;
isExtrema &= adj[2].getPixel(x, y) * sign < value;
isExtrema &= adj[2].getPixel(x, y + 1) * sign < value;
isExtrema &= adj[2].getPixel(x + 1, y - 1) * sign < value;
isExtrema &= adj[2].getPixel(x + 1, y) * sign < value;
isExtrema &= adj[2].getPixel(x + 1, y + 1) * sign < value;
return isExtrema;
}
Second solution I've tried
private boolean isExtrema(BufferedImage low, BufferedImage curr, BufferedImage high, int x, int y) {
BufferedImage[] adj = {low,curr,high};
float cv = adj[1].getPixel(x, y);
boolean isMax = true;
MAX:for(int a = 0; a < 3; a++) {
for (int j = -1; j < 1; j++) {
for (int i = -1; i < 1; i++) {
if (adj[a].getPixel(x + i, y + j) >= cv && !(i == 0 && j == 0 && a == 1)) {
isMax = false;
break MAX;
}
}
}
}
if(isMax)
return true;
boolean isMin = true;
MIN:for(int a = 0; a < 3; a++) {
for (int j = -1; j < 1; j++) {
for (int i = -1; i < 1; i++) {
if (adj[a].getPixel(x + i, y + j) <= cv && !(i == 0 && j == 0 && a == 1)) {
isMin = false;
break MIN;
}
}
}
}
return isMin;
}
Given a sample array the first method gave 24000 extremas wheras the second gave over 200000 thousand...
EDIT: Context for the given code examples
public void findExtrema(BufferedImage[] pyramid) {
for(int i = 1; i < pyramid.length - 1; i++) {
final BufferedImage prev = dogpyr[i-1];
final BufferedImage img = dogpyr[i];
final BufferedImage next = dogpyr[i+1];
final int IMG_BORDER = 5;
for(int row = IMG_BORDER; row < img.getHeight()-IMG_BORDER; row++) {
for(int col = IMG_BORDER; col < img.getWidth()-IMG_BORDER; col++) {
if(isExtrema(col,row,prev,img,next)) {
}
}
}
}
}