Environment sensing is required in order for robots to operate safely in either shared workspaces between robots and human or unpredictable natural environments. However, available perceptual inference algorithms require many smoothness assumptions such as a flat ground plane, straight walls, etc; thus their efficiency depends on the degree of smoothness of the beliefs. Indeed, current autonomous navigation techniques only work well in highly structured environments, but fail to deal with cluttered outdoor environments. Particularly, vegetated terrain introduces one more degree of freedom to the problem that what is considered as an "obstacle" from a purely geometric point of view, may not represent a danger for the robot if it is composed of compressible vegetation. Motivated by concrete robotics problems, we explicitly pursue solutions for vegetation detection and terrain classification, which have recently become the core of any control system for advance autonomous navigation in outdoor environments.