Interpolation and extrapolation of image partitions using Fourier descriptors: application to segmentation-based coding schemes

INTERPOLATION AND EXTRAPOLATION OF IMAGE PARTITIONS USING CODING SCHEMES FOURIER DESCRIPTORS: APPLICATION TO SEGMENTATION-BASED Ferran Marque's, Bernat Llorens and Antoni Gasull Dept. de Teoria del Senyal i Comunicacions Universitat Politkcnica de Catalunya Campus Nord UPC - Edifici D5 c/ Gran Capit& s/n. 08034 Barcelona, Spain E-mail: [email protected] ABSTRACT This paper presents an interpolation/extrapolation technique for sequence partitions. It consists of four steps: region parametrization, region interpolation, region ordering and partition creation. The evolution of each region is divided into two types: regular motion and random deformations. Both types of evolution are parametrized by means of the Fourier descriptors of the regions and they are separately interpolated in the Fourier domain. The final interpolated partition is built from the ordered combination of the interpolated regions, using morphological tools. 1. INTRODUCTION In the framework of image sequence coding, there is a continuos need of new techniques to reach higher compression ratios. A usual approach to reduce the information to be sent is to code only a subset of the total amount of frames in the image sequence. In the receiver side, frames which have not been sent are interpolated from the transmitted information. This is the technique used in the MPEG-2 standard, where the so-called B-frames are interpolated. Towards the goal of achieving very low bit-rates, second generation coding techniques [3] have been proposed. In this framework, the study of segmentation-based coding techniques is, nowadays, a very active field of research [6] [l]. In this case, an accurate interpolation can be performed relying on the coded partitions and gray levels of each region. Therefore, two different types of information should be interpolated: gray levels and partitions. In the coding process, gray levels are usually parametrized (polynomial coefficients, DCT components, ...) so that they can be easily interpolated. On the other hand, typical partition coding techniques [2] do not parametrize contours and, therefore, their interpolation is not straightforward. To interpolate partitions, the information of the interior of the regions yielded by the segmentation could be This work has been partially supported by the RACE Project 2072 (MAVT) of the European Union and the TIC 92-1319-CO3- 01-PB of the Spanish Government used. However, segmentations can be obtained using different criteria and, therefore, regions can be related to different concepts: homogeneous gray level, homogeneous motion, special type of textures, etc. To implement an interpolation technique independent of the segmentation criteria, the technique should use only partition information; that is, the shape and the position of regions in the partition. The first step to interpolate a set of partitions between two initial ones is to perform a region matching between the regions forming these initial partitions. A region appearing in both initial partitions should have assigned the same label in both partitions. When this statement is fulfilled, sequence partitions are said to have temporal label coherence. Region matching is a difficult problem and its solutions are usually very time consuming. Segmentation-based coding techniques solve this problem by keeping track of the region labels through the time domain while performing the segmentation. Thus, the interpolation procedure can assume initial partitions with temporal label coherence. However, a sequence coding scheme may, very likely, use an Intra-frame mode as refreshment, interleaved with the Inter-frame ones. In the case of an Intra-frame mode, the information to be sent is not related to the previously transmitted information. The temporal label coherence is, therefore, broken and interpolation is not possible without carrying out a region matching. A second possibility is, rather than to interpolate between both partitions, to generate the intermediate partitions by extrapolating the information of the last Inter-frame and the Intra-frame coded partitions. Extrapolation is not only useful to deal with partition with temporal uncoherence but also to reduce the time delay in the receiver side. That is, instead of interpolating all partitions between two coded ones, some of them can be extrapolated from the former received partition. In this paper, a technique for interpolation and extrapolation of temporal label coherent partitions is proposed. It uses Fourier Descriptors to model the regular motion as well as the random deformations of regions through the time domain. This technique is described in the sequel as follows. After this introduction, Section 2 is devoted to the general interpolation/extrapolation technique. It is composed 584 0-8186-7310-9/95 $4.00 0 1995 IEEE of four steps: region parametrization, region interpolation, region ordering and creation of a partition. Section 3 details the specific implementation of each of these four steps. To evaluate the interpolation technique, some results are presented in Section 4 and some conclusions are driven. 2. GENERAL SCHEME Partition interpolation and extrapolation can be stated as: given two initial partitions P, and P3, each one composed of a set of regions {R,k} {RJk}, respectively, new partitions have to be found representing the evolution from PI to P3 (interpolation) as well as beyond P3 (extrapolation). Two different approaches can be proposed for the problem of image partition interpolation. A first approach is to interpolate directly the initial partitions, jointly analyzing all the regions in the image [4]. This approach is only feasible when regions slightly vary their position from the first to the last partition. A second approach is to interpolate each region separately and, afterwards, to combine the interpolated regions in order to build the interpolated partitions. This approach can handle partitions without constrains in the region positions. Given this capability, this approach has been chosen in this work. The general interpolation/extrapolation scheme relies on the shape and position information of each region. Region evolution through the time domain is divided into two types: regular motion and random deformations. Regular motion is described by a given motion model (e.g.: translation, zoom and/or rotation). The region evolution that cannot be described by regular motion is said to be random deformations. Both types of information should be parametrized for each region in order to easily obtain its interpolation. There exist techniques that, rather than parametrizing regions, perform the interpolation by computing a geodesical distance between regions in the initial partitions [4] [7]. Such an approach does not allow to extrapolate, given the fact that the geodesical distance is only defined between the two initial partitions P, and P3. Once regions in both partitions have been parameterized, their parameters are interpolated. This parameter interpolation yields a separated representation of the evolution of each region. That is, for each region, it5 position and shape are obtained at each interpolated partition. The region interpolation has to handle the problem of regions which are only in one of the two initial partitions (appearing or disappearing regions). In addition, interpolated regions cannot be directly combined to obtained the final interpolated partition. When combining them, two problems arise. First, interpolated regions can overlap andl, second, some parts of the space may not be covered by any region. To solve the first problem, regions are ordered This ordering gives priority to one region with respect to its neighbors so that, in case of overlap, the area of overlapping is assigned to this region. Finally, after combining the interpolated regions following the above ordering, uncovered areas should be assigned to some of the neighbor regions. This is done in order to ensure that a final partition is achieved. The complete scheme is illustrated in Figure 1. Initial Partitions 1 Parametrization 54 Ordering ic Partition Creation t InterpolatedExtrapolated Partitions Figure 1: General scheme 3. IN’TERPOLATION/EXTRAPOLATION OF IMAGE PARTITIONS In this section, specific implementations of the above four steps are described. They use a Fourier descriptor representation and mathematical morphology tools. 3.1. Region parametrization A given region from both initial partitions (that is, R,, and RJp) is separately parametrized. Their contours are described as two complex functions zEp[n] and z3,[n], namely position functions, where both contours have been normalized to contain the same number of samples N. There is a direct relationship between a position function z[n] and its Fourier transform Z[k]. This transform yields the Fourier descriptor definition: N-1 1 N Z[k] = - c z[n] e--j+n n=O From the Fourier descriptors, a new set of parameters can be defined. This set is more useful for describing the evolution of the contours and, therefore, for interpolation purposes. The evolution between two regions RI, and R3, can be represented as the differences between their contour representations zlP[n] and z3,[n]. This evolution can be divided into two types: regular motion and random deformations. The human visual system is much more sensitive to errors in the interpolation of the regular motion than of the random deformations. Therefore, the information related to regular motion is extracted first from the Fourier descriptors and treated separately. Afterwards, the Fourier descriptors are normalized with respect to the regular motion parameters so that parameters describing the random deformations are obtained. In this work, regular motion corresponds to equiform transformations [8] : translation (Pc,~ E C), zooming (So,@ E R+) and rotation 585 (E,,a E [0,2~]). The parameters related with these concepts are: Gravity center C: It is related to the translation. It is obtained directly from the first Fourier descriptor. The contour representation is normalized Dc by substracting this sample to the Fourier descriptors: ( = Z[O], D<Z[k] = Z[k] - (6[k] (2) Size p: It is related to the zooming. It is obtained as the magnitude of the Fourier descriptors. The contour representation is normalized Sp by dividing the Fourier descriptors by their euclidean norm: (3) Angle of rotation a and initial point r: They are related to the rotation. Several methods for estimating both parameters separately have been analyzed. Nevertheless, the most robust technique has shown to be a joint estimation of both parameters. This technique adds a line phase to the phase of the Fourier descriptors so that the two coefficients of greatest magnitude, Z[kl] and Z[k,], become real after normalization I, R,. That is, 2n N ~(Z*[kl) = ~(Z[kl) + -rk + a = 2xr, T E Z (5) Actually, the estimation of these two parameters is done in such a way that it already accounts with the contour evolution. That is, parameters related to the rotation of region R, are computed using information from the contours in both images, Z,,[k] and Zjp[k]. This is implemented by using for normalization the two coefficients z and j leading to the two greatest magnitude of the product MP[k] =I[ Z,,[k]Z,,[k] 11 (MP[ki] > MP[k2] is assumed). In order not to withdraw possible correct solutions, all cases where O.lMP[k2] < MP[k] are analyzed. Using (5), each pair of possible coefficients results in a set of pairs of normalization parameters (a, r). To chose the final pair (a, r), a measure of dissimilarity is utilized: This measure may yield solutions representing very large rotations. Such rotations are not usual in the addressed application. Thus, a pair (a, r) leading to a solution close to the minimum one but involving a smaller rotation is chosen: d[Z;, z:]" < 2d[Z;, Z2*]mtn1mZlm (7) After this final normalization, contours are represented by two sets of parameters. The first set is related to the regular motion of the region ((,/3, a,r) whereas the second set (Z*[k]) is related to the random deformations. Given that the normalization of a region R, is done using the contour representation of this region in both initial partitions (Z,,[k] and Z,,[k]), conflictive regions (appearing or disappearing regions) have to be handle separately. For such regions, a weighted average of the parameters of their neighbor regions is computed. The weights depend on the amount of contour points that are shared between the given region and its neighbor. The parameters of the neighbor region being closer to the averaged parameters are assigned to the conflictive region. 3.2. Region interpolation/extrapolation The above set of parameters is interpolated in order to obtained the contour representation of the interpolated regions. Several techniques have been analyzed for interpolating both the regular motion and the random deformations. For the case of regular motion parameters, linear interpolation leads to a result which is more pleasant for the human visual system. It yields smooth transitions between regions. Different solutions for the interpolation of random deformation parameters have been also analyzed. Actually, four different techniques for interpolating the normalized Fourier descriptors Z*[k] have been tested: Cartesian interpolation, polar interpolation, high frequency substitution and high frequency elimination [5]. Best results, in terms of leading to a deformation conforming to natural objects motion, have been obtained using the Cartesian interpolation. Note that the above technique for interpolation of regular motion and random deformation parameters can also be applied for extrapolation purposes. Figure 2 shows an example of the interpolation of a region obtained from the segmentation of the image sequence Table-Tennis. This example is used to illustrate the importance of using the procedure to estimate (Y and T, above presented. In the first case, the two interpolated regions are obtained with the pair cy,^) leading to the minimum of the measure of dissimilarity (6), whereas in the second case, the solution constrained in rotation (7) is presented. Note that the second solution yields a more natural motion. Figure 2: Example of interpolation constrained in rotation 3.3. Region ordering Once all the regions have been separately interpolated, they are ordered so that possible overlappings are solved. The ordering gives priority to those regions having a smaller amount of random deformations with respect to their neighbors. This procedure assumes that if the evolution of a region R, can be represented only relying on the regular motion in a more accurate way than its neighbors, this region should preserve, as much as possible, the actual shape given by its interpolation. The ordering is obtained by computing a distance on the normalized contours z:,[n] and zj,[n]. Different distances have been analyzed and the best results, in terms of visual quality, have been obtain with the norm L,. higher order level (lower priority) than the non-conflictive Conflictive regions (appearing or disappearing ones) have 586 region of highest order level. If the non-conflictive region with lowest priority has an order level O,,,, a conflictive region R, will receive the order level O[q] = Om,, + Ob]. Ob] represents the ordering of the non-conflictive region R, from which the conflictive region R, had obtained its regular motion parameters. 3.4. Partition creation Interpolated partitions are created by combination of the different interpolated regions respecting the previous ordering. The use of an ordering solves the problem of overlapping regions. However, there may be areas of the space which are not covered by any interpolated region; that is, holes in the interpolated partition. Such areas should be covered by neighbor regions to obtain a final partition. Different techniques have been studied to fill such holes. A simple solution is to dilate the interpolated regions so that their labels cover the holes. For each interpolated region, its geodesical dilation of size 1 is performed. This geodesical dilation uses as reference space the union of the region to be dilated and the area covered by its neighbor holes. It is applied first to the regions with lower level of priority in the previous ordering. That is, the more reliable is the region representation, the smaller its variation should be. This procedure is iterated until all the holes are covered. The previous technique arises two main problems. First, in the case of a hole between two regions, roughly half of the hole is covered by each region, in spite of their priority level. Second, dilated regions may cover areas very distant from the position of the interpolated regions. The first problem is solved by adapting the size of the geodesical dilation to be applied to each region with respect to its level of priority. Therefore, in the same iteration step, a region with lower priority will be dilated by a structuring element of size greater than a region with higher priority. To solve the second problem, the dilation is carried out in two steps. First, a mask is created. Regions from both initial partitions are interpolated keeping fixed their random deformation parameters and only interpolating the regular motion ones. The union of these new interpolated regions forms a mask and only the holes inside this mask will be covered in the first step. Therefore, the reference space for the geodesical dilation of a given region R, in the first step is formed by the intersection of the previous holes and the area covered by the new interpolations of region R,. In the second step, the remaining holes are covered. 4. RESULTS AND CONCLUSIONS Figure 3 shows an example of interpolation of 4 frames from the sequence Carphone between frames 60 and 65. Note the correct evolution of all the regions, in spite of presenting different motions. Figure 4 shows the extrapolation of 2 frames from the same sequence between frames 65 and 70. Frames 66 and 67 have been extrapolated from frame 65 using the parameters obtained in the previous experience. Note that the evolution of all regions is also correct, although being in the case of extrapolation. The example of Figure 3 illustrates the fact that the interpolation technique that has been presented performs correctly. Moreover, it can be easily extended to the case of extrapolation, as shown in the example of Figure 4. This technique has been tested on a large set of sequences and using different segmentation techniques. In all cases, results have the same quality level as those above presented. 5. REFERENCES F. Bartolini and V. Capellini. A segmentation-based motion-compensated scheme for low-rate video coding. In Proceedings of the First IEEE International Conference on Image Processing, volume 11, pages 457-461, Texas, U.S.A., November 1994. C. Gu and M. Kunt. Contour simplification and motion compensation for very low bit-rate video coding. In First IEEE International Conference on Image Processing, pages 423-427, Texas, U.S.A., November 1994. M. Kunt, A. Ikonomopoulos, and M. Kocher. Second generation image coding techniques. Proceedings of the IEEE, 73(4):549-575, April 1985. F. Meyer. Algorithmes d’interpolation base6 sur des distances gCodCsiques. Technical report , Centre de Morphologie MathCmatique, Fontainebleau, Dec. 1994. R. Queval 0. Bertran and H. Maitre. Shape interpolation using fourier descriptors with application to animation graphics. Signal Processing, 4:53-58, 1982. P. Salembier and M. PardLs. Hierarchical morphological segmentation for image sequence coding. IEEE Transactions on Image Processing, 3(5):639-651, Sept. 1994. P. Soille. Generalized geodesic distances applied to interpolation and shape description. In J. Serra and P. Soille, editors, Mathematical morphology and its applications to image processing, pages 193-200. Khiwer Academic Publishers, 1994. P. Van Otterloo. A contour-oriented approach for shape analysis. Prentice Hall International (UK), 1991. Figure 3: Example of interpolation Figure 4: Example of extrapolation 587