Method for general image manipulation and composition

• US 5,852,673 A
• Filed: 11/21/1996
• Issued: 12/22/1998
• Est. Priority Date: 03/27/1996
• Status: Expired due to Fees

• Current Assignee: Chroma Graphics, Inc.
• Original Assignee: Chroma Graphics, Inc.
• Inventors: Young, Fredric S.
• Primary Examiner(s): Au, Amelia
• Assistant Examiner(s): AHMED, SAMIR ANWAR
• Application Number:
  US08/754,731
• Time in Patent Office: 761 Days
• Field of Search: 382/162, 382/164, 382/165, 382/167, 382/253, 345/150, 345/199, 358/518, 358/520, 395/131
• US Class Current: 382/164
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation

Abstract

Methods are provided for carrying out a selection step and a blending step of a process of photorealistically reconstructing and manipulating a portion of a photograph or digital image, such as a segment or a layer, in order to minimize transition discontinuities and to provide optimum speed in the segmenting of the image, which is a function of increasing importance in a production environment. In the selection step, an image is classified into foreground and background states and regions, which could be limited to a selected layer of a final image. A vector is constructed which maps separation distances in a specialty space such as HSV space between the background region in a background state and the foreground region in a new foreground state. Difference vectors between the old and new foreground states are used to facilitate the mapping via a transition path which occupies the portion of specialty space where all the edge pixels between the foreground and the background parameters are located. An object in a portion of an image which has been manipulated is blended back into the photograph or image in a natural way using the transition vector. In addition, methods for carrying out the manipulating step of this process involve a variable vector quantization step to reduce the number of parameter elements in an image.

Claims

1. In a process of photorealistically processing a portion of a source image, to form a target image using a palette of colors, said process having at least a color selection step and a blending step, the improvement comprising:

in the color selection step, classifying each part of an image segment of the source image in a color space of at least three dimensions as a foreground region, a background region or a transition region; and

in the blending step,

formulating a color gradient between a new foreground color which has been selected by said color selection step and an original background color across said transition region, said gradient defining a seamless color transition between said foreground region and said background region without artificial discontinuities;

employing difference vectors to define an endpoint of a transition vector between said background color and said new foreground color; and

mapping said transition vector from said background color to said new foreground color.

2. In a process of photorealistically processing a portion of a source image, to form a target image using a palette of colors, said process having at least a color selection step and a blending step, the improvement comprising:

in the color selection step, classifying each part of an image segment of the source image in a color space of at least three dimensions as a foreground region, a background region or a transition region; and

in the blending step, formulating a color gradient between a new foreground color which has been selected by said color selection step and an original background color across said transition region, said gradient defining a seamless color transition between said foreground region and said background region without artificial discontinuities, further including a recoloring step, an improvement in the recoloring step comprising;

determining a first weighted average of colors in the color space of the foreground region of the source image;

providing a distribution of colors from the color palette;

determining a second weighted average of colors in the color space of a selected distribution region of the distribution of colors of the color palette;

thereafter

decomposing said first weighted average into a first H-S pair in HSV color space and a first value component;

decomposing said second weighted average into a second H-S pair and a second value component;

generating a first difference vector from the difference between said first H-S pair and said second H-S pair;

generating a second difference vector from the difference between said first value component and said second value component;

recoloring H-S components of said source image with said first difference vector; and

recoloring said value component of said source image with second difference vector.

3. In the process of claim 2, the step of recoloring said H-S components comprising adding said first difference vector to said first H-S pair.

4. In the process of claim 3, the step of recoloring said value component comprising multiplying the value component in each selected foreground pixel of the target image by a function of said second difference vector.

5. In a process of claim 2, the improvement in the recoloring step comprising:

vector quantizing the color space of the target image to represent colors in the target image with a first variable quantization index; and

vector quantizing the color points in the image segment of the source image with a second variable quantization index which can be used to map to the target image.

6. In the process of claim 5, an improvement in the segmenting step comprising using the vector quantized source image to formulate a coarse color space graining, said graining being an index for said segmenting step to facilitate assignment of pixels to said foreground region, said background region and said transition regions.

7. In the process of claim 5, an improvement in the recoloring step further comprising, on first selected pixels representing said foreground region, and using selected discrete color values of said color palette in an HSV color space:

selecting a first degree of granularity of the source image colors;

selecting a second degree of granularity of the color palette colors;

ordering the source image colors into first ordered sets of HSV vectors;

ordering the color palette colors into second ordered sets of HSV vectors;

thereafter

aligning said first ordered sets of HSV vectors with said second ordered sets of HSV vectors in accordance with said quantization indexes;

decomposing each pair of corresponding first and second HSV vectors into HS pairs and V components;

forming a first difference vector from differences in said HS pairs;

adding said first difference vector to an HS vector at its corresponding position in said foreground region;

forming a second difference vector from differences in said V components; and

multiplying said second difference vector with the V component at its corresponding position in said foreground region.

8. In the process of claim 7, the improvement in the blending step comprising:

employing said first difference vector and said second difference vector to define an endpoint of a transition vector between said background color and said new foreground color; and

mapping said transition vector from said background color to said new foreground color.