DE3143429A1 - IMAGE SYSTEM - Google Patents

Description

• · τ *

Int. Ref .: Case 1478 ~ έ ' October 1, 1981

Hewlett-Packard Company

ILLUSTRATION SYSTEM

In devices such as ultrasonic scanners that are used to generate images a cross section of the heart or other organ of the patient are used, the data signals represent analog information longitudinally radial lines of a sector. The reproduction of the images in the same format is not perfect because of the spaces between the radial lines. As a consequence of this, the modern one exists The approach is to scan the data along radial rays and write the scanned data into a digital display memory, what is sometimes referred to as a digital "scan converter".

A description of this approach can be found in the article "Digital Scan Converters in Diagnostic Ultra-Sound Imaging" in Proceedings IEEE, Vol. 67, No. 4, April 1979. Samples of the analog data along each radial line are obtained at points which have a uniform mutual spacing of such a dimension that the Nyquist criterion is met. Your x and y coordinates are determined from their R and Θ coordinates, and the Samples are transferred to the next display point in a display

above
memory bear. Use of this point-to-point translation rather than true image reconstruction gives rise to a number of problems. The most significant of these is the appearance of moiré patterns resulting from the fact that some display points in the display memory do not receive any information.

The moiré pattern can be eliminated by inserting processes, e.g. by inserting the translated value of a neighboring point into an empty display point. However, this creates artificial boundaries or discontinuities introduced into the image, which are very detrimental.

Another attempt to solve the moiré problem is that one or more radial lines of interpolated data between the actual radial lines are inserted before the information

Hewlett-Packard Company

Int. Ref .: Case 1478 - ■ £ ■ -

mation is set in the display points of the display memory, such as. ·. ■ has been described above. While doing so eliminates the moiré pattern, the facts cause many indicator points to have more than one Sample received and that only the last received sample is reproduced in the image, discontinuities, which often appear as artificial richness of contrast and radial distortion of the image manifest. Attempts at solving this problem included a peak value recording or averaging over the in samples written at a given display point. While this is an improvement, it doesn't fundamentally solve that Problem. In addition, the operations "read-modify-write" require a complex circuit which, with the current state of the art, does not work fast enough as it does for real-time operation would be required at the desired sector scan speed of thirty per second.

The invention is based on the object of providing an imaging system create that creates an interference-free, continuous image without misinformation.

Instead of translating data samples from points in the sector into selected points in the display memory, devices according to the invention are provided which select samples which lie at points of different radial lines and which define a sub-section. From these selected sample values, an interpolated data value is derived for each display point contained in the sub-slice, so that a faithful reconstruction of the image is produced over the entire area. Generally, but not necessarily, the selected samples are located at the intersection of two radial arcs with two radial lines such that ii the reference region has inner and outer radial and angular boundaries j. A first and a second interpolated intermediate data value I are derived at the radial position of each display point from '■: the pair of samples along each radial line or at the I angular position of each display point from the pairs of samples Ϊ along each radial arc. When these first and second data. "

Hewlett-Packard Company
Int. Ref .: Case 1478 -

intermediate values derived from the radial position of a display point they become a final interpolated 'data value at the Angular position of the scanning point derived. When the first and second intermediate data values are at the angular position of a display point are derived, they become a final interpolated one Data value derived at the radial position of the display point. the radial position of an indicator point is its radial location in relation to the radial arcs that are on its two sides, and its angular position is its angular location with respect to the radial Lines; which are on both sides. As will be explained, more than one pair of data samples can be used for derivation the first and the second interpolated intermediate data value to be used. The interpolation in one or both of the radial and the angular direction can be carried out with an arbitrarily selected interpolation function. In this example, the Interpolation selected with a straight line, but it would also be possible with a cosine function.

When the areas of an image are reconstructed in this way, the problems with moiré patterns and other noise signals mentioned above disappear easily, provided that each display point is addressed in the sector.

Since there are about 125,000 display points in one sector, it is obvious that the determination of their radial and angular positions and the mentioned interpolations not in a thirtieth! Second, during which the sector is scanned can be carried out by direct calculations based on the x and y coordinates of the display points and the R and Θ positions of the data samples.

■ An important part of this invention, therefore, is that facilities are provided by means of which these calculations can be carried out in real time.

In principle, this is achieved by dividing the sector into sections is divided, each between successive radial Lines and that scanning control signals - for the display points -

Hewlett-Packard Company
Int. Ref .: Case 1478

can be seen taking a step-by-step scan along the lines and successively display columns of display points in each slice.

The radial position of each indicator point within a sub-section is determined by recursive addition or subtraction of a known one Value for each step along a line of display points and one different stored value for each step along a column of indicator points to or from the known radius of a previously sampled one Display point. The fraction of the recursive addition is what you want radial weighting and is referred to below as RERR.

The angular position of each display point within a sub-section is determined by recursively adding a stored value for each intersection along one line of display points and another stored value for each step along a column of indicator points to a known distance (called a COUNT) of a previously sampled one Display point of one of the radial lines of a section, measured along a line of display points in which the display point is located, in such a way that the signal or the value of the COUNT is derived for each display point. Another recursive addition is given a stored value for each step along a column of indicator points to the known distance between the radial lines of a section taken along a given line of display points, such that a signal or value XHAT for each display point is derived. The COUNT signals for each display point can be divided by the XHAT signal for that point, yielding a signal or value 0ERR that represents the Represents angular position. A minimal flaw exists in relation to it to the true angular position, expressed as the ratio of arc lengths between an indicator point and the radial lines of the cut when the angle between the radial lines is small

The time saved for these calculations results from the short one Time it takes for each recursive addition as opposed to the time it would otherwise take for a forward computation of Radius and angles would be needed. For this purpose, refer to the ones described below

JI 4 J 4 L vJ

Hewlett-Packard Company
Int. Ref .: Case 1478

/ tO-

Referred to calculations of RERR and 9ERR.

If the data samples represent brightness, such as in a Ultrasound system, only five bits are needed to display the 32 different To represent brightness levels that can be reproduced on a cathode ray tube. Hence it will only be five bits needed to represent the final values of RERR, COUNT, XHAT and QERR. When performing the recursive addition, however, a greater number of bits, e.g., 12, are used to make up the amount of the accumulated error to an acceptable level.

The interpolations can be done in a very short time by multiplying can be run with read-only memories (ROMs) and ROMs are more reasonable The magnitude of both the brightness samples can be used as well as the values of RERR and OERR used in the interpolations used only have five bits.

Basics of the used recursive calculations and stored values

For ease of notation, the mean radial line is defined as zero degrees. All angles are related to this and are considered positive, ie the plus sign 45 ° radial line lies along both sides of a 90 ° sector. When referring to a section, the "outer" radial line R _{Q has} the larger _{angle labeled Q 2} and the "inner" radial line R ₁ has the smaller angle labeled Θ.

RERR

The recursive relationship changes the previous radius value by one incremental amount determined by the direction traversed between the previous point (j) and the new point (j + 1) has been. If this movement is to the left or to the right in the x-direction, then K = 0. Conversely, if the movement is in

3U3A29

Hewlett-Packard Company
Int. Ref .: Case 1478

y-direction, going up or down, is K = 0. If the movement in the x direction is directed towards the center line of the sector, then K is positive, which leads to an incremental decrease in the radius by K sin9 ₉ . The opposite is true for an outward movement

negative in x-direction K, which leads to an incremental increase of

K sin9 ₉ leads. If the movement in y-direction is away from the vertex of the sector, K is negative and if the movement in y-direction is towards the vertex, K is negative.

The error weights RERR and 9ERR required for each display point apparently require the explicit calculation of the radius R and the angle Θ, where θ is the angle between a vertical Line through the center of the sector and a line through the indicator point to the vertex of the sector cut. That means for the j-th display point

■ R. = T x, ² + y, ² (O

YYY

where x, and y. the right-angled coordinates of the j-th display point

JJ

are and χ.

θ. = arctan -i (2)

J ^y j ■

However, it can be shown that equation (1) alternatively consists of a recursive approximation resulting from a Taylor series expansion approximation given by

Rj ₊₁ = Rj - Κ _χ sin0 ₂ + K eos9 ₂ (3)

where O _{2 represents} the angle of the outer ray of two radial rays that define the sector intersection.

QERR -

It can be shown that the stored value .DELTA..phi Step the scanned paths along a column of display points ._ is added to the derivation of XHAT for each display point, tanQ ,, tan9, is, where 9 “is the angle between the ray '0 = 0 ° and the

* ι ι

Hewlett-Packard Company

Int. Ref .: Case 1478 -JT ^

-sZ-

is the outer radial line of a cut, and Q _{1 is} the angle between the ray 9 = 0 ° and the inner radial line of a cut. The following applies accordingly

XHAT,, = XHAT. + XHAT K. (4)

J 'J J-

It can also be shown that

COUNT. ₊₁ = COUNT. + Κ _χ + K tan9 ₂ (5)

where the value of tanQ ^ is stored for each cut.

The invention is illustrated in the following on the basis of exemplary embodiments Connection explained with the accompanying drawing - In the drawing demonstrate

FIG. 1 shows the basic components of a scanning system (scan converter);

Figures 1A, B and C are graphical representations of the functions of the components in Figure 1;

FIG. 2 shows the representation of radial lines and a field of in Display dots arranged in rows and columns, which in the explanation of the steps to be carried out according to the invention Interpolations are used;

FIG. 3 shows two pairs of radial lines which are used to explain the according to FIG the basic calculations used in the invention are used;

Figure 4 is a general block diagram of the subject matter of the invention containing scanning system;

Figure M (in Figure 7) the composition of Figures 5, 6, 7, 8 and 10 for a full block diagram of the preferred Embodiment of the invention;

Figures 5, 6, 7, 8 and 10 show the details of the preferred embodiment the invention;

3U3429

Hewlett-Packard Company
Int. Ref .: Case 1478

FIG. 4A shows an alternative interpolation device, which in the circuit according to FIG Figure 4 can be used; ■ ■

Figure 5A shows the form of digital information as it may be provided by a scanning system;

Figures 6A and B are truth tables for the multiplexer in Figure 6; FIG. 7A details of an address control counter in FIG. 7;

Figs. 7B, 7B, Bp and B _{3 show} the operation of a translation ROM in Fig. 7; '... ·

FIG. 8A is a truth table for the ROM in FIG. 8, which is used for calculation the radial position of an indicator point is used;

Figure 8B shows the details of a radius counter in Figure 8;

FIG. 8C shows the truth table of a ROM in FIG. 8, which is used for the calculation the angular position of a display point is used; ·

FIG. 9 graphically shows the mode of operation of the preferred exemplary embodiment of the invention;

Figures 11 and 12 are timing charts of various signals;

FIG. 13 shows an alternative embodiment of the invention which can be used to carry out the interpolation of fewer components

compels;

FIG. 14 shows a further alternative embodiment of the invention which is suitable for performing the interpolation on a single ROM needed; and

Hewlett-Packard Company
Int. Ref .: Case 1478

FIG. 15 shows a further alternative embodiment of the invention which the values of RERR and GERR as well as the interpolation can be determined with a single ROM.

The block diagram of Figure 1 shows the basic components of a digital scan converter imaging system of the type to which the invention relates. A scanner 20 sends acoustic impulses into the body of a patient by means of devices not shown in detail and generates an analog signal representing the amplitudes of echoes received from structures of the body which along a number of radial lines of one shown in Figure 1A Sector. Only a few radial lines are shown. When the analog signal is received, it becomes uniformly spaced digital samples (indicated by the dots in Figure 1A) "are derived along each radial line by an A / D converter 22 and the Scanning converter system 24 is supplied. In general, like it in one The system incorporating the invention may occur, the first data sample is at zero origin of the sector, and the other samples are located at the intersection of the radial lines of the sector with equally spaced radial arcs so that the data samples are also distributed along the arcs.

As pointed out above, the function of the scan converter system 24 is to write digital data values derived from the data samples to appropriate display points in a display memory 26 which are effectively arranged along orthogonal rows and columns, as indicated by the characters + in Figure 1B is shown. To do this ,, the scan converter system returns to., Writing data and the x and y coordinates of the display point in the display memory 26 where it is to sit. Once the data have been stored in memory 26, they can be read out from suitable x and y coordinate points by means of a reading device 28 and placed in corresponding coordinate points of a display device 30, as indicated by the + sign in FIG. 1C.

.31Λ 34 29

Hewlett-Packard Company
Int. Ref .: Case 1478

Basic principles of the invention

Figure 2 is an enlarged view of a portion of the sector shown in Figure 1A in which the data sampling points are shown as points appearing along radial lines FU to R ^ at intersections of these radial lines with radial arcs A, "to A ₁₃ , which have a uniform distance s from one another. Each data sample point is denoted by the letter S with an index equal to the radial line on which it appears and an index equal to the arc on which it appears. The data sampling points are thus distributed along the arcs. The sampling points of the display memory (26 in FIG. 1) are represented by the characters +, which are arranged in orthogonal rows and columns which are parallel to the x and y axes, respectively. To simplify the drawing, parts of the radial lines R to Rj have been omitted, but the x-axis, although not shown, goes through the origin zero, at which a display point is located. The distances between the rows of the display dots are K and the distances between the columns of the display dots are K.

To determine a final interpolated data value to be used as a.

an indication point of how DP is to be used, a signal RERR ¹ representing the radial distance between DP and the arc A ₁₁ and a signal 9ERR ¹ representing the angular displacement between DP and the radial line R ₃ are derived. Accordingly, RERR ¹ and 9ERR "represent the radial or angular position of the display point DP relative to A ₁₁ and R _3. A first interpolated intermediate data value Ί can be linearized with the radial position of DP along the radius R

11 12

Interpolation between the data samples at S. and _{derive S 3} according to the following expression, in which a * denotes the value of a data sample:

11 * 1? *

S '' (s-RERR ¹ ) + S, RERR ¹

I ₁ = - ^ _i ³ - (6)

• ·

Hewlett-Packard Company
Int. Ref .: Case 1478

In a similar way, a second interpolated data between

31 ti

12th

Derive value I ₀ at the radial position of DP along the radius R.

11 by linear interpolation of the data samples for S and .S » according to the following expression:

S " ¹¹ * (S-RERR ¹ ) + S. ¹² * RERR '

(7)

The final interpolated data value FDP for DP can be derived from its angular position by linear interpolation of the first and the second interpolated intermediate data value I or I ₂ according to the expression:

I ₁ (AQ-QERR ¹ ) + I ₉ -QERR ¹

_{1 9}
FDP = -! _a _ £ _ (8)

instead of calculating QERR ¹ , a value COUNT, which is the distance between DP and R ₃ measured along the line of display points through DP, and a value XHAT, which is the distance between R ^ and R, measured along the same line of display points, are determined is. It can be shown that COUNT is proportional to XHAT when 9ERR ^{1 is} proportional to Q. The final interpolated data value at the display point DP can be determined by the following expression, in which XHAT replaces the quantity Q in equation (8) and COUNT replaces the QERR ¹ :

I ₁ (XHAT-COUNT) + I ₉ -COUNT 'FDP = -! £ (9)

XHAT

The final interpolated data value for the display point DP could just as easily be derived if the order of the interpolation were reversed, i.e. a first interpolated _{intermediate data value I 1} 'could be derived at the angular position DP along the arc A ₁₁ using the formula:

S- ¹ ^ (XHAT-COUNT) + S, ¹¹ * · COUNT ¹ XHAT

ο ι * »■ * ■ ψ W '*

Hewlett-Packard Company
Int. Ref .: Case 1478

and a second interpolated intermediate data value I ₂ 'could be obtained at the angular position of DP along arc A » _2. using the formula:

Ip * 1O *

S, (XHAT-COUNT) + S ^ -COUNT

Ιο ¹ = - (11)

^c XHAT

The final interpolated value FDP is then given by the following expression given:

V (S-RERR ¹ ) - + I '(RERR ¹ ) FDP = -4. . (1Γ)

As will be apparent, these equations can be calculated more easily when the radial position is represented by a signal RERR = RERR '/ s and the angular position is represented by a signal 9ERR = COUNT / XHAT. RERR is the fractional position of DP between A ... and A ^ ₉ and QERR is the fractional position of DP between the radius lines R ₃ and R ₄ . For example, equation (6) becomes:

I ₁ = S ₃ ¹¹ * (1-RERR) + S ₃ ¹² * .RERR (6 ¹ )

and equation (1) becomes

FDP = I ₁ (I-GERR) + I ₂ -GERR (9 ¹ )

With both calculation methods it should be noted that the first interpolated intermediate data value is derived by interpolating data samples along one of the radial or angular directions which lie on one side of DP in the other direction and that the second interpolated Intermediate data value is derived by interpolation of data samples which lie on the other side of DP in the same radial or angular direction. In the first method, the first interpolated intermediate data _{value I 1 was} obtained by finding an interpolated value

11 * 12 *
derived from S ₃ and S ₃ , which on the left of

Hewlett-Packard Company

Int. Ref .: Case 1478 -YyD-

DP lie in an angular direction, and the second interpolated intermediate data value I ₉ was derived by interpolating from

11 * 12 *
S, and S, j which are on the right side of DP in an angular direction. If the angle between Ro and R is small, I 1, I ₂ and DP lie on a substantially straight line because there is little difference between the tendon and the arch. Similarly, with the second method, I _{1 became} ¹

11 * 11 * "derived by interpolating S, and S- _{running along arc A 11} and on one side of DP in a radial direction

12 * K) direction, and I ₉ - ¹ was derived by interpolating S '

12 *
and S ₄ , which lie along the arc A ₁₂ and on the other side of DP in the radial direction.

While the above description illustrates one way in which a sample converter system in accordance with the invention can operate, other possibilities are readily conceivable, e.g. deriving I, by interpolating four data samples along R-, and deriving I ₂ through Interpolation of four data samples along R », or, in the second method, by interpolation of four data samples along the arc A ,. to derive I, 'and by interpolating four data samples along arc A ₁₂ to derive Ip ¹ . Another method is to derive additional interpolated values I, ρ and I, ~ in the same way as I ₁ and 'I ₂ and interpolate all of these in angular directions to obtain the final interpolated value of DP. Similarly, interpolated values L, ^{1 could be derived} from the data samples along A ₁₀ and I _2R 'from the data samples along A ₁₃ and these could in turn be interpolated in the radial direction, thereby obtaining the final interpolated data value at DP. Another method is to use data

use samples at four sample points that are further away from DP, eg S ₂ ¹⁰ , S ₅ ¹⁰ ; S ₂ ¹³ and S ₅ ¹³ , which define an area containing DP.

Hewlett-Packard Company
Int. Ref .: Case 1478

For the interpolation described, an approximation was made using a Just described, however, any non-linear interpolation method can also be used to. an interpolated value to get the radial or angular position of DP. The type of interpolation only changes the weighting factor, which must be given to the data samples.

Basis of calculation

As stated above, it would take far too much time to calculate all of the foregoing interpolated readings in a sector by direct methods to allow real-time operation with instruments such as ultrasonic scanning systems that cover a sector in a thirtieth! Sample second. Reference is made to FIG. 3 for an explanation of the fundamentals on which the calculations according to the invention are based. Two radius lines from a scanner, an outer line R _n and an inner line Rr defining a section, are shown forming angles θ and, respectively, with a column of display points along the y-axis, which is the center line of the sector. In order to be able to illustrate the concepts involved, the angle Q ₂ - Θ between the lines Rq and Rj has been shown greatly exaggerated (about 10 ° instead of the 3/4 ° or 1 1/2 ° generally used).

Calculation of RERR

The basis of the calculation of RERR can be understood if one starts at a display point DP, in FIG. 3, which _{lies on the outer radius line R n} , and observes what happens when. a step is made along the x-axis in the direction of the origin zero to an adjacent display point DP ₂ which is at a distance Κ _χ from the display point DP. lies. If a perpendicular is drawn from R _n through DP ₂ , the acute angle is the one so formed

30. Right triangle θ ₂ and the Q ₂ opposite side of this triangle is K sin0 _2> subtract this amount from the radius of the

Hewlett-Packard Company * "

Int. Ref .: Case 1478 - MT-

DP

Display point DP. leads, regardless of what it is, in our calculation to the smaller radius of the display point QP; ,, which is indicated by the radius length R ₂ . That this is not entirely correct arises from the fact that the actual radial distance from. DP “is the hypotenuse of the right triangle, of which R _{2 is} one side and therefore slightly smaller than the actual radius. If the step from DPp to DP. would go away, ie away from the origin zero, would the magnitude K sin9 ₂ become that for DP _? calculated radius added. A step in the + y-direction of the length K according to ₃ adds a length of according to the calculation method

K COsQ ₂ , but this also proves to be somewhat imprecise, since the radius R ₃ of DP _{3 is} smaller than the real radius. However, it is a fact that these errors are negligibly small when θρ-θ. as usual, be 1 1/2 ° or 3/4 °.

Although the formulas and the device designed according to them make the angle θ _? the outer radius line use each cut in the implementation of the radius calculation, one could also have a different ". angle" close to "Q ₂ select the ₂ of Q" deviates by less alsAQ. Such a selection ensures that the errors are within

^ O acceptable tolerances are maintained.

The radius at origin 0 is zero. Therefore, when the above-mentioned scanning signals of the display point cause a step-by-step scanning of the scanning points of the section Rq, Rj, starting from the origin 0 as shown by the broken line 31, and when the value of K sin9 ₉ for each Step to the right is subtracted and added for each step to the left, and if K cos9 _{2 is added} for each step along the y-axis away from the origin, the radius of each display point in the scan path can be determined with sufficient accuracy according to the quantitative errors for a display point which lies within the section bounded by Rq and Ry.

3U3429

Hewlett-Packard Company
Int. Ref .: Case 1478

-2λ -

While the value of the radius of a display point in a still to descriptive way can be used to prevent writing of data in the display memory, its more important is Function to determine RERR so that the interpolations along the radial direction described above can be carried out became.

In a format where I K [= | K J = Js | = 1, RERR is only the fraction of the number that represents the radius. However, if K is different from K and s, normalization methods can be used Generate Radius Values "measured in units of s such that the fraction is still RERR. This results in - '

R, ₊₁ = R, - Κ _χ sin9 ₂ + K cos9 ₂ (12) "

Calculation of XHAT

XHAT was defined above as the distance between radius lines of a section, for example R _Q and Ry in Figure 3, measured along a line of display points or along the x-axis. When a normal 32 is drawn from the y-axis to the position of a display point 34, the value of XHAT for display points on the same line can be derived as follows. If the number of increments 2Q of K between the origin 0 and the display point 34 is η, the result is 3 accordingly

χ = nK tan9 ₂ (13)

and

x ¹ = nK tan9., (14)

and · ■ '

XHAT = χ - x ¹ = nK tan9 ₂ - nK tan0 ₁ (15)

If you look at. These equations show that the value

Hewlett-Packard Company

Int. Ref .: Case 1478 -A = h-

of XHAT increases with each change of K along the y-axis by a constant amount Δ XHAT, so that the following applies:

nK tan0 ₉ - nK tanO,
ΔXHAT = - £ ^ ₁₇ i = K tan9 ₀ - tanO, (16)

Calculation of COUNT

As used in the system to be described, COUNT is the distance from the outer radius line, for example R _Q, to a display point, measured along a line of display points which contains the display point for which the value of COUNT is sought. Since DP. is on the outer line R _Q in Figure 3, its COUNT value is zero. The value of COUNT for DP ₉ is K. Accordingly, each step along increases a row of display points in the direction to the center! Iinie the sector _χ the value of COUNT by Κ (see DP ₄ and DP ₄₁ in Figure 3), and each step of the center line away decrements the value of COUNT by K. However, if the step is along a row of display dots or along the y-axis in a direction away from origin 0, for example a step from DP. after DP ₃ , the value of COUNT is increased by K tan9 ₂ .

The value of COUNT for the display point at the origin is assumed to be? {) Zero. Hence, the words of + K-, -K and

Λ Λ

K tanQp is selected as mentioned above, the value of COUNT obtain. It should be noted that we are within the sector cut whenever at each point of reference OoCOUNT ^ XHAT applies.

Dividing COUNT by XHAT, a fractional dimension OERR of the angular position of a display point between the radius lines R ₀ and R _{1 of} a section is obtained. Since RERR is a fraction of the radial distance of a display point between two data sampling points, 9ERR and RERR can be used in the same way in angle and radius interpolations.

3U3A29

Hewlett-Packard Company
Int. Ref .: Case 1478

When determining the value of COUNT for cuts in the right half of the sector, COUNT is still measured to on the outer line, but as can be seen in Figure 3, the outer line R _Q 'is to the right of R ₁ ' instead of to the left of which as 5 · in the case of R _Q and Rj. If COUNT is still _{measured from the outer radius line R n} ', the same calculation applies.

This does not mean, however, that the fractional angular position of a display _{point has to be measured from the outer line R Q} or "R, /. It could, for example, always be measured in relation to the left radius line, which is in the left half of the sector R _Q and in the right half R is _1. The calculations would be the same as just described for the left half, but in the right half + K and -K _v

X X

swap and instead of + tan9 ~ you would have to use -tanO ^. As will be explained, the latter could be put into a ROM. · ■

Although. The final interpolated data values of the display points near the origin are generally unimportant, it is essential, the values of RERR and QERR for this Earning points as these values are needed in the recursive addition to derive the fourth of RERR and 9ERR the final interpolated data values for display points calculate which are of interest.

General system ■ ·

The block diagram according to FIG. 4 generally shows a scanning converter system, containing the various aspects of the invention. Its function is to make the final on a real-time basis to calculate interpolated data value for each of the approximately 125,000 display points of a display memory that are within

Hewlett-Packard Company
Int. Ref .: Case 1478

-ZH -

of a 90 ° sector, as shown in Figure 1A and which scanned about thirty times per second by a Radi al (20 in Figure 1) is scanned. This is accomplished by determining the final interpolated data values for each display point of a cut, i.e. the sampling points on or between a pair of radius lines and by repeating the operation for each subsequent cut.

As shown in FIG. 4, a radial scanner 33 supplies analog data obtained along each successive radius line to an A / D converter 35, which digitizes the sample values of the data occurring at uniformly spaced points along the radius lines, e.g. the sample values S, g, S, -, S. ", S, - on the radius line R ₀ and the samples S ,,, ¹ , S, ', S,' and S ₁₃ ¹ on the radius line Rj in FIG used every cut

Data are different is a line identifier provided, which derives an identification of the line just scanned from the signal of the scanner 33. This can be reduced to an ■ cause a number of species, e.g. by assigning a digital number to each line or by identifying a given line in '20 a sector and count the lines as they are scanned. The line identification signal so derived is used by write controller 38 to read the digital data samples from the A / D converter 35 to storage locations in a memory 40 to be directed such that their radial positions are along the lines

are identifiable. ·

The following description relates to a device for Deriving the signals RERR and 9ERR, which the radial and angular position of a display point and used in the interpolation process. The following description also relates to means for obtaining data samples from memory 40 defining an area which is the sampling point contains.

Hewlett-Packard Company
Int. Az: Case 1478.

A device 42 derives from the signal from the radi al scanner 33 a signal STRTL, which indicates the point in time at which the scanner begins to scan along a radius line. On each Signal STRTL out generates a facility. DPSG display point scanning control signals, which represent the sequence of steps in one of the directions • + χ, -x, + y or -y, which from a given display- point must be made, e.g. one at the origin of the radius lines, when scanned over the display points of the section, the Line identified by the signal provided by the line identification device 36./

Although the sequence of steps is usually those in + x-, -x-, and + y-direction, as indicated by the dashed line 31 indicated in Figure 3. If the scanning path for the display points is shown, it would also be possible for steps to be taken in the -y direction became. A device 46 outputs a signal indicating that a Step is taken along the x-axis; a device 48 generates a signal indicating whether the step was taken in the + x or -x direction shall be; a device 50 emits a signal indicating, that a step is taken along the y-axis; and a device 52 outputs a signal indicating whether the step in + y- or -y-direction should go. The output signals of the facilities 46 and 48 are fed to an x-address counter 54, and the x-coordinate of the display point for the final interpolated The data value to be calculated in a manner yet to be explained is in relation to the x-coordinate of the original display point identified. The output signals of the devices 50 and 52 are fed to a y-address counter 26, and the y-coordinate the same display point is in relation to the y-coordinate of the original. Identified display point. The output signals the x and y address counters 54 and 56, respectively, are placed on address lines of a display memory DM so that the final one interpolated Data value FDP for this point after its determination in

J I 4 J '+ ζ

Hewlett-Packard Company

Int. Ref .: Case 1478 - Vr-

the correct space is given. Calculation of the radii

The determination of the radius of each display point identified by the display point scanning signal is identified by the generator DPSG, can be done as follows. The signal from device 36 that identifies the line along which the radial position in cooperation with the indicator point scan control signal from the generator DPSG is to be determined, selects from a memory 58, which can be a ROM but does not have to be, the appropriate one of the values + K sin9,

-K sin9, - + K cosQ or -K cos9, as in connection with Figure 3 has been explained, for the supply to the input of an adder 60. The angle θ is the angle of a radius line which is sufficiently narrow lies at the center line of the cut. How close she lies there is given by the error that can be tolerated in the angular position is. The output signal of the adder 60 is fed to a buffer memory 62 which is always in operation when a step is taken along the x- or the y-axis, regardless in its direction. For this purpose, its clock input is connected to the output of an OR gate 64, the inputs of which with the Outputs of the x counter 46 and the y counter 50 are connected.

The output of the buffer 62 is "with a further input of the adder 60 connected. Together, the adder 60 and the buffer store 62 form an accumulator which is at the output of the buffer store 62 generates a signal that determines the radius of the display point by adding all the values of + K sin9, -K sin9, + K cos9 or

λ λ y

-K represents cos9 referring to all previous steps in + x-, -x-, + y- and -y-direction were generated along the scanning path, which is predetermined by the scanning control generator DPSG.

Selection of display points

At this point it should be noted that while a final. interpolated data value for each display point in the

Hewlett-Packard Company
Int.Az .: Case 1478

Signals from the DPSG determined scanning path can be derived, the time required to carry out this calculation for display points outside of the cut (hereinafter referred to as overhang) should be minimized using the following rules.

1. Is at the sector vertex where all scans begin to be incremented outside the outline in the x-direction.

2. Outside the outer curve and directed outwards, vertically bend and return in cross direction in x-direction (change XDIR);

3..If you are in the direction outside of a cut moved and there are no further points within the section further outside on the grid currently being crossed and there are no further points on the following line to be crossed, bend vertically and reverse direction (Change XDIR). However, if there is another point within the cut on the following line, cross continue on the current line for one more point and then follow rule 2 ..

4. Continue moving towards the center of the sector, until the inside of the cut or inner line is reached, then bend vertically and reverse direction (change XDIR) to Addressing of the last display point within the current crossing, which is within the cut. ·

For points outside the section, the final interpolated Data value for this point is not in the display memory DM must be entered as it may very well be incorrect and can be read by a display memory scanner 66 and the Display device 68 can be supplied '. It would correspond to the spirit of the invention to use the means for calculating the lock final interpolated data values for display points,

J 14 OkLV

Hewlett-Packard Company

Int. Ref .: Case 1478 -JH- -

which lie outside of the cut, instead of calculating the values and preventing the incorrect data from being stored in the display memory DM would be saved, saving no time. These considerations apply to all calculations.

'Using the radius R

. As described above, the value of the Radi us.R of the DPSG appears

designated display point at the output of the buffer store 62. . Bits corresponding to R are fed to a comparator 70, where they be compared with the value of the maximum radius R, which the

Max

1Ö defines the outer radial limit of the sector. If this comparison shows that the radius R of a display point is smaller than R,

Πι ο. Χ

the comparator 70 delivers a signal ROK to an input of an AND element 72, the output signal of which is an enable input of the Display memory DM is supplied. In a manner to be described, a. Signal THETOK derived, which indicates that the display point is in the current cut, and this signal is fed to the other input of the AND gate 72. It ■ So both signals ROK and THETOK must be affirmative ", if the data value is to be written into the memory DM. The ROK signal is not as important as THETOK, since it is incorrect interpolated data values at some display points at the end of a cut do not pose as big a problem as an incorrect data value inside the cut. The main advantage "of ROK consists in smoothing the outer periphery of the sector.

Calculation of RERR

The value of R cannot be used directly for interpolation,. since equation (6) ze.igt that a signal must be derived which represents the relative radial position of the display point with respect to Datenabtastpunkte ₅ which are 'used polation in the Inter-30, the relative radial position of the display point DP ie in Figure 2 with respect to the data sample points

11 12
So and S_, if the interpolated intermediate values I. and I "

Hewlett-Packard Company

Int. A7 .: Case 1478 '- 24- -

be calculated. It would be possible to derive a signal indicating the

12 represents the radial distance between the outer data sampling point S ₃ and DP and to use this for interpolation according to the invention, or ^{to derive a signal RERR 1} , which the radial derivative

11 stood between DP and the inner data sampling point S ^.

In the preferred exemplary embodiment of the invention, how further will have to be described below, K = K = s, so that the fraction of the values RERR appearing at the output of the buffer store 62 i.e. the ratio of the distance between the display point and the inner arc to the distance s between adjacent ones Sheets. In the general case, however, K- and K can be different from each other "and from s. In this case it is easier if K and K are both smaller than s because of a change in K or

X y. ' . X

K, which occurs when going from one display point to the next, could change the calculated radius by an amount greater than s, so that it would be necessary to take this fact into account ^{when calculating RERR 1.}

In the general case, as shown in Figure 4, K, K and s all have different values. The signal R at output χ

of the latch 62 is applied to one input of a differential calculator 74, and the output of a latch 76 is applied to the other. At the starting point of each radius line, all buffers are cleared by applying the STRTL signal to their clear inputs so that the initial output of buffer 76 is zero. A difference signal RERR ^1, which is equal to the value of R minus the output signal of the buffer memory 76, appears at an output 78 of the difference calculator 74, and a signal RDIR, which indicates whether R rises or falls, appears at another output 80. The difference signal RERR ¹ is applied to one input of a comparator 81, and a value corresponding to s is applied to the other input. When RERR ¹ τ s, the comparator 81 outputs a signal CROSSs. If RERR ¹ ^ 0, the comparator 81 also outputs the signal CROSSs, which indicates that the value of RERR ^{1 is represented} by an integer multiple of s.

Hewlett-Packard Company

Int. Ref .: Case 1478 - 75 -

increasing or decreasing direction. For example, a signal CROSSs becomes either when the display point DP (Figure Z) is scanned to the display point DP ^, both of which are between the radius lines R _? and R ₃ , or when scanning in the opposite direction from DPo to DP. generated.

The input of the buffer 76 is connected to the output of an addition-Z-subtraction circuit 83, one input of which is connected to the output of the buffer memory 76, the other input of which receives the value of s and the control input of which 'receives the signal RDIR. Whenever RDIR indicates that R is increasing, generates the addition / subtraction circuit 83 at its output and at the input of the buffer memory 76 the sum of the output signal of the buffer memory 76 and s. Whenever RDIR indicates, ■ that R falls, the addition / subtraction circuit 83 generates its output and at the input of the buffer store 76 the difference between the output signal of the buffer store 76 and s The clock input of the buffer memory 76 receives the signal CROSSs, so that when CROSSs occur, the input signal of the buffer memory is transmitted to its output and to an input of the difference computer 74.

The signal RERR, which the fractional distance of a display point such as DP in Figure 2 between A ,. and A represents ₁₂ is derived ^{by dividing RERR 1} by s by means of a divider circuit 77. However, if S = K = Κ _χ9 then RERR is simply the fraction of R at the output of the buffer 62, in which case the buffer 76, the addition / subtraction circuit 83, the difference calculator 74, the comparator 81 and the dividing circuit 84 are not required .

Calculation of XHAT

The value of XHAT is the distance between radius lines, measured along a line of display dots which contains the one in question, as shown in FIG. 2, or as can be seen even more clearly

Hewlett-Packard Company
Int. Ref .: Case 1478

. -ac- '

from Figure 3 for the display points DP, and DP ₄₁ results. XHAT is equal to the sum of + AXHAT, where Δ.ΧΗΑΤ is equal to tan9 ₂ -tan9 for each step in the y-direction away from the origin, and -ΔΧΗΑΤ for each step in the y-direction towards the origin. Since the value of XHAT varies for each cut, it is only necessary to supply the line identification signal from the circuit 36 to a ROM 88 and thus to select the value νοηΔΧΗΑΤ for this line.

The output of the ROM 88 is fed to an accumulator which consists of an adder 19 and a buffer memory 92. This 1Q accumulator works in a similar way to adder 60 with \ the buffer memory 62, which are used in the calculation of the radius. However, instead of being updated with every movement in the x and y directions the buffer memory 92 is only updated for movements in the y direction.

Calculation of COUNT

The signal COUNT can be a distance measured along a line ' of display points between a display point in this line and another radius line of the section. The line identification signal from circuit 36, the display point scan control signal from DPSG and the y-up-down signal from circuit 52.

which is fed to a ROM 96 so that one of the values + K ₅ -K, + K / tan9. or -K tan9 is selected and fed to the input of an adder 98. The line identification signal selects a term having a tan9 "corresponding to the angle Q ^ used for the cut and the signal from the y-up-down circuit 52 in conjunction with the display point scan control signal from DPSG selects the appropriate one Value of + K tan9 and -K tanQ. The value of + K or -K

• y y XX

is selected by the steps along the x-direction made by the scan control signal. The following tables show the input selection matrix for the ROM 96 under the specified conditions. Remember that + x took a step to the right with increasing value of χ, -x one step to the left along the

Hewlett-Packard Company Int. Ref .: Case .1478

is the x-axis, -y is a step towards the origin, and + y is a step away from the origin in the direction of the y-axis.

COUNT measured by the outer L line in both quadrants right quadrant
selected LN # • left quadrant
selected K> 0
χ K _x - o K-- 0
X
K tan & ₂ 7 0 —— K tan9 ₂ > 0 K _y tan9 ₂ -c0 K _y tan9 ^ 0 ■ χ YOU y YOU -x - + X + y -y

COUNT measured from the left line in both quadrants

LN # χ YOU y YOU left quadrant
selected right quadrant
selected I I I I
I I I I
I I I I -X
+ X + y
-y .Kf 0
K _y tan9 ₂ > 0
K _y tan9 ₂ - 0 Κ _χ ^ 0
K tan9 ₂ > 0
K _y tan9 ₂ ^ 0

COUNT measured from the right χ YOU y YOU _line in both quadrants right quadrant
.selected LN # -x
+ X + y
-y left quadrant
selected K _x ? O
V °
K tan9 ₂ y 0
K tan9 ₂ <0 - K _x > 0
K _x ^ o
K tan9 ₂ > 0
K tan9 ₂ ^ 0 '

25 ·

The output of the ROM 36 is fed to an adder 98, the Output is connected to a buffer 100, which is clocked by a step in the y or x direction by its clock input connected to the output of the OR gate 64 via a line 102 is. The output of the buffer 100 is connected to an input

3.U3429: 'V>. * <

Hewlett-Packard Company

Int. Ref .: Case 1478 - 2 & - ■

- 33 - "■

output of the adder 98, so that an accumulator is formed which generates a signal COUNT at its output, which is equal to the sum of all changes in the value of COUNT resulting from all previous steps from a display point to another, including negative values.

Determination of QERR

Although the values of XHAT and COUNT could be used directly by interpolation circuits by simply making the angular distances used in the interpolation formula COUNT and XHAT-COUNT (see equations (9), (10), (11) and (H ¹ )) It is generally easier to derive a signal QERR which represents the fraction of the distance of a display point from one line to the other, the particular signal used being based on the selection made above where COUNT is divided in a division circuit 104 by XHAT. Equation (9) becomes Equation (9 ') using OERR.

Is the display point between the radius lines of a section?

To determine whether a given indicator point is between the radius lines of a cut, the following means are used intended. The most significant bit of COUNT at the output of the buffer 100 is fed to an input of an AND element 108 via an inverter 106. As is known, this bit goes to "1", when the digital signal of COUNT goes negative so that the output of inverter 106 goes low. Additionally the values of XHAT and COUNT are fed to a decision circuit which outputs a high level signal when COUNT is less than XHAT and outputs a signal with a low level, if COUNT is greater than XHAT. So if COUNT is negative or greater than XHAT, a situation that only occurs when the Display point is angularly outside the cut, does the output signal THETOK? from AND gate 108 to a low one

3T43429

Hewlett-Packard Company

Int. Ref .: Case 1478

Level. THETOK? is fed to an input of the AND gate 72, whose other input, as remembered, ROK? is fed. If only THETOK? on is high, what indicates that the indicator point is angularly within the section and that ROK? is also at a high level, which indicates that the radius of the display point is smaller than R ^ w the AND gate 72 outputs a signal of a high level so that the display memory DM "is caused to output a final one supplied to it to save the interpolated data value at the displayed x-y address.

interpolation

A read controller 82 receives a plurality of data samples of a plurality of radius lines from memory 40 under control " of RDIR and CROSSs and does these at the same time at the entrances

15th of interpolators 112 and 114 available. Two of the data points are located where an arc with a smaller radius than the display point intersects the radius line of a section, and two of the data points are located where the arc with larger radius lines intersects a section. When the display point scan control. signal caused by DPSG "that the sample intersects the outer or inner curved, informs the signal crosss ^- the read controller 82 that a crossing has occurred, and the signal RDIR determines whether the intersection radially outwardly or inwardly directed ' The read control 82 then selects the appropriate data points so that the four data samples always define an area containing the display point The newly selected data points can be the same as before, further out or further in on the vertex of the sector to, depending on RDIR and the value of s. If, for example, the initial four

on 11 * 12 * 11 * 12 *

Data samples S ₃ ¹¹ , S ₃ , S ₄ ¹¹ and S ₄ ¹ (Figure 2) are and

• the sampling runs from a display point within the area defined by these points to a point outside the arc A ^, if the read control 82 neglects the inner data ^{samples So 11} * and S-, keeps the samples sJ ² *. And sJ ² *

■ 13 * 13 * ο. <\

and adds samples S 'and S ₄ . If the scan path

Hewlett-Packard Company

Int. Ref .: Case 1478 - "3U-

»A

again the line A _1? crosses, the original four samples are used. The interpolated intermediate values supplied by the interpolators 112 and 114 are supplied to an interpolator 116. If switches s _{1 and S 2 are} in the position shown, interpolators 112 and 114 interpolate radially, interpolator interpolates angularly, and Sg outputs data samples on R ₃ to interpolator 112 and data samples on R ₄ to interpolator 114. Condition. If S ₁ and s "are in the respective other position, the order of the interpolation is reversed, and s- supplies inner data samples to the interpolator 112 and outer data samples arr to the interpolator 114. If interpolations are to be carried out which contain different or additional display points, For example, as described in connection with Figure 2, it will be apparent that more interpolators than those labeled 112 and 114 are needed and that read controller 82 must obtain the data samples from memory 40 and make appropriate ones available to the interpolators at the same time. Since a person skilled in the art can easily make the required selection of data samples and interpolator devices, only one other combination is shown (FIG. 4A). In the arrangement according to FIG. 4A, the first and the second interpolated intermediate data value are obtained from the data samples at four sampling points along the radii R ^ and R; (Figure 2) derived. Data samples

10 * 13 * · ■

S,, S-I are fed to an interpolator 118, data sampling

fi * 12 * in *

values S ₃ , S _{3 to} an interpolator 120, data samples S.,

S _{4 to} an interpolator 122 and data samples S ₄ ¹¹ *, S _{4 to} an interpolator 124. The signal RERR is fed to all of these interpolators. The outputs of the interpolators 118 and 120 are connected to an adder 126 which generates a first interpolated intermediate data value I, and the outputs of the interpolators 122 and 124 are connected to an adder 128 which outputs a second interpolated intermediate data value. The interpolators 12 and 122 can take into account the various spacing of the inner and outer data samples of DP, as well as various weighting factors to be applied to them, if necessary.

3U3-429

ψ * m m

Hewlett-Packard Company

Int. Ref .: Case 1478 - "61--

Preferred Embodiments, Sampler Bus Bar (Bus) Signal

In view of the fact that the various trigonometric used in performing the interpolations according to the invention Functions require information such as angles related to the radius lines, along which radius lines a scanner can read the data produced, it is essential to have identification facilities of the scanned line are provided. Various possibilities Consider, for example, generating a pulse on the first line of a sector and providing a count that updates each time is when the scanner emits an acoustic pulse into the body . of a patient. However, in order to create the possibility To format the sector under software control, each angle becomes unique immediately prior to receiving data for that angle labeled with a seven-bit word. The data is in

1Π five bits quantized. To the number of certain signal busbars between a sampler and the sampling transducer according to the invention, share the angle and data bits A common data transfer bus 133 (Figure 5) which is 12 bits wide. The output signal of a sampler 13.4 (Figure 5) is shown in Figure 5A, where it can be seen that when MSB is 1, bits 2 through 8 represent the line number, and when s is 0, bits 2 through 6 represent one of 32 levels for a data sample. To reduce the trigonometric data, which have to be stored in the ROMs, one takes advantage of the. Angular symmetry around the center radius line of the sector and accordingly bit number 1 has the arbitrary value 1 if the line is in the left half of the sector and the value 0 if it is in the right half. At the central irvie of the sector, the bit is set to 1. The LSB, in the present. Case bit number 11 contains pulses labeled "STROBE" and occur during the time when the word contains line identification information and during the time when the word contains the value of a data sample.

3U3429

Hewlett-Packard Company
Int. Ref .: Case 1478

Timer signals

The scan converter system is triggered by pulses CLK generated by a clock 136. But to have enough time ' to provide the function of each circuit, the frequency of the output signal of the clock 136 halved by means of a divider. 138 to derive the ENABL signal. The complement of this signal, NENBL, is thereby made that generates an inverter 140 at the output of the divider. 138 an-. is closed.

Since the clock of the sampler 134 is not necessarily synchronous with the The clock generator 136 of the sampling converter has to run, LSB, STROBE are fed from the sampler 134 to a synchronizer 135. The synchronizer 135 can be constructed in various ways, but in the present example consists of a pair of D flip-flops 132, 139 and an AND gate 141, which are connected to one another as shown. To the sequence of operations of various parts of the scan converter circuit When a word is received from the scanner 134, the output signal of the AND gate 141 (with INENABLE denoted) a synchronized STROBE and is fed to a shift register 142, which is clocked by the pulses CLK. When the frequency of the clock 136 is 12.4 MHz, the signal STROBE is designed to be an active high level for at least 80 ns and an active low level for at least 80 ns so that the successive pulses NINENO, NINEN1 and NINEN2 at the output of the register are synchronous with CLK. Each pulse is 80 ns long at a low level, with the three . Impulse does not last longer than 240 ns. The inverted forms INENO, INEN1 and INEN2 are converted by inverters 144, 146, respectively and 148 derived. As can be seen, NINENO or INENO ■ are used for the release of intermediate storage, NINEN1 or INEN1 for the Control of the write functions and NINEN2 or INEN2 used to control counters.

# f

Hewlett-Packard Company
Int. Ref .: Case 1478

Identification of the line number

The output signal INENABLE from AND gate 141 is "an inverter 150 fed to the release input of a buffer memory 152, so that the word pending at the output of the scanner at this time is cached. Bit number 1, SIGN, which designates the half-sector in which the line is located, as well as bits 2 to 8, which designate the line number, are fed to a buffer 154 so that when the buffer 154 is released, the the bits representing the line number L # appear at one output and the SIGN bits at the other.

Since bits 2 through -6 represent line identification information at certain times and the value of a data sample at other times, it is essential that latch 154 is only enabled when these bits represent the line number. This is achieved by ANDing in a NAND element 158, the MSB ₄ denoted here by HDR1, with the ENABLE signal and the output of an OR element 156 to which INEN1 and INEN2 are fed. The reason for using INEN1 and INEN2 in this way is that INEN1 can occur in one of two stable states with respect to the ENABL signal. ENABLE has a period of 160 ns, while INENO-has a width of 80 ns. In order to ensure that the line number is buffered synchronously with the ENABLE signal, both INENO and INEN1 are required. It should also be noted that the STRTL signal is generated in a similar manner. This . Signal is explained in more detail below. The reason for using ENABLE is to manage the overall timing for the hardware working intervals. By essentially dividing the 12.4 MHz clock rate by 2, a working interval time of 160 ns is specified. Each synchronous operation therefore has 160 ns available within which it must be completed with execution, transmission delay and hold time. The NAND gate 158 can only generate the signal with a low level required to enable the buffer store 124 if HDR1 is the most significant

Hewlett-Packard Company
Int. Az .; Case 1478

Bit that is 1. The pending at the input of a buffer 154 Data represents the scan line information ''. .

Elaboration of the data

Bits 2 to 6 are fed to the input of a buffer 160, which is released by NINENO, so that it can be sent as data to a data collector 162 whether they represent line information or the value of the data samples. ' When these bits line information represent, they are prevented in a way from being written into the line memory according to FIG is to be explained ·. This is done by a qualification signal SWE, -which is derived in that an inverter 164 is connected between a line 166 carrying HDR1 and an input of an AND gate 168 whose other input is connected to INEN1. If the word from scanner 134 is line information, HDR1 is on a high level so that SWE must be at a low level.

However, if the word represents data, then HDR 1 is on one low so that SWE can go high when INEN1 occurs. '

Start of a line

. As previously stated, the calculations of RERR and 9ERR, which are used for the interpolation function, by successive addition or subtraction of certain stored ones Values derived from or from corresponding known initial values. Although these known initial values are the same for any Display point, it is easier to use the origin of the sector as the starting point because the known values for RERR and 9ERR at origin are 0. However, when this is done it is it. It is essential to know the data sample that will be taken at the start of a Line occurs. Since HDR1 occurs at every line start, it can be used to generate a signal STRTL (line start).

One way to do this is to use an inverter 170 between the

3U3429

Hewlett-Packard Company

Int. Ref .: Case 1478 · - * "35" -

Output of the NAND gate 158 and the input of a buffer 172 to switch. While data is being received, ■ HDR1 is at a low level, so that the output signal Latch 172 is also low. However, when an L # is received, HDR1 is on one high level, so that when NENBL releases this buffer, STRTL appears at its output as high level. In Figure 10 STRTL is used to initiate the calculations mentioned. "

Writing in the samples

To explain a method of storing the data samples reference is now made to FIGS. 5 and 6. In the circuit of Figure 6, the data bus 162 of Figure 5 is tri-state buffers or gates 174, 176 and 178 connected to the are in turn connected to the I / O digital line memories 180, 182 or 184 ■. Each line memory can store the 396 samples' store along a line, and it is desirable that samples from a radial line from scanner 134 into memory while the two previously written radial lines are read out in order to be used for interpolation to provide required samples. The tri-state buffers require a low level signal to be supplied to their enable inputs to let the data through to the 'line memories. A facility for deriving the appropriate Release signal NLD is shown in FIG. HDR1 from the line 166 is fed to an input of a NAND gate 1-86, INENO is fed to the other, and the output signal is fed to a modulo-3 counter 188, which by a signal with low level is activated and emits a signal with high level on one of its three output lines Mi, M2 or M3.

. Each HDR1 received causes NAND gate 186 to send a signal NLD outputs to the counter T88 and causes this to output the signal to move high to the next output line. After three HDR1 signals, the sequence is repeated.

Lewlett-Packard Company
; nt. Ref .: Case 1478

Enabling the line memories 180, 182, 184 so that data pending at their I / O can be written to them requires that a low level signal be applied to their write enable inputs. Such signals are derived by appropriate supply Mt, M2 and M3 to the inputs of NAND gates 190, 192 and 194 and by supplying SWE to their other inputs. Recall that SWE is high only when samples are on data bus 162 so that the outputs of NAND gates 190, 192 and 194 can go low and hence the writing of data only allow in the line memory if sampled values are pending on the data bus. This prevents line ¹ liner data from being written into memories 180, 182 and 184. The signal from ML, M2 and M3, which is in each case at a high level, has the effect that its associated NAND element emits a low output signal and thus enables the associated line memory for writing. For example, when M1 is high, line memory 180 is enabled for data reception. ■

However, since each line memory has a common I / O, it is also required that the output channel by applying a High level signal at its output enable terminal OE is disabled while this memory is receiving samples. This is achieved by connecting M1, M2 or M3 to the OE connections' the line memory 180, 182 or 184 are placed. For example, when M1 is high, the output channel is the Line memory 180 locked.

In summary, it can be said that · MI ₅ M2 and M3 successively assume a high level. When M1 is high, the three-state buffer 174 allows samples to access the I / O of the line memory 180, but the three-state buffers 176 and 178 prevent samples from accessing the I / O

3U3429

Hewlett-Packard Company
Int. Ref .: Case 1478

their corresponding line memories 182 and 1.84, respectively. At the same time, the write enable input of line memory 180 receives a Low level signal so that samples can be written into line memory 180. The exit channel of the line memory 180 is blocked, while the output channels of the line memory 182 and 184 are enabled. So if M1 is high, samples can only be stored in line memory 180. M2 and M3 are then low Level, so that previously stored in line memories 182 and 184 Samples can be read out.

The question arises as to how the samples are passed sequentially arranged addresses can be stored. This is controlled by up / down counters 196, 198 and 200. First of all, it should be noted be that the signal NLD at the output of the NAND gate 186 is fed to a load input of the counters, so that they are all at the beginning each line-be reset to zero. So that these Counters can count at all, must be at both inverting inputs ENT and ENP have a signal with a low level. For example, assume that samples are written into line memory 180 that is, M1 is high. Under this condition, the ENP input of the counter 196 is for the entire line is at a low level, since an inverter 195 sends a signal M1 + SHIFT to the input ENP to be described is fed. Ml is located during the line scan constantly at a high level, so the state of SHIFT is irrelevant. When writing, the count always increases, so that AND1 should be high. UND1, UND2 and UND3 become derived by a corresponding connection of MV, M2 and M3 each with an input of OR gates 202, 204 and 206 and of a signal NMDECR to be described with the respective other input. Since M1 is high, the output is of the OR gate 202 at a high level - regardless of the state from NMDECR, and the counter 196 counts up. The actual counting takes place in response to the NMHADDEN.hin signal, which is

■ 3U3429. ; | ". ^: - .. Ί Ί ·

Hewlett-Packard Company

Int. Ref .: Case 1478 - «38 -

ter 193 is fed to the input ENT of the counter 196. Since NM1 is the Negation of M1, is at a low level and cannot set the input ENT of the counter 196 to a low level, a count takes place every time ADDEN goes high. NM1 + ADDEN, NM2 + ADDEN and NM3 + ADDEN are as follows: derived. HDR1 is fed to an input of an AND gate 205 via an inverter 203, so that this input while samples are being received is high. Each sample is accompanied by a signal STROBE, which generates the synchronized STROBE INENABLE, which in turn is INEN2 generated. When INEN2 goes high, the output goes of the AND gate 205, which is the signal ADDEN, also goes to a high level. ADDEN is assigned to each input of the OR gates 207, 208 and 210 are supplied, and signals NM1, NM2, and NM3 become, respectively fed to the other inputs. The latter signals are derived by using M1, M2 and M3 inverters 212, 214 or 216 are supplied. When writing to the line memory 180, the entire line M1 is high and NRI at a low, and the output signal ADDEN of the AND gate 205 goes high upon each INEN2 so that the counter counts 1.96. Since, as has been described, UND1 on a high Level, it counts up. The effect of the various signals on the other line memories and counters is discussed below explained in a section on reading samples from the lines.

In the example just given, the sample values were written into the line memory 180. During the same time, samples are taken read out from the line memories 182 and 184. If the reading sequence only ever went in one direction, the "reading" function would are explained at this point, but since this is not the case, it is necessary to explain how signals INCR, DECR and SHIFT · that control the reading function.

32144-29

Hewlett-Packard Company

Int. Ref .: Case 1478 - «39--

Display point scan control signal

In order to determine the signals just mentioned, devices for Generating display dot scan control signals which allow step-by-step scanning along the rows and columns of display dots represent that are needed for advancement from a given indicator point e.g. that at the origin of the sector through the display points in a section corresponding to a given line number. As noted earlier, the display dot scan control signals as a result of different sequences, of x- and y-movements take on different forms and can through can be generated by a computer or taken from memory, as explained here. The circuit to be described according to FIG. 7 contains a state machine 220 which outputs a series of individual bits which, by means of a zero, indicate that a step along the x-axis and along a line of indicator dots, and indicating by a one that the step is away from the origin along the y-axis and along a column of indicator points. In this particular embodiment of the invention goes the step from the origin of the sector to the left in a section lying in the left half of the sector, such as through the scan path 31 is shown in Figure 3, and to the right in a section in the right half of the sector, as in Figure 3 through the scanning path 31 'is shown. The sampling algorithm uses the concept that every time the y address is changed, the direction for the x counter is changed with respect to its last setting, i.e. after the first y address change in path 31, XDIR is changed to cause the x counter to count up, i. that movement is closer to the center of the sector. It should be noted that the y-movements can be chained successively.

However, every movement in the y-direction implies a change in XDIR so that when the state machine outputs a zero (x move), the x counter moves in the direction of the last implied

3U3429

Hewlett-Packard Company

Int. Ref .: Case 1478 - 4Θ ~

x-direction moves. Also applies to cuts on both sides of the Center line (y-axis) with the same angles that the scan paths are identical with the exception that the directions are more corresponding Steps along the x-axis are opposite. The one and zero signals from the state machine 220, however, are identical. A signal XDIR indicating a step towards the center line Is zero and is one for a step towards the outside of the sector along the x-axis is controlled by means of an address counter control 222 derived from the output of the state machine 220, and the SIGN bit from the latch 230. The address counter control 222, the details of which are shown in FIG. 7A, also emits a signal YINC / XlNC that represents the steps in the x or y direction.

7 will now be discussed in detail. The bit U representing the line number and the bit representing the SIGN at the output of the buffer 154 in FIG. 5 are fed to a scanner buffer 224 which is enabled by the signal STRTL from the buffer 272 in FIG. 5 and the bits for these signals to a FIFO buffer 226, which stores two line numbers, since two successive radius lines of the scanner must be stored in two of the line memories 180, 182 and 184 (Figure 6) before a section is defined and ready for reading. Since each STRTL signal occurs on the radius line, the line number bits in the FIFO buffer 226 are moved on. At the third STRTL of the sector, the L # for the first line of the sector is shifted into a line number translation ROM 228. Its output signal is fed to a buffer store 230. _;

The purpose of the line-number translation ROMs 228 may be understood by consideration of Figures 7B and 7B ,, 7BG. ₃ In the particular format used in this embodiment of the invention, the radius lines are assigned even numbers starting with the outer line in the left half of the sector with 1/120 (Figure 7B), where 1 is the SIGN bit indicating that the Line in the

3U3429

Hewlett-Packard Company

Int.- Ref .: Case 1478 --44-

left half and 120 is the line number. The center line is arbitrarily labeled 1/0. The outermost line in the right half of the sector (not shown) is 0/120. FIG. 7B shows the outermost section in the left "half of the sector, which is spanned by radius lines 1/120 and 1/118. While sample values are read from two of the line memories 180, 182 and 184 (FIG. 6), in which the sample values of the Lines 1/120 and 1/118 were stored, samples from the dashed line 1 / 11.6 are written into the third line memory The various angle measurements used in determining RERR, COUNT and XHAT in ways to be described are based on this particular embodiment on the angle between the outer radius line R _Q and the y-axis.

The line translation R0M228 is required for the following reason.

All trigonometric functions relate to the outline i.e. in the left side of the sector the one with the "oldest" line number in the FIFO buffer 226. If the current output slice is shown as in FIG. 7B, the current output signal is from FIFO buffer 226 line 1/2, which implies that the running angle is that of line 1/2. When the center line is crossed (Figure 7B-), the output signal of the FIFO buffer 226 is 1/0. The angle of -0/2 should be used as it is the same as that of 1/2 in Figure 7B. is. To achieve this result, the line translation ROM adds 228 one in digit 2 for the line number (Figure 7B-J and changes the sign to zero, i.e. 0/2 is output from ROM 228 instead of 1/0 and has the same L # as 1/2 in Figure 7B ,. The SIGN bit has no effect on the L # to be used, but is in delayed in the same way as the line number, for reasons which are described below. A two is added to the remaining lines on the right. All lines on the left side except for the center line become transparent through the ROM 228. .

Hewlett-Packard Company

Int. Ref .: Case 1478 -42-

The state machine

The three most significant of the six bits at the output of the buffer 230, which represent the line numbers, become a ROM selection circuit 232, through which one of eight ROMs is

.5, which are used in the state memory 234, is selected. Any ROM in state memory 234 contains up to eight cuts. The three least significant bits are fed to memory 234, whereby the part is selected which relates to the particular section within the selected ROM. Each cut contains 256 eight-bit words, so that a total of 2048 bits are available for the cut. · Each bit corresponds to a step on the path to be scanned through the display points. It is 0 if the steps are longitudinal in one direction is along the x-axis and it is 1 if the step is along the y-axis. Recall that the special x-direction is given by the Total number of y movements since the origin is determined. \

The STRTL signal at the output of the sampler latch 224 becomes used to start a state machine address counter 236 to output an eleven-bit address at the frequency of the ENABLE pulses (the work interval). Eight of these eleven bits are used to sequentially imprint one of the 256 eight-bit words of each cut Select memory 234 and supply them to a buffer 238. The three least significant bits of these eleven bits at the output of the state machine address counter 236 are linked with ENABLE in an AND element 240, as a result of which the buffer 238 is released for the passage of it from the state machine memory 234 supplied word to a multiplexer 242, which 'selects the bits of the word under the control of the three least significant bits in succession and the address counter control 222 supplies. The output of multiplexer 242 is

Hewlett-Packard Company

Int. Ref .: Case 1478 " -β3. -

Status address decoder ■

'The eleven-bit word at the output of the state machine address counter 236 is applied to a state address decoder 246 which is a ROM and developed certain timing signals. If that by the eleven-bit word The counter reading shown reaches a predetermined value that occurs at a time / that the calculation of QERR and RERR (Figure 8) . Has been executed in a manner to be described, a signal STRTI (start of interpolation) on the reset input of a buffer 248 (Figure 5), the purpose of which is described below. At an appropriate time, the decoder 246 is still transmitting For reasons to be illustrated, a signal NACCCLR, which is a counter and clears three latches in the circuits of Figure 8 which determine R, RERR, COUNT and XHAT. The decoder 246 also inputs Signal NINTL, which is fed to the address counter control 222, so that their output signal is initialized at a suitable time " as well as a signal CTRLD which repeats an x-address counter 249 sets to the x address of the origin of the sector, as determined by a source 250, and sets a y address counter 252 to the y count of the origin, as determined by a source at the beginning of each line, -254.

Address control

As will be described in connection with FIG. 7A, the Address counter control 222 a signal XCNT for the counter 249 for every 0 in the output signal of the multiplexer 242 and a signal YCNT for the y-counter 252 for every 1 in the output signal of the multiplexer 242. The address counter control 222 also provides a signal XU / D to the x counter 249. In addition, the address counter control generates 222 a signal XDIR, which together with the signal YINC / YTNü from Multiplexer 242 paths like 31 and 3Γ defined in Figure 3, namely to the output of the multiplexer 242 and the signal SIGN from the buffer 23.0. XDIR and YINC / XTRU become descriptive in Way used to determine the value of the in the circuits.

Hewlett-Packard Company
Int. Ref .: Case 1478 '

measure figure 8. used trigonometric function to identify, which determine the values R, RERR, XHAT and COUNT. A signal ACCCLK, which is supplied by the address counter control 222, triggers the intermediate memories of the accumulators in FIG of the values of R and COUNT are used and a signal THETCLK provided by controller 222 is used to trigger a The intermediate memory of an accumulator in FIG. 8 is used, which is used to determine the value of XHAT.

Refer now to Figure 7A. At the start of each line and so at the start of each new cut, the signal NINTL from the status address decoder 246 (FIG. 7) goes to a low level and is applied to the preset input of a D flip-flop 256, causing XDIR to go high, indicating that a step along the x-axis towards the outer radius line is made that however, the direction with respect to the origin has not been determined.

NINTL also clears an eight state delay circuit 258, ■ the output of which is connected to an input of an exclusive OR element 260 is connected and one input must be the output of the flip-flop 256 'is connected where XDIR is present. The other entrance to the exclusive ■ OR gate 260 receives the SIGN bit from latch 230 (Figure 7). When the line is in the left half of the sector, SIGN is high so the output of the exclusive OR gate 260 is low, which means a count down, i.e. to the left. If " the line is in the right half of the sector, SIGN is high, so that the output of the exclusive-OR gate 260 up. is high, which means an up count. ·

. Control of XDIR is achieved as follows. YINC / XTHC from Multiplexer 242 (Figure 7) becomes an input of an AND gate. 262 supplied ,, whose other input ENABLE is fed. If the next step continues to go outside, YINC / XTNC is zero, so that The output of AND gate 262 is low

3U3429

Hewlett-Packard Company
Int. Ref .: Case 1478

is located. This output signal becomes an input of an exclusive OR gate 264, the other input of which is connected to XDIR at the output of the D flip-flop 256. Since XDIR when moving is at a high level to the outside, the output signal of the exclusive-OR gate 264 is at a high level, and XDIR also stays high. However, if YINC / XINC One is what indicates that there is movement away from the origin along the y-axis takes place, the output signal of the AND gate 262 is now at a high level when an ENABLE occurs, causing the output of the exclusive OR gate 264 to go to a goes low and thus also reduces XDIR, which is a step towards the middle of the sector at the next Means movement in the x-direction.

. ■ Since now the direction of a step along the x-axis and XUP / DN are known, it remains to generate the signal XCNT for each step in the x direction. To achieve this, YINC / XTHü is fed to a nine-state delay circuit 266 which is also deleted by NINTL. The output of the delay circuit 266 has one input of an AND gate 268 and one 'inverting input of an AND gate 270 connected, and ENABL is fed to their respective other inputs. When YINC / XINC is low, the output is of AND gate 268 at a low level so that no counting takes place in the y direction, but the output signal is des AND gate 270 high so that XCNT is also high and causes the x address counter of the sector counts up or down depending on whether XUP / M is high or low. .

When YINC / XINC is high, indicating that a step is being made in the y direction, the output of the AND gate 268 goes high, causing the y address counter of the sector counts up, which is the only possible direction in the present example.

3U3A29

Hewlett-Packard Company
Int. Ref .: Case 1478

The purpose of delay circuits 258 and 266 is previous data to make it possible to get through the interpolators according to Figure 10, They are triggered by CLK according to ENABLE qualifications. However the D flip-flop 256 is only triggered by CLK.

CLK is also fed to the clock input of a synchronizer 272, which is connected to ENABL with a D input and generates a signal ACCCLK at the corresponding output. Another D input of the Synchronizer 272 is connected to the output of AND gate 262, and the corresponding "Q" output is connected to a third D input connected, and its corresponding Q output generates the signal THETCLK.

The outputs of the x and y address counters 249 and 252 (FIG. 7) are connected to buffers 274 and 276, which in turn are connected to buffers 278 and 280, the ENABLE signal being fed to all of them at their enable input. In the case of each signal ENABLE, the x and y addresses are given on lines 282 and 284, which in FIG. 10 run to a display memory DM ¹ in FIG.

Determination of R and RERR ■

Reference is now made to FIG. The L # bits from the output of the Latch 230 in FIG. 7 and the display point scan control signals XDIR and YINC / XTNÜ from the address counter controller 222 (also FIG. 7) are fed to the input addresses of a ROM 286; in what values of + sin9, -sin9 and + cosQ for the angle θ to be used with each L #. Figure 8A shows the truth table for a given line containing the Output signals of the ROM 286 for the various combinations of the bit values of XDIR and YINC / XINC "shows: The ROM can thus pro-

it
can be programmed to provide twelve-bit matching output signals.

The twelve bits are used to represent those coming from ROM 286 Define fractions and will be receiving a

3143429 ^w · ♦ *
* · « - Al - Hewlett-Packard Company -SZ - Int. Ref .: Case 1478

Buffer 288 supplied, the output signal of which is supplied to one input of an adder 290. A cache 292 is connected between the output of adder 290 and the other input thereof, so that an accumulator is formed.

The output of latch 292 therefore contains the fraction of the running radius of which the five MSB bits are the desired RERR signal. It is expressed by five bits, which has been found to be sufficiently accurate, but the addition has. used all twelve bits to avoid too large an accumulative error. This situation can occur because over 1000 sine and cosine values have to be added or subtracted. are. It should be noted that the buffer memory 292 is cleared at the beginning of a line by NACCCLR, which signal is derived from the status address decoder 246 (FIG. 7) and which is triggered by ACCCLK, which signal is in turn from the address counter controller 222 (FIG. 7) is derived. As can be seen from Figure 7A, NACCCLR is derived from ENABLE, which controls the rate at which the steps through the indicator dots take place. Every movement in x and. ²⁰ y-direction has the effect that an incremental amount (isinG, + cosQ) is added to the last calculations of the radius. As will be shown, the integer portion of the radius calculation is held in a radius counter 294 under control of accumulator carry, XDIR and YINC / YINC.

The values of K and K and the distance between samples along of the radius lines are all equal to one in the present example, so that the connection of the signals YINC / XINC and the carry output of adder 290 to radius counter 294 causes it to count the number of carries and generate a signal R which is equal to the integer part of the sample distance in the radius of each Display point is. The radius counter 294 also outputs an INCR signal when the radius R exceeds an integer value of R, and a · signal DECR if the radius is reduced over a

3U3429

Hewlett-Packard Company
Int. Ref .: Case 1478

- 50 -

Integer value of R goes. The signal R is in a comparator 296 rait compared to a radius limit signal from a source 298 such that that a high level signal is generated whenever the radius R of a display point exceeds the specified limit. The output of the comparator is ROK ?.

The signals RERR, INCR, DECR and ROK? are routed through buffers 300 and 302. The signal RERR reaches the interpolation device according to FIG. 4 and ROK? goes via delay elements 304 to an input of a NAND element 306. A signal THETQK ?, which is derived in a manner to be described below, indicates by its high level that a display point is in the cut. THETOK is fed to the other input of the NAND gate 306 via the delay circuits 304. The output of the NAND gate 306 is fed to a latch 308 and its output to a buffer 210. Thus, if either ROK? or THETOK? are at a low level, is the output signal NVALD? of buffer 310 is high. NVALD? is fed to a display memory DM '(FIG. 10). When NVALD? is at a low level, the final interpolated data value, which is derived by the interpolation device according to FIG. 10 for the display point, is input into ^{the display memory DM 1.} The signals INCR and DECR are used via the circuits in FIG. 5 to control the reading function of two of the line memories 180, 182 and 184.

The radius counter 294

Figure 8B shows an arrangement of logic circuits for deriving the signals R, INCR and DECR from YINC / XTRC and the carry signal of adder 290. The carry signal is 1 when the radius in adder 290 increases and goes through an integer value. That Carry signal is -0 when the radius increases and not through . an integer value goes. The reverse is the carry signal 0 when the radius in adder 290 gets smaller and goes through an integer value, and the carry signal is 1 when the radius

3U3429

Hewlett-Packard Company

Int. Ref .: Case 147.8 -JS- -

♦ · «a

becomes smaller and does not go through an integer value. if the fraction of the radius is 0, the output signal of the radius counter denotes the radius of a display point which is equal to is the radius of one of the sample points.

YINC / XINC is via a two stage delay circuit 312 fed to one input of an OR gate 314, and XDIR reaches its other input via a delay circuit 316. The output of the OR gate 314 is connected to an open / Down control input of an up / down counter 318 and connected to an input of an exclusive OR gate 312. The other entrance of the exclusive-OR gate 320 is connected to the carry output of the adder 290, and its output is to inverting Inputs of AND gates 322 and 324 connected to each other represent other inputs to those with which the OR gate 314 is connected. The output of the OR gate 314 is connected to another inverting input of the AND gate 324 and connected to a non-inverting input of the AND gate 322. The signal NENBL of Figure 5 is the "P enable input of the ■ Counter 318 supplied, the output of the exclusive-OR gate 320 is connected to the T-enable input of the same counter. That Signal INCR is at the output of a two-stage delay circuit 326 is connected to the output of the AND gate 322, and the signal DECR is at the output of a two-stage "delay circuit" 328 is connected to the output of the AND gate 324. The The clock inputs of the delay circuits 312, 316, 326 and 328 as well as the clock input of the up / down counter 318 become the signal CLK and NACCCLR is applied to the "L" input (load) of the counter. If the radius does not go through a radial boundary e.g. the arcs in Figure 3, both INCR and DECR are zero, however, if it grows beyond a radial limit, it becomes INCR to 1 and DECR to 0. If it decreases beyond a radial limit, INCR becomes 0 and DECR becomes 1.

3Η3429

Hewlett-Packard Company
Int. Ref .: Case 1478

Determination of XHAT

Reference is again made to FIG. The values of XHAT _5, which in the present example are equal to tan9 ₂ - tanO, where Qg is the angle from the center of the sector to the outer line of the section and Θ, the angle of the inner line, are stored in a ROM 330 for each radius line . By supplying the L # signal from the output of the buffer 230 in FIG. 7 to the address input of the ROM 330, the corresponding value of XHAT is selected. The output of ROM 330 lasts for an entire line and is fed to the input of an adder 332. The output of the adder 332 is fed to a latch 334 which is cleared by NACCCLR from the status address decoder 246 and triggered by THETCLK from the address counter controller 222, both of which are shown in FIG. The output of the buffer 234 is connected back to another input of the adder 232, so that an accumulator is formed which, at the output of the buffer 334, generates the value of XHAT, which is the sum of XHAT for each step in the y-direction, since FHETCLK triggers the accumulator with every y-movement. A larger number of bits are used in the feedback to adder 332 in order to avoid an excessive accumulated error. 16 bits are used in this accumulator, which takes account of the fact that four MSB bits are used for the integer part of XHAT.

Determination of COUNT

The signals representing the line number from the latch 230 in Figure 7 and the signals YINC / XINC from the address counter controller 222 in the same figure are supplied to a ROM 336 where one of the values +1, -1 and tan9 _? is selected as shown in Figure 8C. The angle θ ~ is the angle between the outer line of a cut and the center line

3U3429

Hewlett-Packard Company
Int. Ref .: Case T478

- 56 -

of the sector, and therefore the value "of + tanGp depends on the selected Line number.

A latch 338 is between the output of ROM 336 and the input of an adder 340 is switched, and the output of the adder 340 is connected to a latch 342. Of the Latch 342 is accessed by NACCCLR from the State Address Decoder 246 (Figure 7.) and cleared by the ACCCLK. From the address counter control 222 (Figure 7) triggered. The output of the buffer 342 is connected to another input of the adder 340.

connected so that all values selected from ROM 336 for each by the display dot scanning control signals YINC / XINC and XDIR displayed step can be summed. This is the value COUNT, measured from the outer line of a cut, without consideration ■ whether this is in the right or left half of the Sector is located. To reduce the accumulative error, 16 bits are used in the feedback loop in comparison to eight bits for the sum. For the integer part of COUNT four bits are used. However, unlike RERR and XHAT, COUNT can have a negative value if the indicator point is is outside the outer line of a cut. For this purpose, the MSB bit is provided at the output of the buffer-342, which indicates whether the value of COUNT is positive or negative.

Determination of QERR

OERR is COUNT / XHAT, as explained earlier. This division could be done directly, but then 16 bits would be divided by 16 bits. Since in the above embodiment such an accuracy is not needed, but an accuracy of five bits is sufficient, a suitably selected five-bit field from both COUNT and XHAT provides the necessary bit resolution in the divider. Since XHAT is the larger of the two numbers and is not negative, it is simply shifted to the left,

■ 3U3429 ■: ν: ■. ι ί. >:

Hewlett-Packard Company

Int. Ref .: Case 1478 - & £ -

-ST "

until MSB is no longer zero, cLh. it finds a simple change of scale instead of. COUNT is then shifted by the same amount. The purpose of the switching elements 344, 346 and 348 is to the ability to create from zero to three shifts.

The five-bit outputs of the ROMs 346 and 348 are given through a latch 350 to a divider ROM 352, which the scaled COUNT by the scaled one. XHAT divides and the result in a buffer 354 which outputs the desired signal 9ERR, which is fed into the interpolation device according to FIG.

. To derive the signal THETOK? Which indicates whether a display point is angularly within the section,

. the bit representing the sign of COUNT is passed through an inverter 349 and the latch 350 to an AND gate. When COUNT is positive, this bit is high, indicating that the indicator point is not outside the outer line (θ ₂ ). However, when COUNT is negative, the input to 356 is low,. what makes THETOK? ceases to exist.

A comparator 358 is connected to receive COUNT and XHAT and to output a high level when COUNT is less than XHAT, indicating that the. Indicator point is not within the inner line of the cut, and outputs a bit with a low level * if COUNT is greater than XHAT is what indicates that the indicator point is within the inner line. This bit at the output of the comparator 358 goes through latch 350 and is fed to another input of AND gate 356. Its output signal passes through the buffer 354, whereby the .Signal THETOK?

which, as previously noted, is generated by the delay circuits 304 goes to a different input of the NAND gate 306 than that, the ROK? is fed.

3U3429

Hewlett-Packard Company
Int. Ref .: Case 1478

- SZ -

Reading out the line memory

As noted above, according to the present embodiment of the invention, the final interpolated data value for each display point is derived by interpolating two pairs of sample values which define the sub-section in which the point lies »As shown in FIG. the values of DP ₅ and DP _{6 are} derived from the samples S ₂ , S ₃ , S ^ ₁ and S ₃₁ which define a sub-cut, but the final data value for DPy is derived from the samples S, S ", S ,, and Sp ₁ , which define the previous sub-cut. Since DP _{β is} in the same sub-section as DPr and DP _β , its final data value is derived from the same data samples as the latter, namely S 1, S ₃ , S ₂ , and S ₃₁ . Therefore, the means for reading the sample values from the line memories 180, 182 and 184 (Figure 6) must be able to hold, advance and delay the sample values selected along each radius line of a section.

The selection of two of the line memories 180, 182 and 184 from which the samples are to be read is determined by ^:

which two of the signals Ml, M2 and M3 are at a low level are located. According to Figure 6, the signals M1, M2bzw. M3 the output enable connections the line memories 180, 182 and 184 are supplied. When Ml is high, the Line memory 180 for receiving, released while data its output channel is blocked so that no data can be read from it can be. M2 and M3 are then at a low level and prevent the line memories 182 and. 184 Receive data can. However, M2 and M3 open the output channel of line memories 182 and 184, respectively, so that data is read out from them at addresses which are predetermined by the counters 198 and 200.

3H3429

Hewlett-Packard Company
Int. Ref .: Case 1478

It can be seen that the outer radius line is on the left Page is located in the left half of a sector and on the right side in the right half of the sector. In the present specific embodiment of the invention relates the signal COUNT always on the outer line, so that the samples must be separated from the outer line from those of the inner line. This function is performed by multiplexer 360 and 362 performed. Different inputs of each multiplexer are connected to the respective I / 0 channels of the line memories 180, 182 ■ '- or 18.4 and are controlled as described below so that the multiplexer 360 samples from the outer radius line on a bus OL and the multiplexer 362 samples from the inner radius line to a manifold IL.

The control for the multiplexer 360 consists of an inverter 363, which is connected between a source for the signal M2 and an input of an AND gate 366, an inverter 368, between the output of an exclusive OR gate 370 and the other input of the AND gate 366 is connected, the inputs of the exclusive OR gate 370 the signals SIGN and M1 are fed. The output signal of the Exclusive RODER element 370 is also fed to an input of an AND gate 372, dessin the signal M3 is fed to the other input via an inverter 374. The output signal of the AND gate '366 is the input LSB, · Selection A of the multiplexer 360 is fed, and the output of the AND gate 373 is the input MSB, selection B of the multiplexer 360 supplied. With these connections, the outer lines are selected as shown in the table according to FIG. 6A and the Manifold OL supplied for the outer line.

The control for multiplexer 362 consists of an inverter 376, between a. Source for the signal M3 and an input an AND gate 378 is connected, an inverter 380, the between a source for M2 and an input of an AND gate

3142429

Hewlett-Packard Company
Int. Ref .: Case T478

- Co -

382 is connected, as well as an exclusive OR gate 383, whose one input with a source for SIGN, the other input with a source for M1 and its output with an input of an AND gate 382 and also via an inverter 384 with a ' Input of AND gate 378 is connected. The output of the AND gate 378 is connected to the input MSB selection B of the multiplexer 382 connected, and the output of AND gate 382 is connected to the Input LSB, selection A of multiplexer 362 connected. With these connections the inner line is shown as in Figure 6B selected and fed to the manifold IL for the inner line.

As can be seen from FIG. 10, the output line OL from multiplexer 360 is connected to the input of a shift register 386, and the output power IL from multiplexer 362 is connected to a shift register 388. Outputs Q. and Q _R of shift register 386 provide successive data points on the outer line to means to be described for deriving a first interpolated intermediate data value, and outputs Q _fl and Q _R of shift register 388 provide successive data points on the inner line to one Means yet to be described for deriving a second interpolated intermediate data value.

Selection of samples from the line memories

The signals INCR and DECR supplied by the radius counter 294 in FIG are used to cause the pair of counters 196, 198 and 200 (Figure 6) connected to the line memories, that they advance, stop at one point, or run back. It is worth remembering that INCR is on a high The level is when the radius of a display point becomes larger than that of a sample value, as in a step from DPy. To DPg (Figure 9), and that DECR goes high when the radius of a display point is smaller than that of a sample

♦ -a *

Hewlett-Packard Company

Int. Ref .: Case 1478 ■ --56 "-

- 6 / - ■

becomes, as in the step from DPg to DPy. If the integer Portion of the radius remains unchanged, as with a step of

DPr- after DP ,, both INCR and DECR stay at the same time ο

low level so that the counter readings do not change. As is described below, the counters cannot change until a SHIFT signal is given in a manner to be described below. SHIFT is given on every high level of INCR and DECR.

At the beginning of a line there is a special situation because, as can be seen from FIG. 3, INCR and DECR are at a low ■ Levels are until a display point has a radius greater than that of the samples S. | and S, -, is. Therefore neither INCR nor DECR the signal required to change the counter readings of the two memories that have just been read according to FIG. 6. Effect SHIFT. Under these circumstances, the counters become as follows . controlled. "

At the beginning of each line of data received from scanner 134, will a signal STRTL is generated at the output of the buffer store 172 (FIG. 5) and used to initiate the sampling of display points, as discussed in connection with FIG. The signal STRTL is also the set input of the buffer 248 and a two-stage shift register 392 supplied. The shift register is enabled by NENBL so that there are two consecutive High level pulses STRT1 · and STRT2 on different inputs an OR gate 396 outputs. Essentially, STRTL is delayed in shift register 392, creating two delayed versions can be generated by STRTL. for input into the OR gate 396. The output of the OR gate 396 becomes an input of a AND gate 398 is supplied, the other input of which is supplied to ENABLE, so that when these two signals coincide, the AND gate • 30 outputs a high level signal, namely SHIFT, so that the Counters can count.

If there is enough time for the RERR and 9ERR signals to build up for the first two samples of each line of a section

Hewlett-Packard Company

Int. Ref .: Case T478 ' -ßh-

- Cl -

dashes .is that occur simultaneously with STRTI and STRT2, where the first sample of each line is at the origin, a signal STRTI (interpolation start) is sent from the status address decoder 246 (Figure 7) to the reset input of the buffer '248 given. The latch 248 was set by STRTL and STRTI clears it. The time interval between STRTL "and STRTI is denoted by WAIT. When STRTI occurs, the cache returns 248 free a buffer memory 399 to which the signals INCR and DECR from the radius counter 294 (FIG. 8) are fed. After this INCR and DECR have passed through buffer 399, they become MINCR and MDECR, respectively, and become different inputs of the OR gate 396 and generate, if they are at a high level, .at the output of the AND gate 398 .a signal SHIFT. In addition, the signal MDECR is fed to an inverter 395 which generates a signal NMDECR. .

Control of the counters with SHIFT

So that counters 196, 198 and 200 can count, their inputs must ENT and ENP are low. It is assumed that sample values are read into the line memory 180 'so that M1 and M2 and M3 are both low. When explaining the write function it was noted that a high signal M1 causes the ENP input of the counter

196 for the line memory 180 for the entire line on one is low, so that its count was advanced each time the signal ADDEN appeared, which corresponds to the inputs ENT is fed. For counters 198 and 200, NM2 and NM3 are during a whole line at a high level and since it has inverters

197 and 199 are fed to the corresponding ENT inputs,

. these inputs are low during the line held.

■ Signals M2 + SHIFT and M3 + SHIFT are transmitted via inverters 400 and 402, respectively fed to the ENP inputs of counters 198 and 200, respectively. M2 and M3

Hewlett-Packard Company
Int. Ref .: Case 1478

are for the entire line on a low rule, so that the ENP inputs cannot go low. Thus, only SHIFT can cause counters 198 and 200 to count. The signals M1 + SHIFT, M2 + SHIFT and M3 + SHIFT are derived by supplying MI, M2 and M3 to inputs of OR gates 408, 410 and 412, the other inputs of which are fed to SHIFT. .

When a line memory 180, 182 or Ϊ84 is read and the corresponding counters 196, 198 or 200 count in response to the SHIFT signal as described, the counters count up when the AND, ANDp and AND ₃ signals are high Levels are and count down when UHOa, UNDp and AND _{3 are} low. As when considering the write function, assume that the samples are being written into line memory 180 so that M1 is high and M2 and M3 are low. It is also assumed that NMDECR are at a high level. Under these conditions, the output signal AND _{1 of} the OR gate 202 (FIG. 5) is at a high level, with the result that the counter 196 for the line memory is in the is enrolled, counting up as desired. The AND ₂ output of the OR gate 204 and the AND ₃ output of the OR gate 206 are also high so that the counters 198 and 200 are set to count up, but when NMDECR is low they will set to count down.

Since the counters 198 and 200 count up and down, the Samples at the corresponding addresses of the line memories and 184 in the Q ^ section of the shift registers 386 and 388 (Fig 10) entered. The SHIFT signal also controls the shift registers 386 and 388 via the following logic circuit in Figure SHIFT is fed to one input of an AND element 409 and one input of an AND element 411, while MDECR is fed to the other

-ΐ Ψ%

3Λ431429

Hewlett-Packard Company

Int. Ref .: Case 1478 -JrT-

Input of the AND gate 409 and via an inverter 413 the other ■ Input of AND gate 411 is fed. The output of the AND gate 409 is connected to the left shift inputs of shift registers 386 and 388, while the output of the AND gate 411 is connected to its right shift inputs. if

The signal SHIFT goes to a high level and MDECR is at a low level, the AND gate 411 causes the registers to shift the sampled values contained in them to the right and to receive new sampled values at the inputs. But if SHIFT and MDECR both go to a high level, the AND gate 409 causes the samples in the registers _{386 and 388 to be shifted to the left, ie that Q. is replaced by Q β} , Q _β by Qp and so on. The shift registers. 386 and 388 are eight words long and have the ability to hold an additional six samples with two words remaining in the registers. SHIFT is set twice at the start of each line, corresponding to the effect of STRT1 and STRT2, which are present at the input of the OR gate 396 (FIG. 5). As a result, the first two data points S ₁₀ and S> from FIG. 3 for the line R _Q and S _1Q1 and S ₁₁₁ for the line Rj are entered into the Q _β and Q sections of their respective shift registers 386 and 388. The interpolation can now proceed, but no further change occurs in the four samples until the display point sampling signals YINC / XINC, XDIR cause a step to a display point which has a larger radius than that of the display point S ₁₁ , S ₁₁ , , at which point the INCR signal goes high causing SHIFT to go high and increment counters 198 and 200 and move the shift registers to the right so that samples S ₁₁ and S _{12 are} output Q _ß and Q. of the shift register 386 and samples S 1, and S, ", the outputs. Qn and Q. of shift register 388 are supplied.

It is now assumed that the display point scanning signal causes a step to a display point whose radius is smaller than that of S ₁₁ and S ₁₁ , that is, a step back over the respective

Hewlett-Packard Company

Int. Ref .: Case 1478. - -GfT-

& a α

inner radial boundary .. Both the DECR and MDECR signals are now at a high level and, if one remembers that M2 and M3 are at a low level, it can be seen that the signals AND “and AND ₃ are low so that counters 198 and 200 are set to count down. The SHIFT signal causes the counters to count down and, in combination with MDECR, causes the shift registers 386 and 388 to shift to the left, whereby the display points S, _Q , S .. and S ,,. ,, S. », go back are set to the locations Qn and Q _{A of} the registers 386 and 388, respectively. Should the step to the next display point cause a third crossing of the arc line on which S, - and S ,,, are located, the samples lost from the registers S «« and S _{,? 1} cause no problem, since the next points depend on the Line memories * * 182 and 184 are the samples S ₁₂ and S, ₂ , since the read address is controlled by SHIFT as previously described.

Interpolation.

Reference is now made to FIG. The samples at the outputs CL and CL of the shift register 386 are supplied to multiplier ROMs 414 and 416, and the samples at the outputs CL and Q _{B of} the shift register 388 are supplied to multiplier ROMs 418 and 420, respectively. The signal RERR, which represents the radial position of the display point, is supplied to all four ROMs after being temporarily stored in 415. The data samples are represented by five-bit numbers, as is the case with the RERR signal, which is of course a fraction. The ROMs are programmed to appropriately multiply the RERR * Q "value in 416 and 420 and the (1-RERR) * Qg value in 414 and 418. The output signal of the ROM 414 is applied to one input of an adder 422 through a latch 414 ', and the output signal of the ROM 416 is applied to the other input of the adder 422 through a latch 416', so that its output signal is the first interpolated intermediate data value is. In a similar way

Hewlett-Packard Company
Int. Ref .: Case 1478

the outputs of the ROMs 418 and 420 become through latches 418 'or 420' fed to the inputs of an adder 424, so that its output signal is the second interpolated intermediate data value. · ■

The first and second interpolated intermediate data values I 1 and I ₂ are fed to the inputs of multiplier ROMs 426 and 428, respectively, via latches 422 'and 424'. The signal GERR "from the output of the latch 354 in FIG. 8 is fed to the multiplier ROMs 426 and 428 after passing through latches 430, 432 and 434, so that the corresponding contributions of the first and the second are interpolated at the outputs of the ROMs 426 and 428 The ROM 426 performs the multiplication of 1-0ERR by the output of the latch 422 ', and the ROM 428 performs the multiplication of 9ERR by the output of the latch 424'. Latches 426 'and 428' are connected between the outputs of the ROMs 426 or 428 and various inputs "of an adder 436, so that the final interpolated data value is generated at its output. After passing through latches 438 and 44.0 and a buffer 441, the final interpolated data value is ^{fed to the x and y addresses in the display memory DM 1} , which were determined by the x and y sector address counters 249 and 252 (FIG. 7), provided that the display point is angularly and radially within the section, a fact which is indicated by NVALD at the output of AND gate 306 (Figure 8) with a high level. The memory DM ¹ is scanned by a read controller 442 in any desired manner and the signals are applied to a display to produce an image free of moiré patterns and other noise present in images from other imaging systems.

Summary of the operating mode

The following table shows the values of the Radius, COUNT and XHAT

■ 3U3429

Hewlett-Packard Company

Int. Az ..:. Case 1478 - & Γ-

and the states of the display point scan control signals XDIR and YINC / XTNC, and INCR, DECR, XUP / DN, XCNT and YCNT for the display points DPr to DP /. (Figure 9), where DP _{5 is} the initial display point with the initial values for Radius, COUNT and XHAT of R., C ^ and XH-. Usually the starting display point is at the origin of the sector at which all these values are zero, but the recursive addition could also start at any other display point for which the values are appropriately known. As previously stated, XDIR = I denotes a step away from the center of the sector, YINC / XTNC = O denotes a step along the x-axis, and YINC / XTNC =! one step along the y-axis away from the origin. INCR and DECR can both be 0 if steps from one display point to another do not cross the radial boundary of an undercut. If one of these signals is 1, the step crosses such a boundary.

Values of 1 for XCNT and YCNT indicate a step Kings of corresponding axis.

As a further aid to understanding the operation of the preferred Exemplary embodiment according to Figures 5, 6, 7, 8 and 10 are used in figures 11 and 12 showing the timing of the various signals used. The points in the circuit at which these signals occur. are indicated by corresponding letters in a circle.

Hewlett-Packard Company-ι Int. Ref .: Case 1478

; λλ

JLNOÄ O σ • I. • a H -a O -a σ • CN. • a O rH • a -a • O • a O rH • a JLNDX H pi O pi rH pi rH CD ' pi - O X U ω rH U rH O pi Να / αίΙΧ rH VO rH r- O co O CTv 0 O C. rH CN rH O - Hoaa O O rH O O • a 0 ■ C Eh CN O CD O O rH HDNI O O O rH rH co 0 O CD In rH. cn O ep DNIX / DNIÄ O O ' . rH O ' O σ rH ! U UJ • a O 0 O Ηΐαχ O O O rH rH I. rH • rH X O O U O O rH rH rH H <3 CJ EH CN CN CN ■ a • a • a . -a • a • a -a -J- • a CN -a -a > 1 > i > 1 > 1 -a ^{+ +} >, rH CN CN rH rH K CN O rH CN H X -J- -J- -J- -J- I. X CD O 1 · CD -j- • a -a • a -a • a -a d • a C. • a • a X X X X X CN -a X • a X X CD co Eh co Eh EH Eh Eh C. rf! rf! (Q approx -j- -j- ►χ] K EH -U • a X • a X X X X X pi *. <] <] O <3 ■ + rH CNl CN CN CN X -J- -J- rH -J- rH -J- -J- • a -a -a -a • a • a I. • a • a ■ a SE te ίο K W. W. SG X X X X X X ■ X X X CNi CN CN CN CD CD CD CD C. CN C. β β CNl ro CD approx approx approx CD -P U -P Z 4Y • P C. rO rö CN 4Y CN O -f- -j- 4Y -f. -J- α H CM CNl rH iH CN rH 4- ■ + -J- -J- -j- 1 -j- -J- -a • a -a • a • a • a -a • a U U U U U xj U 0 CN CN CD CN CD Ul CD ω O Ul O U O C) U + CN W. CN CN CN α CNl CD CD CNl CD CN • a CD β β CD cn CD ¹ U • a -a cn O β (0 • a co co O α • a pi co 0 co CN CN CN I. I. -J- -J- I. -a • a • a pi pi pi CU in 0 ' cn Q rA

Hewlett-Packard Company

Int..Az .: Cose 1478 '- -JsA -

Alternative embodiments and modes of operation

To increase the resolution of a part of the image, e.g. in the Middle, the radius lines of the scanner can be made closer together in this area. The scanning converter system according to the invention could adapt to such a format by storing the ones and zeros in the memory of the state machine according to Figure 7 have been modified to provide scan control signals to select appropriate display points and by changing the stored values of the various trigonometric .Features.

At the present time, the scanning speed of A / D converters is so that it is desirable to interpolate along the radial direction, however, the advance in semiconductor technology is such that much higher scan speeds can be expected, so that such interpolation . is not needed. In such a case it would still be necessary to determine INCR and DECR so that correct sample values, one from each radius line can be selected. Also would be it is still necessary to perform the angular interpolation. The system described would work in this way, if the RERR signal were set to zero.

FIG. 13 shows a modification of the system in which the ROMs .414, 416 from FIG. 10 through a ROM 446, the ROMs 418 and 420 through a ROM 448 and the ROMs 426 and 428 are replaced by a ROM 450.

The buffers have been omitted for the sake of clarity. The ROMs 446, 448 and 450 are identical. Each contains a different stored output signal for each combination of the error signal, be it RERR or GERR, as well as the possible values of the samples. As shown, the RERR signal is applied to ROMs 446 and 448 and the 9ERR signal is applied to ROM 450 so that the first interpolated intermediate data values L and I _{2 are derived} at the radial position of each display point and the final interpolated data value FDP at the angular position of the display point

3H3429

Hewlett-Packard Company

Int. Ref .: Case 1478 "-J56--

is derived. In this case, the samples S and Sp would be those along one radius line of a section, and the samples S ₃ and S _{4 would} lie along the other radius line. However, as previously described _? the signal OERR could be fed to ROMs 448 and 448 and the signal RERR to ROM 450 so that the first and second interpolated intermediate data values I, ¹ and Ip 'are at the angular position of the display point. _{In this case, S 1} and Sp are along one arc, and S 3 and S are along another arc.

· Figure 14 shows a single semiconductor element 452 »that internally performs all of the functions of the three elements 446, 448 and 450 in FIG.

FIG. 15 shows an embodiment of the invention in which the signals RERR and QERR are not actively derived when the display points of a section are scanned. Rather, the values of RERR and QERR for each display point have been previously determined and are stored in a ROM 454. The display point scan control signals XDIR and YINC / XINC are provided by a device and the x, y address of each display point is determined by counter 458 and 460 are determined as explained above, the signal STRTL is applied to the ROM 454 and to reduce the number of connections required, the word representing the first line of a sector can be used by a means 462 for generating a signal at the beginning of each sector scan From the x, y address of a display point, the ROM 454 selects the appropriate stored values of INCR and DECR which are used as described in the description of FIGS 10 to select the correct sample values S, S ", S ₃ and S / from the line memories. ROM 454 contains the final data values for all possible combos nations of RERR, OERR for each display point and DATA are stored. The appropriate final data value is for each point from the digital values of RERR, 9ERR and

31 / O /

Hewlett-Packard Company
Int. Ref .: Case 1478

DATA selected. The ROM 454 is thus a device based on the sample and display point sampling control signals final interpolated data value determined for each display point.

The scanning transducer system according to the invention is suitable for enlargement of a selected part of the image, which is between any two Radius lines and lies within a given radius range. As will be described in an additional application, can achieve this in that devices are provided that have an Anzetgemarke to identify the radius lines and the Radius area included, · a device is provided for Divide the RERR for each display point in the smaller part of the image by a magnification factor m, as well as a device is intended to multiply XHAT and COUNT for each display point in the smaller area by m. It would also be possible to to scan the smaller part of the image faster in order to obtain clearer images of fast-moving objects there.

Instead of using a single radial position, one could also calculate two radial positions in the following way. For each line within the sector, two constants labeled & R and AR would then be selected. AR _? would be fed to a first accumulator and 4.R- would be fed to a second accumulator. These two accumulators would always be updated if the display point scanning signal indicated a movement in the y-direction. The first accumulator would be Q ₂ in the calculation

use the radius that corresponds to the distance from the sector vertex along ■ \

corresponds to the outer line at the intersection of the line where the current display point DP is located. The second accumulators · \ tor would θ, use in the calculation of the radius corresponding to the distance from the sector vertex along the inner line to the intersection point on the same line, as described above. \ Each radius counter would generate its own signals INCR and DECR [ for the appropriate movement of the two shift registers, so that the _{signals at the outputs Q "and Q ß of} each shift register ;;

3U3429.

Hewlett-Packard Company

Int. Ref .: Case 1478 - £ 7- -

standing data limit their corresponding radius calculation would. The two radius calculations would in turn generate two RERR signals, one for the outer line with RERR "and for the inner line RERR ". These signals would be used to interpolate the data pending at each shift register. The end result of the above procedure would be two interpolated intermediate data values, each separated by two sample values would be limited that do not necessarily have the same radial offset from the vertex. The interpolated Intermediate data values would be at the intersection of the current line the output display and the two scan lines that are straight can be read out from the line memories.

These two intermediate data values are then used in a way that which is analogous to the method described above for correcting 9ERR, mainly using the signals COUNT and XHAT. The end result is then a final data value which is derived using COUNT and XHAT for interpolation of the interpolated intermediate data values at the intersection of the current line of display points with the radius lines of a Cut.

As will be described in an additional application, the extension of a selected range by multiplying 9ERR for each display point in this area with a magnification factor m, as well as by dividing RERR by m.

Hewlett-Packard Company
Int. Ref .: Case 1478

Instead of the display points contained within a pair of radius lines To scan, it would be possible to identify display points in any desired sequence by their x and y addresses and to supply these addresses to a ROM programmed with OERR, RERR, LJ and the number of the sample data. The L # and the sample data number are supplied to a ROM in which the sample data is stored so that the correct four sample data values for interpolation can be obtained. These and the values of QERR and RERR are fed to an interpolation ROM. into which the final interpolated data values for each combination of the four sample data values and each combination programmed by OERR and RERR. It should be noted that that the interpolated intermediate data values never appear, though they are used when programming the interpolation ROM.

Another way to use ROMs is to to supply the x and y addresses of each display point to a ROM in which OERR, RERR, INCR and DECR are stored. The sample data values are stored in a three line buffer memory as described, and INCR and DECR become the Buffer memory fed by an up / down counter, so that a correct sequence of sample data values for each radius line is fed to a different shift register. INCR and DECR will then is used to operate the shift register as described, so that the correct four sample data values are sent to the interpolation ROM are fed. GERR and RERR are also used in the interpolation ROM which is programmed to achieve all possible combinations of the four sample data values and 9ERR and RERR can be.

In all embodiments of the invention described so far the signals that control the sampling sequence of the display points are derived first and the corresponding data samples from which the final interpolated data values for the display points

Hewlett-Packard Company

Int. Ref .: Case 1478 - * 9-

are to be fed are derived in response to the scanning signals. It
however, it will be readily apparent to those skilled in the art that the sample data values could also be selected first, while the display points for which the final interpolated data values are to be derived could be selected in response to the sample data values. It is only necessary that the sample data and the display points have a relationship such that the samples used in deriving the final interpolated data values for a display point define an area which contains the display point.

Claims (9)

Hewlett-Packard Company
Int. Ref .: Case 1478 PATENT CLAIMS Circuit for converting original points on polar coordinates in pixels arranged in rows and columns, marked by a memory for storing a number of by means of one Scanning device (20) along radius lines of the polar coordinates determined in uniform steps from the coordinate origin Original points in the form of data values; a retrieval device (DPSG, 82) related to any given pixel retrieves at least four data values from memory, each of which has two original points on two adjacent radius lines of the . Correspond to polar coordinates and span a square that defines the includes the original point immediately corresponding to the respective image point; · · and an arithmetic circuit (112, 114, 116) which, from the four data values, creates an interpolated data value for the respective Pixel calculated. 2. Circuit according to claim 1, characterized in that that the computing circuit has a first device (112), the two original points from two data values corresponding to two original points on one side of the original point corresponding to the image point calculates a first interpolated intermediate data value, a second device (114), which consists of the other two Data values calculates a second interpolated intermediate data value, as well as means (116) for interpolating the final one from the two interpolated intermediate data values Data value calculated. 3. Circuit according to claim 2, characterized in that that a device (104) is provided for deriving a signal which represents the angular position of the respective pixel Hewlett-Packard Comp. Int. Ref .: Case 1478 O I 4 Ο t ty represents that the establishment "(112) to derive the first interpolated intermediate data value an interpolation between makes two data values, the two 'original points on one Radius line d, he polar coordinates correspond to that of the facility (114) to derive the second interpolated data • intermediate value an interpolation between two data values undertakes that the two original points correspond to another radius line of the polar coordinates, and that the device (116) to form the final interpolated data value from the two interpolated intermediate data values accordingly the signal corresponding to the angular position is the final one Performs interpolation. 4. Circuit according to claim 3, characterized in that that means (84) are provided for deriving a signal corresponding to the radial position of the respective pixel and that the means (112, 114) for deriving the interpolated intermediate data values correspond to the Derive radial position. 5. Circuit according to claim 2, characterized in that that e.a means (84) for deriving one of the radial Position of the respective pixel corresponding signal provided is that the device (112., S1) for deriving the first interpolated intermediate data value interpolates two data values, the original points on "different radial lines. which are closer to the coordinate origin than the · the other two that the device (114, Sl) for Deriving'des second interpolated intermediate data value an interpolation between the other two data values and that the means (116) for forming the final "interpolated Data value corresponding to the radial position of the pixel corresponding signal (S2) to the final interpolated Data value determined. · 3H3A29 Hewlett-Packard Company Int. Ref .: Case 1478 - 3 - 6. Circuit according to claim 5, characterized in that that means (104) for deriving a signal corresponding to the angular position of the image point is provided and that the means (112, 114) for deriving of the interpolated intermediate data values, this corresponds to the Derive the angular position of the image point. 7. Circuit according to claim 4 or 5, characterized in that the device (104) for generating that corresponds to the radial position of the respective pixel Signal its facility (DPSG), the sequential Scan signals identifying pixels are generated on a scanned path from a given pixel with a known radius of the polar coordinates for the current image point, a device (58, 60) which In response to the scanning signal, a sum signal is derived from the addition of the following values to the known radius of the given Pixel for the following steps in the scanning path: K sin θ for each step from one pixel to the next along a line in a direction away from the center line of the sector, minus K sin θ for each step of an image point to next along a line in a direction towards the centerline of the sector, plus K cos θ for each step from one pixel to the next along a column in a direction away from the origin and minus K cos θ for each Step from one pixel to the next along a column in a direction towards the origin, where θ is the angle is between a column of image points and a radius line which is angularly close to the respective image point, K is the distance between the columns and K is the distance between the rows of pixels, and means (84) having the difference between the sum and the radius of a of the arcs on both sides of the respective display point as a fraction of the uniform step size S from the origin of the coordinates. Hewlett-Packard Company Int. Ref .: Case 1478 - 4 - 8. A circuit according to claim 7, characterized in that K and K are related to S, so that the difference as a fraction of S is a fraction of the sum. 9. Circuit according to claims 3, 4 and 6, characterized g e k e η η ze Inet that the means (104) for generating a the angular position of the respective display point representing signal has a device (DPSG), the scanning signals for Identification of successive pixels in a scan path from a given pixel with known polar coordinates · Radius generated to the current pixel, a device (88) which generates a signal ΔΧΗΑΤ that the product of K and the difference between the tangent functions of the corresponding angles between the radius lines and a column of pixels represents, a device (90, 92) which, in response to the scanning signals, derives a sum which is equal to the addition.der is the following values for the known distance between the radial lines measured from one containing a given pixel Line - when scanning from the given pixel to the current one Pixel: ΔΧΗΑΤ for each step from one line to the next in a direction away from the origin and minus AXHAT for each step from one row to the next towards the origin, this sum being XHAT, has means (96, 98, 100) which a sum derives, which equals the addition of the following values to the known Is the distance of a given pixel from one of the radial lines, measured along the line containing the given pixel, when scanning from the given pixel to the current one . · Pixel: plus K for each step along a line of one Image point within the radial lines to the next image point in a direction away from the one radial line, minus K for 30 'each step along a line from one pixel within of the radial lines to the next pixel in one direction . which is a radial line too, plus K tan θ for each longitudinal step a column from an image within the radial lines to the 3U3429 a a Hewlett-Packard Company ' Int. Az.! Case 1478 - 5 - next pixel in a direction away from the one radial line minus K tan θ for each step along a column of one pixel within the radial lines to the next pixel in a direction towards the one radial line, where θ is the angle between the one radial line and a column and the values are the same for steps in the same direction with respect to the rows and columns of pixels outside of the radial lines are. '■ ·