function rc_new = bound2eight(rc)
%BOUND2EIGHT Convert 4-connected boundary to 8-connected boundary.
% RC_NEW = BOUND2EIGHT(RC) converts a four-connected boundary to an
% eight-connected boundary. RC is a P-by-2 matrix, each row of
% which contains the row and column coordinates of a boundary
% pixel. RC must be a closed boundary; in other words, the last
% row of RC must equal the first row of RC. BOUND2EIGHT removes
% boundary pixels that are necessary for four-connectedness but not
% necessary for eight-connectedness. RC_NEW is a Q-by-2 matrix,
% where Q <= P.
% Copyright 2002-2004 R. C. Gonzalez, R. E. Woods, & S. L. Eddins
% Digital Image Processing Using MATLAB, Prentice-Hall, 2004
% $Revision: 1.6 $ $Date: 2003/11/21 14:19:38 $
if ~isempty(rc) & ~isequal(rc(1, :), rc(end, :))
error('Expected input boundary to be closed.');
end
if size(rc, 1) <= 3
% Degenerate case.
rc_new = rc;
return;
end
% Remove last row, which equals the first row.
rc_new = rc(1:end - 1, :);
% Remove the middle pixel in four-connected right-angle turns. We
% can do this in a vectorized fashion, but we can't do it all at
% once. Similar to the way the 'thin' algorithm works in bwmorph,
% we'll remove first the middle pixels in four-connected turns where
% the row and column are both even; then the middle pixels in the all
% the remaining four-connected turns where the row is even and the
% column is odd; then again where the row is odd and the column is
% even; and finally where both the row and column are odd.
remove_locations = compute_remove_locations(rc_new);
field1 = remove_locations & (rem(rc_new(:, 1), 2) == 0) & ...
(rem(rc_new(:, 2), 2) == 0);
rc_new(field1, :) = [];
remove_locations = compute_remove_locations(rc_new);
field2 = remove_locations & (rem(rc_new(:, 1), 2) == 0) & ...
(rem(rc_new(:, 2), 2) == 1);
rc_new(field2, :) = [];
remove_locations = compute_remove_locations(rc_new);
field3 = remove_locations & (rem(rc_new(:, 1), 2) == 1) & ...
(rem(rc_new(:, 2), 2) == 0);
rc_new(field3, :) = [];
remove_locations = compute_remove_locations(rc_new);
field4 = remove_locations & (rem(rc_new(:, 1), 2) == 1) & ...
(rem(rc_new(:, 2), 2) == 1);
rc_new(field4, :) = [];
% Make the output boundary closed again.
rc_new = [rc_new; rc_new(1, :)];
%-------------------------------------------------------------------%
function remove = compute_remove_locations(rc)
% Circular diff.
d = [rc(2:end, :); rc(1, :)] - rc;
% Dot product of each row of d with the subsequent row of d,
% performed in circular fashion.
d1 = [d(2:end, :); d(1, :)];
dotprod = sum(d .* d1, 2);
% Locations of N, S, E, and W transitions followed by
% a right-angle turn.
remove = ~all(d, 2) & (dotprod == 0);
% But we really want to remove the middle pixel of the turn.
remove = [remove(end, :); remove(1:end - 1, :)];
if ~any(remove)
done = 1;
else
idx = find(remove);
rc(idx(1), :) = [];
end
