This Repo is an example (or my interpretation) of the adaptive grid compression shown in the following SpaceX video:

[Youtube Video]

xt.py runs the compression on a grayscale image cat.jpg using nearest neighbor (the video shows linear interpolation).

The trick to make this fast is using numpy's vectorized operations. Anchor points can be selected by striding the input array in both dimensions. Then we can simply resize this anchor-point array back up to its original size using the desired interpolation

anchor = arr[::s, ::s]
n0, n1 = anchor.shape

interp = zoom(anchor[::2,::2], 2, order=order)[:n0,:n1]

Next we save the error values that exceed epsilon.

error = anchor - interp

mask = np.abs(error) > epsilon
# Save error values that exceed epsilon
compressed[::s,::s][mask] = error[mask]

And then repeat with stride s *= 2

The result is a small set of anchor points, and the "compressed" image. This result image resembles a gradient image in that the values shown represent the areas of greatest change. In order to actually reduce the memory footprint of the image, we can represent the image, which should contain mostly zeros, as a sparse matrix. It appears that the SpaceX adaptive grid uses a sparse representation similar to 'Dictionary of Keys' (DOK). Scipy has a dok_matrix type, but unfortunately it does not extend to N dimensional tensors/arrays.

In short, the decompression works by interpolating between the anchor points, and adding back the stored errors.

Interpolation	Non-Zero	Compressed	Decompressed
nearest	65.6%
bilinear	74.3%
bicubic	98.4%

Interpolation	Non-Zero	Compressed	Decompressed	Error	%
nearest	40.3%				0.9%
bilinear	35.0%				0.7%
bicubic	36.0%				0.9%

Interpolation	Non-Zero	Compressed	Decompressed	Error	%
nearest	18.7%				4.4%
bilinear	13.2%				3.9%
bicubic	14.1%				4.3%

Interpolation	Non-Zero	Compressed	Decompressed	Error	%
nearest	6.7%				11.1%
bilinear	3.6%				9.1%
bicubic	3.9%				10.1%