We analyze the Shell Sort algorithm under the usual random permutation model. Using empirical distribution functions, we recover Louchard's result that the running time of the 1-stage of (2, 1)-Shell Sort has a li...
详细信息
We analyze the Shell Sort algorithm under the usual random permutation model. Using empirical distribution functions, we recover Louchard's result that the running time of the 1-stage of (2, 1)-Shell Sort has a limiting distribution given by the area under the absolute Brownian bridge. The analysis extends to (h, 1)Shell Sort where we find a limiting distribution given by the sum of areas under correlated absolute Brownian bridges. A variation of (h, 1)-Shell Sort which is slightly more efficient is presented and its asymptotic behavior analyzed.
An automatic cloud classification algorithm is proposed for the Advanced Very High Resolution Radiometer (AVHRR), based on a 5-D histogram technique. The technique determines three-level (high, medium, low) cloud amou...
详细信息
An automatic cloud classification algorithm is proposed for the Advanced Very High Resolution Radiometer (AVHRR), based on a 5-D histogram technique. The technique determines three-level (high, medium, low) cloud amount and the average cloud-top brightness temperature (BT) and reflectance for 128 x 128 pixel areas. Comparison of the products for NOAA-11 AVHRR measurements during 14 orbits over oceans with the International Satellite Cloud Classification Project DX products for the same AVHRR data set is presented.
The limiting distribution of the normalized number of comparisons used by Quicksort to sort an array of n numbers is known to be the unique fixed point with zero mean of a certain distributional transformation S. We s...
详细信息
The limiting distribution of the normalized number of comparisons used by Quicksort to sort an array of n numbers is known to be the unique fixed point with zero mean of a certain distributional transformation S. We study the convergence to the limiting distribution of the sequence of distributions obtained by iterating the transformation S. beginning with a (nearly) arbitrary starting distribution. We demonstrate geometrically fast convergence for various metrics and discuss some implications for numerical calculations of the limiting Quicksort distribution. Finally, we give companion lower bounds which show that the convergence is not faster than geometric. (C) 2001 John Wiley & Sons, Inc.
Drawing on Merritt's divide-and-conquer sorting taxonomy [1], we model comparison-based sorting as an abstract class with a template method to perform the sort by relegating the splitting and joining of arrays to ...
详细信息
ISBN:
(纸本)1581133294
Drawing on Merritt's divide-and-conquer sorting taxonomy [1], we model comparison-based sorting as an abstract class with a template method to perform the sort by relegating the splitting and joining of arrays to its concrete subclasses. Comparison on objects is carried out via an abstract ordering strategy. This reduces code complexity and simplifies the analyses of the various concrete sorting algorithms. Performance measurements and visualizations can be added without modifying any code by utilizing the decorator design pattern. This object-oriented design not only provides the student a concrete way of unifying seemingly disparate sorting algorithms but also help him/her differentiate them at the proper level of abstraction.
Land cover is a key boundary condition in weather, climate, and terrestrial biogeochemical models. Until recently, such models have used maps depicting potential vegetation, which are known to be of relatively poor qu...
详细信息
Land cover is a key boundary condition in weather, climate, and terrestrial biogeochemical models. Until recently, such models have used maps depicting potential vegetation, which are known to be of relatively poor quality, to parameterize land surface properties. In this paper we describe the compilation and assessment of a new map of North American land cover produced through the application of advanced pattern recognition techniques to multitemporal satellite data. This map was produced in a fully automated fashion using supervised classification methods that are robust, fully automated, and repeatable. The processing flow described in this paper is a prototype of the algorithm to be used to generate maps of global land cover using data from EOS MODIS. The superior quality and timeliness of these maps should be very useful for a wide array of sub-continental to global-scale modeling and analysis activities.
During the 1997 winter season, shipborne polarimetric backscatter measurements of Great Lakes ice types using the Jet Propulsion Laboratory (JPL) C-band scatterometer, together with surface-based ice physical characte...
详细信息
ISBN:
(纸本)0780363590
During the 1997 winter season, shipborne polarimetric backscatter measurements of Great Lakes ice types using the Jet Propulsion Laboratory (JPL) C-band scatterometer, together with surface-based ice physical characterization measurements and environmental parameters were acquired concurrently with RADARSAT and ERS-2 SAR data. Using a supervised classification algorithm, measured backscatter values (converted to dB) for three ice types and calm water were applied to an 8 x 8 pixel averaged ERS-2 calibrated SAR image. Certain assumptions were made on the local incidence angle, one of which was that any change in incidence angle across a distributed target was neglected, i.e. a distributed target corresponds to one average value of the incidence angle (23 degrees was used). Although the calculated overall uncertainty was about +/- 1 dB as a result of the averaging and incidence angle effect, an algorithm to correct for power loss and local incidence angle effect is applied in this study to the ERS-2 image, resulting in a more accurate classification.
Generally fuzzy c-means algorithm is one proved that very well suited for remote sensing image segmentation. exhibited sensitivity to the initial guess with regard to both speed and stability. But it also showed sensi...
详细信息
ISBN:
(纸本)0780363590
Generally fuzzy c-means algorithm is one proved that very well suited for remote sensing image segmentation. exhibited sensitivity to the initial guess with regard to both speed and stability. But it also showed sensitivity to noise. This paper proposes a fully automatic technique to obtain image clusters. A modified fuzzy c-means classification algorithm is used to provide a fuzzy partition. This method is less sensitive to noise as it filters the image while clustering it, which is based on the consideration of the neighbors as factors the attract pixels into their cluster, The experimental results on JERS-1 Synthetic Aperture Radar (SAR) image demonstrate its potential usefulness.
High-frequency models for radar backscatter can include components with different structures that correspond to different physical scattering mechanisms on an object. We consider the problem of structure selection for...
详细信息
ISBN:
(纸本)0780362934
High-frequency models for radar backscatter can include components with different structures that correspond to different physical scattering mechanisms on an object. We consider the problem of structure selection for an attributed scattering center model that includes both localized and distributed scattering terms. We propose three structure classification algorithms, and compare their performance. We show that a threshold test on the estimated length parameter performs as well as a GLRT test, but is computationally more efficient. A computationally fast image-based test is shown to perform as well as the GLRT and length-based tests for scattering center lengths greater than twice the crossrange resolution of the measurements.
This communication presents two new classification algorithms based on Time Varying Higher Order Statistic (TVHOS). These two algorithms benefit from the advantageous localization properties provided by TVHOS4 for ins...
详细信息
ISBN:
(纸本)0780362934
This communication presents two new classification algorithms based on Time Varying Higher Order Statistic (TVHOS). These two algorithms benefit from the advantageous localization properties provided by TVHOS4 for instantaneous frequency laws disrupted by a multiplicative noise. The classification scheme used is a bank of several normalized TVHOS4 correlators. Simulations illustrate successful performance of the classification algorithms for different situations and especially if the SNR is higher than -7 dB.
作者：
Claudio GentileDSI
Universita' di Milano Via Comelico 39 20135 Milano Italy
A new incremental learning algorithm is described which approximates the maximal margin hyperplane w.r.t. Norm p ≥ 2 for a set of linearly separable data. Our algorithm, called ALMA_p (Approximate Large Margin algori...
详细信息
ISBN:
(纸本)0262122413
A new incremental learning algorithm is described which approximates the maximal margin hyperplane w.r.t. Norm p ≥ 2 for a set of linearly separable data. Our algorithm, called ALMA_p (Approximate Large Margin algorithm w.r.t. Norm p), takes O ((p-1) X~2/α~2γ~2) corrections to separate the data with p-norm margin larger than (1 ― α) γ, where γ is the p-norm margin of the data and X is a bound on the p-norm of the instances. ALMA_p avoids quadratic (or higher-order) programming methods. It is very easy to implement and is as fast as on-line algorithms, such as Rosenblatt's perceptron. We report on some experiments comparing ALMA_p to two incremental algorithms: Perceptron and Li and Long's ROMMA. Our algorithm seems to perform quite better than both. The accuracy levels achieved by ALMA_p are slightly inferior to those obtained by Support vector Machines (SVMs). On the other hand, ALMA_p is quite faster and easier to implement than standard SVMs training algorithms.
暂无评论