<figure><img src="image_1.png" /></figure>

HAL
open science

# L'Approximation polygonale : bilans et perspectives

Philippe Garnesson, Gerard Giraudon

► To cite this version:

Philippe Garnesson, Gerard Giraudon. L'Approximation polygonale : bilans et perspectives. [Rapport de recherche] RR-1621, INRIA. 1992. inria-00074940

HAL Id: inria-00074940

https://inria.hal.science/inria-00074940

Submitted on 24 May 2006

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
IRIA

UNITÉ DE RECHERCHE
IRIA-SOPHIA ANTIPOLIS

Rapports de Recherche

N°1621

Programme 4
Robotique, Image et Vision

POLYGONAL APPROXIMATION
OVERVIEW AND PERSPECTIVES

Philippe GARNESSON et Gérard GIRAUDON

Juin 1991

Institut National

de Recherche

en Informatique

et en Automatique

Sophia Antipolis

B.P. 109

06561 Valbonne Cedex

France

Tél : 93 65 77 77
L'approximation polygonale
bilans et perspectives

Polygonal Approximation
Overview and Perspectives

Philippe GARNESSON, Gérard GIRAUDON

INRIA Sophia Antipolis
2004 Route des Lucioles - 06561 VALBONNE Cedex
FRANCE

Juin 1991

Rapport de Recherche n° 1621.

Programme 4: Robotique, Image et Vision
Résumé

L'approximation polygonale consiste à transformer une chaîne de points connexes en une
suite de segments de droite. En vision par ordinateur, l'approximation polygonale est une étape
classique et même incontournable si les caractéristiques géométriques des objets doivent être
prises en compte.

Après avoir rappelé les critères qualitatifs souvent contradictoires qui sont recherchés dans
l'approximation et après avoir dressé une revue complète des approches retenues jusqu'à présent,
nous proposons d'utiliser de nouveaux critères basés sur un principe de minimisation d'une
énergie le long de la chaîne. Ces critères sont basés sur les notions d'écart maximum à la droite
et de somme des écarts.

Nous montrons sur de nombreux exemples, l'intérêt de notre approche par rapport aux
approches classiques à la fois vis à vis d'impératifs objectifs, tels que l'invariance en rotation
ou masquage, ainsi que vis à vis de critères subjectifs de respect de l'information géométrique
recherchés tel que préservation des angles ou insensibilité au bruit.

Abstract

Polygonal Approximation is the transformation of linked edge point into a sequence of line
segments. In Computer Vision, Polygonal Approximation is a standard task; it is even unavoi-
dable if geometric characteristics of objects must be considered.

In the first part of the paper, we present different criteria, sometimes inconsistent within
themselves, which are used in Polygonal Approximation; furthermore, we survey the field of
present methods.

Then, we propose a new approach based on the minimization of an energy along the linked edge
points.

This energy is based on the maximum distance between the line segments and the linked edge
points and on the sum of these distances.

We illustrate, with many examples, the interest of our approach through objective tests
(demonstrating e.g. invariance in rotation or with a mask) and through subjective tests showing
geometric shape preservation (such as angles) and the influence of noise.
7 Conclusions et perspectives 30

A Résulats comparatifs 33

A.1 Les méthodes comparées 33

A.2 Les paramètres 33

A.2.1 Les images 33

A.2.2 L'écart maximal 33

A.3 Les mesures comparatives, les tests effectués 34

A.4 Analyse des résultats 40

A.4.1 Nombre de segments et surface 40

A.4.2 L'invariance 41

A.5 Les résultats en images 48

Annexes 57

B Complexité de la méthode proposée 57

C Détermination de l'écart maximal et de la surface 58

C.1 Détermination de l'écart maximal 58

C.1.1 Détermination de la hauteur 58

C.1.2 Détermination de l'écart 59

C.2 Détermination de la surface 59

C.3 Résumé 61

D Structure de données 62

Bibliographie 63
# 1 Le cadre de l'étude

Nous abordons dans cette étude un problème classique: celui de l'approximation polygonale. L'approximation polygonale consiste à transformer une chaîne de pixels [Gira 87] en segments de droites.

Ce changement de structure de représentation de l'information s'accompagne généralement de deux avantages essentiels:

* Le gain en espace mémoire: l'approximation polygonale réduit considérablement le volume des données. A titre indicatif, l'approximation polygonale permet un gain de l'ordre de 90% dans le cadre d'une de nos applications [Garn 89].

* Le gain en efficacité, dans de nombreuses applications complexes, la représentation des points d'une chaîne par un nombre réduit de primitives est indispensable.

En fonction du contexte de l'application, d'autres impératifs spécifiques viennent s'ajouter. Par exemple, dans le cadre d'une application de découpe industrielle de pièces de tissus, les impératifs suivants doivent être pris en compte: l'approximation ne doit pas empiéter sur la surface de l'objet et les chutes de tissus (surface prise en dehors de l'objet) doivent être minimisées. Dans nos thèmes de recherche, une des applications privilégiées concerne la reconnaissance d'objet et plus particulièrement la mise en correspondance entre un modèle géométrique défini par des segments de droite et la géométrie des données.

Dans ce cadre, il nous semble essentiel de définir clairement les critères qui sont généralement recherchés. Pour cela, nous classifions ces critères en deux catégories, les critères objectifs ("invariance") et les critères subjectifs souvent relatifs à l'application.

**Note:** cette étude est illustrée de schémas qui font apparaître simultanément la chaîne de points et son approximation. La chaîne est alors représentée par un trait continu alors que les segments sont représentés par un trait en pointillé.

## 1.1 Les critères objectifs: les critères d'invariance

Dans le contexte de la reconnaissance d'objets il est indispensable de considérer le fait que la mise en correspondance entre le modèle et les données ne peut se faire sans prendre en compte certaines transformations. Une transformation correspond, par exemple, à un changement d'échelle.

Un critère essentiel et objectif pour évaluer les performances d'une approximation consiste à pouvoir assurer que les résultats fournis soient "invariants" quelque soient un ensemble de transformations définies a priori.

Les transformations que nous prendrons en compte sont les plus classiques, il s'agit alors du facteur d'échelle, de la rotation et de la translation ainsi qu'une transformation rarement prise en compte que nous appelons le masquage. Ces transformations sont explicitées en détail ci-après.

### 1.1.1 L'échelle

La distance de l'objet ou parfois sa taille est connue de façon imprécise. Il est donc nécessaire de prendre en compte une variation possible de l'échelle lors de la reconnaissance.