Method and apparatus for acquisition, compression, and characterization of spatiotemporal signals (02-Mar-2010)

CLAIM OF PRIORITY

This application claims priority under 35 USC §119(e) to U.S. Patent Application Ser. No. 60/356,317, filed on Feb. 13, 2002, the entire contents of which are hereby incorporated by reference.

FIELD OF THE INVENTION

The present invention relates to methods and apparatus for characterizing dynamic systems.

BACKGROUND OF THE INVENTION

Images over time, also known as video, capture our daily lives, industrial processes, environmental conditions, etc, economically and accessibly. Compression systems can significantly reduce the cost of transmitting lengthy videos. Machine vision systems can register images with accuracy of fractions of a pixel. Supervised cataloging systems can organize and annotate hours and hours of video for efficient re-use.

Many scientific and industrial applications would benefit from exploiting cost effective video systems for better measurement and quantification of dynamic processes. The current techniques require high computational and storage costs and do not allow for a real-time assessment and control of many nonlinear dynamic systems.

The present invention relates generally to digital data and signal processing. It relates more particularly, by way of example, to measuring self similarity in spatiotemporal signals to characterize (cluster, classify, represent), adaptively control their acquisition and/or storage and assign meta-data and further detail processing. It also relates to qualitative and/or quantitative assessment of spatiotemporal sensory measurements of dynamic systems.

SUMMARY OF THE INVENTION

In general, the invention features methods, e.g., machine-based methods, and apparatuses for evaluating a dynamic system. The methods can include one or more of the following steps (the steps need not be but typically are performed in the order provided herein): acquiring a plurality of images representative of the dynamic system in two or more dimensions, e.g., three dimensions; determining similarity between a selected image and one of the other images; and characterizing the selected image as a statistical function of the similarity determined with respect to it, thereby characterizing the dynamic system, e.g., characterizing the selected image as a function of similarity to one or more images acquired from a different part of the two dimensional continuum, e.g., one or both of an earlier acquired image and/or a later acquired image. In the present methods, a selected image can be compared with one or a plurality of other images, e.g., N images, wherein N is selected by the user and can be any number between 1 and the total number of images acquired, e.g., 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 30, 40, 50, 60, 70, 80, 90, 100 or more, and any number in between. The two dimensions can include any dimensions, including but not limited to time, frequency spectrum, temperature, presence or absence of an attribute of the system. The determining step can include determining similarity between each image and each of the other images; and the characterizing step can include characterizing the dynamic system as a statistical function of the similarities determined with respect to the plurality of images.

Although many of the embodiments described herein refer to time as the two dimensional system it should be understood that analogous embodiments, which acquire images in other dimensions, are included in the invention.

In some embodiments of the invention, the images are acquired by an attentive acquisition or storage method including some or all of the following (the steps need not be but typically are performed in the order provided herein): acquiring images at an initial acquisition and/or storage parameterization, e.g., a first or selected parameterization; determining similarity between selected images, e.g., a more recently acquired image and at least one of the other images, e.g., one or more previously acquired images, e.g., N previously acquired images, where N is set by the user, and can be any number between one and all of the previously acquired images; characterizing the selected images as a statistical function of self-similarity; optionally comparing the characterization with a reference value, e.g., a pre-selected reference value, and optionally adjusting the acquisition or storage parameterization as a function of the self-similarity of the images. In some embodiments, the pre-selected reference value is a measure of change and/or the rate of change in the dynamic system, e.g., self-similarity.

In another aspect, the present invention features methods, e.g., machine-based methods, for evaluating a dynamic system over time. The method includes one or more of and preferably all of (the steps need not be but typically are performed in the order provided herein): acquiring a plurality of images representative of the dynamic system over time; determining similarity between a selected image and one of the other images; and characterizing the selected image as a statistical function of the similarity determined with respect to it. The determining step can include determining similarity between each image and each of the other images; and the characterizing step can include characterizing the dynamic system as a statistical function of the similarities determined with respect to the plurality of images.

In another aspect, the present invention provides methods, e.g., machine-based methods, for evaluating a dynamic system over time includes some or all of (the steps need not be but typically are performed in the order provided herein): acquiring a plurality of images representative of the dynamic system in two or more, e.g., three dimensions, such as time, space, or time and space; determining self-similarity among a representative set of images; and characterizing the set of images as a statistical function of self-similarity. The two dimensions can include any of time, space, frequency spectrum, temperature, presence or absence of an attribute of the system. In some embodiments, the determining step can include determining self-similarity between some or all of the plurality of images; and the characterizing step can include characterizing the dynamic system as a statistical function of the self-similarities determined with respect to the plurality of images. In some embodiments, the images are acquired by a method comprising acquiring images at an initial acquisition and/or storage parameterization; determining similarity between selected images; characterizing the selected images as a statistical function of self-similarity; optionally comparing the characterization with a reference value; and optionally adjusting the acquisition or storage parameterization as a function of the self-similarity of the images. In some embodiments, the pre-selected reference value is a measure of change and/or the rate of change in the dynamic system, e.g., self-similarity.

In another aspect, the present invention features methods, e.g., machine-based methods, for evaluating a dynamic system. The method includes one or all, typically all, of the following (the steps need not be but typically are performed in the order provided herein): acquiring a plurality of images representative of the dynamic system over time; determining self-similarity among a representative set of images, e.g., some or all of the images, e.g., every other image, every third image, randomly selected images, etc.; and characterizing the set of images as a statistical function of self-similarity.

In some embodiments, the determining step can include determining self-similarity between all of the plurality of images; and the characterizing step can include characterizing the dynamic system as a statistical function of the self-similarities determined with respect to the plurality of images.

In some embodiments, the images are acquired by a method, e.g., a machine-based method, comprising acquiring images at an initial acquisition and/or storage parameterization; determining similarity between selected images; characterizing the selected images as a statistical function of self-similarity; optionally comparing the characterization with a reference value; and optionally adjusting the acquisition or storage parameterization as a function of the self-similarity of the images. In some embodiments, the pre-selected reference value is a measure of change and/or the rate of change in the dynamic system, e.g., self-similarity. In some embodiments, the statistical function is a measure of entropy. In some embodiments, the statistical function is Shannon's entropy function. In some embodiments, the statistical function is:
H_j=−ΣP_jlog₂(P_j)/log 2(n)  (10).

In some embodiments, the determining step can include determining pair-wise correlations between images, e.g., pairs of images, for example, determining pair-wise correlations between a plurality of images that comprise a window of length n images. In some embodiments, the determining step includes approximating a correlation between images separated by more than n by treatment of intervening pair-wise correlations as transitional probabilities. In some embodiments, the determining step can include determining long-term and short-term pair-wise correlations between images. In some embodiments, the determining step can include generating a matrix of the similarities. The determining step can include generating a matrix, e.g., a correlation matrix, that is any of square, normalized, comprised of probabilities, and has a diagonal of ones. In further embodiments, the method includes applying a matrix operation to the matrix in order to characterize the dynamic system.

In some embodiments of the invention, the images can be acquired from a sensor. The sensor can be any sensor known in the art, including but not limited to a video camera or other device suitable for acquisition of spatiotemporal or other signals, regardless of whether those signals represent the visual spectrum. The images can be acquired by any method known in the art, and can include any of (i) an image captured by a sensor, and (ii) a processed form of an image captured by a sensor. The processed form of the image can be any processed image known in the art, including but not limited to (i) a filtered form of an image captured by the sensor, (ii) a windowed form of the image captured by the sensor, (iii) a sub-sampled form of the image, (iv) an integration of images captured by the sensor over time, (v) an integration of a square of images captured by the sensor over time, (vi) a gradient-direction form of the image, and/or (vii) a combination thereof.

In another aspect, the invention features a method, e.g., a machine-based method, of attentively acquiring or storing images representative of a dynamic system over time. The method includes some or all, typically all, of the following steps (the steps need not be but typically are performed in the order provided herein): acquiring, at a selected acquisition and/or storage parameterization, a plurality of images representative of the dynamic system over time; determining similarity between a selected image and at least one of the other images; characterizing the images as a statistical function of self-similarity; optionally comparing the characterization with a reference value, e.g., a pre-selected reference value, and optionally adjusting the acquisition and/or storage parameterization as a function of the self-similarity of the images. In some embodiments, the acquisition parameterization can be set to drive the statistical function to a predetermined level, e.g., close to zero. In some embodiments, the acquisition parameterization can be set so that at least one or more most recently acquired images reflects a predetermined rate of change. In some embodiments, the acquisition parameterization can be set so that at least one or more most recently acquired images reflects a predetermined rate of motion, shape change, focal change, temperature change, intensity change.

Thus in some embodiments of the invention, the images are acquired by an attentive acquisition or storage method including some or all of the following (the steps need not be but typically are performed in the order provided herein): acquiring images at a first acquisition parameterization; determining similarity between a selected image, e.g., a more recently acquired image, and at least one of the other images, e.g., one or more previously acquired images, e.g., N previously acquired images, where N is set by the user, and can be any number between one and all of the previously acquired images; characterizing the images as a statistical function of self-similarity; optionally comparing the characterization with a reference value, e.g., a pre-selected reference value, and optionally adjusting the acquisition or storage parameterization as a function of the self-similarity of the images. In some embodiments, the pre-selected reference value is a measure of change and/or the rate of change in the dynamic system, e.g., self-similarity.

In some embodiments, the acquisition parameterization includes, but is not limited to, any of acquisition rate, exposure, aperture, focus, binning, or other parameter.

In some embodiments, at least selected ones of the acquired images are buffered for potential processing. In some embodiments, at least selected ones of the buffered images are processed. In some embodiments, at least selected ones of the acquired images are stored.

In another aspect, the present invention features a method, e.g., a machine-based method, of determining movement of an object. The method includes some or all of the following (the steps need not be but typically are performed in the order provided herein): acquiring a plurality of images of the object; selecting a window of interest in a selected image, the selecting step including performing at least one autocorrelation between a candidate window and a region in which the candidate window resides in the selected image; identifying movement of the object as function of a cross-correlation between the window of interest and corresponding window in another of the images, e.g., by performing at least one autocorrelation between a candidate corresponding window in the another image and a region in that image in which that candidate window resides, optionally by finding a maxima in the cross-correlation. The images can be acquired by a method described herein, including a method including attentive acquisition or storage, wherein the storage or acquisition parameterizations are optionally adjusted as a function of the self-similarity of some subset of the acquired images.

In another aspect, the present invention provides a method, e.g., a machine-based method, for determining movement of an object. The method includes some or all of the following (the steps need not be but typically are performed in the order provided herein): acquiring a plurality of images of the object; selecting a window of interest in a selected image, the selecting step including performing at least one autocorrelation between a candidate window and a region in which the candidate window resides in the selected image; performing at least one autocorrelation on a window that corresponds to the window of interest in another of the images; and identifying movement of the object as function of displacement of the characterizing portions of the autocorrelations, e.g., by matching at least characterizing portions of the autocorrelations. In some embodiments, the images are acquired by a method including attentive acquisition or storage, wherein the storage or acquisition parameterization are optionally adjusted as a function of the self-similarity of some subset of the acquired images.

In another aspect, the present invention provides a method, e.g., a machine-based method, of analyzing motion in a plurality of images. The method includes some or all of the following (the steps need not be but typically are performed in the order provided herein): acquiring a plurality of images, selecting a plurality of windows of interest in a selected image, the selecting step including performing, for each window of interest, at least one autocorrelation between a candidate window and a region in which the candidate window resides in the selected image; and identifying motion vectors as function of a cross-correlation between each window of interest and a corresponding window in another of the images, e.g., by performing at least one autocorrelation between a candidate corresponding window in another image and a region in that image in which that candidate window resides, and optionally finding a maxima in the cross-correlations. In some embodiments, the images are acquired by a method including attentive acquisition or storage, wherein the storage or acquisition parameterizations are optionally adjusted as a function of the self-similarity of some subset of the acquired images. In some embodiments, the method also includes segmenting the image as a function of the motion vectors, e.g., by finding one or more sets of motion vectors with minimum square distances with respect to one another.

In another aspect, the invention provides a method, e.g., a machine-based method of analyzing motion in a plurality of images. The method includes some or all, typically all, of the following (the steps need not be but typically are performed in the order provided herein): acquiring a plurality of images of the object; selecting a plurality of windows of interest in a selected image, by performing, for each window of interest, at least one autocorrelation between a candidate window and a region in which the candidate window resides in the selected image; for each window of interest, performing at least one autocorrelation on a respective corresponding window in another image; and identifying motion vectors as functions of displacements of the characterizing portions the autocorrelations of each window of interest and the corresponding window in the another image, e.g., by matching at least characterizing portions of the autocorrelations. In some embodiments, the images are acquired by a method including acquiring images at an initial acquisition and/or storage parameterization; determining similarity between selected images; characterizing the selected images as a statistical function of self-similarity; optionally comparing the characterization with a reference value; and optionally adjusting the acquisition or storage parameterization as a function of the self-similarity of the images. In some embodiments, the pre-selected reference value is a measure of change and/or the rate of change in the dynamic system, e.g., self-similarity.

In some embodiments, the method also includes segmenting the image based on self-similarity, e.g., as a function of the motion vectors, e.g., by finding one or more sets of motion vectors with minimum square distances with respect to one another.

In the methods of the present invention, the dynamic system is a dynamic biological system including at least one biological unit as defined herein. In some embodiments, the biological unit is undergoing morphological change, e.g., cell differentiation, spreading, contraction, phagocytosis, pinocytosis, exocytosis, growth, death, division, and polarization.

In some embodiments of the present invention, the dynamic biological system is in a single well, e.g., one or more wells, e.g., one or more wells of a dish having multiple wells. In some embodiments, the biological units are on an addressable array, e.g., a cell chip, a multi-well plate, e.g., 96 wells, etc.

In some embodiments of the present invention, the plurality of images representative of the dynamic system are images of a single biological unit.

In some embodiments, the biological unit is motile.

In some embodiments, the biological unit is undergoing cell division, e.g., undergoing meiosis or mitosis.

In some embodiments, the biological unit is undergoing cell adherence, e.g., is adjacent to, in contact with, or adhered to a second entity during image acquisition. The second entity can be a surface or another biological unit.

In some embodiments, the biological units are subcellular objects such as proteins, nucleic acids, lipids, carbohydrates, ions, or multicomponent complexes containing any of the above. Further examples of subcellular objects include organelles, e.g., mitochondria, Golgi apparatus, endoplasmic reticulum, chloroplast, endocytic vesicle, exocytic vesicles, vacuole, lysosome, nucleus. In some embodiments, the biological unit is labeled, e.g., with magnetic or non-magnetic beads, antibodies, fluorophores, radioemitters, and labeled ligands. The radioemitter can be an alpha emitter, a beta emitter, a gamma emitter, or a beta- and gamma-emitter. The label can be introduced into the biological unit using any method known in the art, including administering to cells or ogranisms, by injecting, incubating, electroporating, soaking, etc. Labelled biological units can also be derived synthetically, chemically, enzymatically, or genetically, e.g., by creation of a transgenic animal expressing GFP in one or more cells, or expressing a GFP-tagged protein in one or more cells. The label can also be chemically attached, e.g., a labelled antibody or ligand.

In one aspect, the present invention provides a method, e.g., a machine-based method, for evaluating an attribute of a biological unit over time. The method includes, some or all, typically all, of the following (the steps need not be but typically are performed in the order provided herein): providing a plurality of images representative of the biological unit over time; evaluating the similarity between a selected image and one of the other images to determine a pairwise similarity measurement, e.g., by computed pairwise correlations or by employing fourier optics; generating a self-similarity matrix comprising the pairwise similarity measurement; and characterizing the biological unit as a function of the self-similarity matrix, e.g., by generating eigenvalues and/or entropic indices from the self-similarity matrix, thereby evaluating the attribute of the biological system. In some embodiments, the images are acquired by a method acquiring images at an initial acquisition and/or storage parameterization; determining similarity between selected images; characterizing the selected images as a statistical function of self-similarity; optionally comparing the characterization with a reference value; and optionally adjusting the acquisition or storage parameterization as a function of the self-similarity of the images. In some embodiments, the pre-selected reference value is a measure of change and/or the rate of change in the dynamic system, e.g., self-similarity. In some embodiments, similarity is determined between the selected image and all of the other images.

In some embodiments, the attribute is one or more of the following: cell morphology, cell migration, cell motility, cell death (e.g., necrosis or apoptosis), cell division, binding to or interacting with a second entity, organismal development, organismal motility, organismal morphological change, organismal reproduction, and the movement or morphological change of individual tissues or organs within an organism.

In some embodiments, the method includes selecting a plurality of images and evaluating the similarity between pairs of images to determine a pairwise similarity measurement, e.g., by computed pairwise correlations or by employing fourier optics; and generating a self-similarity matrix comprising the pairwise similarity measurements.

In some embodiments, the method includes selecting a plurality of the images and evaluating the similarity between all the images to determine a pairwise similarity measurement, e.g., by computed pairwise correlations or by employing fourier optics, and generating a self-similarity matrix comprising the pairwise similarity measurements.

In another aspect, the invention provides methods for evaluating an attribute of a dynamic biological system over time. The method includes some or all, typically all of the following (the steps need not be but typically are performed in the order provided herein): providing a plurality of images representative of the dynamic biological system; generating a motion field from at least two images; and characterizing the dynamic biological system as a statistical function of the motion field, thereby evaluating the dynamic biological system. In some embodiments, the dynamic biological system is characterized using a statistical analysis of motion vectors, by evaluating direction and/or velocity in the dynamic biological system, and/or by determining the distribution of direction or velocity in the dynamic biological system.

In some embodiments, the method includes performing a statistical analysis of velocity as a function of direction and/or a statistical analysis of direction as a function of velocity.

In some embodiments, the method includes detecting one or more moving objects, e.g., biological units, in the image, e.g., based on motion vector colocomotion. In some embodiments, the method includes determining the direction or velocity of the moving object as a function of colocomoting motion vectors. In some embodiments, the method includes performing a statistical analysis of velocity as a function of direction and/or a statistical analysis of direction as a function of velocity.

In some embodiments, the method also includes determining the center of motion for a moving object. In some embodiments, the method includes determining the directional persistence of the moving object, determining the direction or velocity of the center of motion of the moving object, and determining the direction and velocity of the center of motion of the moving object. The method can also include performing a statistical analysis of velocity as a function of direction, and/or statistical analysis of direction as a function of velocity. In some embodiments, the method also includes determining the distribution of direction or velocity of a moving object.

In some embodiments, the method also includes establishing a bounding box for a moving object, e.g., for each moving object. The bounding box can correspond exactly to the maximum dimensions of the object. The bounding box can correspond to the maximum dimensions of the object plus a preselected factor. The size of the bounding box can vary with the self-similarity of the object. In some embodiments, the method also includes analyzing the area within the bounding box, e.g., by applying image segmentation based on raw intensity, texture, and/or frequency. In some embodiments, the method also includes evaluating an attribute of the object.

In some embodiments, the method also includes evaluating an attribute of the object, for example, by a method including some or all, typically all, of the following: providing a plurality of images of the object; evaluating the similarity between a plurality of images of the object; and characterizing the object as a function of the similarity between the images, e.g., by generating a self-similarity matrix. In some embodiments, the images of the object are acquired by a method comprising acquiring images at a first acquisition parameterization; determining similarity between a selected image and at least one of the other images; characterizing the images as a statistical function of self-similarity; and the acquisition parameterization is adjusted as a function of the self-similarity of the images. In some embodiments, the plurality of images is a pair of images.

In some embodiments, the plurality of images of the object comprises images of the area within the bounding box. In some embodiments, the method also includes calculating the dimensions of the object, e.g., a major axis and a minor axis. In some embodiments, the method also includes characterizing the shape of the object as a function of the major axis and the minor axis and/or generating eigenvalues.

Any of the methods described herein can be applied to the characterization of a dynamic biological system. Accordingly, in another aspect, the invention provides methods for characterizing a dynamic biological system comprising a biological unit, e.g., a plurality of biological units, e.g., independently selected from one or more of cells, tissue, organs, and unicellular organisms, multicellular organisms. The method includes some or all, typically all, of the following (the steps need not be but typically are performed in the order provided herein): providing the dynamic biological system; acquiring a plurality of images representative of the dynamic biological system in two dimensions; determining self-similarity between a representative set of the images; and characterizing the set of images as a statistical function of self-similarity, thereby characterizing the dynamic biological system. In some embodiments, the images are acquired by a method comprising acquiring images at an initial acquisition and/or storage parameterization; determining similarity between selected images; characterizing the selected images as a statistical function of self-similarity; optionally comparing the characterization with a reference value; and optionally adjusting the acquisition or storage parameterization as a function of the self-similarity of the images. In some embodiments, the pre-selected reference value is a measure of change and/or the rate of change in the dynamic system, e.g., self-similarity. In some embodiments, the plurality of images is a pair of images.

In some embodiments, the method provides information regarding one or more attributes of the biological unit. In some embodiments, the biological unit is a cell, and in some embodiments, the one or more attributes can be cell motility, cell morphology, cell division, cell adherence. In some embodiments, the biological unit is an organism. In some embodiments, the one or more attributes can be organismal motility, organismal morphological change, organismal reproduction, and the movement or morphological change of individual tissues or organs within an organism.

In some embodiments, the dynamic biological system is manipulated, e.g., by altering temperature, viscosity, shear stress, cell density, composition of media or surfaces contacted, electrical charge, gene expression, protein expression, adding one or more other biological units of the same or different type, or by adding or removing or one or more treatments. In some embodiments, the manipulation is addition or removal of a treatment, e.g., one or more test compounds, e.g., small molecules, nucleic acids, proteins, antibodies, sugars and lipids. In some embodiments, a plurality of dynamic biological system is each exposed to a different manipulation. In some embodiments, a redundant set of dynamic biological systems is exposed to a redundant set of manipulations; for example, if a first set includes six dynamic biological systems, and the six dynamic biological systems are each exposed to a different manipulation, a redundant set would be a second set of six dynamic biological systems exposed to the same six manipulations as the first set, resulting in the exposure of two dynamic biological systems to each test compound.

In some embodiments, the method includes acquiring a plurality of images representative of the dynamic biological system at one or more of the following points: prior to, concurrently with, and subsequent to the manipulation. In some embodiments, the method includes evaluating the effect of a manipulation, e.g., a treatment, on one or more attributes of the one or more biological units.

The methods of the invention can be combined with other methods of evaluating a dynamic biological system, e.g., the effect of one or more drug candidates on a dynamic biological system can be analyzed by a method described herein in combination with a second method. The second method can be a method of the invention or another method. The methods can be applied in any order, e.g., a method of the invention can be used to confirm a “hit” candidate compound identified in a prior screen which does not use a method of the invention.

In some embodiments, the biological unit is a cell. In some embodiments, the attribute can be cell motility, cell morphological change, cell adherence, and cell division.

In some embodiments, the biological unit is an organism. In some embodiments, the attribute can be consisting of organismal motility, organismal morphological change, organismal reproduction, and the movement or morphological change of individual tissues or organs within an organism.

In some embodiments, the dynamic biological system includes a plurality of biological units that are all similar or include two or more different biological units. The biological units can differ genetically e.g., as a result of gene deletion or duplication, targeted mutation, random mutation, introduction of additional genetic material, epigenetically, phenotypically or in developmental stage. The biological units can also differ as a result of exposure to a manipulation, e.g., a treatment, e.g., a test compound.

In some embodiments, the method also includes evaluating the effect of the manipulation on an attribute of a biological unit, and selecting the manipulation for further analysis. The further analysis can be by a method described herein, or by a different method, e.g., a method other than a method of evaluating a dynamic biological system comprising providing the biological unit; acquiring a plurality of images representative of the dynamic system in two dimensions; determining self-similarity between a representative set of images; and characterizing the images as a statistical function of self-similarity.

In some embodiments, wherein the manipulation is the addition or removal of a treatment, the further analysis can be by a high throughput or parallel screen, e.g., a screen wherein a number of dynamic biological systems, e.g., at least 10, 10², 10³, 10⁴, 10⁵, 10⁶, 10⁷, 10⁸, 10⁹, 10¹⁰ or more are manipulated, e.g., exposed to a treatment such as a test compound, e.g., a candidate drug, e.g., a candidate for inhibition or promotion of an attribute, e.g., at least 10, 10², 10³, 10⁴, 10⁵, 10⁶, 10⁷, 10⁸, 10⁹, 10¹⁰ or more different manipulations, e.g., treatments, e.g., test compounds. Thus, in one example, each of a plurality, e.g., at least 10, 10², 10³, 10⁴, 10⁵, 10⁶, 10⁷, 10⁸, 10⁹, 10¹⁰ similar dynamic biological systems, e.g., comprising cells, are exposed to a different test compound, e.g., a different chemical compound. The test compound can come from any source, including various types of libraries, including random or nonrandom small molecule, peptide or nucleic acid libraries or libraries of other compounds, e.g., combinatorially produced libraries. In many cases as discussed above a plurality of the same or similar dynamic biological systems and many different drug candidates are tested, or alternatively different dynamic biological systems, e.g., genetically different, e.g., mutants, are test with a single drug. The screen can be for evaluating a test compound for its ability to interact with a biological unit, receptor or other target, e.g., a screen is selected based on combinatorial chemistry, computer-based structural modeling and rational drug design, determining the binding affinity of the test compound, phage display, and drug western. Such screens can comprise contacting a plurality of members of a library, e.g., a library of compounds having variant chemical structures, with a plurality of dynamic biological systems and selecting a library member having a preselected property, e.g., the ability to affect an attribute of a biological unit.

In some embodiments, the manipulation, e.g., a treatment, e.g., a test compound, was identified in prior screen, e.g., a screen performed prior to the method of the present invention. The prior screen can be by a method described herein or by a different method, e.g., a method other than a method of evaluating a dynamic biological system comprising providing the biological unit; acquiring a plurality of images representative of the dynamic system in two dimensions; determining self-similarity between a representative set of images; and characterizing the images as a statistical function of self-similarity. Examples of such screens include those which are based on binding of a ligand to a target.

In another aspect, the invention provides methods for optimizing the effect of a test compound on an attribute of a biological unit. The method includes some or all, typically all, of the following (the steps need not be but typically are performed in the order provided herein): selecting a first test compound; exposing a dynamic biological system to the first test compound; acquiring a plurality of images representative of the dynamic biological system in two dimensions; determining self-similarity between a representative set of the images; characterizing the set of images as a statistical function of self-similarity; providing a next generation test compound; exposing a dynamic biological system to the next generation test compound; acquiring a plurality of images representative of the dynamic biological system in two dimensions; determining similarity between a representative set of the images; and characterizing the set of images as a statistical function of self-similarity. The activity of the first and the next generation compound can be compared, e.g., with one another of with reference value to evaluate the compound. The steps of the method can be repeated with successive next generation compounds, e.g., to optimize the structure of a test compound, e.g., to maximize the effect of the test compound on an attribute.

In some embodiments, the first test compound and the next generation compound are selected from a database of compounds of known chemical structure. In some embodiments, the next generation compound is a variant, e.g., a structural variant, of the first test compound. For example, a particular moiety or functional group can be altered once or serially to identify optimized structures. In some embodiments, more than one moiety or functional groups can be varies, simultaneously or serially.

In some embodiments, the method also includes selecting a first treatment; providing a next generation treatment; exposing a dynamic biological system to the next generation treatment; acquiring a plurality of images representative of the dynamic biological system in two dimensions; determining self-similarity between a representative set of the images; and characterizing the plurality of images as a statistical function of self-similarity.

In some embodiments, the method also includes acquiring a plurality of images representative of the dynamic biological system at one or more of the following points: prior to, concurrently with, and subsequent to the exposure to the next generation treatment.

In another aspect, the invention also provides a method, e.g., a machine-based method, for determining the relationship between a property of a test compound, or a series of test compounds, and the ability to modulate an attribute of a biological unit. The method includes some or all, typically all, of the following (the steps need not be but typically are performed in the order provided herein): providing a first test compound having a first property, e.g., a first chemical structure or property, e.g., a first moiety or structural group at a selected position; exposing a dynamic biological system comprising a biological unit to the first test compound; analyzing the dynamic biological system by a method described herein, e.g., by acquiring a plurality of images representative of the dynamic biological system in two dimensions; determining self-similarity between a representative set of the images; characterizing the set of images as a statistical function of self-similarity; providing a second test compound having at least one property similar to a property of the first treatment and at least one property that differs, e.g., a moiety or functional group, e.g., an R group is varied between the first and second compound; exposing a dynamic biological system comprising a biological unit to the second test compound; analyzing the dynamic biological system by a method described herein, e.g., by acquiring a plurality of images representative of the dynamic biological system in two dimensions; determining self-similarity between a representative set of the images; characterizing the set of images as a statistical function of self-similarity; and correlating the similar property of the first and second test compounds with an effect on one or more attribute.

In some embodiments, the property of the test compound is selected from the group consisting of chemical structure, nucleic acid sequence, amino acid sequence, phosphorylation, methylation, sulfation, nitrosylation, oxidation, reduction, affinity, carbohydrate structure, lipid structure, charge, size, bulk, isomerization; enantiomerization; and rotational property of a selected moiety, or any physical or chemical property of the structure. For example, a moiety is present on a scaffold and the moiety is varied allowing analysis of the ability of the moiety, or other moiety at the same position, to affect an attribute.

In another aspect, the present invention provides a method, e.g., a machine-based method, for evaluating or selecting a target, e.g., to mediate a selected attribute of a biological unit. The method includes some or all, typically all of the following (the steps need not be but typically are performed in the order provided herein): providing a first test compound, e.g., a ligand, for a first target, e.g., a receptor; contacting a dynamic biological system comprising a biological unit with the first test compound; and performing a method described herein, e.g., a method including: (1) acquiring a plurality of images representative of the dynamic biological system in two dimensions; (2) determining self-similarity between a representative set of the images; and (3) characterizing the set of images as a statistical function of self-similarity; thereby providing a value for a parameter related to the effect of the first test compound on the selected attribute; providing a second test compound, e.g., a ligand, for a second target, e.g., a different receptor; contacting one or more biological units with the second test compound; and performing a method a method described herein, e.g., a method including: (1) acquiring a plurality of images representative of the dynamic biological system in two dimensions; (2) determining self-similarity between a representative set of the images; and (3) characterizing the set of images as a statistical function of self-similarity, thereby providing a value for a parameter related to the effect of the second test compound on the selected attribute; and comparing the parameters and selecting the test compound having the desired effect on the attribute, thereby selecting a target.

In one aspect, the invention provides a method, e.g., a machine-based method, for evaluating the activity of a gene. The method includes some or all, typically all, of the following (the steps need not be but typically are performed in the order provided herein): the method comprising: providing a first reference biological unit or plurality thereof; providing a second biological unit or plurality thereof wherein the activity of the gene is modulated as compared to the first biological unit, and performing a method described herein, e.g., a method comprising: (1) acquiring a plurality of images representative of the dynamic biological system in two dimensions; (2) determining self-similarity between a representative set of the images; and (3) characterizing the set of images as a statistical function of self-similarity, thereby evaluating the activity of the gene.

In some embodiments, the gene is modulated by directed or random mutagenesis. In some embodiments, a plurality of genes are modulated, e.g., by random mutagenesis. In some embodiment, the plurality of genes are selected from the results of an expression profile experiment, e.g., a gene chip experiment or are expressed in or known to be associated with a disease state.

In some embodiments, the plurality of genes are modulated in a plurality of biological units and/or dynamic systems. In some embodiments, a unique gene is modulated in each of a plurality of biological units and/or dynamic systems.

In some embodiments, the method includes manipulating the dynamic system and evaluating the effect of the manipulation on the activity of the gene.

In another aspect, the invention provides a method, e.g., a machine-based method, of evaluating the interaction of a biological unit with a surface. The method includes some or all, typically all, of the following (the steps need not be but typically are performed in the order provided herein): providing a dynamic biological system comprising a biological unit; contacting the dynamic biological system with a surface; and performing a method described herein, e.g., a method comprising: (1) acquiring a plurality of images representative of the dynamic biological system in two dimensions; (2) determining self-similarity between a representative set of the images; and (3) characterizing the set of images as a statistical function of self-similarity, thereby evaluating the interaction of the biological unit with the surface.

In some embodiments, the surface is uniform. In some embodiments, the surface is variable, e.g., comprises pores, openings, concavities, convexities, smooth areas, and rough areas, changes in composition, changes in charge, and/or the presence or absence of a test compound, e.g., the test compound is present in a gradient.

In some embodiments, the interaction can be adherence to the surface, movement across the surface, release from the surface; deposit or removal of a material on the surface, and infiltration of pores or openings.

In another aspect, the invention provides a method, e.g., a machine-based method, for evaluating the propensity of one or more biological units to interact with, e.g., infiltrate a structure, e.g., the surface of a prosthetic device, e.g., stainless steel, titanium, ceramic, and synthetic polymer. The method includes some or all, typically all, of the following (the steps need not be but typically are performed in the order provided herein): providing one or more biological units; providing a structure, e.g., a piece of a prosthetic device; performing a method comprising: (1) acquiring a plurality of images representative of the dynamic biological system in two dimensions; (2) determining self-similarity between a representative set of the images; and (3) characterizing the set of images as a statistical function of self-similarity; thereby evaluating the propensity of the biological units to infiltrate a structure. In some embodiments, the method also includes exposing the biological units to a test compound and evaluating the effect of the test compound on the propensity of the biological units to infiltrate the structure.

In another aspect, the invention provides a method, e.g., a machine-based method of evaluating the interaction between a biological unit and a second entity, e.g., bone cells, tissues, e.g., transplant tissue, e.g., allogeneic, autologous, or xenogeneic tissue. In some embodiments, the method includes providing one or more biological units; providing a second entity; performing a method described herein, e.g., a method including: comprising: (1) acquiring a plurality of images representative of the dynamic biological system in two dimensions; (2) determining self-similarity between a representative set of the images; and (3) characterizing the set of images as a statistical function of self-similarity, thereby evaluating the interaction of the biological units and the second entity.

In another aspect, the invention provides a method, e.g., a machine-based method, of evaluating a test compound. The method includes some or all, typically all of the following: providing a first biological unit; providing a second biological unit that is the same as the first biological unit or plurality thereof wherein the first and second biological units are preferably the same; contacting the second biological agent with the test compound; performing a method described herein, e.g., a method including: acquiring a plurality of images representative of the dynamic biological system in two dimensions; determining self-similarity between a representative set of the images; and characterizing the set of images as a statistical function of self-similarity; and comparing the attributes of the biological unit in the presence and absence of the test compound, thereby evaluating the test compound. In some embodiments, the method also includes: providing a second test compound; contacting the first biological unit with the second test compound; performing a method described herein, e.g., a method including: (1) acquiring a plurality of images representative of the dynamic biological system in two dimensions; (2) determining self-similarity between a representative set of the images; and (3) characterizing the set of images as a statistical function of self-similarity; and comparing the attributes of the biological unit in the presence and absence of the test compound.

The invention includes the systems and apparatus described herein. Accordingly, in one aspect, the invention provides an apparatus that includes some or all, typically all, of the following: an acquisition system, e.g., a sensor, configured to acquire images, e.g., spatiotemporal or other signals, representative of a dynamic system at an adjustable parameterization; a storage device configured to store the images at an adjustable parameterization; and a computing device configured to analyze similarities between the images (e.g., images acquired by the acquisition system). The apparatus can also include a display device. In some embodiments, the apparatus also includes buffering means for potential processing of one or more images.

In some embodiments, the computing device is further configured to adjust the acquisition parameterization of the acquisition device and/or the storage parameterization of the storage device as a statistical function of the similarity between images, e.g., includes setting the acquisition parameterization to drive the statistical function to a predetermined level, e.g., setting the acquisition and/or storage parameterization so that at least one or more most recently acquired images reflects a predetermined rate of change, e.g., setting the acquisition parameterization so that at least one or more most recently acquired images reflects a predetermined rate of motion, shape change, focal change, temperature change, or intensity change. The acquisition parameterization can be, but is not limited to, acquisition rate, exposure, aperture, focus, binning, or other parameter. The storage parameterization can be, but is not limited to, image labeling.

In another aspect, the invention features a database. The database includes a plurality of records wherein each record includes at least one of the following:

a. data on the identity of a biological unit;

b. data on an attribute of the biological unit; and

c. data on a the effect of one or more manipulation, e.g., a treatment, e.g., the administration of a test compound, on the attribute.

In some embodiments, the data on the identity of the biological unit includes genotypic and phenotypic information, e.g, information regarding the presence, absence, spatial location, or temporal expression of a gene, and/or information regarding the presence or absence of one or more mutations.

In some embodiments, the phenotypic data includes one or more of cell type, organism type, cell status, and age.

In some embodiments, the database includes at least two records, and the manipulation in each of the records differs from the other record. In some embodiments, the manipulation is administration of a test compound and in one record the preselected factor includes administration of the test compound and in the other record the test compound is not administered or is administered at a different dose. In some embodiments, the database includes at least two records, and at least one manipulation in each of the records differs from the other record. In some embodiments, at least one manipulation in the records differs and at least one of the other manipulations is the same.

In another aspect, the invention provides a method for identifying an unknown target, e.g., a gene, protein or other cellular or extracellular target. The method includes some or all, typically all, of the following: providing a database described herein, including at least a first record having data about the effect of a first manipulation on a attribute, where the target of the first test compound is known; and at least a second record having data about the effect of a second manipulation on an attribute, where the target of the second manipulation is unknown; and comparing the data in the first record to the data of the second record.

In some embodiments, the database is in computer readable form.

Methods and apparatus are described herein to assess self-similarity over the entire length of a spatiotemporal signal as well as on a moving temporal window. In one aspect, a real time signal acquisition system is provided in which, self-similarity in a moving temporal window enables adaptive control of acquisition, processing, indexing, and storage of the said spatiotemporal signal. In another aspect, such system as provided in which self-similarity in a moving temporal window provides means for detecting unexpected. In yet another aspect such system as provided in which, self-similarity in over the entire length of a spatiotemporal signal or a moving or stationary window, provides means to characterize, classify, and compare dynamic processes viewed.

A method for measuring self-similarity of a spatiotemporal signal in systems according to some aspects of the invention includes steps of assuring and maintaining of acquisition at or near the rate of dominant motion in the visual scene as to assure as near linear relationship between any two successive frames or times of acquisition. Further processing includes comparison of near and long range, distance in time, frames. Said comparisons for a temporal window, length greater than one can be arranged in a matrix arrangement. In accordance to further aspects of this invention the said matrix is used to compute self-similarity for the respective temporal window.

Further aspects of the invention provide such methods and apparatus that use an unsupervised learning algorithm to classify statistical dependence of one or more sections of the acquired spatiotemporal signal on any other section of said signal uncovering periodic, regularities, or irregularities in the scene. Said algorithm can be unsupervised insofar as it requires no tuned or specific template or noise model to measure self-similarity and thus describe the visual dynamics.

Further aspects of the invention provide for efficient, cost effective and salient computation of cross matches between frames separated by long range of temporal distance by utilizing the persisted operated model of linearity or near linearity of successive frames and geometric mean of cross-matches in the frequency domain.

Further aspects of the invention provide such methods and apparatus that prescribe an efficient, cost effective, and salient measurement of visual self-similarity across indefinitely long acquisition duration. Visual self-similarity measured, according to related aspects of the invention, can be used to characterize, quantify, and compare the underlying dynamic system to the best representation of the its visual projection.

Further aspects of the invention provide automatic methods for recording of exemplary templates of a acquisition session. A frame is labelled an exemplary template when it is kernel of a sequence of frames acquired consecutively whose incremental temporal integration forms a linear set with any and every frame in the sequence. A related aspect of this invention is its providing means to recognize novel and unpredictable frame or sequence of frames by their nonlinear relationship with the rest of the acquired frames.

Related aspects of the invention provide such methods and apparatus that provide predictive feedback to the acquisition sub-system as to appropriateness of the parameters) controlling temporal sampling, e.g., in the case of video acquisition, typically, frame-rate and exposure.

An information theoretic mechanism can be used, according to still further aspects of the invention, to compute whole or self-symmetry measurement for a group of frames in the buffer. The whole characterization, according to related aspects of the invention, can be tracked and matched to characterizations generating a predictive signal for adjustment of acquisition parameters for frame-rate and exposure as well as identifying frame sequences of interest.

Further aspects of this invention provide such methods and apparatus that prescribe Fourier optics system for computation of cross matches between successive frames.

Further aspects of the invention provide methods and apparatus as described above that utilize conventional or other acquisition devices to measure motion signatures indicating speed and type of dominant characterizing motion in view.

Still further aspects of the invention provide such methods and as are operationally customized via a script that encapsulates users storage and indexing preferences.

Unless otherwise defined, all technical and scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this invention belongs. Although methods and materials similar or equivalent to those described herein can be used in the practice or testing of the present invention, suitable methods and materials are described below. All publications, patent applications, patents, and other references mentioned herein are incorporated by reference in their entirety. In case of conflict, the present specification, including definitions, will control. In addition, the materials, methods, and examples are illustrative only and not intended to be limiting.

Other features and advantages of the. invention will be apparent from the following detailed description, and from the claims.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram of an embodiment of the apparatus.

FIG. 2A is a high-level block diagram of an embodiment of the method.

FIG. 2B is a detailed block diagram of an embodiment of the method.

FIG. 3 is detailed block diagram of an embodiment of the analysis module.

FIG. 4A is a block diagram of attentive capture initialization.

FIG. 4B is a block diagram of method of the self-similarity calculation.

FIG. 5 is a diagram of a self-similarity matrix and entropic indices.

FIG. 6 is a diagram of the use of overlapping tiles for motion estimation.

FIG. 7 is a block diagram of the method of global motion estimation.

FIG. 8 is a block diagram of the method of estimating self-similarity.

FIG. 9 is a schematic diagram of the method of estimating self-similarity.

FIG. 10 is diagram of the overlap between cellular attributes and therapeutic areas.

DETAILED DESCRIPTION

The present invention provides methods and apparatus for characterizing dynamic systems. Embodiments of the invention are further described in the following description and examples, which do not limit the scope of the invention described in the claims.

A block diagram of an embodiment of the apparatus for acquisition, compression and characterization of spatiotemporal signals includes a sensor(s) (102), data processing device(s) (also known as computing device(s)) (103), storage device(s) (105) and display (104) devices as shown in FIG. 1.

Data processing device(s) (103) includes one or more modules (fabricated in software, hardware or a combination thereof) executing on one or more general or special purpose digital data processing or signal processing device(s) in accordance with the teachings below.

The sensor (102) can be one or more video cameras (of the conventional variety or otherwise) or other devices suitable for acquiring spatiotemporal, thermal or other signals (regardless of whether those signals represent the visible light spectrum) representative of a system to be subjected to characterization, indexing or other processing in accordance with the teachings hereof. In one embodiment, the sensor can be monitoring a dynamic system as defined below. However, the teachings herein may also be applied to the monitoring of a non-dynamic system, such as in cases where a system is thought to have the potential to be dynamic, or when a comparison is to be made between systems where at least one system is thought to have the potential to be dynamic.

The sensor can be parameterized or tuned to receive a particular band or bands of frequency, such as might be required, by way of example, for fluorescent imaging techniques. Suitable devices (109) can be inserted between the scene (101) and the sensor to amplify, magnify, or filter or otherwise manipulate the information in the scene prior to its acquisition by the sensor. The output of the sensor (107) is referred to hereafter as an “image” or a “frame,” regardless of the type of sensor and whether or not the image is a direct representation of sensory data, reconstructed sensory data or synthetic data. Element 102 can alternatively be a source of previously acquired video, spatiotemporal or other signals representative of a dynamic system. For the sake of convenience and without loss of generality, element 102 is hereafter referred to as “sensor.”

The sensor (102) can also be, by way of non-limiting example, a source for a multitude of stored frames in two or more dimensions, such as a collection of photographic images, and an embodiment of the present invention can be used to cluster said frames into classes corresponding to measurements of self-similarity, regardless of whether any or all of the frames were acquired from the same system or scene.

Element 102 can also be, by way of further non-limiting examples, two or more cameras or other sensors in a stereo or other multi-source image acquisition system; one or more sensors that include one or more filtering devices between the scene and the signal acquisition device; or an ensemble of sensory modalities, each represented by one or more sensors.

A dynamic system is defined as a system in which values output by a sensor monitoring the system vary across time. A dynamic system can be a system that is “naturally” dynamic, i.e., a system that changes without external perturbation, and would most commonly be viewed by a stationary sensor. A dividing cell, for example, would be a dynamic system. However, a system can be induced to produce varying output from the sensor through a variety of means, including: perturbing or manipulating an otherwise non-changing system being monitored by a stationary sensor, such as would happen when positioning and orienting a semiconductor wafer for photolithography or placing a chemoattractant near a stationary cell; perturbing a sensor that is monitoring a non-changing system, such as would happen when panning a video camera over a document or large photograph; perturbing the signal prior to its output by the sensor through electronic, programmatic or other means; or any combination of perturbations and natural dynamism that would lead to variance in output from the sensor. For the sake of convenience, images are said to be representative of a dynamic system, or particularly a dynamic system over time, regardless of whether the system is inherently dynamic or made to appear dynamic by virtue of imaging modality or any induced perturbation.

Images can be processed before analysis. Processing can include filtering, windowing, sub-sampling, integration, integration of the squares and gradient detection. Images, processed or unprocessed, will be referred to hereafter simply as “images” or “frames”. Images and frames are represented by an array of values representing intensity. A frame or image sequence (106) is a set of arrays of values representing sensory information, where each frame is or could be related to every other frame in some way. In some embodiments, this relationship may be by virtue of the fact that the frames were acquired sequentially by a single sensor, though in other modes this relationship may be through the sharing of similarities in shape, color, frequency or any of a number of other attributes. The sequence may also be defined through ordered or random selection of a subset of frames from a larger set. Frame rate defines the number of frames captured in a unit of time. Exposure time is the length of time a sensor is exposed to the scene (101) while acquiring the data that produces a single frame. Frame rate and exposure time have their usual definitions in the field of visual signal processing. Other sensory modalities have analogous variables.

The illustrated reporting module (203) is comprised of storage media (dynamic, static or otherwise) with suitable capacity for at least temporary storage of video or other spatiotemporal sequences that may be acquired, compressed, characterized and/or indexed by the illustrated embodiment. In FIG. 1, by way of non-limiting example, the storage device (105) is depicted as a disk drive.

The acquisition process starts with the establishment of an initial or first acquisition rate and an attention window (108) size. These parameters can be specified manually or programmatically, based on system capabilities, empirical knowledge about the sensor or the scene, or through other means. The “attention window” is a frame sequence whose length is specified in units of time or some other relevant metric, such as number of frames or interval between peaks in a particular function. One use of the attention window in the present invention is for computing relationships between “short-term” frames, e.g., frames that are close to each other based on measurements of acquisition time, similarity or other metrics. In some embodiments, a maximum frame rate and the corresponding frame size in memory are also derived from the system information. By way of non-limiting example, the attention window size for processing video images representative of cell spreading can range from ½ to many seconds, though other sizes may be used for capturing this and other processes. When an acquisition subsystem is replaced with a signal source, maximum frame rate is preferably the frame rate at which the data was acquired.

In some embodiments, the analysis module contains a first-in-first-out (FIFO) frame sequence buffer, though other buffering designs are possible. Preferably, this buffer is maintained in a high-speed storage area on the data processing device, such as a desktop computer's random access memory, though storage on a disk drive or other digital medium is also possible. In a preferred mode, the frame sequence buffer is sized according to the mathematical relation buffer size=(attention window size in seconds*initial frame rate in seconds*memory space needed for each frames)+an overhead factor. The overhead factor is selected empirically and, for example, can be in the range 1 to 5 percent, depending on memory management design. By way of non-limiting example, a frame sequence buffer for processing video images representative of a biological process may range from 30 to 120 MBytes, though other sizes may be used for these and other processes. Frames in the FIFO may also represent a fixed or variable or adaptively variable sampling of the incoming acquired frames. Incoming frames originate at the sensor (102). Frames exiting the data processing device (103) for storage or display (105 and 104) have associated labels and characterization data attached to them.

In some embodiments, frames are also optionally prefiltered to suppress or promote application-specific spatiotemporal characteristics. Incoming frames, by way of example, could be processed by standard methods in the art to extract gradient direction estimation at a particular spatial scale to amplify signals representative of changes in direction of an object or organism moving in the scene.

In some embodiments, certain analyses are performed on the luminance channel of each frame. In other embodiments, multiple color channels within each frame can be matched separately to corresponding color channels in other frames, with the resulting values combined into a single set of measurements or presented as distinct, one set per color channel. Still other embodiments incorporating visual sensors may use other channels in addition or instead of these, and embodiments incorporating non-visual sensors would use channels appropriate to the information produced by the sensor.

In some embodiments, certain analyses are performed on the dominant frequency band in each frame. This is a preferred mode when the assumption can hold that frequency content changes minimally between successive frames. The choice of frequency band(s) analyzed in other embodiments may be influenced by other factors.

In some embodiments, certain analyses are performed via correlations between sets of individual frames. In other embodiments, a frame might be correlated with a temporal accumulation or per-pixel rank function of some number of related frames. Many variations on this choice for the present embodiment and others noted above, including choices regarding how to process chromatic channels, regions of frames used, and potential preprocessing steps can be implemented to produce similar results.

Frames are transferred into the frame sequence buffer from the sensor (102) in a conventional manner. As widely known in the art, references to said frames can be used to remove the need to utilize system resources for an image copy.

Next, spatiotemporal signals in the acquired frames are analyzed. It is well-known in the art, by way of Parseval's Theorem that the integral of a spatiotemporal signal over time is proportional to the integral of its spatiotemporal frequencies.

∫ x ⁢ ∫ y ⁢ ∫ t ⁢ l ⁡ ( x , y , t ) ≈ ∫ wx ⁢ ∫ wy ⁢ ∫ wt ⁢ F ⁡ ( w x , w y , w t )

Where I is intensity, F is frequency, x and y are spatial coordinates, t is time, w_x and w_y are the frequency components in the spatial dimensions and w_t is the frequency component in the temporal dimension.

Put another way, the integral of the spatiotemporal signal between time t (0→t) and t+n (0→(t+n) is an estimate of the change in spatiotemporal frequencies from time t to (t+n). When frames are acquired at a frame rate above the rate of change of the fastest changing element in the scene, the acquired frames are nearly identical, the integral of the underlying signal approaches a constant value from frame to frame, the difference in information between frames becomes negligible, yet spatial definition within the frame remains high and information content is high. In contrast, when elements change faster than the frame rate of the sensor, the frames are blurred: the integral of the underlying signal also approaches a constant value from frame to frame, but frames lose their spatial definition and consequently information content is reduced. Thus, an estimate of information rate is directly proportional to the rate of change in the temporal autocorrelation function, and consequently in the integral of the spatiotemporal frequencies.

Methods known in the art can be used to estimate changes in the rate of information content, though such estimates have limitations. Art-known compression standards such as MPEG are largely based on an assumption of fixed capture rate and output rate. MPEG encoders use block-based motion calculations to discover temporally redundant data between successive frames. This leads to the implementation of three classes of frames: spatially encoded frames (I), predicted frames (P) and bidirectional frames (B). Encoding frames in this way with a block-based technique, and relying especially on predicted frames to enable efficient compression, leads to data loss that could significantly impair the information content of frames that are found subsequently to be of particular interest. Furthermore, the MPEG method estimates the rate of change in information content using coarse and non-overlapping spatial blocks across a very narrow window (2-3 frames). This leads to further information loss. The net result is that MPEG compression enables temporal integrity in compression and playback, but at the loss of spatial integrity. The present invention enables the preservation of temporal integrity in frame sequences of interest, while also preserving spatial integrity.

Another compression standard, Motion JPEG, does not enable temporal compression and instead applies a variant of the standard single-image JPEG compression to every frame. In Motion JPEG compression, the rate of change in information content is estimated only spatially, and results in chromatic loss. Another approach, employing simple motion detectors, uses the average intensity difference between subsequent frames as an estimate of the rate of change in information content. This approach is limited in a number of ways, including that a change in lighting on a static scene would be perceived as “motion” even though nothing in the scene actually moved.

A human observer can easily and without any previous training measure attributes of a visual dynamic scene. This implies, for example and in a non-limiting way, that there may exist a significant amount of mutual information that is implied and reinforced by each and every frame in an attention window into a dynamic visual scene. In a dynamic system, events captured in closely-spaced frames and those captured in distant frames all impact the rate of change in information content. By performing the present methods in a preferred mode at or near the rate at which frame-to-frame information change is minimized, a characteristic function of the dynamic system can be estimated in small discrete steps where the values produced for a given frame depend on nearby frames as well as distant frames. By way of non-limiting example, such a system could be used to monitor a biological assay in which an event of interest is a particular motion pattern of a nematode worm. The pattern may last only fractions of a second, and may occur infrequently and unpredictably during the 18-day life of a wild-type worm. Nevertheless, moments in which this pattern was sensed would produce reinforcing information over the worm's life, and periods of absence of this pattern would produce reinforcing information of its absence. Therefore, the difference between the two, as represented in a self-similarity function such as those in the present embodiment, would enable the automated detection of each instance of the event of interest. An early realization of importance of both short-term and long-term correlations, as well as self-similarity as a model, was made by Mandelbrot during his work on 800 years of flood data on the Nile River during the construction of the Aswan Dam. Nevertheless, those skilled in the art have not yet found efficient methods to take advantage of long-term correlations in self-similarity analysis. The present invention provides such methods.

Some embodiments of the invention use a Self-similarity matrix for modeling and analyzing spatiotemporal signals, as shown in FIG. 2. In the illustrated embodiment, the self-similarity matrix is a square matrix of normalized positive probabilities having a diagonal of ones, though in other embodiments the self-similarity matrix may have other characteristics instead or in addition. A self-similarity matrix has the form of a symmetric matrix, e.g., a real value Hermitian Matrix. In some embodiments, the invention employs a self-similarity matrix, frames and frame sequences to approximate a temporal autocorrelation of the acquired signal.

In some embodiments the invention exploits the near similarity of frames when sampled temporally at a rate near the dominant motion in the visual scene to approximate an autocorrelation. The nearly similar frames in aggregate approximate a correlation of a given frame with slightly shifted versions of itself. In other embodiments, correlations can be performed at a multitude of frequencies, or an autocorrelation function can be computed using methods well known in the arts.

Other embodiments of the invention might use other learning or approximation algorithms. Popular methods for analyzing spatiotemporal signal include PCA or ICA (Principal Component Analysis or Independent Component Analysis). In particular, PCA and ICA methods both employ a correlation matrix and are widely used in lossy compression methods.

In the illustrated embodiment, the self-similarity matrix is populated with all pairwise similarity measurements. Other embodiments might measure pairwise dissimilarity. Such measurement is straightforward to achieve within the present invention due to the fact that the sum of a similarity measurement and its corresponding dissimilarity measurement is always 1.0. Thus, (1—similarity measurement) yields the dissimilarity measurement. Known in the art is that Fourier optics can also be used to produce pairwise correlations between sequential frames as they are captured by a sensor. Frames generated in this way may be used for further analysis in accordance with the teachings herein.

In some embodiments, the pairwise similarity metric chosen is a normalized correlation (multiplicative) applied to the entire frame. The result of this kind of cross-match is a scalar value from −1.0 (perfect mismatch) to 1.0 (perfect match). In the illustrated embodiment, for reasons described below, we use the square of the cross match. In any case, the similarity metric is associative (Similarity (a,b)=Similarity (b,a)), Reflective (Similarity (a,a)=1.0), and Positive (Similarity (a)>0).

A well-known method for establishing image similarities is the “sum of absolute differences”. This method has both advantages and disadvantages when compared to normalized correlation. Advantages to using the sum of absolute differences include:

(a) It is often faster on many computer platforms, and

(b) It is well-defined on flat intensity patches.

Disadvantages include:

(c) Cross-match result is not normalized,

(d) Cross-match result is not invariant to linear changes in intensity, and

(e) It is not equivalent to linear filtering.

In some embodiments, the present implementation of normalized correlation takes advantage of modem computing architectures to achieve near-parity in computational performance with a “sum of absolute differences” approach, and also detects when the input images have zero variance, thus enabling good definition on flat intensity patches.

In other embodiments, the cross-match operation can be accomplished by other multiplicative, subtractive, feature-based or statistical operations. In the illustrated embodiment, the similarity measurements have the additional property of behaving as spatiotemporal matched filters. Yet another embodiment might use other correlation-based motion detectors.

The self-similarity estimator module (302) estimates short term temporal similarity and approximates long term temporal similarity. In binocular applications, self-similarity is measured between each frame from each camera and every frame acquired by the other camera. In yet other applications, integration of spatiotemporal signals or the square of such signal may be used.

Short-term frames refer to frames in the above-mentioned buffer. Long-term frames refers to frame no longer in the buffer. The role of self-similarity is twofold: first, to boost nearby frames that are similar, and second, to reduce the contribution of dissimilar frames elsewhere. Those skilled in the art may recognize the usage of self-similarity in representing a nonlinear dynamic system or a dynamic system of unknown linearity. Self-similarity is estimated from the:

(1) SS₆₆=Self-Similarity Matrix (X, Δ) where X is the time series, and Δ is the time duration over which self-similarity is measured. In some embodiments, the self-similarity matrix is a square matrix.

To estimate short-term self-similarity, similarity of all frames in the buffer can be measured.

(2) SS_{short-term, Δ}=Self-Similarity Matrix (X, Δ) where X is time sequence of frames, and Δ is the length of the buffer, and

(3) SM(i, j)=correlation (min(i,j), max(i,j)), for all frames i, and j !=i (associativity)

(4) SM(i, i)=1.0 (reflectivity)

In some embodiments, as frames are acquired and placed in the image buffer (301), similarity matching is performed on at least the most recent frame and the frame immediately prior to it. Long-term pairwise matching between any two frames is approximated by treating the string of pairwise correlations separating the frames as transitional probabilities. Similarity metrics other than those described herein could be used, with an impact on the accuracy of this approximation. Correlation in the spatial domain is equivalent to a conjugate multiplication in the frequency domain. In some embodiments,

(5) SS_{long-term, Δ}=Self-SimilarityMatrix (X, Δ) where X is a sequence of frames and Δ is the length of the FIFO, and

(6) SM (i, j)=correlation(i,j), for all i, j and distance (i,j)=1 (associativity)

(7) SM(i, i)=1.0 (reflectivity)

(8) SM(i,j)=(Π_i->jSM (i, i+1))^1/(j-i),

(8A) where j>(i+1)

Equation (8) calculates the geometric mean of the pairwise correlation values separating i and j. Note that the approximations are associative, degrade with distance between i, and j, and produce 0 when any pairwise correlation along the way is 0. Further note that approximations are symmetric, SM(i,j)=SM(j,i).

Long-term and short-term similarities are combined to establish a self-similarity matrix for the entire duration of analysis. In some embodiments, lengthy durations may have windows of time where both short-term estimations and long-term approximations are used for similarity measurements. In some embodiments, shorter durations use short-term estimations entirely. Typically, this choice would largely be based on computational resources.

Further processing of the self-similarity matrix is independent of how the similarity measurements were produced; that is, the measurements can be produced via short-term estimation, long term approximation, or any weighted, normalized, or raw combination of the two.

In some embodiments, the self-similarity matrix (505) is then used to estimate a measure of self-similarity for every frame with a frame sequence, as shown in FIG. 5. In some embodiments, an estimation of entropic indices for each frame is computed from the self-similarity matrix (506). In some embodiments, by way of non-limiting example, Shannon's Entropy Calculation is used. Shannon's entropy calculates the average uncertainty removed by a random variable attaining a set of measurements.

P j = SM j / ∑ j ⁢ SM i , j ⁢ ⁢ normalization ( 9 )

(10) H_j=−ΣP_jlog₂(P_j)/log 2(n)where n is number of frames

For a given sequence, a random variable represents a set of entropic indices for each frame in the sequence. If all the frames in the sequence are exact copies, uncertainty is completely removed and Shannon's entropy is nearly zero. On the other hand, if every frame is completely dissimilar to all other frames, no uncertainty is removed and Shannon's entropy is nearly one.

The self-similarity matrix can be evaluated over the length of a frame sequence where said sequence can be fixed or can be a sliding window across a larger sequence. The calculation of self-similarity for said sliding window uses in preferred mode standard and well-known optimizations to reduce the computational cost to a linear function of the number of frames in the frame sequence.

Existing methods can meaningfully quantifying events of interest in images and image sequences, but only after a spatial or temporal segmentation step. In most cases, these steps are costly in terms of computational time and human intervention, and are impaired by the natural occurrence of noise in the signal. In some embodiments of the invention, dynamic systems presenting events of interest with characteristic visual signatures can be quantified without temporal or spatial segmentation. An example is a spatiotemporal signal representing a visual focusing process. Frames from said signal, as an example, may represent temporally out-of-focus frames, increasingly sharper frames, and in-focus frames. By way of example and for illustration, it is well known that out-of-focus images can be estimated as an in-focus image of the scene convolved with Gaussians. Gaussians with larger standard deviations, when convolved with an in-focus scene image, result in a more blurred image, and conversely, convolving the in-focus scene image with Gaussians having smaller standard deviations would result in a less blurred image. If we assume that pairwise similarity among said frames is proportional to (σ_a-σ_b)², where σ is the standard deviation, the self-similarity matrix tabulates all pairwise similarity measurements. The frame corresponding to the Gaussian with the smallest standard deviation will have the largest accumulated dissimilarities as calculated by either shannon's entropy or a sum of squares method. Hence it will correspond to sharpest image.

The self-similarity matrix can be further manipulated in a number of ways. A standard method of analyzing a symmetric matrix is to compute its eigenvalues. A special property of a symmetric matrix is that the sum of its eigenvalues equals the sum of its diagonal elements. For instance, a symmetric N by N matrix representing pairwise similarities will have N diagonal elements each having a value of 1.0. The sum of the eigenvalues for such a matrix, within numerical precision, is N. Eigenvalues represent roots of an N-degree polynomial represented by the said matrix.

When computed from frames acquired appropriately, derived information from a self-similarity matrix may be used to distinguish visual dynamic processes within a class. As is well-known in the art, the Hurst Parameter can be estimated for a time series of self-similarity measurements. The Hurst Parameter can be used to characterize long-term dependencies. A self-similarity matrix and/or entropic indices can be analyzed to generate numeric evaluations of the represented signal. Many variations on the above choices on how to use self-similarity can be used within the spirits of the invention to produce similar results.

Standard statistical or matrix algebra methods can also be used. The following examples are illustrative only and do not limit the scope of the invention described in the claims.

(a) Largest Eigenvalue of Self-Similarity Matrix

A self-similarity matrix representing a sequence of images containing nearly identical scenes has an eigenvalue nearly equal to sum of its diagonal elements containing similarity match of an image to itself, 1.0 since a self-similarity matrix is a symmetric matrix. A sequence of images can be represented using said eigenvalue of said self-similarity matrix. A plurality of said eigenvalues representing “signatures” resulting from applying a set of perturbations to a system or set of similar systems can be used to rank said signatures with a consistent measurement of the dynamics of the systems under each perturbation.

(b) Periodicity of the Entropic Indices

Applying a self-similarity matrix to a frame sequence or image sequence containing at least 2 whole periods of images representing periodic motion such as that of a beating heart, and acquired with sufficient spatial resolution, produces entropic indices of the signal containing a dominant frequency at or near the periodicity of the imaged periodic motion.

Self-similarity as Motion Estimator

In some embodiments, self-similarity is estimated with overlapping windows (602) and over a moving attention window (605). Specifically, frame geometry is sampled at S_x, and S_y. Defining the top-left as the origin of the sampling window of 2xS_x, and 2xS_y in size, a self-similarity matrix is estimated for each sampling window, as shown in FIG. 6. Sampling windows share 50 percent of their enclosed pixels with their neighboring sampling windows (

1. A method of evaluating a dynamic system, comprising: a. acquiring a plurality of images representative of the dynamic system in two or more dimensions using at least one sensor; b. determining self-similarity among a representative set of images using an unsupervised algorithm defined as being absent a previously known model, wherein the unsupervised algorithm is implemented on at least one data processing device; and c. characterizing the set of images as a statistical function of self-similarity;

thereby evaluating the dynamic system.

2. The method of claim 1, wherein the dimensions include any of time, space, frequency spectrum, temperature, presence or absence of an attribute of the system.

3. The method of claim 1, wherein: the determining step includes determining self-similarity between all of the plurality of images; and the characterizing step includes characterizing the dynamic system as a statistical function of the self-similarities determined with respect to the plurality of images.

4. The method of claim 1, wherein the images are acquired by a method comprising: a. acquiring images at a first acquisition parameterization; b. determining similarity between a selected image and at least one of the other images; c. characterizing the images as a statistical function of self-similarity; and

the acquisition parameterization is adjusted as a function of the self-similarity of the images.

5. A method of evaluating a dynamic system, comprising: a. acquiring a plurality of images representative of the dynamic system in two or more dimensions using at least one sensor; b. determining self-similarity among a representative set of images using an unsupervised algorithm defined as being absent a previously known model, wherein the unsupervised algorithm is implemented on at least one data processing device, wherein determining self-similarity includes estimating a short-term temporal similarity and a long-term temporal similarity; and c. characterizing the set of images as a statistical function of self-similarity, thereby evaluating the dynamic system.

6. The method of claim 5, further comprising combining the long-term and short-term similarities to establish a self-similarity matrix representative of an entire duration of an analysis.

7. The method of claim 6, further comprising processing the self-similarity matrix to model spatiotemporal signals.

8. The method of claim 6, comprising evaluating the self-similarity matrix by analyzing the symmetry of the matrix.

9. The method of claim 6, further comprising analyzing the self-similarity matrix to represent a signal.

10. The method of claim 6, wherein characterizing the set of images includes applying a matrix operation to the self-similarity matrix to characterize the dynamic system.

11. The method of claim 5, further comprising loading images into a frame buffer and using the loaded images for estimating the short-term temporal similarity.

12. The method of claim 11, further comprising using the loaded images for estimating long-term temporal similarity.

13. The method of claim 5, further comprising comparing the characterized set of images with a reference value.