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 .
Response to Amendments
This action is in response to amendments and remarks filed on 12/12/2025.
Claims 1-20 are pending. Claims are 1-3, 8-12, 14, 16-19 are amended. Applicant's amendment reverses the previous specification and claim objections. Though, Applicant's amendment necessitated new grounds of rejection rendering claims 1-20 rejected.
Response to Arguments
Applicant presents the following arguments regarding the previous office action:
Gawel fails to disclose determining a preprocessing initial position of the robot according to an associated node pair with a highest matching degree, the associated node pair with the highest matching degree being an associated node pair of the search branch with the highest matching degree; and based on the preprocessing initial position, performing point cloud matching on the associated node pair with the highest matching degree to determine the current pose of the robot.
Regarding the Applicant’s argument; the argument has been fully considered and is moot in light of new grounds for rejection below.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
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.
Claims 1-2, 9-10 and 17-18 are all rejected under 35 U.S.C. 103 as being unpatentable over Gawel et al. (X-View: Graph-Based Semantic Multi-View Localization) in view of Neira et al. (Data Association in Stochastic Mapping Using the Joint Compatibility Test), further in view of Liu et al. (Global Localization with Object-Level Semantics and Topology).
Regarding claim 1, Gawel discloses, a positioning method applied to a robot (Introduction, X-View introduces graph descriptors that efficiently represent unique topologies of semantic objects. These can be matched in much lower computational effort, therefore not suffering under the need for exhaustive sub-graph matching. By using semantics as an abstraction between robot viewpoints) comprising: obtaining a current local topology map (Introduction, this paper presents the following contributions: A novel graph representation for semantic topologies) … (X-VIEW, we convert a sequence of semantic images Iq into a query graph Gq) and a full topology map (Fig. 2, the inputs to the system are semantically segmented frames (e.g., from RGB images) and the global graph Gdb), wherein the current local topology map is established based on objects in an environment currently observed by the robot (X-VIEW, we convert a sequence of semantic images Iq into a query graph Gq. We extract blobs of connected regions), the full topology map is pre-established based on objects in a full environment in a preset area (II. X-VIEW, we also consider a database semantic graph Gdb, as it could have been built and described on a previous run of our graph building algorithm as presented in the next sub-sections), the current local topology map comprises nodes representing the objects in the environment currently observed by the robot (II. X-VIEW, using a depth channel or the depth estimation from, e.g., optical flow, the neighborhood can be formed in 3D-space, using the 3D locations of the image blobs to compute a Euclidean distance), and the full topology map comprises nodes representing the objects in the full environment (II. X-VIEW, we also consider a database semantic graph Gdb, as it could have been built and described on a previous run of our graph building algorithm as presented in the next sub-sections); matching the nodes in the current local topology map and the nodes in the full topology map, wherein the matching comprises determining a degree of association of at least one node pair to be associated, which is constructed by the nodes in the current local topology map (III. X-VIEW, after both Gq and Gdb are created, we find associations between vertices in the query graph and the ones in the database graph by computing a similarity score between the corresponding graph descriptors), and the nodes in the full topology map (Fig. 2, first, a local graph is extracted from the new segmentation. Then, the sub-graph Gq is assembled and random walk descriptors are computed on each node of Gq. The system matches the sub-graph random walk descriptors to Gdb, e.g., recorded from a different view-point. Finally, the matches are transferred to the localization back-end module to estimate the relative localization between Gq and Gdb); in response that the degree of association of the at least one node pair to be associated is greater than a threshold, determining that the at least one node pair to be associated is an associated node pair (III. X-VIEW, in a second step, the k matches with highest similarity score are selected for estimating the location of the query graph inside the database map) … (IV. EXPERIMENTS, for the PR curves, we vary the consistency threshold tc that is applied on the RANSAC-based rejection, i.e., the acceptable deviation from the consensus transformation between query and database graph vertices); determining a current pose of the robot according to the search branch with the highest matching degree (III. X-VIEW, we compute a Maximum a Posteriori (MAP) estimate of the robot pose ci by minimizing a negative log-posterior), and comprising: determining a preprocessing initial position of the robot according to an associated node pair with a highest matching degree and comprising: determining a preprocessing initial position of the robot according to an associated node pair with a highest matching degree (D. Descriptor Matching, in a second step, the k matches with highest similarity score are selected for estimating the location of the query graph inside the database map).
However, Gawel does not explicitly disclose selecting, from a plurality of search branches, a search branch with a largest number of associated node pairs as a search branch with a highest matching degree, and the associated node pair with the highest matching degree being an associated node pair of the search branch with the highest matching degree; and based on the preprocessing initial position, performing point cloud matching on the associated node pair with the highest matching degree to determine the current pose of the robot.
Nevertheless, Neira who is in the same field of endeavor of Stochastic Mapping discloses, selecting, from a plurality of search branches, a search branch with a largest number of associated node pairs as a search branch with a highest matching degree (III. OBTAINING CONSISTENT HYPOTHESES, we require a search algorithm to traverse the interpretation tree in search for the hypothesis that includes the largest number of jointly compatible pairings. SC could be used to restrict the search to tree nodes representing hypotheses with jointly compatible pairings) … (IV Experiments, the quality of a node at level i, corresponding to a hypothesis Hi, can be defined as the number of non-null pairings that can be established from the node. In this way, nodes with quality lower than the best available hypothesis are not explored).
One of ordinary skill in the art prior to the effective filing date of the given invention
would have been motivated to combine Gawel and Neira because they solve complementary halves of the same data association problem. Gawel gives a semantic graph matcher that computes a node pair similarity score from random walk descriptors and class labels. Neira then provides the search procedure needed and uses that count to bound/prune branches.
Further justification for combining Gawel and Neira not only comes from the state of the art but from Neira (Conclusion, complementary techniques, applicable when there is no estimation of the vehicle location, will constitute further work).
However Even the combination of Gawel and Neira does not explicitly disclose, the associated node pair with the highest matching degree being an associated node pair of the search branch with the highest matching degree; and based on the preprocessing initial position, performing point cloud matching on the associated node pair with the highest matching degree to determine the current pose of the robot.
Nevertheless, Liu who is in the same field of endeavor of global localization with object-level semantics discloses that the associated node pair with the highest matching degree being an associated node pair of the search branch with the highest matching degree (9D. Object Association, the top k global node(s) with the most shared descriptors is taken as a match, and the corresponding objects in the query and global map are associated); and they are based on the preprocessing initial position (E. Localization based on Object-Level Alignment, the alignment result and the estimated transformation are accepted when a minimum percentage of correctly aligned points is met. The estimated transformation gives the initial alignment to localize the query objects within the map), and performing point cloud matching on the associated node pair with the highest matching degree to determine the current pose of the robot (E. Localization based on Object-Level Alignment, this transformation is refined by the Iterative Closest Point algorithm (ICP) [39], resulting in the final 6-DoF query camera pose estimation).
One of ordinary skill in the art prior to the effective filing date of the given invention
would have been motivated to combine Gawel, Neira and Liu because they solve complementary halves of the same data association problem. Liu teaches using those associated semantic objects for pose estimation by the SAC IA method, and then refines the resulting transformation with the ICP algorithm resulting in a 6 DoF query camera pose estimation. This combination would be a predictable use of known techniques to improve pose estimation from the matched associated nodes/objects.
Further justification for combining Gawel, Neira and Liu not only comes from the state of the art but from Neira (Conclusion, complementary techniques, applicable when there is no estimation of the vehicle location, will constitute further work).
Regarding claim 2, Gawel, Neira, and Liu disclose, the method according to claim 1, as discussed supra. Additionally, Gawel discloses, the preprocessing initial position has position information but no attitude information (E. Localization Back-End, we initialize the robot position at the mean location of all matching vertices’ locations from Gdb).
Additionally, Liu discloses, the preprocessing initial position of the robot is determined according to the associated node pair with the highest matching degree by using Sample Consensus Initial Alignment (SAC-IA), (E. Localization Back-End, we use the Fast Point Feature Histograms (FPFH) and the Sample Consensus initial alignment method (SAC-IA) [20] to register the associated object Points … The estimated transformation gives the initial alignment to localize the query objects within the map), and the current pose of the robot is determined by, based on the preprocessing initial position, (E. Localization Back-End, the estimated transformation gives the initial alignment to localize the query objects within the map) and performing point cloud matching on the associated node pair with the highest matching degree using Iterative Closest Point (ICP) (E. Localization Back-End, Finally, this transformation is refined by the Iterative Closest Point algorithm (ICP) [39], resulting in the final 6-DoF query camera pose estimation).
Regarding claim 9, A robot, (Introduction, X-View introduces graph descriptors that efficiently represent unique topologies of semantic objects. These can be matched in much lower computational effort, therefore not suffering under the need for exhaustive sub-graph matching. By using semantics as an abstraction between robot viewpoints): wherein the robot comprises a processor, the processor is configured to: obtain a current local topology map (Introduction, this paper presents the following contributions: A novel graph representation for semantic topologies) … (X-VIEW, we convert a sequence of semantic images Iq into a query graph Gq), and a full topology map, (Fig. 2, the inputs to the system are semantically segmented frames (e.g., from RGB images) and the global graph Gdb), wherein the current local topology map is established based on objects in an environment currently observed by the robot (X-VIEW, we convert a sequence of semantic images Iq into a query graph Gq. We extract blobs of connected regions), the full topology map is pre-established based on objects in a full environment in a preset area (II. X-VIEW, we also consider a database semantic graph Gdb, as it could have been built and described on a previous run of our graph building algorithm as presented in the next sub-sections), the current local topology map comprises nodes representing the objects in the environment currently observed by the robot (II. X-VIEW, using a depth channel or the depth estimation from, e.g., optical flow, the neighborhood can be formed in 3D-space, using the 3D locations of the image blobs to compute a Euclidean distance), and the full topology map comprises nodes representing the objects in the full environment (II. X-VIEW, we also consider a database semantic graph Gdb, as it could have been built and described on a previous run of our graph building algorithm as presented in the next sub-sections); matching the nodes in the current local topology map and the nodes in the full topology map, wherein the matching comprises determining a degree of association of at least one node pair to be associated, which is constructed by the nodes in the current local topology map (III. X-VIEW, after both Gq and Gdb are created, we find associations between vertices in the query graph and the ones in the database graph by computing a similarity score between the corresponding graph descriptors), and the nodes in the full topology map (Fig. 2, first, a local graph is extracted from the new segmentation. Then, the sub-graph Gq is assembled and random walk descriptors are computed on each node of Gq. The system matches the sub-graph random walk descriptors to Gdb, e.g., recorded from a different view-point. Finally, the matches are transferred to the localization back-end module to estimate the relative localization between Gq and Gdb); in response that the degree of association of the at least one node pair to be associated is greater than a threshold, determining that the at least one node pair to be associated is an associated node pair (III. X-VIEW, in a second step, the k matches with highest similarity score are selected for estimating the location of the query graph inside the database map) … (IV. EXPERIMENTS, for the PR curves, we vary the consistency threshold tc that is applied on the RANSAC-based rejection, i.e., the acceptable deviation from the consensus transformation between query and database graph vertices); determining a current pose of the robot according to the search branch with the highest matching degree (III. X-VIEW, we compute a Maximum a Posteriori (MAP) estimate of the robot pose ci by minimizing a negative log-posterior), and comprising: determining a preprocessing initial position of the robot according to an associated node pair with a highest matching degree and comprising: determining a preprocessing initial position of the robot according to an associated node pair with a highest matching degree (D. Descriptor Matching, in a second step, the k matches with highest similarity score are selected for estimating the location of the query graph inside the database map).
However, Gawel does not explicitly disclose selecting, from a plurality of search branches, a search branch with a largest number of associated node pairs as a search branch with a highest matching degree, and the associated node pair with the highest matching degree being an associated node pair of the search branch with the highest matching degree; and based on the preprocessing initial position, performing point cloud matching on the associated node pair with the highest matching degree to determine the current pose of the robot.
Nevertheless, Neira who is in the same field of endeavor of Stochastic Mapping discloses, selecting, from a plurality of search branches, a search branch with a largest number of associated node pairs as a search branch with a highest matching degree (III. OBTAINING CONSISTENT HYPOTHESES, we require a search algorithm to traverse the interpretation tree in search for the hypothesis that includes the largest number of jointly compatible pairings. SC could be used to restrict the search to tree nodes representing hypotheses with jointly compatible pairings) … (IV Experiments, the quality of a node at level i, corresponding to a hypothesis Hi, can be defined as the number of non-null pairings that can be established from the node. In this way, nodes with quality lower than the best available hypothesis are not explored).
However Even the combination of Gawel and Neira does not explicitly disclose, the associated node pair with the highest matching degree being an associated node pair of the search branch with the highest matching degree; and based on the preprocessing initial position, performing point cloud matching on the associated node pair with the highest matching degree to determine the current pose of the robot.
Nevertheless, Liu who is in the same field of endeavor of global localization with object-level semantics discloses that the associated node pair with the highest matching degree being an associated node pair of the search branch with the highest matching degree (9D. Object Association, the top k global node(s) with the most shared descriptors is taken as a match, and the corresponding objects in the query and global map are associated); and they are based on the preprocessing initial position (E. Localization based on Object-Level Alignment, the alignment result and the estimated transformation are accepted when a minimum percentage of correctly aligned points is met. The estimated transformation gives the initial alignment to localize the query objects within the map), and performing point cloud matching on the associated node pair with the highest matching degree to determine the current pose of the robot (E. Localization based on Object-Level Alignment, this transformation is refined by the Iterative Closest Point algorithm (ICP) [39], resulting in the final 6-DoF query camera pose estimation).
Regarding claim 10, Gawel, Neira, and Liu disclose the robot according to claim 9, as discussed supra. Additionally, Gawel discloses, the preprocessing initial position has position information but no attitude information (E. Localization Back-End, we initialize the robot position at the mean location of all matching vertices’ locations from Gdb).
Additionally, Liu discloses, the preprocessing initial position of the robot is determined according to the associated node pair with the highest matching degree by using Sample Consensus Initial Alignment (SAC-IA), (E. Localization Back-End, we use the Fast Point Feature Histograms (FPFH) and the Sample Consensus initial alignment method (SAC-IA) [20] to register the associated object Points … The estimated transformation gives the initial alignment to localize the query objects within the map), and the current pose of the robot is determined by, based on the preprocessing initial position, (E. Localization Back-End, the estimated transformation gives the initial alignment to localize the query objects within the map) and performing point cloud matching on the associated node pair with the highest matching degree using Iterative Closest Point (ICP) (E. Localization Back-End, Finally, this transformation is refined by the Iterative Closest Point algorithm (ICP) [39], resulting in the final 6-DoF query camera pose estimation).
Regarding claim 17 Gawel discloses, A non-transitory storage medium, wherein the non-transitory storage medium stores a computer program, when the computer program is executed by a processor, (Introduction, X-View introduces graph descriptors that efficiently represent unique topologies of semantic objects. These can be matched in much lower computational effort, therefore not suffering under the need for exhaustive sub-graph matching. By using semantics as an abstraction between robot viewpoints): the processor is caused to perform a positioning method, the positioning method comprises: obtaining a current local topology map (Introduction, this paper presents the following contributions: A novel graph representation for semantic topologies) … (X-VIEW, we convert a sequence of semantic images Iq into a query graph Gq) and a full topology map (Fig. 2, the inputs to the system are semantically segmented frames (e.g., from RGB images) and the global graph Gdb), wherein the current local topology map is established based on objects in an environment currently observed by the robot (X-VIEW, we convert a sequence of semantic images Iq into a query graph Gq. We extract blobs of connected regions), the full topology map is pre-established based on objects in a full environment in a preset area (II. X-VIEW, we also consider a database semantic graph Gdb, as it could have been built and described on a previous run of our graph building algorithm as presented in the next sub-sections), the current local topology map comprises nodes representing the objects in the environment currently observed by the robot (II. X-VIEW, using a depth channel or the depth estimation from, e.g., optical flow, the neighborhood can be formed in 3D-space, using the 3D locations of the image blobs to compute a Euclidean distance), and the full topology map comprises nodes representing the objects in the full environment (II. X-VIEW, we also consider a database semantic graph Gdb, as it could have been built and described on a previous run of our graph building algorithm as presented in the next sub-sections); matching the nodes in the current local topology map and the nodes in the full topology map, wherein the matching comprises determining a degree of association of at least one node pair to be associated, which is constructed by the nodes in the current local topology map (III. X-VIEW, after both Gq and Gdb are created, we find associations between vertices in the query graph and the ones in the database graph by computing a similarity score between the corresponding graph descriptors), and the nodes in the full topology map (Fig. 2, first, a local graph is extracted from the new segmentation. Then, the sub-graph Gq is assembled and random walk descriptors are computed on each node of Gq. The system matches the sub-graph random walk descriptors to Gdb, e.g., recorded from a different view-point. Finally, the matches are transferred to the localization back-end module to estimate the relative localization between Gq and Gdb); in response that the degree of association of the at least one node pair to be associated is greater than a threshold, determining that the at least one node pair to be associated is an associated node pair (III. X-VIEW, in a second step, the k matches with highest similarity score are selected for estimating the location of the query graph inside the database map) … (IV. EXPERIMENTS, for the PR curves, we vary the consistency threshold tc that is applied on the RANSAC-based rejection, i.e., the acceptable deviation from the consensus transformation between query and database graph vertices); determining a current pose of the robot according to the search branch with the highest matching degree (III. X-VIEW, we compute a Maximum a Posteriori (MAP) estimate of the robot pose ci by minimizing a negative log-posterior), and comprising: determining a preprocessing initial position of the robot according to an associated node pair with a highest matching degree and comprising: determining a preprocessing initial position of the robot according to an associated node pair with a highest matching degree (D. Descriptor Matching, in a second step, the k matches with highest similarity score are selected for estimating the location of the query graph inside the database map).
Additionally, Neira who is in the same field of endeavor of Stochastic Mapping discloses, selecting, from a plurality of search branches, a search branch with a largest number of associated node pairs as a search branch with a highest matching degree (III. OBTAINING CONSISTENT HYPOTHESES, we require a search algorithm to traverse the interpretation tree in search for the hypothesis that includes the largest number of jointly compatible pairings. SC could be used to restrict the search to tree nodes representing hypotheses with jointly compatible pairings) … (IV Experiments, the quality of a node at level i, corresponding to a hypothesis Hi, can be defined as the number of non-null pairings that can be established from the node. In this way, nodes with quality lower than the best available hypothesis are not explored).
Furthermore, Liu who is in the same field of endeavor of global localization with object-level semantics discloses that the associated node pair with the highest matching degree being an associated node pair of the search branch with the highest matching degree (9D. Object Association, the top k global node(s) with the most shared descriptors is taken as a match, and the corresponding objects in the query and global map are associated); and they are based on the preprocessing initial position (E. Localization based on Object-Level Alignment, the alignment result and the estimated transformation are accepted when a minimum percentage of correctly aligned points is met. The estimated transformation gives the initial alignment to localize the query objects within the map), and performing point cloud matching on the associated node pair with the highest matching degree to determine the current pose of the robot (E. Localization based on Object-Level Alignment, this transformation is refined by the Iterative Closest Point algorithm (ICP) [39], resulting in the final 6-DoF query camera pose estimation).
Regarding claim 18 Gawel, Neira, and Liu disclose, the method according to claim 1, as discussed supra. Additionally, Gawel discloses, the preprocessing initial position has position information but no attitude information (E. Localization Back-End, we initialize the robot position at the mean location of all matching vertices’ locations from Gdb).
Additionally, Liu discloses, the preprocessing initial position of the robot is determined according to the associated node pair with the highest matching degree by using Sample Consensus Initial Alignment (SAC-IA), (E. Localization Back-End, we use the Fast Point Feature Histograms (FPFH) and the Sample Consensus initial alignment method (SAC-IA) [20] to register the associated object Points … The estimated transformation gives the initial alignment to localize the query objects within the map), and the current pose of the robot is determined by, based on the preprocessing initial position, (E. Localization Back-End, the estimated transformation gives the initial alignment to localize the query objects within the map) and performing point cloud matching on the associated node pair with the highest matching degree using Iterative Closest Point (ICP) (E. Localization Back-End, Finally, this transformation is refined by the Iterative Closest Point algorithm (ICP) [39], resulting in the final 6-DoF query camera pose estimation).
Claims 3, 11, and 19 are all rejected under 35 U.S.C. 103 as being unpatentable over Gawel et al. (X-View: Graph-Based Semantic Multi-View Localization), in view of Neira et al. (Data Association in Stochastic Mapping Using the Joint Compatibility Test), further in view of Liu et al. (Global Localization with Object-Level Semantics and Topology), further in view of Rosinol et al. (Kimera: from SLAM to Spatial Perception with 3D Dynamic Scene Graphs).
Regarding claim 3 Gawel, Neira, and Liu disclose, the method according to claim 1 as discussed supra. Additionally, Gawel discloses, establishing a full semantic map based on the full environment image and the full depth image (Figure 5, Sample images from the datasets used in the experiments: (top) RGB image, (middle) Depth image, (bottom) Semantic segmentation. (left SYNTHIA with perfect semantic segmentation, (middle left) SYNTHIA with AdapNet semantic segmentation, (middle right) Airsim with perfect semantic segmentation, (right) StreetView with SegNet semantic segmentation), obtaining the current local topology map comprises: obtaining a current environment image and a current depth image (IV. EXPERIMENTS, this environment is explored with a top-down viewing Unmanned
Aerial Vehicle (UAV) and a car traversing the streets with forward-facing sensors. Both views provide RGB, depth and pixel-wise semantic classification data in 13 different classes
with instance-wise labelling) … (III. X-VIEW, we convert a sequence of semantic images Iq into a query graph Gq), establishing a current semantic map according to the current environment image and the current depth image (III. X-VIEW, we convert a sequence of semantic images Iq into a query graph Gq. We extract blobs of connected regions, i.e., regions of the same class label lj in each image. Since semantically segmented images often show noisy partitioning of the observed scene (holes, disconnected edges and invalid labels on edges)), wherein the current semantic map comprises current point cloud information (III. X-VIEW, the neighborhood can be formed in 3D-space, using the 3D locations of the image blobs to compute a Euclidean distance), and second object type labels corresponding to the current point cloud information (III. X-VIEW, each of the random walks originates at the base vertex vj and stores the class labels of the visited vertices).
Additionally, Liu discloses, obtaining the full topology map comprises: obtaining a full environment image and a full depth image (A. Dataset, the first dataset we experimented is the public SceneNN dataset [38]. It includes a number of indoor sequences of various types, scales and furnishings. Each sequence provides full-sequence RGB frames, depth maps, groundtruth pixel wise semantic classifications, and 6-DoF camera poses); wherein the full semantic map comprises full point cloud information (B. High-Level Features for Localization, combine state-of-the-art SLAM and semantic segmentation CNN to build consistent semantic maps by probabilistically fusing multiple semantic predictions from different viewpoints), and first object type labels corresponding to the full point cloud information (B. Graph Extraction, to add object nodes in the graph, from the semantic map we first extract nearby points having the same semantic labels with Euclidean clustering [37]. Classes of “wall”, “floor”, and “ceiling” are omitted as they do not introduce useful topological relations); clustering the full point cloud information in the full semantic map according to the first object type labels (B. Graph Extraction, to add object nodes in the graph, from the semantic map we first extract nearby points having the same semantic labels with Euclidean clustering [37]. Classes of “wall”, “floor”, and “ceiling” are omitted as they do not introduce useful topological relations), identifying each object (B. Graph Extraction, labels with Euclidean clustering [37]. Classes of “wall”, “floor”, and “ceiling” are omitted as they do not introduce useful topological relations), and obtaining a first bounding box of each object (B. Graph Extraction, In the graph. We choose a bounding sphere to represent each object as spheres hold the implicit property of being rotationally invariant), wherein the first bounding box is an independent space corresponding to point clouds with same first object type label after clustering the point clouds ((B. Graph Extraction, To add object nodes in the graph, from the semantic map we first extract nearby points having the same semantic labels with Euclidean clustering); taking each first bounding box as a node ((B. Graph Extraction, Object nodes and edges are used to describe the 3D semantic topology of a map), and taking a connection line between two adjacent first bounding boxes as an edge to generate the full topology map, (B. Graph Extraction, Undirected edges are formed between any two object nodes within a proximity distance. We also define that two nodes whose bounding spheres interact with each other always form edges regardless of the distance apart), wherein a distance between the two adjacent first bounding boxes is less than a preset distance (B. Graph Extraction, Undirected edges are formed between
any two object nodes within a proximity distance). However, The combination of Gawel and Liu does not explicitly disclose, clustering the current point cloud information in the current semantic map according to the second object type labels identifying each object, and obtaining a second bounding box of each object wherein the second bounding box is an independent space corresponding to point clouds with same second object type label after clustering the point clouds and taking each second bounding box as a node and taking a connection line between two adjacent second bounding boxes as an edge to generate the current local topology map wherein a distance between the two adjacent second bounding boxes is less than the preset distance.
Nevertheless, Rosinol who is in the same field of endeavor of SLAM to spatial perception discloses, clustering the current point cloud information in the current semantic map according to the second object type labels (3.3, using the 2D semantic segmentation, we attach a label to each 3D point produced by dense stereo) … (3.6, to break down the mesh into multiple object instances, Kimera-Objects performs Euclidean clustering using PCL), identifying each object, and obtaining a second bounding box of each object (3.6, to break down the mesh into multiple object instances, Kimera-Objects performs Euclidean clustering using PCL) … (3.6, if a shape is available, Kimera-Objects will try to fit it to the mesh (paragraph “Objects with Known Shape” below), otherwise it will only attempt to estimate a centroid and a bounding box (paragraph “Objects with Unknown Shape”), wherein the second bounding box is an independent space corresponding to point clouds with same second object type label after clustering the point clouds (3.6, from the segmented clusters, Kimera-Objects obtains a centroid of the object (from the vertices of the corresponding mesh), and assigns a canonical orientation with axes aligned with the world frame. Finally, it computes a bounding box with axes aligned with the canonical orientation); and taking each second bounding box as a node and taking a connection line between two adjacent second bounding boxes as an edge to generate the current local topology map (2.2, edges between objects describe relations, such as co-visibility, relative size, distance, or contact (“the cup is on the desk”). Each object node is connected to the corresponding set of points belonging to the object in the Metric-Semantic Mesh), wherein a distance between the two adjacent second bounding boxes is less than the preset distance (2.2, moreover, each object is connected to the nearest reachable place node).
One of ordinary skill in the art prior to the effective filing date of the given invention
would have been motivated to combine Gawel, Neira, and Liu with Rosinol because they solve complementary pieces of the same semantic topological matching problem. Gawel provides the node level semantic similarity mechanism via random walk descriptors and a similarity score. Neira supplies the global search procedure and interpretation tree traversal that selects the hypothesis/branch with the largest number of compatible pairings . Then Rosinol contributes the map representation and features making it natural to use the object nodes as the topology map element that Gawel matches and Neira validates.
Further justification for combining Gawel and Neira with Rosinol not only comes from the state of the art but from Neira (Conclusion, complementary techniques, applicable when there is no estimation of the vehicle location, will constitute further work).
Regarding claim 11, Gawel, Neira, and Liu disclose, the robot according to claim 9 as discussed supra. Additionally, Gawel discloses, establishing a full semantic map based on the full environment image and the full depth image (Figure 5, Sample images from the datasets used in the experiments: (top) RGB image, (middle) Depth image, (bottom) Semantic segmentation. (left SYNTHIA with perfect semantic segmentation, (middle left) SYNTHIA with AdapNet semantic segmentation, (middle right) Airsim with perfect semantic segmentation, (right) StreetView with SegNet semantic segmentation), obtaining the current local topology map comprises: obtaining a current environment image and a current depth image (IV. EXPERIMENTS, this environment is explored with a top-down viewing Unmanned
Aerial Vehicle (UAV) and a car traversing the streets with forward-facing sensors. Both views provide RGB, depth and pixel-wise semantic classification data in 13 different classes
with instance-wise labelling) … (III. X-VIEW, we convert a sequence of semantic images Iq into a query graph Gq), establishing a current semantic map according to the current environment image and the current depth image (III. X-VIEW, we convert a sequence of semantic images Iq into a query graph Gq. We extract blobs of connected regions, i.e., regions of the same class label lj in each image. Since semantically segmented images often show noisy partitioning of the observed scene (holes, disconnected edges and invalid labels on edges)), wherein the current semantic map comprises current point cloud information (III. X-VIEW, the neighborhood can be formed in 3D-space, using the 3D locations of the image blobs to compute a Euclidean distance), and second object type labels corresponding to the current point cloud information (III. X-VIEW, each of the random walks originates at the base vertex vj and stores the class labels of the visited vertices).
Additionally, Liu discloses, obtaining the full topology map comprises: obtaining a full environment image and a full depth image (A. Dataset, the first dataset we experimented is the public SceneNN dataset [38]. It includes a number of indoor sequences of various types, scales and furnishings. Each sequence provides full-sequence RGB frames, depth maps, groundtruth pixel wise semantic classifications, and 6-DoF camera poses); wherein the full semantic map comprises full point cloud information (B. High-Level Features for Localization, combine state-of-the-art SLAM and semantic segmentation CNN to build consistent semantic maps by probabilistically fusing multiple semantic predictions from different viewpoints), and first object type labels corresponding to the full point cloud information (B. Graph Extraction, to add object nodes in the graph, from the semantic map we first extract nearby points having the same semantic labels with Euclidean clustering [37]. Classes of “wall”, “floor”, and “ceiling” are omitted as they do not introduce useful topological relations); clustering the full point cloud information in the full semantic map according to the first object type labels (B. Graph Extraction, to add object nodes in the graph, from the semantic map we first extract nearby points having the same semantic labels with Euclidean clustering [37]. Classes of “wall”, “floor”, and “ceiling” are omitted as they do not introduce useful topological relations), identifying each object (B. Graph Extraction, labels with Euclidean clustering [37]. Classes of “wall”, “floor”, and “ceiling” are omitted as they do not introduce useful topological relations), and obtaining a first bounding box of each object (B. Graph Extraction, In the graph. We choose a bounding sphere to represent each object as spheres hold the implicit property of being rotationally invariant), wherein the first bounding box is an independent space corresponding to point clouds with same first object type label after clustering the point clouds ((B. Graph Extraction, To add object nodes in the graph, from the semantic map we first extract nearby points having the same semantic labels with Euclidean clustering); taking each first bounding box as a node ((B. Graph Extraction, Object nodes and edges are used to describe the 3D semantic topology of a map), and taking a connection line between two adjacent first bounding boxes as an edge to generate the full topology map, (B. Graph Extraction, Undirected edges are formed between any two object nodes within a proximity distance. We also define that two nodes whose bounding spheres interact with each other always form edges regardless of the distance apart), wherein a distance between the two adjacent first bounding boxes is less than a preset distance (B. Graph Extraction, Undirected edges are formed between
any two object nodes within a proximity distance). However, The combination of Gawel and Liu does not explicitly disclose, clustering the current point cloud information in the current semantic map according to the second object type labels identifying each object, and obtaining a second bounding box of each object wherein the second bounding box is an independent space corresponding to point clouds with same second object type label after clustering the point clouds and taking each second bounding box as a node and taking a connection line between two adjacent second bounding boxes as an edge to generate the current local topology map wherein a distance between the two adjacent second bounding boxes is less than the preset distance.
Nevertheless, Rosinol who is in the same field of endeavor of SLAM to spatial perception discloses, clustering the current point cloud information in the current semantic map according to the second object type labels (3.3, using the 2D semantic segmentation, we attach a label to each 3D point produced by dense stereo) … (3.6, to break down the mesh into multiple object instances, Kimera-Objects performs Euclidean clustering using PCL), identifying each object, and obtaining a second bounding box of each object (3.6, to break down the mesh into multiple object instances, Kimera-Objects performs Euclidean clustering using PCL) … (3.6, if a shape is available, Kimera-Objects will try to fit it to the mesh (paragraph “Objects with Known Shape” below), otherwise it will only attempt to estimate a centroid and a bounding box (paragraph “Objects with Unknown Shape”), wherein the second bounding box is an independent space corresponding to point clouds with same second object type label after clustering the point clouds (3.6, from the segmented clusters, Kimera-Objects obtains a centroid of the object (from the vertices of the corresponding mesh), and assigns a canonical orientation with axes aligned with the world frame. Finally, it computes a bounding box with axes aligned with the canonical orientation); and taking each second bounding box as a node and taking a connection line between two adjacent second bounding boxes as an edge to generate the current local topology map (2.2, edges between objects describe relations, such as co-visibility, relative size, distance, or contact (“the cup is on the desk”). Each object node is connected to the corresponding set of points belonging to the object in the Metric-Semantic Mesh), wherein a distance between the two adjacent second bounding boxes is less than the preset distance (2.2, moreover, each object is connected to the nearest reachable place node).
Regarding claim 19, Gawel, Neira, and Liu disclose The non-transitory storage medium according to claim as discussed supra. Additionally, Gawel discloses, establishing a full semantic map based on the full environment image and the full depth image (Figure 5, Sample images from the datasets used in the experiments: (top) RGB image, (middle) Depth image, (bottom) Semantic segmentation. (left SYNTHIA with perfect semantic segmentation, (middle left) SYNTHIA with AdapNet semantic segmentation, (middle right) Airsim with perfect semantic segmentation, (right) StreetView with SegNet semantic segmentation), obtaining the current local topology map comprises: obtaining a current environment image and a current depth image (IV. EXPERIMENTS, this environment is explored with a top-down viewing Unmanned
Aerial Vehicle (UAV) and a car traversing the streets with forward-facing sensors. Both views provide RGB, depth and pixel-wise semantic classification data in 13 different classes
with instance-wise labelling) … (III. X-VIEW, we convert a sequence of semantic images Iq into a query graph Gq), establishing a current semantic map according to the current environment image and the current depth image (III. X-VIEW, we convert a sequence of semantic images Iq into a query graph Gq. We extract blobs of connected regions, i.e., regions of the same class label lj in each image. Since semantically segmented images often show noisy partitioning of the observed scene (holes, disconnected edges and invalid labels on edges)), wherein the current semantic map comprises current point cloud information (III. X-VIEW, the neighborhood can be formed in 3D-space, using the 3D locations of the image blobs to compute a Euclidean distance), and second object type labels corresponding to the current point cloud information (III. X-VIEW, each of the random walks originates at the base vertex vj and stores the class labels of the visited vertices).
Additionally, Liu discloses, obtaining the full topology map comprises: obtaining a full environment image and a full depth image (A. Dataset, the first dataset we experimented is the public SceneNN dataset [38]. It includes a number of indoor sequences of various types, scales and furnishings. Each sequence provides full-sequence RGB frames, depth maps, groundtruth pixel wise semantic classifications, and 6-DoF camera poses); wherein the full semantic map comprises full point cloud information (B. High-Level Features for Localization, combine state-of-the-art SLAM and semantic segmentation CNN to build consistent semantic maps by probabilistically fusing multiple semantic predictions from different viewpoints), and first object type labels corresponding to the full point cloud information (B. Graph Extraction, to add object nodes in the graph, from the semantic map we first extract nearby points having the same semantic labels with Euclidean clustering [37]. Classes of “wall”, “floor”, and “ceiling” are omitted as they do not introduce useful topological relations); clustering the full point cloud information in the full semantic map according to the first object type labels (B. Graph Extraction, to add object nodes in the graph, from the semantic map we first extract nearby points having the same semantic labels with Euclidean clustering [37]. Classes of “wall”, “floor”, and “ceiling” are omitted as they do not introduce useful topological relations), identifying each object (B. Graph Extraction, labels with Euclidean clustering [37]. Classes of “wall”, “floor”, and “ceiling” are omitted as they do not introduce useful topological relations), and obtaining a first bounding box of each object (B. Graph Extraction, In the graph. We choose a bounding sphere to represent each object as spheres hold the implicit property of being rotationally invariant), wherein the first bounding box is an independent space corresponding to point clouds with same first object type label after clustering the point clouds ((B. Graph Extraction, To add object nodes in the graph, from the semantic map we first extract nearby points having the same semantic labels with Euclidean clustering); taking each first bounding box as a node ((B. Graph Extraction, Object nodes and edges are used to describe the 3D semantic topology of a map), and taking a connection line between two adjacent first bounding boxes as an edge to generate the full topology map, (B. Graph Extraction, Undirected edges are formed between any two object nodes within a proximity distance. We also define that two nodes whose bounding spheres interact with each other always form edges regardless of the distance apart), wherein a distance between the two adjacent first bounding boxes is less than a preset distance (B. Graph Extraction, Undirected edges are formed between
any two object nodes within a proximity distance). However, The combination of Gawel and Liu does not explicitly disclose, clustering the current point cloud information in the current semantic map according to the second object type labels identifying each object, and obtaining a second bounding box of each object wherein the second bounding box is an independent space corresponding to point clouds with same second object type label after clustering the point clouds and taking each second bounding box as a node and taking a connection line between two adjacent second bounding boxes as an edge to generate the current local topology map wherein a distance between the two adjacent second bounding boxes is less than the preset distance.
Nevertheless, Rosinol who is in the same field of endeavor of SLAM to spatial perception discloses, clustering the current point cloud information in the current semantic map according to the second object type labels (3.3, using the 2D semantic segmentation, we attach a label to each 3D point produced by dense stereo) … (3.6, to break down the mesh into multiple object instances, Kimera-Objects performs Euclidean clustering using PCL), identifying each object, and obtaining a second bounding box of each object (3.6, to break down the mesh into multiple object instances, Kimera-Objects performs Euclidean clustering using PCL) … (3.6, if a shape is available, Kimera-Objects will try to fit it to the mesh (paragraph “Objects with Known Shape” below), otherwise it will only attempt to estimate a centroid and a bounding box (paragraph “Objects with Unknown Shape”), wherein the second bounding box is an independent space corresponding to point clouds with same second object type label after clustering the point clouds (3.6, from the segmented clusters, Kimera-Objects obtains a centroid of the object (from the vertices of the corresponding mesh), and assigns a canonical orientation with axes aligned with the world frame. Finally, it computes a bounding box with axes aligned with the canonical orientation); and taking each second bounding box as a node and taking a connection line between two adjacent second bounding boxes as an edge to generate the current local topology map (2.2, edges between objects describe relations, such as co-visibility, relative size, distance, or contact (“the cup is on the desk”). Each object node is connected to the corresponding set of points belonging to the object in the Metric-Semantic Mesh), wherein a distance between the two adjacent second bounding boxes is less than the preset distance (2.2, moreover, each object is connected to the nearest reachable place node).
Claims 4-7, 12-15, and 20 are all rejected under 35 U.S.C. 103 as being unpatentable over Gawel et al. (X-View: Graph-Based Semantic Multi-View Localization) in view of Neira et al. (Data Association in Stochastic Mapping Using the Joint Compatibility Test), further in view of Rosinol et al. (Kimera: from SLAM to Spatial Perception with 3D Dynamic Scene Graphs), further in view of De Lorenzi et al. (vf2_subgraph_iso).
Regarding claim 4, Gawel, Neira, and Rosinol disclose, the method according to claim 3 as discussed supra. Additionally Gawel discloses, determining whether the first object type label corresponding to the node in the full topology map is the same as the second object type label corresponding to the node in the current local topology map in the first node pair; (C.Descriptors, each vertex descriptor is an n × m matrix consisting of n random walks of depth m. Each of the random walks originates at the base vertex vj and stores the class labels of the visited vertices) … (D. Descriptor Matching, the number of identical random walks on the two descriptors reflects the similarity score s, w), determining whether the first object type label corresponding to the node in the full topology map is the same as the second object type label corresponding to the node in the current local topology map in the second node pair; (C. Descriptors, each vertex descriptor is an n × m matrix consisting of n random walks of depth m. Each of the random walks originates at the base vertex vj and stores the class labels of the visited vertices) … (D. Descriptor Matching, the number of identical random walks on the two descriptors reflects the similarity score s, w), and obtaining a degree of association of a node pair to be associated formed by the first node pair and the second node pair (D. Descriptor Matching, we find associations between vertices in the query graph and the ones in the database graph by computing a similarity score between the corresponding graph descriptors).
Additionally, Neira discloses, selecting, from the plurality of search branches, the search branch with the largest number of associated node pairs as the search branch with the highest matching degree comprises: combining the current local topology map and the full topology map to construct a search interpretation tree (III. OBTAINING CONSISTENT HYPOTHESES, we require a search algorithm to traverse the interpretation tree in search for the hypothesis that includes the largest number of jointly compatible pairings. SC could be used to restrict the search to tree nodes representing hypotheses with jointly compatible pairings) … (IV Experiments, the quality of a node at level i, corresponding to a hypothesis Hi, can be defined as the number of non-null pairings that can be established from the node. In this way, nodes with quality lower than the best available hypothesis are not explored), wherein the search interpretation tree comprises the plurality of search branches (II. THE CLASSICAL NEAREST NEIGHBOR APPROACH, this exponential solution space can be represented as an interpretation tree of levels each node at level , called an -interpretation, provides an interpretation for the first measurements. each node has branches), and traversing each of the search branches (III. OBTAINING CONSISTENT HYPOTHES, the joint compatibility branch and bound (JCBB) algorithm proposed in this work traverses the interpretation tree in search of the hypothesis with the largest number of nonnull jointly compatible pairings); constituting a second-layer node using each node in the current local topology map; (II. THE CLASSICAL NEAREST NEIGHBOR APPROACH, this exponential solution space can be represented as an interpretation tree of levels; each node at level , called an -interpretation, provides an interpretation for the first measurements. Each node has branches, corresponding to each of the alternative interpretations for measurement Ei),) taking the second-layer node as a parent node, and constituting a third-layer node by taking each node in the full topology map as a child node of the second-layer node, (II. THE CLASSICAL NEAREST NEIGHBOR APPROACH, this exponential solution space can be represented as an interpretation tree of levels [2]; each node at level , called an -interpretation, provides an interpretation for the first measurements. Each node has branches, corresponding to each of the alternative interpretations for measurement (including the possibility that the measurement be Spurious), wherein the second-layer node and the third-layer node constitute a first node pair of the search interpretation tree (III. OBTAINING CONSISTENT HYPOTHESES, we require a search algorithm to traverse the interpretation tree in search for the hypothesis that includes the largest number of jointly compatible pairings. SC could be used to restrict the search to tree nodes representing hypotheses with jointly compatible pairings); wherein the fourth-layer node and the fifth-layer node constitute a second node pair of the search interpretation tree; (HYPOTHESES, we require a search algorithm to traverse the interpretation tree in search for the hypothesis that includes the largest number of jointly compatible pairings. SC could be used to restrict the search to tree nodes representing hypotheses with jointly compatible pairings); determining whether the first object type label corresponding to the node in the full topology map is the same as the second object type label corresponding to the node in the current local topology map in the second node pair according to a distance and an angle between two current local topology map nodes in the first node pair and the second node pair and a distance and an angle between two full topology map nodes in a same search branch, (I. INTRODUCTION, Baley et al. consider relative distances and angles between points and lines in two laser scans and use a graph theoretic approach to find the largest number of pairwise compatible pairings) … (III. OBTAINING CONSISTENT HYPOTHES, the joint compatibility branch and bound (JCBB) algorithm proposed in this work traverses the interpretation tree in search of the hypothesis with the largest number of nonnull jointly compatible pairings), and the degree of association is greater than the threshold, continuing to traverse the node of the current local topology map and the full topology map (B. Joint Compatibility Branch and Bound, we require a search algorithm to traverse the interpretation tree in search of the hypothesis that includes the largest number of jointly compatible pairings), counting a number of associated node pairs of each search branch, (B. Joint Compatibility Branch and Bound, the joint compatibility branch and bound (JCBB) algorithm proposed in this work traverses the interpretation tree in search of the hypothesis with the largest number of nonnull jointly compatible pairings. This monotonically nondecreasing criterion can be used to bound the search in the interpretation tree [2]), and determining the search branch with the largest number of associated node pairs as the search branch with the highest matching degree (B. Joint Compatibility Branch and Bound, the quality of a node at level , corresponding to a hypothesis, can be defined as the number of nonnull pairings that can be established from the node). However, Gawel, Neira, and Rosinol do not explicitly disclose, in response that the first object type label corresponding to the node in the full topology map is different from the second object type label corresponding to the node in the current local topology map in the first node pair, ending a construction of a corresponding search branch; in response that the first object type label corresponding to the node in the full topology map is the same as the second object type label corresponding to the node in the current local topology map in the first node pair, taking the third-layer node as the parent node, and constituting a fourth-layer node by taking all remaining nodes after removing nodes that appeared in an upstream branch of the search branch in the current local topology map as child nodes of the third-layer node; taking the fourth-layer node as the parent node, and constituting a fifth-layer node by taking all the remaining nodes in the full topology map after removing the nodes that appeared in the upstream branch of the search branch as child nodes of the fourth-layer node, and constituting a fifth-layer node by taking all the remaining nodes in the full topology map after removing the nodes that appeared in the upstream branch of the search branch as child nodes of the fourth-layer node in response that the first object type label corresponding to the node in the full topology map is different from the second object type label corresponding to the node in the current local topology map in the second node pair, or the degree of association is less than the threshold, ending the construction of the corresponding search branch; in response that the first object type label corresponding to the node in the full topology map is the same as the second object type label corresponding to the node in the current local topology map in the second node pair.
Nevertheless, De Lorenzi who is in the same field of endeavor of isomorphism between two graphs discloses, in response that the first object type label corresponding to the node in the full topology map is different from the second object type label corresponding to the node in the current local topology map in the first node pair, ending a construction of a corresponding search branch; in response that the first object type label corresponding to the node in the full topology map is the same as the second object type label corresponding to the node in the current local topology map in the first node pair, taking the third-layer node as the parent node (vf2_subgraph_iso, EdgeEquivalencePredicate and VertexEquivalencePredicate predicates are used to test whether edges and vertices are equivalent) … (vf2_subgraph_iso, if a pair of vertices (v, w) is feasible, the mapping is extended and the associated successor states' is computed. The whole procedure is then repeated for state’s'), and constituting a fourth-layer node by taking all remaining nodes after removing nodes that appeared in an upstream branch of the search branch in the current local topology map as child nodes of the third-layer node (vf2_subgraph_iso, each states of the matching process can be associated with a partial mapping M(s). At each level, the algorithm computes the set of the vertex pairs that are candidates to be added to the current states. If a pair of vertices (v, w) is feasible, the mapping is extended and the associated successor states' is computed. The whole procedure is then repeated for state’s'); taking the fourth-layer node as the parent node, and constituting a fifth-layer node by taking all the remaining nodes in the full topology map after removing the nodes that appeared in the upstream branch of the search branch as child nodes of the fourth-layer node, and constituting a fifth-layer node by taking all the remaining nodes in the full topology map after removing the nodes that appeared in the upstream branch of the search branch as child nodes of the fourth-layer node ((vf2_subgraph_iso, an isomorphism between two graphs G1=(V1, E1) and G2=(V2, E2) is a bijective mapping M of the vertices of one graph to vertices of the other graph)… (this function finds all induced subgraph isomorphisms between graphs graph_small and graph_large and outputs them to user_callback), in response that the first object type label corresponding to the node in the full topology map is different from the second object type label corresponding to the node in the current local topology map in the second node pair, or the degree of association is less than the threshold, ending the construction of the corresponding search branch (vf2_subgraph_iso, each states of the matching process can be associated with a partial mapping M(s). At each level, the algorithm computes the set of the vertex pairs that are candidates to be added to the current states. If a pair of vertices (v, w) is feasible, the mapping is extended and the associated successor states' is computed. The whole procedure is then repeated for state’s'); in response that the first object type label corresponding to the node in the full topology map is the same as the second object type label corresponding to the node in the current local topology map in the second node pair, (vf2_subgraph_iso, it can be described by means of a state space representation which is created by the algorithm while exploring the search graph in depth-first fashion. Each states of the matching process can be associated with a partial mapping M(s). At each level, the algorithm computes the set of the vertex pairs that are candidates to be added to the current state’s).
One of ordinary skill in the art prior to the effective filing date of the given invention
would have been motivated to combine Gawel, Neira, and Rosinol’s disclosure with De Lorenzi because De Lorenzi contributes semantic weighting/selection and region of interest focusing that naturally augments Gawel’s similarity to favor distinctive objects and produce a high confidence central node.
Further justification for combining Gawel and Neira not only comes from the state of the art but from Neira (Conclusion, complementary techniques, applicable when there is no estimation of the vehicle location, will constitute further work).
Regarding claim 5, Gawel, Neira, Rosinol, and De Lorenzi disclose the method according to claim 4 as discussed supra. Additionally, Neira discloses, before selecting, from the plurality of search branches, the search branch with the largest number of associated node pairs as the search branch with the highest matching degree, the method further comprises combining the current local topology map and the full topology map to construct the search interpretation tree (III. OBTAINING CONSISTENT HYPOTHESES, we require a search algorithm to traverse the interpretation tree in search for the hypothesis that includes the largest number of jointly compatible pairings. SC could be used to restrict the search to tree nodes representing hypotheses with jointly compatible pairings) … (IV Experiments, the quality of a node at level i, corresponding to a hypothesis Hi, can be defined as the number of non-null pairings that can be established from the node. In this way, nodes with quality lower than the best available hypothesis are not explored); taking each node in the current local topology map as the second-layer node; taking the second-layer node as the parent node, and constructing the third-layer node by taking each node in the full topology map as child nodes of the second-layer node (II. THE CLASSICAL NEAREST NEIGHBOR APPROACH, this exponential solution space can be represented as an interpretation tree of levels [2]; each node at level , called an interpretation, provides an interpretation for the first measurements. Each node has branches, corresponding to each of the alternative interpretations for measurement (including the possibility that the measurement be Spurious); and by analogy, continuing to traverse the nodes of the current local topology map and the full topology map to construct the search interpretation tree (B. Joint Compatibility Branch and Bound, we require a search algorithm to traverse the interpretation tree in search of the hypothesis that includes the largest number of jointly compatible pairings).
Additionally, De Lorenzi discloses, taking the third-layer node as the parent node, and constructing the fourth-layer node by taking all the remaining nodes after removing the nodes that appeared in the upstream branch of the search branch in the current local topology map as child nodes of the third-layer node (vf2_subgraph_iso, EdgeEquivalencePredicate and VertexEquivalencePredicate predicates are used to test whether edges and vertices are equivalent) … (vf2_subgraph_iso, if a pair of vertices (v, w) is feasible, the mapping is extended and the associated successor states' is computed. The whole procedure is then repeated for state’s'); taking the fourth-layer node as the parent node, and constructing the fifth-layer node by taking all remaining nodes after removing the nodes that appeared in the upstream branch of the search branch in the full topology map as the child nodes of the fourth-layer node (vf2_subgraph_iso, an isomorphism between two graphs G1=(V1, E1) and G2=(V2, E2) is a bijective mapping M of the vertices of one graph to vertices of the other graph) … (this function finds all induced subgraph isomorphisms between graphs graph_small and graph_large and outputs them to user_callback).
Regarding claim 6, Gawel, Neira, Rosinol, and De Lorenzi disclose the method according to claim 5 as discussed supra. Additionally, Neira discloses, the search interpretation tree comprises the plurality of search branches, and selecting, from the plurality of search branches, the search branch with the largest number of associated node pairs as the search branch with the highest matching degree comprises: traversing each of the plurality of search branches; (B. Joint Compatibility Branch and Bound, we require a search algorithm to traverse the interpretation tree in search of the hypothesis that includes the largest number of jointly compatible pairings) and counting a number of associated node pairs of each matching branch, and determining the matching branch with the largest number of associated node pairs as the search branch with the highest matching degree (III. OBTAINING CONSISTENT HYPOTHESES, we require a search algorithm to traverse the interpretation tree in search for the hypothesis that includes the largest number of jointly compatible pairings. SC could be used to restrict the search to tree nodes representing hypotheses with jointly compatible pairings) … (IV Experiments, the quality of a node at level i, corresponding to a hypothesis Hi, can be defined as the number of non-null pairings that can be established from the node. In this way, nodes with quality lower than the best available hypothesis are not explored).
Additionally, De Lorenzi discloses, in response that the search branch of the search interpretation tree comprising the associated node pair, determining the search branch as a matching branch; and in response that the search branch of the search interpretation tree not comprising the associated node pair, interrupting a search of the corresponding search branch (vf2_subgraph_iso, this function finds all induced subgraph isomorphisms between graphs graph_small and graph_large and outputs them to user_callback. It continues until user_callback returns false or the search space has been fully explored. vf2_subgraph_iso returns true if a graph-subgraph isomorphism exists and false otherwise).
Regarding claim 7, Gawel, Neira, Rosinol, and De Lorenzi disclose the method according to claim 6 as discussed supra. Additionally, Gawel discloses, matching the nodes in the current local topology map and the nodes in the full topology map, wherein the matching comprises determining a degree of association of at least one node pair to be associated, which is constructed by the nodes in the current local topology map and the nodes in the full topology map” comprises: (D. Descriptor Matching, after both Gq and Gdb are created, we find associations between vertices in the query graph and the ones in the database graph by computing a similarity score between the corresponding graph descriptors) … (Figure 4, each line of the descriptor starts with the seed vertex label and continues with the class labels of the visited vertices) determining whether a first node of the current local topology map and a first node of the full topology map belong to a same object type label (III. X-VIEW, we extract blobs of connected regions, i.e., regions of the same class label lj in each image. Since semantically segmented images often show noisy partitioning of the observed scene (holes, disconnected edges and invalid labels on edges)), in response that the first node of the current local topology map and the first node of the full topology map belong to the same object type label, determining whether a second node of the current local topology map and a second node of the full topology map belong to the same object type label, (D. Descriptor Matching, between vertices in the query graph and the ones in the database graph by computing a similarity score between the corresponding graph descriptors. The similarity measure is computed by matching each row of the semantic descriptor of the query vertex to the descriptor of the database vertex), and in response that the second node of the current local topology map and the second node of the full topology map belong to the same object type label, (Fig. 4, each line of the descriptor starts with the seed vertex label and continues with the class labels of the visited vertices), comparing a distance and an angle between the first node of the current local topology map and the second node of the current local topology map with a distance (D. Descriptor Matching, after both Gq and Gdb are created, we find associations between vertices in the query graph and the ones in the database graph by computing a similarity score between the corresponding graph descriptors) and obtaining the degree of association of the node pair to be associated constructed by the first node pair and the second node pair (D. Descriptor Matching, after both Gq and Gdb are created, we find associations between vertices in the query graph and the ones in the database … The number of identical random walks on the two descriptors reflects the similarity score s, which is normalized between 0 and 1).
Additionally, Neira discloses, wherein the second node of the current local topology map and the second node of the full topology map construct a second node pair (II. THE CLASSICAL NEAREST NEIGHBOR APPROACH, the purpose of a data association algorithm is to generate a hypothesis that pairs each measurement with a map feature (when , the measurement is considered spurious). This exponential solution space can be represented as an interpretation tree of levels), and an angle between the first node of the full topology map and the second node of the full topology map, (I. INTRODUCTION, in other approaches, geometric constraints between features are used to obtain hypotheses with pairwise compatible pairings. Baley et al. [16] consider relative distances and angles between points and lines in two laser scans and use a graph theoretic approach to find the largest number of pairwise compatible pairings), in response that the degree of association is greater than the threshold, determining the node pair to be associated as an associated node pair (B. Joint Compatibility Branch and Bound, we require a search algorithm to traverse the interpretation tree in search of the hypothesis that includes the largest number of jointly compatible pairings).
Additionally, De Lorenzi discloses the first node of the current local topology map and the first node of the full topology map construct a first node pair (vf2_subgraph_iso, each states of the matching process can be associated with a partial mapping M(s). At each level, the algorithm computes the set of the vertex pairs that are candidates to be added to the current states. If a pair of vertices (v, w) is feasible, the mapping is extended and the associated successor states' is computed. The whole procedure is then repeated for state’s').
Regarding claim 12 Gawel, Neira, and Rosinol disclose, the robot according claim 11 as discussed supra. Additionally, Gawel discloses, determining whether the first object type label corresponding to the node in the full topology map is the same as the second object type label corresponding to the node in the current local topology map in the first node pair; (C.Descriptors, each vertex descriptor is an n × m matrix consisting of n random walks of depth m. Each of the random walks originates at the base vertex vj and stores the class labels of the visited vertices) … (D. Descriptor Matching, the number of identical random walks on the two descriptors reflects the similarity score s, w), determining whether the first object type label corresponding to the node in the full topology map is the same as the second object type label corresponding to the node in the current local topology map in the second node pair; (C. Descriptors, each vertex descriptor is an n × m matrix consisting of n random walks of depth m. Each of the random walks originates at the base vertex vj and stores the class labels of the visited vertices) … (D. Descriptor Matching, the number of identical random walks on the two descriptors reflects the similarity score s, w), and obtaining a degree of association of a node pair to be associated formed by the first node pair and the second node pair (D. Descriptor Matching, we find associations between vertices in the query graph and the ones in the database graph by computing a similarity score between the corresponding graph descriptors).
Additionally, Neira discloses, selecting, from the plurality of search branches, the search branch with the largest number of associated node pairs as the search branch with the highest matching degree comprises: combining the current local topology map and the full topology map to construct a search interpretation tree (III. OBTAINING CONSISTENT HYPOTHESES, we require a search algorithm to traverse the interpretation tree in search for the hypothesis that includes the largest number of jointly compatible pairings. SC could be used to restrict the search to tree nodes representing hypotheses with jointly compatible pairings) … (IV Experiments, the quality of a node at level i, corresponding to a hypothesis Hi, can be defined as the number of non-null pairings that can be established from the node. In this way, nodes with quality lower than the best available hypothesis are not explored), wherein the search interpretation tree comprises the plurality of search branches (II. THE CLASSICAL NEAREST NEIGHBOR APPROACH, this exponential solution space can be represented as an interpretation tree of levels each node at level , called an -interpretation, provides an interpretation for the first measurements. each node has branches), and traversing each of the search branches (III. OBTAINING CONSISTENT HYPOTHES, the joint compatibility branch and bound (JCBB) algorithm proposed in this work traverses the interpretation tree in search of the hypothesis with the largest number of nonnull jointly compatible pairings); constituting a second-layer node using each node in the current local topology map; (II. THE CLASSICAL NEAREST NEIGHBOR APPROACH, this exponential solution space can be represented as an interpretation tree of levels; each node at level , called an -interpretation, provides an interpretation for the first measurements. Each node has branches, corresponding to each of the alternative interpretations for measurement Ei),) taking the second-layer node as a parent node, and constituting a third-layer node by taking each node in the full topology map as a child node of the second-layer node, (II. THE CLASSICAL NEAREST NEIGHBOR APPROACH, this exponential solution space can be represented as an interpretation tree of levels [2]; each node at level , called an -interpretation, provides an interpretation for the first measurements. Each node has branches, corresponding to each of the alternative interpretations for measurement (including the possibility that the measurement be Spurious), wherein the second-layer node and the third-layer node constitute a first node pair of the search interpretation tree (III. OBTAINING CONSISTENT HYPOTHESES, we require a search algorithm to traverse the interpretation tree in search for the hypothesis that includes the largest number of jointly compatible pairings. SC could be used to restrict the search to tree nodes representing hypotheses with jointly compatible pairings); wherein the fourth-layer node and the fifth-layer node constitute a second node pair of the search interpretation tree; (HYPOTHESES, we require a search algorithm to traverse the interpretation tree in search for the hypothesis that includes the largest number of jointly compatible pairings. SC could be used to restrict the search to tree nodes representing hypotheses with jointly compatible pairings); determining whether the first object type label corresponding to the node in the full topology map is the same as the second object type label corresponding to the node in the current local topology map in the second node pair according to a distance and an angle between two current local topology map nodes in the first node pair and the second node pair and a distance and an angle between two full topology map nodes in a same search branch, (I. INTRODUCTION, Baley et al. consider relative distances and angles between points and lines in two laser scans and use a graph theoretic approach to find the largest number of pairwise compatible pairings) … (III. OBTAINING CONSISTENT HYPOTHES, the joint compatibility branch and bound (JCBB) algorithm proposed in this work traverses the interpretation tree in search of the hypothesis with the largest number of nonnull jointly compatible pairings), and the degree of association is greater than the threshold, continuing to traverse the node of the current local topology map and the full topology map (B. Joint Compatibility Branch and Bound, we require a search algorithm to traverse the interpretation tree in search of the hypothesis that includes the largest number of jointly compatible pairings), counting a number of associated node pairs of each search branch, (B. Joint Compatibility Branch and Bound, the joint compatibility branch and bound (JCBB) algorithm proposed in this work traverses the interpretation tree in search of the hypothesis with the largest number of nonnull jointly compatible pairings. This monotonically nondecreasing criterion can be used to bound the search in the interpretation tree [2]), and determining the search branch with the largest number of associated node pairs as the search branch with the highest matching degree (B. Joint Compatibility Branch and Bound, the quality of a node at level , corresponding to a hypothesis, can be defined as the number of nonnull pairings that can be established from the node). However, Gawel, Neira, and Rosinol do not explicitly disclose, in response that the first object type label corresponding to the node in the full topology map is different from the second object type label corresponding to the node in the current local topology map in the first node pair, ending a construction of a corresponding search branch; in response that the first object type label corresponding to the node in the full topology map is the same as the second object type label corresponding to the node in the current local topology map in the first node pair, taking the third-layer node as the parent node, and constituting a fourth-layer node by taking all remaining nodes after removing nodes that appeared in an upstream branch of the search branch in the current local topology map as child nodes of the third-layer node; taking the fourth-layer node as the parent node, and constituting a fifth-layer node by taking all the remaining nodes in the full topology map after removing the nodes that appeared in the upstream branch of the search branch as child nodes of the fourth-layer node, and constituting a fifth-layer node by taking all the remaining nodes in the full topology map after removing the nodes that appeared in the upstream branch of the search branch as child nodes of the fourth-layer node in response that the first object type label corresponding to the node in the full topology map is different from the second object type label corresponding to the node in the current local topology map in the second node pair, or the degree of association is less than the threshold, ending the construction of the corresponding search branch; in response that the first object type label corresponding to the node in the full topology map is the same as the second object type label corresponding to the node in the current local topology map in the second node pair.
Nevertheless, De Lorenzi who is in the same field of endeavor of isomorphism between two graphs discloses, in response that the first object type label corresponding to the node in the full topology map is different from the second object type label corresponding to the node in the current local topology map in the first node pair, ending a construction of a corresponding search branch; in response that the first object type label corresponding to the node in the full topology map is the same as the second object type label corresponding to the node in the current local topology map in the first node pair, taking the third-layer node as the parent node (vf2_subgraph_iso, EdgeEquivalencePredicate and VertexEquivalencePredicate predicates are used to test whether edges and vertices are equivalent) … (vf2_subgraph_iso, if a pair of vertices (v, w) is feasible, the mapping is extended and the associated successor states' is computed. The whole procedure is then repeated for state’s'), and constituting a fourth-layer node by taking all remaining nodes after removing nodes that appeared in an upstream branch of the search branch in the current local topology map as child nodes of the third-layer node (vf2_subgraph_iso, each states of the matching process can be associated with a partial mapping M(s). At each level, the algorithm computes the set of the vertex pairs that are candidates to be added to the current states. If a pair of vertices (v, w) is feasible, the mapping is extended and the associated successor states' is computed. The whole procedure is then repeated for state’s'); taking the fourth-layer node as the parent node, and constituting a fifth-layer node by taking all the remaining nodes in the full topology map after removing the nodes that appeared in the upstream branch of the search branch as child nodes of the fourth-layer node, and constituting a fifth-layer node by taking all the remaining nodes in the full topology map after removing the nodes that appeared in the upstream branch of the search branch as child nodes of the fourth-layer node ((vf2_subgraph_iso, an isomorphism between two graphs G1=(V1, E1) and G2=(V2, E2) is a bijective mapping M of the vertices of one graph to vertices of the other graph)… (this function finds all induced subgraph isomorphisms between graphs graph_small and graph_large and outputs them to user_callback), in response that the first object type label corresponding to the node in the full topology map is different from the second object type label corresponding to the node in the current local topology map in the second node pair, or the degree of association is less than the threshold, ending the construction of the corresponding search branch (vf2_subgraph_iso, each states of the matching process can be associated with a partial mapping M(s). At each level, the algorithm computes the set of the vertex pairs that are candidates to be added to the current states. If a pair of vertices (v, w) is feasible, the mapping is extended and the associated successor states' is computed. The whole procedure is then repeated for state’s'); in response that the first object type label corresponding to the node in the full topology map is the same as the second object type label corresponding to the node in the current local topology map in the second node pair, (vf2_subgraph_iso, it can be described by means of a state space representation which is created by the algorithm while exploring the search graph in depth-first fashion. Each states of the matching process can be associated with a partial mapping M(s). At each level, the algorithm computes the set of the vertex pairs that are candidates to be added to the current state’s).
Regarding claim 13 Gawel, Neira, Rosinol, and De Lorenzi disclose the robot according to claim 12 as discussed supra. Additionally, Neira discloses, before selecting, from the plurality of search branches, the search branch with the largest number of associated node pairs as the search branch with the highest matching degree, the method further comprises combining the current local topology map and the full topology map to construct the search interpretation tree (III. OBTAINING CONSISTENT HYPOTHESES, we require a search algorithm to traverse the interpretation tree in search for the hypothesis that includes the largest number of jointly compatible pairings. SC could be used to restrict the search to tree nodes representing hypotheses with jointly compatible pairings) … (IV Experiments, the quality of a node at level i, corresponding to a hypothesis Hi, can be defined as the number of non-null pairings that can be established from the node. In this way, nodes with quality lower than the best available hypothesis are not explored); taking each node in the current local topology map as the second-layer node; taking the second-layer node as the parent node, and constructing the third-layer node by taking each node in the full topology map as child nodes of the second-layer node (II. THE CLASSICAL NEAREST NEIGHBOR APPROACH, this exponential solution space can be represented as an interpretation tree of levels [2]; each node at level , called an interpretation, provides an interpretation for the first measurements. Each node has branches, corresponding to each of the alternative interpretations for measurement (including the possibility that the measurement be Spurious); and by analogy, continuing to traverse the nodes of the current local topology map and the full topology map to construct the search interpretation tree (B. Joint Compatibility Branch and Bound, we require a search algorithm to traverse the interpretation tree in search of the hypothesis that includes the largest number of jointly compatible pairings).
Additionally, De Lorenzi discloses, taking the third-layer node as the parent node, and constructing the fourth-layer node by taking all the remaining nodes after removing the nodes that appeared in the upstream branch of the search branch in the current local topology map as child nodes of the third-layer node (vf2_subgraph_iso, EdgeEquivalencePredicate and VertexEquivalencePredicate predicates are used to test whether edges and vertices are equivalent) … (vf2_subgraph_iso, if a pair of vertices (v, w) is feasible, the mapping is extended and the associated successor states' is computed. The whole procedure is then repeated for state’s'); taking the fourth-layer node as the parent node, and constructing the fifth-layer node by taking all remaining nodes after removing the nodes that appeared in the upstream branch of the search branch in the full topology map as the child nodes of the fourth-layer node (vf2_subgraph_iso, an isomorphism between two graphs G1=(V1, E1) and G2=(V2, E2) is a bijective mapping M of the vertices of one graph to vertices of the other graph) … (this function finds all induced subgraph isomorphisms between graphs graph_small and graph_large and outputs them to user_callback).
Regarding claim 14 Gawel, Neira, Rosinol, and De Lorenzi disclose the robot according to claim 13 as discussed supra. Additionally, Neira discloses, the search interpretation tree comprises the plurality of search branches, and selecting, from the plurality of search branches, the search branch with the largest number of associated node pairs as the search branch with the highest matching degree comprises: traversing each of the plurality of search branches; (B. Joint Compatibility Branch and Bound, we require a search algorithm to traverse the interpretation tree in search of the hypothesis that includes the largest number of jointly compatible pairings) and counting a number of associated node pairs of each matching branch, and determining the matching branch with the largest number of associated node pairs as the search branch with the highest matching degree (III. OBTAINING CONSISTENT HYPOTHESES, we require a search algorithm to traverse the interpretation tree in search for the hypothesis that includes the largest number of jointly compatible pairings. SC could be used to restrict the search to tree nodes representing hypotheses with jointly compatible pairings) … (IV Experiments, the quality of a node at level i, corresponding to a hypothesis Hi, can be defined as the number of non-null pairings that can be established from the node. In this way, nodes with quality lower than the best available hypothesis are not explored).
Additionally, De Lorenzi discloses, in response that the search branch of the search interpretation tree comprising the associated node pair, determining the search branch as a matching branch; and in response that the search branch of the search interpretation tree not comprising the associated node pair, interrupting a search of the corresponding search branch (vf2_subgraph_iso, this function finds all induced subgraph isomorphisms between graphs graph_small and graph_large and outputs them to user_callback. It continues until user_callback returns false or the search space has been fully explored. vf2_subgraph_iso returns true if a graph-subgraph isomorphism exists and false otherwise).
Regarding claim 15, Gawel, Neira, Rosinol, and De Lorenzi disclose the robot according to claim 14 as discussed supra. Additionally, Gawel discloses, matching the nodes in the current local topology map and the nodes in the full topology map, wherein the matching comprises determining a degree of association of at least one node pair to be associated, which is constructed by the nodes in the current local topology map and the nodes in the full topology map” comprises: (D. Descriptor Matching, after both Gq and Gdb are created, we find associations between vertices in the query graph and the ones in the database graph by computing a similarity score between the corresponding graph descriptors) … (Figure 4, each line of the descriptor starts with the seed vertex label and continues with the class labels of the visited vertices) determining whether a first node of the current local topology map and a first node of the full topology map belong to a same object type label (III. X-VIEW, we extract blobs of connected regions, i.e., regions of the same class label lj in each image. Since semantically segmented images often show noisy partitioning of the observed scene (holes, disconnected edges and invalid labels on edges)), in response that the first node of the current local topology map and the first node of the full topology map belong to the same object type label, determining whether a second node of the current local topology map and a second node of the full topology map belong to the same object type label, (D. Descriptor Matching, between vertices in the query graph and the ones in the database graph by computing a similarity score between the corresponding graph descriptors. The similarity measure is computed by matching each row of the semantic descriptor of the query vertex to the descriptor of the database vertex), and in response that the second node of the current local topology map and the second node of the full topology map belong to the same object type label, (Fig. 4, each line of the descriptor starts with the seed vertex label and continues with the class labels of the visited vertices), comparing a distance and an angle between the first node of the current local topology map and the second node of the current local topology map with a distance (D. Descriptor Matching, after both Gq and Gdb are created, we find associations between vertices in the query graph and the ones in the database graph by computing a similarity score between the corresponding graph descriptors) and obtaining the degree of association of the node pair to be associated constructed by the first node pair and the second node pair (D. Descriptor Matching, after both Gq and Gdb are created, we find associations between vertices in the query graph and the ones in the database … The number of identical random walks on the two descriptors reflects the similarity score s, which is normalized between 0 and 1).
Additionally, Neira discloses, wherein the second node of the current local topology map and the second node of the full topology map construct a second node pair (II. THE CLASSICAL NEAREST NEIGHBOR APPROACH, the purpose of a data association algorithm is to generate a hypothesis that pairs each measurement with a map feature (when , the measurement is considered spurious). This exponential solution space can be represented as an interpretation tree of levels), and an angle between the first node of the full topology map and the second node of the full topology map, (I. INTRODUCTION, in other approaches, geometric constraints between features are used to obtain hypotheses with pairwise compatible pairings. Baley et al. [16] consider relative distances and angles between points and lines in two laser scans and use a graph theoretic approach to find the largest number of pairwise compatible pairings), in response that the degree of association is greater than the threshold, determining the node pair to be associated as an associated node pair (B. Joint Compatibility Branch and Bound, we require a search algorithm to traverse the interpretation tree in search of the hypothesis that includes the largest number of jointly compatible pairings).
Additionally, De Lorenzi discloses the first node of the current local topology map and the first node of the full topology map construct a first node pair (vf2_subgraph_iso, each states of the matching process can be associated with a partial mapping M(s). At each level, the algorithm computes the set of the vertex pairs that are candidates to be added to the current states. If a pair of vertices (v, w) is feasible, the mapping is extended and the associated successor states' is computed. The whole procedure is then repeated for state’s').
Regarding claim 20, Gawel, Neira, and Rosinol disclose the non-transitory storage medium according to claim 19 as discussed supra. Additionally, Gawel discloses, determining whether the first object type label corresponding to the node in the full topology map is the same as the second object type label corresponding to the node in the current local topology map in the first node pair; (C.Descriptors, each vertex descriptor is an n × m matrix consisting of n random walks of depth m. Each of the random walks originates at the base vertex vj and stores the class labels of the visited vertices) … (D. Descriptor Matching, the number of identical random walks on the two descriptors reflects the similarity score s, w), determining whether the first object type label corresponding to the node in the full topology map is the same as the second object type label corresponding to the node in the current local topology map in the second node pair; (C. Descriptors, each vertex descriptor is an n × m matrix consisting of n random walks of depth m. Each of the random walks originates at the base vertex vj and stores the class labels of the visited vertices) … (D. Descriptor Matching, the number of identical random walks on the two descriptors reflects the similarity score s, w), and obtaining a degree of association of a node pair to be associated formed by the first node pair and the second node pair (D. Descriptor Matching, we find associations between vertices in the query graph and the ones in the database graph by computing a similarity score between the corresponding graph descriptors).
Additionally, Neira discloses, selecting, from the plurality of search branches, the search branch with the largest number of associated node pairs as the search branch with the highest matching degree comprises: combining the current local topology map and the full topology map to construct a search interpretation tree (III. OBTAINING CONSISTENT HYPOTHESES, we require a search algorithm to traverse the interpretation tree in search for the hypothesis that includes the largest number of jointly compatible pairings. SC could be used to restrict the search to tree nodes representing hypotheses with jointly compatible pairings) … (IV Experiments, the quality of a node at level i, corresponding to a hypothesis Hi, can be defined as the number of non-null pairings that can be established from the node. In this way, nodes with quality lower than the best available hypothesis are not explored), wherein the search interpretation tree comprises the plurality of search branches (II. THE CLASSICAL NEAREST NEIGHBOR APPROACH, this exponential solution space can be represented as an interpretation tree of levels each node at level , called an -interpretation, provides an interpretation for the first measurements. each node has branches), and traversing each of the search branches (III. OBTAINING CONSISTENT HYPOTHES, the joint compatibility branch and bound (JCBB) algorithm proposed in this work traverses the interpretation tree in search of the hypothesis with the largest number of nonnull jointly compatible pairings); constituting a second-layer node using each node in the current local topology map; (II. THE CLASSICAL NEAREST NEIGHBOR APPROACH, this exponential solution space can be represented as an interpretation tree of levels; each node at level , called an -interpretation, provides an interpretation for the first measurements. Each node has branches, corresponding to each of the alternative interpretations for measurement Ei),) taking the second-layer node as a parent node, and constituting a third-layer node by taking each node in the full topology map as a child node of the second-layer node, (II. THE CLASSICAL NEAREST NEIGHBOR APPROACH, this exponential solution space can be represented as an interpretation tree of levels [2]; each node at level , called an -interpretation, provides an interpretation for the first measurements. Each node has branches, corresponding to each of the alternative interpretations for measurement (including the possibility that the measurement be Spurious), wherein the second-layer node and the third-layer node constitute a first node pair of the search interpretation tree (III. OBTAINING CONSISTENT HYPOTHESES, we require a search algorithm to traverse the interpretation tree in search for the hypothesis that includes the largest number of jointly compatible pairings. SC could be used to restrict the search to tree nodes representing hypotheses with jointly compatible pairings); wherein the fourth-layer node and the fifth-layer node constitute a second node pair of the search interpretation tree; (HYPOTHESES, we require a search algorithm to traverse the interpretation tree in search for the hypothesis that includes the largest number of jointly compatible pairings. SC could be used to restrict the search to tree nodes representing hypotheses with jointly compatible pairings); determining whether the first object type label corresponding to the node in the full topology map is the same as the second object type label corresponding to the node in the current local topology map in the second node pair according to a distance and an angle between two current local topology map nodes in the first node pair and the second node pair and a distance and an angle between two full topology map nodes in a same search branch, (I. INTRODUCTION, Baley et al. consider relative distances and angles between points and lines in two laser scans and use a graph theoretic approach to find the largest number of pairwise compatible pairings) … (III. OBTAINING CONSISTENT HYPOTHES, the joint compatibility branch and bound (JCBB) algorithm proposed in this work traverses the interpretation tree in search of the hypothesis with the largest number of nonnull jointly compatible pairings), and the degree of association is greater than the threshold, continuing to traverse the node of the current local topology map and the full topology map (B. Joint Compatibility Branch and Bound, we require a search algorithm to traverse the interpretation tree in search of the hypothesis that includes the largest number of jointly compatible pairings), counting a number of associated node pairs of each search branch, (B. Joint Compatibility Branch and Bound, the joint compatibility branch and bound (JCBB) algorithm proposed in this work traverses the interpretation tree in search of the hypothesis with the largest number of nonnull jointly compatible pairings. This monotonically nondecreasing criterion can be used to bound the search in the interpretation tree [2]), and determining the search branch with the largest number of associated node pairs as the search branch with the highest matching degree (B. Joint Compatibility Branch and Bound, the quality of a node at level , corresponding to a hypothesis, can be defined as the number of nonnull pairings that can be established from the node). However, Gawel, Neira, and Rosinol do not explicitly disclose, in response that the first object type label corresponding to the node in the full topology map is different from the second object type label corresponding to the node in the current local topology map in the first node pair, ending a construction of a corresponding search branch; in response that the first object type label corresponding to the node in the full topology map is the same as the second object type label corresponding to the node in the current local topology map in the first node pair, taking the third-layer node as the parent node, and constituting a fourth-layer node by taking all remaining nodes after removing nodes that appeared in an upstream branch of the search branch in the current local topology map as child nodes of the third-layer node; taking the fourth-layer node as the parent node, and constituting a fifth-layer node by taking all the remaining nodes in the full topology map after removing the nodes that appeared in the upstream branch of the search branch as child nodes of the fourth-layer node, and constituting a fifth-layer node by taking all the remaining nodes in the full topology map after removing the nodes that appeared in the upstream branch of the search branch as child nodes of the fourth-layer node in response that the first object type label corresponding to the node in the full topology map is different from the second object type label corresponding to the node in the current local topology map in the second node pair, or the degree of association is less than the threshold, ending the construction of the corresponding search branch; in response that the first object type label corresponding to the node in the full topology map is the same as the second object type label corresponding to the node in the current local topology map in the second node pair.
Nevertheless, De Lorenzi who is in the same field of endeavor of isomorphism between two graphs discloses, in response that the first object type label corresponding to the node in the full topology map is different from the second object type label corresponding to the node in the current local topology map in the first node pair, ending a construction of a corresponding search branch; in response that the first object type label corresponding to the node in the full topology map is the same as the second object type label corresponding to the node in the current local topology map in the first node pair, taking the third-layer node as the parent node (vf2_subgraph_iso, EdgeEquivalencePredicate and VertexEquivalencePredicate predicates are used to test whether edges and vertices are equivalent) … (vf2_subgraph_iso, if a pair of vertices (v, w) is feasible, the mapping is extended and the associated successor states' is computed. The whole procedure is then repeated for state’s'), and constituting a fourth-layer node by taking all remaining nodes after removing nodes that appeared in an upstream branch of the search branch in the current local topology map as child nodes of the third-layer node (vf2_subgraph_iso, each states of the matching process can be associated with a partial mapping M(s). At each level, the algorithm computes the set of the vertex pairs that are candidates to be added to the current states. If a pair of vertices (v, w) is feasible, the mapping is extended and the associated successor states' is computed. The whole procedure is then repeated for state’s'); taking the fourth-layer node as the parent node, and constituting a fifth-layer node by taking all the remaining nodes in the full topology map after removing the nodes that appeared in the upstream branch of the search branch as child nodes of the fourth-layer node, and constituting a fifth-layer node by taking all the remaining nodes in the full topology map after removing the nodes that appeared in the upstream branch of the search branch as child nodes of the fourth-layer node ((vf2_subgraph_iso, an isomorphism between two graphs G1=(V1, E1) and G2=(V2, E2) is a bijective mapping M of the vertices of one graph to vertices of the other graph)… (this function finds all induced subgraph isomorphisms between graphs graph_small and graph_large and outputs them to user_callback), in response that the first object type label corresponding to the node in the full topology map is different from the second object type label corresponding to the node in the current local topology map in the second node pair, or the degree of association is less than the threshold, ending the construction of the corresponding search branch (vf2_subgraph_iso, each states of the matching process can be associated with a partial mapping M(s). At each level, the algorithm computes the set of the vertex pairs that are candidates to be added to the current states. If a pair of vertices (v, w) is feasible, the mapping is extended and the associated successor states' is computed. The whole procedure is then repeated for state’s'); in response that the first object type label corresponding to the node in the full topology map is the same as the second object type label corresponding to the node in the current local topology map in the second node pair, (vf2_subgraph_iso, it can be described by means of a state space representation which is created by the algorithm while exploring the search graph in depth-first fashion. Each states of the matching process can be associated with a partial mapping M(s). At each level, the algorithm computes the set of the vertex pairs that are candidates to be added to the current state’s).
Claims 8 and 16, are all rejected under 35 U.S.C. 103 as being unpatentable over Gawel et al. (X-View: Graph-Based Semantic Multi-View Localization) in view of Neira et al. (Data Association in Stochastic Mapping Using the Joint Compatibility Test), further in view of Rosinol et al. (Kimera: from SLAM to Spatial Perception with 3D Dynamic Scene Graphs), further in view of De Lorenzi et al. (vf2_subgraph_iso), further in view of Fernández et al., further in view of Bernreiter et al., further in view of Liu et al.
Regarding claim 8, Gawel, Neira, Rosinol, and De Lorenzi disclose the method according to claim 4 as discussed supra. Additionally, Neira discloses, calculating a first random walk feature of each object in the full topology map and a second random walk feature of each object in the current local topology map (C, in this work, we extract random walk descriptors for every node of the graph) … (D. Descriptor Matching, after both Gq and Gdb are created, we find associations between vertices in the query graph and the ones in the database … The number of identical random walks on the two descriptors reflects the similarity score s, which is normalized between 0 and 1).
Additionally, Rosinol discloses, before combining the current local topology map and the full topology map to construct the search interpretation tree, the method further comprises: calculating a size of the first bounding box of each object in the full topology map and a size of the second bounding box of each object in the current local topology map (3.6, from the segmented clusters, Kimera-Objects obtains a centroid of the object (from the vertices of the corresponding mesh), and assigns a canonical orientation) … (2, each node in our DSG includes spatial coordinates and shape or bounding-box information as attributes) … (3.5, we mark detections when the bounding box of the human approaches the boundary of the image or is too small (≤ 30 pixels in our tests) as incorrect).
Additionally, Fernández who is in the same field of endeavor of recognition with plane-based maps discloses, determining a node pair whose similarity in the topology node set is higher than a preset similarity, taking the node of the node pair in the full topology map as a central node, (I. INTRODUCTION, such subgraphs are defined by one reference plane together with their closest neighbors, up to a distance threshold (see figure 1)) … (III. PLACE RECOGNITION, the subgraphs are composed of those planes 1-connected with the one considered as reference (e.g. the subgraphs generated by P1 and P5 in figure 2)) and taking the central node and nodes within a preset range around the central node in the full topology map as a updated full topology map, (III. PLACE RECOGNITION, the problem addressed here is that of matching local neighborhoods of planes, represented as subgraphs in the PbMap. Concretely, as the PbMap grows and is populated with new planes, the current observed planes are used to define subgraphs (one per observed plane) that are to be matched with other ones previously acquired), and the updated full topology map being used to combine with the current local topology map to construct the search interpretation tree (II. PLANE-BASED MAP PBMAP, the graph connections of the observed planes are also updated calculating the minimum distance between them and their surrounding planes that are not connected yet (figure 3.d)).
One of ordinary skill in the art prior to the effective filing date of the given invention
would have been motivated to combine Gawel, Neira, Rosinol, De Lorenzi with Fernandez because it teaches picking a central reference plane and forming a local neighborhood up to a preset distance threshold then matching those subgraphs with an interpretation tree
Further justification for combining Gawel and Neira not only comes from the state of the art but from Neira (Conclusion, complementary techniques, applicable when there is no estimation of the vehicle location, will constitute further work).
Additionally, Bernreiter who is in the same field of endeavor of mapping for robust aata association discloses, counting a number of objects corresponding to the first object type label in the full topology map to determine a first rarity rate and counting a number of objects corresponding to the second object type label in the current local topology map to determine a second rarity rate (III. SEMANTIC LOCALIZATION, on a level of semantic classes we then calculate a term frequency-inverse document frequency (tf-idf) score, i.e where nic denotes the number of occurrences of class c in submap i, ni the total number of classes in i. Furthermore, N denotes the total number of submaps processed so far and nc represents the number of scenes within the submaps which included an object of type c); the first rarity rate, the second rarity rate (III. SEMANTIC LOCALIZATION, on a level of semantic classes we then calculate a term frequency-inverse document frequency (tf-idf) score, i.e where nic denotes the number of occurrences of class c in submap i, ni the total number of classes in i. Furthermore, N denotes the total number of submaps processed so far and nc represents the number of scenes within the submaps which include), calculating a similarity of a topology node set of the current local topology map and the topology node set, (III. SEMANTIC LOCALIZATION, the topology of a scene is represented by the Laplacian matrix which is calculated based on the spatial relationship between the semantic classes as well as their degrees in the scene. We compare the topologies of two scenes based on a normalized cross correlation (NCC) [32] score, SNCC),
One of ordinary skill in the art prior to the effective filing date of the given invention
would have been motivated to combine Gawel, Neira, Rosinol, De Lorenzi, and Fernandez with Bernreiter because Bernreiter counts class occurrences per local submap and across the database, a rarity prior, that can weigh Gawel’s random walk node pair similarity, while Neira supplies object nodes with semantic labels.
Further justification for combining Gawel and Neira not only comes from the state of the art but from Neira (Conclusion, complementary techniques, applicable when there is no estimation of the vehicle location, will constitute further work).
Additionally, Liu discloses a second random walk feature of each object in the current local topology map according to the size of the first bounding box, the size of the second bounding box (B. Graph Extraction, we choose a bounding sphere to represent each object as spheres hold the implicit property of being rotationally invariant. The size of the sphere (depicting the dimension of the object) is the distance of the furthest point away from the cluster center), the first random walk feature, and the second random walk feature (Fig. 2, random walk descriptors based on [14] are obtained for all nodes in the graphs. We match each query graph’s random walk descriptors with those of the global graph to find the best correspondences) … (D, once random walk descriptors are built for the global and query graph, we perform association between their nodes based on the number of identical random walk descriptors they share. This inherently means only objects of the same semantic class will be associated), wherein the topology node set comprises the first node of the full topology map and the second node of the current local topology map, (D, once random walk descriptors are built for the global and query graph, we perform association between their nodes based on the number of identical random walk descriptors they share), and the first object type label corresponding to the first node is the same as the second object type label corresponding to the second node (D, this inherently means only objects of the same semantic class will be associated).
One of ordinary skill in the art prior to the effective filing date of the given invention
would have been motivated to combine Gawel, Neira, Rosinol, De Lorenzi, Fernandez, and Bernreiter with Liu because it supplies the node level association mechanism that computes random walk descriptors. These outputs feeds into Neira’s interpretation tree search for selecting the best hypothesis for semantic labels and bounding boxes.
Further justification for combining Gawel and Neira not only comes from the state of the art but from Neira (Conclusion, complementary techniques, applicable when there is no estimation of the vehicle location, will constitute further work).
Regarding claim 16, Gawel, Neira, Rosinol, and De Lorenzi disclose the robot according to claim 12 as discussed supra. Additionally, Neira discloses, calculating a first random walk feature of each object in the full topology map and a second random walk feature of each object in the current local topology map (C, in this work, we extract random walk descriptors for every node of the graph) … (D. Descriptor Matching, after both Gq and Gdb are created, we find associations between vertices in the query graph and the ones in the database … The number of identical random walks on the two descriptors reflects the similarity score s, which is normalized between 0 and 1).
Additionally, Rosinol discloses, before combining the current local topology map and the full topology map to construct the search interpretation tree, the method further comprises: calculating a size of the first bounding box of each object in the full topology map and a size of the second bounding box of each object in the current local topology map (3.6, from the segmented clusters, Kimera-Objects obtains a centroid of the object (from the vertices of the corresponding mesh), and assigns a canonical orientation) … (2, each node in our DSG includes spatial coordinates and shape or bounding-box information as attributes) … (3.5, we mark detections when the bounding box of the human approaches the boundary of the image or is too small (≤ 30 pixels in our tests) as incorrect).
Additionally, Fernández who is in the same field of endeavor of recognition with plane-based maps discloses, determining a node pair whose similarity in the topology node set is higher than a preset similarity, taking the node of the node pair in the full topology map as a central node, (I. INTRODUCTION, such subgraphs are defined by one reference plane together with their closest neighbors, up to a distance threshold (see figure 1)) … (III. PLACE RECOGNITION, the subgraphs are composed of those planes 1-connected with the one considered as reference (e.g. the subgraphs generated by P1 and P5 in figure 2)) and taking the central node and nodes within a preset range around the central node in the full topology map as a updated full topology map, (III. PLACE RECOGNITION, the problem addressed here is that of matching local neighborhoods of planes, represented as subgraphs in the PbMap. Concretely, as the PbMap grows and is populated with new planes, the current observed planes are used to define subgraphs (one per observed plane) that are to be matched with other ones previously acquired), and the updated full topology map being used to combine with the current local topology map to construct the search interpretation tree (II. PLANE-BASED MAP PBMAP, the graph connections of the observed planes are also updated calculating the minimum distance between them and their surrounding planes that are not connected yet (figure 3.d)).
Additionally, Neira discloses, calculating a first random walk feature of each object in the full topology map and a second random walk feature of each object in the current local topology map (C, in this work, we extract random walk descriptors for every node of the graph) … (D. Descriptor Matching, after both Gq and Gdb are created, we find associations between vertices in the query graph and the ones in the database … The number of identical random walks on the two descriptors reflects the similarity score s, which is normalized between 0 and 1).
Additionally, Rosinol discloses, before combining the current local topology map and the full topology map to construct the search interpretation tree, the method further comprises: calculating a size of the first bounding box of each object in the full topology map and a size of the second bounding box of each object in the current local topology map (3.6, from the segmented clusters, Kimera-Objects obtains a centroid of the object (from the vertices of the corresponding mesh), and assigns a canonical orientation) … (2, each node in our DSG includes spatial coordinates and shape or bounding-box information as attributes) … (3.5, we mark detections when the bounding box of the human approaches the boundary of the image or is too small (≤ 30 pixels in our tests) as incorrect).
Additionally, Fernández who is in the same field of endeavor of recognition with plane-based maps discloses, determining a node pair whose similarity in the topology node set is higher than a preset similarity, taking the node of the node pair in the full topology map as a central node, (I. INTRODUCTION, such subgraphs are defined by one reference plane together with their closest neighbors, up to a distance threshold (see figure 1)) … (III. PLACE RECOGNITION, the subgraphs are composed of those planes 1-connected with the one considered as reference (e.g. the subgraphs generated by P1 and P5 in figure 2)) and taking the central node and nodes within a preset range around the central node in the full topology map as a updated full topology map, (III. PLACE RECOGNITION, the problem addressed here is that of matching local neighborhoods of planes, represented as subgraphs in the PbMap. Concretely, as the PbMap grows and is populated with new planes, the current observed planes are used to define subgraphs (one per observed plane) that are to be matched with other ones previously acquired), and the updated full topology map being used to combine with the current local topology map to construct the search interpretation tree (II. PLANE-BASED MAP PBMAP, the graph connections of the observed planes are also updated calculating the minimum distance between them and their surrounding planes that are not connected yet (figure 3.d)).
Additionally, Bernreiter who is in the same field of endeavor of mapping for robust aata association discloses, counting a number of objects corresponding to the first object type label in the full topology map to determine a first rarity rate and counting a number of objects corresponding to the second object type label in the current local topology map to determine a second rarity rate (III. SEMANTIC LOCALIZATION, on a level of semantic classes we then calculate a term frequency-inverse document frequency (tf-idf) score, i.e where nic denotes the number of occurrences of class c in submap i, ni the total number of classes in i. Furthermore, N denotes the total number of submaps processed so far and nc represents the number of scenes within the submaps which included an object of type c); the first rarity rate, the second rarity rate (III. SEMANTIC LOCALIZATION, on a level of semantic classes we then calculate a term frequency-inverse document frequency (tf-idf) score, i.e where nic denotes the number of occurrences of class c in submap i, ni the total number of classes in i. Furthermore, N denotes the total number of submaps processed so far and nc represents the number of scenes within the submaps which include), calculating a similarity of a topology node set of the current local topology map and the topology node set, (III. SEMANTIC LOCALIZATION, the topology of a scene is represented by the Laplacian matrix which is calculated based on the spatial relationship between the semantic classes as well as their degrees in the scene. We compare the topologies of two scenes based on a normalized cross correlation (NCC) [32] score, SNCC),
Additionally, Liu discloses, a second random walk feature of each object in the current local topology map according to the size of the first bounding box, the size of the second bounding box (B. Graph Extraction, we choose a bounding sphere to represent each object as spheres hold the implicit property of being rotationally invariant. The size of the sphere (depicting the dimension of the object) is the distance of the furthest point away from the cluster center), the first random walk feature, and the second random walk feature (Fig. 2, random walk descriptors based on [14] are obtained for all nodes in the graphs. We match each query graph’s random walk descriptors with those of the global graph to find the best correspondences) … (D, once random walk descriptors are built for the global and query graph, we perform association between their nodes based on the number of identical random walk descriptors they share. This inherently means only objects of the same semantic class will be associated), wherein the topology node set comprises the first node of the full topology map and the second node of the current local topology map, (D, once random walk descriptors are built for the global and query graph, we perform association between their nodes based on the number of identical random walk descriptors they share), and the first object type label corresponding to the first node is the same as the second object type label corresponding to the second node (D, this inherently means only objects of the same semantic class will be associated).
Conclusion
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to SHANE E DOUGLAS whose telephone number is (703)756-1417. The examiner can normally be reached Monday - Friday 7:30AM - 5:00PM.
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, Christian Chace can be reached on (571) 272-4190. 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.
/S.E.D./
Examiner, Art Unit 3665 /CHRISTIAN CHACE/Supervisory Patent Examiner, Art Unit 3665