1 | % MERGESEG - Line segment merging function. |
---|
2 | % |
---|
3 | % Usage: newseglist = mergeseg(seglist, angtol, linkrad) |
---|
4 | % |
---|
5 | % Arguments: seglist - an Nx4 array storing line segments in the form |
---|
6 | % [x1 y1 x2 y2 |
---|
7 | % x1 y1 x2 y2 |
---|
8 | % . . . ] etc |
---|
9 | % |
---|
10 | % angtol - Angle tolerance used when attempting to merge line |
---|
11 | % segements (radians). |
---|
12 | % linkrad - Maximum distance between end points of line segments |
---|
13 | % for segments to be elegible for linking (pixels). |
---|
14 | % |
---|
15 | % Function scans through the list of line segments seeking to merge segments |
---|
16 | % together. Segments are merged if the orientation difference is less than |
---|
17 | % angtol and if the ends of the segments are within linkrad of each other. |
---|
18 | % The comparison is performed by first sorting line segments by angle, then |
---|
19 | % each line segment is only tested against other line segments that satisfy |
---|
20 | % the orientation constraint. |
---|
21 | % |
---|
22 | % See also: EDGELINK, LINESEG, MAXLINEDEV, DRAWSEG |
---|
23 | % |
---|
24 | |
---|
25 | % Copyright (c) 2000-2005 Peter Kovesi |
---|
26 | % School of Computer Science & Software Engineering |
---|
27 | % The University of Western Australia |
---|
28 | % http://www.csse.uwa.edu.au/ |
---|
29 | % |
---|
30 | % Permission is hereby granted, free of charge, to any person obtaining a copy |
---|
31 | % of this software and associated documentation files (the "Software"), to deal |
---|
32 | % in the Software without restriction, subject to the following conditions: |
---|
33 | % |
---|
34 | % The above copyright notice and this permission notice shall be included in |
---|
35 | % all copies or substantial portions of the Software. |
---|
36 | % |
---|
37 | % The Software is provided "as is", without warranty of any kind. |
---|
38 | |
---|
39 | % March 2000 - Original version |
---|
40 | % November 2005 - Bug fix for case Nseg < 4 (thanks to Ming Luo) |
---|
41 | % May 2006 - Bug fix for termination of while loop (thanks to Martin Labrecque) |
---|
42 | |
---|
43 | function newseglist = mergeseg(seglist, angtol, linkrad, linedevtol) |
---|
44 | |
---|
45 | Nseg = size(seglist,1); |
---|
46 | |
---|
47 | if Nseg <= 1 % Nothing to merge |
---|
48 | newseglist = seglist; |
---|
49 | return; |
---|
50 | end |
---|
51 | |
---|
52 | cosAngTol = cos(angtol); |
---|
53 | |
---|
54 | % Build up some data in the following form |
---|
55 | % [x1 y1 x2 y2 dx dy angle merged] |
---|
56 | |
---|
57 | seg = zeros(Nseg,8); |
---|
58 | seg(:,1:4) = seglist; |
---|
59 | seg(:,5:6) = seg(:,3:4)-seg(:,1:2); % delta x and delta y |
---|
60 | seg(:,7) = atan2(seg(:,6), seg(:,5)); % =segment angle [-pi ... pi] |
---|
61 | neg = seg(:,7) < 0; % compress angle range [0...pi] |
---|
62 | seg(:,7) = seg(:,7) + neg*pi; |
---|
63 | [Y,I] = sort(seg(:,7)); % sort by angle |
---|
64 | seg = seg(I,:); |
---|
65 | seg(:,7) = 2*seg(:,7); % double the angles |
---|
66 | |
---|
67 | TotalSegs = Nseg; |
---|
68 | |
---|
69 | for s1 = 1:Nseg |
---|
70 | % fprintf('Merging Segment %d/%d\r',s1,Nseg); |
---|
71 | if ~seg(s1,8) % if segment s1 has not already been merged |
---|
72 | s2 = s1+1; if s2>Nseg, s2=s2-Nseg; end % `modulo' arithetic |
---|
73 | ang1 = seg(s1,7); ang2 = seg(s2,7); |
---|
74 | deltaSin = sin(ang1)*cos(ang2) - cos(ang1)*sin(ang2); |
---|
75 | deltaCos = cos(ang1)*cos(ang2) + sin(ang1)*sin(ang2); |
---|
76 | deltaAng = 0.5*abs(atan2(deltaSin,deltaCos)); |
---|
77 | |
---|
78 | while (s2 ~= s1) && (deltaAng < angtol) |
---|
79 | if ~seg(s2,8) % if segment s2 has not already been merged |
---|
80 | [newseg, merged] = compareseg(seg(s1,:), seg(s2,:),linkrad, ... |
---|
81 | linedevtol); |
---|
82 | if merged |
---|
83 | seg(s1,1:4) = newseg; |
---|
84 | % update delta x, delta y, and angle ? (I think not) |
---|
85 | seg(s2,8) = merged; % eliminate s2; |
---|
86 | TotalSegs = TotalSegs - 1; |
---|
87 | end |
---|
88 | end |
---|
89 | s2 = s2+1; if s2>Nseg, s2=s2-Nseg; end |
---|
90 | ang2 = seg(s2,7); |
---|
91 | deltaSin = sin(ang1)*cos(ang2) - cos(ang1)*sin(ang2); |
---|
92 | deltaCos = cos(ang1)*cos(ang2) + sin(ang1)*sin(ang2); |
---|
93 | deltaAng = 0.5*abs(atan2(deltaSin,deltaCos)); |
---|
94 | end |
---|
95 | end |
---|
96 | end |
---|
97 | |
---|
98 | % fprintf('\n'); |
---|
99 | |
---|
100 | % Now clean up list by extracting the unmerged entries |
---|
101 | |
---|
102 | newseglist = zeros(TotalSegs,4); |
---|
103 | newNseg = 0; |
---|
104 | for s = 1:Nseg |
---|
105 | if ~seg(s,8) % if this segment has not been merged |
---|
106 | newNseg = newNseg+1; % store it in the final list. |
---|
107 | newseglist(newNseg,:) = seg(s,1:4); |
---|
108 | end |
---|
109 | end |
---|
110 | |
---|
111 | |
---|
112 | %---------------------------------------------------------------------- |
---|
113 | % Internal function that does all the work. |
---|
114 | % Two segments, that already meet the angle constraint, are tested for end |
---|
115 | % point proximity. If they meet this constraint they then tested to see |
---|
116 | % what the maximum line deviation would be if they were merged. If this |
---|
117 | % is within tolerance they are merged. |
---|
118 | %---------------------------------------------------------------------- |
---|
119 | |
---|
120 | function [newseglist, merged] = compareseg(seg1, seg2, linkrad, linedevtol) |
---|
121 | |
---|
122 | s1p1 = seg1(1:2); % point1 of segment1 |
---|
123 | s1p2 = seg1(3:4); % point2 of segment1 |
---|
124 | |
---|
125 | s2p1 = seg2(1:2); % point1 of segment2 |
---|
126 | s2p2 = seg2(3:4); % point2 of segment2 |
---|
127 | |
---|
128 | dir1 = seg1(5:6); |
---|
129 | dir2 = seg2(5:6); |
---|
130 | |
---|
131 | cosAng = dot(dir1,dir2); |
---|
132 | |
---|
133 | if cosAng < 0 % Reverse order of points on seg2 so that both |
---|
134 | % segments are in the `same' direction |
---|
135 | tmp = s2p1; |
---|
136 | s2p1 = s2p2; |
---|
137 | s2p2 = tmp; |
---|
138 | end |
---|
139 | |
---|
140 | merged = 0; % Default result: not merged |
---|
141 | newseglist = [seg1; seg2]; % and segments left unchanged |
---|
142 | |
---|
143 | if norm(s1p2-s2p1) < linkrad % If we satisfy endpoint proximity |
---|
144 | rc = [s1p1; s1p2; s2p1; s2p2]; |
---|
145 | [maxdev, index, D] = maxlinedev(rc(:,1),rc(:,2)); % test line deviation |
---|
146 | if maxdev < linedevtol |
---|
147 | newseglist = [s1p1 s2p2]; % Merge the segments one way |
---|
148 | merged = 1; |
---|
149 | end |
---|
150 | elseif norm(s2p2-s1p1) < linkrad |
---|
151 | rc = [s2p1; s2p2; s1p1; s1p2]; |
---|
152 | [maxdev, index, D] = maxlinedev(rc(:,1),rc(:,2)); |
---|
153 | if maxdev < linedevtol |
---|
154 | newseglist = [s2p1 s1p2]; % ... or merge the other way. |
---|
155 | merged = 1; |
---|
156 | end |
---|
157 | end |
---|
158 | |
---|
159 | |
---|
160 | |
---|
161 | |
---|