Python – How to rotate an array of bits

algorithmspython

enter image description here

I currently have a PIL Image object which I store as an array of bits (1's and 0's). However I now would like to be able to rotate that image 45 degrees. One way to do it is take the original PIL image, apply a transform matrix on it, then convert that to an array of bits. Problem with this approach is that it's computationally expensive, especially if I want to start doing more than just one rotation. It would be faster to just modify the array of bits directly.

I tried using numpy.roll:

numpy.roll(bits, 45) # rotate 45 degrees

Unfortunately, this just does a circular shift, not an actual angular rotation.

What algorithm can I use on the array of bits to give me the desired output without having to go through the original image? Even though my application is in Python, your answer can be in whatever language you feel comfortable with, I'm more interested in the algorithm itself not the syntax 🙂

Best Answer

If you always want to rotate an image by a specific angle each time, you only need to do the heavy math once (and really, it's not that heavy). The best way to do this is by working the process backwards. For every pixel in the destination image, you calculate the corresponding location in the starting image. This "source" pixel coordinate is saved in what is called a Lookup Table or LUT. Once you build this LUT for the angle and origin of location that you want, then it is very quick to use each entry of the LUT to "move" the pixels of a source image to the correct pixel of the destination image. Where this gets tricky and involves more math is whn deciding how to weight the source date to come up with the destination data. When you work backwards from the integer destination image coordinates, you will end up with floating point coordinates in the source image. These floating point coordinates need to be interpolated. The simplest method is to use the "Nearest Neighbor" integer pixel coordinate to the calculated floating point values, but there are other algorithms such as "Bi-Linear" or "Bi-Cubic" that will provide a better quality of the finished image (but are of course slower than Nearest NEighbor"

Related Solutions

3d Packing algorithm for item’s shipping

Bin packing is very computationally difficult. Think of half of the problem: you want to pack product in shipping boxes with no wastage in the box. An optimal solution for that would require going through all possible subsets and all possible 3d arrangements of the product that needs to ship in one truck. I'll give you the optimal solution for that because I have a friend who does six impossible things before breakfast.

Now you just have to get all the boxes on the truck with no wastage. My friend does his second impossible thing and gives you the solution. Unfortunately, with the box sizes you selected above, there is empty space in the truck which could be reduced if you'd chosen different (either larger or smaller) boxes in the first task. If you change the size of one box, at best you'll have to re-pack the truck; at worst, you may have to repack all of the boxes which is just as hard as the problem we started with. And, as with the first stage, you'd have to try all possible 3d arrangements.

I found Skiena's The Algorithm Design Manual to be helpful for thinking about what class of algorithms suit which sorts of problems, but I mostly learned that good solutions for even mundane problems blow up in you face with computational difficulty. Most of what you are needing fit into the class of bin-packing problems and that article is a good jumping off point. It is worth noting that some of the best algorithms for this are commercial products because this task pops up everywhere in logistics (what's the smallest number of train cars can I get my goods into? and such). There is considerable money to be made if the right heuristics can save a manufacturer 100 train cars a month.

Unfortunately, the literature on optimizing heuristics isn't nearly as large as for algorithms. If you try to go it alone, I guarantee that you'll be dreaming about moving rectangular prisms around by your second month. I had a cutting-stock problem that if I had to do again I'd probably farm out to the experts (or their propriety software).

Thanks to @JTrana for the fine expansion of my comment.

Algorithms – How to Evenly Distribute Objects Along an Array

Put the 0th element at index 0, the R-1th element at index N-1.

Calculate d = floor(N / R).

This function describes the target indexes for the 1st to the R-2th element: i(x) = 2 * d * x;

Examles:

R=3,N=4
{0, 1, 2, 3}
{o,  , o, o}

R=7 N=12
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11}
{o,  , o,  , o,  , o,  , o,  , o, o}

Best Answer

Related Solutions

3d Packing algorithm for item’s shipping

Algorithms – How to Evenly Distribute Objects Along an Array

Related Topic