DETAILED ACTIONS
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Priority
Acknowledgment is made of applicant’s claim this application being a National Stage of the International Application No. PCT/KR2022/013195, filed on September 2, 2022, and benefit of foreign priority from Korean Patent Application No. KR10-2021-0141243 filed on October 21, 2021 and Korean Patent Application No. KR10-2022-0105413 filed on August 23, 2022.
Information Disclosure Statement
The information disclosure statement (“IDS”) filed on 04/18/2024 was reviewed and the listed references were noted.
Drawings
The 18-page drawings have been considered and placed on record in the file.
Status of Claims
Claims 1-18 are pending.
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph:
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the claim limitation(s) uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitations are: “an image divider”, “a feature extractor”, “a submap similarity score calculator”, and “a global localization processor” in claim 11, “a first geometric feature extractor”, “a second geometric feature extractor” , and “a structural feature extractor” in claim 13, and “a first subtractor”, “a second subtractor”, and “a third subtractor” in claim 14.
Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, it/they is/are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
If applicant does not intend to have this/these limitation(s) interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.
Claim Rejections - 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
(a)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
Claims 1, 9, and 11 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Cop et al., (US 2020/0386862 A1, published 12/10/2020), hereinafter referred to as Cop.
Claim 1
Cop discloses a method for global localization of a mobile robot (Cop, [0111], “a method for use in performing localisation in a three - dimensional ( 3D ) environment will now be described with reference to FIG . 1”), performed by a processor of a computing device (Cop, [0157], “, the microprocessor 300 executes instructions in the form of applications software stored in the memory 301 to allow the required processes to be per formed”) equipped in the mobile robot (Cop, [0153], “Preferably , the at least one laser sensor , one or more electronic processing devices and data store are located on - board a mobile robot or autonomous vehicle”), the method comprising:
dividing a global map image (Cop, [0119], “It is therefore important to recognise that the method relies upon an existing map (i.e. global point cloud) of the 3D environment that has previously been determined in a mapping exercise using the laser sensor, for example in a SLAM based mapping of the environment.”) into a plurality of query submap images (Cop, [0119], “After mapping, the map is segmented into a plurality of portions, each having a respective point cloud and second intensity descriptors are determined for each portion or segment of the map.”, [0044], “generating a submap using at least one portion of the map selected based on the ranking of portions of the map as potential locations”);
calculating a histogram value representing a geometric feature of each query submap image (Cop, [0006], “The usage of global descriptors (that compute single statistics for the whole local scan based on geometrical information) is known to describe places by a histogram of points elevation”, [0047], “retrieving previously calculated submap geometrical descriptors calculated using submap keypoints associated with the portions of the map that are included in the submap”);
calculating a reflection symmetry score representing structural feature information about each query submap image (Cop, [0114], “The local scan performed by the laser sensor consists of a local point cloud of the robot's surroundings. The local point cloud consists of spatial information from which the structure of the environment is determined. In addition to range information, the laser sensor can also provide a measure of intensity for each point, which is the strength of return after reflection from a surface. More precisely, intensity refers to the ratio of power that was emitted by the laser and the power that returned to it. Whilst the term intensity is used generally throughout this disclosure, it should be understood that related parameters such as reflectivity should also be considered to fall within the scope of the term intensity. Reflectivity is a property of a surface obtained from intensity by compensating for intrinsic parameters of the sensor as well as extrinsic features such as distance to the object, incidence angle, air density etc.”, [0018], “calculating the first intensity descriptor based on at least one statistical measure for a distribution of the intensity data in the local point cloud”);
calculating a submap similarity score between each query submap image and submap images stored in a database (Cop, [0141], “It is to be appreciated that submap geometrical descriptors are calculated along with the second intensity descriptors for the map after the 3D environment is mapped and stored in the data store. The geometrical descriptors are calculated for each portion extracted from the map and therefore when portions of the map are merged into a submap, the corresponding geometrical descriptors are retrieved for use in performing the geometrical recognition.”, [171], “Each submap geometrical descriptor is queried against each local geometrical descriptor obtained from the local scan”, [0037], “for each comparison between the first intensity descriptor and a second intensity descriptor: [0039] i) determining a plurality of relative orientations of the second intensity descriptor; and, [0040] ii) comparing the first intensity descriptor segments with the second intensity descriptor segments for each of the plurality of relative orientations of the second intensity descriptor; [0041] b) determining a similarity value for each orientation;” ), based on the histogram value (Cop, [0006], “The usage of global descriptors (that compute single statistics for the whole local scan based on geometrical information) is known to describe places by a histogram of points elevation”) and the reflection symmetry score (Cop, [0114], “intensity refers to the ratio of power that was emitted by the laser and the power that returned to it. Whilst the term intensity is used generally throughout this disclosure, it should be understood that related parameters such as reflectivity should also be considered to fall within the scope of the term intensity.”); and
determining a submap image which is the most similar to the query submap image, based on the submap similarity score (Cop, [0174], “At step 455, the correspondences are clustered based on geometrical consistency. The result of the correspondence search step is a set of matchings between points in the submap and those in the local scan. To ensure that found correspondences belong to the actual instances of the local scan, geometric constraint is imposed on them.”, [0177], “At step 470, the candidate cluster having the highest number of correspondences is selected as the most likely location candidate”), and performing the global localization of the mobile robot, based on coordinate information included in the determined submap image (Cop, Fig. 4C, [0181], “method checks whether the above mentioned validation conditions have been met. If they have then the robot is considered to be localised and the method terminates at step 485. If one or both validation conditions are not met, then at step 490 the method checks whether the maximum number of place candidates ‘n’ for the prior has been reached. If so, then no further searching is performed and the algorithm terminates at step 496 deeming that it is not possible to find the location. Otherwise, the size of the prior is increased at step 495 and the submap is extended by considering further place candidates and the method returns to step 435.”, [0197], “the recognition was performed using the classical approach first (i.e. localisation in a map as a single cloud), the result of it was treated as a ground truth. If the combined pipeline found a place of the same coordinates (with permissible error of the norm <1 m) the place was considered correct.”).
Claim 9
Cop discloses the method of claim 1 (Cop, [0111], “a method for use in performing localisation in a three - dimensional ( 3D ) environment will now be described with reference to FIG . 1”), wherein the calculating of the submap similarity score (Cop, [0141], “It is to be appreciated that submap geometrical descriptors are calculated along with the second intensity descriptors for the map after the 3D environment is mapped and stored in the data store. The geometrical descriptors are calculated for each portion extracted from the map and therefore when portions of the map are merged into a submap, the corresponding geometrical descriptors are retrieved for use in performing the geometrical recognition.”, [171], “Each submap geometrical descriptor is queried against each local geometrical descriptor obtained from the local scan”, [0037], “for each comparison between the first intensity descriptor and a second intensity descriptor: [0039] i) determining a plurality of relative orientations of the second intensity descriptor; and, [0040] ii) comparing the first intensity descriptor segments with the second intensity descriptor segments for each of the plurality of relative orientations of the second intensity descriptor; [0041] b) determining a similarity value for each orientation;” ) comprises:
calculating a first difference value between the histogram value of each query submap image and histogram values representing the geometric features of the submap images stored in the database (Cop, [0006], “The usage of global descriptors (that compute single statistics for the whole local scan based on geometrical information) is known to describe places by a histogram of points elevation”, [0047], “retrieving previously calculated submap geometrical descriptors calculated using submap keypoints associated with the portions of the map that are included in the submap”);
calculating a second difference value between the reflection symmetry score of each query submap image and reflection symmetry scores representing structural features of the submap images stored in the database (Cop, [0114], “The local scan performed by the laser sensor consists of a local point cloud of the robot's surroundings. The local point cloud consists of spatial information from which the structure of the environment is determined. In addition to range information, the laser sensor can also provide a measure of intensity for each point, which is the strength of return after reflection from a surface. More precisely, intensity refers to the ratio of power that was emitted by the laser and the power that returned to it. Whilst the term intensity is used generally throughout this disclosure, it should be understood that related parameters such as reflectivity should also be considered to fall within the scope of the term intensity. Reflectivity is a property of a surface obtained from intensity by compensating for intrinsic parameters of the sensor as well as extrinsic features such as distance to the object, incidence angle, air density etc.”, [0018], “calculating the first intensity descriptor based on at least one statistical measure for a distribution of the intensity data in the local point cloud”); and
calculating the submap similarity score, based on the first and second difference values (Cop, [0141], “It is to be appreciated that submap geometrical descriptors are calculated along with the second intensity descriptors for the map after the 3D environment is mapped and stored in the data store. The geometrical descriptors are calculated for each portion extracted from the map and therefore when portions of the map are merged into a submap, the corresponding geometrical descriptors are retrieved for use in performing the geometrical recognition.”, [171], “Each submap geometrical descriptor is queried against each local geometrical descriptor obtained from the local scan”, [0037], “for each comparison between the first intensity descriptor and a second intensity descriptor: [0039] i) determining a plurality of relative orientations of the second intensity descriptor; and, [0040] ii) comparing the first intensity descriptor segments with the second intensity descriptor segments for each of the plurality of relative orientations of the second intensity descriptor; [0041] b) determining a similarity value for each orientation;” ).
Claim 11
Cop discloses a computing device for global localization of a mobile robot (Cop, [0158], “the electronic processing device 210 may be formed from any suitable processing system, such as a suitably programmed computer system, PC, lap-top, or hand-held PC such as a smartphone, tablet or the like which is mounted on-board the robot 205”), the computing device comprising:
an image divider configured to divide (Cop, [0119], “It is therefore important to recognise that the method relies upon an existing map (i.e. global point cloud) of the 3D environment that has previously been determined in a mapping exercise using the laser sensor, for example in a SLAM based mapping of the environment.”) an occupancy grid map image into a plurality of query submap images (Cop, [0119], “After mapping, the map is segmented into a plurality of portions, each having a respective point cloud and second intensity descriptors are determined for each portion or segment of the map.”, [0044], “generating a submap using at least one portion of the map selected based on the ranking of portions of the map as potential locations”);
a feature extractor configured to calculate a histogram value representing a geometric feature of each query submap image (Cop, [0006], “The usage of global descriptors (that compute single statistics for the whole local scan based on geometrical information) is known to describe places by a histogram of points elevation”, [0047], “retrieving previously calculated submap geometrical descriptors calculated using submap keypoints associated with the portions of the map that are included in the submap”) and calculate a reflection symmetry score representing a symmetry feature of each query submap image (Cop, [0114], “The local scan performed by the laser sensor consists of a local point cloud of the robot's surroundings. The local point cloud consists of spatial information from which the structure of the environment is determined. In addition to range information, the laser sensor can also provide a measure of intensity for each point, which is the strength of return after reflection from a surface. More precisely, intensity refers to the ratio of power that was emitted by the laser and the power that returned to it. Whilst the term intensity is used generally throughout this disclosure, it should be understood that related parameters such as reflectivity should also be considered to fall within the scope of the term intensity. Reflectivity is a property of a surface obtained from intensity by compensating for intrinsic parameters of the sensor as well as extrinsic features such as distance to the object, incidence angle, air density etc.”, [0018], “calculating the first intensity descriptor based on at least one statistical measure for a distribution of the intensity data in the local point cloud”);
a submap similarity score calculator configured to calculate a submap similarity score between each query submap image and submap images stored in a database (Cop, [0141], “It is to be appreciated that submap geometrical descriptors are calculated along with the second intensity descriptors for the map after the 3D environment is mapped and stored in the data store. The geometrical descriptors are calculated for each portion extracted from the map and therefore when portions of the map are merged into a submap, the corresponding geometrical descriptors are retrieved for use in performing the geometrical recognition.”, [171], “Each submap geometrical descriptor is queried against each local geometrical descriptor obtained from the local scan”, [0037], “for each comparison between the first intensity descriptor and a second intensity descriptor: [0039] i) determining a plurality of relative orientations of the second intensity descriptor; and, [0040] ii) comparing the first intensity descriptor segments with the second intensity descriptor segments for each of the plurality of relative orientations of the second intensity descriptor; [0041] b) determining a similarity value for each orientation;” ), based on the histogram value (Cop, [0006], “The usage of global descriptors (that compute single statistics for the whole local scan based on geometrical information) is known to describe places by a histogram of points elevation”) and the reflection symmetry score (Cop, [0114], “intensity refers to the ratio of power that was emitted by the laser and the power that returned to it. Whilst the term intensity is used generally throughout this disclosure, it should be understood that related parameters such as reflectivity should also be considered to fall within the scope of the term intensity.”); and
a global localization processor configured to determine a submap image which is the most similar to the query submap image, based on the submap similarity score (Cop, [0174], “At step 455, the correspondences are clustered based on geometrical consistency. The result of the correspondence search step is a set of matchings between points in the submap and those in the local scan. To ensure that found correspondences belong to the actual instances of the local scan, geometric constraint is imposed on them.”, [0177], “At step 470, the candidate cluster having the highest number of correspondences is selected as the most likely location candidate”), and perform the global localization of the mobile robot, based on coordinate information included in the determined submap image (Cop, Fig. 4C, [0181], “method checks whether the above mentioned validation conditions have been met. If they have then the robot is considered to be localised and the method terminates at step 485. If one or both validation conditions are not met, then at step 490 the method checks whether the maximum number of place candidates ‘n’ for the prior has been reached. If so, then no further searching is performed and the algorithm terminates at step 496 deeming that it is not possible to find the location. Otherwise, the size of the prior is increased at step 495 and the submap is extended by considering further place candidates and the method returns to step 435.”, [0197], “the recognition was performed using the classical approach first (i.e. localisation in a map as a single cloud), the result of it was treated as a ground truth. If the combined pipeline found a place of the same coordinates (with permissible error of the norm <1 m) the place was considered correct.”).
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
Claims 2, 4-5, 10, 12-15, and 17-18 are rejected under 35 U.S.C. 103 as being unpatentable over Cop in view of Millane et al., "Free-Space Features: Global Localization in 2D Laser SLAM Using Distance Function Maps" (2019), hereinafter referred to as Millane.
Claim 2
Cop discloses the method of claim 1 (Cop, [0111], “a method for use in performing localisation in a three - dimensional ( 3D ) environment will now be described with reference to FIG . 1”), wherein the dividing of the global map image into the plurality of query submap images (Cop, [0119], “It is therefore important to recognise that the method relies upon an existing map (i.e. global point cloud) of the 3D environment that has previously been determined in a mapping exercise using the laser sensor, for example in a SLAM based mapping of the environment.”) comprises:
generating the global map image by using a sensor equipped in the mobile robot (Cop, [0115], “It is therefore important to recognise that the method relies upon an existing map (i.e. global point cloud) of the 3D environment that has previously been determined in a mapping exercise using the laser sensor, for example in a SLAM based mapping of the environment.”).
Cop does not explicitly disclose extracting a junction point, defining a point from which a movement path of the mobile robot branches, from the global map image and dividing the global map image into the plurality of query submap images having a certain radius with respect to the junction point.
However, Millane teaches extracting a junction point, defining a point from which a movement path of the mobile robot branches, from the global map image (Millane, Section IV, “Input submaps from the SLAM front-end are initially parameterized as occupancy probability grids, a function mapping from observed space (discretized into voxels), Ω ⊂ Z2, to a probability of occupancy, and unknown space to an sentinel value.”, Section IV.C, “We first extract a circular window of SDF values around a selected keypoint and compute gradient orientations and magnitudes in this window”, selected keypoint is analogous to the junction point) and dividing the global map image into the plurality of query submap images having a certain radius with respect to the junction point (Millane, Table 1 , the parameter for the grid search has the radius of 0.8 m).
Cop and Millane are both considered to be analogous to the claimed invention because they are in the same field of global localization. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified the method as taught by Cop to incorporate the teachings of Millane of extracting a junction point, defining a point from which a movement path of the mobile robot branches, from the global map image and dividing the global map image into the plurality of query submap images having a certain radius with respect to the junction point. Such a modification is the result of combining prior art elements according to known methods to yield predictable results. The motivation for the proposed modification would have been to for optimal performance on a localization experiment (Millane, Table 1).
Claim 4
Cop discloses the method of claim 1 (Cop, [0111], “a method for use in performing localisation in a three - dimensional ( 3D ) environment will now be described with reference to FIG . 1”), wherein the calculating of the histogram value representing the geometric feature of each query submap image (Cop, [0006], “The usage of global descriptors (that compute single statistics for the whole local scan based on geometrical information) is known to describe places by a histogram of points elevation”, [0047], “retrieving previously calculated submap geometrical descriptors calculated using submap keypoints associated with the portions of the map that are included in the submap”).
Cop does not explicitly disclose calculating a boundary histogram value representing a geometric feature of a boundary region, where the mobile robot is incapable of moving, in each query submap image and calculating a free space histogram value representing a geometric feature of a free space region, where the mobile robot is capable of moving, in each query submap image.
However, Millane teaches calculating a boundary histogram value representing a geometric feature of a boundary region, where the mobile robot is incapable of moving, in each query submap image (Millane, Abstract, “the system relies on the use of the distance function for representation of geometry. This representation allows extraction of features which describe the geometry of both surfaces and free-space”, Section IV.C, “we construct a descriptor based partially on a histogram of gradient orientations. We first extract a circular window of SDF values around a selected keypoint and compute gradient orientations and magnitudes in this window,”, Section VI, “At its core the system uses distance function representations of submaps, which allows extraction of novel features which describe the geometry of both occupied and non-occupied space. In particular, we use a DoH-based detector to find points of high curvature on the SDF. Keypoints are described using a gradient his togram, augmented with the feature distance, as well as the stationary point class”, occupied space is analogous to boundary) and calculating a free space histogram value representing a geometric feature of a free space region, where the mobile robot is capable of moving, in each query submap image (Millane, Abstract, “the system relies on the use of the distance function for representation of geometry. This representation allows extraction of features which describe the geometry of both surfaces and free-space”, Section IV.C, “we construct a descriptor based partially on a histogram of gradient orientations. We first extract a circular window of SDF values around a selected keypoint and compute gradient orientations and magnitudes in this window,”, Section VI, “At its core the system uses distance function representations of submaps, which allows extraction of novel features which describe the geometry of both occupied and non-occupied space. In particular, we use a DoH-based detector to find points of high curvature on the SDF. Keypoints are described using a gradient his togram, augmented with the feature distance, as well as the stationary point class”, non-occupied space is analogous to free-space).
Cop and Millane are both considered to be analogous to the claimed invention because they are in the same field of global localization. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified the method as taught by Cop to incorporate the teachings of Millane of calculating a boundary histogram value representing a geometric feature of a boundary region, where the mobile robot is incapable of moving, in each query submap image and calculating a free space histogram value representing a geometric feature of a free space region, where the mobile robot is capable of moving, in each query submap image. Such a modification is the result of combining prior art elements according to known methods to yield predictable results. The motivation for the proposed modification would have because the use of free-space improves localization performance when compared with using the proposed feature in the proximity of occupied space only (Millane, Section VI).
Claim 5
The combination of Cop in view of Millane discloses the method of claim 4 (Cop, [0111], “a method for use in performing localisation in a three - dimensional ( 3D ) environment will now be described with reference to FIG . 1”), wherein the calculating of the boundary histogram value (Millane, Abstract, “the system relies on the use of the distance function for representation of geometry. This representation allows extraction of features which describe the geometry of both surfaces and free-space”, Section IV.C, “we construct a descriptor based partially on a histogram of gradient orientations. We first extract a circular window of SDF values around a selected keypoint and compute gradient orientations and magnitudes in this window,”, Section VI, “At its core the system uses distance function representations of submaps, which allows extraction of novel features which describe the geometry of both occupied and non-occupied space. In particular, we use a DoH-based detector to find points of high curvature on the SDF. Keypoints are described using a gradient his togram, augmented with the feature distance, as well as the stationary point class”, occupied space is analogous to boundary) comprises:
transforming each query submap image into an edge map image, based on an image processing technique (Millane, Section IV.A, “We generate an SDF by thresholding the probability to produce a binary-valued grid, and then by taking the distance transform”);
sampling boundary points configuring the boundary region in the edge map image (Millane, Section IV.C, “Maximums are extracted in areas between obstacles, minimums on surface boundaries and saddles on geometric restrictions (areas where distance from obstacles grows in one direction but reduces in the other”, Section III, “Central to our approach is the use of the SDF, which we denote as the function f : R2 → d, where d ∈ R is the signed distance to the nearest surface. As is common in recent reconstruction systems, we store f as a collection of samples over a discrete uniformly-spaced voxel grid.”);
pairing the sampled boundary points to generate a plurality of boundary point pairs (Millane, Section IV.B, “classify points as either maxima, minima or saddles based on their signs. This classification becomes part of their description”, maxima and minima boundary points are a pair); and
calculating the boundary histogram value, based on a distance value between two boundary points included in each boundary point pair (Millane, Section C, “we construct a descriptor based partially on a histogram of gradient orientations.”, Section IV.C, “.Note that in contrast to image features, where pixels values within the descriptor support are subject to substantial changes between observations (for example, due to lighting changes), the distance produced by f are metrically scaled. To further restrict matches, we require matched features to have the same classification (see Sec. IV-B), as these keypoints represent areas in the environment with distinct topology. Maximums are extracted in areas between obstacles, minimums on surface boundaries and saddles on geometric restrictions (areas where distance from obstacles grows in one direction but reduces in the other).”).
Claim 10
Cop discloses the method of claim 1 (Cop, [0111], “a method for use in performing localisation in a three - dimensional ( 3D ) environment will now be described with reference to FIG . 1”).
Cop does not explicitly disclose wherein the calculating of the first difference value comprises: calculating a difference value between a boundary histogram value, representing the geometric feature of a boundary region where the mobile robot is incapable of moving in each query submap image, and boundary histogram values representing the geometric feature of a boundary region where the mobile robot is incapable of moving in the submap images; and calculating a difference value between a free space histogram value, representing the geometric feature of a free space region where the mobile robot is capable of moving in each query submap image, and free space histogram values representing the geometric feature of a free space region where the mobile robot is capable of moving.
However, Millane teaches wherein the calculating of the first difference value (Cop, [0006], “The usage of global descriptors (that compute single statistics for the whole local scan based on geometrical information) is known to describe places by a histogram of points elevation”, [0047], “retrieving previously calculated submap geometrical descriptors calculated using submap keypoints associated with the portions of the map that are included in the submap”) comprises: calculating a difference value (Millane, Section C, “we construct a descriptor based partially on a histogram of gradient orientations.”, Section IV.C, “.Note that in contrast to image features, where pixels values within the descriptor support are subject to substantial changes between observations (for example, due to lighting changes), the distance produced by f are metrically scaled. To further restrict matches, we require matched features to have the same classification (see Sec. IV-B), as these keypoints represent areas in the environment with distinct topology. Maximums are extracted in areas between obstacles, minimums on surface boundaries and saddles on geometric restrictions (areas where distance from obstacles grows in one direction but reduces in the other).”) between a boundary histogram value, representing the geometric feature of a boundary region where the mobile robot is incapable of moving in each query submap image, and boundary histogram values representing the geometric feature of a boundary region where the mobile robot is incapable of moving in the submap images (Millane, Abstract, “the system relies on the use of the distance function for representation of geometry. This representation allows extraction of features which describe the geometry of both surfaces and free-space”, Section IV.C, “we construct a descriptor based partially on a histogram of gradient orientations. We first extract a circular window of SDF values around a selected keypoint and compute gradient orientations and magnitudes in this window,”, Section VI, “At its core the system uses distance function representations of submaps, which allows extraction of novel features which describe the geometry of both occupied and non-occupied space. In particular, we use a DoH-based detector to find points of high curvature on the SDF. Keypoints are described using a gradient his togram, augmented with the feature distance, as well as the stationary point class”, occupied space is analogous to boundary); and calculating a difference value (Millane, Section C, “we construct a descriptor based partially on a histogram of gradient orientations.”, Section IV.C, “.Note that in contrast to image features, where pixels values within the descriptor support are subject to substantial changes between observations (for example, due to lighting changes), the distance produced by f are metrically scaled. To further restrict matches, we require matched features to have the same classification (see Sec. IV-B), as these keypoints represent areas in the environment with distinct topology. Maximums are extracted in areas between obstacles, minimums on surface boundaries and saddles on geometric restrictions (areas where distance from obstacles grows in one direction but reduces in the other).”) between a free space histogram value, representing the geometric feature of a free space region where the mobile robot is capable of moving in each query submap image, and free space histogram values representing the geometric feature of a free space region where the mobile robot is capable of moving (Millane, Abstract, “the system relies on the use of the distance function for representation of geometry. This representation allows extraction of features which describe the geometry of both surfaces and free-space”, Section IV.C, “we construct a descriptor based partially on a histogram of gradient orientations. We first extract a circular window of SDF values around a selected keypoint and compute gradient orientations and magnitudes in this window,”, Section VI, “At its core the system uses distance function representations of submaps, which allows extraction of novel features which describe the geometry of both occupied and non-occupied space. In particular, we use a DoH-based detector to find points of high curvature on the SDF. Keypoints are described using a gradient his togram, augmented with the feature distance, as well as the stationary point class”, non-occupied space is analogous to free-space).
Cop and Millane are both considered to be analogous to the claimed invention because they are in the same field of global localization. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified the method as taught by Cop to incorporate the teachings of Millane wherein the calculating of the first difference value comprises: calculating a difference value between a boundary histogram value, representing the geometric feature of a boundary region where the mobile robot is incapable of moving in each query submap image, and boundary histogram values representing the geometric feature of a boundary region where the mobile robot is incapable of moving in the submap images; and calculating a difference value between a free space histogram value, representing the geometric feature of a free space region where the mobile robot is capable of moving in each query submap image, and free space histogram values representing the geometric feature of a free space region where the mobile robot is capable of moving. Such a modification is the result of combining prior art elements according to known methods to yield predictable results. The motivation for the proposed modification would have because the use of free-space improves localization performance when compared with using the proposed feature in the proximity of occupied space only (Millane, Section VI).
Claim 12
Cop discloses a computing device of claim 11 (Cop, [0158], “the electronic processing device 210 may be formed from any suitable processing system, such as a suitably programmed computer system, PC, lap-top, or hand-held PC such as a smartphone, tablet or the like which is mounted on-board the robot 205”), wherein the image divider divides the occupancy grid map image into a plurality of query submap images (Cop, [0119], “It is therefore important to recognise that the method relies upon an existing map (i.e. global point cloud) of the 3D environment that has previously been determined in a mapping exercise using the laser sensor, for example in a SLAM based mapping of the environment.”).
Cop does not explicitly disclose the image divider divides the occupancy grid map image into a plurality of query submap images with respect to a junction point from which a movement path of the mobile robot branches, in the occupancy grid map image.
However, Millane teaches the image divider divides the occupancy grid map image into a plurality of query submap images with respect to a junction point from which a movement path of the mobile robot branches, in the occupancy grid map image (Millane, Section IV, “Input submaps from the SLAM front-end are initially parameterized as occupancy probability grids, a function mapping from observed space (discretized into voxels), Ω ⊂ Z2, to a probability of occupancy, and unknown space to an sentinel value.”, Section IV.C, “We first extract a circular window of SDF values around a selected keypoint and compute gradient orientations and magnitudes in this window”, selected keypoint is analogous to the junction point).
Cop and Millane are both considered to be analogous to the claimed invention because they are in the same field of global localization. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified the computing device as taught by Cop to incorporate the teachings of Millane of the image divider divides the occupancy grid map image into a plurality of query submap images with respect to a junction point from which a movement path of the mobile robot branches, in the occupancy grid map image. Such a modification is the result of combining prior art elements according to known methods to yield predictable results. The motivation for the proposed modification would have been to for optimal performance on a localization experiment (Millane, Table 1).
Claim 13
Cop discloses a computing device of claim 11 (Cop, [0158], “the electronic processing device 210 may be formed from any suitable processing system, such as a suitably programmed computer system, PC, lap-top, or hand-held PC such as a smartphone, tablet or the like which is mounted on-board the robot 205”), wherein the feature extractor comprises: a structural feature extractor configured to calculate a reflection symmetry score obtained by quantifying symmetricity of each query submap image (Cop, [0114], “The local scan performed by the laser sensor consists of a local point cloud of the robot's surroundings. The local point cloud consists of spatial information from which the structure of the environment is determined. In addition to range information, the laser sensor can also provide a measure of intensity for each point, which is the strength of return after reflection from a surface. More precisely, intensity refers to the ratio of power that was emitted by the laser and the power that returned to it. Whilst the term intensity is used generally throughout this disclosure, it should be understood that related parameters such as reflectivity should also be considered to fall within the scope of the term intensity. Reflectivity is a property of a surface obtained from intensity by compensating for intrinsic parameters of the sensor as well as extrinsic features such as distance to the object, incidence angle, air density etc.”, [0018], “calculating the first intensity descriptor based on at least one statistical measure for a distribution of the intensity data in the local point cloud”).
Cop does not explicitly disclose a first geometric feature extractor configured to calculate a boundary histogram value obtained by quantifying distribution features of a boundary region where the mobile robot is incapable of moving, in each query submap image and a second geometric feature extractor configured to calculate a free space histogram value obtained by quantifying distribution features of a free space region where the mobile robot is capable of moving, in each query submap image.
However, Millane teaches a first geometric feature extractor configured to calculate a boundary histogram value obtained by quantifying distribution features of a boundary region where the mobile robot is incapable of moving, in each query submap image (Millane, Abstract, “the system relies on the use of the distance function for representation of geometry. This representation allows extraction of features which describe the geometry of both surfaces and free-space”, Section IV.C, “we construct a descriptor based partially on a histogram of gradient orientations. We first extract a circular window of SDF values around a selected keypoint and compute gradient orientations and magnitudes in this window,”, Section VI, “At its core the system uses distance function representations of submaps, which allows extraction of novel features which describe the geometry of both occupied and non-occupied space. In particular, we use a DoH-based detector to find points of high curvature on the SDF. Keypoints are described using a gradient his togram, augmented with the feature distance, as well as the stationary point class”, occupied space is analogous to boundary) and a second geometric feature extractor configured to calculate a free space histogram value obtained by quantifying distribution features of a free space region where the mobile robot is capable of moving, in each query submap image (Millane, Abstract, “the system relies on the use of the distance function for representation of geometry. This representation allows extraction of features which describe the geometry of both surfaces and free-space”, Section IV.C, “we construct a descriptor based partially on a histogram of gradient orientations. We first extract a circular window of SDF values around a selected keypoint and compute gradient orientations and magnitudes in this window,”, Section VI, “At its core the system uses distance function representations of submaps, which allows extraction of novel features which describe the geometry of both occupied and non-occupied space. In particular, we use a DoH-based detector to find points of high curvature on the SDF. Keypoints are described using a gradient his togram, augmented with the feature distance, as well as the stationary point class”, non-occupied space is analogous to free-space).
Cop and Millane are both considered to be analogous to the claimed invention because they are in the same field of global localization. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified the computing device as taught by Cop to incorporate the teachings of Millane of a first geometric feature extractor configured to calculate a boundary histogram value obtained by quantifying distribution features of a boundary region where the mobile robot is incapable of moving, in each query submap image and a second geometric feature extractor configured to calculate a free space histogram value obtained by quantifying distribution features of a free space region where the mobile robot is capable of moving, in each query submap image. Such a modification is the result of combining prior art elements according to known methods to yield predictable results. The motivation for the proposed modification would have because the use of free-space improves localization performance when compared with using the proposed feature in the proximity of occupied space only (Millane, Section VI).
Claim 14
Cop discloses a computing device of claim 11 (Cop, [0158], “the electronic processing device 210 may be formed from any suitable processing system, such as a suitably programmed computer system, PC, lap-top, or hand-held PC such as a smartphone, tablet or the like which is mounted on-board the robot 205”), wherein the submap similarity score calculator (Cop, [0141], “It is to be appreciated that submap geometrical descriptors are calculated along with the second intensity descriptors for the map after the 3D environment is mapped and stored in the data store. The geometrical descriptors are calculated for each portion extracted from the map and therefore when portions of the map are merged into a submap, the corresponding geometrical descriptors are retrieved for use in performing the geometrical recognition.”, [171], “Each submap geometrical descriptor is queried against each local geometrical descriptor obtained from the local scan”, [0037], “for each comparison between the first intensity descriptor and a second intensity descriptor: [0039] i) determining a plurality of relative orientations of the second intensity descriptor; and, [0040] ii) comparing the first intensity descriptor segments with the second intensity descriptor segments for each of the plurality of relative orientations of the second intensity descriptor; [0041] b) determining a similarity value for each orientation;” ) comprises: a third subtractor configured to calculate a difference value between the reflection symmetry score obtained by quantifying symmetricity of each query submap image and a reflection symmetry score obtained by quantifying symmetricity of the submap image stored in the database (Cop, [0114], “The local scan performed by the laser sensor consists of a local point cloud of the robot's surroundings. The local point cloud consists of spatial information from which the structure of the environment is determined. In addition to range information, the laser sensor can also provide a measure of intensity for each point, which is the strength of return after reflection from a surface. More precisely, intensity refers to the ratio of power that was emitted by the laser and the power that returned to it. Whilst the term intensity is used generally throughout this disclosure, it should be understood that related parameters such as reflectivity should also be considered to fall within the scope of the term intensity. Reflectivity is a property of a surface obtained from intensity by compensating for intrinsic parameters of the sensor as well as extrinsic features such as distance to the object, incidence angle, air density etc.”, [0018], “calculating the first intensity descriptor based on at least one statistical measure for a distribution of the intensity data in the local point cloud”).
Cop does not explicitly disclose a first subtractor configured to calculate a difference value between a boundary histogram value obtained by quantifying geometric features of a boundary region in each query submap image and a boundary histogram value obtained by quantifying geometric features of a boundary region in a submap image stored in the database and a second subtractor configured to calculate a difference value between a free space histogram value obtained by quantifying geometric features of a free space region in each query submap image and a boundary histogram value obtained by quantifying geometric features of a free space region of the submap image stored in the database.
However, Millane teaches a first subtractor configured to calculate a difference value (Millane, Section C, “we construct a descriptor based partially on a histogram of gradient orientations.”, Section IV.C, “.Note that in contrast to image features, where pixels values within the descriptor support are subject to substantial changes between observations (for example, due to lighting changes), the distance produced by f are metrically scaled. To further restrict matches, we require matched features to have the same classification (see Sec. IV-B), as these keypoints represent areas in the environment with distinct topology. Maximums are extracted in areas between obstacles, minimums on surface boundaries and saddles on geometric restrictions (areas where distance from obstacles grows in one direction but reduces in the other).”) between a boundary histogram value obtained by quantifying geometric features of a boundary region in each query submap image and a boundary histogram value obtained by quantifying geometric features of a boundary region in a submap image stored in the database (Millane, Abstract, “the system relies on the use of the distance function for representation of geometry. This representation allows extraction of features which describe the geometry of both surfaces and free-space”, Section IV.C, “we construct a descriptor based partially on a histogram of gradient orientations. We first extract a circular window of SDF values around a selected keypoint and compute gradient orientations and magnitudes in this window,”, Section VI, “At its core the system uses distance function representations of submaps, which allows extraction of novel features which describe the geometry of both occupied and non-occupied space. In particular, we use a DoH-based detector to find points of high curvature on the SDF. Keypoints are described using a gradient his togram, augmented with the feature distance, as well as the stationary point class”, occupied space is analogous to boundary) and a second subtractor configured to calculate a difference value (Millane, Section C, “we construct a descriptor based partially on a histogram of gradient orientations.”, Section IV.C, “.Note that in contrast to image features, where pixels values within the descriptor support are subject to substantial changes between observations (for example, due to lighting changes), the distance produced by f are metrically scaled. To further restrict matches, we require matched features to have the same classification (see Sec. IV-B), as these keypoints represent areas in the environment with distinct topology. Maximums are extracted in areas between obstacles, minimums on surface boundaries and saddles on geometric restrictions (areas where distance from obstacles grows in one direction but reduces in the other).”) between a free space histogram value obtained by quantifying geometric features of a free space region in each query submap image and a boundary histogram value obtained by quantifying geometric features of a free space region of the submap image stored in the database (Millane, Abstract, “the system relies on the use of the distance function for representation of geometry. This representation allows extraction of features which describe the geometry of both surfaces and free-space”, Section IV.C, “we construct a descriptor based partially on a histogram of gradient orientations. We first extract a circular window of SDF values around a selected keypoint and compute gradient orientations and magnitudes in this window,”, Section VI, “At its core the system uses distance function representations of submaps, which allows extraction of novel features which describe the geometry of both occupied and non-occupied space. In particular, we use a DoH-based detector to find points of high curvature on the SDF. Keypoints are described using a gradient histogram, augmented with the feature distance, as well as the stationary point class”, non-occupied space is analogous to free-space).
Cop and Millane are both considered to be analogous to the claimed invention because they are in the same field of global localization. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified the computing device as taught by Cop to incorporate the teachings of Millane of a first subtractor configured to calculate a difference value between a boundary histogram value obtained by quantifying geometric features of a boundary region in each query submap image and a boundary histogram value obtained by quantifying geometric features of a boundary region in a submap image stored in the database and a second subtractor configured to calculate a difference value between a free space histogram value obtained by quantifying geometric features of a free space region in each query submap image and a boundary histogram value obtained by quantifying geometric features of a free space region of the submap image stored in the database. Such a modification is the result of combining prior art elements according to known methods to yield predictable results. The motivation for the proposed modification would have because the use of free-space improves localization performance when compared with using the proposed feature in the proximity of occupied space only (Millane, Section VI).
Claim 15
The combination of Cop in view of Millane discloses a computing device of claim 14 (Cop, [0158], “the electronic processing device 210 may be formed from any suitable processing system, such as a suitably programmed computer system, PC, lap-top, or hand-held PC such as a smartphone, tablet or the like which is mounted on-board the robot 205”), wherein the submap similarity score calculator (Cop, [0141], “It is to be appreciated that submap geometrical descriptors are calculated along with the second intensity descriptors for the map after the 3D environment is mapped and stored in the data store. The geometrical descriptors are calculated for each portion extracted from the map and therefore when portions of the map are merged into a submap, the corresponding geometrical descriptors are retrieved for use in performing the geometrical recognition.”, [171], “Each submap geometrical descriptor is queried against each local geometrical descriptor obtained from the local scan”, [0037], “for each comparison between the first intensity descriptor and a second intensity descriptor: [0039] i) determining a plurality of relative orientations of the second intensity descriptor; and, [0040] ii) comparing the first intensity descriptor segments with the second intensity descriptor segments for each of the plurality of relative orientations of the second intensity descriptor; [0041] b) determining a similarity value for each orientation;” ) performs an arithmetic operation on the difference values calculated by the first to third subtractors to calculate a similarity score between each query submap image and the submap images (Cop, [0166], “At step 430, the first intensity descriptor is compared against the second intensity descriptors. This is achieved by comparing histograms of intensity for each segment of the first intensity descriptor with the histogram of intensity of each corresponding segment of a second intensity descriptor.”, the equation used to compare the intensity descriptors uses arithmetic function, [0171],m “geometrical correspondences are determined. Each submap geometrical descriptor is queried against each local geometrical descriptor obtained from the local scan.”, [0174], “he correspondences are clustered based on geometrical consistency. The result of the correspondence search step is a set of matchings between points in the submap and those in the local scan. To ensure that found correspondences belong to the actual instances of the local scan, geometric constraint is imposed on them. The basic assumption is that the points in the clouds are rigidly coupled. This allows the keypoints to be clustered into sets that fulfil the geometric consistency criterion. By this condition two points in the submap are considered geometrically consistent if the difference between 2-norm of their subtraction and 2-norm of subtraction of corresponding points in the local scan is smaller than a defined consensus threshold.”).
Claim 17
Cop discloses a method for global localization of a mobile robot (Cop, [0111], “a method for use in performing localisation in a three - dimensional ( 3D ) environment will now be described with reference to FIG . 1”), performed by a processor of a computing device (Cop, [0157], “, the microprocessor 300 executes instructions in the form of applications software stored in the memory 301 to allow the required processes to be per formed”) equipped in the mobile robot (Cop, [0153], “Preferably , the at least one laser sensor , one or more electronic processing devices and data store are located on - board a mobile robot or autonomous vehicle”), the method comprising:
calculating a reflection symmetry score obtained by quantifying symmetricity of each query submap image with respect to an axis of symmetry extracted from each query submap image (Cop, [0114], “The local scan performed by the laser sensor consists of a local point cloud of the robot's surroundings. The local point cloud consists of spatial information from which the structure of the environment is determined. In addition to range information, the laser sensor can also provide a measure of intensity for each point, which is the strength of return after reflection from a surface. More precisely, intensity refers to the ratio of power that was emitted by the laser and the power that returned to it. Whilst the term intensity is used generally throughout this disclosure, it should be understood that related parameters such as reflectivity should also be considered to fall within the scope of the term intensity. Reflectivity is a property of a surface obtained from intensity by compensating for intrinsic parameters of the sensor as well as extrinsic features such as distance to the object, incidence angle, air density etc.”, [0018], “calculating the first intensity descriptor based on at least one statistical measure for a distribution of the intensity data in the local point cloud”);
comparing the reflection symmetry score of each query submap image with a reflection symmetry score of submap images input from a database to select a submap image, which is the most similar to each query submap image, from among submap images stored in the database (Cop, [0166], “At step 430, the first intensity descriptor is compared against the second intensity descriptors. This is achieved by comparing histograms of intensity for each segment of the first intensity descriptor with the histogram of intensity of each corresponding segment of a second intensity descriptor.”); and
performing the global localization of the mobile robot, based on coordinate information included in the selected submap image (Cop, Fig. 4C, [0181], “method checks whether the above mentioned validation conditions have been met. If they have then the robot is considered to be localised and the method terminates at step 485. If one or both validation conditions are not met, then at step 490 the method checks whether the maximum number of place candidates ‘n’ for the prior has been reached. If so, then no further searching is performed and the algorithm terminates at step 496 deeming that it is not possible to find the location. Otherwise, the size of the prior is increased at step 495 and the submap is extended by considering further place candidates and the method returns to step 435.”, [0197], “the recognition was performed using the classical approach first (i.e. localisation in a map as a single cloud), the result of it was treated as a ground truth. If the combined pipeline found a place of the same coordinates (with permissible error of the norm <1 m) the place was considered correct.”).
Cop does not explicitly disclose calculating a boundary histogram value obtained by quantifying distribution features of a boundary region where the mobile robot is incapable of moving, in each query submap image divided from a global map image, calculating a free space histogram value obtained by quantifying distribution features of a free space region where the mobile robot is capable of moving, in each query submap image, and comparing the boundary histogram value and the free space histogram value of each query submap image with a boundary histogram value and a free space histogram value of submap images input from a database to select a submap image, which is the most similar to each query submap image, from among submap images stored in the database.
However, Millane teaches calculating a boundary histogram value obtained by quantifying distribution features of a boundary region where the mobile robot is incapable of moving, in each query submap image divided from a global map image (Millane, Abstract, “the system relies on the use of the distance function for representation of geometry. This representation allows extraction of features which describe the geometry of both surfaces and free-space”, Section IV.C, “we construct a descriptor based partially on a histogram of gradient orientations. We first extract a circular window of SDF values around a selected keypoint and compute gradient orientations and magnitudes in this window,”, Section VI, “At its core the system uses distance function representations of submaps, which allows extraction of novel features which describe the geometry of both occupied and non-occupied space. In particular, we use a DoH-based detector to find points of high curvature on the SDF. Keypoints are described using a gradient his togram, augmented with the feature distance, as well as the stationary point class”, occupied space is analogous to boundary), calculating a free space histogram value obtained by quantifying distribution features of a free space region where the mobile robot is capable of moving, in each query submap image (Millane, Abstract, “the system relies on the use of the distance function for representation of geometry. This representation allows extraction of features which describe the geometry of both surfaces and free-space”, Section IV.C, “we construct a descriptor based partially on a histogram of gradient orientations. We first extract a circular window of SDF values around a selected keypoint and compute gradient orientations and magnitudes in this window,”, Section VI, “At its core the system uses distance function representations of submaps, which allows extraction of novel features which describe the geometry of both occupied and non-occupied space. In particular, we use a DoH-based detector to find points of high curvature on the SDF. Keypoints are described using a gradient histogram, augmented with the feature distance, as well as the stationary point class”, non-occupied space is analogous to free-space), and comparing the boundary histogram value and the free space histogram value of each query submap image with a boundary histogram value and a free space histogram value of submap images input from a database to select a submap image, which is the most similar to each query submap image, from among submap images stored in the database (Millane, Section IV.D, “In this work we consider place recognition as the pair wise matching problem- that is, given two submaps Si and Sj determine if they are matching. For each submap pair we determine feature correspondences using a nearest neighbour lookup, rejecting ambiguous matches using the ratio-test [25]. This test discards matches which have a nearby second neighbour. We use RANSAC to determine inlier correspondences as well as a SE transform relating the submaps. If the number of inliers exceeds a threshold, the pair are considered a match. Note that, in application, place-recognition systems use several techniques to avoid pairwise comparisons and speed up lookups, such as inverted files and descriptor clustering”).
Cop and Millane are both considered to be analogous to the claimed invention because they are in the same field of global localization. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified the method as taught by Cop to incorporate the teachings of Millane of calculating a boundary histogram value obtained by quantifying distribution features of a boundary region where the mobile robot is incapable of moving, in each query submap image divided from a global map image, calculating a free space histogram value obtained by quantifying distribution features of a free space region where the mobile robot is capable of moving, in each query submap image, and comparing the boundary histogram value and the free space histogram value of each query submap image with a boundary histogram value and a free space histogram value of submap images input from a database to select a submap image, which is the most similar to each query submap image, from among submap images stored in the database. Such a modification is the result of combining prior art elements according to known methods to yield predictable results. The motivation for the proposed modification would have because the use of free-space improves localization performance when compared with using the proposed feature in the proximity of occupied space only (Millane, Section VI).
Claim 18
The combination of Cop in view of Millane discloses the method of claim 17 (Cop, [0111], “a method for use in performing localisation in a three - dimensional ( 3D ) environment will now be described with reference to FIG . 1”), wherein the global map image is a 2D or 3D occupancy grid map image (Millane, Section IV.A, “Input submaps from the SLAM front-end are initially parameterized as occupancy probability grids, a function mapping from observed space (discretized into voxels), Ω ⊂ Z2, to a probability of occupancy, and unknown space to an sentinel value.”).
Cop and Millane are both considered to be analogous to the claimed invention because they are in the same field of global localization. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified the method as taught by Cop to incorporate the teachings of Millane wherein the global map image is a 2D or 3D occupancy grid map image. Such a modification is the result of combining prior art elements according to known methods to yield predictable results. The motivation for the proposed modification would have for increasing localization performance (Millane, Abstract).
Claim 3 is rejected under 35 U.S.C. 103 as being unpatentable over Cop in view of Millane in further view of Brand et al., "Submap Matching for Stereo-Vision Based Indoor/Outdoor SLAM" (2015), hereinafter referred to as Brand.
Claim 3
The combination of Cop in view of Millane discloses the method of claim 3 (Cop, [0111], “a method for use in performing localisation in a three - dimensional ( 3D ) environment will now be described with reference to FIG . 1”), wherein the extracting of the junction point (Millane, Section IV, “Input submaps from the SLAM front-end are initially parameterized as occupancy probability grids, a function mapping from observed space (discretized into voxels), Ω ⊂ Z2, to a probability of occupancy, and unknown space to an sentinel value.”, Section IV.C, “We first extract a circular window of SDF values around a selected keypoint and compute gradient orientations and magnitudes in this window”, selected keypoint is analogous to the junction point) comprises:
transforming the global map image into an edge map image, based on an image processing technique (Millane, Section IV.A, “We generate an SDF by thresholding the probability to produce a binary-valued grid, and then by taking the distance transform”).
The combination of Cop in view of Millane does not explicitly disclose when an nxn image patch including a center pixel of the edge map image and peripheral pixels surrounding the center pixel is assumed, extracting the center pixel as the junction point when a pixel value of the center pixel differs from pixel values of at least three peripheral pixels.
However, Brand teaches when an nxn image patch (Brand, Section IV.C, “we organize the submaps on a 2D grid with a resolution of 3m, each cell representing a histogram bin that contains the number of matches performed on submaps located in the respective cell.”, Section IV.B, “To finalize a submap, we apply a voxel-grid filter with a resolution of 3cm in order to reduce the impact of the radial distribution and the computational requirements for subsequent processing steps”, Millane teaches using thresholding to get an edge image) including a center pixel of the edge map image and peripheral pixels surrounding the center pixel is assumed (Brand, Section IV.B, “From the greyscale and depth images, we first compute 3D pointclouds. We only consider points within a maximum distance of 3.5m from the camera, because for larger distances the stereo error would exceed the map voxel density. Each new submap is anchored with its origin at the robot’s current pose, which is added as a node to the SLAM graph (see Section IV-D”, origin is center pixel), extracting the center pixel as the junction point when a pixel value of the center pixel differs from pixel values of at least three peripheral pixels (Brand, Section IV.B, “In order to limit the drift within the submaps while still providing a sufficient submap size for matching, we empirically determined system-dependent criteria to trigger submap creation. We start new submaps after a maximum driven distance of 2.5m or a maximum integrated rotation of 90◦, whichever criterion is met first.”, “To finalize a submap, we apply a voxel-grid filter with a resolution of 3cm in order to reduce the impact of the radial distribution and the computational requirements for subsequent processing steps”).
Cop, Millane, and Brand are all considered to be analogous to the claimed invention because they are in the same field of global localization. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified the method as taught by the combination of Cop in view of Millane to incorporate the teachings of Brand when an nxn image patch including a center pixel of the edge map image and peripheral pixels surrounding the center pixel is assumed, extracting the center pixel as the junction point when a pixel value of the center pixel differs from pixel values of at least three peripheral pixels. Such a modification is the result of combining prior art elements according to known methods to yield predictable results. The motivation for the proposed modification would have been to reduce the impact of the radial distribution and the computational requirements for subsequent processing steps (Brand, Section IV.B).
Claim 6 is rejected under 35 U.S.C. 103 as being unpatentable over Cop in view of Millane in further view of Lee et al., (US 2008/0273791 A1, 11/06/2008), hereinafter referred to as Lee.
Claim 6
The combination of Cop in view of Millane discloses the method of claim 4 (Cop, [0111], “a method for use in performing localisation in a three - dimensional ( 3D ) environment will now be described with reference to FIG . 1”), wherein the calculating of the free space histogram value comprises:
transforming each query submap image into an edge map image, based on an image processing technique (Millane, Section IV.A, “We generate an SDF by thresholding the probability to produce a binary-valued grid, and then by taking the distance transform”);
extracting free space points configuring the free space region in the edge map image (Section V.B, “We perform a similar analysis to the one described in Sec. V-A, however we limit the proposed method to extracting features near surface boundaries, to varying degrees. In particular, we perform several trails, removing features further than some distance d threshold from a surface boundary. We generate performance curves for settings of this threshold d threshold ∈ {2.0,1.5,1.0,0.5} meters. Figure 6 shows an example submap and the areas where extracted features will be kept in the submap’s description for each trial.”).
The combination of Cop in view of Millane does not explicitly disclose pairing two free space points having a shortest path distance value among the extracted free space points to generate a plurality of free space point pairs and calculating the free space histogram value, based on the shortest path distance value of each free space point pair.
However, Lee teaches pairing two free space points having a shortest path distance value among the extracted free space points to generate a plurality of free space point pairs (Lee, Abstract, “ extracting candidate pairs of feature points, which are in the range of a region division element, from the feature points; extracting a final pair of feature points, which satisfies the requirements of the region division element, from the candidate pair of feature points; forming a critical line by connecting the final pair of feature points”) and calculating the free space histogram value, based on the shortest path distance value of each free space point pair (Lee, [0008], “FIG. 1 is a view sequentially showing a method of drawing a topological map by detecting a narrow path with a Voronoi diagram. First, when the shortest distance between obstacles is obtained in all grids of a free space, a voronoi diagram is drawn by connecting center points of the shortest distances (FIG. 1B). Each point in the voronoi diagram has a value of the shortest distance from obstacles, in the case in which the shortest distance has a local-minimum, a point of the voronoi diagram, that is, a point of the voronoi diagram having a local-minimum, when an X-axis is defined along the voronoi diagram and the distance to an obstacle of each point is defined as a Y-axis, is determined as a critical point (FIG. 1C). Next, a critical line is drawn by connecting points shortest distant from each critical point (FIG. 1D). This critical line is a narrow path which is extracted by the voronoi diagram. Each region divided by the critical lines becomes a topological region (FIG. 1E).”).
Cop, Millane, and Lee are all considered to be analogous to the claimed invention because they are in the same field of global localization. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified the method as taught by the combination of Cop in view of Millane to incorporate the teachings of Lee of pairing two free space points having a shortest path distance value among the extracted free space points to generate a plurality of free space point pairs and calculating the free space histogram value, based on the shortest path distance value of each free space point pair. Such a modification is the result of combining prior art elements according to known methods to yield predictable results. The motivation for the proposed modification would have because to reduce the amount of calculations. (Lee, [0010]).
Allowable Subject Matter
Claims 7 and 8 are objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
The following is a statement of reasons for the indication of allowable subject matter: The claimed features such as “detecting axes of reflection symmetry in the edge map image, based on angles of line segments having a certain length, transforming the edge map image into a blurred image, based on an image blurred technique, and calculating, as the reflection symmetry score, a similarity score between the blurred image and a flipped blurred image flipped with respect to the detected axes of reflection symmetry” claimed in dependent claim 7, in combination with the remainder of the limitations of the claims, are neither anticipated nor obvious in view of the prior art of record.
In the closest prior art of record, Cop teaches calculating a reflection symmetry score in the form of the intensity descriptor.
However, Cop fails to teach detecting the reflection symmetry score based on the angles of line segments having a certain length and blurring the image before calculating the similarity score between the blurred image and a flipped blurred image with respect to the detected axes of reflection symmetry. Therefore claim 7 would be allowable for claiming the limitation “detecting axes of reflection symmetry in the edge map image, based on angles of line segments having a certain length, transforming the edge map image into a blurred image, based on an image blurred technique, and calculating, as the reflection symmetry score, a similarity score between the blurred image and a flipped blurred image flipped with respect to the detected axes of reflection symmetry” in combination with the remainder of the limitations of the claims, are neither anticipated nor obvious in view of the prior art of record..
Because the cited prior art of records does not teach or suggest each and every feature of dependent claim 7, this claim would be allowable. Claim 8 is objected by virtue of their dependency on dependent claim 7.
Claim 16 is objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
The following is a statement of reasons for the indication of allowable subject matter: The claimed features such as “wherein the submap similarity score calculator further comprises an adder configured to summate the difference value calculated by the first subtractor and the difference value calculated by the second subtractor, and the submap similarity score calculator performs an arithmetic operation on the difference value calculated by the third subtractor as a weight and a value summated by the adder to calculate a similarity score between each query submap image and the submap images” claimed in dependent claim 16, in combination with the remainder of the limitations of the claims, are neither anticipated nor obvious in view of the prior art of record.
In the closest prior art of record, Cop teaches calculating a reflection symmetry score in the form of the intensity descriptor and the histogram value representing a geometric feature of each query submap image. In another prior art of record, Millane teaches calculating both the boundary histogram and the free-space histogram.
However, Cop and Millane fails to teach adding the difference values of both the boundary histogram and free-space histogram and performing an arithmetic operation on the difference value calculated by the third subtractor as a weight and a value summated by adding the difference values of both the boundary histogram and free-space histogram to calculate a similarity score. Therefore claim 16 would be allowable for claiming the limitation “wherein the submap similarity score calculator further comprises an adder configured to summate the difference value calculated by the first subtractor and the difference value calculated by the second subtractor, and the submap similarity score calculator performs an arithmetic operation on the difference value calculated by the third subtractor as a weight and a value summated by the adder to calculate a similarity score between each query submap image and the submap images” in combination with the remainder of the limitations of the claims, are neither anticipated nor obvious in view of the prior art of record..
Because the cited prior art of records does not teach or suggest each and every feature of dependent claim 16, this claim would be allowable.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to DENISE G ALFONSO whose telephone number is (571)272-1360. The examiner can normally be reached Monday - Friday 7:30 - 5:30.
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 at (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 published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/DENISE G ALFONSO/Examiner, Art Unit 2662
/AMANDEEP SAINI/Supervisory Patent Examiner, Art Unit 2662
Prosecution Insights