《数字图像处理（MATLAB版）》相关算法代码及其分析（2）

1 将8连通边界转换为4连通边界

1.1 移除对角线转折

1.2 插入额外像素

2 将边界信息转换为二进制图像

2.1 函数定义

2.2 参数处理和验证

2.3 默认大小参数设置

2.4 根据参数调整边界位置

2.5 生成二进制图像

2.6 错误处理

3 对二值图像边界的跟踪和提取

3.1 函数描述

3.2 参数处理

3.3 对象标记

3.4 图像填充

3.5 边界跟踪

3.6 边界坐标存储

3.7 结果修正

3.8 结果输出

1 将8连通边界转换为4连通边界

function rc_new = bound2four(rc)
%BOUND2FOUR Convert 8-connected boundary to 4-connected boundary.
%   RC_NEW = BOUND2FOUR(RC) converts an eight-connected boundary to a
%   four-connected boundary.  RC is a P-by-2 matrix, each row of
%   which contains the row and column coordinates of a boundary
%   pixel.  BOUND2FOUR inserts new boundary pixels wherever there is
%   a diagonal connection.

%   Copyright 2002-2004 R. C. Gonzalez, R. E. Woods, & S. L. Eddins
%   Digital Image Processing Using MATLAB, Prentice-Hall, 2004
%   $Revision: 1.4 $  $Date: 2003/11/21 14:20:21 $

if size(rc, 1) > 1
   % Phase 1: remove diagonal turns, one at a time until they are all gone.
   done = 0;
   rc1 = [rc(end - 1, :); rc];
   while ~done
      d = diff(rc1, 1);
      diagonal_locations = all(d, 2);
      double_diagonals = diagonal_locations(1:end - 1) & ...
          (diff(diagonal_locations, 1) == 0);
      double_diagonal_idx = find(double_diagonals);
      turns = any(d(double_diagonal_idx, :) ~= ...
                  d(double_diagonal_idx + 1, :), 2);
      turns_idx = double_diagonal_idx(turns);
      if isempty(turns_idx)
         done = 1;
      else
         first_turn = turns_idx(1);
         rc1(first_turn + 1, :) = (rc1(first_turn, :) + ...
                                   rc1(first_turn + 2, :)) / 2;
         if first_turn == 1
            rc1(end, :) = rc1(2, :);
         end
      end
   end
   rc1 = rc1(2:end, :);
end

% Phase 2: insert extra pixels where there are diagonal connections.

rowdiff = diff(rc1(:, 1));
coldiff = diff(rc1(:, 2));

diagonal_locations = rowdiff & coldiff;
num_old_pixels = size(rc1, 1);
num_new_pixels = num_old_pixels + sum(diagonal_locations);
rc_new = zeros(num_new_pixels, 2);

% Insert the original values into the proper locations in the new RC
% matrix.
idx = (1:num_old_pixels)' + [0; cumsum(diagonal_locations)];
rc_new(idx, :) = rc1;

% Compute the new pixels to be inserted.
new_pixel_offsets = [0 1; -1 0; 1 0; 0 -1];
offset_codes = 2 * (1 - (coldiff(diagonal_locations) + 1)/2) + ...
    (2 - (rowdiff(diagonal_locations) + 1)/2);
new_pixels = rc1(diagonal_locations, :) + ...
    new_pixel_offsets(offset_codes, :); 

% Where do the new pixels go?
insertion_locations = zeros(num_new_pixels, 1);
insertion_locations(idx) = 1;
insertion_locations = ~insertion_locations;

% Insert the new pixels.
rc_new(insertion_locations, :) = new_pixels;

这段代码的目的是将一个8连通边界转换为4连通边界。在数字图像处理中，连通性是衡量像素之间关系的一种方式。8连通边界意味着边界上的每个像素与其周围的8个像素（水平、垂直和对角线方向）都可能相连。而4连通边界则仅考虑水平和垂直方向的相邻像素。该转换过程涉及两个阶段：首先是移除所有对角线转折点，然后是在需要的位置插入额外的像素以确保4连通性。

以下是对代码的详细分析：

1.1 移除对角线转折

初始化：复制输入的边界坐标rc到rc1并在rc1的开头添加rc的倒数第二行。这样做是为了处理循环边界条件。
循环处理：通过计算rc1的差分d，找出所有对角线连接的位置。这里，对角线连接是指在两个方向（行和列）上都有变化的连接。
双重对角线和转折点检测：接下来，识别连续的对角线连接（双重对角线）并找出其中的转折点。转折点是指相邻的对角线连接在方向上有所不同的地方。
处理转折点：对于每个找到的转折点，通过在转折点位置插入一个新的像素（这个像素的坐标是转折点前后两个像素坐标的平均值）来移除转折。如果处理的是第一个转折点，还需要更新rc1的最后一行，以保持边界的闭合性。
循环结束条件：当没有更多转折点可以处理时，结束循环。

1.2 插入额外像素

计算差分：计算rc1中行和列的差分，以找出对角线连接的位置。
确定新像素数量和位置：根据对角线连接的数量，计算新的边界坐标矩阵rc_new的大小，并初始化为零矩阵。然后，计算原始像素和新插入像素在rc_new中的正确位置。
计算新像素坐标：对于每个需要插入的新像素，根据其相对于原始对角线连接的位置，计算新像素的坐标。
插入操作：在rc_new中填充原始像素和新计算的像素，完成4连通边界的构建。

2 将边界信息转换为二进制图像

function B = bound2im(b, M, N, x0, y0)
%BOUND2IM Converts a boundary to an image.
%   B = BOUND2IM(b) converts b, an np-by-2 or 2-by-np array
%   representing the integer coordinates of a boundary, into a binary
%   image with 1s in the locations defined by the coordinates in b
%   and 0s elsewhere. 
%
%   B = BOUND2IM(b, M, N) places the boundary approximately centered
%   in an M-by-N image. If any part of the boundary is outside the
%   M-by-N rectangle, an error is issued.  
%
%   B = BOUND2IM(b, M, N, X0, Y0) places the boundary in an image of
%   size M-by-N, with the topmost boundary point located at X0 and
%   the leftmost point located at Y0. If the shifted boundary is
%   outside the M-by-N rectangle, an error is issued. XO and X0 must
%   be positive integers. 

%   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/06/14 16:21:28 $

[np, nc] = size(b);
if np < nc
   b = b'; % To convert to size np-by-2.
   [np, nc] = size(b);
end

% Make sure the coordinates are integers.
x = round(b(:, 1)); 
y = round(b(:, 2));

% Set up the default size parameters. 
x = x - min(x) + 1;
y = y - min(y) + 1;
B = false(max(x), max(y));
C = max(x) - min(x) + 1;
D = max(y) - min(y) + 1;

if nargin == 1  
   % Use the preceding default values.
elseif nargin == 3
   if C > M | D > N
      error('The boundary is outside the M-by-N region.')
   end
   % The image size will be M-by-N. Set up the parameters for this.
   B = false(M, N);
   % Distribute extra rows approx. even between top and bottom.
   NR = round((M - C)/2); 
   NC = round((N - D)/2); % The same for columns.
   x = x + NR; % Offset the boundary to new position.
   y = y + NC;  
elseif nargin == 5
   if x0 < 0 | y0 < 0
      error('x0 and y0 must be positive integers.')
   end
   x = x + round(x0) - 1;
   y = y + round(y0) - 1;
   C = C + x0 - 1;
   D = D + y0 - 1;
   if C > M | D > N
      error('The shifted boundary is outside the M-by-N region.')
   end
   B = false(M, N);
else
   error('Incorrect number of inputs.') 
end

B(sub2ind(size(B), x, y)) = true;

这段代码定义了一个名为 bound2im 的函数，它的主要作用是将一个边界（由一系列坐标点组成）转换成一个二进制图像。在这个二进制图像中，边界上的点被标记为 1，其他位置则为 0。

以下是对代码的详细分析：

2.1 函数定义

function B = bound2im(b, M, N, x0, y0)

这表示 bound2im 是一个函数，它可以接收从1到5个参数：

b：一个 np-by-2 或 2-by-np 的数组，代表边界的整数坐标。
M 和 N（可选）：指定输出图像的大小（行数和列数）。
x0 和 y0（可选）：指定边界在图像中的起始位置。

函数返回一个二进制图像 B。

2.2 参数处理和验证

首先，函数检查输入边界 b 的尺寸，并确保其为 np-by-2 的格式。如果不是，就将其转置。这样做是为了确保后续操作中坐标的使用是正确的。

接着，函数通过取整操作确保坐标都是整数值，因为图像中的位置索引必须是整数。

2.3 默认大小参数设置

如果没有指定图像的大小（即只传入了 b 参数），函数会根据边界的最小和最大坐标计算出一个默认的图像大小。这样做的目的是让整个边界都能够被包含在生成的图像中。

2.4 根据参数调整边界位置

如果只给出了边界 b，那么函数会创建一个足够大的图像来容纳整个边界，并将边界放在图像的左上角。
如果给出了图像大小 M 和 N，但没有指定边界的起始位置，那么边界会被置于图像的大致中心位置。此时，如果边界超出了指定的图像大小，函数会报错。
如果同时给出了图像大小和边界的起始位置 x0 和 y0，边界会根据这些位置进行偏移。同样，如果偏移后的边界超出了图像大小，函数也会报错。

2.5 生成二进制图像

最后，函数使用 false 初始化一个大小为 M-by-N 的二进制图像矩阵 B，然后根据调整后的边界坐标，在相应的位置将 B 中的值设置为 true，从而生成最终的边界图像。

2.6 错误处理

如果 nargin（传入的参数数量）不符合要求，函数会报告“Incorrect number of inputs”错误。
如果边界超出了指定的图像区域，或者 x0、y0 不是正整数，函数同样会报错。

3 对二值图像边界的跟踪和提取

function B = boundaries(BW, conn, dir)
%BOUNDARIES Trace object boundaries.  
%   B = BOUNDARIES(BW) traces the exterior boundaries of objects in
%   the binary image BW.  B is a P-by-1 cell array, where P is the
%   number of objects in the image. Each cell contains a Q-by-2
%   matrix, each row of which contains the row and column coordinates
%   of a boundary pixel.  Q is the number of boundary pixels for the
%   corresponding object.  Object boundaries are traced in the
%   clockwise direction.
%
%   B = BOUNDARIES(BW, CONN) specifies the connectivity to use when
%   tracing boundaries.  CONN may be either 8 or 4.  The default
%   value for CONN is 8.
%
%   B = BOUNDARIES(BW, CONN, DIR) specifies the direction used for
%   tracing boundaries.  DIR should be either 'cw' (trace boundaries
%   clockwise) or 'ccw' (trace boundaries counterclockwise).  If DIR
%   is omitted BOUNDARIES traces in the clockwise direction.

%   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:22:07 $

if nargin < 3
   dir = 'cw';
end

if nargin < 2
   conn = 8;
end

L = bwlabel(BW, conn);

% The number of objects is the maximum value of L.  Initialize the
% cell array B so that each cell initially contains a 0-by-2 matrix.
numObjects = max(L(:));
if numObjects > 0
   B = {zeros(0, 2)};
   B = repmat(B, numObjects, 1);
else
   B = {};
end

% Pad label matrix with zeros.  This lets us write the
% boundary-following loop without worrying about going off the edge
% of the image. 
Lp = padarray(L, [1 1], 0, 'both');

% Compute the linear indexing offsets to take us from a pixel to its
% neighbors.  
M = size(Lp, 1);
if conn == 8
   % Order is N NE E SE S SW W NW.
   offsets = [-1, M - 1, M, M + 1, 1, -M + 1, -M, -M-1];
else
   % Order is N E S W.
   offsets = [-1, M, 1, -M];
end

% next_search_direction_lut is a lookup table.  Given the direction
% from pixel k to pixel k+1, what is the direction to start with when
% examining the neighborhood of pixel k+1?
if conn == 8
   next_search_direction_lut = [8 8 2 2 4 4 6 6];
else
   next_search_direction_lut = [4 1 2 3];
end

% next_direction_lut is a lookup table.  Given that we just looked at
% neighbor in a given direction, which neighbor do we look at next? 
if conn == 8
   next_direction_lut = [2 3 4 5 6 7 8 1];
else
   next_direction_lut = [2 3 4 1];
end

% Values used for marking the starting and boundary pixels.
START    = -1;
BOUNDARY = -2;

% Initialize scratch space in which to record the boundary pixels as
% well as follow the boundary.
scratch = zeros(100, 1);

% Find candidate starting locations for boundaries.
[rr, cc] = find((Lp(2:end-1, :) > 0) & (Lp(1:end-2, :) == 0));
rr = rr + 1;

for k = 1:length(rr)
   r = rr(k);
   c = cc(k);
   if (Lp(r,c) > 0) & (Lp(r - 1, c) == 0) & isempty(B{Lp(r, c)})
      % We've found the start of the next boundary.  Compute its
      % linear offset, record which boundary it is, mark it, and
      % initialize the counter for the number of boundary pixels.
      idx = (c-1)*size(Lp, 1) + r;
      which = Lp(idx);
      
      scratch(1) = idx;
      Lp(idx) = START;
      numPixels = 1;
      currentPixel = idx;
      initial_departure_direction = [];
      
      done = 0;
      next_search_direction = 2;
      while ~done
         % Find the next boundary pixel.
         direction = next_search_direction;
         found_next_pixel = 0;
         for k = 1:length(offsets)
            neighbor = currentPixel + offsets(direction);
            if Lp(neighbor) ~= 0
               % Found the next boundary pixel.
               
               if (Lp(currentPixel) == START) & ...
                      isempty(initial_departure_direction)
                  % We are making the initial departure from
                  % the starting pixel.
                  initial_departure_direction = direction;
                  
               elseif (Lp(currentPixel) == START) & ...
                      (initial_departure_direction == direction)
                  % We are about to retrace our path.
                  % That means we're done.
                  done = 1;
                  found_next_pixel = 1;
                  break;
               end
               
               % Take the next step along the boundary.
               next_search_direction = ...
                   next_search_direction_lut(direction);
               found_next_pixel = 1;
               numPixels = numPixels + 1;
               if numPixels > size(scratch, 1)
                  % Double the scratch space.
                  scratch(2*size(scratch, 1)) = 0;
               end
               scratch(numPixels) = neighbor;
               
               if Lp(neighbor) ~= START
                  Lp(neighbor) = BOUNDARY;
               end
               
               currentPixel = neighbor;
               break;
            end
            
            direction = next_direction_lut(direction);
         end
         
         if ~found_next_pixel
            % If there is no next neighbor, the object must just
            % have a single pixel.
            numPixels = 2;
            scratch(2) = scratch(1);
            done = 1;
         end
      end
      
      % Convert linear indices to row-column coordinates and save
      % in the output cell array. 
      [row, col] = ind2sub(size(Lp), scratch(1:numPixels));
      B{which} = [row - 1, col - 1];
   end
end

if strcmp(dir, 'ccw')
   for k = 1:length(B)
      B{k} = B{k}(end:-1:1, :);
   end
end

这段代码实现了对二值图像中对象的边界进行跟踪，最终输出一个包含所有对象边界坐标的 cell 数组。

主要函数 boundaries 接受三个参数：BW 表示输入的二值图像，conn 表示连接性（8 连通或 4 连通），dir 表示跟踪边界的方向（顺时针或逆时针）。根据不同的输入情况，函数会进行相应的处理。其中，首先根据输入参数确定连接性和跟踪方向，然后使用 bwlabel 函数标记输入二值图像中的对象，并初始化一个 cell 数组 B 用于存储边界坐标。

接着，对标记矩阵进行填充操作以简化边界跟踪过程，并定义了一些变量和查找表用于指导边界跟踪的方向。通过在图像中寻找起始位置，然后按照设定的方向依次跟踪边界像素，直到形成完整的边界闭合路径。最后，根据跟踪方向对边界路径进行修正，最终将每个对象的边界坐标存储在 cell 数组 B 中，并按照设定的方向进行排序。

需要注意的是，该代码是基于 MATLAB 的图像处理工具箱编写的，涉及到图像处理中的边界跟踪算法，主要通过对相邻像素进行搜索和遍历完成对象边界的提取。

以下是对代码的详细分析：