Method, arrangement, computer program and computer readable storage medium for scaling two-dimensional structures
View Patent ↗A method for scaling two-dimensional structures, which is especially usable for resizing digital 2D images with a rational scaling factor, is based on efficient implementation of a diamond-shaped filter. The conventional “1”-diamond matrices of variable size are replaced by a (m×n) coefficient matrix. For any given rational scaling factor, the computational load for calculating an output pixel is reduced to filtering (m×n) input pixels with a corresponding (m×n) filter matrix. The coefficients of this filter matrix depend from the phase of the output pixel to be calculated and the factor of interpolation, but are always integer numbers. The coefficients may be stored in lookup tables (LUT), which leads to a very efficient implementation of the inventive method. In one embodiment, a (3×3) coefficient matrix has been found to be advantageous.
1. A method for scaling two-dimensional structures with a scaling factor, wherein a source structure is transformed into a target structure and the source and target structure are each constructed from regularly arranged structure elements, the method comprising:
defining a first scheme comprising structure elements P ij associated with the source structure and arranged in m rows and n columns,
subdividing at least a portion of the structure elements P ij of the first scheme into sub-structure elements arranged in p rows and q columns, with each row and each column having a corresponding sub-structure element P S kl ,
defining a second scheme P D comprising a subset of the sub-structure elements P S kl , and at least one distinguished sub-structure element P D *,
superposing the first scheme with the second scheme P D so as to overlap the at least one distinguished sub-structure element P D * step-by-step with at least a portion of the sub-structure elements P S kl of the first scheme,
for each step of superposing, constructing a coefficient matrix H kl adapt having a dimension that is independent of the scaling factor and that is assigned to the sub-structure element P S kl of the first scheme, with which the distinguished sub-structure element P D * is overlapped, wherein the coefficients h kl ij of the coefficient matrix H kl adapt define a weight of the structure element P ij of the i-th row and j-th column of the first scheme, and
defining a structure element of the target structure by evaluating at least a portion of the structure elements P ij of the first scheme and at least a portion of the matrices H kl adapt .
2. The method according to claim 1 , further comprising a scaling factor which defines at least a parameter p and q of the subdivided sub-structure elements and a step size of the step-by-step overlap.
3. The method according to claim 1 , wherein the weight indicates a measurement of the area of the structure element P ij of the i-th row and j-th column of the first scheme covered by sub-structure elements P D kl of the second scheme P D .
4. The method according to claim 3 , wherein the measurement of the covered area of the structure element P ij of the first scheme is defined as a number of sub-structure elements P S kl within the structure element P ij that overlap with sub-structure elements P D k′l , of the second scheme P D .
5. The method according to claim 1 , wherein at least a portion of the structure elements P ij of the first scheme corresponds to a block of m rows and n columns of adjacent structure elements of the source structure.
6. The method according to claim 1 , wherein the structure element of the target structure are weighted by the coefficients h kl ij of the coefficient matrix H kl adapt .
7. The method according to claim 1 , wherein the coefficients h kl ij of the coefficient matrix H kl adapt are stored in a storage area of a data processing unit.
8. The method according to claim 7 , wherein the coefficients h kl ij of the coefficient matrix H kl adapt are stored in at least one lookup table.
9. The method according to claim 1 , wherein the second scheme P D is defined as diamond-shaped filter.
10. A data processing unit configured to carry out a method for scaling two-dimensional structures with a scaling factor, wherein a source structure is transformed into a target structure and the source and target structure are each constructed from regularly arranged structure elements, by:
defining a first scheme comprising structure elements P ij associated with the source structure and arranged in m rows and n columns,
subdividing at least a portion of the structure elements P ij of the first scheme into sub-structure elements arranged in p rows and q columns, with each row and each column having a corresponding sub-structure element P S kl ,
defining a second scheme P D comprising a subset of the sub-structure elements P S kl and at least one distinguished sub-structure element P D *,
superposing the first scheme with the second scheme P D so as to overlap the at least one distinguished sub-structure element P D * step-by-step with at least a portion of the sub-structure elements P S kl of the first scheme,
for each step of superposing, constructing a coefficient matrix H kl adapt having a dimension that is independent of the scaling factor and that is assigned to the sub-structure element P S kl of the first scheme, with which the distinguished sub-structure element P D * is overlapped, wherein the coefficients h kl ij of the coefficient matrix H kl adapt define a weight of the structure element P ij of the i-th row and j-th column of the first scheme, and
defining a structure element of the target structure by evaluating at least a portion of the structure elements P ij of the first scheme and at least a portion of the matrices H kl adapt .
11. A computer program stored on a non-transitory medium and having computer program instruction which enable a computer, after the computer program is loaded into a memory of the computer, to execute a method for scaling two-dimensional structures with a scaling factor, wherein a source structure is transformed into a target structure and the source and target structure are each constructed from regularly arranged structure elements, by:
defining a first scheme comprising structure elements P ij associated with the source structure and arranged in m rows and n columns,
subdividing at least a portion of the structure elements P ij of the first scheme into sub-structure elements arranged in p rows and q columns, with each row and each column having a corresponding sub-structure element P S kl ,
defining a second scheme P D comprising a subset of the sub-structure elements P S kl and at least one distinguished sub-structure element P D *,
superposing the first scheme with the second scheme P D so as to overlap the at least one distinguished sub-structure element P D * step-by-step with at least a portion of the sub-structure elements P S kl of the first scheme,
for each step of superposing, constructing a coefficient matrix H kl adapt having a dimension that is independent of the scaling factor and that is assigned to the sub-structure element P S kl of the first scheme, with which the distinguished sub-structure element P D * is overlapped, wherein the coefficients h ki ij of the coefficient matrix H kl adapt define a weight of the structure element P ij of the i-th row and j-th column of the first scheme, and
defining a structure element of the target structure by evaluating at least a portion of the structure elements P ij of the first scheme and at least a portion of the matrices H kl adapt .
12. A non-transitory computer-readable storage medium having a computer program stored thereon which enables a computer, after the computer program is loaded in a memory of the computer, to execute a method for scaling two-dimensional structures with a scaling factor, wherein a source structure is transformed into a target structure and the source and target structure are each constructed from regularly arranged structure elements, by
defining a first scheme comprising structure elements P ij associated with the source structure and arranged in m rows and n columns,
subdividing at least a portion of the structure elements P ij of the first scheme into sub-structure elements arranged in p rows and q columns, with each row and each column having a corresponding sub-structure element P S kl ,
defining a second scheme P D comprising a subset of the sub-structure elements P S kl and at least one distinguished sub-structure element P D *,
superposing the first scheme with the second scheme P D so as to overlap the at least one distinguished sub-structure element P D * step-by-step with at least a portion of the sub-structure elements P S kl of the first scheme,
for each step of superposing, constructing a coefficient matrix H kl adapt having a dimension that is independent of the scaling factor and that is assigned to the sub-structure element P S kl of the first scheme, with which the distinguished sub-structure element P D * is overlapped, wherein the coefficients h kl ij of the coefficient matrix H kl adapt define a weight of the structure element P ij of the i-th row and j-th column of the first scheme, and
defining a structure element of the target structure by evaluating at least a portion of the structure elements P ij of the first scheme and at least a portion of the matrices H kl adapt .