Apparatus and method for coding binary image with improved efficiency

• US 6,876,773 B2
• Filed: 07/03/2001
• Issued: 04/05/2005
• Est. Priority Date: 10/23/2000
• Status: Active Grant

• Current Assignee: Nippon Hoso Kyokai
• Original Assignee: Nippon Hoso Kyokai
• Inventors: Shishikui, Yoshiaki, Mizuno, Osamu, Sakaida, Shinichi
• Primary Examiner(s): Chen, Wenpeng
• Application Number:
  US09/898,984
• Publication Number:
  US 20020048409A1
• Time in Patent Office: 1,372 Days
• Field of Search: 382243-236, 382/232, 358/539, 358/426.01, 358/426.16, 375/240, 375/240.01, 375/240.08, 375/240.24
• US Class Current: 382/243
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding

Abstract

An apparatus for coding a binary image representing an object shape includes an inferior symbol detecting unit which decides which one of binary zero and binary one is an inferior symbol that is of smaller occurrence within a given area of the binary image, a divided portion generating unit which divides a rectangular block of the given area into divided portions, a map information generating unit which generates map information for each one of the divided portions, the map information indicating whether a corresponding one of the divided portions has the inferior symbol included therein, and a coding unit which encodes only the divided portions that have the inferior symbol included therein, wherein an identification of the inferior symbol, the map information, and the encoded divided portions are output from the apparatus.

Claims

1. An apparatus for coding a binary image representing an object shape, comprising:

an inferior symbol detecting unit which decides which one of binary zero and binary one is an inferior symbol that is of smaller occurrence within a given area of the binary image;

a divided portion generating unit which divides a rectangular block of the given area into divided portions;

a map information generating unit which generates map information for each one of the divided portions, the map information indicating whether a corresponding one of the divided portions has the inferior symbol included therein; and

a coding unit which encodes only the divided portions that have the inferior symbol included therein, wherein an identification of the inferior symbol, the map information, and the encoded divided portions are output from said apparatus.

2. The apparatus as claimed in claim 1, wherein the binary zero and the binary one represent an interior of the object shape and an exterior of the object shape, respectively.

3. The apparatus us claimed in claim 1, wherein said divided portion generating unit is a pixel-line generating unit that divides the rectangular block into the divided portions that are pixel lines.

4. The apparatus as claimed in claim 3, further comprising:

a block generating unit which divides the given area into rectangular blocks, wherein the given area is one of macro blocks into which the binary image is divided; and

a block map information generating unit which generates block map information indicative of whether a corresponding one of the rectangular blocks has the inferior pixel included therein, wherein each of the rectangular blocks is divided into the divided portions by the divided portion generating unit only if there is the inferior pixel included therein.

5. The apparatus as claimed in claim 3, further comprising:

another inferior symbol detecting unit which detects another inferior symbol within one of macro blocks into which the binary image is divided;

a block generating unit which divides the one of the macro blocks into rectangular blocks including said rectangular block; and

a block map information generating unit which generates block map information indicative at whether a corresponding one of the rectangular blocks has said another inferior pixel included therein, wherein each at the rectangular blocks is divided into the divided portions by the divided portion generating unit only if there is said another inferior pixel included therein.

6. The apparatus as claimed in claim 5, wherein said given area coincides with said rectangular block.

7. The apparatus as claimed in claim 3, further comprising a pixel rearranging unit which rearranges pixels within the pixel lines before said coding unit encodes the divided portions, wherein information about rearrangement of the pixels is output from said apparatus.

8. The apparatus as claimed in claim 1, wherein said coding unit encodes the map information before the map information is output from said apparatus.

9. An apparatus for coding a binary image representing an object shape, comprising:

an inferior symbol detecting unit which decides which one of binary zero and binary one is an inferior symbol that is of smaller occurrence;

a divided portion generating unit which divides a block of the binary image into divided portions; and

a coding unit which encodes only the divided portion that have the inferior symbol included therein.

10. A method of coding a binary image representing an object shape, comprising the steps of:

deciding which one of binary zero and binary one is an inferior symbol that is of smaller occurrence within a given area of the binary image;

dividing a rectangular block of the given area into divided portions; and

encoding only the divided portions that have the inferior symbol included therein.

11. The method as claimed in claim 10, further comprising the steps of:

generating map information for each one of the divided portions, the map information indicating whether a corresponding one of the divided portions has the inferior symbol included therein; and

transmitting to a decoding side an identification of the inferior symbol, the map information, and the encoded divided portions.

12. The method as claimed in claim 10, further comprising the step of:

dividing the given area into rectangular blocks; and

subjecting any given one of the rectangular blocks to said step of dividing a rectangular block only if said any given one of the rectangular blocks has the inferior symbol included therein.

13. An apparatus for coding macro blocks on a macro block-by-macro-block basis, wherein a binary image representing an object shape is divided into the macro blocks each including at least one of interior pixels and exterior pixels of said object shape, the apparatus comprising:

a first unit configured to receive binary image data of one of the macro blocks, to obtain frequencies of occurrences of the interior pixels and the exterior pixels with respect to said one of the macro blocks, to decide a less frequent one of the interior pixels and the exterior pixels as an inferior symbol and a more frequent one of the interior pixels and the exterior pixels as a superior symbol, to output inferior symbol information indicative of which one of the interior pixels and the exterior pixels is the inferior symbol, and to output the binary image data of said one of the macro blocks as a bit pattern represented by the inferior symbol and the superior symbol,

a second unit configured to generate bit patterns of small blocks by dividing the bit pattern corresponding to said one of the macro blocks into a plurality of the small blocks;

a third unit configured to receive the inferior symbol information and the bit patterns of the small blocks, to check whether each of the small blocks includes the inferior symbol, to output a block map information indicative of the check result, and to output only the bit patterns of the small blocks that include the inferior symbol;

a fourth unit configured to receive the output bit patterns of the small blocks that include the inferior symbol, to obtain frequencies of occurrences of the interior pixels and the exterior pixels with respect to each of the received bit patterns of the small blocks, to output new inferior symbol information, to output binary image data of the small blocks that are bit patterns having the inferior symbol and the superior symbol exchanged with each other if the frequencies of occurrences are reversed, and to output the received bit patterns without a change if the frequency of occurrences are not reversed;

a fifth unit configured to divide the bit patterns of the small blocks output from said fourth unit into horizontal or vertical pixel lines to generate bit patterns of pixel lines;

a sixth unit configured to receive the new inferior symbol information and the bit patterns of the pixel lines, to check whether each of the pixel lines includes the inferior symbol, to output the check result as pixel-line map information, to output only the bit patterns of the pixel lines that include the inferior symbol; and

a seventh unit configured to encode, on a pixel-line-by-pixel-line basis, only the pixel lines that include the inferior symbol.

14. The apparatus as claimed in claim 13, further comprising a unit configured to perform a rearranging process for rearranging a sequence of pixel arrangement when the bit patterns of the pixel lines are encoded, wherein the encoding of the pixel lines is performed with respect to the rearranged bit patterns.

15. An apparatus for coding macro blocks on a macro block-by-macro-block basis wherein a binary image representing an object shape is divided into the macro blocks each including at least one of interior pixels and exterior pixels of said object shape, the apparatus comprising:

a first unit configured to receive binary image data of one of the macro blocks, to obtain frequencies of occurrences of the interior pixels and the exterior pixels with respect to said one of the macro blocks, to decide a less frequent one of the interior pixels and the exterior pixels as an inferior symbol and a more frequent one of the interior pixels end the exterior pixels as a superior symbol, to output inferior symbol information indicative of which one of the interior pixels and the exterior pixels is the inferior symbol, and to output the binary image data of said one of the macro blocks as a bit pattern represented by the inferior symbol and the superior symbol,

a second unit configured to generate bit patterns of small blocks by dividing the bit pattern corresponding to said one of the macro blocks into a plurality of the small blocks;

a third unit configured to receive the inferior symbol information and the bit patterns of the small blocks, to check whether each of the small blocks includes the inferior symbol, to output a block map information indicative of the check result, and to output only the bit patterns of the small blocks that include the inferior symbol;

a fourth unit configured to receive the output bit patterns of the small blocks that include the inferior symbol, to obtain frequencies of occurrences of the interior pixels and the exterior pixels with respect to each of the received bit patterns of the small blocks, to output new inferior symbol information, to output binary image data of the small blocks that are bit patterns having the inferior symbol and the superior symbol exchanged with each other if the frequencies of occurrences are reversed, and to output the received bit patterns without a change if the frequency of occurrences are not reversed;

a line-direction identifying unit configured to receive the new inferior symbol information and the bit patterns of the small blocks output from said fourth unit, and to select a pixel-line direction that is one of a horizontal direction and a vertical direction that produces fewer pixel lines including the inferior symbols when the received bit patterns of the small block are divided into horizontal pixel lines or vertical pixel lines;

a fifth unit configured to divide the bit patterns of the small blocks output from said fourth unit into pixel lines extending in the selected pixel-line direction to generate bit patterns of pixel lines;

a sixth unit configured to receive the new inferior symbol information and the bit patterns of the pixel lines, to check whether each of the pixel lines includes the inferior symbol, to output the check result as pixel-line map information, to output only the bit patterns of the pixel lines that include the inferior symbol; and

a seventh unit configured to encode, on a pixel-line-by-pixel-line basis, only the pixel lines that include the inferior symbol.

16. The apparatus as claimed in claim 15, further comprising a unit configured to perform a rearranging process for rearranging a sequence of pixel arrangement when the bit patterns of the pixel lines are encoded, wherein the encoding of the pixel lines is performed with respect to the rearranged bit patterns.