title: Color similarity/distance in RGBA color space
body: <p><strong>How to compute similarity between two colors in RGBA color space?</strong> (where the background color is unknown of course)</p>
  <p>I need to remap an RGBA image to a palette of RGBA colors by finding the <em>best</em> palette entry for each pixel in the image*.</p>
  <p>In the RGB color space the most similar color can be assumed to be the one with the smallest euclidean distance. However, this approach doesn't work in RGBA, e.g., Euclidean distance from <code>rgba(0,0,0,0)</code> to <code>rgba(0,0,0,50%)</code> is smaller than to <code>rgba(100%,100%,100%,1%)</code>, but the latter looks much better.</p>
  <p>I'm using premultiplied RGBA color space:</p>
  <pre><code>r = r×a
  g = g×a
  b = b×a
  </code></pre>
  <p>and I've tried this formula (<em>edit:</em> <a href="https://stackoverflow.com/a/8796867/27009">See the answer below for better formula</a>):</p>
  <pre><code>Δr² + Δg² + Δb² + 3 × Δa²
  </code></pre>
  <p>but it doesn't <em>look</em> optimal — in images with semitransparent gradients it finds wrong colors that cause discontinuities/sharp edges. Linear proportions between opaque colors and alpha seem fishy.</p>
  <p>What's the optimal formula?</p>
  <hr />
  <p>*) for simplicity of this question I'm ignoring error diffusion, gamma and psychovisual color spaces.</p>
  <hr />
  <p>Slightly related: if you want to find nearest color in this non-Euclidean RGBA space, <a href="https://github.com/kornelski/vpsearch" rel="nofollow noreferrer">vp-trees</a> are the best.</p>