Thread Subject: vectorize drawing of bounding boxes

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]);

"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

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
wrote in message <fvteb8$q31$1@fred.mathworks.com>...
> "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
>
>

Roger,

that's a clever use of indexing...and I think it should
work. I will test it out tomorrow. Thanks!

J