4
$\begingroup$

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.

$\endgroup$
10
  • 1
    $\begingroup$ Do you mean that $a_s$ and $\rho_s$ should be uniformly distributed? If so, do $a_s$ and $\rho_s$ need to be independent of $x_s$ and $y_s$? Could you also provide some context explaining why you need to do this? $\endgroup$ Nov 26, 2021 at 13:06
  • $\begingroup$ @JarleTufto I believe independence of $x_s$ and $y_s$ would be desirable, yes $\endgroup$
    – kram1032
    Nov 26, 2021 at 13:11
  • 2
    $\begingroup$ Then I don't think what you suggest is possible. If you cannot place the centers of the sampled rectangles outside R, then you will get an edge effect making the probability that a point is included in the sampled rectangle smaller towards the boundary of R. Except in the limit that the size of the sampled rectangles tends to zero. $\endgroup$ Nov 26, 2021 at 13:18
  • $\begingroup$ If either the condition on the overscan or the midpoint independence were relaxed, would it be possible then? $\endgroup$
    – kram1032
    Nov 26, 2021 at 13:31
  • 2
    $\begingroup$ Yes, if you sample rectangles uniformly from a larger region and reject the ones with no overlap, then there would be no edge effect. Alternatively, if you make the sample rectangles smaller and sample more frequently towards the boundary of R (dependency on $x_s,y_s$), you could maybe devise a method that makes every point in R equally likely to be picked, but that seems like a quite hard problem to solve. $\endgroup$ Nov 26, 2021 at 13:35

1 Answer 1

2
$\begingroup$

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}]$:

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

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

  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.

$\endgroup$
9
  • 1
    $\begingroup$ If I see that right, you are assuming that the minimum coordinate is (1, 1) and the maximum one is (W = 2^w, H = 2^h)? Very minor thing that's gonna vary between languages and such, but most of the time (python included), you'd want to start with (0, 0) and end with (W-1, H-1) - thanks, this looks very promising. I would prefer if the power-of-2 requirement were dropped for a less stringent rational aspect ratio (which is always possible with integer-dimensioned images) Technically I want this to work for floats, but that might be more trouble than it's worth, so your assumption is fine there $\endgroup$
    – kram1032
    Nov 30, 2021 at 21:53
  • 1
    $\begingroup$ That is not a problem, just subtract $1$ at the end and you will be fine. I implemented it as $1$ to $W$ just because the recursion is easier to write. I will update the python code to make it range from $0$ to $W-1$. $\endgroup$ Nov 30, 2021 at 21:54
  • 1
    $\begingroup$ Just some quick observations: You can use different $\alpha$ when sampling from intervals from $[W]$ and $[H]$. By selecting the right constants, you can get whichever aspect ratio $\rho_s$ or $a_s$ you want. I considered the same $\alpha$ just for ease of understanding. Moreover, even if you use the same $\alpha$ for both, you can make the asymptotic area ratio $a_s$ be whatever value you want since $f(\alpha) = 2\alpha/(1-\alpha)$ is a bijection from $[0,1]$ to $[0,1]$. $\endgroup$ Nov 30, 2021 at 22:21
  • 1
    $\begingroup$ Ok, I really like, that there is no overscan at all here. I guess if the AI can see an area $h w$ and my image has area $H W$ I'd likely want $a_s$ to be $\frac{h w}{H W}$ giving me $\alpha = \frac{1}{2 \sqrt{\frac{H W}{hw}} - 1}$ as a solid starting point. I can make do with powers of 2 for $H$ and $W$ for now, so I'll accept this answer. If somebody found a way to generalize this to arbitrary (rational) aspect ratios, I'd probably switch to that answer instead. For now this will work though. thank you! $\endgroup$
    – kram1032
    Nov 30, 2021 at 22:29
  • 1
    $\begingroup$ Yeah that $\alpha$ was meant as an initial guess. Hyperparameter search would definitely be a more rigorous way to figure out a good value for it. Thanks :) $\endgroup$
    – kram1032
    Nov 30, 2021 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.