Creating overlapping, square patches for rectangular images

Given be a rectangular image img and patch s. Now I would like to cover the whole image with square patches of side length s, so that every pixel in img is in at least one patch using the minimal number of patches. Furthermore I want neighboured patches to have as little overlap as possible.

Thus far: I have included my code below and worked out an example. However it does not work yet perfectly. Hopefully, someone finds the error.

Example: Given is img of shape: (4616, 3016) and s = 224 That means I will 21 patches on the longer side, 14 patches on the smaller the width, 21*14 = 294 patches in total.

Now I try to figure out patches how to distribute the overlap between the patches. My patches can cover an image of size: (4704, 3136), thus my patches in the height have to cover 88 overlapping pixels missing_h = ht * s - h, width is analogous.

Now I try to figure out, how to distribute 88 pixels on 21 patches. 88 = 4* 21 + 4 Thus I will have hso = 17 patches with overlap shso = 4 and hbo = 4 patches with overlap 5, width is analogous.

Now I simply loop over the whole image and keep track on my current position (cur_h, cur_w). After each loop I adjust, cur_h, cur_w. I have s, my current patch number i, j, that indicates if the patch has a small or big overlap.

import numpy as np

def part2(img, s):
    h = len(img)
    w = len(img[0])

    ht = int(np.ceil(h / s))
    wt = int(np.ceil(w / s))

    missing_h = ht * s - h
    missing_w = wt * s - w
    hbo = missing_h % ht
    wbo = missing_w % wt
    hso = ht - hbo
    wso = wt - wbo
    shso = int(missing_h / ht)
    swso = int(missing_w / wt)

    patches = list()
    cur_h = 0

    for i in range(ht):
        cur_w = 0
        for j in range(wt):
            patches.append(img[cur_h:cur_h + s, cur_w: cur_w + s])
            cur_w = cur_w + s
            if j < wbo:
                cur_w = cur_w - swso - 1
            else:
                cur_w = cur_w - swso
        cur_h = cur_h + s
        if i < hbo:
            cur_h = cur_h - shso - 1
        else:
            cur_h = cur_h - shso

    if cur_h != h or cur_w != w:
        print("expected (height, width)" + str((h, w)) + ", but got: " + str((cur_h, cur_w)))

    if wt*ht != len(patches):
        print("Expected number patches: " + str(wt*ht) + "but got: " + str(len(patches)) )


    for patch in patches:
        if patch.shape[0] != patch.shape[1] or patch.shape[0] != s:
            print("expected shape " + str((s, s)) + ", but got: " + str(patch.shape))
    return patches


def test1():
    img = np.arange(0, 34 * 7).reshape((34, 7))
    p = part2(img, 3)
    print("Test1 successful")


def test2():
    img = np.arange(0, 4616 * 3016).reshape((4616, 3016))
    p = part2(img, 224)
    print("Test2 successful")


test1()
test2()

Above problem can be fixed, making the following edits:

hbo = missing_h % (ht-1)
wbo = missing_w % (wt-1)
shso = int(missing_h / (ht-1))
swso = int(missing_w / (wt-1))