[C] Array 2d best match

di il
7 risposte

[C] Array 2d best match

Salve,
ho un problema e vi illustro la situazione:
l'utente inserisce una matrice di dimensioni a sua scelta, essa viene popolata solo con zeri e uno.
successivamente genera un'altra matrice, di dimensioni inferiori, la quale sarà comunque riempita esclusivamente con zeri e uno.
Dovrei cercare la posizione della seconda matrice nella prima.

Esempio

1 0 0 1
0 0 1 1


0
0
Posizione 2 colonna 1 riga

Ho provato ad implementare un algoritmo di "best matching", ma con scarsi risultati, potreste aiutarmi?
Grazie in anticipo

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

void creaDati(int rigaImm, int colonnaImm, int rigaObj, int colonnaObj);

void bestMatching(int rigaImmagine, int colonnaImmagine, int immagine[rigaImmagine][colonnaImmagine], int rigaObj, int colonnaObj, int obj[rigaObj][colonnaObj]);
void stampaMatrice(int mx[][100], int col, int row, int rigaObj, int colonnaObj);
int punteggio_migliore(int a[][100], int b[][100], int col_cost, int row_cost, int iColx, int iRowx);

#define rigaMAX 100
#define colonnaMAX 100

int main()
{
    int i, o, rigaImm, colonnaImm, rigaObj, colonnaObj;

    srand(time(0));
    printf("Inserisci numero di righe immagine (MAX 100) : \n");
    scanf("%d", &rigaImm);
    printf("Inserisci numero di colonne immagine (MAX 100) : \n");
    scanf("%d", &colonnaImm);
    // creaImmagine(rigaImm, colonnaImm);

    printf("Inserisci riga oggetto : \n");
    scanf("%d", &rigaObj);
    printf("Inserisci colonna oggetto : \n");
    scanf("%d", &colonnaObj);

    creaDati(rigaImm, colonnaImm, rigaObj, colonnaObj);

    return 0;
}

void creaDati(int rigaImm, int colonnaImm, int rigaObj, int colonnaObj)

{
    srand(time(0));
    if ((rigaObj <= rigaImm) && (colonnaObj <= colonnaImm))
    {
        int iRigaImm, iColonnaImm, iRigaObj, iColonnaObj;

        int immagine[rigaImm][colonnaImm];
        int obj[rigaObj][colonnaObj];

        printf("Immagine : \n\n");

        for (iRigaImm = 0; iRigaImm < rigaImm; iRigaImm++)
        {
            for (iColonnaImm = 0; iColonnaImm < colonnaImm; iColonnaImm++)
            {
                immagine[rigaImm][colonnaImm] = rand() % 2;
                printf("%d ", immagine[rigaImm][colonnaImm]);
            }
            printf("\n");
        }

        printf("Oggetto : \n\n");

        for (iRigaObj = 0; iRigaObj < rigaObj; iRigaObj++)
        {
            for (iColonnaObj = 0; iColonnaObj < colonnaObj; iColonnaObj++)
            {
                obj[iRigaObj][iColonnaObj] = rand() % 2;
                printf("%d ", obj[iRigaObj][iColonnaObj]);
            }
            printf("\n");
        }

        bestMatching(rigaImm, colonnaImm, immagine, rigaObj, colonnaObj, obj);
    }
    else
    {
        printf("Inserisci un oggetto con dimensioni minore dell'immagine");
    }
}

void bestMatching(int rigaImmagine, int colonnaImmagine, int immagine[rigaImmagine][colonnaImmagine], int rigaObj, int colonnaObj, int obj[rigaObj][colonnaObj])
{

    int iCol, iRow, resultCol, resultRow, punteggioMax, punteggio;

    punteggioMax = 0;

    for (iRow = 0; iRow <= (colonnaImmagine - rigaObj); iRow++)
    {
        for (iCol = 0; iCol <= (rigaImmagine - colonnaObj); iCol++)
        {

            // punteggio = bestScoring(iCol, iRow, immagine, colonnaObj, rigaObj, obj);
            punteggio = punteggio_migliore(immagine, obj, colonnaObj, rigaObj, iCol, iRow);

            // punteggio =  punteggio_migliore (iCol ,iRow, immagine, rigaObj, colonnaObj, obj );
            if (punteggio > punteggioMax)
            {
                punteggioMax = punteggio;
                resultRow = iRow;
                resultCol = iCol;
                // printf("--------> iRow : %d iCol : %d ", iRow, iCol);
            }
        }
    }
    // printf("TEST %d\n\n", k);
    stampaMatrice(immagine, resultCol, resultRow, rigaObj, colonnaObj);
    printf("\nColonna : %d Riga : %d Numero coincidenze : %d\n\n", resultCol + 1, resultRow + 1, punteggioMax);
}

void stampaMatrice(int mx[][100], int col, int row, int rigaObj, int colonnaObj)
{
    printf("MATRICE RISULTATO :\n");
    printf("-------------------\n");
    for (int i = row; i < rigaObj + row; i++)
    {
        for (int j = col; j < colonnaObj + col; j++)
        {
            printf("%d ", mx[i][j]);
        }
        printf("\n");
    }
}

int punteggio_migliore(int a[][100], int b[][100], int col_cost, int row_cost, int iColx, int iRowx)
{
    int iC, iR, n_caratteri_uguali;
    n_caratteri_uguali = 0;

    for (iR = iRowx; iR < row_cost + iRowx; iR++)
    {
        for (iC = iColx; iC < col_cost + iColx; iC++)
        {
            // printf ("==== iR : %d   iC : %d   a : %d   b : %d  \n ",iR,iC,a[iR][iC],b[iR-iRowx][iC-iColx]);
            if (a[iR][iC] == b[iR - iRowx][iC - iColx])
            {
                n_caratteri_uguali++;
            }
        }
    }
    // printf("Punt : %d  iCol : %d  iRow : %d \n" , n_caratteri_uguali , iColx , iRowx);
    return n_caratteri_uguali;
}

7 Risposte

  • Re: [C] Array 2d best match

    Non si capisce bene perché tu debba implementare un algoritmo: non devi semplicemente cercare la prima sottomatrice con tutti gli elementi uguali che trovi? Perché poi dovrebbe essere rilevante il fatto che siano matrici di 1 e 0?
  • Re: [C] Array 2d best match

    Sì, dovrei trovare la prima sottomatrice che contiene più elementi uguali.
    La questione del modo in cui sono riempite entrambe le matrici è un dettaglio.
    Hai qualche consiglio?
  • Re: [C] Array 2d best match

    Più o meno qualcosa del genere
    
    int i, j, k, l, trovato = 0;
       for(i=0; i <= righe_A - righe_B; i++)
          for(j=0; j <= colonne_A - colonne_B; j++){
             trovato = 1;
             for(k=0; k < righe_B; k++)
                 for(l=0; l < colonne_B; l++)
                   if(A[i+k][j+l] != B[k][l])
                     trovato = 0;
             if(trovato)
                 goto fine;
          }
    fine:
     if(trovato){
        // i e j indicano la posizione
     }
    
  • Re: [C] Array 2d best match

    Questo per la sottomatrice uguale. Se invece non c'è quella uguale e vuoi quella con più elementi
    
    int i, j, k, l, trovato = 0;
    int C[righe_A - righe_B + 1, colonne_A - colonne_B + 1];
       for(i=0; i <= righe_A - righe_B; i++)
          for(j=0; j <= colonne_A - colonne_B; j++){
             trovato = righe_B * colonne_B;
             for(k=0; k < righe_B; k++)
                 for(l=0; l < colonne_B; l++)
                   if(A[i+k][j+l] != B[k][l])
                     trovato--;
             C[i][j] = trovato;
          }
    fine:
    // Trova gli indici corrispondenti al massimo di C
    
  • Re: [C] Array 2d best match

    Lo sto provando, i e j indicano la posizione?
    cosa dovrei fare in "fine"?
    Grazie mille
  • Re: [C] Array 2d best match

    
    #include <stdlib.h>
    #include <stdio.h>
    #include <time.h>
    
    #define righe_A    5
    #define colonne_A  8
    #define righe_B    2
    #define colonne_B  3
    
    int main(){
        int A[righe_A][colonne_A], B[righe_B][colonne_B];  
        int C[righe_A - righe_B + 1][colonne_A - colonne_B + 1];    
        int i, j, k, l, trovato;
        
        srand(time(0));
        // creazione A
        printf("Matrice A = \n");
        for(i=0; i < righe_A; i++){
            for(j=0; j < colonne_A; j++)
                printf("%d ", A[i][j] = rand() & 1);
            printf("\n");
        }
        printf("\n");
        // creazione B
        printf("Matrice B = \n");
        for(i=0; i < righe_B; i++){
            for(j=0; j < colonne_B; j++)
                printf("%d ", B[i][j] = rand() & 1);
            printf("\n");
        }
        printf("\n");
        // calcolo C         
        for(i=0; i <= righe_A - righe_B; i++)
            for(j=0; j <= colonne_A - colonne_B; j++){
                trovato = righe_B * colonne_B;
                for(k=0; k < righe_B; k++)
                    for(l=0; l < colonne_B; l++)
                      if(A[i+k][j+l] != B[k][l])
                        trovato--;
                C[i][j] = trovato;
            }
        // Trova gli indici corrispondenti al massimo di C
        trovato = -1;
        for(i=0; i <= righe_A - righe_B; i++)
            for(j=0; j <= colonne_A - colonne_B; j++)
                if(C[i][j] > trovato){
                   trovato = C[i][j];
                   k = i;
                   l = j;
                }
        // controllo posizione
        if(trovato == righe_B * colonne_B)
            printf("B e' una sotto-matrice di A alla posizione (%d,%d)\n", k+1, l+1);
        else
            printf("la sotto-matrice di A piu' simile a B e' alla posizione (%d,%d) ed ha %d occorrenze\n", k+1, l+1, trovato);       
        
        return 0;
    }
    
  • Re: [C] Array 2d best match

    Grazie mille
Devi accedere o registrarti per scrivere nel forum
7 risposte