Sampling and Resampling

You can already bring a tile off disk, place its coordinates in a frame you can defend, and index it for logarithmic-time neighbour queries. You obtained that much from the raw records of chapter 3 and the spatial indexes of chapter 4. You still need a tile small enough to compute on, and we address that gap in this chapter.

Here is the size of it. The airborne window of figure 5.6 holds 349 095 measured points over 110 m of an Amsterdam canal. The two subsets we draw from it in this chapter keep 10 000 points each. A little under 3 per cent of the measurements survive. Is that an extreme case? It is the ordinary one. A square kilometre at the 28.9 points per square metre of that tile already holds 28.9 million points. Thirty-five square kilometres pass a billion. A billion points fit neither in memory nor in your time budget for a downstream algorithm.

How much has to go? That depends on the sensor, and you want both patterns in mind before you set a parameter. The airborne windows we use in this chapter arrive at 28.9 and 21.1 points per square metre. This puts their mean spacing at 19 and 22 cm, so a single window holds little redundancy to remove. Terrestrial density behaves differently. It falls as $1/r^2$ with range, since a scanner that steps its beam by a constant angle spreads that step over a footprint growing with the square of the distance. Figure 5.1 shows that law evaluated between 3 m and 30 m, where the density falls from about 300 to about 3 pts/cm$^2$. So one station gives you two orders of magnitude of density variation with no change in the scene. A statement about downsampling means nothing without the sensor and the range beside it.

Now notice what the definition leaves open: the chosen property. The two subsets of figure 5.6 satisfy it equally and differ only in which property of $\mathcal{P}$ each one holds on to. That is what this chapter is really about: which points do you keep, what does keeping them preserve, and what have you given up? Upsampling is separate, since the points it returns were never measured. We treat it separately at the end, in section 5.7.

Let's start with the three properties of a raw point cloud that force the reduction, since a different sampler removes each.