The direct implementation of the conventional vector quantization codec requires unfeasibly large-sized codebooks as the block length increases. This paper discusses a systematic approach for constructing vector quantization codec with large block length which can be compared with that of the transform coding techniques. Here we propose a class of Recursive Vector Quantizer (RVQ) which recursively encodes a given large-dimensional input vector into a series of indices of reproduction vectors derived from a small-sized and small-dimensional codebook. This codebook is referred to as a wavelet codebook. Note that a single codebook will be used repeatedly in every stage of the hierarchical quadtree decomposition of input vectors. For this construction of the RVQ system, the mean value of each input vector is extracted and then encoded separately. The side information, which represents how the wavelet vectors are combined for reproducing the replica of the input vector, can be efficiently encoded by using the binary tree code. We also give a design example of a 64-dimensional RVQ using a four-dimensional tree search vector quantizer as a wavelet quantizer. The results of computer simulation show effectiveness of the RVQ for video signals. For example, the signal-to-noise ratio of 37.6 dB is obtained at the rate of 1.27 bits per pixel for the image data Zelda".

This paper newly proposes HOMomorphic Transformer (HOMT) in order to formalize relations among strictness-related analyses (SRAs) on first-order functional programs. A HOMT is defined to be a composition of special instances of abstract interpretation, and has enough ability to treat known SRAs including head/tail/total strictness detection on nonflat domains. A set of HOMTs, furthermore, is an algebraic space such that some composition of HOMTs can be reduced to a simpler HOMT. This structure gives a transformational mechanism between various SRAs, and further clarifies the equivalence and the hierarchy among them. First, we show a construction of a HOMT as a composition of Unit-HOMTs (U-HOMTs) which are specified by quadruplet representations. Second, algebraic relations among HOMTs are shown as reduction rules among specific pairs of quadruplet representations. Thus, hierarchy among HOMTs can be clarified by finding some adequate quadruplet representation which bridges a HOMT to the other. Third, various SRAs are formalized as HOMTs in either forward or back-ward manners. They are also shown to be safe under unified discussions. Finally, their equivalence and hierarchy are examined in terms of an algebraic structure of HOMTs.

In order to realize a robust computer vision system which can cope with a variety of scenes, we propose a new scheme to integrate multiple vision algorithms in a cooperative framework. The key concepts of the scheme can be summarized as follows: (1) A vision algorithm is implemented as an independent specialist. (2) There are multiple specialists in the system. (3) All specialists work in parallel. (4) Each specialist tries to solve the vision problem in its own way. (5) A specialist may communicate with another specialist when it needs a help. The scheme clearly has a nature of task parallelism and is suitable to be built on a parallel computer. In order to demonstrate the feasibility of the proposed scheme, we are developing two computer vision systems in two different approaches which are both based on the same concept. They are called a cooperative approach and a concurrent top-down approach. Roughly speaking, the former is an integration of multiple algorithms in a bottom-up framework while the latter is in a top-down framework. Preliminary results obtained by the systems are also presented.

Distributed match-making is a paradigm that deals with the match-making property of distributed issues such as name service, mutual exclusion, and replicated data management. In order to realize distributed match-making, two kinds of subsets with certain properties must be constructed for each process. We call a set of the subsets defined for all processes an arrangement." In this paper, we discuss arrangements for symmetric and fault-tolerant distributed match-making. First, it is shown that a combinatorial design called a symmetric balanced incomplete block design (SBIBD) can be applied to fault-tolerant distributed match-making. However, an SBIBD does not realize symmetry. We therefore focus on ways of achieving this. A completely symmetric arrangement for fault-tolerant distributed match-making does not always exist. We show that a completely symmetric arrangement called a symmetric resilient arrangement (SRA) exists when n/m is an integer, where n is the number of processes and m-1 is the resiliency of an algorithm. We present a method of constructing an SRA and generalize the method to allow construction of a generalized SRA (GSRA), which is almost symmetric and can be constructed with any combination of n and m. The communication complexity of fault-tolerant distributed match-making is also discussed. We show that the communication complexity of our SRA is 2mn and that the communication complexity of our GSRA is equal to or less than 2 min (mn/m, n). We also show that a lower bound of the communication complexity of an SBIBD is 2mn.

This paper considers processor utilization in faulty hypercube multiprocessor. The utilization is proportional to the continuity of processor allocation model based on Gray code. Busy and faulty processors make this model fragmented. That prevents assigning of larger tasks onto hypercube and decreases processor utilization. A set of procedures is derived which reassigns active tasks so that a new task configuration along with faulty processors makes as little damage as possible to the continuity of allocation model. First, a hypercube fragmentation measure is defined and a task reassigning technique presented. Then, procedures are given which determine: (1) active tasks to be reassigned, (2) their new optimal locations and (3) the shortest reassigning paths. At last, it is proved that while increasing processor utilization, presented scheme minimizes task reconfiguration overhead.

Logarithmic arithmetic (LA) is a very fast computational method for real numbers. And its precision is better than a floating point arithmetic of equivalent word length and range. This paper shows a method to use LA in computer graphics--picture generation of almost any kind. Various experiments are done--from curve drawing to 3D image generation. The results are all excellent for quality and speed.