Если делать, то только на сканлайнах, перейдя на winapi тикакого выйграша ты не получишь.
Самое главное это быстрые алгоритмы.
Вот
тут очень быстрая функция для подсчета цветов, можешь для начала переделать ее, что бы получить минимальную палитру и число каждого из цветов. Потом идеи еще появятся, я думаю.
А вообще, лучше поискать готовые библиотеки, если порыться в той же XnView, думаю можно найти нужные dll и экспортировать их них функции.