\section*{Acknowledgements}

This work was supported by the Academy of Finland's AutoSOS project with grant number 328755. This project has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 751615.

\bibliographystyle{IEEEtran}

\section{Introduction}

\begin{figure}
    \centering
    \includegraphics[width=0.48\textwidth]{fig_new/security_in_robotics_process_v5.pdf}
    \caption{Classification of data acquisition and analysis processes in autonomous robots and matching security layers.}
    \label{fig:concept}
\end{figure}

With robots and autonomous robots having an increasing penetration across multiple aspects of our society, more attention is being paid to the safety and security aspects in robotic operation~\cite{kirschgens2018robot}. The differentiation between safety and security often becomes fuzzy, with the safety term being utilized to refer to human-robot interaction~\cite{bragancca2019brief}, or to the safety of the robot itself~\cite{huang2014rosrv}. In either case, safe operation of an autonomous robot requires tight control over the security of the data being used, from data defining mission instructions to sensor data. Figure~\ref{fig:concept} shows a layered classification of stages in which information is either collected or processed by an autonomous robotic system. This figure extends the cyberattacks categorization in~\cite{clark2017cybersecurity}, and also takes into consideration that the internal processes can be modeled as a software-defined network from a more abstract point of view~\cite{akhunzada2015securing}. Many robotic frameworks, such as the Robot Operating System (ROS) fall into this consideration~\cite{rivera2019ros}. From the cybersecurity domain point of view, the acquired sensor data needs to be secured as well. This represents an additional challenge. Therefore, an essential aspect in the operation of autonomous robots is to be able to validate both data being shared among subsystems and external systems (a controller or other robots), but also data defining or characterizing the way the robot, seen as a cyber-physical system, interacts with its environment.

A relevant precedent in securing multi-robot cooperation was introduced by Castelló Ferrer et al. in~\cite{ferrer2019secure}, where the authors leveraged Merkle trees to cope with byzantine robots in cooperative missions within swarms of robots. The main novelty of their work is the introduction of a framework for validating data in robots without relying on the data itself, by encoding mission instructions in Merkle trees. Merkle trees are cryptographic structures that enable validation of data through cryptographic proofs that do not involve the data itself.

We aim at extending previous works into a more general framework focusing on encoding not only of mission instructions but also on the relationship between the possible ways in which a mission can be completed. In~\cite{ferrer2019secure}, one of the main research questions is whether it is possible to provide the ``blueprint'' of a robotic mission without describing the mission itself. In this paper, we delve into the possibilities and limitations of encoding instructions, exploring different application scenarios and developing more specific ways in which this idea can be integrated into real robotic missions.
Here, we go beyond separating data verification from the data itself, towards defining new implicit ways for defining complex robotic workflows. We first describe the framework and the different possibilities, from human-robot interaction to collaborative robots, and then provide a proof of concept with navigation instructions. This proof of concept demonstrates that traditional robot behavior can be maintained with minimal impact on robustness and applicability even when providing full mission codification, opening the door to more secure and safe deployment of autonomous robots.

Summarizing the previous considerations, we have found an unexplored research gap in robust data validation schemes for autonomous or semi-autonomous robots. The main research questions that we find so far unanswered extend the work in~\cite{ferrer2019secure} towards broader data validation in autonomous robots:

\begin{itemize}
    \item Is it possible for a robot to safely and securely interact with its environment, operators or other robots in a way that it has zero a priori knowledge of the mission itself;
    \item can encoded information revealing no explicit mission instructions maintain the level of efficiency and applicability of current robotic workflows; and, finally,
    \item can these encoded mission instructions be utilized to simultaneously validate their integrity but also the progress of the mission, together with local information such as sensor inputs and operation of actuators.

\end{itemize}

The first of the above questions applies to a wide variety of situations. For instance, whether a robot in a factory can be given assembly instructions that it cannot understand until the assembly process starts, or whether a robot can be given a map that it can only understand when it starts to navigate its environment. An even more interesting situation occurs when a robot can interact with a human or another robot in a predefined way only when a series of conditions are met. The latter two questions extend the same concept towards more concrete aspects: whether these encoded instructions can be adapted to current robotic algorithms and workflows, extending previous works relying on random movement, and, finally, whether instructions understood by the robots can, \textit{simultaneously}, validate that all processes are working properly. Thus, we are asking whether a single framework can define both end-to-end data validation and define encoded instructions that enable a robot to securely and safely interact with its environment.

These considerations cover the validation of a robot's operation from end to end: from validating sensor data and the correct operation of actuators to validating mission instructions and information received from an external controller. In our experiments, we consider a navigation or exploration mission where a priori information (features) about the environment is available to the mission controller or robot operator (operator hereinafter). In this scheme, an operator generates a set of encoded instructions by hashing the description of a set of landmarks (waypoints) in the environment. The set of encoded landmarks is then given for autonomous robots which utilize them to navigate the objective environment with zero a priori knowledge of it. The encoded landmarks are given to the robots in the form of a navigation graph which also includes information about how to navigate between consecutive landmarks. Because all information is encoded, we minimize the amount of raw data a priori exposed at the robots.

The main contributions of this work are

\begin{enumerate}
    \item the definition of an end-to-end validation framework for autonomous robots based on encoded instruction graphs;
    \item the introduction of a novel approach that encodes a navigation graph utilizing cryptographic hashes to encode environment features, and
    \item the definition of a set of methods that allow robots to follow encoded mission instructions while validating their sensor data without external feedback.
\end{enumerate}

The remainder of this paper is organized as follows. In Section~II, we overview previous works that address security issues in robotic systems. Section~III then introduces the proposed framework,
and describes different use cases
From Section~IV onward, we delve into a proof of concept
for robotic navigation. In that direction, Section~IV introduces the implementation details for an encoded navigation graph,
with Section~V presenting the methodology we have followed in our simulations and experiments. Section~VI describes the experimental results. Finally, Section~VII concludes the work and outlines future research directions.

\section{Background}

There has been a growing interest in securing robotic systems, partly owing to the increased connectivity with which robots are equipped. This is partly due to an increasing amount of data exchange modalities with new attack vectors in remote control commands~\cite{liu2005ibotguard}, telemetry~\cite{rodday2016exploring}, offloading computation~\cite{queralta2020enhancing, wan2016cloud}, robot-to-robot communication~\cite{ferrer2019secure, queralta2020blockchain}, and human-robot interaction~\cite{miller2018social}.

Multiple research efforts have been devoted to studying cybersecurity issues in robotics. In~\cite{clark2017cybersecurity}, Clark et al. review and discuss the main security threads to robotic systems, from spoofing sensor data to denial of service attacks, and including other typical vector attacks such as malicious code injection or signal interference. However, this analysis only takes into account the security aspect in robotics from the cybernetic point of view, without considering the physical dimensions in which robots operate. The interaction of a robot with its environment presents key issues that cannot be addressed with traditional risk mitigation techniques from the cybersecurity domain. An early work in this direction was presented by Py et al. in 2004~\cite{py2004dependable}, where the authors introduced an execution control framework for autonomous robots that would analyze the data obtained from the behavior of the robot through a \textit{state checker}. A more recent work taking into account the nature of robotic operations was presented by Tang et al.~\cite{tang2018event}, where sensor data was estimated through a denial of service attack. Similarly, in~\cite{tiku2019overcoming}, Tiku et al. introduced a methodology for overcoming security vulnerabilities in a deep learning localization method by introducing adversarial training samples.
All these approaches, however, take the point of view of data security in information systems and do not explicitly involve the cyber-physical nature of autonomous robots and their interaction with the environment, which is the objective of this paper. In terms of distributed and multi-robot systems, most efforts have been directed towards the analysis and mitigation of security issues from a networking perspective~\cite{rahman2019evaluation}.

From the point of view of data validation, Legashev et al. described an approach for monitoring, certification, and validation of the operation of autonomous robots~\cite{legashev201monitoring}. The authors' aim was to define a generic framework from a legislative approach, relying on periodic telemetry data obtained from autonomous robots and, in particular, autonomous vehicles.
The framework focuses on validating the robot's operation but not the data itself. The only method available to validate the data itself in this work is through statistical analysis and detection of statistical abnormalities. Data integrity was also the objective of Yousef's \textit{et al} study on cyber-physical threats on robotic platforms~\cite{yousef2018analyzing}.

In general, we see a research gap in terms of addressing the physical dimension in robotic operation from a security and safety point of view. This becomes even more evident when analyzing the most widely used robotic frameworks. Among them, the Robot Operating System (ROS) has become a standard across both industry and academia. Multiple researchers have studied the security flaws of ROS~\cite{demarinis2019scanning}, and proposed different approaches to address these issues~\cite{amini2018cryptoros}. Moreover, many of these are being mitigated in the newest version, ROS2~\cite{kim2018security}. However, these efforts are again directed at securing ROS as a distributed and networked system, and not from the point of view of a robotic framework meant for robots to interact with their environment. While it is highly important to provide security from the data flow point of view, we direct our efforts in this paper towards the gap in securing and validating the way robots are controlled and interact with their environment.

In this work, we focus on providing a framework for validating data integrity. Other types of cyberattacks such as denial of service attacks, in which the communication channels are congested, are not considered. Nonetheless, it is worth noting that our proposed approach can provide some benefits even in such situations. While the communication channel utilized to transmit the encoded commands to the robot might be known to an attacker, the sensor data or inputs triggering the different actions are unknown even to the robot itself, if multiple possibilities exist. Therefore, our framework also provides partial mitigation for other types of cyberattacks where the channel utilized to trigger a robot's actions might be disguised within the encoded instruction graph sent to the robot before the mission starts.

\section{Encoded Instruction Graphs}

In this section, we describe the main framework components and how it can be applied in different scenarios.

\subsection{Encoding Robotic Instructions}

We follow up on the instruction encryption ideas from~\cite{ferrer2019secure}, where missions instructions are given to a robot by encoding combinations of sensor inputs and a set of robot actions. %
We do not consider explicitly multi-robot cooperation but instead focus on describing robust options for encrypting and decrypting mission instructions. Moreover, we also evaluate the performance degradation inherent to encrypting data when compared to standard robotic operation, avoiding random behaviour. In order to do that, the first step is to not only encode a set of actions and features from sensor data, but also some other variable that enables a \textit{hash search}, a trial-and-error process in which a robot does not need to be able to reproduce a specific hash but instead can try multiple hashes until finding a match. An example of this is the addition of a spatial or temporal component. The second step is then to define not only a series of encoded actions but also encoded states, which can be defined based on a combination of variables (e.g., position, time, sensor data or other external inputs). By encoding both states and actions, we can then wrap the set of encoded information into a graph structure, such that the encoded information in an edge of the graph gives the robot information about how to arrive to a different state or process. We call this an encoded instructions graph. A sample encoded instructions graph is shown in Fig.~\ref{fig:sample}. In this graph, the initial instruction is encoded into a hash $H_1$, which the robot is able to decode by combining a certain predefined action with some sensor data. Most of the nodes in the graph represent states, with the majority of the nodes in this example being defined by a position and some sensor data. However, the information that nodes encode is not restrictive, as it can be both actions or states. The edges, however, should encode information that enable the robot to transit between nodes, and therefore should include some type of action or external input. An edge can also be empty, i.e., if the robot can gather enough information to decode a different node without any intermediate step. In the example in Fig.~\ref{fig:sample}, the initial node triggers an action by the robot whenever it is able to acquire some certain sensor data. It can then proceed to two different states in which it must to be able to reproduce both its position and sense a different variable. The encoded information in the second node, $H_2$, can then be decoded after a certain time, which can for example be used as a failsafe to go back to the initial state if the sensor data defining $H_3$ cannot be acquired in time. In practice, the robot is not aware of the type of information encoded in each hash, and must therefore perform a continuous trial and error process to try to reproduce the hashes by all the different means it has been preprogrammed for. In our experiments, we show that this process of trial-and-error has a mostly negligible impact compared to the computational cost of extracting features or processing sensor data in standard robotics algorithms. In any case, the process of deciding how to define the encoded instructions is not trivial, as they must be reproducible, while concise enough to avoid data mismatches.

An encoded instruction graph as described above is a directed graph. For a mission that has only one possible solution and where each step is followed by one and only one other step, then the graph is reduced to a path or linear graph. In many cases, the graph will be acyclic. This happens when there are multiple options to complete a mission, but once a set of steps is taken then the same ones cannot be taken again. For instance, in a manufacturing process, the order in which a set of parts are moved to a working bench might not matter, yet every part must be moved exactly once. In a general case, the graph can be arbitrarily complex and contain any number of cycles. For instance, a reconnaissance mission in which a robot has to navigate an objective area without any specific order could have multiple cycles. Higher mission control embedded at the robot should then be able to understand these more complex graphs and provide a planning strategy that is not directly sent by the mission controller. An example of this will be given in our experiments.

\subsection{Validation Modalities}

The proposed approach can be extended to multiple scenarios, as the encoded information cannot only be a set of predefined actions and features extracted from sensor data, but also other external inputs, variables defining the state of the robot, or even timing constraints. The possibility of utilizing external inputs is particularly interesting as it enables secure and secret multi-robot cooperation but also new ways of defining under which conditions human-robot interaction can happen. Since the inputs can already be encoded, the information exchanged between robots or utilized as external signals triggering robot actions can be defined in a way that they are totally meaningless and only usable when combined with other data. Therefore, if the data is spoofed or a third party gains access to this communication medium, no real data is actually compromised. Different possibilities for encoding and decoding instructions are shown in Fig.~\ref{fig:actions}, and described in more detail in the following subsections.

\subsubsection{Independent Validation}

The simplest approach is to encode mission instructions individually and independently. In this case, an encoded instruction set can be sent to the robot, similar to the approach followed in~\cite{ferrer2019secure} but where only the leaves of the Merkle tree would be sent. This set of instructions does not define a graph structure and does not represent the main interest of this paper. However, these instructions can be utilized as the root of an encoded instruction graph, or as a trigger for starting a parallel process at the robot.

An additional layer of security can be added by introducing time or spatial constraints.
Time constraints (e.g., introducing a timestamp in the hash) provide an extra layer of security against attacks that could spoof the encoded data and reproduce it later, even if the data itself cannot be decoded.
Similarly, spatial constraints can be added by including the robot's location in the hash. This, however,
only prevents the replication of the robot's behavior in other locations.

\subsubsection{Iterative Validation}

An iterative validation happens when a robot is able to validate its own actions. This particular modality will be the case studied in the next sections with the introduction of an encoded navigation graph.

Encoded instruction graphs defining an iterative validation process can contain different types of encoded data in their nodes and edges. For instance, sensor data can be encoded in the graph nodes, which serve the purpose of validating the process. Additionally, this sensor data can encode other information, such as positional information or time information that can be utilized as a part of the control loops at the robot. Then, the actual instruction for the robot to move towards the next step is encoded in the edge of the graph, which encodes both the data in the current node being validated and the action or actions that will enable the robot to decode the next node. An illustration of this process is shown in Fig.~\ref{fig:iterative}.

\begin{figure}
    \centering
    \includegraphics[width=0.48\textwidth]{fig_graphs/iterative_cr_v3.pdf}
    \caption{Illustration of an iterative validation process.}%
    \vspace{-1em}

    \label{fig:iterative}
\end{figure}

\subsubsection{Multi-Robot Simultaneous and Mutual Validation}

As we have mentioned earlier, one significant scenario where this validation framework can be applied is in multi-robot cooperative behavior. Complementing the ideas proposed in~\cite{ferrer2019secure}, we are now also able to break down a mission in two disjoint parts that can be given to two different robots. An example of this is shown in Fig.~\ref{fig:collaborative}, which illustrates a collaborative inspection process. Each encoded instruction is defined with the combination of different signals or parameters, or a subset of them. First, data triggering an action can be a set of features extracted by the robot from its own sensor data, but we can now also differentiate between sensing the environment and sensing the behavior of the other robot. Second, the two or more robots can also exchange messages in order to trigger each other's actions. These messages can be meaningless to both of them, and also include environment data for an extra layer of robustness.

\begin{figure}
    \centering
    \includegraphics[width=0.48\textwidth]{fig_graphs/collaborative_inspection_v3.pdf}
    \caption{Illustration of a collaborative inspection process where robots only have partial instructions.
    \label{fig:collaborative}
\end{figure}

\section{Problem Definition}

\section{Encoded Navigation Graph}
\label{section.EncodedNavigationGraph}

One of the most fundamental ways in which a robot interacts with its environment is by navigating it. Maps have long been utilized for autonomous navigation and exploration in mobile robots to increase the robustness of long-term autonomous operation~\cite{hilnbrand2019roadwaygeometries, sobreira2019mapmatching, qingqing2019multi}. Maps or landmarks provide robots means for localization in a known reference frame, while enabling the calibration and adjustment of on-board odometry and localization algorithms.

Landmark-based navigation has been successfully implemented in various mobile robots with quick response (QR) codes~\cite{andersen2013qrcalibration, zhang2015qrnavigation, nazemzadeh2017qrfusion} or other identifiable images\cite{zamir2010accurate, sattler2016efficient, thoma2019mapping}, wireless sensor networks~\cite{cheng2011wsn}, or ultra-wideband (UWB) markers~\cite{almansa2020autocalibration, shule2020uwbbased, song2019uwb}, among others including IMU fusion~\cite{nazemzadeh2017qrfusion}, or topological maps in for infrastructure-free navigation~\cite{gadd2015warehouse}. When utilizing landmarks that are already encoding certain information, such as QR codes or other text representations, is that additional information can be embedded into the landmarks. In an industrial scenario, this can be utilized to provide further instructions for robots~\cite{qin2017sorting}.

In order to analyze the viability of this idea and discuss the potential directions for solving the research questions defined in Section~I, we consider the most essential aspect of a robot's interaction with its environment: \textit{the navigation}. Therefore, we capsulize the research questions to more concrete considerations regarding the navigation of autonomous robots:

\begin{enumerate}
    \item Is it possible to provide a description of the environment (e.g., a map or a set of landmarks and how to travel between them) to an autonomous robot, in a way that the robot is unable to understand the map until it starts navigating, and such that it can only decode the information in that map if a series of conditions on how it sees its environment are met?
    \item Is there a way of defining navigation instructions for an autonomous robot such that any modification of those instructions automatically renders them unusable ensuring that if wrong sensor data is fed to the robot's controller, the instructions cannot be followed?
\end{enumerate}

\subsection{Encoded Graph Definition}

Rather than modeling a map of the objective exploration area and utilize it for navigation, we utilize a landmark-based navigation graph that encodes the position of the different landmarks and the navigable directions between landmarks. In this graph, each vertex represents one encoded position in the map, and each edge represents a straight or unique path between two positions. By unique we mean a path that might not be straight but such that the robot can realistically follow.
A sample map and the corresponding encoded navigation graph are illustrated in Figure \ref{fig:sample_map}. In this and latter sections, we utilize the following notation. A graph is an ordered pair $\mathcal{G}=(V, E)$, where $V$ represents a set of vertices, and $E$ represents a set of edges associated with two distinct vertices, i.e., a set of tuples $\{(V_i,V_j) \:|\: V_i,V_j \in V\}$. We consider a directed graph, were the order of these tuples matters.

The most straightforward approach to landmark encoding is to define the hash of a position given its coordinates $\vec{r}\in\mathbb{R}^3$. Thus we would define $H_i=H(\vec{r}_i)$.
In order to ensure that hashes will be reproducible, the coordinates need to be given in a coarse grid with a resolution that is dependent on the accuracy of the robots' onboard odometry.

If the environment is accessible a priori, elements can be installed that facilitate the localization of robots when they are nearby, such as QR codes, or Bluetooth/UWB beacons.
The QR codes contain hashed data and can encode additional information, for example, instructions for a robot to operate in a given room or area. An alternative approach is to utilize the environment geometry and topology. The coordinates of the features can still be utilized to define their hash without using a predefined grid. Rather than having a robot utilizing its own or near position to calculate the hash, it can calculate it based on the coordinates of a position that depends on the robot's current local environment.

\subsection{Deployment and Navigation}

We assume that the position where a robot is deployed is either known in an absolute reference frame, or utilized as a common reference in the robots' local coordinate system. If only local references are utilized, these must have a common orientation. The initial position is encoded with a hash but also known to robots.

In the encoded navigation graph, each edge in the graph is given two hashes, as the robots might reach these from different directions. Therefore, the adjacency matrix containing the edge hashes shown in Fig.~\ref{fig:sample_map} is not symmetric.
Only minimal information about the local environment required for navigation purposes needs to be stored at the robots. Odometry-only (map-free) navigation, when possible, would be preferred to minimize the amount of raw information that robots store.

The directions between features, or the initial position and near features, is encoded in a way that can be matched by robots on a basis of trying multiple possible directions until finding one that produces the corresponding hash. The edge hashes are calculated on a trial-and-error basis, and thus they can be defined with an arbitrary division of the $[0, 2\pi)$ interval. However, this decision must take into account the trade-off with the inherent computational overhead. Furthermore, not all the navigable directions are necessarily selected, and therefore the real topology of the objective environment can be, to some extent, hidden. In addition, multiple features can be selected within a single room or small area, but even if all detectable at the same time, a fully connected subgraph does not need to be generated within the navigation graph. In general terms, there is a trade-off between the number of actual connections between features that are encoded in the navigation graph, and the robustness of the navigation in the event of robots not being able to reproduce a certain subset of landmark hashes.

\subsection{Landmark-based Localization}

The accuracy of the feature's position directly affects the error tolerance for the odometry method utilized for navigation when no landmarks are detected. In order to cope with the odometry error, if it can be estimated then it can be taken into account to calculate the hashes from the position of landmarks, following a trial-and-error approach within a certain spatial area around the landmark. The number of trials that a robot needs to perform depends on the accuracy of the odometry method utilized, and the granularity of the grid utilized to define the position of the landmarks and calculate the hashes. Additionally, the possibility of the robot identifying a wrong landmark that is nearby must be taken into account. Therefore, there is a trade-off between accuracy and robustness with multiple factors to take into consideration.

\section{Methodology}

In order to test the feasibility of the encoded navigation approach presented in this paper, we have run a series of simulations and experiments. In these, we analyze the overhead and performance impact from calculating hashes and utilizing the encoded navigation graph. In all cases, we make the assumption that the environment is known to the mission controller. We have devised two types of application scenarios in which we test the proposed framework.

First, we consider an environment where only robots operate. In this case, we have simulated the interior of a building with empty rooms.  For
this scenario, we utilize a simulation environment, in which we encode geometric features in the navigation graph: doorways, corners and rooms. For the simulations, we consider a fully automated environment with no dynamic obstacles and known geometry. This can be applied, for instance, to logistic warehouses where only autonomous robots operate. It can also be applied to autonomous cleaning machines operating at night, or, in general, any scenario where the environment does not change significantly over time. In our simulations, the robot relies on a two-dimensional laser scanner for feature detection.

Second, we consider a real office setting with a dynamically changing environment, people moving in it and a wide variety of objects populating the different rooms. The experiments are carried out relying on visual markers that can be placed in multiple fixed locations. For
this application scenario, real experiments are carried out in an office environment with people and a variety of furniture across different rooms. Because of the large amount of desks, chairs and other equipment, detecting geometric features from the environment would render irreproducible hashes and multiple situations in which features can not be detected due to either objects or people blocking the field of view of sensors. To tackle this issue, we have utilized QR codes as markers to encode the landmark positional information.

\subsection{Simulation Environment}

The proposed encoding approach has been implemented within the Robot Operating System (ROS) in Python. ROS is the current de-facto standard for production-ready robot development~\cite{quigley2009ros, koubaa2017robot}. The simulations were carried out within the ROS/Stage environment. A TurtleBot 3 is simulated with a 2D lidar and wheel odometry. The robot is set to explore an indoor environment with a floorplan illustrated in Fig.~\ref{fig:simulation_results}\,(a). The environment is $40\times40\,m^2$, and the robot has a circular shape with a diameter of $0.35\,m$. The simulated environment contains 9 rooms with a single entrance and 6 more spaces and corridors in between. The starting exploration position of the robots is near the main door, in the bottom-left. The 2D lidar has a field of view of 270\textdegree~and produces 1080 samples (0.25\textdegree~resolution) in each scan, with a scan rate of 1\,Hz. This work presents a proof of concept, and therefore we do not study the effect that different odometry methods have in the exploratory mission. Instead, we utilize wheel odometry and vary its error to study the impact that the corresponding computational overhead has due to a larger number of hashes being calculated.

\begin{algorithm}[t]
    \kwCbk {
        \par
        \kwCal {
            \par
            $\textbf{F} = getF(data)$; \hfill \small{// Orientation-ordered $F$ set} \\
            $\textbf{F}_{cv} = getCv(\textbf{F}) \subseteq \textbf{F}$; \hfill \small{// Set of concave features} \\
            $\textbf{F}_{cc} = getCx(\textbf{F}) \subseteq \textbf{F}$; \hfill \small{// Set of convex  features}  \\
        }
        \kwDef {
            \par
            $\textbf{H} = []$; \hfill \small{// List of hashes}
        }
        \ForEach{$fp_i,\:fp_j\:\in\:\textbf{F}_{cv}$} {
            \If{$\Vert fp_i - fp_j \Vert < \delta_{dw}$} {
                $H.append(doorwayHash(fp_i, fp_j))$\;
            }
        }
        \ForEach{$fp_i\:\in\:\textbf{F}$} {
            \If{$ fp_{i+j}\in\textbf{F}_{cx}\:\:\forall j \in \{-1,0,1\} $} {
                $H.append(roomHash(fp_{i\text{-}1},fp_{i},fp_{i\text{+}1}))$\;
            }
        }
        \ForEach{$fp_i\:\in\:\textbf{F}_{cv}$} {
            \If{$isCorner(fp_i) \:\&\&\: notDoor(fp_i) $} {
                $H.append(cornerHash(fp_i))$\;
            }
        }
        \small{// Utilize any matching hashes to update the robot's} \\
        \small{// position with respect to the global reference frame} \\
        \If{$\exists\:h\in\:H\:\vert\:h\in\:NavGraph$} {
            $updateAbsolutePosition(H))$; \hfill \small{// Use matching hashes}
        }
    }
    \caption{Feature Extraction and Hash Calculation}
    \label{alg:features_and_hashes}
\end{algorithm}

\subsection*{Feature Extraction}

In the simulation experiments, we utilize three types of features to localize the robot and navigate the environment: doorways, concave corners and rooms. These are defined from the same set of $F$ feature points which we denote as Features of Interest $FoI = \{ fp_1, \dots, p = fp_F \}$, where $fp_i\in\mathbb{R}^3$. The feature extraction process is outlined in Algorithm \ref{alg:features_and_hashes}.
The $NavGraph$ variable stores a list of hashed positions as well as an adjacency matrix with the edge hashes. A sample of this is shown in  Fig.~\ref{fig:sample_map}, subfigures (c) and (d). The function $search()$ calculates a certain number of hashes over a predefined area around the identified feature until it either finds a matching hash from $NavGraph$ or ends the search unsuccessfully. This function ensures that the hashes are reproducible even if odometry error accumulates over the inter-landmark navigation. The search area is defined based on the expected odometry error as well as the granularity of the grid utilized to define the hashes. Finally, the function $updateAbsolutePosition()$ takes the matching hashes as arguments, calculates the relative position of the robot with respect to the landmarks that have been identified and utilizes the known position of the landmarks (which is encoded in the hashes) to recalculate its own position and restart the odometry estimation.

\vspace{0.12cm}
\subsubsection*{Doorways}
    We define doorways as any set of two concave feature points that are within two predefined distances $(\delta_{dw,min}, \delta_{dw,max})$ from each other. In our simulations and experiments, we set these distances to $\delta_{dw,min}=1.2\,m, \delta_{dw,max}=2.5\,m$. Note that these feature points might not be consecutive if we consider the ordered set of feature points by orientation.
    We define the corresponding waypoint to be encoded according to~\eqref{eq:door}:

    \begin{equation}
        H_{dw}(fp_i, fp_j)= H\left(\text{"doorway"},\frac{fp_{i}+fp_{j}}{2}, \angle fp_{i}fp_{j} \right)
        \label{eq:door}
    \end{equation}

\vspace{0.12cm}
\subsubsection*{Corners}

    For each concave corner not in a doorway, we define its corresponding hash with~\eqref{eq:corner}:

    \begin{equation}
        H_{cv}(fp_i)= H\left(\text{"corner"}, fp_{i}, \angle fp_{i}\right)
        \label{eq:corner}
    \end{equation}
    where $\angle$ represents the orientation of the normal vector to the wall surface at the position of the corner.

\vspace{0.12cm}
\subsubsection*{Rooms}

    A room waypoint is defined as the centroid of any three consecutive convex points, calculated as the arithmetic mean of their positions.

    To reduce the probability of having a mismatch in rectangular rooms where two consecutive subsets of three convex corners are visible by a robot, we add the area $\Delta$ of the triangle that the points define:

    \begin{multline}
        H_{dw}(fp_i, fp_{i+1}, fp_{i+2})= \\
        H\left(\text{"room"},\dfrac{fp_{i}+fp_{i+1}+fp_{i+2}}{3}, \Delta_{i,i+1,i+2} \right)
    \end{multline}

\subsection{Real-Robot Experimental Settings}

The experimental environment is shown in Fig.~\ref{fig:experiment_results}\,(a). For the experiments, an EAIBOT DashGo D1 has been utilized. We have installed a 16-Channel Leishen 3D Lidar, an SC-AHRS-100D2 IMU, and a Logitech c270 USB camera. The DashGo provides wheel odometry from its differential drive system. The 3D lidar is utilized to accurately localize the landmarks and provide ground truth odometry. The camera is utilized to detect the QR codes and extract the encoded information in them. Figure~\ref{fig:ros_nodes} show the implementation diagram with different ROS nodes. The 3D lidar odometry and mapping are adapted from the LeGo-LOAM-BOR package~\cite{legoloam2018}. The QR code decoding node has been written in Python using OpenCV and the Zbar library. The hash based localization node utilizes the QR codes for localization when available and the wheel and inertial odometry as an estimation between landmarks. The QR codes utilized during the experiment are of known size (12\,cm by 12\,cm), and the localization node has been calibrated to map the size in pixels of a detected QR code in the camera to the distance to it. The localization also takes into account the relative orientation of the QR code.

\begin{figure}
    \centering
    \includegraphics[width=.48\textwidth]{fig_new/ROS_Nodes_light_color.pdf}
    \caption{Data flow in the experiments. Each box represents a ROS Node which has been implemented either in C++ or Python. The outputs are the ground truth, odometry (odom) error and has-based localization error (loc. error).}
    \label{fig:ros_nodes}
\end{figure}

\subsection{Feature Hashing}

We utilize SHA3-256 for hashing~\cite{czajkowski2017quantum}, which generates 32~byte hashes. It takes an average of under 500~ns on an Intel(R) Core(TM) i5-6200U CPU with the pysha3 implementation in Python. If additional security is required against offline attacks on exposed hashes, other hashing algorithms such as Bcrypt~\cite{sriramya2015providing} can be utilized. Bcrypt needs around 300~ms to generate a hash with the same CPU. However, there is a trade-off between security and real-time operation as robots need to calculate multiple hashes per lidar scan. We believe that, in most applications, SHA3-256 is enough and can be utilized even in resource-constrained devices.

\begin{figure}
    \centering
    \includegraphics[width=0.42\textwidth,height=0.23\textwidth]{fig_new/sim_floorplan.pdf}
    \caption{Floorplan of the simulation environment. All doors, rooms and corners are utilized as encoded landmarks.}
    \label{fig:sim}
\end{figure}

\begin{figure*}
    \centering
    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \setlength\figureheight{0.6\textwidth}
        \setlength\figurewidth{\textwidth}
        \footnotesize{\input{fig/sm_paths_TEST121212.tex}}
        \caption{Ground truth and estimated path during simulation.}
    \end{subfigure}
    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \setlength\figureheight{0.6\textwidth}
        \setlength\figurewidth{\textwidth}
        \footnotesize{\input{fig/sm_errors_TEST121212.tex}}
        \caption{Localization error over the simulation time.}
    \end{subfigure}
    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \setlength\figureheight{0.6\textwidth}
        \setlength\figurewidth{\textwidth}
        \footnotesize{\input{fig/error_boxes.tex}}
        \caption{Odometry and hash-based localization error for different odometry noise levels.}
    \end{subfigure}
    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \setlength\figureheight{0.6\textwidth}
        \setlength\figurewidth{\textwidth}
        \footnotesize{\input{fig/time_boxes_log.tex}}
        \caption{Execution time of the different processes (feature extraction in red, hash search and matching in blue) for a varying grid size.}
    \end{subfigure}
    \caption{Simulation results. Subfigures (a) and (b) show the reconstructed path and errors, respectively, with ground truth (GT) wheel and inertial odometry (O), only doorway hashes (D), and all features: doors(D), rooms (R) and concave corners (CC). Subfigure (c) shows the odometry and hash-based localization errors for different odometry noise levels. Finally, (d) shows the execution time distribution for the feature extraction (red) and hash matching (blue) processes, where the grid size represents the search space when trying to find a hash match.}
    \label{fig:simulation_results}
\end{figure*}

\begin{figure}
    \centering
    \includegraphics[width=.42\textwidth, height=0.3\textwidth]{fig/3dmap_cr.png}
    \caption{3D point cloud of the experiment environment utilized as ground truth in our experiments. The path of the robot is shown with colored points, where red represents the start of the mission and purple the end.}
    \label{fig:my_label}
\end{figure}

\begin{figure*}

    \centering
    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \setlength\figureheight{0.6\textwidth}
        \setlength\figurewidth{\textwidth}
        \footnotesize{\input{exp/experiment_paths_xs_v2.tex}}
        \caption{Estimated path and ground truth during the experiment.}
    \end{subfigure}
    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \setlength\figureheight{0.6\textwidth}
        \setlength\figurewidth{\textwidth}
        \footnotesize{\input{exp/experiment_errors_xs.tex}}
        \caption{Localization error over time.}
    \end{subfigure}

    $ $ \\[+6pt]

    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \setlength\figureheight{0.6\textwidth}
        \setlength\figurewidth{\textwidth}
        \footnotesize{\input{exp/experiment_qr_errors_xs.tex}}
        \caption{Localization error when a QR code is in sight.}
    \end{subfigure}
    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \setlength\figureheight{0.6\textwidth}
        \setlength\figurewidth{\textwidth}
        \footnotesize{\input{exp/times.tex}}
        \caption{Execution time for the different processes.}
    \end{subfigure}

    \caption{Experiment results. Subfigures (a) and (b) show the reconstructed path and errors, respectively, with ground truth (GT), wheel and inertial odometry (Odom) and hash-based localization (Hash). In (c), we show a scatter plot with the localization error every time that a QR code is within the field of view of the camera. Finally, (d) shows the execution time for the QR code extraction when it is within field of view (QRV), for the QR code extraction process globally and independently on whether there is or not a QR code visible (QRG), for the hash matching algorithm when a QR code is within field of view (HQR), and for the hash matching algorithm over the global mission (HG).}
    \label{fig:experiment_results}

\end{figure*}

\section{Simulation and Experimental Results}

We have carried out a series of simulations with one and multiple robots to evaluate mainly the cost of utilizing hash matching for localization and navigation, but also the impact on accuracy of the encoded landmarks.

\subsection{Metrics}

In order to evaluate the simulation results, we measure the absolute localization error of the robot with odometry only and hash matching. Furthermore, we analyze the distribution of the computational load among the different tasks that the robots are carrying out: feature extraction, hash calculation and hash matching. In the simulations, we also measure the effect of the odometry-based localization noise and the choice of spatial granularity for landmark positions.

\subsection{Simulation Results}

The aim of the simulations is to prove whether our encoded landmark localization and navigation scheme is viable and adds a significant computational overhead or not.

Figure \ref{fig:simulation_results}\,(b) shows the path recovered from odometry measurements and hash-based localization with doorway hashes only, and all three types of hashes, together with the ground truth (GT). The data is recorded over 150\,s; the translation odometry noise is set with $\sigma_t=0.03$, and rotation noise with $\sigma_r=0.05$. The absolute error of each of these paths is given in Fig.~\ref{fig:simulation_results}\,(c). Because the doorway-type landmarks are predominant in the chosen simulation environment, the localization error does not decrease significantly when also considering rooms and concave corners.

In the simulated environment, we have predefined the position of landmarks with an accuracy of $0.1$\,m. Therefore, when analyzing the errors in Fig.~\ref{fig:simulation_results}\,(c) and Fig.~\ref{fig:simulation_results}\,(d), any values below $0.15$~m represent virtually zero error. Fig.~\ref{fig:simulation_results}\,(d) shows that the localization method is robust even when the odometry error increases significantly ($\sigma_t=0.05$). However, there is a limit, around $\sigma_t=0.06$, for which the size of the environment is big enough that the robot is unable to match landmark hashes due to odometry error. In order to calculate these hashes, we assume an error tolerance with respect to its estimated position of $\pm0.5$\,m, independently of the size of the grid utilized to locate the landmarks and generate the hashes.

Regarding the computational overhead necessary to calculate the hashes, estimate the robot's position, and perform path planning accordingly, Fig.~\ref{fig:simulation_results}\,(e) shows the distribution of computational time utilized to extract the set of features, or points of interest, from the raw lidar data and the distribution of computational time utilized in calculating and matching hashes. For an error tolerance of $\pm0.5$\,m, the graphic shows situations in which the robot tests up to 9, 25, 121, 441 and 1681 grid positions, respectively. The search for a hash match is gradually done in a spiral manner around the estimated position and within the aforementioned error tolerance. These results show that even with fine-grained grid search, in average the time required to localize the robot based on hashes is two orders of magnitude smaller than the time required to extract features from lidar data. In the worst-case scenario, the time required can be comparable, with an equivalent order of magnitude for both hash matching and feature extraction.

\subsection{Experiment Results}

Figure \ref{fig:experiment_results}\,(b) shows the path recovered from odometry measurements and hash-based localization (QR codes). The error in the odometry is significantly higher than in the simulation experiments due to a drift in the yaw measurements. However, the translational odometry error is much smaller. The hash-based localization is able to correct this orientation whenever a QR code is within the field of view, and therefore it does not suffer from the yaw drift. The maximum hash-based localization error that we observed was of 41.3\,cm. This allowed the utilization of a fine grid of 2\,cm for calculating the landmark hashes. We set a $1\,m^2$ hash search area around the estimated location which was enough in this case.

A total of 23\,QR codes were installed in the office environment, and the tests were done with a small number of persons in their offices. Out of those, 17\,QR codes were utilized by the robot during its navigation. The execution time of the hash matching algorithm was on average over one order of magnitude smaller than the time required to extract the QR codes from camera images. Thus, the overhead was mostly negligible. Only in a reduced number of occasions was the latency of these two processes comparable, as Fig.~\ref{fig:experiment_results}\,(e) shows.

\subsection{Viability and Usability}

We have seen that the computational overhead added when encoding landmarks is mostly negligible. Thus, our approach could be incorporated on top of many existing navigation and localization schemes, whether they are landmark-based or not, to increase the level of security if the error tolerance allows.

This approach has additional uses when more than one robot is taken into consideration. In multi-robot cooperation, different robots can share their plans, progress or position (based on the navigation graph only) with others by utilizing the same hashes or parts of them. This would reduce the possibility of raw data being exposed but also virtually eliminate the options for attackers or byzantine agents to affect the mission, as has been shown in~\cite{ferrer2019secure}.

\section{Discussion}

\section{Conclusion and Future Work}

Security and safety in robotics are crucial aspects to take into account with the current surge of autonomous robots penetrating multiple aspects of our society and the increasing interaction between robots, and between robots and humans. In this direction, further research needs to focus on the validation of data at the different layers of robotic systems, and in particular the validation of the interaction of a robot with its environment. This interaction often starts with navigation, which has been the main aspect studied in this paper.

Navigation and localization in autonomous robots require large amounts of raw data for long-term operation, either given a priori by a mission controller or acquired by robots while performing their missions. In addition, validating the integrity of both mission instructions and sensor data without any external feedback is an open problem. We have presented a framework that enables robots to validate both the correct operation of their onboard hardware and sensors, and the integrity of information received from an external controller.

In particular, to the best of our knowledge, this paper introduces and evaluates the first end-to-end validation framework that focuses on navigation and localization with encoded landmarks, which allows robots to effectively perform their missions while performing end-to-end validation of information. We have shown that utilizing an encoded navigation graph adds only a negligible computational overhead even when high-accuracy positioning is required.

The end-to-end validation scheme demonstrated in this work for navigation tasks can be naturally extended to cover virtually all domains of robotic operation. In future work, we will focus our research efforts towards experimentation in more relevant environments, and in particular industrial settings. We will aim at extending this approach to other interaction forms between a robot and its environment, from multi-robot collaborative assembly to human-robot interaction and control.


\section{Introduction}
\label{sec:intro}

\vspace{-5pt}
In recent years, many security cameras were deployed in public places such as streets, malls or airports. Today, most of these video streams are monitored in real-time by security agents, which is expensive and rather inefficient as the amount of videos to analyze is tremendous. In contrast, automated video analysis~\cite{hampapur2003smart} can process large amounts of videos simultaneously but is more prone to errors for complex tasks such as
person re-identification~\cite{ye2020deep}. In addition, even for automated video analysis systems, the final decision often rests with a human security agent, who triggers the appropriate actions. Hence, in practice it seems good to adopt hybrid approaches, where artificial intelligence models can screen the whole network in real time and select only relevant sequences for the monitoring agents.

In computer vision, the person Re-Identification (Re-ID) problem aims at searching a given person (query) in a network of non-overlapping cameras and raising an alert when this person appears in one of the video streams. It seeks to reproduce and enhance the human ability to recognize people in different scenarios, e.g. wearing different clothes,
in a different pose, etc.

The current formulation to address Re-ID (Fig.~\ref{fig:classic_reid}) is based on large databases of images representing human beings in a real-world environment~\cite{market, duke, cuhk, viper, prid}.
These images are usually extracted using pedestrian detection models~\cite{pedestrian_detection} and filtered manually to meet certain standards: each image should contain the entire body of exactly one person, centered and occupying most of the image. From these datasets, a given image is selected as the query and the others constitute the search gallery. Then, the objective is to look for the query person within the gallery \cite{ye2020deep}.
This approach is illustrated in Fig.~\ref{fig:classic_reid}. Sometimes, individual images are replaced by sequences of successive cropped images and the problem is called video-based Re-ID~\cite{PRL_videoBased, PRL_videoBased2}. From now on, the Re-ID setting considering pre-cropped images of persons as input is referred to as Classic Person Re-Identification (C-PRID). Recent successful methods to address C-PRID are mostly based on deep learning~\cite{Ejaz2015, Wang2018, Zheng2019, PRL_multiLevelAttention, PRL_ensemble_reid}.

\begin{figure}[ht]
\centering
\includegraphics[width=0.35\textwidth]{classicReID.png}
\caption{Illustration of the Classic Person Re-ID (C-PRID) setting.}
\label{fig:classic_reid}
\end{figure}

This formulation is a useful building block to implement security application of Re-ID, i.e. to identify a person sought by the authorities in a network of security cameras. However it is not sufficient, as for such a practical implementation, the entire image of the video frames must be used as input, instead of carefully selected pre-cropped images of persons. From now on, this application-oriented Re-ID setting is referred to as Full Frame Person Re-ID (FF-PRID).
In short, in the FF-PRID setting, a successful model must analyze full frames to determine if the query is present in the stream, and if it is, when and where it appeared. The FF-PRID setting is illustrated in Fig.~\ref{fig:realWorld_reid}.

\begin{figure}[ht]
\centering
\includegraphics[width=0.45\textwidth ]{reidFrameworkV2.png}
\caption{Illustration of the Full Frame Person Re-ID (FF-PRID) setting.}
\label{fig:realWorld_reid}
\end{figure}
\vspace{5pt}

One can argue that the C-PRID problem can be easily derived from the FF-PRID setting by applying a pedestrian detection~(PD) model~\cite{pedestrian_detection} on the raw video stream, which is often done in practice. Indeed, some object detection models have demonstrated strong results for detecting human beings over the last few years~\cite{ren2015faster, yolov3, pedestrian_detection2}. However, we argue that not considering the problem as a whole presents several issues:
\vspace{-5pt}
\begin{itemize}[leftmargin=*]
\setlength\itemsep{0.001em}
    \item The bounding boxes extracted by PD models may differ from the images in the reference datasets used for C-PRID training and evaluation, which have been filtered manually to only select clean images. This domain shift between the galleries used for training and the data encountered at inference time can decrease the quality of the model at run time, and thus induces a strong bias for model evaluation.

    \item Even if both a good pedestrian detection model and a good Re-ID model are used, their small prediction errors might add up to produce poor overall results for the final application.

    \item Not considering FF-PRID as an independent problem might dissuade the community from trying different approaches for the full application. Indeed, the vast availability of C-PRID datasets might take researchers away from trying other promising approaches such as end-to-end methods or video based methods, which have been shown to work for other computer vision problems~\cite{end2end_1, video_based_1}.

    \item When developing a practical application, it is crucial to evaluate the quality of the entire pipeline before deploying it in production. To the best of our knowledge, frameworks and metrics to evaluate FF-PRID are missing in the literature.
\end{itemize}{}
\vspace{-5pt}

The main contributions of this paper is to introduces a new setting of the person Re-ID problem, called FF-PRID, which is better suited to implement and evaluate real-world security applications. By formalizing the natural collaboration occurring between an automated Re-ID system and the monitoring agents, a hybrid framework to address the FF-PRID problem more robustly is proposed, as well as two complementary metrics to assess the quality of any FF-PRID pipeline. Then, experiments are conducted to demonstrate the importance of considering the FF-PRID problem in its entirety. The most natural pipeline for FF-PRID is implemented within the proposed framework, it consists in using a pedestrian detection model and a C-PRID model sequentially, with both models performing well on standard datasets for their respective tasks. This FF-PRID pipeline is then tested on a modified version of the PRID-2011 dataset~\cite{prid}, using the metrics introduced in this paper. Our experimental results demonstrate that this combination struggles to produce good results for the FF-PRID problem, despite the apparent success of its two independent components. This shows the importance of considering the person Re-ID problem in its Full Frame setting, using adapted metrics. This research does not claim to have solved the FF-PRID setting but rather to demonstrate that the current way of approaching Re-ID is not suited for practical scenarios. By proposing an alternative framework and evaluation method, we hope that this work will motivate the community to consider the FF-PRID setting, in order to develop algorithms that are better adapted for real-world scenarios.

\section{Human-Machine Hybrid Framework for FF-PRID}
\label{sec:reformulation}

The classic Re-ID formulation consists in comparing a query image with all the images of a search gallery to output a set of similarity scores representing the Re-ID predictions. Conversely, this paper considers the Full Frame Re-ID setting, which is better suited to implement and evaluate security applications. In practice, security application involving Re-ID are inherently human-machine collaboration tasks as the predictions made by a FF-PRID model are used by security agents to decide the actions to be taken. In this section, this interaction is formalized within a hybrid framework to increase robustness of FF-PRID pipelines. We also propose two new evaluation metrics to assess the quality of a FF-PRID model.

\subsection{Framework}
\label{sec:framework}
A FF-PRID system takes as input both a raw video and a query image. Studying this setting is paramount to design reliable Re-ID applications. In the ideal scenario, a FF-PRID model should make predictions for every single frame, and raise an alert as soon as the query is encountered. A monitoring agent can then analyze this alert and trigger appropriate actions. However, in practice FF-PRID for security applications is usually a critical task, which is complex and highly prone to errors. To address this issue, we propose to formalize the interaction occurring naturally between the Re-ID system and the monitoring agent. This way, by introducing user defined parameters to relax the ideal scenario, the amount of human work can be tuned to obtain the required robustness. The ideal case discussed above is a special case of the generic framework presented here.

The proposed framework goes as follows: First, the live video stream is cut into short video segments of $\tau$ frames. Then, a FF-PRID model processes each video segment, and outputs a set of cropped images of persons present in the video, as well as their corresponding similarity scores with respect to the query image. If the highest similarity score returned by the model is higher than a given threshold $\beta$, the $\eta$ members of the gallery with highest similarity scores are shown to the monitoring agent, who decides if the predictions are correct and triggers actions when necessary. An overview of this hybrid framework is shown in Figure~\ref{fig:ffprid-framework}. We underline  that the only assumption made regarding the FF-PRID model is about the shape of its inputs and outputs. A practical example of FF-PRID model is studied in our experiments (Section~\ref{sec:experiments}).

The threshold for raising an alert $\beta$, the number of images shown to the agent $\eta$ and the length of the video segments $\tau$ are user defined parameters that influence the final results. For any real-world implementation of Re-ID for city security, it is always required to tune $\beta$, independently of our proposed framework. The two additional parameters $\tau$ and $\eta$ were introduced because we acknowledged that in practice, the ideal scenario described above ($\tau=1$ and $\eta=1$) generates very poor results.

\begin{figure*}
\centering

\includegraphics[width=\textwidth ]{pipelineReID-security.png}
\caption{Hybrid Human-Machine FF-PRID Framework.}

\label{fig:ffprid-framework}
\end{figure*}

\subsection{Evaluation metric}

For a perfect FF-PRID model, the operator validation is required in all the cases where the query is present in the sequence of $\tau$~frames and not in any other case. Hence, there are two ways for a model to fail: by missing the query when it is present in the video segment or by calling the operator when the query is not present. Thus, to evaluate the quality of a model, we define two important indicators that we call \emph{Finding Rate} (FR) and \emph{True Validation Rate} (TVR). They respectively represent the number of sequences in which the query was found when it appeared and the number of times that the query was present when the operator was solicited.

To define FR and TVR formally, other variables must be introduced first. For a given $\{$query, video$\}$ pair, we define:
\vspace{-5pt}
\begin{itemize}[leftmargin=*]
\setlength\itemsep{0.001em}
    \item A True Call (TC), when the query is present in the video, the highest similarity score is greater than the threshold $\beta$ and the query is in the top $\eta$ best candidates. It corresponds to a successful case of re-identification by the system.
    \item a True Missed Call (TMC), when the query is present in the video, the highest similarity score is greater than $\beta$ and the query is not in the top $\eta$ best candidates. It is the case where the query is present, the system is asking for confirmation but does not provide the correct images to the operator and the query is missed anyways.
    \item a False Silence (FS), when the query is present in the video, but the highest similarity score is smaller than $\beta$. It is the case where the query is missed but the operator is not disturbed.
    \item a False Call (FC), when the query is not in the video but the highest similarity score is greater than $\beta$. It corresponds to the case where the operator is disturbed for nothing.
    \item a True Silence (TS), when the query is not in the video and the highest similarity score is smaller than $\beta$. It is the case where the query is not present and nothing happens.
\end{itemize}{}
Then, the proposed metrics can be defined as follows:
\begin{equation}
    FR = \frac{TC}{TC + TMC + FS},
\end{equation}{}
\begin{equation}
    TVR = \frac{TC}{TC + TMC + FC}.
\end{equation}{}
FR and TVR are comprised between 0 and 1. When FR~=~1, it means that whenever the query was present in the video, it was successfully identified by the hybrid system (model + operator). Likewise, TVR~=~1 means that the operator was never called unnecessarily, i.e. the query was present in the proposed images whenever the model asked for verification. In contrast, FR~$<$~1 means that in some sequences the query was missed, and TVR~$<$~1 means that validation was required in cases where the query was not among the suggestions.

\section{Proposed experiments}
\label{sec:experiments}

To demonstrate the importance of considering the FF-PRID setting when implementing Re-ID in real-world security applications, we implement a very natural FF-PRID pipeline and evaluate it under the proposed metrics.

\subsection{Dataset used for our experiments}

For these experiments, a modified version of the PRID-2011 dataset~\cite{prid} is used, considering full frame videos instead of the pre-cropped, manually filtered images of the original dataset.

The original PRID-2011 dataset is composed of images extracted from multiple person trajectories recorded from two different static surveillance cameras, named A and B. Images from these cameras contain a view point change and a stark difference in illumination and background. Since images are extracted from trajectories, several successive poses per person are available in each camera view, with some people appearing in both views.
After filtering out manually some heavily occluded persons, corrupted images induced by tracking and annotation errors, the official PRID-2011 dataset contains 385 persons in camera view A and 749 in camera view B. The persons with the first 200 labels appear in both views.

PRID-2011 was created to test classic Re-ID approaches, as well as video-based Re-ID~\cite{PRL_videoBased}. To conduct our experiments, we obtained the raw videos and annotations used to create the PRID-2011 dataset\footnote{We thank the authors of the PRID-2011 paper for their cooperation.}. From now on, the two raw full frame videos are called view~A (1:01:53 hours) and view~B (1:06:39 hours). Both views were cut into sub-videos of 2 minutes, to serve as input to the FF-PRID model (Section~\ref{sec:expe_model}). This way, view~A contains 30 videos and view~B contains 33.

For each 2 minute video sample, we generate a ground truth file\footnote{Our code (video processing script and baseline model implementation) is openly available at: \url{https://github.com/fsumari/FF-PRID-2020}.}, which contains containing for each person in the video: its identifier $Id$; the first frame where it appears $fr$; the number of frames in which it appears $s$ and the initial bounding box coordinates $(ulx, uly, brx, bry)$

\subsection{FF-PRID model used for our experiments}
\label{sec:expe_model}

The FF-PRID model used in our experiments is presented in Fig.~\ref{fig:pipeline-rw-reid-modified}. The input video is fed to an Object Detection (OD) model to detect pedestrians and generate clippings for the search gallery. Next, the query is searched in the gallery by means of a C-PRID model, returning a list of images, ordered from most to least similar to the query. Currently, this pipeline is to the most common approach to implementing a real-world application of Re-ID. Both the PD model and the C-PRID model were implemented using TensorFlow~1.14.0 and executed on a NVIDIA P5000 GPU. The implementation of these models is detailed in the following subsections.

\begin{figure*}
\centering
\includegraphics[width=0.95\textwidth ]{od-reid-pipeline.png}

\vspace{3pt}
\caption{Standard pipeline for FF-PRID used in our experiments.}

\label{fig:pipeline-rw-reid-modified}
\end{figure*}

\subsection{Object Detection}

In this paper, we use the You Only Look Once (YOLO-v3)~\cite{yolov3} approach for PD. In short, YOLO methods belong to the family of regression/classification based approaches, mapping directly from image pixels to bounding box coordinates and class probabilities to reduce significantly the time complexity. A detailed explanation of YOLO is out of the scope of this paper, and for a complete overview of the recent literature about Object Detection (OD), we refer the reader to the two following surveys~\cite{OD_survey, OD_survey2}.

In practice, we use the Darknet-53 convolutional architecture and pretrained weights proposed in tensorflow.
This network uses 53 convolutional layers with $3x3$ kernels in the beginning and $1x1$ in the end. The model used was trained on the VOC dataset~\cite{voc}, containing 80 classes. Darknet-53 operates at a level close to state-of-the-art object detectors, but is faster because it uses less floating-point operations. The YOLO-v3 model was prepared with a threshold of 0.5 for both Intersection over union (IOU) and the loss function. During our evaluation (Section~\ref{sec:results_OD}), the score threshold to keep a bounding box, as well as the IOU threshold were both set to 0.5 as well. To generate the search galleries, we only use the output corresponding to the person class from the object detector.

\subsection{Classic Person Re-ID}

In our experiments, we perform C-PRID using a method called SiamIDL~\cite{Ejaz2015}. It uses a Siamese neural network architecture composed of two layers of tied convolution with max pooling, cross-input neighborhood differences, patch summary features, across-patch features, higher-order relationships, and finally a softmax function to yield the final estimate of whether the input images are of the same person or not.

For implementation, we used the source code provided by the authors and trained the network using the training set of the CUHK-03 dataset~\cite{cuhk}, containing 7239 images. We use the same parameters as in the original paper: batch\_size=50, max\_steps=210 000, and learning\_rate=0.01. To evaluate the model, the Cumulative Matching Characteristics (CMC) are computed on both the validation folder of CUHK-03 (938 images) and the original PRID-2011 dataset.

\section{Results}
\label{sec:results}

To demonstrate the importance of evaluating Re-ID models in the full frame setting, and thus corroborate the usefulness of the proposed metrics, the evaluation conducted here is two-fold. First, both the PD and the C-PRID models are evaluated independently on standalone datasets. Then, the full FF-PRID pipeline is evaluated using our proposed metrics.

\subsection{Evaluation of the Pedestrian Detection model}
\label{sec:results_OD}

The PRID-2011 dataset was initially created to evaluate C-PRID models.
Hence, occluded persons, persons with less than five confidence frames, as well as distorted images caused by tracking and annotation errors were removed from the list of Bounding Boxes (BB) (see Figure~\ref{fig:imagePRID}).
To achieve a correct evaluation of YOLO-v3 on the PRID-2011 videos, it is necessary to manually add the BBs of these people who were ignored during dataset creation. To do this, the \textit{LabelIMG} tool was used and a total of 37 772 BBs were added to the labels of video B. The results obtained for pedestrian detection with YOLO-v3 on PRID-2011 are presented in Table~\ref{table:resultsEvaluationOD}. These results correspond to the model used to generate the search gallery for the C-PRID model (Fig.~\ref{fig:pipeline-rw-reid-modified}).\par

\begin{table}[ht]
\caption{Evaluation of YOLO-v3 pedestrian detection model on PRID-2011 (video B). For the Original BBs (OBB), only the ground truth labels from the original dataset are used. For the OBB + Manually added BBs (MBB), the BBs added manually are also considered.}
\begin{tabular}{c|c|c|c|c}
\multicolumn{1}{c|}{}   & \textbf{Precision} & \textbf{Recall} & \textbf{F1-score} & \textbf{mAP} \\ \hline
\textbf{OBB}     & 0.462      & 0.866      & 0.603      & 45.53\%      \\ \hline
\textbf{OBB + MBB} & 0.761    &  0.824     & 0.791       & 69.50\%     \\
\end{tabular}
\label{table:resultsEvaluationOD}
\end{table}

When displaying the BBs predicted by YOLO-v3 on PRID-2011 video~B, the results look almost perfect. This way, the difference in the results between OBB and OBB+MBB can be interpreted as the number of entire human bodies which where manually filtered to obtain the original dataset (e.g. partially overlapping persons). The remaining errors for the OBB+MBB case mostly correspond to incomplete body parts, such as legs, arms or torso (Fig.~\ref{fig:mistakesCropps}), which were not included in our ground truth BBs.
An object detector, such as YOLO-v3, is trained to find characteristics of the object of interest and thus generates BBs for the cases mentioned above. This constitutes an important discrepancy between the domain on which the C-PRID model was trained and the images generated by the PD model. Such domain shift in the inputs of the C-PRID model can be a major source of errors for the complete FF-PRID pipeline.

\begin{figure}[ht]
     \centering
     \includegraphics[width=0.4\textwidth]{mistakes_cropps.png}
     \caption{Illustration of the different mistakes for cropping}
     \label{fig:mistakesCropps}
\end{figure}

\subsection{Evaluation of the classic Re-ID model}
\label{sec:results_REID}

To evaluate the SiamIDL model used in our experiments, we compute the CMC curves for both the validation set of CUHK-03 and PRID-2011. These results can be seen on Fig.~\ref{fig:rank}. The evaluation on CUHK-03 is used to validate our training by comparing the results obtained with the ones reported in the original paper. The blue curve in Fig.~\ref{fig:rank} is very similar to the experimental results obtained in~\cite{Ejaz2015}. The red curve on Fig.~\ref{fig:rank} shows the results of a test performed on the first 200 Ids from view A of PRID-2011. We can see that the results obtained were good, with more than 48\% on Rank 1 and more than 95\% on Rank 20. No additional training was conducted on the PRID-2011 dataset and only the weights trained on CUHK-03 were used in this validation. This last experiment evaluates the practical scenario of deploying Re-ID in new environments (e.g. new city, new shopping center), where it would be impractical to create a new custom training dataset for every new implementation.

\begin{figure}[ht]
     \centering
     \includegraphics[width=0.4\textwidth]{rank.png}
     \caption{CMC curve on CUHK-03 validation set and on view A of PRID-2011, using a SiamIDL model trained on CUHK-03 training set.}
     \label{fig:rank}
\end{figure}

The fact that a network trained on CUHK-03 can generalize to data from another dataset shows that the proposed Re-ID model is able to learn cross-domain Re-ID. Indeed, the kind of images used for training are very different than the images encountered at inference time (see Fig.~\ref{fig:imagesComparison}). This property is interesting as the domains encountered for every new implementation vary a lot with cameras' resolution, distance the people and illumination, among other factors.

\begin{figure}[ht]
     \centering
     \begin{subfigure}[b]{0.195\textwidth}
         \centering
         \includegraphics[width=\textwidth]{cuhk_comp.png}
         \caption{CUHK-03}
         \label{fig:imageCUHK}
     \end{subfigure}
     \hfill
     \begin{subfigure}[b]{0.26\textwidth}
         \centering
         \includegraphics[width=\textwidth]{prid_comp.jpg}
         \caption{PRID 2011}
         \label{fig:imagePRID}
     \end{subfigure}

     \caption{Example images from the CUHK-03 and the PRID-2011 datasets.}
     \label{fig:imagesComparison}
\end{figure}

\begin{figure*}
     \centering
     \begin{subfigure}[b]{0.32\textwidth}
         \centering
         \includegraphics[width=\textwidth]{t10_Results_for_TVR_and_FR.png}
         \caption{$\tau$=10 }
         \label{fig:fr_with_t10}
     \end{subfigure}
     \hfill
     \begin{subfigure}[b]{0.32\textwidth}
         \centering
         \includegraphics[width=\textwidth]{t100_Results_for_TVR_and_FR.png}
         \caption{$\tau$=100}
         \label{fig:fr_with_t100}
     \end{subfigure}
     \hfill
     \begin{subfigure}[b]{0.32\textwidth}
         \centering
         \includegraphics[width=\textwidth]{t1000_Results_for_TVR_and_FR.png}
         \caption{$\tau$=1000}
         \label{fig:fr_with_t1000}
     \end{subfigure}
 \caption{Finding Rate (FR) and True Validation Rate (TVR) curves for different values of $\tau$, $\beta$ and $\eta$. \textit{In Fig.~\ref{fig:fr_with_t1000}, the curves $\eta=10$ and $\eta=20$ are overlapping}.
 \label{fig:results graphs}
\end{figure*}

\subsection{Evaluation of the full pipeline for FF-PRID}

For evaluation, 10 videos of two minutes were selected from each view. For each video, approximately 4 query images were selected. In total, our evaluation consists of 20 videos and 73 queries. Each query appears in its associated video at least in one frame, but does not necessarily appear in each sub-videos after splitting into shorter sequences. To evaluate the influence of the different parameters of the FF-PRID pipeline, i.e. the number of frames for video splitting $\tau$, the threshold for alert generation $\beta$ and the number of candidates shown to the monitoring agent $\eta$, we use different values for each parameter. Thus, we test $\tau \in \{10, 100, 1000\}$, $\eta \in \{1, 10, 20\}$ and the threshold $\beta$ is computed for various values in the interval $\left[0.5, 0.98\right]$. Fig.~\ref{fig:results graphs} shows the FR and TVR curves for different values of $\tau$, $\beta$ and $\eta$.

\subsubsection{Influence of the FF-PRID parameters}

In Fig.~\ref{fig:results graphs}, for all values of $\tau$ and $\eta$, the FR curves decrease when $\beta$ increases. This behavior is due to the fact that with larger $\beta$, the system raises less alerts and is more likely to miss the query. However, with $\tau = 1000$, the decreasing effect is less noticeable. This is because when considering larger galleries, the model has more chances of finding a similar image and having at least one high confidence prediction.
In contrast, the three TVR curves are increasing with $\beta$. This also makes sense as increasing $\beta$ correspond to reducing the accepted confidence range and thus calling the agent less frequently. However, except for $\tau = 1000$, we note that the values of the different TVR are all very low, meaning that the human monitoring agent would be called in many unnecessary cases.

Furthermore, as expected, $\eta = 10$ and $\eta = 20$ performed much better than $\eta = 1$ for all configurations of $\tau$ and $\beta$. Indeed, the C-PRID models are not perfect and training Re-ID models with very high top 1 accuracy is hard. In contrast, decreasing $\eta$, reduces the amount of work for the monitoring agent as it needs to control less image samples.
Besides, the FR curves present better results for $\tau = 100$ than for the two other tested values, meaning that the raw video is split into sub-videos which are neither too short nor too long. This way, the query appears on the video for a sufficient amount of time to be recognize and there are not too many distractors to confuse the network.

\subsubsection{Qualitative Evaluation}

Fig.~\ref{fig:interfaceReID} shows an example of the propositions received by the monitoring agent.
In practice, during the evaluation, we observed that way too many alert calls. Also, when a sub-video of $\tau$ frames contains too many persons, a variety of cropped images are presented, not always representing the query. We also noted that the imperfect BBs produced by YOLO-v3 (Fig.~\ref{fig:mistakesCropps}) had a strong negative influence on the results

\begin{figure}[ht]
     \centering
     \includegraphics[width=0.4\textwidth]{interfaceReID.png}
     \caption{Example of the interface for alert validation with $\eta=6$.}
     \label{fig:interfaceReID}
\end{figure}

\subsubsection{Further considerations}

The results obtained for the FF-PRID problem suggest that careful selection of the tunable parameters ($\tau$, $\beta$ and $\eta$) is paramount. Indeed, with proper selection we can reach an FR of almost 80\% with a TVR of 26\%. Although the score that we managed to reach for the Finding Rate are satisfactory, we acknowledge that the TVR is still too low for the method to be used practically, as the operator would be called too many times if dealing with several cameras at the same time. These mixed results emphasize the importance of considering the FF-PRID problem as a whole and suggest that changing the paradigm for person Re-ID might be the best way to obtain applicable solution for tomorrow's cities.

As already mentioned, the discrepancy between the training domain of the classic Re-ID model and the domain generated by OD is a possible reason for the results obtained. Another possible reason for the low TVR is that SiamIDL is a closed-world method, i.e. it supposes that the query is always present in the search gallery. Hence, the highest ranked prediction tend to have very high confidence scores and to raise alerts very frequently. In the validation example studied here, sometimes the query is not present, thus defining an open set scenario~\cite{openworld}.

\section{Conclusion and Future Work}
\label{sec:conclusion}

In this paper we claim that the classic approach for person Re-ID is not sufficient to develop robust practical implementations for security application. Indeed, full frames of the cameras stream must be processed instead of pre-cropped clean images of people.
To study FF-PRID, we present a new framework, taking into account the fact that a human monitoring agent needs to validate the results. We also introduce two new metrics in order to evaluate FF-PRID models within the proposed pipeline. The metrics are used to evaluate how many times the query is found when it is present in the video (Finding Rate) and how many times the query is present when the agent is solicited (True Validation Rate). These framework and metrics are, to the best of our knowledge, the first proposed approaches to evaluate a FF-PRID model, looking for persons directly in the entire video frames.

To support our claim, we conducted experiments on a modified version of the PRID-2011 dataset, using a standard pipeline for FF-PRID. First, persons BBs are extracted from the input video using a state-of-the-art OD model to generate a search gallery. Then, the query is searched in the gallery using a good C-PRID model. We demonstrated that both the OD model and the C-PRID models managed to perform well on the new dataset without additional training. However, the final results for FF-PRID, evaluated using FR and TVR, were not sufficient to deploy FF-PRID in production. Although choosing the right parameters in our framework enabled us to reach a good FR score ($>80\%$), we were not able to obtain a TVR much better than $25\%$, which means that most of the time the operator calls were unnecessary. Some possible explanations for these results were discussed as well as possible improvements. These mixed results emphasize the importance of considering Re-ID in the FF-PRID setting if we want to develop methods that can be used reliably in practical scenarios. We believe that many improvements could be achieved if the community starts investigating Re-ID solutions for the Full Frame setting instead of focusing only on the classic pre-cropped image-based setting.

After demonstrating the importance of considering the FF-PRID setting, the next step is to propose new approaches to improve the standard pipeline implemented here, and get closer to solving FF-PRID. A possible direction to achieve this is to consider video-based classic Re-ID methods~\cite{PRL_videoBased, PRL_videoBased2}. Another natural option is to consider the open-world person Re-ID setting instead of closed-world~\cite{openworld}. We also plan to train more specific pedestrian detection techniques, focusing on recognizing only full-bodies. Finally, another potential improvement to address the problem would consist in building a large dataset of annotated videos, which could be used for training an end-to-end model for the whole FF-PRID application. This approach sounds promising in regards with the success of end-to-end approaches in solving complex tasks lately~\cite{end2end_1, end2end_2}.