Patent ID: 8238619
Filing Date: 2012-08-07
Classification: G06K

Abstract:
1. A method of extracting ridge and valley lines from three-dimensional point data, the method comprising the steps of: (a) receiving point data input from a three-dimensional range scanning system; (b) estimating a normal vector by analyzing localized neighborhood information of each point from the received point data; (c) creating an approximation of a moving least squares (MLS) surface of points with regard to each point of the received point data and the estimated normal vector thereof; (d) obtaining connection information on each point from the MLS surface of points; (e) measuring a curvature value and a curvature derivative regarding each point on the MLS surface of points to obtain a curvature direction; (f) extracting ridge and valley points by measuring zero-crossing of the connection information; and (g) creating ridge and valley lines by connecting the ridge and valley points in the curvature direction; wherein the localized curvature value and its derivative are measured with regard to one point on a surface approximated by the MLS approximation technique, so that the ridge and valley lines are extracted from the three-dimensional point data with unknown connection information; wherein the connecting step (g) further comprises the step of (g.3) removing unnecessary feature lines of the ridge and valley lines determined by a preset threshold; and wherein the removing step (g.3) further comprises the steps of: (g.3.1) removing ridge and valley lines using a criterion selected from the group consisting of lines shorter than the preset threshold and lines at a point having a curvature smaller than the preset threshold; and utilizing a filtering technique to create a threshold as defined in an equation herein below, based on the edge length and the curvature metric (σ=K wherein, r