1 | % LINESEG - Form straight line segements from an edge list. |
---|
2 | % |
---|
3 | % Usage: [seglist, nedgelist] = lineseg(edgelist, tol, angtol, linkrad) |
---|
4 | % |
---|
5 | % Arguments: edgelist - Cell array of edgelists (row col) coords. |
---|
6 | % tol - Maximum deviation from straight line before a |
---|
7 | % segment is broken in two (measured in pixels). |
---|
8 | % angtol - Angle tolerance used when attempting to merge line |
---|
9 | % segements (radians). |
---|
10 | % linkrad - Maximum distance between end points of line |
---|
11 | % segments for segments to be elegible for |
---|
12 | % linking (pixels). |
---|
13 | % angtol and linkrad are optional. If these parameters are omitted the |
---|
14 | % merging phase is omitted. |
---|
15 | % |
---|
16 | % Returns: seglist - an Nx4 array storing line segments in the form |
---|
17 | % [x1 y1 x2 y2 |
---|
18 | % x1 y1 x2 y2 |
---|
19 | % . . . ] etc |
---|
20 | % |
---|
21 | % nedgelist - a new cell array of edge lists where each edge list |
---|
22 | % corresponds to each segment in seglist above. The |
---|
23 | % edgelist is in row,column coords in the form |
---|
24 | % { [r1 c1 [r1 c1 etc } |
---|
25 | % r2 c2 ... |
---|
26 | % ... |
---|
27 | % rN cN] ....] |
---|
28 | % |
---|
29 | % * Note that a non-empty nedgelist is only returned if there is no segment |
---|
30 | % merging. |
---|
31 | % |
---|
32 | % This function takes each array of edgepoints in edgelist, finds the |
---|
33 | % size and position of the maximum deviation from the line that joins the |
---|
34 | % endpoints, if the maximum deviation exceeds the allowable tolerance the |
---|
35 | % edge is shortened to the point of maximum deviation and the test is |
---|
36 | % repeated. In this manner each edge is broken down to line segments, |
---|
37 | % each of which adhere to the original data with the specified tolerance. |
---|
38 | % |
---|
39 | % The optional final edge merging phase is provided because the initial |
---|
40 | % edge linking phase may have separated edges at `Y' junctions in the |
---|
41 | % image. The merging phase can reconnect broken branches. |
---|
42 | % Note however that the merging process can be slow. |
---|
43 | % |
---|
44 | % See also: EDGELINK, MAXLINEDEV, MERGESEG, DRAWSEG |
---|
45 | % |
---|
46 | |
---|
47 | % Copyright (c) 2000-2005 Peter Kovesi |
---|
48 | % School of Computer Science & Software Engineering |
---|
49 | % The University of Western Australia |
---|
50 | % http://www.csse.uwa.edu.au/ |
---|
51 | % |
---|
52 | % Permission is hereby granted, free of charge, to any person obtaining a copy |
---|
53 | % of this software and associated documentation files (the "Software"), to deal |
---|
54 | % in the Software without restriction, subject to the following conditions: |
---|
55 | % |
---|
56 | % The above copyright notice and this permission notice shall be included in |
---|
57 | % all copies or substantial portions of the Software. |
---|
58 | % |
---|
59 | % The Software is provided "as is", without warranty of any kind. |
---|
60 | |
---|
61 | % December 2000 - Original version |
---|
62 | % February 2003 - Added the returning of nedgelist data. |
---|
63 | |
---|
64 | % ** need to preallocate memory to improve speed *** |
---|
65 | |
---|
66 | function [linelist, nedgelist] = lineseg(edgelist, tol, angtol, linkrad, minLineLength) |
---|
67 | |
---|
68 | linelist = []; |
---|
69 | |
---|
70 | Nline = 0; |
---|
71 | Nedge = length(edgelist); |
---|
72 | |
---|
73 | if nargin == 2 |
---|
74 | merge = 0; |
---|
75 | else |
---|
76 | merge = 1; |
---|
77 | end |
---|
78 | |
---|
79 | for e = 1:Nedge |
---|
80 | y = edgelist{e}(:,1); |
---|
81 | x = edgelist{e}(:,2); |
---|
82 | |
---|
83 | fst = 1; % Indecies of first and last points in edge |
---|
84 | lst = length(x); % segment being considered. |
---|
85 | |
---|
86 | while fst<lst |
---|
87 | [m,i,d] = maxlinedev(x(fst:lst),y(fst:lst)); % Find size & posn of |
---|
88 | % maximum deviation. |
---|
89 | |
---|
90 | while m > tol % While deviation is > tol (m/d) ? |
---|
91 | lst = i+fst-1; % Shorten line to point of max deviation by adjusting lst |
---|
92 | [m,i,d] = maxlinedev(x(fst:lst),y(fst:lst)); |
---|
93 | end |
---|
94 | |
---|
95 | if d > minLineLength |
---|
96 | |
---|
97 | |
---|
98 | Nline = Nline+1; |
---|
99 | % Record line segment. Note that (c,r) corresponds to (x,y) |
---|
100 | linelist(Nline,:) = [x(fst) y(fst) x(lst) y(lst)]; |
---|
101 | |
---|
102 | % Record edgelist that corresponds to the segment. |
---|
103 | nedgelist{Nline} = [y(fst:lst) x(fst:lst)]; |
---|
104 | |
---|
105 | end |
---|
106 | |
---|
107 | % fst = lst+1; % Reset fst and lst. |
---|
108 | fst = lst; % make new fst match last lst so that segments |
---|
109 | % share endpoints. |
---|
110 | lst = length(x); |
---|
111 | end |
---|
112 | |
---|
113 | end |
---|
114 | % fprintf('No of segments = %d\n',length(linelist)); |
---|
115 | % drawseg(linelist,1), title('Raw segments'); |
---|
116 | |
---|
117 | if merge |
---|
118 | % fprintf('\nMerging Segments\n'); |
---|
119 | linelist = mergeseg(linelist, angtol, linkrad, tol); |
---|
120 | nedgelist = {}; |
---|
121 | % fprintf('No of merged segments = %d\n',length(linelist)); |
---|
122 | % drawseg(linelist,2), title('Merged segments'); |
---|
123 | end |
---|
124 | |
---|
125 | |
---|
126 | |
---|