Population mixture modeling with an indeterminate number of sub-populations
First Claim
1. A method of fitting a plurality of sub-population functions to digital image data, comprising the steps of:
- defining a plurality of collections and a set of bins, each of said collections having an initial set of functions corresponding to different ones of said bins, said functions each having one or more function parameters;
determining a plurality of fitness values, each of said fitness values defining a difference between a respective one of said collections and the data;
comparing each said fitness value to stopping criteria to determine if said stopping criteria is satisfied;
if, at said comparing step, said stopping criteria is not satisfied, then altering said plurality of collections to provide a next generation of said collections; and
following said altering step, iterating said determining, comparing, and altering steps;
wherein one or more of said altering steps further comprise;
randomly selecting one of said collections of the respective said next generation and one of said bins;
if the randomly selected bin and one of said functions in the randomly selected collection correspond, deleting said corresponding function;
if the randomly selected bin has no corresponding function in the randomly selected collection, adding to the randomly selected collection a new function corresponding to said randomly selected bin, said new function having one or more randomly selected function parameters.
5 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus for determining the best fit of a population mixture model to data. In the digital imaging area, the use of histogram data is employed. A plurality of sub-population functions are defined and then optimized to fit the data. An objective function is employed, which is based upon the parameters of the underlying functions. The number of underlying functions is added to the parameter mix, such that no a priori knowledge of the number of sub-populations is required. In an illustrative embodiment, a genetic algorithm is used to evolve the objective function to an optimal fit of the data. Once an optimal fit is found, through comparison with stopping criteria in a fitness function, the data is segmented according to threshold determined based of classification error in the data.
-
Citations
34 Claims
-
1. A method of fitting a plurality of sub-population functions to digital image data, comprising the steps of:
-
defining a plurality of collections and a set of bins, each of said collections having an initial set of functions corresponding to different ones of said bins, said functions each having one or more function parameters; determining a plurality of fitness values, each of said fitness values defining a difference between a respective one of said collections and the data; comparing each said fitness value to stopping criteria to determine if said stopping criteria is satisfied; if, at said comparing step, said stopping criteria is not satisfied, then altering said plurality of collections to provide a next generation of said collections; and following said altering step, iterating said determining, comparing, and altering steps; wherein one or more of said altering steps further comprise; randomly selecting one of said collections of the respective said next generation and one of said bins; if the randomly selected bin and one of said functions in the randomly selected collection correspond, deleting said corresponding function; if the randomly selected bin has no corresponding function in the randomly selected collection, adding to the randomly selected collection a new function corresponding to said randomly selected bin, said new function having one or more randomly selected function parameters. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 33, 34)
-
-
14. An apparatus for fitting a plurality of sub-population functions to digital image data, comprising:
-
means for defining a plurality of collections and a set of bins, each of said collections having an initial set of functions corresponding to different ones of said bins, said functions each having a plurality of function parameters; means for determining a plurality of fitness values, each of said fitness values defining a difference between a respective one of said collections and the data; means for comparing each said fitness value to stopping criteria to determine if said stopping criteria is satisfied; means for altering said plurality of function parameters to provide a next generation of said collections, if said means for comparing determines that said stopping criteria is not satisfied; and means for iterating said determining, comparing, and altering steps following said altering step; wherein one or more of said iterated altering steps further comprise; randomly selecting one of said collections of the respective said next generation and one of said bins; if the randomly selected bin and one of said functions in the randomly selected collection correspond, deleting said corresponding function; if the randomly selected bin has no corresponding function in the randomly selected collection, adding to the randomly selected collection a new function corresponding to said randomly selected bin, said new function having one or more randomly selected function parameters. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25)
-
-
26. A method of specifying thresholds for segmenting a digital image, comprising the steps of:
-
producing a histogram of the image, the histogram having histogram data, said histogram defining a plurality of bins; defining a plurality of mixture models, each said mixture model being a combination of a plurality of subpopulations, wherein each subpopulation is a function defined according to a plurality of function parameters; defining a generation of chromosomes, each said chromosome being a vector having a plurality of elements, each said element corresponding to a respective one of said bins, each said element having a zero value or a non-zero value, each of said non-zero value elements encoding the function Parameters of a respective one of said sub-populations; for each chromosome in the generation, performing the following steps; determining the fitting error between the mixture model defined by the chromosome and the histogram data; determining a measure of the relative contributions of the individual sub-populations defined by the chromosome; and determining a fitness value based on said fitting error and said measure of relative contributions; comparing said fitness values to stopping criteria; altering said chromosomes of said generation to define a next generation of chromosomes, if none of said fitness values satisfies said stopping criteria; and repeating said performing, comparing, and altering steps on said next generation of chromosomes, if none of said fitness values satisfies said stopping criteria, wherein one or more of said repeated altering steps further comprise; randomly selecting one or more of said elements; and replacing each of the randomly selected non-zero value elements with a zero value element and each of the randomly selected zero value elements with a non-zero value element encoding randomly selected function parameters of a new sub-population; and specifying at least a first threshold value delineating said sub-populations in a respective said mixture model, if at least one of said fitness values satisfies said stopping criteria. - View Dependent Claims (27, 28, 29, 30, 31)
-
-
32. An apparatus for specifying thresholds for segmenting a digital image, comprising:
-
means for producing a histogram of the image, the histogram having histogram data, said histogram defining a plurality of bins; means for defining a plurality of mixture models, each said mixture model being a combination of a plurality of subpopulations, wherein each subpopulation is a function defined according to a plurality of function parameters; means for defining a generation of chromosomes, each said chromosome being a vector having a plurality of elements, each said element corresponding to a respective one of said bins, each said element having a zero value or a non-zero value, each of said non-zero value elements encoding the function parameters of a respective one of said sub-populations; for each chromosome in the generation, means for performing the following steps; determining the fitting error between the mixture model defined by the chromosome and the histogram data; determining a measure of the relative contributions of the individual sub-populations defined by the chromosome; and determining a fitness value based on said fitting error and said measure of relative contributions; means for comparing said fitness values to stopping criteria; means for altering said chromosomes of said generation to define a next generation of chromosomes, if none of said fitness values satisfies said stopping criteria; and means for repeating said performing, comparing, and altering steps on said next generation of chromosomes, if none of said fitness values satisfies said stopping criteria, wherein one or more of said repeated altering steps further comprise; randomly selecting one or more of said elements; and replacing each of the randomly selected non-zero value elements with a zero value element and each of the randomly selected zero value elements with a non-zero value element encoding randomly selected function parameters of a new sub-population; and means for specifying at least a first threshold value delineating said sub-populations in a respective said mixture model, if at least one of said fitness values satisfies said stopping criteria.
-
Specification