Спосіб класифікації образів

Спосіб класифікації образів, в якому виконують множення кожного елемента вхідного векторного масиву даних (образу) на відповідні вагові коефіцієнти вагової матриці, формують векторні масиви зважених елементів, який C2 1 3 80562 виділення об'єкта на зображенні і не може бути застосований для класифікації образів. Найбільш близьким за технічною суттю є спосіб класифікації образів [Распознавание биоэлектрических сигналов. Зарубежная радиоэлектроника, 1996, №12, с. 50, рис.2], в якому виконують множення кожного елемента вхідного векторного масиву даних (образу) на відповідні вагові коефіцієнти вагової матриці, формують векторні масиви зважених елементів, підсумовують зважені елементи у кожному векторному масиві з формуванням сум зважених елементів, які відповідають конкретним класам розпізнавання образів, порівнюють отримані суми між собою для визначення максимальної за величиною суми серед тих, що є ознакою належності вхідного векторного масиву даних (образу) до відповідного класу образів. Недоліком цього способу є звужена область застосування через неможливість використання його для сортування отриманих сум елементів векторних масивів зважених даних. В основу винаходу поставлена задача створення способу класифікації образів, в якому за рахунок введення нових дій досягається можливість порівняння однойменних елементів в усі х масивах зважених даних із визначенням і вилученням найменшого (ненульового) серед них і наступної транспозиції елементів у кожному масиві зважених даних до послідовного формування масивів з нульовими елементами, причому останній масив з ненульовими елементами є масивом з максимальною сумою його елементів, що дозволяє розширити область застосування цього способу за рахунок можливості виконання не тільки класифікації образів у вигляді векторних масивів даних, але й сортування векторних масивів зважених елементів за сумою цих елементів, що може бути використано в подальшому для кластерізації образів. Поставлена задача вирішується тим, що у способі класифікації образів, в якому виконують множення кожного елемента вхідного векторного масиву даних (образу) на відповідні вагові коефіцієнти вагової матриці, формують векторні масиви зважених елементів, в подальшому визначають мінімальний елемент серед однойменних елементів всіх векторних масивів зважених елементів, формують різницеві зрізи шляхом віднімання значення мінімального елемента від однойменних елементів всіх векторних масивів зважених елементів, виконують транспозицію нульових елементів у кожному векторному масиві зважених елементів праворуч, перевіряють умову отримання векторного масиву зважених елементів, всі елементи якого мають нульові значення, що є ознакою наявності мінімальної суми елементів відповідного векторного масиву зважених елементів серед оброблюваних векторних масивів, далі послідовність вищезазначених операцій повторюють до отримання векторного масиву зважених ненульових елементів, який є останнім серед оброблюваних векторних масивів, що є 4 ознакою належності вхідного векторного масиву даних (образу) до відповідного класу образів. На кресленні зображена блок-схема пристрою, який реалізує спосіб класифікацій образів. Пристрій, що реалізує даний спосіб класифікації образів, містить помножувач 1, на входи 2j ( j = 1 n ) якого подають значення , елементів вхідного векторного масиву даних Z (nвимірного образу), а на входи 3ij ( i = 1, m ) відповідні вагові коефіцієнти wij (які утворюють вагову матрицю W розмірністю m x n). Виходи 4ij помножувача 1 з'єднані з входами 5ij матриці 6 обчислювальних комірок, виходи j-х комірок кожного i-го рядку якої з'єднані з входами i-го елемента 7i групи елементів АБО-НІ 71,...,7m, ви хід якого є виходом 8i ознаки наявності мінімальної суми елементів i-гo масиву зважених елементів ( i = 1, m ) і з'єднаний з входами заборони обчислювальних комірок і-го рядку матриці 6. Група виходів 81,...,8m, ознаки підключена до першої групи входів вузла 9, який містить лічильник 10 і m-вхідний елемент АБО, входи якого з'єднані з першою групою входів вузла 9, а вихід підключений до входу зворотної лічби лічильника 10, інформаційні входи якого з'єднані з другою гр упою входів 121,...,12р вузла 9 (p = log 2m), вхід скиду з'єднаний з настановним входом 13 пристрою, а його вихід ознаки нуля є виходом 14 вузла 9, який є виходом сигналу "Кінець" пристрою. Класифікацію образів виконують таким чином. Спочатку встановлюють у нульовий стан лічильник 10 вузла 9 за сигналом на настановному вході 13 пристрою. При поданні на входи 2j. ( j = 1 n ) , помножувача 1 вхідного векторного масиву Z = (z1 ,...,zj,...,zn), (1) а на його входи 3ij ( i = 1, m ) матриці вагових коефіцієнтів æ w 1,1... w 1,n ö ç ÷ . ç ÷ ç ÷ . ç ÷ ç . ÷ ç ÷ w i,1... w i, n ÷ (2) W= ç ç ÷ . ç ÷ . ç ÷ ç ÷ . ç ÷ ç w m,1... w m,n ÷ è ø він виконує векторно-матричне перетворення. В результаті на його виходах 4ij формують векторні масиви зважених елементів виду: ( ) A 0 = a 01... a 0j ...a 0n , i i, i, i, (3) які записують у відповідні обчислювальні комірки матриці 6 по її входах 5ij. Одночасно у лічильник 10 вузла 9 записують величину (m-1), яку подають у двійковому коді по входах 121...,12р вузла 9 (р = log2 m). 5 80562 елемент. Відповідно, в кожному рядку може бути один, декілька, всі або не бути взагалі нульових елементів. Перевіряють умову наявності m -1 нульових рядків, тобто: Сукупність векторних масивів A0 у матриці б i обчислювальних комірок подають у вигляді двовимірної матриці розміром m x n: æ a 0 a 0 ... a 0 ... a 0 ö æ 0 ö ç 1,1 1,2 1j , 1n , ÷ ç A1 ÷ ç a 0 a 0 ... a 0 ... a 0 ÷ ç A 2 ÷ 2, j 1,n ÷ ç 2,1 2,2 ç ÷ ç ÷ ç . ÷ . ç ÷ ç ÷ . ç ÷ ç . ÷ ç ÷ ç . ÷ . A0 = ç ÷ = ç 0 . ÷, 0 0 0 0 ç a i,1 a i,2 ... a i, j ... a i,n ÷ ç A i ÷ ç ÷ ç . ÷ . ç ÷ ç ÷ ç ÷ ç . ÷ . ç ÷ ç ÷ . ç ÷ ç . ÷ 0 ç a 0 a 0 ... a 0 ... a 0 ,n ÷ ç Am ÷ m ø è ø m, j è m,1 m,2 t t -1 (4) min t -1 a ). В результаті, i i,l формують вектор-рядок з n мінелементів вигляду: Потім виконують кожного мінелемента паралельне mintj-1 (5) віднімання ( j = 1 n ) від кожного і, го елемента відповідного j-стовпця матриці Аt-1 і A0 k t формують невпорядковану матрицю чисел A , яка має вигляд: æ a t-1 - min t-1 a t-1 - min t-1 ... a t-1 - min t-1 ... a t-1 - min t -1 n ç 1,1 1 1,2 2 1,j j 1,n ç . ç . ç ç . tç t- 1 t- 1 t- 1 t- 1 t- 1 t -1 t- 1 t -1 A ç ai,1 - min1 ai,2 - min 2 ... ai ,j - min j ... a i,n - min n ç . ç ç . ç . ç ç a t -1 - mint -1 a t -1 - mint -1 ... a t -1 - min t-1 ... a t -1 - mint -1 m,n n m,1 1 m,2 2 m ,j j è або æ a t a t ... a t ... a t ö ç 1,1 1, 2 1, j 1,n ÷ ç ÷ . ç ÷ . ç ÷ ç ÷ . ç ÷ t t t t t A = ç a i,1 a i, 2 ... a i, j ... a i,n ÷ ç ÷ . ç ÷ ç ÷ . ç ÷ . ç ÷ t t t ç t ÷ ç am,1 am, 2 ... a m, j ... a m,n ÷ è ø Де t ai, j = ait,-1 - mint -1 . j j t t (9) æ a t at ... a t ... a t ö ç 1,1 1, 2 1, j 1,n ÷ ç ÷ . ç ÷ . ç ÷ ç ÷ . ç ÷ t t t t t A = ç ai,1 a i, 2 ... a i, j ... ai,n ÷ (10) ç ÷ . ç ÷ ç ÷ . ç ÷ . ç ÷ t çat ç m,1 am, 2 ... a t , j ... a t ,n ÷ m ÷ m è ø Далі для отриманої матриці Аt повторюють цикли оброблення, які складаються з вищезазначеної послідовності операцій. У деякому циклі t у двовимірній матриці Аt з'являється деякий рядок k з усіма нульовими елементами. Цей рядок вказує на k-й масив чисел ( (mintj -1 = t t Min t -1 = (min 1-1, min 2-1,... min tj -1,... min t -1 ). n t Якщо умова (9) виконується, то оброблення закінчують, у протилежному випадку виконують наступні дії. Для всіх рядків матриці паралельно виконують транспозицію елементів з просуванням праворуч усі х нульових елементів і формують впорядковану матрицю Аt, яка має вигляд: (t= 1 N) виконують визначення найменшого , елемента t A 1 = A i-1 = A i+1 = ...A m = 0, Ai ¹ 0, t = 1,N де A0 - і-й рядок матриці А0. i Ітераційний процес оброблення матриці А° у матриці 6 обчислювальних комірок має такий вигляд. Спочатку для кожного стовпця матриці A 6 ( k = 1 m ), , який є мінімальним серед початкових масивів A0 , A0, ..., A 0 тобто: m 1 2 ö ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ø æ a t at ... a t ... a t ö ç 1,1 12 , 1,j 1n ÷ , ç ÷ . ç ÷ . ç ÷ ç ÷ . ç ÷ t t t ç ak ,1 a k,2 ... a k ,j ... a t ,n ÷ k 0 At = ç ÷ мінімальний масив A к , . ç ÷ ç ÷ . ç t t ÷ t t ç ai,1 ai,2 ... a i, j ... a i,n ÷ ç . ÷ ç ÷ ç a t ,1 at ,2 ... a t ,j ... at,n ÷ m m m i ø è (6) (11) де a t , j = 0, j = 1 n. , k (7) (8) Після виконання таких дій в кожному стовпці отриманої матриці A t є хоча б один нульовий Цей нульовий рядок в подальшому обробленні участі не приймає і значення його елементів не беруть до уваги при визначенні мінелементів кожного стовпця матриці, тобто: 7 80562 æ a t at ... a t ... a t ö ç 1,1 1,2 1, j 1,n ÷ ç ÷ . ç ÷ . ç ÷ ç ÷ ç ÷ - - ... - ... - . t ç t A = ç a a t ... a t ... a t ÷ (12) i,1 i, 2 i, j i,n ÷ ç ÷ . ç ÷ ç ÷ . ç ÷ . ç ÷ ç at at , 2 ... a t , j ... at,n ÷ m i ø è m,1 m Кожний наступний нульовий рядок, який з'явиться у двовимірній матриці Аt, вказує на набір чисел, який є мінімальним серед тих масивів (відповідних рядків), які ще приймають участь в обробленні. Такий нульовий рядок також виключають і оброблення продовжують над тими рядками, які ще мають ненульові елементи. Оброблення двовимірної матриці триває до тих пір, поки не виконається умова (9) наявності m-1 нульових рядків. Тобто, поки не залишиться один єдиний рядок, якій буде містити хоча б один ненульовий елемент, а решта рядків будуть виключені з оброблення як нульові. Матриця у цьому циклі (t = N) буде мати вигляд: AN æ ç ç ç ç ç ç = ç aN ç l,1 ç ç ç ç ç è - - ... - ... ö ÷ . ÷ . ÷ ÷ - - ... - ... ÷ . ÷ aN ... a Nj ... aN ÷ l,2 l, l,n ÷ . ÷ ÷ . ÷ ÷ . ÷ - - ... - ... ø (13) де серед a N є щонайменше один ненульовий l, j елемент, тобто $ a Nj ¹ 0. Цей рядок вказує на l, деякий l-й масив чисел A0 (l Î 1 m ) , який є , l максимальним серед початкових масивів чисел A0 , A 0 ,..., A0 . Величина N дорівнює кількості m 1 2 циклів оброблення, виконаних в процесі пошуку максимального масиву чисел серед масивів A0 , A 0 ,..., A0 . m 1 2 Всі дії, що виконують послідовно у кожному циклі, реалізують у матриці 6 обчислювальних t комірок. Виконання умови A i = 0 фіксують наявністю одиничного сигналу на виході i-го елемента АБО-НІ 7; у групі елементів АБО-НІ 71...,7 m. Цей же сигнал, поданий на вхід заборони обчислювальних комірок i-го рядка матриці 6, ініціює виключення змісту цих комірок з подальшого оброблення. Одночасно всі сигнали з виходів гр упи елементів АБО-НІ 71..., 7 m, подають на входи елемента АБО 11 вузла 9 і формують одиничний сигнал на його виході тільки у разі 8 наявності одиничного сигналу хоча б на одному виході гр упи елементів АБО-НІ 71,..., 7 m, тобто при обнуленні відповідного рядка у матриці 6 обчислювальних комірок. Одиничний сигнал з виходу елемента АБО 11 вузла 9 подають на вхід зворотної лічби лічильника 10 вузла, що викликає зменшення на одиницю його вмісту. Це відбувається до тих пір, поки вміст лічильника не стане нульовим, тобто буде виконуватись умова (9). В результаті з'явиться одиничний сигнал на його виході ознаки нуля, а отже, на виході 14 вузла 9, який є виходом сигналу "Кінець" пристрою. Розглянемо приклад реалізації класифікації і сортування векторних масивів чисел. Нехай маємо чотири ( i = 1,4 ) масиви чисел A0 по чотири ( j = 14 ) числа a 0j в кожному, тобто , i, i 0 A 1 = (14 9 6 3), 0 A 2 = (10 21 8 2), 0 A 3 = (24 18 30 11), A 0 = (23 10 10 22), 4 які складають початкову двовимірну матрицю: æ 14 9 6 3 ö ç ÷ ç 10 21 8 2 ÷ A0 = ç ÷. ç 24 18 30 11÷ ç 23 10 10 22÷ è ø Цикли оброблення цієї матриці представлено у вигляді таблиці 1. Загальний час Т класифікації і сортування векторних масивів чисел розраховують таким чином: T0 = N. Tц = N.(T min+Ts ub+Ttr) = N .((m-1).tcom + m tsub+ t tr ), де Тц - час виконання циклу оброблення; Тmin ,Тsub,Т tr, - час визначення мінімального значення, віднімання у стовпцях і транспозиції у рядках матриці A t -1 (t = 1 N) відповідно; tcom,tsub, , ttr, - час порівняння, віднімання і транспозиції двох чисел відповідно. У випадку, якщо t com ~ ts ub ~ ttr =t,формула (14) має вигляд: T0 = 2mtN (15) Мінімальна кількість циклів, яка необхідна для визначення максимального масиву чисел, складає: Nmin = m-1 (16) Формула (16) виконується за умови, що елементи кожного вектор-стовпця матриці А0 відсортовані в одному напрямку (або всі за збільшенням, або всі за зменшенням). Тобто: 0 a 1, j > a 0, j > ... > a 0j > ... > a 0 , j 2 i, m або 0 a 1, j < a 0, j < ... < a 0j < ... < a 0 , j 2 i, m Тоді, підставивши (16) у (15), розраховують мінімальний час визначення максимального масиву чисел: min T0 = 2m × (m - 1) × t = 2 × (m 2 - m ) × t. (17) 9 80562 10 Але за умови послідовного виконання у межах кожного стовпця матриці A t -1 (t = 1 N) віднімання мінелементів , min , а також суміщення виконання віднімання мінелементів і транспозиції нульових елементів, що передбачає вираз (14), можлива організація конвеєрного оброблення значень матриці А0, що дозволить майже вдвічі скоротити цей процес, а саме: t-1 3/3 æ - -- -ö ç ÷ ç - - - -÷ A3 = ç ÷ ç 2 7 24 9÷ ç 1 3 20 0 ÷ è ø Формування впорядкованої матриці (транспозиція елем нульових елементів праворуч). 4/1 Міn3 = (1 3 20 0) Формування рядка мінелементів (пошу min - - - T0 = (m - 1) × t com + (m × t sub + t tr ) × N min = æ ö æ - - - -ö (18) ç ÷ ç ÷ 2 - - - 4 ç ÷ ç - - - -÷ = (m - 1) × t + (m + 1)( m - 1) × t = (m + m - 2 ) × t. A =ç =ç ÷ ÷ мінімальний ç 2 - 1 7 - 3 24 - 20 9 ÷ ç 1 4 4 9 ÷ ç 1- 1 3 - 3 20 - 20 Таблиця01 0 0 ÷ 0 ÷ ç0 è ø è ø Формування невпорядкованої матриці (віднімання міне Цикл/ Результат (числова матриця або вектор) і коментар Отримано наступний нульовий рядок двовимірної матр Операція 0 0 1/1 Міn = (10 9 6 2) Формування рядка мінелементів (пошук найменшогомінімальним серед масивів A0 , A 0 . Цей ряд чисел A4 є елемента стовпця) 4 3 æ 14 - 10 9 - 9 6 - 6 3 - 2 ö æ 4 0 0 1 ö оброблення. ç ÷ ç ÷ В подальшому немає необхідності виконувати зсув н уль 1 ç 10 - 10 21 - 9 8 - 6 2 - 2 ÷ ç 0 12 2 04/2 ÷ A =ç = залишився лише один рядок з ненульовими елементам 1/2 24 - 10 18 - 9 30 - 6 11 - 2 ÷ ç 14 9 24 9÷ ç ÷ ç ÷ ç 23 - 10 10 - 9 10 - 6 22 - 2÷ ç 13 1 4 20 ÷ æ--- -ö è ø è ø ç ÷ ç у - - - ÷ стовпці матриці). Формування невпорядкованої матриці (віднімання мінелементів - кожномуМАКСИ МУМ A0 4 A =ç ÷ 3 æ 4 1 0 0 ö ç14 4 9÷ ç ÷ ç- ---÷ è ø ç 12 2 0 0 ÷ A1 = ç 14 9 24 9÷ Цей рядок вказує на те, що масив чисел A0 є максима 1/3 ç ÷ 3 ç 13 1 4 20 ÷ Кількість циклів оброблення, виконаних в процесі пошук è ø максимуму, дорівнює 4. Формування впорядкованої матриці (транспозиція елементів у рядках з просуванням нульових елементів праворуч). 2/1 Міn1 = (4 1 0 0) Формування рядка мінелементів (пошук найменшого елемента стовпця). æ 4 - 4 1-1 0 0 ö æ 0 0 0 0 ö ç ÷ ç ÷ ç 12 - 4 2 - 1 0 0 ÷ ç 8 1 0 0 ÷ 0 A2 = ç =ç ÷ ÷ мінімальний масив A1 ç 14 - 4 9 - 1 24 9÷ ç 10 8 24 9÷ ç 13 - 4 4 20 ÷ ç 9 0 4 20 ÷ è ø è ø 2/2 Формування невпорядкованої матриці (віднімання мінелементів у кожному стовпці матриці). Отримано перший нульовий рядок двовимірної матриці, який вказує на те, що масив чисел A0 є мінімальним серед масивів A0 , A0 , A0 , A 0 . Цей рядок виключають з подальшого 4 1 1 2 3 оброблення. 2/3 3/1 3/2 æ -- - - ö ç ÷ ç 8 1 0 0 ÷ 2 A =ç ÷ ç 10 8 24 9 ÷ ç 9 4 20 0 ÷ è ø Формування впорядкованої матриці (транспозиція елементів у рядках з просуванням нульових елементів праворуч). Міn2 = (8 1 0 0) Формування рядка мінелементів (пошук найменшого елемента стовпця). - - - æ ö æ- - - -ö ç ÷ ç ÷ 0 3 ç 8 - 8 1-1 0 0 ÷ ç 8 1 0 0 ÷ A =ç ÷ = ç 2 7 24 9 ÷ мінімальний масив A2 ç 10 - 8 8 - 1 24 9 ÷ ç ÷ ç 9 - 8 4 - 1 20 0 ÷ ç1 3 20 0÷ è ø è ø Формування невпорядкованої матриці (віднімання мінелементів у кожному стовпці матриці). Отримано наступний нульовий рядок двовимірної матриці. Цей рядок вказує на те, що масив 0 чисел A2 є мінімальним серед масивів A0 , A0 , A0 . . Цей рядок виключають з подальшого 4 2 3 оброблення.