[C] Problema matrici

[fabiett1]

Salve a tutti! Sto cercando di svolgere in modo migliore questo programma, in quanto il metodo che sto usando mi pare eccessivamente lungo e laborioso: svolgo prima i calcoli per la parte centrale dell'immagine (matrice imm) e poi passo ai singoli casi (bordo sinistro, bordo destro, borso superiore, bordo infeirore). Potete aiutarmi?
Di seguito trovate il testo dell'esercizio e il mio codice (non finito).

ESERCIZIO
[...]L’operazione di convoluzione prende in ingresso due matrici di numeri interi. La prima è l'immagine da filtrare,
la seconda il kernel che definisce il tipo di filtro. Il filtro esamina ogni pixel dell'immagine e il risultato del
filtraggio si ottiene in questo modo: per prima cosa si "sovrappone" il kernel alla matrice immagine in modo che
il centro del kernel sia in corrispondenza del pixel da elaborare. Quindi, il valore del pixel filtrato si ottiene come
la somma dei prodotti di ciascun elemento della matrice kernel con il corrispondente pixel della matrice
immagine sottostante. Per i pixel sul bordo dell'immagine, dal momento che non tutti gli 8 pixel vicini sono
effettivamente contenuti nell'immagine, si assume che i pixel mancanti abbiano valore 0. Quindi, dato un pixel
di coordinate (x,y), se le coordinate di uno dei suoi vicini cascano fuori dall'immagine si considera il valore 0
nella somma (si vedano gli esempi per chiarimenti).[...]


CODICE:

void progrKernel(int imm[][C], int ker[][DIM_K])
{
    int i, j, k, z, risultato = 0;

    //PARTE CENTRALE
    for(i = 1; i < R - 1; i ++)  //R sono le righe della matrice immagine (7)
        for(j = 1; j < C - 1; j ++) //C sono le colonne della matrice immagine (10)
        {
            risultato = 0;
            for(k = 0; k < DIM_K; k ++)  //DIM_K è la grandezza della matrice quadrata kernel (3)
                for(z = 0; z < DIM_K; z ++)
                {
                    risultato += imm[i - 1 + k][j - 1 + z] * ker[k][z];
                    if(k == 2 && z == 2)
                        imm[i][j] = risultato;
                        risultato = 0;
                }
        }


    //LATO SINISTRO
    if((i - 1) < 0 && (j - 1) < 0) //mi trovo nell'angolo in alto a sinistra
    {
        for(i = 0; i < 2; i ++)
            for(j = 0; j < 2; j ++)
                for(k = 1; k < DIM_K; k ++)
                    for(z = 1; z < DIM_K; z ++)
                        risultato += imm[i][j] * ker[k][z]
    }
    //mi trovo nella parte centrale del lato sinistro
    for(i = 0; i < 2; i ++)
            for(j = 0; j < 2; j ++)
                for(k = 1; k < DIM_K; k ++)
                    for(z = 1; z < DIM_K; z ++)
                        risultato += imm[i][j] * ker[k][z]

    return;
}

[Super Squirrel]

Magari potresti aggiungere alla matrice imm una cornice di 0 e poi usare la sola parte di codice che tu hai chiamato PARTE CENTRALE.

[fabiett1]

Grazie! Ottimo!

[vict85]

Sul miglior modo per gestire questo tipo di cose non saprei dirtelo con certezza, ma so per certo che quel codice restituisce il risultato sbagliato.

Il problema è che hai bisogno della riga superiore alla riga su cui stai lavorando attualmente, ma tu hai già sovrascritto la riga superiore con il risultato finale. Quindi o scrivi il risultato su un'altra matrice oppure ti devi tenere memorizzato da qualche parte la vecchia riga. Lo stesso problema si ha con il risultato calcolato subito prima. Spero di essermi spiegato.

P.S.: Siccome quel filtro è separabile, il modo più efficiente per calcolare quella convoluzione consiste nell'usare la separabilità.

[fabiett1]

Hai perfettamente ragione. Ho provato a modificarlo utilizzando un'altra matrice dove salvare i risultati ma non funziona ancora . Allego il codice integrale:

#include <stdio.h>
#include <stdlib.h>

#define R 9
#define C 12
#define DIM_K 3

void leggiFile(int imm[][C], int ker[][DIM_K], char* immagine, char* kernel);
void progrKernel(int imm[][C], int ker[][DIM_K], int immCod[][C - 2]);


void leggiFile(int imm[][C], int ker[][DIM_K], char* immagine, char* kernel)
{
    int i, j;
    FILE *fp;

    //APERTURA FILE E CONTROLLO
    fp = fopen(immagine,"r");
    if(fp == NULL)
    {
        printf("ERRORE FILE!\n");
        exit(-2);
    }
    //LETTURA IMMAGINE DA FILE
    for(i = 1; i < R - 1; i ++)
        for(j = 1; j < C - 1; j ++)
            fscanf(fp, "%d  ", &imm[i][j]);
    fclose(fp);

    //INSERISCO ZERI SU BORDO SUP E INF
    i = 0;
    for(j = 0; j < C; j ++)
        imm[i][j] = 0;
    i = R - 1;
    for(j = 0; j < C; j ++)
        imm[i][j] = 0;
    //INSERISO ZERI SU LATO DX E SX
    j = 0;
    for(i = 0; i < R; i ++)
        imm[i][j] = 0;
    j = C - 1;
    for(i = 0; i < R - 1; i ++)
        imm[i][j] = 0;


    //APERTURA FILE E CONTROLLO
    fp = fopen(kernel,"r");
    if(fp == NULL)
    {
        printf("ERRORE FILE!\n");
        exit(-3);
    }
    //LETTURA KERNEL DA FILE
    for(i = 0; i < DIM_K; i ++)
        for(j = 0; j < DIM_K; j ++)
            fscanf(fp, "%d  ", &ker[i][j]);
    fclose(fp);


    return;
}


void progrKernel(int imm[][C], int ker[][DIM_K], int immCod[][C - 2])
{
    int i, j, k, z, risultato = 0;

    for(i = 1; i < R - 2; i ++)
        for(j = 1; j < C - 2; j ++)
        {
            for(k = 0; k < DIM_K; k ++)
                for(z = 0; z < DIM_K; z ++)
                {
                    risultato += imm[i - 1 + k][j - 1 + z] * ker[k][z];
                    if(k == 2 && z == 2)
                    {
                        immCod[i - 1][j - 1] = risultato;
                        risultato = 0;
                    }
                }
        }

    return;
}


int main(int argc, char* argv[])
{
    int imm[R][C], ker[DIM_K][DIM_K], immCod[R - 2][C - 2];
    int i, j;


    //CONTROLLO LINEA DI COMANDO
    if(argc != 3)
    {
        printf("ERRORE LINEA DI COMANDO!\n");
        return -1;
    }

    leggiFile(imm, ker, argv[1], argv[2]);

    progrKernel(imm,ker,immCod);

    for(i = 0; i < R - 2; i++)
    {
        for(j = 0; j < C - 2; j ++)
        {
            printf("%d ",immCod[i][j]);
        }
        printf("\n\n");
    }

    return 0;
}

[apatriarca]

E' abbastanza raro calcolare il valore di una convoluzione in-place. E' possibile ma è una inutile complicazione. Soprattutto quando si lavora su più di una dimensione. Come già detto da @vict85, il metodo migliore in questo caso consiste nel sfruttare il fatto che il filtro è separabile. In particolare può essere scritto come il prodotto tra \([1; 0; -1]\) e \([1, 0, -1]\) (dove ho usato la convenzione di Matlab di usare ';' per separare le righe e ',' per le colonne). Puoi quindi applicare i due filtri in passaggi successivi sulla stessa immagine risparmiando parecchi calcoli. L'effettivo vantaggio dipende dalla dimensione del filtro. Per un filtro di dimensione \(P\times Q\) e una immagine di dimensione \(M \times N,\) sfruttando la separabilità si ottiene un tempo proporzionale a \(M\,N,(P+Q)\) invece di \(M\,N\,P\,Q.\) Nel caso di un filtro \(3 \times 3\) si ha quindi un tempo di calcolo potenzialmente uguale a \( 2/3 \) del precedente. Con filtri molto più grandi (per esempio \(9 \times 9\)) questo vantaggio diventa molto più grande (\( 2/9 \approx 0.22 \)). La convoluzione con filtro di dimensione \(1\) è inoltre molto più semplice da parallelizzare perché in questo caso ogni riga o colonna (a seconda di come è fatto il filtro) sono tra di loro indipendenti. Anche eventuali implementazione in-place sono più facili.

Venendo al tuo codice. Non capisco perché hai dichiarato tutte le variabili ad inizio della funzione, non è più necessario. Inoltre è più facile ragionare sul comportamento di un pezzo di codice se il numero di variabili è in qualche modo minimo. La variabile risultato in particolare va a mio parere dichiarata e inizializzata a zero all'interno del secondo ciclo. Il codice dentro l'if più interno va invece spostato dopo i due cicli più interni. La condizione dell'if è infatti del tutto equivalente a chiedersi se i due cicli sono all'ultima iterazione. Per preferenza personale aggiungerei poi le parentesi graffe ad ogni ciclo. E' una cosa molto semplice da fare, ed è troppo semplice commettere errori. Scriverei poi tutte le dimensioni delle matrici e non solo quelle necessarie negli argomenti della funzione. Ho infine modificato gli intervalli di i e j perché ogni volta che usavi tali variabili sottraevi uno.. Alla fine di questi suggerimenti la funzione progKernel diventerebbe la seguente:

void progrKernel(int imm[R][C], int ker[DIM_K][DIM_K], int immCod[R-2][C-2])
{
    for (int i = 0; i < R - 2; i++) {
        for (int j = 0; j < C - 2; j++) {
            int risultato = 0;

            for (int k = 0; k < DIM_K; k++) {
                for (int z = 0; z < DIM_K; z++) {
                    risultato += imm[i + k][j + z] * ker[k][z];
                }
            }

            immCod[i][j] = risultato;
        }
    }
}