Method for checking convergence in fractal image coding

• US 5,978,516 A
• Filed: 09/26/1997
• Issued: 11/02/1999
• Est. Priority Date: 10/07/1996
• Status: Expired due to Fees

• Current Assignee: Deutsche Thomson-Brandt Gmbh (Vantiva SA)
• Original Assignee: Deutsche Thomson-Brandt Gmbh (Vantiva SA)
• Inventors: Siepen, Peter, Dickopp, Gerhard
• Primary Examiner(s): Au, Amelia
• Assistant Examiner(s): Johnson, Timothy M.
• Application Number:
  US08/938,090
• Time in Patent Office: 767 Days
• Field of Search: 341/51, 345/436, 348/384, 348/390, 348/403, 348/404, 348/420, 358/426, 358/430, 358/432, 358/433, 382/232, 382/248, 382/249, 382/276
• US Class Current: 382/249
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame

Abstract

A method is proposed for checking convergence in fractal image coding. In this case, a digitized image is divided into a number of range blocks (R_i, R_i+1) and into a number of domain blocks (D_j, D_k). A similar domain block is determined in relation to each range block. If necessary, in this process a transformation of a domain block is undertaken in order to map the domain block onto a range block. The assignment of the domain block to the range block including the transformation parameters represents the fractal code for the image. A reduced transformation matrix is set up to check convergence of the fractal code. The largest absolute eigenvalue of the transformation matrix is determined approximately. The entire method can be carried out in this case hierarchically. In a first approximation step, at least the row sum norm of each row of the reduced transformation matrix is checked. In further steps, further rows are combined to form square matrices of higher dimension. The latter are used to determine the largest absolute eigenvalues for the purpose of checking convergence.

Claims

1. A method for checking convergence in fractal image coding, in which a digitized image is divided into a number of range blocks (R_i) and into a number of domain blocks (D_j), a similar domain block (D_j) being determined in relation to each range block (R_i), a transformation of a domain block (D_j) being undertaken at least in part in order to map a domain block (D_j) onto a range block (R'"'"'_i), the assignment of domain block to range block including the transformation parameters representing the fractal code, a reduced transformation matrix being set up for the purpose of checking the convergence of the fractal code, wherein checking the convergence of the fractal code comprises approximately determining the largest absolute eigenvalue of the reduced transformation matrix by checking the row sum norm (ZSN_i) of the rows of the reduced transformation matrix.

2. Method according to claim 1, it being the case that it is used in a device for fractal image coding.

3. Method according to claim 1, it being the case that it is used in a device for decoding a fractal code for an image.

4. A method for checking convergence in fractal image coding, in which a digitized image is divided into a number of range blocks (R_i) and into a number of domain blocks (D_j), a similar domain block (D_j) being determined in relation to each range block (R_i), a transformation of a domain block (D_j) being undertaken at least in part in order to map a domain block (D_j) onto a range block (R'"'"'_i), the assignment of domain block to range block including the transformation parameters representing the fractal code, a reduced transformation matrix being set up for the purpose of checking the convergence of the fractal code, said method comprising the steps of:

determining the row sum norm (ZSN_i) of the rows of the reduced transformation matrix and comparing with a predetermined value for approximately determining the largest absolute eigenvalue of the reduced transformation matrix; and

when said row sum norm of a given row is larger than said predetermined value, combining said given row with the remaining rows of the reduced transformation matrix to form a 2×

N_D matrix, N_D specifying the number of the domain blocks, transforming the 2×

N_D matrix into a 2×

2 matrix by selecting those columns which correspond to the row numbers of the reduced transformation matrix which are selected for the 2×

N_D matrix, adding the sum of the absolute values of the deleted elements of a row to the main diagonal element which belongs to the row when this main diagonal element is greater than zero, subtracting the sum of the absolute values of the deleted elements of a row from the main diagonal element when this main diagonal element is smaller than zero, and determining at least the largest absolute eigenvalue of the 2×

2 matrix.

5. The method according to claim 4, wherein the largest absolute eigenvalue of the 2×

2 matrix is determined by means of the von Mises method.

6. The method according to claim 4, wherein when the absolute value of the largest absolute eigenvalue of a 2×

2 matrix is larger than the predetermined value, said method further comprises the steps of setting up all associated 3×

3 matrices, the 3×

3 matrices being produced by combining the rows of reduced transformation matrix which produce the 2×

N_D matrix with each of the remaining rows of the reduced transformation matrix to form 3×

N_D matrices and are transformed into a 3×

3 matrix by omitting the column elements which do not correspond to the participating rows, it being the case that the sum of the absolute values of the non-adopted column elements of a row is in each case again added to the main diagonal element of the corresponding row when the main diagonal element is greater than or equal to zero, and is subtracted from the main diagonal element when the main diagonal element is smaller than zero, and determining at least the largest absolute eigenvalue of the respective 3×

3 matrix.

7. The method according to claim 6, wherein when the absolute value of the largest absolute eigenvalue of a 3×

3 matrix is larger than a predetermined value, said method further comprises the steps of setting up associated square matrices of next higher dimension in a corresponding way, and checking the largest absolute eigenvalue of said associated square matrices.

8. The method according to claim 6, wherein when the largest absolute eigenvalue of the 3×

3 matrix is larger than a predetermined value, said method further comprises the step of adjusting the transformation parameters of the range blocks participating in the 3×

3 matrix to depress the largest absolute eigenvalue below the predetermined value.

9. The method according to claim 4, wherein when the largest absolute eigenvalue of the 2×

2 matrix is larger than a predetermined value, said method further comprises the step of adjusting the transformation parameters (a₁) of the range blocks participating in the 2×

2 matrix to depress the largest absolute eigenvalue below the predetermined value.

10. A method for checking convergence in fractal image coding, in which a digitized image is divided into a number of range blocks (R_i) and into a number of domain blocks (D_j), a similar domain block (D_j) being determined in relation to each range block (R_i), a transformation of a domain block (D_j) being undertaken at least in part in order to map a domain block (D_j) onto a range block (R'"'"'_i), the assignment of domain block to range block including the transformation parameters representing the fractal code, a reduced transformation matrix being set up for the purpose of checking the convergence of the fractal code, said method comprising the steps of:

determining the row sum norm (ZSN_i) of the rows of the reduced transformation matrix and comparing with a predetermined value for approximately determining the largest absolute eigenvalue of the reduced transformation matrix, wherein when the row sum norm of a row of the reduced transformation matrix is greater than a predetermined value, the transformation parameters for the participating range blocks are adjusted to depress the row sum norm below the predetermined value.

11. A method for checking convergence in fractal image coding, in which a digitized image is divided into a number of range blocks (R_i) and into a number of domain blocks (D_j), a similar domain block (D_j) being determined in relation to each range block (R_i), a transformation of a domain block (D_j) being undertaken at least in part in order to map a domain block (D_j) onto a range block (R'"'"'_i), the assignment of domain block to range block including the transformation parameters representing the fractal code, a reduced transformation matrix being set up for the purpose of checking the convergence of the fractal code, said method comprising the steps of:

determining the row sum norm (ZSN_i) of the rows of the reduced transformation matrix and comparing with a predetermined value for approximately determining the largest absolute eigenvalue of the reduced transformation matrix, it being the case that, when it is established that one of a predetermined convergence criteria is not fulfilled, a new assignment of domain blocks (D_j) is made at least for the participating range blocks (R_i) and new associated transformation parameters are determined to depress the largest absolute eigenvalue of the reduced transformation matrix below the predetermined value.