Method and Apparatus for Approximate Matching of Image Data
A method and device are disclosed for an associative and approximate, analog or digital scanning of databases that allows for the asynchronous accessing of data from a mass storage medium. The invention includes providing dedicated analog and digital circuitry and decision logic at the mass storage medium level for determining a key identifying the data of interest, continuously comparing the key to a signal generated from a reading of the data from the mass storage medium with an approximate or exact matching circuit to determine a pattern match, determining a correlation value between the key and the data as it is read in a continuous fashion, and determining a match based upon a preselected threshold value for the correlation value. The pattern matching technique eliminates any need to compare data based on its intrinsic structure or value, and instead is based on an analog or digital pattern. The key and data may be either analog or digital. This device and method may be provided as part of a stand-alone computer system, embodied in a network attached storage device, or can otherwise be provided as part of a computer LAN or WAN.
1 - 37 . (canceled)
38 . A method for determining whether at least a portion of an image is an approximate match to a key, the method comprising:
streaming data corresponding to an image through programmable logic that has been loaded with a key; and
comparing the streaming image data with the key using the programmable logic to thereby identify any approximate matches that exist between the key and the image data.
39 . The method of claim 38 wherein the image data comprises a plurality of pixels, and wherein the key corresponds to a group of pixels for which at least an approximate match is sought in the image data.
40 . The method of claim 39 wherein the key comprises a row of pixels.
41 . The method of claim 39 wherein the key comprises a quadrant of pixels.
42 . The method of claim 39 further comprising:
receiving a search command from a processor that is in communication with the programmable logic via a system bus; and
providing information to the processor that is indicative of any approximate matches identified as a result of the comparing step.
43 . The method of claim 40 further comprising:
determining the key from the search command using the programmable logic.
44 . The method of claim 39 wherein the comparing step comprises:
continuously computing a correlation coefficient between the key and a sliding window of the streaming image data using the programmable logic; and
judging each computed correlation coefficient against a threshold value to thereby identify whether an approximate match exists between the key and the streaming image data.
45 . The method of claim 44 wherein the key comprises an analog key as represented by a plurality of samples, and wherein the streaming step comprises sampling an analog read signal of image data streaming from a database at a high rate, and wherein the comparing step comprises performing the comparing step on the respective samples of the analog key and the image data.
46 . The method of claim 39 wherein the comparing step comprises determining whether an approximate match exists based on an adjustable threshold using the programmable logic.
47 . The method of claim 46 further comprising:
adjusting the threshold to control a degree of approximate matches which is identified as a result of the comparing step.
48 . The method of claim 39 wherein the comparing step comprises pattern comparing the streaming image data with the key using the programmable logic to thereby identify any approximate matches that exist between the key and the streaming image data.
49 . The method of claim 48 wherein the pattern comparing step comprises pattern comparing the streaming image data with the key using the programmable logic without framing the streaming image data.
50 . An apparatus for determining whether a portion of an image stored by a mass storage medium is an approximate match to a key, the apparatus comprising:
an approximate matching unit in communication with a mass storage medium, the approximate matching unit comprising programmable logic, the programmable logic being configured to (1) store a key, (2) receive a stream of image data from the mass storage medium, and (3) compare the received stream of image data with the key to thereby identify an approximate match between the key and the received image data.
51 . The method of claim 50 wherein the image data comprises a plurality of pixels, and wherein the key corresponds to a group of pixels for which at least an approximate match is sought in the image data.
52 . The apparatus of claim 51 wherein the apparatus further comprises a processor and a system bus, the system bus interconnecting the processor with the approximate matching unit, wherein the approximate matching unit is further configured to (1) receive a search command from the processor via the system bus, and (2) provide information to the processor that is indicative of any approximate matches identified as a result of the comparison.
53 . The apparatus of claim 52 wherein the programmable logic is further configured to determine the key from the search command.
54 . The apparatus of claim 51 wherein the apparatus further comprises a network interface and a system bus, the system bus interconnecting the network interface with the approximate matching unit, wherein the approximate matching unit is further configured to (1) receive a search command from the network interface via the system bus, and (2) provide information to the network interface that is indicative of any approximate matches identified as a result of the comparison.
55 . The apparatus of claim 51 wherein the programmable logic is further configured to (1) continuously compute a correlation coefficient between the key and a sliding window of the received image data, and (2) judge the computed correlation coefficients against a threshold value to thereby identify whether any approximate matches exist between the key and the received image data.
56 . The apparatus of claim 55 wherein the key comprises an analog key as represented by a plurality of samples, wherein the approximate matching unit is further configured to sample an analog read signal of image data streaming from the mass storage medium at a high rate, and wherein the programmable logic is further configured to perform its comparison on the respective samples of the analog key and the image data.
57 . The apparatus of claim 51 wherein the programmable logic is further configured to determine whether any of the approximate matches exist based on an adjustable threshold.
58 . The apparatus of claim 57 wherein the approximate matching unit is configured to adjust the threshold to control a degree of approximate matches which is identified as a result of the comparison.
59 . The apparatus of claim 57 further comprising the mass storage medium directly coupled to the approximate matching unit.
60 . The apparatus of claim 59 wherein the mass storage medium comprises at least one hard disk drive.
61 . A method for determining whether a portion of an image is an approximate match to a key, the method comprising:
reading image data from a mass storage medium as a stream of pixels;
correlating a sliding window of the pixel stream with a key using programmable logic, wherein the key corresponds to a group of pixels; and
determining whether an approximate match exists between the key and the pixel stream in response to the correlating step and based on an adjustable threshold.
62 . The method of claim 61 wherein the correlating step comprises continuously computing a correlation coefficient between the key and the sliding window, and wherein the determining step comprises comparing the computed correlation coefficients with a threshold value to thereby identify whether any approximate matches exist between the key and the pixel stream.