Method of describing image information

• US 4,944,023 A
• Filed: 05/18/1988
• Issued: 07/24/1990
• Est. Priority Date: 05/19/1987
• Status: Expired due to Fees

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Watanabe, Hideyuki, Imao, Kaoru
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Jung, Yon
• Application Number:
  US07/195,266
• Time in Patent Office: 797 Days
• Field of Search: 382/37, 382/56, 382/21, 382/39, 382/38, 358/135, 358/108
• US Class Current: 382/240
• CPC Class Codes: G06T 9/40 Tree coding, e.g. quadtree, octree

Abstract

A method of describing an image made up of a plurality of kinds of regions in an n-dimensional space by a tree structure, comprises the steps of recursively and equally dividing the image into 2ⁿ regions until each region includes two or less kinds of regions, thereby making a first level of the tree structure, and recursively and equally subdividing each of the 2ⁿ regions into 2ⁿ subregions until each subregion includes only one kind of region and for describing only one of two kinds of regions by a tree structure in which each parent node which degree is one and only having one branch is integrated into a filial node thereof, thereby making a second level of the tree structure. Each filial node in the second level of the tree structure is added with first division information described by sequential data of 2ⁿ kinds of codes corresponding to position information of each filial node with respect to a parent node thereof, and each leaf in the second level of the tree structure is added with second division information describing at least a least significant code of the first division information by 2ⁿ or more kinds of codes which are pattern information of each leaf with respect to a parent node thereof.

Claims

1. A method of describing an image made up of a plurality of kinds of regions in an n-dimensional space by a tree structure, said method comprising:

a first step of recursively and equally dividing said image in the n-dimensional space into 2ⁿ regions until each of the 2ⁿ regions include two or less kinds of regions, thereby making a first level of said tree structure having a root node corresponding to said image in its entirety, L nodes connected to said root node and each corresponding to a region with three or more kinds of regions and M leaves connected to said root node or a node and each corresponding to a region with two or less kinds of regions, where L=0, 1, 2, . . . , n, M1, 2, 3, . . . , n and L+M=n, each of said nodes having branches branching out therefrom and connecting to a filial node or leaf thereof; and

a second step of recursively and equally subdividing each of said 2ⁿ regions in the n-dimensional space into 2ⁿ subregions until each subregion includes only one kind of region and for describing only one of two kinds of regions by a tree structure in which each node which degree is one and only having one branch is integrated into a filial node or leaf thereof, thereby making a second level of said tree structure, each node in the second level of said tree structure being added with first division information described by sequential data of 2ⁿ kinds of codes corresponding to position information of each node with respect to a parent node thereof, each leaf in the second level of said tree structure being added with second division information, said second division information describing at least a least significant code of said first division information by 2ⁿ or more kinds of codes which are pattern information of each leaf with respect to a parent node thereof,

said tree structure describing said image in the first and second levels thereof.

2. A method as claimed in claim 1 in which each of said nodes in the first level of said tree structure include pointer information indicating a position of a corresponding region, and each of said leaves in the first level of said tree structure include information indicating a kind of region of a corresponding region.

3. A method as claimed in claim 2 in which each of said leaves corresponding to a region including two kinds of regions in the first level of said tree structure further include pointer information to the second level of said tree structure and information indicating a kind of subregion described in the second level of said tree structure.

4. A method as claimed in claim 3 in which said node in the level of said tree structure includes in addition to said first division information pointer information indicating a position of a predetermined number of subregions and end mark information indicating of an end of said pointer information.

5. A method as claimed in claim 1 in which said node in the second level of said tree structure includes in addition to said first division information pointer information indicating a position of a predetermined number of subregions and end mark information indicating an end of said pointer information.

6. A method as claimed in claim 1 which said first step comprises the substeps of:

checking a number of kinds of regions within an arbitrary one of the 2ⁿ regions;

adding a leaf to a node corresponding to the arbitrary region when two or less kinds of regions exist in the arbitrary region;

adding a filial node to the node corresponding to the arbitrary region when three or more kinds of regions exists in the arbitrary region; and

setting a pointer of the added leaf or filial node to a parent node thereof,

said substeps being repeated for each of the 2ⁿ regions.

7. A method as claimed in claim 1 in which said second step comprises the substeps of:

discriminating whether or not a subject subregion exists in the 2ⁿ subregions;

setting a leaf flag when the subject subregion is made up solely single kind of region;

adding a specific filial node to the node in the first level of said tree structure corresponding to the subject subregion when the subject subregion is made up of two or more kinds of regions; and

setting a pointer of said specific filial node to a parent node thereof,

said substeps being repeated for each of the 2ⁿ subregions.

8. A method as claimed in claim 7 which further comprises the substeps of:

adding a leaf to a specific leaf corresponding to the subject subregion set with said leaf flag by integrating one of 2ⁿ -1 pattern codes thereto when said substeps are repeated for each of the 2ⁿ subregions; and

setting a pointer of said specific leaf to the parent node thereof.

9. A method of describing an image made up of a plurality of kinds of regions in an n-dimensional space by a tree structure, said method comprising:

a first step of recursively and equally dividing said image in the n-dimensional space into 2ⁿ regions until each of the 2ⁿ regions include two or less kinds of regions, thereby making a first level of said tree having a root node corresponding to said image in its entirety, L nodes connected to said root node and each corresponding to a region with three or more kinds of regions and M leaves connected to said root node or a node and each corresponding to a region with two or less kinds of regions, where L=0, 1, 2, . . . , n, M=1, 2, 3, . . . , n and L +M=n, each of said nodes having branches branching out therefrom and connecting to a filial node or leaf thereof;

a second step of recursively and equally subdividing each of said 2ⁿ regions in the n-dimensional space into 2ⁿ subregions until each subregion includes only one kind of region and for describing only one of two kinds of regions by a tree structure in which each node which degree is one and only having one branch is integrated into a filial node or leaf thereof, thereby making a second level of said tree structure, each node in the second level of said tree structure being added with first division information described by sequential data of 2ⁿ kinds of codes corresponding to position information of each node with respect to a parent node thereof, each leaf in the second level of said tree structure being added with second division information, said second division information describing at least a least significant code of said first division information by 2ⁿ or more kinds of codes which are pattern information of each leaf with respect to a parent node thereof; and

a third step of making a restructuring of the tree at the nodes of each branch to rearrange the node in order so that a node having a largest number of leaves connected thereto is arranged on one side of the tree and a number of leaves connected to the node decreases toward the other side of the tree;

said tree structure describing said image in the first and second levels thereof.

10. A method of describing an image made up of two kinds of regions in an n-dimensional space by a tree structure, said method comprising the steps of:

recursively and equally dividing said image in the n-dimensional space into 2ⁿ regions until each region includes only one kind of region and for describing only one of two kinds of regions by a tree structure having a root node corresponding to said image in its entirety, L nodes connected to said root node and each corresponding to a region with two kinds of regions and M leaves connected to said root node or a node and each corresponding to a region with one kind of region, where L=0, 1, 2, . . . , n, M=1, 2, 3, . . . , n and L+M=n, each of said nodes having branches branching out therefrom and connecting to a filial node or leaf thereof;

integrating out of said nodes a node which degree is one only having one branch into a filial node thereof; and

adding to each of said nodes and leaves division information described by sequential data of 2ⁿ kinds of codes corresponding to position information with respect to a parent node thereof.

11. A method of describing an image made up of two kinds of regions in an n-dimensional space by a tree structure, said method comprising the steps of:

recursively and equally dividing said image in the n-dimensional space into 2ⁿ regions until each region includes only one kind of region and for describing only one of the two kinds of regions by a tree structure having a root node corresponding to said image in its entirety, L nodes connected to said root node and each corresponding to a region with two kinds of regions and M leaves connected to said root node or a node and each corresponding to a region with one kind of region, where L=0, 1, 2, . . . , n, M=1, 2, 3, . . . , n and L+M=n, each of said nodes having branches branching out therefrom and connecting to a filial node or leaf thereof;

integrating out of said nodes a node which degree is one and only having one branch into a filial node thereof;

adding to each of said nodes and leaves division information described by sequential data of 2ⁿ kinds of codes corresponding to position information with respect to a parent node thereof; and

making a restructuring of the tree at the nodes of each branch to rearrange the node in order so that a node having a largest number of leaves connected thereto is arranged on one side of the tree and a number of leaves connected to the node decreases toward the other side of the tree.

12. A method of describing an image made up of two kinds of regions in an n-dimensional space by a tree structure, said image information control system comprising the steps of:

recursively and equally dividing said image in the n-dimensional space into 2ⁿ regions until each region includes only one kind of region and for describing only one of the two kinds of regions by a tree structure having a root node corresponding to said image in its entirety, L nodes connected to said root node and each corresponding to a region with two kinds of regions and M leaves connected to said root node or a node and each corresponding to a region with one kind of region, where L=0, 1, 2, . . . , n, M=1, 2, 3, . . . , n and L+M=n, each of said nodes having branches branching out therefrom and connecting to a filial node or leaf thereof;

integration out of said nodes a node which degree is one and only having one branch into a filial node thereof;

adding to each node which degree is one and remaining leaves first division information described by sequential data of 2ⁿ kinds of codes corresponding to position information with respect to a parent node thereof; and

adding to each of said leaves second division information corresponding to a least significant code of said first division information and described by 2ⁿ or more kinds of codes which are pattern information with respect to a parent node thereof so as to integrate leaves connected to a common parent node.

13. A method of describing an image made up of two kinds of regions in an n-dimensional space by a tree structure, said method comprising the steps of:

recursively and equally dividing said image in the n-dimensional space into 2ⁿ regions until each region includes only one kind of region and for describing only one of the two kinds of regions by a tree structure having a root node corresponding to said image in its entirety, L nodes connected to said root node and each corresponding to a region with two kinds of regions and M leaves connected to said root node or a node and each corresponding to a region with one kind of region, where L=0, 1, 2, . . . , n, M=1, 2, 3, . . . , n and L+M=n, each of said nodes having branches branching out therefrom and connecting to a filial node or leaf thereof;

integrating out of said nodes a node which degree is one and only having one branch into a filial node thereof;

adding to each node which degree is one and remaining leaves first division information described by sequential data of 2ⁿ kinds of codes corresponding to position information with respect to a parent node thereof;

adding to each of said leaves second division information corresponding to a least significant code of said first division information and described by 2ⁿ or more kinds of codes which are pattern information with respect to a parent node thereof so as to integrate leaves connected to a common parent node; and

making a restructuring of the tree at the nodes of each branch to rearrange the node in order so that a node having a largest number of leaves connected thereto is arranged on one side of the tree and a number of leaves connected to the node decreases toward the other side of the tree.

14. A method of describing an image including point information in an n-dimensional space by a tree structure, said method comprising the steps of:

recursively and equally dividing said image in the n-dimensional space into 2ⁿ regions until each region includes a maximum of one point information and for describing only those regions including point information by a tree structure having a root node corresponding to said image in its entirety, L nodes connected to said root node and each corresponding to a region with two kinds of regions and M leaves connected to said root node or a node and each corresponding to a region with one kind of region, where L=0, 1, 2, . . . , n, M=1, 2, 3, . . . , n and +M=n, each of said nodes having branches branching out therefrom and connecting to a filial node or leaf thereof;

integrating a node which degree is one and only having one branch into a filial node thereof; and

adding to each of said nodes and leaves division information described by sequential data of 2ⁿ kinds of codes corresponding to position information with respect to a parent node thereof.

15. A method of describing an image including point information in an n-dimensional space by a tree structure, said method comprising the steps of:

recursively and equally dividing said image in the n-dimensional space into 2ⁿ regions until each region includes a maximum of one point information and for describing only those regions including point information by a tree structure having a root node corresponding to said image in its entirety, L nodes connected to said root node and each corresponding to a region with two kinds of regions and M leaves connected to said root node or a node each corresponding to a region with one kind of region where L=0, 1, 2, . . . , n, M=1, 2, 3, . . . , n and L+M=n, each of said nodes having branches branching out therefrom and connecting to a filial node of leaf thereof;

integrating a node which degree is one and only having one branch into a filial node thereof;

adding to each of said nodes and leaves division information described by sequential data of 2.sup. kinds of codes corresponding to position information with respect to a parent node thereof; and

making a restructuring of the tree at the nodes of each branch to rearrange the nodes in order so that a node having a largest number of leaves connected thereto is arranged on one side of the tree and number of leaves connected to the node decreases toward the other side of the tree.

16. A method of describing an image including point information in an n-dimensional space by a tree structure, said method comprising the steps of:

recursively and equally dividing said image in the n-dimensional space into 2ⁿ regions until each region includes a maximum of one point information and for describing only those regions including point information by a tree structure having a root node corresponding to said image in its entirety, L nodes connected to said root node and each corresponding to a region with two kinds of regions and M leaves connected to said root node or a node each corresponding to a region with one kind of region, where L=0, 1, 2, . . . ,n, M=1, 2, 3, n and L+M=n, each of said nodes having branches branching out therefrom and connecting to a filial node of leaf thereof;

integrating a node which degree is one and only having one branch into a filial node thereof;

adding to each of said nodes and leaves division information described by sequential data of 2ⁿ kinds of codes corresponding to position information with respect to a parent node thereof; and

converting input data into said division information to retrieve a point by pattern matching with the division information of each of said nodes.