Apparatus for encoding a contour of regions contained in a video signal

Claim 1

An apparatus for encoding a contour of regions contained in a video signal, the video signal having a plurality of frames including a current frame and a previous frame, which comprises: first segmentation means for segmenting the previous frame into a number of regions to generate a previous contour; second segmentation means for segmenting the current frame into a number of regions to generate a current contour; means for generating prediction parameters based on the previous and the current contours, and the previous and the current frames; means for constructing a predicted current contour by transforming the previous contour based on the prediction parameters; means for detecting deviation points lying on portions of the predicted current contour that deviate from the current contour, to thereby generate the deviation points and corresponding displacements to the deviation points, wherein each of the displacements represents a minimum distance in a horizontal direction between each of the deviation points and the current contour; means for encoding the deviation points and the displacements together with the prediction parameters; contour reconstruction means for relocating the deviation points based on the displacements and producing a reconstructed current contour from the predicted current contour; means for taking N sample points on each of a plurality of line segments, each line segment joining two neighboring relocated deviation points on the reconstructed current contour, and calculating an error for each of the N sample points on each of the line segments to produce a set of errors for said each of the line segments, wherein the N sample points are equi-spaced on said each of the line segments and each of the errors represents a distance between each of the N sample points and the current contour; means for summing up the set of errors to provide a similarity index; control means for sequentially providing the feature point selection means with one or more grids until a similarity index obtained based on one of said one or more grids becomes smaller than a predetermined threshold value and generating a grid index indicating the grid related to the similarity index smaller than the predetermined threshold value; and means for encoding the grid index; wherein said prediction parameter generation means includes: means for determining a predetermined number of vertex points on the previous contour to generate vertex information representing the positions of the vertex points on the previous contour; means for generating vertex point blocks from the previous frame based on the vertex information, each of the vertex point blocks having a vertex point at the center thereof; means for defining a search region of the current frame and generating a plurality of equal-sized candidate blocks from the search region, each of the candidate blocks is chosen such that its center pixel is a pixel forming a part of the current contour; means for detecting predicted vertex points by performing a block matching algorithm between a vertex point block and each of the plurality of candidate blocks to generate predicted vertex information representing the positions of the predicted vertex points; and means for generating the prediction parameters based on the vertex information and the predicted vertex information, and wherein said deviation point detection means includes: feature point selection means for selecting a number of points from the points on the predicted current contour as feature points by using a grid, wherein the feature points represent intersection points between the grid and the predicted current contour; and means for determining the deviation points among the feature points, lying on portions of the predicted current contour that deviate from the current contour, and calculating the displacements for the deviation points, to thereby produce the deviation points and the corresponding displacements.

Claim 2

An apparatus for encoding a contour of regions contained in a video signal, the video signal having a plurality of frames including a current frame and a previous frame, which comprises: first segmentation means for segmenting the previous frame into a number of regions to generate a previous contour; second segmentation means for segmenting the current frame into a number of regions to generate a current contour; means for generating prediction parameters based on the previous and the current contours, and the previous and the current frames; means for constructing a predicted current contour by transforming the previous contour based on the prediction parameters; means for detecting deviation points lying on portions of the predicted current contour that deviate from the current contour, to thereby generate the deviation points and corresponding displacements to the deviation points, wherein each of the displacements represents a minimum distance in a horizontal direction between each of the deviation points and the current contour; means for encoding the deviation points and the displacements together with the prediction parameters; contour reconstruction means for relocating the deviation points based on the displacements and producing a reconstructed current contour from the predicted current contour; means for taking N sample points on each of a plurality of line segments, each line segment joining two neighboring relocated deviation points on the reconstructed current contour, and calculating an error for each of the N sample points on each of the line segments to produce a set of errors for said each of the line segments, wherein the N sample points are equi-spaced on said each of the line segments and each of the errors represents a distance between each of the N sample points and the current contour; means for summing up the set of errors to provide a similarity index; control means for sequentially providing the feature point selection means with one or more grids until a similarity index obtained based on one of said one or more grids becomes smaller than a predetermined threshold value and generating a grid index indicating the grid related to the similarity index smaller than the predetermined threshold value; and means for encoding the grid index; wherein said prediction parameter generation means includes: means for determining a predetermined number of vertex points on the previous contour to generate vertex information representing the positions of the vertex points on the previous contour; means for generating vertex point blocks from the previous frame based on the vertex information, each of the vertex point blocks having a vertex point at the center thereof; means for defining a search region of the current frame and generating a plurality of equal-sized candidate blocks from the search region, each of the candidate blocks is chosen such that its center pixel is a pixel forming a part of the current contour; means for detecting predicted vertex points by performing a block matching algorithm between a vertex point block and each of the plurality of candidate blocks to generate predicted vertex information representing the positions of the predicted vertex points; and means for generating the prediction parameters based on the vertex information and the predicted vertex information, and wherein said deviation point detection means includes: feature point selection means for selecting a number of points from the points on the predicted current contour as feature points by using a grid, wherein the feature points represent intersection points between the grid and the predicted current contour; and means for determining the deviation points among the feature points, lying on portions of the predicted current contour that deviate from the current contour, and calculating the displacements for the deviation points, to thereby produce the deviation points and the corresponding displacements.

Claim 3

An apparatus for encoding a contour of regions contained in a video signal, the video signal having a plurality of frames including a current frame and a previous frame, which comprises: first segmentation means for segmenting the previous frame into a number of regions to generate a previous contour; second segmentation means for segmenting the current frame into a number of regions to generate a current contour; means for generating prediction parameters based on the previous and the current contours, and the previous and the current frames; means for constructing a predicted current contour by transforming the previous contour based on the prediction parameters; a feature point selection means for selecting a number of points from the points on the predicted current contour as feature points by using a grid, wherein the feature points represent intersection points between the grid and the predicted current contour; means for determining deviation points among the feature points, lying on portions of the predicted current contour that deviate from the current contour, and calculating displacements for the deviation points, wherein each of the displacements represents a minimum distance in a horizontal direction between each of the deviation points and the current contour; means for relocating the deviation points based on the displacements and producing a reconstructed current contour from the predicted current contour; means for taking N sample points on each of a plurality of line segments, each line segment joining two neighboring relocated deviation points on the reconstructed current contour, and calculating an error for each of the N sample points on each of the line segments to produce a set of errors for said each of the line segments, wherein the N sample points are equi-spaced on said each of the line segments and each of the errors represents a distance between each of the N sample points and the current contour; means for summing up the set of errors to provide a similarity index; control means for sequentially providing the feature point selection means with one or more grids until a similarity index obtained based on one of said one or more grids becomes smaller than a predetermined threshold value and generating a grid index indicating the grid related to the similarity index smaller than the predetermined threshold value; and means for encoding the deviation points, the displacements, the prediction parameters, and the grid index.

Claim 4

An apparatus for encoding a contour of regions contained in a video signal, the video signal having a plurality of frames including a current frame and a previous frame, which comprises: first segmentation means for segmenting the previous frame into a number of regions to generate a previous contour; second segmentation means for segmenting the current frame into a number of regions to generate a current contour; means for generating prediction parameters based on the previous and the current contours, and the previous and the current frames; means for constructing a predicted current contour by transforming the previous contour based on the prediction parameters; a feature point selection means for selecting a number of points from the points on the predicted current contour as feature points by using a grid, wherein the feature points represent intersection points between the grid and the predicted current contour; means for determining deviation points among the feature points, lying on portions of the predicted current contour that deviate from the current contour, and calculating displacements for the deviation points, wherein each of the displacements represents a minimum distance in a horizontal direction between each of the deviation points and the current contour; means for relocating the deviation points based on the displacements and producing a reconstructed current contour from the predicted current contour; means for taking N sample points on each of a plurality of line segments, each line segment joining two neighboring relocated deviation points on the reconstructed current contour, and calculating an error for each of the N sample points on each of the line segments to produce a set of errors for said each of the line segments, wherein the N sample points are equi-spaced on said each of the line segments and each of the errors represents a distance between each of the N sample points and the current contour; means for summing up the set of errors to provide a similarity index; control means for sequentially providing the feature point selection means with one or more grids until a similarity index obtained based on one of said one or more grids becomes smaller than a predetermined threshold value and generating a grid index indicating the grid related to the similarity index smaller than the predetermined threshold value; and means for encoding the deviation points, the displacements, the prediction parameters, and the grid index.

Claim 6

An apparatus for encoding a contour of regions contained in a video signal, the video signal having a plurality of frames including a current frame and a previous frame, which comprises: first segmentation means for segmenting the previous frame into a number of regions to generate a previous contour; second segmentation means for segmenting the current frame into a number of regions to generate a current contour; means for generating prediction parameters based on the previous and the current contours, and the previous and the current frames; means for constructing a predicted current contour by transforming the previous contour based on the prediction parameters; means for detecting deviation points lying on portions of the predicted current contour that deviate from the current contour, to thereby generate the deviation points and corresponding displacements to the deviation points, wherein each of the displacements represents a minimum distance in a horizontal direction between each of the deviation points and the current contour; means for encoding the deviation points and the displacements together with the prediction parameters; contour reconstruction means for relocating the deviation points based on the displacements and producing a reconstructed current contour from the predicted current contour; means for taking N sample points on each of a plurality of line segments, each line segment joining two neighboring relocated deviation points on the reconstructed current contour, and calculating an error for each of the N sample points on each of the line segments to produce a set of errors for said each of the line segments, wherein the N sample points are equi-spaced on said each of the line segments and each of the errors represents a distance between each of the N sample points and the current contour; means for summing up the set of errors to provide a similarity index; control means for sequentially providing the feature point selection means with one or more grids until a similarity index obtained based on one of said one or more grids becomes smaller than a predetermined threshold value and generating a grid index indicating the grid related to the similarity index smaller than the predetermined threshold value; and means for encoding the grid index.

Claim 7

An apparatus for encoding a contour of regions contained in a video signal, the video signal having a plurality of frames including a current frame and a previous frame, which comprises: first segmentation means for segmenting the previous frame into a number of regions to generate a previous contour; second segmentation means for segmenting the current frame into a number of regions to generate a current contour; means for generating prediction parameters based on the previous and the current contours, and the previous and the current frames; means for constructing a predicted current contour by transforming the previous contour based on the prediction parameters; means for detecting deviation points lying on portions of the predicted current contour that deviate from the current contour, to thereby generate the deviation points and corresponding displacements to the deviation points, wherein each of the displacements represents a minimum distance in a horizontal direction between each of the deviation points and the current contour; means for encoding the deviation points and the displacements together with the prediction parameters; contour reconstruction means for relocating the deviation points based on the displacements and producing a reconstructed current contour from the predicted current contour; means for taking N sample points on each of a plurality of line segments, each line segment joining two neighboring relocated deviation points on the reconstructed current contour, and calculating an error for each of the N sample points on each of the line segments to produce a set of errors for said each of the line segments, wherein the N sample points are equi-spaced on said each of the line segments and each of the errors represents a distance between each of the N sample points and the current contour; means for summing up the set of errors to provide a similarity index; control means for sequentially providing the feature point selection means with one or more grids until a similarity index obtained based on one of said one or more grids becomes smaller than a predetermined threshold value and generating a grid index indicating the grid related to the similarity index smaller than the predetermined threshold value; and means for encoding the grid index.