Abstract:
A method for extracting a three-dimensional color vector from a three-dimensional color space in which correlated features are distributed includes steps of projecting the three-dimensional color space on a two-dimensional plane, displaying the two-dimensional plane on a display screen of a display, designating a line segment on the display screen by an input device, and executing the above steps at least two times by changing the angle of projection between the three-dimensional space and the two-dimensional plane to extract the color vector.

Description:
CROSS-REFERENCE TO RELEVANT APPLICATIONS 
     The present application is relevant to copending U.S. patent application Ser. No. 493,447 filed Mar. 14, 1990, and the contents of which are incorporated herein by reference. 
     BACKGROUND OF THE INVENTION 
     The present invention relates to a method for seeking a three-dimensional vector in a three-dimensional feature space, that is, a method for seeking a three-dimensional vector indicating the distribution of features in a three-dimensional space when the features are linearly distributed. More particularly, the present invention relates to a three-dimensional vector extracting method suitable for extracting, from an object region of a color image plotted in a space of three primary colors, a color vector used for the color changing of the object region, that is, a color vector of at least one of a specular reflection vector of the object, a diffuse reflection vector of the object and an ambient vector. 
     The reference &#34;The Measurement of Highlights in Color Images&#34; reported by G. K. Klinker et al. in International Journal of Computer Vision, No. 1, Vol. 2, pp. 7-32 (1988.6) discloses a method which is related the method of the present invention. 
     Statistical methods as well as analytical methods such as principal component analysis and clustering have hitherto been used as methods for seeking the distribution of features in a feature space. Among these methods, it is most customary to use the method of principal component analysis so as to seek the axes of the principal components when there is a correlation between the components of the features. 
     In the case of the principal component analysis, it is necessary to divide the features into a plurality of groups prior to the analysis when there are a plurality of groups of correlated features in the feature space. 
     In the reference cited above, the method of principal component analysis is used to seek, from a three-dimensional feature space, vectors indicating linearly clustering correlated features. That is, in the reference, a plurality of vectors are extracted on the basis of the values of pixels of an object region in a color image plotted in a space of three primary colors. It is assumed that the extracted vectors are connected together at about their start and end points and that the directions of the vectors to be linked are not the same directions, and that the values of all of the vector components are positive. The clustering and plotted points exist in the vicinity of these vectors. In the reference, the vectors are extracted in a manner which will be described below by reference to FIG. 6. 
     First, plotted points are classified. For this purpose, a vector is roughly extracted from a distribution 60 of pixel values in an object region as shown in FIG. 6. A point 61 nearest to the origin of an RGB coordinate system and a point 62 remotest from the origin are extracted, and these two points 61 and 62 are connected by a line segment 63. Then, a point 65 is detected where the distance 64 between that point and the line segment 63 is a maximum. When the value of this distance 64 is larger than a predetermined threshold value, the segment 63 is divided, and the point 65 is selected as a start point and an end point respectively of new segments 66 and 67. Then, the segments 66 and 67 are processed in a manner similar to the processing for the segment 63. The above manner of segment division is repeated until the segment 63 can be finally divided into a plurality of segments, thereby extracting vectors. 
     The classification of the plotted points is such that the distance between each of the individual points and each of the individual segments is detected, and each of the individual points is decided to belong to the nearest segment group. 
     After the classification of the plotted points, the principal component analysis is made for each of the groups, and the axis of the principal component in each group is taken as a vector, thereby determining an accurate three-dimensional vector. 
     The method of principal component analysis used in the reference is excellent in that the number of dimensions need not be limited, and a highly reliable three-dimensional vector reflecting the feature distribution can be obtained when pre-processing for removing, for example, noise is carried out prior to the analysis. However, the method of principal component analysis used in the reference is defective in the points enumerated below. 
     Firstly, when there are a plurality of groups of correlated features in a feature space, it is necessary to carry out, before execution of the principal component analysis, a step of pre-processing for classifying the plotted points in the feature space. This manner of pre-processing in the reference is applicable only when the assumption referred to in the description of the reference is valid with respect to the distribution of features. Thus, the above manner of pre-processing is not universally applicable but differs depending on the distribution of features of an object. Therefore, it is necessary to choose the manner of pre-processing according to the object of vector extraction. 
     Secondly, because an aggregate of numerical data is handled, the result of the pre-processing and also the result of vector or line extraction are generally provided in the form of numerical data, and it becomes necessary to verify these results. Therefore, it is necessary to provide a method for verifying the suitability or validity of both the pre-processing and the extracted vectors or extracted lines. At the same time, a step of processing for executing the verification also becomes necessary. 
     Thirdly, the principal component analysis requires vast steps of computations. 
     SUMMARY OF THE INVENTION 
     With a view to solve the problems of the reference cited above, the present invention intends to provide a method for extracting a three-dimensional vector from a distribution of correlated features in a three-dimensional feature space. 
     It is a first object of the present invention to provide a method for extracting a three-dimensional vector, in which the steps of processing need not be changed depending on the distribution of objective features, and a step of pre-processing for classifying plotted points in the three-dimensional feature space is unnecessary. 
     A second object of the present invention is to provide a three-dimensional vector extracting method in which verification for the result of vector extraction is basically unnecessary. 
     A third object of the present invention is to provide a three-dimensional vector extracting method in which a three-dimensional vector can be extracted by a sequence of simple processing steps without requiring vast steps of computations. 
     In the present invention, the following sequence of processing is executed so as to attain the first, second and third objects described above: 
     (1) Steps of projecting a three-dimensional space on a two-dimensional plane, displaying the two-dimensional plane on a display, and specifying a line segment on the display by an input device are repeated at least two times while changing the angle of projection between the three-dimensional space and the two-dimensional plane. 
     (2) When the line segments are to be specified on the display, an area is detected where feature plotted points cluster on the two-dimensional plane. On the basis of the specified two segments on the two-dimensional plane, planes each including one of the two segments in the three-dimensional space are computed, and the line of intersection between these two planes is sought. 
     (3) The point of, intersection between a straight line, passing the start point of one of the two segments on the two-dimensional plane and perpendicularly intersecting the two-dimensional plane in the three-dimensional space, and the line of intersection between the two planes in the three dimensional space is determined as the start point of the vector, and the point of intersection between a straight line, passing the end point of one of the two segments and perpendicularly intersecting the two-dimensional plane in the three-dimensional space, and the line of intersection between the two planes in the three dimensional space is determined as the end point of the vector. 
     (4) When projecting the three-dimensional space on the two-dimensional plane, the positional relation between a point in the three-dimensional space and the two-dimensional projection plane is fixed, and, as the projection angle, an angle of rotation of the three-dimensional space around the fixed point is used. 
     (5) The center of rotation of the three-dimensional space is the center of gravity of the three-dimensional space which is finite. 
     (6) In the step of projecting the three-dimensional space on the two-dimensional plane while changing the projection angle, the input device supplies parameters on which the projection angle is dependent in both the horizontal and vertical directions of the two-dimensional projection plane displayed on the display. 
     (7) In the step of supplying the parameters, a pattern having a cross depicted in a rectangular area is displayed on the display, and, regarding the pattern as a two-dimensional coordinate system having its origin at the cross point of the cross and using the horizontal and vertical directions of the two-dimensional coordinate system as the parameters of the projection angle in the horizontal and vertical directions respectively, a point is specified in the displayed pattern. 
     (8) In the step of changing the projection angle, a parameter β, on which the projection angle is dependent, is specified by the input device so that, when the value of the projection angle is α at a given time, the value of the projection angle is changed next to α&#39; given by α&#39;=α+f(β). 
     (9) In the step of seeking the vector, a rotation matrix of the rotation is used. 
     Also, for the purpose of attaining the second object described above, the extracted vector or straight line is projected and displayed on the two-dimensional plane. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a flow chart showing the sequence of processing in an embodiment of the method according to the present invention. 
     FIG. 2 illustrates a three-dimensional vector displayed on a CRT used for the practice of the embodiment of the method shown in FIG. 1. 
     FIGS. 3A, 3B, 3C and 3D illustrate rotation of a three-dimensional space. 
     FIG. 4 is a block diagram of a computer system used for the practice of the embodiment of the method shown in FIG. 1. 
     FIGS. 5a, 5B and 5C illustrate the principle of a method of the present invention. 
     FIG. 6 illustrates the principle of a prior art method. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     For a better understanding of the present invention, its basic principle will be first described by reference to FIGS. 5A, 5B and 5C. 
     A straight line in a three-dimensional space can be given by a line of intersection between two planes. Also, when a three-dimensional space is projected on a projection plane perpendicular with respect to a plane in the three-dimensional space, that plane is given by a straight line on the projection plane. Further, when the three-dimensional space is projected on the projection plane, a straight line perpendicular with respect to this projection plane is given by a point on the projection plane. 
     Therefore, in a three-dimensional space in which distributed features are correlated, a three-dimensional vector indicating the correlation of the distributed features can be sought by the steps of processing described by reference to FIGS. 5A to 5C. 
     As shown in FIG. 5A, a three-dimensional feature distribution space projected on a projection plane is first displayed on a display 513, and, on the displayed projections plane, a line segment 53 is specified on an area 50 where feature plotted points cluster linearly. When_the segment 53 is specified as shown in FIG. 5A, a plane 54 including a three-dimensional vector 51 to be extracted from the three-dimensional feature space is determined as shown in FIG. 5C. Then, as shown in FIG. 5B, the three-dimensional feature space is projected again while changing the projection angle, and a line segment 59 is similarly specified on an area on the projection plane where the plotted points linearly cluster. When the segment 59 is so specified, another plane 510 is determined as shown in FIG. 5C. Then, when a line of intersection 52 between these two planes 54 and 510 in the three-dimensional feature space is sought, this intersection line 52 is a straight line indicating the correlation of the RGB components. Also, this intersection line 52 includes the three-dimensional vector to be extracted. The terminal points 55 and 56 of the segment 53 specified on the projection plane are located on respective straight lines 57 and 58 on the plane 54 in the three-dimensional feature space, and the intersections between these straight lines 57, 58 and the intersection line 52 in the three-dimensional feature space provide the start and end points respectively of the three-dimensional vector 51. 
     It is arranged so that the projection angle can be freely changed. After the determination of the vector 51 and the straight line 52 in the three-dimensional feature space or after the determination of the segments 53 and 59 on the two-dimensional projection plane, they are immediately displayed on the display screen of the display 513, so that the suitability or validity of the vector 51, the straight line 52 and the segments 53, 59 thus determined can be confirmed in real time. 
     Unlike the prior art method for vector extraction by means of numerical processing, the present invention carries out the vector extraction by means of interactive processing. Thus, according to the present invention, the suitability or validity of an extracted three-dimensional vector or an extracted straight line can be easily visually verified in real time in the course of the extraction of the vector or the straight line. Therefore, the vector or the straight line can be extracted with high reliability. 
     Further, simultaneously with the extraction of the three-dimensional vector or the straight line, the feature plotted points are naturally, visually classified. Therefore, even when there are a plurality of correlated feature groups, the pre-processing for the purpose of plotted point classification is unnecessary. 
     Also, the present invention can be applied to the pre-processing carried out prior to the principal component analysis so as to generally simplify the classification of the feature plotted points. In such a case, after the extraction of vectors, the individual feature plotted points are classified so that each of them belongs to a vector nearest thereto. 
     An embodiment of the method according to the present invention will now be described in detail by reference to FIGS. 1 to 4. In this embodiment, a vector Vd of a diffuse reflection, a vector Vs of a specular reflection and a vector Va of an ambient shown in FIG. 2 are extracted from a RGB (three primary colors) feature space where pixel values C (R, G, B) (0 ≦R, G, B 23 255; R, G, Bεintegers) of an object region in a color image are plotted. 
     FIG. 1 is a flow chart showing the sequence of processing executed in the embodiment of the present invention, FIG. 2 illustrates the vectors displayed on a CRT used for the practice of the embodiment shown in FIG. 1, FIGS. 3A to 3D illustrate rotation of the three-dimensional space, and FIG. 4 is a block diagram of a computer system used for the practice of the embodiment shown in FIG. 1. It is to be noted that the flow chart shown in FIG. 1 represents the sequence of processing executed until one of the vectors is extracted. Thus, it is apparent that the processing sequence shown in FIG. 1 is repeated until all of the plural vectors are extracted. 
     First, the vector Vd shown in FIG. 2 is extracted according to the flow chart shown in FIG. 1. Subsequently, the vectors Vs and Va are entirely similarly extracted. Therefore, extraction of the vector Vd will only be described in detail herein by way of example. 
     The individual steps shown in the flow chart of FIG. 1 will now be described by reference to FIGS. 3A to 3D and 4. 
     (1) Step 11 
     A three-dimensional feature, that is, three-primary color pixel values stored in a memory 41 shown in FIG. 4 are projected on a CRT 43 shown in FIG. 4 to be displayed on the display screen 21 of the CRT 43, as shown in FIG. 2. In-an initial stage of projection, a two-dimensional projection plane 31 is such that it is parallel to the R-G plane of a cube 32 in the form of the three-dimensional three-primary color space and perpendicular to the B-axis of the cube 32, as shown in FIGS. 3A and 3B. 
     Consider now the rotation of the cube 32 around its center of gravity 33 and a rotation matrix M when the positional relation between the two-dimensional projection plane 31 and the center of gravity 33 of the cube 32 in the form of the three-primary color space is fixed. A three-dimensional xyz coordinate system (-122.5 ≦x, y, z ≦122.5; x, y, z ε real numbers), in which the origin is the center of gravity 33 of the cube 32 in the form of the three-dimensional three-primary color space, and the directions of the x-axis, y-axis and z-axis are the same as the directions of the R-axis, G-axis and B-axis respectively of the cube 32 in the initial stage of projection, is shown in FIG. 3D. Thus, the rotation of the cube 32 relative to this xyz coordinate system may be considered. It is supposed that the values of x 0 , Y 0  and z 0  relative to the values of R 0 , G 0  and B 0  in the initial stage of projection are given by the following equation: ##EQU1## where x 0 , Y 0 , z 0  ; and R 0 , G 0 , B 0  are coordinate values of the origins of the xyz three-dimensional coordinate system and the RGB three-dimensional three-primary color coordinate system respectively, and the value of k is k=122.5. 
     On the two-dimensional projection plane, an xy two-dimensional coordinate system is considered which is equivalent to the result of projection of the xyz three-dimensional coordinate system on the projection plane. 
     The rotation matrix M is stored in the memory 41 shown in FIG. 4. The initial value of this rotation matrix M is that of a unit matrix I, 
     (2) Step 12 
     A mouse 44 shown in FIG. 4 is used to input parameters which determine the angle of rotation of the three-dimensional space around the center of gravity 33 shown in FIG. 3B. As shown in FIG. 2, a two-dimensional rectangular area 22 is displayed on the display screen 21 of the CRT 43. This rectangular area 21 has its center located at the origin of the two-dimensional coordinate system displayed on the CRT display screen and is called hereinafter a rotation indicator 34 in FIG. 3C. The horizontal axis (h-axis) component and, the vertical axis (v-axis) component of the rotation indicator 34 shown in FIG. 3C are used as parameters h and v corresponding to increments hd and vd of the angle of rotation of the cube 32 relative to the y-axis and the angle of rotation of the cube 32 relative to the x-axis, respectively, in FIG. 3D. The mouse 44 connected to a bus line 45 shown in FIG. 4 is used to indicate a point (h, v) in the rotation indicator 34 shown in FIG. 3C. 
     (3) Step 13 
     The parameters h and v are used in a monotonically increasing function f so as to compute the rotation angle increments hd and vd by a CPU 42 shown in FIG. 4, as follows: ##EQU2## Using the rotation angle increments hd and vd thus computed rotation increment angle matrices D h  and D v  are obtained as follows: ##EQU3## 
     When the rotation angle increment matrix D h  relative to the y-axis is first considered, the composite rotation angle increment matrix D is given by 
     
         D=D.sub.v D.sub.h                                          (5) 
    
     On the basis of this rotation angle increment matrix D and the rotation matrix M stored already in the memory 41 shown in FIG. 4, a new rotation matrix M&#39; indicating the rotation from the initial stage is computed by the CPU 42 shown in FIG. 4, as follows: 
     
         M&#39;=D·M                                            (6) 
    
     Since M=I as described already, the rotation matrix M&#39; is expressed as M&#39;=D. The matrix M&#39; is substituted for M. M is stored again in the memory 41 shown in FIG. 4. 
     Not only the rotation angle increments from the present rotation angle can be specified, but also the angle of rotation from the initial stage of projection can be primarily specified by an array of buttons 23 on the CRT display screen 21 shown in FIG. 2. The buttons 23 designated &#34;R-G&#34;, &#34;G-B&#34;, &#34;B-R&#34; and &#34;I&#34; in FIG. 2 correspond respectively to the cases where &#34;the R-G plane is parallel to the projection plane&#34;, &#34;the G-B plane is parallel to the projection plane&#34;, &#34;the B-R plane is parallel to the projection plane&#34;, and &#34;the straight line R=G=B is perpendicular with respect to the projection plane.&#34; The rotation is specified by selecting the button area 23 by the mouse 44 shown in FIG. 4. 
     (4) Step 14 
     The rotation matrix M stored in the memory 41 shown in FIG. 4 is read out to two-dimensionally project and display the three-dimensional three-primary color (RGB) space on the display screen 21 of the CRT 43 as shown in FIG. 2. 
     (5) Step 15 
     When the operator viewing the distribution on the projection screen decides that the three-primary color space is sufficiently linearly distributed on the projection plane, the steps starting from &#34;(6) Step 16&#34; are executed. Otherwise, the steps ranging from &#34;(2) Step 12&#34; to &#34;(5) Step 15&#34; are executed again. 
     (6) Step 16 
     On an area 24 where the distribution clusters on the CRT display screen 21 as shown in FIG. 2, the mouse 44 is used to specify a line segment P a1  P a2  on the CRT 43 shown in FIG. 4. The specified segment P a1  P a2  is displayed on the CRT display screen 21 
     (7) Step 17 
     When the operator decides that the segment P a1  P a2  suitably expresses the feature of the distribution, the steps starting from &#34;(8) Step 18&#34; are executed. Otherwise, &#34;(6) Step 16&#34; is repeated. 
     (8) Step 18 
     On the basis of the segment P a1  P a2  displayed on the xy two-dimensional projection plane, the plane in the xyz three-dimensional space is computed by the CPU 42 shown in FIG. 4. Also, on the basis of the rotation matrix M stored in the memory 41 shown in FIG. 4, the CPU 42 shown in FIG. 4 computes the equation of the plane in the RGB three-dimensional coordinate system. The equation of the plane thus computed is stored in the memory 41. 
     The plane in the xyz three-dimensional space is first computed by the CPU 42 shown in FIG. 4. Suppose that the points P al  and P a2  on the xy two-dimensional projection plane are given by 
     
         P.sub.al =(h1v1)                                           (7) 
    
     
         P.sub.a2 =(h2v2)                                           (8) 
    
     (-122.5≦h1, h2, v1, v2≦122.5) 
     When a line u normal to the plane is expressed as u=(a, b, c), the equation of the plane is given by ##EQU4## 
     Then, the computed plane is transformed into the RGB coordinate system. The RGB three-dimensional space has been rotated from the initial stage by rotation matrix M. Therefore, the plane given by the equations (9) and (10) is transformed by an inverse matrix M -1  of the rotation matrix M so as to rotate the RGB space in the inverse direction. 
     First, the vector of the normal u is transformed as follows: 
     
         u.sup.0 =M.sup.-1 =(a.sup.0, b.sup.0, c.sup.0)             (11) 
    
     Similarly, the coordinate values of the point P(h1, v1, 0) on the plane are also transformed as follows: 
     
         P&#39;=M.sup.31 1 P=(x&#39;,y&#39;,z&#39;)                                 (12) 
    
     Therefore, from the equation (1), the point P&#39;(x&#39;,y&#39;, z&#39;) is turned into a point p 0  (r 0 , g 0 , b 0 ) having the following coordinate values in the RGB coordinate system: 
     
         r.sup.0 =x&#39;+k, g.sup.0 =y&#39;+k, b.sup.0 =z&#39;+k                (13) 
    
     Thus, the plane given by the equations (9) and (10) is now given in the RGB coordinate system by 
     
         a.sup.0 R+b.sup.0 G+c.sup.0 B-a.sup.0 r.sup.0 -b.sup.0 g.sup.0 -c.sup.0 b.sup.0 =0                                                (14) 
    
     (9) After the plane described above is determined, another plane in the RGB coordinate system is similarly determined in the steps 19 to 115 by changing the angle of rotation and by specifying another line segment on the xy two-dimensional projection plane. 
     (10) Step 116 
     For the start and end points of one of the segments specified on the xy two-dimensional projection plane, equations of two straight lines passing these points respectively in the three-dimensional three-primary color space are to be sought. From the equations (7) and (8), two suitable points on each of two straight lines corresponding to the straight lines to be sought in the xyz three-dimensional coordinate system can be determined. For the start point P a1  of the segment P a1  P a2 , these two points are determined as follow. ##EQU5## Then, as in the case of the previous manner of computation of the plane, an inverse matrix M -1  of the rotation matrix M is used to turn the equation (15) into the following equation (16) by inverse rotation: ##EQU6## 
     Thus, from the equation (1), the points P a11  and P a12  in the RGB coordinate system are now expressed as follows: ##EQU7## Therefore, in the RGB coordinate system of the three-dimensional three-primary color space, the straight line passing the two points shown in the equation (17) corresponds to the straight line passing the terminal point P a11  of the segment specified on the two-dimensional projection plane. 
     Similarly, in the case of the end point P a2  of the segment, the line passing this point in the RGB coordinate system of the three-dimensional three-primary color space is sought. 
     (11) Step 117 
     The line of intersection between the two planes given by the equation (14) is sought. 
     (12) Step 118 
     The points of intersection between the line of intersection described above and the two straight lines passing the respective terminal points P a1  and P a2  are sought. These points of intersection provide the start point and the end point of the vector. Because the points of intersection are not necessarily accurately detected due to a computation error, the nearest points on an intersection line between planes to the straight lines are selected. This step is unnecessary when the computation of the line of intersection including the vector Vd is required, but the vector Vd itself need not be computed. 
     (13) Step 119 
     The vector or the straight line is projected and displayed on the CRT 43 shown in FIG. 4 so as to confirm the result of extraction. (In the case of the projection of the straight line, the line is suitably clipped so that it-is to be contained in the three-dimensional three-primary color space.) After the transformation of the vector from the RGB coordinate system to the xyz coordinate system, the vector is rotated by the rotation matrix M stored in the memory 41 shown in FIG. 4 before being projected. 
     (14) Step 120 
     When the operator decides that the extracted vector displayed on the CRT 43 suitably represents the distribution, the vector extraction is ended, and the step 120 is followed by &#34;(15) Step 121&#34;. Otherwise, the step 120 is followed by &#34;(1) Step 11&#34;, and the vector Vd is extracted again. 
     (15) Step 121 
     The extracted vector Vd is stored in the memory 41 shown in FIG. 4. 
     By the above steps, the vector Vd or the line including the vector Vd is sought. Thereafter, as in the case of the extraction of the vector Vd, the other vectors Vs and Va shown in FIG. 2 are similarly extracted by the sequence of processing from &#34;(1) Step 11&#34; to &#34;(15) Step 121&#34; shown in FIG. 1. 
     Thus, even when a plurality of three-dimensional features are correlated with one another, the vectors can be extracted by repeatedly executing the sequence of processing described above. 
     It will be understood from the foregoing detailed description of the method and apparatus of the present invention that a three-dimensional vector and a straight line can be highly reliably, simply and accurately extracted within a short time from a space of correlated three-dimensional features without the necessity for selecting a specific processing sequence depending on the object.