The interest in change detection techniques for autonomous robots has increased considerably during recent years. This is partly due to the fact that changes in robot's working environments are relevant for most tasks and robotics applications. Changes or Novelties are usually detected by comparing the current data acquired by the robot with its previous knowledge (a map or any other model of its surroundings). Gaussian Mixture Models (GMM) have been satisfactorily used for detecting changes in 3D point clouds. However, these methods have drawbacks such as a long computational times and strong dependence on the parameters of the algorithms. In structured environments like offices or homes, it is possible to reduce the number of points to be processed by filtering unlikely-to-change regions of the scene. This paper introduces the concept of Vertical Surface Normal Histogram (VSNH). VSNH provides a method for removing from the point clouds acquired those points associated to the main planes: ceiling, walls and floor. Removing these points decreases the size of the problem and improves the segmentation of the environment into Gaussian Mixture Models. The experimental results demonstrate that the proposed method based on GMM and VSNH achieves change detection in structured indoor environments faster and more accurately than previous approaches.