Fractal production of darwinian objects

• US 6,738,513 B1
• Filed: 10/30/2000
• Issued: 05/18/2004
• Est. Priority Date: 10/24/1997
• Status: Expired due to Term

• Current Assignee: Definiens AG (Astrazeneca PLC)
• Original Assignee: Definiens AG (Astrazeneca PLC)
• Inventors: Baatz, Martin, Eschenbacher, Peter, Voss, Richard, Binnig, Gerd, Schmidt, Günter
• Primary Examiner(s): Ahmed, Samir
• Assistant Examiner(s): LE, BRIAN Q
• Application Number:
  US09/530,174
• Time in Patent Office: 1,296 Days
• Field of Search: 382/224-228, 382/181, 382/190, 706/13, 706/20
• US Class Current: 382/181
• CPC Class Codes: G06T 11/00 2D [Two Dimensional] image generation
• CPC Class Codes: G06V 10/42 Global feature extraction by analysis of the whole pattern, e.g. using frequency domain transformations or autocorrelation

Abstract

A method for fractal-darwinian object generation consists of the steps of: preparing a fractal object library including predetermined objects and associated rules of property and context, forming objects and comparing the formed objects with the objects in the fractal object library. By using the property rules, a local classification likelihood is allocated to each formed object. Thereupon, by using the context rules for each object, a respective fractal classification likelihood is formed. For optimisation of the fractal classification likelihood, alteration rules are applied to the objects. The above method is carried out iteratively, whereby a process of gradual optimisation takes place.

Claims

1. A computer implemented method for multi-scale darwinian object generation from a structure to be examined, comprising the steps of:

a) preparing a hierarchical object library including predetermined objects and associated rules of property, context and alteration;

b) acquiring the structure to be examined;

c) forming basic objects in the structure to be examined, wherein the basic objects are located in a hierarchical object structure including subordinate and superordinate objects;

d) comparing the basic objects with the objects of the hierarchical object library, wherein the respective formed basic object is evaluated to be unknown if no corresponding object having the corresponding property rules exists in the hierarchical object library, and at least one local classification likelihood is allocated to the basic object having said property rule if at least one corresponding object exists in said hierarchical object library;

e) applying said context rules to the respective objects in order to form and calculate respective multi-scale classification likelihoods;

f) applying said alteration rules to the respective objects in order to optimise the multi-scale classification likelihoods;

g) iterative execution of steps e) and f) for stepwise improvement of the multi-scale classification likelihoods, wherein

treatment and description of the objects is similar for subordinate and superordinate objects.

2. The method according to claim 1, wherein said hierarchical object library includes priority rules according to which the temporal order and/or the frequency for said iterative execution in accordance with step g) of all objects of said hierarchical object structure is determined.

3. The method according to claim 1, wherein the step for forming basic objects consists of an iterative segmentation of basic elements while taking into account homogeneity criteria.

4. The method according to claim 1, wherein the hierarchical object structure is generated and thus leads to a hierarchical abstraction of any predetermined set of data by combining smaller objects into larger ones if the application of a homogeneity criterion results in a value situated below a threshold.

5. The method according to claim 1, wherein alteration rules from said hierarchical object library are already used in step c).

6. The method according to claim 5, wherein in image recognition methods, isotropic alteration rules are used for area-type objects and anisotropic alteration rules are used for linear objects in forming the basic objects.

7. The method according to claim 2, wherein a hierarchical object structure of the basic objects is optimised through foundations in order to generate superordinate objects, disintegration in order to generate subordinate objects, fusion in order to generate larger objects, dissolution in order to generate smaller objects, subordination in order to gather subordinate objects, exclusion from a group in order to expel subordinate objects, and/or regrouping in order to exchange subordinate objects in such a way that the weighted sum of the variances of the classification likelihoods of all hierarchical objects becomes minimum, wherein each object is weighted by the number of its subordinate objects.

8. The method according to claim 2, wherein, as a homogeneity criterion, the difference of the heterogeneity h weighted by the size of an object newly created by fusion or foundation, and the sum of the heterogeneities of the original objects (h₁ and h₂, respectively) weighted by the respective sizes (n₁ and n₂, respectively) is employed, which results from

9. The method according to claim 2, wherein of all pairs of objects which may potentially be considered for a fusion or foundation, always those are combined first which have the smallest difference of weighted heterogeneity Δ

h_weight introduced by the fusion or foundation.

10. The method according to claim 2, wherein objects are fused in the combination if the difference of the weighted heterogeneity divided by the overall size Δ

h_weight./.(n₁+n₂) is situated below a predetermined threshold, or a new superordinate object is founded while maintaining the smaller objects, if this difference is situated above said threshold.

11. The method according to claim 1, wherein a subordinate object potentially exchangeable between two objects will actually be relocated whenever the weighted heterogeneity of the two objects will be reduced by this exchange in accordance with the equation

12. The method according to claim 1, wherein the unknown object is added to said hierarchical object library with the associated rules of properties, context and/or alteration.

13. The method according to claim 1, wherein the property rules determine the properties of a particular object.

14. The method according to claim 1, wherein the context rules consist of internal and external context rules.

15. The method according to claim 14, wherein the internal context rules determine a relation between objects not having a direct hierarchical relation among each other.

16. The method according to claim 14, wherein the external context rules determine a relation between the subordinate and superordinate objects or of objects in hierarchical object structures established in parallel.

17. The method according to claim 1, wherein the objects are altered in accordance with the alteration rules set down in said hierarchical object library.

18. The method according to claim 17, wherein the alteration rules additionally include optimisation rules.

19. The method according to claim 18, wherein optimisation in the case of image or pattern recognition corresponds to maximum matching of the multi-scale classification likelihood of the objects with the object library.

20. The method according to claim 18, wherein evolutionary methods are employed for optimisation.

21. The method according to claim 20, wherein several hierarchical object structures which develop in accordance with conventional genetic algorithms exist in parallel.

22. The method according to claim 20, wherein either the sum of all multi-scale weighted classification likelihoods of the overall object or only the multi-scale classification likelihood of the single objects is optimised.

23. The method according to claim 22, wherein weighting of the multi-scale classification likelihoods is carried out either by the number of the subordinate objects or by the total number of the smallest objects, for example pixels.

24. The method according to claim 18, wherein an aspired condition is optimised which relates to the overall object or the partial regions thereof, or is stored in the library in an object-specific manner.

25. The method according to claim 17, wherein several image planes exist which consist either of geometrical, visible or concealed functional data of image segments.

26. The method according to claim 1, wherein the iterative execution of the method steps is terminated when the multi-scale classification likelihood for the overall object has exceeded a particular threshold.

27. The method according to claim 1, wherein the iterative execution of the method steps is terminated when a substantially stable overall object generation has been achieved.

28. The method according to claim 1, wherein the objects are n-dimensional.

29. The method according to claim 28, wherein the n-dimensional objects represent two-dimensional images containing a temporal structure.