DETAILED ACTION
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claims 1-10, 14-15 and 17-24 are pending.
Claims 11-13 and 16 are canceled.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-10, 14-15 and 17-24 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Regarding independent claims 1, 14 and 15, the following 2-step analysis is applied for analyzing the 35 U.S.C. § 101 subject matter eligibility of the claims.
Step 1: Statutory Category
Claim 1 recites a "method for data processing," which falls within the statutory category of a process.
Step 2A, Prong 1: Abstract Idea: Claim 1 is directed to an abstract idea, specifically mathematical concepts. The claim recites:
Linear interpolation of coordinate points using Euclidean distance calculations (eqs. 1-3, specification);
Mathematical data structure construction (K-D tree) involving median calculations and recursive binary partitioning (eq. 4, specification);
Douglas-Peucker thinning algorithm, a well-known mathematical curve simplification technique ([0004], specification);
Weighted elevation calculation using Gaussian kernel functions and normalization (eqs 5-7, specification).
These operations constitute mathematical relationships, formulas, and calculations.
Step 2A, Prong 2: Integration into Practical Application: The claim does not integrate the judicial exception into a practical application. The additional elements merely recite:
"Acquiring a point sequence": generic data gathering;
"Obtaining a first point sequence": routine data manipulation;
"Obtaining elevations": calculating and outputting results.
The operations amount to manipulation of abstract data representations (coordinate points) using mathematical algorithms. The specification explicitly states the purpose is to thin geographic data and maintain features ([0003], specification), which is data content manipulation, not technological improvement.
Step 2B, Significantly More: The claim does not add significantly more beyond the abstract idea. The claim limitations amount to:
Generic computer implementation on terminals/servers ([0037]);
Well-understood, routine, conventional mathematical operations (interpolation, K-D tree construction, Douglas-Peucker algorithm);
Conventional data processing steps performed in a conventional manner;
No unconventional computer components, techniques, or improvements.
The specification describes standard hardware (processors, memory) executing routine mathematical algorithms (Fig. 10). The claim does not recite specific technical improvements to computer functionality, data structures beyond their conventional use, or unconventional technological solutions.
Conclusion: Claim 1 (and 14-15) is directed to an abstract idea without significantly more and is therefore patent-ineligible under 35 U.S.C. § 101.
Regarding dependent claims 2-10 and 17-24: Limitations in all dependent claims have been examined in a similar way to the above independent claims. It was found that all dependent claims 2-10 are patent-ineligible under 35 U.S.C. § 101: each merely adds further mathematical detail to the abstract idea without technological improvement or unconventional implementation.
Claim Rejections - 35 USC § 103
The following is a quotation of pre-AIA 35 U.S.C. 103(a) which forms the basis for all obviousness rejections set forth in this Office action:
(a) A patent may not be obtained though the invention is not identically disclosed or described as set forth in section 102 of this title, if the differences between the subject matter sought to be patented and the prior art are such that the subject matter as a whole would have been obvious at the time the invention was made to a person having ordinary skill in the art to which said subject matter pertains. Patentability shall not be negatived by the manner in which the invention was made.
Claim(s) 1 and 14-15 is/are rejected under 35 U.S.C. 103 as being unpatentable over Norberg et al (US2012/0139325) in view of Crews (US2013/0028482).
Regarding claims 1 and 14-15, Norberg teaches a method for data processing, comprising:
(Norberg, “a computerised method for identifying and classifying edges in a dataset representative of an open-pit mine terrain”, [abstract])
acquiring a point sequence comprising a plurality of coordinate points;
(Norberg, Fig. 2, “a dataset representative of a 3D model of the terrain in question is obtained 202”, [0065]; “a plurality of points of the terrain”, [0010]; “Each point, q in a point cloud is a point in three dimensions: q=(x,y,z)”, [0068])
interpolating the point sequence, and constructing a multi-dimensional data structure tree by using the interpolated point sequence;
(Norberg, “Examples of representations that can be used for the method described herein include grid representations such as a digital-elevation-model (DEM) or a digital-terrain-model (DTM), an irregular triangle format such as a triangulated-irregular-network (TIN), or finite-element-mesh representations. DEM is used where the data represents either the terrain, or the terrain together with surface features. DTM refers to data that represents the terrain only”, [0091], “Such representations may originate from a variety of data processing methods including ..., linear interpolation”, [0092]; DEM, DTM and TIN are 3D models for modeling terrain structures, and generated using, e.g., linear interpolation)
obtaining a first point sequence by
(Norberg, “The terrain dataset (i.e. the output from the terrain estimation process) is a grid in the xy-plane, with each point in the grid having an estimated elevation”, [0099]; the grid of points may be obtained from linear interpolation applied to the data point for creating the grid)
obtaining elevations of the first point sequence based on the multi-dimensional data structure tree and the first point sequence.
(Norberg, “For a point where the height is to be estimated, the closest N points are fetched from a KD-tree of the dataset as described above. The mean value x of these points as well as the variance σ^2 are then calculated”, [0084]; “The terrain dataset (i.e. the output from the terrain estimation process) is a grid in the xy-plane, with each point in the grid having an estimated elevation”, [0099]; “Such representations (for grid) may originate from a variety of data processing methods including ..., linear interpolation”, [0092]; KD-tree organizes the dataset and is used to retrieve nearby coordinate points for elevation estimation; each point is assigned an elevation value; interpolation techniques are applied to the KD-tree (organized dataset) to generate the elevation values)
Norberg does not expressly disclose but Crews teaches:
... thinning...;
(Crews, “A system and method for thinning a point cloud. In one aspect of the method, the point cloud is generated by an imaging device and data points are thinned out of the point cloud based upon their distance from the imaging device”, [abstract]; “the method 100 may calculate the distance between the subject data point and the point of view 20. This distance may then be used in calculating a skipRatio at step 114. The skipRatio is a measurement of whether or not the data point should be skipped (i.e. not included in the thinned point cloud). In one embodiment, the skipRatio is a number between 0 and 1 where 0 indicates the data point should be skipped (i.e. not included in the thinned point cloud) and 1indicates the data point should not be skipped (i.e. included in the thinned point cloud)”, [0028]; “Preferably, the skipRatio is calculated so as to make data points further from the point of view 20 more likely to be excluded from the thinned point cloud. Similarly, the skipRatio is preferably calculated to make data points closer to the point of view 20 more likely to be included in the thinned point cloud”, [0029]; the thinned point cloud is obtained by thinning the point cloud and keeping a subset of the points, where the thinned point cloud is the result of interpolating the thinned points as part of the thinning process to retain detail; “These data sets can be quite large, requiring significant amounts of computing resources to process. Thus, attempts have been made to thin these point clouds to reduce the set of data points that need to be worked with for a given task”, [0003])
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention was made to incorporate the teachings of Crews into the system or method of Norberg in order to thin a point cloud to reduce the number of points to process while retaining detail of the closer points and reducing computational strain for large datasets. The combination of Norberg and Crews also teaches other enhanced capabilities.
Claim(s) 2-5 and 17-20 is/are rejected under 35 U.S.C. 103 as being unpatentable over Norberg et al (US2012/0139325) in view of Crews (US2013/0028482) and further in view of Wikipedia (Linear interpolation, Apr 2021).
Regarding claims 2 and 17, the combination of Norberg and Crews teaches its/their respective base claim(s).
The combination further teaches the method according to claim 1, wherein interpolating the point sequence, and constructing the multi-dimensional data structure tree by using the interpolated point sequence comprises:
performing linear interpolation based on the coordinate points in the point sequence; and
(Norberg, “Such representations may originate from a variety of data processing methods including ..., linear interpolation”, [0092]; the linear interpolation is based on the coordinate points in the dataset as more specifically described by Wikipedia, “Solving this equation for y, which is the unknown value at x, gives
PNG
media_image1.png
45
218
media_image1.png
Greyscale
”,p1; note that the above formular is a 1D linear interpolation for y at x between two geometrical points x0 and x1, i.e., x0 < x < x2, figure, p1; for linear interpolation of 2D points or 3D points, similar formulas are also well known in the art as “bilinear interpolation” for 2D (see, e.g., https://en.wikipedia.org/wiki/Bilinear_interpolation) and
“trilinear interpolation” for 3D (see, e.g., https://en.wikipedia.org/wiki/Trilinear_interpolation))
The combination of Norberg, Crews and Wikipedia further teaches:
constructing the multi-dimensional data structure tree based on the coordinate points in the interpolated point sequence.
(Norberg, Crews, see comments on claim 1)
Regarding claims 3 and 18, the combination of Norberg, Crews and Wikipedia teaches its/their respective base claim(s).
The combination further teaches the method according to claim 2, wherein performing linear interpolation based on the coordinate points in the point sequence comprises:
calculating a Euclidean distance between any two coordinate points in the point sequence;
(Wikipedia, see comments on claim 2; in 1D, (x1-x0 is the Euclidean distance between x0 and x1)
obtaining an interpolation number based on the Euclidean distance and a preset density; and
generating the interpolated point sequence based on the interpolation number and the any two coordinate points in the point sequence.
(Wikipedia, each interpolation performed in a line section between x0 and x1 will divide the line section into two section containing three points x0, x and x1; for a large number of points, each interpolation will approximately double the density of points; the target number of the interpolation corresponding to a target point density is really a design choice)
Regarding claims 4 and 19, the combination of Norberg, Crews and Wikipedia teaches its/their respective base claim(s).
The combination further teaches the method according to claim 3, wherein obtaining the interpolation number based on the Euclidean distance and the preset density comprises:
obtaining an interpolation number of coordinate points to be interpolated in the point sequence based on a product of the Euclidean distance and the preset density.
(Wikipedia, see comments on claim 3; if initial density is D0 with an equal spacing distance L0, the product of D0*L0 remains constant for n number of interpolation because (n*D0)* (L0/n) = D0*L0)
Regarding claims 5 and 20, the combination of Norberg, Crews and Wikipedia teaches its/their respective base claim(s).
The combination further teaches the method according to claim 3, wherein generating the interpolated point sequence based on the interpolation number and the any two coordinate points in the point sequence comprises:
obtaining coordinate points to be interpolated corresponding to the interpolation number based on a difference value between the any two coordinate points in the point sequence and the interpolation number; and
generating the interpolated point sequence based on the coordinate points to be interpolated and the coordinate points in the point sequence.
(Wikipedia, see comments on claim 3; for x0 < x(0,1) < x1, x1 < x(1,2) < x2, ..., the generated interpolated point sequence will be x(0,1), x(1,2), ...)
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JIANXUN YANG whose telephone number is (571)272-9874. The examiner can normally be reached on MON-FRI: 8AM-5PM Pacific Time.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, Applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Amandeep Saini can be reached on (571)272-3382. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see http://pair-direct.uspto.gov. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/JIANXUN YANG/
Primary Examiner, Art Unit 2662 1/29/2026