Interesting question - I think I would start of solving it somehow like:
Problem:
Calculating the average of an picture uses quite alot of CPU-Power.
Finding an fitting color to the color we calculated from the picture.
(my) solution:
I would first of all calculate the color once, and write it to an database - so that you don't need to calculate it with each sitecall. Then I would make an table which holds colors - which harmonize to each other. Of course you should have an color-area -> on the one site.
Well and there you go, when the picture is called the first time - it will calculate its color -> select a fitting from the table you saved.
Some rough code - no even more than rough - should just give an idea what I'm talking about. (I think code explains more then words

)
And sorry had not much time - and no syntax coloring -tool available
PHP Code:
mysql_query(SELECT * FROM TABLE_PICTUES WHERE picturename = mypicture);
if(mysql_num_rows == 0)//picture not in DB
{
$averageColor = getColor($imagename);
mysql_query("INSERT INTO TABLE_PICTURES picturename, $averageColor");
}
//And now get the color from the db - and give it out.
function getColor($image){
$imagepath = 'images/myimages/' . $image;
$src = imagecreatefromjpeg($imagepath);
$width = imagesx($src);
$height = imagesx($src);
$dst = imagecreatetruecolor(1,1);
imagecopyresampled($dst, $src , 0, 0, 0, 0, 1, 1, $width, $height);
$color = imagecolorat($dst,0,0);
$alpha = ($color >>24) & 0xFF;
$red = ($color>> 16) & 0xFF;
$green = ($color>> 8) & 0xFF;
$blue = ($color) & 0xFF;
imagedestroy($src);
imagedestroy($dst);
}
ooh yeah - and remember Im still a noob - so this could be a total mess
