w_wd
2010-08-23, 10:59
相信不少人用过CircularHough_Grd.m进行Hough圆检测吧,我想请问其中求解accum中局部极大值的原理是什么,最好能详细说一下求局部极值的算法流程,谢谢!
部分代码如下,全部代码见附件。
%%%%%%%% Locating local maxima in the accumulation array %%%%%%%%%%%%
% Stop if no need to locate the center positions of circles
if ~func_compu_cen,
return;
end
clear lin2accum weight4accum;
% Parameters to locate the local maxima in the accumulation array
% -- Segmentation of 'accum' before locating LM
prm_useaoi = true;
prm_aoithres_s = 2;
prm_aoiminsize = floor(min([ min(size(accum)) * 0.25, ...
prm_r_range(2) * 1.5 ]));
% -- Filter for searching for local maxima
prm_fltrLM_s = 1.35;
prm_fltrLM_r = ceil( prm_fltrLM_R * 0.6 );
prm_fltrLM_npix = max([ 6, ceil((prm_fltrLM_R/2)^1.8) ]);
% -- Lower bound of the intensity of local maxima
prm_LM_LoBndRa = 0.2; % minimum ratio of LM to the max of 'accum'
% Smooth the accumulation array
fltr4accum = fltr4accum / sum(fltr4accum(:));
accum = filter2( fltr4accum, accum );
% Select a number of Areas-Of-Interest from the accumulation array
if prm_useaoi,
% Threshold value for 'accum'
prm_llm_thres1 = prm_grdthres * prm_aoithres_s;
% Thresholding over the accumulation array
accummask = ( accum > prm_llm_thres1 );
% Segmentation over the mask
[accumlabel, accum_nRgn] = bwlabel( accummask, 8 );
% Select AOIs from segmented regions
accumAOI = ones(0,4);
for k = 1 : accum_nRgn,
accumrgn_lin = find( accumlabel == k );
[accumrgn_IdxI, accumrgn_IdxJ] = ...
ind2sub( size(accumlabel), accumrgn_lin );
rgn_top = min( accumrgn_IdxI );
rgn_bottom = max( accumrgn_IdxI );
rgn_left = min( accumrgn_IdxJ );
rgn_right = max( accumrgn_IdxJ );
% The AOIs selected must satisfy a minimum size
if ( (rgn_right - rgn_left + 1) >= prm_aoiminsize && ...
(rgn_bottom - rgn_top + 1) >= prm_aoiminsize ),
accumAOI = [ accumAOI; ...
rgn_top, rgn_bottom, rgn_left, rgn_right ];
end
end
else
% Whole accumulation array as the one AOI
accumAOI = [1, size(accum,1), 1, size(accum,2)];
end
% Thresholding of 'accum' by a lower bound
prm_LM_LoBnd = max(accum(:)) * prm_LM_LoBndRa;
% Build the filter for searching for local maxima
fltr4LM = zeros(2 * prm_fltrLM_R + 1);
[mesh4fLM_x, mesh4fLM_y] = meshgrid(-prm_fltrLM_R : prm_fltrLM_R);
mesh4fLM_r = sqrt( mesh4fLM_x.^2 + mesh4fLM_y.^2 );
fltr4LM_mask = ...
( mesh4fLM_r > prm_fltrLM_r & mesh4fLM_r <= prm_fltrLM_R );
fltr4LM = fltr4LM - ...
fltr4LM_mask * (prm_fltrLM_s / sum(fltr4LM_mask(:)));
if prm_fltrLM_R >= 4,
fltr4LM_mask = ( mesh4fLM_r < (prm_fltrLM_r - 1) );
else
fltr4LM_mask = ( mesh4fLM_r < prm_fltrLM_r );
end
fltr4LM = fltr4LM + fltr4LM_mask / sum(fltr4LM_mask(:));
% **** Debug code (begin)
if dbg_on,
dbg_LMmask = zeros(size(accum));
end
% **** Debug code (end)
% For each of the AOIs selected, locate the local maxima
circen = zeros(0,2);
for k = 1 : size(accumAOI, 1),
aoi = accumAOI(k,:); % just for referencing convenience
% Thresholding of 'accum' by a lower bound
accumaoi_LBMask = ...
( accum(aoi(1):aoi(2), aoi(3):aoi(4)) > prm_LM_LoBnd );
% Apply the local maxima filter
candLM = conv2( accum(aoi(1):aoi(2), aoi(3):aoi(4)) , ...
fltr4LM , 'same' );
candLM_mask = ( candLM > 0 );
% Clear the margins of 'candLM_mask'
candLM_mask([1:prm_fltrLM_R, (end-prm_fltrLM_R+1):end], :) = 0;
candLM_mask(:, [1:prm_fltrLM_R, (end-prm_fltrLM_R+1):end]) = 0;
% **** Debug code (begin)
if dbg_on,
dbg_LMmask(aoi(1):aoi(2), aoi(3):aoi(4)) = ...
dbg_LMmask(aoi(1):aoi(2), aoi(3):aoi(4)) + ...
accumaoi_LBMask + 2 * candLM_mask;
end
% **** Debug code (end)
% Group the local maxima candidates by adjacency, compute the
% centroid position for each group and take that as the center
% of one circle detected
[candLM_label, candLM_nRgn] = bwlabel( candLM_mask, 8 );
for ilabel = 1 : candLM_nRgn,
% Indices (to current AOI) of the pixels in the group
candgrp_masklin = find( candLM_label == ilabel );
[candgrp_IdxI, candgrp_IdxJ] = ...
ind2sub( size(candLM_label) , candgrp_masklin );
% Indices (to 'accum') of the pixels in the group
candgrp_IdxI = candgrp_IdxI + ( aoi(1) - 1 );
candgrp_IdxJ = candgrp_IdxJ + ( aoi(3) - 1 );
candgrp_idx2acm = ...
sub2ind( size(accum) , candgrp_IdxI , candgrp_IdxJ );
% Minimum number of qulified pixels in the group
if sum(accumaoi_LBMask(candgrp_masklin)) < prm_fltrLM_npix,
continue;
end
% Compute the centroid position
candgrp_acmsum = sum( accum(candgrp_idx2acm) );
cc_x = sum( candgrp_IdxJ .* accum(candgrp_idx2acm) ) / ...
candgrp_acmsum;
cc_y = sum( candgrp_IdxI .* accum(candgrp_idx2acm) ) / ...
candgrp_acmsum;
circen = [circen; cc_x, cc_y];
end
end
% **** Debug code (begin)
if dbg_on,
figure(dbg_bfigno); imagesc(dbg_LMmask); axis image;
title('Generated map of local maxima');
if size(accumAOI, 1) == 1,
figure(dbg_bfigno+1);
surf(candLM, 'EdgeColor', 'none'); axis ij;
title('Accumulation array after local maximum filtering');
end
end
% **** Debug code (end)
部分代码如下,全部代码见附件。
%%%%%%%% Locating local maxima in the accumulation array %%%%%%%%%%%%
% Stop if no need to locate the center positions of circles
if ~func_compu_cen,
return;
end
clear lin2accum weight4accum;
% Parameters to locate the local maxima in the accumulation array
% -- Segmentation of 'accum' before locating LM
prm_useaoi = true;
prm_aoithres_s = 2;
prm_aoiminsize = floor(min([ min(size(accum)) * 0.25, ...
prm_r_range(2) * 1.5 ]));
% -- Filter for searching for local maxima
prm_fltrLM_s = 1.35;
prm_fltrLM_r = ceil( prm_fltrLM_R * 0.6 );
prm_fltrLM_npix = max([ 6, ceil((prm_fltrLM_R/2)^1.8) ]);
% -- Lower bound of the intensity of local maxima
prm_LM_LoBndRa = 0.2; % minimum ratio of LM to the max of 'accum'
% Smooth the accumulation array
fltr4accum = fltr4accum / sum(fltr4accum(:));
accum = filter2( fltr4accum, accum );
% Select a number of Areas-Of-Interest from the accumulation array
if prm_useaoi,
% Threshold value for 'accum'
prm_llm_thres1 = prm_grdthres * prm_aoithres_s;
% Thresholding over the accumulation array
accummask = ( accum > prm_llm_thres1 );
% Segmentation over the mask
[accumlabel, accum_nRgn] = bwlabel( accummask, 8 );
% Select AOIs from segmented regions
accumAOI = ones(0,4);
for k = 1 : accum_nRgn,
accumrgn_lin = find( accumlabel == k );
[accumrgn_IdxI, accumrgn_IdxJ] = ...
ind2sub( size(accumlabel), accumrgn_lin );
rgn_top = min( accumrgn_IdxI );
rgn_bottom = max( accumrgn_IdxI );
rgn_left = min( accumrgn_IdxJ );
rgn_right = max( accumrgn_IdxJ );
% The AOIs selected must satisfy a minimum size
if ( (rgn_right - rgn_left + 1) >= prm_aoiminsize && ...
(rgn_bottom - rgn_top + 1) >= prm_aoiminsize ),
accumAOI = [ accumAOI; ...
rgn_top, rgn_bottom, rgn_left, rgn_right ];
end
end
else
% Whole accumulation array as the one AOI
accumAOI = [1, size(accum,1), 1, size(accum,2)];
end
% Thresholding of 'accum' by a lower bound
prm_LM_LoBnd = max(accum(:)) * prm_LM_LoBndRa;
% Build the filter for searching for local maxima
fltr4LM = zeros(2 * prm_fltrLM_R + 1);
[mesh4fLM_x, mesh4fLM_y] = meshgrid(-prm_fltrLM_R : prm_fltrLM_R);
mesh4fLM_r = sqrt( mesh4fLM_x.^2 + mesh4fLM_y.^2 );
fltr4LM_mask = ...
( mesh4fLM_r > prm_fltrLM_r & mesh4fLM_r <= prm_fltrLM_R );
fltr4LM = fltr4LM - ...
fltr4LM_mask * (prm_fltrLM_s / sum(fltr4LM_mask(:)));
if prm_fltrLM_R >= 4,
fltr4LM_mask = ( mesh4fLM_r < (prm_fltrLM_r - 1) );
else
fltr4LM_mask = ( mesh4fLM_r < prm_fltrLM_r );
end
fltr4LM = fltr4LM + fltr4LM_mask / sum(fltr4LM_mask(:));
% **** Debug code (begin)
if dbg_on,
dbg_LMmask = zeros(size(accum));
end
% **** Debug code (end)
% For each of the AOIs selected, locate the local maxima
circen = zeros(0,2);
for k = 1 : size(accumAOI, 1),
aoi = accumAOI(k,:); % just for referencing convenience
% Thresholding of 'accum' by a lower bound
accumaoi_LBMask = ...
( accum(aoi(1):aoi(2), aoi(3):aoi(4)) > prm_LM_LoBnd );
% Apply the local maxima filter
candLM = conv2( accum(aoi(1):aoi(2), aoi(3):aoi(4)) , ...
fltr4LM , 'same' );
candLM_mask = ( candLM > 0 );
% Clear the margins of 'candLM_mask'
candLM_mask([1:prm_fltrLM_R, (end-prm_fltrLM_R+1):end], :) = 0;
candLM_mask(:, [1:prm_fltrLM_R, (end-prm_fltrLM_R+1):end]) = 0;
% **** Debug code (begin)
if dbg_on,
dbg_LMmask(aoi(1):aoi(2), aoi(3):aoi(4)) = ...
dbg_LMmask(aoi(1):aoi(2), aoi(3):aoi(4)) + ...
accumaoi_LBMask + 2 * candLM_mask;
end
% **** Debug code (end)
% Group the local maxima candidates by adjacency, compute the
% centroid position for each group and take that as the center
% of one circle detected
[candLM_label, candLM_nRgn] = bwlabel( candLM_mask, 8 );
for ilabel = 1 : candLM_nRgn,
% Indices (to current AOI) of the pixels in the group
candgrp_masklin = find( candLM_label == ilabel );
[candgrp_IdxI, candgrp_IdxJ] = ...
ind2sub( size(candLM_label) , candgrp_masklin );
% Indices (to 'accum') of the pixels in the group
candgrp_IdxI = candgrp_IdxI + ( aoi(1) - 1 );
candgrp_IdxJ = candgrp_IdxJ + ( aoi(3) - 1 );
candgrp_idx2acm = ...
sub2ind( size(accum) , candgrp_IdxI , candgrp_IdxJ );
% Minimum number of qulified pixels in the group
if sum(accumaoi_LBMask(candgrp_masklin)) < prm_fltrLM_npix,
continue;
end
% Compute the centroid position
candgrp_acmsum = sum( accum(candgrp_idx2acm) );
cc_x = sum( candgrp_IdxJ .* accum(candgrp_idx2acm) ) / ...
candgrp_acmsum;
cc_y = sum( candgrp_IdxI .* accum(candgrp_idx2acm) ) / ...
candgrp_acmsum;
circen = [circen; cc_x, cc_y];
end
end
% **** Debug code (begin)
if dbg_on,
figure(dbg_bfigno); imagesc(dbg_LMmask); axis image;
title('Generated map of local maxima');
if size(accumAOI, 1) == 1,
figure(dbg_bfigno+1);
surf(candLM, 'EdgeColor', 'none'); axis ij;
title('Accumulation array after local maximum filtering');
end
end
% **** Debug code (end)