Reconstructing 2d image from 1d pixel sequence

Imagine there's an image of size n by m. Then it's flattened into a list of pixels with length of n*m. How to restore original image if n and m are unknown?

The idea is not to find all pairs of divisors of length, but to find some metric which is highest then sampling width is closest to original width of an image. Simular to adjusting horizontal hold on old analog TV.

I'm sure there is an algorithm which is supposed to do this exact thing but I couldn't find it.

Bruteforcing it appears to work.

I try all combinations (h, w) where n is the number of pixels, and h and w are divisors such that n == h * w.

I return the pair of divisors that minimise the average difference between the value of a pixel on a row with the corresponding pixel on the next row.

Note that the value of a pixel is a triplet representing the three colours. I did not even try to be smart about what "difference between two colours" might mean. I just subtracted red from red, green from green, blue from blue, and summed it all with .mean() because I was too lazy to do a sum of squares or anything smart.

On an example picture of a bear, it works.

from imageio.v3 import imread
from sympy import divisors
import numpy as np

img = np.array(imread('Downloads/bear.png'))
height, width, n_channels = img.shape # (90, 136, 3)
flatimg = img.reshape((height*width, n_channels)) # (12240, 3)

def find_dims(flatimg):
    n_pixels, n_channels = flatimg.shape # (12240, 3)
    divs = divisors(n_pixels)[1:-1]
    height,width = min(
        ((height, width) for height, width in zip(divs, reversed(divs))),
        key=lambda dim: np.diff(flatimg.reshape((*dim,n_channels)), axis=0).mean()
    )
    return height, width

print(find_dims(flatimg))
# (90, 136)

80x153 85x144 90x136

102x120 120x102 136x90

Try the divisors of the image area, with reasonable ratios (if the image wasn't cropped, the ratio should not exceed 16:9.

For the different combinations, compute the sum of the vertical gradient magnitude across the whole image. It should be minimum for the right choice.

If you look at raw2tiff.c in the tools directory of libtiff it seeks to around the middle of a raw image file and guesses different scanline widths and reads pairs of lines till the correlation between the two is maximised and uses that as the width. I assume the theory is that most scanlines in a photo are pretty similar, i.e. highly correlated with each other.