Frame synchronization in a multi-camera system

[0002] The present invention relates generally to the field of camera systems, and more particularly, is directed to a method for frame synchronization in a multi-camera system.

[0003] In recent years, multi-camera systems have found many applications that require tracking of moving objects and reconstruction of object shapes. For example, a multi-camera system can be used to track customers in a department store so that the time each customer spends in each department can be recorded and analyzed. Such a system can also be used to track the position and head orientation of a computer user sitting at a keyboard, an essential task in building a “smart” computer that interacts with the user.

[0004] Video telephone and video conferencing equipment can also use a multi-camera system to track the motion of participants and aim the video cameras at a specific participant, such as the person talking. Other applications include surveillance and remote sensing. While it is possible to accomplish some of these tasks with a single camera, multi-camera systems offer a number of advantages. These advantages include the following:

[0005] 1. Multiple cameras allow more precise information to be obtained from different areas, thus enhancing robust estimation and the final verification process;

[0006] 2. Multiple cameras can more readily find the actual size and location of an object, thereby eliminating or greatly reducing the intrinsic scale ambiguity problem on shape and location estimates when a single camera is used; and

[0007] 3. Multiple cameras can combine partial shapes seen from individual cameras through a registration process to form a more complete 3 dimensional (3D) view of the object.

[0008] While multi-camera systems have preferred advantages over single camera systems, use of such multi-camera systems present their own challenges. One such challenge is to ensure synchronization among frames captured by different cameras. Although it is possible for a central control unit to distribute a common clock signal to all cameras, such a solution is often very costly to implement.

[0009] Accordingly, it is an object of the present invention to obviate the above-noted shortcomings and disadvantages of single and multi-camera systems known in the prior art.

[0010] Another object of the present invention is to provide a method of synchronization of the captured frames of a multi-camera system which can be easily and inexpensively performed.

[0011] It is another object of the present invention to provide a method of synchronization of the captured frames of a multi-camera system which does not rely on the use of a common clock signal for each of the cameras.

[0012] It is another object of the present invention to provide a method of frame synchronization which is fully effective and reliable.

[0013] In accordance with the present invention, a technique is provided for calculating the time offsets between different cameras and re-synchronizing the captured frames in a post-processing manner, thus eliminating the necessity of an explicit common clock. This approach allows effective synchronization of frames from different cameras so that a multi-camera system can be used to more accurately analyze the subject under observation.

[0014] The novel features of the present invention are set out with particularity in the appended claims, but the invention will be understood more fully and clearly from the following detailed description of the invention as set forth in the accompanying drawings, in which:

[0015] FIG. 1 is a mathematical representation of two non-synchronized camera frame sequences;

[0016] FIG. 2 illustrates a flow chart for motion matching and frame synchronization in accordance with the present invention; and

[0017] FIGS. 3 and 4 illustrates matrices which contain orthonormal row vectors used to form the basis of a coordinate system.

[0018] In a video acquisition process where there are, for example, two image sequences having the same frame rate for the same scene containing multiple moving objects shot by two different cameras, there exists intrinsic difficulty in keeping the two sequences fully synchronized under a central clock signal. Such a situation is commonly encountered in many environments. One such environment is a surveillance system in which there is no guarantee that the recording process starts at the same time instant for all cameras. In other words, one sequence may lag another by an arbitrary and unknown amount even though the frame rates are the same.

[0019] To correctly identify each object's movement (location and rotation) and reconstruct its 3D shape, object correspondences and frame synchronization are essential tasks. Resolution of the frame synchronization problem involves a determination of the time shift between frames where the individual image sequences have the same frame rate and with known camera geometry. The recovery of the time shift is important for integrated processing of multiple image sequences.

[0020] In recovering the time shift in accordance with the present invention, Applicants utilize the following observations:

[0021] 1. The motion of a rigid body should be the same for observers at different locations (multiple cameras). Thus, the motion of an object provides key information for matching frame pairs from different cameras.

[0022] 2. A rigid body's rotation and scaled translation can be estimated from processing individual sequences. The best match of frame pairs results from close similarity of their estimated rotation since rotation cannot be changed by an arbitrary scale factor.

[0023] 3. When the time shift between two sequences is a multiple of frame duration (i.e. the product of time shift and frame rate is an integer), then the synchronization problem can be formulated as a string matching problem.

[0024] The degree of matching, or matching score, can be defined as the distance of two rotation matrix sequences and/or that of two translational vector sequences.

[0025] 4. In general, the time shift need not be an integer. An interpolation scheme is therefore proposed to improve the matching score so as to find the best match up to a fraction of frame duration.

[0026] FIG. 1 illustrates two non-synchronized sequences. Here, rotation string {R} is an estimate from as image sequence 1 while rotation string {R'} is an estimate from an image sequence 2 of the same object. As shown in FIG. 1, each string is plotted along a time axis “t”. The best match found in a first processing step 1 indicates that sequence 2 should lag sequence 1 by one frame as illustrated in FIG. 1. To find the final solution t₀in a step 2 for “fine-tuning” requires interpolation of the rotation strings.

[0027] The para-perspective projection model is assumed and factorization is used to reconstruct the 3D rotation R_3f×3translation T_3f×1and shape S_3×N. (A paraperspective factorization method for shape and motion recovery is described by C. J. Poelman and T, Kanada (Report CMU-CS-92-208, CMU, 1992) and is incorporated herein by reference.) Here, N is the number of feature points in this object cluster. For each frame, R(f) is a 3×3 rotation matrix describing the orientation of the object in frame f and T(f) is a 3×1 translation vector specifying the location of the object.

[0028] The para-perspective assumption yields two possible solutions for R and S for a single object from each camera due to its inability to distinguish a point's location to be in front of or behind the “scaled” image plane which goes through the object center. Without auxiliary information (e.g. occlusion) in a single camera system, this ambiguity cannot be resolved under the para-perspective assumption. However, as will be discussed below, this ambiguity can be solved if a second camera is viewing the same target or if a true perspective projection model is used to find the estimation.

[0029] FIG. 2 illustrates a flow chart for motion matching and frame synchronization in accordance with the present invention. Each camera has its own local coordinate system. Let a first camera 1, for example, be a reference camera whose local coordinate is the world coordinate and its focus matches the world origin. Let C₁and C₂be the matrices containing the orthonormal row vectors which form a basis for each coordinate system respectively, as illustrated in FIG. 3.

[0030] As shown in FIG. 3,U_x, U_yand U_zform the orthonormal basis for a coordinate system 1 and U_x, U_y, and U_z, forms the orthonormal basis for a coordinate system 2. The origin of coordinate system C₁is the world origin, for example, O_1`=[0 0 0]^T. The origin of coordinate system C₂is O₂=[X₀Y₀Z₀]^T. The conversion between two coordinate systems for a 3D point P =[X Y Z]^Tin coordinate system 1 and [X'Y'Z']^Tin coordinate system 2 is quite straightforward and is illustrated in FIG. 4.

[0031] For single objects, the reconstruction result from camera 1 and camera 2 is denoted by R₁, S₁(in C₁) and R₂, S2 (in C₂), respectively. In order to represent them in the same coordinate system, for example C₁, the positions of the set of points for each frame are R₁(𝑓)S₁for camera 1 and C₂⁻¹R₂(𝑓)S₂for camera 2. Since objects have one rigid motion which can be represented by the orientation (rotation) change between two consecutive frames, the following theorem can be obtained:

[0032] Theorem 1 - Assume that all objects in a scene have a distinctive rigid motion. Thus, then the reconstructed rotation matrices R₁and R₂from cameras 1 and 2, respectively represent the same rigid motion if, and only if, the following relationship is true.

[0033] Equation (1) R₁(f)R₁⁻¹(1) = C₂⁻¹R₂(f)R₂⁻¹(1)C₂∀ f

[0034] For simplicity, the first frame is used as the reference frame so that for both cameras 1 and 2, R₁(1) =I and R₂(1) =I. Thus, Equation (1) then becomes:

[0035] R₁(f) =C₂⁻¹R₂(f)C₂∀f.

[0036] The para-perspective assumption provides two possible solutions of R and S for a single object from each camera due to its inability to distinguish whether a point's location is in front of behind the “scaled” image plane which passes through the object's center. Suppose from camera 1, the two sets of solution for the rotation and shape of object A are denoted by RAI, ^SAD RAI and Sail respectively. Let J=: $J=\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& -1\end{array}$

[0037] Thus, the two sets of solutions have the following relationship:

[0038] S^˜_A1=JS_A1

[0039] R^˜_A1=JR_A1J

[0040] This also applies to the two sets of solution from camera 2. Therefore,

[0041] S^˜_A2=JS_A2and R^˜_A2=JR_A2J.

[0042] Theorem 2 - Given two sets of rotation estimates per camera for the same object, R₁, JR₁J from camera 1 and R₂, JR₂J from camera 2, if R₁(f) R₁⁻¹(1)=C₂⁻¹R_{2(f) R2}⁻¹(1)C₂∀f, then:

[0043] R₁(f) ≢ C₂⁻¹J R₂(f) J C₂

[0044] J R₁(f)J ≢ C₂⁻¹R₂(f) C₂

[0045] J R_l(f)J ≢ C₂⁻¹J R₂(f) J C₂

[0046] In other words, there is only one unique match and consequently a unique set of object motion and shape can be determined. Note that this sign ambiguity can also be removed with only single camera sequence by taking advantage of the predictable choice between concavity/convexity versus positive/negative displacement from the center's image. However, it is important that the second camera offers another more robust alternative to find this unique matching.

[0047] As explained above, there is intrinsic difficulty in using two cameras to shoot the same scene in a fully synchronized manner. In other words, one sequence may lead or lag another by an arbitrary unknown amount even though the frame rate is the same. The present invention determines the time offsets between the different cameras so that individual frames can be synchronize together. This serves as an important processing stage in many video applications.

[0048] When two sequences are fully synchronized, then the motion, especially rotation, reconstructed from individual sequences greatly improves the ability to match the same object in different views. If a sufficient number of frames is considered, multiple rotation strings (due to multiple objects) from one camera can be interpreted as being a time-shifted version of those frame from another camera. Object matching and frame synchronization can therefore be treated as solving a pairwise string matching problem. Two rotation strings from different cameras tend to be shifted and the best match can be found via a matching score function which indicates the similarity of the two rotation strings.

[0049] As shown in FIG. 1, if the two rotation strings {R) and {R′) are from the same object, then is desired to find to so that to =arg maxt MatchScore(R(f-t),R′(f)). In the special case when the time offset to is a multiple of the frame duration, then to is an integer. However, in general to need not be an integer. Without knowing whether to is an integer, the problem can be solved by the following steps:

[0050] Step 1: Find t₀for its best integer solution by string matching.

[0051] Step 2: Fine-tune t₀by linear interpolation of rotation strings.

[0052] In practice, the temporal offset between two sequences captured by different cameras is limited to one frame interval, except for the rare case that one camera introduces some delay in the capturing mechanism. Therefore, Step 1 above can usually be skipped. Step 2 is applied to find the best to that maybe positive or negative.

[0053] It should be obvious from the above-discussed apparatus embodiment that numerous other variations and modifications of the apparatus of this invention are possible, and such will readily occur to those skilled in the art. Accordingly, the scope of this invention is not to be limited to the embodiment disclosed, but is to include any such embodiments as may be encompassed within the scope of the claims appended hereto.