Analyzing an image showing a node-link structure

• US 5,522,022 A
• Filed: 11/24/1993
• Issued: 05/28/1996
• Est. Priority Date: 11/24/1993
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Mahoney, James V., Rao, Satyajit
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US08/157,600
• Time in Patent Office: 916 Days
• Field of Search: 395/120, 395/124, 395/125-127, 395/129-132, 395/133, 395/140, 395/152, 395/155, 395/161, 395/700, 395/128, 382/254, 382/266
• US Class Current: 345/440
• CPC Class Codes: G06V 30/422 Technical drawings; Geographical maps

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. The method of claim 1 in which the input image set shows a sketch made by hand.

6. 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.

7. The method of claim 6 in which the node criterion requires a connected component that encloses more pixels than are in the connected component.

8. The method of claim 6 in which the link criterion requires a connected component that encloses less pixels than are in the connected component.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

21. 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.

22. The machine of claim 21 in which the input image circuitry is connected for receiving facsimile transmissions.

23. 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.

24. 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.

25. The machine of claim 24 in which the output image circuitry is connected for providing facsimile transmissions.

26. 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.

27. The machine of claim 21 in which the machine is a fax server.

28. The machine of claim 21 in which the machine is a copier.

29. 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.

30. 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.