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

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$.

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]$.

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!

@kram1032 yes, I agree that this answer is a starting point. I believe better and more general samplers exists, but getting an algorithm that does the job and proving it actually does it right is a bit of work (as we can see by the long answer). With respect to $\alpha$, if you are doing supervised learning and the training steps are not too long, it might be a good idea to vary $\alpha$ and check the AI performance. Of course, only if your aspect ratio being $\frac{hw}{HW}$ is not a must.

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 :)

I know I actually asked for this, but it turns out very extreme aspect ratios, as this method tends to give, are, well, too extreme. I have changed the algorithm to simply reject interval pairs if the aspect ratio is too extreme, and try again. Is that a reasonable thing to do or do you think that will distort the other properties? (I still don't want squares, just not as extreme rectangles)

@kram1032 intuitively, I think that the probability of a pixel being inside the random rectangle will still be constant for all pixels. For the asymptotic ratio of areas, I believe it will change. Moreover, depending on how you reject, it can go to $0$, which I suppose is something you do not want. Maybe we should continue this conversation in the chat.

Zero-size intervals are "lone pixels", which can be a problem indeed

(I'd later change it so the aspect ratio isn't hard-coded in. This was just for testing)

yeah, in principle that'd be fine, but another function I relied on later down the line ended up generating a singular matrix in such cases and trying to invert it

I am not sure, but I think it might be okay if we stop the recursion before n = 1

For instance, if we set n = 4 as "the base case", then you would return [1, 16] (and its shifteds intervals) as the smallest possible sides for the rectangle

I think that because the induction proofs would remain almost the same think, just changing the base case

(plus indentations)

So that'd amount to simply setting the first line to k==2 and probably changing what it returns then

Yes, if you want a base case of b, then just replace the first two lines of the method by

if k == b:
    return (0, 2**b - 1)

ok that makes sense. Easy fix

Yes, that should be fine. I will verify it carefully later

The aspect ratio part is different though, as it will rely on two separate samples

For the aspect ratio, MAYBE you could use a base case that gives at least the ratio you want

This would introduce dependence between the random width and length

So, you would sample the x_1, x_2 first, for instance, and then sample y_1, y_2 stopping in a base case that allows the ratio to be higher than what you want. However, I am not sure that the algorithm would have its properties if we did so

So you would introduce the "base case" as a parameter as well

it'd certainly be easy enough to at least restore symmetry by randomly picking which one goes first

That is true, and its a good idea

I still think that this would allow any pixel to have the same probability of appearing in the sample rectangle

And would bound the areas ratio away from 0

Not entirely sure I like that better than simply rejecting samples though - at least in terms of acceptance rate, it's perfectly fine. No notable impact on time at all

Yes, rejecting seems fine too. Maybe even more than conditioning as I suggested

The algorithm is very fast since it decays exponentially. It should be O(log(W) + log(H)), and O((log(W)+log(H))/p), where p is the probability of acceptance

yeah absolutely not an issue

OK, then I think I'll introduce b for a minimum scale, but I'll stick to rejecting very skewed rectangles for now. If you have any more insight after more analysis, I'll gladly reconsider though :)

If I find anything that can be useful/interesting for your, I will share it here. Feel free to ask for any further doubts

As a last suggestion, you can do a simple simulation to check if the probability of the pixels is constant after these modifications, and that the expected area ratio seems to converge to something. I will do the simulations myself later.

Yeah might give that a try as well, thanks

Ops, its actually 2**(b-1) - 1

if k == b:
    return (0, 2**(b-1) - 1)

that makes more sense, thanks

How do you get code indentation in chat? The usual stuff seems not to work

I go to the editor, copy from there, paste it here :)

hmm, seems to not work. I somehow still get zero sized intervals. I'll have to figure out why that happens

(with your previous version I didn't though)

I tested the code here and the minimum size is 2**(b-1)

Can you share your current code?

sorry about the indentations, it just flattens itself everytime :-/

You did not change k == 1 to k == b

ah sorry, yes I did, but I changed it back

might still be the problem currently, testing

changed to b and instantly got 0 again

If you are running a jupyter notebook and used the "import" from the script, you need to reload the notebook

nah, local python script. Rerunning from scratch everytime

Ah yes, I found the bug

You did not pass b as an argument for the recursive call

OH dangit, right that makes sense

You wrote l0, r0 = sample_interval(k-1, alpha)

it is l0, r0 = sample_interval(k-1, alpha, b)

literally had the same issue with alpha before, duh

thanks!

That is why I avoided implementing it as an argument hahaha, I always forget

No problem

yeah what a pain to debug haha

There is a bug on the code, the base case should be b = 0

So the code is

If you use the previous base case, it does not give constant probability for all points

ok so originally it also should have been k == 0 then?

Yes

It is just because that, when there is a single point, we should have 2^k = 1, so that k = 0

off by one errors amirite

Yes there are 3 hard things in computer science: (1) Naming variables; (2) Finding off-by-one errors;

So, I ran some simulations somewhat "throughly" and it seems our modification works

I tested varying b, the aspect ratio, alpha

I computed the "gap probability", that is, the probability of the pixel that appears the most minus the one that appears less often

It seems to converge to 0 as I increase the sample size, which is what is expected

This is the code to run the simulation, you can check it yourself if you want

ah nice sim code, I'll try it out, thanks

Really the one big downside to this is how it's locked into powers of 2. The input image has to be power-of-2-dimensioned, and all the intervals it comes up with are also power-of-2-dimensioned. If those two things were relaxed, I think this would be just about perfect

It looks like the rejection sampling version also has the probability gap go to 0 but far more slowly

Since your alpha is about 0.1228, I imagine that smaller rectangles are more probable

Indeed, the probability of choosing the smallest interval possible is $(1-alpha)^(k-b)$

Since your k is not that large and alpha is "close" to 0, I imagine that probability is big

With respect to the powers of 2, I think that you can change it to the power of any natural number m you want, you would just have to change 1/2 to 1/m and the shifting would be a bit more complicated, not just summing 2^(k-1)

But I do not think generalizing powers helps you, if powers of 2 are a problem, then others powers probably do not help either

yeah, ideally I'd like basically any interval size to be possible. Oh well...

(any within the range of course)

The idea of power of 2 is the symmetry in the recursion. You have to guarantee that, whatever you do to the pixels on the first half, you have to do to the other half as well. If you can generalize that, I think it would work, powers of 2 or not

Yeah it's a classic divide-and-conquer style algorithm isn't it

Exactly