0

I want to apply Arnold cat map on an image. I manage this code from Wikipedia but it was getting slow when I increase the iteration number like for 600 by 600 image with 83 iteration it took time=567.8921346664429 second. Can any improvement possible for this code. I guess the looping things make this code very slow, O(n^2) for every iteration.

from PIL.Image import open as load_pic, new as new_pic


def main(path, iterations, keep_all=False, name="arnold_cat-{name}-{index}.png"):
    """
    Params
        path:str
            path to photograph
        iterations:int
            number of iterations to compute
        name:str
            formattable string to use as template for file names
    """
    title = os.path.splitext(os.path.split(path)[1])[0]
    counter = 0
    while counter < iterations:
        with load_pic(path) as image:
            dim = width, height = image.size
            with new_pic(image.mode, dim) as canvas:
                for x in range(width):
                    for y in range(height):
                        nx = (2 * x + y) % width
                        ny = (x + y) % height

                        canvas.putpixel((nx, height-ny-1), image.getpixel((x, height-y-1)))

        if counter > 0 and not keep_all:
            os.remove(path)
        counter += 1
        print(counter, end="\r")
        path = name.format(name=title, index=counter)
        canvas.save(path)

    return canvas

I modify the code for my use case like this:

def cat_map(image_matrix,MAX):
    dim = width, height = image_matrix.shape
    transformed_matrix = np.zeros((width,height)) 
    # Apply Arnold cat map on image_matrix
    index = []
    counter = 0 
    iterations = MAX
    # collect initial index of the image_matrix
    for i in range(len(image_matrix)):
        for j in range(len(image_matrix[0])):
            index.append([i,j])
    forward_index = []
    while counter < iterations:
        for coordinate in index:
            x = coordinate[0]
            y = coordinate[1]
            new_x = (2 * x + y) % width
            new_y = (x + y) % height

            transformed_matrix[new_x][new_y] = image_matrix[x][y]
            forward_index.append([new_x,new_y])
        index = forward_index
        # apply recursive transformation on image_matrix
        image_matrix = transformed_matrix
        # only store the last index matrix
        if counter != iterations - 1:
            forward_index = []
            # re-initialize transformation matrix
            transformed_matrix = np.zeros((width,height)) 
        counter += 1
    return transformed_matrix,forward_index

I need the index_array of the last iteration also. I appreciated the vectorized idea of @dankal444 but then how to store the index array?

Improve this question

1 Answer 1

Reset to default
1

Vectorized version that is around 40 to 80 times faster (depending on the number of iterations and if you are willing to use opencv or not).

Most speed-up for multi-iterations run got from the storing and reusing of transformation idx matrices (x_image, y_image, nx_image, ny_image).

Saving image is now a bottleneck, so if you do not need intermediate images you can just comment it out and get yet another significant (~x2-3) speed-up.

def main(path, iterations, keep_all=False, name="arnold_cat-{name}-{index}.png"):
    """
    Params
        path:str
            path to photograph
        iterations:int
            number of iterations to compute
        name:str
            formattable string to use as template for file names
    """
    title = os.path.splitext(os.path.split(path)[1])[0]
    counter = 0

    with load_pic(path) as image:

        width, height = image.size
        current_image = np.array(image).copy()
        n_channels = current_image.shape[-1]
        x_image = np.repeat(np.arange(width).reshape(-1, 1), height, axis=-1).T
        y_image = np.repeat(np.arange(height).reshape(-1, 1), width, axis=-1)
        nx_image = (2 * x_image + y_image) % width
        ny_image = (x_image + y_image) % height
        transformed_image = np.zeros((width, height, n_channels)).astype(np.uint8)
        ny_image = height - ny_image - 1
        y_image = height - y_image - 1
        while counter < iterations:
            transformed_image[ny_image, nx_image] = current_image[y_image, x_image]

            if counter > 0 and not keep_all:
                os.remove(path)
            counter += 1
            print(counter, end="\r")
            path = name.format(name=title, index=counter)

            # slower saving image:
            # image = fromarray(transformed_image)
            # image.save(path)

            # this is faster alternative of saving image, without it it is still very fast
            import cv2
            cv2.imwrite(path, transformed_image)

            current_image = transformed_image.copy()

        # use canvas at the end, for me this is unnecessary:
        image = fromarray(current_image)

    return image

EDIT: OP wanted transformation indices to be returned as well, so refactored code to have separate function to calculate transformation indices

def main(path, iterations, keep_all=False, name="arnold_cat-{name}-{index}.png"):
    """
    Params
        path:str
            path to photograph
        iterations:int
            number of iterations to compute
        name:str
            formattable string to use as template for file names
    """
    title = os.path.splitext(os.path.split(path)[1])[0]
    counter = 0

    with load_pic(path) as image:

        width, height = image.size
        current_image = np.array(image).copy()
        n_channels = current_image.shape[-1]
        transformation_indices = get_transformation_indices(counter, height, iterations, width)
        current_image = np.array(image)[transformation_indices[:, :, 0], transformation_indices[:, :, 1]]
        # use canvas at the end, for me this is unnecessary:
        image = fromarray(current_image)

    return image, transformation_indices


def get_transformation_indices(counter, height, iterations, width):
    x_image = np.repeat(np.arange(width).reshape(-1, 1), height, axis=-1).T
    y_image = np.repeat(np.arange(height).reshape(-1, 1), width, axis=-1)
    nx_image = (2 * x_image + y_image) % width
    ny_image = (x_image + y_image) % height
    transformation_indices = np.stack((y_image, x_image), axis=-1)
    ny_image = height - ny_image - 1
    y_image = height - y_image - 1
    while counter < iterations:
        transformation_indices[ny_image, nx_image] = transformation_indices[y_image, x_image]
        counter += 1
    return transformation_indices
Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Nice solution. But I need to trace the last indices, here is the current implementation of that. Where I convert image to array and apply transformation on the elements. If I apply your vectorized solution there, then how to get the last indices? @dankal444. Sorry, I should add my version of code in the post. But, I just write that now. That's why failed to add that before.
@WhyMeasureTheory I am not sure I understand what you need. What is "last indices"?
nx,ny of the last iteration here @dankal444. I update the question body.
@WhyMeasureTheory You need to keep track of transformation indices? For let's say iteration 321 you keep track which pixel went where so that for another image (with the same size) you can do the same transformation again in one step instead of 321?
I will check your code and inform you what I have understand @dankal444. Thanks for your help (+1).
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.