Image segmentation method

p0001The invention relates to a method for segmentation of images of an image signal, within an image, a decomposition of the image is carried out in regions where adjacent pixels are combined.

p0002Such methods for image segmentation are used for a so-called object-oriented coding. In contrast to the employed for example in the MPEG2 coding geometrical division of the picture and the subsequent coding of the individual geometrical elements is attempted in the object-oriented coding to make a classification of the image based on the image content so that in this image reproduced objects. This has the advantage that occurring between blocks transition effects not interfere appear, since they coincide with the object boundaries.

p0003A method for segmentation of an object-oriented coding, for example, from "Region-based video coding using mathematical morphology," Philippe Salembier, Luis Torres, Fernand Meyer, Chuang Gu, Proceedings of the IEEE, Vol. 83, No. 6, pp 843-857, June 1995 known. In this known method, an image as a function of the brightness values ​​of the image content is segmented.

p0004From "Segmented coding of digital image sequences" IEEE Proceedings I. Solid Stae & Electron Devices, Institution of Electrical Engineers, Stevenage, GB, ISSN 0956-3776, Vol. 139, No. 2, Part1, 212-218, 01- 04-1992, a segmented coding of digital image sequences is known in the region forming the basis of Y, U and V values ​​of the images is performed.

p0005It is an object of the invention to provide a method for image segmentation in which a higher data compression on the one hand and to minimize the visual perceptibility of the segment by encoding and decoding the data is visible.

p0006This object is achieved by the features of claim 1.

p0007The invention is based on the insight that for the object-oriented coding and thus for this preliminary segmentation of the image even greater data reduction than in the known processes in particular can be achieved by that for the region Education mainly the Farbartwerte the pixels are used. This is possible because the human eye reacts to color stimuli much less sensitive than to brightness data. Therefore, it can be gone so far, per region provide only a chrominance value for all pixels belonging to the region. There are contracted to those contiguous adjacent pixels respectively to a region having similar Farbartwerte within predeterminable limits. It is thus for all pixels of a region only one color value set, which is possible because of the aforementioned relationships.

p0008By doing so, the eye is successfully deceived and there may be a reduction by a factor of 300 to 600 can be achieved for the color information. It should be noted that there is no slurring of color edges or the like, since the edges between transitions of different colors for borders between different regions form and are thus defined exactly. Only within fields similar color subtle color shades are suppressed. Thus the eye anyway insensitive.

p0009Gege quake If the Helliglceitswerte of pixels for forming the regions can be used in addition to the Farbartwerten, they should, however, be weighted weaker than their chromaticity values ​​to obtain the advantages mentioned above.

p0010The formation of regions with common chrominance value of all the pixels of a region is carried out in two stages in such a way that in a first stage intermediate regions are formed, they are generated both the chrominance as well as luminance values ​​of the pixels are used, and that in a second stage of the intermediate regions, the regions are formed in such a way that the intermediate regions are grouped into regions, intermediate regions are combined with similar chrominance values ​​to a common area with a common chrominance value.

p0011In this two-stage approach is accomplished as a result that the region formation is based on the chrominance values ​​of the pixels.

p0012It is carried out in a first stage, for example, a region formation in a conventional manner, as they are generated, both the chrominance as well as luminance values ​​of the pixels are used. The result is thus a segmentation that is based on two values. These intermediate regions are exclusively relative combined their chromaticity values ​​in that intermediate regions having similar chrominance values ​​within predeterminable limit, be combined to form a common region. This common region then has a chromaticity value for all pixels of this region.

p0013This two-step procedure has the advantage that in the first stage, the region formation can more securely grasp the object boundaries, because there also the brightness values ​​are used with. then the intermediate regions formed in this way are summarized again for the formation of the regions, so that the desired effect of reducing the number of regions, and thus the amount of data is achieved in the end.

p0014The region assigned chrominance may advantageously, as is provided according to an embodiment of the invention, correspond to the average of the original Farbartwerte the region awarded pixels. It is thus achieved the lowest possible in the mean deviation of Farbartwertes the region of the original Farbartwerten of their belonging pixels.

p0015For the formation of regions in two stages is provided according to a further embodiment of the invention that in the first stage for successive images, a motion estimation of the intermediate regions in an image I_n and the subsequent image I_{n + 1} is made that based on the determined for each intermediate region by means of the motion estimation motion vectors the new position of the intermediate region in the image I_{n + 1} it is determined that following an adjustment of belonging to each displaced intermediate region pixels of the image I_{n + 1} is made that is not covered by these adapted intermediate regions pixels of the image I_{n + 1} one of these intermediate regions or newly formed intermediate regions are added to it and that, subsequently, in the second stage, the intermediate regions are grouped into regions.

p0016The intermediate regions initially formed in the first stage must not in principle be re-generated in each image. Since the image content of successive images are generally very similar (except for camera switch, scene changes or the like) is possible due to the motion estimation in a subsequent image to locate a region again, even if they should have changed their position in the image. Through this retrieval of the region by means of motion estimation it must not be raised, but their data can be transferred from the previous image. A reduction of the coding complexity of the computational effort and thus the computation time is achieved. The intermediate regions tracked in this way in successive images are combined in the manner described above in each case to regions, intermediate regions are merged with similar chrominance values ​​to a common region with only one chroma value.

p0017For this two-stage approach with the use of motion estimation in the pursuit of the intermediate regions is provided for a further embodiment of the invention that for successive images in an image I_{n + 1} which in the previous image I_n to an associated region combined intermediate regions again are visited, where between the images I_n and I_{n + 1} moving between regions are found using the motion information again that a merger between these regions is attempted to the same assigned region and that a merger with other or new regions will be made for those intermediate regions for which this is not possible.

p0018By tracking the intermediate regions in consecutive frames by the motion estimation intermediate merged regions are retrieved in a subsequent image in general to a region. There is therefore also in the merging of intermediate regions to the regions the opportunity again to merge in successive images the same, possibly moving in the image, between regions back to the common region. This also occurs for this processing step to the advantage that the intermediate regions can be retrieved and the merging of these can be made to the region in the same manner as in the previous image. So that no recalculation must also take place here. Those regions for which it does not, for example, because the intermediate regions are not in the picture content available or new intermediate regions emerge shall entail a merger with other regions or there is one or more new regions formed, in which then the remaining intermediate regions can be merged.

p0019According to a further embodiment of the invention it is provided that the coding of the shape of the regions is made by means of a Kettenkodes, in which the position of an output pixel of the edge of a region is completely encoded and in which the positions of the remaining pixels of the. Edge of the region are successively starting encoding of the output pixel in a way that is only code that indicates whether the pixel in question is located to the left, to the right, 'above or below the previously coded pixel.

p0020In addition to the coding of the pixels with respect to their brightness and their color type is a coding of the shape of the segments required. A data-saving method of coding the shape of the regions is possible by means of a Kettenkodes. Here is the complete position information of that pixel is encoded by only one output pixel. This output pixel is on the edge of a region. Starting from this output pixel of the edge of the region is then carried out a relative coding of the neighbors for each further this adjacent pixel. The output pixel adjacent pixel is encoded only on whether it above, below, is to the left or right of the output pixel. This process is then repeated for each additional adjacent pixel of the edge until the entire screen surface of the edge of the region are coded in this way. apart from the output pixel in this way satisfies a 2-bit coding for each additional pixel on the edge of a region.

p0021The invention will be described with reference to the drawing. Show it:<ul><li>Fig. 1 is a schematic block diagram for the two-stage segmentation, </li><li>FIG. 2 is an image example of the two-step encoding,</li><li>Fig. 3 shows an example of FIG. 2, in FIG. 3 is a follow-up image of the image shown in FIG. 2 is shown with successful movement, and</li><li>Fig. 4 is a schematic representation corresponding to FIG. 1, in addition, a motion estimation for forming the intermediate regions and a follow up of the regions is carried out in successive images.</li></ul>

p0022Fig. 1 shows a schematic representation of the procedure for the two-stage coding. In the simpler case, the two-stage encoding no account of the image content of successive images is carried out. As shown in FIG. 1 passes a signal I, which if desired contains the image content of an image a plurality of successive images, first to a stage 1, in which a first subdivision of the image content is carried out in intermediate segments. This can happen, for example, in a conventional manner by considering the brightness and the color values ​​of the pixels of the image content. The output signal of the block, a label image, in which all points of an intermediate region are i in i with the number.

p0023These data of the intermediate regions are processed to the effect in another circuit block 2 that is checked, which chromaticity values ​​having the pixels of the regions. Among the intermediate regions, there are probably those which have similar chrominance values ​​of their pixels. These intermediate regions are then merged into regions. a chrominance value for all pixels of this region is only provided for each of these regions. The circuit block 2 the representation of FIG. 1 provides the output side this data S of the Regions.

p0024This two-stage nature of the formation of oriented based on the chromaticity values ​​regions will be explained in detail with reference to FIG. 2.

p0025In this FIG. 2A shows an image with registered between regions, as they can be obtained in the first step of the process. Fig. 2B shows the final regions, which have been formed on the basis of Farbartwerte.

p0026The diagram in Fig. 2A, a plurality of intermediate regions have been formed for the illustrated length portrait of a person. Alone for the head 11 of the depicted person six intermediate regions have been formed, in particular, in addition to the facial skin 10 also has its own intermediate region 12 of the nose, and an intermediate region 13 of the mouth of the person depicted.

p0027In the chest area 14 a total of seven intermediate regions have been formed, in particular, a region 15 for the arm of the person or the sleeves and a region 16 for the right side of the chest. In the area of ​​the region 16 there is a further intermediate region 17, which is for example a button on the jacket 16th

p0028These intermediate regions have been formed both on the basis of brightness as well as the color values ​​of the image content. To achieve even greater data reduction especially the chromaticity values, a fusion to regions according to the invention performed as they are entered in FIG. 2B. The formation of these registered in Fig. 2B regions may also take the view in FIG. 2, the procedure is in a two-stage manner, be generated immediately from the original image content.

p0029The illustration shown in FIG. 2B shows, inter alia, that for the header over the intermediate regions two regions could be saved. Thus, the intermediate regions 12 of the nose and the mouth 13 of the intermediate region 10, which represents the other face content, been slammed. From these three intermediate regions 10, 12 and 13 2B is in the representation of FIG. Become a region 21 in which all the pixels of the region 21 having a common chrominance value. This chromaticity value can be created for example by averaging the chrominance values ​​of the regions 10, 12 and 13. FIG. Similarly, there has been a new region 22 in the chest area a fusion of the regions 15, 16 and 17th This is similar to the facial area, possible because it was in the intermediate regions 15, 16 and 17 are those which have similar Farbartwerte. In this example, there are various parts of the jacket, which differ more by brightness values ​​than by color values.

p0030Correspondingly, a further reduction of the data by merger of two registered in Fig. 2A between regions could be 18 and 19 achieved, representing parts of the tie of the person in the chest area. This tie is now represented by a common region 23rd

p0031As a result, Figure 2B shows the Fig., The formed regions which reproduce those image contents having similar chrominance values. For vorzunehmene encoding the data of the image this region formation is useful because on the one hand borders of different of in the image depicted objects are identified by the region formation, and there already to another through the region forming a considerable data reduction of the color values ​​is obtained. then only for the subsequent coding the brightness values ​​of pixels to be coded appropriately.

p0032In the representation of FIG. 2 a two-step encoding was made without taking into account the image contents of preceding or subsequent images within an image.

p0033The following text with reference to the representation of FIG. 2 and 3 are shown, may be additional ways in which a consideration of the image content of successive images, and how this affects the formation of the intermediate regions and the regions.

p0034In Fig. 3A is a view corresponding to Fig. 2A is indicated. In the image content illustrated in FIG. 3A is the image the image Fig. 2A below. For the formation of the intermediate regions of the image corresponding to FIG. 3A is a tracing of the intermediate regions formed in Fig. 2A is carried out based on a motion estimation. By means of this motion estimation, most intermediate regions can be found in the example shown again. In the example of FIG. 2A and 3A, the person depicted has little moved. Due to the motion estimation, a follow-up of intermediate regions would even still succeed if the person would have, for example, moved from the left half of the right half.

p0035In the example case of FIG. 3A all intermediate regions 17 of FIG. 2A could be retrieved with the exception of the intermediate region. The intermediate region 17 as shown in FIG. 2A could not be retrieved because in the chest of the person depicted has pushed a sheet that has been summarized for the segmentation of the image shown in Fig. 3A to a new intermediate region 31st In the image shown in FIG. 3A, an arm is also surfaced with the sleeves are combined to form an intermediate region 32 and the hand to an intermediate region 33rd

p0036As a result, had to be 31, 32 and 33 re-formed as shown in FIG. 3A for the image only three intermediate regions. The remaining intermediate regions could be taken from Fig. 2A. Thus a significant reduction in computational complexity is achieved, since the data of the intermediate regions were adopted by 10 to 16 and 18 and 19th

p0037Also for the illustrated in Fig. 3B forming the regions, which is made with reference to the chromaticity values ​​of the pixels, it holds that an attempt is made to locate regions formed in a previous image again and take over.

p0038From the segmentation process of the previous image shown in FIG. 2 is known for example that the intermediate regions can be 12, 13 and 10 merged into one new common region 21st Therefore, can be repeated for the next image as shown in FIG. 3 for the formation of regions of operation. If necessary, can be dispensed with a single review of Farbartwerte incremental regions or their pixels. For the illustrated in Fig. 3B next screen with the regions this segmentation is automatically taken from the model, because the associated intermediate regions 10, 12 and 13 as shown in FIG. 3A were retrieved and thus the summary of these intermediate regions to the common region 21 can also be taken for the next screen shown in Fig. 3.

p0039Basically succeed in the well, the intermediate regions 15 and 16 to merge in Fig. 3 as a result image to the image shown in Fig. 2 to the new region 22nd The intermediate region 17 is, however, ceased to exist, and therefore can no longer be added to this region 22nd Instead, a new intermediate region 31 has emerged, which can be added to any other intermediate region and therefore constitutes a new region 42nd The reason for this is for example the fact that the sheet has a significantly different color than its surroundings and therefore in particular can not be allocated to the region 22nd

p0040The intermediate region 20, which was acquired in the representation of FIG. 2 unchanged to a region 20, can be fused with the layer formed by the sleeve intermediate region 32 to a new region 41 in the representation of FIG. 3 due to the addition appearing arm. The hand 33 has a different color than the areas surrounding them, so that the intermediate region 33 has become a new Region 43rd

p0041As a result, the display shows in FIG. 3 in that both in the first stage as well as in the second stage, taking into account the picture content of the model and the intermediate regions or regions formed in this for the segmentation of the next picture corresponding to FIG. 3A can be carried out , It is thus the new calculation lapses for a variety of regions and even between regions, since the associated data can be transferred from the model.

p0042Fig. 4 shows a schematic block diagram of how such a two-stage segmentation, in which a consideration of the picture contents of preceding images is carried out, can be made.

p0043In FIG. 4, a circuit block 51 are sequentially the data of successive images I_n, I_{n + 1} etc. supplied. In the circuit block 51 takes in accordance with the circuit block 1 of FIG. 1 a forming the intermediate regions instead. The output data generated to turn the circuit block 51 is supplied via a delay element 52, so that, for example, an image I_{n + 1} which in the example I_n determined between regions are available and their data can be used for motion estimation.

p0044The circuit block 51 is a circuit block 53 connected downstream, where according to the circuit block 2 of the illustration according to FIG. 1 is a formation of regions is performed. Unlike the case shown in Fig. 1 is made, however, in the representation of FIG. 4 is a consideration of the intermediate regions and the regions of the model. The circuit block 53 provides the output side also data indicating from which intermediate regions make up a region. The output side supplied from the circuit block 53 data for the regions of an image to be delayed by a delay element, so that, for example, for the formation of regions of an image I_{n + 1} which in the previous image I_n formed regions are available.

p0045The diagram in Fig. 4 also shows a circuit block 55 which encodes the shape and positioning of regions and spends as data Region S. Such coding region data indicates their location, size, etc.. Here it is advantageous to use a so-called chain code, indicating the location of all boundary points of a region. Only their relative position is based on an output pixel whose position is transmitted completely coded, each of adjacent pixels above, below, left or transfer the right of the adjacent pixel.

p0046Fig. 4 also shows a circuit block 56 in which a coding of the color data is performed. As segmentation and in particular the formation of the Regions has previously carried out in such a way that all related to a region pixels only have a common chrominance value, here coding is only region as required. The circuit block 56 therefore generates for each region, for example, a color difference pair UV_CIndicative of the coded color information for all pixels of a region.

p0047Further, a circuit block 57 is provided, which the brightness values ​​of the pixels in an encoded form as a signal Y_C outputs. both the data of the intermediate regions and the regions can optionally be used to encode the luminance information. a more detailed coding of the individual values ​​of the pixels may have to be made for the brightness information, so that not all the pixels of a region can be encoded with the same brightness value.

p0048The diagram in Fig. 4 shows, with reference to the schematic representation of the circuit blocks 51 to 54, the image segmentation according to the invention. The coding of the image content that will be made in the circuit block 57 is not the subject of the invention.