how to find contour inflection points?

Hi, i have a bw image describing a shape contour. How find the coordinates of inflection points? And then, how plot the fingerprint representarion? Thanks to all!!!

Answer 1

[Bjorn Gustavsson]

Inflection points ought to be rather simple to calculate (function below should get the job done), but the actual contour-lines returned from contour et al. might have a rather large number of inflection-points as you can verify by looking at the example.

HTH,

function r_inflections = contourinflectionpoints(C,fK)
% CONTOURINFLECTIONPOINTS - find inflection-points on contourlines 
%  CONTOURINFLECTIONPOINTS identifies inflection points on
%  contourlines by identifying line-segments where the curvature
%  changes direction. Each contourline is interpreted as a number
%  of connected straight-line-segments and an inflection-point is
%  identified as the mid-point of a line-segment where the
%  neihbouring points fall on opposite sides of the extension of
%  the line-segment.
% 
% Calling:
%   r_inflections = contourinflectionpoints(C,fK)
% Input:
%   C  - contourline matrix as returned by contourc or the
%        contour-family of functions on the format:
%        C = [level1 x1 x2 x3 ... level2 x2 x2 x3 ...;
%             pairs1 y1 y2 y3 ... pairs2 y2 y2 y3 ...]
%   fK - filter-factors used to smoothen the contour-lines (simple
%        experimentation reveal that contourlines can have a large
%        number of spurious inflection-points, smoothing of the
%        contour-lines reduces this problem, user tuning required).
% Output:
%   r_inflections - [n x 2] double array with identified
%                   inflection-points. 
% 
% Example:
%   M = peaks(127);
%   C = contour(M,8);
%   r_i = contourinflectionpoints(C);
%   fK = [1/2,1,1/2]/2;
%   r_s = contourinflectionpoints(C,fK);
%   hold on
%   plot(r_i(:,1),r_i(:,2),'b.')
%   plot(r_s(:,1),r_s(:,2),'ro','linewidth',3)
% 
% No argument checks or error-controls, if you want that you have
% to pay me good money.

% Copyright © B. Gustavsson 20140530, GPL version 3 or later applies

%%Extract the individual contour-lines
iC = 1;
idxC = 1;
while iC < size(C,2)
nP = C(2,iC); % number of points in current contour
xC{idxC} = C(1,iC+(1:nP)); % x coordinates of current contour
yC{idxC} = C(2,iC+(1:nP)); % y coordinates of current contour
if nargin > 1 && ~isempty(fK)
  xC{idxC} = filtfilt(fK/sum(fK),1,xC{idxC});
  yC{idxC} = filtfilt(fK/sum(fK),1,yC{idxC});
end
iC = iC+nP+1;    % Start-point of next contour
idxC = idxC + 1; % next contourline index
% plot(xC{idxC-1},yC{idxC-1},'b.-')
% pause
end

iInflections = 1;
for iC = 1:length(xC),

for iP = 2:(length(xC{iC})-2)
  % First take 2 points on the current contour :
  r0 = [xC{iC}(iP);yC{iC}(iP)];
  r1 = [xC{iC}(iP+1);yC{iC}(iP+1)];
  % let them define a stratight line on the form: 
  % dot(r,e_n) - 1 = 0
  e_n = [cos(pi/2) sin(pi/2);-sin(pi/2) cos(pi/2)]*(r1-r0)/norm(r1-r0);
  l = dot(r0,e_n);
  % the points on the contour on either side of the line-segment:
  r_p = [xC{iC}(iP+2);yC{iC}(iP+2)];
  r_m = [xC{iC}(iP-1);yC{iC}(iP-1)];
  % lengths along e_n to points r_p and r_m
  l_p = dot(r_p,e_n);
  l_m = dot(r_m,e_n);
  % if they are on either side of the line-segment then we have
  % an inflection point
  if (l_p - l)*(l_m - l) <0
    % take the mid-point of that line-segment as the
    % inflection-point, change this according to taste...
    r_inflections(iInflections,:) = (r0+r1)'/2;
    iInflections = iInflections + 1;
  end
end
end

Answer 2

[Image Analyst]

See the FAQ: http://matlab.wikia.com/wiki/FAQ#How_do_I_find_.22kinks.22_in_a_curve.3F

[Image Analyst]

See this: http://www.mathworks.com/matlabcentral/fileexchange/32696-2d-line-curvature-and-normals

and other similar submissions on http://www.mathworks.com/matlabcentral/fileexchange/index?term=authorid%3A29180

Answer 3

[Alessandro]

Hi, thanks for responses! I don't know (and still understand) the 'countour'/'contourc' Matlab function.... I have not regular shapes (triangles, squares, etc...), in my situation i have just a bw image (obtained from such edge detection filters and others..) and i just need to locate the inflection points of a shape in orther to make a descriptor for it. Can i use contour functions also in this situation?... i didn't understand what contour function does with just a bw image.

To be more clear, i need something like figure 3) and 4) of this page http://vgg.fiit.stuba.sk/wordpress/2013-04/css-%E2%80%93-curvature-scale-space-in-opencv/.

[Bjorn Gustavsson]

Well, why don't you first run my example and see what it does for you. Then try to figure out a way to identify/extract your contour-line from your binary image/data and modify the function. Or do the same for the function in the link Image Analyst submitted. Have a go at something...

[Alessandro]

Yes i tried... but i find a lot of points! how can i figure out? (i'm still studying your code)

[Image Analyst]

See http://en.wikipedia.org/wiki/Morphometrics to see if any of those shape description methods work for you.

[Alessandro]

Ok, i understand until you define a straight line between r0 an r1... i've understand you take r0=(xi,yi), r1=(xi+1,yi+1),r_p=(xi+2,yi+2) and rm=(xi-1,yi-1), then you catch an inflection point if the product (l_p -l)(l_m-l) is less than zero.... but i don't understand the meaning of e_n and l..

[Alessandro]

Ok... maybe I am.. l is the line that connect r0 and r1, if rm and rp are both under or both up from this line i have an inflection in the middle of r0 and r1... so for my application i could augment the distance of these points

[Alessandro]

Ok... i got it!!... but i still don't understand the mathematical meaning og e_n and l. Thanks a lot!!