Apparatus for providing calibration data, camera system and method for obtaining calibration data

Abstract

An apparatus comprises a first interface for receiving a plurality of partially overlapping images of an object from a corresponding plurality of cameras being arranged along a first and a second direction according to a camera pattern. The apparatus comprises an analyzing unit configured for selecting at least one corresponding reference point in an overlap area of a set of images, and for determining displacement information along the first and the second direction of the reference point in each of the other images of the set of images. A misalignment of the plurality of images along the first and the second direction is compensated by the displacement information so as to obtain aligned images. The apparatus comprises a determining unit configured for determining offset information between principal points of the plurality of cameras using at least three aligned images. The apparatus comprises a second interface for providing calibration data based on the displacement information and based on the offset information. The calibration data allows for calibrating the plurality of images so as to comply to the camera pattern.

Claims

1. Apparatus comprising: a first interface for receiving a plurality of partially overlapping images of an object from a corresponding plurality of camera positions being arranged along a first and a second direction according to a two-dimensional or three-dimensional camera pattern, wherein patterns comprising camera positions that differ in two directions are two-dimensional patterns and patterns comprising camera positions that differ in three directions are three-dimensional patterns; an analyzing unit configured for selecting at least one corresponding reference point in an overlap area of a set of overlapping images, and for determining a displacement information along the first and the second direction of the reference point in each of the other images of the set of images, wherein a misalignment of the plurality of images along the first and the second direction is compensated by the displacement information so as to acquire aligned images; a determining unit configured for determining an offset information between principal points at the plurality of camera positions using at least three aligned images; and a second interface for providing calibration data based on the displacement information and based on the offset information, the calibration data allowing for calibrating the plurality of images so as to comply to the camera pattern; wherein the analyzing unit is configured to determine the displacement information minimizing an error of a first minimization criteria, wherein for a 2D camera pattern the first minimization criteria is based on the determination rule; $\underset{x_1,x_2,x_3,\mathrm{.Math.},x_N}{\arg \min }\underset{\left(p,q\right)}{.Math.}.Math.v\left(H\left(x_p,C_p,C_q\right).Math.m_{p,q}^{\left(p\right)}\right)-v\left(H\left(x_q,C_p,C_q\right).Math.m_{p,q}^{\left(q\right)}\right).Math.$ $\mathrm{with}.Math.x.Math.=\underset{l}{.Math.}{x}_l^2$ wherein the determining unit is configured to determine the offset information minimizing an error of a second minimization criteria, wherein for the 2D camera pattern the second minimization criteria is based on the determination rule $\underset{x_1,x_2,x_3,\mathrm{.Math.},x_N}{\arg \min }\underset{\left(p,q\right)}{.Math.}.Math.\left(u\left(H\left(x_p,C_p,C_q\right).Math.m_{p,q,r}^{\left(p\right)}\right)-u\left(H\left(x_q,C_p,C_q\right).Math.m_{p,q,r}^{\left(q\right)}\right)\right)\frac{1}{d\left(C_p-C_q\right)}-\left(u\left(H\left(x_p,C_p,C_r\right).Math.m_{p,q,r}^{\left(p\right)}\right)-u\left(H\left(x_r,C_p,C_r\right).Math.m_{p,q,r}^{\left(q\right)}\right)\right)\frac{1}{d\left(C_p-C_r\right)}.Math.$ $\mathrm{with}.Math.x.Math.=\underset{l}{.Math.}{x}_l^2$ wherein argmin denotes the minimization criteria and p, q and r denote indices of individual cameras. C.sub.p, C.sub.q, C.sub.r denote camera positions of cameras p, q and r, d(C.sub.pC.sub.q) is a distance between the camera positions, x.sub.p, x.sub.q and x.sub.r are vectors with parameters to be determined so as to minimizing the error for camera p, q and r, H() is a function providing a homography matrix undistorting points according to a parameter vector x.sub.p and camera positions C.sub.p and C.sub.q, m.sub.p,q=[m.sup.(p).sub.p,q m.sup.(q).sub.p,q] denotes a set of reference points wherein m.sup.(p).sub.p,q corresponds to the respective reference points in camera p, m.sub.p,q,r=[m.sup.(p).sub.p,q,r m.sup.(q).sub.p,q,r m.sup.(r).sub.p,q,r] denotes a set of reference points wherein m.sup.(p).sub.p,q,r corresponds to the respective reference points in camera p, Functions u() and v() extract the horizontal/vertical component of an image point respectively, the set comprises all pairs of partially overlapping images; the set comprises triplets of partially overlapping images; such that each of the N cameras considered in the minimization problem is comprised in at least one pair of cameras comprised in and at least in one triplet of cameras comprised in ; and/or wherein the analyzing unit is configured to determine the displacement information minimizing an error of a linearized first minimization criteria, wherein for a 2D camera pattern the linearized first minimization criteria is based on the determination rule; $\underset{x_1,x_2,x_3,\mathrm{.Math.},x_N}{\arg \min }\underset{\left(p,q\right)}{.Math.}\left[J_{p,q}^{\left(p\right)}\text{|}{J}_{p,q}^{\left(q\right)}\right].Math.\left[\begin{array}{c}{x}_p^T\\ x_q^T\end{array}\right]+b_{p,q}{\mathrm{wherein}\left(v\left(H\left(x_p,C_p,C_q\right).Math.m_{p,q}^{\left(p\right)}\right)-v\left(H\left(x_q,C_p,C_q\right).Math.m_{p,q}^{\left(q\right)}\right)\right)}^2[J_{p,q}^{\left(p\right)}\text{|}{J}_{p,q}^{\left(q\right)}].Math.\left[\begin{array}{c}{x}_p^T\\ x_q^T\end{array}\right]+b_{p,q}$ wherein the determining unit is configured to determine the offset information minimizing an error of a linearized second minimization criteria, wherein for the 2D camera pattern the linearized second minimization criteria is based on the determination rule $\underset{x_1,x_2,x_3,\mathrm{.Math.},x_N}{\arg \min }\underset{\left(p,q,r\right)}{.Math.}\left[\begin{array}{cc}{J}_{p,q,r}^{\left(p\right)}& \begin{array}{cc}{J}_{p,q,r}^{\left(q\right)}& J_{p,q,r}^{\left(r\right)}\end{array}\end{array}\right].Math.\left[\begin{array}{c}{x}_p^T\\ x_q^T\\ x_r^T\end{array}\right]+b_{p,q,r}$ $\mathrm{wherein}(\left(u\left(H\left(x_p,C_p,C_q\right).Math.m_{p,q,r}^{\left(p\right)}\right)-u\left(H\left(x_q,C_p,C_q\right).Math.m_{p,q,r}^{\left(q\right)}\right)\right)\frac{1}{d\left(C_p-C_q\right)}-{\left(u\left(H\left(x_p,C_p,C_r\right).Math.m_{p,q,r}^{\left(p\right)}\right)-u\left(H\left(x_r,C_p,C_r\right).Math.m_{p,q,r}^{\left(q\right)}\right)\right)\frac{1}{d\left(C_p-C_r\right)})}^2[\begin{array}{cc}{J}_{p,q,r}^{\left(p\right)}& \begin{array}{cc}{J}_{p,q,r}^{\left(q\right)}& J_{p,q,r}^{\left(r\right)}\end{array}\end{array}].Math.\left[\begin{array}{c}{x}_p^T\\ x_q^T\\ x_r^T\end{array}\right]+b_{p,q,r}$ wherein argmin denotes the minimization criteria p, q and r denote indices of individual cameras, C.sub.p, C.sub.q, C.sub.r denote camera positions of cameras p, q and r, d(C.sub.pC.sub.q) is a distance between the camera positions, H() is a function providing a homography matrix undistorting points according to a parameter vector x.sub.p and camera positions C.sub.p and C.sub.q, corresponding to camera p with parameter vector x.sub.p, x.sub.q and x.sub.r, are vectors with parameters to be determined so as to minimizing the error for camera p, q and r, m.sub.p,q=[m.sup.(p).sub.p,q m.sup.(q).sub.p,q] denotes a set of reference points wherein m.sup.(p).sub.p,q corresponds to the respective reference points in camera p, m.sub.p,q,r=[m.sup.(p).sub.p,q,r m.sup.(q).sub.p,q,r m.sup.(r).sub.p,q,r] denotes a set of reference points wherein m.sup.(p).sub.p,q,r corresponds to the respective reference points in camera p, the set comprises all pairs of partially overlapping images; the set comprises triplets of partially overlapping images; such that each of the N cameras considered in the minimization problem is comprised in at least one pair of cameras comprised in and in at least one triplet of cameras comprised in , functions u() and v() extract the horizontal/vertical component of an image point respectively, J.sub.p,q=[J.sup.(p).sub.p,q J.sup.(q).sub.p,q] and J.sub.p,q,r=[J.sup.(p).sub.p,q,r J.sup.(q).sub.p,q,r J.sup.(r).sub.p,q,r] denote the Jacobi matrices for camera pairs and camera triplets, respectively, J.sup.(p).sub.p,q and J.sup.(p).sub.p,q,r denote sub-matrices corresponding to a camera p, b.sub.p,q and b.sub.p,q,r denote residual elements.

2. The apparatus according to claim 1, wherein the apparatus is configured, for determining the displacement information, for using a feature detection and matching algorithm to detect references on pairs of images and for acquiring matched image coordinates between the images of the pair of images.

3. The apparatus according to claim 1, wherein the apparatus is configured for performing a self-calibration without imaging a calibration chart.

4. The apparatus according to claim 1, wherein the analyzing unit is configured for determining the displacement information using a set of parameters indicating a real condition of the camera pattern, the parameters comprising a non-linear relationship with respect to each other, wherein the analyzing unit is configured to use a linearized version of the set of parameters and to determine the displacement information by minimizing an error of the linearized version with respect to a desired condition of the camera pattern.

5. The apparatus according to claim 1, wherein the analyzing unit is configured to determine the displacement information minimizing an error of a first minimization criteria, wherein for a 3D camera pattern the first minimization criteria is based on the determination rule; $\underset{x_1,x_2,x_3,\mathrm{.Math.},x_N}{\mathrm{argmin}}\underset{\left(p,q\right)}{.Math.}.Math.v\left(H\left(x_p,C_p,C_q\right).Math.m_{p,q}^{\left(p\right)}\right)-v\left(H\left(x_q,C_p,C_q\right).Math.m_{p,q}^{\left(q\right)}\right).Math.\mathrm{with}.Math..Math.x.Math..Math.=\underset{l}{.Math.}{x}_l^2$ wherein the determining unit is configured to determine the offset information minimizing an error of a second minimization criteria, wherein for the 3D camera pattern the second minimization criteria is based on the determination rule $\underset{x_1,x_2,x_3,\mathrm{.Math.},x_N}{\mathrm{argmin}}\underset{\left(p,q,r\right)}{.Math.}.Math.g\left(x_p,x_q,x_r\right).Math.\mathrm{with}.Math.x.Math.={.Math.}_l{x}_l^2$ $\mathrm{wherein}$ $g\left(x_p,x_q,x_r\right):={\left[\tilde{H}\left(x_q\right).Math.m_q\right]}_x.Math.\left(u_p^{\#}.Math.T_{\left(p,q,r\right),1}+v_p^{\#}.Math.T_{\left(p,q,r\right),2}+T_{\left(p,q,r\right),3}\right).Math.{\left[\tilde{H}\left(x_r\right).Math.m_r\right]}_x$ $\mathrm{wherein}$ $m^{\#}={\left[u_p^{\#}{v}_p^{\#}1\right]}^T=\tilde{H}\left(x_p\right).Math.m$ wherein argmin denotes the minimization criteria, and p, q and r denote indices of individual cameras, C.sub.p, C.sub.q denote camera positions of cameras p and q, d(C.sub.pC.sub.q) is a distance between the camera positions, H() is a function providing a homography matrix undistorting points according to a parameter vector x.sub.p and camera positions C.sub.p and C.sub.q, corresponding to camera p with parameter vector x.sub.p, x.sub.q, x.sub.q and x.sub.r are vectors with parameters to be determined so as to minimizing the error for camera p, q and r, m.sub.p,q=[m.sup.(p).sub.p,q m.sup.(q).sub.p,q] denotes a set of reference points wherein m.sup.(p).sub.p,q corresponds to the respective reference points in camera p, m.sub.p,q,r=[m.sup.(p).sub.p,q,r m.sup.(q).sub.p,q,r m.sup.(r).sub.p,q,r] denotes a set of reference points wherein m.sup.(p).sub.p,q,r corresponds to the respective reference points in camera p, Function v() extracts the vertical component of an image point, the set comprises all pairs of partially overlapping images; the set comprises triplets of partially overlapping images; such that each of the N cameras considered in the minimization problem is comprised at least in one pair of cameras comprised in and in at least one triplet of cameras comprised in , wherein T.sub.(p,q,r),i represents a matrix representing the Trifocal Tensor corresponding to camera indices p, q, and r, m.sub.p.sup.# denotes a transformed point according to a homography matrix H wherein u.sub.p.sup.# and v.sub.p.sup.# denote the horizontal and vertical component of a point respectively, g models the Trifocal Tensor as defined and {tilde over (H)}(x.sub.i) is a result of a multiplication of a center matrix K with a rotation matrix R.sub.i of camera i, correcting a camera's orientation such that it corresponds to its ideal orientation as given by an ideal camera setup and the center matrix K modelling a standard camera matrix, K being based on $k=\left(\begin{array}{ccc}{f}_x& s& {}_x\\ 0& f_y& {}_y\\ 0& 0& 1\end{array}\right)$ with f.sub.x and f.sub.y denoting focal lengths along a first and a second direction, s denotes a skew factor and .sub.x and .sub.y denote deviations along the first and second direction.

6. The apparatus according to claim 1, wherein the analyzing unit is configured to determine the displacement information minimizing an error of a linearized first minimization criteria, wherein for a 3D camera pattern the linearized first minimization criteria is based on the determination rule; $\underset{x_1,x_2,x_3,\mathrm{.Math.},x_N}{\mathrm{argmin}}\underset{\left(p,q\right)}{.Math.}\left[J_{p,q}^{\left(p\right)}.Math.J_{p,q}^{\left(q\right)}\right].Math.\left[\begin{array}{c}{x}_p^T\\ x_q^T\end{array}\right]+b_{p,q}$ ${\mathrm{wherein}\text{.Math.}\left(v\left(H\left(x_p,C_p,C_q\right).Math.m_{p,q}^{\left(p\right)}\right)-v\left(H\left(x_q,C_p,C_q\right).Math.m_{p,q}^{\left(q\right)}\right)\right)}^2\left[J_{p,q}^{\left(p\right)}.Math.J_{p,q}^{\left(q\right)}\right].Math.\left[\begin{array}{c}{x}_p^T\\ x_q^T\end{array}\right]+b_{p,q}$ wherein the determining unit is configured to determine the offset information minimizing an error of a linearized second minimization criteria, wherein for the 3D camera pattern the linearized second minimization criteria is based on the determination rule $\underset{x_1,x_2,x_3,\mathrm{.Math.},x_N}{\mathrm{argmin}}\underset{\left(p,q,r\right)}{.Math.}\left[J_{p,q,r}^{\left(p\right)}{J}_{p,q,r}^{\left(q\right)}{J}_{p,q,r}^{\left(r\right)}\right].Math.\left[\begin{array}{c}{x}_p^T\\ x_q^T\\ x_r^T\end{array}\right]+b_{p,q,r}$ ${\mathrm{wherein}\left(g\left(x_p,x_q,x_r\right)\right)}^2=({\left[\tilde{H}\left(x_q\right).Math.m_q\right]}_x.Math.\left(u_p^{\#}.Math.T_{\left(p,q,r\right),1}+v_p^{\#}.Math.T_{\left(p,q,r\right),2}+T_{\left(p,q,r\right),3}\right).Math.{\left[{\tilde{H}\left(x_r.Math.m_r\right]}_x\right)}^2\left[J_{p,q,r}^{\left(p\right)}{J}_{p,q,r}^{\left(q\right)}{J}_{p,q,r}^{\left(r\right)}\right].Math.\left[\begin{array}{c}{x}_p^T\\ x_q^T\\ x_r^T\end{array}\right]+b_{p,q,r}\mathrm{wherein}{m}_p^{\#}={\left[u_p^{\#}{v}_p^{\#}1\right]}^T=\tilde{H}\left(x_p\right).Math.m$ wherein argmin denotes the minimization criteria p, q and r denote indices of individual cameras, C.sub.p, C.sub.p, C.sub.r denote camera positions of cameras p, q and r, H is a function providing a homography matrix
H(x.sub.p,C.sub.p,C.sub.q)=R.sub.0.Math.K.Math.R.sub.i=R.sub.0{tilde over (H)}(x.sub.p)
with {tilde over (H)}(x.sub.p)=K.Math.R.sub.i corresponding to camera p with parameter vector x.sub.p, x.sub.q, and x.sub.r, are vectors with parameters to be determined so as to minimizing the error for camera p, q and r, m.sub.p,q=[m.sup.(p).sub.p,q m.sup.(q).sub.p,q] denotes a set of reference points wherein m.sup.(p).sub.p,q corresponds to the respective reference points in camera p, m.sub.p,q,r=[m.sup.(p).sub.p,q,r m.sup.(q).sub.p,q,r m.sup.(r).sub.p,q,r] denotes a set of reference points wherein M.sup.(p).sub.p,q,r corresponds to the respective reference points in camera p, the set comprises all pairs of partially overlapping images; the set comprises triplets of partially overlapping images; such that each of the N cameras considered in the minimization problem is comprised in at least one pair of cameras comprised in and in at least one triplet of cameras comprised in , Functions u() and v() extract the horizontal/vertical component of an image point respectively, J.sub.p,q=[J.sup.(p).sub.p,q J.sup.(q).sub.p,q] and J.sub.p,q,r=[J.sup.(p).sub.p,q,r J.sup.(q).sub.p,q,r J.sup.(r).sub.p,q,r] denote the Jacobi matrices according to
(x,a):=T(x,a)=T F.sub.x,a(1,0)=F.sub.x,a(0)+F.sub.x,a(0)
F.sub.x,a:.fwdarw.:=t>(a+t.Math.(xa))
and
0=[Tg.sub.1,1(,a),Tg.sub.1,2(,a), . . . ,Tg.sub.3,3(,a)].sup.T
0=J.Math.+b for camera pairs and camera triplets, respectively, J.sup.(p).sub.p,q and J.sup.(p).sub.p,q,r denote sub-matrices corresponding to a camera p, b.sub.p,q and b.sub.p,q,r denote residual elements, T.sub.(p,q,r),i represents a matrix representing the Trifocal Tensor corresponding to camera indices p, q, and r, m.sub.p.sup.# denotes a transformed point according to a homography H, wherein u.sub.p.sup.# and v.sub.p.sup.# denote the horizontal and vertical component of a point respectively and {tilde over (H)}(x.sub.i) of camera i is a multiplication of a rotation matrix R.sub.i correcting a camera's orientation such that it corresponds to its ideal orientation as given by an ideal camera setup and a center matrix K modelling a standard camera matrix based on $K=\left(\begin{array}{ccc}{f}_x& s& {}_x\\ 0& f_y& {}_y\\ 0& 0& 1\end{array}\right)$ with f.sub.x and f.sub.y denoting focal lengths along a first and a second direction, s denotes a skew factor and .sub.x and .sub.y denote deviations along the first and second direction; wherein R.sub.0 is an outer rotation matrix, R.sub.i is an inner rotation matrix R.sub.i of camera i=p, C.sub.p, C.sub.q denote camera positions of cameras p and q and x.sub.p relates to a vector, F.sub.x,a is a function of t that evaluates the function f(x) at the point a+t.Math.(xa), f(x) is the function to approximate at a point a, parameters to the function f(x) are comprised in the parameter vector x, wherein t is a scalar value, a is a vector with identical size as x, first order Taylor approximation T of a function f(x) at the point a is expressed as Taylor expansion of a scalar function F.sub.x,a(t), wherein F.sub.x,a is expanded at point t.sub.0=0 by computing the function value of F.sub.x,a with t.sub.0=0 and the value of the first order derivative F.sub.x,a=F.sub.x,ad/dt also at t.sub.0=0, wherein T g.sub.i,j(, a) denotes the Taylor approximation of a function g and indices in g denote an entry in a matrix returned by function g.

7. The apparatus of claim 1, wherein the analyzing unit is configured to determine the displacement information pairwise for a pair of images of the plurality of images.

8. The apparatus of claim 1, wherein the analyzing unit is configured to first determine the displacement information along one of the first and the second direction and to subsequently determine the displacement information for the other direction.

9. The apparatus of claim 1, wherein the analyzing unit is configured to determine the displacement information along a first image direction independent from the displacement information along a second image direction.

10. The apparatus of claim 1, wherein the calibration data is based on angles that describe a rotation of the cameras, to a focal length of the cameras and to a principal point of the cameras, wherein the calibration data does not comprise information indicating a position of cameras of the plurality of camera positions.

11. The apparatus of claim 1, further comprising at least one camera being configured to provide the plurality of images from the plurality of camera positions, wherein the apparatus is configured to determine a depth map of an object region comprising a plurality of subregions, wherein the at least one camera is configured to provide the corresponding image by projecting one of the plurality of subregions.

12. The apparatus of claim 1, further comprising at least one camera being configured to provide the plurality of images from the plurality of camera positions, wherein the apparatus is configured to apply the calibration data to the plurality of images so as to acquire a plurality of rectified images and to provide the plurality of rectified images.

13. The apparatus of claim 1, wherein displacement information referring to an image of the plurality of images comprises at least one of a shift of the image along a lateral direction and a rotation of the image.

14. The apparatus of claim 1, wherein the set of images is a subset of the plurality of images.

15. Camera system comprising at least one camera being configured to provide a plurality of images from a corresponding plurality of camera positions and comprising a memory having stored thereon calibration information derived from calibration data generated from an apparatus according to one of previous claims, wherein the calibration information is the calibration data or incorporates at least part thereof.

16. The camera system of claim 15, further comprising an apparatus of claim 1.

17. Method for acquiring calibration data, the method comprising: receiving a plurality of partially overlapping images of an object from a corresponding plurality of camera positions being arranged along a first and a second direction according to a two-dimensional or three-dimensional camera pattern, wherein patterns comprising camera positions that differ in two directions are two-dimensional patterns and patterns comprising camera positions that differ in three directions are three-dimensional patterns; selecting at least one corresponding reference point in an overlap area of a set of overlapping images, and determining a displacement information along the first and the second direction of the reference point in each of the other images of the set of images, such that a misalignment of the plurality of images along the first and the second direction is compensated by the displacement information so as to acquire aligned images; determining an offset information between principal points at the plurality of camera positions using at least three aligned images; and providing calibration data based on the displacement information and based on the offset information, the calibration data allowing for calibrating the plurality of images so as to comply to the camera pattern; and determining the displacement information minimizing an error of a first minimization criteria, wherein for a 2D camera pattern the first minimization criteria is based on the determination rule; $\underset{x_1,x_2,x_3,\mathrm{.Math.},x_N}{\mathrm{argmin}}\underset{\left(p,q\right)}{.Math.}.Math.v\left(H\left(x_p,C_p,C_q\right).Math.m_{p,q}^{\left(p\right)}\right)-v\left(H\left(x_q,C_p,C_q\right).Math.m_{p,q}^{\left(q\right)}\right).Math.\mathrm{with}.Math..Math.x.Math..Math.=\underset{l}{.Math.}{x}_l^2$ determining the offset information minimizing an error of a second minimization criteria, wherein for the 2D camera pattern the second minimization criteria is based on the determination rule $\underset{x_1,x_2,x_3,\mathrm{.Math.},x_N}{\mathrm{argmin}}\underset{\left(p,q,r\right)}{.Math.}.Math.(u\left(H\left(x_p,C_p,C_q\right).Math.m_{p,q,r}^{\left(p\right)}\right)-u\left(H\left(x_q,C_p,C_q\right).Math.m_{p,q,r}^{\left(q\right)}\right))\frac{1}{d\left(C_p-C_q\right)}-(u\left(H\left(x_p,C_p,C_r\right).Math.m_{p,q,r}^{\left(p\right)}\right)-u\left(H\left(x_r,C_p,C_r\right).Math.m_{p,q,r}^{\left(r\right)}\right))\frac{1}{d\left(C_p-C_r\right)}.Math.\mathrm{with}.Math.x.Math.=\underset{l}{.Math.}{x}_l^2$ wherein argmin denotes the minimization criteria and p, q and r denote indices of individual cameras. C.sub.p, C.sub.q, C.sub.r denote camera positions of cameras p, q and r, d(C.sub.pC.sub.q) is a distance between the camera positions, x.sub.p, x.sub.q and x.sub.r are vectors with parameters to be determined so as to minimizing the error for camera p, q and r, H() is a function providing a homography matrix undistorting points according to a parameter vector x.sub.p and camera positions C.sub.p and C.sub.q, m.sub.p,q=[m.sup.(p).sub.p,q m.sup.(q).sub.p,q] denotes a set of reference points wherein m.sup.(p).sub.p,q corresponds to the respective reference points in camera p, m.sub.p,q,r=[m.sup.(p).sub.p,q,r m.sup.(q).sub.p,q,r m.sup.(r).sub.p,q,r] denotes a set of reference points wherein m.sup.(p).sub.p,q,r corresponds to the respective reference points in camera p, Functions u() and v() extract the horizontal/vertical component of an image point respectively, the set comprises all pairs of partially overlapping images; the set comprises triplets of partially overlapping images; such that each of the N cameras considered in the minimization problem is comprised in at least one pair of cameras comprised in and at least in one triplet of cameras comprised in ; and/or determining the displacement information minimizing an error of a linearized first minimization criteria, wherein for a 2D camera pattern the linearized first minimization criteria is based on the determination rule; $\underset{x_1,x_2,x_3,\mathrm{.Math.},x_N}{\mathrm{argmin}}\underset{\left(p,q\right)}{.Math.}\left[J_{p,q}^{\left(p\right)}.Math.J_{p,q}^{\left(q\right)}\right].Math.\left[\begin{array}{c}{x}_p^T\\ x_q^T\end{array}\right]+b_{p,q}$ ${\mathrm{wherein}\text{.Math.}\left(v\left(H\left(x_p,C_p,C_q\right).Math.m_{p,q}^{\left(p\right)}\right)-v\left(H\left(x_q,C_p,C_q\right).Math.m_{p,q}^{\left(q\right)}\right)\right)}^2\left[J_{p,q}^{\left(p\right)}.Math.J_{p,q}^{\left(q\right)}\right].Math.\left[\begin{array}{c}{x}_p^T\\ x_q^T\end{array}\right]+b_{p,q}$ determining the offset information minimizing an error of a linearized second minimization criteria, wherein for the 2D camera pattern the linearized second minimization criteria is based on the determination rule $\underset{x_1,x_2,x_3,\mathrm{.Math.},x_N}{\mathrm{argmin}}\underset{\left(p,q,r\right)}{.Math.}\left[J_{p,q,r}^{\left(p\right)}{J}_{p,q,r}^{\left(q\right)}{J}_{p,q,r}^{\left(r\right)}\right].Math.\left[\begin{array}{c}{x}_p^T\\ x_q^T\\ x_r^T\end{array}\right]+b_{p,q,r}$ ${\mathrm{wherein}\text{.Math.}\left(\left(u\left(H\left(x_p,C_p,C_q\right).Math.m_{p,q,r}^{\left(p\right)}\right)-u\left(H\left(x_q,C_p,C_q\right).Math.m_{p,q,r}^{\left(q\right)}\right)\right)\frac{1}{d\left(C_p-C_q\right)}-\left(u\left(H\left(x_p,C_p,C_r\right).Math.m_{p,q,r}^{\left(p\right)}\right)-u\left(H\left(x_r,C_p,C_r\right).Math.m_{p,q,r}^{\left(r\right)}\right)\right)\frac{1}{d\left(C_p-C_r\right)}\right)}^2\left[J_{p,q,r}^{\left(p\right)}{J}_{p,q,r}^{\left(q\right)}{J}_{p,q,r}^{\left(r\right)}\right].Math.\left[\begin{array}{c}{x}_p^T\\ x_q^T\\ x_r^T\end{array}\right]+b_{p,q,r}$ wherein argmin denotes the minimization criteria p, q and r denote indices of individual cameras, C.sub.p, C.sub.q, C.sub.r denote camera positions of cameras p, q and r, d(C.sub.pC.sub.q) is a distance between the camera positions, H() is a function providing a homography matrix undistorting points according to a parameter vector x.sub.p and camera positions C.sub.p and C.sub.q, corresponding to camera p with parameter vector x.sub.p, x.sub.q and x.sub.r, are vectors with parameters to be determined so as to minimizing the error for camera p, q and r, m.sub.p,q=[m.sup.(p).sub.p,q m.sup.(q).sub.p,q] denotes a set of reference points wherein m.sup.(p).sub.p,q corresponds to the respective reference points in camera p, m.sub.p,q,r=[m.sup.(p).sub.p,q,r m.sup.(q).sub.p,q,r m.sup.(r).sub.p,q,r] denotes a set of reference points wherein m.sup.(p).sub.p,q,r corresponds to the respective reference points in camera p, the set comprises all pairs of partially overlapping images; the set comprises triplets of partially overlapping images; such that each of the N cameras considered in the minimization problem is comprised in at least one pair of cameras comprised in and in at least one triplet of cameras comprised in , functions u() and v() extract the horizontal/vertical component of an image point respectively, J.sub.p,q=[J.sup.(p).sub.p,q J.sup.(q).sub.p,q] and J.sub.p,q,r=[J.sup.(p).sub.p,q,r J.sup.(q).sub.p,q,r J.sup.(r).sub.p,q,r] denote the Jacobi matrices for camera pairs and camera triplets, respectively, J.sup.(p).sub.p,q and J.sup.(p).sub.p,q,r denote sub-matrices corresponding to a camera p, b.sub.p,q and b.sub.p,q,r denote residual elements.

18. A non-transitory digital storage medium having a computer program stored thereon to perform the method for acquiring calibration data, the method comprising: receiving a plurality of partially overlapping images of an object from a corresponding plurality of camera positions being arranged along a first and a second direction according to a two-dimensional or three-dimensional camera pattern, wherein patterns comprising camera positions that differ in two directions are two-dimensional patterns and patterns comprising camera positions that differ in three directions are three-dimensional patterns; selecting at least one corresponding reference point in an overlap area of a set of overlapping images, and determining a displacement information along the first and the second direction of the reference point in each of the other images of the set of images, such that a misalignment of the plurality of images along the first and the second direction is compensated by the displacement information so as to acquire aligned images; determining an offset information between principal points at the plurality of camera positions using at least three aligned images; and providing calibration data based on the displacement information and based on the offset information, the calibration data allowing for calibrating the plurality of images so as to comply to the camera pattern; and determining the displacement information minimizing an error of a first minimization criteria, wherein for a 2D camera pattern the first minimization criteria is based on the determination rule; $\underset{x_1,x_2,x_3,\mathrm{.Math.},x_N}{\mathrm{argmin}}\underset{\left(p,q\right)}{.Math.}.Math.v\left(H\left(x_p,C_p,C_q\right).Math.m_{p,q}^{\left(p\right)}\right)-v\left(H\left(x_q,C_p,C_q\right).Math.m_{p,q}^{\left(q\right)}\right).Math.\mathrm{with}.Math..Math.x.Math..Math.=\underset{l}{.Math.}{x}_l^2$ determining the offset information minimizing an error of a second minimization criteria, wherein for the 2D camera pattern the second minimization criteria is based on the determination rule $\underset{x_1,x_2,x_3,\mathrm{.Math.},x_N}{\mathrm{argmin}}\underset{\left(p,q,r\right)}{.Math.}.Math.(u\left(H\left(x_p,C_p,C_q\right).Math.m_{p,q,r}^{\left(p\right)}\right)-u\left(H\left(x_q,C_p,C_q\right).Math.m_{p,q,r}^{\left(q\right)}\right))\frac{1}{d\left(C_p-C_q\right)}-(u\left(H\left(x_p,C_p,C_r\right).Math.m_{p,q,r}^{\left(p\right)}\right)-u\left(H\left(x_r,C_p,C_r\right).Math.m_{p,q,r}^{\left(r\right)}\right))\frac{1}{d\left(C_p-C_r\right)}.Math.\mathrm{with}.Math.x.Math.=\underset{l}{.Math.}{x}_l^2$ wherein argmin denotes the minimization criteria and p, q and r denote indices of individual cameras. C.sub.p, C.sub.q, C.sub.r denote camera positions of cameras p, q and r, d(C.sub.pC.sub.q) is a distance between the camera positions, x.sub.p, x.sub.q and x.sub.r are vectors with parameters to be determined so as to minimizing the error for camera p, q and r, H() is a function providing a homography matrix undistorting points according to a parameter vector x.sub.p and camera positions C.sub.p and C.sub.q, m.sub.p,q=[m.sup.(p).sub.p,q m.sup.(q).sub.p,q] denotes a set of reference points wherein m.sup.(p).sub.p,q corresponds to the respective reference points in camera p, m.sub.p,q,r=[m.sup.(p).sub.p,q,r m.sup.(q).sub.p,q,r m.sup.(r).sub.p,q,r] denotes a set of reference points wherein m.sup.(p).sub.p,q,r corresponds to the respective reference points in camera p, Functions u() and v() extract the horizontal/vertical component of an image point respectively, the set comprises all pairs of partially overlapping images; the set comprises triplets of partially overlapping images; such that each of the N cameras considered in the minimization problem is comprised in at least one pair of cameras comprised in and at least in one triplet of cameras comprised in ; and/or determining the displacement information minimizing an error of a linearized first minimization criteria, wherein for a 2D camera pattern the linearized first minimization criteria is based on the determination rule; $\underset{x_1,x_2,x_3,\mathrm{.Math.},x_N}{\mathrm{argmin}}\underset{\left(p,q\right)}{.Math.}\left[J_{p,q}^{\left(p\right)}.Math.J_{p,q}^{\left(q\right)}\right].Math.\left[\begin{array}{c}{x}_p^T\\ x_q^T\end{array}\right]+b_{p,q}$ $\mathrm{wherein}$ ${\left(v\left(H\left(x_p,C_p,C_q\right).Math.m_{p,q}^{\left(p\right)}\right)-v\left(H\left(x_q,C_p,C_q\right).Math.m_{p,q}^{\left(q\right)}\right)\right)}^2\left[J_{p,q}^{\left(p\right)}.Math.J_{p,q}^{\left(q\right)}\right].Math.\left[\begin{array}{c}{x}_p^T\\ x_q^T\end{array}\right]+b_{p,q}$ determining the offset information minimizing an error of a linearized second minimization criteria, wherein for the 2D camera pattern the linearized second minimization criteria is based on the determination rule $\underset{x_1,x_2,x_3,\mathrm{.Math.},x_N}{\mathrm{argmin}}\underset{\left(p,q,r\right)}{.Math.}\left[J_{p,q,r}^{\left(p\right)}{J}_{p,q,r}^{\left(q\right)}{J}_{p,q,r}^{\left(r\right)}\right].Math.\left[\begin{array}{c}{x}_p^T\\ x_q^T\\ x_r^T\end{array}\right]+b_{p,q,r}$ $\mathrm{wherein}\text{.Math.}(\left(u\left(H\left(x_p,C_p,C_q\right).Math.m_{p,q,r}^{\left(p\right)}\right)-u\left(H\left(x_q,C_p,C_q\right).Math.m_{p,q,r}^{\left(q\right)}\right)\right)\frac{1}{d\left(C_p-C_q\right)}-{\left(u\left(H\left(x_p,C_p,C_r\right).Math.m_{p,q,r}^{\left(p\right)}\right)-u\left(H\left(x_r,C_p,C_r\right).Math.m_{p,q,r}^{\left(r\right)}\right)\right)\frac{1}{d\left(C_p-C_r\right)})}^2\left[J_{p,q,r}^{\left(p\right)}{J}_{p,q,r}^{\left(q\right)}{J}_{p,q,r}^{\left(r\right)}\right].Math.\left[\begin{array}{c}{x}_p^T\\ x_q^T\\ x_r^T\end{array}\right]+b_{p,q,r}$ wherein argmin denotes the minimization criteria p, q and r denote indices of individual cameras, C.sub.p, C.sub.q, C.sub.r denote camera positions of cameras p, q and r, d(C.sub.pC.sub.q) is a distance between the camera positions, H() is a function providing a homography matrix undistorting points according to a parameter vector x.sub.p and camera positions C.sub.p and C.sub.q, corresponding to camera p with parameter vector x.sub.p, x.sub.q and x.sub.r, are vectors with parameters to be determined so as to minimizing the error for camera p, q and r, m.sub.p,q=[m.sup.(p).sub.p,q m.sup.(q).sub.p,q] denotes a set of reference points wherein m.sup.(p).sub.p,q corresponds to the respective reference points in camera p, m.sub.p,q,r=[m.sup.(p).sub.p,q,r m.sup.(q).sub.p,q,r m.sup.(r).sub.p,q,r] denotes a set of reference points wherein m.sup.(p).sub.p,q,r corresponds to the respective reference points in camera p, the set comprises all pairs of partially overlapping images; the set comprises triplets of partially overlapping images; such that each of the N cameras considered in the minimization problem is comprised in at least one pair of cameras comprised in and in at least one triplet of cameras comprised in , functions u() and v() extract the horizontal/vertical component of an image point respectively, J.sub.p,q=[J.sup.(p).sub.p,q J.sup.(q).sub.p,q] and J.sub.p,q,r=[J.sup.(p).sub.p,q,r J.sup.(q).sub.p,q,r J.sup.(r).sub.p,q,r] denote the Jacobi matrices for camera pairs and camera triplets, respectively, J.sup.(p).sub.p,q and J.sup.(p).sub.p,q,r denote sub-matrices corresponding to a camera p, b.sub.p,q and b.sub.p,q, denote residual elements, when said computer program is run by a computer.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Embodiments of the present invention will be detailed subsequently referring to the appended drawings, in which:

(2) FIG. 1 is a schematic block diagram of an apparatus according to an embodiment.

(3) FIG. 2a is a schematic top view of a plurality of cameras before mechanical calibration;

(4) FIG. 2b is a schematic top view of the cameras of FIG. 2a after mechanical calibration;

(5) FIG. 2c is a schematic diagram that illustrates parameters of embodiments described herein;

(6) FIG. 2d is a schematic perspective view of a camera that may be used in embodiments;

(7) FIG. 3a is a schematic diagram of a camera pattern according to an embodiment;

(8) FIG. 3b is a schematic view of picture positions of the pattern that has been described in connection with FIG. 3a;

(9) FIG. 3c is a schematic diagram of transformed images according to FIG. 3b;

(10) FIG. 4a is a schematic perspective view of nine cameras that are arranged according to an embodiment;

(11) FIG. 4b is a schematic view of example images arranged according to the pattern of FIG. 4a;

(12) FIG. 4c is a schematic perspective view of an example camera array that is arranged according to a 28 pattern;

(13) FIG. 4d is a schematic representation of an example 3D camera pattern;

(14) FIG. 4e is a schematic top view of a part of the pattern of FIG. 4d;

(15) FIG. 5 is a schematic flow chart of method for obtaining calibration data according to an embodiment;

(16) FIG. 6a is a schematic flow chart of another method for obtaining calibration data according to a further embodiment;

(17) FIG. 6b is a schematic diagram of a block of FIG. 6a, that illustrates a linearization strategy that may be implemented by a analyzing unit according to an embodiment;

(18) FIG. 6c is a schematic representation of a graph that represents triple-matching correspondence points according to an embodiment;

(19) FIG. 6d is a graph similar to FIG. 6c in an incomplete state;

(20) FIG. 7 is a schematic block diagram of an apparatus according to an embodiment that comprises a plurality of cameras; and

(21) FIG. 8 is a schematic block diagram of a camera system according to an embodiment that comprises a plurality of cameras and comprises a memory having stored thereon calibration information.

DETAILED DESCRIPTION OF THE INVENTION

(22) Equal or equivalent elements or elements with equal or equivalent functionality are denoted in the following description by equal or equivalent reference numerals even if occurring in different figures.

(23) In the following description, a plurality of details is set forth to provide a more thorough explanation of embodiments of the present invention. However, it will be apparent to those skilled in the art that embodiments of the present invention may be practiced without these specific details. In other instances, well known structures and devices are shown in block diagram form rather than in detail in order to avoid obscuring embodiments of the present invention. In addition, features of the different embodiments described hereinafter may be combined with each other, unless specifically noted otherwise.

(24) In the following, reference is made to camera arrays comprising a plurality of cameras that are arranged at different positions. Such arrays are described herein as being arranged according to a two-dimensional pattern for illustrating the advantages of the embodiments. Although referring to a two-dimensional pattern, other patterns may also be used that comprise cameras being arranged according to a three-dimensional pattern. For example, this may be considered when allowing for divergences of the focal length of a camera. According to other embodiments, the camera pattern may comprise only one dimension, i.e., the cameras are arranged along a single line (or row). Some embodiments are described as one camera being arranged at each camera position such that embodiments that relate to a plurality of partially overlapping images of an object being received from a corresponding plurality of camera positions may be understood as the plurality of images being received from a corresponding plurality of cameras.

(25) Without limitation one camera may capture two or more images at different locations when being moved from a location to another such that images from different camera positions may be captured by a single camera.

(26) Embodiments described herein are explained in terms of stepwise rectifying images. This may relate to rectify or transform images so as to obtain transformed images and to use such transformed images for further steps or for further processing. Without any limitation, such descriptions rate to correction data that is obtained stepwise, i.e., the original images may remain partially or completely unchanged, wherein a transformation of the images is only theoretically performed, e.g., when determining displacement data. Thus, rectifying or transforming the images may be equivalent to determining the amount of the transformation that has to be applied to the images.

(27) Embodiments described herein relate to a displacement of images with respect to each other and/or with respect to a camera pattern. The displacement relates to a transformation according to a first and/or second direction parallel to an object plane but also relates to a rotation of the image in the three-dimensional space. In the following, reference is made to rectifying images, i.e., to calibration of images. Such rectification may comprise a transformation of images. Such transformation may relate to a shifting or a movement of the image along at least one image direction, to a rotation of the image in the image plane and/or to a scaling (skew) of images. Thus and unless stated otherwise, reference made herein that relates to a shift of an image also relates to a rotation and/or a scaling of the image.

(28) FIG. 1 is a schematic block diagram of an apparatus 10 according to an embodiment. The apparatus 10 comprises an input interface 12 for receiving a plurality of partially overlapping images of an object or object area 16. The images 14 are provided from a corresponding plurality of cameras 18a to 18c that project the object 16 by projecting sub areas 22a to 22c of the object 16 wherein each sub area 22a to 22c may correspond to one of the plurality of images 14. An overlap of the sub regions or sub areas 22a to 22c may correspond to an image overlap of the images 14. The plurality of cameras 18a to 18c is arranged according to a pattern along a first direction x and along a second direction y, for example, in an x/y plane. The apparatus 10 comprises an analyzing unit 24 configured for selecting one or more reference points 26 in an overlap area 28 of one of the images 14 which is illustrated, by non-limiting example only, for reference point 26.sub.1 in an image 14a of the plurality of images 14. The image 14a overlaps with another image 14b of the plurality of images 14 in the overlap area 28, i.e., in the overlap area 28, both images 14a and 14b show the same part of the object 16. The reference point 26 contained as reference point 26.sub.1 in the image 14a is also contained as reference point 26.sub.2 in the image 14b. For example, the image 14a is captured by camera 18a and the image 14b is captured by camera 18b. Due to a misalignment between the cameras 18a and 18b, the reference points 26.sub.1 and 26.sub.2 are displaced by a displacement 32 along the x direction and/or y direction. The analyzing unit 24 is configured to determine the displacement information 34 that indicates the displacement 32 along the x direction and the y direction. The misalignment of the images 14a and 14b along the x direction and the y direction is compensated by applying the displacement information 34 which allows obtaining aligned images. Determining the displacement information 34 so as to obtain information on how to transform the images and allowing for low or a minimum of remaining errors for all of the considered images may be a first optimization problem. The analyzing unit 24 may be configured to solve the optimization problem, as will be described later.

(29) Further, the analyzing unit is configured for receiving the images 14 from the plurality of cameras, e.g., without or only coarse prior knowledge with respect to the content thereof and/or overlaps of the images. The analyzing unit may be configured for selecting a corresponding reference point, i.e., image content in the overlap area, e.g., by comparing images. The corresponding reference point or reference region may be a single point or region/object in the captured scene. By identifying similar or identical content, the overlap area may be identified and a set of cameras (pairs, triplets, etc.) may be identified having overlaps in their images at least at a region comprising the reference point 26.sub.1 and/or 26.sub.2. The set of images may thus be configured such that the set of images is a subset of the plurality of images 14, i.e., at least one of the images is not contained in the respective set. In contrast each camera is contained in one or more, e.g., at least two sets.

(30) Based thereon relationships between the cameras may be determined as being described in connection with FIG. 6c. The analyzing unit 24 may be configured for determining offsets or shifts or other deviations of the reference point starting from one image in one (pair of images) tow (triplet of image) or a higher number of other images. The analyzing unit 24 may be configured for determining further reference points for the same set of cameras and/or for other sets of cameras.

(31) Further images of the plurality of images 14 may be misaligned with respect to the image 14a and/or the image 14b. The analyzing unit 24 is configured to determine the displacement, to determine the displacement information 34, respectively, between the plurality of images 14. The analyzing unit 24 may be configured to determine the misalignment or displacement globally, i.e., to select all images of the plurality of images 14 that illustrate the same reference point 26 and to determine the displacement information globally for the selected set of images. Alternatively, the analyzing unit 24 may be configured to align two images such as the images 14a and 14b with respect to each other, i.e., to operate pair-wise. The analyzing unit 24 may be configured to select a set of images that comprise the same reference point 26 and to pair-wise align the images with respect to each other. The analyzing unit 24 may be configured to select more than just one reference point in the overlap area such as, for example, at least 5, 10, or 100. For determining the displacement information along one of the first and second direction, a first image of a selected pair of images may be rotated and scaled so as to be aligned along one image direction, i.e., such as lines or columns of pixels point towards the other camera position. Then, the second image may be transformed along the respective direction so as to align the at least one selected reference point. This may be repeated for the other direction. The machine has knowledge about the position of all cameras. It is even assumed that this information is reliable.

(32) The apparatus 10 comprises a determining unit 36 configured for determining a offset information 38 that relates to principal points 42a to 42c of the plurality of images 14. The offset information may thus be a distance information that describes a distance between principal points and may thus be a relative information relative with respect to the images associated to the principal points. Based on a physical distance between cameras (or camera positions) 18a and 18b or between cameras (or camera positions) 18a and 18c or between cameras (or camera positions) 18b and 18c, a view on the scene or object area, i.e., the object 16 is different from camera to camera. This effect is known as disparity and is used for determining 3D images. For a stereoscopic view, two cameras are needed, for example, cameras 18a and 18b. Through the use of camera 18b and 18c, 18a and 18c, respectively, a second stereoscopic view may be obtained that may allow for an increase in information. When considering now a first stereoscopic view being obtained by using cameras 18a and 18b and a second stereoscopic view being obtained by using cameras 18b and 18c, the stereoscopic information may differ from one another when distances 44a between principal points 42a and 42b and a distance 44b between the focal points 42b and 42c differ from each other. Based thereon disparity estimation and/or depth reconstruction might lead to different results, which may be prevented by the described embodiments.

(33) The determining unit 36 is configured to determine the offset information 38 so as to comprise information related to the distances 44a and 44b. The determining unit 36 is configured to use at least three images, for example, the images of the cameras 18a to 18c, for determining the offset information 38. For determining the distances 44a and/or 4b the reference points may be used. The respective reference point may be the identical in a pair of images and may be identical or different from each other in different sets of images, i.e., in a picture that is part of different pairs of images, different reference points may be used. Determining the offset information 38 so as to obtain information on how to transform the images and allowing for low or a minimum of remaining disparity offset for all of the considered images may be a second optimization problem. The determining unit 36 may be configured to solve the optimization problem, as will be described later.

(34) The apparatus 10 comprises an interface 46 for providing calibration data 48 that is based on the displacement information 34 and based on the offset information 38. The calibration data may allow for rectifying the images 14 including a compensation in differences between distances 44a and 44b between the focal points 42a to 42c. The apparatus 10 may comprise an optional directing unit 52 being configured to process and/or to direct the calibration data 48. For example, the apparatus 10 may comprise an optional memory 54, wherein the directing unit 52 is configured to store the calibration data 38 in the memory 54. The directing unit 52 may be implemented by a central processing unit (CPU), by a microcontroller, by a field programmable gate array (FPGA) or the like.

(35) Based on the displacement information 34, the apparatus 10 has knowledge about the displacement of the images 14 and may compensate for the displacement either by transforming such as shifting the images with respect to each other or by considering the displacement during further operation. This allows determining the differences in the distances 44a and 44b using aligned images such that the distance may sufficiently be calculated along one direction such as x for obtaining sufficient, precise information. An alignment of the images 14 may allow for reconstructing one dimensional dependencies in the camera pattern such as lines, rows or diagonals of the cameras 18a to 18c. The alignment performed by the analyzing unit 24 may, for example, allow for each of the images 14 being in-line or in-row of the camera pattern. This may leave unconsidered a distance between two lines of the pattern, or two rows of the pattern, respectively. However, by determining the distance 44a and the distance 44b, differences in the disparity between different stereoscopic images may be compensated for. Thus, by pre-aligning the images, the compensation for deviations in distances of principal points may be performed along one direction and may, at the same time, provide sufficient information. Thus, disparity estimation and/or depth reconstruction as well as rectification of images may be performed with low computational effort.

(36) FIG. 2a shows a schematic top view of the cameras 18a to 18c before mechanical calibration. Optical axes 54a to 54c of the cameras 18a to 18c differ from each other.

(37) FIG. 2b shows a schematic top view of the cameras 18a to 18c after mechanical calibration. The optical axes 54a to 54c are essentially in parallel but may differ from each other by the displacement described in connection with FIG. 1. In addition, distances b.sub.x12 between a position C.sub.1 of camera 18a and position C.sub.2 of camera 18b may be different when compared to a distance b.sub.x23 between the position C.sub.2 and the position C.sub.3 of camera 18c, wherein the distances b.sub.x12 and b.sub.x23 relate to the x direction. C.sub.1, C.sub.2 and C.sub.3 are positions of the cameras 18a, 18b and 18c in the three-dimensional world.

(38) In other words, FIGS. 2a and 2b show the top view of an array from the top before and after (mechanical) calibration. Before the calibration orientation of cameras C.sub.1, C.sub.2 and C.sub.3 are not consistent and not in parallel. The calibration rotates the cameras such that their optical axes are parallel and perpendicular to the base line of the cameras. Thus, FIG. 2a shows a top view of the camera array before calibration. The optical axes of the cameras are slightly different. FIG. 2b shows a top view of the camera array after calibration. The optical axes are in parallel. Both FIGS. 2a and 2b may show only a top row of the camera array.

(39) FIG. 2c shows a schematic diagram that illustrates parameters of embodiments described herein. The three dimensional world may be described by the x direction, the y direction and the z direction that may be arranged perpendicular to each other. A rotation by an angle around the x direction may be referred to as tilt. A rotation by an angle around the y direction may be referred to as yaw. A rotation by an angle around the z direction may be referred to as roll. The illustrated parameters may be part of a vector that is optimized for obtaining rectified images.

(40) FIG. 2d shows a schematic perspective view of a camera 18 that may be arranged in the array of cameras and may thus be camera 18a, 18b or 18c. The camera 18 comprises and image sensor 58 that comprises a center point 62. Properties of an imaging lens 64 or an array thereof may determine or at least influence a focal length f of camera 18. The focal length f may face an error at. Furthermore, the location of the lens 64 may at least influence the location of the principal point 42 on the image sensor 58 that may be different from the center 62. The principal point 42 may describe a center point of the image that is projected, wherein the point 62 may be a center point of the image sensor 58. A divergence or distance between the projected sub region of the object area and the center of the image sensor 58 may be described by a distance p.sub.x along the x direction and by a distance p.sub.y along the y direction. The parameters p.sub.x and p.sub.y may be assumed to be almost zero for calibrated cameras so as to denote that the optical center of the camera coincides with the center 62 of the imaging sensor.

(41) When referring again to the model of the pinhole camera, the projection matrix P may be formulated according to:
P=K.Math.R.Math.[I|C]Formula 1

(42) K is, for example, a 33 matrix consisting of the intrinsic parameters. These include the focal length, the principal point and the skew factor s.

(43) FIG. 3a shows a schematic diagram of an example of a camera pattern 30 according to which cameras 18a to 18d are arranged, i.e., the pattern 30 is a 22 pattern in the x/y plane. The camera array may be in a state that may be obtained after a mechanical calibration that is explained in connection with FIG. 2b. Camera 18a may be arranged at position C.sub.1, camera 18b may be arranged at position C.sub.2, camera 18c may be arranged at position C.sub.3, and camera 18d may be arranged at position C.sub.4, that are, in an error-free state, arranged according to a rectangle or a square. Other numbers of cameras and/or other patterns are possible.

(44) Parameters that may be evaluated for determining the displacement between images may be a focal length. In FIG. 3a, the focal length a.sub.f1 of camera 18a is different from the focal length a.sub.f3 of camera 18c which results in different sizes 66.sub.1 and 66.sub.3 along the x direction and/or different sizes 68.sub.1 and 68.sub.3 along they direction of pictures 14a and 14c. Furthermore, picture 14b may be rotated by an angle .sub.2. Thus, the displacement information may relate to a transformation such as a shift, a rotation and/or a scaling of the images 14a to 14d along lateral directions x, y and/or z as well as to a rotation of images around at least one axis as described in connection with FIG. 2c.

(45) FIG. 3b shows a schematic view of pictures 14a to 14d of the 22 pattern that has been described in connection with FIG. 3a. On the left hand side, the images 14a to 14d are displaced; in particular, the image 14d does not match the intended pattern. On the right hand side a scenario is illustrated that may be obtained when compensating for the displacement. Arrows 72.sub.1 to 72.sub.3 indicate a direction along which the images 14a to 14c have to be transformed including one or more of a shift, a rotation and a scaling, with respect to image 14d such that the reference points 26.sub.1 to 26.sub.4 correspond to the camera pattern. The arrows 72.sub.1 to 72.sub.3 may also indicate a distance along which the respective image 14a to 14c has to be transformed along the directions x and/or y and may therefore indicate the displacement information. The black parts in the images 14a to 14d schematically illustrate regions from which the image has been transformed away.

(46) The analyzing unit 24 may be configured to determine the displacement information along the x direction and subsequently along the y direction or vice versa. When compared to a determining of the displacement along x direction and y direction simultaneously, this may provide for a high robustness. The apparatus may have knowledge about the error-free pattern 30 and may determine that lines 74a and 74b should be in parallel to each other and that columns 76a and 76b should also be in parallel to each other. The analyzing unit 24 may be configured to determine that this is not true and that the images have to be transformed with respect to each other as illustrated on the right hand side of FIG. 3b where the lines 74a and 74b and the columns 76a and 76b are each in parallel with each other. The determination of the displacement information may also be executed independently from each other, i.e., lines 74a and 74b may be brought into a parallel condition independent of columns 76a and 76b or vice versa. This may refer to a first direction that may be corrected independent from the second direction. The second direction such as the columns 76a and 76b when first having transformed the lines 74a and 74b is executed dependent on the other direction so as to maintain the corrected images.

(47) Thus, the left hand side of FIG. 3b shows an initial state before calibration but after mechanical calibration. The bottom right hand image is clearly not aligned with the other three images. On the right hand side of FIG. 3b rectified images are illustrated. Corresponding pixels are in the same row for horizontal adjacent views and the same column for vertical adjacent views.

(48) In other words, the left hand side of FIG. 3b shows a 22 camera array in a general state. Camera 2 is slightly rotated and camera 3 has a slight deviation in focal length.

(49) FIG. 3c shows a schematic diagram of the transformed images 14a to 14d according to FIG. 3b on the right hand side. Based on different positions C.sub.1 to C.sub.4 of the cameras, the structure that is projected as reference points 26.sub.1 to 26.sub.4 on the images 14a to 14d is arranged on laterally different positions within the images 14a to 14d. On images 14a and 14c, the reference point or reference structure 26.sub.1 may comprise a distance u.sub.1 to a first side of the image, wherein distances indicated with u may be, for example, in parallel with the x direction. In pictures 14b and 14d, reference points 26.sub.2 and 26.sub.4 may face a distance u.sub.2 that is different from u.sub.1 to a comparable side of the image. The same effect may relate to images 14a and 14b with respect to a different perpendicular side. The reference points 26.sub.1 and 26.sub.2 may face a distance v.sub.1 to that side, wherein the distance may be in parallel, for example, along the y direction. The reference points 26.sub.3 and 26.sub.4 of images 14c and 14d may face a different distance v.sub.3 to the comparable side.

(50) An angle .sub.14 indicates an angle by which image 1 (24a) has to be rotated around an anchor point, possibly around a center 27.sub.1 of the image 24a, such that its direction u or alternatively v at the anchor is directed towards the comparable anchor 27.sub.4 in image 4 (24d). An angle .sub.24 indicates an angle by which image 2 (24b) has to be rotated around an anchor point, possibly around a center 27.sub.2 of the image 24b, such that its direction u at the anchor is directed towards the comparable anchor 27.sub.4 in image 4 (24d). Such angles may provide for information indicating the displacement information. may therefore be a parameter fixed for a pair of images or views (p,q) as it only depends on the mechanical center/position of cameras p and q. Centers 24.sub.1 to 24.sub.4 may also indicate the used camera position C.sub.1 to C.sub.4.

(51) FIG. 4a shows a schematic perspective view of nine cameras 18a to 18i that are arranged according to a 33 pattern.

(52) FIG. 4b shows a schematic view of the pattern 40, wherein the images 14a to 14i are arranged according to the pattern 40 of the cameras 18a to 18i in FIG. 4a. Distances b.sub.x and b.sub.y may differ from camera to camera which may be compensated for when determining the offset information.

(53) In other words, FIG. 4b shows a schematic view of a 33 camera array from the back side. Cameras in the array are consecutively numbered starting at the top left corner with camera C.sub.1 going on to the right, to the end of the row, and then continuing on to the next row in the left-most column and so on. The last camera in the bottom right corner is consequently denoted C.sub.MN, M indicating the row an N indicating the column of the pattern.

(54) FIG. 4c shows a schematic perspective view of a camera array 40 that is arranged according to an 28 pattern. Any other patterns comprising an arbitrary number of cameras may be implemented. The concept may be implemented for a number of three or more images. The at least three images may be acquired at different locations with at least one camera. As the rectification is done on an image-basis, also a single camera may be used that is moved between taking the pictures. The distance between the centers of the cameras or the principal points may then relate to the distance when having moved from position one to position two. Accordingly, to be able to take at least three pictures, also two cameras may be used, wherein at least one camera is moveable. Three images may also be acquired by three cameras such that for any number of images a corresponding number of cameras or a lower number may be used.

(55) Although having described patterns that comprise a square or rectangular shape, any other shape may be realized. Any number of cameras such as at least three, five, nine or sixteen may be used. Thus, known approaches are extended towards two dimensional arrays of cameras, for example, such as shown in FIGS. 4a and 4c. Such two dimensional systems may comprise a set of cameras but may also be mounted on a gantry that is able to move the camera to a specific position and take a picture.

(56) Apparatus 10 implements a concept that transforms the images such that the remaining deviation compared to a given model is minimized. This may be achieved by approximating a highly non-linear problem by a series of sub-problems that may be of a linear nature. The overall problem may be approximated and solved using iterative minimization methods minimizing the residual error. Alternatively, the apparatus 10 may also be configured to solve a non-linear optimization.

(57) FIG. 4d shows a schematic representation of a 3D camera pattern 40 that is arranged, by non-limiting example, on a curved surface such as on a sphere. The pattern may also be considered to have lines 74a-d and/or columns 76a, wherein the lines and/or columns may be occupied different from each other. Alternatively or in addition, the lines and columns may be arranged in a non-perpendicular manner with respect to each other, along curved lines and/or columns or according to other rules.

(58) FIG. 4e is a schematic top view of a part of the pattern 40 of FIG. 4d. Objects 77 and 79 may be part of a scene to be captured. The pairs of cameras 18b/18e and 18d/18e of line 74c may each have different direction of view and different distances to the objects 79a and 79b that are seen by both pairs which may lead to additional information needed when compared to a 2D-pattern.

(59) In other words, typically, the precision of mechanical setups is limited. Therefore, the exact properties of one or several cameras need to be reconstructed. Such a reconstruction of camera parameters is also known as calibration. In this procedure, different measurements are made and based on a physical or mathematical model, unknown parameters are found using the analyzing unit and/or the determining unit. Once those unknown parameters are found, one can use these parameters, for example, to define a function that transforms a set of non-rectified images into a set of rectified images. Thus, the obtained calibration data may be applied to non-rectified images which allows for storing or transmitting the non-rectified images even if the displacement information has already been obtained.

(60) The focal length f of a camera may differ from its intended/ideal value in horizontal and/or vertical direction via the error at. The skew factor s may be used to describe the skew of a pixel. In the case of modern imaging sensors, this factor is typically 0, meaning that pixel cells are rectangular. The principal point describes the point of intersection between the camera's optical axis and the sensor. If the sensor is positioned exactly beyond the central point of the optical axis, .sub.x, deviation along the x direction and .sub.y, deviation along the y direction, both are zero. Therefore, the properties of a camera may be formulated as a matrix as:

(61) $\begin{array}{cc}K=\left(\begin{array}{ccc}{f}_x& s& {}_x\\ 0& f_y& {}_y\\ 0& 0& 1\end{array}\right)& \mathrm{Formula}2\end{array}$

(62) By convention it may be formulated that, in a default state, an ideal camera is oriented such that it is strictly pointing down the z axis of a coordinate system such as the one illustrated in FIG. 2d. Image lines may be parallel with the x axis while image columns may be parallel with the y axis, respectively and by non-limiting example only. It should be understood that different coordinate systems may be used that may be transferred from one into another without limitation. In such a case, the rotation matrix may be the identity matrix I. This is not constantly the case and therefore the rotation matrix R is a general rotation matrix that is constructed from three angular components , and , denoting rotations about the primary axes of the coordinate system as described in connection with FIG. 2c. The camera position C may be given as a three dimensional coordinate. The projected points or image points m.sub.i from a set of 3D world points M.sub.1 . . . M.sub.N may then be computed according to the determination rule:

(63) 0$\begin{array}{cc}\left[\begin{array}{ccc}{m}_1^T& \mathrm{.Math.}& m_N^T\end{array}\right]=P\text{|}.Math.\left[\begin{array}{ccc}{M}_1^T& \mathrm{.Math.}& M_N^T\\ 1& \mathrm{.Math.}& 1\end{array}\right]& \mathrm{Formula}3\end{array}$

(64) In this case [M.sub.i.sup.T, 1].sup.T, denotes a homogenous 4D coordinate. The resulting image coordinate m, may then be a three-element vector. This point represents an image coordinate such that the vector may be normalized to its third component. After this normalization, u and v denote the horizontal/vertical position of a point in an image plane which may also be understood as distance (in pixels) from a side of the image.

(65) For each vector m, the following rule may be applied:

(66) $\begin{array}{cc}{m}_i=\left(\begin{array}{c}{u}_i\\ \begin{array}{c}{v}_i\\ 1\end{array}\end{array}\right)& \mathrm{Formula}4\end{array}$

(67) In the context of multi-camera self-calibration, bundle adjust (BA), as described in [2], chapter 18, and which is also known as bundle-adjustment, is a known and proven algorithm. This algorithm uses iterative optimization methods like the Levenberg-Marquardt algorithm to minimize the following problem:

(68) $\begin{array}{cc}\underset{{\hat{P}}^i,{\hat{M}}_j}{\min }\underset{\mathrm{ij}}{.Math.}d\left({\hat{P}}^i.Math.{\hat{M}}_j,x_j^i\right)& \mathrm{Formula}5\end{array}$

(69) wherein d() denotes the geometric distance between an image point x.sub.j.sup.i and a re-projected point {circumflex over (P)}.sup.i.Math.{circumflex over (M)}.sub.j.Math.{circumflex over (P)}.sup.i.Math.{circumflex over (P)}.sup.i denotes the estimated camera matrix for camera i and {circumflex over (M)}.sub.j denotes an estimated world point. Variants of this algorithm are known that are designed to improve efficiency for specific applications and working points. In [3] a method is presented to calibrate a similar camera system consisting of 25 cameras in total. A well-known chart-based calibration method presented in [4] is used and the result is refined using global optimization. Other works as presented in [5], [6] and [7] use additional means like projected patterns or laser pointers to calibrate a set of cameras or entail actively controlling the camera orientation or zoom. A calibration procedure as described in [8] whilst making references to [9] involves the user to provide a calibration object (such as a checkerboard) in front of the multi-camera system. Furthermore the system is limited to two-dimensional (2D) camera setups and the calibration object needs at least to be partially visible in all cameras at once. The properties of the calibration object need to be known to the algorithm. Thus, the calibration object cannot be selected arbitrary. Thus, in known systems, properties of the calibration object are known to the algorithm. I.e., the number of patches on the checkerboard or the fact that all patches are squares. This is directly exploited in the algorithm. The algorithm will fail if the calibration object cannot be detected properly.

(70) Camera systems such as the ones illustrated in FIGS. 4a and 4c and schematically illustrated in FIG. 4b are arranged so as to share one common plane and their optical axis may be roughly, i.e., at most 15%, 10% or 5% deviation is possible, perpendicular to that plane. Additionally, all cameras form a rectangular grid. A grid may be understood as comprising lines 74 and columns 76 that may be, but do not need to be, perpendicular to each other. The apparatus 10 has knowledge about the physical layout of the camera setup, i.e., the analyzing unit 24 and the determining unit 36 have such knowledge. The model or knowledge includes knowledge about a camera position C and each camera's ideal orientation. The ideal orientation is thus a specified condition.

(71) The starting point of the calibration procedure that may be performed with apparatus 10 may be seen on the left hand side of FIG. 3b. It illustrates a subsystem of four cameras that is arranged on a 22 grid and captures a scene from slightly different positions. Corresponding image points, i.e., the reference points 26.sub.1 to 26.sub.4, are connected with lines. A set of corresponding points denotes image points, regions or objects that refer to the same 3D scene point. Thus, even if defining reference points, embodiments are not limited to single points but refer to image regions or objects. In other words those individual image points correspond to a single scene point. This point/object is observed in two or more individual cameras. Corresponding points can be detected by means of feature detection and matching algorithms. Those algorithms assume that the projection of an object into different cameras results in similar image patches. Due to different distortions such as non-exact mechanical alignment, corresponding points typically form a non-regular quadrilateral. This is not very descriptive and establishing a simple relationship between those corresponding points 26 is intuitively difficult or impossible. Therefore, the images are transformed such that the connecting shape is rectangular for all corresponding points in the images. By aligning the reference points 26.sub.1 to 26.sub.4, other selected reference points may also be aligned. An aligned version is illustrated in FIG. 3b on the right hand side. Once this requirement is met, further processing steps like stereo-matching may be executed efficiently.

(72) Based on the pinhole camera model and the projection matrix P, the situation on the right hand side of FIG. 3b may be met if the cameras' focal length is identical and the optical axis of the cameras are parallel and perpendicular to the plane formed by the cameras' centers.

(73) In the remaining part of the document subscripts as in x.sub.p are used to indicate that a vector x denotes properties or information belonging to a specific element such as a camera p. If a variable encodes information belonging to a pair or tuple of cameras we denote this using a two-element subscript such as .sub.pg In this example .sub.pg encodes an angular relationship between to cameras p and q. Similarly, relationship or information comprising three cameras is encoded using a three element subscript such as in A.sub.pqr.

(74) The calibration task can be formulated as measuring the deviation from its ideal state and finding a set of functions H(x.sub.p,C.sub.p,C.sub.q) and H(x.sub.q, C.sub.p, C.sub.q) that, given a pair of images, transforms each image point such that corresponding image points are located in the same image row. For example, matrix H is a 33 homography matrix. Mathematically, this may be expressed as:

(75) $\mathrm{Formula}6$$v\left(H\left(x_p,C_p,C_q\right).Math.P_p.Math.M\right)-v\left(H\left(x_q,C_p,C_q\right).Math.P_q.Math.M\right)=0$$\mathrm{Formula}7$$\underset{\mathrm{left}\mathrm{view}}{\underset{}{v\left(H\text{|}\left(x_p,C_p,C_q\right).Math.m_p\right)}}-\underset{\mathrm{right}\mathrm{view}}{\underset{}{v\left(H\left(x_q,C_p,C_q\right).Math.m_q\right)}}=0$

(76) M denotes a 3D world coordinate, P.sub.p denotes the projection matrix for camera p. Typically, M as well as P are unknown. Assuming that the world point M can be seen in both cameras p and q, this point forms one pair of corresponding image points m.sub.p and m.sub.q. H(x.sub.p,C.sub.p,C.sub.q) is a function of each camera's position C.sub.p and C.sub.g and several intrinsic parameters x.sub.p. The row vector x may be formulated according to the rule:
x:=[.sub.f p.sub.x p.sub.y] Formula 8

(77) H(x.sub.p,C.sub.p,C.sub.q) may be modeled using the pinhole camera model. The outer function v() is used to extract the vertical component of an image point. The equation given above may be implemented for all possible pairs of cameras for a given subset which is relevant for the further processing. Although Formulas 6 and 7 and other descriptions made herein differentiate between left view and right view, this may be changed with respect to each other or manipulated, without any limitation. When referring, for example, to FIG. 3b, x direction and y direction are illustrated as travelling from left to right or from bottom to top and therefore define positive and negative values of Formulas 6 and 7. By redefining the coordinate system such as when letting x travel from right to left, the left view and the right view are interchangeable. It is therefore important to differentiate between the views of a stereo setup in view of the coordinate system. For example, p may be related to the left view and q may be related to the right view or camera. In other words, camera q is to the right of camera p. For this reason, the ordering of the camera positions C is p, q in the left part of Formula 7 as well as in its right part.

(78) The problem discussed above is typically valid for the case of a pinhole camera that does not suffer from side effects like lens-distortion. If lens-distortion is relevant for a specific camera and lens in an implementation Formula 7 may be extended:
v(H(x.sub.p,C.sub.p,C.sub.q).Math.undist(m.sub.p,x.sub.p))v(H(x.sub.q,C.sub.p,C.sub.q).Math.undist(m.sub.p,x.sub.q)) Formula 9

(79) Undist( ) denotes a function that reverts lens-distortion according to some model and parameters contained in x as (Formula 8). Undist( ) may be defined as:

(80) $\begin{array}{cc}\mathrm{undist}\left(m,x\right):=\left(\begin{array}{c}{}_x+L\left(\sqrt{u^2+v^2},\right).Math.\left(u-{}_x\right)\\ {}_y+L\left(\sqrt{u^2+v^2},\right).Math.\left(v-{}_y\right)\\ 1\end{array}\right)& \mathrm{Formula}10\\ L\left(r,\right):=1+k_1.Math.r+k_2.Math.r^2+\mathrm{.Math.}& \mathrm{Formula}11\end{array}$

(81) Function L(r, ) actually models the distortion and is controlled by . Different models may be selected as well as a different length of parameter vector . Here, the discussion is limited to two elements in . In the ongoing part of this text, explicit elements in will be referred to as k such that may be expressed as: =[k.sub.1, k.sub.2, . . . ].

(82) In principle, this problem may be solved using stereo calibration methods on each pair of cameras. In general, such a method will estimate a parameter set x.sub.p, x.sub.q for images p and q, but a different parameter set {tilde over (x)}.sub.p,{tilde over (x)}.sub.r for images p and r, wherein image r is located, for example, below picture p such as image 14c with respect to image 14a. In contrast, it is an object to obtain only one set of parameters x per camera. The desired calibrated situation may also be expressed using the camera matrices P. In the calibrated case, all cameras have identical camera matrices K. All cameras are orientated identical with their optical axis perpendicular to the camera baseline. In this situation, the camera matrix P only depends on the camera position C as described by:
P.sub.p=K.Math.[I|C.sub.p]Formula 12

(83) In the case of independent stereo calibration, the obtained solution is slightly different and doesn't match all criteria: Self-calibration methods can only estimate a relative difference between two cameras. This is, of course, also true for the principal point. In case of a horizontal calibrated stereo rig with corresponding image points on identical image lines, both horizontal principal points .sub.x,1 and .sub.x,2 may be selected and manipulated arbitrarily. Both images still form a stereo system. This fact is, in example, also exploited in stereoscopic productions to manipulate the convergence plane.

(84) In case of complex image processing such as multi-camera disparity estimation, one likes to ensure that corresponding image points across more than two views can be correlated by a simple relationship. Based on the simplified projection matrices given in Formula 9, one can deduce the following formula:

(85) $\begin{array}{cc}\frac{{\mathrm{disp}}_{1,2}}{.Math.C_2-C_1.Math.}-\frac{{\mathrm{disp}}_{1,3}}{.Math.C_3-C_1.Math.}=0& \mathrm{Formula}13\end{array}$

(86) Given a triplet of matching feature points, one can see that stereo disparity directly corresponds to the distance between the cameras' centers. The denominator of Formula 10 may be the distance 44 or b.sub.x, b.sub.y, respectively.

(87) In a real setup, true camera positions will slightly differ from the given values C and known calibration methods are in general not applicable. However, the concept according to embodiments described herein assumes that the positional error is very small and can be ignored which allows for a reduced space of parameters and therefore for a lower complexity of the problem. The concept according to the embodiments described herein may be applied but may slightly increase back-propagation error.

(88) It is therefore one aspect of the embodiments described herein to first align the images and afterwards determine the distance between the principal points by using a different number of images. For determining the displacement information, images may be used pair-wise, wherein the offset information may be determined using three cameras.

(89) The displacement information as well as the offset information may be determined without user-interaction. For each pair of images/triplet of images robust corresponding points, i.e., reference points, regions or objects are determined in an automatic manner, especially without a user providing special calibration patterns such as checkerboards or similar objects. In contrast to existing systems (such as [8]) it is in addition not needed that a single (possibly known) object or point can be observed in all cameras at one time.

(90) Thus, the number of cameras is adapted to the problem to be solved. Furthermore, the underlying non-linear optimization problem may be reformulated. The analyzing unit and/or the determining unit may be configured to solve the non-linear optimization problems. According to an embodiment, the analyzing unit and/or the determining unit may be configured to linearize the non-linear problem for some distinct points and to solve the linearized versions using standard iterative minimization algorithms. Instead of solving one large non-linear problem, such embodiments set up a list of local, piece-wise linear problems that are used to formulate the global problem. This global problem may then be solved iteratively using linear methods. When assuming that the mechanical design of the system is known, including camera position and ideal orientation, the calibration procedure may enforce camera views to obey this model. Additionally, the determination of the displacement information may be split into two parts. By this, highly correlated parameters leading to unstable results can be separated and optimized sequentially. Known approaches such as BA involve estimating 3D world points from image correspondences. This is, in itself, a complex, erroneous procedure. In embodiments, 3D world points are not needed, increasing the stability and efficiency of the approach. By example, BA optimizes camera parameters as well as position of 3D world points. The total number of degrees-of-freedom can be computed as 7N+3P. In this case, N denotes the number of cameras while P denotes the number of 3D world points. According to embodiments, a focus is set on the intrinsic parameters and the camera rotation. This, initially, yields, in an example, number of degrees-of-freedom of 8N. When referring again to Formula 8, the vector x comprises a number of 6 parameters. When formulating a problem based on the 6 parameters that rely on a single camera, the number of cameras N8 values per camera yield in the value above. Thus, embodiments described herein focus on obtaining a result, i.e., the displacement information and the offset information, that makes subsequent image processing steps efficient. In the first step, correspondences between image pairs are sufficient. The second step involves correspondences in three, possibly adjacent, views. This solution may spread an error in the camera array among all cameras, which is a specific property of embodiments described herein. Thus, an apparatus such as apparatus 10 may be configured to impinge on an error-free image with an error so as to compensate for inter-image errors. The concept is designed to fit a set of images to a given model, i.e., the camera pattern. The physical model, as well as the mapping between an image and its position in the array, is specified, by a user.

(91) FIG. 5 is a schematic flow chart of method 500 according to an embodiment that may be used to obtain calibration data. The method 500 comprises a set 510 in which a plurality of partially overlapping images of an object is received from a corresponding plurality of cameras being arranged along a first and a second direction according to a camera pattern. In step 520, a reference point is selected in an overlap area of one of the images, and displacement information along the first and the second direction of the reference point is determined in each of the images such that a misalignment of the plurality of images along the first and the second direction is compensated for by the displacement information so as to obtain aligned images. In step 530, offset information between principal points of the plurality of cameras is determined, using at least three aligned images. In step 540, calibration data is provided based on the displacement information and based on the offset information. The calibration data allows for calibrating the plurality of images so as to comply with the camera pattern when being applied to the images.

(92) FIG. 6a is a schematic flow chart of another method for obtaining calibration data according to a further embodiment. The method may be organized in three sub-methods 602, 603 and 608. Block 602 may be considered to be an initialization. The initialization 602 may comprise steps 612, 614 and 616, wherein in step 612 L images are obtained, for example, from a L=MN camera array with L=MN cameras. In another example the L images are obtained from a sphere or cylinder like structure with L cameras. Two or more of the L cameras may be substituted by a single camera that is moved between different positions and configured to provide more than one picture. For simplicity, the method 600 is first described for the special case of an L=MN camera array with cameras mounted on a rectangular grid.

(93) Sub-method 603 comprises block 604 that is a linear optimization procedure and block block 606 that is performed alternatively or in addition to block 604 and is a non-liner optimization procedure. Only one of the blocks 604 and 606 needs to be executed in order to obtain a set of calibration data 607. Block 608 generates, in a block 612, a set of calibrated images from the calibration data obtained in 607 so as to obtain L rectified images in a block 614 or stores the calibration data in a block 616 for future use. Method 600 allows for use of linear strategies as well as of non-linear strategies and is consistent for planar camera array and non-planar camera array.

(94) In the following reference will be made to a use of a linear optimization, for example, in block 604 using steps 612,614 and 616 of method 600. In the MN camera array (M1)N+(M1)N, individual stereo pairs can be formed using directly adjacent camera positions. When referring, for example, to FIG. 4b, such pairs may be C.sub.1/C.sub.2, C.sub.1/C.sub.4, C.sub.2/C.sub.3, C.sub.2/C.sub.5, C.sub.3/C.sub.6, C.sub.4/C.sub.5, C.sub.4/C.sub.7, C.sub.5/C.sub.6, C.sub.5/C.sub.8, C.sub.6/C.sub.9, C.sub.7/C.sub.8, and C.sub.8/C.sub.9. I.e., the analyzing unit may be configured to determine the displacement information pair-wise for a pair of the plurality of images, e.g., direct neighbors. Alternatively, any other pairs of images may be used such as C.sub.1/C.sub.5, C.sub.1/C.sub.9, C.sub.2/C.sub.6, or the like. The apparatus is configured to select a sufficient number of pairs that allows determining a needed number of parameters. Such a number of parameters may be, by non-limiting example only 6 as described above. Such a number is needed for each camera such as 9 such that in total 54 parameters are needed. Each camera is advantageously part of a number of different pairs of images that corresponds to the number of dimensions along which the camera pattern is arranged. A single line is considered as one-dimensional, camera positions (centers) differing in two directions are considered as two-dimensional and camera positions (centers) differing in three directions are considered as three-dimensional. For the present example, this is true for each camera being part of at least two pairs which is fulfilled for the list given above, wherein a number of 8 pairs (each of the 9 cameras may for a pair with 8 other cameras and has to be a part of two pairs equals in 28/2), wherein additional information may be obtained by additional pairs.

(95) Although description was made in connection with a number of six parameters that are to be determined in order to calibrate images, also a different number of parameters or different parameters may be used, e.g., in case one or more of the above mentioned is considered to be within a tolerance range, calibration of that parameter may be skipped. Alternatively or in addition other parameters may be considered such as a distortion of lenses used in the cameras which may lead to low picture quality. The apparatus 10 may be configured to calibrate for the distortion, e.g., during determination of the displacement information. Different reference points in the image may allow for compensating the distortion of the lens.

(96) In this way, each view is at least involved in two individual stereo pairs. The set of stereo pairs is further referenced as the set . The set may in example comprise pairs (p,q), (p,r), (q,r) and others. In general, the method is not limited to directly adjacent cameras. Each possible pair of views with overlapping image areas that allow for a common reference point may be formed. In step 614 interest points or reference are detected on each of the images and these interest points are matched on the mentioned stereo pairs in step 616. This may be done using any arbitrary feature detection and matching algorithm like SIFT, SURF or BRIEF. As a result, sets of corresponding, matched image coordinates

(97) $m_{p,q}=\left\{\underset{\underset{m_{p,q}^{\left(p\right)}}{}}{u_p,v_p},\underset{\underset{m_{p,q}^{\left(q\right)}}{}}{u_q,v_q}\right\}$
between two images p and q is obtained.

(98) u.sub.p and v.sub.p denote vectors containing l horizontal/vertical positions of feature matches between view p and view q respectively. In the example of FIG. 3b, / would have dimension 1. If only one set of feature points belonging to a set of cameras is needed, this is denoted by an additional superscript in round braces. I.e., m.sub.p,q.sup.(p) denotes all feature points in image p obtained from the pair (p,q). The third (homogenous) component is neglected here but is considered in further steps. In such a case, the third homogenous component may be set to a value of 1.

(99) In block 604 disparities along a direction, e.g., vertical disparities, for all stereo pairs contained in are reduced or minimized. For example, this may be done along the vertical direction such as the y direction. Formally, for one pair (p,q) this can be written as:
0=v(H(x.sub.p,C.sub.p,C.sub.q).Math.m.sub.p,q.sup.(p))v(H(x|.sub.q,C.sub.p,C.sub.q).Math.m.sub.p,q.sup.(q)) Formula 14

(100) As before, H(x.sub.p,C.sub.p,C.sub.q) denotes a function returning a 33 homography matrix for view p. The argument x.sub.p of this function is a vector of length k. Function v(x) extracts the vertical component of a feature point coordinate:

(101) $v\left(x\right)=\frac{x\left(2,i\right)}{x\left(3,i\right)}il$
where x is a 3l matrix. Consequentially, v(x) returns a vector of length l. In the present consideration x is a variable unrelated to other variables named x herein and shall simply denote an argument of function v. The overall minimization task can now be formulated as:

(102) $\mathrm{Formulas}15\&16$$\underset{x_1,x_2{x}_3,\mathrm{.Math.},x_N}{\arg \min }\underset{\left(p,q\right)}{.Math.}.Math.v\left(H\left(x_p,C_p,C_q\right).Math.m_{p,q}^{\left(p\right)}\right)-v\left(H\left(x_q,C_p,C_q\right).Math.m_{p,q}^{\left(q\right)}\right).Math.$$\mathrm{with}.Math.x.Math.=\underset{l}{.Math.}{x}_l^2$

(103) The result thereof may allow the analyzing unit for obtaining a solution for all images p, q, r and s forming pairs, the pairs being comprised of the set , i.e., a common solution for all x may be obtained.

(104) In Formula 15 the square norm is selected in order to model the error between two views. Other choices are possible. The notation .sub.(p,hd q)arg indicates that the tuple (p,q) is one tuple exemplarily selected from the set but also that the summation is performed for all tuples contained in . H(x.sub.p,C.sub.p,C.sub.q) is defined as a product of three functions R.sub.0, K and R.sub.i:
H(x.sub.p,C.sub.p,C.sub.q)=R.sub.0.Math.K.Math.R.sub.i=R.sub.0.Math.{tilde over (H)}(x.sub.p)
with {tilde over (H)}(x.sub.p)=K.Math.R.sub.i Formula 17

(105) This formulation can be interpreted as follows: The right-most rotation matrix R.sub.i corrects a camera's orientation such that it corresponds to its ideal orientation as given by the ideal camera setup. The center matrix K corrects parameters like focal length and principal point. The left-most rotation R.sub.0 rotates a camera p such that it forms a stereo system with a camera q. Only this matrix is individual for each pair of views.

(106) K may model the standard camera matrix as given above. R.sub.0 and R.sub.i denote the outer and inner rotation matrix. More precisely, R.sub.0 is computed from the relative position and orientation of two cameras p and q. Because each camera position is known, R.sub.0 is known. In some arrangements, all these cameras share one common plane, such that the outer rotation R.sub.0 can be modeled using a single rotation around the optical axis. This may be referred to as angle that is explained in connection with FIG. 3c. As illustrated in FIG. 3a, a 22 camera array in a general state may comprise camera 18b that is slightly rotated by angle .sub.2, wherein camera 18c has a slight deviation in focal length. For the pair C.sub.1, C.sub.3, R.sub.0,13 needs to rotate C.sub.1 and C.sub.3 by /2 to form a rectified system assuming that no further distortion occurs. The angle may be computed with respect to left/right viewpoint. In the example of FIG. 3a, C.sub.1 is exactly above C.sub.3. In order to be rectified to camera 18c and being the left view in this setup, C.sub.1 may be rotated by 90. In contrast, C.sub.3 forms the right view and is consequently also rotated by 90. This is also expressed in the argument ordering of H. The second argument denotes the left view while the third argument denotes the right view.

(107) Alternatively, Formula 17 may also be defined as:
H(x.sub.p,C.sub.p,C.sub.q)=R.sub.0.Math.R.sub.i.Math.K=R.sub.0.Math.{tilde over (H)}(x.sub.p)
with {tilde over (H)}(x.sub.p)=R.sub.i.Math.K Formula 17b

(108) In the more general case when the cameras do not share a common plane, the apparatus, in particular the analyzing unit is configured to determine R.sub.0 from the position C.sub.p and C.sub.q of two cameras p and q. R.sub.0 is a 33 matrix with elements as listed below:

(109) TABLE-US-00001 Formula 18 R.sub.0(1,1) c.sub.p.sub.1 c.sub.q.sub.1 R.sub.0(1,2) (c.sub.p.sub.2 c.sub.q.sub.2) {square root over ((c.sub.p.sub.1c.sub.q.sub.1+1)(1+c.sub.p.sub.1c.sub.q.sub.1))} R.sub.0(1,3) (c.sub.p.sub.3 c.sub.q.sub.3) {square root over ((c.sub.p.sub.1c.sub.q.sub.1+1)(1+c.sub.p.sub.1c.sub.q.sub.1))} R.sub.0(2,1) (c.sub.p.sub.2 c.sub.q.sub.2) {square root over ((c.sub.p.sub.1c.sub.q.sub.1+1)(1+c.sub.p.sub.1c.sub.q.sub.1))} R.sub.0(2,2) (1 c.sub.p.sub.1 + c.sub.q.sub.1) c.sub.p.sub.3.sup.2 + 2c.sub.q.sub.3 (1 + c.sub.p.sub.1 c.sub.q.sub.1) c.sub.p.sub.3 + (1 c.sub.p.sub.1 + c.sub.q.sub.1) c.sub.q.sub.3.sup.2 + c.sub.p.sub.1 c.sub.q.sub.1 R.sub.0(2,3) (c.sub.p.sub.3 c.sub.q.sub.3) (c.sub.p.sub.2 c.sub.q.sub.2) (1 + c.sub.p.sub.1 c.sub.q.sub.1) R.sub.0(3,1) (c.sub.p.sub.3 c.sub.q.sub.3) {square root over ((c.sub.p.sub.1c.sub.q.sub.1+1)(1+c.sub.p.sub.1c.sub.q.sub.1))} R.sub.0(3,2) (c.sub.p.sub.3 c.sub.q.sub.3) (c.sub.p.sub.2 c.sub.q.sub.2) (1 + c.sub.p.sub.1 c.sub.q.sub.1) R.sub.0(3,3) (1 c.sub.p.sub.1 + c.sub.q.sub.1) c.sub.p.sub.2.sup.2 + 2c.sub.q.sub.2 (1 + c.sub.p.sub.1 c.sub.q.sub.1) c.sub.p.sub.2 + (1 c.sub.p.sub.1 + c.sub.q.sub.1) c.sub.q.sub.2.sup.2 + c.sub.p.sub.1 c.sub.q.sub.1

(110) The parameter vector x.sub.p contains all unknown parameters for a camera p and is defined according to Formula 8. Based on this definition H(x.sub.p,C.sub.p,C.sub.q) may now be completely defined as:

(111) $\mathrm{Formulas}19\&20$$H\left(x_p,C_p,C_q\right)=R_o\left(0,0,{}_{p,q}\right).Math.K\left(a_f,{}_x,{}_y\right).Math.R_i\left(,,\right)$$\mathrm{with}{}_p{,}_q=a\tan \frac{C_{p,2}-C_{q,2}}{C_{p,1}-C_{q,1}}$

(112) The integer number subscript such as in C.sub.p,2 denotes the second element in the vector C.sub.p. Please note that in Formula 19 subscripts in the elements of x.sub.p such as have been neglected. It should however be clear that in any formula comprising elements of x, those elements need to be interpreted with respect to specific camera p. In Formula 19 the ideal orientation of all cameras is identical and perpendicular to the baseline. If this is not the case, H can be extended by an additional rotation matrix R(,, ) describing the specific orientation with respect to the coordinate frame:
H(x.sub.p,C.sub.p,C.sub.q,,,)R.sub.o(0,0,.sub.p,q).Math.R(,,).sup.1.Math.K(.sub.fp.sub.x,p.sub.y).Math.R.sub.i(,,) Formula 21

(113) In the ongoing description the case expressed in Formula 14 is considered. If needed, calculations can be redone including R(,, ).

(114) With respect to the alternative definition of Formula 17 as given in Formula 17b, Formulae 19, 20 and 21 can be adapted by switching the order of the two rightmost matrices R.sub.i and K.

(115) According to embodiments, the apparatus is configured to consider the lens-distortion. The functionality of the apparatus may be expressed by including Formula 10 in Formula 11 and Formula 12 as to obtain an undistorted version of reference points m.

(116) The term of Formula 14 forms a non-linear system. This formula can be solved using iterative least-square minimization techniques like Levenberg-Marquardt algorithm or comparable methods. However, this solution is inefficient. This non-linear minimization is depicted in block 606 of FIG. 6a.

(117) The problem in Formula 12 may be reformulated in order to find the values in H efficiently: Therefore, it may be assumed that all variables in x are small. This corresponds to the block 604 in FIG. 6a. This block is depicted in more detail in FIG. 6b that illustrates a linearization strategy that may be implemented by the analyzing unit.

(118) With the complete definition of H, Formula 12 may be evaluated for one pair of cameras p, q and for one pair of point correspondences.

(119) In the next step such a formulation may be expanded, for example, using first order Taylor expansion of several variables. This expansion may be defined as:
(x,a):=T(x,a)=T F.sub.x,a(1,0)=F.sub.x,a(0)+F.sub.x,a(0)
F.sub.x,a:.fwdarw.:=t.fwdarw.(a+t.Math.(xa)) Formula 22 & 23

(120) In Formulae 21 and 22 F.sub.x,a is a function of t that evaluates the function f(x) at the point a+t.Math.(xa). f(x) is the function to approximate at some point a. Parameters to the function f(x) are contained in the parameter vector x. t is a scalar value. a is a vector with identical size as x. First order Taylor approximation T of a function f(x) at some point a may be expressed as Taylor expansion of a scalar function F.sub.x,a(t). F.sub.x,a is expanded at point t.sub.0=0 by computing the function value of F.sub.x,a with t.sub.0=0 and the value of the first order derivative

(121) 0$F_{x,a}^{}=F_{x,a}\frac{d}{\mathrm{dt}}$
also at t.sub.0=0. Evaluating the resulting term at t=1 yields the first order Taylor approximation of function f(x) at point a. The expansion may exemplary be computed for a single pair of images p and q and a single pair of reference points. Then, Formula 16 (here also including lens-distortion as given in Formula 9) may be simplified as written in Formula 24.
v(H(x.sub.p,C.sub.p,C.sub.q).Math.undist([u.sub.p,v.sub.p,1].sup.Tx.sub.p))v(H(x.sub.q,C.sub.p,C.sub.q).Math.undist([u.sub.g,v.sub.q,1].sup.T,x.sub.q)) Formula 24

(122) The apparatus may be configured to determine the Taylor expansion using Formula 22 for Formula 24 for all variables contained in x.sub.p and x.sub.q forming a parameter vector like =[x.sub.p, x.sub.q]. is argument to Formula 22 as well as an expansion point a=0. Without limitation, other expansion points may be selected.

(123) This yields an approximation for the point x.sub.p=0 and x.sub.q=0. The resulting equation can be differentiated with respect to every unknown variable in x.sub.p and x.sub.q. As a result, one obtains the Jacobian matrix of this system. Each column in the Jacobian matrix contains an approximation for each parameter in the system. These approximations may also be expressed as:

(124) TABLE-US-00002 Formula 25 .sub.p v.sub.pu.sub.p sin(.sub.pq) cos(.sub.pq) v.sub.p.sup.2 cos(.sub.pq) .sub.q v.sub.qu.sub.q sin(.sub.pq) + cos(.sub.pq) v.sub.q.sup.2 + cos(.sub.pq) .sub.p sin(.sub.pq) u.sub.p.sup.2 + v.sub.pu.sub.p cos(.sub.pq) + sin(.sub.pq) .sub.q sin(.sub.pq) u.sub.q.sup.2 v.sub.qu.sub.q cos(.sub.pq) sin(.sub.pq) .sub.p u.sub.p cos(.sub.pq) v.sub.p sin(.sub.pq) .sub.q u.sub.q cos(.sub.pq) + v.sub.q sin(.sub.pq) a.sub.fp sin(.sub.pq) u.sub.p + cos(.sub.pq) v.sub.p a.sub.fq sin(.sub.pq) u.sub.q cos(.sub.pq) v.sub.q {open oversize brace} .sub.xp sin(.sub.pq) {close oversize brace} {open oversize brace} .sub.xq sin(.sub.pq) {close oversize brace} .sub.yp cos(.sub.pq) .sub.yq cos(.sub.pq) k.sub.p,1 (sin(.sub.pq) u.sub.p + cos(.sub.pq) v.sub.p) {square root over (u.sub.p.sup.2+v.sub.p.sup.2)} k.sub.q,1 (sin(.sub.pq) u.sub.q + cos(.sub.pq) v.sub.q) {square root over (u.sub.q.sup.2+v.sub.q.sup.2)} k.sub.p,2 (u.sub.p.sup.2 + v.sub.p.sup.2) (sin(.sub.pq) u.sub.p + cos(pq) v.sub.p) k.sub.q,2 (u.sub.q.sup.2 + v.sub.q.sup.2) (sin(.sub.pq) u.sub.q + cos(pq) v.sub.q)

(125) In this case, k.sub.g, h denotes the parameters to model lens-distortion of view g being either q or p according to Formula 10 and 11 and the definition of vector .

(126) The remaining constant part may be formulated as:
b.sub.p,q=(v.sub.pv.sub.q)cos(.sub.pq))+sin(.sub.pq)(u.sub.pu.sub.q) Formulas 26

(127) All elements in J and also the constant part b.sub.p,q can now be evaluated for point correspondences. The resulting system can be re-written as linear system according to:

(128) $\begin{array}{cc}{J}_{p,q}.Math.\left[\begin{array}{c}{\tilde{x}}_p^T\\ {\tilde{x}}_q^T\end{array}\right]=-b_{p,q}\left[J_{p,q}^{\left(p\right)}\text{|}{J}_{p,q}^{\left(q\right)}\right].Math.\left[\begin{array}{c}{\tilde{x}}_p^T\\ {\tilde{x}}_q^T\end{array}\right]=-b_{p,q}& \mathrm{Formulas}27\&28\end{array}$

(129) In Formulas 27 & 28, J.sub.p,q is a lx(2*m) matrix where l denotes the number of point correspondences and m denoting the number of variables in x. b is a column vector with length l.

(130) As the Taylor expansion only approximates the function value at one point, the true parameter vector x.sub.p needs to be replaced by an approximated value {tilde over (x)}.sub.p. In Formula 27, J.sub.p,q and b.sub.p,q denote the Jacobian matrix and constant part of two views (p, q) evaluated for all point correspondences. As before, J.sub.p,q.sup.(p) in Formula 28 denotes the columns of J.sub.p,q belonging to unknowns of camera p.

(131) For the set of all stereo-pairs , the overall minimization task may be formulated by the analyzing unit 24 as follows: Each pair (p, q) in forms one line in the global constraint matrix A that is generated in a step 621 of method 600. For a 22 camera array with four individual stereo pairs, the problem can be written as:

(132) $\begin{array}{cc}\underset{\underset{A}{}}{\left[\begin{array}{cccc}{J}_{12}^{\left(1\right)}& J_{12}^{\left(2\right)}& 0& 0\\ J_{13}^{\left(1\right)}& 0& J_{13}^{\left(3\right)}& 0\\ 0& J_{24}^{\left(2\right)}& 0& J_{24}^{\left(4\right)}\\ 0& 0& J_{34}^{\left(3\right)}& J_{34}^{\left(4\right)}\end{array}\right]}.Math.\underset{\underset{}{}}{\left[\begin{array}{c}{\tilde{x}}_1^T\\ {\tilde{x}}_2^T\\ {\tilde{x}}_3^T\\ {\tilde{x}}_4^T\end{array}\right]}=\underset{\underset{b}{}}{-\left[\begin{array}{c}{b}_{12}\\ b_{13}\\ b_{24}\\ b_{34}\end{array}\right]}A.Math.=b& \mathrm{Formulas}29\&30\end{array}$

(133) The number of feature matches in each stereo pair may be greater than the number of unknown variables in x, such that the overall system is overdetermined. To solve the linearized system and thus finding a set of parameters approximating the real condition of the plurality of cameras as given by Formula 15, the system can be solved for by computing the Pseudo-inverse of A. In total, the solution for can be obtained as:
=(A.sup.T.Math.A).sup.1.Math.A.sup.T.Math.b Formula 31

(134) Thus, the analyzing unit may be configured to minimize the error based on the determination rule that corresponds to Formula 31. The analyzing unit may be configured for determining the displacement information using a set of parameters, that indicates a real condition of the plurality of cameras. The parameters may comprise a non-linear relationship with respect to each other. The analyzing unit may be configured to determine a linearized version of the parameters in the vector and may be configured to determine the displacement information by minimizing an error of the linearized version with respect to a desired condition of the plurality of cameras. This is indicated as step 622, i.e., the system is solved for . Alternatively, the analyzing unit may solve the non-linear problem. The at least two elements in x show the approximation for .sub.x and .sub.y. As both do not depend on image coordinates and only depend on which is constant, the linearization does not provide valuable information of these parameters. For this reason, both parameters .sub.x and .sub.y are excluded in this step. This works by dropping the value in {tilde over (x)}.sub.p and {tilde over (x)}.sub.q as well as the appropriate columns in J.sub.p,q. As a consequence, deviations in a camera's principal point will be approximated by a small additional rotation around the y axis and x axis respectively. I.e., the calibration data may be based on angles that describe a rotation of the cameras, to a focal length of the camera and to a principle point of the cameras, wherein the calibration data may be in absence to a position of the cameras of the plurality of cameras, i.e., does possibly not contain information indicating the camera positions. This may be possible as the camera position is considered as known variable in the system.

(135) The elements in now contain an approximated solution for the overall non-linear problem. At this point, the overall problem can now be solved using an iterative optimization algorithm like gradient descent. In every iteration a small portion of .Math. is added to the previous x.sub.p.sup.(t-1) forming a new x.sub.p.sup.(t), i.e., the solution vector is updated in a step 623. The current x.sub.p.sup.(t) is then used to generate an intermediate mapping homography {tilde over (H)} for each camera. This intermediate homography is used to update all feature sets (p, q). Those updated feature sets {tilde over (m)}.sub.p,q form new initial feature sets in the next iteration, i.e., the feature points are transformed in a step 624. Ideally, x.sub.p.sup.(t) iteratively approaches the desired solution. As soon as is smaller than threshold {tilde over ()}.sub.0 or the remaining error cannot be reduced anymore, the algorithm stops. I.e., the analyzing unit may be configured to iteratively minimize the error of the linearized version. This is indicated in step 625 checking, if congruence is reached. This may also be expressed as:
x.sub.p.sup.(t)=.Math.+x.sub.p.sup.(t-1)
{tilde over (m)}.sub.p,q.sup.(p)={tilde over (H)}.sub.p.Math.m.sub.p,q.sup.(p)=K(a.sub.f,p,p.sub.x,p,p.sub.y,p).Math.R.sub.i(.sub.p,.sub.p,.sub.p).Math.m.sub.p,q.sup.(p)
and {tilde over (m)}.sub.p,q.sup.(q)={tilde over (H)}.sub.p.Math.m.sub.p,q.sup.(q)=K(a.sub.f,q,q.sub.x,q,q.sub.y,q).Math.R.sub.i(.sub.q,.sub.q,.sub.q).Math.m.sub.p,q.sup.(q) Formulas 32 & 33(a)

(136) Once this iterative minimization algorithm has converged, the second part of this linearized calibration procedure can be started, i.e., block 627 may be started, e.g., by the determining unit. At the end of block 625 a result according to FIG. 3c may be obtained, i.e., after the first rectification step, images may be pair-wise rectified. Corresponding pixels are shifted horizontally only for views in the same row and shifted vertically in the same column respectively. Both, the transformation of the images in step 622 by the analyzing unit and the estimation of the principal points in step 627 by the determining unit may be executed by determining a solution for a minimization problem that may be linear or non-linear. I.E., four problems may be formulated, two for solving the minimization criteria with respect to the transformation that may be referred to a first (vertical) disparity and two for solving the second (horizontal) disparity. The problems may be re-formulated for a 2D and a 3D-pattern of cameras.

(137) The final state after the converge criteria is this illustrated FIG. 3c for a 22 array. The position of the marked objects in C.sub.1 is denoted by u.sub.1 and v.sub.1. In C.sub.2, the object has slightly moved to the left but the vertical coordinate is still v.sub.1. A similar condition holds for the vertical pair C.sub.1, C.sub.3: the object is shifted vertically but not horizontally.

(138) As formally expressed in Formula 13, corresponding disparity values in three cameras may depend on the array geometry only. Up to this point, this has not been taken into account in the method 604. Consequentially, it is possible that Formula 13 is not met. Simplified, a distance between columns in pairs may differ or vary. This condition can be re-written in order to formulate a condition similar to Formula 15. For a triplet of three cameras this may be formulated as:

(139) $\mathrm{Formula}34\&35$$\left(u\left(R_o\left(0,0,{,}_{p,q}\right).Math.{\tilde{m}}_q\right)-u\left(R_o\left(0,0,{,}_{p,q}\right).Math.{\tilde{m}}_q\right)\right)\frac{1}{d\left(C_p-C_q\right)}-\left(u\left(R_o\left(0,0,{,}_{p,q}\right).Math.{\tilde{m}}_p\right)-u\left(R_o\left(0,0,{,}_{p,r}\right).Math.{\tilde{m}}_r\right)\right)\frac{1}{d\left(C_p-C_r\right)}=0$$\mathrm{with}$$\tilde{m}={\left[\begin{array}{ccc}\tilde{u}& \tilde{v}& 1\end{array}\right]}^T=\tilde{H}\left(x\right).Math.m$

(140) H denotes the mapping homography that has been obtained in the last iteration of the previous steps, i.e., block 625. H() may be defined as given in Formula 17 or 17b with respect to a parameter vector x. The function u() extracts the horizontal component of image point. d(C.sub.pC.sub.q) denotes the Euclidian distance between two camera C.sub.p and C.sub.q. Using {tilde over (m)} instead of m, it may be assumed that optical axes are parallel and that all cameras have identical focal lengths. The remaining error can be modeled by a shift in the cameras' principal point. Formula 34 can now be used to define a second minimization problem which is subject to be minimized and formulated as follows:

(141) $\mathrm{Formula}36\underset{x_1,x_2,x_3{\mathrm{.Math.x}}_N}{\arg \min }\underset{\left(p,q,r\right)}{.Math.}.Math.\left(u\left(H\left(x_p,C_p,C_q\right).Math.m_{p,q,r}^{\left(p\right)}\right)-u\left(H\left(x_q,C_p,C_q\right).Math.m_{p,q,r}^{\left(q\right)}\right)\right)\frac{1}{d\left(C_p-C_q\right)}-\left(u\left(H\left(x_p,C_p,C_r\right).Math.m_{p,q,r}^{\left(p\right)}\right)-u\left(H\left(x_r,C_p,C_r\right).Math.m_{p,q,r}^{\left(r\right)}\right)\right)\frac{1}{d\left(C_p-C_r\right)}.Math.$

(142) Formula 36 refers to the general case when the cameras are not in a calibrated state. The analyzing unit may be configured to solve this problem so as to determine the displacement information. Alternatively or in addition, the analyzing unit may be configured to solve a linearized version thereof that may be expressed by

(143) $\mathrm{Formula}37\underset{x_1,x_2,x_3{\mathrm{.Math.x}}_N}{\arg \min }\underset{\left(p,q,r\right)}{.Math.}.Math.\left(u\left(\hat{H}\left({\hat{x}}_p,C_p,C_q\right).Math.{\tilde{m}}_{p,q,r}^{\left(p\right)}\right)-u\left(\tilde{H}\left({\hat{x}}_q,C_p,C_q\right).Math.{\tilde{m}}_{p,q,r}^{\left(q\right)}\right)\right)\frac{1}{d\left(C_p-C_q\right)}-\left(u\left(\hat{H}\left({\hat{x}}_p,C_p,C_r\right).Math.{\tilde{m}}_{p,q,r}^{\left(p\right)}\right)-u\left(\hat{H}\left({\hat{x}}_r,C_p,C_r\right).Math.{\tilde{m}}_{p,q,r}^{\left(r\right)}\right)\right)\frac{1}{d\left(C_p-C_r\right)}.Math.$

(144) Function (x.sub.p,C.sub.p,C.sub.q) may be defined as:
{tilde over (H)}({circumflex over (x)}.sub.p,C.sub.p,C.sub.q)R.sub.o(0,0,.sub.p,q).Math.K.sub.i(0,{circumflex over ()}.sub.x,p,{circumflex over ()}.sub.y,p)
{circumflex over (x)}[{circumflex over ()}.sub.x,{circumflex over ()}.sub.y] Formula 38

(145) Function as given in Formula 38 models a transformation that performs a shift in a cameras' principal point and as before rotates two images such that they may form a stereo pair. Thus, by comparing two individual stereo pairs minimizing the remaining error as given in Formulas 36 and 37 by finding optimum values for {circumflex over ()} may be performed.

(146) As an additional condition, Formulas 36 and 37 may be minimized with respect to the minimization criteria given in Formula 15. Being consistent to the definition of sets of feature point pairs m.sub.p,q given before, m.sub.p,q,r defines a set of triple matching feature points. All triplets (p, q, r) of cameras sharing overlapping image areas are contained in the set .

(147) Formulas 36 and 37 may be evaluated for various camera configurations with the requirements as given above. Depending on the camera configuration and the resulting image overlap the set of equations that is obtained will have a different shape. It is possible that the resulting system can be solved exactly with linear methods, and is over or under determined.

(148) In matrix notation, problem 37 may be written as follows: For one triplet of cameras (p,q,r) this may be formulated as:

(149) $\begin{array}{c}\mathrm{Formula}39\left[\begin{array}{ccc}{A}_{\mathrm{pqr}}^{\left(p\right)}& A_{\mathrm{pqr}}^{\left(q\right)}& A_{\mathrm{pqr}}^{\left(r\right)}\end{array}\right].Math.{\left[\begin{array}{ccc}{\hat{x}}_p& {\hat{x}}_q& {\hat{x}}_r\end{array}\right]}^T+b_{\mathrm{pqr}}=0A.Math.{\left[\begin{array}{ccc}{\hat{x}}_p& {\hat{x}}_q& {\hat{x}}_r\end{array}\right]}^T+b_{\mathrm{pqr}}=0\mathrm{Formula}40\\ \mathrm{wherein}\\ A_{\mathrm{pqr}}^{\left(p\right)}=\left[\begin{array}{cc}\frac{-\cos \left({}_{\mathrm{pr}}\right).Math.d_{\mathrm{pq}}+\cos \left({}_{\mathrm{pq}}\right).Math.d_{\mathrm{pr}}}{d_{\mathrm{pq}}.Math.d_{\mathrm{pr}}}& \frac{\sin \left({}_{\mathrm{pr}}\right).Math.d_{\mathrm{pq}}-\sin \left({}_{\mathrm{pq}}\right).Math.d_{\mathrm{pr}}}{d_{\mathrm{pq}}.Math.d_{\mathrm{pr}}}\\ \sin \left({}_{\mathrm{pq}}\right)& \cos \left({}_{\mathrm{pq}}\right)\\ \sin \left({}_{\mathrm{pr}}\right)& \sin \left({}_{\mathrm{pr}}\right)\\ 0& 0\end{array}\right]\mathrm{Formula}41A_{\mathrm{pqr}}^{\left(q\right)}=\left[\begin{array}{cc}\begin{array}{c}\frac{\cos \left({}_{\mathrm{pq}}\right)}{d_{\mathrm{pq}}}\\ -\sin \left({}_{\mathrm{pq}}\right)\\ 0\\ \sin \left({}_{\mathrm{qr}}\right)\end{array}& \begin{array}{c}\frac{\sin \left({}_{\mathrm{pq}}\right)}{d_{\mathrm{pq}}}\\ -\cos \left({}_{\mathrm{pq}}\right)\\ 0\\ \cos \left({}_{\mathrm{qr}}\right)\end{array}\end{array}\right]A_{\mathrm{pqr}}^{\left(r\right)}=\left[\begin{array}{cc}\begin{array}{c}\frac{\cos \left({}_{\mathrm{pr}}\right)}{d_{\mathrm{pr}}}\\ 0\\ -\sin \left({}_{\mathrm{pr}}\right)\\ -\sin \left({}_{\mathrm{qr}}\right)\end{array}& \begin{array}{c}-\frac{\sin \left({}_{\mathrm{pq}}\right)}{d_{\mathrm{pq}}}\\ 0\\ -\cos \left({}_{\mathrm{pr}}\right)\\ -\cos \left({}_{\mathrm{qr}}\right)\end{array}\end{array}\right]b_{\mathrm{pqr}}=\left[\begin{array}{c}\frac{-{\tilde{u}}_p+\widetilde{u_q}}{d_{\mathrm{pq}}}+\frac{{\tilde{v}}_p-{\tilde{v}}_r}{d_{\mathrm{pr}}}\\ 0\\ 0\\ 0\end{array}\right]\end{array}$