Assume that each edge e of a graph G is assigned a list (set) L(e) of colors. Then an edge-coloring of G is called an L-edge-coloring if each edge e of G is colored with a color contained in L(e). In this paper, we prove that any series-parallel simple graph G has an L-edge-coloring if |L(e)| max{3,d(v),d(w)} for each edge e = vw, where d(v) and d(w) are the degrees of the ends v and w of e, respectively. Our proof yields a linear algorithm for finding an L-edge-coloring of series-parallel graphs.

Karger, Motwani and Sudan presented a graph coloring algorithm based on semidefinite programming, which colors any k-colorable graph with maximum degree Δ using (Δ1-2/k) colors. This algorithm leads to an algorithm for k-colorable graph using (n 1-3/(k+1)) colors. This improved Wigderson's algorithm, which uses O(n1-1/(k-1)) colors, containing as a subroutine an algorithm using (Δ+1) colors for graphs with maximum degree Δ. It is easy to imagine that an algorithm which uses less colors in terms of Δ leads to an algorithm which uses less colors in terms of n. In this paper, we consider this influence assuming that we have an algorithm which uses (Δ 1-x/k) colors for 2

In this letter, we propose a new method to detect faces in color images based on the characterized convex regional relationship. We detect skin and hair likeness regions using the derived skin and hair color models and the convex skin likeness and hair likeness regions are adopted as the characteristic convex regions. Finally, human faces can be detected via their intersection relationship. The proposed algorithm can accomplish face detection in an image including not only single face but also multi-faces and also detect deformed faces efficiently. To validity the effectiveness of the proposed method, we make experiments with various cases.

The present paper deals with the blind deconvolution of a Multiple-Input Multiple-Output Finite Impulse Response (MIMO-FIR) system. To deal with the blind deconvolution problem using the second-order statistics (SOS) of the outputs, Hua and Tugnait considered it under the conditions that a) the FIR system is irreducible and b) the input signals are spatially uncorrelated and have distinct power spectra. In the present paper, the problem is considered under a weaker condition than the condition a). Namely, we assume that c) the FIR system is equalizable by means of the SOS of the outputs. Under b) and c), we show that the system can be blindly identified up to a permutation, a scaling, and a delay using the SOS of the outputs. Moreover, based on this identifiability, we show a novel necessary and sufficiently condition for solving the blind deconvolution problem, and then, based on the condition, we propose a new algorithm for finding an equalizer using the SOS of the outputs, while Hua and Tugnait have not proposed any algorithm for solving the blind deconvolution under the conditions a) and b).

Let each vertex v of a graph G have a positive integer weight ω(v). Then a multicoloring of G is to assign each vertex v a set of ω(v) colors so that any pair of adjacent vertices receive disjoint sets of colors. A partial k-tree is a graph with tree-width bounded by a fixed constant k. This paper presents an algorithm which finds a multicoloring of any given partial k-tree G with the minimum number of colors. The computation time of the algorithm is bounded by a polynomial in the number of vertices and the maximum weight of vertices in G.

Assume that each edge e of a graph G is assigned a list (set) L(e) of colors. Then an edge-coloring of G is called an L-edge-coloring if each edge e of G is colored with a color contained in L(e). It is known that any series-parallel simple graph G has an L-edge-coloring if either (i) |L(e)| max{4,d(v),d(w)} for each edge e=vw or (ii) the maximum degree of G is at most three and |L(e)| 3 for each edge e, where d(v) and d(w) are the degrees of the ends v and w of e, respectively. In this paper we give a linear-time algorithm for finding such an L-edge-coloring of a series-parallel graph G.

In this paper, a novel chrominance up-sampling algorithm for color post-processing is described. This scheme exploits so-called inter-chrominance coherence, i.e., luminance and chrominance signals share the same structural information. Usually luminance has higher spatial resolution than chrominance in compression coding standards. So the idea is to up-sample chrominance signals using the structural information extracted from the luminance.

We developed a new method to improve the efficiency of the PDP (plasma display panel) by the use of a novel protecting film or Gd doped MgO film. In the cells of the PDP, the VUV (vacuum ultraviolet ray) is generated by Xe discharge. The VUV is simply absorbed by the protecting film or MgO film. Therefore, normally the absorbed VUV doesn't contribute to the light conversion efficiency. However, the novel protecting film or MgO:Gd film radiates the ultraviolet ray of which 317 nm wavelength, by the irradiation of the shorter wavelength VUV, and it excites the blue phosphor. Consequently the efficiency of blue emission is improved.

Uniform color spaces are very important in color engineering, image source coding and multimedia information processing. In spite of many efforts have been paid on the subject, however, construction of an exact uniform color space seems difficult until now. Existing approaches mainly used local and heuristic approximations. Moreover, there seemed also certain confusion in definitions of the uniform spaces. In this paper we discuss the issue from a point of view of global Riemannian geometry. The equivalence between global and local definitions of uniform space are shown. Then both an exact and a simplified algorithm are presented to uniformize either a part or the totality of a color space. These algorithms can be expected to find applications in optimal quantization of color information.

In previous work we have proposed a steganographic technique for gray scale images called BPCS-Steganography. We also apply this technique to full color images by decomposing the image into its three color component images and treating each as a gray scale image. This paper proposes a method to apply BPCS-Steganography to palette-based images. In palette-based images, the image data can be decomposed into color component images similar to those of full color images. We can then embed into one or more of the color component images. However, even if only one of the color component images is used for embedding, the number of colors in the palette after embedding can be over the maximum number allowed. In order to represent the image data in palette-based format, color quantization is therefore needed. We cannot change the pixel values of the color component image that contains the embedded information, but can only change the pixel values of the other color component images. We assume that the degrading of the color component2 image with information embedded is smaller than that of the color component images that are used for color reduction. We therefore embed secret information into the G component image, because the human visual system is more sensitive to changes the luminance of a color, and G has the largest contribution to luminance of the three color components. In order to reduce the number of colors, the R and B component images are then changed in a way that minimizes the square error.

There are several kinds of coloring of digraphs, such as vertex-coloring and arc-coloring. We call an arc-coloring of a digraph G the first type if it is an assignment of colors to the arc set of G in which no two consecutive arcs have the same color. In some researches, the arc-coloring of first type has been associated with the minimum number of the vertex-coloring called chromatic number. Considering the class of line digraphs, an arc-coloring of a digraph G of the first type is equivalent to the vertex-coloring of its line digraph L(G). In this paper, we study the arc-coloring of the first type and the vertex-coloring of line digraphs. We give the upper bound of the chromatic number of L(G) by the chromatic number of a digraph G which admits loops. It is also shown that there exists quite a small integer k so that the iterated line digraph Lk(G) is 3-vertex-colorable. As a consequence, we derive the chromatic number of de Bruijn and Kautz digraphs.

Coloring problem is a well-known combinatorial optimization problem of graphs. This paper considers H-coloring problems, which are coloring problems with restrictions such that some pairs of colors can not be used for adjacent vertices. The restriction of adjacent colors can be represented by a graph H, i.e., each vertex represents a color and each edge means that the two colors corresponding to the two end-vertices can be used for adjacent vertices. Especially, H-coloring problem with a complete graph H of order k is equivalent to the traditional k-coloring problem. This paper presents sufficient conditions such that H-coloring problem can be reduced to an H-coloring problem, where H is a subgraph of H. And it shows a hierarchy about classes of H-colorable graphs for any complement graph H of a cycle of order odd n 5.

A kind of online edge-coloring problems on bipartite graphs is considered. The input is a graph (typically with no edges) and a sequence of operations (edge addition and edge deletion) under the restriction that at any time the graph is bipartite and degree-bounded by k, where k is a prescribed integer. At the time of edge addition, the added edge can be irrevocably assigned a color or be left uncolored. No other coloring or color alteration is allowed. The problem is to assign colors as many times as possible using k colors. Two algorithms are presented: one with competitiveness coefficient 1/4 against oblivious adversaries, and one with competitiveness coefficient between 1/4 and 1/2 with the cost of requiring more random bits than the former algorithm, also against oblivious adversaries.

An approach to the enhancement of speech signals corrupted by additive colored noise is proposed and the system architecture to implement the proposed idea in real-time communication is introduced in this paper. A combination of a bandpass FIR filtering technique with wiener filtering is used to improve the SNR for speech signals. The average SNR improvement (between input and output SNR) is 22.48 dB. The additive noises are the sound from a turbo prop aircraft. The system, which shows excellent performance, is designed based on a 16 bits fixed point DSP (ADSP-2181) from Analog Devices. Experiment results demonstrate that the FIR filter leads to a significant gain in SNR, thus visibly improvement for the quality and the intelligibility of the speech.

We propose a new field of application for machine vision, a machine-vision-based cash-register system. We show that the overall system of color analysis for such an application should include the method of color distribution analysis which we propose, and that the analysis of shape and size is important. We present our test results and identify a few technical issues which may have to be considered for its practical utilization.

In this paper, we first introduce the notion of texture precision given the 3d geometry of a scene. We then provide an algorithm to acquire a texture/color map of the scene within a given precision. The texture map is obtained using projective devices (like pinhole sensing device) from data acquired either in the real world or computer-synthesized. Finally, we describe a procedure to obtain level of precisions by combining a modified edge-collapse geometry technique with an appropriate remapping texture engine. We report on our experiments and give perspectives for further research.

An advanced spare-connection scheme for K-out-of-N redundancy is proposed for constructing fault-tolerant ring- or toroidal mesh-connected processing-node arrays able to enhance emulation of binary hypercubes by using bypass networks. With this scheme, a component redundancy configuration for a base array with a fixed number of primary nodes, such as that for 8-node ring or 32-node toroidal mesh, can be constructed by using bypass links with a segmented bus structure to selectively connect the primary nodes to a spare node in parallel. These bypass links are allocated to the primary nodes by graph-node coloring with a minimum inter-node distance of three in order to use the bypass links as the hypercube connections as well as to attain strong fault tolerance for reconfiguring the base array with the primary network topology. An extended redundancy configuration for a large fault-tolerant array can be constructed by connecting the component configurations by using external switches of a hub type provided at the bus nodes of the bypass links. This configuration has a network topology of the parallel star-connections of sub-hypercubes whose diameter is smaller than that of the regular hypercube.

Feasibility of a color shutter using ferroelectric liquid crystal polymer panel and a field sequential ultra high-resolution CRT with the color shutter as a color field-switching device was studied. The color shutter consists of ferroelectric liquid crystal polymer panels and color polarizers. First, evaluation indices of the color shutter, such as the color gamut, the average transmittance and the white chromaticity shift, were formulated, and the simulation of evaluation indices was examined, where the spectral transmittance characteristics of the polarizer were changed in steps. It was indicated that there was a tradeoff between the color gamut and the average transmittance of the color shutter, and the shutter configuration that provides 0.096 (63% to NTSC) color gamut and 4.3% average transmittance was selected based on the simulation results. Next, the three-line simultaneous scanning method of the monochrome CRT was improved so that the disturbance due to the raster modulation was eliminated by averaging the distribution of beam luminance apparently. To confirm results of the study, the prototype of 21-inch screen size was produced, and the following display characteristics was obtained: luminance of 71 cd/m2, contrast ratio of 146:1 and color gamut of 0.096 (63% to NTSC) under the standard room lighting environment.

Large amounts of color-printed documents are published now everyday. Some OCR approaches of color-printed document images are provided, but they cannot normally work if the input images skew. In the past years, many algorithms are provided to detect the skew of monochrome document images but none of them process color-printed document images. All of these methods assume that text is printed in black on a white background and cannot be applied to detect skew in color-printed document images. In this paper, we propose an algorithm to detect the skew angle of a color-printed document image and reconstruct it. Our approach first determines variation of color-transition count at each angle (from -45 to +45) and the angle of maximal variation is regarded as the skew angle. Then, a scanning-line model reconstructs the image. We test 100 color-printed document images of various kinds and get good results (93 succeed and 7 fail). The average processing time of A4 size image is 2.76 seconds and the reconstruction time is 3.97 seconds on a Pentium III 733 PC.

In this paper, we consider the net assignment problem in the logic emulation system. This problem is also known as the board-level-routing problem. There are field programmable logic arrays (FPGAs) and crossbars on an emulator board. Each FPGA is connected to each crossbar. Connection requests between FPGAs are called nets, and FPGAs are interconnected through crossbars. We are required to assign each net to the suitable crossbar. This problem is known to be NP-complete in general. A polynomial time algorithm is known for a certain restricted case, in which we treat only 2-terminal nets. In this paper we propose a new polynomial time algorithm for this case.