US5522022A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Analyzing an image showing a node-link structure
Assignee: Xerox Corp
•
Filing: 1993-11-24
•
Granted: 1996-05-28
•
Expires: 2013-11-24
Abstract
Abstract Input image data define an input image set that shows a node-link structure, such as a directed graph, an undirected graph, a tree, a flow chart, a circuit diagram, or a state-transition diagram. The input image set can include one image showing the node-link structure or two images, one showing graphical features that are a subset of the nodes and the other an image of an overlay with editing marks that include the links and another subset of the nodes. The input image data are used to obtain likely node-link data indicating parts of the input image set that satisfy a constraint on nodes and parts that satisfy a constraint on links. The likely node-link data are used to obtain constrained node-link data indicating subsets of the likely nodes and links that satisfy a constraint on node-link structures. The likely node-link data can include data defining a likely node image showing parts that meet a node criterion and data defining a likely link image showing parts that meet a link criterion. The constrained node-link data can be obtained by iteratively applying a link nearness criterion to the likely nodes and a node nearness criterion to the likely links until stability is reached. The constrained node-link data can be used to obtain output image data defining an output image that includes a precisely formed version of the node-link structure or an edited version of an input image. Or the constrained node-link data can be used to provide control signals to a system.
Inventors
- 👤 Satyajit Rao
- 👤 James V. Mahoney
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 02:13
CPC Classifications
G; G06; G06V; G06V30/00; G06V30/40; G06V30/42; G06V30/422
Claims Analysis
Total Claims: 35
Claim 1
Independent Claim
153 words
A method comprising: obtaining input image data defining an input image set that shows an input node-link structure; the input image set showing a set of nodes that satisfy a constraint on nodes and a set of links that satisfy a constraint on links; the input node-link structure satisfying a constraint on node-link structures; using the input image data to obtain likely node-link data; the likely node-link data indicating a first set of parts of the input image set that satisfy the constraint on nodes and indicating a second set of parts of the input image set that satisfy the constraint on links; and using the likely node-link data to obtain constrained node-link data, the constrained node-link data indicating a subset of the first set of parts and indicating a subset of the second set of parts, the subsets of the first and second sets of parts satisfying the constraint on node-link structures.
Claim 2
Independent Claim
153 words
A method comprising: obtaining input image data defining an input image set that shows an input node-link structure; the input image set showing a set of nodes that satisfy a constraint on nodes and a set of links that satisfy a constraint on links; the input node-link structure satisfying a constraint on node-link structures; using the input image data to obtain likely node-link data; the likely node-link data indicating a first set of parts of the input image set that satisfy the constraint on nodes and indicating a second set of parts of the input image set that satisfy the constraint on links; and using the likely node-link data to obtain constrained node-link data, the constrained node-link data indicating a subset of the first set of parts and indicating a subset of the second set of parts, the subsets of the first and second sets of parts satisfying the constraint on node-link structures.
Claim 3
Dependent Claim
28 words
The method of claim 1 in which the input image set includes only one image, the one image showing all nodes and links in the input node-link structure.
Claim 4
Dependent Claim
40 words
The method of claim 1 in which the input image set includes first and second images, the first image showing a first subset of the set of nodes, the second image showing a second subset of the set of nodes.
Claim 5
Dependent Claim
67 words
The method of claim 3 in which the first image shows graphical features, each graphical feature being one of the first subset of the set of nodes; the second image showing an overlay with editing marks that can be superimposed on the first image to obtain the input node-link structure, the editing marks including the set of links and the second subset of the set of nodes.
Claim 6
Dependent Claim
17 words
The method of claim 1 in which the input image set shows a sketch made by hand.
Claim 7
Dependent Claim
122 words
The method of claim 1 in which the input image set includes pixels; the constraint on nodes including a node criterion; the constraint on links including a link criterion; the act of using the input image data to obtain likely node-link data comprising: obtaining likely node data; the likely node data defining a version of the input image set in which each pixel's value indicates whether the pixel is in a part of the input image set that meets the node criterion; and obtaining likely link data; the likely link data defining a version of the input image set in which each pixel's value indicates whether the pixel is in a part of the input image set that meets the link criterion.
Claim 8
Dependent Claim
24 words
The method of claim 6 in which the node criterion requires a connected component that encloses more pixels than are in the connected component.
Claim 9
Dependent Claim
24 words
The method of claim 6 in which the link criterion requires a connected component that encloses less pixels than are in the connected component.
Claim 10
Dependent Claim
32 words
The method of claim 6 in which the link criterion requires a connected component with a first end that meets a head criterion and a second end that meets a tail criterion.
Claim 11
Dependent Claim
251 words
The method of claim 1 in which the constraint on node-link structures includes a link nearness criterion and a node nearness criterion; the act of using the likely node-link data comprising a sequence of iterations, each iteration using starting node data and starting link data to obtain ending node data and ending link data; the sequence beginning with a first iteration and ending with a last iteration; the first iteration's starting node data indicating the first set of parts of the input image set; the first iteration's starting link data indicating the second set of parts of the input image set; the starting node data of each iteration after the first iteration being the ending node data of the preceding iteration; the starting link data of each iteration after the first iteration being the ending link data of the preceding iteration; the last iteration's ending node data and ending link data together being the constrained node-link data; each iteration comprising: using the iteration's starting node data and starting link data to obtain the iteration's ending node data; each iteration's ending node data indicating parts of the input image set that are indicated by the iteration's starting node data and that meet the link nearness criterion; and using the iteration's starting node data and starting link data to obtain the iteration's ending link data; each iteration's ending link data indicating parts of the input image set that are indicated by the iteration's starting link data and that meet a node nearness criterion.
Claim 12
Dependent Claim
50 words
The method of claim 10 in which the link nearness criterion requires a part of the input image set that is the nearest part of the input image set that meets the node criterion to an end of a part of the input image set that meets the link criterion.
Claim 13
Dependent Claim
52 words
The method of claim 10 in which the node nearness criterion requires a part of the input image set with a length that is greater than a distance from an end of the part of the input image set to a part of the input image set that meets the node criterion.
Claim 14
Dependent Claim
55 words
The method of claim 10 in which each iteration further comprises: using the iteration's starting node data, starting link data, ending node data, and ending link data to obtain stability data indicating whether a change occurred during the iteration; the stability data of the last iteration indicating that no change occurred during the last iteration.
Claim 15
Dependent Claim
26 words
The method of claim 1 in which the act of using the likely node-link data to obtain constrained node-link data comprises obtaining a list of nodes.
Claim 16
Dependent Claim
49 words
The method of claim 14 in which the act of using the likely node-link data to obtain constrained node-link data further comprises obtaining a list of links; each link in the list of links being defined as an ordered pair of nodes that are in the list of nodes.
Claim 17
Dependent Claim
38 words
The method of claim 1, further comprising: using the constrained node-link data to obtain output image data; the output image data defining an output image set that shows an output node-link structure similar to the input node-link structure.
Claim 18
Dependent Claim
30 words
The method of claim 1 in which the input node-link structure is a directed graph, an undirected graph, a tree, a flow chart, a circuit diagram, or a state-transition diagram.
Claim 19
Independent Claim
209 words
A method of operating a machine that includes: image input circuitry for obtaining data defining images as input; and a processor connected for receiving data defining images from the image input circuitry; the method comprising: operating the processor to receive input image data from the image input circuitry, the input image data defining an input image set that shows an input node-link structure; the input image set including an image showing a set of nodes that satisfy a constraint on nodes and a set of links that satisfy a constraint on links; the input node-link structure satisfying a constraint on node-link structures; operating the processor to use the input image data to obtain likely node-link data; the likely node-link data indicating a first set of parts of the input image set that satisfy the constraint on nodes and indicating a second set of parts of the input image set that satisfy the constraint on links; and operating the processor to use the likely node-link data to obtain constrained node-link data, the constrained node-link data indicating a subset of the first set of parts and indicating a subset of the second set of parts, the subsets of the first and second sets of parts satisfying the constraint on node-link structures.
Claim 20
Independent Claim
209 words
A method of operating a machine that includes: image input circuitry for obtaining data defining images as input; and a processor connected for receiving data defining images from the image input circuitry; the method comprising: operating the processor to receive input image data from the image input circuitry, the input image data defining an input image set that shows an input node-link structure; the input image set including an image showing a set of nodes that satisfy a constraint on nodes and a set of links that satisfy a constraint on links; the input node-link structure satisfying a constraint on node-link structures; operating the processor to use the input image data to obtain likely node-link data; the likely node-link data indicating a first set of parts of the input image set that satisfy the constraint on nodes and indicating a second set of parts of the input image set that satisfy the constraint on links; and operating the processor to use the likely node-link data to obtain constrained node-link data, the constrained node-link data indicating a subset of the first set of parts and indicating a subset of the second set of parts, the subsets of the first and second sets of parts satisfying the constraint on node-link structures.
Claim 21
Dependent Claim
44 words
The method of claim 18 in which the machine is connected for providing control signals to a system; the method further comprising: operating the processor to use the constrained node-link data to obtain a control signal; and providing the control signal to the system.
Claim 22
Dependent Claim
66 words
The method of claim 18 in which the machine further comprises image output circuitry for providing data defining images as output; the method further comprising: operating the processor to use the constrained node-link data to obtain output image data defining an output image that includes an output node-link structure similar to the input node-link structure; and providing the output image data to the image output circuitry.
Claim 23
Dependent Claim
227 words
A machine comprising: image input circuitry for obtaining data defining images as input; memory for storing data; and a processor connected for receiving data defining images from the image input circuitry and connected for accessing data stored in the memory; the data stored in the memory comprising instruction data indicating image processing instructions the processor can execute; the processor, in executing the image processing instructions: receiving input image data from the image input circuitry, the input image data defining an input image set that shows an input node-link structure; the input image set including a image showing a set of nodes that satisfy a constraint on nodes and a set of links that satisfy a constraint on links; the input node-link structure satisfying a constraint on node-link structures; using the input image data to obtain likely node-link data; the likely node-link data indicating a first set of parts of the input image set that satisfy the constraint on nodes and indicating a second set of parts of the input image set that satisfy the constraint on links; and using the likely node-link data to obtain constrained node-link data, the constrained node-link data indicating a subset of the first set of parts and indicating a subset of the second set of parts, the subsets of the first and second sets of parts satisfying the constraint on node-link structures.
Claim 24
Dependent Claim
227 words
A machine comprising: image input circuitry for obtaining data defining images as input; memory for storing data; and a processor connected for receiving data defining images from the image input circuitry and connected for accessing data stored in the memory; the data stored in the memory comprising instruction data indicating image processing instructions the processor can execute; the processor, in executing the image processing instructions: receiving input image data from the image input circuitry, the input image data defining an input image set that shows an input node-link structure; the input image set including a image showing a set of nodes that satisfy a constraint on nodes and a set of links that satisfy a constraint on links; the input node-link structure satisfying a constraint on node-link structures; using the input image data to obtain likely node-link data; the likely node-link data indicating a first set of parts of the input image set that satisfy the constraint on nodes and indicating a second set of parts of the input image set that satisfy the constraint on links; and using the likely node-link data to obtain constrained node-link data, the constrained node-link data indicating a subset of the first set of parts and indicating a subset of the second set of parts, the subsets of the first and second sets of parts satisfying the constraint on node-link structures.
Claim 25
Dependent Claim
17 words
The machine of claim 21 in which the input image circuitry is connected for receiving facsimile transmissions.
Claim 26
Dependent Claim
46 words
The machine of claim 21 in which the processor is further connected for providing control signals to a system; the processor further, in executing the image processing instructions: using the constrained node-link data to obtain a control signal; and providing the control signal to the system.
Claim 27
Dependent Claim
68 words
The machine of claim 21 in which the machine further comprises image output circuitry for providing data defining images as output; the processor further, in executing the image processing instructions: using the constrained node-link data to obtain output image data defining an output image set that includes an output node-link structure similar to the input node-link structure; and providing the output image data to the image output circuitry.
Claim 28
Dependent Claim
17 words
The machine of claim 24 in which the output image circuitry is connected for providing facsimile transmissions.
Claim 29
Dependent Claim
65 words
The machine of claim 21 in which the machine is an image processing server; the image processing server being connected to a network for receiving requests for image processing operations; the network including the image input circuitry; the instruction data further indicating request handling instructions the processor can execute; the processor, in executing the request handling instructions, determining whether to execute the image processing instructions.
Claim 30
Dependent Claim
13 words
The machine of claim 21 in which the machine is a fax server.
Claim 31
Dependent Claim
12 words
The machine of claim 21 in which the machine is a copier.
Claim 32
Independent Claim
393 words
A method comprising: obtaining input image data defining a set of images that shows an input node-link structure; the set of images showing a set of nodes that satisfy a constraint on nodes and a set of links that satisfy a constraint on links; the input node-link structure satisfying a constraint on node-link structures, the constraint on node-link structures including a link nearness criterion and a node nearness criterion; using the input image data to obtain probable node-link data; the probable node-link data indicating a first set of parts of the set of images that satisfy the constraint on nodes and indicating a second set of parts of the set of images that satisfy the constraint on links; and using the probable node-link data to obtain constrained node-link data by performing a sequence of iterations, the constrained node-link data indicating a subset of the first set of parts and indicating a subset of the second set of parts, the subsets of the first and second sets of parts satisfying the constraint on node-link structures; each iteration of the sequence using starting node data and starting link data to obtain ending node data and ending link data; the sequence beginning with a first iteration and ending with a last iteration; the first iteration's starting node data indicating the first set of parts of the set of images; the first iteration's starting link data indicating the second set of parts of the set of images; the starting node data of each iteration after the first iteration being the ending node data of the preceding iteration; the starting link data of each iteration after the first iteration being the ending link data of the preceding iteration; the last iteration's ending node data and ending link data together being the constrained node-link data; each iteration comprising: using the iteration's starting node data and starting link data to obtain the iteration's ending node data; each iteration's ending node data indicating parts of the set of images that are indicated by the iteration's starting node data and that meet the link nearness criterion; and using the iteration's starting node data and starting link data to obtain the iteration's ending link data; each iteration's ending link data indicating parts of the set of images that are indicated by the iteration's starting link data and that meet a node nearness criterion.
Claim 33
Independent Claim
393 words
A method comprising: obtaining input image data defining a set of images that shows an input node-link structure; the set of images showing a set of nodes that satisfy a constraint on nodes and a set of links that satisfy a constraint on links; the input node-link structure satisfying a constraint on node-link structures, the constraint on node-link structures including a link nearness criterion and a node nearness criterion; using the input image data to obtain probable node-link data; the probable node-link data indicating a first set of parts of the set of images that satisfy the constraint on nodes and indicating a second set of parts of the set of images that satisfy the constraint on links; and using the probable node-link data to obtain constrained node-link data by performing a sequence of iterations, the constrained node-link data indicating a subset of the first set of parts and indicating a subset of the second set of parts, the subsets of the first and second sets of parts satisfying the constraint on node-link structures; each iteration of the sequence using starting node data and starting link data to obtain ending node data and ending link data; the sequence beginning with a first iteration and ending with a last iteration; the first iteration's starting node data indicating the first set of parts of the set of images; the first iteration's starting link data indicating the second set of parts of the set of images; the starting node data of each iteration after the first iteration being the ending node data of the preceding iteration; the starting link data of each iteration after the first iteration being the ending link data of the preceding iteration; the last iteration's ending node data and ending link data together being the constrained node-link data; each iteration comprising: using the iteration's starting node data and starting link data to obtain the iteration's ending node data; each iteration's ending node data indicating parts of the set of images that are indicated by the iteration's starting node data and that meet the link nearness criterion; and using the iteration's starting node data and starting link data to obtain the iteration's ending link data; each iteration's ending link data indicating parts of the set of images that are indicated by the iteration's starting link data and that meet a node nearness criterion.
Claim 34
Independent Claim
184 words
A method comprising: obtaining input image data defining a set of images that shows an input node-link structure; the set of images showing a set of nodes that satisfy a constraint on nodes and a set of links that satisfy a constraint on links; the input node-link structure satisfying a constraint on node-link structures; using the input image data to obtain probable node-link data; the probable node-link data indicating a first set of parts of the set of images that satisfy the constraint on nodes and indicating a second set of parts of the set of images that satisfy the constraint on links; using the probable node-link data to obtain constrained node-link data, the constrained node-link data indicating a subset of the first set of parts and indicating a subset of the second set of parts, the subsets of the first and second sets of parts satisfying the constraint on node-link structures; and using the constrained node-link data to obtain output image data; the output image data defining an output image set that shows an output node-link structure similar to the input node-link structure.
Claim 35
Independent Claim
184 words
A method comprising: obtaining input image data defining a set of images that shows an input node-link structure; the set of images showing a set of nodes that satisfy a constraint on nodes and a set of links that satisfy a constraint on links; the input node-link structure satisfying a constraint on node-link structures; using the input image data to obtain probable node-link data; the probable node-link data indicating a first set of parts of the set of images that satisfy the constraint on nodes and indicating a second set of parts of the set of images that satisfy the constraint on links; using the probable node-link data to obtain constrained node-link data, the constrained node-link data indicating a subset of the first set of parts and indicating a subset of the second set of parts, the subsets of the first and second sets of parts satisfying the constraint on node-link structures; and using the constrained node-link data to obtain output image data; the output image data defining an output image set that shows an output node-link structure similar to the input node-link structure.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-05-28 | 1999-11-27 | 2000-05-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-05-28 | 2003-11-27 | 2004-05-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-05-28 | 2007-11-27 | 2008-05-28 | $7700.00 | Window Closed / Lapsed |