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.
Takayuki NAKACHI Tatsuya FUJII
This paper proposes a unified coding algorithm for the lossless and near-lossless compression of still color images. The proposed unified color image coding scheme can control the Peak Signal-to-Noise Ratio (PSNR) of the reconstructed image while the level of distortion on the RGB plane is suppressed to within a preset magnitude. In order to control the PSNR, the distortion level is adaptively changed at each pixel. An adaptive quantizer to control the distortion is designed on the basis of psychovisual criteria. Finally, experiments on Super High Definition (SHD) images show the effectiveness of the proposed algorithm.
Nagul COOHAROJANANONE Kiyoharu AIZAWA
In this paper we will present a new color distance measure, that is, angular distance of cumulative histogram. The proposed measure is robust to light variation. We also applied the weitght value to DR, DG, DB according to a Hue histogram of the query image. Moreover, we have compared the measure to previous popular measure that is cumulative L1 distance measure. We show that our method performed more accurate and perceptually relevant result.
A new adaptive multichannel filtering approach is introduced and analyzed in this paper. The technique is simpler and more appropriate than traditional approaches that have been addressed by means of groupwise vector ordering information. These filters are a two-stage filters based on rational functions (RF) using fuzzy transformations of the Euclidean and angular distances among the different vectors to adapt to local data in the color image. The output is the result of vector rational operation taking into account three fuzzy sub-function outputs. Simulation studies indicate that the filters are computationally attractive and have excellent performance such as edge and details preservation and accurate chromaticity estimation.
Yoshiyuki SHINKAWA Masao J. MATSUMOTO
It is one of the difficulties in enterprise modeling that we must deal with many fragmented pieces of knowledge provided by various domain-experts, which are usually based on mutually different viewpoints of them. This paper presents a formal approach to integrate those pieces into enterprise-wide model units using Rough Set Theory (RST). We focus on business processes in order to recognize and identify the constituents or units of enterprise models, which would compose the model expressing the various aspects of the enterprise. We defined five model unit types of "resource," "organization," "task," "function," and "behavior. " The first three types represent the static aspect of the enterprise, whereas the last two types represent the dynamic aspect of it. Those units are initially elicited from each domain-expert as his/her own individual model units, then they are integrated into enterprise-wide units using RST. Our approach is methodology-free, and any methodologies can include it in their early stage to identify what composes the enterprise.
Hideya TAKAHASHI Kenji YAMADA Eiji SHIMIZU
The visual reality of a holographic image has improved effectively by utilizing multicolor reconstruction procedure. This fact is applicable to a real-time three-dimensional display for a computer generated hologram (CGH). However, it is quite difficult to generate a CGH for multicolor imaging in real-time because a CGH contains essentially a huge amount of information, and increases further information produced by multiplying the number of primary colors for multicolor imaging. Moreover, the optical system is considerably complicated for the multicolor image reconstruction. In this paper, a new method is presented to reconstruct a three dimensional multicolor image from a CGH. In this method, three sub-holograms to reconstruct the primary color images are sampled respectively for reducing the amount of computation and realizing a simple optical system. Fringe patterns are displayed by only one spatial light modulator (SLM) and color crosstalk images are eliminated by a color filtering system for ensuring that each sub-hologram can be only illuminated by the light with an appropriate color. A multicolor imaging method from a CGH is proposed and also the experimental results are shown.
Ho Chi HUANG Kwok Cheong LEE Chun Kwan YIP Hon Lung CHEUNG Po Wing CHENG Hoi Sing KWOK
We have developed a highly integrated liquid-crystal-on-silicon microdisplay for virtual reality applications. The silicon panel of 704 576 pixels was designed and fabricated by a custom 0.35 µm complementary metal oxide semiconductor (CMOS) technology with emphasis on surface planarization. Topographic variation of less than 100 within the pixels was achieved. The pixel pitch was 9.6 µm, fill factor was 88% and display area was 0.36" in diagonal. Eight-bit digital data drivers and gamma-correction circuitry were integrated onto the silicon panel for true gray scale and full color representation. The display panel was assembled with a mixed twisted nematic and birefringence liquid crystal cell for high contract at CMOS compatible voltage. Chromatic characterization of the display using 3-color-in-1 light emitting diode (LED) as light source was performed. Contrast ratios on the pixel array were 95, 72 and 56, respectively, for red, green and blue colors at 3 V root-mean-squared voltage. In addition, a three-dimensional (3D) video stream in interlaced format was generated by a 3D modeling code for test and demonstration. Control logic was implemented to extract the left and right video frames and perform system timing synchronization. The silicon microdisplay was driven in frame inversion and by color sequence. With two sets of silicon microdisplays and eyepieces for each eye, we have demonstrated a 3D stereoscopic display based on the silicon microdisplay technology.
Nobuo FUNABIKI Teruo HIGASHINO
This paper presents a heuristic graph coloring algorithm named MIPS_CLR, a MInimal-state Processing Search algorithm for the graph CoLoRing problem. Given a graph G(V, E), the goal of this NP-complete problem is to find a color assignment to every vertex in V such that any pair of adjacent vertices must not receive the same color but also the total number of colors should be minimized. The graph coloring problem has been widely studied due to its large number of practical applications in various fields. In MIPS_CLR, a construction stage first generates an initial minimal state composed of as many as colored vertices by a simple greedy algorithm, after a maximal clique of G is found by a maximum clique algorithm. Then, a refinement stage iteratively seeks a solution state while keeping minimality in terms of a cost function by a minimal-state transition method. In this method, the schemes of a best color selection, a random color selection, a color assignment shuffle, and a gradual color expansion are used together to realize the discrete descent search with hill-climbing capabilities. The performance of MIPS_CLR is evaluated through solving DIMACS benchmark graph instances, where the solution quality is generally better than existing algorithms while the computation time is comparable with the best existing one. In particular, MIPS_CLR provides new lower bound solutions for several instances. The simulation results confirm the extensive search capability of our MIPS_CLR approach for the graph coloring problem.
Efficient content-based retrieval of complex images is a challenging task since the detected object may appear in various scale, rotation and orientation with a wide variety of background colors and forms. In this paper, we propose a novel representation of objects with multiple colors, the spatial neighborhood-adjacency graph(SNAG), which can serve as a basis for detecting object by color contents from the candidate image. The SNAG consists of a set of main-vertices and two sets of edges. Each main-vertex represents a single color region of multi-colored object, and edges are divided into two classes: Neighborhood edges representing neighborhood relationship between two main-vertices with similar color, and adjacency edges representing adjacency relationship between a main-vertex and another vertex with different color. By investigating whether SNAG of object image is an isomorphic subgraph of SNAG of a candidate image, we can determine whether the similar object exists in the candidate image. In addition, we have also applied the proposed approach to a range of different object detection problems involving complex background, and effectiveness has been proved.
Yoshiyuki SHINKAWA Masao J. MATSUMOTO
Software Composition is one of the major concerns in component based software development (CBSD). In this paper, we present a formal approach to construct software systems from requirements models using available components. We focus on the knowledge resides in the requirements and the components in order to deal with those heterogeneous concepts. This approach consists of three steps. The first step is selecting adaptable components to the requirements model. The requirements and the components are transformed into the form of Σ algebra, and the component adaptability is evaluated by Σ homomorphism. Rough Set Theory (RST) is used to make carriers of two Σ algebras common, which are derived from the requirements and the components. The second step is identifying the control structure of the requirements. Decision tables are used for representing the knowledge on the requirements, and RST is used to optimize the control structure. The third step is to implement the control structure as glue codes which would perform the components appropriately. This approach mainly focuses on enterprise back-office applications in this paper, however, it can be easily applied to other domains, since it assumes the requirements to be expressed in Colored Petri Nets (CPN), and CPN can express various problem domains other than enterprise back-office applications.
Xiao ZHOU Yasuaki KANARI Takao NISHIZEKI
Let l be a positive integer, and let G be a graph with nonnegative integer weights on edges. Then a generalized vertex-coloring, called an l-coloring of G, is an assignment of colors to the vertices of G in such a way that any two vertices u and v get different colors if the distance between u and v in G is at most l. In this paper we give an algorithm to find an l-coloring of a given graph G with the minimum number of colors. The algorithm takes polynomial time if G is a partial k-tree and both l and k are bounded integers.
This paper surveys how geometric information can be effectively used for efficient algorithms with focus on clustering problems. Given a complete weighted graph G of n vertices, is there a partition of the vertex set into k disjoint subsets so that the maximum weight of an innercluster edge (whose two endpoints both belong to the same subset) is minimized? This problem is known to be NP-complete even for k = 3. The case of k=2, that is, bipartition problem is solvable in polynomial time. On the other hand, in geometric setting where vertices are points in the plane and weights of edges equal the distances between corresponding points, the same problem is solvable in polynomial time even for k 3 as far as k is a fixed constant. For the case k=2, effective use of geometric property of an optimal solution leads to considerable improvement on the computational complexity. Other related topics are also discussed.
Graph coloring is a fundamental problem, which often appears in various scheduling problems like the file transfer problem on computer networks. In this paper, we survey recent advances and results on the edge-coloring, the f-coloring, the [g,f]-coloring, and the total coloring problem for various classes of graphs such as bipartite graphs, series-parallel graphs, planar graphs, and graphs having fixed degeneracy, tree-width, genus, arboricity, unicyclic index or thickness. In particular, we review various upper bounds on the minimum numbers of colors required to color these classes of graphs, and present efficient sequential and parallel algorithms to find colorings of graphs with these numbers of colors.
Takayuki NAKACHI Tatsuya FUJII Junji SUZUKI
This paper describes a unified coding algorithm for lossless and near-lossless color image compression that exploits the correlations between RGB signals. A reversible color transform that removes the correlations between RGB signals while avoiding any finite word length limitation is proposed for the lossless case. The resulting algorithm gives higher performance than the lossless JPEG without the color transform. Next, the lossless algorithm is extended to a unified coding algorithm of lossless and near-lossless compression schemes that can control the level of the reconstruction error on the RGB plane from 0 to p, where p is a certain small non-negative integer. The effectiveness of this algorithm was demonstrated experimentally.
Yoshiyuki SHINKAWA Masao J. MATSUMOTO
Adaptability evaluation of software systems is one of the key concerns in both software engineering and requirements engineering. In this paper, we present a formal and systematic approach to evaluate adaptability of software systems to requirements in enterprise business applications. Our approach consists of three major parts, that is, the common modeling method for both business realms and software realms, functional adaptability evaluation between the models with Σ algebra and behavioral adaptability evaluation with process algebra. By our approach, one can rigorously and uniquely determine whether a software system is adaptable to the requirements, either totally or partially. A sample application from an order processing is illustrated to show how this approach is effective in solving the adaptability evolution problem.
Sin Jun KANG Seok Ho JANG Hee Soo HWANG Kwang Bang WOO
In this paper, an effective method of system modeling and dynamic scheduling to improve operation and control for the Back-End process of semiconductor manufacturing is developed by using Colored Timed Petri-Nets (CTPNs). The simulator of a CTPNs model was utilized to generate a new heuristic scheduling method with genetic algorithm(GA) which enables us to obtain the optimal values of the weighted delay time and standard deviation of lead time.
Ali Md. HAIDER Toyohisa KANEKO
This paper proposes an automatic method for reconstructing a realistic 3D facial image from CT (computer tomography) and three color photographs: front, left and right views, which can be linked easily with the underlying bone and soft tissue models. This work is the first part of our final goal, "the prediction of patient's facial appearance after cancer surgery" such as removal of a part of bone or soft tissues. The 3D facial surface derived from CT by the marching cubes algorithm is obviously colorless. Our task is to add the color texture of the same patient actually taken with a digital camera to the colorless 3D surface. To do this it needs an accurate registration between the 3D facial image and the color photograph. Our approach is to set up a virtual camera around the 3D facial surface to register the virtual camera images with the corresponding color photographs by automatically adjusting seven parameters of the virtual camera. The camera parameters consists of three rotations, three translations and one scale factor. The registration algorithm has been developed based upon Besl and McKay's iterative closest point (ICP) algorithm.
Yegui XIAO Yoshihiro TAKESHITA Katsunori SHIDA
In this paper, a new gradient-based adaptive algorithm for the estimation of discrete Fourier coefficients (DFC) of a noisy sinusoidal signal is proposed based on a summed least mean squared error criterion. This algorithm requires exactly the same number of multiplications as the conventional LMS algorithm, and presents much improved performance in both white and colored noise environments at the expense of some additional memories and additions only. We first analyze the performance of the conventional LMS algorithm in colored additive noise, and point out when its performance deteriorates. Then, a summed least mean squared error criterion is proposed, which leads to the above-mentioned new gradient-based adaptive algorithm. The performance of the proposed algorithm is also analyzed for a single frequency case. Simulation results are provided to support the analytical findings and the superiority of the new algorithm.
Mei YU Gang Yi JIANG Dong Mun HA Tae Young CHOI Yong Deak KIM
In this paper, quasi-Gaussian filter, quasi-median filter and locally adaptive filters are introduced. A new adaptive vector filter based on noise estimate is proposed to suppress Gaussian and/or impulse noise. To estimate the type and degree of noise corruption, a noise detector and an edge detector are introduced, and two key parameters are obtained to characterize noise in color image. After globally estimating the type and degree of noise corruption, different locally adaptive filters are properly chosen for image enhancement. All noisy images, used to test filters in experiments, are generated by PaintShopPro and Photoshop software. Experimental results show that the new adaptive filter performs better in suppressing noise and preserving details than the filter in Photoshop software and other filters.
Noboru YABUKI Yoshitaka MATSUDA Hiroyuki KIMURA Yutaka FUKUI Shigehiko MIKI
In this paper, we propose a method to detect a road sign from a road scene image in the daytime. In order to utilize color feature of sign efficiently, color distribution of sign is examined, and then color similarity map is constructed. Additionally, color similarity shown on the map is incorporated into image energy of an active net model. A road sign is extracted as if it is wrapped up in an active net. Some experimental results obtained by applying an active net to images are presented.