Encoding method and apparatus applying coefficient reordering

• US 8,200,033 B2
• Filed: 11/27/2006
• Issued: 06/12/2012
• Est. Priority Date: 11/30/2005
• Status: Active Grant

• Current Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Mertens, Mark Jozef Willem, Mietens, Stephan Oliver
• Primary Examiner(s): Dang, Duy M
• Application Number:
  US12/095,140
• Publication Number:
  US 20090046941A1
• Time in Patent Office: 2,024 Days
• Field of Search: 382/232, 382/233, 382/236, 382/239, 382/282, 382/250, 382/251
• US Class Current: 382/250
• CPC Class Codes: H04N 19/129 Scanning of coding units, e.g. zig-zag scan of transform coefficients or flexible macroblock ordering [FMO]
• CPC Class Codes: H04N 19/14 Coding unit complexity, e.g. amount of activity or edge presence estimation H04N19/146 takes precedence
• CPC Class Codes: H04N 19/149 by estimating the code amount by means of a model, e.g. mathematical model or statistical model
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/18 the unit being a set of transform coefficients
• CPC Class Codes: H04N 19/46 Embedding additional information in the video signal during the compression process H04N19/517, H04N19/68, H04N19/70 take precedence
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

In a method of encoding and encoder a method step is performed in which the scan order of a set of image region modeling coefficients is established on the basis of information of set of image region modeling coefficients preceding said set of image region modeling coefficients, and said set of image region modeling coefficients subsequently undergoes a scan ordering.

Claims

1. A computer program embodied in a non-transitory computer-readable medium for effecting the performance of a method of encoding a sequence of sets of image region modeling coefficients representing respective regions of an image into a sequence of reordered sets of image region modeling coefficients by repeatedly determining which of a plurality of different scan orders to use, said method comprising:

a. using a predetermined one of the scan orders to scan a plurality of the image region modeling coefficients representing a respective region of the image;

b. based on information from the already-scanned plurality of image region modeling coefficients, determining whether a different one of the scan orders has a higher probability of effectively encoding successive image region modeling coefficients representing another respective region of the image;

c. if said probability is higher, using said different scan order for encoding the successive image region modeling coefficients; and

d. repeatedly performing steps b and c for already-scanned modeling coefficients and yet-to-be-scanned modeling coefficients, respectively.

2. A computer program as in claim 1 where the different scan orders are predetermined and the probable effectiveness of each of said scan orders in encoding specific image region modeling coefficients is determined by calculating a respective fit parameter.

3. A computer program as claimed in claim 1 where the scan order is determined on the basis of statistical analysis of information of preceding sets of image region modeling coefficients.

4. A computer program as claimed in claim 1 where for already-scanned image region modeling coefficients determined to have an approximate value of zero at common positions the scan order for a following set of image region modeling coefficients is determined such that said coefficients are pushed back in the scan order.

5. A computer program as claimed in claim 1 where each of the sets of image region modeling coefficients comprises a plurality of coefficients and where for some of said plurality of coefficients the scan order is determined while for the remaining coefficients a fixed scan order is used.

6. A computer program as claimed in claim 1 where a plurality of different algorithms are used for determination of the scan order to be used.

7. An encoder for encoding a sequence of sets of image region modeling coefficients representing respective regions of an image into a sequence of reordered sets of image region modeling coefficients by repeatedly determining which of a plurality of different scan orders to use, said encoder comprising a scan order determinator for:

a. selecting a predetermined one of the scan orders to scan a plurality of the image region modeling coefficients representing a respective region of the image;

b. based on information from the already-scanned plurality of image region modeling coefficients, determining whether a different one of the scan orders has a higher probability of effectively encoding successive image region modeling coefficients representing another respective region of the image;

c. if said probability is higher, using said different scan order for encoding the successive image region modeling coefficients; and

d. repeatedly performing steps b and c for already-scanned modeling coefficients and yet-to-be scanned modeling coefficients, respectively.

8. An encoder as claimed in claim 7 where the different scan orders are predetermined and the probable effectiveness of each of said scan orders in encoding specific image region modeling coefficients is determined by calculating a respective fit parameter.

9. An encoder as claimed in claim 7, where the scan order is determined on the basis of statistical analysis of information of preceding sets of image region modeling coefficients.

10. An encoder as claimed in claim 7 where for already-scanned image region modeling coefficients having common zero values in preceding sets of image region modeling coefficients, the scan order for a following set of image region modeling coefficients is determined such that said coefficients are pushed back in the scan order.

11. An encoder as claimed in claim 7 where each of the sets of image region modeling coefficients comprises a plurality of coefficients and where for some of said plurality of coefficients the scan order is determined while for the remaining coefficients a fixed scan order is used.

12. An encoder as claimed in claim 7, where the scan order determinator uses a plurality of different algorithms for determining the scan orders to be used.

13. An encoder as claimed in claim 12 where the encoder is operative to add information pertaining to the algorithm used in the scan ordering to a signal comprising the reordered sets of image region modeling coefficients.

14. A transmitter including an encoder for encoding a sequence of sets of image region modeling coefficients representing respective regions of an image into a sequence of reordered sets of image region modeling coefficients by repeatedly determining which of a plurality of different scan orders to use, said encoder comprising a scan order determinator for:

a. selecting a predetermined one of the scan orders to scan a plurality of the image region modeling coefficients representing a respective region of the image;

b. based on information from the already-scanned plurality of image region modeling coefficients, determining whether a different one of the scan orders has a higher probability of effectively encoding successive image region modeling coefficients representing another respective region of the image;

c. if said probability is higher, using said different scan order for encoding the successive image region modeling coefficients; and

d. repeatedly performing steps b and c for already-scanned modeling coefficients and yet-to-be scanned modeling coefficients, respectively.

15. A transmitter as claimed in claim 14, said transmitter comprising an image-capturing device.

16. A transmitter as claimed in claim 14, said transmitter comprising a device for recording information.

17. A computer program embodied in a non-transitory computer-readable medium for effecting the performance of a method of decoding a sequence of reordered sets of image region modeling coefficients produced by an encoder into a sequence of reconstructed sets of image region modeling coefficients representing respective regions of an image, said method comprising performing a reverse scan ordering based on a known algorithm used by the encoder for reordering image region modeling coefficients in which:

a. a predetermined one of a plurality of scan orders is used to scan a plurality of the image region modeling coefficients representing a respective region of the image;

b. based on information from the already-scanned plurality of image region modeling coefficients, it is determined whether a different one of the scan orders has a higher probability of effectively encoding successive image region modeling coefficients representing another region of the image;

c. if said probability is higher, using said different scan order for encoding the successive image region modeling coefficients; and

d repeatedly performing steps b and c for already-scanned modeling coefficients and yet-to-be scanned modeling coefficients, respectively.

18. A computer program as in claim 17 where the probable effectiveness of each of said scan orders in encoding specific image region modeling coefficients is determined by calculating a respective fit parameter.

19. A computer program as claimed in claim 17 where the reverse scan orders are determined on basis of statistical analysis of preceding reconstructed sets of image region modeling coefficients.

20. A computer program as claimed in claim 17, where for already reconstructed image region modeling coefficients having common zero values the reverse scan order for a following reordered set of image region modeling is such that said coefficients are pushed back in the reverse scan order.

21. A computer program as claimed in claim 17 where each of the sets of image region modeling coefficients comprises a plurality of coefficients and where for some of said plurality of coefficients the reverse scan order is determined while for the remaining coefficients a fixed reverse scan order is used.

22. A computer program as claimed in claim 17 where a plurality of different algorithms are used for determination of the reverse scan order to be used.

23. A decoder for decoding a sequence of reordered sets of image region modeling coefficients produced by an encoder into a sequence of reconstructed sets of image region modeling coefficients representing respective regions of an image, said decoder comprising a reverse scan order determinator for performing a reverse scan ordering based on a known algorithm used by the encoder for reordering image region modeling coefficients in which:

a. a predetermined one of a plurality of scan orders is used to scan a plurality of the image region modeling coefficients representing a respective region of the image;

b. based on information from the already-scanned plurality of image region modeling coefficients, it is determined whether a different one of the scan orders has a higher probability of more effectively encoding successive image region modeling coefficients representing another region of the image;

c. if said probability is higher, using said different scan order for encoding the successive image region modeling coefficients; and

d. repeatedly performing steps b and c for already-scanned modeling coefficients and yet-to-be-scanned modeling coefficients, respectively.

24. A decoder as claimed in claim 23 where the different scan orders are predetermined and the probable effectiveness of each of said scan orders in encoding specific image region modeling coefficients is determined by calculating a respective fit parameter.

25. A decoder as claimed in claim 23, where the reverse scan order is determined on the basis of statistical analysis of preceding reconstructed sets of image region modeling coefficients.

26. A decoder as claimed in claim 23, where for already reconstructed sets of image region modeling coefficients having common zero values the reverse scan order for a following reordered set of image region modeling coefficients is determined such that said coefficients are pushed back in the reverse scan order.

27. A decoder as claimed in claim 23 where each of the sets of image region modeling coefficients comprises a plurality of coefficients, and where for some of the plurality of coefficients the reverse scan order is determined while for the remaining coefficients a fixed reverse scan order is used.

28. A decoder as claimed in claim 23 where the reverse scan order determinator uses a plurality of different algorithms for determination of the reverse scan order to be used.

29. A receiver comprising a decoder as claimed in claim 23.

30. A receiver as claimed in claim 29, said receiver comprising an image reproduction device.