Simulation-Based Evaluation of Ease of Wayfinding Using Digital Human and As-Is Environment Models

Abstract

As recommended by the international standards, ISO 21542, ease of wayfinding must be ensured by installing signage at all key decision points on walkways such as forks because signage greatly influences the way in which people unfamiliar with an environment navigate through it. Therefore, we aimed to develop a new system for evaluating the ease of wayfinding, which could detect spots that cause disorientation, i.e., “disorientation spots”, based on simulated three-dimensional (3D) interactions between wayfinding behaviors and signage location, visibility, legibility, noticeability, and continuity. First, an environment model reflecting detailed 3D geometry and textures of the environment, i.e., “as-is environment model”, is generated automatically using 3D laser-scanning and structure-from-motion (SfM). Then, a set of signage entities is created by the user. Thereafter, a 3D wayfinding simulation is performed in the as-is environment model using a digital human model (DHM), and disorientation spots are detected. The proposed system was tested in a virtual maze and a real two-story indoor environment. It was further validated through a comparison of the disorientation spots detected by the simulation with those of six young subjects. The comparison results revealed that the proposed system could detect disorientation spots, where the subjects lost their way, in the test environment.

1. Introduction

It is increasingly important in our rapidly aging society [1] to perform accessibility evaluations for enhancing the ease and safety of access to indoor and outdoor environments for all people, including the elderly and the disabled. Under international standards [2], “accessibility” is defined as “provision of buildings or parts of buildings for people, regardless of disability, age or gender, to be able to gain access to them, into them, to use them and exit from them.” As recommended in the ISO/IEC Guide 71 [3], accessibility must be assessed considering both the physical and cognitive abilities of individuals. From the physical viewpoint, for example, tripping risks in an environment [4] must be assessed to ensure the environment is safe to walk in, as conducted in our previous study [5]. By contrast, from the cognitive aspect, ease of wayfinding [6] must be assessed to enable people to gain access to destinations in unfamiliar environments.

Wayfinding is a basic cognitive response of people trying to find their way to destinations in an unfamiliar environment based on perceived information and their own background knowledge [7]. Visual signage influences the way in which people unfamiliar with an indoor environment navigate through it [8]. As shown in

Table 1. Signage type and navigation information.

Signage Type	Navigation Information
Positional signage	Next goal position to be reached to arrive at a destination (e.g., map)
Directional signage	Next walking direction to take to reach a destination (e.g., right or left)
Routing signage	Walking route to be taken to reach a destination (e.g., route drawn on map or indicated by textual information)
Identification signage	Name of current place

, visual signage can be classified into positional, directional, routing, and identification signage depending on the type of navigation information on the signage. As recommended in the guidelines [2], these four types of signage must be arranged appropriately at key decision points considering the relationship between the navigation information on signage and the path structure of the environment. In addition, as mentioned in the literature [9], ease of wayfinding must be evaluated considering not only signage continuity, visibility, and legibility but also signage noticeability.

Currently, ease of wayfinding is evaluated using four approaches: real field testing [10], virtual field testing [11,12], CAD model analysis [13], and wayfinding simulation [14,15,16,17,18,19,20]. In real field tests [10], a certain number of human subjects are asked to perform experimental wayfinding tasks in a real environment. By contrast, in virtual field tests [11,12], subjects are asked to perform wayfinding tasks in a virtual environment using virtual reality devices. In these real or virtual field tests [10,11,12], ease of wayfinding is evaluated by analyzing subjects’ responses to a questionnaire and their wayfinding results, e.g., walking route, gaze duration, and gaze direction. However, in these tests, prolonged wayfinding experiments involving a variety of wayfinding tasks must be conducted by various human subjects of different ages, genders, body dimensions, and visual capabilities. Thus, field tests are not necessarily efficient and low-cost approaches. In CAD model analysis [13], signage continuity is evaluated by analyzing the relationships among various pieces of user-specified navigation information indicated by signage. However, this approach cannot evaluate ease of wayfinding in terms of signage visibility, legibility, and noticeability because three-dimensional (3D) interactions between individuals and signage are not considered. Recently, a variety of wayfinding simulations has been proposed [14,15,16,17,18,19,20]. Such simulation-based approaches have made it possible to evaluate the ease of wayfinding by simulating the wayfinding of the pedestrian model. However, these simulations consider only a part of signage factors such as signage location, continuity, visibility, legibility, and noticeability. In addition, these simulations involve only simplified as-planned environment models that do not model the detailed environmental geometry, including obstacles on the walkway, and realistic environmental textures. For reliable evaluation, an environment model must be created to reflect the as-is situation of the environment because detailed 3D geometry and realistic textures affect the wayfinding of individuals [17,21].

Given the above background, the purpose of this study is to develop a new system for evaluating ease of wayfinding. The system makes it possible to detect spots that cause disorientation, i.e., “disorientation spots”, based on simulated 3D interactions among realistic wayfinding behaviors, as-is environment model, and realistic signage system. In this study, the as-is environment model represents an environment model that reflects a given environment as-is, i.e., detailed 3D geometry including obstacles and realistic textures. A schematic of the proposed system is shown in Figure 1. To achieve this goal, we draw on the results of our previous studies, in which algorithms of as-is environment modeling [22], walking simulation of a digital human model (DHM) in that environment model [23], and basic wayfinding simulation of the DHM [24] were developed.

As shown in Figure 1, first, the as-is environment model consisting of the walk surface points $W_S$, navigation graph $G_N$, and textured 3D environmental geometry $G_I$ is automatically generated from 3D laser-scanned point clouds [22] and a set of photographs of the environment [24]. Then, a set of signage entities is created by the user by manually assigning signage information. Then, a wayfinding simulation scenario is specified manually by the user. Thereafter, the DHM commences its wayfinding in accordance with the navigation information indicated by the arranged signage, while estimating signage visibility, noticeability, and legibility based on imitated visual perception. As a result, disorientation spots are detected.

The proposed system is demonstrated in a virtual maze and a real two-story indoor environment. The system is further validated by comparing the disorientation spots detected by the simulation with those obtained in a test involving six young subjects in the two-story indoor environment.

The rest of this paper is organized as follows. Section 2 introduces the related literature and clarifies the contributions of this study. Section 3 presents a brief introduction of the previously developed as-is environment modeling system [22,24]. In Section 4, an overview of signage entity creation is described. In Section 5, the algorithm for the simulation in which DHM performs wayfinding is introduced. Finally, in Section 6, the system is demonstrated and validated.

2. Related Work

This study is related primarily to wayfinding simulation research. A variety of simulation algorithms aiming to evaluate the ease of wayfinding have been studied.

Chen et al. [14] proposed a wayfinding simulation algorithm based on architectural information such as egress width, height, contrast intensity, and room illumination in a 3D as-planned environment model. Furthermore, Morrow et al. [15] proposed an environmental visibility evaluation system using 3D pedestrian model. In the study, environmental visibilities from pedestrian models were evaluated to assist facility managers in designing architectural layout and signage placement. However, these studies [14,15] are not applicable to the evaluation of ease of wayfinding based on signage system because the pedestrian models used in them were not modeled to incorporate the surrounding signage in the simulation.

Hajibabai et al. [16] proposed a wayfinding simulation using directional signage in an as-planned 2D environment model for emergency evacuation during a fire. The 2D pedestrian model used in the study could make decisions about its walking route based on perceived signage and fire propagation. However, in that study, signage visibility and legibility were estimated by oversimplified human visual perception, and signage noticeability was not considered. In addition, performing a precise 3D wayfinding simulation using a 3D as-is environment model using their framework is infeasible.

Recently, signage-based 3D wayfinding simulation has been advancing. Brunnhuber et al. [17] and Becker-Asano et al. [18] proposed schemes for wayfinding simulation using directional and identification signage in a 3D as-planned environment model. In these simulations, the next walking direction of the pedestrian models was determined autonomously based on the navigation information on the perceived signage. Signage perception was realized by estimating signage visibility and legibility based on the imitated visual perception of the pedestrian model. However, signage noticeability was not considered in these simulations, although it has a significant effect on the wayfinding of people in unfamiliar environments [9].

More recently, advanced approaches for estimating suitable signage locations have been proposed. Zhang et al. [19] proposed a system for planning the placement of directional signage for evaluation. In their system, a minimum number of signage and appropriate signage locations were determined automatically by simulating interactions between the pedestrian models and the signage system. In addition, Motamedi et al. [20] proposed a system for optimizing the arrangement of directional and identification signage in building information model (BIM)-enabled environments. Their system estimated optimal signage arrangement based on signage visibility and legibility for a 3D pedestrian model walking in a BIM-based environment model. However, as in cases of other previous simulations, signage noticeability was not considered in these studies [19,20]. In addition, the system [19] was validated with an oversimplified environment model imitating a large rectangular space having an egress, and the feasibility of its use in realistic and complex as-is environments was not validated. By contrast, in the system [20], the walking route of the pedestrian model was not changed based on the navigation information indicated by perceived signage, so evaluation based on signage continuity was basically infeasible.

Furthermore, these simulations [16,17,18,19,20] treated only one or two types of signage—Directional and/or identification. Thus, these simulations cannot be applied to actual signage systems including all signage types in Table 1.

Moreover, with the exception of the simulation proposed by Motamedi et al. [20], simplified as-planned environment models were used in the previous wayfinding simulations. Therefore, to realize a reliable evaluation of ease of wayfinding, simulation users and/or facility managers are urged to create detailed and realistic as-planned environment models, including small obstacles and environmental textures based on measurements of the environment.

Unlike the simulations developed in these previous studies [14,15,16,17,18,19,20], the proposed system can evaluate the ease of wayfinding by simulating 3D interactions among realistic wayfinding behaviors, as-is environment model, and realistic signage system. Specifically, the contributions of the present study are as follows:

• DHM can make a decision based on the surrounding signage perceived by its imitated visual perception in consideration of signage location, continuity, visibility, noticeability, and legibility.
• As-is environment model including detailed environmental geometry and realistic textures, can be generated automatically using 3D laser-scanning and SfM.
• Proposed system can simulate the wayfinding of the DHM by discriminating among four types of signage, namely, positional, directional, routing, and identification signage.
• Proposed system is validated through a comparison of disorientation spots between simulations and measurements obtained from young subjects.

3. Automatic 3D As-Is Environment Modeling

In the proposed system, first, an as-is environment model is generated automatically. As shown in Figure 2, the model comprises walk surface points $W_S$, a navigation graph $G_N$, and textured 3D environmental geometry $G_I$. $W_S$ represents a set of laser-scanned point clouds on walkable surfaces such as floors, slopes, and stair-treads. Specifically, $W_S$ is used to estimate the footprints of the DHM during the simulation. $G_N$ generated from $W_S$ represents the environmental pathways that the DHM would navigate through during the simulation. The graph $G_N=\langle V, E, c, \mathit{t}, E_S\rangle$ comprises a set of graph nodes $V$ and a set of edges $E$. Each node $v_k\in V$ represents free space in the environment, and has a position vector $\mathit{t}(v_k)$ and cylinder attribute $c(v_k)$, whose radius $r(v_k)$ and height $h_v$ represent the distance to the wall and walkable step height, respectively. Each edge $e_k$, representing the connectivity of free spaces, is generated between two adjacent nodes with a common region. $E_S=\{e_{sk}\}$ represents a set of stair edges connecting two graph nodes at the end of stairs. $W_S$ and $G_N$ can be generated automatically using our method [22]. By contrast, $G_I$ represents a 3D mesh model with high-quality textures, and it is used to estimate signage visibility and noticeability during simulation. $G_I$ can be created automatically using SfM with a set of photographs of the environment [24]. Detailed algorithms and demonstrations are given in our previous studies [22,23,24].

4. Creation of Signage Entity

In the proposed scheme, the signage system is modeled as a set of signage entities $S=\{S_i\}$. Each signage entity $S_i=[G_i,I_i]$ consists of a 3D textured mesh model $G_i$ of the signage and a set of signage information entities $I_i=\{I_{i,j}\}$ ($j\in [1,N_i]$), where $N_i$ represents the number of signage information items included in $S_i$. When modeling the existing signage, $G_i$ is constructed using SfM; otherwise, $G_i$ is created using 3D CAD software. $I_{i,j}$ is created by manually assigning the geometric, navigation, and legibility properties in

Table 2. Signage information entity.

Property	Attribute	Assignment Method
Geometric property	Description region $R_g=[{\mathit{p}}_{top}, {\mathit{p}}_{bottom}]$	Assigned by user by picking two diagonal points
	Center position ${\mathit{p}}_g$	Estimated from $R_g$
	Unit normal vector ${\mathit{n}}_g$
	Width $w_g$
	Transformation matrix ${\mathrm{T}}_{GI}$	Estimated from ${\mathit{p}}_g$ and ${\mathit{n}}_g$
Navigation property	Type of signage $T_n\in \{‘positional’, ‘directional’, ‘routing’, ‘identification’\}$	Assigned by user based on the signage design
	Name of indicated place $D_n$
	Navigation information $N_I$
Legibility property	Maximum viewing distance $d_l$	Measured from human subjects
	Center point of 3D VCA ${\mathit{p}}_l$	Estimated from $d_l$
	Radius of 3D VCA $r_l$

. The details are given below.

4.1. Geometric Property

The geometric property includes the description region $R_g$, center position ${\mathit{p}}_g$, unit normal vector ${\mathit{n}}_g$, width $w_g$, and transformation matrix ${\mathrm{T}}_{GI}$. As shown in Figure 3a, $R_g=[{\mathit{p}}_{top}, {\mathit{p}}_{bottom}]$ consists of two diagonal points of the rectangular description region on $G_i$, in which the signage information is written. ${\mathit{p}}_g$, ${\mathit{n}}_g$, and $w_g$ are estimated from $R_g$. ${\mathrm{T}}_{GI}$ represents a transformation matrix from the local coordinate system $X_I$ of $I_{i,j}$ to the coordinate system $X_G$ of $G_i$, where $X_I$ is defined to satisfy three conditions: (1) the origin of $X_I$ is located on ${\mathit{p}}_g$, (2) y-axis of $X_I$ is aligned with ${\mathit{n}}_g$, and (3) z-axis of $X_I$ is aligned with the z-axis of $X_G$. Under this definition, ${\mathrm{T}}_{GI}$ is calculated automatically from ${\mathit{p}}_g$ and ${\mathit{n}}_g$.

4.2. Navigation Property

The navigation property includes the type of signage $T_n$, name of indicated place $D_n$, and navigation information $N_I$. As listed and shown in

Table 3. Assignment of navigation information depending on signage type.

Signage Type	Navigation Information ${\mathit{N}}_{\mathit{I}}$ to Achieve a Destination	Referenced Coordinate System
Positional signage	Next goal position ${\mathit{p}}_n$	$X_W$ of $G_I$
Directional signage	Next walking direction ${\mathit{d}}_n$	$X_I$ of $I_{i,j}$
Routing signage	A set of passing points $P_N=\{{\mathit{p}}_k\}$	$X_W$ of $G_I$
Identification signage	Name of current place $C_n$	None

and Figure 3b, respectively, $N_I$ is assigned by the user in accordance with $T_n$. The user must specify a next goal position ${\mathit{p}}_n$, next walking direction ${\mathit{d}}_n$, and a set of passing points $P_N$ for positional, directional, and routing signage, respectively. ${\mathit{p}}_n$ and $P_N$ are specified w.r.t. the coordinate system $X_W$ of the textured environmental geometry $G_I$. By contrast, ${\mathit{d}}_n$ is specified w.r.t. $X_I$ of $I_{i,j}$.

4.3. Legibility Property

The legibility property includes the center point ${\mathit{p}}_l$ w.r.t. $X_I$ of $I_{i,j}$ and radius $r_l$ of the 3D visibility catchment area (VCA). As shown in Figure 3c, the 3D VCA of signage represents a sphere in which people can recognize the information written in the signage. The VCA was defined originally as a 2D circle by Fillipidis et al. [25] and Xie et al. [26]. In this study, the 3D VCA is calculated such that the great circle of the sphere on the horizontal plane corresponds to the 2D VCA circle proposed by Xie et al. [26]. Specifically, ${\mathit{p}}_l$ and $r_l$ are calculated using the following equation:

$$\begin{array}{c}{r}_l=\frac{w_g}{2 \sin {\phi }_l}\\ {\mathit{p}}_l={\mathit{p}}_g+{\mathit{n}}_g(\frac{w_g}{2 \tan {\phi }_l})\\ {\phi }_l={\tan }^{-1}(\frac{w_g}{2 d_l}),\end{array}$$

(1)

where $d_l$ represents the maximum viewing distance between the signage and the subject standing at a place, in which the subject can recognize the information on the signage. By measuring $d_l$ from the subjects, the legible space of the signage is calculated as the 3D VCA using Equation (1).

5. System for Evaluation of Ease of Wayfinding

As shown in Figure 1, the wayfinding simulation using the DHM is performed in accordance with the user-specified wayfinding scenario, including DHM properties $H=[M, {\theta }_H,{\theta }_V,n_t]$, start position ${\mathit{p}}_s$, initial walking direction ${\mathit{d}}_I$, name of destination $D$, and signage locations and orientations $T_s=\{{\mathrm{T}}_i\}$, where $M$, ${\theta }_H$, ${\theta }_V$, $n_t$, and ${\mathrm{T}}_i$ represent motion-capture (MoCap) data for flat walking obtained from the gait database [27], horizontal and vertical angles of view frustum, threshold value of signage noticeability, and transformation matrix from $X_G$ to $X_W$, respectively.

Before the simulation, the locations and the orientations of each signage entity $S_i\in S$ are determined by assigning ${\mathrm{T}}_i\in T_s$. Then, a DHM having the same body dimensions as the subject of $M$ is generated. As shown in Figure 4, the DHM has 41 degrees of freedom and a link mechanism corresponding to that of $M$. The imitated eye position ${\mathit{p}}_{eye}$ of the DHM is estimated as the midpoint between the top of the head and the neck.

Finally, the wayfinding simulation is performed by repeating the algorithms described in the following subsections.

5.1. Signage Perception Based on Imitated Visual Perception

In the proposed system, signage visibility, noticeability, and legibility are estimated to determine whether a signage is found and its information is recognized by the DHM. The details are described in the following subsections.

5.1.1. Signage Visibility Estimation

Signage visibility represents whether a signage is included in the view frustum of the DHM defined by ${\theta }_H$ and ${\theta }_V$. As shown in Figure 5, it is estimated simply by scanning the eyesight of the DHM. First, the eyesight of the DHM is obtained using OpenGL by rendering an image from the camera model located at the DHM eye position ${\mathit{p}}_{eye}$. At the same time, as shown in the figure, the textured 3D environmental geometry $G_I$ and the textured 3D mesh model $G_i$ of each signage $S_i\in S$ are rendered with a single color instead of their original textures. Finally, if the color of $G_i$ appears in the rendered image, $S_i$ is considered “visible” signage and inserted into a set of visible signage entities $S_{vis}=\{S_k\}$.

5.1.2. Signage Noticeability Estimation

As people overlook objects in their eyesight, it is not always true that the DHM can find a signage $S_i$ when $S_i$ is visible $S_i\in S_{vis}$. Therefore, signage noticeability representing whether the DHM can notice $S_i\in S_{vis}$ must be estimated.

In the proposed system, signage noticeability is estimated using the saliency estimation algorithm proposed by Itti et al. [28] based on the visual search mechanism of real humans [29]. In this algorithm, a Gaussian pyramid is first generated from an image rendered by the camera model at ${\mathit{p}}_{eye}$. Then, feature maps representing contrasts of intensity, color differences, and orientations are obtained from each image. By integrating and normalizing the feature maps, a saliency map $M_s=\{m(x,y)\}$ is generated, where $m(x,y)\in [0,1]$ represents the degree of saliency at a pixel $(x,y)$. In the map, $m(x,y)$ increases at the pixel, in which contrasts of intensity, color differences, and orientations are higher than those of other pixels. Finally, as shown in Figure 6, the propose system estimates the noticeability $n_i$ of visible signage $S_i\in S_{vis}$ using the following equation:

$$n_i=\underset{(x,y)\in P_i}{\max }m(x,y),$$

(2)

where $m(x,y)$ and $P_i$ represent the degree of saliency at pixel $(x,y)$ in $M_S$ and a set of pixels, in which the signage geometry $G_i$ is rendered. If $n_i$ is greater than the noticeability threshold $n_t$ of the user-specified wayfinding scenario, $S_i$ is considered “found” signage, and inserted into a set of found signage entities $S_{found}=\{S_k\}$ ($S_{found}\subseteq S_{vis}$).

5.1.3. Signage Legibility Estimation

Signage legibility represents whether the DHM can recognize signage information of found signage $S_i\in S_{found}$, i.e., whether the DHM can read the textual or graphical information written on the signage. It is estimated using the 3D VCA of signage information $I_{i,j}$ of $S_i$. If ${\mathit{p}}_{eye}$ is included in the 3D VCA of $I_{i,j}$, $I_{i,j}$ is considered “recognized” signage information. In the proposed system, it is assumed that the DHM can correctly interpret $I_{i,j}$ only when $S_i$ and $I_{i,j}$ are found (i.e., $S_i\in S_{found}$) and recognized, respectively. Note that the signage noticeability, $n_i$, does not influence the signage legibility estimation.

5.2. Wayfinding Decision-Making Based on Signage Perception

Based on the estimated signage visibility, noticeability, and legibility, the wayfinding state of the DHM is changed dynamically in accordance with the state transition chart shown in Figure 7a. As shown in the figure, when the simulation is performed, the DHM is set to start walking in the direction ${\mathit{d}}_I$ (state SW1 in Figure 7a). Then, as shown in Figure 7b, when a signage $S_i$ is found by the DHM, i.e., $S_i$ is inserted to $S_{found}$, the DHM is set to walk toward the center position ${\mathit{p}}_g$ of $I_{i, j}$ of $S_i$ (state SW2) to read the information on $S_i$. Thereafter, the other signage $S_j$ does not influence the state transition until the state is changed to the look-around state (SW3) even if $S_j$ is found by the DHM. When $I_{i, j}$ of $S_i$ becomes legible, the name of indicated place $D_n$ of $I_{i, j}$ is compared with the name of destination $D$ of the wayfinding scenario. If $D_n\ne D$, the state is changed to SW3 to find other signage related to $D$; else, the state is changed in accordance with the type of recognized signage information $T_n$. If $T_n$ represents positional, directional, or routing signage, the state is changed to the motion planning state (SW4). By contrast, if $T_n$ represents an identification signage, the state is changed to the success state (SW5). In this state, the simulation is deemed complete because this state is the final state.

During the wayfinding simulation, the DHM basically repeats the states SW2, SW4, SW6, and SW3. As shown in Figure 7c, when the DHM recognizes $I_{i, j}$, it is set to walk toward the temporal destination of the DHM, i.e., subgoal position ${\mathit{p}}_{sub}$ (SW4 and SW6). Then, as shown in Figure 7d, when the DHM arrives at ${\mathit{p}}_{sub}$, it is asked to observe the surrounding environment (i.e., look-around) by rotating the neck joint horizontally within its range of motion (SW3). When the DHM finds new signage in this state, the state changes back to SW2. By contrast, when the DHM cannot find any signage, the current DHM position is treated as a “disorientation spot” (SW7). The state SW7 is considered the failed state. Note that the state can be changed to SW8 from SW7 only when $T_n$ represents a directional signage, as described in Section 5.3.1.

5.3. Signage-Based Motion Planning

5.3.1. Updating Subgoal Position of DHM

In the signage-based motion planning state (SW4), first, the subgoal position ${\mathit{p}}_{sub}$ is determined automatically depending on the type of recognized signage information $T_n$ and its navigation information $N_I$.

When $T_n=‘positional’$, ${\mathit{p}}_{sub}$ is determined as the next goal position ${\mathit{p}}_n$ of $N_I$ to make the DHM walk toward a location indicated by the recognized signage information $I_{i,j}$.

When $T_n=‘directional’$, as shown in Figure 8, a queue of fork points $F=\{{\mathit{p}}_m\}$ is extracted by the following steps.

(1)

A graph node $v_c(v_c\in V)$ just under the pelvis position ${\mathit{p}}_p$ of the DHM is extracted from the navigation graph $G_N$. Then, $v_c$ is inserted into a set of graph nodes $V_P^{\prime }$, where $V_P^{\prime }$ represents graph nodes on a feasible walking path when the DHM walks in accordance with the next walking direction ${\mathit{d}}_n$ indicated by $I_{i, j}$.

(2)

$v_c$ and ${\mathit{d}}_n$ of $I_{i, j}$ are assigned to the variables $v_t$ and ${\mathit{d}}_t$, respectively.

(3)

A graph node $v_p$ located in the direction of ${\mathit{d}}_t$ is extracted using the following equation:

$$\begin{array}{c}p=\arg \underset{k\in N_t}{\max }{\mathit{d}}_k·{\mathit{d}}_t\\ {\mathit{d}}_k=\frac{\mathit{t}(v_k)-\mathit{t}(v_t)}{\Vert \mathit{t}(v_k)-\mathit{t}(v_t)\Vert },\end{array}$$

(3)

where $N_t$ represents a set of indices of graph node $v_k$ ($v_k\notin V_P^{\prime }$) connected to $v_t$ by a graph edge. Using this equation, $v_p$ is determined as a graph node with the minimum angle difference between ${\mathit{d}}_t$ and a graph edge connecting $v_k$ and $v_t$.

(4)

If $N_t\ne \varnothing$, $v_p$ is inserted into $V_P^{\prime },$ and ${\mathit{d}}_k$ and $v_p$ are assigned to $v_t$ and ${\mathit{d}}_t$, respectively.

(5)

If $\left|N_t\right|\ge 2\vee N_t=\varnothing$, $\mathit{t}(v_p)$ is pushed into $F$ because $\mathit{t}(v_p)$ is considered a center position at the fork way or at the terminal of the walkway.

(6)

Steps (3)–(5) are repeated, until $N_t=\varnothing$, i.e., until a graph node representing the terminal of the walkway is found.

When the wayfinding state is changed to SW4 or SW8 in Figure 7a, a first fork point is taken from $F$ and assigned to ${\mathit{p}}_{sub}$. This algorithm enables the proposed system to detect multiple disorientation spots, i.e., fork points with no visible and noticeable signage after perceiving directional signage.

When $T_n=‘routing’$, ${\mathit{p}}_{sub}$ is determined as the last elements of a set of passing points $P_N$ of $N_I$ indicated by $I_{i,j}$. Then, the walking path $V_P$ of the DHM is estimated such that it passes the graph nodes at ${\mathit{p}}_k\in P_N$ in Section 5.3.2.

5.3.2. Walking Path Selection and Walking Trajectory Generation

As shown in Figure 9, after determining the subgoal position ${\mathit{p}}_{sub}$, the walking path $V_P=\{v_i\}$ ($v_i\in V$) of the DHM is determined automatically by the following function:

$$V_P=\mathrm{Path}({\mathit{p}}_a, {\mathit{p}}_b),$$

(4)

where $\mathrm{Path}({\mathit{p}}_a, {\mathit{p}}_b)$ represents a function to select a set of graph nodes $V_P$ between two nodes located at ${\mathit{p}}_a$ and ${\mathit{p}}_b$ using the Dijkstra method from $G_N$.

When the wayfinding state is changed to SW2 with the visible signage $S_i\in S_{vis}$, $\mathit{t}(v_c)$ and ${\mathit{p}}_g$ are assigned to ${\mathit{p}}_a$ and ${\mathit{p}}_b$, where $v_c$ and ${\mathit{p}}_g$ represent a graph node just under the DHM pelvis position ${\mathit{p}}_p$ and the center position ${\mathit{p}}_g$ of $I_{i, j}$ of $S_i$, respectively. By contrast, when the state is changed to SW4, ${\mathit{p}}_a$ and ${\mathit{p}}_b$ are determined depending on the type of recognized signage information $T_n$. When $T_n=‘positional’$ or $T_n=‘directional’$, $\mathit{t}(v_c)$ and ${\mathit{p}}_{sub}$ are assigned to ${\mathit{p}}_a$ and ${\mathit{p}}_b$, respectively. By contrast, when $T_n=‘routing’$, $V_P$ is determined as $V_P={\cup }_{k=0}^{k<\left|P_N\right|}\mathrm{Path}({\mathit{p}}_k, {\mathit{p}}_{k+1})$, where ${\mathit{p}}_k\in P_N$ is a passing point representing a walking route indicated by $N_I$ of $I_{i, j}$.

After determining $V_P$, the walking trajectory $V_T=\langle {\mathit{p}}_i\rangle$ is generated automatically by our previously developed optimization algorithm [23], where $V_T$ represents a sequence of sparsely discretized target pelvis positions of the DHM. This optimization algorithm is designed to make $V_T$ more natural and smooth, while avoiding contact with walls. The details are described in [23].

5.4. MoCap-Based Adaptive Walking Motion Generation

Finally, the walking motion of the DHM is generated as it follows $V_T$ using our MoCap-based adaptive walking motion generation algorithm [23]. In the algorithm, realistic articulated walking movements of the DHM are generated based on MoCap data $M$ for flat walking. The details and demonstrations are introduced in [23].

6. Results and Validations

The proposed system was developed using Visual Studio 2010 Professional edition with C++. The system was applied to a virtual maze and a real two-story indoor environment. In addition, it was validated by comparing the disorientation spots between the simulation and measurements obtained from young subjects. Videos of as-is environment modeling and wayfinding simulation results, i.e., Figure 10, Figure 11, Figure 12 and Figure 13, are available in the supplementary video file.

6.1. Evaluation of Ease of Wayfinding in Virtual Maze

The proposed system was first applied to a virtual maze with a set of signage entities $S=\{S_1,S_2,S_3,S_4,S_5\}$, to test its basic performance. Figure 10 shows the constructed environment model of the virtual maze. In the figure, textured environmental geometry $G_I$ was constructed manually using CAD software [30], and the set of walk surface points $W_S$ and navigation graph $G_N$ were constructed from a set of vertices of $G_I$. Note that the proposed system could perform not only in the as-is environment model but in the given 3D model of the environment, e.g., CAD data of the environment, by converting the model to dense point clouds.

Table 4. User-specified wayfinding scenario.

Parameters	Specified Values
MoCap data for flat walking $M$ of $H$	MoCap data of a young male subject (Age: 22 years, height: 1.73 m)
Horizontal angle of view frustum ${\theta }_H$ of $H$	100 deg 1
Vertical angle of view frustum ${\theta }_V$ of $H$	60 deg 1
Noticeability threshold $n_t\in [0, 1]$ of $H$	0.3 2
Start position ${\mathit{p}}_s$	Shown in Figure 10d
Initial walking direction ${\mathit{d}}_I$
Name of destination $D$	“Goal“
Signage locations and orientations $T_s$	Shown in Figure 10d

¹ ${\theta }_H$ and ${\theta }_V$ were specified based on the handbook [31]. ² $n_t$ was specified as a small value for validation.

and

Table 5. User-assigned parameters of signage information.

Parameters	Sign ${\mathit{S}}_1$	Sign ${\mathit{S}}_2$	Sign ${\mathit{S}}_3$	Sign ${\mathit{S}}_4$	Sign ${\mathit{S}}_5$
Type of signage $T_n$	‘Positional’	‘Directional’	‘Directional’	‘Routing’	‘Identification’
Name of indicated place $D_n$	“Goal”
Navigation information $N_I$	Shown in Figure 10d				“Goal”
Maximum viewing distance $d_l$	4.0 m 1			5.0 m 1	1.74 m 1

¹ $d_l$ was specified as a tentative value without human measurements.

show the wayfinding scenario and the user-assigned parameters of each signage information $I_{i,j}$, respectively. As shown in Table 5, all four types of signage were used.

Figure 11 shows the evaluation results of ease of wayfinding. As shown in Figure 11a, when the simulation was performed, the DHM found and recognized $S_1$ and $I_{1, 1}$, respectively. In consequence, the DHM was set to walk toward the next goal positon ${\mathit{p}}_n$ indicated by $I_{1, 1}$. Then, when the DHM arrived at ${\mathit{p}}_n$, $S_2$ and $I_{2, 1}$ were found and recognized by the DHM (Figure 11b), respectively. A feasible walking path $V_P^{\prime }$ and a set of fork points $F$ of $I_{2, 1}$ were then extracted. Then, the DHM was set to walk toward the first fork point ${\mathit{p}}_1\in F$ of $I_{2, 1}$. After that, the DHM found and recognized $S_3$ and $I_{3, 1}$ at ${\mathit{p}}_1\in F$, respectively. Then, as shown in Figure 11c, $V_P^{\prime }$ and $F$ of $I_{3, 1}$ were extracted. At the same time, the DHM was set to walk toward ${\mathit{p}}_1\in F$ of $I_{3, 1}$. However, as shown in Figure 11d, the DHM could not find any new signage when it arrived at ${\mathit{p}}_1\in F$ of $I_{3, 1}$. Therefore, this spot was detected as a disorientation spot. As recommended by international standards [2], a facility manager must provide signage at all key decision points such as forks. Therefore, from this standpoint, the detection of this disorientation spot can be considered reasonable.

Thereafter, as shown in Figure 11e, the DHM was set to walk toward ${\mathit{p}}_2\in F$ indicated by $I_{3, 1}$ to evaluate the ease of wayfinding after passing the detected disorientation spot. In consequence, the DHM found and recognized $S_4$ and $I_{4, 1}$ at ${\mathit{p}}_2\in F$ of $I_{3, 1}$, respectively. Then, the DHM was set to walk toward ${\mathit{p}}_4\in P_N$ of $I_{4, 1}$ following $V_P$ generated on passing points ${\mathit{p}}_i\in P_N$ of $I_{4, 1}$. Finally, as shown in Figure 11f, the DHM found and recognized $S_5$ and $I_{5, 1}$, respectively, where $S_5$ was an identification signage pertaining to the destination $D$. In consequence, the wayfinding simulation was completed.

Based on the above results, from the standpoints of system performance, the following conclusions were obtained.

• The proposed system could detect disorientation spots resulting from the lack of signage or poor location of signage in the environment model.
• The proposed system could simulate the wayfinding of the DHM by discriminating among four types of signage, namely, positional, directional, routing, and identification.

6.2. Evaluation Results of Ease of Wayfinding in Real Two-Story Indoor Environment

The proposed system was further applied to a real two-story indoor environment with a set of signage entities $S=\{S_1, S_2, S_3, S_4\}$. Figure 12 shows the constructed as-is environment model. In Figure 12, the laser-scanned point clouds were acquired from the environment by a terrestrial laser scanner [32]. The textured environmental geometry $G_I$ was constructed from 21,143 photos of the environment using commercial SfM software, ContextCapture [33], where the photos were extracted from the video data captured using a digital single-lens reflex camera [34]. As shown in Figure 12c, the model contains a few distorted regions, which can be attributed to the performance limitations of the SfM software. However, most of the model could be generated successfully.

In the simulation, the DHM properties $H$ of the wayfinding scenario was identical to that in Table 4. The starting position ${\mathit{p}}_s$, initial walking direction ${\mathit{d}}_I$, and signage locations and orientations $T_S$ are shown in Figure 12d,e. The maximum viewing distance $d_l$ of each signage was specified as $d_l$ = 4.46 m for each signage information $I_{i,j}$, as determined by measurement of $d_l$ of $S_1$ using six subjects ranging in age from 22 to 26 years. A positional signage $S_1$, two types of directional signage $S_2$ and $S_3$, and an identification signage $S_4$ were arranged in the environment to simulate the situation in which people tried to find a conference room using only the signage in the unfamiliar indoor environment.

Figure 13 shows the evaluation results of ease of wayfinding. As shown in Figure 13a, when the simulation was performed, $S_1$ and $I_{1, 1}$ were found and recognized by the DHM, respectively. Since the next goal position ${\mathit{p}}_n$ indicated by $I_{1, 1}$ was specified on the end of the caracole on the second floor, the DHM was set to ascend the caracole. When the DHM arrived at ${\mathit{p}}_n$ of $I_{1, 1}$, the DHM was asked to observe the surrounding environment to find new signage. However, as shown in Figure 13b, the DHM could not find $S_2$ although $S_2$ was visible. This was because the estimated signage noticeability $n_2=0.27$ of $S_2$ at the spot was less than the user-specified threshold, $n_t=0.3$. Thus, this spot was detected as a disorientation spot because $S_2$ was overlooked.

Following the above results, in Figure 13c, the signage design of $S_2$, i.e., texture on $G_i$, was improved to enhance its noticeability. As a result, the ease of wayfinding was improved to enable the DHM to find $S_2$ at the detected disorientation spot. This improvement was caused by the fact that $n_2$ of $S_2$ from the DHM standing at the disorientation spot detected previously increased to an adequately large value, $n_2=0.68$.

After the DHM recognized $I_{2, 1}$, the DHM was set to walk toward the first fork point ${\mathit{p}}_1$ indicated by $I_{2, 1}$. However, as shown in Figure 13c, when the DHM arrived at ${\mathit{p}}_1$ of $I_{2, 1}$, the wayfinding state had fallen into SW7, i.e., gotten lost, since the DHM could not find any new signage at ${\mathit{p}}_1$. This was because any signage could not be seen by the DHM at ${\mathit{p}}_1$. Therefore, this spot was also detected as a disorientation spot owing to the lack of signage.

By contrast, in Figure 13d, a new positional signage $S_5$ was arranged around the detected disorientation spot. As a result, as shown in the figure, the wayfinding simulation of the DHM was completed successfully.

As described above, the proposed system enabled the user to validate the ease of wayfinding in the environment interactively by considering the wayfinding of the DHM, as-is environment model, and arranged signage system. From the standpoint of system performance, the following conclusions were obtained.

• The proposed system could detect disorientation spots resulting from the lack of signage and overlooking signage.
• The proposed system could simulate the wayfinding of the DHM even in the realistic and complex as-is environment model.
• The proposed system could quickly re-evaluate rearranged signage based on the simulation.

6.3. Efficiency of Environment Modeling and Simulation

Table 6. Time required for environment modeling and simulation. (CPU: Intel(R) Core(TM) i7-6850K 3.60 GHz, RAM: 64 GB, GPU: GeForce GTX 1080).

Process	Time Required in Case of Virtual Maze	Time Required in Case of Two-Story Indoor Environment
Automatic construction of $W_S$ and $G_N$ from laser-scanned point clouds	2.5 s (#points: 963,691) 1	50.0 s (#points: 5,980,647) 1
Automatic construction of $G_I$ using SfM software [33]		Approximately 1 week (#photos: 21,143) (resolution: 1920 × 1080)
Signage visibility, legibility, and noticeability estimation	Less than 0.17 s
Signage-based motion planning	Less than 0.02 s
One-step walking motion generation with 100 frames interpolation 2	0.15 s	2.5 s

¹ Number of downsampled points used for environment modeling. ² Elapsed time of signage visibility, legibility, and noticeability evaluation was not included.

shows the elapsed time of the as-is environment modeling and simulation. As shown in the table, the times for 3D environment modeling from laser-scanned point clouds were less than one minute in both environments. By contrast, owing to the performance limitation of the SfM software [33], construction of the textured environmental geometry $G_I$ required approximately one week.

Furthermore, the time required for signage visibility, legibility, and noticeability estimation was less than 0.17 s. In addition, the times required for one-step walking motion generation were 0.15 s and 2.5 s in the virtual maze and the two-story indoor environment, respectively. Therefore, it was confirmed that the proposed system could simulate the DHM wayfinding efficiently. Note that the time required for walking motion generation in the two-story indoor environment was longer owing to the high computational load of rendering the environment model.

6.4. Experimental Validation of System for Evaluating Ease of Wayfinding

6.4.1. Overview of Wayfinding Experiment

The simulation results on ease of wayfinding presented in Section 6.2 were validated by the wayfinding experiment using six young subjects. In the validation, two signage systems imitating $S=\{S_1, S_2, S_3, S_4\}$ and $S\cup S_5$ were arranged in the real environment, where $S$ and $S_5$ represent the set of signage entities used in the simulation in Figure 13a,b and the added signage in the simulation in Figure 13d, respectively. In the wayfinding experiment, first, the name of destination was revealed to the subjects at the start position ${\mathit{p}}_s$. Then, the subjects were asked to find their way to the destination using the arranged signage system. During this process, wayfinding events such as finding signage and recognizing signage information were recorded by the thinking-aloud method [36], where the subjects were asked to walk while continuously thinking out loud. Verbal information from the subjects was recorded by handheld voice recorders. At the same time, videos of the walking trajectories of the subjects were captured by the observer. Finally, when the subjects arrived at the destination, the experiment was deemed complete. Note that all subjects have regularly used the environment, but the locations of arranged signage and the destination were not revealed to them. In addition, in the simulation results in Section 6.2, the maximum viewing distance $d_l$ was specified by measuring $d_l$ from those six subjects.

In the experiments, first, the wayfinding behaviors of three young subjects (Y1–Y3) were measured using the signage system imitating $S$. After that, the behaviors of the other three young subjects (Y4–Y6) were measured using the signage system imitating $S\cup S_5$.

6.4.2. Comparison of Wayfinding Results between DHM and Subjects

Figure 14 shows the comparison of wayfinding results between the DHM and the subjects. As shown in Figure 14a, a disorientation spot was found during the experiment by three subjects (Y1–Y3), which corresponded to the disorientation spot detected by the simulation. Thus, it was confirmed that the proposed ease of wayfinding simulation could detect disorientation spot, where the subjects actually lost their way owing to the lack of signage.

By contrast, as shown in Figure 14b, two subjects, Y4 and Y5, arrived at the destination when the signage system imitating $S\cup S_5$ was arranged. However, a disorientation spot was found during the experiment by subject Y6. This was explained by the fact that the subject Y6 overlooked the signage imitating $S_2$. As shown in Figure 14a, this disorientation spot was also detected in the simulation because the DHM could not find $S_2$ owing to the low noticeability of $S_2$. Therefore, it was further confirmed that the proposed system could detect disorientation spot, where subjects actually lost their way owing to overlooking signage.

7. Conclusions

In this study, we developed a simulation-based system for evaluating ease of wayfinding using a DHM in an as-is environment model. The proposed system was demonstrated using a virtual maze and a real two-story indoor environment. The following conclusions were drawn from our results:

• Our system makes it possible to evaluate the ease of wayfinding by simulating the 3D interactions among the realistic wayfinding behaviors of a DHM, as-is environment model, and realistic signage system.
• Under the user-specified wayfinding scenario, the system simulates the wayfinding of the DHM by evaluating signage locations, continuity, visibility, legibility, and noticeability based on the imitated visual perception of the DHM.
• Realistic signage system, including four types of signage, namely, positional, directional, routing, and identification, can be discriminated in the wayfinding simulation.
• Disorientation spots owing to the lack of signage and overlooking signage can be identified only by conducting the simulation.
• Rearranged signage plans can be re-evaluated quickly by carrying out the simulation alone.

Our system was further validated by comparison of disorientation spots between simulations and measurements obtained from six young subjects. From this validation, it was confirmed that the proposed system has a possibility of detecting disorientation spots, where people lose their way owing to the lack of signage or overlooking signage.

To validate the performance of the proposed system in detail, wayfinding experiments with a greater number of subjects in various as-is environments, including outdoor environments, must be conducted using more complex wayfinding scenarios in a future work. Furthermore, in Section 6.1 and Section 6.2, the noticeability threshold $n_t$ was specified without reference to measurements of human visual capabilities. However, in practice, $n_t$ must be specified as the minimum value estimated by the dominant users of the environment in consideration of their visual capabilities. Therefore, a method for determining a suitable value of $n_t$ using a statistical database related to human visual capabilities [37] will be developed in a future work.

The textured environmental geometry $G_I$ of the two-story indoor environment included a few distorted regions owing to performance limitations of the SfM software and poor textures on the walls. In the proposed system, $G_I$ was used for signage noticeability estimation. From the standpoint of evaluating ease of wayfinding, the system must detect the disorientation spot, where low signage noticeability is expected. In general, the signage noticeability decreases in areas where wall surfaces around the signage are complex and textural, i.e., saliency of signage design is relatively low compared to its surroundings. Fortunately, in such areas, $G_I$ can be well reconstructed owing to the nature of the SfM algorithm. Therefore, the proposed system can detect disorientation spots resulting from overlooking signage, even if a part of $G_I$ is distorted.

Furthermore, as mentioned in the literature [20], the presence of crowds influences the ease of wayfinding. Thus, crowd simulation technologies must be introduced into the proposed simulation framework. In addition, in the proposed system, the walking trajectory of the DHM was generated using a previously developed optimization algorithm [23]. However, as observed in Figure 14, the walking trajectories of individual human subjects vary. In our future work, such variabilities will be considered by introducing Monte Carlo simulation into the proposed system, i.e., generating a variety of DHM walking trajectories using the algorithm [23] with resampled parameters related to the trajectory generation.