Extraction of object boundaries from an image

Dear all,

I am working with the above image that contains 20 irregularly shaped objects on a Cartesian grid. Given the (x,y) coordinates of an arbitrary point, is there a way to determine whether or not the point lies within the boundary of one of the objects? Please note that the (x,y) coordinates may not necessarily be an integer multiple of the grid spacing of 0.2 used in the above figure.

I belive it is first necessary to identify the boundaries of each of the 20 objects using the Image Processing Toolbox. I have tried using the bwtraceboundary function for this purpose without any success thus far.

Any help/hints would be greatly appreciated.

[Peter O]

Is the grid spacing present in the image? That could complicate the region detection and segmentation. Without the grid overlay, it should be really straightforward for bwboundaries to find the regions.

Is the grid always at 0.2, or can it be determined a priori (perhaps with an edge detector)? You could play some games with the areas of fill regions and then knit ROIs together.

[Karthik Nagarajan]

Hi Peter O,

Thanks for your help.

The grid is indeed present in the image. Please find attached the image file. It is the only thing that I have to work with at the moment.

The only purpose of the grid is to show the objects' positions in 2D space. The exact value of the grid spacing is not important for my purposes.

Answer 1

[DGM]

I don't know why everyone loves to hand out complete garbage test images for assignments like this. I lopped off the plot box and reduced it so that it's usable. Consider the primary focus of this answer to be the image preparation. I'm sure someone can offer a better method for dealing with the blob membership test.

% since this is such a garbage picture, thresholding can get rid of some of the grid
inpict = rgb2gray(imread('blobgrid.png'))<32;
inpict = bwareaopen(inpict,10); % clean up leftover bits
bp = bwmorph(inpict,'branchpoints'); % this is for later

% process with a really wide edge filter to find long lines
w = 100;
fk = repmat([-1 1],[w 1])./w;
ppict = padarray(inpict,[1 1],0,'both'); 
a = imfilter(ppict,fk) | imfilter(ppict,fk.');
a = a(1:end-2,1:end-2);

% remove lines
inpict = inpict & ~a;
% add branchpoints in the hopes that it closes most gaps
inpict = inpict | bp;
% clean up 
inpict = bwareaopen(inpict,10);
inpict = bwmorph(inpict,'thin',10);
inpict = bwmorph(inpict,'spur',2);

% try to reassemble the pieces of objects
[y x] = find(bwmorph(inpict,'endpoints')); % find endpoints
D = (x-x.').^2 + (y-y.').^2; % squared distance to/from all points
D(D<1E-6) = NaN; % remove self-distances
[~,Nn] = min(D,[],2); % minimize to find nearest neighbors
% stitch lines back together
for ep = 1:numel(Nn)
    hl = images.roi.Line('position',[x(ep) y(ep); x(Nn(ep)) y(Nn(ep))]);
    inpict = inpict | createMask(hl,inpict);
end

% fill closed paths
inpict = imfill(inpict,'holes');

% now the image is usable.
imshow(inpict); hold on;

% these are example query points [x y]
nqp = 30;
qp = [linspace(150,360,nqp); linspace(130,97,nqp)].' % in image space

% test query points for blob membership
L = bwlabel(inpict);
qp = round(qp);
inblob = zeros(size(qp,1),1);
for p = 1:size(qp,1)
    inblob(p) = L(qp(p,2),qp(p,1));
end
inblob

which gives:

inblob =
     0
     0
     0
     0
     0
     0
     0
     3
     3
     0
     0
     0
     0
     0
     0
     0
     6
     6
     6
     6
     6
     0
     0
     0
     0
     0
    10
    10
    10
    10

We can visualize the test by graphing everything:

% show where the query points are to see if that makes sense
for p = 1:size(qp,1)
    plot(qp(p,1),qp(p,2),'mx')
end
S = regionprops(inpict,'centroid');
C = vertcat(S.Centroid);	
for b = 1:numel(S)
    text(C(b,1),C(b,2),num2str(b),'horizontalalignment','center');
end

Which makes sense to me.

Translating the coordinate ranges described by the original plot to the native pixel coordinates should be simple enough. Just scale qp and flip the y component. EDIT: Something like this.

% these are example query points [x y]
nqp = 30;
datalimits = [50 25];
qp = [linspace(12.5,30,nqp); linspace(12.5,22.5,nqp)].' % in data space
qp(:,2) = datalimits(2)-qp(:,2);
qp = qp./datalimits.*[size(inpict,2) size(inpict,1)];

Everything else would be the same

[Karthik Nagarajan]

Hi DGM,

Thank you for the detailed answer. It is exactly what I was looking for. I tried running the first part of your code in MATLAB R2021a and obtained the following result:

There seem to be some additional white regions that are not there in the image in your answer. May I know why this is the case? Is it necessary to carry out some additional pre-processing to obtain 'blobgrid.png'?

[Karthik Nagarajan]

It turns out that DGM's code almost worked. I had to perform a few additional manual adjustments.

This is the program I used:

clear;clc;clf;
close all hidden;

% since this is such a garbage picture, thresholding can get rid of some of the grid
inpict = rgb2gray(imread('Media.png'))<32;
inpict = bwareaopen(inpict,10); % clean up leftover bits
bp = bwmorph(inpict,'branchpoints'); % this is for later
% process with a really wide edge filter to find long lines
w = 100;
fk = repmat([-1 1],[w 1])./w;
ppict = padarray(inpict,[1 1],0,'both'); 
a = imfilter(ppict,fk) | imfilter(ppict,fk.');
a = a(1:end-2,1:end-2);
% remove lines
inpict = inpict & ~a;

% Clean edges of image
% i1,i2,j1 and j2 were determined through manual trial and error
% This code segment was not in DGM's original answer.
i1=50;
i2=334;
j1=40;
j2=650;
inpict(1:i1,:)=false;
inpict(i2:end,:)=false;
inpict(:,1:j1)=false;
inpict(:,j2:end)=false;

% add branchpoints in the hopes that it closes most gaps
inpict = inpict | bp;
% clean up 
inpict = bwareaopen(inpict,10);
inpict = bwmorph(inpict,'thin',10);
inpict = bwmorph(inpict,'spur',2);
% try to reassemble the pieces of objects
[y x] = find(bwmorph(inpict,'endpoints')); % find endpoints
D = (x-x.').^2 + (y-y.').^2; % squared distance to/from all points
D(D<1E-6) = NaN; % remove self-distances
[~,Nn] = min(D,[],2); % minimize to find nearest neighbors
% stitch lines back together
for ep = 1:numel(Nn)
    hl = images.roi.Line('position',[x(ep) y(ep); x(Nn(ep)) y(Nn(ep))]);
    inpict = inpict | createMask(hl,inpict);
end
% fill closed paths
inpict = imfill(inpict,'holes');
% now the image is usable.
imshow(inpict); hold on;

The following result was obtained in R2021a:

[Peter O]

Awesome solution, @DGM

[Karthik Nagarajan]

@DGM I would like to seek clarification regarding the following code :

% these are example query points [x y]
nqp = 30;
datalimits = [50 25];
qp = [linspace(12.5,30,nqp); linspace(12.5,22.5,nqp)].' % in data space
qp(:,2) = datalimits(2)-qp(:,2);
qp = qp./datalimits.*[size(inpict,2) size(inpict,1)];

This seems to assume that the edges of the grid coincide with the corner pixels of the image. However, this is not the case for the image that I am working with. For example, the point with Cartesian coordinates (3.2,0.7) lies within one of the object boundaries. However, running the following code

nqp = 30;
datalimits = [10 5];
qp = [3.2 0.7]; % point within an object boundary
qp(:,2) = datalimits(2)-qp(:,2);
qp = qp./datalimits.*[size(inpict,2) size(inpict,1)]; % in image space

% test query points for blob membership
L = bwlabel(inpict);
qp = round(qp);
inblob = zeros(size(qp,1),1);
for p = 1:size(qp,1)
    inblob(p) = L(qp(p,2),qp(p,1));
end
inblob

yields inblob = 0. Is there a way to resolve this issue?

[DGM]

I'm assuming the corner pixels are the extent of the plot box -- because the image I'm working with has been cropped down manually to the plot box (see attached image). Using your data extents and qp, it returns inblob=4. I mentioned it, but I should've included the image.

It's not in the code because I just threw it into GIMP and cropped it out. For one-off image repair of low technical importance, it would typically be far easier to just do all the image cleanup in a regular image manipulation environment than it would be to concoct a bunch of filtering procedures as I demonstrated. Not everything has to be done in Matlab, especially tasks that are arguably outside the scope of the assigned work. At least that's my opinion.

[Karthik Nagarajan]

@DGM Thank you very much. Your answer not only solved my problem but also enabled me to better understand the functionality in the Image Processing Toolbox, which I had never used previously.