Perception with Guarantees: Certified Pose Estimation via Reachability Analysis Tobias Ladner 1 2 1 , Yasser Shoukry 2 , Matthias Althoff 1 Abstract Agents in cyber-physical systems are increasingly entrusted with safety-critical tasks. Ensuring safety of these agents often requires localizing the pose for subsequent actions. Pose estimates can, e.g., be obtained from various combinations of lidar sensors, cameras, and external services such as GPS. Crucially, in safety-critical domains, a rough estimate is insufficient to formally determine safety, i.e., guaranteeing safety even in the worst-case scenario, and external services might additionally not be trustworthy. We address this problem by presenting a certified pose estimation in 3D solely from a camera image and a well-known target geometry. This is realized by formally bounding the pose, which is computed by leveraging recent results from reachability analysis and formal neural network verification. Our experiments demonstrate that our approach efficiently and accurately localizes agents in both synthetic and real-world experiments. 1 1 footnotetext: This research was conducted during Tobias Ladner’s research stay at the University of California, Irvine. I Introduction Agents act increasingly autonomously in real-world scenarios, including safety-critical domains such as autonomous driving [ 21 ] . If one demands safety guarantees in such systems, they have to be formally verified [ 2 ] . This necessitates a correct perception of the pose of the agent with respect to surrounding obstacles so that the agent can move safely within the environment by selecting only actions that adhere to the given safety specifications [ 16 ] , and might iteratively refine its understanding as it moves through the environment [ 11 ] . Unfortunately, existing localization techniques [ 7 , 39 ] – e.g., based on cameras and lidar sensors – only provide a rough estimate of the current pose, which is insufficient for downstream tasks if formal safety is required. In addition, techniques using deep learning [ 8 ] are susceptible to adversarial attacks [ 20 ] . Moreover, external services, such as GPS, can be interfered with – e.g., in geopolitically tense scenarios [ 38 , 46 ] – making them not trustworthy. We address this problem by presenting an approach to obtain certified pose estimates solely from images taken by an event-based camera [ 14 ] and a well-known target geometry. Such a target geometry can be, e.g., the geometry of a stop sign or standardized runway markings on the ground ( fig. 1 ). Knowing the geometry, we aim to robustly detect the target in an image and return a certified pose estimation of the camera in relation to this target. We show that such a pure vision-based setting is already sufficient to obtain certified pose estimates. (a)                 (b) Fig. 1: (a) Runway markings as by ICAO standard [ 25 , Chp. 5] . (b) Runway markings observed from a landing plane [ 5 ] . In summary, our work marks an important step toward the deployment of autonomous agents in safety-critical domains and our main contributions are: 1. We enclose possible images of a target from an uncertain pose using reachability analysis. 2. We show how a certified pose estimate given a concrete image can be retrieved, thereby guaranteeing a correct perception. 3. Our approach naturally incorporates uncertainty in poses, camera parameters, and target geometry. 4. We obtain tight certified pose estimates on synthetic experiments as well as real-world experiments on noisy images. II Background II-A Notation Let \mathbb{N} be the natural numbers, \mathbb{R} be the real numbers, and \mathbb{B}=\{0,1\} . We denote scalars and vectors by lowercase letters, matrices by uppercase letters, and sets by calligraphic letters. The i -th element of a vector v\in\mathbb{R}^{n} is written as v_{(i)} , the element in the i -th row and j -th column of a matrix A\in\mathbb{R}^{n\times m} is written as A_{(i,j)} , and the entire i -th row and j -th column are written as A_{(i,\cdot)} and A_{(\cdot,j)} , respectively. We denote by I_{n} the identity matrix of dimension n\in\mathbb{N} . The bold symbols \mathbf{0} and \mathbf{1} refer to matrices with all zeros and ones of proper dimensions, respectively. Given n\in\mathbb{N} , we use the shorthand notation [n]=\left\{1,\ldots,n\right\} . The cardinality of a discrete set \mathcal{D} is denoted by |\mathcal{D}| . Let \mathcal{D}\subseteq[n] , then A_{(\mathcal{D},\cdot)} denotes all rows i\in\mathcal{D} in lexicographic order; this is used analogously for columns. Given a\leq b\leq n , we also use A_{(a:b,\cdot)}=A_{([b]\setminus[a-1],\cdot)} for readability when indexing. Let \mathcal{S}\subset\mathbb{R}^{n} be a set and f\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{m} be a function, then f(\mathcal{S})=\left\{f(x)\ \middle|\ x\in\mathcal{S}\right\} . We also use the (matrix) indexing defined above for multi-dimensional sets. An interval with bounds a,b\in\mathbb{R}^{n} is denoted by [a,b] , where a\leq b holds element-wise. We denote the indicator function by \mathbb{1}_{\{\texttt{}\}} . II-B Model of the System Our goal is to obtain a certified pose estimate of a target object from a binary image I\in\mathbb{B}^{w\times h} , which are known for their sensitivity [ 14 ] . We assume that the target object can be decomposed into multiple convex polygons ( fig. 1 ), and subsequently define a generalized form of polygons [ 12 ] , where their vertices are on a two-dimensional plane in a three-dimensional Euclidean space. Definition 1 (Polygon) . Given c\in\mathbb{R}^{3} , d\in\mathbb{R} defining a plane, and \nu vertices V\in\mathbb{R}^{3\times\nu} in counter-clockwise winding order, we define a convex polygon as: \displaystyle\mathcal{P}=\left_{P\,} \displaystyle=\text{\small{$\mathtt{convHull}$}}(V)\subset\mathbb{R}^{3}, \displaystyle\text{with }c^{\top}V_{(\cdot,i)} \displaystyle=d,\quad i\in[\nu], where \text{\small{$\mathtt{convHull}$}}\left(V\right)=\left\{\sum_{i=1}^{\nu}\lambda_{i}V_{(\cdot,i)}\ \middle|\ \lambda_{i}\in[0,1],\,\sum_{i=1}^{\nu}\lambda_{i}=1\right\} . The target object is given by: Definition 2 (Target Object) . Given \rho convex polygons \mathcal{P}_{1},\ldots,\mathcal{P}_{\rho}\subset\mathbb{R}^{3} , the target model \mathcal{T}=\left<\mathcal{P}_{1},\ldots,\mathcal{P}_{\rho}\right>_{T\,}\subset\mathbb{R}^{3} is: \mathcal{T}=\bigcup_{i=1}^{\rho}\mathcal{P}_{i}. The polygons of the target \mathcal{T} are given in the target coordinate frame (TCF). This space is transformed through the camera ( camera coordinate frame , CCF) onto the final image ( pixel coordinate frame , PCF), where we consider a pinhole camera model specified by intrinsic and extrinsic parameters [ 24 , Chp. 6.1] : The intrinsic parameters consist of the focal length f\in\mathbb{R}_{>0} as well as the width w\in\mathbb{N} and height h\in\mathbb{N} of the final image. We assume that the principal point of the camera, i.e., where the optical axis of the camera intersects the image sensor plane, is at the center of the image. The extrinsic parameters involve the pose \xi of the camera with respect to the target \mathcal{T} : \xi=\left[\begin{matrix}x&y&z&\theta_{x}&\theta_{y}&\theta_{z}\end{matrix}\right]^{\top}\in\Xi\subset\mathbb{R}^{6}, (1) where x,y,z is the position in the global coordinate frame, and \theta_{x},\theta_{y},\theta_{z} are the roll, pitch, and yaw angles, respectively. The file ’’./figures/externalize-twocol/.pdf‘‘ does not exist and has to be exported first. Please re-compile with tikz externalize and shell escape enabled. Check the documentation for details. Fig. 2: Example transformation given a target \mathcal{T} and a pose \xi . The goal of this work is the inverse: How to obtain a certified estimate of \xi given the final image and \mathcal{T}^{\text{TCF}} ? Subsequently, we detail how an image is computed from \xi , which we also illustrate in fig. 2 : Given a convex polygon \mathcal{P}_{i}=\left_{P\,} of \mathcal{T} , with V_{i}^{\text{TCF}}\in\mathbb{R}^{3\times\nu_{i}} , and the parameters of the camera f,w,h,\xi , the analog output of the camera is [ 24 , Chp. 6.1] : V_{i}^{\text{CCF}}=K_{f,w,h}\,\left(R(\theta_{x},\theta_{y},\theta_{z})\,V_{i}^{\text{TCF}}+T(x,y,z)\right), (2) using the intrinsic matrix [ 24 , Eq. 6.2] : K_{f,w,h}=\left[\begin{matrix}f&0&w/2\\ 0&f&h/2\\ 0&0&1\end{matrix}\right], (3) the rotation matrix [ 18 , Eq. 4.17] : \displaystyle\begin{split}&R(\theta_{x},\theta_{y},\theta_{z})=R_{x}(\theta_{x})\,R_{y}(\theta_{y})\,R_{z}(\theta_{z})=\\ &\resizebox{20348790}{}{$\displaystyle\left[\begin{matrix}1&0&0\\ 0&\cos(\theta_{x})&-\sin(\theta_{x})\\ 0&\sin(\theta_{x})&\cos(\theta_{x})\end{matrix}\right]\left[\begin{matrix}\cos(\theta_{y})&0&\sin(\theta_{y})\\ 0&1&0\\ -\sin(\theta_{y})&0&\cos(\theta_{y})\end{matrix}\right]\left[\begin{matrix}\cos(\theta_{z})&-\sin(\theta_{z})&0\\ \sin(\theta_{z})&\cos(\theta_{z})&0\\ 0&0&1\end{matrix}\right]$},\end{split} (4) and the translation: T(x,y,z)=\left[\begin{matrix}x&y&z\end{matrix}\right]^{\top}. (5) The digital behavior of the camera maps the polygon in the CCF onto the pixels of the binary image I_{i}\in\mathbb{B}^{w\times h} taken by the event-based camera [ 14 ] . This is computed by [ 24 , Eq. 6.1] : \displaystyle\begin{split}\forall(q_{x},q_{y})\in&\ [w]\times[h]\colon\\ I_{i(q_{x},q_{y})}=&\begin{cases}1&\text{if $(q_{x},q_{y})\in\text{\small{$\mathtt{convHull}$}}(V_{i}^{\text{PCF}})$,}\\ 0&\text{otherwise,}\end{cases}\\ \text{where}\ V_{i(\cdot,k)}^{\text{PCF}}=&\left[\begin{matrix}\nicefrac{{V_{i(1,k)}^{\text{CCF}}}}{{V_{i(3,k)}^{\text{CCF}}}}\\ \nicefrac{{V_{i(2,k)}^{\text{CCF}}}}{{V_{i(3,k)}^{\text{CCF}}}}\end{matrix}\right]\in\mathbb{R}^{2},\quad k\in[\nu_{i}].\end{split} (6) We have now all ingredients to define the camera model used in this work. Definition 3 (Pinhole Camera Model [ 24 , Chp. 6.1] ) . Given a target \mathcal{T}=\{\mathcal{P}_{1},\ldots,\mathcal{P}_{\rho}\} , the pose \xi\in\Xi , and the parameters of the camera f\in\mathbb{R} , w\in\mathbb{N} , h\in\mathbb{N} , the images I_{i}\in\mathbb{B}^{w\times h} of each polygon i\in[\rho] , captured by a camera C_{f,w,h} , are computed using ( 2 )-( 6 ), and the combined image I\in\mathbb{B}^{w\times h} is given by: I=\min\{1,\,\Sigma_{i=1}^{\rho}I_{i}\}. Thus, a pixel is turned on if any polygon \mathcal{P}_{i} intersects with the pixel. Noisy images In practice, images are subject to noise for which we define a noise budget. Definition 4 (Noise Budget) . Given a clean image I\in\mathbb{B}^{w\times h} as produced by definition 3 , we say that an image \widetilde{I}\in\mathbb{B}^{w\times h} does not exceed a maximal noise budget \tau\in\mathbb{N}_{0} iff the number of perturbed pixels is bounded by: \lVert I-\widetilde{I}\rVert_{1}\leq\tau. We assume that noise does not lead to turned-off pixels along the edges of the target, as event-based cameras can reliably detect edges [ 14 ] . II-C Set-Based Computing We use (matrix) polynomial zonotopes [ 30 ] to represent sensing uncertainties as their Minkowski sum and multiplication can be computed exactly and efficiently. We briefly state the definition and the required operations here and provide an example in section A-A . Definition 5 (Matrix Polynomial Zonotope [ 34 , Def. 7] ) . Given an offset O\in\mathbb{R}^{n\times m} , dependent generators G\in\mathbb{R}^{n\times m\times h} , independent generators G_{I}\in\mathbb{R}^{n\times m\times q} , and an exponent matrix E\in\mathbb{N}_{0}^{p\times h} with an identifier {\scalebox{0.9}{$\mathtt{id}$}}\in\mathbb{N}^{p} , a matrix polynomial zonotope \mathcal{M}=\left_{PZ\,}\subset\mathbb{R}^{n\times m} is defined as: \displaystyle\mathcal{M}\coloneqq\left\{O+\sum_{i=1}^{h}\left(\prod_{k=1}^{p}\alpha_{k}^{E_{(k,i)}}\right)G_{(\cdot,\cdot,i)}+\sum_{j=1}^{q}\beta_{j}G_{I(\cdot,\cdot,j)}\ \right| \displaystyle\left.\alpha_{k},\beta_{j}\in\left[-1,1\right]\right\}. Given two matrix polynomial zonotopes \mathcal{M}_{1}=\left_{PZ\,},\,\mathcal{M}_{2}=\left_{PZ\,}\subset\mathbb{R}^{n\times m} with a common identifier, the Minkowski sum is computed as [ 34 , Eq. 5] : \displaystyle\begin{split}\mathcal{M}_{1}\oplus\mathcal{M}_{2}=\left\{M_{1}+M_{2}\ \middle|\ M_{1}\in\mathcal{M}_{1},\,M_{2}\in\mathcal{M}_{2}\right\}\\ =\left_{PZ\,}.\end{split} (7) Given two matrix polynomial zonotopes \mathcal{M}_{3}\subset\mathbb{R}^{n\times k} , \mathcal{M}_{4}\subset\mathbb{R}^{k\times m} , their multiplication: \displaystyle\mathcal{M}_{3}\boxdot\mathcal{M}_{4}=\left\{(M_{3}M_{4})\ \middle|\ M_{3}\in\mathcal{M}_{3},\,M_{4}\in\mathcal{M}_{4}\right\} (8) is computed by broadcasting the multiplication onto each offset and generator combination [ 34 , Lemma 1] . Notably, an affine map is computed as a special case of ( 7 ) and ( 8 ), with one matrix polynomial zonotope being a singleton. Subscript operations on a matrix polynomial zonotope \mathcal{PZ}=\left_{PZ\,}\subset\mathbb{R}^{n\times m} , can be computed by applying them on O , G , G_{I} . For example, the uncertainty at the (i,j) -th entry of the matrix, i\in[n],j\in[m] , is obtained by: \mathcal{PZ}_{(i,j)}=\left_{PZ\,}. (9) For instance, \mathcal{V}\subset\mathbb{R}^{3\times\nu} can be a matrix polynomial zonotope bounding the uncertain vertices of a polygon. Then, for k\in[\nu] , \mathcal{V}_{(\cdot,k)}\subset\mathbb{R}^{3} returns the uncertainty of the k -th vertex. Given a set \mathcal{X}\subset\mathbb{R}^{n} and a function f\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{m} , we also require to bound f(\mathcal{X})\subseteq\mathcal{Y}\subset\mathbb{R}^{m} . To do so, we leverage recent advances in formal neural network verification [ 29 ] , in particular, for polynomial zonotopes [ 31 , 33 ] . Verifying certain properties of the output of f given \mathcal{X} is NP-hard [ 28 ] . Thus, the output is usually enclosed using abstractions, for which polynomial zonotopes have a good trade-off between precision and computation time. Proposition 1 (Image Enclosure [ 31 , Sec. 3] ) . Given a set \mathcal{X}\subset\mathbb{R}^{n} and a function f\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{m} , \mathcal{Y}=\text{\small{$\mathtt{enclose}$}}\left(f,\mathcal{X}\right)\supseteq f(\mathcal{X}) computes an outer-approximative output set. We provide details on \text{\small{$\mathtt{enclose}$}}\left(\cdot,\cdot\right) in section A-A . II-D Problem Statement Given a target \mathcal{T}\subset\mathbb{R}^{3} ( definition 2 ), a camera C_{f,w,h} ( definition 3 ), and a binary image I^{*}\in\mathbb{B}^{w\times h} , we want to find a certified set of poses \mathcal{E}^{*}\subseteq\Xi such that the (unobservable) true pose \xi^{*}\in\Xi , which reproduces I^{*} up to a considered noise budget \tau , is contained: \xi^{*}\in\mathcal{E}^{*} . To penalize simply returning the trivial solution \mathcal{E}^{*}=\Xi , pose estimates \mathcal{E}^{*} with smaller volume are preferred. The file ’’./figures/externalize-twocol/.pdf‘‘ does not exist and has to be exported first. Please re-compile with tikz externalize and shell escape enabled. Check the documentation for details. Fig. 3: Overview: (a) Given a concrete image I^{*} ( ) and a pose candidate \mathcal{E}_{c} ( ), we check whether I^{*} is contained in the outer-approximative image \widehat{I}_{\mathcal{E}_{c}} ( ). (b) If not, \mathcal{E}_{c} is discarded as \xi^{*}\not\in\mathcal{E}_{c} then. Otherwise, we exploit the relative position of the vertices in I^{*} ( ) within the uncertain vertices ( ) of \mathcal{E}_{c} – which are a byproduct of computing \widehat{I}_{\mathcal{E}_{c}} – to (c) impose constraints ( ) on \mathcal{E}_{c} , which – when computed for all vertices – obtains us the certified pose estimate \mathcal{E}^{*} ( ). III Framework for Certified Pose Estimation Our approach to obtain a certified pose estimate is based on reachability analysis and pre-image enclosures using the computed reachable sets. In particular, we compute outer-approximative images from a set of pose candidates in section III-A , on which we later, given a concrete image, impose constraints to obtain a tight certified pose estimate in section III-B . An overview of this process is shown in fig. 3 . III-A Sound Image Enclosure From Uncertain Pose Given an uncertain pose \mathcal{E}\subseteq\Xi , we present an approach to characterize all resulting images from concrete poses \xi\in\mathcal{E} . This section closely follows section II-B , while computing everything in a set-based manner. The process is summarized in algorithm 1 . Algorithm 1 Enclosing an Image From Uncertain Pose 1: Target \mathcal{T}=\left<\mathcal{P}_{1},\ldots,\mathcal{P}_{\rho}\right>_{P\,}\in\mathbb{R}^{3} , uncertain pose \mathcal{E}\subseteq\Xi , camera C_{f,w,h} 2: // Analog behavior of camera. 3: \mathcal{S}\leftarrow\text{\small{$\mathtt{enclose}$}}(\sin,\mathcal{E}_{(4:6)}) \triangleright proposition 1 4: \mathcal{C}\leftarrow\text{\small{$\mathtt{enclose}$}}(\cos,\mathcal{E}_{(4:6)}) 5: Construct \mathcal{R}_{x},\mathcal{R}_{y},\mathcal{R}_{z} using \mathcal{S},\mathcal{C} \triangleright ( 4 ) 6: \mathcal{R}\leftarrow\mathcal{R}_{x}\boxdot\mathcal{R}_{y}\boxdot\mathcal{R}_{z} \triangleright ( 4 ),( 8 ) 7: for \mathcal{P}_{i}=\left_{P\,} in \mathcal{T} do 8: \mathcal{V}_{i}^{\text{CCF}}\leftarrow K_{f,w,h}\boxdot(\mathcal{R}\boxdot V_{i}^{\text{TCF}}\oplus\mathcal{E}_{(1:3)}) \triangleright ( 10 ) 9: // Digital behavior of camera. 10: \mathcal{V}_{i(1:2,\cdot)}^{\text{PCF}}\leftarrow\mathcal{V}_{i(1:2,\cdot)}^{\text{CCF}}\boxdot\text{\small{$\mathtt{enclose}$}}(x\mapsto\nicefrac{{1}}{{x}},\mathcal{V}_{i(3,\cdot)}^{\text{CCF}}) \triangleright ( 6 ) 11: \widehat{\mathcal{P}}_{i}^{\text{PCF}}\supseteq\text{\small{$\mathtt{convHull}$}}\left(\mathcal{V}_{i(\cdot,1)}^{\text{PCF}},\ldots,\mathcal{V}_{i(\cdot,\nu_{i})}^{\text{PCF}}\right) \triangleright ( 11 ) 12: \widehat{I}_{i}\leftarrow\mathbf{0}\in\mathbb{B}^{w\times h} \triangleright Initialize image 13: for (q_{x},q_{y})\in[w]\times[h] do 14: \widehat{I}_{i(q_{x},q_{y})}\leftarrow\mathbb{1}_{\{(q_{x},q_{y})\in\widehat{\mathcal{P}}_{i}^{\text{PCF}}\}} \triangleright Check containment 15: return \widehat{I}_{\mathcal{E}}\leftarrow\min\{1,\,\sum_{i=1}^{\rho}\widehat{I}_{i}\} \triangleright definition 3 We first enclose the \sin and \cos functions for the given angles \mathcal{E}_{(4:6)} using proposition 1 (line 3 ), and bound all possible rotation matrices \mathcal{R} ( 4 ) using ( 8 ) (line 5 ). Subsequently, the analog output of the camera ( 2 ) is computed by: \mathcal{V}_{i}^{\text{CCF}}=K_{f,w,h}\boxdot(\mathcal{R}\boxdot V_{i}^{\text{TCF}}\oplus\mathcal{E}_{(1:3)}) (10) using ( 8 ) and ( 7 ). Please note that uncertainty in both the camera parameters and the target geometry can be modelled by adding uncertainty to K_{f,w,h} and V^{\text{TCF}} , respectively; further details are provided in section A-B . The file ’’./figures/externalize-twocol/.pdf‘‘ does not exist and has to be exported first. Please re-compile with tikz externalize and shell escape enabled. Check the documentation for details. Fig. 4: Computation of the outer-approximative image for a target with a single polygon ( \rho=1 ) and an uncertain pose \mathcal{E} with perturbed angles \theta_{x},\theta_{y},\theta_{z} by 10 degrees: (a) Uncertain vertices \mathcal{V}_{1}^{\text{PCF}} enclose the vertices of the random samples. (b) Convex hull computation over \mathcal{V}_{1}^{\text{PCF}} . (c) Outer-approximative image \widehat{I}_{\mathcal{E}} . The digital behavior of the camera ( 6 ) requires us to compute the convex hull over all vertices \mathcal{V}_{i(\cdot,k)}^{\text{PCF}} ( definition 1 ); however, these are now sets themselves due to the uncertainty in the pose \mathcal{E} ( fig. 4 ). As \mathcal{V}_{i(\cdot,k)}^{\text{PCF}} is two-dimensional, efficient algorithms exist to compute this convex hull [ 6 ] : \widehat{\mathcal{P}}_{i}^{\text{PCF}}\supseteq\text{\small{$\mathtt{convHull}$}}\left(\mathcal{V}_{i(\cdot,1)}^{\text{PCF}},\ldots,\mathcal{V}_{i(\cdot,\nu_{i})}^{\text{PCF}}\right); (11) more details are provided in section A-C . Finally, we check for pixel containment in the outer-approximative polygon \widehat{\mathcal{P}}_{i}^{\text{PCF}} of each polygon i\in[\rho] (lines 12 - 14 ), and combine the resulting image to obtain the final image (line 15 ). Proposition 2 (Pose to Image) . Given a target \mathcal{T}=\left<\mathcal{P}_{1},\ldots,\mathcal{P}_{\rho}\right>_{P\,}\in\mathbb{R}^{3} , an uncertain pose \mathcal{E}\subseteq\Xi , and a camera C_{f,w,h} , algorithm 1 computes an image \widehat{I}_{\mathcal{E}}\in\mathbb{B}^{w\times h} such that: \displaystyle\forall\xi\in\mathcal{E}\colon \displaystyle\forall(q_{x},q_{y})\in[w]\times[h]\colon \displaystyle\qquad\mathbb{1}_{\{I_{\xi(q_{x},q_{y})}=1\}}\ \implies\ \mathbb{1}_{\{\widehat{I}_{\mathcal{E}(q_{x},q_{y})}=1\}}, where I_{\xi}\in\mathbb{B}^{w\times h} is the image produced by a concrete pose \xi using definition 3 . The computational complexity is given by \mathcal{O}(\rho wh) . Proof. The proof can be found in appendix B . ∎ III-B Certified Pose Estimation From Image Now that we have computed the outer-approximative image \widehat{I}_{\mathcal{E}} , we detail how to obtain a certified pose estimate given a concrete, possibly noisy, image I^{*} ( section II-D , overview in fig. 3 ). Our approach exploits dependencies between the computed sets, i.e., between the uncertain pose \mathcal{E}\subseteq\Xi and the computed vertices \mathcal{V}_{i(\cdot,k)}^{\text{PCF}} . This is possible as all \mathcal{V}_{i(\cdot,k)}^{\text{PCF}} are computed from \mathcal{E} via algorithm 1 . In particular, these sets have a shared latent space , enabling us, by imposing constraints on \mathcal{V}_{i(\cdot,k)}^{\text{PCF}} , to also impose constraints on \mathcal{E} through this latent space. This constrained \mathcal{E} will then be our certified pose estimate \mathcal{E}^{*}\subseteq\Xi , where it is ensured that the (unobservable) true pose \xi^{*}\in\Xi is contained: \xi^{*}\in\mathcal{E}^{*} ( section II-D ). Subsequently, we detail the individual steps and summarize our approach in algorithm 2 . Algorithm 2 Obtaining Certified Pose Estimates From Image 1: Image I^{*}\in\mathbb{B}^{w\times h} , target \mathcal{T}\subset\mathbb{R}^{3} , camera C_{f,w,h} 2: // 1) Filter candidate poses. 3: Gather candidate poses \mathcal{E}_{1},\ldots,\mathcal{E}_{\zeta}\subseteq\Xi \triangleright (pre-computed) 4: for c\in[\zeta] do 5: Gather \widehat{I}_{\mathcal{E}_{c}},\mathcal{V}_{c,1}^{\text{PCF}},\ldots,\mathcal{V}_{c,\rho}^{\text{PCF}} \triangleright algorithm 1 (pre-computed) 6: if I^{*}\not\in\widehat{I}_{\mathcal{E}_{c}} then 7: C_{c}\leftarrow\mathbf{0} ; d_{c}\leftarrow-1 ; continue \triangleright Quick exit ( 13 ) 8: // 2) Refine candidate poses. 9: for i\in[\rho] do 10: for k\in[\nu_{i}] do 11: Compute \mathcal{Q}_{c,i,k}\subseteq[w]\times[h] for \mathcal{V}_{c,i(\cdot,k)}^{\text{PCF}} \triangleright ( 16 ) 12: Compute C_{c,i,k},d_{c,i,k} \triangleright ( 16 ), lemma 1 13: C_{c,i}=\left[\begin{matrix}C_{c,i,1}^{\top}&\ldots&C_{c,i,\nu_{i}}^{\top}\end{matrix}\right]^{\top} 14: d_{c,i}=\left[\begin{matrix}d_{c,i,1}^{\top}&\ldots&d_{c,i,\nu_{i}}^{\top}\end{matrix}\right]^{\top} 15: C_{c}=\left[\begin{matrix}C_{c,1}^{\top}&\ldots&C_{c,\rho}^{\top}\end{matrix}\right]^{\top} ; d_{c}=\left[\begin{matrix}d_{c,1}^{\top}&\ldots&d_{c,\rho}^{\top}\end{matrix}\right]^{\top} 16: return \mathcal{E}^{*}\leftarrow\mathcal{E}_{1}|_{C_{1}\leq d_{1}}\cup\,\cdots\,\cup\,\mathcal{E}_{\zeta}|_{C_{\zeta}\leq d_{\zeta}}\subseteq\Xi \triangleright ( 17 ) algorithm 2 consists of two phases: 1) the selection of candidate poses \mathcal{E}_{c} , and 2) the refinement of the candidate poses by imposing constraints on the shared latent space. III-B 1 Selection of candidate poses We can – offline – pre-compute a set of (axis-aligned) boxes \mathcal{E}_{1},\ldots,\mathcal{E}_{\zeta} partitioning the pose space \Xi\subset\mathbb{R}^{6} : \Xi=\bigcup_{c\in\zeta}\mathcal{E}_{c}, (12) and compute the corresponding \widehat{I}_{\mathcal{E}_{c}}\in\mathbb{B}^{w\times h},\mathcal{V}_{c,1}^{\text{PCF}},\ldots,\mathcal{V}_{c,\rho}^{\text{PCF}}\subset\mathbb{R}^{2} for each candidate pose \mathcal{E}_{c} , c\in[\zeta] , using algorithm 1 . Then, – online, e.g., as a landing plane takes pictures of the runway ( fig. 1 ) – given a concrete image I^{*}\in\mathbb{B}^{w\times h} , we efficiently filter all irrelevant boxes \mathcal{E}_{c} ( algorithm 2 , line 7 ) by checking: I^{*}\in\widehat{I}_{\mathcal{E}_{c}}, (13) where the containment checks whether all pixels (q_{x},q_{y})\in[w]\times[h] with I_{(q_{x},q_{y})}^{*}=1 are also turned on in \widehat{I}_{\mathcal{E}_{c}} ( proposition 2 ). On the remaining pose candidates, we also analogously check if I^{*} is at least partially contained in \widehat{I}_{\mathcal{E}_{c},i,k} for each vertex k\in[\nu_{i}] , i\in[\rho] . This filters candidates that are, e.g., too close to the camera. Due to the outer-approximative computation of the images, we can guarantee that the true pose \xi^{*} has to be contained in the remaining pose candidates. As this filtering has to be done on all \zeta candidate poses, it has to be implemented efficiently to be computationally feasible online. Please note that all involved variables are binary bitmaps. Thus, this can be done in a batch-wise manner with complexity \mathcal{O}(\zeta\rho\nu_{i}wh) . III-B 2 Refinement of candidate poses We refine our selected candidate poses \mathcal{E}_{c} , by imposing constraints C_{c}\leq d_{c} on the shared latent space between \mathcal{E}_{c} and its computed vertices \mathcal{V}_{c,i(\cdot,k)}^{\text{PCF}} . In particular, let \mathcal{E}_{c}=\left_{PZ\,}\subseteq\Xi be an axis-aligned box, and let \mathcal{A}_{c}=[-\mathbf{1},\mathbf{1}]\subset\mathbb{R}^{6} be a hypercube, then, \mathcal{E}_{c} is simply a projection of that hypercube \mathcal{A}_{c} (compare with definition 5 ): \mathcal{E}_{c}=o_{c}+G_{c}\mathcal{A}_{c}. (14) Crucially, as each vertex \mathcal{V}_{c,i(\cdot,k)} is computed through algorithm 1 from \mathcal{E}_{c} , and, thus, ultimately from \mathcal{A}_{c} ( 14 ), it can be decomposed: \displaystyle\mathcal{V}_{c,i(\cdot,k)}^{\text{PCF}}=\left<\widetilde{o}_{c,i,k},[\widetilde{G}_{c,i,k}\ \widehat{G}_{c,i,k}],\widehat{G}_{I},[I_{6}\ \widehat{E}_{c,i,k}]\right>_{PZ\,} \displaystyle=\underbrace{\left<\widetilde{o}_{c,i,k},\widetilde{G}_{c,i,k},[\ ],I_{6}\right>_{PZ\,}}_{\text{Linearized term $\mathcal{V}_{c,i(\cdot,k)}^{\text{LIN}}$}}\oplus\underbrace{\left<\mathbf{0},\widehat{G}_{c,i,k},\widehat{G}_{I},\widehat{E}_{c,i,k}\right>_{PZ\,}}_{\text{Approx. error $\mathcal{V}_{c,i(\cdot,k)}^{\text{ERR}}$}}, \displaystyle\text{with }\mathcal{V}_{c,i(\cdot,k)}^{\text{LIN}}=\widetilde{o}_{c,i,k}+\widetilde{G}_{c,i,k}\mathcal{A}_{c} (15) Thus, also the linearized term of \mathcal{V}_{c,i(\cdot,k)}^{\text{PCF}} is a projection of the hypercube \mathcal{A}_{c} . In fact, \mathcal{A}_{c} is the shared latent space between \mathcal{V}_{c,i(\cdot,k)}^{\text{PCF}} and \mathcal{E}_{c} . In the context of neural network verification, such a shared latent space is used to impose constraints from the output space on the uncertain input of a network, thus, enclosing a preimage of the network: Lemma 1 (Preimage Enclosure [ P ] rop. 2) . koller2025out] Given a function f\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{m} , an input set \mathcal{X}=\left_{PZ\,}\subset\mathbb{R}^{n} , and a polytope \mathcal{U}=\left_{H\,}\subset\mathbb{R}^{m} , let \mathcal{Y}=\left<\widetilde{o}_{y},[\widetilde{G}_{y}\ \widehat{G}_{y}],G_{I},[I_{n}\ \widehat{E}_{y}]\right>_{PZ\,}=\text{\small{$\mathtt{enclose}$}}\left(f,\mathcal{X}\right)\subset\mathbb{R}^{m} and let f_{\mathcal{X}}^{-1}(\mathcal{U})=\{x\in\mathcal{X}\ |\ f(x)\in\mathcal{U}\} . Then, \displaystyle f_{\mathcal{X}}^{-1}(\mathcal{U})\subseteq\mathcal{X}|_{C\leq d}=\left\{o_{x}+\sum_{i=1}^{n}\alpha_{(i)}G_{x(\cdot,i)}\ \right| \displaystyle\left.\alpha\in\mathcal{A}=[-\mathbf{1},\mathbf{1}],\,C\mathcal{A}\leq d\right\}, where \displaystyle\qquad C=A\widetilde{G}_{y},\qquad d=b-A\widetilde{o}_{y}+|A\widehat{G}_{y}|\mathbf{1}. The preimage enclosure \mathcal{X}|_{C\leq d} is effectively a constrained zonotope [ 44 , Def. 3] , except that they are defined with equality constraints in the original paper. Proof. The proof can be found in appendix B . ∎ We generalize lemma 1 to general functions, and, in particular, use it on the function computed by algorithm 1 (mapping from the pose space \Xi to the PCF space in \mathbb{R}^{2} ). Considering our problem statement ( section II-D ), the preimage enclosure must contain the true pose \xi^{*}\in\Xi , 1 1 1 If \xi^{*}\not\in\mathcal{E}_{c} , lemma 1 can return the empty set \mathcal{E}|_{C\leq d}=\emptyset . which is unobservable, and thus difficult to find \mathcal{U}\subset\mathbb{R}^{2} in the PCF space for lemma 1 to be applicable. Intuitively, \mathcal{U} must contain the (unobservable) vertex V_{i(\cdot,k)}^{*} produced by \xi^{*} . This guarantees that the constraints C_{c},d_{c} we eventually obtain from lemma 1 keep \xi^{*} in the set \mathcal{E}_{c}|_{C_{c}\leq d_{c}} . We construct \mathcal{U} by choosing pixels \mathcal{Q}_{c,i,k}^{*}\subseteq[w]\times[h] from the given image I^{*} such that V_{i(\cdot,k)}^{*} is contained. More formally, we require that it holds: \mathcal{V}_{c,i(\cdot,k)}^{*}=\mathcal{Q}_{c,i,k}^{*}\oplus\mathcal{D}\subset\mathbb{R}^{2}\quad\implies\quad V_{i(\cdot,k)}^{*}\in\mathcal{V}_{c,i(\cdot,k)}^{*}, (16) where \mathcal{D}=[-\mathbf{1},\mathbf{1}]/2\subset\mathbb{R}^{2} captures the discretization error during the image creation ( 6 ). Please note that there is ambiguity in the pixels that could contain V_{i(\cdot,k)}^{*} due to the surjection during the image creation ( definition 3 ). For the remainder of this section, we add all turned-on pixels in \mathcal{V}_{c,i(\cdot,k)} to \mathcal{Q}_{c,i,k}^{*} , which trivially fulfills this requirement ( 16 ) as it must hold V_{i(\cdot,k)}^{*}\in\mathcal{V}_{c,i(\cdot,k)} due to the outer approximation ( proposition 2 ). As \mathcal{Q}_{c,i,k}^{*} is constructed from the observed image I^{*} , we refer to them as witness pixels . We further discuss the ambiguity and possible removals from the witness pixels \mathcal{Q}^{*}_{c,i,k} in section IV . Finally, to apply lemma 1 , we enclose \mathcal{U}_{c,i,k}\supseteq\mathcal{V}_{c,i(\cdot,k)}^{*} using ( 11 ), and impose the resulting constraints C_{c,i,k} , d_{c,i,k} on \mathcal{E}_{c} . Crucially, all vertices k\in[\nu_{i}] share the same latent space, and \xi^{*} must be contained in the intersection of all constraints. Thus, for each uncertain pose \mathcal{E}_{c} , c\in[\zeta] , we collect the constraints of all vertices in all polygons in joint variables C_{c} , d_{c} . Then, the final certified pose estimate is given by: \mathcal{E}^{*}=\mathcal{E}_{1}|_{C_{1}\leq d_{1}}\cup\ \cdots\ \cup\ \mathcal{E}_{\zeta}|_{C_{\zeta}\leq d_{\zeta}}\subseteq\Xi. (17) By the pose candidates partitioning the pose space \Xi and the soundness of lemma 1 , it is ensured that \xi^{*}\in\mathcal{E}^{*} if \xi^{*}\in\Xi . This process can again be computed batch-wise to be feasible online. Please note that in algorithm 2 , if an irrelevant candidate pose \mathcal{E}_{c} is filtered in phase 1, we set the constraint C_{c}=\mathbf{0} and d_{c}=-1 to indicate that \xi^{*}\notin\mathcal{E}_{c} as the constraint is infeasible. The file ’’./figures/externalize-twocol/.pdf‘‘ does not exist and has to be exported first. Please re-compile with tikz externalize and shell escape enabled. Check the documentation for details. Fig. 5: Certified pose estimation ( algorithm 2 ): (a) Given an image I^{*} and a (simple) target \mathcal{T}^{\text{TCF}} ( \rho=1 ), (b) the vertices of the (unobservable) target \mathcal{T}^{\text{PCF}} are contained in the witness pixels \mathcal{Q}_{c,1,k} , k\in[\nu_{1}] , enabling us to impose constraints C_{c,1,k}\leq d_{c,1,k} on a pose candidate \mathcal{E}_{c}\subseteq\Xi via the shared latent space to (c) obtain a tight certified estimate of \xi^{*}\in\mathcal{E}_{c}|_{C_{c}\leq d_{c}} . A visual example of this procedure is shown in fig. 5 : Given an image I^{*} and a pose candidate \mathcal{E}_{c} , we can compute the witness pixels \mathcal{Q}^{*}_{c,1,k} for each vertex k\in[\nu] . Then, as each pre-computed vertex \mathcal{V}_{c,1(\cdot,k)}^{\text{PCF}} is a projection of a latent space (shown in fig. 5 b floating above each vertex, respectively), we can impose constraints on this latent space by considering \mathcal{Q}^{*}_{c,1,k} and the approximation errors while computing \mathcal{V}_{c,1(\cdot,k)}^{\text{PCF}} ( 15 ) using lemma 1 . Moreover, as each \mathcal{V}_{c,1(\cdot,k)}^{\text{PCF}} is a projection of the same latent space, the final certified pose estimate is given by the intersection of all these constraints ( fig. 5 c). Theorem 1 (Image to Pose) . Given a target \mathcal{T}\subset\mathbb{R}^{3} ( definition 2 ), a camera C_{f,w,h} ( definition 3 ), an image I^{*}\in\mathbb{B}^{w\times h} produced by an (unobservable) true pose \xi^{*}\in\Xi , and \zeta pose candidates partitioning \Xi for which algorithm 1 is pre-computed, algorithm 2 computes a certified pose estimate: \mathcal{E}^{*}\subseteq\Xi\quad\text{s.t.}\quad\xi^{*}\in\mathcal{E}^{*} with a computational complexity of \mathcal{O}(\zeta\rho\nu_{i}wh) . Proof. The proof can be found in appendix B . ∎ IV Witness Pixels and Where to Find Them In this section, we consider possible removals from the set of witness pixels \mathcal{Q}_{c,i,k}^{*}\subseteq[w]\times[h] ( 16 ). Any removal from \mathcal{Q}_{c,i,k}^{*} helps to impose stricter constraints on the pose candidate \mathcal{E}_{c} ( lemma 1 ), thereby obtaining a tighter certified pose estimate \mathcal{E}^{*} . We begin by discussing the ambiguity due to the surjection in the image generation ( definition 3 ) in more detail. In particular, there is ambiguity regarding which pixel contains the (unobservable) vertices V_{i(\cdot,k)}^{*} of the true pose \xi^{*} , and one must consider all these pixels as witnesses when imposing constraints. This ambiguity is exemplarily illustrated in fig. 6 a-c: Different poses \xi^{(a)},\xi^{(b)},\xi^{(c)}\in\Xi result in different positions of V_{i(\cdot,k)}^{*} of the transformed target \mathcal{T}^{\text{PCF}} , but all result in the same image I^{*} . The file ’’./figures/externalize-twocol/.pdf‘‘ does not exist and has to be exported first. Please re-compile with tikz externalize and shell escape enabled. Check the documentation for details. Fig. 6: Ambiguity of an (unobservable) target \mathcal{T}^{\text{PCF}} given an image I^{*} (shown for \tau=0 in zoomed-in view): (a-c) Possible orientations of \mathcal{T}^{\text{PCF}} resulting in the same image I^{*} . (d) Witness pixels must be on the boundary of the target given the pre-computed \mathcal{V}_{c,i(\cdot,k)}^{\text{PCF}} . Despite this ambiguity, it is possible to better bound the witness pixels \mathcal{Q}_{c,i,k}^{*} than choosing the trivial solution of selecting all turned-on pixels contained in \mathcal{V}_{c,i(\cdot,k)}^{\text{PCF}} , which is possible as \mathcal{V}_{c,i(\cdot,k)}^{\text{PCF}} is computed outer-approximatively ( proposition 2 ). To avoid additional ambiguity, we only apply this tightening on standalone vertices k , i.e., vertices for which their uncertain set \mathcal{V}_{c,i(\cdot,k)}^{\text{PCF}} does not overlap with other vertices of the same polygon or other polygons altogether: \displaystyle\begin{split}\forall k^{\prime}\in[\nu_{i}]\setminus\{k\}\colon\qquad&\mathcal{V}_{c,i(\cdot,k)}^{\text{PCF}}\cap\mathcal{V}_{c,i(\cdot,k^{\prime})}^{\text{PCF}}=\emptyset,\\ \text{and }\forall i^{\prime}\in[\rho]\setminus\{i\}\colon\qquad&\mathcal{V}_{c,i(\cdot,k)}^{\text{PCF}}\cap\widehat{\mathcal{P}}_{c,i^{\prime}}^{\text{PCF}}=\emptyset.\end{split} (18) Thus, we can look at each remaining vertex individually and do not consider edge cases with overlaps to other parts of the target 2 2 2 This restriction can be loosened for some vertices where we know that overlapping does not compromise soundness, e.g., vertices constituting the corner of the convex hull of \mathcal{T} cannot have turned-on pixels of other vertices further outside by definition. . Please note that in our noise threat model ( definition 4 ), we assume that the edge is reliably detected by the event-based camera [ 14 ] ; thereby guaranteeing that V_{i(\cdot,k)}^{*} is within a turned-on pixel. However, there might be additional turned-on pixels outside the target and some pixels inside the target might be turned off. Conversely, the latter case helps directly to impose tighter constraints as these pixels do not get added to \mathcal{Q}_{c,i,k}^{*} in the first place. Using ( 18 ) and the convexity of each polygon of \mathcal{T}^{\text{PCF}} ( definition 2 ), we can infer that V_{i(\cdot,k)}^{*} has to be on the boundary of the restricted region, i.e., the pixels within \mathcal{V}_{c,i(\cdot,k)}^{\text{PCF}} ( fig. 6 d); however, the noise makes this boundary fuzzy, i.e., \tau additional pixels might be turned on. By considering the orientation of the transformed target of our pose candidate \mathcal{E}_{c} , we can determine the \tau farthest out pixels, which we always have to include in \mathcal{Q}_{c,i,k}^{*} , and additionally add the boundary pixels of the remaining pixels to \mathcal{Q}_{c,i,k}^{*} . This ensures that all boundary pixels are selected, thereby guaranteeing that V_{i(\cdot,k)}^{*} is contained in \mathcal{V}_{c,i(\cdot,k)}^{*} ( 16 ). For \tau=0 , it is also possible to restrict the ambiguous pixels using geometric considerations. As we optimize for speed in the online setting, we only use a single, basic geometric consideration, and leave more complex considerations for future work. As all remaining witness pixels \mathcal{Q}_{c,i,k}^{*} on the boundary are turned on, there has to exist an edge of \mathcal{T}^{\text{PCF}} crossing these pixels. In particular, this edge must cross the left- and right-most witness pixels with respect to the direction orthogonal to the boundary. Thus, any triangle spanned by a witness The file ’’./figures/externalize-twocol/.pdf‘‘ does not exist and has to be exported first. Please re-compile with tikz externalize and shell escape enabled. Check the documentation for details. Fig. 7: Geometric consideration: Triangle construction of the selected witness pixels ( \mathbf{\circ} ) without pixel expansion. pixel q\in\mathcal{Q}_{c,i,k}^{*} and the left- and right-most witness pixel, expanded to cover the entire pixel ( 16 ), has to intersect with all remaining witness pixels q^{\prime}\in\mathcal{Q}_{c,i,k}^{*} ( fig. 7 ). Otherwise, q cannot contain the vertices V_{i(\cdot,k)}^{*} of the true pose \xi^{*} as q^{\prime} would not be turned on then. As a special case of this geometric consideration, if a pixel q\in\mathcal{Q}_{c,i,k}^{*} only has one turned-on neighboring pixel, q is the only witness pixel as you cannot span such a triangle using another pixel such that it intersects with the selected pixel q . After the witness pixels \mathcal{Q}_{c,i,k}^{*} are found, we have to determine the certified estimate of the vertex \mathcal{V}_{c,i(\cdot,k)}^{*} ( 16 ). This is realized by expanding the set to cover the entire pixel area using \mathcal{D}=[-\mathbf{1},\mathbf{1}]/2 , shown visually in yellow in fig. 6 d and fig. 7 rather than individual points in \mathcal{Q}_{c,i,k}^{*} , and then applying lemma 1 to obtain the constraints for all joint witness pixels. Future work could also consider loosening ( 18 ), e.g., by applying a similar technique on inner corners of a target, which are currently ignored due to the second condition of ( 18 ). This could, e.g., be useful on the inner corners of the digit 0 in fig. 2 . V Experimental Results We have implemented our approach 3 3 3 Code available at: https://github.com/toladnertum/paper-pose-repeatability using the MATLAB toolbox CORA [ 3 ] , which offers a wide range of set-based computing functionalities, and conducted all experiments on an 11th Gen Intel(R) Core(TM) i7-11800H processor with 64 GB of memory. Evaluation details and additional experiments are given in appendix C . V-A Experiment on Synthetic Data: Landing Plane We simulate a landing plane with the camera facing the runway. The camera has a resolution of 200\times 200 and a focal length f=250 ( 3 ). The pose space \Xi is chosen large enough to capture the entire landing maneuver: \displaystyle\begin{split}\Xi&=[-50,50]\times[-50,150]\times[50,350]\\ &\times[0,90]\times[-5,5]\times[-5,5]\subset\mathbb{R}^{6},\end{split} (19) where the values are chosen to match a typical landing maneuver, 4 4 4 Angles are converted to radians in the implementation. and restricted to where the target is visible on the image. Examples, along with the resulting certified pose estimations, are visualized in fig. 8 : We notice that our approach can correctly and tightly identify the pose, particularly when the camera is closer to the target. Please note that for larger distances, many images indeed become very similar visually ( fig. 8 a-b), and thus the exact pose becomes more ambiguous due to the surjection of the image generation ( definition 3 ). The file ’’./figures/externalize-twocol/.pdf‘‘ does not exist and has to be exported first. Please re-compile with tikz externalize and shell escape enabled. Check the documentation for details. The file ’’./figures/externalize-twocol/.pdf‘‘ does not exist and has to be exported first. Please re-compile with tikz externalize and shell escape enabled. Check the documentation for details. Fig. 8: Landing plane scenario: Images and resulting certified pose estimates \mathcal{E}^{*} . In our experiment, we randomly sample 100 poses from \Xi and generate images using different targets on a runway ( fig. 2 ). Then, we recover the poses again using our approach. The results are shown in table I . For each sample, the true pose is contained in the obtained certified pose estimate, validating the soundness of our approach. We note that the initial filtering of the pose candidates ( algorithm 2 , line 7 ) can rule out many pose candidates, which is only possible due to a tight computation of the offline part ( section III-A ), as a larger approximation error there results in a larger area of the image where the target could be for each pose candidate. On the remaining pose candidates, we impose constraints based on the witness pixels of the images. As shown in table I , this again substantially reduces the volume of \mathcal{E}^{*} while barely increasing the computation time. TABLE I: Comparison of computation time and resulting volume of the certified position estimate \mathcal{E}^{*} using different targets: Initial filtering using the offline pre-computations (baseline, Filter ), and our full approach ( Ours ). #Candidates Online Time [s] Norm. Vol. [%] Target Offline [h] \zeta Filter Filter Ours Filter Ours 30 1.86 5979 41.6 \pm 9.3 0.23 \pm 0.08 2.81 \pm 1.02 1.29 \pm 0.33 \mathbf{0.16} \pm \mathbf{0.41} R 0.53 3966 28.5 \pm 6.9 0.12 \pm 0.04 2.10 \pm 0.82 4.28 \pm 1.24 \mathbf{0.30} \pm \mathbf{0.97} Stripes 0.17 1405 30.8 \pm 7.2 0.05 \pm 0.02 2.10 \pm 0.78 4.82 \pm 1.24 \mathbf{0.64} \pm \mathbf{1.71} V-B Experiment on Real-World Data: Sign Detection We additionally demonstrate our approach on a real-world dataset consisting of 138 images recorded by a SilkyEvCam event-based camera with calibrated true poses \xi^{*} using a Vicon motion capture system. The camera has an image resolution of 640\times 480 and focal length f=533.33 . In this experiment, we consider the task of detecting a slow-moving vehicle sign in front of the camera, with a large enough pose space \Xi for the considered setting: \displaystyle\begin{split}\Xi&=[-0.5,0.5]\times[-0.5,0.5]\times[0.5,1.5]\\ &\times[-5,5]\times[-5,5]\times[-15,15]\subset\mathbb{R}^{6}.\end{split} (20) The file ’’./figures/externalize-twocol/.pdf‘‘ does not exist and has to be exported first. Please re-compile with tikz externalize and shell escape enabled. Check the documentation for details. Fig. 9: Example image of recorded dataset: (a) raw image ( Raw ), and (b) with basic denoising applied ( Cleaned ). Method #Cand. Time [s] Vol. [%] Raw 88.7 \pm 20.2 3.39 \pm 0.80 5.54 \pm 1.84 Cleaned 48.6 \pm 15.2 2.14 \pm 0.69 1.17 \pm 0.50 TABLE II: Results using our approach ( Ours ) on both methods shown in fig. 9 . We show in fig. 9 a an example image from this dataset. Please note that the event-based camera reliably detects the edges of the sign, with additional noise spread across the entire image. We empirically determined the maximum noise level \tau=(w\cdot h)\cdot 1\%=3072 pixels, and compare our approach on the raw images from the camera and on images with basic denoising applied ( fig. 9 b). We initially partition the pose space \Xi into \zeta=666 candidates and pre-compute the respective properties offline. Subsequently, online, our approach quickly and accurately localizes the true pose \xi^{*} on all images using both methods. These results are shown in table II . We again note that the true pose was contained in the certified pose estimate for this experiment. Please note that the cleaned images substantially reduce the online computation time as fewer candidates have to be considered. Thus, any progress in formal filtering methods, such as explored in [ 43 ] , directly benefits our approach. V-C Standalone Experiment on Sound Image Enclosures We want to stress that our sound image enclosure ( section III-A ) also has applications beyond pose estimation, such as in abstract rendering [ 26 ] . Thus, we provide additional results solely on the image enclosure in this experiment. We first show some qualitative examples in fig. 10 depicting the tightness of our approach: We generate 5 random samples from an uncertain pose \mathcal{E} and compute the resulting transformations ( definition 3 ). Subsequently, the enclosure \mathcal{V}_{i(\cdot,k)}^{\text{PCF}} using the entire \mathcal{E} is computed ( proposition 2 ). Thus, the vertices of the computed samples must be contained in the enclosures. The results demonstrate the tightness of our approach in (a) rotational uncertainty, (b) zoom uncertainty (z-axis), and (c) translational uncertainty (x- and y-axis), as the vertices of the samples are spread within the entire respective set \mathcal{V}_{i(\cdot,k)}^{\text{PCF}} . Please note that areas in the set that do not contain any samples do not necessarily reflect outer approximation. As a measure of this outer approximation, the average ratio between the interval hull radius of the linearized term and the approximation error in ( 15 ) is 18.6\% in the experiments presented above; details on this measure are provided in section C-A . The file ’’./figures/externalize-twocol/.pdf‘‘ does not exist and has to be exported first. Please re-compile with tikz externalize and shell escape enabled. Check the documentation for details. Fig. 10: Qualitative examples on the sound image enclosure: (a) Angle perturbation on target 30 . (b) Zoom uncertainty ( z -axis) on target R . (c) Translational uncertainty ( x - and y -axis) on target Stripes . Target \mathcal{T}^{\text{PCF}} is shown for the center of the perturbed pose \mathcal{E} , respectively. V-D Ablation Studies Ablation studies and additional experiments are provided in section C-B . VI Related Work While several techniques exist to localize an object [ 39 , 13 , 7 , 23 ] , including approaches based on deep learning [ 8 ] , obtaining formal guarantees of the pose solely from an image is largely unexplored: The local robustness of deep-learning-based object detectors [ 10 ] and pose estimators [ 35 , 26 ] can be verified. While the formal neural network verification has progressed rapidly in recent years [ 29 ] , their focus is limited to verifying local robustness properties in image classification [ 27 ] . The geometric transformations of the camera ( definition 3 ) can be modelled as a neural network [ 42 ] , such that, when concatenated with a perception-based control network, robustness queries can be utilized to verify the control actions of local pose spaces. Image-invariant regions in the pose space can also be utilized to verify vision-based controllers [ 22 ] . We refer interested readers to this survey [ 36 ] for further approaches applying formal verification to vision-based deep learning. However, the black-box nature of neural networks prevents giving global guarantees of their correctness [ 19 ] . For noisy images, the modeling of the camera as a network also enables the formal noise reduction and obtaining certified pose estimates [ 43 , 41 ] ; however, these approaches do not consider the full six-dimensional pose space \Xi we are able to verify in our approach. Certified pose estimation can also be obtained from partial point clouds [ 48 , 45 ] , including the relative change of position between two frames [ 15 ] . Conformal prediction [ 4 , 47 ] can also provide guarantees under the considered dataset. It is also worth noting that global pose localizations can be obtained by using QR codes as landmarks [ 49 , 37 ] , but the precise location of the agent relative to the QR code remains unknown. Our approach could also be used in set-based observers [ 9 , 1 , 40 ] to update the current set of states given an image. VII Conclusion and Next Steps We show that certified pose estimates can be obtained solely from an image and a known target geometry. Our experiments demonstrate the effectiveness of our approach, thereby reliably localizing an agent relative to the target in just over a second. This potentially opens the door to real-time capabilities if implemented and optimized in a more efficient programming language than MATLAB, and GPU acceleration can be applied as all operations are based on simple matrix manipulations in a batch-wise manner. We acknowledge several limitations of this work, each of which opens up interesting research questions that we leave for future investigation. Firstly, our approach assumes context in the current setting, e.g., that the target is clearly visible in the image. However, this might not occur in practice, as weather conditions can affect the visual perception, and malicious actors can manipulate the target. Secondly, noisy images make finding a small subset of witness pixels to refine the offline pre-computed pose candidates more challenging. While we show that our approach still efficiently localizes the agent even for unprocessed images, we also show that denoising helps to find a tighter certified pose estimate, and further research on both the algorithm to find the witness pixels as well as the refinement through lemma 1 would benefit our approach as well. Thirdly, we only consider a single (target) object present in the image, which might be unrealistic in complex settings. Please note that if the images of the respective objects are separated and the distances between multiple objects are known, one can compute an intersection of the obtained cones ( fig. 8 ) to obtain an even tighter result due to the different angles of the object with respect to the camera. Despite these limitations, we believe that our work is already a significant step towards guaranteeing the safety of autonomous agents in safety-critical settings. Appendix A On Set-Based Computing A-A Polynomial Zonotopes and Image Enclosures We construct a running example to illustrate the image enclosure ( proposition 1 ) using polynomial zonotopes ( definition 5 ) in this section. For simplicity, we only use regular polynomial zonotopes [ 30 ] ; the construction with their matrix equivalent is analogous. Consider an uncertain angle \theta\in\mathcal{O}=[\pi/6,\,\pi/2]\subset\mathbb{R} . As a polynomial zonotope, this set is represented by: \mathcal{O}=\left<[\nicefrac{{\pi}}{{3}}],[\nicefrac{{\pi}}{{6}}],[\ ],[1]\right>_{PZ\,}. (21) Thus, the offset of \mathcal{PZ} is at the center of \mathcal{O} with a single generator spanning the radius to cover the entire range. For multiple angles [\theta_{x}\ \theta_{y}\ \theta_{z}]\in\mathcal{O}^{\prime}\subset\mathbb{R}^{3} , the construction is analogous: \mathcal{O}^{\prime}=\left<\text{\small{$\mathtt{center}$}}\left(\mathcal{O}^{\prime}\right),\text{\small diag}\left(\text{\small{$\mathtt{radius}$}}\left(\mathcal{O}^{\prime}\right)\right),[\ ],I_{3}\right>_{PZ\,}. (22) The generator matrix is given by a diagonal matrix, as the angles can vary independently from each other. In our approach, we are required to enclose the output of the \sin(x) and \cos(x) functions given an uncertain input ( algorithm 1 , line 3 ). We illustrate this process in fig. 11 : To obtain a tight enclosure, we first determine the domain \mathcal{D} by computing bounds of the input angles \mathcal{O} . Within this domain, we compute an approximation p(x) of f(x) using regression and determine the maximal approximation error d within this domain. Represented as a polynomial zonotope, these two steps can be computed using ( 8 ) and ( 7 ), respectively. The file ’’./figures/externalize-twocol/.pdf‘‘ does not exist and has to be exported first. Please re-compile with tikz externalize and shell escape enabled. Check the documentation for details. Fig. 11: Example image enclosure of \sin(x) and \cos(x) on a given domain \mathcal{D} . For the angles in ( 21 ), the respective approximations and approximation errors are given by: \displaystyle p_{\sin}(x) \displaystyle=0.4851x+0.2981, \displaystyle d_{\sin} \displaystyle=0.0602,\text{ and} (23) \displaystyle p_{\cos}(x) \displaystyle=-0.8402x+1.3432, \displaystyle d_{\cos} \displaystyle=0.0374, which is also illustrated in fig. 11 . Thus, written as a polynomial zonotope, the enclosure is given by: \displaystyle\begin{split}&\left[\begin{matrix}\sin{(\mathcal{O})}\\ \cos{(\mathcal{O})}\end{matrix}\right]\subseteq\\ &\left<\left[\begin{matrix}0.8061\\ 0.4634\end{matrix}\right],\left[\begin{matrix}0.2540\\ -0.4399\end{matrix}\right],\left[\begin{matrix}0.0602&0\\ 0&0.0374\end{matrix}\right],[1]\right>_{PZ\,}\hskip-10.22226pt.\hskip-2.77779pt\hphantom{\scriptsize PZ}\hskip-34.5021pt\end{split} (24) Please note that here, the dependent generator matrix (second entry, definition 5 ) is not a diagonal matrix, as it is computed from the same uncertain angles \mathcal{O} and thus carries dependence. Carrying such dependencies through algorithm 1 enables us to exploit them in algorithm 2 by imposing constraints on the shared hypercube. A-B Uncertain Target Geometry Through Reference Points Please note that the transformation from TCF into CCF is linear in the given vertices V_{i}^{\text{TCF}} ( 2 ). For this reason, we can compute the transformation by computing ( 2 ), independently of the number of polygons and their vertices, using only three non-collinear reference points B^{\text{TCF}}\in\mathbb{R}^{3\times 3} , as any point p\in\mathbb{R}^{3} can be reconstructed from B^{\text{TCF}} as follows: p=\lambda_{(1)}B_{(:,1)}^{\text{TCF}}+\lambda_{(2)}B_{(:,2)}^{\text{TCF}}+\lambda_{(3)}B_{(:,3)}^{\text{TCF}}, (25) where \lambda\in\mathbb{R}^{3} is found by solving the linear system of equations: B^{\text{TCF}}\lambda=p. (26) Given uncertainty, this reformulation and reconstruction can directly be computed using ( 8 ) and ( 7 ). Moreover, it naturally enables us to introduce uncertainty in the shape of the target \mathcal{T} by adding uncertainty to \lambda . Let B=I_{3} , then any uncertainty added to \lambda directly results in uncertainty in the three axis directions. For planar targets ( fig. 1 ), i.e., where all polygons are oriented on the same hyperplane depicted by c=\left[\begin{matrix}0&0&1\end{matrix}\right]^{\top} , d=0 ( definition 1 ), we can choose B=[[I_{2}\ \mathbf{0}]^{\top}\ \mathbf{0}]\in\mathbb{R}^{3\times 3} , which effectively eliminates \lambda_{(3)} as B_{(\cdot,3)}=\mathbf{0} . A-C Convex Hulls of Uncertain Vertices To obtain a tight convex hull over all \mathcal{V}_{i(\cdot,k)}^{\text{PCF}} to compute pixel containment in the entire polygon, we deploy an algorithm based on support functions summarized in algorithm 3 . Algorithm 3 Convex Hull Using Support Functions 1: Uncertain vertices \mathcal{V}_{i}^{\text{PCF}} 2: Gather directions C_{i}\in\mathbb{R}^{\gamma\times 2} , init. d\leftarrow\mathbf{0}\in\mathbb{R}^{\gamma} \triangleright Support function enclosure 3: for j\in[\gamma] do \triangleright ( fig. 12 ) 4: d_{i(j)}\leftarrow\max_{k\in[\nu_{i}]}\text{\small{$\mathtt{supportFunc}$}}(\mathcal{V}_{i(\cdot,k)}^{\text{PCF}},\,C_{i(j,\cdot)}) \triangleright ( 27 ) 5: return \widehat{\mathcal{P}}_{i}^{\text{PCF}}\leftarrow\left_{H\,}\subset\mathbb{R}^{2} \triangleright \widehat{\mathcal{P}}_{i}^{\text{PCF}}\supseteq\text{\small{$\mathtt{convHull}$}}\left(\mathcal{V}_{i}^{\text{PCF}}\right) Let us first recall the definition of a support function [ 17 , Def. 1] : Given a set \mathcal{S}\subset\mathbb{R}^{n} and a direction a\in\mathbb{R}^{n} , \displaystyle\begin{split}\text{\small{$\mathtt{supportFunc}$}}\left(\mathcal{S},\,a\right)=\min&\quad b\in\mathbb{R},\\ \text{s.t.}&\quad\forall s\in\mathcal{S}\colon a^{\top}s\leq b.\end{split} (27) Thus, \mathcal{H}=\left_{H\,} forms a constraint for a half-space such that \mathcal{S}\subseteq\mathcal{H} . For multiple constraints, i.e., A\in\mathbb{R}^{\gamma\times n} with b\in\mathbb{R}^{\gamma} computed for each constraint individually, \mathcal{P}=\left_{H\,} forms a polytope such that \mathcal{S}\subseteq\mathcal{P} . If \mathcal{S} is represented as a polynomial zonotope, the inequality in ( 27 ) is often not strict [ 30 , Prop. 7] . The file ’’./figures/externalize-twocol/.pdf‘‘ does not exist and has to be exported first. Please re-compile with tikz externalize and shell escape enabled. Check the documentation for details. Fig. 12: Example of the support function enclosure for a target with a single polygon ( \rho=1 ) with uncertain vertices \mathcal{V}_{1}^{\text{PCF}} via algorithm 1 , for a pose \mathcal{E} with perturbed angles \theta_{x},\theta_{y},\theta_{z} by 10 degrees. In our case, for each polygon i\in[\rho] , \mathcal{S}_{i}=\cup_{k\in[\nu_{i}]}\mathcal{V}_{i(\cdot,k)}^{\text{PCF}} (28) to obtain an enclosure of the respective polygon \widehat{\mathcal{P}}_{i}^{\text{PCF}}\subset\mathbb{R}^{2} . By construction, any A_{i}\in\mathbb{R}^{\gamma\times 2} will result in a sound enclosure; however, we deploy the following heuristics to obtain tight results: (i) To preserve the overall shape, we choose directions orthogonal to the edges of the polygon, which are computed via the offset of two subsequent uncertain vertices \mathcal{V}_{i(\cdot,k)}^{\text{PCF}} , \mathcal{V}_{i(\cdot,k+1)}^{\text{PCF}} ( definition 5 ). (ii) To sharpen the corners, we have found that it helps to also add the direction from the center of the polygon, computed by the mean of the vertex offsets, to each vertex offset. An example with these directions is shown in fig. 12 b. Please note that if two subsequent uncertain vertices are influenced by \mathcal{E} to a different degree, the direction orthogonal to the edge (heuristic (i)) can be very conservative. For example, compare the bottom two vertices with the top two vertices in fig. 12 b, and notice the gap between the top right vertex and the half-space boundary to its right. This can be iteratively refined by selecting the points v_{i,k}\in\mathcal{V}_{i(\cdot,k)}^{\text{PCF}} , v_{i,k+1}\in\mathcal{V}_{i(\cdot,k+1)}^{\text{PCF}} for which the support function is realized ( 27 ), respectively, and then (iii) additionally computing the support function in the direction orthogonal to the line connecting v_{i,k} and v_{i,k+1} . Appendix B Proofs We give all missing proofs in this section in the order they appear in the main body of the paper. We also restate all statements for convenience. See 2 Proof. The implication follows as each applied operation to compute I is outer-approximative. In particular, to compute \widehat{\mathcal{P}}_{i}^{\text{PCF}} , the operations defined in proposition 1 , ( 8 ) and ( 7 ) are used, and the support function enclosure ( 27 ) is computed for polynomial zonotopes using [ 30 , Prop. 7] . Please note that the number of generators to represent \mathcal{V}_{i(\cdot,k)}^{\text{PCF}} as a polynomial zonotope is constant, as we initially always have 6 generators representing the uncertainty in \Xi\subset\mathbb{R}^{6} , and the number of operations to obtain each \mathcal{V}_{i(\cdot,k)}^{\text{PCF}} is constant, each only adding a fixed number of generators: Given a polynomial zonotope \mathcal{PZ}_{1}\subset\mathbb{R}^{n} , proposition 1 adds at most n generators to \mathcal{PZ} . Let \mathcal{PZ}_{1} have h_{1} generators and a second \mathcal{PZ}_{2} have h_{2} generators with proper dimensions, then, applying ( 8 ) results in \mathcal{O}(h_{1}h_{2}) generators, and applying ( 7 ) results in h_{1}{+}h_{2} generators. Thus, in algorithm 1 , all computations leading up to the convex hull (line 2 ) are negligible in the computational complexity analysis. As we compute this convex hull using support functions in \gamma=3\nu_{i} directions ( section A-C ), and as the number of polygon vertices \nu_{i}\ll w\cdot h , the overall complexity is dominated by the pixel inclusion check in line 14 and is thus given by \mathcal{O}(\rho wh) . Please note that both the inner for loop in algorithm 1 and algorithm 3 can be computed efficiently in a batch-wise manner. ∎ See 1 Proof. While the original statement in [ 32 , Prop. 2] is given for zonotopes [ 30 , Def. 2] , we have polynomial zonotopes as inputs. However, the approach is still applicable as the input set \mathcal{X} is effectively a zonotope as it has the identity as exponent matrix [ 30 , Def. 2] , we take the linearized (zonotopic) part \widetilde{G}_{y} to compute C , and the computation of d is outer-approximative via a zonotope enclosure [ 30 , Prop. 5] . ∎ See 1 Proof. The soundness of our approach follows from the outer-approximative computation in algorithm 1 ( proposition 2 ) and the application of lemma 1 , which ensures that if \xi^{*}\in\mathcal{E}_{c} , the constraints C_{c}\leq d_{c} only restrict \mathcal{E}_{c} such that \xi^{*}\in\mathcal{E}_{c}|_{C_{c}\leq d_{c}} . Given the pre-computation of all candidate poses using algorithm 1 , the remaining work for each candidate, polygon, and vertex, is finding the witness pixels, which can be done in \mathcal{O}(wh) using the pre-computed bitmap, and the application of lemma 1 given by \mathcal{O}(\gamma wh) . As \gamma is a small constant ( section A-C ), the overall computational complexity is given by \mathcal{O}(\zeta\rho\nu_{i}wh) . ∎ Appendix C Evaluation Details and Ablation Studies C-A Evaluation Details We assume that a pixel of an image is turned on if the polygon \mathcal{T}^{\text{PCF}} intersects with the respective area ( fig. 13 a). This assumption is reasonable for event-based cameras. Please note that this intersection has to be computed whenever pixel containment is checked in the presented algorithms. The file ’’./figures/externalize-twocol/.pdf‘‘ does not exist and has to be exported first. Please re-compile with tikz externalize and shell escape enabled. Check the documentation for details. Fig. 13: (a) We assume pixels are turned on if the (unobservable) target \mathcal{T} intersects with the respective area of the pixel. (b) Pose candidates \mathcal{E}_{c} partitioning pose space \Xi in a hierarchical manner. We determine the pose space by analyzing the maximum poses at which anything meaningful is visible in the resulting image. Afterward, the pose candidates are determined by partitioning the pose space \Xi in a hierarchical manner ( fig. 13 b): Given a pose candidate \mathcal{E} , we pass \mathcal{E} through algorithm 1 , and analyze the ratio between the radius of the interval hull between the linear approximating generators and the error generators ( 15 ). If this ratio exceeds a certain threshold \delta\in\mathbb{R}_{+} , the pose candidate \mathcal{E} is split in half in each dimension – where we use sensitivity analysis to determine the dimensions to split – and the process is repeated. Otherwise, a sufficiently tight pose candidate \mathcal{E} is found and added to the list. The process starts with the entire pose space \mathcal{E}=\Xi . Usually, finding the pose candidates takes substantially less time than computing the subsequent properties of each pose candidate (e.g., pixel containments), and both are shown combined as offline computation time in this work. Please note that the target cannot be seen from some poses, and we filter these as well while partitioning \Xi , and are thus not visible in fig. 13 b. Moreover, we show the geometry of the targets used in our experiments in fig. 14 . The file ’’./figures/externalize-twocol/.pdf‘‘ does not exist and has to be exported first. Please re-compile with tikz externalize and shell escape enabled. Check the documentation for details. Fig. 14: Geometry of used targets: (a) 30 , (b) R , (c) Stripes , and (d) SlowVehicle . C-B Ablation Studies In this section, we give further insights into the hyperparameters of our approach using ablation studies. C-B 1 Ablating the image resolution. TABLE III: Ablation study on the image resolution. Image Resolution \textbf{\#Candidates }\zeta Filter Time [s] #Witness Pixels 100\times 100 286 24.5 \pm 3.5 1.47 \pm 0.46 \ \ \ \ \ \ 3.8 \pm 1.6 200\times 200 1405 29.5 \pm 5.7 2.17 \pm 0.50 4.2 \pm 1.4 300\times 300 1857 28.8 \pm 7.0 2.84 \pm 0.85 3.3 \pm 1.4 500\times 500 2592 30.1 \pm 6.1 4.50 \pm 1.15 2.8 \pm 1.1 The file ’’./figures/externalize-twocol/.pdf‘‘ does not exist and has to be exported first. Please re-compile with tikz externalize and shell escape enabled. Check the documentation for details. Fig. 15: Comparison of number of support function evaluation \gamma (showing zoomed-in view of setting in fig. 12 ): (a) only in directions of the edges, (b) + directions to corners, (c-d) + iterative refinement. We ablate in table III the effect of the image resolution on the results. Interestingly, despite requiring more pose candidates with larger image resolution, the average after the initial filtering is applied ( algorithm 2 , line 7 ) stays roughly constant and thus also the computation time. We also show the average number of witness pixels that have to be considered with each image resolution, confirming the efficiency of our approach. Please also note that the computational complexities in proposition 2 and theorem 1 can be improved by cropping a high-resolution image I\in\mathbb{B}^{w\times h} to the relevant part, and adjusting the application of lemma 1 due to this rescaling (not implemented). However, we did not implement this optimization to avoid distorting the overall evaluation results. C-B 2 Ablating the support function heuristics. In algorithm 1 , we discuss a convex hull enclosure by running \gamma support function evaluations. The detailed process is described in section A-C , and is also illustrated in fig. 12 . In this ablation study, we provide further insights by presenting qualitative examples of different heuristics for selecting support function directions in fig. 15 . In particular, we show the result for the direction orthogonal to the edge connecting the center of the respective vertices ( fig. 15 a), the directions to the vertices themselves ( fig. 15 b), and one additional iterative heuristic ( fig. 15 c-d): When evaluating the direction orthogonal to an edge, we obtain a point from each vertex where this support is realized ( 27 ). Connecting these two points, and again running a support function evaluation orthogonal to this line, usually gives a better outer approximation of the true shape. We have found that choosing \gamma>3\cdot\nu only has diminishing returns.