Given an input image X of size m*n, a block size of T, how to generate k random non-overlapping blocks of size T*T?

user_3006092 0
Viewed 252

While reading the paper Local Shannon entropy measure with statistical tests for image randomness, I come up with the following question:

Given an input image X of size mn, a block size of T, generate k random non-overlapping blocks of size TT.

I came up with the idea that represent every block by its top-left coordinate. Then, I used the following piece of code to generate those non-overlapping blocks. Although I employed some randomness into this code, the result is not random and does not cover all possible situations. Are there any efficient algorithms for doing this? Even keywords for further search are appreciated.

m, n = Y.shape
T = 44
k = 30
possible_blocks_vert = m // T
possible_blocks_horiz = n // T
possible_blocks = possible_blocks_vert * possible_blocks_horiz
if possible_blocks < k:
    assert False
else:
    last_possible_starting = (divmod(m, T)[1], divmod(n, T)[1])
    random_y0, random_x0 = np.random.randint(last_possible_starting[0]), np.random.randint(last_possible_starting[1])
    random_xs = [random_x0+i*T for i in range(possible_blocks_horiz)]
    random_ys = [random_y0+i*T for i in range(possible_blocks_vert)]
    
    i = 0
    Xs = []
    Ys = []
    for x in np.random.permutation(random_xs):
        for y in np.random.permutation(random_ys):
            Xs.append(x)
            Ys.append(y)
            i += 1
            if (i >= k):
                break
        if (i >= k):
            break
Xs, Ys

There are at least two downsides to this implementation:

  • The selection first selects all of the first random row, then all of the second and so on until all k blocks are chosen
  • The selection is not distributed in all possible places.

Note. The paper proposes a novel measure called Local Shannon Entropy, LSE, which generates k random blocks and compute their average Shannon entropy as LSE.

algorithm python
4 Answers

You could try jittered sampling (Figure 7.18 c). That is, split the image into (at least) k cells and place each block into a randomly picked cell somewhere inside of it.

For simplicity, let's assume the image is 256x256 pixel, each of 10 blocks is 32x32 pixels. Split the image into regular grid of 4x4 (ceil(sqrt(k))) cells each of which is 64x64 large, pick 10 cells out of 16, place the 32x32 block at random into each 64x64 cell.

user_10374070

I don't think you can generate all of the blocks in one shot and satisfy all your requirements at the same time. You can generate each block and check that it's non-overlapping:

import random

WIDTH = 100  # m
HEIGHT = 70  # n
BLOCK_SIZE = 12  # t
NUM_BLOCKS = 15  # k

blocks = []
while len(blocks) < NUM_BLOCKS:
    x = random.randint(0, WIDTH-BLOCK_SIZE-1)
    y = random.randint(0, HEIGHT-BLOCK_SIZE-1)
    for block in blocks:
        # if the block overlaps an existing block, try again
        if not (x+BLOCK_SIZE < block[0] or 
                block[0]+BLOCK_SIZE < x or
                y+BLOCK_SIZE < block[1] or
                block[1]+BLOCK_SIZE < y):
            break
    else:
        blocks.append((x, y))

To visualize:

import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle

ax = plt.gca()
for block in blocks:
    ax.add_patch(Rectangle(block, BLOCK_SIZE, BLOCK_SIZE,
                           color=(random.random(), random.random(), random.random())))
ax.set_xlim(0, WIDTH)
ax.set_ylim(0, HEIGHT)
plt.show()

Note that this type of solution may fail (run forever) if there's no room to insert an additional block.

user_84518140

Woodford's answer gives a uniformly random sample, but it has two related problems:

  1. It can get stuck and run forever. This happens when its choice of blocks so far leaves no room for any more blocks to fit, so no more non-conflicting block placements are possible.
  2. It can take a very long time. This happens when there is room for more blocks, but only a tiny fraction of locations are non-conflicting, so a lot of time is spent generating random conflicting locations and rejecting them.

Neither of these issues are likely to bite you if kT^2 is small compared to mn. But in any case, the second problem can be eliminated (which should speed things up across the board) and the first problem can be detected and used to backtrack or restart (which turns an infinite loop into a possibly slow but finite one).

To eliminate the second problem, the idea is that, instead of picking a random (x, y) location and testing whether it conflicts with existing block placements, keep only a list of non-conflicting (x, y) locations and randomly choose among them -- then remove all locations from this array that have now become conflicting. Let's represent block placements using the coordinates of their top-left corners, and use an array validLocations of (int, int) pairs to hold the list.

  1. Initially, set validLocations to contain all (x, y) pairs obeying x < n-T and y < m-T.
  2. On each iteration:
    1. If validLocations is empty, restart from the beginning or backtrack. (This is the situation in which Woodford's algorithm would loop forever.)
    2. Otherwise, randomly choose an index into this array. We know that the coordinate pair (Rx, Ry) at this location is a valid placement for a block.
    3. Add (Rx, Ry) to the list of block placements.
    4. Remove all coordinate pairs from validLocations that are no longer valid. That is, remove all pairs (x, y) such that abs(Rx-x) < T && abs(Ry-y) < T. This can be done using a single pass through the array.
user_479840

Interesting problem. One approach could be to randomly pick k seed cells and randomly pick one of them to expand.

One other consideration what distribution should the blocks follow?

user_7863510
Related