Automatic range image registration without any knowledge of the viewpoint requires identification of common regions across different range images and then establishing point correspondences in these regions. We formulate this as a graph-based optimization problem. More specifically, we define a graph in which each vertex represents a putative match of two points, each edge represents binary consistency decision between two matches, and each edge orientation represents match quality from worse to better putative match. Then strict sub-kernel defined in the graph is maximized. The maximum strict sub-kernel algorithm enables us to uniquely determine the largest consistent matching of points. To evaluate the quality of a single match, we employ the histogram of triple products that are generated by all surface normals in a point neighborhood. Our experimental results show the effectiveness of our method for rough range image registration.