How to divide an image into evenly sized, overlapping if needed, tiles?

Question

I have an image with that has height/width dimensions of 3837x5126 pixels, respectively.

My goal is to divide this image into separate tiles with the exact dimensions of 1000x1000 pixels. If the image cannot be divided evenly, overlapping tiles should be created so the tiles are all 1000x1000 pixels.

Here's a ROUGH visualization created in PowerPoint to illustrate what I am trying to do:

My thought process was this:

1. divide the image by my ideal size (1000)
2. note the remainder
3. create an offset by dividing that remainder by all divisions
4. for each division, subtract the offset
5. overlapping tiles are created with 1000x1000 dimensions.

---

Here is the code that I have so far.

import numpy as np

def get_divisions(num, divisor):
    n = num / divisor
    divisions = math.floor(n)
    remainder = n % 1
    offset = remainder / divisions

    return divisions, offset


def get_tiles(height, width, window_size=1000):
    number_of_rows, row_offset   = get_divisions(height, window_size)
    number_of_columns, col_offet = get_divisions(width, window_size)


    tiles = []
    for row in range(number_of_rows):
        for col in range(number_of_columns):
            if row == 0:
                row_offset = 0

            if col == 0:
                col_offset = 0

            x = (col * window_size) - (col_offset * window_size)
            y = (row * window_size) - (row_offset * window_size)
            w = window_size
            h = window_size

            tiles.append([x, y, h, w])
    return np.array(tiles, dtype="uint32")

height = 3837
width = 5126
get_tiles(height, width)

outputs:

array([[   0,    0, 1000, 1000],
       [1000,    0, 1000, 1000],
       [2000,    0, 1000, 1000],
       [3000,    0, 1000, 1000],
       [4000,    0, 1000, 1000],
       [   0, 1000, 1000, 1000],
       [1000, 1000, 1000, 1000],
       [2000, 1000, 1000, 1000],
       [3000, 1000, 1000, 1000],
       [4000, 1000, 1000, 1000],
       [   0, 2000, 1000, 1000],
       [1000, 2000, 1000, 1000],
       [2000, 2000, 1000, 1000],
       [3000, 2000, 1000, 1000],
       [4000, 2000, 1000, 1000]], dtype=uint32)

As you can see, my matrix of [x, y, h, w] is incorrect because there are some x,y points that are outside of the 3837x5126 pixel image.

Any help would be greatly appreciated!

---

Edit:

Here is answer @HansHirse gave with some added tests.

import unittest
import math
import numpy as np

def tile(h, w, tile_width=None, tile_height=None, window_size=100):
    np.seterr(divide='ignore', invalid='ignore')

    if not tile_width:
        tile_width = window_size

    if not tile_height:
        tile_height = window_size

    wTile = tile_width
    hTile = tile_height

    if tile_width > w or tile_height > h:
        raise ValueError("tile dimensions cannot be larger than origin dimensions")

    # Number of tiles
    nTilesX = np.uint8(np.ceil(w / wTile))
    nTilesY = np.uint8(np.ceil(h / hTile))

    # Total remainders
    remainderX = nTilesX * wTile - w
    remainderY = nTilesY * hTile - h

    # Set up remainders per tile
    remaindersX = np.ones((nTilesX-1, 1)) * np.uint16(np.floor(remainderX / (nTilesX-1)))
    remaindersY = np.ones((nTilesY-1, 1)) * np.uint16(np.floor(remainderY / (nTilesY-1)))
    remaindersX[0:np.remainder(remainderX, np.uint16(nTilesX-1))] += 1
    remaindersY[0:np.remainder(remainderY, np.uint16(nTilesY-1))] += 1

    # Initialize array of tile boxes
    tiles = np.zeros((nTilesX * nTilesY, 4), np.uint16)

    k = 0
    x = 0
    for i in range(nTilesX):
        y = 0
        for j in range(nTilesY):
            tiles[k, :] = (x, y, hTile, wTile)
            k += 1
            if j < (nTilesY-1):
                y = y + hTile - remaindersY[j]
        if i < (nTilesX-1):
            x = x + wTile - remaindersX[i]

    return tiles

class TestTilingWithoutRemainders(unittest.TestCase):
    def test_it_returns_tiles_without_overflow(self):
        self.assertEqual(tile(500, 500, window_size=500).tolist(), np.array([[0, 0, 500, 500]], dtype="uint16").tolist())
        self.assertEqual(tile(250, 500, window_size=250).tolist(), np.array(
            [[0, 0, 250, 250], [250, 0, 250, 250]], dtype="uint16"
            ).tolist())

        self.assertEqual(tile(500, 250, window_size=250).tolist(), np.array(
            [[0, 0, 250, 250], [0, 250, 250, 250]], dtype="uint16"
            ).tolist())

class TestTilingWithRemainders(unittest.TestCase):
    def test_it_returns_tiles_with_overflow(self):
        self.assertEqual(tile(500, 501, window_size=500).tolist(), np.array(
            [[0, 0, 500, 500], [1, 0, 500, 500]], dtype="uint16"
            ).tolist())


        self.assertEqual(tile(251, 250, window_size=250).tolist(), np.array(
            [[0, 0, 250, 250], [0, 1, 250, 250]], dtype="uint16"
            ).tolist())


class TestTilingWithInvalidWindowSizes(unittest.TestCase):
    def test_it_raises_an_error_with_invalid_tile_height(self):
        self.assertRaises(ValueError, tile, 500, 500, tile_height=50000000)

    def test_it_raises_an_error_with_invalid_tile_width(self):
        self.assertRaises(ValueError, tile, 500, 500, tile_width=50000000)

    def test_it_raises_an_error_with_invalid_window_size(self):
        self.assertRaises(ValueError, tile, 500, 500, window_size=50000000)

Answer 1

Here comes my solution. Unfortunately, my code isn't based on yours, but I hope you can follow it nevertheless. The main approach is exactly the same as you described in your question.

Let's have a look at the code:

import cv2
import numpy as np

# Some image; get width and height
image = cv2.resize(cv2.imread('path/to/your/image.png'), (512, 383))
h, w = image.shape[:2]

# Tile parameters
wTile = 100
hTile = 100

# Number of tiles
nTilesX = np.uint8(np.ceil(w / wTile))
nTilesY = np.uint8(np.ceil(h / hTile))

# Total remainders
remainderX = nTilesX * wTile - w
remainderY = nTilesY * hTile - h

# Set up remainders per tile
remaindersX = np.ones((nTilesX-1, 1)) * np.uint16(np.floor(remainderX / (nTilesX-1)))
remaindersY = np.ones((nTilesY-1, 1)) * np.uint16(np.floor(remainderY / (nTilesY-1)))
remaindersX[0:np.remainder(remainderX, np.uint16(nTilesX-1))] += 1
remaindersY[0:np.remainder(remainderY, np.uint16(nTilesY-1))] += 1

# Initialize array of tile boxes
tiles = np.zeros((nTilesX * nTilesY, 4), np.uint16)

# Determine proper tile boxes
k = 0
x = 0
for i in range(nTilesX):
    y = 0
    for j in range(nTilesY):
        tiles[k, :] = (x, y, hTile, wTile)
        k += 1
        if (j < (nTilesY-1)):
            y = y + hTile - remaindersY[j]
    if (i < (nTilesX-1)):
        x = x + wTile - remaindersX[i]

print(tiles)

For some image with dimensions [512, 383] and tile size [100, 100], the tiles array looks like this:

[[  0   0 100 100]
 [  0  94 100 100]
 [  0 188 100 100]
 [  0 283 100 100]
 [ 82   0 100 100]
 [ 82  94 100 100]
 [ 82 188 100 100]
 [ 82 283 100 100]
 [164   0 100 100]
 [164  94 100 100]
 [164 188 100 100]
 [164 283 100 100]
 [246   0 100 100]
 [246  94 100 100]
 [246 188 100 100]
 [246 283 100 100]
 [329   0 100 100]
 [329  94 100 100]
 [329 188 100 100]
 [329 283 100 100]
 [412   0 100 100]
 [412  94 100 100]
 [412 188 100 100]
 [412 283 100 100]]

You get 24 tiles, each of size [100, 100] and most similar overlaps possible.

If we switch to some image with dimensions [500, 300], we get these tiles:

[[  0   0 100 100]
 [  0 100 100 100]
 [  0 200 100 100]
 [100   0 100 100]
 [100 100 100 100]
 [100 200 100 100]
 [200   0 100 100]
 [200 100 100 100]
 [200 200 100 100]
 [300   0 100 100]
 [300 100 100 100]
 [300 200 100 100]
 [400   0 100 100]
 [400 100 100 100]
 [400 200 100 100]]

As you can see, there are only 15 tiles left, and no overlaps at all.

Hope that helps!