convex hull in 3D binary matrix

I've looked at a few options in Matlab and can't seem to find a way to do what I want it to do. How can I use Matlab to draw a convex hull around specific cells in a 3D binary matrix?

I'm working with RGB image colors in a 256x256x256 binary matrix with the axes representing the R, G, and B color coordinates from 0 to 255. If an image has a specific color, let's call it "x,y,z", then the cell at coordinates x,y,z in the matrix is set to 1, else it's a 0. What I'm doing is adding 1's to the RGB cube, each representing colors from color samples that I want to be able to flag in RGB colorspace (specifically, they represent samples of colors that need to be deleted from a given image, leaving the rest of the colors in the image unchanged). What this results in is basically like a 3D scatterplot of points in RGB space from the samples.

However, the sample colors themselves (represented by the points) are not all I'm interested in. I also want to eliminate closely-related colors whose exact RGB coordinates may not have been represented in the color samples, but those colors are similar enough to some that WERE sampled that they should be flagged along with them. Example: suppose I sample pixel value 120,96,71 in an image. A very similar color is 126,108,75. However, suppose 126,108,75 was not sampled. I still want to be able to eliminate it because it is a very similar shade to another color I want to remove.

What I want to do is to fill in nearby cells in the RGB cube representing those related color values using a 3D convex hull grouping the sampled color values together AND filling in all cells on or within the convex hull with 1's if they have not already been set to 1. I can then use the RGB cube as a lookup table to see if a given pixel value should or should not be eliminated from a given image (if a given pixel's color coordinates fall on or within the hull in RGB colorspace, it gets eliminated, if not, it remains).

Basically what I'm asking is how to do a 3D convex hull like the bwconvhull() function (which as far as I know only works for 2D images). Also note, this is different from PLOTTING a convex hull in a 3D graph. Visualization does me no good for this. I need to use the convex hull itself as a lookup table, which means this needs to be stored as a 3D binary matrix. I am aware of functions like convhull(), convhulln(), and using the Delaunay triangulation convex hull. None of these do me any good for what I'm trying to accomplish.

[JOMS ANTONY]

A range based binary thresholding will help right? ie instead of looking for a specific value like 120,96,71, you can change the logic to check if the pixel values are in the custom range like (120 to 130),(90 to 100),(70 to 80) which you are looking for, By the way I would like know what is the application use-case for this. Does there exists any scenario for computing the convex hull of large 3D matrices where this thresholding thing has to be performed first on the pixels of interest

[EricT]

I did look into something similar to what you're describing. This will result in a series of cubes in RGB space, each centered around a specific sampled color. You can also do the same thing with spheres instead of cubes. However, I thought using a convex hull was a more complete and elegant way of encompassing the set of sampled colors. The intended application is for filtering images based on sampling the colors of specific pixels from elements in the image you want to remove. For example, after generating the binary matrix, your script could go through an image pixel by pixel checking the color values. If any of those color values were flagged in the binary matrix, the pixel in question can be filtered out by setting its color values to whatever color you want (ie (0,0,0) if you want to black out the filtered pixels, (255,255,255) if you want to white them out, etc.). In my case I was looking for an efficient way to automatically filter aerial crop images to remove background pixels, leaving behind only the foliage. That way, when analyzing the images, the non-foliage pixels may be ignored.

Answer 1

[John D'Errico]

It is easy enough to do, although I will suggest that a convex hull is often a bad idea when applied to color data. AN alpha shape is often better IMHO. You don't show any data, so I'll need to conjour some up. As it turns out, I had some garbage data hidden away. I saved a .mat file with the variable mat in it.

load mat.mat
rgbind = find(mat);
[r,g,b] = ind2sub(size(mat),rgbind);

So that extracts the elements in mat that were non-zero. We can see them here:

plot3(r,g,b,'o')
grid on
box on

We can easily enough wrap a convex hull around them. I like to use alphaShape, because this allows me to plot it trivially, as well as change the value of alpha.

S = alphaShape(rgbs,inf);
plot(S)

An alpha shape with inf alpha produces the convex hull of your data.

A sometimes problem with a convex hull however, especially when applied to color data is these gamut sets are rarely convex. It is easy enough here to change alpha. But if we stick with the convex hull...

[rall,gall,ball] = ndgrid(1:256,1:256,1:256);
rgball = [rall(:),gall(:),ball(:)];
inlist = inShape(S,rgball);

sum(inlist)
ans =
     1137778
      
256*256*256
ans =
    16777216
      
plot3(rall(inlist),gall(inlist),ball(inlist),'.')
grid on
box on

So out of the 16.7 million possible colors we could encode in that color cube, around 1.1 million lie inside the convex hull of the point set I provided in mat.

Given inlist, it is now easy enough to go back, and stuff them into the original matrix.

[EricT]

With a few minor tweaks, this appears to be exactly what I was looking for. Thanks!

Attached is my 'cube' matrix. I like to use implay() to see what's in it (around slice 200 is where the color points start). Since this is only a test for proof of concept, it's only filled with a handful of color values from one sampling. I would use the basic procedure below multiple times to draw separate convex hulls around clusters of color values from multiple samplings, however. The idea is that each sampled set of colors corresponds to some feature that I want eliminated, and so if those colors are encountered in an image I'm filtering, those pixels get colored to some uniform flag value, like pure red.

Anyway, here's what I did:

load cube.mat
implay(cube);  %if you want to have a look at the data

%find the nonzero elements:
rgbind = find(cube);
[r,g,b] = ind2sub(size(cube),rgbind);
rgbs = zeros(length(r),3);
rgbs(:,1) = r;
rgbs(:,2) = g;
rgbs(:,3) = b;

%view the points:
plot3(r,g,b,'o')
grid on
box on

%create and view the alpha shape:
S = alphaShape(rgbs,inf);
plot(S)

%view the points inside the convex hull:
[rall,gall,ball] = ndgrid(1:256,1:256,1:256);
rgball = [rall(:),gall(:),ball(:)];
inlist = inShape(S,rgball);
sum(inlist)
plot3(rall(inlist),gall(inlist),ball(inlist),'.')
grid on
box on

%extract the points inside the convex hull and put them in a new 'cube' matrix:
cube2 = cube;
count = 1;
for b_ind = 1:256
    for g_ind = 1:256
        for r_ind = 1:256
            if inlist(count) == 1
                cube2(r_ind,g_ind,b_ind) = 1;
            end
            count = count + 1;
        end
    end
end
implay(cube2);

'cube2' can now be used as a lookup table for any image you wish to filter - it will allow you to eliminate pixels with colors inside that convex hull. Bear in mind however, that because Matlab uses base-1 indexing, there is an offset between the coordinates in 'cube' / 'cube2' and the actual RGB color values. A 'cube' index of 1 actually corresponds to RGB values equal to 0, and likewise an index of 256 actually is for RGB values equal to 255. Just remember that offset.

Edit: made a slight correction to the code - the triple-nested for loop at the end needs to go in the order B-G-R to extract the values in the proper order from 'inlist'.

Answer 2

[Matt J]

It sounds like imdilate() is all that you need. Just choose the strel to be the shape of the convex neighborhood that you want.

[EricT]

I had a look at imdilate(), but I'm confused about how to properly use the strel part. Suppose my 3D binary matrix is a variable called 'cube'. My understanding is the syntax would go like so: 'im_out = imdilate(cube,strel(nhood))', although it looks like there are several other options for how to use strel(). What does 'nhood' need to be? I've tried listing the coordinates of each of the points in 'cube' in an nx3 matrix (one column for each of the x, y, and z coordinates). Using the call 'im_out = imdilate(cube,strel(nhood))' where 'nhood' is this list of coordinates goes from this in one slice of the cube:

To this (at the same slice):

I also tried running that same list of points through convhulln() and using that output (let's call it 'K') as the input for strel, like so: 'im_out = imdilate(cube,strel(K))', which produces this (at the same slice as above):

So I would assume using 'K' is the way to go, but I still need to fine-tune the arguments for strel() and imdilate() to get a proper convex hull, which I'm not sure of. Suggestions?

So far the closest I've been able to get to what I want is either by using bwconvhull() on each 2D slice of 'cube', which would look like this for the same slice as the images above:

Or by using a script I wrote which draws a sphere around each individual point in 'cube' using the Euclidean distance formula at a given radius. Neither of these approaches are quite what I need, but they're the closest I've gotten.

[Matt J]

For example, if you wanted your convex neighborhood around each point to be a 5x5x3 cuboid you would do,

im_out = imdilate(cube,ones(5,5,3));

Or, if you wanted the convex neighborhood to be a sphere of radius 6, you would do,

im_out = imdilate(cube,strel('sphere',6))