Фотоальбом
Матейчук Максим Сергійович
Науково-навчальні матеріалиПрактичні роботи

АЛГОРИТМ виконання оригінального безмаскового пі-перетворення для зображення на CPU

АЛГОРИТМ

виконання оригінального безмаскового пі-перетворення для зображення на CPU

 

1) завантажуємо зображення в пам’ять.

n – висота зображення, m – ширина зображення.

 

2) елементи, які мають значення нуль, на відповідь не впливають. до того ж, в процесі роботи алгоритма кількість нульових елементів значно перевищує кількість ненульових, тому, для значного прискорення роботи, числові дані про кожен ненульовий піксель будемо зберігати у власній структурі, що містить три поля:

значення, рядок, колонка

struct elem {

         int val, r, c;

};

 

3) заведемо структуру розміром [n * m] (максимально можлива кількість ненульових елементів) і заповнимо її даними при кожен ненульовий елемент

 

4) заведемо дві змінні L R, ліва і права границя, в межах яких ми працюємо з нашим масивом даних. ініціалізуємо L = 0, R = кількість ненульових елементів

 

5) основу пі-перетворення складають 3 операції: Транспонування (Т),   G-перетворення (G), Зсув (S). Алгоритми виконання кожної операції будуть розглянуті нижче.

 

6) виконаємо операцію G.

 

7) доки до обробки не залишився один елемент, тобто доки L < R – 1 виконуємо послідовно три операції: T, G, S.

 

8) Елементи з 0 до L включно – хвостові елементи, результат роботи алгоритму.

 

Операція T:

1) В масиві даних, починаючи з L до R невключно, для кожного елемента міняємо місцями значення рядка і колонки.

 

2) Міняємо значення n, m місцями.

 

3) дані транспоновані, але в масиві порядок невірний, тому необхідно впорядкувати масив в межах [L, R) використовуючи наступну логіку при порівнянні, який з двох елементів йде раніше: елемент А йде раніше елемента Б, якщо значення рядка елемента А менше значення рядка елемента Б, або при їх рівності значення колонки А менше значення колонки Б.

 

 

 

Операція G:

1) Впорядковуємо масив в межах [L, R) використовуючи наступну логіку при порівнянні, який з двох елементів йде раніше: елемент А йде раніше елемента Б, якщо значення рядка елемента А менше значення рядка елемента Б, або при їх рівності значення А менше значення Б. таким чином всі рядки матриці будуть впорядковані по зростанню.

 

2) для кожного рядка підраховуємо, яку кількість елементів він містить

 

3) заведемо змінну sum = 0

 

4) для кожного рядка, будемо пробігати зліва направо, і для кожного елемента

обраховувати, який елемент він утворить у перетвореній матриці, що рівний

добутку елемента на кількість ненульових елементів, тобто

int tmp_val = (data[cur].val - sum) * (row_cnt[i] - j);

якщо він утворить ненульовий елемент, то записуєм його в рядок і змінюємо значення суми:

sum += (data[cur].val - sum);

 

5) R = кількості утворених ненульових елементів + L

6) m = максимальній кількості ненульових елементів в нових рядках.

 

Приклад операції (на матриці):

 

 

 

сортуємо, рахуємо кількість елементів в рядках і тд:

2 2 8

2 4 5

1 3 19

 

в кожному рядку виконуємо пункт 4:

 

 

значення R зменшиться на одиницю

 

 

 

 

Операція S:

1) L = L + 1

 

2) В масиві даних, починаючи з L до R невключно, для кожного елемента до значення колонки додаємо значення рядка – 1 (індексація з 0). таким чином ми зсуваємо i-тий рядок на і клітинок вправо. на нових місцях утворюються нулі, тому ми не звертаємо на них увагу.

 

3) В масиві даних, починаючи з L до R невключно, знаходимо максимальне значення колонки і присвоюємо m цьому значенню.

 

 

 

АЛГОРИТМ

класифікації зображень на основі підрахованих масивів хвостових елементів на CPU

 

1) використовуємо наступні формули і розраховуємо

 

 

де

- сума хвостових елементів еталона

,  - сума k-того рядка початкової матриці, хвостові елементи класифікуємого зображення

 

2)  розраховуємо коефіцієнт відхилення від еталону