The U.S. Patent and Trademark Office granted on Tuesday a patent titled “Building segmentation for densely built urban regions using aerial LIDAR data” to a team of researchers led by Bogdan Calin Mihai Matei and including Supun Samarasekera, Janet Yonga Kim, Charles Fielding Finch Karney, Harpreet Singh Sawhney, Rakesh Kumar. It’s basically what it sounds like, a method for identifying the ground, identifying buildings, and throwing away the rest of the data from a lidar-generated point cloud. Then automatically identifying the buildings and modeling them as separate things. The question is: What are they going to do with it?
The team works for SRI International, “an independent, nonprofit research institute conducting client-sponsored research and development for government agencies, commercial businesses, foundations, and other organizations.” They were founded by Stanford in 1964 and now bring in $585 million a year in revenue.
Maybe they’re best known for having created and spun-off Siri, the voice in your phone, the technology for which Apple acquired in 2010. Who knew that came from a DARPA initiative? Not me.
It’s not clear in the description whether all of the R&D is done under contract for someone else who already has an idea for a commercial application or whether they develop technology and then sell it off on behalf of investor types who throw money behind an idea and see if they can sell it to someone else to commercialize. Thus, it’s unclear if this is a patent that will immediately give a going concern some leverage to protect the uniqueness of its software, or whether this is just the beginning of what will be a commercial enterprise sometime in the future.
I’ve got an email in to inquire.
But it’s interesting to look at the approved patent itself. First, it was initially filed in 2008. When you consider the way the technology has leapt forward in the last few years, it seems hard to believe that a patent idea from four years ago could still represent cutting-edge technology. Surely, even they have significantly surpassed themselves by this point, right? Here’s the full text of their patented method description:
A method for extracting a 3D terrain model for identifying at least buildings and terrain from LIDAR data is disclosed, comprising the steps of generating a point cloud representing terrain and buildings mapped by LIDAR; classifying points in the point cloud, the point cloud having ground and non-ground points, the non-ground points representing buildings and clutter; segmenting the non-ground points into buildings and clutter; and calculating a fit between at least one building segment and at least one rectilinear structure, wherein the fit yields the rectilinear structure with the fewest number of vertices. The step of calculating further comprises the steps of (a) calculating a fit of a rectilinear structure to the at least one building segment, wherein each of the vertices has an angle that is a multiple of 90 degrees; (b) counting the number of vertices; (c) rotating the at least one building segment about an axis by a predetermined increment; and (d) repeating steps (a)-(c) until a rectilinear structure with the least number of vertices is found.
Or, if you like things in flow charts, this:
When you put it like that, it doesn’t seem all that revolutionary, right? But I’m guessing the patent is in the details and this idea of “best fitting” and “fewest number of vertices.” (Why most of those words are capitalized, but not “fitting,” I’m having a hard time understanding. No capitalizing articles makes sense, same with prepositions, but “is” is a verb and “fitting” is a participle, and sure they feel left out.)
Here is how the problem they’re solving is described: “Automating building segmentation is a critical component in any 3D modeling system by providing 3D regions (segments) with little or no manual interaction. Each of the aforementioned methods employ automatic building segmentation algorithms which fall short in efficiency or resolution. More particularly, the above-cited references assume that the ground (as opposed to buildings) covers the largest surface area, and are therefore innapropriate for use in modelling dense urban areas. Accordingly, what would be desirable, but has not yet been provided, is an efficient, accurate method for automatic building segmentation for automatically extracting 3D models of dense urban regions using aerial LIDAR data.”
I don’t know all the programs out there, but it seems like people are doing this already. I guess if the method is different, though, just the fact that they have the same abilities doesn’t matter. I’m no lawyer. Heck, Exelis could be licensing this technology for all I know (though I don’t think so).
Anyway, it looks like SRI has a pretty extensive wing that focuses on the 3D space. GIS applications are prominent, as are virtualization for training, but check out this robotic mapping solution they’ve got:
It produces images like this:
It appears to be a collaboration with the Robotics Technology Consortium – where have these guys been hiding (this is how a reporter pretends it’s not his fault he didn’t know something. If he doesn’t know about it, they must have been “hiding,” rather than the journalist just not paying attention)? This is definitely something I’m going to look into further.