Time Reversal Gaussian Approximation Filter

The present invention relates to filters useful in signal processing. In particular, the present invention relates to the field of time reversal filters for use in audio and image processing.

Time reversal filters are used for processing both audio and video signals. For spatially filtering images, a separable filter, such as a Gaussian filter, is particularly desirable. Each horizontal scan line of pixels is filtered independently, then each vertical column of pixels is similarly filtered. If the filter is a true Gaussian filter, then the resulting filtering of the two dimensional image is radially symmetric. That is, at any arbitrary angle through the image, the resulting filtered image will be the same as if the line of pixels at such arbitrary angle were directly filtered by the Gaussian filter. To the extent that a close approximation to Gaussian filter is used, the resulting image filtering is close to radially symmetric. Due to its symmetry, the ideal Gaussian filter has no phase shift over all frequencies of interest.

One of the most important applications of Gaussian filtering is for sharpening, or edge enhancement. Gaussian filtering to sharpen an image is especially desirable when a photographic original has been scanned at very high resolution (for example, a 35 mm negative scanned at 4000 dots per inch). Scanning an image at very high resolution, i.e. significantly greater than that absolutely needed to capture the image detail within the Nyquist frequency of the sampling process, then sharpening using Gaussian filtering, produces an image with minimal image artifacts. The rotational symmetry of the Gaussian filter means that lines of any angle will be sharpened by an identical amount, a property not shared by the closest competitor to the Gaussian filter for image sharpening: the Laplacian (or 3.times.3 convolution) filter. Thus, the Gaussian filtering is popular for very high quality image processing systems.

Another application of Gaussian filtering is removing film grain, unwanted screens (as when scanning photos from a magazine), as well as other unwanted artifacts.

A drawback to Gaussian filtering is its relatively great computational cost. Most digital implementations of a Gaussian filter use finite impulse response (FIR) filters. The larger the extent, or, equivalently, the lower the cutoff frequency of the Gaussian filter, the more computationally expensive it is to implement. A typical implementation requires dozens of multiplications per pixel. Further, because the shape of the Gaussian curve is infinite in extent, practical implementations must truncate the actual curve, which can cause quality problems.

Time reversal filtering is known in the field of audio engineering. The input audio signal is filtered through a first stage, and the result recorded on tape. Then, the tape is played back backwards (i.e. in reverse) through a second, identical stage of filtering. The result is recorded on a second tape. When the second tape is played back again backwards, the result is the desired filtered audio signal. Symmetrical filtering is desired in the field of audio processing. The result of symmetrical time reverse filtering is an audio signal in which the frequencies have been filtered as desired, but the phase has been absolutely preserved.

There are many drawbacks to audio time reversal filtering. For one, it takes twice as long, because the tape must be run through a second time. For another, it requires twice as much tape. Further, the signal undergoes the degradation of two recording processes, which is a much more severe problem for analog than digital recording. Perhaps most importantly, it is completely unworkable for real time audio processing, because it is impossible to hear any results until the whole tape has been filtered.

The present invention is embodied in a low pass filter having an impulse response substantially equal to a Gaussian bell curve, while minimizing computational complexity. Specifically, the present invention is embodied in a novel architecture time reversal filter employing infinite impulse response (IIR) filters. Infinite impulse response filters, by themselves, tend to be asymmetrical. In one embodiment of the present invention, multiple stages of IIR filters are used in a time reversal filter, resulting in a perfectly symmetrical filter. A first stage of IIR filtering is performed in the forward direction, and an identical stage of IIR filtering is performed in the reverse, or backward direction. In the preferred embodiment of the present invention, an IIR filter element composed of a cascade of two filters with an exponential decay response, in series, is used in a time reversal filter to create a Gaussian approximation filter.

In accordance with another embodiment of the present invention, the forward and backward passes of a time reversal filter are performed in essentially one pass using a segmented approach. The input signal is divided into segments, each segment is filtered first in the forward direction, then in the reverse direction, and the segments thus filtered are reassembled, or spliced together to form the output signal. In addition, the overlap in the reverse direction from each filtered segment extending backward into the prior filtered segment is preserved in memory and added to the output of reassembled segments. Although, in theory, the output signal of an IIR filter continues for many samples after the input signal ceases (i.e. after the end of the segment, the output continues for an infinite amount of time), in practice the filter output drops below a threshold after a finite number of samples. Therefore, retaining a finite number of overlap samples for each segment in the reverse direction approximates the backward pass of the time reversal filter. Adding the overlap derived from filtering each segment in the reverse direction to the prior segment permits the independently time reverse filtered segments to be spliced together to form the continuous output signal.

In accordance with a further embodiment of the present invention, a single memory in the form of a circular buffer is used to store both the signal samples of each segment, and the overlap samples between segments. A pointer is moved forward and backward around the circular buffer to load, time reverse, and output the processed signal samples.

In accordance with yet another aspect of the present invention, multiple time reversal Gaussian approximation filters (TRGA) are combined to form more complex filters.

FIG. 1 is a block diagram of a prior art time reversal filter.

FIG. 3 is a time diagram of signals associated with the circuit of FIG. 2 in combination with the block diagram of FIG. 1, in accordance with the present invention.

FIG. 2 is schematic diagram of an IIR filter which may be used for the IIR filter 12 or the IIR 16 in FIG. 1, in accordance with the present invention.

FIGS. 3A-3G are time diagrams which illustrate the operation of a TRGA filter embodying the present invention.

FIG. 4 is a flow chart diagram of a software program embodying the present invention.

FIG. 5 is a block diagram of a composite filter utilizing TRGA filters of the present invention.

FIG. 6 is a block diagram of a TRGA filter embodying the present invention.

As shown in FIG. 1, a time reversal filter comprises a first IIR 12, a first time reversal memory 14, a second IIR 16 and a second time reversal memory 18. If time reversal is implemented by recording on magnetic tape or other mass memory, and by playing the tape or retrieving signal memory in reverse time order, then one IIR filter for forward and reverse filtering may for used in lieu of IIR filters 12 and 14. In operation, an input signal on terminal 10 is filtered by IIR 12, reversed in time by memory 14, filtered a second time by IIR 16, and finally reversed a second time by memory 18, to produce result signal 20.

The design of the IIR filters 12 and 16 determines the impulse response of the filtering performed by the system. It is desirable that the impulse response approximate a Gaussian bell curve as closely as possible. An embodiment of a digital IIR filter is shown in FIG. 2. The filter consists of two exponential decay filters in series. An analog exponential decay filter is the familiar series resistance, parallel capacitance, low pass RC filter. In general, the response of an exponential decay filter to an impulse input is an exponential function, having declining positive output values, following an exponential curve into infinity.

Input terminal 22 is coupled to the positive input of subtractor 24. The output of subtractor 24 is coupled to the input of multiplier 26, the output of which is coupled to one input of adder 28. The output of adder 28 is coupled through a delay element 30, to feedback to the negative input of subtractor 24 and the other input of adder 28. Subtractor, 32, multiplier 34, adder 36, and feedback delay element 38 are connected in a similar fashion to form a second exponential decay filter in series. The final output is at terminal 38.

The parameter g, the gain of multipliers 26 and 34, controls the extent of the filter, i.e. the width of the Gaussian bell curve. A particularly desirable feature of the IIR filter of FIG. 2 is that the multiply by g operations can be accomplished by a simple shift operation when g is of the form 2.sup.-n and by a simple shift and add when g is of the form 2.sup.-n +2.sup.-m or 2.sup.-n -2.sup.-m.

The three waveforms of FIG. 3 illustrate the operation of the filter of FIG. 1 when IIR filters 12 and 16 are of the type shown in FIG. 2. The input signal 11 is an impulse input to terminal 10 (FIG. 1). An intermediate signal 13 is the output of the first IIR filter 12 (FIG. 1). The output signal 15 is the result after time reversal, filtering in IIR 16, and a second time reversal.

The simplest way to accomplish time reversal is to record the entire signal into a (large) memory, and play back the entire signal in reverse order. An improved method of time reversal filtering in accordance with the present invention, is to divide the input signal into a number of segments, reverse each segment, filter each segment as desired, reverse each segment a second time, and finally combine the resulting segments to form the output signal.

The output signal of an IIR filter continues for many samples after the input signal ceases (i.e. after the end of the segment). In theory, it continues for an infinite amount of time, but in practice, it drops below a given threshold after a finite number of samples. If the signal is an image, the threshold can be set at 10.sup.-3, or if audio, at 10.sup.-6. The number of samples is ##EQU1##

For example, if the threshold is 10.sup.-3 and g is 0.25, then the output of the IIR will decay below the threshold after about 25 samples. Thus, each segment is extended (overlapped with the adjacent prior segment) by 25 samples to allow for the decay of the IIR filter. When segments are recombined into a continuous signal, each extension will overlap the preceding segment. The recombination is performed by simple addition. FIGS. 3A-3G illustrate the process.

The original signal after the first IIR filter output, 100 in FIG. 3A, is divided into segments 102, 103 (FIG. 3B). Each segment is reversed in time to form segments 104, 106 in FIG. 3C. Then, each segment is filtered by a second IIR filter as shown by segments 108, 110 in FIG. 3D. Also, while filtering segment 108, overlap samples 114 are created following the filtering. Similarly, while filtering segment 110, overlap samples 116 are created.

The reverse filtered segments with their respective overlap samples of FIG. 3D, are again time reversed in FIG. 3E to form forward segments 112, 120 with their respective forward overlap samples 118, 122. In FIG. 3F, forward segments 112, 120 are reassembled into the final output signal by adding the overlap 122, 121 from following segment to the respective portions of the prior segments. The final reassembled output signal segments 124, 126 are shown in FIG. 3G. The leading overlap samples 118 are the result of filtering the signal in the reverse direction back to the beginning plus the overlap in the reverse direction (overlap 114 in FIG. 3D), and then time reversing overlap 114 to form 118 in the output signal of FIG. 3G.

If a segment 102, 104 is stored in a random access memory, then it may be preferable to filter the segment in reverse direction, in place, rather than reverse the segment, filter it, and reverse it a second time. Memory to store the overlap samples 118, 122 would also be needed. Filtering in reverse direction, in place, is equivalent to the method described above.

It is possible to implement the present invention in software, using a circular buffer. The size of the circular buffer is equal to the segment size plus the overlap (25 samples in the preceding example). The segment size should generally be a small multiple of the overlap (i.e. if the multiple is 3, the segment size is 75 samples, and the total buffer size is 100 samples). An equivalent block diagram of the implementation using a circular buffer is shown in FIG. 6. A first IIR filter 182 is coupled to input terminal 180, and to controller 186. A second IIR filter 184 is also coupled to controller 186. A circular buffer 188 is provided, having a length equal to the chosen segment 192 plus the overlap 194. An address pointer 190 indicates the location within the circular buffer 188 for reading and writing data samples. The buffer 188 is circular in that incrementing (or decrementing) the address pointer 190 past the edge of the overlap 194 (or below the edge of the segment 192) will result in the pointer moving to the opposite end of the buffer. In other words, the pointer is moved forward and backward using modulo arithmetic, modulo the buffer size. A circular buffer provides a single memory element to perform both the first time reversal of the output from the first IIR filter 182, and the second time reversal the output of the second IIR filter 184. Filter output is provided at terminal 196.

A flow chart of a software program for the operation of controller 186 is shown in FIG. 4. In outline form, the software implementation repeats the following sequence, in which each iteration processes one segment's worth of signal samples including overlap samples:

A. Filter input values using the first IIR filter. Store one segment length of results in buffer, moving buffer pointer forward one segment length of samples, at step 80. In this example, the pointer starts at 0, and ends up at 75, after storing one segment length of values.

B. Reset second IIR filter at step 82, by setting filter delay memory to zero. In an analog RC exponential filter, a reset operation is the equivalent of discharging the charge stored on the capacitor to an initial condition of zero volts.

C. Filter buffer contents in the reverse order using the second IIR filter, and storing the result back into the buffer at step 84. The pointer decrements backward a total of one segment length. Continuing the above example, the pointer starts at 75 and decrements down to 0.

D. For the overlap, input zeros into the second IIR filter, and add the result to the buffer contents, decrementing the pointer backward by the overlap length at step 86. That is, the overlap between segments in the reverse direction is added to stored samples of the previous segment in the forward direction. Since the buffer is circular, the pointer decrements for 25 values from 99 to 75.

E. Output one segment length of values from the buffer, incrementing the pointer forward a total of one segment length, at step 88. The pointer increments from 75 to 99 and then from 0 to 50.

F. The pointer is moved forward by one overlap length at step 90. The pointer jumps from 50 to 75.

Each iteration performs the same signal processing, but leaves the pointer moved forward in the circular buffer a total of one segment length. After each iteration, the program checks whether all segments have been processed at step 92, and if all segments are not processed, the next segment is indexed at step 78. On the second iteration, the pointer starts at 75 and ends at 50. On the third iteration, the pointer starts at 50 and ends at 25. On the fourth iteration, the pointer starts at 25 and ends at 0.

In more detail, the above algorithm can be expressed as:

until all values have been processed.

As indicated above, image filtering applied separately in horizontal and vertical directions, making use of the property of separability of Gaussian filtering. Since the time reversal filter of the present invention is a close approximations to a Gaussian filter, the resulting filter response is close to radially symmetric. Scanned images are typically represented as a sequence of horizontal scan lines, known as a raster scan.

In the horizontal direction, each scan line is filtered using time reversal, but not using the segmented approach. However, in the vertical dimension, the segmented approach avoids the need to store all the scan lines of the image in order to perform TRGA filtering in the vertical direction. For vertical filtering, a buffer holds a number of scan lines, equal to the chosen segment length. Without the use of the segment technique, time reversal filtering is practical, but requires much disk activity if the image is too large to fit entirely in RAM. Given that the intermediate image stored on disk requires more bits (say, 16 instead of 8), and that it must be both written and read, it can require four times the amount of disk access than simply reading the source image or writing the resulting image. Further, the disk space or the disk may not be available. Thus, the method of segments, described above for the audio case, allows the filtering to proceed without requiring any disk storage. The intermediate segments are stored in RAM.

For audio signal processing, the present invention can be used for real time TRGA signal filtering. The output signal is delayed by the length of one segment, rather than for the entire two pass filtering process of recording, time reversal and playback. Thus, the present invention is very desirable for audio signal processing, in that it provides real time linear phase audio filtering. It also requires relatively few computational steps, yet results in very good quality at low cost.

The TRGA filter described above is essentially a low pass filter, designed to approximate a Gaussian frequency response. However, there are also applications for other types of filters, such as high pass and band pass filters, as well as specialized filters in which it is desirable to have precise control over the filter frequency characteristics. Such specialized filters may be realized by connecting a number of TRGA filters in parallel, each of which is tuned to a different coefficient, and summing the results of these multiplications to produce the resulting filtered signal. All of the filters must have the same buffer size or be synchronized by some delay means. The multiplying coefficients are selected so the frequency response matches the desired frequency response as closely as possible. As indicated, TRGA filtering is special because passing input signals in both forward and reverse directions through an identical filter eliminates phase shift distortions. Therefore, the use of TRGA filters results in a composite filter with the desirable property of linear phase.

Referring to FIG. 5, the input signal at terminal 50 is coupled to a delay 52, and TRGA filters 56, 62, and 68. The delay 52 delays the signal so that it is synchronized with the response peaks of filters 56, 62, and 68. Filters 56, 62, and 68 are each tuned to a different frequency, by adjusting the g parameter (FIG. 2). The results are multiplied by multipliers 54, 58, 64, and 70, by coefficients C.sub.0, C.sub.1, C.sub.2, through C.sub.n. The results of the multipliers are in turn summed by adders 60, 66, and 72, resulting in output signal at terminal 74.

The frequency response of the composite filter will be equal to the sum of the frequency response of each filter multiplied by its corresponding coefficient C. Mathematically expressed, if the frequency response of filter i, is represented by F.sub.1 (h), with F.sub.0 (h) assumed to be equal to one, then the frequency response of the composite filter is: ##EQU2##

A significant advantage of the present invention is that the number of operations is constant no matter how large the extent of the filter. However, the memory required for the intermediate segments does increase linearly with the extent of the filter. In conventional 2-D FIR filtering systems, the number of multiplications is rises quadratically with the extent of the filter. In 1-D and more sophisticated separable 2-D implementations, the number of multiplications rises linearly with the extent.

Another significant advantage of the present filter is that all filters are inherently stable, avoiding the instability problems and complex instability detection and compensation circuitry of traditional IIR designs.