Generating a discrete random subwindow from a given window

Question

I'm working on an image processing application, and I have the problem that I'd like to generate a random subwindow from a given window. For instance, given a 5x5 (pixel) window, I would like to generate a subwindow in a given location in x,y with a given width and height. Currently, it's OK to assume that the width and height of the subwindow will always be equal to each other. The original window, however, does not have this constraint.

Currently, I'm just generating a random width/height for the subwindow that I know fits inside of the original window. Then I generate a valid x,y coordinate that allows that subwindow to fit within the original window. The problem with the current approach is that it doesn't respect the fact that smaller windows are much more plentiful and are therefore more likely to occur. By choosing a random dimension for the subwindow width/height, I'm assuming that their distribution in terms of width and height is uniform, when in fact it is not.

For instance, imagine we are given a 5x5 window. There are 25 possible 1x1 subwindows, 16 possible 2x2 windows, 9 possible 3x3 windows, 4 possible 4x4 windows, and 1 possible 5x5 window. Thus, I should choose a 1x1 window with a probability of about 0.45 (25/(25+16+9+4+1), a 2x2 window with a probability of about 0.29, etc.

I'm not sure how to quickly generate such allowable subwindows from the correct distribution without brute force evaluating all possible windows and then simply choosing one from the list, but I'm fairly sure there's a smarter approach to doing this, I just don't know where to begin.

Thanks!

Answer 1

For an n∙n window, there are (n-m+1)² sub-windows of size m∙m.

In general, for an x∙y window, there are (x-m+1)(y-m+1) sub-windows of size m∙m.

Suggested algorithm:

• For each m, calculate the number of sub-windows; build an array of these values.
• Sum the values in the array, and generate a uniformly-distributed integer in this range
• Map this integer into the relevant sub-window size (using value-map or range-map)

Edit:

Actually you can do better.

• There is 1 sub-window with width x, 2 sub-windows with width (x-1), ... , x sub-windows with width (x-(x-1)). In total, there are (1+2+3+...+x)= x(x+1)/2 possible options for width/horizontal-position.
• Generate a uniformly-distributed integer r in the range [1, x(x+1)/2].
• Determine the width using the following formula: w= x-floor( sqrt(2r-1.75)-0.5 )

Same for the height.