Draft:Entropy Compass

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

A. Entropy Compass[1]: The map parsing process is bootstrapped by the observation that office-like environments tend to be aligned to a pair of orthogonal axes. This alignment defines a notion of cardinal directions, with a quarter-revolution ambiguity: any 90◦ rotation of the map is just as good as another. While this alignment is useful when presenting maps to human users, it also serves to provide a strong prior to geometry recognition tasks such as wall extraction. The proposed method of determining the dominant orientation of an environment presumed to be significantly rectilinear is to consider histograms of projections of occupancy grid data. For a given orientation, θ, 2D point data from the occupancy grid is projected onto a line and binned into a histogram, Hθ, with bin extents, bini . Hθ,i = X p∈points countθ,i(p) countθ,i(p) = � 1 if sin(θ)px + cos(θ)py ∈ bini 0 otherwise To determine whether this projection of the map data is aligned with a dominant direction of the building geometry, the entropy of the histogram associated with each projection angle, − P i Hθ,ilog(Hθ,i), is summed with its orthogonal partner, θ + 90◦ , yielding a measure whose minimum occurs when the projection and building orientations (with respect to an arbitrary coordinate frame) coincide. The intuition behind this approach is that most walls in a building lie on lines that are either parallel or orthogonal to each other. Hallways then provide strong reinforcement for a specific orientation, while adding unstructured noise to the orthogonal projection. A representative plot of the described measure, shown in Figure 5, displays the characteristic local minima at a pair of orientations separated by a quarter revolution at 47◦ and 137◦ .

B. Wall Extraction The orientation provided by the entropy compass informs a mechanism for extracting line segments representing wall geometry. The histogram for a given orientation is considered, for instance the histogram associated with the 47◦ projection in Figure 5, and the local maxima of the histogram bins are identified, as these bins correspond to likely walls in the mapped environment. The coordinates of occupancy grid cells that project into the locally maximal histogram bins may then be sorted along the axis of projection and broken into contiguous runs. These contiguous runs represent collinear wall segments, and can be filtered by requiring that a wall segment be above some minimum length (e.g. one meter). The robustness of this method may be improved by scanning in a plane perpendicular to the ground plane. Such scan data may be used to identify occupancy grid cells for which a vertical column of points has been detected. An example is to require that a particular 2D occupancy grid cell be sensed as occupied at three different heights separated by at least half meter intervals. The resulting wall occupancy information can be efficiently represented using a data structure designed for sparse tenancy. The wall extraction component of the topometric map parsing technique is not required to detect every wall in the environment. Instead, the aim is to provide sparse evidence for divisions between free space regions. Since the walls in the environments considered here are seldom visible, the entropy compass is relied upon to provide a prior for detecting the suspected planar geometry. The geometry extracted from the range data is insufficient by itself to reconstruct a floor plan suitable for effective exploration, but its output is still valuable for subsequent analyses.


  1. ^ Cowley, Anthony; Taylor, Camillo J.; Southall, Ben (May 2011). "Rapid multi-robot exploration with topometric maps". (:unav). doi:10.1109/icra.2011.5980403.