Identify all co-linear line segments (in matlab)

Question

I have posted a related but not the same question here https://stackoverflow.com/questions/8279698/measuring-length-of-dna-fibers-from-an-image-of-single-molecules

Background: I have many images that look like this:

I would like to identify all line segments that are co-linear and then measure the length of these segments. In the image above there are 3 pairs of segments that are on an imaginary line with a negative slope. The line segment that is the longest does not have a pair so it would not be considered i.e. there must be atleast 2 segments that are colinear.

I get the following:

I  = imread('http://dl.dropbox.com/u/18072545/c_39_green.tif'); 
BW = edge(I,'canny');
[H,T,R] = hough(BW);
NUMPEAKS=15;
PEAKTHRESHOLD= 80; 
SUPPRESSNHBR=[40 40];
P  = houghpeaks(H,NUMPEAKS,'threshold',PEAKTHRESHOLD,'NHoodSize',SUPPRESSNHBR); 
MINLENGTH_OF_SEGMENT=50;
GAPLENGTH_TO_MERGE=30;
lines = houghlines(BW,T,R,P,'FillGap',GAPLENGTH_TO_MERGE,'MinLength',MINLENGTH_OF_SEGMENT);
max_len = 0;
figure, imshow(I), hold on
for k = 1:length(lines)
  xy = [lines(k).point1; lines(k).point2];
  plot(xy(:,1),xy(:,2),'LineWidth',2,'Color','green');
  plot(xy(1,1),xy(1,2),'x','LineWidth',2,'Color','yellow');
  plot(xy(2,1),xy(2,2),'x','LineWidth',2,'Color','red');
end

I had to play around with the parameters in order to get a reasonable performance (though I am unable to find a parameter that will capture the starting bit of the segment that is at the bottom). However, I am unable to avoid finding multiple segments that are overlapping.

Can someone please help me 1. Prevent identification of overlapping segments. 2. Identify all the lines that are co-linear

Many thanks!

Title

(for 2:) could you just pick one segment, find its slope and check for others that are of similar (within some tolerance) slope? I know this doesn't take into account parallel segments, but you could try to use some sort of ROI defined by the slope +/- some tolerance to eliminate other segments from creating false positives. – Billingsgate

How will you treat a case with 3 co-linear segments, where the first segment and the second segment intersect? Do you need to consider both the set containing the first and the third and the set containing the second and the third segment? – Hugues

@Hugues When 2 segments intersect then they are part of the same segment (as such intersection is not common in our experiments). I am not sure however what strategy to use discard one of the two or more intersecting segments. Any ideas? – Title

Answer 1

This code finds co-linear groups of lines.

theta = zeros(length(lines),1);
rho   = zeros(length(lines),1);
for k = 1:length(lines)
  xy = [lines(k).point1; lines(k).point2];
  plot(xy(:,1),xy(:,2),'LineWidth',1,'Color','green');
  plot(xy(1,1),xy(1,2),'x','LineWidth',1,'Color','yellow');
  plot(xy(2,1),xy(2,2),'x','LineWidth',1,'Color','red');
  %text(xy(1,1),xy(1,2),['    ' num2str(k)],'fontsize',10,'color',[1 1 1]);
  theta(k) = lines(k).theta;
  rho(k) = lines(k).rho;
end

theta_tolerance = 2;
theta2 = abs(bsxfun(@minus, theta, theta')) <= theta_tolerance;
theta2(1:size(theta2,2)+1:numel(theta2)) = 0; % zero diagonal
rho_tolerance = 1;
rho2 = abs(bsxfun(@minus, rho, rho')) <= rho_tolerance;
rho2(1:size(rho2,2)+1:numel(rho2)) = 0; % zero diagonal
rhotheta2 = sparse(rho2 & theta2);
[nc, C] = graphconncomp(rhotheta2);


paired = ismember(C,find(hist(C,1:max(C))>1)); % paired lines
colors=get(gcf,'DefaultAxesColorOrder');
for line=find(paired)
    xy = [lines(line).point1; lines(line).point2];
    plot(xy(:,1),xy(:,2),':','LineWidth',4,'Color',colors(C(line),:));
    text(xy(1,1),xy(1,2),num2str(C(line)),'fontsize',20,'Color',colors(C(line),:));
end

It doesn't take care of overlapping. It is not clear how want to treat a case with 3 co-linear segments, where the first segment and the second segment intersect? Do you need to consider both the set containing the first and the third and the set containing the second and the third segment?

Hugues

Many thanks for your very helpful response. It almost answers my question. Only one issue remains -- any idea how to prevent identification of overlapping regions? For example, in your image the segments labelled 6 and 2 are actually the same segment--there appears to be a small deformation that confuses the line segment identification. Is it possible to modify the segment identification that – Title

My previous comment was incomplete. Many thanks for your very helpful response. Any idea how to prevent identification of overlapping regions? For example, in your image the segments labelled 6 and 2 are actually part of the same segment-- a small inflection confuses the houghline algorithm. Is it possible to modify the segment identification that will tolerate a bit of deformation? I am also not sure that even after identification of intersecting segments, how to decide which line to disregard? However, by visual inspection, it is clear that the there are only 3 pairs of line segments. – Title