(PDF) OpenHPS: An Open Source Hybrid Positioning System

OpenHPS: An Open Source Hybrid Positioning System Maxim Van de Wynckel Beat Signer Web & Information Systems Engineering Lab Web & Information Systems Engineering Lab Vrije Universiteit Brussel Vrije Universiteit Brussel 1050 Brussels, Belgium 1050 Brussels, Belgium

ABSTRACT abstraction supporting a wide range of positioning techniques and Positioning systems and frameworks use various techniques to de- fusion algorithms. termine the position of an object. Some of the existing solutions Using our knowledge on various positioning techniques and arXiv:2101.05198v1 [cs.CV] 29 Dec 2020 combine different sensory data at the time of positioning in order algorithms which are discussed in Section 2.1 and Section 2.2, we to compute more accurate positions by reducing the error intro- identified and analysed the actors of our system as highlighted in duced by the used individual positioning techniques. We present Section 4.1.1. This analysis revealed that actors play a different role OpenHPS, a generic hybrid positioning system implemented in depending on the positioning method being used. In order to allow TypeScript, that can not only reduce the error during tracking by the system to combine different existing positioning methods, we fusing different sensory data based on different algorithms, but also opted for a processing stream network where each node in a graph also make use of combined tracking techniques when calibrating topology contributes to the sampled data. or training the system. In addition to a detailed discussion of the Our design goal with the chosen processing network is to handle architecture, features and implementation of the extensible open positioning data in real time, giving developers complete control source OpenHPS framework, we illustrate the use of our solution in over the data flow. The proposed OpenHPS framework is presented a demonstrator application fusing different positioning techniques. in Section 4 together with an illustrative demonstrator use case While OpenHPS offers a number of positioning techniques, future before discussing some future work in Section 5. extensions might integrate new positioning methods or algorithms and support additional levels of abstraction including symbolic 2 BACKGROUND locations. The first step in conceptualising our hybrid positioning framework was to investigate existing positioning methods in order to find KEYWORDS their similarities as well as differences. OpenHPS has to be able to OpenHPS; hybrid positioning; open source; processing network; support a wide range of different positioning methods and imple- indoor positioning mentation goals. When analysing existing approaches, we made a distinction between positioning methods and algorithms, similar to 1 INTRODUCTION Wilson et al. [34]. Positioning methods represent the techniques Determining the location of a person or asset is an important aspect and technologies that are available to determine a location while of various human-computer interaction (HCI) solutions. Position positioning algorithms include the algorithms that can be used to tracking can be used to create autonomous vehicles, navigation combine these methods. systems and in context brokers such as CoBrA [7] to create implicit interactions based on the location and possibly other contextual 2.1 Positioning Methods information [35]. While we mainly rely on the Global Positioning System (GPS) to determine our location outdoors, many other posi- In this section we list some of the more prominent positioning tioning techniques exist that work both, indoors as well outdoors methods ranging from signal-based to visual solutions. Note that and sometimes even have been designed for completely different use the selected positioning methods represent a limited set of the cases as described later in Section 2.1. Each positioning technique techniques and functional requirements we aim to support. has its advantages and disadvantages depending on the environ- 2.1.1 Global Position System (GPS). Starting with the most well- ment where it is being used. Hybrid positioning systems use the known technology, the Global Positioning System (GPS) is used combination of different techniques and sensors to determine a for outdoor positioning [6]. It makes use of satellites in an orbit more accurate position through sensor fusion [8]. around the Earth to triangulate a location consisting of a longitude, One of the disadvantages with most commonly used indoor po- latitude and elevation. There also exist variations on the original sitioning methods such as Bluetooth Beacons or Wi-Fi access point global position system, including Differential GPS (DGPS) [33] or positioning is the requirement of some form of calibration or train- the Assisted GPS (a-GPS) [13] that fuses GPS with dead reckoning ing. With our proposed hybrid system called OpenHPS 1 , the goal is described later in Section 2.1.5. to achieve hybrid positioning during both, the navigation or track- ing (online stage) and between tracking, training and calibration 2.1.2 RF-based Positioning. RF-based positioning is a commonly of the used positioning techniques (offline stage). Unlike many of used technique for indoor environments. Examples of technologies the existing frameworks, the goal of OpenHPS is to offer a layered used for RF-based positioning include Wi-Fi, Bluetooth Beacons, 1 https://www.openhps.org RFID and LTE cell towers. These RF signals offer a landmark that Maxim Van de Wynckel and Beat Signer can be used as a reference when determining the position based on recognition or dead reckoning may want to perform different types fingerprinting or other mathematical calculations. of noise filtering algorithms tailored to their data. 2.1.3 Simultaneous Localisation and Mapping (SLAM). Simultane- 2.2.4 Machine Learning. This type of algorithms includes a number ous Localisation and Mapping, or SLAM for short, is a positioning of machine learning algorithms that can be of aid during calibration method that makes use of 2D sensors to map its surroundings. One as well as positioning. These algorithms require training during of the more common examples includes the use of LIDAR (Light the offline stage with the results being deployed during the online Detection and Ranging) [28], capturing distance readings around a stage. This issue will be further discussed when discussing the sensor. These readings can then be used to generate a 2D map of requirements in Section 4.1, where we allow data to be used in the the environment. online and offline stages of the OpenHPS framework. 2.1.4 Visual Positioning Techniques. Existing visual positioning 2.2.5 Computer Vision. With the visual positioning methods dis- techniques use image sensors to determine the position of the object cussed in Section 2.1.4, the tracked actor is not always uniquely the sensor is attached to (e.g. Visual SLAM [38]) or the position identified. Such visual positioning methods have to be able to detect of objects in its field of view. In previously mentioned positioning and track objects between multiple frames, camera angles or posi- methods, the tracked object obtains the sensor data. With Multi- tions. The algorithms used to track and detect persons or objects Target Multi-Camera Tracking (MTMCT) [23] the tracked object is from a video stream are beyond the scope of our framework, but moving within the field of view of one or more image sensors. OpenHPS should be able to provide a generic interface supporting these types of algorithms. 2.1.5 Dead Reckoning. Dead reckoning calculates the current po- sition based on the previous known position and the velocity or 2.3 Hybrid Positioning acceleration that is applied to that position [3, 20]. While the ac- Apart from supporting different positioning methods and algo- curacy of dead reckoning is not ideal, it can be used to improved rithms, OpenHPS should be able to combine these methods. This other positioning techniques such as GPS. requires a choice of algorithms to specify how the result of each method can be used in the combined output. 2.2 Positioning Algorithms Sensor fusion can occur at a low or high level [14]. Raw sensor In order to calculate a position or to combine multiple positioning data such as IMU sensors or the relative signal strength from a methods, different algorithms are used. The list of algorithms pre- transmitter can be fused in noise filtering algorithms. On a high sented in this section offers a baseline for the types of positioning level, calculated or provided positions (i.e. by third-party position- algorithms to be supported, but our OpenHPS framework is not ing systems) with a certain predicted accuracy can be combined limited to the presented set of algorithms. using linear regression, heuristic weighted averages or any decision fusion algorithm. 2.2.1 Triangulation and Multilateration. Mathematical operations such as triangulation and multilateration can be used for several 3 RELATED WORK positioning methods and technologies discussed in Section 2.1. For Location-based Services (LBS) represent a generalised category techniques that provide a landmark such as RF-based positioning, of systems that provide the current location of a person or other the received signal strength (RSS) might provide a rough estimate objects [24]. A distinction between a push- and pull-based LBS is of the distance. Other examples include mathematical positioning made [37]. A pull LBS provides a location when it is requested to using a time difference with respect to the time of arrival (ToA) or do so, while a push LBS delivers information when a new location the angle of arrival (AoA). is determined by a provider. The idea of combining multiple positioning methods in an LBS 2.2.2 Fingerprinting. While with multilateration we only need in- is not new. In this section we present some related work, ranging formation about the position of the used landmarks, fingerprint- from existing hybrid positioning systems, frameworks, their used ing requires a calibration for all possible positions in the tracking terminology and standards throughout location-based services. area [39]. A fingerprint of the sensor data at a given provided position is created during the offline stage. Later, these stored fin- gerprints are used during the online stage to reverse the sensor 3.1 Location APIs and Specifications data into a position. On the Web, the Geolocation API [31] offers a high-level interface for single or repeated position updates. The API provides an ab- 2.2.3 Noise Filtering. Sensor data should be filtered, which can be straction of the underlying technologies and algorithms used to done through different noise filters. Similar to dead reckoning, a determine the position. However, developers can request a high noise filter often requires knowledge of previous sensor readings accuracy result or maximum cache age if hardware permits this. and positions to predict the next result. Resulting positions are geographical coordinates complying with Noise filtering is one of the main requirements of our hybrid the WGS84 standard [11]. positioning system. The reason why we want to combine multiple JSR-179 and the improved JSR-293 [2] specifications are Java 2 technologies or algorithms is to reduce errors and noise filtering Micro Edition (J2ME) modules that provide developers an API to is the key component in realising this error reduction of position- obtain the location and orientation of a mobile device. Included in ing data. Note that individual positioning methods such as object the API is a storage interface for landmarks (see Section 2.1.2). The OpenHPS: An Open Source Hybrid Positioning System specification represents locations as timestamped coordinates with only provide geographical positions, HyLocSys provides geometric, an orientation, accuracy, speed and information about the used symbolic as well as hybrid location models. Symbolic locations rep- positioning method [12]. When requesting a location, criteria such resent abstract places such as buildings, floors and rooms that are as the desired accuracy, power consumption and response timeout relatively positioned to each other. A hybrid location can convert can be provided. this symbolic location to a geometric position. Note that the paper WebXR [22, 27] is a Web API that provides an interface for the does not discuss positioning technologies such as dead reckoning or tracking and use of VR or AR headsets. The API uses the pose SLAM that require periodic updates in order to keep an up-to-date terminology to indicate the position and orientation of the person position. wearing an XR headset in 3D space. While WebXR should not be Scholl et al. [36] propose a system that uses a LIDAR scanner considered as a location API, its specification uses terminology that to determine the fingerprinting position. This is somewhat similar is common in our framework. As an API that provides a tracking to our goal of using different positioning methods to support the position, it adds a goal for our framework to support these third- offline stage. party APIs. The Robot Operating System (ROS) [32] is a structured com- munication layer that can be used to create autonomous robots. It focuses on the integration of various robotics aspects such as 3.2 Hybrid Positioning Systems positioning, computing and hardware interfacing. ROS provides Various research concerning the fusion of sensor data to predict the concept of peer-connected nodes that perform computational a more accurate position exists. SignalSLAM [29] represents an tasks. These nodes represent interchangeable software modules example of a hybrid system that uses signals of various positioning that help to build a pipeline from sensory data to an output action. methods such as GPS, Wi-Fi and Bluetooth to map the surround- For positions and orientations, ROS uses the pose concept which ings. Chen et al. [8] have shown how a smartphone can combine contains both the position and orientation of a user. sensor data of Wi-Fi access point positioning and Pedestrian Dead Our framework should adhere to specifications such as WGS84 Reckoning (PDR). This combination of dead reckoning with another when working with geographical positions. However, unlike many positioning method is a common combination used by many hybrid of the related work discussed in this section, we also want to support systems. LearnLoc [30] is a smartphone-centred positioning frame- non-geometric positions. The hybrid location model presented by work that uses fingerprinting algorithms (k-nearest neighbours Ficco and Russo [15] offers a good type of location, but is still algorithm) in combination with various sensor data available on heavily focused on geometric positions. a smartphone to provide power-efficient indoor positioning. The Positioning methods and algorithms are often represented un- consideration of power efficiency is a common requirement in mo- der the term providers that are optionally combined via high-level bile positioning systems. Other than achieving the most accurate decision fusion. In our framework, we want to separate providers position, these location-based services use sensor fusion to prevent into generic algorithms and positioning methods that can easily be the continuous use of precise sensors such as cameras or GPS. switched. This not only allows for more extensibility, but also some IndoorAtlas provides a Platform-as-a-Service (PaaS) with a well- low-level sensor fusion. established Software Development Kit (SDK) for combining Wi-Fi, The Geolocation API, JSR-179 and HyLocSys allow for the speci- GPS, Bluetooth beacons, dead reckoning and even geomagnetic fication of accuracy or other criteria when requesting a position. positioning [18]. While the latter method has been found to be less However, unlike high-level APIs that hide the underlying technolo- ideal in steel reinforced buildings [30], it still offers a useful addi- gies, OpenHPS is aimed towards developers with an understanding tion for creating a hybrid positioning system where geomagnetic of the available hardware and positioning techniques that influence positioning might be combined with other positioning methods. the criteria. In the research by Bekkelien and Deriaz [4] a framework called The landmark storage of JSR-179 is a very useful addition to a po- Global Positioning Module (GPM) had been presented for in- and sitioning system, as it is a common requirement for many position- outdoor positioning. GPM provides a uniform interface to different ing techniques. The persistence of landmarks between the online position providers. These providers are fused in a kernel that selects and offline stage is an important requirement that is extended to fin- the position based on provided criteria (e.g. precision, accuracy or gerprinting information and cached position storage in OpenHPS. detection probability). Their approach offers a clear methodology This persistence should allow us to interface with existing systems on how this criteria can contribute to the selection or fusion of such as the Geolocation API that support both push-based position different technologies. However, the position providers and kernels updates as well as retrieving the current (cached) position. are implemented on a high level of abstraction providing no room for developers to choose different algorithms or fusion techniques. Ficco and Russo [15] presented a technology-independent hy- brid positioning middleware called HyLocSys. Position estimators, 4 OPENHPS FRAMEWORK representing different technologies, provide positions when a user In this section, we present and discuss the system design of our performs a pull of their current position. Sensor fusion combines proposed OpenHPS hybrid positioning framework. After listing these estimated positions into a final response. With the middleware some general requirements in Section 4.1, we outline the overall being an extension of the JSR-179 specification presented earlier, architecture in Section 4.2. Next, we provide some general infor- these pull requests accept criteria such as the preferred response mation on our chosen implementation and demonstrate the use of time and expected accuracy. Other than many frameworks that OpenHPS in Section 4.3 and Section 4.4. Maxim Van de Wynckel and Beat Signer 4.1 Requirements • Decentralisation: Our positioning framework should be Based on existing positioning methods and algorithms discussed in able to combine the four different actors introduced in the Section 2.1 and Section 2.2, the following framework requirements previous section based on remote hardware. This requires have been derived. We start by specifying the actors of our system the framework to work decentralised without requiring any and motivate the use of a processing network where each node of centralised sensor fusion, which can be achieved by allowing the graph topology might represent one of these actors. multiple computing actors to work independently. However, developers should still be given the option to centralise cer- 4.1.1 System Actors. After investigating different existing posi- tain parts of the system if needed. tioning techniques, we defined four actors in OpenHPS: • Monotonicity: Partial information from a source should result in a partial output. In the context of a positioning • Tracked actor: This is an actor that can be tracked during system, this means that a computing actor does not need the online positioning stage. A tracked actor can be an end the sensor data of all positioning methods to determine a user or an asset that might optionally contain sensors to position. This requirement also helps in the decentralisation further support the tracking. Our main goal is to determine and parallelisation of the framework. the most accurate position of this type of actor. • Tracking actor: This type of actor is responsible for track- 4.1.3 Non-functional Requirements. The following non-functional ing a tracked actor. Note that for some positioning methods, requirements contributed to the final decision about the software the same actor might act as a tracking actor as well as a language used for OpenHPS. tracked actor. However, for positioning methods such as the • Availability: Our solution has to be available on various visual object tracking introduced in Section 2.1.4, the track- platforms ranging from servers to embedded systems; also ing actor is represented by the camera while a tracked actor supporting the decentralisation functional requirement. is the object that is being detected. • Performance and latency: Throughput is an important • Calibration actor: Some positioning methods require a cal- criteria when processing streaming data. Input data such as ibration before the positioning method can be used. Unlike video and audio streams needs to be processed in real time. the tracked actor, the purpose of a calibration actor is to The latency also indicates how long it takes for data to be train and calibrate how the tracking actor will be used in the used in computations. As our goal is to achieve an accurate online stage of the system. current position, outdated sensor data is not relevant. • Computing actor: The computing actor is responsible for • Modularity: The framework should be modular with both, providing the final position output by our system. This ac- a low-level API and modules that can be added and removed tor combines the data generated by one or more tracking based on the available sensors and concrete use cases. De- actors about a tracked actor and processes the data by, for velopers should remain in control of the types of algorithms example, using one of the positioning algorithms described and the flow of data from producer to consumer. in Section 2.2. These four actors represent the four main components within 4.2 Framework Architecture OpenHPS. By distinguishing between the tracked and tracking actor, In order to support the presented functional and non-functional the system is able to support the tracking of persons or objects that requirements, we decided to build on a stream-based positioning do not actively participate in the positioning process. system that takes various types of input data and processes this data to get the desired output. Data that is transmitted between nodes 4.1.2 Functional Requirements. In the following, we list the mini- is encapsulated in so-called data frames that can contain sensory mal functional requirements for our OpenHPS framework. data as well as one or more data objects the sensor data applies to, • Online stage positioning: In order to perform hybrid po- and are described in detail in Section 4.2.2. sitioning or sensor fusion, multiple (processed) sources need For the design of our process network, a number of existing to be combined by using different algorithms. stream- and layer-based frameworks such as Akka Streams [9] or • Offline stage positioning: Processed results can be used TensorFlow [1] have been investigated. These frameworks solve to calibrate positioning methods of another (online) stage. similar issues and are further detailed in Section 4.2.1. Due to the fact • Third-party frameworks: Our framework needs to sup- that each node needs to be configured individually, the decision was port third-party high-level positioning systems. These ex- made to investigate flow-based frameworks where each component ternal systems might provide their own calculated position of the stream network is added individually. of a tracked actor that needs to be fused with the position Unlike low-level data stream frameworks, OpenHPS focuses on determined by our framework. In addition, the identification data that is helpful for positioning. We offer a higher-level API of this tracked actor might differ between frameworks. for creating the network and data that is handled by the sytem. • Environment mapping: With the requirement to support Concepts such as edges or ports that are often found in stream-based positioning methods such as SLAM and VSLAM, the system programming languages are abstracted and not directly accessible does not only offer the possibility to output an absolute by developers. However, unlike other hybrid frameworks [4, 18], position, but might also create an environment map. Our the stream processing is extensible enough to give developers the solution should be capable of handling, storing and using opportunity to modify the positioning methods along with the used this map to its advantage. algorithms. OpenHPS: An Open Source Hybrid Positioning System We start by discussing our process network design that uses feedback loops to gain knowledge on previously calculated a graph topology similar to other stream frameworks. Next, we positioning data. present the data frames, objects and positional data that are being • Processing node: A processing node is a higher-level inter- handled by the network. face for a regular node. It provides an abstraction on the push and pull functionality to simplify the creation of a processing 4.2.1 Process Network Design. The OpenHPS framework uses a function of either data frames or individual data objects. process network to handle data. The data is processed and dynam- • Sink node: An output node or sink node accepts a specific ically manipulated by multiple connected nodes in a predefined data type as output frame. Unlike processing nodes, this type graph topology. In the following, we list our three main design of node will not push data to other nodes. Upon receiving a goals for this network: data frame, the data objects will be stored using a compat- (1) Consistent data types: Data that is being processed in the ible data service. Once saved, an event is sent upstream to network should have a reliable type and content. We process indicate that the processing of this frame and its contained DataObjects encapsulated in DataFrames, which provides objects is completed. a defined scope how generic parts of our network should Extensions of these nodes, allowing for specific data flow shapes handle information. and common position processing nodes, are provided in our core (2) Processing goal: Processing has the goal of providing an component. Figure 1 shows an example of a positioning model that absolute position for our tracked actors. With this goal we has a source node, a sink node and four processing nodes connected have a clear understanding how every computing actor con- in a graph structure. This positioning model describes a configured tributes to the output. computational model aimed for processing sensor and positioning (3) Producer priority: The producer or tracking actor has the data [25]. Similar to existing streaming or pipelining frameworks, highest priority. Slow consumers or computing actors must the graph can contain data flow shapes that manipulate the flow of not result in outdated sensor information. Rather, developers data frames. Examples of such shapes include, but are not limited should be given the opportunity to control what happens to balance nodes, data frame chunking, debouncing and merging with the overflow of information that cannot be processed of data objects and their processed positions. timely. Starting from the goal of producing up-to-date positioning in- formation, we opted for a push-pull-based stream. Data can be ... dropped if its not relevant for determining a more up-to-date po- sition. The monotonicity of our framework ensures that positions Source Process Process Sink can be determined based on partial data. Each node can be designed to accept both push and pull requests. Similar to reactive streams [16], push and pull actions are promise- ... based and can be executed asynchronously. If a node that receives a pull request cannot respond with a data frame itself, it will forward the pull request to its incoming node(s). Different to a traditional pull that returns a response, we use Service A Service B Service C Map User Data Room the push terminology to indicate a response for a given pull. This Store Store Store behaviour and terminology is similar to Akka Streams [9], but unlike reactive streams where data can only be provided when there is a demand, there is no back pressure built into the stream Figure 1: Example OpenHPS positioning model itself. Using the push terminology for a pull response removes the ambiguity of a response arriving after an already existing push in All nodes in a positioning model have access to a set of ser- the pipeline. It also enforces the design goal of producers having vices that allow the storage of objects. In the given example, three the highest priority, even if a producer only generates information services are added for the storage of map, user data and room in- when requested. formation. In our implementation, sink nodes always store data A regular node has a unique identifier and push/pull functionality objects contained in received data frames. However, every node has for data frames. Each node can have 0 . . . 𝑛 inlets or outlets. Our the ability to fetch or insert new data into available services. This system consist of the following three subtypes of the regular node: persistence allows for the storage of landmark objects, similar to • Source node: A source node provides a specific data type. the JSR-179 specification [12]. At the same time, these services can This can either be a push or pull node that pushes data be used as an interface to fetch the latest position without requiring frames when they are available (e.g. a camera recording at a specific implementation in the sink. a fixed frame rate) or creates a new data frame when the The positioning model can be created by using a builder pattern downstream node asks for it via a pull request (e.g. triggering as illustrated in Listing 1. This builder creates the immutable prop- a Bluetooth scan). The source node merges data objects in erties of the model, including data services and the flow of data the data frame with those that were previously stored via from source to sink. Models can have multiple flow shapes, each data services. This merging behaviour prevents the need for with one or more sources, processing nodes and sinks. Maxim Van de Wynckel and Beat Signer Node #1 Node #2 Node #3 Node #4 /* @openhps/core | version 0.2.0 */ SourceNode ProcessingNode ProcessingNode SinkNode 1 ModelBuilder.create() pull() pull() pull() 2 .addService(/* ... */) 3 .addShape(GraphBuilder.create() 4 .from(/* ... */) 5 .via(/* ... */) push(data) 6 .to(/* ... */)) resolve pull resolve pull resolve pull 7 .build().then((model: Model) => { /* ... */ }); resolve push push(data') Listing 1: Creation of a positioning model resolve push push(data'') In Figure 2, data is being pushed by an active source node. Pro- cessing nodes will process the data and push the modified frame to resolve push their output nodes. Push and pull actions are promise-based and completed data'' completed data'' completed data'' resolved whenever the node finishes processing the frame. This allows for non-blocking asynchronous requests. The resolved push promise (indicated in green) gives an indication that the processing Figure 3: Data being pushed by source after receiving a pull of the push is finished. However, it does not provide knowledge on whether or not the frame is processed by the complete network. To indicate this, sink nodes that receive a frame will emit a completed pull-based source node on lines 1 to 7 implements the onPull() event that includes the data frame identifier and list of persisted function that is called whenever the source receives a pull() re- object identifiers. quest. This function expects a promise of a data frame. Internally, the extended source node class will push this data frame as shown Node #1 Node #2 Node #3 Node #4 in Figure 3. With the push-based source (lines 9 to 22), the onPull() SourceNode ProcessingNode ProcessingNode SinkNode is unused. Instead, a timer is created that pushes a new data frame push(data) every 1000 milliseconds. A similar abstraction exists for sink nodes resolve push push(data') with the onPush() function. resolve push push(data'') /* @openhps/core | version 0.2.0 */ resolve push 1 export class PullBasedSource extends SourceNode<DataFrame> { 2 public onPull(): Promise<DataFrame> { completed data'' completed data'' completed data'' 3 return new Promise((resolve) => { 4 resolve(new DataFrame(this.source)); 5 }); 6 } Figure 2: Data being pushed by a source 7 } 8 9 export class PushBasedSource extends SourceNode<DataFrame> { With the swim lane shown in Figure 3, the data is not auto- 10 constructor(source: DataObject) { 11 super(source); matically pushed by the source node. A downstream node such 12 this.on('build', () => { as a sink will send a pull() request to its input nodes. If these 13 setInterval(this._generate.bind(this), 1000); nodes cannot provide a frame of their own, the pull() request is 14 }); 15 } forwarded to their respective input nodes. If the source has data 16 private _generate(): void { available, a response to this pull is provided asynchronously. As 17 this.push(new DataFrame(this.source)) mentioned in the beginning of this section, a pull() response will 18 } 19 public onPull(): Promise<DataFrame> { use the same invocation as a push(). In that case, the pull promise 20 return Promise.resolve(undefined); is resolved right after the source sends this push as indicated by 21 } 22 } the blue resolve chain in Figure 3. As promises are resolved after the data frame is processed by a node, upstream nodes in the process chain cannot determine Listing 2: Push- and pull-based SourceNode classes whether data has been processed successfully. Figure 5 shows a push() request that throws an error at the sink node (e.g. failure to Similar to sources and sinks, processing nodes are abstracted. store). An error event is triggered on previous node(s). By default, Any pull() requests to these nodes are automatically forwarded these nodes will chain the error to upstream nodes. However, each to the incoming nodes, as these process nodes do not generate new node can act upon this error in its individual implementation. data frames. Developers are expected to implement a process() Nodes are implemented by developers on a high level of abstrac- function manipulating a frame or individual objects within a frame. tion compared to other stream processing frameworks. Developers do not have the ability to push or pull from specific incoming or 4.2.2 Data Frame. Data that is pushed through the positioning outgoing edges. Listing 2 shows two custom source nodes. The model is represented within data frames, generated by a source OpenHPS: An Open Source Hybrid Positioning System VideoDataFrame IMUDataFrame RFDataFrame uid timestamp uid timestamp uid timestamp source DataObject source source AP1 CameraObject DataObject RFReceiverObject DataObject Detected uid: "camera", object uid: "imusensor", uid: "wifiscanner", uid: "AP1", position: { DataObject position: { relativePositions: [ position: { No additional objects x: 2, y: 5, z: 3 x: 0, y: 0, { x: 0, y: 0 AP2 }, Detected linearVelocity: { obj: "API1", } DataObject projection: ..., object DataObject x: 1, y: 0 distance: 5 width: 1280, } }, { uid: "AP2", height: 1024 Detected } obj: "AP2", position: { object distance: 8 x: 15, y: 3 }] } Image Acceleration Sensor Frequency Figure 4: Data frame content examples node. This ensures that the origin of data can be determined via existing velocity. In our third and final example, we show a data some collection of metadata. The data contained in these frames frame created by a Wi-Fi scanner. The scanner (source) has two includes (but is not limited to) the following attributes: relative distances to access points (AP). The information, mainly • Unique identifier: Each frame generated by a source is the position of these access points is included in the frame. uniquely identified. This ensures that frames which are being processed by multiple processing nodes in parallel can be Node #1 Node #2 Node #3 Node #4 SourceNode ProcessingNode ProcessingNode SinkNode merged at a later stage in the stream. push(data) • Timestamp: Required for determining when the data was created or obtained. When working with multiple sources resolve push push(data') that capture data of the same tracked actor, the timestamps resolve push push(data'') will be used to merge the data frames. A timestamp is kept for the creation of each data frame by the source. This timestamp emit error emit error reject push can also be used for time-based calculations such as applying velocity to a position. Using this timestamp instead of the system time results in a more deterministic output. Figure 5: Error handling in push() request • Source data object: This is the data object that obtained the sensory data (e.g. the camera object or RF receiver). It is not always the object that is being tracked, but it can be required 4.2.3 Position. Similar to existing work [17, 26], OpenHPS distin- in order to determine the position of other objects (see actors guishes between relative and absolute positions. Absolute positions in Section 4.1.1). Similar to the timestamp and identifier, the represent a fixed position in a specified space while relative po- source data object can be used to specify certain criteria on sitions indicate the position relative to another object. Absolute how data frames or positions should be merged. positions contain the following information: • Data objects: Data objects include everything that is of • Timestamp: The time when the absolute position has been relevance to the positioning (e.g. the tracking and tracked recorded or modified. The timestamp can be set by the sensor actor). This also includes reference spaces needed for the or by a processing node that calculated the position. positioning as pointed out later in Section 4.2.5. By grouping • Accuracy: General position accuracy with the same unit the data objects in the same data frame, nodes do not have as the position itself. In the context of a hybrid positioning to access any services to get this relevant information. system, the accuracy can be used as a weight when merging In order to demonstrate the content of data frames, Figure 4 with other calculated positions. depicts three situations where data is contained in frames. The • Orientation: Stationary orientation of the data object at the first example shows a data frame created by a camera source. This recorded position. This orientation is relative to the 𝑋 -axis camera object has a certain position and projection matrix. Linked and is represented in quaternions. However, it is possible to to the data frame is a single image (i.e. video frame) captured by this convert the quaternion representation to (and from) Euler source. During the processing of the image, objects can be detected or axis angles. and added to this frame before being pushed further downstream. In • Linear velocity: Linear velocity at the recorded position, the second example we show data obtained by an accelerometer. The relative to the orientation of the object (see Figure 6) using source object has a velocity and position, the frame itself contains the axis 𝑋𝑂𝑏 𝑗 and 𝑌𝑂𝑏 𝑗 of the point 𝑃 with orientation 𝜙. the current acceleration and sensor frequency. This information • Angular velocity: Similar to linear velocity, the angular can be used by a processing node to add the acceleration to the velocity is relative to the orientation of the object. Maxim Van de Wynckel and Beat Signer • Position vector: Each position can be converted to a three- relevance of this last known position can be determined dimensional vector, which enables the use of 2D positions using its timestamp and developers can request the trans- in 3D reference spaces. formed position in their own reference space. • Unit: Length unit of the position. This unit applies to the • Relative positions: These are relative positions to other position vector and its accuracy. reference objects. Each object can have multiple types of positions relative to different objects. This allows a data 𝑌 object to have a relative distance, angle and velocity to the same object. • Parent object: A data object can specify its parent. This can 𝑌𝑂𝑏 𝑗 be useful for indicating that individual sensor objects belong to the same tracked actor. Depending on what the data object represents, it can be extended 𝑋𝑂𝑏 𝑗 to store the information needed for its representation. In Listing 3, we create a basic data object of a user who is uniquely identified by 𝜙 their e-mail. During the creation of this object, we set the current 𝑃 position to a geographical coordinate. 𝑋 /* @openhps/core | version 0.2.0 */ 1 const object = new DataObject("

"); 2 object.displayName = "Maxim Van de Wynckel"; Figure 6: Position representation 3 object.setPosition(new GeographicalPosition(50.82075, 4.39234)); Relative positions have the following attributes: Listing 3: Creation of a DataObject • Timestamp: Similar to the absolute position, this is the time when the relative position has been recorded. Data objects can be created and modified without those changes • Accuracy: General position accuracy in a specified unit. being persisted in the positioning model. In order to detect persisted • Reference object: The referenced data object to which the changes, a listener can be added to the data object service as shown position is relative to. in Listing 4. • Reference value: The value that determines the relative position to the reference object. This can be a distance, angle /* @openhps/core | version 0.2.0 */ or velocity. 1 const service = myModel.findDataSerice(DataObject); 2 service.on('insert', (uid, changedObject) => { By default, OpenHPS and its core positioning algorithms sup- 3 if (uid === object.uid) port 2D, 3D and geographical coordinates. Developers can further 4 console.log(changedObject.getPosition()); 5 }); extend the coordinate space with higher-level absolute and relative positions. Positions can be stored with a specified unit (i.e. length unit for absolute positions) in order to offer developers flexibility Listing 4: Listener for data object changes in the stored precision. Linear and angular velocity values are con- verted to a fixed unit (𝑚/𝑠 for linear and 𝑟𝑎𝑑/𝑠 for angular velocity). 4.2.5 Reference Space. Reference spaces are data objects that rep- However, this can be customised by extending the velocity objects. resent spaces which are used for absolute positions. Using these The position terminology is used throughout the API as opposed reference spaces, absolute positions created in a different space can to location or pose. Pose is a term that is often used when defining easily be identified and transformed to the global reference space a position and orientation in a three-dimensional space. However, created when building a model. with the support of 2D positions, this term was not favourable. Location is described by the English Oxford Dictionary as “a par- /* @openhps/core | version 0.2.0 */ ticular place or position”. This abstraction of “place” led us to our 1 const refSpace = new ReferenceSpace(model.referenceSpace) final decision of choosing the more precise position terminology. 2 .unit(LengthUnit.CENTIMETER) 3 .translation(10, 10, 0) 4.2.4 Data Object. A data object represents anything that is rele- 4 .scale(1, 1, 0) vant to the positioning. It can be the tracked object, the tracking 5 .rotation(0, 0, 0, AngleUnit.RADIANS); object or a landmark needed for the relative positioning. Each object contains the following attributes: Listing 5: Creation of a ReferenceSpace • Unique identifier: Data objects are uniquely identified, ei- ther by a supplied identifier or a random UID. Optionally, a Listing 5 shows the creation of a reference space relative to the developer can provide a more user-friendly display name. global space represented by model.referenceSpace. This refer- • Absolute position: Data objects store their last known ab- ence space has an origin offset. Absolute positions set when provid- solute position. The stored position is always relative to the ing this reference space will automatically transform to the origin global reference space introduced later in Section 4.2.5. The of the global space. OpenHPS: An Open Source Hybrid Positioning System A reference space can transform the position, velocity and orienta- • Trajectories: Historical position data of DataObjects. Dri- tion in the following ways: vers can be implemented for storing this information in • Translation: Translate the position with an origin offset. specialised databases such as MobilityDB [40]. • Rotation: Rotate the position, orientation and angular ve- Normal services in our framework include, but are not limited locity. to a time service that allows developers to synchronise the time • Scale: Scale the position and linear velocity. between multiple machines, and a worker service that acts as a • Perspective: Transform the (inverse) perspective of the po- (remote) proxy for data services. sition (e.g. the perspective of a camera). Listing 7 shows examples of how a service can be retrieved from • Unit conversion: Convert the unit of a position to a refer- the model. Nodes can retrieve a data service by providing either ence unit. the class of an object, an object instance or the class name of the Reference spaces can be created to model different scenarios: object. This allows the use of difference services for different types of DataObjects. • Third-party positioning systems: Frameworks like the WebXR [22] API manage their own origin and orientation based on the underlying hardware. The output of such third- /* @openhps/core | version 0.2.0 */ party frameworks are high-level positions that should be 1 // Finding a data service by class 2 this.model.findDataService(DataObject); aligned with the other positioning methods. 3 // Finding a data service object instance • Sensor placement: Developers can model a reference space 4 this.model.findDataService(myObject); for sensors that have a static offset or rotation (e.g. a motion 5 // Finding a data service by name 6 this.model.findDataService("RFDataObject"); sensor that is placed upside down). • Calibrated reference space: Some sensors require a cali- bration (either automatic or by manual user input). A goal Listing 7: Retrieving a data service from a model of OpenHPS is to easily persist this type of calibration. • Map storage: As a data object, a reference space can be extended to store environment map information as outlined 4.2.7 Measurement Units. Unlike many positioning frameworks in our functional requirements. aiming for geographical positioning, OpenHPS aims to support a wide range of use cases ranging from small scale to celestial In Listing 6, we set the current position of a data object to (5, 5, 5) positioning. We provide a unit system consisting of the Unit and using the previously created reference space shown in Listing 5. DerivedUnit objects. A derived unit consists of multiple units with Internally, the stored position of myObject will be the transformed a specific power and offset. Math.js [10] offers a similar unit system position with coordinates (−5, −5, 5). with the possibility to automatically evaluate and convert units. While this allows for the easy creation of derived units, it is not necessary for our framework. /* @openhps/core | version 0.2.0 */ 1 myObject.setPosition(new Absolute3DPosition(5, 5, 5), refSpace); /* @openhps/core | version 0.2.0 */ Listing 6: Setting the object position in a reference space 1 // Time unit called 'second' 2 const second = new TimeUnit('second', { 3 // Unit for 'time' 4 baseName: 'time', As these spaces are data objects, they are uniquely identified and 5 // Also called 's', 'sec' or plural can have a parent object or space. This parent allows for abstract 6 aliases: ['s', 'sec', 'seconds'], 7 // Supports decimal prefixes (milli, micro, ...) reference spaces such as rooms, floors and buildings. These types of 8 prefixes: 'decimal', abstractions allow us to use different positioning methods per floor 9 }); 10 that are stored in a global reference space representing a building. 11 // Millisecond is a second with the prefix specifier milli 12 const millisecond = second.specifier(UnitPrefix.MILLI); 4.2.6 Services. Each positioning model can have multiple services. 13 A service can be accessed by all nodes in that model to perform 14 const minute = new TimeUnit('minute', { 15 baseName: 'time', certain general actions ranging from communication services that 16 aliases: ['m', 'min', 'minutes'], handle the data between remote nodes, to data services that store 17 // Minute can be defined as 60 * 1 second data frames, objects or other relevant information. 18 definitions: [{ magnitude: 60, unit: 's' }], 19 }); A data service serialises and stores information. By default, our core API offers data services for: • Data objects: To store the processed objects and their last Listing 8: Unit creation known position. This can also be used as a persistent storage for landmarks used in the positioning. Listing 8 shows the creation of a base unit second for time. • Node data: Node-specific data about DataObjects can be During its creation the developer can specify aliases for the unit and stored. This can be useful for intermediate calculations by similar to Math.js, a unit can have a set of unit prefixes. This allows noise filtering algorithms or sensor fusion techniques. the use of “millisecond, microsecond, nanosecond, . . . ” without Maxim Van de Wynckel and Beat Signer specifically creating individual units for these specifiers. Note that /* @openhps/core | version 0.2.0 */ aliases can be provided to optionally allow the units to be converted 1 { to string evaluators of other mathematical modules. 2 "createdTimestamp":1606501972983302, When creating a new unit, the developer should specify the base 3 "uid":"8865727c-7c98-4a8d-a33c-506d2650e59d", 4 "position":{ unit. For the minute example in Listing 8 this is done by creating a 5 "x":-4.07093248547983, definition for converting minutes to seconds (using a magnitude of 6 "y":55.59130128032057, 7 "timestamp":1606502001594449, 60 for the unit seconds). 8 "velocity":{ 9 "linear":{ 10 "x":-0.27608249684331726, /* @openhps/core | version 0.2.0 */ 11 "y":0.3606549076013354, 1 const radSecond = new DerivedUnit('radian per second', { 12 "z":0.013291033512841348 2 baseName: 'angularvelocity', 13 }, 3 aliases: ['rad/s', 'radians per second'], 14 "angular":{ 4 }) 15 "x":-3.9937982517329886, 5 .addUnit(AngleUnit.RADIAN, 1) 16 "y":0.2311694373502423, 6 .addUnit(TimeUnit.SECOND, -1); 17 "z":-0.5070813464456928 7 18 } 8 const degreeSecond = radSecond.swap( 19 }, 9 [AngleUnit.DEGREE], 20 "orientation":{ 10 { 21 "x":-0.09754179767548248, 11 baseName: 'angularvelocity', 22 "y":0.15388368786071302, 12 name: 'degree per second', 23 "z":0.04266920115206052, 13 aliases: ['deg/s', 'degrees per second'], 24 "w":0.9823363719162936 14 }); 25 }, 15 26 "unit":{ 16 const degreeMinute = radSecond.swap( 27 "name":"centimeter" 17 [AngleUnit.DEGREE, TimeUnit.MINUTE], 28 }, 18 { 29 "referenceSpaceUID":"5582d63d-c7af-4624-9fed-6ce0d9036f62", 19 baseName: 'angularvelocity', 30 "accuracyUnit":{ 20 name: 'degree per minute', 31 "name":"meter" 21 aliases: ['deg/min', 'degrees per minute'], 32 }, 22 }); 33 "__type":"Absolute2DPosition" 34 }, 35 "relativePositions":[], 36 "__type":"DataObject" Listing 9: Derived unit creation 37 } In order to use a unit that is derived from other base units, a Listing 10: Serialised DataObject DerivedUnit can be created as shown in Listing 9. The developer provides a name of the unit and adds the units that are contained in the derived unit (lines 5 and 6) along with their magnitude. Variants on derived units can be created by swapping a unit (lines 9 and 17). Listing 10 shows a serialised data object created with sensor data retrieved from a Sphero Mini6 toy. The main DataObject and 4.3 Framework Implementation Absolute2DPosition have a __type key that defines the object type. Definitions of a unit are not included in the serialisation and OpenHPS is implemented in TypeScript2 , a type-safe superset of its complete name is used to indicate the unit. This means that a JavaScript. It can be executed as a client-side browser application, custom unit should be available in all processes that are required hybrid mobile applications, on JavaScript supported embedded to deserialise the unit. systems such as Espruino and even as a server-side application using Node.js3 or Deno4 . 4.3.2 Performance. One of the non-functional requirements men- The ability to run our positioning model on a large range of tioned in Section 4.1 is the ability to perform real-time data process- server and client devices enables the decentralisation mentioned ing. In order to achieve these performance requirements, parts of in the functional requirements. Additional remote components the processing network can be run in their own thread, web worker such as the socket API outlined in Section 4.3.4 allow for other or process. This threading is made possible due to the serialisability programming languages to be supported as well. of data frames and objects, which allows the transmission of frames from one process or thread to another. 4.3.1 Serialisation. Data frames and contained objects are serialis- Listing 11 shows the creation of a model with parts of the graph able throughout the framework. This functionality is implemented going through a WorkerNode. This threaded node is initialised with using an extension of TypedJSON5 that adds the ability for poly- a model builder function evaluated on the threaded process. If no morphic data types. The detection of such data types is necessary data services are (re)initialised in this function, the data services of for allowing developers to create additional position or data objects the main thread are made accessible in the individual threads. without having to recreate all classes where these are used. A WorkerNode can also run a larger portion of a process network 2 https://www.typescriptlang.org that is declared in a separate file. This is more developer friendly 3 https://nodejs.org/en/about/ 4 https://deno.land 5 https://github.com/JohnWeisz/TypedJSON 6 https://sphero.com/products/sphero-mini OpenHPS: An Open Source Hybrid Positioning System #workers FPS Error Speed-up /* @openhps/core | version 0.2.0 */ 1 ModelBuilder.create() Sequential 229.04 1.19% - 2 .addService(/* ... */) 1 200.74 0.67% 0.88 3 .from(/* ... */) 2 389.44 0.56% 1.70 4 .via(new WorkerNode((builder: GraphShapeBuilder) => { 5 const { TrilaterationNode } = require('@openhps/core'); 3 512.42 0.92% 2.24 6 builder.via(new TrilaterationNode()) 4 616.29 1.15% 2.69 7 }, { 5 671.00 0.59% 2.93 8 poolSize: 4 9 })) 6 746.07 0.67% 3.26 10 .to(/* ... */) 7 801.32 0.90% 3.50 11 .build().then(model => { /* ... */ }); 8 822.47 0.69% 3.59 Table 1: WorkerNode benchmark Listing 11: Threaded node creation time service that returns the time in a specific unit. This allows de- than having to import all the nodes within a builder function. List- velopers to extend the framework with additional modules such as ing 12 shows the worker node named “video” being created in the microtime7 for more precise calculations. In addition, Decimal.js8 main thread (lines 2 to 6). Internally, this node is a graph created in could be used with an extended position class to provide more video.ts. Pull requests to this node (line 8) will be forwarded to a precise number operations. pool of four workers. 4.3.4 Modularity. OpenHPS provides a modular API that splits the functionality of positioning methods and algorithms in differ- /* @openhps/core | version 0.2.0 */ ent npm9 modules. Using this method, developers can extend on 1 // main.ts // our core framework or other components. It also prevents them 2 ModelBuilder.create() from having to depend on very large modules, reducing the overall 3 .addNode(new WorkerNode("video.ts", { 4 poolSize: 4, dependency size. 5 name: "video" 6 })) 7 .from("video") 8 .via(new TimedPull(1, TimeUnit.MILLISECOND)) 9 .to(/* ... */) graph 10 .build().then(model => { /* ... */ }); object unit 11 graph 12 // video.ts // data 13 export default GraphBuilder.create() reflect.js threads 14 .from(/* ... */) 15 .via(/* ... */) services 16 .to(); utils dependencies services position typedjson Listing 12: Threaded graph creation shapes As a simple demonstration of our worker node, we created a nodes processing node calculating 5000 prime numbers for every received frame. This test was conducted on an Intel i7-6700HQ laptop CPU other processing math misc with 8 logical cores, running Node.js 14.10. These 5000 prime num- bers can be calculated 237.03 times per second without the over- Figure 7: @openhps/core minified web module tree map head of data frames, objects and services. The data frames that we push contain a source object, position and velocity to simulate the Our core API, named @openhps/core is available for server and amount of data normally serialised and communicated between the web deployment in the CommonJS (CJS), ECMAScript (ESM) and main process and workers. However, the contained data does not Universal Module Definition (UMD) formats. Figure 7 presents an affect the time it takes to compute the prime numbers. overview of the core components content size in its current state Table 1 shows the results of our benchmark with one worker (version 0.2.0). Most of the file size is taken up by dependencies assigned to each logical CPU core. Performance is measured in (≈30%, indicated in blue) and the mathematical classes of Three.js10 frames per second (FPS) represented by the amount of computed (≈22%, as part of the mathematical utilities in yellow). Default nodes data frames received by the sink of our model. For each worker we such as processing nodes, graph shapes and common sink or source indicate the speed-up compared to the sequential implementation. nodes account for ≈16%. The main purpose of the dependencies are The overhead shown with a single worker is due to the serialisation to help with serialisation (i.e. TypedJSON, Reflect.js). Mathematical and deserialisation of data, an operation that is not required when pushing in a sequential network. 7 https://www.npmjs.com/package/microtime 8 https://www.npmjs.com/package/decimal 4.3.3 Precision. Calculations within the framework are made us- 9 https://www.npmjs.com ing JavaScript number operations. Time-critical operations use a 10 https://threejs.org/docs/ Maxim Van de Wynckel and Beat Signer classes such as quaternions, matrices and vectors from Three.js offer general operations for handling 2D and 3D position manipulation. We list several examples of modules that can be used to extend the core functionality: • Data storage: By default, the core API provides the possibil- ity of using in-memory data storage. In order for this data to be persisted, additional components making use of different database management systems such as MongoDB, Redis or MobilityDB [40] can be applied. • Remote communication: The remote APIs introduce a RemoteNode that can be added to the model. This node will transmit push (or pull) requests to a remotely connected model through either a REST API, socket connection or a message broker such as MQTT [21]. • Positioning methods and algorithms: The core API of- fers basic processing nodes to determine a position (i.e. trilat- eration, triangulation or fingerprinting) and can be extended with different components. Examples include techniques Figure 8: Demonstrator overview that require additional machine learning or computer vision libraries. • Symbolic positions: Our core API offers the 2D, 3D and manually calibrated the origin orientation using the provided mo- geographical positioning. This can be abstracted to locations bile application for the Sphero. This provides us knowledge on the or places such as a room, building or site. start orientation used by the internally calculated position which • Third-party positioning systems: Third-party position- allowed us to define the reference spaces. ing solutions can be integrated into OpenHPS by using mod- Various methods exist to combine the aforementioned position- ules that provide this interface. ing methods. Figure 9 shows the simplified graph presentation of our demonstrated positioning model. Starting from the four differ- ent sources, we will discuss how each signal is processed and fused 4.4 Demonstrator together. We use two feedback loops from our fused position to Unlike some of the frameworks discussed in Section 3 that are made provide temporal information to our positioning model. to tackle a certain issue or goal, the core idea of OpenHPS is to combine different positioning concepts into one model. Main feedback loop As a non-trivial demonstrator, we provide a positioning system for a Sphero Mini toy using the internal sensors and an external Video Blob Velocity Debounce Source Detection Processing Logitech Brio11 camera. The Sphero provides raw sensor reading for the linear and angular velocity, raw accelerometer data, orien- tation and an internally computed position. This internal position is computed by the Sphero toy itself and makes use of the motor Input Velocity Position velocity, accelerometer and gyroscope. Sink Source Processing Merging We make use of the @openhps/core12 , @openhps/opencv13 and the use case-specific @openhps/sphero14 modules to construct a model that fuses these multiple sources together into one position. The model consists of four sources; the video input, internally IMU Velocity Velocity Source Processing Processing computed position, the input that is sent to the Sphero and finally the dead reckoned position that is calculated by the framework itself using the provided velocity. Our setup is shown in Figure 8. We used yellow floor markers to Sphero Velocity Position define an area of 260 𝑐𝑚 × 200 𝑐𝑚. The camera is positioned with a Filter Position Calculation Merging perspective view on the area and the start position of the Sphero is at the bottom right corner of the camera source. For the scope of this demonstration, the Sphero performs a sim- Figure 9: Demonstrator positioning model ple trajectory. The input for this device consists of an orientation (heading) and speed. Before the start of our input trajectory, we The results of each independent source is shown in the trajectory scatter plots in Figure 10. Each positioning method has a different 11 https://www.logitech.com/en-us/product/brio 12 https://github.com/OpenHPS/openhps-core/ frequency, resulting in a varying amount of data points used to 13 https://github.com/OpenHPS/openhps-opencv/ determine the position. Our main feedback loop in Figure 9 ensures 14 https://github.com/OpenHPS/openhps-sphero/ that the fused position never relies on a single source. OpenHPS: An Open Source Hybrid Positioning System (a) Input Position (b) Sphero Position 200 200 150 150 100 100 50 50 0 0 0 50 100 150 200 250 0 50 100 150 200 250 (c) Dead Reckoning Position (d) Video Position 200 200 150 150 100 100 50 50 0 0 0 50 100 150 200 250 0 50 100 150 200 250 Figure 10: Individual position estimates for the given in- put (a), including the internally calculated position (b), dead Figure 11: Conversion of wrapped video to blob reckoning position (c) and video source (d) 4.4.3 Internal Position. In Figure 10b we show the internal posi- tioning calculated by the Sphero, converted to a certain reference 4.4.1 Input Control. Input to the Sphero is given using a heading space created with our calibrated orientation knowledge. Instead (degrees), speed (0-255) and roll duration. We make the assumption of using the raw position, we determine the displacement of this in- that the Sphero Mini has a maximum speed of 1 𝑚/𝑠 as documented ternal position (using the filtered feedback loop shown in Figure 9) on the product website15 . and apply this displacement to the fused position. As input trajectory, we provide a spiralling rectangle starting from an outer corner to the centre of the area with a speed of 150 /* @openhps/core | version 0.2.0 */ (= 0.58 𝑚/𝑠). We provide a basic roll duration of 4.2 seconds (= 1 class ContourDetectionNode extends ProcessingNode<VideoFrame> { 2.436 𝑚) for the X-axis and a roll duration of 3.2 seconds (= 1.856 𝑚) 2 public process(frame: VideoFrame): Promise<VideoFrame> { for the Y-axis. Every turn, the duration of the movement along the 3 return new Promise((resolve) => { 4 let contours = frame.image.findContours( X-axis is reduced by 168 ms while the movement along the Y-axis 5 OpenCV.RETR_EXTERNAL, is reduced by 128 ms. This input is fed to our framework’s velocity 6 OpenCV.CHAIN_APPROX_SIMPLE); processing node resulting in the output shown in Figure 10a. 7 if (contours.length >= 1) { 8 // Sort contours by area 9 contours = contours.sort((a, b) => a.area - b.area); 4.4.2 Visual Positioning. The video source uses the OpenCV [5] 10 // Select the contour with the largest area size library to capture a 30 FPS camera feed from the Logitech Brio cam- 11 const m = contours[0].moments(); era which has a perspective view of the floor. When processing the 12 const center = new OpenCV.Vec2( 13 m.m10 / m.m00, video stream, we create the inverse perspective view by manually 14 m.m01 / m.m00); specifying the position of four yellow markers on the floor. This 15 // Use the center as the 2D pixel position 16 const position = new Absolute2DPosition( creates a wrapped image rectangle of 1040 𝑝𝑥 × 800 𝑝𝑥. 17 center.x, Once the video source is wrapped, blob detection is used to 18 center.y); determine the centroid position of the blue Sphero Mini. We apply 19 position.unit = LengthUnit.CENTIMETER; 20 position.accuracy = Math.sqrt(contours[0].area); a colour mask that converts the image to an HSV colour space and 21 frame.source.setPosition(position); performs a masking filter to only show the blue ball as illustrated in 22 } Figure 11. Next, in Listing 13 we create a custom processing node 23 resolve(frame); 24 }); that sets the position of our tracked object to the pixel position 25 } of the blob. As the accuracy for our position we take the square 26 } root of the blob area. A reference space is created (lines 1 to 4 in Listing 14) and applied to the output position (pixel coordinate) on Listing 13: Contour detection processing node line 25 to scale it to the corresponding rectangle dimensions. Without interference from other sources, the video processing 4.4.4 Dead Reckoning Position. Apart from an internally calculated provides the output shown in Figure 10d. We will use this source position, the Sphero provides raw sensor data for the accelerometer, as our most accurate position, as it is the only available external gyroscope, orientation and velocity (internally fused from the motor positioning method. velocity and acceleration). For the scope of this demonstration we make use of this velocity and orientation to compute the position 15 https://support.sphero.com/article/6drb2qggx4-sphero-mini-faq using OpenHPS. The output of this source is shown in Figure 10c. Maxim Van de Wynckel and Beat Signer /* @openhps/core | version 0.2.0 */ /* @openhps/core | version 0.2.0 */ 1 const videoSpace = new ReferenceSpace(defaultSpace) 1 ModelBuilder.create() 2 .translation(1040, 800) 2 .addNode(new WorkerNode("video.ts", { 3 .rotation(new Euler(180, 180, 0, 'ZXY', AngleUnit.DEGREE)) 3 poolSize: 1, 4 .scale(4, 4); 4 name: "video" 5 /* ... */ 5 })) 6 export default GraphBuilder.create() 6 .addShape(inputSource) 7 .from(new VideoSource(new CameraObject("sphero_video"), { 7 .addShape(spheroPosition) 8 autoPlay: true, 8 .addShape(spheroVelocity) 9 fps: 30, 9 // Feedback loop 10 // Do not fetch a frame if the webcam can not handle it 10 .addShape(GraphBuilder.create() 11 throttleRead: true, 11 .from("merged") 12 source: new CameraObject("sphero_video") 12 .debounce(10, TimeUnit.MILLISECOND) 13 }).load("/dev/video2")) 13 // Clone the frame and update timestamp 14 .via(new ImageTransformNode({ 14 // (needed to process velocity) 15 src: [ 15 .clone({ 16 new OpenCV.Point2(307, 120), 16 repack: true 17 new OpenCV.Point2(1473, 87), 17 }) 18 new OpenCV.Point2(1899, 891), 18 .via(new VelocityProcessingNode()) 19 new OpenCV.Point2(20, 1024), 19 .to("feedback")) 20 ], 20 .addShape(GraphBuilder.create() 21 height: 800, // 200cm 21 .from("video", "sphero_position", "input", 22 width: 1040 // 260cm 22 "sphero_velocity", "feedback") 23 })) 23 .merge((frame, options) => options.sourceNode, 24 .via(new ColorMaskProcessing({ 24 { 25 minRange: [90, 50, 50], 25 timeout: 20, 26 maxRange: [140, 255, 255] 26 timeoutUnit: TimeUnit.MILLISECOND, 27 })) 27 // Minimum two sources, else the feedback 28 .via(new ContourDetectionNode()) 28 // loop will continue 29 .convertFromSpace(videoSpace) 29 minCount: 2, 30 .to(); 30 objectFilter: obj => obj.uid === 'sphero', 31 }) 32 .via("merged") // Feedback loop Listing 14: Graph shape video 33 .to(new CSVDataSink("position.csv", [ 34 { id: "timestamp", title: "timestamp" }, 35 { id: "x", title: "x" }, 36 { id: "y", title: "y" }, 4.4.5 Model Creation. In Listing 15 we combine the four graph 37 ], (frame: DataFrame) => { 38 return { shapes for our video output, internal position, input and dead reck- 39 timestamp: frame.createdTimestamp, oned position. We use a built-in object merging node (lines 22 to 30) 40 x: frame.source.getPosition().toVector3().x, that merges frames where the source UID is equal to “sphero”. The 41 y: frame.source.getPosition().toVector3().y, 42 }; merge node will wait until all of its incoming edges pushed a frame, 43 }))) or the timeout of 20 ms has been reached. By default, this merge 44 .build().then(model => { will use the weighted average of all incoming positions, velocities 45 // Model created 46 }); and orientations (with the weight being the inverse of its accuracy). Developers have the choice to choose their own strategy by, for instance, selecting a single position based on the highest accuracy. Listing 15: Demonstration model creation This final fused position is presented in Figure 12a. Compared to the individual positioning methods shown in Figure 10, we have processing was still able to detect an object, whereas the positions more data points for our positions. This is because we do not wait calculated without input from the video source are highlighted in for all sources to provide data before computing the next position red in the figures. (20 𝑚𝑠 timeout). Our feedback loop called “feedback” ensures that position fusion never relies on just one source. Source(s) Avg error Max error all sources (Fig. 12a) 0.00 cm 0.00 cm 4.4.6 Evaluation. We have shown our completed positioning sys- input control only (Fig. 10a) 23.07 cm 50.06 cm tem in the previous section. Four sources and a feedback loop internal position only (Fig. 10b) 16.16 cm 33.38 cm resulted in a fused position. In order to evaluate this positioning dead reckoning only (Fig. 10c) 17.09 cm 34.44 cm model, we removed parts of our video source to simulate an obstacle video source only (Fig. 10d) 1.30 cm 4.74 cm or blind spots for the camera. all sources excl. video (Fig. 12b) 13.59 cm 29.73 cm The goal of this evaluation is to first ensure that the positioning blind spot left (Fig. 12c) 4.26 cm 21.65 cm model can function with missing information and to determine the blind spot right (Fig. 12d) 4.81 cm 24.40 cm error as a result of this missing positioning data. To illustrate a baseline of the remaining sources that will take Table 2: Average and maximum XY position error compared over the positioning, we show the merged position of all sources to the fused position with all sources except the video source in Figure 12b. Figures 12c and 12d show two examples with video blind spots In Table 2, we show the average and maximum position error (grey areas). Indicated in blue are the data points where the video compared to the final fused position from Figure 12a. This error is OpenHPS: An Open Source Hybrid Positioning System 200 200 175 175 150 150 Y-Coordinate (cm) Y-Coordinate (cm) 125 125 100 100 75 75 50 50 25 25 0 0 0 50 100 150 200 250 0 50 100 150 200 250 X-Coordinate (cm) X-Coordinate (cm) (a) Fused position using all sources (b) Fused position without video source all sources expected all sources expected 200 excl. video blind spot 200 excl. video blind spot 175 175 150 150 Y-Coordinate (cm) Y-Coordinate (cm) 125 125 100 100 75 75 50 50 25 25 0 0 0 50 100 150 200 250 0 50 100 150 200 250 X-Coordinate (cm) X-Coordinate (cm) (c) Fused position with camera blind spot on the left (d) Fused position with camera blind spot on the right Figure 12: Fused positions processed by our model determined by taking 100 timestamped key points in each trajectory With the evaluation in Figure 12 and Table 2 we have proven that (every 51 ms) and calculating the average and maximum difference multiple producers of sensor information can be merged together for those points. into a continuous stream of fused positions. By creating blind spots Our results show that the video source is the main positioning in our video source, we have shown that the model is capable of method in the fused position. Blind spots in this source result in running without our main visual positioning method. the model falling back to the remaining dead reckoning. However, the positioning model is self correcting and will gradually align with the video source position once it becomes available. 5 CONCLUSION AND FUTURE WORK The positioning model we illustrated in Figure 9 is highly adapt- We have presented OpenHPS, an open source hybrid positioning able depending on the desired outcome. For example, noise filtering system. We focused on the different actors of our system that have nodes such as a Simple Moving Average (SMA) can be used on the been defined based on an investigation of some of the more promi- video accuracy to provide a smoother transition at the border of nent existing positioning methods and algorithms. These actors, the blind spot. in combination with our requirements, were used in developing Maxim Van de Wynckel and Beat Signer our positioning framework with its graph topology. We further [5] Gary Bradski. 2000. The OpenCV Library. Dr. Dobb’s Journal of Software Tools presented our definition of nodes, data frames, data objects as well (November 2000). https://www.drdobbs.com/open-source/the-opencv-library/ 184404319# as positions. Finally, the OpenHPS implementation in TypeScript [6] Nirupama Bulusu, John Heidemann, and Deborah Estrin. 2000. GPS-less Low- highlighting how we addressed and satisfied our non-functional Cost Outdoor Localization for Very Small Devices. IEEE Personal Communications 7, 5 (October 2000). https://doi.org/10.1109/98.878533 requirements, has been discussed in Section 4.3. [7] Harry Chen, Tim Finin, and Anupam Joshi. 2003. An Ontology for Context-aware In the demonstrator application in Section 4.4, we have illustrated Pervasive Computing Environments. The Knowledge Engineering Review 18, 3 how multiple positioning methods can be fused via some high-level (September 2003). https://doi.org/10.1017/S0269888904000025 [8] Zhenghua Chen, Han Zou, Hao Jiang, Qingchang Zhu, Yeng Soh, and Lihua Xie. decision fusion. We have further highlighted—by removing certain 2015. Fusion of WiFi, Smartphone Sensors and Landmarks Using the Kalman parts of our main sensor source—how the presented positioning Filter for Indoor Localization. Sensors 15, 1 (January 2015). https://doi.org/10. model continues to work on the remaining positioning methods 3390/s150100715 [9] Adam L. Davis. 2019. Akka Streams. In Reactive Streams in Java. https://doi.org/ and manages to recover once the input from the main sensor source 10.1007/978-1-4842-4176-9_6 is back. [10] Mansfield E. de Jong J. 2014. Math.js: An Advanced Mathematics Library for JavaScript. Computing in Science & Engineering 20, 1 (January 2014). https: A major effort in the design and development of OpenHPS went //doi.org/10.1109/MCSE.2018.011111122 into the extensibility of our framework. External modules can be [11] B. Louis Decker. 1986. World Geodetic System 1984. In Proceedings to the Fourth used to extend OpenHPS with additional positioning methods and International Geodetic Symposium on Satellite Positioning. Austin, USA. [12] Cristiano di Flora, Massimo Ficco, Stefano Russo, and Vincenzo Vecchio. 2005. techniques. Some basic positioning methods are currently included Indoor and Outdoor Location Based Services for Portable Wireless Devices. In in the core OpenHPS component. However, in order to prevent that International Workshop on Services and Infrastructure for Ubiquitous and Mobile the core contains potentially unused nodes, in the future some of Internet. Columbus, USA. https://doi.org/10.1109/ICDCSW.2005.77 [13] Goran M. Djuknic and Robert E. Richton. 2001. Geolocation and Assisted GPS. these basic positioning methods and algorithms might be moved to Computer 34, 2 (February 2001). https://doi.org/10.1109/2.901174 their own dedicated modules (e.g. for fingerprinting techniques). [14] Wilfried Elmenreich. 2002. An Introduction to Sensor Fusion. Technical Report 47/2001. Vienna University of Technology. Apart from individual nodes, these modules can also provide com- [15] Massimo Ficco and Stefano Russo. 2009. A Hybrid Positioning System for plete graph shapes that act similar to position providers in other Technology-independent Location-aware Computing. Software: Practice and high-level hybrid positioning systems. Experience 39, 13 (September 2009). https://doi.org/10.1002/spe.919 [16] Marc Geilen and Twan Basten. 2004. Reactive Process Networks. In Proceedings of The real-time processing of positioning information was the EMSOFT 2004, International Conference on Embedded Software. Pisa, Italy. https: most important goal for the presented OpenHPS framework. During //doi.org/10.1145/1017753.1017778 the development, the computing performance of the positioning [17] Yanying Gu, Anthony Lo, and Ignas Niemegeers. 2009. A Survey of Indoor Positioning Systems for Wireless Personal Networks. IEEE Communications model has therefore always received a high priority and lead to Surveys & Tutorials 11, 1 (2009). https://doi.org/10.1109/SURV.2009.090103 the introduction of worker nodes and services. Future research [18] Janne Haverinen. 2014. Utilizing Magnetic Field Based Navigation. US Patent 8,798,924. and development of the OpenHPS hybrid positioning system might [19] Jeffrey Hightower and Gaetano Borriello. 2001. Location Systems for Ubiquitous focus on optimising the serialisation of data frames in order to only Computing. Computer 34, 8 (August 2001). https://doi.org/10.1109/2.940014 serialise changes in data rather than all available information. This [20] Fabian Hölzke, Johann-P. Wolff, and Christian Haubelt. 2019. Improving Pedes- trian Dead Reckoning Using Likely Paths and Backtracking for Mobile Devices. optimisation would ensure that data transfers are limited to new In Proceedings of PerLS 2019, International Workshop on Pervasive Smart Living data only. Spaces. Kyoto, Japan. https://doi.org/10.1109/PERCOMW.2019.8730734 Overall, the presented OpenHPS framework represents a solid [21] Urs Hunkeler, Hong Linh Truong, and Andy Stanford-Clark. 2008. MQTT-S: A Publish/Subscribe Protocol for Wireless Sensor Networks. In Proceedings of the hybrid positioning solution offering various possibilities for future International ICST Workshop on Intelligent Networks: Adaptation, Communication extensions. An obvious future extension would be the introduc- & Reconfiguration. Bangalore, India. https://doi.org/10.1109/COMSWA.2008. 4554519 tion of additional layers of abstraction providing similar high-level [22] Brandon Jones and Nell Waliczek. 2020. WebXR Device API. https://www.w3. functionality as offered by some of the solutions discussed in the org/TR/webxr/ related work. Further, the exiting reference spaces might be ex- [23] John Krumm, Steve Harris, Brian Meyers, Barry Brumitt, Michael Hale, and Steve Shafer. 2000. Multi-Camera Multi-Person Tracking for EasyLiving. In tended in a separate OpenHPS module in order to represent and Proceedings of VS 2000, International Workshop on Visual Surveillance. Dublin, deal with symbolic locations, similar as offered by HyLocSys [15]. Ireland. https://doi.org/10.1109/VS.2000.856852 The support of symbolic locations [19] will further strengthen the [24] Axel Küpper. 2005. Location-based Services: Fundamentals and Operation. John Wiley & Sons. position of OpenHPS as a framework for context-aware computing [25] Edward A. Lee and Thomas M. Parks. 1995. Dataflow Process Networks. Proc. and implicit human-computer interaction. IEEE 83, 5 (May 1995), 773–801. https://doi.org/10.1109/5.381846 [26] Hui Liu, Houshang Darabi, Pat Banerjee, and Jing Liu. 2007. Survey of Wireless Indoor Positioning Techniques and Systems. IEEE Transactions on Systems, Man, REFERENCES and Cybernetics 37, 6 (2007). https://doi.org/10.1109/TSMCC.2007.905750 [1] Martín Abadi et al. 2016. TensorFlow: A System for Large-scale Machine Learning. [27] Blair Maclntyre and Trevor F. Smith. 2018. Thoughts on the Future of WebXR In Proceedinsg od USENIX 2016, International Conference on Operating Systems and the Immersive Web. In Proceedings of International Workshop on Creativity Design and Implementation. Savannah, USA. in Design with & for Mixed Reality. Munich, Germany. https://doi.org/10.1109/ [2] Sean J. Barbeau, Miguel A. Labrador, Philip L. Winters, Rafael Pérez, and ISMAR-Adjunct.2018.00099 Nevine Labib Georggi. 2008. Location API 2.0 for J2ME: A New Standard in [28] Ellon Mendes, Pierrick Koch, and Simon Lacroix. 2016. ICP-based Pose-Graph Location for Java-enabled Mobile Phones. Computer Communications 31, 6 (April SLAM. In Proceedings of SSRR 2016, International Symposium on Safety, Security, 2008). https://doi.org/10.1016/j.comcom.2008.01.045 and Rescue Robotics. Lausanne, Switzerland. https://doi.org/10.1109/SSRR.2016. [3] Stephane Beauregard and Harald Haas. 2006. Pedestrian Dead Reckoning: A Basis 7784298 for Personal Positioning. In Proceedings of WPNC 2006, Workshop on Positioning, [29] Piotr Mirowski, Tin Kam Ho, Saehoon Yi, and Michael MacDonald. 2013. Navigation and Communication. Merida City, Mexico. https://doi.org/10.1109/ SignalSLAM: Simultaneous Localization and Mapping with Mixed WiFi, ICEEE.2011.6106608 Bluetooth, LTE and Magnetic Signals. In Proceedings of IPIN 2013, International [4] Anja Bekkelien and Michel Deriaz. 2012. Hybrid Positioning Framework for Conference on Indoor Positioning and Indoor Navigation. Montbeliard-Belfort, Mobile Devices. In Proceedings of UPINLBS 2012, International Conference on France. https://doi.org/10.1109/IPIN.2013.6817853 Ubiquitous Positioning, Indoor Navigation, and Location Based Service. Helsinki, [30] Sudeep Pasricha, Viney Ugave, Charles W Anderson, and Qi Han. 2015. LearnLoc: Finland. https://doi.org/10.1109/UPINLBS.2012.6409759 A Framework for Smart Indoor Localization with Embedded Mobile Devices. OpenHPS: An Open Source Hybrid Positioning System In Proceedings of CODES 2015, International Conference on Hardware/Software https://doi.org/10.1109/TCST.2006.886439 Codesign and System Synthesis. Amsterdam, Netherlands. https://doi.org/10. [36] Philipp M. Scholl, Stefan Kohlbrecher, Vinay Sachidananda, and Kristof Van Laer- 1109/CODESISSS.2015.7331366 hoven. 2012. Fast Indoor Radio-Map Building for RSSI-based Localization Systems. [31] Andrei Popescu. 2016. Geolocation API Specification 2nd Edition. https: In Proceedings INSS 2012, International Conference on Networked Sensing. Antwerp, //www.w3.org/TR/geolocation-API/ Belgium. https://doi.org/10.1109/INSS.2012.6240574 [32] Morgan Quigley, Ken Conley, Brian Gerkey, Josh Faust, Tully Foote, Jeremy Leibs, [37] Stefan Steiniger, Moritz Neun, and Alistair Edwardes. 2006. Foundations of Rob Wheeler, and Andrew Y Ng. 2009. ROS: An Open-Source Robot Operating Location Based Services. System. In Proceedings of the International Workshop on Open Source Software. [38] Shinya Sumikura, Mikiya Shibuya, and Ken Sakurada. 2019. OpenVSLAM: A Kobe, Japan. Versatile Visual SLAM Framework. In Proceedings of MM 2019, International [33] Shahram Rezaei and Raja Sengupta. 2007. Kalman Filter-based Integration of Conference on Multimedia. Nice, France. https://doi.org/10.1145/3343031.3350539 DGPS and Vehicle Sensors for Localization. IEEE Transactions on Control Systems [39] Wendong Xiao, Wei Ni, and Yue Khing Toh. 2011. Integrated Wi-Fi Finger- Technology 15, 6 (October 2007). https://doi.org/10.1109/TCST.2006.886439 printing and Inertial Sensing for Indoor Positioning. In Proceedings of IPIN 2011, [34] Wilson Sakpere, Michael Adeyeye-Oshin, and Nhlanhla B.W. Mlitwa. 2017. A International Conference on Indoor Positioning and Indoor Navigation. Guimaraes, State-of-the-Art Survey of Indoor Positioning and Navigation Systems and Portugal. https://doi.org/10.1109/IPIN.2011.6071921 Technologies. South African Computer Journal 29, 3 (December 2017). https: [40] Esteban Zimányi, Mahmoud Sakr, Arthur Lesuisse, and Mohamed Bakli. 2019. //doi.org/10.18489/sacj.v29i3.452 MobilityDB: A Mainstream Moving Object Database System. In Proceedings of [35] Albrecht Schmidt, Michael Beigl, and Hans-Werner Gellersen. 1999. There is SSTD 2019, International Symposium on Spatial and Temporal Databases. Vienna, More to Context Than Location. Computers & Graphics 23, 6 (December 1999). Austria. https://doi.org/10.1145/3340964.3340991