Data processing: artificial intelligence – Machine learning – Genetic algorithm and genetic programming system
Reexamination Certificate
1998-04-29
2002-10-15
Powell, Mark (Department: 2762)
Data processing: artificial intelligence
Machine learning
Genetic algorithm and genetic programming system
C706S020000, C382S103000, C382S194000
Reexamination Certificate
active
06466923
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to pattern recognition and more particularly this invention relates to applications of mathematical techniques based on molecular genetics.
It has been observed that certain genetic processes can be described and analyzed mathematically, particularly by nonlinear mathematics. It has been observed that there are underlying similarities between digital information and molecular genetics. An example is the discovery that actual molecular biological reactions can be used to solve mathematical problems, such as the “traveling salesman” routing problem. (Dr. Leonard Adleman, a computer scientist at U.S.C., created an artificial DNA string for each node in a space and allowed the DNA strings to combine to define a singular path. L. Adleman, “Molecular Computation of Solutions to Combinatorial Problems.”
Science
Magazine. Vol. 266, Nov. 11, 1994.)
U.S. Patents and references were identified in an investigation of the prior art and are cited to the U.S. Patent Office in a separate Invention Disclosure Statement. Nothing showed the use of biomathematical techniques for texture or pattern recognition.
Of the references uncovered, U.S. Pat. No. 5,375,195 to Johnston shows the use of “genetic algorithms” to effect facial recognition, drawing on the techniques of mutation, phenotyping, gene, genotyping and crossover with mathematical processes. The use of the term “genetic algorithm” therein and elsewhere in the literature refers to recombining and selecting functions which mimic the processes occurring in natural genetic reproduction in living organisms.
The only known precedent for the use of the term “genetic algorithm” beyond the conventional use as in Johnston is in Adleman's work in solution of the Hamiltonian path problem. The equivalent term for Adleman's process is “molecular computation.” Adleman's work has spawned a new field of research investigation, which so far has lead to computational tools and elements, which is reported in the research science literature. An example is the proceedings of the Discrete Mathematics and Computer Science Workshop held Apr. 4, 1995 at Princeton University.
A 1981 Ph.D. dissertation entitled “Computational Models for Texture Analysis and Texture Synthesis” by David Garber at the University of Southern California discussed the concept of the use of N-gram statistics in texture analysis and generation. His analysis used a technique involving a maximum of N equal to four pixels in a row to determine fourth order statistical analysis to extract parameter sets in texture generation. He was able to correlate textures of different orders based on statistical analysis of pixel groupings. While never treated as image fragments, the present inventor has recognized a relationship between the concept of N-grams and the pixel groupings of contiguous pixels used in the present invention to create probes.
What is needed is an improved method to solve mathematically-challenging pattern problems, such as pattern recognition problems, including “edge” detection within a dataset (rather “edge” detection on a physical structure) wherein the dataset has an unarticulated but definable topology. The following invention exploits similarities between the genetic pattern recognition problems in the realm of image topology, where the topology is a function of relationships between pixels of an image.
SUMMARY OF THE INVENTION
According to the invention, 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. These topological genotypes are by definition orthogonal elements to edges.
The image fragments may be resolution independent. However, the image fragments can likewise be pixel strings where the pixels delimit the resolution of the image. Nevertheless, the probe derived from the image fragment can be constructed with an informational vector that is not limited by the resolution of the pixel representation. It is merely necessary that any informational vector, such as shape defined as a gradient in an analysis space, be compatible with the analysis space.
In the present invention, the process of applying genetic analysis techniques is analogized in the realm of digital computing, including the mimicking of functions carried out by molecular biologists in genetic analysis for biotechnology. Some of these techniques may be based on natural processes carried out by extra-chromosomal genetic elements. Some techniques have also been engineered by researchers. The genetic analysis techniques of the present invention are used for the image processing needed in pattern recognition and in particular texture recognition. Various methods for constructing probes are described.
The provisional application described a process involving a probe constructed from image fragment data to yield a type code. The present description further expounds on that description by recognizing that two types of information can be derived from a data array (such as pixel image data) to form a probe to yield a type code. The sequence that makes up a probe can be a sequence of entities (pixels) in an array and a sequence of differences between entities of the array.
The invention will be better understood upon reference to the following description in connection with the accompanying drawings.
REFERENCES:
patent: 4697242 (1987-09-01), Holland et al.
patent: 4821333 (1989-04-01), Gillies
patent: 5222192 (1993-06-01), Shaefer
patent: 5375195 (1994-12-01), Johnston
patent: 5400436 (1995-03-01), Nara et al.
patent: 5448668 (1995-09-01), Perelson et al.
patent: 5479523 (1995-12-01), Gaborski et al.
patent: 5581657 (1996-12-01), Lyon
patent: 5623513 (1997-04-01), Chow et al.
patent: 5700637 (1997-12-01), Southern
patent: 5768318 (1998-06-01), Mestdagh
patent: 5787113 (1998-07-01), Chow et al.
patent: 5830645 (1998-11-01), Pinkel et al.
patent: 5835536 (1998-11-01), May et al.
patent: 5845049 (1998-12-01), Wu
patent: 5853979 (1998-12-01), Green et al.
patent: 5864630 (1999-01-01), Cosatto et al.
patent: 5864633 (1999-01-01), Opsal et al.
patent: 6021220 (2000-02-01), Anderholm
Lank, E.; Blostein, D., N-grams: a well-structured knowledge representation for recognition of graphical documents,Document Analysis and Recognition, 1997., Proceedings of the Fourth International Conference on, vol.: 2., 1997, pp.: 801-804 vol. 2, Jan. 1997.
Allen Kenneth R.
Chroma Graphics, Inc.
Powell Mark
Starks Wilbert
Townsend and Townsend / and Crew LLP
LandOfFree
Method and apparatus for biomathematical pattern recognition does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for biomathematical pattern recognition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for biomathematical pattern recognition will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2979079