# US 6,731,822 B1 · Method and apparatus for filtering images having insufficient tonal precision

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 6,731,822 B1
- Document ID: US6731822B1
- Status: Granted
- Kind: B1
- Application number: 09/429,245
- Filed: 1999-10-28
- Granted: 2004-05-04
- Earliest claimed: 1999-10-28
- Assignees: Hewlett-Packard Development Company, L.P.
- Inventors: Irwin Sobel; Ronny Kimmel
- Web page: https://patentgrep.com/patent/US6731822B1

## CPC

- G06T 5/70: Denoising; Smoothing
- G06T 2207/20016: Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

An array of n-bit words representing an image is filtered to produce a corresponding array of higher precision m-bit words representing the image. During the filtering, upper and lower bounds for the m-bit words are identified, and values for the m-bit words are selected between the upper and lower bounds. There is at least some spatial smoothness between the selected values. For example, the values may be selected at sample points of a curve or surface between the upper and lower bounds.

## Claims

### Claim 1

A method of filtering a signal representing an array of n-bit words to produce a signal representing a corresponding array of m-bit words, where m and n are integers and m>n, the method comprising:
identifying upper and lower bounds of each m-bit word; and
selecting values for the m-bit words between the upper and lower bounds, there being at least some spatial smoothness between the selected values;
the lower bound of a given m-bit word having its n most significant bits equal to the corresponding n-bit word;
the upper bound of a given n-bit word being equal to a sum of a maximum uncertainty and the lower bound of the given m-bit word.

### Claim 2 (depends on 1)

The method of claim 1, wherein the values are selected by generating a sequence of curves within the upper and lower bounds of the m-bit words; and selecting values for the m-bit words at sample points on the curves.

### Claim 3 (depends on 1)

The method of claim 1, wherein the lower bound of a given m-bit word equals a product of 2m−n and the value of the corresponding n-bit word; and wherein each quantization uncertainty has 2m−n subintervals and a maximum uncertainty of 2m−n−1.

### Claim 4 (depends on 1)

The method of claim 1, wherein the values of a plurality of m-bit words are selected by
identifying a first change point in the array;
skipping a constant run of lower bounds following the first change point;
identifying a second change point at the end of the constant run; and
interpolating values for the m-bit words in the constant run, the values of the plurality of m-bit words being interpolated between the first and second change points.

### Claim 5 (depends on 4)

The method of claim 4, wherein each change point is identified by finding first and second consecutive lower bounds having different values; and wherein a change point value is computed as a geometric center of a change region between the first and second consecutive lower bounds.

### Claim 6 (depends on 4)

The method of claim 4, wherein the interpolation is linear.

### Claim 7 (depends on 4)

The method of claim 4, further comprising the step of clipping interpolated values that are outside corresponding lower and upper bounds.

### Claim 8 (depends on 4)

The method of claim 4, further comprising:
accessing n-bit image data;
processing each row of image data by identifying first and second change points between constant runs of n-bit words, and interpolating the m-bit words in the constant runs;
transposing the image data;
processing each row of transposed image data by identifying first and second change points between constant runs of n-bit words, and interpolating the m-bit words in the constant runs;
re-transposing the processed image data; and
taking an average of the m-bit words obtained by re-transposing the processed transposed image data and the non-transposed image data, while keeping registration between the two sets of filtered data.

### Claim 9 (depends on 1)

The method of claim 1, wherein the values of the m-bit words are selected by generating an optimally smooth surface within upper and lower bounds of the m-bit words; and selecting values of the m-bit words at sample points on the optimally smooth surface.

### Claim 10 (depends on 9)

The method of claim 9, wherein the optimally smooth surface is generated by solving for
min ∫∫|∇I(x,y)|2dx dy
subject to LB(x,y)≦I(x,y)≦UB(x,y), where I(x,y) is a selected value at coordinates x and y, LB(x,y) is the lower bound at coordinates x and y, UB is the upper bound at coordinates x and y, and ∇ represents a gradient.

### Claim 11 (depends on 9)

The method of claim 9, wherein a multi-resolution pyramid of the m-bit words and the upper and lower bounds is generated; wherein
a surface is generated for a highest level of the pyramid; and wherein
the surface is refined for lower levels of the pyramid.

### Claim 12

A method of filtering a signal representing a sequence of n-bit words to produce a signal representing a corresponding array of m-bit words, where m and n are integers and m>n, the method comprising:
identifying upper and lower bounds of the m-bit words in the sequence;
identifying a first change point in the sequence;
skipping a constant run of lower bounds following the first change point;
identifying a second change point at the end of the constant run;
interpolating values for the m-bit words in the constant run, the values of the m-bit words being interpolated between the first and second change points; and
clipping any values that fall outside of the upper or lower bounds.

### Claim 13

A method of filtering a signal representing a two-dimensional array of n-bit words to produce a signal representing a corresponding two-dimensional array of m-bit words, where m and n are integers and m>n, the method comprising the steps of:
identifying upper and lower bounds of each m-bit word;
generating an optimally smooth surface between the upper and lower bounds of the m-bit words; and
selecting values of the m-bit words at sample points on the surface;
the lower bound of a given m-bit word having its n most significant bits equal to the corresponding n-bit word;
the upper bound of a given n-bit word being equal to a sum of a maximum uncertainty and the lower bound of the given m-bit word.

### Claim 14 (depends on 13)

The method of claim 13, wherein a multi-resolution pyramid of the m-bit words and the upper and lower bounds is generated;
wherein a surface is generated for a highest level of the pyramid; and
wherein the surface is refined for lower levels of the pyramid.

### Claim 15

A data system comprising:
means for generating a plurality of n-bit data words; and
means for filtering the plurality of n-bit words to produce corresponding m-bit words, the filtering being performed by identifying upper and lower bounds of the m-bit words; and selecting values of the m-bit words between the upper and lower bounds, there being at least some spatial smoothness between the selected values, the lower bound of a given m-bit word having its n most significant bits equal to the corresponding n-bit word, the upper bound of a given n-bit word being equal to a sum of a maximum uncertainty and the lower bound of the given m-bit word.

### Claim 16

Apparatus for filtering a plurality of n-bit words to produce a plurality of corresponding m-bit words, the apparatus comprising:
a processor; and
computer memory encoded with a program that, when executed, instructs the processor to identify upper and lower bounds of each m-bit word; and select m-bit word values between the upper and lower bounds, there being at least some spatial smoothness between the selected values, the lower bound of a given m-bit word having its n most significant bits equal to the corresponding n-bit word, the upper bound of a given n-bit word being equal to a sum of a maximum uncertainty and the lower bound of the given m-bit word.

### Claim 17 (depends on 16)

The apparatus of claim 16, wherein the values are selected by generating a sequence of curves within the upper and lower bounds of the m-bit words; and selecting values of the m-bit words at sample points on the curves.

### Claim 18 (depends on 17)

The apparatus of claim 17, wherein the values of a plurality of m-bit words are selected by
identifying a first change point in the sequence;
skipping a constant run of lower bounds following the first change point;
identifying a second change point at the end of the constant run; and
interpolating values for the m-bit words in the constant run, the values of the plurality of m-bit words being interpolated between the first and second change points.

### Claim 19 (depends on 18)

The apparatus of claim 18, further comprising the step of clipping interpolated values that are outside a lower bound or upper bound.

### Claim 20 (depends on 16)

The apparatus of claim 16, wherein the values of the m-bit words are selected by generating an optimally smooth surface within upper and lower bounds of each m-bit word; and selecting values of the m-bit words at sample points on the optimally smooth surface.

### Claim 21 (depends on 20)

The apparatus of claim 20, wherein the optimally smooth surface is generated by solving for
min ∫∫|∇I(x,y)|2dx dy
subject to LB(x,y)≦I(x,y)≦UB(x,y), where I(x,y) is a point on the curve at x and y, LB(x,y) is the lower bound at x and y, UB is the upper bound at x and y, and ∇ represents a gradient.

### Claim 22 (depends on 20)

The apparatus of claim 20, wherein a multi-resolution pyramid of the m-bit words and the upper and lower bounds is generated; wherein a surface is generated for a highest level of the pyramid; and wherein the surface is refined for lower levels of the pyramid.

### Claim 23

An article of manufacture for a processor of an image filter, the article comprising:
computer memory; and
a program encoded in the computer memory, the program, when executed, instructing the processor to identify upper and lower bounds of each m-bit word in an array; and select values of the m-bit words between the upper and lower bounds, there being at least some spatial smoothness between the selected values, the lower bound of a given m-bit word having its n most significant bits equal to the corresponding n-bit word, the upper bound of a given n-bit word being equal to a sum of a maximum uncertainty and the lower bound of the given m-bit word.
