Image Texture Characterization Using the Discrete Orthonormal S-Transform

The process of calculating the DOST of a 1D signal in the time domain is described in32. That process involves calculating the basis functions, which are derived by taking linear combinations of the Fourier complex sinusoids in band-limited subspaces and applying appropriate phase and frequency shifts. In this paper, we describe the process of calculating the DOST of a 2D image in the frequency domain using a dyadic sampling scheme.

We begin by defining the forward 2D-FT of a discrete function f[x,y], which is assumed to have a sampling interval of one in the x- and y-directions: and the inverse 2D-FT:

The 2D-DOST of a N × N image h[x,y] is calculated by partitioning the 2D-FT of the image, H[m,n], multiplying by the square root of the number of points in the partition, and performing an inverse 2D-FT, where we define \(v_{x} = 2^{{p_{x} - 1}} + 2^{{p_{x} - 2}}\) and \(v_{y} = 2^{{p_{y} - 1}} + 2^{{p_{y} - 2}}\) as the horizontal and vertical “voice frequencies”32. One should note that the operation to create the voice image (S[x,y,ν _{x 0},ν _{y 0}]) consists of an inverse fast Fourier transform (FFT) of smaller dimension (not N × N). The spectrum is partitioned such that the wavenumbers (ν _{x 0},ν _{y 0}) are shifted to the zero wavenumber point, and a \(2^{{p_{x} - 1}} \times 2^{{p_{y} - 1}}\) inverse FFT is performed, resulting in a rectangular (in general) voice image of \(2^{{p_{x} - 1}} \times 2^{{p_{y} - 1}}\) points (see Fig. 1). The total number of points in the DOST result and in the original image are the same.

The inverse transform for the 2D-DOST is similar to the 1D case in32. Since the DOST is an energy-conserving transform32, we can apply the forward 2D-FFT to each “voice” in order to reverse the spectral partitioning and reconstruct the spectrum of the image: The image can then be recovered by performing an inverse FT: Source code for the forward 2D-DOST is given in Appendix. Note that, in the source code, the division by \(\sqrt {2^{p_x + p_y - 2} } \) is replaced with a multiplication by the same factor; this is to account for the fact that the inverse FFT calculation inherently divides the total number of samples in the partition \({\left( {2^{{p_{x} - 1}} \times 2^{{p_{y} - 1}} } \right)}\), resulting in the overall scaling by \({\left( {2^{{p_{x} + p_{y} - 2}} } \right)}^{{{ - 1} \mathord{\left/ {\vphantom {{ - 1} 2}} \right. \kern-\nulldelimiterspace} 2}}\).

The DOST in this formulation, like the DWT, uses a dyadic sampling scheme (orders = 0, 1, 2, …, log₂ N − 1; Fig. 1). However, the two transforms provide different information about the frequency content of the image. The DWT gives horizontal, vertical, and diagonal “detail” coefficients for each order, while the DOST provides information about the voice frequencies (ν _x ,ν _y ) that contain a bandwidth of \(2^{{p_{x} - 1}} \times 2^{{p_{y} - 1}}\) frequencies. While the wavelet decomposes the image into “scales” of size M × M, the DOST uses the minimum number of points required to describe the amplitude of a Fourier frequency component in each of the horizontal and vertical directions. For example, a Fourier frequency component with two cycles spanning the horizontal direction and four cycles spanning the vertical direction is represented in the DOST by 4 × 8 points. As a result, the DOST provides more texture features for a N × N image than the DWT, while maintaining an overall size of N ². For example, Figure 2 shows the DOST and DWT transforms of an image containing four textures from the Brodatz texture library33. Each texture section is size 128 × 128 pixels and has been normalized such that the average (DC) is zero. The DWT was calculated using the Daubechies tap-4 (db4) wavelet at five levels of decomposition. The difference in partitioning can be seen in this example.

Once we have the DOST description of an image, we can find the contribution of each horizontal and vertical voice to any pixel within the image. By simply choosing a set of (x,y) coordinates representing a single pixel or image region, we can determine the value of S[x′,y′,ν _x ,ν _y ] for all (ν _x ,ν _y ). Since the voice images are of varying shape and size, the value of the DOST for frequency order (p _x ,p _y ) at image location (x,y) can be found at \(S{\left[ {x \mathord{\left/ {\vphantom {x N}} \right. \kern-\nulldelimiterspace} N \times 2^{{p_{x} - 1}} ,\;y \mathord{\left/ {\vphantom {y N}} \right. \kern-\nulldelimiterspace} N \times 2^{{p_{y} - 1}} ,v_{x} ,v_{y} } \right]}\). By iterating over all values of (p _x ,p _y ), we can build up a local spatial frequency domain of size 2 log₂ N × 2 log₂ N for each pixel or averaged region within an image; this domain contains the positive and negative frequency components from the DC, (ν _x ,ν _y ) = (0,0), to the Nyquist frequency, (ν _x ,ν _y ) = (N/2,N/2). We refer to the local domain for a pixel (x,y) as the local spectrum, S _{x ,y} [ν _x ,ν _y ]. Alternatively, we can refer to the components of the domain in terms of the frequency orders (p _x ,p _y ), instead of the voice frequencies (ν _x ,ν _y ), since they have a simple relationship.

Note that, since the voice images are of size \({\left( {2^{{p_{x} - 1}} \times 2^{{p_{y} - 1}} } \right)}\), the mapping will not be unique for low-frequency components of neighboring pixels. For example, the p _x  = p _y  = 2 contribution describes the low-frequency portion of the image using 4 pixels. Therefore, all pixels in a particular quadrant of the image will contain the same low-frequency information. In the extreme case, the p _x  = p _y  = 0 order will be represented by a single point for the entire image.

The local frequency domain is analogous to a local 2D Fourier domain, often referred to as k-space. This provides a way to measure the texture characteristics by examining the contribution of each horizontal and vertical frequency bandwidth within the image. These “texture descriptors” replace the 1D texture curves of the polar ST analysis used in28‐30. If we use the dyadic sampling scheme presented above, the frequency scale is linear and the bandwidths do not overlap.

For example, Figure 3 shows the local domain at the center of each texture region in Figure 2a. The local domain of straw (Fig. 3a) reflects the strong diagonal stripes present in the image. The figure also shows that wood (Fig. 3b) has more high frequency components oriented horizontally than vertically, while sand (Fig. 3c) and grass (Fig. 3d) have similar frequency distributions, with grass having slightly more high frequency energy.

In order to more easily determine the most significant spatial frequency component at a particular point or region, we calculate the “primary” or highest amplitude frequency. This is done for a particular point by determining the value of each voice image in the DOST at that pixel location. We examine the value of each voice image at location (x,y) and determine the component with the highest amplitude. The (ν _x ,ν _y ) pair is the “primary frequency” for the pixel.

We can extend this analysis to calculate the primary frequency at every image pixel. This results in a value of (ν _x ,ν _y) for each value of (x,y) in the image. We can represent this as a complex image, with the real channel corresponding to the primary ν _x value and the imaginary channel corresponding to the primary ν _y value. The magnitude image can then be used to examine the primary radial frequency, \(\nu _r = \sqrt {\nu _x^2 + \nu _y^2 } \). The phase image tells us the angle of orientation of the primary frequency, θ _ν  = arctan(ν _y /ν _x ).

The DOST is normalized to preserve the length of the vector; like the FT, it satisfies a Parseval theorem. Thus, each voice is divided by the size of its partition—which attenuates the amplitude of high frequency signals when dyadic sampling is employed. To obtain a domain where the relative contribution of each partition is constant, we remove the partition factor. This provides the equivalent scaling as the original ST.

The DOST is rotationally variant because we calculate measures of local spatial frequency content in the horizontal and vertical directions. The result of a horizontal shift by Δx pixels and/or a vertical shift of Δy pixels results in a corresponding shift of each voice image. We can understand this effect by considering the DOST process on a shifted image. A circular shift of the image by Δx pixels in x and Δy pixels in y causes the phase of the FFT of the image to be multiplied by the complex value \(e^{2\pi i\left( {x\Delta x + y\Delta y} \right)} \). The multiplied FFT is partitioned, and each partition is inverse Fourier-transformed. The phase ramp applied to each partition causes it to be shifted horizontally by Δx pixels and vertically by Δy pixels when inverse transformed. The multiplication of an image by a scaling factor causes the DOST to be multiplied by the same factor, as it is a linear transform.

In the case of a 90° rotation, the effect is a transpose or a switching of the x and y values in the image and a reversal of the y-coordinate. As a result, each voice image has the x- and y-coordinates switched and the y-coordinate reversed. Similarly, for a 180° rotation, the effect is to reverse the y-coordinates and maintain the x-coordinates. The result on the DOST is to reverse the y-coordinates of each voice image; the x-coordinates are not affected. In the case of rotations of 0 < θ < 90°, the effect is more complicated. A rotation of the image implies a rotation of its FT. Therefore, when calculating the 2D-DOST of a rotated image, the partitioning grid is applied to the rotated FT. As a result, the frequency components are rotated into different partitions.

In order to obtain rotationally invariant features from the DOST, we can follow a method similar to the invariant wavelet transform described in34. In that approach, invariant wavelet coefficients are computed by taking the wavelet coefficients at each level, averaged over the horizontal and vertical coefficients. Figure 4a shows the wavelet channels that are averaged together, marked with the same letter (A = level 0, B = level 1, etc.). The diagonal channels are excluded from the feature extraction, since they tend to contain the majority of the noise in the image and can degrade classification performance34.

We can take a similar approach with the 2D-DOST by averaging together the magnitude of the horizontal and vertical frequency values for each order and excluding “diagonal” elements of the DOST domain where p _x  = p _y . By combining the horizontal and vertical frequency information for the entire DOST, we can obtain an invariant domain describing the entire image. This is useful when using the DOST to examine a small ROI. However, for medical imaging applications, we would like to retain the spatial information and the frequency information of the DOST. In this case, we can combine the diagonal elements of the local DOST spectrum, described in “Pixel-Wise Local Spatial Frequency Description.”

Figure 4b shows an example of how the values are calculated from the local frequency domain for N = 8. The features marked with the same letter are averaged together to get an invariant DOST spectrum of texture features. For a given N, the DOST approach provides more texture features (A to H = 10) than the wavelet approach (A to D = 4).

In order to determine the frequency response of the 2D-DOST, we calculated the point spread function. This was done by creating a “delta” image—a 256 × 256 image where the pixel at location (128,128) had a value of one, and all other pixels had a value of zero. We took the 2D-DOST of the delta function and then computed the local spectrum. We also measured the average time to calculate the DOST and determined the amount of memory required to store the structure, for randomly generated N × N images, where N varied from 4 to 1,024. We compared the computation times and storage requirements to the ST. These calculations were based on the calculation of real images, where only half of the space-frequency domain needs to be calculated and stored due to Hermitian symmetry.

We tested the accuracy of the DOST inversion by taking the DOST of each of the nine Brodatz texture images shown in Figure 5, then inverting the 2D DOST domain according to Eqs. 4 and 5. We measured the L ₁ norm between each inverted image, s ₁, and the original, s ₀:

To examine the changes in local DOST frequency domains with varying levels of noise, we evaluated a series of synthetic images with known frequency content and added noise. By varying both of these factors, we were able to determine the smallest change in spatial frequency, and contrast, that can be reliably detected. We expect these two factors to be related; that is, we expect that high spatial frequencies will be more reliably detected in images with high contrast-to-noise ratios. The relationship between contrast and maximum detectable frequency is akin to the modulation-transfer-function used to characterize imaging systems and should provide a robust characterization of the 2D-DOST.

We generated a series of images of size 256 × 256 with a single frequency component. We varied the frequency of a sinusoid of wavenumber k = 1, 10, 20, …, 120, oriented either horizontally or diagonally, or both (equal components horizontally and vertically), with a minimum value of −1.0 and a maximum of +1.0. We also added various levels of Gaussian noise with standard deviation σ = 0.1, 0.2, …, 1.0. This gave us a total of 260 test images (13 frequencies × 2 orientations × 10 noise levels).

To determine the effect of the varying frequency and noise, we measured the signal-to-noise ratio (SNR) of the local DOST spectrum, Sx,y(p _x ,p _y ), for the central 5 × 5 pixels in the image. The SNR was defined in units of decibels (dB) as the amplitude of the frequency component being analyzed divided by the root mean square amplitude of the rest of the domain values. where A _signal is the amplitude of the voice frequency contained in the noise-free image in the local spectrum at the central pixel, and A _noise is the RMS amplitude of the remaining frequency components, not present in the noise-free image, but introduced with the addition of Gaussian noise, We analyzed the accuracy of the primary frequency estimation by determining what fraction of image pixels were correctly classified in the single-frequency images. For this experiment, we used a 10 × 10 pixel region in the center of the image or 100 test pixels per image (for a total of 26,000 pixels). For each pixel within the central 10 × 10 region, we recorded the primary frequency as found by the 2D-DOST and compared it to the true frequency of the image. The number of misclassifications were recorded.

To test the ability of the rotation-invariant DOST to classify textures, we performed an experiment on nine images from the Brodatz texture library shown in Figure 5: grass, straw, herringbone weave, woolen cloth, pressed calf leather, beach sand, wood grain, raffia, and pigskin, obtained from33. We tested the ability of the invariant DOST spectra to classify the images when: (1) trained and tested on non-rotated images, (2) trained on rotated and tested on non-rotated images, and (3) trained and tested on a variety of angles. We extracted multiple sub-images from each 512 × 512 texture image; each sub-image was of size 64 × 64 pixels. We then calculated the invariant DOST spectrum for each sub-image.

We compared the classification results using the DOST to those obtained using the invariant wavelet transform described in34. The DWT of each image was computed in Matlab with a db4 mother wavelet at five levels of decomposition using wavedec2.m. The invariant coefficients were calculated by averaging the horizontal and vertical coefficients for each level of decomposition (obtained using detcoef2.m) and computing the L1 norm, given by where the w _n is the wavelet decomposition for level n of dimensions M × M.

Classification was performed in Matlab using linear discriminant analysis (classify.m). We used two different types of discriminant functions: a linear classifier that fits a multivariate normal density to each group with a pooled estimate of covariance and a quadratic function that fits multivariate normal densities with covariance estimates stratified by group (texture).

For the first experiment, we extracted 64 sub-images of size 64 × 64 from each texture oriented at 0°. We trained the classifier on 56 sub-images of each texture (56 images × 9 textures = 504 total) and tested the classification on eight sub-images of each texture (8 images × 9 textures = 72 total). In the second case, we tested the ability of the DOST and wavelet methods to classify images oriented at a different angle than the classifier was trained on. For this experiment, we extracted texture images oriented at angles: 0°, 30°, 60°, 90° and 120°. We extracted 25 sub-images of size 64 × 64 pixels from each 512 × 512 image at each angle (25 sub-images × 5 angles × 9 textures = 1,125 images in total). We then calculated the invariant DOST spectrum for each image and the invariant wavelet spectrum. The classifier was trained on the DOST spectra from the 25 sub-images at angles 30°, 60°, 90°, and 120° (25 sub-images × 4 angles × 9 textures = 900 images) and tested on the 0° images (25 sub-images × 1 angle × 9 textures = 225 images). Finally, we trained the classifier on DOST spectra from 20 sub-images of each texture at each angle (0°, 30°, 60°, 90°, and 120°; 20 sub-images × 5 angles × 9 textures = 900 images) and tested on five images of each texture at each angle (5 sub-images × 5 angles × 9 textures = 225 images).