Source: http://www.google.com/patents/US7251375?dq=6,163,776
Timestamp: 2016-08-28 13:04:58
Document Index: 606820879

Matched Legal Cases: ['art1', 'art2', 'art3', 'art4', 'art1', 'art2', 'art3', 'art4']

Patent US7251375 - Tile boundary artifact removal for arbitrary wavelet filters - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsA method for processing data is described. In one embodiment, the method includes decompressing a plurality of sets of compressed data, including performing detiling on a first set of compressed data using neighbor information from at least one other set of compressed data, and recombining the plurality...http://www.google.com/patents/US7251375?utm_source=gb-gplus-sharePatent US7251375 - Tile boundary artifact removal for arbitrary wavelet filtersAdvanced Patent SearchPublication numberUS7251375 B2Publication typeGrantApplication numberUS 10/941,537Publication dateJul 31, 2007Filing dateSep 14, 2004Priority dateFeb 29, 2000Fee statusLapsedAlso published asUS6813387, US20050031218Publication number10941537, 941537, US 7251375 B2, US 7251375B2, US-B2-7251375, US7251375 B2, US7251375B2InventorsKathrin Berkner, Edward L. SchwartzOriginal AssigneeRicoh Co., Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (7), Non-Patent Citations (1), Classifications (27), Legal Events (4) External Links: USPTO, USPTO Assignment, EspacenetTile boundary artifact removal for arbitrary wavelet filters
US 7251375 B2Abstract
This is a continuation of application Ser. No. 09/515,458, filed Feb. 29, 2000, now U.S. Pat. No. 6,813,387, entitled “Tile Boundary Artifact Removal for Arbitrary Wavelet Filters,” assigned to the corporate assignee of the present invention and incorporated herein by reference.
A way to avoid block artifacts in wavelet-based compression is presented in J. K. Eom, Y. S. Kim, and J. H. Kim, “A Block Wavelet Transform for Sub-band Image Coding/Decoding,” in SPIE Electroinc Imaging, vol. 2669, (San Jose, Calif.), pp. 169-77, January 1996. In this approach, wavelet coefficients of overlapping tiles are computed. The overlap-size depends on the maximal level of decompression in the wavelet tree. Storing wavelet coefficients computed from overlap regions is equivalent to storing selected coefficients from the full-frame decomposition. The higher the level of decomposition, the more full-frame wavelet coefficients have to be stored. “Line-based” or “rolling buffer” methods have similar storage requirements. These methods complicate random access to memory and parallel processing.
s 2 J m j = Hs 2 J - 1 m j - 1 and d 2 j m j - Gs 2 j - 1 m j - 1 . Using this notation, the coefficients
s 2 j m + 2 j - 1 j and d 2 j m + 2 j - 1 j can be computed by applying the transform operators H and G to the coefficients
s 2 j - 1 ( m + 1 ) j - 1 and d 2 j - 1 ( m + 1 ) j - 1 , which are shifted sequences of the original coefficients. If the coefficients
s 2 j m + 2 J - 1 j and d 2 j m + 2 j - 1 j are available, one step of the inverse transform also yields the set of coefficients sj-1.
s 2 J m j for a classical DWT is shown in FIG. 1B. Referring to FIG. 1B, the application of an inverse transform to the level 2 s coefficients in row 210 produces the level 1 s coefficients in row 211. For example, applying the inverse transform to s coefficient 222-224 and corresponding d coefficients generates s coefficient 225. The number of coefficients of a higher level of decomposition needed to generate one value in the next lower level of decomposition depends on the length of the filter and may depend on the level of decomposition.
s 2 J m + 2 J - 1 j of a shifted DWT is shown in FIG. 1C. Referring to FIG. 1C, the application of a forward transform to the level 1 s coefficients in row 216 produces the level 2 s coefficients in row 215. For example, applying the forward transform to s coefficients 219, 231, 233 and generates s coefficient 218 and the corresponding d coefficient (not shown).
s k - 4 m 2 have to be stored or fed into the computation of the decomposition at the next level. However, the coefficients
s k - ( 4 m - 2 ) 2 can be computed from the stored information by applying one step of the inverse transform and one step of the shifted forward transform. Applied to coefficients of the quality measure at scale 2, this procedure gives the in-between coefficients
s k - ( 4 m - 2 ) 2 . Furthermore, instead of using the coefficients
s k - 4 m 2 , the coefficients
s k - ( 4 m - 2 ) 2 can also be used in the reconstruction of the quality of measure to obtain the coefficients
s k - 2 m 1 . Using these additional coefficients in the reconstruction, smoother approximations are obtained. The technique described herein uses these ideas to “smooth across tiles.” The approximation coefficients s j are computed in a series of steps and starts with lowpass and highpass coefficients at the largest scale, i.e., scale 2 in this example.
s _ k j - 1 of s k j - 1 by applying the inverse transform operator H* to the
s _ k - ( 4 m - 2 ) j coefficients (processing logic 203). Finally, processing logic computes new coefficients
s _ k j - 1 coefficients.
s _ k - 2 2 and s _ k + 2 2 to compute
FIG. 4 is a flow diagram of one embodiment of a process for removing tile boundary coefficients. The processing is performed by processing logic that may comprise hardware, software, or a combination of both. Referring to FIG. 4, processing logic computes s coefficients for the tile wavelet decomposition at level J-1 by applying a tile inverse transform to s and d coefficients at level J (processing block 401). Then processing logic computes an approximation of the full-frame coefficients at level J by applying a full-frame forward transform to the shifted sequence of s coefficients at level J-1 (processing block 402). The result of the computation is an alternative phase of the s coefficients at level J.
function [sc,s,sinv,wc,w,L] = tilecorrectcirc(s,w,p,L,hr,gr); % Detiling for 3–9 wavelet system and scale L=2. In this case only one coefficient % at scale L=1 has to be corrected. % Example: x=wnoise(4,8); L=2; p=64; % [f1,g1,f2,g2]=wfilters(‘bior2.4’); % [s,w,p,L,option]=tiledwtcirc(x,f2,g2,p,L); % [sc,s,sinv,wc,w,L]=tilecorrectcirc(s,w,p,L,f1,g1); % subplot(3,1,1); plot(sc); % smoothed version; % subplot(3,1,2); plot(ttts); % nonsmoothed version; % subplot(3,1,3); plot(ttts-sc); % a = [0.0331 −0.0663 −0.1768 0.4198 0.9944]; % filter coefficients for inverse lowpass b = [0.3536 0.7071 0.3536]; % filter coefficients for forward lowpass origsize = floor(length(s) * (2{circumflex over ( )}L)); mt = origsize/p tsize = length(s)/mt; wc = w; s1=s; wsize = length(w); sc = s; tw = w(wsize−length(s)+1:wsize); size(tw) ttw = zeros(size(tw)); size (ttw) [ts,pp,1] = tileidwtcirc(tw,s,hr,gr,p/2,1); sinv = ts; size(ts); s1=ts; sc = s1; for i = 1:mt−1 sindex = i*2*tsize + 1; spart1 = b(1)*s1(sindex−4) + b(2)*s1(sindex−3)+b(1)*s1(sindex−2) spart2 = b(1)*s1(sindex−2) + b(2)*s1(sindex−1)+b(1)*s1(sindex) spart3 = b(1)*s1(sindex) + b(2)*s1(sindex+1)+b(1)*s1(sindex+2) spart4 = b(1)*s1(sindex+2) + b(2)*s1(sindex+3)+b(1)*s1(sindex+4) sc(i*2*tsize+1) = a(2)*spart1+a(4)*spart2+a(4)*spart3+ a(2)*spart4; end; clear ts ts = zeros(1,mt*tsize); for i=1:mt ts(i*tsize) = sc((i−1)*tsize+1); ts((i−1)*tsize+1:i*tsize−1) = sc((i−1)*tsize+2:i*tsize); end function [s,w,p,L] = tiledwtcirc(x,hd,gd,p,L); m = length(x); mt = floor(m/p) wsize =m−m/(2{circumflex over ( )}L); w = zeros(1,wsize); s1 = x; index = 1; tsize = p/2; for j = 1:L for i = 0:mt−1 tsize = floor(p/(2{circumflex over ( )}j)); clear ts tw; [ts,tw] = dwtper(s1(2*tsize*i+1:2*tsize*(i+1)),hd,gd); w(index:index−1+tsize) = tw; s1((i)*tsize+1) = ts(length(ts)); s1((i)*tsize+2:(i+1)*tsize) = ts(1:tsize−1); index = index + tsize; end; s1(mt*tsize+1:m) = 0; end; s = zeros(1,mt*tsize); s = s1(1:mt*tsize); function [xinv,p,L,s2] = tileidwtcirc(w,s,hr,gr,p,L); n = length(s)+length(w) mt = floor(n/p); wsize = length(w); tx = zeros(1,p+L*4); xinv = zeros(1,n); index = wsize; s1 = zeros(1,n); tsize = length(s)/mt; ts = zeros(1,n); ts(1:length(s)) = s; for j = 1:L tsize =p/(2{circumflex over ( )}(L+1−j)); for i = 1:mt s1(i*tsize) = ts((i−1)*tsize+1); s1((i−1)*tsize+1:i*tsize−1) = ts((i−1)*tsize+2:i*tsize); end; tw = w(index−mt*tsize+1:index); for i = 0:mt−1 tx = idwtper(s1(i*tsize+1:(i+1)*tsize),tw(i*tsize+1:(i+1)*tsize),hr,gr); xinv(i*2*tsize+1:(i+1)*2*tsize) = tx; end; index = index − mt*tsize; s1(1:mt*2*tsize) = xinv(1:mt*2*tsize); ts(1:mt*2*tsize) = s1(1:mt*2*tsize); end; xinv = s1; Copyright 1999-2000 Ricoh Silicon Valley
The filters are normalized such that the coefficients of each lowpass filter sum up to 1/√{square root over (2)}. Columns show the vector of coefficients that have been downsampled and that have to be convolved with the scaling or wavelet coefficients at scale J in order to compute the smooth approximation the column. The position “index” marks the first position to the right of the tile boundary and corresponds to “k” in the example. The indices denoted by “left . . . ” and “right . . . ” denote the coefficients from boundary extensions that are necessary for the first inverse tile transform step. Thus, the steps depicted in FIGS. 2 and 3 may be reduced to the single step of applying a pre-computed filter.
< s ( 2 ) , f [ s ] > + < d ( 2 ) , f [ d ] >= s ~ index 1 where <a,b> means vector inner product of a and b.
n left ( L ) = D + ⌊ n left ( L - 1 ) 2 ⌋ , the number of nright(L) of filters to correct lowpass coefficients right of tile boundary is as follows:
n right ( L ) = D + ⌊ n right ( L - 1 ) 2 ⌋ where nleft(1)=D and nright(1)=D. If forward lowpass filter is of length N=2*(2*D+1)+1, which applies to filters such as the 3,9 wavelet system, then the number nleft(L) of filters to correct lowpass coefficients left of tile boundary is as follows:
n left ( D ) = D + ⌊ n right ( L - 1 ) 2 ⌋ where nleft(1)=D and nright(1)=D+1, and the number nright(L) of filters to correct lowpass coefficients right of tile boundary is as follows:
n right ( D ) = D + ⌊ n left ( L - 1 ) 2 ⌋ where nleft(1)=D and nright(1)=D+1.
1/2F*(−z)[A(−z2)]�(z)
1/2F*(−z)[A(−z 2)]�(z)=T F j *F(z)�(z)
In one embodiment, the binary entropy coder comprises a high speed parallel coder. Both the QM-coder and the FSM coder require that one bit be encoded or decoded at a time. The high-speed parallel coder handles several bits in parallel. In one embodiment, the high speed parallel coder is implemented in VLSI hardware or multi-processor computers without sacrificing compression performance. One embodiment of a high speed parallel coder that may be used in the present invention is described in U.S. Pat. No. 5,381,145, entitled “Method and Apparatus for Parallel Decoding and Encoding of Data”, issued Jan. 10, 1995.
The generation of the transform may be illustrated with an example. Assume a tiled signal x is Tiled X:0 . . . 0|100 . . . 100, where “|” is a boundary and 0,100 are pixel values (chosen arbitrarily), then applying the forward transform results in Tiled S:0 . . . 0|400 . . . 400, and Tiled D:0 . . . 0|0 . . . 0
0 … 0 - 100 16 - 300 16 200 16 | 1400 16 1900 16 1700 16 1600 16 … 1600 16 - This reconstruction has “ringing,” it is “peaky” around the tile boundary.
S : 0 … 0 200 16 600 16 | 1000 16 1400 16 1600 16 … 1600 16 This reconstruction is smooth at the boundary.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5764805 *Oct 23, 1996Jun 9, 1998David Sarnoff Research Center, Inc.Low bit rate video encoder using overlapping block motion compensation and zerotree wavelet codingUS5991454 *Oct 6, 1997Nov 23, 1999Lockheed Martin CoporationData compression for TDOA/DD location systemUS6141446 *Sep 30, 1997Oct 31, 2000Ricoh Company, Ltd.Compression and decompression system with reversible wavelets and lossy reconstructionUS6389074 *Sep 28, 1998May 14, 2002Canon Kabushiki KaishaMethod and apparatus for digital data compressionUS6587588 *Dec 16, 1999Jul 1, 2003At&T Corp.Progressive image decoder for wavelet encoded images in compressed files and method of operationUS6754394 *May 1, 2000Jun 22, 2004Ricoh Company, Ltd.Compression and decompression system with reversible wavelets and lossy reconstructionUS6996281 *Nov 19, 2003Feb 7, 2006Ricoh Co., Ltd.Compression and decompression system with reversible wavelets and lossy reconstruction* Cited by examinerNon-Patent CitationsReference1 *Zakhor, "Iterative Procedure for Reduction of Blocking Effects in Transform Image Coding", IEEE Transactions on Circuits and Systems for Video Technology, Mar. 1992, vol. 2, No. 1, pp. 91-95.* Cited by examinerClassifications U.S. Classification382/240, 382/242, 375/E07.075, 382/233, 375/E07.19, 382/232International ClassificationG06K9/40, H03M7/30, G06K9/36, H04N7/30, H04N7/26Cooperative ClassificationH04N19/48, H04N19/176, H04N19/117, H04N19/467, H04N19/86, H04N19/18, H04N19/63, H04N19/645European ClassificationH04N7/26A8B, H04N7/26C, H04N7/26A8C, H04N7/26H30Q, H04N7/26P4, H04N7/26E10, H04N7/26A4F, H04N7/26H30Legal EventsDateCodeEventDescriptionJan 27, 2011FPAYFee paymentYear of fee payment: 4Mar 13, 2015REMIMaintenance fee reminder mailedJul 31, 2015LAPSLapse for failure to pay maintenance feesSep 22, 2015FPExpired due to failure to pay maintenance feeEffective date: 20150731RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services