Method and system for facilitating compression

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
0Forward
Citations 
0
Petitions 
0
Assignments
First Claim
1. A computerimplemented method for facilitating compression, comprising:
 receiving a first vector,wherein the first vector is based on an ndimensional mchannel patch,wherein n≥
0, andwherein m≥
1;
determining a second vector based on a difference between the first vector and a mean vector and a transposition of the difference between first vector and the mean vector,wherein the mean vector is based on a plurality of ndimensional mchannel patches; and
providing the second vector to a receiver,wherein the receiver determines a second ndimensional mchannel patch based on the second vector.
0 Assignments
0 Petitions
Accused Products
Abstract
During operation, embodiments of the subject matter can perform compression of an ndimensional mchannel patch based on unsupervised learning (clustering). Embodiments of the subject matter can perform multiple such compressions of patches tessellated (tiled) across a space. Embodiments of the subject matter can also perform hierarchical compression through recursive application of embodiments of the subject matter. Embodiments of the subject matter can compress but are not limited to compressing the following: a database, a sequence, an image, a video, and a volumetric video.
2 Citations
No References
Image compression with tile alignment  
Patent #
US 7,158,679 B2
Filed 05/29/2002

Current Assignee
Ricoh Company Limited

Sponsoring Entity
Ricoh Company Limited

Moving picture compression apparatus, image processing apparatus, moving picture compression method, image processing method, and data structure of moving picture compression file  
Patent #
US 9,693,072 B2
Filed 10/24/2012

Current Assignee
Sony Interactive Entertainment Inc.

Sponsoring Entity
Sony Corporation, Sony Interactive Entertainment Inc.

15 Claims
 1. A computerimplemented method for facilitating compression, comprising:
receiving a first vector, wherein the first vector is based on an ndimensional mchannel patch, wherein n≥
0, andwherein m≥
1;determining a second vector based on a difference between the first vector and a mean vector and a transposition of the difference between first vector and the mean vector, wherein the mean vector is based on a plurality of ndimensional mchannel patches; and providing the second vector to a receiver, wherein the receiver determines a second ndimensional mchannel patch based on the second vector.  View Dependent Claims (2, 3, 4, 5)
 6. One or more nontransitory computerreadable storage media storing instructions that when executed by one or more computers cause the one or more computers to perform operations for facilitating compression, comprising:
receiving a first vector, wherein the first vector is based on an ndimensional mchannel patch, wherein n≥
0, andwherein m≥
1;determining a second vector based on a difference between the first vector and a mean vector and a transposition of the difference between first vector and the mean vector, wherein the mean vector is based on a plurality of ndimensional mchannel patches; and providing the second vector to a receiver, wherein the receiver determines a second ndimensional mchannel patch based on the second vector.  View Dependent Claims (7, 8, 9, 10)
 11. A system comprising one or more computers and one or more storage devices storing instructions that when executed by the one or more computers cause the one or more computers to perform operations for facilitating compression, comprising:
receiving a first vector, wherein the first vector is based on an ndimensional mchannel patch, wherein n≥
0, andwherein m≥
1;determining a second vector based on a difference between the first vector and a mean vector and a transposition of the difference between first vector and the mean vector, wherein the mean vector is based on a plurality of ndimensional mchannel patches; and providing the second vector to a receiver, wherein the receiver determines a second ndimensional mchannel patch based on the second vector.  View Dependent Claims (12, 13, 14, 15)
1 Specification
The subject matter relates to data compression, where the data can be a database, a table, a sequence, an image, a video, or any multidimensional shape comprised of elements that are vectors (channels). For example, each pixel element in an image can comprise a threeelement vector, which can correspond to the RGB channels.
Internet video streaming and downloads have exploded the last few years. This growth is not likely to stop: video traffic is expected to quadruple in the next five years. In addition, the Big Data revolution resulted in enormous and diverse data sets including but not limited to images, texts, audio, genomic data, 3D virtual reality data, medical volumetric video data, and point cloud data from autonomous mapping. This growth is driving further refinements in compression to ensure Quality of Experience (QoE) on the client (receiver) side.
QoE comprises three parts: speed of compressed content delivery from the server to the receiver, speed of decompression on the receiver side, and fidelity of the decompressed content on the receiver side. QoE heavily impacts revenue on the server side: when bandwidth becomes narrower and content becomes large, QoE becomes worse, which can prompt a client to cancel a service, seek the content from sources with more bandwidth, or simply give up in frustration.
The market for QoE is enormous because most manufacturers have allocated personnel, time, funds, and even space on integrated circuits and chips for video and audio compression. This means anything that improves QoE will be adopted quickly. Moreover, since bandwidth costs users and carriers money, any mechanism that can produce the same QoE with lower bandwidth can facilitate a gain in market share. Slow downloads can also eat up energy (e.g., battery power), which can raise overall costs. Compression might help improve QoE through faster downloads of compressed data, faster decompression on the client side, and higher fidelity decompressed content.
Existing compression methods tend to leverage redundant information. For example, images of nature scenes tend to contain a large amount of redundant information because neighbor pixels tend to be correlated with each other. Most existing compression methods take advantage of such correlation to reduce image size for compression.
For example, traditional compression methods such as JPEG rely on handcrafted though generalpurpose encoder and decoder pairs (called codecs). But these codecs do not leverage particulars of the data being compressed.
In contrast adaptive machine learning methods such as neural networks, can leverage the particulars of the data and have been shown to produce better quality images with 25% smaller file sizes. But such methods still result in images that are too big to load quickly on mobile devices.
Hence, what is needed is a method and a system for compression that facilitates high QoE (i.e., fast downloads with fast and high fidelity decompression), that does not require handcrafting (i.e., scales across multidimensional data of various sizes), and that can leverage the particulars of the data being compressed while adapting to the bandwidth at hand.
One embodiment of the subject matter can compress data based on unsupervised learning (clustering) and then provide that compressed data to a receiver, which can then decompress it.
This embodiment facilitates a client to produce, for example, highdefinition video from lowbandwidth transmission, thus improving QoE. The results of clustering (i.e., the parameters) can be precomputed across multiple samples of the data. For example, the results of clustering can be precomputed across a sample of images available on the internet. Once precomputed, the compression model (the results of clustering) can be provided to anyone or any system to compress similar data. The clustering can also run in realtime by embodiments of the subject matter.
Embodiments of the subject matter could result in faster and more accurate diagnoses in medicine. For example, embodiments of the subject matter could facilitate quickly sending detailed medical images of a patient to the best doctors throughout the world for a faster and more accurate diagnosis based on highfidelity decompressed images. Patients from underserved and remote areas could especially benefit from embodiments of the subject matter.
Embodiments of the subject matter could benefit particular types of medical imaging by customizing its compression to suit particular needs. For example, in a mammogram the boundaries between dense and notdense tissues is important in diagnosis. Embodiments of the subject matter can take that density difference into account by producing compressions based on clustering over a training set comprising only mammogram images. The results of clustering can be precomputed across a sample of such images for medical applications including but not limited to breast cancer diagnosis.
Embodiments of the subject matter can also be useful in emergency situations associated with disaster zones, where bandwidth might be limited but where highquality medical images need to be transmitted to doctors outside of the disaster zone.
For secure encryption methods, embodiments of the subject matter can be used to generate onetime encryption/decryption keys based on compression. That is, the data to be encrypted can be clustered for encryption, not just compression.
Embodiments of the subject matter can be used to reduce download costs. For example, companies that spend enormous amounts of money on infrastructures for image downloads (e.g., Twitter) could see lighter loads on their infrastructure and therefore scale down spending on such infrastructures.
Embodiments of the subject matter can be used to compress natural language sequences through numerical encodings of words such as word embeddings or onehot encodings. In addition, text can be encoded as images, or a sequence of images across multiple pages.
More generally, embodiments of the subject matter can facilitate compression of multiple patches, tessellated (tiled) across the data, where a patch comprises an ndimensional piece of data comprising multiple channels. Multiple such patches can be compressed and downloaded such that an entire piece of data (e.g., a database, an image, or a video) can be decompressed on the receiver'"'"'s side. That is, embodiments of the subject matter can be applied repeatedly over multiple patches and provided to a receiver serially or in parallel or in some combination thereof.
For example, when n=0, a patch can be a row in a database or table and the channels can represent the columns of that table. When n=1, a patch can be a sequence of such multiple channels. For example, the patch might be a portion of an audio wavefile or a portion of an audio spectrogram, where each channel can be associated with a particular frequency and its corresponding power value.
When n=2, the patch can be part of an image, where the channels represent Red, Green, and Blue (RGB) levels. Note that a patch can be square, rectangular, or any two dimensional regular or irregular shape. The aforementioned RGB channels are only illustrative of the type of information that can be associated with an image. For example, RGB levels could be translated to another color space known as YCbCr, which covers the same color space though with a different representation. It has been shown that two of the replacement components, Cb and Cr (the color components), are highly compressible because a human viewer is more able to discriminate the brightness component (Y) than color components (Cb and Cr). This means that the brightness value can be higher fidelity than the two color components. Embodiments of the subject matter can automatically facilitate this aspect of human vision by downsampling chroma values prior to clustering.
When n=3, the data can be a video, which comprises a sequence of frames (images). For example, a patch in a video can be threedimensional with RGB channels. More specifically, a patch in a video can be a 3×3×3 hypercube of RGB channels, where each slice of the hypercube can be associated with a frame. The first 3×3 slice can be associated with frame i−1. The second 3×3 slice can be associated with frame i. The third 3×3 slice can be associated with frame i+1. Together, these three slices comprise the 3×3×3 hypercube. Embodiments of the subject matter can leverage relationships between pixels in the three frames.
Thus, the threedimensional space in a video comprises multiple 3×3×3 cubic patches of RGB channels tessellated across the entire video. Embodiments of the subject matter are not limited to cubes, rectangular parallelepiped, and other regular or irregular shapes (patches) that can be used to tessellate the threedimensional space by themselves or in conjunction with other patch shapes.
When n=4, the patches can comprise threedimensional shapes over time. For example, such patches can be from a threedimensional video of the brain or body over time, as obtained from imaging devices such as MRI, fMRI, PET, CAT, or CT. Any one frame comprises a threedimensional volume, where each voxel comprises RGB values.
Embodiments of the subject matter are not limited to four dimensions but can be any number of dimensions. More generally, a patch can be a cube, a rectangle, a hypercube, a hyperrectangle, a hypervolume, or any regular or irregular shape in multiple dimensions.
Embodiments of the subject matter can perform multiple such compressions, which can correspond to compressing an entire piece of data. Multiple different patches or the same shape of a patch can be used to tesselate (tile) or cover a particular space (ndimensional volume). The compressed versions of these multiple patches of the same or different shape that tesselate a space can then be provided to the receiver in any order, serially or in parallel, thus facilitating decompression of the entire ndimensional space. For example, in a video, the compressed versions of a patch can be provided frame by frame, in order of appearance, and left to right and top to bottom for any frame.
Particular embodiments of the subject matter described in this specification can be implemented so as to realize better QoE for the receiver: faster downloads, faster decompression, and higher fidelity decompressions.
The details of one or more embodiments of the subject matter are set forth in the accompanying drawings and the description below. Other features, aspects, and advantages of the subject matter will become apparent from the description, the drawings, and the claims.
In the figures, like reference numerals refer to the same figure elements.
Compression system 100 receives first vector 130, which is based on a first ndimensional mchannel patch. The first vector can be a flattened version of the elements of the first ndimensional mchannel patch. Here “flattening” means that all the elements of the patch are flattened into a vector. For example, in an image, the first vector can comprise a 27element vector, which comprises the RGB values of a flattened 3×3 patch. Similar flattening can be applied to any first ndimensional mchannel patch. The result is a vector that contains every element'"'"'s value in the first ndimensional mchannel patch.
Compression system 100 receives first vector 130 with receiving subsystem 140. Next, compression system 100 determines a second vector with secondvector determining system 160 based on a difference between the first vector and a mean vector and a transposition of the difference between the first vector and the mean vector 150. The mean vector is based on a plurality of ndimensional mchannel patches, each of which has been flattened as described above. The mean vector is an average of these flattened vectors. These flattened vectors can be training examples for an unsupervised learning (clustering) system, which can produce the mean vector, a covariance matrix, and a probability distribution of clusters.
The training examples for the unsupervised learning (clustering) system can comprise flattened ndimensional mchannel patches sampled from the data. These flattened samples can be exhaustive (i.e., all possible flattened ndimensional mchannel patches), randomly chosen, or chosen based on some predefined criteria, which can reflect the desired parts of the data. Multiple different samples can be used to produce multiple different first vectors, all of which can be combined on the receiver side, after decompression, through averaging or other combinational methods. Note that flattening is not essential in embodiments of the subject matter and is merely an artifact of a particular clustering method, which expects training data in a set of rows of vectors (columns), where the columns correspond to features. Clustering algorithms can be modified to expect training data in the form of one or more patches rather than rows where each row corresponds to a flattened patch. Flattening is also an artifact of the typical way to represent a mean over the clusters as a vector rather than as a patch. The mean could also be defined over a patch rather than a flattened version of a patch.
In a preferred embodiment of the subject matter, the second vector s is comprised of k≥1 elements, where the ith element of s is defined as:
Here, x is the first vector, μ_{i }is a mean vector for the ith cluster, T is the transpose operator, Σ_{i }is a covariance matrix for the ith cluster, Σ_{i}^{−1 }is an inverse of the covariance matrix for the ith cluster, Σ_{i} is a determinant of the covariance matrix, and p_{i }is a probability of the ith cluster. For a given number of clusters, these parameters can be computed or approximated with ExpectationMaximization, where the ith mixture is characterized by μ_{i}, Σ_{i}, and p_{i}. Other methods can be used to compute these parameters. Typically, these methods are iterative and a small random value is added along the diagonal of the covariance matrix to prevent singularity. Similarly, p_{i }can be approximated from the frequency count (how many rows are assigned to the cluster i) for any one iteration, with appropriate constants added to the numerator and denominator to avoid dividebyzero errors.
As mentioned above, the training data for this clustering is one or more rows of flattened ndimensional mchannel patches. For example, ExpectationMaximization can be used to determine μ_{i}, Σ_{i}, and p_{i }based on this training data. As no target labels are part of the input training data, this clustering method can be termed unsupervised learning.
Many other methods can be used to compute these quantities for each mixture as well as to choose the number of mixtures, which corresponds to length of the second vector. Moreover, s_{i }can be represented through many different mathematically equivalent forms, with or without normalization constants. The particular form above is derived from a multivariate normal distribution with normalization constants removed and a natural logarithm transformation applied, both for ease of computation. Alternatively, a probabilistic version of the multivariate normal distribution can be used. However, this results in a more complex form, which includes exponentials.
The righthand side of the equation can be viewed as a distance metric between a particular vector x and a particular cluster i, characterized by μ_{i}, Σ_{i}, and p_{i}. Item 1 in the equation corresponds to the difference between the first vector and a mean vector and a transposition of the difference between the first vector and the mean vector. Item 2 in the equation corresponds to the Mahalanobis distance, a common distance measure. Item 3 measures the amount of uncertainty (multidimensional spread) in the cluster: the smaller this item is, the less uncertainty. Item 4 corresponds to the prior probability of the cluster. This item is subtracted because the larger the prior probability, the closer the natural logarithm of the prior probability, which will be negative, will be to zero.
Many other simplified forms of this equation are possible, including the following:
Item 5 corresponds to the Mahalanobis distance. This distance can also have a simplified form, where the covariance matrix is diagonal (i.e., offdiagonal values are 0). Item 5 is the Euclidean distance, which is used in the kmeans method of clustering. Kmeans clustering with the distance metric in items 5 or 6 can also be leveraged to produce the parameters that are fed into compression system 100.
A preferred embodiment of compression system 100 leverages all three of μ_{i}, Σ_{i}, and p_{i }as in the equation above with items 14, for k≥1 clusters, to produce a klength second vector in second vector determining system 160.
Note that the number of clusters k can be determined based on bandwidth constraints and desired QoE. Alternatively, the number of clusters k can be determined experimentally. For example, k can be determined based on a validation set or the original training set, by determining when the likelihood (or a similar measure) does not appreciably increase as k increases. This is a point of diminishing returns, where overfitting, which is not desirable, begins to show its effects.
Subsequently, compression system 100 provides second vector 180 to a receiver with second vector providing system. A receiver can then determine a second ndimensional mchannel patch based on second vector 180 with second ndimensional mchannel patch determining subsystem 190. The second ndimensional mchannel patch can be called a “reconstruction” of the first ndimensional mchannel patch, though there is no guarantee of a lossless “reconstruction.”
The second ndimensional mchannel patch determining subsystem can also leverage a previously trained model, where the previously trained model can be based on training data comprising pairs of two elements. The first element can be a second vector (as produced with Items 14 above) and second element can be a corresponding vector of a flattened ndimensional mchannel patch. A supervised learning method can be used to learn a model which can predict each element of the corresponding vector given the first element. Nonparametric methods such as nearest neighbor can also be used to predict each element of a flattened ndimensional mchannel patch.
Another way to produce the corresponding vector is to transform the second vector into a vector of probabilities and then determine a weighted sum of each cluster'"'"'s probability multiplied by each cluster'"'"'s corresponding mean vector. Next, the resulting vector can be converted to the ndimensional mchannel patch by unflattening it. One method to produce a vector w from the second vectors can be based on the following equation:
The vector w can then be translated to the second ndimensional mchannel patch based on a mapping between each location in the vector w and its corresponding location in the second ndimensional mchannel patch. Embodiments of the subject matter can additionally provide the receiver with the mean vector for each cluster such that a transformation to the second ndimensional mchannel patch can be facilitated on the receiver side based on the equation for w above.
This approach, based on w, to determining a second ndimensional mchannel patch based on second vector 180 with second ndimensional mchannel patch determining subsystem 190 doesn'"'"'t require building a model based on pairs of elements comprising second vectors and representation of the patch as a target. That is, the same model that was used in clustering can be repurposed for decompression. For example, a generative cluster model such as Gaussian Mixtures can be repurposed as a highfidelity decompressor/decoder on the receiver side.
In contrast, neural net models, such as autoencoders, are not generative and require two stages of learning: learn an intermediate representation (i.e., the encoder) from the data and then learn how to recreate the original data (i.e., a decoder). These stages are typically combined, which can be computationally harder. The ExpectationMaximization approach to clustering attempts to find models that maximize the likelihood of the data, which directly addresses the decoding portion. That is, the parameters of a Gaussian Mixture can be used both to compress and decompress an ndimensional mchannel patch in accordance with embodiments of the subject matter described above.
ExpectationMaximization and other clustering models can produce several different models from the same training set. Each of these different clustering models can be used to compress the data differently, with decompression on the receiver side as described above. A set of these decompressions can be combined on the receiver side, for example, by averaging their results over multiple decompressed ndimensional mchannel patches. Combining multiple different decompressions can be important to facilitate improved decompressed fidelity, which in turn results in improved QoE for the receiver. These decompressions can be run in parallel for greater speed, as part of the QoE process.
Embodiments of the subject matter can also facilitate hierarchical compression as follows. Given a tessellation (tiling) of a space with ndimensional mchannels patches, the space of ndimensional mchannels patches can be sampled as described above, flattened, clustered into k clusters, and then each patch can be compressed into k channels accordance with embodiments of the subject matter.
The patch itself can be replaced by the kchannels and repositioned geographically in the context of the other patches, which have also been replaced by their corresponding k channels. For example, the center of a 3×3 twodimensional patch of RGB channels can be replaced by a single patch (point) of kchannels, which represents the distance to each cluster from the 3×3 patch. This patch (point) can then be positioned relative to other similarly compressed patches (points) so that the geographic proximity of the original ndimensional mchannel patch to nearby original ndimensional mchannel patches in the space is approximately preserved.
These new ndimensional kchannel patches can then be sampled as described above, flattened, clustered into j clusters, and further compressed also in accordance with embodiments of the subject matter. This process can repeat on the new ndimensional jchannel patches by placing them in a geographic context that is in approximately the same relationship as the original ndimensional kchannel patches. More generally, this process can repeat recursively multiple times, until a desired level of compression is reached.
For example, an image could be tessellated (tiled) by 3×3 patches of RGB channels. In accordance with embodiments of the subject matter, each of these 3×3 patches of RGB channels can then be converted to klength second vectors through sampling and clustering. Next, each of these klength second vectors replace the whole of the corresponding 3×3 patches of RGB channels from which they were derived, thus compressing the original data. This process can be repeated multiple times until a desired level of compression or fidelity is obtained.
Note that the sampling and flattening can be interchanged. That is, the patches can be flattened first into a set of rows and then the rows can be sampled. Or, as described above, the patches can first be sampled and then flattened for further processing.
Each of these nine 3×3 patches of 3 channels (RGB) can then be reduced to a single 3×3 patch of kchannels, through flattening, clustering, creation of a second vector based on a distance metric in accordance with embodiments of the subject matter. The flattened versions can then be placed into their corresponding geographic positions, as shown in ndimensional kchannel patches 210. In the figure, each of the x′ are klength vectors, where the ith element corresponds to the distance to the ith cluster, as described above. These new ndimensional kchannel patches can then be further compressed through recursive application of embodiments of the subject matter.
If ndimensional mchannel patches tiled across surface 200 comprised 18×18 RGB pixels, ndimensional kchannel patches 210 will be comprised of 6×6 kchannel patches. These 6×6 ndimensional kchannel can then be further compressed into a 2×2 patch with jchannels, by sampling, clustering into j clusters, determining a jlength distance vector in accordance with embodiments of the subject matter, and then placing that vector into the geographic context of the patch from which it was derive so as to approximately preserve neighbor relationships in the patch from which the vector was derived.
The preceding example described a threelevel compression hierarchy: 18×18 3 channels→6×6 k channels→2×2 j channels. For example, if k=4 and j=3, embodiments of the subject matter can compress 972 pieces of information to 144 pieces of information to 27 pieces of information. In general, compression can be a reduction in the amount of information, which is what this example illustrates.
The receiver can be provided the final compression and a way to decompress a second vector using a decompression method described above. Hierarchical decompression requires only decompression between levels using a compression method described above for determining the second ndimensional mchannel patch. Similar hierarchical compression and decompression can be applied to any ndimensional mchannel filled space including but not limited to sequences, videos, or 3D videos such as from a timeseries of frames from a volumetric medical scanning device such as CAT, CT, PET, MRI, and fMRI.
Hierarchical compression can be an alternative to deep learning, which uses various pooling techniques based on simple functions such as the mean or the maximum over all RGB values, by channel. Not only do these simple functions not capture as much information as the second vector in embodiments of the subject matter, but such pooling is typically accomplished only per channel. That is, the channels are treated separately. In contrast, embodiments of the subject matter combine all channels at once as part of the compression. Embodiments of the subject matter can be translation, rotation, and scale invariant. In contrast, pooling is typically only translation invariant.
Next, the system determines a second vector based on a difference between the first vector and a mean vector and a transposition of the difference between first vector and the mean vector, wherein the mean vector is based on a plurality of ndimensional mchannel patches. This mean vector can be based on the results of unsupervised learning (clustering) on a training set based on a plurality of (flattened) ndimensional mchannel patches.
Each patch in this plurality of ndimensional mchannel patches can be flattened into a vector to facilitate the aforementioned unsupervised learning (clustering). This clustering then produces several parameters, including the mean vector, a covariance matric, and a probability—one such triple of parameters for each cluster. As mentioned above, many techniques can be used to determine an appropriate number of clusters.
Subsequently, the system provides the second vector to a receiver, wherein the receiver determines a second ndimensional mchannel based on the second vector. This second ndimensional mchannel can be based on the second vector as well as a model. This model can be the aforementioned cluster model (or its mathematical equivalent) or another model trained on a plurality of pairs of elements, where the first element comprises a second vector and a second element comprises a corresponding vectors equivalent to a second ndimensional mchannel patch. These pairs can be viewed as training examples to facilitate building a decompression model using a supervised machine learning method.
The system can provide the receiver this second vector through a communication system, which can be any known or later developed device or system for connecting a computer to a receiver, including a direct cable connection, a connection over a wide area network or a local area network, a connection over an intranet, a connection over the Internet, or a connection over any other distributed processing network or system. Further, the communication links can be wired or wireless links to a network. The network can be a local area network, a wide area network, an intranet, the Internet, or any other distributed processing and storage network.
The preceding description is presented to enable any person skilled in the art to make and use the subject matter, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the subject matter. Thus, the subject matter is not limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein.
Embodiments of the subject matter and the functional operations described in this specification can be implemented in digital electronic circuitry, in tangibly embodied computer software or firmware, in computer hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them.
Embodiments of the subject matter described in this specification can be implemented as one or more computer programs, i.e., one or more modules of computer program instructions encoded on a tangible nontransitory program carrier for execution by, or to control the operation of data processing system.
A computer program (which may also be referred to or described as a program, software, a software application, a module, a software module, a script, or code) can be written in any form of programming language, including compiled or interpreted languages, or declarative or procedural languages, and it can be deployed in any form, including as a standalone program or as a module, component, subroutine, or other unit suitable for use in a computing environment.
A computer program may, but need not, correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or data, e.g., one or more scripts stored in a markup language document, in a single file dedicated to the program in question, or in multiple coordinated files, e.g., files that store one or more modules, subprograms, or portions of code.
Alternatively, or in addition, the program instructions can be encoded on an artificially generated propagated signal, e.g., a machinegenerated electrical, optical, or electromagnetic signal, that is generated to encode information for transmission to a suitable receiver system for execution by a data processing system. The computer storage medium can be a machinereadable storage device, a machinereadable storage substrate, a random or serial access memory device, or a combination of one or more of them.
Computers suitable for the execution of a computer program include, by way of example, can be based on general or special purpose microprocessors or both, or any other kind of central processing unit. Generally, a central processing unit will receive instructions and data from a read only memory or a randomaccess memory or both. The essential elements of a computer are a central processing unit for performing or executing instructions and one or more memory devices for storing instructions and data.
A computer can also be distributed across multiple sites and interconnected by a communication network, executing one or more computer programs to perform functions by operating on input data and generating output.
A computer can also be embedded in another device, e.g., a mobile telephone, a personal digital assistant (PDA), a mobile audio or video player, a game console, a Global Positioning System (GPS) receiver, or a portable storage device, e.g., a universal serial bus (USB) flash drive, to name just a few.
Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto optical disks, or optical disks. However, a computer need not have such devices.
The term “data processing system” encompasses all apparatus, devices, and machines for processing data, including by way of example a programmable processor, a computer, or multiple processors or computers.
For a system of one or more computers to be configured to perform particular operations or actions means that the system has installed on it in software, firmware, hardware, or a combination of them that in operation cause the system to perform the operations or actions. For one or more computer programs to be configured to perform particular operations or actions means that the one or more programs include instructions that, when executed by data processing system, cause the system to perform the operations or actions.
The processor and the memory can be supplemented by, or incorporated in, special purpose logic circuitry. More generally, the processes and logic flows can also be performed by and be implemented as special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application specific integrated circuit), a dedicated or shared processor that executes a particular software module or a piece of code at a particular time, and/or other programmablelogic devices now known or later developed. When the hardware modules or system are activated, they perform the methods and processes included within them.
The system can also include, in addition to hardware, code that creates an execution environment for the computer program in question, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of them.
The computerreadable storage medium includes, but is not limited to, volatile memory, nonvolatile memory, magnetic and optical storage devices such as disk drives, magnetic tape, CDs (compact discs), DVDs (digital versatile discs or digital video discs), computer instruction signals embodied in a transmission medium (with or without a carrier wave upon which the signals are modulated), and other media capable of storing computerreadable media now known or later developed. For example, the transmission medium may include a communications network, such as a LAN, a WAN, or the Internet.
Computer readable media suitable for storing computer program instructions and data include all forms of nonvolatile memory, media and memory devices, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto optical disks; and CD ROM and DVDROM disks.
The methods and processes described in the detailed description section can be embodied as code and/or data, which can be stored in a computerreadable storage medium as described above. When a computer system reads and executes the code and/or data stored on the computerreadable storage medium 120, the computer system performs the methods and processes embodied as data structures and code and stored within the computerreadable storage medium.
The components of the system can be interconnected by any form or medium of digital data communication, e.g., a communication network. Examples of communication networks include a local area network (“LAN”) and a wide area network (“WAN”), e.g., the Internet.
While this specification contains many specific implementation details, these should not be construed as limitations on the scope of any subject matter or of what may be claimed, but rather as descriptions of features that may be specific to particular embodiments of particular subject matters. Certain features that are described in this specification in the context of separate embodiments can also be implemented in combination in a single embodiment.
Conversely, various features that are described in the context of a single embodiment can also be implemented in multiple embodiments separately or in any suitable subcombination. Moreover, although features may be described above as acting in certain combinations and even initially claimed as such, one or more features from a claimed combination can in some cases be excised from the combination, and the claimed combination may be directed to a subcombination or variation of a subcombination.
Similarly, while operations are depicted in the drawings in a particular order, this should not be understood as requiring that such operations be performed in the particular order shown or in sequential order, or that all illustrated operations be performed, to achieve desirable results. In certain circumstances, multitasking and parallel processing may be advantageous.
Moreover, the separation of various system modules and components in the embodiments described above should not be understood as requiring such separation in all embodiments, and it should be understood that the described program components and systems can generally be integrated together in a single software product or packaged into multiple software products.
The foregoing descriptions of embodiments of the subject matter have been presented only for purposes of illustration and description. They are not intended to be exhaustive or to limit the subject matter to the forms disclosed. Accordingly, many modifications and variations will be apparent to practitioners skilled in the art. Additionally, the above disclosure is not intended to limit the subject matter. The scope of the subject matter is defined by the appended claims.