Nghiên cứu về Phân loại và Nhận diện Biểu tượng qua Đồ thị

Luận văn thạc sĩ nghiên cứu fouille de graphes et classification de graphes application au symbol spotting, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện pháp hoàn thiện

• Tác giả: Nguyen Quoc Toan
• Người hướng dẫn: Professeur Jean-Marc Ogier
• Trường học: Université de la Rochelle
• Chuyên ngành: Informatique
• Đề tài: Nghiên cứu về Phân loại và Nhận diện Biểu tượng qua Đồ thị
• Loại tài liệu: Thesis
• Năm xuất bản: 2009
• Địa điểm: La Rochelle

Tóm tắt

I. Giới thiệu Nghiên cứu Phân loại và Nhận diện Biểu tượng

Nghiên cứu về phân loại và nhận diện biểu tượng là một lĩnh vực quan trọng trong nhận dạng mẫu, với ứng dụng rộng rãi trong kiến trúc, bản đồ, điện tử, cơ khí và nhiều ngành công nghiệp khác. Do sự đa dạng của các loại tài liệu đồ họa và các bộ biểu tượng đặc trưng cho mỗi loại, việc định nghĩa chính xác một biểu tượng trở nên khó khăn. Một cách tổng quát, biểu tượng có thể được định nghĩa là một thực thể đồ họa mang một ý nghĩa cụ thể trong ngữ cảnh của một lĩnh vực ứng dụng cụ thể. Hiện nay, có rất nhiều phương pháp tiếp cận để nhận dạng biểu tượng. Mỗi phương pháp đều có những ưu điểm và hạn chế riêng, chỉ phù hợp với một số ngữ cảnh và điều kiện nhất định. Nghiên cứu này sử dụng phương pháp dựa trên đồ thị để biểu diễn hình ảnh tài liệu kỹ thuật và biểu tượng yêu cầu dưới dạng đồ thị. Mỗi nút của đồ thị đại diện cho một thành phần liên thông trong hình ảnh tài liệu. Mối quan hệ giữa hai thành phần liên thông được thể hiện trong một đồ thị "lân cận". Vấn đề nhận dạng biểu tượng được chuyển thành bài toán đẳng cấu đồ thị con, nhằm tìm các đồ thị con tương ứng với các biểu tượng đồ họa.

1.1. Ý nghĩa và ứng dụng của Phân loại Biểu tượng

Việc phân loại biểu tượng đóng vai trò then chốt trong nhiều ứng dụng thực tế, từ phân tích sơ đồ mạch điện đến nhận diện các thành phần trong bản vẽ kiến trúc. Quá trình này cho phép máy tính hiểu và xử lý thông tin một cách hiệu quả hơn, giảm thiểu sự can thiệp của con người và tăng độ chính xác. Các ứng dụng tiềm năng bao gồm tự động hóa thiết kế, tìm kiếm và truy xuất thông tin, cũng như cải thiện khả năng tiếp cận cho người khuyết tật. Ví dụ, trong lĩnh vực kỹ thuật, phân loại biểu tượng có thể giúp kỹ sư nhanh chóng xác định và kiểm tra các thành phần trong một sơ đồ phức tạp, giảm thiểu sai sót và tiết kiệm thời gian. Ngoài ra, việc này còn hỗ trợ trong việc tạo ra các tài liệu kỹ thuật dễ hiểu và trực quan hơn.

1.2. Các phương pháp Nhận diện Biểu tượng phổ biến hiện nay

Hiện nay, có rất nhiều phương pháp nhận diện biểu tượng khác nhau, mỗi phương pháp có những ưu điểm và hạn chế riêng. Các phương pháp dựa trên đặc trưng hình dạng sử dụng các thuộc tính như diện tích, chu vi, và tỷ lệ để phân biệt các biểu tượng. Các phương pháp dựa trên học máy sử dụng các thuật toán như mạng nơ-ron và máy vector hỗ trợ (SVM) để huấn luyện mô hình nhận diện biểu tượng. Các phương pháp dựa trên cấu trúc đồ thị, như phương pháp được sử dụng trong nghiên cứu này, biểu diễn hình ảnh dưới dạng đồ thị và sử dụng các thuật toán so khớp đồ thị để tìm các biểu tượng. Lựa chọn phương pháp nào phụ thuộc vào đặc điểm của dữ liệu và yêu cầu của ứng dụng. Cần xem xét kỹ lưỡng các yếu tố như độ phức tạp của thuật toán, độ chính xác, và khả năng mở rộng để đưa ra lựa chọn phù hợp.

II. Thách thức Phân loại Biểu tượng và Đồ thị Phức tạp

Việc phân loại biểu tượng hiệu quả đối mặt với nhiều thách thức đáng kể, đặc biệt khi xử lý các đồ thị phức tạp. Sự biến đổi về kích thước, hướng, và hình dạng của biểu tượng, cùng với sự nhiễu loạn trong hình ảnh, có thể làm giảm độ chính xác của các thuật toán nhận diện. Hơn nữa, việc biểu diễn thông tin một cách hiệu quả dưới dạng đồ thị, cũng như việc lựa chọn các đặc trưng phù hợp để mô tả các nút và cạnh của đồ thị, đòi hỏi kiến thức chuyên sâu và kỹ năng thiết kế thuật toán. Sự phức tạp của các đồ thị biểu diễn hình ảnh có thể dẫn đến chi phí tính toán cao, làm chậm quá trình nhận diện biểu tượng. Vì vậy, cần có những phương pháp mới để giảm thiểu sự phức tạp của đồ thị và tăng tốc độ xử lý.

2.1. Ảnh hưởng của nhiễu và biến dạng hình ảnh

Nhiễu và biến dạng hình ảnh là những yếu tố quan trọng ảnh hưởng đến hiệu suất của các thuật toán phân loại biểu tượng. Nhiễu có thể xuất hiện do nhiều nguyên nhân, chẳng hạn như điều kiện ánh sáng kém, chất lượng hình ảnh thấp, hoặc quá trình quét tài liệu. Biến dạng hình ảnh có thể xảy ra do góc nhìn khác nhau, hoặc do sự biến dạng tự nhiên của vật thể. Các thuật toán phân loại biểu tượng cần phải có khả năng chống lại nhiễu và biến dạng để đạt được độ chính xác cao. Một số kỹ thuật thường được sử dụng để giảm thiểu ảnh hưởng của nhiễu và biến dạng bao gồm tiền xử lý hình ảnh, trích xuất đặc trưng mạnh mẽ, và sử dụng các mô hình học máy có khả năng chống nhiễu.

2.2. Khó khăn trong việc biểu diễn thông tin bằng đồ thị

Việc biểu diễn thông tin bằng đồ thị là một bước quan trọng trong phương pháp nhận diện biểu tượng dựa trên đồ thị. Tuy nhiên, việc lựa chọn các nút và cạnh của đồ thị, cũng như các đặc trưng để mô tả chúng, không phải là một nhiệm vụ đơn giản. Cần phải đảm bảo rằng đồ thị biểu diễn đầy đủ thông tin quan trọng, đồng thời giảm thiểu thông tin dư thừa để giảm độ phức tạp tính toán. Ngoài ra, cần phải chọn các đặc trưng phù hợp để phân biệt các biểu tượng khác nhau. Các đặc trưng có thể bao gồm hình dạng, kích thước, vị trí, và mối quan hệ không gian giữa các thành phần của biểu tượng. Việc lựa chọn các đặc trưng phù hợp đòi hỏi sự hiểu biết sâu sắc về đặc điểm của các biểu tượng cần nhận diện.

III. Phương pháp Gán Đồ thị Con dựa trên Ma trận Chi phí

Nghiên cứu này đề xuất một phương pháp gán đồ thị con dựa trên ma trận chi phí để nhận diện biểu tượng hiệu quả. Phương pháp này bao gồm việc chia đồ thị biểu diễn hình ảnh thành các đồ thị con nhỏ hơn, sau đó xây dựng một ma trận chi phí để đánh giá sự tương đồng giữa các đồ thị con. Bằng cách sử dụng các thuật toán tối ưu hóa, chúng ta có thể tìm ra sự gán tốt nhất giữa các đồ thị con và các biểu tượng mục tiêu. Phương pháp này giúp giảm độ phức tạp tính toán và tăng độ chính xác của quá trình nhận diện biểu tượng. Sự đổi mới nằm ở cách chúng ta xác định chi phí trong ma trận, kết hợp nhiều yếu tố như khoảng cách chỉnh sửa đồ thị và đặc trưng của các nút và cạnh.

3.1. Xây dựng ma trận chi phí cho gán đồ thị con

Việc xây dựng ma trận chi phí là một bước quan trọng trong phương pháp gán đồ thị con. Ma trận chi phí thể hiện sự tương đồng giữa các đồ thị con trong hình ảnh và các biểu tượng mục tiêu. Chi phí càng thấp, sự tương đồng càng cao. Có nhiều cách khác nhau để xác định chi phí, chẳng hạn như sử dụng khoảng cách chỉnh sửa đồ thị, hoặc kết hợp nhiều đặc trưng khác nhau của các nút và cạnh. Trong nghiên cứu này, chúng tôi sử dụng một phương pháp kết hợp khoảng cách chỉnh sửa đồ thị và các đặc trưng hình dạng để xác định chi phí. Điều này cho phép chúng tôi đánh giá sự tương đồng giữa các đồ thị con và các biểu tượng mục tiêu một cách toàn diện hơn.

3.2. Tối ưu hóa gán đồ thị con bằng thuật toán Hungarian

Sau khi xây dựng ma trận chi phí, chúng ta cần tìm ra sự gán tốt nhất giữa các đồ thị con và các biểu tượng mục tiêu. Đây là một bài toán tối ưu hóa có thể được giải bằng nhiều thuật toán khác nhau, chẳng hạn như thuật toán Hungarian. Thuật toán Hungarian là một thuật toán hiệu quả để giải bài toán gán, đảm bảo tìm ra sự gán tối ưu trong thời gian ngắn. Trong nghiên cứu này, chúng tôi sử dụng thuật toán Hungarian để tối ưu hóa gán đồ thị con. Điều này cho phép chúng tôi tìm ra sự gán tốt nhất giữa các đồ thị con và các biểu tượng mục tiêu một cách nhanh chóng và chính xác.

IV. Ứng dụng Nhận diện Biểu tượng trong Tài liệu Kỹ thuật

Việc nhận diện biểu tượng có nhiều ứng dụng quan trọng trong việc xử lý tài liệu kỹ thuật. Nó có thể được sử dụng để tự động hóa việc trích xuất thông tin từ sơ đồ mạch điện, bản vẽ kiến trúc, và các tài liệu kỹ thuật khác. Điều này giúp giảm thiểu thời gian và công sức cần thiết để xử lý tài liệu, đồng thời tăng độ chính xác và hiệu quả. Ngoài ra, nhận diện biểu tượng còn có thể được sử dụng để tạo ra các tài liệu kỹ thuật dễ hiểu và trực quan hơn, giúp người dùng dễ dàng tìm kiếm và truy xuất thông tin.

4.1. Tự động trích xuất thông tin từ sơ đồ điện

Trong lĩnh vực điện tử, việc nhận diện biểu tượng có thể được sử dụng để tự động trích xuất thông tin từ sơ đồ mạch điện. Điều này cho phép kỹ sư nhanh chóng xác định các thành phần trong mạch, kiểm tra kết nối, và phân tích hoạt động của mạch. Việc tự động trích xuất thông tin giúp giảm thiểu sai sót và tiết kiệm thời gian, đồng thời tăng hiệu quả của quá trình thiết kế và kiểm tra mạch điện.

4.2. Nhận diện thành phần trong bản vẽ xây dựng kiến trúc

Tương tự, trong lĩnh vực kiến trúc, việc nhận diện biểu tượng có thể được sử dụng để nhận diện các thành phần trong bản vẽ xây dựng. Điều này cho phép kiến trúc sư và kỹ sư xây dựng dễ dàng xác định vị trí của các cửa, cửa sổ, cột, dầm, và các thành phần khác. Việc nhận diện biểu tượng tự động giúp tăng tốc quá trình thiết kế và xây dựng, đồng thời giảm thiểu sai sót và cải thiện chất lượng công trình.

V. Đánh giá Hiệu năng và Thử nghiệm Phân loại Đồ thị

Hiệu năng của phương pháp phân loại đồ thị được đánh giá thông qua một loạt các thử nghiệm trên các bộ dữ liệu khác nhau. Các thử nghiệm này tập trung vào việc đo lường độ chính xác, độRecall và thời gian tính toán của thuật toán. Kết quả cho thấy rằng phương pháp gán đồ thị con dựa trên ma trận chi phí có thể đạt được độ chính xác cao với thời gian tính toán hợp lý. Các thử nghiệm cũng cho thấy rằng phương pháp này có khả năng chống lại nhiễu và biến dạng hình ảnh, làm cho nó phù hợp cho các ứng dụng thực tế. Để đánh giá khách quan, so sánh với các phương pháp state-of-the-art là cần thiết.

5.1. Tiêu chí đánh giá độ chính xác Phân loại Biểu tượng

Độ chính xác là một tiêu chí quan trọng để đánh giá hiệu năng của các thuật toán phân loại biểu tượng. Độ chính xác được định nghĩa là tỷ lệ giữa số lượng biểu tượng được phân loại đúng và tổng số lượng biểu tượng trong bộ dữ liệu. Tuy nhiên, chỉ sử dụng độ chính xác không đủ để đánh giá hiệu năng một cách toàn diện. Cần phải xem xét thêm các tiêu chí khác, chẳng hạn như độRecall và độPrecision, để đánh giá khả năng phát hiện tất cả các biểu tượng cần thiết và tránh phát hiện sai.

5.2. So sánh với các phương pháp nhận diện biểu tượng khác

Để đánh giá hiệu quả của phương pháp nhận diện biểu tượng được đề xuất, cần so sánh nó với các phương pháp khác hiện có. So sánh có thể dựa trên các tiêu chí như độ chính xác, độRecall, độPrecision, và thời gian tính toán. Kết quả so sánh cho thấy rằng phương pháp gán đồ thị con dựa trên ma trận chi phí có thể cạnh tranh với các phương pháp khác, và thậm chí vượt trội trong một số trường hợp. Điều này chứng tỏ rằng phương pháp này là một lựa chọn hứa hẹn cho các ứng dụng nhận diện biểu tượng trong thực tế.

VI. Kết luận và Hướng Phát triển trong Phân loại Đồ thị

Nghiên cứu về phân loại và nhận diện biểu tượng thông qua đồ thị là một lĩnh vực đầy tiềm năng. Phương pháp gán đồ thị con dựa trên ma trận chi phí là một hướng đi hứa hẹn, nhưng vẫn còn nhiều vấn đề cần được giải quyết. Trong tương lai, có thể tập trung vào việc cải thiện hiệu năng của thuật toán, giảm độ phức tạp tính toán, và tăng khả năng chống lại nhiễu và biến dạng hình ảnh. Ngoài ra, cần khám phá các ứng dụng mới của phân loại đồ thị trong các lĩnh vực khác nhau, chẳng hạn như phân tích mạng xã hội, phân tích dữ liệu sinh học, và phân tích tài chính.

6.1. Tóm tắt kết quả và đóng góp của nghiên cứu

Nghiên cứu này đã đề xuất một phương pháp mới để phân loại và nhận diện biểu tượng dựa trên đồ thị. Phương pháp này sử dụng kỹ thuật gán đồ thị con dựa trên ma trận chi phí để so khớp các biểu tượng với các đồ thị con trong hình ảnh. Các kết quả thử nghiệm cho thấy rằng phương pháp này có hiệu năng tốt và có khả năng chống lại nhiễu và biến dạng hình ảnh. Đóng góp của nghiên cứu này là cung cấp một phương pháp mới và hiệu quả để giải quyết bài toán phân loại biểu tượng, đồng thời mở ra những hướng nghiên cứu mới trong lĩnh vực này.

6.2. Các hướng nghiên cứu tiếp theo trong phân loại đồ thị

Có nhiều hướng nghiên cứu tiếp theo có thể được thực hiện trong lĩnh vực phân loại đồ thị. Một hướng là phát triển các thuật toán mới để giảm độ phức tạp tính toán của việc so khớp đồ thị, làm cho chúng có thể được sử dụng trong các ứng dụng thời gian thực. Một hướng khác là khám phá các phương pháp mới để biểu diễn thông tin dưới dạng đồ thị, để tăng độ chính xác và hiệu quả của quá trình phân loại. Ngoài ra, cần phải nghiên cứu các phương pháp để kết hợp thông tin từ nhiều nguồn khác nhau, chẳng hạn như hình ảnh, văn bản, và siêu dữ liệu, để cải thiện khả năng phân loại đồ thị trong các ứng dụng phức tạp.

Trích đoạn nội dung tài liệu

Mémoire de fin d’étude Fouille de graphes et Classification de graphes Application au "Symbol Spotting" Réalisé par : Nguyen Quoc Toan Responsable du stage : Jean-Marc Ogier Jean-Christophe Burie Romain Raveaux Ce stage a été réalisé au département Pascal de Laboratoire Informatique, Image et Interaction, Université de la Rochelle La Rochelle, France, Novembre 2009 TIEU LUAN MOI download : [e-mail] Table des matières 1 Introduction.2 Objectif et contribution du stage.3 Environnement de stage.4 Plan du document.1 Définition de graphe.2 Correspondance de Graphe.3 Graphe de distance.2 Distance entre signatures de graphe «graph probing ». 17 3 Etat de l'art.1 Les méthodes de construction de graphe .2 Les methodes de mise en correspondances des graphes.3 Récaputulation des méthodes. 24 4 Une méthode de mise en correspondance de graphes fondée sur l’assignement de sous- graphes.1 Définition : Décomposition en sous-graphes.2 La correspondance de sous-graphes.3 Le coût de fonction (c) pour la correspondance des signatures.4 Sous graphe de longueur ι.5 Construction de matrice de coûts. 28 5 Représentation de l’information contenue dans une image.1 Constitution de l'ensemble des nœuds.2 Extraction des composantes connexes.3 Étiquetage des composantes connexes.1 Extraction de caractéristiques .2 Statistique de la forme .3 Classification non supervisée des caractéristiques morphologiques.4 Organisation de l’information : Construction d’un Graphe de voisinage.1 Relations d'Allen bidimensionnelles.2 Intervalle basé sur les distances entre deux régions.1 Test en classification.2 Bases de tests.1 Pour la classification.2 Pour le Symbol Spotting.1 Test en classification.

54 NGUYEN Quoc Toan – Promotion 13 Page 2 TIEU LUAN MOI download : [e-mail] REMERCIEMENTS Je voudrais tout d'abord remercier professeur Jean-Marc Ogier, Jean-Christophe Burie, mes responsables de stage, de m'avoir accueillie au sein de l’équipe du projet ALPAGE du Laboratoire L3i (Laboratoire Informatique, Image et Interaction) de l’Université de la Rochelle et de m’a donné l’environnement de travail très chaleureuse pendant toute la durée du stage. Je remercie également Romain Raveaux pour ses conseils, son explication très clairement des nouveaux concepts, ses aides, ses commentaires et ses discussions qui ont fait progresser mon travail. Je lui suis reconnaissant d’avoir toujours été disponible et agréable. Je voudrais remercier tout le personnel du laboratoire L3I et particulièrement l’équipe du projet ALPAGE pour leur accueil chaleureux.

Je voudrais aussi adresser mes sincères remerciements à tous les professeurs de l’IFI pour leurs enseignements et les cours intéressants qu’ils m’ont donné pendant mes études au niveau master. Finalement, je voudrais remercier ma famille, mes parents et mes amis qui sont toujours près de moi et m’ont apporté le courage dans les moments difficiles de ma scolarité à l’IFI. NGUYEN Quoc Toan – Promotion 13 Page 3 TIEU LUAN MOI download : [e-mail] Résumé Reconnaissance des symboles est un domaine de recherche visant le développement d'algorithmes et de techniques et il y a une nombreuse méthode de reconnaissance de graphiques ont été développées pour la reconnaissance des symboles graphiques. Le problème « Symbole Spotting » est comme la localisation d'un ensemble de régions d'intérêt d'un document image, qui sont susceptibles de contenir une instance d'un certain symbole demandé sans le reconnaître explicitement.

Nous présentons donc dans ce mémoire un processus d’extraction et d’organisation de l’information contenue dans une image afin de la structurer sous forme d’un graphe pour tenir compte de la spécificité que contiennent les documents techniques. Chaque nœud du graphe représente une composante connexe dans l’image de document, ces nœuds sont étiquetés automatiquement par l’algorithme de clustering « k-Mean ». Ce dernier utilise des descripteurs de formes extraits des composantes connexes. La relation entre deux composantes connexes est matérialisée dans un graphe de « voisinage » par un arc étiqueté automatiquement en utilisant les relations d'Allen bidimensionnelles ou la distance entre composantes connexes.

Nous proposons une méthode de mise en correspondance de graphes fondée sur l’assignement de sous-graphes de longueur l. Nous proposons aussi une définition de sous- graphe de longueur l. Le problème de reconnaissance des symboles devient donc de trouver les sous-graphes les plus similaires au graphe symbole donné en requête. Nous extrayons le graphe de plan en des sous-graphes de longueur l.

Le résultat de notre application est ensemble de sous-graphes isomorphisme que la distance entre les sous-graphes et le graphe de symbole est inférieur une valeur seuil. Afin d’évaluer la classification de graphes, nous utilisons un classifieur de type K-NN pour évaluer la performance de notre méthode de mise en correspondance de graphes fondée sur l’assignement de sous-graphes. NGUYEN Quoc Toan – Promotion 13 Page 4 TIEU LUAN MOI download : [e-mail] Abstract Symbol Recognition is a research area for the development of algorithms and techniques, a lot of method of graphics recognition are developed for the recognition of graphic symbols. The problem "Symbol Spotting" aims to find the locations of a set of regions interest in a document image, which may contain an instance of a symbol without explicitly recognize.

We therefore present in this paper a process for extracting and organizing information in an image to the structure of a graph for the specificity technical documents. Each graph node is a connected component. These nodes are labeled automatically by the clustering algorithm "k-means”. We extract the connected components using shape descriptors.

We use the family of graph "Neighborhood based on k nearest neighbors" to build edges and they are automatically labeled by the Bi-dimensional Allen Algebra or the distance between regions. We propose a method for mapping graph-based assignment of subgraphs of length l. We also propose a definition of subgraph of length l. The symbols recognition problem is like to find subgraphs which are the nearest similar to the graph of symbol.

We extract the graph of technical documents in many subgraphs of length l. The recognition task consists of finding all subgraphs isomorphism which the distance between sub-graphs and symbol graphs is less than a certain threshold. To test the classification of graphs based on graph prototypes, we use a K-NN classifier in order to evaluate our method for mapping graph-based assignment of subgraphs of length l by the rate of recognition.spotting NGUYEN Quoc Toan – Promotion 13 Page 5 TIEU LUAN MOI download : [e-mail] Liste des figures Figure 1: La distance entre signatures de graphe GP, (a) les graphes non orienté, sans étiquetage, (b) les graphes orientés, sans étiquetage, (c) les graphes étiquetés, orientés.16 Figure 2: La distance entre deux graphes selon ED et GP, (a) les graphes non orienté, sans étiquetage, (b) les graphes orientés, sans étiquetage, (c) les graphes étiquetés, orientés.17 Figure 3 : Graphiques attribués relationnelle, chaque nœud est comme une ligne segmentée, un arcs établis la relation d’adjection entre deux segmentations (source[14]). 19 Figure 4: Chaque nœud est une région fermée.

L’arc lie deux régions adjacentes (source[32]) .19 Figure 5: Graphe transaction, source [33].20 Figure 6: vectorisation de quadrilatères, source [45]. 20 Figure 7: La zone influence de quadrilatère et le graphe correspondant, source [45]. 21 Figure 8: exemple de construction d’un graphe basé sur les relations topologique, source [35] .21 Figure 9: La décomposition en sous-graphes. p1, p2, p3, p4 est des sous-graphes d’extractions de longueur 1 qui associés à chaque nœuds du graphe G.

25 Figure 10: à partir deux graphes G1, G2 (a), on extrait des sous-graphes de longueur 1 (a), (b). Le graphe bipartite complet Gem obtenu par P1 et P2.28 Figure 12: un exemple de la correspondance de graphe, (a), (b) les sous-graphes d’extraction de longueur 1, (c) la correspondance de sous-graphe selon distance d’édition (ED). 30 Figure 13: Analyse des composantes connexes. 31 Figure 14: Mesure de l'élongation, comme le ratio de la longueur-largeur.

33 Figure 15:Graphe des k plus proches voisins (a) les composantes connexes, (b) k=2, (c) k=134 Figure 16: Jeu restreint de relations d'Allen.35 Figure 17: (a) deux composantes connesxes, (b) détermination du système de coordonnées lié aux. 35 Figure 18: L’image à gauche : représentation de la distance entre deux composantes connexes, d-max = 39. Le graphe droit obtenu par n = 10 (n est le nombre d’intervalles). 36 Figure 19: La vérité terrain pour un plan.

41 Figure 20: Les exemples de lettres A, M, K et Z: l'origine et la déformation des niveaux faible, moyen et élevé (de gauche à droite). 42 Figure 21 : Illustration du composant d’une molécule. 43 Figure 22:la comparaison le temps de calcul sur PMDED et PMDGP. 45 Figure 23: La courbe de précision, rappel selon la méthode Hu_Dist.

47 Figure 24: La courbe de précision, rappel selon la méthode Hu_ Allen.48 Figure 25: La courbe de précision, rappel selon la méthode Shape_Allen.49 Figure 26: La courbe de précision, rappel selon la méthode Shape_Dist. 50 Figure 27: Les meilleurs courbes de chaque méthode d'étiquetage.spotting NGUYEN Quoc Toan – Promotion 13 Page 6 TIEU LUAN MOI download : [e-mail] Liste des tableaux Table 1: Matrice des coûts de G1, G2.13 Table 2: étape 1 : réduction des lignes. 13 Table 3: étape 2 : réductions des colonnes.13 Table 4: étape 3 : déterminer le nombre minimal de lignes sur les lignes, colonnes pour couvrir tous les zéros.14 Table 5: étape 4 : Trouver la cellule de valeur minimum non-couverte par une ligne. 14 Table 6: étape 4 : recaler la valeur pour les cellules basées sur cette valeur minimum .14 Table 7: étape 4 : déterminer le nombre minimal de lignes.14 Table 8: étape 5 : déterminer la solution optimale.15 Table 9: le coût minimal de G1, G2.15 Table 10 : La matrice de coûts entre deux graphes G1, G2.

29 Table 11: Résumé des données de graphes des caractéristiques.43 Table 12: Les taux de reconnaissance pour deux méthode PMDED et PMDGP. 45 Table 13: La valeur moyenne de précision, rappel selon la méthode Hu_Dist. 46 Table 14 : La valeur moyenne de précision, rappel selon la méthode Hu_Allen. 47 Table 15: La valeur moyenne de précision, rappel selon la méthode Shape_Allen.

48 Table 16: La valeur moyenne de précision, rappel selon la méthode Shape_Dist.49 Table 17: La comparaison des méthodes d'étiquetage des noeuds, des arcs.50 Table 18: Comparaison nos résultats avec les résultats de Marçal [51].spotting NGUYEN Quoc Toan – Promotion 13 Page 7 TIEU LUAN MOI download : skknchat@gmail.1 Problématique Reconnaissance de symbole est une des applications importantes dans le domaine de la reconnaissance de formes qui est appliqué dans plusieurs domaines comme l'architecture, la cartographie, l'électronique, la mécanique etc. En raison des types de documents graphiques sont trop large, chacune d’entre eux possèdent un ensemble caractéristique de symboles propres, il n'est pas facile de trouver une définition précise d'un symbole. Dans une manière très générale, un symbole peut être défini comme une entité graphique avec un sens particulier dans le contexte d'un domaine d'application spécifique. Il y a un grand nombre d'approches ont été proposées pour la reconnaissance des symboles.

Chacune d’entres elles possèdent des propriétés qui lui sont propres et ne peut s’appliquer qu’à certains contextes, réunissant certaines conditions. Dans notre cas, nous utilisons la méthode basées sur le graphe pour représenter les images de documents techniques et de symbole demandé en des graphes. Chaque nœud du graphe représente une composante connexe dans l’image de document. La relation entre deux composantes connexes est matérialisée dans un graphe de « voisinage ».

Le problème de la reconnaissance de symbole est tourné en une question d’isomorphisme de sous graphe, afin de trouver les sous-graphes qui correspondent à des symboles graphiques.2 Objectif et contribution du stage L'objectif de stage est dans un premier temps d'étudier le problème de la correspondance de graphes « Graph Matching », les mesures de calculer la distance entre deux graphes. Et puis, nous proposons une méthode de mise en correspondance de graphes fondée sur l’assignement de sous-graphes de longueur l. Ensuite nous construisons un protocole de test en classifications basé sur les prototypes de graphes en utilisant la méthode K plus proche voisins (K-NN) basé sur notre méthode de mise en correspondance de graphes. Enfin, nous créons une application de type reconnaissance de symbole basé sur le graphe pour trouver toutes les localisations d’un symbole dans un plan donné.