A proper algorithm model is required for system partitioning. It is started with the Matlab model shown below. A detailed study of this model identifies key aspects of the system design that impact its solution. For example:
The overall compute load complexity is driven by the image size through \(R\) and \(C\) dimensions.
The resolution adopted for $\theta$ through the
theta_res
parameter drives complexity, bandwidth, and histogram storage.The algorithm exhibits a “dual-nested for-loop” character.
The algorithm employs lookup tables through
cos_theta
andsin_theta
.The algorithm has been quantized to use
int16
data types.There are multiple compute workloads: for
rho_i
,addr
and histogram updateH
.
function [H,theta,rho,rho_calc] = hough_model( BW, theta_res )
if (nargin == 1) theta_res = 180;
elseif (nargin ~= 2) error('hough_model(BW,theta_res)'); end
[R,C] = size(BW);
rho_max = ceil(sqrt((R-1)^2 + (C-1)^2));
fprintf(1,'rho_max: %g\n',rho_max);
% Initialize:
tmp = linspace(-90,90,1+theta_res);
theta = tmp(1:end-1);
cos_theta = double(fi(cos(theta*pi/180),1,16,15,'RoundingMethod','Round','OverflowAction','Saturate'));
sin_theta = double(fi(sin(theta*pi/180),1,16,15,'RoundingMethod','Round','OverflowAction','Saturate'));
rho = [-rho_max:1:rho_max];
Nt = numel(theta);
Nr = numel(rho);
H = zeros(Nr,Nt);
rho_calc = zeros(R,C,Nt);
% Compute transform:
for yy = 0 : R-1
for xx = 0 : C-1
% Compute the 'rho' value:
rho_i = double(fi(xx*cos_theta + yy*sin_theta,...
1,16,0,'RoundingMethod','Round','OverflowAction','Saturate'));
rho_calc(1+yy,1+xx,:) = rho_i;
% Add offset to turn onto 'rho' address:
addr = rho_i + rho_max;
for ii = 1 : Nt
H(1+addr(ii),ii) = H(1+addr(ii),ii) + BW(1+yy,1+xx);
end % yy
end %xx
end
The Matlab model is run and its performance compared to the built-in Matlab function hough
is found in the Image Processing Toolbox. Here, it is run with a $216\times 240$ image of the AMD Instinct and show “heat maps” of the 2D Hough Transform output histograms for both the Matlab function and the AMD 16-bit Matlab model.