color_palette_generation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Color palette generation\n",
    "\n",
    "This notebook describes the generation of a color palette containing an arbitrary number of colors that are maximally distinct from each other. The process allows color vision deficiency (CVD) to be taken into consideration so that the colors are distinguishable by people with different types of color blindness."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from enum import Enum\n",
    "\n",
    "import kmedoids\n",
    "import numpy as np\n",
    "from coloraide import Color\n",
    "from IPython.display import Markdown, display\n",
    "from scipy.optimize import linear_sum_assignment\n",
    "from tqdm import tqdm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class CVD(Enum):\n",
    "    NORMAL = 0\n",
    "    PROTAN = 1\n",
    "    DEUTAN = 2\n",
    "    TRITAN = 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "N_RANDOM_COLORS = 1_500 # Number of random colors to generate\n",
    "N_COLORS = 6 # Number of colors in the palette\n",
    "L_RANGE = (0.3, 0.9) # Luminance range (0 to 1)\n",
    "C_RANGE = (0, 0.9) # Chroma range (0 to 1)\n",
    "H_RANGE = (0, 360) # Hue range (0 to 360)\n",
    "CVD = CVD.DEUTAN"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A set of `N_RANDOM_COLORS` random colors are generated in the sRGB space. Colors are then filtered to keep the ones that fall within the defined luminance, chroma, and hue ranges (`L_RANGE`, `C_RANGE`, and `H_RANGE`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "random_colors = []\n",
    "for s in range(N_RANDOM_COLORS):\n",
    "    np.random.seed(s)\n",
    "    r = np.random.uniform(0, 1)\n",
    "    np.random.seed(s + N_RANDOM_COLORS)\n",
    "    g = np.random.uniform(0, 1)\n",
    "    np.random.seed(s + N_RANDOM_COLORS + 2)\n",
    "    b = np.random.uniform(0, 1)\n",
    "    c = Color(\"srgb\", [r, g, b]).convert(\"oklch\")\n",
    "    if (\n",
    "        c.coords()[0] >= L_RANGE[0]\n",
    "        and c.coords()[0] <= L_RANGE[1]\n",
    "        and c.coords()[1] >= C_RANGE[0]\n",
    "        and c.coords()[1] <= C_RANGE[1]\n",
    "        and c.coords()[2] >= H_RANGE[0]\n",
    "        and c.coords()[2] <= H_RANGE[1]\n",
    "    ):\n",
    "        random_colors.append(c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A distance matrix is gennerated by computing the Euclidean distance between each pair of colors in the Oklab color space. If a CVD was chosen, a filter is applied to simulate CVD prior to distance computation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 1403/1403 [05:15<00:00,  4.45it/s]\n"
     ]
    }
   ],
   "source": [
    "distance_matrix = np.zeros((len(random_colors), len(random_colors)))\n",
    "for i in tqdm(range(len(random_colors))):\n",
    "    for j in range(len(random_colors)):\n",
    "        if CVD == CVD.DEUTAN:\n",
    "            c_i = random_colors[i].filter(\"deutan\").clip()\n",
    "            c_j = random_colors[j].filter(\"deutan\").clip()\n",
    "        elif CVD == CVD.PROTAN:\n",
    "            c_i = random_colors[i].filter(\"protan\").clip()\n",
    "            c_j = random_colors[j].filter(\"protan\").clip()\n",
    "        elif CVD == CVD.TRITAN:\n",
    "            c_i = random_colors[i].filter(\"tritan\").clip()\n",
    "            c_j = random_colors[j].filter(\"tritan\").clip()\n",
    "        else:\n",
    "            c_i = random_colors[i]\n",
    "            c_j = random_colors[j]\n",
    "        distance_matrix[i, j] = c_i.delta_e(c_j, method=\"ok\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We perform clustering of the random colors using the k-medoids algorithm to find `N_COLORS` color clusters in the Oklab color space. Next, the representative colors of the clusters (medoids) are sorted using the Traveling Salesman Problem (TSP) to maximize the average distance between adjacent colors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Step 1: Cluster colors to find representative colors (medoids)\n",
    "medoid_indices = kmedoids.fasterpam(distance_matrix, N_COLORS, random_state=0).medoids\n",
    "medoid_colors = [random_colors[i] for i in medoid_indices]\n",
    "\n",
    "# Step 2: Get the pairwise distances between representative colors\n",
    "medoid_distances = distance_matrix[np.ix_(medoid_indices, medoid_indices)]\n",
    "\n",
    "# Step 3: Solve TSP to maximize the total distance\n",
    "row_ind, col_ind = linear_sum_assignment(medoid_distances, maximize=True)\n",
    "\n",
    "# Step 4: Sort colors according to the TSP solution\n",
    "sorted_medoid_colors = [medoid_colors[i] for i in col_ind]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Display the generated palette."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "<span style='font-family: monospace'>#16d7bc <span style='color: oklch(0.78919 0.14153 179.16)'>██████</span></span><br><span style='font-family: monospace'>#d83e44 <span style='color: oklch(0.5926 0.19102 22.969)'>██████</span></span><br><span style='font-family: monospace'>#225b54 <span style='color: oklch(0.43025 0.05996 184.59)'>██████</span></span><br><span style='font-family: monospace'>#b75fd3 <span style='color: oklch(0.63423 0.18663 317.58)'>██████</span></span><br><span style='font-family: monospace'>#29e750 <span style='color: oklch(0.81003 0.24052 145.43)'>██████</span></span><br><span style='font-family: monospace'>#1846c2 <span style='color: oklch(0.45298 0.19952 264.05)'>██████</span></span>"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "display(Markdown('<br>'.join(\n",
    "    f\"<span style='font-family: monospace'>{c.convert('srgb').to_string(hex=True)} \"\n",
    "    f\"<span style='color: {c.to_string()}'>██████</span></span>\"\n",
    "    for c in sorted_medoid_colors\n",
    ")))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "snakemake",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}