Interactive graphical search and replace utility for computer-resident synthetic graphic image editors

• US 5,133,052 A
• Filed: 08/04/1988
• Issued: 07/21/1992
• Est. Priority Date: 08/04/1988
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Kurlander, David J., Bier, Eric A.
• Primary Examiner(s): Herndon, Heather R.
• Application Number:
  US07/228,882
• Time in Patent Office: 1,447 Days
• Field of Search: 364/518-522, 382/41, 382/44, 382/45, 382/16, 382/25, 382/40, 382/30, 382/48, 340/723, 340/747, 395/155, 395/133, 395/136
• US Class Current: 715/234
• CPC Class Codes: G06T 11/00 2D [Two Dimensional] image generation
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

Provision is made for search digital synthetic graphics data (e.g., displayed single page scenes, multi-page files or multi-file databases) to find graphical patterns which match a user specified graphical search pattern. Furthermore, there is support (i) for performing pre-recorded macro operations on all or some of the matches that are found, or (ii) for substituted user-specified replacements for some or all of the geometric characteristics and graphical properties of the pattern matches that are found.

Claims

1. A computerized graphical search and replace process for editing digital synthetic graphical data representing a computer generated n-dimensional scene, where n>

1;

said process comprising the steps of

searching said data in an n-dimensional directed order for n-dimensional graphical patterns matching geometric characteristics and graphical properties of a user-specified n-dimensional graphical search pattern;

selecting one after another of any data patterns that are found during said search to be substantially matched graphically to said search pattern; and

editing at least some of said selected data patterns on a case-by-case basis in accordance with user-specified editing instructions.

2. The process of claim 1 wherein said editing instructions are defined by a pre-recorded macro.

3. The process of claim 1 wherein said editing instructions are defined by a user-specified n-dimensional graphical replacement pattern.

4. A computerized graphical search process for finding matches to a user-specified n-dimensional graphical search pattern in digital synthetic graphical data representing a computer generated n-dimensional scene, where n>

1;

said process comprising the steps of

searching said data in a n-dimensional directed order for graphical patterns matching geometric characteristics and graphical properties of a user-specified n-dimensional graphical search pattern; and

selecting one after another of any data patterns that are found during said search to be substantially matched graphically to said search pattern.

5. A computerized graphical search process for finding matches, including affine transformed matches, to a user-specified n-dimensional graphical search pattern in digital synthetic graphical data representing a computer generated n-dimensional scene, where n>

1;

said process comprising the steps of;

computing a first affine transformation for mapping said graphical seach pattern into a canonical form;

searching said data in n-dimensional directed order for potential instances of said search pattern, including permissible affine transformed instances;

computing at least one permissible trial affine transformation for test mapping the canonical form of said search pattern separately into each of said potential instances;

test mapping the canonical form of said search pattern into each of said potential instances of said search pattern in accordance with each trial transformation for such instance; and

determining from all test mappings for each potential instance of said search pattern which, if any, of said potential instances are actual instances of said search pattern.

6. The computerized graphical search process of claim 5 further including the step of:

registering user specified affine invariants for limiting said search to graphical patterns exactly matching all specified affine invariants of said graphical search pattern.

7. A computerized graphical search and replace process for editing digital synthetic graphical data representing a computer generated n-dimensional scene by substituting a user-specified n-dimensional graphical replacement pattern, where n>

1, for selected instances of a user-specified n-dimensional graphical search pattern when said data includes such instances in unknown affine transformed form;

said process comprising the steps of;

computing a first affine transformation for mapping said search pattern into a canonical form;

storing said first affine transformation;

searching said data in n-dimensional directed order for locating potential instances of said search pattern;

computing at least one affine trial transformation for test mapping the canonical form of said search pattern independently into each of said potential instances of said search pattern, whereby each test mapping relates to a particular trial transformation and to a particular potential instance of said search pattern;

determining from each test mapping whether the related trial transformation substantially matches the canonical form of the search pattern to the related potential instance of the search pattern, thereby identifying any actual instances of said search pattern and a related pattern matching affine transformation for each of said actual instances;

storing the related pattern matching affine transformation for each of said actual instances;

selecting certain of said actual instances of said search pattern; and

substituting transformed versions of said replacement pattern for said certain instances of said search pattern, each of said versions of said replacement pattern being transformed serially in accordance with said first affine transformation and in accordance with the pattern matching transformation for the instance of said search pattern for which the transformed version of said replacement pattern is being substituted.

8. The graphical search and replace process of claim 7 further including the step of:

registering user-selected affine invariants for excluding selected affine operations from at least some of said affine transformations.