Patent ID: 8209143

Claim:
A computer-implemented method for laser scan alignment comprising: splitting, by a laser scan alignment computer, an area covered by a plurality of laser scans into a first set of grid cells, the first set of grid cells having a first resolution; estimating, by the laser scan alignment computer, a first template surface representation for the first set of grid cells using original poses of the plurality of laser scans; aligning, by the laser scan alignment computer, each laser scan in the plurality of laser scans to the estimated first template surface representation to provide a first updated pose for each laser scan in the plurality of laser scans; splitting, by the laser scan alignment computer, the area covered by the plurality of laser scans into a second set of grid cells, the second set of grid cells having a second resolution, wherein the second resolution of the second set of grid cells is finer than the first resolution of the first set of grid cells; estimating, by the laser scan alignment computer, a second template surface representation for the second set of grid cells using the first updated poses for the plurality of laser scans; repeating, by the laser scan alignment computer, the splitting the area into the second set of grid cells, and the estimating the second template surface representation until the aligned plurality of laser scans substantially converges with the second template surface representation; simultaneously aligning, by the laser scan alignment computer, the plurality of laser scans to each other to provide a final pose for each laser scan in the plurality of laser scans; dividing, by the laser scan alignment computer, the plurality of laser scans into overlapping groups of laser scans; and providing the estimated second template surface representation to a display as a map of the area covered by the plurality of laser scans, wherein the splitting the area covered by the plurality of laser scans into the first set of grid cells comprises splitting the mea covered by each group of laser scans in the overlapping groups of laser scans into the first set of grid cells, and wherein the aligning each laser scan in the plurality of laser scans to the estimated first template surface representation comprises aligning each group of laser scans in the overlapping groups of laser scans to the estimated first template surface representation to provide the updated pose for each group of laser scans in the overlapping groups of laser scans.