VPF::Алгоритм конв. bitmap'a из 16млн. в 256 цветов

586

Дата 30.8.2006, 03:51 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2243
Регистрация: 8.5.2006

Репутация: нет
Всего: 146

Нужно конвертировать точечный рисунок из 16 миллионов цветов в 256 с наименьшими потерями качества рисунка. Такая же задача из 256 цветов в 16. Есть ли какой-нибудь алгоритм?

Romikgy

Дата 30.8.2006, 09:02 (ссылка)

(нет голосов)

Загрузка ...

Любитель-программер

Профиль
Группа: Участник Клуба
Сообщений: 7326
Регистрация: 11.5.2005
Где: Porto Franco Odes sa

Репутация: 1
Всего: 146

Что обозначает

Цитата(586 @ 30.8.2006, 02:51

)

с наименьшими потерями качества рисунка.

как можно здесь сделать меньше или больше качество? ты все равно режешь цветность !
а алгоритм очень прост
цвет 16 млн это 24 бита цветности, 8 бит красный , 8 бит зеленый , 8 бит синий,
256 цветов это 8 бит, и там делается через палитры цветов
http://forum.vingrad.ru/index.php?showtopic=94227&hl=
прочитай много интересного

--------------------

Владение русской орфографией это как владение кунг-фу — истинные мастера не применяют его без надобности.

maxim1000

Дата 30.8.2006, 09:56 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110

Цитата(Romikgy @ 30.8.2006, 08:02

)

как можно здесь сделать меньше или больше качество? ты все равно режешь цветность !
а алгоритм очень прост

от выбора цветов палитры качество очень даже зависит
если, например, рисунок серый с вкраплениями красного, то и палитра должна состоять из градаций серого и красного
а если отводить ещё цвета и на зелёный с синим, то количество уветов для серого и красного уменьшится и они будут переданы хуже, хотя ни синий, ни зелёный не используются

думаю, для начала нужно построить диаграмму распределения цвета - кубик 256х256х256, заполненный действительными (ну или целыми) числами, а потом в нём расставлять 256 (или 16) точек

кроме того нужно выбрать функцию определения степени различия двух цветов и собственн критерий оптимальности (либо минимум средней разницы, либо минимакс какой-нибудь)

а дальше - самое интересное - алгоритм расстановки точек
тут мыслей пока немного:
перебор будет слишком долго
возможно, удастся приспособить динамическое программирование
но тут лучше сначала с критерием определиться, а потом уже дальше думать...

--------------------

qqq

Earnest

Дата 30.8.2006, 11:18 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 7
Всего: 183

Одним из лучших (и несложных в реализации) является алгоритм квантования цветов методом построения октанового дерева. Вкратце: на первом проходе все встреченные цвета помещаются в октановое дерево: корень - все RGB - пространство, имеет 8 потомков, где каждой представляет 1/8 RGB-пространства корня. Деление осуществляется разбиением корневого диапазона на 2 половины по каждой цветовой компоненте, т.е. решение принимается на основании очередного бита компоненты. Т.е. дерево теоретически имеет 9 уровней. Дерево (а не массив) используется потому, что позволяет боле просто ограничить размер дерева по мере его роста (т.к. полное RGB-дерево занимает безбну памяти): по дороге в каждом узле накапливается информация о числе "прошедших" через него пикселов. Когда дерево слишком разрастается, малозначительные ветви просто обрубаются (но огрубленная информация остается в их корнях). На втором проходе число листьев дерева сокращается до требуемого (256) тем же путем огрубления малозначительных ветвей. По оставшимся строится цветовая таблица.
Более подробное описание алгоритма есть в книгах по графике, например, у Фень Юаня. А может, и в Интернете найти можно.

--------------------

...

cardinal

Дата 30.8.2006, 15:58 (ссылка)

(нет голосов)

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: 5
Всего: 99

Тут посмотри
http://forum.vingrad.ru/index.php?act=Sear...er&skipped=
(короче по ключевому слову dither ищи)...

--------------------

Немецкая оппозиция потребовала упростить натурализацию иммигрантов
В моем блоге: Разные истории из жизни в Германии

"Познание бесконечности требует бесконечного времени, а потому работай не работай - все едино". А. и Б. Стругацкие

586

Дата 30.8.2006, 21:44 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2243
Регистрация: 8.5.2006

Репутация: нет
Всего: 146

Цитата(Earnest @ 30.8.2006, 12:18

)

Более подробное описание алгоритма есть в книгах по графике, например, у Фень Юаня

Earnest,
Фень Юань - Программирование графики для Windows?
Какая страница?

Earnest

Дата 31.8.2006, 08:16 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 7
Всего: 183

Да, у меня - 726,
Глава 13 Палитра, Квантование цветов

--------------------

...

586

Дата 31.8.2006, 19:40 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2243
Регистрация: 8.5.2006

Репутация: нет
Всего: 146

Помогите довести до ума.
Главный вопрос в том, как использовать эти классы (взял из книги).
// строка 298 - работа с классом

Код

#include <windows.h>

class KNode
{
public:
 bool IsLeaf;        // указ., является ли узел листовым (листовой узел опр. как узел, не имеющий потомков)
 KNode *Child[8];
 unsigned Pixels, SigmaRed, SigmaGreen, SigmaBlue;

 KNode(bool leaf)
 {
  IsLeaf=leaf;
  Pixels=0;
  SigmaRed=0;
  SigmaGreen=0;
  SigmaBlue=0;
  memset(Child, 0, sizeof(Child));
 }
 RemoveAll(); // удаляет все узлы текущего поддерева
 int PickLeaves(RGBQUAD *pEntry, int *pFreq, int size);
  // собирает итоговую информация, накопленную в дереве
};

KNode::RemoveAll()
{
 for(int i=0; i<8; i++)
  if(Child[i])
  {
   Child[i]->RemoveAll();
   Child[i]=0;
  }
 delete this;
}

int KNode::PickLeaves(RGBQUAD *pEntry, int *pFreq, int size)
{
 if(!size) return 0;
 if(IsLeaf)
 {
  *pFreq=Pixels;
  pEntry->rgbRed=(SigmaRed+Pixels/2)/Pixels;
  pEntry->rgbGreen=(SigmaGreen+Pixels/2)/Pixels;
  pEntry->rgbBlue=(SigmaBlue+Pixels/2)/Pixels;
  return 1;
 } else {
  int sum=0;
  for (int i=0; i<8; i++)
   if(Child[i])
    sum+=Child[i]->PickLeaves(pEntry+sum, pFreq+sum, size-sum);
  return sum;
 }
}

class KOctree
{
public:
 typedef enum{ MAXNODE = 65536 };
 KNode *pRoot;
 int TotalNode;
 int TotalLeaf;

 void Reduce(KNode *pTree, unsigned threshold);

public:
 KOctree()
 {
  pRoot=new KNode(false);
  TotalNode=1;
  TotalLeaf=0;
 }
 
 ~KOctree()
 {
  if(pRoot)
  {
   pRoot->RemoveAll();
   pRoot=0;
  }
 }
 
 void AddColor(BYTE r, BYTE g, BYTE b);
 void ReduceLeaves(int limit);
 int GenPellete(RGBQUAD *entry, int *pFreq, int size);
 void Merge(KNode *pNode, KNode &target);
};

void KOctree::AddColor(BYTE r, BYTE g, BYTE b)
{
 KNode *pNode=pRoot;
 for(BYTE mask=0x80; mask!=0; mask>>=1) // Следовать до листового узла
 {
  // Добавить пиксел
  pNode->Pixels++;
  pNode->SigmaRed+=r;
  pNode->SigmaGreen+=g;
  pNode->SigmaBlue+=b;
  if(pNode->IsLeaf) break;
  
  // Взять по одному биту от каждой состовляющей
  // для формирования индекса
  int index=((r & mask) ? 4 : 0)+
            ((g & mask) ? 2 : 0)+
            ((b & mask) ? 1 : 0);
  
  // Создать новый узел, если это новая ветвь
  if(!pNode->Child[index])
  {
   pNode->Child[index]=new KNode(mask==2);
   TotalNode++;
   if(mask==2) TotalLeaf++;
  }
  
  // Следовать дальше
  pNode=pNode->Child[index];
 }
 for(int threshold=1; TotalNode>MAXNODE; threshold++)
  Reduce(pRoot, threshold);
}
 
// Объединить узел с листовыми узлами-потомками и количеством пикселов, не превышающих threshold
// Объединить листовой узел с количеством threshold, с ближайшим соседом
 
void KOctree::Reduce(KNode *pTree, unsigned threshold)
{
 if(!pTree) return;
 bool childallleaf=true;
 
 // Рекурсивно вызвать для всех не-листовых потомков
 for(int i=0; i<8; i++)
  if(pTree->Child[i] && !pTree->Child[i]->IsLeaf)
  {
   Reduce(pTree->Child[i], threshold);
   if(!pTree->Child[i]->IsLeaf)
    childallleaf=false;
  }
 
 // Если все потомки являются листовыми узлами
 // а количество пикселов не превышает порогового - объединить
 if(childallleaf & (pTree->Pixels<=threshold))
 {
  for(int i=0; i<8; i++)
   if(pTree->Child[i])
   {
    delete pTree->Child[i];
    pTree->Child[i]=NULL;
    TotalNode--;
    TotalLeaf--;
   }
  pTree->IsLeaf=true;
  TotalLeaf++;
  return;
 }
 
 // Объединить листовых потомков
 // с небольшим количеством пикселов
 for(i=0; i<8; i++)
 {
  if(pTree->Child[i] && pTree->Child[i]->IsLeaf &&
     (pTree->Child[i]->Pixels<=threshold))
  {
   KNode temp=*pTree->Child[i];
   delete pTree->Child[i];
   pTree->Child[i]=NULL;
   TotalNode--;
   TotalLeaf--;
   for(int j=0; j<8; j++)
    if(pTree->Child[j])
    {
     Merge(pTree->Child[j], temp);
     break;
    }
 }}
}

void KOctree::Merge(KNode *pNode, KNode &target)
{
 while(true)
 {
  pNode->Pixels+=target.Pixels;
  pNode->SigmaRed+=target.SigmaRed;
  pNode->SigmaGreen+=target.SigmaGreen;
  pNode->SigmaBlue+=target.SigmaBlue; 
 
  if(pNode->IsLeaf) break;
  KNode *pChild = NULL;
  
  for(int i=0; i<8; i++)
   if(pNode->Child[i])
   {
    pChild=pNode->Child[i];
    break;
   }
  if(!pChild)
  {
   //assert(FALSE);
   return;
  } else 
   pNode=pChild;
 }
}

void KOctree::ReduceLeaves(int limit)
{
 for(unsigned threshold=1; TotalLeaf>limit; threshold++)
  Reduce(pRoot, threshold);
}

int KOctree::GenPellete(RGBQUAD *entry, int *pFreq, int size)
{
 ReduceLeaves(size);
 return pRoot->PickLeaves(entry, pFreq, size);
}

// Класс построения палтры с применением октантного дерева
/*class KPaletteGen: public KPixelMapper
{
 KOctree octree;
 
 // вернуть true, если данные изменились
 virtual bool MapRGB(BYTE &red, BYTE &green, BYTE &blue)
 {
  octree.AddColor(red, green, blue);
  return false;
 }

public:
 void AddBitmap(KImage &dib)
 {
  dib.PixelTransform(*this);
 }

 int GetPallete(RBGQUAD *pEntry, int *pFreq, int size)
 {
  return octree.GenPalette(pEntry, pFreq, size);
 }
};*/

/*int GetPalette(BITMAPINFO *pDIB, RGBQUAD *pEntry, int pFreq, int size)
{
 KImage dib;
 KPalleteGen palgen;
 
 dib.AttachDIB(pDIB, NULL, 0);
 palgen.AddBitmap(dib);
 return palgen.GetPallete(pEntry, pFreq, size);
}*/

//==================================================================================

void __stdcall GetErrDscr(HWND hWnd, char *str)
{
    char *c;
    FormatMessage(0x1100, 0, GetLastError(), 0, (char*)&c, 0, 0);
    MessageBoxA(hWnd, c, str, 16); 
}

int __stdcall WinMain(HINSTANCE, HINSTANCE, LPSTR, INT)
{
    HANDLE f, ff, hMap;
    void *pMap;
    f=CreateFile("C:\\test.bmp", GENERIC_READ, FILE_SHARE_READ, 0, OPEN_EXISTING, 0, 0);
    if(f!=(HANDLE)-1)
    {
        hMap=CreateFileMapping(f, 0, PAGE_READONLY, 0, 0, 0);
        if(hMap)
        {
            pMap=MapViewOfFile(hMap, FILE_MAP_READ, 0, 0, 0);
            if(pMap)
            {
                ff=CreateFile("C:\\ret.bmp", GENERIC_WRITE, FILE_SHARE_READ, 0, CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, 0);
                if(ff!=(HANDLE)-1)
                {
                    BITMAPFILEHEADER *bmfh=(BITMAPFILEHEADER*)pMap;
                    BITMAPINFOHEADER *bmih=(BITMAPINFOHEADER*)(DWORD)pMap+sizeof(BITMAPFILEHEADER);
                    RGBQUAD          aColors[16];        // array
                    BYTE             *aBits=(PBYTE)(DWORD)pMap+bmfh->bfOffBits;    // array
                    BITMAPFILEHEADER __bmfh;        // для записи
                    BITMAPINFOHEADER __bmih;        // для записи
                    DWORD r;
                    int i;
                    // копирование заголовка из оригинального файла для работы с ним
                    memcpy(&__bmfh, bmfh, sizeof(BITMAPFILEHEADER));
                    // вычисление размера файла
                    __bmfh.bfSize=bmih->biHeight*bmih->biWidth+    // разм. массива
                        4*16+sizeof(BITMAPFILEHEADER)+            // разм. RGBQUAD и заголовочных структур
                        sizeof(BITMAPINFOHEADER);
                    __bmfh.bfOffBits=sizeof(BITMAPFILEHEADER)+
                        sizeof(BITMAPINFOHEADER)+4*16;
                    WriteFile(ff, &__bmfh, sizeof(BITMAPFILEHEADER), &r, 0);

                    // копирование второго заголовка из оригинального файла для работы с ним
                    memcpy(&__bmih, bmih, sizeof(BITMAPINFOHEADER));
                    __bmih.biBitCount=8;    // задание количества бит на пиксел
                    __bmih.biSizeImage=bmih->biWidth*bmih->biHeight;
                        // задание размера буфера с пикселами
                    WriteFile(ff, &__bmih, sizeof(BITMAPINFOHEADER), &r, 0);

                    KOctree *t=new KOctree();
                    for(i=0; i<__bmfh.bfSize; i+=3)
                        t->AddColor(aBits[i], aBits[i+1], aBits[i+2]);
                    t->GenPellete((RGBQUAD*)&aColors, &i, 256);        // ??????
                    delete t;
                    WriteFile(ff, &aColors, 4*16, &r, 0);
                        // сохранение расцветки RGBQUAD
                    
                    CloseHandle(ff);
                } else GetErrDscr(0, "Can't create output file");
                UnmapViewOfFile(pMap);
            } else GetErrDscr(0, "Can't map view of file");
            CloseHandle(hMap);
        } else GetErrDscr(0, "Can't create file mapping");
        CloseHandle(f);
    } else GetErrDscr(0, "Can't to open file");
    return 0;
}

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »