Uniformly sample pieces of a rectangle Say I have a rectangle $R: \left[{0,W}\right] \times \left[{0,H}\right]$ where $W$ is the width and $H$ is the height, with coordinates $\left(x, y\right) \in \mathbb{R}^2$.
I would like to randomly pick out (axis-aligned) rectangles $r_s: \left[{x_s-\frac{w_s}{2},x_s+\frac{w_s}{2}}\right] \times \left[{y_s-\frac{h_s}{2},y_s+\frac{h_s}{2}}\right]$ such that:

*

*every position in $R$ is equally likely to be picked (in the limit, if I overlapped all $r_s$, the density with which each point in $\left(x, y\right) \in R$ is sampled will be uniform)

*the sampled relative areas $a_s= \frac{w_s \times h_s}{W \times H}$ and aspect ratios $\rho_s = \frac{H}{W} \frac{w_s}{h_s}$ are also even (I'm not quite sure what the appropriate way to say this would be. But effectively, ideally, I'd like the algorithm to be "scale-free" with respect to $a_s$ if it can be. If it can't, then whatever closest notion it actually can be instead is fine. For $\rho_s$, I think some sort of cutoff is necessary to avoid divisions by 0, but that is fine. Let's just say there is a $\rho_{max}$ and a corresponding $\rho_{min}=\frac{1}{\rho_{max}}$)

Additionally, overscanning is allowed (the rₛ may land partially outside R), but at least half the area of the each rₛ must land within R. - If that helps, this also means the $r_s$ may actually occasionally be larger than $R$. I don't mind if they are but this is not a requirement. I think the largest possible $r_s$ would be $r_{max}: \left[\frac{W}{2}+\frac{\sqrt{2}W}{2},\frac{W}{2}-\frac{\sqrt{2}W}{2}\right] \times \left[\frac{H}{2}+\frac{\sqrt{2}H}{2},\frac{H}{2}-\frac{\sqrt{2}H}{2}\right]$ with relative area $a_{max} = 2$
Is it possible to sample in this manner? And how might one do so efficiently?

The use-case is machine learning and image processing using pytorch, so code is also welcome, however I should be fine if you give me a basic algorithm:
In particular, I have an AI that can process images of at most some fixed resolution. I am generating an image larger than that context size, and in order for the AI to still approximately get the full image, I am sending it pieces of the whole, scaled to fit the AI's context. If I do this unevenly, the AI over-focuses on parts of the image. I'd like it to consider the whole thing as evenly as possible. Every part of the image should be covered evenly, and every scale as well.
Technically, the varying aspect ratio isn't as necessary, however I found that this can help with the robustness of my results.
 A: I provide here one possible answer to your question. I had to make a few assumptions, but based on your comments, I believe they are acceptable.
I will describe briefly the assumptions, the algorithm and its properties, and will leave the path for the full mathematical derivation for assertions.
For easy of writing, given $m \in \, \mathbb{N}$, consider the notation $[m] = \{1,\ldots,m\}$.
The assumptions were:

*

*We are sampling integer rectangles contained on the rectangle $[W]\times[H]$. This seems okay since you said you are working with images;


*The dimensions $W$ and $H$ are powers of $2$. This seems less feasible, but I believe you could scale your images so that this assumptions is satisfied. On the full derivation, it becomes clear why this assumptions is required.
To get an algorithm to sample rectangles, we actually just need an algorithm to sample intervals from an integer interval $[2^{n}]$. Fix $\alpha \, \in \, (0,1)$, I will now describe a "pseudocode" for $H_\alpha(n)$, a recursive method that receives an integer $n$ and returns $[l, r]$, the left and right index of integer interval from $[2^{n}]$:



*

*If $n = 0$, return $[1, 1]$. If not, go to step (2);


*With probability $\alpha$, return $[1, 2^n]$. Else, go to step (3);


*Call $H_\alpha(n-1)$ recursively and store its output in $[l_0, r_0]$. With probability $1/2$, return $[l_0, r_0]$. Else, return $[l_0 + 2^{n-1}, r_0 + 2^{n-1}]$.
Note: In the algorithm above, assume independence between all random variables used to make decisions where to halt or not.
Let $W = 2^n$ and $H = 2^m$. To sample a rectangle contained in $[W]\times[H]$, let $(x_1, x_2) = H_\alpha(n)$ and $(y_1, y_2) = H_\alpha(m)$, and assume that $(x_1, x_2)$ and $(y_1, y_2)$ are independent. Your rectangle is  $R = [x_1, x_2]\times[y_1, y_2]$.
Here is a python implementation for you:
from random import random

def sample_interval(k):
    alpha = 0.4 # Can be any number in (0,1)
    if k == 0:
        return (0, 0)

    # with prob alpha return the whole interval
    if random() < alpha:
        return (0, 2**k - 1)
    
    l0, r0 = sample_interval(k-1)
    # half the times, do not add 2**(k-1)
    if random() < 1.0/2:
        return (l0, r0)

    # half the times, do add 2**(k-1)
    else:
        return (l0 + 2**(k-1), r0 + 2**(k-1))

# remember that W = 2**n and H = 2**m
def sample_rectangle(n, m):
    x1, x2 = sample_interval(n)
    y1, y2 = sample_interval(m)

    upper = (x1, y1)
    lower = (x2, y2)

    return (upper, lower)

Now you are surely asking: why sample it like this? The reason is that this algorithm has the properties you want:
(P1) Every integer point (pixel) on $[W]\times[H]$ has the same probability of appearing in the sampled rectangle. This probability is constant for all points, but depends on $n$ and $m$. Asymptotically, if $W$ and $H$ go to infinite, this probability converges to $(\frac{2\alpha}{1+\alpha})^2$;
(P2) The limit average rectangle area divided by the area of the big rectangle is scale free. That is, let $A_{nm}$ be the random variable associated with area a rectangle sampled from $[2^n]\times[2^m]$ according to this algorithm, then
\begin{equation*}
a_s = \lim_{n\rightarrow\infty}\lim_{m\rightarrow\infty} \frac{E[A_{nm}]}{W H} = \left(\frac{2\alpha}{1+\alpha}\right)^2 \quad.
\end{equation*}
Since these are the properties you asked, this sampling method solves your problem. Note that you can change $\alpha$ freely. Increasing $\alpha$ makes you sample the whole rectangle more. Decreasing it makes you sample smaller rectangles more. If $\alpha$ is very close to $0$, you will probably end up sampling lone pixels.
Mathematical Proofs The proofs are based on mathematical induction since the algorithm is inherently recursive. We also focus on the proof on the interval case. For the rectangles, it follows trivially from the interval case and independence.
Lets prove all points have equal probability of appearing in the random interval. For $n = 0$, it is trivial. Assume that all points in $[2^{n-1}]$ have constant probability $p_{n-1}$ to appear in a random interval (this obviously depends on $n$, but it can not depend on the  point).
Now we prove for $k = n$. Consider a point in $[2^k]$ that is smaller or equal to $2^{k-1}$. There are two ways that a random interval can contain this point. First, in the case we sample the whole interval $[2^k]$, which has probability $\alpha$. Second, if, after not sampling in the first step, the interval from recursive call contains the point AND we do not add $2^{k-1}$. This second event has probability $(1-\alpha)\times p_{n-1}\times\frac{1}{2}$ (just use independence and the induction hypothesis). Therefore
$$ p_n = \alpha + \frac{(1-\alpha)}{2}p_{n-1} \quad.$$
You can prove that the probability is the same if you consider a point above $2^{k-1}$. This finishes the proof.
For the average size of the interval, writing $E_n$ as the expected interval size, the same idea gives you the recursion
$$ E_n = \alpha 2^n + (1-\alpha)E_{n-1} \quad.$$
Now divide both sides by $2^n$, we have
$$ \frac{E_n}{2^n} = \alpha + \frac{1-\alpha}{2}\frac{E_{n-1}}{2^{n-1}} \quad.$$
Taking the limit and calling it $e_s$, we have
$$ e_s = \alpha + \frac{1-\alpha}{2}e_s \quad,$$
and a bit of algebra gives you $e_s = \frac{2\alpha}{1+\alpha}$. Since the average area of the rectangle is the product of the average size (again, independence), it follows that
$$ a_s = e_s^2 \quad,$$
giving you your scale free algorithm.
