Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to rotate an array by ± 180° in an efficient way?

What is the best algorithm to rotate a non-square M×N array by 180° around its center, using the least memory and operations, for C langages and derivatives (Python, Cython, pure C) ?

like image 764
Aurélien Pierre Avatar asked Dec 21 '17 18:12

Aurélien Pierre


2 Answers

Assuming out is an initialized copy of array, M and N their rows and columns numbers, and we are using a language indexing arrays from 0 to (M-1) and (N-1) :

In Python :

def rotate_180(array, M, N, out):
    for i in range(M):
        for j in range(N):
            out[i, N-1-j] = array[M-1-i, j]

This takes 5.82 s on a 4000×3000 array.

In parallelized Cython + OpenMP using Memviews :

cdef void rotate_180(float[:, :] array, int M, int N, float[:, :] out) nogil:

    cdef size_t i, j

    with parallel(num_threads=8):
        for i in prange(M):
            for j in range(N):
                out[i, N-1-j] = array[M-1-i, j]

This takes 5.45 s on a 4000×3000 array.

In comparison, numpy with np.rot90(array, 2) takes 8.58 µs.

Edit : to avoid know-it-all comments out of the point, here is what it does :

a = array([[1, 2, 3],
           [4, 5, 6],
           [7, 8, 9]])

rotate_180(a, 3, 3, b)

b = array([[9, 8, 7],
           [6, 5, 4],
           [3, 2, 1]])

Using 2 successive 90° rotations with numpy built-in function, we get :

np.rot90(a, 2)

out = array([[9, 8, 7],
             [6, 5, 4],
             [3, 2, 1]])

So this rotate_180() is indeed a 180° rotation. Now :

np.flip(a, 0)

out = array([[7, 8, 9],
             [4, 5, 6],
             [1, 2, 3]])

is not a rotation but a symmetry along the last line. If we compose 2 symmetries along each direction :

np.flip(np.flip(a, 1), 0)

out = array([[9, 8, 7],
             [6, 5, 4],
             [3, 2, 1]])

we also get a 180° rotation.

So, yes, thank you, my code does what it says.

like image 78
Aurélien Pierre Avatar answered Nov 08 '22 06:11

Aurélien Pierre


It's relatively late to answer this question but still better than doing nothing.

For 2D numpy arrays being in shape of H x W:

rotated_array = old_array[::-1,::-1] #rotate the array 180 degrees

For 2D numpy images being in shape of H x W x 3:

rotated_image = image[::-1,::-1] #rotate the image 180 degrees
like image 33
TaQuangTu Avatar answered Nov 08 '22 07:11

TaQuangTu