Implementation of a vector quantization codebook design technique based on a competitive learning artificial neural network

We describe an implementation of a vector quantization codebook design algorithm based on the frequencysensitive competitive learning artificial neural network. The implementation, designed for use on high-performance computers, employs both multitasking and vectorization techniques. A C version of the algorithm tested on a CRAY Y-MP8/864 is discussed. We show how the implementation can be used to perform vector quantization, and demonstrate its use in compressing digital video image data. Two images are used, with various size codebooks, to test the performance of the implementation. The results show that the supercomputer techniques employed have significantly decreased the total execution time without affecting vector quantization performance.This work was supported by a Cray University Research Award and by NASA Lewis research grant number NAG3-1164.     

Mean-field phase transitions and correlation functions for Gibbs random fields

The use of Gibbs random fields (GRF) to model images poses the important problem of the dependence of the patterns sampled from the Gibbs distribution on its parameters. Sudden changes in these patterns as the parameters are varied are known asphase transitions. In this paper we concentrate on developing a general deterministic theory for the study of phase transitions when a single parameter, namely, the temperature, is varied. This deterministic framework is based on a technique known as themean-field approximation, which is widely used in statistical physics. Our mean-field theory is general in that it is valid for any number of gray levels, any pairwise interaction potential, any neighborhood structure or size, and any set of constraints imposed on the desired images. The mean-field approximation is used to compute closed-form estimates of the critical temperatures at which phase transitions occur for two texture models widely used in the image modeling literature: the Potts model and the autobinomial model. The mean-field model allows us to gain insight into the Gibbs model behavior in the neighborhood of these temperatures. These analytical results are verified by computer simulations that use a novel mean-field descent algorithm. An important spinoff of our mean-field theory is that it allows us to compute approximations for the correlation functions of GRF models, thus bridging the gap between neighborhood-based and correlation-baseda priori image models.The work of I.M. Elfadel was supported in part by the National Science Foundation under grant MIP-91-17724. The work of A.L. Yuille was supported by the Brown, Harvard, and MIT Center for Intelligent Control Systems under U.S. Army Research Office grant DAAL03-86-C-0171, by the Defense Advanced Research Projects Agency under contract AFOSR-89-0506, and by the National Science Foundation under grant IRI-9003306.     

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.     

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.     

Combining databases with prioritized information

To solve a problem one may need to combine the knowledge of several different experts. It can happen that some of the claims of one or more experts may be in conflict with the claims of other experts. There may be several such points of conflict and any claim may be involved in several different such points of conflict. In that case, the user of the knowledge of experts may prefer a certain claim to another in one conflict-point without necessarily preferring that statement in another conflict-point.Our work constructs a framework within which the consequences of a set of such preferences (expressed as priorities among sets of statements) can be computed. We give four types of semantics for priorities, three of which are shown to be equivalent to one another. The fourth type of semantics for priorities is shown to be more cautious than the other three. In terms of these semantics for priorities, we give a function for combining knowledge from different sources such that the combined knowledge is conflict-free and satisfies all the priorities.Jack Minker and Shekhar Pradhan were supported in part by the National Science Foundation grant IRI-89-16059 and Air Force Office of Scientific Research grant 91-0350. V.S. Subrahmanian was supported in part by Army Research Office grant DAAL-03-92-G-0225, Air Force Office of Scientific Research Grant F49620-93-1-0065, and NSF grant IRI-9109755.     

Elements of the information technology of cytological specimen analysis: Taxonomy and factor analysis

The automated software system “Black Square,” Version 1.2 is described. The system is intended for the automation of image processing, analysis, and recognition. It is an open system for generating new knowledge: objects, algorithms of image processing, recognition procedures originally not intended for image processing, and methods for solving applied problems. The system combines the features of information retrieval, reference, training, and computing systems. This work was partially supported by the Russian Foundation for Basic Research, project nos. 03-07-90406, 05-04-49846, and 05-07-08000; by the INTAS grant no. 04-77-7067; by the Cooperative grant “Image Analysis and Synthesis: Theoretical Foundations and Prototypical Applications in Medical Imaging” within agreement between Italian National Research Council and Russian Academy of Sciences (RAS); by the grant of the RAS in the framework of the Program “Fundamental Science to Medicine.” An erratum to this article is available at .     

Algebraic analysis of the generating functional for discrete random sets and statistical inference for intensity in the discrete Boolean random-set model

We consider binary digital images as realizations of a uniformly bounded discrete random set, a mathematical object that can be defined directly on a finite lattice. In this setting we show that it is possible to move between two equivalent probabilistic model specifications. We formulate a restricted version of the discrete-case analog of a Boolean random-set model, obtain its probability mass function, and use some methods of morphological image analysis to derive tools for its statistical inference.This research was partially supported by National Science Foundation grant NSFD CDR 8803012 through the Engineering Research Centers program.     

Development of the open system for the automation of scientific research in image understanding Black Square, Version 1.2

The automated software system Black Square, Version 1.2 is described. The system is intended for the automation of image processing, analysis, and recognition. It is an open system for generating new knowledge: objects, algorithms of image processing, recognition procedures originally not intended for image processing, and methods for solving applied problems. The system combines the features of information retrieval, reference, training, and computing systems. This work was partially supported by the Russian Foundation for Basic Research, project nos. 04-07-90187 and 05-07-08000; by the INTAS grant no. 04-77-7067; by the Cooperative grant “Image Analysis and Synthesis: Theoretical Foundations and Prototypical Applications in Medical Imaging” within agreement between Italian National Research Council and Russian Academy of Sciences (RAS); by the RAS Program “Fundamental Science to Medicine”; and by the Program of Scientific Research of the Presidium of RAS “Mathematical Modeling and Intellectual Systems.”     

A new standard method of subjective assessment of barely visible image artifacts and a new public database

Assessing image quality is an important aspect of developing new display technology. A particularly challenging assessment is determining whether a bitwise lossy operation is visually lossless. We define “visually lossless” and describe a new standard for a subjective procedure to assess whether the image quality meets these criteria. Assessments are made between a reference image and temporally interleaved reference and test images using a forced‐choice procedure. In extensive testing, we have validated that this method is suitable for discriminating between subtle differences in image rendering and is free of observer bias or criteria variability. The results of these tests demonstrate the efficacy of using as few as five randomly chosen observers. We have found that the subjective testing is more reliable than several widely available image quality metrics. As part of this work, we release a database of nearly 0.25 million subjective responses collected from 35 observers to 18 different images. The study uses a largely within‐subjects design and tested observers from two viewing distances. We encourage the use of this dataset in future research to refine objective image quality metrics to improve predictability of subtle but potentially visible compression‐induced image impairments.     

Timing analysis of MRL: A real-time rule-based system

This paper examines issues on how to predict timing behavior of rule-based decision systems for real-time applications. In particular, we focus on the analysis of response time of rule-based programs written in the production system language MRL. The design goal of MRL is to allow programmers to write OPS5-like rule-based programs in a language that is more amenable to formal analysis based on the semantic foundation underlying the language Unity. The language MRL, its analysis algorithms, and its execution system form a package of design tools for programming real-time rule-based decision systems.This project is partly supported by research grants from Office of Naval Research under ONR contract number N00014-89-J-1472 as well as ONR contract number N000014-89-J-1913, by a grant from Texas Advance Technology Program, and also by a grant from Texas Instruments Corporation.     

A Heuristic-adaptive procedure for segmentation of time patterns

This paper treats segmentation of time patterns as a heuristic search problem. Segmentation is formulated in terms of image restoration. An observed pattern, which is the stochastically deformed image of a pure image consisting of a number of regimes, is to be segmented to recover the regimed structure. Standard statistical decision methods are not very useful here because of the computational difficulties involved. The search process described here consists of application of a sequence of heuristic-adaptive operators. Each operator is designed to detect certain flaws in previous segmentations and make modifications accordingly. The search path thus generated ends in a loop from among which the final solution is chosen by an evaluating function. Results of experiments with simulated data are presented and discussed.Research supported in part by an NSF research grant on pattern recognition (GJ-31007X2) and an ONR research contract on computer systems performance evaluation (NOOO14-67-A-0191-0026-01) while the author was at the Division of Applied Mathematics, Brown University, Rhode Island.     

On renamable Horn and generalized Horn functions

A Boolean function in disjunctive normal form (DNF) is aHorn function if each of its elementary conjunctions involves at most one complemented variable. Ageneralized Horn function is constructed from a Horn function by disjuncting a nested set of complemented variables to it. The satisfiability problem is solvable in polynomial time for both Horn and generalized Horn functions. A Boolean function in DNF is said to berenamable Horn if it is Horn after complementation of some variables. Succinct mathematical characterizations and linear-time algorithms for recognizing renamable Horn and generalized Horn functions are given in this paper. The algorithm for recognizing renamable Horn functions gives a new method to test 2-SAT. Some computational results are also given.The authors were supported in part by the Office of Naval Research under University Research Initiative grant number N00014-86-K-0689. Chandru was also supported by NSF grant number DMC 88-07550.The authors gratefully acknowledge the partial support of NSF (Grant DMS 89-06870) and AFOSR (Grant 89-0066 and 89-0512).     

基于双重压缩协议的医学图像压缩方法研究

针对医学图像数据量大、存储和传输对内存和带宽要求高的问题,提出一种基于双重压缩协议的医学图像压缩方法。首先,使用方形网络对图像进行缩小处理;然后,利用数字水印技术在缩小图像的每个像素中,嵌入该像素最佳放大方法的编码;最后,对水印图像利用JPEG-LS无损压缩,得到最终的压缩图像,并进行存储和传输。对磁共振（MR）图像和计算机断层（CT）图像两种医学图像进行实验,实验结果表明,与其他方法相比,所提方法具有明显的优势,在高压缩比的情况下,能够保留良好的图像质量。     

一种基于四叉树分解的图像压缩方法

在信息社会高度发展的今天,图像成为可以传递信息的重要载体之一。由于未经处理的图像信息量非常大,大力研究和开发图像压缩编码技术就非常重要。论文主要探讨对于存在连续阴影或者大量连续相同像素的图像压缩,通过分析RLE算法的不足,提出了一种基于四叉树分解的图像压缩方法,实验表明运用这种方法实现静态图像压缩可以使压缩效率得到进一步的提高,该方法为实现静态图像压缩开辟了新的思路和途径。     

基于ROI的医学图像无损压缩

如何高效地压缩医学图像,以便减少存储空间和传输时间,已经成为迫切需要解决的问题。在分析现有的图像压缩方法和医学图像特点的基础上,针对医学图像有损压缩方法和无损压缩方法各自的不足,研究了一种基于ROI（Region of Interest）的医学图像无损压缩方法。     

A theory of nonmonotonic rule systems II

Conclusions We have proved a number of results on nonmonotonic rule systems. This theory allows us to capture many constructions appearing in the current literature on the logical foundations of artificial intelligence.Our results provide additional tools tying these constructs with traditional methods of logic and recursion theory.In a sequel we shall deal with rule systems containing variables in the rules and with predicate logics. We shall prove results related to the properties of recursive systems that are not necessarily highly recursive. We shall also explore connections with.Work partially supported by NSF grant RII-86-10671 and Kentucky EPSCoR program and ARO contract DAAL03-89-K-0124.Work partially supported by NSF grant DMS-89-02797 and ARO contract DAAG629-85-C-0018.Work partially supported by NSF grants DMS-87-02473 and DMS-90-06413.     

A knowledge-theoretic analysis of uniform distributed coordination and failure detectors

It is shown that, in a precise sense, if there is no bound on the number of faulty processes in a system with unreliable but fair communication, Uniform Distributed Coordination (UDC) can be attained if and only if a system has perfect failure detectors. This result is generalized to the case where there is a bound t on the number of faulty processes. It is shown that a certain type of generalized failure detector is necessary and sufficient for achieving UDC in a context with at most t faulty processes. Reasoning about processes knowledge as to which other processes are faulty plays a key role in the analysis.Received: 15 June 2000, Accepted: 15 April 2004, Published online: 26 July 2004A preliminary version of this paper appeared in the 18th ACM Symposium on Principles of Distributed Computing, 1999, pp. 73-82. Work supported in part by NSF under grants IRI-96-25901 and CTC-0208535, by ONR under grant N00014-02-1-0455, by the DoD Multidisciplinary University Research Initiative (MURI) program administered by the ONR under grants N00014-97-0505 and N00014-01-1-0795, and by a Guggenheim and a Fulbright Fellowship. Sabbatical support from CWI and the Hebrew University of Jerusalem is also gratefully acknowledged.     

带宽限制条件下的实时图像传输研究

图像数据量大的特点使其网络传输具有延迟大、实时性低的特点,在一些应用领域,图像传输的数据量大同实时性要求高之间形成了突出矛盾。论文研究了带宽限制条件下的图像传输策略,在保证图像传输质量、合理控制图像压缩时间的前提下,获得较高的图像压缩比。     

A Hard Dial-a-Ride Problem that is Easy on Average

In the dial-a-ride-problem (Darp) objects have to be moved between given sources and destinations in a transportation network by means of a server. The goal is to find the shortest transportation for the server. We study the Darp when the underlying transportation network forms a caterpillar. This special case is strongly NP-hard in the worst case. We prove that in a probabilistic setting there exists a polynomial time algorithm that finds an optimal solution with high probability. Moreover, with high probability the optimality of the solution found can be certified efficiently. In addition, we examine the complexity of the Darp in a semirandom setting and in the unweighted case.Research supported by the German Science Foundation (DFG, grant FOR 413/1-1)Research supported by the German Science Foundation (DFG, grant Gr 883/10)Research supported by the German Science Foundation (DFG, grant PR 296/6-3)     

Runtime monitoring of timing constraints in distributed real-time systems

Embedded real-time systems often operate under strict timing and dependability constraints. To ensure responsiveness, these systems must be able to provide the expected services in a timely manner even in the presence of faults. In this paper, we describe a run-time environment for monitoring of timing constraints in distributed real-time systems. In particular, we focus on the problem of detecting violations of timing assertions in an environment in which the real-time tasks run on multiple processors, and timing constraints can be either inter-processor or intra-processor constraints. Constraint violations are detected at the earliest possible time by deriving and checking intermediate constraints from the user-specified constraints. If the violations must be detected as early as possible, then the problem of minimizing the number of messages to be exchanged between the processors becomes intractable. We characterize a sub-class of timing constraints that occur commonly in distributed real-time systems and whose message requirements can be minimized. We also take into account the drift among the various processor clocks when detecting a violation of a timing assertion. Finally, we describe a prototype implementation of a distributed run-time monitor.This work was done while the first two authors were at the IBM T.J. Watson Research Center.Supported in part by the Office of Naval Research under grant number N00014-89-J-1040 and by National Science Foundation under grant number CCR-9200858.