US5058158A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Video scrambling apparatus and method based on space filling curves
Assignee: Individual
•
Filing: 1990-03-19
•
Granted: 1991-10-15
•
Expires: 2010-03-19
Abstract
Abstract A method of encrypting a video signal employing a pseudorandom Space Filling Curve having a highly irregular scanning pattern for scanning the pixel addresses of a video picture stored in a frame buffer. The method is used with a video scrambler/descrambler device and is characterized by a much higher cryptographic strength than existing techniques, which is not subject to simple correlation attacks by comparing and matching of line portions. In addition, the method features a reduction in the video signal bandwidth for typical pictures.
Inventors
- 👤 Yossi Matias
- 👤 Adi Shamir
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 16:50
CPC Classifications
H; H04; H04N; H04N7/00; H04N7/16; H04N7/167; H04N7/169; H04N7/1696
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
100 words
A method of encoding a video signal comprising the steps of: storing in the locations of a frame buffer the pixel values of a group of video information lines representing at least a portion of a video picture container in the video signal; defining a pseudo-random Space Filling Curve (SFC) providing a sequence corresponding to locations of the frame buffer mapping random directions of movement between adjacent pixels of the video picture portion; and addressing the locations of the frame buffer in accordance with the defined sequence to read the pixel values thereof for encoded transmission of the video signal.
Claim 2
Independent Claim
100 words
A method of encoding a video signal comprising the steps of: storing in the locations of a frame buffer the pixel values of a group of video information lines representing at least a portion of a video picture container in the video signal; defining a pseudo-random Space Filling Curve (SFC) providing a sequence corresponding to locations of the frame buffer mapping random directions of movement between adjacent pixels of the video picture portion; and addressing the locations of the frame buffer in accordance with the defined sequence to read the pixel values thereof for encoded transmission of the video signal.
Claim 3
Dependent Claim
29 words
The method of claim 1, wherein the frame buffer forms an element of a video encoder which generates the SFC and addresses the frame buffer location in accordance therewith.
Claim 4
Dependent Claim
80 words
The method of claim 2, wherein the encoding provided by the video encoder in the transmission of the video signal is decoded by a decoder by use of a shared key stream between the encoder and decoder, such that the latter generates the same pseudo-random SFC as is used in the encoder, thereby providing it with the correct sequence with which to write the video signal into the locations of a frame buffer included therein for restoring the original signal.
Claim 5
Dependent Claim
84 words
The method of claim 2, wherein the encoding provided by the video encoder in the transmission of the of the video signal is decoded by a decoder which as stored therein a plurality of SFC's from which a selection is made in accordance with a signal indicating the SFC being used in the encoder, thereby providing the decoder with the correct sequence with which to write the video signal into the locations of a frame buffer included therein for restoring the original video signal.
Claim 6
Dependent Claim
61 words
The method of claim 2, wherein the SFC used for encoding in the video encoder is included in the transmission of the video signal for use by a decoder, such that the latter is provided with the correct sequence with which to write the video signal into the locations of a frame buffer included therein, for restoring the original video signal.
Claim 7
Dependent Claim
60 words
The method of claim 2, wherein the pseudo-random SFC is generated by execution of an algorithm whose output domain is a family of the pseudo-random SFC's in the rectangular grid graph provided by the encoder frame buffer, with the SFC being chosen from the family and used to define the sequence in which the encoder frame buffer addresses are read.
Claim 8
Dependent Claim
27 words
The method of claim 6, wherein after a predetermined period of time, the original SFC is replaced by another SFC from the family of the pseudo-random SFC's.
Claim 9
Dependent Claim
23 words
The method of claim 1, wherein the SFC visits substantially all of the pixels in the portion of the video picture exactly once.
Claim 10
Dependent Claim
26 words
The method of claim 1, wherein the SFC visits substantially all of the pixels in the portion of the video picture by movement between adjacent pixels.
Claim 11
Dependent Claim
35 words
The method of claim 1, wherein the SFC is substantially a Hamiltonian path which visits substantially all of the pixels in the portion of the video picture exactly once and by movement between adjacent pixels.
Claim 12
Dependent Claim
33 words
The method of claim 1, wherein the SFC provides mapping of at least two of vertical, horizontal and diagonal random directions of movement between substantially all adjacent pixels of the video picture portion.
Claim 13
Dependent Claim
27 words
The method of claim 1, wherein the bandwidth of the video signal is reduced and the SFC preserves the correlation between adjacent pixels of the video picture.
Claim 14
Dependent Claim
39 words
The method of claim 1, wherein the SFC is applied to a sequence of consecutive frames in the video picture, providing a three-dimensional sequence of possible frame buffer locations within a cubic grid built by the consecutive video frames.
Claim 15
Dependent Claim
10 words
A video encoding system incorporating the method of claim 1.
Claim 16
Independent Claim
124 words
A method for decoding a video signal, the video signal having been encoded as a sequence of pixel values from a group of video information lines representing at least a portion of a video picture represented by the video signal, the sequence being ordered according to a pseudo-random Space Filling Curve (SFC), wherein neighboring pixels of the sequence are mapped from random directions of movement between adjacent pixels of the video picture portion, the method comprising the steps of: (a) addressing the locations of a frame buffer in accordance with the order of the SFC; (b) storing the pixel values in the frame buffer in accordance with the addressed locations; and (c) sequentially reading the pixel values from neighboring addresses of the frame buffer.
Claim 17
Independent Claim
124 words
A method for decoding a video signal, the video signal having been encoded as a sequence of pixel values from a group of video information lines representing at least a portion of a video picture represented by the video signal, the sequence being ordered according to a pseudo-random Space Filling Curve (SFC), wherein neighboring pixels of the sequence are mapped from random directions of movement between adjacent pixels of the video picture portion, the method comprising the steps of: (a) addressing the locations of a frame buffer in accordance with the order of the SFC; (b) storing the pixel values in the frame buffer in accordance with the addressed locations; and (c) sequentially reading the pixel values from neighboring addresses of the frame buffer.
Claim 18
Dependent Claim
81 words
The method of claim 15, wherein the encoding provided by the video encoder in the transmission of the video signal is decoded by a decoder by use of a shared key stream between the encoder and decoder, such that the latter generates the same psuedo-random SFC as is used in the encoder, thereby providing the decoder with the correct sequence with which to write the video signal into the locations of the decoder frame buffer for restoring the original video signal.
Claim 19
Dependent Claim
81 words
The method of claim 15, wherein the encoding provided by the video encoder in the transmission of the video signal is decoded by a decoder which as stored therein a plurality of SFC's from which a selection is made in accordance with a signal indicating the SFC being used in the encoder, thereby providing the decoder with the correct sequence with which to write the video signal into the locations of the decoder frame buffer for restoring the original video signal.
Claim 20
Dependent Claim
60 words
The method of claim 15, wherein the SFC used for encoding in the video encoder is included with the transmission of the video signal for use by a decoder, such that the latter is provided with the correct sequence with which to write the video signal into the locations of the decoder frame buffer for restoring the original video signal.
Claim 21
Dependent Claim
23 words
The method of claim 15, wherein the SFC visits substantially all of the pixels in the portion of the video picture exactly once.
Claim 22
Dependent Claim
26 words
The method of claim 15, wherein the SFC visits substantially all of the pixels in the portion of the video picture by movement between adjacent pixels.
Claim 23
Dependent Claim
35 words
The method of claim 15, wherein the SFC is substantially a Hamiltonian path which visits substantially all of the pixels in the portion of the video picture exactly once and by movement between adjacent pixels.
Claim 24
Dependent Claim
62 words
The method of claim 21, wherein the pseudo-random SFC is generated by execution of an algorithm whose output domain is a family of the Hamiltonian paths in the rectangular grid graph provided by an encoder frame buffer, with the SFC being chosen from the Hamiltonian path family and used for defining the sequence in which the encoder frame buffer addresses are read.
Claim 25
Dependent Claim
24 words
The method of claim 22, wherein after a predetermined period of time, the original SFC is replaced by another SFC from the Hamiltonian family.
Claim 26
Dependent Claim
33 words
The method of claim 15, wherein the SFC provides mapping of at least two of vertical, horizontal and diagonal random directions of movement between substantially all adjacent pixels of the video picture portion.
Claim 27
Dependent Claim
81 words
The method of claim 24, wherein the encoding provided by said video encoder in the transmission of the video signal is decoded by a decoder by use of a shared key stream between the encoder and decoder, such that the latter generates the same pseudo-random SFC as is used in the encoder, thereby providing the decoder with the correct sequence with which to write the video signal into the locations of the decoder frame buffer for restoring the original video signal.
Claim 28
Dependent Claim
40 words
The method of claim 15, wherein the SFC is applied to a sequence of consecutive frames in the video picture, providing a three-dimensional sequence of possible decoder frame buffer locations within a cubic grid built by the consecutive video frames.
Claim 29
Dependent Claim
10 words
A video decoding system incorporating the method of claim 15.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-10-14 | 1995-04-15 | 1995-10-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-10-14 | 1999-04-15 | 1999-10-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-10-14 | 2003-04-15 | 2003-10-15 | $7700.00 | Window Closed / Lapsed |