VirusShooter – The Algorithm


Two weeks ago, I’ve posted new game in my MATLAB Fun Toolbox: VirusShooter. However, due to force majeur (I’m too sleepy), I didn’t explain anything about the game’s algorithm. So, here I am, trying to keep my promises and explain the algoritm of the VirusShooter game. Here goes:

General Gameplay

Since this game will be using a webcam or any other image acquisition device compatible with MATLAB, MATLAB’s Image Acquisition Toolbox and Image Processing Toolbox are needed to code the game. Image Acquisition Toolbox is compulsory (because I don’t know any other way to capture webcam images other than using Image Acquisition Toolbox, however Image Processing Toolbox is not. A built-in function from Image Processing Toolbox, normxcorr2 is used in this game but it can be easily coded if you don’t have it. So, no biggie.

As in my other game, a while loop is used to run the game. However, since this game involves image acquisition hardware, a setup for image acquisition must be executed first before the while loop is executed. The thing is that, in this game, the image acquisition device will be feeding image data constantly to MATLAB, while on the other hand, MATLAB needs to process the image data and run the game accordingly. So, to avoid image lag, it is preferred to capture/acquire new image after all image processing and data calculation was done. To do this, the following setup for image acquisition is used:

%Creating new IMAQ object
IMAQobj=videoinput(IMAQadaptorlist{adaptorID},...
                   IMAQdevicelist{adaptorID}{devideID},...
                   IMAQformatlist{adaptorID}{IMAQformat});
%Setting up IMAQ parameter
triggerconfig(IMAQobj,'manual');
set(IMAQobj,'ReturnedColorSpace','rgb')
set(IMAQobj,'TriggerRepeat',Inf)
set(IMAQobj,'FramesPerTrigger',1)
set(IMAQobj,'FrameGrabInterval',1)
VidRes=get(IMAQobj,'VideoResolution');

After image acquisition setup is executed, the game was initiated by creating random viruses at random location with random movement speed and then one frame of image were captured as a reference image before the main while loop is executed. In every single loop in the main while loop, a trigger was sent to image acquisition device to capture one frame of image. This new image will be compared with the reference image by using cross-correlation technique to determines camera movement. From the camera movement and the virus movement itself, viruses’ position are determined  and then the new image will be displayed with several virus image added on top of it based on their position. Because of this, the virus will be shown on webcam’s image feed and it will move in sync with webcam’s movement, making the virus looks like it does exist in the surrounding. At the end of a loop, the new image will be used as reference image that will be used in the next loop for cross-correlation with the newer images. So, the code that executes the gameplay should be like this:

%Creating newvirus
[x,y,Vx,Vy,ax,ay]=createnewvirus(n_virus);
%Starting IMAQ
start(IMAQobj)
%Getting the first image for pool initialization
trigger(IMAQobj)
oldImage=getdata(IMAQobj,1,'uint8');
%Displaying game
playstat=true;
timer=1;
while playstat
  %Trigerring IMAQ object
  trigger(IMAQobj)
  %Acquiring new image and calculating virus movement
  newImage=getdata(IMAQobj,1,'uint8');
  try
    [dx,dy]=findcammove(oldImage,newImage);
  catch
    dx=0;
    dy=0;
  end
  [x,y,Vx,Vy,ax,ay]=movevirus(x,y,Vx,Vy,ax,ay,dx,dy);
  %Clearing image
  cla(mainaxes)
  hold(mainaxes,'on')
  %Displaying image
  displayimage=putvirus(newImage,x,y);
  imshow(displayimage,'Parent',mainaxes)
  %Adjusting image axis
  axis(mainaxes,[0,VidRes(1),0,VidRes(2)])
  %Refreshing loop
  oldImage=newImage;
  timer=timer+1;
  %Delaying loop
  pause(dt)
end

Detecting Camera Movement

Notice that somewhere in the main loop above, I used findcammove function. This function is the most important function in this game as it is used to detect camera movement. Yup, to make the viruses’ movement realistic and looks like it were in our surrounding, the viruses movement must be in sync with the camera movement. What I mean is like this: for example, you have a virus drawn on the left of your cross hair, so you must rotate or move your camera to the left and when you do so, the code must be able to detect it so that the virus can be drawn moving to the right and reaching the cross hair. Thus,  an information about the camera movement is needed and that’s where findcammove function comes in. So, just solely based on the webcam’s image feed, findcammove must be able to detect camera’s movement.

For the core component of findcammove, I used normxcorr2 built-in function to perform normalized cross correlation. Normalized cross correlation is a common technique used in image processing for image tracking. I won’t explain the mathematic behind normxcorr2 and normalized cross correlation (because it will be long and boring and because I don’t know how to type equation here, but if you are intereseted to learn more, check out the wikipedia link that I provided), but basically when you cross-correlate two images (or use normxcorr2 on two images), you will get what-so-called correlation map. These correlation map represent the similarity between two image as the function of discrete offset. So, to make it simple, from a peak in correlation map, a displacement that occurs between given two images can be found by finding the peak’s relative distance from the center of the correlation map. Thus, based on that theory, camera’s movement can be calculated from the camera’s image feed.

Unfortunately, normxcorr2 cannot be used directly on camera’s image feed because it only works on grayscale image. Beside that, normxcorr2 also takes quite some computational time when it is used on images with large size. Thus, to keep camera movement detection accurate while preventing lag due to computational time, only four corner parts of image with size of 32×32 pixels that will be used for normxcorr2. So, four pair of images will be cross-correlated to get four different displacements. Then, the camera movement is determined from the smallest displacements from all four. This is done to avoid false camera movement detection due to local movement in the image.

So, based on those theory, findcammove should be written as follows:

function [u,v]=findcammove(image1,image2)
  %Converting image to grayscale
  image1=rgb2gray(image1);
  image2=rgb2gray(image2);
  %Sampling image1 for template
  template=cell(4,1);
  template{1}=image1((0.5*trackpixel)+1:...
                     (0.5*trackpixel)+1+trackpixel,...
                     (0.5*trackpixel)+1:...
                     (0.5*trackpixel)+1+trackpixel);
  template{2}=image1(VidRes(2)-(0.5*trackpixel)+1-trackpixel:...
                     VidRes(2)-(0.5*trackpixel),...
                     (0.5*trackpixel)+1:...
                     (0.5*trackpixel)+1+trackpixel);
  template{3}=image1((0.5*trackpixel)+1:...
                     (0.5*trackpixel)+1+trackpixel,...
                     VidRes(1)-(0.5*trackpixel)+1-trackpixel:...
                     VidRes(1)-(0.5*trackpixel));
  template{4}=image1(VidRes(2)-(0.5*trackpixel)+1-trackpixel:...
                     VidRes(2)-(0.5*trackpixel)+1,...
                     VidRes(1)-(0.5*trackpixel)+1-trackpixel:...
                     VidRes(1)-(0.5*trackpixel)+1);
  %Sampling image2 for search area
  search{1}=image2(1:2*trackpixel,...
                   1:2*trackpixel);
  search{2}=image2(VidRes(2)-(2*trackpixel)+1:....
                   VidRes(2),...
                   1:2*trackpixel);
  search{3}=image2(1:2*trackpixel,...
                   VidRes(1)-(2*trackpixel)+1:....
                   VidRes(1));
  search{4}=image2(VidRes(2)-(2*trackpixel)+1:....
                   VidRes(2),...
                   VidRes(1)-(2*trackpixel)+1:....
                   VidRes(1));
  %Performing cross-correlation
  u=zeros(4,1);
  v=zeros(4,1);
  for imID=1:4
    cmap=normxcorr2(template{imID},search{imID});
    [r,c]=find(cmap==max(cmap(:)));
    u(imID)=c(1)-(1.5*trackpixel);
    v(imID)=-r(1)+(1.5*trackpixel);
  end
  %Averaging camera speed
  u=u(abs(u)==min(abs(u)));
  v=-v(abs(v)==min(abs(v)));
  if numel(u)<1
    u=0;
  elseif numel(u)>1
    u=u(1);
  end
  if numel(v)<1
    v=0;
  elseif numel(v)>1
    v=v(1);
  end
end

Synchronizing Viruses’ Movement with Camera’s Movement

After camera’s movement is determined, viruses’ movement must be synchronized with the camera’s movement to make it realistic. It can be easily done by simply substracting viruses’ movement with camera movement. To make things interesting, I also made the viruses had their own movement, which are randomly generated along with their position using rand function. Thus, in the main while loop, viruses position is updated in every single loop based on their own individual movement and global camera movement. To do so, another function, movevirus was written as follows:

function [x,y,Vx,Vy,ax,ay]=movevirus(x,y,Vx,Vy,ax,ay,dx_cam,dy_cam)
  for virusID=1:n_virus
    %Integrating movement speed
    Vx(virusID)=Vx(virusID)+(ax(virusID)*dt);
    Vy(virusID)=Vy(virusID)+(ay(virusID)*dt);
    %Integrating position
    x(virusID)=x(virusID)+(Vx(virusID)*dt);
    y(virusID)=y(virusID)+(Vy(virusID)*dt);
    %Adjusting position based on camera movement
    x(virusID)=x(virusID)+dx_cam;
    y(virusID)=y(virusID)+dy_cam;
    %Recircling position
    x(x>fieldratio*VidRes(1))=x(x>fieldratio*VidRes(1))-...
                              (2*fieldratio*VidRes(1));
    x(x<-fieldratio*VidRes(1))=x(x<-fieldratio*VidRes(1))+...
                               (4*fieldratio*VidRes(1));
    y(y>fieldratio*VidRes(1))=y(y>2*VidRes(1))-...
                              (4*fieldratio*VidRes(2));
    y(y<-fieldratio*VidRes(1))=y(y<-fieldratio*VidRes(1))+...
                               (4*fieldratio*VidRes(2));
  end
end

Putting Viruses and CrossHair in the Image Feed

After viruses movement and position has been determined relative, it must be puton the top of the image feed. Same thing also must be done for the crosshair. So, to make it simple, I decided that for the image frame position, (0,0) is located in the middle of image feed and the viruses are drawn accordingly. Adding viruses on top of image feed can be done simply by adding virus image array (yup, you need an image for the virus appearance) into the image feed array and then displaying them using imshow function. However, since the virus image is smaller than the image feed, image array addition must be executed using correct indexing. Long story short, here it is, a function that are used to put viruses and crosshair image on top of camera’s image feed.

function displayimage=putvirus(BGimage,x,y)
  %Padding image
  paddedimage=uint8(zeros(size(BGimage)+...
              [2*virus_size(1),2*virus_size(1),0]));
  paddedimage(:,:,1)=padarray(BGimage(:,:,1),...
                            [virus_size(1),virus_size(1)],'both');
  paddedimage(:,:,2)=padarray(BGimage(:,:,2),...
                            [virus_size(1),virus_size(1)],'both');
  paddedimage(:,:,3)=padarray(BGimage(:,:,3),...
                            [virus_size(1),virus_size(1)],'both');
  %Adding virus to image
  for virusID=1:n_virus
    if (x(virusID)<-0.5*(VidRes(1)+virus_size(2)))||...
       (x(virusID)>0.5*(VidRes(1)+virus_size(2)))||...
       (y(virusID)<-0.5*(VidRes(2)+virus_size(1)))||...
       (y(virusID)>0.5*(VidRes(2)+virus_size(1)))

    else
      paddedimage((0.5*VidRes(2))+round(y(virusID))-...
                  (0.5*virus_size(1))+1+virus_size(1):...
                  (0.5*VidRes(2))+round(y(virusID))+...
                  (0.5*virus_size(1)+virus_size(1)),...
                  (0.5*VidRes(1))+round(x(virusID))-...
                  (0.5*virus_size(2))+1+virus_size(2):...
                  (0.5*VidRes(1))+round(x(virusID))+...
                  (0.5*virus_size(2))+virus_size(2),:)=...
               paddedimage((0.5*VidRes(2))+round(y(virusID))-...
                           (0.5*virus_size(1))+1+virus_size(1):...
                           (0.5*VidRes(2))+round(y(virusID))+...
                           (0.5*virus_size(1))+virus_size(1),...
                           (0.5*VidRes(1))+round(x(virusID))-...
                           (0.5*virus_size(2))+1+virus_size(2):...
                           (0.5*VidRes(1))+round(x(virusID))+...
                           (0.5*virus_size(2))+virus_size(1),...
                           :)+...
               (10*virus_image(:,:,:));
    end
  end
  %Drawing crosshair
  paddedimage((0.5*VidRes(2))-...
              (0.5*xhair_size(1))+1+virus_size(1):...
              (0.5*VidRes(2))+...
              (0.5*xhair_size(1))+virus_size(1),...
              (0.5*VidRes(1))-...
              (0.5*xhair_size(2))+1+virus_size(2):...
              (0.5*VidRes(1))+...
              (0.5*xhair_size(2))+virus_size(2),...
              :)=...
            paddedimage((0.5*VidRes(2))-(0.5*xhair_size(1))+1+...
                        virus_size(1):...
                        (0.5*VidRes(2))+(0.5*xhair_size(1))+...
                        virus_size(1),...
                        (0.5*VidRes(1))-(0.5*xhair_size(2))+1+...
                        virus_size(1):...
                        (0.5*VidRes(1))+(0.5*xhair_size(2))+...
                        virus_size(1),:)+...
                        xhair_image(:,:,:);
  %Cutting image
  displayimage=paddedimage(virus_size(1)+1:...
                           virus_size(1)+VidRes(2),...
                           virus_size(2)+1:...
                           virus_size(2)+VidRes(1),:);
end

Well, after two weeks late, finally I finished the algorithm explaination for VirusShooter. I hope this is useful for you, especially those who wants to learn more about image processing and object tracking. Regarding the normalized cross-correlation operation, it is quite complicated if it is the first time you play with digital image array, but when you are used to it, it will be a piece of cake.

So, I think that’s all about the VirusShooter. Now, I’m going to look for other ideas for the next fun toolbox, while laying in my bed until I fall asleep.

Regards,

0X_R

This entry was posted in Uncategorized and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s