Ryusuke Sagawa
email: sagawa@am.sanken.osaka-u.ac.jp

Takurou Sakai
email: t-sakai@am.sanken.osaka-u.ac.jp

Tomio Echigo
email: echigo@isc.osakac.ac.jp

Keiko Yagi
email: yagi@am.sanken.osaka-u.ac.jp

Masatsugu Shiba

Kazuhide Higuchi

Tetsuo Arakawa
email: arakawat@med.osaka-cu.ac.jp

Yasushi Yagi

Omnidirectional Vision Attachment for Medical Endoscopes

Medical endoscopes are equipped with wide-angle lenses to provide a wide field of view operating doctors. However, it has been pointed out that there is a backward looking blind area for endoscopes such that an affected area could be overlooked since the gastrointestinal system is intricate and the inside shaped by plicae. In this paper, we propose an omnidirectional vision attachment that has a convex mirror fitted at the tip of an endoscope. The attachment enables backward observations with the endoscope by providing a 360 degrees view. The issue related to developing this attachment is illumination of the field of view. Because the light source is usually only the light at the tip of the endoscope when it is inside the organ, we designed an attachment to illuminate the back-looking viewing field by reflecting light in a mirror. In the experiment, we measured the field of view and the illuminated field, and confirmed that the field behind an endoscope tip can be observed using the attachment.

Introduction

Examining digestive organs, such as the esophagus, stomach, duodenum, and large intestine using a medical endoscope is one of the most common methods for digestive disease investigations. The numbers of examinations are about 5, 6.2 and 3.2 million a year in Japan, US, and UK/Germany/France, respectively. In an examination, a doctor operates an endoscope by watching the video captured by a camera positioned at the tip of the probe. Especially, for examinations of the large intestine, it is necessary to sophisticatedly manipulate an endoscope according to the intestinal shape. Since the camera has only a forward looking view, much manipulation is required to view the complete intestine. Therefore, it is difficult to examine without missing something. For example, at the bending section between transverse and descending colon, the inner side of the place of flexion is usually blind and so could be overlooked. Furthermore, there are many plicae in an intestine;. the reverse side of a plica is occluded from the forward view and so the probe needs to be bent backward to observe the reverse side. This increased operational requirement is a burden for both doctors and patients. Although the frontal view of the camera is suitable for inserting the probe and operating forceps, it is not always optimal for finding affected areas. Instead, a 360-degree panoramic view of lateral and backward directions is more suitable since it can simultaneously observe all the intestinal wall.

To obtain a lateral or backward field of view, various endoscopes have been proposed. For an endoscope with a lateral field of view, lateral-or oblique-viewing endoscopes have been used [START_REF] Yamaguchi | Camera model and calibration procedure for oblique-viewing endoscope[END_REF][START_REF] Misra | Colonoscopy and colonoscopic polypectomy using sideviewing endoscope: a useful, effective and safe procedure[END_REF]. However, the field of view of these endoscopes is rather narrow to obtain the 360-degree panoramic view. For endoscopes with lateral and backward views, systems that use a secondary backward looking camera [START_REF] Triadafilopoulos | A novel retrogradeviewing auxiliary imaging device (third eye retroscope) improves the detection of simulated polyps in anatomic models of the colon[END_REF] and an endoscope with a conic mirror at the tip [START_REF] Arber | Proof-of-concept study of the Aer-O-Scope omnidirectional colonoscopic viewing system in ex vivo and in vivo porcine models[END_REF] have been proposed. However, these approaches have practical problems for examinations. Since [START_REF] Triadafilopoulos | A novel retrogradeviewing auxiliary imaging device (third eye retroscope) improves the detection of simulated polyps in anatomic models of the colon[END_REF] uses the forceps channel for the secondary camera, forceps cannot be used with this system. In [START_REF] Arber | Proof-of-concept study of the Aer-O-Scope omnidirectional colonoscopic viewing system in ex vivo and in vivo porcine models[END_REF], the tip of the endoscope is covered by a capsule and the conic mirror has a small hole for a 20-degree forward view. Thus, forceps cannot be used with the endoscope and the forward field of view is rather narrow for manipulation. Moreover, since it is not an attachment to an existing endoscope, a special endoscope is required.

In this paper, we propose an omnidirectional vision attachment for an endoscope to resolve the issue described above. This attachment has an annular convex mirror and is positioned at the tip of an endoscope. It enables a lateral and backward view in addition to the frontal one, thus providing a 360-degree view. Therefore, it is useful for examine bending sections and the reverse sides of plicae. Hence, a doctor can examine an intestine more efficiently with less manipulation. Since the oversight in an examination is expected to be reduce, the burden on a patient will also be reduced. Additionally, since the proposed attachment uses an annular mirror, a forceps can be used as with existing endoscopes.

In the following sections, we explain our omnidirectional vision attachment and detail its optical characteristics. We also give an experimental evaluation of the effectiveness and safety by using a model of the intestine and an animal experiment.

Omnidirectional Vision Attachment

The goal of the omnidirectional attachment proposed in this paper is to observe the lateral and backward directions of an endoscope. To achieve this, the attachment should enable not only a backward field of view but should also illuminate the field of view. In this section, we explain the requirements of the attachment based on a preliminary experiment described in Section 3.1. Finally, the prototype of the attachment is presented.

Practical Requirements for Designing an Attachment

For designing an attachment, the requirements from the point of operability and safety must be estimated, as well as the fields of view in lateral and backward directions. We describe the requirements for designing an attachment based on the results obtained from a preliminary experiment. First, the requirements from practical viewpoints are as follows.

Inserting a probe

When an endoscope is inserted into the large intestine, the end of the probe needs to bend flexibly according to the shape of the intestine. Several centimeters from the tip are usually inflexible because the camera and lens are housed there. The length of the inflexible part strongly affects the operability of inserting a probe. Therefore, doctors request that any proposed attachment is not larger than the existing endoscopic attachments. Additionally, since a doctor pushes the intestine with the tip of the probe while inserting it, the attachment needs to be robust to carry out the operation.

Operating a forceps

One of the advantages of digestive endoscopy is that a doctor can treat an affected area using a forceps as well as observing it. Thus, it is important that the proposed attachment can be simultaneously used with a forceps.

Washing optical components

Because the optical components become blurred by residue and mucus in the intestine, they are constantly washed by water injected from a water nozzle. It is desirable that the attachment can also be washed if it becomes similarly blurred.

Design of Proposed Attachment

The proposed approach provides lateral and backward fields of view utilizing a catadioptric imaging system in which a convex mirror is positioned at the tip of the endoscope. We designed an experimental attachment for an Olympus CF-240AI. The tip of the probe is shown in Fig. 1. It has a camera, two light sources, a forceps channel and air/water nozzle. The position of the camera is not the center of the probe. The positions of the light sources are different from the camera and not symmetrical with respect to the camera.

In an omnidirectional catadioptric imaging system, a convex mirror is usually placed on the axis of the camera lens. Similarly, it is desirable to place a convex mirror on the axis of a lens to omnidirectionally illuminate a scene. Therefore, two approaches were considered. The first approach was that three mirrors be used for the camera and the two light sources, separately. The second was that a single mirror be used for both observation and illumination.

An endoscopic camera usually has a wide field of view; for example, the CF-240AI has 140 degrees. Thus, the mirrors for the first approach must be small and be placed very close to the camera and light sources. Contrarily, the backward direction is occluded by the probe itself if the mirrors are close. Moreover, it is undesirable to place a mirror close to the lens from the point of focal depth. We created mirror samples of 5mm in diameter. After testing, doctors suggested that small mirrors may injure the intestine if a small prominence was to exist at the tip. Although one can use a hemispherical cover for a mirror, it is not practical from the point of washing. Therefore, we determined our first approach was not practical.

In this paper, we adopt the second approach. This uses a convex mirror for both observation and illumination. This approach can use a mirror with a diameter as large as that of the probe. It makes it easy to realize both lateral and backward fields of view. It is also desirable from the point of focal depth. An issue related to this approach is the illumination of the scene because the positions of the camera and light sources are different. The luminance may not be uniform because of the displacement of the field of view and illumination. However, by placing a mirror distant from the lens, we can reduce the effect of displacement. As well, the inter-reflection of the intestinal wall is expected to work for ambient illumination. Since it is impossible to place a single mirror on the axis of both camera and light sources, we decided to place the axis of the proposed mirror on the center of the probe because the gravity of the illuminating and imaging system is near the center of the probe.

Based on the requirements described in Section 2.1, we designed an attachment that consisted of a single convex mirror and a body to support the mirror. The external and cross-section view are shown in Fig. 2 and Fig. 3, respectively.

The shape of the experimental mirror is a body of revolution around z-axis given by

z = cr 2 1 + √ 1 -(1 + k)c 2 r 2 , ( 1
)
where r is the radial coordinate, c is the curvature (the reciprocal of the radius), and k is the conic constant. If k < -1, (1) represents a hyperboloid. By considering the size of mirror and the field of view of the endoscopic camera, we determined the distance between the mirror and the front of the probe is 5.62mm. To achieve the lateral and backward field of view, the parameters are determined as c = -0.219 and k = -1.19. The hole of the mirror is 8mm in diameter to enable operating a forceps. The annular hyperboloidal mirror has three supports making it easy to wash while keeping it stable. The width of the supports is 1.23mm, decided by considering the stress during an operation. One of the supports is placed at the near side of camera and others at the far side to minimize any occlusion. The attachment with the cylindrical body is positioned at the tip of an endoscope and fixed with tape. The difference in the diameters of the attachment and the endoscope is 2.5mm. The front field of view is about 70 degrees, as shown in the cross sectional figure. The attachment body and mirror are made from polycarbonate, a material that is often used for medical equipment, and formed by a molding process. Therefore, it is disposable and sanitary. Fig. 4 shows the omnidirectional vision attachment positioned on an endoscope. The size of the attachment is 16mm in width and 18mm in height. The length of the part that sticks out from the probe is 9mm, which is less than the existing attachment.

Evaluation of the Experimental Attachment

In this section, we first estimate the characteristics of the endoscopic camera and light sources in a preliminary experiment. Second, we measure the field of view by computing the viewing ray of the camera with the omnidirectional vision attachment. Third, we measure the field of illumination by examining the light reflected by the mirror. Fourth, we estimate the luminance of a scene illuminated by reflected light using the endoscopic camera. Finally, we explain the results of evaluations by doctors.

Preliminary Experiment

As shown in Fig. 1(a), the tip of the endoscope has a camera, two light sources, a forceps channel, and an air/water nozzle. Their configuration is shown in Fig. 1(b). The distance between the camera and light sources is 4.1-4.6mm. Therefore, the line of sight is different from the rays of the illumination. This is an issue to address in designing the attachment.

We investigated the field of view of the camera and the distribution of the illumination. First, the viewing angle of the endoscopic camera is 140 degrees diagonally. Since the diameter of the lens is 2.9mm, we assumed that the focal point of the camera was 0.53mm inside the lens front, as shown in Fig. 5. Next, we measured the distribution of the light power of the light sources. We placed a white diffusing plate in front of the endoscope and captured the image of the diffuser using another camera. The light power in each direction was measured by the brightness of the diffuser. Fig. 6 shows the results. The vertical axis indicates the relative power with respect to direction. In the figure, the front direction is 90 degrees. From this result, the power at an angle 30 degrees from the front direction was reduced by half.

Measuring the Field of View Method

We measured the field of view of the camera with the proposed omnidirectional attachment using structured light patterns. We placed a flat display by the side of the attachment, as shown in Fig. 7(1). The structured light patterns on the display were capture by the camera. The coordinate of the display was associated with that of the camera using the structured light patterns [START_REF] Sagawa | Calibration of lens distortion by structured-light scanning[END_REF]. If the structured light patterns were projected from the display at two positions, for which the relative distance d was known, as shown in Fig. 7(3), the direction of a viewing ray could be computed. If a pixel of the camera image corresponds to points A 1 and A 2 in the display, the direction of the ray is computed from A 1 , A 2 and d [START_REF] Grossberg | A general imaging model and a method for finding its parameters[END_REF]. We measured the field of view by computing the viewing rays for all pixels.

Result Fig. 8 shows the field of view of the endoscopic camera with the attachment. We measured the field of view in three directions, as shown in the top-left figure. The viewing rays are indicated by white lines in the cross-sectional views. The regions between the dashed lines are the backward fields of view obtained by mirror reflection. The forward and backward fields of view intersect each other. Because the camera is not at the center of the probe, the observed forward field of views are different: outside the mirror for Direction 1, inside for Direction 3, and both sides for Direction 2. The curved line indicates the position of the mirror. The backward viewing angle is a, the angle between the horizontal plane and the backward field of view is b, and the angle between the forward and backward fields of view is c. For Direction 2, the angle between the horizontal plane and the inner forward field of view is d.

The results for the viewing angles are summarized in Fig. 9. Cross-sections A and B are parallel to Directions 1 and 2 in Fig. 8, respectively. The backward field of view is maximized in Direction 1 and minimized in Direction 3 because of the relative positions of the camera and the mirror. The maximum and minimum backward viewing angles can be computed from the angles a and b in each direction. The minimum angle is between 12 and 24 degrees and the maximum angle between 24 and 43, as shown in Fig. 9A. The forward field of view has 50 degrees in Fig. 9B and more than 40 degrees in Fig. 9A. This difference is caused by the shift of the centers between the camera and the mirror.

Measuring the Field of Illumination Method

The field of illumination was measured by projecting the light of the endoscope onto screens. We projected the light onto two screens for which the relative distance d was known, as shown in Fig. 10(1). The distance between the horizontal line and the illuminated area was measured. The angle a was computed from L 1 , L 2 and d. The illuminated screen is shown in Fig. 10(2). The distances L 1 and L 2 are given by measuring the distance L between the horizon- tal line, which is indicated by the dashed line, and the edge of the illuminated area.

Result Fig. 11 shows the measured results of the field of illumination in three directions in Fig. 8. Since the endoscope has two light sources, the solid lines indicate the light by the near one and the dashed lines indicate the other. The thick curved lines indicate the position of the mirror. The field of illumination is regarded as the area illuminated by one of two light sources for Directions 1 and 3, and the area illuminated by the near one for Direction 2. We measured the angle a of the illuminated area and the angle b between the horizontal line and the illuminated area.

Next, we compared the field of view and the illumination. Fig. 12 shows the field of view overlapped with the field of illumination. For Directions 1 and 3, the field of view indicated by the gray area is covered by the field of illumination indicated by the solid lines. Thus, the field of view is successfully illuminated. For Direction 2, the area illuminated insufficiently is about 4 degrees. However, if an observed object is close to the endoscope, it can be illuminated.

Measuring the Distribution of Illumination

Method Next, we evaluated the distribution of illumination with the attachment. To simulate the situation that the endoscope is in an intestine, we fixed the Fig. 15. The distributions of illumination in the radial and circumferential directions: the intensity observed with the attachment is 70-80% of the result without the attachment. For the direction (c) that correspond to Direction 2, the scene was illuminated uniformly. Thus, a field of view within 25mm from the camera can be sufficiently illuminated. The large peaks indicate the mirror supports and the small peaks indicate dust and small blemishes in the mirror. The circles in (e) are caused by the irregular reflection at the edge of the mirror.

endoscope in a 50mm diameter acrylic pipe, a white diffusing object, as shown in Fig. 13. The distribution of illumination was measured by capturing an image with the endoscopic camera. If the intensity of the image is similar to the case without the attachment, the field of view had been sufficiently illuminated. We evaluated four radial directions (a), (b), (c) and (d) and a circumferential direction (e) shown in Fig. 14. Directions (a), (c) and (d) correspond to Directions 1, 2 and 3 in Fig. 8.

Result

The distributions of illumination in the radial and circumferential directions are shown in Fig. 15. For radial directions, the intensities of the area observed by mirror reflection and the outside area directly observed are nearly similar. The intensity observed with the attachment is 70-80% of the result without the attachment. The peak parts in the graphs indicate the edge of the mirror. For the circumferential direction, the large peaks indicate the mirror supports and the small peaks indicate dust and small blemishes in the mirror.

Since the image observed with the attachment was captured without saturation or black-out, it was shown to be successfully illuminated. For the direction (c) that correspond to Direction 2, the scene was illuminated uniformly. Thus, From these experiments, we showed that the proposed attachment simultaneously provided forward and backward fields of view. Therefore, it satisfied the requirements set for its design.

Evaluating the Field of View by using an Intestine Model

Method To evaluate the field of view with the attachment, we next tested the attachment by capturing images in an intestine model. We painted small black marks inside the model as reference points. If the attachment provided a desirable field of view, the marks would be observable even on the reverse side of a plica or the inner side in a bending section. Fig. 16 shows the marks on the reverse side of a plica. We painted some marks on the front and back side of a bending section as shown in Fig. 17. We captured an image sequence as shown in Fig. 18. Result In Fig. 16, the attachment was shown to enable the observation of a mark a on the reverse side of a plica b in the mirror part. The mark cannot be observed in the forward field of view. Meanwhile, Fig. 18 shows that the inner side of a bending section could be observed by using the attachment. Without the attachment, we can observe a mark a in the front, but cannot observe a mark b at the back. With the attachment, we can observe both a and b. As shown in Fig. 19, it is difficult to observe the mark b without the attachment because of the restriction that the maximum curvature of bending an endoscope is limited because of the intestine diameter. By contrast, the attachment enabled us to observe both a and b without complicated manipulations of the endoscope. These results showed that the attachment was useful to observe areas occluded from the forward field of view.

Evaluation by Doctors Based on an Animal Experiment

Finally, an evaluation of the attachment by three expert endoscopists based on an experiment with a model of intestine and an animal experiment are presented. First, the endoscopists tested the attachment using a model. They verified that the endoscopic video obtained images with the attachment and that the reverse side of a plica, a bending section, and the pylorus could be observed.

Next, an animal experiment using a dog was evaluated. Fig. 20 shows examples of the images of an intestine with the omnidirectional vision attachment. The lateral and backward directions can be observed in the mirror part. From this experiment, we verified that endoscopists can operate an endoscope without breaking the attachment or damaging the intestine. One issue found in the experiment was that the mirror became blurred by residue in the intestine and could not be washed clearly in some cases, as shown in Fig. 21. Based on this evaluation, we plan to improve the washing method.

Another issue was that the attachment narrows the forward field of view. The evaluation by the endoscopists showed that the endoscope with the attachment could be operated in similar manner to an endoscope without the attachment when inserted for an intestinal examination. However, the image in the mirror part is disturbing for beginner endoscopists to operate an endoscope with the attachment. This is because the motion in the mirror part is in the opposite direction to the forward field of view image; however, this problem was resolved by carrying out several training exercises to use the endoscope with the attachment. In this experiment, medical endoscopists determined that they could examine an intestine even if part of the forward field of view was occluded by the attachment. This was because the outer part of the forward field of view provides images in a fine resolution. We plan to continue our evaluations to determine all practical issues.

Conclusion

In this paper, we proposed an omnidirectional vision attachment that enabled observations of lateral and backward panoramic field of view around an endoscopic camera. These directions are usually blind when using existing endoscopes. Since the requirements for the attachment are to provide forward and backward directional views and to maintain operability of the endoscope and forceps, we determined that the attachment would consist of an annular hyperboloidal mirror with three supports. The experimental attachment was manufactured by a molding process. We experimented with various optical characteristics of the fields of view and illumination. It was verified that the attachment provided lateral and backward fields of view with sufficient illumination. Through experimental evaluations by medical endoscopists, we showed that the panoramic field of view obtained was useful and that operability was maintained. However, since the input video is not intuitive for beginners, we plan to improve the video representation when using the attachment.

Fig. 1 .

 1 The tip of an endoscope has a camera, two light sources, a forceps channel, and air/water nozzle.

Fig. 2 .

 2 Fig. 2. External view of the experimental attachment.

Fig. 3 .

 3 Fig. 3.Cross-sectional view of the experimental attachment.

Fig. 4 .

 4 Fig. 4. Omnidirectional vision attachment positioned at the tip of an endoscope.

Fig. 5 .

 5 Fig. 5. The viewing angle of the endoscopic camera is 140 degrees diagonally. Since the diameter of the lens is 2.9mm, we assumed that the focal point of the camera was 0.53mm inside the lens front.

Fig. 6 .

 6 Fig. 6. The distribution of light power is measured. The vertical axis indicates the relative power with respect to direction. The front direction is 90 degrees.

Fig. 7 .

 7 Fig. 7. (1) The field of view is measured by using structured light on a flat display. (2) An example of the camera image of the structured light. (3) the direction of a viewing ray is computed by projective structured light patterns from the display at two positions, for which the relative distance d was known.

Fig. 9 .

 9 Fig. 8. Top-left: the field of view is measured in three directions. Top-right, Bottom-left, and Bottom-right: the viewing rays are indicated by white lines in the cross-sectional views for Direction 1, 2, and 3, respectively. The backward viewing angle is a, the angle between the horizontal plane and the backward field of view is b, and the angle between the forward and backward fields of view is c. For Direction 2, the angle between the horizontal plane and the inner forward field of view is d.

Fig. 10 .

 10 Fig.10. The field of illumination was measured by projecting the light of the endoscope onto screens. We projected the light onto two screens for which the relative distance d was known, as shown in[START_REF] Yamaguchi | Camera model and calibration procedure for oblique-viewing endoscope[END_REF]. The distance between the horizontal line and the illuminated area was measured. The angle a was computed from L1, L2 and d. The distances L1 and L2 are given by measuring the distance L between the horizontal line, which is indicated by the dashed line, and the edge of the illuminated area as shown in[START_REF] Misra | Colonoscopy and colonoscopic polypectomy using sideviewing endoscope: a useful, effective and safe procedure[END_REF].

Fig. 11 .

 11 Fig. 11. The measured results of the backward field of illumination in three directions in Fig. 8: the solid lines indicate the light by the near one and the dashed lines indicate the other of two light sources. The thick curved lines indicate the position of the mirror. The angle a of the illuminated area and the angle b between the horizontal line and the illuminated area were measured.

Fig. 12 .

 12 Fig. 12. The gray areas indicate the fields of view and the areas closed with solid lines indicate the fields of illumination. For Directions 1 and 3, the field of view indicated by the gray area is covered by the field of illumination indicated by the solid lines. For Direction 2, the area illuminated insufficiently is about 4 degrees. However, if an observed object is close to the endoscope, it can be illuminated.

Fig. 13 .

 13 Fig. 13. The distribution of illumination is measured by capturing an image in an acrylic pipe.

Fig. 14 .

 14 Fig. 14. The distribution of illumination is measured in the five directions, four radial directions (a), (b), (c) and (d) and a circumferential direction (e).

Fig. 16 .

 16 Fig. 16. Marks on both sides of a plica in an intestine model: a. reverse side b. front side. The attachment enables to observe both marks.

Fig. 17 .Fig. 18 .

 1718 Fig. 17. Marks on a bending section: a. front side b. back side.

Fig. 19 .

 19 Fig. 19. The attachment enables the observation of the inner side of a bending section without complicated manipulations of the endoscope.

Fig. 20 .

 20 Fig. 20. Example of images of an intestine with the omnidirectional vision attachment: the lateral and backward directions can be observed in the mirror part.

Fig. 21 .

 21 Fig. 21.Washing the attachment: one issue found in the experiment was that the mirror became blurred by residue in the intestine and could not be washed clearly in some cases.


Kazuaki Kondo
email: kondo@am.sanken.osaka-u.ac.jp

Yasuhiro Mukaigawa
email: mukaigaw@am.sanken.osaka-u.ac.jp

Yasushi Yagi
email: yagi@am.sanken.osaka-u.ac.jp

Free-Form Mirror Design Inspired by Photometric Stereo

A significant issue in the design of catadioptric imaging systems is what shape the component mirrors should take. In this paper, we propose a novel algorithm for designing a free-form mirror. A free-form mirror expressed as the assembly of its gradients, is the most flexible surface representation that can form various shapes. We improve the shape reconstruction framework used in a photometric stereo scheme for use in the design of free-form mirrors for catadioptric imaging systems. An optimal mirror shape is created to produce the best possible desired projection, under integrability conditions in order to be a consistent surface. Curved mirrors are designed for various catadioptric configurations and these design experiments confirm that the resulting free-form mirrors can approximate the desired projections.

Introduction

Catadioptric imaging systems combine cameras with mirrors to change camera projections. These systems are used in numerous applications, including robot navigation and wide view surveillance. Conventional catadioptric imaging systems use mirrors with basic shapes [START_REF] Yamazawa | HyperOmni Vision: Visual Navigation with an Omnidirectional Image Sensor[END_REF][START_REF] Nayar | Catadioptric Omnidirectional Camera[END_REF], or with special rotationally symmetric shapes to obtain the desired resolution in a vertical direction [START_REF] Nakamura | Automatic 2D map construction using a special catadioptric sensor[END_REF][START_REF] Gasper | Constant Resolution Omnidirectional Cameras[END_REF][START_REF] Conroy | Resolution Invariant Surfaces for Panoramic Vision Systems[END_REF][START_REF] Hicks | Equi-areal Catadioptric sensors[END_REF]. Gaechter et al. used not only a such mirror also a space variant imager to control image resolution [START_REF] Gaechter | Mirror Design for an Omnidirectional camera with a space variant imager[END_REF]. Kondo et al. designed an asymmetric convex mirror to obtain an isotropic projection property [7]. Hicks et al. assumed a mirror formed by a polynomial function, and solved it using a non-linear optimization [START_REF] Hicks | Designing a mirror to realize a given projection[END_REF]. The shapes of all the mirrors used in these proposals were defined by a parameterized function, resulting in limited shape representation and projection forming capabilities. A generalized representation of a mirror surface with a high DOF, together with the knowledge of the design thereof, are necessary to produce arbitrary projections.

A free-form mirror determined from multiple control points is one of the most generalized representations. It can be used to realize, without distortion, various projections given by practical configurations, such as a wide panoramic view. In this case, the desired projection is a uniform projection onto a cylindrical scene around the camera. Another example of the use thereof is to correct the image distortion in a projector system. A free-form mirror can produce counterwarping against the distortion. An algorithm for designing free-form mirrors was proposed by Swaminathan et al. [START_REF] Swaminathan | Designing of Mirrors for catadioptric systems that minimize image error[END_REF]. They modeled the shape of the mirror using the cross products of splines to formulate the design problem as a linear equation. A limited number of control points on the splines that decide the design DOF, however, still remain. In addition, this design cannot represent non-smooth surfaces.

In this paper, we propose a new design method for a free-form mirror constructed as the assembly of its gradients. This type of free-form definition can represent mirror shapes, including non-smooth surfaces, more generally than the conventional algorithms, thus allowing a variety of projections to be produced. An example of this is a compound mirror constructed from multiple flat planes such as a polygon mirror. Of course compound mirrors constructed from curved surfaces can be defined as a result of the free-form definition. Our method can design such a compound mirror directly as it is a single mirror surface.

However, there is a problem in using a free-form mirror surface. The gradients of the points are determined so as to satisfy a given desired projection, but their movement is actually not perfectly independent as they must form a consistent surface. In this case, the gradients need to move under the constraint known as integrability. This problem also occurs in photometric stereo schemes for shape reconstruction, where the optimal shape of a target object forming shadings in an input image is estimated. The free-form mirror design algorithm estimates the optimal shape of a mirror that produces a given projection. These two problem specifications are therefore very similar. However, using the methods deployed in photometric stereo schemes directly is not feasible in that the meaning of the residuals is different in each case. The assumption of an orthographic camera is also a problem in catadioptric imaging systems. To this end, the algorithms used in photometric stereo schemes are extended for application to the mirror design problem. The results are tested experimentally.

Problem settings

Problem specification for mirror design

Mirror design for catadioptric imaging systems begins with defining the desired projection. Assume that each incoming ray from a scene is reflected at some point on the free-form surface, and its captured position on the image plane is (u, v). Then the desired projection can be expressed by rays in the scene P s (u, v) defined on the image plane, and can be freely manipulated by a designer. Similarly, projections of the primary camera are expressed as P c (u, v). Figure 1(a) and Fig. 2 illustrate this configuration. P s (u, v)andP c (u, v) are defined on the image plane where all lengths are equal to 1. These two vector fields are related by reflection on a curved mirror placed in front of the camera:

N(u, v) = - P s (u, v) + P c (u, v) P s (u, v) + P c (u, v) (1)
where N(u, v) is a normal vector field. The aim in mirror design is to determine the surface that produces N(u, v). This is achieved by integrating gradient vectors from the normal vector field N(u, v). Generally, gradients of a smooth surface can be determined by differentiation. However, the inverse, integrating the given gradients to reconstruct an original surface, is not always possible. Since an integration result depends on its path, integrations along different paths may (and in most cases do) produce divergent results when freely distributed gradients are given. To form a consistent surface, one needs to consider this problem.

Problem specification for formulation of photometric stereo schemes

The creation of photometric stereo schemes can be seen as a similar problem to mirror design. Photometric stereo schemes reconstruct a surface in two steps. First, a normal vector field of the target object is estimated from images under different illuminations. The formulation of the general image irradiance equation for classical photometric stereo schemes given below assumes that (x(u, v), y(u, v), z(u, v)) is the form of the object surface defined on the image plane of a camera (u, v).

I(u, v) = ρ(u, v) L • N(u, v) L N(u, v) (2)
where I(u, v) is the intensity at (u, v), ρ(u, v) is the albedo, L is the direction of the parallel light source, and N(u, v) is the normal vector of the object surface (Fig. 1(b)). Parallel light sources illuminating from three or more different points allow us to solve Eq. ( 2) about one normal vector and obtain a normal vector field.

The gradients produced by the normal vector field are then integrated to reconstruct the shape of the original object. Various methods have been proposed to assist in this process. These include solving a two-dimensional Poisson equation (this is the easiest and the most popular), an iterative approach with the Gauss-Seidel method as per Horovitz et al. [START_REF] Horovitz | Depth from gradient fields and control points: Bias correction in photometric stereo[END_REF], and a linear method from Agrawal [START_REF] Agrawal | An Algebraic Approach to Surface Reconstruction from Gradient Fields[END_REF].

Similarities and differences in problem specification

As described in Sections 2.1 and 2.2, despite mirror design and photometric stereo scheme creation being very different projects, interestingly, they result in very similar problems. We make use of this similarity in this paper. However, using the same approach as in photometric stereo scheme creation has disadvantages for mirror design.

Normal vector fields estimated from input images in the photometric stereo schemes are generated from a real object. So, in principle, the shape of the object surface can be perfectly reconstructed if the images do not include any errors. Thus, if the integration cannot be performed consistently, it is as a result of image errors caused by, for instance, specular reflections, shadows, miscalibration, bad approximations, and so on. Decreasing the influence of image errors is, therefore, important in this type of shape reconstruction problem.

For mirror design, whether or not the normal vector field produced from the desired projection P s (u, v) can form a continuous consistent surface is a problem. Generally the desired projection P s (u, v) is given without considering the possibility of forming a consistent surface. Therefore, in most cases a solution that perfectly satisfies a given desired projection P s (u, v) does not exist, which is very different from the shape reconstruction problem in photometric stereo schemes. The reason why integration of the gradients does not form a consistent surface is the given projection itself. In this case an approach that minimizes the overall projection residual is recommended.

Furthermore some photometric stereo schemes assume a known boundary condition and an orthographic projection camera. In free-form mirror design, the shape of the mirror is completely unknown. Furthermore, since the mirror is placed close to the camera in catadioptric imaging systems, orthographic projection cannot be assumed. The mirror design problem for catadioptric imaging systems requires a method without boundary conditions for conventional perspective projection cameras. Thus, the approach in photometric stereo schemes needs to be extended for use in mirror design. 3 Design of a free-form mirror

Representation of the free-form mirror

In this paper we assume that a target catadioptric imaging system is constructed with a conventional perspective camera C and a single reflective mirror M placed in front of the camera (Fig. 2). The camera C has a W × H size image plane (u, v) that corresponds to a pixel on the image plane. The camera projection vector field P c (u, v) is given by:

P c (u, v) =   -K u u -K v v f   (3)
where the camera has a focal length f and the size of the pixels K u , K v . We assume a depth of field z(u, v) defined on the image plane to form the shape of the mirror surface S(u, v):

S(u, v) = 1 f P c (u, v)z(u, v). ( 4
)
We represent the free-form mirror shape with gradients p = ∂z ∂u , q = ∂z ∂v . The objective of mirror design is to optimize S(u, v) by moving p, q so as to produce N(u, v) with a minimum residual.

Integrability of a free-form surface

The reconstruction or design of a 3D surface must be done in such a way as to form a consistent surface. This is an implicit constraint that is referred to as the integrability of the surface [START_REF] Horn | Robot Vision(Mit Electrical Engineering and Computer Scenece Series)[END_REF]. On a consistent surface, integration of surface gradient vectors from a point A to a point B must be constant along any path as shown in Fig. 3. This is known as the integrability of a potential field [START_REF] Horn | Robot Vision(Mit Electrical Engineering and Computer Scenece Series)[END_REF]. When an integration result along a path differs from that along any other path, the surface is discontinuous at that point.

Let p(u, v) and q(u, v) be gradients of S(u, v) in the u and v directions ∂S ∂u and ∂S ∂v , respectively. Integrability of the surface is generally formulated with a curl operator of S as:

curl(p, q) = ∂p ∂v - ∂q ∂u = 0 (5)
at any point on (u, v), thus representing the constraint of forming a consistent surface. Note that the shape of the mirror surface is as per Eq. ( 4). Since camera projection P c is determined by the camera parameters, and the only freedom in the shape S(u, v) is in the scalar field z(u, v), an integrability constraint can be written in a scalar domain about z instead of a vector domain S:

curl(p, q) = ∂p ∂v - ∂q ∂u = 0. ( 6
)
The mirror design must be performed with Eq. ( 6) to form a consistent surface. The integrability constraint is enforced over a discrete domain based on [START_REF] Agrawal | An Algebraic Approach to Surface Reconstruction from Gradient Fields[END_REF] to formulate the design problem as linear equations. The mirror surface can then be described more generally in a discrete domain than in a spline defined surface as proposed in [START_REF] Swaminathan | Designing of Mirrors for catadioptric systems that minimize image error[END_REF] or a polynomial function as proposed in [START_REF] Hicks | Designing a mirror to realize a given projection[END_REF]. In a discrete domain, the derivatives of the gradients are given by:

∂p ∂v = p(u, v + 1) -p(u, v) ∂q ∂u = q(u + 1, v) -q(u, v). ( 7
)
The equation for curl can be written in the discrete domain using Eq. ( 7):

curl = p(u, v + 1) -p(u, v) -q(u + 1, v) + q(u, v). ( 8
)
One can write Eq. ( 8) in linear form as:

curl = [1... -1...1... -1]g ( 9
)
where g is a W H × 1 vector constructed from the series of gradients p, q. Eq. ( 8) corresponds to a particular loop integral around a box of four pixels. Note that the loop integral around any other bigger loop can be expressed as linear combinations of the elementary loop integrals and thus does not provide any additional information. Thus stacking Eq. ( 9)=0 on the entire (u, v) field, one obtains a linear equation for the integrability constraint.

Cg = 0 (10)
C is a sparse matrix of size (W -1)(H -1) × 2W H. Each row in C is in accordance with Eq. ( 9) and has four non-zero values; two +1's corresponding to p(u, v + 1) and q(u, v), respectively, and two -1's corresponding to p(u, v) and q(u + 1, v), respectively.

Integrability on a perspective projection

The majority of research into photometric stereo schemes has assumed an orthographic projection camera because a camera can be placed sufficiently far inria-00325319, version 1 -28 Sep 2008 from the target object to approximate the perspective projection into an orthographic one. If an orthographic projection is assumed, we can easily calculate the gradients p, q from the normal vector field N because x = K u u, y = K v v (Fig. 4(a)). However, in catadioptric imaging systems, curved mirrors are placed relatively close to the camera for compactness. Thus, the perspective projection cannot be approximated to an orthographic one. This means a method is needed to calculate the gradients. Generally a normal vector N can be decomposed into two perpendicular gradient vectors whose outer product becomes N itself. For a perspective projection, we can obtain the directions of the gradient vectors, but their lengths are not uniquely determined because they depend on their depth as shown in Fig. 4(b). Tankus' proposal [START_REF] Tankus | A New Perspective [on] Shape-from-Shading[END_REF][START_REF] Tankus | Photometric Stereo under Perspective Projection[END_REF] provides a hint to solve this problem. Fortunately, the relationship between the length of the gradient vector and its depth under perspective projection is linear, resulting in [START_REF] Horovitz | Depth from gradient fields and control points: Bias correction in photometric stereo[END_REF] rather than p = ∂z ∂u and q = ∂z ∂v . Having obtained the above, consideration should be given to how the integrability constraint with p , q is formulated. Consider that curl(p , q ) can be expressed with curl(p, q) as:

p = 1 z ∂z ∂u q = 1 z ∂z ∂v
curl(p , q ) = ∂p ∂v -∂q ∂u = ∂ ∂v ( 1 z ∂z ∂u ) -∂ ∂u ( 1 z ∂z ∂v ) = -1 z 2 ( ∂z ∂v ∂z ∂u -∂z ∂v ∂z ∂u ) + 1 z ( ∂ 2 z ∂v∂u -∂ 2 z ∂u∂v ) = 1 z curl(p, q) ( 12
)
Since z > 0, curl(p, q) = 0 is equivalent to curl(p , q ) = 0. We can now say that curls in the discrete domain have the same characteristics as curls in the inria-00325319, version 1 -28 Sep 2008 continuous domain. Thus a line of p , q can be used as g instead of p, q for the integrability constraint. Note that this usage of p , q requires an additional step: forming the shape. The shape of the surface can easily be produced by integrating p, q. Integration of p , q provides a log scaled shape for the radical shape because

p = 1 z ∂z ∂u = ∂ ln z ∂u q = 1 z ∂z ∂v = ∂ ln z ∂v . ( 13
)
The exponents of the integration results must be obtained to convert a log scaled shape into a radical.

Gradient optimization under the integrability constraint

An optimal shape for the mirror surface should minimize residuals from the desired gradients under the integrability constraint from the previous section. The approach proposed by Agrawal [START_REF] Agrawal | An Algebraic Approach to Surface Reconstruction from Gradient Fields[END_REF] for the photometric stereo method uses a graph that describes the reliability of the gradients. Gradients with high reliability are retained and the others are ignored to satisfy the integrability constraint, much like an elimination of outliers. This proposal works well for the photometric stereo problem because the gradients obtained from the images can have unexpected errors. Conversely, residuals in the mirror design problem are not caused by unexpected errors but by non-integrability of the given desired gradients. Thus, minimization of residuals all over is superior to the elimination of outliers. We use a simple Least Mean Square(LMS) algorithm to obtain the optimal gradients. Let g be a line of gradients p , q that form a surface, and g d be a line of desired gradients obtained from the desired projection. The ideal solution about g is:

g = g d . ( 14
)
If this equation is solved under integrability constraint Eq. ( 10), that contracts the solution space for Eq. ( 14), the solution space h is given by:

g = Th. ( 15
)
where T is a 2W H × (W -1)(H -1) matrix whose rows are linear independent solutions of Cg = 0. Since the matrix C is very sparse, one can easily produce the T matrix. Substituting Eq. ( 15) into Eq. ( 14) and solving it with the LMS algorithm, we obtain optimal solutions about gradients p , q .

Th = g d (16
)

h = T + g d → g = TT + g d ( 17
)
where T + is a pseudo inverse matrix of T. This procedure does not require any additional conditions despite the fact that the photometric stereo scheme needs boundary conditions.

Designing experiments

We performed design experiments to validate the effectiveness of our algorithm with different configurations. How much a desired projection is realized depends on the integrability of the desired projection. In the following three configurations, the former two require producing non-integrable projections. Since there is no form that perfectly satisfies the projection, there is no ground truth. The last configuration requires producing integrable one, we can evaluate and compare degree of approximations given by our algorithm and the conventional one.

Wide panoramic imaging system

The free-form mirrors designed with our algorithm satisfy both the expanding FOV and reduced distortion on captured images. We assumed a configuration for a wide panoramic imaging system as shown in Fig. 5(a). In this setup, distortionfree means that cylindrical scenes around the camera appear directly on the images. A desired projection is given by dividing an objective panoramic FOV into the same size grids. The FOV of the camera and the objective panoramic FOV are respectively, ±20.0×±15.3degrees produced with a 6.0mm focal length and ±50.0×±20.0degrees. The shape of the designed mirror, a target panoramic scene, and a captured image are shown in Fig. 5. Checkers on the cylindrical scene appear approximately as squares on the image. The center region has almost no distortion, whereas a little distortion appears at the image edges. The distortion is, however, much smaller than that in the conventional parametric approaches such as with rotationally symmetric mirrors.

Catadioptric projector system

Free-form mirrors can also correct image distortions in projector systems. Generally direct projection by an upward facing projector has trapezoidal distortion. Using a combination of a projector and a free-form mirror, rectangular images appear on a screen without image deformation, and these cancel the trapezoidal distortion. Since the projection of a projector is the same as that of a camera apart from the direction of the light, our algorithm can be applied directly. Assume a catadioptric projector system as shown in Fig. 6(a). We configured a rectangular projection as the desired one, and designed the catadioptric projector system using our algorithm. The focal length and FOV of the projector are the same as those of the camera in the previous experiment.

Compound Mirror

Direct definition of the mirror surface with its gradients as control variables can represent a non-smooth surface. So our method covers not only a single curved mirror addressed in conventional methods such as [START_REF] Hicks | Designing a mirror to realize a given projection[END_REF][START_REF] Swaminathan | Designing of Mirrors for catadioptric systems that minimize image error[END_REF] but also a compound mirror constructed by multiple component mirrors. In this section, we evaluate the design ability for a compound mirror by designing a pyramid mirror. The pyramid mirror is constructed from four flat mirrors, which have four non-smooth borders at their joints. Thus many residuals remain when redesigning the pyramid mirror shape from its own projection using the conventional method [START_REF] Swaminathan | Designing of Mirrors for catadioptric systems that minimize image error[END_REF] that assumes a single curved mirror (Fig. 7 right). In order to avoid these residuals, each component mirror needs to be designed individually in the conventional methods. But this causes problems in the construction step as continuity at the joints is not considered. On the other hand, our method suppresses residuals at the joints and allows them to expand to neighborhoods (Fig. 7 left) in spite of the single mirror design. The pyramid mirror, which is one of the simplest examples of compound mirrors, is used to evaluate residuals easily. Our method also works well for other compound mirrors, such as the construction of curved mirrors.

Conclusion

In this paper, we proposed a novel design method for a free-form mirror surface for a catadioptric imaging system using the assembly of its gradients. We for- mulated an integrability constraint of the gradients to form a consistent surface in the mirror design, using a method similar to that used in creating photometric stereo schemes. Our approach produces mirror surfaces with minimal overall projection residuals, and it also works well for compound mirrors. This work is supported by the Special Coordination Funds for Promoting Science and Technology of Ministry of Education, Culture, Sports, Science and Technology.

Fig. 1 .

 1 Fig. 1. Configuration of two problems. (a) Design of a single free-form mirror for a catadioptric imaging system. (b) Formation of photometric stereo schemes.

Fig. 2 .

 2 Fig. 2. Camera-Mirror configuration.

Fig. 3 .

 3 Fig. 3. A model of integrability on a surface. Integration results from A to B along any path Pi are constant for a consistent surface.

Fig. 4 .

 4 Fig.4. Relationship between a normal vector and a gradient vector. (a) and (b) show models of orthographic projection and perspective projection cameras. The gradient vector in (a) is constant, independent of its depth. In (b) depth is ambiguous.

Fig. 5 .

 5 Fig. 5. Wide panoramic imaging system. X, Y , and Z axes in figure (b) correspond to the camera coordinate system.

Fig. 6 .

 6 Fig. 6. Catadioptric projector system.


Jean-Charles Bazin
email: jcbazin@rcv.kaist.ac.kr

Inso Kweon
email: iskweon@ee.kaist.ac.kr

Cedric Demonceaux
email: cedric.demonceaux@u-picardie.fr

Pascal Vasseur
email: pascal.vasseur@u-picardie.fr

Spherical Region-Based Matching of Vanishing Points in Catadioptric Images

A large literature exists for rotation estimation using vanishing points (VP). All these VP-based methods require to match the vanishing points in consecutive frames. It is usually considered that this matching step is trivial. However whereas some techniques exist, they suffer from some important limitations and might not work correctly in real robotic applications. For example, the continuity constraint (which aims to match the pair of VPs having the lowest angular distance) cannot handle large rotations and the line matching technique is very slow to execute and assumes accurate/stable line detection. In this paper, we present a fast and robust method to build the correspondences of VPs in catadioptric images. This work is strongly motivated by our research on real-time rotation estimation for dynamic vehicles using catadioptric vision. The underlying idea of the proposed method consists in matching, by histogram comparison, the spherical regions defined by the VPs in the equivalent sphere. Experiments have demonstrated the efficiency of this approach in terms of speed and robustness to translation, rotation, dynamic environment and image blurring.

Introduction

Vanishing Points (VP) are invariant to translation and thus provide key information to estimate the rotation of a camera. That is why there exists a large literature for rotation estimation using vanishing points. This paper particularly focuses on catadioptric images. These images are obtained from a vision system composed of a mirror with a specific shape and a conventional camera. Independently of the vision system that is used (e.g. traditional or catadioptric camera), most of the existing methods for rotation estimation proceeds in two steps: first, VP extraction and second, VP matching. The VPs are usually extracted by detecting lines and their intersections [START_REF] Antone | Automatic recovery of relative camera rotations for urban scenes[END_REF][2][3] [START_REF] Quan | Determining perspective structures using hierarchical hough transform[END_REF]. To match the VPs, two methods are widely used. The first one refers to the continuity constraint which matches the pairs of VPs having the lowest angular distance [START_REF] Bazin | UAV attitude estimation by vanishing points in catadioptric image[END_REF]. This approach is extremely fast but assumes that each rotation angle is less than 45 • . This assumption might not be verified for highly dynamic robotic systems or low frame-rate videos for example. The second method consists in matching the lines associated to the VPs. Several types of constraints have been used to match the lines like neighborhood correlation, epipolar geometry, orientation, length, overlapping, average contrast or mid-point (due to space limitation, cf [START_REF] Schmid | Automatic line matching across views[END_REF] and [START_REF] Karimian | A new efficient stereo line segment matching algorithm based on more effective usage of the photometric, geometric and structural information[END_REF] for a review). Whereas these constraints may provide interesting results, they suffer from at least one of the following limitations. First, many of them assume the camera geometry is known to impose epipolar constraint. Second, it is hard to extend some of these methods to catadioptric images for taking distortions into account. Third, they assume a reliable line detection but due to camera calibration error, a line might be split into two parts during the line extraction [START_REF] Bazin | Rectangle extraction in catadioptric images[END_REF][8] [START_REF] Vasseur | Central catadioptric line detection[END_REF]. Fourth, after matching the lines, these methods usually assume a rotation lower than 90 • to match the VPs. Finally, they are computationally expensive, especially when many lines are extracted, and thus cannot be used for real-time applications.

Regarding the existing works for VP matching, we aim to develop a new method that can overcome the listed limitations. After recalling the sphere equivalence, we will introduce our proposed method for VP matching. Finally, we will test its performance on several catadioptric videos.

Proposed Method

The problem of VP matching is motivated by our application of real-time rotation estimation for dynamic vehicles using catadioptric vision. Due to the specificities of this application, our goal is to develop a method for VP matching that must verify the following constraints:

-automatic: no manual interaction during the execution -robust to motion -fixed complexity: to guarantee execution time -fast: for real-time application Our solution is based on the fact that VPs provide strong photometric information. More precisely, our proposed method consists in matching, by histogram comparison, the spherical regions defined by the VPs in the equivalent sphere. In the following, we recall the sphere equivalence and present the details of our proposed algorithm.

Sphere equivalence

Geyer and Daniilidis have demonstrated the equivalence for the central catadioptric sensors (single viewpoint constraint) with a two-step projection via a unitary sphere centered on the focus of the mirror [START_REF] Geyer | Catadioptric projective geometry[END_REF]. A key advantage of the sphere equivalence is that it allows working in a general framework, i.e. the sphere, independently on the fact that a hyperbolic or a parabolic mirror is used. A second important advantage is that the sphere space provides some very interesting projection properties for lines. It has been proven that a line is projected as a great circle in the sphere and the great circles associated to a pencil of 3D parallel lines intersect in two antipodal points in the sphere [START_REF] Geyer | Catadioptric projective geometry[END_REF]. These two important properties are depicted on Figure 1 and will be used for our proposed method of VP matching. Fig. 1. A line in the world is projected as a great circle in the sphere and the projections of parallel lines intersect in two antipodal points in the sphere. These two antipodal points correspond to the vanishing points of the parallel lines.

Region definition

In this section, we investigate some region definitions for efficient VP matching. Our initial proposition was based on the remark that the neighborhoods (in sphere or image space) of the VPs are different enough to distinguish, match and track the VPs. However early experiments have shown an important difficulty of this approach: the VPs might appear/disappear in the image so that it is not possible to build and/or match their neighborhoods. That is why we preferred developing another region definition. An important comment is that, even if the VPs do not lie in the image, they lie in the sphere space and can provide strong photometric information. An intuitive region definition for VP matching consists in clustering each pixel with respect to its nearest VP. Mathematically, each i th vanishing point V i defines a region R i and a pixel projected on the sphere at P s belongs to the region R k where k is the solution of arg i max V i • P s. Since the vanishing points of parallel lines correspond to 2 antipodal points in the sphere, we also take into account the list of opposite VPs -V i . Therefore, given N VPs, the sphere is split into 2N regions. An example of regions obtained by this definition (referred as definition1 in the following) is shown in Fig 2 . One may notice that, in Fig 2(b), whereas the sphere is split into 2 × 3 = 6 regions, only 5 regions are contained in the image. This issue will be analyzed in section 2.4.

We also investigate a second region definition. Based on the properties of parallel lines projection in the sphere, each VP associated to a group of parallel lines can be represented by a unit vector in sphere space or a plane normal to this vector. Therefore, given N vanishing points, the sphere is split by N planes. The spherical points are clustered into regions depending on their position with respect to the planes defined by each VP. The algorithm for N = 2 is given in Algorithm1. The splitting of the sphere depends on the order of the vanishing points, i.e. switching V P 1 and V P 2 in Algorithm1 leads to a different splitting. This region definition is referred as definition2 in the following and some examples of split images are shown in Figure 3. In these examples, the projections of all the spherical regions lie in the image and experiments have shown that it is generally the case. Exemptions will be analyzed in section 2.4. Both region definitions provide some important photometric cues and can lead to interesting results. One may notice that definition1 and 2 are equivalent for N = 1. They will be experimentally studied in section 3.2. It is worthwhile to note that the sphere provides a simplified framework for splitting the image into regions. First, the VPs are usually obtained in the sphere since the algorithms of line detection for general catadioptric images [START_REF] Bazin | Rectangle extraction in catadioptric images[END_REF][8] [START_REF] Vasseur | Central catadioptric line detection[END_REF] perform in this space.

And second, it is needed to compute only N dot products to classify a pixel in its corresponding region, where N is the number of vanishing points (N usually equals to 2 or 3).

Algorithm 1 FnSphereSplitting (V P 1 ,V P 2 )
// (V P 1 ,V P 2 ) : the 1 st and 2 nd vanishing points // FnProjectionSphere(i,j) : projects the point (i,j) on the sphere // FnAddInRegion(i,j,k) : add the point (i,j) to the region k // s : sampling step for speed purpose for i = 1 : s + 1 : height do for j = 1 : s + 1 : width do P s = F nP rojectionSphere(i, j)

pos 1 = V P 1 • P s pos2 = V P2 • P s if pos 1 > 0 and pos 2 > 0 then F nAddInRegion(i, j, 1)
if pos 1 > 0 and pos 2 <= 0 then F nAddInRegion(i, j, 2) if pos1 <= 0 and pos2 > 0 then F nAddInRegion(i, j, 3) if pos 1 <= 0 and pos 2 <= 0 then F nAddInRegion(i, j, 4) end for end for

Region Comparison

In order to match the regions of 2 split spheres, we need a representation of the regions and a method to compare them. We assume that the number of spherical regions is the same in the 2 images, i.e. same number of VPs. One approach would be to extract feature points (e.g. Harris corners [START_REF] Harris | A combined corner and edge detection[END_REF] or SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]) in each region and match them. However it is computationally expensive and thus cannot verify our real-time constraint. Our approach is to represent each region by a histogram using the intensity of every pixel inside this region and then match the histograms. This technique of region-based matching has been previously used for stereo vision [START_REF] Marapane | Region-based stereo analysis for robotic applications[END_REF], optical flow [START_REF] Fuh | Region-based optical flow estimation[END_REF] or egomotion estimation [START_REF] Irani | Recovery of ego-motion using region alignment[END_REF]. It provides the key advantage to be very fast and further experiments will also demonstrate its robustness. Several distances have been defined to compute the similarity between two histograms (cf [START_REF] Rubner | The earth mover's distance as a metric for image retrieval[END_REF] for a review). For experiments, we have implemented and evaluated two popular methods: Minkowski-form distance of order 1 (L 1 ) and histogram intersection [START_REF] Swain | Color indexing[END_REF]:

d(H, K) = N b i=1 |H(i) -K(i)| and d(H, K) = 1 - N b i=1 min(H(i), K(i)) N b i=1 K(i) (1)

inria-00325320, version 1 -28 Sep 2008

where H and K are two histograms composed of N b bins.

As the sizes of the regions can be different, our algorithm must be able to compare histograms containing a different number of observations. This problem can be solved by histogram normalization, which can be done in two ways:

H(n) = H(n) N b i=1 H(i)
and

H(n) = H(n)w(n) N b i=1 H(i) (2)
where w(n) is the width of the n th bin. The basic and intuitive solution is to divide the number of observation of each bin by the total number of observations (cf eq (2)-left). Thus each bin corresponds to the proportion of data and their sum is 1. Another solution consists in dividing each bin by the total number of observations and multiplying by the bin width w (cf eq (2)-right). Whereas this normalization is less intuitive, it permits to use the histogram to model a probability density function (the integral of the histogram is 1).

Matching of regions and VPs

To build the correspondences of regions between the previous and current images, we had initially performed the following procedure: for each region in the current image, test all the regions in the previous image and select the one maximizing the histogram similarity. However this basic method has several problems. First of all, two regions in the current image can be matched to the same region in the previous image. One solution would be to perform a disambiguation process by double-cross checking (i.e. matching from current to previous images, then from previous to current images and finally keep the matches that have the same single correspondence). However it might lead to the fact that a region has no correspondence. Second, contrary to what could be thought, once the regions are matched, it is not trivial to get the combination of VPs that leads to this matching. Third, we could obtain a solution that is not physically possible. Indeed, the list of matched VPs in the previous and current images (v i t-1 and v i t ) must verify the relation

v i t = Rv i t-1
, where R is the rotation matrix between the two images. If this relation is verified, the matching is said physically possible otherwise physically impossible because a rotation that maps the VPs does not exist. Regarding all these difficulties, we preferred the following approach: we test all the physically possible matching solutions and pick up the one that maximizes the sum of the histogram comparisons for all the regions. Given a VP, it exists only 4 combinations of the two other VPs thanks to the right-hand constraint. So for 3 VPs and their opposite direction, it exists 2 × 3 × 4 = 24 physically possible hypothesis. However some hypothesis are repeated. There exists a total number of 16 non-repeated combinations of VPs: (x, y, z), (x, z, -y), (x, -z, y), (x,(y,x,(y,z),(z,y,(z,x),y,x),x,z),y,z,y),z). The number of non-repeated combinations can be reduced to only 4 if we assume that the vertical vanishing point remains stable (planar motion).

In some cases, the number of regions between two images might be different because some spherical regions might not be projected inside the image. To handle this situation, we used the following simple technique: if the projection of a spherical region in the image contains less than a few number of pixels (less than 20 in our code), its histogram distance is set to 0 for all its physically possible matching regions in the other image.

In a theoretical point of view, the method proposed in this paper assumes the regions are invariant to camera motion. In practice, the histograms representing the regions could change a lot when the camera suddenly approaches or leaves an object that represents a large part of the field of view (e.g. wall, near car, etc...). In our application, the vehicle (ground or aerial) is expected to approach no objects very suddenly. Therefore the histograms should not change dramatically. However in some real cases, this constraint might not be verified and the camera may approach some large objects, such as a car, but experimental results will show that our algorithm can successfully handle such situations.

Experimental Results

Methods used for comparison

To compare our method, we have implemented two existing techniques: the continuity constrain and one method of line matching. The continuity constraint matches the pair of VPs having the lowest angular distance. Formally, the i th vanishing point v t i of frame t is matched to the vanishing point v t-1 j of frame t -1 which is solution of: arg max

j |v t i • v t-1 j | (3)
The choice of a method for line matching was more difficult. Indeed the epipolar geometry is unknown and basic experiments have shown that simple constraints based on orientation, length, overlapping, average contrast or midpoint did not work in our catadioptric videos. Therefore we have selected the method of [START_REF] Schmid | Automatic line matching across views[END_REF] for short range motion. The idea is to treat each line as a list of points to which neighborhood correlation is applied as a measure of similarity (cf Fig 4). The point-to-point correspondence with an other line is obtained by searching along the line with a winner-takes-all matching strategy. In practice, the matching cost of two lines l i and l j is defined as:

cost(l i , l j ) = P i ∈l i max P j ∈l j ZN CC(P i , P j ) ( 4
)
where ZN CC(P i , P j ) computes the zero mean normalized cross-correlation between the 2 square neighborhoods centered at P i and P j . Two lines l i and l j are matched if cost(l i , l j ) > thresh and l j is the solution of arg min l k cost(l i , l k ). Since some lines in the left image may be matched to a same line in the right image, a global disambiguation process for selecting the most relevant correspondences of lines is applied by double-cross checking. The final step matches each VP of the current frame with the VP of the previous frame having the highest number of corresponding lines. An important remark is that the line matching permits to build the correspondences between the vanishing points (and between the groups of parallel lines) but only up to a sign. For example this approach cannot differentiate the matchings v t-1 ↔ v t and v t-1 ↔ -v t . This is very important because an error on the sign of the VP leads to a totally wrong estimation of the rotation. Generally, the choice between v t and -v t is made on the maximum of v t-1 • v t and v t-1 • -v t . This technique can deal with rotation lower than 90 • . Finally, since the line matching procedure is very slow, our implementation aims to match only the 10 longest (i.e. the most stable) lines of each group of parallel lines. Fig. 4. Extraction of VPs (displayed in yellow squares), their associated lines (red and green conics) and associated points (cyan) by [START_REF] Bazin | Rectangle extraction in catadioptric images[END_REF] in two consecutive images of the sequence Gungdong1. The line matching technique of [START_REF] Schmid | Automatic line matching across views[END_REF] for short range motions aims to build the line correspondences by matching the points associated to the lines.

Results

For clarity to general readers, we explicitly write the procedure of the proposed method. It is composed of the following main steps:

1. given a list of VPs for the previous and current images, build the spherical regions of both images (cf section 2.2) and their histograms. 2. for each physically possible solution (a) compute the histogram similarity between each region in the current image and their corresponding region in the previous image (cf section 2.3) (b) compute the total score as the sum of the similarities 3. the VP matching corresponds to the solution having the highest score For the experiments, the camera is calibrated by [START_REF] Barreto | Geometric properties of central catadioptric line images and their application in calibration[END_REF] and we have used the framework of [START_REF] Bazin | Rectangle extraction in catadioptric images[END_REF] to detect the lines and the vanishing points. To validate our inria-00325320, version 1 -28 Sep 2008

proposed method, we have performed several series of experiments and for each experiment, we have tested the two region definitions and the two histogram distances. Due to space limitation, we only include the results obtained by the region definition2. For more results, the readers are invited to refer to our website http://rcv.kaist.ac.kr/∼jcbazin/.

In a first experiment, we have tested two important aspects on the sequence ParkingStraight. This sequence contains a large rotation around the z-axis and in some frames, the VPs lie outside the image (Fig 5). As depicted in Fig 6, our method is able to match the regions and thus can correctly track the associated VPs. In Fig 7, we compare the rotation angles estimated by the continuity constraint and our proposed method with a calibrated Inertial Measurement Unit (IMU). It is important to note that the continuity constraint failed for this sequence due to the rotation higher than 45 • around the z-axis (yaw angle) at the 69 th frame. The line matching based approach managed to track the VPs for small intra-frame motions. However as soon as rotation occurs, correlation fails because the ZNCC is not invariant to rotation. In a second test, we have analyzed the dependency of the histogram matching to the translation on the sequence Gungdong1. Experiments showed that translation has no effect at the motion speed of the original sequence (about 30cm between each image at 3fps). Thus the regions were correctly matched for the whole sequence. Obviously, if the translation speed is very large, then it becomes very hard to match the regions. To study faster motion (i.e. larger translation), we have skipped some images of the sequence and applied the same method. Results have shown that we can handle up to about 4meters between each image (40 images were skipped) and still correctly track the VPs. Figure 8 shows two pairs of images with 40 (success) and 50 (failure) skipped frames. The continuity constraint and the line matching based approach worked properly in the original sequence because there are only very small rotations and translations. Finally, we have applied our algorithm in a difficult experiment. The sequence Gungdong2 contains two important difficulties. First, it is a dynamic environment composed of moving cars and pedestrians. And second, large objects (cars) approach the camera. This sequence contains also an additional specificity: only 2 VPs are detected. As depicted in Fig 9, our approach works successfully and can correctly handle the two difficult aspects of dynamic environment and large objects approaching the camera. To test our algorithm with 3 VPs, we have synthesized a virtual third VP which is orthogonal to the 2 other VPs. Fig 10 shows that our proposed method works also with 3 vanishing points. The continuity constraint worked correctly for this sequence because the intra-frame rotation is small. The line matching based approach failed for some frames especially because of the image blur.

inria-00325320, version 1 -28 Sep 2008

For all the studied sequences, both region definitions and both histogram distances have lead to the same results of region matching. We have tested several different values for the number N b of histogram bins and experiments showed that this parameter does not play a key role as long as N b > 20bins. The continuity constraint runs almost instantaneously. On the contrary, matching lines is extremely time consuming, especially when the scene contains a large number of lines or long lines. Thus it is totally impossible to use this approach for real-time systems. In terms of complexity, to split the sphere, the proposed Fig. 9. Matching of the spherical regions in 4 consecutive images of the sequence Gung-dong2 with a dynamic environment (car and pedestrians) and large object approaching the camera with 2 vanishing points using region definition2.

inria-00325320, version 1 -28 Sep 2008

algorithm performs of the order of N * height * width/(s+1) 2 dot products where s is the sampling rate (in pixels) and N the number of vanishing points. We have tested the importance of s and experiments have shown that s = 0, 5, 10 pixels reach similar results for region matching so we finally set s = 10. The execution time using non-optimized C++ code was about 6ms only per frame for sphere splitting and histogram comparison with s = 10 pixels and N = 3 vanishing points. Therefore the proposed method can be easily used for real-time applications.

Conclusion

Estimating the rotation by vanishing points is very popular. This approach usually consists of two steps: first, extract the VPs and second, match them in a sequence. It is widely considered that the second step is so simple that there is no reason to work on this aspect. However we have shown that existing methods (essentially continuity constraint and line matching) suffer from many limitations: they cannot handle large rotations, are very slow to execute and/or assume stable line detection. As a consequence, these methods cannot be applied for our work on real-time rotation estimation of dynamic vehicles using catadioptric vision. That is why in this paper, we have presented an original method to match the VPs in catadioptric videos. Our approach offers three important advantages. First its complexity depends only on the image size. Therefore it is fixed for any images, which permits to guarantee the execution time, and it is independent of the number/length of lines which is an important aspect for catadioptric images because a high number of long lines could be detected. Second it is very fast and can be applied for real-time applications since it runs in 6ms only. Finally, experiments on real data have demonstrated that our algorithm is robust to large rotation, translation, dynamic environment and image blurring.

Acknowledgement

This work has been performed within the STAR project of the Hubert Curien (Egide) partnership between RCV Lab at KAIST-Korea and MIS at UPJV-France. Authors also thank the anonymous reviewers for their useful comments and suggestions.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Example of splitting the image into regions according to definition1 with 2 (left) and 3 (right) dominant vanishing points.

Fig. 5 .

 5 Fig. 5. Extraction of VPs (displayed in yellow squares) and their associated lines (one color per group of parallel lines) in some frames of the sequence ParkingStraight where some VPs lie outside the image.

Fig. 6 .

 6 Fig.6. Correct matching of the spherical regions in 4 consecutive images of the sequence ParkingStraight with a large rotation motion using definition2. The matched regions are drawn in the same color. Note that due to a rotation higher than 45 • around z-axis, the continuity constraint fails for this sequence.

Fig. 7 .

 7 Fig. 7. Comparison of the three rotation angles roll (top), pitch (middle) and yaw (bottom) in degrees obtained by the continuity constraint (left) and the proposed method (right) along the 120 frames of the sequence ParkingStraight. These angles are drawn in blue and the ground truth data obtained by a calibrated IMU in red. The error of the continuity constraint occurs in yaw angle because the vertical VP is correctly tracked and the 2 horizontal VPs have been mismatched.

Fig. 8 .

 8 Fig. 8. Matching of the spherical regions in 2 pairs of images of the sequence Gung-dong1 with large translation using definition2. Top-row: success with around 4 meters displacement (40 skipped frames). Bottom-row: failure with around 5 meters displacement (50 skipped frames).

Fig. 10 .

 10 Fig. 10. Same than Figure 9 but using a virtual third vanishing point.