Newsgroup: it.comp.lang.c
Titolo: AIUTO PROBLEMA DI MEMORIA!

pt0pt2 é un programma che legge un file di testo .pt0 così strutturato:
1) prima linea: numero di punti (pixels) che compongono il contorno di una
cella nuvolosa (ad es. m punti)
2) successive m linee: lista delle coordinate dei punti che compongono il
contorno
3) ultima linea: flag di contatto della cella nuvolosa con il bordo della
matrice immagine (0=non tocca il bordo, 1=tocca il bordo)
Questo programma serve a "lisciare" il contorno della cella nuvolosa: esso
elimina  il numero o la percentuale di punti del contorno che viene fornita
come parametro da linea di comando dall'utente, prende come riferimento un
punto per volta ed elimina i punti "troppo vicini", calcolando anche una
funzione peso. Il risultato della decimazione viene scritto in un file .pt2
così strutturato:
1) prima linea: numero di punti superstiti (ad es. mr)
2) seconda linea: coordinate del baricentro della cella nuvolosa
3) successive mr linee: lista delle coordinate dei punti superstiti riferite
al baricentro
Questo programma era stato scritto per lavorare con immagini di 160x160
pixels, io lavoro con immagini di 640x480 pixels ed ho problemi di
allocazione della memoria (il programma si blocca quando deve allocare float
** dist (mxm) matrice delle distanze di tutti i punti). La soluzione sarebbe
quella di considerare un numero inferiore ad m come punti su cui calcolare
la matrice delle distanze (con una mia immagine ho m=52000!), ad es. m=100
(anche 10 sarebbero sufficienti, tanto l'esponenziale usato per calcolare i
pesi decresce rapidamente). Ciò significa considerare solo i 100 punti piu
vicini al punto considerato , e non tutti gli m punti. In questo modo
snellisco di molto la computazione delle distanze e dei pesi da dare ai vari
punti ( i punti piu vicini al punto corrente hanno pesi maggiori di quelli
piu lontani, secondo un andamento esponenziale). Ovviamente non basta
troncare tutti i cicli for a 100 o 10 (considerando solo 100 o 10 punti non
c'é piu corrispondenza tra gli indici!).
Qualcuno di voi mi potrebbe aiutare a modificare il codice in modo da
raggiungere questo scopo?.
Qui di seguito vi listo il programma "vecchio" , scusandomi per il lungo
post.
Ringrazio chiunque mi voglia aiutare , ciao, Luca.
/* pt0pt2.c
*
*  Programma che converte un file .pt0 in un .pt2
* Accetta nomi di files di ingresso e di uscita
* con estensioni qualsiasi. La presente versione 2
* e' un tentativo di rendere automatica la generazione
*  del II nome di file a partire dal I.
*
* Accetta (e necessita) dalla riga di comando
* l'indicazione sul numero o sulla percentuale di punti
* che devono sopravvivere alla decimazione.
*
* Questa versione legge i .pt0 con formato modificato:
* -non legge piu' il flag di contatto col bordo;
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "all_matr.c" /* accessorio per allocare matrici */
#define MAXLUNGNOMI 90
main(int argc, char **argv)
{
char *nomefilein;  /* nome del file d'ingresso */
char *nomefileout;  /* nome del file d'uscita */
char *nomeelenco;  /* nome del file elenco listapt2 */
char *nome;   /* var. ausiliaria */
char *numero,*stringa;  /* var. ausiliarie per mem. III argom. */
char *punt;  /* puntatore per operazioni su stringhe */
float *x,*y; /* coordinate dei punti della figura */
float *x1,*y1; /* coordinate dei punti della figura riferite al baric. */
float *x2,*y2; /* coordinate dei punti della figura con assi ruotati */
float perc; /* percentuale di punti da conservare */
float **dist; /* matrice delle distanze tra i punti */
double *mdist; /* media dist. 2 pti piu' vicini */
double dist_min; /* dist. min. = passo griglia pixel */
int nearest;  /* indice punto piu'vicino al corrente */
int qn;  /* indice II punto piu' vicino al corrente */
double sigmaq;  /* varianza della gauss. di pesatura */
double *pesi; /* pesi dei punti nella media */
double totpesi; /* somma dei pesi, per loro normalizz. */
int punti_da_segare; /* quanti punti devo eliminare */
float xbar,ybar; /* coord. baricentro */
double temp;  /* var. temp. */
int i,j,k;  /* indici */
int m;  /* n. punti nel file origine */
int mr;  /* n. punti dopo la riduzione */
FILE *fp;  /* puntatore al file */
 /* alloco memoria per i nomi */
nomefilein = (char *) calloc( MAXLUNGNOMI, sizeof (char) );
nomefileout = (char *) calloc( MAXLUNGNOMI, sizeof (char) );
nomeelenco = (char *) calloc( MAXLUNGNOMI, sizeof (char) );
nome = (char *) calloc( MAXLUNGNOMI, sizeof (char) );
 /* alloco memoria per variabili ausiliarie */
numero = (char *) calloc( 10, sizeof (char) );
stringa = (char *) calloc( 10, sizeof (char) );
 /* controllo che il numero di argomenti sia corretto */
if (argc!=4)
{
 fprintf(stderr,"\n Uso di %s:\n",argv[0]);
 fprintf(stderr,"\n %s filein.est fileout.est|= nps|pps\n",argv[0]);
 fprintf(stderr," filein.est :  file di ingresso, compresa estensione\n");
 fprintf(stderr," fileout.est :  file di uscita, oppure\n");
 fprintf(stderr," = : nome fileout=nomefilein con est. cambiata in .pt2\n");
 fprintf(stderr," nps :  numero punti superstiti, oppure\n");
 fprintf(stderr," pps :  percentuale punti superstiti\n\n");
 for (i=0; i<argc; fprintf(stderr," %s\n",argv[i++]) );
 exit(EXIT_FAILURE);
}
 /* genero il nome del file d'ingresso */
strcpy(nomefilein,argv[1]);
if ( (fp=fopen(nomefilein,"r"))==NULL )
{
 fprintf(stderr,"\n\n Problemi di apertura del file origine
%s\n\n",nomefilein);
 exit(EXIT_FAILURE);
}
if ( fscanf(fp,"%d",&m)<=0 )
{
 printf("\n\n Problemi in lett. del n. di punti dal file %s\n\n",nome);
 exit(EXIT_FAILURE);
}
 /* alloco memoria per le coordinate */
x = (float *) calloc( m+1, sizeof (float) );
y = (float *) calloc( m+1, sizeof (float) );
x1 = (float *) calloc( m+1, sizeof (float) );
y1 = (float *) calloc( m+1, sizeof (float) );
x2 = (float *) calloc( m+1, sizeof (float) );
y2 = (float *) calloc( m+1, sizeof (float) );
 /* alloco memoria per le medie delle distanze */
if ( (mdist = (double *) calloc( m+1, sizeof (double) )) == NULL )
 {
  printf("\n\nImpossibile Allocare Memoria! ('mdist')\n\n");
  exit(EXIT_FAILURE);
 }
 /* alloco memoria per i pesi */
if ( (pesi = (double *) calloc( m+1, sizeof (double) )) == NULL )
 {
  printf("\n\nImpossibile Allocare Memoria! ('pesi')\n\n");
  exit(EXIT_FAILURE);
 }
 /* alloco memoria per la matrice distanze */
if(( dist = (float **) AllocIm ( m+1, m+1 , sizeof( float ) ) ) == NULL)
 {
  printf("\n\nImpossibile Allocare Memoria! ('dist')\n\n");
  exit(EXIT_FAILURE);
 }
for (i=0; i<m; ++i)
{
 if (fscanf(fp,"%f %f",&x[i],&y[i])<=0)
 {
  fprintf(stderr,"\n\n Probl. in lett. del dato n. %d dal file
%s\n\n",i,nome);
  exit(EXIT_FAILURE);
 }
}
fclose(fp);
 /* stabilisco il numero di punti da eliminare */
strcpy(numero,argv[3]);
printf("\n Sto elaborando.\n\n");
i=strlen(numero);
if (strchr(numero,'%')!=NULL)
{
 strncpy(stringa, numero, i-1);
 perc = atof(stringa);
 perc /= (float) 100;
        punti_da_segare = floor( (1-perc) *  m );
}
else
{
 punti_da_segare = m - atof(numero);
}
 /* controllo che il numero di punti da eliminare sia accettabile */
if ( punti_da_segare<0 )
{
 punti_da_segare=0; /* cioe' lascia le cose come sono */
}
if ( punti_da_segare>=m )
{
 fprintf(stderr,"\n\n Risulta un numero eccessivo ( %d)
\n",punti_da_segare);
 fprintf(stderr," di punti da eliminare\n\n");
 exit(EXIT_FAILURE);
}
 /* calcolo coordinate baricentro */
xbar=ybar=0;
for (i=0; i<m; ++i)
{
 xbar += x[i];
 ybar += y[i];
}
xbar /= (float) m;
ybar /= (float) m;
 /* porto nel baricentro l'origine degli assi */
for (i=0; i<m; ++i)
{
 x[i] -= xbar;
 y[i] -= ybar;
}
for (i=0; i<m; ++i)  /* calcolo matrice distanze tra i punti */
 for (j=i; j<m; ++j)
  dist[i][j]=dist[j][i]=sqrt( (x[i]-x[j]) * (x[i]-x[j]) + (y[i]-y[j]) *
(y[i]-y[j]) );
dist_min=dist[0][1]; /* determino il passo della griglia di pixel */
for (i=0; i<(m-1); ++i)
{
 for (j=i+1; j<m; ++j)
 {
  if (dist[i][j]<dist_min)
   dist_min=dist[i][j];
 }
}
sigmaq=pow(dist_min,2);  /* varianza della funzione peso */
/* ciclo per mediare le posizioni dei punti */
for (i=0; i<m; ++i)
{
 /* calcolo i pesi */
 totpesi = 0;
 for (j=0; j<m; ++j)
  totpesi += (pesi[j]=exp(-dist[i][j]/sigmaq));
 /* li normalizzo a somma 1 */
 for (j=0; j<m; ++j)
  pesi[j] /= totpesi;
 /* calcolo la media */
 x1[i]=y1[i]=0;
 for (j=0; j<m; ++j)
 {
  x1[i] += x[j]*pesi[j];
  y1[i] += y[j]*pesi[j];
 }
}
for (i=0; i<m; x2[i]=x1[i],y2[i]=y1[i++]); /* copio le coord. sul terzo
vettore */
mr=m; /* all'inizio, n. punti ridotto = n. punti orig. */
for (k=0; k<punti_da_segare; ++k) /* ciclo per eliminazione punti */
{
 for (i=0; i<mr; ++i)  /* calcolo media dist. 2 pti piu' vicini */
 {
  nearest=( i==mr-1 ? 0 : i+1); /* per evitare di porre dist. min.= dist da
se' stesso */
  for (j=1; j<mr; ++j)
   if ( (dist[i][j]<dist[i][nearest]) && (i!=j) )
    nearest=j;
  qn=( i==mr-1 ? ( nearest ? 0 : 1 ) : ( nearest==i+1 ? ( i ? 0 : mr-1) :
i+1) );
  for (j=1; j<mr; ++j)
   if ( (dist[i][j]<dist[i][qn]) && (i!=j) && (j!=nearest) )
    qn=j;
  mdist[i]=(dist[i][nearest]+dist[i][qn])/2.0;
 }
 /* cerco il punto con i vicini piu' vicini */
 nearest=0;
 for (i=1; i<mr; ++i)
  if (mdist[i]<mdist[nearest])
   nearest=i;
 /* elimino il punto con i vicini piu' vicini */
 for (i=nearest; i<mr; x2[i]=x2[i+1],y2[i]=y2[i+1],++i);
 for (i=nearest; i<mr; ++i)
  for (j=0; j<mr; dist[i][j]=dist[i+1][j++]);
 for (i=nearest; i<mr; ++i)
  for (j=0; j<mr-1; dist[j][i]=dist[j++][i+1]);
 --mr;
}   /* FOR eliminazione punti */
 /* genero il nome del file d'uscita */
if ( strcmp(argv[2],"=") ) /* se il secondo argomento non e' "=" */
 strcpy((nomefileout),argv[2]); /* allora file uscita=secondo argomento */
else     /* altrimenti */
{
 strcpy(nomefileout,argv[1]); /* copia il nome del file d'ingresso */
 punt=strrchr(nomefileout,(int) '.'); /* trova l'inizio dell'estensione */
 if (punt!=NULL)   /* se esiste l'estensione */
  *punt='\0';  /* allora la taglia */
 strcat(nomefileout,".pt2"); /* aggiunge la nuova estensione */
}
/* scrivo su file i risultati */
if ( (fp=fopen(nomefileout,"w"))==NULL )
{
 fprintf(stderr,"\n\n Problemi di apertura del file destinazione
%s\n\n",nomefileout);
 exit(EXIT_FAILURE);
}
if (fprintf(fp,"%d\n",mr)<=0)
{
 fprintf(stderr," Errore in scrittura del numero\n");
 fprintf(stderr," di punti sul file: %s\n\n",nomefileout);
 exit(EXIT_FAILURE);
}
if (fprintf(fp,"%f ",xbar)<=0)
{
 fprintf(stderr," Errore in scrittura della coord. x\n");
 fprintf(stderr," del baricentro sul file: %s\n\n",nomefileout);
 exit(EXIT_FAILURE);
}
if (fprintf(fp,"%f\n",ybar)<=0)
{
 fprintf(stderr," Errore in scrittura della coord. y\n");
 fprintf(stderr," del baricentro sul file: %s\n\n",nomefileout);
 exit(EXIT_FAILURE);
}
for (i=0; i<mr; ++i)
{
 if (fprintf(fp,"%f %f\n",(float) x2[i],(float) y2[i])<=0)
 {
  fprintf(stderr," Errore in scrittura della coppia\n");
  fprintf(stderr," di coord. n. %d sul file %s\n\n",i,nomefileout);
  exit(EXIT_FAILURE);
 }
}
fclose(fp);
printf("\n File %s registrato.\n\n",nomefileout);
/* apro il file elenco dei .pt2 registrati*/
if ( (fp=fopen("listapt2","a"))==NULL )
{
 fprintf(stderr,"\n\n Problemi di apertura in scrittura\n");
 fprintf(stderr,"del file elenco listapt2.\n\n");
 exit(EXIT_FAILURE);
}
/* ora aggiorno l'elenco dei .pt2 */
strcpy(nome,nomefileout);
punt=strrchr(nome,(int) '.'); /* individua dove si trova l'estensione */
if (punt!=NULL)
 *punt='\0';  /* taglia l'estensione */
if (fprintf(fp,"%s\n",nome)<=0)
{
 fprintf(stderr," Errore in scrittura del nome ('%s')\n",nome);
 fprintf(stderr," del file risultato sul file elenco listapt2.\n\n");
	exit(EXIT_FAILURE);
}
printf("\n File listapt2 aggiornato.\n\n");
fclose(fp);
exit(0);
}

if(( dist = (float **) AllocIm ( m+1, m+1 , sizeof( float ) ) ) == NULL)
Non vorrei sbagliarmi ma l'allocazione non mi sembra corretta.
Nel caso il valore non fosse m+1 si allocherebbero molti piu' valori di quelli
richiesti.
Andrea Laforgia
----
I guai ve li andate a cercare : 
quando Bill Gates annuncio' che avrebbe fatto scrivere 
Windows98 a Topo Gigio perche' non gli avete creduto ?

richiesti.
L'allocazione é giusta : la funzione AllocIm si trova nel file "All_matr.c"
che viene incluso all'inizio del programma (questo file non l'ho postato per
non occupare troppo spazio). Inoltre il valore da allocare (se non é  m+1) é
sicuramente m (il che non cambia molto) , perche m é il numero di punti del
contorno della cella nuvolosa, le cui coordinate vengono lette dal file .pt0
che viene dato in pasto al programma.
Una cosa ritengo di ribadire : questo programma va benissimo cosi come é
(funziona perfettamente) , fintantoche i punti del contorno non superano un
certo valore (non so ancora quale sia). Siccome io non posso buttare via i
punti del contorno a casaccio, devo ottimizzare questo programma in modo che
anche con tanti punti non mi dia problemi di allocazione di memoria.
Grazie comunque per il suo interessamento ,signor Laforgia, ho potuto
apprezzare la sua competenza in altri messaggi apparsi in questo NG
(captatio benevolentiae...). Se avrà ancora il tempo e la voglia di
cimentarsi in questo problema potrò mandarle indicazioni ancora piu precise.
Luca.

Grazie comunque per il suo interessamento ,signor Laforgia, 
Figurati ! ma dammi del tu !


Figurati ! ma dammi del tu !
Volentieri!
Ciao e grazie.
Luca.

dimensione anche 3000 x 3000 (m x m) float!.
Vediamo se ho capito.
Supponiamo di dover trattare una matrice di 9 * 10^6 punti (3000x3000).
Il problema e' : come trovare, dato Xi, i 100 punti ad esso piu' vicino ?
Soluzione : analizzando le distanze di TUTTI i punti da Xi e cogliendo le prime
100 piu' piccole (o c'e' un metodo piu' veloce ?).
Ora, dato che la matrice delle distanze e' simmetrica, non serve memorizzare m *
m valori ma (m * m)/2, a cui va sottratto m se m e' dispari oppure m/2 se m e'
pari.
Difatti, con (m*m)/2 si considerano solo i valori della matrice triangolare
superiore (o quella inferiore) e con i valori sottratti si escludono quelli
della diagonale in quanto identicamente uguali a 0. 
A questo punto le distanze da analizzare da 9000000 si riducono a 4497000.
Pero', facendo un passo indietro, il problema piu' grosso e' come calcolare le
distanze di un punto da tutti gli altri !
Ho capito male ?
