User-directed interaction with an image structure map representation of an image

• US 5,710,877 A
• Filed: 12/29/1995
• Issued: 01/20/1998
• Est. Priority Date: 12/29/1995
• Status: Expired due to Term

• Current Assignee: Marconi Communications, Inc. (Marconi Holdings Company Limited)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Guibas, Leonidas John, Marimont, David H.
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US08/581,660
• Time in Patent Office: 753 Days
• Field of Search: 395/127, 395/133, 395/119, 345/113, 345/114, 345/117
• US Class Current: 345/427
• CPC Class Codes: G06T 11/00 2D [Two Dimensional] image generation

Abstract

A data structure representation of an image called an image structure map (ISM) accurately and explicitly represents the geometry, topology and signal properties of regions in an original image and allows for efficient and accurate spatial indexing of the image and those regions. The ISM may serve as the basis for an image interaction system in which a user interacts with a rendered view of an original image that is produced from the ISM data structure. The rendered view of the original image represents the geometry and topology of the original image as represented in the ISM. The user interacts with the rendered view to make alterations to, or to query, the structures in the ISM. The user may also modify the ISM by interacting directly with a displayed view of the original image. The user may further invoke automatic operations to be performed using the original image data structure that produce image region data, such as signal property descriptors and boundary data, that may be used to modify the ISM. An image interaction system implemented in this manner takes full advantage of automatic computation methods to capture the geometric and topological properties of an image while permitting a user to employ human perceptual skills to augment the automatic operations. An illustrated implementation of the system uses an ISM having the form of a vertical cell decomposition that is mathematically robust, topologically consistent with the original image and is able to be modified dynamically--that is, without recomputing the entire ISM when a change is made.

Claims

1. A method for operating a processor-controlled machine to dynamically interact with an image structure map data structure representing an original image in response to input interaction signals received from a user;

the machine including input signal circuitry for receiving interaction signals from a user interaction device;

memory for storing data;

output circuitry connected to a display device for presenting images thereon; and

a processor connected for accessing instruction data stored in the memory for operating the machine;

the processor being further connected for receiving the input interaction signals from the user interaction device, and connected for providing image definition data defining images to the output circuitry for presenting the images on the display device;

the method comprising;

receiving an image interaction signal from the input circuitry indicating a request from a user to dynamically modify an image structure map data structure, referred to as an image structure map;

the image interaction signal including an input image location included in an input image definition data structure and an image interaction request;

the image structure map representing an original image definition data structure defining an original image in a form suitable for presenting the original image on the display device of the machine;

the image structure map representing the original image definition data structure as a partition of a two-dimensional (2D) plane induced by a set of intersecting image boundaries determined to be included in the original image into one or more region data items each indicating a respective image region in the original image formed by the set of intersecting image boundaries;

the image structure map, also referred to as an image structure map representation of the original image, being dynamically modifiable such that a selected image structure included in the image structure map is capable of being modified without recomputing all image structures included in the image structure map at the time of modification;

each region data item indicating a plurality of image region boundary data items;

each image region boundary data item indicating a respective one of the set of intersecting image boundaries forming the respective image region;

each region data item further indicating a signal property descriptor;

the signal property descriptor having a value indicating a smoothly varying function of signals included in locations in the original image definition data structure determined to be included in the respective image region of the original image; and

in response to receiving the image interaction signal, modifying the image structure map according to the image interaction request using the input image location by

determining an image structure map location of a target image structure in the image structure map using the input image location; and

modifying the target image structure in the image structure map according to the image interaction request such that only the target image structure and, when necessary, image structures associated with the target image structure, are modified in response to the request from the user.

2. The method of claim 1 for operating a processor-controlled machine to dynamically interact with an image structure map data structure wherein the request from the user to modify the image structure map is an insertion request to insert an image boundary in the image structure map representation of the original image;

wherein the input image location included in the image interaction signal is a location of the image boundary in the original image; and

wherein modifying the image structure map includes

determining a region data item in the image structure map representation of the original image that includes the image boundary; and

modifying the region data item such that the image boundary is inserted into the image structure map.

3. The method of claim 2 wherein the image location of the image boundary data item in the original image is produced by the user using the user interaction device to trace the image boundary data item in a displayed view of the original image.

4. The method of claim 2 wherein, when insertion of the image boundary data item creates a new image region in the image structure map, modifying the image structure map further includes inserting a new region data item in the image structure map, and computing a signal property descriptor for the new region data item.

5. The method of claim 1 for operating a processor-controlled machine to dynamically interact with an image structure map in response to user interaction signals wherein the input image location included in the image interaction signal is an image location in a rendered image data structure, referred to as a rendered image, such that the user interacts with the rendered image in order to modify the image structure map;

the rendered image being displayed in the display area and being a displayed view of the image structure map representation of the original image;

the rendered image showing display features indicating the region data items included in the image structure map representation of the original image;

the rendered image optionally showing a value of the signal property descriptor for each respective region data item.

6. The method of claim 1 for operating a processor-controlled machine to interact with an image structure map data structure wherein a region data item in the image structure map represented by an image region in the original image includes at least one subregion referred to as a cell;

the cell having a standardized geometric shape having a fixed number of bounded sides.

7. The method of claim 6 wherein the standardized geometric shape is a trapezoid;

the partition of the 2D plane induced by the set of image boundary data items in the original image being referred to as a vertical cell decomposition.

8. The method of claim 1 for operating a processor-controlled machine to dynamically interact with an image structure map in response to user interaction signals wherein the request from the user to modify the image structure map is a request to compute a current value for the signal property descriptor for a selected image region in the original image;

and wherein modifying the image structure map includes

locating the region data item representing the selected image region in the image structure map representation of the original image using the image location in the original image;

determining image locations in the original image included in the selected image region using image structure map locations indicated by the region data item representing the selected image region;

computing the current value of the signal property descriptor for the selected image region using signal data indicated by the image locations in the original image; and

updating the signal property descriptor indicated by the region data item in the image structure map with the current value.

9. The method of claim 1 for operating a processor-controlled machine to dynamically interact with an image structure map wherein the signal property descriptor is a color descriptor indicating a function of a color indicated by image locations in the original image determined to be included in an image region in the original image;

and wherein an image boundary in the original image is determined by a discontinuity in color such that each region data item in the image structure map representation of the original image represents a coherent area of the original image having a substantially similar color.

10. The method of claim 9 wherein the color descriptor indicating the function of the color of the image locations in the original image indicates a constant function;

the color descriptor indicating a single color for the image region.

11. The method of claim 9 wherein the color descriptor indicating the function of the color of the image locations in the original image is a linear function;

the color descriptor indicating a sequence of linearly varying colors for the image region.

12. The method of claim 1 for operating a processor-controlled machine to interact with an image structure map wherein the set of image boundary data items in the original image from which the partition of the original image is produced is a set of line segments.

13. The method of claim 1 for operating a processor-controlled machine to interact with an image structure map wherein the original image data structure indicates a digital image representation of a continuous-tone image.

14. The method of claim 1 for operating a processor-controlled machine to dynamically interact with an image structure map

wherein features observed in the original image have locations and orientations with respect to each other that define topological and geometric relationships among the features;

wherein image structures representing the features observed in the original image are stored in the image structure map in a manner that preserves topological and geometric consistency with the features observed in the original image; and

wherein, when the input image location included in the image interaction signal is an original image location in the original image data structure, the original image location is capable of being used to spatially index into the image structure map to locate an image structure in the image structure map that represents a feature of the original image that includes the original image location.

15. The method of claim 1 wherein each intersection and endpoint location, referred to as an unrounded vertex, of an image boundary in the set of intersecting image boundaries forming an image region determined to be included in the original image is represented in the image structure map as a machine representable value computed according to a rounding operation applied to an unrounded vertex value of the unrounded vertex;

the rounding operation producing a rounded vertex value for the respective unrounded vertex in a manner that preserves topological consistency between vertex locations in the original image and vertex locations in the image structure map.

16. The method of claim 15 wherein, when modifying the target image structure in the image structure map according to the image interaction request includes inserting an image boundary into the image structure map, modifying the target image structure includes applying the rounding operation to each unrounded vertex of the image boundary to produce a machine representable value for storing as the rounded vertex value in the image structure map.

17. The method of claim 16 wherein, when a first image boundary is inserted into the image structure map representation of the original image, the first image boundary is stored in the image structure map both as a region boundary data item having rounded vertex values and as a first unrounded image boundary data item;

and wherein, when a second image boundary intersecting with the first image boundary is subsequently inserted into the image structure map, the rounding operation is applied to an unrounded intersection location of the second image boundary with the first unrounded image boundary data item;

using the first unrounded image boundary data item to determine the unrounded intersection location ensuring that a machine representable value of a rounded vertex indicates a location and orientation in the image structure map representation of the original image that is topologically and geometrically consistent with a location and orientation of the respective unrounded intersection location determined to be included in the original image.

18. The method of claim 1 for operating a processor-controlled machine to dynamically interact with an image structure map in response to user interaction signals

wherein the request from the user to modify the image structure map includes a request to invoke an automatic image segmentation operation for producing image boundaries for insertion into the image structure map;

wherein the input image location included in the image interaction signal is a location of a portion of the original image definition data structure;

wherein modifying the image structure map includes performing the automatic image segmentation operation using the portion of the original image definition data structure specified in the image interaction signal to produce a plurality of image boundary data items each indicating an image boundary determined to be included in the original image and an input image location in the original image data structure; and

wherein modifying the image structure map includes automatically inserting each image boundary data item into the image structure map by determining a region data item in the image structure map representation of the original image that includes the image boundary and modifying the region data item such that the image boundary is inserted into the image structure map.

19. A method for operating a processor-controlled machine to dynamically interact with an image structure map data structure representing an original image in response to input interaction signals received from a user;

the machine including input signal circuitry for receiving interaction signals from a user interaction device;

memory for storing data;

output circuitry connected to a display device for presenting images thereon; and

a processor connected for accessing instruction data stored in the memory for operating the machine;

the processor being further connected for receiving the input interaction signals from the user interaction device, and connected for providing image definition data defining images to the output circuitry for presenting the images on the display device;

the method comprising;

storing in the memory an original image definition data structure defining the original image in a form suitable for presenting the original image on the display device;

receiving an image interaction signal from the input circuitry indicating a request from a user to dynamically insert an image boundary determined to be included in the original image data structure into an image structure map data structure, referred to as an image structure map;

the image boundary, referred to as a selected image boundary, being identified by an image boundary location in the original image data structure;

the image structure map representing the original image definition data structure as a partition of a two-dimensional (2D) plane induced by a set of intersecting image boundaries determined to be included in the original image into one or more region data items each indicating an image region formed by the set of intersecting image boundaries;

the image structure map spatially indexing the original image data structure such that an original image location in the original image data structure is able to be used to locate an image structure in the image structure map that represents a feature observed in the original image that includes the original image location;

the image structure map, also referred to as an image structure map representation of the original image, being dynamically modifiable such that an image boundary determined to be included in the original image definition data structure is capable of being inserted into the image structure map without recomputing all image structures included in the image structure map at the time of insertion thereof;

each region data item further indicating a plurality of image region boundary data items;

each image region boundary data item indicating a respective one of the set of intersecting image boundaries forming the respective image region;

each region data item further indicating a signal property descriptor;

the signal property descriptor having a value indicating a smoothly varying function of signals included in locations in the original image definition data structure determined to be included in the respective image region of the original image; and

in response to receiving the image interaction signal, inserting the selected image boundary into the image structure map by

determining a target region data item included in the image structure map that includes the selected image boundary using the image boundary location in the original image data structure; and

modifying the target region data item to indicate the selected image boundary.

20. The method of claim 19 wherein modifying the target region data item to indicate the selected image boundary includes representing each intersection location and endpoint location, referred to as an unrounded vertex, of the selected image boundary inserted into the image structure map as a machine representable value computed according to a rounding operation applied to an unrounded vertex value of each unrounded vertex;

the rounding operation producing a rounded vertex value for the respective unfounded vertex in a manner that preserves topological consistency between the unrounded vertex location in the original image and the rounded vertex location in the image structure map.

21. The method of claim 20 wherein inserting the selected image boundary into the image structure map further includes storing the selected image boundary in the image structure map as an unrounded image boundary data item;

and wherein, with respect to subsequent insertion of a next selected image boundary into the image structure map that intersects with the unrounded image boundary data item at an unrounded intersection location, the rounding operation is applied to the unrounded intersection location;

using the unfounded image boundary data item to determine the unrounded intersection location ensuring that a machine representable value of a rounded vertex indicates a location and orientation in the image structure map representation of the original image that is topologically and geometrically consistent with a location and orientation of the unrounded intersection location determined to be included in the original image.

22. An article of manufacture for use by a machine;

the machine including input signal circuitry for receiving interaction signals from a user interaction device;

output circuitry connected to a display device for presenting images thereon;

storage medium access circuitry for accessing a medium that stores data; and

a processor connected for receiving the input interaction signals from the user interaction device, connected for providing image definition data defining images to the output circuitry for presenting the images on the display device, and connected for receiving data from the storage medium access circuitry;

the article comprising;

a data storage medium that can be accessed by the storage medium access circuitry when the article is used by the machine; and

data stored in the data storage medium so that the storage medium access circuitry can provide the stored data to the processor when the article is used by the machine;

the stored data comprising instruction data indicating instructions the processor can execute;

the processor, in executing the instructions, receiving an image interaction signal from the input circuitry indicating a request from a user to dynamically modify an image structure map data structure, referred to as an image structure map;

the image interaction signal including an input image location included in an input image definition data structure and an image interaction request;

the image structure map representing an original image definition data structure defining an original image in a form suitable for presenting the original image on the display device of the machine;

the image structure map representing the original image definition data structure as a partition of a two-dimensional (2D) plane induced by a set of intersecting image boundaries determined to be included in the original image into one or more region data items each indicating an image region formed by the set of intersecting image boundaries;

the image structure map, also referred to as an image structure map representation of the original image, being dynamically modifiable such that a selected image structure included in the image structure map is capable of being modified without recomputing all image structures included in the image structure map at the time of modification thereof;

each region data item indicating a plurality of image region boundary data items;

each image region boundary data item indicating a respective one of the set of intersecting image boundaries forming the respective image region;

each region data item further indicating a signal property descriptor;

the signal property descriptor having a value indicating a smoothly varying function of signals included in locations in the original image definition data structure determined to be included in the respective image region of the original image;

the processor, further in executing the instructions, modifying the image structure map according to the image interaction request using the input image location, in response to receiving the image interaction signal;

the processor, further in executing the instructions for modifying the image structure map, determining an image structure map location of a target image structure in the image structure map using the input image location; and

modifying the target image structure in the image structure map according to the image interaction request such that only the target image structure and, when necessary, image structures associated with the target image structure, are modified in response to the request from the user.

23. The article of manufacture of claim 22 wherein

features observed in the original image have locations and orientations with respect to each other that define topological and geometric relationships among the features;

image structures representing the features observed in the original image are stored in the image structure map in a manner that preserves topological and geometric consistency with the features observed in the original image; and

when the input image location included in the image interaction signal is an original image location in the original image data structure, the processor, in executing the instructions, uses the original image location to spatially index into the image structure map to locate an image structure therein that represents a feature of the original image that includes the original image location.

24. The article of manufacture of claim 22 wherein

the request the processor receives from the user to dynamically modify the image structure map is an insertion request to insert an image boundary in the image structure map representation of the original image;

the input image location included in the image interaction signal received by the processor is a location of the image boundary in the original image; and

the processor, in executing the instructions for modifying the image structure map, determines a region data item in the image structure map representation of the original image that includes the image boundary; and

modifies the region data item such that the image boundary is inserted into the image structure map.