[37] | 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 | |
---|