Registration of range images requires the identification of common portions of surfaces between which a minimization is performed. This paper proposes a framework for the use of dense attributes of range image elements as a matching constraint in the registration. These attributes are chosen to be invariant to rigid transformations, so that their values is similar in different views of the same surface portion. Attributes can be derived from the geometry information in the range image, such as surface curvature, or be obtained from associated intensity measurements. The method is based on the Iterative Closest Compatible Point algorithm augmented with a random sampling scheme that uses the distribution of attributes as a guide for point selection. Distance considered compatible on the basis of their attributes. The performance o the method is illustrated on a rotationally symmetric object with color patterns.