US 6,069,661 AGrant
Method and Arrangement for Computing Pixel Values of Pixels of a Digital Picture Signal That Are Arranged Outside a Two-Dimensional Scanning Raster
Issue Date:2000-05-30
•7 Claims
•3 Drawing Sheets
Abstract
A method and arrangement for computing values of pixels arranged outside a 2-dimensional scanning raster of pixels having pixel values of a digital picture signal, where at least 3 of 4 reference pixels arranged around the searched pixel are determined for computing a searched pixel value s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y). A polynomial p(x,y) in the form c.sub.m-1 x.sup.am-1 y.sup.bm-1 +c.sub.m-2 x.sup.am-2 y.sup.bm-2 + . . . +c.sub.2 x+c.sub.1 y+c.sub.0 is constituted corresponding to their values. Next, k 1st derivatives .delta.s(x,y)/.delta.x in the x-direction and .delta.s(x,y)/.delta.x in the y-direction are formed from at least one of the reference pixel values. Then, a matrix is formed whose elements consist of the values of the basic functions x.sup.am-1 y.sup.bm-1,x.sup.am-2 y.sup.bm-2, . . . x,y,1 of the polynomial at at least 3 of the reference pixels and the k 1st derivatives .delta.p(x,y)/.delta.x in the x-direction and .delta.p(x,y)/.delta.y in the y-direction of the basic functions at at least one of the reference pixel values. The basic functions are allocated to a reference pixel or a 1st derivative of a reference pixel in one matrix row. An inverse or pseudo-inverse matrix is formed from the matrix by means of inversion and multiplied by an observation vector for determining the polynomial coefficients c.sub.m-1 through c.sub.0. The polynomial coefficients are introduced into polynomial p(x,y) and the new pixel value s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y) is computed from the function value of the polynomial p(.DELTA.x,.DELTA.y) at the location (.DELTA.x, .DELTA.y).
Metadata
Assignee
- U.S. Philips Corporation
Inventor
- Achim Ibenthal
Application Information
Application Number:US 0702188
Filing Date:1998-04-30
Priority Date:1997-05-02
Art Unit:271
Classifications
IPC:
H04N 701
Field of Search:
348382441;581;571;625250;278;298-300;260
Patent Drawings (3 sheets)
Description
Background of the Invention
The invention relates to a method and an arrangement for computing values s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y) of pixels which are arranged outside a two-dimensional scanning raster {x.sub.0 .+-.n, y.sub.0 .+-.m, with m,n=0,1,2,3, . . . } of pixels having pixel values s(x.sub.0 .+-.n,y.sub.0 .+-.m) of a digital picture signal.
In such methods and arrangements for computing new pixel values, it is important to determine the values of pixels which are located outside a two-dimensional scanning raster. The known pixels are situated at locations (x.sub.0 .+-.n,y.sub.0 .+-.m) in which m and n are integers of zero up to a maximal value. The pixels of a digital picture signal which are located in this scanning raster have known pixel values. By way of non-limitative example, it is herein assumed that the distance between two adjacent pixels is 1 in the horizontal and vertical directions.
For example, for the purpose of television signal conversion, conversion between different graphic modes in PCs, video data compression, or for medical applications, it is often desirable or necessary to determine pixel values of pixels which are not located at the predetermined points on the two-dimensional scanning raster but are located between these points. Fundamentally, the searched pixel values may have arbitrary positions between the points on the scanning raster. This complicates their computation.
In the state of the art, methods are known which are based on bilinear or bicubic interpolation for computing such new pixel values in their simplest case. In bilinear interpolation, a linear weighting of the four pixels located closest to a searched pixel in the scanning raster is performed. In the interpolation by means of cubic B-splines, an ideal interpolation filter is approximated by means of a sin(x)/x-shaped pulse response for the one-dimensional case by means of a 3rd-order polynomial, which minimizes the interpolation error, but strongly reduces the resolution. Cf. K. Pratt: "Digital Image Processing", second edition, pp. 114 etc.
For computing new pixel values, it is further possible to perform a combined up and down-sampling.
EP-A-660 514 discloses a filter which operates as a one-dimensional polynomial interpolator and in which a one-dimensional polynomial is set up which should approximate the pixel values located outside a one-dimensional scanning raster as satisfactorily as possible.
Summary of the Invention
It is an object of the invention to provide a method and an arrangement allowing the computation of pixels which are located outside a two-dimensional scanning raster. The computation should be as accurate as possible and yet performed with a reasonable number of components.
For a method according to the invention, this object is solved in that for computing a searched pixel value s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y), at least three pixel values s(x.sub.0,y.sub.0), s(x.sub.0,y.sub.0 +1), s(x.sub.0 +1,y.sub.0) and s(x.sub.0 +1,y.sub.0 +1) of four reference pixels arranged around the searched pixel are determined,
a polynomial p(x,y) of the form
is constituted which, at the positions of at least three of the four reference pixels should correspond to their values, so that p(0,0)=s(x.sub.0,y.sub.0), p(1,0)=s(x.sub.0 +1,y.sub.0), p(0,1)=s(x.sub.0,y.sub.0 +1) and/or p(1, 1)=s(x.sub.0 +1,y.sub.0 +1),
the k first derivatives .delta.s(x,y)/.delta.x in the x-direction and .delta.s(x,y)/.delta.y in the y-direction are formed from at least one of the reference pixel values,
a matrix is formed, whose elements consist of the values of the basic functions
of the polynomial at at least three of the reference pixels and the k first derivatives .delta.p(x,y)/.delta.x in the x-direction and .delta.p(x,y)/.delta.y in the y-direction of the basic functions at least one of the reference pixels, the basic functions allocated to a reference pixel or to a first derivative of a reference pixel being in one row of the matrix,
an inverse or pseudo-inverse matrix is formed from the matrix by means of inversion,
the inverse or pseudo-inverse matrix is multiplied by an observation vector for determining the polynomial coefficients c.sub.m-1, c.sub.m-2, . . . , c.sub.2, c.sub.1, c.sub.0, which vector comprises as elements at least three of the reference pixel values and the k first derivatives .delta.s(x,y)/.delta.x in the x-direction and .delta.s(x,y)/.delta.y in the y-direction of at least one of the reference pixels,
the polynomial coefficients are introduced into the polynomial p(x,y) and the new pixel value s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y) is computed by computing the function value of the polynomial p(.DELTA.x,.DELTA.y) at the location (.DELTA.x,.DELTA.y).
In the method according to the invention, a polynomial is set up which maximally approximates the values of four pixels which are located in the two-dimensional scanning raster and whose values are known. Moreover, the polynomial should maximally approximate the k.sup.th derivatives of these pixels. Such a computed polynomial allows a reasonably accurate determination of pixel values which are arranged in the square between the four known pixels.
For a searched pixel value s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y), the values of four reference pixels arranged around this searched pixel are first determined. These are the pixels which are closest to the searched pixel in the two-dimensional scanning raster and whose values are known. A polynomial of the above-mentioned form is set up, which, as a target, should maximally approximate the pixel values of these four reference pixels.
For example, for the reference pixel value s(x.sub.0,y.sub.0), the polynomial should yield its pixel value when the values 0 for x and 0 for y are introduced in the polynomial. The polynomial should yield the reference pixel value s(x.sub.0 +1,y.sub.0) when the values 1 for x and 0 for y are introduced in the polynomial. A corresponding situation is valid for the two further reference pixel values.
The k first derivatives .delta.s(x,y)/.delta.x and .delta.s(x,y)/.delta.y are formed from at least one of the reference pixel values. The polynomial should maximally approximate also these values of the derivatives so that the derivative of the polynomial for each pixel is equal to the corresponding derivative of the pixel value itself.
It is generally sufficient when the first derivatives in the x and y-directions are formed for one of the reference pixels and when the polynomial for one of these reference pixel values maximally approximates its derivative.
The above polynomial is initially present in a general form; for computing the searched pixel value s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y), particularly the polynomial coefficients c.sub.m-1, c.sub.m-2, . . . , c.sub.2, c.sub.1, c.sub.0 are to be determined. To this end, a matrix is formed whose values only consist of the basic functions of the polynomial. In this matrix, the polynomial coefficients thus do not occur but only the other elements of the polynomial occur. The polynomial is then set up for at least three of the reference pixel values and for the first derivatives in the x and y-directions at at least one of the reference pixel values. The basic functions are set up within the matrix in such a way that, within a row of the matrix, the basic functions allocated to one reference pixel value or to a first derivative of a reference pixel value are arranged in the same sequence as in the polynomial. Thus, the basic functions of the polynomial of at least three of the reference pixel values and of at least the first derivatives in the x and y-directions of at least one of the reference pixel values are line-sequentially present within the matrix.
An inverse or pseudo-inverse matrix which is multiplied by means of an observation vector is formed from this matrix by means of inversion. The observation vector line-sequentially has the corresponding values of the reference pixels themselves and the corresponding derivatives of the reference pixels. The lines within the vector and within the inverse matrix are allocated to the same reference pixels or reference pixel derivatives.
The polynomial coefficients c.sub.m-1, c.sub.m-2, . . . , c.sub.2, c.sub.1, c.sub.0 are computed by multiplying the inverse matrix by the observation vector.
The polynomial coefficients can now be introduced into the polynomial p(x,y).
The values .DELTA.x and .DELTA.y are introduced into the polynomial for the searched pixel value s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y). The polynomial is now computed and yields, as a result, the searched pixel value s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y).
A very good approximation of the searched pixel value is found by means of this two-dimensional polynomial computation of this value. Nevertheless, the number of components required for the computation remains reasonable, because some of the above-mentioned computation steps do not need to be repeated for each pixel value. Only the new values to be introduced for the reference pixels and their first derivatives are to be determined each time. The polynomial in its basic form, as well as the inverse matrix, are, however, maintained for changing (.DELTA.x,.DELTA.y). Moreover, the polynomial values p(0,0), p(1,0), p(0,1) and p(1,1) remain identical because the searched pixel value is introduced in such a way that it is arranged at the location x.sub.0 +.DELTA.x and y.sub.0 +.DELTA.y. Independent of the fact where the searched pixel value is arranged in a two-dimensional raster, the quadrant of reference pixel values is always set up with these values, while only the relative location within this quadrant is re-introduced by the values .DELTA.x and .DELTA.y for the searched pixel value.
An embodiment of the invention is characterized in that for forming the matrix, the first derivatives .delta.p(x,y)/.delta.x in the x-direction and .delta.p(x,y)/.delta.y in the y-direction are formed from one of the reference pixel values, preferably the reference pixel value s(x.sub.0,y.sub.0), and that the observation vector comprises the four reference pixel values s(x.sub.0,y.sub.0), s(x.sub.0,y.sub.0 +1), s(x.sub.0 +1,y.sub.0) and s(x.sub.0 +1,y.sub.0 +1) and the first derivatives .delta.s(x,y)/.delta.x in the x-direction and .delta.s(x,y)/.delta.y in the y-direction of one of the reference pixels, preferably the reference pixel value s(x.sub.0,y.sub.0).
For the computation explained above, it is fundamentally sufficient to take the four reference pixel values and the first derivatives in the x and y-directions of one of the reference pixel values into account. In this case, already very good approximations of the searched pixel value are obtained, without using elaborate computations.
According to the invention, the object mentioned hereinbefore is solved for an arrangement in that
first computing means are provided, which
constitute a polynomial (p(x,y) of the form
which, at the positions of at least three of the four reference pixels should correspond to their values, so that p(0,0)=s(x.sub.0,y.sub.0), p(1,0)=s(x.sub.0 +1,y.sub.0), p(0,1)=s(x.sub.0,y.sub.0 +1) and/or p(1,1)=s(x.sub.0 +1,y.sub.0 +1),
form a matrix whose elements consist of the values of the basic functions
of the polynomial at at least three of the reference pixels and the k first derivatives .delta.p(x,y)/.delta.x in the x-direction and .delta.p(x,y)/.delta.y in the y-direction of the basic functions at least one of the reference pixels, the basic functions allocated to a reference pixel or to a first derivative of a reference pixel being in one row of the matrix,
form an inverse or pseudo-inverse matrix from the matrix by means of inversion,
differentiators are provided which form the k first derivatives .delta.s(x,y)/.delta.x in the x-direction and .delta.s(x,y)/.delta.y in the y-direction from at least one of the reference pixel values,
second computing means are provided, which
for computing a searched pixel value s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y), receive at least three pixel values s(x.sub.0,y.sub.0), s(x.sub.0,y.sub.0 +1), s(x.sub.0 +1,y.sub.0) and s(x.sub.0 +1,y.sub.0 +1) of four reference pixels arranged around the searched pixel,
multiply the inverse or pseudo-inverse matrix by an observation vector for determining the polynomial coefficients c.sub.m-1, c.sub.m-2, . . . , c.sub.2, c.sub.1, c.sub.0, which vector comprises as elements at least three of the reference pixel values and the k first derivatives .delta.s(x,y)/.delta.x in the x-direction and .delta.s(x,y)/.delta.y in the y-direction of at least one of the reference pixels,
and introduce the polynomial coefficients into the polynomial p(x,y) and compute the new pixel value s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y) by computing the function value of the polynomial p(.DELTA.x,.DELTA.y) at the location (.DELTA.x,.DELTA.y).
This arrangement operates in accordance with the method described hereinbefore. For the arrangement, the fact that not all of the above-mentioned computations have to be repeated for computing a new pixel value, may be utilized to advantage.
Therefore, first computing means are provided in the arrangement, which set up the polynomial, compute the polynomials at the four reference pixel values and form the matrix and the inverse matrix. These means may be implemented in such a way that they perform these computations only once.
Furthermore, differentiators are provided which perform the required first derivations.
With the aid of second computing means, a searched pixel value s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y) is computed in the manner described above. The computations performed by the computing means are to be repeated each time for one searched pixel value s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y).
Dependent on their realization, the means for computing the polynomial, its values and the matrices may be implemented in such a way that they are realized in the computing means. This means that the computing means are implemented in such a way that the computations of the polynomial, its values and the matrices are implicitly realized in their structure.
The arrangement according to the invention is further characterized in that the differentiators in the frequency range for forming the k.sup.th derivative approximatively have the transfer function H=(j.omega.).sup.k, in which .omega. is the local frequency in the x-direction or the y-direction, dependent on whether the derivative is to be realized in the x-direction or the y-direction. A very good approximation of the derivative values is achieved by this implementation of the transfer function.
In accordance with a further embodiment of the invention, the differentiators comprise successively arranged delay elements, and that adders are provided which receive, within the differentiator, each time those signals which are multiplied by coefficients of the same value, the adders preceding a multiplier performing the multiplication by the allocated coefficients, and the output signals from the multipliers are added by means of an adder which supplies the output signal of the differentiator.
Since the above-mentioned transfer function can be performed by multiplication of pixel values delayed by several values and since pixel values delayed by several values are to be multiplied by the same coefficients, this differentiator structure limits the number of components to a maximal extent.
A further embodiment of the arrangement according to the invention is characterized in that
the values s(x.sub.0 .+-.n,y.sub.0 .+-.m) are applied to a series arrangement of line memories whose output signals supply pixel values s(x.sub.0 +3,y.sub.0+ 2), s(x.sub.0 +3,y.sub.0 +1), . . . , s(x.sub.0 +3,y.sub.0 -3),
a first delay element is provided which receives the pixel value s(x.sub.0 +3,y.sub.0 +1) and supplies the pixel value s(x.sub.0 +1,y.sub.0 +1) from its output,
a second delay element is provided which receives the pixel value s(x.sub.0 +1,y.sub.0 +1) and supplies the pixel value s(x.sub.0,y.sub.0 +1) from its output,
a third delay element is provided which receives the pixel value s(x.sub.0 +3,y.sub.0) and supplies the pixel value s(x.sub.0 +1,y.sub.0) from its output,
a fourth delay element is provided which receives the pixel value s(x.sub.0 +1,y.sub.0) and supplies the pixel value s(x.sub.0,y.sub.0) from its output,
a first differentiator is provided which receives the pixel values s(x.sub.0 +3,y.sub.0 +3), s(x.sub.0 +3,y.sub.0 +2), . . . , s(x.sub.0 +3,y.sub.0 -3) and performs a first derivation .delta.s(x,y)/.delta.y.vertline.(x.sub.0 +3,y.sub.0) of the pixel value s(x.sub.0 +3,y.sub.0) in the y-direction,
a fifth delay element is provided which receives the first derivative in the y-direction at the location (x.sub.0 +3,y.sub.0) and supplies from its output the third derivative of the pixel values in the y-direction at the location (x.sub.0,y.sub.0),
a second differentiator is provided which receives the pixel value s(x.sub.0 +3,y.sub.0) and performs a first derivation .delta.s(x,y)/.delta.x.vertline.(x.sub.0,y.sub.0) of the pixel value in the x-direction,
the computing circuit comprises a superposition stage by means of which the pixel values and first derivatives s(x.sub.0,y.sub.0), s(x.sub.0,y.sub. +1), s(x.sub.0 +1,y.sub.0), s(x.sub.0 +1,y.sub.0 +1),.delta.s(x,y)/.delta.x.vertline.(x.sub.0,y.sub.0) and .delta.s(x,y)/.delta.y.vertline.(x.sub.0,y.sub.0) are superimposed in accordance with the inverse matrix in such a way that the superposition stage supplies the coefficients from its output,
the computing circuit comprises multipliers by means of which the coefficients are multiplied by the polynomial basic functions which are generated from .DELTA.x and .DELTA.y,
and the output signals from the multiplier are added by means of an adder stage in the computing circuit, which adder stage supplies the value of the searched pixel s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y) from its output.
This arrangement consisting of the line memories, the delay elements and the differentiators supplies the required values to the second computing circuit which requires these values for setting up the observation vector. The computation of the coefficients is then performed by corresponding fixed combinations in the superposition stage. The superposition stage supplies the coefficients of the polynomial from its output. The coefficients are subsequently multiplied by the polynomial basic functions which are generated from .DELTA.x and .DELTA.y of the searched pixel value s.sub.i. The combination of these products by means of the adder stage then yields the searched pixel value s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y).
In this arrangement, the first computing means are integrated in the second computing means in such a way that the second computing circuit and its superposition stage have such a structure that implicitly a computation of the values in accordance with the polynomial or its k first derivatives is performed. Moreover, the combinations in the superposition stage are chosen to be such that the inverse or pseudo-inverse matrix is realized by predetermined combinations of the pixel values or their first derivatives.
In this arrangement, the first computing circuit does not explicitly appear but is realized by the structure of the second computing circuit. This is possible because the computations of the first computing circuit do not need to be individually performed for pixel values but represent general computing prescriptions which can be realized by the structure of the second computing circuit.
Brief Description of the Drawings
These and other aspects of the invention are apparent from and will be elucidated with reference to the embodiments described hereinafter.
In the drawings:
FIG. 1 shows diagrammatically a two-dimensional scanning raster with one searched pixel value and four reference pixel values,
FIG. 2 shows diagrammatically the mode of operation of an arrangement for computing pixel values,
FIG. 3 is a block diagram of an arrangement for computing pixel values according to the invention, and
FIG. 4 is a block diagram of a differentiator which can be used in the arrangement of FIG. 3 for computing pixel values.
Detailed Description of the Preferred Embodiments
FIG. 1 shows a two-dimensional scanning raster with pixel values s(x,y). The section of the scanning raster of FIG. 1 shows raster points x.sub.0 -1, x.sub.0, x.sub.0 +1 and x.sub.0 +2 in the x-direction. In the y-direction, this scanning raster shows raster values y.sub.0 -1, y.sub.0, y.sub.0 +1 and y.sub.0 +2.
It is assumed that a pixel value s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y) is searched. The searched pixel value s.sub.i is thus arranged within a square which has reference pixel values s(x.sub.0,y.sub.0), s(x.sub.0,y.sub.0 +1), s(x.sub.0 +1, y.sub.0) and s(x.sub.0 +1,y.sub.0 +1).
Independent of the fact that where the searched pixel value s.sub.i is actually located within the two-dimensional raster, its location in the two-dimensional scanning raster is always computed on the basis of a reference pixel s(x.sub.0,y.sub.0). This means that the pixels arranged around the searched pixel s.sub.i always have the above-mentioned raster values.
FIG. 2 shows a coarse block diagram of an arrangement for computing the searched pixel value s.sub.i. The values of the pixels of the two-dimensional scanning raster s(x,y) are applied to differentiators 1, 2 to 3 arranged one behind the other in the arrangement and performing a derivation of the received pixel values in the x-direction. An overall number of k such differentiators may be provided. Furthermore, the differentiators 4, 5 to 6 are provided which perform derivations of the received pixel values in the y-direction of the two-dimensional scanning raster. Here again, as many differentiators 4 to 6 are provided as first derivations are to be performed.
The output values of all differentiators 1 to 6 are applied to a circuit block 7 which forms an observation vector from the values of the reference pixel values themselves as well as from their k first derivatives.
Furthermore, a polynomial of the form
is set up in the circuit block 7. A matrix is also formed, whose elements consist of the values of the basic functions
of the polynomial at the reference pixels and the k first derivatives. The basic functions allocated to the reference pixel or to one of the k first derivatives of a reference pixel are arranged within a row of the matrix. In the arrangement, an inverse or pseudo-inverse matrix A.sup.31 is formed from this matrix. This matrix is multiplied by the observation vector and supplies the polynomial coefficients c.sub.m-1, c.sub.m-2, . . . , c.sub.2, c.sub.1, c.sub.0 at its output. This signal represents the output signal of the circuit block 7 which is applied to a second circuit block 8 in which a computation of the above-mentioned polynomial is performed for the searched pixel value s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y) in that the coefficients are introduced into the polynomial and the function value of the polynomial is determined by introducing the values .DELTA.x and .DELTA.y. The result of this polynomial thus computed yields the pixel value s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y).
The above-mentioned polynomial of the form
should maximally approximate the values of the four reference pixels s(x.sub.0,y.sub.0), s(x.sub.0,y.sub.0 +1), s(x.sub.0 +1,y.sub.0) and s(x.sub.0 +1,y.sub.0 +1). Moreover, the k first derivatives of this polynomial at at least one of the reference pixels should maximally approximate the k first derivatives of the values of the corresponding reference pixels.
This will be explained hereinafter, assuming that for the computation of a searched pixel s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y) the four reference pixel values s(x.sub.0,y.sub.0), s(x.sub.0,y.sub.0 +1), s(x.sub.0 +1,y.sub.0) and s(x.sub.0 +1,y.sub.0 +1) arranged around this searched pixel are used for this computation. Moreover, only the first derivative of the reference pixel s(x.sub.0,y.sub.0) in the x and y-directions are used.
A matrix is formed whose elements consist of the values of the basic functions
of the polynomial and the four reference pixel values and the first derivative of the basic functions of the polynomial at the reference pixel value s(x.sub.0,y.sub.0). The basic functions are arranged line-sequentially for the four reference pixel values and the first derivatives in the x and y-directions.
For the general case in which .delta.p(x,y)/.delta.x and .delta.p(x,y)/.delta.y are used for the polynomial p(x,y) and for the first derivatives, it should hold that: ##EQU1## This equation may be set up in this form because the basic functions which are present in the matrix and are multiplied by the allocated polynomial coefficients should yield the polynomials and the derivatives of the polynomials again.
For the special, simplified case in which the above-mentioned four reference pixels and the first derivatives of one of the reference pixels are used for computing a pixel value s.sub.i, this equation is as follows: ##EQU2## By using the reference pixel values and the first derivatives of one of the reference pixel values in the basic functions, the matrix is simplified in which there are only zeros and ones left.
For the special case assumed for this equation in which only the values of the four reference pixels and the first derivatives in the x and y-directions of one of the reference pixel values are used, the above-mentioned polynomial can be simplified to the form
Since in the equation (2) shown above, the coefficients c.sub.0 to c.sub.5 are initially unknown, the equation (2) is solved in accordance with the vector with the coefficients c.sub.5 to c.sub.0. Then the following equation is obtained ##EQU3## Since the polynomial should maximally approximate the values of the reference pixels and the first derivatives in the manner described above, equation (4) can be written as: ##EQU4##
In this equation, the matrix set up with the basic functions is now an inverse or pseudo-inverse matrix. The vector comprising the pixel values and their first derivatives as elements will hereinafter be referred to as observation vector. By multiplication of this observation vector with the inverse or pseudo-inverse matrix, the vector can be computed with the polynomial coefficients c.sub.5 to c.sub.0.
When the polynomial coefficients c.sub.5 to c.sub.0 are known, they can be introduced into the polynomial
For computing a searched pixel s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y), these values should then be introduced into the polynomial so that:
In the coefficients c.sub.5 to c.sub.0 which are now known, the searched pixel value s.sub.i can then be computed directly.
FIG. 3 is a block diagram of an arrangement according to the invention computing the pixel value s.sub.i in accordance with this example in which the four reference pixel values s(x.sub.0,y.sub.0),s(x.sub.0 +1,y.sub.0),s(x.sub.0,y.sub.0 +1) and s(x.sub.0 +1,y.sub.0 +1) surrounding the searched pixel are used for computing the pixel value s.sub.i. Moreover, the first derivative in the x and y-directions of the reference pixel value s(x.sub.0,y.sub.0) is introduced.
The pixel values s(x,y) present in the two-dimensional scanning raster of FIG. 1 are applied to three line memories 31 to 36 arranged one behind the other in the arrangement of FIG. 3. The line memories 31 to 36 perform a delay by a period of one picture line so that they supply pixels of the same x value at the output, which pixels have an y value which is smaller than a given value, i.e. they are each time located one line higher in the same horizontal position.
When the output value of the line memory 33 is used as value s(x.sub.0 +3,y.sub.0), the following pixel values are provided:
the pixel value s(x.sub.0 +3,y.sub.0 +3) is present at the input of the line memory 31, the value s(x.sub.0 +3,y.sub.0 +2) is present at the output of the line memory 31, the value s(x.sub.0 +3,y.sub.0 +1) is present at the output of the line memory 32, the value s(x.sub.0 +3,y.sub.0 -1) is present at the output of the line memory 34, the pixel value s(x.sub.0 +3,y.sub.0 -2) is present at the output of the line memory 35, and the pixel value s(x.sub.0 +3,y.sub.0 -3) is present at the output of the line memory 36.
All of these pixel values are applied to a first differentiator 41 which performs a derivation of the pixel values in the y-direction, the derivation being performed on the basis of the pixel value s(x.sub.0 +3,y.sub.0).
Subsequently, a delay member 43 is provided which delays the derivation of the pixel values in the y-direction at the position (x.sub.0 +3,y.sub.0) by a period of three pixel values so that the derivation of the pixel values in the y-direction is present at the output at the position (x.sub.0,y.sub.0).
Furthermore, two delay elements 51 and 52 are provided, each performing a delay by a period of two pixel values, thus generating a delay by two values in the x-direction of the two-dimensional scanning raster.
The first delay element 51 receiving the pixel value s(x.sub.0 +3,y.sub.0 +1) supplies a pixel value s(x.sub.0 +1,y.sub.0 +1) at the output.
The second delay element, which receives the pixel value s(x.sub.0 +3,y.sub.0) at the input, supplies the value s(x.sub.0 +1,y.sub.0) at the output.
Moreover, two further delay elements 53 and 54 are provided, each performing a delay by a period of one pixel value, thus generating a delay by one value in the x-direction of the two-dimensional scanning raster.
The third delay element 53, which receives the pixel value s(x.sub.0 +1,y.sub.0 +1), then supplies a pixel value s(x.sub.0,y.sub.0 +1) at the output. The fourth delay element 54, which receives the pixel value s(x.sub.0 +1,y.sub.0) at the input, supplies the value s(x.sub.0,y.sub.0) at the output.
The value s(x.sub.0,y.sub.0) supplied by the second delay element 52 is applied to a second differentiator 42 which performs a first derivation in the x-direction at the location of this pixel.
The arrangement of FIG. 3 further comprises computing means 61 which are provided with a superposition stage 62.
The superposition stage 62 receives the output signals from the differentiator 42, the output signals from the delay elements 51 to 54, as well as the output signal from the delay element 43.
The values s(x.sub.0,y.sub.0), s(x.sub.0 +1,y.sub.0), s(x.sub.0,y.sub.0 +1), s(x.sub.0 +1,y.sub.0 +1) as well as the first derivative of the pixel value s(x.sub.0,y.sub.0) in the x and y-directions are thereby available at the input of the superposition stage.
These are the values of the vector in accordance with equation (4) which, multiplied by the inverse matrix of this equation, yield the vector with the polynomial coefficients c.sub.5 to c.sub.0.
A further consideration of this equation (5) shows that, for example, the polynomial coefficient c.sub.5 results from the sum -s(x.sub.0,y.sub.0), s(x.sub.0 +1,y.sub.0) and -.DELTA.s(x,y)/.delta.x at the location (x.sub.0,y.sub.0). In a corresponding manner, the coefficients c.sub.4 to c.sub.0 are obtained by corresponding inverse matrix superposed values or inverted values of the observation vector in equation (5).
This coherence between the pixel values of the observation vector and the polynomial coefficients is shown in the computing means 61 by a corresponding connection of adders 63 to 68 within the superposition stage 62.
For example, for the polynomial coefficient c.sub.5 taken as an example hereinbefore, the adders 63 and 64 are provided which perform a superposition of the input values in accordance with the prescription indicated by the inverse matrix in equation (5). The adder 63 receives the output signal from the second differentiator 42 at an inverting input, which differentiator supplies the signal -s(x,y)/.delta.x at the location (x.sub.0,y.sub.0). The signal s(x.sub.0 +1,y.sub.0) is applied to a non-inverting input of the adder 63. The output signal of the adder 63 is applied to a non-inverting input of the adder 64. The signal s(x.sub.0,y.sub.0) is applied to an inverting input of the adder 64.
The adder 64 thereby supplies the coefficient c.sub.5 at the output, in accordance with equation (5).
In a corresponding manner, the adders 65 and 66 are provided for generating the polynomial coefficient c.sub.4, the adders 65, 67 and 68 are provided for generating the polynomial coefficient c.sub.3. In accordance with the inverse matrix in equation (5), the polynomial coefficient c.sub.2 directly results from the value -s(x,y)/.delta.x at the location (x.sub.0,y.sub.0), i.e. from the value of the second differentiator 42. The polynomial coefficient c.sub.1 directly results from the value -s(x,y)/.delta.y at the location (x.sub.0,y.sub.0), i.e. from the value of the delay member 43. The polynomial coefficient c.sub.0 corresponds to the pixel value s(x.sub.0,y.sub.0).
The superposition stage 62 thereby supplies the polynomial coefficients c.sub.5 to c.sub.0 at the output.
Since the pixel value s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y) is obtained by introducing the values .DELTA.x and .DELTA.y into the polynomial, the equation (6) is now valid, which is computed within the computing means 61 by multiplying the polynomial coefficients c.sub.5 to c.sub.0 by the allocated basic functions at the locations .DELTA.x and .DELTA.y. Thus, the multiplier 71 multiplies the polynomial coefficient c.sub.5 by the value .DELTA.x.sup.2, the multiplier 72 multiplies the polynomial coefficient c.sub.4 by the basic function .DELTA.y.sup.2, the multiplier 73 multiplies the polynomial coefficient c.sub.3 by the basic function .DELTA.x.multidot..DELTA.y, the multiplier 74 multiplies the polynomial coefficient c.sub.2 by the basic function .DELTA.x and the multiplier 75 multiplies the polynomial coefficient c.sub.1 by the basic function .DELTA.y. Since c.sub.0 should be multiplied only by 1, a multiplier is not necessary in this case.
The polynomial coefficient c.sub.0 as well as the output values of the multipliers 71 to 75 are applied to an adder stage 81 which supplies the value s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y) of the searched pixel at the output, in conformity with equation (6).
In the arrangement of FIG. 3, the computing instruction in conformity with the polynomial and the inverse matrix is contained in the implementation of the superposition stage. The searched pixel values s.sub.y can be directly and continuously computed thereby from the input signal s(x,y) of the arrangement of FIG. 3. This may be done very accurately on the basis of the method according to the invention, with the number of components in the arrangement of FIG. 3 remaining relatively small.
The differentiators 41 and 42 shown as a block in FIG. 3 preferably have a transfer function H=(j.omega.).sup.k, in which .omega. is the local frequency in the x or the y-direction, dependent on whether the derivation should be effected in the x or the y-direction.
This transfer function may be realized, for example, by a filter which has the filter coefficients 13/128, -40/128, 115/128, 0/128, -115/128, 40/128 and -13/128.
This filter is realized by a corresponding circuit in FIG. 4.
The filter shown in FIG. 4 has six delay elements 11 to 16 which are arranged one behind the other, and in which the first delay element 11 receives the input signal to be differentiated. In conformity with the filter coefficients to be selected, the input signal as well as the output signal from the last delay element 16, inverted by means of an inverter 26, is applied to an adder 21 because both are to be multiplied in a non-inverted and an inverted form by the factor 13/128. This is realized by means of a multiplier 24 arranged subsequent to the adder 21.
In conformity with the filter coefficients mentioned above, the output signals from the first delay element 11 and the fifth delay element 15 are superposed in a non-inverted and an inverted form by means of a summing device 19 and multiplied by the filter coefficient -40/128. Similarly, the output signals from the second delay element 12 and the fourth delay element 14 are applied in a non-inverted form and in a form inverted by means of an inverter 18 to an adder 17 whose output signal is multiplied by the allocated filter coefficient 115/128 by means of a multiplier.
The output values of the multipliers 22 to 24 are superposed by means of an adder 25 so that the overall arrangement of FIG. 4 has a filter behavior which is a good approximation of the above-mentioned transfer function.
Such differentiators can be used in the circuit of FIG. 3. The delay elements within the differentiator are provided for the differentiation in the x-direction. The delay elements in the arrangement of FIG. 3 are externally built up as line memories 31 to 36 for the delay in the y-direction. In this case, the input signal and the output signals of the line memories 31 to 36 should be applied in a corresponding manner to the adders 17, 19 and 21 in a non-inverted and an inverted form, without passing through the delay elements 11 to 16.
Moreover, the delay time of the vertical differentiator 41 in FIG. 3 is to be matched with the delay time of the horizontal differentiator 42 by means of a delay member 43 which realizes a horizontal delay of three pixels, so that the horizontal derivative of the input signal s(x,y) at the point (x.sub.0,y.sub.0) is present at the output of the differentiator 42, and the vertical derivative of the input signal s(x,y) at the same point (x.sub.0,y.sub.0) is present at the output of the delay member 43.
Claims
I claim:
1. A method of computing values s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y) of pixels which are arranged outside a two-dimensional scanning raster {x.sub.0 .+-.n,y.sub.0 .+-.m, with m,n=0,1,2,3, . . . } of pixels having pixel values s(x.sub.0 .+-.n,y.sub.0 .+-.m) of a digital picture signal, comprising the steps of: determining, for computing a searched pixel value s.sub.i (x.sub.0 +.DELTA.x, y.sub.0 +.DELTA.y), at least three pixel values s(x.sub.0, y.sub.0), s(x.sub.0, y.sub.0 +1), s(x.sub.0 +1,y.sub.0), and s(x.sub.0 +1,y.sub.0 +1) of four reference pixels arranged around the searched pixel; constituting a polynomial p(x,y) of the form . . +c.sub.2 x+c.sub.1 y+c.sub.0 which, at the positions of at least three of the four reference pixels should correspond to their values, so that p(0,0)=s(x.sub.0,y.sub.0),p(1,0)=s(x.sub.0 +1,y.sub.0),p(0,1)=s(x.sub.0, y.sub.0 +1) and/or p(1,1)=s(x.sub.0 +1,y.sub.0 +1); forming the k first derivatives .delta.s(x,y)/.delta.x in the x-direction and .delta.s(x,y)/.delta.y in the y-direction from at least one of the reference pixel values; forming a matrix, whose elements consist of the values of the basic functions x.sup.am-1 y.sup.bm-1,x.sup.am-2 y.sup.bm-2, . . . x,y,1 of the polynomial at at least three of the reference pixels and the k first derivatives .delta.p(x,y)/.delta.x in the x-direction and .delta.p(x,y)/.delta.y in the y-direction of the basic functions at least one of the reference pixel values, wherein the basic functions being allocated to a reference pixel or to a first derivative of a reference pixels being in one row of the matrix; forming an inverse or pseudo-inverse matrix from the matrix by means of inversion; multiplying the inverse or pseudo-inverse matrix by an observation vector for determining the polynomial coefficients c.sub.m-1, c.sub.m-2, . . . , c.sub.2, c.sub.1, c.sub.0, which vector comprises as elements at least three of the reference pixel values and the k first derivatives .delta.s(x,y)/.delta.x in the x-direction and .delta.s(x,y)/.delta.y in the y-direction of at least one of the reference pixel values; and introducing the polynomial coefficients into the polynomial p(x,y) and computing the new pixel value s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y) by computing the function value of the polynomial p(.DELTA.x,.DELTA.y) at the location (.DELTA.x,.DELTA.y).
2. A method as claimed in claim 1, wherein, in the step of forming the matrix, forming the first derivatives .delta.p(x,y)/.delta.x in the x-direction and .delta.p(x,y)/.delta.y in the y-direction from the reference pixel value s(x.sub.0,y.sub.0), and wherein the observation factor comprises the four reference pixel value s(x.sub.0,y.sub.0), s(x.sub.0,y.sub.0 +1), s(x.sub.0 +1,y.sub.0) and s(x.sub.0 +1,y.sub.0 +1), and forming the first derivatives .delta.s(x,y)/.delta.x in the x-direction and .delta.s(x,y)/.delta.y in the y-direction from the reference pixel value s(x.sub.0,y.sub.0).
3. An arrangement for computing values s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y) of pixels which are arranged outside a two-dimensional scanning raster {x.sub.0 .+-.n,y.sub.0 .+-.m, with m,n=0,1,2,3, . . . } of pixels having pixel values s(x.sub.0 .+-.n,y.sub.0 .+-.m) of a digital picture signal, comprising: first computing means which: constitute a polynomial p(x,y) of the form p(x,y)=c.sub.m-1 x.sup.am-1 y.sup.bm-1 +c.sub.m-2 x.sup.am-2 y.sup.bm-2 + . . . +c.sub.2 x+c.sub.1 y+c.sub.0 which, at the positions of at least three of the four reference pixels should correspond to their values, so that p(0,0)=s(x.sub.0,y.sub.0),p(1,0)=s(x.sub.0 +1,y.sub.0), p(0,1)=s(x.sub.0,y.sub.0 +1) and/or p (1,1)=s(x.sub.0 +1, y.sub.0 +1), form a matrix whose elements consist of the values of the basic functions x.sup.am-1 y.sup.bm-1,x.sup.am-2 y.sup.bm-2 . . . x,y,1 of the polynomial at at least three of the reference pixels and the k first derivatives .delta.p(x,y)/.delta.x in the x-direction and .delta.p(x,y)/.delta.y in the y-direction of the basic functions at at least one of the reference pixel values, wherein the basic functions are allocated to a reference pixel or to a first derivative of a reference pixels being in one row of the matrix, form an inverse or pseudo-inverse matrix from the matrix by means of inversion; first and second differentiators which form the k first derivatives .delta.s(x,y)/.delta.x in the x-direction and .delta.s(x,y)/.delta.y in the y-direction, respectively, from at least one of the reference pixel values; and second computing means which: for computing a searched pixel value s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y), receive at least three pixel values s(x.sub.0,y.sub.0), s(x.sub.0,y.sub.0 +1), s(x.sub.0 +1,y.sub.0) and s(x.sub.0 +1,y.sub.0 +1) of four reference pixels arranged around the searched pixel, multiply the inverse or pseudo-inverse matrix by an observation vector for determining the polynomial coefficients c.sub.m-1, c.sub.m-2, . . . , c.sub.2, c.sub.1, c.sub.0, which vector comprises as elements at least three of the reference pixel values and the k first derivatives .delta.s(x,y)/.delta.x in the x-direction and .delta.s(x,y)/.delta.y in the y-direction of at least one of the reference pixel values, and introduce the polynomial coefficients into the polynomial p(x,y) and compute the new pixel value s.sub.i (x.sub.0 +.DELTA.x,y.sub.0 +.DELTA.y) by computing the function value of the polynomial p(.DELTA.x,.DELTA.y) at the location (.DELTA.x,.DELTA.y).
4. An arrangement as claimed in claim 3, wherein the first and second differentiators in the frequency range for forming the k.sup.th derivative approximately have the transfer function H=(j.omega.).sup.k, in which .omega. is the local frequency in the x-direction or y-direction, dependent on whether the derivative is to be realized in the x-direction or the y-direction.
5. An arrangement as claimed in claim 3, wherein the first differentiator comprises successively arranged delay elements and that adders are provided which receive, within the first differentiator, each time those signals which are multiplied by coefficients of the same value, the adders preceding a multiplier performing the multiplication by the allocated coefficients, and the output signals from the multipliers are added by means of another adder which supplies the output signal of the first differentiator, and the second differentiator, which has the same structure as the first differentiator, receives the input and the output signals from line memories as input signals for the inverted or non-inverted inputs of the adders.
6. An arrangement as claimed in claim 3, wherein: the values s(x.sub.0 .+-.n,y.sub.0 .+-.m) are applied to a series arrangement of line memories whose output signals supply pixel values s(x.sub.0 +3,y.sub.0 +2), s(x.sub.0 +3,y.sub.0 +1), . . . , s(x.sub.0 +3,y.sub.0 -3); a first delay element is provided which receives the pixel value s(x.sub.0 +3,y.sub.0 +1) and supplies the pixel value s(x.sub.0 +1,y.sub.0 +1) from its output; a second delay element is provided which receives the pixel value s(x.sub.0 +1,y.sub.0 +1) and supplies the pixel value s(x.sub.0,y.sub.0 +1) from its output; a third delay element is provided which receives the pixel value s(x.sub.0 +3,y.sub.0) and supplies the pixel value s(x.sub.0 +1,y.sub.0) from its output; a fourth delay element is provided which receives the pixel value s(x.sub.0 +1,y.sub.0) and supplies the pixel value s(x.sub.0,y.sub.0) from its output; the first differentiator receives the pixel values s(x.sub.0 +3,y.sub.0 +3), s(x.sub.0 +3,y.sub.0 +2), . . . , s(x.sub.0 +3,y.sub.0 -3) and performs a first derivation .delta.s(x,y)/.delta.y.vertline.(x.sub.0 +3,y.sub.0) of the pixel value s(x.sub.0 +3,y.sub.0) in the y-direction; a fifth delay element is provided which receives the first derivative in the y-direction at the location (x.sub.0 +3,y.sub.0) and supplies from its output the third derivative of the pixel values in the y-direction at the location (x.sub.0,y.sub.0); the second differentiator receives the pixel values s(x.sub.0 +3,y.sub.0) and performs a first derivation .delta.s(x,y)/.delta.x.vertline.(x.sub.0,y.sub.0) of the pixel value s(x.sub.0 +3,y.sub.0) in the x-direction; the second computing means comprises a superposition stage by means of which the pixel values and first derivatives s(x.sub.0,y.sub.0), s(x.sub.0,y.sub.0 +1), (x.sub.0 +1,y.sub.0), s(x.sub.0 +1,y.sub.0 +1) .delta.s(x,y)/.delta.x.vertline.(x.sub.0,y.sub.0) and .delta.s(x,y)/.delta.y.vertline.(x.sub.0,y.sub.0) are superimposed in accordance with the inverse matrix in such a way that the superposition stage supplies the coefficients from its output; the second computing means further comprises multipliers by means of which the coefficients are multiplied by the polynomial basic functions which are generated from .DELTA.x and .DELTA.y; and the output signals from the multiplier are added by means of an adder stage in the second computing means, which adder stage supplies the value of the searched pixel s.sub.i (x.sub.0 +.DELTA.x, y.sub.0 +.DELTA.y) from its output.
7. A method as claimed in claim 1, comprising converting a format of the digital picture signal.