This paper presents a method for increasing spatial resolution of a depth map using its corresponding high-resolution (HR) color image as a guide. Most of the previous methods rely on the assumption that depth discontinuities are highly correlated with color boundaries, leading to artifacts in the regions where the assumption is broken. To prevent scene texture from being erroneously transferred to reconstructed scene surfaces, we propose a framework for dividing the color image into different regions and applying different methods tailored to each region type. For the region classification, we first segment the low-resolution (LR) depth map into regions of smooth surfaces, and then use them to guide the segmentation of the color image. Using the consensus of multiple image segmentations obtained by different super-pixel generation methods, the color image is divided into continuous and discontinuous regions: in the continuous regions, their HR depth values are interpolated from LR depth samples without exploiting the color information. In the discontinuous regions, their HR depth values are estimated by sequentially applying more complicated depth-histogram-based methods. Through experiments, we show that each step of our method improves depth map upsampling both quantitatively and qualitatively. We also show that our method can be extended to handle real data with occluded regions caused by the displacement between color and depth sensors.