Television Systems Transmitting Dither-Quantized Signals

The invention concerns television systems that transmit dither-quantized samples, including systems of the copending application Ser. No. 527,275, filed May 5, 1990 and of U.S. Pat. No. 4,758,893 as well as those of related prior art. The systems are improved by substituting novel multiphase dithers of the invention for previously known dithers. Rules sufficient for the construction of dithers of the invention are shown herein and examples, including preferred examples, are shown.

The improved dithers of the present invention comprise ordered-dither frame patterns and typically have sixteen or eight phases and sixteen sizes of dither. Whereas a first variety shifts a fixed pattern of dither sizes spatially relative to the TV picture but is not self-interpolating, a second variety is characteristically self-interpolating and the pattern of sizes may be reflected from frame to frame. Although methods and means of U.S. Pat. No. 4,758,893 are generally not convenient for generation of these varieties, convenient novel alternatives are disclosed herein. Self-interpolating dithers are especially useful in the systems of my copending application, Ser. No. 527,275.

FIG. 1 shows a set of nasik dither matrices defining a 16-phase dither that produces continuous size-tracks that are similar for all dither sizes.

FIG. 2 represents a portion of the tiled continuum formed by replicating a Type I nasik dither matrix horizontally and vertically. The size-0 tracks of two different dithers are shown thereon.

FIG. 3 shows a set of nasik dither matrices defining a self-interpolating 16-phase dither characterized by continuous size-tracks.

FIG. 4 is a table giving the logical binary sum of two numbers each between 0 and 15 inclusive.

FIG. 5 shows a set of nasik dither matrices corresponding to a preferred self-interpolating dither.

FIG. 6 shows schematically means using one frame pattern and a set of logical addends to generate a self-interpolating multiphase dither.

FIG. 7 is of the prior art and shows an exemplary system transmitting dither-quantized television signals.

FIG. 8 is a schematic drawing showing means for generating a dither having translated frame patterns.

Terminology used herein incorporates to applicable terminology of U.S. Pat. No. 4,758,893. The latter discloses use of various species of multi-phase dithers, each dither a signal comprising a one-dimensional stream of dither samples restricted Q sizes. The dither sizes are arranged in a repeating sequence, the sequence being divisible into p phases, each phase corresponding to a frame pattern.

The present invention improves various systems of prior art transmitting or recording analog or digital television signals that have been dither-quantized so that only quantum values of amplitude are sent. FIG. 7 (substantially the same as FIG. 1 of U.S. Pat. No. 4,652,905) exemplifies some of the prior-art systems to which the invention pertains. Luminance component Y', and chrominance components I' and Q' from matrix 2 are respectively dither-quantized in quantizers 3, 4 and 5 before transmission by communications means 7 to a TV receiver. Dither-quantizing includes combining a dither (e.g. DY) with a video component (e.g. Y') and quantizing the combined signal to a limited number of specified amplitude levels (as in producing Y). CLY is a strobe pulse.

All of the novel dithers disclosed herein comprise ordered-dither frame patterns. We conveniently specify a frame pattern by means of a dither matrix and specify a p-phase dither by means of an ordered set of p dither matrices. Successive matrix transformations change the arrangement of dither sizes on the matrix and hence change successive frame patterns.

Many of the dithers disclosed herein incorporate a 4.times.4 pandiagonal magic square (called a nasik) as the dither matrix and are referred to as nasik dithers. There are two main categories of 4.times.4 nasiks typified by

Logical addition of a constant addend to all elements of either of the above matrices interchanges rows and/or columns. The resultant transformation may include matrix reflection about horizontal and/or vertical axes as well as pattern shifts; however the matrix remains a pandiagonal magic-square of the same category. A multiphase dither realized in terms of one nasik category usually has an equivalent in terms of the other category. It is known that a nasik frame pattern can be oriented to avoid large-area flicker in TV systems having 2:1 interlaced scanning, while 90.degree. rotation from such orientation promotes flicker. Nasiks are therefore shown herein with suitable orientation for horizontal scanning with interlace, and the disclosed transformations avoid 90.degree. rotations.

The sixteen nasik matrices of FIG. 1 exemplify dithers of a first embodiment of the invention. The frame pattern merely shifts translationally from frame to frame so that all dither sizes maintain their relative positions; furthermore, the shifts are such that, each individual size moves horizontally, vertically or diagonally into a next-adjacent pels position of the TV raster during one change of frame and every pel receives all 16 dither sizes in the course of the 16-phase dither cycle. Micropatterns in the stipple that renders non-quantum shades of gray on the TV display are translated correspondingly from frame to frame.

FIG. 2 represents part of an indefinitely extended 2-dimensional array (continuum) on which the dither matrix for any particular frame of FIG. 1 is continually replicated horizontally and vertically. Whereas a one-dimensional sequence of dither samples is employed to dither-quantize a TV signal in the system of FIG. 7, it will be apparent to persons skilled in the art that, in order to generate a continuously translated dither like that of FIG. 1 for such a system, I may first store in addressable memory means a 2-dimensional array similar to FIG. 2 and larger than the TV frame in dimensions. For each phase of the dither, I may then scan sequentially the elements of a different subarray corresponding to a different one of the frame patterns, using a consistent scanning pattern. Assuming that scanning for Frame 1 commences with size 0, scanning for each subsequent frame commences at the next one of a series of index sizes that form a broken line connecting only horizontally, vertically, or diagonally adjacent elements of the stored array (e.g. line 1 of FIG. 2).

A translational multiphase dither is completely defined by the matrix for Frame #1 (a Type I nasik matrix in the case of FIG. 1) and a sequence of index sizes. The sequence of index sizes for FIG. 1 is as follows:

Whereas 16-phase dither is shown in FIG. 1, we can obtain 8-phase dither by returning to Frame 1 after Frame 8, or we could return after Frame 4 for 4-phase dithering. I have found, however, that sixteen phases generally insures better picture quality with very little additional cost in apparatus or complexity of operation.

Methods disclosed in U.S. Pat. No. 4,758,893 for using arithmetic addition, modulo a radix, to repeatedly transform a first frame pattern to produce the remaining frame patterns of a multiphase dither, are not convenient for generating the dithers exemplified in FIG. 1.

The dithers exemplified by FIG. 1 lack a desirable property, called herein self-interpolation, that is found in some prior-art dithers as well as other dithers disclosed hereinbelow. Wherever the intensity of an input component (e.g. Y', I' or Q' of FIG. 7) differs sufficiently from a quantum level of the associated quantizer, the corresponding dither-quantized signal of the invention (e.g. Y, I, or Q) alternates between two adjacent quantum levels, so that a pattern of dots, called stipple, is displayed by a a TV receiver. constant input over the entire display raster, dither quantizing with a uniform quantizer, and 16-phase dither. Then self-interpolation acts as follows: When the input signal exceeds a quantum level by half the quantizer step size (so that the stipple on any one frame comprises 50% lighter dots and 50% darker dots), the stipple patterns from any two successive TV frames (phases) interleave perfectly, so that every dot of the stipple becomes brighter exactly once and darker exactly once, corresponding to uniform average luminance; when the excess input is one-fourth the step size, the stipple patterns from any four successive frames interleave perfectly, every element becoming brighter once and darker three times, producing a uniform luminance when averaged over four frames; likewise, the stipple patterns produced from excess of one-eighth step interleave perfectly during eight successive frames, and excess of one-sixteenth step interleaves perfectly in the course of 16 frames.

My copending application, Ser. No. 527,275, discloses means whereby a video signal quantized with a self-interpolating dither can be requantized to approximate the same video originally quantized with a significantly larger number of quantum levels and multiphase dither. Even in the absence of such requantizing, self-interpolation tends to reduce the visibility of artifacts displayed on the TV receiver of FIG. 7.

Another embodiment of the invention employs a class of dithers exemplified in FIG. 3. These are self-interpolating dithers also characterized by movement of sizes on continuous tracks. The sizes do not shift in concert, however--some move in one direction as others move in other directions.

Referring to FIG. 3, Frame 1 is the same as Frame 1 of FIG. 1, but the subsequent frames are not merely shifted--the transformations involve transposition of adjacent pairs of rows and/or columns of the Frame 1 matrix, equivalent to reflection of the nasik continuum about horizontal and/or vertical axes.

A convenient method for construction of a self-interpolating 16-phase ordered dither is transformation of a first matrix into fifteen subsequent matrices by logical binary addition of the numbers 0 to 15, the order of said numbers (addends) conforming to rules disclosed hereinbelow. Each addend transforms every element of said first matrix. FIG. 4 shows a table (of prior art) for logical addition of two numbers from 0 to 15; it is derived by writing the augend and addend numbers in binary notation, adding binary digits without carries, and converting the result back to decimal form. Addition of the binary digits without carries is equivalent to EXCLUSIVE-OR combination of each pair of addend and augend digits that have equal binary weight.

The series of logical addends for FIG. 3 is

Because this series of addends happens to make a continuous track on the nasik continuum, the size-tracks are continuous. The addends track labelled 2 on FIG. 2 is also the track of size 0. Although the remaining sizes also follow continuous tracks, some sizes maintain a fixed position relative to 0 and other sizes (1, for example) move in contrary directions.

Another example of this kind of dither is specified by the Type II nasik, instead of Type I, and the following sequence of addends:

In similar fashion, a rectangular ordered-dither matrix of prior art, namely

together with the addends sequence

is sufficient for another self-interpolating dither with continuous size tracks.

Finally, the dither specified by the matrix

and the addends sequence

exemplifies self-interpolation with continuous size-tracks, all tracks being confined to one closed figure.

As mentioned previously, successive dither matrices corresponding to self-interpolating multi-phase dithers of the invention can be constructed by 1) selecting a first matrix, 2) choosing an ordered set of numbers (addends) according to certain rules, and 3) generating subsequent matrices by modifying said first matrix according to each consecutive addend in turn. Recalling that the elements of a matrix are numbers corresponding to dither sizes, a matrix is modified by replacing each matrix element by the logical binary sum of itself and the addend. For sixteen (or fewer) phases and sixteen (or fewer) sizes, FIG. 4 presents a table showing the logical binary sum of two numbers, each between 0 and 15 inclusive.

The following rules are sufficient for addends producing a 16-phase self-interpolating ordered dither: Let the letters

designate the required sequence of sixteen addends. Those skilled in the art will understand that the sequence repeats cyclically and that it may be read in reversed order. Then:

a) A=0, E=2, I=1, M=3

b) The set C,G,K,O corresponds to any consecutive set of four numbers, read either left-to-right or right-to-left, from the series 4,6,5,7,4,6,5,7.

c) Either Option 1 or Option 2 applies.

Option 1) The set B,F,J,N corresponds to any consecutive set of four numbers, read either way, from the series 8,10,9,11,8,10,9,11; and the set D,H,L,P is taken likewise from 12,14,13,15,12,14,13,15.

Option 2) The set D,H,L,P corresponds to any consecutive set of four numbers, read either way, from the series 8,10,9,11,8,10,9,11; and the set B,F,J,N is taken likewise from 12,14,13,15,12,14,13,15.

These rules insure that any 4.times.4 first matrix comprising sizes in the range 0 to 15 inclusive is transformed by the addends into an ordered series of matrices sufficient for a 16-phase self-interpolating dither.

Any consecutive set of eight from the set of sixteen addends is sufficient to provide an 8-phase self-interpolating dither and a consecutive set of four provides 4-phases.

Persons skilled in the art will understand that decimal notation is used to specify dither sizes and addends for convenience, and that specification and computation of dither sizes can also be done with equivalent binary or other-radix numbers without departing from the spirit of the invention. It will likewise be understood that, although the cyclic sequence of addends is conveniently written commencing with 0, the choice of first addend, corresponding to a first phase, is arbitrary inasmuch as the sequence of frame patterns repeats cyclically.

Dithers for a preferred embodiment of the invention are generated by the following sequence of logical addends:

This sequence can also be derived by writing the binary numbers from 0000 through 1111 in natural sequence, then reversing the order of bit positions before converting to decimal notation.

FIG. 5 shows such a dither with Type I nasik frame patterns. A related dither has the Type II nasik matrix, but nasik frame patterns are not essential for self-interpolation.

Frames 1 to 4 of FIG. 5 are also the frames of a 4-phase dither called 3-d nasik dither in U.S. Pat. No. 4,568,966 and related patents and first disclosed in U.S. Pat. No. 3,739,082. The latter patent discloses nasik dithers respectively corresponding to Frames #1 and #2, and Frames #1-#4, of FIG. 5 and states (col. 12, lines 36-41) that additional circuitry may provide "an even longer sequence of alternating dither patterns". Only nasik frame patterns are disclosed, whereas self-interpolating dithers of the present invention need not be nasik dithers and need not correspond to the canonical sequence of addends.

FIG. 6 shows exemplary means for producing a stream of dither samples corresponding to a self-interpolating multiphase ordered dither of the invention. The figure differs from FIG. 12 of U.S. Pat. No. 4,758,893 (not deemed practical for dithers of the invention) in that the latter shows transformation of a first frame pattern into other frame patterns by arithmetic addition modulo a radix, whereas FIG. 6 shows transformation by logical binary addition.

Referring to FIG. 6, double lines are used for connections transmitting digital signals and single lines for those transmitting analog or sync signals. Frame sync 17, lines sync 18 and pels clock 19 may be obtained from a TV scanning generator (not shown) in accordance with prior art. Ordered dither generator 20, of prior art, generates a stream of dither samples that corresponds to a first frame pattern and is repeated from frame to frame in synchronism with frame sync 17.

Counter 12 counts frame syncs (hence frames) modulo-16 and the count n goes to look-up table 26. An addend a.sub.n put out from table 26 is related to n according to the disclosed rules for addends producing self-interpolating 16-phase dithers.

Each dither sample z.sub.0 from generator 20 is operated upon with the current addend a.sub.n in means 21, which may operate with the function table of FIG. 4 or by equivalent means producing binary logical addition. When the numerical value of the addend is 0, z.sub.n from unit 21 is the same as z.sub.0 ; but at all other times, the sizes are rearranged as required for various frame patterns. Clock 19 insures that dither samples z.sub.0 from generator 20, and dither samples z.sub.n from means 21, are synchronous with sampling of pels on the TV raster.

FIG. 8 shows a means for generating multiphase dithers having translated frame patterns, wherein all sizes move in concert. Frames sync 17, lines sync 18, and pels clock 19 of FIG. 8 are similar to the corresponding units of FIG. 6 and double lines signify digital signal paths. Assuming that a 16-phase dither comprising 16 dither sizes is to be generated, frame counter 12 counts frames modulo 16 and corresponding to each frames count n, and Read Only Memory 53 (ROM 53), delivers two predetermined offset numbers, X.sub.n and Y.sub.n, each between 0 and 15, inclusive.

ROM 50 stores a predetermined pattern of dither samples having sizes from 0 to 15 inclusive on a 2-dimensional array corresponding to (x,y) addresses; the number of x-addresses is not less than the number of pels on a line of the TV frame plus the maximum x.sub.n, and the number of y-addresses is not less than the number of lines on the frame plus the maximum y.sub.n.

Frame scanner 51 and the array on ROM 50 are so arranged that, when x.sub.n and y.sub.n are both zero, the addresses (x.sub.t, y.sub.t) are scanned to emulate raster scanning of the TV frame for successive values of the pels count t; the scanned elements of the 2-dimensional array correspond to a particular frame pattern of the dither coextensive with the TV frame, and the one-dimensional output z.sub.t from ROM 50 corresponds to one phase of the dither.

It will be obvious to persons skilled in the art that, inasmuch as the array stored in 50 is sufficiently larger than the frame, other frame patterns (obtained with at least one non-zero offset) will be laterally, vertically or diagonally displaced from said particular pattern according to the offset values, and the one-dimensional dither is modified accordingly from phase to phase.

Ordered dither frame patterns are generated when the oversize array stored in 50 is ordered (like FIG. 2) and continuous size paths occur when the successive offset pairs are arranged suitably in ROM 53. Specifically, the 16 successive offset pairs should correspond to the different elements of a 4.times.4 array, and successive pairs should be adjacent.

It will be obvious to persons skilled in the art that I may employ the means of FIG. 8 to generate a set of dither matrices such the matrices of FIG. 3 or FIG. 5 in a manner analogous to the generation of frame patterns.

Persons skilled in the art will understand that FIG. 6 is exemplary and that, within the spirit of the invention, equivalent means can be used to produce specific dithers having the same structures as would be produced by the means of FIG. 6. Furthermore, it will be recognized that a dither of the invention (or iteraled portions thereof) may conveniently be recorded in a memory device, so that the stream of dither samples required by a TV transmitter of the invention is obtained in practice by readout from memory.

Whereas sequences of addend or track positions have been written as simple series, it should be understood that any such series repeats continually to provide a continuous stream of dither samples comprising cyclically repeating phases.

Any continuous subsequence of eight addends extracted from the cycle of sixteen addends defining a 16-phase self-interpolating dither is sufficient for a new addends cycle which defines an 8-phase dither that is self-interpolating for sequences of two, four and eight frames.

Obtain a sequence of addends by reading Array A or an equivalent array, either left to right and top to bottom or right to left and top to bottom. It will be apparent that reading all such arrays, in both directions of line scan, is sufficient to provide the same totality of cyclic sequences as the rules disclosed above.

While I have disclosed the invention in terms of specific embodiments, other, equivalent embodiments will no doubt be obvious to persons having normal skill in the art and it is intended that the invention be construed to include all such equivalent modifications. For example, although I have explained and exemplfied the invention by means of particular ordered dithers based on 4.times.4 dither matrices and sixteen, eight or four phases, design parameters that correspond to integral powers of the number 2, the persons skilled in the art will understand that I may provide equivalent dithers correspondingly related to 3, 5 or another number.