Image analysis – Image compression or coding – Shape – icon – or feature-based compression
Reexamination Certificate
1997-08-08
2002-07-30
Au, Amelia M. (Department: 2623)
Image analysis
Image compression or coding
Shape, icon, or feature-based compression
C382S305000
Reexamination Certificate
active
06427028
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method for the linear transformation of image signals on arbitrarily-shaped segments.
The term image signal is understood herein to mean a 2D or 3D digital signal. The term segment is understood to mean the geometry of the region of the image defining the object of interest. The invention relates more particularly to a method for the linear transformation of an image signal on arbitrarily-shaped and arbitrarily sized segments with a view to encoding.
The invention can be applied to image encoding by linear transformation.
The method presented falls within the context of the development of a new class of image encoders known as object-oriented encoders. This is a novel approach to encoding in which the audiovisual scene is represented as a set of objects in motion. This opens the way towards the implementation of new functions related to digital images.
Standardized systems for the encoding of images with digital bit rate reduction (for example according to the H261 recommendation of the CCITT for video encoding at P times 64 Kbits/s) are based on a sub-division of the digital image into a set of square blocks (with a general size of 8×8) which undergo the encoding operations. This formulation is a rigid one and does not take account of the contents of each block, for example the existence of contours or sharp variations in luminance within a block.
The encoding of the image signal generally comprises a first phase of orthogonal linear transformation aimed at concentrating the energy of the signal and decorrelating its components
The linear transformation used is generally the discrete cosine transform or DCT which can be implemented by simple or efficient algorithms and therefore enables real-time applications. The DCT has been chosen because it can be used to obtain a decorrelation close to the maximum when the signal can be represented by a separable first-order Markov process that is highly correlated, i.e. with a correlation coefficient close to 1.
It is however highly advantageous for many applications to show the image in terms of objects to be found, described and transmitted.
In this context, an object can be defined as a arbitrarily-shaped and arbitrarily-sized region of the image, which may represent either a physical object or a predefined zone of interest or simply a region that has properties of homogeneity with respect to one or more criteria.
An object may be described by its shape and texture.
Several authors have recently taken an interest in the search for appropriate methods to encode, firstly, the shapes of objects and, secondly, the texture of objects.
Reference may be made to the drawing of
FIG. 1
which illustrates the different steps implemented by these methods. The processing of shapes comprises an encoding operation, transmission, decoding at reception and depiction.
The processing of the texture comprises an orthogonal transformation, a quantification and an entropic encoding, transmission, entropic decoding with reverse quantification and reverse transformation to reconstitute the texture.
The methods of linear transformation on square blocks of a size fixed in advance cannot be directly applied to objects with arbitrarily-shaped segments for the encoding of the texture.
Thus, the present invention relates to a new method of linear transformation for the encoding of the texture on objects that have arbitrarily-shaped segments.
2. Description of the Prior Art
Recent studies on the subject have been published by several authors. The methods proposed can be divided into two classes: adaptive methods and methods of extrapolation.
Adaptive methods consist of the adaptation of the orthogonal linear transformations to the geometry of the segment.
Reference may be made to the adaptation of the Karhunen-Loeve transformation to segments by S. F. Chang and D. G. Messerschmidt, Transform Coding of Arbitrarily-Shaped Image Segments, Proceedings of ACM Multimedia, Anaheim, Calif., USA, pp. 83-90, Aug. 1993 and the method for the generation of orthogonal bases on segments proposed by Gilge, T. Engelhardt and R. Mehlan, Coding of Arbitrarily-Shaped Image Segments Based on a Generalized Orthogonal Transform. Signal processing,: Image Communication 1, pp. 153-180, 1989.
This method recommends the orthonormalization of any family of vectors, which are free on the segment, by an algebraic method known as the Gram-Schmidt method. This method is however very cumbersome from the computational point of view and is therefore unsuited to“real-time” applications. Gilge's work has given rise to many studies on the fast generation of orthogonal bases on the segment ([M. Cermelli, F. Lavagetto and M. Pampolini, A Fast Algorithm for Region-Oriented Texture Coding, ICASSP, 1994, pp. 285-288], [W. Philips, A Fast Algorithm for the Generation of Orthogonal Base Functions on an Arbitrarily-Shaped Region, Proceedings of ICASSP 1992, Vol. 3, pp. 421-424, Mar. 1992, San Francisco], [W. Philips and C. Christopoulos, Fast Segmented Image Coding Using Weakly Separable Bases, Proceedings of ICASSP 1994, Vol. 5, pp. 345-348]).
The methods of extrapolation consisting in extending the signal to a regular segment which is generally the rectangle circumscribed in the segment to be encoded.
These methods enable the application of existing linear transformations to regular (rectangular or square-shaped) segments which are therefore fast and easy to implement. In this category of methods, the best known is the iterative method based on projections on convex sets proposed in H. H. Chen, M. R. Cinvalar and B. G. Haskell, A Block Transform Coder For Arbitrarily-Shaped Image Segments, International Conference on Image Processing (ICIP), 1994, pp. 85-89.
Other simpler methods have been tested, such as “zero-padding” (filling of the zone with zeros), “mirroring” (reflection of the signal on edges of the object) and morphological expansion ([S. F. Chang and D. G. Messerschmidt, Transform Coding Of Arbitrarily-Shaped Image Segments, Proceedings of ACM Multimedia, Anaheim, Calif., USA, pp. 83-90, Aug. 1993], [H. H. Chen, M. R. Chinvalar and B. G. Haskell, A Block Transform Coder For Arbitrarily-Shaped Image Segments, International Conference on Image Processing (ICIP), 1994, pp. 85-89]).
The two classes of methods recalled here above have their own advantages and drawbacks.
The adaptive methods have the advantage of perfect reconstruction with as many coefficients as there are points of the segment when no quantification is done. They enable the theory of encoding by linear transformation to be extended to arbitrarily-shaped segments. By contrast, they are generally cumbersome in terms of complexity and computation time.
The methods of extrapolation on the contrary offer an easy implementation suited to existing systems, but entail the risk of contributing artifacts related to the introduction of new frequencies in the signal.
For practical applications, it would therefore be worthwhile to combine the advantages of both categories of methods referred to here above, i.e. to use linear transformations that are fast and adapted to segments. The work done in D1 (M. Bi, W. K. Cham and Z. H. Zheng, Discrete Cosine Transform on Irregular Shape for Image Coding, IEEE Tencon 93 Proceedings, Beijing, pp. 402-405) and D2 (T. Sikora and B. Makai, Shape Adaptive DCT for Generic Coding of Video, IEEE Transactions on Circuits and Systems for Video Technology, Vol. 5, No. 1, pp. 59-72, Feb. 1995) proposes the application of a standard DCT orthogonal transformation separately on the rows and columns of the segment, by analogy with the row/column separability of the standard orthogonal transformations. This separability enables the successive application of two one-way transformations.
In D
1
, the authors propose a stage of analysis of the correlations between the coefficients derived from the first transformation, making the method fairly complex. In D2, the grouping and t
Avaro Olivier
Donescu Ioana
Roux Christian
Au Amelia M.
France Telecome
Nilles & Nilles SC
Wu Jingge
LandOfFree
Method for the transformation of images signals on... 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 for the transformation of images signals on..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for the transformation of images signals on... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2911349