{"id":2701,"date":"2017-09-29T16:23:01","date_gmt":"2017-09-29T20:23:01","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/?p=2701"},"modified":"2019-11-01T17:17:21","modified_gmt":"2019-11-01T21:17:21","slug":"feret-diameter-introduction","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2017\/09\/29\/feret-diameter-introduction\/","title":{"rendered":"Feret Diameter: Introduction"},"content":{"rendered":"

This is the first of a few blog posts about object measurements based on a concept called the Feret diameter<\/i>, sometimes called the caliper diameter<\/i>. The diagram below illustrates the concept. Place the object to be measured inside the jaws of a caliper, with the caliper oriented at a specified angle. Close the jaws tightly on the object while maintaining that angle. The distance between the jaws is the Feret diameter at that angle.<\/p>

\"\" <\/p>

Eventually, we'll examine several related measurements (and algorithms for computing them), like these.<\/p>

\"\" <\/p>

Today, though, I'm just going to play around with a very small binary image. (Note: the pixelgrid<\/tt> function is a utility that I wrote. It's at the bottom of this post.)<\/p>

bw = [ ...<\/span>\r\n    0   0   0   0   0   0   0   0   0   0   0\r\n    0   0   0   0   0   0   0   0   0   1   0\r\n    0   0   0   0   0   0   1   1   1   1   0\r\n    0   0   0   0   0   1   1   1   1   0   0\r\n    0   0   0   1   1   1   1   1   1   0   0\r\n    0   0   1   1   1   0   0   0   0   0   0\r\n    0   0   1   1   1   0   0   0   0   0   0\r\n    0   0   0   0   0   0   0   0   0   0   0\r\n    0   0   0   0   0   0   0   0   0   0   0 ];\r\n\r\n\r\nimshow(bw)\r\npixelgrid\r\n<\/pre>\"\" 
I want to brute-force my to finding the two corners of the white blob that are farthest apart. Let's start by finding all the pixel corners. (I'll be using implicit expansion<\/a> here, which works in R2016b or later.)<\/p>
[y,x] = find(bw);\r\nhold on<\/span>\r\nplot(x,y,'xb'<\/span>,'MarkerSize'<\/span>,5)\r\ncorners = [x y] + cat(3,[.5 .5],[.5 -.5],[-.5 .5],[-.5 -.5]);\r\ncorners = permute(corners,[1 3 2]);\r\ncorners = reshape(corners,[],2);\r\ncorners = unique(corners,'rows'<\/span>);\r\nplot(corners(:,1),corners(:,2),'sr'<\/span>,'MarkerSize'<\/span>,5)\r\nhold off<\/span>\r\n<\/pre>\"\" 
Well, let's get away from pure brute force just a little. We really only need to look at the points that are part of the convex hull<\/i> of all the corner points.<\/p>
hold on<\/span>\r\nk = convhull(corners);\r\nhull_corners = corners(k,:);\r\nplot(hull_corners(:,1),hull_corners(:,2),'r'<\/span>,'LineWidth'<\/span>,3)\r\nplot(hull_corners(:,1),hull_corners(:,2),'ro'<\/span>,'MarkerSize'<\/span>,10,'MarkerFaceColor'<\/span>,'r'<\/span>)\r\nhold off<\/span>\r\n<\/pre>\"\" 
Now let's find which two points on the convex hull are farthest apart.<\/p>
dx = hull_corners(:,1) - hull_corners(:,1)';\r\ndy = hull_corners(:,2) - hull_corners(:,2)';\r\npairwise_dist = hypot(dx,dy);\r\n[max_dist,j] = max(pairwise_dist(:));\r\n[k1,k2] = ind2sub(size(pairwise_dist),j);\r\n\r\npoint1 = hull_corners(k1,:);\r\npoint2 = hull_corners(k2,:);\r\nhold on<\/span>\r\nplot([point1(1) point2(1)],[point1(2) point2(2)],'-db'<\/span>,'LineWidth'<\/span>,3,'MarkerFaceColor'<\/span>,'b'<\/span>)\r\nhold off<\/span>\r\n<\/pre>\"\" 
And the maximum distance is ...<\/p>
max_dist\r\n<\/pre>
\r\nmax_dist =\r\n\r\n    10\r\n\r\n<\/pre>
(I thought I had made a mistake when I first saw this number come out to be an exact integer. But no, the answer is really 10.)<\/p>
That's a pretty good start. I don't know exactly where I'll go with this topic next time. I'm making it up as I go.<\/p>
function<\/span> hout = pixelgrid(h)\r\n%pixelgrid Superimpose a grid of pixel edges on an image<\/span>\r\n%   pixelgrid superimposes a grid of pixel edges on the image in the<\/span>\r\n%   current axes.<\/span>\r\n%<\/span>\r\n%   pixelgrid(h_ax) superimposes the grid on the image in the specified<\/span>\r\n%   axes.<\/span>\r\n%<\/span>\r\n%   pixelgrid(h_im) superimposes the grid on the specified image.<\/span>\r\n%<\/span>\r\n%   group = pixelgrid(___) returns an hggroup object that contains the two<\/span>\r\n%   lines that are used to draw the grid. One line is thick and darker, and<\/span>\r\n%   the other is thin and lighter. Using two contrasting lines in this way<\/span>\r\n%   guarantees that the grid will be visible regardless of pixel colors.<\/span>\r\n%<\/span>\r\n%   EXAMPLES<\/span>\r\n%<\/span>\r\n%   Superimpose pixel grid on color image. Zoom in.<\/span>\r\n%<\/span>\r\n%       rgb = imread('peppers.png');<\/span>\r\n%       imshow(rgb)<\/span>\r\n%       pixelgrid<\/span>\r\n%       axis([440 455 240 250])<\/span>\r\n%<\/span>\r\n%   Change the colors and line widths of the pixel grid.<\/span>\r\n%<\/span>\r\n%       rgb = imread('peppers.png');<\/span>\r\n%       imshow(rgb)<\/span>\r\n%       h = pixelgrid;<\/span>\r\n%       axis([440 455 240 250])<\/span>\r\n%       h.Children(1).Color = [178 223 138]\/255;<\/span>\r\n%       h.Children(1).LineWidth = 2;<\/span>\r\n%       h.Children(2).Color = [31 120 180]\/255;<\/span>\r\n%       h.Children(2).LineWidth = 4;<\/span>\r\n%<\/span>\r\n%   LIMITATIONS<\/span>\r\n%<\/span>\r\n%   This function is intended for use when looking at a zoomed-in image<\/span>\r\n%   region with a relatively small number of rows and columns. If you use<\/span>\r\n%   this function on a typical, full-size image without zooming in, the<\/span>\r\n%   image will not be visible under the grid lines.<\/span>\r\n%<\/span>\r\n%   This function attempts to determine if MATLAB is running with a high<\/span>\r\n%   DPI display. If so, then it displays the pixel grid using thinner<\/span>\r\n%   lines. However, the method for detecting a high DPI display on works on<\/span>\r\n%   a Mac when Java AWT is available.<\/span>\r\n\r\n%   Steve Eddins<\/span>\r\n%   Copyright The MathWorks, Inc. 2017<\/span>\r\n\r\nif<\/span> nargin < 1\r\n    him = findobj(gca,'type'<\/span>,'image'<\/span>);\r\nelseif<\/span> strcmp(h.Type,'axes'<\/span>)\r\n    him = findobj(h,'type'<\/span>,'image'<\/span>);\r\nelseif<\/span> strcmp(h.Type,'image'<\/span>)\r\n    him = h;\r\nelse<\/span>\r\n    error('Invalid graphics object.'<\/span>)\r\nend<\/span>\r\n\r\nif<\/span> isempty(him)\r\n    error('Image not found.'<\/span>);\r\nend<\/span>\r\n\r\nhax = ancestor(him,'axes'<\/span>);\r\n\r\nxdata = him.XData;\r\nydata = him.YData;\r\n[M,N,~] = size(him.CData);\r\n\r\nif<\/span> M > 1\r\n    pixel_height = diff(ydata) \/ (M-1);\r\nelse<\/span>\r\n    % Special case. Assume unit height.<\/span>\r\n    pixel_height = 1;\r\nend<\/span>\r\n\r\nif<\/span> N > 1\r\n    pixel_width = diff(xdata) \/ (N-1);\r\nelse<\/span>\r\n    % Special case. Assume unit width.<\/span>\r\n    pixel_width = 1;\r\nend<\/span>\r\n\r\ny_top = ydata(1) - (pixel_height\/2);\r\ny_bottom = ydata(2) + (pixel_height\/2);\r\ny = linspace(y_top, y_bottom, M+1);\r\n\r\nx_left = xdata(1) - (pixel_width\/2);\r\nx_right = xdata(2) + (pixel_width\/2);\r\nx = linspace(x_left, x_right, N+1);\r\n\r\n% Construct xv1 and yv1 to draw all the vertical line segments. Separate<\/span>\r\n% the line segments by NaN to avoid drawing diagonal line segments from the<\/span>\r\n% bottom of one line to the top of the next line over.<\/span>\r\nxv1 = NaN(1,3*numel(x));\r\nxv1(1:3:end) = x;\r\nxv1(2:3:end) = x;\r\nyv1 = repmat([y(1) y(end) NaN], 1, numel(x));\r\n\r\n% Construct xv2 and yv2 to draw all the horizontal line segments.<\/span>\r\nyv2 = NaN(1,3*numel(y));\r\nyv2(1:3:end) = y;\r\nyv2(2:3:end) = y;\r\nxv2 = repmat([x(1) x(end) NaN], 1, numel(y));\r\n\r\n% Put all the vertices together so that they can be drawn with a single<\/span>\r\n% call to line().<\/span>\r\nxv = [xv1(:) ; xv2(:)];\r\nyv = [yv1(:) ; yv2(:)];\r\n\r\nhh = hggroup(hax);\r\ndark_gray = [0.3 0.3 0.3];\r\nlight_gray = [0.8 0.8 0.8];\r\n\r\nif<\/span> isHighDPI\r\n    bottom_line_width = 1.5;\r\n    top_line_width = 0.5;\r\nelse<\/span>\r\n    bottom_line_width = 3;\r\n    top_line_width = 1;\r\nend<\/span>\r\n\r\n% When creating the lines, use AlignVertexCenters to avoid antialias<\/span>\r\n% effects that would cause some lines in the grid to appear brighter than<\/span>\r\n% others.<\/span>\r\nline(...<\/span>\r\n    'Parent'<\/span>,hh,...<\/span>\r\n    'XData'<\/span>,xv,...<\/span>\r\n    'YData'<\/span>,yv,...<\/span>\r\n    'LineWidth'<\/span>,bottom_line_width,...<\/span>\r\n    'Color'<\/span>,dark_gray,...<\/span>\r\n    'LineStyle'<\/span>,'-'<\/span>,...<\/span>\r\n    'AlignVertexCenters'<\/span>,'on'<\/span>);\r\nline(...<\/span>\r\n    'Parent'<\/span>,hh,...<\/span>\r\n    'XData'<\/span>,xv,...<\/span>\r\n    'YData'<\/span>,yv,...<\/span>\r\n    'LineWidth'<\/span>,top_line_width,...<\/span>\r\n    'Color'<\/span>,light_gray,...<\/span>\r\n    'LineStyle'<\/span>,'-'<\/span>,...<\/span>\r\n    'AlignVertexCenters'<\/span>,'on'<\/span>);\r\n\r\n% Only return an output if requested.<\/span>\r\nif<\/span> nargout > 0\r\n    hout = hh;\r\nend<\/span>\r\n\r\nend<\/span>\r\n\r\nfunction<\/span> tf = isHighDPI\r\n% Returns true if running with a high DPI default display.<\/span>\r\n%<\/span>\r\n% LIMITATION: Only works on a Mac with Java AWT available. In other<\/span>\r\n% situations, this function always returns false.<\/span>\r\ntf = false;\r\nif<\/span> ismac\r\n    if<\/span> usejava('awt'<\/span>)\r\n        sf = java.awt.GraphicsEnvironment.getLocalGraphicsEnvironment().getDefaultScreenDevice.getScaleFactor();\r\n        tf = sf > 1;\r\n    end<\/span>\r\nend<\/span>\r\nend<\/span>\r\n<\/pre>