Structure of aura and co-occurrence matrices for the Gibbs texture model

The aura matrix of an image indicates how much of each gray level is present in the neighborhood of each other gray level and generalizes the popular texture-analysis tool, the co-occurrence matrix. In this paper we show that interesting structure appears in both the aura and co-occurrence matrices for textures that are synthesized from Gibbs random-field models. We derive this structure by characterizing configurations of the distribution that are most likely to be synthesized when the Gibbs energy is minimized. This minimization is an important part of applications that use the Gibbs model within a Bayesian estimation framework for maximum a posteriori (MAP) estimation. In particular, we show that the aura matrix will become tridiagonal for an attractive autobinomial field when suitable constraints exist on the histogram, neighborhood, and image sizes. Under the same constraints, but where the field is repulsive instead of attractive, the matrix will become antitridiagonal. The interpretation of this structure is especially significant for modeling textures with minimum-energy configurations: zeros in the matrix prohibit certain colors from occurring next to each other, thus prohibiting large classes of textures from being formed.This work was supported by the National Science Foundation and the Defense Advanced Research Projects Agency under grant MIP-88-14612, the National Science Foundation under grant IRI-8719920, and the Rome Air Development Center of the U.S. Air Force Systems Command and the Defense Advanced Research Projects Agency under contract F30602-89-C-0022.     

Degradation reduction in optics imagery using Toeplitz structure

This paper is concerned with improvement in optical image quality by image restoration. Image restoration is an ill-posed inverse problem which involves the removal or minimization of degradations caused by noise and blur in an image, resulting from, in this case, imaging through a medium. Our work here concerns the use of the underlying Toeplitz structure of such problems, and associated techniques for accelerating the convergence of iterative image restoration computations. Denoising methods, including total variation minimization, followed by segmentation-based preconditioning methods for minimum residual conjugate gradient iterations, are investigated. Regularization is accomplished by segmenting the image into (smooth) segments and varying the preconditioners across the segments. By taking advantage of the Toeplitz structure, our algorithms can be implemented with computational complexity of onlyO (ln ² logn), wheren ² is the number of pixels in the image andl is the number of segments used. Also, parallelization is straightforward. Numerical tests are reported for atmospheric imaging problems, including the case of spatially varying blur. Research supported in part by a National Science Foundation Postdoctoral Research Fellowship. Research sponsored by the U.S. Air Force Office of Scientific Research under grant F49620-97-1-1039. Research sponsored by the U.S. Air Force Office of Scientific Research under grant F49620-97-1-0139, and by the National Science Foundation under grant CCR-96-23356. Research sponsored by the National Science Foundation under grant CCR-96-23356.     

Optimal parallel verification of minimum spanning trees in logarithmic time

We present the first optimal parallel algorithms for the verification and sensitivity analysis of minimum spanning trees. Our algorithms are deterministic and run inO(logn) time and require linear-work in the CREW PRAM model. These algorithms are used as a subroutine in the linear-work randomized algorithm for finding minimum spanning trees of Cole, Klein, and Tarjan. Research partially supported by a National Science Foundation Graduate Fellowship and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, Grant No. NSF-STC88-09648. Research at Princeton University was partially supported by the National Science Foundation, Grant No. CCR-8920505, the Office of Naval Research, Contract No. N00014-91-J-1463, and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, Grant No. NSF-STC88-09648.     

The Impact of Non-Gaussian Distribution Traffic on Network Performance

Recent extensive measurements of real-life traffic demonstrate that the probability density function of the traffic in non-Gaussian.If a traffic model does not capture this characteristics,any analytical or simulation results will not be accurate.In this work,we study the impact of non-Gaussian traffic on network performance,and present an approach that can accurately model the marginal distribution of real-life traffic.Both the long-and short-range autocorrelations are also accounted.We show that the removal of non-Gaussian components of the process does not change its correlation structure,and we validate our promising procedure by simulations.     

A systematic incrementalization technique and its application to hardware design

A systematic transformation method based on incrementalization and value caching generalizes a broad family of program optimizations. It yields significant performance improvements in many program classes, including iterative schemes that characterize hardware specifications. CACHET is an interactive incrementalization tool. Although incrementalization is highly structured and automatable, better results are obtained through interaction, where the main task is to guide term rewriting based on data-specific identities. Incrementalization specialized to iteration corresponds to strength reduction, a familiar program improvement technique. This correspondence is illustrated by the derivation of a hardware-efficient nonrestoring square-root algorithm, which has also served as an example of theorem prover-based implementation verification. Published online: 9 October 2001 RID="*" ID="*"S.D. Johnson supported, in part, by the National Science Foundation under grant MIP-9601358. RID="**" ID="**"Y.A. Liu supported in part by the National Science Foundation under grant CCR-9711253, the Office of Naval Research under grant N00014-99-1-0132, and Motorola Inc. under a Motorola University Partnership in Research Grant. RID="***" ID="***"Y. Zhang is a student recipient of a Motorola University Partnership in Research Grant.     

Semiconvergence of P-regular splittings for solving singular linear systems

We investigate necessary and sufficient conditions for semiconvergence of a splitting for solving singular linear systems, where the coefficient matrix A is a singular EP matrix. When A is a singular Hermitian matrix, necessary and sufficient conditions for semiconvergence of P-regular splittings are given, which generalize known results. As applications, the necessary and sufficient conditions for semiconvergence of block AOR and SSOR iterative methods are derived. A numerical example is given to illustrate the theoretical results. The work is supported by the National Natural Science Foundation of China under grant 10371056, the Foundation for the Authors of the National Excellent Doctoral Thesis Award of China under grant 200720 and the Natural Science Foundation of Jiangsu Province of China under grant BK2006725.     

Algorithms for bichromatic line-segment problems and polyhedral terrains

We consider a variety of problems on the interaction between two sets of line segments in two and three dimensions. These problems range from counting the number of intersecting pairs between m blue segments andn red segments in the plane (assuming that two line segments are disjoint if they have the same color) to finding the smallest vertical distance between two nonintersecting polyhedral terrains in three-dimensional space. We solve these problems efficiently by using a variant of the segment tree. For the three-dimensional problems we also apply a variety of recent combinatorial and algorithmic techniques involving arrangements of lines in three-dimensional space, as developed in a companion paper.Work on this paper by the first author has been supported in part by the National Science Foundation under Grant CCR-9002352. Work by the second author was supported in part by the National Science Foundation under Grant CCR-8714565. The fourth author has been supported in part by the Office of Naval Research under Grant N0014-87-K-0129, by the National Science Foundation under Grant NSF-DCR-83-20085, by grants from the Digital Equipment Corporation and the IBM Corporation, and by a grant from the US-Israeli Binational Science Foundation.     

Space-bounded simulation of multitape turing machines

A new proof of a theorem of Hopcroft, Paul, and Valiant is presented: Every deterministic multitape Turing machine of time complexityT(n) can be simulated by a deterministic Turing machine of space complexityT(n)/logT(n). The proof includes an overlap argument.Supported by National Science Foundation Grant No. MCS-78-04343.Supported by National Science Foundation Grant No. MCS-77-19754 and the Fannie and John Hertz Foundation.     

Verification of evolving software via component substitutability analysis

This paper presents an automated and compositional procedure to solve the substitutability problem in the context of evolving software systems. Our solution contributes two techniques for checking correctness of software upgrades: (1) a technique based on simultaneous use of over-and under-approximations obtained via existential and universal abstractions; (2) a dynamic assume-guarantee reasoning algorithm—previously generated component assumptions are reused and altered on-the-fly to prove or disprove the global safety properties on the updated system. When upgrades are found to be non-substitutable, our solution generates constructive feedback to developers showing how to improve the components. The substitutability approach has been implemented and validated in the ComFoRT reasoning framework, and we report encouraging results on an industrial benchmark. This is an extended version of a paper, Dynamic Component Substitutability Analysis, published in the Proceedings of the Formal Methods 2005 Conference, Lecture Notes in Computer Science, vol. 3582, by the same authors. This research was sponsored by the National Science Foundation under grant nos. CNS-0411152, CCF-0429120, CCR-0121547, and CCR-0098072, the Semiconductor Research Corporation under grant no. TJ-1366, the US Army Research Office under grant no. DAAD19-01-1-0485, the Office of Naval Research under grant no. N00014-01-1-0796, the ICAST project and the Predictable Assembly from Certifiable Components (PACC) initiative at the Software Engineering Institute, Carnegie Mellon University. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of any sponsoring institution, the US government or any other entity.     

Randomized competitive algorithms for the list update problem

We prove upper and lower bounds on the competitiveness of randomized algorithms for the list update problem of Sleator and Tarjan. We give a simple and elegant randomized algorithm that is more competitive than the best previous randomized algorithm due to Irani. Our algorithm uses randomness only during an initialization phase, and from then on runs completely deterministically. It is the first randomized competitive algorithm with this property to beat the deterministic lower bound. We generalize our approach to a model in which access costs are fixed but update costs are scaled by an arbitrary constantd. We prove lower bounds for deterministic list update algorithms and for randomized algorithms against oblivious and adaptive on-line adversaries. In particular, we show that for this problem adaptive on-line and adaptive off-line adversaries are equally powerful.A preliminary version of these results appeared in a joint paper with S. Irani in theProceedings of the 2nd Symposium on Discrete Algorithms, 1991 [17].This research was partially supported by NSF Grants CCR-8808949 and CCR-8958528.This research was partially supported by NSF Grant CCR-9009753.This research was supported in part by the National Science Foundation under Grant CCR-8658139, by DIMACS, a National Science Foundation Science and Technology center, Grant No. NSF-STC88-09648.     

An evaluation of buffer management strategies for relational database systems

In this paper we present a new algorithm, DBMIN, for managing the buffer pool of a relational database management system. DBMIN is based on a new model of relational query behavior, thequery locality set model (QLSM). Like the hot set model, the QLSM has an advantage over the stochastic models due to its ability to predict future reference behavior. However, the QLSM avoids the potential problems of the hot set model by separating the modeling of reference behavior from any particular buffer management algorithm. After introducing the QLSM and describing the DBMIN algorithm, we present a performance evaluation methodology for evaluating buffer management algorithms in a multiuser environment. This methodology employed a hybrid model that combines features of both trace-driven and distribution-driven simulation models. Using this model, the performance of the DBMIN algorithm in a multiuser environment is compared with that of the hot set algorithm and four more traditional buffer replacement algorithms.This research was partially supported by the Department of Energy under Contract No. DE-AC02-81ER10920 and the National Science Foundation under grant MCS82-01870.     

Gibbs random fields, cooccurrences, and texture modeling

Gibbs random field (GRF) models and features from cooccurrence matrices are typically considered as separate but useful tools for texture discrimination. The authors show an explicit relationship between cooccurrences and a large class of GRF's. This result comes from a new framework based on a set-theoretic concept called the “aura set” and on measures of this set, “aura measures.” This framework is also shown to be useful for relating different texture analysis tools. The authors show how the aura set can be constructed with morphological dilation, how its measure yields cooccurrences, and how it can be applied to characterizing the behavior of the Gibbs model for texture. In particular, they show how the aura measure generalizes, to any number of gray levels and neighborhood order, some properties previously known for just the binary, nearest-neighbor GRF. Finally, the authors illustrate how these properties can guide one's intuition about the types of GRF patterns which are most likely to form     

Dynamic file grouping for load balancing in streaming media clustered server systems

A dynamic file grouping strategy is presented to address the load balancing problem in streaming media clustered server systems. This strategy increases the server cluster availability by balancing the workloads among the servers within a cluster. Additionally, it improves the access hit ratio of cached files in delivery servers to alleviate the limitation of I/O bandwidth of storage node. First, the load balancing problem is formulated as a two layers semi-Markov switching state-space control process. This analytic model captures the behaviors of streaming media clustered server systems accurately, and is with constructional flexibility and scalability. Then, a policy iteration based reinforcement learning algorithm is proposed to optimize the file grouping policy online. By utilizing the features of the event-driven policy, the proposed optimization algorithm is adaptive and with less computational cost. Simulation results demonstrate the effectiveness of the proposed approach. Recommended by Editor Hyun Seok Yang. This work was supported by the National Natural Science Foundation of China under grant Nos. 60774038, 60574065, National 863 HI-TECH Research & Development Plan of China under grant Nos. 2006AA01Z114, 2008AA01A317, Natural Science Foundation of Anhui Province under grant No. 070412063, Graduate Student Innovation Foundation of USTC under grant No. KD2006036, and Science Research Development Foundation of HFUT under grant No. GDBJ2008-045. Qi Jiang received the B.S. degree in Industrial Electrical Automation from Southeast University in 1989 and the Ph.D. degree in Control Science and Engineering from University of Science and Technology of China in 2008. He is currently a Post-doc in USTC. His research interests include optimization and control of stochastic dynamic systems, and performance analysis and optimization of network communication systems. Hong-Sheng Xi received the M.S. degree in Applied Mathematics from University of Science and Technology of China in 1977. He is currently a Professor in Department of Automation, USTC. His research interests include discrete event dynamic systems, performance analysis and optimization of network communication systems, robust control, and network security. Bao-Qun Yin received the B.S. degree in Mathematics from Sichuan University in 1985, the M.S. degree in Applied Mathematics and the Ph.D. degree in Pattern Recognition and Intelligent Systems from University of Science and Technology of China in 1993 and 1998, respectively. He is currently a Professor in Department of Automation, USTC. His research interests include discrete event dynamic systems, and Markov decision processes.     

On the linear span of the p -ary cascaded GMW sequences

In this paper, a recursion is derived to compute the linear span of the p-ary cascaded GMW sequences. It is the first time to determine the linear span of the p-ary cascaded GMW sequence without any restriction on the parameters completely. Whereas, the known result on the p-ary cascaded GMW sequence with the specific parameters in the literature could be viewed as a special case of the new result. Supported by the National Natural Science Foundation of China (Grant No. 60302015), the Foundation for the Author of National Excellent Doctoral Dissertation of China (Grant No. 200341), and Sichuan Youth Science Foundation (Grant No. 04ZQ026-048)     

On non-determinancy in simple computing devices

Summary This paper studies one-tape Turing machines with k read-only heads which are restricted to the original input. The main result shows that if any set accepted by such a 3-head non-deterministic Turing machine can be accepted by a deterministic Turing machine with more read-only heads, then the deterministic and non-deterministic context-sensitive languages are identical. Several related results are derived and some tantalizing open problems are discussed.This research has been supported in part by National Science Foundation Grant GJ-155.     

Partitioning trees: Matching,domination, and maximum diameter

A matching and a dominating set in a graph G are related in that they determine diameter-bounded subtree partitions of G. For a maximum matching and a minimum dominating set, the associate partitions have the fewest numbers of trees. The problem of determining a minimum dominating set in an arbitrary graph G is known to be NP-complete. In this paper we present a linear algorithm for partitioning an arbitrary tree into a minimum number of subtrees, each having a diameter at mostk, for a givenk.Research supported in part by the National Science Foundation under Grant ENG 7902960.Research supported in part by the National Science Foundation under Grant STI 7902960.     

On optimizing the evaluation of a set of expressions

A branch- and-bound type algorithm is developed to optimize the evaluation of a set of expressions. The algorithm proceeds in a depth-first manner and achieves an optimal solution. The algorithm is applied to optimize the evaluation of sets of relational expressions. Analogies to the heuristic information associated with theA* algorithm are investigated. Examples are presented illustrating the use of the algorithm. Pragmatics associated with the algorithm and its application to Boolean optimization are also discussed.Research supported by the National Science Foundation under grant number NSF MCS 79-19418 and by the National Aeronautics and Space Administration under grant number NGR 21-002-270-9.     

Extended parallelism in the Gröbner basis algorithm

This paper presents a new parallel implementation to compute Gröbner bases utilizing two different forms of parallelism. A coarse-grain technique developed by Jean-Phillipe Vidal expands and reducesS-polynomials in parallel. A finegrain technique, proposed by Melenk and Neun, constructs a pipeline of processors to overlap execution of the reduction operations. A hybrid algorithm that outperforms both of the original approaches is presented. The combined algorithm requires the user to select the appropriate allocation of processors to the two styles of parallelism, and uses this static assignment throughout the computation. The paper also discusses the design and implementation approaches used to construct an efficient version of this algorithm.The author was partially supported by an NSF graduate fellowship. This research was sponsored in part by the Avionics Laboratory, Wright Research and Development Center, Aeronautical Systems Division (AFSC), U.S. Air Force, Wright-Patterson AFB, Ohio 45433-6543 under Contract F33615-90-C-1465, ARPA Order No. 7597 and in part by the National Science Foundation under grant CCR-87-226-33. The views and conclusions contained in this document are those of the author and should not be interpreted as representing the official policies, either expressed or implied, of the National Science Foundation or the U.S. government.     

Coordinated Collective Motion of Groups of Autonomous Mobile Robots with Directed Interconnected Topology

Coordinated collective motion of groups of autonomous mobile robots is studied. A qualitative analysis for the collective dynamics of multiple autonomous robots with directed interconnected topology using nearest neighbor rules is given. A necessary and sufficient graphical condition is proposed to guarantee that the headings of all robots converge to the same heading. The graph having a globally reachable node plays a crucial role in convergence analysis. Furthermore, we show that the globally reachable node having no neighbors serves as a group leader as a special case Supported in part by National Natural Science Foundation of China under the grant 60604001 and 60674081, Natural Science Research Project of Hubei Provincial Department of Education under the grant D20081306 and Scientific Innovation Team Project of Hubei Provincial College under the grant T200809.