Structure de donnée

Structure de donnée - C++ - Programmation

Marsh Posté le 23-02-2011 à 16:20:18    

Bonjour,
 
je dois stocker pour une image de taille inconnue au départ (cela varie suivant ce que l'utilisateur donne à manger au programme en gros 3500 * 2500 voir 5500 * 3500) un certain nombre de données (des indices de face 3D) de type

Code :
  1. int

par pixel ... mais je ne sais pas à l'avance combien pour chaque pixel ni même précisément le maximum de données par pixel (disons en gros 20

Code :
  1. int

stocké par pixel mais ca pourrait aller jusque 100 pour certains pixels)... ce qui est sur c'est que ce nombre varie pour chaque pixel de l'image...  
 
En gros je vaudrait stocker dans un tableau a deux dimensions des conteneurs de type

Code :
  1. std::vector<int>


 
Quelle solution serait la plus appropriée du point de vue C++ ?
 
Du fait de la compléxité du programme je ne m'était pas rendu compte que je stockait un objet de type :
 

Code :
  1. struct PseudoZData
  2. {
  3.     double dist;
  4.     uint pseudoface;
  6.     std::vector<int> listFace;
  8.     PseudoZData(){};
  9.     PseudoZData(double d, uint f):dist(d),pseudoface(f){};
  10. };


 
dans un tableau C
 

Code :
  1. protected:
  2. // tableau de pixels
  3. T *map;


 
via
 

Code :
  1. template<typename T>
  2.     bool BMP_BASE<T>::Alloc(uint in_width, uint in_height)
  3.     {
  4.         bool res = alloc(in_width, in_height);
  6.         Comp_Self_Parameters();
  7.         return res;
  8.     }


 
T etant ici mon PseudoZData
 
or cette version marche très souvent ... pour autant des comportements étranges sont observés quand on commence à avoir beaucoup de monde dans le std::vector<int> listFace ... j'en ai déduis peut être un soucis des que le std::vector dois modifier sa taille ...
 
je patauge un peu dans les modèles de données possible et je ne voudrais pas me tromper... merci de votre aide par avance.
 
David  

Reply

Marsh Posté le 23-02-2011 à 16:20:18   

Reply

Marsh Posté le 23-02-2011 à 16:23:38    

il manque la fonction qui fait vraiment l'allocation dans mon message ci dessus :
 

Code :
  1. //fonction privee d'allocation de memoire, la fonction n'initialise
  2. //pas de parametres de l'image autre que sa taille
  3. template<typename T>
  4.     bool BMP_BASE<T>::alloc(uint in_width, uint in_height)
  5.     {
  6.         if(in_width == 0 || in_height == 0)
  7.         {
  8.             if(map) delete [] map;
  10.             map = NULL;
  11.             iH.biWidth = iH.biHeight = 0;
  12.             return false;
  13.         }
  15.         //buffer deja alloue
  16.         if(map)
  17.         {
  18.             //taille identique
  19.             if(in_width == iH.biWidth && in_height == iH.biHeight) return true;
  20.             else delete [] map;
  21.         }
  22.         //buffer non encore alloue
  23.         iH.biWidth = in_width;
  24.         iH.biHeight = in_height;
  26.         try
  27.         {
  28.             map = new T[iH.biWidth*iH.biHeight];
  29.         }
  30.         catch (std::bad_alloc)
  31.         {
  32.             map = NULL; iH.biWidth = 0; iH.biHeight = 0;
  33.             return false;
  34.         }
  36.         return true;
  37.     }

Reply

Marsh Posté le 23-02-2011 à 18:13:39    

Et qu'est ce que tu entends pas comportement etrange?
 
Par ailleurs, tu n'as poste aucun code relatif au remplissage ou utilisation de listFace.

Reply

Marsh Posté le 23-02-2011 à 18:25:09    

Le comportement étrange c'est que quand j'ai un très important volume de données ... des images du genre 5500 x 3500 avec un remplissage important de mes std::vector<int>... eh bien les images en sortie du programme sont vides. Mais il n'y a pas de plantage du programme... il est content mais il me sort des trucs sans intérêt.
 
Alors que je n'ai pas de soucis avec des images plus petites 3500 x 2500...
 
pour le remplissage j'utilise des listFace.push_back(value);
 

Code :
  1. void PseudoZBuffer::PushFace (uint x, uint y, uint val)
  2.     {
  3.          if(x >= 0.0 && x < iH.biWidth && y >= 0.0 && y < iH.biHeight)
  4.          {
  5.               map[x+y*iH.biWidth].listFace.push_back(val);
  6.          }
  7.     }


 
et pour aller chercher la donnée je travail avec des iterateurs sur listFace
 

Reply

Marsh Posté le 23-02-2011 à 21:19:12    

C'est difficile de voir ou ca cloche ... Qu'entends tu par images vides?
 
Es tu sur qu'il n'y a pas de probleme de memoire (std::bad_alloc que tu catches dans ta fonction alloc) ?  
 
Si tu ne remplis pas les listFace, qu'est ce qu'il se passe?

Reply

Marsh Posté le 23-02-2011 à 21:26:16    

un tableau 2D de qualité passe par un poinetur de Iliffe.
Un exemple en C
 
http://codepad.org/K2WAwRBP
 
facilement transposable en C++ avec std::vector

Reply

Marsh Posté le 23-02-2011 à 23:22:24    

@ Joel F
 
je capte bien ton code mais mon problème n'est pas de faire un tableau 2D... enfin je veux dire j'ai une troisième dimension qui a une taille variable... et je peux pas la fixer même à une valeur haute (pour ne pas inutilement occupé trop d'espace mais aussi parce que je n'ai pas d'idée sur cette valeur a priori ca dépend de trop de paramètre que l'utilisateur va fixer) d'ou le std::vector<int> stocké via la structure PseudoZData dans mon tableau (1D pour moi mais finalement pas si loin du tiens dans les grandes lignes ... du C quoi)
 
enfin sauf si tu es sûr que stocker une structure tel que celle ci :  
 

Code :
  1. struct PseudoZData
  2.    {
  3.         double dist;
  4.         uint pseudoface;
  5.  
  6.         std::vector<int> listFace;
  7.  
  8.         PseudoZData(){};
  9.         PseudoZData(double d, uint f):dist(d),pseudoface(f){};
  10.    };


 
en lieu et place des float dans ton exemple , ne pose pas de soucis...  
 

Code :
  1. PseudoZData** alloc_array( int h, int w )
  2. {
  3.   int i;
  4.   /* Allocation des h pointeurs sur les debuts de lignes */
  5.   PseudoZData** m = (PseudoZData**)malloc(h*sizeof(PseudoZData*));
  6.   /* La premiere ligne pointe vers le debut de l'espace memoire contigu du tableau */
  7.   m[0] = (PseudoZData*)malloc(h*w*sizeof(PseudoZData));
  8.   /* Pre-calcul des debut de lignes 1 à h-1 */
  9.   for(i=1;i<h;i++) m[i] = m[i-1]+w;
  10.   return m;
  11. }


 
moi je me pose la question de savoir ce qui se passe quand le vecteur doit changer sa dimension (il arrive a saturation de l'espace initialement alloué)  je ne sais pas je me trompe peut être complètement !
 
 
@mr simon  
 
le logiciel calcul des orthophotographies, et a partir d'un certain volume de données (taille des photos en entrées et sortie, taille du maillage 3D) et bien il me sort bien une image mais qui n'a plus que la couleur du fond et plus du tout d'image rectifiée .... hors d'après mes investigation multiples dans mon code il semblerait que le PseudoZbuffer ne se calcul plus correctement passé une certaine taille ... le PseudoZbuffer qui est de type BMP_BASE<PseudoZbuffer> ...
 
je ne catch aucune erreur lorsque mon programme rend une feuille blanche !!
 
si je ne remplis pas les listFace alors je ne peux rien calculer c'est comme si je disais au programme que le modèle 3D était hors du champ de vision de l'image et donc il rend tres normalement une image vide dans ce cas.
 
moi je pense qu'il y a un sournois problème de mémoire  mais mes connaissances informatique touche ici leur limite !!!

Reply

Marsh Posté le 24-02-2011 à 07:18:30    

si tu remplace les malloc par des std vector et que tu ecris une fonction resize recursive qui va bien oui, je vois pas de probleme.

Reply

Marsh Posté le 24-02-2011 à 09:43:02    

Bon je crois qu'on se focalise trop sur mon code...
 
Moi je voudrais juste savoir comment vous structureriez vos données dans un cas comme le miens.
 
 
le prend un exemple qui n'a rien a voir :
 
On imagine une image image Bitmap de la France avec une taille de pixel que l'utilisateur peu fixer... suivant les cas on aura des pixel de 10m x 10m ou de 1000m x 1000m... ou n'importe quoi d'autre... c'est l'utilisateur qui choisit. Pour chacune des pixels on va vouloir stocker dans une structure les identités de tous les gens qui habite la ... genre struct identite {std::string Nom; int age;}; donc les pixels sur paname seront blindées de données alors que le plateau du larzac sera peinard ...  
 
comment vous veriez le stockage des identités dans ce cas la ; d'apres moi il faut bien une grille a la base ; tableau C ou boost::multi_array pour modeliser le bitmap et puis la dedans dans chque case des std::vector d'identité ...
 

Reply

Marsh Posté le 24-02-2011 à 12:42:43    

c'est pas nécessaire d'avoir unr grille, tu peux avoir une structure associative (map, hashmap, ...) qui, à un jeu de coordonnées associe tes identités


---------------
last.fm
Reply

Marsh Posté le 24-02-2011 à 12:42:43   

Reply

Marsh Posté le 24-02-2011 à 13:26:01    

tu veux dire  
 

Code :
  1. std::map<Coord, std::vector<Identite> >


 
avec
 

Code :
  1. struct Coord
  2. {
  3. int x;
  4. int y;
  5. };
  7. struct identite {
  8. std::string Nom;
  9. int age;};
  11. bool operator < (const Coord& a, const Coord& b)
  12. {
  13.      if (a.x < b.x) return true;
  14.      if (a.y == b.y)
  15.      {
  16.         if (a.y < b.y) return true;
  17.         if (a.y == b.y)
  18.         {
  19.             if (a.z < b.z) return true;
  20.             else return false;     
  21.         }
  22.         else return false;
  23.      }
  24.      else return false;
  25. }


 
est ce que cela est approprié pour des stockages important : image de 5500 x 3500 (et ca augmentera dans le temps et les nouveaux CCD)
et en moyenne 100 éléments dans les std::vector<> ?
 
 

Reply

Marsh Posté le 24-02-2011 à 13:27:15    

oups pas de .z dans le bool operator < ... copié collé un peu rapide

Reply

Marsh Posté le 24-02-2011 à 20:54:15    

je crois que je commence a voir le jour dans cette affaire.
 
Le problème essentiel dans ma structure de données réside dans le fait que mon image est stockée dans un tableau 1D... comme je fait un seul new il faut un très important espace contigu pour stocker mes données .... ce qui même sur ma machine à 8Go de RAM peut poser des problèmes.
 
Dites moi si je me trompe mais il me semble que si new int[80000000] renvoi un std::bad_alloc() ca ne veut pas dire que huit new int[10000000] successif ne pourrons pas se faire... dans un cas je dois avoir un espace contigu très important dans l'autre je le morcelle en 8 morceaux plus petits et donc il a plus de chance de passer.
 
Donc se rapproche du
 

Code :
  1. float** alloc_array( int h, int w )
  2. {
  3.   int i;
  4.   /* Allocation des h pointeurs sur les debuts de lignes */
  5.   float** m = (float**)malloc(h*sizeof(float*));
  6.   /* La premiere ligne pointe vers le debut de l'espace memoire contigu du tableau */
  7.   m[0] = (float*)malloc(h*w*sizeof(float));
  8.   /* Pre-calcul des debut de lignes 1 à h-1 */
  9.   for(i=1;i<h;i++) m[i] = m[i-1]+w;
  10.   return m;
  11. }


 
préconisé par Joel F
 
En regardant de prêt le moniteur de ressource j'ai remarqué que le programme lancait des std::bad_alloc() alors qu'il restait plus de 1.5Go de RAM libre... ce qui est plus important que ce dont le programme doit avoir besoin...
 
Maintenant si c'est bien ca c'est pas drôle car changé cela implique pas mal de réécriture puisqu'implementé dans une classe mère dont moulte autres derivent... c'est la vie ;)
 
Pour les comportements bizarre mr simon avait vu juste je ne gérait pas correctement mes blocs try catch et donc je ne voyait même pas que l'allocation ne s'était pas bien passée... comme par ailleurs mon code était bien sécurisé ca ne crashait pas :)
 
 

Reply

Marsh Posté le 24-02-2011 à 21:21:40    

non, un pointeur de iliffe reste un bloc de memoire contigue ...

Reply

Marsh Posté le 24-02-2011 à 21:38:08    

en effet j'avais mal lu ton code !!!
 
donc je ne m'inspire pas de cela puisque je veux subdiviser mon tableau ...
 
               

Code :
  1. stuff** tab;
  2.  tab = new stuff*[h];
  4.  for(int i = 0; i < h; ++i)
  5.  {
  6.   tab[i] = new stuff[h];
  7.  }


 
ca devrait aller mieux

Reply

Marsh Posté le 25-02-2011 à 10:50:48    

Tout dépend des données que tu vas manipuler et ce que ca donne, mais si tu pousses ton exemple dans d'autres contextes, disons : pour noter des infos sur les habitants en traitant uniquement le canada, tu vas pouvoir t'attendre à avoir de grandes zones vides. Dans ton exemple, ca voudra dire de grandes quantités de mémoire gaspillées et éventuellement du temps passé à parcourir des zones vides.
 
Je suis d'accord que la solution de Joel est parfaite pour faire du traitement d'image ou ce genre de chose ou l'importance des données est uniformément répartie dans le tableau. Mais lorsqu'on l'applique à d'autres domaines, suivant le type de données, on peut souhaiter  une organisation différentes (comme pour les matrices creuses, par exemple)
 
Tu peux par exemple traiter ton problème en ayant un tableau contigu pour chaque zone à forte densité et les recenser dans une structure associative. Le type de structure dépendra de tes besoins : recherche d'un élément ou parcrours de tout l'ensemble ?
Dans l'idée, tu auras peut-être quelque chose comme :
 

Code :
  1. struct Rect
  2. {
  3.   size_t x, y, width, height;
  4. };
  6. struct Zone
  7. {
  8.   Rect position;
  9.   Data* donnees;
  10. };
  12. vector< Zone > carte;


 
Ca te permet d'éliminer les zones qui sont creuses tout en gardant un parcours de données contigues dans les endroits intéressants. Bref, si tu manipules de gros volumes de données, il est important de tirer profit de ce que tu sais de tes données.

Message cité 1 fois

---------------
last.fm
Reply

Marsh Posté le 25-02-2011 à 12:43:31    

theShOcKwAvE a écrit :


Je suis d'accord que la solution de Joel est parfaite pour faire du traitement d'image ou ce genre de chose ou l'importance des données est uniformément répartie dans le tableau. Mais lorsqu'on l'applique à d'autres domaines, suivant le type de données, on peut souhaiter  une organisation différentes (comme pour les matrices creuses, par exemple)


 
Exactement

Reply

Marsh Posté le 25-02-2011 à 13:03:20    


@theshockwave @Joel F
 
je comprends vos deux idées... bon le truc c'est que je bosse clairement sur du traitement d'images... mais en l'occurrence je ne stocke pas des char r v b pour chaque pixel mais des liste d'indice de face 3D pour chaque pixel ... de sorte a calculer plus tard des profondeurs....  
 
Je ne sais pas a l'avance combien je vais avoir de faces pour chaque pixel ... ca dépend du coté chahuter du Modèle 3D... mais en gros chaque pixel reçoit de 1 à 10 indices de faces 3D... On dirait pas comme ca mais ca fait vite du monde en mémoire tout ca quand on travail sur des images sortie d'un Canon EOS1D 21MP !
 
Mon idée est pour l'instant de rester sur ma structure initiale (assez proche de ce que preconise Joel F ... un espace contigu quoi... sauf pour le contenu de mes vector dont je ne sait exactement ou il atterri... pas dans ma map en tout cas !) mais de traiter l'aspect PseudoZBuffer sous la forme d'une image a pixel deux fois plus grande que l'image qu'elle décrit 4Pixel image = 1 pixel PseudoZBuffer... ca va me rajouter un peu de temps calcul mais je pense marginalement seulement.... je ramène ainsi mes PseudoZBuffer a du 5MP ce qui est plus digeste pour la machine !!
 

Code :
  1. struct PseudoZData
  2.    {
  3.      double dist;
  4.      uint pseudoface;
  5.    
  6.      std::vector<int> listFace;
  7.    
  8.      PseudoZData(){};
  9.      PseudoZData(double d, uint f):dist(d),pseudoface(f){};
  10.    };


 
le tout stocké dans un  
 

Code :
  1. PseudoZData *map;


 
après moulte test en tout genre ca me semble plutôt pas mal
 
ce qui est embettant c'est la taille residuel d'un std::vector<int> vide : 24o mais bon je crois que c'est le container le plus light malgré tout de ce point de vue...

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed