38
Algorithmique, C++ Recollement d'images

Algorithmique, C++ - Ensiwiki · 2009-07-08 · Algorithmique et structures de données ... 4 séances de cours + 7 séances en salle machine + 1 séance de TD (planning : cf. wikiosk)

  • Upload
    lengoc

  • View
    222

  • Download
    0

Embed Size (px)

Citation preview

Algorithmique, C++

Recollement d'images

Objectif du TP : programmation d'un algorithme de recollement d'images

Langage C++ Introduction au langage Gestion de la mémoire, héritage, généricité,

Standard Template Library (STL), ... Algorithmique et structures de données

Application de notions vues en CTD Algos de programmation dynamique et

Dijkstra Structures de données, calculs de coûts

Programmation efficace et optimisations Options de compilation, outils de

profilage, ... Débogage de programmes

Déroulement

4 séances de cours + 7 séances en salle machine + 1 séance de TD (planning : cf. wikiosk)

Travailler sur votre compte sur ensibm

3 délivrables, sur 2/2/1 point(s), à rendre à la fin de 3 séances machines (Teide)

Note de TP = ¼ de la note d'algo

Séances notées Nouveauté : une note pour 2 séances

consécutives (5 et 6, 8 et 9, 11 et 12)

Enoncé fourni au début de la première séance

Travail à effectuer pour le début de la seconde séance

Début de la seconde séance : questionnaire + énoncé complémentaire

Ce qui vous est fourni Poly (cf. wikiosk) :

Enoncé du sujet global du TP Introduction à C++ (non exhaustif !)

Des fichiers sources Au début des séances de TP Eventuellement incomplets

Des images pour les tests Vous pouvez aussi en utiliser d'autres

Ce qui doit être rendu A la fin des séances n° 6, 9 et 12

Un code complété Un questionnaire rempli

Via Teide Travail en monômes (Hopefully) Retour/correction lors de la

séance suivante

Questionnaire Début de séance 2/2, questions de

compréhension sur la 1ère partie Code de la séance 1/2 pas forcément

corrigé Certains, pris au hasard, seront corrigés Note ≠note du questionnaire => sanction Vous pouvez demander une correction

individualisée

Rq: toutes les séances en salles machines sont obligatoires (-1 pt sur la note finale par absence)

Sujet du TP : recollement d'images

Une image numérique est constituée d'un tableau d'éléments de base appelés pixels

Pixel = PICTure ELement

A chaque pixel est associée une couleur :

triplet de scalaires (R,V,B)

R : Rouge, V : Vert, B : Bleu

Soient deux images I1 et I

2

deux vues voisines de la même scène, placées en partie l’une sur l’autre pour qu’elles se raccordent le mieux possible.

J : zone de chevauchement (Rectangle de taille n x m pixels)

I1

I2

J

Deux images se chevauchant

Recollement d'images

221

221

221 )B+(B)V+(V)R(R=ε(p) −−−

I1

I2

Chemin dans J : suite de pixels voisins ∈ J

Erreur entre les images en un pixel p ∈ J de couleur (R1,V1,B1) dans I

1 et de couleur (R2,V2,B2) dans I

2

Recollement d'images

Coût d'un chemin tracé dans J = somme des erreurs des pixels qui forment le chemin

But : raccordement entre les images le moins visible possible

Calculer le chemin de coût minimal

Image I1

affichée à gauche de ce chemin,

Image I2 à sa droite.

Recollement d'images

Recollement d'images

Objectifs des séances de TP :

Préparer les classes et méthodes utiles Calculer un chemin optimal :

Plusieurs algorithmes Tester et comparer ces algorithmes

Tests : n'hésitez pas à utiliser vos propres photos !

Recollement d'images

Plan des séances de cours Aujourd'hui (séance n° 1)

Présentation du sujet du TP De Java et C à C++

Séance n° 3 Héritage, généricité

Séance n° 7 STL et structures de données

Séance n° 10 Optimisation, débogage, exceptions, …

Introduction à C++Première partie

De Java et C à C++

Introduction Langage objet : classes, héritage,

généricité… C++ peut être considéré comme extension

de C (en première approximation)

C est un sous-ensemble de C++ (à peu de choses près)

Pas de garbage collector (≠ Java) Bibliothèque Standard : STL

Structures de données Algos standards

“Héritage” du C Types de base : int, double, float, char…

Arithmétique de base : +, - , *, /, %, …

Tests et boucles : if (condition) { insts; } else { insts; } for (int i=0; i<n; i++) { insts;} while (condition) {insts;} do {insts;} while(condition);

Pointeurs et tableaux : char v[10]; int *i;

Extensions des fonctions Surcharge de fonctions : int puissance(int x, int n){ //calcule xn = x.x…x}double puissance(int x, double n){ //calcule xn = en log x

} Arguments par défaut d’une fonctionint ajouter(int a, int b=1) {

return a+b; }ajouter(2); // renvoie 3

Gestion de la mémoire 2 nouveaux opérateurs de gestion de la

mémoire :

new type : allocation d'un objet unique new type[n] : allocation d'un tableau de taille

n delete adresse : libération d'un objet unique delete [] adresse : libération d'un tableau

Plus de malloc, allocation dynamique

Attention aux fuites de mémoire !

Gestion de la mémoire Exemple :

int* pi = new int;// Au lieu de : // int *pi = (int *) malloc(sizeof(int));

float* RGB = new float[3];

delete pi;// Au lieu de : free(pi);

delete [] RGB;

Références Notion de référence : &

& (ampersand) = alias sur une variable ou un objet.

Exemple :

int ix;

int &ir = ix; // Est une ref sur ix

ir = j; // Ne transforme pas ir en ref sur j // mais copie j dans ix

ix = 1; // ir = 1 aussi

ir = 2; // ix = 2 aussi Passage de Paramètres :

void Recopie(int &i);

Entrées/sorties de base Soit printf, scanf… , soit utilisation des

flux. #include <iostream> Entrée clavier :

int i; std::cin >> i; // Lit un entier

Sortie à l'écran : int i = 2;std::cout << "i : " << i << std::endl;

Flux d'erreur :std::cerr << "erreur !" << std::endl;

Entrées/sorties fichier Exemple : ifstream f("infile"); // Ouverture en lecture ofstream g("outfile");// Ouverture en écriture fstream h("filename",ios::in|ios::out);

//Ouverture en lecture et écriture

char buf[81]; f.getline(buf, 80); // Lit une ligne while (f) { g << buf << std::endl; // Envoie dans g f.getline(buf,80); // Lit la ligne suivante }

Espace de nommage Équivalent du paquetage Java et Ada Défini à l’aide du mot-clé namespace Intérêt : éviter les conflits de noms entre

plusieurs modules. namespace pile_de_char {

void empiler(char);char depiler(); }

namespace pile_de_int {void empiler(int);int depiler(); }

Espace de nommage :utilisation

Exemple :void main(){

pile_de_char::empiler( ‘x’ ); if (pile_de_char::depiler() != ‘x’) std::cerr << "impossible" << std::endl; }

Mot-clé using : introduit l'identificateur dans la région déclarative courante :

using pile_de_char::empiler(char); => empiler('x');

Les classes Définition d'un nouveau type C++

Une classe est composée :

d'attributs (données internes) de fonctions membres appelées

méthodes

Une variable de ce type (une instance) est appelée un objet

Encapsulation : déclaration méthodes et attributs à un endroit unique

Un exemple de classe

class Point { int _x, _y;

int abscisse () const { return _x; } int ordonnee () const { return _y; } void set_coord (int x, int y) { _x = x; _y = y; }};

Exemple d'utilisation

void main() { Point p; p.set_coord(1,2); std::cout << "abscisse : " << p.abscisse()

<< " ordonnee : " << p.ordonnee()

<< std::endl;}

Accès aux attributs et méthodes

L'utilisateur peut restreindre l'accès aux attributs et fonctions membres de ses classes : public, private, protected

private : autorisé uniquement aux fonctions membres de la classe

public : autorisé pour toute fonction protected : autorisé uniquement aux

fonctions membres de la classe et aux classes dérivées

Conseil d'utilisation : tous les attributs privés

Un exemple d'utilisation

class Point {private: // Pas obligatoire, par défaut !

int _x, _y;public: // Les méthodes suivantes sont publiques

int abscisse () const { return _x; } int ordonnee () const { return _y; } void set_coord (int x, int y) {

_x = x; _y = y; }

};

Constructeurs

Rôle (principalement) : allouer la mémoire initialiser les attributs

Par défaut sont implémentés : constructeur vide constructeur de recopie

Constructeurs : exempleclass Point {

int _x, _y; public :

Point() : _x(0), _y(0) {}// Constructeur par défaut ; celui qui est appelé lors d'une déclaration du

type :// Point p;

Point(int x, int y) : _x(x), _y(y) {}// Constructeur appelé lors d'une déclaration du type :// Point p(1,2);

Point(const Point& P) : _x(P._x), _y(P._y){}// Constructeur de recopie :

// Point p1; // Point p2(p1); // p2 est une copie de p1

};

Eléments de syntaxe Liste d'initialisation d'un constructeur :

Point() : _x(0),_y(0) {…}

Fonctions membres constantes :ne modifient pas les attributs de la classe

class Point { int _x, _y; public: int abscisse() const { return _x; } … };

Destructeurs Rôle : libérer la mémoire !

Appelés automatiquement à la fin de la portée de l'objet (fermeture d'accolade } )

Par défaut un destructeur vide est implémenté

Destructeur : exempleclass Tableau { int *_t;

public: Tableau(int s = 10) { _t = new int[s]; } ~Tableau() { delete [] _t; }};

{ Tableau T; …} // Destructeur ~Tableau() appelé automatiquement // en fin de portée

Séparation déclaration/implantation

Fichier Point.h :Class Point { int _x, _y;Public: int abscisse() const; …};

Fichier Point.cpp :Point::Point() : _x(0), _y(0) {}int Point::abscisse() const {return _x;}

Références croisées Problème :

#include "titi.h"class toto { void f1(titi t);};

toto.h titi.h#include "toto.h"class titi { void f1(toto t);};

NE FONCTIONNE PAS !!

toto.cpp

#include "toto.h"void toto::f1(titi t){…}

titi.cpp

#include "titi.h"void titi::f1(toto t){…}

Références croisées Solution : prédéclarations

class titi;class toto { void f1(titi t);};

toto.h titi.h

class toto;class titi { void f1(toto t);};

toto.cpp

#include "toto.h"#include "titi.h"void toto::f1(titi t){…}

titi.cpp

#include "titi.h"#include "toto.h"void titi::f1(toto t){…}