Method and apparatus for coding/decoding scalable shapes by using scan interleaving

• US 6,377,622 B1
• Filed: 07/02/1998
• Issued: 04/23/2002
• Est. Priority Date: 07/02/1997
• Status: Expired due to Term

• Current Assignee: Pantech Incorporated
• Original Assignee: SK Hynix Inc.
• Inventors: Moon, Joo-Hee, Chung, Jae-Won, Chun, Sung-Moon, Kim, Jong-Deuk
• Primary Examiner(s): Kelley, Chris
• Assistant Examiner(s): PHILIPPE, GIMS S
• Application Number:
  US09/109,959
• Time in Patent Office: 1,391 Days
• Field of Search: 375/240, 375/240.09, 375/240.24, 375/240.17, 375/240.25, 348/408.1, 348/410.1, 348/385.1, 348/397.1, 348/414.1, 348/420.1, 348/440.1, 348/384.1, 348/409.1, 382/243, 382/242, 382/268, 382/240, 345/441, 345/468
• US Class Current: 375/240
• CPC Class Codes: G06T 9/20 Contour coding, e.g. using detection of edges

Abstract

A plurality of layers having other resolution are coded in order to encode scalably shape information. A base layer having the lower resolution is coded and transmitted to a decoder, and an enhancement layer is coded by employing a scan interleaving method from the base layer. A scan order of vertical and horizontal scannings is decided according to a generation frequency of TSD (transitional sample data) and ESD (exceptional sample data) and the number of coding bits on the base layer, or a type of boundary lines on images. When the scan order is decided, additional information indicating the scan order is transmitted to the decoder. The base layer is also coded and transmitted to the decoder. In case that the scan order is decided according to the horizontal and vertical of the boundary lines on an image of the base layer, it is no need to transmit the additional information indicating the scan order on the received base layer and execute the decoding in the same order as the coded scan order.

Claims

1. A method for decoding scalably shapes on a plurality of layers having mutually other resolution by using a scan interleaving method, said method comprising the steps of:

calculating the number of cases that vertically adjacent pixel values on a base layer are different from each other, N1, and horizontally adjacent pixel values on the base layer are different from each other, N2;

detecting whether or not the number of cases that the vertically adjacent pixel values are different from, N1, is larger than the number of cases that the horizontally adjacent pixel values are different from each other, N2; and

deciding the scan order for executing the horizontal scanning first in a case of N1>

N2 and performing the vertical scanning first in cases excepting N1>

N2.

2. An apparatus for coding scalably shapes on a plurality of layers having mutually other resolution through a scanning based on a predetermined scan order in employing a scan interleaving method, said apparatus comprising:

base layer extraction means for extracting a base layer from shape information;

scan order decision means for comparing lengths of horizontal and vertical boundary lines on the base layer and outputting switching control signals according to its comparison result;

switching means for switching an enhancement layer and the base layer in response to the switching control signals outputted from said scan order decision means;

first symmetrical movement means for symmetrically moving said shape information centering on a diagonal line and outputting it;

second symmetrical movement means for symmetrically moving said base layer centering on the diagonal line and outputting it;

horizontal direction scan means for scanning the shape information and the base layer outputted through said switching means or said first and second symmetrical movement means in a horizontal direction; and

vertical direction scan means for scanning the shape information and the base layer outputted through said switching means or said first and second symmetrical movement means in a vertical direction.

3. The apparatus of claim 2, wherein said scan order decision means detects a scan order, controls the switching means to output the shape information and the base layer to said horizontal and vertical direction scan means in case that its scan order is same as the predetermined scan order, and controls the switching means to switch the shape information and the base layer to said first and second symmetrical movement means in case that its scan order is not same as the predetermined scan order.

4. The apparatus of claim 2, wherein said first symmetrical movement means symmetrically moves the shape information centering on the diagonal line or rotates the shape information 90 degrees and outputs it;

and

said second symmetrical movement means symmetrically moves the base layer centering on the diagonal line or rotates the base layer 90 degrees and outputs it.

5. A method for decoding scalably shapes on a plurality of layers having mutually other resolution by using a scan interleaving method, said method comprising the steps of:

deciding an order of vertical and horizontal scannings on shape information or a base layer;

detecting whether or not the scan order decided in said deciding step is same as predetermined scan direction;

rotating the shape information 90 degrees or symmetrically moving the shape information centering on a diagonal line in case that the detecting result is not same; and

executing a scanning in the predetermined scan order in the same case.

6. The method of claim 5, wherein the scan order decided in said deciding step is decided, to generate coding bits in a small quantity, by a direction of a boundary line, the number of TSDs (transitional sample data'"'"'s), the number and ESDs (exceptional sample data'"'"'s), the sum of TSD (transitional sample data) and ESD (exceptional sample data), the number of bits in coding the TSD, the number of bits in coding the ESD and the number of bits in coding the TSD (transitional sample data) and the ESD (exceptional sample data).

7. An apparatus for decoding scalably shapes on a plurality of layers having mutually other resolution through a scanning based on a predetermined scan order in employing a scan interleaving method, said apparatus comprising:

base layer decoding means for decoding a base layer in coding data;

scan order decision means for comparing lengths of horizontal and vertical boundary lines on the base layer and outputting switching control signals according to its comparison result;

first switching means for switching the base layer outputted from said base layer decoding means in response to the switching control signals outputted from said scan order decision means;

symmetrical movement means for symmetrically moving the base layer outputted through said first switching means centering on a diagonal line or rotating it 90 degrees and outputting it;

horizontal direction decoding scan means and vertical direction decoding scan means for performing a decoding scanning on shape information and the base layer outputted through said first switching means or symmetrical movement means in horizontal and vertical directions;

second switching means for switching data outputted from said vertical direction decoding scan means in response to the switching control signal outputted from said scan order decision means; and

converse symmetrical movement means for symmetrically moving the data outputted through said second switching means in an opposite direction to said symmetrical movement means or rotating the data 90 degrees and outputting it.

8. The apparatus of claim 7, wherein said scan order decision means compares the lengths of the horizontal and vertical boundary lines and controls the switching means to switch the base layer to the symmetrical movement means, in case that the length of the horizontal boundary line is longer than that of the vertical boundary line.

9. The apparatus of claim 7, wherein said vertical direction decoding scan means receives decoding data from the horizontal direction decoding scan means, and then executes a vertical decoding scanning.

10. The apparatus of claim 7, wherein the switching control signal of said scan order decision means controls so that the second switching means may switch an enhancement layer outputted from the vertical direction decoding scan means to said converse symmetrical movement means in response to the switching control signal of the scan order decision means, in case that the first switching means controls the base layer to be switched to said symmetrical movement means.

11. A method for decoding scalably shapes on a plurality of layers having mutually other resolution by using a scan interleaving method, said method comprising the steps of:

receiving additional information indicating a scan order;

detecting whether or not the scan order represented in said additional information is same as a predetermined scan order;

rotating shape information 90 degrees or symmetrically moving the shape information centering on a diagonal line in case that the detecting result is not same; and

executing a decoding scanning in the predetermined scan order in the same case.

12. An apparatus for coding scalably shapes on a plurality of layers having mutually other resolution by using a scan interleaving method, said apparatus comprising:

shape information extraction means for extracting shape information from inputted images and outputting it;

base layer extraction means for extracting pixel data corresponding to a base layer from shape information data outputted from said shape information extraction means and outputting it;

scan order decision means for comparing lengths of horizontal and vertical boundary lines on the base layer outputted from said base layer extraction means and outputting switching control signals according to its comparison result;

switching means for switching the shape information and the base layer in response to the switching control signals outputted from said scan order decision means;

first direction scan means for receiving the base layer data and the shape information and executing a horizontal scanning first and a vertical scanning next;

second direction scan means for receiving the base layer data and the shape information and performing the vertical scanning first and the horizontal scanning next;

said scan order decision means controls the switching means to output the switching control signal for switching the shape information and the base layer to the second direction scan means, in case that the length of the horizontal boundary line is longer than the length of the vertical boundary line;

said scan order decision means controls the switching means to output the switching control signal for switching the shape information and the base layer to the, first direction scan means, in case that the length of the vertical boundary line is longer than the length of the horizontal boundary line;

said first direction scan means comprises;

a horizontal direction scan means for executing the horizontal scanning; and

a vertical direction scan means for performing the vertical scanning on data completed in a scanning process of said horizontal direction scan means, the shape information and the base layer data,

said second direction scan means comprises a vertical direction scan means and a horizontal direction scan means in an opposite constructive order to that of said first direction scan means;

said horizontal direction scan means comprises;

coding pixel extraction means for extracting coding pixel from the shape information;

horizontal adjacent pixel extraction means for extracting pixels positioned on the right and left of the pixel extracted by said coding pixel extraction means;

first comparison means for comparing pixels adjacent to said coding pixel outputted from said horizontal adjacent pixel extraction means and outputting the switching control signals;

first switching means for switching the coding pixel and horizontal adjacent pixels in response to the switching control signal of said first comparison means;

second comparison means for comparing the coding pixel and adjacent pixels and outputting the switching control signals;

second switching means for switching the coding pixel and the horizontal adjacent pixels in response to the switching control signal of said second comparison means;

TSD (transitional sample data) coding means for encoding the coding pixel outputted through said first switching means; and

ESD (exceptional sample data) coding means for encoding the coding pixel outputted through said second switching means.

13. The apparatus of claim 12, wherein said horizontal adjacent pixel extraction means executes a coding for a first row and first column of an enhancement layer by using a pixel value belonging to a corresponding position of an adjacent block or doubly using a first row and first column of the base layer.

14. The apparatus of claim 13, wherein said vertical direction scan means comprises:

coding pixel extraction means for receiving the shape information and horizontal direction coding data outputted from said horizontal direction scan means and extracting the coding pixel from the shape information and the coding data;

vertical adjacent pixel extraction means for receiving the horizontal direction coding data outputted from said horizontal direction scan means and the base layer data and extracting pixels positioned on the upper and lower sides of the pixel extracted by said coding pixel extraction means;

third comparison means for comparing with each other vertical adjacent pixels outputted from said vertical adjacent pixel extraction means and outputting the switching control signals according to its comparison result;

first switching means for switching the coding pixel and the horizontal adjacent pixels in response to the switching control signal of said third comparison means;

fourth comparison means for comparing the coding pixel and adjacent pixels and outputting the switching control signals;

second switching means for switching the coding pixel and the vertical adjacent pixels in response to the switching control signal of said fourth comparison means;

TSD (transitional sample data) coding means for encoding the coding pixel outputted through said first switching means; and

ESD (exceptional sample data) coding means for encoding the coding pixel outputted through said second switching means.

15. The apparatus of claim 14, wherein said vertical adjacent pixel extraction means executes a coding for the first row and first column of the enhancement layer by using a pixel value belonging to a corresponding position of an adjacent block or doubly using the first row and first column of the base layer.

16. An apparatus for decoding scalably shapes on a plurality of layers having mutually other resolution by utilizing a scan interleaving method, said apparatus comprising:

base layer decoding means for receiving and decoding base layer coding data transmitted from a coding apparatus;

scan order decision means for comparing lengths of horizontal and vertical boundary lines on the base layer outputted from said base layer decoding means and outputting switching control signals according to its comparison result;

switching means for switching coding data transmitted from the coding apparatus and base layer data outputted from said base layer decoding means in response to the switching control signals outputted from said scan order decision means;

first direction scan decoding means for receiving the base layer data and the coding data and executing a horizontal decoding scanning first and a vertical decoding scanning next;

second direction scan decoding means for receiving the base layer data and the coding data and performing the vertical decoding scanning first and the horizontal decoding scanning next;

said scan order decision means controls the switching means to output the switching control signal for switching the shape information and the base layer to the second direction scan decoding means, in case that the length of the horizontal boundary line is longer than the length of the vertical boundary line;

said scan order decision means controls the switching means to output the switching control signal for switching the shape information and the base layer to the first direction scan decoding means, in case that the length of the vertical boundary line is longer than the length of the horizontal boundary line;

said first direction scan decoding means comprising;

a horizontal direction decoding scan means for executing the horizontal decoding scanning; and

a vertical direction decoding scan means for performing the vertical decoding scanning on data completed in a scanning process of said horizontal direction decoding scan means, the coding data and the base layer data;

said second direction scan decoding means comprises a vertical direction decoding scan means and a horizontal direction decoding scan means in an opposite constructive order to that of said first direction scan decoding means;

said horizontal direction decoding scan means comprising;

horizontal adjacent pixel extraction means for extracting pixels positioned on the right and left of decoding pixel from said base layer;

comparison means for comparing pixels adjacent to said decoding pixel outputted from said horizontal adjacent pixel extraction means and outputting the switching control signals;

first switching means for switching the coding data and horizontal adjacent pixels in response to the switching control signal of said comparison means;

second switching means for switching the horizontal adjacent pixels and the coding data transmitted from the coding apparatus according as corresponding decoding data among the coding data belongs to an ESD (exceptional sample data) or does not belong to the ESD (exceptional sample data);

TSD (transitional sample data) decoding means for decoding the coding data outputted through said first switching means;

ESD (exceptional sample data) decoding means for decoding the coding pixel outputted through said second switching means; and

adjacent pixel copy means for storing horizontal adjacent pixel values of decoding pixels not belonging to a TSD (transitional sample data) or the ESD (exceptional sample data).

17. The apparatus of claim 16, wherein said horizontal adjacent pixel extraction means executes a decoding for a first row and first column of an enhancement, layer by using a pixel value belonging to a corresponding position of an adjacent block or doubly using a first row and first column of the base layer.

18. An apparatus for decoding scalably shapes on a plurality of layers having mutually other resolution by utilizing a scan interleaving method, said apparatus comprising:

base layer decoding means for receiving and decoding base layer coding data transmitted from a coding apparatus;

scan order decision means for comparing lengths of horizontal and vertical boundary lines on the base layer outputted from said base layer decoding means and outputting switching control signals according to its comparison result;

switching means for switching coding data transmitted from the coding apparatus and base layer data outputted from said base layer decoding means in response to the switching control signals outputted from said scan order decision means;

first direction scan decoding means for receiving the base layer data and the coding data and executing a horizontal decoding scanning first and a vertical decoding scanning next;

second direction scan decoding means for receiving the base layer data and the coding data and performing the vertical decoding scanning first and the horizontal decoding scanning next;

said first direction scan decoding means comprising;

a horizontal direction decoding scan means for executing the horizontal decoding scanning;

a vertical direction decoding scan means for performing the vertical decoding scanning on data completed in a scanning process of said horizontal direction decoding scan means, the coding data and the base layer data;

said second direction scan decoding means comprises a vertical direction decoding scan means and a horizontal direction decoding scan means in an opposite constructive order to that of said first direction scan decoding means;

said vertical direction decoding scan means comprises;

vertical adjacent pixel extraction means for receiving the horizontal direction decoding data outputted from said horizontal direction decoding scan means, the coding data and the base layer data, and extracting pixels positioned on the upper and lower sides of the decoding pixel;

comparison means for comparing with each other vertical adjacent pixels outputted from said vertical adjacent pixel extraction means and outputting the switching control signals according to its comparison result;

first switching means for switching the coding data, horizontal decoding data and the horizontal adjacent pixels in response to the switching control signal of said comparison means;

second switching means for switching the vertical adjacent pixels and the coding data transmitted from the coding apparatus according as corresponding decoding data among the coding data belongs to the ESD (exceptional sample data) or does not belong to the ESD (exceptional sample data);

TSD (transitional sample data) decoding means for decoding the coding data outputted through said first switching means;

ESD (exceptional sample data) decoding means for decoding the coding data outputted through said second switching means; and

adjacent pixel copy means for storing horizontal adjacent pixel values of decoding pixels not corresponding to the TSD (transitional sample data) or the ESD (exceptional sample data).

19. The apparatus of claim 18, wherein said vertical adjacent pixel extraction means executes a decoding for the first row and first column of the enhancement layer by using a pixel value belonging to a corresponding position of an adjacent block or doubly using the first row and first column of the base layer.

20. A method for coding scalably shapes on a plurality of layers having mutually other resolution by using a scan interleaving method, said method comprising the steps of:

deciding a scan order of vertical and horizontal scanning, said scan order being for generating coding bits in a small quantity;

detecting whether or not the scan order decided in said deciding step is as a priority order of the vertical scanning;

executing first the vertical scanning in a preferential case of the vertical scanning and the horizontal scanning next;

performing first the horizontal scanning in a preferential case of the horizontal scanning and the vertical scanning next;

the scan order deciding step comprises the steps of;

calculating the number of cases that vertically adjacent pixel values are different from each other and horizontally adjacent pixel values are different from each other, on a base layer extracted from shape information;

detecting whether or not number of cases that the vertically adjacent pixel values are different from, N1, is larger than the number of cases that the horizontally adjacent pixel values are different from, N2; and

deciding the scan order for executing the horizontal scanning first in a case of N1>

N2, and performing the vertical scanning first in cases excepting N1>

N2.

21. A method for coding scalably shapes on a plurality of layers having mutually other resolution by using a scan interleaving method, said method comprising the steps of:

deciding a scan order of vertical and horizontal scanning, said scan order being for generating coding bits in a small quantity;

detecting whether or not the scan order decided in said deciding step is a priority order of the vertical scanning;

executing first the vertical scanning in a preferential case of the vertical scanning and the horizontal scanning next;

performing first the horizontal scanning in a preferential case of the horizontal scanning and the vertical scanning next;

said scan order deciding step comprises the steps of;

calculating the coding number of TSDs (transitional sample data'"'"'s) and ESDs (exceptional sample data'"'"'s) in the horizontal scanning, (N_H), and computing the coding number of TSDs (transitional sample data'"'"'s) and ESDs (exceptional sample data'"'"'s) in the vertical scanning, (N_V), on shape information;

adding up said N_H and N_V and computing the total number of TSDs (transitional sample data'"'"'s) and ESDs (exceptional sample data'"'"'s), (N_HV), which is generated in a horizontal direction priority scan order;

counting the coding number of TSDs (transitional sample data'"'"'s) and ESDs (exceptional sample data'"'"'s) in the vertical scanning, (N_V), and calculating the coding number of TSDs (transitional sample data'"'"'s) and ESDs (exceptional sample data'"'"'s) in the horizontal scanning, (N_H), on said preferential case of the horizontal scanning and the vertical scanning next.

22. A method for coding scalably shapes on a plurality of layers having mutually other resolution by using a scan interleaving method, said method comprising the steps of:

deciding a scan order of vertical and horizontal scanning, said scan order being for generating coding bits in a small quantity;

detecting whether or not the scan order decided in said deciding step is a priority order of the vertical scanning;

executing first the vertical scanning and the horizontal scanning next;

performing first the horizontal scanning and the vertical scanning next;

said scan order deciding step comprises the steps of;

calculating the coding number of TSDs (transitional sample data'"'"'s) and ESDs (exceptional sample data'"'"'s) in the horizontal scanning, (N_H), and computing the coding number of TSDs (transitional sample data'"'"'s) and ESDs (exceptional sample data'"'"'s) in the vertical scanning, (N_V), on shape information;

adding up said N_H and N_V and computing the total number of TSDs (transitional sample data'"'"'s) and ESDs (exceptional sample data'"'"'s), (N_HV), which is generated in a horizontal direction priority scan order;

counting the coding bits of the TSD (transitional sample data) (ESD) (exceptional sample data) in the vertical scanning, (N_V), and calculating the coding bits of the TSD (transitional sample data) (ESD) (exceptional sample data) in the horizontal scanning, (N_H), on said shape information;

summing up said N_H and N_V and computing the total coding bits of the TSD (transitional sample data) (ESD) (exceptional sample data), (N_VH), which is generated in the vertical direction priority scan order;

detecting whether or not it is N_HV>

N_VH;

deciding the scan order in which the vertical scanning is preferentially executed in a case of N_HV>

N_VH, and the horizontal scanning is preferentially executed in case that it is not N_HV>

N_VH; and

transmitting the scan order decided in the deciding step to the decoder.

23. A method for coding scalably shapes on a plurality of layers having mutually other resolution by using a scan interleaving method, said method comprising the steps of:

deciding a scan order of vertical and horizontal scanning, said scan order being for generating coding bits in a small quantity;

detecting whether or not the scan order decided in said deciding step is a priority order of the vertical scanning;

executing first the vertical scanning and the horizontal scanning next;

performing first the horizontal scanning and the vertical scanning next;

said scan order deciding step comprises the steps of;

calculating the sum of TSDs (transitional sample data'"'"'s) and ESDs (exceptional sample data'"'"'s) in the horizontal scanning, (N_H), and computing the sum of TSD (transitional sample data) and ESD (exceptional sample data) in the vertical scanning, (N_V), on shape information;

adding up said N_H and N_V and computing the total number of TSD (transitional sample data) and ESD (exceptional sample data), (N_HV), which is generated in a horizontal direction priority scan order;

counting the sum of TSD (transitional sample data) and ESD (exceptional sample data) in the vertical scanning, (N_V), and calculating the sum of TSD (transitional sample data) and ESD (exceptional sample data) in the horizontal scanning, (N_H), on said shape information;

summing up said N_H and N_V and computing the total coding bits of the TSD (transitional sample data) (ESD) (exceptional sample data), (N_VH), which is generated in the vertical direction priority scan order;

detecting whether or not it is N_HV>

N_VH;

deciding the scan order in which the vertical scanning is preferentially executed in a case of N_HV>

N_VH, and the horizontal scanning is preferentially executed in case that it is not N_HV>

N_VH; and

transmitting the scan order decided in the deciding step to the decoder.

24. A method for coding scalably shapes on a plurality of layers having mutually other resolution by using a scan interleaving method, said method comprising the steps of:

deciding a scan order of vertical and horizontal scanning, said scan order being for generating coding bits in a small quantity;

detecting whether or not the scan order decided in said deciding step is a priority order of the vertical scanning;

executing first the vertical scanning and the horizontal scanning next;

performing first the horizontal scanning and the vertical scanning next;

said scan order deciding step comprises the steps of;

calculating the sum of TSDs (transitional sample data'"'"'s) and ESDs (exceptional sample data'"'"'s) in the horizontal scanning, (N_H), and computing the sum of TSD (transitional sample data) and ESD (exceptional sample data) in the vertical scanning, (N_V), on shape information;

adding up said N_H and N_V and computing the total number of TSD (transitional sample data) and ESD (exceptional sample data), (N_HV), which is generated in a horizontal direction priority scan order;

counting the sum of TSD (transitional sample data) and ESD (exceptional sample data) in the vertical scanning, (N_V), and calculating the sum of TSD (transitional sample data) and ESD (exceptional sample data) in the horizontal scanning, (N_H), on said shape information;

summing up said N_H and N_V and computing the total coding bits of the TSD (transitional sample data) (ESD) (exceptional sample data), (N_VH), which is generated in the vertical direction priority scan order;

detecting whether or not it is N_HV>

N_VH;

deciding the scan order in which the vertical scanning is preferentially executed in a case of N_HV>

N_VH, and the horizontal scanning is preferentially executed in case that it is not N_HV>

N_VH; and

transmitting the scan order decided in the deciding step to the decoder.