Image representation using tree-like structures

• US 5,274,718 A
• Filed: 09/30/1991
• Issued: 12/28/1993
• Est. Priority Date: 09/30/1991
• Status: Expired due to Term

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.), AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T, Inc.
• Inventors: Radha, Hayder S., Leonardi, Riccardo, Naylor, Bruce F.
• Primary Examiner(s): Razavi, Michael T.
• Assistant Examiner(s): Fox, David
• Application Number:
  US07/769,138
• Time in Patent Office: 820 Days
• Field of Search: 382/56, 382/37, 382/49, 382/27, 358/133, 358/426, 358/433, 358/432
• 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 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;

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; and

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;

wherein said step of selecting is performed in an iterative fashion such that the line selected in each iteration corresponds to a point in Hough space having a maximum value for the Hough transform of a predetermined domain of an edge image corresponding to said image.

2. The invention as described in claim 1 wherein said step of selecting is further performed within each region resulting from a partitioning of said domain by said selected line until either all of the resulting regions each have an area smaller than a first predetermined threshold or the resulting regions contain a number of edge points that is less than a second predetermined threshold.

3. The invention as described in claim 1 wherein said binary tree is comprised of nodes, each non-leaf node of said binary tree being a parent node that is associated with two child nodes, said parent nodes containing said description of at least one line of the set of arbitrarily oriented lines and each child node of said parent represents a region created by partitioning said domain in a particular iteration and said region itself may be further partitioned.

4. 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;

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;

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;

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 means and said 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 means and said for assigning a description;

said means for selecting including means for deriving the location of edge points of said image; and

said means for selecting further including means for computing the Hough transform for the edge points in said domain.

5. The invention as described in claim 4 wherein said means for selecting further includes means for determining the Hough transform peak and picking the line represented by said peak to be the line selected.