如何基于8位向量近似实现数组中最匹配颜色的查找？

核心结论 #

直接用((a - b) ** 2 & 0xff00) >> 8作为平方距离的近似完全不可行，会丢失关键精度，导致颜色匹配结果严重失真。

为什么这个近似无效 #

8位颜色的差值范围是0_{255，对应的平方差范围是0}65025（即16位整数）。你取平方差的高8位，相当于只保留了数值除以256的整数部分：

• 当差值为15时，平方是225，高8位为0，会被误判为无差异；
• 当差值为16时，平方是256，高8位为1，会被当成最小差异。
  这种粗暴的截断会把大量不同的颜色差异归为同一等级，完全无法准确区分调色板中颜色的匹配度。

替代的8位向量优化方案 #

既然AVX2/AVX512没有_mm256_mulhi_epu8指令，推荐两种高效实现平方距离计算的思路：

1. 预计算平方表+向量查表 #

利用8位绝对差的范围仅0~255的特性，预先生成一个256项的平方值表，再通过向量指令批量查表得到平方差，最后累加RGB通道的结果：

// 预先生成平方值表
uint16_t sq_table[256];
void init_sq_table() {
    for (int i = 0; i < 256; i++) {
        sq_table[i] = (uint16_t)i * i;
    }
}

// AVX2批量计算平方距离
#include <immintrin.h>
__m256i compute_sq_distances_avx2(__m256i pixel_r, __m256i pixel_g, __m256i pixel_b, 
                                 __m256i palette_r, __m256i palette_g, __m256i palette_b) {
    // 计算RGB各通道绝对差
    __m256i dr = _mm256_abs_epi8(_mm256_sub_epi8(pixel_r, palette_r));
    __m256i dg = _mm256_abs_epi8(_mm256_sub_epi8(pixel_g, palette_g));
    __m256i db = _mm256_abs_epi8(_mm256_sub_epi8(pixel_b, palette_b));
    
    // 查表获取平方值
    __m256i sq_dr = _mm256_shuffle_epi8(_mm256_loadu_si256((const __m256i*)sq_table), dr);
    __m256i sq_dg = _mm256_shuffle_epi8(_mm256_loadu_si256((const __m256i*)sq_table), dg);
    __m256i sq_db = _mm256_shuffle_epi8(_mm256_loadu_si256((const __m256i*)sq_table), db);
    
    // 将8位平方值扩展为16位
    sq_dr = _mm256_unpacklo_epi8(sq_dr, _mm256_setzero_si256());
    sq_dg = _mm256_unpacklo_epi8(sq_dg, _mm256_setzero_si256());
    sq_db = _mm256_unpacklo_epi8(sq_db, _mm256_setzero_si256());
    
    // 累加三通道平方差
    __m256i total = _mm256_add_epi16(sq_dr, sq_dg);
    total = _mm256_add_epi16(total, sq_db);
    
    return total;
}

2. 扩展为16位后计算平方 #

直接将8位差值扩展为16位整数，再用AVX2的16位乘法指令计算平方，最后累加结果。这种方法虽然用到16位向量，但AVX2对16位数据的处理效率很高，完全可以接受：

#include <immintrin.h>
__m256i compute_sq_distances_avx2_v2(__m256i pixel_r, __m256i pixel_g, __m256i pixel_b, 
                                     __m256i palette_r, __m256i palette_g, __m256i palette_b) {
    // 将8位颜色值扩展为16位有符号整数
    __m256i p_r = _mm256_cvtepi8_epi16(pixel_r);
    __m256i p_g = _mm256_cvtepi8_epi16(pixel_g);
    __m256i p_b = _mm256_cvtepi8_epi16(pixel_b);
    
    __m256i pal_r = _mm256_cvtepi8_epi16(palette_r);
    __m256i pal_g = _mm256_cvtepi8_epi16(palette_g);
    __m256i pal_b = _mm256_cvtepi8_epi16(palette_b);
    
    // 计算差值
    __m256i dr = _mm256_sub_epi16(p_r, pal_r);
    __m256i dg = _mm256_sub_epi16(p_g, pal_g);
    __m256i db = _mm256_sub_epi16(p_b, pal_b);
    
    // 计算平方
    __m256i sq_dr = _mm256_mullo_epi16(dr, dr);
    __m256i sq_dg = _mm256_mullo_epi16(dg, dg);
    __m256i sq_db = _mm256_mullo_epi16(db, db);
    
    // 累加三通道平方差
    __m256i total = _mm256_add_epi16(sq_dr, sq_dg);
    total = _mm256_add_epi16(total, sq_db);
    
    return total;
}

纯C版本代码优化建议 #

你的纯C实现可以做两点优化：用无符号类型存储距离避免溢出风险，显式计算绝对差让逻辑更清晰：

#include <stdint.h>
#include <stdlib.h>

struct col {
    uint8_t r,g,b;
};

struct col cols[256];

int find_i(struct col x) {
    int mini = 0;
    uint32_t mind = UINT32_MAX;
    for (int i = 0; i < 256; i++) {
        uint8_t dr = abs((int)x.r - (int)cols[i].r);
        uint8_t dg = abs((int)x.g - (int)cols[i].g);
        uint8_t db = abs((int)x.b - (int)cols[i].b);
        uint32_t d = (uint32_t)dr*dr + (uint32_t)dg*dg + (uint32_t)db*db;
        if (d < mind) {
            mind = d;
            mini = i;
        }
    }
    return mini;
}

内容的提问来源于stack exchange，提问作者Cloud11665