United States Patent [191
`Kafri et al.
`
`[II] Patent Number:
`[45] Date of Patent:
`
`4,776,013
`Oct. 4, 1988
`
`[54] METHOD AND APPARATUS OF
`ENCRYPTION OF OPTICAL IMAGES
`Inventors: Oded Kafri, Beersheba; Eliezer
`Keren, Arad, both of Israel
`
`[75]
`
`[73] Assignee: Rotlex Optics Ltd., Beersheba, Israel
`[21] Appl. No.: 32,820
`[22] Filed:
`Apr. 1, 1987
`[30]
`Foreign Application Priority Data
`
`Israel .. .............................. .. .... .. 78541
`
`Apr. 18, 1986 (IL]
`[51]
`Int. Cl.~ ............................................... H04L 9/00
`[52] U.S. CI ......................................... 380/54; 380/10;
`380/20
`[58] Field of Search .............................. 380/54, 10, 20
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`2,495,790 1/1950 Valensi ......................... ......... 380/54
`2,952,080 9/1960 Avakian et at. ...................... 380/ 54
`3,156,051 11/1964 Hughes et at. ........................ 380/54
`3,234,663 2/1966 Ferris et at. ............. .............. 380/54
`3,627,919 12/ 1971 Roth et al. ....................... ... .. 380/54
`
`..... 380/ 5~
`3.889.056 6/1975 Mayer. Jr. et al.
`3,914,877 10/1975 Hines ...............
`3 80/ 5~
`4,586,711 5/ 1986 Winterset at. .......... ...... .. .... 380/ 5~
`4,682.954 7/1987 Cook ............. .. ..................... 380/ 5~
`
`Primary Examiner-Salvatore Cangialosi
`Attorney, Agent, or Firm-Benjamin J. Barish
`
`ABSTRACT
`[57]
`A method of encoding an optical image comprises:
`converting the optical iamge to an image grid com(cid:173)
`prised of an image matrix of pixels each having at least
`two possible intensity values; providing a master grid
`comprised of a master matrix of pixels each having at
`least two possible intensity values; and transmitting, for
`each pixel location of the image matrix, a pixel intensity
`value representing the intensity value of the master
`matrix at the corresponding location, its complement,
`or a random intensity value, depending on the intensity
`value of the pixel in the image matrix at the correspond(cid:173)
`ing location. Also described is an apparatus for carrying
`out the above encoding method.
`
`19 Claims, 6 Drawing Sheets
`
`r:'l-10--~•~ I Encod~ 2 ~---t•~ llid -16-· --t•~ Transmitt~:·
`
`D
`,. 14.
`~CODED
`---··
`' '
`
`GRID
`
`26.
`
`,
`
`'
`
`30.
`
`22.
`
`Decoder
`
`•
`
`MASTE
`GRID
`
`Receiver
`
`ENCODED
`20. GRID
`
`'
`
`MASTER
`GRID
`
`24.
`
`Vedanti Systems Limited - Ex. 2013
`Page 1
`
`

`
`U.S. Patent Oct. 4, 1988
`
`Sheet 1 of 6
`
`4,776,013
`
`10.
`
`12.
`
`•
`
`-~••I Encode \--~.-~
`83
`
`•
`
`14.
`
`MASTE
`GRID
`
`,
`
`--l•~ I Receiver
`
`ENCODED
`2o. GRID
`---1•~
`
`•
`
`18.
`
`16.
`
`, - - t .. ~ Transmitter
`
`ENCODED
`GRID
`
`26.
`
`30.
`
`22.
`
`Decoder • •
`
`•
`
`'
`
`DECODE
`
`FIG .1
`
`44.
`
`B
`r-1 MA-S-TE_R_,H ~~~~R~ ~-1---~r
`
`14.
`
`44.
`
`48.
`
`50.
`
`3 >+------1
`
`FIG .2
`
`Vedanti Systems Limited - Ex. 2013
`Page 2
`
`

`
`U.S. Patent Oct. 4, 1988
`
`Sheet 2 of 6
`
`4,776,013
`
`NO
`
`TRANSMJT
`COMPLEMENT
`OFMASTER
`PIXEL
`
`TRANMIT
`MASTER
`PIXEL
`
`FIG .3
`
`Vedanti Systems Limited - Ex. 2013
`Page 3
`
`

`
`U.S. Patent Oct. 4, 1988
`
`Sheet 3 of6
`
`4,776,013
`
`FIG. 4 A (MliSTER GRI'D)
`
`FIG. 4 8
`
`(ENCODED GRID)
`
`FIG. 4 C
`
`(DECODED PICTURE)
`
`Vedanti Systems Limited - Ex. 2013
`Page 4
`
`

`
`U.S. Patent Oct. 4, 1988
`
`Sheet 4 of6
`
`4,776,013
`
`TRANSMIT
`RANDOM
`PIXEL
`
`FIG .5
`
`YES
`
`1RANMIT
`MASTER
`'PIXEL
`
`NO
`
`TRANSMIT
`COMPLEMENT
`or
`MASTER
`. PIXEL
`
`YES
`
`TRANMIT
`RANDOM
`PIXEL
`
`FIG .6
`
`Vedanti Systems Limited - Ex. 2013
`Page 5
`
`

`
`U.S. Patent Oct. 4, 1988
`
`Sheet 5 of 6
`
`4.,776.,013
`
`TRANSMIT
`<:<>f\II'LEMENT
`OF
`!\lASTER
`l'IXEL
`
`YES
`
`YES
`
`TRANSMIT
`MASTER
`PIXEL
`
`TRANSMIT
`RANDOM
`PIXEL
`
`FIG .7
`
`SP 2
`
`- -c -
`
`SP 1
`p
`p
`1
`2
`: · - - -
`p
`p
`4
`3
`
`- -r---·
`
`- - -
`
`-
`
`SP 3
`
`SP 4
`
`FIG.S
`
`Vedanti Systems Limited - Ex. 2013
`Page 6
`
`

`
`U.S. Patent
`
`Oct. 4, 1988
`
`Sheet 6 of6
`
`4,776,013
`
`106
`
`104
`
`Image
`
`store ·
`
`Master frmnc
`stoi-c
`
`START
`
`CONSTRUCT
`LOOK-Ul'
`TABLE
`l(g),J(g) ,L(g)
`
`READ GRAY
`LEVEL,~.
`of SUPER l'IXEL
`
`READ I,J,L
`FROM
`LOOK-UP
`TADLE
`
`112
`
`'l'ransm.i tter
`
`FIG.O
`
`OUT
`
`OUT
`
`'l'HANSM!T
`MASTEn
`PL'<I~ L
`IN
`SICL. COOHD.
`
`FIG.lO
`
`Vedanti Systems Limited - Ex. 2013
`Page 7
`
`

`
`1
`
`4,776,013
`
`2
`representing white, "!"representing grey, and "0" rep(cid:173)
`resenting black. In this described embodiment, the mas(cid:173)
`ter pixel is transmitted if the image pixel is "1", a ran(cid:173)
`dom pixel is transmitted if the image pixel is"!", and the
`5 complement of the master pixel is transmitted if the
`image pixel is "0".
`Since in all the above-described embodiments, the
`encoded grid is a combination of two or more random
`grids, the encoded grid itself is also a random grid;
`10 therefore, by itself, it does not convey any information
`about the encoded picture. This makes it very difficult
`to decipher by an unauthorized person not having the
`master grid. As will also be described below, the
`method can be extended to the encryption of pictures
`with more than three grey levels, thereby further in(cid:173)
`creasing the difficulty of deciphering without the mas(cid:173)
`ter grid.
`The invention also provides apparatus for encoding
`20 and for encryption in accordance with the above(cid:173)
`described method.
`
`METHOD AND APPARATUS OF ENCRYPTION
`OF OPTICAL IMAGES
`
`BACKGROUND OF THE INVENTION
`The present invention relates to a method and appara(cid:173)
`tus for encoding and encrypting optical images, such as
`two-dimensional patterns and shapes.
`The encoding of two-dimensional patterns and shapes
`is important for transmission of pictures and for similar
`purposes in civilian security as well as military applica(cid:173)
`tions. Many techniques have been proposed and are
`now in use, but efforts are continuously being made to
`increase the difficulty in deciphering the transmission
`by an unauthorized person.
`An object of the present invention is to provide a
`method and apparatus for encoding and encrypting
`optical images in a manner extremely difficult to deci(cid:173)
`pher by an unauthorized person.
`
`15
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`BRIEF SUMMARY OF THE INVENTION
`According to the present invention, there is provided
`a method of encoding an optical image comprising:
`The invention will be better understood by reference
`converting the optical image to an image grid com-
`prised of an image matrix of pixels each having at least 25 to the enclosed drawings, wherein:
`two possible intensity values (sometimes called "bright-
`FIG. 1 is a block diagram illustrating the main steps in
`ness" or "grey-level") values; providing a master grid
`a method of encrypting an optical image in accordance
`comprised of a master matrix of pixels each having at
`with the present invention;
`least two possible intensity values; and transmitting, for
`FIG. 2 is a block diagram illustrating the main com-
`each pixel location of the image matrix, a pixel intensity 30 ponents of a system for encrypting an optical image in
`value representing the intensity value of the master
`accordance with the present invention;
`FIG. 3 is a flow diagram illustrating the operation of
`matrix at the corresponding location, its complement,
`or a random intensity value, depending on the intensity
`the encoder in the system of FIG. 2 for encrypting an
`value of the pixel in the image matrix at the correspond-
`optical image in accordance with one embodiment of
`ing location.
`35 the invention;
`It will thus be seen that the novel method is based on
`FIGS. 4a-4c illustrate, respectively, the master grid,
`the use of random grids. An important property of
`the encoded grid, and the decoded image, when en-
`random grids is the principle of "combination". That is,
`crypting the optical image of the number "3" in accor-
`if a section is cut-out from a random grid and is replaced
`dance with the embodiment of the invention repre-
`with a section of similar shape from a second random 40 sented by the flow diagram of FIG. 3;
`grid, the result is yet another random grid. The number
`FIGS. 5, 6 and 7 are flow diagrams illustrating three
`of different grids possible is in the order of 2N, where,
`additional methods of encoding the transmitted optical
`"N" is the number of pixels in the array.
`image, and thereby decoding of the transmitted optical
`When two random grids with the same dimensions
`image, in accordance with three further embodiments
`are placed on top of one another so that they corre- 45 of the invention;
`FIG. 8 diagrammatically illustrates a "superpixel"
`spond pixel by pil!;el, and when each pixel can have but
`two possible intensity values (e.g. "1" =transparent, and
`involved when extending the encryption of pictures to
`"O"=opaque), the probability of each superimposed
`more than three grey levels;
`pixel being transparent is 1. Thus, the average transmis-
`FIG. 9 is a block diagram illustrating the apparatus
`sion of two superimposed different random grids is 1. 50 when encrypting according to the "superpixel" varia(cid:173)
`When the two grids are identical, the average transmis-
`sion is ! .
`tion; and
`Several embodiments of the invention are described
`FIG. 10 is a flow diagram illustrating the manner of
`below for purposes of example. In one embodiment, the
`encryption according to the "superpixel" variation.
`master pixel is transmitted when the image pixel is of 55
`DESCRIPTION OF PREFERRED
`one intensity value (e.g. "1" indicating "white"), and
`EMBODIMENTS
`the complement of the master pixel intensity value is
`Reference is first made to FIG. 1 illustrating the basic
`transmitted when the image pixel is of the other inten(cid:173)
`concept of the method of encryption in accordance
`sity value ("0" indicating "black"); in a second de(cid:173)
`with the present invention. Thus, as shown in FIG. 1,
`scribed embodiment, the master pixel is transmitted 60
`the optical image 10 to be transmitted, representing the
`when the image pixel is "1", as in the filist embodiment,
`number "3", is encoded in an encoder 12 with a master
`but a random pixel is transmitted when the image pixel
`grid 14 to produce an encoded grid 16 which is trans(cid:173)
`is "0"; and in a third described embodiment, a random
`mitted via transmitter 18 to a receiver 20. The receiver
`pixel is transmitted when the image pixel is "1", and the
`20 includes a decoder 22 which receives the encoded
`complement of the master pixel is transmitted when the 65
`grid 26, corresponding to the transmitted encoded grid
`image pixel is "0".
`16, and also the master grid 24, corresponding to the
`A fourth embodiment of the invention is described
`wherein each pixel is of three grey levels, namely "1"
`master grid 14 in the transmitter, to produce the de-
`
`Vedanti Systems Limited - Ex. 2013
`Page 8
`
`

`
`4,776,013
`
`3
`coded grid 30, which is a reproduction of the optical
`image 10 originaly transmitted.
`The encoding operation 12 in the transmitter end, and
`the decoding operation 22 in the receiver end, may be
`performed according to any one of a number of algo(cid:173)
`rithms as described below particularly with reference to
`FIGS. 3, 5, 6 and 7, respectively. In all these algorithms,
`the optical image 10 is converted to an image grid com(cid:173)
`posed of an image matrix of pixels each having at least
`two possible intensity values ("1" and "0" in the algo- 10
`rithms of FIGS. 3, 5 and 6; and "1", "!",and "0" in the
`algorithm of FIG. 7); and there is transmitted, for each
`pixel location of the image matrix, a pixel intensity
`value representing the intensity value of the master grid
`(14, 24) at the corresponding location, its complement, 15
`or a random intensity value, depending on the intensity
`value of the pixel in the image matrix of the correspond(cid:173)
`ing location. Since the encoded grid which is transmit(cid:173)
`ted (grid 16 in FIG. 1) thus constitutes a combination of
`two random grids, the encoded grid itself is a random 20
`grid, and therefore, by itself, does not convey any infor(cid:173)
`mation about the encoded grid. This makes deciphering
`of the encoded grid extremely difficult by an unautho(cid:173)
`rized person not having the master grid.
`The master grid 14 may be generated by scanning a 25
`master image and converting it to a master matrix of
`pixels each having the same two (or three, or more)
`possible intensity values as the optical image. Prefera(cid:173)
`bly, the master grids 14 and 24 are in the form of a ROM
`(Read Only Memory) storing the master matrix of pix- 30
`els and used in the above-described encoding step 12
`and decoding step 22, respectively; alternatively, the
`master grid used in the decoding could be in the form of
`a transparency superimposed over the encoded image.
`FIG. 2 is a block diagram illustrating one implemen- 35
`tation of the encryption method described above with
`respect to FIG. 1.
`Thus, the optical image 10 to be encoded is scanned
`by a TV camera 40, converted by a digitizer 42 to an
`image grid composed of an image matrix of pixels in 40
`which matrix each pixel may have two intensity values,
`for "white", and "0" for "black", and
`namely "1"
`stored in an image memory 44. The master grid 14
`composed of a master matrix in which each pixel may
`have the same two values as in the image matrix, was 45
`previously stored in a memory 44. Each pixel of the
`inulge matrix from the image memory 44 is introduced
`into encoder 48 with the correspondingly-located pixel
`of the master matrix from the master memory 46.
`Encoder 48 utilizes both the image matrix and master so
`matrix to produce an encoded grid (16, FIG. 1) accord(cid:173)
`ing to the specific algorithm selected for encryption, as
`described below with rexpect to FIGS. 3, 5 and 6. The
`encoded grid is then transmitted by transmitter 50, and
`is received by receiver 52. The master grid, if stored in 55
`memory, is used in the decoding; but if in the form of a
`transparency, it is superimposed over the encoded grid
`in decoder 54, to produce the decoded grid which is
`displayed in a display unit 56.
`FIG. 3 is a flow diagram illustrating one algorithm 60
`which may be used for operation of the encoder 48, and
`also the decoder 54, in the system illustrated in FIG. 2.
`The algorithm illustrated in FIG. 3 is for use when each
`pixel of the image matrix and master matrix has only
`two possible intensity values, in this case a "1" when the 65
`pixel is white, and a "0" when the pixel is black.
`Thus, as shown by the algorithm illustrated in FIG. 3,
`each pixel of the image matrix inputted into the encoder
`
`4
`48 is examined to determine whether it is "1": if so, the
`encoder 48 outputs to the transmitter 50 the master pixel
`at the corresponding location of the matrix; if not, en(cid:173)
`coder 48 outputs to the transmitter the complement of
`the master pixel at the corresponding location of the
`matrix.
`As described above with respect to FIG. 2, the en(cid:173)
`coded grid received by the receiver 52 is decoded in
`decoder 54, by the use of a computer-stored or an opti(cid:173)
`cally-transparent master matrix, to produce the de(cid:173)
`coded picture displayed in diplay 56.
`FIG. 4a illustrates the master grid which, as indicated
`above, is a random grid; FIG. 4b illustrates the encoded
`grid outputted from encoder 48 and inputted into de(cid:173)
`coder 54 using the master grid of FIG. 4a and the pic(cid:173)
`ture 10 encrypted by the sytem; and FIG. 4c illustrates
`the decoded picture outputted from decoder 54 and
`displayed in display 56. It will thus be seen that, in the
`decoded picture of FIG. 4c, the black pixels of the origi(cid:173)
`nal image 10 are reproduced as black (pixel intensity
`value equal "0"), whereas the white pixels in the origi(cid:173)
`nal image are reproduced as "grey" (pixel intensity
`value equal 'T').
`Since the encoded grid of FIG. 4b is a combination or
`superposition of two random grids, (namely, the master
`grid and the complement of the master grid), the en(cid:173)
`coded grid itself is a random grid and therefore does not
`convey any information about the encoded picture,
`thereby making deciphering of the encoded picture
`extremely difficult.
`FIG. 5 illustrates a second algorithm which may be
`used for operation of encoder 48 and decoder 54 in the
`system of FIG. 2, wherein each pixel of the image ma(cid:173)
`trix and master matrix also has two grey levels, namely
`"1" representing white, and a "0" representing black.
`Thus, when the encoder and decoder are operated ac(cid:173)
`cording to the algorithm illustrated in FIG. 5, the en(cid:173)
`coder 48 transmits the master pixel intensity value when
`the image pixel at the corresponding location is "1"
`(white), and a random pixel intensity value when the
`image pixel at the corresponding location is "0" (black).
`The same master grid is used in decoder 54 for decoding
`the so-encrypted picture. The encoded picture pro(cid:173)
`duced according to this algorithm is even more difficult
`to decipher than the algorithm of FIG. 3, since some
`regions of the encoded grid bear no relationship to
`other pictures encoded from the same master; however,
`the contrast is poorer than when using the algorithm of
`FIG. 3.
`FIG. 6 illustrates a further algorithm that may be
`used for operating the encoder 48 and decoder 54 in the
`system of FIG. 2, also in the case where each pixel
`intensity value is of one of two grey levels, namely a "1"
`representing white, and a "0" representing black. Ac(cid:173)
`cording to the algorithm of FIG. 6, the encoder 48
`transmits a random intensity value when the image pixel
`intensity value at the correponding location of the ma(cid:173)
`trix is "1" (white), and the complement of the master
`pixel when the image intensity value at the correspond(cid:173)
`ing location of the matrix is "0" (black). The encoded
`grid according to the algorithm illustrated in FIG. 6 is
`as difficult to decipher as the algorithm illustrated in
`FIG. 5, but the final picture has improved contrast over
`the algorithm illustrated in FIG. 5 because "black" is
`reproduced as "black"; however, the contrast is poorer
`than with the algorithm illustrated in FIG. 3.
`FIG. 7 illustrates a still further algorithm which may
`be used for operating the encoder 48 and decoder 54 in
`
`Vedanti Systems Limited - Ex. 2013
`Page 9
`
`

`
`5
`the systm of FIG. 2. The algorithm illustrated in FIG. 7
`requires that each pixel be of one of three grey levels,
`namely "1" representing white, "!"representing grey,
`and "0" representing black.
`According to the algorithm illustrated in FIG. 7, 5
`encoder 48 transmits the intensity value of the master
`pixel where the image pixel is "1" at the corresponding
`location of the matrix, a random pixel where the image
`pixel at the corresponding location is 'T', and the com(cid:173)
`plement of the master pixel where the image pixel at the 10
`corresponding location is "0". Encryption according to
`the algorithm illustrated in FIG. 7 is even more difficult
`to decipher than the method illustrated by the algo(cid:173)
`rithms of FIGS. 3, 5 and 6.
`The method can be extended to the encryption of 15
`pictures with more than 3 grey levels.
`Thus, let the picture with N=n Xm pixels have K+ 1
`distinct levels of grey with intensity values 0, 1, •• . K.
`In order to encode this picture an imaging system is
`say 20
`needed having a higher spatial
`resolution,
`N1=n1Xm1 pixels, with N1>N. To each pixel in the
`picture there is assigned a rectangular array of
`M=(ntln)X(mllm) pixels in the image frame. This
`array of M pixels is referred to as a "superpixel". The
`relationship between the number of grey levels and the 25
`required superpixel dimensionality will be calculated as
`follows:
`The encoder and master random grids have identical
`numbers of superpixels and pixels and the same subdivi- 30
`sion of superpixels into pixel arrays. Each pixel in the
`encoded grid corresponds to one pixel in the master,
`with the same coordinates. Three choices are available
`for determining the light transmission by each pixel in
`the encoded grid:
`(1) duplicate the corresponding pixel in the master
`grid, which leads to an average transmission of! in the
`superimposed grids;
`(2) complement the master, which yields zero trans-
`mission; or
`(3) choose randomly, which results in an average
`transmission of 1.
`Various combinations of the three assignments pro(cid:173)
`duce intermediate levels of grey according to the fol-
`lowing procedure.
`Let I be the number of duplicated pixels out of the M
`pixels of a particular superpixel in the master. The num(cid:173)
`is J;
`ber of complemented pixels
`the remaining
`L =M-I -J are chosen at random. The resulting aver-
`age transmission is:
`
`45
`
`50
`
`4,776,013
`
`35
`
`40
`
`6
`Unless g equals "0" or "K" the choice of I and J is
`not unique. In order to maximize the randomness of the
`coding mechanism, it is preferable to choose J =0 for
`g::§K/2 and I::§O for g=K/2. Alternatively, it is possi(cid:173)
`ble to choose the values of I and J at random, subject to
`the constraints of eqs. 2 and 4.
`The assignment of individual pixels within the array
`to the three coding alternatives is also done at random.
`This further reduces the correlation between different
`superpixels in the coded grid.
`Although the average transmission of random grids is
`!. the transmissions of individual superpixels may differ
`from !. due to the random choice and the small size of
`the pixel array. The width of the distribution of super(cid:173)
`pixel transmissions, which is centered around !. is in(cid:173)
`versely proportional to the square root of the number M
`of pixels in each superpixel. When the master and en(cid:173)
`coded grids are superimposed, the resulting transmis(cid:173)
`sion may be slightly different from that expected from
`eq. 3. This variation cancels out when averaged over
`many neighboring superpixels, and produces in effect,
`dithering. Dithering is a technique often used for
`smoothing out artificial contours formed at the transi(cid:173)
`tion between different levels in a picture with a limited
`number of grey levels. This is attained through deliber(cid:173)
`ate addition of a random noise to the picture, producing
`a result that is more pleasing to the eye. This beneficial
`effect results automatically from the proposed method
`and has the added advantage of making deciphering
`more difficult.
`FIG. 8 illustrates several such "superpixels" SP1,
`SP2, SP3, each constituted of a · matrix of 2 X 2 regular
`pixels (e.g. P1-P4) thereby providing nine grey levels.
`The image is encrypted by a system according to the
`block diagram illustrated in FIG. 9, and according to
`the flow diagram of FIG. 10.
`Thus, a processor 100 is supplied with information
`concerning the master image from a master frame store
`102, and is also supplied with the image information by
`scanning the image at 104, digitizing it by digitizer 106,
`and storing it in the image frame store 108. Processor
`100 is also provided with a look-up table 110 which
`outputs signals to processor 100 in accordance with the
`one of nine possible grey levels of the corresponding
`superpixel. These signals are used by the processor for
`encoding the image . before transmitting the encoded
`image via transmitter 112.
`Following is one example of such a look-up table for
`the case of superpixels including 2 X 2 pixels (nine possi(cid:173)
`ble grey levels).
`
`T=l/(2M)+L/(4M)+O(J),
`
`T=(I-J)/4MH
`
`O<l:J:L<M
`
`(I)
`
`(2) 55
`
`From eqs. 1, 2 "T" ranges from 0 to l in steps of
`l!(4M), so there are overall 2M+ 1 distinct transmission
`values, namely K=2M.
`The superpixel in a picture with intensity (brightness) 60
`values gin the range 0-K will be assigned according to
`
`T=g!2K
`
`(3)
`
`The choice of I and J for each superpixel must satisfy 65
`inequality (2) and (See eq. 1):
`
`I-J=(4T -I)M=g-M
`
`(4)
`
`TABLE 1
`
`Symbol
`
`I
`No. of
`copied
`pixels
`from Master
`0
`0
`0
`0
`0
`I
`2
`3
`4
`
`No. of
`complement
`from Master
`4
`3
`2
`I
`0
`0
`0
`0
`0
`
`L
`No. of
`random
`pixels
`0
`1
`2
`3
`4
`3
`2
`I
`0
`
`g
`meaning grey level
`(transmittance)
`0 (0)
`1 (1116)
`20)
`3 (3/16)
`40)
`s {5/16)
`6(i)
`7 (7/16)
`sm
`
`With reference to the flow diagram of FIG. 10, the
`first step is the construction of a look-up table which
`
`Vedanti Systems Limited - Ex. 2013
`Page 10
`
`

`
`7
`gives three outputs: (1) the number (I) of pixels to be
`copied from the master; (2) the number (J) of pixels to
`be complemented and; (3) the number (L) of pixels to be
`chosen at random. The sum of I, J, and Lis equal to the
`number "M" of pixels in the superpixel array. The input 5
`"g" to the look-up table is one of 2M+ 1 grey levels;
`where a superpixel includes 4 pixels (2 X 2) as in our
`case, three are 9 grey levels of the image being coded.
`The superpixels are scanned in a normal sequence.
`For each superpixel, the grey level(g) is determined and 10
`the corresponding I, J, and L values are read from the
`look-up table. If I is positive (J =0), the processor fol(cid:173)
`lows the sequence in the rightmost column in the flow(cid:173)
`charts. The coordinates of the first pixel to be transmit(cid:173)
`ted are selected at random. In future iterations, only 15
`enabled coordinates, namely those which have not been
`transmitted yet, may be selected. The value of the mas(cid:173)
`ter grid at the selected coordinates is transmitted, and
`the corresponding pixel in the image is disabled to pre(cid:173)
`vent it from being selected again. This sequence is re- 20
`peated I times.
`If J is positive (1=0), the sequence of the middle
`column is carried out. No pixel is duplicated. Instead, J
`pixels will be transmitted with values equal to the com(cid:173)
`plement of the pixel value in the corresponding coordi- 25
`nates of the master grid.
`When either of the above sequences has been com(cid:173)
`pleted, control is passed to the leftmost column in the
`chart, where pixel values are chosen at random. The
`pixel coordinates are scanned in a regular fashion (not 30
`random), and those pixel which have not been disabled
`in previous steps are assigned random values and trans(cid:173)
`mitted. If either I or J is equal toM, namely L=O, this
`section is bypassed, and control is transferred to the
`next superpixel in the image.
`When L=M, namely both I and J equal 0, both right(cid:173)
`most and middle column are bypassed, and the entire
`pixel array is transmitted in a random fashion through
`the left column of the chart.
`Several additional methods can be used to make un- 40
`authorized deciphering even more difficult. The coordi(cid:173)
`nates of the superpixels can be scrambled, with the
`unscrambling done by the computer after combining
`the encoded grid with the master. The master grid can
`be a physical grid, or a numerical grid stored in the 45
`computer's memory. Alternatively, a simpler scram(cid:173)
`bling mechanism would be to vary the origin of the
`coordinate axes so that it corresponds to an arbitrary
`point in the master. The two grids are thus cyclically
`shifted relative to one another. The information on the 50
`correct origin is sent together with the encoded grid. A
`variation of this technique would be to use various
`masters, with the identity of the master encoded to(cid:173)
`gether with the picture. These and other methods may
`be necessary to reduce the correlation between different 55
`encoded grids, in case someone tries to decipher the
`code by combining them.
`In addition, random grids can be employed as trans(cid:173)
`parencies with a range of transmissions chosen at ran(cid:173)
`dom, instead of "0" and "1" as described above; the 60
`combined transmission of the master and encoded grids
`is the picture. Further, instead of black and white, color
`can also be employed.
`The method can be implemented in various forms.
`For instance, the encoded picture can be printed on an 65
`identification card and the master stored in the comput(cid:173)
`er's memory. During decoding, the computer would
`combine the stored master with the video frame of the
`
`35
`
`_4,776,013
`
`8
`card, and do the necessary contrast enhancement opera(cid:173)
`tions. The use of a computer for processing the image
`may have additional benefits, such as filtering out ran(cid:173)
`dom noise with some well known noise reduction algo(cid:173)
`rithm.
`While the invention has been described with respect
`to several preferred embodiments, it will be appreciated
`that many other variations, modifications and applica(cid:173)
`tions of the invention may be made.
`What is claimed is:
`1. A method of encoding an optical image compris(cid:173)
`ing:
`converting the optical image to an image grid com(cid:173)
`prised of an image matrix of pixels each having at
`least two possible intensity values;
`providing a master grid comprised of a master matrix
`of pixels each having at least two possible intensity
`values;
`and transmitting, for each pixel location of the image
`matrix, a pixel intensity value representing the
`intensity value of the master matrix at the corre(cid:173)
`sponding location, its complement, or a random
`intensity value, depending on the intensity value of
`the pixel in the image matrix at the corresponding
`location.
`·
`2. The method according to claim 1, wherein the
`master grid is stored in a memorydevice.
`3. The method according to claim 1, wherein the
`master pixel intensity value is transmitted when the
`image pixel is of one intensity value, and the comple(cid:173)
`ment of the master pixel intensity value is transmitted
`when the image pixel is of the other intensity value.
`4. The method according to claim 1, wherein the
`master pixel intensity value is transmitted when the
`image pixel is of one intensity value, and a random
`intensity value is transmitted when the master pixel is of
`the other intensity value.
`5. The method according to claim 1, wherein a ran(cid:173)
`dom intensity value is transmitted when the image pixel
`is of one intensity value, and the complement of the
`master pixel intensity value is transmitted when the
`image pixel is of the other intensity value.
`6. The method according to claim 1, wherein each
`pixel has at least three possible intensity values, the
`master pixel intensity value being transmitted when the
`image pixel is of one intensity value, a random intensity
`value being transmitted when the pixel is of the second
`intensity value, and the complement of the master pixel
`intensity value being transmitted when the image pixel
`is of the third intensity value.
`7. The method according to claim 1, wherein said
`optical image is converted to an image matrix of pixels
`each having more than three pixel intensity values by
`grouping a plurality of pixels into groups of superpixels
`having a number of grey levels increasing with the
`number of pixels in the superpixel.
`8. A method of encrypting an optical image, compris(cid:173)
`ing:
`transmitting the encoded optical image in accordance
`with claim 1;
`receiving said encoded optical image;
`and decoding said encoded optical image by combin(cid:173)
`ing each pixel of the received matrix with each
`pixel of said master matrix.
`9. The method according to claim 8, wherein the
`master grid, during the decoding, is stored in a memory.
`
`Vedanti Systems Limited - Ex. 2013
`Page 11
`
`

`
`4,776,013
`
`9
`10. The method according to claim 8, wherein the
`master grid, during the decoding, is in the form of a
`transparency combined with the encoded image matrix.
`11. Apparatus for encoding an optical image compris(cid:173)
`ing:
`means for converting the optical image to an image
`grid comprised of an image matrix of pixels each
`having at least two possible intensity values;
`means for storing a master grid comprised of a master
`matrix of pixels each having at least two possible 10
`intensity values;
`and means for transmitting, for each pixel location of
`the image matrix, a pixel intensity value represent(cid:173)
`ing the intensity value of the master matrix at the
`corresponding location, its complement, or a ran- 15
`dom intensity value, depending on the intensity
`value of the pixel in the image matrix at the corre(cid:173)
`sponding location.
`12. Apparatus according to claiin 11, wherein said
`latter means transmits the master pixel intensity value 20
`when the image pixel is of one intensity value, and the
`complement of the master pixel intensity value when
`the image pixel is of the other intensity value.
`13. Apparatus according to claim 11, wherein said
`latter means transmits the master pixel intensity value 25
`when the image pixel is of one intensity value, and a
`random intensity value is transmitted when the master
`pixel is of the other intensity value.
`14