BIB DATA SHEET
`
`Page 1 of 1
`
`UNITED STATES DEPARTMENT OF COMMERCE
`United States Patent and Trademark Office
`Address: COMMISSIONER FOR PA TENTS
`P.O. Box 1450
`Alexandria, Virginia 22313-1450
`www.uspto.gov
`
`CONFIRMATION NO. 9199
`
`SERIAL NUMBER
`
`13/083,932
`
`FILING or 371 (c)
`DATE
`04/11/2011
`
`CLASS
`
`375
`
`GROUP ART UNIT ATTORNEY DOCKET
`NO.
`2485
`2011_0589A
`
`RULE
`
`APPLICANTS
`Matthias NARROSCHKE, Langen, GERMANY;
`Hisao Sasai, Osaka, JAPAN;
`** CONTINUING DATA*************************
`** FOREIGN APPLICATIONS *************************
`** IF REQUIRED, FOREIGN FILING LICENSE GRANTED**
`04/21/2011
`
`0 Yes al No
`Foreign Priority claimed
`35 USC 119(a-d) conditions met O Yes al No
`/NEIL R MIKESKN
`Verified and
`Acknowledged
`~xammer's Signature
`
`O Metafter
`Allowance
`
`Initials
`
`STATE OR
`COUNTRY
`
`SHEETS
`DRAWINGS
`
`TOTAL
`CLAIMS
`
`INDEPENDENT
`CLAIMS
`
`GERMANY
`
`12
`
`15
`
`3
`
`ADDRESS
`WENDEROTH, LIND & PONACK L.L.P.
`1030 15th Street, N.W.
`Suite 400 East
`Washington, DC 20005-1503
`UNITED STATES
`TITLE
`ORDER OF DEBLOCKING
`
`FILING FEE FEES: Authority has been given in Paper
`to charge/credit DEPOSIT ACCOUNT
`RECEIVED No.
`for following:
`No.
`1220
`
`lo All Fees
`IO 1.16 Fees (Filing)
`0 1.17 Fees (Processing Ext. of time)
`0 1.18 Fees (Issue)
`0 Other
`0 Credit
`
`I
`
`I
`
`BIB (Rev. 05/07).
`
`SAMSUNG EXHIBIT 1071
`Samsung Electronics Co., Ltd. v. M & K Holdings, Inc.
`IPR2018-00697
`
`Page 1 of 312
`
`

`

`Electronic Acknowledgement Receipt
`
`EFSID:
`
`Application Number:
`
`9851592
`
`13083932
`
`International Application Number:
`
`Confirmation Number:
`
`9199
`
`Title of Invention:
`
`ORDER OF DEBLOCKING
`
`First Named Inventor/Applicant Name:
`
`Matthias NARROSCHKE
`
`Customer Number:
`
`52349
`
`Filer:
`
`W. Douglas Hahm/pam veazey
`
`Filer Authorized By:
`
`W. Douglas Hahm
`
`Attorney Docket Number:
`
`2011_0589A
`
`Receipt Date:
`
`11-APR-2011
`
`Filing Date:
`
`Time Stamp:
`
`15:16:20
`
`Application Type:
`
`Utility under 35 USC 111 (a)
`
`Payment information:
`
`Submitted with Payment
`
`Payment Type
`
`Payment was successfully received in RAM
`
`RAM confirmation Number
`
`Deposit Account
`
`Authorized User
`
`yes
`
`Credit Card
`
`$1090
`
`1777
`
`230975
`
`HAHM,W DOUGLAS
`
`The Director of the USPTO is hereby authorized to charge indicated fees and credit any overpayment as follows:
`
`Charge any Additional Fees required under 37 C.F.R. Section 1.16 (National application filing, search, and examination fees)
`
`Charge any Additional Fees required under 37 C.F.R. Section 1.17 (Patent application and reexamination processing fees)
`
`Page 2 of 312
`
`

`

`Charge any Additional Fees required under 37 C.F.R. Section 1.19 (Document supply fees)
`
`Charge any Additional Fees required under 37 C.F.R. Section 1.20 (Post Issuance fees)
`
`Charge any Additional Fees required under 37 C.F.R. Section 1 .21 (Miscellaneous fees and charges)
`
`File Listing:
`
`Document
`Number
`
`Document Description
`
`File Name
`
`File Size(Bytes)/
`Message Digest
`
`Multi
`Part /.zip
`
`Pages
`(if appl.)
`
`237046
`
`1
`
`Transmittal of New Application
`
`ATTACHA.pdf
`
`no
`
`1
`
`b 167a90fa0627fedf19463b33e4790ee9df9
`10ab
`
`Warnings:
`
`The PDF file has been signed with a digital signature and the legal effect of the document will be based on the contents of the file not the
`digital signature.
`
`Information:
`
`2
`
`ATTACHB.pdf
`
`yes
`
`42
`
`905869
`
`56a8e 13869302912b719c0447 eca370f%9
`5245d
`
`Multipart Description/PDF files in .zip description
`
`Document Description
`
`Start
`
`End
`
`Specification
`
`Claims
`
`Abstract
`
`Drawings-only black and white line drawings
`
`Warnings:
`
`1
`
`24
`
`30
`
`31
`
`23
`
`29
`
`30
`
`42
`
`The page size in the PDF is too large. The pages should be 8.5 x 11 or A4. If this PDF is submitted, the pages will be resized upon entry into the
`Image File Wrapper and may affect subsequent processing
`
`The PDF file has been signed with a digital signature and the legal effect of the document will be based on the contents of the file not the
`digital signature.
`
`Information:
`
`3
`
`Oath or Declaration filed
`
`ATTACHC.pdf
`
`no
`
`3
`
`129838
`
`ca42520b06cc6a2e011 c72e87221227e870
`3936a
`
`Warnings:
`
`The PDF file has been signed with a digital signature and the legal effect of the document will be based on the contents of the file not the
`digital signature.
`
`Information:
`
`4
`
`Fee Worksheet (PTO-875)
`
`fee-info.pdf
`
`no
`
`2
`
`33037
`
`de9122203Sb2b6a39dbd9a29ac6a9c94bffC
`4743
`
`Warnings:
`
`Information:
`
`Page 3 of 312
`
`

`

`,------- -
`
`Total Files Size (in bytes)
`
`1305790
`
`This Acknowledgement Receipt evidences receipt on the noted date by the USPTO of the indicated documents,
`characterized by the applicant, and including page counts, where applicable. It serves as evidence of receipt similar to a
`Post Card, as described in MPEP 503.
`
`New Applications Under 35 U.S.C. 111
`If a new application is being filed and the application includes the necessary components for a filing date (see 37 CFR
`1.53(b)-(d) and MPEP 506), a Filing Receipt (37 CFR 1.54) will be issued in due course and the date shown on this
`Acknowledgement Receipt will establish the filing date of the application.
`
`National Stage of an International Application under 35 U.S.C. 371
`If a timely submission to enter the national stage of an international application is compliant with the conditions of 35
`U.S.C. 371 and other applicable requirements a Form PCT /DO/EO/903 indicating acceptance of the application as a
`national stage submission under 35 U.S.C. 371 will be issued in addition to the Filing Receipt, in due course.
`
`New International Application Filed with the USPTO as a Receiving Office
`If a new international application is being filed and the international application includes the necessary components for
`an international filing date (see PCT Article 11 and MPEP 181 O), a Notification of the International Application Number
`and of the International Filing Date (Form PCT/RO/1 OS) will be issued in due course, subject to prescriptions concerning
`national security, and the date shown on this Acknowledgement Receipt will establish the international filing date of
`the application.
`
`Page 4 of 312
`
`

`

`Electronic Patent Application Fee Transmittal
`
`Application Number:
`
`Filing Date:
`
`Title of Invention:
`
`ORDER OF DEBLOCKING
`
`First Named Inventor/Applicant Name:
`
`Matthias NARROSCHKE
`
`Filer:
`
`W. Douglas Hahm/patricia hill
`
`Attorney Docket Number:
`
`2011_0589A
`
`Filed as Large Entity
`
`Utility under 35 USC 111 (a) Filing Fees
`
`Description
`
`Fee Code
`
`Quantity
`
`Amount
`
`Sub-Total in
`USO($)
`
`Basic Filing:
`
`Utility application filing
`
`Utility Search Fee
`
`Utility Examination Fee
`
`1011
`
`1111
`
`1311
`
`1
`
`1
`
`1
`
`330
`
`540
`
`220
`
`330
`
`540
`
`220
`
`Pages:
`
`Claims:
`
`Miscellaneous-Filing:
`
`Petition:
`
`Patent-Appeals-and-Interference:
`
`Page 5 of 312
`
`

`

`Description
`
`Fee Code
`
`Quantity
`
`Amount
`
`Sub-Total in
`USO($)
`
`Post-Allowance-and-Post-Issuance:
`
`Extension-of-Time:
`
`Miscellaneous:
`
`Total in USD ($ )
`
`1090
`
`Page 6 of 312
`
`

`

`Modified PTO/SB/05 (08/2008)
`Patent and Trademark Office: U.S. DEPARTMENT OF COMMERCE
`Under the Paperwork Reduction Act of 1994 no persons are required to respond to a collection of information unless it displays a valid 0MB control number.
`
`UTILITY
`PA TENT APPLICATION
`TRANSMITTAL
`(Only.for new nonprovisional applications under 37 CFR l.53(b)
`
`Attorney Docket No.: 2011_0589A
`
`First Named Inventor: Dr. Matthias NARROSCHKE et al.
`
`Title: ORDER OF DEBLOCKING
`
`Express Mail Label No.:
`
`APPLICATION ELEMENTS
`See JfPEP chapter 600 concerning utility patent application contents.
`
`ADDRESS TO:
`
`Commissioner for Patents
`P.O. Box 1450
`Alexandria, VA 22313-1450
`
`I. []
`
`Fee Transmittal Form
`
`ACCOMPANYING APPLICATION PARTS
`
`2. []
`
`Small Entity Status is hereby asse1ied.
`
`3. [X]
`
`[Total Pages: 30}
`Specification
`Both the claims and abstract must start on a new page
`(For information on the preferred arrangement, see MPEP 608.01 (a))
`
`4. [X] Drawing(s) (35 USC 113)(Figs. 1-12) [Total Sheets: 12]
`
`5. [X] Oath or Declaration
`[Total Pages: 3}
`a. I. [] Newly executed (original or copy)
`a.2. [Xl Unexecuted
`[] Copy from a prior application (37 CFR l .63(d))
`h.
`(/or ,·on1inua1io111di,·isio11al H'ith Box I 8 completed)
`i. l] DELETION OF INVENTOR(S)
`Signed statement attached deleting inventor(s) named in the
`prior application. see 37 CFR l.63(d)(2) and l.33(b).
`
`6. []
`
`Application Data Sheet (see 37 CFR 1.76)
`
`7. []
`
`8. []
`
`CD-ROM or CD-R in duplicate, large table or computer program
`(Appendix)
`
`Nucleotide and/or Ami.no Acid Sequence Submission
`(if applicable. all necessa,y)
`a. []
`Computer Readable Fonn
`h. Specification Sequence Listing on:
`CD-ROM or CD-R (2 copies); or
`1.
`[]
`ii. []
`Paper
`The paper and computer readable copies are identical
`
`c. []
`
`9. [] Assignment Papers (cover sheet & document(s))
`Name of Assignee:
`
`10. []
`
`37 CFR 3.73(b) Statement
`( when there is an assignee)
`[]
`Power of Attorney
`
`11. []
`
`English Translation Document
`(if applicable)
`
`12. []
`
`Infonnation Disclosure Statement (IDS)/PTO-SB/08
`[]
`Copies of IDS Citations
`
`13. []
`
`Preliminary Amendment
`
`14. [] Return Receipt Postcard (MPEP 503)
`(Should be specifically itemized)
`
`15. [] Certified Copy of Priority Document( s)
`(if foreign priority is claimed)
`
`16. [] Non-Publication Request and Certification
`under 35 U.S.C. 122 (b)(2)(B)(i).
`Applicant must attach form PTO/SB/35 or its equivalent.
`
`1 7. [] Other
`
`18. If a CONTINUING APPLICATION, check appropriate box, and supply the requisite information below, and in a preliminary amendment, or in an
`Application Data Sheet :
`[] Continuation
`
`[] Continuation-in-part (CIP)
`
`of prior application No.
`
`[] Divisional
`
`Prior Application Information: Examiner:
`
`Group Art Unit:
`
`For CONTINUATION OR DIVISIONAL APPS only: The entire disclosure of the prior application, from which an oath or declaration is supplied under Box 5b, is
`considered a pmt of the disclosure of the accompanying continuation or divisional application and is hereby incorporated by reference therein. The incorporation can only
`be relied upon when a po1tion has been inadve1tently omitted from the submitted application parts.
`19. CORRESPONDENCE ADDRESS
`
`/W. Douglas Hahm/
`2011.04.11 14:38:55 -04'00'
`
`CUSTOMER NO.
`
`52349
`
`By:
`
`W. Douglas Hahm
`Registration No. 44,142
`
`WENDEROTH, LIND & PONACK, L.L.P.
`1030 15th Street, N.W., Suite 400 East
`Washington, D.C. 20005-1503
`Phone:(202) 721-8200
`Fax:(202) 721-8250
`
`April 11,2011
`
`The USPTO is hereby authorized to charge a11y fees under 37 C.F.R. §§ 1.16, 1.17, and 1.492, which may be required by this paper a11dfor the entire pe11dency of
`the present application to Deposit Account No. 23-0975, except fees for multiple dependent claims.
`
`Page 7 of 312
`
`

`

`1
`
`Order of Deblocking
`
`FIELD OF THE INVENTION
`
`The present invention relates to block-based video coding, in particular to methods
`
`for removing blocking artifacts in reconstructed video images.
`
`BACKGROUND OF THE INVENTION
`
`For the compression of video data, a plurality of video encoding standards has been
`developed. Such video standards are, for instance, ITU-T standards denoted with
`H.26x and 1SO/IEC standards denoted with MPEG-x. The most up-to-date and
`
`advanced video encoding standard
`
`is currently
`
`the standard denoted as
`
`H.264/MPEG-4 AVC (Advanced Video Coding).
`
`As a successor to H.264/MPEG-4 AVC, High Efficiency Video Coding (HEVC) is
`
`currently under joint development by the 1SO/IEC Moving Picture Experts Group
`(MPEG) and ITU-T Video Coding Experts Group (VCEG). The new video standard
`
`HEVC will further improve coding efficiency as compared to AVC High Profile, i.e.
`
`reduce bitrate requirements by half with comparable image quality, probably at the
`expense of increased computational complexity. Depending on the application
`
`requirements, HEVC will be able to trade off computational complexity, compression
`
`rate, robustness to errors and processing delay time.
`
`Both H.264/MPEG-4 AVC and HEVC are based on hybrid video coding, which
`
`consists of the following main stages:
`
`GR0NECKER · KINKELDEY · STOCKMAIR & SCHWANHAUSSER
`
`Page 8 of 312
`
`

`

`2
`
`Dividing each individual video frame into two-dimensional blocks of pixels in
`(a)
`order to subject each video frame to data compression at a block level.
`
`Decorrelating spatiotemporal video information by applying a spatio-temporal
`(b)
`prediction scheme to each block and by transforming the prediction error from the
`
`spatial domain into the frequency domain so as to obtain coefficients.
`
`(c)
`
`Reducing the overall amount of data by quantizing the resulting coefficients.
`
`Compressing the remaining data by encoding the quantized coefficients and
`(d)
`prediction parameters by means of an entropy coding algorithm.
`
`Hence, state-of-the-art video standards employ a Differential Pulse Code
`Modulation (DPCM) approach which only transmits differences between blocks of
`an input video sequence and their predictions based on previously encoded blocks
`
`("the locally decoded image"). One of the prediction schemes that may be employed
`by these video coding standards is motion compensated prediction.
`In
`this
`prediction scheme, at least one motion vector is determined for each block of video
`data in order to describe image displacements caused be object and/or camera
`
`movements. Based on the motion vectors determined, the image content of one
`block may be predicted at least to a certain extend from the image content of
`previously coded blocks. The difference between the predicted and the actual input
`image content is called the prediction error, which is then encoded together with the
`
`motion vectors rather than the actual input image content. In this manner, a
`substantial reduction in the amount of information to be coded can be achieved for
`most "natural" video sequences.
`
`Figure 1 is an exemplary block diagram of a conventional video encoder, which is in
`accordance with the emerging High Efficiency Video coding (HEVC) standard, as
`well as with the established H.264 / AVC standard. The video encoder, generally
`
`GR0NECKER · KINKELDEY · STOCKMAIR & SCHWANHAUSSER
`
`Page 9 of 312
`
`

`

`3
`
`denoted by reference numeral 100, comprises a subtractor 110 for determining
`
`differences between a current block of a video image (input signal) and a prediction
`signal of the current block which is based on previously encoded blocks ("the locally
`decoded image") stored in the reference frame memory 150. The reference frame
`memory 150 thus operates as a delay unit that allows a comparison between
`
`current signal values and a prediction signal generated by prediction unit 155 from
`previous signal values. A transform unit 115 and a quantization unit 120 transforms
`the resulting prediction error from the spatial domain to the frequency domain and
`
`quantizes the obtained coefficients in accordance with a quantization parameter
`provided by controller 160. An entropy coding unit 170 entropy encodes the
`
`quantized coefficients and the quantization parameter.
`
`The locally decoded image is provided by a decoding unit incorporated into video
`
`encoder 100. The decoding unit performs the encoding steps in reverse manner.
`An inverse transform unit 125 applies an inverse transformation to the quantized
`
`coefficients.
`In adder 130, the decoded differences are added to the prediction
`signal to form the locally decoded image.
`
`Due to the quantization, quantization noise is superposed to the reconstructed video
`
`signal. Due to the blockwise coding, the superposed noise often has a blocking
`characteristic, which may be subjectively annoying. In order to reduce the blocking
`
`characteristic, a deblocking filter 135 is applied to the reconstructed signal, which is
`the sum of the prediction signal and the quantized prediction error signal.
`
`The deblocked signal is the decoded signal, which is generally displayed. The
`deblocking filter in H.264/AVC, as well as in HEVC, has the capability of local
`adaptation. In the case of a high degree of blocking noise, a strong low pass filter is
`applied whereas for a low degree of blocking noise, a weak low pass filter is
`
`applied. The strength of the low pass filter is determined by the prediction and by
`
`GRONECKER . KINKELDEY · STOCKMAIR & SCHWANHAUSSER
`
`Page 10 of 312
`
`

`

`4
`
`the quantized prediction error signal. This deblocking filter has the following two
`
`benefits:
`
`1. Block edges are smoothed resulting in an improved subjective quality of
`
`decoded images.
`
`2. Since the filtered macroblock is used for the motion-compensated prediction
`
`of further images, the filtering may result in smaller prediction errors and thus
`
`in improved coding efficiency.
`
`As an example for deblocking at a vertical block boundary, a linear deblocking filter
`
`with four coefficients is provided. This filter is applied to input samples P2, P1, Po, qo,
`
`q1 and q2, wherein Po and qo are two adjacent pixels at the block boundary, P1 and
`
`q1 pixels adjacent to Po and qo, and so on. The filter output Po.new and qo,new is then
`
`defined as Po.new= (P2- (P1 << 1) +(Po+ qo + 1) >> 1) >> 1 and qo,new = (q2- (q1 <<
`
`1) + (Qo + Po + 1) >> 1) >> 1. Further details on the conventional deblocking filter
`
`process can be found in the document "WD3: Working Draft 3 of High-Efficiency
`
`Video Coding" by Thomas Wiegand, Woo-Jin Han, Benjamin Bross, Jens-Rainer
`
`Ohm, and Gary J. Sullivan (JCTVC-E603, Joint Collaborative Team on Video
`
`Coding (JCT-VC) of ITU-T SG16 WP3 and 1SO/IEC JTC1/SC29/WG11, Geneva,
`
`CH, 16-23 March, 2011 ), which is incorporated herewith in its entirety.
`
`For reconstructing the encoded images at the decoder side, the encoding process is
`
`applied in reverse manner. A schematic block diagram, illustrating the configuration
`
`of the corresponding decoder, is shown in Fig. 2.
`
`In decoder 200 of Fig. 2, first the entropy encoding of coefficients is reversed in an
`
`entropy decoding unit 210. The decoded block of quantized coefficients is then
`
`submitted to an inverse transform unit 220. The result of the inverse transform is the
`
`quantized prediction error in the spatial domain, which is added by adder 230 to the
`
`GRONECKER · KINKELDEY · STOCKMAIR & SCHWANHAUSSER
`
`Page 11 of 312
`
`

`

`5
`
`prediction signal stemming from the prediction unit 255. The reconstructed image is
`
`passed through a deblocking filter 235 and the resulting decoded signal is stored in
`reference frame buffer 250 to be provided to prediction unit 255.
`
`Figure 3 is a schematic illustration of a frame 300 of video data divided into a
`plurality of blocks 310 denoted as largest coding units (LCUs) according to HEVC.
`
`The numbers indicate the processing order of the LCUs: According to HEVC, the
`
`individual LC Us of a frame of video data are processed line-by-line, starting with the
`
`top-most LCU to the left.
`
`The size of an LCU may vary, for example, from 8x8 pixels to 64x64 pixels. Each
`LCU may be further divided into independently encoded sub-blocks denoted as
`coding units (CUs). An example of an LCU 400 divided into 16 distinct CUs 410 is
`shown in Fig. 4. The numbers indicate the order in which the individual CUs 410 are
`
`encoded and decoded (Z-scan).
`
`Each of the individual CUs may be encoded with a different quantization parameter,
`different prediction method, and different prediction parameters. This may lead to
`disturbing blocking artifacts at the edges of the CUs. These artifacts are reduced by
`applying a deblocking filter at each of the various horizontal and vertical edges, as
`
`explained above.
`
`This is further illustrated in Fig. 5, which shows an exemplary 16x16 CU. A CU with
`
`16x16 pixels may be further subdivided into 4 blocks of 8x8 pixels each, which may
`be coded by different coding parameters. This leads to a total of four vertical edges
`v1, v2, V3, V4 and four horizontal edges h1, h2, h3, h4, which are considered during
`deb locking for each 16x16 CU. The smallest block size considered during
`
`deblocking is 8x8, i.e., edges of less than 8 pixels length are neglected.
`
`Specifically, the following deblocking steps are performed in the stated order:
`
`GRUNECKER · KINKELDEY · STOCKMAIR & SCHWANHAUSSER
`
`Page 12 of 312
`
`

`

`6
`
`1. For all vertical edges vi of current CU: decide whether edge vi has to be
`filtered or not
`
`2.
`
`If so, apply vertical deblocking filter to edge Vi
`
`3. For all horizontal edges of current CU: decide whether edge hi has to be
`filtered or not
`
`4.
`
`If so, apply horizontal deblocking filter to edge hi
`
`The sequence of steps performed during conventional ( de-)coding and deb locking
`
`is illustrated in Figs. 6A to 6D. Each of Figs. 6A-6D shows (part of) a frame 600 of
`video data consisting of six exemplary CUs 610, 620 of 8x8 pixels each. Previously
`
`decoded pixels are indicated by filled circles, pixels that are currently decoded are
`indicated by open circles.
`
`In the first step illustrated in Fig. 6A, the left vertical edge of a current CU 620 is
`
`subjected to deblocking by applying a horizontal deblocking filter to each set 630 of
`In the second
`eight horizontally arranged pixels, as indicated by the broken lines.
`step illustrated in Fig. 6B, the upper edge of the current CU 620 is subjected to
`
`deblocking by applying a vertical deblocking filter to each set 640 of eight vertically
`
`arranged pixels, as indicated by the broken lines.
`
`These steps are repeated when the next CU is decoded. In Fig. 6C, the left vertical
`edge of the current CU 620 is subjected to deblocking by applying a horizontal
`deblocking filter to each set 630 of eight horizontally arranged pixels, as indicated
`
`by the broken lines. Subsequently, the upper edge of the current CU 620 is
`subjected to deblocking by applying a vertical deblocking filter to each set 640 of
`eight vertically arranged pixels, as illustrated by broken lines in Fig. 6D.
`
`GR0NECKER · KINKELDEY · STOCKMAIR & SCHWANHAUSSER
`
`Page 13 of 312
`
`

`

`7
`
`In this manner, all edges of all coding units will be subjected to deblocking filtering
`as decoding progresses.
`
`The problem with this approach, however, is that there are many dependencies
`between the individual steps that impede an efficient implementation both in
`hardware and in software. For instance, deblocking of a vertical edge can only be
`performed if the previous CU, i.e., the block to the left of the edge, has already been
`decoded; the next CU, on the other hand, can only be decoded when deblocking of
`the current block is completed. Moreover, deblocking of a horizontal edge can only
`
`be performed after deblocking of nearby vertical edges has been completed since
`there are always pixels in the corners of a coding unit that are affected by both
`horizontal and vertical deblocking.
`
`SUMMARY OF THE INVENTION
`
`Therefore, it is an object of the present invention to provide an improved deblocking
`method that allows for a more efficient hardware and software implementation.
`
`Specifically, it is an object of the present invention to provide a deblocking method
`that lends itself to parallel processing.
`
`This is achieved by the features as set forth in the independent claims.
`
`Preferred embodiments are the subject matter of dependent claims.
`
`It is the particular approach of the present invention to perform deblocking filtering
`of all horizontal edges of a given frame in a first step and to perform deblocking
`
`filtering of all vertical edges of said frame in a second step, or vice versa. In this
`manner, the application of the individual horizontal or vertical deblocking filters in
`
`GRONECKER · KINKELDEY · STOCKMAIR & SCHWANHAUSSER
`
`Page 14 of 312
`
`

`

`8
`
`the first or the second step can be performed independently of each other. This
`
`allows for a more efficient implementation, both in software that is adapted for state(cid:173)
`
`of-the-art multicore processors and in hardware with multiple processing pipelines.
`
`According to a first aspect of the present invention, a method for deblocking video
`data is provided. The method comprises the steps of receiving a frame of video data
`
`consisting of a plurality of blocks, each block consisting of a plurality of pixels;
`applying a horizontal deblocking filter to each vertical edge between two horizontally
`
`adjacent blocks of video data; and applying a vertical deblocking filter to each
`
`horizontal edge between two vertically adjacent blocks of video data, wherein either
`the horizontal deblocking filter is applied to all vertical edges before the vertical
`
`deblocking filter is applied to a horizontal edge, or the vertical deblocking filter is
`applied to all horizontal edges before the horizontal deblocking filter is applied to a
`vertical edge.
`
`Preferably, a size of the blocks and a support (i.e., the set of pixels that are taken
`into account for the filtering) of the vertical deblocking filter are adapted such that
`each pixel of the plurality of blocks is affected by at most one application of the
`vertical deblocking filter, so that the steps of applying the vertical deblocking filter
`
`are independent of each other. Further, a size of the blocks and a support of the
`horizontal deblocking filter are preferably adapted such that each pixel of the
`plurality of blocks is affected by at most one application of the horizontal deblocking
`filter, so that the steps of applying the horizontal deblocking filter are independent of
`
`each other. In this manner, the application of deblocking filters on different edges do
`not affect each other and the corresponding processes may be performed parallel to
`each other.
`
`Specifically, the steps of applying the vertical and/or the horizontal deblocking filter
`are performed parallel to each other, which results in a reduction of overall
`processing time.
`
`GR0NECKER · KINKELDEY · STOCKMAIR & SCHWANHAUSSER
`
`Page 15 of 312
`
`

`

`9
`
`According to a second aspect of the present invention, a method for decoding video
`data is provided. The method comprises the steps of receiving compressed video
`data comprising prediction error data; for each block of a frame of video data,
`predicting said block from previously decoded video data; reconstructing the frame
`of video data by adding the prediction error data to the predicted blocks; and
`deblocking the reconstructed frame of video data with a method according to the
`first aspect of the present invention.
`
`According to a third aspect of the present invention, a method for encoding video
`data is provided. The method comprises the steps of receiving video data;
`predicting video data from previously encoded video data; computing prediction
`error data indicating a difference between the received video data and the predicted
`video data; and encoding the prediction error data, wherein the predicting step
`further comprises the step of generating locally decoded video data by decoding the
`previously encoded video data with a method according to the second aspect of the
`present invention.
`
`According to a fourth aspect of the present invention, a video decoder for decoding
`compressed video data comprising prediction error data is provided. The video
`decoder comprises a prediction unit configured for predicting video data from
`previously decoded video data; an adder for obtaining reconstructed video data by
`adding the prediction error data to the predicted video data; a buffer memory for
`storing a frame of reconstructed video data consisting of a plurality of blocks, each
`block consisting of a plurality of pixels; a first filter unit configured for applying a
`horizontal deblocking filter to each vertical edge between two horizontally adjacent
`blocks of video data; and a second filter unit configured for applying a vertical
`deblocking filter to each horizontal edge between two vertically adjacent blocks of
`video data; wherein either the horizontal deblocking filter is applied to all vertical
`edges before the vertical deblocking filter is applied to a horizontal edge, or the
`vertical deblocking filter is applied to all horizontal edges before the horizontal
`deblocking filter is applied to a vertical edge.
`
`GR0NECKER · KINKELDEY · STOCKMAIR & SCHWANHAUSSER
`
`Page 16 of 312
`
`

`

`10
`
`Finally, according to a fifth aspect of the present invention, a video encoder for
`encoding input video data is provided. The video data encoder comprises a
`predicting unit configured for predicting video data from previously encoded video
`data; a computing unit configured for computing prediction error data indicating a
`difference between the input video data and the predicted video data; an encoding
`unit configured for encoding the prediction error data, wherein the predicting unit
`further comprises a video decoder according to the fourth aspect of the present
`invention for generating locally decoded video data by decoding the previously
`encoded video data.
`
`The above and other objects and features of the present invention will become
`more apparent from the following description and preferred embodiments given in
`conjunction with the accompanying drawings, in which:
`
`Fig. 1
`
`is an exemplary block diagram of a conventional video encoder;
`
`Fig. 2
`
`is an exemplary block diagram of a conventional video decoder;
`
`Fig. 3
`
`is an illustration of the conventional processing order in a frame with a
`plurality of LCUs;
`
`Fig. 4
`
`is an illustration of the conventional processing order in an LCU with a
`plurality of CUs;
`
`Fig. 5
`
`is an illustration of the edges within a CU that are considered during
`deblocking;
`
`illustration of the steps performed during decoding and
`Figs. 6A-6D is an
`deblocking according to a conventional method;
`
`GR0NECKER. KINKELDEY · STOCKMAIR & SCHWANHAUSSER
`
`Page 17 of 312
`
`

`

`11
`
`illustration of the steps performed during decoding and
`Figs. 7 A-7B is an
`deblocking according to the present invention;
`
`Fig. 8
`
`is an illustration of a recording medium for storing a program realizing any
`of the embodiments of the present invention by means of a computer
`system;
`
`Fig. 9
`
`is a block diagram showing an overall configuration of a content supply
`system for realizing a content distribution service using the coding and
`decoding approach of the present invention;
`
`Fig. 10 is a schematic drawing showing a cell phone for using the video/audio
`coding approach of the present invention;
`
`Fig. 11
`
`is a block diagram illustrating the functional blocks of the cell phone
`exemplified in Figure 1 O; and
`
`Fig. 12 is illustrating a wireless digital system for incorporating the coding and
`decoding approach of the present invention.
`
`DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
`
`According to the present invention, deblocking is no longer performed on a block(cid:173)
`by-block basis but in batch mode for an entire frame. Moreover, the processes of
`decoding, horizontal deblocking, and vertical deblocking are disentangled in the
`sense that, in a first step, a plurality of blocks is decoded, which are then
`simultaneously subjected to horizontal deblocking in a second step. After horizontal
`deblocking is completed, all blocks are subjected to vertical deblocking in a third
`
`GRUNECKER · KINKELDEY · STOCKMAIR & SCHWANHAUSSER
`
`Page 18 of 312
`
`

`

`12
`
`step. Obviously, the sequence of the horizontal deblocking and
`deblocking may be exchanged.
`
`the vertical
`
`In this manner, the dependencies between the individual steps are substantially
`reduced, allowing for highly efficient implementation on concurrent computing
`systems.
`
`Figure 7 A schematically illustrates a frame 700 of video data, consisting of a
`plurality of coding units 710 with 8x8 pixels each. In a first step, pixel data has been
`
`decoded for each of said coding units (open circles). In a second step, all vertical
`edges within the plurality of coding units are subjected to horizontal deblocking. The
`
`support (i.e., the set of pixels that are taken into account for the filtering) of the
`
`horizontal deblocking filter, which is illustrated by a broken line in Fig. 7 A, comprises
`
`eight pixels arranged on a horizontal line, namely four pixels to the left of the edge
`and four pixels to the right of the edge. As it is apparent from Fig. 7 A, the support of
`
`the deblocking filter does not overlap when applied to different edges. Therefore,
`application of the deblocking filter to one edge does not interfere with the application
`
`of the deblocking filter to another edge. Consequently, the step of performing
`
`deblocking of vertical edges can be split into up to N concurrent processes, wherein
`N is the number of vertical edges times the length of the