Generating rich representations of environments is a fundamental task in mobile robotics. In this paper we introduce a novel approach to building object type maps of outdoor environments. Our approach uses conditional random fields (CRF) to jointly classify the laser returns in a 2D scan map into seven object types (car, wall, tree trunk, foliage, person, grass, and other). The spatial connectivity of the CRF is determined via Delaunay triangulation of the laser map. Our model incorporates laser shape features, visual appearance features, visual object detectors trained on existing image data sets and structural information extracted from clusters of laser returns. The parameters of the CRF are trained from partially labeled laser and camera data collected by a car moving through an urban environment. Our approach achieves 91 accuracy in classifying the object types observed along a 3 kilometer long trajectory.