Arbitrary shape wavelet transform with phase alignment

Details Arbitrary shape wavelet transform with phase alignment Arbitrary shape wavelet transform with phase alignment

1998-07-07

2001-05-15

Mancuso, Joseph (Department: 2621)

Image analysis

Image compression or coding

Transform coding

C382S240000

Reexamination Certificate

active

06233357

ABSTRACT:

BACKGROUND OF THE INVENTION
The invention relates to wavelet transform of an arbitrary shape object and more particularly to an arbitrary shape wavelet transform with phase alignment (ASWP).
Compared with coding a whole rectangular image, coding of individual objects in a nonrectangular shape has numerous advantages in coding efficiency and functionality. Such coding requires coding of the shape mask and the content image. The binary shape mask can be encoded by modified modified READ or context adaptive arithmetic coding. The arbitrary shape content image is transformed into the transform domain, quantized and entropy encoded. Since the content image is not of a rectangular shape, regular DCT and wavelet transforms can not be applied directly.
There are a number of approaches for transforming an arbitrary shape content image. The most popular approach is padding which is described by Z. Wu and T. Kanamaru, “Block-based DCT and wavelet selective coding for arbitrarily shaped images”, Visual Communication and Image Processing'97, SPIE Vol. 3024, pp. 658-665, January 1997, San Jose, Calif. With padding, the image is segmented into fixed size blocks. Only those blocks that contain at least one object pixel are encoded. For blocks that are not fully occupied by the object, the remaining pixels are padded repeatedly with nearby object pixels. Since padding increases the number of coefficients to be coded, coding efficiency is significantly decreased. An improved version of the padding approach is described by J. Moon, G. Park, S. Chun and S. Choi, “Shape-adaptive region partitioning method for shape-assisted block-based texture coding”, IEEE Trans. on Circuits and Systems for Video Technology, vol. 7, no.1, pp.240-246, February 1997. In Moon et al., block positions are systematically changed to reduce the number of blocks that need to be coded and the number of coefficients that need to be padded.
A wavelet padding approach is described by H. Katata, N. Ito, T. Anno and H. Kusao, “Object wavelet transform for coding of arbitrarily shaped image segments”, IEEE Trans. on Circuits and Systems for Video Technology, vol. 7, no. 1, pp.235-237, February 1997. In Katata, et. al., padding is restricted to a small region around the original object. Although these techniques reduce the number of coefficients to be padded, padding is still required.
A shape-adaptive (SA) DCT is described by P. Kauff, B. Makai, S. Rauthenberg, U. Golz, J. Lameillieure and T. Sikora, “Functional coding of video using a shape-adaptive DCT algorithm and an object-based motion prediction toolbox”, IEEE Trans. on Circuits and systems and Video Technology, vol. 7, no. 1, pp.181-196, February 1997. The shape-adaptive (SA) DCT avoids padding in block based DCTs. To apply the DCT to a block not fully occupied by the object, SA-DCT first moves all pixels toward the upper block boundary. A variable basis DCT is applied independently to each column with the DCT basis equal to the number of coefficients in each column. After SA-DCT in the vertical direction, the pixels are moved toward the left block boundary, and a similar variable basis DCT with basis corresponding to the number of coefficients in each row are applied horizontally.
Although SA-DCT avoids padding, there are several disadvantages in terms of transform efficiency and implementation complexity. The variable basis DCT used in SA-DCT has no fast algorithms. It is also not separable and the result is different if the horizontal transform is applied first. Transform efficiency is reduced because the neighboring pixels in the horizontal transform might not be the neighboring pixels in the original image. A nonpadding shape adaptive wavelet transform is described by W. Li and S. Li, “Shape-adaptive discrete wavelet transform for coding arbitrarily type shaped texture”, Visual Communication and Image Processing'97, SPIE Vol. 3024, pp. 1046-1056, January 1997, San Jose, Calif. Whenever the data length is longer than the wavelet filter, if the data length is even, the data is directly transformed with a circular wavelet transform, if the data length is odd, the data is truncated to the next even length and transformed again with the circular wavelet transform, the extra pixel is copied directly to the low pass band. A Haar transform is adopted whenever the wavelet filter length is longer than the data. This technique is complex as there are several modes of the transform. The transform efficiency is also reduced since the Haar transform adopted when the data length is short is not very efficient, and in a 2D transform, the subsequent vertical transform is not applied on the phase aligned horizontal transform coefficients.
Thus a need remains to improve the transform efficiency for encoding arbitrary shaped objects.
SUMMARY OF THE INVENTION
A 2-D arbitrary shape wavelet transform with phase alignment (ASWP) is used to transform an arbitrary shaped object in an image. The 2-D ASWP first 1-D ASWP transforms the object horizontally and then l-D ASWP transforms the object vertically. The 1-D ASWP will first be discussed and then the 2-D ASWP. In 1-D ASWP, the phase of an odd tap wavelet filter is adjusted so that the center of the low and high pass filters are always aligned with an alternate odd and even index with regard to the original segments. The phase of an even tap wavelet filter is adjusted so that the low pass filter and the high pass filter are both centered in the middle of the odd and even index with regard to the original segments. The objects are then wavelet transformed using symmetrical extension.
1-D ASWP separately transform 1-D objects that each occupy pixels from index idx_st to index idx_end, with length len=idx_end-idx_st+1. The 1-D objects for odd tap wavelet filters are each symmetrically extended by mirroring the objects separately from the opposite ends but not mirroring the pixels at locations idx_st and idx_end. The objects for the even tap filter are symmetrically extended by mirroring the pixels from the opposite ends including mirroring the pixels at locations idx_st and idx_end. The phase of the filter is then adjusted according to the index with respect to the original segment, not the index with respect to the objects. The objects are then transformed by wavelet filtering with symmetrical extension.
The ASWP is different from other shape adaptive wavelet transforms in that the ASWP can handle objects of both even and odd length. Also, during a horizontal wavelet transform, the phase of the wavelet coefficients are aligned for further vertical decomposition. Unlike padding based wavelet transforms, ASWP does not require any padding, and the number of coefficients after performing the arbitrary shape wavelet transform is exactly the same as that in the space domain. The ASWP scheme is based on the symmetrical signal extensions already used with rectangular shaped wavelet transforms. Thus, ASWP can be implemented using current existing hardware. Because the ASWP is consistent in implementation with rectangular wavelet transforms, there is no implementation overhead.
The foregoing and other objectives, features and advantages of the invention will become more readily apparent from the following detailed description of a preferred embodiment of the invention, which proceeds with reference to the accompanying drawings.


REFERENCES:
patent: 5862260 (1999-01-01), Rhoads
patent: 5867602 (1999-02-01), Zandi et al.
patent: 5966465 (1999-10-01), Keith et al.
patent: 5999656 (1999-12-01), Zandi et al.
patent: 2 758 636 (1998-10-01), None
Efficient Signal Extension for Subband/Wavelet Decomposition of Arbitrary Length Signals by H.J. Barnard, J.H. Weber and J. Biemond, Delft University of Technology, Dept. of Electrical Engineering,966/SPIEvol. 2094 (10 pp.)
Signal Extension and Noncausal Filtering for Subband Coding of Images by Stephen A. Martucci, School of Electrical Engineering, Georgia Institute of Technology,SPIE vol. 1605 Visual Communications and Image Processing '91: Visual Communication, pp. 137-148.
Discrete Cos

Affiliated with

Also associated with

Rating

Arbitrary shape wavelet transform with phase alignment does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Arbitrary shape wavelet transform with phase alignment, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arbitrary shape wavelet transform with phase alignment will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2468541