Image analysis – Image segmentation
Reexamination Certificate
2001-03-26
2004-12-14
Couso, Yon (Department: 2625)
Image analysis
Image segmentation
C382S171000
Reexamination Certificate
active
06832002
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method for segmentation of a digital picture consisting of a multiplicity of single picture elements which is in particular suitable for digital picture processing and/or object and pattern recognition.
2. Description of the Prior Art
In most fields of application of digital picture processing and pattern recognition it is necessary to recognize and classify pertinent structures in a picture consisting of a multiplicity of single picture elements. An important step therefore consists in combining pertinent, contiguous picture elements into coherent picture segments. This technique is referred to as segmentation. Through their shape and texture properties the picture segments thereby found offer substantially more information for a subsequent classification than single picture elements, with this information being strongly dependent on the quality of segmentation.
The essential criteria for the segmentation of picture elements are contiguity and so-called homogeneity criteria which determine whether or not a picture segment, following the combination of picture elements, is judged to be homogeneous. A homogeneity criterion determines whether or not combination is performed. In a homogeneity criterion for example specific texture properties or a homogeneity of features can be defined.
One particular difficulty in segmentation of a picture is caused by the texture of picture regions which occurs in very many pictures in most variegated degrees. Characteristically, almost all object types are more or less textured. A like texture is, besides other properties for example seediness or grain, essentially characterized by a higher or lower degree of distribution of features, for example a gray value distribution or color distribution. Such distributions of feature values may be greater or smaller for various objects and may also overlap.
For example in
FIG. 17
a case is represented wherein altogether six picture objects each presenting a differently sized range of gray values ranging on a scale between 0 and 256 are shown, wherein the respective range of gray values of the picture objects represented above partly or entirely overlaps with the one of the picture objects represented below.
This causes considerable difficulties in segmentation as on the one hand, textured picture objects, which in part present very different feature values, are to be segmented entirely, whereas on the other hand segmentation is performed as a general rule on the basis of similarities of features. Where the differences of features within an picture object are too large, segmentation will become problematic owing to similarity of features. At the same time it is generally difficult to separate two contiguous picture objects having overlapping feature distributions.
In many segmentation methods of the prior art the similarity or pertinence of picture elements and picture segments is determined for example by means of so-called one- or more-dimensional threshold techniques, wherein the feature space defined by the features of the picture elements is classified into partial ranges. The homogeneity criterion is satisfied in these known methods whenever the picture elements are contained in a same partial range. Thus for example the 256 gradations of gray in which a digitized picture is frequently present, may be classified into 16 regions each having 16 gray values. If two contiguous picture elements are in a same range of gray values, they are judged to be similar and are therefore segmented. This does, however, often solve the above described difficulties only very insufficiently. Even where certain objects are well described by the classification of the regions, this classification may fail altogether for other picture objects.
Other methods attempt to combine picture segments based on specific predetermined texture features which leads to a texture-based segmentation. This works more or less well for specific textures in particular picture regions, however often worse in other picture regions. These methods at the same time necessitate beforehand knowledge about the picture and its textures, and furthermore do not enable any desired resolutions.
Segmentation methods utilizing watershed transformation employ as the basis for segmentation a representation of the color gradients in the picture, begin segmentation in the most homogeneous picture regions, and successively, i.e. by and by, expand the segments into more heterogeneous picture regions. In this way homogeneous picture regions are well segmentable, uniformly heterogeneous picture regions however with more difficulty. Simultaneous segmentation of homogeneous and heterogeneous picture regions, or of picture regions having different degrees of heterogeneity, can be performed only with great difficulty. In addition the method disregards the original color information.
Techniques performing pixel classification operate along the principle of determining, based on beforehand knowledge, intervals or distributions in the feature space which are known to be characteristic for particular object classes. In this case the examined picture elements are each allocated to a respective class with which they present the highest probability of pertinence in accordance with their vector in the feature space. The homogeneity criterion is in this case defined as pertinence to the same object class. Apart from the fact that much less information for classification is available about single picture elements than about picture segments, a particular difficulty is encountered in processing aerial and satellite pictures owing to the fact that the distribution of the features for particular object types depends very strongly on weather, time of the day and season, as well as light conditions at the time when the picture was taken. Accordingly a suitable preliminary definition of typical distributions for particular object classes in the feature space is very difficult.
From the article J. C. Tilton: “HYBRID SEGMENTATION FOR EARTH REMOTE SENSING DATA ANALYSIS”, IEEE International, vol. 1, pp. 703 to 705, there is known a method for segmentation of a digital picture which uses a combination of region growing and boundary detection. In a first step of this method edge boundaries are detected and in a second step of this method region growing is performed by not allowing to grow regions past edge boundaries defined by the boundary detection. However, this method has disadvantages in that the maximum size of regions to be grown is the size defined by the edge boundaries. Thus, this method fails to provide the possibility to grow regions having similar features past edge boundaries which are in fact no edges of different picture objects but result from textures or the like.
SUMMARY OF THE INVENTION
It is therefore one object of the present invention to provide a method for segmentation of a digital picture which ensures an excellent segmentation or object recognition even in cases where respective objects have overlapping feature ranges or are characterized by feature values which are liable to strongly vary under different conditions.
In accordance with a first aspect of the present invention there is provided a method for segmentation of a digital picture consisting of a multiplicity of single picture elements comprising (a) determining if one of one and several features relating to contiguous picture objects comprising picture elements and picture segments are conforming or not conforming based on a specific homogeneity criterion by means of referencing a predetermined tolerance for each feature as a termination criterion, within which feature values relating to the contiguous picture objects in question may differ; (b) if one of one feature and several features relating to the contiguous picture objects are determined to be conforming then merging the conforming picture objects; and (c) repeating the resulting segmentation until the resulting segmentation converges in a stable or approxim
Baatz Martin
Binnig Gerd
Eschenbacher Peter
Melchinger Andreas
Sogtrop Michael
Blakely & Sokoloff, Taylor & Zafman
Couso Yon
Definiens AG
LandOfFree
Method of iterative segmentation of a digital picture 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 of iterative segmentation of a digital picture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of iterative segmentation of a digital picture will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3327163