Digital video effects with image mapping on to curved surface

• US 5,293,233 A
• Filed: 07/10/1992
• Issued: 03/08/1994
• Est. Priority Date: 01/12/1990
• Status: Expired due to Fees

• Current Assignee: Questech Corporation
• Original Assignee: Questech Corporation
• Inventors: Barton, Nicholas, Billing, Robert
• Primary Examiner(s): Powell, Mark R.
• Application Number:
  US07/890,597
• Time in Patent Office: 606 Days
• Field of Search: 395/125, 395/119, 358/160, 358/182, 358/183
• US Class Current: 348/581
• CPC Class Codes: G06T 3/4007 based on interpolation, e.g. bilinear interpolation image demosaicing G06T3/4015; edge-driven or edge-based scaling G06T3/403

Abstract

In a digital video effects system having a store (8) wherein coordinate values are stored in curved order by addressing the store with coordinate values transformed by a function generator (1) and transformer (2) and storing linear values derived from counters (6), the resolution of incremental values from the transformer (2) is increased as necessary to avoid unwritten addresses in the store by providing, between the transformer (2) and the store (8), delay means (3) for providing coordinates of the corners of adjacent quadrilateral areas defined by integer values of the transformed coordinates, a "predisector" (4) for providing coordinates of smaller quadrilateral areas into which the first areas can be divided, and a "hole filler" (5) for generating intermediate coordinate values failing within each smaller quadrilateral. An interpolator (7) serves to provide intermediate data values derived from the linear values to match the intermediate coordinate values generated by the hole filler.

Claims

1. A process for deriving from a set of two dimensional co-ordinate signals that have been transformed according to curved functions in order to represent, relative to a video image, frame positions to be occupied by an image of a curved surface, intermediate values of the transformed coordinate signals to a resolution which is greater than that provided by said set, the method comprising the steps of:

a) providing within a memory store a look up table containing for each of a given number of two dimensional geometric figures within a given range of sizes a corresponding distribution of values of co-ordinate positions within each figure, such that the stored distributions collectively include substantially all possible distributions of such values that can occur within a given incremental area or range of areas of the image frame;

b) processing a set of said transformed co-ordinate signals to derive a plurality of subsets thereof, each of which includes a plurality of signals defining immediately adjacent co-ordinate positions at the corners of an area of the image frame of a given geometric shape;

c) processing at least some of said subsets of co-ordinate signals to derive a plurality of sets of further signals each defining an area of geometric shape and size corresponding to that of one of the geometric figures of the look up table, such that the respective areas defined by said sets of further signals collectively make up the whole area defined by the originating subset;

d) addressing said memory store with the sets of further signals to retrieve for each area defined thereby a correspondingly stored distribution of co-ordinate values occurring therein; and

e) combining the retrieved co-ordinate values with value derived from the set of transformed signals to provide a composite set of signals representing a continuous array of transformed co-ordinate positions having a predetermined maximum incremental spacing.

2. A process according to claim 1, wherein the said two dimensional geometric figures for which distributions of values of co-ordinate positions are stored in said look up table are triangles.

3. A process according to claim 2, wherein the said subsets of signals derived from the set of transformed signals are subsets of four signals representing immediately adjacent co-ordinates in the horizontal and vertical directions of the image frame that collectively define the corners of a quadrilateral area, and wherein at least some of said subsets of four signals are each processed to derive, for each quadrilateral area exceeding a given size, a plurality of further sets of co-ordinate signals corresponding to the co-ordinates of a plurality of smaller quadrilateral areas into which the first quadrilateral area can be subdivided, said smaller quadrilateral areas each lying within predetermined limits of size.

4. A process according to claim 3, wherein each of the sets of further signals is derived by processing the co-ordinate signals defining one of said quadrilateral areas or one of said smaller quadrilateral areas to obtain vector signals corresponding to two sides of each of leading and trailing triangular areas into which the quadrilateral are is divided diagonally.

5. A process according to claim 1, wherein the co-ordinate positions defined by each subset of signals are logically compared to a co-ordinate area of the image frame to detect any such set of signals for which the corresponding geometric area lies wholly outside the co-ordinate area of the image frame, and processing is terminated in respect of any subset of signals so detected.

6. A data processing device for deriving from a set of two dimensional co-ordinate signals that have been transformed according to curved functions in order to represent, relative to a video image, frame positions to be occupied by an image of a curved surface, intermediate values of the transformed co-ordinate signals to a resolution which is greater than that provided by said set, the data processing device comprising:

means for processing said set of transformed co-ordinate signals to derive therefrom a plurality of subsets of said signals each of which subsets includes a plurality of signals defining immediately adjacent co-ordinate positions at the corners of a given geometrical area of a digital video image, and means for processing at least some of said subsets of signals to derive, for each of said geometric areas exceeding a given size, a plurality of further sets of co-ordinate signals corresponding to the co-ordinates of a plurality of smaller geometric areas of similar shape into which the first area can be subdivided, said smaller areas each lying within predetermined limits of size.

7. A device according to claim 6, wherein said subsets each comprise four signals defining the corners of a quadrilateral area.

8. A device according to claim 7, wherein said means for processing said set of co-ordinate signals comprises delay means for receiving a set of co-ordinate signals provided serially in the form of a digital video signal, and for providing at respective outputs signals delayed relatively to one another by the period of one pixel in the horizontal direction and one line in the vertical direction, whereby said respective outputs provide said plurality of subsets of signals consecutively in synchronism with the received signal.

9. A device according to claim 7, wherein said means for processing said subsets of signals comprises means for subtracting respective signals of each subset to determine the values of the horizontal and vertical components of the vectors of the respective sides of the corresponding quadrilateral area, means for comparing said values in order to determine a number of sections into which said quadrilateral area may be divided in horizontal and vertical directions in order that the magnitude of each section in the horizontal and vertical directions shall lie between predetermined limits and for providing a corresponding output signal, means responsive to said output signal for providing, consecutively, output signals representative of the corresponding fractional division of said vector components of the quadrilateral area by the respective sides of smaller quadrilateral areas into which it is to be divided, and means for computing from said vector components and said output signals, the respective co-ordinates of the corners of each said smaller quadrilateral area.

10. A data processing device for deriving from a set of two dimensional co-ordinate signals that have been transformed according to curved functions in order to represent, relative to a video image, frame positions to be occupied by an image of a curved surface, intermediate values of the transformed co-ordinate signals to a resolution which is greater than that provided by said set, the data processing device comprising:

a memory store including a look up table containing for each of a finite number of two dimensional geometric figures within a given range of sizes a corresponding distribution of values of co-ordinate positions within the figure, said values being determined in accordance with vectors of corresponding liner sides of each figure, such that the stored distributions collectively include substantially all possible distributions of such values that can occur within a given incremental area of a digital video image frame;

means for processing co-ordinate signals representing the corners of a geometric area of a video image frame to derive therefrom respective sets of further signals each defining a geometric figure corresponding to one of the geometric figurers of the look up table;

means for addressing said memory store with said sets of further signals to retrieve the correspondingly stored distributions of values, and means for generating from said co-ordinate signals and said distributions of values a continuous array of co-ordinate values extending within said geometric area.

11. A data processing device according to claim 10, wherein said two dimensional geometric figures are triangles and said geometric area is a quadrilateral.

12. A data processing device for deriving from a set of two dimensional co-ordinate signals that have been transformed according to curved functions in order to represent, relative to a video image, frame positions to be occupied by an image of a curved surface, intermediate values of the transformed co-ordinate signals to a resolution which is greater than that provided by said set, the data processing device comprising:

transformed co-ordinate signal processing means for processing said set of transferred co-ordinate signals to derive therefrom a plurality of subsets of said signals each of which subsets includes a plurality of signals defining immediately adjacent co-ordinate positions at the corners of a given geometric area of a digital video image, and means for processing at least some of said subsets exceeding a given size, a plurality of further sets of co-ordinate signals corresponding to the co-ordinates of a plurality of smaller geometric areas of similar shape into which the first area can be subdivided, said smaller areas each lying within predetermined limits of size;

a memory store including a look up table containing for each of a finite number of two dimensional geometric figures within a given range of sizes a corresponding distribution of values of co-ordinate positions within the figure, said values being determined in accordance with vectors of corresponding linear sides of each figure, such that the stored distributions collectively include substantially all possible distributions of such values that can occur within a given incremental area of a digital video image frame;

means for processing co-ordinate signals representing the corners of a geometric area of a video image frame to derive therefrom respective sets of further signals each defining a geometric figure corresponding to one of the geometric figures of the look up table;

means for addressing said memory store with said sets of further signals to retrieve the correspondingly stored distribution of values, and means for providing from said co-ordinate signals and said distributions of values of continuous array of co-ordinate values extending within said geometric area, wherein the further sets of co-ordinate signals of said transformed co-ordinate signal processing means are provided to the memory store as said co-ordinate signals, and wherein the means for processing said subsets of signals is further arranged to provide to said means for processing said further sets of control signals for avoiding redundancy in the retrieval of stored values corresponding to matching boundaries of adjacent ones of said smaller geometric areas.

13. A data processing device for deriving from a set of two dimensional co-ordinate signals that have been transformed according to curved functions in order to represent, relative to a video image, frame positions to be occupied by an image of a curved surface, intermediate values of the transformed co-ordinate signals to a resolution which is greater than that provided by said set, the data processing device comprising:

a) means for processing said set of transformed co-ordinate signals to derive therefrom a plurality of subsets of said signals defining immediately adjacent co-ordinate positions at the corners of a given geometric area of a digital video image;

b) means for comparing said subsets of signals with respective boundaries of a predetermined image frame, in order to provide output signals determining the presence or absence of each corresponding co-ordinate position within said image frame in a given co-ordinate direction, and means for logically combining said output signals to provide a corresponding control signal only when said geometric area lies wholly outside said predetermined image frame; and

c) means for processing said subsets of signals to derive, for each said geometric area exceeding a given size, a plurality of further sets of co-ordinate signals corresponding to the co-ordinates of a plurality of smaller geometric areas of similar shape into which the first area can be subdivided, said smaller areas each lying within predetermined limits of size;

said means for processing said subsets of signals being inhibited in response to said control signal.

14. A data processing device for enabling stored video images to be processed to reproduce image information from one image frame of a video signal so that it appears within another image frame of a video signal as if transposed onto a curved surface, the data processing device comprising:

means for generating a first set of co-ordinate signals the values of which represent the co-ordinate positions of image information within a store containing the picture information of said one image frame;

means for transforming the values of said first set of co-ordinate signals according to functions defining the desired curved surface in order to derive a second set of co-ordinate signals the values of which represent the co-ordinate positions within said other image frame at which the said curved surface will appear;

means for processing said second set of co-ordinate signals to derive therefrom a plurality of subsets of said signals each of which subsets includes a plurality of signals defining immediately adjacent co-ordinate positions at the corners of a given geometric area of a digital video image;

subset processing means for processing at least some of said subsets of signals to derive, for each said geometric area exceeding a given size, a plurality of further sets of co-ordinate signals corresponding to the co-ordinates of a plurality of smaller geometric areas of similar shape into which the first area can be subdivided, said smaller areas each lying within predetermined limits of size, said subset processing means comprising;

a memory store including a look up table containing for each of a finite number of two dimensional geometric figures within a given range of sizes a corresponding distribution of values of co-ordinate positions within the figure, said values being determined in accordance with vectors of corresponding linear sides of each figure, such that the stored distributions collectively include substantially all possible distributions of such values that can occur within a given incremental area of a digital video image frame;

means for addressing said memory store with said subsets of signals to retrieve the correspondingly stored distributions of values as said further sets of co-ordinate signals;

means for generating from said second set of co-ordinate signals and said further sets of co-ordinate signals output signals comprising a continuous array of co-ordinate values extending within said geometric area;

a data store, means for addressing said data store with the said output signals of the said subset processing means and means for writing into said data store values derived from said first set of co-ordinate signals whereby at each co-ordinate address of the store defined by said out signals there are stored corresponding values of input co-ordinates.

15. A data processing device for enabling stored video images to be processed to reproduce image information from one image frame of a video signal so that it appears within another image frame of a video signal as if transposed onto a curved surface, the data processing device comprising:

means for generating a first set of co-ordinate signals the values of which represent the co-ordinate positions of image information within a store containing the picture information of said one image frame;

means for transforming the values of said first set of co-ordinate signals according to functions defining the desired curved surface in order to derive a second set of co-ordinate signals the values of which represent the co-ordinate positions within said other image frame at which the said curved surface will appear;

means for processing said second set of co-ordinate signals to derive therefrom a plurality of subsets of said signals each of which subsets includes a plurality of signals defining immediately adjacent co-ordinate positions at the corners of a given geometric area of a digital video image;

subset processing means for processing at least some of said subsets of signals to derive, for each said geometric area exceeding a given size, a plurality of further sets of co-ordinate signals corresponding to the co-ordinates of a plurality of smaller geometric areas of similar shape into which the first area can be subdivided, said smaller areas each lying within predetermined limits of size, said subset processing means comprising;

a memory store including a look up table containing for each of a finite number of two dimensional geometric figures within a given range of sizes a corresponding distribution of values of co-ordinate positions within the figure, said values being determined in accordance with vectors of corresponding linear sides of each figure, such that the stored distributions collectively include substantially all possible distributions of such values that can occur within a given incremental area of a digital video image frame; and

means for addressing said memory store with said subsets of signals to retrieve the correspondingly stored distributions of values as said further sets of co-ordinate signals;

means for providing from said second set of co-ordinate signals output signals comprising a continuous array of co-ordinate values extending within said geometric area;

a data store, means for addressing said data store with the said output signals of the said subset processing means, and means for writing into said data store values derived from said first set of co-ordinate signals whereby at each co-ordinate address of the store defined by said output signals there are stored corresponding values of input co-ordinates;

said writing means comprising an interpolator arranged to receive fractional values of said first set of co-ordinate signals together with the said output signals of said subset processing means and to compute said derived values to be written to the data store.

16. A data processing device for enabling stored video images to be processed to reproduce image information from one image frame of a video signal so that it appears within another image frame of a video signal as if transposed onto a curved surface, the data process device comprising:

means for generating a first set of co-ordinate signals the values of which represent the co-ordinate positions of image information within a store containing the picture information of said one image frame;

means for transforming the values of said first set of co-ordinate signals according to functions defining a desired curved surface in order to derive a second set of co-ordinate signals the values of which represent the co-ordinate positions within said other image frame at which the said curved surface will appear;

means for processing said second set of co-ordinate signals to derive therefrom a plurality of subsets of said signals each of which subsets includes a plurality of signals defining immediately adjacent co-ordinate positions at the corners of a given geometric area of a digital video image;

subset processing means for processing at least some of said subsets of signals to derive, for each of said geometric areas exceeding a given size, a plurality of further sets of co-ordinate signals corresponding to the co-ordinates of a plurality of smaller geometric areas of similar shape into which the first area can be subdivided, said smaller areas each lying within predetermined limits of size, said subset processing means comprising a memory store including a look up table containing for each of a finite number of two dimensional geometric figures within a given range of sizes a corresponding distribution of values of co-ordinate positions within the figure, said values being determined in accordance with vectors of corresponding linear sides of each figure, such that the stored distributions collectively include substantially all possible distributions of such values that can occur within a given incremental area of a digital video image frame; and

means for addressing said memory store with said subsets of signals to retrieve the correspondingly stored distributions of values as said further sets of co-ordinate signals;

means for generating from said second set of co-ordinate signals and said further sets of co-ordinate signals output signals comprising a continuous array of co-ordinate values extending within said geometric area;

a data store;

means for addressing said data store with said output signals of said subset processing means; and

writing means for writing into said data store values derived from said first set of co-ordinate signals whereby at each co-ordinate address of the store defined by said output signals of the subset processing means there are stored corresponding values of input co-ordinates, said writing means including means for comparing said output signals of the subset processing with manually adjustable horizontal and vertical, high and low co-ordinate limits to produce an enable signal whereby said enable signal is false outside said limits, and means for suppressing said writing means when said enable signals is false.

17. A data processing device for enabling stored video images to be processed to reproduce image information from one image frame of a video signal so that it appears within another image frame of a video signal as if transposed onto a curved surface, the data processing device comprising:

means for generating a first set of co-ordinate signals the values of which represent the co-ordinate positions of image information within a store containing the picture information of said one image frame;

means for transforming the values of said first set of co-ordinate signals according to functions defining a desired curved surface in order to derive a second set of co-ordinate signals the values of which represent the co-ordinate positions within said other image frame at which the said curved surface will appear;

means for processing said second set of co-ordinate signals to derive therefrom a plurality of subsets of said signals each of which subsets includes a plurality of signals defining immediately adjacent co-ordinate positions at the corners of a given geometric area of a digital video image;

subset processing means for processing at least some of said subsets of signals to derive, for each said geometric area exceeding a given size, a plurality of further sets of co-ordinate signals corresponding to the co-ordinates of a plurality of smaller geometric areas of similar shape into which the first area can be subdivided, said smaller areas each lying within predetermined limits of size;

means for generating from said second set of co-ordinate signals and said further sets of co-ordinate signals output signals comprising a continuous array of co-ordinate values extending within said geometric area;

a data store;

means for addressing said data store with output signals of said subset processing means; and

writing means for writing into said data store values derived from said first set of co-ordinate signals whereby at each co-ordinate address of the store defined by said output signals of the subset processing means there are stored corresponding values of input co-ordinates;

said writing means comprising;

means for processing said subsets of signals defining immediately adjacent co-ordinate positions at the corners of a given geometric area to obtain a corresponding inverse determinant signal therefrom;

means for deriving from said subsets of signals, signals representing components of vectors defining the sides of said geometric area;

further means for processing said subsets of signals in conjunction with said output signals of said subset processing means to obtain component signals of a further vector having its ends defined by said output signals and said subsets of signals;

transformation means for obtaining in respect of said other image frame, component signals of said further vector, including multiplication means for multiplying said signals with said geometric area vector component signals and said inverse determinant signal; and

addition means for adding said other image frame component signal to said first set of co-ordinate signals whereby the summed signals represent the values to be written to the said data store.