如何优化此haskell功能

Question

我需要在调色板中找到最接近ps给定颜色的颜色p.如何在nearestColor不改变Pixel8或类型的情况下尽可能快地完成 功能PixelRGB8.到目前为止,我已尝试内联.

import qualified Data.Vector as V

type Pixel8 = Word8    

data PixelRGB8 = PixelRGB8 {-# UNPACK #-} !Pixel8 -- Red
                           {-# UNPACK #-} !Pixel8 -- Green
                           {-# UNPACK #-} !Pixel8 -- Blue
           deriving (Eq, Ord, Show)

nearestColor :: PixelRGB8 -> Vector PixelRGB8 -> PixelRGB8
nearestColor p ps = snd $ V.minimumBy comp ds
  where
    ds = V.map (\px -> (dist2Px px p, px)) ps
    comp a b = fst a `compare` fst b

dist2Px :: PixelRGB8 -> PixelRGB8 -> Int
dist2Px (PixelRGB8 r1 g1 b1) (PixelRGB8 r2 g2 b2) = dr*dr + dg*dg + db*db
  where
    (dr, dg, db) =
      ( fromIntegral r1 - fromIntegral r2
      , fromIntegral g1 - fromIntegral g2
      , fromIntegral b1 - fromIntegral b2 )

Answer 1

如果你想使用单个调色板并请求不同的颜色,我首先要翻转你的签名:

type Palette = V.Vector PixelRGB8
nearestColor :: Palette -> PixelRGB8 -> PixelRGB8

这有利于部分应用,并允许记录调色板配置.

接下来,您要这样做:将调色板重新存储在适合快速查找的数据结构中.既然你在ℝ欧氏距离基本上感兴趣³(BTW没有真正理想的颜色比较),这是一个非常普遍的问题.经典结构是k- d树,长期以来一直用于这种最近邻搜索.确实有一个Haskell库可供使用,它为您提供了非常方便的界面:

import qualified Data.Trees.KdTree a s KD

instance KD.Point PixelRGB where
  dimension _ = 3
  coord 0 (PixelRGB r _ _) = fromIntegral r
  coord 1 (PixelRGB _ g _) = fromIntegral g
  coord 2 (PixelRGB _ _ b) = fromIntegral b
  dist2 = fromIntegral . dist2Px

然后我们可以将调色板转换为这样的树:

type FastPalette = KD.KdTree PixelRGB8
accelPalette :: Palette -> FastPalette
accelPalette = KD.fromList . V.toList

最后只需使用库提供的下一个邻居搜索:

nearestColor palette = fromJust . KD.nearestNeighbor fpal
 where fpal = accelPalette palette