Method and apparatus for biomathematical pattern recognition

• US 6,466,923 B1
• Filed: 04/29/1998
• Issued: 10/15/2002
• Est. Priority Date: 05/12/1997
• Status: Expired due to Fees

• Current Assignee: Chroma Graphics, Inc.
• Original Assignee: Chroma Graphics, Inc.
• Inventors: Young, Fredric S.
• Primary Examiner(s): Powell, Mark
• Assistant Examiner(s): STARKS, WILBERT L
• Application Number:
  US09/070,110
• Time in Patent Office: 1,630 Days
• Field of Search: 706/13, 706/20, 382/103, 382/194
• US Class Current: 706/13
• CPC Class Codes: G06V 10/44 Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components
• CPC Class Codes: G16B 20/00 ICT specially adapted for functional genomics or proteomics, e.g. genotype-phenotype associations
• CPC Class Codes: G16B 25/00 ICT specially adapted for hybridisation; ICT specially adapted for gene or protein expression
• CPC Class Codes: G16B 25/20 Polymerase chain reaction [PCR]; Primer or probe design; Probe optimisation
• CPC Class Codes: G16B 40/00 ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding

Abstract

In an analysis of a set of discrete multidimensional data which can be represented in an array with a topology, where the array that can be mapped to an image space of discrete elements, such as digitized image data, seismic data and audio data, genotype/phenotype classifications are imposed on the topology, and then molecular biological-like processes (annealing, fragmentation, chromatographic separation, fingerprinting, footprinting and filtering) are imposed upon that topology to perceive classifiable regions such as edges. More specifically, an image feature probe constructed of strings of contiguous image fragments of the class of N-grams called linear N-grams, anneals genotypes of topological features by complementary biological-like techniques in the same manner that complex biological systems are analyzed by genetic mapping, sequencing and cloning techniques. For example, molecular biological probes anneal with molecular biological genotypes and then are used to classify those genotypes. More specifically, an image feature probe constructed of strings of contiguous pixels, of the class of N-grams called linear N-grams, mates genotypes of topological features by complementary biological-like techniques in the same manner that molecular biological probes mate with molecular biological genotypes. The topological genotypes are by definition orthogonal elements to edges. Techniques are disclosed for defining the feature probes.

Claims

1. In a computing machine, a method for mapping a dataset representative of physical features to a specific pattern representative of physical objects wherein said dataset can be mapped intermediately to a spatially-defined image, said method comprising:

selecting a basis for generating at least one probe set of data from a training dataset;

creating at least one probe set composed of probes of partitionable, spatially-definable data from said training dataset on said computing machine for mating with patterns in known spatially-definable images to be recognized, each said probe of said probe set having a complementary value at selected image fragment positions among a preselected fraction of image fragments in key features in the spatially-defined image;

inputting an unknown dataset to said computing machine;

separating said unknown dataset into an ordering for decomposition;

segmenting said unknown dataset into partitions corresponding to segmentation on said training dataset;

applying said at least one probe set to said unknown dataset to identify with said patterns; and

outputting said patterns associated with said selected image fragment positions of said unknown dataset specifying representations of physical objects associated with said patterns.

2. In a computing machine, a method for mapping a dataset representative of physical features to a specific pattern representative of physical objects wherein said dataset can be mapped intermediately to a spatially-defined image, said method comprising:

creating at least one probe composed of spatially-definable data on said computing machine for mating with patterns in known spatially-definable images to be recognized, each said probe having a complementary value at selected image fragment positions among a preselected fraction of image fragments in key features in the spatially-defined image;

inputting said dataset to said computing machine;

applying said at least one probe to said input dataset to identify with said patterns; and

outputting said patterns associated with said selected image fragment positions of said dataset specifying representations of physical objects associated with said patterns, wherein said probe creating step comprises;

selecting a basis for generating a probe set of data preliminary to establishing the probe set;

selecting a level of graining or quantization resolution per point, and a level of pixel resolution of a point, across the entire dataset;

separating the dataset into an ordering for decomposition such that the dataset can be analyzed sequentially in a one-dimensional array;

selecting conditions for fragmentation of the one-dimensional string;

segmenting said one-dimensional string according to partition type; and

preparing a histogram of fragments by said partitions.

3. The method according to claim 2 further including the steps of:

determining the number of different types in each length partition;

creating a combinatoric histogram within length categories with the number of copies of each sequence type in each partition; and

converting said combinatoric histogram information into a type code that lists detailed histogram and sequence combinatorics of each fragment class into order to yield a type-code probe.

4. The method according to claim 3 further including the steps of:

picking a representative set of textures that have a range of variations;

selecting the level of z-axis quantization and pixel resolution;

decomposing the dataset along rows, columns and axes to set orientation for further decomposition;

selecting conditions for fragmentation into fragments;

sorting said fragments by at least length;

sorting fragments of equal length by sequence;

preparing a histogram of length and sequence types;

creating a type-code probe for each individual texture; and

constructing a type-code for each pattern.

5. The method according to claim 3 further including the steps of:

normalizing the type-codes;

hybridizing to the type-codes for each pattern investigated using a library of type-codes;

testing on a library type-code for a structural match with a probe;

if a structural match is not found, repeating the testing step with a next probe;

otherwise, if a match is found, normalizing size to fit with the scale of the library type-code; and

hybridizing a corresponding sequential library type-code to a normalized target image sequence type-code in complementary form to determine if there is a more precise match.

6. The method according to claim 5 further including the steps of preparing a structure type-code for said library of type-codes comprising:

grouping image fragments according to common repetition frequency to obtain groups;

ordering said groups from most populous to least populous;

designating the group having the highest population as the normalized group of value of 1;

assigning all other groups a fractional value of 1 based upon relative population compared with said normalized group; and

establishing structural type-code by number of fragments, length of the fragments, and normalized population size.

7. The method according to claim 6 for probing a target with a type-code from said type-code library comprising:

inputting an unknown target image;

setting up type-codes of the unknown target image, said target type-codes being of a form that is complementary to probe type-codes stored in the image library;

hybridizing the probe type-codes of the patterns in the library to the complementary target type-codes of the target image;

reporting an image identification match upon finding a meeting of a threshold of preestablished closeness criteria and number criteria between probe type-codes and target type-codes.

8. The method according to claim 7 wherein said probe type-codes of said image library are a collection of structural type-codes and of sequence type-codes.

9. The method according to claim 2 further including the steps of:

cleaving the source dataset at selected pixel locations to yield end locations on each fragment;

labeling each end location with tags with a value defining local cleavage condition;

partitioning the fragments by length of the index for the fragment, while excluding the end labels;

classifying the lengths by cutting condition;

partitioning the fragments by fragment class;

constructing a histogram based on additional data, including length, sequence, presence of end labels, shape and type of end labels, in order to obtain a dataset for feature classification and identification.

10. The method according to claim 2 further including the steps of:

randomly fragmenting a decomposed dataset into fragments formed of groups of elements;

computing for selected lengths of fragments a sequence histogram at each fragmentation level;

examining peaks in histograms for the fragments having those sequences of the most frequent occurrence to identify the natural unit sizes for fragments of a known sequence;

selecting most abundant natural-length sequences for use as a model for a recognition site sequence and as a tool for building a preprobe; and

building the preprobe as a complement to each sequence so selected.

11. In a computing machine, a method for matching unknown information patterns representative of physical features organized into a set of discrete multidimensional data which can be represented in an array with a topology, wherein the array can be mapped intermediately to a spatially-defined image space of discrete elements which are definable along axes with boundaries, said method comprising:

creating at least one probe set composed of probes of partionable, spatially-defined data which is complementary at a genotype level with patterns to be recognized in the image space, each said probe having a complementary value at selected image fragment positions of at least the first order among a preselected fraction of image fragments in key features in the image space; and

employing said probe set to identify and locate said patterns within the image space wherein said employing step comprises inputting said n-dimensional data to said computing machine;

applying said at least one probe set to said input n-dimensional data to identify with said patterns; and

outputting said patterns associated with said selected image fragment positions in order to specify physical objects associated with said patterns.

12. The method according to claim 11 further including:

building a collection of different probes for perceiving different patterns within the image.

13. The method according to claim 11 further comprising:

building a collection of said probes for use together; and

employing said group of probes to identify features at a phenotype level.

14. In a computer system, a method operative on information patterns representative of physical features in a set of discrete multidimensional data which can be represented in an array with a topology, wherein the array that can be mapped to spatially-defined image space of discrete elements, for determining similarity between two complementary sequences, said method comprising the steps of:

creating a probe which is complementary at a genotype level with patterns to be recognized in the image space, said probe having a complementary value at selected image fragment positions of at least the first order among a preselected fraction of image fragments in key features in the image space;

employing said probe to identify and locate said patterns within the image space, said probe-employing step comprising the steps of;

applying a set of unweighted probes formed of datasets to a target training image to determine as a presumably rough cut any matches between individual probes and the target image to obtain strings;

sorting the strings which are rough probe matches by probe index, in order to group the strings of rough matches with selected probes;

training probe weights by iteratively applying, for each probe index, the probe with various weights to the group of rough matches; and

optimizing weights to yield a minimal set of probes which selectively and completely identify targets from which the probes are made.

15. An apparatus for matching information patterns in a set of discrete multidimensional data, which can be represented in an array, with a physical topology, where the array that can be intermediately mapped to a spatially-defined image in an image space of discrete elements which are definable along axes with boundaries, said apparatus comprising:

means for creating at least one probe set composed of probes of partitionable, spatially-definable data from a training dataset, each said probe being complementary at a genotype level with known spatially-definable patterns to be recognized in the image space, each said probe in said probe set having a complementary value at selected image fragment positions among a preselected fraction of image fragments in key features in the spatially-defined image in the image space;

means coupled to said probe-creating means for storing said probe set; and

means for employing said probe set to identify and locate said patterns within the image space, wherein said employing means comprises

dataset input means coupled to said computing machine for inputting an unknown dataset;

segmentation means for segmenting said unknown dataset into partitions corresponding to segmentation in said training dataset;

probe application means for probing said unknown dataset to identify with said patterns; and

pattern output means for outputting patterns associated with said selected image fragment positions of said dataset and specifying representations of physical objects associated with said patterns.

16. An apparatus for matching information patterns representative of physical objects in a spatially-defined image, said apparatus comprising:

a probe creator means for making at least one probe set of probes for patterns in an unknown image to be recognized from patterns extracted from a model image, each said probe having a complementary value at selected pixel positions among a preselected fraction of image pixels in key features in the model image;

a storage mechanism coupled to said probe-creator means for storing said probe set; and

a probe applicator and detector employing said probe set to identify and locate said patterns within the image under test; and

output means for outputting identity and location of said patterns.