1.

Introduction

The global village enjoys the availability of data rich environment, but sometime suffers from an explosive growth of useless data known as the curse of dimensionality in the digital age. Thus, the scientific community has developed various pre- and post-processing techniques to deal with the curse of dimensionality. For example, a smart organization principle called compressive sensing.^{1, 2} Specifically, when one does not need the frequency information of those sinusoidal components, one shall not sense it with the Fourier transform (FT), but with a physical group wave packet called the wavelet transform (WT). Furthermore, the wavelet transform in compressive sensing can be viewed upon as preprocessing technique replacing the FT with the adaptive WT,³ which allows several super-mother wavelet kernels that each match the time evolving signal content, and therefore create a natural spatiotemporal preprocessing. For post-processing, the conventional data compressions or removing the redundancy in data such as JPEG, MPEG, face detection, etc., and dimensionality reduction (DR) algorithms, i.e., ISOMAP,⁴ local linear embedding,⁵ Laplacian eigenmap^{6, 7} and diffusion map.^{8, 9} They have been developed to discover the nonlinear manifold underlying complex datasets that traditional dimensionality reduction methods, e.g., principle component analysis¹⁰ and multidimensional scaling¹¹ could not do. In addition, more DR algorithms^{12, 13, 14, 15} have been developed by encoding objects as matrices or tensors or arbitrary order. A generalized framework for dimensionality reduction has been presented in Ref. 16.

The generic DR for video datasets is defined as follows. Since every lexicographical order of pixels of the i’th video frame, L×M pixels, forms a long vector [TeX:] $\vec X _t \in O(L \times M)$ ${\vec{X}}_t\in O(L\times M)$ , subscript t = 1, …,N, has its own intensity values, the video itself becomes an exceedingly high dimensional set of light spots O(L×M×N time-frames). All these light spots are contributing to the Haken's cooperative and competitive self-organization phenomena^{17, 18} yielding the collective or master degrees of freedom, e.g., facial pose angles, which drive all the underlying slaver degrees of freedom.

Szu¹⁹ has derived asymmetric weights W_{i, j} ≠ W_{j, i} which have the positive diagonal W_{i, i} ⩾ 0 and a Kirchhoff-like graph theory energy function K as the weighted least mean square (LMS) [TeX:] $\min\cdot K = \min\cdot\break \sum\nolimits_{i = 1}^N {\sum\nolimits_{j = 1}^N {W_{i,j} |\vec X _i - \vec X _j |} ^2 \ge 0}$ $\min ·K=\min ·{\sum }_{i=1}^N{\sum }_{j=1}^N{W_{i,j}|{\vec{X}}_i-{\vec{X}}_j|}^2\ge 0$ where an in-bound risk [TeX:] $R_j = \sum\nolimits_i {W_{i,j} } \ge 0$ $R_j={\sum }_i{W}_{i,j}\ge 0$ is different from the out-bound popularity [TeX:] $P_i = \sum\nolimits_j {W_{i,j} \ge 0}$ $P_i={\sum }_j{W}_{i,j}\ge 0$ , [TeX:] $\sum\nolimits_i {|\vec X _i |^2 P_i } \ne \sum\nolimits_j {|\vec X _j |} ^2 R_j$ ${\sum }_i|{\vec{X}}_i{|}^2{P}_i\ne {\sum }_j{|{\vec{X}}_j|}^2{R}_j$ and the off-diagonal terms are [TeX:] $ - 2\sum\nolimits_i {\sum\nolimits_j {W_{i,j} } } \vec X _i \cdot \vec X _j$ $-2{\sum }_i{\sum }_j{W}_{i,j}{\vec{X}}_i·{\vec{X}}_j$ .¹⁹ Thus, the Kirchhoff energy [TeX:] $K \equiv (\vec X _i,K_{i,j},\vec X _j) \ge 0$ $K\equiv ({\vec{X}}_i,K_{i,j},{\vec{X}}_j)\ge 0$ becomes the inner product of the Kirchhoff matrix operator K_{i, j} ≡ [(R_j + P_i/2)δ_{i, j} − W_{i, j}], [TeX:] $\vec X _i$ ${\vec{X}}_i$ and [TeX:] $\vec X _j$ ${\vec{X}}_j$ . In the traditional video pose nonlinear DR, the Gaussian distance among pixels of video images becomes symmetric, and then the Kirchhoff matrix operator K_i,j is reduced to the graph-Laplacian matrix: L_ij ≡ [d_iδ_ij − W_ij] where d_i ≡ (R_j + P_i/2). The ground state zero eigenvalue is the facial membership functions indicating the same person⁷ (a degenerated ground state will indicate more than one person). The eigenvectors of the next eigenvalue become the master order parameters whose inner products with each facial image are the directional cosine angles representing the turning pose ordering angles. Such a pose-sorting similarity measure refers to the heading angles such as left-to- right and up-to-down.

To deal with the curse of dimensionality in the persistent surveillance, different strategies mentioned above can be applied, but in the end, a potential loss of association among different sensory tracks, i.e., video and audio, may occur. The observer cannot answer “who speaks what, when and where.” In this paper, a video organization principle is given and demonstrated in a controlled persistent surveillance environment, which can be generalized for other applications such as i. smart grid infrastructure, ii. biomedical wellness web, and iii. hyperspectral data for precision farming, etc.

In persistence surveillance, video cameras are remotely set up for security reasons while low-cost audio recorders are hidden locally within the persistent surveillance field shown in Fig. 1. To reduce the video storage size requirement, one can extract facial poses from each video frame and store those facial boxes instead of the video, which reduces the storage size by 6 orders of magnitude (see Table 1). The face detections, by facial color hue, and extractions in video are implemented by a face detection (FD)²⁰ system on chip. Adding time stamps on facial boxes is not recommended because it may be insufficient to reconstruct time-order and takes extra time. For an example, when there is a crowd in a single camera, faces of a crowd may be blocked by each other, obstacles, or detected without enough size, these faces are ignored by face detection techniques. Moreover, when passengers move past each other, the face of unwanted people momentarily fills the location of the face of the person of interest. In the consequences, facial boxes cut from each video frame are labeled by time stamps but the order of facial boxes from each frame are still in random order. Due to the reasons mentioned above, the collection of facial poses in video over 10 s is stored in a randomized order for further process. Such a loss of temporal correlation requires a re-establishment of the association across different sensor modalities that may help to ascertain “who said what, when, and where.”

Fig. 1

In most persistent surveillance systems, multiple remote cameras are used for monitoring a ball field-sized area with local nondirectional audio recorders 24/7. In such a setup, hundreds of people are under surveillance at a time. The challenge for security personnel is to track people of interest within the crowds in accumulated video database over time. This challenging problem can be solved with the strategy we suggested in the beginning of this paper: removing redundancy but keeping the faces of passengers. The trade-off is that the collections of random faces from several cameras stored in the CPU for further processing are in random order.

Table 1

Persistent surveillance is commonly used from military to civil applications. The storage requirement of persistent surveillance is huge and content organization is complex due to the huge amount of video data. It is a challenge for security personnel to sort and search for specific intruders among enormous video data. Since human faces are the most typical surveillance targets, saving faces of passengers/intruders without redundant background information saves up to 6 orders of magnitude when considering storage volume.

For an example, a passenger was walking in an airport transit looking left, right, and left again for the exit sign and speaking to her son about “where is the exit?” Both of their facial boxes were collected in Fig. 2. In Fig. 2, facial poses were sorted from left to right and top to bottom by graph embedded dimensionality reduction algorithms such as Laplacian eigenmap, etc., that is good to pick out mug-shots of each person, but they cannot reconstruct the time-ordering of walking passengers which is necessary to associate with an acoustic manifold finding out what may have been spoken. On the opposite, in Fig. 2, video and audio were correlated by the reconstructed time-ordering of passengers in a video. Furthermore, the walking speed of a passenger could be determined from a set of time-ordered facial boxes alone, assuming only few facial boxes were ignored by the FD system on a chip. In the latest studies,^{21, 22} walking speed is correlated with the personality.

Fig. 2

This collection of facial poses of different passengers is stored in a randomized order in the computer for further processing. Current NDR techniques (sorting facial poses by similarity, left-to-left, right-to-right, etc.), yield results that do not reconstruct the time-ordering and cannot solve cross track association of video and audio. On the contrary, if we can precisely reconstruct the time-ordering of facial poses, the result will provide a method for cross track association between passengers and time-ordered audio recordings.

A time-order reconstruction requires the careful differentiation between the continuous notion of time versus the discrete sampling of time flowing known as the time-ordering in this paper. Thus, we begin with a concept of a clock, Newton's concept of time, which can mark 1 s time unit with a “tick and tock.” Then, the unit of time must be followed by another unit tick and tock to indicate the 2 s time-order. This fact of directional flow may be described by a product of triple correlation functions, [TeX:] $W_{t_i,t_j,t_k } W_{t_k,t_l,t_m }$ $W_{t_i,t_j,t_k}{W}_{t_k,t_l,t_m}$ , where the common node t_k represents a discrete sampling point of time.

In Sec. 2, we approximate the triple correlation products with a product of pair correlation functions for a computationally efficient sorting algorithm, which we call the zipper chain (ZC) algorithm. It works like a zipper, two rows of multiple “teeth,” mounted across each other alternatively. The underlying topology may be visualized as the time flow along a geodesic line, where two intertwined least mean square (LMS) minimums intersect. The ZC algorithm describes the product of paired correlations verified by a zip-chain event—an anchor face, say frontal β, has two nearest neighbors, A and C, while A and C have another two nearest neighbors, respectively. The time-order is determined if the anchor face β happens to be also the nearest neighbor of A and C. To choose an anchor face, the traditionally supervised desired output of the LMS Weiner matched filter becomes unsupervised, and is self-determined by the facial box dataset itself in two passes: the so-called local instances of good seeing determined by a self-referencing matched filter (SRMF) by Szu and Blodgett²³ in 1982. The first pass takes a uniform average of all faces, producing a blurred, but statistically correct, face at a specific pose with respect to the setup between multiple camera angles and the walking corridor [emulating the so-called astronomical imaging long exposure (LE) of a double star in order to catch an instance of good seeing to take a turbulent-free snapshot]. For our digital video post-processing, the second pass chooses a sharp short exposure (SE) to be the anchor face (which could be the frontal face for a narrow corridor and head-on setup of videos).

Another phenomenon of facial boxes extracted by face detection techniques is that facial boxes extracted from video are in different sizes and coordinates. A preprocessing of viewing transformation and registration for each facial box is necessary before time-ordering reconstruction. This preprocessing is introduced to overcome the change of facial boxes by a maximum overlapping central region by a morphological image processing focusing the binarized center of each face box to achieve the scale invariant peripheral vision²⁴ in Sec. 3. The ZC algorithm for time-ordered reconstruction of facial poses for association across different sensory is in Sec. 3. In Sec. 4, the impact of leak-through background information in maximum overlapped face boxes for the neighborhood determination is discussed. In addition, when the product of triple correlation is replaced by a pair-wise correlation, we have derived a fast approximation of embedding in line for facial pose similarity sorting in a short duration. The simulation of ZC is compared step-by-step against simpler similarity sorting results without the iterative re-check necessarily for the time-order sorting in Sec. 5. In Sec. 6, several possible applications of the algorithmic framework developed in this paper are briefly introduced before the conclusion in Sec. 6.

2.

Theory of Time-Order Reconstruction of Pictures

Understanding time through the simple observation of a clock is the key. One tick-tock of a clock is a record of time, but it may take more than one set of tick-tock's to tell the time-order. This time-order is used to track the flow of time by the changes. That is to say tick-tock and tick-tock. On the other hand, a static face can be regarded as a collection of pixels (L×M) with light intensities representing each pixel. This collection of pixels specifies a high dimensional vector space [TeX:] $\vec x _j \in O(L \times M)$ ${\vec{x}}_j\in O(L\times M)$ with respect to a set of L×M Cartesian coordinates, one per pixel. Given any specific face, [TeX:] $\vec x _j$ ${\vec{x}}_j$ , there are two nearest neighbor frames of facial poses, [TeX:] $\vec x_i,\vec x_k$ ${\vec{x}}_i,{\vec{x}}_k$ except the first and last frames. In other words, we may need to introduce more than one pair correlation [TeX:] $W_{i,j} (\vec x_i,\vec x_j)$ $W_{i,j}({\vec{x}}_i,{\vec{x}}_j)$ of the i’th tick and the j’th tock time subscript; e.g., [TeX:] $W_{i,j} (\vec x _i,\vec x _j)W_{l,m} (\vec x _l,\vec x _m)$ $W_{i,j}({\vec{x}}_i,{\vec{x}}_j)W_{l,m}({\vec{x}}_l,{\vec{x}}_m)$ where the l’th tick must follow j’th tock as the necessary condition with two more faces [TeX:] $(\vec x _l,\vec x _m)$ $({\vec{x}}_l,{\vec{x}}_m)$ . To make explicit this restrictive condition, time-order reconstruction is an iterative sorting of finding the maximum chain product of triple image correlation W_{i, j, k}W_{k, l, m} over the time-ordered facial image space. The triple correlation is defined as

2.2.

Self-Reference Matched Filter

For simplicity, the square (Euclidean) norm distance, also called the LMS distance, in Eq. 3 represents a measurement of similarity (or for neighborhood determination) between two images,

Eq. 3

[TeX:] \documentclass[12pt]{minimal}\begin{document}\begin{equation} \hbox{\it Min}\;e = \hbox{\it Min}||\vec x _i - \vec x _j ||^2, \end{equation}\end{document} $$\mathit{\text{Min}}e=\mathit{\text{Min}}\left|\right|{\vec{x}}_i-{\vec{x}}_j{\left|\right|}^2,$$

where [TeX:] $\vec x _i$ ${\vec{x}}_i$ and [TeX:] $\vec x _i$ ${\vec{x}}_i$ are images and represented by a single vector O(L×M) of image size L×M consisting of all gray pixel values of the whole image. Although in general the norm distance may not necessarily be the accurate metric to determine the similarity (e.g., other pertinent features: color of clothes, background of the person). In our applications, Eq. 3 seems to be adequate for image sorting of facial surveillance videos provided that we have a preprocessing called binarized centroid registration of each short exposure in a facial box, inspired by a graceful degradation of scaling in the human visual system (HVS) (see Appendix).

If we explicitly combine the maximum likelihood cost function together with the graph-Laplacian diffusion distance, the similarity metrics becomes identical to our self-reference matched filter (SRMF) least mean square energy as follows:

Eq. 4

[TeX:] \documentclass[12pt]{minimal}\begin{document}\begin{eqnarray} e &=& \hbox{\it Min}||\vec x _D - \vec x _{t_i } ||^2 /2\sigma = - \log [G_{ij} (\vec {x_i },\vec x _j)]\nonumber\\ &=& - \log \left[ {\exp \left( { {-} \frac{{||\vec x _i - \vec {x_j } ||^2 }}{{2\sigma }}} \right)} \right]. \end{eqnarray}\end{document} $$\begin{array}{ccc}\hfill e& =& \mathit{\text{Min}}\left|\right|{\vec{x}}_D-{\vec{x}}_{t_i}{\left|\right|}^2/2\sigma =-\log \left[G_{ij}(\overrightarrow{x_i},{\vec{x}}_j)\right]\hfill \\ & =& -\log \left[\exp \left(-\frac{\left|\right|{\vec{x}}_i-\overrightarrow{x_j}{\left|\right|}^2}{2\sigma }\right)\right].\hfill \end{array}$$

Coifman have adopted the graph-Laplacian spectral theory [TeX:] $G_{ij} (\vec x _i,\vec x _j) \equiv \exp ( - ||\vec x _i - \vec {x_j } ||^2 /2\sigma)$ $G_{ij}({\vec{x}}_i,{\vec{x}}_j)\equiv \exp (-||{\vec{x}}_i-\overrightarrow{x_j}{\left|\right|}^2/2\sigma )$ to sort facial poses as an example of nonlinear dimensionality reduction.^{8, 9} Without creating any confusion, we have associated, for two sets of readerships familiar with video processing and with nonlinear dimensionality reduction (NDR) graph theory, a snapshot time index [TeX:] $\vec x _{t_i }$ ${\vec{x}}_{t_i}$ freely with the vortex node [TeX:] $\vec x _i$ ${\vec{x}}_i$ of a face image. The minimization process, Min in Eq. 4, is due to the opposite algebraic signs. The first term [TeX:] $\vec x _{t_i }$ ${\vec{x}}_{t_i}$ represents an individual face image and [TeX:] $\vec x _D$ ${\vec{x}}_D$ is the first pass average through all faces as the statistically centroid correct but blurred LE defined as:

Eq. 5

[TeX:] \documentclass[12pt]{minimal}\begin{document}\begin{equation} \vec x _D \cong \frac{1}{N}\sum\limits_{t = 1}^N {\vec x _t }. \end{equation}\end{document} $${\vec{x}}_D\cong \frac{1}{N}\sum _{t=1}^N{\vec{x}}_t.$$

The instantaneous output [TeX:] $\vec x _{t_i }$ ${\vec{x}}_{t_i}$ is the SE facial images. The filter can select a SE with minimum square norm distance error to long exposure.^{23, 25} An example is illustrated in Fig. 3.

Fig. 3

SRMF illustration: In this single video setup, the passenger is limited to walking through a narrow corridor toward the camera. (a) SE of a video from 70th to 89th frame with different sizes, frames from 70 to 79 have 58×58 pixels and from 80 to 89 have 59×59 pixels (8 bits dynamic range). (b) For frames from 70 to 79, the pixels in the 59th row and column are set to 0. From Eq. 5, LE is blurred but is the statistically correct centroid of the frontal pose, 59×59 pixels (8 bits DR). (c) Square norm distance error between SE and LE. The minimum norm distance error of SE happens on the 79th frame and the bit error per pixel is 0.05 due to size and background difference.

3.

Implementations

In remote video surveillance, facial data acquired from video is generally a lower resolution than photographic biometric resolution, which typically must have at least 12 pixels between the eyes defined.²⁶ Our time-order reconstruction algorithm must follow this constraint as well. A static face is regarded as a collection of pixels with light intensity on each pixel. This collection of pixels also specifies the Cartesian coordinates of a point with respect to a set of axes. Therefore, a point can represent a face in an abstract image space.^{4, 5, 27} For facial images of walking passengers, they can be visualized as lying on a three-dimensional manifold that can be parameterized by two pose angles and changes of resolution, assuming light intensity is constant in a short duration, perhaps lasting over 10 s.

3.1.

Solving Variable Faces by Focusing at the Binarized Centroid for a Graceful Degradation of Facial Scaling

Our goal is to sort the time-order of changing faces among backgrounds. We are motivated from HVSs to derive a morphologically efficient preprocessing technique. It allows us to track maximum overlapping common foreground faces among changing perspectives and size distances. The outputs of a face detection system on chip, in Fig. 9, are boxes in different sizes. Some boxes have a lot of background information and some boxes do not. Before comparison between facial boxes, image preprocessing is needed to deal with the different sizes of boxes and any unwanted background information. Mathematically speaking, our approach is equivalent to a video version of gray-scaled self-reference Wiener matched filter. Physiologically speaking, we have 150 million night vision cones distributed nonuniformly in polar-exponentially grids at the fovea, which is densely packed in the middle of the fovea and exponentially dropping out in the peripheral. The location of each rod is denoted by a vector r_i. There are about 100 rods that share an integrator called ganglion firing through a single neurofiber at the fovea output denoted as a vector u_j to the cortex 17. Altogether there are millions of neurofibers that are closely packed together into a uniform output bundle toward the lateral geniculate nucleus.²⁴ For example, the input i‘th pixel of facial boundary is r_i = exp(u_j), which is equivalent to the output u_j = log(r_i) achieving a massive parallel flow-through logarithmic scaling transform without explicit computation. In other words, when a face changes its size with a scale factor s at [TeX:] $r^{\prime} _i \equiv r_i s = \exp (u^{\prime} _i)$ $r_i^{\prime }\equiv r_{i}s=\exp \left(u_i^{\prime }\right)$ implying [TeX:] $u^{\prime} _i = \log (r^{\prime} _i) = \log (r_i s) = \log (r_i) + \log (s) \cong u_j$ $u_i^{\prime }=\log \left(r_i^{\prime }\right)=\log \left(r_{i}s\right)=\log \left(r_i\right)+\log \left(s\right)\cong u_j$ . For example, a size of half s = 2 change gives log_e (2) = ln(2) = 0.69 which is a small fraction over many pixels. This fan-in polar exponential grid (PEG) architecture²⁴ facilitates the logarithmic computation of millions of rods’ coordinates in a parallel flow through the PEG. This real-time “algo-tecture” is one of the wonders of the human visual system. This is the reason why a hunter running after a prey in the moon light can gracefully tolerate the rapid changes of the prey, that allows the hunter to integrate continuously for a better signal to noise ratio (SNR) over several hundred photons falling upon the bundle of 100 rods via another fan-in architecture connecting hundreds of rods to a single ganglion toward lateral geniculate nucleus (LGN) and cortex 17. Incidentally, a rod detecting a single photon at SNR = 40 due to the wavelength at night is about 1 μm, equivalent to 1 eV, while the body temperature at 37°C is equivalent to 1/40 eV. The spatial spreading of a single micron photon can cover a 100 rod bundle at 100 nm each.

Fig. 9

(a) FD is well developed and commercialized in most modern cameras by different brands. This example of FD is from Google. (b) An example of multiple cameras adopted for surveillance in a long corridor for monitoring passengers. (c) An aided target recognition system for inspectors to take a closer second look at the specific passenger who has the same (or similar) pose of mug shots in the system. The two mug-shots are selected from MIT face databases.³³

To achieve a morphologic registration of the facial invariant centroid, we will approximate the aforementioned color hue for face detection by the gray scale intensity thresholding. For example, we choose the Heaviside step function of the gray scale g by an arbitrary θ threshold: [TeX:] $u = \hbox{\it Heaviside}|\frac{g}{\theta } - 1| = 1\;{\rm if}\;g \ge \theta$ $u=\mathit{\text{Heaviside}}|\frac{g}{\theta }-1|=1\mathrm{if}g\ge \theta$ ; zero if otherwise. Instead of the logarithmic transform of a million coordinates for the scale invariance, a real-time morphologic preprocessing is a simple binarized centroid determination at the middle of unity counts, as shown in Fig. 4.

Fig. 4

Technique to find a common central facial portion. Facial center allows us to cut an identical central portion of each face. (a) Translation from facial center to box center: two facial boxes are in different sizes. The dot is the binarized centroid of the face and the square is the geometry centroid of the box. The first translation is to move the face from binarized centroid of the face to the geometry centroid of its box. After that, a transformation is applied to every face box from its original coordinates to the laboratory coordinates. (b) Registration of every face box to the centroid of the long exposure: the triangle is the binarized centroid of the long exposure in Eq. 5. (c) Choose common portions of faces: after the two translations, major facial features such as the eyes, nose, and mouth of every face box are relatively close under the same coordinates. It is crucial so that norm distance or Gaussian diffusion distance can be adequate for a similarity measurement. (d) Clean cut foregrounds: every face box is cut by a rectangle template to get rid of the unwanted background information.

Binarized centroid registrations: For N face boxes (SE) in different sizes, a complete segmentation of a face box R is a finite set of regions R₁, …, R_s,

Eq. 6

[TeX:] \documentclass[12pt]{minimal}\begin{document}\begin{equation} R = \cup _{i = 1}^s R_i,\quad R_i \cap R_j = \phi,\quad i \ne j. \end{equation}\end{document} $$R={\cup }_{i=1}^s{R}_i,R_i\cap R_j=\phi ,i\ne j.$$

The morphologic segmentation likewise resulted from the threshold operation that transforms an input gray-scale image f to an output binary image g as follows:

Eq. 7

[TeX:] \documentclass[12pt]{minimal}\begin{document}\begin{equation} \begin{array}{*{20}c} \hfill {g(i,j) = 1\quad \hbox{\it for}\quad f(i,j) \ge T,} \\[5pt] \hspace*{33pt}\hfill { = 0\quad \hbox{\it for}\quad f(i,j) < T,} \\ \end{array} \end{equation}\end{document} $$\begin{array}{c}\hfill g(i,j)=1\mathit{\text{for}}f(i,j)\ge T,\\ =0\mathit{\text{for}}f(i,j)<T,\end{array}$$

where T is the threshold, g(i, j) = 1 for the face, and g(i, j) = 0 for the background.

Eq. 8

[TeX:] \documentclass[12pt]{minimal}\begin{document}\begin{equation} \overrightarrow {bc} _i = \frac{1}{n}\sum\limits_{j,k}^n {g(j,k)},\quad\hbox{\it where}\quad g(j,k) = 1, \end{equation}\vspace*{-11pt}\end{document} $${\overrightarrow{bc}}_i=\frac{1}{n}\sum _{j,k}^{n}g(j,k),\mathit{\text{where}}g(j,k)=1,$$

Eq. 9

[TeX:] \documentclass[12pt]{minimal}\begin{document}\begin{equation} (\overrightarrow {bc} _i - \overrightarrow {gc} _i) = 0,\quad\hbox{\it for}\quad i = 1,\ldots,N, \end{equation}\vspace*{-11pt}\end{document} $$({\overrightarrow{bc}}_i-{\overrightarrow{gc}}_i)=0,\mathit{\text{for}}i=1,...,N,$$

Eq. 10

[TeX:] \documentclass[12pt]{minimal}\begin{document}\begin{equation} \overrightarrow {bc} _i^* - \overrightarrow {bc} _{LE} = 0,\quad {\it for}\quad i = 1,\ldots,N, \end{equation}\end{document} $${\overrightarrow{bc}}_i^{*}-{\overrightarrow{bc}}_{LE}=0,\mathit{for}i=1,...,N,$$

where [TeX:] $\overrightarrow {bc} _i$ ${\overrightarrow{bc}}_i$ is the binarized centroid of the face in i’th face box (SE), [TeX:] $\overrightarrow {gc} _i$ ${\overrightarrow{gc}}_i$ is the geometric centroid of the i’th face box, * in [TeX:] $\overrightarrow {bc} _i^*$ ${\overrightarrow{bc}}_i^{*}$ indicates the translation from the i’th coordinate to the laboratory coordinates system that covers every face box, and [TeX:] $\overrightarrow {bc} _{LE}$ ${\overrightarrow{bc}}_{LE}$ is the binarized centroid of the long exposure, Eq. 5, determined by Eq. 8. The first pass centroid registration is demonstrated in Eqs. 9, 10 is the second pass centroid registration. The determination of T ’s gray scale value is critical in this algorithm. For optimization of the threshold, different strategies have been developed for different scenarios.²⁸ The robustness of the binarized centroid of facial boxes is discussed in the Appendix.

3.3.

ZC Algorithm

The theory of time-order from Sec. 2 is implemented in an iterative research fashion herein. The video sequence captured by the camera satisfies the following inequality, Eq. 11, in an abstract manifold:

Eq. 11

[TeX:] \documentclass[12pt]{minimal}\begin{document}\begin{eqnarray} \left\| {O_t {-} O_{t \pm 1} } \right\| < \left\| {O_t {-} O_{t \pm s} } \right\|,\;t > s > 1\;\hbox{\it and}\,t,s \in {\rm Integer},\hspace*{-15pt}\nonumber\\ \end{eqnarray}\end{document} $$\begin{array}{c}\hfill ‖O_t-O_{t\pm 1}‖<‖O_t-O_{t\pm s}‖,t>s>1\mathit{\text{and}}t,s\in \mathrm{Integer},\end{array}$$

where O_t is a node representing a facial box and the subscript labels t and s are the time indices of the time-ordering of nodes on the manifold. The ∥·∥ represents the geodesic distance between nodes of the original time-ordering of nodes on the manifold. If Eq. 11 holds true, it implicitly indicates that a trajectory of time-ordering (of a passenger) cannot intersect itself and other trajectories of time-orderings (of other passengers) on the manifold. It also indicates that finding the time-order is equivalent to find out the geodesic order which has the lowest total neighborhood geodesic distances. We plot the geodesic distance (simulated by LMS distance) as the contour map over the N² dimensionality surface in Fig. 5.

Fig. 5

Iterative confirmation logic for time-ordering reconstruction and contour map of N nodes over the N ² dimensionality surface. (a) Iterative confirmation logic of s-curve poses ZC algorithm: In this example, facial boxes are sorted in a manner of time-order. The first confirmation is to select the two nearest neighbors in LMS distance of the 9th frame, that are the 8th and 10th frames. The second confirmation is to determine whether the 9th frame is also one of the two nearest neighbors of the 8th and 10th frames in LMS distance. The third confirmation check is to determine another neighbor of the 8th and 10th frames, that is the 7th and 11th frames, respectively, and so on. The poses in the 9th and 37th frames are similar. However, with the morphological preprocessing and the iterative confirmation logic given in this paper, we can find the correct neighbors of the 9th frame without confusion. The axes are frame index, iterative confirmation of neighbors, and LMS distance between frames. (b) Contour map of N random nodes over the N ² dimensionality surface. N is 50 in this example. The axes are frame index, frame index, and LMS distance between frames. (c) Contour map of N time-ordered nodes over the N ² dimensionality surface. N is 50 in this example. The axes are frame index, frame index, and LMS distance between frames. The correct time-ordering of facial boxes is found when the summation of all neighborhood pair-wise distances between nodes happens to be at the absolute minimum on the manifold.

In implementation, we adopt LMS distance between facial boxes to approach the geodesic distance on the manifold. Explicitly, this approach may be skewed sometimes. If a video sequence cannot satisfy Eq. 11 all the time, some frames may be in an incorrect time-order. The impact of incorrect alignment, partial frames in sequence, and of time-order is discussed in Sec. 7. The meta algorithm is stated as follows:

4.

Discussion

In this section, two phenomenon are discussed. The first is the impact of leak-through background information in face boxes for the neighborhood determination. The second is what the consequence is if the step of iterative two neighborhoods comparisons in ZC algorithm is replaced by a direct neighborhood determination by LMS distance.

4.1.

Impact of Background Information of Face Boxes for Neighborhood Determination

Many spectral clustering methods ^{4, 5, 6, 7, 8, 9, 27, 29} are developed for sorting facial poses at a fixed distance with clear backgrounds. As mentioned in Sec. 2, norm distance or LMS distance has been used for the neighborhoods (or similarity) determination of facial poses in adjacency matrix. ^{4, 5, 6, 7, 8, 9, 16, 27, 29} However, in video surveillance, when passengers move, the facial resolutions of passengers change over time with respect to a fixed video camera. Moreover, the backgrounds of face boxes are not clear. In this case, the pixel-by-pixel LMS distance could not determine the correct neighborhoods due to the leak-through background information.

The under-sampled real world surveillance images of faces shown in 14 facial poses in a 4 s window are in Fig. 6. The LMS distance may not be sufficient to determine the similarity between faces when the changes of background are drastic for each face box shown in Fig. 6. However, with binarized centroid registration preprocessing applied be-fore sorting, the result became much more robust to be able to tolerate a factor of 2 in sizes over about 10 s walking time.

Fig. 6

Impact of background information for neighborhood determination (a) Fourteen selected time-ordered facial boxes of a passenger in different sizes, resolutions, backgrounds, and poses. The time window between the first frame and the last frame is 4 s. In (a), the change of image resolutions and backgrounds are significant. (b) Random order: The fourteen facial boxes are in a random order. (c) The sorting result by LMS distance when the difference of resolutions and background information between each image is significant. The result can be improved by two pass binarized centroid registrations. (d) Before sorting, two pass centroid registrations were applied and background information was removed as mentioned in Sec. 3.1. This result is in a much better shape. It shows for neighborhood determination that the LMS distance is less sensitive to the resolution difference than leak-through background information between each frame.

5.

Simulations

The ZC algorithm was coded in MATLAB on a PC with an Intel i-7 920 processor and 12 GB memory. The time of loading facial images is excluded in the execution time. The first simulation is a similarity sorting test of 60 facial poses of 1 person in different order. The face boxes are in different sizes and resolutions over time. In this simulation, it shows the robustness of our similarity sorting algorithm. No matter what orders the facial poses are, the sorting result is the same, as illustrated in Fig. 7. It is a robust and real-time sorting approximation of moving objects in a short time window, based on the two-pass centroid registrations and SRMF proposed in this paper.

Fig. 7

Sixty different facial poses in two random orders in (b) and (c). The sorting result of (b) and (c) by the similarity sorting algorithm proposed in this paper is in (d). The execution time is 0.65 s including two pass centroid registration preprocessing in average. The sorting results from different order of facial poses are the same.

For a simulation of time-ordered reconstruction, detailed steps are illustrated in Fig. 8. There are seven facial boxes in a random order. By the zipper chain algorithm introduced in Sec. 3, the norm distance matrix is built up by the input facial boxes. After that, the two nearest neighbor matrix are constructed in Fig. 8. The adjacent graph is determined by the two nearest neighbor matrix and the result is in Fig. 8.

Fig. 8

(a) Seven facial boxes in a time-ordering. (b) The same seven facial boxes in (a) but in a randomized order. (c) The norm distance matrix of each facial box. The first column is the root of norm distance between the long term average and each facial box. It determined the 3rd facial box is the pivot point in this simulation. (d) The two nearest neighborhood matrix of each facial box. (e) The adjacent graph of seven facial boxes constructed by the two nearest neighborhood matrix in (d) and (f) The final result is the same as (a).

6.

Applications

In this section, we briefly consider several possible video surveillance applications for the algorithmic framework developed in this paper.

6.3.

Association Across Sensory Modalities

The cross track association problem of archival video and audio becomes challenging after a different compression algorithm using current technologies. Without the basic spatiotemporal-order reconstruction, a close-up lip read and gesture motion cannot easily associate without ambiguity a remotely imaged passenger and with in situ audio recording by local microphones. The facial boxes of a crowd can be detected efficiently in random order by the face detection system on the chip mentioned in this paper. The next step is to sort out those facial boxes in a time-ordering so that we may be able to read lips, gestures, and other body languages in the right order. For example, in Fig. 10, “where is exit?” and “I am tired.” are recorded by dual microphones with airport music and background noise. In Fig. 10, two speeches are separated, e.g., by fast independent component analysis (ICA) algorithm based on different positive Kurtosis values. For a passenger who is looking for an exit, the passenger has a higher chance to look around, turning to face right and left, instead of looking down at the floor. The time-ordering sorting algorithm proposed in this paper is useful for cross track association of video and audio.

Fig. 10

(a) Two passengers are walking in a corridor. (b) Mixed signals of audio from two passengers, recorded by dual microphones. (c) Signals separated by fast ICA.

7.

Conclusion

In this paper, we have presented an efficient time-order reconstruction algorithm of sorting facial boxes in order to associate remote video and local audio for answering the surveillance challenge—“who speaks what, where and when.” We show that it is crucial to have a morphological image preprocessing which begins at a binarized centroid registration, in order to find a maximum overlapping common region from all facial boxes in different sizes and coordinates. Then a ZC algorithm is developed by considering the products of pair correlations functions in tandem verification. Consequently, each face box is linked together in a time-order, as if the zipper's teeth are mounted overlapping one another. This ZC algorithm reconstructs the time-order linking the video manifolds of walking facial boxes and audio manifolds of in situ voice recorders. Independent of the cameras setup configuration, the video sampling rate is an important parameter. Our experience shows to be sufficient at 20 to 30 Hz for an average walking pace of 3 to 6 miles per hour. However, if a passenger runs faster than the walking limit, the camera sampling rate must be increased to reduce the image blur. We combine the anchor face that is automatically discovered by means of self-reference matched filter with the time-order ZC sorting capability, and we hope to find the time-order of each person to allow us to associate each with his or her own voices recording. In general, the average speaking speed is 3 to 4 words per second. In the movie industry, the technician can sync the voice recording by a lip reading technique when a close up facial detail is available. However, the remote video may not have the detail. In this situation, our goal is to identify the corresponding speakers according to the recorded audio.

The time-order reconstruction of facial poses belongs to a nondeterminant polynomial-time (NP) complete problem and the proof is in Appendix B. Given N image poses, the ordering index runs from 1 to N. Then, there are N! possibilities to assign the ordering index to each pose. We plot the LMS distance as the contour map over the N² dimensionality surface in Sec. 3.3. The time-order reconstruction is equivalent to find the geodesic order that has the lowest total neighborhood distances on an abstract manifold. ZC algorithm is a heuristic solution for this NP complete problem. Equation 11 is the constraint of the solution that each time-ordering trajectory on an abstract manifold is prohibited to intersect with itself or other time-ordering trajectories.