Bitmap Rotation using VHDL

[yttuncel]

Hello,

In my current project I hold an image inside a ROM and when asked, I copy the content into a frame buffer which is read by the monitor. I can successfully copy and show the image on the screen. Now I am adding something new. The image will be rotated by x degrees (input) before being copied into the frame buffer.

One important thing is that I am using 1bpp in ROM. So it is not RGB data, only ones(background) and zeros(image).

I looked for rotation algorithms on the web but I can not select between the rotation matrix method and the rotation by shearing method. Rotation matrix seems more compute intensive than shearing method, but on the other hand it is easily implementable.

Can anybody give me any heads up, what method is the best for a hardware implementation?

Thanks.

 

[TrickyDicky]

You know the algorithm, so you should know or be able to work out the logic requirements. The requirement wont change during runtime. All you need to compute is the destination address (line counter and pixel counter) and then use that, through the rotation as the look-up address.

 

[yttuncel]

You know the algorithm, so you should know or be able to work out the logic requirements. The requirement wont change during runtime. All you need to compute is the destination address (line counter and pixel counter) and then use that, through the rotation as the look-up address.

Thank you for the answer. To me rotation by shear is more logic friendly as it calculates a shear amount for the whole line and places pixels accordingly. The other method needs to calculate where each pixel should map to, so it needs more computations on the paper. I've been doing some matlab trial and errors with the shear method, but I still can not reproduce the matlab's built in imrotate function.

One problem thats stuck in my head is the destination image size. Since this method involves three shears I need to store each step in separate RAMs. So I will read from ROM, shear by -tan(theta/2)*y in the x direction and store this sheared image on the first RAM. Then I will read from first RAM and shear by sin(delta)*x in the y direction and store this resulting image in the second RAM. In the end I will read from second RAM and shear in the x direction again and store this data in the third RAM. Once these shears are completed, I will then copy the contents of the third RAM into Frame Buffer. However for every theta, the shear amount changes, so the width and height of the image change too. I thought of calculating the biggest possible resulting image in MATLAB so that I will use it for my RAM size to be able to handle the worst case, but so far I failed to do so in Matlab.

I reproduced Paeth's code in matlab, with no antialiasing as I use 1bpp. Here is the code:

function data_out = xshear(data,delta)


[height,width] = size(data);
shear = -tan(delta/2);

for y=1:height,
  skew = shear * y;     
  skewi = floor(skew);         
  for x=1:width 
    pixel = data(x, y);        
    
    if (x+skewi > 0),
      data_out(x+skewi,y) = pixel;
    end
    
  end
end

function data_out = yshear(data,delta)


[height,width] = size(data);
shear = sin(delta);

for x=1:width,
  skew = shear * x;            
  skewi = floor(skew);        

  for y=1:height,            
    pixel = data(x, y);        
    if (y+skewi > 0),
      data_out(x,y+skewi) = pixel;
    end
  end
end

Is there anything I am missing here? When I call xshear, yshear and xshear matlab gives error index out of bounds. I know this problem has kind of shifted towards Matlab, but I will implement it after I am done with this part, so I will be glad if you guys can help me out.

Thanks!

 

[TrickyDicky]

Rotation via matrix is rather simple. It is just the sum of several multiplies. This CAB easily be done in a single pipeline from the source to the destination. It can even be done on real time on video.

 

[yttuncel]

Rotation via matrix is rather simple. It is just the sum of several multiplies. This CAB easily be done in a single pipeline from the source to the destination. It can even be done on real time on video.

After hours of working I concluded so This method is easy to understand but shearing the image wrto its centre is a rather hard thing to do. I can now rotate the image by shearing, but I need 1000x1000 canvas to rotate a 200x200 image by 75 degrees. So it is definitely not logic and memory friendly in terms of requirements.

Rotation via matrix should map destination to source, not source to destination, right? Because latter causes artifacts (dots) on the image as far as i know. In which source this method is best explained?

Thank you for your time.

 

[TrickyDicky]

Yes - always map destination to source. So your destination is simply just X and Y counters that will always pull a value out of the source buffer from somewhere. Depending on how you implement the algorithm, you may want saturation in there to prevent going over the source boundaries. This may be the "dots" you're talking about?

Ive seen a whole "warp" engine done by just 9 coefficients IIRC. It could do full rotation, scale and X/Y shift all in 1 go.

 

[yttuncel]

Yes - always map destination to source. So your destination is simply just X and Y counters that will always pull a value out of the source buffer from somewhere. Depending on how you implement the algorithm, you may want saturation in there to prevent going over the source boundaries. This may be the "dots" you're talking about?

Ive seen a whole "warp" engine done by just 9 coefficients IIRC. It could do full rotation, scale and X/Y shift all in 1 go.

The dots im talking about are shown here: https://www.datagenetics.com/blog/august32013/index.html

They are due to the sine and cosine producing noninteger results and these results cause the destination not be mapped 1:1 to source. But inverting the rotation matrix solves the issue , just like you summarized, destination pixels are not chosen, they choose. How will I implement matrix multplication in an efficient manner? Im guessing I should do something different than matrice multiplication but I am not really sure.