Producing a rendered image version of an original image using an image structure map representation of the image

• US 5,809,179 A
• Filed: 05/31/1996
• Issued: 09/15/1998
• Est. Priority Date: 05/31/1996
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Marimont, David H., Guibas, Leonidas John
• Primary Examiner(s): LEE, TOMMY D
• Application Number:
  US08/660,058
• Time in Patent Office: 837 Days
• Field of Search: 382/254, 382/173, 382/181, 382/190, 382/195, 382/199, 382/201, 382/203, 382/204, 358/448, 358/453
• US Class Current: 382/254
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 7/12 Edge-based segmentation

Abstract

The invention automatically produces a rendered image version of an original image that accurately represents perceptually distinguishable objects, surfaces and edges in the original image. The original image is first converted to a unique data structure representation called an image structure map (ISM) that accurately, compactly and explicitly represents the geometry, topology and signal properties of perceptually distinguishable regions in the original image. The ISM is a dynamic partition of the image induced by a set of image region boundaries, and includes, for each region in the original image, a region data item that indicates the region boundary data items that form the region and a signal property descriptor indicating the value of signals computed for image locations in the region. An automatic segmentation operation determines image region boundaries occurring in the original image by analyzing discontinuities in signal values of original image locations. The topology of the rendered image version is accurate because vertices (endpoints and intersections) of image region boundaries are represented in the ISM in machine representable values that result from modifying exact vertex values using a rounding operation that mathematically ensures topological and geometric consistency with the original image. The method is particularly useful for producing rendered image versions of full color, continuous tone photographic images, and for producing line drawings of such images. The ISM representation of an image is, in most cases, more compact than its original raster form, and serves as a useful representation for archiving the image.

Claims

1. A method for operating a processor-controlled machine to produce a rendered image version of an input original image on a display device;

the machine including image input circuitry for receiving image definition data defining the input original image;

memory for storing data;

output circuitry connected to the display device; 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 original image from the image input circuitry, and connected for providing image definition data defining images to the output circuitry for presenting the rendered image version on the display device;

the method comprising;

performing an automatic image segmentation operation using the input original image;

the automatic image segmentation operation determining image region boundaries occurring in the input original image between image regions therein by detecting a discontinuity in a value of a smoothly varying signal property of signal values indicated by original image locations in the original image;

an image region in the original image being indicated by a coherent area of original image locations in which the signal values vary smoothly;

an image region boundary occurring at a discontinuity in the smoothly varying signal values;

producing a partition data structure representation, referred to as a partition, of the original image using the image region boundaries determined by the automatic image segmentation operation;

the partition indicating a plurality of nonoverlapping image regions of a 2D plane induced by the set of image region boundaries;

the partition being produced dynamically by inserting image region boundaries one at a time therein;

the partition including, for each image region in the original image, a region data structure including region boundary data items each indicating an adjacent image region boundary of the image region in the original image;

the region data structure further including a plurality of vertex data items each indicating a vertex location adjacent to a region boundary data item included in the region data structure, wherein a vertex location refers to an endpoint location of a respective one of the image region boundaries or an intersection location between two image region boundaries;

each vertex data item having a machine representable value when stored in the partition;

the machine representable value being computed by applying a rounding operation to an exact higher precision value for the vertex location of the respective image region boundary and modifying the exact value to produce the machine representable value;

modifying the vertex location of an image region boundary producing a rounded image region boundary represented by the region boundary data item;

rendering a rendered image version of the original image using the partition data structure;

the rendered image version showing the image regions determined to be included in the original image; and

presenting the rendered image version of the original image on a display device.

2. The method for operating a processor-controlled machine to produce a rendered image version of an input original image of claim 1 wherein the rendered image version shows the image region boundaries determined to be included in the original image;

the rendered image version of the original image having an appearance of a line drawing of the original image.

3. The method for operating a processor-controlled machine to produce a rendered image version of an input original image of claim 1

wherein each respective region data item included in the partition further indicates a signal property descriptor data item indicating a smoothly varying function of signals included in locations in the original image determined to be included in the image region represented by the respective region data item;

the partition including the signal property descriptor being referred to as an image structure map; and

wherein the rendered image version shows the value of the signal property descriptor of each image region determined to be included in the original image.

4. The method for operating a processor-controlled machine of claim 3 wherein the signal property descriptor is a color descriptor indicating a color function representing color values of the locations in the original image represented by a respective region data item;

and

wherein the rendered image version of the original image shows, in each image region represented by a respective region data item, a value for the color function indicated by the respective region data item.

5. The method for operating a processor-controlled machine of claim 4 wherein the color function representing the color value of the image locations in the original image is a constant function indicating a single color value for the image region;

and

wherein the rendered image version of the original image shows a constant color value in each image region determined to be included in the original image.

6. The method for operating a processor-controlled machine of claim 4 wherein the color function representing color values of the image locations in the original image is a linear function;

the color descriptor indicating that the color values for a respective image region vary linearly within the image region; and

wherein the rendered image version of the original image shows color values varying linearly in each image region.

7. The method for operating a processor-controlled machine of claim 3 wherein, when the smoothly varying function of signals indicated by the signal property descriptor indicates a function of signal values other than color values in image locations in the original image, rendering the rendered image version of the original image using the image structure map data structure includes representing the signal values of locations in the original image in each image region as color values;

the rendered image version showing a color value indicating each image region determined to be included in the original image.

8. The method for operating a processor-controlled machine to produce a rendered image version of an input original image of claim 1 further including storing the partition data structure in a data base of partition representations of original images.

9. The method for operating a processor-controlled machine to produce a rendered image version of an input original image of claim 1 further including storing the rendered image version of the original image in a data base of rendered image versions of original images.

10. The method for operating a processor-controlled machine to produce a rendered image version of an input original image of claim 1 wherein the original image definition data structure indicates a digital image representation of a continuous-tone color image;

the rendered image version of the original image further showing, in each respective image region determined to be included in the original image, a color value of the respective image region.

11. A method for operating a processor-controlled machine to automatically produce a data store of image structure map data structure representations of a plurality of original image definition data structures, referred to as original images;

the machine including image input circuitry for receiving image definition data defining an original image;

memory for storing data; and

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

the processor being further connected for receiving original images from the image input circuitry;

the method comprising;

performing, for each original image, an automatic image segmentation operation using the original image;

the automatic image segmentation operation determining image region boundaries occurring in the original image between image regions therein by detecting a discontinuity in a value of a smoothly varying signal property of signal values indicated by original image locations in the original image;

an image region in the original image being indicated by a coherent area of original image locations in which the signal values vary smoothly;

an image region boundary occurring at a discontinuity in the smoothly varying signal values;

producing, for each original image, an image structure map data structure representation of the original image using the image region boundaries determined by the automatic image segmentation operation;

the image structure map indicating a partition of a 2D plane induced by the set of image region boundaries into a plurality of nonoverlapping image regions included in the original image;

the image structure map being produced dynamically by inserting image region boundaries one at a time therein;

the image structure map including, for each image region in the original image, a region data structure including region boundary data items each indicating an adjacent image region boundary of the image region in the original image;

the region data structure further including a plurality of vertex data items each indicating a vertex location adjacent to a region boundary data item included in the region data structure, wherein a vertex location refers to an endpoint location of a respective one of the image region boundaries or an intersection location between two image region boundaries;

each vertex data item having a machine representable value when stored in the image structure map;

the machine representable value being computed by applying a rounding operation to an exact higher precision value for the vertex location of the respective image region boundary and modifying the exact value to produce the machine representable value;

modifying the vertex location of an image region boundary producing a rounded image region boundary represented by the region boundary data item;

computing a signal property descriptor data item for each respective image region determined to be included in the original image;

the signal property descriptor indicating a smoothly varying function of signals included in locations in the respective image region; and

for each image structure map representation of an original image, storing the image structure map in a data store of image structure map representations of original images;

a rendered image version of the original image being capable of being rendered using the image structure map representation of the original image;

the rendered image version showing the image regions determined to be included in the original image and showing the value of the signal property descriptor of each image region represented in the image structure map.

12. The method of claim 11 for operating a processor-controlled machine to produce a data store of image structure map representations of original images wherein, when the number of image regions determined to be included in the original image is less than the number of image locations in the original image, the image structure map is a compressed representation of the original image.

13. The method of claim 12 for operating a processor-controlled machine wherein the signal property descriptor is a color descriptor indicating a color function representing color values of the locations in the original image represented by a respective region data item;

and

wherein, when a rendered image version of the original image is rendered using the image structure map, the rendered image version of the original image shows, in each image region represented by a respective region data item, a value for the color function indicated by the respective region data item.

14. The method for operating a processor-controlled machine of claim 11 wherein the original image definition data structure indicates a digital image representation of a continuous-tone color image;

and wherein, when a rendered image version of the original image is rendered using the image structure map, the rendered image version of the original image further shows, in each respective image region determined to be included in the original image, a color value of the respective image region.

15. An article of manufacture for use by a processor-controlled machine for producing a rendered image version of an input original image on a display device;

the machine including image input circuitry for receiving image definition data defining the input original image;

memory for storing data;

output circuitry connected to the display device; 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 original image from the image input circuitry, and connected for providing image definition data defining images to the output circuitry for presenting the rendered image version on the display device;

the processor being further 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, performing an automatic image segmentation operation using the input original image;

the automatic image segmentation operation determining image region boundaries occurring in the input original image between image regions therein by detecting a discontinuity in a value of a smoothly varying signal property of signal values indicated by original image locations in the original image;

an image region in the original image being indicated by a coherent area of original image locations in which the signal values vary smoothly;

an image region boundary occurring at a discontinuity in the smoothly varying signal values;

the processor, further in executing the instructions, producing a partition data structure representation, referred to as a partition, of the original image using the image region boundaries determined by the automatic image segmentation operation;

the partition indicating a plurality of nonoverlapping image regions of a 2D plane induced by the set of image region boundaries;

the partition being produced dynamically by inserting image region boundaries one at a time therein;

the partition including, for each image region in the original image, a region data structure including region boundary data items each indicating an adjacent image region boundary of the image region in the original image;

the region data structure further including a plurality of vertex data items each indicating a vertex location adjacent to a region boundary data item included in the region data structure, wherein a vertex location refers to an endpoint location of a respective one of the image region boundaries or an intersection location between two image region boundaries;

each vertex data item having a machine representable value when stored in the partition;

the machine representable value being computed by applying a rounding operation to an exact higher precision value for the vertex location of the respective image region boundary and modifying the exact value to produce the machine representable value;

modifying the vertex location of an image region boundary producing a rounded image region boundary represented by the region boundary data item;

the processor, further in executing the instructions, rendering a rendered image version of the original image using the partition data structure;

the rendered image version showing the image regions determined to be included in the original image;

the processor, still further in executing the instructions, presenting the rendered image version of the original image on a display device.

16. The article of manufacture of claim 15 wherein the rendered image version shows the image region boundaries determined to be included in the original image;

the rendered image version of the original image having an appearance of a line drawing of the original image.

17. The article of manufacture of claim 15 wherein each respective region data item included in the partition further indicates a signal property descriptor data item indicating a value of a smoothly varying function of signals included in locations in the original image determined to be included in the image region represented by the respective region data item;

the partition including the signal property descriptor being referred to as an image structure map; and

wherein the rendered image version shows the value of the signal property descriptor of each image region determined to be included in the original image.

18. The article of manufacture of claim 17 wherein the signal property descriptor is a color descriptor indicating a color function representing color values of the locations in the original image represented by a respective region data item;

and

wherein the rendered image version of the original image shows, in each image region represented by a respective region data item, a value for the color function indicated by the respective region data item.