Reconstruct Values from Overlapping Patches

Task

Write reconstruct_patches(image_shape, patches, overlap_rule). The declared image shape is (height, width, channels) with positive dimensions. Each item in patches is a dictionary with:

{"origin": (top, left), "patch": values, "mask": valid}

values is a uint8 array of shape (patch_height, patch_width, channels). valid is a boolean array of shape (patch_height, patch_width). A True cell at (r, c) contributes values[r, c] to source position (top + r, left + c). A padded patch uses False outside the declared image; every in-bounds position must be True, and every True position must be in-bounds. Origins are non-negative integer row and column coordinates.

The only accepted overlap_rule is the supplied rule "mean". Build an integer coverage array of shape (height, width) and an accumulated int64 array of shape (height, width, channels). Add each valid patch value once and increment coverage once. Return a dictionary containing these arrays, "uncovered" (a tuple of uncovered (row, column) pairs), and "status".

If every pixel is covered and each accumulated channel value divides exactly by its coverage, return status "ok" and an independent uint8 array under "reconstruction", calculated as accumulated // coverage[..., None]. If any pixel is uncovered, return status "incomplete", set "reconstruction" to None, and list every uncovered coordinate in row-major order. If all pixels are covered but a mean is not integral, return status "non-integral mean" and None rather than silently rounding. Invalid patch records or a rule other than "mean" may raise ValueError.

Example

Two overlapping copies of the same source pixel contribute twice to its coverage and twice its value to accumulated. Dividing the accumulator by coverage recovers the original value exactly; coverage zero is never treated as a value to divide by.

Your implementation

You may import NumPy as np. Do not modify patch arrays or print or ask for input. The returned evidence arrays must not share writable memory with any input patch.