Path: news.mathworks.com!not-for-mail
From: "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
Newsgroups: comp.soft-sys.matlab
Subject: Re: vectorize drawing of bounding boxes
Date: Wed, 7 May 2008 23:35:04 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 88
Message-ID: <fvteb8$q31$1@fred.mathworks.com>
References: <fvspfn$m20$1@fred.mathworks.com>
Reply-To: "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1210203304 26721 172.30.248.37 (7 May 2008 23:35:05 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Wed, 7 May 2008 23:35:04 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:467268


"jay vaughan" <jvaughan5.nospam@gmail.com> wrote in message <fvspfn
$m20$1@fred.mathworks.com>...
> Hi,
> 
> I am trying to optimize the speed of drawing a bunch of
> bounding boxes on identified objects. I know to try to avoid
> loops, but wasn't sure how to vectorize the code (below).
> Any ideas on vectorizing this process or speeding it up in
> general? Eventually it will be done many times per second,
> so I do need the speed.
> 
> A simulation of this below where the first part generates
> the coordinates the objects, and the second part is a loop
> that creates the boxes.
> 
> % FIRST PART, CREATE (RANDOM) BOX COORDINTES
> num_boxes= 1000;
> box_size= 13;
> frame_size = [512 512];
> 
> rows = (frame_size(1)-1)*rand(num_boxes,1);
> cols = (frame_size(2)-1)*rand(num_boxes,1);
> box_coords = round([rows cols]);
> 
> % SECOND PART, CREATE BOXES (IF NOT TOO CLOSE TO EDGE)
> M = zeros(frame_size);
> tic
> for k = 1:size(box_coords,1)
>     dl = floor(box_size/2);
>     dr = ceil(box_size/2);
>     R1 = box_coords(k,1)-dl;
>     R2 = box_coords(k,1)+dr;
>     C1 = box_coords(k,2)-dl;
>     C2 = box_coords(k,2)+dl;
>     if R1>=1 && C1>=1 && R2<=frame_size(1) && ...
>       C2<=frame_size(2)
>         M(R1:R2,C1) = 1;
>         M(R1:R2,C2) = 1;
>         M(R1,C1:C2) = 1;
>         M(R2,C1:C2) = 1;
>     end
> end
> toc
> % 0.043 seconds on my computer. I was hoping to get <0.01
> 
> imagesc(M)
> colormap gray
> set(gcf,'position',[200 200 frame_size(2) frame_size(1)])
> set(gca,'position',[0 0 1 1]);
---------
  A couple of thoughts come to mind.  First, it seems inefficient to not 
generate the "box_coords" in such a way that the corresponding "boxes" 
cannot extend past the bounds of the 'frame_size'.  That should be very easy 
to do by altering the way 'rows' and 'cols' are originally defined.  Then the 'if' 
part in your for-loop would be unnecessary.  The execution of this 'if' portion 
may represent a substantial part of your execution time.

  The second is more difficult to describe and may not actually save you time.  
Only experimenting would determine this.  You could define a box "template" 
centered at (0,0) just once and convert its 52 or so pairs of subscripts into 
single indices which apply to the frame_size.  The same could be done with 
the set of 1000 'box_coords' pairs.  Then you could call 'ndgrid' and add the 
outputs to obtain every possible sum of the 52 linear indices with those of 
the 1000 centers to get an array of 52000 indices.  These can then be used to 
set the corresponding points in M to 1's.  The following shows how this can 
be done.

 [m,n] = size(frame_size);
 
 % Create a box template centered at (0,0)
 t = [(-dl:dr)-m*dl,(-dl:dr)+m*dr, ...
      -dl+m*(-dl+1:dr-1),dr+m*(-dl+1:dr-1)];
 
 % Convert 'box_coords' to linear indices in 'frame_size'
 b = box_coords(:,1)+m*(box_coords(:,2)-1);

 % Now get all 52000 possible combined sums
 [T,B] = ndgrid(t,b);
 p = T(:)+B(:); % p is 52000 by 1 in size
 M = zeros(size(frame_size));
 M(p) = 1; % Place 52000 1's in M

   This of course depends on your having carried out the first suggestion so 
that no box extends beyond the boundaries of 'frame_size'.

Roger Stafford