Detecting changes between the existing building basemaps and newly acquired high spatial resolution remotely sensed (HRS) images is a time-consuming task. This is mainly because of the data labeling and poor performance of hand-crafted features. In this paper, for efficient feature extraction, we propose a fully convolutional feature extractor that is reconstructed from the deep convolutional neural network (DCNN) and pre-trained on the Pascal VOC dataset. Our proposed method extract pixel-wise features, and choose salient features based on a random forest (RF) algorithm using the existing basemaps. A data cleaning method through cross-validation and label-uncertainty estimation is also proposed to select potential correct labels and use them for training an RF classifier to extract the building from new HRS images. The pixel-wise initial classification results are refined based on a superpixel-based graph cuts algorithm and compared to the existing building basemaps to obtain the change map. Experiments with two simulated and three real datasets confirm the effectiveness of our proposed method and indicate high accuracy and low false alarm rate.