Kazushige Sugiura
email: sugiura@am.sanken.osaka-u.ac.jp

Yasushi Makihara
email: makihara@am.sanken.osaka-u.ac.jp

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

Omnidirectional Gait Identification by Tilt Normalization and Azimuth View Transformation

We propose an effective matching method of gait sequences containing changes of observed tilt and azimuth views provided by an omnidirectional camera. Given gait image sequence, observed tilt view and depth to the subject are normalized by re-projecting the images to a virtual tilt-free image plane orthogonally, and a series of tilt-and size-normalized gait silhouette images are constructed as Gait Silhouette Volume (GSV). On the other hand, a relatively wide range of azimuth view changes can be continuously observed by tracking the subject in the omnidirectional image, multi-view frequency-domain features can be obtain from the GSV as attractive multiple cues for identification. Observed azimuth view ranges of two gait sequences do, however, not always coincide, therefore a View Transformation Model (VTM) supported by reference view addition with geometrical model is exploited to synthesize missing-view gait features for each gallery and probe sequence in matching phase. Experiments of gait identification including 22 subjects from different view ranges demonstrate the effectiveness of the proposed method.

Introduction

Gait-based person identification is considered as a promising method for various applications such as wide-area surveillance because gait personalities can be observed at a distance from a camera, while other biometrics such as faces and fingerprints needs a person's approach to a sensor.

Recently, many gait identification methods have been studied [START_REF] Sarkar | The humanid gait challenge problem: Data sets, performance, and analysis[END_REF][2] [START_REF] Han | Individual recognition using gait energy image[END_REF]. One of the difficulties facing those approaches is an appearance change due to changes of viewing or walking direction. Yu et al. [START_REF] Yu | Modelling the effect of view angle variation on appearancebased gait recognition[END_REF] discussed the effects of view angle variation on gait identification and reported a performance drop when view difference is large. This fact implies that gait images from different views contain different types of features.

From this point of view, previous works handling view changes have been divided into two directions: view-invariant approaches and multi-view approaches.

View-invariant approaches try to match different-view gait image sequences by extracting view-invariant features or by transforming features' views. Kale et al. [START_REF] Kale | Towards a view invariant gait recognition algorithm[END_REF] proposed a method to synthesize arbitrary-view images from a single-view image with perspective projection by assuming a walking person as a planer object parallel to his/her sagittal plane (call it sagittal plane assumption). Makihara et al. [START_REF] Makihara | Gait recognition using a view transformation model in the frequency domain[END_REF] proposed a View Transformation Model (VTM) which enables to transform a few-view reference gait features to arbitrary-view features. These methods, however, treat only azimuth view changes, that is, they do not consider tilt view changes.

Multi-view approaches tries to improve identification performance integrating multi-view gait features for matching as multiple cues. Wang et al. [START_REF] Wang | Gait recognition based on fusion of multiview gait sequences[END_REF] introduced Dempster-Shafer (D-S) rule for fusing multi-view gait sequences. Sugiura et al. [START_REF] Sugiura | Gait identification based on multi-view observations using omnidirectional camera[END_REF] used an omnidirectional camera to observe a wide range of view transition of a tracked walking person. The methods [START_REF] Wang | Gait recognition based on fusion of multiview gait sequences[END_REF] [START_REF] Sugiura | Gait identification based on multi-view observations using omnidirectional camera[END_REF] are, however, not effective when an overlapped view range (call it "intersection views") between a gallery and a probe sequences is narrow. For example, if the intersection view is just a single view, the methods are degraded from multi-view approaches to single-view approaches in essentials.

Therefore, we propose an effective matching method of gait sequences containing changes of observed tilt and azimuth views provided by an omnidirectional camera. In the gait sequence captured by the omnidirectional camera, a range of observed azimuth view change is much wider than that of observed tilt view change, hence we make the most of observed azimuth view changes as attractive multiple cues for identification, while we normalize observed tilt change as nuisance for identification. First, because the sagittal plane assumption [START_REF] Kale | Towards a view invariant gait recognition algorithm[END_REF] works well for normalization of relatively small view change, we extend the assumption to the tilt normalization. Second, gait features for the exclusive-or observed azimuth views of gallery and probe views are synthesized by the VTM [START_REF] Makihara | Gait recognition using a view transformation model in the frequency domain[END_REF] to make the most of view ranges of a gallery and probe sequence. Then, features both for the intersection views and the exclusive-or views (call joined views "union views") are matched and the matching results are integrated for better identification. Note that the proposed method matches gait features for union views, while the previous methods [START_REF] Wang | Gait recognition based on fusion of multiview gait sequences[END_REF][8] do so only for intersection views.

The outline of this paper is as follows. First, construction of GSV considering tilt and depth normalization is addressed in section 2. Second, multi-view gait feature extraction from a omnidirectional image sequence is presented in section 3. Then, matching of gait sequences with different view ranges are addressed with the VTM formulation and reference view addition with geometrical model in section 4. Moreover, experimental results of gait identification are shown in section 5. Section 6 contains conclusions and further works in the area.

Construction of tilt and depth normalized GSV

A GSV is composed of spatio-temporal gait silhouette images which are normalized by height, tilt, depth, and the center of the region and which are aligned on the temporal axis. In this paper, the silhouette candidates are extracted by background subtraction and shadow removal, and then graph-cut algorithm segments out the silhouette (see [START_REF] Makihara | Silhouette extraction based on iterative spatio-temporal local color transformation and graph-cut segmentation[END_REF] for detail). In the following sections, we describe a procedure for construction of tilt and depth normalized GSV.

Observed azimuth view estimation

The first step is estimation of observed azimuth view. The observed azimuth view θ is defined as θ = (π -ϕ) + ρ, where ρ is an azimuth angle, and ϕ is a walking direction (see Fig. 1). In this paper, we calculate these values based on a foot point as shown in Fig. 1 (a). The azimuth angle ρ is simply defined as direction of a foot point P f (x f , y f ) in the omnidirectional image as shown in Fig. 3. The walking direction ϕ is estimated from a trajectory of foot points P F (X W f , Y W f , Z W f ) in a world coordinate. Here, the world coordinate is defined by an origin which is a middle point between a mirror focal point O m and camera center O c (see Fig. 1), and by three axes : X and Y axes which are parallel to x and y axes in the omnidirectional image, and Z axis whose direction is vertical against the ground.

Let (r f , ρ) and (R f , ρ) be the foot points of polar coordinate in the omnidirectional image and on the floor plane respectively. If the floor plane is regarded as another image plane, the distance H r from mirror focal point O m to the floor plane can be seen as focal length to the floor image plane. Then, radius R f is calculated as [START_REF] Yamazawa | Hyperomni vision: Visual navigation with an omnidirectional image sensor[END_REF]

R f = -(b 2 -c 2 )H r r f (b 2 + c 2 )f -2bc √ r 2 f + f 2 , ( 1
)
where f is focal length for the omnidirectional image plane, and b and c are hyperboloidal mirror parameters. Thus, walking trajectory on the floor plane is obtained as a time series of the foot points (R f , ρ). Next, walking direction ϕ is defined as a tangential direction of the estimated walking trajectory. Let (

X W f (n), Y W f (n)) and (V X W f (n) , V Y W f (n) )
V X W f (n) = X W f (n + ∆n) -X W f (n -∆n) 2∆n (2)
V Y W f (n) = Y W f (n + ∆n) -Y W f (n -∆n) 2∆n . (3)
Here, ∆n is set to be 15 [frame] considering velocity smoothness. Finally, walking direction ϕ n in nth frame is defined as direction of velocity vector (V

X W f (n) , V Y W f (n) ).
Figure 3 shows a transition of the azimuth angle ρ, the walking direction ϕ, and the observed azimuth view θ for a straight-walk sequence. While the walking direction ϕ keeps the almost the same values, the azimuth angle ρ changes widely from 340 deg to 280 deg. As a result, even if the walking trajectory is straight, the wide range of the views can be gained thanks to the azimuth angle changes as shown in Fig. 3.

Tilt and depth normalization

The second step is GSV construction considering tilt and depth normalization. Because a tilt changes by a depth from a camera to a subject, captured images vary even if observed azimuth view does not change. For example, when the subject walks near the camera, both feet do not appear in the same vertical position on the image due to perspective projection. Therefore tilt and depth normalization is needed. Concretely speaking, we assume a walking subject as a plane object parallel to his/her sagittal plane (call it sagittal plane assumption), and create a silhouette image on the sagittal plane. Then, a virtual camera is set on the same height as the body center point (let it be P and tilt and depth are normalized by orthogonal projection from the silhouette image with the camera. Note that Kale et al. [START_REF] Kale | Towards a view invariant gait recognition algorithm[END_REF] normalize observed azimuth view under the sagittal plane assumption, and that in case of large view difference, transformation error becomes large due to self occlusion (see [START_REF] Makihara | Gait recognition using a view transformation model in the frequency domain[END_REF]). For example, in case of front oblique view, backward arm swing for the opposite side to a camera is occluded by the body, while that in case of side view is not occluded. On the other hand, we apply sagittal plane assumption to relatively small change of tilt, hence the self occlusion effects are much less.

C (X W c , Y W c , Z W c )),
Thus, a sagittal plane is defined as the first step to the normalization. It is supposed that the subject walks heading toward walking direction and stands vertical to the floor plane (see Fig. 1). Based on the assumption, the sagittal plane turns out to pass the foot point P F and is composed by two vectors of vertical direction and walking direction, and it is defined as

tan ϕ = Y W -Y W f X W -X W f . ( 4
)
Next, let the head point in the sagittal plane and the omnidirectional image be P T (X W t , Y W t , Z W t ) and P t (x t , y t , z t ) respectively. Then a ray of the head point in the world coordinate is defined as tan ρ = Y W /X W = y t /x t (5)

Z W = √ 1 + tan 2 X W tan α + c, (6)
where, γ and α are elevation and depression angles defined in Fig. 2 respectively, and they are defined as

α = tan -1 (b 2 + c 2 ) sin γ -2bc (b 2 -c 2 ) cos γ (7) γ = tan -1 f √ x 2 t + y 2 t . ( 8
)
As a result, the head point P T is solved by Eqs. from ( 4) to [START_REF] Sugiura | Gait identification based on multi-view observations using omnidirectional camera[END_REF]. Finally, a body center point P C is given as a middle point between the head point P T and foot point P F as follows

X W c = X W t + X W f 2 , Y W c = Y W t + Y W f 2 , Z W c = Z W t + Z W f 2 . ( 9
)
Next, each point silhouette in the omnidirectional image coordinate is projected to the sagittal plane in the same way as the head point, and it subsequently transformed into a point in the virtual camera coordinate. Here, the virtual camera coordinate is defined by an origin O V (0, 0, Z W c ), and Z-axis which passes body center and is parallel to the floor plane, Y-axis which is perpendicular downward, and X-axis which is orthogonal to Y and Z axes (see Fig. 2). Let R and t be rotation matrix and translation vector from the world coordinate to the virtual camera coordinate. They are defined as

R =   cos( π 2 -ρ) 0 sin( π 2 -ρ) sin( π 2 -ρ) 0 -cos( π 2 -ρ) 0 -1 0   (10) t = [ 0 0 -Z W c ] T . ( 11
)
Then, each point defined in the virtual camera coordinate is projected to a virtual image plane orthogonally. Finally, the image is normalized so that the height (Z W t -Z W f ) can be just predefined height H g , and so that the aspect ratio of image can be kept. Here, H g is set to be 30 pixel empirically. Finally a GSV is constructed by aligning images on the temporal axis.

Figure 4 shows GSV examples for multiple observed azimuth views. We can clearly see appearance changes in each view, while both feet lie on almost the same vertical position on the image thanks to tilt and depth normalization. In this section, Multi-view gait feature extraction is described briefly (see [START_REF] Sugiura | Gait identification based on multi-view observations using omnidirectional camera[END_REF] for detail).

Frequency-domain feature extraction

First, gait period N gait is detected by maximizing the normalized autocorrelation of the constructed GSV for the temporal axis. Next, subsequence S ns composed of N gait frames is picked up from a complete sequence S . A Discrete Fourier Transformation (DFT) for the temporal axis is then applied for the subsequence, and amplitude spectra normalized with gait period N gait are calculated. In this paper, direct-current elements (0-times frequency, averaged silhouette) and lowfrequency elements (1-and 2-times frequencies) are chosen as gait features. Let a be a feature vector composed of elements of the amplitude spectra. As a results, the dimension of the feature vector a sums up to 20 × 30 × 3 = 1800.

Multi-view feature extraction

In this section, multi-view feature extraction is introduced based on the estimated observed azimuth views. First, multiple basis views θ i (i = 1, 2, . . .) are chosen from observed azimuth views at 15 deg intervals. Next, a basis frame n θi corresponding to a basis view θ i is found from a complete sequence, and a subsequence is picked up as a set of N gait frames around the basis frame n θi as shown in Fig. 5.

Results of multi-view feature extraction for multiple subjects are shown in Fig. 6. In this figure, each block indicates each subject, and each row and column indicate observed azimuth view and frequency respectively. We can see individual differences, for example, swing motion difference of subject 2 and 4 in 2-times frequency of 270-deg features. In addition, we can also see view differences for each subject. Thus, by integrating the different type of features across views, gait identification performance should improve more than the case of a single-view feature. Next section gives how to match the multi-view features.

Gait feature matching using a VTM

Overview of VTM

First, a typical implementation of a VTM is shown in Fig. 7. In the training phase, gait features are collected from a limited number of training subjects from all views to form a training set that is then used to create the VTM. Gait features from identification-target subjects are then stored from only a few reference views. Note that the identification-target subjects are different from the training subjects for the VTM and that not all-view galleries but few-view galleries are stored for the identification-target subjects. In the identification phase, this reference set is transformed into the gallery set with the same view as the probe view using the VTM and then matching between the gallery and the probe is processed.

a 1 θK • • •a M θK    = U SV T =    P θ1 . . . P θ K    [ v 1 • • • v M ] , ( 12
)
where U is the KN A ×M orthogonal matrix, V is the M ×M orthogonal matrix, S is the M × M diagonal matrix composed of singular values, P θ k is the N A × M submatrix of U S, and v m is the M dimensional column vector. The vector v m is an intrinsic feature vector of the mth subject and is common for all views. The submatrix P θ k is a projection matrix from the intrinsic vector v to the feature vector for view θ k , and is common for all subjects. Thus, the feature vector a m θi for the view θ i of the mth subject is represented as

a m θi = P θi v m . ( 13
) θref -θ ref 180+θ ref 180-θ ref sym.
pers.

pers. + sym. . . .

Walking direction

P θ ref (N ref θ )    +     a m θ ref (1)
) } are given for an identification-target subject, arbitrary-view galleries âm θi can be transformed from the references by the VTM.

Reference view addition with geometrical model

In this section, we briefly describe addition of virtual reference view based on the geometrical model to make view transformation more precise (see [START_REF] Makihara | Which reference view is effective for gait identification using a view transformation model?[END_REF] for detail). First, when weak perspective projection is assumed (call it pers.), the silhouette image observed from the opposite side (θ + 180) deg becomes a mirror image of the original silhouette image thanks to tilt and depth normalization. Moreover, when a left-right symmetry of gait motion is assumed (call it sym.), the silhouette image from (360 -θ) deg also becomes a mirror image of the original. When both of the weak perspective projection and the symmetry are assumed (call it pers.+sym.), the silhouette image from (180 -θ) deg becomes the same image of the original.

Gait feature transformation for exclusive views

Let S P and S G be complete sequences for probe and galley respectively. Also observed azimuth views for probe and gallery are defined as

θ P = {θ P (i)|i = 1, • • • , N P θ } and θ G = {θ G (j)|j = 1, • • • , N G θ }
, and corresponding gait features as a P θ P (i) and a G θ G (j) respectively. Then, an intersection and union set between probe and gallery are defined views as intersection views

θ int = {θ int (k)|k = 1, • • • , N int θ } and union views θ uni = {θ uni (k)|k = 1, • • • , N uni θ } respectively.
In addition, a set of excluded views (missing views) for probe and gallery are defined as excluded views θ P,ex = {θ P,ex (i

)|i = 1, • • • , N P,ex θ } and θ G,ex = {θ G,ex (j)|j = 1, • • • , N G,ex θ
} respectively. Note that excluded views for gallery and probe are discarded in the matching procedure in the previous works such as [START_REF] Sugiura | Gait identification based on multi-view observations using omnidirectional camera[END_REF].

Next, probe gait features for the excluded views θ P,ex are recovered in order of the following priorities.

1. Reference addition with geometrical model from the observed azimuth views θ P (let them be θ P,add ). 2. VTM from the observed azimuth views θ P and the added views θ P,add .

In the same way, gallery gait features for θ G,ex are transformed.

As a result, we can define probe and gallery gait features for the union views as a P,uni θ uni (k) and a G,uni θ uni (k) by using original and transformed gait features respectively.

Matching

In this section, matching of the union-view gait features is addressed. The matching measure for each union view is simply chosen as the Euclidean distance as

d(a P,uni θ uni (k) , a G,uni θ uni (k) ) = ∥a P,uni θ uni (k) -a G,uni θ uni (k) ||. (15)
Next, matching measures between two complete sequences S P and S G are defined. Because the distance distributions are different for each view, z-normalization is processed before integration as

d z (a P,uni θ uni (k) , a G,uni θ uni (k) ) = d(a P,uni θ uni (k) , a G,uni θ uni (k) ) -d θ uni (k) σ d θ uni (k) , ( 16
)
where d θ uni (k) and σ d θ uni (i) are an average and standard deviation of distances of all subjects in the gallery for each union view θ uni (k) respectively, and d z is a normalized distance. Finally, an average of the normalized distance is defined as complete matching measure:

D(S P , S G ) = 1 N uni θ N uni θ ∑ k=1 d z (a P,uni θ uni (k) , a G,uni θ uni (k) ). (17)
5 Experiments

Datasets

A dataset of walking sequences was obtained in a room (see Fig. 9) and a total of 22 subjects joined the experiments (see Tab. subjects). The camera used was Sony Inc. DCR-VX2000, and images were captured by 720 × 480 pixel size at 30 fps. The hyperboloidal mirror and camera parameters were a = 13.722, b = 11.708, c = 18.038, f = 427.944 (unit: mm). The omnidirectional camera was placed at an diagonal point of 5m by 5m square space and each subject was asked to walk between specified points as shown in Fig. 9. Totally 2 test sets composed of 4 sequences were obtained for each subject and multiple basis views were extracted at 15 deg intervals for each sequence as shown in Tab. 2. Though the proposed method can also treat curving sequences, the sequences in this experiment were limited to straight one to easily obtain almost the same walking courses for all the subjects.

Feature transformation

The dataset is divided into 2 sets: training set for the VTM and test set for gait identification experiment including 11 subjects respectively, namely, there are no overlapped subjects between training and test set.

In the previous methods (e.g. [START_REF] Sugiura | Gait identification based on multi-view observations using omnidirectional camera[END_REF]), only a single intersection view {75} and two intersection views {255, 270} are used for matching in experiment set Ex1 and Ex2 respectively. On the other hand, transformed features for excluded views are also used in the proposed method as shown in Fig. 10. For experiment set Ex1, excluded views for sequence S1 (Gallery) are {90, 105, 120}, and virtual reference views {105, 120} are added from 2 gallery reference views {75, 60} respectively, then feature for view {90} is transformed from 4 gallery reference views {60, 75, 105, 120}. On the other hand, an excluded view for sequence S2 (Probe) is {60}, and virtual reference view {60} is added from a gallery reference view {120}. As a result, a total of 5 pairs of gait features for views {60, 75, 90, 105, 120} are obtained, and they are used for matching.

For experiment set Ex2, because views {255, 270} for sequence S3 (gallery) are included in views {240, 255, 270, 285, 300} for sequence S4 (probe), no features are added to S4. Then virtual reference view {285} are added from a gallery reference view {255}, and then missing views for sequence S3 {240, 300} are transformed from 3 gallery reference views {255, 270, 285}. As a result, a total of 5 pairs of gait features are obtained.

Gait identification results

The proposed method was compared with the multiple intersection view method [START_REF] Sugiura | Gait identification based on multi-view observations using omnidirectional camera[END_REF] to confirm the effectiveness of feature transformation. In this section, the proposed method and the previous method are denoted by "VTM" and "NT (No Transformation)" respectively.

The gait identification experiments were repeated 20 times for different combination of training and test sets. The results were evaluated by Receiver Operating Characteristics (ROC) curves [START_REF] Phillips | The feret evaluation methodology for face-recognition algorithms[END_REF]. The ROC curves shows relation between False Rejection Rate (FRR) P F R and False Acceptance Rate (FAR) P F A when the receiver changes the acceptance thresholds. In the ROC evaluation, a curve near the left bottom corner indicates high performance because it realizes both low false rejection and low false acceptance.

ROC curves for experiment sets in Tab. 2 are illustrated in Fig. 11. As a whole, ROC curves for VTM are closer to the left bottom than those for NT. Then, Equal Error Rate (EER) is picked up by calculating an intersection of the ROC curve and EER line P F R = P F A as a typical performance measure for ROC curve. As a result, EERs decrease from 8.4% for NT to 6.3% for VTM in Ex1, 6.0% for NT to 5.0% for VTM in Ex2 respectively, and it turns out the effectiveness of the proposed method.

Conclusion and future works

We propose an effective matching method of gait sequences containing changes of observed tilt and azimuth views provided by an omnidirectional camera.

Given gait image sequence, observed tilt view and depth to the subject are normalized by re-projecting the images to a virtual tilt-free image plane orthogonally under a assumption that a walking subject is a plane object parallel to his/her sagittal plane [START_REF] Kale | Towards a view invariant gait recognition algorithm[END_REF]. Then, a series of tilt-and size-normalized gait silhouette images are constructed as Gait Silhouette Volume (GSV) and frequencydomain feature of the GSV are calculated subsequently. Because a relatively wide range of azimuth view changes can be continuously observed by tracking the subject in the omnidirectional image, multi-view features can be obtain from a sequence as attractive multiple cues for identification. Observed azimuth view ranges of the probe and the gallery do, however, not always coincide, therefore a View Transformation Model (VTM) [START_REF] Makihara | Gait recognition using a view transformation model in the frequency domain[END_REF] supported by reference view addition with geometrical model is exploited to synthesize excluded-view (missing-view) gait features for each gallery and probe sequence in matching phase. Note that the proposed method exploited union views between the probe and gallery to make the most of observed azimuth view ranges while previous works such as [START_REF] Sugiura | Gait identification based on multi-view observations using omnidirectional camera[END_REF] exploited gait features only for intersection views, that is, discarded the excluded views.

Gait identification experiments including 22 subjects from different view ranges were made to show the effectiveness of the proposed method. Compared with the previous work [START_REF] Sugiura | Gait identification based on multi-view observations using omnidirectional camera[END_REF], Equal Error Rate (EER) decreases from 8.4% to 6.3% for sequences with a single intersection view, and does from 6.0% to 5.0% for those with a two intersection views. Consequently, it was clear that the proposed method contributed to better performance.

In this paper, though equal weights are used when integrating matching score for all the union views for simplicity, matching reliance is actually dependent on the following factors:

-Whether features for matching are original or transformed ones, namely, whether a view of the feature is intersection view or excluded view between a probe and gallery. -View transformation accuracy derived from the number of reference views or from view differences between a transformed view and the reference views.

Hence, one of future directions is the optimal weights assignment in matching considering the above factors. We propose an effective matching method of gait sequences containing changes of observed tilt and azimuth views provided by an omnidirectional camera. This research was supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Scientific Research (S).

Fig. 1 .

 1 Fig. 1. Definition of observed azimuth view and sagittal plane

Fig. 3 .

 3 Fig. 3. Changes of azimuth angle ρ, walking direction ϕ, and observed azimuth view θ

Fig. 4 .

 4 Fig. 4. GSV examples for multiple observed azimuth views

Fig. 5 .

 5 Fig. 5. Overview of multi-view feature extraction

Fig. 6 .Fig. 7 . 4 . 2

 6742 Fig. 6. Multi-view features for each subject (every 15 deg) Training set (all views) 1 2 MT θ1

Fig. 8 .

 8 Fig. 8. Overview of reference view addition Feature vector transformation from N ref θ reference views (let them be θ ref = {θ ref (k)|k = 1, • • • , N ref θ } is now easily obtained by least-square method as

Figure. 8

 8 shows overview of these assumptions. Hence, once a gait feature for reference view θ ref is obtained, we can virtually add the same feature for view (180 -θ ref ) and a mirror feature for view (θ ref + 180) and (360 -θ ref ).

Fig. 9 .

 9 Fig. 9. Experimental setup (left) and scene (right)

Fig. 10 .

 10 Fig. 10. Feature transformation

Fig. 11 .

 11 Fig. 11. ROC curves

Table 1 .

 1 Breakdown list of subjects

	Age Male Female Total
	20-29 10	4	14
	30-39 5	2	7
	40-49 0	0	0
	50-59 0	1	1
	Total 15	7	22

Table 2 .

 2 Gait sequences and their views (G: Gallery, P: Probe)

	Set Sequence Course	Views
	Ex1	S1 (G) P 3-P 1 S2 (P) P 2-P 1	60, 75 75, 90, 105, 120
	Ex2	S3 (G) P 1-P 4 S4 (P) P 1-P 5 240, 255, 270, 285, 300 255, 270


Sreekar Krishna

Dirk Colbry

John Black

Vineeth Balasubramanian

Sethuraman Panchanathan

A Systematic Requirements Analysis and Development of an Assistive Device to Enhance the Social Interaction of People Who are Blind or Visually Impaired

People who are blind can be at a disadvantage in social situations because face-to-face communication relies heavily on non-verbal cues. Lack of access to cues such as eye contact can sometimes lead to awkward situations, such as answering a question that was directed to another person. This problem is compounded by the fact that sighted people are not always aware of their use of these nonverbal cues, and they do not take this into account when communicating with people who are blind. In the long term, this can limit employment opportunities for people who are blind, can adversely impact their professional advancement, and can even isolate them. To address this problem, we propose a methodology for determining and enumerating the most important needs of people who are blind, as they interact with others in social situations. Next, we establish design guidelines for building a Social Interaction Assistant to provide access to essential visual information during social encounters for the visually impaired. Finally, we use our design guidelines to develop a wearable Social Interaction Assistant prototype that is aimed at providing this essential information in real-time, during social interactions.

Introduction

In the United States 1.3 million people are legally blind and 11.4 million people have some sort of visual impairment. People with visual impairments use creative methods for coping with the lack of visual information in their daily lives. For example, specialized training can help people with visual impairments use their sense of hearing more effectively, training in the use of a white cane can help them navigate successfully, and training in the use of screen reading software can make computers more accessible.

Historically, the development of assistive devices has tended to be characterized by a technology-centric approach, which begins by asking "What can we do?" This approach is often inspired by a newly emerging technology, and it tends to produce one-size-fitsall technological solutions to the obvious problems that people with disabilities might Sreekar.Krishna@asu.edu; Ph: +1 (480) 326 6334; Fax: +1 (480) 965 1885 have already largely solved for themselves. One example of this type of technologycentric approach is the development of numerous robotic guide dogs [START_REF] Tachi | Electrocutaneous communication in a guide dog robot (meldog)[END_REF] [2] [START_REF] Kulyukin | Robocart: toward robot-assisted navigation of grocery stores by the visually impaired[END_REF]. Sadly, the technology-centric approach often fails to address some less obvious, but more important, unsolved problems.

Another problem with the technology-centered approach is that it often focuses only on the disabilities of the user, without taking into full account the user's abilities. For example, people who are blind are often able to perceive the presence of large objects in the environment around them. Ambient sound sources in the environment provide a form of audio illumination and the resulting sounds bouncing off of objects (or sounds shadowed by objects) allow a person who is blind to detect the presence of those objects [START_REF] Shinohara | Designing assistive technology for blind users[END_REF]. Sometimes in attempting to overcome a disability, developers of assistive devices unintentionally interfere with the user's abilities. For example, navigational assistive devices that require the user to wear headphones or earphones deprive the user of sounds that are vital to the perception of the environment.

In an effort to avoid the problems of technology-centric design, this paper describes a human-centric approach that begins by asking "What is needed?" It answers this question by identifying unmet needs (as seen by people with disabilities) and guides the development of assistive devices to specifically address these needs. This human-centric approach often uncovers a wide variety of such needs, inspiring the development of a variety of different devices.

Motivation

In order to identify unmet needs of the visually impaired community, we established two focus groups consisting primarily of people who are blind, as well as disability specialists and parents of students with visual impairment and blindness. Members of these focus groups who were blind or visually impaired were encouraged to speak freely about their challenges in coping with daily living. During these focus groups, the participants agreed on many issues as being important problems. However, one particular problem -that of engaging freely with their sighted counterparts -was highlighted as a particularly important problem that was not being addressed by technology specialists. As an example of this type of social disconnect, consider a simple form of nonverbal communication: glancing at a watch to signal that it is time to wrap up a meeting. The sighted participants might respond to such a glance automatically, without consciously realizing that this visual information is not accessible to a participant who is blind. Similarly, a sighted person asking a question in a group will use gaze direction and eye contact to indicate to whom the question is directed. Without access to this visual cue, people who are blind might be left wondering whether the question was directed towards them. They can answer immediately (at the risk of feeling foolish if the question was not directed at them) or they can wait to see if anyone else answers (and risk being thought of as rather slow witted).

People who are blind often find themselves unable to independently access essential visual information. This can be a particularly difficult problem in social situations, where as much as 65 % of two-person conversation is non-verbal [ [START_REF] Knapp | Nonverbal communication in human interaction[END_REF], p.30]. Compounding this problem is the fact that sighted people are often unaware of the nonverbal cues that they use in social situations, and do not make allowances for this when communicating with people who are blind. People who are blind are often unwilling, or unable, to constantly ask others for this non-verbal information, because it places a perceived burden on friends and family. Over time such situations can put a person who is blind at a disadvantage, potentially leaving them socially isolated [START_REF] Wiener | Audition for the traveler who is visually impaired[END_REF]. This social isolation is an important concern. Humans are social beings who need meaningful communication and interaction with others to lead healthy and productive lives [START_REF] Raver | Increasing social skills training for visually impaired children[END_REF]. However, while many assistive devices have been developed to meet a wide range of the needs of people who are blind, there has not been enough attention given to the development of assistive devices that satisfy the need for access to nonverbal communication cues. In response, our goal has been to develop assistive devices that will allow people who are blind to access important visual information during social encounters.

Section 2 lists the needs that the members of our focus groups and the respondents to our online survey felt were most important in social situations. Section 3 discusses existing computer vision algorithms that might be used to meet those needs. Section 4 presents the three design alternatives that we considered for our Social Interaction Assistant, and Section 5 describes the hardware and software implementation that we developed. Section 6 provides a summary, and a discussion of our plans for future development.

Requirements for a Social Interaction Assistant

Members of our focus groups voiced many concerns about social interaction and isolation. Based on these conversations, we compiled a list of needs that are often experienced by people with visual impairments. In doing so, we identified two aspects of social interaction that are particularly important: access to the non-verbal cues of others during social interactions, and how one is perceived by others during social interactions.

Access to Non-Verbal Cues

Access to the non-verbal cues of others during a social interaction is something that sighted people take for granted. Non-verbal cues such as eye contact, hand gestures, and body posture play very important roles in social communication [START_REF] Burgoon | Interpersonal deception: Ix. effects of social skill and nonverbal communication on deception success and detection accuracy[END_REF]. As an important first step in the design of our Social Interaction Assistant, we decided to develop a better understanding of the most important nonverbal cues that we need to convey to a person who is blind or visually impaired.

How One is Perceived by Others Although people who are blind cannot visually perceive their own appearance and demeanor during social interactions, members of our focus groups indicated that understanding how others perceived them was important. For example, assistive technology that makes the user stand out (such as the Jordy [START_REF]Low vision aids, low vision products, assistive technology from enhanced vision[END_REF] enhanced vision system) were rejected. "Don't make me look like a Martian" was a sentiment that was shared by most of the attendees. This sentiment makes it important that assistive technologies be extremely discreet. Ideally, assistive devices should allow a person who is blind or visually impaired to interact with sighted peers without those peers even being aware of their disability, or their assistive device.

Another cause of social isolation for people who are blind are distracting or unusual body mannerisms [START_REF] Knapp | Nonverbal communication in human interaction[END_REF]. For example, a person who is blind might rock back and forth during a conversation without being fully aware of how this is being perceived by sighted people. Training can make people who are blind more aware of the social norms, expectations, and needs of sighted people -for example, turning their head to face a sighted person as they speak to her as a substitute for establishing eye contact. Assistive technologies could also play a role in helping individuals who are blind recognize, learn, and practice body mannerisms that are considered socially appropriate.

Essential Requirements

As a first step toward the development of a Social Interaction Assistant, we used our focus group results to identify and enumerate the following list of needs for information that is not always accessible by people who are blind, as they engage in social interactions:

1. Knowing how many people are standing in front you, and where each person is standing. 2. Knowing where a person is directing his/her attention. 3. Knowing the identities of the people standing in front of you. [START_REF] Shinohara | Designing assistive technology for blind users[END_REF]. Knowing something about the appearance of the people standing in front of you. 5. Knowing whether the physical appearance of a person who you know has changed since the last time you encountered him/her. 6. Knowing the facial expressions of the person standing in front of you. 7. Knowing the hand gestures and body motions of the person standing in front of you. 8. Knowing whether your personal mannerisms do not fit the behavioral norms and expectations of the sighted people with whom you will be interacting.

Online Survey

We conducted a web-based survey in order to validate the list of needs that we identified from our focus groups, and to help establish the relative importance for each of these needs. This survey was anonymously completed by 27 people, of whom 16 were blind, 9 had low vision, and 2 were sighted specialists in the area of visual impairment.

The online survey consisted of eight questions that corresponded to the previously identified list of needs. Respondents answered each question using a five-point Likert scale:

(1) Strongly disagree, (2) Disagree, (3) Neutral, (4) Agree, and (5) Strongly agree. Table 1 shows the eight questions, sorted by descending importance, as indicated by the survey respondents (the question numbers correspond to the need listed in the previous section).

Need The Question

The Mean Score 8. I would like to know if any of my personal mannerisms might interfere with my social interactions with others.

3.4

Table 1: Results of the online survey

The histogram of responses (Fig. 1) from the online survey reveals the importance levels of the various needs. The responses to question 8 suggest that the respondents are highly concerned about how they are perceived by their sighted peers. The responses to questions 3, 6, and 7 suggest that respondents would like to know the identities, facial expressions and body gestures of the people with whom they are communicating. The responses to questions 4 and 5 indicate that there was a wide variation in respondents' interest in (4) knowing the physical appearance of people with whom they are communicating and (5) knowing about changes in the physical appearance of people with whom they are communicating. Many respondents indicated moderate, little, or no interest in either of these areas.

Relevance of Computer Vision in Building Solutions

Many of the needs for social interaction could be served by current and future computer vision research. For example, the problem of person recognition has been approached using algorithms for face recognition and gait-based identity recognition. Other research efforts in computer vision could be employed to meet other needs in the list. Table 2 shows the potential uses of existing computer vision algorithms for addressing the various needs in the list. Assessing attention a. Head pose estimation [START_REF] Murphy-Chutorian | Head pose estimation in computer vision: A survey[END_REF] b. Eye detection [START_REF] Park | In: Facial and Eye Gaze Detection[END_REF] c. Eye contact detection [START_REF] Park | In: Facial and Eye Gaze Detection[END_REF] d. Facial feature extraction [START_REF] Zhao | Face Processing: Advanced Modeling and Methods[END_REF] 3 Person identification a. Face recognition [START_REF] Turk | Face recognition using eigenfaces[END_REF] [11] b. Gait Recognition [START_REF] Moeslund | A survey of advances in vision-based human motion capture and analysis[END_REF] 4 & 5 Extracting physical descriptors a. Facial Feature extraction [START_REF] Zhao | Face Processing: Advanced Modeling and Methods[END_REF] b. Eye glass detection [START_REF] Zhao | Face Processing: Advanced Modeling and Methods[END_REF] c. Clothing detection [START_REF] Mori | Recovering human body configurations: combining segmentation and recognition[END_REF] 6 Facial expression a. Facial Feature extraction [START_REF] Zhao | Face Processing: Advanced Modeling and Methods[END_REF] b. Facial action analysis [START_REF] Zhao | Face Processing: Advanced Modeling and Methods[END_REF] 7 Gesture and mannerism recognition a. Motion analysis [START_REF] Moeslund | A survey of advances in vision-based human motion capture and analysis[END_REF] b. Skin region extraction [START_REF] Kakumanu | A survey of skin-color modeling and detection methods[END_REF] c. Activity recognition [START_REF] Moeslund | A survey of advances in vision-based human motion capture and analysis[END_REF] d. Body part detection [START_REF] Mori | Recovering human body configurations: combining segmentation and recognition[END_REF] e. Facial expression recognition [START_REF] Zhao | Face Processing: Advanced Modeling and Methods[END_REF] 8 Social training a. Rocking detection (Motion estimation) [START_REF] Moeslund | A survey of advances in vision-based human motion capture and analysis[END_REF] b. Social gaze training (Face detection and eye detection) [START_REF] Park | In: Facial and Eye Gaze Detection[END_REF] Table 2: Potential uses of computer vision algorithms

Alternative Platforms for a Social Interaction Assistant

Having determined the requirements for a Social Interaction Assistant, we next concentrated on a potential platform for the device. We observed that four important criteria had to be taken into account: (1) the device must be unobtrusive and socially acceptable;

(2) the device must be lightweight and compact for easy everyday use; (3) the device should be wearable, so users have their hands free; and (4) the device should allow the user to control the direction of the wearable device unobtrusively. Based on these considerations, we investigated three different conceptual approaches, including:

Concept 1: A wearable video camera in a clip-on device, and a small audio emitter device that could be worn on the ear without obstructing normal hearing. Both of these devices would be connected to a compact computing element such as an Ultra-mobile PC (UMPC) (Fig. 2).

Fig. 2: A clip on camera and small audio emitter

Concept 2: A tiny, ear-mounted video camera and sound emitter (inspired by Bluetooth headsets) mounted on a small device that communicates with a UMPC (Fig. 3).

Concept 3:

A tiny video camera and a sound emitter mounted unobtrusively in a pair of glasses -both of which are attached to a UMPC (Fig. 4).

Based on the previously mentioned criteria, we concluded that Concept 3 best met the requirements for unobtrusiveness, social acceptability, light weight, compactness, wearability, and ease of user control. We mounted an analog camera (1/3" CCD, 0.2 Lux light sensitivity, 92 • field of view and 320 line scan NTSC output) on the nose bridge of a pair of sunglasses. The analog data were converted to digital using a video digitizer that connected to the computing element (a UMPC) through a USB port. The audio output (conveying processed information) was delivered to the user through the earpiece of the glasses. The prototype device is shown in Fig. 5.

Fig. 5:

The prototype Social Interaction Assistant: Hardware

Prototype Software

The prototype Social Interaction Assistant processes the video stream from the camera, and uses existing computer vision algorithms to analyze the video frames (Fig. 6). The frames are processed by a face detection algorithm [START_REF] Viola | Rapid object detection using a boosted cascade of simple features[END_REF] that identifies the location of faces within the camera's field of view, sending a covert audio signal to the user when a face is detected. This is shown in Fig. 7, which is a screen shot of the demonstration software used to illustrate the functioning of the system.

The audio signal generated from the face detection result helps the user to know when someone approaches, allows the user to choose whether to initiate a conversation, and helps the user determine when to make eye contact. At the user's option, the Social Interaction Assistant can send detected faces to a face recognition component [START_REF] Turk | Face recognition using eigenfaces[END_REF] that analyzes the face, compares the resulting feature vector to a user-specific database, and speaks the identity to the user if there is a successful match. The system also provides a quantitative measure of its belief on the top matches in the database (as shown in Fig. 8), which may help the user assess the confidence of the recognition result. If the face in the scene is a new acquaintance (i.e. no high confidence match), the system captures 25 images of the new face, and the user is later prompted to provide the name of the person. This combined information is then added to the database, for future use.

Summary and Future Work

The Social Interaction Assistant described here is the result of a systematic exploration of the needs of individuals who are blind or visually impaired. As one member of our focus groups said, "I appreciate the fact that we have a hand in designing it now, instead of it just being given to us, without a chance to see what we can do to make it better."

We believe that current and future computer vision techniques have the potential to meet many of the needs that we have enumerated. Advances in computing technology have allowed us to package our prototype system in a laptop that can be carried in a backpack. The current prototype (shown in Fig. 5) is intended as a proof-of-concept. It works well in a controlled laboratory setting, but it cannot handle drastic changes in pose angle or lighting conditions. More computer vision work will be needed to better handle these challenges. However, the needs that we have enumerated above provide a clearly defined target for such research. With respect to longer range goals, we are working on methods to recognize features such as hair color, facial expression, age, and gender.

We believe that a Social Interaction Assistant, such as the one described here, has the potential to transform the way that people with visual impairments conduct their daily lives, by improving their confidence and ability to engage in social interactions. In addition, we believe that ongoing work in this area will focus and extend computer vision research that will have important applications in many other domains.

4 . 5 6. 4 3. 3 7. 2 1. 1 2..0 5 . 5 4.

 45432155 I would like to know what facial expressions others are displaying while I am interacting with them. 4.When I am standing in a group of people, I would like to know the names of the people around me.4.I would like to know what gestures or other body motions people are using while I am interacting with them. 4.When I am standing in a group of people, I would like to know how many people there are, and where each person is. 4.When I am standing in a group of people, I would like to know which way each person is facing, and which way they are looking. 4I would like to know if the appearance of others has changed (such as the addition of glasses or a new hair-do) since I last saw them. 3.When I am communicating with other people, I would like to know what others look like.

Fig. 1 :

 1 Fig. 1: Histograms of online survey responses

Fig. 3 :Fig. 4 :

 34 Fig. 3: An ear-mounted video camera and sound emitter

Fig. 6 :

 6 Fig. 6: The prototype Social Interaction Assistant: Software

Fig. 7 :

 7 Fig. 7: Screen shot of the demonstration software performing face detection; image captured from the camera on the prototype hardware.

Fig. 8 :

 8 Fig. 8: Confidence levels in face recognition output.

The Social Interaction Assistant PrototypeThe following sections detail the hardware and software developed for our prototype Social Interaction Assistant.


Olivier Koch
email: koch@csail.mit.edu

Seth Teller
email: teller@csail.mit.edu

A Self-Calibrating, Vision-Based Navigation Assistant

We describe a body-worn sensor suite, environment representation, set of algorithms, and graphical-aural interface designed to provide human-centered guidance to a person moving through a complex space. The central idea underlying our approach is to model the environment as a graph of visually distinctive places (graph nodes) connected by path segments (graph edges). During exploration, our algorithm processes multiple video-rate inputs to identify visual features and construct the "place graph" representation of the traversed space. The system then provides visual and/or spoken guidance in user-centered terms to lead the user along existing or newly-synthesized paths. Our approach is novel in several respects: it requires no precise calibration of the cameras or multi-camera rig used; it generalizes to any number of cameras with any placement on the body; it learns the correlation between user motion and evolution of image features; it constructs the place graph automatically; and it provides only coarse (rather than precise metrical) guidance to the user. We present an experimental study of our methods applied to walking routes through both indoor and outdoor environments, and show that the system provides accurate localization and effective navigation guidance.

Introduction

The ability to navigate effectively while performing long-duration walking excursions through spatially extended environments is fundamentally useful and difficult to achieve. Navigation systems have been proposed for environments in which GPS is available [START_REF] Golledge | A geographic information system for a GPS based personal guidance system[END_REF], providing the blind with some degree of situational awareness and guidance. However, when moving within an environment without good GPS reception (e.g., indoors, or in outdoor spaces with limited sky visibility), some other navigation sensor must be used. Because the world provides rich visual information, and because this information can be gathered with passive sensors (video cameras), we have chosen to investigate the use of machine vision techniques to assist with way-finding in complex GPS-denied environments.

We present a vision-based navigation system designed to assist both sighted and visually-impaired people in navigating through previously unexplored environments. We envision an operating scenario in which a user moves, beginning inria-00325434, version 1 -29 Sep 2008 Author manuscript, published in "Dans Workshop on Computer Vision Applications for the Visually Impaired (2008)" from some designated start point, through an environment with complex internal structure such as passages, intersections, and turns. At any point along the user's path, our system provides guidance of the following form:

retracing: guide from the starting point to any specified location; homing: guide from any specified (explored) location to the starting point; routing: guide from any specified (explored) location to any other.

An additional capability of our method is loop excision, that is, the ability to remove from an offered path any cycles that occurred during the user's initial exploration of the environment.

The user performing the exploration need not be the same as the user receiving the guidance, thus opening the possibility of sighted users generating a delayed guidance capability for sightless users.

Our method does not perform a metrical reconstruction of the environment. Instead, it automatically builds an annotated topological map of the environment by capturing orientation-and location-dependent scene appearance, and subsequently provides user-centered guidance within the captured region. The idea of using vision for non-metric, qualitative navigation is not new [START_REF] Chen | Qualitative vision-based mobile robot navigation[END_REF]. However, our method is novel in several respects. First, it is self-calibrating in that neither intrinsic nor precise extrinsic camera calibration are provided to or recovered by the system. Second, it relies on a new classifier-based approach for learning the correlation between the image motion field and the user's motion. Third, it does not attempt to produce metrically accurate guidance, but rather coarse guidance about progress and direction, much like one human would provide another. Finally, the method does not specify, or limit, the number of cameras used or their respective positions on the user's body. The method does not make any assumption about the appearance of the environment except that it contains visually distinctive and trackable features. We demonstrate the capability of the system on several real-world exploration and navigation sequences.

Section 3 presents our place graph representation. Section 4 gives a description of the user interface. Section 5 describes our algorithm for capturing a place graph. Section 6 shows how the place graph can be used to generate user-centered guidance. Section 7 presents applications specific to the visually impaired. Finally, section 8 presents validation and experimental results.

Related Work

A natural approach to vision-based navigation is to explicitly estimate metrical egomotion from the image motion field. Building on seminal work [START_REF] Horn | Motion fields are hardly ever ambiguous[END_REF], recent methods demonstrate robust real-time egomotion estimation [START_REF] Nister | Visual odometry[END_REF]. Some exploit the idea that egomotion estimation is more robust when using wide-field-of-view (FOV) sensors [START_REF] Gluckman | Ego-motion and omnidirectional cameras[END_REF][START_REF] Stratmann | Omnidirectional vision and inertial clues for robot navigation[END_REF]. Meanwhile, the problem of recovering both the camera motion and the structure of the environment, known as Simultaneous Localization and Mapping (SLAM) has attracted substantial attention [START_REF] Koenig | Unsupervised learning of probabilistic models for robot navigation[END_REF][START_REF] Davison | Active search for real-time vision[END_REF][START_REF] Wang | Coarse-to-fine vision-based localization by indexing scale-invariant features[END_REF][START_REF] Davison | MonoSLAM: Real-time single camera SLAM[END_REF][START_REF] Sim | A study of the Rao-Blackwellised particle filter for efficient and accurate vision-based SLAM[END_REF]. However, SLAM algorithms often come at the cost of complex algorithms and well-calibrated sensors. In addition, achieving efficient performance as the explored environment and excursion length grow remains a long-standing problem.

In order to cope with the complexity and scale of real environments, both topological [START_REF] Goedemé | Omnidirectional vision based topological navigation[END_REF][START_REF] Cummins | FAB-MAP: Probabilistic Localization and Mapping in the Space of Appearance[END_REF] and hierarchical [START_REF] Modayil | Using the topological skeleton for scalable global metrical map-building. Intelligent Robots and System[END_REF] approaches have been proposed. In comparison, our method is hybrid in a sense that it builds a topological representation of the environment, but also computes an estimate of the user's orientation and progress in a local frame.

The Place Graph Representation

Our method builds a topological representation of the environment on-line during exploration. We define a "place graph" as an undirected graph where nodes represent places of interest, and edges represent physical paths between successive nodes (Figure 1). Given a function f that measures the variability in visual appearance of the scene, our method involves finding local maxima in the gradient of f which correspond to places of highest variability in the scene appearance. Nodes in the map correspond to local maxima of ∇f .

Our algorithm takes as input a sequence of images, and computes feature points for each image, associating the features with edges and nodes in the place graph. Sec 5 describes the rotation guidance algorithm, which takes as input the feature sets for two images and computes the optimal user rotation that would bring them in alignment. The algorithm is based on a voting scheme which provides a variance associated with its output. The variance represents a measure of confidence in the output and by extension, a measure of similarity between the two input images. When two images are visually similar, the votes will aggregate around a consensus and the variance will be low. On the other hand, when two images are dissimilar, the votes will randomly spread across [0, 2π) and the variance will be high.

Let us define f (t 1 , t 2 ) as the variance between a frame acquired at time t 1 and one acquired at time t 2 . As the user moves about the environment, the algorithm computes f (t, t -∆t) at intervals (typically, ∆t =one second) and searches for maxima of the gradient of f . For every local maximum, a node is added to the place graph (we smooth the data to avoid detecting multiple maxima too close together in time or space). While the user navigates from a node to the next, the system records the set of image features at every frame.

User Interface

Our system includes four cameras, two pointing forward, two pointing backward, loosely mounted on the shoulder straps of a backpack (Figure 2). The overall field of view of the rig is 360 • degrees horizontally and 90 • vertically. The cameras are connected to a laptop, which captures visual data as the user explores the environment. Feature points are computed online.

The user interacts with the system using a Portable Device Assistant (PDA), headset and microphone. While the system builds a place graph automatically, f Fig. 1. We represent the environment as a place graph where nodes (red circles) are places of high variability in visual appearance of the scene and edges (black lines) are physical paths between nodes. The map is built automatically by the system during exploration. Features observed along edges (black dots) are stored in a database. Fig. 2. Our operating scenario involves a human exploring a complex internal space (notional view at left; user path shown as dotted line). The user wears a multi-camera processing rig (center). At any point in time, the system provides audio information to the user about his/her global location in the place graph as well as user-centered directions toward the target destination.

the user may also wish to add a node in the map whenever s/he feels s/he is passing through a notable place. The user does so by pressing a button on the PDA. The system subsequently records the user's voice for a few seconds. The audio file is repeated to the user any time the node is revisited.

At any time during navigation, the user may request that the system replay the sound track attached to the previous and next node in the map. In addition, the system provides user-centered navigation guidance at any point by uttering one of the following phrases: "Rear Center", "Rear left", "Rear right", "Front Center", "Front left", "Front right", "Side left", "Side right". The system also periodically utters a progress estimate, expressed as a percentage, as the user traverses each place graph edge.

Capturing the Place Graph

The topological map relies on the existence of a function f that captures the location-dependent variation in visual appearance of the environment. We now describe an algorithm that takes as input two images and returns the optimal rotation that would bring one in alignment with the other. We refer to this algorithm as the rotation guidance algorithm. First, it provides guidance to the user when reaching a place that has been visited before. Second, the variance in its output provides a measure of the visual similarity between the two input images.

The intuition underlying our method is that motion fields are hardly ever ambiguous [START_REF] Horn | Motion fields are hardly ever ambiguous[END_REF], and that the ambiguity is further decreased when using multiple (wide-FOV) cameras. Ideally, one could compute optical flow at pixel resolution and reconstruct both the 3D structure of the environment and the 3D motion of the camera. However, as our method demonstrates, these steps are not necessary for successful navigation. Instead, learning a coarse mapping between the user egomotion and the motion fields is sufficient. The algorithms works with an arbitrary number of cameras, for which no intrinsic or extrinsic calibration is required.

We reduce the mapping function to a hash table (or classifier), in which each row corresponds to a region (bin) in one camera image and each column to another region in another camera image. The value in each cell of the table represents the user egomotion required to bring a point from the source region to the target region.

Image frame

Classifier tables Image frame Fig. 3. Given a rotation speed ω, a feature tracked from camera u at time t to camera v at time t + dt generates an entry α = ω * dt in the matrix M uv . There are nc * (nc + 1)/2 matrices where nc is the number of cameras on the rig.

During a training phase, the user rotates in place at approximately constant speed while the system captures data. Given the number of frames in the sequence and the number of turns executed during the sequence (typically, two), the system can estimate the rotation angle in the user's body frame between any two frames. Given a set of feature point matches between the two frames, the hash table is populated as shown in figure 3.

In practice, each camera image is subdivided into a grid of k × k bins (typically, k = 10). The hash table is represented by a set of matrices M uv for each camera u and v (u < v). When multiple feature matches hit the same cell, the algorithm retains the average rotation value, in the following sense:

ᾱ = atan( n k=1 sin(α k ) n k=1 cos(α k ) ) (1)
which corresponds to minimizing the square sum of the distances between each angle α i represented as a point on the 2D unit circle and the point (1, 0). The algorithm proceeds as follows. First, it extracts a set of feature points F in the first image and a set G in the second image. Given a correspondence between a point f i ∈ F on camera u and a point f j ∈ G on camera v, it determines the rotation angle that would bring f i into alignment with f j . To do so, it computes r and s, the bins to which f i and f j belong respectively. Then, the desired rotation angle corresponds to M uv rs . This process is repeated for all feature matches and a voting algorithm returns an average rotation motion (Figure 4).

Method Resolution

Assuming a dense and homogeneous feature distribution and perfect feature matching, the accuracy of the algorithm does not depend on the grid resolution of the classifier. In order to prove this statement, we model the rig as four cameras, each covering a 90 • FOV (Figure 5). We further assume that the classifier has been trained with a single bin per image. A feature match within the same camera votes for a rotation of zero degree. A feature match between camera 0 and camera 1 votes for a rotation of 90 • , and so forth.

Let us assume that the rig rotates by 90 • (second tile on Figure 5). Each feature in camera 0 now appears in camera 1, and so forth. Hence, all feature matches vote for a rotation of 90 • , yielding a zero error in the rotation estimate. Let us assume that the rig rotates by 45 • (thid tile on Figure 5). Half of the features in camera 0 now appears in camera 1 (and votes for a rotation of 90 • ), while the other half stays in camera 0 (and votes for a rotation of zero). The average rotation estimate is therefore 45 • , which again yields a zero error.

Finally, let us assume that the camera rotates by an arbitrary angle α (fourth tile on Figure 5). Let us us put β the ratio of α over 90 • . A ratio of β feature matches will move to camera 1 (and vote for a rotation of 90 • ) while the remaining will vote for a rotation of zero degree. The rotation estimate is equal to β × π/2 + (1 -β) × 0 = α, which again yields a zerro error. This reasoning extends straightforwardly to any number of bins. Second tile: after a rotation of π/2. All features have moved from camera 0 to camera 1 (in yellow). Third tile: after a rotation of π/4. Half of the features remain on camera 0 (blue) while the other half is now visible in camera 1 (yellow). Fourth tile: after an arbitrary rotation of α. The ratio of features which stay in camera 0 and move to camera 1 yield a perfect estimate of the rotation angle. In practice, subdividing images into bins helps support the non-density and non-homogeneity of feature distribution.

In practice however, the assumption of perfect feature matching and dense feature distribution does not hold. Assuming that feature mismatches spread evenly across cameras, a higher number of bins in the grid does not improve the method accuracy. However, a higher number of bins helps combat the uneven and non-dense nature of feature distribution. Indeed, if γ is the average angle subtended by any two features, the accuracy of a k-bin classifier has a minimum bound of γ/k. In addition, in the case of a one-bin classifier, if a large cluster of features located on the edge of a camera image moves in one block to the neighboring camera following a small rotation of the rig, the whole cluster will vote for a rotation of π/2 which will incur an over-estimation of the rotation of the rig. A higher grid resolution decreases the importance of this phenomenon.

On the other hand, the method may be subject to aliasing effects if the number of bins is too high. Given the finite number of feature matches during training, a high-resolution grid may result in a sparse hash table from which queries return too few votes to obtain a significant result. As a conclusion, there exists an optimal grid size for the method driven on one hand by the sparsity of feature distribution in the image and on the other hand by the number of feature matches during training.

Generating Guidance from the Place Graph

To provide navigation assistance, the system tracks the motion of the user within the place graph graph. When the user is standing at a node, the system uses the rotation guidance algorithm to determine the relative orientation of the user at the node. This relative orientation is then converted into a user-centric navigation suggestion (Section 4). When the user is navigating along an edge, the system must determine the location of the user along that edge.

We formulate the problem as a general state estimation problem using a recursive estimator. The state is defined as a vector which length is the number of frames recorded during the first visit of the current edge. The value of each element in the vector is the probability of the user to be located at the corresponding frame. Let b t be the belief state at time t after incorporating actual observations {o 1 , •, o t }. We proceed in two steps:

Transition update b ′ t+1 (s t+1 ) = P (S t+1 |O 1 = o 1 , •, O t = o t ) = st P (S t+1 = s t+1 |S t = s t )b t (s t ) (2) Observation update, given a new observation o t+1 : b t+1 (s t+1 ) = P (S t+1 = s t+1 |O 1 = o 1 , •, O t+1 = o t+1 ) (3) = P (O t+1 = o t+1 |S t+1 = s t+1 )b ′ t+1 (s t+1 ) sj P (O t+1 = o t+1 |S t+1 = s j )b ′ t+1 (s j ) (4)
The belief state is initially set to [1, 0, . . . , 0] as the user leaves the node. The probability distribution P (S t+1 = s j |S t = s i ) used in the transition update is defined as a Normal distribution centered on s i . The probability P (O t+1 = o t+1 |S t+1 = s t+1 ) used in the observation update is defined as a quadratic function of the variance of the rotation guidance algorithm run between the features observed during the first visit of the edge (s t+1 ) and the current features o t+1 .

The current location of the user along the edge corresponds to the maximum element in the belief state vector. The relative orientation of the user is determined by running the rotation guidance algorithm against the corresponding set of features in the database.

Application Scenarios

There are several applications of our system for the visually impaired. First, the homing feature allows the user to navigate within an unknown environment with the ability to be guided back to the starting point at any time. This is particularly useful for people who explore their neighborhood for the first time.

As a second application, a non-impaired person can use our device to first visit a new environment, such as a public building. Robust to small changes in relative camera position, the rig can then be used to guide a visually impaired user who is navigating the space for the first time.

As demonstrated in section 5, the system calibrates itself in a few minutes and does not require the assistance of a non-impaired person. We hope to leverage future advancements in camera technology and portable computers to decrease the size and weight of the system.

Validation and Experimental Results

System Details

The system includes four IEEE-1394 PointGrey Firefly MV cameras. Each camera holds a wide-angle 2.2 mm Tamron lens. The rig's overall field of view is 360 • degrees horizontally and 90 • vertically. The cameras are connected to a dual-core, 1.7-GHz laptop through a firewire hub, enabling video recording at full resolution (4 × 752 × 480) at 8 Hz. The laptop performs real-time Scale Invariant Feature Transform (SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]) feature computation on half-size images at 4 Hz. The user interacts with the system using a handheld PDA connected via Bluetooth. A 12 V battery pack supports several hours of untethered operation.

Classifier Resolution

We evaluate the accuracy of our system by comparing the output of the rotation guidance algorithm on a set of video sequences for which ground-truth is known using an Inertial Measurement Unit (IMU). The sequences correspond to the user rotating in place in a different environment than the one used during training. Each sequence is approximately 200 frames long. The algorithm is run on every pair of frames, yielding to about 20, 000 data points per measurement.

Table 1 shows the standard deviation against ground-truth for various classifier resolutions. The accuracy of the method for a one-bin classifier is 13.2 • , which is comparable to the average subtended angle γ between any two features in the image. Indeed, given an average number of n f = 70 features per image and a horizontal field of view h f ov = 120 • , we estimate γ as γ = h f ov / √ n f = 14.3 • . As the number of bins increases, the standard deviation decreases slightly since the feature distribution in images is not dense and homogeneous. The two-bin classifier represents an outlier for which we have no clear explanation.

However, the standard deviation starts increasing beyond a threshold number of bins. Given n f,t the number of frames in the training sequence and n k,t the inria-00325434, version 1 -29 Sep 2008 average number of features per frame, we estimate the number of hits in the hash table as n hits = n f,t × (n f,t -1)/2 × n k,t . For n f,t = 200 and n k,t = 300, n hits = 6 millions. On the other hand, given n c the number of cameras and n bins the grid resolution, the number of cells in the hash table n cells is n cells = n 2 c × n 4 bins . For n c = 4 and n bins = 20, n cells = 2.5 millions. In conclusion, using a higher resolution than 20 bins is not reasonable, which shows in Figure 1.

Datasets

We tested our system on two datasets. The INDOOR dataset was collected during a 15 minute-long exploration across several building of a campus, for a total distance of approximately 1.5 kilometers. The OUTDOOR dataset was collected during a 15 minute-long walk across a dense urban environments, for a total distance of approximately one kilometer. Both datasets were collected in unprepared environments involving dynamic scenes and lighting changes. We first present the topological maps generated by the system for the two datasets. Table 2 presents summary data. Generating the Place Graph Figure 8 shows the ∇f function described in Section 3 for the INDOOR dataset. Maxima in the function correspond to nodes in the map. Figure 6 shows the corresponding nodes manually overlaid on a 2D map. Figure 7 shows the topological map for the OUTDOOR dataset. Figure 9 shows sample images at node locations. As expected, nodes correspond to places of high variability in the appearance of the scene. They often correspond to places of interest in human-made environments.

Guidance From the Place Graph We performed a retrace scenario for each dataset. In each case, the user started from the first node in the map and requested navigation assistance from the system to the last node in the map. For the INDOOR environment, the mission was run seven days after the first visit. For the OUTDOOR dataset, the mission was run at 4pm in the afternoon, while the first visit had happened at 10am in the morning. From a node to the next, the system automatically estimates the user's relative position on the map using the belief state estimator shown on Figure 10. Each time a new node is reached, the system plays back the audio file that was captured at the corresponding location during the first visit and gives rotation guidance to the user in a human-oriented fashion (Section 4). Note that the belief state estimator is reset every time a new node is encountered, which bounds the uncertainty on the user's location over time. Figure 11 shows the relative progress of the user along several consecutive edges on the INDOOR and OUTDOOR dataset. The average standard deviation from ground truth estimated assuming constant speed during the first visit is 3.3 frames for the INDOOR dataset (i.e approximately one second or 1.5 meters) and 7.7 frames for the OUTDOOR dataset (i.e approximately two seconds or 3 meters). The degradation in performance on the OUTDOOR dataset can be explained by the drastic change in lighting between the morning and the afternoon, making the feature matching more challenging.

Discussion

We described a vision-based navigation guidance system designed to assist a person in navigating through complex spaces. Our method is hybrid. It builds a topological map representation by analyzing the visual appearance of the environment and provides user-centric guidance in a human-oriented way within the map. Our method requires no calibration of the cameras, generalizes to any number of cameras and learns the correlation between user motion and evolution of image features. We have presented the performance of our system on both indoor and outdoor datasets under real conditions.

We are currently working on solving the global localization problem in a scalable way. Also, the current mapping strategy does not scale well since it requires storing all features observed during exploration. Methods based on a vocabulary tree [START_REF] Nister | Scalable recognition with a vocabulary tree[END_REF] for instance may help build a scalable mapping algorithm. Finally, we are working on a solution to detecting when the user leaves the map unexpectedly and helping them getting back on track.

Fig. 4 .

 4 Fig.[START_REF] Nister | Visual odometry[END_REF]. Assuming pure rotation of the rig by an unknown angle β, each feature match is assigned a rotation angle by the classifier. The mean of all the angles (in the sense of equation 1) gives an estimation of β.

Fig. 5 .

 5 Fig.5. Representing the rig as four cameras covering each 90 • of field of view. Cameras are numbered from 0 to 3. First tile: reference position. Features on camera 0 are shown in blue. Second tile: after a rotation of π/2. All features have moved from camera 0 to camera 1 (in yellow). Third tile: after a rotation of π/4. Half of the features remain on camera 0 (blue) while the other half is now visible in camera 1 (yellow). Fourth tile: after an arbitrary rotation of α. The ratio of features which stay in camera 0 and move to camera 1 yield a perfect estimate of the rotation angle. In practice, subdividing images into bins helps support the non-density and non-homogeneity of feature distribution.

Fig. 6 .

 6 Fig. 6. Topological map for the INDOOR dataset. The map is built online and automatically by analyzing the variance in scene appearance. Nodes are represented as red circles. The notional path of the user is shown in dotted line.

Fig. 7 .

 7 Fig. 7. Topological map for the OUTDOOR dataset. Nodes are represented as red circles. The notional path of the user is shown in dotted line.

Fig. 8 .

 8 Fig. 8. Gradient of the variance in the rotation guidance algorithm over time (INDOOR dataset). Maxima in the function (shown in dots) correspond to nodes in the map.

Fig. 9 .

 9 Fig. 9. Sample node images for the INDOOR dataset (top) and OUTDOOR dataset (bottom). Nodes correspond to places of high variability in the visual appearance of the scene.

Fig. 10 .

 10 Fig. 10. Propagation of the belief state as the user navigates across the map. The uncertainty in the position estimate is reset every time a node is encountered. Notional user motion on the top.

Fig. 11 .

 11 Fig. 11. Relative progress along several consecutive edges ((a): INDOOR dataset, (b): OUTDOOR dataset). Ground truth estimated using constant speed assumption shown in dotted line. The standard deviation is 3.3 frames for the INDOOR dataset (i.e approximately one second or 1.5 meters) and 7.7 frames for the OUTDOOR dataset (i.e approximately two seconds or 3 meters).

Table 1 .

 1 Standard deviation of the classifier (in degrees) and memory requirement with respect to the grid resolution.

	Grid resolution	1	2	4	8	12	16	20	30
	Standard deviation ( • ) 13.2 10.4 11.8 10.5	7.1	12.9 33.7	45.2
	Memory usage	4.0 K 8.0 K 76 K 1.2 M 5.6 M 18 M 43 M 217 M

Table 2 .

 2 Datasets information

	Name	Duration	Path length	Frame rate	# frames	# nodes
	INDOOR	12 min	1.5km	4 Hz	6, 000	120
	OUTDOOR	12 min	1km	4 Hz	2, 900	43

10 Acknowledgments We thank Ed Olson for his suggestion of the algorithm underlying Equation 1. Olivier Koch is supported by a University Research and Development award from Draper Laboratory.