Title of Invention	RANDOMIZED SIGNAL TRANSFORMS AND THEIR APPLICATIONS
Abstract	Techniques are disclosed to provide randomized signal transforms and/or their applications. More particularly, a signal (e.g., an audio signal, an image, or a video signal) is transfoimed by applying randomly-selected basis functions to the signal. The applications of the randomized signal transforms include, but are not limited to, compression, denoising, hashing, identification, authentication, and data embedding (e.g., watermarking).

Title of Invention

RANDOMIZED SIGNAL TRANSFORMS AND THEIR APPLICATIONS

Abstract

Techniques are disclosed to provide randomized signal transforms and/or their applications. More particularly, a signal (e.g., an audio signal, an image, or a video signal) is transfoimed by applying randomly-selected basis functions to the signal. The applications of the randomized signal transforms include, but are not limited to, compression, denoising, hashing, identification, authentication, and data embedding (e.g., watermarking).

Full Text	RANDOMIZED SIGNAL TRANSFORMS AND THEIR APPLICATIONS TECHNICAL FIELD [OOOl] The present invention generally relates to signal transforms, and more particularly, to randomized signal transforms andor their applications. BACKGROUND [0002] As digital communication becomes more commonplace, the need for securing andlor authenticating the transferred digital data becomes increasingly more important. Digital signals carrying digital data is often (if not always) transformed into a specific format (e.g., by a transform) prior to being transferred. For example, a file containing digital data may be compressed prior to sending it over the Internet. [00031 , Since more powerhl computers, high-speed Internet connections, and superior compression technologies are available to most users, the demand for digital media content is greater than ever. With instant and anytime access to literally millions of their favorite music and videos, consumers are applauding the convenience that digital distribution has afforded them. They enjoy being able to download or stream music to their hard drive or personal computer hard drive as fluidly as any television broadcast. * [0004] While the demand for digital content grows, however, so does the potential for its unauthorized use. Without a secure distribution system in place, digital media files can be easily copied or compressed into smaller files without the content owner's authorization. These files can then be transferred across the Internet for others to use or distribute freely. This violates the copyrights held by thousands of media companies, record labels, filmmakers, and recording artists. Such unauthorized use also strips these entities of valuable revenues as well. [OOOS] One current approach is to encrypt the digital content to limit its unauthorized use. This approach, however, introduces additional overhead which can reduce the speed of systems utilizing signal transformation. [0006] Accordingly, signal transformation solutions are desired which provide additional security while limiting performance degradation. SUMMARY [0007] Techniques are disclosed to provide randomized signal transforms and/or their applications. More particularly, a signal (e.g., an audio or video signal) is transformed by applying randomly-selected basis hctions to the signal. The applications of the randomized signal transforms include, but are not limited to, compression, denoising, hashing, identification, authentication, and data embedding (e.g., watermarking). BRIEF DESCRIPTION OF THE DRAWINGS [OOOS] The detailed description is described with reference to the accompanying figures. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The use of the same reference numbers in different figures indicates similar or identical items. [0009] Fig. 1 illustrates an exemplary randlet transform (RT) system. [00 lo] Fig. 2 illustrates an exemplary RT method. [OOll] Fig. 3 illustrates an exemplary method for generating RT basis functions. [0012] Fig. 4 illustrates an exemplary method for generating an RT basis functions library. [OO 131 Fig. 5 illustrates an exemplary method for applying RT transformations. [0014] Fig. 6 illustrates an exemplary method for RT-based compression. [0015] Fig. 7 illustrates an exemplary method for RT-based denoising. [OO 161 Fig. 8 illustrates an exemplary method for RT-based hashing. [0017] Fig. 9 illustrates an exemplary method for RT-based watermarking. [OOl 81 Fig. 10 illustrates an exemplary method for reconstruction of a signal transformed using RT. 9 [0019] Fig. 11 illustrates a general computer environment 1100, which can be used to implement the techniques described herein. DETAILED DESCRIPTION [0020] The following disclosure generally describes techniques for improving signal transformation. More specifically, a family of signal transforms, referred to herein as randlet transforms (RTs), are applied to signals (such as audio and/or video signals) to provide security, while maintaining reasonable performance. Each family member transform uses a set of basis hnctions (also referred to herein as "randlets") that are chosen randomly or pseudorandomly based on a secret key (K). In various described implementations, the application of RT can result in improved data embedding (e.g., watermarking), identification, authentication, hashing, denoising, and/or compression. [0022] Fig. 1 illustrates an exemplary randlet transform (RT) system 100. An RT module 102 receives input data (104) such as an audio andlor video signal. The signal may be provided by a computer-readable medium, by a source connected to a computer network (e.g., an intranet, the Internet, a wireless network, etc.), and the like (as will be further discussed with reference to the computing environment of Fig. 11). * [0023] The RT module 102 transforms the input signal using a set of basis functions (106) that are selected randomly. The randomness is provided by a random number generated (or multiple random numbers generated) by a pseudorandom generator (108). In an implementation, the pseudorandom generator (108) is seeded by a secret key (K) (110). The secret key (K) may be provided as a bit stream. In one implementation, the generator 108 is a cryptologically-strong pseudorandom generator. The output of the RT module 102 (e.g., a vector) can be used for a number of applications (112), which will be further discussed, for example, with reference to Figs. 6- 10. [0024] Fig. 2 illustrates an exemplary RT method 200. After RT basis functions are generated (202) (as will be further discussed with reference to Figs. 3 and 4), a number of the generated basis functions are selected at random (204) such as discussed with reference to Fig. 1. In an implementation, a secret key (K) (e.g., used as a seed for a pseudorandom number generator) specifies which basis functions should be selected for a particular instance. An input signal (104) is then b transformed by applying the randomly selected basis functions (206). In an implementation, the input signal may be divided into blocks as will be mher discussed with reference to Fig. 5, for example. [0025] Moreover, the RT may be applied as a discrete transform. The provided randomness may give the RT two distinct advantages. First, it is useful for security purposes because an attacker cannot know which basis functions are 9' used in the transform, making attacks relatively much more difficult. Second, because the basis is chosen at random from a relatively large set of basis functions, the worst-case performance of the transform occurs with relatively low probability. The measure for the RT is therefore the average-case performance rather than the worst-case performance. [0027] The basis functions (also referred to herein as "randlets") are based on a set of two-dimensional functions called "mother randlets." A variety of mother randlets are discussed below. It is envisioned that basis functions that are one-dimensional, two-dimensional, or three-dimensional (e.g., corresponding to audio signals, images, and video signals, respectively) may be utilized. [0028] Fig. 3 illustrates an exemplary method 300 for generating RT basis functions. Generally, a randlet is produced by scaling (302), rotating (304), translating (306), discretizing (308), and normalizing (310) a mother randlet. Other orders of stages 302, 304, 306, and/or 308-310 are also envisioned. Furthermore, rotation may not be done for certain distributions such as symmetrical Gaussian distributions (i.e., rotation of a circle is not done). [0029] In an implementation, given a mother randlet m(x,y) , a randlet with horizontal translation a, vertical translation b, horizontal scaling a, vertical scaling P, and rotation 6 would be: [0033] Accordingly, to choose the specific randlets used in an instance of the RT, the secret key (K) is used to seed a pseudorandom number generator (such as 108 of Fig. 1). And, whenever a random number is needed, it is taken &om this pseudorandom number generator. [0035] Fig. 4 illustrates an exemplary method 400 for generating an RT basis functions library. Generally, it is possible to define an RT basis by choosing all randlets independently and at random. In one implementation, however, this is unnecessary for practical reasons, as equal performance can be achieved by slightly constraining the choices of randlets. Furthermore, by limiting the choices of randlets, computational performance may be significantly improved. [0036] In an implementation, the basis fbnctions are constrained by allowing only a finite set of scaling and rotation operations, instead of choosing the scaling and rotation independently for each randlet. Instead of defining each randlet independently of all others, a random library of non-translated randlets is generated. These randlets are known as "step-mother randlets," and are generated by randomly scaling and rotating the mother randlets (402 and 404, respectively). This set of all step-mother randlets may be referred to as the "library" (406). 100371 Each mother randlet is scaled randomly in both directions. The distributions for the scaling depend on both the specific mother randlet and the application. Examples are given in later sections. For each scaled mother randlet, the number of rotations generated may be proportional to the perimeter. [0038] The step-mother randlets are translated (408), discretized (410), and normalized (412). Because a step-mother randlet is a discretized version of a mother randlet that has been scaled and rotated by real numbers, the normalization constant is determined by setting the inner product of the randlet with itself equal to 1. Hence: [0041] Note that K depends on a and P . [0042] The following several important values are parameters for the creation of an RT basis: [0043] n: The total number of basis functions. : The width and height of the block to be transformed, respectively. [0045] FC): An algorithm which determines the type of each randlet. [0046] The full set of randlets is generated by randomly choosing and translating (408) step-mother randlets from the library. This is done by generating a list of n 3-tuples, with each one representing one randlet that will be used in the transform: . In the 3-tuples, i is in index to the library, and so implicitly determines the scaling and rotation of the randlet. i is chosen at random by the function FC). The exact function F used depends on the application. a and b are the real-valued horizontal and vertical translation of center point of the randlet, chosen uniformly at random from [O,T] and [O,U], respectively. In an implementation, once the list has been generated, it is sorted according to the size of the randlets, e.g., with the largest randlets first and the smallest randlets last. [0048] As discussed above, mother randlets are the base randlets from which all others are created as discussed with reference to Fig. 4. Mother randlets are two-dimensional real-valued functions with localized effective support, centered around (0,O). There are generally two types of mother randlets, lowfrequency randlets and high-frequency randlets. Both types of randlets have a Gaussian shape in the horizontal direction. In the vertical direction, low-frequency randlets have a Gaussian shape while high-frequency randlets have an oscillatory i shape. The only high-frequency randlet is also known as the Gaussian randlet. It is usell for finding low-frequency components of an image or audio content. It has a Gaussian shape in both the horizontal and vertical directions, although each direction can have different widths. [0049] Gaussian Randlet: [0051] High-frequency randlets have a Gaussian shape in the horizontal direction and various oscillatory shapes in the vertical direction. Since they will be rotated, we refer to the smooth direction as the direction of the Gaussian, and the rough direction as the direction of the oscillatory function. The variations in the vertical direction give these randlets edge-detection properties in the horizontal direction. When rotated by B degrees, they will tend to detect edges at B degrees. Other types of randlets include: [0052] Half Randlet: [0053] 0~x2+uyy2 m(x, Y) = we [0054] Mexican Hat Randlet: [0055] m(x, y) = q2e"=x2+cY~2 [0056] Wavelet Randlet: [0057] m(x, y) = CDv(y)eUxx2 [0058] The w@ portion of the wavelet randlet is a one-dimensional wavelet function. In an implementation, when scaling a wavelet randlet, instead of choosing a wavelet of fixed size, a wavelet family can be chosen, and instead of scaling, a longer or shorter member of the wavelet family can be chosen. [0059] Generally, high-frequency randlets are scaled so that the randlet is longer in the smooth direction than in the rough direction. This enhances the randlet's ability to detect edges. [0060] In an implementation, the mother randlets may be obtained by combinations of the Gaussian, half, Mexican Hat, andor wavelet randlets. [0061] RT TRANSFORMATION [0062] Fig. 5 illustrates an exemplary method 500 for applying RT transformations. The transform is done by projecting each randlet onto the signal in turn (502). The randlets may be selected pseudorandomly (e.g., as discussed with reference to Figs. 1-2). After each projection is taken, it is subtracted from the signal (504). What remains of the signal after the subtraction is called the "residue." The RT transformation method 500 continues by projecting each selected randlet onto the residue of the previous randlet (506). In this manner, the transform converges to the original signal, and the power of the coefficients tends to fall exponentially. [0063] A transform coefficient k is computed (508) for each randlet by finding the inner product of randlet k and the residue of randlet k-1. If the randlet k is denoted by rk, the residue of randlet rn is denoted by R,, and coefficient n is denoted by c, , then: [0065] As each coefficient is generated, it is quantized (510), and it is the quantized value that is stored (512) as the coefficient in the transform. In accordance with one implementation, it is also this quantized value that is subtracted fiom the signal (504). In an implementation, a uniform quantizer is used, basing the number of levels on type and scaling of the randlet. Randomized rounding may also be used, e.g., to round the coefficient based on a random number. The effects of randomized rounding may be accommodated by the iterative convergence of the algorithm. [0066] Once the quantization is complete, the next residue is computed (514). If Qc) is the quantizer, then: [0068] In an implementation, the randlets are not projected upon the entire signal block. The effective footprint of the randlets is computed in a preprocessing phase (not shown) by considering only the area where the randlets have nonnegligible value. The randlets are then only projected in that area. [0069] In an alternative implementation, the basis functions are placed as normal and then their positions are perturbed to the nearby location of maximum power. This makes the transform converge with fewer coefficients, but extra information would have to be stored with each coefficient giving the horizontal and vertical perturbation. [0070] Since the center of each randlet ranges uniformly across the whole signal block, the extremities of the randlets can reach outside of the block. This causes edge effects at the block boundaries. These edge effects may be eliminated by padding each block with a mirror signal of itself at each edge. In general, a padding of 5 to 10 pixels (e.g., for an image) is sufficient, even for very large images. [0072] Generally, a specific instance of the RT is generated to work on a specific size of signal block (e.g., an image). There are three ways to do this. First, the randlets can be chosen with centers in the range [O,l], and the transform can be expanded to the actual size of whatever signal block is chosen. One advantage of this method is that many coefficients of the transform will become scalinginvariant. However, to ensure that this transform will scale well for large data blocks, an enormous number of randlets may need to be chosen. These randlets will be redundant on small signals, but necessary to enable the transform to be taken to large scales. [0073] Another method is to define the transform for a maximum signal block size. This method is similar to the previous method, except that the number of basis functions can be bounded, since the maximum block size is known. There is still the problem of redundant basis functions on smaller blocks, though. [0074] The third method is to generate the transform for a relatively small block, e.g. images of 50 x 50 or 100 x 100. Any block that is larger than this size is decomposed into blocks of this size, transform is performed separately on all blocks. This method may be beneficial for transforms, because it avoids the redundant basis functions of the previous two methods. However, the first method is useful for applications of the RT such as hashing and watermarking, where a small number of basis functions can be used. These are further discussed below under the same titles. [0075] Furthermore, since most signal blocks will not come in integer multiples of the block size, the blocks may be padded with zero values to achieve a size that is a multiple of the block size. This padding may be removed as part of the inverse transform or reconstruction discussed below. [0076] In one implementation, the basis functions need not be completely and independently random. For example, the first basis function may be chosen completely randomly. For each subsequent basis function, a set of linear constraints may be generated which include constraints that ensure orthogonality to all previously-chosen basis functions andlor normalization. Such constraints * may also ensure that the shape of the basis function is a randlet. The next basis function may then be randomly chosen fiom the functions which fulfill the constraints. As additional basis functions are chosen, it may however become harder for functions to fulfill all of the constraints. In this situation, the next basis function may be chosen randomly fiom among the functions which approximately fulfill the constraints (e.g., almost orthogonal), such as defined by some threshold which may vary with the size of the desired basis function. In one implementation, this process can be implemented by an optimization algorithm. [0078] Fig. 6 illustrates an exemplary method 600 for RT-based compression. After quantization (e.g., stage 5 10 of Fig. 5), many of the transform coefficients may be zero. This distribution of coefficients lends itself very well to compression because these coefficients may be eliminated (602). [0079] Moreover, lossy compression may be performed to an arbitrary level by throwing out coefficients corresponding to the smallest randlets (602). With respect to the sorted list of randlets discussed with reference to Fig. 4, lossy compression may be achieved by using only the randlets near the beginning of the list, ignoring the randlets at the end of the list. Other lossy compression techniques may also be utilized such as: (1) the coefficients can be compressed more harshly; and/or (2) thresholds may be applied to the value of the coefficients, e.g., throwing out coefficients where the magnitude (e.g., absolute value) is below a certain threshold. [OOSO] Furthermore, the rate of lossy compression can be varied dynamically as well, so the amount of bandwidth spent on a signal block is made accordingly to the bandwidth available. Also, an image can be sent iteratively so that the basic representation appears first, and the details are filled in later. Moreover, when the list of basis functions is sorted by size (as discussed with reference to Fig. 4), this happens automatically. [0082] Fig. 7 illustrates an exemplary method 700 for RT-based denoising. First, the small basis functions are de-emphasized (702). Then, the super-position of the remaining basis functions cancels out much of the noise (704). [0084] The RT is an ideal tool for multimedia signal hashing such as image hashing. Even though this section discusses image hashing specifically in portions, it is envisioned RT based hashing may be generally applied to signals as will be discussed with reference to Fig. 8. [0085] With respect to image hashing, the generated hash value is believed to be robust to perturbations in the image, and the randomized nature of the basis functions ensures that the hash is hard to predict. A modified version of the RT of Fig. 5 may be used for hashing, because there are fewer requirements to hash than for the full transform. In particular, when using a transform to generate hash values, it is not necessary to be able to invert the hash values to produce the original signal. Therefore, many fewer coefficients are used when hashing than when performing a full image transform. [0086] Additionally, when hashing, it may be valuable to have each coefficient taken from a same distribution as all of the other coefficients, when taken over all images, for example. Therefore, the use of residues is not done when the RT is used for hashing. This simplifies the hashing algorithm and ensures that the power of hash coefficients are not reduced by previous randlets. Also, when residues are taken, later coefficients depend on earlier coefficients, so a small perturbation in a signal can cause large changes in later coefficients. This is an undesirable property for an approximate hash. [0087] In an implementation, the hashed vector can be quantized using a suitable lattice. For example, one can have a public key lattice for which a private key allows quantization easily, whereas quantization from the public key may introduce more errors. Accordingly, the public key basis would be the image of a private key basis for the lattice under a suitable unimodular matrix transformation. Moreover, the quantization also allows one to ignore small changes. [OOSS] Furthermore, when choosing a transform for a hash, the randlets do not have to be sorted by size (such as discussed with reference to Fig. 4). As a illustrated in Fig. 8, an RT-based hashing is done by first scaling the signal to a set size (802), for example 256 x 256, and then projecting each of the selected randlets directly onto the signal (804), without using residues. The transform coefficients are computed (806) (as discussed with reference to Fig. 5). The coefficients that are produced are then (heavily) quantized (808). [0089] Finally, error correction is applied to the quantized transform coefficients (810) and the coefficients are stored (8 12). In an implementation, an error-correcting code's decoder is used to shrink the hash value and make it even more resistant to perturbations. [0090] HASHINGF OR IDENTIFICATION/AUTHENTICATION [0091] Images (and signals generally) can be compared by performing an RT-based hashing (as discussed with reference to Fig. 8) and comparing the various hash values. However, for image identification or authentication, the errorcorrecting decoding is not necessary (810). As a result, each signal or image is associated with a vector of quantized transform coefficients. By comparing the vectors of coefficients based on a distance metric, signals can quickly be compared. [0092] In an implementation, the L2 norm is utilized. It is envisioned that the L, norm may produce better results, where n is large (since it magnifies large differences between coefficients while downplaying smaller differences). CI [0093] Coefficients can be compared directly, or as ratios. For example, comparing the ratios of statistics in one image to the ratios of the same statistics in other images can help to defeat equalization attacks. This is similar to normalizing the transform coefficients. Alternately, statistics can be formed which are functions of subsets of coefficients. Again, these can be compared directly, or as ratios. [0095] Fig. 9 illustrates an exemplary method 900 for RT-based watermarking. It is envisioned that the method 900 may more generally be utilized for data embedding. In watermarking (or more generally data embedding), the RT is defined for a relatively small number of unsorted randlets and no residues are taken, just like in RT-based hashing (see the discussion of Fig. 8 above). First, the signal size is scaled (902). For an image signal, the transform is defined on an image of canonical size, [O, I] x [0, I] and is scaled to the size of the image that is presented. The transform is performed by projecting the randlets directly onto the signal (904) and computing the transform coefficients (906) such as discussed with reference to Figs. 5 and 8. [0096] The watermark is then applied to the transform coefficients (908), which are inserted back into the signal (910), e.g., via a minimum-norm matrix solution to inverting the transform. To ensure that the matrix is well-behaved, the randlets may be chosen so that they do not substantially overlap. This may make it easier to identi@ and defeat the watermark, however. [0098] Fig. 10 illustrates an exemplary method 1000 for reconstruction of a signal transformed using RT. Because residues are used when taking the transform (as discussed with reference to Fig. 5), the projection of each randlet is orthogonal to the previous randlets. This means that the original image can be reconstructed by simply adding up the projection of each randlet. That is, multiply each randlet by the corresponding transform coefficient (1002) and add them together (1004) to provide the input signal (1006). [0099] For example, if I[i, j] is the image, then: [OOl 011 In one implementation, the reconstruction method 1000 can be applied to almost-orthogonal basis hctions. Accordingly, the reconstruction method 1000 may be applied when residues are used, when the basis functions are orthogonal, or when the basis functions are almost orthogonal. [00103] Fig. 11 illustrates a general computer environment 1100, which can be used to implement the techniques described herein. For example, the computer environment 1100 may be utilized to execute instructions associated with performing the tasks discussed with reference to the previous figures. The computer environment 1100 is only one example of a computing environment and is not intended to suggest any limitation as to the scope of use or hnctionality of the computer and network architectures. Neither should the computer environment 1100 be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the exemplary computer environment 1100. [OO 1041 Computer environment 1 100 includes a general-purpose computing device in the form of a computer 1102. The components of computer 1102 can include, but are not limited to, one or more processors or processing units 11 04 (optionally including a cryptographic processor or co-processor), a system memory 1 106, and a system bus 1 108 that couples various system components including the processor 1 104 to the system memory 1 106. [00 1051 The system bus 11 08 represents one or more of any of several types of bus structures, including a memory bus or memory controller, a peripheral bus, an accelerated graphics port, and a processor or local bus using any of a variety of bus architectures. By way of example, such architectures can include an Industry Standard Architecture (ISA) bus, a Micro Channel Architecture (MCA) bus, an Enhanced ISA (EISA) bus, a Video Electronics Standards Association (VESA) local bus, and a Peripheral Component Interconnects (PCI) bus also known as a Mezzanine bus. a [00106] Computer 1102 typically includes a variety of computer-readable media. Such media can be any available media that is accessible by computer 11 02 and includes both volatile and non-volatile media, removable and non-removable media. [00107] The system memory 1 106 includes computer-readable media in the form of volatile memory, such as random access memory (RAM) 1110, and/or non-volatile memory, such as read only memory (ROM) 1112. A basic inputJoutput system (BIOS) 1114, containing the basic routines that help to transfer information between elements within computer 11 02, such as during startup, is stored in ROM 11 12. RAM 11 10 typically contains data and/or program modules that are immediately accessible to and/or presently operated on by the processing unit 1 104. [00 1081 Computer 1102 may also include other removablelnon-removable, volatilelnon-volatile computer storage media. By way of example, Fig. 11 illustrates a hard disk drive 11 16 for reading from and writing to a non-removable, non-volatile magnetic media (not shown), a magnetic disk drive 11 18 for reading from and writing to a removable, non-volatile magnetic disk 1120 (e.g., a "floppy disk"), and an optical disk drive 1122 for reading from and/or writing to a removable, non-volatile optical disk 1124 such as a CD-ROM, DVD-ROM, or other optical media. The hard disk drive 1116, magnetic disk drive 1118, and optical disk drive 1122 are each connected to the system bus 1108 by one or more data media interfaces 1126. Alternatively, the hard disk drive 11 16, magnetic disk drive 11 18, and optical disk drive 1122 can be connected to the system bus 1108 by one or more interfaces (not shown). [00109] The disk drives and their associated computer-readable media provide non-volatile storage of computer-readable instructions, data structures, program modules, and other data for computer 1102. Although the example illustrates a hard disk 1116, a removable magnetic disk 1120, and a removable optical disk 1124, it is to be appreciated that other types of computer-readable media which can store data that is accessible by a computer, such as magnetic cassettes or other magnetic storage devices, flash memory cards, CD-ROM, digital versatile disks (DVD) or other optical storage, random access memories (RAM), read only memories (ROM), electrically erasable programmable read-only memory (EEPROM), and the like, can also be utilized to implement the exemplary computing system and environment. [OOllO] Any number of program modules can be stored on the hard disk 11 16, magnetic disk 1120, optical disk 1124, ROM 11 12, andlor RAM 11 10, including by way of example, an operating system 1126, one or more application programs 1128, other program modules 11 30, and program data 1132. Each of such operating system 1126, one or more application programs 1128, other program modules 1130, and program data 11 32 (or some combination thereof) 4 may implement all or part of the resident components that support the distributed file system. [OOlll] A user can enter commands and information into computer 11 02 via input devices such as a keyboard 1134 and a pointing device 1136 (e.g., a "mouse"). Other input devices 1138 (not shown specifically) may include a microphone, joystick, game pad, satellite dish, serial port, scanner, andlor the like. These and other input devices are connected to the processing unit 1104 via inputloutput interfaces 1140 that are coupled to the system bus 1108, but may be connected by other interface and bus structures, such as a parallel port, game port, or a universal serial bus (USB). [00112] A monitor 1142 or other type of display device can also be connected to the system bus 1108 via an interface, such as a video adapter 1144. In addition to the monitor 1142, other output peripheral devices can include components such as speakers (not shown) and a printer 1146 which can be connected to computer 1 102 via the inputloutput interfaces 1 140. [00113] Computer 1102 can operate in a networked environment using logical connections to one or more remote computers, such as a remote computing device 1148. By way of example, the remote computing device 1148 can be a personal computer, portable computer, a server, a router, a network computer, a peer device or other common network node, game console, and the like. The remote computing device 1148 is illustrated as a portable computer that can * include many or all of the elements and features described herein relative to computer 1 102. [00114] Logical connections between computer 1102 and the remote computer 1148 are depicted as a local area network (LAN) 1150 and a general wide area network (WAN) 11 52. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets, and the Internet. [00115] When implemented in a LAN networking environment, the computer 1 102 is connected to a local network 1 150 via a network interface or adapter 1154. When implemented in a WAN networking environment, the computer 1102 typically includes a modem 1156 or other means for establishing communications over the wide network 1152. The modem 1156, which can be internal or external to computer 11 02, can be connected to the system bus 11 08 via the input/output interfaces 1140 or other appropriate mechanisms. It is to be appreciated that the illustrated network connections are exemplary and that other means of establishing communication link(s) between the computers 1102 and 1 148 can be employed. [00116] In a networked environment, such as that illustrated with computing environment 1100, program modules depicted relative to the computer 1102, or portions thereof, may be stored in a remote memory storage device. By way of example, remote application programs 11 58 reside on a memory device of remote computer 1148. For purposes of illustration, application programs and other Ilr executable program components such as the operating system are illustrated herein as discrete blocks, although it is recognized that such programs and components reside at various times in different storage components of the computing device 11 02, and are executed by the data processor(s) of the computer. [00117] Various modules and techniques may be described herein in the general context of computer-executable instructions, such as program modules, executed by one or more computers or other devices. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. Typically, the hctionality of the program modules may be combined or distributed as desired in various implementations. [OOllS] An implementation of these modules and techniques may be stored on or transmitted across some form of computer-readable media. Computerreadable media can be any available media that can be accessed by a computer. By way of example, and not limitation, computer-readable media may comprise "computer storage media" and "communications media." [00119] "Computer storage media" includes volatile and non-volatile, removable and non-removable media implemented in any method or technology for storage of information such as computer-readable instructions, data structures, program modules, or other data. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, II CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by a computer. [00120] "Communication media" typically includes computer-readable instructions, data structures, program modules, or other data in a modulated data signal, such as carrier wave or other transport mechanism. Communication media also includes any information delivery media. The term "modulated data signal" means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, radio fiequency (RF), infrared (IR), wireless fidelity (e.g., IEEE 802.11b wireless networking) (Wi-Fi), cellular, Bluetooth enabled, and other wireless media. Combinations of any of the above are also included within the scope of computer-readable media. [00122] Although the invention has been described in language specific to structural features andor methodological acts, it is to be understood that the invention defined in the appended claims is not necessarily limited to the specific features or acts described. For example, the techniques discussed herein may be applied to audio signals, images, andor video signals (i.e., one, two, or three m dimensional signals, respectively). Hence, the specific features and acts are disclosed as exemplary forms of implementing the claimed invention. CLAIMS What is claimed is: 1. A method comprising: randomly selecting a plurality of generated basis functions; and applying the randomly selected basis functions to a signal. 2. A method as recited by claim 1, wherein the basis functions are generated from a set of functions that are selected from one or more items of a group comprising one-dimensional, two-dimensional, and three-dimensional functions. 3. A method as recited by claim 1, wherein each of the basis functions is generated by an act selected from a group comprising scaling, rotating, translating, discretizing, and normalizing a mother randlet. 4. A method as recited by claim 3, wherein the basis functions are constrained by allowing only a finite set of scaling and rotation operations. 5. A method as recited by claim 3, wherein instead of defining each basis function independently of all others, a library of non-translated basis functions is generated by randomly scaling and rotating the mother randlets. 6. A method as recited by claim 3, wherein when scaling, a wavelet family is chosen. 7. A method as recited by claim 3, wherein the mother randlet is selected from a group comprising Gaussian, half, Mexican Hat, wavelet randlets, and combinations thereof. 8. A method as recited by claim 1, wherein the applying comprises: projecting each selected basis function onto the signal; subtracting each projection from the signal; projecting each selected basis function onto a residue of the previous basis function; ' computing a transform coefficient for each basis function; quantizing the transform coefficients; storing the quantized transform coefficients; and computing a next residue. 9. A method as recited by claim 1, wherein the method is used for compressing the signal and the applying comprises: projecting each selected basis function onto the signal; subtracting each projection from the signal; computing a transform coefficient for each basis function; quantizing the transform coeflicients; eliminating select quantized transform coeficients; and storing the quantized transform coefficients. 10. A method as recited by claim 1, wherein the method is used for denoising the signal by de-emphasizing relatively smaller basis functions and superpositioning remaining basis functions. 1 1. A method as recited by claim 1, wherein the method is used for hashing the signal and the applying comprises: scaling the signal; projecting each selected basis function onto the scaled signal; computing a transform coeficient for each basis function; ' quantizing the transform coefficients; applying error correction to the quantized transform coefficients; and storing the quantized transform coeficients. 12. A method as recited by claim 1 1, wherein a value of the hashed signal is utilized for identification or authentication. 13. A method as recited by claim 1, wherein the method is used for watermarking the signal and the applying comprises: scaling the signal; projecting each selected basis function onto the scaled signal; computing a transform coefficient for each basis function; applying a watermark to the transform coefficients; and inserting the watermark into the signal. 14. A method as recited by claim 1, wherein the applying provides a transformed signal and the transformed signal is reconstructed by acts comprising: multiplying each basis function by a corresponding transform coeacient; and summing results of the multiplying. 1 5. A system comprising: a randlet transform (RT) module to receive a signal and apply a plurality of randomly selected basis functions to the signal; and a pseudorandom generator coupled to the RT module to generate a random number utilized by the RT module to select the randomly selected basis functions. 16. A system as recited by claim 15, wherein the pseudorandom generator utilizes a secret key as a seed to generate the random number. 17. A system as recited by claim 16, wherein the seed is a bit stream. 18. A system as recited by claim 15, wherein each of the basis hnctions is generated by scaling, rotating , translating , discretizing, and normalizing a mother randlet. 19. One or more computer-readable media having instructions stored thereon that, when executed, direct a machine to perform acts comprising: randomly selecting a plurality of generated basis functions; and applying the randomly selected basis hnctions to a signal. 20. One or more computer-readable media as recited by claim 19, wherein the basis functions are generated from a set of functions that are selected from one or more items of a group comprising one-dimensional, twodimensional, and three-dimensional functions. P 2 1. One or more computer-readable media as recited by claim 19, wherein each of the basis functions is generated by scaling, rotating, translating, discretizing, and' normalizing a mother randlet. 22. One or more computer-readable media as recited by claim 21, wherein the basis functions are constrained by allowing only a finite set of scaling and rotation operations. 23. One or more computer-readable media as recited by claim 2 1, wherein instead of defining each basis function independently of all others, a library of non-translated basis functions is generated by randomly scaling and rotating the mother randlets. 24. One or more computer-readable media as recited by claim 2 1, wherein when scaling, a wavelet family is chosen. 25. One or more computer-readable media as recited by claim 21, wherein the mother randlet is selected &om a group comprising Gaussian, half, Mexican Hat, wavelet randlets, and combinations thereof. 26. One or more computer-readable media as recited by claim 19, wherein the applying comprises: projecting each selected basis function onto the signal; subtracting each projection from the signal; projecting each selected basis function onto a residue of the previous basis function; computing a transform coefficient for each basis function; quantizing the transform coeficients; storing the quantized transform coefficients; and computing a next residue. 27. One or more computer-readable media as recited by claim 19, wherein the acts are used for compressing the signal and the applying comprises: projecting each selected basis function onto the signal; subtracting each projection from the signal; computing a transform coeficient for each basis function; quantizing the transform coefficients; eliminating select quantized transform coeficients; and storing the quantized transform coefficients. 28. One or more computer-readable media as recited by claim 19, wherein the acts are used for denoising the signal by de-emphasizing relatively smaller basis hctions and super-positioning remaining basis functions. 29. One or more computer-readable media as recited by claim 19, wherein the acts are used for hashing the signal and the applying comprises: scaling the signal; projecting each selected basis function onto the scaled signal; computing a transform coefficient for each basis function; quantizing the transform coefficients; applying error correction to the quantized transform coefficients; and storing the quantized transform coefficients. 30. One or more computer-readable media as recited by claim 29, wherein a value of the hashed signal is. utilized for identification or authentication. 3 1. One or more computer-readable media as recited by claim 19, wherein the acts are used for watermarking the signal and the applying comprises: scaling the signal; projecting each selected basis function onto the scaled signal; computing a transform coefficient for each basis function; applying a watermark to the transform coefficients; and inserting the watermark into the signal. 32. One or more computer-readable media as recited by claim 19, wherein the applying provides a transformed signal and the transformed signal is reconstructed by acts comprising: multiplying each basis function by a corresponding transform coefficient; and summing results of the multiplying.

Full Text

RANDOMIZED SIGNAL TRANSFORMS AND THEIR
APPLICATIONS
TECHNICAL FIELD
[OOOl] The present invention generally relates to signal transforms, and
more particularly, to randomized signal transforms andor their applications.
BACKGROUND
[0002] As digital communication becomes more commonplace, the need for
securing andlor authenticating the transferred digital data becomes increasingly
more important. Digital signals carrying digital data is often (if not always)
transformed into a specific format (e.g., by a transform) prior to being transferred.
For example, a file containing digital data may be compressed prior to sending it
over the Internet.
[00031 , Since more powerhl computers, high-speed Internet connections,
and superior compression technologies are available to most users, the demand for
digital media content is greater than ever. With instant and anytime access to
literally millions of their favorite music and videos, consumers are applauding the
convenience that digital distribution has afforded them. They enjoy being able to
download or stream music to their hard drive or personal computer hard drive as
fluidly as any television broadcast.
*
[0004] While the demand for digital content grows, however, so does the
potential for its unauthorized use. Without a secure distribution system in place,
digital media files can be easily copied or compressed into smaller files without
the content owner's authorization. These files can then be transferred across the
Internet for others to use or distribute freely. This violates the copyrights held by
thousands of media companies, record labels, filmmakers, and recording artists.
Such unauthorized use also strips these entities of valuable revenues as well.
[OOOS] One current approach is to encrypt the digital content to limit its
unauthorized use. This approach, however, introduces additional overhead which
can reduce the speed of systems utilizing signal transformation.
[0006] Accordingly, signal transformation solutions are desired which
provide additional security while limiting performance degradation.
SUMMARY
[0007] Techniques are disclosed to provide randomized signal transforms
and/or their applications. More particularly, a signal (e.g., an audio or video signal)
is transformed by applying randomly-selected basis hctions to the signal. The
applications of the randomized signal transforms include, but are not limited to,
compression, denoising, hashing, identification, authentication, and data
embedding (e.g., watermarking).
BRIEF DESCRIPTION OF THE DRAWINGS
[OOOS] The detailed description is described with reference to the
accompanying figures. In the figures, the left-most digit(s) of a reference number
identifies the figure in which the reference number first appears. The use of the
same reference numbers in different figures indicates similar or identical items.
[0009] Fig. 1 illustrates an exemplary randlet transform (RT) system.
[00 lo] Fig. 2 illustrates an exemplary RT method.
[OOll] Fig. 3 illustrates an exemplary method for generating RT basis
functions.
[0012] Fig. 4 illustrates an exemplary method for generating an RT basis
functions library.
[OO 131 Fig. 5 illustrates an exemplary method for applying RT
transformations.
[0014] Fig. 6 illustrates an exemplary method for RT-based compression.
[0015] Fig. 7 illustrates an exemplary method for RT-based denoising.
[OO 161 Fig. 8 illustrates an exemplary method for RT-based hashing.
[0017] Fig. 9 illustrates an exemplary method for RT-based watermarking.
[OOl 81 Fig. 10 illustrates an exemplary method for reconstruction of a signal
transformed using RT.
9
[0019] Fig. 11 illustrates a general computer environment 1100, which can
be used to implement the techniques described herein.
DETAILED DESCRIPTION
[0020] The following disclosure generally describes techniques for
improving signal transformation. More specifically, a family of signal transforms,
referred to herein as randlet transforms (RTs), are applied to signals (such as audio
and/or video signals) to provide security, while maintaining reasonable
performance. Each family member transform uses a set of basis hnctions (also
referred to herein as "randlets") that are chosen randomly or pseudorandomly
based on a secret key (K). In various described implementations, the application of
RT can result in improved data embedding (e.g., watermarking), identification,
authentication, hashing, denoising, and/or compression.
[0022] Fig. 1 illustrates an exemplary randlet transform (RT) system 100.
An RT module 102 receives input data (104) such as an audio andlor video signal.
The signal may be provided by a computer-readable medium, by a source
connected to a computer network (e.g., an intranet, the Internet, a wireless
network, etc.), and the like (as will be further discussed with reference to the
computing environment of Fig. 11).
*
[0023] The RT module 102 transforms the input signal using a set of basis
functions (106) that are selected randomly. The randomness is provided by a
random number generated (or multiple random numbers generated) by a
pseudorandom generator (108). In an implementation, the pseudorandom
generator (108) is seeded by a secret key (K) (110). The secret key (K) may be
provided as a bit stream. In one implementation, the generator 108 is a
cryptologically-strong pseudorandom generator. The output of the RT module 102
(e.g., a vector) can be used for a number of applications (112), which will be
further discussed, for example, with reference to Figs. 6- 10.
[0024] Fig. 2 illustrates an exemplary RT method 200. After RT basis
functions are generated (202) (as will be further discussed with reference to Figs. 3
and 4), a number of the generated basis functions are selected at random (204)
such as discussed with reference to Fig. 1. In an implementation, a secret key (K)
(e.g., used as a seed for a pseudorandom number generator) specifies which basis
functions should be selected for a particular instance. An input signal (104) is then
b
transformed by applying the randomly selected basis functions (206). In an
implementation, the input signal may be divided into blocks as will be mher
discussed with reference to Fig. 5, for example.
[0025] Moreover, the RT may be applied as a discrete transform. The
provided randomness may give the RT two distinct advantages. First, it is useful
for security purposes because an attacker cannot know which basis functions are
9'
used in the transform, making attacks relatively much more difficult. Second,
because the basis is chosen at random from a relatively large set of basis functions,
the worst-case performance of the transform occurs with relatively low probability.
The measure for the RT is therefore the average-case performance rather than the
worst-case performance.
[0027] The basis functions (also referred to herein as "randlets") are based
on a set of two-dimensional functions called "mother randlets." A variety of
mother randlets are discussed below. It is envisioned that basis functions that are
one-dimensional, two-dimensional, or three-dimensional (e.g., corresponding to
audio signals, images, and video signals, respectively) may be utilized.
[0028] Fig. 3 illustrates an exemplary method 300 for generating RT basis
functions. Generally, a randlet is produced by scaling (302), rotating (304),
translating (306), discretizing (308), and normalizing (310) a mother randlet.
Other orders of stages 302, 304, 306, and/or 308-310 are also envisioned.
Furthermore, rotation may not be done for certain distributions such as
symmetrical Gaussian distributions (i.e., rotation of a circle is not done).
[0029] In an implementation, given a mother randlet m(x,y) , a randlet with
horizontal translation a, vertical translation b, horizontal scaling a, vertical
scaling P, and rotation 6 would be:
[0033] Accordingly, to choose the specific randlets used in an instance of
the RT, the secret key (K) is used to seed a pseudorandom number generator (such
as 108 of Fig. 1). And, whenever a random number is needed, it is taken &om this
pseudorandom number generator.
[0035] Fig. 4 illustrates an exemplary method 400 for generating an RT
basis functions library. Generally, it is possible to define an RT basis by choosing
all randlets independently and at random. In one implementation, however, this is
unnecessary for practical reasons, as equal performance can be achieved by
slightly constraining the choices of randlets. Furthermore, by limiting the choices
of randlets, computational performance may be significantly improved.
[0036] In an implementation, the basis fbnctions are constrained by
allowing only a finite set of scaling and rotation operations, instead of choosing
the scaling and rotation independently for each randlet. Instead of defining each
randlet independently of all others, a random library of non-translated randlets is
generated. These randlets are known as "step-mother randlets," and are generated
by randomly scaling and rotating the mother randlets (402 and 404, respectively).
This set of all step-mother randlets may be referred to as the "library" (406).
100371 Each mother randlet is scaled randomly in both directions. The
distributions for the scaling depend on both the specific mother randlet and the
application. Examples are given in later sections. For each scaled mother randlet,
the number of rotations generated may be proportional to the perimeter.
[0038] The step-mother randlets are translated (408), discretized (410), and
normalized (412). Because a step-mother randlet is a discretized version of a
mother randlet that has been scaled and rotated by real numbers, the normalization
constant is determined by setting the inner product of the randlet with itself equal
to 1. Hence:
[0041] Note that K depends on a and P .
[0042] The following several important values are parameters for the
creation of an RT basis:
[0043] n: The total number of basis functions.
: The width and height of the block to be transformed,
respectively.
[0045] FC): An algorithm which determines the type of each randlet.
[0046] The full set of randlets is generated by randomly choosing and
translating (408) step-mother randlets from the library. This is done by generating
a list of n 3-tuples, with each one representing one randlet that will be used in the
transform: . In the 3-tuples, i is in index to the library, and so implicitly
determines the scaling and rotation of the randlet. i is chosen at random by the
function FC). The exact function F used depends on the application. a and b are
the real-valued horizontal and vertical translation of center point of the randlet,
chosen uniformly at random from [O,T] and [O,U], respectively. In an
implementation, once the list has been generated, it is sorted according to the size
of the randlets, e.g., with the largest randlets first and the smallest randlets last.
[0048] As discussed above, mother randlets are the base randlets from
which all others are created as discussed with reference to Fig. 4. Mother randlets
are two-dimensional real-valued functions with localized effective support,
centered around (0,O). There are generally two types of mother randlets, lowfrequency
randlets and high-frequency randlets. Both types of randlets have a
Gaussian shape in the horizontal direction. In the vertical direction, low-frequency
randlets have a Gaussian shape while high-frequency randlets have an oscillatory
i
shape. The only high-frequency randlet is also known as the Gaussian randlet. It is
usell for finding low-frequency components of an image or audio content. It has
a Gaussian shape in both the horizontal and vertical directions, although each
direction can have different widths.
[0049] Gaussian Randlet:
[0051] High-frequency randlets have a Gaussian shape in the horizontal
direction and various oscillatory shapes in the vertical direction. Since they will be
rotated, we refer to the smooth direction as the direction of the Gaussian, and the
rough direction as the direction of the oscillatory function. The variations in the
vertical direction give these randlets edge-detection properties in the horizontal
direction. When rotated by B degrees, they will tend to detect edges at B degrees.
Other types of randlets include:
[0052] Half Randlet:
[0053] 0~x2+uyy2 m(x, Y) = we
[0054] Mexican Hat Randlet:
[0055] m(x, y) = q2e"=x2+cY~2
[0056] Wavelet Randlet:
[0057] m(x, y) = CDv(y)eUxx2
[0058] The w@ portion of the wavelet randlet is a one-dimensional wavelet
function. In an implementation, when scaling a wavelet randlet, instead of
choosing a wavelet of fixed size, a wavelet family can be chosen, and instead of
scaling, a longer or shorter member of the wavelet family can be chosen.
[0059] Generally, high-frequency randlets are scaled so that the randlet is
longer in the smooth direction than in the rough direction. This enhances the
randlet's ability to detect edges.
[0060] In an implementation, the mother randlets may be obtained by
combinations of the Gaussian, half, Mexican Hat, andor wavelet randlets.
[0061] RT TRANSFORMATION
[0062] Fig. 5 illustrates an exemplary method 500 for applying RT
transformations. The transform is done by projecting each randlet onto the signal
in turn (502). The randlets may be selected pseudorandomly (e.g., as discussed
with reference to Figs. 1-2). After each projection is taken, it is subtracted from the
signal (504). What remains of the signal after the subtraction is called the
"residue." The RT transformation method 500 continues by projecting each
selected randlet onto the residue of the previous randlet (506). In this manner, the
transform converges to the original signal, and the power of the coefficients tends
to fall exponentially.
[0063] A transform coefficient k is computed (508) for each randlet by
finding the inner product of randlet k and the residue of randlet k-1. If the randlet k
is denoted by rk, the residue of randlet rn is denoted by R,, and coefficient n is
denoted by c, , then:
[0065] As each coefficient is generated, it is quantized (510), and it is the
quantized value that is stored (512) as the coefficient in the transform. In
accordance with one implementation, it is also this quantized value that is
subtracted fiom the signal (504). In an implementation, a uniform quantizer is
used, basing the number of levels on type and scaling of the randlet. Randomized
rounding may also be used, e.g., to round the coefficient based on a random
number. The effects of randomized rounding may be accommodated by the
iterative convergence of the algorithm.
[0066] Once the quantization is complete, the next residue is computed
(514). If Qc) is the quantizer, then:
[0068] In an implementation, the randlets are not projected upon the entire
signal block. The effective footprint of the randlets is computed in a preprocessing
phase (not shown) by considering only the area where the randlets have nonnegligible
value. The randlets are then only projected in that area.
[0069] In an alternative implementation, the basis functions are placed as
normal and then their positions are perturbed to the nearby location of maximum
power. This makes the transform converge with fewer coefficients, but extra
information would have to be stored with each coefficient giving the horizontal
and vertical perturbation.
[0070] Since the center of each randlet ranges uniformly across the whole
signal block, the extremities of the randlets can reach outside of the block. This
causes edge effects at the block boundaries. These edge effects may be eliminated
by padding each block with a mirror signal of itself at each edge. In general, a
padding of 5 to 10 pixels (e.g., for an image) is sufficient, even for very large
images.
[0072] Generally, a specific instance of the RT is generated to work on a
specific size of signal block (e.g., an image). There are three ways to do this. First,
the randlets can be chosen with centers in the range [O,l], and the transform can
be expanded to the actual size of whatever signal block is chosen. One advantage
of this method is that many coefficients of the transform will become scalinginvariant.
However, to ensure that this transform will scale well for large data
blocks, an enormous number of randlets may need to be chosen. These randlets
will be redundant on small signals, but necessary to enable the transform to be
taken to large scales.
[0073] Another method is to define the transform for a maximum signal
block size. This method is similar to the previous method, except that the number
of basis functions can be bounded, since the maximum block size is known. There
is still the problem of redundant basis functions on smaller blocks, though.
[0074] The third method is to generate the transform for a relatively small
block, e.g. images of 50 x 50 or 100 x 100. Any block that is larger than this size
is decomposed into blocks of this size, transform is performed separately on all
blocks. This method may be beneficial for transforms, because it avoids the
redundant basis functions of the previous two methods. However, the first method
is useful for applications of the RT such as hashing and watermarking, where a
small number of basis functions can be used. These are further discussed below
under the same titles.
[0075] Furthermore, since most signal blocks will not come in integer
multiples of the block size, the blocks may be padded with zero values to achieve
a size that is a multiple of the block size. This padding may be removed as part of
the inverse transform or reconstruction discussed below.
[0076] In one implementation, the basis functions need not be completely
and independently random. For example, the first basis function may be chosen
completely randomly. For each subsequent basis function, a set of linear
constraints may be generated which include constraints that ensure orthogonality
to all previously-chosen basis functions andlor normalization. Such constraints
*
may also ensure that the shape of the basis function is a randlet. The next basis
function may then be randomly chosen fiom the functions which fulfill the
constraints. As additional basis functions are chosen, it may however become
harder for functions to fulfill all of the constraints. In this situation, the next basis
function may be chosen randomly fiom among the functions which approximately
fulfill the constraints (e.g., almost orthogonal), such as defined by some threshold
which may vary with the size of the desired basis function. In one implementation,
this process can be implemented by an optimization algorithm.
[0078] Fig. 6 illustrates an exemplary method 600 for RT-based
compression. After quantization (e.g., stage 5 10 of Fig. 5), many of the transform
coefficients may be zero. This distribution of coefficients lends itself very well to
compression because these coefficients may be eliminated (602).
[0079] Moreover, lossy compression may be performed to an arbitrary level
by throwing out coefficients corresponding to the smallest randlets (602). With
respect to the sorted list of randlets discussed with reference to Fig. 4, lossy
compression may be achieved by using only the randlets near the beginning of the
list, ignoring the randlets at the end of the list. Other lossy compression techniques
may also be utilized such as: (1) the coefficients can be compressed more harshly;
and/or (2) thresholds may be applied to the value of the coefficients, e.g., throwing
out coefficients where the magnitude (e.g., absolute value) is below a certain
threshold.
[OOSO] Furthermore, the rate of lossy compression can be varied
dynamically as well, so the amount of bandwidth spent on a signal block is made
accordingly to the bandwidth available. Also, an image can be sent iteratively so
that the basic representation appears first, and the details are filled in later.
Moreover, when the list of basis functions is sorted by size (as discussed with
reference to Fig. 4), this happens automatically.
[0082] Fig. 7 illustrates an exemplary method 700 for RT-based denoising.
First, the small basis functions are de-emphasized (702). Then, the super-position
of the remaining basis functions cancels out much of the noise (704).
[0084] The RT is an ideal tool for multimedia signal hashing such as image
hashing. Even though this section discusses image hashing specifically in portions,
it is envisioned RT based hashing may be generally applied to signals as will be
discussed with reference to Fig. 8.
[0085] With respect to image hashing, the generated hash value is believed
to be robust to perturbations in the image, and the randomized nature of the basis
functions ensures that the hash is hard to predict. A modified version of the RT of
Fig. 5 may be used for hashing, because there are fewer requirements to hash than
for the full transform. In particular, when using a transform to generate hash
values, it is not necessary to be able to invert the hash values to produce the
original signal. Therefore, many fewer coefficients are used when hashing than
when performing a full image transform.
[0086] Additionally, when hashing, it may be valuable to have each
coefficient taken from a same distribution as all of the other coefficients, when
taken over all images, for example. Therefore, the use of residues is not done when
the RT is used for hashing. This simplifies the hashing algorithm and ensures that
the power of hash coefficients are not reduced by previous randlets. Also, when
residues are taken, later coefficients depend on earlier coefficients, so a small
perturbation in a signal can cause large changes in later coefficients. This is an
undesirable property for an approximate hash.
[0087] In an implementation, the hashed vector can be quantized using a
suitable lattice. For example, one can have a public key lattice for which a private
key allows quantization easily, whereas quantization from the public key may
introduce more errors. Accordingly, the public key basis would be the image of a
private key basis for the lattice under a suitable unimodular matrix transformation.
Moreover, the quantization also allows one to ignore small changes.
[OOSS] Furthermore, when choosing a transform for a hash, the randlets do
not have to be sorted by size (such as discussed with reference to Fig. 4). As
a
illustrated in Fig. 8, an RT-based hashing is done by first scaling the signal to a set
size (802), for example 256 x 256, and then projecting each of the selected
randlets directly onto the signal (804), without using residues. The transform
coefficients are computed (806) (as discussed with reference to Fig. 5). The
coefficients that are produced are then (heavily) quantized (808).
[0089] Finally, error correction is applied to the quantized transform
coefficients (810) and the coefficients are stored (8 12). In an implementation, an
error-correcting code's decoder is used to shrink the hash value and make it even
more resistant to perturbations.
[0090] HASHINGF OR IDENTIFICATION/AUTHENTICATION
[0091] Images (and signals generally) can be compared by performing an
RT-based hashing (as discussed with reference to Fig. 8) and comparing the
various hash values. However, for image identification or authentication, the errorcorrecting
decoding is not necessary (810). As a result, each signal or image is
associated with a vector of quantized transform coefficients. By comparing the
vectors of coefficients based on a distance metric, signals can quickly be
compared.
[0092] In an implementation, the L2 norm is utilized. It is envisioned that
the L, norm may produce better results, where n is large (since it magnifies large
differences between coefficients while downplaying smaller differences).
CI
[0093] Coefficients can be compared directly, or as ratios. For example,
comparing the ratios of statistics in one image to the ratios of the same statistics in
other images can help to defeat equalization attacks. This is similar to normalizing
the transform coefficients. Alternately, statistics can be formed which are functions
of subsets of coefficients. Again, these can be compared directly, or as ratios.
[0095] Fig. 9 illustrates an exemplary method 900 for RT-based
watermarking. It is envisioned that the method 900 may more generally be utilized
for data embedding. In watermarking (or more generally data embedding), the RT
is defined for a relatively small number of unsorted randlets and no residues are
taken, just like in RT-based hashing (see the discussion of Fig. 8 above). First, the
signal size is scaled (902). For an image signal, the transform is defined on an
image of canonical size, [O, I] x [0, I] and is scaled to the size of the image that is
presented. The transform is performed by projecting the randlets directly onto the
signal (904) and computing the transform coefficients (906) such as discussed with
reference to Figs. 5 and 8.
[0096] The watermark is then applied to the transform coefficients (908),
which are inserted back into the signal (910), e.g., via a minimum-norm matrix
solution to inverting the transform. To ensure that the matrix is well-behaved, the
randlets may be chosen so that they do not substantially overlap. This may make it
easier to identi@ and defeat the watermark, however.
[0098] Fig. 10 illustrates an exemplary method 1000 for reconstruction of a
signal transformed using RT. Because residues are used when taking the transform
(as discussed with reference to Fig. 5), the projection of each randlet is orthogonal
to the previous randlets. This means that the original image can be reconstructed
by simply adding up the projection of each randlet. That is, multiply each randlet
by the corresponding transform coefficient (1002) and add them together (1004) to
provide the input signal (1006).
[0099] For example, if I[i, j] is the image, then:
[OOl 011 In one implementation, the reconstruction method 1000 can be
applied to almost-orthogonal basis hctions. Accordingly, the reconstruction
method 1000 may be applied when residues are used, when the basis functions are
orthogonal, or when the basis functions are almost orthogonal.
[00103] Fig. 11 illustrates a general computer environment 1100, which can
be used to implement the techniques described herein. For example, the computer
environment 1100 may be utilized to execute instructions associated with
performing the tasks discussed with reference to the previous figures. The
computer environment 1100 is only one example of a computing environment and
is not intended to suggest any limitation as to the scope of use or hnctionality of
the computer and network architectures. Neither should the computer environment
1100 be interpreted as having any dependency or requirement relating to any one
or combination of components illustrated in the exemplary computer environment
1100.
[OO 1041 Computer environment 1 100 includes a general-purpose computing
device in the form of a computer 1102. The components of computer 1102 can
include, but are not limited to, one or more processors or processing units 11 04
(optionally including a cryptographic processor or co-processor), a system
memory 1 106, and a system bus 1 108 that couples various system components
including the processor 1 104 to the system memory 1 106.
[00 1051 The system bus 11 08 represents one or more of any of several types
of bus structures, including a memory bus or memory controller, a peripheral bus,
an accelerated graphics port, and a processor or local bus using any of a variety of
bus architectures. By way of example, such architectures can include an Industry
Standard Architecture (ISA) bus, a Micro Channel Architecture (MCA) bus, an
Enhanced ISA (EISA) bus, a Video Electronics Standards Association (VESA)
local bus, and a Peripheral Component Interconnects (PCI) bus also known as a
Mezzanine bus.
a
[00106] Computer 1102 typically includes a variety of computer-readable
media. Such media can be any available media that is accessible by computer 11 02
and includes both volatile and non-volatile media, removable and non-removable
media.
[00107] The system memory 1 106 includes computer-readable media in the
form of volatile memory, such as random access memory (RAM) 1110, and/or
non-volatile memory, such as read only memory (ROM) 1112. A basic
inputJoutput system (BIOS) 1114, containing the basic routines that help to
transfer information between elements within computer 11 02, such as during startup,
is stored in ROM 11 12. RAM 11 10 typically contains data and/or program
modules that are immediately accessible to and/or presently operated on by the
processing unit 1 104.
[00 1081 Computer 1102 may also include other removablelnon-removable,
volatilelnon-volatile computer storage media. By way of example, Fig. 11
illustrates a hard disk drive 11 16 for reading from and writing to a non-removable,
non-volatile magnetic media (not shown), a magnetic disk drive 11 18 for reading
from and writing to a removable, non-volatile magnetic disk 1120 (e.g., a "floppy
disk"), and an optical disk drive 1122 for reading from and/or writing to a
removable, non-volatile optical disk 1124 such as a CD-ROM, DVD-ROM, or
other optical media. The hard disk drive 1116, magnetic disk drive 1118, and
optical disk drive 1122 are each connected to the system bus 1108 by one or more
data media interfaces 1126. Alternatively, the hard disk drive 11 16, magnetic disk
drive 11 18, and optical disk drive 1122 can be connected to the system bus 1108
by one or more interfaces (not shown).
[00109] The disk drives and their associated computer-readable media
provide non-volatile storage of computer-readable instructions, data structures,
program modules, and other data for computer 1102. Although the example
illustrates a hard disk 1116, a removable magnetic disk 1120, and a removable
optical disk 1124, it is to be appreciated that other types of computer-readable
media which can store data that is accessible by a computer, such as magnetic
cassettes or other magnetic storage devices, flash memory cards, CD-ROM, digital
versatile disks (DVD) or other optical storage, random access memories (RAM),
read only memories (ROM), electrically erasable programmable read-only
memory (EEPROM), and the like, can also be utilized to implement the exemplary
computing system and environment.
[OOllO] Any number of program modules can be stored on the hard disk
11 16, magnetic disk 1120, optical disk 1124, ROM 11 12, andlor RAM 11 10,
including by way of example, an operating system 1126, one or more application
programs 1128, other program modules 11 30, and program data 1132. Each of
such operating system 1126, one or more application programs 1128, other
program modules 1130, and program data 11 32 (or some combination thereof)
4
may implement all or part of the resident components that support the distributed
file system.
[OOlll] A user can enter commands and information into computer 11 02 via
input devices such as a keyboard 1134 and a pointing device 1136 (e.g., a
"mouse"). Other input devices 1138 (not shown specifically) may include a
microphone, joystick, game pad, satellite dish, serial port, scanner, andlor the like.
These and other input devices are connected to the processing unit 1104 via
inputloutput interfaces 1140 that are coupled to the system bus 1108, but may be
connected by other interface and bus structures, such as a parallel port, game port,
or a universal serial bus (USB).
[00112] A monitor 1142 or other type of display device can also be
connected to the system bus 1108 via an interface, such as a video adapter 1144. In
addition to the monitor 1142, other output peripheral devices can include
components such as speakers (not shown) and a printer 1146 which can be
connected to computer 1 102 via the inputloutput interfaces 1 140.
[00113] Computer 1102 can operate in a networked environment using
logical connections to one or more remote computers, such as a remote computing
device 1148. By way of example, the remote computing device 1148 can be a
personal computer, portable computer, a server, a router, a network computer, a
peer device or other common network node, game console, and the like. The
remote computing device 1148 is illustrated as a portable computer that can
*
include many or all of the elements and features described herein relative to
computer 1 102.
[00114] Logical connections between computer 1102 and the remote
computer 1148 are depicted as a local area network (LAN) 1150 and a general
wide area network (WAN) 11 52. Such networking environments are commonplace
in offices, enterprise-wide computer networks, intranets, and the Internet.
[00115] When implemented in a LAN networking environment, the
computer 1 102 is connected to a local network 1 150 via a network interface or
adapter 1154. When implemented in a WAN networking environment, the
computer 1102 typically includes a modem 1156 or other means for establishing
communications over the wide network 1152. The modem 1156, which can be
internal or external to computer 11 02, can be connected to the system bus 11 08 via
the input/output interfaces 1140 or other appropriate mechanisms. It is to be
appreciated that the illustrated network connections are exemplary and that other
means of establishing communication link(s) between the computers 1102 and
1 148 can be employed.
[00116] In a networked environment, such as that illustrated with computing
environment 1100, program modules depicted relative to the computer 1102, or
portions thereof, may be stored in a remote memory storage device. By way of
example, remote application programs 11 58 reside on a memory device of remote
computer 1148. For purposes of illustration, application programs and other
Ilr
executable program components such as the operating system are illustrated herein
as discrete blocks, although it is recognized that such programs and components
reside at various times in different storage components of the computing device
11 02, and are executed by the data processor(s) of the computer.
[00117] Various modules and techniques may be described herein in the
general context of computer-executable instructions, such as program modules,
executed by one or more computers or other devices. Generally, program modules
include routines, programs, objects, components, data structures, etc. that perform
particular tasks or implement particular abstract data types. Typically, the
hctionality of the program modules may be combined or distributed as desired in
various implementations.
[OOllS] An implementation of these modules and techniques may be stored
on or transmitted across some form of computer-readable media. Computerreadable
media can be any available media that can be accessed by a computer. By
way of example, and not limitation, computer-readable media may comprise
"computer storage media" and "communications media."
[00119] "Computer storage media" includes volatile and non-volatile,
removable and non-removable media implemented in any method or technology
for storage of information such as computer-readable instructions, data structures,
program modules, or other data. Computer storage media includes, but is not
limited to, RAM, ROM, EEPROM, flash memory or other memory technology,
II
CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic
cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices,
or any other medium which can be used to store the desired information and which
can be accessed by a computer.
[00120] "Communication media" typically includes computer-readable
instructions, data structures, program modules, or other data in a modulated data
signal, such as carrier wave or other transport mechanism. Communication media
also includes any information delivery media. The term "modulated data signal"
means a signal that has one or more of its characteristics set or changed in such a
manner as to encode information in the signal. By way of example, and not
limitation, communication media includes wired media such as a wired network or
direct-wired connection, and wireless media such as acoustic, radio fiequency
(RF), infrared (IR), wireless fidelity (e.g., IEEE 802.11b wireless networking)
(Wi-Fi), cellular, Bluetooth enabled, and other wireless media. Combinations of
any of the above are also included within the scope of computer-readable media.
[00122] Although the invention has been described in language specific to
structural features andor methodological acts, it is to be understood that the
invention defined in the appended claims is not necessarily limited to the specific
features or acts described. For example, the techniques discussed herein may be
applied to audio signals, images, andor video signals (i.e., one, two, or three
m
dimensional signals, respectively). Hence, the specific features and acts are
disclosed as exemplary forms of implementing the claimed invention.

CLAIMS
What is claimed is:
1. A method comprising:
randomly selecting a plurality of generated basis functions; and
applying the randomly selected basis functions to a signal.
2. A method as recited by claim 1, wherein the basis functions are generated
from a set of functions that are selected from one or more items of a group
comprising one-dimensional, two-dimensional, and three-dimensional
functions.
3. A method as recited by claim 1, wherein each of the basis functions is
generated by an act selected from a group comprising scaling, rotating,
translating, discretizing, and normalizing a mother randlet.
4. A method as recited by claim 3, wherein the basis functions are constrained
by allowing only a finite set of scaling and rotation operations.
5. A method as recited by claim 3, wherein instead of defining each basis
function independently of all others, a library of non-translated basis
functions is generated by randomly scaling and rotating the mother
randlets.
6. A method as recited by claim 3, wherein when scaling, a wavelet family is
chosen.
7. A method as recited by claim 3, wherein the mother randlet is selected from
a group comprising Gaussian, half, Mexican Hat, wavelet randlets, and
combinations thereof.
8. A method as recited by claim 1, wherein the applying comprises:
projecting each selected basis function onto the signal;
subtracting each projection from the signal;
projecting each selected basis function onto a residue of the previous
basis function;
' computing a transform coefficient for each basis function;
quantizing the transform coefficients;
storing the quantized transform coefficients; and
computing a next residue.
9. A method as recited by claim 1, wherein the method is used for
compressing the signal and the applying comprises:
projecting each selected basis function onto the signal;
subtracting each projection from the signal;
computing a transform coefficient for each basis function;
quantizing the transform coeflicients;
eliminating select quantized transform coeficients; and
storing the quantized transform coefficients.
10. A method as recited by claim 1, wherein the method is used for denoising
the signal by de-emphasizing relatively smaller basis functions and superpositioning
remaining basis functions.
1 1. A method as recited by claim 1, wherein the method is used for hashing the
signal and the applying comprises:
scaling the signal;
projecting each selected basis function onto the scaled signal;
computing a transform coeficient for each basis function; '
quantizing the transform coefficients;
applying error correction to the quantized transform coefficients; and
storing the quantized transform coeficients.
12. A method as recited by claim 1 1, wherein a value of the hashed signal is
utilized for identification or authentication.
13. A method as recited by claim 1, wherein the method is used for
watermarking the signal and the applying comprises:
scaling the signal;
projecting each selected basis function onto the scaled signal;
computing a transform coefficient for each basis function;
applying a watermark to the transform coefficients; and
inserting the watermark into the signal.
14. A method as recited by claim 1, wherein the applying provides a
transformed signal and the transformed signal is reconstructed by acts
comprising:
multiplying each basis function by a corresponding transform
coeacient; and
summing results of the multiplying.
1 5. A system comprising:
a randlet transform (RT) module to receive a signal and apply a
plurality of randomly selected basis functions to the signal; and
a pseudorandom generator coupled to the RT module to generate a
random number utilized by the RT module to select the randomly selected
basis functions.
16. A system as recited by claim 15, wherein the pseudorandom generator
utilizes a secret key as a seed to generate the random number.
17. A system as recited by claim 16, wherein the seed is a bit stream.
18. A system as recited by claim 15, wherein each of the basis hnctions is
generated by scaling, rotating , translating , discretizing, and normalizing a
mother randlet.
19. One or more computer-readable media having instructions stored thereon
that, when executed, direct a machine to perform acts comprising:
randomly selecting a plurality of generated basis functions; and
applying the randomly selected basis hnctions to a signal.
20. One or more computer-readable media as recited by claim 19, wherein the
basis functions are generated from a set of functions that are selected from
one or more items of a group comprising one-dimensional, twodimensional,
and three-dimensional functions.
P
2 1. One or more computer-readable media as recited by claim 19, wherein each
of the basis functions is generated by scaling, rotating, translating,
discretizing, and' normalizing a mother randlet.
22. One or more computer-readable media as recited by claim 21, wherein the
basis functions are constrained by allowing only a finite set of scaling and
rotation operations.
23. One or more computer-readable media as recited by claim 2 1, wherein
instead of defining each basis function independently of all others, a library
of non-translated basis functions is generated by randomly scaling and
rotating the mother randlets.
24. One or more computer-readable media as recited by claim 2 1, wherein
when scaling, a wavelet family is chosen.
25. One or more computer-readable media as recited by claim 21, wherein the
mother randlet is selected &om a group comprising Gaussian, half, Mexican
Hat, wavelet randlets, and combinations thereof.
26. One or more computer-readable media as recited by claim 19, wherein the
applying comprises:
projecting each selected basis function onto the signal;
subtracting each projection from the signal;
projecting each selected basis function onto a residue of the previous
basis function;
computing a transform coefficient for each basis function;
quantizing the transform coeficients;
storing the quantized transform coefficients; and
computing a next residue.
27. One or more computer-readable media as recited by claim 19, wherein the
acts are used for compressing the signal and the applying comprises:
projecting each selected basis function onto the signal;
subtracting each projection from the signal;
computing a transform coeficient for each basis function;
quantizing the transform coefficients;
eliminating select quantized transform coeficients; and
storing the quantized transform coefficients.
28. One or more computer-readable media as recited by claim 19, wherein the
acts are used for denoising the signal by de-emphasizing relatively smaller
basis hctions and super-positioning remaining basis functions.
29. One or more computer-readable media as recited by claim 19, wherein the
acts are used for hashing the signal and the applying comprises:
scaling the signal;
projecting each selected basis function onto the scaled signal;
computing a transform coefficient for each basis function;
quantizing the transform coefficients;
applying error correction to the quantized transform coefficients; and
storing the quantized transform coefficients.
30. One or more computer-readable media as recited by claim 29, wherein a
value of the hashed signal is. utilized for identification or authentication.
3 1. One or more computer-readable media as recited by claim 19, wherein the
acts are used for watermarking the signal and the applying comprises:
scaling the signal;
projecting each selected basis function onto the scaled signal;
computing a transform coefficient for each basis function;
applying a watermark to the transform coefficients; and
inserting the watermark into the signal.
32. One or more computer-readable media as recited by claim 19, wherein the
applying provides a transformed signal and the transformed signal is
reconstructed by acts comprising:
multiplying each basis function by a corresponding transform
coefficient; and
summing results of the multiplying.

Documents:

572-del-2005-Abstract-(09-10-2013).pdf

572-del-2005-Abstract-(16-05-2005).pdf

572-del-2005-Assignment-(09-10-2013).pdf

572-del-2005-Assignment.pdf

572-del-2005-Claims-(09-10-2013).pdf

572-del-2005-Claims-(16-05-2005).pdf

572-del-2005-Claims-(24-02-2015).pdf

572-del-2005-Correspondence Others-(09-10-2013).pdf

572-del-2005-Correspondence Others-(24-02-2015).pdf

572-DEL-2005-Correspondence-Others-(08-12-2010).pdf

572-DEL-2005-Correspondence-Others-(09-06-2010).pdf

572-del-2005-Description-(Complete)-(16-05-2005).pdf

572-del-2005-Drawings-(09-10-2013).pdf

572-del-2005-Drawings-(16-05-2005).pdf

572-DEL-2005-Form-1-(08-12-2010).pdf

572-del-2005-Form-1-(16-05-2005).pdf

572-del-2005-Form-18-(04-04-2008).pdf

572-del-2005-Form-2-(16-05-2005).pdf

572-del-2005-Form-3-(09-10-2013).pdf

572-del-2005-Form-3-(16-05-2005).pdf

572-del-2005-Form-5-(16-05-2005).pdf

572-DEL-2005-GPA-(09-06-2010).pdf

572-del-2005-GPA.pdf

572-del-2005-Intellectual Property-(24-02-2015).pdf

572-del-2005-Manul Of Patent Office-(24-02-2015).pdf

572-del-2005-Marked Claims-(24-02-2015).pdf

572-del-2005-Others-(24-02-2015).pdf

572-del-2005-Parliament Of India-(24-02-2015).pdf

572-del-2005-Petition-137-(09-10-2013).pdf

FORM-6(PRS)-401-500.23.pdf

FORM-6(PRS)-401-500.23.pdf ONLINE

MS to MTL Assignment.pdf

MS to MTL Assignment.pdf ONLINE

MTL-GPOA - PRS.pdf

MTL-GPOA - PRS.pdf ONLINE

PD000631IN-SC_PETITION.pdf

PD000631IN-SC_PETITION.pdf ONLINE

« Previous Patent

Next Patent »

Patent Number

265898

Indian Patent Application Number

572/DEL/2005

PG Journal Number

13/2015

Publication Date

27-Mar-2015

Grant Date

23-Mar-2015

Date of Filing

16-Mar-2005

Name of Patentee

MICROSOFT TECHNOLOGY LICENSING, LLC

Applicant Address

ONE MICROSOFT WAY, REDMOND, WASHINGTON 98052, U.S.A

Inventors:

#	Inventor's Name	Inventor's Address
1	MICHAEL T. MALKIN	ONE MICROSOFT WAY, REDMOND, WASHINGTON 98052, U.S.A
2	RAMARATHNAM VENKATESAN	ONE MICROSOFT WAY, REDMOND, WASHINGTON 98052, U.S.A

PCT International Classification Number

G06F 17/00

PCT International Application Number

N/A

PCT International Filing date

PCT Conventions:

#	PCT Application Number	Date of Convention	Priority Country
1	10/837,563	2004-04-30	U.S.A.