图像分块数目

Question

一个nxm二值画图像，如果把相邻(8 临点)的颜色相同的地方看成一块区域，请问这个图像的最大区域数目是什么？数学理论证明？例如：下面的4x4图像的块数被认为是3而不是4.
  1 0 1 0
  0 1 0 0
  0 0 0 0
  1 1 1 1
那么对任意的nxm二值画图像，这个块数的精确上限的表达是是什么？

Answer 1

感谢大家对这个问题感兴趣，
 1   0   1   0 
 0   1   0   0 
 0   0   0   0 
 1   1   1   1 
这个图中，三个块 分别是,*是无关内容，数字是属于同一个块区域的像素。凡是跟一个点A能通过8临点联通的点B都与A属于同一个块；
1 * 1 *
* 1 * *
* * * *
//////////////////////////////////
* 0 * 0
0 * 0 0
0 0 0 0
* * * *
///////////////////////////////
* * * *
* * * *
1 1 1 1

Answer 2

感谢大家对这个问题感兴趣，
 1   0   1   0 
 0   1   0   0 
 0   0   0   0 
 1   1   1   1 
这个图中，三个块 分别是,*是无关内容，数字是属于同一个块区域的像素。凡是跟一个点A能通过8临点联通的点B都与A属于同一个块；
1 * 1 *
* 1 * *
* * * *
//////////////////////////////////
* 0 * 0
0 * 0 0
0 0 0 0
* * * *
///////////////////////////////
* * * *
* * * *
1 1 1 1

Answer 3

感谢大家对这个问题感兴趣，
 1   0   1   0 
 0   1   0   0 
 0   0   0   0 
 1   1   1   1 
这个图中，三个块 分别是,*是无关内容，数字是属于同一个块区域的像素。凡是跟一个点A能通过8临点联通的点B都与A属于同一个块；
1 * 1 *
* 1 * *
* * * *
//////////////////////////////////
* 0 * 0
0 * 0 0
0 0 0 0
* * * *
///////////////////////////////
* * * *
* * * *
1 1 1 1

Answer 4

0. 定义一个flag矩阵, 用于表示各点的visit状态;
1. 从第一个点出发, 找一个unvisit的点, 若均visit, 则退出.
2. 用类似maze的算法递归查找下一个可联通且unvisit的点, 若找到则置该点visit状态为true;
3. 返回1

Answer 5

不需要膨胀收缩的,
估计类似于Matlab的
bwlabel
可以满足你的要求function [L,numComponents] = bwlabel(BW,mode)
%BWLABEL Label connected components in 2-D binary image.
%   L = BWLABEL(BW,N) returns a matrix L, of the same size as BW, containing
%   labels for the connected components in BW. N can have a value of either
%   4 or 8, where 4 specifies 4-connected objects and 8 specifies
%   8-connected objects; if the argument is omitted, it defaults to 8.
%
%   The elements of L are integer values greater than or equal to 0.  The
%   pixels labeled 0 are the background.  The pixels labeled 1 make up one
%   object, the pixels labeled 2 make up a second object, and so on.
%
%   [L,NUM] = BWLABEL(BW,N) returns in NUM the number of connected objects
%   found in BW.
%
%   Note: Comparing BWLABEL and BWLABELN
%   ------------------------------------
%   BWLABEL supports 2-D inputs only, whereas BWLABELN support any 
%   input dimension.  In some cases you might prefer to use BWLABELN even
%   for 2-D problems because it can be faster.  If you have a 2-D input
%   whose objects are relatively "thick" in the vertical direction,
%   BWLABEL will probably be faster; otherwise BWLABELN will probably be
%   faster.
%
%   Class Support
%   -------------
%   BW can be logical or numeric, and it must be real, 2-D, and
%   nonsparse.  L is double.
%
%   Example
%   -------
%       BW = logical([1 1 1 0 0 0 0 0
%                     1 1 1 0 1 1 0 0
%                     1 1 1 0 1 1 0 0
%                     1 1 1 0 0 0 1 0
%                     1 1 1 0 0 0 1 0
%                     1 1 1 0 0 0 1 0
%                     1 1 1 0 0 1 1 0
%                     1 1 1 0 0 0 0 0]);
%       L = bwlabel(BW,4);
%       [r,c] = find(L == 2);
%
%   See also BWAREAOPEN, BWEULER, BWLABELN, BWSELECT, LABEL2RGB.%   Copyright 1993-2005 The MathWorks, Inc.
%   $Revision: 1.29.4.5 $  $Date: 2006/06/15 20:08:28 $iptchecknargin(1,2,nargin,mfilename);
iptcheckinput(BW, {'logical' 'numeric'}, {'real', '2d', 'nonsparse'}, ...
              mfilename, 'BW', 1);if (nargin < 2)
    mode = 8;
else
    iptcheckinput(mode, {'double'}, {'scalar'}, mfilename, 'N', 2);
endif ~islogical(BW)
    BW = BW ~= 0;
end
[M,N] = size(BW);% Compute run-length encoding and assign initial labels.
[sr,er,sc,labels,i,j] = bwlabel1(BW,mode);
if (isempty(labels))
    numLabels = 0;
else
    numLabels = max(labels);
end% Create a sparse matrix representing the equivalence graph.
tmp = (1:numLabels)';
A = sparse([i;j;tmp], [j;i;tmp], 1, numLabels, numLabels);% Determine the connected components of the equivalence graph
% and compute a new label vector.% Find the strongly connected components of the adjacency graph
% of A.  dmperm finds row and column permutations that transform
% A into upper block triangular form.  Each block corresponds to
% a connected component; the original source rows in each block
% correspond to the members of the corresponding connected
% component.  The first two output% arguments (row and column
% permutations, respectively) are the same in this case because A
% is symmetric.  The vector r contains the locations of the
% blocks; the k-th block as indices r(k):r(k+1)-1.
[p,p,r] = dmperm(A);% Compute vector containing the number of elements in each
% component.
sizes = diff(r);
numComponents = length(sizes);  % Number of components.blocks = zeros(1,numLabels);
blocks(r(1:numComponents)) = 1;
blocks = cumsum(blocks);
blocks(p) = blocks;
labels = blocks(labels);% Given label information, create output matrix.
L = bwlabel2(sr, er, sc, labels, M, N);
上面的代码凑合点参考下,详细可以看看matlab里面的

Answer 6

Thanks for Iorikingdom.I have implemented a function like bwlabel in C in N, and now it works fine.