Click here to Skip to main content
14,691,039 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
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);

// Since all neighbors all need to be on the same 'side' for an
// extremum we can just take an arbitrary neighbor to determine
// if we might face a minimum or a maximum.
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)) {
                  // Further processing
                }
            }
        }
    }
}
Posted
Updated 28-Mar-20 2:09am
v4
Comments
0x01AA 24-Mar-20 11:58am
   
The question is not that easy. Let us have a look to two dimension and we are on a maximum y= f(x). Now if you go "left" side let us assume y= 2. If you go "right" side y =1. Both are minimum, but does the lower minimum counts more? And if yes why? And for N dimensions?
JONLIN 28-Mar-20 6:13am
   
The definition of a extrema here is that a given pixel is greator or smaller than all of it's 26 neighbours.
It's therefore possible to have 2 adjacent extrema where one is a maximum and the other is a minimum.
There is no weighting attach to extrema (yet, see chapter 4) so all extrema count the same.

I include this answer for completeness sake.
While Mr Tomas Takac answers if the given pixel is a minimum or not it does not answer the question if it is a extrema (It is easily modifiable so I'll mark it as an answer).

I did some extra research on implementations of the paper I reference and I came across this which answers the given question with this implementation.

(The implementation, c++, is copied here for completeness)
highData is the z+1 slice of the 3D array, currData is the z slice and lowData is the z-1 slice. index is the index into the 2D image slice to point (x,y) where w is the width of the image. The |val| >= contr_thr is a contrast check relevant only to this use case and should be omitted if used elsewhere (don't, this code deserves to be featured in r/programminghorror).

bool bExtrema =
    (val >= contr_thr && val > highData[index - w - 1] &&
    val > highData[index - w] &&
    val > highData[index - w + 1] &&
    val > highData[index - 1] && val > highData[index] &&
    val > highData[index + 1] &&
    val > highData[index + w - 1] &&
    val > highData[index + w] &&
    val > highData[index + w + 1] &&
    val > currData[index - w - 1] &&
    val > currData[index - w] &&
    val > currData[index - w + 1] &&
    val > currData[index - 1] &&
    val > currData[index + 1] &&
    val > currData[index + w - 1] &&
    val > currData[index + w] &&
    val > currData[index + w + 1] &&
    val > lowData[index - w - 1] &&
    val > lowData[index - w] &&
    val > lowData[index - w + 1] &&
    val > lowData[index - 1] && val > lowData[index] &&
    val > lowData[index + 1] &&
    val > lowData[index + w - 1] &&
    val > lowData[index + w] &&
    val > lowData[index + w + 1]) || // Local min
    (val <= -contr_thr && val < highData[index - w - 1] &&
    val < highData[index - w] &&
    val < highData[index - w + 1] &&
    val < highData[index - 1] && val < highData[index] &&
    val < highData[index + 1] &&
    val < highData[index + w - 1] &&
    val < highData[index + w] &&
    val < highData[index + w + 1] &&
    val < currData[index - w - 1] &&
    val < currData[index - w] &&
    val < currData[index - w + 1] &&
    val < currData[index - 1] &&
    val < currData[index + 1] &&
    val < currData[index + w - 1] &&
    val < currData[index + w] &&
    val < currData[index + w + 1] &&
    val < lowData[index - w - 1] &&
    val < lowData[index - w] &&
    val < lowData[index - w + 1] &&
    val < lowData[index - 1] && val < lowData[index] &&
    val < lowData[index + 1] &&
    val < lowData[index + w - 1] &&
    val < lowData[index + w] &&
    val < lowData[index + w + 1]);
   
Comments
Tomas Takac 28-Mar-20 9:11am
   
Point taken. I only showed how to search for minimum because I thought that modifying it for max is trivial. I should have stated this explicitly.
Your code is so stripped down that it is impossible to guess how you use it.
All I can say is that I see nothing to handle a point on a side or corner of the 3D array, and it is bad sign. It is probably time to learn debugger.
My algorithm would be brute force with 6 loops nested.
Quote:
I've tried 2 different solutions both giving wildly different answers and at a surface level neither seems to get me the correct answer...

Your code do not behave the way you expect, or you don't understand why !

There is an almost universal solution: Run your code on debugger step by step, inspect variables.
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't know what your code is supposed to do, it don't find bugs, it just help you to by showing you what is going on. When the code don't do what is expected, you are close to a bug.
To see what your code is doing: Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.

Debugger - Wikipedia, the free encyclopedia[^]

Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]

http://docs.oracle.com/javase/7/docs/technotes/tools/windows/jdb.html[^]
https://www.jetbrains.com/idea/help/debugging-your-first-java-application.html[^]

The debugger is here to only show you what your code is doing and your task is to compare with what it should do.
   
Comments
JONLIN 28-Mar-20 6:14am
   
I deemed the full code to be very long but very well I'll update my question.
JONLIN 28-Mar-20 6:48am
   
While yes, the code provided wouldn't even compile let alone run. But I'll state it again
"
Given an array with dimensions width=w, height=h and depth=d, find all local maximums and minimums. [...]

A local extrema is found when it is bigger/smaller than all of it's 26 neighbours.
"
3 loops are therefore required for each dimension. The 26 points is the surrounding required to define a extrema, a 3x3x3 box.
This surrounding however is not defined for edges and corners, therefore a extrema can not exist on an edge or corner.
the 3 required loops are therefore
for(int x = 1; x < w-1; x++) {
for(int y = 1; y < h-1; y++) {
for(int z = 1; z < d-1; z++) {
if(isExtrema(x,y,z)) {
//...
}}}}

I am at fault for assuming this, I realize that but I hope this clears up your concerns.
My implementation is in C#. I assume arr is an array of objects that have getPixel(x, y) method. I created class Layer for this purpose.

To verify minimum for a given set of coordinates:
bool IsMinimum(Layer[] arr, int x, int y, int z)
{
    double myValue = arr[z].getPixel(x, y);
    int xlo = Math.Max(0, x - 1);
    int xhi = Math.Min(MaxX, x + 2);
    int ylo = Math.Max(0, y - 1);
    int yhi = Math.Min(MaxY, y + 2);
    int zlo = Math.Max(0, z - 1);
    int zhi = Math.Min(MaxZ, z + 2);
    
    bool isMinimum = true;
    for (int zi = zlo; zi < zhi; zi++)
        for (int yi = ylo; yi < yhi; yi++)
            for (int xi = xlo; xi < xhi; xi++)
                if (xi != x || yi != y || zi != z)              
                {
                    double neighborValue = arr[zi].getPixel(xi, yi);
                    isMinimum = isMinimum && (myValue < neighborValue);
                }
            
    return isMinimum;
}

The you simply call it for all pixels:
for (int z = 0; z < MaxZ; z++)
    for (int y = 0; y < MaxY; y++)
        for (int x = 0; x < MaxX; x++)
            if (IsMinimum(arr, x, y, z))
                Console.WriteLine("x={0}, y={1}, z={2}, value={3}", x, y, z, arr[z].getPixel(x, y));

This is a brute force approach. There is most probably a better way to do it as we are reading the same values several time.
   
Comments
JONLIN 28-Mar-20 6:53am
   
I'm actually wondering, is it possible to even find a solution that doesn't do it a "brute force" way? Would such a solution find if a subset of the 3D image contain a extrema?
Tomas Takac 28-Mar-20 9:09am
   
This is not a trivial question. Only brute force approach will be guaranteed to find all the extrema. The limitation of course is that you are able to search the whole set in a reasonable time. There are techniques to find global min/max like Simulated annealing[^]. I don't recall any technique to find all the local extrema though.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900