US5978031A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for determining an optimum grid for use in a block-based video signal coding system
Assignee: Quarterhill Inc
•
Filing: 1997-04-14
•
Granted: 1999-11-02
•
Expires: 2017-04-14
Abstract
Abstract A method, for use in a block based video signal coding system, for determining a search grid by dividing a video object plane of an object into a plurality of equal-sized search blocks, generates a plurality of search grids, each of the search grids being relatively shifted from its adjacent search gird by a predetermined spacing, and detects edge blocks included in each search grid. Then, the method selects a search grid based on the number of the edge blocks and the pixel values in the edge blocks.
Inventors
- 👤 Jin-Hun Kim
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 10:57
CPC Classifications
H; H04; H04N; H04N19/00; H04N19/10; H04N19/169; H04N19/17; H04N19/102; H04N19/119; H04N19/134; H04N19/136; H04N19/14; H04N19/176; H04N19/20
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
260 words
A method, for use in a block-based video signal coding system, for determining an optimum search grid which divides a video object plane of a video signal of an object into a plurality of equal-sized search blocks, each of the search blocks having N×N pixels with N being a positive integer, which comprises the steps of: (a) generating a plurality of search grids, wherein each of the search grids is relatively shifted from an adjacent search grid by a predetermined spacing; (b) detecting edge blocks included in each search grid, wherein an edge block represents a search block having a portion of the boundary of the object, by using shape information of the object; and (c) selecting a search grid based on the number of the edge blocks and the pixel values in the edge blocks to determine the selected search grid as the optimum search grid, wherein said step (c) includes the steps of: (c1) choosing search grids having a minimum of the edge blocks; (c2) calculating, if a multiplicity of search grids have a same minimum number of the edge blocks, a mean activity value for each of the multiplicity of search grids based on the pixel values of the edge blocks included in said each of the multiplicity of search grids, wherein the mean activity value represents a degree of dispersion among the pixel values of the edge blocks; (c3) detecting a search grid having a minimum mean activity value among the multiplicity of search grids; and (c4)determining the detected search grid as the optimum search grid.
Claim 2
Independent Claim
260 words
A method, for use in a block-based video signal coding system, for determining an optimum search grid which divides a video object plane of a video signal of an object into a plurality of equal-sized search blocks, each of the search blocks having N×N pixels with N being a positive integer, which comprises the steps of: (a) generating a plurality of search grids, wherein each of the search grids is relatively shifted from an adjacent search grid by a predetermined spacing; (b) detecting edge blocks included in each search grid, wherein an edge block represents a search block having a portion of the boundary of the object, by using shape information of the object; and (c) selecting a search grid based on the number of the edge blocks and the pixel values in the edge blocks to determine the selected search grid as the optimum search grid, wherein said step (c) includes the steps of: (c1) choosing search grids having a minimum of the edge blocks; (c2) calculating, if a multiplicity of search grids have a same minimum number of the edge blocks, a mean activity value for each of the multiplicity of search grids based on the pixel values of the edge blocks included in said each of the multiplicity of search grids, wherein the mean activity value represents a degree of dispersion among the pixel values of the edge blocks; (c3) detecting a search grid having a minimum mean activity value among the multiplicity of search grids; and (c4)determining the detected search grid as the optimum search grid.
Claim 3
Dependent Claim
136 words
The method as recited in claim 1, wherein said step (c2) further contains the steps of: (c21) competing an activity value for each edge block in each search grid based on the pixel values of the edge blocks included in said each search grid, wherein each activity value for each edge block is calculated as: ##EQU2## wherein M is the number of N×N pixels within an edge block, H(i,j) represents a pixel value at a pixel location(i,j) in the edge block, m is a mean pixel value of all the pixel values within the edge block and i and j are positive integers no larger than the integer N, respectively; and (c22) averaging all the activity values for all the edge blocks in the search grid to generate a mean activity value for the search grid.
Claim 4
Dependent Claim
22 words
The method as recited in claim 2, wherein each of the search grids is shifted from each other on a pixel-by-pixel basis.
Claim 5
Dependent Claim
18 words
The method as recited in claim 3, wherein the pixel value is a luminance level of a pixel.
Claim 6
Independent Claim
265 words
An apparatus, for use in a block based video signal coding system, for determining an optimum search grid which divides a video object plane of a video signal of an object into a plurality of equal-sized search blocks, each of the search blocks having N×N pixels with N being a positive integer, the apparatus comprising: means for generating a plurality of search grids, wherein each of the search grids is relatively shifted from an adjacent search grid by a predetermined spacing; means for detecting edge blocks included in each search grid, wherein an edge block represents a search block having a portion of the boundary of the object, by using shape information of the object; and means for selecting a search grid based on the number of the edge blocks and the pixel values in the edge blocks to determine the selected search grid as the optimum search grid; wherein said selecting means includes: means for choosing search grids having a minimum number of the edge blocks; means for calculating, if a multiplicity of search grids have a same minimum number of the edge blocks, a mean activity value for each of the multiplicity of search grids based on the pixel values of the edge blocks included in said each of the multiplicity of search grids, wherein the mean activity value represents a degree of dispersion among the pixel values of the edge blocks; means for detecting a search grid having a minimum mean activity value among the multiplicity of search grids; and means for determining the detected search grid as the optimum search grid.
Claim 7
Independent Claim
265 words
An apparatus, for use in a block based video signal coding system, for determining an optimum search grid which divides a video object plane of a video signal of an object into a plurality of equal-sized search blocks, each of the search blocks having N×N pixels with N being a positive integer, the apparatus comprising: means for generating a plurality of search grids, wherein each of the search grids is relatively shifted from an adjacent search grid by a predetermined spacing; means for detecting edge blocks included in each search grid, wherein an edge block represents a search block having a portion of the boundary of the object, by using shape information of the object; and means for selecting a search grid based on the number of the edge blocks and the pixel values in the edge blocks to determine the selected search grid as the optimum search grid; wherein said selecting means includes: means for choosing search grids having a minimum number of the edge blocks; means for calculating, if a multiplicity of search grids have a same minimum number of the edge blocks, a mean activity value for each of the multiplicity of search grids based on the pixel values of the edge blocks included in said each of the multiplicity of search grids, wherein the mean activity value represents a degree of dispersion among the pixel values of the edge blocks; means for detecting a search grid having a minimum mean activity value among the multiplicity of search grids; and means for determining the detected search grid as the optimum search grid.
Claim 8
Dependent Claim
134 words
The apparatus as recited in claim 5, wherein said calculating means contains: means for computing each activity value for each edge block in each search grid based on the pixel values of the edge blocks included in said each search grid, wherein each activity value for each edge block is calculated as: ##EQU3## wherein M is the number of N×N pixels within an edge block, H(i,j) represents the pixel value at a pixel location(i,j) in the edge block, m is a mean pixel value of all the pixel values within the edge block and i and j are positive integers no larger than the integer N, respectively; and means for averaging all the activity values for all the edge blocks in the search grid to generate a mean activity value for the search grid.
Claim 9
Dependent Claim
22 words
The apparatus as recited in claim 6, wherein each of the search grids is shifted from each other on a pixel-by-pixel basis.
Claim 10
Dependent Claim
18 words
The apparatus as recited in claim 7, wherein the pixel value is a luminance level of a pixel.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-01 | 2003-05-03 | 2003-11-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-01 | 2007-05-03 | 2007-11-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-01 | 2011-05-03 | 2011-11-02 | $7700.00 | Window Closed / Lapsed |