Image representation using tree-like structures

• US 5,740,280 A
• Filed: 10/01/1993
• Issued: 04/14/1998
• Est. Priority Date: 09/30/1991
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Leonardi, Riccardo, Radha, Hayder Sadiq, Naylor, Bruce F.
• Primary Examiner(s): Mancuso, Joseph
• Assistant Examiner(s): RAZAVI, MICHAEL
• Application Number:
  US08/131,261
• Time in Patent Office: 1,656 Days
• Field of Search: 382/21, 382/22, 382/37, 382/56, 382/240, 382/243, 358/426
• US Class Current: 382/240
• CPC Class Codes: G06T 9/40 Tree coding, e.g. quadtree, octree
• CPC Class Codes: G06V 10/40 Extraction of image or video features
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: H04N 19/96 Tree coding, e.g. quad-tree coding

Abstract

An image, having N dimensions, is partitioned into a set of bounded arbitrarily shaped regions. This partitioning is achieved through the use of arbitrarily shaped N-1 dimensional surfaces which pass through the boundaries of the image. The arbitrarily shaped regions are represented in the leaf nodes of a binary tree and the arbitrarily shaped surfaces, which are used to partition the image, are represented in the non-leaf nodes of the tree. In a preferred embodiment, arbitrarily oriented lines passing through the image boundaries are employed to partition a two-dimensional image into a set of convex regions. The convex regions are represented in the leaf nodes of a binary tree and the arbitrarily oriented lines, which are used to partition the image, are represented in the non-leaf nodes of the tree. Furthermore, the arbitrarily oriented lines are selected through the use of a Hough transform and the image is partitioned, along the selected lines, in a recursive manner as the binary tree is developed.

Claims

1. A method for use in developing in an image coding system a signal that represents an image having N dimensions contained within a signal containing images, said method comprising the steps of:

selecting a set of arbitrarily shaped surfaces having N-1 dimensions which are representable by a finite number of parameters, each of said surfaces being selected from any of the surfaces that intersect and partition said image;

said surfaces partitioning said image into a finite set of bounded arbitrarily shaped regions; and

forming a signal representing a binary tree in such a way that each non-leaf node of the binary tree contains at least a description of at least one arbitrarily shaped surface of the set of arbitrarily shaped surfaces and each leaf node of said binary tree contains at least a description of one of said bounded arbitrarily shaped regions that description being a representation of an estimate of the nature of the signal for said image within said one region.

2. A method, for use in an image coding system, to develop a signal that represents at least one image contained within a signal containing images, said method comprising the steps of:

selecting a set of arbitrarily oriented lines that partition the image into a set of unpartitioned convex regions each of said lines being selected from any of the lines that intersect and partition said image;

assigning a description to each of said unpartitioned convex regions, said description being an estimate of the nature of the signal for said image within the region to which it is assigned;

forming a signal representing a binary tree in a such way that each non-leaf node of the binary tree contains at least a description of at least one line of the set of arbitrarily oriented lines and each leaf node of said binary tree contains at least a description for one of said unpartitioned convex regions.

3. The invention as described in claim 2 further including the step of supplying said signal representing said binary tree as an output of said image coding system.

4. The invention as described in claim 2 further including the step of storing said signal representing said binary tree in a memory.

5. The invention as described in claim 2 wherein the individual descriptions assigned to each of said convex regions are chosen from a plurality of predetermined descriptions.

6. The invention as described in claim 2 wherein said step of selecting is performed in a recursive manner on each new region which results from partitioning of a prior region by a selected line.

7. The invention as described in claim 2 wherein said step of assigning further includes the steps of:

determining if said region should not be further partitioned; and

developing an estimate of the nature of the signal for the at least one image within the region to which it is assigned if said region should not be further partitioned.

8. Apparatus, for use in an image coding system for developing a signal that represents at least one image contained within a signal containing images, the apparatus comprising:

means for selecting an arbitrarily oriented line for partitioning a predetermined domain of said image into two subdomains said line being selected from any of the lines that intersect and partition said domain;

means for determining if a particular subdomain derived from a partitioning of said domain by a line selected by said means for selecting should not be further partitioned;

means for assigning a description to said particular subdomain if said means for determining has determined that said particular subdomain should not be further partitioned, said description being an estimate of the nature of the signal for said image within said particular subdomain; and

means for developing a signal representing a binary tree, said binary tree being such that a description of said line is contained within at least one non-leaf node of the binary tree and said description of said particular subdomain, if assigned, is contained within at least one leaf node of said binary tree.

9. The invention as described in claim 8 further including:

means for storing particular values for said domain, said subdomains, said line and said description;

means for reinitializing said means for selecting, said means for determining and said means for assigning a description;

means for assigning said domain to be a predetermined one of said subdomains; and

means for restarting said means for selecting, said means for determining and said means for assigning a description.

10. The invention as described in claim 9 further including means for retrieving particular values for said domain, said subdomains, said line and said description from said means for storing.

11. The invention as described in claim 9 wherein said means for selecting includes means for deriving the location of edge points of said image.

12. A method, for use in an image coding system, to develop a signal that represents an at least one image contained within a signal containing images, said method comprising the steps of:

selecting an arbitrarily oriented line to partition a predetermined domain of said image into two subdomains said line being selected from any of the lines that intersect and partition said domain;

developing a signal representing a binary tree, said binary tree being such that a description of said line is contained within at least one non-leaf node of the binary tree;

determining for each particular one of said subdomains if that particular subdomain should not be partitioned further;

assigning a description to each of the subdomains that should not be further partitioned, as determined by said step of determining, and placing at least one of said descriptions within at least one leaf node of said binary tree; and

recursively restarting said method for each of said particular subdomains that should be further partitioned, said restarting performed in a manner such that said predetermined domain upon such restarting is equal to said particular subdomain.

13. The invention as described in claim 12 wherein, in said step of developing, said descriptions are placed in said leaf nodes in a manner such that only one description is placed in each leaf node.

14. A method for use in developing in an image coding system a signal that represents an image having N dimensions contained within a signal containing images, said method comprising the steps of:

selecting a set of arbitrarily shaped surfaces having N-1 dimensions which are representable by a finite number of parameters, the shape of each of said arbitrarily shaped surfaces being other than solely limited to a shape selected from a predefined set of orthogonal shapes, said surfaces partitioning said image into a finite set of bounded arbitrarily shaped regions; and

forming a signal representing a binary tree in such a way that each non-leaf node of the binary tree contains at least a description of at least one arbitrarily shaped surface of the set of arbitrarily shaped surfaces and each leaf node of said binary tree contains at least a description of one of said bounded arbitrarily shaped regions that description being a representation of an estimate of the nature of the signal for said image within said one region.

15. A method, for use in an image coding system, to develop a signal that represents at least one image contained within a signal containing images, said method comprising the steps of:

selecting a set of arbitrarily oriented lines that partition the image into a set of unpartitioned convex regions, the angle of orientation of each of said arbitrarily oriented lines being other than solely limited to an angle selected from a predefined set of orthogonal angles;

assigning a description to each of said unpartitioned convex regions, said description being an estimate of the nature of the signal for said image within the region to which it is assigned;

forming a signal representing a binary tree in a such way that each non-leaf node of the binary tree contains at least a description of at least one line of the set of arbitrarily oriented lines and each leaf node of said binary tree contains at least a description for one of said unpartitioned convex regions.

16. Apparatus, for use in an image coding system for developing a signal that represents at least one image contained within a signal containing images, the apparatus comprising:

means for selecting an arbitrarily oriented line for partitioning a predetermined domain of said image into two subdomains, the angle of orientation of said selected line being other than solely limited to an angle selected from a predefined set of orthogonal angles;

means for determining if a particular subdomain derived from a partitioning of said domain by a line selected by said means for selecting should not be further partitioned;

means for assigning a description to said particular subdomain if said means for determining has determined that said particular subdomain should not be further partitioned, said description being an estimate of the nature of the signal for said image within said particular subdomain; and

means for developing a signal representing a binary tree, said binary tree being such that a description of said line is contained within at least one non-leaf node of the binary tree and said description of said particular subdomain, if assigned, is contained within at least one leaf node of said binary tree.

17. A method, for use in an image coding system, to develop a signal that represents an at least one image contained within a signal containing images, said method comprising the steps of:

selecting an arbitrarily oriented line to partition a predetermined domain of said image into two subdomains, the angle of orientation of said selected line being other than solely limited to an angle selected from a predefined set of orthogonal angles;

developing a signal representing a binary tree, said binary tree being such that a description of said line is contained within at least one non-leaf node of the binary tree;

determining for each particular one of said subdomains if that particular subdomain should not be partitioned further;

assigning a description to each of the subdomains that should not be further partitioned, as determined by said step of determining, and placing at least one of said descriptions within at least one leaf node of said binary tree; and

recursively restarting said method for each of said particular subdomains that should be further partitioned, said restarting performed in a manner such that said predetermined domain upon such restarting is equal to said particular subdomain.