1. Introduction

Video stitching provides high-resolution panoramic video of large field-of-view and has been widely used in multi-camera surveillance systems to monitor public places in wide areas [1-2]. However, in spite of satisfactory stitching results, most video stitching methods entail difficulty in meeting the increasing demand for real-time performance and visual quality [3-7]. Video stitching is performed in three steps: registration, seam-searching and blending.

In existing multi-camera surveillance systems, the locations of cameras remain stable and fixed. Thus, matching and registration of images from different cameras can be implemented only at the beginning and then keep changeless for the following frames. Meanwhile, real-time update is necessary for stitching seams according to the change in video content.

To obtain a satisfied result in video stitching with a natural transition from one frame to another, it is needed to decide which pixels to use and how to blend them in the overlapping area. Compared with simple techniques such as feathering and center-weighting, finding optimal seams in the overlapping area achieves better results. Although a variety of seam-searching algorithms have been applied in image stitching and obtain satisfactory visual quality, most of them fail to meet real-time performance, which limits their application in video stitching. In this paper we make improvements on an existing seam-searching algorithm to accelerate the computing speed while maintaining the accuracy in the meantime.

When moving objects pass through the seam, the sections on both sides of the seam are combined in the fusion strategy. The shape of the merged moving object may be deformed owing to the inevitable registration and calibration errors, as shown in the red box in Fig. 1(b). As perceivable stitching quality is more sensitive to moving objects than to static objects, the deformation of moving objects results in the artifacts and impairs the subsequent object detection, recognition and tracking. To cope with this problem, a real-time local update strategy is associated with seam-searching process in our method and prevents the seams from passing through moving objects.

Fig. 1.Deformation of moving objects passed through by the stitching seam

As the images to be stitched are taken with different cameras, lighting condition and intensity differences may influence the consistency of the entire scene. Thus, color correction and smooth transition should be implemented in video stitching, but traditional methods are complex and make satisfactory results difficult to achieve. Applying color correction model is an effective technique, but conventional global color corection often fails to consider the local feature of color diffrence. Instead of taking a global color correction model, we introduce a local model to make color correction within local regions obtained by image segmentation. The local color correction model makes better use of the information of the stitching seam and achieves smooth transition in the overlapping area.

The rest of the paper is organized as follows. In Section 2, we review previous research on video stitching, including seam searching, dealing with moving objects and color correction. In Section 3, we describe our video stitching method. A two-stage seam searching method based on enhanced dynamic programming algorithm is proposed, followed by a local update scheme of stitching seam to cope with moving objects. To improve the quality of smooth transition, a seam-based local color transfer model is constructed. In Section 4, we present the experimental results of video stitching using the proposed method and compare this method with conventional ones. In Section 5, we summarize the main conclusions and discuss directions for future research.

2. Related Work

In the overlapped areas of stitched images, it is required to obtain optimal seams which can decide how to choose and blend pixels from different images. Some conventional seam-searching algorithms, such as Graph Cuts [5], Dijkstra algorithm [6], traditional dynamic programming [8] have been used in static image stitching and achieved satisfactory stitching result. However, most of these algorithms often fail to obtain satisfactory performance in real-time video stitching, especially for huge amounts of video data, because of their computational complexity and large memory requirements.

Among these algorithms, enhanced dynamic programming [7] is less time-consuming because of low computing complexity and it provides more flexible extending directions for seam-searching than dynamic programming. Therefore, enhanced dynamic programming is an effective seam-searching algorithm. Although the conventional enhanced dynamic programming algorithm finds the global optimal seam, its real-time performance is still limited and it requires improvement when being used in video stitching.

When motion occurs in the overlapping area, the deformation of the merged moving object would reduce the accuracy of object detection, recognition and tracking. Image and video stitching with moving objects has been studied by several researchers [2,9,10]. Uyttendaele et al. [9] proposed a region of difference based method to deal with moving objects in the overlapped area. Mills presented a new technique to create consistent image mosaics in spite of the presence of moving objects [10]. In the seam-searching process, it is necessary to deal with moving objects separately to keep the consistency of moving parts.

Due to color and intensity differences of multiple cameras, incoherence may occur in the stitched image. Conventional methods including linear color transfer model [11,12] is proposed to adjust the gain level of the images captured by different cameras. These methods use invariable color transfer models to deal with color difference in the overlapped area. Although the models are simple and obtain good performance, they fail to achieve smooth transition and generate a visible seam. Some conventional image blending techniques [13,14] cause blur when blending pixels from different images. Instead of taking a global color correction model which often fails to consider the local feature of color difference, color correction can be made in local regions with similar color features. Image segmentation which has been studied by many researchers [15,16] provides a new perspective for local color correction.

Based on the previous research about image and video stitching, we propose a novel real-time panoramic video stitching method for multi-camera surveillance system. The proposed two-stage seam searching method based on enhanced dynamic programming can obtain satisfactory seam-searching result while achieving better real-time performance. In addition, a local update strategy is proposed for seam update, which can prevent the moving objects from passing through the seam, thereby maintaining the shape of the objects and avoiding the resulting deformation. A seam-based local color transfer model is constructed to achieve smooth transition in the overlapped area.

3. Video Stitching Method for Multi-Camera Surveillance Systems

3.1 Implementation of registration

Considering that the relative locations of cameras remain stable for most of the multi-camera surveillance systems, the alignment, registration and matching relations of different images are fixed. To improve the real-time performance of coordinate transformation, the one-to-one correspondence between coordinates can be stored in a pre-calculated look-up table (LUT).

For the pixel in the stitched image, the coordinates of corresponding source pixels are stored in the LUT. It is needed to look up the corresponding coordinates in the LUT. Registration and alignment of images can be implemented through simple look-up operations instead of complex conventional algorithms.

Every pixel (xc, yc) in the stitched image corresponds to a source pixel in the source image Si , and can be expressed as: where I(ㆍ) and D(ㆍ) are the integral and the fractional part, respectively. The pixel value at (xc, yc) can be obtained:

where

Static overlapped images are taken by the cameras, and alignment, registration and matching of these images can be achieved using SIFT and RANSAC algorithms [12]. The images are projected and transformed to form the stitched image. Thus the look-up table can be constructed and then applied to video stitching. Given the fixed and immovable layout of the cameras, the same LUT is used for different scenes when this platform is moved to another location.

The implementation of the LUT is shown in Fig. 2.

Fig. 2.Look-up table (LUT) implementation.

The entire LUT can be divided into a series of sub-tables (sub-LUT) that can be handled in parallel to improve the processing efficiency. The size of each sub-table is Ws × Hs. A bounding box covering the corresponding part of the image can be obtained and loaded into memory.

3.2 Two-stage seam searching method based on enhanced dynamic programming

Although the traditional enhanced dynamic programming algorithm can obtain the global optimal seam, its computational complexity degrades the real-time performance. In this section, we introduce a two-stage seam searching method based on enhanced dynamic programming algorithm. This algorithm not only takes advantage of the traditional enhanced dynamic programming, but also improves the real-time performance. The proposed algorithm is described as follows:

Stage 1: Down-sample the original image with the sampling interval of r . Perform enhanced dynamic programming algorithm on the down-sampled image and obtain the optimal seam, which is then interpolated to the original resolution, as shown in Fig. 3(a). The interpolated seam, which is the approximation of the final optimized seam, can be used as the initial value of stage 2;

Stage 2: Perform enhanced dynamic programming algorithm in the adjacent area along the initial seam with the width of K , and obtain the final optimized seam, as shown in Fig. 3(b).

Fig. 3.Two-stage seam searching method based on enhanced dynamic programming algorithm.

The seam-searching process in the two stages can be implemented as follows:

(1)For each row of the overlapped area ( from the bottom to the top ), calculate the minimal accumulated cost f (i, j) for every pixel (i, j) as f (i, j) = where is the minimal accumulated cost calculated from the left border to the right border and is that calculated from the opposite direction, which can be obtained as follows:

where Pk(k = 1 ㆍㆍㆍ5) denotes the following points:

The seam-searching process discussed above is illustrated in Fig. 4.

Fig. 4.Illustration of seam-searching process.

(2) Select the point that satisfies as the starting point of the seam, and obtain the optimal seam according to the values of minimal accumulated cost.

In the seam-searching process, the definition of the cost function is similar to the definition of cost value [7].

where Sg and Sc measure the gradient smoothness and the color vector similarity of corresponding pixels in the overlapped region, respectively, and α,β are the weights used to balance the relative influence of the two factors. Thus the cost value in the overlapped area can be constructed as an image with pixel values indicating the gradient smoothness and the color vector similarity for each point.

However, the determination of the weights α,β as well as Sg, Sc remains a problem. The values of the weights are important to the process of seam searching and improper selection of weights may cause imbalance of the two factors and degrade the seam-searching result and image stitching quality. To solve this problem, we use the following technique to determine the weights.

can be defined as:

where I1,I2, are the overlapped images, and represents the norm of the gradient for each pixel. denote the maximum value of ▽(I1+I2) and respectively.

If the two factors are considered to be of the same importance when calculating the value of cost function, then α = β = 0.5 .Thus the relative influence of the two factors can be balanced. The cost value of the three testing overlapped areas in our experiments is shown in Fig. 7. The corresponding source images I1,I2 and I3 are shown in Fig. 8.

3.3 Local update of stitching seam

Moving objects contained in the overlap area cause partial change in only part of the scene instead of the entire scene. For most parts, the video contents remain static and changing the segments of the seam passing through static area is unnecessary.

We divide the existing image into sections with the same height and each section contains a segment of the seam, as shown in Fig. 11. Each segment can be handled independently. When the moving objects appear in the overlapped region but are far from the seam, dealing with them immediately is not necessary. The adjacent area Ra is defined as the pixels located along the seam with a horizontal distance less than Δd :

where Sp is the seam point which is of the seam row as pixel P . Moving objects approaching the seam result in difference in the adjacent area. Thus we only need to perform object detection in the adjacent region instead of the entire overlapped region, and make local modification to the seam if some moving objects pass through it. The code-book scheme [9] is applied in detecting moving objects in the adjacent region.

For the stitching seam the strategy of local update can be listed as follows:

1. If the moving object is detected near the seam segment and no moving objects are found for the adjacent segment update the seam segment using the two-stage seam searching method.

2. If moving objects are detected near a series of seam segments update the seam part using the two-stage seam searching method.

The local update strategy 1 and 2 are illustrated in Fig. 5(a) and (b), respectively. The seam segments in red are the parts to be updated. The result for local update of stitching seam is shown in Fig. 12.

Fig. 5.Local update strategy for stitching seam

3.4 Seam-based local color transfer model

Although the color difference between neighbour images is effectively decreased, stitching seam still exist in the overlapped area. Considering that perceiving visual quality turns to be more sensitive to the the seams in the transition areas, a smooth scheme is required to eliminate the visible seams.

Instead of taking a global color correction model that often fails to consider the local feature of color diffrence, we introduce a local model to perform color correction within local regions. Segmentation for the overlapped areas is implemented by mean shift algorithm [14], as shown in Fig. 15(a).

In our two-stage seam-searching approach, the optimal seam is obtained (Fig. 15(b)). Within the local regions which is not passed through by the seam, the color remains continuous and coherent, so adjusting the color in these regions is not necessary. We construct a seam-based local color transfer model and apply this method to the regions passed through by the seam. Instead of blending the pixels in two images, we use a linear model for color transfer on the pixels within each local region, which is able to adjust the coefficients according to the horizontal distance to the seam.

For each local region passed through by the seam in the overlapped area, we consider the pixels on the seam for the two neighbor images. For overlapped images 1 and 2, the overlapped area in the stitched image is divided into two parts ( Parts 1 and 2, as shown in Fig. 15(b) ) by the stitching seam, that belongs to source image 1 and 2, respectively. The overlapped area is segmented into local regions by mean shift algorithm. Within each local region, the color of pixels remains coherent and continuous, so color correction is conducted within each local region instead of the entire overlapped area.

where SP(i) is the set of m seam points for image i (i = 1,2) and is one of the seam points. denotes channel j for pixel Solve the linear models for R, G, and B channels, respectively, and get the coefficients:

where:

is the weighted combination of seam points in source image 1 and 2:

nc(t) and Nc denote the column index of and the width of the overlapped area, respectively. For each local region in Part 1, the linear color transfer model for each channel j = R,G,B at pixel x is defined as:

where cj(x) and (i = 1,2; j = R, G, B) denote the color values of channel j at pixel x for the stitched image and source image 1 and 2, respectively. Instead of keeping constant values, the coefficients adjust as follows:

where nc(x) is the column index of pixel x, and ds(x) is the horizontal distance to the seam (number of pixels) at pixel x . and Δαi(x) , Δβi(x) are obtained as follows:

Similarly, we can obtain the color transfer model at pixel x for Part 2 as follows:

where the values of coefficients are obtained as follows:

where are expressed as:

The result of the seam-based local color transfer model is illustrated in Fig. 16(c).

4. Experimental Results and Analysis

The procedure of the proposed algorithm is illustrated in Fig. 6.

Fig. 6.Flowchart of the proposed algorithm

The experiments are conducted on a multi-camera sampling platform using HIKVISION DS-2CD3210(D)-I5 720p cameras. The proposed video stitching algorithms are implemented on a 2.00 GHz PC with 2GB memory. In Fig. 8, the results of different seam-searching algorithms for three overlapped areas: image I1, I2 , I3 are compared, with (a)-(c), (d)-(f) and (g)-(i) illustrating the seams obtained through dynamic programming, enhanced dynamic programming and the proposed algorithm, respectively. In these algorithms, the stitching seams are illustrated with red labels.

Compared with the dynamic programming and enhanced dynamic programming algorithm, the seam-searching result of the proposed algorithm is also satisfactory. Meanwhile, the proposed seam-searching algorithm can effectively reduce the computational complexity, as illustrated in Table 1.

Video stitching based on the proposed seam-searching algorithm obtains almost the same satisfactory result as enhanced dynamic programming, while the dynamic programming algorithm suffers worse stitching results. As shown in Fig. 1, when the seam obtained by dynamic programming passes through unsmooth region (Fig. 1(b)), deformation and incoherence occur in the red pane. Seam-searching using the proposed algorithm is more flexible in the searching direction because the seam can extend on the horizontal direction. Thus the unsmooth region can be detoured by the seam. The overlapped areas have a dimension of 640× 480 , based on the surveillance videos.

The comparison of merging results for the proposed method and the traditional dynamic programming algorithm are shown in Fig. 9 and Fig. 10. Structure deformations occur in the red boxes in Fig. 10 for dynamic programming, while the proposed algorithm can obtain satisfactory merging result.

Fig. 7.Cost value of overlapped areas for images I1, I2 , I3

Fig. 8.Comparison of seam-searching results. (a)-(c), (d)-(f), (g)-(i) are the seam-searching results of dynamic programming, enhance dynamic programming, and the proposed algorithm, respectively. Three columns of images correspond to image I1, I2 , I3, respectively.

Fig. 9.Merging results of the proposed algorithm

Fig. 10.Merging results of the dynamic programming

Given the combinations of parameters r and K , the computing time of seam-searching and the accumulated cost of stitching seam obtained by Equation (3) are shown in Tables 1 and 2, respectively.

Table 1 and 2 indicate that the proposed seam-searching algorithm overcomes conventional methods in terms of computing time, and the accuracy of this algorithm is also satisfactory. Although the value of accumulated cost of stitching seam is slightly higher than that of enhanced dynamic programming owing to information loss in the down-sampling process, it achieves better real-time performance and hardly influences the stitching quality.

Table 1.Computing time of seam-searching

Table 2.Accumulated cost of stitching seam

Table 1 and 2 show that the computing time of seam searching and the accumulated cost of stitching seam are sensitive to the settings of parameters r and K . Less accumulated cost of stitching seam corresponds to higher visual quality of the stitched image. Considering both computing time and accumulated cost, the combination r = 4,K = 60 generates the best result and the corresponding seam-searching results are shown in Fig. 8(g-i). Compared with enhanced dynamic programing, the computing time of the proposed method is reduced by 66.4% on average for the input images, while the seam-searching performance is maintained.

With the increase of sampling interval r , the computing time of stage 1 drops dramatically because of the decrease of pixels to be processed. However, the accumulated cost of stitching seams are also on the increase due to the error of the initial seam in stage 1, which is caused by information loss in the down-sampling process.

Larger values of K contributes to the decrease of accumulated cost, and the descent speed declines due to the increasing accuracy for seam optimization. The computing time of stage 2 is proportional to the choice of K . For image 1, when r = 4 the variation of accumulated cost and computing time of stage 2 with the increase of K is shown in Fig. 11(a) and (b).

Fig. 11.The variation of accumulated cost and computing time.

Fig. 12.Dividing the existing seam into sections.

As shown in Fig. 12, the entire seam is divided into sections. The results for local update of stitching seams in video surveillance are shown in Fig. 13, preventing the seam from passing through the moving objects. In our experiment, where w is the width of the overlapped area, and the seam is segmented into 9 parts. Compared with Fig. 1, the stitching results of the moving car passed through by the seam are shown in Fig. 13(a) and (b), indicating that the proposed algorithm can achieve better stitching result.

Fig. 13.local update of stitching seam

Smooth transition can be achieved using the seam-based local color transfer model. The two source images are shown in Fig. 14. Segmentation is implemented using Mean shift algorithm and the result is shown in Fig. 15(a), with the different colors indicating labels for regions. Fig. 15(b) illustrates the seam-searching result.

As shown in Fig. 16(a),(b), the method [12] cannot eliminate the visble seam and the blending method [13] produce blurring result as a result of registration error,. Based on the results of segmentation, the seam-based local color transfer model is applied to the local regions passed through by the seam. Compared with results of traditional smooth transition methods in Fig. 16(a) and (b), more natural and smooth transition result is obtained using the proposed model. Blurring and visible seams in the overlapped region are eliminated.

Fig. 14.Source images for smooth transition

Fig. 15.Segmentation and seam-searching for the overlapped area

Fig. 16.Comparison of smooth transition methods

The final results of video stitching with moving objects are displayed in Fig. 17.

Fig. 17.Results of video stitching

5. Conclusion

In this paper, a novel video stitching method for multi-camera surveillance systems is presented. To achieve better real-time performance for seam-searching process, a two-stage seam searching method based on enhanced dynamic programming is proposed and satisfactory seam searching result is obtained. A local update scheme for stitching seams is proposed to eliminate deformation results. A seam-based local color transfer model is constructed to achieve smooth transition between different images. Experiments have shown the effectiveness of the proposed method. For future research, hardware implementation of this method will be designed to accelerate the process of video stitching. Other efficient stitching algorithms will be further explored.