Ex Parte Ha et al

Patent Trial and Appeal BoardNov 25, 2013

11171344 (P.T.A.B. Nov. 25, 2013)

UNITED STATES PATENT AND TRADEMARK OFFICE ____________________ BEFORE THE PATENT TRIAL AND APPEAL BOARD ____________________ Ex parte TAE-HYEUN HA and JAE-SEOK KIM ____________________ Appeal 2011-009081 Application 11/171,344 Technology Center 2400 ____________________ Before BRUCE R. WINSOR, MICHAEL J. STRAUSS, and DANIEL N. FISHMAN, Administrative Patent Judges. FISHMAN, Administrative Patent Judge. DECISION ON APPEAL Appeal 2011-009081 Application 11/171,344 2 STATEMENT OF CASE This is an appeal under 35 U.S.C. § 134 from the Final Rejection of claims 1-11. App. Br. 4. We have jurisdiction under 35 U.S.C. § 6(b). An oral hearing was requested and scheduled for November 14, 2013. Appellants waived oral hearing by failing to appear. We affirm. THE INVENTION The invention relates to motion estimation in video encoding/decoding including dividing a current frame into blocks and performing a full search algorithm on blocks sampled from the divided blocks, allocating motion vectors obtained through linear interpolation to non-sampled blocks in the current frame based on a motion vector obtained through the full search, and performing a fast search algorithm using the motion vector obtained through linear interpolation as a search starting point. See generally Abstract. Claims 1 and 6, reproduced below, are illustrative: 1. A method for motion estimation based on hybrid block matching in a video compression system, the method comprising: dividing a current frame into a plurality of blocks and performing a full search algorithm on sampled blocks of the plurality of blocks; allocating a motion vector (iMV) obtained through linear interpolation to non-sampled blocks of the plurality of blocks in the current frame based on motion vectors (fMV) obtained through the performing of the full search algorithm; and Appeal 2011-009081 Application 11/171,344 3 performing a fast search algorithm using the motion vector obtained through the linear interpolation as a search starting point; wherein a search area for the fast search is variably determined with reference to at least motion vectors of neighboring blocks that are nearest to a corresponding block or motion vectors of neighboring blocks of the corresponding block that are obtained through a full search algorithm. 6. The method of claim 5, wherein the search area (SA) is given by SA = MAX { | fMV(a)-iMV(i,j) | , | fMV(b)-iMV(i,j) | , | fMV(c)-iMV(i,j) | , | fMV(d)-iMV(i,j) | }, where (i,j) are spatial coordinates of pixels, iMV(i,j) is a motion vector obtained through the linear interpolation in a block and fMV(a) through fMV(d) are motion vectors obtained by performing the full search algorithm on neighboring blocks of the block. THE REJECTIONS The Examiner provisionally rejected claim 1 on the ground of nonstatutory obviousness-type double patenting over claim 1 of patent application number 11/153,347 (now abandoned). Ans. 4-5. The Examiner provisionally rejected claims 9 and 10 on the ground of nonstatutory obviousness-type double patenting over claim 1 of patent application number 11/153,347 (now abandoned) and Chen (Yen-Kuang Chen et al., Frame-Rate Up-Conversion Using Transmitted True Motion Vectors, IEEE Second Workshop on Multimedia Signal Processing, 622-627 (1998)). Ans. 5-6. The Examiner rejected claims 6 and 7 under 35 U.S.C. § 112, second paragraph. Ans. 6. Appeal 2011-009081 Application 11/171,344 4 The Examiner rejected claims 1, 2, and 8 under 35 U.S.C. § 103(a) as unpatentable over Zaccarin (U.S. Patent No. 5,210,605; issued May 11, 1993) and Tourapis (Alexis M. Tourapis et al., Predictive Motion Vector Field Adaptive Search Technique (PMVFAST) – Enhancing Block Based Motion Estimation, Proceedings of Visual Communication and Image Processing 2001, 883-892 (Dec. 2000)).1 Ans. 6-10. The Examiner rejected claim 3 under 35 U.S.C. § 103(a) as unpatentable over Zaccarin, Tourapis, and Orchard (Michael T. Orchard & Gary J. Sullivan, Overlapped Block Motion Compensation: An Estimation- Theoretic Approach, IEEE Trans. On Image Processing, Vol. 3, No. 5, 693-699 (1994)). Ans. 10-11. The Examiner rejected claims 4 and 5 under 35 U.S.C. § 103(a) as unpatentable over Zaccarin, Tourapis, and Hwang (Jenq-Neng Hwang et al., Dynamic Frame-Skipping In Video Transcoding, IEEE Second Workshop on Multimedia Signal Processing, 616-621 (1998)). Ans. 11-13. The Examiner rejected claims 6 and 7 under 35 U.S.C. § 103(a) as unpatentable over Zaccarin, Tourapis, Hwang, and Dinerstein (U.S. Patent Publication No. 2003/0161400 A1; published Aug. 28, 2003). Ans. 13-14. The Examiner rejected claims 9-11 under 35 U.S.C. § 103(a) as unpatentable over Zaccarin, Tourapis, and Chen. Ans. 14-17. THE OBVIOUSNESS-TYPE DOUBLE-PATENTING REJECTIONS Earlier filed patent application 11/153,347 was abandoned due to failure to respond to a pending office action (see Notice of Abandonment 1 Throughout this opinion, page number references to Tourapis are to the printed pages as they appear in the record. Appeal 2011-009081 Application 11/171,344 5 mailed July 13, 2010). Thus, appeals of the nonstatutory obviousness-type double-patenting rejections are dismissed as moot. THE § 112 REJECTION The Examiner rejects claims 6 and 7 as indefinite arguing that both claims recite determinations of a search area (“SA”) as a function of the absolute values of motion vectors of encoded video frame data. Ans. 6, 17- 18. Specifically, the Examiner contends that “search area is two dimensional (horizontal and vertical) and absolute value is one dimensional.” Ans. 6. Therefore, according to the Examiner, “[t]he absolute value of |fMV(a) - iMV(i,j) | can be interpreted as either absolute of vector (magnitude of a vector) or absolute of vector component (either x or y direction) [such that claims 6 and 7] are indefinite.” Id. Appellants argue that the Specification (e.g., ¶ 0039) and the claims are consistent in referring to an exemplary search area (SA) and the absolute values of motion vectors as one dimensional values. App. Br. 11-12; Reply Br. 5. We agree with Appellants that the Examiner erred. A “search area,” as recited in base claim 1, from which claims 6 and 7 indirectly depend, may be broadly understood to be the actual area to be searched—encompassing both a starting point and a range or extent outward in two dimensions from that starting point. Claims 6 and 7 recite a limitation that requires the variable determination of the search area to include at least one specific parameter given by corresponding specified equations. We find that the skilled artisan would understand claims 6 and 7 to recite determining a parameter of the search area (SA) as a scalar value (a one dimensional value) as a function of the absolute value of the magnitude of various motion Appeal 2011-009081 Application 11/171,344 6 vectors. We find further support for such a claim construction in a technical dictionary definition of “absolute value” as: “[A] norm (written as | |) on a vector space that is calculated as an ordinary Euclidean length without regard to its direction. Also MAGNITUDE.” Academic Press Dictionary of Science and Technology, 8 (1992). In view of the above discussion, we are persuaded that the Examiner erred in rejecting claims 6 and 7 as indefinite under § 112. THE § 103 REJECTIONS The Examiner rejects claim 1 finding that Zaccarin discloses the dividing and allocating steps but fails to disclose the performing step and the variable determination of the search area. Ans. 7-8. The Examiner further finds that Tourapis cures these deficiencies and articulates a reason for combining the references. Ans. 8-9. Appellants argue that the combination fails to teach performing a fast search, allocating a motion vector, and the variable determination of the search area as recited in claim 1. App. Br. 12- 15. ISSUES Appellants’ arguments present us with the following issues: 1. Has the Examiner erred in finding that the combination of Zaccarin and Tourapis teaches or suggests the performing step as recited in claim 1? 2. Has the Examiner erred in finding that the combination of Zaccarin and Tourapis teaches or suggests the allocating step as recited in claim 1? Appeal 2011-009081 Application 11/171,344 7 3. Has the Examiner erred in finding that the combination of Zaccarin and Tourapis teaches or suggests the variable determination of the search area as recited in claim 1? ANALYSIS Issue 1 Appellants argue that Tourapis teaches using a set of predictor motion vectors to increase correlation as distinct from “performing a fast search algorithm using the motion vector obtained through the linear interpolation as a search starting point” as recited in claim 1. App. Br. 13-14. More specifically, Appellants argue that Tourapis “does not indicate that choosing a linear interpolation as a starting point would likewise increase correlation” (emphasis omitted), and further argue that using a linear interpolated motion vector as a search starting point “would frustrate the purpose of Tourapis to increase correlation with the motion vector of the current block.” App. Br. 14. We are unpersuaded that the Examiner erred. The Examiner explains that Tourapis discloses “selecting the best among the motion predictor set including a linear combination of motion vectors of neighboring blocks,” and thus concludes it would be obvious to the skilled artisan “to try a linear interpolation of motion vectors of neighboring blocks as a starting point” as in the combination of Zaccarin (showing linear interpolation of a motion vector) and Tourapis (showing selecting among predictor motion vectors to reduce computation in selecting a starting point for a fast search). Ans. 18-19. We agree. Zaccarin discloses that a motion vector of a block may be generated by interpolating from the motion vectors of neighboring blocks. Zaccarin, col. 19, ll. 41-45. Tourapis Appeal 2011-009081 Application 11/171,344 8 discloses selecting among predictor motion vectors to determine a starting point for a fast search (i.e., the starting position for a “Diamond search”). Tourapis, 2, ll. 1-5 under chapter 2 heading. Such predictor motion vectors may include “the motion vectors of the three spatially adjacent blocks.” Tourapis, 4, l. 8. Further, Tourapis discloses that a larger set of predictor motion vectors may include “several other highly probable candidates.” Tourapis, 4, ll. 10-11. Thus, we find that the predictor motion vector of an adjacent block (a predictor in Tourapis’ set of such predictors) could be an interpolated motion vector (as taught by Zaccarin). We therefore agree with the Examiner’s finding that the combination of Zaccarin and Tourapis teaches or suggests “performing a fast search algorithm using the motion vector obtained through the linear interpolation as a search starting point” as recited in claim 1. Appellants further argue that “the Examiner has not provided any rationale as to how selecting the linear interpolation of motion vectors of neighboring blocks as a starting point reduces the computation required for the adaptive selection of the best motion predictor.” Reply Br. 8. Appellants therefore contend that the Examiner has failed to establish a prima facie case of obviousness. Id. We remain unpersuaded. The Examiner has articulated a reason for the proposed combination based on rational underpinnings (i.e., reducing required computation). KSR Int’l Co. v. Teleflex Inc., 550 U.S. 398, 418 (quoting In re Kahn, 441 F.3d 977, 988 (Fed. Cir. 2006)). Appellants’ argument fails to provide sufficient evidence of error in the Examiner’s reasoning or conclusion. Appeal 2011-009081 Application 11/171,344 9 Issue 2 We are unpersuaded by Appellants’ argument. Appellants specifically argue that “claim 1 is directed to ‘allocating a motion vector obtained through linear interpolation ... based on motion vectors obtained through the performing of the full search algorithm,’ whereas Zaccarin teaches interpolating from motion vectors of neighboring blocks.” App. Br. 14. The Examiner explains that Zaccarin performs a full search for sampled (e.g., “dark” blocks”) and “teaches assigning motion vectors to non-sampled block by the linear interpolation of motion vectors of neighboring sampled- blocks (col. 19, line 41-45).” Ans. 19. We agree. In other words, the motion vector (iMV) for a non-sampled block is determined by interpolation of motion vectors of neighboring sampled blocks for which the motion vectors (fMV) may be determined by a full search. Thus, we find that the combination of Zaccarin and Tourapis teaches or suggests “allocating a motion vector (iMV) obtained through linear interpolation to non-sampled blocks of the plurality of blocks in the current frame based on motion vectors (fMV) obtained through the performing of the full search algorithm” as recited in claim 1. Issue 3 We are unpersuaded by Appellants’ argument. Appellants specifically argue that “Tourapis merely teaches using MPEG-4, SA 15, which implies that the search area examined is (-16 + 15) around the center” and thus contend that Tourapis fails to disclose “a search area for the fast search is variably determined” as recited in claim 1. App. Br. 15. The Examiner explains that under a broad but reasonable interpretation, the Appeal 2011-009081 Application 11/171,344 10 “search area” can be interpreted as the particular area (i.e., location) to be searched as distinct from the range or extent of the search. Ans. 19. The Examiner therefore finds that, although the range of a search in Tourapis may be fixed as a 16x16 range surrounding a starting point, the combination or Zaccarin and Tourapis discloses that “the search area of each block is changed from a block to block, centered at the linear interpolation of motion vectors of neighboring sampled-blocks.” Id. We agree. Appellants further argue that the Examiner’s interpretation of “search area” is inconsistent with the Specification paragraphs 39-41 and thus is unreasonably broad. Reply Br. 8-9. We are unpersuaded. Appellants’ examples of “search area” (SA) discussed at paragraphs 39-41 do not provide a limiting definition. Consistent with the Specification, “search area” may be reasonably understood as encompassing any area of search to be performed by the fast search algorithm. We therefore find the Examiner’s interpretation of “search area” broad but reasonable and not inconsistent with the Specification. Furthermore, Tourapis also discloses selecting a small diamond or large diamond based on a predictor motion vector. Tourapis, 6, ll. 16-22. Thus, Tourapis also discloses varying the search range of a fast search to be performed based on a predictor motion vector. In view of the above discussion, we are not persuaded of error in the Examiner’s rejection of claim 1. Appellants argue that claims 2-11 are allowable for the same reasons as claim 1. App. Br. 15-16. We are therefore unpersuaded of error in the Examiner’s rejections of claims 2-11 for the same reasons as claim 1. Appeal 2011-009081 Application 11/171,344 11 DECISION For the above reasons, the Examiner’s obviousness-type double- patenting rejections are dismissed as moot. For the above reasons, the Examiner’s rejection of claims 6 and 7 under 35 U.S.C. § 112, second paragraph is reversed. For the above reasons, the Examiner’s rejections of claims 1-11 under 35 U.S.C. § 103 are affirmed. No time period for taking any subsequent action in connection with this appeal may be extended under 37 C.F.R. § 1.136(a)(1)(iv) (2010). AFFIRMED msc