Find local extrema of 3D array

Question

0.00/5 (No votes)

See more:

Question title says it all.

Given an array

Java

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

Java

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.

Java

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

Java

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

Java

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 24-Mar-20 4:26am

JONLIN

Updated 28-Mar-20 1:09am

v4

Add a Solution

Comments

[no name] 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.

3 solutions

Solution 1

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.

Posted 24-Mar-20 6:01am

Patrice T

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.

Add a Solution

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

JONLIN · Accepted Answer · 2020-03-28T01:10:00

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).

C++

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]);

Tomas Takac · Accepted Answer · 2020-03-24T23:51:00

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:

C#

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:

C#

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.

Find local extrema of 3D array

3 solutions

Solution 3

Solution 1

Solution 2

Add your solution here

Preview 0

Find local extrema of 3D array

3 solutions

Solution 3

Solution 1

Solution 2

Add your solution here

Preview 0

Existing Members

...or Join us