# Robust junction detector in line-drawing images and time-efficient feature indexing in feature vector space

The Anh Pham

► To cite this version:

The Anh Pham. Robust junction detector in line-drawing images and time-efficient feature indexing in feature vector space. Computer Science [cs]. Université de Tours, 2013. English. NNT: tel-04006532

HAL Id: tel-04006532

https://theses.hal.science/tel-04006532

Submitted on 1 Mar 2023

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.

Public Domain
UNIVERSITÉ FRANÇOIS RABELAIS DE TOURS

ÉCOLE DOCTORALE MIPTIS

Laboratoire d'Informatique (EA 6300)

THÈSE présentée par :

The Anh PHAM

soutenue le : 27 novembre 2013

pour obtenir le grade de : Docteur de l'université François - Rabelais de Tours

Discipline/ Spécialité : INFORMATIQUE

Détection robuste de jonctions et points d'intérêt dans les
images et indexation rapide de caractéristiques dans un
espace de grande dimension

THÈSE DIRIGÉE PAR :

RAMEL Jean-Yves Professeur, Université François Rabelais de Tours

CO-ENCADRANTS :

DELALANDRE Mathieu Maître de Conférences, Université François Rabelais de Tours

BARRAT Sabine Maître de Conférences, Université François Rabelais de Tours

RAPPORTEURS :

TABBONE Salvatore-Antoine Professeur, Université de Lorraine, France.

OGIER Jean-Marc Professeur, Université de La Rochelle, France.

JURY :

LLADOS Josep Professeur, Université Autonoma de Barcelone, Espagne.

TABBONE Salvatore-Antoine Professeur, Université de Lorraine, France.

OGIER Jean-Marc Professeur, Université de La Rochelle, France.

KISE Koichi Professeur, Université Osaka Prefecture, Japon.

RAMEL Jean-Yves Professeur, Université François Rabelais de Tours

DELALANDRE Mathieu Maître de Conférences, Université François Rabelais de Tours

BARRAT Sabine Maître de Conférences, Université François Rabelais de Tours
<figure><img src="image_1.png" /></figure>
Acknowledgments

"Gratitude is the sign of noble souls."

– Aesop

First of all, I would like to present my warmest regards to my advisors: Dr. Mathieu Delalandre, Dr. Sabine Barrat, and Professor Jean-Yves Ramel. I am delighted and I feel privileged to be supervised by you all. All the achievement that I have obtained during my PhD are due to your patience, openness and devotion provided to me during the past three years. I appreciate so very much all the open discussion that we have exchanged with each other through a huge number of reading groups during this thesis. I feel blessed to keep forever all your kind guidance, great efforts, and considerable enthusiasm at the bottom of my heart.

I am grateful to the reviewers for taking time to give me valuable comments and suggestions on this manuscript. Despite of my exhaustive effort on fulfilling this work, there are still a number of issues that need to be pointed out and corrected by you. Your comments and feedback shall definitely make this dissertation improved considerably.

I musk thank the administration staff of Laboratory of Computer Science (François Rabelais University of Tours) for their pretty kind assistance and support during three years of my thesis research. Thank you very much for making easier all the administrative works involved in my thesis and part of my life here in Tours. In particular, on behalf of Vietnamese students at Polytech'Tours, I would like to present my special thanks to Professor Jean-Charles Billaut for his openness, kindness, and infinite help and support. I am definitely sure that you all are very friendly, open-hearted, and helpful people that I have ever had the change of knowing you.

Thank you very much all my friends. When I first came here, everything is new and strange for me, but you have helped me a lot. You make me more and more familiar to the new environment. You gave me the chance to participate in our excellent PhD student network in which we can freely discuss about our work and share our ideas together. I realize that you all are very friendly, intelligent, and humorous people. I sincerely hope we shall have the chance to meet together in the future.

At last, I would like to thank the people from my personal side. I am thankful to Vietnam International Education Development (VIED)<fnref n="1" /> for awarding scholarship to fulfill

<footnote n="1">¹www.vied.vn</footnote>
my PhD research. Many thanks to my affiliation in Vietnam, Hong Duc University (HDU)<fnref n="2" />,
for making all the arrangements to allow me to concentrate entirely on my PhD research
abroad. Big thanks to Vietnamese Student Association in Tours and Blois (AEViVaL)<fnref n="3" /> for
your support and promoting me as a vice-president during two years in the past. Thanks a
million to the association of Touraine-Vietnam<fnref n="4" /> for your considerable encouragement and
assistance. Special thanks to my little family, parents and brothers. Your love and moral
support actually made me go through the crucial and difficult phases of this thesis. Thank
you so very much!

November 27th, 2013 (Tours, France).

The Anh Pham

<footnote n="2">²www.hdu.edu.vn</footnote>

<footnote n="3">³Association des Etudiants Vietnamiens du Val de Loire (AEViVaL): www.aevival.fr</footnote>

<footnote n="4">⁴www.touraine-vietnam.fr</footnote>
# Résumé

Les caractéristiques locales sont essentielles dans de nombreux domaines de l'analyse d'images comme la détection et la reconnaissance d'objets, la recherche d'images, etc. Ces dernières années, plusieurs détecteurs dits locaux ont été proposés pour extraire de telles caractéristiques. Ces détecteurs locaux fonctionnent généralement bien pour certaines applications, mais pas pour toutes. Prenons, par exemple, une application de recherche dans une large base d'images. Dans ce cas, un détecteur à base de caractéristiques binaires pourrait être préféré à un autre exploitant des valeurs réelles. En effet, la précision des résultats de recherche pourrait être moins bonne tout en restant raisonnable, mais probablement avec un temps de réponse beaucoup plus court. En général, les détecteurs locaux sont utilisés en combinaison avec une méthode d'indexation. En effet, une méthode d'indexation devient nécessaire dans le cas où les ensembles de points traités sont composés de milliards de points, où chaque point est représenté par un vecteur de caractéristiques de grande dimension.

Malgré le succès des nombreuses méthodes proposées dans la littérature pour la mise en place de tels détecteurs, aucune approche robuste de détection au sein des images de trait ne semble exister. Par conséquent, la première contribution de cette thèse est de proposer une telle approche. Plus précisément, une nouvelle méthode de détection de jonctions dans les images de trait est présentée. La méthode proposée possède plusieurs caractéristiques intéressantes. Tout d'abord, cette méthode est robuste au problème de déformation des jonctions. De plus, cette méthode peut détecter plusieurs jonctions dans une même zone, supportant ainsi les cas de détection multiple. Ensuite, les jonctions sont détectées avec peu d'erreurs de localisation, caractérisant ainsi la précision de la méthode. La méthode proposée a également une faible complexité algorithmique, lui permettant ainsi de supporter des applications à fort coût de calcul comme la localisation, la recherche ou la reconnaissance de symboles. Enfin, elle est invariante aux transformations géométriques habituelles (rotation, changement d'échelle et translation) et robuste aux déformations communes rencontrées dans les images de documents (comme le bruit d'impression, la basse résolution et artefacts de compression).

Des expériences approfondies ont été menées pour étudier le comportement de la méthode proposée. Celle-ci a été comparée à deux méthodes référentes de l'état de l'art. Les résultats ont montré que la méthode proposée surclasse significativement les approches de l'état de l'art. De plus, cette méthode s'est avérée utile pour la réalisation d'applications de plus haut-niveau. En effet, une application de localisation de symboles a été développée, démontrant que les jonctions détectées pouvaient être un support essentiel à l'extraction des autres primitives graphiques composant le document, permettant ainsi une localisation
et une reconnaissance robuste des symboles.

La seconde contribution de cette thèse traite de l'indexation de caractéristiques. Les méthodes de recherche de plus proches voisins rapides sont devenues un besoin crucial pour de nombreux systèmes de recherche ou de reconnaissance. Bien que de nombreuses techniques d'indexation aient été proposées dans la littérature, leurs performances de recherche restent limitées à certains domaines d'application seulement. De plus, les méthodes existantes, qui sont efficaces dans le cas de la recherche approximative de plus proches voisins, s'avèrent moins efficaces pour ce qui est de la recherche exacte. Les limites de ces méthodes nous ont conduits à proposer un algorithme d'indexation avancé. L'algorithme d'indexation proposé fonctionne aussi bien pour les tâches de recherche approximative que de recherche exacte de plus proches voisins. Des expériences approfondies ont été menées afin de comparer l'algorithme proposé à plusieurs méthodes de l'état de l'art. Ces tests ont montré que l'algorithme proposé améliore significativement les performances de recherche, pour différents types de caractéristiques, par rapport aux méthodes auxquelles notre algorithme a été comparé.

Enfin, les codes source des deux ont été rendus disponibles pour l'intérêt des chercheurs.

**Mots clés :** Détection de jonctions, caractérisation de jonctions, détection de points d'intérêt, documents graphiques, images de trait, recherche approximative de plus proches voisins, indexation de caractéristiques, arbres de clustering.
Abstract

Local features are of central importance to deal with many different problems in image
analysis and understanding including image registration, object detection and recognition,
image retrieval, etc. Over the years, many local detectors have been presented to detect
such features. Such a local detector usually works well for some particular applications
but not all. Taking an application of image retrieval in large database as an example,
an efficient method for detecting binary features should be preferred to other real-valued
feature detection methods. The reason is easily seen: it is expected to have a reasonable
precision of retrieval results but the time response must be as fast as possible. Generally,
local features are used in combination with an indexing scheme. This is highly needed for
the case where the dataset is composed of billions of data points, each of which is in a
high-dimensional feature vector space.

Despite the success of many local detectors in the literature, no robust approach to detect local features in line-drawing images seems to exist. Therefore, the first contribution of this dissertation attempts to bring such an approach. Particularly, a new method for junction detection and characterization in line drawing images is presented. The proposed approach has many favorable features. First, it is robust to the problem of junction distortion. Second, it has the ability of detecting and handling multiple junctions at a given crossing zone. Third, the junctions are detected with a small error of location, highlighting like this method precision. Fourth, the proposed approach is time-efficient supporting different time-critical applications such as symbol spotting/retrieval/recognition. Finally, it is stable to common geometry distortions (e.g., rotation, scaling, and translation) and can resist some typical noise in document images (e.g., produced by scanners, re-sampling or compression algorithms) with a satisfactory level.

Extensive experiments were performed to study the behavior of the proposed approach.
Comparative results were also provided where the proposed approach gives much better
results than two other state-of-the-art methods. Furthermore, the usefulness of the de-
tected junctions is shown at application level. For this concern, an application to symbol
localization is developed. This application shows that the junction features are useful,
distinctive, and can be used to support the problem of symbol localization/spotting in a
very efficient way.

The second contribution of this thesis is concerned with the problem of feature indexing.
Fast proximity search is a crucial need of many recognition/retrieval systems. Although
many indexing techniques have been introduced in the literature, their search performance
is limited to the application domains where a very high search precision is expected (e.g.,
> 90%). Besides, the existing methods work less efficiently for the case of exact nearest neighbor search. The limitations of these methods have led us to propose an advanced indexing algorithm. The proposed indexing algorithm works really well for both the tasks of exact/approximate nearest neighbor search. Extensive experiments are carried out to evaluate the proposed algorithm in comparison with many state-of-the-art methods. These experiments clearly show that a significant improvement of search performance is achieved by the proposed indexing algorithm for different types of features.

At last, the source codes of our two contributions are made publicly available for the interest of researchers.

**Keywords:** Junction Detection, Junction Characterization, Junction Distortion, Topology Correction, Edge Grouping, Dominant Point Detection, Graphical Documents, Line-Drawings, Approximate Nearest Neighbor Search, Feature Indexing, Locality-Sensitive Hashing, Clustering trees.
# CONTENTS

<table><tbody><tr><td>2.4.1</td><td>Evaluation metric and protocol</td><td>90</td></tr><tr><td>2.4.2</td><td>Baseline methods</td><td>91</td></tr><tr><td>2.4.3</td><td>Datasets</td><td>91</td></tr><tr><td>2.4.4</td><td>Comparative results</td><td>92</td></tr><tr><td>2.5</td><td>Discussion</td><td>99</td></tr><tr><td><b>3</b></td><td><b>Application to symbol localization</b></td><td><b>103</b></td></tr><tr><td>3.1</td><td>Introduction</td><td>103</td></tr><tr><td>3.2</td><td>Document decomposition</td><td>105</td></tr><tr><td>3.3</td><td>Keypoint matching</td><td>107</td></tr><tr><td>3.4</td><td>Geometry consistency checking</td><td>109</td></tr><tr><td>3.5</td><td>Experimental Results</td><td>111</td></tr><tr><td>3.6</td><td>Discussion</td><td>114</td></tr><tr><td><b>II</b></td><td><b>Feature indexing in high-dimensional vector space</b></td><td><b>117</b></td></tr><tr><td><b>4</b></td><td><b>State-of-the-art in feature indexing</b></td><td><b>119</b></td></tr><tr><td>4.1</td><td>Introduction</td><td>119</td></tr><tr><td>4.2</td><td>Space-partitioning-based methods</td><td>122</td></tr><tr><td>4.3</td><td>Clustering-based methods</td><td>128</td></tr><tr><td>4.4</td><td>Hashing-based methods</td><td>132</td></tr><tr><td>4.5</td><td>Other methods</td><td>136</td></tr><tr><td>4.6</td><td>Discussion</td><td>139</td></tr><tr><td><b>5</b></td><td><b>An efficient indexing scheme based on linked-node m-ary tree (LM-tree)</b></td><td><b>141</b></td></tr><tr><td>5.1</td><td>Introduction</td><td>141</td></tr><tr><td>5.2</td><td>The proposed algorithm</td><td>142</td></tr><tr><td>5.2.1</td><td>Construction of the LM-tree</td><td>142</td></tr><tr><td>5.2.2</td><td>Exact nearest neighbor search in the LM-tree</td><td>145</td></tr><tr><td>5.2.3</td><td>Approximate nearest neighbor search in the LM-tree</td><td>147</td></tr><tr><td>5.3</td><td>Experimental results</td><td>149</td></tr><tr><td>5.3.1</td><td>ENN search evaluation</td><td>151</td></tr><tr><td>5.3.2</td><td>ANN search evaluation</td><td>151</td></tr><tr><td>5.3.3</td><td>Parameter tuning</td><td>154</td></tr><tr><td>5.4</td><td>Application to image retrieval</td><td>157</td></tr><tr><td>5.5</td><td>Discussion</td><td>159</td></tr><tr><td><b>Conclusions</b></td><td></td><td><b>161</b></td></tr></tbody></table>
List of Tables

<table><tbody><tr><td>1.1</td><td>Related work for junction detection in computer vision</td><td>33</td></tr><tr><td>1.2</td><td>Edge-grouping-based methods for junction detection in CV</td><td>34</td></tr><tr><td>1.3</td><td>Performance evaluation of the junction detectors.</td><td>42</td></tr><tr><td>1.4</td><td>Parametric-based methods for junction detection in CV</td><td>43</td></tr><tr><td>1.5</td><td>Related work for junction detection in document image analysis</td><td>50</td></tr><tr><td>1.6</td><td>Comparison of different skeletonization approaches</td><td>51</td></tr><tr><td>1.7</td><td>Skeleton-based methods for junction detection</td><td>52</td></tr><tr><td>1.8</td><td>Contour-based methods for junction detection</td><td>60</td></tr><tr><td>1.9</td><td>Tracking-based methods for junction detection</td><td>67</td></tr><tr><td>2.1</td><td>Datasets used in our experiments</td><td>92</td></tr><tr><td>2.2</td><td>Comparison of the dominant point detection rates for three scenarios.</td><td>97</td></tr><tr><td>2.3</td><td>Report of the processing time (ms) and the number of detected junctions (in brackets).</td><td>98</td></tr><tr><td>3.1</td><td>Dataset used for symbol spotting in GREC2011.</td><td>112</td></tr><tr><td>3.2</td><td>Experimental results of our system (%).</td><td>112</td></tr><tr><td>3.3</td><td>The detail of the SESYD (floorplans) dataset.</td><td>113</td></tr><tr><td>3.4</td><td>The results of our system for the SESYD (floorplans) dataset.</td><td>114</td></tr><tr><td>3.5</td><td>Comparison of recent methods for symbol localization on the SESYD (floorplans-01) dataset.</td><td>114</td></tr><tr><td>4.1</td><td>Indexing methods based on space partitioning in ℝ<sup>k</sup> vector space</td><td>121</td></tr><tr><td>4.2</td><td>Indexing methods based on clustering in ℝ<sup>k</sup> vector space.</td><td>129</td></tr><tr><td>4.3</td><td>Hashing-based indexing methods in ℝ<sup>k</sup> vector space.</td><td>133</td></tr><tr><td>4.4</td><td>Other indexing methods in ℝ<sup>k</sup> vector space.</td><td>137</td></tr><tr><td>4.5</td><td>Summary of different approaches for feature indexing in vector space</td><td>140</td></tr><tr><td>5.1</td><td>Report of search time and fraction of searched points for the 5-NN LM-trees.</td><td>159</td></tr></tbody></table>
List of Figures

<table>
  <tbody>
    <tr>
      <td>1</td>
      <td>A typical architecture of a real time image processing system.</td>
      <td>21</td>
    </tr>
    <tr>
      <td>2</td>
      <td>Example of the SURF keypoints detected for: (a) a natural image; (b) a line-drawing image; (the image (a) is reprinted from [Bay et al., 2008]).</td>
      <td>23</td>
    </tr>
    <tr>
      <td>3</td>
      <td>Example of the detected junction points (small red dots) and junction arms (green straight lines) for a line-drawing image.</td>
      <td>24</td>
    </tr>
    <tr>
      <td>4</td>
      <td>Example of the junction points and junction characterization in the CV field; (reprinted from [Xia, 2011]).</td>
      <td>24</td>
    </tr>
    <tr>
      <td>5</td>
      <td>Example of multiple junction detection: (a) an input image containing a X-crossing zone and its skeleton (thin white lines); (b) the vectorization presentation of (a) with three detected junctions; (reproduced from [Hilaire and Tombre, 2006]).</td>
      <td>25</td>
    </tr>
    <tr>
      <td>1.1</td>
      <td>The detected junctions (small red dots) and junction arms (yellow lines); (reprinted from [Bergevin and Bubel, 2004]).</td>
      <td>32</td>
    </tr>
    <tr>
      <td>1.2</td>
      <td>Different approaches for junction detection in CV and DIA.</td>
      <td>32</td>
    </tr>
    <tr>
      <td>1.3</td>
      <td>Illustration of the process of branch extraction and grouping: (A) a ROI in input image; (B) image decomposition using PCA; (C) the candidate branches and junction; (reproduced from [Bergevin and Bubel, 2004]).</td>
      <td>36</td>
    </tr>
    <tr>
      <td>1.4</td>
      <td>The detected junctions (small red dots) and junction arms (white thin lines); (reprinted from [Bergevin and Bubel, 2004]).</td>
      <td>36</td>
    </tr>
    <tr>
      <td>1.5</td>
      <td>Illustration of orientation vector propagation and curvature update: (a) original orientation vectors; (b) v&#775;<sub>i</sub> is the orientation vector at the low curvature endpoint P<sub>i</sub> (i = 1, 2), and propagation of orientation vector starting from P<sub>i</sub>; (c) update of the curvature for every line point (e.g., P<sub>3</sub>) between the two point P<sub>1</sub> and P<sub>2</sub> using the difference in direction of the two vectors: v&#775;<sub>1</sub> and v&#775;<sub>2</sub> (e.g., dash lines); (reproduced from [Deschênes and Ziou, 2000]).</td>
      <td>37</td>
    </tr>
    <tr>
      <td>1.6</td>
      <td>(a) Vector fields (gray short bars) and streamlines (green lines); (b) the partial distance between two streamlines at a relative tracking size s; (c) local scale estimation; (reproduced from [Faas and van Vliet, 2007]).</td>
      <td>39</td>
    </tr>
    <tr>
      <td>1.7</td>
      <td>(a) An input image with a Y-junction; (b) three anchor points q<sub>1</sub>, q<sub>2</sub>, q<sub>3</sub>; (reprinted from [Laganiere and Elias, 2004]).</td>
      <td>39</td>
    </tr>
    <tr>
      <td>1.8</td>
      <td>(a) An original image; (b) the detected contours (thin lines) and junctions (asterisk marks); (reprinted from [Maire et al., 2008]).</td>
      <td>41</td>
    </tr>
  </tbody>
</table>
<table>
  <tbody>
    <tr>
      <td>1.9</td>
      <td>(a) An input image; (b) the detected corners and junctions (small black dots on the right figure); (reprinted from [Förstner, 1994]).</td>
      <td>45</td>
    </tr>
    <tr>
      <td>1.10</td>
      <td>Illustration of a piecewise constant model of a 3-junction: (a) the junction model in the image plane; (b) the junction model formulated as a piecewise constant function; (reproduced from [Parida et al., 1998]).</td>
      <td>45</td>
    </tr>
    <tr>
      <td>1.11</td>
      <td>Examples of detected junctions: (a) 2-junction points; (b) 3-junction points; (reprinted from [Parida et al., 1998]).</td>
      <td>47</td>
    </tr>
    <tr>
      <td>1.12</td>
      <td>(a) An ideal L-junction point; (b) the ideal response of a 1D profile for the L-junction point; (reproduced from [Sluzek, 2001]).</td>
      <td>47</td>
    </tr>
    <tr>
      <td>1.13</td>
      <td>(a) The skeleton of an input image; (b) the lines 1 and 2 are grouped (similar to the lines 3 and 4) based on their similar spatial continuity (dash line); (reproduced from [Nagasamy and Langrana, 1990]).</td>
      <td>52</td>
    </tr>
    <tr>
      <td>1.14</td>
      <td>(a) The skeleton of an input image; (b) the initial dominant points; (c) the remaining dominant points after primitive fitting; (reproduced from [Nagasamy and Langrana, 1990]).</td>
      <td>53</td>
    </tr>
    <tr>
      <td>1.15</td>
      <td>The process of refining the location of a dominant point; (reproduced from [Janssen and Vossepoel, 1997]).</td>
      <td>54</td>
    </tr>
    <tr>
      <td>1.16</td>
      <td>Fraction of the obtained vectorization where the false anchor points are marked with the circles (reproduced from [Janssen and Vossepoel, 1997]).</td>
      <td>55</td>
    </tr>
    <tr>
      <td>1.17</td>
      <td>Illustration of the Criterion A: (a) correct fusion of two junction points P<sub>1</sub> and P<sub>2</sub>; (b) wrong fusion of two junction points P<sub>1</sub> and P<sub>2</sub>.</td>
      <td>56</td>
    </tr>
    <tr>
      <td>1.18</td>
      <td>(a, b) The uncertainty domains (gray zones) defined for a line and a circle primitive; (c) illustration of the junction optimization process; (reproduced from [Hilaire and Tombre, 2001]).</td>
      <td>56</td>
    </tr>
    <tr>
      <td>1.19</td>
      <td>Illustration of primitive grouping: (a) P joins Q by L<sub>P</sub>; (b) P joins Q by L<sub>P</sub> Q joins P by L<sub>Q</sub>; (reproduced from [Hilaire and Tombre, 2006]).</td>
      <td>57</td>
    </tr>
    <tr>
      <td>1.20</td>
      <td>Illustration of the process of skeleton and junction optimization: (a) an input image with its skeleton; (b) the results of skeleton segmentation process; (c) the connectivity graph; (d-f) the process of graph simplification; (g) the final graph; (f) the final skeleton and junction points; (reproduced from [Hilaire and Tombre, 2006]).</td>
      <td>58</td>
    </tr>
    <tr>
      <td>1.21</td>
      <td>Another possible interpretation of the crossing structure in [Hilaire and Tombre, 2006]: (a) an input crossing structure; (b) an interpretation for the crossing in (a) where two T-junctions are constructed.</td>
      <td>59</td>
    </tr>
    <tr>
      <td>1.22</td>
      <td>Illustration of the process of progressive extension of line fitting; (reproduced from [Hori and Tanigawa, 1993]).</td>
      <td>61</td>
    </tr>
    <tr>
      <td>1.23</td>
      <td>Illustration of the process of correcting the junction location; (reproduced from [Hori and Tanigawa, 1993]).</td>
      <td>62</td>
    </tr>
    <tr>
      <td>1.24</td>
      <td>Illustration of the process of gap filling and junction generation after contour segment pairing: (a) without common vector and (b) with common vector; (reproduced from [Han and Fan, 1994]).</td>
      <td>63</td>
    </tr>
  </tbody>
</table>
<table>
  <tbody>
    <tr>
      <td>1.25</td>
      <td>Illustration of the process of filling gap and junction generation; (reproduced from [Fan et al., 1998]).</td>
      <td>64</td>
    </tr>
    <tr>
      <td>1.26</td>
      <td>The obtained skeletal vectors and junctions in the work of [Fan et al., 1998]. The displacement of skeletal vectors and junctions are marked by the circles; (reproduced from [Fan et al., 1998]).</td>
      <td>65</td>
    </tr>
    <tr>
      <td>1.27</td>
      <td>Illustration of the contour matching process (see explanation in the text); (reprinted from [Ramel et al., 2000]).</td>
      <td>65</td>
    </tr>
    <tr>
      <td>1.28</td>
      <td>Construction of the structural graph (reprinted from [Ramel et al., 2000]).</td>
      <td>66</td>
    </tr>
    <tr>
      <td>1.29</td>
      <td>The branch construction process: (a) circle following; (b) branch construction; (reproduced from [Van Nieuwenhuizen and Bronsvoort, 1994]).</td>
      <td>68</td>
    </tr>
    <tr>
      <td>1.30</td>
      <td>Illustration of the junction recovery process: (a) conflict of the width run and the width preservation; (b) a new invalid tracking point; (c) a new valid tracking point on the current branch; (d) a new valid tracking point on a different branch; (reproduced from [Dori and Liu, 1999]).</td>
      <td>69</td>
    </tr>
    <tr>
      <td>1.31</td>
      <td>Illustration of MIC tracking process; (reproduced from [Chiang et al., 1998]).</td>
      <td>70</td>
    </tr>
    <tr>
      <td>1.32</td>
      <td>Bar tracking process (a) and intersection preservation deletion (b); (reproduced from [Song et al., 2002]).</td>
      <td>71</td>
    </tr>
    <tr>
      <td>2.1</td>
      <td>Overview of the proposed approach.</td>
      <td>76</td>
    </tr>
    <tr>
      <td>2.2</td>
      <td>Some examples in which Teh-Chin's technique fails to correctly determine the ROS. Top row: (a) ROS(p<sub>i</sub>) = d for any point p<sub>i</sub> on a circle with radius R, where l<sub>d</sub> = 2R; (b) ROS(p<sub>i</sub>) = +∞ (i.e., p<sub>i</sub> is the middle point of segment q<sub>1</sub>q<sub>2</sub> and thus l<sub>k+d</sub> > l<sub>k</sub> for any k, d > 0); (c) ROS(p<sub>i</sub>) = 1 (i.e., l<sub>k+1</sub> = l<sub>k</sub>). Bottom row: expected ROS for each case in the top row.</td>
      <td>79</td>
    </tr>
    <tr>
      <td>2.3</td>
      <td>(a) An original image; (b) the detected dominant points (small dots) and the corresponding local scales (small circles).</td>
      <td>81</td>
    </tr>
    <tr>
      <td>2.4</td>
      <td>(a) An input image with the detected CCDZs (gray connected components) and reliable line segments (thin white lines); (b) the local topology defined for a CCDZ.</td>
      <td>82</td>
    </tr>
    <tr>
      <td>2.5</td>
      <td>Incorrect convergence of the junction optimization step in [Maire et al., 2008]: (a) four line segments with the same length; (b) the detected junction, which is the same distance from the lines 1 and 2; (c) the expected junctions.</td>
      <td>83</td>
    </tr>
    <tr>
      <td>2.6</td>
      <td>Outline of our junction optimization algorithm.</td>
      <td>84</td>
    </tr>
    <tr>
      <td>2.7</td>
      <td>(a) An image with its skeleton; (b) the CCDZ(s) and the reliable line segments; (c) the local topology configuration extracted for one CCDZ (marked by Z<sub>d</sub>); (d) the first cycle of steps {1, 2, 3, 4, 5}: the junction J<sub>1</sub> is found corresponding to the cluster containing line segments {1, 3, 4}; (e) the second cycle: the junction J<sub>2</sub> is found corresponding to the second cluster comprised of lines {1, 2}; (f) the third cycle: the junction J<sub>3</sub> is found corresponding to the third cluster of {1, 5}; (g) topology correction for three junctions.</td>
      <td>86</td>
    </tr>
    <tr>
      <td>2.8</td>
      <td>Detected junctions (red dots) and local scales (circles).</td>
      <td>87</td>
    </tr>
  </tbody>
</table>
<table>
  <tbody>
    <tr>
      <td>2.9</td>
      <td>(a) A CCDZ cropped from Figure 2.7 with the superposition of three clusters; (b) detected junctions {J<sub>1</sub>, J<sub>2</sub>, J<sub>3</sub>}; (c) the detected junctions are classified as a 3-junction even though J<sub>2</sub> and J<sub>3</sub> are constructed from two clusters, {1, 2} and {1, 5}, respectively, each of which only contains two local line segments.</td>
      <td>88</td>
    </tr>
    <tr>
      <td>2.10</td>
      <td>Corresponding junction matches between a query symbol (left) and a cropped document (right).</td>
      <td>89</td>
    </tr>
    <tr>
      <td>2.11</td>
      <td>The evaluation strategy applied to each detector.</td>
      <td>91</td>
    </tr>
    <tr>
      <td>2.12</td>
      <td>Repeatability scores of three systems on rotation change (a), and scaling change (b), where location error is set at 4 pixels.</td>
      <td>93</td>
    </tr>
    <tr>
      <td>2.13</td>
      <td>Repeatability scores of three systems for setA, setB, setC, and setD of GREC2011.</td>
      <td>94</td>
    </tr>
    <tr>
      <td>2.14</td>
      <td>Junctions detected (red dots) by the proposed system for setC ((a) and (b)) and setD ((c) and (d)) of GREC11. False positives caused by context noise in setD are marked by dashed-line boxes.</td>
      <td>95</td>
    </tr>
    <tr>
      <td>2.15</td>
      <td>Repeatability scores of three systems for SESYD low resolution dataset (a), and the UMD logo dataset (b).</td>
      <td>96</td>
    </tr>
    <tr>
      <td>2.16</td>
      <td>Junctions detected (red dots) by the proposed system for few Chinese characters and logo images.</td>
      <td>97</td>
    </tr>
    <tr>
      <td>2.17</td>
      <td>Impact of the parameters E<sub>min</sub> and E<sub>max</sub>: the repeatability score is computed on the setC.</td>
      <td>98</td>
    </tr>
    <tr>
      <td>2.18</td>
      <td>Detected junctions for a synthetic symbol with different levels of noise.</td>
      <td>100</td>
    </tr>
    <tr>
      <td>2.19</td>
      <td>Detected junctions for a real musical score image.</td>
      <td>100</td>
    </tr>
    <tr>
      <td>2.20</td>
      <td>Detected junctions for part of an electronical image.</td>
      <td>101</td>
    </tr>
    <tr>
      <td>2.21</td>
      <td>Detected junctions for a mechanical-text image.</td>
      <td>102</td>
    </tr>
    <tr>
      <td>3.1</td>
      <td>Overview of our symbol localization system.</td>
      <td>105</td>
    </tr>
    <tr>
      <td>3.2</td>
      <td>Basic primitive decomposition and description.</td>
      <td>106</td>
    </tr>
    <tr>
      <td>3.3</td>
      <td>Keypoint-based representation of a simple document image.</td>
      <td>107</td>
    </tr>
    <tr>
      <td>3.4</td>
      <td>The matching process of L-keypoints (a) and A-keypoints (b).</td>
      <td>108</td>
    </tr>
    <tr>
      <td>3.5</td>
      <td>An example of context distortion of the detected junctions: a 3-junction p in (a) is distorted as a 5-junction q in (b).</td>
      <td>108</td>
    </tr>
    <tr>
      <td>3.6</td>
      <td>Geometry consistency checking: (a) the matches before checking; (b) the matches after checking.</td>
      <td>111</td>
    </tr>
    <tr>
      <td>3.7</td>
      <td>An example of symbol localization: a query symbol (left) and the detected instances of the query (red bounding boxes).</td>
      <td>115</td>
    </tr>
    <tr>
      <td>3.8</td>
      <td>The system fails to detect the symbol "outlet" (left) due to the omission of the E-keypoint and the displacement of the L-keypoint on the instance of the symbol (right).</td>
      <td>115</td>
    </tr>
    <tr>
      <td>3.9</td>
      <td>Few examples of the detected symbols of our system.</td>
      <td>116</td>
    </tr>
  </tbody>
</table>
<table>
  <tbody>
    <tr>
      <td>4.1</td>
      <td>Different approaches for feature indexing in vector space.</td>
      <td>120</td>
    </tr>
    <tr>
      <td>4.2</td>
      <td>Illustration of data partitioning of the KD-tree in an 2D space: the resulting KD-tree (left) and the corresponding partitioned space (right).</td>
      <td>122</td>
    </tr>
    <tr>
      <td>4.3</td>
      <td>Illustration of the searching process in the KD-tree: only the regions whose bounding boxes do intersect the circle are inspected.</td>
      <td>123</td>
    </tr>
    <tr>
      <td>4.4</td>
      <td>Illustration of computing the lower bound using the cosine rule of the PA-tree (reprinted from [McNames, 2001]).</td>
      <td>124</td>
    </tr>
    <tr>
      <td>4.5</td>
      <td>The construction of the R-tree (right) for a dataset (left); (reprinted from [Guttman, 1984]).</td>
      <td>125</td>
    </tr>
    <tr>
      <td>4.6</td>
      <td>The construction of the SR-tree (reprinted from [Katayama and Satoh, 1997]).</td>
      <td>127</td>
    </tr>
    <tr>
      <td>4.7</td>
      <td>Illustration of the rule 1 (a) and rule 2 (b) for tree pruning; (reproduced from [Fukunaga and Narendra, 1975])</td>
      <td>128</td>
    </tr>
    <tr>
      <td>4.8</td>
      <td>Construction of the vocabulary tree with the branching factor K = 3 (reprinted from [Nister and Stewenius, 2006]).</td>
      <td>130</td>
    </tr>
    <tr>
      <td>4.9</td>
      <td>Illustration of searching process in the multi-probe LSH algorithm: g<sub>i</sub>(q) is the hash values of the query q (green buckets), and g<sub>i</sub>(q) + Δ<sub>i</sub> are the adjacent buckets for probing (reprinted from [Lv et al., 2007]).</td>
      <td>135</td>
    </tr>
    <tr>
      <td>4.10</td>
      <td>Example of the hashing algorithm in [Auclair, 2009]: Two points x<sup>1</sup> and x<sup>2</sup> are quite similar in a 8-dimensional space; D(x<sup>1</sup>) and D(x<sup>2</sup>) are the sorted vectors with respect to the distinctive dimensions; Key(x<sup>1</sup>) and Key(x<sup>2</sup>) are the obtained hash keys where K = 2 in this example; (reprinted from [Auclair, 2009]).</td>
      <td>136</td>
    </tr>
    <tr>
      <td>4.11</td>
      <td>Illustration of multi-level indexing in [Roy et al., 2012].</td>
      <td>138</td>
    </tr>
    <tr>
      <td>4.12</td>
      <td>Shapeme descriptor: (a) an input image; (b) shapeme representation of (a); (reproduced from [Mori et al., 2001]).</td>
      <td>139</td>
    </tr>
    <tr>
      <td>5.1</td>
      <td>Illustration of the iterative process of data partitioning in an 2D space: the 1<sup>st</sup> partitioning is applied to the dataset X, and the 2<sup>nd</sup> partitioning is applied to the subset X<sub>6</sub> (the branching factor m = 6).</td>
      <td>143</td>
    </tr>
    <tr>
      <td>5.2</td>
      <td>Illustration of the lower bound computation.</td>
      <td>146</td>
    </tr>
    <tr>
      <td>5.3</td>
      <td>Illustration of our bandwidth search with b = 1: X<sub>6</sub> is an intermediate node of the considering path, and its adjacent sibling nodes, X<sub>1</sub> and X<sub>5</sub>, will also be searched; if q is too close to the centroid (e.g., inside the circle for the case of X<sub>6</sub>), then all of the sibling nodes of X<sub>6</sub> will be searched.</td>
      <td>149</td>
    </tr>
    <tr>
      <td>5.4</td>
      <td>Exact search performance for the SIFT (a) and GIST (b) features.</td>
      <td>152</td>
    </tr>
    <tr>
      <td>5.5</td>
      <td>Approximate search performance for the SIFT (a) and GIST (b) features.</td>
      <td>152</td>
    </tr>
    <tr>
      <td>5.6</td>
      <td>ANN search performance as a function of the dataset size: (a) the SIFT datasets (search precision = 96%); (b) the GIST datasets (search precision = 95%).</td>
      <td>153</td>
    </tr>
    <tr>
      <td>5.7</td>
      <td>Evaluation of distance error ratio for ANN search applied to SIFT (a) and GIST (b) features.</td>
      <td>155</td>
    </tr>
  </tbody>
</table>
<table>
  <tbody>
    <tr>
      <td>5.8</td>
      <td>Search performance as a function of the pruning factor: precision is set to 95%, 90%, and 80% for both the SIFT and GIST features.</td>
      <td>156</td>
    </tr>
    <tr>
      <td>5.9</td>
      <td>Several example images of ornamental drop caps in the dataset.</td>
      <td>157</td>
    </tr>
    <tr>
      <td>5.10</td>
      <td>Search quality of the k-NN LM-trees (a), and search quality versus speedup of the k-NN LM-trees (b).</td>
      <td>159</td>
    </tr>
    <tr>
      <td>5.11</td>
      <td>Few examples of the retrieval results: for each query in the left, the top ranked 5-NNs are showed for the ideal linear scan (the top row) and our LM-trees (the bottom row).</td>
      <td>160</td>
    </tr>
  </tbody>
</table>
# Introduction

This dissertation concerns two emerging problems of (i) junction detection and characterization in line-drawing images and (ii) feature indexing in high-dimensional vector space. The former problem is addressed in the context of graphical line-drawing images which is an active sub-area of document image analysis and understanding. The useful applications typically include symbol recognition, symbol localization and spotting, symbol indexing and retrieval, sketch-based retrieval of architectural/electronic images, etc. The later problem is addressed in a more general context of feature vector space in which its applications are broad including those in both computer vision (CV) and document image analysis (DIA) fields. This chapter aims at providing a brief introduction of the context of this thesis. Particularly, three main points are discussed including a general discussion about the CV and DIA fields; the important role of local feature detector, descriptor, and indexing; and the motivation of this work.

## Introduction to CV and DIA

Computer vision is a vast and active field of computer science in which its interests are broad including the methods for acquiring, processing, analyzing, understanding, segmenting, and recognizing images from the real world [Morris, 2004]. Some typical applications of the CV field include robot navigation, security monitoring and surveillance, bio-informatics recognition system, people tracking and counting, content-based image retrieval (CBIR), gesture recognition, etc. Among various topics of the CV field, pattern recognition (PR) could be considered as a core and interdisciplinary part whose key goal is to assign a label for a given input data. Generally, pattern recognition algorithms involves in three crucial tasks of object segmentation, feature extraction, and classification. These algorithms are often categorized as structural-based and statistical-based approach. The structural-based approach involves in constructing the structural relations among the primitives. These relations can be represented by the means of syntactics and graphs. Primitive matching is then performed using a grammar parsing process [Tanaka, 1995] or a subgraph matching algorithm [Damiand et al., 2009]. In contrast to the structural pattern recognition methods, the statistical-based approach offers many powerful computation models of clustering, classification, and regression. These models have been proved to be highly efficient to perform many different tasks of object detection, spotting, and recognition. An extensive review of statistical pattern recognition methods could be found in [Jain et al., 2000]. Several attempts have been investigated to combine the advantages of both the approaches.
This is referred to graph embedding as presented in [Riesen et al., 2007, Luqman, 2012].

Document image analysis is another active research field of computer science whose interests are mainly focused on processing, understanding, and recognizing document images. These document images could be acquired by digital machines like scanners, cameras, electronic pen-input devices. Some typical applications of DIA include optical character recognition (OCR), writer identification, signature verification, mathematical formula identification and recognition, historical document retrieval, symbol detection, localization and spotting, etc. Among many different research themes of DIA, the problem of using graphic information is an intensive research activity. Generally, graphics recognition concerns assigning a class label for an input object given a list of pre-defined graphics objects. In DIA, graphic objects can be lines, arcs, arrows, logos, symbols, etc. Earlier works on graphics recognition were considered as a post-process of a vectorization system. In this context, the main goal of graphics recognition is to group the raw results from a vectorization system into different types of graphic objects [Wenyin and Dori, 1998].

Recent works on graphics recognition have moved towards symbol recognition, retrieval and spotting, and performance evaluation [Tombre, 2006]. Logos and trademarks can be considered as a special type of symbol. In this sense, interesting topics are logo detection [Zhu and Doermann, 2007], logo spotting [Rusinol and Llados, 2009a], and logo retrieval [Rusinol and Llados, 2010]. Emerging topics on this field have focused on fast logo retrieval under large-scale datasets [Jain and Doermann, 2012]. On the other hand, in line drawings a symbol can be defined as a graphical entity with a particular meaning in the context of specific application domain. Symbols can serve in different applications including document re-engineering, understanding, classification and retrieval [Rusinol et al., 2010]. A survey of existing works of symbol recognition on logical diagrams, engineering drawings, and maps was reported in [LLados et al., 2002]. Comparative results have been reported throughout a series of symbol recognition contests, which concern the aspects of performance evaluation [Delalandre et al., 2008].

Nowadays, due to the fast growing of portable digital imaging devices (e.g., cameras, smartphones, electronic camera-pen systems), the acquisition of document images becomes much more convenient, and thus the huge expansion of document data emerges. In this expeditious evolution, the real challenges in DIA have shifted to the problems of mass of data. Camera-based document image analysis (CBDAI) has emerged as a very hot research topic [Kim, 2005, Liang et al., 2005, Yin et al., 2007, Vajda et al., 2011]. Large-scale digitization and analysis of historical documents and artworks has also increasingly focused [Lins et al., 2011, Yang et al., 2011, Embley et al., 2011, Landon, 2013]. Open challenges involve the activities of constructing, indexing, and browsing of mass digitized documents. In practices, over the past decade, the interests have moved towards real time document analysis systems. Few examples of such systems include real time graphical symbol spotting in camera-acquired documents [Rusinol et al., 2013], real time camera-based document retrieval [Takeda et al., 2011], fast word spotting in large-scale digital libraries [Roy et al., 2012].

Although the DIA methods involve in handling the document images, there exists some common themes that can be reused from the well established theories in the CV field. Particularly, many powerful statistical computation models such as support vector machine
(SVM), Bayesian networks, neural network, AdaBoost, and hidden Markov model (HMM), can take part of the OCR systems [Parvez and Mahmoud, 2013], writer and signature verification systems [Liwicki et al., 2011], handwriting recognition systems [Graves et al., 2009]. Besides, the structural-based methods using graphs have been extensively used in many different areas of DIA such as clustering of ancient ornamental letters [Jouili et al., 2010], symbol spotting [Qureshi et al., 2008], symbol recognition [Llados et al., 2001], image retrieval [Jouili and Tabbone, 2012]. Moreover, since real time camera-based document analysis has emerged as an important activity in the DIA field, traditional techniques using local features and indexing in the CV field can be employed as the promising solutions [Jain and Doermann, 2012, Takeda et al., 2012].

## Local feature detection, description, and indexing

To support a wide range of applications in both the CV and DIA fields, local features have been emerged as an important role in image analysis and recognition [Tuytelaars, 2007]. Especially, local features are very useful to address time-critical applications. Typically, there are three main challenges involved in processing local features: local detector, local descriptor, and indexing. Figure 1 gives an illustration of a general system architecture which is commonly employed in both the CV and DIA fields [Lowe, 2004, Leibe et al., 2006, Jain and Doermann, 2012, Takeda et al., 2012]. We shall base our discussion on this system architecture to explain in detail the context of our work and the connection of the two parts of this work. The discussion of each component of this architecture is also given in the following.

<figure><img src="image_2.png" /><figcaption>Figure 1: A typical architecture of a real time image processing system.</figcaption></figure>

The first component is served as local keypoint detector. Local keypoints or local features have emerged as a crucial research domain in the literature [Tuytelaars, 2007]. Over the years, a large number of methods for local feature detection have been proposed and widely used in various areas of activity such as image registration and object detection, matching, recognition and retrieval. A *local interest point* or *keypoint*, by definition in the CV field [Tuytelaars, 2007], is a point-like feature in image, which differs from its immediate neighborhood in terms of some image properties such as intensity, color, orientation, texture, curvature. Keypoint detection is one of the most important topics in the CV field
since keypoints are considered as useful features to address the problems of image matching, object recognition and spotting, etc. For that reason, many techniques have been proposed in the literature to detect different types of keypoint. Some examples of well-known keypoint detectors are Harris-Corner [Harris and Stephens., 1988], SIFT [Lowe, 2004], LOG [K.Mikolajczyk and Schmid, 2001], SURF [Bay et al., 2008].

Once the keypoints are detected, each keypoint is characterized by a descriptor as indicated by the second component in Figure 1. Typically, a descriptor for a given keypoint is constructed by extracting the local features within a local neighborhood. The common local features are intensity, color, texture, orientation and shape distribution. The features extracted for a given keypoint are then often represented by a feature vector or keypoint descriptor. Some well-known examples of different types of descriptors are shape-based descriptors (e.g., ShapeContext [Belongie et al., 2002], Shapeme [Mori et al., 2001]), binary-based descriptors (e.g., BRIEF [Calonder et al., 2010], ORB [Rublee et al., 2011]), and real-value descriptors (e.g., GLOH [Mikolajczyk and Schmid, 2005], SIFT [Lowe, 2004]). It is highly expected for a keypoint descriptor to meet the following basic properties: rotation-, scale-, and translation-invariant. Depending on the application domains, other complicated properties which might be needed are illumination-, affine- and viewpoint-invariant. Furthermore, one of the most critical property of a keypoint descriptor is the dimensionality. It is highly desired to design a keypoint descriptor such that it is distinctive enough while retaining the dimensionality as low as possible. The reason of this is to gain efficiency while performing the keypoint matching procedure. A reasonable dimensionality of a local keypoint descriptor would be, perhaps, less than one hundred.

The third component aims at addressing the problem of fast matching to support time-critical applications. Although the processing time can be addressed by reducing the dimensionality of the keypoint descriptor, this process may not significantly decrease time complexity of the system. Moreover, in many applications, the descriptor's dimensionality could be sufficiently high (e.g., > 100) in order to make the descriptors highly discriminative. Therefore, a promising solution for fast matching of the descriptors would be the use of an efficient indexing scheme. Basically, an indexing algorithm is formulated as the task of reorganization of the data, such that it is able to produce quickly the query of proximity search [Beis and Lowe, 1997]. Some efficient indexing schemes in the literature are hashing-based approach (e.g., LHS [Indyk and Motwani, 1998], Kernelized LSH [Kulis and Grauman, 2009]), clustering-based approach (e.g., vocabulary K-means tree [Nister and Stewenius, 2006], randomized K-medoids trees [Muja and Lowe, 2012]), and space-partitioning-based approach (e.g., KD-tree [Friedman et al., 1977], principal axis tree [McNames, 2001]).

## A new contribution on junction detection and characterization in line-drawings

Even though a large number of methods have been introduced to deal with different problems of keypoint detector, descriptor and indexing, these methods might not work well for a particular kind of binary line-drawing images. Two main reasons are attributed to this fact. First, it is very often the case that graphical line-drawing images are produced
in the binary form in which the segmentation of background and foreground is obviously
clear. Second, the crucial content of graphical line-drawing images is constituted by line-
like objects or elongated shapes in which the line thickness is rarely thin (i.e., 1-pixel).
Particularly, a typical shape in line-drawing images would be composed of a set of adjacent
black pixels. Such a shape could be treated as a homogeneous region in CV. Hence,
edge detection in line-drawing images is a trivial task and the transition between the
background and the foreground is high and virtually similar in magnitude for every edge
point. As a result, the common keypoint detectors in the CV field, like blob-point detector
for instance, would produce a significant increase of the detected keypoints. Furthermore,
the distinctiveness of the detected keypoint would be highly dropped because of the poor
distribution of the local features (e.g., only two values: foreground and background) around
the detected keypoints.

To illustrate these issues, Figure 2 provides an example of the detected SURF key-
points for a typical natural image (a) and a line-drawing image (b). It was showed in
[Bay et al., 2008] that the detected SURF keypoints for natural images are distinctive and
robust. However, from Figure 2 (b), it is evident that lot of keypoints are detected when
applying the SURF detector for a line-drawing image even the image is composed of few
details.

<figure><img src="image_3.png" /><figcaption>Figure 2: Example of the SURF keypoints detected for: (a) a natural image; (b) a line-drawing image; (the image (a) is reprinted from [Bay et al., 2008]).</figcaption></figure>

The arguments above raise an interesting question: what would be the suitable features
for such kind of graphical line-drawing images? The answer is naturally related to the con-
tent of line-drawing images which are mainly composed of line-like objects. Hence, the
expected features would be basic primitives including straight lines, arcs, circles, curves,
quadrilaterals, etc. In fact, there is a strong evidence that much of work has been performed
to extracted these primitives in the literature [Han and Fan, 1994, Dori and Liu, 1999,
Song et al., 2002, Hilaire and Tombre, 2006]. Furthermore, these primitives have been ex-
tensively employed as interesting features to address different applications such as engineer-
ing drawings recognition [Yan and Wenyin, 2003] and symbol recognition/retrieval/spotting
[Dosch and LLados, 2004, Qureshi et al., 2008, Rusinol et al., 2010]. Among many differ-
ent types of basic primitives, junction point is an important feature in line-drawing images
[Hilaire and Tombre, 2006, Zuwala and Tabbone, 2006]. Junction point serve as a "bridge" point connecting different primitives. Therefore, the accurate detection of other primitives is highly dependent on the correct detection of junction points. From Figure 3, it can be noted that these junction points can provide effective and efficient features for describing such a line-drawing document image.

<figure><img src="image_4.png" /><figcaption>Figure 3: Example of the detected junction points (small red dots) and junction arms (green straight lines) for a line-drawing image.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Figure 4: Example of the junction points and junction characterization in the CV field; (reprinted from [Xia, 2011]).</figcaption></figure>

By definition in the CV field, a junction point is defined as the place of intersection of at least two different edge directions in the image [Bergevin and Bubel, 2004]. In addition to the detected junctions, it is desired to extract the junction parameters or junction characteristics such as the number of branches of each junction, the strength and orientation of each junction branch, and the local scale of the junction. It is worth mentioning that there is a close relationship between the junction points and corner points. Although the
terminologies of junction and corner are often interchangeably used in the CV field with a little distinction, there in fact exists some important differences. In the first place, a junction point could be considered as a corner point (i.e., L-, X-, Y-, T-junction), but the converse is not necessarily true (e.g., an endpoint is most likely to be detected as a corner point but this point is clearly not a junction point). In the other place, the characteristic of each junction point also distinguishes a junction detector from a corner detector. As argued in [Laganiere, 2004], a corner detector works as a two-stage process of estimating a measure of corner response for every pixel, followed by a second stage of thresholding to select the strongest corner candidates. On the contrary, a junction detector should simultaneously perform both the tasks of detection and characterization or classification of junction points.

Different approaches have been introduced to deal with the detection of junction points. In the first place, the CV methods detect junction points as the meeting points of edge lines. Such methods are not well adapted to graphical line-drawing images because of several main reasons. First, few works [Faas and van Vliet, 2007, Bergevin and Bubel, 2004, Deschênes and Ziou, 2000] discuss about junction characterization, which is very important for junction features. Second, all of these methods are limited to single junction detection, whereas it is very often for line-drawings to encounter a crossing zone which contains multiple junctions as illustrated in Figure 5. Most importantly, the perception of a junction point in the context of graphical line-drawing images is quite different from that in the CV field. In line-drawings, junctions are treated as the intersections of median lines, whereas the CV methods detect junctions as the intersections of the edges. This point, in fact, makes the CV methods unsuitable.

<figure><img src="image_6.png" /><figcaption>Figure 5: Example of multiple junction detection: (a) an input image containing a X-crossing zone and its skeleton (thin white lines); (b) the vectorization presentation of (a) with three detected junctions; (reproduced from [Hilaire and Tombre, 2006]).</figcaption></figure>

On the other place, the problem of junction detection for graphical line-drawing images has been mainly embedded in a vectorization system [Fan et al., 1998, Song et al., 2002, Hilaire and Tombre, 2006]. The obtained results are therefore subjected to the error-prone caused by the raster-to-vector conversion process. Moreover, such a vectorization system has been known to be sensitive to setting parameters, and present difficulties when heterogeneous primitives (e.g., straight lines, arcs, curves, and circles) appear within a single
document. Knowledge about the document content (objects, entities, document layout) must be included and derived using an appropriate strategy to make the system more robust at the cost of adaptability.

Considering all the aforementioned points, it can be noted that introducing a suitable and efficient junction detection approach dedicated to line-drawing images would be highly appreciated. Therefore, the first contribution of this dissertation is an attempt to bring a robust and accurate approach for detecting and characterizing the junction points in line-drawings. The proposed approach is evaluated using a wide corpus set of line-drawings. Extensive performance evaluation is performed to study the behaviors of the proposed system at different aspects. Comparative results are provided to demonstrate the strengths and weaknesses of our system. Additional experiments at the application level are also given to prove that our junction detector is robust and discriminated enough to be used in the applications of symbol localization and spotting.

## A new contribution on feature indexing

As illustrated in Figure 1, it is very often the case that the detected keypoints would be associated with some features or local descriptors. Typically, these feature vectors are computed using statistical histogram of local features within the neighborhoods around the detected keypoints. In order to be highly distinctive for differentiating different objects, the dimensionality of a feature vector must be sufficiently high. However, this raises an expensive computation cost for the subsequent steps of matching the feature vectors and object retrieval/recognition. An efficient solution for this problem is known as feature indexing. Hence, the second contribution of this dissertation is concerned with the problem of indexing in feature vector space. Although a large number of indexing algorithms have been proposed in the literature, few of them (e.g., randomized KD-trees [Muja and Lowe, 2009], hierarchical K-means tree [Muja and Lowe, 2009], randomized clustering trees [Muja and Lowe, 2012], and LHS-based schemes [Lv et al., 2007, Kulis and Grauman, 2009]) have been well validated on extensive experiments to give satisfactory performance of approximate nearest neighbor (ANN) search on some specific benchmarks. However, the search performance of these indexing algorithms is still limited to the cases (e.g., word spotting, face detection, document retrieval) where a pretty high search precision is desired (e.g., > 90%). Especially, for some applications (e.g., logo recognition, handwriting identification, signature verification) where exact nearest neighbor (ENN) search is required, these algorithms give little or even no better search performance compared to the brute-force search.

To overcome such shortcomings, an advanced indexing algorithms in feature vector space is proposed as the second main contribution in this dissertation. Particularly, a new and efficient indexing algorithm is presented based on a linked-node m-ary tree (LM-tree) structure. The proposed indexing algorithm works really well for both the ENN and ANN search. Extensive experiments show that the proposed algorithm gives a significant improvement of search performance, compared to the state-of-the-art indexing algorithms including randomized KD-trees, hierarchical K-means tree, randomized clustering trees, and multi-probe LHS scheme. To further demonstrate the outstanding search performance
of the proposed indexing algorithm, an application of image retrieval is developed. In this work, a wide corpus set of historical books of ornamental graphics is used to stress our indexing system. Performance evaluation, carried out on this dataset, show the outstanding search efficiency of the indexing system.

## Organization of the thesis

The rest of this dissertation is organized into two main parts and one conclusion chapter. A brief introduction of these parts is given hereafter.

* **Part 1:** In this part, the contribution on junction detection and characterization in line-drawing images is presented in three chapters as follows:

- Chapter 1: A detailed review of state-of-the-art methods in junction detection is presented in this chapter. The main characteristics of each method, the connection among them, and the missing issues requiring further treatments are carefully discussed.

- Chapter 2: The proposed approach for junction detection in graphical line-drawing images is described in great detail in this chapter. Complexity evaluation of the proposed system is included. Extensive experiments are performed to study the behaviors of the proposed system in comparison with other methods. Finally, the main contributions of the proposed junction detector are summarized and the shortcomings are pointed out to identify further extensions.

- Chapter 3: In this chapter, the usefulness of the proposed junction detector is evaluated at application level. For this purpose, an application to symbol localization in line-drawing images is investigated. This application shows that the junction features are useful and distinctive, and support the problem of symbol localization/spotting in a very efficient way.

* **Part 2:** In this part, two chapters are presented for the second contribution of this thesis on feature indexing. These chapters are shortly described as follows.

- Chapter 4: A deep review on state-of-the-art methods for feature indexing in high-dimensional feature vector space is presented. The main ideas, advantages, and weaknesses of each method are thoroughly studied. The highlight of an advanced contribution for feature indexing is given as the conclusion of this chapter.

- Chapter 5: In this chapter, a novel indexing algorithm called linked-node m-ary tree (LM-tree) is presented. The main processes of tree construction and tree traverse are carefully described to deal with both the ENN and ANN search. Extensive experiments are carried out in comparison with the state-of-the-art indexing schemes. At last, an application of image retrieval is provided to demonstrate the effectiveness and efficiency of the proposed indexing algorithm.
* **Conclusions**: In this chapter, the main contributions of the dissertation are summarized. The merits and limitations of this work are also reviewed. Finally, possible lines of improvement are given for future work.
# Part I

## Junction detection in line-drawing images
<figure><img src="image_7.png" /></figure>
# Chapter 1

# State-of-the-art in junction detection

This chapter presents a deep review of state-of-the-art methods for junction detection. The merits and weaknesses of each method are discussed in great detail. The interconnections among them are evaluated and the potential link to our subsequent contribution is also justified.

## 1.1 Introduction

In the CV field, the junction points are often detected by finding the prominent points in the image at which the boundaries of the adjacent regions meet as illustrated in Figure 1.1. The edges meeting at a junction point are regarded as the arms of the junction and are used to characterize junctions into different types such as L-, T-, or X-junction.

It has been shown in the literature [Parida et al., 1998, Hansen and Neumann, 2004, Biederman, 1986] that junction/corner points are important features for image analysis. They are critical features for object recognition as suggested in [Parida et al., 1998]. In the work presented in [Hansen and Neumann, 2004, Biederman, 1986], the authors studied and demonstrated the importance of corner and junction points for human object recognition in a number of psychophysical experiments. Especially, the work in [Biederman, 1986] showed that object perception of line drawings is severely degraded when corners or high curvature points are removed. In contrast, this perception is largely preserved when the parts of low curvature are eliminated. Junction features have been used to address different applications in the literature. [Mordohai and Medioni, 2004] employed junction inference for figure completion. [Rubin, 2001] performed a deep study of junction features for surface completion and contour matching. The use of junction features for robotic weld seam inspection has
<figure><img src="image_8.png" /><figcaption>Figure 1.1: The detected junctions (small red dots) and junction arms (yellow lines); (reprinted from [Bergevin and Bubel, 2004]).</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 1.2: Different approaches for junction detection in CV and DIA.</figcaption></figure>

been proposed in [Sluzek, 2001]. Various works [Liu et al., 1999, Lin and Tang, 2002] for stroke extraction and Chinese character recognition have been performed based on junction detection. A comprehensive study of the role of junction features can be found in [Hansen and Neumann, 2004].

Despite abundance of the methods proposed in the CV field [Bergevin and Bubel, 2004, Köthe, 2003, Maire et al., 2008, Parida et al., 1998, Deschênes and Ziou, 2000] to detect junctions, these methods can not directly applied to a particular kind of graphical line-drawing images. The main reason is realized on the fact that the definition of junction is different from that in the CV field. Particularly, a junction point is treated as the intersection of at least two line-like primitives and the problem of junction detection is usually formalized as finding the intersections of median lines in images. However, some specific techniques in CV may be adapted to be part of a junction detector in line-drawings. Therefore, it is of crucial important to identify such possible favourable techniques of the CV for junction detection.
In line-drawing images, junction points are processed with the regard to median lines. Unfortunately, median line extraction is not a trivial task because of the well-known problem of skeleton/junction distortion. One important reason of this problem is due to the line thickness of the shapes. Line-drawings are often acquired using digitization devices and thus the line thickness is rarely perfect (e.g., 1-pixel thickness). Consequently, the median lines extracted at crossing zones are distorted leading to the false formalization of junction points. For these reasons, dedicated methods [Dori and Liu, 1999, Hilaire and Tombre, 2006, Liu et al., 1999, Song et al., 2002] for junction detection in line-drawings have been mainly considered as a post-processing of a vectorization process.

This chapter describes state-of-the-art methods for junction detection including those for natural images in CV and graphical line-drawing images in DIA. Our goal here is to identify the potential techniques in CV that may be adapted to be part of a junction detector in line-drawings, and to make the connection between the both fields. These methods are briefly outlined as shown in Figure 1.2 depending on the application domains and groups of methods. For the CV-based methods, the junction detectors can be classified into two main approaches: edge grouping and parametric modeling. The other methods are dedicated to line-drawing images including skeleton-based, contour-based and tracking-based approaches. In the following sections, we will discuss the most representative works for each of these classes.

# 1.2 Junction detection in computer vision

## 1.2.1 Introduction

A number of techniques have been proposed in CV field to deal with the problem of junction detection. These methods are often classified [Parida et al., 1998] into two categories: edge-grouping-based and parametric-based. The former approaches are typically composed of two stages. The first stage detects the edges in image by computing one or several intensity-based gradient maps. The obtained edge maps are grouped in the second stage to generate hypotheses about junction parameters (e.g., junction branches and junction size). For the parametric-based methods, a junction model is first defined for representing the junction characteristics. Next, the junction characteristics are derived by fitting them to some energy functions. A brief list of the methods for junction detection in CV is presented on Table 1.1, and they are detailed in the following sections.

<table><caption>Table 1.1: Related work for junction detection in computer vision</caption><thead><tr><td>Approach</td><td>References</td></tr></thead><tbody><tr><td>Edge grouping</td><td>[Deschênes and Ziou, 2000, Köthe, 2003, Maire et al., 2008, Bergevin and Bubel, 2004, Laganiere and Elias, 2004, Xia, 2011]</td></tr><tr><td>Parametric-based</td><td>[Förstner, 1994, Parida et al., 1998, Sluzek, 2001, Tabbone et al., 2005, Kalkan et al., 2007]</td></tr></tbody></table>
<table><caption>Table 1.2: Edge-grouping-based methods for junction detection in CV</caption><thead><tr><th>Method</th><th>Scale invariant</th><th>Multi-detection</th><th>Junction characteristics</th><th>Edge and branch detection</th><th>Branch grouping</th><th>Performance evaluation</th></tr></thead><tbody><tr><td>Bergevin and Bubel, 2004</td><td>No</td><td>No</td><td>Yes</td><td>Local orientation gradient filters, binary tree representation, spatial dispersion and occupancy rate</td><td>Adaptive distance threshold</td><td>None<sup>a</sup></td></tr><tr><td>Deschênes and Ziou, 2000</td><td>No</td><td>No</td><td>No</td><td>Local curvature, orientation propagation</td><td>High curvature point detection, threshold-dependent</td><td>None</td></tr><tr><td>Köthe, 2003</td><td>No</td><td>No</td><td>No</td><td>Structural and boundary tensor</td><td>Local maxima of the intrinsically 2D energy function, threshold-dependent</td><td>None</td></tr><tr><td>Faas and van Vliet, 2007</td><td>Partial</td><td>No</td><td>Yes</td><td>Local vector field of structural tensor, streamline divergence</td><td>Centroid of intersection region</td><td>None</td></tr><tr><td>Laganiere and Elias, 2004</td><td>No</td><td>No</td><td>No</td><td>Local directional maxima of gradients (radial lines)</td><td>#Radial lines ≥ 2 and radial line strength > threshold</td><td>None</td></tr><tr><td>Maire et al., 2008</td><td>No</td><td>No</td><td>No</td><td>Local features (e.g., brightness, color, texture gradients) and global features (e.g., generalized eigenvectors)</td><td>EM-based optimization, fixed threshold of local window size</td><td>BSDS dataset, F-score = 0.41</td></tr><tr><td>Xia, 2011</td><td>Yes</td><td>Yes</td><td>Yes</td><td>Local normalization of gradients</td><td>a contrario theory-based decision, adaptive threshold selection</td><td>BSDS dataset, F-score = 0.37</td></tr></tbody></table>

<footnote><sup>a</sup>Actually, these experiments have been performed on few test images as illustrative example without characterization of the method.</footnote>
1.2.2 Edge-grouping-based methods

These methods are typically composed of two main stages. The first stage extracts
different edge maps in image by computing one or several intensity-based gradient maps.

The obtained edge maps are grouped in the second stage to generate hypotheses about junction branches including the strength, orientation, and the number of the radial lines. Next, junction points are reconstructed as the meeting points of the junction branches. A summary of these methods are presented on Table 1.2 (page 34) along with the merits and limitations of each method. We have based our discussion on different criteria as follows:

* Scale invariant: the ability of detecting the junctions at different scales.

* Multi-detection: the ability of detecting multiple junctions at a given zone.

* Junction characteristics: the ability of extracting junction parameters including the number of junction branches, the strength and orientation of each branch, etc.

* Edge and branch detection: how the method detects the edge and junction branches.

* Branch grouping: how the edges are merged to form the junctions.

* Performance evaluation: which datasets and metrics are used to evaluate the performance of the method.

In [Bergevin and Bubel, 2004], the edge points are first detected using several local oriented-based filters [Heitger, 1995]. The detected edge points, which are of similar amplitude and orientation, are grouped to form the potential junction branches. Next, a branch grouping algorithm is presented applying to each region of interest (Figure 1.3 (A)). This algorithm constructs a binary tree for hierarchically representing the local structure of the edge points within the region of interest. At each level of the tree, the highest variance axis obtained from principal component analysis (PCA) is selected to partition the edge points into two sub-sets (Figure 1.3 (B, G₁₁, G₂₁)). This continues as long as the split axis of the underlying subset satisfies the stopping criteria: it has a low spatial dispersion and high occupancy rate. The spatial dispersion measures the uniform distribution of the edge points and the occupancy rate measures the connectivity of the edge points projected on the splitting axis.

Once the tree is constructed, the potential junction branches are detected as the split-
ting axes obtained during the tree's construction (Figure 1.3 (G₂₂, G₃₂)), whereas the
rest of data are considered as noise (Figure 1.3 (G₃₁)). The constructed branches are
finally analyzed to make a hypothesis about junction point (Figure 1.3 (C)). To do so,
the junction branches are first segmented as constant curvature primitives correspond-
ing to straight line segments and arc segments. An adaptive threshold computed from
contour density and average primitive fitting error is used to select the branches that
form a junction point centered on the region of interest under consideration. Junction
characterization is also obtained in this stage by determining the characterized primitives
passing through the junction location. The junction position is then further improved to
obtain a sub-pixel accuracy using an adaptation of the junction localization operator in
<figure><img src="image_10.png" /><figcaption>Figure 1.3: Illustration of the process of branch extraction and grouping: (A) a ROI in input image; (B) image decomposition using PCA; (C) the candidate branches and junction; (reproduced from [Bergevin and Bubel, 2004]).</figcaption></figure>

[Förstner and Gülch, 1987]. The demonstration of the proposed method on several simple images are interesting but it is sensitive to a number of predefined parameters: the size of the region of interests, and the thresholds of classifying the low spatial dispersion and high occupancy rate. Figure 1.4 shows some examples of the detected junctions.

<figure><img src="image_11.png" /><figcaption>Figure 1.4: The detected junctions (small red dots) and junction arms (white thin lines); (reprinted from [Bergevin and Bubel, 2004]).</figcaption></figure>

[Deschênes and Ziou, 2000] presented a method for detecting specific junction types in gray-level images including L-, X-, Y-, and T-junction, and line terminations. Given the lines extracted from input image using some basic edge operator, the proposed method computes the local curvature measure at each point and then partitions the line points into two classes (i.e., low curvature point and high curvature point) based on a fixed threshold
$t_c$. Next, a new concept of low curvature endpoint is defined as a line point which has a low curvature and belongs to a local neighborhood of a high curvature point. In Figure 1.5, $P_0$ is a high curvature point, and $P_1$ and $P_2$ are two low curvature endpoints. Starting from every low curvature endpoint, the propagation of orientation vector is applied to update the curvature of every line point (e.g., $P_3$ in Figure 1.5(c)). This is accomplished by compensating a weight computed as the difference in curvature of the orientation vectors of the starting low curvature endpoint and another low curvature endpoint (e.g., $\vec{v}_1$ and $\vec{v}_2$ in Figure 1.5(c)). Particularly, the curvature is updated for every line point $P(x, y)$ between the two endpoints $P_1$ and $P_2$ as follows:

$$C(P) = 1 + C_0(P) + s(\vec{v}_1, \vec{v}_2) \qquad (1.1)$$

where $C_0(P)$ is the old curvature at $P$, and $s(\vec{v}_1, \vec{v}_2)$ is computed as:

$$s(\vec{v}_1, \vec{v}_2) = 1 - \frac{|\vec{v}_1 \cdot \vec{v}_2|}{||\vec{v}_1||||\vec{v}_2||} \qquad (1.2)$$

<figure><img src="image_12.png" /><figcaption>Figure 1.5: Illustration of orientation vector propagation and curvature update: (a) original orientation vectors; (b) $\vec{v}_i$ is the orientation vector at the low curvature endpoint $P_i$ ($i = 1, 2$), and propagation of orientation vector starting from $P_1$; (c) update of the curvature for every line point (e.g., $P_3$) between the two point $P_1$ and $P_2$ using the difference in direction of the two vectors: $\vec{v}_1$ and $\vec{v}_2$ (e.g., dash lines); (reproduced from [Deschênes and Ziou, 2000]).</figcaption></figure>

After that, the junctions and line terminations are identified by extracting the local maxima of the updated curvatures within a given neighborhood. The results presented on several real and synthetic images show that the proposed method is able to localize accurately the desirable junctions. Several weaknesses of this method are handling the multi-endpoints in a given neighborhood and handling the size of the neighborhood. In addition, some true junctions might be missed as only the point having maximum curvature is selected among the local maxima of each neighborhood. The classification of low/high curvature point is sensitive to the value of $t_c$.

[Köthe, 2003] introduced an integrated system for edge and junction detection with boundary tensor computed based on the responses of polar separable filters. A boundary tensor is a 2×2 matrix constructed from a combination of a structure tensor $T_{odd}$ (i.e., first-order partial derivatives) and a Hessian matrix $T_{even}$ (i.e., second-order partial derivatives)
as follows:

$$ T_{boundary} = T_{odd} + \frac{1}{4} T_{even} = \begin{pmatrix} t_{11} & t_{12} \\ t_{21} & t_{22} \end{pmatrix} \qquad (1.3) $$

Such a tensor can be decomposed into two components:

$$ T_{boundary} = T_{edge} + T_{junction} = (\lambda_1 - \lambda_2)\vec{e}_1\vec{e}_1^T + \lambda_2 \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \qquad (1.4) $$

where $\lambda_1$, $\lambda_2$ are the eigenvalues of $T_{boundary}$, and $\vec{e}_1$ is the unit eigenvector associated with $\lambda_1$.

The first component, $T_{edge}$, encodes the 1-dimensional features (i.e., edge strength and edge orientation) of the current point, while the second component, $T_{junction}$, encodes the 2-dimensional properties such as junction or corner features. Therefore, the junctions can be detected as those points corresponding to the peaks of the second component ($T_{junction}$). This boundary tensor is rotation invariant and provides satisfactory detection rate for some common junction types such as L-, T- and X-junction. However, this approach is subjected to several weaknesses, being scale-dependent and poor localization of the detected junctions.

[Faas and van Vliet, 2007] introduced a streamline method for junction detection and classification in gray-scale images (Figure 1.6). The proposed method first computes vector fields using the eigenvectors corresponding to the smallest eigenvalues of the structure tensors. Next, the vector fields are linked to form the streamlines. More precisely, a streamline is mathematically defined as a curve whose every point is tangent to a local vector field (Figure 1.6(a)). A new measure of partial distance $d_{pq}(s)$ between two streamlines $P$ and $Q$ is defined as the distance of the line connecting two points $P(s)$ and $Q(s)$ where $s$ is a tracking size relative to some pivot point $P(0)$ or $Q(0)$ (Figure 1.6(b)). The basic idea of the junction detection algorithm is that two streamlines originating from $P(0)$ and $Q(0)$ within a local neighborhood of a junction can end up in two different directions with a significant distance $d_{pq}(s)$. By summing up the distances $d_{pq}(s)$ of the streamline passing a pivot point $P(0)$ and the other streamlines within a local neighborhood $N$, a new measure of streamline divergence ($d_p$) is derived as follows:

$$ d_p = \sum_{q \in N} d_{pq} \qquad (1.5) $$

The size of the neighborhood ($N$) is treated as the local scale and determined as the longest diameter, $d_{max}$, of the common zone shared by the incident streamlines (Figure 1.6(c)). The junction locations are then detected as those areas having high responses of the streamline divergence. However, such a measure of streamline divergence is quite sensitive to noise. To alleviate this matter, the authors suggested weighting these responses by the certainty of the Hessian matrix. In this way, the responses of streamline divergence corresponding to the background are degraded close to zero. The junctions are then identified as the centers of gravity of the intersection regions. This method is also subjected to several weaknesses being sensitive to the determination of the pivot points and the selection of the parameter $s$ (i.e., $s = 7, 8$ in their experiments).
<figure><img src="image_13.png" /><figcaption>Figure 1.6: (a) Vector fields (gray short bars) and streamlines (green lines); (b) the partial distance between two streamlines at a relative tracking size *s*; (c) local scale estimation; (reproduced from [Faas and van Vliet, 2007]).</figcaption></figure>

The work in [Laganiere and Elias, 2004] detects the junctions based on intensity gradient. The proposed approach constructs two binary images *B* and *B*<sup>+</sup> as follows:

* *B* is formed by thresholding the gradient image with a threshold *t*<sub>B</sub>.

* *B*<sup>+</sup> is formed by looking for local maxima in the direction of gradient.

Next, for each point *p* ∈ *B*, a list *C*<sub>*A*</sub> containing the anchor points *q*<sub>*i*</sub> ∈ *B*<sup>+</sup> is constructed by choosing the point *q*<sub>*i*</sub> lying in the boundary of the circle centered at the point *p* with a radius *r* (Figure 1.7).

<figure><img src="image_14.png" /><figcaption>Figure 1.7: (a) An input image with a Y-junction; (b) three anchor points $q_1, q_2, q_3$; (reprinted from [Laganiere and Elias, 2004]).</figcaption></figure>

Each line $d_{qp}$ connecting an anchor point $q_i \in C_A$ and the corresponding center point $p$ is treated as a candidate junction branch. A candidate branch $d_{qp}$ is accepted as a valid junction branch if there exists a continuous path of points in $B$ so that the distance from each point to $d_{qp}$ is less than 1 pixel. For such a branch $d_{qp}$, the strength of $d_{qp}$ is defined as the sum of squared distances of each point in $B^+$ to $d_{qp}$. The strength of $d_{qp}$ is then normalized based on the length of $d_{qp}$. Next, every valid junction branch having
the strength less than a threshold $t_s$ is discarded. Finally, the junctions are detected as the points having more than two valid junction branches. In the case of a 2-junction (i.e., junction formed by exact two branches), an additional step is applied to verify that this junction is not a straight line segment. Limited experiments have been provided to demonstrate the performance of the method. This method is sensitive to the selection of the parameters: $t_B$, $t_s$, and $r$.

[Maire et al., 2008] presented a new method for contour and junction detection in natural images. The contours are first detected by combining local features (i.e., brightness, color, texture gradients) and global features (i.e., generalized eigenvectors obtained from spectral clustering) to form a *globalized probability of boundary*. Next, the obtained contours are segmented into a set of straight line segments using a polygon approximation technique. A final process of line segment grouping is performed using an EM-like technique. This iterative process works based on the idea that if we know the position of the junction, the associated line segments passing through this junction could be easily identified and vice versa. The algorithm is therefore composed of two iterative steps: estimating an optimized location of the junction within a local neighborhood and updating the weights based on the distances of the newly derived junction to the contour segments nearby. The main idea of this junction optimization method is outlined below:

* Step 1: Estimate an optimized location $J$ of the junction within a neighborhood $N$:

$$J = \arg \min_{J \in N} \sum_{i=1}^{n} w_i * d(C_i, J) \qquad (1.6)$$

where $C_i$ is a contour segment, $n$ is the number of the contour segments, $w_i$ is the weight associated to the contour $C_i$, and $d(C_i, J)$ is the Euclidean distance from $J$ to $C_i$.

* Step 2: Update the weights based on the strengths (i.e., $|C_i|$) of the contour segments:

$$w_i = |C_i| \cdot \exp\left(\frac{-d(C_i, J)}{\epsilon}\right)^2 \qquad (1.7)$$

where $\epsilon$ is a distance tolerance determined empirically.

* Step 3: Repeat Step 1,2 until the junction $J$ converges to a fixed point or until a number of iterations is done.

This method assumes that each neighborhood $N$ contains at most one junction point and thus it is not able to detect multiple junctions, if any. Besides, it is subjected to high computation load because the size of the neighborhood must be sufficiently large to ensure that it is less impacted by the error-prone introduced by the previous step of contour detection. The authors suggested choosing the neighborhoods around the terminations of the contour segments. In addition, the reweighting step (i.e., Step 2) does not consider the weights accumulated during the previous iterations. This omission may lead to incorrect junction convergence for the case that all the contour segments has the same strength.
The proposed method has been evaluated on the BSDS benchmark dataset<fnref n="1" /> using the F-score metric. The BSDS is composed of 300 natural images whose boundaries have been manually segmented by different human subjects. From the ground-truth segmentations, the 3-junctions were extracted as the places of intersection of at least three regions. The 2-junctions were also extracted as places of high curvature points along the contours hand-drawn by the humans. Combination of these two types of junctions is served as junction ground-truth. Precision, recall, and F-score were employed as evaluation metrics where a true detection is validated if the distance between the detected junction and the ground-truth one is smaller than 6 pixels. The obtained results are quite interesting with F-score = 0.41 compared to the human agreement of F-score = 0.47. An example of detected contours and junctions is shown in Figure 1.8.

<figure><img src="image_15.png" /><figcaption>Figure 1.8: (a) An original image; (b) the detected contours (thin lines) and junctions (asterisk marks); (reprinted from [Maire et al., 2008]).</figcaption></figure>

Recently, [Xia, 2011] introduced the concept of meaningful junctions based on the *a contrario* detection theory originally proposed by [Desolneux et al., 2000]. This detection theory basically states that an observed image feature is meaningful if it is unlikely to occur randomly under some null hypothesis $H_0$. The advantage of the *a contrario* theory is that it provides a way of automatically computing the threshold for creating a binary decision for determining a meaningful junction point. This is accomplished by controlling an expected number of false detections. Scale invariant was achieved by employing a multi-scale approach. Experiment was performed on the BSDS benchmark, and the comparative results are summarized on Table 1.3. One of the advantages of this method is that it requires fewer parameters, while detecting accurate junction points. Although the proposed method employs multi-scale approach to detect the junction, the first step of local normalization of gradient is scale-dependent (the neighborhood size was fixed at 5 × 5). Therefore, the detection rate is sensitive to the parameter tuning. Actually, the proposed method achieved the F-score of 0.38 with respect to the neighborhood size of 11 × 11.

In summary, we will highlight hereafter several key remarks. For performance evaluation, since there is a lack of standard benchmarks for the junction detection algorithms, it gives a rise of difficulties to evaluate the real performances of the existing works. Most of the existing methods performed the experiments on their own and pretty small datasets. No evaluation metrics and no comparative results were reported for performance evaluation

<footnote n="1">¹www.cs.berkeley.edu/projects/vision/grouping/segbench/</footnote>
<table><caption>Table 1.3: Performance evaluation of the junction detectors.</caption><thead><tr><td>System</td><td>Dataset</td><td>F-score</td></tr></thead><tbody><tr><td>[Xia, 2011]</td><td>BSDS</td><td>0.38</td></tr><tr><td>[Maire et al., 2008]</td><td>BSDS</td><td>0.41</td></tr><tr><td>[Harris and Stephens., 1988]</td><td>BSDS</td><td>0.28</td></tr><tr><td>Human agreement</td><td>BSDS</td><td>0.47</td></tr></tbody></table>

except the works of [Maire et al., 2008, Xia, 2011]. Typically, these experimental results were carried out by visually showing the detected junctions for few test images. Although [Maire et al., 2008] have recently provided the BSDS benchmark for the field, limited performance evaluation of different techniques has been carried out. Only [Xia, 2011] reported their results on this benchmark in comparison with the work of [Maire et al., 2008] and a classical Harris corner detector. General speaking, these works achieved quite good results with respect to the human agreement in terms of junction detection. [Maire et al., 2008] obtained better results than the two others probably due to combining local and global cues in contour detection.

It can be concluded that there are two main challenges for the edge-grouping-based junction detectors. The first one concerns the extraction of junction branches from image features such as local curvatures or local gradients [Bergevin and Bubel, 2004, Köthe, 2003, Faas and van Vliet, 2007]. However, these basic features are sensitive to contrast change and noise. To alleviate this problem, [Xia, 2011] normalizes the extracted gradients using the mean and standard deviation of local gradient within a local neighborhood. The obtained results showed that the proposed system is quite robust to the contrast change, but it is subjected to the proper setting of the size of the local neighborhood. [Maire et al., 2008] proposed a more robust approach by combining the local and global cues for contour extraction. They obtained the best results in terms of junction detection for their benchmark dataset.

The second challenge of every edge-grouping-based junction detection method is the selection of junction branches to form a junction. Typically, this is accomplished by thresholding and grouping the survived branches nearby. Consequently, this gives another difficult issue: the selection of a proper distance threshold. A high value of the distance threshold will reduce the false detections but may miss some true junctions, and vice versa. Some methods just empirically fixed these values as in the cases of [Köthe, 2003, Laganiere and Elias, 2004, Maire et al., 2008]. Interestingly, [Xia, 2011] exploited the *a contrario* detection theory for junction branch grouping provided in advance the expected number of false detections. That said, given a specific number of false detections, the junction detector can automatically decide which points are likely to be the useful junctions. [Bergevin and Bubel, 2004] addressed this matter by adaptively deriving the distance thresholds based on the local contour density and average primitive fitting error obtained previously.
<table><caption>Table 1.4: Parametric-based methods for junction detection in CV</caption><thead><tr><th>Method</th><th>Scale invariant</th><th>Multi-detection</th><th>Junction classification</th><th>Junction model</th><th>Fitting criteria</th><th>Performance evaluation</th></tr></thead><tbody><tr><td>Förstner, 1994</td><td>No</td><td>No</td><td>No</td><td>Corner function using average squared gradients</td><td>Local minimum of regularity measure, adaptive threshold selection</td><td>None<sup>a</sup></td></tr><tr><td>Parida et al., 1998</td><td>Yes</td><td>No</td><td>Yes</td><td>Piecewise constant functions</td><td>Local minimum of radial intensity variation, thresholding the relative error of radial variation and fitting energy</td><td>None</td></tr><tr><td>Sluzek, 2001</td><td>No</td><td>No</td><td>No</td><td>1D orientation profile of intensity</td><td>Local peak of the junction profile, fixed threshold dependent</td><td>None</td></tr><tr><td>Kalkan et al., 2007</td><td>No</td><td>No</td><td>Yes</td><td>Harris corner function</td><td>Local minimum of intersection consistency, hard thresholding 1D orientation junction profile</td><td>None</td></tr></tbody></table>

<footnote><sup>a</sup>Actually, these experiments have been performed on few test images as illustrative example without characterization of the method.</footnote>
1.2.3 Parametric-based methods

In the preceding section, we described the methods that detect junctions based on branch detection and branch grouping. In this section, we are going to discuss the most representative parametric-based methods for junction detection. For the parametric-based methods, a junction model is first constructed. This model formalizes the junction parameters including junction’s location, junction’s scale, orientation and magnitude of each junction branch, etc. Next, these parameters are derived by fitting them to one or several energy functions designed to explicitly reflect the junction model.

Table 1.4 summarizes some typical parametric-based methods for junction detection. The first three evaluation criteria have the same interpretation as presented in Table 1.2 (page 34), whereas the last ones indicate the main idea of the parametric-based methods such as the definition of junction model and model fitting. The detail of each method is given in the paragraphs thereafter.

[Förstner, 1994] introduced a general framework for low level feature extraction such as corners, junctions, edge points, and circular symmetric features. Particularly, the authors introduced some local image characteristics such as the average squared gradient and regularity measure. The average squared gradient is defined as the convolution of a 2 × 2 squared gradient matrix to a rotationally symmetric Gaussian function. By analyzing the eigenvalues and eigenvectors of the resulting matrix, the corners and junctions can be detected as those having large values of the two eigenvalues λ₁ and λ₂.

The regularity measure is designed to estimate the location of the junctions and circular symmetric features. Given a local patch centered at p, the regularity measure S(p, σ) is defined as follows:

$$
S(p, \sigma) = \iint d^2(p, q) ||\nabla g(q)||^2 G_{\sigma}(||p - q||) dq \quad (1.8)
$$

where d(p, q) is the Euclidean distance between p and q, and ||∇g(q)|| is the gradient magnitude at q, and G_σ is the Gaussian function.

The accurate location of the junction and corner candidates can be obtained by minimizing the regularity measure within a 3 × 3 window. Figure 1.9 shows an illustrative example where all the corners and junctions are correctly detected. However, in contrast to edge-grouping-based methods, all the steps of the proposed method purely rely on low-level feature extraction without incorporating high-level processing or scene knowledge analysis. Hence, the method is sensitive to noise. To alleviate this problem, image smoothing using Gaussian function can be applied, but it raises another concern of scale selection.

[Parida et al., 1998] formalized a junction model as a small disk of image in which the intensity values are piecewise constants in the incident homogeneous regions (i.e., the wedges) pointing towards the center of the disk (Figure 1.10). Particularly, the junction model involves the following parameters: the central point, the radius of the disk, the number of wedges, the intensity value in each wedges, and the junction branches separating two adjacent wedges.

Typically, a junction model is formalized as an energy function:
<figure><img src="image_16.png" /><figcaption>Figure 1.9: (a) An input image; (b) the detected corners and junctions (small black dots on the right figure); (reprinted from [Förstner, 1994]).</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>Figure 1.10: Illustration of a piecewise constant model of a 3-junction: (a) the junction model in the image plane; (b) the junction model formulated as a piecewise constant function; (reproduced from [Parida et al., 1998]).</figcaption></figure>

$$E = \lambda \Re + \bar{E} \qquad (1.9)$$

The term $\Re$ (i.e., Equation 1.10) is regarded as the radial variation of intensity, and is constructed as the sum of weighted squared gradients within a local neighborhood. The gradient at a given point $(r, \theta)$ is weighted by the squared distance of the center of the neighborhood to that point, where $(r, \theta)$ is polar coordinate of the point.

$$\Re(r) = \int_{0}^{r} \int_{0}^{2\pi} s^{2} \left(\frac{\partial I}{\partial s}\right)^{2} ds d\theta \qquad (1.10)$$

The $\Re(r)$ behaves similar to that of the regularity measure in [Förstner, 1994]: it moves towards a minimum value at a junction location. Therefore, the precise location of a junction can be derived by finding the point which has a minimum $\Re(r)$ within a local neighborhood. Also, the scale of a junction can be estimated by thresholding the relative error $e_s(r)$ defined as follows:
$$e_s(r) = \frac{\Re(r)}{\Re(r+1)} < \tau_{\varpi} \qquad (1.11)$$

where $\tau_{\varpi}$ is a fixed threshold.

The term $\bar{E}$ is used to estimate the junction characteristics including the number of junction branches ($n$), the orientation of each branch $\theta_i$ with $i \in \{1, \dots, n\}$, and the intensity $T_i$ in each junction wedge. These junction parameters are derived using the following procedure:

* Fix the number of junction branches, say that $n$.

* Uniformly sample the range $[0, 2\pi]$ into $d$ regular intervals.

* Explore all possible discretized sets of the angles $\theta_{k_i}$ with $i = 1, \dots, n$, and look for the solution that minimize the fitting energy $\bar{E}^n$.

In the procedure above, the fitting energy $\bar{E}^n$ is formalized as the sum of squared differences of the data intensities and the fitted values $T_i(s)$. Assume that the orientations $\theta_{k_i}(s)$ are known, the fitted intensity $T_i$ can be estimated as the average value of the data in the corresponding wedge. However, it still needs to determine the optimized number of junction branches. This is accomplished by varying the value $n$ and measuring the decrease in the optimized energy $\bar{E}^n$. The optimized number of junction branches is derived if the following relative error ($r^n$) is small enough:

$$r^n = \frac{\bar{E}^{n+1}}{\bar{E}^n} < \tau_c \qquad (1.12)$$

where $\tau_c$ is a fixed threshold. In their experiments, with a fixed setting for the two thresholds: $d = 16$, $\tau_{\varpi} = 2.1$ and $\tau_c = 0.4$, the authors provided some illustrative results using several synthesized and real images (Figure 1.11).

[Sluzek, 2001] formalized a junction model as a summation function $g(\theta)$ of image intensity along a given angular direction $\theta$ within a local circular window of size $R$ ($15 < R < 30$).

$$g(\theta) = \int_{\alpha=-\pi}^{+\pi} \int_{r=0}^{R} I(r \cos \alpha, r \sin \alpha) \delta(\alpha - \theta) dr d\alpha \qquad (1.13)$$

where $(r, \alpha)$ is the polar coordinate of a point, and $\delta(x)$ is equal to either 1 or 0 taking into account $x = 0$ or $x \neq 0$.

The local function $g(\theta)$ is computed for every edge point yielding a 1D profile representing the characteristics of a junction, if any. At a junction location (Figure 1.12), such a 1D profile presents several spikes and the position of spikes indicates the geometry of the junction. Identification of spikes is not an easy task since it is a highly threshold-dependent process. The authors suggested two-step normalization process for dealing with this issue. The first step is to normalize the response of $g(\theta)$ inversely proportional to the number of pixel in the local window, and the second step is to rescale this response proportionally to
<figure><img src="image_18.png" /><figcaption>Figure 1.11: Examples of detected junctions: (a) 2-junction points; (b) 3-junction points; (reprinted from [Parida et al., 1998]).</figcaption></figure>

the number of junction branches. A final process of template matching is applied to measure the dissimilarity scores between the junction profile and the model junction profiles. By thresholding these dissimilarity scores, the junction is either accepted or rejected. Few test examples were used to demonstrate the performance of the proposed method.

<figure><img src="image_19.png" /><figcaption>Figure 1.12: (a) An ideal L-junction point; (b) the ideal response of a 1D profile for the L-junction point; (reproduced from [Sluzek, 2001]).</figcaption></figure>

[Kalkan et al., 2007] proposed two new improvements enabling a classical corner detector (Harris [Harris and Stephens., 1988], SUSAN [Smith and Brady, 1995], etc.) to be a semantic junction detector. The first advancement concerns improving the location of the detected corners. This is accomplished by designing a new measure of intersection consistency (IC), which is similar in spirit to the function $\Re(r)$ in [Parida et al., 1998]:

$$IC(p_c) = \int_{p \in P} c_{i1D}(p)^2 (1 - d(l_p, p_c)/d(p, p_c)) dp \quad (1.14)$$

where the involved parameters are described as follows:

* $p_c$ is the center of some local image patch $P$;
* $p$ is an image pixel in $P$;

* $c_{i1D}$ is the gradient strength of $p$;

* $l_p$ is the line passing $p$ with a slope of $\theta_p$ computed as the local orientation at $p$;

* $d(x, p_c)$ is the Euclidean distance between $p_c$ and $x$.

The $IC(p_c)$ could be interpreted as a measure of how the pixels in $P$ pointing towards the center $p_c$. Therefore, $IC(p_c)$ will be high if $P$ contains one local line passing $p_c$ or $p_c$ is a junction formed by the intersection of several edge lines. Thanks to this characteristic, the improved location of a corner $q$ is achieved by looking for a point having local maximum IC within a local neighborhood of $q$. The second improvement concerns the estimation of junction characteristics such as junction branches and the strength of the branches. This is accomplished by clustering and thresholding an energy histogram over the junction-relative orientations (i.e., essentially similar to the function $g(\theta)$ in [Sluzek, 2001]). The experimental results showed a significant improvement of junction localization and junction characteristic compared to the Harris and SUSAN corner detectors.

[Tabbone et al., 2005] carried out an in-depth study of the behavior in the scale space of the extrema of Laplacian of Gaussian (LoG). Different junction models have been investigated including linear junction models, non-linear junction models, and linear junction multi-models. Here, a linear model is concerned with the straight edges forming the junction, whereas a non-linear model is associated to the curved straight edges. For the linear junction multi-models, two models are considered including infinite and finite models. They are called multi-models as each contains several adjacent L-junctions. Based on these behaviors, several key conclusions have been drawn:

* Each of these junction models contains at least one LoG extremum point inside the junction sectors;

* The LoG extrema inside the sectors of a junction model are very robust even if the junction model is distorted by geometric transformation and illumination change;

* These LoG extrema can be good starting points to detect junction points.

Although the authors concluded that the LoG extrema are reliable to detect junction points, they did not provide any hints on how to detect the junctions from these extrema. Furthermore, it was concluded that each junction model provides one or several extrema inside the junction sectors but the converse is not studied. More precisely, the LoG extrema appear not only inside the junction sectors but also at different locations. This indeed raises a real challenge as we do not know yet a criterion to justify whether a given LoG extremum point does appear inside a junction sector nearby or it does not.

In summary, the parametric-based methods work from a junction model following model fitting for junction optimization. The junction model can be constructed as a corner model [Förstner, 1994, Kalkan et al., 2007], a piecewise constant function [Parida et al., 1998], or a local 1D orientation profile [Sluzek, 2001]. For the model fitting, [Parida et al., 1998,
Kalkan et al., 2007] employed the same criterion (i.e., regularity measure) originally developed by [Förstner, 1994]. This criterion measures the regularity distribution or intersection consistency of local intensities within a neighborhood. However, the original work of [Förstner, 1994] is limited to simple junction detection without junction characterization, whereas the later works presented robust techniques to estimate junction parameter using dynamic programming [Parida et al., 1998] or semantic interpretation [Kalkan et al., 2007]. Automatic scale selection was addressed in [Parida et al., 1998], but not discussed in [Förstner, 1994, Kalkan et al., 2007, Sluzek, 2001].

### 1.2.4 Conclusions of junction detection methods in CV

To conclude this section, we shall highlight hereafter several key remarks for both the merits and weaknesses of the existing methods. At first, most of these methods are scale-dependent, and restricted to limited experiments without comparative evaluation with other methods. Experimental results have been mainly performed by giving some illustrative results of the detected junctions for few images. Limited comparisons have been carried out merely using the F-scores on the BSDS benchmark [Maire et al., 2008, Xia, 2011]. Few works [Faas and van Vliet, 2007, Bergevin and Bubel, 2004, Deschênes and Ziou, 2000] discuss junction characterization, which is very important for junction features. Furthermore, the CV methods for junction detection are too much dependent on the analysis and extraction of junction branches. Most of these methods address this matter using the local features and thus are sensitive to noise. The use of combined local and global features has been proposed in [Maire et al., 2008] to make this stage much more robust. Besides, a number of parameters are needed for these methods. Interestingly, the use of the powerful *a contrario* detection theory for junction branch grouping has been shown to give quite good results. Finally, all of these methods are limited to single junction detection in the senses that the considering region of interest contains exactly one junction point.

## 1.3 Junction detection in graphical line-drawing images

### 1.3.1 Introduction

In contrast to the definition of the junction point in CV, the junction points in line-drawings are treated as the meeting points of the median lines. However, the task of extracting median lines is not trivial. To be more specific, the major problem is the sensitiveness to small perturbations of the shape boundary and the line thickness of the shapes. This matter results in unwanted skeleton branches which pose another serious problem of junction distortion. That is, both the position of skeleton and junction points are not correctly extracted. Despite of these weaknesses, several methods for junction detection are skeleton-based. The methods start from skeleton and incorporate high-level post-processing steps to correct the junction location. Other works, which try to avoid the problems resulting from skeletonization step, are based on contour matching and element tracking. Table 1.5 summarizes these approaches and the details are discussed in the next sub-sections.
<table><caption>Table 1.5: Related work for junction detection in document image analysis</caption><thead><tr><th>Approach</th><th>References</th></tr></thead><tbody><tr><td>Skeleton-based</td><td>[Nagasamy and Langrana, 1990], [Janssen and Vossepoel, 1997],<br>[Liu et al., 1999], [Hilaire and Tombre, 2001],<br>[Hilaire and Tombre, 2006]</td></tr><tr><td>Contour matching</td><td>[Hori and Tanigawa, 1993], [Han and Fan, 1994], [Lee and Wu, 1998],<br>[Fan et al., 1998], [Ramel et al., 2000]</td></tr><tr><td>Element tracking</td><td>[Van Nieuwenhuizen and Bronsvoort, 1994], [Chiang et al., 1998],<br>[Dori and Liu, 1999], [Song et al., 2002]</td></tr></tbody></table>

1.3.2 Skeleton-based methods

In shape analysis, the term "skeleton" of a shape is referred to a thin representation of the shape that is equidistant to its boundaries. As argued by [Bai et al., 2007], the skeleton of a shape should meet the following properties:

* Preserve the topology of the original shape,

* Extract accurately the location of skeleton points,

* Robust to small distortions of contours and geometric transformations,

* Reversible,

* Represent significant visual parts of the shape.

A comprehensive survey for these methods can be found in [Lam et al., 1992]. Some common approaches for skeletonization are based on iterative thinning [Rosenfeld, 1975, Kwok, 1988], Voronoi diagrams [Näf et al., 1997, Ogniewicz and Ilg, 1992], veinerization [Deseilligny et al., 1998], and distance transform [Niblack et al., 1990, di Baja, 1994]. Table 1.6 summarizes the main features of the traditional skeletonization approaches. Iterative thinning algorithms extract the skeleton by recursively removing the outer boundaries of the object. The resulting skeleton is connected and preserves the topology of the original shape, but it is sensitive to small distortions of boundaries. The veinerization-based technique [Deseilligny et al., 1998] constructs a graph containing rich topological information of the object that is useful to extract different levels of skeleton. The final results are depending on specific applications. For instance, one can select a particular parameter setting to obtain skeleton satisfying one or few specific properties. The Voronoi diagram methods partition the image into regions, each of which is closer to a particular pivot point than others. The pivot points are selected on the boundaries of the object. The skeleton is obtained by extracting the boundaries dividing the regions. The distance transform based methods calculate the shortest distance of each foreground pixel to the background. The skeleton is extracted by finding the pixels having local maximal distance transform.
Consequently, the resulting skeleton is not connected, and an additional step of linking the skeleton points must be incorporated.

<table><caption>Table 1.6: Comparison of different skeletonization approaches</caption><thead><tr><td>Approach</td><td>Geometry invariance</td><td>Reversible ability</td><td>Junction accuracy</td><td>Complexity</td></tr></thead><tbody><tr><td>Iterative thinning</td><td>Yes</td><td>No</td><td>Low</td><td>High</td></tr><tr><td>Voronoi diagrams</td><td>Yes</td><td>Yes</td><td>Low</td><td>High</td></tr><tr><td>Veinerization</td><td>Yes</td><td>Yes</td><td>Medium</td><td>High</td></tr><tr><td>Distance transform</td><td>Partial</td><td>Yes</td><td>Medium</td><td>Low</td></tr></tbody></table>

Despite a large number of existing methodologies for skeletonization, it is difficult to obtain a satisfactory skeletonization algorithm as argued by [Deseilligny et al., 1998]. Recent advanced methods for skeletonization are presented by [Bai et al., 2007, Aslan et al., 2008, Shen et al., 2011, Ward and Hamarneh, 2010]. [Bai et al., 2007] proposed a new skeletonization method using contour partitioning obtained by discrete curve evolution (DCE). The DCE algorithm starts from a polygonal approximation of the contours and iteratively simplifies the boundary polygon. [Aslan et al., 2008] extracted the disconnected skeleton segments for a single shape at a coarse scale. This method successively smoothes the contours until the resulting shapes are simple enough. The skeleton segments are then detected as the symmetry points from the smoothed curves. To make the system more robust to contour distortion, some skeletonization methods [Ward and Hamarneh, 2010, Shen et al., 2011] introduce the concept of branch significance measure to prune the spurious skeleton branches. Although the obtained results are promising, these methods are not related to the junction detection problem and are thus not suitable when dealing with complex and distorted junction in line-drawing images.

In summary, despite a large number of existing methodologies, it is difficult to obtain a satisfactory skeletonization algorithm satisfying the aforementioned properties. Besides, the major problem of skeleton distortion and junction distortion at crossing or irregular zones has not been thoroughly addressed. For these reasons, the skeleton-based methods for junction detection need to incorporate high-level processing steps to correct the location of junction points [Liu et al., 1999, Hilaire and Tombre, 2006]. Such methods work by extracting the skeletons of input image, following a skeleton segmentation and pivot point extraction (e.g., high curvature points). Next, the obtained skeleton segments and pivot points are refined by incorporating some heuristic merging rules. Some specific post-processing steps are applied to handle particular junction areas. Finally, the junction points are detected as the intersections of the skeleton segments, in combination with the retaining pivot points. Table 1.7 briefly describes such methods where the first three criteria have the same meaning as those in the Table 1.2 (page 34), and the two last ones indicate the ways of computing the thresholds for junction merging and junction treatment.

[Nagasamy and Langrana, 1990] proposed a method dedicated to preprocessing and vectorizing engineering drawings. At first, some basic steps such as noise removal and hole
<table><caption>Table 1.7: Skeleton-based methods for junction detection</caption><thead><tr><th>Features</th><th>Nagasamy and<br>Langrana, 1990</th><th>Janssen and<br>Vossepoel,<br>1997</th><th>Liu et al.,<br>1999</th><th>Hilaire and<br>Tombre, 2001,<br>2006</th></tr></thead><tbody><tr><td>Scale invariant</td><td>No</td><td>No</td><td>No</td><td>Yes</td></tr><tr><td>Multi-detection</td><td>No</td><td>No</td><td>Yes</td><td>Yes</td></tr><tr><td>Junction<br>characterization</td><td>No</td><td>No</td><td>Partial</td><td>Yes</td></tr><tr><td>Threshold for<br>junction merging</td><td>Fixed</td><td>Fixed</td><td>Fixed</td><td>Fixed</td></tr><tr><td>Junction<br>treatment rule</td><td>Spatial<br>continuity</td><td>Maximal<br>morphology</td><td>Criterion A</td><td>Topological<br>correction</td></tr></tbody></table>

filling are applied using morphological filters. Next, thickness layer separation is employed to separate the thick objects (e.g., filled areas, arrows, blobs) from the thin line structures from which the skeleton is extracted. At a crossing zone, the skeleton segments are merged to preserve the spatial continuity of the relevant lines. As illustrated in Figure 1.13, the step of merging the skeleton segments is accomplished by first identifying the incident lines at a given junction and then pairing the lines based on the continuity criteria such as the slope and local curvature at the junction.

<figure><img src="image_20.png" /><figcaption>Figure 1.13: (a) The skeleton of an input image; (b) the lines 1 and 2 are grouped (similar to the lines 3 and 4) based on their similar spatial continuity (dash line); (reproduced from [Nagasamy and Langrana, 1990]).</figcaption></figure>

In the next stage, each skeleton line is vectorized by a two-step procedure. The first step detects the dominant points from the skeleton line as illustrated in Figure 1.14 (a-b), and the second step tries to fit the curve segments bounded between two successive dominant points to the arc primitives, if any (Figure 1.14 (c)). The rest of the skeleton line, which can not be fitted by some arc primitives, is fitted to one or several straight line primitives. Part of the dominant points retained after the vectorization process can be treated as 2-junction
points (e.g., like L-junctions) as shown in Figure 1.14 (c). Since the distorted skeleton
parts appearing across the junctions are still included in the skeleton lines, the fitting-
based vectorization process is affected. Besides, the location of the obtained junctions is
displaced since no correction of junction location is performed.

<figure><img src="image_21.png" /><figcaption>Figure 1.14: (a) The skeleton of an input image; (b) the initial dominant points; (c) the remaining dominant points after primitive fitting; (reproduced from [Nagasamy and Langrana, 1990]).</figcaption></figure>

[Janssen and Vossepoel, 1997] presented a coarse-to-fine approach for obtaining the vec-
torization and anchor points of input images. First, the skeleton of an input image is
coarsely vectorized using a polygon approximation technique [Douglas and Peucker, 1973]
with a large threshold $t_{dp\_coarse}$. This step will result in a set of dominant points including
the endpoints, corners, and junctions. Next, these dominant points are refined by moving
them to "correct" location using the maximal threshold morphology. This process of refin-
ing the location of a dominant point is illustrated in Figure 1.15, where (a) is an original
image, and (b) is its coarse vectorization results including two line segments (black thin
lines) and an initial pivot point (red dot). The process of refining the dominant point is
summarized as follows:

* Construct a structuring element corresponding to the current location of the domi-
nant point and the two line segments within a local window. The structuring element
contains three values {1, 0, -1} corresponding to the black pixels, white pixels, and
gray pixels as shown in Figure 1.15(c). This structuring element is constructed in a
particular way to reflect the approximate shape of the input image given a current
skeleton vector.

* Search for a black point within the local window which corresponds to the maximal threshold morphology. To be specific, the structuring element is convolved with the original image and the maximal value is set as the threshold for selecting the output points. In Figure 1.15(d), there is only one point whose value is equal to the maximal threshold.

* Update the obtained point as the new dominant point and repeat the two steps above until the dominant point converges to a fixed location. That is, the distance of the
dominant points found during two successive iterations is less than a fixed threshold (Figure 1.15(f)).

<figure><img src="image_22.png" /><figcaption>Figure 1.15: The process of refining the location of a dominant point; (reproduced from [Janssen and Vossepoel, 1997]).</figcaption></figure>

After that, the corrected dominant points so-called anchor points are used to correct the subsequent step of refining the vectorization results. This is accomplished by re-performing the polygonal approximation step of the skeleton with a sufficiently small threshold $t_{dp}$, following a post-processing step of removing false dominant points. The post-processing step works based on several heuristic rules:

* A dominant point is removed if the distance to the closest anchor point is less than a fixed threshold;

* Two T-junctions are merged to form an X-crossing if their distance is less than a fixed threshold;

* A link dominant point is discarded if the bend angle is small enough.

Since these rules are mainly relying on several fixed thresholds, the obtained results are sensitive to the parameter setting. Figure 1.16 gives an example of the results obtained by applying these rules. From Figure 1.16, it may be noted that many false anchor points were detected.

[Liu et al., 1999] introduced a new set of feature points, $S_n$, computed based on the crossing number $N_c(P)$ for a given binary-value pixel P as follows:

$$S_n = S_e \cup (S_b \cap S_3) \qquad (1.15)$$

$$S_3 = \{P | (N_c(P) \ge 3) \text{ or } (N_b(P) \ge 4)\} \qquad (1.16)$$
<figure><img src="image_23.png" /><figcaption>Figure 1.16: Fraction of the obtained vectorization where the false anchor points are marked with the circles (reproduced from [Janssen and Vossepoel, 1997]).</figcaption></figure>

$$N_c(P) = \frac{1}{2} \sum_{i=0}^{8} |P_{i+1} - P_i| \qquad (1.17)$$

where $S_e$ is the set of endpoints, $S_b$ is the set of black points, $S_3$ is the set of crossing points, and $N_b(P)$ is the number of the black adjacent points of a black point $P$.

The set $S_n$, in conjunction with the dominant points obtained from a polygonal approximation step, are represented by a geometrical graph. This graph is then used in accordance with a criterion, called *Criterion A*, to correct spurious junction points (i.e., fork points in the notation of their paper). The basic idea of the *Criterion A* is that two junctions $P_1$ and $P_2$ are merged if there exists a point $P^*$ belonging to $P_1P_2$ such that for every branch $B$ originating from $P_i$ ($i = \{1, 2\}$) except the branch $P_1P_2$:

* These is a straight line segment $P^*P_b$ fully included in the black region of the image and the length of $P^*P_b$ is sufficiently long; or

* These is a straight line segment $P^*P_b$ fully included in the black region of the image and $P_b$ is a termination point of the branch $B$.

In the experiment, the authors suggested choosing $P_b$ as a point in the branch $B$. Figure 1.17 (a) gives an example where the *Criterion A* is successfully applied to merge two junction points. However, this criterion is less effective when dealing with different thickness and degraded objects. Figure 1.17 (b) illustrates such a situation where two junction points $P_1$ and $P_2$ are merged even that their location is far from each other.

The work presented in [Hilaire and Tombre, 2001] detects junctions based on topological correction of vectorization results. In their work, each skeleton branch is segmented into line and arc segments using a sampling method. Considering the segmentation of line segments, for instance, the sampling algorithm works by iteratively selecting two random points on the branch and extending the candidate line passing these two points as far as possible. This process is repeated for a number of times to find the best candidate line.
<figure><img src="image_24.png" /><figcaption>Figure 1.17: Illustration of the Criterion A: (a) correct fusion of two junction points $P_1$ and $P_2$; (b) wrong fusion of two junction points $P_1$ and $P_2$.</figcaption></figure>

A similar process is applied to obtain the arc segments, but three random points are chosen. Each skeleton segment is then classified into either short or long primitives by simply comparing its length with the local line-thickness. Each long primitive $p$ is then associated with an uncertainty domain $\Delta(p)$ defined as the region extended by two curves at a distant of $\epsilon$ on both sides from the that primitive (Figure 1.18).

<figure><img src="image_25.png" /><figcaption>Figure 1.18: (a, b) The uncertainty domains (gray zones) defined for a line and a circle primitive; (c) illustration of the junction optimization process; (reproduced from [Hilaire and Tombre, 2001]).</figcaption></figure>

Next, the long primitives are clustered into different groups by calculating the intersection zones from the uncertainty domains. Finally, each junction point $J$ is reconstructed from the primitives in each group by minimizing the weighted distance error. Particularly, the optimized junction $J$ is computed using the following formula:

$$J = \arg \min_{J \in I_{\Delta}} \sum_{i=1}^{n} w_i * d^2(p_i, J) \qquad (1.18)$$

where $n$ is the number of primitives in the considering group, $d(p_i, J)$ is the Euclidean distance from a point $J$ to the primitive $p_i$, the weight $w_i$ is set to the length of $p_i$, and $I_{\Delta}$ is the intersection area of the uncertainty domains $\Delta(p_i)$ with $i \in \{1, \dots, n\}$ (as illustrated in
Figure 1.18 (c)). This work, as discussed by the authors themselves, has several weaknesses, including being time-consuming, being sensitive to interrupted patterns, and featuring the ambiguous step of merging junction points. In addition, the use of the uncertainty domains is too restricted and threshold-dependent as the junction points need not to lie inside the uncertainty domains.

This work has been further improved in [Hilaire and Tombre, 2006] where the main improvement lies in the step of junction and skeleton optimization. The improved work employs the same technique for skeleton segmentation as before. Next, a new criterion, which is quite similar in spirit to the *Criterion A*, is defined for merging two long primitives. This criteria is illustrated in Figure 1.19. To be more specific, a long segment *P*, which has two endpoints $L_P$ and $R_P$, is said to join another long segment *Q* having two endpoints $L_Q$ and $R_Q$ by $L_P$ if and if there are two discrete primitives *X* and *Y* such that the following conditions meet:

* $X$ and $Y$ are fully included in the black region of original image,

* $P \subseteq X$, $Q \subseteq Y$, and $X \cap Y \neq \emptyset$, and

* $\exists K \in X \cap Y$ such that $[R_P K] \cap [R_P L_P] = [R_P L_P]$, where $[R_P K] \in X$ is a discrete primitive having two endpoints $R_P$ and $K$, and the same for $[R_P L_P]$.

Figure 1.19 illustrates two examples of possible joining primitives where *P* joins *Q* by $L_P$ (Figure 1.19(a)), and *P* joins *Q* by $L_p$ and *Q* joins *P* by $L_Q$ (Figure 1.19 (b)).

<figure><img src="image_26.png" /><figcaption>Figure 1.19: Illustration of primitive grouping: (a) *P* joins *Q* by $L_P$; (b) *P* joins *Q* by $L_p$ and *Q* joins *P* by $L_Q$; (reproduced from [Hilaire and Tombre, 2006]).</figcaption></figure>

Next, the criterion is applied to achieve the global optimization of the skeleton and junction location. To accomplish this, a connectivity graph is constructed where the nodes are the primitives and an edge connects two adjacent primitives. The junction optimization algorithm traverses all possible paths in this connectivity graph, starting from a long segment and leading to either another long segment or the last segment of a sequence of the short ones. For each path traversed, the criterion above is applied to check whether the first segment could join the final one of the considering path.

Figure 1.20 demonstrates an illustrative example of the junction optimization process. Figure 1.20 (a) is an original image and Figure 1.20 (b) is the results of the skeleton
<figure><img src="image_27.png" /><figcaption>Figure 1.20: Illustration of the process of skeleton and junction optimization: (a) an input image with its skeleton; (b) the results of skeleton segmentation process; (c) the connectivity graph; (d-f) the process of graph simplification; (g) the final graph; (h) the final skeleton and junction points; (reproduced from [Hilaire and Tombre, 2006]).</figcaption></figure>

segmentation step: the capital letters (i.e., A, B, C, D) indicates the long primitives, while the rest represent the short ones. The resulting connectivity graph is shown in Figure 1.20 (c) where the black nodes correspond to the long primitives and the white nodes are the short ones. In Figure 1.20 (d), we obtain the first path composing of the nodes {A, b, B}, and the second path is found later in Figure 1.20 (e) composing of the nodes {B, c, d, C}. For the first path, because the node A can join B using the aforementioned joining rule, the node b is then marked for deletion and the two nodes A, B are directly connected. This process is repeated for the other paths as shown in Figure 1.20 (e, f). The final graph is plotted in Figure 1.20 (g), which corresponds to the final skeleton and junction structure as illustrated in Figure 1.20 (h). When the optimized algorithm terminates, the nodes marked for deletion with unlinked edges are deleted.

The problem with this approach concerns the ambiguous step of constructing the con-
nectivity graph. For instance, it was not discussed in the paper why the edges (b, c), (c, k),
(i, c), and (j, k) are not included in the graph in Figure 1.20 (c). Besides, as mentioned
by the authors, multiple merging situations of the primitives might happen, the process of
reconstruction of the junctions is thus non-deterministic. Hence, more than a single solu-
tion can be obtained depending on the order of primitive merging. Figure 1.21 illustrates
such a case where another possible solution is presented for the crossing structure in Figure
1.20.
<figure><img src="image_28.png" /><figcaption>Figure 1.21: Another possible interpretation of the crossing structure in [Hilaire and Tombre, 2006]: (a) an input crossing structure; (b) an interpretation for the crossing in (a) where two T-junctions are constructed.</figcaption></figure>

In summary, one of the most challenges of the skeleton-based methods is to handle the problem of skeleton distortion taken place at the crossing zones. Most of these methods addressed this problem by introducing a junction optimization step that uses some simple and heuristic rules to merge the junction candidates. Such a rule, therefore, is highly relying on the selection of several thresholds to make the decision of merging the junctions. As the chosen of these thresholds is not trivial and mainly found based on empirical trials, these methods can not perform well for different datasets. In practices, due to different levels of degradation of input images, the obtained results could be substantially affected.

1.3.3 Contour-based methods

To avoid the distortion problem resulting from the skeletonization step, some works detect junctions from contour-based vectorization results. Instead of using a traditional skeletonization technique, these works are concerned with the extraction of median lines from contours to avoid the problem of skeleton/junction distortion. These methods are typically composed of four main stages. The first stage detects contours and partitions them to obtain a set of contour segments. The second stage performs contour segment pairing to find the matching contour segments located in two opposite sides of a stroke. In the third stage, the median lines are generated from the matching contour segments. Median line correction may be applied to refine the extracted lines. The last stage is junction localization using the direction and continuity of the median lines and contour boundaries. Table 1.8 presents the representative methods of this approach. The two first criteria of multi-detection and junction characterization have the same meaning as previously used in Table 1.2 (page 34). The last three criteria explain for the rules used in the stages of contour paring, median line extraction/correction, and junction localization respectively.

In [Hori and Tanigawa, 1993], the contours and skeletons of input image are polygonally approximated to obtain two sets of skeleton and contour fragments. Next, each skeleton fragment is associated to the closest contour fragments based on some heuristic criteria.
<table><caption>Table 1.8: Contour-based methods for junction detection</caption><thead><tr><td>Method</td><td>Multi-detection</td><td>Junction characterization</td><td>Contour pairing rule</td><td>Median line correction</td><td>Junction localization</td></tr></thead><tbody><tr><td>Hori and Tanigawa, 1993</td><td>No</td><td>Partial</td><td>Missing</td><td>Progressive searching and fitting</td><td>Intersection of median lines sharing a same segment</td></tr><tr><td>Han and Fan, 1994</td><td>No</td><td>No</td><td>Direction difference, spatial distance, and contour projection overlapping</td><td>Median lines of matched contours, gap filling by extrapolating to the junction</td><td>Centroid of intersections of median lines or terminations</td></tr><tr><td>Fan et al., 1998</td><td>Yes</td><td>No</td><td>Direction difference, minimum spatial distance, and minimum matching cost</td><td>Median lines of matched contours, gap filling using adjacent blocks or contour continuity</td><td>Intersection of median lines</td></tr><tr><td>Ramel et al., 2000</td><td>Yes</td><td>Yes</td><td>Spatial distance, parallelism, and foreground density</td><td>Not used</td><td>Intersection of quadrilaterals</td></tr></tbody></table>
A line fitting process is then performed as an iterative process composing of two steps.
The first step chooses a seed for line fitting as the longest unused skeleton fragment or
contour segment. The selected seed is then treated as a path on a graph where the nodes
are the skeleton fragments and an edge connects two adjacent skeleton fragments. Such a
path will be used to find a candidate line, fitting well to the skeleton segments of the path.
The second step extends the path by iteratively inserting, in one direction, a new adjacent
node of the current termination node of this path. A new node is inserted to the ongoing
path if two following conditions are met (Figure 1.22):

* The average distance between the endpoints of every skeleton fragment of the ongoing path and the candidate fitting line is less than a threshold;

* The fitting candidate line lies inside an enclosed region bounded by the contour fragments.

This searching step terminates when all candidate lines are visited and the longest one is
considered as the best line.

<figure><img src="image_29.png" /><figcaption>Figure 1.22: Illustration of the process of progressive extension of line fitting; (reproduced from [Hori and Tanigawa, 1993]).</figcaption></figure>

A final step of correcting the junction location is performed as follows with respect to
Figure 1.23:

* Find every two lines which share the same skeleton segment. For instance, in Figure 1.23, the first line is composed of two skeleton segments {$S_1, S_2$}, and the second one contains two skeleton segments {$S_3, S_2$}. These two lines share the same skeleton segment $S_2$.

* If the two lines share the same skeleton segment in two different directions, as presented in Figure 1.23 (a, b), the intersection of the new lines without the shared skeleton segment is treated as a new junction point. Figure 1.23 (d, e) demonstrate the junction correction results for the cases in Figure 1.23 (a, b).

* If the two lines share the same skeleton segment in the same direction, as presented in Figure 1.23 (c), these two lines are refitted by merging their termination points to produce the result (Figure 1.23 (f)).

This method can handle simple crossing zones corresponding to the T-, L-, and X-
junction. For more complicated junction configurations, special post-processing is needed.
<figure><img src="image_30.png" /><figcaption>Figure 1.23: Illustration of the process of correcting the junction location; (reproduced from [Hori and Tanigawa, 1993]).</figcaption></figure>

In [Han and Fan, 1994], the contours are first vectorized to obtain a set of contour segments such as straight line segments, circular arcs, and curve segments. The contour segments of the same type are then matched based on the following criteria:

• The distance between two segments is small enough;

• The overlap of the projection of the two segments on either horizontal axis or vertical axis is sufficiently high;

• The direction difference of two straight line segments is close to 0° or 180°, or the difference of the radii of two circular arcs must be small enough.

All these criteria are applied using some fixed thresholds. Next, the median lines generated from the matching contour vectors, are vectorized resulting in a set of skeleton vectors. Since there is often no properly matched contour segments at the crossing zones, no median lines are generated at such location. To remedy this matter, a last process is performed to connect the gaps and generate junction points as illustrated in Figure 1.24. At first, a gap is detected as the place where there is at least two adjacent pairs of matching contour vectors. Next, gap filling and junction generation is applied. Given $n$ adjacent contour vector pairs represented by $\{V_{i_1}, V_{i_2}\} (i = 1, \dots, n)$, a junction is constructed employing the following procedure:

1. If there is no common contour vector among the $n$ adjacent contour vector pairs, as illustrated Figure 1.24 (a), the followings are the main steps of gap filling:
* Pick randomly a skeleton vector as a reference vector.

* Compute the intersections of the reference vector with the rest.

* A new junction point is computed as the center of the intersections.

* The skeleton lines are extrapolated to the junction point.

2. If there exist two pairs of contour vectors which share the same contour vector (e.g., $V_1$ in Figure 1.24 (b)), the process of gap filling is performed as follows:

* Join the two skeleton vectors corresponding to the pair of continue collinear contour vectors.

* Compute the intersections of the joint skeleton vector with the rest.

* A new junction point is computed as the center of the intersections.

* The skeleton lines are extrapolated to the junction point.

<figure><img src="image_31.png" /><figcaption>Figure 1.24: Illustration of the process of gap filling and junction generation after contour segment pairing: (a) without common vector and (b) with common vector; (reproduced from [Han and Fan, 1994]).</figcaption></figure>

This work assumes that each crossing zone contains exact one meeting point or junction point. In addition, the meeting point computed in this way might be located outside the crossing zone. Furthermore, the junction location obtained for the case in Figure 1.24 (a) may differ from time to time because the reference skeleton vector is selected randomly without checking at the global point of view.

[Fan et al., 1998] presented a method to deal with the distortion of thinning-based skeletonization using block decomposition and contour vector matching. The proposed method first decomposes a binary input image into blocks and then the contours of each block are extracted and polygonally approximated to obtain a set of contour vectors. A matching process is then performed for pairing the matched contour vectors based on several heuristic criteria. Particularly, a contour vector $L_j$ is matched with another contour vector $L_i$ if the following conditions are met:
* The direction difference between $L_i$ and $L_j$ is within a range of [90, 270], and

* $L_j$ is the line having the shortest distance, $dist(L_i, L_j)$, to $L_i$, and having the smallest matching cost defined as $dist(L_i, L_j)/|L_i|$, where $|L_i|$ is the length of vector $L_i$.

Next, the median lines are generated from the matching contour vectors. The median lines are vectorized to obtain a set of skeleton vectors. A final process of gap filling is applied to connect the disjointed skeleton vectors due to the discontinuity of the blocks as illustrated in Figure 1.25. Two different types of gaps are defined in this approach and two different methods are employed for filling the gaps. These methods are illustrated in the following.

* Type 1 gap: A gap of type 1 is formed by the matching of one contour vector $C_1$ and two disconnected contours $C_2$ and $C_3$ as shown in Figure 1.25 (a). For such a case, gap filling is treated by linking two contour vectors corresponding to the matched contours $C_1$, $C_2$, and $C_3$ as illustrated in Figure 1.25 (b).

* Type 2 gap: A gap of type 2 is formed by the matching of two skeleton vectors belonging to different adjacent blocks $B_1$ and $B_2$ as shown in Figure 1.25 (c). In this case, gap filling is completed by linking these two skeleton vectors as shown in Figure 1.25 (d).

<figure><img src="image_32.png" /><figcaption>Figure 1.25: Illustration of the process of filling gap and junction generation; (reproduced from [Fan et al., 1998]).</figcaption></figure>

Figure 1.26 shows an example of the obtained skeletal vectors and junction points. It can be seen from this example that the proposed method produces a noticeable displacement of the skeleton and junctions (marked by the circles). In addition, the proposed method works by incorporating various heuristic rules which would be failed to handle complicated crossing zones.

The work in [Ramel et al., 2000] formulates the junction detection problem as an identification of relations (i.e., intersection, succession, parallelism) between contour primitives. The contours of input image are first extracted and polygonally approximated to obtain a set of vectors. A quadrilateral is defined as a pair of two matched vectors on two opposite sides of a line segment. To construct the quadrilaterals, the matching algorithm picks up
<figure><img src="image_33.png" /><figcaption>Figure 1.26: The obtained skeletal vectors and junctions in the work of [Fan et al., 1998]. The displacement of skeletal vectors and junctions are marked by the circles; (reproduced from [Fan et al., 1998]).</figcaption></figure>

the largest vector $V_1$ from the list of non-matched vectors, and then looks for the two closest opposite vectors, $V_2$ and $V_3$, based on the distances (e.g., $d_1$ and $d_2$ on Figure 1.27) between the terminations of these vectors. A heuristic criterion, using parallelism and foreground density, is then derived to match $V_1$ versus $V_2$ and $V_3$. To illustrate how this criterion is applied, Figure 1.27 gives the match of $V_1$ and $V_2$. In this case, the vector $V_1$ could be decomposed into two sub-vectors by projecting one of two terminations of $V_2$ into $V_1$ (e.g., $P'_1$). The less matched sub-vector (e.g., connecting $P'_1$ and $P'_2$) is then updated as non-matched vector. This procedure is continued until all vectors are processed.

<figure><img src="image_34.png" /><figcaption>Figure 1.27: Illustration of the contour matching process (see explanation in the text); (reprinted from [Ramel et al., 2000]).</figcaption></figure>

Finally, a structural graph is constructed to represent the structural relationships be-
tween the quadrilaterals such as parallel relation (P), T-, X-, and L-junction. Figure 1.28
illustrates such a graph constructed for part of an input image. The main weakness of this
work is the loss of connectivity among the adjacent quadrilaterals. It is also sensitive to
parasite and degenerate quadrilaterals. In addition, the structural relation defined between
the quadrilaterals is restricted to few simple junction types.

<figure><img src="image_35.png" /><figcaption>Figure 1.28: Construction of the structural graph (reprinted from [Ramel et al., 2000]).</figcaption></figure>

In short, the contour-based methods avoid the major problem of skeleton distortion, but they give a rise of several other drawbacks. In the first place, image contours must be first extracted and polygonally approximated to obtain a set of contour vectors. The resulting contour vectors are thus highly subjected to contour noise and distortion. On the other hand, while contour vector matching is an obligated stage of these methods, it is well-known that there has been no robust enough technique to accomplish this task. Although existing techniques often employ various heuristic rules to perform contour matching and junction construction, the obtained results are still far from perfection, especially when encountering a crossing zone. Finally, the loss of connectivity of the median lines at the crossing zones is an inherent drawback of these methods.

1.3.4 Tracking-based methods

Apart from the before-mentioned approaches for junction detection, tracking-based
methods have been proposed. These methods, known as direct vectorization, are involved
in vectorizing line-drawings without using any segmentation steps(i.e., neither skeleton
segmentation nor contour segmentation). Therefore, any error-prone introduced by a seg-
mentation process is avoided. Typically, these methods are composed of three main steps:
seed initializing, line tracking, and junction handling. Seed initializing is a step to detect a
starting element for the subsequent step of line tracking. These elements could correspond
to pixels (e.g., Sparse Pixel Vectorization [Dori and Liu, 1999]), oriented bounding boxes
[Song et al., 2002], circular regions (e.g., Maximal Inscribing Circle [Chiang et al., 1998]).
The second step of line tracking is an iterative process to fit the seed element to the fore-
ground region until some specific terminations are satisfied. Typically, the tracking process
terminates where it reaches a junction zone or an entire object is tracked. Then, the last
step of junction handling is triggered to determine the next tracking branch or to remove
the tracked objects.

A summary of the key works belonging to this approach is presented on Table 1.9 where the two first criteria of multi-detection and junction characterization have the same meaning as previously defined in Table 1.2 (page 34). The last three criteria outline the main ideas of the three steps of a tracking-based algorithm. The details of these methods are presented in the following.
<table><caption>Table 1.9: Tracking-based methods for junction detection</caption><thead><tr><td>Method</td><td>Multi-detection</td><td>Junction characterization</td><td>Seed initializing</td><td>Line tracking</td><td>Junction handling</td></tr></thead><tbody><tr><td>Nieuwenhuizen et al., 1994</td><td>No</td><td>No</td><td>User-interaction</td><td>Two opposite contour followers</td><td>Circle following and branch construction</td></tr><tr><td>Dori and Liu, 1999</td><td>Yes</td><td>No</td><td>Reliable starting median point detection</td><td>Tracking the mid-points of successive vertical/horizontal runs</td><td>Line merging based on width similarity, collinear, and proximity</td></tr><tr><td>Chiang et al., 1998</td><td>Yes</td><td>No</td><td>Maximal inscribing circle fitting</td><td>Circular region based tracking</td><td>Line labeling and connecting using Bezier curve</td></tr><tr><td>Song et al., 2002</td><td>Yes</td><td>No</td><td>Oriented bounding box fitting</td><td>Bar segment based tracking</td><td>Deletion of the tracked bars using contour directions</td></tr></tbody></table>
In [Van Nieuwenhuizen and Bronsvoort, 1994], seeds are initialized manually. The user points out the line and the direction to be tracked. Next, the indicated line is tracked using two contour followers, called the left and right ones, on two opposite sides of the line. This tracking process terminates until one of the following conditions is met:

* The last point found by the left contour follower equals to the previous point found by the right contour follower and vice versa (i.e., the end of the line is reached).

* The current tracking position returns to the starting position (i.e., the line is closed).

* The distance between two successive median points is smaller than a threshold (i.e., a crossing zone).

While arriving at a junction location, the tracking algorithm detects the relevant branches by constructing a series of *n* circles centralized at the current interrupted median point with increasing radii as illustrated in Figure 1.29 (a). The radii are determined such that the corresponding circles pass through the previous tracked median points. The intersections between these circles and the contours of the junction area are called *circle-contour* points as shown in Figure 1.29 (b).

Next, starting from a circle-contour point of the current branch $B_1$ and the $i^{th}$ circle with $i = 2, ..., n-1$ (e.g., $P_1$ in Figure 1.29 (b)), a clockwise contour follower is applied to detect the other circle-contour points. This contour follower terminates when the last circle-contour point $P_2$ is reached. The detected circle-contour points are then paired to find the pairs of opposite circle-contour points used to identify the relevant branches of the current junction area (e.g., the branches $B_2, B_3$, and $B_4$ in Figure 1.29 (b)). Besides, for each pair of two opposite circle-contour points, a new median point is generated. The detected branches are finally provided to the user for the selection of next tracking branch.

<figure><img src="image_36.png" /><figcaption>Figure 1.29: The branch construction process: (a) circle following; (b) branch construction; (reproduced from [Van Nieuwenhuizen and Bronsvoort, 1994]).</figcaption></figure>

This method is robust to handle the varying line width and irregular border as well.
The main weakness is that it requires the intervention of the user in both seed initializing and junction handling. Besides, the process of branch construction is sensitive to the fixed setting of the parameter *n* in the tracking algorithm at the junction location.

[Dori and Liu, 1999] proposed a pixel-tracking-based vectorization system called Sparse Pixel Vectorization (SPV). In the first step, a reliable starting median point is detected as the midpoint of either the vertical run or horizontal run originated from the first encountered black pixel. Next, tracking process is proceeded in either horizontal or vertical direction depending on the corresponding run length. During the tracking, the widths of the tracked lines are estimated and compared to a threshold. If the width run conflicts the width preservation, as shown in Figure 1.30 (a), a junction recovery process is triggered. The junction recovery process works as an iterative search along the junction area, composed of three steps:

* Revert back to the last medial point (Figure 1.30 (b));

* Update the tracking step length with half of the length in the previous step (Figure 1.30 (b, c));

* Explore a new tracking position.

<figure><img src="image_37.png" /><figcaption>Figure 1.30: Illustration of the junction recovery process: (a) conflict of the width run and the width preservation; (b) a new invalid tracking point; (c) a new valid tracking point on the current branch; (d) a new valid tracking point on a different branch; (reproduced from [Dori and Liu, 1999]).</figcaption></figure>

The junction recovery process leads to two possible cases:

* A new valid tracking point is found, as shown in Figure 1.30 (d), and the tracking process is proceeded on the new line.

* No valid points are found (i.e., the tracking step length becomes zero). In this case, the tracking step continues with a new seed point.

Once the tracking step terminates, the median lines are polygonally approximated following some post-processing steps to link the collinear line segments of the same line width, correct the defects at the junction location, and refine the endpoints. As argued by [Song et al., 2002], the weakness of this junction recovery process is that it fails to pass the junction areas where the length of the intersection zones is greater than the tracking
step length. In addition, the loss of connectivity, when encountering the arcs, is another weakness of the proposed method.

The authors in [Chiang et al., 1998] proposed a region-based vectorization system called *maximal inscribing circle* (MIC). A MIC is defined as a maximal-radius circle fitting inside a line segment in the sense that it has at least two contact points with the border of this line segment (Figure 1.31). The line segments are then tracked using the MIC(s) following a labeling algorithm to analyze different detected lines, identify junction zones, and construct spatial relations among them. After connecting the different lines through common junction zones, the connected lines are vectorized to obtain vector-based representation. Two short line vectors can be merged using the Bezier curve, if necessary. The final junction points are calculated as the intersections of the vectorized lines. Experimental results showed interesting performance of the proposed method, compared to the traditional approaches. In contrast to many existing methods, the proposed system requires no post-processing steps to prune the short segments and unify the spurious junctions. However, the system is highly dependent on the step of line unifying at the common junction areas. In addition, false merging of the two short segments can be happened due to the selection of fixed thresholds.

<figure><img src="image_38.png" /><figcaption>Figure 1.31: Illustration of MIC tracking process; (reproduced from [Chiang et al., 1998]).</figcaption></figure>

In [Song et al., 2002], a different approach based on object-oriented vectorization is proposed. In this approach, the primitives are tracked in a specific order starting from the simple ones (e.g., bar lines) to the complex ones (e.g., arcs, circles, text). This is referred to the progressive simplification process whose main idea is to progressively recognize the objects and then to remove them for reducing their disturbance. The seed initialization step, as illustrated in Figure 1.32 (a), starts from a foreground pixel A and detects the regular runs in both horizontal and vertical directions. This terminates where the number of successive regular runs satisfies a pre-defined threshold, resulting in a successful seed segment detection. The detected seed is then used to track the entire bar in both opposite directions. Tracking process is continued until the length (L) of the last perpendicular run violates the thickness (W) of the seed segment. To be more specific, the termination conditions are as follows: $L < 0.5 \times W$ or $L > 2 \times W$. Once the bar is completely tracked, it will be removed to eliminate the interference with the rest of foreground objects. However, the deletion operator at a junction area is not trivial. At such a junction zone, as illustrated in Figure 1.32 (b), the authors suggested detecting the contours of the branches involved in this zone and then analyzing their trends to calculate the part of the junction zone to be preserved. Followings are the main steps of deleting a recognized bar at a junction area:
* If there are at least two branches on both sides of the tracked bar, use the trends of the incident contours to determine the area to be preserved (e.g., the center area in Figure 1.32 (b)).

* If all the incident branches are on one side of the tracked bar, simply remove half of the tracked bar which corresponds to the side containing no branches (e.g., the top area in Figure 1.32 (b)).

The main challenge with this process is its sensitivity to contour noise. In addition, when two intersection zones are too close to each other, the estimation of contour trends is not reliable. The experimental results, applied to several vectorization test datasets, showed the robustness of their system in the context of vectorization.

<figure><img src="image_39.png" /><figcaption>Figure 1.32: Bar tracking process (a) and intersection preservation deletion (b); (reproduced from [Song et al., 2002]).</figcaption></figure>

In summary, one common major problem of the tracking-based methods is the tracking initialization. Depending on the detected seed segment, the subsequent step of line tracking can be impacted since the stop tracking conditions are mainly relied on the seed's information such as its location, direction, and size. Another problem related to the tracking-based methods is the reading order. A tracking method is a recursive process, wherein next tracking steps are initiated from the previous ones. Therefore, a small change in the location and direction of the previously tracked segment could lead to different results of the newly detected segments. Consequently, the tracked median lines and the obtained junctions could be displaced from time to time. Finally, the junction detection and correction process is triggered by the tracking process. Any mistakes in the tracking progress could lead to the miss detection of the junction point.

### 1.3.5 Conclusions of junction detection methods in line-drawings

In conclusion of the methods for junction detection in line-drawing images, we can draw here several noticeable remarks. At first, since the junctions are detected as the intersections of the median lines, different methods have been proposed to deal with the problem.
of median line extraction and correction. One line of research has been relied on the skeletonization approach. These methods directly extract median lines using some skeletonization techniques and then corrects the problem of junction distortion by incorporating high-level processing steps. To accomplish this, most of these junction correction steps are heuristics-based rules, which require specific parameter tuning to merge the false detections. Besides, scale invariant is partially achieved and junction characterization is rarely discussed. Other methods, which try to avoid the problems resulting from skeletonization step, are based on contour matching and element tracking. However, the contour-based methods have two major problems: contour matching and gap handling. It may be noted that there is no robust technique to handle the one-to-many and many-to-many matches in the process of contour segment pairing. In addition, the loss of connectivity is an inherent drawback of these methods. For the last approach of element tracking, seed initialization and tracking order are two main issues. The junction detection and correction process is highly dependent on the line tracking and detection. The last noticeable point is that no real evaluations of these all methods in terms of junction detection are performed. In fact, all these approaches have evaluated under the context of vectorization contests of which the test images were not severely degraded and the evaluation metrics are not dedicated to keypoint performance evaluation. The common metrics for evaluating a vectorization system are Combined Detection Index (CDI) [Wenyin and Dori, 1997] and Editing Cost Index (ECI) [Phillips and Chhabra, 1999]. The CDI metric computes the positive and negative detection rates at both pixel and vector levels, whereas the ECI metric is computed at vector level measuring the cost of correcting a mistake (e.g., miss detection, false alarm, one-to-many, and many-to-one) of a detection system. Since both the CDI and ECI metrics are calculated at the vectorization results and the detected junctions take very small part of the detection results, the real performance of the detected junctions is thus negligible and not correctly evaluated. More precisely, evaluation of the junction detection process has been embedded in a vectorization evaluation protocol.

## 1.4 Open discussion

Following the conclusions made at the end of each previous section, it is clear that the techniques in CV for junction detection can not be directly employed to the same problem in line-drawing images. As the line-drawing images are mainly composed of binary features, the matter of extracting the edge map is thus a trivial task. However, junctions in line-drawings are considered as the meeting points of the median lines, the CV techniques based on edge grouping are likely to produce much of false detection rate. On the other hand, the parametric-based techniques need to construct the junction models which are also relying on the behavior of the edge ridges. These techniques therefore can not deal with the correct detection of junction points in line-drawing images. To be more specific, the detected points using these CV methods would be the corner points rather than the junctions points when applying to line-drawing images. At last, due to the lack of standard datasets for junction detectors, performance evaluation of the CV methods was rarely concerned. Although a semantic benchmark was provided by [Maire et al., 2008], few methods for junction detection were evaluated on this dataset.
In line-drawing images, the problem of junction detection has been mainly embed-
ded in a vectorization system. The obtained results are therefore subjected to the error-
prone caused by the raster-to-vector conversion process. Such a vectorization system has
been known to be sensitive to setting parameters, and present difficulties where hetero-
geneous primitives (e.g., straight lines, arcs, curves, and circles) appear within a single
document. Knowledge about the document content (objects, entities, document layout)
must be included and derived using an appropriate strategy to make the system more ro-
bust at the cost of adaptability. Besides, few of them (e.g., [Hilaire and Tombre, 2001] and
[Hilaire and Tombre, 2006]) are able to handle the multiple junction detection at a given
crossing zone, and junction characterization was not thoroughly discussed. Furthermore,
the real performance of these junction detection approaches have not been thoroughly eval-
uated due to the lack of extensive and comparative experiments. Indeed, most of these
methods were evaluated under the context of vectorization. Other methods just give few
illustrative examples of the detected junctions. Therefore, the real performance of these
methods for junction detection is still an open question.

Apart from the before-mentioned challenges, we are also aware of favourable features
of the existing methods. First, it is desired to use the median lines as a good presentation
of the line-like primitives but not the crossing zones. Therefore, if the crossing zones can
be segmented out, an off-the-shelf skeleton-based method would be useful to represent the
rest of line-drawings [di Baja, 1994]. Second, once the major part of line-drawings are rep-
resented by the median lines, the 2-junctions (e.g., L-, V-, M-junctions) can be detected by
partitioning the median curves into straight line segments. To do so, a polygonal approxi-
mation method can be applied. However, such a method shall produce many false alarms
for perfect smooth primitives taking a circle for example. A good alternative solution is
the use of a high curvature point detection. For this concern, we can reuse many robust
methods for dominant point detection in the literature [Teh and Chin, 1989]. Finally, once
the crossing zones have been segmented out, the incident median lines of a given crossing
zone are unlikely to be impacted by the problem of junction distortion or skeleton distor-
tion. The *n*-junctions (*n* > 2) contained in each crossing zone could be reconstructed using
an advanced junction optimization algorithm, and interesting approaches on this problem
have investigated in the literature by [Hilaire and Tombre, 2006, Maire et al., 2008].

In this dissertation, we attempt to create such an approach for junction detection
in line-drawings that exploits the advantages of several existing techniques. The proposed
approach has the following major features: junction distortion avoidance, accurate junction
detection, multiple junction detection, efficiency and robustness. We will justify thoroughly
all these features in the next chapter.
# Chapter 2

# Accurate junction detection and characterization in line-drawings

Following the conclusions made in the previous chapter, it is highly agreed that junction features are crucial for many applications. This chapter presents a novel approach for junction detection and characterization in line-drawing images. The proposed approach has been deeply evaluated through extensive experiments in comparison with two other baseline methods. Experimental results showed that the proposed approach is robust to common geometry transformations and can resist a satisfactory level of noise/degradation. Furthermore, it works very efficiently in terms of time complexity and requires no prior knowledge of the document content. At last, the proposed method is independent on any vectorization systems.

## 2.1 Introduction

In line-drawing images, junction features are of crucial importance to support different applications such as symbol localization and spotting, vectorization, storing and retrieval of engineering documents. Despite a number of works for junction detection have been proposed in the literature, each of these approaches has some specific limitations as thoroughly mentioned earlier. As we are interested in detecting and characterizing the junctions for the analysis of engineering document images, this chapter attempts to bring a novel, complete, and accurate approach for that purpose.

In the proposed approach, we directly formulate the problem of junction detection as searching for optimal meeting points of line-like primitives from input images. However, as
it is impossible to obtain ideal line primitives (i.e., 1-pixel-thick lines) from a digitization
process, the intersection areas of the line primitives can not converge or contract to one
pixel as expected. Therefore, to achieve exact junction localization, the line primitives
must be represented in suitable forms that facilitate the step of finding their intersections.
Apart from the major drawback of junction distortion, median axis lines have been known
to be very good representations of such line primitives. At first glance, it seems that our
approach would directly encounter the well-known problem of junction distortion. However,
it is important to note that if we can identify and remove all distorted zones, the remaining
line segments could be well represented as the mean of the median lines with little (or even
without) disturbance concerning the issue of junction distortion. We therefore develop our
approach based on this idea.

It is noted that similar idea has been explored in the literature [Hilaire and Tombre, 2001, Hilaire and Tombre, 2006]. However, the approach taken in these works is quite different from ours. Particularly, these two methods partition the skeleton into reliable and unreliable line segments relying solely on a single line-thickness criterion. If the length of one segment is less than the line thickness, it is considered to be a short segment and *vice versa*. The short segments are treated as unreliable segments and thus removed. Using such a threshold is too vulnerable and would lead to many mis-classifications among unreliable/reliable segments.

<figure><img src="image_40.png" /><figcaption>Figure 2.1: Overview of the proposed approach.</figcaption></figure>

In our approach, a distorted zone is identified by addressing two probing questions: where such a zone is likely to appear and how large this distortion zone would be. Naturally, the distorted zones occur at crossing locations and these zones would be restricted to small areas fitting inside the crossing structures. The former fact indicates that we could make use of *candidate* junctions to determine the locations of distorted zones, whereas the latter observation suggests that a maximal inscribing circle [Chiang et al., 1998] would be useful
to determine the areas of the distorted zones. We have investigated these two main lines as the core strategy of our approach to detect the distorted zones.

Once the distorted zones are segmented out, the major part of line-drawings shall be well represented by median lines. The 2-junctions are then detected as the meeting points of two straight line segments. To do so, one can employ a polygonal approximation method. However, such a method is sensitive to smooth objects. Taking the circles and arcs for examples, a polygonal approximation method shall produce many small straight line segments, resulting in many false detections of junction points. Interestingly, an alternative approach is the use of a high curvature point detection method as it detects the points in which the curvature is significantly changed in a local neighborhood. We have thus employed the technique of [Teh and Chin, 1989] with a major change in the step of region of support determination, making the method more robust to scaling change and digitalization effect.

The *n*-junctions ($n > 2$) are reconstructed from the distorted zones. For this concern, several techniques have been introduced using a specific junction optimization process [Hilaire and Tombre, 2006, Maire et al., 2008]. Both these works share the common idea of using distance error minimization as an objective function. The work in [Maire et al., 2008] seems to be robust to distorted edge lines as its main idea relies on an iterative process of junction-branch optimization (i.e., an EM-based algorithm). However, this work is limited to single junction reconstruction and is not scale invariant. To detect the *n*-junctions, we have extended this work to make it well-adapted to multiple junction detection and more robust to noise.

The global system we propose is presented in Figure 2.1. It exploits five main stages, each of which is briefly described hereafter:

* Pre-processing: Image enhancement and skeletonization.

* Candidate junction detection: This stage detects 2-junction candidates and *n*-junction candidates ($n > 2$). The 2-junction candidates are detected as the high curvature points of skeleton segments, and the *n*-junction candidates are detected as the crossing points.

* Distorted zone detection: This stage detects and conceptually removes the distorted zones using the information of the detected junction candidates and the line thickness.

* Extraction of local topology: The local topology around each distorted zone is extracted and then described using a specific structure to support the subsequent stage of junction optimization.

* Junction optimization: This stage clusters the local skeleton segments of a given topology structure into different groups, each of which shall construct a final junction point.

In the following sections, we shall discuss in detail all these stages of our system.
2.1.1 Pre-processing

Our method is applied to binary images. These images could be obtained following some
enhancement processes, such as noise filtering and binarization, depending on the specific
application. Next, the median lines are pre-extracted using the technique presented in
[di Baja, 1994] because it is probably argued as one of the most robust techniques for
skeleton extraction in the literature. In addition, this method is time-efficient, supporting
all our processes at a low time cost. At the end of this step, the median lines and crossing
points (i.e., the points with at least three 8-connected neighbors) are extracted to be used
in the subsequent stage (Figure 2.1).

2.1.2 Detection of candidate junctions

In the second stage, candidate junction points are detected from the median lines extracted previously. These candidate junctions, in combination with the line thickness information, are used to detect distorted zones and drive our junction optimization process in the next stages of our system (see Figure 1). In our case, the candidate junctions are classified into 2-junctions and *n*-junctions (i.e., the junctions formed by *n* arms with *n* ≥ 3). The *n*-junction candidates are easily extracted by detecting the crossing-points obtained from the skeletonization step.

The 2-junction candidates are detected as the dominant points of the median lines. Generally, the approaches for dominant point detection can be categorized into two classes: multi-scale and single-scale. Although the former approaches [Awrangjeb and Lu, 2008, Mokhtarian and Suomela, 1998] have been known to be robust to noise, they often produce high false positive rates. This matter is realized based on the fact that curve smoothing and curvature estimation are two of the most critical stages of a dominant point detector [Mohammad Awrangjeb and Fraser, 2012, Teh and Chin, 1989]. However, the choice of an appropriate smoothing scale is not trivial and the use of a multi-scale framework to smooth the curve does not solve the problem of scale selection. For the single-scale-based approaches [Carmona-Poyato et al., 2005, Reisfeld et al., 1995, Teh and Chin, 1989], the major challenge is the determination of the region of support (ROS) or local scale. In our work, the candidate 2-junctions are detected by exploiting Teh-Chin's method [Teh and Chin, 1989] with a major change in the step of determination of ROS. The key idea in Teh-Chin's work relies on the observation that ROS could be determined by measuring the sudden change of the chord length. Given a point $p_i$ of a digital curve, let $l_k$ is the length of the chord connecting two points $p_{i-k}$ and $p_{i+k}$ and $h_k$ is the Euclidean distance of $p_i$ to the chord $l_k$. The region of support is determined by starting with $k = 1$ and gradually increasing this value until one of two following conditions is satisfied:

$$
l_k \ge l_{k+1} \tag{2.1}
$$

$$
\left| \frac{h_k}{l_k} \right| \geq \left| \frac{h_{k+1}}{l_{k+1}} \right| \qquad (2.2)
$$

The condition (2.1) measures the sudden change of the length of two chords between
two consecutive iterations while the condition (2.2) limits how far around the curve that
condition (2.1) should be applied. These two criteria could be useful for continuous curves but are fragile in the case of digital curves. Figure 2.2 presents few examples that the Teh-Chin's technique fails to correctly determine the region of support. In the case of a circle in Figure 2.2(a), the condition (2.2) turns out to measure the sudden change of the angle (i.e. $\tan(\theta_k) = \frac{2*\text{h}_k}{l_k}$) formed by the chord and the line segment $p_ip_{i-k}$ between two consecutive iterations. Therefore, by applying the condition (2.2) and/or (2.1) we conclude that every point on the circle has the same local scale of $r$ which is also the diameter of the circle. This local scale is clearly not an expected one. Naturally, as a circle is a perfectly smooth curve, the local scale at each point on the circle should be selected as one presented in Figure 2.2(d) such that the included angle estimated at that point is close to 180 degrees. In addition, the condition (2.2) is used only when the $\text{h}_k \neq 0$ and thus resulting in some cases that we can not determine true scales as presented in Figure 2.2(b) where the point $p_i$ is the middle point on the line segment $q_1q_2$. In that case, the desirable local scale of $p_i$ should be one as presented in Figure 2.2(e). Most frequently, there exists many configurations of digital curves as presented in Figure 2.2(c) that the Teh-Chin's technique could not determine the correct scale due to digitization effect and noise. Taking Figure 2.2(c) as an example, the region of support of 1 is selected for the point $p_i$ (i.e. the point $u$ in the zoomed in version) resulting in an included angle of 90 degrees at that point. This region of support is again not an expected one while the correct local scale for this case should be selected as those in the Figure 2.2(f).

<figure><img src="image_41.png" /><figcaption>Figure 2.2: Some examples in which Teh-Chin's technique fails to correctly determine the ROS. Top row: (a) ROS($p_i$) = $d$ for any point $p_i$ on a circle with radius $R$, where $l_d = 2R$; (b) ROS($p_i$) = $+\infty$ (i.e., $p_i$ is the middle point of segment $q_1q_2$ and thus $l_{k+d} > l_k$ for any $k, d > 0$); (c) ROS($p_i$) = 1 (i.e., $l_{k+1} = l_k$). Bottom row: expected ROS for each case in the top row.</figcaption></figure>
Our solution to the problem of ROS determination relies on the observation that for every point $p_i$ of a curve, there exists a trailing line segment (i.e., the segment composing of the points {$p_i, p_{i-1}, \dots, p_{i-k_t}$}) and a leading line segment (i.e., the segment composing of the points {$p_i, p_{i+1}, \dots, p_{i+k_l}$}), where $k_l > 0$ and $k_t > 0$, such that both line segments together constitute a meaningful view of that point regardless of how smooth the curve is. This observation is especially true at dominant points on the curve, where a dominant point is usually treated as the point at which two edges meet and form a vertex. This fact suggests that the ROS of a point could be determined by finding the straight lines fitted to the leading and trailing segments of that point. It turns out that this task could be efficiently accomplished using linear least squares (LLS) line fitting technique. In the proposed approach, given a curve consisting of $N$ ordered points $p_1, p_2, \dots, p_N$, the ROS at a point $p_i$ is determined as follows:

* Step 1: Start with $k_l = 1$ and gradually increase $k_l$ in increments of one to estimate the straight line $d_f$ of the form $y = \alpha + \beta x$, which provides the best fit for the points {$p_i, p_{i+1}, \dots, p_{i+k_l}$}. The parameters $\alpha$ and $\beta$ are derived by minimizing the following objective function:

$$Q(\alpha, \beta) = \sum_{j=i}^{i+k_l} (y_j - \alpha - \beta x_j)^2 \qquad (2.3)$$

Next, we define the distance error $h(p_j, d_f)$ computed as the Euclidean distance from a point $p_j(x_j, y_j)$ to the straight line $d_f$ as follows:

$$h(p_j, d_f) = \frac{|\beta x_j - y_j + \alpha|}{\sqrt{\beta^2 + 1}} \qquad (2.4)$$

The step of searching the local scale on the leading segment of $p_i$ will be terminated at some point $p_{i+k_l}$ if either of the two following conditions is satisfied:

$$\frac{1}{k_l} \sum_{j=i}^{i+k_l} h(p_j, d_f) \ge E_{min} \qquad (2.5)$$

$$h(p_{i+k_l}, d_f) \ge E_{max} \qquad (2.6)$$

The condition (2.5) requires that the average distance error associated to the fitting line is less than $E_{min}$ pixels. The condition (2.6) is designed to limit the maximum distance error from a point $p_j$ to $d_f$: no point is $E_{max}$ pixels away from $d_f$ ($E_{max} > E_{min}$). The value $s_l = k_l - 1$ is then treated as the local scale on the leading segment of $p_i$.

* Step 2: Repeat Step 1 to find the optimal scale $s_t = k_t - 1$ on the trailing segment {$p_i, p_{i-1}, \dots, p_{i-k_t}$}.

* Step 3: The ROS of $p_i$ is finally computed as: $ROS(p_i) = Min(s_t, s_l)$.
Our empirical investigation showed that the values of $E_{min}$ and $E_{max}$ produce a negligible impact on the detection rate provided that $E_{min} \in [1.2, 2.0]$ and $E_{max} \in [1.5, 3.0]$. In our implementation, we fixed the following setting for all the experiments: $E_{min} = 1.3$ and $E_{max} = 1.8$. Once the ROS is determined, we then apply Teh-Chin's algorithm to detect the dominant points from skeleton branches. Figure 2.3 shows the dominant points and the corresponding ROS(s) detected from an image. The detected points, in combination with crossing-points, are treated as the candidate junctions and will be used to detect distorted zones in the next stage.

<figure><img src="image_42.png" /><figcaption>Figure 2.3: (a) An original image; (b) the detected dominant points (small dots) and the corresponding local scales (small circles).</figcaption></figure>

### 2.1.3 Distorted zone detection

The candidate junction points we have detected previously are used in conjunction with the line thickness information to first detect distorted zones and then conceptually remove these distorted zones to eliminate their interference in terms of the distortion of median lines. In our approach, a distorted zone is identified by tackling two probing questions: where is such a zone likely to occur and how large this distortion zone would be. Naturally, the distorted zones occur at junction locations, and these zones would be restricted to small areas fitting inside the crossing structures. Furthermore, line thickness is also one of main causes of skeleton/junction distortion (i.e., *thin* objects are not or weakly subjected to skeleton distortion). Relying on these observations, the distorted zones could be easily identified by using the information of the line thickness at the candidate junction points detected in the previous steps. More precisely, we define a distorted zone $Z_J$ for a given candidate junction point $J$ as the area constructed by a circle centered at $J$ whose diameter equal to the local line thickness computed at $J$. This definition is actually a variation of the maximal inscribing circle, as presented in [Chiang et al., 1998]. By making use of line thickness information, these maximal inscribing circles are easily determined with a high degree of accuracy. We call several distorted zones that intersect together a connected component distorted zone (CCDZ). Once the CCDZ(s) have been detected, the skeleton segments lying inside these zones are treated as distorted segments and thus removed. From this point, our subsequent stage of junction reconstruction proceeds based on the reliable line segments only. Figure 2.4 (a) shows the reliable segments remaining after removing
all distorted zones (marked as gray connected components).

<figure><img src="image_43.png" /><figcaption>Figure 2.4: (a) An input image with the detected *CCDZs* (gray connected components) and reliable line segments (thin white lines); (b) the local topology defined for a *CCDZ*.</figcaption></figure>

### 2.1.4 Junction reconstruction

The junction reconstruction exploits candidate junction points to remove possible false alarms, merge candidate junction points, and correct final junction locations. This reconstruction is initiated in a first step by extracting local topologies, corresponding to sets of segments belonging to the same distorted zone or set of intersecting distorted zones. These local topologies will drive a second step in our junction optimization process. We will present these two steps in the following subsections.

#### 2.1.4.1 Extraction of local topology

This step defines and constructs the local topology at each *CCDZ*. In particular, given a *CCDZ*, its local topology is defined as the set of local lines segments, {$P_iQ_i$}$_{i=1,...,n}$, stemming from this *CCDZ*. That is, for each reliable skeleton segment stemming from a *CCDZ*, we characterize the first part of this segment by a local line segment starting from the extremity linked to the *CCDZ*. By defining and analyzing these local geometry topologies, we have significantly simplified the complexity of the objects of input images; thus, the proposed approach is able to work on any type of shape rather than straight lines and/or arc primitives exclusively. Moreover, this step can be performed efficiently by reusing the results of the ROS determination stage applied at each extremity of each reliable skeleton segment stemming from the *CCDZ*. As a result, for each *CCDZ*, we obtain a list of local line segments describing its local geometry topology. In addition to these local lines, the foreground pixels lying inside the *CCDZ* are also recorded for use as a local search neighborhood for the subsequent step of junction optimization. In summary, the local topology associated with a *CCDZ* is now represented by a list of *n* local lines, {$P_iQ_i$}$_{i=1,...,n}$, and a set, $Z_d$, containing the foreground pixels located inside the *CCDZ*. Figure 2.4 (b) illustrates a local topology extracted for a *CCDZ*.
### 2.1.4.2 Junction optimization

The goal of this step is to reconstruct the junction points for a specific *CCDZ* represented by *n* line segments {$P_iQ_i$}$_{i=1,...,n}$ and a set, $Z_d$, of foreground pixels lying inside the *CCDZ*. We accomplish this goal by clustering the line segments into different groups such that the clustered lines in each group will be used to form a junction point. Concerning this problem of clustering segments, the authors in [Hilaire and Tombre, 2001], as discussed above, calculated the intersection zones from the uncertainty domains of the long primitives. This approach is subjected to the constraint that each primitive is allowed to be clustered in one group only, increasing the difficulty of the subsequent junction linking step. Another approach to segment clustering was presented in [Maire et al., 2008] based on the idea that if we know the position of the junction, the associated line segments passing through this junction could be easily identified and *vice versa*. However, this work assumed that each neighborhood (see Figure 2.5) contains one junction only, and this approach is subjected to high computation load because the optimization step must include sufficiently large neighborhoods likely containing junctions to reduce the error introduced by the previous step of contour detection. In addition, the reweighting step does not consider the weights accumulated during the previous iterations. This omission may lead to incorrect convergence, as shown in Figure 2.5.

<figure><img src="image_44.png" /><figcaption>Figure 2.5: Incorrect convergence of the junction optimization step in [Maire et al., 2008]: (a) four line segments with the same length; (b) the detected junction, which is the same distance from the lines 1 and 2; (c) the expected junctions.</figcaption></figure>

We therefore develop an integrated solution for both clustering and optimizing tasks to address the aforementioned weaknesses, described below. In particular, the proposed algorithm is able to handle the following issues simultaneously: (1) each neighborhood can contain multiple junctions, (2) each line segment can be clustered into more than one group, and (3) junction linking and characterization are automatically derived.

The key spirit behind our algorithm is as follows. Starting from a *CCDZ* (e.g., Figure 2.7(c)), a new junction point is constructed by iteratively searching for a foreground pixel of the *CCDZ* such that the distance error, computed as the sum of weighted Euclidean distances from this pixel to the line segments of the *CCDZ*, is minimized (e.g., Figure 2.7(d)). To achieve this goal, each line segment has to be assigned with a proper weight in
the sense that the lines, which are close to the junction, would have higher weights than the ones away from the junction. This implies that the weights are set mainly relying on the distances from the junction to the lines. In practice, a smooth function (e.g., Gaussian function) should be used to update the weights. As the algorithm evolves, the junction tends to converge towards the lines with higher weights and move away from the lines with lower weights. Hence, the junction would converge to a fixed point after several iterations (e.g., Figure 2.7(d)). Once a newly optimized junction is derived, the weights are re-assigned in such a way that higher weights are given to the lines which have not been involved in constructing the junctions previously. The optimization process is then repeated to find a new junction (e.g., Figure 2.7(e, f)). This continues until every line segment has been participated in constructing at least one junction. A final post-processing step is then applied to make the topology of the obtained junctions be consistent (e.g., Figure 2.7(g)). The proposed algorithm works as follows.

Let $w_i$ be a weight assigned to the line segment $P_iQ_i$ with $1 \le i \le n$, and $\Omega_J$ be a set of optimal junctions found during the optimization process. At the beginning, $\Omega_J \leftarrow \emptyset$ and all line segments $\{P_iQ_i\}$ are marked as unvisited. Basically, the weights could be initiated uniformly (e.g., $w_i = 1.0$), but we can make faster the process of junction convergence by incorporating some priority. One common way is to assign the weights with respect to the strength of the line segments [Hilaire and Tombre, 2001, Maire et al., 2008]. Followings are the main steps of the proposed algorithm with the outline in Figure 2.6.

<figure><img src="image_45.png" /><figcaption>Figure 2.6: Outline of our junction optimization algorithm.</figcaption></figure>

* Step 1: Search for an optimal junction $J^*$:

$$J^* = \arg \min_{J \in \mathcal{Z}_d} \left\{ \sum_{i=1}^{n} w_i \cdot d(J, P_iQ_i) \right\} \quad (2.7)$$
where $d(J, P_iQ_i)$ is the Euclidean distance from $J$ to $P_iQ_i$.

* Step 2: Update the weights {$w_i$}:

$$w_i = w_i \cdot \exp\left(\frac{-\pi \cdot d(J^*, P_iQ_i)^2}{S_{CCDZ}}\right) \qquad (2.8)$$

where $S_{CCDZ}$ is the area of the CCDZ.

* Step 3: Enact a penalty (i.e., smaller weight) for the line segment farthest from $J^*$:

$$w_{imax} = \frac{w_{imax}}{\tau} \qquad (2.9)$$

where $imax = \arg\max_i\{d(J^*, P_iQ_i)\}$ and $\tau > 1$. If there are several line segments with the same greatest distance from $J^*$, one is randomly selected to assign a penalty.

* Step 4: Repeat steps {1, 2, 3} until $J^*$ converges to a fixed point or a given number of iterations has been reached. Then, insert the newly obtained junction to $\Omega_J$: $\Omega_J \leftarrow \Omega_J \cup \{J^*\}$, and go to Step 5.

* Step 5: Determine the line segments that pass through the junction $J^*$ and mark them as *visited*. A new cluster is constructed corresponding to these line segments. If all line segments have been marked as visited, go to Step 7. Otherwise, go to Step 6 to look for other junctions.

* Step 6: Reinitiate the weights: $w_i = 1$ if the label of $P_iQ_i$ is *visited*; otherwise:

$$w_i = \prod_{k=1}^{L} \exp\left(\frac{\pi \cdot d(J_k^*, P_iQ_i)^2}{S_{CCDZ}}\right) \qquad (2.10)$$

where $L$ is the number of times that steps {1, 2, 3, 4, 5} have been fulfilled, and $J_k^*$ is the optimal junction found during the corresponding cycle. Return to Step 1.

* Step 7: Topology consistency verification by resetting the weights: $w_i = 1$ if the line $P_iQ_i$ is involved in only one cluster; otherwise $w_i = w_\infty = K \cdot \sqrt{H^2 + W^2}$, where $W$ and $H$ are the width and height of input image respectively, and $K = |\Omega_J|$. Then, apply Step 1 to the line segments in each cluster to obtain the final junctions. In this way, the lines assigned with the weight $w_\infty$ are fixed in one place.

The idea of using distance error minimization in Step 1 has been employed in several works. [Hilaire and Tombre, 2001] employed least squares error minimization to find the optimal position of the junction, but this process is performed separately from segment clustering. [Maire et al., 2008] developed this idea by incorporating a reweighting step like that in Step 2 but differing in that it does not incorporate the weights accumulated during the previous iterations and requires a training step to empirically derive a parameter controlling the decay of distance tolerance.

Our investigation has shown that Step 1 will quickly converge to the optimal junction if the weights are updated taking into account the weights derived during the previous
<figure><img src="image_46.png" /><figcaption>Figure 2.7: (a) An image with its skeleton; (b) the *CCDZ(s)* and the reliable line segments; (c) the local topology configuration extracted for one *CCDZ* (marked by $Z_d$); (d) the first cycle of steps {1, 2, 3, 4, 5}: the junction $J_1$ is found corresponding to the cluster containing line segments {1, 3, 4}; (e) the second cycle: the junction $J_2$ is found corresponding to the second cluster comprised of lines {1, 2}; (f) the third cycle: the junction $J_3$ is found corresponding to the third cluster of {1, 5}; (g) topology correction for three junctions.</figcaption></figure>

iterations. In addition, we avoid the training step by normalizing the distances, $d(J, P_iQ_i)$, based on the area of the *CCDZ* (i.e., the factor $\pi \cdot d(J, P_iQ_i)^2/S_{CCDZ}$ is equal to the ratio of the area constructed by a circle with radius of $d(J, P_iQ_i)$ centralized at $J$ and the area of *CCDZ*). Step 3 enacts a penalty (the parameter $\tau = 2$ in our implementation) for the line segment farthest from the optimal point $J^*$. If there are several line segments with the same greatest distance from $J^*$, one is randomly selected to assign a penalty. This step is used to allow the optimization process to quickly converge to a correct junction location. More importantly, it acts as a *trigger* to break the balance state or incorrect convergence, if any, as discussed in Figure 2.5. Note that if one line segment is penalized, it does not imply that this line segment will not pass through the *latest* optimal junction.

Step 4 is used to repeat the three steps above until the optimal junction is found. The obtained junction is then added to the set $\Omega_J$ (e.g., the junction $J_1$ in Figure 2.7(d)). Next, the line segments that actually form this junction are determined by looking for the lines whose distances from the detected junction tend to form a monotonically decreasing order (e.g., the lines {1, 3, 4} in Figure 2.7(d)). This is accomplished because at each iteration, the optimal junction would converge towards the lines with higher weights and move away from the lines with lower weights. Therefore, the distances from the optimal junction in each iteration to the line segments are recorded and then used to determine the real lines passing the most recently found junction. The obtained lines are then associated to a new cluster, and marked as visited (i.e., already involved in at least one junction). If all
lines have participated in constructing at least one junction, the algorithm terminates after checking topology consistency in Step 7. Otherwise, Step 6 is invoked to initiate a new cycle to find other junctions (i.e., a cycle is composed of the first five steps {1, 2, 3, 4, 5} to completely find a new optimal junction).

In Step 6, the weights are reinitiated such that more priority or higher weights are given to the lines that have not yet been involved in junction construction (e.g., the lines {2, 5} in Figure 2.7(d)). To this end, the recorded distances that violate the monotonic decrease are used to accumulate the weights for the lines. In this way, these lines increasingly gain weight, and at the end, when the weights are large enough, the optimization process (i.e., steps {1, 2, 3, 4}) will be driven by these weights, leading to a new junction convergence at the corresponding lines (e.g., $J_2$ in Figure 2.7(e) and $J_3$ in Figure 2.7(f)).

Step 7 is aimed at verifying the topology consistency of all line segments in the obtained clusters. At this time, we obtain *K* clusters, each containing one optimal junction. As one line segment, say $P_iQ_i$, can be clustered in several groups (e.g., the line 1 in Figure 2.7(f)) and there is no warranty that all the optimal junctions in these groups will form a straight line that fully contains $P_iQ_i$, such situations must therefore be identified and corrected. This step could be easily processed by setting a large enough weight for the line $P_iQ_i$ and then performing Step 1 once for each cluster. In this way, a small change in the distance error computed from each point $J \in Z_d$ to the line $P_iQ_i$ will cause a large change in the objective function in Step 1. The line $P_iQ_i$ is thus fixed in one place, and the new optimal junctions found in the clusters, in which $P_iQ_i$ is involved, become consistent (Figure 2.7(g)). Figure 2.7 demonstrates the steps of our junction optimization algorithm, and Figure 2.8 shows all the detected junctions and the corresponding local scales.

<figure><img src="image_47.png" /><figcaption>Figure 2.8: Detected junctions (red dots) and local scales (circles).</figcaption></figure>

## 2.2 Junction characterization

One of the main advantages of our junction reconstruction process is that the detected junctions could be automatically characterized and classified into different types, such as T-, L-, and X-junctions. More generally, we wish to characterize any complicated junctions in the same manner based on the arms forming the junction. In our case, as each junction point is constructed from the local line segments of one group, we can consider these line segments as the arms of the junction point. However, as each *CCDZ* can contain multiple