CN1138232C - A Spatial Encoding Method - Google Patents

Abstract

The present invention belongs to the technical field of three dimensional sensing and measurement. The present invention is characterized in that code words corresponding to each coding region are different; the Hamming distances between adjacent coding regions are 1; each object point has at least one chance that the object point is projected by a bright fringe and a dark fringe; the breadth of a minimum region of divided by the projection fringes is at least two times wider than the visual field breadth of a picture element. The present invention has the characteristics of high efficiency and little error.

Description

A Spatial Encoding Method

technical field

The invention belongs to the technical field of three-dimensional sensing and measurement, in particular to a spatial encoding method in computer reconstruction technology of three-dimensional object surface topography.

Background technique

The computer reconstruction technology of the surface profile of three-dimensional objects is one of the hot spots in the research of three-dimensional sensing and metrology at home and abroad. It is widely used in aerospace, machinery manufacturing, on-line inspection and quality control, medical diagnosis, computer-aided design/computer Auxiliary manufacturing (CAD/CAM), robot vision system and other fields. The spatial coding method based on the triangulation method is one of the main research directions of 3D topography reconstruction. However, the existing spatial coding methods have disadvantages such as low coding efficiency. Therefore, the development of an efficient and high-precision spatial coding method is increasingly receiving The attention of experts from various countries.

The working principle of trigonometry is described as follows:

Fig. 1a is an XZ plane view of the spatial coordinate system XYZ, and Fig. 1b is a YZ plane view. The object point P is any point on the surface of the measured object 11. The CCD camera 12 and the projector 13 are placed above the object, and their optical axes form a certain angle. In the figure, the camera and the projector are simplified into two lenses respectively. . Taking the center of the camera lens as the origin (0, 0, 0), the coordinates of the center of the projector lens are (X ₀ , 0, Z ₀ ), and  ₀ is the clamp between the optical axis of the projector and the optical axis of the camera. horn. The horizontal viewing angle and vertical viewing angle of the object point P relative to the camera lens are α and β respectively, and the projection angle relative to the projector lens is . According to the geometric triangle relationship between the center of the projector lens, the center of the camera lens and the object point P, the coordinates of point P are (X, Y, Z), and the following equations can be established:

                           (2)

Y=Z·tgβ (3) According to the above equations, as long as the horizontal viewing angle, vertical viewing angle and projection angle of the object point are known, the three-dimensional position coordinates of the point can be obtained, where the viewing angle α and β are defined by the object point P at The corresponding pixel positions in the camera CCD array are given.

The CCD camera imaging relationship is shown in Figure 2, the horizontal width of the measured reference plane 21 corresponding to the CCD array 22 in the figure is W, the distance from the camera lens 23 to the measured reference plane 21 is L, and the object point P is on the CCD array The pixel position in the horizontal direction is m, and the total number of pixels in the horizontal direction of the CCD array is M, then the horizontal viewing angle α is expressed as: $\mathrm{\α}={\mathrm{tg}}^{-1}(\frac{m}{m}\·\frac{W}{L})---\left(4\right)$ Similarly, the vertical viewing angle β is expressed as: $\mathrm{\β}={\mathrm{tg}}^{-1}(\frac{\mathrm{no}}{N}\·\frac{h}{L})---\left(5\right)$ Wherein, H is the vertical height of the measured reference plane corresponding to the CCD array of the camera, n is the pixel position of the object point P in the vertical direction on the CCD array, and N is the total number of pixels in the vertical direction of the CCD array. The projection angle  is obtained by fringe projection spatial coding method.

The principle of spatial coding triangulation is shown in Figure 3. The LCD projector 33 projects the projection patterns A, B, and C to the measured space 31 in sequence, as shown in Figure 3a; the CCD camera records three grayscale images in sequence, As shown in Figure 3b; images a, b, and c correspond to patterns A, B, and C, respectively. In general, the camera 32 is placed facing the measured space 31 , and the optical axis of the projector 33 forms a certain angle with the optical axis of the camera 32 . The black and white bars in the projected pattern form light and dark bars in the measured space, which result in different gray values in the camera image. After binarizing the image, the bright stripes with high gray values are represented as "1", and the dark stripes with low gray values are represented as "0". In this way, each pixel in the image obtains a binary code with a word length of three bits, one code bit corresponds to one image, and the sequence is: the first bit corresponds to image a, the second bit corresponds to image b, and so on. That is to say, different projected patterns have different weights, with projected pattern A having the highest weight, pattern B next, and so on.

In Figure 3b, the simplest binary code projection pattern is used. The first pattern A is composed of two bright and dark stripes of equal width, and the second pattern B divides the two stripes in the first pattern into two equal parts. Bright and dark stripes, the subsequent projection patterns subdivide each stripe in the previous pattern into two light and dark stripes of equal width. In Figure 3a, three projection patterns are used to divide the measured space into 8 regions d, and each region is represented by a three-bit binary code word. Region 0 gets a code of "000," region 1 gets a code of "001," region 2 gets a code of "010," and so on. Then convert the binary code obtained for each area into the corresponding projection code of the area, this process is called decoding. The decoding process can be completed by establishing a decoding table or a decoding formula. The decoding table of the projection pattern in Fig. 3 is expressed as follows:

Table 1 decoding table binary code 111 110 101 100 011 010 001 000 decimal code 7 6 5 4 3 2 1 0 projection code 3.5 2.5 1.5 0.5 -0.5 -1.5 -2.5 -3.5 Write a search and decoding program according to the above decoding table, and the computer completes the decoding process. The binary code projection pattern can also establish the decoding formula:

N _p =N _d -2 ^n-1 +0.5 (6) Wherein, N _p is the projection code, N _d is the decimal code, and n is the number of binary code projection patterns. With the projection code, the projection angle can be obtained through the following relational expression. Among them, L is the distance from the lens to the measured datum surface, and K is the width of the sub-region divided by the projection fringe on the measured datum surface.

In the above-mentioned triangulation measurement, a simple binary code is used, and its coding efficiency is as high as 100%, but it has obvious disadvantages. Use the form shown in Figure 4 to represent the binary coded projection pattern, each pattern is represented by a row of black and white squares, each square corresponds to a coded area, the white squares represent bright stripes, and the binarization is "1", Black squares represent dark stripes, binarized to "0". There are 4 projection patterns in the figure, which divide the measured space into 16 areas D, numbered 1-16 from right to left. The code of area 6 is "0101", the code of area 7 is "0110", and the code of the boundary between area 6 and area 7 may be "0101", "0110", "0100", "0111", among which the code "0100 " and "0111" correspond to area 5 and area 8 respectively. If the boundary between area 6 and area 7 is coded as "0100" or "0111", a larger coding error will be generated, and when it is coded as "0101" or "0110", the error will be the smallest. Through the above analysis, it can be concluded that the more black-and-white stripe changes occur at the boundary of the region, the more likely the boundary will be encoded, and the greater the encoding error will be. If the number of black-and-white stripe changes at the adjacent coding boundaries is defined as the Hamming distance H, obviously its variation range is 1-N (N is the number of projection patterns), then when the Hamming distance is 1, the edge coding error is the smallest; when the Hamming When the distance is N, the edge error is the largest. For example, the fringe projection pattern shown in the figure has a Hamming distance H of 4 at the edge of area 8 and area 9, which produces the largest coding error, and a Hamming distance H of 1 at the edge of area 1 and area 2, which produces the smallest coding error . The current popular coding method is Gray code, which is a coding method with only one bit difference between adjacent codes, and the coding error is the smallest. However, the coding efficiency of Gray code is low, the efficiency is only 25%, and because there are all-bright and all-dark areas in the coding, it cannot be binarized well, so a better coding method needs to be developed.

Contents of the invention

The purpose of the present invention is to overcome the shortcomings of existing spatial coding, and propose a spatial coding method, which has the characteristics of high efficiency and small error.

A kind of spatial coding method that the present invention proposes is characterized in that, comprises:

1) The codewords corresponding to each coding region are different;

2) The Hamming distance between adjacent coding regions is 1, and the Hamming distance is defined as the number of black and white stripe changes at the region boundary;

3) Each object point has at least one chance of being projected by a bright stripe and a dark stripe;

4) The width of the smallest area divided by the projected fringe is at least twice the width of a pixel field of view.

The specific implementation steps of the above-mentioned spatial coding method can be:

1) Set the number N of projected patterns, so that the width of the smallest area divided by the projected stripes is at least twice the width of the field of view of a pixel, and the light and shade distribution of each projected pattern corresponds to the set coded area M, forming a line with N as rows, M is an N*M matrix of columns, and the element a _ij in the matrix corresponds to the value of the i-th bit of the j-th coding region;

2) Assign an initial value to the first column of the matrix, the initial value can be any combination of 1 and 0, or take the default value;

3) Change the value of one bit in the first column and use it as the next column;

4) Judging whether the column is all 0 or all 1 or the same as a previous column, if so, change the value of another bit, and then judge; if there is no above situation, use it as a newly generated column;

5) Repeat steps 3 and 4 until all projection pattern matrices are generated.

In the present invention, when 7 patterns are projected, the coding efficiency is 98.4%, and when 8 patterns are projected, the coding efficiency is 98.8%, which is far higher than the 25% coding efficiency of Gray code. Experiments have proved that better measurement results can be obtained by using this coding method.

Description of drawings

Figure 1 is a schematic diagram of the principle of trigonometry.

Figure 2 is a schematic diagram of the imaging relationship of the CCD camera.

Fig. 3 is a schematic diagram of the principle of the spatial coding triangulation method.

FIG. 4 is a schematic diagram of a binary code fringe projection pattern.

Fig. 5 is a schematic diagram of the independence of coding in the present invention.

FIG. 6 is a schematic diagram of encoding patterns with Hamming distances of 1 in the present invention.

Fig. 7 is a schematic diagram of the coding self-normalization of the present invention.

Fig. 8 is a schematic diagram of the sampling theorem of the encoding of the present invention.

FIG. 9 is a flow chart of an automatic code pattern generation program according to an embodiment of the present invention.

FIG. 10 is a schematic diagram of a binary coding pattern in this embodiment.

Detailed ways

An embodiment of a spatial coding method proposed by the present invention is described in detail in conjunction with the accompanying drawings as follows:

The spatial coding method of the present invention is described in detail as follows:

1. Mutual independence of coding.

In the encoding pattern, the corresponding codewords of each encoding region are different. This condition is necessary to enable single-pixel-based triangulation without ambiguity when the computer automatically handles the encoding. Figure 5 lists a mutually independent binary code.

2. The Hamming distance between adjacent coding regions is 1.

This condition minimizes the edge coding error caused by the fringe projection space binary coding. FIG. 6 lists a coding in which the Hamming distance H is all 1.

3. Coding self-normalization.

During the measurement, because the gray value of the light intensity obtained on the pixel is affected by the reflectivity of the projected object surface, it may happen that the gray value of the dark stripes on the white object surface is higher than that of the bright stripes on the black object surface. The value is large. In this way, it is impossible to use a globally constant binarization threshold to satisfy all the measured areas. The global threshold is only applicable to the structure with the same reflectance of the object surface and no external illumination or uniform external illumination. Therefore, each object point is required to be projected by at least one bright fringe and one dark fringe, and the light intensity gray value sequence on its corresponding pixel will contain a larger and a smaller gray value. This enables binarization on a single pixel basis to obtain a binary code, where the threshold is the average of the larger and smaller grayscale values at that pixel. Such an encoding is called self-regularizing, and it can be applied to non-constructive situations where the reflectance of the object surface is inconsistent and there is external lighting.

The Gray code in Fig. 7a has the characteristic that the Hamming distance of adjacent codewords is always 1, and at the same time has the characteristic of being convenient for data conversion. However, this code contains region D which cannot self-normalize, these are region 0 and region 5. Region 0 is coded by three all-bright stripes, and region 5 is coded by three all-dark stripes. When performing dynamic threshold binarization, some code bits among them are binarized into "1", and other code bits are binarized into "0", thereby generating encoding errors. The solution to this problem is to add a full-bright and a full-dark projection pattern to ensure that each codeword can self-normalize, as shown in Figure 7b. This is equivalent to adding a 0 and 1 bit to each codeword, so that areas 0 and 5 change from the original codewords "111" and "000" to the current codewords "01000" and "01111", which can realize dynamic Threshold binarization.

4. Encoding must satisfy the sampling theorem.

The sampling theorem can be described here as the sampling frequency of the camera is more than twice that of the area division frequency of the object surface by the projector. That is, the width of the minimum area where the coding needs to satisfy projection fringe division is at least twice the width of a pixel field of view.

As shown in Figure 8, the small square in the figure represents the field of view corresponding to one pixel of the CCD camera on the surface of the measured object. The width of the minimum area divided by the projected stripes on the graph is greater than the width of the field of view of two pixels, which satisfies the sampling theorem.

The efficiency of spatial binary coding refers to the number of effective code words generated by encoding under a certain word length divided by the word length. The more, the higher the measurement resolution.

The spatial encoding method of this embodiment is automatically completed by a program, and the program flow chart is shown in FIG. 9 . Firstly, the number N of patterns to be projected is set, and N=5 in this embodiment. Then calculate the size of the projection matrix that needs to be generated, and clear all matrix elements to zero (C _{N, M} =0). The number of rows N of the matrix is the number of projection patterns, which is a set value of 5. The number of columns M is the number of space divisions of the code, which should be 2 ^N in theory. However, these 2 ^N divisions include all-bright and all-dark codes, which cannot be binarized well; and the condition that the Hamming distance is 1 may not be satisfied. If the number of columns M=2 ^N -2 or M=2 ^N -3 is respectively set according to the parity classification of N, then it can be guaranteed that the generated code meets the conditions set by the present invention. Next enter the first column or take the default. Next, the program transforms one bit in this column, and checks whether the column is all zeros (all dark), all ones (all bright) or repeated with the previous column, and then decides to accept the column or change another bit to continue checking until Get a satisfied column. In this way, the codes are generated column by column, and when all the codes are generated, the code matrix is output. Figure 10 is a group of 5-bit binary code patterns generated by this program. It has 30 code words and divides the measured space into 30 sub-regions. Each code word is a 5-bit binary code. This group of encoding patterns is generated using the default initial columns [10...0] ^T , of course, if different initial columns are used, different encoding patterns will be generated.

Figure 10 is a group of 5-bit binary code patterns generated by this program. It has 30 code words and divides the measured space into 30 sub-regions. Each code word is a 5-bit binary code. This group of encoding patterns is generated using the default initial columns [10...0] ^T , of course, if different initial columns are used, different encoding patterns will be generated.

Claims (1)

1, a kind of spatial coding method, it is characterized in that, comprise: the corresponding code word of each coded area is all different; The Hamming distance between the adjacent coded areas is all 1, and Hamming distance is defined as the black-and-white stripe change that takes place at the area boundary number of times; each object point has at least one chance to be projected by a bright stripe and a dark stripe; the width of the smallest area divided by the projection stripe is at least twice the width of a pixel field of view; The specific implementation steps are: 1) Set the number N of projected patterns, so that the width of the smallest area divided by the projected stripes is at least twice the width of the field of view of a pixel, and the light and dark distribution of each projected pattern corresponds to the set coding area M, forming an N*M matrix, The element a _ij in the matrix corresponds to the value of the i-th bit of the j-th coding region; 2) Assign an initial value to the first column of the matrix, the initial value can be any combination of 1 and 0, or take the default value; 3) Change the value of one bit in the first column and use it as the next column; 4) Judging whether the column is all 0 or all 1 or the same as a previous column, if so, change the value of another bit, and then judge; if there is no above situation, use it as a newly generated column; 5) Repeat steps 3 and 4 until all projection pattern matrices are generated.

Images