РОЗДІЛ 2
ПАРАЛЕЛЬНЕ ПЕРЕТВОРЕННЯ МАСИВІВ ДАНИХ
ЗА МЕТОДОМ РІЗНИЦЕВИХ ЗРІЗІВ
2.1 Основні положення перетворення векторних масивів
Нехай інформація представлена у вигляді числової матриці розмірністю елементів
і матриці вагових коефіцієнтів тієї ж розмірності. Якщо притримуватись,
наприклад, порядку обходу елементів матриці по рядках, то можна отримати деякий
вектор відповідно з кількістю елементів. Розглянемо векторну операцію типу , де
- скалярний операнд. Прикладом такої операції являється процес підсумовування
числових величин, які є координатами вектора . Але оскільки при виконанні
операції із вектора отримується скаляр, то дану операцію називають операцією
згортки векторів [90]. Також слід наголосити, що процес отримання кінцевого
результату будемо вважати, на відміну від [104], де розглядається операція
додавання чисел (причому з плаваючою комою), процесом підсумовування елементів
вектора відповідної розмірності. При цьому елементи вектора є додатними і
відмінними один від одного.
Нехай - початковий векторний масив (або вектор) ненульових числових даних,
елементи якого відмінні один від одного. За аналогією з [123] визначимо
перетворення вектора для процесу одновимірної згортки векторів.
Означення 1. Перетворенням вектора для процесу одновимірної згортки елементів
векторів називається кортеж чотирьох величин
P=(U, Q, M, C), де U - набір елементарних символів та символів, які не
являються примітивами, Q - множина арифметичних операцій типу , M – множина
матриць типу вектор-стовпець або вектор-рядок, C – математичний апарат базових
векторно-матричних операцій [44].
В цьому контексті алгоритмічну модель по аналогії з [123] можна визначити таким
чином.
Означення 2. Алгоритмічною моделлю лінійної згортки елементів векторів
називається математичний опис обчислювального процесу, який дозволяє в зручній
формі описати алгоритмічну структуру, властивості та відношення між
функціональними модулями даного процесу [44].
Оскільки розглядається перетворення саме векторних масивів даних (надалі,
просто векторних масивів), то є сенс розглядати таке перетворення в контексті
векторизації обчислювального процесу [104].
Означення 3. Векторизацією обчислювального процесу (алгоритму) називається його
представлення в такій формі, яка дозволяє виконувати одночасну обробку всіх
елементів вхідного вектора даних.
Математичний апарат С, до складу якого входять основні операції
векторно-матричної алгебри, дозволяє представити обчислювальні процеси, що
реалізуються при розв’язуванні задач обробки сигналів та зображень, в найбільш
зручній та компактній формі. Так, наприклад, при одночасній обробці двох
зображень відбувається операція додавання двох матриць, при “посиленні” сигналу
– множення вектора на скаляр [90]. При цьому представлення векторизованих
обчислювальних процесів у вигляді векторно-матричних обчислювальних процедур
може мати як самостійне значення при реалізації задач обробки сигналів та
зображень, так і бути зручним інструментом формалізованого синтезу різних за
призначенням і складності засобів цієї обробки [36,123].
Оскільки процес підсумовування елементів векторного масиву будемо розглядати в
контексті багатооперандної обробки, то для зручності опису такого процесу
наведемо наступне означення.
Означення 4. Мультипідсумовуванням назвемо паралельний процес багатооперандного
(багатомісного) підсумовування елементів векторного масиву відповідної
розмірності [61].
Оскільки перетворення будуть базуватись на формуванні різницевих зрізів, то за
аналогією з [29] наведемо більш коректне визначення для різницевого зрізу.
Означення 5. Нехай – початковий вектор ненульових елементів ai,0 розмірності ;
– проміжні вектори з елементами ai,j (). Тоді вектор назвемо різницевим зрізом
(РЗ) j – ої позиції при умові, що являє собою різницю між елементами
попереднього вектора та мінімальною складовою того ж вектора, яку будемо
розглядати в якості внутрішнього порогового елемента [61]. При цьому під
методом різницевого зрізу (МРЗ), що застосовується в процесі оброблення масиву
, будемо розуміти метод, який використовує наведений в роботі [29] принцип
різницевих зрізів.
Означення 6. Прямим перетворенням векторних масивів назвемо процес
мультипідсумовування елементів цих масивів, які містять числових величин.
В процесі доведення тверджень в подальшому використовуються такі поняття, як
маска і, зокрема, бінарна маска. Наведемо означення цих понять [149].
Означення 7. Маска - це комбінація знаків, які використовуються для аналізу
чисел такого ж, як і маска, формату шляхом зіставлення відповідних знаків маски
та розрядів чисел. В широкому розумінні в області розпізнавання зображень
маскою називається набір величин, які утворюють вектор, що множиться скалярно
на інший вектор, який є результатом дискретизації зображення, для обчислення
величини, що характеризує їх схожість.
Означення 8. Бінарна маска - це маска, елементами якої є числа у двійковому
представленні (0 та 1).
Розглянемо елементи деякої довільної множини, яка представляє собою
одновимірний масив даних, який можна розглядати як засіб оперування групою
даних, зокрема, векторних.
Означення 9. Послідовність елементів , розташованих в порядку зростання (або
спадання) їх значень будемо називати відсортованою послідовністю.
Означення 10. Кільцем назвемо одновимірний масив із замкненими кінцями, тобто
масив, в якому кінці відсутні. При цьому процес переходу від довільного
векторного масиву даних до кільця будемо розглядати як процес замикання даного
масиву.
2.2 Розпаралелювання процесу мультипідсумовування елементів векторного масиву
Розглянемо обґр
- Київ+380960830922