DETAILED ACTION
This action is in response to the submission filed on 4/22/2025. Claims 1-19 are presented for examination.
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 .
Drawings
The drawings are objected to because Figures 2A and 2B are blurry and difficult to discern details. Corrected drawing sheets in compliance with 37 CFR 1.121(d) are required in reply to the Office action to avoid abandonment of the application. Any amended replacement drawing sheet should include all of the figures appearing on the immediate prior version of the sheet, even if only one figure is being amended. The figure or figure number of an amended drawing should not be labeled as “amended.” If a drawing figure is to be canceled, the appropriate figure must be removed from the replacement sheet, and where necessary, the remaining figures must be renumbered and appropriate changes made to the brief description of the several views of the drawings for consistency. Additional replacement sheets may be necessary to show the renumbering of the remaining figures. Each drawing sheet submitted after the filing date of an application must be labeled in the top margin as either “Replacement Sheet” or “New Sheet” pursuant to 37 CFR 1.121(d). If the changes are not accepted by the examiner, the applicant will be notified and informed of any required corrective action in the next Office action. The objection to the drawings will not be held in abeyance.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 5-6 and 14-18 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Claim 5 recites “The computer-implemented method according to any one of claim 1” which should be “according to claim 1”.
Claim 6 recites “whether an end point is located within a fifth predetermined vicinity or length”. However, claim 6 depends from 1, which does not recite any first, second, third, or fourth predetermined vicinity or length, rendering the claim unclear. For examination purpose, claim 6 is interpreted to be dependent on claim 5 which states the first, second, third, or fourth predetermined vicinity or length.
Claim 14 recites what appears to be a preamble but then continues directly into method steps. The preamble should include a phrase such as “wherein the method comprises…” or something similar.
Claim 16 recites “a graph convolutional (neural) network (GCN)”. It is unclear why ‘neural’ is in parentheses. Appropriate correction is required.
Claim 17 recites “one or more of accessibility objects and/or access points/connections/objects, and/or obstacles”. It is unclear why the term ‘and/or’ is used in addition to simple backlashes. It is unclear if the backslashes are intended to mean ‘and/or’, or merely ‘or’ in contrast to ‘and/or’.
Claims 15-18 are rejected by virtue of their dependency from independent claim 14.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-19 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. To determine if a claim is directed to patent ineligible subject matter, the Court has guided the Office to apply the Alice/Mayo test, which requires:
1. Determining if the claim falls within a statutory category;
2A. Determining if the claim is directed to a patent ineligible judicial exception consisting of a law of
nature, a natural phenomenon, or abstract idea; and
2B. If the claim is directed to a judicial exception, determining if the claim recites limitations or elements
that amount to significantly more than the judicial exception.(See MPEP 2106).
Step 1: With respect to claims 1-19, applying step 1, the preamble of independent claims 1, 14 and 19, claim a method, a method and an electronic data processing system. As such these claims fall within the statutory categories of process, process and machine.
Step 2A, prong one: In order to apply step 2A, a recitation of claim 1 is copied below. The limitations of the claim that describe an abstract idea are bolded.
A computer-implemented method of converting unstructured map data, the method comprising:
- obtaining unstructured map data according to a first data representation, the unstructured map data representing or comprising a number of geometric entities where the first data representation is a technical drawing representation or a CAD data representation, and
- converting the unstructured map data according to the first data representation to structured map data according to a second data representation, where the second data representation is a graph data representation (mental process/drawing with pen and paper –observation, evaluation, judgement, opinion).
The limitations as analyzed include concepts directed to the "mental process" groupings of abstract ideas performed in the human mind (including an observation, evaluation, judgment, opinion) (see MPEP § 2106.04(a)(2), subsection III). The claim involves converting map data to graph representation. The step is simple enough/broadly claimed that it could be performed mentally or with pen and paper and drawing the representations. Thus, limitations noted above also fall into the "mental process" groupings of abstract ideas.
Step 2A, prong two: Under step 2A prong two, this judicial exception is not integrated into a practical application because the additional claim limitations outside the abstract idea only present generic computing components and insignificant extra-solution activity. In particular, the claim recites the additional limitations: “A computer-implemented method of converting unstructured map data” (generic computing components merely carrying out the abstract idea - see MPEP § 2106.05(f) and (b)), “obtaining unstructured map data according to a first data representation, the unstructured map data representing or comprising a number of geometric entities where the first data representation is a technical drawing representation or a CAD data representation” (insignificant extra-solution activity - mere data gathering/output MPEP 2106.05(g)).
Accordingly, these additional elements do not integrate the abstract idea into a practical application because they do not impose any meaningful limits on practicing the abstract idea.
Step 2B: Moving on to step 2B of the analysis, the Examiner must consider whether each claim limitation individually or as an ordered combination amounts to significantly more than the abstract idea. This analysis includes determining whether an inventive concept is furnished by an element or a combination of elements that are beyond the judicial exception. For limitations that were categorized as "apply it" or generally linking the use of the abstract idea to a particular technological environment or field of use, the analysis is the same. The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception because the additional limitations is considered directed towards generic computer components carrying out the abstract idea and data gathering. See MPEP 2106.04(d) referencing MPEP 2106.05(h). Furthermore, as Berkheimer evidence that the claim elements “obtaining unstructured map data according to a first data representation, the unstructured map data representing or comprising a number of geometric entities where the first data representation is a technical drawing representation or a CAD data representation” are Well-Understood, Routine, and Conventional, MPEP § 2106.05(d) (II) provides support that mere data collecting and data outputting is well understood, routine, and conventional: "The courts have recognized the following computer functions as well- understood, routine, and conventional functions when they are claimed in a merely generic manner (e.g., at a high level of generality) or as insignificant extra- solution activity:
• Receiving or transmitting data over a network, e.g., using the Internet to gather
data, Symantec, 838 F.3d at 1321, 120 USPQ2d at 1362 (utilizing an intermediary
computer to forward information); TLI Communications LLC v. AV Auto. LLC, 823 F.3d
607, 610, 118 USPQ2d 1744, 1745 (Fed. Cir. 2016) (using a telephone for image
transmission); OIP Techs., Inc., v. Amazon.com, Inc., 788 F.3d 1359, 1363, 115 USPQ2d
1090, 1093 (Fed. Cir. 2015) (sending messages over a network); buySAFE, Inc. v. Google,
Inc., 765 F.3d 1350, 1355, 112 USPQ2d 1093, 1096 (Fed. Cir. 2014) (computer receives
and sends information over a network); but see DDR Holdings, LLC v. Hotels.com, L.P.,
773 F.3d 1245, 1258, 113 USPQ2d 1097, 1106 (Fed. Cir. 2014)
• Storing and retrieving information in memory, Versata Dev. Group, Inc. v. SAP
Am., Inc., 793 F.3d 1306, 1334, 115 USPQ2d 1681, 1701 (Fed. Cir. 2015); OIP Techs., 788
F.3d at 1363, 115 USPQ2d at 1092-93
• Presenting offers and gathering statistics, OIP Techs., 788 F.3d at 1362-63, 115
USPQ2d at 1092-93
For the foregoing reasons, claim 1 is directed to an abstract idea without significantly more, and is rejected as not patent eligible under 35 U.S.C. 101. The same conclusion is reached for the claims 2-19.
Claims 2-13 and 17 are further directed towards concepts directed to the "mental process" groupings of abstract ideas performed in the human mind (including an observation, evaluation, judgment, opinion) (see MPEP § 2106.04(a)(2), subsection III). The claim involves converting map data to graph representation. The step is simple enough/broadly claimed that it could be performed mentally or with pen and paper and drawing the representations. Thus, limitations noted above also fall into the "mental process" groupings of abstract ideas. Under step 2A prong two, this judicial exception is not integrated into a practical application because the additional claim limitations outside the abstract idea only present generic computing components. In particular, the claim recites the additional limitations: “The computer-implemented method” (generic computing components merely carrying out the abstract idea - see MPEP § 2106.05(f) and (b)). Accordingly, these additional elements do not integrate the abstract idea into a practical application because they do not impose any meaningful limits on practicing the abstract idea. The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception because the additional limitations is considered directed towards generic computer components carrying out the abstract idea.
Claims 14, 15, 16 and 18, are further directed towards concepts directed to the "mental process" groupings of abstract ideas performed in the human mind (including an observation, evaluation, judgment, opinion) (see MPEP § 2106.04(a)(2), subsection III). The claim involves converting map data to graph representation. The step is simple enough/broadly claimed that it could be performed mentally or with pen and paper and drawing the representations. Thus, limitations noted above also fall into the "mental process" groupings of abstract ideas. Under step 2A prong two, this judicial exception is not integrated into a practical application because the additional claim limitations outside the abstract idea only present generic computing components. In particular, the claim recites the additional limitations: “implementing a trained graph artificial intelligence or machine learning method or component or a trained graph neural network (GNN), to generate or output the detected or identified one or more objects”, “wherein the trained graph artificial intelligence or machine learning method or component is or implements a graph neural network (GNN)”, “wherein the trained graph neural network (GNN) is a graph convolutional (neural) network (GCN) node classification system” and “wherein the trained graph neural network (GNN) is a graph attention network (GAT)” (generic computing components merely carrying out the abstract idea - see MPEP § 2106.05(f) and (b)). Accordingly, these additional elements do not integrate the abstract idea into a practical application because they do not impose any meaningful limits on practicing the abstract idea. The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception because the additional limitations is considered directed towards generic computer components carrying out the abstract idea.
Claim 19 is further directed towards concepts directed to the "mental process" groupings of abstract ideas performed in the human mind (including an observation, evaluation, judgment, opinion) (see MPEP § 2106.04(a)(2), subsection III). The claim involves converting map data to graph representation. The step is simple enough/broadly claimed that it could be performed mentally or with pen and paper and drawing the representations. Thus, limitations noted above also fall into the "mental process" groupings of abstract ideas. Under step 2A prong two, this judicial exception is not integrated into a practical application because the additional claim limitations outside the abstract idea only present generic computing components. In particular, the claim recites the additional limitations: “An electronic data processing system, comprising: one or more processing units connected to an electronic memory, wherein the one or more processing units are programmed and configured to execute the computer- implemented method” (generic computing components merely carrying out the abstract idea - see MPEP § 2106.05(f) and (b)). Accordingly, these additional elements do not integrate the abstract idea into a practical application because they do not impose any meaningful limits on practicing the abstract idea. The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception because the additional limitations is considered directed towards generic computer components carrying out the abstract idea.
Claim Rejections - 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claims 1-3, 5, 11, 13, and 19 are rejected under 35 U.S.C. 102(a) as being anticipated by “System for line drawings interpretation” (“Boatto”).
Regarding claim 1, Boatto teaches:
A computer-implemented method of converting unstructured map data (Boatto: Abstract), the method comprising:
- obtaining unstructured map data according to a first data representation, the unstructured map data representing or comprising a number of geometric entities where the first data representation is a technical drawing representation or a CAD data representation (Boatto: Abstract, “'the line drawings that we analyze contain interconnected thin lines, (lashed lines, text, and symbols. Characters and symbols may overlap with lines”; Introduction, “The first and the third phase of the process are valid for any kind of line drawing, while the other phases require the knowledge of the drawing's semantics, and have to be adapted to process different categories of drawings. A system, based on this approach, has been developed for the processing of cadastral maps. These are drawn onto an AO format paper sheet and represent land and real properties, together with geographic information (fig. 1). They contain interconnected thin lines, (lashed lines, text, symbols and hatched areas. Characters and symbols may overlap with lines”), and
- converting the unstructured map data according to the first data representation to structured map data according to a second data representation, where the second data representation is a graph data representation (Boatto: Introduction, “the raster image is converted into a graph using suitable algorithms. The edges of this graph are the portions of the image which can be approximated with straight segments, while the vertices are the portions which identify the extremes or the intersection points of segments. The bitmap is stored for both edges and vertices portions”; Abstract, “extracts information from line drawings, in order to feed CAl) or GIS systems. 'the line drawings that we analyze contain interconnected thin lines, (lashed lines, text, and symbols. Characters and symbols may overlap with lines. Our approach is based on the properties of the run representation of a binary image that allow giving the image a graph structure. Using this graph structure, several algorithms have been designed to identify, directly in the raster image, straight segments, dashed lines, text, symbols, hatching lines, etc. Straight segments and dashed lines are converted into vectors, with high accuracy and good noise immunity”; 2. System Description, “Graph decomposition of the image”).
Regarding claim 2, Boatto teaches:
The computer-implemented method according to claim 1, wherein converting the unstructured map data according to the first data representation comprises:
- for at least a first geometric entity of the number of geometric entities, the first geometric entity comprising a number, or a plurality, of line segments, each line segment of the first geometric entity comprising two opposite end points, where an end point of a line segment may be shared or may be non-shared, respectively, with an end point of another line segment of the first geometric entity or of another of the number of geometric entities (Boatto: page 6, “'method used to identify buildings is based on the fact that a building is drawn as a hatched polygon. The graph of the image is scanned, searching for the typical hatching lines pattern, i.e. a segment intersected by some other segments each one parallel to the other”; Abstract, “Using this graph structure, several algorithms have been designed to identify, directly in the raster image, straight segments, dashed lines, text, symbols, hatching lines, etc. Straight segments and dashed lines are converted into vectors, with high accuracy and good noise immunity”),
o generating one node in the graph data representation for each non-shared end point,
o generating a single node in the graph data representation for each shared end point,
o generating one edge in the graph data representation for each line segment so that a
generated edge is connecting two generated nodes in the graph data representation that are generated for respective end points of a line segment that the edge is generated for (Boatto: page 3, “Nodes and edges the graph are associated to connected sets o I '5 of the binary image (in the following, the terms "node" and "edge" will also be used to mean the image pieces associated to the elements of the graph”; Figure 4, “An example of mixed graph representation. Edges, shown in black consist of connected set of vertical or horizontal runs (depending on the slope of the line portion). Nodes, shown in grey, consist of connected sets of vertical runs and sub-runs”; page 3, “graph representation is especially convenient for line-like images, since it disassembles the line structure into "edges" and "nodes" which formalize the intuitive notions of "line" and "crossing point between lines"”).
Regarding claim 3, Boatto teaches:
The computer-implemented method according to claim 1, wherein the computer-implemented method further comprises
- for at least one, some, or all geometric entities of the number of geometric entities that comprises at least a circular segment and/or one or more other non-line segments, converting or replacing such geometric entities to or by an approximating line segment version before or when converting such geometric entities to the graph data representation (Boatto: Introduction, “the raster image is converted into a graph using suitable algorithms. The edges of this graph are the portions of the image which can be approximated with straight segments, while the vertices are the portions which identify the extremes or the intersection points of segments. The bitmap is stored for both edges and vertices portions”; Abstract, “extracts information from line drawings, in order to feed CAl) or GIS systems. The line drawings that we analyze contain interconnected thin lines, (lashed lines, text, and symbols. Characters and symbols may overlap with lines. Our approach is based on the properties of the run representation of a binary image that allow giving the image a graph structure. Using this graph structure, several algorithms have been designed to identify, directly in the raster image, straight segments, dashed lines, text, symbols, hatching lines, etc. Straight segments and dashed lines are converted into vectors, with high accuracy and good noise immunity”; 2. System Description, “Graph decomposition of the image”).
Regarding claim 5, Boatto teaches:
The computer-implemented method according to any one of claim 1, wherein the computer-implemented method further comprises
- determining a plurality of end points of line segments of the first data representation that are within a first predetermined vicinity or length of each other or of a single one of the plurality of end points, and
- replacing the determined plurality of end points within the first predetermined vicinity or length of each other or of a single one of the plurality of end points by a single end point retaining or having the line segments of the determined plurality of nodes,
and/or
- determining an end point of the first data representation, among end points of two line segments, that is located within a second predetermined vicinity or length of at least one of the two line segments, and
- replacing the determined end point by a new single end point on one or both of the line segments at the location where the two line segments intersect or, if not intersecting, would intersect if at least one of the two line segments is extended until the two line segments intersect,
and/or
- determining an end point of the first data representation, connected with only a single other end point and being located within a third predetermined vicinity or length of a further other end point, and - connecting the determined end point with the further other end point by a new line segment (Boatto: Figure 4, “An example of mixed graph representation. Edges, shown in black consist of connected set of vertical or horizontal runs (depending on the slope of the line portion). Nodes, shown in grey, consist of connected sets of vertical runs and sub-runs”),
and/or
- determining two at least substantially parallel line segments of the first data representation that at least partly overlaps in their length direction and are distanced apart by less than a fourth predetermined vicinity or length in a direction substantially perpendicular to the length direction of the at least two substantially parallel line segments, and
- replacing the two at least substantially parallel line segments with a single line segment comprising the combined end points of the replaced two at least substantially parallel line segments.
Regarding claim 11, Boatto teaches:
The computer-implemented method according claim 1, wherein the first data representation is a layered or a non-layered two-dimensional or three-dimensional drawing data representation and/or the first data representation comprises data representing a drawing of a building or at least a part thereof (Boatto: Abstract, “'the line drawings that we analyze contain interconnected thin lines, (lashed lines, text, and symbols. Characters and symbols may overlap with lines”; Introduction, “The first and the third phase of the process are valid for any kind of line drawing, while the other phases require the knowledge of the drawing's semantics, and have to be adapted to process different categories of drawings. A system, based on this approach, has been developed for the processing of cadastral maps. These are drawn onto an AO format paper sheet and represent land and real properties, together with geographic information (fig. 1). They contain interconnected thin lines, (lashed lines, text, symbols and hatched areas. Characters and symbols may overlap with lines”; 2.4. Building recognition).
Regarding claim 13, Boatto teaches:
The computer-implemented method according claim 1, wherein each geometric entity of the number of geometric entities is not connected to another geometric entity of the number of geometric entities (Boatto: 2.4. “Building recognition”, “In a cadastral map, buildings are represented by hatched polygons, often containing numbers and dashed lines. A cadastral map representing a city usually contains several buildings and a large number of hatching lines inside them. Hatching lines inside polygons just mean that those polygons represent buildings and should not he vectorized”).
Regarding claim 19, Boatto teaches:
An electronic data processing system, comprising: one or more processing units connected to an electronic memory, wherein the one or more processing units are programmed and configured to execute the computer- implemented method according to claim 1 (Boatto: page 9, “Configuration and Performance”) and/or to execute the computer- implemented method according to claim 14.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claims 4, 7-10, and 14-18 are rejected under 35 U.S.C. 103 as being unpatentable over “System for line drawings interpretation” (“Boatto”) in view of “Improved Graph Neural Networks for Spatial Networks Using Structure-Aware Sampling” (“Iddianozie”).
Regarding claim 4, Boatto does not teach but Iddianozie does teach:
The computer-implemented method according to claim 2, wherein the computer-implemented method further comprises
- assigning a weight for at least one edge, the weight for an edge corresponding to a length value of a line segment that the edge is or was generated for (Iddianozie: page 7, “a is a weight vector”).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have combined Boatto (directed to converting images to graph representations) and Iddianozie (directed to assigning a weight) and arrived at converting images to graph representations using weight assignment. One of ordinary skill in the art would have been motivated to make such a combination because “Graph Neural Networks (GNNs) have received wide acclaim in recent times due to their performance on inference tasks for unstructured data” (Iddianozie: Abstract).
Regarding claim 7, Boatto does not teach but Iddianozie does teach:
The computer-implemented method according to claim 1, wherein the computer-implemented method further comprises
- assigning a value for each of a number of predetermined features for each node of the graph data representation, wherein each of the predetermined features characterises an aspect of the node in question and its context (Iddianozie: “Table 3. OpenStreetMap (OSM) descriptive tags used to attribute the graph nodes”, “Tag Type”, “Tag Value”).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have combined Boatto (directed to converting images to graph representations) and Iddianozie (directed to node identification) and arrived at converting images to graph representations using node identification. One of ordinary skill in the art would have been motivated to make such a combination because “Graph Neural Networks (GNNs) have received wide acclaim in recent times due to their performance on inference tasks for unstructured data” (Iddianozie: Abstract).
Regarding claim 8, Boatto does not teach but Iddianozie does teach:
The computer-implemented method according to claim 7, wherein the values of the predetermined features are provided to an input part or input layer of a graph neural network, or a graph convolutional neural network, for subsequent data processing(Iddianozie: page 2, “we study GNNs for node classification on street networks. Specifically, we seek to investigate the relationship between two pertinent characteristics of spatial networks to GNNs”; Figure 1, “A description of our proposed methodology for the transductive learning case. We perform node sampling using the global structure of the graph. The input to the Graph Neural Network (GNN) is a partially labelled input graph. The global graph structure and node attributes are used to train our network. The output graph is fully labelled, where the colours of the node denote class membership”).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have combined Boatto (directed to converting images to graph representations) and Iddianozie (directed to a graph neural network) and arrived at converting images to graph representations using a graph neural network. One of ordinary skill in the art would have been motivated to make such a combination because “Graph Neural Networks (GNNs) have received wide acclaim in recent times due to their performance on inference tasks for unstructured data” (Iddianozie: Abstract).
Regarding claim 9, Boatto does not teach but Iddianozie does teach:
The computer-implemented method according to claim 7, wherein the predetermined features for a particular node comprises one or more selected from the group of:
- a minimum length of edge(s) connected to the particular node,
- a maximum length of edge(s) connected to the particular node,
- indication of which angle group(s), if any, of a plurality of different angle groups, the particular node is determined to belong to,
- for each angle group, a number of occurrences that the particular node is determined to belong to a respective angle group,
- a number of one or more neighbouring nodes determined to be orthogonal to each other as seen from the particular node,
- a circle probability representing a probability of the particular node being determined to be part of a circle,
- an indication of whether the particular node is determined to be part of a circle or not,
- an indication of whether the particular node is determined to be part of a half circle,
- an indication of whether the particular node is determined to be part of a quarter circle,
- an indication of whether the particular node is determined to be part of an angle group representing a corner,
- a shortest Euclidean distance or length between the particular node and a node determined to belong to an angle group representing a quarter circle,
- a shortest topological graph distance or length between the particular node and a node determined to belong to the angle group representing a quarter circle,
- a shortest topological graph distance or length between the particular node and a node determined to belong to an angle group representing a half-circle,
- a shortest Euclidean distance or length between the particular node and a node determined to belong to the angle group representing a half-circle, and
- an identifier or indication of which type of geometric entity the particular node arises from (Iddianozie: “Table 3. OpenStreetMap (OSM) descriptive tags used to attribute the graph nodes”, “Tag Type”, “Tag Value”).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have combined Boatto (directed to converting images to graph representations) and Iddianozie (directed to node identification) and arrived at converting images to graph representations using node identification. One of ordinary skill in the art would have been motivated to make such a combination because “Graph Neural Networks (GNNs) have received wide acclaim in recent times due to their performance on inference tasks for unstructured data” (Iddianozie: Abstract).
Regarding claim 10, Boatto does not teach but Iddianozie does teach:
The computer-implemented method according to claim 1, wherein the nodes of the graph data representation are non-ordered, the graph data representation is undirected (Iddianozie: Table 1, “G = (V, E) An undirected spatial graph”), and/or the graph data representation is a non-connected graph representation.
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have combined Boatto (directed to converting images to graph representations) and Iddianozie (directed to undirected graph data) and arrived at converting images to graph representations using an undirected graph data. One of ordinary skill in the art would have been motivated to make such a combination because “Graph Neural Networks (GNNs) have received wide acclaim in recent times due to their performance on inference tasks for unstructured data” (Iddianozie: Abstract).
Regarding claim 14, Boatto teaches:
A computer-implemented method of detecting or predicting a presence of at least one object in unstructured map data according to a first data representation, the unstructured map data representing or comprising a number of geometric entities, wherein the first data representation is a technical drawing representation or a CAD data representation and one or more of the number of geometric entities represents or defines an object to be detected or to have its presence predicted (Boatto: Abstract, “'the line drawings that we analyze contain interconnected thin lines, (lashed lines, text, and symbols. Characters and symbols may overlap with lines”; Introduction, “The first and the third phase of the process are valid for any kind of line drawing, while the other phases require the knowledge of the drawing's semantics, and have to be adapted to process different categories of drawings. A system, based on this approach, has been developed for the processing of cadastral maps. These are drawn onto an AO format paper sheet and represent land and real properties, together with geographic information (fig. 1). They contain interconnected thin lines, (lashed lines, text, symbols and hatched areas. Characters and symbols may overlap with lines”),
- converting the unstructured map data according to the first data representation to structured map data according to a second data representation, or according to the method according to claim 1, where the second data representation is a graph data representation (Boatto: Introduction, “the raster image is converted into a graph using suitable algorithms. The edges of this graph are the portions of the image which can be approximated with straight segments, while the vertices are the portions which identify the extremes or the intersection points of segments. The bitmap is stored for both edges and vertices portions”; Abstract, “extracts information from line drawings, in order to feed CAl) or GIS systems. 'the line drawings that we analyze contain interconnected thin lines, (lashed lines, text, and symbols. Characters and symbols may overlap with lines. Our approach is based on the properties of the run representation of a binary image that allow giving the image a graph structure. Using this graph structure, several algorithms have been designed to identify, directly in the raster image, straight segments, dashed lines, text, symbols, hatching lines, etc. Straight segments and dashed lines are converted into vectors, with high accuracy and good noise immunity”; 2. System Description, “Graph decomposition of the image”),
Boatto does not teach but Iddianozie does teach:
- detecting or identifying one or more objects in the structured map data according to the second data representation in response to providing the structured map data according to the second data representation to a computer program or routine implementing a trained graph artificial intelligence or machine learning method or component, or a trained graph neural network (GNN), to generate or output the detected or identified one or more objects (Iddianozie: page 2, “we study GNNs for node classification on street networks. Specifically, we seek to investigate the relationship between two pertinent characteristics of spatial networks to GNNs”; Figure 1, “A description of our proposed methodology for the transductive learning case. We perform node sampling using the global structure of the graph. The input to the Graph Neural Network (GNN) is a partially labelled input graph. The global graph structure and node attributes are used to train our network. The output graph is fully labelled, where the colours of the node denote class membership”).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have combined Boatto (directed to converting images to graph representations) and Iddianozie (directed to a graph neural network) and arrived at converting images to graph representations using a graph neural network. One of ordinary skill in the art would have been motivated to make such a combination because “Graph Neural Networks (GNNs) have received wide acclaim in recent times due to their performance on inference tasks for unstructured data” (Iddianozie: Abstract).
Regarding claim 15, Boatto does not teach but Iddianozie does teach:
The computer-implemented method according to claim 14, wherein the trained graph artificial intelligence or machine learning method or component is or implements a graph neural network (GNN) (Iddianozie: page 2, “we study GNNs for node classification on street networks. Specifically, we seek to investigate the relationship between two pertinent characteristics of spatial networks to GNNs”).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have combined Boatto (directed to converting images to graph representations) and Iddianozie (directed to a graph neural network) and arrived at converting images to graph representations using a graph neural network. One of ordinary skill in the art would have been motivated to make such a combination because “Graph Neural Networks (GNNs) have received wide acclaim in recent times due to their performance on inference tasks for unstructured data” (Iddianozie: Abstract).
Regarding claim 16, Boatto does not teach but Iddianozie does teach:
The computer-implemented method according to claim 14, wherein the trained graph neural network (GNN) is a graph convolutional (neural) network (GCN) node classification system (Iddianozie: Table 5, “Summary of results for the Graph Convolutional Networks (GCN)”).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have combined Boatto (directed to converting images to graph representations) and Iddianozie (directed to a graph convolutional neural network) and arrived at converting images to graph representations using a graph convolutional neural network. One of ordinary skill in the art would have been motivated to make such a combination because of “their performance on inference tasks for unstructured data” (Iddianozie: Abstract).
Regarding claim 17, Boatto and Iddianozie teach:
The computer-implemented method according to claim 14, wherein the one or more objects being detected or identified in the structured map data according to the second data representation is one or more of accessibility objects and/or access
points/connections/objects (Boatto: page 8, “the high-level entities of the map, corresponding to the various cadastral entities (such as parcels, streets, rivers, etc)”; streets are access connections), and/or obstacles.
Regarding claim 18, Boatto does not teach but Iddianozie does teach:
The computer-implemented method according to claim 14, wherein the trained graph neural network (GNN) is a graph attention network (GAT) (Iddianozie: page 5, “a method called SAS-GAT: Structure-Aware Sampling-Graph Attention Networks. We use this network to train a model for node classification on street networks, where the nodes denotes the street segments and the model learns a function to predict their class.”).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have combined Boatto (directed to converting images to graph representations) and Iddianozie (directed to a graph attention network) and arrived at converting images to graph representations using a graph attention network. One of ordinary skill in the art would have been motivated to make such a combination because of “their performance on inference tasks for unstructured data” (Iddianozie: Abstract).
Claim 12 is rejected under 35 U.S.C. 103 as being unpatentable over “System for line drawings interpretation” (“Boatto”) in view of ---“Framework for Indoor Elements Classification via Inductive Learning on Floor Plan Graphs” (“Song”).
Regarding claim 12, Boatto does not teach but Song does teach:
The computer-implemented method according claim 1, wherein the unstructured map data is or comprises unstructured indoor map data and/or is or comprises unstructured indoor floor plan data (Song: Abstract, “we first convert the input floor plan image into vector data and utilize a graph neural network.”).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have combined Boatto (directed to converting images to graph representations) and Song (directed to indoor floor plan data) and arrived at converting indoor floor plan data to graph representation. One of ordinary skill in the art would have been motivated to make such a combination “to capture different types of indoor elements including basic elements, such as walls, doors, and symbols, as well as spatial elements, such as rooms and corridors. In addition, the proposed method can also detect element shapes. Experimental results show that our framework can classify indoor elements with an F1 score of 95%, with scale and rotation invariance” (Song: Abstract).
Allowable Subject Matter
Claim 6 contains allowable subject matter.
Dependent claim 6 will be allowed if the rejections under 35 USC 112 and 101 are overcome, and incorporates all of the limitations of the independent claim 1.
The independent claims will be in condition for allowance when the allowable dependent claim(s) are incorporated into the independent claims, in addition to overcoming the 35 USC 112 and 101 rejections.
Boatto, Iddianozie and Song teach a method for converting image data to graph representation. However, these references and the remaining prior art of record, alone or in combination, fails to disclose or suggest
(claim 6)
“- determining a position or set of coordinates of where two line segments of the number of geometric entities of the first data representation intersect, and
- determining whether an end point is located within a fifth predetermined vicinity or length of the determined position or set of coordinates, and if so then replacing the line segment for each of the two intersecting line segments with two line segments and connecting respective line segments to the end point determined to be within the fifth predetermined vicinity or length of the determined position or set of coordinates”,
in combination with the remaining elements and features of the claimed invention. It is for these reasons that the applicant’s invention defines over the prior art of record.
Additional References Cited
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure and are cited in the attached PTOL-892.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to NITHYA J. MOLL whose telephone number is (571)270-1003. The examiner can normally be reached Monday-Friday 10am-6pm EST.
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, Rehana Perveen can be reached at 571-272-3676. 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.
/NITHYA J. MOLL/Primary Examiner, Art Unit 2189