Method of isomorphic singular manifold projection still/video imagery compression

• US 7,747,085 B2
• Filed: 12/21/2000
• Issued: 06/29/2010
• Est. Priority Date: 07/28/1997
• Status: Active Grant

• Current Assignee: Mercury Mission Systems LLC (Mercury Systems, Incorporated)
• Original Assignee: Physical Optics Corporation
• Inventors: Jannson, Tomasz P., Ternovskiy, Igor, Kostrzewski, Andrew
• Primary Examiner(s): SHERALI, ISHRAT I
• Application Number:
  US09/745,363
• Publication Number:
  US 20020015532A1
• Time in Patent Office: 3,477 Days
• Field of Search: 382232-253, 382/108, 382/276, 3752401-24027, 35842601-42616, 345418-428, 345581-588
• US Class Current: 382/232
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame

Abstract

Methods and apparatuses for still image compression, video compression and automatic target recognition are disclosed. The method of still image compression uses isomorphic singular manifold projection whereby surfaces of objects having singular manifold representations are represented by best match canonical polynomials to arrive at a model representation. The model representation is compared with the original representation to arrive at a difference. If the difference exceeds a predetermined threshold, the difference data are saved and compressed using standard lossy compression. The coefficients from the best match polynomial together with the difference data, if any, are then compressed using lossless compression. The method of motion estimation for enhanced video compression sends I frames on an “as-needed” basis, based on comparing the error between segments of a current frame and a predicted frame. If the error exceeds a predetermined threshold, which can be based on program content, the next frame sent will be an I frame. The method of automatic target recognition (ATR) including tracking, zooming, and image enhancement, uses isomorphic singular manifold projection to separate texture and sculpture portions of an image. Soft ATR is then used on the sculptured portion and hard ATR is used on the texture portion.

Claims

1. A method of compressing a still image comprising:

identifying at least one catastrophe in said image;

representing said catastrophe with a canonical polynomial; and

transforming said canonical polynomial into datery as compressed data.

2. A method of compressing an image comprising:

segmenting the image into blocks of pixels;

creating a canonical polynomial surface for at least one catastrophe in at least one of said blocks of pixels; and

transforming said canonical polynomial into datery as compressed data.

3. The method of claim 2, further comprising:

creating a modeled surface of the image with the canonical polynomial, said modeled surface being isomorphically related to the image.

4. The method of claim 2, wherein a model image is generated from said canonical polynomial which is a best match canonical polynomial selected based on a difference between an original image and said model image.

5. The method of claim 2, wherein a model image is generated from said canonical polynomial which is a best match canonical polynomial selected based on a difference between the original still image and said model image.

6. The method of claim 5, wherein said difference is calculated using the equation:

$Q=\sqrt{\frac{1}{\mathrm{MN}}}<br><br>\stackrel{M-1}{\underset{x=0}{\sum <br><br>}}<br><br>\stackrel{N-1}{\underset{=0}{\sum <br><br>}}<br><br>{\left(i_0<br><br>\left(x,y\right)-i_m<br><br>\left(x,y\right)\right)}^2.$

wherein Q is the difference, M is the number of rows in an image, N is the number of columns in the image, x is an x-coordinate of a pixel, y is an y-coordinate of the pixel, i₀ is a function that returns a pixel from a segment of the original still image, and i_m is a function that returns a pixel from a segment of the model image.

7. The method of claim 5, wherein a transformation is applied to said selected canonical polynomial to obtain a function describing a model surface.

8. The method of claim 7, wherein said transformation is a non-homogeneous linear transformation.

9. The method of claim 8, wherein said non-homogeneous linear transformation takes the form:

$f_{\mathrm{cononical}}=x_1^3+x_1+x_2.$

wherein x₁ takes the form;

$x_1=\left(y_1+a_1<br><br>y_1^2+\mathrm{\dots <br><br>}<br><br><br><br>a_n<br><br>y_n^2\right);<br><br>$

and

wherein x₂ takes the form;

$x_2=\left(y_2+b_2<br><br>y_2^2+\mathrm{\dots <br><br>}<br><br><br><br>b_n<br><br>y_n^2\right).$

10. A method of still image encoding comprising the following steps:

(a) capturing a frame;

(b) dividing said frame into segments of pixels;

(c) determining the dynamic range of a segment by subtracting the intensity of the pixel having maximum intensity from the intensity of the pixel having minimum intensity in said segment;

(d) comparing said dynamic range to a threshold below which said segment is likely to represent background;

(e) selecting a canonical polynomial from a table if said threshold in (d) above is exceeded;

(f) compressing said segment using standard texture compression techniques and storing the result if the threshold of step (d) is not exceeded;

(g) performing a transformation on said canonical polynomial to obtain an equation representing a modeled surface;

(h) substituting the coordinates of each pixel from said segment into said equation representing said modeled surface to obtain a matrix of modeled surface elements of said segment;

(i) calculating the overall quality of the modeled surface of said segment compared with said original segment by (1) subtracting the difference between the pixels of said original segment and corresponding pixels of said modeled surface (2) squaring said differences (3) summing up all of said squares and (4) taking the square root of said sum to arrive at a quality determination for said modeled surface;

(j) comparing said quality determination of step (i) to a predetermined threshold;

(k) selecting new coefficients for said canonical polynomial if said quality determination is greater than said predetermined threshold of step

     0) and repeating steps (i) and

     0) until a best quality determination, less than said predetermined threshold of step (i) is achieved;

(l) storing said best quality determination for said canonical polynomial and said coefficients that produced said best quality determination;

(m) repeating steps (f-1) for polynomials not yet tested until all canonical polynomials from said table have been tested for said segment;

(n) determining the polynomial having the overall best quality determination of the polynomials tested for said segment to arrive at a selected polynomial for said segment;

(o) storing the coefficients for said selected polynomial representing a model surface for said segment;

(p) selecting a next segment of said frame and performing steps (c) through (o) on all such next segments until all segments of the frame have been selected;

(q) calculating the average distance between said model surface of said segment and each adjacent segment of said frame to determine if connections to neighboring segments can be made;

(r) comparing the average distances determined in the preceding step to a threshold average distance;

(s) extending said model surface to adjacent segments if the average distance between such segments is less than said threshold average distance;

(t) calculating a spline to approximate the surface of adjacent segments if the average distance for any such segment exceeds said threshold average distance to form a graph;

(u) constructing a model image of the entire frame by creating a table of all of the data representing the modeled segments to obtain a matrix describing the entire modeled frame surface;

(v) calculating the peak signal to noise ratio over the entire frame;

(w) comparing the peak signal to noise ratio of the entire frame to a signal to noise threshold;

(x) calculating a difference frame by subtracting the value of each pixel of the model image from each pixel of the original captured frame if the peak signal to noise ratio exceeds said signal to noise threshold;

(y) compressing the difference frame, if any, using standard lossy compression methods; and

(z) compressing the frame data comprising the coefficients for said selected polynomials, and said compressed difference frame, if any.

11. The method of claim 10, further comprising applying a non-homogeneous linear transformation to obtain said matrix of modeled surface elements of said segment.

12. The method of claim 10, further comprising applying a homogeneous linear transformation to obtain said matrix of modeled surface elements of said segment.

13. The method of claim 10, further comprising applying a non-homogeneous nonlinear transformation to obtain said matrix of modeled surface elements of said segment.

14. The method of claim 10, wherein said step of segmenting said frame into blocks of pixels comprises segmenting into blocks that are fixed in size.

15. The method of claim 10, wherein said step of segmenting said frame into blocks of pixels comprises segmenting into blocks that are variable in size.