Abstract:
A video processing system which can produce a different shape of output picture than the input. Addresses into which incoming picture points must be written to produce the desired shape changes are stored in a shape store. These addresses can also be manipulated in real time so that the position of the shape they define is changed. For example a Mercator projection of a map can be projected onto a globe and this globe could then be tilted, rotated etc.

Description:
This is a continuation of application Ser. No. 580,370, filed Sep. 6, 1990, now abandoned, which in turn is a continuation of Ser. No. 163,184, filed Feb. 25, 1988 (abandoned), which in turn is a continuation of Ser. No. 713,028, filed Mar. 18, 1985 (abandoned). 
    
    
     BACKGROUND OF THE INVENTION 
     This invention relates to video signal processing systems, especially though not exclusively for producing so called production effects in television. 
     In our co-pending Patent Application No. 8306789 there is described a video signal processing system in which production effects are produced by writing input video signals, received in television raster format, into storage locations of a frame store so chosen that when the signals are subsequently read from the storage locations in television raster format, the signals are re-arranged in the raster to alter the image in shape, size or position, or in some other way. In order to achieve the selection of storage locations for the input signals a shape store is provided containing, at positions which correspond to respective pixel positions in the television raster, address signals identifying storage positions in the frame store at which the input video signals should be written in order to achieve the desired effect. A set of address signals describing a desired shape or other characteristic of an image is called an address map. Normally the address map is only coarsely sub-divided, comprising, say, an address for each eighth pixel, in each eighth line of a frame. Sequences of address maps are provided to produce changing effects, successive maps in a sequence describing, say every fourth field. The addresses are thus distributed on a coarse grid, and interpolating means are provided to produce addresses for the intervening pixels and also for the intervening fields. This allows addresses to be read at a rate less than `real time`, but to be used after interpolating for writing the input video signals in the frame store in real time. 
     The stored maps are entered in the shape store from a computer having a keyboard or other control means by which desired production effects can be entered into the computer. The computer is arranged to generate the addresses for desired maps under software control. Effects which can be produced in the image include such effects as rolling a sheet into a cylinder, turning pages of a book, or converting, say a map in Mercator projection into a representation of the map on a globe. To enable effects to be created which involve changing the image of a two dimensional object into a three dimensional object, or turning an object in space, the computer is arranged to generate addresses in three dimensions, and then convert the three dimensional addresses into two dimensional addresses by projection on the image plane, taking account of perspective. 
     Each storage location in the frame store in which the re-arranged video signals are written will correspond to a pixel in the output signal television raster. However, in general, the address calculated by the computer will not coincide with a storage location in the frame store but will lie within a rectangular area defined by four storage locations. Therefore on writing an input video signal (relating to a pixel in the input signal raster) in the frame store, it is usually necessary to distribute the signal among four storage locations by interpolation, (this interpolation being different from the address interpolation previously referred to). This means that up to four storage locations have to be accessed for each address obtained directly or by interpolation from the map. As a corollary, each storage location has to be accessed a plurality of times in response to different addresses. Furthermore the distribution of addresses in a map over the area of the output image may vary, so that the `density` of addresses per unit area will differ on the image. This can lead to incorrect variations in brightness over the output image. This effect can be appreciated by considering the change of a map in Mercator projection into the image of a map on a globe, in which case all video signals representing the top of the first map would be crowded in the region of the north pole on the globe. To reduce this effect, means are provided to variably attenuate video signals, prior to writing in the frame store, in proportion to the density of addresses to produce density compensation. 
     The system described in the aforesaid patent application represents a powerful means of producing video effects in real time. The address maps have, however, to be produced off line, and this involves the producer in trying to determine all effects which he may desire for a particular programme or series of programmes, since he does not have the facility of creating effects during the transmission of television signals. 
     SUMMARY OF THE INVENTION 
     In accordance with the present invention there is provided a video signal processing system comprising frame store means, 
     input means for receiving sequences of picture point signals defining successive pictures, 
     shape store means for signals representing address maps for re-arranging input video signals received in raster format, and circuit means for manipulating address signals derived from said store so as to produce movement of the image shape defined by said address signals. 
     Preferably, said shape store is arranged to store three dimensional address signals and said circuit means is arranged to manipulate said signal in three dimensions and then convert them into two dimensional address signals by projection on an image plane, taking account of perspective. 
     The present invention is based on the realisation that greater flexibility of control can be achieved without undue hardware complexity by effecting movement of the shapes defined by the address maps using circuit means, which allow the movements to be continuously adjusted in real time by the producer, rather than by the provision of respective address maps which have to be created off line. Conveniently the circuit means is arranged to produce rotation about three axes, or displacement in three dimensions, or combinations of these. The invention reduces the number of address maps which need to be stored and although it remains necessary to store a library of individual address maps and sequences of such maps, the number of effects which can be produced is no longer limited to the number of predetermined maps. The conversion to two dimensional addresses after manipulation also adds to the flexibility of the system. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     In order that the invention may be more clearly understood and readily carried into effect, it will now be more fully described with reference to the accompanying drawings in which: 
     FIG. 1, parts 1 and 2, illustrate in block form on example of a video signal processing system according to the present invention. The figure is in two parts; 
     FIGS. 2 and 3 are diagrams explanatory of the operation of part of the system illustrated in FIG. 1; 
     FIG. 4 illustrates details of a signal processor included in the system illustrated in FIG. 1; 
     FIG. 5 illustrates details of a second signal processor of the FIG. 1 system; 
     FIG. 6 shows a representative arrangement of pixel addresses which will be used in describing the operation of the system; 
     FIG. 7 is another diagram explanatory of the operation of the FIG. 1 arrangement. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Referring to the drawings, reference 1 denotes a shape library for storing predetermined groups of signals defining addresses in a television raster. The library is in the form of a magnetic disc store and it is arranged to store a three dimensional address for each pixel on the coarse grid which makes up the map of a shape, and a map is provided, say for every fourth television field in a sequence making up one continuous effect. Each dimension of an address comprises an 16 bit word, of which one bit is a flag bit the purpose of which need not be discussed in this application. In FIG. 2, the dots in the frame ABC (only partly shown) represent pixel positions in the input television raster of the system. It is to be understood that the pixels represented comprise only every eighth pixel on every eighth line, and the store 1 stores a three dimensional address for each such pixel. Assuming that the address map for the frame ABC is one of a sequence predetermined to effect transformation of the output image through a sequence of shapes, other address maps are stored for subsequent frames, such as A&#39;B&#39;C&#39; which is represented as being the fourth field after ABC. Some of the pixels for which addresses are represented are also shown on this frame. Reference 2 denotes the computer used to generate the addresses in response to commands, introduced via a keyboard or other input means such as a touch tablet. The controller for the disc store 1 is indicated by the Reference 3. The disc store has, of course, the capacity to store many shape maps or reference of such maps. 
     Address signals read from the disc store 1 are applied via the controller 3 selectively to three 20,000 word shape buffer stores 4, 5 and 6 via switching means indicated diagrammatically at 7. The switch is phased by the sequencer for the system, so that address maps are fed in sequence to the three buffers from the store 1 in successive periods, each comprising four fields. During any one such period, therefore, address maps are available in two of the buffers, whilst a new address map is in course of being written into the third buffer. This gives adequate time for addressing the disc store despite its relatively slow rate of operation compared with the television pixel rate. During the period in question, the two buffers, say 4 and 5, already containing address maps are read in parallel into a temporal interpolator 8 which produces, by interpolation, four coarse grid address maps, one in each of the four field periods, from, say, the frame ABC to the frame A&#39;B&#39;C&#39; in FIG. 2. It will be understood that the addresses in both maps ABC and A&#39;B&#39;C&#39;, will contribute more or less to the interpolated addresses as the frame timing advances from that of ABC to that of A&#39;B&#39;C&#39;, thence the description &#34;temporal&#34; interplation. The interpolator 8 may be of the form described in our co-pending patent application no. 8306789. The interpolated address maps are fed out, frame by frame, to a first processing circuit 9. 
     It will be understood that at this point the address maps are still coarse maps and that the address signals are three dimensional. 
     The processing circuit 9 is arranged to manipulate address signals received from the interpolator 8, so as to produce the effect of movement of the respective image shape. The manipulated signals are then passed to a second processing circuit 10, which is arranged to convert the three dimensional address signals to two dimensional address signals related to a single image plane, with perspective. Assume that a three dimensional shape, described by a particular coarse address map, is represented by 64×100 co-ordinates in each of x, y and z. To move this three dimensional shape, 4×4 matrix transforms are used, three for producing rotations about the axis and three for producing translations along the axis. 
     The transforms for rotations are as follows: ##EQU1## 
     The transforms for displacement are as follows: ##EQU2## 
     Any desired move in three dimensions can be defined by multiplying a number of the above basic transforms and it is to be noted that, due to the nature of matrix multiplication, the order in which the transforms are multiplied is critical. The processing circuit 9 is arranged (as will appear) to apply the resultant movement transform to the three dimensional coarse map from the interpolator 8 as twelve co-efficients. The co-efficients themselves are evaluated in a computer 11 which is arranged to perform the matrix multiplication. The particular multiplications which are performed in the computer 11 are determined by operator control of a joystick or other means by which the producer can signal a desired movement of the image shape to the system. the manipulation of one line of the coarse map (for a particular field) can be represented as follows: ##EQU3## 
     The quantities a,b,c, etc. are the co-efficients evaluated by the matrix multiplication. The d column is not in fact used and as a general result the co-ordinates, after manipulation to effect the image movements, can be expressed as follows, for a representative address after movement) x i&#39;  y i&#39;  z i&#39;  : 
     
         x.sub.i&#39; =a.sub.1 x.sub.i +a.sub.2 y.sub.i +a.sub.3 z.sub.i +a.sub.4 
    
     
         y.sub.i&#39; =b.sub.1 x.sub.i +b.sub.2 y.sub.i +b.sub.3 z.sub.i +b.sub.4 
    
     
         z.sub.i&#39; =c.sub.1 x.sub.i +c.sub.2 y.sub.i +c.sub.3 z.sub.i +c.sub.4 
    
     Reference will now be made to FIG. 3 to explain the operation of the second processor 10, in converting manipulated addresses produced by the processor 9 from three dimensions to two dimensions. This shows the x and z co-ordinates x&#39; and z&#39; respectively of an address calculated by the processor 9 (the y co-ordinate y&#39; not being visible on the drawing). The line 12 represents the position of the image plane (the viewing screen of the television receiver) on which the image is to be projected for viewing and D represents the viewing distance. The figure illustrates that to produce the two dimensional image on the image place, with correct perspective, the co-ordinate x&#39; has to be converted to x&#34; and the corresponding y&#39; co-ordinate similarly converted to y&#34;. The drawing shows that: ##EQU4## 
     The quotient z&#39;/D+1 is in fact produced directly in the processor 9 by pre-multiplying all the c co-efficients by 1/D and adding 1. Hence, referring to the equation of z i&#39;  above: ##EQU5## 
     In the processor 10, the quantity 1/z&#34; is derived using floating point arithmetic. The mantissa may be arranged to lie in the range of 0.5-1, and it is then possible to evaluate 1/z&#34; using the approximation : 
     
         1/z&#34;=2a-z&#34;a.sup.2 
    
     Where a is approximately the value of one divided by the top eight bits of z&#39;. 
     
         As z&#39;→0, z&#34;→1, x&#34;→x&#39; 
    
     
         As z&#39;→00, z&#34;→00, x&#34;→0 
    
     The manner in which the foregoing algorithms are applied is illustrated in FIGS. 4 and 5. According to FIG. 4 which illustrates the processor 9, the x,y and z address signals in the form of 16 bit words from the temporal interpolator 8 are fed to a buffer 20 and thence are read into a multiplying and accumulating circuit 21, in which are performed the evaluations of x&#39;, y&#39; and z&#34; referred to above. The twelve co-efficients required for each address evaluation are derived by the matrix multiplications previously referred to, which are carried out, as stated, in the computer 11 and delivered to a co-efficients RAM 22, from which they are applied, as 16 bit words to the circuit 21. The output signals from the circuit 21, are 24 bit words comprising of the three co-ordinates x&#39;, y&#39; and z&#34;. These signals are temporarily held in a buffer store 23 before being applied to a floating point converter 24 the output of which, for each co-ordinate of an address, comprises an exponent of five bits on the output 25 and a mantissa of 16 bit delivered on the output 26. 
     The second processing circuit 10, comprises, as shown in FIG. 5, a multiplier 30 and a look up table 31. The output 26 from FIG. 4, is applied in parallel to the multiplier 30 and the look up table 31. The look up table responds to the mantissa of each z co-ordinate to derive the mantissa of 1/z&#34; and applies this with multiplier 30, where it is multiplied by the corresponding x&#39; and y&#39; mantissae. The products are fed to a floating point converter 32. The respective exponents of each product, appearing on the output 25 of the processor 10, are added to the adder 33, the earlier exponent being delayed by latch 34 as required. The sum of exponents from the second input to the converter 32 and the 16 bit x&#34; and y&#34; outputs of the converter, with fixed point, is applied to a shift circuit 35. This receives post scroll signals from a generator 37 which in response to commands from the computer 11, moves the original of the co-ordinates from the centre of the image plane to the origin of the raster scan. 
     Reverting to FIG. 1, the output of the processor 10 comprises the two dimensional addresses to which pixels on the coarse address grid in the input raster should be transferred in the output raster; these addresses depend both on the shape and the movement to be imparted to the input image. These addresses are applied alternately to further shape stores 40 and 41, during alternate field periods and are read therefrom, also during alternate field periods but in inverse order. The read circuits of the stores 40 and 41 serve to retime the address signals into a sequence related to the order in which the addresses are required in an area calculating circuit 42, to facilitate the area calculations. 
     The retimed address signals are read to the said calculating circuit 42 which is arranged to calculate for each address the area of the meshes in the address grid at that address. In FIG. 6 a representative address for a given input pixel is x&#34;, y&#34; and the address for pixels above, to the right, below and to the left on the coarse address grid are x 1&#34; , y 1&#34; , x 2&#34; , y 2&#34; , x 3&#34; , y 3&#34; , and x 4&#34; , y 4&#34;  respectively. These four addresses derived from the store 40 and 41 are employed in the circuit 42 to calculate the mesh area at the address x, y using the following algorithm (omitting the primes for convenience) 
     
         Area (x.sub.2 +x.sub.1) (y.sub.2 -y.sub.1)+(x.sub.3 +x.sub.2) (y.sub.3 -y.sub.2)+(x.sub.4 +x.sub.3) (y.sub.4 -y.sub.3)+(x.sub.1 +x.sub.4) (y.sub.1 -y.sub.4) 
    
     The calculation is repeated for each &#34;coarse&#34; address, the figures from the stores 40 and 41 being read to the calculator 42 in the correct order to produce the required area calculations. It is to be noted that the area is a signed quantity. 
     The x and y components of the address signals from the stores 40 and 41 are fed to respective x and y interpolators 44 and 45 to produce for each pixel in the input signal raster respective x and y components of the address which the respective video signal should occupy in the output signal raster. The address is for pixels in odd and even numbered lines are produced during alternate field periods. The two interpolators are each similar to the interpolator described with reference to FIG. 8 of our co-pending Patent Application No. 8306789. Assume that an interpolated address for one pixel is x r  y r , as denoted in FIG. 7. As already indicated, this address will not in general coincide with the address of a pixel in the output raster but will lie within the rectangle defined by four pixel addresses, denoted in the representative case of FIG. 7 as x n , y n  ; x n+  1, y n  ; x n , y n+  1 and x n+  1, y n+  1. The interpolated address x r , y r  for each pixel is applied to a calculator 46 (FIG. 1 [part 2]) which may comprise a look up table, which produces, for each interpolated address, signals representing four neighbouring addresses as defined above and applies them as address signals to four frame stores 47 to 50. The calculator 46 also produces four fractional address signals which are applied to multiplying circuits 51 to 54 respectively. These fractional addresses are related to the area of overlap of a pixel at address x r , y r  on the pixels at the neighbouring address as shown in FIG. 7. These fractional address may be derived with the aid of a variety of interpolation functions, as will be known to persons skilled in the art. The area calculator 42, as aforesaid produces signals representing the mesh area at the coarse addresses as defined by the address signals from the stores 40 and 41. These signals are applied to an area interpolator 55 (FIG. 1 [part 1]) which is arranged to produce for each pixel in the input signal raster an interpolated signal called a density compensation co-efficient K. This signal is applied, for each pixel, by way of a connection 43 to a multiplying circuit 56. The area interpolator 55 also produces from the signals from the calculator 42, a signal which represents the sign of the mesh area for each pixel and this signal is applied via connection 43a to two input gates 57 and 58 to select for application to the multiplier 56 one or other of two sources 59 and 60 of input video signals, for a reason to be described subsequently. Assume, for the present, that say gate 57 is open and input video signals are received from the source 59 and applied to the multiplier 56. The video signal for each pixel multiplied by the co-efficient K, is applied in parallel to the four multiplying circuits 51 to 54, where it is multiplied by the fractional addresses. The resultant fractions of the video signal are then applied in the stores to the respective addresses x n , y n  ; x n+  1, y n  ; x n , y n+  1; and x n  +1, y n  +1, as indicated in FIG. 7, to produce the required spatial interpolation of the video signal. Write command signals for each pixel are applied to the four stores in parallel at the appropriate times by the computer 11. 
     As the writing of the input video signals in the store 47 to 50 continues through a frame period all the addresses in each of the stores will receive a fractional part (which may be 1 or 0 in some cases) of successive video signals. The same address in the four frame stores 47 to 50 will receive the interpolated fractions from four input pixels required to build up the output video signals at the respective address. The output signals are derived by applying sequential address signals and corresponding read command signals from the computer 11, by way of connection 62, to read the four fractional signals from successive identical addresses in the four frame stores. The four fractions are added in the adding circuit 63 to form the output video signal. It will be understood that reading occurs from one field of pixels in each frame store at the same time as writing occurs in the other field of pixels, the functions being alternated at field rate. The sequence of video signals read from the adding circuit 63 therefore represent the same image as the input video signals, but with a shape alteration determined by the address maps read from the store 1, and with such movement as may be introduced by the processors 7 and 10. The re-addressing of the video signals may cause the density of video signals applied to pixels in the output signal raster to vary as a function of the shape alterations or movements of the image. The multiplier 56, however, amplifies or attenuates the video signals in inverse proportion to the signal density to avoid undesired change in brightness over the image. 
     If the signal from the computer 11, representing the sign of the area derived by the calculator 42, changes sign, this indicates that the image changes from outside to the inside of a surface. For example, on rotating a hollow cylinder using the processors 9 and 10, different parts of the outside and inside surfaces of the cylinder may become visible as the rotation progresses. To deal with a situation such as this the sources 59 and 60 are arranged to provide video signals representing the outside surface and inside surface respectively, and the area-sign signals select the video signals for different pixels of the output raster, depending on the sign signal. 
     It will be understood that the invention may be realised in practice in many other ways than the example herein described with reference to the drawings.