PPI to Raster Display Scan Converter

This invention relates to apparatus for the conversion of video information from a radar receiver for display on a cathode ray tube (CRT). More particularly, the radar data is received in a polar coordinate format (R,.theta.) and converted to a cartesian coordinate format (X,Y) for display on a raster type display device.

The presentation of radially formatted Plan Position Indicator (PPI) type radar data at high resolution has been virtually the exclusive domain of cursive displays. Presentation of such radially formatted data on raster type displays requires a conversion of the scanning direction from radial or polar coordinates to X,Y coordinates; unfortunately, such a conversion cannot be conducted as a one-to-one memory cell exchange because a one-to-one correspondence between R,.theta. radial cells and X,Y raster cells does not exist.

The prior art attempts to perform the needed conversion from a polar to a cartesian coordinate format by the use of a "closest proximity" re-mapping scan converter approach. With this technique, sample cells of incoming radial data are mapped into the nearest corresponding X,Y addresses. However, the resultant scan converted image is at best marginal and the following deficiencies become evident: the detailed shape of video information is seriously deformed with a resultant loss of net resolution; all X,Y cells do not necessarily contain converted data, that is, black holes can occur within "target" boundaries; the radial intervals between active radials tend to form Moire patterns with the raster X,Y address which are very distracting to an operator; and the storage of converted data in final refresh memory format is complicated by the fact that it is not produced in normal X,Y scanning order. The present invention eliminates all of these deficiencies.

Another approach in the prior art performs a coordinate conversion on radar video input data corresponding to each azimuth angle of a transmitted radar beam. However, time consuming calculations comprising determining trigonometric functions and multiplications have to be performed requiring high speed arithmetic hardware instead of primarily using simple adders.

Other approaches in the prior art of scan converters have involved "horizontal smearing" or "tangential smearing" techniques for filling data gaps between radial lines and/or between regions on each radial. To avoid said gaps, the data for each particular region is used from surrounding regions to fill in the gaps. However, these approaches although probably sufficient for some low density and low resolution applications are not as precise and lack the conversion speed generally required for radar applications where each radial is converted when its data is available rather than waiting for all radial lines to be stored and then initiating a conversion process.

This invention discloses an apparatus and method for converting data such as radar data defined by an R,.theta. polar coordinate format to an X,Y cartesian coordinate format for display on a raster display primarily utilizing addition calculations. X addresses and Y addresses are generated for specifying picture elements on a raster display. A radial address is also generated in polar coordinates for each picture element within a standard angle increment on a raster display and this radial address specifies the location of the stored input data that is to be transferred to a mass memory location specified by an X address and a Y address. The radial address represents the range of a picture element from an origin in the X,Y cartesian coordinate system. The X and Y addresses and corresponding radial addresses are generated for all picture elements within a standard angle increment and for all successive standard angle increments which correspond to successive input radial paths comprising digitized data obtained for increments of range along an azimuth angle. The X addresses and the Y addresses for picture elements on a raster display directly correspond to the X addresses and Y addresses of mass memory locations used for the storage of input data prior to transmittal to a raster display. A standard angle increment is the difference between two adjacent standard angles and a quadrant, octant or a full 360.degree. is divided up into a sufficient number of standard angles to enable the required coordinate conversion calculations to be accomplished primarily by additions and an occasional multiplication. Predetermined coordinate conversion values for each standard angle are stored in PROMs.

The invention further discloses means for specifying a standard angle for use during a conversion of defining data with polar coordinates to cartesian coordinates with an input signal causing an advance to successive standard angles, first memory means responsive to the standard angle specifying means for storing conversion values for each standard angle providing a change in an X address for each increment of a Y address, first accumulating means responsive to the first memory means for generating X addresses and for determining start and end boundaries of a plurality of X addresses within a standard angle increment which is the difference between two adjacent standard angles, and means for generating a plurality of successive Y addresses within a standard angle increment during the conversion. In addition, second memory means is disclosed responsive to the standard angle specifying means for storing conversion values for each standard angle, said conversion values providing a change in a range radial described by a radial address for each increment of a Y address which extends from an origin to each said X address and Y address location of a corresponding standard angle boundary. Also disclosed are third memory means responsive to the standard angle specifying means for storing conversion values for each standard angle providing a change in the range radial or radial address for each increment of an X address, second accumulating means for summing the output of the second memory means for each increment of the Y address during a standard angle increment conversion, third accumulating means for summing the incremental changes in the radial address resulting from incremental changes in the X address and Y address wherein the radial address specifies the location of stored input data to be transferred to a mass memory location specified by the X address and Y address, multiplier means responsive to the first accumulating means and third memory means for calculating changes of the radial address resulting from a non-integer increment in said X address, and decoder means responsive to the third accumulating means for determining when a maximum radial address or a maximum X address is reached. The standard angle specifying means comprises one or more counters, and quadrant control means increment or decrement the counters.

This invention further discloses the method of converting data defined by R,.theta. polar coordinate format to X,Y cartesian coordinate format for display on a raster scan display comprising the steps of generating a plurality of X addresses to specify picture elements on said raster display, generating a plurality of Y addresses to specify picture elements on the raster display, generating a radial address in polar coordinates corresponding to a selected picture element within a standard angle increment on a raster display having an X address and a Y address in cartesian coordinate, said radial address specifying the location of stored input data to be transferred to a mass memory location specified by the X address and the Y address, generating successive X,Y addresses and corresponding radial addresses for all picture elements on a raster display within a standard angle increment, said increment being the difference between two successive standard angles, generating successive X,Y addresses and corresponding radial address for successive standard angle increments corresponding to successive input radial paths, and storing coordinate system conversion values for each said standard angle used for the generation of said X addresses, Y addresses and radial addresses. The step of storing conversion values includes values for each standard angle within an octant, a quadrant or full 360 degrees.

Other and further features and advantages of the invention will become apparent in connection with the accompanying drawings wherein:

FIGS. 1A and 1B together are a block diagram representation of the invention;

FIG. 2 illustrates a PPI display in R,.theta. format;

FIG. 3 illustrates a portion of a rectangular X,Y raster display showing a .DELTA.R increment per .DELTA.X increment for two adjacent pixels A and B on a Y line;

FIG. 4 illustrates a standard angle increment .DELTA..theta. during a scan conversion with a start boundary 1 defined by .theta..sub.1 and a stop boundary 1 defined by .theta..sub.2, and showing pixels on two adjacent raster lines Y.sub.1 and Y.sub.2 ; and

FIG. 5 is an enlargement of the area around pixels 4 and 5 on a raster display near the intersection of the Start Boundary 1 side of a standard angle with a raster line Y.sub.2 showing the non-integer or fractional distance .DELTA.X.sub.b and the integer distance .DELTA.X.

Referring now to FIGS. 1A and 1B, there is shown a block diagram of a digital scan converter according to the present invention for converting radar data in polar coordinates to a cartesian coordinate format for display on a raster type display. Radar beams are transmitted as a series of pulses and the radar returns are received in an R,.theta. format as illustrated in FIG. 2 where .theta. is the azimuth position of a radar antenna transmitting a beam and R represents the range radial of targets reflecting the radar beams. This data is readily displayed as a PPI representation on a CRT which has an effective circular display coinciding with the actual radar operation. However, the data may also be displayed on a raster type display, one quadrant of which is partially illustrated in FIG. 3. Each picture element (pixel) along the horizontal scan lines such as A or B is represented by an X,Y address where the X address is the horizontal distance from any chosen vertical reference line on the CRT and the Y address is the vertical distance from any chosen horizontal (reference) line. The hardware of FIGS. 1A and 1B assume an X,Y reference corresponding to the radar center as mapped onto the raster display. The scan converter sequentially fills mass memory locations, corresponding to X,Y positions within each predefined standard angle increment (.DELTA..theta.) as shown in FIG. 4, with radar data from sample positions along the stored radar data radial applicable to the standard angle increment (.DELTA..theta.). There typically are 200 to 250 standard radials per quadrant in order to keep the .DELTA..theta. angle increments less than 0.5.degree. to facilitate the conversion approximation calculations.

The scan converter for performing a coordinate conversion is shown in FIGS. 1A and 1B and comprises Radial Conversion Counter A 10 and Radial Conversion Counter B 40 which generate the addresses for the programmable read-only memories (PROM) that contain the constants applicable to each standard angle. Because standard angles are produced sequentially, sequential counts of the conversion counters define successive regions for conversion. Each counter is incremented by a Next Radial 70 signal. The Radial Conversion Counter A 10, an 8-bit counter, provides an address to PROM 14 and Radial Conversion Counter B 40, also an 8-bit counter, provides an address for PROMs 42 and 44. They are reset to zero via the Quadrant Control 12 logic by the North Reference 72 signal. If N is the number of radials per quadrant, the Radial Conversion Counter A increments from 1 to N in the first quadrant, decrements from N to 0 in the second quadrant, increments from 1 to N in the third, and decrements from N to 0 in the fourth quarter. Radial Conversion Counter B 40 functions similarly except it counts up from 0 to N-1 in the first quadrant, starts at N-1 in second quadrant and counts down to 0, starts at 0 in the third quadrant and counts up to N-1, and starts at N-1 in the fourth quadrant and counts down to 0.

Still referring to FIGS. 1A and 1B, PROM 14 provides a 23 bit (9 integer, 14 fractional) conversion factor for the change in the X address of intersection of the applicable standard radial for each increment of Y address. This factor represents .DELTA.X/.DELTA.Y which equals tan .theta.. Since the processing of successive X,Y points within the present standard angle increment proceeds across all applicable X points for a given Y line, the value defined by PROM 14 must be added (together with the value corresponding to the previous standard angle) to accumulators through registers to define the X boundaries of the next Y line to be processed. An additional bit from PROM 14 indicates Theta Max 71 which inhibits X Comparator 30 and causes an increment in Y only when the MAX-X Advance Y Line 88 signal occurs, since at 90.degree. and 270.degree. the Tan .theta. is infinite and cannot be added to an accumulator. .theta. is defined as the upper standard angle in the first quadrant. When there are 200 standard angles or radials per quadrant, .theta. steps from 0.45.degree. to 90.00.degree..

The radial range of the starting point of intersection of the applicable standard angle increment (one extreme) with successive Y lines must be defined so that the total radial range of each X,Y point can be computed. PROM 42 provides a 23-bit (10 integer, 13 fractional) conversion factor which represents the increment in radial range for each increment in the Y direction along one boundary of the standard angle or .DELTA.R/.DELTA.Y=K/cos .theta.. The K term within this expression allows for the accommodation of scale (sampling density) differences between mass memory (used for display refresh) storage cell equivalent size and the separation between successive stored radar return samples. PROM 44 provides the change in radial range which results from each increment in the X direction or .DELTA.R/.DELTA.X=K sin .theta. for each standard radial. This 14-bit value (2 integer, 12 fractional) is added to the Range Accumulator 54 each time the X address (for a given Y address) is incremented. Both PROM 42 and PROM 44 are addressed by the 8-bit output of Radial Conversion Counter B 40.

Register 16 and Register 18 each provide temporary storage for the previous .DELTA.X/.DELTA.Y value produced by PROM 14. The particular register being used during a standard angle conversion is dependent upon the Quadrant Control 12 logic. Using these registers, the upper bound X address of the previous standard angle increment becomes the lower bound X address of the present standard angle increment, thereby assuring the absence of mathematical round-off error at standard angle boundaries. Register 16 connects to the X Start Accumulator 20 which is comprised of a 25-bit, (11 integer, 14 fractional) adder-register combination. It repeatedly (for each increment in Y) adds the value of .DELTA.X/.DELTA.Y corresponding to the present standard angle start boundary to produce a definition of the starting X address of X line segments to be processed on each successive Y line of the current standard angle. Register 18 connects to the X End Accumulator 22 which comprises a 25-bit (11 integer, 14 fractional) adder-register combination. It repeatedly (for each increment in Y) adds the value of .DELTA.X/.DELTA.Y corresponding to the present standard angle stop boundary to produce a definition of the ending X address of the X line segments to be processed on each successive Y line of the current standard angle.

The X Start Accumulator 20 connects to the X Adder 28 which combines the integer portion of the X address of the standard angle start for the current Y line with the X Increment Counter 26 integer output thereby providing a definition of the current X address being processed. The X Increment Counter 26 comprising 11 bits or stages defines the total number of X addresses which have been processed (plus the present X address being processed) since the start of the current Y line processing. This counter is effectively reset to 1 at the start of each Y line processing within a standard angle except for standard angles starting at 0.degree. and 180.degree. at which point it is preset to 0. A Clock 24 connects to the X Increment Counter 26 as well as controlling all other pixel synchronous operations. The output of the X Adder 28 connects to a Bus Driver 32 which also receives an X Sign 76 Signal from the Quadrant Control 12. The output of the Bus Driver 32 is an X Address 78 which is one of the three main outputs of the scan converter shown in FIGS. 1A and 1B.

The X Adder 28 output also connects to an X Comparator 30. Another input to the X Comparator 30 is the output of the X End Accumulator 22. This 12-bit comparator continuously compares the present integer X address with the maximum integer X address for the current Y line. Detection of an equals condition causes completion of that current point conversion and an advance to the next Y line. Detection of a present X greater than maximum causes the aborting of the present point conversion and an advance to the next Y line. The Y line is also advanced when the maximum range for a selected radar field is reached as determined by Decoder 56 which generates a Radial Complete Interrupt 86 signal effectively causing the reset of the Y Increment Counter by Reset 79 signal. The output of the X Comparator 30 is a Y Line Advance 80 Signal which connects to the Y Increment Counter 34, the X Start Accumulator 20, the X End Accumulator 22, the X Increment Counter 26 and the Radial Accumulator 46. The Y Increment Counter 34 provides a definition of the current Y line. The output connects to Bus Driver 36 which provides a Y Address 82 which is the second main output of the scan converter.

The output word from PROM 42 connects to a 25-bit (12 integer, 13 fractional) Radial Accumulator 46 comprising an adder-register combination. It repeatedly adds (for each increment in Y) the value of .DELTA.R/.DELTA.Y to produce a radial sample address applicable to the intersection of the starting standard angle boundary with the current Y line. A 24-bit output from Radial Accumulator 46 connects to one side of Multiplexer 52. A 14-bit output word from PROM 44 connects to Multiplexer 50. Four bits of the output word from PROM 44 connect to a 4-bit Multiplier 48. Because the X address corresponding to the beginning of a standard angle increment (for each Y line) is not in general an integer, the Range Accumulator 54 must be increased in proportion to the fraction remaining to the next integer X address such as .DELTA.X.sub.b in FIG. 5. The 4-bit Multiplier 48 approximates this correction by weighting the .DELTA.R/.DELTA.X magnitude with the ones complement of the fractional portion of the start point address. An 8-bit output from the 4-bit Multiplier 48 connects to the other side of Multiplexer 50. Multiplexers 50 and 52 select the appropriate components for addition to the Range Accumulator 54. At the beginning of each new Y line of a standard angle, the multiplexers provide the output of the Radial Accumulator 46 and the output of the 4-bit Multiplier 48 for summation into the Range Accumulator 54. For each subsequent X increment for the current Y scan line, the multiplexers permit the summation of the Range Accumulator 54 with the value of .DELTA.R/.DELTA.X provided by PROM 44. The Range Accumulator 54 is a 24-bit (12 integer, 12 fractional) adder-register combination which defines the stored radar radial video memory address that corresponds to the current X,Y point being processed. At the beginning of each new Y line within a standard angle, this register is caused to assume the range address corresponding to the next integer X address after the X address corresponding to the beginning boundary of the current standard angle at that Y line. For each additional X increment on that Y line, the register is incremented by the value of .DELTA.R/.DELTA.X from PROM 44 for that standard angle. The output of Range Accumulator 54 connects to Bus Driver 58 which provides a 12-bit Radial Address 84 which is a third main output of the scan converter. Decoder 56 receives four MSB signals from Range Accumulator 54 and generates the Radial Complete Interrupt 86 which indicates an advance to the next input radial for processing and the Max X-Advance Y Line 88 signals.

Referring now to FIG. 3, the geometric relationships are shown for a change in radial R (.DELTA.R) per change in X (.DELTA.X). The parameters are defined as follows:

R=Known range to a specific point A on an X line (e.g. the intersection of an X start boundary with current X line).

.DELTA.X=Displacement along X line from known intersection point A (e.g. one integer increment in X address).

R+.DELTA.=Range of point B on X line at end of .DELTA.X displacement.

.DELTA.R=Extension of range resulting from .DELTA.X displacement.

.phi.=Azimuthal angle subtended by .DELTA.X.

.theta.=Standard angle.

The determination by the scan converter of the change in radial range which results from each increment in the x direction is based on the approximation

which is derived as follows:

From the law of cosines,

Define a variable

Then,

and substituting the identity in equation (2) results in

From the law of sines, ##EQU1## so,

and substituting for (.DELTA.X).sup.2 cos.sup.2 .theta. in equation (6)

or,

and, ##EQU2##

Substituting equation (3) into equation (12) ##EQU3##

A starting point A along X in FIG. 3 is defined by the angle .theta. and is analogous to an X start address in the coordinate conversion process. The angle .phi. depends upon the value of .DELTA.X chosen but cannot be larger than the angular separation between standard angles. For radar systems .phi.max equal to .DELTA..theta. is usually 0.5.degree. or smaller but may in some applications be 1.0.degree.. For, .vertline..phi..vertline.<0.5.degree.

and, ##EQU4##

Substitution of the lower and upper bounds of (15) into equation (13) produces

Therefore,

When .phi..ltoreq.0.5.degree. and for values of R less than 10,000, the approximation

provides less than 0.5 error in the R+.DELTA.R length. Few applications require display magnifications or display resolutions which would approach an R of 10,000. Therefore, equation (19) is sufficiently accurate approximation of .DELTA.R. Even when .phi..sub.max =1.0.degree., approximation (19) is sufficiently accurate for R values as large as 2500. The values of .DELTA.R for increments of .DELTA.X are calculated using equation (19) and stored in PROM 44.

PROM 14 supplies the change in the X address (.DELTA.X) of intersection of the applicable standard radial for each increment of Y address as shown in FIG. 4. ##EQU5##

PROM 42 supplies the increment in range .DELTA.R for each increment in the Y direction along one boundary of a standard angle, as shown in FIG. 4. ##EQU6## when the Y units are the same as R units; otherwise, there are K units of R for each Y unit and then

The operation of the scan converter as shown in FIGS. 1A and 1B is now described with reference also to FIGS. 4 and FIG. 5. Digitized radar radial video data corresponding to the standard angle (.theta..sub.1) shown in FIG. 4 is stored in a high speed radial buffer memory (not shown, but known to one of ordinary skill in the art). Each address of the buffer memory represents an increment of range along the radar radial path. A mass memory or bit image display refresh memory (not shown, but known to one of ordinary skill in the art) is used to store the converted video data in cartesian coordinates (X,Y). The number of memory locations corresponds to the number of pixel locations on the CRT to be used as a raster display. An X Address 78 and Y Address 82 are generated by the scan converter identifying a mass memory location for the storage of the input radar radial data associated with that address. In addition, a Radial Address 84 is generated which identifies the specific radar return data stored in the input radar radial buffer memory to be transferred to that corresponding X,Y mass memory location. Three tables of values are stored in PROMS 14, 42 and 44 for use during the coordinate conversion procedure. Each address of the PROMS 14, 42 and 44 contains the values required for the calculation performed within each standard angle increment (.DELTA..theta.) during the conversion procedure. As noted previously, a standard angle increment is generally 0.5.degree. or less and typically there are 200 to 250 standard angles per quadrant (depending on the angle selected).

Referring now to FIGS. 1A, 1B and 4, assume that the processing for point 3 within the standard angle increment (.DELTA..theta.) has just been completed in which case the following operation occurs:

1. The X Increment Counter 26 is advanced one count by Clock 24.

2. The new output of X Adder 28 is compared with the X End Accumulator 22 in Comparator 30.

3. The X position output line 77 from the X Adder 28 now exceeds the X address corresponding to the Stop Boundary 1 in FIG. 4 causing a Y Line Advance 80 signal to occur.

4. The Y Line Advance 80 causes the value provided by Register 16 (previous .DELTA.X/.DELTA.Y) and Register 18 (current .DELTA.X/.DELTA.Y) to be added to the X Start Accumulator 20 and the X End Accumulator 22 respectively, and it resets the X Increment Counter 26. It also increments the Y Increment Counter 34 defining a new Y Address 82.

5. The Y Line Advance 80 also causes the .DELTA.R/.DELTA.Y PROM 42 output to be added to the Radial Accumulator 46. In addition, the Y Line Advance 80 signal causes the Multiplexers 50 and 52 (for the subsequent clock pulse only) to switch such that Multiplexer 50 provides the 4-Bit Multiplier 48 output to the Range Accumulator 54 and Multiplexer 52 provides the Radial Accumulator 46 output to the Range Accumulator 54.

6. The clock pulse subsequent to the Y Line Advance 80 signal event causes the Range Accumulator 54 to assume the value equal to the sum of the 4-Bit Multiplier 48 output and the Radial Accumulator 46 output. This sum is equal to the Radial Address corresponding to the pixel location designated as point 4 in FIG. 4. Illustrated in FIG. 4 is the .DELTA.R.sub.Y magnitude added to the Radial Accumulator 46 to define the range of the point of intersection of the Start Boundary 1 with the Y-axis position Y.sub.2. FIG. 5 illustrates the fractional portion (.DELTA.X.sub.b) of a complete .DELTA.X increment which must be employed to compute a corresponding .DELTA.R distance to point 4 of FIGS. 4 and 5. The .DELTA.X.sub.b distance is approximated as the ones complement of the four most significant fractional bits of the Start Boundary 1 address at Y-axis position Y.sub.2 and it is provided to the 4-Bit Multiplier 48 which also receives as its other input a .DELTA.R increment per whole .DELTA.X increment from PROM 44. The output of the 4-Bit Multiplier 48 (.DELTA.R) corresponds to the fractional portion of the .DELTA.R/.DELTA.X value necessary to adjust the value provided by the Radial Accumulator 46 to the new range distance (or Radial Address 84) for point 4 of FIG. 4.

7. At the same clock pulse for which the Range Accumulator 54 assumes the range or Radial Address 84 of point 4 in FIG. 4, the X Increment Counter 26 is advanced to 1 to define at the output of X Adder 28 the X Address 78 for point 4.

8. Since the address of point 4 is found to be less than the Stop Boundary 1 X address intersection (an integer compare only), the video data stored in the address corresponding to the Radial Address 84 provided by Range Accumulator 54 is selected as the data to be stored in the mass memory address corresponding to the pixel address for point 4 in FIG. 4 defined by X Address 78 and Y Address 82.

9. Point 5 or pixel 5 of FIG. 4 is now processed by advancing the X Increment Counter 26 by 1 and simultaneously adding to the Range Accumulator 54 the .DELTA.R/.DELTA.X increment value provided by PROM 44. This addition occurs via Multiplexers 50 and 52 when the output of PROM 44 is transferred through Multiplexer 50 and the previous Range Accumulator value is transferred through Multiplexer 52.

10. Assuming point 5 is found to be less than the Stop Boundary 1 address intersection, the video data stored in the radial address corresponding to the new Range Accumulator 54 output is selected as the data to be stored in the mass memory address corresponding to the pixel address for point 5 in FIG. 4 defined by a new X Address 78 and the Y address for Y.sub.2.

11. The processing of X points along Y.sub.2 continues until incrementing the X Increment Counter 26 causes the X Adder 28 to produce an X address which exceeds the integer portion of the X End Accumulator 22 which then causes a new Y Line Advance 80 signal to occur.

This concludes the description of the preferred embodiment. However, many modifications and alterations will be obvious to one of ordinary skill in the art without departing from the spirit and scope of the inventive concept; for example, the PROMs 14, 42 and 44 may be ROMs. Therefore, it is intended that the scope of this invention be limited only by the appended claims.