Katrina Vanura

Florentin Späth

Andreas Gleiss

Edit Porpaczy Trang Le

Cathrin Skrabs

Alexander Hauswirth

Karin Fleiss

Florian Wessely

Alexander Gaiger

Karin Fleiß

Leonhard Müllauer

Ulrich Jäger
email: ulrich.jaeger@meduniwien.ac.at

Prevalence and clinical impact of autoimmune diseases and chronic infections in malignant lymphomas at diagnosis

Keywords: lymphoma, autoimmune diseases, chronic infections, prevalence, therapy

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Malignant lymphomas are neoplasms of the lymphoid system characterized by a wide range of biological, pathological, and epidemiological features thus showing heterogeneous clinical presentation and behavior [START_REF] Swerdlow | WHO classification of Tumours of Haematopoietic and Lymphoid Tissues[END_REF]. Two major groups of malignancies can be distinguished, Hodgkin´s lymphoma (HL) and non-Hodgkin´s lymphomas (NHL). Incidences are 3/100.000 for HL and 10/100.000 for NHL per year in Western Countries, respectively, both subgroups have a male predominance (1.5-2:1) [START_REF] Boyle | In Word Cancer Report[END_REF], and the number of incidences is increasing [START_REF] Müller | Epidemiology of non-Hodgkin's lymphoma (NHL): trends, geographic distribution, and etiology[END_REF]. The etiology of lymphomas is largely unknown. However, development may be accompanied by altered immunological functions, either chronic antigenic stimulation (CS) (chronic infections (CI), autoimmune disease (AI)) or immunosuppression (immunodeficiencies, transplant patients) [START_REF] Müller | Epidemiology of non-Hodgkin's lymphoma (NHL): trends, geographic distribution, and etiology[END_REF][START_REF] Hansen | B-cell lymphoproliferation in chronic inflammatory rheumatic diseases[END_REF]. In particular, autoimmune diseases have repeatedly been shown to confer an increased risk for certain hematologic malignancies [START_REF] Smedby | Autoimmune and inflammatory disorders and risk of malignant lymphomas -an update[END_REF][START_REF] Anderson | Population-based study of autoimmune conditions and the risk of specific lymphoid malignancies[END_REF]. Linking infectious agents with neoplasia, however, is a more difficult task. To demonstrate a causal relationship between a microorganism and the development of a disease, certain criteria have to be fulfilled [START_REF] Hill | The enviroment and disease: association or causation?[END_REF][START_REF] Fredericks | Sequence-based identification of microbial pathogens: a reconsideration of Koch's postulates[END_REF].

Thus, Epstein-Barr virus (EBV), human herpes virus 8, human T-lymph tropic virus type I, human immunodeficiency virus, Plasmodium falciparum, hepatitis C virus, hepatitis B virus, Helicobacter pylori, Campylobacter jejuni, Chlamydia psittaci, and Borrelia burgdorferi have been shown to be associated with malignant lymphoma (reviewed by Hjalgrim [START_REF] Hjalgrim | Infectious aetiology of Hodgkin and non-Hodgkin lymphomas: a review of the epidemiological evidence[END_REF]). The common theme in these settings is a state of persistent foreign-or auto-antigenic stimulation initiating inflammatory responses. The accelerated expansion of particular cell populations involves an increased risk for genetic lesions and/or functional errors which may perturb balance and interactions of immune cell compartments. Accumulation of additional transforming events may then trigger malignant progression of lymphoid clones leading to lymphoma or leukemia (see also Fisher & Fisher [10])

Considering the tight association of AI and CI with hematologic malignancies, surprisingly few data are available regarding the prevalence of CS in lymphoma patients. Also, it is still largely unclear how and to which degree CS influences the course of the disease in terms of prognosis and treatment. Therefore, we investigated the occurrence of chronic infectious and autoimmune diseases in patients with malignant lymphoma. These data were correlated with age, sex, type of disease, the international prognostic index for NHL, and overall survival (OS).

MATERIALS AND METHODS

Patients

This is a retrospective, monocentric study performed at the Division of Hematology and Hemostaseology of the Medical University of Vienna. In total, 574 patients with malignant lymphoma were diagnosed at the unit between 2001 and 2005. Of note, this number does not include patients with chronic lymphocytic leukemia (CLL) and MALT lymphoma since results for these entities were published elsewhere [START_REF] Wöhrer | MALT lymphoma in patients with autoimmune diseases: a comparative analysis of characteristics and clinical course[END_REF][START_REF] Vanura | Autoimmune conditions and chronic infections in CLL patients at diagnosis are associated with unmutated IgVH genes[END_REF]. Of 574 patients, 94 were excluded from the analysis because of underlying immunosuppression (HIV positivity, post transplant lymphoproliferative disorder, common variable immunodeficiency) or because they were classified as primary CNS lymphomas. Of the remaining 480 patients, 386 suffered from Non-Hodgkin´s and 94 from Hodgkin´s lymphoma. Due to insufficient survival data, the number of patients was reduced to 297 and 70 for NHL and HL, respectively. Thus, a total of 367 patient records were analyzed for this study.

Patients were considered having chronic conditions only if specific medical records or laboratory data or both were available. Patient data collected included: sex, age, mortality, lymphoma subtype, international prognostic index, and treatment. Lymphomas studied were diffuse large B cell lymphoma (DLBCL), follicular lymphoma (FL), mantle cell lymphoma (MCL), T-cell neoplasms (PTCL -peripheral T-cell lymphoma; T-ALCL -T-cell anaplastic large cell lymphoma, T-LGL -T-cell large granular lymphocytic leukemia), marginal zone lymphoma (MZL; splenic and nodal subtypes), small lymphocytic lymphoma (SLL), lymphoplasmacytic lymphoma (LPL), and unclassifiable B-cell lymphoma with features intermediate between DLBCL and Burkitt lymphoma (ICD-O code 9680/3 [START_REF] Kluin | B-cell lymphomas, unclassifiable, with features intermediate between diffuse large B-cell lymphoma and Burkitt lymphoma[END_REF]). Rare subtypes and unspecified types of lymphomas were combined as "other B cell lymphomas". DLBCL, FL grade 3, high grade unclassifiable B-cell lymphoma, PTCL, and T-ALCL were defined as aggressive, the remaining malignancies as indolent lymphoma subtypes. Chronic infections were defined as chronic or recurrent conditions caused by an infectious agent at least 6 months prior to lymphoma diagnosis and included: chronic colitis (CC), Epstein-Barr virus (EBV), hepatitis C virus (HCV), hepatitis B virus (HBV), Helicobacter pylori (HP) gastritis, lues latens (Treponema infection; LL), and chronic respiratory tract infections (RTI).

Autoimmune diseases included were: systemic lupus erythematosus (SLE), rheumatoid arthritis (RA), Hashimoto's thyroiditis (HT), ulcerative colitis (UC), urticarial vasculitis (UV), idiopathic thrombocytopenic purpura (ITP), Sjögren's syndrome (SS), and atopic dermatitis (AD). Patients received standard chemotherapeutic lymphoma treatment including CD20 antibody therapy or radiation according to guidelines and current clinical practice.

Statistical analysis

Categorical variables were described by absolute and relative frequencies and compared between groups using Chi-Square tests (or Fisher´s Exact tests where necessary). Age was described by median and range due to its skewed distribution and compared between groups using Wilcoxon´s rank-sum test. Overall survival (OS) was calculated from the time of diagnosis either until death or date last seen at the clinic and is represented graphically based on Kaplan-Meier estimates. Median observation time was estimated using the Inverse Kaplan-Meier method [START_REF] Schemper | A note on quantifying follow-up in studies of failure time[END_REF]. In order to quantify the potential effect of various factors on overall survival, a multi-variable Cox proportional-hazards model was used. The independent variables in this model comprise CS vs. non-CS, NHL vs. HL, AI vs. CI, and gender. Furthermore, a variable was nested in the NHL group in order to distinguish aggressive from indolent lymphoma. Since this variable showed a time-dependent effect on overall survival, its interaction with log-time was also nested in the NHL-group. No other interaction of CS vs. non-CS was significant thus the CS-effect is the same for NHL and HL as well as for both sexes.

In order to evaluate the influence of incorporating International Prognostic Index (IPI) classification on the results of survival analysis, a three stage classification variable was

RESULTS

General considerations

In this study, 367 patients with malignant lymphoma were analyzed regarding a history of chronic antigenic stimulation. Of these patients, 70 suffered from HL. Patients with NHL (N=297) had diffuse large B cell lymphoma (N=115), follicular lymphoma (N=65), mantle cell lymphoma (N=21), T-cell neoplasms (N=19), marginal zone lymphoma (N=18), small lymphocytic lymphoma (N=14), lymphoplasmacytic lymphoma (N=9), Burkitt-like lymphoma (N=1), and other lymphomas (N=35). A history of chronic antigenic stimulation was found in 36 patients (9.8%), 16 with AI (4.4%) and 20 with CI (5.4%) (Tables 1A and1B). AI diseases found were SLE (N=4; 1.1%), Hashimoto´s thyroiditis (N=3; 0.8%), RA (N=3; 0.8%), ulcerative colitis (N=2; 0.5%), atopic dermatitis (N=1; 0.3%), ITP (N=1; 0.3%), Sjögren´s syndrome (N=1; 0.3%), and urticarial vasculitis (N=1; 0.3%). CI included respiratory tract infections (N=6; 1.6%), HCV (N=5; 1.4%), HBV (N=3; 0.8%), HP gastritis (N=3; 0.8%), chronic colitis (N=1; 0.3%), EBV (N=1; 0.3%), and lues latens (N=1; 0.3%). One HL patient with RA had concomitant RTI. This patient was classified under AI because, in our opinion, AI outweighs CI. CS diseases as found per lymphoma subtype are listed in Tables 1A and1B. One hundred eighteen patients have died, the median observation period was 74.7 months (quartiles: 62.6 to 89.1 months). No significant difference in overall survival between CS and non-CS patients was observed (HR 0.63, 95% confidence interval 0.26 -1.54; p=0.311). Kaplan-Meier estimates for survival after 48 months were 77.7% in CS vs. 71.8% in non-CS patients (HL: CS 100.0%, non-CS 88.7%; aggressive NHL: CS 66.7%, non-CS 58.6%; indolent NHL: CS 84.6%, non-CS 77.0%; p=0.311). Patient characteristics are listed in Table 2. Median age at diagnosis of lymphoma was 57.0 years for CS patients and 59.7 years for non-CS patients (p=0.775).

Sex-specific differences

We found a slight male predominance in this patient cohort, men constituting 51.7% (N=190) of patients compared to 48.2% women (N=177). Considering CS patients only, however, there was a significant prevalence of women (66.7% or N=24) compared to the non-CS group (45.9% or N=152) (p=0.018) which was due to an overrepresentation of women in the AI group (87.5%; N=14)(p=0.001). In the CI group, no gender bias was found (50% women; N=10;p=0.851). The effect of CS vs. non-CS on OS was the same in both sexes (p=0.249)

NHL -antigenic stimulation

Twelve patients with NHL had a history of AI, 19 showed CI. This corresponds to 4.1% and 6.4% of 297 NHL patients, respectively. Most frequent AI were SLE (N=4; 1.35%) and HT (N=2; 0.67%). Among CI, RTI (N=6; 2.02%) ranked top followed by HCV (N=5; 1.68%), HBV (N=3; 1.01%) and HP (N=3; 1.01%). For a complete list see Table 1A.

Considering NHL subtypes, 58.1% (N=18) of CS patients suffered from an aggressive lymphoma of B-cell type compared to 51.1% (N=133) of patients without antigenic stimulation (p=0.395). Among AI patients only, the prevalence of an aggressive subtype was 75% (N=9 of 12), among CI patients 9 of 19 had aggressive lymphomas (47.4%). DLBCL was slightly more prevalent in the CS group than in the non-CS group (48.4% vs. 37.6%)(p=0.243).

Among CS patients, notably persons suffering from autoimmune diseases showed a high rate of DLBCL (66.7% vs. 37.6% of non-CS patients)(p=0.066).

The effect of CS on OS was not significantly different, being the same in indolent and aggressive lymphomas (HR=0.63, p=0.311) (Fig. 1).

Additional lymphomas found in the CS group were: FL (N=8 or 26 %), MCL (N=4 or 13%), MZL (N=2 or 6%), and other B cell lymphomas (N=2 or 6%). Of note, MCL and MZL cases were associated with CI only. In the case of MZL, the low number may be explained by the fact that MALT lymphomas were not included in this study. Among

NHL -sex-specific differences

As expected, men were predominant in the entire patient cohort (N=154 vs. 143; 51.8% vs.

48.1%

). In patients with CS, however, the sex ratio was skewed in favor of women (N=21 vs. 10; 67.7% vs. 32.3%)(p=0.021). Sex had no significant influence on OS (p=0.072), albeit men had a slightly better OS than women (HR 0.71, 95% confidence intervals 0.50-1.03).

Interestingly, CS men showed the best OS compared to all other groups. Non-CS men, and CS and non-CS women had comparable OS (Fig. 2). However, the effect of CS vs. non-CS on OS was not significantly different for the two sexes, being thus in both genders HR=0.63 (p=0.311).

HL -antigenic stimulation

Five patients out of 70 persons with HL (7.1%) were found to have a history of CS, 4 with AI (5.6%) and 1 with CI (1.4%) (Table 1B). Chronic diseases found were RA (N=2; 2.8%), HT (N=1; 1.4%), and UC (N=1; 1.4%). The single patient with CI had EBV infection (1.4%).

Histological data on LMP1 expression were available for 32/70 patients, 31 were negative, a single patient was LMP1 positive. As in NHL, CS conferred a slight advantage for OS in HL patients (OR 0.63, 95% confidence intervals 0.26-1.54, p=0.311). Median age at diagnosis was 53.1 years for CS patients and 34.5 years for non-CS patients (p=0.454).

HL -sex-specific differences

Sex distribution of the entire cohort were 51.4% men and 48.5% women (N=36 vs. N=34).

The CS group consisted of three women and two men (60% vs. 40%), within the non-CS group, women constituted 48% (N=31), men 52% (N=34).

DISCUSSION

Chronic antigenic stimulation has long been implicated in the development of non-HIV associated hematologic malignancies. Reasons are the observed prevalence and the increased risk of cancer particularly among patients with autoimmune diseases and the association of some infectious agents with certain malignancies.

In this study, we found a prevalence of 9.8% for a history of chronic stimulation in a cohort of 367 malignant lymphoma patients, rates being almost equal for AI and CI. Published estimates of AI prevalence in the general population range between 3 and 10% [START_REF] Dooley | Environmental epidemiology and risk factors for autoimmune disease[END_REF][START_REF] Invernizzi | Female predominance and X chromosome defects in autoimmune diseases[END_REF][START_REF] Cooper | Recent insights in the epidemiology of autoimmune diseases: improved prevalence estimates and understanding of clustering of diseases[END_REF] and was reported to lie between 5 and 8% within the US population [START_REF]Progress in Autoimmune Diseases Research[END_REF]. The prevalence of 4.4%

of AI in our study cohort, thus, is in concordance with these reports for Western countries.

Only for SLE, a higher prevalence was observed compared to the general population (1.1% vs. 0.02%-0.04%) [START_REF] Cooper | Recent insights in the epidemiology of autoimmune diseases: improved prevalence estimates and understanding of clustering of diseases[END_REF][START_REF] Hopkinson | Clinical features and race-specific incidence/prevalence rates of systemic lupus erythematosus in a geographically complete cohort of patients[END_REF]. The prevalence of 4% AI among our NHL patients, however, was lower compared to a study published by Cuttner who found 13% of NHL patients to have a history of AI compared to 5% of controls [START_REF] Cuttner | Autoimmune disease is a risk factor for the development of non-Hodgkin's lymphoma[END_REF]. Of note, Cuttner and colleagues analyzed HL and CLL patients with the control group. Other studies reported 39% AI among MALT lymphoma patients [START_REF] Wöhrer | MALT lymphoma in patients with autoimmune diseases: a comparative analysis of characteristics and clinical course[END_REF], and 16% and 11.8%, respectively, in CLL [START_REF] Vanura | Autoimmune conditions and chronic infections in CLL patients at diagnosis are associated with unmutated IgVH genes[END_REF][START_REF] Barcellini | Relationship between autoimmune phenomena and disease stage and therapy in B-cell chronic lymphocytic leukemia[END_REF]. In all three studies, AI patients with malignant diseases were predominantly women.

According to the Austrian Ministry of Health, the prevalence of HCV in Austria is 0.7% and that of HBV is even lower. In this study cohort, HCV and HBV constituted 1.4% (N=5) and 0.8% (N=3) of patients, respectively, which would indicate a 2-fold overrepresentation compared to the general population. On the other hand, conflicting results have been obtained regarding the frequency of such infections among lymphoma patients from other countries. Some studies found no association of HCV or HBV infections with NHL [START_REF] Pioltelli | Hepatitis C virus in non-Hodgkin´s lymphoma. A reappraisal after a prospective case-control study of 300 patients[END_REF][START_REF] Isikdogan | Hepatitis C virus in patients with non-Hodgin´s lymphoma in southeastern Anatolian region of Turkey: a prospective case-control study of 119 patients[END_REF][START_REF] Morgensztern | Prevalence of hepatitis C infection in patients with non-Hodgin´s lymphoma in south Florida and review of the literature[END_REF],

other studies found a higher prevalence of hepatitis C and B in NHL patients compared to controls [START_REF] Cucuianu | Hepatits B and C virus infection in Romanian non-Hodgkin´s lymphoma patients[END_REF][START_REF] Shirin | Prevalence of hepatitis C virus infection in patients with lymhoproliferative disorders[END_REF][START_REF] Mele | Hepatitis C virus and B-cell non-Hodgkin lymphomas: an Italian multicenter case-control study[END_REF]. This has, in part, been ascribed to different rates of hepatitis infections in the general population of the respective countries. Wang reported a decreased rate of HBV infections in patients with T-cell lymphoma compared to patients with B-cell malignancies [START_REF] Wang | High incidence of hepatitis B virus infection in B-cell subtype non-Hodgkin lymphoma compared with other cancers[END_REF].

In our study, SLL and T-cell lymphoma patients were not found to have a history of chronic stimulation, neither did LPL patients. This probably is due to the low patient numbers for these disease entities and the low prevalence of AI in general.

Considering the entire patient cohort, men were only slightly overrepresented compared to women (52 vs. 48%), and this distribution of sexes did not change when analyzing NHL and HL separately. However, among CS patients women predominated which was due to an overrepresentation of women in the AI group (87.5%). Due to few CS patients, this difference was not statistically significant in HL.

Median age at diagnosis of CS and non-CS patients was not statistically different in any of the groups. While among NHL patients non-CS patients were slightly older, the reverse was observed in HL patients where non-CS patients were much younger than CS patients. HL is known to have a bimodal distribution, one peak at an age of about 30 years and a second peak at 50 years and older [START_REF] Hjalgrim | Infectious aetiology of Hodgkin and non-Hodgkin lymphomas: a review of the epidemiological evidence[END_REF], the most striking difference being that HL in young adults is less likely associated with EBV compared to the older age group [START_REF] Jarrett | Risk factors for Hodgkin's lymphoma by EBV status and significance of detection of EBV genomes in serum of patients with EBV-associated Hodgkin's lymphoma[END_REF]. The results here are in concordance with the reported distribution of HL in developed countries, where etiological agents responsible for HL incidence in the young adult age group remain to be elucidated [START_REF] Jarrett | Risk factors for Hodgkin's lymphoma by EBV status and significance of detection of EBV genomes in serum of patients with EBV-associated Hodgkin's lymphoma[END_REF]. Still, it is notable that only 1 of 70 HL patients had concomitant clinical EBV infection, the other CS patients suffering from autoimmune disorders.

While CS patients were more often found to have an aggressive type of lymphoma, there was no significant difference in overall survival between CS and non-CS patients. The same was observed in indolent and aggressive subtypes and in both sexes. To assess for an association with known prognostic markers, DLBCL and FL patients were risk classified according to the IPI and the data incorporated in the Cox model. Even after stratification, no significant deviations from the original model could be observed indicating a lack of prognostic relevance.

This study has some limitations. Rigid criteria were used with regard to classifying a patient as CS or non-CS. Due to missing laboratory data, the number of CS patients may be underestimated, and serological evidence was not obtained in all patients. Thus, confidence is placed in the diagnosing physician and in the data provided by the patient during the interview. Since chronic infections, particularly RTI, might be due to immunosuppression caused by lymphomagenesis, in some cases it will remain unclear whether CI was preexisting or a result of the developing lymphoma. The prevalence of chronic antigenic stimulation may also be under-or overestimated due to this study not being a case-control study.

The major conclusion of this study is that the presence of chronic antigenic stimulation in general does not decisively influence the clinical outcome of lymphoma patients. This does not preclude that in some cases additional specific anti-inflammatory or anti-infectious treatment may be required.

  used as stratification factor in a Cox model on a reduced data set. For this purpose, patients suffering from DLBCL and FL (N=180; data available for 141 patients) were classified into low, intermediate, and high risk groups (IPI 0-1 = low risk, IPI 2-3 = intermediate risk, IPI 4-5 = high risk) before the model was applied. Due to the low number of CS patients DLBCL and FL were analyzed together (N=23).The reported p-values are the results of two-sided tests. P-values ≤ 0.05 were considered to be statistically significant. All computations have been performed using SAS software Version 9.2 (SAS Institute Inc., Cary, NC,USA, 2008)

  Abbreviations: ADatopic dermatitis; AI -autoimmune disease; CCchronic colitis; CI -chronic infection; FLfollicular lymphoma; DLBCLdiffuse large B cell lymphoma; EBV -Epstein-Barr virus; HCV, HBVhepatitis C / B virus; HL -Hodgkin´s Lymphoma; HT -Hashimoto´s thyroiditis; ITPimmune thrombocytopenia; LLlues latens; LPL -lymphoplasmacytic lymphoma /Morbus Waldenström; MCLmantle cell lymphoma; MZL -marginal zone lymphoma (splenic and nodal types); Nnumber of patients; RArheumatoid arthritis; RTIrespiratory tract infections; SLEsystemic lupus erythematosus; SS -Sjögren´s syndrome; T-cell neoplasms -PTCL (peripheral T-cell lymphoma), T-ALCL (T-cell anaplastic large cell lymphoma), T-LGL (T-cell large granular lymphocytic leukemia); UCulcerative colitis; UVurticarial vasculitis.

Figure 1 :

 1 Figure 1: Overall survival (OS) of NHL patients with indolent or aggressive lymphoma subtype in relation to a history of chronic stimulation (CS) (N=297). The effect of CS on OS was not significantly different in indolent and aggressive lymphomas (p=0.311).

Figure 2 :

 2 Figure 2: Overall survival of NHL patients in relation to sex and chronic stimulation (N=297). (Male vs. female p=0.072; CS vs. non-CS p=0.311 in both men and women).

  SLL, T-cell neoplasms (PTCL, T-ALCL, T-LGL), and LPL, no history of AI or CI was found. Median age at NHL diagnosis was lower in CS patients (60.1 vs. 62.4 years; p=0.203).

	To include prognostic markers in the model, patients with the most frequent histologies,
	DLBCL and FL, were risk stratified based on the international prognostic index. The
	percentage of CS patients in the risk groups were 11.4%, 8.2%, and 15.4% for low,
	intermediate and high risk group, respectively (p=0.711). Incorporating IPI risk stratification in
	the Cox model resulted in a comparable hazard ratio for CS patients of 0.58 (CI 0.18 -1.90;
	p=0.371).

Table 1A : Incidence of chronic inflammatory conditions found in NHL patients in our study cohort (N=297).

 1A

	non-CS patients	Lymphoma	CS patients
	N	%*	subtype	N	%*	CI	N	AI	N
	100	87.0	DLBCL	15	13.0	HBV	2	AD	1
						HCV	1	HT	1
						HP	2	RA	1
						RTI	2	SLE	3
								UC	1
								UV	1
							6.1%		6.9%
	57	87.7	FL	8	12.3	HBV	1	HT	1
						HCV	2	ITP	1
						LL	1	SS	1
						RTI	1
							7.7%		4.6%
	17	81.0	MCL	4	19.0	HCV	1
						HP	1
						RTI	2
							19.0%
	16	88.9	MZL	2	11.1	HCV	1
						RTI	1
							11.1%
	33	94.3	Other lymphomas	2	5.7	CC	1	SLE	1
							2.9%		2.9%
	19	100.0	T-cell neoplasms	-
	14	100.0	SLL	-
	9	100.0	LPL	-
			Unclassifiable B-
	1	100.0	cell lymphoma	-

* refers to the incidence of non-CS patients and CS-patient within lymphoma subtypes, respectively.

Table 1B : Incidence of chronic inflammatory conditions found in HL patients in our study cohort (N=70).

 1B

	non-CS patients	Lymphoma		CS patients
	N	%	subtype	N	%	CI	N	AI	N
	65	92.9	HL	5	7.1	EBV	1	HT	1
								RA	2
								UC	1

Table 2 : Characteristics of CS and non-CS patients with malignant lymphomas.

 2

	CS	Non-CS
		p*

* n.d.: not determined

Acknowledgements:

We want to thank Maria Kössler and Manuela Supparitsch for excellent technical assistance. This work was supported by the Austrian Federal Ministry of Science and Research through the Gen-AU-Child project (GZ 200.136/1 -VI/1/2005).


Nicholas Ayache

Francis Lustman

Trinocular Stereovision for Robotics


Nicholas Ayache

Olivier Faugeras

Maintaining Representations of the Environment of a Mobile Robot

published or not. The documents may come   L'archive ouverte pluridisciplinaire


published or not. The documents may come

Efficient Registration of stereo images by matching graph descriptions of edge segments


Nicholas Ayache

MEMBER, IEEE Olivier D Faugeras

S W Zucker

HYPER: A New Approach for the Recognition and Positioning of Two-Dimensional Objects

Keywords: Computer vision, occlusions, robotics, scene analysis, shape recognition

A new method has been designed to identify and locate objects lying on a flat surface. The merit of the approach is to provide strong robustness to partial occlusions (due for instance to uneven lighting conditions, shadows, highlights, touching and overlapping objects) thanks to a local and compact description of the objects boundaries and to a new fast recognition method involving generation and recursive evaluation of hypotheses named HYPER (HYpotheses Predicted and Evaluated Recursively). The method has been integrated within a vision system coupled to an indutrial robot arm, to provide automatk picking and repositioning of partially overlapping industrial parts.

I. INTRODUCTION

COMPUTER VISION is an important field where _roughly two somewhat conflicting tendencies can be identified. On the one hand, a very strong demand for ap- plications implies that performant solutions to concrete problems have to be quickly developed. On the other hand, there is a very natural desire to understand human vision as a problem in itself, hoping that this will result in the development of a general methodology for solving com- puter vision related tasks.

One may argue that many applications are either not sufficiently representative of the whole set of vision problems or that the people who solved them did not bother identifying the general methods that could be used else- where. On the other side of the road, vision theoreticians can often be reproached not to always be enough concerned with the implementation of their findings on "reasonable" hardware executing "reasonable" code.

Three main problems can be identified in computer vi- sion. The first is the construction from sensor output of a symbolic description where information necessary to solve the problem at hand is explicitely represented. The second is that of the representation of a priori knowledge. This "world model" is generally very complex and few things are known about ways of representing and organizing the corresponding database. The third problem is that of using these two structures to achieve the task.

Of course, there are many relationships between these three problems. Nonetheless, separating them allows us to Fig. 1. Isolated objects and excellent contrast are the constraints required by most of the currently available vision systems.

identify a number of potential bottlenecks. Problem I is mostly a signal processing problem, problem II mostly a knowledge representation problem, and problem III mostly a control strategy problem. Their complexity can be de- fined in terms of a number of parameters such as signal quality of the sensor output, how many and how different are the objects or phenomena that can be observed, and what type of a priori information is available.

We hope that if we fix one or several of these parameters and make the others vary in a controlled manner, we shall be able to outline a methodology for solving the corre- sponding problems in a large variety of situations. This has been our approach.

We present in this paper the methods we have developed in order to solve a very specific problem, that of analyzing scenes with randomly oriented and partially occulted industrial parts. These parts are assumed to be "flat," i.e., one of their dimensions is small compared to the other two. If we attempt to characterize this task in terms of the above parameters, it is clear that depending on signal quality, problem I may or may not be simple. On the other hand, the a priori information about the objects is of a quantitative geometric nature and can be made as accurate as needed; as a direct consequence problems II and III should be simpler. This task has been tackled by several authors and is solved in a limited way by some commercially available systems. Such systems typically deal with isolated objects with excellent lighting conditions (see Fig. 1) making problem I very simple. Silhouettes of objects are usually extracted by a simple luminance thresholding followed by a connectivity analysis. Silhouettes are then represented Fig. 2. Metallic and plastic objects often produce unpredictable highlights.

Fig. 3. Before their final process, foundary castings often have sprues and dead-heads (-) whose number and size are quite variable. by a few global numerical features making problem II also very simple, and the recognition and positioning problem is solved by nearest-neighbor techniques in feature space (for a good overview of existing industrial Vision Systems, the interested reader is referred to [START_REF] Zimmerman | Overview of industrial vision systems[END_REF]).

A strong limitation of such systems is that they cannot handle partial alterations of the observed silhouettes which can be due, for instance, 1) to uneven lighting conditions including variations of contrast, shadows, or highlights (see Fig. 2), 2) to the occurence on the objects of sprues or dead- heads, whose sizes and shapes can vary much (see Fig. 3),

3) to the occurence of touching and overlapping objects (see Fig. 4).

More sophisticated systems can so far be found only in the laboratory. They can usually deal with objects under poor lighting conditions, thanks to sophisticated edge detection techniques, and tolerate partial occlusions by using structural representation of objects and more elaborate symbolic matching techniques. The systems developed by Perkins [2] and Dessimoz [3] are based upon cross-cor- relating the tangent angle or the curvature as functions of the curve length between the scene description and the database of models. They have produced good results on complex industrial scenes, but the preprocessing (segmentation) is expensive and both methods are not well suited to scale variations. Another approach is that of Rummel [4] and Hattich et al. [5] who have developed systems based on a representation of objects with line segments, corners, and circular holes. Model primitives are then matched with scene primitives with an A* tree-search al- gorithm. Basic limitations of these systems are the com- binatorial explosion when the number of primitives in- creases and the unability to deal with scale variations. A third approach is that of finding maximal cliques in rep- resentation graphs as pioneered by Ambler et al. [61 and further improved by Bolles and Cain [7]. A basic limita- tion here is the very large complexity of the clique finding problem. A last approach developed by Davis [8], Bhanu and Faugeras [9], and Ayache and Faugeras [10] is based on the use of relaxation techniques. Objects and scenes represented by relational graphs and subgraph isomor- phisms are searched for. A basic limitation is the very large complexity of the relaxation algorithm. A fourth approach is that of the PVV system of Lux and Souvignier [11] which uses two modules implemented as coroutines: a de- scription module extracts features in the image in a top- down or bottom-up mode and a prediction and verification module that interprets features produced by the other module in terms of a data base of models. More recently, Segen [121, Turney [13], and Grimson and Lozano-Perez [14] proposed new approaches to the problem.

The approach described in this paper is based upon matching simple descriptions of the scene and the models by a technique called HYPER (HYpotheses Predicted and Evaluated Recursively) of hypotheses generation and ver- ification coupled with a recursive estimation of the model to scene transformation [START_REF] Ayache | Un systeme de vision bidimensionnelle en robotique industrielle[END_REF]- [START_REF] Ambler | A versatile computer controlled assembly system[END_REF]. It is fast, accurate, ro- bust to noise, and can deal with scale changes. It is also general in the sense that it is basically independent of the kinds of primitives used to represent the 2-D shapes and in the sense that it can be extended without too much dif- ficulty to the corresponding 3-D problem [18].

In the next section we describe how models and scene descriptions are built, i.e., what kind of primitives are used in our representation and how we compute them from the input image. We then describe the matching process that identifies models in the scene description and esti- mates the corresponding geometric transformation. An analysis of the complexity of the corresponding algorithms is then presented, and we conclude with results obtained from a number of difficult scenes.

II. BUILDING MODELS AND SCENE DESCRIPTIONS Our system is designed to handle objects with one di- mension much smaller than the other two, that is flat or almost flat objects. Partial occultation is allowed, and no special care is taken of the illumination, i.e., the system is capable of working under poor lighting conditions. The acquisition device is a cheap standard Vidicon camera IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. PAMI-8. NO. 1. JANUARY 1986 connected to an image memory. The video signal is typi- cally quantized using 256 grey levels and the image size is either 256*256 or 512*512.

One key feature of the system is that models and scenes are represented the same way. This makes life a lot easier for the matching procedures we describe later.

In order to build a model or a scene description, the following sequence of operations is applied to the picture of the isolated object or of the scene:

1) if the contrast is high enough (i.e., if the lighting conditions are perfectly controlled), threshold the image, smooth the resulting binary picture using erosions and di- lations [19].

2) if the contrast is not high enough (general lighting conditions), find the edges by combining gradient and sec- ond order derivative information [20], [211. A Sobel op- erator is first applied to the image and the result is thresh- olded yielding the major intensity discontinuities with the standard problems of contours which are not connected and of width larger than one pixel. Second, the picture is low-pass filtered with two filters of different sizes (in the current implementation we use 7*7 and 3*3 arithmetic av- erages). The results are subtracted and zero crossings de- tected. This produces a very accurate detection of all in- tensity discontinuities. Edges are connected and of width one pixel. By following edges in parallel in the two im- ages, we can eliminate those corresponding to low con- trast variations while keeping the connectivity high.

3) find the list of connected border points [START_REF] Chieze | Logiciel d'analyse de contours[END_REF]. 4) approximate the connected components with poly- gons [START_REF] Pavlidis | Structural Pattern Recognition[END_REF].

Shapes of 2-D objects are therefore represented by po- lygonal approximations of their borders. This description has several advantages which are as follows.

1) It is local, meaning that different parts of the objects are described independently of each other, allowing for independent identification.

2) It is compact, meaning that most objects can be ac- curately described using a small number of line segments (typically less than 100).

3) It is general, meaning that it can be applied to any planar shape.

4) It is sensitive to variations in the position and ori- entation of the objects and allows to recover those param- eters accurately.

5) It is simple, meaning that the operations used to go from the image to the description are straightforward and fast; most of them can be executed in fractions of a second on commercially available equipment.

Fig. 5 shows the silhouettes of two mechanical parts used in the French car industry. These parts are foundry castings. Fig. 6 shows the model description associated with these silhouettes and with their symmetric homo- logues. The number of segments involved in these descrip- tion ranges between 39 and 50. The contrast conditions are very good and allow for the use of the first method.

Fig. 2 shows some of the parts of an electromechanical device made by TELEMECANIQUE; Fig. 7 shows the model descriptions associated with these silhouettes. (Symmetric homologues are not shown because their con- tours are too similar to the original ones).

The number of segments of these descriptions ranges between 22 and 129. The contrast conditions are poor and vary from one part to another, and the unpredictable pres- ence of reflects (some parts are metallic, others are made of plastic) imposed the use of the second extraction method.

In the following, we assume that both the model and the scene descriptions are given by a set of linear segments, respectively, (M,) and (Sj) of the form: Mi = (xi, yi, li, a1) and Sj = (xj, yj, lI', aj) where x and y are the coordinates of the segment midpoint, I is the segment length, and a is the segment orientation measured relatively to the hori- zontal axis.

In addition, the model description will include a certain number of privileged segments: in the current implemen- tation, the privileged segments are the ten longest seg- ments of the model description. (For justification, see Sec- tion IV-A.)

III. MATCHING MODELS AND SCENE DESCRIPTIONS

A. Overview The problem is to match in a scene one or several models while allowing for distorsion by partial occlusions and by a similarity transformation (the product of a translation, a rotation, and a scaling). The basic idea is, for each pos- sible model, to generate (predict) and evaluate a number of hypotheses.

To generate a hypothesis is to predict the position of the model in the scene: this prediction is made by matching a privileged segment in the model description (M.D.) with a segment in the scene description (S.D.) by comparing local intrinsic features. Typically, a few hundred hypotheses are generated and ranked on the basis of a local criterion of merit.

To evaluate a hypothesis is to take advantage of the pre- dicted position of the model to identify additional seg- ments between the two descriptions, and also refine the predicted position of the model (by a Kalman filter). Only the best first hypotheses are evaluated (typically a few tens), and the result of each evaluation is a final position estimate and a quality measure which accounts for the relative length of the identified segments.

The matching ends when a sufficient number of hy- potheses has been evaluated or when a very high quality measure is reached. The hypothesis with the highest qual- ity score is then reexamined before being validated or re- jected.

We shall now describe these different stages in detail.

B. Generating Hypotheses

The model position is defined by a transformation T, the product of a rotation, a scaling, and a translation. The transformation T is described by a parameter vector v - (k -cos 0, k -sin 0, tx, ty), such that the image (x*, y*) of an arbitrary point (x, y) of the M.D. is given by the set of equations

x* = tx + x * k -cos 0 -y k * sin 0 y* = ty + x -k -sin 0 + y -k -cos 0.

(

(2)

Given an M.D. and S.D., a hypothesis (i.e., a prediction of the position of the model in the scene) is generated by matching a privileged segment of the M.D. to a compat- ible segment of the S.D. Compatibility is locally defined as follows:

Let Mo be a privileged segment of the M.D. A segment S,0 of the S.D. is defined as compatible with Mo iff:

1) the angle A between Mo and its preceding neighbor is close to the angle A' between Si0 and its preceding neighbor. (Close means that abs (A -A') is lower than a threshold, typically 30 degrees).

2) the ratio r between the lengths of So and Mo is close to the a priori estimate ko of the scale factor, when this estimate is available (close means that abs (r -ko) is be- low a threshold, typically 0.3 * ko). When a privileged segment Mo is matched to a compat- ible scene segment Sio, and if no a priori estimate ko of the scale factor is available, the parameter vector v0 = (ko cos 00, ko sin 00, to, tv,0)T of To is computed by resolving

(1) and ( 2) for the two pairs of corresponding endpoints of MO and Sjo [see (3)-( 6)]. In practice, one sometimes has a good a priori estimate ko of the scale factor k. In this case, the three remaining parameters 00, txo, and tyo of To are computed by ( 4)-( 6) only.

ko= I (Sjo)Il (Mo) 00a(S0) -a(M0) txo = x -ko -(xo -cos 00 -yo sin 00) tYo = y -ko -(x0 -sin 00 + yo * cos 00)

(3)

(5)

(6)
where 1 (Sjo), 1(Mo), a (Sj0), and a (M0) denote, respec- tively, [he lengths and orientations relative to the horizontal axis of Sio and Mo, and where (x0, y4) are the coordi- nates of the midpoints of the segments S10 and MO, respectively.

Since the initial estimate To of T is very likely in error, we introduce a measure of this error: So is an error co- variance matrix defined by

So = E((v0 -v) -(v -v)t) (7)
where v and v0 are, respectively, the parameter vectors of the unknown transformation T and its estimate To. In practice, So is initialized for each hypothesis with respect to the error variances Sk,2 s2,52 and S2 attached, respec- tively, to the initial estimates ko, 00, txo, and tyo. In the current implementation, these variances are heuristically estimated. Assuming that sk and s2 are small compared to 1, the elements of S0 are approximated by So(1, 1) = k20 sin2 (00

) * S2 + cos2 (00) _ Sk So(2, 2) = k0 cos2 (00) * S2 + sin2 (00) 2 Sk (8) (9) SO(1, 2) = So(2, 1) = sin (00) cos (00) . (S k-. S2) (10) So(3, 3) = s- So(4, 4) = s' (1 1) (12)
the other terms of Sjo being equal to zero.

When a given number of hypotheses has been generated (typically a few hundred), the hypotheses are ranked by measuring the compatibility between the pairs of matched segments (see above). Then the best hypotheses (usually a few tens) are evaluated.

C. Evaluating Hypotheses

After computing an initial estimate To of the transfor- mation, we match additional segments of the M.D. with segments of the S.D., while updating the estimate of the position of the model in the scene and computing a quality measure of the resulting match. We now proceed to de- scribe in more details those three points.

1) Matching Additional Segments: After having iden- tified Mo with Sjo, the program matches the other seg- ments of the model by an iterative algorithm: at iteration i, the program selects among the non yet examined seg- ments of the M.D., the segment Mi which is closest to Mo (see Fig. 8). The choice of segments Mi close to Mo is because if the initial estimate To of T is inaccurate, then the error in position between the estimated image TO(MW)

of T(M1) increases with the distance 11MoMil|. This seg- ment Mi is transformed into a segment MA* by the current estimate T, -I of the transformation T Then a dissimilarity measure dij is computed between the image segment MF and every segment Sj of the S.D. This dissimilarity mea- sure is a weighted sum of three positive quantities which, respectively, account for 1) ai, = the absolute value of the difference between orientations of M,* and Sj,

2) Di = the Euclidean distance between the midpoints of Mt and SJ,

3) ,j = the absolute value of the relative difference be- tween lengths of MF and Sj: lij = (Pl--lj)Iij.

Each of these quantities is upper bounded by amax, Dmax, and lmax' respectively. dij is then computed as follows:

* if aij or Dij or lij is above its corresponding upper bound, then di = 1.

* otherwise, di, is given by d,j = p * aii/amax + q * Dij/Dmax + r * 'ij/lmax (13) where p, q, and r are associated positive weights which add up to one. In the current implementation, we chose p = 0.6, q = 0.3, and r = 0.1, values emphasizing the role of the segments orientation. dij takes a minimum value of zero when MF and Sj are just superimposed, and increases when the discrepancy between Mi* and Sj increases: the maximum value of dij is 1, and this value is reached if and only if one of the quan- tities aij/amax, Dij/Dmax, or lij/lmax is greater than or equal to one. In the current implementation we have amax = 20 degrees, Dmax -12 pixels, and lmax = 70 percent.

M1 is matched with the segment Sj of the S.D. such that dij is minimum and lower than one. Otherwise, Mi is matched with NIL, which means that Mi has no homo- logue in the S.D. with respect to the current hypothesis.

2) Updating the Model Position: When a segment Mi is matched with a segment Sii, a recursive least square Basic Method: Given a set of matches {(M,, Sj,)}, we look for the transformation T which minimizes the crite- rion

R = E-A2K(T(m1), sj,) (14)
where mi and sj, are the midpoints of segments Mi and Sj, respectively, A is the usual Euclidean distance, and 1i is the length of segment Mi. The term 1l/K is here to em- phasize the role of long segments which are less sensitive to noise. K is a constant whose value depends on the qual- ity of the observed images (in our implementation, we simply computes K = Dmax 1 where 1 is the av- erage segment length and Dmax is the quantity defined in Section III-C-1).

If we represent, as in Section III-B, the transformation T by the vector v = (k cos 0, k sin 0, tx, ty)t, and the point sj, of coordinates x,!, y/ by the vector Yi = (x', y/)t, we can rewrite (14) as

R = E (Y -C, V)t W1(Y -C, v).
Matrix Ci is given by C bi -Yi I 08 Yi xi 0 1/ where xi and yi are the coordinate of point mi.

Matrix Wi is given by ( -O [START_REF] Ayache | Un systeme de vision bidimensionnelle en robotique industrielle[END_REF] with wi = K/li.

We would also like to control the variation of some of the parameters of the transformation T This can be achieved by adding to R an extra term of the form (v - v0)T S) I(V -v0) where v0 corresponds to the initial hy- pothesis and So is the matrix described in Section III-B.

Finally, the criterion R is written as 16) R is a quadratic criterion and can be minimized recursively by the standard following equations (cf.

R = (YI -C v)t W' l(YI -C v)t + (v -vo)t So 1(v -vo). (
[24] for in- stance):

vi = vi_I + Ki * [Yi-Ci * vi- (17) Ki = S cc[[ i + Cwi* Si_l C[] (18) Si = [-Ki Ci] Si-1 (19)
These equations are initialized for a new hypothesis by So and vo computed in Section III-B, and are recursively updated after each new match (Mi, Sj).

Refined Method: In the previous approach, the updating of the transformation T was done by trying to superimpose the centers of the matched segments. More accu- rate results were obtained by superimposing the center of each identified model segment on the straight line supporting its homologous scene segment. In this case, the determination of T is much less sensitive to the variations of the segment lengths, as it does not modify the position of the supporting straight lines.

In that case we simply minimize the criterion R' =Z -K A2(T(mi), Sji) (14')

where A(T(Mi), Sji) is the distance of the point T(mi) to the infinite line containing SYi. If its orientation is a' and if the coordinates of sj, are (x', y!), the criterion can be rewritten as R= Z ([-sin (a!') cos (a[)] Civ + 3 ')2 (15') i KI I where 6/ = xl sin (a') -y cos (a'). The minimization is performed exactly in the same way as before.

3) Computing a Quality Measure: The use of the quality measure is to discriminate between correct and wrong hypotheses. After each iteration i, Q(i) measures the length of the identified model segments as a percentage of the total model length. Q = Q(N) (N is the number of model segments) is upper bounded by 1; this maximum value is obtained whenever the model is perfectly and en- tirely identified in the scene. Q decreases in the presence of occlusions and nonrigid distorsions (noise, tilted ob- jects, errors of segmentation, * * *).

D. Ending the Matching Process

The matching ends when the number of hypotheses which have been evaluated is large enough (typically a few tens), or when a very high quality measure is reached by an hypothesis. In each case the hypothesis with the highest quality measure is reexamined before being validated or rejected: the reexamination consists in evaluating a last hypothesis, whose a priori parameters are the a posteriori estimate and covariance matrix of the best hypothesis. This reexamination is to check whether some additional model segments could be matched with a more accurate initial estimate of T When this is the case, the process is repeated until it converges. The reexamined hypothesis is then definitely validated if its quality measure is above a prespecified threshold, and rejected otherwise.

IV. COMPLEXITY ANALYSIS A. Computing Time

The average computing time required to match a model description with a scene description is equal to the number of generated hypotheses multiplied by the average evalu- ation time of a hypothesis.

The number of generated hypotheses is reduced by hav- ing a small number of discriminant model segments se- lected to be used as privileged segments Mo. The choice of the long segments is for two reasons. First, long segments are usually less numerous and therefore more dis- criminant. Second, the initial estimate of the transfor- mation T is more accurate with long segments. Of course at least one of the privileged segments has to be visible (e.g., occluded length < 30 percent of segment length) in the scene for the model to be identified. It appeared that the choice of the 10 longest model segments as privileged segments never prevented the recognition of reasonably occulted objects (e.g., total occluded length <60 percent of model length) in our experiments. This is probably due to the fact that, in this case, the probability of having all the priviliged segments occluded simultaneously is very small.

In addition, each privileged segment Mo of the M.D. is identified only with compatible segment Sjo of the S.D.

(compatibility is defined in Section V-B). Typically, the number of scene segments compatible with a privileged model segment is about 10 percent of the total number of scene segments (allowing a scale variation of about 30 percent). Therefore, if there are 10 privileged model seg- ments, the number of generated hypotheses is usually close to the number of scene segments.

The evaluation time is reduced mainly by three techniques. First, a branch-and-bound technique is used: dur- ing the evaluation of a hypothesis and at each iteration i, the program computes an upper bound Qmax on the final quality measure Q(N): this upper bound is computed by adding to the current partial quality measure Q(i) the nor- malized length of the model contours which have not been examined yet (therefore assuming this remaining part will be perfectly matched). As Q(i) is a decreasing function of i, the evaluation of the current hypothesis is aborted early (and the hypothesis rejected) as soon as Qmax happens to be lower than the quality measure attached to a previously evaluated hypothesis.

Second, the evaluation process is significantly acceler- ated by having the scene segment orientations aj initially sorted: in this case, when searching for the best match Si of an image segment Ml (cf. Section III-C-1), the scene segments Sj whose orientation aj is compatible with the orientation of M* (i.e., such that abs (a* -aj < amax) are selected by a binary search in logarithmic time. One could also compute square buckets on the S.D. to have fast ac- cess to the scene segments close to a predicted location.

Third, all segments whose length is below a fixed limit (typically 8 pixels for images of size 256 * 256) are re- moved from both the M.D. and the S.D. before process- ing. To conclude, one could notice the possibility of gener- ating and evaluating all hypotheses independently of each other. This property allows for an execution of the pro- gram on parallel hardware to still reduce the global com- puting time. If several models must be located in the same scene, they can also be processed in parallel. The storage requirements are small and are a linear function of the data size: one has to store essentially the M.D. and the S.D., i.e., the vertices coordinates of two polygonal approximations (usually a few hundred points). Also, and in order to speed up the evaluation process (cf. above), one can store the orientations of the segments of both descriptions.

V. RESULTS The recognition method described in this article has been integrated within a vision system and tested on a large number of different scenes. The vision system has also been coupled to an industrial robot arm to achieve picking and repositioning of unoriented partially overlap- ping industrial parts [25]. We present here some typical results which illustrate the capacities of the vision system.

Except for Example 6, programs are written in Fortran and run on a minicomputer Perkin Elmer 3240. Also, computing times refer to the matching process only ex- cluding the image segmentation process; in effect, the segmentation process is totally independent of the match- ing process and should be performed in a fraction of a second on dedicated hardware.

A. Example 1: Illustrative Example

We first present a simple didactic example to illustrate the major steps of the recognition procedure. Fig. 10 il- lustrates the generation and evaluation of a correct hypothesis, while Fig. 11 illustrates the discrimination be- tween correct and wrong hypotheses.

Let us consider the two left-most drawings of the first row of Fig. 10; they show, respectively, the model description associated to a car shock absorber and the scene description associated to the image of a similar part rotated, translated, and partially occluded by another part. Both descriptions have been obtained by the method described in Section I (good lighting conditions).

The task of the recognition program is to match and locate the model within the scene. Among all the hypotheses generated by the program, a correct hypothesis is obtained when the privileged model segment repre- sented by a solid line in the M.D. is matched to the com- patible scene segment represented by a solid line in the S.D. (first row of Fig. 10). In this situation, the program determines an a priori estimate of the model position which is shown in the third column of this first row.

Rows 2, 3, and 4 of Fig. 10 correspond to some steps of the evaluation process. Columns 1 and 2 show, respectively, in solid lines the segments which are identified be- tween the M.D. and the S.D. Column 3 shows the current estimate of the model position. Successive estimates

(f) (g) (h) (i) (a) (b) (c) (d) (e)
Fig. 12. Models 3 and 4 of Fig. 6 are identified and located (in white) in four scenes. Notice the presence of sprues and dead-heads on the castings, and the presence of scaling between model and scene descriptions of 0.68 in scenes (a), (b), and (c), and 1.06 in scene (d).

superimposed to better exhibit the convergence result, and one can visualize the recursive update of the model position. Numerically speaking, the parameters (0, k, tx, ty)

of the transformation T vary from an a priori estimate (-81.7°, 1.13, -49 pixels, 281 pixels) to a final estimate (-73.86°, 1.015, -15.67 pixels, 237.52 pixels).

The last row of Fig. 10 shows the final result obtained after the reexamination of this hypothesis: one can notice the correction of some matching errors which were ini- tially due to the inacurrate a priori estimate of the model position. The parameters of the final estimate of T after reexamination are (-74.07°, 1.00, -9.55 pixels, 236.34 pixels).

Among all the hypotheses generated by the program, we see in Fig. 11 nine hypotheses generated when the same privileged segment is identified with nine different com- patible scene segments. All these hypotheses (except for the last one) have a quality measure lower than 0.25 and are rejected; the last hypothesis has a quality measure greater than 0.60, and is validated.

B. Example 2: Castings with Dead-Heads, Variable Scale Factor Fig. 12 shows the result of the identification and positioning of models 3 and 4 of Fig. 6 in four different scenes containing similar parts in arbitrary planar positions. The parts are observed just after the casting process and they have sprues and dead-heads attached to them. In addition, there is a scaling between models and scenes of 0.68 in Fig. 12(a), (b), and (c), and of 1.06 between models and (d). This scaling is taken into account by using (3) to es- timate ko.

The pictures are segmented as described in Section II (good lighting conditions). The models are correctly detected and located, and the computed positions are superimposed in the pictures. The quality scores vary between 65 and 85 percent, and the computing time is of the order of one second per model.

C. Example 3: Partially Overlapping Castings

Fig. 13 shows the identification and positioning of models 1, 2, 3, and 4 of Fig. 6 in a scene containing similar parts in arbitrary positions [Fig. 13(a)]. In addition, some of the parts have large sprues and dead-heads attached to them, and the parts are partially occluding each other. The picture is segmented as described in Section I (good lighting conditions) and the resulting scene descrip- tion is shown in Fig. 13(b) (280 segments). The result of the matching is shown in Fig. 13(c), where the models have been superimposed in white on the scene at the lo- cation determined by the program. We show in Table I the main parameters of the solution.

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. PAMI-8, NO. 1, JANUARY 1986 (b) Fig. 14(a) shows a scene with several overlapping parts of an electromechanical device observed under bad light- ing conditions (this image corresponds to the scene shown in Fig. 3). The scene is segmented by the second method described in Section I and the resulting scene description (759 segments) is shown in Fig. 14(b). Models 5, 6, 7, 8, and 9 of Fig. 7 are successfully identified and located in the scene; the result of the matching is shown in Fig. 14(c) where the models have been superimposed in white on the scene at the location determined by the program. Note that when there are several occurences of a model in a scene, the program simply selects the hypothesis with the highest quality measure, which usually corresponds to the most visible occurence. A minor modification in the pro- gam would allow for the recognition of all the occurences of a model corresponding to hypotheses whose quality measure is above a determined threshold. Table II shows the main parameters of the result. E. Example 5: Coupling with a Robot Arm

The vision system has been coupled to a robot arm to achieve automatic picking and placing of overlapping workpieces. In this system, the modeling of objects in- (c) Fig. 14. (a) Original scene containing parts of an electromechanical device (this is the observed image of the scene in Fig. 4). (b) Segmented scene description (759 linear segments). (c) Models of Fig. 7 are identified and located (in white) by the program in the scene. cludes a list of potential grasping locations, and the rec- ognition procedure includes, when a model is identified, the selection of an accessible grasping location among the potential grasping locations. This robot system is described within details in another article [25] and we shall only present results in the sequel. Fig. 15 shows the potential grasping locations attached to models 8 and 9 of Fig. 7. Fig. 16 shows the accessible grasping locations selected after the recognition of these models, and Fig. 17 shows the actual picking and repositioning of the corresponding objects.

The result of this coupling has been to provide a more realistic testbed for the vision system, and also to dem- onstrate the feasability of the automatic picking and re- positioning of partially overlapping workpieces lying on a flat surface using our vision system.

F. Example 6: Precision Test

It is difficult to compute the accuracy of the determination of the transformation T in general because it de- pends on many factors such as the nature of the model, the quality of the viewing conditions, and the degree of rig. Ii. iaraspilg anu repositoning ot tne oujects sciecieu in rig. Io.

(a) (b) Fig. 16. Determination of accessible grasping locations for two of the models identified in Fig. 14; the rectangles are the vertical projections of the gripper fingers.

occultation of the observed objects. At the least, a qualitative estimate was derived by having the robot arm safely picking and repositioning several different objects in many different situations. However, a quantitative estimate of the accuracy of the determined rotation angle 6 was made on images of mechanical gears. The polygonal segmentations extracted from two different images of a gear are shown in Fig. 18. One can notice some local alterations of the contours which are mainly due to unpredictable metallic reflections.

The precision experiment consisted in extracting the description of a gear in a reference position. This description was taken as a model description. Then, the same gear was rotated by a precisely measured angle, and the corresponding extracted description was taken as a scene description. For 300 successive measures, the maximum deviation between the estimate and the actual angle was 0.15 degrees. The measured standard deviation was 0.07 de- grees.

For this industrial application, the program was trans- ported to a Motorola-68000 based microcomputer, and partially translated to machine code. The number of generated hypotheses was 50, and only the 8 best hypotheses were evaluated. The maximum length of non identified segments was upper-bounded by 30 percent of the total model length, while the average length of nonidentified segments was 20 percent (due to the lighting conditions and the lack of stability of the segmentation algorithm). The computing time is lower than one second, including the segmentation process which is done on dedicated hardware. PAMI-8, NO. 1, JANUARY 1986 VI. CONCLUSION We have described a new method for the recognition and positioning of 2-D objects. This method uses segmented descriptions of the object contours to generate and recur- sively evaluate a number of selected hypotheses. The main features of this method are its robustness to lighting con- ditions, partial occlusions (up to 60 percent typically) and scale variations (20-40 percent typically), its accuracy in locating objects, its high degree of parallelism (hy- potheses can be generated in parallel), and its small stor- age requirements (essentially the storage of the segments endpoints). The method has been experimented on a large number of different scenes, and some typical examples have been presented, including the coupling of the vision system to a robot arm.

Returning to problems I, II, and III of the Introduction, we can say that the existing work in computer vision al- lows us to generate quickly and accurately the outlines of flat objects even under difficult viewing conditions. Boundary representations can then easily be built by func- tional approximation techniques. First degree polyno- mials were used in this paper but nothing (except the com- puting time) would have prevented us from using other functions. Problem I is therefore solved by algorithms which can be implemented by very fast programs or hard- ware.

We have only scratched the surface of problem II. We represent our models the same way as our scenes, i.e., with polygonal approximations. The corresponding data- base is simply a sequence of such models and no ways are provided for smarter model indexing than a simple linear scan of that database. A lot remains to be done in this area.

Problem III, that of matching models with scene de- scriptions, has been solved in a simple way by exploiting the very important constraint of rigidity. This allows us to work with the well-known group of similarity transfor- mations and to drastically prune our search tree. By cou- pling the search algorithm with a recursive estimation of the transformation, we have achieved a high positional ac- curacy. We believe that these two features (exploiting ri- gidity and recursive parameters estimation) are basic in many related applications. In that sense we think our work is also a contribution to establishing the lacking method- ology we were referring to in the Introduction.

Fig. 4 .

 4 Fig. 4. Touching and overlapping objects.

FigFig. 7 .

 7 Fig. 5. Reference parts.

  Fig. 8. Order of selection of the model segments.

Fig. 9 .

 9 Fig. 9. Notations for matching. technique (Kalman filter) is used to update the estimate Ti of T The new value of the parameter vector vi is computed as follows.

  IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL.PAMI-8. NO. 1, JANUARY 1986

  are

Fig. 10 .

 10 Fig. 10. Generation and evaluation of a correct hypothesis (see text).

Fig. 11 .

 11 Fig.11. Discrimination between wrong and correct hypotheses (see text).

  Fig. 13. (a) Original scene containing four partially overlapping castings with sprucs and dead-heads. (b) Segmented scene description (280 linear segments). (c) Models of Fig. 6 are identified and located (in white) by the program in the scene.

Fig. 15 .

 15 Fig.15. Grasping locations attached to models 8 and 9 of Fig.7. The symmetric rectangles are the vertical projections of the gripper fingers.

Fig. 18 .

 18 Fig. 18. Descriptions associated with the gears used in the precision test. (a) Reference gear. (b) Gear rotated by an angle of 7°. (c) Superimposition of (a) and (b) by the program.

  PATTERN ANALYSIS AND MACHINE INTELLIGENCE. VOL.

TABLE 11

 11

		RECOGNITION OF MODELS 5, 6, 7, 8, AND 9
	Model Number of Segments	Quality Measure Computing Time
	5	73	39 percent	7 s
	6	22	36 percent	4 s
	7	48	40 percent	2 s
	8	129	66 percent	I s
	9	89	38 percent	3.5 s

Authorized licensed use limited to: UR Sophia Antipolis. Downloaded on July 7, 2009 at 09:29 from IEEE Xplore. Restrictions apply.


Isaac Cohen

Laurent D Cohen

Nicholas Ayache

published or not. The documents may come

Using deformable surfaces to segment 3-D images and infer differential structures


Isabelle Herlin

Nicholas Ayache

published or not. The documents may come


Nicholas Ayache

Isaac Cohen

Isabelle Herlin

Isabelle Herlin Medical

Image Tracking Blake

Medical Image Tracking

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.