Browse Prior Art Database

Quartic Residue Custom Palette Color Selection

IP.com Disclosure Number: IPCOM000103661D
Original Publication Date: 1993-Jan-01
Included in the Prior Art Database: 2005-Mar-18
Document File: 2 page(s) / 113K

Publishing Venue

IBM

Related People

Burns, NA: AUTHOR [+3]

Abstract

This article presents an improved algorithm for selection of a palette of colors customized for a selected image. As the colors are selected for the custom palette, they are placed with regard to the residue left by reducing a representation matrix according to the fourth power of distance of colors already selected.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Quartic Residue Custom Palette Color Selection

       This article presents an improved algorithm for selection
of a palette of colors customized for a selected image.  As the
colors are selected for the custom palette, they are placed with
regard to the residue left by reducing a representation matrix
according to the fourth power of distance of colors already selected.

      This article is based on a color selection algorithm.  The
algorithm uses two three-dimensional arrays with red, green, and blue
dimensions.  The first population array holds a three-dimensional bar
graph of the number of occurrences in the image of each color.  The
second representation array holds a measure of how well represented
each color is by the colors already chosen for the palette.  The next
color chosen for the expanding palette is the one for which the ratio
of population to representation is the highest.  After this choice,
the representation array is modified and the process repeated until
the palette is filled.

      After selection of a color, the algorithm multiplies each
element in the representation array by the square of the cartesian
distance between that element's associated color and the newly
selected color.  The algorithm of this disclosure differs on this
step by substituting the following procedure:
1- Calculate distance emphasizing luminance over chrominance.
2- Use the fourth power of distance.
3- Replace each representation array element with the smaller of the
original value and this fourth power of distance to that element.

      Point 1 above is a simple refinement and will not be discussed
further.  By marking the minimum distance as in point 3 above, each
element in the representation array will be affected by the CLOSEST
color ONLY.  This is justified because when the image is finally
color mapped, the palette color chosen for each pel will in fact be
the ONE that is closest in color space, and the perceived noise will
be the difference between that closest palette color and the true
color.  It will make no difference how far the next best color was.

      The reason for the fourth power in point 2 is the subject of
the rest of this article.  If image colors were clustered along
one-dimensional lines, then the ideal function would be the third
power.  If image colors were clumped in uniformly filled
three-dimensional volumes, then the ideal function would be the fifth
power.  If image colors were grouped on planes in the color space,
the ideal function would be the fourth power.  The real world color
formations in color space are a blend of all these cases, with a
predominance of the planar di...