[Python] How to simplify the generation process of these boolean images?

I have written efficient code that generates all n-bit binary sequences and all n-bit gray codes. The output of them are NumPy 2D arrays containing only 0s and 1s, the height of the array is 2n and the width is n.

I have also written code that generates Thue-Morse sequence, its output is in the same format as above. More specifically, each intermediate result is kept as a column in the final output, with the elements repeated so that every column is of the same length.

For example, if the input is 3, we start with 01, we repeat the elements 4 times so that the first column is 00001111, in the next iteration we invert the bits and add to the previous iteration to get 0110, we repeat the elements twice so the second column is 00111100, and finally the last column is 01101001, so the output is:

array([[0, 0, 0],
[0, 0, 1],
[0, 1, 1],
[0, 1, 0],
[1, 1, 1],
[1, 1, 0],
[1, 0, 0],
[1, 0, 1]], dtype=uint8)


I also wrote another function that creates square sequences following rules similar to Thue-Morse. We start with [[0, 1], [1, 0]], in each subsequent iteration, we take the result from previous iteration (here I refer to it as a), and we flip the bits of a (it should be referred to as b), we grow the square by concatenating [[a, b], [b, a]].

For example, the output for 3 is:

array([[0, 1, 1, 0, 1, 0, 0, 1],
[1, 0, 0, 1, 0, 1, 1, 0],
[1, 0, 0, 1, 0, 1, 1, 0],
[0, 1, 1, 0, 1, 0, 0, 1],
[1, 0, 0, 1, 0, 1, 1, 0],
[0, 1, 1, 0, 1, 0, 0, 1],
[0, 1, 1, 0, 1, 0, 0, 1],
[1, 0, 0, 1, 0, 1, 1, 0]], dtype=uint8)


6 iterations example image:



Now the second kind of image I want to generate is simple, we repeat each column 2n - 1 - i times, so that each run of 1s becomes a rectangle, whose height is the length of the run, and in each subsequent column the rectangles are halved in width, so that sum of the width of the rectangles is height - 1.

This is the 7-bit binary codes example of such image:



7-bit gray codes:



7-bit ABBABAAB:



The third kind of images I want to generate is just taking the sequences and convert them to polar coordinates:

7-bit binary polar:



7-bit gray polar:



7-bit ABBABAAB polar:



6 iterations 2D ABBABAAB polar:



And finally I want to take the fractal squares and convert them to polar:

7-bit binary fractal polar:



7-bit gray fractal polar:



7-bit ABBABAAB fractal polar:




Now from the number of images I have posted you might guess that I wrote code to generate these images. Yes, I did, but it is inefficient. It is easy to write working code, but it is hard to make it run fast.

Code


import cv2
import numpy as np
from enum import Enum
from PIL import Image
from typing import Generator


def validate(n: int) -> None:
if not (n and isinstance(n, int)):
raise ValueError(f"Argument {n} is not a valid bit width")


def binary_codes(n: int) -> np.ndarray:
validate(n)
places = 1 << np.arange(n)
return (
np.concatenate(
[
np.tile(
np.concatenate([np.zeros(a, dtype=bool), np.ones(a, dtype=bool)]), b
)
for a, b in zip(places[::-1], places)
]
)
.reshape((n, 1 << n))
.T
)


def gray_codes_columns(places: np.ndarray) -> Generator[np.ndarray, None, None]:
for i, (a, b) in enumerate(zip(places, places[1:])):
yield np.tile(
np.concatenate(
[
np.zeros(b, dtype=bool),
np.ones(a, dtype=bool),
np.zeros(b, dtype=bool),
]
),
1 << i,
)


def gray_codes(n: int) -> np.ndarray:
validate(n)
if n == 1:
return np.array([(0,), (1,)], dtype=bool)

half = 1 << (n - 1)
places = 1 << np.arange(n - 1, -1, -1)
return (
np.concatenate(
[
np.zeros(half, dtype=bool),
np.ones(half, dtype=bool),
*gray_codes_columns(places),
]
)
.reshape((n, 1 << n))
.T
)


def abba_codes(n: int) -> np.ndarray:
validate(n)
power = 1 << (n - 1)
abba = np.array([0, 1], dtype=np.uint8)
powers = 1 << np.arange(n - 2, -1, -1)
return (
np.concatenate(
[
np.zeros(power, dtype=np.uint8),
np.ones(power, dtype=np.uint8),
*(
np.tile(
(abba := np.concatenate([abba, abba ^ 1])), (power, 1)
).T.flatten()
for power in powers
),
]
)
.reshape((n, 1 << n))
.T
)


def abba_square(n: int) -> np.ndarray:
validate(n)
abba = np.array([[0, 1], [1, 0]], dtype=np.uint8)
for _ in range(n - 1):
flip = abba ^ 1
abba = np.concatenate(
[np.concatenate([abba, flip]), np.concatenate([flip, abba])], axis=-1
)

return abba


class Bool_Codes(Enum):
binary_codes = binary_codes
gray_codes = gray_codes
abba_codes = abba_codes


def bool_squares(func: Bool_Codes, n: int) -> np.ndarray:
arr = func(n).T[::-1]
powers = 1 << np.arange(n + 1)
result = np.zeros((powers[-1],) * 2, dtype=np.uint8)
for i, (a, b) in enumerate(zip(powers, powers[1:])):
result[a:b] = arr

return result


def upright_square(func: Bool_Codes, n: int) -> np.ndarray:
return (bool_squares(func, n).T[:, ::-1] ^ 1) * 255


def to_polar(square: np.ndarray, length: int = 1024) -> np.ndarray:
square = np.array(Image.fromarray(square).resize((length, length), resample=0))
return cv2.warpPolar(square, (length, length), [half := length >> 1] * 2, half, 16)


def bool_polar(func: Bool_Codes, n: int, length: int = 1024) -> np.ndarray:
return to_polar(upright_square(func, n), length)


def bin_polar(n: int, length: int = 1024) -> np.ndarray:
return bool_polar(Bool_Codes.binary_codes, n, length)


def gray_polar(n: int, length: int = 1024) -> np.ndarray:
return bool_polar(Bool_Codes.gray_codes, n, length)


def abba_polar(n: int, length: int = 1024) -> np.ndarray:
return bool_polar(Bool_Codes.abba_codes, n, length)


def bool_square_img(func: Bool_Codes, n: int, length: int = 1024) -> Image:
return Image.fromarray(upright_square(func, n)).resize((length, length), resample=0)


def bin_square_img(n: int, length: int = 1024) -> Image:
return bool_square_img(Bool_Codes.binary_codes, n, length)


def gray_square_img(n: int, length: int = 1024) -> Image:
return bool_square_img(Bool_Codes.gray_codes, n, length)


def abba_square_img(n: int, length: int = 1024) -> Image:
return bool_square_img(Bool_Codes.abba_codes, n, length)


def abba_isosquare(n: int, length: int = 1024) -> Image:
square = (abba_square(n) ^ 1) * 255
return Image.fromarray(square).resize((length, length), resample=0)


def bool_isopolar(func: Bool_Codes, n: int, length: int = 1024) -> np.ndarray:
return to_polar((func(n).astype(np.uint8) ^ 1) * 255, length)


def bin_isopolar(n: int, length: int = 1024) -> np.ndarray:
return bool_isopolar(Bool_Codes.binary_codes, n, length)


def gray_isopolar(n: int, length: int = 1024) -> np.ndarray:
return bool_isopolar(Bool_Codes.gray_codes, n, length)


def abba_isopolar(n: int, length: int = 1024) -> np.ndarray:
return bool_isopolar(Bool_Codes.abba_codes, n, length)


def abba_square_polar(n: int, length: int = 1024) -> np.ndarray:
return to_polar((abba_square(n) ^ 1) * 255, length)

Performance


In [23]: %timeit bin_polar(10)
23 ms ± 179 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [24]: %timeit gray_polar(10)
23 ms ± 177 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [25]: %timeit abba_polar(10)
22.5 ms ± 371 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [26]: %timeit bin_isopolar(10)
14.9 ms ± 63.1 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [27]: %timeit gray_isopolar(10)
14.8 ms ± 36.2 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [28]: %timeit abba_isopolar(10)
15.1 ms ± 452 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [29]: %timeit bin_square_img(10)
9.18 ms ± 57.3 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [30]: %timeit gray_square_img(10)
9.62 ms ± 569 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [31]: %timeit abba_square_img(10)
9.26 ms ± 619 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [32]: %timeit abba_square_polar(10)
17.3 ms ± 507 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [33]: %timeit abba_isosquare(10)
2.97 ms ± 12.7 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)


You see, I had to mix PIL and cv2, because only cv2 offers polar coordinate transformation, and only PIL lets me resize without any interpolation at all.

The following don't give intended result:

cv2.imwrite('D:/garbage.png', cv2.resize(abba_square(4) * 255, (1024, 1024), cv2.INTER_NEAREST_EXACT))




cv2.imwrite('D:/garbage1.png', cv2.resize(abba_square(4) * 255, (1024, 1024), cv2.INTER_AREA))




No matter what interpolation mode I try, it always gives a blurry image. I want the edges to be sharp and everything staying rectangles. So I had to use PIL to resize the images. Of course I can use a two level nested for loop to broadcast the pixels with result[i*n:i*n+n, j*n:j*n+n] = img[i, j] but that would be slow.

The edges of the polar images are jagged, not smooth, I want the edges to be smooth, and the corners are black, I want the corners white. And if I pass n larger than 14 to bool_squares it just hangs.

What are better ways to do these?

Continue reading...