Identifying and marking image regions

Hello all,

I have an image (original.png) that I need to separate regions where there are and are not these white dots. The final image should look something like (final.png).

I've tried playing with some image processing functions but because the spaces between the dots is so large relative to the size of the dots I can't find an effective way of filling in the spaces.

Original.png

Final.png

[Jeff]

I'm going to post the results of trying these different methods one at a time for future users to check out to see what will work best for their application. Check back as I update based on my results

1) IMCLOSE TECHNIQUE

Results - Takes a fair bit to set your thresholds. My steps were;

- Use 'canny' edgefinder

- imclose with a large 'disk' shape

- smooth the edges twice with 'diamond' tool and imerode

- created outline and applied gaussian filter to smooth the edges more

2) ALPHA SHAPES TECHNIQUE

Results - I didn't spend as much time setting my thresholds on this one.

- Find the (x,y) locations of your points that correspond to a certain pixel value (I just used a couple of loops because mine were either 0 or 1 if a dot was suppose to be there). This needs to be a matrix of 2 or 3 columns (depending on if doing 2 or 3d)

- Use alphavol on this matrix with appropriate thresholds

This method was pretty simple and fast to compute but it seems like it basically finds the outer boundary of your points. While this may be good for some applications it's not the best for mine which requires finding the location of maximum gradient of particles in my images.

3) CONVEX HULL TECHNIQUE

Results - This technique is only really useful if you just want the overall shape. As Image Analyst says, it's like wrapping a rubber band around your points and you miss the internal structure.

- Find (x,y) location of your points

- Use convhull

[Image Analyst]

There is no need for the Canny edge detector in that algorithm.

[Cedric]

Looking at your image with the convex hull .. it's worth what it's worth, but in a totally different context (GIS), I would build a buffer around points that I would dissolve, remove interior polygons, and clip with the convex hull.

Answer 1

[Image Analyst]

There are at least four ways that I can think of. One is to to an imclose() with a really big kernel - big enough so that the dots connect. Then use bwboundaries to find the "envelope."

The second way is to use alpha shapes: http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html. The File Exchange has submissions on alpha shapes, as well as snakes, active contours, balloons, or whatever you want to call them.

The third way is to use a "restricted" convex hull - something I've been after the Mathworks for years to add. I have a inefficient demo of that if you're interested. Basically it's kind of like the convex hull but it only looks within a certain distance to find convex points, so it has the effects of going into the little bays, nooks, and crannies more. So you'll get something like you showed in the red line, whereas a standard convex hull is just like you wrapped a rubber band around the points so that you will have no following of the points into bays.

The fourth way might be to calculate the Euclidean Distance transform with bwdist() and then threshold. I haven't tried this (just thought it up now) but it might work.

[Jeff]

Do you have the demo of the restricted convex hull that I could try and use?

Thanks

[Image Analyst]

I warn you that it's not the most efficient algorithm in the world:

% function RestrictedConvexHull()
% http://www.liacs.nl/~fverbeek/courses/iammv/scil_ref.pdf
% Demo to have the user click a bunch of vertex points and compute the restricted convex hull of those points.
% DESCRIPTION
% Calculate a restricted convex hull of each object in the image "in" and store
% the result in image "out". For each object in "in", all combinations of two contour
% points with Euclidean distance less than or equal to "dist", are connected by a straight
% line. If a background pixel is found on such a line, it is added to the original object.
% This operation closes all holes in an object which are less than "dist" wide. The
% contour of an object is also smoothed, because gaps with a length less than "dist" are
% completely filled.

clc;  % Clear command window.
clear;  % Delete all variables.
close all;  % Close all figure windows except those created by imtool.
imtool close all;  % Close all figure windows created by imtool.
workspace;  % Make sure the workspace panel is showing.
fontSize = 14;

% Change the current folder to the folder of this m-file.
if(~isdeployed)
        cd(fileparts(which(mfilename)));
end
set(gcf, 'Position', get(0,'Screensize')); % Enlarge figure to full screen.
set(gcf,'name','Spline Image Analysis Demo','numbertitle','off') 

grayImage = zeros(240,320);
subplot(2,2,1);
imshow(grayImage);
axis on;
xlabel('X', 'FontSize', fontSize);
ylabel('Y', 'FontSize', fontSize);
title('Your Points', 'FontSize', fontSize);
hold on
% Initially, the list of points is empty.
knots = [];
numberOfPointsClicked = 0;
% Prompt the user
message = sprintf('Left click to draw some vertex points in a "C" or "U" shape.\nRight click the final point to finish drawing.');
uiwait(msgbox(message));
buttonThatWasClicked = 1;
% Enter a loop asking user to click on the know vertexes.
while buttonThatWasClicked == 1
    [xKnot, yKnot, buttonThatWasClicked] = ginput(1);
    plot(xKnot, yKnot, 'ro', 'LineWidth', 2)
    numberOfPointsClicked = numberOfPointsClicked+1;
  % Make this coordinate a new column.
    knots(:, numberOfPointsClicked) = [xKnot; yKnot];
end

% Find all the distances between any point and any other point.
subplot(2,2,2);
set(gca,'YDir','reverse'); % Flip upside down so chart matches image.
numberOfLines = 0;
for k1 = 1 : numberOfPointsClicked
  %----- Burn line into image -----
  % Create line mask, h, as an ROI object over the second image in the bottom row.
  x1 = knots(1, k1);
  y1 = knots(2, k1);
  for k2 = k1 + 1 : numberOfPointsClicked
    x2 = knots(1, k2);
    y2 = knots(2, k2);
    numberOfLines = numberOfLines + 1;
    distance = sqrt((x2-x1) ^ 2 + (y2-y1) ^ 2);
    distances(numberOfLines) = distance;
    plot([x1 x2], [y1 y2], 'r-');
    hold on;
  end
end
set(gca,'YDir','reverse'); % Flip upside down so chart matches image.
% Display all the lines.
title('All Possible Lines Between All Points', 'FontSize', fontSize);

% Now get a histogram of the distances.
[count, distanceValues] = hist(distances);
subplot(2,2,3);
bar(distanceValues, count);
title('Histogram of distances between lines', 'FontSize', fontSize);
drawnow;

% Have user indicate the distance
subplot(2,2,1);  % Switch current axes to the upper left one.
userPrompt = sprintf('In the upper left image, indicate the longest distance between points that you would like to connect.\nLeft click the first point.\nRight click the second point.');
reply = questdlg(userPrompt,'Continue?', 'OK','Cancel', 'OK');
% reply = '' for Upper right X, 'OK','' for OK',', 'Cancel' for Cancel.
if strcmpi(reply, 'Cancel') || strcmpi(reply, '')
  return;
end

% Get the coordinates.
[xCoords yCoords lineProfile] = improfile;
plot([xCoords(1) xCoords(end)], [yCoords(1) yCoords(end)], 'y-', 'LineWidth', 2);  % Show the line again on the image (improfile doesn't leave it up there.)
minDistance = sqrt((xCoords(end) - xCoords(1)) ^ 2 + (yCoords(end) - yCoords(1)) ^ 2);
userPrompt = sprintf('The distance you specified is %.1f pixels.\nClick OK to compute the restricted convex hull.', minDistance);
reply = questdlg(userPrompt,'Continue?', 'OK','Cancel', 'OK');
% reply = '' for Upper right X, 'OK','' for OK',', 'Cancel' for Cancel.
if strcmp(reply, 'Cancel')
  return;
end
  
% Calculate the restricted convex hull
binaryImage = false(size(grayImage));
subplot(2,2,3);
imshow(binaryImage);
indexesToKeep = [];
for k1 = 1 : numberOfPointsClicked
  x1 = knots(1, k1);
  y1 = knots(2, k1);
  for k2 = k1 + 1 : numberOfPointsClicked
    x2 = knots(1, k2);
    y2 = knots(2, k2);

    distance = sqrt((x2-x1) ^ 2 + (y2-y1) ^ 2);
    if distance > minDistance
      continue;
    end
    indexesToKeep = [indexesToKeep k1 k2];
    hLine = imline(gca,[x1 x2],[y1 y2]); % Second argument defines line endpoints.
    % Create a binary image ("mask") from the ROI object.
    binaryImage2 = hLine.createMask();

    % Burn line into image by setting it to 255 wherever the mask is true.
    binaryImage(binaryImage2) = true;
  end
end
% Plot just the lines of the restricted convex hull.
subplot(2,2,3);
imshow(binaryImage, []);
caption = sprintf('Restricted Convex Hull Image with only lines shorter than %.1f', minDistance);
title(caption, 'FontSize', fontSize);

% Fill in the image to get a solid mask representing the restricted convex hull
subplot(2,2,4);
filledImage = imfill(binaryImage, 'holes');
imshow(filledImage, []);
title('Filled Restricted Convex Hull Image', 'FontSize', fontSize);

% Remove duplicates.
indexesToKeep = unique(indexesToKeep);
% Extract out just the restricted convex hull vertices from the list of all of them.
rchVertices = knots(:, indexesToKeep);
% Plot them in the original image.
subplot(2,2,1);
x = rchVertices(1, :);
y = rchVertices(2, :);
plot(x, y, 'gs');

uiwait(msgbox('Done with this Restricted Convex Hull demo!'));

[Jeff]

Thanks for your help Image Analyst. I have a follow-up question. How would I go about smoothing the borders that I made. So in this image, is there a way to make the borders a little smoother?

Thanks

[Image Analyst]

You could try splines with extra, smoothed coordinates in between. Run my demo: http://www.mathworks.com/matlabcentral/answers/73917#answer_83836

Answer 2

[Sean de Wolski]

The concave hull is by definition ill-defined without some other knowledge.

See this thread for more information and specifically Steven Lord's reply:

Newsreader thread on concave hull