Keywords: Rolling shutter, Image correction, Pose estimation, Relative pose estimation, Homography, Structure from Motion, Bundle Adjustment. vii . . . . . . . . . . 6.3 Comparison of computation time of different RSSfM methods . . . .

3D Vision Geometry for Rolling Shutter Cameras

by Yizhen LAO Many modern CMOS cameras are equipped with Rolling Shutter (RS) sensors which are considered as low cost, low consumption and fast cameras. In this acquisition mode, the pixel rows are exposed sequentially from the top to the bottom of the image. Therefore, images captured by moving RS cameras produce distortions (e.g. wobble and skew) which make the classic algorithms at best less precise, at worst unusable due to singularities or degeneracies. The goal of this thesis is to propose a general framework for modelling and solving structure from motion (SfM) with RS cameras. Our approach consists in addressing each sub-task of the SfM pipe-line (namely image correction, absolute and relative pose estimation and bundle adjustment) and proposing improvements.

The first part of this manuscript presents a novel RS correction method which uses line features. Unlike existing methods, which uses iterative solutions and make Manhattan World (MW) assumption, our method R4C computes linearly the camera instantaneousmotion using few image features. Besides, the method was integrated into a RANSAClike framework which enables us to detect curves that correspond to actual 3D straight lines and reject outlier curves making image correction more robust and fully automated.

The second part revisits Bundle Adjustment (BA) for RS images. It deals with a limitation of existing RS bundle adjustment methods in case of close read-out directions among RS views which is a common configuration in many real-life applications. In contrast, we propose a novel camera-based RS projection algorithm and incorporate it into RSBA to calculate reprojection errors. We found out that this new algorithm makes SfM survive the degenerate configuration mentioned above.

The third part proposes a new RS Homography matrix based on point correspondences from an RS pair. Linear solvers for the computation of this matrix are also presented. Specifically, a practical solver with 13 point correspondences is proposed. In addition, we present two essential applications in computer vision that use RS homography: plane-based RS relative pose estimation and RS image stitching.

The last part of this thesis studies absolute camera pose problem (PnP) and SfM which handle RS effects by drawing analogies with non-rigid vision, namely Shape-from-Template (SfT) and Non-rigid SfM (NRSfM) respectively. Unlike all existing methods which perform 3D-2D registration after augmenting the Global Shutter (GS) projection model with the velocity parameters under various kinematic models, we propose to use local differential constraints. The proposed methods outperform stat-of-the-art and handles configurations that are critical for existing methods.

v

Résumé

De nombreuses caméras CMOS modernes sont équipées de capteurs Rolling Shutter (RS). Ces caméras à bas coût et basse consommation permettent d'atteindre de très hautes fréquences d'acquisition. Dans ce mode d'acquisition, les lignes de pixels sont exposées séquentiellement du haut vers le bas de l'image. Par conséquent, les images capturées alors que la caméra et/ou la scène est en mouvement présentent des distorsions qui rendent les algorithmes classiques au mieux moins précis, au pire inutilisables en raison de singularités ou de configurations dégénérées. Le but de cette thèse est de revisiter la géométrie de la vision 3D avec des caméras RS en proposant des solutions pour chaque sous-tâche du pipe-line de Structure-from-Motion (SfM).

Le chapitre II présente une nouvelle méthode de correction du RS en utilisant les droites. Contrairement aux méthodes existantes, qui sont itératives et font l'hypothèse dite Manhattan World (MW), notre solution est linéaire et n'impose aucune contrainte sur l'orientation des droites 3D. De plus, la méthode est intégrée dans un processus de type RANSAC permettant de distinguer les courbes qui sont des projections de segments droits de celles qui correspondent à de vraies courbes 3D. La méthode de correction est ainsi plus robuste et entièrement automatisée.

Le chapitre III revient sur l'ajustement faisceaux ou bundle adjustment (BA). Nous proposons un nouvel algorithme basé sur une erreur de projection dans laquelle l'index de ligne des points projetés varie pendant l'optimisation afin de garder une cohérence géométrique contrairement aux méthodes existantes qui considère un index fixe (celui mesurés dans l'image). Nous montrons que cela permet de lever la dégénérescence dans le cas où les directions de scan des images sont trop proches (cas très communs avec des caméras embraquées sur un véhicule par exemple).

Dans le chapitre VI nous étendons le concept d'homographie aux cas d'images RS en démontrant que la relation point-à-point entre deux images d'un nuage de points coplanaires pouvait s'exprimer sous la forme de 3 à 7 matrices de taille 3X3 en fonction du modèle de mouvement utilisé. Nous proposons une méthode linéaire pour le calcul de ces matrices. Ces dernières sont ensuite utilisées pour résoudre deux problèmes classiques en vision par ordinateur à savoir le calcul du mouvement relatif et le « mosaïcing » dans le cas RS.

Dans le chapitre V nous traitons le problème de calcul de pose et de reconstruction multi-vues en établissant une analogie avec les méthodes utilisées pour les surfaces déformables telles que SfT (Structure-from-Template) et NRSfM (Non Rigid Structure-from-Motion). Nous montrons qu'une image RS d'une scène rigide en mouvement peut être interprétée comme une image Global Shutter (GS) d'une surface virtuellement déformée (par l'effet RS). La solution proposée pour estimer la pose et la structure 3D de la scène est ainsi composée de deux étapes. D'abord les déformations virtuelles sont d'abord calculées grâce à SfT ou NRSfM en assumant un modèle GS classique (relaxation du modèle RS). Ensuite, ces déformations sont réinterprétées comme étant le résultat du mouvement durant l'acquisition (réintroduction du modèle RS). L'approche proposée présente ainsi de meilleures propriétés de convergence que les approches existantes.

Mot clés

Rolling shutter, Pose absolue et relative, Homographie, S-f-M, Ajustement de faisceaux.

The past three years at Clermont-FD have been an unforgettable and invaluable experience to me. I would not have been able to make this journey without the help and support of many, many people and I feel deeply indebted to them.

First of all, I want to thank my supervisor Helder Araujo for his guidance during my study. I also want thank Adrien Bartoli for being on my thesis jury and also for a lot of advices and valuable help throughout our collaboration. But specially, I want to express my deepest appreciation to my advisor Omar Ait-Aider. Omar is an extremely kind, caring and supportive advisor that I could not have asked for more. He continually instilled the requirements of being a good scientist into my mind, which will have a lifelong influence on me. And I have already started to miss him.

I would also like to thank all the jury members, Tomas Pajdla, Nicolas Andreff and Sylvie Chambon for reading my thesis. Their insightful remarks are absolutely helpful for this work.

Secondly, I want to thank my fellow PhD students at the ComSee group for many enlightening discussions and the time we working together. Besides, my thanks also go to my friends at Clermont-Ferrand, Chao Zhang, Jinpeng Wang, Yongzhe Yan, Miao Wang with all of whom I shared hours of discussion, study, work, play, food, and travel. In addition, I am thankful to some friends outside, Fang Li, Mingye Bao and Hanjun Ling for making my spare time enriched and memorable.

I thank my parents: Liling Jiang and Ningjun Lao. Like most Chinese students in my generation, I am the only child of my family and I have a very close relationship with them. They give me their very long emotional and financial support, true love, wisdom. In short, my parents made me who I am today and I never know how to pay them back. I hope that they are at least a little proud of me for what I have been through so far.

In the end, I want to thank my wife Yumeng for her love and support. Thank you for making our married life all that I dreamed it would be. Thank you for filling our home with love and happiness. Thank you for giving me the most beautiful children Da-He. I love you with all my heart.

List of Figures

Context

The main objective of 3D computer vision is to recover 3D information from a collection of 2-D images. This task is widely termed as 3D reconstruction. Although active image sensors which can provide the scene depth directly such as laser sensor cameras, timeof-flight and structured light RGB-D cameras are now available, 3D reconstruction from classical 2D images basing on multiple-view geometry remains an intensively studied topic for industrial and academic communities since it is considered as a low-cost and flexible solution. It had been applied to building reconstruction, hyperscale landform model generation, street view mobile mapping and even VR/AR gaming etc. When 3D reconstruction is needed, multiple view geometry based methods using consumer cameras (e.g. cellphone cameras) is much more cost and time efficient than classical methods such as aerial photogrammetry or laser scanning. However, these low-cost filming devices could easily suffer from some low-level imaging problems [START_REF] Yang | Challenges in monocular visual odometry: Photometric calibration, motion bias, and rolling shutter effect[END_REF], namely photometric calibration, image blur and rolling shutter (RS) effect, which can greatly affect the quality of 3D reconstruction from 2D images. In this thesis, we address the problem of 3D reconstruction from multiple images under RS effect.

Global Shutter VS. Rolling Shutter:

The camera sensor consists of a 2D array of photon-sensitive elements which record the intensity of light that falls on them. The global shutter (GS) mechanism employed in CCD sensors exposes all sensor elements to light at the same time. Thus, the 2D image is a projection of a 3D scene at a particular time, similar to the projection of light on the human retina. On the other hand, the rolling shutter (RS) mechanism in a camera sensor captures scenes in a different way compared to that of humans and global shutter. This mechanism is employed primarily in CMOS sensors as against CCD sensors as discussed by [Litwiller, 2001]. The rolling shutter sensor is designed in such a way that each of its rows starts its exposure sequentially one after the other. Through this mechanism, each of the rows ends its exposure at different times from each other, and hence, a single read-out circuit is shared by all rows. Thus, a rolling shutter camera embeds a temporal interplay between its exposure and sensor rows.

The shared read-out mechanism employed in rolling shutter sensors leveraging the sequential exposure reduces the circuitry used, resulting in a compact camera with reduced power consumption. For these reasons, RS cameras are considered as low-cost, smaller, faster cameras that use less power. They are the preferred choice for embedded consumer systems.

As shown in Fig. 1.1, almost all consumer cameras in the current market employ the RS mechanism, and hence, it is important to study its effects now.

3D Vision with RS Cameras

A static RS camera filming a rigid scene can be regarded as a GS camera. However, when either the scene or the camera moves during the acquisition period, the row delay introduces distortions and image artefacts called RS effect. Even with a shorter exposure, each row of sensors experiences different camera motion during its own exposure interval producing geometric distortions. Fig. 1.2(a) shows an image of a rotating propeller captured by a static rolling shutter camera. Fig. 1.2(b), shows a scene captured from a moving rolling shutter camera. Obviously, RS effect can not be corrected in a straightforward manner since it depends on both the scene geometry and the camera motion which are precisely the desired parameters in 3D vision applications.

Nowadays the multi-view geometry with GS is well understood and mature and stable solutions have been proposed for all 3D vision problems. Many solutions have been commercialized such as [Wu, 2011]. However, almost all these classical 3D reconstruction methods were developped for GS camera models. The use of these methods with RS cameras and dynamic scenes produces at best, degraded results, at worst errors due to ill-defined problems or singularities [START_REF] Hedborg | Rolling shutter bundle adjustment[END_REF].

Although RS, as a space-time sweeping camera, is related to non-central camera models such as push-broom (PB) cameras [START_REF] Hartley | Multiple view geometry in computer vision[END_REF], oblique cameras [Pajdla, 2002] and The Crossed-Slits (X-Slits) cameras [START_REF] Feldman | On the epipolar geometry of the crossed-slits projection[END_REF]. However, RS camera model had never been specifically addressed (even not been mentioned in the famous textbook in 3D vision [START_REF] Hartley | Multiple view geometry in computer vision[END_REF]) before it was defined geometrically for the first time in 2005 [START_REF] Meingast | Geometric models of rolling-shutter cameras[END_REF].

Motivation and Challenges

Applications

Developing 3D vision solutions for RS cameras is of a very broad interest in many applications where the images are taken with moving RS cameras such as hand-held mobile phone photography and robot platform. Good solutions have many applications in a range of domains including (some examples are shown in Fig. 1.3):

• Entertainment -Augmented Reality (AR)/Virtual Reality (VR) [Bapat and[START_REF] Bapat | [END_REF]Frahm, 2018] -Mobile phone image correction and denoising [Forssén andRingaby, 2010, Rengarajan et al., 2017] • Object pose and kinematic estimation [START_REF] Ait-Aider | Simultaneous object pose and velocity computation using a single view from a rolling shutter camera[END_REF], Magerand et al., 2012] • 3D scene reconstruction -Mobile vehicle platform [START_REF] Klingner | Street view motion-from-structure-from-motion[END_REF][START_REF]Rolling Shutter Stereo[END_REF] -UAV platform [START_REF] Vautherin | Photogrammetric accuracy and modeling of rolling shutter cameras[END_REF] • Robot navigation -Absolute pose estimation [START_REF] Albl | R6p-rolling shutter absolute camera pose[END_REF], Saurer et al., 2015] -Visual odometry (VO) [START_REF] Guan | Visual odometry using a homography formulation with decoupled rotation and translation estimation using minimal solutions[END_REF] -Visual SLAM [START_REF] Kim | Direct semi-dense slam for rolling shutter cameras[END_REF] -RS compensation for self-driving car [Purkait and Zach, 2017]

Current Approaches and Their Limitations

As mentioned earlier, the 3D reconstruction by using SfM with GS cameras cannot be directly extended to RS case. As these RS images may suffer from deformations, the interimage visual motion is now dependent on both camera pose and instantaneous-motion during the acquisition period.

RS images

(a) Application to single RS image correction [START_REF] Rengarajan | Unrolling the shutter: Cnn to correct motion distortions[END_REF] (b) Application to object pose [START_REF] Ait-Aider | Structure and kinematics triangulation with a rolling shutter stereo rig[END_REF] and camera pose estimation [Albl et al., 2017] (c) Application to UAV-based photogrammetry [START_REF] Vautherin | Photogrammetric accuracy and modeling of rolling shutter cameras[END_REF] (f) Application to large-scale RS SfM [START_REF] Klingner | Street view motion-from-structure-from-motion[END_REF] (e) Application to RS SLAM [START_REF] Kim | Direct semi-dense slam for rolling shutter cameras[END_REF] (d) Application to RS visual odometry [START_REF] Guan | Visual odometry using a homography formulation with decoupled rotation and translation estimation using minimal solutions[END_REF] FIGURE 1.3: Applications of 3D vision with RS cameras.

Existing work try to solve 3D reconstruction with RS cameras problem from different view angles:

• By correcting RS effect: [Purkait et al., 2017, Purkait andZach, 2017] attempted to compensate the RS effect in each image before performing classical GS SfM based on the corrected images.

• By using additional sensors: [START_REF] Klingner | Street view motion-from-structure-from-motion[END_REF], Saurer et al., 2016] try to solve the SfM with RS cameras by using GPS and IMU, which offer more information and constraints on camera motion.

• By using video sequence: [START_REF] Hedborg | Structure and motion estimation from rolling shutter video[END_REF], Zhuang et al., 2017, Im et al., 2018] propose to use RS videos, which provide ordered and successive frames with short base-lines, to recover the 3D scene.

• By using RS absolute pose estimation: Absolute pose estimation can be used to add a new frame and expand the reconstruction incrementally in SfM pipeline. Therefore, an effective RS absolute pose estimation method can serve for RS SfM (e.g. [START_REF] Albl | Degeneracies in rolling shutter sfm[END_REF] uses RS pose estimation method [START_REF] Albl | R6p-rolling shutter absolute camera pose[END_REF] to add the views.)

The extension of GS multiple view geometry with GS to the RS case is not straightforward. Most of existing solutions are with strong assumptions that limit the field of application. These hypotheses are made either on the geometry of the scene (planars scenes, Manhattan world, presence of vanishing directions) or on the kinematic model describing the movement during the acquisition (pure translation, pure rotation, smooth motion) or on the camera poses (short baselines, varying scanning direction). With the brief discussion above (details in section. 2.4), we want to emphasize the following limitations of existing SfM with RS cameras methods:

1. Strong assumptions that do not always hold in real applications such as pure rotation [Ito and Okatani, ], pure translation [START_REF] Saurer | Sparse to dense 3d reconstruction from rolling shutter images[END_REF] or smooth motion [START_REF] Hedborg | Structure and motion estimation from rolling shutter video[END_REF].

2. Using additional sensors which makes the implementation not straightforward [Hee Park and Levoy, 2014, Jia and Evans, 2012, Patron-Perez et al., 2015].

3. Video-based methods [START_REF] Liang | Analysis and compensation of rolling shutter effect[END_REF],Forssén and Ringaby, 2010,Kim et al., 2011, Grundmann et al., 2012, Zhuang et al., 2017] commonly impose a high acquisition framerate which results in high computational efficiency requirements. Unordered images with large baseline are not handled.

4. SfM with RS cameras may easily fail into the degeneracies pointed out in [START_REF] Albl | Degeneracies in rolling shutter sfm[END_REF]. The solutions proposed in [Albl et al., 2016b, Ito and Okatani, ] impose a filming style (different readout directions) that can not be achieved in practical applications.

Objectives

In summary, although recently, many methods have been designed to fit RS camera applications, 3D vision with RS currently lacks strong theoretical understanding. 3D reconstruction with RS cameras undergoing general motion and observing general scenes remains an open and challenging problem. A new robust and stable solution to solve RS SfM with unordered images and without overly restrictive assumptions on camera motion, readout direction or projection model is still absent from the literature. Thus, the goal of this thesis is to propose a general framework for modelling and solving 3D reconstruction with RS cameras. Our approach consists in addressing each sub-task of the SfM pipe-line (namely feature selection and matching, monocular pose and relative pose) and proposing improvements. It is now clear that the general RS SfM is not sufficiently constrained, and thus can not be solved efficiently without any prior. Nevertheless, all the proposed methods are based on constraints that are feasible and that are usually used in classical computer vision applications. Beside the theoretical contribution, this work aims to be a step in the potential widespread deployment of 3D vision with RS imaging systems.

Contribution

As shown in Fig. 1.4, this thesis has six main contributions:

A Robust Method for Strong Rolling Shutter Effects Correction Using Lines with

Automatic Feature Selection. We present a novel RS correction method which uses line features. Unlike existing methods, which uses iterative solutions and make Manhattan World (MW) assumption, our method R4C computes linearly the camera instantaneous-motion using few image features. Besides, the method was integrated in a RANSAC-like framework which enables us to detect curves that correspond to actual 3D straight lines and reject outlier curves making image correction more robust and fully automated.

2. RS Bundle Adjustment (RSBA) Revisited. [START_REF] Albl | Degeneracies in rolling shutter sfm[END_REF]] investigated mechanism of planar degeneracy which often raised during RSBA using measurementsbased projection. In contrast, we propose a novel camera-based RS projection algorithm, and incorporate it into RSBA to calculate reprojection errors. We found out that this camera-based RS BA (C-RSBA) makes SfM survive degenerate solutions that occur with common and natural capture style compared to existing works. Thus, without constrains on camera motions e.g. perpendicular read-out directions among RS views [START_REF] Albl | Degeneracies in rolling shutter sfm[END_REF], C-RSBA can also successfully achieve accurate structure and motion computation.

3. Robustified SfM with Rolling-Shutter Camera Using Straightness Constraint. We propose a 3-steps approach for RSSfM problem using the proposed single RS image correction method and the camera-based RSBA. We show that the combination of these two methods enables us to achieve high accuracy 3D reconstruction basing on large dataset experiments with both synthetic and real scenes.

4. Rolling Shutter Homography and its Applications. We investigate the computation of the homography matrix based on correspondences from an RS pair. We show that at least 36 correspondences are needed in theory to compute the homography matrix linearly, and then we derive a practical method which works with 13 correspondences. In addition, we present two essential applications in computer vision that use RS homography: 1) Plane-based RS relative pose estimation and 2) RS image stitching.

Rolling Shutter Pose and Instantaneous-motion Estimation using Shape-from-Template.

The main idea consists in considering that RS distortions due to camera instantaneousmotion during image acquisition can be interpreted as virtual deformations of a template captured by a GS camera. First, the virtual deformations are recovered Chapter 2

Chapter 3

Chapter 4

Chapter 5

Chapter 6

 Straightness constrain [START_REF] Rengarajan | From bows to arrows: Rolling shutter rectification of urban scenes[END_REF]]  CNN method [START_REF] Rengarajan | Unrolling the shutter: Cnn to correct motion distortions[END_REF]]  Vanishing constrain [Purkait et al., 2017] RS correction RS pose estimation  R6P + Measurement-based RSBA [START_REF] Albl | Degeneracies in rolling shutter sfm[END_REF] RSSfM Robustified line-based RS correction with automatic feature selection

Absolute pose

 R6P [START_REF] Albl | R6p-rolling shutter absolute camera pose[END_REF] Relative pose  RS epipolar geometry [Dai et al., 2016] State-of-the-art basing on local differential constraints thanks to Shape-from-Template (SfT) technique. Then, the camera pose and instantaneous-motion are computed by registering the deformed scene on the original template. This 3D-3D registration involves a 3D cost function based on the Euclidean point distance, more physically meaningful than the re-projection error or the algebraic distance based cost functions used in previous work.

6. Solving Rolling Shutter SfM Using Non-Rigid SfM. We propose a solution to the SfM problem for RS images (RSSfM) using an analogy with Non-Rigid SfM (NRSfM).

We first show that, to a certain extent, images of a rigid surface acquired by a moving RS camera can be interpreted as images of a virtually deformed surface taken by a GS camera. We then propose the following two-step method for at least three RS images of an unknown scene. The first step reconstructs virtual deformation by means of NRSfM by relaxing the RS constraint. The second step retrieves the actual structure, camera pose and instantaneous-motion by reintroducing the RS constraint. The proposed method handles most of the common degenerate configurations of RSSfM and outperforms existing methods in accuracy and stability.

Thesis Organization

We have divided this thesis into 7 chapters:

• Chapter. 2: Background theory and mathematical preliminaries.

• Chapter. 3: Contributions to RS correction and the 3-steps RSSfM method.

• Chapter. 4: Contributions to RS bundle adjustment.

• Chapter. 5: Contributions to RS homography.

• Chapter. 6: Contributions to RS pose estimation and RSSfM using NRSfM

• Chapter. 7: Conclusions and perspectives for future work.

Chapter 2

Background and Previous Work

In this chapter, we first introduce the classical Global Shutter (GS) model and three famous 3D computer vision problems which are addressed in this thesis. We will then discuss Rolling Shutter (RS) model and give a brief overview of exiting methods that addressed RS 3D vision problems. A digital camera captures light rays from a 3D scene and provides a digital image under the form of a pixel array. It is constituted of two parts: an optical lens that focuses the light rays and a photosensitive retina which converts the light into electrical charges, then into digital values that represent RGB or gray level data (Fig. 2.1).

Image Formation

A Little Electronics

The Retina

The retina, is the part of the camera that converts the light (namely the number of photons that cross lens and fall in the same point) into an electrical charge which is digitized and stored.

Historically, image data was created by a chemical reaction on a thin film behind the lens. The time during which the sensor is exposed to light determines the amount of light that is stored, and therefore the value of the pixels. A mechanical shutter was then used to allow exposure for only a definite time.

CCD vs CMOS

In digital cameras, the film has been replaced by a panel of sensors consisting of electronic components. CCD (charge coupled device) and CMOS (complementary metal oxide semiconductor) image sensors are two different technologies for capturing digital images. Each has unique strengths and weaknesses giving advantages in different applications. In a CCD technology, charge is transferred using few output nodes. All of the retina surface serves to light capture providing high image uniformity. The advantage of CCDs are lower readout noise, no fixed pattern noise, and low on-chip power dissipation. But on the other side, they require high charge transfer efficiency, complex and large controlling units which increases the device size and are high power consuming.

In a CMOS sensor, each pixel has its own conversion circuit so that the chip outputs digital bits. The design complexity reduces the area devoted to light capture and image uniformity is lower. Inversely, image data transfer is massively parallel, allowing high speed imaging and on-chip image processing.

After CCD domination in the 1970s, due to superior images, there was a renewed interest on CMOS based on lowered power consumption, camera-on-a-chip integration, lowered fabrication costs and high image quality since the 1990s.

Global Shutter vs Rolling Shutter

Exposure time is no longer controlled by a mechanical obturator but rather by an electronic shutter. This led to two shutter modes.

Global Shutter: With a GS, all existing information is first removed from pixels. The pixels are then electronically allowed together to receive the light (exposure phase). At the end of the exposure time, the charges are recorded simultaneously into an area which is insensitive to light. This information is then converted in gray levels by CMOS sensors and transferred. The current CMOS sensors have become so fast that pixel information is transferred simultaneously in series on up to 24 cables, which is an extreme challenge for the following circuits (FPGA, ASIC, and USB or Ethernet chips)1 . As shown in Fig. 2.2, all pixels are simultaneously exposed to light in a GS camera. This exposure mechanism is installed in the majority of CCD sensors. The ability of simultaneously controlling all pixels allows to capture a true snapshot of the scene regardless of the camera instantaneous-motion.

Rolling Shutter:

The current trend is to get more and more pixels on a constantly smaller surface. This is an extreme challenge and requires a pixel to house many components. To achieve even smaller pixels (for example for smart-phones with mega-pixel resolution), the pixel must fit in the 1 µm range. This forces you to drop components, such as the buffer in the pixel. A global shooting at a specific moment is no longer possible with a simple chip. The solution is to determine the end of exposure by reading the information directly. Since the lines are transmitted one after the other, this is a rolling recording, hence the rolling shutter designation2 . As shown in Fig. 2.3, the RS slit slides over the sensor exposing each scanline sequentially (commonly from the top to the bottom of the image).

Global Shutter vs Rolling Shutter: Images taken with a GS camera are free from any artifacts generated by the motion, because they are snapshots. A static RS camera filming a static scene equals to a GS one since all the scanlines exposure are with the same pose. However, images captured by moving RS cameras produce distortions (e.g. wobble, skew).

By dropping the buffer image, quality is improved. In the GS case, at the end of the exposure time, the value relative to the brightness is "saved by elimination" in a memory cell. Because the last line expects the total duration of a frame for the final extraction this information can be altered by temperature variation over time. The black level and the digital noise are increased. On the other hand, a RS sensor directly converts the brightness, without this intermediate step.

A GS sensor can produce annoying ghosting images when shooting in bright sunlight with a lot of light and a very short exposure time. Buffer information is also not exposed directly to light after shooting. However ghost images appear due to the displacement of the object once the exposure time ended. A RS sensor does not have this feature.

Camera Geometrical Modelling

Pinhole Model

The optical part of this image formation process can be modelled geometrically using the very well-known pinhole model. It describes how a 3D point Q i = [X i , Y i , Z i ] defined in a camera coordinate systems first projects onto the image plane as image point q i , then transforms into the image space as an image measurement [START_REF] Hartley | Multiple view geometry in computer vision[END_REF]:

m i = [u i , v i ] [
s i m i 1 = s i Kq i = KQ i (2.1)
where s i ∈ R is a scale factor and K is a 3 × 3 intrinsic parameter matrix which is usually denoted as:

K =   f x 0 c x 0 f y c y 0 0 1   (2.2)
where c x and c y define the centre of image. f x and f y are camera's focal length. If the aspect ratio of the sensor's pixel is squared, then f x = f y .

Camera Pose

As shown in Fig. 2.4, assuming that a GS camera is with a pose [R|t], the rotation R ∈ SO 3 and the translation t ∈ R 3 bring a 3D point P i from the world coordinate system to the camera coordinate system as Q i = RP i + t. Thus, Eq. (2.1) becomes:

s i m i 1 = K R t( P i 1 (2.3)
Note that scale s i is related to the depth of P i . Thus, Eq. ( 2.3) can be rewritten as:

m i = Π GS (KQ i ) = Π GS (K R t P i 1 ) with Π GS ([X Y Z] ) = 1 Z [X Y]
(2.4)

Π GS is the GS projection operator.

Camera pose estimation (PnP) is the problem of calculating the pose [R|t] of a calibrated camera from n 3D-2D correspondences. Camera pose estimation is important and extensively used in Simultaneous Localization And Mapping (SLAM) for robotics, object or camera localization and Augmented Reality (AR).

Relative Pose

The aim of relative pose estimation is to recover the rotation and translation between two cameras. It is of eminent importance in many computer vision applications such as structure-from-motion (SfM), visual odometry (VO) and SLAM. Without losing in generality, we assume two cameras are with poses [I|0] and [R|t] respectively. In existing works, two methods are commonly used to solve this problem (estimating R and t) by using a set of correspondences between two views, namely epipolar geometry and homography.

Epipolar geometry.

Each point correspondence m i ↔ m i holds [START_REF] Hartley | Multiple view geometry in computer vision[END_REF]:

m i 1 F m i 1 = 0 (2.5)
where F is the fundamental matrix. 8pt method [Hartley, 1995] and 5pt method [START_REF] Li | Five-point motion estimation made easy[END_REF]] can be used to estimate F. If both the cameras are calibrated, one can calculate the 3 × 3 essential matrix which involves only motion parameters by using:

E = K FK = [t] × R (2.6)
Eq. (2.6) can be written::

q i E q i = 0 with K -1 m i 1 = q i (2.7)
Once E is obtained, we can decompose it into camera relative pose R and t by using singular value decomposition (SVD) [START_REF] Hartley | Multiple view geometry in computer vision[END_REF].

Feature extraction

Homography

If all the 3D points {P i } locate in a plane, each point correspondence holds:

s i m i = H GS m i with H GS = K (R 0 - t 0 n d )K -1 (2.8)
where H GS is the 3 × 3 GS homography matrix, α i is a scale factor that depends on the depth of P i in each camera. n is the normal vector of the observed plane and d is the distance from the first camera to the plane under the constraint n P i + d = 0. H is usually computed using the Direct Linear Transform algorithm (DLT) with at least four point correspondences. If the two cameras are calibrated, H GS can be decomposed into R and t using SVD [Ma et al., 2012, Malis and[START_REF] Malis | [END_REF].

Structure from Motion

Given a set of images, the task of structure-from-motion (SfM) is to compute the camera pose and the scene's 3D structure simultaneously. We review the procedure a classical SfM pipeline in the following:

Problem setting: A group of 3D points {P i } with i = 1 . . . n viewed by m cameras with pose [R j |t j ]. Let m j i
be the coordinates of the projection of the i th 3D point onto the j th camera. The SfM problem described as follows: given the group of pixel coordinates {m i }, find the corresponding set of camera pose [R j |t j ] and the scene structure {P i } such that

m j i 1 K i R j t j P i 1 (2.9)
where a collection P i , [R j |t j ], m j i holds Eq. (2.9) is called a configuration. Thus, we say that configuration P i , [R j |t j ], m j i explains images m j i .

SfM pipeline:

As shown in Fig. 2.5, a basic SfM pipeline has five steps:

• Step 1: Keypoint Extraction. Extracting keypoints from the images. Different features detectors and descriptors exit. SURF points [START_REF] Bay | Surf: Speeded up robust features[END_REF] were used in the experiments described in this manuscript.

•

Step 2: Matching. Image point pairs are obtained by matching the feature descriptors. Then the outliers of matching point can be rejected by a geometric verification process such as Random sample consensus (RANSAC) with epipolar constraint [START_REF] Hartley | Multiple view geometry in computer vision[END_REF]].

•

Step 3: Tracking. We use 2D trackers to record the visibilities of each 3D point over multiple images and its correspondence projection.

•

Step 4: Pose estimation. Commonly, two or three views are used to initialize 3D structure and relative pose between the camera using epipolar geometry [START_REF] Hartley | Multiple view geometry in computer vision[END_REF]. Then additional views are added incrementally to expand the existing reconstruction using relative pose estimation or absolute pose estimation [START_REF] Gao | Complete solution classification for the perspective-three-point problem[END_REF]].

•

Step 5: Bundle adjustment. Typically, every time a new image is added, we will perform a non-linear optimization of the model called bundle adjustment, to refine all unknown parameters P i and [R j |t j ].

Actually, this description is a very summarized representation. In practice many additional tasks such as loop closing and scale factor drift handling have to be implemented to make the SfM pipeline work in realistic applications (for example for large scale environments). The input image set of SfM can categorized in two types: 1) Ordered image set. This commonly can be extracted from a video. However, processing a video sequence frame by frame is with a heavy computational load and time-consuming. 2) Unordered image set. This is a more general but also more challenging case for SfM since building the correct corresponding matches is difficult. Recently, large scale SfM with unordered image set have been reported in [START_REF] Agarwal | Building rome in a day[END_REF], Heinly et al., 2015]. Unordered image sets can also come from a network composed of multiple cameras.

Bundle Adjustment

We commonly perform a GS Bundle Adjustment (BA) as the final step in a SfM pipeline. Given an initial set of 3D points P i and camera poses [R j |t j ] and 2D corresponding image features measurements m j i , BA aims to find the best 3D structure and camera poses that minimize the sum of squares of reprojection errors as follow:

{P * i } , [R j * |t j * ] = arg min m ∑ j=1 n ∑ i=1 V j i e j i 2 with e j i = mj i -Π GS (K j R j t j P i 1 ) (

Degeneracies

Once images {m i } can be explained by at least two configurations that are not equivalent, we say that these images are critical. Thus, such cases which leads to ambiguities in 3D reconstruction, are termed degenerate. Degeneracies in SfM with pinhole cameras have been studied for calibrated two views [Maybank, 2012], multiple views [START_REF] Hartley | Critical configurations for projective reconstruction from multiple views[END_REF] and also for uncalibrated sequences [START_REF] Torr | The problem of degeneracy in structure and motion recovery from uncalibrated image sequences[END_REF].

Computer Vision with RS Cameras

Rolling Shutter Definition

The majority of CMOS sensors are inherently with RS mechanism. Therefore, RS is an important topic to study in computer vision, wherein the default camera model is GS.

As shown in Fig. 2.3, the RS slit slides over the sensor exposing each scanline sequentially (commonly from the top to the bottom of the image). Images captured by moving RS cameras produce distortions (e.g. wobble, skew), which defeat the classical GS geometric models in 3D computer vision. Thus, new methods adapted to RS cameras are strongly desired.

RS Projection Model

As shown in Fig. 2.6, with a moving RS camera, each row will be captured in turn and thus with a different pose during frame exposure, yielding a new projection operator Π RS . Thus, Eq. ( 2.4) becomes:

m i = Π RS (KQ i ) = Π GS (KQ RS i ) = Π GS (K[R(v i ) t(v i )]P i ) (2.11)
where R(v i ) and t(v i ) define the camera pose when the image row of index v i is acquired. Therefore, a static 3D point P i in world coordinates is transformed into Q RS i , instead of Q i , in camera coordinates.

RS Instantaneous-motion Models

Instantaneous camera motion: During the acquisition of a single shot, the rotation R(v i ) and the translation t(v i ) of an RS camera are functions of row index v i . Note that this motion during the image acquisition is different from the term 'motion' in "structure from motion (SfM)", which refers to the relative pose between two images (views). Many naming have been used in previous works such as kinematic model [START_REF] Ait-Aider | Simultaneous object pose and velocity computation using a single view from a rolling shutter camera[END_REF], RS model [START_REF] Albl | Degeneracies in rolling shutter sfm[END_REF], RS camera model [START_REF] Dai | Rolling shutter camera relative pose: generalized epipolar geometry[END_REF] or camera motion [START_REF] Rengarajan | From bows to arrows: Rolling shutter rectification of urban scenes[END_REF], Purkait et al., 2017]. For the consistency and readability, we name the camera motion during the image acquisition as instantaneous-motion in this manuscript, and keep denote the camera relative pose as motion. Although the term "instantaneous" is not entirely appropriate, it quite correctly reflects the fact that the exposure time is of course very short compared to the unpredictable changes in camera trajectory.

Using the RS projection model with a new pose parameters for each feature as described by section 2.1.1 would lead to over parametrized systems whilst overdetermined systems are required to solve most of computer vision problems. Independently estimating of the pose of each row is an ill-posed problem. Therefore, it seems clear that there is a need for a more minimal parametrization that describes the relationship between the poses of image features.

In this section, we introduce various RS instantaneous-motion models. Since the image acquisition time is short (usually a fraction of a second), it is common to assume that the instantaneous-motion of an RS camera is smooth. Note that this assumption is on the camera instantaneous-motion only, without constraint on the motion (relative pose) between views.

We will present the different models of instantaneous movement used in RS methods. We will then discuss the relevance and applicability of each model depending on the application context.

Constant Velocity Motion

Constant velocity motion assumes that the camera is with constant direction and magnitude of translational and rotational velocity during the acquisition. Now, we introduce different parametrizations that can then be used for the constant translational and rotational velocity.

Constant translational velocity:

The constant translational motion assumes a linearized translational motion with constant velocity as:

t(v i ) = t 0 + dv i (2.12)
where t 0 is the translation of first row while d = [d x , d y , d z ] is the translational velocity.

Constant rotational velocity: Three main parametrizations have been used for the constant rotational velocity in the existing works.

1. Rodrigues' Formula. Rodrigues formula is to define a rotation matrix. In RS case, we assume that the rotation is with instantaneous rotational speed ω around an instantaneous axis of unit vector a = [a x , a y , a z ] . Then the rotations during the acquisition are obtained as follows [START_REF] Ait-Aider | Simultaneous object pose and velocity computation using a single view from a rolling shutter camera[END_REF], Ait-Aider et al., 2007]:

R(v i ) = (aa (1 -cos(ωv i )) + I cos(ωv i ) + [a] × sin(ωv i ))R 0 (2.13)
where t 0 is the translation of first row, [a] × is the antisymetric matrix of a and I is a 3 × 3 identity matrix.

2. Linearized model. Most of rotation parametrizations leads to highly nonlinear equations which can be solved by nonlinear optimization techniques for the last refinement steps. However, in order to reduce the complexity of the model, we can use a linearization of the rotation matrices. Assuming that the rotation during the acquisition is small, the first order Taylor expansion of Eq. (2.13) gives a polynomial approximation of the rotations as:

R(v i ) = (I + [ω] × v i )R 0 with ω = ωa ω = ω [ω] × =   0 -ωz ω y ω z 0 -ω x -ω y ω x 0   (2.14)
where ω = [ω x , ω y , ω z ] is the rotational velocity vector. Such instantaneousmotion model with the RS rotation linearized, was used in [START_REF] Magerand | Global optimization of object pose and motion from a single rolling shutter image with automatic 2d-3d matching[END_REF], Dai et al., 2016[START_REF] Albl | Degeneracies in rolling shutter sfm[END_REF], Magerand et al., 2012, Lao et al., 2018a[START_REF] Lao | Rolling shutter pose and ego-motion estimation using shape-from-template[END_REF].

3. Double linearized model. Eq. (2.14) has been further linearized in [START_REF] Albl | R6p-rolling shutter absolute camera pose[END_REF], Albl et al., 2016a] using the first order Taylor expansion as:

R(v i ) = (I + [ω] × v i )(I + [r] × ) (2.15)
where r = [r x , r y , r z ] is the Euler angles component about axes x, y, z. This approximation requires the initial global rotation R 0 is small.

Constant Acceleration Motion

Constant acceleration motion relaxes the constant velocity assumption. Specifically, it assumes constant direction of translational and rotational velocity, but allows its magnitude to change gradually. Different parametrizations of the constant translational and rotational acceleration can be used.

Constant translational acceleration:

The constant translational acceleration motion has been considered first time in [START_REF] Zhuang | Rolling-shutteraware differential sfm and image rectification[END_REF] to enhance the generality of the RS instantaneous-motion model as:

t(v i ) = t 0 + dv i + 1 2 av i 2 (2.16)
where a is the acceleration.

Cayley transform:

Cayley transform [Golub and Van Loan, 2012] was used to express the accelerated rotations [START_REF] Rengarajan | From bows to arrows: Rolling shutter rectification of urban scenes[END_REF], Purkait et al., 2017]. We denote the Rodrigues parameterization [Morawiec, 2003] of each row as r A = [r x , r y , r z ] which is defined by:

   r x = α + a 1 t + • • • + a ṅt ṅ r y = β + b 1 t + • • • + b ṅt ṅ r z = γ + c 1 t + • • • + c ṅt ṅ with a i , b i beeing real coefficients and t = v i -1 H
(2.17)

Then the rotation matrix can be calculated by using Cayley transform as follows:

R(r A ) = 1 Z   1 + r x 2 -r y 2 -r z 2 2r x r y -2r z 2r y + 2r x r z 2r z + 2r x r y 1 -r x 2 + r y 2 -r z 2 2r y r z -2r x 2r x r z -2r y 2r y r z + 2r x 1 -r x 2 -r y 2 + r z 2   with Z = 1 + r x 2 + r y 2 + r z 2 (2.18)
Therefore, estimation of the instantaneous rotation is equivalent to the estimation of 3( ṅ + 1) motion parameters [α, a 1 , . . . , a ṅ; β, b 1 , . . . , b ṅ; γ, c 1 , . . . , c ṅ; ]. For instance, ṅ = 2 are used in [START_REF] Rengarajan | From bows to arrows: Rolling shutter rectification of urban scenes[END_REF], Purkait et al., 2017].

Interpolated Poses

Instead of constraining the velocity during the acquisition period, one can also constrain the instantaneous-motion by interpolating the poses between two successive frames. A very popular interpolation method for rotations is SLERP [Shoemake, 1985] which has been used for RS images in [START_REF] Hedborg | Rolling shutter bundle adjustment[END_REF]. Assuming two successive frames with rotations R 1 and R 2 respectively, the rotations of rows v i in 1 st image can be estimated as follows:

R(v i ) = R 1 sin(Ω -tΩ) sin(Ω) -R 2 sin(tΩ) sin(Ω) with Ω = arccos(R 1 R 2 ) t = v i -1 H (2.19)
where H is the number of rows in the first image.

Non-general-motion Models

Models in this category restrict the instantaneous-motion (e.g. ignore either translational or rotational velocity) to obtain a simplified model for specific applications. We introduce three such models that were used in existing works.

(1) Pure translation model. Authors in [START_REF]Rolling Shutter Stereo[END_REF], Saurer et al., 2016] consider pure translation with constant translational velocity defined in Eq. (2.12). However, this assumption approximately holds only for limited scenarios such as car driving straightly.

(2) Pure rotation model. This model is based on the assumption that the rotations play a major role for RS effect in images captured by hand-held cameras [START_REF] Ringaby | Efficient video rectification and stabilisation for cell-phones[END_REF] and even by vehicle cameras [START_REF] Duchamp | A rolling shutter compliant method for localisation and reconstruction[END_REF]. Thus, many previous works use pure rotation instantaneous-motion model and do not consider the translational velocity [START_REF] Rengarajan | From bows to arrows: Rolling shutter rectification of urban scenes[END_REF], Ito and Okatani, , Purkait et al., 2017, Lao and Ait-Aider, 2018].

(3) Ackermann motion. [Purkait and Zach, 2017] use the conventional Ackermann steering principle, which models a four wheels vehicle rolling around a common point during a turn, to constraint the RS instantaneous-motion. This principle holds for any vehicle which ensures all the wheels exhibit a rolling motion.

Discussion

It is common that the higher order of the instantaneous-motion model leads to more realistic description of the camera motion during image acquisition. However, at the same time, despite the advent of modern new polynomial equation solvers [START_REF] Henrion | [END_REF]Lasserre, 2003, Kukelova et al., 2008], solving such model is also time consuming and unstable (local minimas when performing a non-linear optimization and numerically unstable when solving a polynomial system). In this manuscript, we use the linearized model described by Eq. (2.12) and (2.14) as follows:

R(v i ) = (I + [ω] × v i )R 0 t v i = t 0 + dv i (2.20)
because we consider that it is a good compromise between accuracy and complexity as it has been justified in [START_REF] Magerand | Global optimization of object pose and motion from a single rolling shutter image with automatic 2d-3d matching[END_REF]. Note that both translational and rotational velocities express the displacements per row instead of displacements per time unit (e.g. second or minute) [START_REF] Ait-Aider | Simultaneous object pose and velocity computation using a single view from a rolling shutter camera[END_REF]. The transformation between these two expressions of velocities requires the exposure time per row, which can be calibrated by imaging a flashing light source with known frequency [START_REF] Meingast | Geometric models of rolling-shutter cameras[END_REF].

Problem Statements and Previous Works

After an analysis of the state of the art in 3D vision with RS cameras, we identified several themes for which improvements could be made both in terms of theoretical formalization and in terms of proposing pragmatic and practical solutions. We address four important but challenging problems in RS 3D vision:

RS Correction

Definition: By given single or multiple distorted RS images, the aim of RS correction is to remove the distortions and recover the corresponding undistorted GS images.

Previous works:

The state-of-the-art works for RS image rectification can be divided into three main classes:

1. Video-based methods: Methods of [START_REF] Liang | Analysis and compensation of rolling shutter effect[END_REF], Forssén and Ringaby, 2010, Kim et al., 2011,Grundmann et al., 2012,Zhuang et al., 2017] try to recover the geometry between RS frames first, then to compensate RS effects by scanline realignment or RS-aware warping.

Previous works:

The existing works for RS-PEnP problem can be divided into two main classes:

1. Non-linear optimization methods: In [START_REF] Ait-Aider | Simultaneous object pose and velocity computation using a single view from a rolling shutter camera[END_REF] authors first solved the RS-PEnP problem using a non-linear optimization with the instantaneous-motion assumption modelling by Rodrigues' Formula and constant translation velocity. This method had been further extended to use lines instead of point features in [START_REF] Ait-Aider | Kinematics from lines in a single rolling shutter image[END_REF]. [START_REF] Magerand | Global optimization of object pose and motion from a single rolling shutter image with automatic 2d-3d matching[END_REF] [START_REF] Albl | R6p-rolling shutter absolute camera pose[END_REF]. Albl et al. [Albl et al., 2016a] also propose another minimal solver, which requires at least 5 3D-2D matches but requires to the assistance of inertial measurement units (IMUs).

RS Relative Pose Estimation

Definition: The goal of RS relative pose estimation is to estimate the relative pose (rotation and translation) between two RS images and also to calculate the instantaneousmotions of both cameras by using feature correspondences.

Previous works: [START_REF] Feldman | On the epipolar geometry of the crossed-slits projection[END_REF] is the first work develop the epipolar geometry of the translation-only crossed-slits cameras which related to RS projection model. [START_REF] Dai | Rolling shutter camera relative pose: generalized epipolar geometry[END_REF] is the only work that investigate the epipolar geometry of RS cameras and provide solutions to the RS relative pose problem. The authors derived the 5 × 5 and 7 × 7 essential matrices for pure translation and uniform linearized model respectively. They also introduce 20pt and 44pt linear solvers to estimate the two types of RS essential matrices, which then are needed to be refined by nonlinear solvers by using Sampson error. Linear algorithms for the extraction of the relative pose and instantaneous-motion from these matrices are also presented.

RS structure from Motion

Definition: The goal of RS structure from motion (RSSfM) is to reconstruct the 3D structure and to estimate the camera poses as well as the camera instantaneous-motions during each of the image readouts.

Previous works:

1. RSSfM using video sequence: The methods in [START_REF] Hedborg | Structure and motion estimation from rolling shutter video[END_REF] use an RS video sequence to solve RSSfM by assuming smooth camera motion between every consecutive frames. [START_REF] Im | Accurate 3d reconstruction from small motion clip for rolling shutter cameras[END_REF] proposes a dense 3D reconstruction method from narrow-baseline RS image sequences.

Optical flow based RSSfM:

In [START_REF] Zhuang | Rolling-shutteraware differential sfm and image rectification[END_REF], 8pt and 9pt linear solvers were developed to recover the relative pose of a RS camera that undergoes constant velocity and acceleration motion respectively.

3. RSSfM with additional sensors: [START_REF] Klingner | Street view motion-from-structure-from-motion[END_REF] proposes a vehicle-based RSSfM method for large scale scene by exploiting a good relative pose prior using additional sensors such as GPS and IMU.

4. Stereo RSSfM: [START_REF] Ait-Aider | Structure and kinematics triangulation with a rolling shutter stereo rig[END_REF] first studied the calibrated RS stereo system, and presented a method for object structure and kinematics estimation by using iterative optimization. [START_REF]Rolling Shutter Stereo[END_REF] addressed the stereo RSSfM under pure translation instantaneous-motion model.

Unordered RSSfM:

The methods in [Ito and Okatani, ] attempt to solve RSSfM by establishing an equivalence with self-calibrated SfM based on the pure rotation instantaneous-motion model and affine camera assumption. [START_REF] Albl | Degeneracies in rolling shutter sfm[END_REF]] also addressed the unordered RSSM problem and pointed out common degeneracies of RSSfM.

Chapter 3

RS Correction and SfM using Straightness Constraint

Introduction

Straight lines frequently appear in man-made environments such as urban or indoor scenes. Furthermore, using straight lines as features offers several advantages such as detection accuracy and the possibility to handle partial occlusions. Thus, line features have been used for various GS vision application such as pose estimation, SfM, SLAM, visual odometry (VO). However, when using RS cameras, straight segments may be rendered as curves under different kinematic models. Thus, classical GS based vision methods using lines suffers from RS effect. To the best of our knowledge, except in [START_REF] Ait-Aider | Kinematics from lines in a single rolling shutter image[END_REF], Rengarajan et al., 2016, Purkait et al., 2017], line features have never been used for RS vision applications.

In this section, we present two methods both using a set of image curves, basing on the knowledge that they correspond to 3D straight lines. Namely, a robust method which compensates RS distortions in a single image, and a robustified 3-step RSSfM method (Fig. 3.1). Unlike in existing work, no a priori knowledge about the line directions (e.g. Manhattan World assumption) is required.

Chapter outline. The rest of this chapter organized as:

• First, we show that the parameterization of the projection of a 3D straight line leads to a first (section 3.3.2), second (section 3.3.4.1 and 3.3.4.2) or third degree (section 3.3.3) polynomial depending on the kinematic model considered during image acquisition (table . 3.1).

• Second we propose a theoretical linear rotational velocity extraction algorithm using at least 16 image curves (section 3.4.1), then we derive a more practical version using 4 curves (section 3.4.3). We also analyse the degenerate cases in the rotational velocity extraction method (section 3.4.4).

• Moreover, we propose a RANSAC-like strategy to select image curves which really correspond to 3D straight lines and reject those corresponding to actual curves in 3D world (section 3.5.0.2). This automatic feature selection is crucial because it makes the method robust to noise and also fully automated. Then the RS image can be finally corrected by compensating the estimated camera instantaneous-motion.

• Finally we propose a 3-step RSSfM method (section 3.6). In step one, each image is corrected using lines while rotational speed is computed. In step two, the translational speed as well as the motion between cameras is recovered. At the end,

Multiple RS views with distortions

Curves detection and fitting

Step all the parameters are refined using a new BA technique which enables to avoid degeneracy reported in the state-of-the-art (section 3.6.3).

• A comparative experimental study with both synthetic and real data from famous benchmarks shows that the proposed method outperforms all the existing techniques from the state-of-the-art for both RS correction and RSSfM problem (section 3.7).

Related Work and Motivation

Related Work for RS correction

The related works for RS correction are discussed in section 2.4.1 suffer from the following disadvantages:

(1) Simplified instantaneous-motion model: Methods of [START_REF] Rengarajan | From bows to arrows: Rolling shutter rectification of urban scenes[END_REF], Rengarajan et al., 2017] correct RS by making the output image visually pleasant for human without considering correctness of projection geometry. Thus, camera x and y axis instantaneous-rotations are neglected which may lead to geometrical inconsistencies.

(2) Manhattan world (MW) assumption: Methods of [START_REF] Rengarajan | From bows to arrows: Rolling shutter rectification of urban scenes[END_REF], Purkait et al., 2017] require that the MW assumption is valid. This requires that the images feature at least two orthogonal vanishing directions. Beside the difficulty to find such image features, nonorthogonal 3D lines and 3D curves are also common in urban area. Since both methods lack of outlier filter process, strong deformations occur in the final correction (Fig. 3.2(b)(c)).

(3) Time-consuming: Nonlinear iterative solutions are used in [START_REF] Rengarajan | From bows to arrows: Rolling shutter rectification of urban scenes[END_REF], Purkait et al., 2017] which may be time-consuming and suffer from the risk to fall into local minima due to the absence of a good initial guess estimation process.

In order to overcome disadvantages of the techniques from the state-of-the art, we present a method which enables us to compensate RS distortions using a set of image curves which correspond to 3D straight lines with free unknown directions. The method estimates linearly the camera instantaneous-motion and then compensates image distortions according to the computed rotation. The presence of outlier curves which do not correspond to actual 3D straight lines is also addressed (Fig. 3.2(e)(f)).

Related Work for RSSfM

Due to the complexity and the high non-linearity of RS perspective projection model, strong assumptions which usually do not hold in practice, have been made in existing literatures in order to solve the SfM problem with RS cameras.

Smooth motion assumption. Some approaches require continuity and "smoothing" of the movement during the shooting but also between the views thus imposing an acquisition at very high frequency [START_REF] Hedborg | Rolling shutter bundle adjustment[END_REF], Kim et al., 2016] which makes both data transferring and processing very time and memory consuming without mentioning the case where different cameras with wide baselines are used. Other approaches consider simplified movements such as linear motion (pure translation) [START_REF]Rolling Shutter Stereo[END_REF], pure rotation [Ito and Okatani, ] or small angular velocity [START_REF] Dai | Rolling shutter camera relative pose: generalized epipolar geometry[END_REF]. We believe that a method based on a more general kinematic model and which handles wide baselines would give significant improvement not only in terms of accuracy of pose and motion estimation, but also in terms of automatic data matching performances (namely outliers rejection).

Degeneracies in RSSfM.

With numerous parameters and highly non linear projection model, problems of local minima occur more frequently, for instance in bundle adjustment [START_REF] Hedborg | Rolling shutter bundle adjustment[END_REF]. RS degeneracies were firstly reported in [Ait-Aider and Berry, 2009] showing that a linear motion (pure translation) nearly parallel to the baseline gives an infinite number of solutions due to the coupling between shape and motion parameters. [Albl et al., 2016b, Ito and Okatani, ] analyzed the case of planar degeneracy which occurs most often for RS SfM and prove that images captured by cameras having parallel read-out directions is a critical motion sequence (CMS) with specific angularvelocities as degenerate solutions. They both suggested that it can be avoided by using RS images with different readout directions, which is not a convenient solution for practical applications.

RS vision applications using lines. [START_REF] Rengarajan | From bows to arrows: Rolling shutter rectification of urban scenes[END_REF] used line features to estimate instantaneous-motion of cameras by extracting angular velocity from curves with preknowledge of corresponding directions in 3D space. The aim of this work is to rectify the image for better visualization by fitting curves with larger length and specific angle on image assuming a pure rotational motion model and using an iterative optimization of a nonlinear function. Thus, the recovered angular-velocities in this work may be far away from ground-truth as long as the results are visually acceptable, which is not sufficient to be used in RSSfM.

Straight Line Projection with RS

Context. One way to handle problems of degeneracy and local minima mentioned in section. 3.2.2, consists in adding constraints on scene geometry. But the constraint should be convenient and feasible in practical situations. Straight lines can be used to partially constrain the geometry of a scene. Advantages of using line features in computer vision are known very well (vanishing point detection, uncoupling rotation and translation parameters etc.). In the case of a moving RS camera, straight lines do not project as straight lines anymore but as curves whose shape depends from the motion during image scanning. Thus, motion parameters are hiding in the deviation from those curves to a straight line. This is the basis of the 'Straight line have to be straight' principle used in [START_REF] Devernay | Straight lines have to be straight[END_REF] to remove radial distortion effects.

3D Line Representation

In this paper we adopt the convenient formulation used in [START_REF] Schindler | Linebased structure from motion for urban environments[END_REF] and which represents a 3D straight line in R 3 as a tuple L = < R, (a, b)) > ∈ SO 3 × R 2 . L defines an algebraic set which is a 4 dimensional manifold embedded in SO 3 × R 2 with 4 degrees of freedom (DoF) as illustrated in Fig. 3.3. Note that under this parametrization, R ∈ SO 3 but there are just two DoF since we fix the yaw angle as 0. In other word, a general rotation matrix is defined by R general = R z (α)R y (β)R x (γ), however, the R in our parametrization is defined as: R = R y (β)R x (γ).

3D Line Projection with GS Camera

Assuming a calibrated camera, intrinsic matrix K is known. [START_REF] Schindler | Linebased structure from motion for urban environments[END_REF] prove that the projection of a 3D line into a GS camera image can be divided into three main steps:

Transformation into camera coordinate frame: We denote a 3D line in the world coordinate system as < R w , (a w , b w )) > and the transformation between the camera coordinate frame and the world frame as R w c and t w c . The 3D straight line can be expressed in the camera coordinate system as:

R c = R w c R w t c = t x t y t z = (R w ) t w c (a c , b c ) = a w -t x , b w -t y (3.1)
Perspective projection: The direction m cip = m x m y m z of a straight line on the image denoted as m x u + m y v + m z = 0 within a plane at z = 1 in the camera frame can be calculated by the cross product of R z and R c (a c x + b c y):

m cip = a c R c2 -b c R c1 (3.2)
Where R c2 and R c1 are the second and first columns of R c .

Image space projection:

Image lines can be obtained as:

m ci = K -1 m cip . Finally,
we can write a projected 2D line in image as follows:

GS F 1 u + GS F 2 v + GS F 3 = 0 (3.3)

3D Line Projection with Uniform RS Instantaneous-motion Model

Under the more realistic assumption of a uniform motion with both rotational and translational velocities, modelling by linearized instantaneous-motion described by Eq. (2.20), Eq. (3.1) becomes:

R c = ((I + [ω] × v])R c w )) R w t c = t x t y t z = (R w ) (t w c + dv) (a c , b c ) = a w -t x , b w -t y (3.4)
from which we finally obtain a cubic curve:

Uni f F 1 v 3 + Uni f F 2 v 2 u + Uni f F 3 v 2 + Uni f F 4 vu + Uni f F 5 v + Uni f F 6 u + Uni f F 7 = 0 (3.5)
where the seven coefficients are determined by K, 3D line parameters, camera pose and kinematic parameters (d, ω).

Derivation of Eq. (3.5).

We first denote (K ) -1 by using the components of the intrinsic matrix K as follows:

(K ) -1 = f x 0 0 0 f y 0 c x c y 1 (3.6)
Based on Eq. (3.4), in order to make it easier to derived curve expression, we let:

R c = ((I + [ω] × v)R c w ) R w = R w c R w + R w c [ω] × R w v = A + Bv a c = a w -R w1 t w c -R w1 dv = C a -D a b c = b w -R w2 t w c -R w2 dv = C b -D b (3.7)
where, A and B are two 3 × 3 matrices, C a , C b , D a and D b are scalar variables. Thus, the direction vector of straight line m cip are now also determined by row-index v:

   m x cip m y cip m z cip    = L   v 2 v 1   =   L x 2 L x 1 L x 0 L y 2 L y 1 L y 0 L z 2 L z 1 L z 0     v 2 v 1   with L =   D b B 11 -D a B 12 C a B 12 -D a A 12 -C b B 11 + D b A 11 C a A 12 -C b A 11 D b B 21 -D a B 22 C a B 22 -D a A 22 -C b B 21 + D b A 21 C a A 22 -C b A 21 D b B 31 -D a B 32 C a B 32 -D a A 32 -C b B 31 + D b A 31 C a A 32 -C b A 31   (3.8)
where the 3 × 3 auxiliary matrix L consisted by nine variables

L x 0 , L x 1 , L x 2 , L y 0 , L y 1 , L y 2 , L z 0 , L z 1
and L z 2 in order to do further derivations. Now we substitute m cip in Eq. ( 3.3) by Eq. (3.8). We obtain the expression of a cubic curve instead of a straight line as follows:

          f y L y 2 f x L x 2 f y L y 1 + c x L x 2 + c y L y 2 + L z 2 f x L x 1 f y L y 0 + c x L x 1 + c y L y 1 + L z 1 f x L x 0 c x L x 0 + c y L y 0 + L z 0                     v 3 v 2 u v 2 vu v u 1           =            Uni f F 1 Uni f F 2 Uni f F 3 Uni f F 4 Uni f F 5 Uni f F 6 Uni f F 7                      v 3 v 2 u v 2 vu v u 1           = 0 (3.9)
where Eq. (3.9) is equivalent to Eq. (3.5). If we force the translational velocity d and rotational velocity ω to be equal to zero, Eq. (3.9) will collapse into Eq. ( 3.3) as a straight line.

3D Line Projection with Other RS Instantaneous-motion Models

From the uniform model in Eq. (3.5), one can derive two simpler models: linear RS model and rotate-only model which assumes pure translation and pure rotation during image acquisition. By either forcing the linear velocity d or the angular velocity ω to be equal to 0 respectively, one can obtain a hyperbolic curve. The parameterizations of 3D line projection with different RS models are summarized in table . 3.1 and Fig. 3.4.

3D Line Projection with linear RS model

By forcing the rotational velocity ω = 0, Eq. (3.5) becomes:

Camera model Projection equation Curve type Parameters

GS Eq. (3.3) GS F 1 u + GS F 2 v + GS F 3 = 0 Straight line R,t Linear RS Eq. (3.10) Lin F 1 v 2 + Lin F 2 vu + Lin F 3 v+ Hyperbolic R,t,d Proof in section 3.3.4.1 Lin F 4 u + Lin F 5 = 0 curve Rotate-only RS Eq. (3.14) Rot F 1 v 2 + Rot F 2 vu + Rot F 3 v Rot + Hyperbolic R,t,ω Proof in section 3.3.4.2 Rot F 4 u + Rot F 5 = 0 curve Uniform RS Eq. (3.5) Uni f F 1 v 3 + Uni f F 2 v 2 u+ Proof in section 3.3.3 Uni f F 3 v 2 + Uni f F 4 vu+ Cubic curve R,t,d,ω Uni f F 5 v + Uni f F 6 u + Uni f F 7 = 0 Lin F 1 v 2 + Lin F 2 vu + Lin F 3 v + Lin F 4 u + Lin F 5 = 0 (3.10)
where the five coefficients are determined by K, 3D line parameters, camera pose and kinematic parameters (d).

Derivation of Eq. (3.10).

Distinctively, if we assume that the angular velocity ω is equal to zero. Eq. (3.4) becomes:

R c = R c w R w t c = t x t y t z = (R w ) (t w c + dv) (a c , b c ) = a w -t x , b w -t y (3.11)
Thus, the straight line director vector m cip can be expressed as follows:

   m x cip m y cip m z cip    = L v 1 =   L x 1 L x 0 L y 1 L y 0 L z 1 L z 0   v 1 with L =   (R w2 R c22 -R w1 R c12 )d (a w -R w1 t w c )R c12 -(b w -R w2 t w c )R c11 (R w2 R c21 -R w1 R c22 )d (a w -R w1 t w c )R c22 -(b w -R w2 t w c )R c21 (R w2 R c31 -R w1 R c32 )d (a w -R w1 t w c )R c32 -(b w -R w2 t w c )R c31   (3.12)
where the 3 × 2 auxiliary matrix L is consisted by six variables L x 0 , L x 1 , L y 0 , L y 1 , L z 0 and L z 1 . Then we substitute Eq. (3.12) into Eq. (3.3), we obtain a hyperbolic curve as follows:

      f y L y 1 f x L x 1 f y L y 0 + c x L x 1 + c y L y 1 + L z 1 f x L x 0 f x L x 0 + c y L y 0 + L z 0             v 2 vu v u 1       =       Lin F 1 Lin F 2 Lin F 3 Lin F 4 Lin F 5             v 2 vu v u 1       = 0 (3.13)
where Eq. (3.13) is equivalent to Eq. (3.10). If we set the translational velocity d = 0, Eq. (3.13) will collapse into Eq. ( 3.3) as a straight line.

3D Line Projection with pure rotation model

By setting the rotational velocity d = 0, Eq. (3.5) becomes:

Rot F 1 v 2 + Rot F 2 vu + Rot F 3 v + Rot F 4 u + Rot F 5 = 0 (3.14)
where the five coefficients are determined by K, 3D line parameters, camera pose and kinematic parameters (d).

Derivation of Eq. (3.14).

Distinctively, if we assume that the angular velocity d is equal to zero. Eq. (3.4) becomes:

R c = ((I + [ω] × v])R c w )) R w t c = t x t y t z = (R w ) t w c (a c , b c ) = a w -t x , b w -t y (3.15)
Thus, the straight line director vector m cip can be expressed as follows:

   m x cip m y cip m z cip    = L v 1 =   L x 1 L x 0 L y 1 L y 0 L z 1 L z 0   v 1 with L =   a c B 12 -b c B 11 a c A 12 -b c A 11 a c B 22 -b c B 21 a c A 22 -b c A 21 a c B 22 -b c B 31 a c A 32 -b c A 31   and A = R w c R w B = R w c [ω] × R w (3.16)
where A and B are two 3 × 3 auxiliary matrices defined by R c = A + Bv. While the 3 × 2 auxiliary matrix L is consisted by six variables L x 0 , L x 1 , L y 0 , L y 1 , L z 0 and L z 1 . Then we substitute Eq. (3.16) into Eq. ( 3.3), we obtain a hyperbolic curve as follows:

      f y L y 1 f x L x 1 f y L y 0 + c x L x 1 + c y L y 1 + L z 1 f x L x 0 f x L x 0 + c y L y 0 + L z 0             v 2 vu v u 1       =       Rot F 1 Rot F 2 Rot F 3 Rot F 4 Rot F 5             v 2 vu v u 1       = 0 (3.17)
where Eq. (3.17) is equivalent to Eq. (3.14). If we force the translational velocity ω = 0, Eq. (3.17) will collapse into Eq. ( 3.3) as a straight line.

Instantaneous-motion from 2D Curves

In this section, we show how to estimate the instantaneous-motion of the camera by using the coefficients of 2D curves.

Linear 16-curves Solution for Uniform RS Model

We introduce a 16-curves linear solution called R16C to estimate instantaneous-rotation basing on the RS uniform instantaneous-motion model. For a single RS image, if we assume the camera frame as world coordinate system, hence, R c w = I and t c w = 0. Then, based on Eq. (3.5), ω can be expressed according to the seven coefficients of the cubic curves and intrinsic parameters in K:

C 1 • • • C 17 W 1 • • • W 17 T = 0 (3.18)
where C i are 17 known auxiliary variables determined by K and cubic curve coefficients uni f F 1 to uni f F 7 . While W i , i = 1, . . . , 17 are 17 unknown variables consisted by components of ω. Finally, this equation can be solved linearly by SVD with at least 16 detected curves which correspond to 3D straight segments.

Derivation of Eq. (3.18).

Basing on Eq. (3.9). We first denote 3D line structural parameters as

a c R w2 -b c R w1 = [s 1 , s 2 , s 3 ] T , and assume D a R w2 -D b R w1 = [h 1 , h 2 , h 3 ] T . Thus, the 3 × 3 auxiliary matrix L consisted by nine variables L x 0 , L x 1 , L x 2 , L y 0 , L y 1 , L y 2 , L z 0 , L z 1 and L z
2 in Eq. (3.8) can also be denoted as follows:

L =   L x 2 L x 1 L x 0 L y 2 L y 1 L y 0 L z 2 L z 1 L z 0   =   ω z h 2 -ω y h 3 s 3 ω y -s 2 ω z -h 1 s 1 ω x h 3 -ω z h 1 s 1 ω z -s 3 ω x -h 2 s 2 ω y h 1 -ω x h 2 s 2 ω x -s 1 ω y -h 3 s 3   (3.19)
For readability, we denote as F 1 , F 2 , F 3 , F 4 , F 5 , F 6 and F 7 respectively. Thus, for each fitted cubic curve, we obtain a polynomial group with 7 equations:

F Uni 1 , F Uni 2 , F Uni 3 , F Uni 4 , F Uni 5 , F Uni
                     F 1 = f y (ω x h 3 -ω z h 1 ) F 2 = f x (ω z h 2 -ω y h 3 ) F 3 = f y (s 1 ω z -s 3 ω x -h 2 ) + c x F 2 f x + c y F 1 f y + ω y h 1 -ω x h 2 F 4 = f x (s 3 ω y -s 2 ω z -h 1 ) F 5 = f y s 2 + c x F 4 f x + c y (s 1 ω z -s 3 ω x -h 2 ) + s 2 ω x -s 1 ω y -h 3 F 6 = f x s 1 F 7 = c x s 1 + c y s 2 + s 3 (3.20)
The objective is to eliminate h 1 , h 2 , h 3 , s 1 , s 2 and s 3 from the above 7 equations.

we Basing on Eq. (3.3), h 1 , h 2 and h 3 , which contain translational velocity d, can be expressed by using ω and s 1 , s 2 , s 3 and curve coefficients as follows:

(1) Base on the definition of

F 4 = f x (s 3 ω y -s 2 ω z -h 1 )
, we obtain the expression of h 1 as:

h 1 = s 3 ω y -s 2 ω z -F 4 / f x (3.21)
(2) Base on the definition of F 1 = f y (ω x h 3ω z h 1 ) and Eq. (3.21), we the expression of h 3 as:

h 3 = F 1 f y ω x + ω z ω x h 1 = F 1 ω x f y + ω z (s 3 ω y -s 1 ω z ) -F 4 / f x ω x (3.22)
(3) Base on the definition of F 2 = f x (ω z h 2ω y h 3 ) and Eq. (3.21) and (3.22), we the expression of h 2 as:

h 2 = F 2 f x ω z + ω y ω z h 3 = F 2 f x ω z + F 1 ω y f y ω x ω z + ω y ω x h 1 = F 2 f x + ω y F 1 ω x f y + ω z (s 3 ω y -s 1 ω z )-F 4 / f x ω x ω z (3.23)
Then we introduce two new auxiliary variables a and b:

(1) Basing on the definition of 3.20), we assume:

F 3 = f y (s 1 ω z -s 3 ω x -h 2 ) + c x F 2 f x + c y F 1 f y + ω y h 1 -ω x h 2 from Eq. (
a = F 3 -c x F 2 / f x -c y F 1 / f y = f y (s 1 ω z -s 3 ω x -h 2 ) + (ω y h 1 -ω x h 2 ) (3.24)
(2) Basing on the definition of

F 5 = f y s 2 + c x F 4 f x + c y (s 1 ω z -s 3 ω x -h 2 ) + s 2 ω x -s 1 ω y - h 3 from Eq. (3.20), we assume: b = F 5 -c x F 4 / f x = f y s 2 + c y (s 1 ω z -s 3 ω x -h 2 ) + s 2 ω x -s 1 ω y -h 3 (3.25)
Now, we consider F 6 and F 7 in Eq. Eq. (3.20):

(1) From the definition of F 6 = f x s 1 , we obtain the expression of d 1 :

s 1 = F 6 f x (3.26)
(2) From the definition of F 7 = c x s 1 + c y s 2 + s 3 , we obtain the relation between s 2 and s 3 as:

s 3 = F 7 - c x F 6 f x -c y s 2 (3.27)
Then we substitute h 1 from Eq. (3.21), h 2 from Eq. (3.23), h 3 from Eq. (3.22) and Eq. (3.27) into Eq. (3.24) to obtain the expression of s 3 :

s 3 = f y F 6 f x ω z - f y F 2 f x ω z - f y F 1 ω y f x ω x ω z + F 7 f y ω y ω x 2 - f y c x F 6 ω y f x c y ω x - f y F 4 ω y f x ω x -F 2 ω x f x ω z - F 1 ω y f x ω z -a f y ω x + f y ω y 2 ω x + f y ω y c y ω x (3.28)
This time, By substituting s 3 , s 2 calculated by Eq. (3.27) and Eq. (3.27), h 1 from Eq. (3.21), h 2 from Eq. (3.23), h 3 from Eq. (3.22) into Eq. (3.25), we will obtain a pronominal which all the terms are consisted by ω while all the coefficients are determined by K and cubic curve coefficients F 1 to F 7 as follows:

C 1 • • • C 17 W 1 • • • W 17 T =                                J 1 J 7 + G 7 J 2 J 3 + J 6 -G 3 G 9 J 1 J 5 -G 4 J 4 -G 6 G 2 G 1 G 5 J 3 J 3 + J 7 -G 8 J 4 J 5 J 6                                                                ω 4
x ω 3

x ω 3

x ω y ω 3

x ω z ω 2

x ω y ω 2

z ω 2 x ω 2 y ω 2 x ω y ω z ω 2 x ω 2 x ω 2 z ω 2 x ω z ω 2 x ω y ω x ω 3 y ω x ω 2 y ω y ω x ω y ω 2 z ω 2 y ω 2 y ω z ω 4 y ω z                                 = 0 with                                J 1 = F 6 / f x c x +F 7 c 2 y J 2 = F 6 / f x c y J 3 = -c x F 7 -F 6 / f x c 2 x c 2 y J 4 = F 1 f x c y + F 4 f x c y J 5 = -f 6 c x f x c y J 6 = -f 6 c x f x c y J 7 = b c y - f y F 7 -c x f y F 6 / f x c 2 y and                                    G 1 = -(a -F 6 / f x ) G 2 = c x a f y G 3 = a f y G 4 = F 6 f x f y G 5 = F 4 f x f y G 6 = F 2 f x G 7 = F 2 f x f y G 8 = F 6 F 4 f 2 x G 9 = F 6 F 4 f 2 x f y (3.29)
where J 1 , . . . , J 7 and G 1 ...G 9 are auxiliary variables which can be computed by calibration matrix K and cubic curve coefficients uni f F 1 to uni f F 7 .

Basing on Eq. (3.29), we can use non-linear optimization to estimate ω x , ω y and ω z . In such case, at least 3 fitted curves are needed. Alternatively, by giving 16 curves, Eq. (3.29) can also be solved linearly using SVD.

Comparison of the Three RS Models

Some existing works argued that only angular-velocity plays a main role for hand-held and vehicle devices [Ringaby andForssén, 2012, Duchamp et al., 2015, Rengarajan et al., 2016, Purkait et al., 2017, Ito and Okatani, ]. Here, we give a further quantitative analysis of both rotational and translational instantaneous-motion effects on 3D line projection.

Although the linear RS model will introduce a hyperbolic curve, however, its second order coefficients Lin

F 1 = K - 22 (R w21 R w2 -R w22 R w1 )d, Lin F 2 = K - 11 (R w11 R w2 -R w12 R w1 )d are much smaller compared to Lin F 3 = K - 22 (a w R w22 -b w R w21 ) + K - 31 K - 11 Lin F 2 + K - 32 K - 22 Lin F 1 + (R w31 R w2 -R w32 R w1 )d and Lin F 4 = K - 11 (a w R w12 -b w R w11 )
and can be ignored in practice. The simulated data experiment shown in Fig. 3.5 confirmed that even with a high linear speed, Lin F 1 , Lin F 2 are relatively low, and projected curves (blue) are close to straight lines as for GS case (green).

In practice, the effect of translational speed can be compensated by an increment on the rotational speed. Therefore, we chose to extract the angular velocity basing on the rotate-only RS model instead of the uniform model. This assumption holds because the translation during frame exposure is negligible in comparison to the depth of the features to be used. Doing so, it becomes possible to compensate rolling shutter effects of the hole image independently from the depth associated to each pixel. This is the key of the single-view based RS correction.

However, the R16C still can be used in very specific application where the translational speed is very high in comparison to scan speed, and where curve detection can be achieved with a very high accuracy (subpixellic).

Practical Linear 4-Curves Algorithm

Now, we introduce a 4-curves linear solution called R4C to estimate instantaneous-rotation basing on the RS rotate-only model.

For a single RS image, if we assume the camera frame as world coordinate system, hence, R c w = I and t c w = 0. Then we denote the 3D line structural parameters as a c R w2b c R w1 = [s 1 , s 2 , s 3 ] , for five hyperbolic coefficients of each curve, we can formulate a group of equations:

F 1 = f y (s 1 ω z -s 3 ω x ) F 2 = f x (s 3 ω y -s 2 ω z ) F 3 = f y s 2 + c x (s 3 ω y -s 2 ω z ) + c y (s 1 ω z -s 3 ω x ) + (s 2 ω x -s 1 ω y ) F 4 = f x s 1 F 5 = f x s 1 + c y s 2 + s 3 (3.30)
where s 1 , s 2 and s 3 are different for each curve.

From Eq. (3.30), s 1 , s 2 , s 3 and ω z can be substituted by ω x and ω y . We can obtain a bivariate cubic polynomial. With new coefficients C 1 to C 8 which are only determined by matrix K and coefficients F 1 to F 5 . Now, by giving four curves, we have:

C 1 1 • • • C 1 8 . . . . . . . . . C 4 1 • • • C 4 8 [ω x 3 , ω y 2 ω x , ω x 2 , ω y 2 , ω x ω y , ω x , ω y , 1] = 0 (3.31)
By eliminating ω 3 x and ω 2 y ω x , Eq. (3.31) becomes a two bi-variables quadratic polynomial equations:

T 1 1 • • • T 1 6 T 2 1 • • • T 2 6 [ω x 2 , ω y 2 , ω x ω y , ω x , ω y , 1] = 0 (3.32)
Where coefficients T are calculated by coefficients C in Eq. 3.31. Again, we further substitute ω y by ω x and the 10 coefficients T in Eq. (3.32), then we obtain:

(H 1 , H 2 , H 3 , H 4 , H 5 )(ω x 4 , ω x 3 , ω x 2 , ω x , 1) = 0 (3.33)
Thus, Eq. 3.32 turns into a bi-quadratic polynomial equation with one unknown (ω x ).

The five variables H 1 , . . . , H 5 can be computed by using F 1 , . . . , F 5 and components of K. If more than 4 curves are available, parameter ω x can be recovered by solving the non homogeneous linear system Eq. (3.33), after which ω y will be recovered using Eq. (3.31). Then we calculate ω z based on Eq. (3.30).

Derivation of Eq. (3.33)

Transformation from Eq. (3.30) to Eq. (3.31). In order to extract angular velocity from Eq. (3.30), we can first substitute structure unknowns s 1 , s 2 and s 3 just by angular velocity parameters ω x , ω y and ω z . Thus, we define four auxiliary variables a, b, c and d as follows:

a = F 5 -F 4 = c y s 2 + s 3 b = F 2 f x = s 3 ω y - a -s 3 c y ω z c = F 1 f y = F 4 f x ω z -s 3 ω x d = F 3 - c y f y F 1 - c x f x F 2 = ( f y + ω x ) a -s 3 c y - F 4 f x ω y (3.34)
then we substitute ω z and s 3 by ω x and ω y , then we obtain:

c y [(d - a f y c y + a c y )ω x - f y F 4 f x ω y + F 4 f x ω x ω y + a c y ω 2 x + ( a f y c y -f y d)][ω y - a f x F 4 c y c] = 0 (3.35)
Eq. (3.35) can be re-written as Eq. (3.31)'s form, which is a cubic bi-varibales polynomial:

C 1 ω x 3 + C 2 ω y 2 ω x + C 3 ω x 2 + C 4 ω y 2 + C 5 ω x ω y + C 6 ω x + C 7 ω y + C 8 = 0 with C 1 = - a 2 f x f y F 4 c y C 2 = - c y F 4 f x C 3 = (- a f x F 4 )(d - a f y c y + a c y ) + f x ac F 4 c y + a 2 -b - f x F 4 c y ac C 4 = - f y F 4 c y f x + F 2 4 c 2 y f 2 x C 5 = dc y -a f x + a + f y a + c + 2aF 4 c y C 6 = a f y F 4 ( f y d -a f y c y ) + f x c F 4 (d -a f y c y + a c y ) + 2adc y -2a 2 f y (b + f x F 4 c y ac) C 7 = (a f y -f y c y d) -f y c + 2 dF 4 c 2 y f x -2 ac y F 4 f y f x C 8 = c f x F 4 ( a f y c y -f y d) + c 2 y d 2 -2ac y f y d + a 2 f 2 y -f 2 y (b + f x F 4 c y ac) (3.36)
Transformation from Eq. (3.31) to Eq. (3.32). We first re-write the equation system of four curves basing on Eq. (3.36):

C

(1)

1 ω x 3 + C (1)
2 ω y 2 ω x + C

(1)

3 ω x 2 + C (1)
4 ω y 2 + C

(1)

5 ω x ω y + C

(1)

6 ω x + C

(1)

7 ω y + C

(1)

8 = 0 (3.37)

C

(2)

1 ω x 3 + C (2) 2 ω y 2 ω x + C (2) 3 ω x 2 + C (2) 4 ω y 2 + C (2) 5 ω x ω y + C (2) 6 ω x + C (2) 7 ω y + C (2) 8 = 0 (3.38) C (3) 1 ω x 3 + C (3) 2 ω y 2 ω x + C (3) 3 ω x 2 + C (3) 4 ω y 2 + C (3) 5 ω x ω y + C (3) 6 ω x + C (3) 7 ω y + C (3) 8 = 0 (3.39) C (4) 1 ω x 3 + C (4) 2 ω y 2 ω x + C (4) 3 ω x 2 + C (4) 4 ω y 2 + C (4) 5 ω x ω y + C (4) 6 ω x + C (4) 7 ω y + C (4) 8 = 0 (3.40) where C (i)
1 is the C 1 coefficient of the i th curve. Now, we define three auxiliary variables r 1 , r 2 and r 3 as follows:

r 1 = C 1 1 C 2 1 , r 2 = C 1 1 C 3 1 and r 3 = C 1 3 -r 1 C 2 3 C 3 3 -r 2 C 2 3 (3.41)
we can substitute ω y by ω x by using Eq. (3.37), (3.38), (3.39) and the three auxiliary variables above as follows:

Eq.(3.37)r 1 Eq.(3.38)r 3 (Eq.(3.39)r 2 Eq.(3.38)) = 0 (3.42)

which is equivalent to the first row of Eq. (3.32) as:

T 1 1 ω 2 x + T 1 2 ω 2 y + T 1 3 ω x ω y + T 1 4 ω x + T 1 5 ω y + T 1 6 = 0 (3.43)
where coefficients T 1 1 , . . . , T 1 5 can be computed by C 1 1 , . . . , C 3 8 . Then we use Eq. (3.40) to replace Eq. (3.39) and under the same transformation Eq. (3.42). We will obtain the second row of Eq. (3.32) as:

T 2 1 ω 2 x + T 2 2 ω 2 y + T 2 3 ω x ω y + T 2 4 ω x + T 2 5 ω y + T 2 6 = 0 (3.44)
Transformation from Eq. (3.32) to Eq. (3.33). At this stage, ω y can be substituted by ω x using Eq. (3.43) and Eq. (3.44) and leads to Eq. (3.33) as:

(H 1 , H 2 , H 3 , H 4 , H 5 )(ω x 4 , ω x 3 , ω x 2 , ω x , 1) = 0 (3.45)
where coefficients

H 1 to H 5 correspond to [T 1 1 , . . . , T 1 6 , T 2 1 , . . . , T 2 6 ].
In such case, two bivariables cubic polynomial equation turn into a quartic polynomial equation with one unknown. Finally,Eq. (3.33) can be solved directly with four geometric possible solutions, however, only one is correct. Therefore, we choose the most geometrically consistent value.

Degeneracies Analysis

Generally, instantaneous-motion estimation basing on projected curves (namely on their coefficients F 1 , . . . , F 5 of Eq. (3.14)) leads to a unique solution {< R w , (a w , b w )) >, ω}. Nevertheless, some degenerate or singular configurations leads to ambiguous results on ω. We present three degenerate configurations:

Case 1: 3D line located within y-z-plane (a w = 0, b w = ∀x, R w = (∀x, 0, 0)) and arbitrary instantaneous-rotation along x-axis (ω = (∀x, 0, 0)).

Case 2: 3D line located within x-z-plane (a w = ∀x, b w = 0, R w = (0, ∀x, 0)) and arbitrary instantaneous-rotation along y-axis (ω = (0, ∀x, 0)).

Case 3: 3D line parallel to x-axis (a w = ∀x, b w = ∀x, R w = (0, π/2, 0)) and arbitrary instantaneous-rotation along y-axis (ω = (∀x, 0, 0)).

However, the configurations occur rarely in practice with hand-held camera or with a camera embedded on a vehicle.

Proof of the three degenerate cases

We present derivation details of the three degenerate cases of the linear 4-curves solution.

Proof. Degenerate case 1 We assume a 3D line located within y-z-plane and a camera under an arbitrary instantaneous-rotation about x-axis. This leads to the following configuration:

L =< R w , (a w , b w )) >= {< R(∀x 1 , 0, 0), (0, ∀x 2 ) > |x 1 , x 2 ∈ R} ω = {[∀x, 0, 0] |x ∈ R} (3.46)
where R(a, b, c) is a rotation matrix generated by rotation angles a, b and c about x-y-z axis respectively. By substituting Eq. (3.46) into Eq. (3.17), and assuming R W C = I and t W C = [0; 0; 0], Eq. (3.14) becomes:

F 1 = 0 F 2 = 0 F 3 = f y L y 0 = 0 F 4 = L x 0 F 5 = c x L x 0 + L z 0 (3.47)
The equation above indicates that if an arbitrary 3D line within y-z-plane is observed by an RS camera under instantaneous-rotation about x-axis, no matter magnitude of speed, all of these lines will be projected as the same 2D line u = c x / f x . In other words, a projected curve can be explained by multiple configurations {< R w , (a w , b w )) >, ω}. Thus, configuration in Eq. (3.46) is a degenerate one.

Proof. Degenerate case 2 This time, we assume a 3D line located within x-z-plane and camera under arbitrary instantaneous-rotation along y-axis during acquisition. This leads to:

L =< R w , (a w , b w )) >= {< R(0, ∀x 1 , 0), (∀x 2 , 0) > |x 1 , x 2 ∈ R} ω = {[0, ∀x, 0] |x ∈ R} (3.48)
Thus, Eq. (3.14) becomes:

F 1 = 0 F 2 = 0 F 3 = f y L y 0 F 4 = f x L x 0 = 0 F 5 = c y L y 0 + L z 0 (3.49)
The equation above indicates that if an arbitrary 3D line within y-z-plane is observed by an RS camera under instantaneous-rotation about y-axis, no matter magnitude of speed, all of these lines will be projected as the 2D lines v = c y / f x . Therefore, the configuration in Eq. (3.48) is also a degenerate one.

Proof. Degenerate case 3

We assume a 3D line parallel to x-axis and camera under arbitrary instantaneous-rotation about x-axis during acquisition. This leads to:

L =< R w , (a w , b w )) >= {< R(0, π/2, 0), (∀x 1 , ∀x 2 ) > |x 1 , x 2 ∈ R} ω = {[∀x, 0, 0] |x ∈ R} (3.50)
Thus, Eq. (3.14) becomes:

           F 1 = -f y b w ω x F 2 = 0 F 3 = f y L y 0 -c y b w ω x + a w ω x F 4 = 0 F 5 = c y L y 0 + L z 0 (3.51)
The equation above indicates that if an arbitrary 3D line parallel to x-axis is observed by a RS camera under instantaneous-rotation about x-axis, no matter magnitude of speed, all of these lines will be projected as horizontal 2D lines in image as F 1 v 2 + F 3 v + F 5 = 0. Indeed, each of these lines can be explained by the coupling of a w , b w and ω. Therefore, the configuration in Eq.(3.50) is also a degenerate one.

RS Image Correction

In this section we show how to correct the RS image in this section, after successfully extracting the rotational velocity from the detected curves.

Compensating Instantaneous-motion

We compensate the effects of ω in order to correct RS image by performing a forward mapping (eliminating P i with Eq. (2.4), Eq. (2.11) and Eq. (2.20) ) to all pixels as:

m GS i = Π GS (KR(v i ) -1 K -1 m RS i ) (3.52)
where, the procedure will map original points q RS to q GS on global frame. R(v i ) is computed by using Eq. (2.20).

Automatic Selection of Actual 3D Lines

Since both 3D lines and curves will rendered as 2D curves on image, the problem of how to automatically distinguish image curves corresponding to 3D lines from actual 3D curves arises.

Method of [START_REF] Rengarajan | From bows to arrows: Rolling shutter rectification of urban scenes[END_REF] uses 3 degree polynomial fitting to reject obvious outliers, but not ambiguous ones. The method of [Purkait et al., 2017] uses Huber Mestimator during joint estimation of motion parameters and vanishing directions to reject short line segments which are not sufficiently well oriented according to the vanishing directions. Unfortunately, some of these line segments survive the rejection process because they may be aligned with one of the vanishing directions despite not satisfying MW assumption, thus participating to motion parameter computation.

In this paper, we propose a 2-steps method (shown in Fig. 3.6) inspired from RANSAC technique. This selection process aims not only to reject features corresponding to non straight lines (outliers) but also to maximize the number of features corresponding to actual straight lines (inliers), thus increasing the accuracy and robustness of instantaneousmotion calculation.

Step 1: The goal of this step is to generate a preliminary set of candidate curves. Edge curves are first detected using Canny detector and linked to close small gaps. Then short curves (less than 20 pixels in experiments) are discarded. Finally, curves which sufficiently fit hyperbolic polynomial are selected basing on RMSE fitting error score.

Step 2: The second step is a global consistency verification. It consists in the integration of the R4C method within a RANSAC-like framework:

• Repeat N times (i) Select a random sample S i = {C 1 , C 2 , C 3 , C 4 } of 4 four curves C j among the candidate curves.
Step 1

Curves detection and fitting

Step 2

Repeat N times

Sample 1 Sample N Correction 1 Correction N

R4C R4C

N corrections

Best correction result

Step 3 Image correction

Inliers Final correction

R4C

GS image

Ego-motion

RS image

Objective: looks the same FIGURE 3.6: Automatic actual 3D line selection. Both 3D straight lines and curves observed will be projected as 2D curves on RS cameras under instantaneous-motion. We firstly fit all detected curve pixels to hyperbolic polynomials and discard curves with big fitting errors (red curves in step 1). In step 2, we randomly select putative sets of 4 curves (blue curves) and compute camera instantaneous-motion for each set. Then we correct all image candidate curves basing on the obtained instantaneous-motion and compute the global straightness score. After N samples, the sample with the smallest straightness score is chosen as best sample. After discarding curves whose corrected straightness exceeds a defined threshold, we obtain final set of inliers.

(ii) Run R4C to calculate ω i based on S i .

(iii) Perform forward mapping Eq. (3.52) to all curves pixels and calculate straightnesses of each curves after correction.

• Select the sample with maximum number of inliers (straightness of the corrected curve smaller than pixels) as best solution over all samples.

• Refine the best solution by performing R4C again using the inliers.

The straightness of a curve is calculated by mean square of perpendicular offset of each curve pixel to its corresponding least-squares-fitting line. We set = 1 experimentally and the number of samples N is set automatically used method in [START_REF] Hartley | Multiple view geometry in computer vision[END_REF]. Fig. 3.7 shows an example of outlier rejection procedure that some outliers survive from the first selection criteria. However, the RANSAC-like automatic feature selection reject those curves which are not corresponding to the actual 3D lines.

3-step RSSfM using Lines

Step 1: Compensating the Effect of Rotational Velocities for Each Image

In order to compensate the effects of ω, we perform an inverse mapping to all pointmatches among all the RS images using Eq. (3.52).

Step 2: SfM Using Extracted Rotational Velocities

After extracting rotational velocities for each image, we still need to recover both motion between images and linear-velocities during acquisition. This is achieved as follows: first each image is rectified by compensating the rotational velocities computed in the previous section. This results in a new image pair which looks like if each camera undergoes linear motion (pure translation) during acquisition. Thus, the epipolar geometry of this image pair is computed along with the translational instantaneous velocities of the cameras using the linear RS model. The advantage of using linear RS model in SfM is to avoid planar degenerate solutions described in [Albl et al., 2016b, Ito and Okatani, ]. This is caused by the fact that using angular-velocities as unknown parameters will make the algorithm collapse into specific values during non-linear optimization. Thus, using linear RS model by fixing rotational velocities can avoid this degeneracy.

After the image correction, we can solve the relative pose problem of linear RS cameras using 5 × 5 essential matrix with point matches [START_REF] Dai | Rolling shutter camera relative pose: generalized epipolar geometry[END_REF]:

[u i , v i ] T ↔ [u i , v i ] proposed by
v i 2 v i u i v i u i 1 E 5×5 v 2 i v i u i v i u i 1 = 0 (3.53)
With at least 20 point correspondences, E 5×5 can be computed as usual using a DLT (Direct Linear Transform) Algorithm. Then, the relative pose [R, t] and the translational instantaneous velocities are extracted linearly from E 5×5 . Finally, 3D points are reconstructed by triangulation [Albl et al., 2016a].

Step 3: Camera-based RS Bundle Adjustment

We present a novel camera-based RS bundle adjustment (C-RSBA) which is different from existing works that calculate reprojection errors with image measurements, thus imposing a constant raw index during optimization. This enables to refine the parameters obtained thanks to the straightness constraint by avoiding degenerate configurations, thus outperforming existing RSBA methods. Since the C-RSBA can serve for all the RS vision applications using the reprojection-based iterative refinement such as pose estimation [START_REF] Ait-Aider | Simultaneous object pose and velocity computation using a single view from a rolling shutter camera[END_REF], Magerand et al., 2012], VO [START_REF] Schubert | Direct sparse odometry with rolling shutter[END_REF] and SLAM [START_REF] Kim | Direct semi-dense slam for rolling shutter cameras[END_REF], we will discuss C-RSBA in details in chapter 4.

Experiments

In this section, we compare our image correction method (R4C with automatic feature selection) to existing works using both synthetic and real data. The results of the proposed 3-step RSSfM will be presented in Chapter 4.

Experiment setting.

The experiments were conducted on a i5 CPU 2.8G Hz with 4G RAM. It took around 4.1s for curve detection and fitting, 1.9s for instantaneous-motion estimation with automatic feature selection, and 0.1s for image correction with 240 × 320 size. The proposed method was implemented in MATLAB. An improvement can be expected using C++.

Comparison to state-of-the-art. The proposed RS correction method was compared to three state-of-the-art techniques:

• R4C: The proposed linear 4-curve RS correction method with RANSAC-like automatic feature selection.

• Rengarajan: The single RS correction method using straightness constraint with MW assumption [START_REF] Rengarajan | From bows to arrows: Rolling shutter rectification of urban scenes[END_REF] 1 .

• CNN: The single RS correction method using Convolutional Neural Network [START_REF] Rengarajan | Unrolling the shutter: Cnn to correct motion distortions[END_REF] 2 .

• Purkait: The single RS correction method using vanising direction constraint with MW assumption [Purkait et al., 2017] 3 .

Synthetic RS Image Experiments

Grid Scene

We simulated a grid scene where MW assumption holds on as required by Rengarajan and Purkait (but not by our method). Images corresponding to random angularvelocities were generated using the following virtual camera parameters: focal = 1 unit, resolution as 640 × 480 and scan speed=7.5 × 10 -5s/row. Then values of ω were computed from deformed edges using R4C. While ground-truths are available, we evaluated instantaneous-rotation accuracy using both visual checking and mean value of estimated rotation errors ērotate [START_REF] Rengarajan | Unrolling the shutter: Cnn to correct motion distortions[END_REF] of each image row (calculated using Eq. 2.20). 100 values of ω were generated randomly in different directions. Since Rengarajan uses z-axis rotate model fails in most cases. We compared our method to two other single-image based RS correction methods also using line features, namely Rengarajan and Purkait.

Gentle configuration:

The results in Fig. 3.9 (first row) show that our method, Rengarajan and Purkait obtain correct results under gentle conditions ( d = 5 unit/s, ω = 5 during acquisition, RS image with average 0.5 pixel noise and no outlier curves). However, significant differences appear when RS effect becomes more important.

Accuracy vs Angular Velocity: Experiments were carried out with |ω| varying from 0 to 30 degree/frame. Results in Fig. 3.8, 3.9 show that the RS instantaneous-motion estimation errors of Rengarajan climb from 0 to 14 degrees while errors of Purkait keep low under 15 deg/frame but dramatically increase with bigger ω. Inversely, R4C maintains the error under 1 deg.

RS images

Rengarajan

Purkait

R4C

Gentle condition

Large ω Large d Outliers presence Accuracy vs Translational Velocity: Since all tested methods assume translational velocity is negligible during image exposure, we now verify accuracy of these three methods if RS translation velocity effect is significant. The translation velocity d was increased from 0 to 12 unit/s which is extremely high and rarely occurs in a real application context. The results in Fig. 3.8 shows that the three methods perform stable and achieve errors under 1.2 degree with big translation velocities.

Accuracy vs Outlier Curves:

In this experiment, we simulated 3D straight lines and added 3D curves as outliers. The number of outliers was increased from 0% to 50%. Results in Fig. 3.8 and Fig. 3.9 show that both Rengarajan and Purkait fail in presence of outliers. In contrast, thanks to automatic feature selection, R4C obtains correct correction in different settings.

Accuracy vs Pixel Noise:

We fixed the camera translational speed to 5 unit/s and the angular velocity to 5 deg/frame. We added a random Gausian noise to projected curve points( mean std dev increases from 0 to 2 pixels). The results in Fig. 3.8 demonstrate that R4C is much more robust against increasing noises compared to Rengarajan and Purkait.

Complex Urban Scene

We evaluated performances of our method R4C compared to Rengarajan, CNN and Purkait using synthetic RS images.

'House' dataset. Our first experiment based on a public synthetic RS image dataset [START_REF] Forssén | Rectifying rolling shutter video from hand-held devices[END_REF] which contains multiple RS videos filming a house scene. Since ground-truth of camera instantaneous-motions are known, we keep using ērotate to evaluate accuracy of corrections.

The results in Fig. 3.10 shows that Purkait fails since house roof and current lead violate MW assumption. R4C, Rengarajan and CNN obtain corrected images visually close to ground-truth image. However, both Rengarajan and CNN use simplified instantaneousmotion model which can not recover instantaneous-rotation along all three x-y-z axis. In other words, visually acceptable correction does not ensure consistency of geometry.

The quantitative evaluation results in Fig. 3.10 using ērotate demonstrate that our method not only offers visually pleasant corrected image, but also recovers images which better fit GS-based 3D geometry.

Urban scene dataset. We also perform our method with different baselines using RS images from urban scene dataset [START_REF] Rengarajan | Unrolling the shutter: Cnn to correct motion distortions[END_REF] and results are shown in Fig. 3.11.

Since MW assumption holds on in the first RS image of Fig. 3.11, except Rengarajan, there are no significant curvatures left in the corrected images. However, Purkait keeps effects of vertical shrinking while CNN and our method obtain better visual corrections.

The second RS image shows a circular building with many 3D curves. The correction results demonstrate that our proposed method can successfully filter outliers while Rengarajan and Purkait fail. One can note that the corrected image of our method preserves curves belonging to the circular facade, meanwhile, CNN straights every curve. Moreover, the curves obtained by our method R4C fit better ellipse sections being the perspective projection of circles.

The third and fourth images are veiled by tree branches which can be regarded as outliers. As a result, distortions are observed on corrected images of Rengarajan and Purkait meanwhile R4C and CNN obtain similar corrections, however small curvature remains on results of CNN.

Real RS Image Experiments

RS video dataset:

We conduct the first real images experiment on a RS video dataset [START_REF] Ringaby | Efficient video rectification and stabilisation for cell-phones[END_REF]. Comparison of our frame-by-frame RS corrections with methods of Rengarajan, CNN and Purkait are shown in Fig. 3.12. We use the approach described in [Purkait et al., 2017] to do a quantitative evaluation by counting mean value of the number of found inliers |R F | (point matches after estimating the fundamental matrix) from corrected frame pairs. The results show our method obtains the higher inlier number and demonstrate that it can better recover the consistency of projection geometry.

Hand-held web-cam dataset:

We also compared our method on a challenging complex urban dataset which was captured by a Logitech camera with strong RS effects. It can be seen in Fig. 3.13 that Rengarajan obtain relatively acceptable corrections for the first image but fails for the second image due to the difficulty in grouping curves. Methods of CNN and Purkait fail in both cases because of the complexity of the scenes and the large angular velocities during acquisition. In contrast, we can see that our method obtains visually better corrections in both RS images.

Discussion and Conclusion

In this chapter, we first presented a novel RS correction method which uses line features. Unlike existing methods, which uses iterative solutions and make MW assumption, our method R4C computes linearly the camera instantaneous-motion using few image features. Besides, the method was integrated in a RANSAC-like framework which enables us to reject outlier curves making image correction more robust and fully automated.

Extensive experiments demonstrated the robustness and the accuracy of the proposed method in variable complex urban scenes or under extreme filming conditions. Specifically, our method not only produces visually pleasant corrections, but also is able to preserve consistency of geometry. Thus, the proposed method in this paper can serve for rolling shutter image correction as well as for pre-processing images in other computer vision applications such as feature matching and tracking.

Thanks to this RS correction method, we also presented a 3-steps method which solve RSSfM. Unlike with approaching methods, a general motion model is assumed and no a priori knowledge on the 3D lines is needed. Moreover, the first two steps of proposed solution are linear and works with fewer matches than previous methods.

RS distorted image

Correction by Rengarajan

Correction by Purkait

Correction by CNN

Correction by R4C

FIGURE 3.13: omparison of image correction results on two real RS images of a complex urban scene with strong RS effects against to methods of [ [START_REF] Rengarajan | From bows to arrows: Rolling shutter rectification of urban scenes[END_REF], Purkait et al., 2017, Rengarajan et al., 2017].

Chapter 4

RS Bundle Adjustment Revisited

Context

In this chapter, we address on the bundle adjustment (BA) in RSSfM. In existing works, reprojection error is calculated by using row indexes of corresponding image measurements. We point out that this measurement-based method brings the risk of obtaining degenerated solution [START_REF] Albl | Degeneracies in rolling shutter sfm[END_REF]. Alternatively, we present a novel RS projection method based on camera motion and instantaneous-motion only without using image measurements, called camera-based projection. Then we incorporate it into RS BA as the final step of the proposed 3-steps RSSfM (chapter. 3). We provide analysis of why measurement-based RS BA tends to collapse into degeneracy, while our proposed camera-based RS BA survives. Thus, as shown in Fig. 4.1, different from the state-of-the-art works which require input images with distinct readout directions, our method allows more common and nature at capture style.

Both synthetic and real experiments we demonstrate that with the help of the proposed RS BA method, our 3-steps RSSfM pipeline (chapter. 3) outperforms existing works in accuracy and removes constraint on filming style.

Related Work

Estimating parameters by minimizing reprojection (photometric) error is a common technique in 3D vision applications. It has been widely used in RS applications, for instance, in object or pose calculation [START_REF] Ait-Aider | Simultaneous object pose and velocity computation using a single view from a rolling shutter camera[END_REF], SfM [START_REF] Im | Accurate 3d reconstruction from small motion clip for rolling shutter cameras[END_REF], Duchamp et al., 2015[START_REF] Albl | Degeneracies in rolling shutter sfm[END_REF] and SLAM [START_REF] Kim | Direct semi-dense slam for rolling shutter cameras[END_REF]. Whereas the reprojection of points involves only the pose and the point cartesian coordinates with GS images, it requires image measurements, that is to say the line indexes of each point, with RS images . The problem is that for reprojection to be geometrically consistent, these indexes must evolve during iterative optimization. We found out that there are two main drawbacks of this measurement-based projection method:

• Measurement-based projection cannot simulate true RS projection procedure and leads to accuracy loss.

• Measurement-based projection bring risks of collapse into degeneracy during RS BA (Fig. 4.1).

Thus, we need a new algorithm to calculate RS projection point and incorporate it with RS BA to improve SfM accuracy and avoid degeneracy.

RS Reprojection

Formulation of Rolling Shutter Bundle Adjustment (RSBA)

Considering a sequence of two or more images, a GSBA can be performed to refine motion [R|t] and scene structure P ( as shown in Eq. (2.10).

In contrast, the objective of RSBA is to refine motion [R|t], camera instantaneousmotion [ω|d] and scene structure P simultaneously. Thus, Eq. (2.10) changes to:

{P * i } , [R j * |t j * ], [ω j * |d j * ] = arg min m ∑ j=1 n ∑ i=1 V j i e j i 2 with e j i = mj i -p(P i ) (4.1)
where e j i is reprojection error, which is the distance between measured image point mj i and the reprojection point of P i on j th image. V j i indicates the visible index which equals to 1 if 3D point P i is seen on the j th image. p is the RS projection operator which transforms the 3D point P i in world coordinate system into image point m j i .

Measurement-based Projection

To the best of our knowledge, all existing works [START_REF] Ait-Aider | Simultaneous object pose and velocity computation using a single view from a rolling shutter camera[END_REF], Hedborg et al., 2012[START_REF] Albl | Degeneracies in rolling shutter sfm[END_REF]

s i m i 1 = p m (P i ) = K[R( ṽi ) t( ṽi )] P i 1 with R(v i ) = (I + [ω] × ṽi )R 0 t(v i ) = t 0 + d ṽi (4.2)
where the row index of measurement information ṽj i is the key to calculate the RS projection point.

Camera-based Projection

Alternatively, we propose a novel approach to calculate reprojected points purely basing on RS camera model (pose [R, t] and instantaneous-motion ω, d), without using image measurement information. We call this camera-based RS projection (p c ):

m i = u i v i = p c (P i ) where v i = -b ± √ -4ac + b 2 2a u i = (KR) (1) P i + R(1) P i v i + (Kt) (1) + (Kd) (1) v i (KR) (3) P i + R(3) P i v i + (Kt) (3) + (Kd (3) )v i with R = K[ω] × R a = R(3) P i + (Kd) (3) b = R (3) P i + (Kt) (3) -R(2) P i -(Kd) (2) c = -R (2) P i -(Kt) (2) (4.3)
where M (r) is the r th row of matrix M. a, b and c are three auxiliary variables while R is an auxiliary matrix.

Proof of Eq. (4.3): Substituting Eq. (2.20) into Eq. (2.11):

s i m i 1 =   s i u i s i v i s i   = (I + [ω] × v i )RP i + t + dv i (4.4)
Then, by substituting the third row of Eq. (4.4) into the second row of equation above, we have a quadratic equation where v i is the only unknown: av 2 i + bv i + c = 0. We provide recipes of solving this equation later. After we obtain v i , u i can be easily calculated by substituting third row into the first row of Eq. (4.4).

Double-projection

The quadratic equation in Eq. ( 4.3) yields two geometric feasible solutions v 1 and v 2 named as double-projection pattern (shown in Fig. 4.2). In common and practical configurations, there are usually one solution located within image range while another one far away from image range. We analyze two typical cases in Fig. 4.2. A 3D point with 10 unit depth projected as two points within image range requires translation speed at least 500 unit/s and angular speed 50 rad/s which are rarely achieved in real applications.

Thus, since only one solution is consistent with the pose in practice. We propose to always select the solution that is nearer measurement to image by comparing reprojection values obtained by using v 1 and v 2 respectively during bundle adjustment (each round in non-linear optimization). This selection provides a solution that maintains projection point within the camera field of view.

It is important to note that camera-based RS projection approach not only can be used in RS SfM or existing works [START_REF] Hedborg | Rolling shutter bundle adjustment[END_REF][START_REF]Rolling Shutter Stereo[END_REF], Duchamp et al., 2015, Kim et al., 2016] , but also in other applications basing on reprojection errors minimization such as pose estimation [START_REF] Ait-Aider | Simultaneous object pose and velocity computation using a single view from a rolling shutter camera[END_REF], Magerand et al., 2012].

Comparison of the Two RS Projection Algorithms

The differences between classical GSBA, measurement-based RSBA and camera-based RSBA are summarized in table .

Measurement-based RSBA

Measurement-based RSBA (M-RSBA) uses measurement-based RS projection algorithm to calculate the reprojection point during RSBA. In other words, reprojection is computed using p m (P i ) described in Eq. (4.2).

Disadvantages of M-RSBA: M-RSBA uses measurements as pre-knowledge to calculate reprojection points and makes exposure-delay of each point fixed. However, during optimization, exposure-delays should change at each iteration in order to maintain structure and motion consistency according to row-index of respected reprojections. Therefore, we indicate two drawbacks of M-RSBA:

• It can't simulate true projection during optimization which conducts accuracy loss.

• It brings the risks of degeneracy as shown in [START_REF] Albl | Degeneracies in rolling shutter sfm[END_REF].

Camera-based RSBA

Camera-based RSBA (C-RSBA) uses Camera-based RS projection algorithm to calculate the reprojection point during RSBA. In other word, p(P i ) in Eq. ( 4.1) can be computed using p c (P i ) described in Eq. ( 4.3). [START_REF] Albl | Degeneracies in rolling shutter sfm[END_REF]] investigated mechanism of planar degeneracy which often arises during RSBA using measurement-based projection: Multiple RS views with parallel read-out directions will collapse into solutions that consist in cameras with ω = [-1; 0; 0] and 3D points located on y = 0 plane since image noise presence as shown in Fig. 4.3. Under this degeneracy, each 3D point can be observed in any row on image. During RSBA, we can always find projection point on row v i that satisfies constraints of measurements-based projection in Eq. (4.3). Since image noise presence, this degeneracy provides solution superior to ground-truth.

Planar Degeneracy

Why does C-RSBA Survives Planar Degeneracy?

In contrast, we found out that by using camera-based method to calculate reprojection errors, C-RSBA survives planar degeneracy. The observations for the difference in behavior of C-RSBA and M-RSBA is given bellow. Proposition: When RSBA collapses towards planar degeneracy, reprojection errors calculated by p m gradually descend to 0 while errors using p c become huge (Fig. 4.4).

Without formal demonstration, we show two examples to compare the performances of M-RSBA and C-RSBA with approximate critical configurations. We assume a single RS camera and instantaneous-motion close to planar critical configuration as ω = [-1, 0, 0] , d = 0 and 3D points (in camera coordinate system) close to P = [X, 0, Z] T . C indicates camera pose and instantaneous-motion parameters.

Example 1 (M-RSBA): Assuming RS camera with referenced pose [I, 0]. We firstly set ω = [-1 + ∆ ω , 0, 0] T and P = [X, 0, Z] . Where ∆ ω are tiny changes of ω x .

e = e u e v = m -p m (R, t, ω, d, P, ṽ) = ũ -X Z ṽ∆ ω (4.5)
when ∆ ω is changing closer and closer to 0, the second component of reprojection error e v is also becoming smaller and tends to 0. Then, we investigate reprojection errors when Y of P is optimized towards 0. we set

P = [X, ∆ Y , Z] T . Where ∆ Y are tiny changes of Y. e = e u e v = m -p m (R, t, ω, d, P, ṽ) = ũ -X Z ṽ2 +1 ṽ-Z/∆ Y (4.6)
Similarly, when ∆ Y is closing to 0, e v are reduced to 0. Therefore, decrease of ∆ ω and ∆ Y makes e v reduced to 0.

Therefore, the reprojection error by using p m is:

e = e u e v = m -p m (C, P, ṽ) = ũ -X Z 0 (4.7)
Simultaneously, [X, 0, Z] is further optimized to make e u also reduced to 0. Finally, overall error e will descend to 0.

Example 2 (C-RSBA):

We first assume ω × of instantaneous-motion close to -1 as [-1 + ∆ ω , 0, 0] T . 3D point located at y = 0 plane.

e = e u e v = m -p c (R, t, ω, d, P) = ũ -X Z ṽ (4.8)
when ω is close to [-1, 0, 0] , the projection points will gather on a line v = 0. Thus, e v becomes ∑ v j i . Again, we investigate reprojection errors with P = [X, ∆ Y , Z] and ω = [-1, 0, 0] :

e = e u e v = m -p c (R, t, ω, d, P) = ũ -X Z ṽ (4.9)
In such a case, reprojected points located at infinity on image plane which is regarded with reprojection point at v = 0 as double-projection pattern. However, according to p c , we always choose v = 0 as final solution. Thus e v will becomes v j i . Therefore, the reprojection error by using p c is,

e = e u e v = m -p c (C, P) = ũ -X Z ṽ (4.10)
The overall reprojection becomes v j i which may be even larger than reprojection error of start point.

Discussion. Through example 1 and example 2, one can observe that planar degenerate solution is a perfect minimum for cost function of M-RSBA while as plateau for C-RSBA. This explains how C-RSBA successfully avoids this degeneracy. An example of reprojection errors of M-RSBA and C-RSBA when configurations are slipping towards planar degeneracy (shown in Fig. 4.4) illustrates our proposition.

Thus, without constraints on camera motions (e.g. perpendicular read-out directions), C-RSBA successfully handles planar degeneracy.

Experiments

The proposed method C-RSBA was evaluated on both synthetic and real data. It was also compared to two BA method:

• Classical GS BA method, close to [START_REF] Lourakis | Sba: A software package for generic sparse bundle adjustment[END_REF].

• State-of-the art RS BA method M-RSBA [START_REF] Albl | Degeneracies in rolling shutter sfm[END_REF].

BA and Read-out directions

The angles between read-out directions among the image sequence have a significant impact on final reconstruction quality. Thus we designed a simulation experiment to evaluate GSBA, M-RSBA (initialized by GSBA) and C-RSBA (initialized by the proposed linear two-step method with respect to this parameter).

Three cameras generated randomly on a sphere with a radius of 1 unit and heading to a cubical scene with varying average scanning angles from 0 to 90 deg. In Fig. 4.5, a deformed 3D cube is being reconstructed by GSBA in both parallel and perpendicular read-out directions cases. M-RSBA obtains correct reconstruction using images with perpendicular read-out directions but fails in parallel one, which is a common configuration in practical applications. The proposed C-RSBA reconstructs a correct 3D scene in both parallel and perpendicular cases.

In order to draw a quantitative conclusion, we used the sum of distances between reconstructed 3D points and ground-truth 3D points as a criteria to evaluate SfM performances. Results in Fig. 4.6 show that M-RSBA achieves better reconstruction than GSBA when read-out direction angles are bigger than 60 deg, while C-RSBA obtains higheraccuracy and is more stable with close read-out directions (below 30 deg).

Noise Level Effect

In order to evaluate the effect of noise level on RSBA, we added random Gaussian noise to image measurements. We designed five comparison groups: GSBA, M-RSBA and C-RSBA using parallel and perpendicular scanning (read-out) directions RS images respectively. The results are shown in Fig. 4.7. M-RSBA and C-RSBA achieve the same SfM accuracy superior to GSBA in noise free cases by using parallel read-out direction. However, M-RSBA collapse into degeneracy deeper and deeper with increasing noise levels and even much worse than GSBA. In contrast,estimation. Another interesting observation is that errors of C-RSBA using parallel readout directions are even lower than errors of M-RSBA with perpendicular directions.

3-steps RSSfM Method with RSBA

We incorporated C-RSBA into the pipeline of the 3-steps RSSfM method described in chapter 3 and show the final results in this experiment.

Synthetic RS Images

Synthetic RS benchmark [Forssén and Ringaby, 2010]: We evaluated our three-steps RS SfM approach on synthetic RS images benchmarked by Forssen et al. [START_REF] Forssén | Rectifying rolling shutter video from hand-held devices[END_REF]. Comparison of reconstructed 3D scene by our proposed method and GS approach are given in Fig. 4.8.

Synthetic RS benchmark [Kim et al., 2016]:

We further evaluated performances of GSBA, M-RSBA and 3-steps method using synthetic RS images form public benchmark 'Sequence 77' [START_REF] Kim | Direct semi-dense slam for rolling shutter cameras[END_REF]. Contrarily to the approach used in [START_REF] Kim | Direct semi-dense slam for rolling shutter cameras[END_REF] which requires smooth and continuous camera trajectory, we address the case of unordered sets of images. Thus, instead of using every frame of the video, we randomly picked 24 non-successive frames. The results in Fig. 4.9 show that C-RSBA successfully estimates camera poses near ground-truth trajectory and achieves correct 3D scene reconstruction. In contrast, GSBA and M-RSBA fail in achieving RS SfM.

Real Images

Finally we compared GSBA, M-RSBA and C-RSBA on two real RS image sequences. The first data sets [START_REF] Hedborg | Rolling shutter bundle adjustment[END_REF] captured by an iPhone4 camera for facade of warehouse and a road along wall. The second dataset shows a real complex building captured by a Logitech camera with strong RS effects. All images were captured with small read-out direction angles. The results shown in Fig. 4.10 confirmed our predication in section. 4.5.2 and the results of simulation experiments. GSBA suffers from distorted reconstruction. We can observe that the more strong distortion in RS image, the more deformations after SfM. It is important to realize that M-RSBA can not handle the case where input RS images with small scanning direction angles (down from 60 degrees). Strong deformations close to a plane were observed in 3D scene reconstructed with M-RSBA. Quite the contrary, C-RSBA provides significantly better reconstructions than GSBA and M-RSBA which collapse into degeneracy.

We also tested the whole 3-step pipeline on two a benchmarks [START_REF] Sturm | A benchmark for the evaluation of rgb-d slam systems[END_REF] in man-made indoor environment with available ground truth. Fig. 4.11 demonstrates that estimated trajectories by using our proposed approach are much closer to ground truth than by GS BA method.

Discussion and Conclusion

In this chapter, we propose a novel C-RSBA, which can successfully avoid planar degeneracy without any constraint on read out direction as in existing approaches. Note that image capture style with similar read-out directions are extremely natural and common in real applications while requirements of two distinct read-out directions will strongly limit the application range. Experiments with both real and synthetic data prove that the proposed method outperforms existing ones and can handle degeneracies pointed out in the literature. C-RSBA was successfully used as a final step in RSSfM pipeline. We believe that this work will help to take an extra step toward the use of RS cameras in SfM applications. Finally, since it can handle very strong RS effects, the proposed method can also be seen as a monocular instantaneous-speed measurement technique.

Chapter 5

RS Homography and its Applications

Introduction

Homography is one of the important concepts in 3D vision and has been studied for a long period. However, all the existing methods are only applicable to conventional GS cameras. Homography for RS cameras, has not been addressed before.

In this chapter, we investigate the computation of the homography matrix based on correspondences from a RS pair. We show that at least 36 point correspondences are needed in theory to compute such a matrix linearly, and then we derive a practical method which works with 13 correspondences. In addition, we present two essential applications in computer vision that use RS homography: 1) Plane-based relative pose estimation and 2) image stitching. We experimentally show that the proposed methods outperform state-of-the-art techniques as well as well-known commercial applications, basing on many synthetic and real datasets.

Related Work and Motivation

Estimating the camera motion by using point correspondences is one of the most studied minimal problems in computer vision. For example, with GS, at least 3 point matches are needed to estimate the absolute pose [START_REF] Gao | Complete solution classification for the perspective-three-point problem[END_REF]], while at least 5 are needed to recover the relative pose between two calibrated GS views [Nistér, 2004]. Given the higher complexity of RS projection model [START_REF] Meingast | Geometric models of rolling-shutter cameras[END_REF], more points are commonly needed. Methods for structure and motion estimation with RS images can be grouped into two categories (summarized in table. 5.1): optical flow and epipolar geometry.

Optical Flow methods:

In [START_REF] Zhuang | Rolling-shutteraware differential sfm and image rectification[END_REF], 8pt and 9pt linear solvers were developed to recover the relative pose of a RS camera that undergoes constant velocity and acceleration motion respectively. Unfortunately, consistency between the camera poses and their motion only holds with high-frame rates and smooth movements. In addition to the resulting high computation load, unordered image sets can not be processed. Epipolar Geometry: In multi-view reconstruction, many common configurations become critical with RS cameras and lead to reconstruction ambiguities. Authors in [START_REF] Albl | Degeneracies in rolling shutter sfm[END_REF] provide mathematical analysis for configurations with one, two or more views. They provide practical recipes on how to photograph with RS cameras to avoid reconstruction errors. This method can be used to unblock some situations but it is not a solution to the standard general SfM problem. Authors in [START_REF] Dai | Rolling shutter camera relative pose: generalized epipolar geometry[END_REF] introduce 20pt and 44pt linear solvers for pure translational and uniform motion models respectively. However, the pure translational motion assumption is not feasible to model the camera motion in most of practical applications. Although more general, the 44-point solution requires too many correspondences and is therefore not suitable for use with RANSAC (Random Sample Consensus).

GS RS epipolar

Differential RS geometry

In summary, estimating relative pose of RS cameras remains an open problem and there is a need for new methods which require less input data (i.e. number of matches) and which work for various camera configurations. With some acceptable constraints on the scene structure or on the camera motion, homography could be used instead of epipolar geometry to recover the relative pose with less point matches [START_REF] Hartley | Multiple view geometry in computer vision[END_REF], Zhou et al., 2012, Saurer et al., 2017]. It has many applications namely image rectification, image registration and plane-based camera relative pose estimation. However, none of previous work has attempted to adapt the homography to the RS case. Authors in [START_REF] Forssén | Rectifying rolling shutter video from hand-held devices[END_REF],Grundmann et al., 2012,Liu et al., 2013,Vasu et al., 2018] try to solve the RS correction problem by building multiple independent homographies between each of image rows or row-blocks.These parameterized homographies are actually local GS homographies. In order to avoid discontinuities across rows (blocks), complex functions are used to smoothly interpolate the homographies. But the major issue of this approach is that points on a given row (row-block) in the first image have to be matched with points which also belong to a row (row-block) in the second image. This obviously limits the number of matches even with small inter-frame motion.

In this chapter, we address the problem of computing the homography from two RS images. We first propose a theoretical 36pt linear solution and then derive a practical 13pt minimal solver that gives good estimates of the geometry between two RS views. We also investigate the use of the proposed method for two major computer vision applications:

Plane-based Relative Pose Estimation: Although the RS relative pose problem has been addressed before [START_REF] Dai | Rolling shutter camera relative pose: generalized epipolar geometry[END_REF], Zhuang et al., 2017], a more efficient and robust solution is proposed by using RS homography in this paper. This solution can also be used in plane-based RS SfM and SLAM.

Image Stitching: Users nowadays frequently create panoramas from videos by rotating RS cameras, e.g. 'Pano' mode in iPhone. Besides, 360 VR images such as Street View could also be taken with RS cameras installed on a moving platform such as the Google car [START_REF] Klingner | Street view motion-from-structure-from-motion[END_REF]. As shown in Fig. 5.1(b-e), the most well-known commercial stitching software or state-of-the-art methods, which are based on the GS model, lead to poor results in the presence of RS effects. Therefore, designing a RS stitching method by using RS homography will be of valuable significance.

Chapter outlines

The rest of the chapter is organized as follows:

• Then we derive the full and the simplified RS homography matrices in section 5.4 followed by the solutions for the RS homography matrix computation from point matches in section 5.5.

• Next we show how to estimate the RS relative pose basing on a planar scene in section 5.6 and also RS image stitching by using RS homography in section 5.7.

• Finally, we present experimental results obtained thanks to the proposed methods in section 5.8.

GS Homography

Let us assume that a planar object is observed from two GS cameras at the poses [I|0] and [R 0 |t 0 ]. The transformation between the two corresponding image points q i and q i can be written as:

α i q i = Hq i = (R 0 - t 0 n d )q i , α i = z /z (5.1)
where α i is a scale factor that depends on the depth of P i in each camera. H GS is the 3 × 3 GS homography matrix, n is the normal vector of the observed plane and d is the distance from the first camera to the plane under the constraint n P i + d = 0. Note that we assume that each of the two cameras is calibrated. Thus, the normalized image point q i can be obtained by multiplying image measurement point m i by K -1 .

RS Homography

RS Relative Pose

Let us consider n 3D points P i imaged by two RS cameras at poses

[R v i |t v i ] and [R v i |t v i ],
as q i = [u i , v i , 1] and q i = [u i , v i , 1] in the two images respectively.

[I|0] and [R 0 |t 0 ] are the camera poses of the first row of each image. Thus, the rotation R i and the translation t i between the the row v i in the first image and the row v i in the second image are:

R i = (I + [ω 2 ] × v i )R 0 (I -[ω 1 ] × v i ) t i = t 0 + d 2 v i -(I + [ω 2 ] × v i )R 0 (I -[ω 1 ] × v i )d 1 v i (5.2)
where {ω 1 , d 1 } and {ω 2 , d 2 } are instantaneous-motion parameters of the two RS cam- eras.

Proof of Eq. (5.2). We assume a 3D point P in world coordinates is expressed as P v i and P v i in the two camera coordinate systems. The transformations are written as:

P v i = R v i P + t v i (5.3)
and Proof of Eq. (5.9) For convenience, we denote R i , t i in Eq. (5.2) and n i , d i in Eq. (5.8) as:

R i = R 0 + R 1 v i + R 2 v i + R 3 v i v i t i = t 0 + t 1 v i + t 2 v i + t 3 v 2 i + t 4 v i v i + t 5 v 2 i v i - n i d i ≈ - n 0 -n 0 [ω 1 ] × v i d 0 = N 0 + N 1 v i (5.12)
where,

       R 0 = R 0 R 1 = -R 0 [ω 1 ] × R 2 = [ω 2 ] × R 0 R 3 = -[ω 2 ] × R 0 [ω 1 ] ×                t 0 = t 0 t 1 = -R 0 d 1 t 2 = d 2 t 3 = R 0 [ω 1 ] × d 1 t 4 = -[ω 2 ] × R 0 d 1 t 5 = [ω 2 ] × R 0 [ω 1 ] × d 1    N 0 = - n 0 d 0 N 1 = n 0 [ω 1 ] × d 0
(5.13) By substituting Eq. 5.12 into Eq.5.1, we can obtain Eq. (5.9):

H RS = R i - t i n i d i = (R 0 + R 1 v i + R 2 v i + R 3 v i v i ) + (t 0 + t 1 v i + t 2 v i + t 3 v 2 i + t 4 v i v i + t 5 v 2 i v i )(N 0 + N 1 v i ) = (R 0 + t 0 N 0 ) H GS + (R 1 + t 1 N 0 + t 0 N 1 ) H 1 v i + (R 2 + t 2 N 0 ) H 2 v i + (R 3 + t 4 N 0 + t 2 N 1 ) H 3 v i v i + (t 3 N 0 + t 1 N 1 ) H 4 v 2 i + (t 5 N 0 + t 4 N 1 ) H 5 v 2 i v i + (t 3 N 1 ) H 6 v 3 i + (t 5 N 1 ) H 7 v 3 i v i
(5.14)

Simplified RS Homography Matrix

Approximation of RS Relative Pose.

Under the small rotation assumption, the second and higher order terms in Eq. ( 5.2) can be ignored. This simplification is also used in [START_REF] Albl | R6p-rolling shutter absolute camera pose[END_REF], Ito and Okatani, , Purkait and Zach, 2017, Lao et al., 2018a]. This approximation can be justified in that we force the translational speed vectors d 1 and d 2 to be constant in the world coordinate system, which is physically coherent with the constant velocity kinematic model. Therefore, we obtain an approximate expression of RS relative pose:

R i = R 0 -R 0 [ω 1 ] × v i + [ω 2 ] × R 0 v i t i = t 0 + d 2 v i -R 0 d 1 v i (5.15)

Approximation of the Plane Pose.

In practice, since the translation during acquisition is commonly much smaller than the distance from the camera to the scene plane, we can ignore the terms affected by translational velocities. In addition, we drop the second order terms, and obtain the approximate expressions:

n i = n 0 (I -[ω 1 ] × v i ) d i = d 0 -n 0 d 1 v i ≈ d 0 (5.16)

Derivation of the Simplified RS Homography Matrix

Using both approximations in Eq. ( 5.15) and (5.16), the RS homography matrix H RS between the row v i and the row v i in the two images can be simplified as follows:

H RS,i =H GS + A 1 v i + A 2 v i where, A 1 = -R 0 [ω 1 ] × + R 0 d 1 n 0 d 0 + t 0 n 0 [ω 1 ] × d 0 A 2 = [ω 2 ] × R 0 - d 2 n 0 d 0
(5.17)

A 1 and A 2 are two atomic matrices. Note that the RS homography matrix consists of the GS homography matrix H GS defined in Eq. ( 5.1) and of the two matrices A 1 , A 2 which contain the instantaneous-motion parameters. For readability, we denote H RS as H in the rest of the paper.

Proof of the Eq. (5.17). By substituting Eq. ( 5.15) and (5.16) into Eq. (5.9), we have:

H RS =R i - t i n i d i =R 0 -R 0 [ω 1 ] × v i + [ω 2 ] × R 0 v i - t 0 n 0 + d 2 n 0 v i -R 0 d 1 n 0 v i -t 0 n 0 [ω 1 ] × v i d 0 =(R 0 - t 0 n 0 d ) + (-R 0 [ω 1 ] × + R 0 d 1 n 0 d 0 + t 0 n 0 [ω 1 ] × d 0 )v i + ([ω 2 ] × R 0 - d 2 n 0 d 0 )v i =H GS + A 1 v i + A 2 v i (5.18)

Comparisons of Full Model and Simplified Model

The GS homography and three RS homographies are summarized into table. 5.1. We propose to use simplified model instead of completed model for RS relative pose and instantaneous-motions estimation for the following reasons:

1. Both [START_REF] Dai | Rolling shutter camera relative pose: generalized epipolar geometry[END_REF] and complete RS homography, which require 44 and 36 point matches respectively, are intractable to use in RANSAC estimation. In contrast, simplified RS model requires significantly less point matches (13 in total).

2. In practical applications, the simplified RS homography provides similar accuracy compared to the complete RS homography. A simulated experiment is conducted to justify the validity of the proposed simplified RS homography model. We simulated 60 feature points (within a planar object) and observed by two RS cameras positioned randomly on a sphere of radius of 100m. Then the mean projection errors (Euclidean distance) between Hq i and corresponding q i , where H are calculated by using GS-based homography H GS , complete RS homography H R S (in Eq. (5.9)) and simplified H RS (in Eq. (5.17)) respectively. We varied the norm value of camera rotational velocities from 0 to 30 deg/frame and translational velocities from 0 to 30 m/frame, which are both even too high to achieve in real applications. Results in Fig. 5.2 show that the simplified RS homography achieves similar accuracy to the completed RS homography model, while being much better compared to the GS one.

Base on the comparison above, we believe that simplified RS model is with higher practicality than the complete one.

RS Homography Estimation

4pt GS Homography Estimation

The homography matrix is usually computed using the Direct Linear Transform algorithm (DLT). From Eq. (5.1) we obtain q v i × H GS q i = 0. This gives two linearly independent equations:

0 -q i v i q i q i 0 -u i q i    H GS,(1) H GS,(2) H GS,(3)    = L i h GS = 0 (5.19)
where 0 = [0, 0, 0] and H GS,(i) is the i th row of H GS . Given n point correspondences (n 4), we obtain a system in the form Lh GS = 0 where L is a 2n × 9 matrix. The solution is then the singular vector associated to the smallest singular value of L.

36pt Full RS Homography Matrix Estimation

By setting H GS,33 = 1 and substituting Eq. (5.9) into h, Eq. ( 5.19) can be rewritten as follows:

M RS,i h RS =                                               0 q i -q i 0 v i [u i , v i ] -u i [u i , v i ] 0 v i q i -v i q i 0 v i v i q i -v i u i q i 0 v i q i -v i q i 0 v i 2 q i -u i v i q i 0 v i v i q i -v i v i q i 0 v i v i 2 q -u i v i v i q i 0 v i 2 q i -v i 2 q i 0 v i 2 v i q i -u i v i 2 q i 0 v i 2 v i q -v i 2 v i q i 0 v i 2 v i 2 q i -u i v i 2 v i q i 0 v i 3 q i -v i 3 q i 0 v i 3 v i q -u i v i 3 q i 0 v i 3 v i q i -v i 3 v i q i 0 v i 3 v i 2 q i -u i v i 3 v i q i                                                                                                   H GS,(
                                                    = b i = -v i u i (5.20)
where M RS,i is a 2 × 71 matrix while b i is a 2 × 1 vector. h RS is a 71 × 1 vector. 0 = [0, 0, 0] , H (i) , A 1,(i) and A 2,(i) are the i th rows of H GS , A 1 and A 2 respectively. Each point correspondence gives two constraints in Eq. (5.20). Thus, we obtain a system in the form M RS h RS = b which is solved using SVD.

13pt Simplified RS Homography Matrix Estimation

In the simplified case of section. 5.4.3, by setting H GS,33 = 1 and substituting Eq. (5.17) into h GS , Eq. ( 5.19) can be rewritten as:

               0 q i -q i 0 v i [u i , v i ] -u i [u i , v i ] 0 v i q i -v i q i 0 v i v i q i -v i u i q i 0 v i q i -v i q i 0 v i 2 q i -u i v i q i                                  H GS,(1) H GS,(2) H GS,31 H GS,32 A 1,(1) A 1,(2) A 1,(3) A 2,(1) A 2,(2) A 2,(3)                   = M RS,i h RS = b i = -v i u i (5.21)
where M RS,i reduces to a 2 × 26 matrix and b RS,i is a 26 × 1 vector. h is a 26 × 1 vector with by using SVD. In order to obtain stable results, we perform a normalization of M RS and b RS in the way explained in [Hartley andZisserman, 2003, Dai et al., 2016]. This 13pt minimal problem solver is used to extend the RANSAC pipeline [START_REF] Fischler | Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[END_REF] to the robust estimation of RS Homography with automatic matching.

Proof of the Eq. (5.21). By substituting Eq. (5.17) into h GS , the two linear independent equations in Eq. (5.19) can be rewritten as:

L RS1 h RS1 =                        u i v i v i u i v i 2 v i 2 v i v i v i 2 u i v i u i v i v i v i v i 2 v i 2 u i v i v i 1                                               A 1,31 A 2,31 A 1,32 A 2,32 -A 1,21 -A 2,21 + H GS,31 -A 2,22 + H GS,32 + A 1,33 -A 1,22 A 2,33 -H GS,21 -H GS,22 -A 1,23 H GS,33 -A 2,23 -H GS,23                        = 0 (5.22) L RS2 h RS2 =                              u i u i v i u i v i v i u i u i v i u i v i 2 u i v i u i v i u i u i u i v i u i v i v i v i v i 2 u i u i v i v i 1                                                           -A 2,31 -A 2,32 -A 1,31 -A 1,32 A 1,11 A 2,11 -H GS,31 -H GS,32 -A 1,33 -A 2,33 A 2,12 A 1,12 H GS,11 -H GS,33 H GS,12 + A 1,13 A 2,13 H GS,13                              = 0 (5.23)
where M i,jk is the component at j th row and k th column of the matrix M i . Without loss of generality, We can set H GS,33 = 1 and rewrite Eq. (5.22) and (5.23) in a unified matrix form:

               0 q i -q i 0 v i q i -u i q i 0 v i q i -v i q i 0 v i v i q i -v i u i q i 0 v i q i -v i q i 0 v i 2 q i -u i v i q i                2×27 matrix                     H (1) H (2) H GS,31 H GS,32 1 A 1,(1) A 1,(2) A 1,(3) A 2,(1) A 2,(2) A 2,(3)                     27×1 vector = 0
(5.24)

Eq. ( 5.24) can be solved directly using a DLT algorithm or rewritten in the non homogeneous form Ax = b as follow:

               0 q i -q i 0 v i [u i , v i ] -u i [u i , v i ] 0 v i q i -v i q i 0 v i v i q i -v i u i q i 0 v i q i -v i q i 0 v i 2 q i -u i v i q i                                  H GS,(1) H GS,(2) H GS,31 H GS,32 A 1,(1) A 1,(2) A 1,(3) A 2,(1) A 2,(2) A 2,(3)                   = -v i u i (5.25)
Thus, we obtain Eq. (5.21).

Plane-based RS Relative Pose and Instantaneous-motion Estimation

Relative pose

[R 0 |t 0 ] and plane normal vector n 0 : Once H GS is known, it can be decomposed into R 0 , t 0 and n 0 by using SVD. d 0 is set as 1 and absorbed by t 0 . Generally, this decomposition yields four solutions, where only one is physically meaningful considering the positive depth constraint [Ma et al., 2012, Malis and[START_REF] Malis | [END_REF].

Instantaneous-motion:

We can further retrieve instantaneous-motion parameters of the cameras thanks to two linear equation systems derived from matrices A 1 and A 2 :

1. First we compute ω

1 = ω x 1 , ω y 1 , ω z 1 and d 1 = d x 1 , d y 1 , d z 1 by using [R 0 |t 0 ]
and n 0 in matrix A 1 (6 unknowns with 9 equations).

Then we extract ω

2 = ω x 2 , ω y 2 , ω z 2 and d 2 = d x 2 , d y 2 , d z 2 from A 2 (6

unknowns with 9 equations).

Extracting ω 1 and d 1 from A 1 : Based on the definition of A 1 in Eq. (5.17), we obtain the following linear system in ω 1 and d 1 :

               0 -G 0,11 G 0,12 n x 0 R 0,(1) G 0,13 0 -G 0,11 n y 0 R 0,(1) -G 0,12 G 0,11 0 n z 0 R 0,(1) 0 -G 0,23 G 0,22 n x 0 R 0,(2) G 0,23 0 -G 0,21 n y 0 R 0,(2) -G 0,22 G 0,21 0 n z 0 R 0,(2) 0 -G 0,33 G 0,32 n x 0 R 0,(3) G 0,33 0 -G 0,31 n y 0 R 0,(3) -G 0,22 G 0,31 0 n z 0 R 0,(3)                        ω x 1 ω y 1 ω z 1 d x 1 d y 1 d z 1         = 0 (5.26)
where the auxiliary matrix G is defined as G = R 0 + t 0 n 0 . As a result, 6 unknowns in ω 1 and d 1 can be obtained by solving Eq. (5.26) linearly.

Extracting ω 2 and d 2 from A 2 : Based on the definition of A 2 in Eq. ( 5.17), we obtain the following linear system in ω 1 and d 1 :

   0 R 0,(3) -R 0,(2) -n 0 0 0 -R 0,(3) 0 R 0,(1) 0 -n 0 0 R 0,(2) R 0,(1) 0 0 0 -n 0            ω x 2 ω y 2 ω z 2 d x 2 d y 2 d z 2         = 0 (5.27)
Thus ω 2 and d 2 can be obtained by solving Eq. (5.27) linearly.

Nonlinear Refinement.

The final step consists in a nonlinear refinement of pose and instantaneous-motion parameters with n pairs of point matches which are the inliers from the 13pt-RANSAC. This is achieved by minimizing the following cost function where the full homography matrix is now used:

arg min R 0 ,t 0 ,n 0 ,d 0 ,ω 1 ,ω 2 ,d 1 ,d 2 = n ∑ i=1 (M RS,i h RS -b i ) 2
(5.28)

RS Image Stitching

Stitching Assumption

The goal of image stitching is to create a very wide angle image (or a panorama) from a set of images. After finding the homography matrix that aligns each pair of neighboring cameras, all the images are transformed so that they are mapped into the same projective space.

For that purpose, the cameras are assumed to have rotated about (approximately) the same centre of projection (Fig. 5.3). Thus, the RS homography matrix is further simplified by setting t i , d 1 and d 2 to 0, which leads to

H GS = R 0 , A 1 = -R 0 [ω 1 ] × and A 2 = [ω 2 ] × R 0 .

Stitching Pipeline

The proposed RS stitching pipeline consists of 4 steps: (1) RS homography estimation with 13pt solver: The RS homography matrix of coinciding optical centres has the same structure as the simplified RS homography matrix in Eq. (5.17). Thus, the 13pt method (section 5.5.3) is also feasible here.

(2) RS image alignment: When aligning two GS images all image points are directly mapped to new locations by applying q i = H GS q i . Differently, in the RS case we have

q i = (H GS + A 1 v i + A 2 v i )q i .
Note that the row index v i is present in both sides of the equation. Thus, the point coordinates mapping equation becomes a second degree equation which is solved as follows:

   v i = -b± √ b 2 -4ac 2a u i = (H GS,(1) +A 1,(1) v i +A 2,(1) v i )q i (H GS,(3) +A 1,(3) v i +A 2,(3) v i )q i where, a = A 2,(3) q i b = H GS,(3) q i + A 1,(3) q i v i -A 2,(2) q i c = -H GS,(2) q i -A 1,(3) q i v i
(5.29)

There are two feasible solutions for each pixel in the original image. The solution with the smaller Euclidean distance to original point before warping is chosen as the correct one. This is usually the solution which maintains the consistency of image registration as we will show through experiments.

(3) Blending: To seamlessly blend the images, a multi-band blending strategy [Burt andAdelson, 1983, Brown et al., 2003] is used. In this procedure, we first decompose the images into a set of band-pass filtered component images. Then a corresponding bandpass mosaic are generated by assembling the component images in each spatial frequency hand. Finally, we sum these band-pass mosaic images to obtain the desired image mosaic.

(4) Correction of stitched RS images: After determining the instantaneous-motion parameters by means of the method described in section 5.6, an inverse mapping is applied to the aligned image points in order to remove RS distortions by compensating camera instantaneous-motion as follows [START_REF] Lao | A robust method for strong rolling shutter effects correction using lines with automatic feature selection[END_REF]:

m correct = K 2 (I -[ω 2 ] × )q
(5.30)

Uncalibrated Image Stitching

Direct RS Image Alignment

In image stitching applications, it is common that the input images are uncalibrated.

Considering that points m i and m i are the image measurements in pixels (i.e [u i , v i , 1]) instead of normalized points, Eq. (5.21) gives the uncalibrated H image RS,i which is defined as follows:

H image GS = K 2 H GS K 1 -1 A image 1 = K 2 A 1 K 1 -1 A image 2 = K 2 A 2 K 1 -1 (5.31)
where K 1 and K 2 are the calibration matrices of the first and second cameras respectively.

Thus the 13pt method (section 5.5.3) can be used to align RS image directly in image space without prior knowledge of the calibration matrices K 1 and K 2 .

RS Correction of Uncalibrated Images

The determination of the instantaneous-motion parameters from A image 1 and A image 2 is different from the decomposition method of A 1 and A 2 described in section 5.6 since the calibration matrices are unknown.

Thus, basing on the pin-hole camera model, we assume that principle point is located in the centre of the image. Thus only the focal length f remains unknown. Now, the problem is to estimate the focal length f and instantaneous-motions ω 1 and ω 2 given

H image GS , A image 1 and A image 2
. We first set the focal length as 0.9 times of the maximal dimension of each corresponding image [Purkait and Zach, 2017]. By using the direct relative pose and instantaneous-motion algorithm in section 5.6, we can roughly estimate the rotation between the two images and angular velocities. Finally, we perform an iterative refinement to estimate the focal lengths, the rotation between cameras and instantaneous-motions as follows:

arg min f 1 , f 2 ,R 0 ,n 0 ω 1 ,ω 2 = n ∑ i=1 (M RS,i h RS -b i ) 2
(5.32)

With the estimated parameters, an inverse mapping similar to Eq. (5.30) is applied to the stitched image directly, as follows:

m correct = K 2 (I -[ω 2 ] × )K 2 -1 m (5.33)

Experiments

Both the RS homography-based pose estimation (RSH) and image stitching method presented in this chapter were evaluated on synthetic and real data. The proposed methods were also compared to GS homography methods such as:

• Classical GS-based homograhy relative pose estimation method (GSH) and its stitching application AutoStitch [START_REF] Brown | Automatic panoramic image stitching using invariant features[END_REF].

• Local multiple homography method: As-Projective-as-Possible stitching method (APAP) [START_REF] Zaragoza | Asprojective-as-possible image stitching with moving dlt[END_REF].

• Local multiple homography method: Adaptive as-natural-as-possible image stitching method (AANAP) [START_REF] Lin | Adaptive as-natural-as-possible image stitching[END_REF].

• Microsoft image stitching software: Image Composite Editor (ICE) [ICE, ].

• Stitching function in Adobe PhotoShop:

Photoshop [pho, ].
Results are summarized below.

Relative pose estimation

Synthetic data experiments

Experiment setting: We generated a planar scene with 60 feature points, which was imaged by two RS cameras with 480 × 640 image resolution. We set the distance from the plane to the optical centre of the first camera as 1 unit, and located the second camera randomly on a sphere around the centre of the plane with 1 unit length radius. Since the ground truth of the relative pose is known, we calculated the rotation error as e rot = arccos((tr(RR GT ) -1)/2) and the translation error as e trans = arccos(t t GT /( t t GT )).

We compared GSG and RSH by varying the noise in the image, the rotational and the translational speeds. The results are obtained after averaging the errors over 50 trials (the default setting is 1pixel noise, 10 degs/frame and 0.04 units/frame for the rotational and translational speed).

Relative pose estimation accuracy vs varying noise. We first tested the stability of the proposed method in the presence of image noise. Here we increased the random Gaussian image noise from 0 to 2pixels. Results in Fig. 5.4 show that the proposed method is more stable and achieves higher accuracy than GSH.

Relative pose estimation accuracy vs varying instantaneous-motion speed. We also evaluated the performances by increasing the rotational speed from 0 to 20 degs/frame and the translational speed from 0 to 0.08 units/frame receptively. As shown in Fig. 5.4, our method obtains obvious improvements comparing to GSH.

Number of detected inliers vs varying instantaneous-motion speed.

Finally, we investigated the influence of the RS instantaneous-motion on RANSAC-based inlier selection.

As shown in Fig. 5.5, with the increase of the camera instantaneous-motion, the inlier detection rate of GSH-RANSAC decreases dramatically. In contrast, the proposed GSH with RANSAC maintains its good performance.

Real data experiments (1) Plane-based trajectory estimation

For this experiment we used sequence '01' and '22' from [START_REF] Hedborg | Rolling shutter bundle adjustment[END_REF] which was captured by an iPhone4 camera. However, contrarily to [START_REF] Hedborg | Rolling shutter bundle adjustment[END_REF] and [START_REF] Zhuang | Rolling-shutteraware differential sfm and image rectification[END_REF] which require smooth motion input video, the proposed method can handle large baselines. Thus we just selected non-successive frames with 9 frames interval as an input sequence. We then performed RSH for the relative pose estimation and used camera-based RS bundle adjustment [Lao et al., 2018a] to refine the poses. Beside, we applied GSH to estimate the relative pose and run the GS plane-based bundle adjustment described but with known calibration matrix [START_REF] Zhou | Robust plane-based structure from motion[END_REF]. We used the method described in [START_REF] Hedborg | Rolling shutter bundle adjustment[END_REF] to calculate the trajectory error. The visual and quantitative evaluations summarized in Fig. 5.6 and Table 5.2 show that the proposed RSH method performs significantly better than GSH in both sequences.

(2) Plane-based SfM We evaluated both GSH and RSH on two more challenging RS image sequences from [START_REF] Lao | Rolling shutter pose and ego-motion estimation using shape-from-template[END_REF]: 'trans' and 'rot' which are taken with mainly translational and rotational velocities respectively. Two RS images of a chessboard (also present in the images) are chosen from the same sequence to estimate the relative pose with GSH and RSH. Then we perform a triangulation to reconstruct the chessboard (note that the pose of a row of RS image is obtained by using Eq. (6.8)).

Since the ground-truth of the poses are unknown, we use two methods to evaluate the accuracy of the relative pose estimation:

• Average homography transform errors of the feature points in the chessboard from the first image to the second.

• The reconstruction errors of the chessboard (each reconstructed 3D point is spatially aligned to the ground-truth, by minimizing the sum of all squared point-to-point distances).

The results presented in Fig. 5.7 and Table 5.2 show that RSH obtains significantly better results compared to GSH in both sequences.

Image Stitching

Synthetic Dataset

We first compared the performances of GSH, APAP, ANNAP and RSH on two synthetic RS image sequences with pure rotation from [START_REF] Forssén | Rectifying rolling shutter video from hand-held devices[END_REF]: 'rot1'(camera aim changing) and 'rot2'(both changing camera aim, and in-plane rotation).

In order to evaluate the stability of all the methods with different instantaneousmotions, we chose the first frame of each sequence as a reference, then we transformed and stitched all the other frames to it. We kept the number of input feature matches the same for all the three methods and calculated the average transformation errors.

The results in Fig. 5.9, Fig. 5.10, Fig. 5.11 and Fig. 5.12 show the stitching results of frame 1 to frames 2,3,...,12 in 'rot2' video sequence. The results summarized in Table . 5.3 show that the proposed method RSH clearly outperforms all the other methods.

The results in Fig. 5.8 show that in the only aim changing sequence, all the three methods obtain similar performances while RSH is slightly better than GSH and APAP in all the groups. However, with in-plane rotation, the transformation errors of GSH and APAP increase dramatically, while RSH performs obviously better.

Real Images

(1) Images from [START_REF] Forssén | Rectifying rolling shutter video from hand-held devices[END_REF]. The first input image pair is from a RS image sequence 'indicator' [START_REF] Forssén | Rectifying rolling shutter video from hand-held devices[END_REF] taken by an iPhone4. The second input is from a self-capture dataset 'facade' with strong RS effects. In Fig. 5.13, we can observe that AutoStitch produces blur on stitched images while the results from APAP are slightly better. The result of ICE in 'indicator' dataset is visually acceptable although significant misalignments can be observed along the pole. For the 'facade' dataset, ICE gives a dramatically mismatched result. Photoshop performances are visually good in both datasets, however, some wrong alignments are present such as the pole in the 'indicator' dataset and the eave in the 'facade' dataset. In contrast, HRS achieves the best results. After stitching, our method can remove the distortions and offers a much more visually pleasant stitching image as final outputs.

(2) Images from 'facade' sequence. In this experiment, we evaluate the stitching quality with varying number of point-matches by decreasing the number of point correspondences. We conduct this evaluations on 'facade' dataset. Results in Fig. 5.14 show that the multiple local homographies (spatially-varying warping) methods such as APAP and AANAP are sensitive to the number of input point-matches. With the decreasing of input matches, the quality of stitching results with APAP and AANAP declines dramatically. In contrast, the global methods GSH and RSH show a relative high stability.

(3) Images from [START_REF] Jia | Probabilistic 3-d motion estimation for rolling shutter video rectification from visual and inertial measurements[END_REF]. In this experiment, we evaluate all the stitching methods on a real RS images sequence from [START_REF] Jia | Probabilistic 3-d motion estimation for rolling shutter video rectification from visual and inertial measurements[END_REF] which captured a urban scene under fast rotation. The results in Fig. 5.15 and 5.16 show that AutoStitch fails in image alignment. APAP and AANAP provide blur stitching in regions with lack of point-matches. ICE and Photoshop provide visually pleasant results, however, geometry inconsistencies or 'object's fracture' are present along the stitching seams. In contrast, the proposed method RSH obtains the best results. Note that RSH can not align the nonrigid objects such as moving cars or pedestrians, nevertheless, APAP and AANAP are not able to handle it neither.

Discussion and Conclusion

The present work in this chapter is the first to address the homography for the RS case. We first defined a theoretical RS Homography matrix and proposed a 36pt solver to retrieve it from an image pair. Then we derived a simplified homography matrix and the associated 13pt minimal solver which is more suited for RANSAC based applications. The RS homography was successfully used in two well-known homography-based applications: relative pose estimation and image stitching. The experiment results show that the proposed method is superior to the state-of-the-art techniques and some wellknown commercial image editing applications. [START_REF] Zhuang | Rolling-shutteraware differential sfm and image rectification[END_REF].

AutoStitch

Chapter 6

Analogies between RS and Non-rigid Vision

Introduction

When looking at an image which is strongly distorted by RS effects, one immediately imagines that the scene is deforming as if it was non-rigid. Thus, it seemed us natural to investigate the possibility to take advantage from theoretical background of non-rigid vision methods to solve RS vision problems.

In this chapter, We propose new methods for the absolute camera pose problem (PnP) and structure from motion (SfM) which handles Rolling Shutter (RS) effects by drawing analogies with non-rigid vision (Fig. 6.1). Unlike all existing methods which perform 3D-2D registration after augmenting the Global Shutter (GS) projection model with the velocity parameters under various kinematic models, we propose to use local differential constraints.

Estimating RS camera pose and instantaneous motion. The main idea of estimating RS camera pose and instantaneous motion simultaneously (RS-PInP) consists in considering that RS distortions due to camera instantaneous-motion during image acquisition can be interpreted as virtual deformations of a template captured by a GS camera.

Once the virtual deformations have been recovered using Shape-from-Template (SfT), the camera pose and instantaneous-motion are computed by registering the deformed scene on the original template. This 3D-3D registration involves a 3D cost function based on the Euclidean point distance, more physically meaningful than the re-projection error or the algebraic distance based cost functions used in previous work. By transforming the RS PnP problem into a 3D-3D registration problem, we show that our RS-PInP solution is more robust and stable than existing works [START_REF] Albl | R6p-rolling shutter absolute camera pose[END_REF] because the constraints to be minimized are more physically meaningful and are all expressed in the same metric dimension.

Results on both synthetic and real data show that the proposed method outperforms existing RS pose estimation techniques in terms of accuracy and stability of performance in various configurations.

RSSfM.

We also propose a solution to the SfM problem for Rolling Shutter images (RSSfM) using an analogy with Non-Rigid SfM (NRSfM). This is an extension of the template-based analogy from a single view case to the multiple views and template-free case.

We propose the following two-step method for at least three RS images of an unknown scene. In the first step, RS distortions are used to compute one-to-one relative 3D deformations of points on the scene surface based only on their 2D measurements in at least three images. This is achieved thanks to the NRSfM method [START_REF] Parashar | Isometric non-rigid shape-from-motion with riemannian geometry solved in linear time[END_REF]. This step consists in relaxing the RS constraints (kinematic and projection models) and treating the distorted images as GS ones obtained under 3D deformations. Then, a new algorithm is proposed to simultaneously retrieve the actual structure, the camera poses and instantaneous-motions that correctly explain image distortions using the RS projection model and a constant velocity instantaneous-motion assumption. This second step, which reintroduces the RS constraint, is carried out by minimizing a non-linear cost function summing squared distances between 3D points. A strategy is proposed for the initialization of shape and motion parameters based on Generalized Procrustes Analysis (GPA) [START_REF] Bartoli | Stratified generalized procrustes analysis[END_REF].

Specifically, we show that this two step approach enables us to handle common singular configurations of classical RSSfM such as similar readout directions [START_REF] Albl | Degeneracies in rolling shutter sfm[END_REF]. We show experimentally that the proposed method outperforms state-of-art techniques.

Chapter outline. The rest of this chapter is organized as:

• We first review the related works about RS-PInP and RSSfM in section 6.2.

• We briefly introduce the two main techniques of non-rigid vision (section 6.3), namely SfT (section 6.3.1) and NRSfM (section 6.3.2).

• Then we show two analogies which build the links between RS-PInP problem and SfT (section 6.4.1), and between RSSfM and NRSfM (section 6.4.2).

• The details of the proposed RS-PInP method using SfT will be presented in section 6.5.

• The details of the proposed novel RSSfM method using NRSfM is introduced in section 6.6.

• Experiments are shown in section. 6.7 and section. 6.8.

Related Work

RS-PInP

One of the key issues in solving RS geometric problems is incorporating feasible camera instantaneous-motion into projection models. We give bellow the state-of-the-art works of RS-PInP:

• Saurer et al. [START_REF] Saurer | A minimal solution to the rolling shutter pose estimation problem[END_REF] propose a minimal solver to estimate RS camera pose based on the translation-only model with at least 5 3D-2D correspondences. However, this solution is limited to specific scenarios, such as a forward moving vehicle. It is not feasible for the majority of applications such as a hand-held camera, a drone or a moving robot, where instantaneous-rotation contributes significantly to RS effects [START_REF] Hedborg | Rolling shutter bundle adjustment[END_REF], Duchamp et al., 2015].

• Albl et al. [Albl et al., 2016a] propose another minimal solver, which also requires at least 5 3D-2D matches. It is based on a uniform instantaneous-motion model. Nevertheless, it also requires the assistance of inertial measurement units (IMUs), which makes the algorithm dependent on additional sensors. Albl et al. also propose a minimal and non-iterative solution to the RS-PInP problem called R6P [START_REF] Albl | R6p-rolling shutter absolute camera pose[END_REF], Albl et al., 2019], which can achieve higher accuracy than the standard P3P [START_REF] Haralick | Analysis and solutions of the three point perspective pose estimation problem[END_REF] by using an approximate doubly-linearized model. The approximation requires that the rotation between camera and world frames is small. Therefore, all 3D points need to be rotated first to satisfy the doublelinearization assumption based on a rough estimation from IMU measurements or P3P. This pre-processing step makes R6P suffer from dependencies on additional sensors or the risk that P3P gives a non satisfactory rough estimate. Besides, R6P gives up to 20 feasible solutions and no flawless recipe is provided to choose the right one, which may lead to unstable performances.Recently, [START_REF] Kukelova | Linear solution to the minimal absolute pose rolling shutter problem[END_REF] presents new efficient solutions to the RS camera absolute pose problem. Unlike R6P, we approach the problem using simple and fast linear solvers in an iterative scheme.

• Magerand et al. [START_REF] Magerand | Global optimization of object pose and motion from a single rolling shutter image with automatic 2d-3d matching[END_REF] present a polynomial projection model for RS cameras and propose the constrained global optimization of its parameters by means of a semidefinite programming problem obtained from the generalized problem of moments method. Contrarily to other methods, their optimization does not require an initialization and can be considered for automatic feature matching in a RANSAC framework. Unfortunately, the resolution is left to an automatic but computationally expensive solver.

In summary, a new efficient and stable solution to estimate the pose and instantaneousmotion of an RS camera under general motion, without the need for other sensors, is still absent from the literature. Such a solution is highly required for many potential applications.

RSSfM

The state-of-the-art works of RS-PInP are:

• The methods in [START_REF] Hedborg | Structure and motion estimation from rolling shutter video[END_REF], Zhuang et al., 2017, Im et al., 2018] use an RS video sequence to solve RSSfM by assuming smooth camera motion between every consecutive frames. This imposes a high acquisition framerate which results in high computational efficiency requirements. Unordered images with large baseline are not handled.

• The methods in [Ito and Okatani, ] attempts to solve RSSfM by establishing an equivalence with self-calibrated SfM. Nevertheless, the method has strong constraints, namely a purely rotational motion, an affine camera and the availability of one image without RS effects.

• The degeneracies of RSSfM were pointed out in [START_REF] Albl | Degeneracies in rolling shutter sfm[END_REF]. It is explained that when the images are taken at positions with similar readout directions, bundle adjustment (BA) with the RS model fails to recover structure and motion. The proposed solution is simply to avoid these degenerate configurations, by taking images at positions with close to perpendicular readout directions.

In summary, a new robust and stable solution to solve RSSfM with unordered images and without overly restrictive assumptions on camera motion, readout direction or projection model is still absent from the literature. Such a solution would be an important step in the potential widespread deployment of 3D vision with RS imaging systems.

Non-rigid Vision

There are two main methods in deformable 3D reconstruction from images (Fig. 6.2). These go by the names of Shape-from-Template (SfT), Non-Rigid Structure from Motion (NRSfM).

Shape-from-Template

SfT refers to the task of template-based monocular 3D reconstruction, which estimates the 3D shape of a deformable surface by using different physics-based deformation rules [START_REF] Salzmann | [END_REF]Fua, 2011,Bartoli et al., 2015]. Fig. 6.3 illustrates the geometric modeling of SfT. A 3D template τ ⊂ R 3 transforms to the deformed shape S ⊂ R 3 by a 3D deformation Ψ ∈ C 1 (τ, R 3 ). If Ω ⊂ R 2 is a 2D space obtained by flattening a 3D template τ, thus, an unknown deformed embedding ϕ ⊂ C 1 (Ω, R 3 ) maps a 2D point p ∈ Ω to Q ∈ S. Finally, Q can be projected onto an image point q ∈ I by a known GS-based projection function Π GS . The known transformation between Ω and I is denoted as η. It is obtained from 3D-2D point correspondences using Bsplines as in [START_REF] Brunet | Monocular templatebased 3d surface reconstruction: Convex inextensible and nonconvex isometric methods[END_REF]. The goal of SfT is to obtain the deformed surface S given p, q and the first order derivatives of the optical flow at p, namely ∂η ∂p (p). The deformation constraints used to solve SfT can be categorized as: Isometric deformation. The geodesic distances are preserved by the deformation [START_REF] Bartoli | Shape-from-template[END_REF], Salzmann and Fua, 2011, Brunet et al., 2014, Collins and Bartoli, 2015, Chhatkuli et al., 2017]. This assumption commonly holds for paper, cloth and volumetric objects. Conformal deformation. The isometric constraint can be relaxed to conformal deformation, which preserves angles since local scaling varies isotropically, and possibly handles isotropic extensible surfaces such as a balloon [START_REF] Bartoli | Shape-from-template[END_REF].

Elastic deformation. Linear [Malti et al., 2015,Malti and[START_REF] Malti | [END_REF] or non-linear [START_REF] Haouchine | Single view augmentation of 3d elastic objects[END_REF] elastic deformations are used to constrain extensible surfaces. Elastic SfT does not have local solution, in contrast to isometric SfT, and requires boundary condition to be available, as a set of known 3D surface points.

Non-rigid SfM

Conventional SfM allows the computation of a rigid object's 3D structure by given images of the object from different views. However, the rigidity constraints of SfM do not hold in many applications since real-world objects are more complex containing not only rigid motions but also non-rigid deformations, as well as their combination. Non-Rigid Structure-from-Motion (NRSfM) which uses multiple images of a deforming object to reconstruct its 3D, can solve such reconstruction problems.

The extension from SfM to the non-rigid case is by allowing the 3D points P i , to vary from frame to frame as follows:

P j i = P 1 i P 2 i . . . P m i (6.1)
Where P j i is the location of i th point at j th frame. In order to reduce the ill-posedness of the NRSfM problem, a prior or regularization is often employed such as: 1) the deformable model used (statistical [START_REF] Bregler | Recovering non-rigid 3d shape from image streams[END_REF], Akhter et al., 2009, Gotardo and Martinez, 2011a] or physical [START_REF] Varol | Template-free monocular reconstruction of deformable surfaces[END_REF], Taylor et al., 2010, Chhatkuli et al., 2018, Parashar et al., 2018]). 2) the camera model (weak [Gotardo and Martinez, 2011a, Gotardo and We define ψ j as a deformation that maps the original 3D structure P i from world coordinates into camera coordinates directly. Then the RS projection described in Eq. (2.11) may be re-written as:

m j i = Π RS (P j i ) = (Π GS • ψ j )(P i ) (6.4)
Analogy 2: Eq. ( 6.4) and Fig. 6.5 show that a set of RS images m j i of a rigid scene may also be interpreted by the same scene under deformations ψ j captured by multiple GS cameras.

Since the deformations are virtual, the 3D scene does not actually deform in the real world. Therefore, we called the original 3D shape P i as actual structure, the deformations ψ j as the virtual deformations, and the virtually deformed shape Pj i = ψ j (P i ) as the virtual deformed shape.

RS Pose and Instantaneous-motion Estimation using SfT

In this section, we introduce the proposed novel RS-PInP method, illustrated in Fig. 6.6, which first recovers the virtual template deformation using SfT and then computes the pose and velocity parameters using 3D-3D registration. Step 1: Given an RS image and a known 3D template, we reconstruct the virtually deformed shape using SfT.

Step 2: By performing 3D-3D registration between the virtually deformed shape and the template, RS camera pose and instantaneous-motion are obtained simultaneously.

Step 1: Reconstruction of the Virtual RS Deformed Shape

After showing the link between the RS-PInP and SfT problems, we focus on how to reconstruct the virtual deformed shape by using SfT. Since the assumption on the physical properties of the template plays a crucial role in solving the SfT problem we should determine which one of the deformation constraints can best describe the virtual deformation.

Equivalent RS Deformation under Different Instantaneous-motion Types

Any RS instantaneous-motion can be regarded as a combination of six atomic instantaneousmotions: translations along the X (d x ), Y (d y ), Z (d z ) axes and rotations about the X (ω x ), Y (ω y ), Z (ω z ) axes. Fig. 6.7 shows RS images and virtual deformed shapes produced by different types of RS instantaneous-motions. Albl et al. [Albl et al., 2016a] and Rengarajan et al. [START_REF] Rengarajan | Unrolling the shutter: Cnn to correct motion distortions[END_REF] illustrated four different types of RS effects (2D deformations) produced by camera instantaneous-motion. Differently, we focus on virtual 3D deformations instead. Fig. 6.7 also shows that the corresponding virtual deformations caused by different camera instantaneous-motions can be summarized into three types, by assuming a vertical scanning direction of the 3D template:

• (i) Horizontal wobble: Translation along the x-axis, rotation along the y-axis and zaxis creates surface wobble along the horizontal direction (perpendicular to the scan direction). In such cases, the distances are preserved only along the horizontal direction while the angles change during the deformation.

• (ii) Vertical shrinking/extension: Translation along the y-axis or rotation along the xaxis produce a similar effect, which shrinks or extends the 3D shape along the scan direction (vertical). This deformation preserves the distances along the horizontal direction but changes the angles. Thus, unlike an elastic deformation, stretching the The exact same images are also obtained as the projection of the corresponding virtually deformed 3D shapes (blue) into a GS camera (third row). The type of corresponding virtual deformations are also given, see main text for details.

surface in the vertical direction will not introduce a compression in the horizontal direction.

• (iii) Vertical wobble: Beside horizontal wobble, rotation along the z-axis also leads to wobble in the vertical direction. The distances along the horizontal direction remain unchanged while the angles vary dynamically.

Choosing the Appropriate Physic Prior of SfT

It is important to notice that the virtual deformations do not follow any classical physicsbased SfT surface models such as isometry, conformity or elasticity: isometric surface deformation preserves the distances along all directions while the virtual distortion only preserves the distances along the horizontal direction. The conformal deformation is a relaxation of the isometric model, which allows local isotropic scaling and preserves the angles during deformation. However, it cannot describe how the virtual deformation FIGURE 6.8: Choosing the best virtual shape from conformal SfT. . angles change. The elastic surface stretches in one direction and generally produces extension in the orthogonal direction. In contrast, no shrinking or extension occurs along the horizontal direction during the virtual deformation. We focus on reconstructing the virtual deformed shape based on the isometric and conformal deformations for the following reasons:

• The isometric constraint holds along the horizontal direction on the 3D shapes.

Since the image acquisition time is commonly short, the effects of extension and compression of the 3D shape are limited, which makes the isometric model work in practice. Alternatively, the conformal model can reconstruct extensible 3D shapes [START_REF] Bartoli | Shape-from-template[END_REF]. Thus, the conformal model as a relaxation of the isometric model can be theoretically considered a better approximation to the virtual deformation.

• A complex virtual deformed shape will be produced if an RS camera is under general instantaneous-motion, composed of the six types of atomic motions. Therefore, different surface patches on the shape could be under different 3D deformations. Importantly, the isometric and conformal SfT solutions we used from [START_REF] Bartoli | Shape-from-template[END_REF] exploit local differential constraints and recover the local deformation around each point on the shape independently. The assumption we implicitly make is thus that the camera projection is GS in each neighbourhood. This turns out to be a very mild and valid assumption in practice.

• Analytical solutions to SfT using the isometric and conformal models are reported in [START_REF] Bartoli | Shape-from-template[END_REF], which are therefore faster and show the potential to form real-time applications [START_REF] Collins | realtime shapefrom-template: System and applications[END_REF]. In contrast, the existing solutions to the elastic model are made slower [START_REF] Malti | A linear least-squares solution to elastic shape-from-template[END_REF][START_REF] Malti | [END_REF] and require boundary conditions unavailable in RS-PInP.

Isometric deformation. Bartoli et al. showed that only one solution exists to isometric surface reconstitution from a single view and proposed the first analytical algorithm [START_REF] Bartoli | Shape-from-template[END_REF]. A stable solution framework for isometric SfT has been proposed later [START_REF] Chhatkuli | A stable analytical framework for isometric shape-from-template by surface integration[END_REF]. Thanks to the existing isometric algorithms, we can stably and efficiently obtain a single reconstruction of virtual deformed shape Ψ RS (P i ).

Conformal deformation. Contrarily to the isometric case, conformal-based SfT theoretically yields a small, discrete set of solutions (at least two) and a global scale ambiguity [START_REF] Bartoli | Shape-from-template[END_REF]. Thus, we obtain multiple reconstructed virtual deformed shapes by using the analytical SfT method under the conformal constraint. However, only one reconstruction is close to the real virtual deformed shape Ψ RS (P i ). Therefore, we pick up the most practically reasonable reconstruction based on distance preservation along the horizontal direction. We assume that a total of m reconstructed shapes Ψ RS j (P), j = 1, 2..., m are obtained. As shown in Fig. 6.8 the 2D points located close to each other in the scanning direction in the image are segmented into b groups G k , k ∈ [1, b] of N k points. In the experiments, we group two 2D points into the same group if their difference of row index is lower than a threshold (experimentally set as 5 pixels). Then, we calculate a global scale factor s j of each reconstructed virtual deformed shape to the template by

using s j = 2 n(n-1) ∑ i,i ∈[1,n],i =i d ii /d j ii
, where d ii is the euclidean distance between 3D points P i and P i and d j ii is the euclidean distance of the corresponding reconstructed 3D points Ψ RS j (P i ) and Ψ RS j (P i ). We choose i, i ∈ [1, n] randomly and calculate the average value. Finally, we choose the reconstruction Ψ RS j (P) with the smallest sum of distance differences along the horizontal direction between each virtual deformed shapes x d j ii and known 3D template x d ii as the best solution:

arg min j∈[1,m] b ∑ k=1 ∑ i,i ∈[1,N k ], i =i |s j x d j ii -x d ii | (6.5)

6.5.2

Step 2: Camera Pose and Instantaneous-motion Computation

Instantaneous-motion model

Since the acquisition time of a frame is commonly short, one can generally assume a uniform kinematic model (with constant translational and rotational velocities). Moreover, by considering small rotation angles, we obtain the so-called linearized model, which has been used in many applications [START_REF] Magerand | Global optimization of object pose and motion from a single rolling shutter image with automatic 2d-3d matching[END_REF], Albl et al., 2015, Dai et al., 2016[START_REF] Albl | Degeneracies in rolling shutter sfm[END_REF] as shown in Eq. (2.14).

3D-3D Registration

After obtaining the virtual shape Ψ RS (P), we register the virtually deformed shape to the known 3D template P using the RS instantaneous-motion model. By iteratively minimizing the distance errors between the known 3D template and the reconstructed virtual shape, we obtain the camera pose and instantaneous-motion parameters simultaneously:

arg min R 0 ,t 0 ,ω,d n ∑ i=1 R(v i )P i + t(v i ) -Ψ RS (P i ) (6.6)
Actually, we slightly abused the term 'registration' to mean that the 3D points of the virtually deformed surface are fitted with the corresponding 3D points of the template. This can be seen as a registration where the recovered parameters are not a mere rigid transformation but a local motion with constant velocity.

Initialization: we initialize the parameters in Eq. (6.6) as follows:

• R 0 and t 0 are initialized using a classical PnP method [START_REF] Haralick | Analysis and solutions of the three point perspective pose estimation problem[END_REF].

• The instantaneous-motion parameters (ω,d) are initialized by the following two steps: (1) Group image points into sets of vertically close points (so that the RS effect can be neglected) and run P3P for each set. (2) Initialize d and ω by computing the relative translation and rotation between groups and dividing by the scan time.

Alternatively, we can operate in the same procedure by grouping the points of the deformed surface into subsets of close 3D points, which are registered by 3D point could transformations [START_REF] Horn | Closed-form solution of absolute orientation using orthonormal matrices[END_REF].

However, in many practical situations, it is more convenient and more efficient to set the initial values of d and ω to 0, which in our experiments always allowed convergence toward the correct solution.

Solving RSSfM Using NRSfM

In this section, we introduce the proposed RSSfM method, illustrated in Fig. 6.9, which first recovers the virtual deformed structure for each input RS image using NRSfM and then computes the actual structure, camera pose and instantaneous-motion using 3D-3D RS registration.

Step 1: Reconstruction of the one-to-one virtual deformed shapes

Choosing the Appropriate NRSfM Method. NRSfM aims to recover the 3D shapes of an object under deformation from a set of 2D GS images. Thus, it allows us to reconstruct the virtual deformed shapes Pj i for every RS image. Various NR-SfM methods have been presented over the last two decades. For example, [START_REF] Hu | Fast and accurate matrix completion via truncated nuclear norm regularization[END_REF] requires no missing data while [Agudo andMoreno-Noguer, 2015, Agudo et al., 2016] require rigid motion at the beginning of the sequence. [Akhter et al., 2009, Gotardo and[START_REF] Gotardo | Kernel nonrigid structure from motion[END_REF] require smooth video sequences. These assumptions do not hold with unordered RS image sets. Besides, some piece-wise methods [START_REF] Varol | Template-free monocular reconstruction of deformable surfaces[END_REF],Taylor et al., 2010,Russell et al., 2014] require a segmentation of the image domain into regions, which may be costly with large input datasets or unavailable.

However, as our discussion in section 6.3.2, not all of them are suitable for RSSfM. In this paper, we use isometric NRSfM (Iso-NRSfM) [START_REF] Parashar | Isometric non-rigid shape-from-motion with riemannian geometry solved in linear time[END_REF] to reconstruct the virtual deformed shapes for the following reasons:

1. Isometry is a good constraint to model the virtual deformation [START_REF] Lao | Rolling shutter pose and ego-motion estimation using shape-from-template[END_REF].

2. It handles missing data due to occlusions and unordered input images. 3) It requires m ≥ 3 views with linear complexity in the number of views and points, and thus combines the use of minimal data with higher efficiency than the other NRSfM methods.

General isometric NRSfM. The Iso-NRSfM method models the object's 3D shape for each image by a Riemannian manifold and deformations as isometric mappings. Each manifold is parameterized by embedding the corresponding retinal plane. This modeling allows one to reason on the metric tensor and Christoffel Symbols, directly in retinal coordinates, and in relationship to the inter-image warps, which can be computed from point-matches between images. Based on the theorem that the metric tensor and Christoffel Symbols may be transferred between views using only the warps, a system of RS image 1 RS image 2 RS image m Input: Unordered RS images Computed virtual deformed shapes

Step 1: NRSfM

Virtual shape 1 Virtual shape 2 Virtual shape m

Step 2: 3D-3D RS registration Step 1: Given multiple RS images, the virtually deformed shape is reconstructed for each image using NRSfM.

Step 2: By performing an iterative 3D-3D RS registration using Generalized Procrustes Analysis and RS pose estimation as initialization, the actual structure, camera pose and instantaneous-motion are obtained simultaneously. FIGURE 6.10: The 3D-3D registration, recovers the actual shape P i (green) by minimizing the sum of squares of the distance differences between re-deformed shapes (black) Pj i and the virtual deformed shapes Pj i (red, yellow and blue) recovered by the NRSfM.

two quartics in two variables that involves up to second order derivatives of the warps can be created for an infinitesimally planar surface at each point. The solution of this system are normals of the surface in all views. The shapes can finally be recovered by integrating the normal fields for each view.

Isometric NRSfM with the infinitesimal planarity assumption. In infinitesimal planarity, one assumes that a surface is at each point locally planar. Thus the surface is globally curved and represented infinitesimally by a set of planes. Since we assume the linearized model for RS instantaneous-motion, the virtual deformations are quasi continuous and smooth in the case of wobble, shrinking and extension [START_REF] Lao | Rolling shutter pose and ego-motion estimation using shape-from-template[END_REF], which can thus be interpreted by infinitesimal planarity. The general solution for Iso-NRSfM uses the solution with infinitesimal planarity as initialization. However, infinitesimal planarity (InfP-NRSfM) also alone gives good results while being much faster than the general algorithm. Therefore, we compare the use of both Iso-NRSfM and InfP-NRSfM to reconstruct the virtual deformed shapes in the experiments.

6.6.2

Step 2: Recovering the Actual Shape and Cameras

3D-3D Registration

After obtaining virtual deformed shapes Pj i for each view, we have to estimate the actual shape and camera pose and instantaneous-motion. However, the transformations from the actual shape to the virtual deformed shapes are non-rigid. Therefore, as shown in Fig. 6.10, in order to estimate an accurate actual shape, pose and instantaneous-motion of each view, we design a specific 3D-3D registration by minimizing the sum of squares of the distance difference between re-deformed shapes Pj i and the virtual deformed shapes Pj i recovered by NRSfM:

arg min β = m ∑ j=1 n ∑ i=1 V j i Pj i - Pj i 2 with β = {P i } , R j 0 , t j 0 , ω j , d j Pj i = ψ j (P i ), (6.7)
where V j i ∈ [0, 1] indicates if a 3D point P i is visible in the j th image or not. The deformation function ψ j is constrained by the RS instantaneous-motion model. Various models have been presented in existing work such as SLERP [START_REF] Hedborg | Rolling shutter bundle adjustment[END_REF], Rodrigues formula [START_REF] Ait-Aider | Simultaneous object pose and velocity computation using a single view from a rolling shutter camera[END_REF] for the rotation and the constant accelerated translation [START_REF] Zhuang | Rolling-shutteraware differential sfm and image rectification[END_REF]. The proposed 3D-3D RS registration can easily equip with different RS instantaneous-motion models. Here, we use a constant velocity model (Eq. (2.14) which is a good compromise between accuracy and complexity and is widely used in previous RS works [START_REF] Magerand | Global optimization of object pose and motion from a single rolling shutter image with automatic 2d-3d matching[END_REF], Dai et al., 2016, Albl et al., 2015[START_REF] Albl | Degeneracies in rolling shutter sfm[END_REF][START_REF] Lao | Rolling shutter pose and ego-motion estimation using shape-from-template[END_REF]:

ψ j (P i ) = (I + [ω j ] × v j i )R j 0 P i + t j 0 + d j v j i (6.8)
The cost function in Eq. (6.7) being non-linear, the availability of a good initial guess for the actual surface points, camera pose and instantaneous-motion is crucial to ensure convergence toward the solution. This is addressed in the next section.

Shape, Pose and Instantaneous-Motion Initialization

We propose to use Generalized Procrustes Analysis (GPA) and RS pose estimation. GPA solves the problem of registering more than two observed shape data [START_REF] Dryden | Statistical shape analysis[END_REF]. In this problem, a reference shape which should be as similar as possible to all observed shapes and one global transformation per observed shape has to be computed. In RSSfM, we assume that the deformations of a given actual point P i in all images can be approximated by a random noise. Thus the actual scene could be close to the 'average' shape among all the virtual deformed shapes. We can then roughly estimate the actual scene {P i } by performing GPA using the virtual deformed shapes Pj i as observed shapes. Then using RS pose computation [START_REF] Lao | Rolling shutter pose and ego-motion estimation using shape-from-template[END_REF] from this rough computed actual scene and the RS images, we find the global camera pose R j 0 , t j 0 and instantaneousmotion ω j , d j to initialize the optimization in Eq. (6.7).

Planar Degeneracy

The combination of NRSfM and the RS constraints makes the proposed two-step method work in the common degenerate configurations of RSSfM. An intuitive explanation to this desirable property is as follows. First, NRSfM reconstructs consistent virtually deformed shapes by considering that the viewed surface is locally smooth and differentiable. This is a convenient prior on the scene structure which, though widely applicable, is not used by any other RSSfM methods. Once the 3D surfaces are reconstructed for each image, the RS assumption serves to constrain the pose and instantaneous-motion parameters to be compatible with these while the degeneracy was already resolved at the first step.

We explain how using the 3D-3D error to recover the scene structure and camera motion instead of the reprojection error enables us to fix the degenerate configuration uncovered in [START_REF] Albl | Degeneracies in rolling shutter sfm[END_REF]. It is stated that any number of RS images with parallel readout directions can be explained by a planar scene. Bundle adjustment with the linearized RS model (RSBA) always converges toward this trivial solution. However this case is not degenerate for the proposed 3D-3D method.

We assume without loss of generality that an RS camera has the pose R 0 = I and t 0 = [0, 0, 0] , while the ground-truth of the instantaneous-motion is ω GT and d GT . According to Eq. (2.11) and (6.8), a 3D point P

GT i = [X, Y, Z] projects as m i = [u i , v i ] = Π GS ((I + [ω] × v i )P i + dv i ).
RSBA minimizes the sum of squares of the re-projection errors:

e i = m i -Π GS ((I + [ω] × v i )P i + dv i ) (6.9)
In our method however, the first step using NRSfM does not have degeneracies [START_REF] Parashar | Isometric non-rigid shape-from-motion with riemannian geometry solved in linear time[END_REF]. After obtaining the equivalent deformed shape Pj

i = (I + [ω GT ] × v i )P GT i + d GT v i ,
the second step uses the 3D-3D re-deformation error instead:

e i = Pi -Pi = Pi -((I + [ω] × v i )P i + dv i ) (6.10)
Obviously, both Eq. (6.9) and (6.10) vanish for the correct configuration

P i = P GT i , ω = ω GT , d = d GT .
However, if we alter the 3D scene and camera to the configuration P i = [X, 0, Z] , ω = [-1; 0; 0] , d = [0, 0, 0] , Eq. (6.9) still vanish, while Eq. (6.10) does not. This means that the RS images could be explained by projecting the 3D scene to the plane Y = 0 with the specific instantaneous-motion (ω = [-1; 0; 0] ). However, this ambiguity does not occur for the proposed 3D-3D RS registration.

Experiments of RS-PInP

In our experiments, the analytical isometric solution and analytical conformal solution are used to reconstruct the virtual deformed shape from RS images of both synthetic and real planar and non planar templates under isometric and conformal constraints respectively. The Levenberg-Marquardt algorithm is used in the non-linear pose and instantaneous-motion estimation from Eq. (6.6).

We compare the proposed methods to two state-of-the-art camera pose approaches:

• AnIRS: The analytical isometric solution [START_REF] Chhatkuli | A stable analytical framework for isometric shape-from-template by surface integration[END_REF] 1 .

• AnCRS: The analytical conformal solution (AnCRS) [START_REF] Bartoli | Shape-from-template[END_REF] 4 .

• GS-PnP: GS PnP solution2 [START_REF] Gao | Complete solution classification for the perspective-three-point problem[END_REF]].

• RS-PnP: The RS-PInP solution3 which uses R6P [START_REF] Albl | R6p-rolling shutter absolute camera pose[END_REF].

Synthetic Data

We simulated a calibrated pin-hole camera with 640 × 480 px resolution and 320 px focal length. The camera was located randomly on a sphere with a radius of 20 units and was pointing to a simulated surface (10 × 10 units) with varying average scanning angles from 0 to 90 deg. We drew n points on the surface to form the 3D template. Random Gaussian noise with standard deviation σ was also added to the 2D projected points m. We first evaluate the reconstruction accuracy of AnIRS and AnCRS on the virtual deformed shape. Since the types of deformation depend on the type of RS instantaneousmotion, we measure the mean and standard deviation of distances between the reconstructed 3D points and the corresponding points on the 3D template under six atomic instantaneous-motion types (section 6.5.1.1). For each motion type, we run 200 trials to obtain statistics. We varied the number of 3D-2D matches from 10 to 121 and used a noise level σ = 1 px. At each trial, the instantaneous-motion speed was randomly set as follows: translational speed varying from 0 to 3 units/frame and rotational speed varying from 0 to 20 deg/frame.

The results in Fig. 6.11 show that both AnIRS and AnCRS provide stable and high accuracy results for the virtual deformed shape reconstruction. The quantitative evaluation in Table 6.1 demonstrates that AnCRS generally performs better than AnIRS. Specifically, it indicates that the advantages of AnCRS are significant in the cases of instantaneousrotation along the x or z-axis. The only exception is in translation along the z-axis, where the virtual deformation is with relatively smaller extension/shrinking than other types. Thus, AnIRS gives better results than AnCRS. However, all observations confirm our analysis in section 6. In the first 10 frames, all four methods obtained acceptable reprojected matrix boundaries due to the small RS effects. However, finding more inliers does not ensure retrieving the true pose and instantaneous-motion, as RS-PnP yields 20 geometrically feasible solutions and it is challenging to pick the 'true' one. For example, Fig. 6.14(a) shows the estimated pose in our AR dataset, where only static camera frames (without instantaneousmotion) were picked. Fig. 6.14(b) shows that R6P gives distributed locations and huge instantaneous-motion up to 5m/frame, while P3P and our method give similar poses.

In the second frame, with the camera quickly moving, RS-PnP and The GS-based method GS-PnP provide unstable estimates of camera pose. In contrast, both proposed methods AnIRS and AnCRS significantly outperform GS-PnP and RS-PnP. It is noteworthy that AnCRS achieves slightly smaller reprojection errors than AnIRS. This coincides with the observations made in the synthetic experiments and confirms the theoretical analysis of section 6.5.1.1 that the conformal constraint is more suitable to explain the virtual deformations.

Pose Registration with Real RS Video

We tested the four methods for pose registration of an SfM reconstruction. The public dataset [START_REF] Hedborg | Rolling shutter bundle adjustment[END_REF] was used, which was captured by both RS and GS cameras installed on a rig. The 3D points were obtained by performing SfM with the GS images.

Running Time

The experiments were conducted on an i5 CPU at 2.8GHz with 4G RAM. On average, it took around 2.8s per frame for AnIRS (0.1s for isometric reconstruction and 2.7s for 3D-3D registration) and 14.6s for AnCRS (10.6s for conformal reconstruction and 4s for 3D-3D registration). Since the proposed method was implemented in MATLAB, an improvement can be expected when using C++ and GPU acceleration, as shown in [START_REF] Collins | realtime shapefrom-template: System and applications[END_REF].

Experiments of RSSfM

In our experiments, the Iso-NRSfM and InfP-NRSfM [START_REF] Parashar | Isometric non-rigid shape-from-motion with riemannian geometry solved in linear time[END_REF] 4 are both used to reconstruct the virtual deformed shapes. Then we use the stratified GPA method [START_REF] Bartoli | Stratified generalized procrustes analysis[END_REF] 5 to initialize the optimization described by Eq. (6.7) using the Levenberg-Marquardt algorithm. The proposed method was compared to four state-of-the-art techniques:

• SfM: An SfM method close to [Wu, 2011] 6 .

• RSBA [Albl et al., 2016b]: SfM followed by R6P [START_REF] Albl | R6p-rolling shutter absolute camera pose[END_REF] to initialize camera pose and instantaneous-motions, and refinement by RSBA.

• Iso-RSSfM: The proposed method with Iso-NRSfM.

• InfP-RSSfM: The proposed method with InfP-NRSfM.

Synthetic Data

We simulated RS cameras located randomly on a sphere with a radius of 20 units and pointing to a cylindrical surface consisting of 81 points. The size of the surface is 8 units × 8 units with a varying radius. The RS image size is 640p × 480p and the focal length 320p. We compared all methods by varying the instantaneous-motion speed, the noise on image measurements, the number of views, the surface curvature and the readout direction. The results are obtained after averaging the errors over 50 trials. The default setting is 15 degs/frame and 0.5 units/frame for rotational and translational speed, 1p noise, 6 views, 15 units radius (inverse curvature). (1) Reconstructing the virtual deformed shapes. We first evaluate the ability of InfP-RSSfM and Iso-RSSfM to reconstruct the virtual deformed shapes. Since the types of deformation depend on the type of RS instantaneous-motion, we measure the mean distance between the reconstructed 3D points and the corresponding ground truth 3D points computed by Eq. (6.4) and (6.8). The results in Fig. 6.17 and table 6.2 show that the two proposed methods accurately reconstruct the non-rigid shapes under different noise than RSBA even though its global performance is lower. Both proposed methods achieve the best performance with all noise levels.

(4) Varying number of views. Fig. 6.19 shows that all the four methods give descending errors from 3 to 12 views. InfP-RSSfM and Iso-RSSfM provide similar results, and better than SfM and RSBA.

(5) Varying curvature. In this experiment, we vary the radius of the surface (inverse of the curvature) from 5 to 30 units. The results in Fig. 6.19 show that all the four methods perform better with smaller curvature. The performance of InfP-RSSfM and Iso-RSSfM are the best among the compared methods. However, as expected Iso-RSSfM provides slightly better results than InfP-RSSfM when the curvature is large.

(6) Varying readout direction angle. We evaluate the robustness of the four methods with an RS critical motion sequence. We vary the readout directions of the cameras from parallel to perpendicular by increasing the mean angles between them from 0 deg to 90 degs (degenerate to stable). In Fig. 6.19, we observe that RSBA provides better results than SfM with at least 30 deg readout direction angle. While with smaller angle, the reconstruction error of RSBA grows dramatically, which means that it collapses into the planar degenerate solution. As expected from the analysis in section 6.6.2.3, InfP-RSSfM and Iso-RSSfM provides stable results under all settings.

(7) Data from public benchmark. We tested the four methods on synthetic RS image datasets from [START_REF] Forssén | Rectifying rolling shutter video from hand-held devices[END_REF]. We generated unordered image sets by randomly selecting 2 image triplets. In Fig. 6.20, we observe that quantitatively our methods work best in pose estimation and that qualitatively SfM obtains deformed reconstruction, while RSBA performs even worse and provides extremely deformed reconstruction. In contrast, InfP-RSSfM and Iso-RSSfM provide reconstructions close to ground truth.] 6.8.2 Real Data

Planar Marker Dataset

We use the RS video dataset from [START_REF] Lao | Rolling shutter pose and ego-motion estimation using shape-from-template[END_REF] which captures a chessboard with strong RS effects. First, the frames from the video sequence were manually categorized into vertical and horizontal readout direction. Then we designed two kinds of experiments: 1) We randomly chose 3 images from the 'vertical' group and 'horizontal' group respectively. 2) We randomly chose 6 images from the 'vertical' group only. Since the rigid 3D shape is known, we measured the mean distance difference between the computed and ground truth 3D points. The results in Fig. 6.21 show that SfM provides deformed reconstructions in both experiments. RSBA obtains better results than SfM in the provides deformed reconstructions for the two datasets. Since the readout directions are close to parallel, RSBA obtains extremely deformed results close to planar. InfP-RSSfM and Iso-RSSfM perform best in both the visual checking and quantitative evaluations for both datasets.

Running Time

The proposed methods were implemented in MATLAB. The experiments were conducted on an i5 CPU at 2.8GHz with 4G RAM. Table 6.3 summarises the results and shows that the running time of both InfP-RSSfM and Iso-RSSfM grows slightly with the increasing number of point correspondences and views.

Chapter 7

Conclusion and Future Work

The aim of this thesis is to address all the problems of 3D vision with RS images. These problems form the so called SfM pipeline. As shown in Fig. 7.1, we have proposed several algorithms that can be used for each step of the pipeline when images may show RS effects.

In chapter 3, we presented a single-image RS correction method which uses line features. Unlike existing methods, our method R4C is based on a linear computation of instantaneous-motion using few image features without any prior on scene geometry. Besides, the method was integrated in a RANSAC-like framework which enables us to reject outlier curves making image correction more robust and fully automated. Specifically, our method not only produces visually pleasant corrections, but also preserves consistency of geometry. Thus, the proposed method has been integrated in a 3-steps RSSfM which uses corrected images.

In chapter 4, we proposed a novel C-RSBA to be as final refinement method. Contrarily to classical BA, C-RSBA successfully avoid planar degeneracy which tends to flatten the reconstructed 3D scene when scanning directions of input image sequence are similar or close. With C-RSBA, we relax the constraint on capture style suggested by other authors to handle this degeneracy, and thus extend the use of RS cameras in realistic image capture conditions.

In chapter 5 we proposed a new matrix for the RS case that is equivalent to homography matrix. We first defined the theoretical RS Homography matrix and proposed a solver to retrieve it from an image pair. Then we derived a simplified homography matrix and the associated minimal solver which is more suited for RANSAC based applications. This RS homography was used as the basis for extending two well-known homography-based methods, i.e. relative pose estimation and image stitching, to the RS case.

Within chapter 6, we proposed for the first time a completely different approach to achieve 3D vision with RS images. This consists in establishing an analogy between deformable-surface vision and RS effects. We presented a novel method which addresses the RS-PEnP problem: using SfT. By analyzing the link between the SfT and RS-PEnP problems we have shown that RS effects can be explained by the GS projection of a virtually deformed shape. As a result the RS-PEnP is expressed as a 3D-3D registration problem. The proposed solution outperforms existing RS-PEnP techniques in terms of accuracy and stability. We also established an analogy between SfM with multiple RS images and Non-Rigid SfM. We proposed a novel solution for RSSfM by showing that the RS effects in multiple images can be explained by multiple one-to-one virtual deformations of a 3D shape captured by GS cameras. Again, RSSfM is transformed into a 3D-3D registration problem that solved using more physically meaningful error functions.

All the proposed methods and algorithms were intensively tested using both synthetic and real data from famous benchmarks. We systematically compared our results to those obtained with the most related state-of-the-art methods. The experiment results show that the proposed methods are superior to the state-of-the-art techniques and outperform well known commercial image editing applications. In summary, the methods described in this manuscript:

• Handles common singular and degenerate configurations of RS image sequences.

• Do not make unattainable assumptions on scene geometry or camera kinematics.

• Outperform related state-of-the-art methods.

• Handle very strong RS effects.

We believe that this work will help to take an extra step toward the widespread of use of RS cameras in real-life computer vision applications.

Future Work. The very next steps of this work will be dedicated to making the proposed methods efficient and fully automated in realistic conditions.

First, an efficient implementation of the algorithms will be achieved by migrating the Matlab sources toward real-time compiled languages. Analytical expression of the Jacobian matrix would also help to make faster the steps based on non-linear optimization.

Beside, a careful analysis of the structure of the jacobian and the normal equation matrix may shows a sparse and specific structure that can be exploited to make the resolution more efficient.

Local effect of RS should also be studied. Although this effect is generally negligible, it is of theoretical interest to study how RS impacts feature detectors and descriptors. The goal is to boost the matching performances and to make the algorithms handle even higher speed motion.

Finally, the spatio-temporal projection models used for RS may be generalized and unified with other vision systems that are based on spatio-temporal acquisition principle. Obvious candidates are event-based cameras and dynamic-reconfigurable-ROI systems [START_REF] Dahmouche | Dynamic visual servoing from sequential regions of interest acquisition[END_REF].

1. 1

 1 RS cameras everywhere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Examples of RS effect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Applications of 3D vision with RS cameras . . . . . . . . . . . . . . . . . . 1.4 Overview of the main contributions of this thesis . . . . . . . . . . . . . . . 2.1 Camera imaging model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Exposure mechanism of GS cameras. . . . . . . . . . . . . . . . . . . . . . . 2.3 Exposure mechanism of RS cameras. . . . . . . . . . . . . . . . . . . . . . . 2.4 GS projection model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 A simplified overview of classical SfM pipeline. . . . . . . . . . . . . . . . 2.6 RS projection model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 Problem statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.1 Overview of the proposed RS correction and RSSfM method using straightness constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Comparsion of the proposed RS correction method and existing work. . . 3.3 3D line representation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 3D line projection with different RS models. . . . . . . . . . . . . . . . . . . 3.5 Comparison of the three RS models . . . . . . . . . . . . . . . . . . . . . . . 3.6 Overview of automatic actual 3D line selection . . . . . . . . . . . . . . . . 3.7 An example of automatic feature slection . . . . . . . . . . . . . . . . . . . 3.8 Quantitatively evaluatition of the RS correction methods for grid scene . . 3.9 Visual comparision of the RS correction methods for grid scene . . . . . . 3.10 Visual and quantitative evaluations of RS correction methods on 'house' dataset. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.11 Visual comparison of RS correction methods on a public urban scene benchmark. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.12 Visual and quantitative evaluations of RS correction methods on an RS video. 3.13 Visual comparsions of RS correction methods on a challenging complex urban dataset. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Comparison of measurement-based RSBA and proposed camera-based RSBA 53 4.2 Two examples of double-projections pattern . . . . . . . . . . . . . . . . . . 4.3 How planar degeneracy raised? . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Comparaison of C-RSBA and M-RSBA reprojection errors . . . . . . . . . . 4.5 An example of reconstuction by GSBA, M-RSBA and C-RSBA with different read-out direction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 GSBA, M-RSBA and C-RSBA with varying read-out direction angles . . . 4.7 GSBA, M-RSBA and C-RSBA with different image noise . . . . . . . . . . 4.8 Reconstructed 3D scene by proposed method and GS method. . . . . . . . 4.9 SfM results of GSBA, M-RSBA and C-RSBA on synthetic dataset . . . . . . 4.10 SfM with unordered real RS images . . . . . . . . . . . . . . . . . . . . . . 4.11 SfM result with real RS images . . . . . . . . . . . . . . . . . . . . . . . . .

  FIGURE 1.1: CMOS cameras where rolling shutter commonly used are now wining the battle of current camera market against to CCD cameras.

  FIGURE 1.2: Images captured with a rolling shutter camera. (a) Rotating propeller captured with a static rolling shutter camera. (b) Moving rolling shutter camera, capturing a static scene. Due to the camera motion, distortion presents in the image.

FIGURE 1 . 4 :

 14 FIGURE 1.4: Overview of the main contributions of this thesis. We discuss the background theory, mathematical preliminaries and state-of-the-art in chapter. 2. Chapter. 3 presents our contributions to RS correction and the 3-steps RSSfM method. Chapter. 6 give our contributions to RS pose estimation and RSSfM using NRSfM. While our contributions to RS homography and bundle adjustment are shown in Chapter. 5 and Chapter. 4 respectively. Chapter. 7 presents our conclusions and perspectives for future work.

FIGURE 2 . 1 :

 21 FIGURE 2.1: Camera imaging model.

  FIGURE 2.4: GS projection model.

FIGURE 2 . 7 :

 27 FIGURE 2.7: The four RS vision problems we address in this manuscript.

FIGURE 3 . 1 :

 31 FIGURE 3.1: Overview of the proposed RS correction and RSSfM method using straightness constraint.

  FIGURE 3.2: (a) An example of a distorted RS image. (b)Arc segments detected by Purkait[Purkait et al., 2017] using LSD detector[Von Gioi et al., 2010] where outliers are also considered in correction. In contrast, the automatic feature selection in our method successfully filters outliers among detected candidate curves (d) and obtains correctly fitted curves (e). Final corrections by Purkait and our method are shown on (c) and (f).

  FIGURE 3.3: 3D line representation. The line can be treated as a line parallel to Z-axis passing through point (a, b, 0) within XY-Plane (green line shown in the left figure) which is then rotated by R to a new position (Shown on the right part). Thus, the final straight line passes through point R(ax + by), and is heading Rz, where x = [1, 0, 0] , y = [0, 1, 0] , z = [0, 0, 1] and R ∈ R 3 indices the rotation.

  FIGURE 3.4: 3D line projection with different RS models.

  7

  FIGURE 3.5: Projections of a 3D straight lines with different RS camera kinematics. (a) A simulated 3D straight line projected onto a 2D image as different forms of curves with no instantaneous-motion (green), linear (blue), rotate-only (pink) and uniform instantaneousmotion (yellow). Assuming the depth from the 3D straight line to camera as 1 unit length.Blue curves in (b) are the projection of a 3D line into a linear RS camera with linear velocities from 0.5 to 2.5 unit/s, while green line is for the GS case. The variations of Lin F 1 , Lin F 2 , Lin F 3 and Lin F 4 and constant value of GS F 3 are shown in (c).

FIGURE 3 . 7 :

 37 FIGURE 3.7: An example of automatic feature slection. Curves detected from the façade survived the first selection criteria, but not the 2 nd round where we perform the automatic feature selection to reject the outliers.

FIGURE 3 . 8 :

 38 FIGURE 3.8: Comparison of the proposed method with Rengarajan and Purkait under different configurations (varying angular velocities, translation velocity, outlier curves number and image noise). We use mean value of estimated rotation errors ērotate as a tool to quantitatively evaluate accuracy of instantaneous-motion estimation.

FIGURE 3 . 9 :

 39 FIGURE 3.9: Comparison of the proposed method with Rengarajan and Purkait under gentle condition (first column), large ω (second column), large d (third column) and outlier presence (fourth column).

  FIGURE 3.10: Comparison of R4C (f) with Rengarajan (c), CNN (d) and Purkait (e) on a synthetic RS image dataset [Forssén and Ringaby, 2010]. The correction results are evaluated by using mean value of estimated rotation errors ērotate of each row compared to ground truth.

FIGURE 3 .

 3 FIGURE 3.11: Visual comparison of the proposed method R4C with baselines Rengarajan, CNN and Purkait. The red boxes highlights the superiority of our method.

  FIGURE 3.12: An example frame from a RS video [Ringaby and Forssén, 2012] (a). The correction results by Rengarajan, CNN, Purkait and by our method R4C are shown in (b)-(e). A quantitative evaluation using the mean number of found inliers |R F | between corrected frame pairs are also shown below each corrected image.

FIGURE 4 . 1 :

 41 FIGURE 4.1: RS SfM with three BA frameworks. GSBA performs poorly in reconstruction due to RS effect presence. M-RSBA which uses image measurements to calculate reprojection points collapse into degeneracy and provides incorrect reconstruction when input images with parallel read-out directions. In contrast the proposed method C-RSBA which uses camerabased RS projection algorithm survives the degeneracy.

FIGURE 4 . 2 :

 42 FIGURE 4.2: Two examples of double-projections pattern. On the left, a RS camera is under pure translation heading to [0; 1; 0] T rapidly. Besides, a example of pure-rotation with axis (1, 0, 0) shown on the right. During the acquisition, a 3D point X will be observed twice at row v1 and v2 if the speeds are big enough.

FIGURE 4 . 3 :

 43 FIGURE 4.3: How planar degeneracy raised? Any RS image generated by 3D scene (green points) can also be explained by 3D points located in plane y = 0 with ω = [1; 0; 0] during acquisition. In such situation, all 3D points will projected to each row of image (on right side), thus, planar degeneracy raised.

FIGURE 4 . 4 :

 44 FIGURE 4.4: Comparaison of C-RSBA and M-RSBA reprojection errors. We perform M-RSBA using multiple RS views with parallel read-out directions. In each iteration during optimization, we also calculate overall reprojection errors by p m for M-RSBA (blue) and p c for C-RSBA (green) based.

FIGURE 4 . 5 :

 45 FIGURE 4.5: Reconstruction results of GSBA (blue), M-RSBA (red) and C-RSBA (green) by using images with parallel and perpendicular read-out directions in comparison to ground-truth (cyan).

FIGURE 4 . 6 :

 46 FIGURE 4.6: Reconstruction errors of GSBA, M-RSBA and C-RSBA with read-out direction angles varying from 0 to 90 degrees. M-RSBA provides better results than GSBA only when read-out direction angles are big (up to 60 degrees). C-RSBA obtains accurate reconstructions stably with varying direction angles.

  FIGURE 4.7: Simulated experiments with randomly distributed RS cameras. For each configuration, we perform GSBA, M-RSBA and C-RSBA with parallel (vertical) and perpendicular (vertical+horizontal) read-out directions respectively to achieve SfM with different image noise levels. The estimation errors of rotation (a), translation (b) and reconstruction (c) demonstrate that with small read-out direction angle, M-RSBA fails while C-RSBA provides highest quality estimation in both parallel and perpendicular read-out directions cases.

FIGURE 4 . 8 :

 48 FIGURE 4.8: Reconstructed 3D scene by proposed method and GS method. 3D reconstructed scene by GS BA (left) and our proposed method (right) from front view (first row), side view (second row) and top view (third row).

  FIGURE 4.9: SfM with unordered images. (a) 24 non-successive frames from 'Sequence 77' as an input RS image set. SfM results of GSBA(c), M-RSBA(d) and C-RSBA(e) (the first and second columns are top and side views respectively). Compared to ground-truth shown in (b)[START_REF] Kim | Direct semi-dense slam for rolling shutter cameras[END_REF], GSBA and C-RSBA failed in motion calculation and obtains deformed 3D scene (tilt walls). While C-RSBA provided accurate camera poses and correct reconstruction. Loopclosing optimization and smooth trajectory assumption were not used.

FIGURE 4 .

 4 FIGURE 4.10: SfM with unordered real RS images. Input images (left) are with similar readout direction and M-RSBA reconstructions are below. Results of GSBA (middle) and C-RSBA (right) are compared together. Obviously, M-RSBA suffers from planar degeneracy, while significant deformations can also be observed in GSBA reconstructions. However, C-RSBA provides correct reconstructed 3D scene.

  FIGURE 4.11: (a)Example RS frame. (b) Comparison of proposed estimated trajectories by 3steps algorithm (blue) and GS BA (red) against to ground-truth (green). (d) Reconstructed 3D scene.

FIGURE 5

 5 FIGURE 5.1: RS images (a). Stitching results obtained with well-known commercial stitching applications such as AutoStitch [Brown and Lowe, 2007] (b) Microsoft Image Composite Editor (ICE) [ICE, ] (c) Adobe Photoshop [pho, ] (d) state-of-the-art multiple homographies stitching method APAP [Zaragoza et al., 2014] (e). The stitching results and the correction of the RS effects obtained with the the proposed method are shown in (f) and (g).

FIGURE 5 . 2 :

 52 FIGURE 5.2: Comparison of the GS, completed RS and simplified RS homographies.

  FIGURE 5.3: RS homographies in the general case (a) and in the pure-rotation case (b).

FIGURE 5

 5 FIGURE 5.4: Errors of relative pose estimation by using GSH and RSH with increasing image noise level (a), rotational speed (b) and translational speed(c).

FIGURE 5 . 5 :

 55 FIGURE 5.5: Rate of inliers by using GSH and RSH with increasing rotational speed and translational speed.

FIGURE 5

 5 FIGURE 5.6: Comparison of trajectory estimation (right sides) by using GSH and RSH on two RS image sequences (examples of input RS images are shown on the left side).

FIGURE 5 . 7 :

 57 FIGURE 5.7: Mapping and 3D reconstruction errors by using GSH and RSH on sequence 'trans' and 'rot' respectively.

FrameFIGURE 5

 5 FIGURE 5.9: Stitching frame02, frame03 and frame04 to frame01 of 'rot2' sequence.

FrameFIGURE 5

 5 FIGURE 5.10: Stitching frame05, frame06 and frame07 to frame01 of 'rot2' sequence.

FrameFIGURE 5

 5 FIGURE 5.11: Stitching frame08, frame09 and frame10 to frame01 of 'rot2' sequence.

FIGURE 5 .

 5 FIGURE 5.13: Results of real uncalibrated RS images stitching with different methods.

  FIGURE 5.14: The evaluations of stitching qualities by varying the number of input pointmatches.

  Photoshop

FIGURE 5 .

 5 FIGURE 5.17: RANSAC results (inliers in pink, outliers in green) for a pair of real RS images from[START_REF] Zhuang | Rolling-shutteraware differential sfm and image rectification[END_REF].

FIGURE 6 . 3 :

 63 FIGURE 6.3: Geometric modeling of SfT.

  FIGURE 6.5: Analogy 2: Equivalence between a rigid 3D scene filmed by multiple RS cameras and a non-rigid scene filmed by multiple GS cameras.

  FIGURE 6.6: An overview of the proposed pose and instantaneous-motion estimation method:Step 1: Given an RS image and a known 3D template, we reconstruct the virtually deformed shape using SfT.Step 2: By performing 3D-3D registration between the virtually deformed shape and the template, RS camera pose and instantaneous-motion are obtained simultaneously.

FIGURE 6

 6 FIGURE 6.7: The 3D template shapes (green) captured by a RS camera under different atomic instantaneous-motions (first and third row) yield distorted RS images (second and fourth row).The exact same images are also obtained as the projection of the corresponding virtually deformed 3D shapes (blue) into a GS camera (third row). The type of corresponding virtual deformations are also given, see main text for details.

FIGURE 6 . 9 :

 69 FIGURE 6.9: Overview of the proposed RSSfM method.Step 1: Given multiple RS images, the virtually deformed shape is reconstructed for each image using NRSfM.Step 2: By performing an iterative 3D-3D RS registration using Generalized Procrustes Analysis and RS pose estimation as initialization, the actual structure, camera pose and instantaneous-motion are obtained simultaneously.

FIGURE 6 .

 6 FIGURE 6.11: Reconstructed virtual deformed shapes by AnIRS (magenta points) and AnCRS (green crosses) compared to ground truth structure (blue circles) under six types of camera instantaneous-motion. TABLE 6.1: Mean (|e I |, |e C |) and standard deviation (σ I , σ C ) of reconstruction errors (expressed in units) of the virtual deformed shape by AnIRS and AnCRS under six types of camera instantaneous-motions.d x d y d z ω x ω y ω z |e I | 0.0130283 0.0113629 0.0001183 0.0023273 0.0020031 0.1338190 |e C | 0.0040963 0.0052104 0.0009037 0.0000921 0.0008493 0.0008417 σ I 0.0001810 0.0000943 0.0000014 0.0000834 0.0007209 0.0393570 σ C 0.0000318 0.0000529 0.0000310 0.0000206 0.0003639 0.0001201

  FIGURE 6.12: Pose estimation errors for AnIRS, AnCRS, GS-PnP and RS-PnP under different instantaneous-translations (a) and instantaneous-rotations (b).

  FIGURE 6.13: Pose estimation errors for AnIRS, AnCRS, GS-PnP and RS-PnP under different image noise levels (a) and number of matches (b).

  FIGURE 6.14: Pose and instantaneous-motion estimation by different methods with 10 frames with small RS effects.

FIGURE 6 .

 6 FIGURE 6.15: Visual comparison of reprojected object boundaries by different camera pose and instantaneous-motion estimates. e rp is the reprojection error of the 3D marker points.

  FIGURE 6.16: Results of pose registration with real RS video: (a) An example of input RS image. (b) Rotation and translation errors of each frame. (c) Estimated trajectories by GS-PnP, RS-PnP, AnIRS and AnCRS compared to ground truth.

FIGURE 6 .

 6 FIGURE 6.18: Reconstruction and pose estimation errors for SfM, RSBA, InfP-RSSfM and Iso-RSSfM with increasing rotational and translational speed.

FIGURE 6 .

 6 FIGURE 6.19: Reconstruction errors for SfM, RSBA, InfP-RSSfM and Iso-RSSfM under different noise levels in image, number of views, curvature and readout direction angle.

FIGURE 6 .

 6 FIGURE 6.20: Reconstruction results and pose estimation errors of SfM, RSBA, InfP-RSSfM and Iso-RSSfM for synthetic RS images dataset.

FIGURE 6 .

 6 FIGURE 6.21: Reconstructed shapes and mean of reconstruction errors E (expressed in units) of SfM, RSBA, InfP-RSSfM and Iso-RSSfM with 'vertical+horizontal' and 'vertical' as inputs respectively for the planar marker dataset.

  FIGURE 7.1: Revist of the contributions and organization of this thesis.

TABLE 3

 3

.1: Parametric representation of 3D straight line projection with different RS models

TABLE 4

 4

	.1: Comparison of GSBA, M-RSBA and C-RSBA.

TABLE 5 .

 5 1: Comparison of properties of existing RS relative pose solvers and the proposed solvers based on RS homography (RSH) in this chapter.

TABLE 5 .

 5

	GSH RSH

2: Errors of the trajectory estimation for 'seq01' and 'seq02'. Errors of homography transformation and 3D reconstruction for seq 'trans' and seq 'rot'.

TABLE 6 .

 6 2: Mean values (|e InfP |, |e Iso |) of reconstruction errors (expressed in units) of the virtual deformed shape by InfP-RSSfM and Iso-RSSfM under six types of camera instantaneousmotion.

https://fr.ids-imaging.com//technical-article//fr_tech-article-rolling-shutter-sensors.html

https://fr.ids-imaging.com//technical-article//fr_tech-article-rolling-shutter-sensors.html

Gyroscopes-based methods: Methods of [HeePark and Levoy, 2014,Jia and Evans, 2012,Patron-Perez et al., 2015] utilize gyroscopes to measure camera instantaneousmotion during acquisition and compensate RS effects directly.

3. Straightness constraint-based methods: After line features had been explored in object motion estimation [Ait-Aider et al., 2007], 3D straight lines have been also used for solving single RS image correction problem based on straightness [Ren-garajan et al., 2016] or vanishing direction[Purkait et al., 2017]

constraints. 4. Machine learning methods: Rengarajan et al. first developed a learning-based single RS correction method using Convolutional Neural Network (CNN) in [Rengarajan et al., 2017].2.4.2 RS Pose and Instantaneous-motion EstimationDefinition: The aim of RS pose and instantaneous-motion estimation (RS-PInP) is to calculate the pose of a calibrated RS camera and its instantaneous-motion from n 3D-2D correspondences.

The results are supplied by the authors upon request.

https://github.com/yogeshbalaji/CVPR17∼Unrolling∼the∼shutter

Self-implemented after having discussion with the authors.

http://igt.ip.uca.fr/∼ab/Research

estimateWorldCameraPose function in MATLAB

http://cmp.felk.cvut.cz/∼alblcene/r6p

http://igt.ip.uca.fr/∼ab/Research/Local-Iso-NRSfM_v1p1.zip

http://igt.ip.uca.fr/∼ab/Research/SGPA_v1p0.tar.gz

http://mathworks.com/help/vision/examples/structure-from-motion-from-multiple-views.html

Acknowledgements

sponsored by the French government research program "Investissements d'Avenir" through the IDEX-I-SITE initiative 16-IDEX-0001 (CAP 20-25), the IMobS3 Laboratory of Excellence (ANR-10-LABX-16-01). This research was also financed by the European Union through the Regional Competitiveness and Employment program -2014-2020-(ERDF -AURA region) and by the AURA region.

5.1 Compaprasions of RS image stitching by satyr-of-the-art methods, commercial softwares and the proposed method . . . . . . . . .

RS distorted Images

Correction by Rengarajan

Correction by Purkait

Correction by CNN Correction by R4C

(5.4) By substituting Eq. ( 5.3) into Eq. (5.4) and eliminating P, we obtain the transformation between P v i and P v i as:

(5.5)

Thus, the relative pose can be expressed as:

Then we substitute Eq (2.20) into Eq. (5.5), and we obtain:

(5.7)

RS Homography Matrix

When instantaneous-motion occurs during the acquisition, H between two RS cameras varies with different row combinations. The relative pose between row v i in the first image and the row v i in the second image is defined in Eq. (5.2). Similarly the plane normal and the distance to the plane are also changing dynamically with different row indexes. By using linear instantaneous-motion model, we can express the normal vector and distance to the plane w.r.t row v i as:

where n 0 and d 0 are the normal vector and the distance for the first row. By substituting Eq. (5.2) and (5.8) into Eq. (5.1), we obtain the expression of RS homography matrix as:

where H GS , H 1 ...H 7 are 3 × 3 atomic matrices.

Proof of Eq. (5.8) When the RS camera is at the pose of its first row, the plane constraint is:

By substituting the transform from P to P v i in Eq. ( 5.3) into Eq. (5.10), we obtain:

By substituting Eq. (2.20) into Eq. (5.11), we finally obtain Eq. (5.8).

Frame 11 to Frame 1

Frame 12 to Frame 1 FIGURE 5.12: Stitching frame11 and frame12 to frame01 of 'rot2' sequence.

(4) Images from [START_REF] Zhuang | Rolling-shutteraware differential sfm and image rectification[END_REF]. In this experiment, we evaluate all the stitching methods by using two real RS image from [START_REF] Zhuang | Rolling-shutteraware differential sfm and image rectification[END_REF], which have a large overlap region. As shown in Fig. 5.17, the inliers between the two images distribute densely in the right part of the two images while being limited to the white facade on the left part. The stitching results in Fig. 5.18 show that APAP and AANAP suffer from this unbalanced point-matches distribution and provide significant distortions on the stitched regions of the 'white facade'. Slight geometrical inconsistencies are present along the stitching seams of ICE and Photoshop's results. In contrast, the proposed method RSH obtains the best result.

Running Time

The experiments were conducted on an i5 CPU at 2.8GHz with 4G RAM. On average, it took around 3.35s for GSH, 13.5s for APAP and 6.5s for RSH(0.05s for 13pt solver running per time, 0.16s for the non-linear refinement, 5.9s for the image warping, blending and RS correction). Since the proposed method was implemented in MATLAB, a significant improvement can be expected when using C++. Martinez, 2011c] or full perspective [START_REF] Hartley | Perspective nonrigid shape and motion recovery[END_REF]). The fitness of the prior to deformation is a crucial element in successfully solving the NRSfM problem.

An Equivalence between RS Projection and Surface Deformation

In this section, we introduce two analogies between non-rigid vision and RS vision. The first analogy is between RS-PInP and SfT. The second is between RSSfM and NRSfM.

Analogy between RS-PInP and SfT

The main idea here is that distortions in RS images caused by camera instantaneousmotion can be expressed as the virtual deformation of a 3D shape captured by a GS camera. We first model the GS projection of a known 3D shape after a deformation Ψ:

If we define the deformation as Ψ RS (P i ) = R(v i )P i + t(v i ), Eq. ( 6.2) becomes similar to Eq. (2.11):

Analogy 1: Eq. ( 6.3) and Fig. 6.4 show that 3D shapes observed by a moving an RS camera are equivalent to corresponding deformed 3D shapes filmed by a GS camera.

We name this virtual corresponding deformation Ψ RS as the virtual deformation and the virtually equivalent deformed shape Ψ RS (P i ) as the virtual deformed shape.

Equivalence between RSSfM and NRSfM

Here, we extend the previousely defined analogy to the case with multiple RS images of an unknown shape. Namely, we consider different images of the same rigid surface taken by a moving RS camera as GS snapshots of a deforming 3D surface.

virtual deformation generally.

Pose estimation.

We compared AnIRS and AnCRS in camera pose estimation with both GS-PnP and RS-PnP. Since the ground truth of camera poses are known, we measured the absolute error of rotation (deg) and translation (units).

Accuracy vs instantaneous-motion speed. We fixed the number of 3D-2D matches to 60 and noise level to σ = 1 px. We increased the translational speed and rotational speed from 0 to 3 units/frame and 20 deg/frame gradually. At each configuration, we run 100 trials with random velocity directions and measured the average pose errors. The results in Fig. 6.12(a,b) show that both AnIRS and AnCRS provide significantly more accurate estimates of camera orientation and translation with all instantaneous-rotation configurations (ω x , ω y and ω z ) compared to GS-PnP and RS-PnP. Under three instantaneoustranslations, AnIRS and AnCRS show an obvious superiority in camera rotation estimation, and perform slightly better in camera translation estimation than RS-PnP. As expected, GS-based GS-PnP fails in pose estimation once the instantaneous-motion is strong. In contrast, RS-PnP achieves better results in translation than GS-PnP, but both of them provide an inaccurate estimate for camera rotation to the same extent.

Accuracy vs image noise. In this experiment, we evaluated the robustness of the four solutions against different noise levels. Thus, we fixed the camera with translational and rotational speed at 1 unit/frame and 5 deg/frame. Random noise with levels varying from 0 to 2 px were added to the 60 image points. The results in Fig. 6.13(c) show that both AnIRS and AnCRS are robust to the increasing image noise. In contrast, GS-PnP and RS-PnP are relatively sensitive to image noise.

Accuracy vs number of matches.

The number of 3D-2D matches has a great impact on the PnP problem. Therefore, we evaluated the performance of the proposed method with different numbers of 3D-2D matches. The camera was fixed with translational and rotational speed at 1 unit/frame and 5 deg/frame. The image noise level was set to 1 px. Then we increased the number of matches from 10 to 120. The results in Fig. 6.13(d) show that the estimation accuracy of all four methods increases with the number of matches. However AnIRS and AnCRS provide better results in both rotation and translation estimation in comparison to GS-PnP and RS-PnP.

Real Data

Augmented Reality with an RS Video

The four methods have been further evaluated by using real RS images. A planar marker providing 64 3D-2D matches was captured by a hand-held logitech webcam. Strong RS effects are present on the recorded video due to the quick arbitrary camera instantaneousmotion. This scenario can occur in many AR applications. After obtaining the camera pose and instantaneous-motion, the boundaries of the calibration board were reprojected into the RS image. As shown in Fig. 6.15, if the poses and instantaneous-motions are accurately recovered, the reprojected matrix boundaries can perfectly fit the planar marker.

In addition to visual checking, the mean value of reprojection errors of 3D marker points of each frame were used as a quantitative measurement.

Ground-truth 3D point and its projection with GS Virtual RS deformed shape and its projection with RS

Reconstruction with InfP-RSSfM

Reconstruction with Iso-RSSfM FIGURE 6.17: Deformed shapes reconstructed by InfP-RSSfM and Iso-RSSfM in comparison to ground truth under six types of camera instantaneous-motion.

instantaneous-motion types. Although Iso-RSSfM achieves slightly better reconstruction for d z , ω x and ω z than InfP-RSSfM, no significant visual differences can be observed.

(2) Varying instantaneous-motion speed. We evaluated the robustness of the four methods against increasing rotational and translational speed from 0 to 30 degs/frame and 1 units/frame gradually, but with random directions. We measure the reconstruction errors (mean difference between computed and ground truth 3D points in units) and pose errors (mean difference between the computed and ground truth rotation e rot = arccos((tr(RR GT ) -1)/2) and translation e trans = arccos(t t GT /( t t GT )) of each camera in deg). The results in Fig. 6.18 show that the estimated errors of SfM grow with speed. RSBA achieves better results with slow instantaneous-motion, while its errors grow dramatically beyond 15 degs/frame. In contrast, both InfP-RSSfM and Iso-RSSfM provide the best results under all configurations.

(3) Varying noise. In Fig. 6.19, we observe that the errors for all methods increase linearly when noise varies from 0 to 3 pixels. However, SfM shows a better tolerance to 'vertical+horizontal' experiment, while it suffers from the planar degeneracy and gives a strongly deformed shape in the 'vertical-only' experiment. In contrast, InfP-RSSfM and Iso-RSSfM provide a correct reconstruction in both experiments.

Cup and Box Datasets

A cylinder cup and a cubic box were captured by a hand-held Logitech webcam with strong RS effects. The videos were with close readout direction during the acquisition. Again, we randomly chose 6 frames from each video sequence. The ground-truth is now not available. Thus, we use two methods to evaluate the reconstruction results: 1) Visual checking. 2) For the cup dataset, we fitted the computed shapes with cylinders by using the 'pcfitcylinder' function in MATLAB and measured the fitting errors. For the box dataset, we segmented and fitted the computed scenes with three planes respectively in CloudCompare 7 . Thus, the mean value of fitting errors and angle between normal vector of the three planes (supposed to be 90 degs) are used as quantitative evaluation criteria. We can observe in Fig. 6.22 and Fig.

Discussion and Conclusion

In this chapter, we have proposed two novel methods which addresses the RS-PInP and RSSfM problems respectively from a new angle: using non-rigid vision.

RS-PInP

We propose a novel method for RS-PInP problem using SfT. By analyzing the link between the SfT and RS-PInP problems we have shown that RS effects can be explained by the GS projection of a virtually deformed shape. As a result the RS-PInP problem is transformed into a 3D-3D registration problem. Experimental results have shown that the proposed methods outperform existing RS-PInP techniques in terms of accuracy and stability. We interpret this improved accuracy as the result of transforming the problem from a 3D-2D registration into a 3D-3D registration problem. This has enabled us to use 3D point-distances instead of the re-projection errors, which carry more physical meaning and make the error terms homogeneous. A possible extension of our work is to derive the exact differential properties of virtual deformation.

RSSfM

We proposed a novel solution to RSSfM using NRSfM. By showing that the RS effects in multiple images can be explained by multiple one-to-one virtual deformations of a rigid 3D shape captured by GS cameras, we drew a link between RSSfM and NRSfM. As a result, RSSfM is transformed into a 3D-3D registration problem, which we show theoretically and experimentally can successfully avoid the risk of collapsing into a degenerate solution with the usual camera capture manner (parallel readout directions). We showed that the proposed methods outperform the existing RSSfM methods using 3D-2D registration in accuracy and stability.