You get a bonus - 1 coin for daily activity. Now you have 1 coin

9.2. DISCRETED SUPERPOSITION OPERATOR

Lecture



In digital image processing, in many cases it is required to convert the integral superposition operator in discrete form, connecting continuous images at the input and output of the linear system. Phenomena such as image blurring caused by imperfections in the optical system, aperture distortion or distortion when viewed through a turbulent atmosphere can be described using the following integral equation:

  9.2.  DISCRETED SUPERPOSITION OPERATOR , (9.2.1а)

Where   9.2.  DISCRETED SUPERPOSITION OPERATOR and   9.2.  DISCRETED SUPERPOSITION OPERATOR describe the input and output images, respectively, and the core   9.2.  DISCRETED SUPERPOSITION OPERATOR represents the impulse response of a linear system. The impulse response can be a function of four variables — the coordinates of the points of the input and output planes. If the linear system is spatially invariant, then the image at its output can be described using the convolution integral

  9.2.  DISCRETED SUPERPOSITION OPERATOR . (9.2.1b)

With discrete processing, the output image will be represented by samples. Therefore, the integral of superposition or convolution should be transformed so as to express explicitly the connection of the output image samples with the values ​​of the function describing the input image. The question of the discrete representation of integral transforms is important, since the resulting errors can lead to large errors in the processed image or even to the loss of stability of the digital processing process. In addition, the choice of the discrete-representation algorithm, as a rule, greatly depends on the complexity of the processing itself.

In the first stage of the discretization process of the superposition integral, the output image is discretized using a lattice from   9.2.  DISCRETED SUPERPOSITION OPERATOR Dirac delta pulses separated by an interval   9.2.  DISCRETED SUPERPOSITION OPERATOR . The result is an array of samples.

  9.2.  DISCRETED SUPERPOSITION OPERATOR , (9.2.2)

Where   9.2.  DISCRETED SUPERPOSITION OPERATOR . The delta function can be introduced into the integrand of the integral (9.2.1a); the result is a ratio

  9.2.  DISCRETED SUPERPOSITION OPERATOR . (9.2.3)

It should be noted that the output image is discretized according to the coordinates of the plane of the observed image.   9.2.  DISCRETED SUPERPOSITION OPERATOR and does not affect current variables   9.2.  DISCRETED SUPERPOSITION OPERATOR on which integration is carried out.

In the next step, the impulse response should be limited in duration. For this we set

  9.2.  DISCRETED SUPERPOSITION OPERATOR (9.2.4)

at   9.2.  DISCRETED SUPERPOSITION OPERATOR and   9.2.  DISCRETED SUPERPOSITION OPERATOR . Then

  9.2.  DISCRETED SUPERPOSITION OPERATOR . (9.2.5)

It should be noted that the truncation of the impulse response is equivalent to multiplying it by the weighting function (“window”)   9.2.  DISCRETED SUPERPOSITION OPERATOR equal to one inside the square   9.2.  DISCRETED SUPERPOSITION OPERATOR ,   9.2.  DISCRETED SUPERPOSITION OPERATOR and zero beyond. According to the convolution spectrum theorem, the spectrum obtained after truncating an image is equal to the convolution of the image spectra   9.2.  DISCRETED SUPERPOSITION OPERATOR and weight function (window)   9.2.  DISCRETED SUPERPOSITION OPERATOR and the spectrum of the latter is a two-dimensional sinc function. Such a distortion of the spectrum   9.2.  DISCRETED SUPERPOSITION OPERATOR leads to the appearance of parasitic components with high spatial frequencies, grouped near frequencies that are multiple   9.2.  DISCRETED SUPERPOSITION OPERATOR (the Gibbs phenomenon). The distortion of the truncation can be reduced by using more sophisticated weight functions, such as Bartlett, Blackman, Hamming, or Hann's windows [3], which can smooth out unwanted effects associated with the presence of gaps in a rectangular window. The choice of a suitable window is of great importance, since the incorrectness of the integral transform (9.2.1a) can lead to a sharp increase in distortion caused by the truncation of the impulse response in the image reconstruction process.

The next step in the sampling process is that the continuous source image   9.2.  DISCRETED SUPERPOSITION OPERATOR represented by a set of values ​​describing its function in nodes of a rectangular grid with a step   9.2.  DISCRETED SUPERPOSITION OPERATOR and size   9.2.  DISCRETED SUPERPOSITION OPERATOR . This operation is not a sampling of real samples, but only a mathematical transformation, which results in an array

  9.2.  DISCRETED SUPERPOSITION OPERATOR , (9.2.6)

Where   9.2.  DISCRETED SUPERPOSITION OPERATOR , and   9.2.  DISCRETED SUPERPOSITION OPERATOR and   9.2.  DISCRETED SUPERPOSITION OPERATOR denote the minimum and maximum index values   9.2.  DISCRETED SUPERPOSITION OPERATOR .

If the ultimate goal is to estimate the continuous source image by processing real samples of the observed physical field, then step   9.2.  DISCRETED SUPERPOSITION OPERATOR must be taken small enough for the Nyquist criterion to be satisfied for the original image. This means that if the original image has a spectrum of finite width, then the distance between the nodes should be set equal to the corresponding Nyquist interval. Ideally, this provides the ability to accurately restore the image.   9.2.  DISCRETED SUPERPOSITION OPERATOR by interpolating estimated values   9.2.  DISCRETED SUPERPOSITION OPERATOR .

Using the formulas for the approximate calculation of integrals, in equality (9.2.5), the integral can be approximated by a sum [2]. In this case, the actual image samples can be described by the expression

  9.2.  DISCRETED SUPERPOSITION OPERATOR , (9.2.7)

Where   9.2.  DISCRETED SUPERPOSITION OPERATOR - weight coefficients in a particular approximate formula used for calculations. Usually they use the formula of rectangles, for which all weights are equal to one. In any case, it is convenient to combine the weights and impulse response counts, so that

  9.2.  DISCRETED SUPERPOSITION OPERATOR . (9.2.8)

Then

  9.2.  DISCRETED SUPERPOSITION OPERATOR . (9.2.9)

It should be noted that the function   9.2.  DISCRETED SUPERPOSITION OPERATOR has not been sampled by the first two variables. In the formulas, its values ​​simply appear in the corresponding points. The limits of summation in equality (9.2.9) are equal

  9.2.  DISCRETED SUPERPOSITION OPERATOR , (9.2.10)

where is the symbol   9.2.  DISCRETED SUPERPOSITION OPERATOR denotes rounding to the nearest integer.

In fig. 9.2.1 is an example of how real counts   9.2.  DISCRETED SUPERPOSITION OPERATOR output image is mapped to anchor points   9.2.  DISCRETED SUPERPOSITION OPERATOR source image. In this example, the interval between the nodes is twice as large as the distance between the actual samples. The impulse response values ​​used in calculating the sum (9.2.9) are shown in dots in this figure.

  9.2.  DISCRETED SUPERPOSITION OPERATOR

Fig. 9.2.1. The relationship between the real image samples and the values ​​of the original image at the nodal points in the numerical representation of the superposition integral.

In connection with the discrete representation (9.2.9) of a linear integral transform, an important note should be made: regardless of the ratio between the number of nodal points and the number of real samples, the area of ​​the original image   9.2.  DISCRETED SUPERPOSITION OPERATOR where the nodal points that affect the values ​​of real samples are located, always turns out to be larger than the area of ​​the sampled output image   9.2.  DISCRETED SUPERPOSITION OPERATOR . As shown in fig. 9.2.2, the sizes of both images with an accuracy of one sampling interval are related by the relation

  9.2.  DISCRETED SUPERPOSITION OPERATOR . (9.2.11)

  9.2.  DISCRETED SUPERPOSITION OPERATOR

Fig. 9.2.2. The ratio between the regions of the location of real samples and nodal points in the numerical representation of the integral of the superposition.

A - the original image; B - area of ​​location of counts of the observed image; In - the location of the nodal points.

So, a discrete finite model of a linear integral transform was built, which links the output image samples   9.2.  DISCRETED SUPERPOSITION OPERATOR with the values ​​of the elements of the original image   9.2.  DISCRETED SUPERPOSITION OPERATOR through the mathematical operation of a discrete linear transformation. Such an operation is an approximation of the continuous transform, since the impulse response   9.2.  DISCRETED SUPERPOSITION OPERATOR subjected to truncation, and the integral was calculated by approximate quadrature formulas. It is clear that, by expanding the domain of the impulse response, the truncation error can be made arbitrarily small, although this is associated with an increase in the amount of computation. Errors due to the approximate calculation of the integrals can be reduced by applying more accurate quadrature formulas, but also at the cost of complicating the calculations. It should be noted, however, that the discrete version of the linear integral transform is an exact approximation of the latter, if all the functions of the spatial variables included in formula (9.2.1) have spectra of limited width, and the intervals when sampling the output image and the numerical representation of the original image are selected in according to the Nyquist criterion [4]. The question of the accuracy and stability of the discrete representation is considered in Chapter. 14.

It often turns out that it is more convenient to use relation (9.2.9) if it is represented in a vector form. To this end, the numbering of the elements of the arrays   9.2.  DISCRETED SUPERPOSITION OPERATOR and   9.2.  DISCRETED SUPERPOSITION OPERATOR should be changed so that arrays of sizes are formed respectively   9.2.  DISCRETED SUPERPOSITION OPERATOR and   9.2.  DISCRETED SUPERPOSITION OPERATOR with positive indices. Assume that

  9.2.  DISCRETED SUPERPOSITION OPERATOR , (9.2.12а)

Where   9.2.  DISCRETED SUPERPOSITION OPERATOR , but

  9.2.  DISCRETED SUPERPOSITION OPERATOR , (9.2.12b)

Where   9.2.  DISCRETED SUPERPOSITION OPERATOR . In addition, we define the impulse response so that

  9.2.  DISCRETED SUPERPOSITION OPERATOR . (9.2.12c)

In fig. 9.2.3 shows the geometric relationships between these functions.

  9.2.  DISCRETED SUPERPOSITION OPERATOR

Fig. 9.2.3. Arrays of samples of the image and impulse response.

The discrete transformation (9.2.9) with respect to shifted arrays has the following form:

  9.2.  DISCRETED SUPERPOSITION OPERATOR , (9.2.13)

Where   9.2.  DISCRETED SUPERPOSITION OPERATOR a

  9.2.  DISCRETED SUPERPOSITION OPERATOR .

Using the methodology described in Ch. 5, vectors can be formed   9.2.  DISCRETED SUPERPOSITION OPERATOR and   9.2.  DISCRETED SUPERPOSITION OPERATOR which are the scan matrix   9.2.  DISCRETED SUPERPOSITION OPERATOR and   9.2.  DISCRETED SUPERPOSITION OPERATOR by columns. These vectors are related by the relation [1]

  9.2.  DISCRETED SUPERPOSITION OPERATOR (9.2.14)

Where   9.2.  DISCRETED SUPERPOSITION OPERATOR - size matrix   9.2.  DISCRETED SUPERPOSITION OPERATOR having the following structure:

  9.2.  DISCRETED SUPERPOSITION OPERATOR . (9.2.15)

Matrix elements   9.2.  DISCRETED SUPERPOSITION OPERATOR determined by equality

  9.2.  DISCRETED SUPERPOSITION OPERATOR (9.2.16)

at   9.2.  DISCRETED SUPERPOSITION OPERATOR ,   9.2.  DISCRETED SUPERPOSITION OPERATOR where   9.2.  DISCRETED SUPERPOSITION OPERATOR there is an odd integer closest to the size of the impulse response, expressed by the number of discretization steps   9.2.  DISCRETED SUPERPOSITION OPERATOR . Further, for simplicity, the matrix   9.2.  DISCRETED SUPERPOSITION OPERATOR will be called the lubrication matrix. If the impulse response is invariant with respect to the bias, i.e.

  9.2.  DISCRETED SUPERPOSITION OPERATOR , (9.2.17)

then the operation of discrete superposition (9.2.13) turns into a discrete convolution:

  9.2.  DISCRETED SUPERPOSITION OPERATOR . (9.2.18)

An interesting case when   9.2.  DISCRETED SUPERPOSITION OPERATOR where   9.2.  DISCRETED SUPERPOSITION OPERATOR - integer. Wherein

  9.2.  DISCRETED SUPERPOSITION OPERATOR (9.2.19)

Now the elements of the blur matrix are equal

  9.2.  DISCRETED SUPERPOSITION OPERATOR , (9.2.20)

Where   9.2.  DISCRETED SUPERPOSITION OPERATOR and   9.2.  DISCRETED SUPERPOSITION OPERATOR . Further, if   9.2.  DISCRETED SUPERPOSITION OPERATOR , the elements of the blur matrix take the form

  9.2.  DISCRETED SUPERPOSITION OPERATOR . (9.2.21)

Besides,

  9.2.  DISCRETED SUPERPOSITION OPERATOR . (9.2.22)

Therefore, all rows of the matrix   9.2.  DISCRETED SUPERPOSITION OPERATOR are obtained by shifting the first row. Then the operator   9.2.  DISCRETED SUPERPOSITION OPERATOR is a discretized convolution operator, and the sum representation (9.2.19) is simplified:

  9.2.  DISCRETED SUPERPOSITION OPERATOR . (9.2.23)

In fig. 9.2.4, and the printout of matrices of the discretized convolution operator is given, when the input array consists of   9.2.  DISCRETED SUPERPOSITION OPERATOR counts   9.2.  DISCRETED SUPERPOSITION OPERATOR impulse response is presented   9.2.  DISCRETED SUPERPOSITION OPERATOR counts   9.2.  DISCRETED SUPERPOSITION OPERATOR and the output array contains   9.2.  DISCRETED SUPERPOSITION OPERATOR countdown   9.2.  DISCRETED SUPERPOSITION OPERATOR . In fig. 9.2.4, b shows the view of the matrix   9.2.  DISCRETED SUPERPOSITION OPERATOR for the case of higher dimensions when   9.2.  DISCRETED SUPERPOSITION OPERATOR and the impulse response is Gaussian.

  9.2.  DISCRETED SUPERPOSITION OPERATOR

Fig. 9.2.4. Examples of matrices of discretized convolution operators.

a - the general case   9.2.  DISCRETED SUPERPOSITION OPERATOR ; b - impulse response of the Gaussian form,   9.2.  DISCRETED SUPERPOSITION OPERATOR .

Assume that the impulse response is spatially invariant and separable, i.e.

  9.2.  DISCRETED SUPERPOSITION OPERATOR , (9.2.24)

where are the matrices   9.2.  DISCRETED SUPERPOSITION OPERATOR and   9.2.  DISCRETED SUPERPOSITION OPERATOR size   9.2.  DISCRETED SUPERPOSITION OPERATOR have the following structure:

  9.2.  DISCRETED SUPERPOSITION OPERATOR . (9.2.25)

In this case, the calculation of a two-dimensional convolution is reduced to the sequential execution of convolutions in rows and columns of the matrix of the original image. In this way,

  9.2.  DISCRETED SUPERPOSITION OPERATOR . (9.2.26)

To perform a superposition operation or to calculate a convolution in vector form   9.2.  DISCRETED SUPERPOSITION OPERATOR arithmetic operations, and this number does not include multiplication by zero elements of the matrix   9.2.  DISCRETED SUPERPOSITION OPERATOR . If we separate the convolution operator, then for calculations in the matrix form it suffices   9.2.  DISCRETED SUPERPOSITION OPERATOR arithmetic operations.

Suppose that with the same impulse response size   9.2.  DISCRETED SUPERPOSITION OPERATOR to an array of image size counts   9.2.  DISCRETED SUPERPOSITION OPERATOR To simulate the process of continuous superposition, a superposition operator of finite arrays and a discretized superposition operator are applied. Then the array processed by the first operator coincides with the array obtained as a result of the action of the second operator, which is surrounded by a strip of   9.2.  DISCRETED SUPERPOSITION OPERATOR extra elements, and vice versa, if the sizes of the processed arrays are the same, then   9.2.  DISCRETED SUPERPOSITION OPERATOR the border elements of the array obtained with the help of the finite superposition operator will be distorted. Thus, one should carefully use the operator of a superposition of finite arrays to simulate continuous processes.


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Digital image processing

Terms: Digital image processing