JPH0644363A - Method and device for processing distance image - Google Patents

Abstract

PURPOSE:To eliminate necessity for previously specifying relation between a coordinate system, where an object is positioned, and the coordinate system of an image. CONSTITUTION:This distance image processing method is provided with a process (S303) to transform the form of an inputted distance image and to normalize it with respect to respective axes, arithmetic process (S306, 308, 317, 319, 321, 323 and 325) to prepare data expressing the character of an object surface described by the distance image by calculating the value of the transformed distance image, and display process (S322, 324 and 326) to display image information expressing the character of the object surface based on the data prepared by the arithmetic process.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a range image processing method and a range image processing method for creating information indicating the features of the surface shape of a three-dimensional object represented by the range image from the range image input by a range image input device. It relates to the device.

[0002]

2. Description of the Related Art A range image processing method in which a range image is a processing target and information indicating characteristics of the surface shape of a three-dimensional object in the range image is detected is described in, for example, the following document "Naoko Yokoya, Martin".
D. Levin: “Hybrid method for distance image segmentation based on differential geometric features”, Transactions of Information Processing Society of Japan, Vol.
30, No. 8, pp. 944-953 (1989) ”.

[0003]

However, in the conventional range image processing method, the relationship between the coordinate system in which the object is placed and the coordinate system of the image is not defined, and the aspect ratio in each coordinate axis direction, etc. There was a problem that the parameter of 1 had to be given for each process.

[0004]

The distance image processing method of the present invention has been invented in view of the above points, and a step of converting the type of an input distance image and normalizing each axis. And a calculation step of calculating the value of the converted distance image to create data representing the property of the object surface described by the distance image, and the object surface based on the data created by the calculation step. And a display step of displaying image information representing the property of.

The distance image processing apparatus of the present invention further comprises an input means for inputting the distance image data, a normalization means for converting the type of the distance image input by the input means, and normalizing each axis. Based on the data created by the computing means, computing the value of the distance image data converted by the normalizing means to create data representing the property of the object surface described by the distance image. , Display means for displaying image information representing the property of the surface of the object.

[0006]

[Embodiments] Before describing the processing procedures of the embodiments of the present invention in detail below, the words are simply defined. A "distance image" is an object surface measured by a distance measuring sensor. It is a distance image given the vertical distance (parallel projection) between each point and the reference plane. As the data format, the distance (Z value) is stored at each point on the (X, Y) square two-dimensional grid. Recently
It is data that has begun to be used in the fields of Computer Vision and Computer Graphics.

(First Embodiment) A first embodiment of the present invention will be described in detail below with reference to the drawings.

FIG. 1 is a block diagram showing the basic arrangement of a distance image processing system according to this embodiment.

In the figure, 1 is a program memory for storing various processing procedures, 2 is a data memory for storing information necessary for processing of this system, and input / output data, 3 is a program memory 1 The CPU is for controlling various parts of the apparatus by performing various processes in accordance with the processing procedure stored in.

Reference numeral 4 denotes a display unit for displaying a 3D shape model obtained by this system and interactively displaying an instruction from the user. In this embodiment, it is assumed that the display unit is a multi-window type display unit. Reference numeral 5 is a mouse for inputting a command from the user. A keyboard (KB) 6 is used by a user to create a program or input a command to the system. Further, 7 is a laser range finder, which measures the vertical distance between each point on the object surface and the reference surface and inputs a distance image.

FIG. 2 is a diagram showing stored contents of the program memory 1 and the data memory 2. In the program memory 1 of FIG. 2A, 201 is an axis normalization program that converts the type of a range image and normalizes each axis. 20
2 is a jump edge detection program for detecting jump edges from a distance image. 203 is a primary partial differential calculation program for calculating a primary partial differential from a range image. 204 is
A secondary partial differential calculation program that calculates a secondary partial differential from a range image. Reference numeral 205 is a local first-order plane approximation program that approximates the range image to a local first-order plane and calculates the coefficient of the equation. 206 is a local quadratic surface approximation program that approximates a range image to a local quadric surface and calculates the coefficient of the equation. 207 is a Gaussian curvature calculation program that calculates Gaussian curvature. 208 is an average curvature calculation program for calculating the average curvature. Reference numeral 209 is a normal curvature calculation program for calculating a normal curvature. 210 is a curvature radius calculation program for calculating the curvature radius. Reference numeral 211 is a Gaussian curvature code determination program for determining the sign of Gaussian curvature. Reference numeral 212 is an average curvature sign determination program for determining the sign of the average curvature. 213
Is a surface type discriminating program that discriminates the surface type by the combination of the sign of Gaussian curvature and the sign of average curvature. A normal vector calculation program 214 calculates a unit normal vector from the first partial differential image. Reference numeral 215 is a roof edge detection program for detecting the roof edge from the unit normal vector. The processing of each program will be described later.

Further, in the data memory 2 of FIG. 2B, reference numeral 221 denotes an input range image input by a range image input device or the like. 222 is a jump edge image detected from the distance image. 223 is a first partial differential image detected from the distance image. 224 is 2 detected from the range image
Second partial differential image. 225 is a coefficient image detected from the distance image. 226 is the calculated Gaussian curvature image. 227
Is the calculated average curvature image. 228 is the calculated normal curvature image. 229 is the calculated radius of curvature image. 230
Is a normal vector image that represents the calculated unit normal vector. 231 is the calculated Gaussian curvature code image. 232
Is the calculated mean curvature code image. 233 is the calculated face type image. 234 is a calculated roof edge image.

FIG. 3 is a flow chart showing the flow of this embodiment.

The flow of processing of the entire embodiment will be described with reference to the flowchart of FIG.

At the start of this process, it is assumed that the range image has already been input and stored in the data memory 2 by measuring the object with the laser range finder 7, for example. Further, the distance image to be the subject of this processing is not limited to the one based on such actual measurement, but may be artificial data obtained from an image database or the like. Here, the method of acquiring the range image is detailed in the following document. Iguchi, Sato: "Three-dimensional image measurement", Shoshodo, (1990).

As the first process, the range image data 221 stored in the data memory 2 is taken out (step S301) and displayed on the display unit 6 (step S302). Next, according to the axis normalization program 201, the range image type is converted and each coordinate axis is normalized (step S303). Thus, in the calculation below,
This converted range image is used. Hereinafter, the jump edge is detected and displayed according to the jump edge detection program 202 (steps S304 to S3).
05). According to the primary partial differential calculation program 203 and the secondary partial differential calculation program 204, respectively, primary and secondary partial differentials are calculated and the values are displayed (step S306).
~ 309). According to the local first-order plane approximation program 205 and the local quadratic surface approximation program 206, it is applied to the local first-order plane and the second-order curved surface, the coefficients of the equations representing the plane and the curved surface are obtained, and the results are displayed (step S310-S1010). Three
12). Further, using the values of the first partial differential data 223 and the second partial differential data 224 calculated according to the programs 207 to 211 and 214, Gaussian curvature, average curvature,
The normal curvature, the radius of curvature, and the unit normal vector are calculated and displayed (steps S313 to 314, 317 to 320, 32).
7-330). Furthermore, the curvature code determination program 211,
According to 212, code maps 231 and 232 are created and displayed from the obtained Gaussian curvature 226 and average curvature 227 (steps S321 to 324). Further, according to the surface type discriminating program 213, by the values of the two curvature codes,
Distinguishing the type of surface, class name (number) of the surface type for each pixel
Is displayed (steps S325-32)
6). Further, according to the roof edge detection program 215, the roof edge is detected from the calculated unit normal vector 230 and displayed (steps S315 to 316).

Each processing will be described in detail below.

Normalization of each coordinate axis (step S303) The actual length corresponding to one pixel in the x-axis direction of the input image,
The density image is output so that the actual length corresponding to one pixel in the y-axis direction matches the actual length corresponding to one quantum unit in the z-axis direction. Each pixel of the output image is
It has a float value.

Now, the actual length corresponding to one pixel in the x-axis direction and the actual length corresponding to one pixel in the y-axis direction are both actual lengths corresponding to one quantum unit in the Δx and z-axis directions. Δ
If z, the value z of each pixel of the input range image
_i (x, y) is transformed to the next z _o (x, y).

[0020]

[Outer 1]

In the subsequent processing, this converted z is used.

Jump Edge Extraction (Step S304) In the input image, a portion where the distance from the viewpoint is discontinuous is detected. The maximum value of the distance difference in the vicinity of 8 and the value larger than the threshold value are detected. Threshold
Then, JumpEdge of the following equation is given as the value of each pixel. JumpEdge (x, y) = Max {| Z (x, y) -Z (x + k, y + l) |: -1≤k, l≤1} (1) Fitting by a local plane (step S304 ) Approximate the surface to a local first-order plane and calculate the parameters of the equation. That is, the object surface S of the range image =
Calculate each coefficient of (x, y, -z (x, y)) by the least squares approximation using the window of winsize ² on the plane ax + by + c = -z.

The operator for calculating each coefficient is determined as follows. winsize is the operator's window size (the number of pixels on one side of the square window), and any positive odd number.

A · C = B (2)

[0025]

[Outside 2]

Considering a window of size winsize = (2w + 1) shown in FIG. 4, and setting the origin at the center of this window,

[0027]

[Outside 3] _Assuming that each element is (e _ij ),

[0028]

[Outside 4] That is,

[0029]

[Outside 5] As an example winsize = 3, and 5 (3 * 3, and 5 *
The operator of the plane fitting of 5) is shown.

(A) Window size 3 * 3 (winsize
= 3, w = 1) Substituting w = 1 into equation (6), E (that is, e ₁₁ , e ₂₂ , e
₃₃ ), (x ₁ , x ₂ , ・ ・ ・, x _n ), (y ₁ , y ₂ , ・ ・ ・ y _n )
Is substituted into the equation (8) to obtain the next operator, and this operator is multiplied by B (that is, the range image).

[0031]

[Outside 6] (B) Window size 5 * 5 (winsize = 5, w =
In the case of 2), the following operator is obtained in the same manner as in (a) above.

[0032]

[Outside 7]

Fitting with local quadric surface (step S312) The object surface S = (x, y, -z (x, y)) of the range image is converted into a quadric surface ax ² + by ² + cxy + dx + ey +. Fit each coefficient to f = -z by least square approximation and calculate each coefficient.

The operator for calculating each coefficient is obtained by the same idea as the fitting by the local plane described above. Although detailed description is omitted here, FIG. 5 shows two types of operators.

Calculation of First-Order and Second-Order Partial Derivatives (Steps S306 and 308) First-order or second-order partial derivatives are calculated from the range image by the following three methods. (1) Directly obtained by partial differential operator, (2) Obtained from the coefficient of the fitted local plane equation, (3) Obtained from the coefficient of the fitted local quadratic surface equation. (1) Function to directly obtain from the original image Fig. 5 shows two types of partial differential operators as an example. (2) Function to obtain first partial differential from the coefficients of the fitted local plane. Calculate using the following method. n and m are operator sizes (the number of pixels on one side of the window). As shown in FIG. 7, n × m windows of size n × m including the target point are prepared, and each of them is subjected to the method described in the description of the fitting by the local quadratic plane, and -z (x, y) = ax It is similar to + by + c. The window with the smallest variance of the absolute value of the error is selected from the n × m windows, and the differential value of the target point is obtained from the equation of this window.

For a plane, the fitted plane equation ax + by + c =
The following formula is obtained by calculating the partial differential value from -z.

Z _x = -a Z _y = -b (9) (3) Function for obtaining partial differential from coefficient of fitted local quadratic surface A differential value of a certain point of interest is calculated by the following method. n and m are operator sizes (the number of pixels on one side of the window). As shown in FIG. 6, n × m windows of size n × m including the target point are prepared, and each of them is subjected to the method described in the explanation of the fitting by the local quadric surface, -z (x, y) = ax. It is similar to + by + c.
The window with the smallest variance of the absolute value of the error is selected from the n × m windows, and the differential value of the target point is obtained from the equation of this window. In the case of plane, fitted quadric surface expression ax ² + by ² + cxy +
The following formula is obtained by calculating the partial differential value from dx + ey + f = -z.

Z _x = −2ax-cy-d Z _y = −2by-cx-e Z _xx = 2a Z _yy = 2b Z _xy = c (10) Normal vector calculation (step S313) Local surface A normal vector of a tangent plane is calculated as a unit vector of size 1.

The input image is a first partial differential image.

The x, y and z components of the unit normal vector are calculated based on the following equations. Unit normal vector N (x, y,
z) = (N ₁ , N ₂ , N ₃ ) N ₁ = Z _x / (Z _x ² + Z _y ² +1) ^1/2 N ₂ = Z _y / (Z _x ² + Z _y ² +1) ^1/2 N ₃ = -1 / (Z _x ² + Z _y ² +1) ^1/2 (11) where Z _x is the first derivative of the x component of the distance data, Z _y
Is the first-order derivative of the y component of the distance data.

Equation (11) is based on the following calculation. The range image surface treated by this method is S = (x, y, -z (x, y)) The first partial differential S _x = (1, 0, -Z _x ) by the x component of S and the y component of S As the outer product of the first partial differential S _y = (1, 0, -Z _y ), the normal vector of the following equation is obtained.

N = (Z _x , Z _y , −1) (12) If this is a unit vector of size 1, then equation (11) is obtained.

Roof edge extraction (step S315) A refraction point at a distance from the viewpoint is extracted. The input image is a normal vector image. The maximum value of the angular difference between the unit normal vectors in the vicinity of 8 and the value larger than the threshold value threshold are detected. The value of each pixel is given by Roof Edge of the following equation.

RoofEdge (x, y) = Max {| N (x, y) · N (x + k, y + 1) |: -1 ≦ k, l ≦ 1} (13) where N ( x, y) is the following normal vector.

N (x, y) = (N ₁ (x, y), N ₂ (x, y), N ₃ (x, y)) N ₁ (x, y) is x of the unit normal direction vector The component image N ₂ (x, y) is the y component image of the unit normal direction vector N ₃ (x, y) is the z component image of the unit normal direction vector Gaussian curvature calculation (step S317) The Gaussian curvature K is calculated by substituting it in the formula.

[0046]

[Outside 8] However, Z _x is the first partial differential due to the x component of the distance data Z _y is the first partial differential due to the y component of the distance data Z _xx is the second partial differential due to the x component of the distance data Z _yy is The secondary partial differential Z _xy by the y component of the distance data is the secondary partial differential average curvature calculation by the x and y components of the distance data (step S317) Substituting each partial differential value into the following equation, the average curvature Calculate H.

[0047]

[Outside 9] However, Z _x is the first partial differential due to the x component of the distance data Z _y is the first partial differential due to the y component of the distance data Z _xx is the second partial differential due to the x component of the distance data Z _yy is The second partial differential Z _xy based on the y component of the distance data is the second partial differential based on the x and y components of the distance data. Gaussian curvature code map creation (steps S321, 32)
2) Let kimg (x, y) be the input Gaussian curvature image, and thk be the threshold value (float) that determines the sign. Output an image with the following class assigned to each pixel.

Considering kimg (x, y) <− thk as Gaussian curvature is negative, class 1 −thk <kimg (x, y) <thk is considered as Gaussian curvature 0, and class 2 kimg (x, y) )> Thk, class 3 average curvature code map creation assuming that Gaussian curvature is positive (steps S323, 324) himg (x, y) average curvature image input, thh is a threshold value (float) that determines the sign Suppose An image in which the following class is given to each pixel is output.

Class 1 -thh <himg (x, y) <thh is regarded as having a mean curvature of 0, and class 2 himg (x, y) is considered as himg (x, y) <-thh. )> Thh, assuming that the average curvature is positive Class 3

Surface Type Classification (Steps S325, 326) The surface is classified into eight surface types based on the theory of differential geometry. thk and thh are thresholds that determine the sign. Here, the differential geometry of curved surfaces is explained in detail in the following literature. Tadatsugu Adachi: "Outline of Differential Geometry", Baifukan, (1976) Shoshichi Kobayashi: "Differential Geometry of Curves and Phases", Shokado, (19
77) Homma, Okabe: "Introduction to Differential Geometry and Topology-", Basic Mathematics Series 6, Shinyisha (1979) Moreover, the following is an example of using this for the segmentation of range images. Yokoya, Martin D. Levine: “Hybrid Method for Distance Image Segmentation Based on Differential Geometric Features”, Information Theory, VOL.
30 No.8 pp945-953 (1989) Paul J. Besl: “Surfaces in range image understand
ing ”, Springer-Verlag, (1988) Besel, PJ and Jain, RC:“ Invariant surface
characteristics for 3Dobject recognition in range
images ”, CVGIP, 33, pp. 33-80, (1986) An image in which the following eight classes are given to each pixel by the sign of the Gaussian curvature image kimg (x, y) and the average curvature image himg (x, y) Is output.

Kimg (x, y)> thk and himg (x, y) <− thh class 1 kimg (x, y)> thk and himg (x, y)> thh class 2 −thk <kimg (x, y ) <Thk and himg (x, y) <-thh class 3 -thk <kimg (x, y) <thk and himg (x, y)> thh class 4 -thk <kimg (x, y) <thk and- thh <himg (x, y) <thh Class 5 kimg (x, y) <-thk and -thh <himg (x, y) <thh Class 6 kimg (x, y) <-thk and himg (x, y ) <-Thh Class 7 kimg (x, y) <-thk and himg (x, y)> thh Class 8 kimg (x, y)> himg (x, y) ² (prohibition area) Class 0 Class 1 point Is a negative elliptic point (K> 0, H <0), class 2
Points are positive elliptic points (K> 0, H> 0), points of class 3 are negative paraboloids (K = 0, H <0), and points of class 4 are positive paraboloids (K = 0, H). > 0), class 5 points are flat points (K = 0,
H = 0), the point of class 6 is a minimum point (K <0, H = 0),
Class 7 points are negative hyperbolic points (K <0, H <0), Class 8
Point is called a regular hyperbolic point (K <0, H> 0).

Calculation of Normal Curvature (Step S327) The normal curvatures in the respective x and y axis directions when cut on a plane including a straight line parallel to the z axis and the x axis or the y axis are calculated for each pixel.

The pixel values of the input primary and secondary partial differential images are substituted into the following equations to calculate the normal curvatures κ _x and κ _y in the x and y directions, respectively.

[0054]

[Outside 10] However, Z _x is the first partial differential due to the x component of the distance data Z _y is the first partial differential due to the y component of the distance data Z _xx is the second partial differential due to the x component of the distance data Z _yy is Second-order partial differentiation by the y component of distance data

Calculation of radius of curvature (step S329) For each pixel, the radius of curvature (1 / normal curvature) in each of the x and y axis directions when cutting is performed on a plane including a straight line parallel to the z axis and the x axis or the y axis. Calculate.

Substituting each pixel value of the first-order and second-order partial differential images of the input into the following equation, the radii of curvature ρ _x , ρ
Calculate _y .

[0057]

[Outside 11] However, Z _x is the first partial differential due to the x component of the distance data Z _y is the first partial differential due to the y component of the distance data Z _xx is the second partial differential due to the x component of the distance data Z _yy is Second-order partial differentiation by y component of distance data By the above, each processing in FIG. 3 is executed.

Further, the present invention is not limited to a single device, but can be applied to a system composed of a plurality of devices as long as the functions of the present invention are executed, and further, a program is supplied to the device or the system. It goes without saying that the present invention can be applied even to a system in which processing is performed by doing so.

[0059]

As described above, according to the present invention, by providing the step of converting the type of the range image and normalizing each axis, parameters such as the aspect ratio in each coordinate axis direction are used, Since each pixel value is calculated according to the type of data given to each pixel of the input distance image, the relationship between the coordinate system in which the object is placed and the coordinate system of the image is specified in advance, and each coordinate axis direction It became unnecessary to give parameters such as aspect ratio of each process.

[Brief description of drawings]

FIG. 1 is a block diagram showing an overall configuration of a distance image processing device.

FIG. 2 is a diagram showing a memory configuration of an embodiment.

FIG. 3 is a flowchart of overall processing.

FIG. 4 is a diagram showing an example of a window.

FIG. 5 is a diagram showing an example of an operator for directly obtaining a first-order partial differential and a second-order partial differential from a fitted coefficient of a quadric surface.

FIG. 6 is a diagram showing an example of an operator for directly obtaining a first partial differential and a second partial differential from an original distance image.

FIG. 7 is a diagram illustrating selective local plane fitting.

[Explanation of symbols]

 1 Program Memory 2 Data Memory 3 CPU 4 Display 5 Mouse 6 Keyboard 7 Laser Range Finder

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Inventor Osamu Yoshizaki 3-30-2 Shimomaruko, Ota-ku, Tokyo Canon Inc.

Claims (16)

[Claims] 1. A step of converting a type of an input distance image and normalizing each axis, and calculating a value of the converted distance image to determine a property of an object surface described by the distance image. A distance image processing method comprising: a calculation step of generating data to be represented; and a display step of displaying image information representing the property of the object surface based on the data generated by the calculation step. 2. The calculation step includes a step of detecting a jump edge from a distance image.
The described distance image processing method. 3. The distance image processing method according to claim 1, wherein the calculation step includes a step of calculating a first partial differential from the distance image. 4. The distance image processing method according to claim 1, wherein the calculation step includes a step of calculating a second partial differential from the distance image. 5. The distance image is locally calculated in the calculation step.
The range image processing method according to claim 1, further comprising a step of calculating a coefficient of the equation by approximating to a quadratic plane. 6. The distance image is locally calculated in the calculation step.
The distance image processing method according to claim 1, further comprising the step of approximating a quadric surface to calculate the coefficient of the equation. 7. The calculation step further includes a step of calculating a second partial differential from a range image and a step of calculating a Gaussian curvature by using the calculated first and second partial differentials. The distance image processing method according to claim 3. 8. The calculation step further includes a step of calculating a second partial differential from a range image, and a step of calculating an average curvature using the calculated first and second partial differentials. The distance image processing method according to claim 3. 9. The calculation step further includes a step of calculating a second partial differential from a range image, and a step of calculating a normal curvature by using the calculated first and second partial differentials. The distance image processing method according to claim 3. 10. The calculation step further comprises 2 from the range image.
4. The distance image processing method according to claim 3, further comprising a step of calculating a second partial differential and a step of calculating a radius of curvature by using the calculated first and second partial differentials. 11. The distance image processing method according to claim 7, wherein the calculation step further includes a step of determining a sign of the calculated Gaussian curvature. 12. The distance image processing method according to claim 8, wherein the calculation step further includes a step of determining a sign of the calculated average curvature. 13. The calculation step is a first order from a range image,
Partial differential operation step for calculating the second partial differential, and the calculated 1
Next, a curvature calculation step of calculating the Gaussian curvature and the average curvature by using the second partial differential, a code determination step of determining the sign of the calculated Gaussian curvature and the average curvature, a sign of the determined Gaussian curvature and the average curvature The distance image processing method according to claim 1, further comprising: a surface type determination step of determining a surface type by a combination of symbols. 14. The distance image processing method according to claim 3, wherein the calculation step includes a step of calculating a unit normal vector by using the calculated first partial differential. 15. The distance image processing method according to claim 14, wherein the calculating step includes a step of detecting a roof edge from the calculated unit normal vector. 16. An input means for inputting range image data, a normalizing means for converting the type of the range image input from the input means, and normalizing each axis, and a normalizing means for converting. Calculation means for calculating the value of the range image data to create data representing the property of the object surface described by the range image; and representing the property of the object surface based on the data created by the calculation means. A distance image processing device, comprising: a display unit for displaying image information.