12D-DST scheme for image mirroring and rotation Do Nyeon Kim and K. R. Rao Department of Electrical Engineering The University of Texas at Arlington 416 Yates Street, TX 76019, USA E-mail: [email protected], [email protected] Abstract. Mirroring an image (horizontally or vertically) and rotation by 90°, 180° and 270° in the spatial domain has been implemented by changing the signs of the 2D-DCT coefficients of the original image appropriately. This approach leads to an efficient compressed domain-based image mirroring and rotation. This technique is now extended to 2D-DST, i.e., 2D-DST has properties similar to 2D-DCT and can be applied to image mirroring (horizontally or vertically) and also rotation by 90°, 180° and 270°. We illustrate these methods in video editing application. 1 Introduction Image or video coding standards like JPEG, MPEG-1,2,4 and latest H.264 utilize DCT or integer DCT1 to compress image or video data. We can compress images to save storage space or transmit and then edit in the compressed-domain. Compressed-domain image manipulation has been introduced by Smith and Rowe2. By using the linearity of the DCT, video dissolve and caption insert were processed in the compressed domain. Chang and Messerschmitt3 introduced a method to reconstruct DCT block using neighboring2four DCT blocks in the compressed domain based on the fact that the DCT is distributive to matrix multiplication. Merhav and Bhaskaran4 introduced fast DCT-domain bilinear interpolation and motion compensation. Shen, Sethi and Bhaskaran5 introduced logotype insertion in the compressed video. They showed that DCT-domain convolution which corresponds to multiplication in the spatial domain is more efficient because of the orthogonality of the DCT. As an extension of these studies, a discrete cosine transform (DCT)-domain image flipping scheme has been introduced.6 We present a similar discrete sine transform (DST)-domain7,8 image mirroring and rotation scheme in this paper. 2 Proposed Algorithm By changing the signs of the DST (discrete sine transform) coefficients, we can change the order of input sequence elements into the reverse order in the time domain. In other words, let (){,1X (),2X …, ()}1−NX be the DST coefficients of a sequence, (){,1x (),2x …, ()}1−Nx . Change the signs of the DST coefficients as follows, (){,1X (),2X− (),3x (),4X− …, ()}1−− Nx . The inverse DST of the latter is (){}11−=Nnny(){,1−= Nx (),2−Nx …, (),2x ()}1x which has elements in reverse order. This can be proved as follows. For a sequence, x(n) for n = 1, 2, …, 1−N, the DST Type I and its inverse7 are defined as follows: ⎟⎠⎞⎜⎝⎛=∑−=NmnnxNmXNnπsin)(2)(11 m = 1, 2, …, 1−N (1) ⎟⎠⎞⎜⎝⎛=∑−=NmnmXNnxNmπsin)(2)(11 n = 1, 2, …, 1−N . (2)3 From Eq. (2) we can recover the sequence (){}11−=Nnnx as follows: ⎥⎦⎤⎢⎣⎡+++= "NXNXNXNxπππ3sin)3(2sin)2(sin)1(2)1( (3) ⎥⎦⎤⎢⎣⎡+++= "NXNXNXNxπππ6sin)3(4sin)2(2sin)1(2)2( (4) … ⎥⎦⎤+−+−+⎢⎣⎡−+−=−"ππππ41sin)4(31sin)3(21sin)2(1sin)1(2)1(NNXNNXNNXNNXNNx (5) .4sin)4(3sin)3(2sin)2(sin)1(2⎥⎦⎤+−⎢⎣⎡+−="NXNXNXNXNππππ (6) Let Y(m) for m = 1, 2, …, 1−N be the DST coefficients of y(n) for n = 1, 2, …, 1−N, and be related to X(m) for m = 1, 2, …, 1−N as follows: )12()12( −=− kXkY (7) )2()2( kXkY −= (8) for k = 1, 2, …, ()21−N . The sequence y(n) for n = 1, 2, …, 1−N is the mirror sequence of (){}11−=Nnnx, i.e., )1(4sin)4(3sin)3(2sin)2(sin)1(2)1(−=⎥⎦⎤+−⎢⎣⎡+−=NxNXNXNXNXNy"ππππ (9) …4)2(42sin)4(32sin)3(22sin)2(2sin)1(2)2(xNNXNNXNNXNNXNNy=⎥⎦⎤+−−−+⎢⎣⎡−−−=−"ππππ (10) ().141sin)4(31sin)3(21sin)2(1sin)1(2)1(xNNXNNXNNXNNXNNy=⎥⎦⎤+−−−+⎢⎣⎡−−−=−"ππππ (11) 11)}({−=Nnny(){,1−= Nx(),2−Nx …, (),2x()}1x is (){}11−=Nnnx in reverse order. 3 Extension to the Two-D Case Mirroring and rotation of an image is illustrated using a (4×4) block. Given []⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛=44434241343332312423222114131211xxxxxxxxxxxxxxxxx Horizontally mirrored sequence of []x is []⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛=41424344313233342122232411121314xxxxxxxxxxxxxxxxxh. Vertically mirrored sequence of []x is []⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛=14131211242322213433323144434241xxxxxxxxxxxxxxxxxv.5[]x rotated by 90o is []⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛=1424344413233343122232421121314190xxxxxxxxxxxxxxxxxO. []x rotated by 180o is []⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛=11121314212223243132333441424344180xxxxxxxxxxxxxxxxxO. []x rotated by 270o is []⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛=41312111423222124333231344342414270xxxxxxxxxxxxxxxxxO. Then []Ox90= []{}Txh, where {}⋅h denotes horizontal flipping an input matrix and is defined by [] []{}[][]Jxxhxh== (12) where []⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛=OOJ111$ is the opposite diagonal unit matrix. Here the superscript T represents transpose. Image can be represented as nonoverlapping blocks of size ()( )11 −×− NN (for example 81 =−N). Each block can be represented as a matrix []81,2121)},({==nnnnxx. The DST is defined in matrix form as []81,1111)},({==nmnmsS where6)9sin(92),(1111πmnnms =. (13) Then we can compute the two-dimensional DST coefficients matrix []X of an input image block or matrix, []x as follows: [][][][]SxSX =. (14) Let the 2D-DST of horizontally mirrored sequence []hx be []HX and the 2D-DST of vertically mirrored sequence []vx be []VX. Then we can compute []HX and []VX as follows: [][][]MXXH= (15) [][][]XMXV= (16) where the matrix []M is defined as []⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝⎛−−−−=1000000001000000001000000001000000001000000001000000001000000001M. (17) Thus we can select a group of consecutive 2D-DST blocks of an image and flip horizontally according to the following steps: 1. Apply the (8×8) 2D-DST to the nonoverlapping blocks of size (8×8) of the image. 2. Set the size of a rectangular block to be horizontally flipped. Horizontal and vertical sizes should be multiples of eight according to the DST size. 3. Compute DST-domain image flipping for each 2D-DST block by using Eq. (15).74. Rotate horizontally DST blocks within the rectangular block. The most left DST block goes to the most right, and vice versa. In general this