Video scanning systems.

0001This invention relates to video scanning systems for use for example in television.

0002Transmission of images by television is conventionally performed by raster scanning in which a signal is formed by scanning the image in a series of parallel lines, either horizontal or vertical. In broadcast television the scan starts at the top left hand corner and finishes at the bottom right hand corner, the scan lines being horizontal. Moreover, each line is scanned in the same direction so that the scan must return to the beginning of each line in, ideally, an infinitessimally short time. Such an action is known as the flyback.

0003The scanning in conventional imaging and display devices is by way of a continuously moving electronic beam which is deflected by electric or, usually, magnetic fields. With such devices the beam flyback takes a finite time which is, therefore, an "overhead". The horizontal scanning waveform, which is proportional to the deflecting field, therefore appears as in Figure 1, the idealised version of which is known as a sawtooth waveform.

0004Similarly, the vertical scanning waveform needed to ensure the equal spacing of the scan lines is another sawtooth, though of much lower frequency. This has a corresponding flyback, imposing a further "overhead". It should be'noted that the continuous nature of the vertical scan imposes a continuous vertical displacement on the scan lines so that they are not strictly horizontal. However, the skew thus imposed is negligible.

0005The large rate of change of the flyback in the horizontal scan waveform is used to provide the high voltage needed in a conventional CRT display. However, it can cause problems if the line rate is increased to provide scanning for higher definition formats since the flyback time of conventional deflection circuits may become a significant proportion of the line period. For this reason, UK Patent Application 2,137,844A has proposed a boustrophedonic scanning format in which lines are alternately scanned in opposite directions. This requires a triangular form for the horizontal scan waveform as shown in Figure 2 (a). This eliminates the flyback, but the sawtooth of the vertical scan must now be modified to a stepped form as shown in Figure 2 (b) to ensure that adjacent lines are parallel. It also requires that non-linearities in the horizontal scan waveform result in a symmetrical function as shown in Figure 3.

0006A disadvantage of raster-based scanning is that it is committed to a standard in the form of lines in the picture. This means that once an image scanning standard is chosen the display must adopt the same standard, or convert the incoming signal to its own line standard, which is a complex and costly process. Moreover, any curtailment in the bandwidth of an analogue channel used to carry the signal will affect only the horizontal resolution of the image, not the vertical resolution. Excessive curtailment will therefore give an unacceptable image quality, inferior to that which could be obtained with equal horizontal and vertical resolutions.

0007The present invention is defined by the appended claims to which reference should now be made.

0008The invention is applicable to both analogue and digital scans. In the former case the image is scanned along a trace formed by a defined co-ordinate sequence, and in the latter case the pixels of the image are scanned in that co-ordinate sequence.

0009We have appreciated that it would be possible to have a scanning format which is not committed to a line standard and therefore is open to evolution, i.e., the image scanning may be upgraded in acuity without needing a change in the structure of the display. This means that it is downwards compatible. Moreover, it is possible for such a format to be upwards compatible such that the display can be upgraded without changing the source scanning format. Such a technique relies on the use of FRACTALS for defining the scanning locus.

0010Fractals may be described as structures whose length is undefinable or infinite as the finer the scale used to observe the structure, the greater the apparent length. An example of such a structure is a coastline. The closer it is observed, the greater its length becomes as finer detail becomes resolved.

0011Such self-similar shapes are neither one-nor two-dimensional shapes as they are defined by conventional Euclidian geometry. That is, they have a fractional dimension.

0012Fractals may be identical on each level or scale, or may be irregular. A coastline is an irregular fractal. Figure 4 shows how a regular fractal may be generated. This example is the well known Koch curve or Koch snowflake. The straight sides of an equilateral triangle Fig. 4b (the initiator shown in Figure 4a) are operated on by a generator shown in Figure 4a. This operation produces the result shown in Figure 4c. The operator is then applied to each of the sides of the shape of Figure 4c and then subsequently to the sides of the resultant figure, and so on. The result is a figure resembling a snowflake.

0013It can be shown that the fractal dimension can be defined as <ul id="ul0001" list-style="none"><li>D = - log (N)/Iog ( ^;)</li><li>where N is the number of parts of the objected generated and is the similarity ratio which is used to divide the initiator. For the Koch curve of Figure 4; N = 4 and + =</li><li>so that D = 1.26</li></ul>

0014A fuller description of fractals can be found in the book: Mandlebrot FRACTALS - Form, Chance and Dimension, W.H. Freeman, ISBN 0-7167-0473-0. The use of fractals in the field of computer graphics to simulate texture is well established. The use of a fractal curve to explore a multi-dimensional space is known from Stevens, R.J., Lehar, A.F. and Preston, F.H. 1982, "Data ordering and compression of multispectral images using the Peano scan", International Conference on electronic image processing 26-28 July 1982, IEE conference publication No. 214 pages 209-213. However, the use of a fractal curve to scan an image for transmission and display, with its attendant advantages is thought to be novel.

0015The invention will be disclosed in terms of a particular fractal -EI Peano curve, named after the Italian mathematician Guiseppe Peano, see "Selected works of Guiseppe Peano" translated and edited by Hubert C. Kennedy, ISBN 0-04-164002-0, Allen and Unwin. It is also called Hilbert curve. However, other forms of fractal may be more suitable, in particular the Sierpinski curve, described by Writh, N. in "Algorithms + data structures = programs", Prentice-Hall Inc., ISBN 0-13-022418-9 pages 134-137. In general, the curve may be multi-dimensional; only the two dimensional form is discussed in detail here.

0016The invention will be described by way of example with reference to the drawings, in which:- <ul id="ul0002" list-style="none"><li>Figure 1 (referred to above) illustrates the sawtooth waveform of conventional raster scanning;</li><li>Figure 2 (referred to above) shows the waveforms required for boustrophedonic scanning in (a) the horizontal (b) the vertical directions;</li><li>Figure 3 (referred to above) illustrates the permissible non-linearity of the horizontal scan in boustrophedonic scanning;</li><li>Figure 4 (referred to above) illustrates the steps in generating a Koch curve;</li><li>Figure 5 illustrates a fifth-order (32 x 32) Peano curve;</li><li>Figure 6 illustrates a first-order (basic) Peano curve;</li><li>Figure 7 illustrates a second-order Peano curve;</li><li>Figure 8 illustrates a third-order Peano curve;</li><li>Figure 9 shows the smoothed third-order curve resulting from band-limiting the coordinate waveforms fairly sharply to half the pixel frequency;</li><li>Figure 10 illustrates a portion of the horizontal and vertical waveforms interpolated by a raised cosine filter;</li><li>Figure 11 illustrates the effect of four-fold averaging and interpolation (filtering) of the scan;</li><li>Figure 12 illustrates the effect of two-fold averaging of the scan;</li><li>Figure 13 illustrates the effect of three-fold averaging of the scan;</li><li>Figure 14 illustrates the effect of 16-fold averaging of the scan;</li><li>Figure 15 illustrates the superposition of the third and fourth-order scans;</li><li>Figure 16 shows the starting and finishing points for various aspect ratios: (a) 2:1 (b) 3:1 (c) 4:1 (d) 3:2 (e) 4:3;</li><li>Figure 17 is a block diagram of a television system embodying the invention;</li><li>Figure 18 is a block diagram illustrating conversion for compatibility with the current technology; and</li><li>Figure 19 is a block diagram of a basic circuit for generating an n-th order scan.</li><li>Figure 5 shows a two-dimensional fifth-order Peano curve, i.e., a curve connecting an array of 32 x 32 points. Close inspection shows that it can be divided into quarters, each of which is connected by a single step. The quarters, in turn, can be further subdivided into quarters, again connected by only a single step, and so on. Further, the quarters are seen to be replicas, either directly or rotated through a right angle.</li><li>Figures 6, 7 and 8 show the first, second and third order curves respectively. It can be seen that each order is derived from the previous order according to simple geometrical rules. Alternatively, the derivation of each order can be considered by way of the Cartesian coordinate sequences as shown in the Appendix below. These sequences, when interpolated, are the waveforms that would need to be applied to the horizontal and vertical deflection circuits of a conventional camera tube or CRT display. Alternatively, they are the horizontal and vertical addressing sequences that would be needed for a discrete display device. The derivation process can be repeated indefinitely to yield higher and higher order curves connecting more and more points.</li></ul>

0017The Peano scan has three important properties relevant to scanned images:- <ul id="ul0003" list-style="none"><li>1. It gives a means of simultaneously altering the horizontal and vertical resolution of the image.</li><li>2. The set of curves for different orders form a hierarchical family capable of resolving finer and finer detail.</li><li>3. The curve for a particular order 'gracefully degrades' to the previous order when smoothed.</li></ul>

0018The first property arises because the signal obtained by scanning has information in the horizontal and vertical directions in alternating or near alternating fashion. As a result, if the bandwidth of the signal is limited by a bearer channel the resolution of the image is limited equally in both directions. This is the optimum way of using the available bandwidth.

0019The second property arises because each order is derived from the previous one and so creates compatibility. Taking a running average of four coordinate values and then selecting every fourth average produces the coordinate values of the previous order.

0020The third property is relevant only to continuous scanning devices such as those using electron beams. The curves in Figures 5 to 8 are idealised in the sense that, if the continuously moving scanning spot traces the curve at a constant speed, the x and y coordinate waveforms would be band-limited which would, in general, smooth the corners of the scan. Figure 9 shows the effect of limiting the bandwith of the waveforms using a particular filter characteristic which cuts at half the pixel frequency, that is the frequency at which x,y point co-ordinates are generated. This operation would be carried out by the filters following the digital-to-analogue converters generating the waveforms from the coordinate sequences.

0021There is, however one special case where limiting the bandwidth of the waveforms does not smooth the curve. This is the case of a simple raised-cosine filter pulse response, the base width of the pulse being the pixel spacing. Figure 10 shows a portion of the waveforms when so filtered. As can be seen, at the ideal point values, each coordinate has zero rate of change and neither overshoots. This means that the spot comes momentarily to rest and, as only one coordinate changes at any time, the motion passes smoothly from one coordinate to the other.

0022Figure 11 shows the result of smoothing the scan by taking a running average of four coordinate values and filtering with the first filter. As can be seen, the scan closely resembles that of the previous order except for slight overshoots. Figures 12 and 13 show the intermediate situations of two-and three-fold averaging and these clearly show how the scan gradually changes from one order to the next. The two-fold averager appears to join half the number of points, corresponding to a step of half an order. To obtain the next lowest order, appearing to join one sixteenth of the number of points, a 16-fold averaging is necessary, shown in Figure 14. This again closely resembles the ideal curve. Likewise, an eight-fold averager appears like the two-fold averager of Figure 12 but one order lower. Averaging by any amount in between corresponds to a curve with intermediate detail. As averaging is a form of low-pass filtering this means that gradually reducing the bandwidth of the coordinate functions causes the curve to gradually change from one order to the next, always retaining its fractal nature.

0023Given that either the video signal or the scan waveforms may be band-limited to an arbitrary degree, three cases arise at the display. These are: <ul id="ul0004" list-style="none"><li>1. The video and scan bandwidths are equal.</li><li>2. The video bandwidth is less than the scan bandwidth.</li><li>3. The video bandwidth is greater than the scan bandwidth.</li></ul>

0024The first case is straightforward in that there are as many independent video samples as there are points in the scan so that each point contributes maximally to the resolution. In the second case the video signal is not changing as fast as it can from point to point and so the resolution is limited by the signal. In the third case the source scan is assumed to be of a higer order than the display. In this case the display will average out of the signal by superposition, either exactly, if discrete, or approximately, if continuous. This can be appreciated by considering adjacent orders of scan. Figure 15 shows the superposition of third and fourth-order scans. As can be seen, the higher order scan is never more than half a pixel displaced from the lower order. Thus, four adjacent samples of a signal derived on the higher order, if displayed by a continuous scan on the lower order, will suffer no more than half a pixel displacement and so will tend to superpose.

0025This compatibility between different situations carries the important implication that it is not necessary to know the order of the scan in order to reproduce a version of the image. Thus we have an image transmission system which is independent of the number of pixels in the image. Only the number of fields per second, the form of the fractal (i.e., that it is a Peano curve) and the starting and finishing points need to be standardised.

0026Thus we have a hierarchical family of scanning standards for transmitting and displaying images such that an image scanned by one member of the family may be displayed by another member of the family without knowledge of the first member. Such an arrangement allows an evolution of scanning acuity to occur.

0027An apparent theoretical objection to the idea is that it can be applied only to square arrays of points. Arbitrary image aspect ratios are not possible. However, ratios of 2:1 3:1 4:1 3:2 and 4:3 are possible by starting and finishing at the points shown in Figure 16. Small deviations from these values are possible by altering the pixel. aspect ratio without departing significantly from the spirit of isotropic resolution.

0028Because the scan is contiguous there is no flyback except between fields and thus time is saved. Even field flybacks may be eliminated by using a modified square scan consisting of two 2:1 scans joined at their endpoints. Alternatively, a Sierpinski curve may be used which has an inherently endless form. In such a case, synchronising information would have to be sparse, compared with the present systems, possibly consisting of a recognisable framing pattern.

0029The system is particularly suitable for use with imaging and display devices which are based on discrete rather than continuous scanning. These include systems comprising cameras based on charge- coupled devices (CCDs) for example. Addressable display devices would be particularly suitable.

0030An outline block diagram of a television system embodying the invention is shown in Figure 17. Synchronised cameras operating with various orders of scan may be selected at will and their signals transmitted through the channel. The ninth-order scan camera represents, approximately, the current system. The eighth order scan camera represents, say, a low-resolution lightweight 'electronic journalism' camera whilst the 10th-order scan camera represents a high definition camera. They could be used in different programmes or even in the same programme. The llth-order scan camera represents a camera which could be developed in the future, being introduced when required. The same remarks apply to the hierarchy of displays, the eighth-order display representing, say, a wrist-watch receiver based on a liquid crystal display.

0031The system is capable of being introduced piecemeal and so thus coexisting with current scanning technology. If it were introduced on the channel then compatibility with current technology would require raster-to-Peano converters in conventional cameras and Peano-to-Raster converters in conventional displays, as shown in Figure 18, the converters merely re-ordering the sequence of incoming pixel values. Such converters would consist simply of a picture store which would write the pixel data in one sequence and read it in another. This re-ordering of data could also be regarded as a scrambling technique to prevent unauthorised reception of a newly-introduced service.

0032The scan could be generated using a memory addressed by a counter as shown in Figure 19. An nth order scan would require a memory of 2²ⁿlocations, each of 2n bits, containing n-bit x and y values and a 2n-bit memory counter able to count from 0 to 2² " -1. The contents of the memory could be derived according to the method described in the appendix below. The two outputs of the memory can be used directly to address a discrete scanning device. However, for a continuous scanning device the memory outputs need to be fed to two n-bit digital-to-analogue converters to produce continous wave forms.

DERIVATION OF THE SEQUENCES

0033The x and y coordinate sequences for the first order case of Figure 6 are shown in Table 1, in units of the scan step. The y sequence is a palindrome and the x sequence is a complementary palindrome. The coordinate sequences of the second-order case, written in binary form, are shown in Table 2. As there are 4 x 4 points, each coordinate requires 2 bits and there are 16 entries. The more significant bit is seen to be a replication of the corresponding first-order pattern, each entry being replicated four times. The less significant bit is seen to be the sequence YXX7 for the x coordinate or XYYX for the y coordinate where X and Y are the first-order patterns of the x and y coordinates. The first of these sequences is a complementary palindrome and the second is a palindrome. <tables id="tabl0001" num="0001"><img file="EP0253608A2_D0001.tif" /></tables><tables id="tabl0002" num="0002"><img file="EP0253608A2_D0002.tif" /></tables>

0034Development of the higher order cases proceeds along the same rules. The third-order case, shown in Table 3, has 64 entries of three bit values, the sequences of the first two bits of x and y being the same as those of the corresponding second-order case, each entry being replicated four times. The least significant bit of the x coordinate has the sequence XYYX YXX<o>Y</o> YXX Y <o>XYY</o> X where X and Y represent the same sequences as before. It can be seen that the initial sequence of each group of four follows the same pattern as the sequences in the first group. Likewise, the least significant bit of the y coordinate has the sequence YXXY XYYX XYYX <o>YXX</o> Y. It will be noted that the least significant bits are appropriately palindromic or complementary palindromic.

0035The rule for derivation of the higher order cases is therefore. <ul id="ul0005" list-style="none"><li>1. The sequences of all but the least significant bit are those of the previous order, each entry being replicated four times.</li><li>2. The sequence of the least significant bit consists of groups of four sub-sequences, each taking the form ABB A .</li><li>3. The first sub-sequence of the nth group of four is the same as the nth sub-sequence.</li><li>4. A can be X or Y or X or Y. If A is X then B is Y and vice versa.</li><li>5. The first sub-sequence of x is X if the order is odd and Y if it is even, and vice versa for y.</li><li>6. X and Y are the x and y sequences of the first order case.</li></ul>