Recently, a section of the I-85 in Atlanta collapsed due to a human-caused fire (images below). The accident impacted Atlanta traffic and led to the closure of the I-85 in both directions in the vicinity of the damaged section.

Due to the impact of the accident, damage removal, traffic control, and construction of the new section began almost immediately.

Of course, the authorities also wanted to document the state of the bridge. As part of the damage assessment, the Georgia Department of Transportation needs to create a post-disaster scan of the bridge and compare it to a scan performed earlier, when the bridge was fully intact. The scan analysis will also assist in the repair as it will provide important geometric information regarding the section.

Let's go through a simulated version of the analysis. With the current tools in hand, you should be able to identify the missing components from the original laser scans. Now, these “laser scans” are far larger than what you have been dealing with so far, so your algorithms to date may not work out of the box due to memory constraints. We'll break this problem into a few smaller problems that will lead towards the final answer.

The laser scanning folk were nice enough to register the original scan to the new scan, so they are both in the same coordinate system (i.e., they have a common origin). that means, you can directly check the point clouds to see what differences there are. Eventually, we'd like to quantify the differences not in terms of points, but in terms of surfaces. Since the point cloud is too big, we'll need to partition it too.

Let's first see if we can identify the difference in the bridge due to both the collapse of the bridge, as well as due to the burning of some of the components. Create a new member function for your pts3D class that takes in another pts3D object (call it the testCloud) and a distance threshold ($\rho_{dist}$), then returns the indices into the points of the testCloud that are more than ($\rho_{dist}$) away from the points in the calling point cloud. For that, you may also want to create a member function called distanceToPoints. The idea is to be able to invoke a member function as follows:

  farPointInds = sourceCloud.getDifference(testCloud, rho);

and have it pass back the indices to the points in testCloud that are far away from the points in sourceCloud (as in a distance more than rho).

To aid this procedure, write a member function called distanceToPoints whose stub is:

function [minDist, minInd] = distanceToPoints(this, testPts)
...
end

Cleverly using pdist you can find both the minimizing distance and the associated index for the return arguments. Your main function getDifference should invoke it and then perform the distance thresholding to identify the outlier points and returns their indices.

You should also write a member function called removeInds

function remPts = removeInds(this, inds)
...
end

that takes a set of indices to remove, removes the points from the point set, and returns a new point set (e.g., a pts3D object) with the removed points. Using this removal function, you should visualize the set of points that are outliers, so you can visualize what parts of the bridge were damaged or altered in the fire.

Note: You shouldn't be setting just any threshold, otherwise, you may get an incorrect outcome. It is best to zoom into the point cloud and figure out what the typical point to point distances are (or, if you are clever, you can use pdist to figure this out for you). Your threshold should be such that you don't mistake neighbouring points for matches.

Deliverable: Turn in a plot of the set of points that differ. Describe in English which bridge components were damaged.

To be able to process the point cloud, we will have to partition it into smaller subsets that are not too big (say between 20,000 to 30,000 points roughly). The laser scanning company was nice and aligned the bridge with the y-axis. Furthermore, there is some symmetry along the x-axis. That means the bridge can be split in half (along the x-axis), and then multiple times along its span (y-axis). Your job is to write a function called partitionCloud that will partition it based on a target point cloud subset size 'desCard' (i.e., desired cardinality).

function subClouds = partitionCloud(thePts, desCard)

...

end

If should perform the half and half split for the x-axis, then perform the multiple split along the y-axis by density.

Approach: The approach to do this would be to examine the density of the point cloud along the span axis and then create a subset along intervals that keep the subset cardinality lower than the desired cardinality. To get the density, it might be helpful to compute a histogram of the point cloud (or its split) based on the y-coordinate. Computing the cumulative sum, then tells you how much points are accumulated as you go from one extreme to the other. Create partitions just before the cumulative sum ends up being more than the desired upper cardinality. The output should be an array with an even quantity of pts3D objects representing the partitions.

Deliverable: Plot a few of the partitions showing that you got it done. Provide the cardinality of all the partitions that you've obtained to show that they are less than the desired cardinality threshold. Sum their cardinalities and show that you get the number of points in the original point cloud (it would be wrong to lose points!).

Images from:

1. WCY 5 News
2. Source: Fox 6 Now
3. Source: Atlanta Journal Constitution
4. Source: Atlanta Journal Constitution
5. Source: Atlanta Journal Constitution

ECE4580 Learning Modules