Rachel Bocquet
email: rachel.bocquet@univ-savoie.fr

Product and process innovations in subcontracting: Empirical evidence from the French 'Sillon Alpin'

Keywords: Subcontracting relationships, small firms, product/process innovations. JEL: L24, L26, 031, L61 Subcontracting relationships, small firms, product and process innovations. JEL: L24, L26, 031, L61

This paper investigates the role that subcontracting relationships (collaborative outsourcing versus traditional subcontracting) can have on a subcontractor's ability to innovate in process and product. In order to measure the "full" impact of subcontracting relationships on innovation, we take into account the possible interaction between process and product innovations. The empirical test is based on 93 small firms operating in "pure subcontracting industries". Using a bivariate probit model, we give evidence that process and product innovations are not independent choices. The test confirms the positive impact of collaborative outsourcing agreement on the subcontractor's probability to innovate whatever the type of innovation. Finally, the results show that process and product innovations are reinforced by different inter-organizational practices and tools as well as distinct absorptive capabilities. This suggests important implications for subcontractors' competitive position.

Introduction

The new context of knowledge-based economy has important implications for companies operating in "pure subcontracting industries" 2 [START_REF] Hätönen | 30+ years of research and practice of outsourcing -Exploring the past and anticipating the future[END_REF]. Nowadays, subcontractors are not only required to simply produce but are often urged to generate the technological knowledge which fuels new product and process development. Since the early 90s, a growing body of research has endeavored to describe this new "collaborative outsourcing mode" based on interdependent and long-term relationships [START_REF] Cohendet | A dual theory of the firm between transactions and competences: conceptual analysis and empirical considerations[END_REF][START_REF] Baudry | Incitation et coordination dans la firme-réseau[END_REF][START_REF] Takeishi | Knowledge partitioning in the interfirm division of labor: The case of automative Product development[END_REF][START_REF] Amesse | Issues on Partnering: Evidences from Subcontracting in Aeronautics[END_REF]Nonaka and Takeichi 1995).

Quite surprisingly, there are very few empirical studies which provide direct information on innovation and technology transfer capabilities of subcontractors associated to this new mode [START_REF] Takeishi | Knowledge partitioning in the interfirm division of labor: The case of automative Product development[END_REF]. In this paper, we would like to assess to what extent "talented suppliers" (Smith and Transfield 2005) that are placed in collaborative relationships might be more innovative or at least more actively involved in innovation than traditional subcontractors.

Besides, we know very little about the type of innovation (process and/or product) although this may be a key aspect to better understand the firms' competitive position [START_REF] Weiss | Adoption of product and process innovations in differentiated markets: the impact of competition[END_REF]. The special attention given to the possible interaction between product and process innovations makes this study different from other studies that focus only on product innovation or sometimes on process innovation.

To assess the full impact of the type of subcontracting relationships on the ability of a subcontractor to innovate in process and product, we first specify two types of subcontractors according to the nature of their subcontracting agreements, their inter-organizational practices and tools, and their absorptive capacities [START_REF] Cohen | Absorptive capacity: A new perspective on learning and innovation[END_REF]. Secondly, we measure this impact according to the type of subcontractors' innovation (process and/or product). By following the Oslo Manual (OECD 2005), we define innovation in a comprehensive way at 2 Pure subcontracting industries are considered those in which 80% of the turnover derives from subcontracting activity (Sessi 2007). These industries are not delineated according to a sectoral base (nature of the final output) but to a destination base (volume of the collected activity).

the decision making level of the firm. There will be innovation when the firm has introduced a substantially improved or completely new product and/or process in the last three years (2004)(2005)(2006).

The empirical analysis is based on data collected from subcontracting firms in May 2007.

All firms were operating in "pure subcontracting industries". They are by nature quasi-firms insofar as they depend more or less on other firms. Pure subcontracting industries are also made up of a large number of small independent companies which operate in traditional or low-tech activities (Sessi 2007). The study was conducted in one of the biggest industrial subcontracting regions in France: the "Sillon Alpin".

By estimating a bivariate probit model we have made several advances. Firstly, in line with previous empirical studies, results show that process and product innovations are not independent. Secondly, the test confirms the positive impact of a collaborative outsourcing agreement on the subcontractor's probability to innovate whatever the type of innovation.

Finally, we give evidence that product and process innovations are associated with differentiated inter-organizational practices and tools and distinctive absorptive capabilities.

The paper is organized as follows: Section 2 presents the theoretical foundations of the research; Section 3 sets out the empirical procedure and describes the dataset; Section 4 discusses the empirical results. In Section 5 we conclude with several theoretical implications and primary conclusions for policy makers.

Innovation in subcontracting firms

Studying subcontracting is difficult since it has been defined, elaborated and used differently.

Technology transfer literature considers subcontracting as an asymmetric inter-firm relationship. Marketing and purchasing literature focuses on subcontracting as partnering in the context of single development projects. The concept itself remains multi-faceted and heterogeneous (Amesse et al. 2000): it is linked with opportunism and capabilities dimensions (MacIvor 2009) and distinct levels of analysis (the interfirm relationship as a whole versus the single development project). Moreover, the primary concern of most studies is to analyze subcontracting from the point of view of contractors, neglecting the suppliers' innovation performance [START_REF] Nobeoka | The influence of customer scope on supplier learning and performance in the Japanese Automobile Industry[END_REF]. In order to have a more integral framework, we consider transaction-based and knowledge-based approaches of the firm. This allows us to distinguish traditional subcontracting from collaborative outsourcing and understand their potential impact on subcontractors' innovation (2.1). Then, we clarify the "true" impact of subcontracting relationships by differentiating product and process innovations, taking into consideration their possible interaction (2.2).

Subcontracting relationships and innovation

In transaction cost theory [START_REF] Williamson | The Economic Institutions of Capitalism[END_REF][START_REF] Williamson | Strategy research: governance and competence perspectives[END_REF], subcontracting is merely a practice driven by cost reduction. This does not mean that there is no room for knowledge creation or innovation but these processes are a by-product of the division of labor [START_REF] Williamson | Strategy research: governance and competence perspectives[END_REF].

According to [START_REF] Baudry | Economie de la firme (Paris, La découverte, Repères)[END_REF], two types of "traditional" subcontractors can be identified: subcontractors of economy and subcontractors of specialization 3 , which differ mainly by their degree of dependence and the uncertainty level of their relationship. However, both share the same objective of producing goods and services under the guidance of large firms according to detailed knowledge specifications. Traditional subcontractors produce peripheral products that do not involve specific assets. This makes it more cost effective for a contractor to outsource if market incentives can be maintained and bureaucratic distortion avoided. The challenge for the contractor is to avoid a situation of capacity dependence. Subcontracting 3 Used to making a product itself, a firm exceptionally delegates this particular production to a subcontractor of economy because of temporary overloading or technical failure. In contrast, whenever a firm, because of its own strategy, does not intend to master a specific part of the industrial process, it will then call for a specialized subcontractor. The latter is selected using double criteria of know-how and technical equipment (Sessi, 2007). relationships are therefore based on arm's length contracts which are uncertain by nature and dependent on the subcontractor's performance. Furthermore, the degree of interdependence is generally low because the activities in question are peripheral. In this way, transaction cost theory is useful to describe non innovative or less innovative subcontracting firms : "in terms of technology transfer, what is at stake in this zone (of quasi-market relations) is the exchange of artefacts, rather than innovative ideas or new tacit knowledge" (Cohendet and Llerena 2005, pp. 182-183). In most cases, subcontractors are rarely in charge of product design, which is too specific or risky to be subcontracted. Thus, if we consider the nature of this interfirm relationship, subcontractors have no incentive to innovate in process or product.

Nevertheless, subcontractors might be able to improve their processes because of passive learning effects.

In contrast, the knowledge-based approach views subcontractors as "talented suppliers" (Smith and Transfield 2005) endowed with a new role in knowledge creation. Subcontracting relations are derived from the needs of contractors to access the complementary knowledge required to make their own skills valuable. Subcontractors contribute to building the knowledge base of their client and benefit from their accumulated absorptive capabilities [START_REF] Nobeoka | The influence of customer scope on supplier learning and performance in the Japanese Automobile Industry[END_REF]. Since the learning process is intrinsically social and collective [START_REF] Nelson | An evolutionary Theory of Economic Change[END_REF], it occurs not only through imitation, but also because of joint contributions to the understanding of complex problems based on relational long term-contracts and coordinative routines. Compared to arm's length market contracts, such arrangements are more structured, involve constant interaction between firms, more open information channels, greater trust and put less emphasis on price [START_REF] Teece | Firm Organization, Industrial Structure and Technological Innovation[END_REF]). Similarly, Van Echtelt et al. (2008) demonstrate that suppliers' involvement in product development is more effective when close relationships are adopted. Long term benefits will depend on the ability of the contractor to manage a process along which learning routines are built to ensure that the capacity sets of both parties are aligned and remain useful for future projects. Since the relationship can be close but adversarial, [START_REF] Nobeoka | The influence of customer scope on supplier learning and performance in the Japanese Automobile Industry[END_REF] find that it is important to distinguish between the scope and the degree of inter-firm cooperation, rather than simply assume that "the fewer the customers the more cooperative the inter-firm relationship" (p.730). They show that suppliers that cultivate highly cooperative relationships with multiple customers can benefit from more learning opportunities than suppliers with fewer customers. Here, two main arguments should be retained.

The first concerns the type of contractual agreement, which in the case of collaborative outsourcing is not a matter of dependence but of co-specialization [START_REF] Teece | Firm Organization, Industrial Structure and Technological Innovation[END_REF]. Contractual mechanisms have to guarantee incentives for innovation. The length of the contract (mid/long term) and its explicit nature becomes a guarantee if compared to a short-term open, repetitive order, which characterizes traditional subcontracting. Then, subcontractors will be encouraged to innovate in order to reap future gains and benefit from the renewal of the contract to enjoy the fruits of the quasi-rent. The second argument relates to the weakness of the contractual dimension to qualify the full potential of subcontracting relationships. The knowledge-based approach to subcontracting is comparable to a process that depends both on the type of agreement and the quality of interaction between the contractor and subcontractor. To transfer and share knowledge, it is necessary to build routines as well as incentive schemes and information-sharing rules [START_REF] Blumenberg | Knowledge transfer processes in IT outsourcing relationships and their impact on shared knowledge and outsourcing performance[END_REF]. From this perspective, characterization must include inter-organizational practices and tools and absorptive capabilities of firms.

To guarantee the integration of activities and flow of knowledge between subcontractors and contractors, two types of practices and tools can be considered as determinants of the innovation learning process. The first are practices dedicated to the coordination of quality, such as insurance-quality procedures, just-in-time or lean supply [START_REF] Baudry | Economie de la firme (Paris, La découverte, Repères)[END_REF]. Since the outcome of the exchange is difficult to predict, these practices are necessary to make sure that a product or process will meet quality requirements. They also facilitate the renewal of contracts and promote the subcontractor's technological potential. [START_REF] Baudry | L'économie des relations inter-firmes[END_REF] shows that the closest subcontractors use coordination mechanisms that "are no longer reduced to price mechanisms but require practices and tools that reveal the ability of a subcontractor to deliver goods in due quality and time and to innovate" (p. 106). Studying the case of the lean supply model, [START_REF] Lamming | Beyond partnership: strategies for innovation and lean supply[END_REF] suggests that these new practices and tools foster the ability of the subcontractor to innovate. Secondly, logistical integration tools, such as Electronic Data Interchange (EDI) or Enterprise Resource Planning software (ERP) have become strategic in the development of new forms of subcontracting that include the sharing and diffusion of knowledge [START_REF] Raymond | Adopting EDI in a network enterprise: the case of subcontracting SMEs[END_REF]. EDI help share data and applications (such as ERP) among users in different organizations [START_REF] Iacovou Charalambos | Electronic data interchange and small organization: adoption and impact of technology[END_REF]. EDI is often conducted over propriety value-added networks and controlled by one large firm 4 [START_REF] Zhu | Information transparency in electronic marketplaces: why data transparency may hinder the adoption of B2B exchanges[END_REF].

Studying ICT adoption modes of French industrial firms, [START_REF] Bocquet | Variety of ICT Adoption modes and second movers' behaviour. A Theoretical Analysis and Empirical Evidence[END_REF] show distinct behavior which leads some firms to select network-oriented ICT equipment (EDI) or software-oriented ICT equipment (ERP) while others prefer to adopt both types of ICT (EDI and ERP). The presence of an EDI can be interpreted as the signal of a network organization in which a "hub" firm decentralizes activities to subcontracting firms [START_REF] Raymond | Adopting EDI in a network enterprise: the case of subcontracting SMEs[END_REF]. [START_REF] Andersen | Organizing international technological collaboration in subcontractor relationships: an investigation of the knowledge-stickeness problem[END_REF] has shown that EDI use depends on the subcontracting type. On the basis of 445 subcontractors in the Danish industry, he gives evidence that developmentoriented subcontractors (in both product and process) are more likely to use EDI than other traditional subcontractors. 4 New tools such as Webedifacts may change the Propriety issue since the initial cost load is much less than it used to be in the EDI-days. However, [START_REF] Bocquet | Adoption des TIC, proximité et diffusion localisée des connaissances[END_REF] show that industrial firms in the Sillon Alpin are late adopters in matters concerning EDI: with an adoption rate far lower than the national average, these subcontractors should not be concerned by this new kind of tool.

The knowledge-based literature considers the subcontractors' absorptive capacity as a key factor for successful partnership. The absorptive capacity of firms, defined as their ability to absorb outside knowledge, reflects the cumulative nature of knowledge which is largely a function of prior related knowledge [START_REF] Cohen | Absorptive capacity: A new perspective on learning and innovation[END_REF]). In the case of collaborative outsourcing, a supplier's absorptive capacity is seen as a pre-requisite to building the contractors' knowledge base. But, "it is also important for the firm to enhance absorptive capacities of the suppliers themselves" (Cohendet and Llerena 2005, p.182). This means that a contractor does not only assist in the area of cost reduction but also in increasing technological competence. The use of external links to extend a firm's base has thus been frequently related to successful innovation. This is particularly important for small subcontractors that have to "compensate for small internal resources by being good at interacting with the outside world" (Fagerberg 2005, p. 11). Through 43 case studies in Low and Medium Tech industries of nine EU countries Hirsch-Kreisen (2008) shows that the acquisition and the generation of innovation knowledge rarely takes place within firms but relies on external knowledge sources such as customers or machine suppliers.

Another way to estimate the absorptive capacities of subcontractors is to consider the firm's strategic positioning as a determinant of its ability to learn [START_REF] Fiol | Organizational learning[END_REF]. Most empirical studies on subcontracting emphasize that cost-driven objectives prevail in all types of subcontracting agreements and tend to blur all other objectives. In their qualitative study on subcontracting in the aeronautical industry in Quebec, [START_REF] Amesse | Issues on Partnering: Evidences from Subcontracting in Aeronautics[END_REF] show that subcontractors perceive all agreements as a result of the main contractor's cost-driven strategy, although the latter is seeking technology transfer. Dyer and Singh (1988) conclude that partnering does not differ significantly from arm's length contracts when cost-driven objectives are prevailing. In her study of 18 Finnish subcontractors, [START_REF] Lehtinen | Subcontractors in a partnership environment: a study on changing manufacturing strategy[END_REF] provides new evidence. Although she observes an increase of stable commitment-based relationships, partnerships involving integrated R&D processes or mutual sharing strategic visions are still very few. [START_REF] Smith | Talented suppliers? Strategic change and innovation in the UK aerospace industry[END_REF], studying the UK aerospace industry, find that new subcontracting practices based on lean supply give subcontractors the opportunity to have a new status and role. But, their ability for innovation is less apparent: only two subcontractors out of ten are engaged in innovation.

To sum up, the few studies that deal with knowledge creation and innovation through subcontracting relationships tend to confirm that a new type of subcontractor does exist.

Theoretically, these "suppliers" differ from traditional subcontractors because of the structure of the contractual agreement, the nature of their absorptive capabilities and the interorganizational devices by which they are committed to the contractor. However, empirical results concerning the supplier's ability to innovate are still ambiguous. Some studies give evidence of the impact of certain practices and tools on innovation, while others are more pessimistic, concluding that the so-called "talented suppliers" are an ideal image rather than a reality.

The ability to innovate in process and product

The clear-cut distinction between product and process innovations has important implications for a better understanding of the determinants of innovation and for the competitive position of firms [START_REF] Weiss | Adoption of product and process innovations in differentiated markets: the impact of competition[END_REF]. Several empirical studies show that product and process innovations are closely interlinked in many firms but are driven by different industry and/or firm level variables [START_REF] Vaona | Firm size and innovation in European manufacturing[END_REF]Pianta, 2008, Rouvinen 2002) or organizational capabilities (Damampour and Gopalakrishnan 2001). Using the SIEPI-CIS2 database, [START_REF] Vaona | Firm size and innovation in European manufacturing[END_REF] prove that product and process innovations are present together. In the case of small firms, process innovation is reinforced by strategies for production flexibility while product innovation is explained by patenting. After comparing small manufacturing firms in Germany and the United Kingdom, [START_REF] White | Small firms Innovation: why regions differ?[END_REF] note that process innovation tends to be independent from product innovation when the motive is cost reduction. In contrast, process innovation tends to be more related to product innovation when the level or intensity of the latter is high or requires similar technical expertise.

Other empirical studies test if one type of innovation is a driver of the other type or if they complement each other. [START_REF] Kraft | Are product-and process-innovations independent of each other[END_REF] shows that product innovation has a significant impact on process innovation -but no evidence can be found for the reverse. In contrast, [START_REF] Martinez-Ros | Explaining the decisions to carry out product and process innovations : the spanish case[END_REF] demonstrates that product and process innovations are complementary after checking for the presence of unobserved firm effects like managerial ability, experience, or other factors that remain constant during one period. Athey and Schmutzler (1995) show that returns on implementing a product innovation are higher when the firm also implements a process innovation in the short term.

Despite the fact that these empirical studies use different methodologies, they show that product and process innovations may not be independent choices. The possibility of an interaction between the two types of innovations cannot be rejected a priori. Besides, product and process innovations are driven by different factors. In the case of subcontracting firms, the pattern of interaction between product and process innovations is still unclear. There remains important issues: does the "true" potential of collaborative outsourcing have consequences for small manufacturers? Is the result a process or a product innovation, or both?

Method

In this section, we present the data (3.1), the empirical procedure (3.2) and the variables used in this study (3.3).

Data

Data were collected in May 2007. A specially designed questionnaire was e-mailed to 1126 companies (with more than 2 employees) operating in "pure subcontracting industries" (Sessi 2007). All firms are by nature quasi-firms insofar as they are in a state of dependence (more or less favourable) regarding their contractors, particularly concerning equipment and car manufacturers who constitute the main customer sector. In the sample the share of subcontracting activity collected by firms reaches 88%. The size of firms under study matches the sector-based data established on a national scale (Sessi, 2007). Over half the subcontractors are small (micro) independent firms. Sampled firms are located in the "Sillon Alpin". This region is the biggest industrial subcontracting area in France, employing 25% of the people working in the metal cutting and forming sector. 75% of the country's mechanical and bar turning industries are concentrated in this region. In the sample, the biggest majority of subcontractors (80,6%) belongs to the metal cutting and forming sector. This sector represents the first group of subcontracting activities nationally (Sessi 2007). If firms are operating in different activities (Bar Turning, Mechanical, Forge, Stamping, Cutting) and supply various industries such as the car industry, they compete in environments that are similar in terms of market structure and innovation. Staying dependent from their contractor and due to their small size, many firms (especially those with proprietary know-how) should be reluctant to participate in inter-firm knowledge-sharing activity.

Senior managers were asked to provide information about what type of subcontracting agreements they had, paying particular attention to the agreement with the most important contractor. We obtained details about their degree of dependence, their role in the subcontracting relationship and the level of uncertainty they face. Another part of the questionnaire was about their ability to innovate in product and process, their organizational competencies, their strategic priorities and the different sources of technical knowledge they use to support innovative activities. We collected 93 exploitable questionnaires5 , and the final data is representative of subcontracting firms situated in the "Sillon Alpin" for the 3 sectors and the 2 size classes (See Tables A1 andA2 in Appendix).

Empirical procedure

Subcontracting firms innovate because it is profitable for them to do so (expected returns exceed associated costs). Expected profits of an innovator i must be higher with innovation (Π I i ) than without innovation (Π N i ), ie:

y * i = (Π I i ) -(Π N i ) > 0 (1)
A latent regression can be specified as:

y * i = α + β' C X C + β' O X O + β' S X S + β' SO X SO + β' CO X CO + ε (2)
Where: X C represents the types of subcontracting agreements, X O captures the organizational practices and tools stated in the subcontracting firm, X S captures its strategic orientation, X SO characterizes the sources of knowledge used to support innovative activities, X CO represents the control variables and ε is the error term (assumed to be normally distributed).

Unfortunately, the subcontractors' profits with and without innovation cannot be observed.

We only observe whether it innovates or not. The observed counterpart to y* i is y i , which takes a value of 0 (no innovation) or 1 (innovation), noted as follows:

1 if and only if y * i > 0 y i =

(3) 0 otherwise Table 1 indicates that 16 subcontractors (17%) qualify for the title of highly innovating firms as they have made innovations in both products and processes in the three years prior to the survey. However, estimating the probability to innovate using a probit model is restrictive as this supposes that the two processes are independent. As shown before, this hypothesis is not adapted because product and process innovations can be linked. It is therefore more appropriate to estimate a system of equations rather than separate estimations for each type of innovation. For the two types of innovation, process and product, respectively noted j and k, we have:

P(y ij =1) = Ф (β' j X ij + ε ij ) P(y ik =1) = Ф (β' k X ik + ε ik ) (4)
Where β is a vector of coefficient, X i denotes the vector of explanatory variables, and ε ij and ε ik the error terms which follow a bivariate normal distribution with zero mean, unit variances and ρ is the correlation coefficient of the error terms. We used a bivariate analysis to test the correlation between the types of innovation. The test was carried out with a simple t test on the ρ coefficient. If ρ is statistically different from zero, the two innovation processes are not independent and should not be estimated separately.

Before presenting the econometric results, we first describe the variables used in the regressions (see Table 4).

Measures

Dependent variables

By following the Oslow Manual and the Community Innovation Survey, we privilege the "subject" approach of innovation (Mairesse and Mohnen 2010). The information is collected at the firm-level, including all its innovation outputs and activities. This implies that we do not have data on particular innovation projects. Innovation can be classified by basic purpose (products and processes) and degree of novelty (new to the firm and/or new to the industry).

In this study, we do not differentiate between subcontractors by the intensity of innovation since this is mainly incremental in traditional and low-tech industries (De jong and Marsili 2006). Process innovation (INOPROC) and product innovation (INOPROD) are examined as two binary measures of whether or not new or significantly modified production processes or products were introduced in the 3 years prior to the survey .

Independent variables

The covariates used in the regression correspond to the four following series of variables.

Types of subcontracting agreements. The type of contractual agreement is recorded from three dimensions derived from studying the literature (see section 2): the role played by the subcontractor in the relationship, the scope and the degree of dependence on its main contractor and the level of uncertainty. The operationalization of these dimensions has been accomplished with seven core variables used before (see Table 2 hereafter).

Table 2. Definition of the variables used in the cluster analysis Variables Definition REAL = 1 if the subcontractor manufactures products only (= 0 otherwise) CONCEPT = 1 if the subcontractor participates (even partially) in the development of the products / processes (= 0 otherwise) NDO = Total number of contractors VOLP = Part of the collected subcontracting activity from the main contractor / total volume of production of the subcontractor CONTRACT = 1 if the contract is written (= 0 otherwise) DUREE1 = 1 if the duration of the agreement is less or equal to 1 year (= 0 otherwise) RENEG = 1 if the agreement is systematically submitted to renegotiation (= 0 otherwise)

A principal component analysis 7 (PCA) was conducted on these seven variables. The MSA test (Hair et al. 1998) showed that all the variables were good candidates for a PCA (MSA values>0.5). In addition, KMO and Bartlett's test of sphericity met common standards 6 In this study, we adopt an absolute definition of innovation since we consider that all firms are innovative as soon as they declare to be innovative. As noted by [START_REF] Freel | Strategy and structure in innovative manufacturing in SMEs: The case of an English region[END_REF], the use of a minimum threshold for the share of sales attributed to new or modified products/processes would allow us to check the robustness of our results. Unfortunately, like many authors that examine the choice between product and/or process innovations [START_REF] Vaona | Firm size and innovation in European manufacturing[END_REF][START_REF] Rouvinen | Characteristics of product and process innovators: some evidence from the Finnish innovation survey[END_REF][START_REF] Martinez-Ros | Explaining the decisions to carry out product and process innovations : the spanish case[END_REF], we do not have such information.

7 All these results are available from the author on request.

(KMO = 0.55 and p < 0.001). The PCA uncovered three factors that summarize the theoretical dimensions well (59.8% of the total explained variance). A non-hierarchical cluster analysis was then carried out on the factor scores. To determine the final number of clusters, we used three usual criteria: (i) the statistical accuracy of the classification measured by the ratio of within and between cluster variances, (ii) the number of firms per cluster, and (iii) the economic significance of the clusters identified. According to the criteria, the version with two clusters of subcontracting firms was preferred8 . The variable DUREE1 could not be used to describe the profile of clusters as there was no significant effect. This suggests that subcontractors (whatever their profile) are placed in similar conditions concerning the duration of their agreement. The two clusters can be interpreted as follows (see Table 3):

In Cluster 1, 41 subcontractors (44.1%) manufacture products only and do not have a free hand in product or process development. They are very dependent on their contractors (due to the small number of contractors, and the authority of the main one). The presence of arm's contracts, which are continually in the balance, conforms to traditional subcontracting.

In Cluster 2, 52 subcontractors (55.9%) participate in product/process conception.

Subcontractors are linked to a larger number of contractors and the weight of the main contractor is weaker than in Cluster 1, although it is still 22% of the total volume of production. Contracts are established (written) and are less risky than with traditional subcontractors (not systematically renegotiated), which reflects relationships based on trust and reciprocity. This type of agreement corresponds more to collaborative outsourcing based on incentive schemes as well as routines for the coordination of knowledge and learning process.

The two dummy variables (C1 for traditional subcontracting and C2 for collaborative outsourcing) used in the econometric analysis, result from this classification procedure. Note: We interpret the two clusters (C1 and C2) with the variables used in the cluster analysis. We calculated the mean of each variable in each cluster. For example, Traditional subcontractors have fewer customers (28) than suppliers (86.9). This table also provides the total number of observations (N) for each cluster.

Organizational practices and tools. To reveal how much integration exists between subcontractors and contractors we use two series of variables. The first is related to the existence of a shared information system through the use of the EDI network and/or ERP applications. The second series of variables aims to identify the presence of practices dedicated to the coordination of quality in new forms of subcontracting [START_REF] Baudry | Economie de la firme (Paris, La découverte, Repères)[END_REF]:

FORM indicates if there are formal agreements between subcontractors and their suppliers or contractors, QUALI informs about the adoption of organizational practices centered on quality management. LPJAT reveals if subcontractors have implemented a "just-in-time"

logistical organization.

Sources of knowledge. Like many authors, we underline the importance of external sources of knowledge used by subcontractors as a complement to their internal sources. Four variables were used to distinguish external sources from internal ones. The external sources are defined as follows: PREST stands for firms that collaborate with external providers to acquire new knowledge (private firms specialized or not in R&D and innovation, technical centers, public research centers, associations). ACTIFS identifies firms that buy specific assets to innovate such as patents, licenses or machines. As far as internal sources are concerned, we distinguish firms that rely on their own R&D or engineering departments (BERD) from those that recruit new workers or train staff to support their innovative activities (RH).

Strategy variables. To complete the specification of the absorptive capabilities of subcontractors, we have included a menu of variables related to their strategic objectives. This provides the following explanatory variables DEVINOV (development of R&D or innovation), RATION (cost-reduction), REDUCDEP (reduction of dependence from contractors), DIVER (market diversification).

Control variables. Two control variables have also been defined: firm size is measured by EFF1 (less than 10 employees) and EFF2 (10 employees or more). As far as industrial affiliation of subcontractors is concerned, we have undertaken some regrouping inside the SIC9 four digit level, in order to acknowledge the two main activities of the metal cutting and forming sector in the "Sillon Alpin": bar turning (DEC) and mechanical (MECA). The other subcontracting activities are noted as APE2. = 1 if the type of subcontracting agreement corresponds to collaborative outsourcing (= 0 otherwise) Organizational practices and tools QUALI =1 if the firm has adopted organizational practices centered on quality management such as certification, total productive maintenance, value analysis (= 0 otherwise) LPJAT = 1 if the firm has adopted a "just-in-time" logistical organization (= 0 otherwise) EDI = 1 if the firm has adopted an Electronic Data Interchange (EDI) system (= 0 otherwise) ERP = 1 if the firm has adopted an Enterprise Resources Planning (ERP) software (= 0 otherwise) EDI_ERP =1 if the firm has adopted an EDI system and an ERP planning software (=0 otherwise)

Strategy variables

Results

We estimated the system of equations defined in Eq. 4, with a bivariate probit model. As regards the robustness of the model, we used White's procedure (1982) to deal with any potential heteroscedasticity problems. The percentage of correct predictions (60.2%) suggests that the model has a good explanatory power compared to the "naïve prediction ratio" of 25%10 . The first important result concerns the statistical link between the two innovation choices.

In Table 5, the correlation coefficient Rho is significantly different from zero suggesting that process and product innovations are not independent choices. Thus, the estimation of two separate models would lead to a loss of efficiency and possible misleading results (Rouvinen 2001).

Clearly, product and process innovation are affected by different factors. This confirms previous empirical results that make a clear distinction between the two types of innovation: process and product innovations only have the type of subcontracting agreement in common.

As expected, the type of subcontracting agreement explains the ability to innovate of a small manufacturer. Suppliers (C2) are more likely to innovate than traditional subcontractors (C1).

When arrangements are well-established and not systematically renegotiated, and when suppliers are invited to play an active role in design, new critical components (trust and reciprocity) are introduced that favor their ability to innovate both in product and process.

As suggested by the knowledge-based perspective, the nature of the contract is not sufficient to assess the full role of subcontracting relationships on innovation patterns. Other factors such as the presence of organizational practices and tools and the absorptive capacities of subcontractors are likely to impact on their ability to innovate. These variables have a positive impact on innovation. The likelihood to innovate is higher if subcontractors have adopted organizational practices centered on quality management (QUALI) and logistical tools (ERP and EDI_ERP). This confirms the importance of the "quality" of integration between contractor and subcontractor. However, few variables have a positive effect, meaning that innovation capabilities are not necessarily supported by all new practices. This result matches the literature on new practices in subcontracting (including lean practices) which underline their weak impact on subcontractors' innovation capabilities. Furthermore, and more interestingly, process and product innovations are not affected by the same organizational practices or IT tools.

Process innovation is helped by the presence of quality-oriented practices and ERP software while the use of both EDI and ERP (cross variable) diminishes the likelihood to innovate in process. In contrast, product innovation depends on the sole combination of both EDI and ERP technologies, and is not affected by quality oriented practices. Considering the complementarity between ICT, we note that sharing an information system with a hub firm has a positive effect on product innovation and an opposite effect on process innovation. This result is in line with recent developments on new forms of subcontracting. The presence of such a logistical integration, which is sometimes comparable to an irreversible organizational investment, consists of the implementation of a common language between principals and subcontractors. What is at stake here is the mutual exchange of complementary forms of knowledge between firms for the co-conception of new products. In contrast, process innovation is associated with ERP and organizational practices centered on quality management mainly aiming for cost reduction. These devices do not concern the technological potential of the subcontractor.

As for the strategic variables, the formulation of a clear objective oriented towards R&D or innovation (DEVINOV) decreases the probability to innovate in process. Besides, process innovation is explained by a cross effect that measures the pursuit of cost-driven and innovation objectives. This result, in line with previous studies, shows that "even when the main contractor is concerned by technology transfer, cost-driven actions blur the technological objectives of any type of subcontracting agreement" (Amesse et al. 2001, p. 568). Quite surprisingly, strategic objectives oriented towards R&D and innovation, are not positively associated with product innovation. A candidate explanation for this result is that product innovation is a never ending improvement process rather than an asserted strategy of R&D or new product development. As noted by [START_REF] Pavitt | Sectoral patterns of technological change: towards a taxonomy and a theory[END_REF], "competitive success [of small specialized suppliers] depends to a considerable degree on firm-specific skills reflected in continuous improvements in product design and in product reliability" (p. 359). This explanation is strengthened if we consider the sources of knowledge which support the innovative activities of subcontractors. The role of firm-specific skills is captured by the significant and positive effects of internal R&D and engineering activities (BERD) on process innovation and the recruitment of new competence and staff training on product innovation (RH). Though different, the internal sources play a significant role on both types of innovation. The significant link between process innovation and BERD is well-explained by the fact that small subcontractors in metal manufacturing produce a relatively high proportion of their own process technology [START_REF] Pavitt | Sectoral patterns of technological change: towards a taxonomy and a theory[END_REF]. Process innovation is also driven by external sources of knowledge. This supports the absorption capacity hypothesis [START_REF] Cohen | Absorptive capacity: A new perspective on learning and innovation[END_REF]. In contrast, product innovators solely rely on their main contractor as a source of innovation. Following [START_REF] Bruce | Dangerous liaisons: an application of supply chain modelling for studying innovation within the UK clothing industry[END_REF], the relationship between supplier and contractor seems too close. This reduces the subcontractor's absorptive capacity and leads to a failure to absorb and benefit from external sources of innovation [START_REF] Pardo | Technical capital and social capital in outsourcing networks: complements or subsitutes[END_REF].

Considering the control variables, sectoral variables are never related to product innovation only. The fact that process innovation is significantly associated with APE2

(rubber and plastic products) matches well the behavior of "science-based" firms. These firms innovate both in process and product, with a prevalence of process over product.

Firms operating in metal manufacturing sectors belong to the cluster of "suppliers of intermediate goods" (Archibughi and al. 1991), or "supplier-dominated firms" (De [START_REF] Jong | The fruit flies of innovations: A taxonomy of innovative small firms[END_REF] which are mainly small process-oriented firms. As observed by these authors, micro-firms (from 1 to 9 employees) are over-represented among supplier-dominated firms.

Finally, the metal cutting and forming sector (that represent more than 80% of the sample)

refers to important aspects of low-tech industries with specific innovation modes [START_REF] Hirsch-Kreinsen | Low-Tech[END_REF]. With a high percentage of small firms, innovation is less technology oriented than those of High and Medium Tech firms. Though process innovators are innovating through external sources, the main customer still appears to be the primary source of innovation for most suppliers. Collaborations with external partners such as providers, scientific institutions, specialized consultants, etc. does not appear to be as systematic as it is in HMT industries.

Conclusion

Innovation is seen as a crucial factor for the survival and competitive strength of small firms.

This paper shows that a small subcontractor's ability to innovate is a complex phenomenon driven by multiple influences, including the type of subcontracting agreements, the nature of inter-organizational practices and tools, and the "quality" of the subcontractor's absorptive capabilities. Contrary to the majority of studies that focus either on product or process innovation, the results indicate that the interaction between the types of innovation themselves is also complex since they are not independent choices. The clear-cut distinction between product and process innovations in subcontracting relationships leads to important conclusions.

Firstly, this study has revealed the impact of the type of subcontracting agreement on the subcontractor's ability to innovate. Being a supplier rather than a traditional subcontractor increases the likelihood of innovation in both process and product. This supports the claim that subcontracting relationships are not only a mere practice driven by cost-reduction. Today subcontracting relationships are changing as contractual agreements give more scope for mutual commitment. This result is in line with the new generation of industrial organization theory. Small contractors may move from a dependent status to the category of innovating firm by upgrading their own innovation and technology transfer capabilities with, in some instances, the help of their main contractors. This result outlines both the role and the responsibility of the contractor in relation to the future of traditional subcontractors and their survival. Bearing in mind that 44.1% of subcontractors operate in uncertain conditions and with strong dependence, it is not surprising that these subcontractors are less committed to innovation than suppliers since their contractual arrangements provide per se no incentive to innovate.

Secondly, we have shown that subcontractors differ according to the type of innovation.

Process innovation is supported by the pursuit of two objectives: cost reduction and innovation. Furthermore, subcontractors are more likely to innovate in process when their activities have been integrated with their contractors in quality and information sharing (QUAL and ERP). But, this operational integration is circumscribed to a dyadic relationship to foster process innovation. In contrast, product innovation is influenced by EDI and ERP tools that play a crucial role in the sharing of information and diffusion of innovation in a network-organization. We also give evidence that product and process innovations are not affected by the same sources of knowledge. In the case of process innovation, subcontractors are more likely to innovate in process if they use formal R&D and other lower sources of technical knowledge such as engineering and external providers. Product innovation is strengthened by the recruitment of new competence and staff training. The fact that external providers do not affect product innovation means that subcontractors rely heavily on the sole understanding of the contractors' need to innovate. Even though we must remain cautious, it seems that product innovation is more likely to emerge in a network-organization under the control of the prime contractor. In this case, relationships that are too close may be a substitute rather than a complementary source to the innovation process, with some risks of lock-in for the supplier. Consistent with [START_REF] Nobeoka | The influence of customer scope on supplier learning and performance in the Japanese Automobile Industry[END_REF], one main challenge for subcontractors is to lessen their dependence by enlarging their customer scope once they strengthen their own innovation capabilities.

Thirdly, the firms' characteristics and innovation modes in pure subcontracting industries are very close to those found in Low-Tech industries. Subcontractors are mostly process innovators showing that cost-minimization and flexibility are still major sources of competitiveness for most small subcontracting firms.

The results of this explanatory research suggest further issues for policy makers and theoretical implications. In France, the setting up of "competitiveness clusters" is an attempt to bridge the innovation gap of small firms, and new public policies are being implemented to help subcontractors to innovate. However, although these policies are useful, they often miss their goal. They are too often directed at subcontractors (without differentiating them) or certain contractors (the most involved), so neglecting the relationship itself. It is time that policy makers recognize that the ability of a subcontractor to innovate depends on the nature of the subcontracting relationship and requires an alignment of their organizational practices and tools [START_REF] Van Echtelt | Managing Supplier involvement in New Product Developpement: a multiple-case study[END_REF]. Any attempt to bring a contractor close to its subcontractors might prove a useful step to create true partnership relations based on shared representations. The study shows that the theoretical model of partnership described by the knowledge-based perspective is still a distance from its practical expression in pure subcontracting industries.

The significant and positive impact of internal sources of knowledge on innovation is

another key point in this study. As pointed out by [START_REF] Freel | Innovation and cooperation in the Small firm sector: Evidence from 'Northern Britain[END_REF], internal resources are crucial and "networking is neither a sufficient nor, even, a necessary condition for innovation" (Op. Cit, p. 301). This conclusion is strengthened in the case of collaborative outsourcing if the potential of innovation of the subcontractors is looked for. We think that policy makers should develop the internal learning and absorptive capabilities of subcontractors. Some initiatives have already been conducted in this way. For instance, to compensate for resource and capability shortages of micro-firms, diverse forms of groupings have been initiated. These allow firms to propose global solutions to customers relying on their complementarities. Nevertheless, these policy initiatives are not sufficient because they neglect the most vulnerable subcontractors: the small traditional ones. Moreover, they fail to motivate a personal interest to participate in collective projects and to openly share their knowledge with other members.

Finally, we acknowledge that there are some limitations to our study. Firstly, the specificity of the population studied reduces the number of observations. But it also has the advantage that firms are relatively homogeneous. Innovation in pure subcontracting industries has rarely been a subject of interest even though it helps to better understand firms' competitiveness in low-tech industries. It would be interesting to confront these results with data from regions in other countries which still depend on these particular industries since this question has important implications for their future competitiveness. Secondly, we have to stress the limitation of an innovation survey to capture the impact of shared knowledge (that is intrinsically social and collective) on outsourcing performance [START_REF] Blumenberg | Knowledge transfer processes in IT outsourcing relationships and their impact on shared knowledge and outsourcing performance[END_REF].

Following the same methodology as the one chosen by [START_REF] Dyer | Creating and managing a high performance knowledgesharing network: the Toyota case[END_REF], it would be interesting to highlight the quantitative results with qualitative data coming from interviews with contractors and subcontractors belonging to the same network. This would make it possible to distinguish the nature of the shared knowledge during the relation process (relation-specific knowledge versus redeployable knowledge) since it does not have the same impact on the suppliers' performance [START_REF] Nobeoka | The influence of customer scope on supplier learning and performance in the Japanese Automobile Industry[END_REF]. Thirdly, our study is a static cross-sectional analysis. Changes in the subcontracting relationships over time, underlying strategic and management processes as well as their impact on innovation cannot be identified. The analysis of project-related processes to manage supplier involvement (Van der

Valk and Wynstra 2005) could be a complementary way of research. Lastly, we know that because of its cost-cutting nature, process innovation may have ambiguous effects on a firm's growth [START_REF] Fagerberg | Innovation, a guide to the literature[END_REF]. Further research is needed to assess the impact of process and product innovations on subcontractors' competitive position.

  DEVINOV = 1 if the firm aims to develop R&D or innovation (= 0 otherwise) RATION = 1 if the firm aims to reduce costs (= 0 otherwise) RATION_DEV =1 if the firm aims to develop R&D or innovation and aims to reduce costs (=0 otherwise) REDUCDEP = 1 if the firm aims to reduce the dependence from its contractors (= 0 otherwise) DIVER = 1 if the firm aims to sell in new markets (= 0 otherwise) Sources of knowledge to support innovative activities BERD =1 if the firm resorts to its research or production engineering departments to innovate (= 0 otherwise) PREST = 1 if the firm turns to external providers to innovate (= 0 otherwise) ACTIFS = 1 if the firm buys specific assets to innovate (such as patents, licenses, machines) (= 0 otherwise) RH = 1 if the firm recruits new competences or trains the staff to innovate (= 0 otherwise) Control variables Firm size (ref. EFF2= 1 if the firm has 10 employees or more) EFF1 = 1 if the firm has less than 10 employees (= 0 otherwise) Industrial sector (ref. MECA= 1 if the firm operates in the mechanical industry) DEC = 1 if the firm operates in the bar turning industry (= 0 otherwise) APE2 = 1 if the firm operates in other pure subcontracting industries (= 0 otherwise)

Table 1 .

 1 Product and process innovations of subcontractors

		INOPROC
	INOPROD 0	1
	0	26 29
	1	22 16

Table 3 .

 3 Interpretation of the two subcontracting clusters

			NDO	VOLP	CONTRAT CONCEPT	REAL	RENEG
	C1: Traditional	Mean	28.00	37.88	.02	.12	.95	.71
	subcontracting	N	41	41	41	41	41	41
	C2: Collaborative	Mean	86.90	22.33	.31	.37	.65	.54
	outsourcing	N	52	52	52	52	52	52
	Total	Mean	60.94	29.18	.18	.26	.78	.61

Table 4 .

 4 Definition of variables

	Dependent variables	Definition
	INOPROC	= 1 if the firm has introduced a substantially improved or a completely new process
		in the last three years (= 0 otherwise)
	INOPROD	= 1 if the firm has introduced a substantially improved or a completely new product
		in the last three years (=0 otherwise)
	Independent variables Definition
	Subcontracting agreements (Ref. C1= 1 if the type of subcontracting agreement corresponds to traditional
	subcontracting)
	C2

Table 5 .

 5 Results of the bivariate probit model.

					INOPROC-INOPROD
		INOPROC (y j )	INOPROD (y k )	Marginal effects
	Variables (x)	β	σ β	β	σ β	y ij =1 ; y ik =0	y ij =1 ; y ik =1	y ik =1 ; y ij =0	y ik =0 ; y ij =0
	Constant	-2.28***	0.95	-0.60	0.78
	C2	0.90**	0.91	0.69**	0.30	0.17	0.18*** 0.07	-0.42***
	QUALI	0.90**	0.40	-0.40	0.37	0.29**	0.04	-0.20	-0.14
	LPJAT	0.05	0.37	0.39	0.32	-0.03	0.05	0.08	-0.10
	EDI	-0.29	0.42	0.03	0.41	-0.08	-0.02	0.03	0.07
	ERP	1.95***	0.61	-0.71	0.55	0.50*** 0.09	-0.33*** -0.26***
	EDI_ERP	-2.56***	0.94	2.44***	0.82	-0.47*** -0.04	0.70*** -0.18**
	RATION	-0.46	0.67	-0.47	0.53	-0.03	-0.14	-0.03	0.21
	DEVINOV	-2.31***	0.78	0.11	0.58	-0.54*** -0.18	0.22	0.50
	RATION_DEV 2.67***	0.89	-0.50	0.69	0.48**	0.18	-0.35*** -0.31***
	REDUCDEP	-0.82*	0.45	-0.45	0.37	-0.20	-0.10**	-0.06	0.37**
	DIVER	-0.90	0.61	-0.25	0.38	-0.16	-0.24**	0.15	0.25***
	BERD	2.66***	0.38	0.17	0.42	0.34**	0.37*** -0.31*** -0.40***
	PREST	1.08**	0.44	0.16	0.37	0.20	0.19**	-0.13	-0.26***
	ACTIFS	0.72	0.50	0.72	0.52	-0.02	0.30**	-0.02	-0.25***
	RH	0.46	0.33	0.77**	0.33	0.05	0.13**	0.14	-0.32***
	EFF1	1.52***	0.43	-0.42	0.33	0.44*** 0.10*	-0.26*** -0.28**
	DEC	1.02***	0.38	0.26	0.40	0.20	0.18*	-0.08	-0.30***
	APE2 ρ	1.63***	0.39	0.46	0.39 -0.94** (0.38) 0.27**	0.31*** -0.13	-0.44***
	Number of				93
	observations
	Log-likelihood Wald test of ρ				-80.6 6.01**
	Rate of good				60,2%
	predictions
	Robust standard errors [using heteroscedastic-consistent errors from White's procedure] are reported in italics.
	Estimated coefficients are statically different from 0 at 10% (*), at 5% (**), at 1% (***)

The sampling rate is somewhat small (8%). It can be explained by the strategic nature of the information collected and the secrecy policy which is dominant in subcontracting activities.

For all comparisons of variances, Fisher's test is significant at the 0.000 level and indicates a good differentiation of the subcontracting firms.

Standard Industrial Classification

Four probability scores can be computed P 00 = probability of no innovation; P 01 = probability to innovate in product only; P 10 = probability to innovate in process; P

= probability to innovate in process and product.

Acknowledgments: This paper has been funded by a General Council of Isère research grant. The author would also like to thank four anonymous referees for their constructive comments.

Appendix: Data descriptives Table A1. Firms' Industrial affiliation (SIC: 4 -digit)


Dominique Lépingle

Oblique repulsion in the nonnegative quadrant

We consider the differential system ẋ = α/x + β/y, ẏ = γ/x + δ/y in the nonnegative quadrant. Here α and δ are positive, β and γ are real constants. Under some condition on the constants there exists a unique global solution. The main difficulty is to prove uniqueness when starting at the corner of the quadrant.

1 Introduction.

We are interested in the question of existence and uniqueness of the solution u(.) = (x(.), y(.)) to the following integral system x(t) = x + α (2) for any t ≥ 0. Here α, β, γ and δ are four real constants with α > 0 and δ > 0.

The system has a single singularity at each side of the nonnegative quadrant S = {(x, y) : x ≥ 0, y ≥ 0} and a double singularity at the corner 0 = (0, 0). We write S • := S \ {0} for the punctured quadrant.

We will note ẋ(t) the derivative dx(t)/dt. So the integral system (1) may be written as an initial-value problem ẋ

= α x + β y ẏ = γ x + δ y (3)
with the inital condition (x(0), y(0)) ∈ S.

We first remark that if β < 0, γ < 0 and αδ < βγ, there exist λ > 0 and µ > 0 such that λα + µγ < 0 and λβ + µδ < 0. Thus z(t) := λx(t) + µy(t) is decreasing, min (x(t), y(t)) → 0 and ż(t) → -∞ as t → t f where t f < ∞ and there is no solution. If β < 0, γ < 0 and αδ = βγ, then v(t) := αy(t) -γx(t) remains equal to αy -γx and there is a unique solution (x(t), y(t)) that converges to ( γx-αy β+γ , βy-δx β+γ ) except if (x, y) = 0 in which case there is no solution.

From now on we will make the following hypothesis:

(H) max (β, γ) ≥ 0 or βγ < αδ.

This is equivalent to the existence of λ ≥ 0 and µ ≥ 0 such that λα+ µγ > 0 and λβ + µδ > 0. This last formulation amounts to saying that the matrix

A = α β γ δ
is an S-matrix in the terminology of [START_REF] Fiedler | Some generalizations of positive definiteness and monotonicity[END_REF]. In the sequel, we fix a pair (λ, µ) with λ > 0, µ > 0, such that λα + µγ > 0 and λβ + µδ > 0.

The aim of this note is to prove the following result.

Theorem 1 Under condition (H), there exists a unique solution to (1) for any starting point (x, y) ∈ S.

2 Some preliminary lemmata.

We begin with a comparison lemma.

Lemma 2 Let x 1 and x 2 be nonnegative continuous functions on [0, ∞) which are solutions to the system

x 1 (t) = v 1 (t) + α t 0 ds x 1 (s) x 2 (t) = v 2 (t) + α t 0 ds x 2 (s)
where α > 0, v 1 and v 2 are continuous functions such that 0

≤ v 1 (0) ≤ v 2 (0), and v 2 -v 1 is nondecreasing. Then x 1 ≤ x 2 on [0, ∞).
Proof. Assume there exists t > 0 such that x 1 (t) > x 2 (t). Set

τ := max {s ≤ t : x 1 (s) ≤ x 2 (s)}. Then x 2 (t) -x 1 (t) = x 2 (τ ) -x 1 (τ ) + (v 2 (t) -v 1 (t)) -(v 2 (τ ) -v 1 (τ )) + α t τ ( 1 x 2 (s) -1 x 1 (s) )ds ≥ 0, a contradiction. Lemma 3 Let the system ẋ = α x + φ(x, z) ż = ψ(x, z) (4)
with x(0) = x 0 ≥ 0, z(0) = z 0 ∈ R, α > 0, φ and ψ two Lipschitz functions on R + × R, and |φ| ≤ c for some c < ∞. Then there exists a unique solution to (4). Moreover, for this solution, x(t) > 0 for any t > 0.

Proof. Assume first x 0 > 0. Then the system (4) is Lipschitz on [min {x 0 , α c }, ∞) × R and the solution does not step out of this domain, so there is a unique global solution. When x 0 = 0, we let w 0 (t) = 0, z 0 (t) = z 0 and for n ≥ 1

w n (t) = 2αt + 2 t 0 w n-1 (s) φ( w n-1 (s), z n-1 (s))ds z n (t) = z 0 + t 0 ψ( w n-1 (s), z n-1 (s))ds. Let M > 0 and assume |w n-1 (t)| ≤ M on some interval [0, T ]. Then, for 0 ≤ t ≤ T , |w n (t)| ≤ T (2α + 2c √ M )
and this is again ≤ M for T small enough. We also have |z n (t)| ≤ M ′ for any n ≥ 0 for T small enough. Equicontinuity of (w n , z n ) n≥0 is easily verified and from the Arzela-Ascoli theorem it follows there exists a subsequence (w

n k , z n k ) converging on [0, T ] to a solution (w, z) of the system ẇ = 2α + 2 √ w φ( √ w, z) ż = ψ( √ w, z) (5)
with the initial conditions w(0

) = 0, z(0) = z 0 . For small T , ẇ > 0 on [0, T ]. Set now x(t) = w(t). Then (x, z) is a solution to (4) on [0, T ] with x(T ) > 0.
We may extend the solution to [0, ∞) by using the above result with x 0 > 0.

We now prove uniqueness. Let (x, z) and (x ′ , z ′ ) be two solutions of (4). Then

(x(t) -x ′ (t)) 2 + (z(t) -z ′ (t)) 2 = 2α t 0 (x(s) -x ′ (s))( 1 x(s) -1 x ′ (s) )ds + 2 t 0 (x(s) -x ′ (s))(φ(x(s), z(s)) -φ(x ′ (s), z ′ (s)))ds +2 t 0 (z(s) -z ′ (s))(ψ(x(s), z(s)) -ψ(x ′ (s), z ′ (s)))ds ≤ 4L t 0 ((x(s) -x ′ (s)) 2 + (z(s) -z ′ (s)) 2 )ds
where L is the Lipschitz constant of φ and ψ. Uniqueness follows from Gronwall's inequality.

Lemma 4 Let u(.) = (x(.), y(.)) be a solution to [START_REF] Fiedler | Some generalizations of positive definiteness and monotonicity[END_REF] and let ν = (λ, µ). Then the function z(t) := ν.u(t) = λx(t) + µy(t) is increasing on [0, ∞) and we have u(t) ∈ S • for any t > 0.

Proof. Recall that condition (H) is in force. We easily check that ż(t) is positive.

3 Existence. Case x = 0, y = 0.

There is an explicit solution to (1) when the starting point is the corner.

Proposition 5 There is a solution to (1) with initial condition 0 given by

x(t) = c √ t y(t) = d √ t (6)
where c = (2α + β δ (β -γ + (β -γ) 2 + 4αδ)) 1/2 d = (2δ + γ α (γ -β + (β -γ) 2 + 4αδ)) 1/2 . ( 7
)
Proof. Writing down x(t) = c √ t and y(t) = d √ t we have to solve the system

c 2 = α c + β d d 2 = γ c + δ d ;
We first compute

d c = γ -β + (β -γ) 2 + 4αδ 2α (8)
and then obtain (7) provided that

C = 2α + β δ (β -γ + (β -γ) 2 + 4αδ) D = 2δ + γ α (γ -β + (β -γ) 2 + 4αδ)
are positive. If β ≥ 0, C is clearly positive. This is also true if β < 0 and βγ < αδ since C may be written

C = 4α(αδ -βγ) 2αδ -βγ + β 2 -β 4(αδ -βγ) + (β + γ) 2 .
The proof for D is similar. Uniqueness in this case is more involved and will be treated in the last section. We only remark for the moment that the system (3) with α = δ = 0, β > 0, γ > 0 and initial value 0 has a one-parameter family of solutions.

Angular behavior.

We are now in a position to study the behavior of y(t)

x(t) . For any u = (x, y) ∈ S • we set

θ(u) = arctan y x .
We also set

u * = (x * , y * ) := c λc + µd , d λc + µd .
Proposition 6 Let u(.) be a solution to (1) starting at u = (x, y) ∈ S • . Then for any t > 0 1.

dθ(u(t)) dt

> 0 and θ(u(t)

) < θ(u * ) if θ(u) < θ(u * ) dθ(u(t)) dt = 0 and θ(u(t)) = θ(u * ) if θ(u) = θ(u * ) dθ(u(t)) dt < 0 and θ(u(t)) > θ(u * ) if θ(u) > θ(u * ).

2.

x(t) ≥ min x, c λx+µy λc+µd y(t) ≥ min y, d λx+µy λc+µd .

Proof. From Lemma 4 we know that u(t) ∈ S • for any t ≥ 0.

1. We compute

dθ(u(t)) dt = 1 x 2 (t) + y 2 (t) d c - y(t) x(t) α + x(t)(β -γ + (β -γ) 2 + 4αδ) 2y(t) (10)
and the conclusion follows.

2. Let a, b ∈ S • with 0 ≤ θ(a) < θ(u * ), θ(u * ) < θ(b) ≤ π 2 and let l > 0. We set

A = {v ∈ S • : θ(a) ≤ θ(v) ≤ θ(u * )} B = {v ∈ S • : θ(b) ≥ θ(v) ≥ θ(u * )}. ( 11
)

Same estimations for y(t).

Corollary 7 Let u(.) be a solution to [START_REF] Fiedler | Some generalizations of positive definiteness and monotonicity[END_REF]. Then

lim t→∞ θ(u(t)) = θ(u * ), i.e. lim t→∞ y(t) x(t) = d c .
Proof. If u = (x, y) ∈ S • , this is an easy consequence of (10). If u = (0, 0) we may apply Lemma 4 and then (10).

5 Existence and uniqueness. Case x > 0, y > 0.

Proposition 8 There exists a unique solution u(.) to (1) starting at u = (x, y) with x > 0, y > 0. It satisfies x(t) > 0, y(t) > 0 for any t ≥ 0.

Proof. We now assume θ(a) > 0 and θ(b) < π 2 in (11). Let l > 0 and ν = (λ, µ). We set L := {v ∈ S • : ν.v ≥ l}. From Lemma 4 and Proposition 6 we know that any solution starting from A ∩ L stays in A ∩ L, and the same is true for B ∩ L. As the system is Lipschitz in A ∩ L and in B ∩ L, there is a unique global solution to (1) in both cases.

6 Existence and uniqueness. Case x = 0, y > 0.

Proposition 9 There exists a unique solution u(.) to (1) starting at u = (x, y) with x = 0, y > 0. It satisfies x(t) > 0, y(t) > 0 for any t > 0.

Proof. Let ε ∈ (0, y µd λc+µd ). We define on R + × R ψ ε (x, z) := 1 max (γx + z, αε) .

We apply Lemma 3 to obtain a unique solution x ε (.), z ε (.) to

x ε (t) = α t 0 ds xε(s) + α m β t 0 ψ ε (x ε (s), z ε (s))ds z ε (t) = αy + α(αδ -βγ) t 0 ψ ε (x ε (s), z ε (s))ds. (12) Let y ε (t) = 1 α (γx ε (t) + z ε (t)) τ y (ε) = inf {t > 0 : y ε (t) < ε}.
On the interval [0, τ y (ε)], (x ε (.), y ε (.)) is the unique solution to [START_REF] Fiedler | Some generalizations of positive definiteness and monotonicity[END_REF]. From (9) we know that y ε (t) > ε on this interval. Thus τ y (ε)) = ∞ and (x(.), y(.)) := (x ε (.), y ε (.)) is the unique global solution to (1).

Path behavior.

Let us note u(t, u 0 ) the solution to (1) starting at u 0 ∈ S • . Using Gronwall's inequality as in the proof of uniqueness, it is easily seen that for any t > 0 the solution u(t, u 0 ) continuously depends on the initial condition u 0 . It has the Scaling Property:

(SC) u(r 2 t, u 0 ) = ru(t, u 0 r )
for any r > 0, t ≥ 0, u 0 ∈ S • . Using Lemma 4 we also note that any solution u(.) to ( 1) has the Semi-group Property:

(SG) u(s + t) = u(t, u(s))
for any s > 0 and t ≥ 0. With Proposition 8 and Proposition 9 this entails that x(t) > 0 and y(t) > 0 for any t > 0. We now set for any r > 0:

L r := {u = (x, y) : x > 0, y > 0, ν.u = r} L r := {u = (x, y) : x ≥ 0, y ≥ 0, ν.u = r}
Lemma 10 Let u(.) be a solution to (1) starting at u 0 ∈ S with ν.u 0 ≤ r. We set τ (r) := inf {t ≥ 0 : ν.u(t) = r}.

Then

τ (r) ≤ r 2 2[λ(λα + µγ) + µ(λβ + µδ)] .
Proof. Set z(t) := ν.u(t).

As

z(t) = ν.u 0 + [λ(λα + µγ) + µ(λβ + µδ)] t 0 ds z(s) + t 0 f (s)ds with f (s) = µ(λα + µγ) y(s) x(s) + λ(λβ + µδ) x(s) y(s) > 0
for s > 0, it follows from Lemma 2 that z(t) ≥ w(t) where

w(t) = ν.u 0 + [λ(λα + µγ) + µ(λβ + µδ)] t 0 ds w(s) ,
and then

z 2 (t) ≥ w 2 (t) = 2[λ(λα + µγ) + µ(λβ + µδ)]t + (ν.u 0 ) 2 .
The conclusion follows. We now define q : L 1 → L 1 by

q(u 1 ) = 1 2 u(τ (2), u 1 )
where

τ (2) = inf {t ≥ 0 : ν.u(t, u 1 ) = 2} (13)
is finite from the above Lemma. Let now r > 0 and u ∈ L r . From (SC), the geometric paths in S of u(., u) and ru(., u r ) are identical. Therefore

u(τ (2r), u) = ru(τ (2), u r )
where in this equality τ (2r) is relative to u(., u) and τ (2) is relative to u(., u r ). Thus

q( u r ) = 1 2r u(τ (2r), u).
Iterating and using (SG), we get for any n ≥ 1

q n ( u r ) = 1 2 n r u(τ (2 n r), u). ( 14
)
Proposition 11 There exists k ∈ (0, 1) such that for any

u 1 ∈ L 1 |q(u 1 ) -u * | ≤ k |u 1 -u * |.
Proof. From Proposition 6 we know that q has a unique invariant point u * . We consider the solution u(t, u 1 ) = (x(t), y(t)) on the time interval [0, τ (2)], where τ (2) was defined in (13).

We first assume that

y 1 x 1 < y * x * = d c .
We note for further use that

x * < x 1 ≤ 1 λ 0 ≤ y 1 < y * < 1 µ .
We set

u 2 = (x 2 , y 2 ) := u 1 + (αy 1 + βx 1 , γy 1 + δx 1 ) λ(αy 1 + βx 1 ) + µ(γy 1 + δx 1 )
.

Then, 2u * , u * + u 1 and u 2 ∈ L 2 . Setting for z ∈ [0, ∞] h(z) = γz + δ αz + β we compute dh dz (z) = βγ -αδ (αz + β) 2 . ( 15
)
From Proposition 6 we know that for any t ∈ [0, τ (2)]

y(t) x(t) < d c . (16)
When αδ > βγ, it follows from (15) and ( 16) that

ẏ(t) ẋ(t) = h( y(t) x(t) ) > h( d c ) = d c
and then 2q(u 1 ) belongs to the open interval (2u * , u * + u 1 ) on L 2 . Therefore,

|2q(u 1 ) -2u * | < |u 1 -u * |.
When αδ = βγ, the path of the solution is a straight half-line with slope d c and

|2q(u 1 ) -2u * | = |u 1 -u * |.
When αδ < βγ, ẏ(t) ẋ(t) is increasing on [0, τ (2)] and then

γy 1 + δx 1 αy 1 + βx 1 ≤ ẏ(t) ẋ(t) < d c .
As a result, 2q(u 1 ) belongs to the open interval (u * + u 1 , u 2 ) on L 2 . Moreover, using the relation λx 1 + µy 1 = 1 twice, we get

2x 1 -x(τ (2)) > 2x 1 -x 2 = x 1 - αy 1 +βx 1 λ(αy 1 +βx 1 )+µ(γy 1 +δx 1 ) = αλx 1 y 1 +βλx 2 1 +γµx 1 y 1 +δµx 2 1 -αy 1 -βx 1 λ(αy 1 +βx 1 )+µ(γy 1 +δx 1 ) = µ -αy 2 1 +(γ-β)x 1 y 1 +δx 2 1 λ(αy 1 +βx 1 )+µ(γy 1 +δx 1 ) = αµ λ(αy 1 +βx 1 )+µ(γy 1 +δx 1 ) (x 1 d c -y 1 ) y 1 + β-γ+ √ (β-γ) 2 +4αδ 2α x 1 = α(λc+µd) c[λ(αy 1 +βx 1 )+µ(γy 1 +δx 1 )] (x 1 -x * ) y 1 + β-γ+ √ (β-γ) 2 +4αδ 2α
x 1 .

In the same way,

y(τ (2)) -2y 1 > y 2 -2y 1 = α(λc+µd) c[λ(αy 1 +βx 1 )+µ(γy 1 +δx 1 )] (y * -y 1 ) y 1 + β-γ+ √ (β-γ) 2 +4αδ 2α x 1 .
Setting 8 Uniqueness. Case x = 0, y = 0.

k 1 = λµ(β-γ+ √ (β-γ) 2 +4αδ) 4[λ(λα+µγ)+µ(λβ+µδ)] > 0 we obtain |2q(u 1 ) -2u 1 | > 2k 1 |u 1 -u * | and
Existence was proven in Section 3. We may now conclude the proof of Theorem 1.

Proposition 12 The solution given by ( 6) is the unique solution to (1) starting at 0.

Proof. Let u(.) be a solution to (1) starting at 0. For any n ≥ 1 and s > 0, u(τ (s)) = u(τ (s), u(τ (s2 -n )))

where τ (s) in the l.h.s. is relative to u(.) and τ (s) in the r.h.s. is relative to u(., u(τ (s2 -n ))).

We may apply (14) with r = s2 -n and u = u(τ (s2 -n )). We obtain

u(τ (s)) s = q n ( u(τ (s2 -n )) s2 -n ).
From Proposition 11 (or directly from (10) it follows that the r.h.s. converges to u * as n → ∞. Thus for any s > 0 u(τ (s)) s = u * and this implies y(τ (s))

x(τ (s)) = d c .

From Lemma 10 we know that τ is one-to-one from [0, ∞) to [0, ∞) , and thus for any t > 0,

y(t) x(t) = d c .
Going back to the system (1) we conclude that

x(t) = c √ t y(t) = d √ t.

  x(.) and y(.) are continuous functions from [0, ∞) to [0, ∞) with the conditions t 0 1 I {x(s)=0} ds = 0 t 0 1 I {y(s)=0} ds = 0 t 0 1 I {x(s)>0} ds x(s) < ∞ t 0 1 I {y(s)>0} ds y(s) < ∞

then |q(u 1 )

 1 u * | = |u 1u * | -|q(u 1 )u 1 | < (1 -k 1 ) |u 1u * |. If now y 1 x 1 > d c, in the same way there exists k 2 > 0 such that|q(u 1 )u * | < (1 -k 2 ) |u 1u * |We may take k = 1 -min(k 1 , k 2 )

  It follows from above that any solution starting from A stays in A, and the same is true for B. If u ∈ A,

		x(t) ≥ -	µ λ	y(t) + (x +	µ λ	y) ≥ -	µd λc	x(t) + x +	µ λ	y
	and therefore					x(t) ≥ c	λx + µy λc + µd	.
	If u ∈ B,	x(t) ≥	x y	y(t) ≥	x y	(-	λ µ	x(t) +	λx + µy µ	)
	and therefore
						x(t) ≥ x.


Nam Hoang
email: hoangnam.ho@univ-lr.fr

Christophe Ho

Jean-Christophe Rigaud
email: christophe.rigaud@univ-lr.fr

Jean-Marc Burie
email: jean-marc.ogier@univ-lr.fr

Ogier

Redundant structure detection in attributed adjacency graphs for character detection in comics books

Keywords: Comics, character detection, attributed adjacency graph, graph comparison, graph matching, spatial relation

Graphs are popular data structures used to model pair wise relations between elements from a given collection. In image processing, adjacency graphs are often used to represent the relations between segmented regions. Such graphs can be compared but graph matching strategies are essential to find similar patterns. In this paper, we propose to detect the recurrent characters of a comics book. In this method each panel is represented with an attributed adjacency graph. Then, an inexact graph matching strategy is applied to find redundant structures among this set of graphs. The main idea is that the same character will be represented by similar subgraphs in the different panels where it appears. The two-step matching process consists in a node matching step and an edge validation step. Experiments show that our approach is able to detect redundant structures in the graph and consequently the recurrent characters in a comics book. The originality of our approach is that no model is required, the algorithm detects all by itself all redundant structures.

I. INTRODUCTION

Nowadays, with the development of information technology and communication, the digital information is becoming increasingly popular. It is a great challenge for computer science to develop applications to help the user to process this information. Born in the 19th century, comics spread worldwide and became an important industry. Although hundreds of thousands comics albums have been digitized around the world, few researches have been carried out in order to exploit the content of digitized comics. Some works have been done to analyze the layout of Japanese mangas [START_REF] Tanaka | Layout analysis of tree-structured scene frames in comic images[END_REF], to extract panels [START_REF] Chan | Automatic panel extraction of color comic images[END_REF], [START_REF] Ishii | A study on frame position detection of digitized comics images[END_REF], [START_REF] Ho | Panel and speech balloon extraction from comic books[END_REF], [START_REF] Rigaud | Automatic text localisation in scanned comic books[END_REF], to localize speech balloons [START_REF] Arai | Automatic e-comic content adaptation[END_REF], [START_REF] Ho | Panel and speech balloon extraction from comic books[END_REF] or to detect text [START_REF] Arai | Automatic e-comic content adaptation[END_REF], [START_REF] Rigaud | Automatic text localisation in scanned comic books[END_REF]. In [START_REF] Sun | Similar manga retrieval using visual vocabulary based on regions of interest[END_REF], authors are able to detect faces, in Japanese mangas, as regions of interests to detect illegal copies. But, at present, a big challenge consists in developing methods to extract characters and to analyze the scenery which can be make up different objects or background according to the situation. To our knowledge, no research has been done to analyze the graphical content of color comic books.

If we consider the characters illustrated in the panels of a comic books, their representation change because the artist usually draw the characters with different size or from different point of views, with various face expressions or in diverse positions. Usual pattern recognition methods would try to match a candidate area with a given model of a character. But the main problem to solve would be to define a model of this character since there are almost as many models as character representations.

The first question is how to represent a character ? Each character corresponds to a set of regions with different colors which represent clothes, head, skin, eyes and hair and so on... More generally, each panel is a set of color regions which represent the parts of the characters, but also the ones of the background. Graphs are popular data structures used to model pair wise relations between elements from a given collection. In document analysis, or more generally, in image processing, adjacency graphs are often used to represent the relations between segmented regions. Such graphs can be compared but graph matching strategies are essential to find similar patterns.

We propose to represent each panel with an attributed adjacency graph and to extract redundant structures. The main idea is that the same character will be represented by similar subgraphs in the different panels where it appears. Thus, an inexact graph matching strategy has been developed to find these redundant structures among this set of graphs.

The paper is organized as follow. The second section gives an overview of comparison methods between graphs. The method used to represents comic panels with graphs is detailed in section III. Section IV describes the inexact graph matching approach. The experimentations and results are given in section V. Finally, conclusion and future works end this paper.

II. OVERVIEW OF GRAPH COMPARISON METHODS

A graph G = (V, E) is a set of vertex (nodes) V connected by edges (links) E. In model-based pattern recognition problems, two graphs are given, the model graph G M and the data graph G D . The procedure for comparing them involves checking whether they are similar or not. Generally speaking, we can state the graph matching problem as follows: given two graphs

G M = (V M , E M ) and G D = (V D , E D ), with|V M | = |V D |, the problem is to find a one-to-one mapping f : V D → V M such that (u, v) ∈ E D if f (f (u), f (v)) ∈ E M .
When a mapping f exists, this is called an isomorphism, and G D is said to be isomorphic to G M . This type of problem is known as exact graph matching. On the other hand, the term "inexact" applied to graph matching problems means that it is not possible to find an isomorphism between the two graphs. This is the case when the number of nodes is different in both the model and data graphs. Therefore, in these cases no isomorphism can be expected between both graphs, and the graph matching problem does not consist in searching for the exact way of matching nodes of a graph with nodes of the other, but in finding the best matching between them. This leads to a class of problems known as inexact graph matching. In that case, the matching aims at finding a nonbijective correspondence between a data graph and a model graph [START_REF] Bunke | Error-Tolerant Graph Matching: A Formal Framework and Algorithms[END_REF], [START_REF] Messmer | A New Algorithm for Error-Tolerant Subgraph Isomorphism Detection[END_REF]. If one of the graphs involved in the matching is larger than the other, in terms of the number of nodes, then the matching is performed by a subgraph isomorphism. A subgraph isomorphism from G M to G D means finding a subgraph s g of G D such that G M and s g are isomorphic.

Two drawbacks can be stated for the use of graph matching. First, the computational complexity is an inherent difficulty of the graph-matching problem. A research effort has been made to develop computationally tractable graph-matching algorithms [START_REF] Shapiro | Structural descriptions and inexact matching[END_REF]. The second drawback is dealing with noise and distortion. The encoding of an object of an image may not be perfect due to noise and errors introduced in low-level stages. In such situations, the graph representation of identical objects may not exactly match. To overcome this shortcoming, some methods propose to define a distance between graphs. The edit distance is often used to measure the distance between graphs [START_REF] Tsai | Error-Correcting Isomorphisms of Attributed Relational Graphs for Pattern Analysis[END_REF]. The edit distance is a dissimilarity measure that represents the minimum-cost sequence of basic editing operations to transform a graph into another graph by means of insertion, deletion and substitution of nodes or edges. The flexibility of the edit distance allows to use this approach on a large diversity of graphs with no constraint on the labels or the topology. Anyway, its application is limited to small graphs.

Another approach, to overcome computational time and dimensionality problems, consists in embedding graph in vector spaces. Different graph embedding procedures have been proposed. Some of them are based on the spectral graph theory, others take advantage of typical similarity measures to perform the embedding tasks [START_REF] Bunke | Recent advances in graph-based pattern recognition with applications in document analysis[END_REF]. The main advantage of this approach is that the comparison of graphs becomes a comparison of vectors, euclidian distance can be used and computational time depends on the vector size. Moreover all classification methods based on vectors are available to the graph domain. However, graph embedding lacks the capabilities to address the problem of graph matching. This is because of the strict limitation of the resulting feature vector which is not capable of preserving the matching between nodes of graphs.

In our work, we have considered the search of redundant structures as an inexact graph matching problem. The approach will be detailed in section IV.

III. GRAPH REPRESENTATION OF COMICS

We introduce in this section an approach to represent a comics panel by a graph. First, we extract the color regions and their features, second the graph is constructed in three steps: node labeling, edge construction and edge labeling.

A. Pre-processing

The first step consists in extracting panels from a comics page with the method proposed in [START_REF] Rigaud | Automatic text localisation in scanned comic books[END_REF]. Each panel is then processed separately as shown in figure 1. To obtain regions, any color segmentation method can be used in this stage. However to avoid over-segmentation, a color reduction of 16 Fig. 1. Process from comics page to panels most significant colors is applied to the page. In order to limit noise and distortion in the graph, three filtering steps are applied to remove:

• The text inside the balloons with the method given in [START_REF]Graphics Recognition. New Trends and Challenges, ser[END_REF] • The small regions to limit the number of regions and consequently the size the graph.

• The black lines surrounding the color regions.

The black lines are a feature of most color comics but are not interesting in our approach since they create no significant region and break the adjacency relationship between meaningful color regions. Since a black line surrounds all the regions of the panel, it produces the biggest connected component in the panel. This component can easily be ignored in the rest of process.

After this pre-processing stage, a set of regions is obtained. Each region is characterized by the following features: color, surface area, compactness, shape and its adjacent regions.

B. Node labeling

In our approach, the regions are represented as the nodes of the graph. Each node is described by the following attributes:

• Color. The color is defined in CIE L*a*b* color space [14]. L*a*b* is a uniform color space based on the human perceptual system. It has been specially designed so that the calculated euclidian distances between colors correspond to the differences perceived by the human eye. The region color is represented by a vector of three dimensions where each element corresponds respectively to L (luminance), a and b (chromatic components).

• Compactness. This value is calculated in the segmentation step.

• Shape. The shape of the regions is characterized by Hu moments [START_REF] Hu | Visual pattern recognition by moment invariants, ire trans[END_REF] which are invariant under translation, changes in scale, and also rotation. These properties are essential in our case because the characters can be drawn with different size or orientation. This attribute is defined by a vector with the 7 values of Hu moments.

Finally, by combining these attributes, each region is characterized by an 11-dimensional vector. Since the magnitude of each component of this vector can be very different, a normalization process is applied to give the same weight to each component and to be able to compare vectors objectively. Let X i be the value of one component, X i the average value and Γ the standard deviation. The normalization is performed as follows: (X i -X i )/Γ. This normalized vector will be used to compare the regions.

C. Edge construction

The edges of the graph are constructed according to spatial relationships between regions. If two regions are adjacent then their nodes will be linked by an edge otherwise no link will be created. This strategy allows to take into account the spatial organization of the regions extracted in the comics panel and provides an adjacency graph.

D. Edge labeling

The last step consists in giving labels to the edges in order to quantify the relationship between two regions. This measure should be invariant to rotation and scaling change to take into account that a character can be drawn with different size and position. We propose to use the surface area ratio between adjacent regions. Indeed, we assume that the proportions between regions will be preserved, either the character is viewed from near or far. Let S R1 and S R2 be respectively the area of regions R1 and R2. Since the ratio S R1 /S R2 is the reciprocal number of the ratio S R2 /S R1 , an orientation is given to the edge indicating how the ratio has been computed. So, an edge is oriented from the node corresponding to the region R1 toward the node corresponding to the region R2 if the label given to the edge is S R1 /S R2 and reciprocally from R2 toward R1 if the label is S R2 /S R1 .

Finally, each panel is transformed into an attributed adjacency graph where nodes, labeled with an 11-dimensional vector, correspond to the regions and the oriented edges quantify the relationships between adjacency regions in terms of surface ratio.

IV. INEXACT GRAPH MATCHING APPROACH

In this section, the approach to compare two graphs is presented. First, the algorithm description is discussed and then the algorithm is detailed.

A. Algorithm description

Panels are transformed into graphs with the method presented above. In order to find redundant structures in the comics book, a specific method is necessary to compare graphs and to extract similar subgraphs. Let G 1 and G 2 be two graphs to compare. This algorithm consists of two steps :

• The first one concerns the node matching. The distance between each node of G 1 and each node of G 2 , characterized respectively by an 11-dimensional vector, is computed. The lowest distances are selected to provide a list of matched nodes.

• The goal of the second step is to verify, for each pair of matched nodes, the compatibility of the edges that connect them, in order to extract the common subgraphs. 1) Node matching: to match the regions of 2 panels represented respectively by two graphs G 1 and G 2 , we define a matrix P of size n 1 × n 2 where n 1 and n 2 are respectively the node number in G 1 and G 2 . Each element p ij in P corresponds to the euclidian distance between node i in G 1 and node j in G 2 with i ∈ {1, ..., n 1 } and j ∈ {1, ..., n 2 }.

In each row i of P , we select the element j with the minimal value. The indices i and j of the selected element match the node i in G 1 with the node j in G 2 . However, to avoid wrong matching, this minimal value has to be lower than a threshold λ, defined experimentally here. Consequently, a node i in G 1 may not have corresponding node in G 2 .

When all the rows of P have been processed, this first step provides a set of pairs of matched nodes between the graphs G 1 and G 2 . Let (N k G1 , N k G2 ) be a pair of matched node between G 1 and G 2 with k ∈ {1, ..., l} and where l is the number of matched nodes. An example of pairs of matched nodes is given in table I. The result shows that the region (node) 1 of the panel (graph) G 1 is similar to region (node) A of the panel (graph) G 2 .

2) Edge compatibility: The node matching is not enough, the relationships between regions, represented by the edges, have also to be compatible in order to extract similar subgraph. Let (N i G1 , N i G2 ) and (N j G1 , N j G2 ) be two pairs of matched node with i, j ∈ {1, ..., l}: If N i G1 is connected with N j G1 and N i G2 with N j G2 , the edge labels are compared. As mentioned above, the edge label is the ratio between the surface areas of adjacent regions. If the two edges have the same orientation, the labels can be compared as they are. Otherwise, the reciprocal number of one of the label has to be computed before comparing them. The compatibility of the edges and therefore the similarity is established if the distance between the 2 labels is lower than a threshold ω. This threshold is chosen to be quite tolerant since variations of the ratio of 20% are accepted to consider that the edges are compatible.

B. Algorithm and Complexity 1) Algorithm:

We present here the algorithm used for graph matching. Input : two attributed adjacency graphs G 1 and G 2 Output : the common subgraph to G 1 and G 2 Pre-condition : the node number n 1 of G 1 is lower than the one n 2 of G 2

Initialize P as follows p ij = d(N G1 , N G2 ) : Euclidian distance between two nodes N G1 and N G2 . Node matching between G 1 and G 2 for all i = 0 to n 1 -1 do for all j = 0 to n 2 -1 do if p ij < λ then Keep the lowest value p ij Save i and j, it means that the node i is similar to the node j else Do nothing (there is no matching between the node j and the node i) end if end for end for Research the similar elements (nodes and edges) between G 1 and G 2 Set l as the matching number founded in below for all i = 0 to l -1 do for all j = i + 1 to l -1 do Set a as edge between the node i and node j of G 1 Set b as edge between the node i and node j of

C. Redundancy

The approach detailed above allows to compare two graphs (panels) in order to extract common subgraphs (similar objects). But, our purpose is to extract redundant objects drawn in the comics. So, how to define the redundancy of an object? The strategy consists in comparing panels (or rather their graphs) two by two and in counting the number of times a given subgraph is detected. Let f be the frequency of apparition of an object in the panels and N p the total number of panels. An object (or subgraphs) is called redundant if it verifies the following expression: f ≥ n/2. In this approach no model is given, the algorithm finds by itself the redundant subgraphs and consequently the characters in our case.

V. EXPERIMENTATIONS AND RESULTS

Two experimentations have been carried out to evaluate the performance of the proposed approach. The first one searches the same characters in two panels. The second one consists of the analysis of a whole comics album to extract the redundant characters. For each experimentation, the panels are first extracted and transformed into graphs with the method described in section III. Note that the text of speech balloons has been removed [START_REF] Rigaud | Automatic text localisation in scanned comic books[END_REF] to avoid the introduction of noise in the process. The two thresholds used in this method are set to λ = 10 and ω = 0.2.

A. Comparison of two panels

The aim of the first experimentation is to test the ability of the algorithm to detect the similarity between two panels. A data set with 200 panels extracted from a comics album has been created. Then, the 200 panels have been transformed in 200 distinct graphs. From these 200 graphs, 100 pairs of graphs have been selected. 76 pairs contain similar elements, 24 pairs have no similar elements. In this study, the time required to execute the comparison is also considered. Figure 2 shows an example where the algorithm detects similar objects (here a character) in two panels. To visualize the results a bounding box has been drawn around the similar subgraph found in the panels.

In some cases, only partial detections of the characters are carried out. An example is shown on figure 3. The algorithm detects similarities between the parts corresponding to the hair and the upper body, but no similarity is found for the face. This result can be explained because the facial features (mouth, eyes) are different. This creates an ambiguity in the detection. If we consider the character detection process, the algorithm failed. However it succeeded to find redundant structures. This example shows the capabilities of our approach to extract similar parts of the panels, but the method needs to be improved to take into account the fact that characters can show bigger variations.

To evaluate the detection results we consider that a pair is valid if a character has been correctly found in the two panels. Table II shows a confusion matrix, which is the result of the comparison of 100 pairs of the graphs. 54 pairs have been well detected. Among the 22 pairs detected as non valid, 7 correspond to partial detections of the characters. 5 non valid pairs have been detected as valid because similar regions, in terms of shape and color, are drawn in the panels. As the algorithm considers that redundant structures are characters, they have been evaluated as valid. In terms of rappel and precision, we obtain respectively a rate of 71.05% and 91.5%.

The computation time to process a pair of graphs is

B. Redundant character detection

The second experiment was carried out with a set of 42 pages of comics. All pages contain at least one redundant character. Each page consists of 4 panels. To limit computation time, the purpose of this test is to verify if the algorithm is able to detect redundancies in each comic page and not in the whole album. Redundancy (see section IV-C) is defined by the frequency of occurrence of an object. For a page of 4 panels as shown in figure 4, a redundant character is a character that appears at least two times. To evaluate algorithm performance, the detection is considered as valid if this redundancy condition is true. Table III presents the results. At least one redundant character has been detected in 71.4% of the pages. Partial detections have been detected in 9.6% of the 42 pages. Non valid pages correspond to pages where the redundancy criterion is not verified. The characters have been detected but only one times.

The average computation time for one comic page with 4 panels is about 4 seconds. The results of this experimentation are encouraging for the detection of redundant objects but improvements are necessary to solve the problem of partial detections.

VI. CONCLUSION AND FUTURE WORKS

In this paper, we have presented an approach to detect redundant structures in comic books. Each panel is transformed in an attributed adjacency graph where the nodes represent the regions and the edges the relationships between adjacency regions. A specific inexact graph matching has been developed to extract similar subgraphs. This approach has been used to detect redundant characters drawn in a comic but it could be used to detect any redundant objects. The originality of this approach is that the definition of a model is not required. The algorithm detects by itself all the redundant structures. Future works will concentrate on the problem of partial detections to improve the rate of recognition of characters. We will also study the possibility to extract other objects or scenery elements for comics book indexation.

G 2

 2 Call Verification (a, b) end for end for Verification (a,b) Verify if a and b are in the same direction, and calculate D e dge, the distance between a and b if D e dge < ω then keep the nodes and the edges, they correspond to a common subgraph between G 1 and G 2 end if 2) Complexity: The complexity of the algorithm is O(n 1 × n 2 × l) where n 1 is the number of nodes of G 1 , n 2 is the number of nodes of G 2 and l is the number of matching nodes.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Detection of similar objects (Image credit: Cosmozone [16])

Fig. 4 .

 4 Fig. 4. Redundant character detection (Image credit: Cosmozone [16])

TABLE I

 I

		.	NODE MATCHING FOR TWO GRAPHS
	G1	Node 1	Node 2	Node 3	Node i
	G2	Node A	Node B	Node C	Node j

TABLE II

 II

	.	RESULTS OF COMPARISON OF TWO GRAPHS
				Estimated class
				Valid	Non valid
	Real class	Valid	54	22
			Non valid	5	19

TABLE III .

 III RESULTS OF COMPARISON FOR A PAGE OF COMICS

	Valid page	Non valid page	Page with partial detection
	71.4%	19%	9.6%

ACKNOWLEDGMENT

This work is supported by the region Poitou-Charentes, the General Council of Charente Maritime, the town of La Rochelle and the European Regional Development Fund.