Population mixture modeling with an indeterminate number of sub-populations

• US 7,103,219 B2
• Filed: 04/12/2001
• Issued: 09/05/2006
• Est. Priority Date: 04/12/2001
• Status: Expired due to Fees

• Current Assignee: Monument Peak Ventures, LLC (Dominion Harbor Enterprises, LLC)
• Original Assignee: Eastman Kodak Company
• Inventors: Cahill, Nathan D.
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): TUCKER, WESLEY J
• Application Number:
  US09/833,377
• Publication Number:
  US 20020196975A1
• Time in Patent Office: 1,972 Days
• Field of Search: 382/168, 382170-173
• US Class Current: 382/171
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/143 involving probabilistic approaches, e.g. Markov random field [MRF] modelling

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.

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.

2. The method of claim 1 wherein said collections are each defined as a vector representation of said plurality of function parameters.

3. The method of claim 1 further comprising the steps of specifying at least a first threshold value delineating said plurality of functions of each of said collections.

4. The method of claim 3 wherein said at least a first threshold value is calculated based upon the likelihood of misclassification of data.

5. The method of claim 3 further comprising the step of segmenting the data according to said at least a first threshold value.

6. The method of claim 3 wherein said collections are each defined as a vector representation of said plurality of function parameters.

7. The method of claim 2 wherein said altering step is accomplished by evolving said plurality of collections according to a genetic, wherein said genetic algorithm includes a mutation operator comprising said randomly selecting, deleting, and adding steps.

8. The method of claim 7 wherein said evolving includes crossover followed by said mutation operator.

9. The method of claim 1 wherein said plurality of functions are normal distributions, and said plurality of functions parameters include the mean and standard deviations of said normal distributions.

10. The method of claim 1 wherein said comparing step includes the utilization of a statistical f-test to evaluate the relative contribution of each of said plurality of functions in comparison of said fitting error and the data.

11. The method of claim 1 wherein the data is organized as a histogram.

12. The method of claim 1 wherein said stopping criteria are defined by a fitness function.

13. The method of claim 12 wherein said fitness function is optimized to minimize the magnitude of the fit error between each of said collections and the data.

33. The method of claim 1 wherein said altering further comprises randomly applying a genetic crossover operator to provide one or more pair of offspring collections, said deleting and adding being limited to said offspring collections.

34. The method of claim 33 wherein said crossover operator is a single-point genetic crossover operator.

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.

15. The apparatus of claim 14 wherein said collections are each defined as a vector representation of said plurality of function parameters.

16. The apparatus of claim 14 further comprising means for specifying at least a first threshold value delineating said plurality of functions.

17. The apparatus of claim 16 wherein said at least a first threshold value is calculated based upon the likelihood of misclassification of data.

18. The apparatus of claim 16 further comprising means for segmenting the data according to said at least a first threshold value.

19. The apparatus of claim 15 wherein said means for altering operation is accomplished by evolving said plurality of collections according to a genetic algorithm;

wherein said genetic algorithm includes a mutation operator, said mutation operator comprising said randomly selecting, deleting, and adding steps.

20. The apparatus of claim 19 wherein said genetic algorithm includes crossover followed by said mutation operator.

21. The apparatus of claim 14 wherein said plurality of functions are normal distributions, and said plurality of functions parameters include the mean and standard deviations of said normal distributions.

22. The apparatus of claim 14 wherein said means for comparing includes the utilization of a statistical f-test to evaluate the relative contribution of each of said plurality of functions parison of said fitting error and the data.

23. The apparatus of claim 14 wherein the data is organized as a histogram.

24. The apparatus of claim 14 wherein said stopping criteria are defined by a fitness function.

25. The apparatus of claim 24 wherein said fitness function is optimized to minimize the magnitude of the fit error between said each of said collections and the data.

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.

27. The method of claim 26 wherein said at least a first threshold value is calculated based upon the likelihood of misclassification of said histogram data.

28. The method of claim 26 wherein said plurality of functions are normal distributions, and said plurality of functions parameters include the mean and standard deviations of said normal distributions.

29. The method of claim 26 wherein said comparing step includes the utilization of a statistical f-test to evaluate the relative contribution of each of said plurality of functions in comparison of said fitting error and the data.

30. The method of claim 26 wherein said stopping criteria are defined by a fitness function.

31. The method of claim 30 wherein said fitness function is optimized to minimize the magnitude of the fit error between said mixture model and the data.

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.