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