1. Field of the Invention
The present invention relates to a method of selection of an object in an N-dimensional frame of reference and to a method of display of the selected object. Selection of the object essentially consists in establishing the list of coordinates of the loci of the reference frame which are considered to be present in said object. It will be understood that the coordinates referred-to in the present invention have a broad meaning: they are in fact octree data organized in an object universe. These octree data, these coordinates, are obtained by decomposition of the universe in accordance with an octree method into father nodes and into son nodes of these father nodes. The invention is mainly directed to the treatment of objects coded numerically in arborescent form of the octree type. Subsequently to this treatment, the coded objects can be displayed, measured, etc . . . . The invention contributes to an improvement in subsequent treatments.
2. Description of the Prior Art
Numerical coding of images in an arborescent form usually referred-to as octree is well-known in many publications such as, for example, in the article by D. J. R. Meagher: "High-speed display of 3D medical images using octree encoding" which appeared in the September, 1981 issue of "Rensselaer Polytechnic Institute Technical Report", or else in the article by the same author entitled "Geometric modeling using octree encoding" which appeared in the review "Computer Graphics and Images Processing", No. 19, June, 1982, pages 129 to 147. As disclosed in U.S. Pat. No. 4,694,404 or in European patent Application published under No. 0,152,741, there is also known a method of three-dimensional (3D) display starting from images of an object coded in octree form. This method essentially consists in forming, from octree data organized in an object universe, the projection of said object in a target plane parallel to a viewing screen. Other methods are known which make it possible from a given octree decomposition to represent the object at another angle of incidence such as a 3/4 rear view, for example, as well as with different lighting conditions.
But all these techniques have in common the utilization of objects already obtained by decomposition of the universe in accordance with an octree method. If necessary and under certain conditions, it is possible to devote attention only to certain parts of the objects thus selected. There are essentially known the partitions of the universe carried out from planes. In accordance with these partitions, portions of the object located on one side of a plane can be eliminated so as to apply the subsequent treatments only to the remaining portions. Furthermore, combinations of planes can lead to determination of restricted sub-universes. The partitions which are the easiest to carry out concern those which are oriented along the three axes of coordinates XYZ of the reference frame. In fact, the octree decomposition is carried out on a numerical volume. A numerical volume represents schematically an object to be studied or to be constructed. This object is defined by an item of information which is representative of a property of the object (in tomodensitometry, this property can be radiological density) associated with the coordinates of determination of the volume element of said object which has this property. The determination is a three-dimensional determination along the three axes XYZ. This determination corresponds to addresses in memories of the memory cells containing the corresponding items of information.
In a known manner, the addresses include address moments which are representative of each coordinate axis. One of the most simple partitions of the objects to be examined therefore consists in extracting from said object all the volume elements whose address moments are related to each other by a linear relation. In fact, such linear relations on the coordinates of the reference frame define planes. For example, it will be possible to extract all the volume elements whose first address moment, which is representative of the coordinate X, is positive.
The coordinates of a volume element in a decomposition of the octree type have a structure which is slightly different from that known in cartesian representation XYZ. A volume element or octant is defined by a composite address constituted as follows. In order to be able to decompose an object contained in a universe cube, a hierarchical dichotomy is performed. To this end, the cube is split into eight equal cubes by dividing said cube into two parallel to each of the six limiting principal planes. Each sub-cube can be similarly divided into eight sub-sub-cubes and so on. There is thus obtained a multilevel hierarchy at whose summit (level 0 by definition) is located the initial universe cube. The first sub-cubes are located at level 1, and so on. The initial cube is known as the father or father node of the eight sub-cubes which are known as son nodes. Each of these son sub-cubes is in turn the father of eight sub-sub-cubes, and so on. FIG. 1 represents this hierarchical dichotomy at the decomposition levels 0, 1 and 2. Decomposition of a cube is always performed by numbering the sub-cubes in the same manner. Thus in the principal cube shown, there are distinguished eight sub-cubes numbered from 0 to 7, the first four being located in a lower plane and the next four being located in an upper plane. Similarly, at the decomposition level number No. 2, the sub-cube 0 has been split up into eight sub-sub-cubes dimensioned 0' to 7'. These sub-cubes are arranged in the same manner as the sub-cubes dimensioned from 0 to 7 were arranged in the principal cube. This permanence of the partition entails the need, in a known manner in the octree technique, to preserve in the address of a node (of a cube at a given level) on the one hand the hierarchical level to which it belongs and on the other hand the respective coordinates of the centers of the son nodes. The result thereby achieved is that the partition of a numerical volume along its principal axes which is readily transposable to a partition according to the address moments of the representation of this numerical volume in memory, is also readily transposable to an octree decomposition of the object.
But a decomposition in planes is not always well adapted. For example, it may be required to display an eye in a numerical volume which is representative in medical engineering of an acquisition of the head. It is understood that it is preferable to approach, in the numerical volume, the shape of the eye by means of a sphere rather than a cube. Should it be desired, for example, to calculate the mean radiological density of said eye, the partition with planes is not very practical. It is possible to enhance the fineness of the representation with planes by creating multifacet volumes and by utilizing properties of inclined planes for extracting information relating to a round portion of an object. But this mode of representation has a disadvantage. It occupies data-processing machines for periods of time which are incompatible with work intentions in real time. In fact, a curved surface such as the eye is more closely imitated as the volume which approaches it has a larger number of facets. The calculation of the planes corresponding to these facets is longer as they are greater in number.
Moreover, the definition of curved surfaces in order to limit objects leads to equations of combination of the coordinates which are at least of the second degree in X, Y or Z. Without going into details, the object approach by curved surfaces requires calculation of multiplication operations by the treatment processors. Multiplication operations are unfortunately too time-consuming, especially if they are carried out on a large scale. These operations also preclude utilization in real time.
The object of the invention is to overcome these disadvantages by nevertheless proposing partitions with curved surfaces comprising, in their cartesian expression, terms of the second degree. But the invention provides a simplification such that it permits calculation in real time. In substance, by replacing in these expressions all the terms of the second degree by constants and by judiciously applying a change of reference frame at each change of hierarchical level of the octree decomposition, one can arrive at a simplified expression which makes it possible, as in the case of partition with planes, to take into consideration only those parts of the object which are located on the correct side with respect to the partition surface. The change of reference frame can be assimilated with an address shift. It will be shown on the one hand that it can be pre-calculated and on the other hand that it involves only binary addition and subtraction operations. The replacement of the terms of the second degree by a constant leads to elimination of all the multiplications which caused a waste of time. Furthermore, curved surfaces can be combined with each other in order to define complex volumes.
USPTO Backgrounds
USPTO Backgrounds