XEP-0392: Consistent Color Generation

Abstract:This specification provides a set of algorithms to consistently generate colors given a string. The string can be a nickname, a JID or any other piece of information. All entities adhering to this specification generate the same color for the same string, which provides a consistent user experience across platforms.
Author:Jonas Wielicki
Copyright:© 1999 – 2017 XMPP Standards Foundation. SEE LEGAL NOTICES.
Status:Experimental
Type:Standards Track
Version:0.2
Last Updated:2017-10-04

WARNING: This Standards-Track document is Experimental. Publication as an XMPP Extension Protocol does not imply approval of this proposal by the XMPP Standards Foundation. Implementation of the protocol described herein is encouraged in exploratory implementations, but production systems are advised to carefully consider whether it is appropriate to deploy implementations of this protocol before it advances to a status of Draft.


Table of Contents


1. Introduction
2. Requirements
3. Use Cases
    3.1. Generating a color
    3.2. Adding colors to participants of a conversation
    3.3. Auto-Generating Avatars
4. Business Rules
5. Algorithms
    5.1. Angle generation
    5.2. Corrections for Color Vision Deficiencies
       5.2.1. Red/Green-blindness
       5.2.2. Blue-blindness
    5.3. CbCr generation
    5.4. CbCr to RGB
    5.5. Adapting the Color for specific Background Colors
    5.6. RGB to YCbCr
    5.7. Conversion of an RGB color palette to a CbCr color palette
    5.8. Mapping of a CbCr color to closest palette color
6. Implementation Notes
    6.1. Gamma Correction
7. Accessibility Considerations
8. Security Considerations
9. Design Considerations
    9.1. Other variants of the YCbCr color space
    9.2. Hue-Saturation-Value/Lightness color space
    9.3. Palette-based and context-aware coloring
    9.4. Choice of mixing function in angle generation
10. IANA Considerations
11. XMPP Registrar Considerations
12. Acknowledgements
13. Test Vectors and Constants
    13.1. Constants for YCbCr (BT.601)
    13.2. Test Vectors
       13.2.1. No Color Vision Deficiency correction
       13.2.2. With Red/Green-blindess correction
       13.2.3. With Blue-blindess correction
    13.3. Test Vectors for mapping to 216 color palette
       13.3.1. No Color Vision Deficiency correction
       13.3.2. With Red/Green-blindess correction
       13.3.3. With Blue-blindess correction

Appendices
    A: Document Information
    B: Author Information
    C: Legal Notices
    D: Relation to XMPP
    E: Discussion Venue
    F: Requirements Conformance
    G: Notes
    H: Revision History


1. Introduction

Colors provide a valuable visual cue to recognize text. Recognition of colors works much faster than recognition of text. Together with the length and overall shape of a piece of text (such as a nickname), a color provides a decent amount of entropy to distinguish a reasonable amount of entities.

Clients have been using randomly or deterministically chosen colors for users in multi-user situations for a long time already. However, since there has been no standard for how this is implemented, the experience differs across platforms. The goal of this XEP is to provide a uniform, platform-independent, stateless and easy-to-implement way to map arbitrary bytestrings to colors, as well as give recommendations how this is applied to color names of participants in conversations, roster entries and other pieces of text.

To allow cross-client use, it is important that the color scheme can be adapted to different environments. This specification provides means to adapt colors to different background colors as well as Color Vision Deficiencies.

In no way is the system presented in this specification a replacement for names. It only serves as an additional visual aid.

2. Requirements

The color generation mechanism should provide the following features:

3. Use Cases

3.1 Generating a color

To generate a color from a string of text, the follownig algorithms are applied in order:

  1. Generate an angle in the CbCr plane from the text.
  2. If enabled, apply configured corrections for Color Vision Deficiencies.
  3. Convert the angle to a CbCr pair.
  4. If the output device only supports a small palette of colors, map the CbCr value to the closest palette color.
  5. If the output device supports RGB output, convert the CbCr pair to an RGB triple.

3.2 Adding colors to participants of a conversation

Implementations may colorize the participants of a conversation with an individual color to make them easier to distinguish.

In such cases, the color SHOULD be generated as described in the Generating a color section. The input used SHOULD be, in descending order of preference, (a) the nickname from the conversation, (b) the bare JID.

3.3 Auto-Generating Avatars

Implementations may want to show a picture in connection with a contact even if the contact does not have an avatar defined (e.g. via User Avatar (XEP-0084) [1]).

In such cases, auto-generating an avatar SHOULD happen as follows:

  1. Obtain a name for the contact, in descending order of preference, (a) by using the actual bare JID of the contact (not the bare JID of the conference in case of a XEP-0045 MUC), (b) by using the nickname from the conversation.
  2. Generate a color as described in the Generating a color section.
  3. Fill an implementation-defined background shape with that color.
  4. Render the first character of the name in white or black centered on the shape.

4. Business Rules

5. Algorithms

5.1 Angle generation

Input: An identifier, encoded as octets of UTF-8 (RFC 3269 [2]).

Output: Angle in the CbCr plane.

Note: The goal of this algorithm is to convert arbitrary text into a scalar value which can then be used to calculate a color. As it happens, the CbCr plane of the YCbCr space determines the color (while Y merely defines the lightness); thus, an angle in the CbCr plane serves as a good scalar value to select a color.

  1. Run the input through CRC32 as defined by zlib (TODO: add citation).
  2. Take the lower 16 bits and XOR them with the upper 16 bits.
  3. Divide the value by 65535 (use float division) and multiply it by 2π (two Pi).

5.2 Corrections for Color Vision Deficiencies

Input: Angle in the CbCr plane.

Output: Angle in the CbCr plane.

Note: This algorithm will re-map the angle to map it away from ranges which can not be distinguished by people with the respective Color Vision Deficiencies.

5.2.1 Red/Green-blindness

Divide the angle by two.

5.2.2 Blue-blindness

Divide the angle by two and add π/2 (half Pi).

5.3 CbCr generation

Input: Angle in the CbCr plane, from the previous algorithm.

Output: Values for Cb and Cr in the YCbCr BT.601 [3] color space in the range from -0.5 to 0.5.

Form a vector from the angle and project it to edges of a quad in 2D space with edge length 1 around (0, 0). The resulting coordinates are Cb and Cr:

float cr = sin(angle);
float cb = cos(angle);
float factor;
if (abs(cr) > abs(cb)) {
  factor = 0.5 / abs(cr);
} else {
  factor = 0.5 / abs(cb);
}
cb = cb * factor;
cr = cr * factor;

5.4 CbCr to RGB

Input: Values for Cb and Cr in the YCbCr BT.601 [3] color space in the range from -0.5 to 0.5; Value for Y.

Output: Values for Red (R), Green (G) and Blue (B) in the RGB color space in the range from 0 to 1.

Note: The recommended value for Y is 0.732. See Gamma Correction for a discussion on the choice of Y.

  1. Calculate r, g and b according to BT.601:

    float r = 2*(1 - KR)*cr + y;
    float b = 2*(1 - KB)*cb + y;
    float g = (y - KR*r - KB*b)/KG;
    
  2. Clip the values of r, g and b to the range from 0 to 1.

See Constants for YCbCr (BT.601) for the values of KR, KG and KB.

5.5 Adapting the Color for specific Background Colors

Input: RGB values for the color to adapt (Ri, Gi, Bi) and for the background color to adapt to (Rb, Gb, Bb), in the range from 0 to 1 each.

Output: Values for Red (Rc), Green (Gc) and Blue (Bc) in the RGB color space in the range from 0 to 1.

  1. Invert the background color by subtracting the individual channels from 1 each:

    rb_inv = 1-rb;
    gb_inv = 1-gb;
    bb_inv = 1-bb;
  2. Mix the inverted background with the color to adapt, using a mixing factor of 0.2:

    rc = 0.2*rb_inv + 0.8*ri;
    gc = 0.2*gb_inv + 0.8*gi;
    bc = 0.2*bb_inv + 0.8*bi;

5.6 RGB to YCbCr

Input: Values for Red (R), Green (G) and Blue (B) in the RGB color space in the range from 0 to 1.

Output: Values for Cb and Cr in the YCbCr BT.601 [3] color space in the range from -0.5 to 0.5; Value for Y.

Calculate Y, Cb and Cr according to BT.601:

y = KR*r + (1 - KR - KB)*g + KB*b;
cb = (b - y) / (1 - KB) / 2
cr = (r - y) / (1 - KR) / 2

See Constants for YCbCr (BT.601) for the values of KR, KG and KB.

5.7 Conversion of an RGB color palette to a CbCr color palette

Input: A set of RGB colors (each component from 0 to 1).

Output: A mapping from CbCr pairs (each component from -0.5 to 0.5) to RGB colors.

Note: when the algorithm finishes, the mapping maps CbCr values (rounded to two decimal places) to the R, G, B triples which come closest to the desired color and lightness.

  1. Create an empty mapping M which maps from pairs of CbCr values to quadruples of Y, R, G and B.
  2. For each color R, G, B from the input palette:
    1. Calculate Y, Cb and Cr from R, G, B as described in RGB to YCbCr.
    2. Round Cb and Cr to two decimal places as Cb' and Cr'.
    3. If the (Cb', Cr') pair is not in the mapping M yet, or if the Y value of the existing entry is farther away from 0.732 than the new Y value, put the Y, R, G, and B values as value for the (Cb', Cr') pair into the mapping.
  3. Strip the Y values from the values of mapping M.
  4. Return M as the result of the algorithm.

5.8 Mapping of a CbCr color to closest palette color

Input: A set of colors (the palette) as tuples of Cbp and Crp and a color to map to the closest palette color as Cb and Cr value.

Output: A palette color as Cbr and Crr values.

  1. For each color as pair Cbp, Crp in the palette, calculate the distance metric:

    D = sqrt((Cbp-Cb)*(Cbp-Cb) + (Crp-Cr)*(Crp-Cr))
    .
  2. Pick the palette color Cbp, Crp with the smallest distance metric D as result color Cbr, Crr.

Note: the distance metric is simply the euclidian distance in the CbCr plane.

6. Implementation Notes

6.1 Gamma Correction

An implementation may choose a different value for Y depending on whether the sink for the R, G and B values expects Gamma Encoded or Gamma Decoded values. The recommended default of 0.732 is 0.5 to the power of 0.45, that is, a Gamma Encoded 0.5.

Modifications to Y SHOULD NOT be used to correct for bright/dark backgrounds. Implementations SHOULD instead use the algorithm described in Adapting the Color for specific Background Colors for that.

7. Accessibility Considerations

As outlined above, implementations SHOULD offer the Red/Green-Blindness and Blue-Blindness corrections as defined in the Corrections for Color Vision Deficiencies section. Users SHOULD be allowed to choose between:

The last option is important for users with monochromatic view.

Some sources on the internet indicate that people with Color Vision Deficiencies may profit from having larger areas of color to be able to recognize them. This should be taken into consideration when selecting font weights and line widths for colored parts.

8. Security Considerations

This specification extracts a bit more information from an entity and shows it alongside the existing information to the user. As the algorithm is likely to produce different colors for look-alikes (see Best Practices to Prevent JID Mimicking (XEP-0165) [4] for examples) in JIDs, it may add additional protection against attacks based on those.

Due to the limited set of distinguishable colors and only extracting 16 bits of the hash function output, possible Color Vision Deficiencies and/or use of palettes, entities MUST NOT rely on colors being unique in any context.

9. Design Considerations

This section provides an overview of design considerations made while writing this specification. It shows alternatives which have been considered, and eventually rejected.

9.1 Other variants of the YCbCr color space

The other common YCbCr variants, BT.709 and BT.2020, do not achieve a brightness across the color space as uniform as BT.601 [3] does. Adapting the Y value for uniform luminosity across the range for CbCr would have complicated the algorithm with little or no gain.

9.2 Hue-Saturation-Value/Lightness color space

The HSV and HSL color spaces fail to provide uniform luminosity with fixed value/lightness and saturation parameters. Adapting those parameters for uniform luminosity across the hue range would have complicated the algorithm with litte to no gain.

9.3 Palette-based and context-aware coloring

Given a fixed-size and finite palette of colors, it would be possible to ensure that, until the number of entities to color exceeds the number of colors, no color collisions happen.

There are issues with this approach when the set of entities is dynamic. In such cases, it is possible that an entity changes its associated color (for example by re-joining a colored group chat), which defeats the original purpose.

In addition, more state needs to be taken into account, increasing the complexity of choosing a color.

9.4 Choice of mixing function in angle generation

This specification needs to collapse an arbitrarily long string into just a few bits (the angle in the CbCr plane). To do so, SHA-1 (RFC 3174 [5]) is used.

CRC32 and Adler32 have been considered as faster alternatives. Downsides of these functions:

SHA-1 is widely available. From a security point of view, the exact choice of hash function does not matter here, since it is truncated to 16 bits. At this length, any cryptographic hash function is weak.

10. IANA Considerations

This document requires no interaction with the Internet Assigned Numbers Authority (IANA) [6].

11. XMPP Registrar Considerations

This document requires no interaction with the XMPP Registrar [7].

12. Acknowledgements

Thanks to Daniel Gultsch, Georg Lukas, and Tobias Markmann.

13. Test Vectors and Constants

13.1 Constants for YCbCr (BT.601)

Throughout the document, the constants KR, KG and KB are used. They are defined in BT.601 [3] as:

KR = 0.299
KG = 0.587
KB = 0.114

13.2 Test Vectors

This section holds test vectors for the different configurations. The test vectors are provided as Comma Separated Values. Strings are enclosed by single quotes ('). The first line contains a header. Each row contains, in that order, the original text, the text encoded as UTF-8 as hexadecimal octets, the angle in radians, and the Cb, Cr, Red, Green, and Blue values.

13.2.1 No Color Vision Deficiency correction

text,hextext,angle,cb,cr,r,g,b
'Romeo','526f6d656f',5.711769,0.500000,-0.321484,0.281,0.790,1.000
'juliet@capulet.lit','6a756c69657440636170756c65742e6c6974',3.654957,-0.500000,-0.281892,0.337,1.000,0.000
'😺','f09f98ba',5.780607,0.500000,-0.274827,0.347,0.756,1.000

13.2.2 With Red/Green-blindess correction

text,hextext,angle,cb,cr,r,g,b
'Romeo','526f6d656f',2.855884,-0.500000,0.146872,0.938,0.799,0.000
'juliet@capulet.lit','6a756c69657440636170756c65742e6c6974',1.827478,-0.131236,0.500000,1.000,0.420,0.499
'😺','f09f98ba',2.890304,-0.500000,0.128358,0.912,0.812,0.000

13.2.3 With Blue-blindess correction

text,hextext,angle,cb,cr,r,g,b
'Romeo','526f6d656f',4.426681,-0.146872,-0.500000,0.031,1.000,0.472
'juliet@capulet.lit','6a756c69657440636170756c65742e6c6974',3.398275,-0.500000,-0.131236,0.548,0.998,0.000
'😺','f09f98ba',4.461100,-0.128358,-0.500000,0.031,1.000,0.505

13.3 Test Vectors for mapping to 216 color palette

The used palette can be generated by sampling the RGB cube evenly with six samples on each axis (resulting in 216 colors). The resulting palette is commonly known as the palette of so-called "Web Safe" colors.

The format of the test vectors is the same as in the full range case above.

13.3.1 No Color Vision Deficiency correction

text,hextext,angle,cb,cr,r,g,b
'Romeo','526f6d656f',5.711769,0.500000,-0.321484,0.000,0.400,1.000
'juliet@capulet.lit','6a756c69657440636170756c65742e6c6974',3.654957,-0.500000,-0.281892,0.400,1.000,0.000
'😺','f09f98ba',5.780607,0.500000,-0.274827,0.000,0.200,1.000

13.3.2 With Red/Green-blindess correction

text,hextext,angle,cb,cr,r,g,b
'Romeo','526f6d656f',2.855884,-0.500000,0.146872,1.000,1.000,0.000
'juliet@capulet.lit','6a756c69657440636170756c65742e6c6974',1.827478,-0.131236,0.500000,1.000,0.000,0.000
'😺','f09f98ba',2.890304,-0.500000,0.128358,1.000,1.000,0.000

13.3.3 With Blue-blindess correction

text,hextext,angle,cb,cr,r,g,b
'Romeo','526f6d656f',4.426681,-0.146872,-0.500000,0.000,1.000,0.400
'juliet@capulet.lit','6a756c69657440636170756c65742e6c6974',3.398275,-0.500000,-0.131236,0.600,1.000,0.000
'😺','f09f98ba',4.461100,-0.128358,-0.500000,0.000,1.000,0.400

Appendices


Appendix A: Document Information

Series: XEP
Number: 0392
Publisher: XMPP Standards Foundation
Status: Experimental
Type: Standards Track
Version: 0.2
Last Updated: 2017-10-04
Approving Body: XMPP Council
Dependencies: None
Supersedes: None
Superseded By: None
Short Name: colors
Source Control: HTML
This document in other formats: XML  PDF


Appendix B: Author Information

Jonas Wielicki

Email: jonas@wielicki.name
JabberID: jonas@wielicki.name


Appendix C: Legal Notices

Copyright

This XMPP Extension Protocol is copyright © 1999 – 2017 by the XMPP Standards Foundation (XSF).

Permissions

Permission is hereby granted, free of charge, to any person obtaining a copy of this specification (the "Specification"), to make use of the Specification without restriction, including without limitation the rights to implement the Specification in a software program, deploy the Specification in a network service, and copy, modify, merge, publish, translate, distribute, sublicense, or sell copies of the Specification, and to permit persons to whom the Specification is furnished to do so, subject to the condition that the foregoing copyright notice and this permission notice shall be included in all copies or substantial portions of the Specification. Unless separate permission is granted, modified works that are redistributed shall not contain misleading information regarding the authors, title, number, or publisher of the Specification, and shall not claim endorsement of the modified works by the authors, any organization or project to which the authors belong, or the XMPP Standards Foundation.

Disclaimer of Warranty

## NOTE WELL: This Specification is provided on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, express or implied, including, without limitation, any warranties or conditions of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A PARTICULAR PURPOSE. ##

Limitation of Liability

In no event and under no legal theory, whether in tort (including negligence), contract, or otherwise, unless required by applicable law (such as deliberate and grossly negligent acts) or agreed to in writing, shall the XMPP Standards Foundation or any author of this Specification be liable for damages, including any direct, indirect, special, incidental, or consequential damages of any character arising from, out of, or in connection with the Specification or the implementation, deployment, or other use of the Specification (including but not limited to damages for loss of goodwill, work stoppage, computer failure or malfunction, or any and all other commercial damages or losses), even if the XMPP Standards Foundation or such author has been advised of the possibility of such damages.

IPR Conformance

This XMPP Extension Protocol has been contributed in full conformance with the XSF's Intellectual Property Rights Policy (a copy of which can be found at <https://xmpp.org/about/xsf/ipr-policy> or obtained by writing to XMPP Standards Foundation, P.O. Box 787, Parker, CO 80134 USA).

Appendix D: Relation to XMPP

The Extensible Messaging and Presence Protocol (XMPP) is defined in the XMPP Core (RFC 6120) and XMPP IM (RFC 6121) specifications contributed by the XMPP Standards Foundation to the Internet Standards Process, which is managed by the Internet Engineering Task Force in accordance with RFC 2026. Any protocol defined in this document has been developed outside the Internet Standards Process and is to be understood as an extension to XMPP rather than as an evolution, development, or modification of XMPP itself.


Appendix E: Discussion Venue

The primary venue for discussion of XMPP Extension Protocols is the <standards@xmpp.org> discussion list.

Discussion on other xmpp.org discussion lists might also be appropriate; see <http://xmpp.org/about/discuss.shtml> for a complete list.

Errata can be sent to <editor@xmpp.org>.


Appendix F: Requirements Conformance

The following requirements keywords as used in this document are to be interpreted as described in RFC 2119: "MUST", "SHALL", "REQUIRED"; "MUST NOT", "SHALL NOT"; "SHOULD", "RECOMMENDED"; "SHOULD NOT", "NOT RECOMMENDED"; "MAY", "OPTIONAL".


Appendix G: Notes

1. XEP-0084: User Avatar <https://xmpp.org/extensions/xep-0084.html>.

2. RFC 3269: UTF-8, a transformation format of ISO 10646 <http://tools.ietf.org/html/rfc3269>.

3. BT.601: Studio encoding parameters of digital television for standard 4:3 and wide screen 16:9 aspect ratios <https://www.itu.int/rec/R-REC-BT.601-7-201103-I/en>

4. XEP-0165: Best Practices to Prevent JID Mimicking <https://xmpp.org/extensions/xep-0165.html>.

5. RFC 3174: US Secure Hash Algorithm 1 (SHA1) <http://tools.ietf.org/html/rfc3174>.

6. The Internet Assigned Numbers Authority (IANA) is the central coordinator for the assignment of unique parameter values for Internet protocols, such as port numbers and URI schemes. For further information, see <http://www.iana.org/>.

7. The XMPP Registrar maintains a list of reserved protocol namespaces as well as registries of parameters used in the context of XMPP extension protocols approved by the XMPP Standards Foundation. For further information, see <https://xmpp.org/registrar/>.


Appendix H: Revision History

Note: Older versions of this specification might be available at http://xmpp.org/extensions/attic/

Version 0.2 (2017-10-04)

Move to SHA-1 as mixing function; Properly reference BT.601 and include constants in text; Prefer bare JID over roster name when selecting the hash function input; Editing.

(jwi)

Version 0.1 (2017-09-27)

Accepted as Experimental by Council.

(XEP Editor: jwi)

Version 0.0.1 (2017-09-14)

First draft.

(jwi)

END