Image segmentation using robust mixture models

• US 5,802,203 A
• Filed: 06/07/1995
• Issued: 09/01/1998
• Est. Priority Date: 06/07/1995
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Black, Michael Julian, Jepson, Allan Douglas
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US08/488,002
• Time in Patent Office: 1,182 Days
• Field of Search: 382/173, 382/176, 382/177, 382/302, 358/462
• US Class Current: 382/173
• CPC Class Codes: H04N 1/40062 Discrimination between different image types, e.g. two-tone, continuous tone

Abstract

An image segmentation system segments images into component elements by modelling the image as a series of combined layers. The brightness of pixels within each layer is modelled as a parametric function of pixel position. Weights are assigned to each pixel position within each layer and describe how the layers are combined to form a recovered image. By modelling the image as a compilation of layers having different brightness functions, the system segments elements within an image, including text, when the image is corrupted by noise and when elements are combined, such as text and graphics. Enhanced image compression is obtained by modelling the image in multiple layers.

Claims

1. An image segmentation system for segmenting an image into a plurality of layers and a plurality of sets of weights, each set of weights corresponding to one of the plurality of layers, each of the plurality of layers comprising a plurality of layer pixels, each of the plurality of layer pixels corresponding to an image pixel in the image, the image segmentation system comprising:

image brightness means for determining an actual image pixel brightness for each image pixel in the image;

parametric model means for generating a layer pixel brightness model for each of the plurality of layers, each layer pixel brightness model describing a layer pixel brightness value for each layer pixel in the corresponding layer, each layer pixel brightness model generated based on the corresponding set of weights and the actual image pixel brightness of the image pixels in the image;

residual determining means for determining a plurality of sets of residual values, each set of residual values corresponding to one layer, each residual value in the corresponding set of residuals corresponding to a layer pixel in the corresponding layer, each residual value determined based on the corresponding layer pixel brightness value for the corresponding layer pixel determined by the parametric model means and the corresponding actual image pixel brightness of the corresponding image pixel;

weight determining means for determining the plurality of sets of weights, each weight in each set of weights corresponding to a layer pixel in the corresponding layer, each weight determined based on the residual value for the corresponding layer pixel in the corresponding layer; and

control means for controlling the image brightness means, the parametric model means, the residual determining means and the weight determining means.

2. The image segmentation system of claim 1, wherein the weight determining means determines each weight based on a comparison between a layer pixel brightness for the corresponding pixel in the corresponding layer and the actual image pixel brightness of the corresponding image pixel.

3. The image segmentation system of claim 1, wherein each weight in each set of weights is determined based on a robust error norm having a scale parameter.

4. The image segmentation system of claim 3, wherein the robust error norm is the Geman/McClure error norm.

5. The image segmentation system of claim 1, wherein the layer pixel brightness model is an affine model.

6. The image segmentation system of claim 5, wherein each layer pixel brightness model is given by:

space="preserve" listing-type="equation">u(x,y;

a.sub.i)=a.sub.0 +a.sub.1 x+a.sub.2 y

where u is the layer pixel brightness value of each layer pixel at a pixel position (x,y) in the corresponding layer, and a₀, a₁ and a₂ are parameters.

7. The image segmentation system of claim 1, wherein at least one layer pixel brightness model is a quadratic model.

8. The image segmentation system of claim 1, wherein the controller assembles a recovered image using at least two of the plurality of layers and the corresponding sets of weights, and a recovered image pixel brightness of recovered image pixels in the recovered image is determined by the image segmentation system based on the layer pixel brightnesses and the weights of the corresponding layer pixels in the at least two layers.

9. The image segmentation system of claim 1, wherein the control means assembles a recovered image using selected ones of the plurality of layers and the corresponding sets of weights, and a recovered image pixel brightness of recovered image pixels in the recovered image is determined by the image segmentation system based on the layer pixel brightness and the weights of corresponding layer pixels in the selected ones of the plurality of layers.

10. A method for segmenting an image, the image comprising a plurality of image pixels, each of the plurality of image pixels having an image pixel brightness represented by image data, the method comprising the steps of:

inputting the image data representing the image, the image data corresponding to a plurality of the image pixels;

determining an actual image pixel brightness for each of the plurality of image pixels from the image data;

estimating a number of layers needed to segment the image, each layer comprising a plurality of layer pixels and having a layer pixel brightness model, each of the plurality of layer pixels corresponding to an image pixel in the image;

estimating at least one parameter for each layer pixel brightness model of the number of layers, each layer pixel brightness model representing the layer pixel brightness for each layer pixel in the corresponding layer;

determining a layer pixel brightness for each layer pixel in each layer based on the layer pixel brightness model corresponding to the layer;

determining a set of residuals corresponding to each layer, each residual corresponding to a layer pixel in the layer and based on the layer pixel brightness of the corresponding layer pixel and the actual image pixel brightness of the corresponding image pixel;

determining a number of sets of weights, each set corresponding to one layer based on the corresponding set of residuals and a robust error norm, each weight in a set of weights corresponding to a layer pixel in the corresponding layer;

updating the at least one parameter for the pixel brightness model corresponding to each layer based on the corresponding set of weights and the actual image pixel brightness of the plurality of image pixels in the image;

determining if a convergence criterion is met; and

repeating the layer pixel brightness determining step through the convergence criterion determining step if the convergence criterion is not met.