[PASCAL] Stack Overflow Error e Ricorsione

[leadergl]

Ragazzi ho un problema, ho scritto un algoritmo ricorsivo per il calcolo della COMPONENTE CONNESSA di una immagine.

I Pixel di questa immagine sono memorizzati in un Array bidimensionale, quindi la Componente Connessa viene calcolata a partire da un pixel dell'immagine (k quindi sarebbe un elemento dell'array).

Questo è l'algoritmo:

{Procedure per il Calcolo della Componente Connessa}
procedure CalcolaCC(Riga,Colonna,PixelIniziale,s,ToniMax:integer; VAR i,j:integer);
var	new_i, new_j:integer;

begin


    {Verifica se gli indici individuano ancora una locazione della matrice}
    If ((i<=Riga) And (j<=Colonna)) And ((i>0) And (j>0)) Then
    begin
        {Verifica se il pixel appartiene alla componente connessa}
        If (Dati[i, j] - PixelIniziale) < s Then
        begin
            {Modifica della matrice che individuer… la componente connessa}
            DatiAppoggio[i,j]:=1;

	    {Modifica del valore della matrice per far modo che la ricorsione non sia infinita}
            Dati[i,j]:=2*ToniMax;

            {Autoattivazione ("destra","sotto", "sinistra", "sopra")}
            new_j:=j+1;
            CalcolaCC(Riga, Colonna, PixelIniziale, s, ToniMax, i, new_j);
            new_i:=i+1;
            CalcolaCC(Riga, Colonna, PixelIniziale, s, ToniMax, new_i, j);
            new_j:=j-1;
            CalcolaCC(Riga, Colonna, PixelIniziale, s, ToniMax, i, new_j);
            new_i:=i-1;
            CalcolaCC(Riga, Colonna, PixelIniziale, s, ToniMax, new_i, j);
        End;
    End;

end;

Come posso risolvere i problemi di stack overflow?

[71104]

Originariamente inviato da leadergl

Come posso risolvere i problemi di stack overflow?

questo è un problema sul quale a volte rifletto, e ancora non ho trovato la soluzione
allora, secondo me devi trasformare l'algoritmo ricorsivo in iterativo, quindi vuol dire che partendo da un pixel devi (ad esempio) trovare tutti quelli della componente connessa nella sua stessa scanline; poi se il pixel che gli sta sopra fa parte anch'esso della stessa componente, sali di una scanline e cerchi tutti i pixel della scanline superiore; vai avanti fino a che non trovi un pixel diverso e fai la stessa cosa di sotto. il problema di questo algoritmo è che funziona solo coi poligoni convessi e con pochi casi di poligoni concavi.
un approccio alternativo potrebbe essere quello di cercare tutti i pixel nell'immagine che potrebbero far parte della tua componente e poi cercare di capire quali sono quelli della componente che contiene il pixel indicato, ma mi sembra più difficile.

[71104]

ecco qua, mi è venuta una mezza idea: ti descrivo quello che dovresti fare andando verso l'alto, ma poi devi fare lo stesso scendendo verso il basso.
allora, hai il tuo pixel che sta nella tua scanline; del pixel te ne freghi, cerchi subito l'inizio di quella scanline (a partire dal primo pixel della componente), dopodiché la analizzi un pixel alla volta: per ogni pixel fai una ulteriore iterazione verso l'alto e quindi controlli pure quelli della stessa colonna; è chiaro dunque che parte delle scanlines superiori le avrai già analizzate in questo modo, perciò quando sali ne devi tenere conto: non devi salire semplicemente alla scanline superiore, ma a quella dove la componente si allarga (o a destra o a sinistra), perché se si allarga vuol dire che ci sono dei pixel laterali che non hai avuto la possibilità di analizzare.
dunque passi all'analisi di questa nuova scanline, che però non è necessario analizzare completamente: la maggior parte l'hai già fatta, quindi ogni volta che sali in questo modo devi tenerti in qualche variabile gli indici delle colonne che hai sicuramente già analizzato.
per i pixel rimanenti l'analisi avviene nello stesso modo della scanline inferiore: per ciascuno fai anche una iterazione verso l'alto finché non tocchi un bordo della componente.
poi continui a salire e così via.
volendo migliorare l'algoritmo si potrebbero unire le due analisi verticali: ogni volta che analizzi una colonna corrispondente a un pixel, cerchi direttamente il margine superiore e la analizzi verso il basso (oppure il contrario).

[71104]

un ulteriore possibile approccio potrebbe essere quello di "camminare lungo il bordo" della componente: se ad es. il tuo scopo è quello di modificare tutti i pixel di una certa componente (come accade nell'esempio che hai mostrato in Pascal), prima devi trovare un modo per camminare sul bordo esterno, e ad ogni pixel che "calpesti" () gli cambi valore; poi passi al bordo più interno, e cammini pure su quello, e continui a restringere il bordo finché non finisci (cioè finché non riesci più a trovare un bordo i cui pixel non siano stati ancora cambiati).

siccome questa cosa mi interessa molto, oggi se ho tempo farò qualche prova.

ciao

[leadergl]

uhm...alcune domande forse banali ma per me utili...:

Cosa è una "ScanLine"?

Inoltre ho notato che il mio algoritmo (k in C/C++, in VB ed in Delphi funziona bene) non va in Stack Overflow se invece delle 4 chiamate ricorsive per volta gliene faccio fare 3, in pratica se abolisco una sola di queste:

           {Autoattivazione ("destra","sotto", "sinistra", "sopra")}
            new_j:=j+1;
            CalcolaCC(Riga, Colonna, PixelIniziale, s, ToniMax, i, new_j);
            new_i:=i+1;
            CalcolaCC(Riga, Colonna, PixelIniziale, s, ToniMax, new_i, j);
            new_j:=j-1;
            CalcolaCC(Riga, Colonna, PixelIniziale, s, ToniMax, i, new_j);
            new_i:=i-1;
            CalcolaCC(Riga, Colonna, PixelIniziale, s, ToniMax, new_i, j);

tutto funziona a meraviglia...ovvio che poi non mi calcola la Componente Connessa Completa...

però questo mi ha dato un'idea...ovvero che potrei far richiamare questa procedura ricorsiva da una iterativa aumentando di una il numero delle variabili passate e che questa serva a selezionare quali ricorsioni attivare...esempio:

procedure CalcolaCC(RAMO,Riga,Colonna,PixelIniziale,s,ToniMax:integer; VAR i,j:integer);
...
if RAMO=1 then
begin
           {Autoattivazione ("destra","sotto", "sinistra", "sopra")}
            new_j:=j+1;
            CalcolaCC(1,Riga, Colonna, PixelIniziale, s, ToniMax, i, new_j);
            new_i:=i+1;
            CalcolaCC(1,Riga, Colonna, PixelIniziale, s, ToniMax, new_i, j);
end else 
begin
            new_j:=j-1;
            CalcolaCC(2,Riga, Colonna, PixelIniziale, s, ToniMax, i, new_j);
            new_i:=i-1;
            CalcolaCC(2,Riga, Colonna, PixelIniziale, s, ToniMax, new_i, j);
end;

in modo che gli faccio calcolare tutto in due tronconi distinti...
ed il tutto sarebbe richiamato da una procedura normale tipo:

Procedura SperiamoCheVa;
begin
           CalcolaCC(1,.....);
           CalcolaCC(2,.....);
end;

che dici può funzionare?
so che lato codice è bruttissimo...

cmq la tua idea mi sembra più "Professional" e quindi mi piace...ma mi devi spiegare un po più nel dettaglio che intendi fare...magari anche con qualche piccolo esempio...

[leadergl]

no...ho scoperto che la situazione seppur migliora non va...ci sono alcune zone particolari dove non calcola la componente connessa...

inoltre ho notato un piccolo problema, k nn riguarda la CC, abbastanza strano..si verifica quando salvo l'immagine creata tramite la CC...mi manca l'ultima riga della matrice...il bello è che la funzione è la stessa che uso per salvare l'immagine prodotta dalla funzione che calcola il negativo dell'immagine...e questo lo salva bene...vabbè problema secondario...


ritorniamo alla CC...

[71104]

per "scanline" intendo semplicemente una intera riga nella matrice contenente l'immagine; tu hai un pixel, che risiede in una certa scanline: l'idea è quella di analizzare la scanline partendo dall'inizio (cioè cercando il margine sinistro della componente in quella scanline) fino alla fine (cioè fino al margine destro); per ogni pixel fai l'analisi anche in verticale (cioè cerchi i margini superiore e inferiore della componente in quella colonna) e poi quando sali (o scendi) alla scanline successiva fai lo stesso per le colonne che non hai ancora analizzato (per sapere quali colonne non hai analizzato devi tenerti i range che hai analizzato in un array). adesso spero sia più chiaro, cmq domani se ci riesco faccio le mie prove
ciao

[leadergl]

ti ringrazio...aspetto tue notizie

[71104]

Originariamente inviato da leadergl

ti ringrazio...aspetto tue notizie

mie notizie: non ti affidare a me perché di fare ste prove non c'ho tempo in questi giorni; il poco tempo che ho da dedicare al computer lo vorrei usare per altri programmi che mi interessano, quindi mi sa che ste prove prima che le faccio sarà Natale 2007
quindi non aspettare me per quel lavoro, specie se hai una scadenza, se è per l'università o per il lavoro.

ciao

[leadergl]

Originariamente inviato da 71104

per "scanline" intendo semplicemente una intera riga nella matrice contenente l'immagine; tu hai un pixel, che risiede in una certa scanline: l'idea è quella di analizzare la scanline partendo dall'inizio (cioè cercando il margine sinistro della componente in quella scanline) fino alla fine (cioè fino al margine destro); per ogni pixel fai l'analisi anche in verticale (cioè cerchi i margini superiore e inferiore della componente in quella colonna) e poi quando sali (o scendi) alla scanline successiva fai lo stesso per le colonne che non hai ancora analizzato (per sapere quali colonne non hai analizzato devi tenerti i range che hai analizzato in un array). adesso spero sia più chiaro, cmq domani se ci riesco faccio le mie prove
ciao

il fatto è che non è detto che tutti i pixel di una determinata scanline appartengano alla componente connessa...quando trovo uno di questi che non appartiene che faccio? mi fermo?

inoltre l'algoritmo che ti ho passato in effetti fa questo...prende un pixel e ne analizza tutta la colonna e la riga in cui si trova...

mi si sta incasinando il cervello...

[71104]

Originariamente inviato da leadergl

il fatto è che non è detto che tutti i pixel di una determinata scanline appartengano alla componente connessa...quando trovo uno di questi che non appartiene che faccio? mi fermo?

certo che si: lascia perdere il pixel, tu quando parti all'inizio vai immediatamente tutto a sinistra ad es. (oppure tutto a destra) finché non trovi il margine sinistro (o destro) della componente in quella scanline; trovato il margine inizi a fare l'analisi vera e propria: fai una iterazione che procede verso l'altro margine in quella scanline (ad es. il destro) e analizzi pixel per pixel: per ogni pixel analizzi anche tutta la colonna: cerchi il margine superiore e quello inferiore della componente in quella colonna. poi quando hai finito quella scanline sali sopra, e continui a salire di una scanline finché non ne trovi una in cui la componente si allarga, cioè in cui il margine sinistro si trova più a sinistra o il destro più a destra (volendo generalizzare, dovremmo dire che ne devi cercare una che contiene della ranges orizzontali che non hai analizzato); dunque analizzi la scanline che hai trovato e vai avanti finché non riesci più a salire, e poi la stessa cosa la fai di sotto.

inoltre l'algoritmo che ti ho passato in effetti fa questo...prende un pixel e ne analizza tutta la colonna e la riga in cui si trova...

si ma:
1) manca l'idea delle ranges
2) è ricorsivo e sputtana lo stack
la mia idea invece è completamente iterativa

[leadergl]

vediamo se ho capito bene...

Allora io ho la matrice e come punto di partenza dell'utente ho il punto (3,5) che vale ad esempio 255.

Ora non tenendo in considerazione quel punto, ma solo il suo valore contenuto, parto dal punto (1,1) e:

1) analizzo in pratica l'intera colonna (scendendo verso il basso...quindi (1+x,1)) o almeno finchè non trovo un valore che non rientra nella componente connessa.
2) mi memorizzo le coordinate di partenza e di arrivo, in questo caso (1,1) e (x,y)
3) procedo col punto (1,2), quindi mi sposto di una colonna a destra, ed analizzao tutta la colonna (scendendo verso il basso...quindi (1+x,2)) finchè non finisce la colonna o non trovo un valore che non rientra nella componente connessa.

e ripeto sempre questo MA

se ad esempio al punto 3 vedo che invece di scorrere fino al punto (x,y) sono andato fino a (x,y+1) allora da qui comincerò a prendere come punto di partenza (x+1,y+1) ovvero il punto di lato a destra e faccio sempre il procedimento del punto 2 e 3.

una cosa del genere?

P.S. continuo a ringraziarti per la pazienza...

[71104]

Originariamente inviato da leadergl

vediamo se ho capito bene...

Allora io ho la matrice e come punto di partenza dell'utente ho il punto (3,5) che vale ad esempio 255.

Ora non tenendo in considerazione quel punto, ma solo il suo valore contenuto, parto dal punto (1,1) e:

no! mi sono spiegato male
non devi partire da (1, 1): piuttosto, nella scanline che ha index 5 devi cercare il margine sinistro della componente ed effettuare l'analisi fino al margine destro. quando dicevo "te ne freghi del punto" intendevo dire che te ne freghi della coordinata X, in questo caso 3 ^^
mi ero spiegato male io

1) analizzo in pratica l'intera colonna (scendendo verso il basso...quindi (1+x,1)) o almeno finchè non trovo un valore che non rientra nella componente connessa.

ok, ma ricordati di fare lo stesso anche verso l'alto.

2) mi memorizzo le coordinate di partenza e di arrivo, in questo caso (1,1) e (x,y)

si, in pratica ti crei un array di ranges, e quando hai fatto la prima scanline ci metti il primo range che hai fatto, che però non è (1, 1)-(x, y), ma in questo caso (x0, 5)-(x1, 5); e tieni ben presente che a mano a mano che vai avanti con le scanlines, le ranges potrebbero aumentare: pensa ad esempio al caso in cui la componente è una "ciambella", cioè è un cerchio e ha un buco al centro: supponiamo di partire dalla prima scanline in alto; inizialmente hai una sola range, piuttosto piccola; scendendo verso il basso la componente si allarga (e la range con essa), e quando arrivi a toccare il buco (eddai, cosa vai a pensare!! ) dovrai aggiungere un'altra range all'array, perché da quel punto in poi le scanlines si dividono in due parti e si riuniscono più in basso.

3) procedo col punto (1,2), quindi mi sposto di una colonna a destra, ed analizzao tutta la colonna (scendendo verso il basso...quindi (1+x,2)) finchè non finisce la colonna o non trovo un valore che non rientra nella componente connessa.

vabbè, qui non è così perché mi ero spiegato male prima, ma spero che adesso hai capirai.

e ripeto sempre questo MA

se ad esempio al punto 3 vedo che invece di scorrere fino al punto (x,y) sono andato fino a (x,y+1) allora da qui comincerò a prendere come punto di partenza (x+1,y+1) ovvero il punto di lato a destra e faccio sempre il procedimento del punto 2 e 3.

qui mi sono perso perché non ho letto il punto precedente, che mi sembrava sbagliato ^^

una cosa del genere?

P.S. continuo a ringraziarti per la pazienza...

ma guarda, a dire il vero interesserebbe molto anche a me fare questa prova, solo che si tratta di una cosa che richiede un po' di tempo.

[71104]

dimenticavo: una volta che hai realizzato l'algoritmo, per metterlo alla prova prova a vedere come va con un caso estremo: la componente connessa a forma di SPIRALE!!!!
se riesci a colorare una spirale penso proprio che ce l'hai fatta
o addirittura una spirale che a un certo punto si divide e torna indietro, perché no?

[leadergl]

Originariamente inviato da 71104

dimenticavo: una volta che hai realizzato l'algoritmo, per metterlo alla prova prova a vedere come va con un caso estremo: la componente connessa a forma di SPIRALE!!!!
se riesci a colorare una spirale penso proprio che ce l'hai fatta
o addirittura una spirale che a un certo punto si divide e torna indietro, perché no?

eh...se lo riesco a realizzare :P è un casino...

[leadergl]

niente...mi serve uno spunto...non riesco a fare il concetto mio ed a realizzare un algoritmo...

mi hai dato miliardi di informazioni lo so....e mi sento un po idiota a nn riuscire a concretizzare...ma mi sto esaurendo...


P.S. ho sistemato alcune cose nel resto del progetto ed in DevPascal funziona tutto bene, in FreePascal non so perchè si blocca la procedura di lettura del file, mentre in TP7 mi da sempre stack overflow nel calcolo della CC...bah tre compilatori e 3 risultati differenti

ho una settimana ancora......mi serve aiuto...

[leadergl]

...non mi abbandonate...help....