I dont know what does this means,

Plot the MPP for each image.

[Sean de Wolski]

Neither do I. And I am guessing Google's first few results aren't what you are looking for.

Answer 1

[Image Analyst]

I have code for a "restricted convex hull" and include demo code for that below. It's like the convex hull but allows the hull to follow the outline into some concave parts of the shape. You specify a parameter that says how tightly the shape hugs the actual outline.

% 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 Demo by ImageAnalyst','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!'));

There is also something called "concave hull" http://www.concavehull.com/home.php?main_menu=2 I haven't used it but from the pictures it looks similar to alpha shapes http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html

Answer 2

[Walter Roberson]

minimum perimeter polygon

[Sean de Wolski]

So the convex hull?

[Walter Roberson]

Apparently not: it can be non-convex.

Apparently until 2006 there was no known polynomial time algorithm for MPP, and at first look the polynomial time algorithm does not appear to be recognized.

[Shoaib Akhtar]

Hi, Is there any function in matlab to calculate minimum perimeter polygon.

[Image Analyst]

I have a hard time envisioning how a non-convex polygon will have a smaller perimeter than its convex hull. Perhaps someone can supply an example.

[Walter Roberson]

Shoaib: No, there is no built-in function to calculate mpp. It appears to be an open research question of how to do it in a reasonable time.

IA: see the above link labled "non-convex"; it has an example right at the beginning.

[Image Analyst]

I did. The convex hull would have a shorter length than the solid black line they show, so that's what I don't understand. How can they say that solid black line is more "minimum" than the convex hull?

[Walter Roberson]

The topic is a new one on me.

I found a page that describes it as "Minimum perimeter polygons  cover boundary  by cells (pixels) of chosen size and force a rubber  band to fit inside the cells."

Looking at the example there (which turns out to be the same as the one above), it appears that one pixelizes the boundary outline and then finds the minimal perimeter polygon where each polygon edge cannot go outside the boundary outline pixels (but the polygon can pass immediately against the edge of pixels.) The pixel list doesn't change, but the representation does.

[Image Analyst]

Fairly new to me too. But your latest description kind of sounds to me like a type of snake (active contour) that I've heard called "balloons." With that, it's like you have an inflatable balloon in your background and you start to blow it up. As it inflates, it will get closer and closer to the object perimeter but not go inside. The less you inflate it the less closely it hugs the object perimeter and the more you inflate the balloon the closer it gets and more closely fills the nooks and crannies of the object perimeter. It's a way of getting a smoothed perimeter of objects. Useful if you know the perimeter should be smooth, like for most internal human organs.

[Image Analyst]

After looking at the diagram some more, it looks like the polygon in the "MPP" concept is constrained to lie internal to the pixels. The lines don't leave the boudnaries of the pixels, if you consider each pixel like a box. You see where you can draw a straight line within the existing boundary pixels and keep track of those polygons (most will be lines I would think). This is different than other methods where you will get new, smoother perimeters that have new pixels different than the original pixels.