# US 2014/0193076 A1 · Compressive sensing with local geometric features > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0193076 A1 - Document ID: US20140193076A1 - Status: Published application - Kind: A1 - Application number: 13/800,332 - Filed: 2013-03-13 - Published: 2014-07-10 - Earliest claimed: 2012-03-22 - Assignees: The Charles Strak Draper Laboratory, Inc. - Applicants: The Charles Strak Draper Laboratory, Inc. - Inventors: Brian Gardiner; Rishi Gupta; Piotr Indyk; Eric Price; Yaron Rachlin; Christopher Yu - Web page: https://patentgrep.com/patent/US20140193076A1 ## CPC - G06T 9/00: Image coding (bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00) - G06V 10/20: Image preprocessing - H04N 19/90: using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals - G06V 10/513: {Sparse representations} - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING - H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION ## Abstract Methods and apparatuses for compressive sensing that enable efficient recovery of features in an input signal based on acquiring a few measurements corresponding to the input signal. One method of compressive sensing includes folding an image to generate first and second folds, and recovering a feature of the image based on the first and second folds without reconstructing the image. One example of a compressive sensing apparatus includes a lens, a focal plane array coupled to the lens and configured to generate first and second folds based on the image, and a decoder configured to receive the first and second folds and to recover a feature of the image without reconstructing the image. The feature may be a local geometric feature or a corner. Compressive sensing methods and apparatuses for determining translation and rotation between two images are also disclosed. ## Claims ### Claim 1 A method of compressive sensing, comprising: folding an image to generate a first fold and a second fold, each of the first fold and the second fold being a compressed representation of the image; and recovering a feature of the image, using a processor, based on the first fold and the second fold without reconstructing the image. ### Claim 2 (depends on 1) The method of claim 1, wherein the image includes N pixels and k features and folding the image includes acquiring a plurality of measurements corresponding to the image, the plurality of measurements being O(k logk N) and being less than N, wherein N is a positive integer. ### Claim 3 (depends on 1) The method of claim 1, wherein recovering includes: calculating a plurality of feature vectors based on the first fold and the second fold; thresholding the plurality of feature vectors; clustering the plurality of thresholded feature vectors to generate a plurality of clusters; and decoding a cluster of the plurality of clusters to recover the feature. ### Claim 4 (depends on 1) The method of claim 1, wherein the feature is a corner and recovering the feature includes applying corner detection to each of the first fold and the second fold to generate a first plurality of corners based on the first fold and to generate a second plurality of corners based on the second fold. ### Claim 5 (depends on 4) The method of claim 4, wherein recovering the feature further includes: detecting an artificial edge created by the folding in at least one of the first fold and the second fold; and eliminating a subset of at least one of the first plurality of corners and the second plurality of corners based on the artificial edge. ### Claim 6 (depends on 5) The method of claim 5, wherein eliminating includes generating a first plurality of pruned corners and a second plurality of pruned corners and recovering the feature further includes matching a first corner of the first plurality of pruned corners with a corresponding second corner of the second plurality of pruned corners. ### Claim 7 (depends on 4) The method of claim 4, wherein recovering the feature further includes: matching a first corner of the first plurality of corners with a corresponding second corner of the second plurality of corners; and decoding to recover the feature based on the first corner and the second corner. ### Claim 8 (depends on 7) The method of claim 7, wherein matching further includes: calculating a plurality of cross correlation values, each respective cross correlation value corresponding to a respective first window and a respective second window, the respective first window being associated with a respective first corner of the first plurality of corners and the respective second window being associated with a respective second corner of the second plurality of corners; pruning a candidate match based on a cross correlation value of the plurality of cross correlation values; and matching each respective corner of the first plurality of corners with a respective second corner of the second plurality of corners. ### Claim 9 (depends on 8) The method of claim 8, further including thresholding the plurality of cross correlation values and wherein pruning the candidate match includes pruning the candidate match based on a thresholded cross correlation value. ### Claim 10 (depends on 8) The method of claim 8, wherein recovering includes recovering a plurality of features of the image, the plurality of features being a plurality of corners, and decoding includes decoding to recover each feature of the plurality of features in response to matching each respective corner of the first plurality of corners with a respective second corner of the second plurality of corners. ### Claim 11 An apparatus for compressive sensing, comprising: a lens; a focal plane array coupled to the lens so as to receive an image, the focal plane array being configured to generate a first fold and a second fold based on the image, each of the first fold and the second fold being a compressed representation of the image; a decoder configured to receive the first fold and the second fold and to recover a feature of the image without reconstructing the image. ### Claim 12 (depends on 11) The apparatus of claim 11, further including: a digitizer configured to receive the first fold and the second fold and to output a digitized first fold and a digitized second fold; and wherein the decoder is configured to receive the digitized first fold and the digitized second fold and to output the feature of the image based on the digitized first fold and the digitized second fold without reconstructing the image. ### Claim 13 (depends on 11) The apparatus of claim 11, wherein the decoder is further configured to: calculate a plurality of feature vectors based on the first fold and the second fold; threshold the plurality of feature vectors; cluster the plurality of thresholded feature vectors to generate a plurality of clusters; and decode a cluster of the plurality of clusters to recover the feature. ### Claim 14 (depends on 11) The apparatus of claim 11, wherein the feature is a corner and the decoder is configured to apply corner detection to each of the first fold and the second fold to generate a first plurality of corners based on the first fold and to generate a second plurality of corners based on the second fold. ### Claim 15 (depends on 14) The apparatus of claim 14, wherein the decoder is further configured to: identify an artificial edge in at least one of the first fold and the second fold; and eliminate a subset of at least one of the first plurality of corners and the second plurality of corners based on the artificial edge. ### Claim 16 (depends on 15) The apparatus of claim 15, wherein the decoder is further configured to generate a first plurality of pruned corners and a second plurality of pruned corners and to match a first corner of the first plurality of pruned corners with a corresponding second corner of the second plurality of pruned corners. ### Claim 17 (depends on 14) The apparatus of claim 14, wherein the decoder is further configured to: match a first corner of the first plurality of corners with a corresponding second corner of the second plurality of corners; and decode to recover the feature based on the first corner and the second corner. ### Claim 18 (depends on 17) The apparatus of claim 17, wherein the decoder is further configured to: calculate a plurality of cross correlation values, each respective cross correlation value corresponding to a respective first window and a respective second window, the respective first window being associated with a respective first corner of the first plurality of corners and the respective second window being associated with a respective second corner of the second plurality of corners; prune a candidate match based on a cross correlation value of the plurality of cross correlation values; and match each respective corner of the first plurality of corners with a respective second corner of the second plurality of corners. ### Claim 19 (depends on 18) The apparatus of claim 18, wherein the decoder is configured to threshold the plurality of cross correlation values and to prune the candidate match based on a thresholded cross correlation value. ### Claim 20 (depends on 18) The apparatus of claim 18, wherein the decoder is configured to recover a plurality of features of the image, the plurality of features being a plurality of corners, in response to matching each respective corner of the first plurality of corners with a respective second corner of the second plurality of corners.