Rolling shutter distortion correctionChia-Kai Liang*, Yu-Chun Peng**, and Homer Chen***Graduate Institute of Communication Engineering, National Taiwan University, TaiwanABSTRACTAs opposed to the global shutter, which starts and stops the light integration of each pixel at the same time by incorporating a sample-and-hold switch with analog storage in each pixel, the electronic rolling shutter found in most low-end CMOS image sensors today collects the image data row by row, analogous to an open slit that scans over the image sequentially. Each row integrates the light when the slit passes over it. Therefore, the scanlines of the image are not exposed at the same time. This sensor architecture creates an objectionable geometric distortion, known as the rolling shutter effect, for moving objects. In this paper, we address this problem by using digital image processing techniques. A mathematical model of the rolling shutter is developed. The relative image motion between the moving objects and the camera is determined by block-based motion estimation. A Bezier curve fitting is applied to smooth the resulting motion data , which are then used for the alignment of scanlines. The basic ideas behind the algorithm presented here can be generalized to deal with other complicated cases.Keywords: rolling shutter, motion estimation1.INTRODUCTIONMore and more low-cost imaging devices are equipped with CMOS image sensor array. Unlike the CCD sensor array that normally has interline connections, the CMOS sensor array does not hold and store all the pixels. An electronic rolling shutter is thus resulted because each scanline of the CMOS sensor array is exposed, sampled, and stored sequentially. An annoying effect of the electronic rolling shutter is that it introduces geometric distortion to moving objects. A graphical illustration of this annoying effect is shown in Figure 1. We can see that the image of a vertical object becomes slanted. In this simple example, we assume that the object is stationary and the camera is moving. Note that the same effect occurs when the image of a moving object is captured by a still camera. In general, as long as there is a relative motion between the camera the scene, the rolling shutter effect would appear. The extent of the geometrical distortion depends on the magnitude and direction of the relative motion.Many circuit architectures have been developed to address the rolling shutter problem1, 2 by implementing a sample-and-hold circuit for the CMOS sensor. However, the transistor count of such architectures becomes two to four times more than that of the original architecture, introducing new problems, such as the requirement of more advanced IC process, that are more costly to solve.Little has been studied to overcome the rolling shutter effect by digital image processing. C. Geyer et al. have derived a camera model for rolling shutter cameras3. They developed a general rolling-shutter constraint on the motion of each image point. However, this approach involves an elaborated procedure to compute the 3-D motion of object that is sensitive to image errors..In this paper, we develop a simple model to characterize the rolling shutter effect without resorting to 3-D analysis. With this model, the rolling shutter distortion can be corrected by the alignment of scanlines. An attractive feature of this algorithm is that it is relatively easy to implement.The paper is organized as follows. Section 2 describes our approach to the compensation of rolling shutter distortion, including a basic mathematical model of the rolling shutter, an algorithm for rolling shutter compensation, and the extension of the algorithm to more general image motions . Section 3 describes the setup of our experiments in detail and shows the simulation results. This is followed by a conclusion in Section 4.*r93942031@.tw **b88901049@.tw ***homer@.twVisual Communications and Image Processing 2005, edited by Shipeng Li,Fernando Pereira, Heung-Yeung Shum, Andrew G. Tescher, Proc. of SPIE Vol. 5960(SPIE, Bellingham, WA, 2005) · 0277-786X/05/$15 · doi: 10.1117/12.6326712.APPROACHWithout loss of generality, we start the derivation of our approach with the case where the object is stationary and thecamera moves horizontally from right to left, as shown in Figure 1(a). Since the camera is moving, by the time thecamera finishes storing the sampled data of the first scanline and is ready to scan the second line, the object wouldappear to have moved by a certain distance horizontally. Therefore, a displacement between the sampled data along thetwo scanlines is resulted. This is shown in Figure 1(b). In effect, the shape of the object is seriously distorted whenthe entire image of the object is captured. The basic idea of our approach, as shown in Figure 2(a), is to correct thisgeometric distortion by aligning the scanlines according to the apparent object movement detected in the image. InFigure 2(a), x i is the displacement between scanlines l i and l i+1. Note that x i is equivalent to the displacement between the horizontal object segments shown in Figure 2(b).(a) (b) Figure 1. Illustration of the rolling shutter effect. (a) A vertical object appears to move to the left of the image while a rolling shuttercamera moving horizontally to the right of the object acquires the image data line-by-line. (b) The resulting image of the verticalobject (partial view). Note the inevitable distortion on the object caused by the rolling shutter.(a) (b)Figure 2. (a) Correcting the rolling shutter distortion by aligning the scanlines. (b) The object displacement x i betweenscanlines.For the approach to work, the displacement (or offset) x i along each scanline has to be determined. This displacementof scaneline l i is related to the velocity v(t) of the object, measured in the image plane, by1,nT i ti nT i t x v t dt ' ' ³ (1)where n is the frame index, Ϧt is the exposure time of each scanline, and T is the time interval between two consecutivevideo frames. For most commercial cameras, we may consider that there is a constant time lapse d between the end of theprevious frame and the beginning of the current frame. Assuming a constant frame rate f , we have T=1/f . Then theexposure time of the scaneline can be determined by,t T d S '(2) where S denotes the total number of effective scanlines in a video frame.Based on v (t ), we can determine the displacement x i line-by-line and hence compensate the rolling shutter distortion.Since the object is stationary, we determine v (t ) by global motion estimation. The global motion vector of the n th frameis related to the camera motion by³nT T n dt t v nT GMV 1 (3) ³¦ nT n i dt t v iT GMV nT AGMV 00 (4)where GMV (nT ) is the global motion vector of the n th frame and AGMV (nT ) denotes the accumulated global motion vector with respect to the first frame.If v (t ) varies slowly, it can be computed by the finite difference method as followsT nT GMV T T n AGMV nT AGMV dt t dAGMV nT v nT t 1)( (5)The block diagram of our rolling shutter correction algorithm is shown in Figure 3. In this algorithm, a block-based motion estimation is applied to the image sequence. The global motion is determined by clustering and classifying the motion vectors thus obtained.5 Then v (t ) is calculated by equation (5), and x i is obtained by (1). Finally each scanline of the distorted image is compensated by x ito generate the corrected image.Figure 3.Block diagram of the rolling shutter correction algorithm.Note that a constant velocity for the entire frame is assumed in (5). However, this constant velocity assumption may not always be a good approximation. This is illustrated in Figure 5, where the solid curve is the actual accumulated global motion, and the piecewise linear segment represents the accumulated global motion under the constant velocity assumption. An ideal case occurs when the two curves completely overlap. In such a case, the estimated x i leads to accurate rolling shutter compensation. When the two curves are apart from each other during a frame interval, the algorithm may not generate good result.To improve the performance of the algorithm, we reconstruct the value of AGMV (t ) from the sampled AGMV (nT )and obtain dAGMV (t )/dt at the time instant of interest. Here, we are dealing with the case where the sampling rate of AGMV (t ), which is equal to the frame rate, is potentially smaller than the bandwidth of AGMV (t ). According to the Nyquist theorem, this may lead to an aliasing effect. If the reconstructed AGMV (t ) is larger than the real one, an over-compensated frame is resulted, as shown in the 45th compensated frame in Figure 4(b) where the Christmas tree is slightly tilted over to the left. Note that the over-compensation can happen to the finite difference method and thereconstruction method.(a)(b)Figure 4. (a) The 39th (left) and 45th (right) frames of the original sequence (6 frames/sec). (b) The corrected frames.Figure 5. Accumulated Global Motion Vector.We have observed the over-compensation degrade the video quality much seriously than under-compensation. Therefore, we need to apply a low pass filter upon AGMV (t ) to make it smoother. However, it is difficult to find a filter suitable for AGMV (t ). Even it can be found, it normally requires a large number of samples as input, resulting in a large output delay. Instead, we adopt the Bezier method to approximate the curve. A Bezier curve for AGMV (t ) between nT and (n +1)T is described by,1313143322213P t P t t P t t P t t Q (6)where P i ’s are the control points of the curve, which can be derived by using the following boundary conditionsT n AGMV Q 20 (7) T n AGMV Q 11 (8) nT AGMV Q 32 (9)T n AGMV Q 11 (10)Once the control points are obtained, the velocity v (t ) can be calculated by ¸¹·¨©§ T T t Q dt d t v 32 (11)The dotted curve in Figure 5 shows the reconstructed curve based on AGMV(nT). The Bezier method removes the high frequency components of AGMV(t). Unlike deterministic low pass filters, the Bezier method is a low pass filter with adaptive control points and introduces only one frame delay. The control points are updated frame-by-frame according to the local characteristics of AGMV(t). The result of Bezier curve method is shown in Figure 6, where the over-compensation is removed.(a)(b)Figure 6. (a) The 39th (left) and 45th (right) frames of the original sequence (6 frames/sec). (b) The corrected frames using Bezier curve approximation.We have shown how to correct the rolling shutter distortion for the simple horizontal motion case. Now we discuss how to generalize it to other types of motions. For the case where the scene is static and the camera moves perpendicularly to the scanlines, the rolling shutter compensation can be achieved in a similar way. However, an extra step is required to interpolate the missing scanlines. An illustration of the problem is shown in Figure 7.(a) (b)Figure 7. The rolling shutter effect due to vertical camera motion. (a) The distorted image. (b) The compensated image.If the objects in the scene are at different depths, our algorithm in general can still restore the image because the global motion obtained by the algorithm represents the motion of most parts of the image. For the case where the camera is stationary and the objects are moving, the algorithm can be further enhanced by supplementing it with a segmentation technique to distinguish the objects from each other and from the background.Figure 8. VGA frame timing of OmniVision 1.3 MegaPixel CameraChip3.SIMULATION RESULTSWe implement our algorithm on two different video sequences captured by OmniVision 1.3 MegaPixel CameraChip4. This chip only performs image format conversion and color interpolation on the captured images. The timing parameters of this chip shown in Figure 8 are obtained from the user’s manual. Both simulation sequences are in VGA size. In our simulations, the search range of motion estimation is r120 pixels and the vertical compensation is turned off.Figures 9 and 10 show the results of our first simulation. The frame rate of this sequence is 6 frames per second. The blank region of the corrected images is filled with black pixels. Based on the black region, it can be clearly seen that the velocity v(t) of (1) is not constant.Figure 9. The original and corrected 1st, 5th and 6th, and frames of the first sequenceFigure 10. The original and corrected 12th, 26th, and 38th frames of the second sequence Figures 11 and 12 show the simulation result of our second sequence. In this simulation, the frame rate is 12 frames per second. Because of the smoothing effect on the global motion vectors, no over-compensation occurs in the corrected images.Figure 11. The original and corrected 1st, 15th, and 30th frames of the second sequenceFigure 12. The original and corrected 45th, 60th , and 75th frames of the second sequence Our algorithm corrects most distortions caused by translational movements, even if there are moving objects in the scene. However, non-translational movements, such as rotation and zooming, are not analyzed yet. The information loss in non-translational motion is serious and block-based motion estimation is not suitable to detect such movements. We will construct a more robust distortion model of the rolling shutter effect in non-translational motion.4.CONCLUSIONIn this paper, we have described an algorithm for compensating the rolling shutter effect. A mathematical model for rolling shutter cameras is developed. Two different correction methods, the finite difference method and the reconstruction method, are examined and their drawbacks are discussed. Because over-compensation degrades the video quality, a Bezier curve fitting technique is adopted to smooth the global motion and improve the video quality. Compared with other techniques, this algorithm only involves digital image processing and does not need any sample-and-hold circuit. The algorithm is relative easy to implement.REFERNECES1.S. Lauxtermann et al., “A mega-pixel high speed CMOS imager with sustainable gigapixel/sec readout rate”, inProc. 2001 IEEE Workshop on Charge-Coupled Devices and Advanced Image Sensors, pp. 48-51, Lake Tahoe, NV, June 7-9, 20012.M. Wäny and G.Paul, “CMOS image sensor with NMOS-only global shutter and enhanced responsivity”, in IEEETransactions on Electron Devices, vol. 50, no. 1, pp. 57-62, January, 20033. C. Geyer, M. Meingast and S. Sastry, “Geometric Models of Rolling-Shutter Cameras”, 4.OmniVision Technologies, Inc. 5.Chia-Kai Liang, Yu-Chun Peng, Hung-Au Chang, Che-Chun Su and Homer Chen, “The effect of digital imagestabilization on coding performance”, International Symposium on Intelligent Multimedia, Video and SpeechProcessing, October, 2004。