Segmentation

You arrive here knowing a great deal about every individual point and nothing about any object. The filtering of chapter 6 left you coordinates you can defend. In chapter 7 we put a normal beside each of them. In chapter 9 we determined whether the surface underneath is the terrain. In chapter 10 we added a descriptor computed from the neighbours. But every one of those is one quantity per point, read off that point's own surroundings. And not one of them says that this point and that point lie on the same roof. That is what we determine in this chapter, and it is where the unit of work stops being the point.

Open the suburban window of figure 11.13 and you meet the difficulty in the first line of the file. You are looking at 90 632 airborne returns at 25 points per square metre. Nothing in that file records which of them lie on a roof, which on the ground and which in a tree crown. So segmentation supplies that record by grouping the points into candidate regions, each homogeneous under a criterion you choose. Every method in this chapter is a different answer to what homogeneous should mean. What you produce is a hypothesis about the scene rather than a measurement of it, so an error you make here is carried unchanged by everything downstream. Suppose you merge a roof plane with the wall beneath it: no clean roof plane is left to fit. So the reconstructed building loses that surface and every area computed from the model inherits the loss. That is why we give as much space in this chapter to measuring a partition (section 11.9) as to producing one. In section 11.8.1 we apply the geometric methods to one indoor scan in order.

Read that definition against the airborne window and notice how little of your work it fixes. Consider a normal-similarity criterion: the roof of one house is one region and the road is another. Now switch to a proximity criterion, and the house and the car parked against it fall into a single region. Which is the correct segmentation? Both are, and both satisfy definition 11.1 equally, since you choose the criterion and nothing in the definition attaches a meaning to a region. That is the line between this chapter and chapter 12.

That change of unit has consequences. Remember that cleaning, normal estimation and ground extraction each computed one result per point from that point's own neighbourhood. But whether two points belong together depends on the pair, and ultimately on the whole partition, so every method here works on chains, samples or graphs and costs you more than anything earlier in the pipeline. These methods consume the normals of chapter 7 and the spatial indexes of chapter 4. They work best once the ground extraction of chapter 9 has removed the one surface that touches every object in the scene. What they return feeds the classifiers of chapter 12, the modelling methods of chapter 16 and the learned pipelines of chapter 19.