Method for dynamically maintaining multiple structural interpretations in graphics system

• US 5,553,224 A
• Filed: 08/04/1993
• Issued: 09/03/1996
• Est. Priority Date: 08/04/1993
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Saund, Eric, Moran, Thomas P., Becker, Craig D.
• Primary Examiner(s): Bayerl, Raymond J.
• Assistant Examiner(s): DELA TORRE, CRESCELLE N
• Application Number:
  US08/101,646
• Time in Patent Office: 1,126 Days
• Field of Search: 395/155, 395/161, 395/159, 395/156, 395/133, 395/134, 395/141, 395/142, 395/143, 382/9, 382/22, 382/25
• US Class Current: 345/619
• CPC Class Codes: G06T 11/00 2D [Two Dimensional] image generation

Abstract

A graphical input and display system for creating and manipulating an abstract graphical image by decomposing it into abstract elemental objects and organizing the elemental objects into a set of perceptually coherent composite objects. The system includes an input device for entering the graphical image, such as a mouse or digitizer and electronic stylus, a display, and a function selection system for manipulating the graphical image. The system decomposes the graphical image entered onto the display into abstract elemental objects each consisting of one or more consecutive "on" pixels within the image. The system organizes the elemental objects into composite objects, which are abstract groups of elemental objects, such that each elemental object belongs to one or more composite objects and each composite object contains one or more elemental objects. The elemental and composite objects are linked in a lattice data structure stored in system memory. When a user manipulates the graphical image, the system creates new elemental objects in the manipulated region of the image, reorganizes all or part of the composite objects into one or more new composite objects, and updates the lattice data structure.

Claims

1. A graphical input and display system for creating and manipulating an abstract graphical image comprising:

input means, display means, memory means and function selection means, said input means being user manipulable for entering said graphical image onto said display means and for selecting functions on said function selection means for manipulating said graphical image;

means for decomposing said graphical image entered onto said display means into abstract elemental objects;

means for organizing said elemental objects into abstract groups of elemental objects, such that each elemental object belongs to one or more groups and each group contains one or more elemental objects;

means for reorganizing all or part of said groups of elemental objects into one or more new abstract groups of elemental objects in response to a user manipulation of all or part of said graphical image; and

at least one data structure stored in said memory means in which said elemental objects and said groups of elemental objects are linked.

2. The graphical input and display system of claim 1 further comprising a spatial and scale indexed graphical data structure stored in said memory means for organizing said groups of elemental objects according to the locations and sizes of said groups in said graphical image.

3. The system of claim 1 wherein said at least one data structure comprises a lattice data structure in which each elemental object is linked to each group to which it belongs and each group is linked to each elemental object contained in said group.

4. The system of claim 3 wherein said lattice data structure comprises a series of bi-directional pointers linking each of said elemental objects with each corresponding group of elemental objects.

5. The system of claim 1 further comprising means for updating said at least one data structure in response to a reorganization by said means for reorganizing.

6. The system of claim 1 further comprising means for manipulating each of the elemental objects belonging to a group in response to a user manipulation of said group.

7. The system of claim 1 wherein said means for decomposing a graphical image into abstract elemental objects comprises:

a bit map data structure stored in said memory means for accessing values of pixels in the graphical image; and

means for organizing said pixels into said elemental objects based at least in part on said values of said pixels.

8. The system of claim 1 wherein said means for organizing said elemental objects into groups comprises a spatial image analyzer for heuristically determining spatial and geometric properties of said elemental objects.

9. A method of manipulating all or a portion of a graphical abstract image entered on a display device comprising:

decomposing said graphical image into abstract elemental objects;

organizing said elemental objects into abstract groups of objects;

storing a data structure linking said elemental objects and said groups of elemental objects;

determining based on said data structure which of said elemental objects are to be manipulated in accordance with a selected manipulation of a given group of elemental objects in said graphical image;

performing said selected manipulation on said determined elemental objects;

reorganizing said manipulated elemental objects into further abstract groups of elemental objects;

updating said data structure in accordance with said reorganization.

10. The method of claim 9 wherein said graphical image includes at least a first and second portion having a shared boundary, said method further comprising the steps of:

assigning a multiple role to said shared boundary and, following a manipulation of said first or second portion, reorganizing said first and second portions into separate groups of elemental objects, such that at least one of said groups has a boundary duplicating said shared boundary.

11. A method of processing data representing a graphical image comprising:

deriving pixel identification data from the graphical image data;

identifying Prime Objects from the pixel identification data;

identifying a plurality of perceptually coherent Composite Objects from the Prime Objects, each Composite Object being a set of one or more Prime Objects;

creating a list of Prime Objects and a list of Composite Objects; and

linking the lists such that each Prime Object and each Composite Object to which the Prime Object corresponds is linked and each Composite Object and each Prime Object to which the Composite Object corresponds is linked, thereby providing the ability to locate a Prime or Composite Object based on the identity of the corresponding Composite or Prime Object, respectively.

12. The method of claim 11 further comprising the steps of deriving Stroke Ends from the Prime Objects and creating a list of series of pairs of Stroke Ends corresponding to the Prime Objects from which said Stroke Ends are derived.

13. The method of claim 12, wherein new objects are added to the graphical image, comprising the steps of:

detecting intersection locations of added Prime Objects with existing Prime Objects, detecting T junctions of added Prime Objects with existing Prime Objects, deleting existing and added Prime Objects formed by crossing or T junction, creating new Prime Object set, deleting obsolete Prime Objects and replacing with new Prime Objects, updating Stroke Ends associated with each Composite Object, removing Composite Objects associated with obsolete Prime Objects, removing Stroke Ends associated with obsolete Prime Objects, writing new Stroke Ends into data structures and marking such Stroke Ends, resolving marked Stroke Ends as changed Stroke Ends, detecting changed Stroke Ends and merging same with associated Prime Objects, deleting obsolete Composite Objects and replacing with new Composite Objects, extracting Prime Objects associated with changed Stroke Ends, and storing said extracted Prime Objects.

14. The method of claim 12, wherein objects are deleted from the graphical image, comprising the steps of:

deleting obsolete Prime Objects and replacing with new Prime Objects, deleting Stroke Ends associated with obsolete Prime Objects, marking junction Stroke Ends as affected, performing resolve junctions on affected Stroke Ends, marking affected Stroke Ends which are changed by removed Prime Objects as changed Stroke Ends, detecting pairs of changed Stroke Ends and merging with Prime Objects, removing and replacing obsolete Composite Objects, and extracting Prime Objects associated with changed Stroke Ends.

15. The method of claim 11 wherein Prime or Composite Objects are grouped and indexed according to their size and location within the graphical image, comprising the steps of:

sorting Objects by size, creating lists of Objects sorted by size, sorting Objects by location, creating lists of Objects sorted by location, defining a spatial neighborhood for each group of Objects, the size of the neighborhood depending upon a predetermined range of scale space for the Objects in the group, assigning a token to each Object in the neighborhood, and arraying respective tokens in an indexed data structure array by groups within the predetermined range of scaled space.

16. The method of claim 11 wherein the data is further processed following a manipulation of the graphical image by a user, comprising:

defining a region of the graphical image affected by the manipulation;

deriving revised pixel identification data in the affected region;

identifying Composite Objects and corresponding Prime Objects in the affected region;

changing the Prime Objects in the affected region based on the revised pixel identification data;

changing the Composite Objects in the affected region based on the changed Prime Objects; and

updating the lists of Prime and Composite Objects and the links therebetween based on the changed Prime and Composite Objects.

17. An article of manufacture comprising a computer usable medium having computer readable program code embodied in said medium which, when said program code is executed by said computer, causes said computer to perform method steps for creating and manipulating an abstract graphical image entered onto a display, said method steps comprising:

decomposing the graphical image into abstract elemental objects;

organizing said elemental objects into abstract groups of elemental objects, such that each elemental object belongs to one or more groups and each group contains one or more elemental objects;

creating at least one data structure in which said elemental objects are linked with said groups of elemental objects;

reorganizing all or part of said groups of elemental objects into one or more new abstract groups of elemental objects in response to a user manipulation of all or part of said graphical image; and

updating said at least one data structure in response to a reorganization.

18. A memory for storing data for access by a program being executed on a computer for creating and manipulating data representing an abstract graphical image, said memory comprising:

a lattice data structure stored in said memory, said lattice data structure including data used by said program, including;

a plurality of elemental objects stored in said memory, said elemental objects being derived from pixel identification data derived from the graphical image data, the elemental objects arranged in at least one elemental object list;

a plurality of perceptually coherent composite objects identified from the elemental objects, each composite object being a set of one or more elemental objects, said composite objects arranged in at least one composite object list; and

a plurality of bi-directional pointers linking the elemental object list or lists and the composite object list or lists such that each elemental object and each composite object to which the elemental object corresponds are linked and each composite object and each elemental object to which the composite object corresponds is linked,

said lattice data structure providing the program with the ability to locate and manipulate an elemental or composite object based on the identity of a corresponding composite or elemental object.