Information Technology Reference
In-Depth Information
C
could be a discrete, or continuous, color
space. This is intentional since we are interested in both scenarios. All we assume is
that
Note that (1) is stated rather generally:
C
sits in a Euclidean space of dimension
d
.
Once we colored the collision graph, we can use the same coloring scheme for the
edges of the original graph. The complete pipeline of our proposed approach is illus-
trated in Fig. 2. Notice that the collision graph in Fig. 2(b) is disconnected. We apply
ouralgorithm on each component of the collision graph.
3.3
A Color Optimization Algorithm
Dillencourt
e
t al. [7] proposed a force-directed algorithm in a Euclidean color space.
They wanted
all
pairs of nodes to have distinctively different colors. Consequently their
algorithm used a force model where repulsive forces exist among all pairs of nodes.
Because in our case edges can have the same color as long as they do not collide,
there is no need to push all pairs of nodes of the collision graph apart in the color space.
Therefore we can not use the algorithm of Dillencourt
e
t al. [7] as is. Althoughitis
possible to adapt their algorithm, we opt to propose an alternative algorithm. One reason
is that we like to be able to use not only continuous color spaces, but also discrete color
palettes.Another reason is due to the fact that even when deciding the optimal color for
one node of the collision graph with regard to all its neighbors, this seemingly simple
problem can have many local maxima.
We give an example to illustrate this point. For simplicity of illustration, within this
example, we assume for that our color space is 2D, and that the color distance is the
Euclidean distance. Suppose we want to find the best color embedding for a node
u
in
the collision graph with six neighbors, and the six neighbors are currently embedded
as shown in Fig. 4 (left). We want to place
u
as far away from the set of six points as
possible. Fig. 4 (left) shows a color contour of the distance from the set of six points
(the distance of a point to a set of point is defined as the minimum distance between this
point and all the points in the set, assumingunit weighting factors). Color scale is given
in the figure, with blueforlowvalues and off-white for large. From the contourplot
it is clear that there are seven or more local maxima. In 3D there could be even more
local maxima. A force-directed algorithm such as [7], even with the random jumps and
swaps, is likely to settle in one of the local maxima.
Instead we hope to find the global maximum. A naive way to find the global maxi-
mum position in the color space with regard to a set of points is to search exhaustively by
imposing afinegrid over the color space, and calculating the distance from each mesh
point to the set. However, given that the color space are typically of three dimensions,
even at a resolution of 100 subdivisions along each dimension, we need 10
6
distance
calculations. This is computationally too expensive, bear in mind that this computation
needs to be performed for each and every node of the collision graph repeatedly until
the overall embedding in the color space converges.
We propose a more efficient algorithm based on the octree data structure (quadtree
for 2D) that does not require evaluations of the distance over all mesh points. Pseudo
code for the algorithm is given in [13]. We give a high level description here. Using
Fig. 4 (left) as an example, we want to find a point in the color space that is of maximal
distance to a target set of points. Define the objective function valueofasquare to be
