Fourier transform. Linear filtering in the frequency domain
Linear filtering of images can be performed both in the spatial and in the frequency domain. It is considered that the "low" spatial frequencies correspond to the main content of the image - the background and large-sized objects, and the "high" spatial frequencies - small-sized objects, small details of large shapes and a noise component.
Traditionally, methods based on $ \\ textit (Fourier transform) $ are used to move to the spatial frequency domain. In recent years, methods based on $ \\ textit (wavelet-transform) $ are also increasingly used.
Fourier transform.
The Fourier transform allows you to represent almost any function or data set as a combination of trigonometric functions such as sine and cosine, which allows you to identify periodic components in the data and evaluate their contribution to the structure of the original data or the shape of the function. Traditionally, there are three main forms of the Fourier transform: the integral Fourier transform, Fourier series and the discrete Fourier transform.
The integral Fourier transform transforms a real function into a pair of real functions or one complex function into another.
The real function $ f (x) $ can be expanded in terms of the orthogonal system of trigonometric functions, that is, represented in the form
$$ f \\ left (x \\ right) \u003d \\ int \\ limits_0 ^ \\ infty (A \\ left (\\ omega \\ right)) \\ cos \\ left ((2 \\ pi \\ omega x) \\ right) d \\ omega - \\ where $ A (\\ omega) $ and $ B (\\ omega) $ are called integral cosine and sine transforms:
$$ A \\ left (\\ omega \\ right) \u003d 2 \\ int \\ limits _ (- \\ infty) ^ (+ \\ infty) (f \\ left (x \\ right)) \\ cos \\ left ((2 \\ pi \\ omega x ) \\ right) dx; \\ quad B \\ left (\\ omega \\ right) \u003d 2 \\ int \\ limits _ (- \\ infty) ^ (+ \\ infty) (f \\ left (x \\ right)) \\ sin \\ left ((2 \\ pi \\ omega x ) \\ right) dx. $$
{!LANG-89c111a6272dac8d8af6501ee8c40193!}
The Fourier series represents the periodic function $ f (x) $, given on the interval $$, as an infinite series in sines and cosines. That is, the periodic function $ f (x) $ is associated with an infinite sequence of Fourier coefficients
$$ f \\ left (x \\ right) \u003d \\ frac (A_0) (2) + \\ sum \\ limits_ (n \u003d 1) ^ \\ infty (A_n) \\ cos \\ left ((\\ frac (2 \\ pi xn) ( ba)) \\ right) + \\ sum \\ limits_ (n \u003d 1) ^ \\ infty (B_n \\ sin \\ left ((\\ frac (2 \\ pi xn) (ba)) \\ right)), $$
$$ A_n \u003d \\ frac (2) (ba) \\ int \\ limits_a ^ b (f \\ left (x \\ right)) \\ cos \\ left ((\\ frac (2 \\ pi nx) (ba)) \\ right) dx ; \\ quad B_n \u003d \\ frac (2) (ba) \\ int \\ limits_a ^ b (f \\ left (x \\ right)) \\ sin \\ left ((\\ frac (2 \\ pi nx) (ba)) \\ right) dx ... $$
Discrete Fourier transform transforms a finite sequence of real numbers into a finite sequence of Fourier coefficients.
Let $ \\ left \\ ((x_i) \\ right \\), i \u003d 0, \\ ldots, N-1 $ be a sequence of real numbers - for example, pixel brightness readings along an image line. This sequence can be represented as a combination of finite sums of the form
$$ x_i \u003d a_0 + \\ sum \\ limits_ (n \u003d 1) ^ (N / 2) (a_n) \\ cos \\ left ((\\ frac (2 \\ pi ni) (N)) \\ right) + \\ sum \\ limits_ (n \u003d 1) ^ (N / 2) (b_n \\ sin \\ left ((\\ frac (2 \\ pi ni) (N)) \\ right)), $$
$$ a_0 \u003d \\ frac (1) (N) \\ sum \\ limits_ (i \u003d 0) ^ (N-1) (x_i), \\ quad a_ (N / 2) \u003d \\ frac (1) (N) \\ sum \\ limits_ (i \u003d 0) ^ (N-1) (x_i) \\ left ((- 1) \\ right) ^ i, \\ quad a_k \u003d \\ frac (2) (N) \\ sum \\ limits_ (i \u003d 0) ^ (N-1) (x_i \\ cos \\ left ((\\ frac (2 \\ pi ik) (N)) \\ right)), $$
$$ b_k \u003d \\ frac (2) (N) \\ sum \\ limits_ (i \u003d 0) ^ (N-1) (x_i \\ sin \\ left ((\\ frac (2 \\ pi ik) (N)) \\ right) ), \\ quad i \\ le k The main difference between the three forms of the Fourier transform is that if the integral Fourier transform is defined over the entire domain of definition of the function $ f (x) $, then the series and the discrete Fourier transform are defined only on a discrete set of points, infinite for the Fourier series and finite for a discrete transformation. As can be seen from the definitions of the Fourier transform, the discrete Fourier transform is of the greatest interest for digital signal processing systems. Data received from digital media or information sources are ordered sets of numbers written as vectors or matrices. It is usually assumed that the input data for a discrete transformation is a uniform sample with a step $ \\ Delta $, and the value $ T \u003d N \\ Delta $ is called the record length, or the main period. The fundamental frequency is $ 1 / T $. Thus, in the discrete Fourier transform, the input data is decomposed into frequencies that are an integer multiple of the fundamental frequency. The maximum frequency determined by the dimension of the input data is equal to $ 1/2 \\ Delta $ and is called the $ \\ it (Nyquist frequency) $. Accounting for the Nyquist frequency is important when using discrete transforms. If the input data has periodic components with frequencies higher than the Nyquist frequency, then the calculation of the discrete Fourier transform will replace the high-frequency data with a lower frequency, which can lead to errors in the interpretation of the results of the discrete transform. The $ \\ it (energy spectrum) $ is also an important tool for data analysis. The signal strength at the frequency $ \\ omega $ is determined as follows: $$ P \\ left (\\ omega \\ right) \u003d \\ frac (1) (2) \\ left ((A \\ left (\\ omega \\ right) ^ 2 + B \\ left (\\ omega \\ right) ^ 2) \\ right ). $$ This quantity is often called the $ \\ it (signal energy) $ at the $ \\ omega $ frequency. According to Parseval's theorem, the total energy of the input signal is equal to the sum of the energies over all frequencies. $$ E \u003d \\ sum \\ limits_ (i \u003d 0) ^ (N-1) (x_i ^ 2) \u003d \\ sum \\ limits_ (i \u003d 0) ^ (N / 2) (P \\ left ((\\ omega _i) \\ right)). $$ The plot of power versus frequency is called the power spectrum or power spectrum. The energy spectrum makes it possible to reveal the hidden periodicities of the input data and evaluate the contribution of certain frequency components to the structure of the initial data. In addition to the trigonometric form of writing the discrete Fourier transform, $ \\ it (complex representation) $ is widely used. The complex notation of the Fourier transform is widely used in multivariate analysis and, in particular, in image processing. The transition from trigonometric to complex form is carried out on the basis of Euler's formula $$ e ^ (j \\ omega t) \u003d \\ cos \\ omega t + j \\ sin \\ omega t, \\ quad j \u003d \\ sqrt (-1). $$ If the input sequence is $ N $ complex numbers, then its discrete Fourier transform will have the form $$ G_m \u003d \\ frac (1) (N) \\ sum \\ limits_ (n \u003d 1) ^ (N-1) (x_n) e ^ (\\ frac (-2 \\ pi jmn) (N)), $$ and the inverse transformation $$ x_m \u003d \\ sum \\ limits_ (n \u003d 1) ^ (N-1) (G_n) e ^ (\\ frac (2 \\ pi jmn) (N)). $$ If the input sequence is an array of real numbers, then both complex and sine-cosine discrete transforms exist for it. The relationship between these views is expressed as follows: $$ a_0 \u003d G_0, \\ quad G_k \u003d \\ left ((a_k -jb_k) \\ right) / 2, \\ quad 1 \\ le k \\ le N / 2; $$ other $ N / 2 $ transformation values \u200b\u200bare complex conjugate and do not carry additional information. Therefore, the discrete Fourier transform power spectrum plot is symmetric about $ N / 2 $. The simplest way to calculate the discrete Fourier transform (DFT) is direct summation, which results in $ N $ operations for each coefficient. Total coefficients are $ N $, so the total complexity is $ O \\ left ((N ^ 2) \\ right) $. This approach is not of practical interest, since there are much more efficient ways of calculating the DFT, called the fast Fourier transform (FFT), which has a complexity of $ O (N \\ log N) $. The FFT applies only to sequences that have a length (number of elements) that is a multiple of a power of 2. The most general principle in the FFT algorithm is to split the input sequence into two half-length sequences. The first sequence is filled with data with even numbers, and the second with odd numbers. This makes it possible to calculate the DFT coefficients through two transformations of dimension $ N / 2 $. Denote $ \\ omega _m \u003d e ^ (\\ frac (2 \\ pi j) (m)) $, then $ G_m \u003d \\ sum \\ limits_ (n \u003d 1) ^ ((N / 2) -1) (x_ (2n )) \\ omega _ (N / 2) ^ (mn) + \\ sum \\ limits_ (n \u003d 1) ^ ((N / 2) -1) (x_ (2n + 1)) \\ omega _ (N / 2) ^ (mn) \\ omega _N ^ m $. For $ m< N/2$ тогда можно записать $G_m =G_{\textrm{even}} \left(m \right)+G_{\textrm{odd}}
\left(m \right)\omega _N^m $. Учитывая, что элементы ДПФ с индексом
б ольшим, чем $N/2$, являются комплексно сопряженными к элементам с индексами
меньшими $N/2$, можно записать $G_{m+(N/2)} =G_{\textrm{even}} \left(m \right)-G_{\textrm{odd}}
\left(m \right)\omega _N^m $. Таким образом, можно вычислить БПФ длиной $N$,
используя два ДПФ длиной $N/2$. Полный алгоритм БПФ заключается в рекурсивном
выполнении вышеописанной процедуры, начиная с объединения одиночных элементов в пары,
затем в четверки и так до полного охвата исходного массива данных. The discrete Fourier transform for a two-dimensional array of numbers of size $ M \\ times N $ is defined as follows: $$ G_ (uw) \u003d \\ frac (1) (NM) \\ sum \\ limits_ (n \u003d 1) ^ (N-1) (\\ sum \\ limits_ (m \u003d 1) ^ (M-1) (x_ (mn ))) e ^ ((- 2 \\ pi j \\ left [(\\ frac (mu) (M) + \\ frac (nw) (N)) \\ right])), $$ and the inverse transformation $$ x_ (mn) \u003d \\ sum \\ limits_ (u \u003d 1) ^ (N-1) (\\ sum \\ limits_ (w \u003d 1) ^ (M-1) (G_ (uw))) e ^ ((2 \\ pi j \\ left [(\\ frac (mu) (M) + \\ frac (nw) (N)) \\ right])). $$ In the case of image processing, the components of the 2D Fourier transform are called $ \\ textit (spatial frequencies) $. An important property of the two-dimensional Fourier transform is the ability to calculate it using the one-dimensional FFT procedure: $$ G_ (uw) \u003d \\ frac (1) (N) \\ sum \\ limits_ (n \u003d 1) ^ (N-1) (\\ left [(\\ frac (1) (M) \\ sum \\ limits_ (m \u003d 0) ^ (M-1) (x_ (mn) e ^ (\\ frac (-2 \\ pi jmw) (M)))) \\ right]) e ^ (\\ frac (-2 \\ pi jnu) (N) ), $$ Here the expression in square brackets is a one-dimensional transformation of a row of a data matrix that can be performed with a one-dimensional FFT. Thus, to obtain a two-dimensional Fourier transform, one must first compute the one-dimensional transformations of the rows, write the results into the original matrix, and compute the one-dimensional transformations for the columns of the resulting matrix. When calculating the two-dimensional Fourier transform, low frequencies will be concentrated in the corners of the matrix, which is not very convenient for further processing of the information received. To translate the representation of the two-dimensional Fourier transform, in which low frequencies are concentrated in the center of the matrix, you can perform a simple procedure, which consists in multiplying the original data by $ -1 ^ (m + n) $. In fig. 16 shows the original image and its Fourier transform. Grayscale image and its Fourier transform (images obtained in the LabVIEW system) The convolution of the functions $ s (t) $ and $ r (t) $ is defined as $$ s \\ ast r \\ cong r \\ ast s \\ cong \\ int \\ limits _ (- \\ infty) ^ (+ \\ infty) (s (\\ tau)) r (t- \\ tau) d \\ tau. $$ In practice, one has to deal with discrete convolution, in which continuous functions are replaced by sets of values \u200b\u200bat the nodes of a uniform grid (usually an integer grid is taken): $$ (r \\ ast s) _j \\ cong \\ sum \\ limits_ (k \u003d -N) ^ P (s_ (j-k) r_k). $$ Here $ -N $ and $ P $ define a range beyond which $ r (t) \u003d 0 $. When calculating convolution using the Fourier transform, the property of the Fourier transform is used, according to which the product of images of functions in the frequency domain is equivalent to the convolution of these functions in the time domain. To calculate the reconciliation, it is necessary to transform the original data into the frequency domain, that is, calculate their Fourier transform, multiply the transformation results and perform the inverse Fourier transform, restoring the original representation. The only subtlety in the operation of the algorithm is related to the fact that in the case of a discrete Fourier transform (as opposed to a continuous one), two periodic functions are convolved, that is, our sets of values \u200b\u200bspecify exactly the periods of these functions, and not just values \u200b\u200bon some separate section of the axis. That is, the algorithm considers that the point $ x_ (N) $ is not followed by zero, but the point $ x_ (0) $, and so on in a circle. Therefore, for the convolution to be read correctly, it is necessary to assign a sufficiently long sequence of zeros to the signal. Linear filtering methods are well-structured methods for which efficient computational schemes based on fast convolution algorithms and spectral analysis have been developed. In general, linear filtering algorithms perform a transformation of the form $$ f "(x, y) \u003d \\ int \\ int f (\\ zeta -x, \\ eta -y) K (\\ zeta, \\ eta) d \\ zeta d \\ eta, $$ where $ K (\\ zeta, \\ eta) $ is the kernel of the linear transformation. When the signal is discretely represented, the integral in this formula degenerates into a weighted sum of samples of the original image within a certain aperture. In this case, the choice of the kernel $ K (\\ zeta, \\ eta) $ in accordance with one or another criterion of optimality can lead to a number of useful properties (Gaussian smoothing in the regularization of the problem of numerical differentiation of the image, etc.). Linear processing methods are most efficiently implemented in the frequency domain. The use of the Fourier transform of an image to perform filtering operations is primarily due to the higher performance of such operations. Typically, performing forward and inverse 2D Fourier transforms and multiplication by the Fourier transform of the filter takes less time than performing 2D convolution of the original image. The frequency domain filtering algorithms are based on the convolution theorem. In the two-dimensional case, the convolution transform looks like this: $$ G \\ left ((u, v) \\ right) \u003d H \\ left ((u, v) \\ right) F \\ left ((u, v) \\ right), $$ where $ G $ is the Fourier transform of the convolution result, $ H $ is the Fourier transform of the filter, and $ F $ is the Fourier transform of the original image. That is, in the frequency domain, the two-dimensional convolution is replaced by element-wise multiplication of the images of the original image and the corresponding filter. To perform convolution, you must complete the following steps. The relationship between the filter function in the frequency domain and the spatial domain can be determined using the convolution theorem $$ \\ Phi \\ left [(f \\ left ((x, y) \\ right) \\ ast h (x, y)) \\ right] \u003d F \\ left ((u, v) \\ right) H \\ left (( u, v) \\ right), $$ $$ \\ Phi \\ left [(f \\ left ((x, y) \\ right) h (x, y)) \\ right] \u003d F \\ left ((u, v) \\ right) \\ ast H \\ left (( u, v) \\ right). $$ The convolution of a function with an impulse function can be represented as follows: $$ \\ sum \\ limits_ (x \u003d 0) ^ M (\\ sum \\ limits_ (y \u003d 0) ^ N (s \\ left ((x, y) \\ right))) \\ delta \\ left ((x-x_0, y-y_0) \\ right) \u003d s (x_0, y_0). $$ Fourier transform of an impulse function $$ F \\ left ((u, v) \\ right) \u003d \\ frac (1) (MN) \\ sum \\ limits_ (x \u003d 0) ^ M (\\ sum \\ limits_ (y \u003d 0) ^ N (\\ delta \\ frac (1) (MN). $$ Let $ f (x, y) \u003d \\ delta (x, y) $, then the convolution $$ f \\ left ((x, y) \\ right) \\ ast h (x, y) \u003d \\ frac (1) (MN) h \\ left ((x, y) \\ right), $$ $$ \\ Phi \\ left [(\\ delta \\ left ((x, y) \\ right) \\ ast h (x, y)) \\ right] \u003d \\ Phi \\ left [(\\ delta \\ left ((x, y) \\ right)) \\ right] H \\ left ((u, v) \\ right) \u003d \\ frac (1) (MN) H \\ left ((u, v) \\ right). $$ It can be seen from these expressions that the filter functions in the frequency and spatial domains are interconnected through the Fourier transform. For a given filter function in the frequency domain, you can always find the corresponding filter in the spatial domain by applying the inverse Fourier transform. The same is true for the opposite case. Using this relationship, you can define a procedure for synthesizing spatial linear filters. ($ \\ textit (Ideal low pass filter) $) $ H (u, v) $ is of the form $$ H (u, v) \u003d 1, \\ quad \\ mbox (if) D (u, v)< D_0 ,$$
$$H(u,v) = 0, \quad \mbox{если }D(u,v) \ge D_0 ,$$
где $D\left({u,v} \right)=\sqrt {\left({u-\frac{M}{2}} \right)^2+\left({v-\frac{N}{2}} \right)^2}$ - расстояние от центра частотной плоскости. ($ \\ textit (Ideal high pass filter) $) is obtained by inverting the ideal low pass filter: $$ H "(u, v) \u003d 1-H (u, v). $$ Here there is a complete suppression of low-frequency components while maintaining high-frequency. However, as in the case of an ideal low-pass filter, its use is fraught with significant distortion. Various approaches are used to design filters with minimal distortion. One of them is the synthesis of exponential filters. Such filters introduce minimal distortion in the resulting image and are convenient for synthesis in the frequency domain. Widely used in image processing is the real-Gaussian filter family. $ \\ textit (Low Pass Gaussian Filter) $ is $$ h \\ left (x \\ right) \u003d \\ sqrt (2 \\ pi) \\ sigma Ae ^ (- 2 \\ left ((\\ pi \\ sigma x) \\ right) ^ 2) \\ mbox (and) H \\ left ( u \\ right) \u003d Ae ^ (- \\ frac (u ^ 2) (2 \\ sigma ^ 2)) $$ The narrower the filter profile in the frequency domain (the more $ \\ sigma $), the wider it is in the spatial domain. ($ \\ textit (High Pass Gaussian Filter) $) has the form $$ h \\ left (x \\ right) \u003d \\ sqrt (2 \\ pi) \\ sigma _A Ae ^ (- 2 \\ left ((\\ pi \\ sigma _A x) \\ right) ^ 2) - \\ sqrt (2 \\ pi ) \\ sigma _B Be ^ (- 2 \\ left ((\\ pi \\ sigma _B x) \\ right) ^ 2), $$ $$ H \\ left (u \\ right) \u003d Ae ^ (- \\ frac (u ^ 2) (2 \\ sigma _A ^ 2)) - Be ^ (- \\ frac (u ^ 2) (2 \\ sigma _B ^ 2 )). $$ In the two-dimensional case ($ \\ it (low-pass) $), the Gaussian filter looks like this: $$ H \\ left ((u, v) \\ right) \u003d e ^ (- \\ frac (D ^ 2 \\ left ((u, v) \\ right)) (2D_0 ^ 2)). $$ The ($ \\ it (High Frequency) $) Gaussian filter has the form $$ H \\ left ((u, v) \\ right) \u003d 1-e ^ (- \\ frac (D ^ 2 \\ left ((u, v) \\ right)) (2D_0 ^ 2)). $$ Let's consider an example of image filtering (Fig. 1) in the frequency domain (Fig. 17 - 22). Note that frequency filtering of an image can make sense of both anti-aliasing ($ \\ textit (low-frequency filtering) $) and extracting outlines and small-sized objects ($ \\ textit (high-frequency filtering) $). As seen from Fig. 17, 19, as the filtering "power" increases in the low-frequency component of the image, the effect of "apparent defocusing" or $ \\ it (blurring) $ of the image becomes more pronounced. At the same time, most of the information content of the image gradually passes into the high-frequency component, where at the beginning only the contours of objects are observed (Fig. 18, 20-22). Let us now consider the behavior of high-pass and low-pass filters (Fig. 23 - 28) in the presence of additive Gaussian noise in the image (Fig. 7). As seen from Fig. 23, 25, the properties of low-pass filters to suppress additive random noise are similar to the properties of the previously considered line filters - with sufficient filter power, noise is suppressed, but the price for this is a strong blurring of the edges and "defocusing" of the entire image. The high-frequency component of the noisy image ceases to be informative, since in addition to the contour and object information, the noise component is now also completely present there (Fig. 27, 28). The use of frequency methods is most expedient in the case when the statistical model of the noise process and / or the optical transfer function of the image transmission channel are known. It is convenient to take into account such a priori data by choosing a generalized filter controlled (by parameters $ \\ sigma $ and $ \\ mu $) as follows: $$ F (w_1, w_2) \u003d \\ left [(\\ frac (1) (P (w_1, w_2))) \\ right] \\ cdot \\ left [(\\ frac ((\\ vert P (w_1, w_2) \\ vert ) ^ 2) (\\ vert P (w_1, w_2) \\ vert ^ 2 + \\ alpha \\ vert Q (w_1, w_2) \\ vert ^ 2)) \\ right]. $$ where $ 0< \sigma < 1$, $0 < \mu < 1$ - назначаемые параметры фильтра,
$P(w_{1}$, $w_{2})$ - передаточная функция системы, $Q(w_{1}$, $w_{2})$ -
стабилизатор фильтра, согласованный с энергетическим спектром фона. Выбор
параметров $\sigma = 1$, $\mu = 0$ приводит к чисто инверсной фильтрации,
$\sigma =\mu = 1$ к \it{винеровской фильтрации}, что позволяет получить изображение, близкое к
истинному в смысле минимума СКО при условии, что спектры
плотности мощности
изображения и его шумовой компоненты априорно известны. Для дальнейшего
улучшения эффекта сглаживания в алгоритм линейной (винеровской) фильтрации
вводят адаптацию, основанную на оценке локальных статистик: математического
ожидания $M(P)$ и дисперсии $\sigma (P)$. Этот алгоритм эффективно фильтрует
засоренные однородные поверхности (области) фона. Однако при попадании в
скользящее окно обработки неоднородных участков фона импульсная
характеристика фильтра сужается ввиду резкого изменения локальных статистик,
и эти неоднородности (контуры, пятна) передаются практически без
расфокусировки, свойственной неадаптивным методам линейной фильтрации. The advantages of linear filtering methods include their clear physical meaning and simplicity of results analysis. However, with a sharp deterioration in the signal-to-noise ratio, with possible variants of areal noise and the presence of high-amplitude impulse noise, linear methods of preprocessing may be insufficient. In this situation, nonlinear methods are much more powerful. 19 Ticket1. Dilation operation 2. Spatial-spectral features Dilatation operations. Let A and B be sets from the space Z 2. Dilation of a set A over a set B (or with respect to B) is denoted by A⊕B and is defined as It can be rewritten as follows: The set B will be called the structure-forming set or the dilation primitive. (11) is based on obtaining the central reflection of the set B relative to its initial coordinates (center B), then the shift of this set to the point z, the dilatation of the set A along B is the set of all such displacements z at which A and A coincide in at least one element. This definition is not the only one. However, the dilatation procedure is in a sense similar to the convolution operation, which is performed on sets. Spatial-spectral features In accordance with (1.8), the two-dimensional Fourier transform is defined as where w x, w y - spatial frequencies. The square of the modulus of the spectrum M ( w x, w y) \u003d | Ф ( w x, w y) | 2 can be used to calculate a number of features. Function integration M(w x, w y) by the angle on the plane of spatial frequencies gives a spatial-frequency feature that is invariant with respect to the shift and rotation of the image. Introducing the function M(w x, w y) in polar coordinates, we write this feature in the form where q\u003d arctg ( w y/w x); r 2 = w x 2 +w y 2 . 20 Ticket1. Operation erosion The discrete two-dimensional Fourier transform of the image sample matrix is \u200b\u200bdefined as a series: where, and the discrete inverse transformation is: By analogy with the terminology of the continuous Fourier transform, the variables are called spatial frequencies. It should be noted that not all researchers use the definitions (4.97), (4.98). Some prefer to put all scale constants in the expression for the inverse transformation, while others change the signs in the nuclei to the opposite. Since the transformation kernels are symmetric and separable, the two-dimensional transformation can be performed as successive one-dimensional transformations along the rows and columns of the image matrix. Basic transformation functions are exponents with complex exponents that can be decomposed into sine and cosine components. Thus, The spectrum of the image has many interesting structural features. Spectral component at the origin of the frequency plane equal to increased in N times the average (over the original plane) value of the image brightness. Substituting into equality (4.97) where and are constants, we get: For any integer values \u200b\u200band, the second exponential factor of equality (4.101) becomes one. Thus, for, which indicates the periodicity of the frequency plane. This result is illustrated in Figure 4.14, a. The two-dimensional Fourier spectrum of an image is essentially a representation of a two-dimensional field in the form of a Fourier series. For this representation to be valid, the original image must also have a periodic structure, i.e. have a pattern repeating vertically and horizontally (Figure 4.14, b). Thus, the right edge of the image is adjacent to the left, and the top edge is adjacent to the bottom. Due to the discontinuities in the brightness values \u200b\u200bin these places in the image spectrum, additional components appear that lie on the coordinate axes of the frequency plane. These components are not related to the brightness values \u200b\u200bof the inner points of the image, but they are necessary to reproduce its sharp edges. If the array of image samples describes the brightness field, then the numbers will be real and positive. However, the Fourier spectrum of this image generally has complex values. Since the spectrum contains components representing real and imaginary parts or phase and the modulus of the spectral components for each frequency, the Fourier transform might appear to increase the dimension of the image. This, however, is not the case, since it has complex conjugation symmetry. If in equality (4.101) we set and equal to integers, then after complex conjugation we get the equality: Using substitution and src \u003d http: //electrono.ru/wp-content/image_post/osncifr/pic126_15.gif\u003e you can show that Due to the presence of complex conjugate symmetry, almost half of the spectral components are excessive, i.e. they can be formed from the rest of the components (Fig. 4.15). Excessive components can, of course, be considered harmonics that fall not in the lower, but in the right half-plane. Fourier analysis in image processing is used for the same purposes as for 1D signals. However, in the frequency domain, images do not provide any meaningful information, making Fourier transforms less useful in image analysis. For example, when the Fourier transform is applied to a one-dimensional audio signal, a difficult and complex waveform in the time domain is converted into an easy-to-understand spectrum in the frequency domain. For comparison, by taking the Fourier transform (Fourier transform) of the image, we transform the ordered information in the spatial domain (spatial domain) into a coded form in the frequency domain (frequency domain). In short, don't expect Fourier transform to help you understand the information encoded in images. Likewise, do not refer to the frequency domain when designing a filter. The main characteristic feature in the images is the border - the line separating one an objector regionfrom another objector areas... Since the contours in the image contain a wide range of frequency components, trying to change the image by manipulating the frequency spectrum is an ineffective task. Image processing filters are usually designed in a spatial domain where information is presented in its simplest and most accessible form. When solving image processing problems, it is rather necessary to operate in terms of operations smoothingand underliningcontours (spatial domain) than in terms of high pass filterand low pass filter(frequency domain). Despite this, Fourier image analysis has several useful properties. For example, convolutionin the spatial domain corresponds to multiplicationin the frequency domain. This is important because multiplication is a simpler mathematical operation than convolution. As with 1D waveforms, this property allows FFT convolution and various deconvolution techniques. Another useful property in the frequency domain is fourier sector theorem, establishing correspondences between the image and its projections (views of the same image from different sides). This theorem forms the theoretical basis for such directions as computed tomography, fluoroscopywidely used in medicine and industry. The frequency spectrum of an image can be calculated in several ways, but the most practical method for calculating the spectrum is the FFT algorithm. When using the FFT algorithm, the original image must contain N lines and N columns, and the number N must be a multiple of a power of 2, i.e. 256, 512, 1024 and etc. If the original image is not a multiple of a power of 2 in terms of its dimension, then it is necessary to add pixels with a zero value to complete the image to the required size. Due to the fact that the Fourier transform preserves the order of information, the amplitudes of the low-frequency components will be located at the corners of the two-dimensional spectrum, while the high-frequency components will be in its center. As an example, consider the result of the Fourier transform of an electron microscopic image of the input stage of an operational amplifier (Figure 4.16). Since the frequency domain may contain pixels with negative values, the gray scale of these images is shifted in such a way that negative values \u200b\u200bare perceived as dark points in the image, zero values \u200b\u200bas gray, and positive values \u200b\u200bas light ones. Usually, the low-frequency components of the image spectrum are much larger in amplitude than the high-frequency ones, which explains the presence of very bright and very dark points in the four corners of the spectrum image (Fig. 4.16, b). As can be seen from the figure, a typical specialComplex representation of the Fourier transform.
Fast Fourier Transform.
Two-dimensional Fourier transform.
Convolution using Fourier transform.
Filtering images in the frequency domain.
Scale invariance is possessed by the attribute
