Image Edges: Calculate complexity of a line segment?

Can anyone suggest a good way to calculate the 'complexity' of a line segment (obtained from 'bwlabel' after 'canny' edge detection).

I want to define 'complexity' in 2 parts:

1. How straight the line is
2. How long the line is

and would like to weight each line segment such that a long and straight line is more favourable than a short and wavy line.

It is ok for the line to change direction so long as they do not change direction regularly (for example, a large square is fine because it is made up of 4 'simple' straight lines). However, edges corresponding to leaves on a tree for example are not good because they change direction too much.

As mentioned, I have used 'bwlabel' after 'canny' edge detection. I then want to iterate through each bwlabel number independently and rank them in order of how (predominately) straight and long they are.

Many thanks for your help!

Answer 1

[Ashish Uthama]

(I'll try to flesh this soon) How about:

• Obtain the PixelList property of each line using regionprops
• Compute the difference in location between pixels (gives you an idea of how much the line wiggles)
• Maybe take the mean of this difference
• And weight it with the number of pixels in this segment

[Walter Roberson]

In a line that curves, you can get pixel lists where the list does not follow the "outside" (or "inside") of the curve. For example,

.x..

xxx.

x..x

then the ordering of the pixels in the section that touches itself is not necessarily going to "thread" the line.

It might make more sense to use http://www.mathworks.com/help/toolbox/images/ref/bwtraceboundary.html as at least then you know the order of the tracing.

Answer 2

[Image Analyst]

Usually the tortuosity ( http://en.wikipedia.org/wiki/Tortuosity) is what is used. I think it's sometimes called "curl" when dealing with fibers. It is the ratio of the length to the distance between the endpoints. A number of alternative definitions are also discussed on that web page.

You can also use fractal dimension ( http://en.wikipedia.org/wiki/Fractal_dimension).

[Philip]

Thanks! I have used the simplest form of Tortuosity (length of line / distance between endpoints of the line), and this has helped to some extent... but when ordering the tortuosity of each line segment in ascending/descending order, it does not return results that are quite what I was hoping for.

I have attached an edge image (http://imageshack.us/photo/my-images/27/edgese.png/) with 6 line segments. I would hope that the line segment corresponding to the near vertical line (towards the right of the image) should have the highest tortuosity as it is closest to a straight line. Then I would expect to see the 3 line segments corresponding to the large wavy lines to appear next, followed by the 2 small horizontal blocks at the edge of the image... I think I will need to weight the tortuosity in favour of long lines that do not deviate much, but I am not sure how to...

Here is how I calculate tortuosity:

img = imread('edges.png');

canny_edges = edge(img,'canny');

[LS, qty] = bwlabel(canny_edges,8);

for i=1:qty

[xcoords ycoords] = find(LS==i);

route = bwtraceboundary(LS,[xcoords(1),ycoords(1)],'W',8,length(xcoords),'clockwise');

% Tortuoisity: ratio of length(route) / distance between start/endpoints

% distance = sqrt((x2-x1)^2 + (y2-y1)^2)

len = length(route);

dist = sqrt((route(end,2)-route(1,2))^2 + (route(end,1)-route(1,1))^2);

tort = len/dist;

profile(i,1) = i;

profile(i,2) = tort;

end

profile_sorted = sortrows(profile,-2);

[Image Analyst]

Not how I'd do it. How did you get x1 and x2? I'd call bwmorph to get the endpoints, then calculate the distance for each labeled object. Then get the histogram - use as many bins as there are objects. This will get you the sum of all the lengths of all the lines in just one line of code: perimeters = hist(LS, qty). Then divide them. Sort them if desired.

[Philip]

x1 and x2 are obtained from the output of 'bwtraceboundary.' x1 = route(1,1); x2 = route(end,1); y1 = route(1,2); y2 = route(end,2);

Sorry, can I ask you to elaborate on what you mean when you say you would use 'bwmorph' to get the endpoints? And also, what do you mean by "then divide them"? Do you mean divide the lengths of each line with the corresponding distance between endpoints? or something else?

Answer 3

[Image Analyst]

Philip: Alright, try this code:

clc;    % Clear the command window.
close all;  % Close all figures (except those of imtool.)
imtool close all;  % Close all imtool figures.
clear;  % Erase all existing variables.
workspace;  % Make sure the workspace panel is showing.
fontSize = 20;

% Change the current folder to the folder of this m-file.
if(~isdeployed)
  cd(fileparts(which(mfilename)));
end
  
% Check that user has the Image Processing Toolbox installed.
hasIPT = license('test', 'image_toolbox');
if ~hasIPT
  % User does not have the toolbox installed.
  message = sprintf('Sorry, but you do not seem to have the Image Processing Toolbox.\nDo you want to try to continue anyway?');
  reply = questdlg(message, 'Toolbox missing', 'Yes', 'No', 'Yes');
  if strcmpi(reply, 'No')
    % User said No, so exit.
    return;
  end
end

% Read in a standard MATLAB gray scale demo image.
folder = 'C:\Users\Philip\Documents\Temporary';
baseFileName = 'edgese.png';
fullFileName = fullfile(folder, baseFileName);
% Get the full filename, with path prepended.
fullFileName = fullfile(folder, baseFileName);
if ~exist(fullFileName, 'file')
  % Didn't find it there.  Check the search path for it.
  fullFileName = baseFileName; % No path this time.
  if ~exist(fullFileName, 'file')
    % Still didn't find it.  Alert user.
    errorMessage = sprintf('Error: %s does not exist.', fullFileName);
    uiwait(warndlg(errorMessage));
    return;
  end
end
grayImage = imread(fullFileName);
% Get the dimensions of the image.  numberOfColorBands should be = 1.
[rows columns numberOfColorBands] = size(grayImage);
% Display the original gray scale image.
subplot(2, 2, 1);
imshow(grayImage, []);
title('Original Image', 'FontSize', fontSize);
% Enlarge figure to full screen.
set(gcf, 'units','normalized','outerposition',[0 0 1 1]);
set(gcf,'name','Demo by ImageAnalyst','numbertitle','off') 

binaryImage = grayImage > 0;
[labeledImage numberOfLines] = bwlabel(binaryImage);
fprintf('numberOfLines = %d\n', numberOfLines);
endpoints = bwmorph(binaryImage, 'endpoints');

subplot(2, 2, 2);
imshow(endpoints, []);
title('Endpoints Image', 'FontSize', fontSize);
% Number of Endpoints should = 2 * numberOfLines because each line will have two endpoints.
numberOfEndpoints = sum(endpoints(:));
fprintf('numberOfEndpoints = %d\n', numberOfEndpoints);

% Find the length of each line
lineLengths = histc(labeledImage(:), 1:numberOfLines)
% Find the endpoints for each
% Then find the distance and the tortuosity.
for lineNumber = 1 : numberOfLines
  theseEndpoints = (labeledImage .* endpoints) == lineNumber;
  subplot(2, 2, 3);
  imshow(theseEndpoints, []);
  caption = sprintf('Endpoints for line #%d', lineNumber);
  title(caption, 'FontSize', fontSize);
  drawnow;
  [rows columns] = find(theseEndpoints);
  distanceBetweenEndpoints = sqrt((rows(1)-rows(2))^2 + (columns(1)-columns(2))^2);
  tortuosity(lineNumber) = lineLengths(lineNumber) / distanceBetweenEndpoints;
  fprintf('For line #%d,  curve length = %.2f, distance = %.2f,tortuosity = %.3f\n',...
    lineNumber, lineLengths(lineNumber), distanceBetweenEndpoints, tortuosity(lineNumber));
end

[Philip]

Thanks for all your help!! I just ran your code, and I get the same ordering as with my version (when sorting the tortuosity and label id) - labels: 1,4,3,6,5,2.

However, I'm not sure why label 4 (the vertical line towards the right of the image), does not have the highest value. It is clearly the straighter than label 1... Can you think of any reason for this, or perhaps a way to weight the tortuosity data such that it favours the straighter line?

[Philip]

UPDATE: the problem with bwlabel == 1 seems to be that the straight line distance is 50 pixels, and the actual length of the line is 51 pixels; this is why the tortuoisity comes out as though it is a pretty much a straight line (even though it is not).

is there a way to get a 'fitness' of the theoretical shortest (straight) distance to the end points, vs. the actual line? I am finding this difficult, since for the most part, the straight line contains fewer coordinates than the actual line...

[Image Analyst]

You might have to subtract one if you want center-to-center. The sum method used by the histc routine counts pixels. How long is this line:

0 0 1 1 1 0 0 0

Is it 3 long (total length, summed), or is it 2 long (center to center)? I hope you get the idea.

[Philip]

Thanks! Yes, I already made this change today... In your example, the line length is 2, and the distance to/from the endpoints is also 2. So the tortuosity is 1. The tortuosity will indeed always be 1 when the line is straight - this wasn't true before subtracting 1.

The problem I have now is that the following two lines yield the same tortuoisty, even though one is clearly straighter than the other.

0 0 1 1 1 1 1 1 1 1 1 1 0 0

and.

0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 1 0 0 0 0 0 0

0 0 0 0 0 1 0 0 1 0 0 0 0 0

0 0 0 0 1 0 0 0 0 1 0 0 0 0

0 0 0 1 0 0 0 0 0 0 1 0 0 0

0 0 1 0 0 0 0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0

In both cases, the lineLength = 9, and the distance between endpoints = 9, so the tortuosity = 9/9 = 1 (i.e. a straight line). Can you suggest a solution that maybe combines the tortuosity with some other data such that these two lines would be regarded as different?

[Image Analyst]

Yeah, I forgot about the diagonals would still have the same number of pixels even though the distance is sqrt(2) times as long. I'll have to think about that. There doesn't seem to be an alternate perimeter measurement (that I can think of off the top of my head) like there is for area (in bwarea which counts "partial pixels").

[Philip]

yeah, it sure is a tricky one... i can't even think of something to code from scratch. I tried assigning numbers to the path along the line (from pixel to pixel) using the coordinates obtained from bwtraceboundaries (i.e. if North then 1; if NE then 2; if W then 3 etc...) I then get the histogram (1:8 bins) of this data to see what the most popular direction is. I then work out the popularity of this direction as a percentage of the length of the line (a straight line would yield 100 here). I'm having some success with separating the two cases mentioned above if I add the percentage popularity figure to the tortuosity value. However, after some brief testing, it seems that the bwtraceboundary function doesn't always pick an endpoint of the line as the starting position of the trace - and it causes obvious problems when this happens.

[Image Analyst]

Philip: the perimeter computed by regionprops() seems to go center to center and so will work with slanted lines. Here, try this code

binaryImage = logical([...

0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 1 1 1 1 1 1 1 1 1 1 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 1 0 0 0 0 0 0

0 0 0 0 0 1 0 0 1 0 0 0 0 0

0 0 0 0 1 0 0 0 0 1 0 0 0 0

0 0 0 1 0 0 0 0 0 0 1 0 0 0

0 0 1 0 0 0 0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 ])

[labeledImage numberOfRegions] = bwlabel(binaryImage)

fprintf('numberOfRegions = %d\n', numberOfRegions);

measurements = regionprops(binaryImage, 'Perimeter', 'area');

allPerimeters = [measurements.Perimeter]/2

allAreas = [measurements.Area]

I trust you can apply this code to my earlier code to get the tortuosity with this perimeter array.

[Image Analyst]

By the way, make sure your blobs have been skeletonized first (use bwmorph) so that they are only a single pixel wide.

[Philip]

Thanks, I have dropped that code into your previous demo, and it seems to be very fast and reliable. I'm trying to see if I can use the 'perimeter' data to help with measuring straight vs. diagonal lines (as per the example above). It seems that the perimeter data returns odd results for more complex lines, which may not be useful for some images that are processed.