Фрактальный алгоритм сжатия изображений

@EVG! · Регистрация: 21.11.2010

Студворк — интернет-сервис помощи студентам

Хочется последовательно обсудить реализацию фрактального алгоритма кодирования ЦВЕТНЫХ изображений.
Пункт 1. Перевод изображения из RGB в YUV.
Y = 0.299 * R + 0.587 * G + 0.114 * B;
U = -0.14713 * R - 0.28886 * G + 0.436 * B;
V = 0.615 * R - 0.51499 * G - 0.10001 * B;
С формулами все ясно. А вот насчет той груды груды информации (Y, U, V для каждого пиксела) которую надо будет жранить для последующей обработки возникают вопросы.
Первое, что пришло на ум:
1. Изображение загружаем в БитМан bm;
2. Для хранения Y,U,V создаем

Delphi
1
2
3
4
Type
    colorYUV = Record
    Y, U ,V : real;
    end;

3. Создаем список для хранения указателей на colorYUV:

Delphi
1
ListYUV:=TList.Create;

4. Объявляем R: ^colorYUV и далее для каждого пиксела:

Delphi
1
2
3
4
5
6
7
8
9
10
11
New(R);
R^.Y:=0.299*getRValue(bm.Canvas.Pixels[i,j])+
           0.587*getGValue(bm.Canvas.Pixels[i,j])+
           0.114*getBValue(bm.Canvas.Pixels[i,j]);
R^.U:=-0.14713*getRValue(bm.Canvas.Pixels[i,j])-
           0.28886*getGValue(bm.Canvas.Pixels[i,j])+
           0.43600*getBValue(bm.Canvas.Pixels[i,j]);
R^.V:=0.61500*getRValue(bm.Canvas.Pixels[i,j])-
          0.51499*getGValue(bm.Canvas.Pixels[i,j])-
          0.10001*getBValue(bm.Canvas.Pixels[i,j]);
ListYUV.Add(R);

Как на Ваш взгляд все это дело упростить и сделать более грамотно?
Если же все так и оставить, то как грамотнее реализовать следующий шаг разбиение изображения в YUV сеткой 8 на 8, с условием что каждый квадрат легко можно было бы подвергнуть аффинным преобразованиям?

@snake32 · 22.11.2010, 02:32

Может проще заюзать динамический массивчиг?
Какие плюсы я вижу:
1 Из массива легче будет вырезать куски 8*8
2 Скорость увеличится за счёт единовременного выделения памяти, а не для каждого пикселя
Ещё одно ускорение - можно использовать тип single
Итого:

Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
type
  TYUV = packed record // упакованная запись ест меньше памяти,
    Y,U,V : single;          //  хотя в данном случае, скорее всего, весить будет одинаково
  end;
 
var 
  YUVmatrix:array of array of TYUV;// двумерный динамический массив
 
begin
  SetLength( YUVmatrix, bmp.Height, bmp.Width );
  for j:=0 to bmp.Height-1 do
    for i:=0 to bmp.Width-1 do
    begin
      YUVmatrix[j,i].Y := ...
      YUVmatrix[j,i].U := ...
      YUVmatrix[j,i].V := ...
    end;
end;

Не знаю как в других делфях, но в 2010 можно записям назначать свои методы и перегружать операторы, что сокращает код и приводит его в более читабельный вид.
Например, к структуре TcolorYUV можно дописать метод преобразования из RGB:

Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
TYUV = packed record
    Y,U,V : single;
    procedure SetFromTColor( const color:TColor );
  end;
 
// где-то после implimentation
procedure TYUV.SetFromTColor( const color:TColor );
begin
  Y := ...
  U := ...
  V := ...
end;
// тогда заполнение будет выглядеть так:
SetLength( YUVmatrix, bmp.Height, bmp.Width );
  for j:=0 to bmp.Height-1 do
    for i:=0 to bmp.Width-1 do
      YUVmatrix[j,i].SetFromTColor( bmp.Canvas.Pixels[i,j] );

Сообщение от EVG!

разбиение изображения в YUV сеткой 8 на 8, с условием что каждый квадрат легко можно было бы подвергнуть аффинным преобразованиям?

Думаю, проще всего работать с квадратами как с объектами(или как минимум с записями). Поэтому лучше всего создать класс TSprite, например, который сам по себе независимый и имеет такие атрибуты как: позиция, угол поворота... ну вообщем все необходимые данные для самостоятельной работы.

@EVG! · 22.11.2010, 17:31 **[ТС]**

Спасибо за развернутый ответ.
Немного о самом алгоритме:
Сначала берется исходное изображение, и разбивается равномерной сеткой 8*8 на регионы.
Далее подготавливается доменное изображение. Оно меньше, чем исходное в 4 раза (по площади). Доменное изображение разбивается на домены (8*8).
Размер доменов равен размеру регионов. НО! ДОМЕНЫ МОГУТ ПЕРЕКРЫВАТЬСЯ! (перекрытие задается пользователем, чаще всего 50%)
Процесс фрактального сжатия заключается в поиске самоподобных областей. В нашем случае последовательно перебираются все регионы, и для каждого региона определяется наиболее похожий на него домен. Применяется не только простое попиксельное сравнение региона с доменом, но и аффинные преобразования. Используются следующие аффинные преобразования:
1) поворот на 0 градусов (с технической точки зрения – тоже вариант)
2) поворот на 90 градусов
3) поворот на 180 градусов
4) поворот на 270 градусов
5) симметрия относительно оси Х
6) симметрия относительно оси У
7) симметрия относительно главной диагонали
8) симметрия относительно второстепенной диагонали
Итак, аффинные преобразования можно выполнять как над регионами, так и над доменами. Однако аффинные преобразования над доменами будут выполняться дольше, чем над регионами, так как в процессе сжатия регионы перебираются всего 1 раз, а домены – много раз (для каждого региона по разу). Таким образом, аффинные преобразования следует выполнять над регионами.
В общем, в процессе сжатия последовательно перебираются все регионы, для каждого региона последовательно перебираются все домены, которые в свою очередь сравниваются со всеми аффинными преобразованиями текущего региона.
Изображения сравниваются по пикселям.
Самый лучший домен тот, у которого окажется самым минимальным выражение:
СуммаПоI_CуммаПОJ(s*dij+o-rij)^2,
где s=СуммаПоI_CуммаПОJ((dij-d)*(rij-r))/СуммаПоI_CуммаПОJ((dij-d)^2)
o=r-s*d;
r,d - средние значения для регионов и доменов.
Итак, после того, как для текущего региона (со всеми аффинными преобразованиями) был найден наиболее схожий с ним домен, необходимо запомнить следующие данные:
- координаты домена (относительно доменного изображения);
- номер аффинного преобразования (2-е и 4-е аффинное преобразование следует поменять местами, так как при распаковке изображения аффинные преобразования нужно будет выполнять не над регионами, а над доменами);
- s, o;
- количество регионов по гор-ли и повертикали.

Добавлено через 14 минут
Интересует алгоритм сжатия размеров изображения в 4 по площади. Вот так можно:

Delphi
1
2
3
4
5
6
7
8
9
 imR := Graphics.TBitmap.Create; //исходное изображение
 imR.LoadFromFile('3.bmp');
 w:=round(imR.Width/2); //размеры 
 h:=round(imR.Height/2); //      уменьшенного
 imD := Graphics.TBitmap.Create; //само будущее уменьшенное изображение
 imD.Width:=w;
 imD.Height:=h;
//формирование в imD уменьшенного изображения
 StretchBlt(imD.Canvas.Handle,0,0,w,h,imR.Canvas.Handle,0,0,imR.Width,imR.Height,SrcCopy);

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

Delphi
1
2
3
TColorYUV = packed record
    Y,U,V : single;
end;

переводим ранговое imR и доменное imD изображения в YUB:

Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 SetLength(RegionYUV, imR.Height, imR.Width);
  for j:=0 to imR.Height-1 do
    for i:=0 to imR.Width-1 do
    begin
      RegionYUV[j,i].Y :=0.299*getRValue(imR.Canvas.Pixels[i,j])+
                         0.587*getGValue(imR.Canvas.Pixels[i,j])+
                         0.114*getBValue(imR.Canvas.Pixels[i,j]);
      RegionYUV[j,i].U :=-0.14713*getRValue(imR.Canvas.Pixels[i,j])-
                          0.28886*getGValue(imR.Canvas.Pixels[i,j])+
                          0.43600*getBValue(imR.Canvas.Pixels[i,j]);
      RegionYUV[j,i].V :=0.61500*getRValue(imR.Canvas.Pixels[i,j])-
                         0.51499*getGValue(imR.Canvas.Pixels[i,j])-
                         0.10001*getBValue(imR.Canvas.Pixels[i,j]);
    end;
 SetLength(DomainYUV, imD.Height, imD.Width);
  for j:=0 to imD.Height-1 do
    for i:=0 to imD.Width-1 do
    begin
      DomainYUV[j,i].Y :=0.299*getRValue(imD.Canvas.Pixels[i,j])+
                         0.587*getGValue(imD.Canvas.Pixels[i,j])+
                         0.114*getBValue(imD.Canvas.Pixels[i,j]);
      DomainYUV[j,i].U :=-0.14713*getRValue(imD.Canvas.Pixels[i,j])-
                          0.28886*getGValue(imD.Canvas.Pixels[i,j])+
                          0.43600*getBValue(imD.Canvas.Pixels[i,j]);
      DomainYUV[j,i].V :=0.61500*getRValue(imD.Canvas.Pixels[i,j])-
                         0.51499*getGValue(imD.Canvas.Pixels[i,j])-
                         0.10001*getBValue(imD.Canvas.Pixels[i,j]);
    end;

И кодируем регионы, т.е в цикле перебираем каждый регион и для него строим 8 матриц 8*8 в соответствии с выше описанными преобразованиями и сравнимаем с доменами. Здесь вопрос об алгоритмах реализации этих самых преобразований с наибольшим выигрыванием времени, ведь алгоритм сам по себе минут 10 будет работать для всего изображения (это самый простой случай алгоритма, после его реализации непосредственно займусь его оптимизацией по времени, сначало посмотрю что к чему в нем).

15.05.2012, 09:15

EVG!, Добрый день! Не могли бы вы написать адрес своей электронной почты мне в ЛС? Есть несколько вопросов по данной теме.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

MichaelJ
	15.05.2012, 09:15
	EVG!, Добрый день! Не могли бы вы написать адрес своей электронной почты мне в ЛС? Есть несколько вопросов по данной теме.