Keywords: Algorithms, Mea Semantic segme detection, smooth

nternet search h apid emergence Additionally, ma been started to d n a transition fr modeling of buil focus has been o Detection And aerial cameras ha point clouds from hese point cloud 3D building mod This paper prese flow for the auto built-up areas fro extruding from, o each roof is bein can then be class oof shapes. We compete well esearchers. Our Austria) with 18

INTROD

copies of all or pa d without fee prov t or commercial a l citation on the f n servers or to re nd/or a fee. USA.

-0/00/0010…$10.0 concept of "supe to well-define n automating an ntation of buildin tion vertical aeri ffers a measure leading to a bas re based on a te show that vertic ment to a roof typ on is a framewo al with extrudin the images an roperties, buildin ach building. isolated, roofs g DSM with a tot all roof planes g ed by [START_REF] Toldo | Robust Multiple Structures Estimation with J-linkage[END_REF] an and conceptu to a classificatio t an interpretatio n photogrammet that discuss th othing algorithm edges and sma plane detection w iation" TGV [13 an be efficient ast.

n of the model b ually composed with the a-prio f the solution an to the input dat ideally suited f uited to buildin urfaces.

Elimina

The definiti elimination of s dormer windows There are t processing step: planes must exc Additionally we planes are linke herefore relevan discontinuities at within a roof ca chimneys. Figur structures have b here. In addition to the principal roof types of table 1, the approach also works with the connecting roof shapes of figure 9.

Figure 9. Examples for possible connecting roof shapes

One significant improvement of the proposed method over [START_REF] Kada | 3D building reconstruction from lidar based on a cell decomposition approach[END_REF] is the ability to deal with non-symmetric and more general roof shapes.

Experiments

The test area covers 400m x 400m near the core of the city of Graz with 186 different buildings. The vertical aerial photography was taken with a GSD of 10 cm and 80% forward and 60% sideward overlaps, using the large format digital aerial camera UltraCam-X.

Ground truth of the roof shapes was collected by hand. Table 2 summarizes the types of roofs. Since some roofs fall outside the standard types, a "miscellaneous" category with 24 entries was required. An additional classification was into "simple" and "complex" buildings, and the latter was further classified into Lbuildings (corners), T-buildings and buildings with U-and other irregular shapes. The test area has 125 simple and 61 complex buildings. Of the complex buildings 25 are L-and 17 are Tbuildings, and 19 fall into the miscellaneous category.

Table 2. Ground truth: types of roof shapes for the 186building test area

The smoothing of the DSM not only eliminates outliers, but increases the throughput of plane detections by a factor two. Plane detection requires a focus on the major planes, and thus a meaningful threshold for the acceptable minimal size for plane segments. This threshold is calculated for every building depending on the size of the building footprint and the size of the single plane segments.

The 186 buildings consist of a total of 614 major roof planes. Of these, our approach detected 567 planes. Table 3 presents the detection rates at 92%. A major limitation for the plane detection presents itself when the roofs are curved or very fragmented, thus when there are no planes. The test area has four such buildings. Down-sampling of the DSM point clouds by a factor 4 is acceptable to first suppress minuscule plane segments and to secondly accelerate the throughput. This down-sampling eliminates small structures in advance. Nonetheless even with this down-sampling not all small structures can be eliminated especially larger dormer windows. Before the roof type can be assigned one needs to eliminate the remaining small structures caused by bigger dormers and chimneys and other extrusions or intrusions. Success in defining and removing such small structures was at 83%, identifying 612 of the 738 smaller roof structures. The assignment of a standard roof type concerns 162 of the 186 buildings, since 24 fall outside the standards. If we could detect these non allocatable buildings automatically we achieve a detection rate of 88%, thus 145 buildings out of 162 were correctly classified (see table 4). If we include the 24 nonallocatable buildings we achieve 78%.

While the flat roof would seem to be the easiest type to identify, only 88% were correct. This translates to an error in 2 of 16 buildings, and it turns out that these 2 flat roofs have gardens. The shed roofs were identified at a rate of 86% since 2 buildings were incorrectly classified due to large extrusions in the form of large dormer windows. Gable roofs were detected at a 91% success rate. Problems again occur with large extrusions. All hip roofs were correctly detected. However, the half-hipped roofs only were correctly classified in 43% of the cases. The problem with this category derives from the two small plane segments in the upper height class. The current approach eliminates those plane segments during plane detection The test area did not include any mansard and mansard hipped roofs. We therefore processed 10 additional buildings from another data set (Annecy, France) for each of these two types. All 5 mansard roofs were detected. Errors occurred with the mansard hipped roofs in 2 of the 5 cases. The plane segments in such roofs are at very similar pitches so that plane detection merges plane segments when they should be kept separate.

Conclusion

We propose a method for automatically mapping roofs and classifying them into architecturally accepted standard types, based on traditional digital large format color aerial photography. This method relies on point clouds at 25 pts/m 2 extracted from highly overlapping vertical aerial imagery, and on an image classification using color and texture to delineate building outlines and footprints. Experimental work in a Graz-test area with 186 buildings with 614 roof planes, results in correct roof planes in 92% of the cases. Small roof structures do confuse the analysis and must therefore be detected and eliminated. This is successful in 83% of all the test cases. Roof types get classified correctly at a rate of 88%. LiDAR literature quotes its success with roof type assignments at xxx%. Limitations exist with complex roof shapes that include large dormers, or with curved roofs. However, those difficulties are not specific to aerial photography and also present themselves with LiDAR data. We may thus conclude that aerial photography produces results at least as good as those from LiDAR point clouds.

While we propose to continue with the development of roof analysis work based on aerial photography, the experimental work has revealed that some weaknesses exist in the proposed method. These weaknesses from confusions with large dormers, or roof gardens, or small differences in pitch angels of mansard hipped roofs will be addressed. In addition work is needed with a wide range of buildings in diverse areas of the World where architectural styles are different from those in the initial test area Graz. An initial look at French urban areas immediately shows the strong use that is being made there of curved roofs. Snow-free coastal resort environments may have various types of flat roofs, historical small towns, alpine towns, urban cores with skyscrapers and the urban fringe with its industrial zones will offer different challenges.

Figure 3

 3 Figure 3: (left) of building roo Dimen (right) 3D Point the two major

Figure 4

 4 Figure 4: RGB smaller

Figure 5

 5 Figure 5: (a) bu entation result ( façade reconstru fter the determi e have to split th a further interp ding footprint int ance with figu ement that the nu by defining an teristics of the bu

ail of Leiden, Ne nal Surveys, Be urveys.com/].

	nar Ro of Surf face Se egmenta ation u w geometry [9], and thus to a c ]. Such dense e DSM leads	sing 3D D Visio	n
	ing roof lines a and is helpful in
	ysis.
	lipp Meixne er presents the aut tomatic segmen	Fra anz Leberl	Math hieu Brédif
	Computer Gr raphics & built-up areas fr rom high-resolut	Institute of C Computer Gra aphics &	MATI S Laboratory
	Vision versity of Tech hnology ns to each roof a a type, and it of oof to carry sola ar panels.	Graz Unive ersity of Tech Vision	nology	Institute Géo Univer ographique Na rsité Paris-Es ationale t
	10 Graz, Aust er@icg.tugra tria az.at multi-step process ts of the propos sing framework sed procedure ar ustria) with 186 6 buildings We s	A-801 leberl@ 0 Graz, Austr @icg.tugraz ria z.at	9 94165 Saint-M Mathieu Mandé Cedex u.bredif@ig x, France n.fr
	ovide us with a	success assignm
	ofs.
	T has initially bee e of 3D buildin any commercial develop urban 3D om the classical lding roofs is th on the use of a Ranging). How as rendered poss m high overlap ds jointly with t dels. en a strong driv ng models of la and government D geographic inf l 2D-to the nov hus a relevant re aerial LiDAR po wever, recent pr sible the acquisit digital aerial im he image inform ving force for th arge urban area tal initiatives hav formation system vel 3D-GIS. Th esearch topic. Th oint clouds (Lig rogress in digit tion of very den magery, and to u mation to genera he as. ve ms ch or the proposed r roof interpretatio 1] and its impr rovement to de building [12]. This segments c point clouds in nto individual pr he D point clouds as ssociated with ea he uilding's point c cloud has been i ght steps. First is a sm moothing of the tal ation method (TG GV) [13]. Then nse an approach first introduce use -called random m sampling ate Finally the roof p planes are input	tree, st dimens doors, suspend figure 1 treet detail, brid sions, and many facade elemen ded wires, stree 1). LOD-2 to LO dge and water y details will be nts, sidewalks, m et signs etc., a OD-4 need a mod body is model included such a manholes, park all as separate o del of the roof sh led in three as windows, king meters, objects (see hapes.
	ents a multi-step p processing fram mework and wo ork
	The 2-dimension model of the Ear 3D GIS and its planning, archit environmental s ransactions etc. he required lev ange from the L models with roof such as windows nclude the build he virtual city w omatic segmenta om high-resoluti or intruding into ng modeled by m sified as a specif e show that the with LiDAR-re experimental w ation of building ion vertical aeri , a roof are bein means of its pla fic roof type from results from a esults as repo work employs a g roofs in dense al images. Detai g excluded so th anar segments an m a set of standa erial photograph orted by LiDA test area in Gr ely moothing ils ange data will b be noisy so that hat opic is a very p rominent one in nd e there exist m any algorithms ard ain requirement for such a smoo hy es noise but pr reserves sharp AR his reason and to o accelerate the p az using the "total generalized var 86 buildings. and Subject alysis (Object rec rms asurement, Exper ntation, roofs, r hing DUCTION nal GIS is rapid rth and human ha 3D virtual citi tectural design, simulations, dis Depending on t el of detail (LO Lego-type parall f shapes as LOD s and roof detai ding interior [18 will model not o t Descriptor construction). rimentation, Ver roof shapes, aer dly morphing int abitat. Typical u ies include urba tourist and saster prepared the input data an OD) may vary w lelepipeds denot D-2 to building m ls as LOD-3 and 8]. In its most so only each buildi rification. rial images, plan o a 3-dimension use of the resultin an and landscap leisure activitie dness, real esta nd the applicatio widely. This ma ted as LOD-1 v models with deta d on to LOD-4 ophisticated form ing, but also eac ne nal ng pe on, ay via ail to m, ch ACM 1-58113-000-cific permission an -2011, Chicago Il, ublish, to post on notice and the full ributed for profit oom use is granted ke digital or hard ate es, d "Huber model g the Huber nor er reflects the n at it reduces st rm is based on T erm is based on oximated by piec e surfaces and t er variant of thi rces the solution ut the smoothne e regularization f an energy-func onal approach fi rs has the advanta age that it ca the GPU and is therefore very fa	Figure e 1. 3D city mod del, LOD2 (deta [C Courtesy: Aerod data Internation http://ww ww.aerodata-su 1000 p GSD b model wires. comput traditio acquire pts/m², based on etween 10 cm a details of facad The DSM from ted at point int onal 2-image st ed at a density of imaging with G and 3 cm. Tho des and roofs, m aerial photog tervals of 10 to tereo overlaps. f 1 point per pix Ground Samplin etherlands) elgium, se densities are street signs and graphy no long o 20 pixels asso Current point xel taking advant tage of a 10-clouds get ociated with ger is being d suspended desirable to ng Distances acquisi ition of very de ense point cloud ds at 100 pts/m m² and up to offer in Digital approac data-dr forms a forms [ driven preferre planar one ro reconst density Distanc point id Th nstant access to Surface Mode ches for 3D bu riven. Model-dri as presented in [1], [2]. Comple methods. Theref ed [3], [4], [5], roof elements. oof plane. A r tructed building y of 25 pts/m 2 w ce of 20cm. It q dentification of 1 he progress in d o point clouds a el (DSM). The uilding reconstru iven methods us figure 7 and m ex roofs typical fore data-driven [6], [7], where Ideally, each d recent paper [8 g models using which correspon quotes a total st digital aerial cam meras has made possible the 10-15cm. and an easy tra two fundamen uction are mode se a predefined match the data a lly are beyond s n roof reconstruc a roof gets seg data-plane descri 8] assesses the LiDAR. It quo nds to a Groun andard deviation ansition to a n for corner nd Sampling otes a point quality of ibes exactly mented into ction is often such model-gainst those list of roof el-driven or tal LiDAR-Th based o he state of the ar on airborne LiD rt methods of int DARs (Light Det terpreting buildi tection And Ran ing roofs are nging). They

inds the solution tional that is usu n term copes w ess properties of n to be similar is functional is therefore well su ce-wise planar su n the robust Hu TGV. The stren tair-casing often noise model of r rm to the data a l" is obtained.

Figur datas shows ra 2.2 P

	er-ed		min
	ny
		Ω	… Image doma
	ng ial of	Κ f 1 … … observed ran … single observ u … … sought soluti α … … smoothing fa
		ε,	δ … Parameter of
	sic est cal pe	Th he main property piecew wise polynomial propert ty to be convex optimal l. For the appro
		the TG GV regularizatio
		approxi imated by pie
	ng ork	norm. combin nes TGV regular
	nd ng	min ,
	get tal get nd ual	Ap result il of Graz within structur
	on
	on
	try
	his
	is
	all
	we
	3].
	tly
	by
	of
	ori
	nd
	ta.
	for
	gs	Th
		detectio
	uber-L1 norm, th ngth of the Hube n found in oth real range image and regularizatio he er-her es. on	"J-Link RANSA we wil random differen way th
		That m
		the foll
	art of this work fo or
	ided that copies ar re
	advantage and tha at
	first page. To cop py
	edistribute to list s,	Z
		σ
	00.	x i

n | | pplying this me llustrated in Fig z, Austria. In thi the range data re of a roof.

re 2: (a )Shows R set (b) shows ra s range image u ange data (e) sh Plane Detec

		| |
		ain
		nge images
		vation
		ion
		actor (α ≥ 0)
		f Huber norm
		y of TGV this is
		functions of a
		x, which means
		oximation of bui
		on of the secon
		ecewise planar
		rization of secon
		|ε v
		ethod to a typica
		gure 2, taken from
		is image you can
		are minimized
	he smoothed p
	on. This applies
	kage" method
	AC method. The
	ll present a sho
	m sampling to
	nce to RANSAC
	hat neighboring p
	means that if a po
	lowing probabili
	…	nor
	…	heu
	,x j …	sin

RGB image of s nge image with using TGV mod hows detail of ra ction

	|	|
	s that it allows to
	arbitrary order.
	that a solution
	ildings it is suffi
	nd order since t
	r surfaces. Th
	nd order with th
	|	|
	al roof produces
	m the test datase
	n see that outlie
	by maintaining
	oint clouds are
	s to façades as w
	introduced by
	e approach is de
	ort summary h
	o generate mo
	C is that minim
	points are select
	oint x i has alread ity of being draw
	1
	0
	rmalization cons
	uristically chose
	ngle observations

single building hout using TGV del (d) shows de ange data using

	o reconstruct
	It has the
	n is globally
	icient to use
	they can be
	his method
	he Huber-L1
	|
	a smoothed
	et in the city
	rs and noise
	g the global
	e now the inpu
	well as to roofs.
	[14] that res
	scribed in [14] i
	ere. The proces
	del hypotheses
	mal sets are cons
	ted with higher
	dy been selected
	wn:
	stant
	n constant
	s

of our test V model (c) etail of raw g TGV.

		RANSAC i
	th hat is in our cas
	w with the characte
	f fit the point. Upo
	e each point a pre
	th hat belong to th
	m meaning they are
		A tailored a
	to o the same mod
	m minimum pairwi
	tw wo preference se
	w where A and B a
	th he two sets and
	li inked together
	r	epresented as s
	p plane detection f
	F
	(
	2
	e
	d
	p
	p	ut to plane
	A	We use the
	p	sembles the
	th	in detail, but
	d	ss starts by
	w	s. The big
	c	structed in a
	s	probability.
	h	d, that x j has

Table es

 es

		e 1. Different ro
	es
	f Pitch
	ntation -
	ses
	o
	acency
	es
	f Pitch
	ntation -
	ses
	o
	acency
		Gable roof
		2
	f Pitch	> 0 degree (similar)
	ntation	1x is -1 (dot produc
	ses	all 2 planes have low
	o	same ratio
	acency	1 neighoring
		Hip roof
	es
	f Pitch
	ntation
	ses
	o
	acency
	es
	f Pitch
	ntation
	ses
	o
	acency
	es
	f Pitch
	ntation
	ses
	o
	acency
		M
	es
	f Pitch
	ntation
	ses
	o
	acency
	es
	f Pitch
	ntation
	ses
	o
	acency

Table 3 . Different roof shapes

 3

		roof planes	smaller structures
	total	614	738
	detected	567	612
	Detection rate [%]	92	83

Table 4 . Evaluation of roof shape detection;

 4

We expect that a focus will be needed next on the analysis of the detailed extrusions, sometimes intrusions, on roofs. These concern chimneys, dormers, sky lights, terraces etc. Success with those details will reflect back on an improvement of the roof analysis and type assignments.


Philipp Meixner
email: meixner@icg.tugraz.at

Franz Leberl
email: leberl@icg.tugraz.at

Mathieu Brédif
email: mathieu.bredif@ign.fr

3D Roof Details by 3D Aerial Vision

Virtual cities in a 3D GIS will not be complete without the details of roofs with chimneys, dormer windows, skylights. We contribute a method of extracting such details from digital large format aerial photography. The dense point clouds produced by a photogrammetric process produce major and minor plane surfaces of a roof and enter into a classification of its superstructures. In real city data with a total of 1312 superstructures the proposed automated process finds 1024, thus achieving success at a rate of 78%.

Introduction

We observe the emergence of virtual cities as the 2D geographic information system GIS morphs into a 3D GIS. This is being greatly helped along by innovations in sensors, computing, storage, software so that data can be created at low cost per building and per unit area. Innovations in the applications infrastructure with the Internet and smart telephony increase the applicability of 3D detail.

Advances in digital aerial cameras are the source of lowcost very dense point clouds that are necessary to generate 3D building models. "Very dense" refers to clouds of points at a density of 1 to 2 pixels in the source imagery. This has become possible through new algorithms in combination with multi-view geometry and high overlap imagery. In the process, 3D city modeling has become a lively research area within the photogrammetric community [START_REF] Haala | An update on automatic 3d building reconstruction[END_REF][START_REF] Kim | Building roof modeling from airborne laser scanning data based on level set approach[END_REF][START_REF] Ahn | Object space matching and reconstruction using multiple images[END_REF]. Whereas in the past city models often have been built for visualization purposes new applications have information needs beyond visual characteristics. This implies that the geometric information be augmented by semantics and topology to help with thematic queries, analysis tasks, automatic integration, validity checking, or spatial data mining.

Buildings are the most relevant elements of a 3D GIS and are in the focus of considerable research efforts. The detection of buildings and of their footprints, even mapping of the main roof faces, has become possible by automated means [START_REF] Haala | An update on automatic 3d building reconstruction[END_REF].

The required level of detail (LOD) depends on the application. This may range from the Lego-type parallelepipeds denoted as LOD-1 via models with general roof shapes as LOD-2 to building models with windows and roof details as LOD-3 and on to LOD-4 to include the building interior [START_REF] Thomas | CityGML -OGC Standard for Photogrammetry[END_REF] (see figure 1). Figure 2 shows a French LOD-2 city model augmented with photo texture. In its most sophisticated form, each building, tree, street detail, bridge and water body is modeled in three dimensions, details such as windows, doors, fac ¸ade elements, sidewalks, manholes, parking meters, suspended wires, street signs etc. exist as separate objects. For LOD-2 to LOD-4 the roof and its extrusions and intrusions are of interest.

This paper contributes a method to map a roof's details as they extrude from, or sometimes intrude into, the major roof planes. The paper also addresses skylights as an additional element for the degree of development of a roof. The novel method uses high-resolution vertical aerial photography to segment and classify roof details, so that one obtains the type roof architecture, the number and location of chimneys, dormer windows and skylights. We segment the roofs into major roof planes, minor roof planes and planes associated with superstructures. The major roof planes provide information about the architectural roof style; another application would be the examination of the roof's suitability for the installation of solar panels. Of particular interest in our case are superstructures. We divide these into dormer windows, chimneys and other structures. Especially the existence of dormers and of skylights is of great interest for the level of use of a building's attic.

Experiments use aerial photography of an urban core with 186 buildings and at a GSD of 10cm. We show that our initial approach maps dormers, chimneys and skylights at a rate between 76% and 81%. We see significant avenues for improvement in the source data as well as algorithms to increase that rate of success in the future.

Approach

In order to analyze roofs, one will first want to separate the given input data per building. The aerial imagery with its derived 3D point clouds and classified land surface elements is being merged with the cadastral property data. The result consists of each individual property and the area occupied by a building. Its outline is from the image classification and the 3D point clouds. From the building one proceeds to the fac ¸ades: building footprints become fac ¸ade baselines and they in turn serve to refine the building's roof outlines. This has been developed by [START_REF] Meixner | Characterizing Building Fac ¸ades from Vertical Aerial Images. The international archives of photogrammetry[END_REF] and is used for this work.

Roofs and their superstructures now need to get mapped using the building's point cloud and image segments. The process consists of five steps (Figure 3). First is the smoothing of the noisy digital surface model (DSM) using total generalized variation TGV presented in [START_REF]Rainbow of Computer Science: Dedicated to Hermann Maurer on the Occasion of His 70th Birthday[END_REF]. Second is the extraction of all plane roof segments using a method introduced in [START_REF] Toldo | Robust Multiple Structures Estimation with J-Linkage[END_REF] and resembling the RANSAC algorithm for plane detection, however with the consideration of neighborhoods. Third, each plane surface patch gets labeled as a major, minor or superstructure plane. This initially uses the DSM point cloud and then refines the segmentation by incorporating the RGB-image data. In a region growing approach, plane segments get merged into larger surfaces, or are set aside for further analysis.

A fourth process element is the search for skylights in the major and minor roof planes using a template matching method in the form of fast directional chamfer matching introduced by [START_REF] Liu | Fast directional chamfer matching[END_REF].

The fifth step is the interpretation of the data and assignment of labels to the isolated data elements and collected list of features. The roof gets an overall attribution to a specific architectural style, the "left-over" data are the basis for a classification into dormers, chimneys and sky lights.

DSM Smoothing

Photogrammetrically measured elevation data (range data) are noisy. At a pixel to multi-pixel level, this will obstruct any search for plane surface patches. For this reason the 3D point clouds need smoothing. The filtering of elevation measurements is a traditional function of photogrammetric work in the form of an approximation and interpolation of terrain elevation grids from manually measured surface points. In the current application, we have very dense data and need a filter that preserves sharp surface discontinuities and small structures while producing smoothness within the roof. A recent innovation is "total generalized variation" TGV introduced by [START_REF]Rainbow of Computer Science: Dedicated to Hermann Maurer on the Occasion of His 70th Birthday[END_REF]. It satisfies the requirements of the roof surface analysis and is available in a GPUimplementation for very fast throughput.

Plane Detection

Roof planes get detected in the smoothed point cloud. Of the many different methods available for the task, RANSAC plane detection has become a standard, in particular in the LiDAR literature [START_REF] Brenner | Towards Fully Automated 3 D City Model Generation[END_REF][START_REF] Schnabel | Efficient RANSAC for point-cloud shape detection[END_REF][START_REF] Ying | Plane Detection in Point Cloud Data[END_REF]. Its principle is well explained in [START_REF] Mullen | Manual of Photogrammetry. Fifth Edition[END_REF][START_REF] Fischler | Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[END_REF]. A limitation of RANSAC results from its disregard for neighborhoods; it treats all points the same without considering that a point might be near another. For that reason [START_REF] Toldo | Robust Multiple Structures Estimation with J-Linkage[END_REF] has introduced a variation on RANSAC that incorporates neighborhood relations. It starts by random sampling to generate model hypotheses. Minimal sets are constructed in a way that neighboring points are selected with higher probability. That means that if a point x i has already been selected, that x j has the following probability of being drawn:

P (x i |x j ) = 1 Z exp - xj -xi 2 σ 2 if x j = x i 0 if x j = x i ( 1
)
where Z is the normalization constant, σ is a heuristically chosen constant, x i and x j are single observations. After the creation of all hypotheses, a preference set of preferred hypotheses is created for each point. Points belonging to the same structure have a similar preference set, thus they are close in the conceptual space. To find the models the method uses an agglomerative clustering procedure, where at each step the two clusters with the minimum pairwise distance are merged. This distance reaches from 0 (identical sets) to 1 and just elements are linked together whose preference sets overlap. Figure 5 shows the result of the plane detection for one building of our test dataset. The comparison of a plane with the point cloud produces a measure of accuracy. We find that the test data have elevation noise of ±12cm; this is to be related to the GSD at 10 cm.

Classification

The roof plane detection is the basis for a classification into major planes, minor planes and superstructure planes. We further divide the category superstructures into chimneys, dormer windows and other structures. Our classification workflow, illustrated in figure 6, consists of an initial and a refined classification. The initial classification analyzes every plane segment to determine if it is linked to any other segment to build a larger "region". Then the size of the resulting region or assembly of plane segments gets considered.

Depending on the size of the regions with respect to the overall size of the roof we assign each region to an appropriate category.

A secondary analysis addresses the smaller planes and superstructures. Depending on their height values with respect to the neighboring pixels these regions are classified as part of a smaller plane segment (regions without height continuities at the borders), or of a superstructure or are eliminated entirely. To achieve meaningful results we distinguish between height discontinuities at the edges of the roof and within the roof by using the information about a building from the building classification.

The refined classification for the superstructures uses the DSM and the RGB-values for a more accurate and robust segmentation of the roof parts as proposed by [START_REF] Koivunen | Combined edge-and region-based method for range image segmentation[END_REF]. This is region growing with seed pixels for every region from the initial segmentation. The seed pixel locations are the centroid of each segment. The region is iteratively grown by comparing all unallocated neighboring pixels to the region. The difference between a pixel's intensity value and the region's mean is used as a measure of similarity.

The pixel with the smallest difference measured this way is allocated to the region. This process stops when the intensity difference between region mean and new pixel becomes larger than a certain threshold.

The classification of the single regions is performed using area, geometric form and height discontinuities at the region's borders.

For the example of chimneys one postulates that on all 4 edges of the region are height discontinuities and that the maximum height is not lower than the height of the roof's ridge. Dormer windows have height discontinuities on at least three edges. Moreover their area is larger than the chimney's and the geometric form is more "quadratic" than elongated. Chimneys have usually smaller and narrower forms with a maximum width of 50cm. In a last step we approximate the single chimneys by best fitting rectangles. Figure 7 shows the different generalized segmentation results for two example buildings.

Template Matching

A major question of roof analysis addresses the use of the attic. The existence of dormer windows strongly indicates that the attic has been extended. However, the absence of dormers does not indicate that the attic has not been extended. In lieu of dormers there might be skylights.

Skylights can be detected by matching a rectangular skylight template with an edge image computed from the aerial photography over the area of the major roof planes. The match is scale and rotation variant. Fast directional chamfer matching as proposed in [START_REF] Liu | Fast directional chamfer matching[END_REF] improves the traditional alignment between two edge images by incorporation of edge information into the matching costs. This improves the robustness of chamfer matching in the presence of background clutter. This method augments the chamfer distance with an additional cost for orientation mismatch which is given by the average difference in orientations between template edges and their nearest edge points in the query image. Instead of an explicit formulation of the orientation mismatch, the chamfer distance is generalized to points in R 3 for matching directional edge pixels. The directional cham-fer distance score is given in [START_REF] Liu | Fast directional chamfer matching[END_REF] by

d DCM (U, V ) = 1 n ui∈V min vj ∈V |u i -v j | + λ|φ(u i ) -φ(v j )| λ .
. . weighting factor between location and orientation terms; u i . . . set of template image edge map u i . . . set of query image edge map φ() . . . direction term Figure 8 shows results for the detection of skylights on building roofs.

Roof Meta-Interpretation

A meta-interpretation of the roof concerns its extended or not. This is based on the number and location of chimneys, the use of skylights and dormers. These may be of interest as escape routes in the event of a disaster. Future work might address the existence roof terraces, flat roofs with their elevator shafts and air conditioning compressors to interpret the uses of the building. This is interesting for urban planning, real estate development and transactions or it could be used for value assessments for property tax assessments. Figure 9 illustrates a segmented building roof with the conclusion whether the attic is living space or not.

Experimental Results

The test area covers 400m x 400m near a European urban core with 186 different buildings. The vertical aerial photography was taken with a GSD of 10 cm, 80% forward-, 60% side-overlap.

Ground truth was obtained by a manual interpretation of the 69 extended attics in the 186 building (see table 1). The extended attics are characterized in 20 instances by dormer windows, in 17 cases they have just skylights and 32 have both dormers as well as skylights. Additional ground truth was obtained manually for all major and minor planes, dormer windows, chimneys and skylights (see table 2). Part of the experimental work was to understand the effect of the smoothing operation. It not only eliminates outliers, but improves the throughput of plane detections by a factor two since the smoothness of the point cloud improves the size of the plane segments.

A differentiation between major and minor or smaller planes is heuristic and a function of architectural customs in an area. The threshold can be assigned as a function of every building's footprint and the size of the individual plane segments. But some smaller planes will get erroneously assigned to the major plane class and vice versa.

Table 3 summarizes the achieved results. Detected were 446 major and 198 smaller planes, 186 dormer windows, 552 chimneys and 574 skylights. Of the total of 644 planes, 579 were detected, thus achieving a detection rate of 90%. It was somewhat more successful to detect major planes than minor ones, with success rates at 92% and 86%.

Current limitations of the approach were found in cases where plane segments have very similar pitches and are thus merged erroneously into one plane when they should be kept separate. Another limitation exists with curved roof surfaces that exist in some regions extensively, such as in France, and they may also be found in modern buildings. In these cases the attempt at fitting roof planes produces many small segments and a failure of the approach. A will be needed that addresses curved roofs. Of 738 superstructures, 571 were detected. This corresponds to a detection rate of 77%. The dormer window detection rate was at 81%, the chimneys' at 76%. Applying these superstructures to an interpretation of extended attics delivers success at a rate of 82%.

Misclassifications of superstructures occurred in the case of very complex roof shapes with non-allocatable roof structures, particularly when surfaces were curved. Since our approach had not been considering the existence of roof gardens, it failed in those cases.

It is thus obvious that further work is needed to address curved roofs and roof terraces.

Conclusion

We contribute a novel use of vertical aerial images to describe and characterize building roofs as a new content in a 3D GIS. Since the aerial photographs offer a very high overlap, they produce very dense 3D point clouds. These in turn support, jointly with the RGB-content of the images, the mapping of major roof planes and of roof superstructures. The rate of correctly detecting roofs, dormer windows, chimneys and skylights are at 76% to 81%. This in turns permit one to assign to a "normal" building a label of "extended attic" and assign specific architectural roof styles.

LiDAR today is the workhorse for the production of 3D point clouds, and research in building reconstruction is often considering LiDAR as the major data source. However, a search for LiDAR-literature addressing roof superstructures came up empty. We will therefore argue that vertical aerial photography is a valid data source for mapping building roofs, and that the same cannot be said at this time for LiDAR.

Our future work therefore will continue with vertical aerial imagery. Improvements of algorithms will have to address curved roofs and roof terraces, and will have to broaden the algorithmic basis to include more image-derived features to augment the point clouds.

A differentiation between major and minor or smaller planes is heuristic and a function of architectural customs in an area which makes the algorithm less robust. In order to solve this problem in future work we want to enter this information as prior knowledge of an area.

Very importantly, a widening of the range of architectural styles will be needed to go from coastal resort environments via historical small towns and mountainous urban areas to modern urban zones with skyscrapers and industrial facilities in various regions of the World.

Figure 1 .

 1 Figure1. CityGML levels of details[START_REF] Brédif | Modélisation 3D de bâtiments : reconstruction automatique de superstructures de toits et recalage cinétique de toits polyédriques prenant en compte la topologie[END_REF]

Figure 2 .

 2 Figure 2. 3D model of a detail of the 12th district of Paris, GSD 15cm [Courtesy: Laboratoire MATIS, IGN France]

Figure 3 .

 3 Figure 3. Sequence of the five major processing steps

Figure 4 Figure 4 .

 44 Photogrammetrically measured elevation data (range data) are noisy. At a pixel to multi-pixel level, this will obstruct any search for plane surface patches. For this reason the 3D point clouds need smoothing. The filtering of elevation measurements is a traditional function of photogrammetric work in the form of an approximation and interpolation of terrain elevation grids from manually measured surface points. In the current application, we have very dense data and need a filter that preserves sharp surface discontinuities and small structures while producing smoothness within the roof. A recent innovation is "total generalized variation" TGV introduced by[START_REF]Rainbow of Computer Science: Dedicated to Hermann Maurer on the Occasion of His 70th Birthday[END_REF]. It satisfies the requirements of the roof surface analysis and is available in a GPUimplementation for very fast throughput.Figure4is taken from our experiments. It illustrates that outliers and noise in the elevation data are minimized, yet the global structure of a roof is maintained.

Figure 5 .

 5 Figure 5. Axonometric view of (a) point cloud of building roof, points in red; (b) point cloud and detected major planes in green. Note the intersection line and points belonging to the planes in black (c) point cloud and detected minor planes in blue. Note intersection line and points belonging to the planes in black; (d) Side view of point cloud and major planes; at right is an enlarged detail showing standard deviation between points and plane at ±12cm.

Figure 6 .

 6 Figure 6. Proposed classification processing steps

Figure 7 .

 7 Figure 7. Classification of two test buildings; (a) major roof planes (in red); (b) smaller roof planes (in yellow); (c) dormer windows (in blue); (d) chimneys (in green);

Figure 8 .

 8 Figure 8. Left: original roof image; Right: detected skylights (marked in green) on a building roof.

Figure 9 .

 9 Figure 9. Left: original roof image; Right: detected skylights (marked in green) on a building roof.

Table 1 .

 1 Ground truth for 69 extended attics in 186 buildings. Some attics have only dormer windows or skylights, and some have both.

		Dormer	skylights	both	total
		windows
	number	20	17		32	69
		Major	Smaller	Dormer	Chimneys	Skylights
		planes	planes	windows
	number	446	198	186	552	574

Table 2 .

 2 Ground truth for the major and smaller planes, dormer windows, chimneys and skylights in the 186 buildings of the test area.

Table 3 .

 3 Experimental results for the building roof segmentation

		Major	Smaller	Dormer	Chimneys	Skylights
		planes	planes	windows
	Total	446	198	186	552	574
	number
	Detected	409	170	151	420	453
	segments
	Detection	92	86	81	76	79
	rate (%)


K Houari
email: hk_houari@yahoo.fr

Larbi Ben M'hidi

Oum El Bouaghi

M K Kholladi
email: kholladi@yahoo.fr

Spectral clustering and dimensionality reduction applied to Content based image retrieval with hybrid Descriptors

Keywords: image retrieval, Sift, clustering, texture, Nyström. I

published or not. The documents may come

Spectral clustering and dimensionality reduction applied

to Content based image retrieval with hybrid Descriptors

Introduction

Algorithms of spectral classification for the unsupervised analysis of data offer a very effective tool for the exploration of the data structure. Methods of Clustering [START_REF] Chung | Spectral graph theory[END_REF][START_REF] Dy | Feature selection for unsupervised learning[END_REF] have been used in various contexts and such disciplines 'dated mining', research of documents, image segmentation and classification of objects. The objective of clustering methods is the classification of objects on the basis of the criteria of similarity or chosen dissimilarity where groups (or classes) are a set of similar objects.

The Crucial aspect in the classification is the representation of models and the distance of similarity. Every model is usually represented by a set of descriptors of the studied system. It is important to note that a good choice of model representation can increase performances of the classification. The choice of the set of descriptors depends on the system. The system of representation being fixed, it is possible to choose the suitable similarity measure between models or objects. The most popular measure of dissimilarity for a metric representation is the distance, as Euclidian distance. [START_REF] Hagen | New spectral methods for radio cut partitioning and clustering[END_REF].

Techniques of Clustering can be divided globally in two categories: Hierarchical, Partitioning. Hierarchical Techniques of clustering [START_REF] Chung | Spectral graph theory[END_REF][START_REF] Kannan | On clusterings: Good, bad and spectral[END_REF][START_REF] Luxburg | tutorial on spectral clustering[END_REF] are capable to find the structure that is then divided in substructure and so forth recursively .the result is a hierarchical structure of groups that is called 'dendrogram'. Methods of clustering 'Partitioning' try to get a unique partition of data without the other under-partitions as in hierarchical algorithm processes and are based always on the optimization of an appropriated objective function. The result is the creation of a hyper-surface separation between classes. The Standard methods of partitioning (ex., K-means, fuzzy c-means, SOM and neural gas) that use two centroides are unable to separate in the desired manner the two sets. The use of several centroides can solve the problem but by generating a complex description of a simple whole of data. For all these reasons modifications and a new approach were introduced.

Among the range of modifications we can mention the varieties of fuzzy c-means [START_REF] Mackay | Information theory, inference, and learning algorithms[END_REF], but the major problem is that information on the forms of the clusters must be introduced as a preliminary. Recently, some methods of clustering which produce a nonlinear separation of hyper surfaces between the clusters were proposed. Theses algorithms can be divided into two great families: Several methods of clustering were modified by incorporating the concept of kernels (ex: k-means, fuzzy c-means, SOM and neural gas). The use of the kernels makes it possible to implicitly represent the data in a space of great dimension called space of description; while carrying out a linear partitioning of this space of descriptors, the result of the partitioning of the space of input will be non-linear Methods of Spectral clustering are based on concepts of the spectral theory of graphs. The basic idea is to construct a graph either weighted from data in entries. Each vertices or nodes represents a pattern (object) and every weighted edges or lines holds only in account the similarity between two patterns. In this case the problem of clustering amounts to a problem of graph portioning, what is treated by the spectral graphs theory. The heat of this theory is the calculation of the eigen values of the Laplace matrix of the weighted graph obtained from data. There is a narrow relation in fact between the second smaller value of Laplace and the partitioning of graph [START_REF] Meila | Comparing clusterings[END_REF][START_REF] Meila | Learning segmentation by random walks[END_REF].

Lately, the interest for the reduction and the treatment of high dimension data turned toward the spectral clustering methods, because of numerous successes [START_REF] Lafon | Diffusion maps and geometric harmonics[END_REF]. These methods use the spectral content of a similarity matrix (distance between each pair of data) to achieve the reduction and the partition of a data. More specifically, the eigenvectors are seen like a tool providing a representation of data in a space where it is well separated and can be grouped easily, and the eigen values having the possibility to capture the conceptual features and perceptual of a set of data. This last mathematical property has not been taken practically ever in account for the assessment of performances of algorithms of the clustering spectral In this article the first section describes the SIFT descriptor as well as the texture ones and in the second section we describe the spectral method of global diffusion applied for reducing the space representation. Conclusions and recommendations for the future works are presented in the last section.

II. Extraction of SIFT points.

During these last years, the invariant descriptor to the Scale transformations "Invariant Features Transform (SIFT) feature" [START_REF] Verma | comparison of spectral clustering algorithms[END_REF] received a lot of attention. It has been demonstrated in a recent survey [START_REF] Ward | Hierarchical grouping to optimize an objective function[END_REF] that he gives better results than other descriptors. Some minor modifications on the descriptor initial SIFT have been brought (PCA-SIFT [START_REF] Newman | Random graph models of social networks[END_REF], however Gloh-Sift [START_REF] Ward | Hierarchical grouping to optimize an objective function[END_REF], but the gain is not always obvious in all experimentations. Thus, in our present survey, we are interesting to the initial SIFT. The SIFT method is used to extract the invariant interest points to transformations and scale from image in order to matching it with another image with different point of view of an object or a stage. The Descriptor is invariant to scale and rotation and he has been shown that he procures a robust matching through a certain degree of refine distortions, of changes of view in 3D, addition of noises, and of illumination changes. Descriptors are highly distinctive; in the sense that only one descriptor can be matched correctly with a big probability with a big database of several other image descriptors.

The algorithm consists in four main stages: The first stage identifies the localizations and the scales which can be assigned under various points of sights of the same object. The Detection of the localizations which are invariant with the scaling of the image can be achieved by the search of the points which are stable through all the scales, by using a continuous function of the space of scales. The only possible core of spaces of scales is the Gaussian function.

Of that, the space of the scales of images is defined like the function: L(x, y, σ), which are produced from the convolution of the variable scale-Gaussian G(x, y, σ), with the image of Input I(x; y), i.e.:

Where * is the operation of convolution and

The points of interests are detected by using the extreme in the space of scales in the function of Gaussian difference D convoluted with the image: I(x; y):

Where k is a constant factor multiplying which separates two close spaces. With an aim of detecting the local maxima and the minima of: , each point is compared has its eight neighbors in the current image and has its new neighbors of the image of scale to the top and below. It is selected so only it is higher or lower than all its neighbors. Once the point of interest candidate was found by comparing the pixel has its neighbors; the following stage consists to make a filtering detailed in the vicinity of the point to detect the localization, the scale, and the ratio of curve. This information makes it possible to reject the points which have a weak contrast (and which is sensitive to the noise) or are located on edges. A quadratic function 3D is applied to the local points Where D and its derivatives are evaluated at the simple point . The localization of the extrema is obtained by considering the derivatives compared to X, which gives us: Who is a linear system 3x3, easy to solve.

The value of the function at the extrema is:

Who is very useful for the unstable rejection of the extreme with a weak contrast? At this stage, the algorithm rejects also the interest points which have slightly defined nodes, i.e.: the points which have in the function of Gaussian Difference a broad curve around an edge with low curve in the perpendicular direction. By assigning a consistent orientation, based on the properties of the local image, the descriptor of the interest point can be represented relative with this orientation by ensuring however invariance to the rotation of the image. For each simple image, on this scale, the magnitude of the gradient, and the orientation, are pre-calculated by using the differences of pixel:

The histogram of orientation is formed starting from the orientations of gradients of the simple points inside the area around the key point (interest). Finally the description of the point of interest SIFT is made by calculation magnitude of the gradient and the orientation of each simple point of image in an area around the localization of the point of interest. These points are balanced by a Gaussian window and then accumulated in a histogram of orientation of 8 elements (directions) which synthesizes contained 4x4 under areas, with like length of each column, the sum magnitudes of gradient close to this orientation inside the area. The size of the final descriptor is of 4x4x8=128 and the procedure of standardization is applied to the descriptor to allow Invariance with the changes of illumination

III. Texture description

Each image is treated to extract the descriptors of texture by employing the most popular methods of extraction of texture descriptors , which are 1) spectral filtering of Gabor [START_REF] Hagen | New spectral methods for radio cut partitioning and clustering[END_REF], 2) laws of energy filtering [ 4.5 ], and the 3) ' Wavelet transform'. These methods were largely used by researchers and are carried out very well for various tasks of segmentation and classification of image. The 'Wavelet transform' used in this study offer space information, of frequency and very rich scale for the descriptors of texture and is a robust and effective method for the image processing.

IV. Dimension Reduction Techniques.

We present in this section a panorama on the traditional methods for dimension reduction, and synthetically the global methods based on the spectral decomposition. We conclude by an evaluation of the contributions of these approaches within the meaning of the metric properties. Reducing a dimension means to find a configuration , which draws up the maps of data of the starting space X with their original description such as: Thus, the configuration will be mentioned like a fixing of the space of high dimension X in another lower space of dimension and more expressive Y: Among these configurations, we distinguish the linear methods and the nonlinear methods.

m x x x X ..., , , 2 1 ,

IV.1. The Linear methods.

For the linear methods, we find the algorithm of analysis in principal components (ACP), consisting in projecting the samples on the axes of maximum variance of the data. In other words, the ACP aims at identifying the linear dependences subjacent with a stochastic observation (random) in order to obtain a description of lower dimension. The use of this algorithm is legitimate if the data observed are roughly located on a linear variety. In the same method, one finds the algorithm of multidimensional positioning (MDS) which carries out a linear reduction of dimension indirectly, starting from square distances. Clearly, multidimensional positioning (MDS) makes it possible to build a configuration of m not in starting from the distances between m objects with which these points are associated. In this context, one does not observe any more the points directly in space of origin but rather the m (m-1)/2 distances corresponding to these points. The distances provided to MDS should not necessarily be Euclidean and can consequently be to represent by the other metric ones.

Unfortunately, conflicts of these methods resident in the fundamental character of spaces of data observed in nature which very often exhibit highly nonlinear characteristics. If it is supposed that the data have an intrinsic dimension 'd' weaker than the dimension of observations (n) and if the data are rather drawn from a nonlinear variety, the ACP will be unable to express the characteristics of this variety and consequently will not be able to create a representation in lower dimension respecting the properties of the variety. In the same order of idea, if the distances provided to MDS are the Euclidean distances, this algorithm will not be able to either generate a positioning of the adequate points to the nature of the variety.

IV.2. The Nonlinear methods.

Deficiencies of the linear methods involved the development of the configurations being able to approximate the data by nonlinear varieties. The kernels provide nonlinear measurements of similarity easily being able to be incorporated in already existing linear algorithms. Due to this, spectral methods of estimation of nonlinear varieties where introduced. These algorithms are based, for a set of vectors of entry on a matrix of similarity , and drive to calculate its principal's eigen vectors and eigen values. The representation in small dimension of every vector xi in entry is gotten while using the first eigenvectors of . (Isomap, LLE 'Locally Linear Embedding Algorithm)). The ISOMAP method builds a graph from the K nearest neighbors and then performs Multi-Dimensional Scaling MDS (Michael Lee).

V. Spectral Clustering. V.1. Notations. The notation for spectral graph theory foots on graph theory and appeals to intuition. Except for minor differences in the names of matrices, variables, and counters, this notation seems pretty standard.

Fig.1: Example of graph

In This section we present briefly the mathematical notations of the algorithms that will be presented.

A graph or undirected graph G can be written as an ordered pair G := (V, E), where V is a set of vertices or nodes, and E is a set of pairs (unordered) of distinct vertices, called edges or lines. The vertices belonging to an edge are called the ends, endpoints, or end vertices of the edge. [START_REF] Wikipedia | Degree matrix -wikipedia, the free encyclopedia[END_REF] The adjacency matrix (also similarity matrix or weight matrix) of a finite directed or undirected graph G on n vertices is the n*n matrix where the no diagonal entry is the number of edges from vertex i to vertex j, and the diagonal entry is either twice the number of loops at vertex i or just the number of loops (usages differ, depending on the mathematical needs; this report is not concerned with reflexive connections). The adjacency matrix is symmetric for undirected graphs. [START_REF] Wikipedia | Adjacency matrix -wikipedia, the free encyclopedia[END_REF] In the following, we assume w ij = w ji >= 0.

Given A € V, its complement, V \ A will be denoted as A. i € A shall be shorthand for indices of will denote the number of vertices in A. vol (A) measures the size of A by the weights of its edges, i.e. The degree (or valency) of a vertex is the number of edge endpoints to the vertex. Loops are counted twice. The degree matrix D for G is a n × n matrix defined as [START_REF] Wikipedia | Degree matrix -wikipedia, the free encyclopedia[END_REF].

Intuitively, a subset A € V is connected, if paths between any two points in A need only points in A. A is called connected component with respect to

, if A is connected, and there are no edges between vertices in A and A. Subsets A 1 , A 2 ,…. A k represent a partitioning of V, if, for all 1<= j, x >= k, A i ∩ A j =Ф. And (Usually also defined nonempty).

V.2. Clustering.

Generally speaking, clustering means partitioning of a graph, so that the edges between different groups have low similarity (low distance) and the edges within groups have high weight (low distance). The first requirement for the partitioning can be stated as the minicut criterion, which has to be minimized:

Or following the minicut requirement, often only a little group of points is isolated. For this reason, tweaks have been introduced:

As for the second requirement, within-cluster similarity means optimizing Within-cluster similarity is maximized if is small and vol (A) is big. Therefore, Ncut implements the second criterion. Ncut can be interpreted as cutting through edges rarely transitions by a random walk. RadioCut, by maximizing |Ai|, as within-cluster similarity is not related to the number of vertices in A, does not implement this requirement. [START_REF] Luxburg | tutorial on spectral clustering[END_REF]

V.3. Laplacians and their properties

The spectral algorithms presented here foot on eigenvectors of Laplacians, which are a combination of the weight and the degree matrix. For a more thorough and broader discussion of mathematical properties of Laplacians refer to [START_REF] Mohar | Some applications of Laplace eigenvalues of graphs[END_REF] and [START_REF] Chung | Spectral graph theory[END_REF]. The (unnormalized) graph Laplacian is defined as For a graph G and its admittance matrix L with eigen values λ 0 ≤ λ 1 ≤ …. ≤ λ n-1 , these properties are important, in the context of spectral clustering. [START_REF] Wikipedia | Laplacian matrix -wikipedia, the free encyclopedia[END_REF].

• L is always positive-semi definite (∀ i λ i ≥ 0).

• The multiplicity of '0' as an eigen values of L is the number of connected components of G.

• λ 1 is called the algebraic connectivity.

• The smallest non-trivial eigen values of L is called the spectral gap.

Noteworthy is furthermore, that matrices with identical non-diagonal elements have the same unnormalized Laplacians. The normalized graph Laplacian is defined in two distinct ways: Some properties are:

• L rw and L sym are positive semi-definite and have n nonnegative real-valued eigen values 0= λ 1 ≤ …. ≤ λ n • The multiplicity k of the eigen values 0 of both L rw and L sym equals the number of connected components A 1 , . .. , A k in the graph.

Refer to [START_REF] Chung | Spectral graph theory[END_REF] for an in-depth discussion of normalized Laplacians.

V.4. Clustering algorithms

Spectral clustering became popular with, among others, [START_REF] Shi | Normalized cuts and image segmentation[END_REF] and [START_REF] Ng | On spectral clustering: analysis and an algorithm[END_REF]. Its efficiency is mainly based on the fact that it does not make any assumptions on the form of the clusters. This property comes from the mapping of the original space to an Eigen space. Algorithms differ basically in the number of eigenvectors they use for partitioning.

Algorithms can be categorized based on the number of eigenvectors they use: [START_REF] Verma | comparison of spectral clustering algorithms[END_REF] • One eigenvector -recursively uses a single eigenvector on partitions (recursive).

• Many eigenvectors -Directly computes a multi-way partition of the data.

• Non spectral -Grouping algorithms that can be used in conjunction with multi-way spectral algorithms.

V.5. Spectral clustering algorithms

For the algorithms we assume data points x 1 , . . . , x n and their similarities S is symmetric and non-negative. They are rather similar, except for the different Laplacians they use. The change of representation from x to u with the help of the Laplacians enhances the cluster properties of the data. [START_REF] Luxburg | tutorial on spectral clustering[END_REF]. Algorithms introduced here are unnormalized spectral clustering, ( [START_REF] Shi | Normalized cuts and image segmentation[END_REF], [START_REF] Kannan | On clusterings: Good, bad and spectral[END_REF], [START_REF] Meila | Learning segmentation by random walks[END_REF] .

Unnormalized spectral clustering proceeds as in the following:

Inputs: k, the number of desired clusters, X, and S. -Let be the matrix containing the vectors as columns. -Form the matrix from V normalizing the row sums to have norm 1, that is -For i=1,…..,n, let be the vector corresponding to the i-th row of V.

-Cluster the points with the kmeans algorithm into clusters C 1 ,….,C k .

Output: clusters A 1 ,….,A k with

VI. SIMILARITY GRAPHS.

Given a set of points, x 1 … x n , and their distances not related to the degree), there are several constructions to obtain a graph (i.e. construct W), which are regularly used in spectral clustering.

The -neighborhood graph is the simplest possibility. All connections with distances below a threshold are set to '1'.

i.e. k-nearest neighbor graphs lead to a directed graph. The k-shortest distances from i are connected. In order to make the graph undirected, directions can be ignored, e.g. constructing a k-nearest neighbor graph, then doing either:

.

(Usually this is called k-nearest neighbor graph) or (mutual k-nearest neighbor graph). A fully connected graph results from connecting all points with positive similarity with each other.

VII. CONCLUSION

The spectral algorithms are simple methods simple and efficient for the classification. The preprocessing is an important stage and can help meaningfully to raise results of classification. The choice of a likeness graph can be non trivial and can require preprocessing more extended. However, there is a graph of likeness once, the problem is linear and the spectral methods don't endure the local optimum problem intrinsically. [START_REF] Verma | comparison of spectral clustering algorithms[END_REF], [START_REF] Shi | Normalized cuts and image segmentation[END_REF]. Besides, the objective of this paper is the automatic classification of the input image in a database image , so the determination of the number of k classes, and selections / weight of the different measurements of the weight matrix that permits to refine to the maximum the classification on the robust and invariant descriptors to changes of scales and noises, of this survey, we disqualify RadioCuts because they don't optimize intraclasses likeness, and according to the study of the state of the art as well as advantages and inconveniences of several other algorithms we conclude that algorithms of spectral clustering give some superior results has those of the no -spectral methods, particularly their properties of non restriction to the convex regions of likeness and the hardiness to noises make them more attractive.

  Where

																	n
											i x					.
	To a new space Y where their description is considered
	simplest.
	Y	1 y	, 2 y	,	...,	y m	,	with	:	y i	R	d	;	and	,	d	. n

Algorithm of Unnormalized Spectral Clustering:

						Output: clusters A 1 ,….,A k with
						Algorithm of Normalized Spectral Clustering:
						Input: Similarity matrix S € R nxn , number k of clusters
						to construct
						-Construct a similarity graph by one the way
						described in section 5.
						Let W be its weighted adjacency matrix.
						-Compute the unnormalized Laplacian L.
						-Compute the first k eigenvectors v 1 ;……,v k of the
						generalized eigenproblem	.
						-Let	be the matrix containing the
						vectors	as columns.
						-For i=1,…..,n, let y i S € R k be the vector
						corresponding to the i-th row of V.
						-Cluster the points	with the k-
						means algorithm into clusters C 1 ,….,C k .
						Output: : clusters A 1 ,….,A k with
						Algorithm of Normalized Spectral Clustering:
						Input: Similarity matrix	, number k of clusters
	• Following the steps in section "similarity graph"	to construct.
	construct W (graph matrix),				-Construct a similarity graph by one the way
	• then calculate 'admittance matrix) L,			described in section 5.
	• then the first k eigenvectors • Let contain correspond to the i-th row of V. as columns and Cluster the points with the k-means algorithm into clusters	-Let W be its weighted adjacency matrix. -Compute the unnormalized Laplacian L sym . -Compute the first k eigenvectors v 1 ;……,v k of L sym.
	Output: Clusters				.
	Note that similar to RadioCut, unnormalized spectral
	clustering does not optimize within-cluster similarity. [6]
	Input: Similarity matrix	, number k of clusters
	to construct
	-Construct a similarity graph by one the way
	described in section 5.
	-Let W be its weighted adjacency matrix.
	-Compute the unnormalized Laplacian L.
	-Compute	the	first	k	eigenvectors
	-Let	be the matrix containing the
	vectors	as columns.
	-For i=1,…..,n, let		be the vector
	corresponding to the i-th row of V.
	-Cluster the points			with the k-
	means algorithm into clusters C 1 ,….,C k .