An integer linear program for substitution-tolerant subgraph isomorphism and its use for symbol spotting in technical drawings
Identifieur interne : 000514 ( France/Analysis ); précédent : 000513; suivant : 000515An integer linear program for substitution-tolerant subgraph isomorphism and its use for symbol spotting in technical drawings
Auteurs : Pierre Le Bodic [France] ; Pierre Héroux [France] ; Sébastien Adam [France] ; Yves Lecourtier [France]Source :
- Pattern Recognition [ 0031-3203 ] ; 2012-06-16.
English descriptors
Abstract
This paper tackles the problem of substitution-tolerant subgraph isomorphism which is a specific class of error-tolerant isomorphism. This problem aims at finding a subgraph isomorphism of a pattern graph S in a target graph G. This isomorphism only considers label substitutions and forbids vertex and edge insertion in G. This kind of subgraph isomorphism is often needed in pattern recognition problems when graphs are attributed with real values and no exact matching can be found between attributes due to noise. Our proposal to solve the problem of substitution-tolerant subgraph isomorphism relies on its formulation in the Integer Linear Program (ILP) formalism. Using a general ILP solver, the approach is able to find, if one exists, a mapping of a pattern graph into a target graph such that the topology of the searched graph is kept and the editing operations between the labels have a minimal cost. This technique is evaluated on both a set of synthetic graphs and a problem of symbol detection in technical drawings. In the second case, document and symbol images are represented by vector-attributed Region Adjacency Graphs built from a segmentation process. Obtained results demonstrate the relevance of considering subgraph isomorphism as an optimization process.
Url:
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 000035
- to stream Hal, to step Curation: 000035
- to stream Hal, to step Checkpoint: 000301
- to stream Main, to step Merge: 000578
- to stream Main, to step Curation: 000573
- to stream Main, to step Exploration: 000573
- to stream France, to step Extraction: 000514
Links to Exploration step
Hal:hal-00726076Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">An integer linear program for substitution-tolerant subgraph isomorphism and its use for symbol spotting in technical drawings</title><author><name sortKey="Le Bodic, Pierre" sort="Le Bodic, Pierre" uniqKey="Le Bodic P" first="Pierre" last="Le Bodic">Pierre Le Bodic</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-2544" status="VALID"><idno type="RNSR">199812948M</idno><orgName>Laboratoire de Recherche en Informatique</orgName><orgName type="acronym">LRI</orgName><desc><address><addrLine>LRI - Bâtiments 650-660 Université Paris-Sud 91405 Orsay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.lri.fr/</ref></desc><listRelation><relation active="#struct-92966" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-411575" type="direct"></relation><relation name="UMR8623" active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-92966" type="direct"><org type="institution" xml:id="struct-92966" status="VALID"><orgName>Université Paris-Sud - Paris 11</orgName><orgName type="acronym">UP11</orgName><desc><address><addrLine>Bâtiment 300 - 91405 Orsay cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.u-psud.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="direct"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-411575" type="direct"><org type="institution" xml:id="struct-411575" status="VALID"><orgName>CentraleSupélec</orgName><desc><address><addrLine>3, rue Joliot Curie,Plateau de Moulon,91192 GIF-SUR-YVETTE Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.centralesupelec.fr</ref></desc></org></tutelle><tutelle name="UMR8623" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country></affiliation></author><author><name sortKey="Heroux, Pierre" sort="Heroux, Pierre" uniqKey="Heroux P" first="Pierre" last="Héroux">Pierre Héroux</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-389520" status="INCOMING"> <orgName>DOCAPP</orgName> <desc> <address> <country key="FR"></country> </address> </desc> <listRelation> <relation active="#struct-23832" type="direct"></relation> <relation active="#struct-300317" type="indirect"></relation> <relation name="EA4108" active="#struct-300318" type="indirect"></relation> <relation active="#struct-301288" type="indirect"></relation> <relation active="#struct-301232" type="indirect"></relation> </listRelation><tutelles><tutelle active="#struct-23832" type="direct"><org type="laboratory" xml:id="struct-23832" status="VALID"><orgName>Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes</orgName><orgName type="acronym">LITIS</orgName><desc><address><addrLine>Avenue de l'Université UFR des Sciences et Techniques 76800 Saint-Etienne du Rouvray</addrLine><country key="FR"></country></address><ref type="url">http://www.litislab.eu</ref></desc><listRelation><relation active="#struct-300317" type="direct"></relation><relation name="EA4108" active="#struct-300318" type="direct"></relation><relation active="#struct-301288" type="direct"></relation><relation active="#struct-301232" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-300317" type="indirect"><org type="institution" xml:id="struct-300317" status="VALID"><orgName>Université du Havre</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="EA4108" active="#struct-300318" type="indirect"><org type="institution" xml:id="struct-300318" status="VALID"><orgName>Université de Rouen</orgName><desc><address><addrLine> 1 rue Thomas Becket - 76821 Mont-Saint-Aignan</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-rouen.fr/</ref></desc></org></tutelle><tutelle active="#struct-301288" type="indirect"><org type="department" xml:id="struct-301288" status="VALID"><orgName>Institut National des Sciences Appliquées - Rouen</orgName><orgName type="acronym">INSA Rouen</orgName><desc><address><country key="FR"></country></address></desc><listRelation><relation active="#struct-301232" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-301232" type="indirect"><org type="institution" xml:id="struct-301232" status="VALID"><orgName>Institut National des Sciences Appliquées</orgName><orgName type="acronym">INSA</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Le Havre</settlement><region type="region" nuts="2">Région Normandie</region><region type="old region" nuts="2">Haute-Normandie</region></placeName><orgName type="university">Université du Havre</orgName><placeName><settlement type="city">Rouen</settlement><region type="region" nuts="2">Région Normandie</region><region type="old region" nuts="2">Haute-Normandie</region></placeName><orgName type="university">Université de Rouen</orgName></affiliation></author><author><name sortKey="Adam, Sebastien" sort="Adam, Sebastien" uniqKey="Adam S" first="Sébastien" last="Adam">Sébastien Adam</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-389520" status="INCOMING"> <orgName>DOCAPP</orgName> <desc> <address> <country key="FR"></country> </address> </desc> <listRelation> <relation active="#struct-23832" type="direct"></relation> <relation active="#struct-300317" type="indirect"></relation> <relation name="EA4108" active="#struct-300318" type="indirect"></relation> <relation active="#struct-301288" type="indirect"></relation> <relation active="#struct-301232" type="indirect"></relation> </listRelation><tutelles><tutelle active="#struct-23832" type="direct"><org type="laboratory" xml:id="struct-23832" status="VALID"><orgName>Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes</orgName><orgName type="acronym">LITIS</orgName><desc><address><addrLine>Avenue de l'Université UFR des Sciences et Techniques 76800 Saint-Etienne du Rouvray</addrLine><country key="FR"></country></address><ref type="url">http://www.litislab.eu</ref></desc><listRelation><relation active="#struct-300317" type="direct"></relation><relation name="EA4108" active="#struct-300318" type="direct"></relation><relation active="#struct-301288" type="direct"></relation><relation active="#struct-301232" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-300317" type="indirect"><org type="institution" xml:id="struct-300317" status="VALID"><orgName>Université du Havre</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="EA4108" active="#struct-300318" type="indirect"><org type="institution" xml:id="struct-300318" status="VALID"><orgName>Université de Rouen</orgName><desc><address><addrLine> 1 rue Thomas Becket - 76821 Mont-Saint-Aignan</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-rouen.fr/</ref></desc></org></tutelle><tutelle active="#struct-301288" type="indirect"><org type="department" xml:id="struct-301288" status="VALID"><orgName>Institut National des Sciences Appliquées - Rouen</orgName><orgName type="acronym">INSA Rouen</orgName><desc><address><country key="FR"></country></address></desc><listRelation><relation active="#struct-301232" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-301232" type="indirect"><org type="institution" xml:id="struct-301232" status="VALID"><orgName>Institut National des Sciences Appliquées</orgName><orgName type="acronym">INSA</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Le Havre</settlement><region type="region" nuts="2">Région Normandie</region><region type="old region" nuts="2">Haute-Normandie</region></placeName><orgName type="university">Université du Havre</orgName><placeName><settlement type="city">Rouen</settlement><region type="region" nuts="2">Région Normandie</region><region type="old region" nuts="2">Haute-Normandie</region></placeName><orgName type="university">Université de Rouen</orgName></affiliation></author><author><name sortKey="Lecourtier, Yves" sort="Lecourtier, Yves" uniqKey="Lecourtier Y" first="Yves" last="Lecourtier">Yves Lecourtier</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-389520" status="INCOMING"> <orgName>DOCAPP</orgName> <desc> <address> <country key="FR"></country> </address> </desc> <listRelation> <relation active="#struct-23832" type="direct"></relation> <relation active="#struct-300317" type="indirect"></relation> <relation name="EA4108" active="#struct-300318" type="indirect"></relation> <relation active="#struct-301288" type="indirect"></relation> <relation active="#struct-301232" type="indirect"></relation> </listRelation><tutelles><tutelle active="#struct-23832" type="direct"><org type="laboratory" xml:id="struct-23832" status="VALID"><orgName>Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes</orgName><orgName type="acronym">LITIS</orgName><desc><address><addrLine>Avenue de l'Université UFR des Sciences et Techniques 76800 Saint-Etienne du Rouvray</addrLine><country key="FR"></country></address><ref type="url">http://www.litislab.eu</ref></desc><listRelation><relation active="#struct-300317" type="direct"></relation><relation name="EA4108" active="#struct-300318" type="direct"></relation><relation active="#struct-301288" type="direct"></relation><relation active="#struct-301232" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-300317" type="indirect"><org type="institution" xml:id="struct-300317" status="VALID"><orgName>Université du Havre</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="EA4108" active="#struct-300318" type="indirect"><org type="institution" xml:id="struct-300318" status="VALID"><orgName>Université de Rouen</orgName><desc><address><addrLine> 1 rue Thomas Becket - 76821 Mont-Saint-Aignan</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-rouen.fr/</ref></desc></org></tutelle><tutelle active="#struct-301288" type="indirect"><org type="department" xml:id="struct-301288" status="VALID"><orgName>Institut National des Sciences Appliquées - Rouen</orgName><orgName type="acronym">INSA Rouen</orgName><desc><address><country key="FR"></country></address></desc><listRelation><relation active="#struct-301232" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-301232" type="indirect"><org type="institution" xml:id="struct-301232" status="VALID"><orgName>Institut National des Sciences Appliquées</orgName><orgName type="acronym">INSA</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Le Havre</settlement><region type="region" nuts="2">Région Normandie</region><region type="old region" nuts="2">Haute-Normandie</region></placeName><orgName type="university">Université du Havre</orgName><placeName><settlement type="city">Rouen</settlement><region type="region" nuts="2">Région Normandie</region><region type="old region" nuts="2">Haute-Normandie</region></placeName><orgName type="university">Université de Rouen</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:hal-00726076</idno><idno type="halId">hal-00726076</idno><idno type="halUri">https://hal.archives-ouvertes.fr/hal-00726076</idno><idno type="url">https://hal.archives-ouvertes.fr/hal-00726076</idno><date when="2012-06-16">2012-06-16</date><idno type="wicri:Area/Hal/Corpus">000035</idno><idno type="wicri:Area/Hal/Curation">000035</idno><idno type="wicri:Area/Hal/Checkpoint">000301</idno><idno type="wicri:doubleKey">0031-3203:2012:Le Bodic P:an:integer:linear</idno><idno type="wicri:Area/Main/Merge">000578</idno><idno type="wicri:Area/Main/Curation">000573</idno><idno type="wicri:Area/Main/Exploration">000573</idno><idno type="wicri:Area/France/Extraction">000514</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">An integer linear program for substitution-tolerant subgraph isomorphism and its use for symbol spotting in technical drawings</title><author><name sortKey="Le Bodic, Pierre" sort="Le Bodic, Pierre" uniqKey="Le Bodic P" first="Pierre" last="Le Bodic">Pierre Le Bodic</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-2544" status="VALID"><idno type="RNSR">199812948M</idno><orgName>Laboratoire de Recherche en Informatique</orgName><orgName type="acronym">LRI</orgName><desc><address><addrLine>LRI - Bâtiments 650-660 Université Paris-Sud 91405 Orsay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.lri.fr/</ref></desc><listRelation><relation active="#struct-92966" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-411575" type="direct"></relation><relation name="UMR8623" active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-92966" type="direct"><org type="institution" xml:id="struct-92966" status="VALID"><orgName>Université Paris-Sud - Paris 11</orgName><orgName type="acronym">UP11</orgName><desc><address><addrLine>Bâtiment 300 - 91405 Orsay cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.u-psud.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="direct"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-411575" type="direct"><org type="institution" xml:id="struct-411575" status="VALID"><orgName>CentraleSupélec</orgName><desc><address><addrLine>3, rue Joliot Curie,Plateau de Moulon,91192 GIF-SUR-YVETTE Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.centralesupelec.fr</ref></desc></org></tutelle><tutelle name="UMR8623" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country></affiliation></author><author><name sortKey="Heroux, Pierre" sort="Heroux, Pierre" uniqKey="Heroux P" first="Pierre" last="Héroux">Pierre Héroux</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-389520" status="INCOMING"> <orgName>DOCAPP</orgName> <desc> <address> <country key="FR"></country> </address> </desc> <listRelation> <relation active="#struct-23832" type="direct"></relation> <relation active="#struct-300317" type="indirect"></relation> <relation name="EA4108" active="#struct-300318" type="indirect"></relation> <relation active="#struct-301288" type="indirect"></relation> <relation active="#struct-301232" type="indirect"></relation> </listRelation><tutelles><tutelle active="#struct-23832" type="direct"><org type="laboratory" xml:id="struct-23832" status="VALID"><orgName>Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes</orgName><orgName type="acronym">LITIS</orgName><desc><address><addrLine>Avenue de l'Université UFR des Sciences et Techniques 76800 Saint-Etienne du Rouvray</addrLine><country key="FR"></country></address><ref type="url">http://www.litislab.eu</ref></desc><listRelation><relation active="#struct-300317" type="direct"></relation><relation name="EA4108" active="#struct-300318" type="direct"></relation><relation active="#struct-301288" type="direct"></relation><relation active="#struct-301232" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-300317" type="indirect"><org type="institution" xml:id="struct-300317" status="VALID"><orgName>Université du Havre</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="EA4108" active="#struct-300318" type="indirect"><org type="institution" xml:id="struct-300318" status="VALID"><orgName>Université de Rouen</orgName><desc><address><addrLine> 1 rue Thomas Becket - 76821 Mont-Saint-Aignan</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-rouen.fr/</ref></desc></org></tutelle><tutelle active="#struct-301288" type="indirect"><org type="department" xml:id="struct-301288" status="VALID"><orgName>Institut National des Sciences Appliquées - Rouen</orgName><orgName type="acronym">INSA Rouen</orgName><desc><address><country key="FR"></country></address></desc><listRelation><relation active="#struct-301232" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-301232" type="indirect"><org type="institution" xml:id="struct-301232" status="VALID"><orgName>Institut National des Sciences Appliquées</orgName><orgName type="acronym">INSA</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Le Havre</settlement><region type="region" nuts="2">Région Normandie</region><region type="old region" nuts="2">Haute-Normandie</region></placeName><orgName type="university">Université du Havre</orgName><placeName><settlement type="city">Rouen</settlement><region type="region" nuts="2">Région Normandie</region><region type="old region" nuts="2">Haute-Normandie</region></placeName><orgName type="university">Université de Rouen</orgName></affiliation></author><author><name sortKey="Adam, Sebastien" sort="Adam, Sebastien" uniqKey="Adam S" first="Sébastien" last="Adam">Sébastien Adam</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-389520" status="INCOMING"> <orgName>DOCAPP</orgName> <desc> <address> <country key="FR"></country> </address> </desc> <listRelation> <relation active="#struct-23832" type="direct"></relation> <relation active="#struct-300317" type="indirect"></relation> <relation name="EA4108" active="#struct-300318" type="indirect"></relation> <relation active="#struct-301288" type="indirect"></relation> <relation active="#struct-301232" type="indirect"></relation> </listRelation><tutelles><tutelle active="#struct-23832" type="direct"><org type="laboratory" xml:id="struct-23832" status="VALID"><orgName>Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes</orgName><orgName type="acronym">LITIS</orgName><desc><address><addrLine>Avenue de l'Université UFR des Sciences et Techniques 76800 Saint-Etienne du Rouvray</addrLine><country key="FR"></country></address><ref type="url">http://www.litislab.eu</ref></desc><listRelation><relation active="#struct-300317" type="direct"></relation><relation name="EA4108" active="#struct-300318" type="direct"></relation><relation active="#struct-301288" type="direct"></relation><relation active="#struct-301232" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-300317" type="indirect"><org type="institution" xml:id="struct-300317" status="VALID"><orgName>Université du Havre</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="EA4108" active="#struct-300318" type="indirect"><org type="institution" xml:id="struct-300318" status="VALID"><orgName>Université de Rouen</orgName><desc><address><addrLine> 1 rue Thomas Becket - 76821 Mont-Saint-Aignan</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-rouen.fr/</ref></desc></org></tutelle><tutelle active="#struct-301288" type="indirect"><org type="department" xml:id="struct-301288" status="VALID"><orgName>Institut National des Sciences Appliquées - Rouen</orgName><orgName type="acronym">INSA Rouen</orgName><desc><address><country key="FR"></country></address></desc><listRelation><relation active="#struct-301232" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-301232" type="indirect"><org type="institution" xml:id="struct-301232" status="VALID"><orgName>Institut National des Sciences Appliquées</orgName><orgName type="acronym">INSA</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Le Havre</settlement><region type="region" nuts="2">Région Normandie</region><region type="old region" nuts="2">Haute-Normandie</region></placeName><orgName type="university">Université du Havre</orgName><placeName><settlement type="city">Rouen</settlement><region type="region" nuts="2">Région Normandie</region><region type="old region" nuts="2">Haute-Normandie</region></placeName><orgName type="university">Université de Rouen</orgName></affiliation></author><author><name sortKey="Lecourtier, Yves" sort="Lecourtier, Yves" uniqKey="Lecourtier Y" first="Yves" last="Lecourtier">Yves Lecourtier</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-389520" status="INCOMING"> <orgName>DOCAPP</orgName> <desc> <address> <country key="FR"></country> </address> </desc> <listRelation> <relation active="#struct-23832" type="direct"></relation> <relation active="#struct-300317" type="indirect"></relation> <relation name="EA4108" active="#struct-300318" type="indirect"></relation> <relation active="#struct-301288" type="indirect"></relation> <relation active="#struct-301232" type="indirect"></relation> </listRelation><tutelles><tutelle active="#struct-23832" type="direct"><org type="laboratory" xml:id="struct-23832" status="VALID"><orgName>Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes</orgName><orgName type="acronym">LITIS</orgName><desc><address><addrLine>Avenue de l'Université UFR des Sciences et Techniques 76800 Saint-Etienne du Rouvray</addrLine><country key="FR"></country></address><ref type="url">http://www.litislab.eu</ref></desc><listRelation><relation active="#struct-300317" type="direct"></relation><relation name="EA4108" active="#struct-300318" type="direct"></relation><relation active="#struct-301288" type="direct"></relation><relation active="#struct-301232" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-300317" type="indirect"><org type="institution" xml:id="struct-300317" status="VALID"><orgName>Université du Havre</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="EA4108" active="#struct-300318" type="indirect"><org type="institution" xml:id="struct-300318" status="VALID"><orgName>Université de Rouen</orgName><desc><address><addrLine> 1 rue Thomas Becket - 76821 Mont-Saint-Aignan</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-rouen.fr/</ref></desc></org></tutelle><tutelle active="#struct-301288" type="indirect"><org type="department" xml:id="struct-301288" status="VALID"><orgName>Institut National des Sciences Appliquées - Rouen</orgName><orgName type="acronym">INSA Rouen</orgName><desc><address><country key="FR"></country></address></desc><listRelation><relation active="#struct-301232" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-301232" type="indirect"><org type="institution" xml:id="struct-301232" status="VALID"><orgName>Institut National des Sciences Appliquées</orgName><orgName type="acronym">INSA</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Le Havre</settlement><region type="region" nuts="2">Région Normandie</region><region type="old region" nuts="2">Haute-Normandie</region></placeName><orgName type="university">Université du Havre</orgName><placeName><settlement type="city">Rouen</settlement><region type="region" nuts="2">Région Normandie</region><region type="old region" nuts="2">Haute-Normandie</region></placeName><orgName type="university">Université de Rouen</orgName></affiliation></author></analytic><series><title level="j">Pattern Recognition</title><idno type="ISSN">0031-3203</idno><imprint><date type="datePub">2012-06-16</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>Integer linear programming</term><term>Substitution-tolerant subgraph isomorphism</term><term>Symbol spotting</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">This paper tackles the problem of substitution-tolerant subgraph isomorphism which is a specific class of error-tolerant isomorphism. This problem aims at finding a subgraph isomorphism of a pattern graph S in a target graph G. This isomorphism only considers label substitutions and forbids vertex and edge insertion in G. This kind of subgraph isomorphism is often needed in pattern recognition problems when graphs are attributed with real values and no exact matching can be found between attributes due to noise. Our proposal to solve the problem of substitution-tolerant subgraph isomorphism relies on its formulation in the Integer Linear Program (ILP) formalism. Using a general ILP solver, the approach is able to find, if one exists, a mapping of a pattern graph into a target graph such that the topology of the searched graph is kept and the editing operations between the labels have a minimal cost. This technique is evaluated on both a set of synthetic graphs and a problem of symbol detection in technical drawings. In the second case, document and symbol images are represented by vector-attributed Region Adjacency Graphs built from a segmentation process. Obtained results demonstrate the relevance of considering subgraph isomorphism as an optimization process.</div></front></TEI><affiliations><list><country><li>France</li></country><region><li>Haute-Normandie</li><li>Région Normandie</li></region><settlement><li>Le Havre</li><li>Rouen</li></settlement><orgName><li>Université de Rouen</li><li>Université du Havre</li></orgName></list><tree><country name="France"><noRegion><name sortKey="Le Bodic, Pierre" sort="Le Bodic, Pierre" uniqKey="Le Bodic P" first="Pierre" last="Le Bodic">Pierre Le Bodic</name></noRegion><name sortKey="Adam, Sebastien" sort="Adam, Sebastien" uniqKey="Adam S" first="Sébastien" last="Adam">Sébastien Adam</name><name sortKey="Heroux, Pierre" sort="Heroux, Pierre" uniqKey="Heroux P" first="Pierre" last="Héroux">Pierre Héroux</name><name sortKey="Lecourtier, Yves" sort="Lecourtier, Yves" uniqKey="Lecourtier Y" first="Yves" last="Lecourtier">Yves Lecourtier</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/France/explor/LeHavreV1/Data/France/Analysis
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000514 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/France/Analysis/biblio.hfd -nk 000514 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/France
|area= LeHavreV1
|flux= France
|étape= Analysis
|type= RBID
|clé= Hal:hal-00726076
|texte= An integer linear program for substitution-tolerant subgraph isomorphism and its use for symbol spotting in technical drawings
}}
| This area was generated with Dilib version V0.6.25. |  |