How to sample (without replacement) from a large set by randomly sampling non-overlapping subsets?

I've got a large corpus of video, and I want to randomly sample frames over the whole corpus.

A naive way to do this is convert all videos to a giant set of images with ffmpeg then subsample the gigantic set.

An alternative is to convert each video, subsampling from its frames.

I'd like to take the second approach to avoid having to store more than a few images at a time, but I'd also like the final randomly-sampled distribution to match the first approach. Is there a statistical relationship that would allow me to do this?

I can come up with a way to get close to what I'm looking for:

When I select from the big set, I'll select some number of frames out of the total: $$\frac{n}{N}$$. So if I set the probability that I select any individual frame as $$\frac{n}{N}$$, I should get approximately $$n$$ frames back. It's not exact, but I can do this selection procedure on single examples, which means I can do it on subsets of any size by iterating through frames from any video in the corpus.

In my case I don't actually know better than an estimate for $$N$$ without converting all videos at least once. I could get this number by iteration and not have to sit on a mountain of data at once.

Is there a more elegant way?

• IIUC, you don't want to store all the converted videos because that would take loads of memory? But I think you could still go through the entire corpus, get the number of frames for each video n_i and store these, as well as compute N = sum n_i once. Then, for sampling n frames, you sample n videos (with replacement) with probability n_i / N, and then convert each sampled video, and sample a frame in each video uniformly? Commented Jun 24, 2020 at 18:49
• yeah, I know I could loop through and not store all images at once to get $N$. I still don't want to do that work and then delete the files, because I'll just have to convert again, and I don't want to sit on the files. The only way around that would be a method that doesn't rely on $N$, which probably isn't possible. Commented Jun 24, 2020 at 18:57
• Sorry, what do you mean by "sit on the files"? Also, you could approximate the number of frames by either 1) the size of the file or 2) the length of the videos in seconds. Then you can do what I describe but instead, n_i is one of these 2 things? Commented Jun 25, 2020 at 0:03

You have to know $$N,$$ even if finding out requires examining all the videos. Then you can make a second pass to sample them. But you can sample them separately, one video at a time.

Suppose the videos are a collection $$\mathcal V$$ and each video $$V\in\mathcal V$$ is itself a collection of frames, so the set of all frames is

$$\mathcal F = \bigcup_{V\in\mathcal V}V.$$

Because all videos are assumed to have no overlapping frames, the total population contains

$$N = |\mathcal F| = \bigcup_{V\in\mathcal V}|V|$$

frames, where $$|\quad |$$ refers to the cardinality of any set.

To sample $$n$$ frames randomly from $$\mathcal F$$ your alternatives include:

• ("Naively") take a random subset of $$n$$ frames from $$\mathcal F.$$ If you focus on a single video $$V$$ with $$k = |V|$$ frames, notice that the chance this sample includes exactly $$0\le X \le k$$ frames is the hypergeometric probability $$p(X,k,N) = \frac{\binom{k}{X}\binom{N-k}{n-X}}{\binom{N}{n}}.$$

• Pick one $$V\in \mathcal V$$ consisting of $$k=|V|$$ frames. Randomly determine a subsample size $$X$$ from the distribution with probability function $$\Pr(X)=p(X,k,N)$$ and sample $$X$$ (distinct) frames from $$V.$$ Iterate this process with the remaining videos (where $$N$$ is now $$N-k$$ and $$n$$ is $$n-X$$).

You can make your life a lot easier by choosing to sample a percentage of the total frames. For example, if you decide you want a training set with 1% of all of the frames in the population, you can go through each video and sample 1% of the frames. This is just stratified random sampling.

You won't know the exact number of frames you will end up with in your sample. However, if that is necessary, you can aim for a specific sample size with a little extra work. If you have data on the file size/length of each video, and each video's resolution, you can build a simple model to predict the number of frames of each video. You can use that model to estimate N, and then determine the percentage that will almost certainly give you, at minimum, the desired sample size.

• This is what I sort of ended up doing. I'd still like the generalized equation for the future, but for this application it seemed to work well enough. Commented Jun 26, 2020 at 2:02
• @pavel-komarov what about this approach is not ideal? Perhaps there is a better method. Commented Jun 26, 2020 at 16:18