Algorithms for constrained <Emphasis Type="Italic">k</Emphasis>-nearest neighbor queries over moving object trajectories

An important query for spatio-temporal databases is to find nearest trajectories of moving objects. Existing work on this topic focuses on the closest trajectories in the whole data space. In this paper, we introduce and solve constrained k-nearest neighbor (CkNN) queries and historical continuous CkNN (HCCkNN) queries on R-tree-like structures storing historical information about moving object trajectories. Given a trajectory set D, a query object (point or trajectory) q, a temporal extent T, and a constrained region CR, (i) a CkNN query over trajectories retrieves from D within T, the k (≥ 1) trajectories that lie closest to q and intersect (or are enclosed by) CR; and (ii) an HCCkNN query on trajectories retrieves the constrained k nearest neighbors (CkNNs) of q at any time instance of T. We propose a suite of algorithms for processing CkNN queries and HCCkNN queries respectively, with different properties and advantages. In particular, we thoroughly investigate two types of CkNN queries, i.e., CkNN_P and CkNN_T, which are defined with respect to stationary query points and moving query trajectories, respectively; and two types of HCCkNN queries, namely, HCCkNN_P and HCCkNN_T, which are continuous counterparts of CkNN_P and CkNN_T, respectively. Our methods utilize an existing data-partitioning index for trajectory data (i.e., TB-tree) to achieve low I/O and CPU cost. Extensive experiments with both real and synthetic datasets demonstrate the performance of the proposed algorithms in terms of efficiency and scalability.     

Channel invariant online visibility enhancement for visual SLAM in a turbid environment

This paper presents a real‐time and channel‐invariant visibility enhancement algorithm using a hybrid image enhancement approach. The proposed method is initially motivated by an underwater visual simultaneous localization and mapping (SLAM) failure in a turbid medium. The environments studied contain various particles and are dominated by a different image degradation model. Targeting image enhancement for degraded images but not being limited to it, the proposed method provides a highly effective solution for both color and gray images with substantial improvement in the process time compared to conventional methods. The proposed method introduces a hybrid scheme of two image enhancement modules: a model‐based (extensive) enhancement and a model‐free (immediate) enhancement. The proposed method is validated by using simulated synthetic color images and real‐world color and grayscale underwater images. Real‐world validation is performed in various environments such as hazy indoor, smoky indoor, and underwater. Using the ground truth trajectory or clear images acquired from the same area but without turbidity, we evaluate the proposed visibility enhancement and camera registration improvement for a feature based (ORB‐SLAM2), a direct (LSD‐SLAM), and a visual underwater SLAM application.     

Multibit C k NOT quantum gates via Rydberg blockade

Long range Rydberg blockade interactions have the potential for efficient implementation of quantum gates between multiple atoms. Here we present and analyze a protocol for implementation of a k-atom controlled NOT (C _k NOT) neutral atom gate. This gate can be implemented using sequential or simultaneous addressing of the control atoms which requires only 2k + 3 or 5 Rydberg π pulses respectively. A detailed error analysis relevant for implementations based on alkali atom Rydberg states is provided which shows that gate errors less than 10% are possible for k = 35.     

Bounds for the 2-domination number of toroidal grid graphs

A k-dominating set for a graph G(V, E) is a set of vertices D? V such that every vertex v∈V\ D is adjacent to at least k vertices in D. The k-domination number of G, denoted by γ _k (G), is the cardinality of a smallest k-dominating set of G. Here we establish lower and upper bounds of γ _k (C _m ×C _n ) for k=2. In some cases, these bounds agree so that the exact 2-domination number is obtained.     

Small Space Representations for Metric Min-sum k-Clustering and Their Applications

The min-sum k -clustering problem is to partition a metric space (P,d) into k clusters C ₁,…,C _k ?P such that $\sum_{i=1}^{k}\sum_{p,q\in C_{i}}d(p,q)The min-sum k -clustering problem is to partition a metric space (P,d) into k clusters C ₁,…,C _k ⊆P such that ?_i=1^k?_{p,q ? Ci}d(p,q)\sum_{i=1}^{k}\sum_{p,q\in C_{i}}d(p,q) is minimized. We show the first efficient construction of a coreset for this problem. Our coreset construction is based on a new adaptive sampling algorithm. With our construction of coresets we obtain two main algorithmic results.     

A spatially adaptive fast atmospheric correction algorithm

An atmospheric correction algorithm for high spatial resolution satellite sensors like Landsat Thematic Mapper (TM) has been developed. The algorithm works with a catalogue of atmospheric correction functions stored in look-up tables. The catalogue consists of a broad range of atmospheric conditions (different altitude profiles of pressure, air temperature, and humidity; several aerosol types; ground elevations from 0-1?km above sea level; solar zenith angles ranging from 0°-70°). The catalogue covers visibilities (surface meteorological range) from 5-40?km, values can be extrapolated down to 4?km and up to 80km. The 1994 edition of the catalogue was compiled using the MODTRAN-2 and the SENSAT-5 codes.

The algorithm consists of an interactive and an automatic part. The interactive phase serves for the definition of a reference target (dense dark vegetation or water) as well as haze and cloud. The reflectance of the reference target in a single spectral band (dark vegetation: TM band 3; water: TM band 4) has to be specified. Additionally, the image can be partitioned into sub-images, called sectors. This phase also selects one of the atmospheres available in the catalogue, i.e. the altitude profile of pressure, temperature and humidity as well as the aerosol type (e.g. rural) are fixed.

The automatic phase first calculates the visibility of the reference areas for the selected atmosphere. The visibility is obtained by matching the measured signal (i.e the digital number (DN) converted to a radiance using the sensor calibration) to the model-derived signal in the spectral channel of known target reflectance. The sector-average visibility of the reference pixels is assigned to the non-reference pixels. The second step is the haze removal performed by histogram matching the statistics of the haze regions to the statistics of the clear part of the scene for each sector and each channel. The last step is the calculation of the ground reflectance image including the adjacency correction, and the computation of the ground brightness temperature image (TM band 6)     

A method of predicting the number of clusters using Rand's statistic

Distributional and asymptotic results on the moment of Rand's C_k statistic were derived by DuBien and Warde [1981. Some distributional results concerning a comparative statistic used in cluster analysis. ASA Proceedings of the Social Statistics Section, 309–313.]. Based on those results, a method to predict the number of clusters is suggested by applying various agglomerative clustering algorithms. In the procedure, the methods using different indexes are examined and compared based on the concept of agreement (or, disagreement) between clusterings generated by different clustering algorithms on the set of data. Our method having practical generality works better than the other methods and assigns statistical meaning to C_k values in determining the number of clusters from the comparison.     

On Rooted Node-Connectivity Problems

Let G be a graph which is k -outconnected from a specified root node r , that is, G has k openly disjoint paths between r and v for every node v . We give necessary and sufficient conditions for the existence of a pair rv,rw of edges for which replacing these edges by a new edge vw gives a graph that is k -outconnected from r . This generalizes a theorem of Bienstock et al. on splitting off edges while preserving k -node-connectivity. We also prove that if C is a cycle in G such that each edge in C is critical with respect to k -outconnectivity from r , then C has a node v , distinct from r , which has degree k . This result is the rooted counterpart of a theorem due to Mader. We apply the above results to design approximation algorithms for the following problem: given a graph with nonnegative edge weights and node requirements c _u for each node u , find a minimum-weight subgraph that contains max {c _u ,c _v } openly disjoint paths between every pair of nodes u,v . For metric weights, our approximation guarantee is 3 . For uniform weights, our approximation guarantee is \min{ 2, (k+2q-1)/k} . Here k is the maximum node requirement, and q is the number of positive node requirements. Received September 15, 1998; revised March 10, 2000, and April 17, 2000.     

Pseudo Zero-watermarking Technique based on non-blind watermarking and VSS

This paper proposes a solution for digital image copyright protection technique using the combination of watermarking and visual encryption technique. In our solution, the copyright information (copyright logo) is distributed into n shares using k ? out ? of ? n distributed algorithm, also called (k, n) visual secret sharing method. One of the shares is randomly selected to embed into the original image to prove the user’s copyright. The remaining n ??1 shares is used to register with Copyright Department. When claiming the copyright belongs to the user, the verifier only needs to extract the watermark information from the watermarked image, then decodes with any registered k ??1 shares from n ??1 shares for restoring copyright information. Experimental results of the proposed method compared with the method using only digital watermark show that our method has more practical effectiveness in the application of digital product copyright protection.

     

A relationship between difference hierarchies and relativized polynomial hierarchies

Chang and Kadin have shown that if the difference hierarchy over NP collapses to levelk, then the polynomial hierarchy (PH) is equal to thekth level of the difference hierarchy over ₂ ^p . We simplify their poof and obtain a slightly stronger conclusion: if the difference hierarchy over NP collapses to levelk, then PH collapses to (P _(k–1) ^NP )^NP, the class of sets recognized in polynomial time withk – 1 nonadaptive queries to a set in NP^NP and an unlimited number of queries to a set in NP. We also extend the result to classes other than NP: For any classC that has _m ^p -complete sets and is closed under _conj ^p -and _m ^NP -reductions (alternatively, closed under _disj ^p -and _m ^co-NP -reductions), if the difference hierarchy overC collapses to levelk, then PH ^C = (P _(k–1)–tt ^NP ) ^C . Then we show that the exact counting class C_P is closed under _disj ^p - and _m ^co-NP -reductions. Consequently, if the difference hierarchy over C_P collapses to levelk, then PH^PP(= PH^C_P) is equal to (P _(k–1)–tt ^NP )^PP. In contrast, the difference hierarchy over the closely related class PP is known to collapse.Finally we consider two ways of relativizing the bounded query class P _k–tt ^NP : the restricted relativization P _k–tt ^{NP C} and the full relativization (P _k–tt ^NP ) ^C . IfC is NP-hard, then we show that the two relativizations are different unless PH ^C collapses.Richard Beigel was supported in part by NSF Grants CCR-8808949 and CCR-8958528. Richard Chang was supported in part by NSF Research Grant CCR 88-23053. This work was done while Mitsunori Ogiwara was at the Department of Information Science, Tokyo Institute of Technology, Tokyo, Japan.     

Recursive identification for EIV ARMAX systems

The input u _k and output y _k of the multivariate ARMAX system A(z)y _k = B(z)u _k + C(z)w _k are observed with noises: u _k ^ob ≜ u _k + ε _k ^u and y _k ^ob ≜ y _k + ε _k ^y , where ε _k ^u and ε _k ^y denote the observation noises. Such kind of systems are called errors-in-variables (EIV) systems. In the paper, recursive algorithms based on observations are proposed for estimating coefficients of A(z), B(z), C(z), and the covariance matrix Rw of w _k without requiring higher than the second order statistics. The algorithms are convenient for computation and are proved to converge to the system coefficients under reasonable conditions. An illustrative example is provided, and the simulation results are shown to be consistent with the theoretical analysis.     

暗通道先验图像去雾的大气光校验和光晕消除

目的 针对暗通道先验图像去雾方法中存在的大气光误判以及光晕效应等问题,提出一种基于大气光校验和光晕消除策略的改进算法。方法 首先,采用基于支持向量机的大气光校验方法对候选大气光的有效性进行判断,剔除太阳光、车灯等高光区域的干扰;然后,采用基于块偏移的精细透射率计算方法获得边缘保持的透射率,极大地抑制了无雾图像中光晕像素的数量;最后,采用基于导向滤波的光晕像素检测和校正方法进一步消除了残留的少量光晕像素。结果 本文算法有效抑制了大气光的误判现象,大大消除了光晕效应,提升了无雾图像的细节可辨认度,最终获得的无雾图像细节丰富、颜色深度感饱满。结论 本文算法在无雾图像的可见度增强等诸多方面超越了已有的方法,在视频监控、交通监管和目标识别等领域具有较大实用价值。     

The construction of mutually independent Hamiltonian cycles in bubble-sort graphs

A Hamiltonian cycle C=? u ₁, u ₂, …, u _n(G), u ₁ ? with n(G)=number of vertices of G, is a cycle C(u ₁; G), where u ₁ is the beginning and ending vertex and u _i is the ith vertex in C and u _i ≠u _j for any i≠j, 1≤i, j≤n(G). A set of Hamiltonian cycles {C ₁, C ₂, …, C _k } of G is mutually independent if any two different Hamiltonian cycles are independent. For a hamiltonian graph G, the mutually independent Hamiltonianicity number of G, denoted by h(G), is the maximum integer k such that for any vertex u of G there exist k-mutually independent Hamiltonian cycles of G starting at u. In this paper, we prove that h(B _n )=n?1 if n≥4, where B _n is the n-dimensional bubble-sort graph.     

The linear programming approach to the Randić index

Let G(k, n) be the set of simple graphs (i.e. without multiple edges or loops) that have n vertices and the minimum degree of vertices is k. The Randi? index of a graph G is: , where δ_u is the degree of vertex u and the summation extends over all edges (uv) of G. Using linear programming, we find the extremal graphs or give good bounds for this index when the number n_k of vertices of degree kis n?k+t, for 0tk and kn/2. We also prove that for n_kn?k, (kn/2) the minimum value of the Randi? index is attained for the graph .     

An efficient Boolean based multi-secret image sharing scheme

The purpose of this paper is to develop an algorithm for sharing k secret images to n participants in such a way that each participant gets a single share image by encoding all k images. Any qualified subgroup of t : t ≤ n of those n participants can reconstruct the k_ith secret image only by combining their share images if they are qualified to reconstruct the k_ith secret image. Most of the existing literature solves this problem for the cases where t =?2 or t = n making it a very restrictive scheme. In this article, we aim to design a multi-secret image sharing scheme based on XOR operation where t is not restricted to be 2 or n. We have used n random matrices of the same size as the secret image size as private share to generate r (where r is the number of qualified subgroups) share images as public share using XOR operations. The proposed scheme is computationally lightweight and lossless due to XOR operation only. It does not involve any pixel expansion. The experimental results with a very low correlation coefficient between share and secret images confirm that share image does not reveal anything about secret image. The scheme is secure against differential attack as a higher value of Number of Changing Pixel rate (NPCR) confirms that. The current proposal is based on a general access structure, and hence any secret image can be reconstructed by a qualified group of t or more shares where t need not be 2 or n only.

     

Atmospheric effects on radiometry from zenith of a plane with dark vertical protrusions

Effects of an optically thin plane-parallel scattering atmosphere on radiometric imaging from the zenith of a specific surface type are analysed. The surface model was previously developed to describe arid steppe, where the sparse vegetation forms dark vertical protrusions from the bright soil plane. The analysis is in terms of the surface reflectivity to the zenith r_p for the direct beam, which is formulated as r_p = r_i exp(?s tan θ₀), where r_i is the Lambert-law reflectivity of the soil, the protrusion parameter 5 is the projection on a vertical plane of protrusions per unit area and θ⁰ is the zenith angle. The surface reflectivity r_P is approximately equal to that for the global irradiance (which is directly measured in the field) only for a narrow range of the solar zenith angles. The effects of the atmosphere when imaging large uniform areas of this type are comparable to those in imaging a Lambert surface with a reflectivity r_P . Thus, the effects can be approximated by those in the case of a dark Lambert surface (analysed previously), inasmuch as r_P is smalleSr than the soil reflectivity r_i for any off-zenith illumination. The surface becomes effectively darker with increasing solar zenith angle.

Adjacency effects of a reflection from one area and scattering in the instantaneous field of view (object pixel) are analysed as cross radiance and cross irradiance, The analysis is only for the case of a small object pixel embedded in a different terrain, extending to infinity as a uniform area. The effects of the cross radiance (which are dominant) are found to be smaller than those over a Lambert plane for the same surroundings-to-object-pixel contrast and atmospheric conditions. However, the adjacency effects are highly variable, because the effective contrast for our plane with dark protrusions is a function of not only the surface parameters but also of the solar zenith angle and the atmospheric conditions.     

An evaluation of multi-spectral responses on selected turfgrass species

Multi-spectral measurements have been shown to detect plant stress in numerous species. Leaf chlorophyll concentration may change in response to altered plant physiological functions due to plant stress; this may also be detected by reflectance data. This research was conducted on established field plots of creeping bentgrass (Agrostis palustris Huds.) and bemudagrass (Cynodon dactylon L X C. transvaalensis Burtt-Davy) at the University of Georgia turfgrass rhizotron in Athens, GA. Multi-spectral data and visual ratings of quality, colour, and density were taken simultaneously on the two species in October 1997. Reflectance was greater in the C₄ bemudagrass than the C₃ bentgrass, greater in the visible range in bentgrass plots receiving N at 16.1 kg ha ^-1 and greater from 2 DAT on in bermudagrass plots receiving glyphosate.     

A simple algorithm to estimate sensible heat flux from remotely sensed MODIS data

Sensible heat flux (H) has a large impact on energy exchange between the surface and the atmosphere and, thus, affects climate change and climatic and hydrological modelling. In the past, remote sensing of H has been a major area of interest and, as a result, various methods have been established for its retrieval. However, large discrepancies between measured and simulated values of H have been observed over land surfaces because of various assumptions and simplifications. This article presents a generalized algorithm for the estimation of sensible heat flux that is suitable for a wide range of atmospheric and terrestrial conditions from Moderate Resolution Imaging Spectroradiometer (MODIS) data. Standard built-in atmospheric profiles in Fast Atmospheric Signature Code (FASCODE) together with atmospheric conditions obtained by periodic radio sounding, once a week, performed at the Broglio Space Centre in Malindi, Kenya, were used in simulating MODIS data at 11.03 and 12.02 μm wavelengths using PcLnWin software. This new approach improves the form of the Mito algorithm, developed to determine surface temperature, by removing some of the assumptions underlying the algorithm – for example, the assumption that air temperature T _a is approximately equal to surface temperature T _s. The resulting bulk aerodynamic resistance equation allows the formulation of a general algorithm for the determination of H, which takes into account the surface emittance effect, water vapour column (WVC), canopy properties, air temperature and different atmospheric stabilities. Unlike other conventional methods developed earlier for the determination of H, a prior knowledge of surface temperature as an auxiliary input is not necessary in this new algorithm. The estimates of sensible heat flux derived from MODIS using the proposed algorithm compared well with in situ measurements, giving a good correlation coefficient of r?=?0.9.