Patent ID: 8599278

Claim:
A method for estimating a plane in a range image, comprising: a data conversion step of converting three-dimensional data of pixels arranged in a square lattice to a houndstooth arrangement; a triangle-of-interest computation step of focusing on a small triangle of interest that constitutes a smallest unit of the houndstooth arrangement, and computing, based on converted three-dimensional data corresponding to three vertices of the small triangle of interest, an equation of a plane defined by the three vertices, and a cross product of two vectors corresponding respectively to two sides of the small triangle of interest as a normal vector of the plane; an adjacent triangle computation step of computing a normal vector for each of three small triangles that are adjacent in such a manner as to respectively share a different one of three sides of the small triangle of interest; a plane candidate search step of searching for a plane candidate by performing, for all of the converted three-dimensional data while shifting the small triangle of interest focused on in the triangle-of-interest computation step, a process of deriving a largest value among respective magnitudes of cross products of all pairings of the normal vector computed in the triangle-of-interest computation step and the three normal vectors computed in the adjacent triangle computation step, and a process of determining a large triangle composed of the small triangle of interest and the three adjacent small triangles to be a plane candidate if the largest value is less than or equal to a first threshold; a plane determination step of sequentially repeating the triangle-of-interest computation step, the adjacent triangle computation step and the plane candidate search step with a large triangle determined to be a plane candidate in the plane candidate search step taken as the small triangle of interest in the triangle-of-interest computation step, recursively performing the repetition while enlarging the small triangle of interest, and, when an area of a new large triangle determined to be a plane candidate is greater than or equal to a second threshold, determining a region corresponding to the large triangle to be a plane; and a plane-determined region separation step of separating the region determined to be a plane in the plane determination step from a range image.