JP2011182397A - Method and apparatus for calculating shift length - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To calculate shift length between two cameras for stereoscopic image photographing. <P>SOLUTION: A shift length calculation apparatus includes: a determiner operable to determine a feature-point position within a first image and a corresponding feature-point position within a second image; a definer operable to define, within the first image and the second image, the optical axis of the cameras capturing the respective first and second images; a calculator operable to calculate the shift length between the feature-point position within the first image and the corresponding feature-point position within the second image using a predetermined model; and a tester operable to test the validity of the calculated shift length using a random sample consensus technique; wherein the shift length is calculated in dependence upon the location of the feature-point position of the first image and the corresponding feature-point position of the second image relative to the defined optical axis of the respective first and second images, and the tested shift length is valid when a predetermined condition is achieved. <P>COPYRIGHT: (C)2011,JPO&INPIT

Description

  The present invention relates to a deviation amount calculation method and a deviation amount calculation apparatus.

  When a 3D image is captured to view a 3D image, it is common to capture the image using two cameras. In order to ensure that the video is captured correctly, the two cameras need to have the same zoom level and minimal vertical parallax. In addition, the amount of roll deviation between the two cameras needs to be minimal.

  Usually, the deviation is corrected by the camera operator if possible. Since the deviation between the two cameras is typically not a single, but a combination of two or more deviations, it is difficult for the camera operator to determine and correct these deviations. Furthermore, it is important to correct such errors quickly and accurately, especially in the case of live video footage.

European Patent Application No. 2112630 British Patent Application No. 2372659

LACEY et al., "An evaluation of the performance of RANSAC algorithms for stereo camera calibration" BMVC 200: Proceedings of the 11th British Machine Vision Conference; 11-14 September 200, University of Bristol, UK; Conference Paper, Vol 2, Pages 646 -655

  Embodiments of the present invention aim to address the above problems.

  According to the first embodiment of the present invention, there is provided a method for calculating a shift amount between a first image and a second image that can be viewed in three dimensions, and a feature point in the first image. And the position of the corresponding feature point in the second image, and in the first image and the second image, the first image and the second image are respectively The optical axis of the camera to be photographed is determined, and using a predetermined model, the difference between the position of the feature point in the first image and the position of the corresponding feature point in the second image Calculating the amount and testing the validity of the calculated displacement amount using a random sample consensus technique, wherein the displacement amount is determined by the determined light of each of the first image and the second image. The position of the feature point of the first image with respect to the axis and the top of the second image. Is calculated according to the position of the corresponding feature points, the tested shift amount, the random sample consensus techniques are appropriate when the predetermined condition is achieved, the shift amount calculating method is provided.

  The deviation amount may be appropriate when the probability that the deviation amount is accurate exceeds a threshold value.

  The predetermined condition may be that the random sample consensus technique is repeated a predetermined number of times.

  The number of repetitions may be calculated based on the following formula.

式中、target_incorrect_est_probは、上記モデルが不正確である確率であり、incorrect_est_probは、上記対応する特徴点が不正確である確率である。

Where target_incorrect_est_prob is the probability that the model is incorrect and incorrect_est_prob is the probability that the corresponding feature point is incorrect.

  The model may be defined by the following equation:

式中、ｙは、上記第２の画像内の上記特徴点の垂直位置、ｘＬおよびｙＬはそれぞれ、上記第１の画像内の上記特徴点の水平位置および垂直位置であり、θは回転ずれ量であり、Ｓはスケールずれ量であり、かつ、Ｔは、上記第１の画像と上記第２の画像との間の垂直ずれ量である。

Where y is the vertical position of the feature point in the second image, xL and yL are the horizontal position and vertical position of the feature point in the first image, respectively, and θ is the amount of rotational deviation. S is the amount of scale deviation, and T is the amount of vertical deviation between the first image and the second image.

  The deviation amount calculation method may further include a step of acquiring feature points from a reduced version of the original first image and the original second image using a block matching technique.

  The deviation amount calculation method further includes calculating the feature points acquired from the reduced version of the original first image and the original second image, using the original first image and the original second image. It may be used as a starting point for a block matching technique in an image, and may include obtaining a first feature point and a second feature point from the original first image and the original second image.

  The deviation amount calculation method further includes the step of specifying the position of at least one further feature point in the first image and specifying the position of at least one corresponding further feature point in the second image. The position of two feature points in the first image and the position of the two corresponding feature points in the second image may be selected, and the position between the first image and the second image may be selected. A vertical shift amount between the first image and the second image may be calculated based on a given rotation shift amount.

  The position of the feature point in the first image and the position of the corresponding feature point in the second image may be located above the determined optical axis, and the first image The position of the further feature point in the second image and the position of the corresponding feature point in the second image may be located below the determined optical axis.

  Selecting a position of a feature point in the first image, selecting a position of a corresponding feature point in the second image, and providing a given point between the first image and the second image Based on the vertical shift amount, the scale shift amount between the first image and the second image may be calculated.

  The position of the feature point in the first image and the position of the corresponding feature point in the second image may be located above the determined optical axis, or The position of the feature point in one image and the position of the corresponding feature point in the second image may be located below the determined optical axis.

  The deviation amount calculation method further includes the step of specifying the position of at least one further feature point in the first image and specifying the position of at least one corresponding further feature point in the second image. Alternatively, the positions of two feature points are selected in the first image, the positions of two corresponding feature points are selected in the second image, and the first image and the second image are selected. The amount of rotational deviation between the first image and the second image may be calculated based on a given amount of scale deviation between the first image and the second image.

  The position of the feature point in the first image and the position of the corresponding feature point in the second image may be located on the left side of the determined optical axis, and the first The position of the further feature point in the second image and the position of the corresponding feature point in the second image may be located on the right side of the determined optical axis.

  The position of the feature point and the position of the further feature point may be randomly generated.

  The position of the feature point may be a pixel position in the first image and the second image.

  According to the second embodiment of the present invention, there is provided a program for causing a computer to execute each step of the deviation amount calculation method.

  According to the third embodiment of the present invention, a recording medium on which a program (corresponding to claim 16) is recorded is provided.

  According to the fourth embodiment of the present invention, there is provided an apparatus for calculating a shift amount between a first image and a second image that can be viewed stereoscopically, and a feature point in the first image. And a specifying unit for specifying the position of the corresponding feature point in the second image, and the first image and the second image in the first image and the second image. And a position of the feature point in the first image and a position of the corresponding feature point in the second image using a model. And a tester that tests the validity of the calculated amount of deviation using a random sample consensus technique, the amount of deviation being the first image and The first image with respect to the determined optical axis of each of the second images; Calculated according to the position of the feature point and the position of the corresponding feature point of the second image, and the tested deviation is valid when the random sample consensus technique achieves a predetermined condition. A deviation amount calculation device is provided.

  The deviation amount may be appropriate when the probability that the deviation amount is accurate exceeds a threshold value.

  The predetermined condition may be that the random sample consensus technique is repeated a predetermined number of times.

  The number of repetitions may be calculated based on the following formula.

式中、target_incorrect_est_probは、上記モデルが不正確である確率であり、incorrect_est_probは、上記対応する特徴点が不正確である確率である。

Where target_incorrect_est_prob is the probability that the model is incorrect and incorrect_est_prob is the probability that the corresponding feature point is incorrect.

  The model may be defined by the following equation:

式中、ｙは、上記第２の画像内の上記特徴点の垂直位置、ｘＬおよびｙＬはそれぞれ、上記第１の画像内の上記特徴点の水平位置および垂直位置であり、θは回転ずれ量であり、Ｓはスケールずれ量であり、かつ、Ｔは、上記第１の画像と上記第２の画像との間の垂直ずれ量である。

Where y is the vertical position of the feature point in the second image, xL and yL are the horizontal position and vertical position of the feature point in the first image, respectively, and θ is the amount of rotational deviation. S is the amount of scale deviation, and T is the amount of vertical deviation between the first image and the second image.

  The deviation amount calculation device may further include an acquisition unit that acquires feature points from a reduced version of the original first image and the original second image using a block matching technique.

  The acquirer further determines the feature points acquired from the reduced version of the original first image and the original second image in the original first image and the original second image. It may be operable to obtain a first feature point and a second feature point from the original first image and the original second image, used as a starting point for a block matching technique.

  The identifier is further operable to locate a location of at least one additional feature point in the first image and to locate a location of at least one corresponding further feature point in the second image. The position of two feature points in the first image and the position of two corresponding feature points in the second image may be selected, and the first image and the second image may be selected. A vertical shift amount between the first image and the second image may be calculated based on a given roll shift amount.

  The position of the feature point in the first image and the position of the corresponding feature point in the second image may be located above the determined optical axis, and the first image The position of the further feature point in the second image and the position of the corresponding feature point in the second image may be located below the determined optical axis.

  Selecting a position of a feature point in the first image, selecting a position of a corresponding feature point in the second image, and providing a given point between the first image and the second image Based on the vertical shift amount, the scale shift amount between the first image and the second image may be calculated.

  The position of the feature point in the first image and the position of the corresponding feature point in the second image may be located above the determined optical axis, or The position of the feature point in one image and the position of the corresponding feature point in the second image may be located below the determined optical axis.

  The identifier is further operable to locate a location of at least one additional feature point in the first image and to locate a location of at least one corresponding further feature point in the second image. The positions of two feature points in the first image may be selected, the positions of the two corresponding feature points in the second image may be selected, and the first image and the second image may be selected. An amount of rotational deviation between the first image and the second image may be calculated based on a given scale deviation amount between the first image and the second image.

  The position of the feature point in the first image and the position of the corresponding feature point in the second image may be located on the left side of the determined optical axis, and the first The position of the further feature point in the second image and the position of the corresponding feature point in the second image may be located on the right side of the determined optical axis.

  The position of the feature point and the position of the further feature point may be randomly generated.

  The position of the feature point may be a pixel position in the first image and the second image.

  The above and other objects, features and advantages of the present invention will become apparent from the following detailed description of exemplary embodiments to be read with reference to the accompanying drawings.

It is a figure which shows the camera system connected to the deviation | shift amount calculator by one Embodiment of this invention. It is a figure which shows the deviation | shift amount calculator of FIG. 2 is a flowchart for explaining processing executed by an edge detector and a corresponding point calculator in the deviation amount calculator of FIG. 1. It is a figure which shows the illustration of the flowchart of FIG. It is a flowchart explaining calculation of deviation | shift amount. It is a flowchart explaining the principle which calculates vertical deviation | shift amount. It is a figure which shows the method of converting a pixel position into the pixel position regarding an optical axis. It is a flowchart explaining the principle which calculates the amount of scale shifts. It is a flowchart explaining the principle which calculates rotation deviation | shift amount. It is a figure explaining calculation of a perpendicular deviation amount algorithm. It is a figure explaining calculation of a rotation gap amount algorithm. It is a figure explaining calculation of a rotation gap amount algorithm. It is a flowchart explaining the technique which fixes a corresponding point correctly. It is a flowchart explaining the technique which fixes a corresponding point correctly.

[Overview of method]
In the embodiment, the following method is generally performed to calculate the shift amount for a stereoscopic image.
1) Select a main feature point in one of the two images. In the embodiment, the main feature points in the left image are selected.
2) Using the main feature point as a reference for the block matching process, the corresponding main feature point in the right image is calculated.
3) A series of geometric operations is executed to obtain three distortion amounts (deviation amounts). Specifically, a shift amount indicating vertical parallax is calculated, a shift amount indicating scale (enlargement / reduction) parallax is calculated, and finally, a shift amount indicating roll (rotation) parallax is calculated. In the embodiment, the deviation amount calculated in the preceding step is used in the deviation amount calculation in the later-described step. Although the three shift amounts are described as being calculated in a specific order, the present invention is not limited to this as described later. The amount of deviation can be calculated in any order. The amount of deviation can then be used to adjust the physical position of the camera and / or camera parameters, or the captured image can be adjusted electronically based on the amount of deviation.

  FIG. 1 shows one implementation of the embodiments of the present invention. The two cameras 110 and 120 are set to capture a stereoscopic image. A camera system 100 is configured by these stereoscopic image cameras. The output from each camera is supplied to the deviation amount calculator 200 according to the embodiment of the present invention. The deviation amount calculator 200 calculates the deviation amount between the two cameras of the camera system 100. In addition, although the camera set to image | photograph a stereo image performs a horizontal displacement, the algorithm for the image which performs a horizontal displacement is not essential. Therefore, the shift amount calculator 200 calculates the shift amount indicating the vertical parallax and the shift amount indicating the rotational parallax, and the shift amount indicating the scale parallax is generated. By using these shift amounts by the camera operator, the shift of the camera can be physically corrected, or the shift can be corrected by controlling the servo motor using the shift amount. In practice, by using the shift amount, it is possible to electronically correct the image generated by the camera system 100 without physically correcting the camera orientation.

  FIG. 2 shows the shift amount calculator 200 in more detail. First, using conventional technology, the images from the two cameras are reduced to ¼ HD (ie, from 1280 × 720p to 480 × 270 resolution or 360 × 180) and supplied to the edge detector 210. Reducing the image resolution means that edge detection is performed more quickly. The edge detector 210 is used to calculate the horizontal edge in the left image. The detected edge is supplied to the corresponding point calculator 220, and the corresponding point calculator 220 calculates a point in the right image corresponding to a point in the left image. In other words, the corresponding point calculator 220 calculates where certain pixels of the right image are located in the left image. The deviation amount is calculated by the deviation amount calculator 230 and output.

  FIG. 3 is a flowchart for explaining processing executed by the edge detector 210 and the corresponding point calculator 220. The flowchart will be described with reference to the illustration of FIG.

  In FIG. 4, the left image 120A (taken by the left camera 120) includes an image of the automobile 125A. This is first reduced to 1/4 HD resolution using conventional techniques. Decreasing the resolution means that edge detection is performed more quickly. In step 2101 of FIG. 3, a horizontal edge in the left image is detected. In an embodiment, this is achieved by an edge detection algorithm such as, for example, a Sobel edge detection algorithm. The reason why the horizontal edge is detected is that one of the calculated shift amounts is the vertical displacement between the two images. In this way, by calculating only the horizontal edges, the number of candidate feature points is reduced without substantially affecting the accuracy of the results.

  After calculating the horizontal edge in the left image, an image such as 120B (see FIG. 4) is generated. As can be seen in FIG. 4, an error edge 125B has been generated. The error edge 125B does not have a corresponding point in the right image. Therefore, it is desirable to reduce the number of detected horizontal edges. The number of horizontal edges is reduced in step S2102 of FIG. To achieve this, the image in which the edge is detected is divided into tiles. In an embodiment, each tile is 16 pixels wide by 16 pixels high. In FIG. 4, a reference numeral 125C is assigned to one tile. However, any size tile can be selected. Similarly, tiles of any shape can be selected, for example rectangular tiles. Ignore any edges that don't catch on the tile. In other words, of the detected edges, those having a length of less than 16 pixels are ignored. By making this reduction, false error edges are ignored. This improves the reliability of the results and reduces the cost of the operation of the method.

  After reducing the number of detected edges, the image is divided into quadrants. The center of the quadrant is the optical axis of the image. In the embodiment, the center of the quadrant is placed on the optical axis because the optical axis is an invariant line. That is, the optical axis is not affected by scale distortion or roll distortion. For convenience of explanation, it is assumed that the optical axis of the image is the center of the image. However, those skilled in the art will appreciate that this is only a valid assumption and does not always apply. This is indicated by 120D in FIG. A section of the quadrant image is indicated with a reference sign (125D).

  After dividing the image into quadrants, a plurality of sample edge pixels are selected for each quadrant. In the embodiment, 20 pixels are selected for each quadrant, but the present invention is not limited to this, and an arbitrary number of pixels can be selected. This selection may be based on a tradeoff between accuracy and speed of computation, as will be appreciated. Furthermore, in the embodiment, the pixels are randomly selected, but the present invention is not limited to this.

  A typical image with a plurality of selected pixels selected is shown at 120E in FIG. One pixel position of such a pixel is indicated with a reference sign (125E). Although the pixel position is determined as a suitable feature point, the present invention is not limited to this. As can be appreciated, other feature points such as sub-pixel positions in the ¼ resolution image can also be calculated. If any one of the sub-pixels is present at a “normal” pixel location (ie, the pixel location of the full resolution HD signal), the value of the sub-pixel may be selected randomly or by some other method Good. In addition, the user may be informed of the different sub-pixel values that may exist at the “normal” pixel location.

  So far, the method has identified feature locations in the left image. These feature positions are pixel positions in the left image. Next, it is necessary to calculate where the corresponding pixel position in the right image exists.

  A search is performed for each pixel position determined in the right image. In other words, since a plurality of pixel positions are determined in the left image, it is necessary to perform a search around the same pixel position in the right image in order to calculate the corresponding pixel position. This is achieved using block matching techniques.

  In step 2104, a conventional block matching technique is performed for each pixel position of the right image to calculate a corresponding pixel position. This is illustrated at 110B in FIG. As seen in the image 110B, the pixel position 125E derived from the left image forms the center of the search area in the right image 110B. The size of the search area must account for the amount of misalignment due to the intentional horizontal displacement and errors required to achieve stereoscopic viewing. Thus, if the image is a typical full resolution image, the search area is 250 pixels wide by 100 pixels high. However, the present invention is not limited to this, and search areas of other sizes and shapes can be employed. Specifically, for a 1/4 resolution, the search area is 63 pixels wide by 45 pixels high.

  The result of the block matching technique is a probability map, which provides the probability of each pixel location in the search area corresponding to the pixel location 125E established in the left image. The pixel position in the right image having the highest probability is selected as the pixel position in the right image corresponding to the pixel position in the left image 125E. As shown in FIG. 4, the pixel position of the right image is determined as a pixel position 119B. This is repeated for all pixel positions determined in the left image, as shown in step S2105.

  In order to reliably reduce the number of error results, the results from step S2105 are subjected to filtering. As a first filter, if a clearly corresponding pixel location in the right image has a probability of 1, for example, all results below a certain threshold of 0.98 (or probability of 98%) are ignored. This reduces the number of error results. Since this is an exemplary threshold, other suitable thresholds can be envisaged and the invention is not limited to this.

  Furthermore, if the pixel position in the left image is an edge pixel position, the corresponding point in the right image should also be an edge pixel position. Therefore, the right image is also subjected to an edge detection algorithm such as a Sobel edge detection algorithm in order to detect a horizontal edge. When the corresponding pixel position in the right image is located on one of the three horizontal edges, the probability that the pixel position in the right image corresponds to the pixel position calculated in the left image is high. Become. Note that it is possible to reduce the possibility of an error result using one or both of the above techniques. In practice, a combination of both techniques is used.

  Referring to FIG. 2, the output from the corresponding point calculator 220 is a list of pixel positions in the left image and a list of corresponding points in the right image.

  In order to improve the accuracy of the corresponding point calculator 220, the block matching technique is repeated using a full resolution (1920 × 1080) image in which corresponding points are identified. Specifically, the block matching technique is repeated using a 16 pixel × 16 pixel search window in the left image and a 32 pixel × 32 pixel search window in the right image. The center of each search window is positioned at the point calculated by the corresponding point calculator 220. The result of full resolution block matching is supplied to the deviation calculator 230. As described above, a conventional technique for calculating a position in the first image and a corresponding point in the second image may be similarly used. However, it should be noted that the above method is faster and less expensive to calculate than conventional techniques such as SIFT (Scale-Invariant Feature Transform).

[Calculation of deviation]
After deriving the corresponding feature point and converting it to a position related to the optical axis of the image, a method of deriving the following shift amount may be used.

  Referring to FIG. 10, assuming that the vertical offset is constant, the vertical offset will be invariant to scale and roll rotation, and the following equation holds:

式中、ｙ２_ｒは点ｐ２_ｒ（光軸に関して）の垂直位置であり、ｘ２_ｌおよびｙ２_ｌはそれぞれ_、点ｐ２_ｌの水平位置および垂直位置であり、θはロール角（回転ずれ量）であり、Ｓはスケールずれ量であり、そして、Ｔは、２枚の画像間の垂直ずれ量である。

Where y2 _r is the vertical position of point p2 _r (with respect to the optical axis), x2 _l and y2 _l are the horizontal position and vertical position of point p2 _l , respectively _, and θ is the roll angle (rotational deviation) Yes, S is the amount of scale deviation, and T is the amount of vertical deviation between the two images.

Furthermore, it is possible to measure the vertical position difference d between the points p2 _l and p2 _r using block matching.

したがって、［１］および［２］を用いると、以下の式が明らかになる。

Therefore, when [1] and [2] are used, the following equation becomes clear.

If there are three unknown parameters, T, S, and θ (or T, a, and b), these three points, p1 _l , p2, with coordinates (x, y) expressed with respect to the optical axis in the left image It is possible to find corresponding points in _l and p3 _l and the right image, and the following equation is shown:

    From [3], [4] and [5] it is clear that T, θ and S are established.

  If four or more feature points are measured, in an embodiment it is possible to list the points in descending order of the image (ie from the first image to the last image). These three corresponding points are selected. The three selected points are i-th, i-th + n / 3 and i-th + 2n / 3 feature points, where i is the number of iterations of feature point selection (0-n / 3-1) , N is the number of feature points measured. The values of a, b and T are calculated each time it is repeated, and after all iterations have been made, the values are ordered. The median of a, b and T is chosen as the best estimate and these values are used to calculate T, S and θ.

  With reference to FIGS. 13A and 13B, a method for more accurately verifying θ, S and T described above is disclosed. If there is an error in verifying the accuracy of the corresponding point, the accuracy of θ, the scale and T will be incorrect. Therefore, it is desirable to reduce inaccuracies and thus inaccuracies in the calculated deviations in determining corresponding points. In order to increase the accuracy of the calculated deviation amount, three corresponding points required for calculating θ, S, and T are verified using a RANSAC (RANdom Sample Consensus) method. 13A and 13B show a flowchart illustrating such a method.

  The method starts in step S1305. In step 1310, the number of RANSAC technique iterations is calculated. The number of iterations required depends on the accuracy of the required results and the accuracy of the corresponding points. In general, the probability that an arbitrary corresponding point is accurate is about 80% for a high-performance corresponding algorithm such as SIFT, SURF or block matching (or the probability that the corresponding point is inaccurate is 20%).

  In order to calculate the required number of iterations n, the probability that the corresponding point after the RANSAC technique is correct is calculated. In an embodiment, the probability that the values of θ, S, and T are accurate is 99.9999%. Therefore, the following equation holds.

式中、target_incorrect_est_probは、θ、ＳおよびＴの値が正確である確率であり、incorrect_est_probは、対応点が不正確である確率である。

In the equation, target_incorrect_est_prob is the probability that the values of θ, S, and T are correct, and incorrect_est_prob is the probability that the corresponding point is incorrect.

  After calculating the value n, three corresponding points in the left image are randomly selected. Further, the corresponding point of the right image is verified (S1315). Using these selected points, θ, scale, and T are calculated in the above equation (S1320). The randomly selected points are added to the consensus set in step S1325.

  Then, all other corresponding points are individually inserted into the model to calculate the position of the point in the right image and the distance between the predicted position and the measured position calculated using the values of S and T. These proven values are compared with the values calculated by the randomly selected corresponding points (step S1335). If the difference between the values is below the threshold, a corresponding point is added to the consensus set (S1340). If the difference is above the threshold, no points are added to the consensus set (S1345).

  After testing all corresponding points, the number of points present in the consensus set is counted. If the number of points is above the threshold, i.e. below the accuracy of the point correspondence algorithm, the median of values method is used for the entire consensus set to generate a better model S1355A. The model is tested again using all corresponding points (S1360). On the other hand, when the number of points in the consensus set falls below the threshold, another three consensus points are selected at random and the process is repeated (S1355).

  As described above, the model is tested against the previous model using all corresponding points in the consensus set. If the difference between the model under test and the preceding model falls below the error threshold, it is determined that the model under test is a better model than the preceding model (S1365). If the model under test is not better than the preceding model, the model under test is ignored (S1370).

  If the model under test is better than the previous model, store the consensus set, model, and error value for use in the next iteration. The error value is compared with a threshold error, and if the error falls below the threshold, the RANSAC process is stopped. Alternatively, if the error is above the threshold but the number of RANSAC iterations is below n, another three corresponding points are randomly selected. However, if the error exceeds the threshold and the number of iterations exceeds n, the RANSAC process ends. Note that the overall threshold abort technique (step S1380) may or may not be used. In embodiments, this step may not be included.

  Upon completion of the RANSAC process, the output values of θ, S, and T are verified.

  FIG. 5 is a flowchart for explaining another method for calculating the shift amount after the corresponding points are calculated.

  As can be seen from the structure of the algorithm, the deviation amount of this embodiment is calculated iteratively. During each iteration of the algorithm, the amount of deviation begins to settle to a constant value. The algorithm is executed in real time. This means that in one frame of video, the algorithm may not reach the required steady state. In this case, the algorithm is executed for a plurality of different frames. This is because the amount of shift is unlikely to change over the few frames required until a steady state is reached. When it is necessary to execute the shift amount algorithm for another frame of the video, it is necessary to execute the corresponding algorithm described in FIG. 3 for a new frame of the video. On the other hand, when the steady state is reached during one frame of the video, the corresponding algorithm in FIG. 3 only needs to be executed once.

  After reaching steady state, the algorithm may be executed periodically, for example, once every 10 seconds, or after a predetermined number of frames to ensure that the camera is not misaligned. Alternatively, the algorithm may be executed after the camera focal length has changed or in response to any other action.

  In step 501, the roll (rotation) deviation amount is set to 0 degree before the first iteration of deviation amount calculation. This value of the rotational deviation is updated during the first iteration of the deviation calculation algorithm. The reason why the rotational deviation amount is set to 0 degrees instead of other arbitrary values of the assumed deviation amount is that the rotational deviation amount is close to zero. This is because, during the initial setting by the camera operator, the roll difference is likely to be small due to the effect of rotational mismatch on the image. Therefore, assuming that the rotational deviation amount is initially 0 degree, the accuracy of the other deviation amounts initially takes a high value, so that the entire algorithm reaches a suitable accuracy level more quickly.

  In step 502, the amount of vertical deviation (movement) is calculated using the roll value. This will be described later with reference to FIG.

  In step 503, the amount of scale deviation is calculated using the calculated amount of vertical deviation. This will be described later with reference to FIG.

  In step 504, the roll deviation amount is calculated using the calculated scale deviation amount. This will be described later with reference to FIG.

  When the shift amount is calculated repeatedly, in step S505, the number of repetitions of the shift amount calculation for one frame of the video is calculated. If the number of iterations is below the threshold (eg 5), the algorithm is re-executed using the value calculated in the previous iteration as the initial value.

  If the number of iterations exceeds the threshold, the algorithm is checked to determine whether a steady state has been reached (step S506). It may be determined that a steady state has been reached when the amount of deviation between iterations has changed only by a threshold such as 0.05%. If the deviation amount is in a steady state, the algorithm waits until the deviation amount is output and needed again, for example, until the camera settings are changed as described above.

[Vertical Deviation Calculation (Step S502 in FIG. 5)]
FIG. 6 is a flowchart for explaining the principle for calculating the vertical deviation amount.

  If the optical axis is invariant with respect to scale, it is advantageous to calculate a vertical deviation (movement) value with respect to the optical axis of the image taken by the camera. In order to do this, it is necessary to convert the pixel position calculated by the corresponding point calculator 220 into a pixel position related to the optical axis. FIG. 7 shows a method for converting a pixel position into a pixel position with respect to the optical axis. In the figure, the dimensions relate to a full HD signal, but in the embodiment, the resolution may be lower than this. In the conventional image labeling method, the upper left pixel position is (0, 0) and the lower right pixel position is (1920, 1080) for a high-resolution image. Therefore, in such a conventional system, the center of the image (assumed as the optical axis position as described above) has a pixel position of (960, 540) (see above). However, in the embodiment of the present invention, the center of the image has (0,0) pixel positions. In order to convert the conventional pixel position of (400, 400) into that related to the optical axis, it is necessary to calculate the distance between the pixel position and the center of the image. From FIG. 7, it is clear that the conventional pixel position (400, 400) is at 560 pixels to the left and 200 pixels above from the optical axis. Therefore, the conventional pixel position (400, 400) is at the pixel position (−560, 200) with respect to the optical axis.

  In order to calculate the amount of vertical deviation, the positions of two feature points from the left image are selected. Specifically, as the position of the feature point, one that is located below the optical axis in the left image and one that is located above the optical axis are selected (S602). In the embodiment, these feature points are randomly selected, but the present invention is not limited to this. Further, the position of the corresponding feature point is selected from the right image (S603).

  After selecting the points, these are applied to the following equation 6 to calculate a movement value (S604).

式中、Ｔは移動値であり、ｙｌ_ｒは第２の画像における特徴位置のｙ座標であり、ｙ２_ｌは第１の画像におけるさらなる特徴位置のｙ座標であり、ｘ１_ｒは、第１の画像における特徴位置に対応する第２の画像における特徴位置のｘ座標、ｙ１_ｒは、第２の画像における対応する特徴位置のｙ座標であり、ｘ２_ｒは、第２の画像における対応するさらなる特徴位置のｘ座標であり、かつｙ２_ｒは、第２の画像における対応するさらなる特徴位置のｙ座標である。

Where T is the displacement value, yl _r is the y coordinate of the feature position in the second image, y2 _l is the y coordinate of the further feature position in the first image, and x1 _r is the first coordinate The x coordinate of the feature position in the second image corresponding to the feature position in the image, y1 _r is the y coordinate of the corresponding feature position in the second image, and x2 _r is the corresponding further feature in the second image. The x coordinate of the position, and y2 _r is the y coordinate of the corresponding further feature position in the second image.

  The derivation of this equation is described at the end of the specification.

Note that the value of θ in the values of R ₁ and R ₂ is determined by the quadrant in which the feature points p1 and p2 are located. Specifically, when the feature point (or feature position) is in the lower right quadrant or the upper left quadrant, the roll value is −θ. On the other hand, when the feature point is in the lower left quadrant or the upper right quadrant, the roll value is + θ. This is because the roll is measured with respect to the optical axis.

  After calculating the movement of these points, the calculated number of vertical deviations is incremented by 1 (step S605). This number is compared with a threshold value (step S606). If the calculated number of deviations is below the threshold, another two points are selected and the vertical deviation algorithm is re-executed. In an embodiment, the threshold is 20, but any other value is also expected.

  If the calculated number of deviation values exceeds the threshold value, the calculated values are arranged in ascending order (step S607). The median of the ordered list is selected (step S608), and this is considered to be the calculated deviation value for step S502 of FIG. The median deviation value is output as the vertical deviation amount and supplied to the scale deviation amount algorithm (step S503 in FIG. 5). The median value may be selected directly from the derived value. In other words, it is not necessary to arrange the shift amounts in order before selecting the median value. This also applies to other shift amount calculations.

[Calculation of Scale Deviation (Step S503 in FIG. 5)]
FIG. 8 is a flowchart for explaining the principle for calculating the amount of scale deviation.

  In step 801, the pixel position calculated by the corresponding point calculator 220 is converted into a pixel position related to the optical axis as described with reference to FIG.

  In order to calculate the amount of scale deviation, a feature position from the left image is selected (S802). In the embodiment, the feature points are randomly selected, but the present invention is not limited to this. Also, a corresponding feature position is selected from the right image (S803).

  After selecting a point, this is applied to the following equation 7 to calculate a scale value (S804).

式中、移動ずれ量Tの正負は、点の位置によって決まり、ｙ_ｌは、第１の画像における特徴位置のｙ座標であり、ｙ_ｒは、第２の画像における特徴位置のｙ座標であり、ｘ_ｒは、第２の画像における特徴位置のｘ座標である。Ｐが光軸の上方に位置する場合、値は＋Ｔとなり、他方、点が光軸の下方に位置する場合、値は−Ｔとなる。また、θの正負は、後述するように点ｐが位置する象限によって決まる。

Wherein the positive and negative movement shift amount T is determined by the position of the point, y _l is the y-coordinate of feature position in the first image, y _r is an y-coordinate of feature position in the second image , _Xr are the x coordinates of the feature positions in the second image. If P is located above the optical axis, the value is + T, while if the point is located below the optical axis, the value is -T. Further, the sign of θ is determined by the quadrant where the point p is located, as will be described later.

  The derivation of this equation is also described at the end of the specification.

  After calculating the scale, the calculated number of scale deviations is incremented by 1 (step S805). This number is compared with a threshold value (step S806). If the number of calculated deviation values falls below the threshold, another point is selected and the scale deviation amount algorithm is re-executed. In an embodiment, the threshold is 20, but any other value is also expected.

  When the calculated number of deviation values exceeds the threshold value, the calculated values are arranged in ascending order (step S807). The median of the ordered list is selected (step S808), and this is considered to be the calculated deviation value for step S503 of FIG. This median deviation value is output as a scale deviation amount and supplied to the rotation deviation amount algorithm (step S504 in FIG. 5).

[Rotation deviation calculation]
FIG. 9 is a diagram illustrating the principle for calculating the rotational deviation amount.

  In step 901, as described with reference to FIG. 7, the pixel position calculated by the corresponding point calculator 220 is converted into a pixel position related to the optical axis.

  In order to calculate the amount of rotational deviation, two feature positions from the left image are selected. Specifically, as the characteristic position, one that is located on the left side of the optical axis in the left image and one that is located on the right side of the optical axis are selected (S902). In the embodiment, these feature points are randomly selected, but the present invention is not limited to this. Also, a corresponding feature position is selected from the right image (S903).

  After selecting the points, these are applied to the following equation 8 to calculate the movement value (S904).

式中、Ｓは第１の画像と第２の画像との間のスケールずれ量であり、ｙ２_ｌは、第１の画像におけるさらなる特徴位置のｙ座標であり、ｙ１_ｌは、第１の画像における特徴位置のｙ座標であり、ｙ１_ｒは第２の画像における対応する特徴位置のｙ座標、ｘ２_ｒは第２の画像における対応するさらなる特徴位置のｘ座標、かつｘ１_ｒは、第２の画像における対応する特徴位置のｘ座標である。

Where S is the amount of scale shift between the first image and the second image, y2 _l is the y coordinate of the further feature position in the first image, and y1 _l is the first image Is the y coordinate of the feature position in, y1 _r is the y coordinate of the corresponding feature position in the second image, x2 _r is the x coordinate of the corresponding further feature position in the second image, and x1 _r is the second coordinate It is the x coordinate of the corresponding feature position in the image.

  The derivation of this equation is also described at the end of the specification.

  After calculating these points, the calculated number of roll deviation values is incremented by 1 (step S905). This number is compared with a threshold value (step S906). If the calculated number of deviation values is below the threshold, another two points are selected and the roll deviation amount algorithm is re-executed. In an embodiment, the threshold is 20, but any other value is also expected.

  When the calculated number of deviation values exceeds the threshold value, the calculated values are arranged in ascending order (step S907). The median of the ordered list is selected (step S908), and this is considered to be the calculated deviation value for step S504 of FIG. This median deviation value is output as a roll deviation amount.

  When the deviation amount calculation algorithm is re-executed in step S505 or S506, the roll value calculated in step S908 is used in the next iteration. However, when the deviation amount calculation algorithm is not re-executed, the roll deviation amount calculated in step S908, the vertical deviation amount from step S608, and the scale deviation amount from step S808 are output as the result of the deviation amount calculation algorithm. .

[Other Embodiments]
Thus, the steady state has been mentioned. However, this is not essential for the present invention. A single iteration of the algorithm indicates the mismatch level at which the correction is made. Actually, the mismatch amount is specified by any number of iterations.

  Embodiments of the present invention may be provided as computer-readable instructions (computer programs) that, when loaded into a computer, cause the computer to perform the steps of the method described above. The computer readable instructions can be written in any computer readable language, or indeed any language that can be understood by a suitable microprocessor. The computer program may be stored in a recording medium such as a magnetic disk, an optical disk, or any solid-state memory. Further, the computer program may exist as a carrier on a network such as the Internet.

  Although pixel conversion related to the optical axis of the image in each individual algorithm has been described, the present invention is not limited to this. In practice, the conversion may be performed between the corresponding point calculation and the feature point supply to the deviation amount calculator 230. Thereby, the calculation load in the deviation amount calculator 230 is reduced. Furthermore, in the same or other embodiments, only selected pixel positions used in each algorithm are transformed with respect to the optical axis. In other words, they are converted only after points are selected for calculating the amount of deviation.

  Although the case where different deviation amounts are calculated in a specific order has been described, the present invention is not limited to this. The amount of deviation can be calculated in any order.

  Although the case of acquiring the shift amount from the high-resolution image has been described, the present invention is not limited to this. For example, the amount of deviation can be obtained from a standard quality image or from a scaled down version of a high resolution image. For example, the shift amount can be acquired from 4: 1 scale reduction. In this case, one pixel in the reduced image is composed of four pixels in the high resolution image. In this situation, the actual pixel value of the reduced image can be selected from four possible pixels in the high resolution image. Such selection may be performed at random.

  Further, if one or more values of the deviation amount indicate that the error is not of an integer pixel value, the nearest integer pixel value above and below the deviation amount value is displayed to the user, and the user You may make it selectable the pixel to use. Alternatively, the nearest pixel value rounded to the nearest integer may be selected.

  While exemplary embodiments of the invention have been described with reference to the accompanying drawings, the invention is not limited to the precise embodiments described above, but from the scope and spirit of the invention as defined by the appended claims. It should be understood that various changes and modifications can be made by those skilled in the art without departing from the scope.

[Derivation of travel distance]
Referring to FIG. 10, assuming two points, p1 represented by a set of coordinates (x1, y1) and p2 represented by a set of coordinates (x2, y2), the rotation of points y1 _r and y2 _r The position of y1 _l and y2 _{l with} respect to movement, scaling can be represented.
Assuming that y1 _l is located above the optical axis, it is described as follows.

ｙ２_ｌが光軸の上方に位置すると仮定すると、以下のように記述される。

Assuming that y2 _l is located above the optical axis, it is described as follows.

式中、Ｓは、スケールを表す定数であり、Ｔは、垂直移動を表す定数である。
［１５］から、光軸の上方に位置する点ｐ１に関して、

In the formula, S is a constant representing a scale, and T is a constant representing a vertical movement.
From [15], for the point p1 located above the optical axis,

［１６］から、光軸の下方に位置する点ｐ２に関して、

From [16], regarding point p2 located below the optical axis,

［１７］および［１８］においてＳは等価であるため、以下のようにＴが導き出される。

Since S is equivalent in [17] and [18], T is derived as follows.

[Derivation of scale amount]
From the above equations [17] and [18], it can be seen that the scale S is calculated as follows.

これを以下のように一般化することができる。

This can be generalized as follows.

式中、移動量Ｔの正負は、点の位置によって決まり、ｐが光軸の上方に位置している場合、値＋Ｔとなり、点が光軸の下方に位置している場合、値は−Ｔとなる。また、θ正負は、点ｐがいずれの象限に位置しているかによって決まる。

In the equation, whether the moving amount T is positive or negative is determined by the position of the point. When p is located above the optical axis, the value is + T. When the point is located below the optical axis, the value is −T. It becomes. Further, θ positive / negative is determined by which quadrant the point p is located.

[Derivation of rotation amount]
Referring to FIG. 11 showing selection of points used for rotation calculation and FIG. 12 showing angle measurement based on vertical position, one from the left side of the optical axis (p1), one from the right side of the optical axis (p2), Random main feature positions are selected.
In order to measure the relative rotation of the points p1 and p2, the gradient between p1 _l and p2 _l is calculated and compared with the gradient between p1 _r and p2 _r , in other words, It is necessary to compare the gradient between two points in the left image with the gradient between corresponding points in the right image. Note that the rotation calculation is invariant to movement, but is variable to scale. The scale (S) is therefore accounted for in the calculation.
The slope between p1 _r and p2 _r is calculated as follows:

垂直視差がなく、スケール（Ｓ）による影響しかないと仮定すると、すなわち、

Assuming there is no vertical parallax and only an influence by the scale (S):

とすると、垂直視差がない勾配は以下のようになる。

Then, the gradient without vertical parallax is as follows.

［１９］は、以下のように表される。

[19] is expressed as follows.

［２０］ は、以下のように表される。

[20] is expressed as follows.

次いで、ロール量の実際の角度を以下のように計算することができる。

The actual angle of roll amount can then be calculated as follows.

三角恒等式を仮定すると以下のようになる。

Assuming the triangular identity,

ロール量を以下の式に表すことができる。

The roll amount can be expressed by the following formula.

Claims (32)

A shift amount calculation method for calculating a shift amount between a first image and a second image that are stereoscopically visible,
Identifying the position of the feature point in the first image and the position of the corresponding feature point in the second image;
In the first image and the second image, determine an optical axis of a camera that captures each of the first image and the second image;
Using a predetermined model, calculating a deviation amount between the position of the feature point in the first image and the position of the corresponding feature point in the second image;
Using random sample consensus technology, test the validity of the calculated deviation amount,
The amount of deviation is the position of the feature point of the first image and the corresponding feature of the second image with respect to the determined optical axis of each of the first image and the second image. Calculated according to the position of the point,
The tested deviation amount is valid when the random sample consensus technique achieves a predetermined condition. The shift amount calculation method according to claim 1,
The deviation amount calculation method is valid when a probability that the deviation amount is accurate exceeds a threshold value. The shift amount calculation method according to claim 1,
The predetermined condition is that the random sample consensus technique is repeated a predetermined number of times. The shift amount calculation method according to claim 3,
The number of iterations is calculated based on the following formula:

Where target_incorrect_est_prob is the probability that the model is incorrect and incorrect_est_prob is the probability that the corresponding feature point is incorrect.
Deviation amount calculation method. The shift amount calculation method according to claim 1,
The model is defined by the following equation:

Where y is the vertical position of the feature point in the second image, xL and yL are the horizontal position and vertical position of the feature point in the first image, respectively, and θ is the amount of rotational deviation. S is a scale shift amount, and T is a vertical shift amount between the first image and the second image. The shift amount calculation method according to claim 1, further comprising:
A deviation amount calculation method including a step of acquiring feature points from each reduced version of the original first image and the original second image using a block matching technique. The deviation amount calculation method according to claim 6, further comprising:
The feature points obtained from the respective reduced versions of the original first image and the original second image are used to start block matching technology in the original first image and the original second image. A deviation amount calculation method including a step of obtaining a first feature point and a second feature point from the original first image and the original second image, which are used as points. The shift amount calculation method according to claim 1, further comprising:
Locating at least one further feature point in the first image and locating at least one corresponding further feature point in the second image,
The position of two feature points in the first image is selected, the position of two corresponding feature points in the second image is selected, and the location between the first image and the second image is selected. A deviation amount calculation method for calculating a vertical deviation amount between the first image and the second image based on a given rotation deviation amount. The shift amount calculation method according to claim 8,
The position of the feature point in the first image and the position of the corresponding feature point in the second image are located above the determined optical axis, and in the first image A method of calculating a deviation amount, wherein the position of the further feature point of the second position and the position of the corresponding feature point in the second image are located below the determined optical axis. The shift amount calculation method according to claim 1,
Selecting a position of a feature point in the first image, selecting a position of a corresponding feature point in the second image, and giving a given position between the first image and the second image A deviation amount calculation method for calculating a scale deviation amount between the first image and the second image based on a vertical deviation amount. The shift amount calculation method according to claim 10,
The position of the feature point in the first image and the position of the corresponding feature point in the second image are located above the determined optical axis, or the first image A deviation amount calculation method in which a position of the feature point in the image and a position of the corresponding feature point in the second image are positioned below the determined optical axis. The shift amount calculation method according to claim 1, further comprising:
Locating at least one further feature point in the first image and locating at least one corresponding further feature point in the second image,
Select the position of two feature points in the first image, select the position of two corresponding feature points in the second image, and place between the first image and the second image A shift amount calculation method for calculating a rotation shift amount between the first image and the second image based on the given scale shift amount. The shift amount calculation method according to claim 12,
The position of the feature point in the first image and the position of the corresponding feature point in the second image are located on the left side of the determined optical axis, and in the first image The displacement amount calculation method in which the position of the further feature point and the position of the corresponding feature point in the second image are located on the right side of the determined optical axis. The shift amount calculation method according to claim 1,
The position of the feature point and the position of the further feature point are randomly generated. The shift amount calculation method according to claim 1,
The position of the feature point is a pixel position in the first image and the second image.   The program which makes a computer perform each step of the deviation | shift amount calculation method of Claim 1.   A recording medium on which the program according to claim 16 is recorded. A shift amount calculation device that calculates a shift amount between a first image and a second image that can be viewed stereoscopically,
A specifier that identifies the position of the feature point in the first image and the position of the corresponding feature point in the second image;
A determinator that determines an optical axis of a camera that captures each of the first image and the second image in the first image and the second image;
An arithmetic unit that calculates a shift amount between the position of the feature point in the first image and the position of the corresponding feature point in the second image using a predetermined model;
Using a random sample consensus technique, and testing the validity of the calculated deviation amount,
The amount of deviation is the position of the feature point of the first image and the corresponding feature of the second image with respect to the determined optical axis of each of the first image and the second image. Calculated according to the position of the point,
The tested deviation amount is valid when the random sample consensus technique achieves a predetermined condition. The deviation amount calculation apparatus according to claim 18, wherein
The deviation amount calculation device is valid when the probability that the deviation amount is accurate exceeds a threshold value. The deviation amount calculation apparatus according to claim 18, wherein
The predetermined condition is that the random sample consensus technique is repeated a predetermined number of times. The deviation amount calculation device according to claim 20, wherein
The number of iterations is calculated based on the following formula:

In the equation, target_incorrect_est_prob is a probability that the model is incorrect, and incorrect_est_prob is a probability that the corresponding feature point is incorrect. The deviation amount calculation apparatus according to claim 18, wherein
The model is defined by the following equation:

Where y is the vertical position of the feature point in the second image, xL and yL are the horizontal position and vertical position of the feature point in the first image, respectively, and θ is the amount of rotational deviation. S is a scale shift amount, and T is a vertical shift amount between the first image and the second image. The deviation amount calculation device according to claim 18, further comprising:
A deviation amount calculation device comprising an acquisition unit that acquires a feature point from each reduced version of an original first image and an original second image using block matching technology. The deviation amount calculation device according to claim 23, wherein
The acquirer further determines the feature points acquired from the respective reduced versions of the original first image and the original second image as the original first image and the original second image. Used as a starting point of the block matching technique in the above, and is operable to acquire the first feature point and the second feature point from the original first image and the original second image . The deviation amount calculation apparatus according to claim 18, wherein
The identifier is further operable to locate a location of at least one additional feature point in the first image and to locate a location of at least one corresponding further feature point in the second image. Yes,
The position of two feature points in the first image is selected, the position of two corresponding feature points in the second image is selected, and the location between the first image and the second image is selected. A deviation amount calculation device that calculates a vertical deviation amount between the first image and the second image based on a given rotation deviation amount. The shift amount calculation apparatus according to claim 25, wherein
The position of the feature point in the first image and the position of the corresponding feature point in the second image are located above the determined optical axis, and in the first image The deviation amount calculation device in which the position of the further feature point and the position of the corresponding feature point in the second image are located below the determined optical axis. The deviation amount calculation apparatus according to claim 18, wherein
Selecting a feature point position in the first image and a corresponding feature point position in the second image, and a given vertical shift between the first image and the second image; A deviation amount calculation device that calculates an amount of scale deviation between the first image and the second image based on an amount. The deviation amount calculation device according to claim 27, wherein
The position of the feature point in the first image and the position of the corresponding feature point in the second image are located above the determined optical axis, or the first image A deviation amount calculation device in which the position of the feature point in the image and the position of the corresponding feature point in the second image are located below the determined optical axis. The deviation amount calculation apparatus according to claim 18, wherein
The identifier is further operable to identify a location of at least one additional feature point in the first image and to identify at least one corresponding further feature location in the second image;
Select the position of two feature points in the first image, select the position of two corresponding feature points in the second image, and place between the first image and the second image A shift amount calculation device that calculates a rotational shift amount between the first image and the second image based on the given scale shift amount. The deviation amount calculation device according to claim 29, wherein
The position of the feature point in the first image and the position of the corresponding feature point in the second image are located on the left side of the determined optical axis, and in the first image The deviation amount calculation device in which the position of the further feature point and the position of the corresponding feature point in the second image are located on the right side of the determined optical axis. The deviation amount calculation apparatus according to claim 18, wherein
The position of the feature point and the position of the further feature point are randomly generated. The deviation amount calculation apparatus according to claim 18, wherein
The position of the feature point is a pixel position in the first image and the second image.

Images