Visual coding by optimal graph-coloring |
| |
Authors: | Xiaolin Wu Yonggang Fang |
| |
Affiliation: | (1) Department of Computer Science, University of Western Ontario, N6A 5B7 London, Ontario, Canada;(2) Department of Electronic Engineering, Tsinghua University, Beijing, People's Republic of China |
| |
Abstract: | A formal study of visual codings in user interface design is presented. Visual codings for maximum distinction of different objects in displayed images are formulated as a discrete optimization problem of maximum-distance graph-coloring. The formulation is a generalization of the classical coloring problem in graph theory. Having pointed out that maximum-distance graph-coloring is NP-complete, we develop new, fast approximation algorithms for optimal visual codings. The proposed algorthms run inO (M N) time, whereM is the number of visual codes used andN is the number of objects to be encoded. Besides being efficient, the algorithms are simple and easy to implement. Our experiments showed that geographic maps automatically colored by the new algorithms were preferred to those colored by the previous graph-theoretical approach and they are competitive, if not better, in terms of the visual distinction of different regions than those drawn by hand.Supported by grans from Natural Science and Enginneering Research Council of Canada |
| |
Keywords: | Visual codings User interface Graph-coloring Optimization Connected components Color distance Graph theory Algorithms |
本文献已被 SpringerLink 等数据库收录! |
|