Python 3的功能是将图像旋转90°

A coding challenge that rotates an image 90 degrees counterclockwise. The image is represented as an array matrix. I believe the time complexity is O(n²), but I'd like to know for sure, as well as any other feedback.

将图像逆时针旋转90度的编码挑战。图像表示为阵列矩阵。我相信时间复杂度是O(n2),但我想知道,以及任何其他反馈。

def rotate_image(img):
    rotated_image = [[] for x in range(len(img))]
    for i in range(len(img)):
        for j in range(len(img[i])):
          rotated_image[len(img) - j - 1].append(img[i][j])
    return rotated_image

Example usage:

image = [
  [1, 1, 5, 9, 9],
  [2, 2, 6, 0, 0],
  [3, 3, 7, 1, 1],
  [4, 4, 8, 2, 2],
  [5, 5, 9, 3, 3]
]

rotated_img = rotate_image(image)
for i in rotated_img:
    print(i)

Outputs:

[9, 0, 1, 2, 3]
[9, 0, 1, 2, 3]
[5, 6, 7, 8, 9]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]

3 个解决方案

#1

How about using Python built-ins to do the job?

如何使用Python内置函数来完成这项工作?

img = [[1, 2, 3], [10, 20, 30], [100, 200, 300]]
list(reversed(list(zip(*img))))
[(3, 30, 300), (2, 20, 200), (1, 10, 100)]

#2

You can use NumPy module that's good with arrays and matrices. It has a built-in for exactly that purpose -

您可以使用适用于数组和矩阵的NumPy模块。它有一个内置的目的 -

import numpy as np

np.rot90(image).tolist()

With array manipulations, that's essentially same as performing matrix/array transpose and then flipping the rows -

使用数组操作,这与执行矩阵/数组转置然后翻转行基本相同 -

np.asarray(image).T[::-1].tolist()

If the input is already an array, we can skip the array-conversion. Also, if the output as an array is okay, it would be simply a view into the input and as such the entire operation would be virtually-free.

如果输入已经是数组,我们可以跳过数组转换。此外,如果作为数组的输出是可以的,那么它只是输入的视图,因此整个操作几乎是免费的。

Thus, with image_arr as the input array, it would be -

因此,使用image_arr作为输入数组,它将是 -

np.rot90(image_arr)

With transpose and flipping rows -

使用转置和翻转行 -

image_arr.T[::-1]

Let's take the provided sample and check out outputs on an IPython console -

让我们在IPython控制台上获取提供的示例并检查输出 -

In [48]: image
Out[48]: 
[[1, 1, 5, 9, 9],
 [2, 2, 6, 0, 0],
 [3, 3, 7, 1, 1],
 [4, 4, 8, 2, 2],
 [5, 5, 9, 3, 3]]

In [50]: np.asarray(image).T[::-1].tolist()
Out[50]: 
[[9, 0, 1, 2, 3],
 [9, 0, 1, 2, 3],
 [5, 6, 7, 8, 9],
 [1, 2, 3, 4, 5],
 [1, 2, 3, 4, 5]]

Timings on a large 5000 x 5000 sized image

大型5000 x 5000大小的图像上的时间

1) Image as a list :

1)图像列表:

In [53]: image = np.random.randint(0,256,(5000,5000)).tolist()

# @Dima Tisnek's soln
In [54]: %timeit list(reversed(list(zip(*image))))
1 loop, best of 3: 1.09 s per loop

In [55]: %timeit np.array(image).T[::-1].tolist()
1 loop, best of 3: 1.06 s per loop

Time-complexity

There's no time-complexity involved here (not on computation anyway) and the entire play is about array and list conversion, as shown below when we break down the steps -

这里没有涉及时间复杂度(不管计算是什么),整个游戏都是关于数组和列表转换,如下所示,当我们分解步骤时 -

In [72]: image_arr = np.array(image)

In [71]: %timeit np.array(image) # convert to array
1 loop, best of 3: 771 ms per loop

In [73]: %timeit image_arr.T[::-1] # perform 90deg rotation
1000000 loops, best of 3: 372 ns per loop

In [74]: %timeit image_arr.T[::-1].tolist() # convert back to list
1 loop, best of 3: 296 ms per loop

2) Image and output as arrays :

2)图像和输出为数组:

In [56]: image = np.random.randint(0,256,(5000,5000))

# @Dima Tisnek's soln
In [57]: %timeit list(reversed(list(zip(*image))))
1 loop, best of 3: 1.34 s per loop

In [58]: %timeit image.T[::-1]
1000000 loops, best of 3: 363 ns per loop

In [59]: %timeit np.rot90(image)
100000 loops, best of 3: 9.05 µs per loop

The last two NumPy based ones are virtually free as discussed earlier. This is because internally image.T[::-1] is same as input image, but with different stride pattern representation. Let's verify that they are same by checking their memory occupancy -

如前所述,最后两个基于NumPy的实际上是免费的。这是因为内部图像.T [:: - 1]与输入图像相同,但具有不同的步幅模式表示。让我们通过检查他们的内存占用率来验证它们是否相同 -

In [60]: np.shares_memory(image, image.T[::-1])
Out[60]: True

Conversion to list on own-data for slight perf. boost

Closer inspection on list conversion reveals that converting to list when the strided pattern isn't regular (row-order) might not be the most optimal scenario. So, one way would be create a copy of array data once we have the rotated one and then convert. This seems to give around 10% improvement -

对列表转换的仔细检查表明,当跨步模式不规则(行顺序)时转换为列表可能不是最佳方案。因此,一旦我们有旋转的数据然后转换,一种方法是创建数组数据的副本。这似乎提高了约10% -

In [2]: image = np.random.randint(0,256,(5000,5000)).tolist()

In [8]: %timeit list(reversed(list(zip(*image))))
1 loop, best of 3: 1.12 s per loop

In [9]: %timeit np.asarray(image).T[::-1].tolist()
1 loop, best of 3: 1.11 s per loop

# Have own-data (copy) and then convert to list
In [10]: %timeit np.asarray(image).T[::-1].copy().tolist()
1 loop, best of 3: 1.01 s per loop

#3

from scipy.ndimage import rotate
from scipy.misc import imread, imshow

img = imread('raven.jpg')
rotate_img = rotate(img, 90)

imshow(rotate_img)