This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
Digital Techniques For Processing 2d Analog Signals
Digital signal processing (DSP) is concerned with the representation of the signals by a sequence of numbers or symbols and the processing of these signals. Digital signal processing and analog signal processing are subfields of signal processing. DSP includes subfields like: audio and speech signal processing, sonar and radar signal processing, sensor array processing, spectral estimation, statistical signal processing, digital image processing, signal processing for communications, biomedical signal processing, seismic data processing, etc.
Since the goal of DSP is usually to measure or filter continuous real-world analog signals, the first step is usually to convert the signal from an analog to a digital form, by using an analog to digital converter. Often, the required output signal is another analog output signal, which requires a digital to analog converter. Even if this process is more complex than analog processing and has a discrete value range, the stability of digital signal processing thanks to error detection and correction and being less vulnerable to noise makes it advantageous over analog signal processing for many, though not all, applications.
DSP algorithms have long been run on standard computers, on specialized processors called digital signal processors (DSPs), or on purpose-built hardware such as application-specific integrated circuit (ASICs). Today there are additional technologies used for digital signal processing including more powerful general purpose microprocessors, field-programmable gate arrays (FPGAs), digital signal controllers (mostly for industrial apps such as motor control), and stream processors, among others.
2. Digital Techniques
Aliasing (For Image Processing)
In signal processing and related disciplines, aliasing refers to an effect that causes different signals to become indistinguishable (or aliases of one another) when sampled. It also refers to the distortion or artifact that result when the signal reconstructed from samples is different than the original continuous signal.
When a digital image is viewed, a reconstruction - also known as an interpolation - is performed by a display or printer device, and by the eyes and the brain. If the resolution is too low, the reconstructed image will differ from the original image, and an alias is seen. An example of spatial aliasing is the Moiré pattern one can observe in a poorly pixelized image of a brick wall. Techniques that avoid such poor pixelizations are called anti-aliasing. Aliasing can be caused either by the sampling stage or the reconstruction stage; these may be distinguished by calling sampling aliasing prealiasing and reconstruction aliasing postaliasing.
Temporal aliasing is a major concern in the sampling of video and audio signals. Music, for instance, may contain high-frequency components that are inaudible to human beings. If a piece of music is sampled at 32000 samples per second (sps), any frequency components above 16000 Hz (the Nyquist frequency) will cause aliasing when the music is reproduced by a digital to analog converter (DAC). To prevent that, it is customary to remove components above the Nyquist frequency (with an anti-aliasing filter) prior to sampling. But any realistic filter or DAC will also affect (attenuate) the components just below the Nyquist frequency. Therefore, it is also customary to choose a higher Nyquist frequency by sampling faster (typically 44100 sps (CD), 48000 (professional audio), or 96000).
In video or cinematography, temporal aliasing results from the limited frame rate, and causes the wagon-wheel effect, whereby a spoked wheel appears to rotate too slowly or even backwards. Aliasing has changed its apparent frequency of rotation. A reversal of direction can be described as a negative frequency.
Like the video camera, most sampling schemes are periodic; that is they have a characteristic sampling frequency in time or in space. Digital cameras provide a certain number of samples (pixels) per degree or per radian, or samples per mm in the focal plane of the camera. Audio signals are sampled (digitized) with an analog-to-digital converter, which produces a constant number of samples per second. Some of the most dramatic and subtle examples of aliasing occur when the signal being sampled also has periodic content.
Band Limited Functions
Actual signals have finite duration and their frequency content, as defined by the Fourier transform, has no upper bound. Some amount of aliasing always occurs when such functions are sampled. Functions whose frequency content is bounded (bandlimited) have infinite duration. If sampled at a high enough rate, determined by the bandwidth, the original function can in theory be perfectly reconstructed from the infinite set of samples.
Band Pass Signals
Sometimes aliasing is used intentionally on signals with no low-frequency content, called band pass signals. Under sampling, which creates low-frequency aliases, can produce the same result, with less effort, as frequency-shifting the signal to lower frequencies before sampling at the lower rate. Some digital channelizers exploit aliasing in this way for computational efficiency; see IR/RF sampling.
Sampling Sinusoidal Functions
Sinusoids are an important type of periodic function, because realistic signals are often modeled as the summation of many sinusoids of different frequencies and different amplitudes (with a Fourier series or transform). Understanding what aliasing does to the individual sinusoids is useful in understanding what happens to their sum.
Here a plot depicts a set of samples whose sample-interval is 1.0, and two (of many) different sinusoids that could have produced the samples. The sample-rate in this case is . For instance, if the interval is 1 second, the rate is 1 sample per second. Nine cycles of the red sinusoid and 1 cycle of the blue sinusoid span an interval of 10. The respective sinusoid frequencies are = 0.9 and = 0.1.
In general, when a sinusoid of frequency is sampled with frequency the resulting samples are indistinguishable from those of another sinusoid of frequency for any integer (with being the actual signal frequency). Most reconstruction techniques produce the minimum of these frequencies, so it is often important that be the unique minimum. A sufficient condition for that is where is commonly called the Nyquist frequency of a system that samples at rate .
In our graphic example, the Nyquist condition is satisfied if the original signal is the blue sinusoid (). But if the lowest image frequency is:
- A reconstruction technique that constructs the lowest possible frequency from the samples will reproduce the blue sinusoid instead of the red one.
- We note that is also an image frequency, but since there is no way to distinguish a sinusoid of frequency from one of frequency all aliases can be described in terms of just positive frequencies.
When the condition is met for the highest frequency component of the original signal, then it is met for all the frequency components, a condition known as the Nyquist criterion. That is typically approximated by filtering the original signal to attenuate high frequency components before it is sampled. They still generate low-frequency aliases, but at very low amplitude levels, so as not to cause a problem. A filter chosen in anticipation of a certain sample frequency is called an anti-aliasing filter. The filtered signal can subsequently be reconstructed without significant additional distortion, for example by the Whittaker-Shannon interpolation formula.
The Nyquist criterion presumes that the frequency content of the signal being sampled has an upper bound. Implicit in that assumption is that the signal's duration has no upper bound. Similarly, the Whittaker-Shannon interpolation formula represents an interpolation filter with an unrealizable frequency response. These assumptions make up a mathematical model that is an idealized approximation, at best, to any realistic situation. The conclusion, that perfect reconstruction is possible, is mathematically correct for the model, but only an approximation for real samples of a real signal.
Complex Signal Representation
Complex signals are signals whose samples are complex numbers, and the concept of negative frequency is necessary for such signals. In that case, the frequencies of the aliases are given by just: Therefore, as increases from to the image closest to 0 moves from up to 0.
Real-valued sinusoids have the same negative-frequency aliases as complex ones. The absolute value operator, is introduced because there is always an equivalent sinusoid with a positive frequency. Therefore, as increases from to an image moves from down to 0. This creates a local symmetry about the frequency For example, a frequency component at has a "mirror" image at That effect is commonly referred to as folding. And another name for (the Nyquist frequency)is folding frequency.
Historically the term aliasing evolved from radio engineering because of the action of superheterodyne receivers. When the receiver shifts multiple signals down to lower frequencies, from RF to IF by heterodyning, an unwanted signal, from an RF frequency equally far from the local oscillator (LO) frequency as the desired signal, but on the wrong side of the LO, can end up at the same IF frequency as the wanted one. If it is strong enough it can interfere with reception of the desired signal. This unwanted signal is known as an image or alias of the desired signal.
Aliasing occurs whenever the use of discrete elements to capture or produce a continuous signal causes frequency ambiguity.
Spatial aliasing, particular of angular frequency, can occur when reproducing a light field or sound field with discrete elements, as in 3D displays or wave field synthesis of sound.
This aliasing in visible in images such as posters with lenticular printing: if they have low angular resolution, then as one moves past them, say from left-to-right, the 2D image does not initially change (so it appears to move left), then as one moves to the next angular image, the image suddenly changes (so it jumps right) - and the frequency and amplitude of this side-to-side movement corresponds to the angular resolution of the image (and, for frequency, the speed of the viewer's lateral movement), which is the angular aliasing of the 4D light field.
The lack of parallax on viewer movement in 2D images and in 3-D film produced by stereoscopic glasses (in 3D films the effect is called "yawing", as the image appears to rotate on its axis) can similarly be seen as loss of angular resolution, all angular frequencies being aliased to 0 (constant).
Online "Live" Example
The qualitative effects of aliasing can be heard in the following audio demonstration. Six sawtooth waves are played in succession, with the first two sawtooths having a fundamental frequency of 440 Hz (A4), the second two having fundamental frequency of 880 Hz (A5), and the final two at 1760 Hz (A6). The sawtooths alternate between bandlimited (non-aliased) sawtooths and aliased sawtooths and the sampling rate is 22.05 kHz. The bandlimited sawtooths are synthesized from the sawtooth waveform's Fourier series such that no harmonics above the Nyquist frequency are present.
The aliasing distortion in the lower frequencies is increasingly obvious with higher fundamental frequencies, and while the bandlimited sawtooth is still clear at 1760 Hz, the aliased sawtooth is degraded and harsh with a buzzing audible at frequencies lower than the fundamental. Note that the audio file has been coded using Ogg's Vorbis codec, and as such the audio is somewhat degraded.
A form of spatial aliasing can also occur in antenna arrays or microphone arrays used to estimate the direction of arrival of a wave signal, as in geophysical exploration by seismic waves. Waves must be sampled at more than two points per wavelength, or the wave arrival direction becomes ambiguous.
A device for converting the information contained in the value or magnitude of some characteristic of an input signal, compared to a standard or reference, to information in the form of discrete states of a signal, usually with numerical values assigned to the various combinations of discrete states of the signal.
Analog-to-digital (A/D) converters are used to transform analog information, such as audio signals or measurements of physical variables (for example, temperature, force, or shaft rotation) into a form suitable for digital handling, which might involve any of these operations: (1) processing by a computer or by logic circuits, including arithmetical operations, comparison, sorting, ordering, and code conversion, (2) storage until ready for further handling, (3) display in numerical or graphical form, and (4) transmission.
If a wide-range analog signal can be converted, with adequate frequency, to an appropriate number of two-level digits,or bits, the digital representation of the signal can be transmitted through a noisy medium without relative degradation of the fine structure of the original signal. See also Computer graphics; Data communications; Digital computer.
Conversion involves quantizing and encoding. Quantizing means partitioning the analog signal range into a number of discrete quanta and determining to which quantum the input signal belongs. Encoding means assigning a unique digital code to each quantum and determining the code that corresponds to the input signal. The most common system is binary, in which there are 2n quanta (where n is some whole number), numbered consecutively; the code is a set of n physical two-valued levels or bits (1 or 0) corresponding to the binary number associated with the signal quantum.
The illustration shows a typical three-bit binary representation of a range of input signals, partitioned into eight quanta. For example, a signal in the vicinity of 3/8; full scale (between 5/16 and 7/16) will be coded 011 (binary 3).
2-D Filtering A Raster Scanned Image In Real Time
A method and an arrangement for realizing true 2-D analog filtering structures of either IIR or FIR type in hardware using only analog devices and line delays. The wide variety of 2-D signal processing techniques that are based on a 2-D transfer function of general order can be implemented. 2-D analog filters are realized in hardware that can directly operate on a raster scanned image without the need for expensive frame stores, A/D and D/A converters. The high-speed operation inherent in the analog nature of the processing makes possible real-time operation at the high data rates of analog raster scanned images, even at high pixel resolution as in HDTV. Many applications involving TV imaging in such areas as advanced television systems, industrial and biomedical video systems are possible.
Background Of The Invention
In the development of new receivers for television, more advanced signal processing techniques will be implemented in the circuitry of the video processing section. It has been proposed that such advanced video signal processing can be carried out by high-speed two-dimensional (2-D) spatial filtering or by three-dimensional (3-D) temporal filters. See for example, "Digital Signal Processing in Television Receivers" by M. J. J. C. Annegarn, A. H. H. J. Nillesen, and J. G. Raven, Philips Tech. Rev. 42, No. 6/7, 183-200, Apr. 1986. Newer receivers will display pictures that have higher pixel resolution. For what has been termed High Definition Television (HDTV), if the processing is done in real-time, that is, at the same rate as the effective sampling rate of the picture, processing rates as high as 40 million pixels/sec would be required. Methods of deriving high-speed filtering structures cast in the form of practical apparatus, constructed entirely from conventional devices and components, are of current interest not only for application in the area of advanced television systems, but also in the area of biomedical and industrial video applications. Such a method of deriving practical structures together with the characteristic high-speed two-dimensional video signal processing apparatus that results from the application of the method is the subject of the present invention.
In the past analog signal processing techniques such as noise coring, edge peaking, and comb filter separation of luminance and chrominance signals have been based on one-dimensional time domain approaches implemented as simple Finite Impulse Response (FIR) signal processing structures. These have been quite limited as to the type of signal processing and enhancement operations that could be performed by the characteristic type of apparatus that resulted from following that approach. In general, an FIR filter structure will require a higher order signal processing structure than for an equivalent Infinite Impulse Response (IIR) filter structure; hence, the complexity of apparatus that would be required to embody such an FIR structure will be correspondingly greater. The method of the present invention overcomes these limitations by making possible the derivation of true 2-D signal processing apparatus with the real-time capability inherent in analog devices and components, allowing the implementation of the gamut of 2-D filtering techniques in either IIR or FIR structures.
The direct application of techniques for filtering 2-D data, known from the field of Mathematical Image Processing Theory, has been hampered by the difficulty in developing digital filter structures that can be embodied in the form of practical conventional digital hardware apparatus that can operate at the high data rates required for real-time video signal processing. See for example, "High-Speed Architectures for Digital Image Processing", by A. N. Venetsanopoulos, K. M. Ty, and A. C. P. Loui, IEEE Trans. on Circuits and Systems, Vol. CAS-34., No. 8, 887-895, Aug. 1987. Considerations of hardware complexity, physical size of apparatus, power consumption, and economical manufacture are all of vital importance in any practical signal processing apparatus intended for use in consumer products. The present invention overcomes these difficulties by introducing a method and an apparatus in which the two-dimensional s,z transform is used to derive 2-D signal processing structures for performing 2-D signal processing in accordance with given specifications. These given specifications may be those that arise out of the need or desire to implement either well-known or newly derived Image Processing techniques. Those embodiments of 2-D signal processing apparatus derived by the method of the present invention are comprised of line delays, analog summing amplifiers, analog inverting amplifiers, analog integrators and passive components. The use of analog devices makes these embodiments inherently capable of real-time operation while remaining practical in light of the above mentioned considerations.
Recently, motion adaptive digital filters have been proposed for use in high-definition television video signal processing. These can be regarded as common 3-D FIR filters, for the implementation of techniques for video signal processing. They require delays of one or more field periods, such delays being accomplished by means of frame-stores. Since pixels in separate fields are combined, this type of signal processing is referred to as temporal filtering and can only be performed on those pixels for which no motion in the scene of the picture being displayed has occurred between fields. Thus the development of such a filter is complicated by the necessary inclusion of circuitry that implements a motion detection algorithm. The embodiments of apparatus arising out of the present invention do not require analog to digital (A/D) and digital to analog (D/A) converters, often used in conjunction with analog pre-filters and post-filters, to convert video signal data from analog raster scanned form to sampled digital data for processing; nor do they require expensive frame-stores or motion detection circuitry.
Other methods of performing real-time 2-D signal processing have been based on elaborate algorithms such as the Burt Pyramid which separates an image into a number of 2-D spatial frequency bandpass images. See for example, "A Two-Dimensional Real-Time Video Pyramid Processor", by J. H. Arbeiter and R. F. Bessler, RCA Review, Vol. 47, 3-31, March 1986. This method, although capable of real-time operation, has the disadvantage of greater complexity relative to the present invention, due to the need to process multiple bands and to generate a set of component images. When embodied in digital hardware, a large amount of circuitry is required along with the need for A/D, and D/A converters
Summary Of The Invention
The object of the present invention is to provide a method and an apparatus for two-dimensionally filtering (i.e. signal processing) a raster scanned image in real-time, with either IIR or FIR structures, without the need for expensive digital systems that require A/D and D/A converters. In this method, a raster scanned image is interpreted as a 2-D input signal x(t,nT) consisting of individual horizontal lines occurring in discrete time periods nT.
In accordance with this method, an equation is arrived at which indicates how the output signal is determined in terms of the basic operations of delaying a signal by one or more line scanning periods, multiplications by scale factors, inversions.
A derived structure in terms of basic operational elements is thus obtained which can be embodied in practical
The type of apparatus characteristic of the present invention has advantages in view of considerations of hardware complexity, physical size of apparatus, power consumption and economical manufacture. Moreover, the high-speed operation inherent in the analog nature of the processing makes possible real-time operation at the high data rates of analog raster scanned images, even at high pixel resolution, as in HDTV.
Real Time 2-D Filtering Of Video Signals
A method and device for real time processing of analog signals, such as video signals, representative of frames of data acquired in row order in a two dimensional field. The incoming signal is processed (for example filtered) by analog means, transposed to column order, processed again by analog means, and transposed back to row order. The transpositions are done by digitizing each frame of the signal, transposing the digital signal, and converting the transposed digital signal back to analog form. The process can be pipelined to be accomplished in real time with only a constant delay of two frames.
Field And Background Of The Invention
The present invention relates to video processing and, more particularly, to a method and device for real-time two dimensional filtering of video signals.
Video cameras are familiar in their industrial (e.g., commercial television) and consumer (home video) applications. A video camera renders the scene being photographed as a video image, which is an electrical voltage as a function of time. As such, it is a one-dimensional signal that represents the two-dimensional line-scanned scene. The two-dimensionality of the scene is represented in the video image by synchronization pulses, which allow a two-dimensional representation of the scene to be reconstructed from the one-dimensional video image.
Video images suffer from two kinds of distortion. One kind is inherently two-dimensional, associated with factors such as atmospheric blur, image motion, vibration blur and defocusing. The other kind is inherently one-dimensional and includes noise imposed on the video image by the electronic system of the camera. One-dimensional distortions can be suppressed by one-dimensional techniques. Two-dimensional distortions suppression requires two-dimensional techniques.
Because analog techniques operate on the video signal itself, which is inherently one dimensional, the usual approaches to picture enhancement and restoration are digital techniques, include digital signal processing (DSP) and digital filtering. The development of DSP microprocessors has made DSP the method of choice in recent years. Unfortunately, real time DSP requires relatively expensive DSP microprocessors.
Consider, for example, a typical DSP sequence performed on a 512×512 pixel video frame. The sequence includes a forward 2D FFT (3.15 million floating point operations), multiplication by a restoration filter in the transform domain (0.2 million floating point operations), and an inverse 2D FFT (another 3.15 million floating point operations). Adding to this 20% overhead for branches in program execution and 20% overhead associated with parallelization gives a total of about 10 million floating point operations to process one video frame. Convolutional processing generally requires even more operations than FFT processing: a 4×4 convolution of a 512×512 pixel frame requires 8.38 million floating point operations. At a standard rate of 25 frames per second (Europe) or 30 frames per second (USA), this means that a DSP microprocessor must perform at speeds in excess of 250 Mflops just to perform the calculations. If the operations needed to transfer the data to and from the processor are included, it turns out that the processor must perform faster than 400 Mflops if programmed in assembler language and faster than 600 Mflops if programmed in a high level language such as C. Typical moderately priced DSP microprocessors do not achieve these speeds.
DSP has other disadvantages. The millions of floating point operations applied to a single video frame introduce numerical roundoff error. The operation count cited above is for a power-of two FFT. The pixel dimensions of typical video frames often are not powers of two, so either the digitized frames must be padded with zeros or an even slower DFT (Digital Fourier Transform) must be performed. These disadvantages would be obviated if two-dimensional picture enhancement could be done by analog means.
There is thus a widely recognized need for, and it would be highly advantageous to have, and at least partly analog method and device for two-dimensional video picture enhancement.
Summary Of The Invention
According to the present invention there is provided a method of processing a frame of an input analog signal, including the steps of: (a) transposing the frame, thereby producing a transposed analog frame; and (b) analog processing the transposed analog frame, thereby producing a processed analog frame.
According to the present invention there is provided a method of processing successive frames of an input analog signal including the steps of: for each frame of the input analog signal: (a) transposing the frame, thereby producing a transposed analog frame; and (b) analog processing the transposed analog frame, thereby producing a processed analog frame.
According to the present invention there is provided a device for processing successive input frames of an input analog signal including: (a) a first A/D converter for digitizing each of the input frames, thereby producing a first digital frame; (b) a mechanism for transposing each of the first digital frame, thereby producing a first transposed digital frame; (c) a first D/A converter for converting each of the first transposed digital frame to a transposed analog frame; and (d) a mechanism for analog processing of each of the transposed analog frame to a processed analog frame.
The general approach of the present invention is illustrated in the high level block diagram of FIG. 1. Each frame of the incoming video signal, in which the pixels appear in row order, is filtered by an analog filter, transposed to column order, filtered again by an analog filter, and transposed back to row order to give the output video signal. Typically, the two analog filters are identical. As explained below, the transpositions are performed digitally; but digital transposition is much faster than two-dimensional digital filtering. Unlike the digital operations performed in DSP, the operations performed by the present invention on the digitized samples change only the order in which those samples are stored, and not the sample values themselves. Therefore, the only noise added to the signal by the digital portion of the present invention is digitization noise. The noise added by modern analog filters, which have a signal-to-noise ratio better than 80 dB, is negligible.
The scope of the present invention includes two dimensional processing generally of any analog signal that represents frames of data acquired in a two-dimensional field, and includes processing in general that can be realized by analog circuits, not just filtering. Nevertheless, the primary intended application of the present invention is to video processing, and the present invention is described below in terms of video processing