Techniques for caching images
View Patent ↗Techniques for caching images are presented. A matrix of pixel values represents an image. A diagonal of the matrix is used as an array of numbers representing an index value. The index value is compared to existing index values housed in a cache. When no match is present, the index value is inserted into the cache and the corresponding image associated with the inserted index value acquired. When a match is present no action is taken on the index values of the cache.
1. A computer-implemented method that uses a processor to perform the processing of:
applying a discrete cosine transform (DCT) algorithm to images;
diagonally traversing each resultant matrix acquired from applying the DCT algorithm to each image to acquire an index value for each image; and
populating a cache with the index values, wherein each index value links to a particular image to which it relates for retrieval from the cache, and wherein when a new image is to be subsequently processed to the cache, a new index value is supplied for the new image and then the cache is searched for a match between the new index value and one of the index values already present in the cache, and assembling the index values in a balanced k-dimensional tree (KD tree) format within the cache, and using a nearest neighbor algorithm to determine the match for the new index value and to acquire a distance metric between the match and the new index value and when the distance metric is more than a threshold value adding the new index value to the KD tree within the cache and acquiring the new image for local linking to the cache.
2. The method of claim 1 , wherein applying further includes traversing the cache that originally indexed the images via a hashing technique using hashing values to acquire each of the images for which the DCT algorithm is applied.
3. The method of claim 1 , wherein applying further includes acquiring the images in a compressed format.
4. The method of claim 1 , wherein diagonally traversing further includes representing each index value as an array of numbers that depict a particular image to which it relates in a frequency domain.
5. The method of claim 1 , wherein populating further includes deciding to add the new image to the cache via the new index value and using the distance metric to generate the new image from an existing image associated with the match when the distance metric is less than or equal to the threshold value.
6. A computer-implemented method that uses a processor to perform the processing of:
receiving a candidate index value for a new image, the candidate index value representing an array of numbers for a diagonal of pixel values assembled from a matrix that represents the new image;
using a nearest neighbor algorithm to search index values already present in a cache against the candidate index value; and
determining whether a match is present in the cache in response to using the nearest neighbor algorithm, when the match is present the candidate index value is not placed in the cache and the new image is not acquired, when the match is not present the candidate index value is placed in the cache and the new image is acquired for linking to the cache, and deciding whether the match exists by comparing a distance metric for the candidate index value against each compared index value from the cache and determining the match exists when the distance metric is within a threshold value.
7. The method of claim 6 , wherein receiving further includes obtaining the candidate index value from a remote network site that natively vends the new image.
8. The method of claim 7 , wherein obtaining further includes having the remote network site use a discrete cosine transform (DCT) algorithm to produce the matrix from which the index value is derived via the diagonal.
9. The method of claim 6 , wherein using further includes searching the cache, wherein the index values are organized as a tree structure within the cache.
10. The method of claim 9 , wherein searching further includes representing the tree structure as a multidimensional tree structure.
11. The method of claim 6 , wherein determining further includes acquiring the new image by applying the distance metric to a particular image associated with a particular index value of the match to derive the new image.
12. A computer-implemented system, comprising:
a cache manager implemented in a computer-readable storage medium and to process on a processor; and
a cache implemented in a computer-readable storage medium accessible to the processor; wherein the cache manager maintains the cache as a tree data structure, each node of the tree data structure represented as a particular index value linked to a particular image, and particular index value representing a diagonal of a pixel matrix that represents the particular image, and wherein the cache is searched when a candidate index value is supplied to determine whether a candidate image associated with the candidate index value is represented within the tree data structure, and wherein the candidate index value is received remotely over a network connection by the cache manager, and wherein the cache manager uses a nearest neighbor algorithm to determine whether a match exists within the cache for the candidate index value, and wherein the cache manager determines a match exists if the comparison between the candidate index value and the index values of the cache fall within or below a predefined threshold.
13. The system of claim 12 , wherein the tree is a balanced k-dimensional tree (KD tree).
14. The system of claim 12 , wherein the cache is initially populated with hash values that the cache manager converts to the index values by iterating the cache to replace each of the hash values with a specific index value.