Projective transforms on periodic discrete image arrays
Date
2006
Authors
Kingston, Andrew
Svalbe, Imants D
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
Abstract
This chapter reviews the properties and applications of transforms designed specifically to project digital data already arranged on a discrete, regular spatial grid and that have the ability to exactly reconstruct the original data. An immediate application arises in computed tomography (CT), where a digital image is reconstructed from a measured set of discrete X-ray absorption profiles. The scientifically interesting aspect of mapping a truly digital object or function into digital projections is that they produce natural directional contractions or compressions of the object that conform to the original arrangement of the discrete pixel array. Studying digital projections of digital data may reveal how to obtain optimal sets of digital image projection data from continuous space projection measurements, as required for CT. This raises the possibility of achieving a more exact image reconstruction process, one that makes fewer, or preferably no arbitrary assumptions about reconstruction filters or data interpolation. Links to seismology, number theory, data transmission, and security in computer science will also be discussed. The popular puzzle Sudoku and the ancient magic squares (see Figure 1b) are variants of problems with solutions that are constrained by digital projections. In particular, this chapter concentrates on the discrete projections that result when two-dimensional (2D) image data are assumed to be periodic in both the axis directions, i.e., the image is mapped to a torus (as depicted in Figure 2c) as for the 2D discrete Fourier transform (DFT). Any natural line over the torus surface can also be produced by extending the line in the original image across the boundaries of replicated sets (as depicted in Figure 2b) and so continue across the same pattern of data values. This produces a wrapped digital line in the original image. This approach is best exemplified by the finite discrete Radon transform (FRT), as published by Matus and Flusser (1993), which has formed the basis for our work. However, there are many other approaches to discretize the projection of functions (e.g., Guédon and Normand, 1997; Averbuch et al., 2001) that preserve varying aspects of the continuous projection theory developed by Radon (whose original 1917 paper is translated in Deans, 1993). It is instructive to consider this other work in the context of the periodic FRT, to see how their discrete properties are interrelated. The conversion of Radon's formula into the various guises of discrete Radon transformations has a parallel with the conversion of Fourier's transform into the DFT, but projecting discrete sets of points has far more degrees of freedom and produces deeper and more complex problems than invoked by the finite sampling of discrete points inside a continuous interval. From the straightforward one-dimensional (1D) DFT, it is trivial to extend the DFT definition to higher dimensions. This is not the case for the DRT, since the Radon transform has no 1D analogue. The advantage of pursuing a truly digital projection method matched to the underlying discrete data representation is that exact reconstruction of objects from a given set of projections can be achieved in a straightforward manner. Collecting the appropriate set of digital projections enables exact digital image reconstruction or, alternatively, permits tight control over what information about the object you want reconstructed. Overview of FRT: The FRT samples the image values at points corresponding to the Dirac image model, for which the transform can be written as{A formula is presented}{A formula is presented} where δ 〈 η 〉p is 1 when η ≡ 0 (mod p) and equals zero otherwise. This definition can be extended to model the projections as beams of finite width by assuming the pixel values are distributed uniformly across the pixel area (Haar pixel model) or by using higher order interpolation functions, for example, by the set of splines in Guédon and Normand (2002). Exactly how the point based image model should be extended is a fundamental difference between several discrete projection methods; the Dirac model is the simplest representation to which the pixels based on more complex image models should be able to revert. Figure 3a shows an example of a 3 × 3 discrete data set, with arbitrary pixel values labelled a-i, as indicated. In the FRT, the set of discrete projections Rm ( t ) of an image I ( x, y ) is generated by repeated displacement of a vector ( m, 1) for 0 ≤ m < p and the vector ( 1, 0 ) for Rp ( t ) [or R0⊥ ( t )]. The origin of the vector displacements occurs at translate t, where 0 ≤ t < p. Figure 3b depicts the pixels summed by the projection vectors (shaded gray) for t = 1 over all m = 0, 1, 2, and 3. We take x (and t) to increase in unit pixel steps from left to right across the top row of I and take y to increase in unit steps from top to bottom. Choosing the data array size to be square and furthermore restricting the length of the array sides to be a prime number (p) of pixels makes each projection unique, because of the way it samples each and every element of the p × p image array once and only once. The method of generating discrete projections described by Matus and Flusser (1993) has a mathematical foundation in group theory, where each resulting element of projection data Rm ( t ) is the sum of the value of elements from one of the p2 + p unique cosets of Zp2. The resulting set of projection values is shown in Figure 3c (where t increases along the rows and m increases down each column). The perpendicular projection Rp (also denoted R0⊥) is taken as sums along the data rows, with translate t here increasing with y. The difference between continuous Radon projections and discrete FRT projections is clear. Continuous projections integrate smoothly along the path described, whereas the FRT projections sum whole pixel values taken only from those pixels that are coincident with the vector translations ( t, 0 ) + j ( m, 1 ) for 0 ≤ j < p [or pixels centered on the line x ≡ m y + t ( mod p )]. Furthermore, the FRT includes the contribution from wrapped, parallel component lines. These wrapped contributions can be kept separate in an extension of Rm ( t ) (Svalbe and van der Spek, 2001; Kingston and Svalbe, 2003a, b) denoted as Rθ ( k ). This produces a redundant transform with p + 1 projection angles and O( p3 / 2) translates. Here k labels the translate of each individual line segment and the angle θm, defined as θm = tan-1 ( ym / xm ), uses the shortest distance dm = sqrt(xm2 + ym2) between pixels sampled by the digital line of Rm ( t ), as shown in Figure 4. The motivation for choosing a projection direction that minimizes the distance between sampled pixels [and that is carried over into our version of Rm ( t )] is to emulate the continuous Radon projection case as closely as possible. It can be shown that the largest value of dm over all 0 ≤ m < p for a given array size p, which is denoted dmax, scales as dmax = sqrt(( 2 p / sqrt(3) )) for a square lattice and as dmax = sqrt(p) for the hexagonal lattice (Svalbe and Kingston, 2003a). The FRT is unique among the DRT formalisms in that the size p of the array is the only free variable in the projection set. Once p has been determined, all of the translates and projection angles are automatically fixed through the sums over all unique cosets in Zp2. The relative quality of images reconstructed from continuous CT projection data using similar chosen values of p can be compared. The composition of the projection set turns out to change slowly as a function of the array size, p. The FRT is a 1:1 projective transform. Rm ( t ) as shown in Figure 3c is a p ( p + 1 ) data set, but contains exactly p2 elements of unique information. The sum of each projection, Rm, or row of Rm ( t ), is constant (and is referred to as Isum) since it is equivalent to the sum over all p × p pixels of I. For the example given in Figure 3a, Isum = abcdefghi. The value Isum needs to be stored just once in R. Each projection can then omit one entry, since that value is recoverable (as Isum less the current projection sum), leaving ( p + 1 ) ( p - 1 ) + 1 = p2 necessary elements. The FRT also can be shown to preserve two fundamental properties of the continuous Radon transform, the Fourier slice theorem and the convolution property (Matus and Flusser, 1993). The first property means that it is possible to construct a sinogram from over(I, ̂) ( u, v ), which has practical applications in CT design and image reconstruction. The second property enables 2D convolutions in I ( x, y ) to be performed as 1D convolutions in Rm ( t ). This provides great efficiency in applications that require extensive filtering, such as feature matching. Just as scale, rotation, and translation of I ( x, y ) can be implemented in the Fourier domain, the same operations can also be effected in Rm ( t ) (Svalbe, 2002).
Description
Keywords
Keywords: Computerized tomography; Discrete Fourier transforms; Formal logic; Image processing; Vectors; X ray analysis; Discrete Image Arrays; Feature matching; Image models; Vector translations; Mathematical transformations
Citation
Collections
Source
Advances in Imaging and Electron Physics
Type
Journal article
Book Title
Entity type
Access Statement
License Rights
Restricted until
2037-12-31
Downloads
File
Description