Soha Farhat

Abed Ellatif Samhat

Samer Lahoud

Bernard Cousin

Hybrid Decision Algorithm for Access Selection in Multi-Operator Networks

Keywords: Access Selection, multi-operator networks, cooperation, resource management, cost function. I

In this paper, we propose a hybrid decision algorithm for the selection of the access in multi-operator networks environment, where competing operators share their radio access networks to meet traffic and data rate demands. The proposed algorithm guarantees the user satisfaction and a global gain for all cooperating operators. Simulation results prove the efficiency of the proposed scheme and show that the cooperation between operators achieves benefits to both users and operators; user acceptance as well as the operator resource utilization and the operator revenue increase.

INTRODUCTION

Wireless Networks are growing rapidly to support the heavy mobile broadband traffic, and to meet the everincreasing user expectations. The operators feel the need to upgrade their networks in order to increase capacity, data rates and coverage, therefore satisfying their subscribers with maximum efficiency. To meet traffic and data rate demands, one approach is to deploy a heterogeneous network [START_REF] Landstrom | Heterogenous Networks-increasing cellular capacity and coverage[END_REF] [START_REF] Johansson | Cost Effective Deployment Strategies for Heterogenous Wireless Networks : doctoral dissertation in telecommunication[END_REF] with advanced traffic management. This cost-effective solution integrates multiple radio access technologies (RATs), such IEEE 802.11 WLANs, UMTS, LTE…, and assumes an efficient Radio Resource Management (RRM) jointly done among the different RATs. It creates a multi-RATs environment under the management of a single operator, and a joint RRM begins by optimizing users association to the different RATs in order to enhance resource utilization, users' satisfaction and overall network performance.

Another approach is to deploy a multi-operator sharing network [START_REF] Johansson | Cost Effective Deployment Strategies for Heterogenous Wireless Networks : doctoral dissertation in telecommunication[END_REF], where competing operators share their radio access networks. This solution seems convenient, when there is insufficient revenue for the operator to deploy multiple networks. Moreover, it helps to avoid the waste of radio resources, when traffic level is lower than planned, and to defeat QoS degradation, when the traffic is higher than expected. In such cooperative environment, when an operator is unable to insure satisfaction constraints to its user, he tries to give him access to the service through another network operator, thus avoiding his rejection. Therefore, operators' cooperation is unavoidable in order to achieve a joint resource management and consequently improve the global system performance and ameliorate operators' profits. The choice of the cooperating operator for the client transfer and the decision process are based on a selection problem, relying on different criterions and depending on specific user/operator considerations.

Most of the existing works have studied the access selection in the context of multi-RATs under a single operator, and many approaches were adopted to perform the decision [START_REF] Karam | A QoS based Decision Algorithm in next generation networks[END_REF][START_REF] Zhang | Handover decision using fuzzy MADM in heterogeneous networks[END_REF][START_REF] Song | A network selection mechanism for next generation networks[END_REF][START_REF] Stevens-Navarro | Comparison between vertical handoff decision algorithms for heterogenous wireless networks[END_REF][START_REF] Taha | A Framework for Radio Resource Management in Heterogenuous Wireless Networks[END_REF][START_REF] Helou | A hybrid approach for radio access technology selection in heterogenous wireless networks[END_REF][11]. To our knowledge, however, the multi-operator context is rarely considered. In this paper, we propose a hybrid decision method for RAT selection in a multi-operator context. The proposed selection algorithm is hybrid i.e., it guaranties users' satisfaction, in terms of preference and QoS application requirements, and associates them in a way to improve operator's profits and network performance.

The rest of the paper is organized as follows: Section II presents some existing work related to RAT selection algorithms. Section III describes our hybrid decision algorithm. Simulation environment and results are presented in section IV. Section V briefly concludes the paper.

II. BACKGROUND AND RELATED WORKS

Access Selection was widely studied in heterogeneous wireless networks with a single operator. Different approaches were adopted for decision making, and many algorithms were conceived in order to associate users to the best available RAT, at admission or during a vertical handover [3-8][11].

In order to select the best radio access network, a number of parameters must be considered. These parameters can be divided into four categories: Access network information, user preferences, terminal capabilities and service type. In a cost function based algorithm, these parameters are normalized, assigned a weight and then injected into a weighted sum to produce a selection score [START_REF] Karam | A QoS based Decision Algorithm in next generation networks[END_REF][8] [START_REF] Helou | Radio access selection approaches in heterogeneous wireless networks[END_REF]. In [START_REF] Zhang | Handover decision using fuzzy MADM in heterogeneous networks[END_REF], authors use fuzzy logic to deal with imprecise criteria and user preferences; data are first converted to crisp numbers and then classical Multiple Attribute Decision Making (MADM) methods as Simple Additive Weighting (SAW) and Technique for Order Preference by Similarity to Ideal Solution (TOPSIS), are applied. Another approach aims to prioritize the available RATs to decide the optimum one for mobile users. Such approach is used in [START_REF] Song | A network selection mechanism for next generation networks[END_REF]: Analytical Hierarchy Process (AHP) was adopted to arrange selection parameters in three hierarchical levels, in order to calculate the corresponding weighting factors. Then, Grey Relational Analysis (GRA) is applied to prioritize the networks for the selection decision. In [START_REF] Stevens-Navarro | Comparison between vertical handoff decision algorithms for heterogenous wireless networks[END_REF], a performance comparison was made between Multiplicative Exponent Weighting (MEW), SAW, TOPSIS and GRA. Results showed similar performance to all traffic classes. However, higher bandwidth and lower delay are provided by GRA for interactive and background traffic classes. A network centric approach is adopted in [START_REF] Taha | A Framework for Radio Resource Management in Heterogenuous Wireless Networks[END_REF], and a cost function is used to accommodate the maximum number of users in available RATs, while insuring load balancing. It consists of minimizing the costs of resource underutilization, demand rejection, thus maximizing the network operator profits. A Joint Radio Resource Management (JRRM) framework in a multi-operator environment is introduced in [START_REF] Giupponi | Improved revenue and radio resource usage through inter-operator joint radio resource management[END_REF]. Authors extended their single operator approach to an operator cooperation scenario. They proposed a two-layer JRRM strategy to fully exploit the available radio resource and to improve operators' revenue. The proposed economic-driven JRRM is based on fuzzy neural methodology with different classes of input parameters: Technical inputs, Economic inputs and Operator policies. The satisfying RAT is selected referring to a Fuzzy Selected Decision (FSD) indicating the appropriateness of selecting each available RAT in front of the others. This work showed how an inter-operator agreement can bring more benefits in terms of network performance and operators' revenue. In [START_REF] Kamal | Inter-operator spectrum sharing for cellular networks using game theory[END_REF], game theory is used for Dynamic Spectrum Access algorithm with cellular operators. Authors have defined a utility function, for the operators, considering user's bit rate, the blocking probability and the spectrum price. And they have presented a penalty function to control the blocking probability.

Therefore, we need a new algorithm for operator selection in a multi-operator environment, providing users the capability of being Always Best Connect (ABC) and guaranteeing operator's satisfaction, while enhancing the network performance. In our proposal, a user has more chance to get the service even when its home operator (which user has contract with) cannot satisfy his QoS requirements. In this case, the selection algorithm will direct him to the operator that best suit its demand while guaranteeing higher profit for his home operator. In fact, our proposal adds the profit by user exchange as a selection criterion, and it is assigned a specific weight W Op which can be varied to control selection and achieve more profits. Moreover, the proposed algorithm takes into consideration users' preferences, incomes and costs that may results from user's exchange, in order to optimize users association and guarantee profit improvement for all cooperating operators. Our hybrid approach for RAT selection in a multi-operator environment is presented in the following section.

III. OPERATOR SELECTION ALGORITHM

Consider a set of mobile operators who decided to cooperate. After executing the selection algorithm, a user can be served in the network of the home operator, denoted by Hop, bound by a contract, or in the network of another operator, denoted by serving operator. Users are not aware of the transfer between operators.

A. Decision Parameters

In order to insure an ABC profile for users and guarantee operators' satisfaction, the selection decision must take into account a number of parameters collected from application requirements, the user and the available access networks.

The application requirements are specified based on QoS classes. We consider two classes: real time such as Conversational class and non-real time as the Interactive class [START_REF] Stevens-Navarro | Comparison between vertical handoff decision algorithms for heterogenous wireless networks[END_REF]. The Conversational class groups services such as Voice over IP. This group of application is sensitive to jitter and delay. The Interactive class concerns the traffic of human interaction with remote equipments such as web browsing and server access. This scheme includes services sensitive to loss rate and round trip delay. Thus, four QoS parameters are considered as user application requirements [START_REF] Karam | A QoS based Decision Algorithm in next generation networks[END_REF]: the required Bandwidth BW Req , the required Jitter J Req , the required Delay D Req , and the required Bit Error Rate BER Req .

The second factor in the operator selection process is user preferences. In fact, user preferences are generally difficult to assess. The user may be ready to pay any price to receive service with best quality. Or he may prefer a cheap service regardless of the quality of the offered connection. In our work, user preferences are translated with a couple of weights [W QoS W p ] determining the degree of preference of the required QoS over the paid price per service p.

Furthermore, the wireless environment contains different operators as stated previously. And, without loss of generality, each operator manages a single RAT and is capable of offering service to all possible users. Each technology offers some QoS parameters such as: The available Bandwidth BW R , delay specifications as the mean Jitter J M and the mean Delay D M , and loss rate as the mean Bit Error Rate BER M . In addition, each technology sets a service access price sp. Moreover, each operator adopts its own market strategy i.e., an operator may consider user satisfaction as a top priority to prevent any churn risk, or he may ensure an acceptable QoS for his client while maximizing his profits. This will affect surely the selection decision for user transfer. In addition, the operators' cooperation could be done with a previous financial agreement determining the inter-operator service pricing, it means that when an operator transfers its client to another serving operator, the latter will charge him a service access cost Cs. This cost may be equal, lower or even higher than the service price sp. Therefore, an operator transferring his client must consider a serving operator with low service cost Cs, in order to ameliorate his profits. All the mentioned requirements and parameters will be quantified and injected in a cost function to achieve the selection decision.

B. Decision Cost Function

Since we intend to adopt a hybrid approach, the selection problem must fulfill two objectivesμ user's satisfaction and operator's satisfaction.

1) User's Satisfaction:

We suppose that a user intends to connect for a single service. The admission request to his Hoperator contains information about the service type and his preferences Fig. 1. Once the H-operator cannot meet the application requirements of his client, because of lack of resource or an usatisfying QoS, the application request will be transferred to the available cooperating operators. The selection process associates the user to the best operator in a transparent way. The selected operator must offer satisfaying QoS specifications and must respect user preferences. However, choosing always the best network operator may penalize this network by an overload and the others by underutilization. Therefore, we suggest choosing the operator delivering enough QoS to fit user's application requirements.

To achieve this selection, we consider the Nearest Performance Handover introduced in [START_REF] Karam | A QoS based Decision Algorithm in next generation networks[END_REF] and used in the context of multi-RAT under single operator. It consists of defining a score for the ideal solution, then defining a score for every selection candidate, and finally, choosing the candidate with the closest score to the ideal one. In our approach, the ideal operator/network is the one delivering the QoS parameters required by the user's application. Hence, the ideal solution will be assigned the user score. This score is a weighted combinaition of the different required QoS parameters. We propose adding the paid price p to this score in order to consider user preferences. Consequently, user's score Su is computed as follows:

 Su=W QoS *S QoS W p *p 
Where, W QoS is the weight determining the degree of preference of the required QoS over the paid price, and W p is the weight determining the degree of preference of the paid price over the QoS. Moreover, S QoS is the user QoS score calculated as follows: The selected operator that satisfies the user has a score with minimum distance to the ideal solution score. Every cooperating operator able to satisfy the user will be assigned a score S T computed as follows:

 S QoS
 S T =W QoS *S TQoS W p *sp  With  S TQoS =W JM *J M +W DM *D M +W BWR *BW R W BERM *BER M  
Where J M , D M , BW R and BER M are the mean jitter, mean endto-end delay, the remaining bandwidth and the mean loss rate measured on the candidate operator network, respectively. These parameters are normalized, assigned a weight, and then combined to form S T .

Finally, the selected operator must satisfy the user by minimizing |Su-S T |.

2) Operator's Satisfaction: An operator is satisfied when he gets better profits and improves his network performance. Thus, the preferred candidate to transfer his client (for service renting) will be an operator having a low Cs. In fact, a simplified cost analysis determines the income of the Hoperator by the price paid by his client p and the cost charged to him, while transferring his client, is the service cost Cs established by the candidate serving operator. Consequently, the selected serving operator is the one capable of maximizing the profit ( p-Cs).

Finally, considering both objectives, the best operator to choose is the one verifying the following condition:

 Selected(Op i )=min (W u *Su-S T |-W Op *(p-Cs))  i
Where, W u is the weight determining the degree of importance, for the H-operator, to satisfy the user. And W Op is the weight determining the degree of importance, for the H-operator, to improve his profits.

IV. SIMULATION AND RESULTS

A. Simulation Environment

For illustration, we consider three cooperating operators, Op 1 , Op 2 and Op 3 , each managing a single radio access network UMTS, WLAN1 and WLAN2, respectively. The conditions of the networks are shown in Table I. In this study, we suppose that all RATs are capable of delivering a constant value for J M , D M and BER M . The normalization of the different parameters is done for each access network with respect to the service requirements. The normalized values of these parameters are presented in Table II. For the service price sp, we use the following values: 0.9, 0.1 and 0.2 unit/kByte [START_REF] Song | A network selection mechanism for next generation networks[END_REF] for Op 1 , Op2 and Op 3 respectively.

After they arrive, mobiles are uniformly associated with a user profile, determining the service type, user preferences and the service price to pay p. We consider two possible service types: real-time and non real-time, and two preference vectors: [0.7 0.3] and [0.4 0.6], for high QoS preference and for high price preference, respectively. In addition, Conversational and Interactive QoS weights, corresponding to the bandwidth, the jitter, the delay and the loss rate are determined by applying AHP [START_REF] Song | A network selection mechanism for next generation networks[END_REF] [START_REF] Stevens-Navarro | Comparison between vertical handoff decision algorithms for heterogenous wireless networks[END_REF], and are given by the following vectors: [0.05, 0.45, 0.45, 0.05] and [0.16, 0.04, 0.16, 0.64], respectively. Moreover, application requirements for real-time and non realtime services are determined in Table III, taking into account that bandwidth consumption of a service varies with the network technology.

B. Simulation Setup

We consider the system formed by the three operators Op 1 ,Op 2 and Op 3 . Users arrive to the system sequentially. We model the arrival and departure of users as a Poisson Process with mean arrival interval 1/ . We perform simulation for different values of 1/ = 5/2, 25/9, 10/3 and 5. Once connected, the user will stay in the system for a certain service time, assumed to follow an exponential distribution of mean 1/ =4min. During this service time, the user will consume a constant bit rate depending on his service type and the access technology of the serving operator. Note that no scheduling is considered. And, at the end of the connection, the user will leave the system improving, consequently, the available bandwidth of the serving operator. The simulation is done for duration of 1200 sec and repeated for 20 experiments. We use Matlab to achieve this simulation.

C. Simulation Results

For lack of space, we will present only simulation results for the system performance and profits amelioration, obtained for W u /W op =1 and Cs=sp, for all operators. The effect of user preferences and the financial strategy of the H-operator will be presented in a following work. Simulation results are discussed in this section. In all figures, the number of users represents the sum of arrivals in the system.

1) Global performance:

We first illustrate simulation results for the global blocking probability, translating the global performance of the system. Fig. 2 compares the performance of the system, in term of blocking probability, before and after cooperation. Operators are assumed adopting the same strategy (W u /W op ) and keeping the same price for service renting (Cs=sp). Simulation results show an excellent reduction in the blocking probability. When the operators cooperate, this probability does not reach 5%. One can see how much cooperation has helped operators to face blockings. These blockings, generally, are associated with a lack of resource, a bad QoS specifications or an overload situation. But, when operators cooperate, the blocking probability is reduced about 20%, showing that this cooperation is unavoidable and it brings benefits for the overall mobile system.

2) Network performance: The study of the blocking probability of each operator shows an important improvement, espacially for the operators managing a limited capacity. Fig. 3 presents a comparison between the blocking probabilities, before and after cooperation, for every cooperating operator. One can see that, Op1 is taking the largest benefit from this cooperation. His blocking probability is reduced by 48%, thus raising the number of admitted users. Op1 could face overload situations by transferring his clients to Op2 and Op3. In addition, Op3 has limited his blocking percentage below 2% after cooperation. Moreover, Op2 has benefitted slightly of this cooperation; this operator already had a low blocking rate even without cooperation. In fact, Op2 has the best capacity among the cooperating operators in the system. In addition, comparing the blocking probability for Op2 and Op3 shows the same performance for a number of arrivals below 360 users, but for higher number of arrivals, Op3 denotes higher blocking rates. This is due not simply to the capacity difference, but also to the fact that Op3 is more acting as a serving operator than Op2. An additional analysis of the served users by Op2 and Op3, for high arrival rates, showed that up to 40% of the users served by Op3, are guests coming mostly from Op1, but Op2 guests do exceed 18% of the served users. Beside, when Op1 intends to transfer his clients, 79% of them go towards Op3 and the rest to Op2. In addition, the majority of the transferred clients, from Op1 to Op3, seeks an interactive service that consumes well in a WLAN RAT, thus raising the probabilty of blocking in Op3 access network.

3) Operators' profit amelioration: The capacity gain achieved through cooperation induced a profit gain. New incomes are available from guests and transferred clients. Fig. 4 shows profit improvements for Op1, Op2 and Op3. The important increase of the users' acceptance, after cooperation, brought more incomes for Op1; clients transferred, from Op1 to another serving operators, instead of being blocked and guests served by Op1 participated all in the increase of Op1 incomes. We can notice the remarkable amelioration of Op1 profits. Op3 also benefits from profit amelioration. In fact, up to 40% of the incomes of Op3, as shown in Fig. 5 are from exhanged clients and served guests. This income has risen after cooperation. In addition to the increase of users' IV. Consequently, it reduces the rate consumption, thus the service cost charged to Op3, next to this exhange. We can see clearly from Fig. 5 that the service cost charged to Op3 is lower than the additionnal incomes from tranferred users. Again, Op2 does not take much benefits from this cooperation, little profit improvement is noticed. If we remark the amount of users exchanged (transferred) from Op2 in Fig. 5, we can see that it is relatively low. Moreover, a study of the direction of this transfer has revealed that the majority of the transferred clients are designated to Op1. The latter has high service cost; 9 times the Cs of Op2, thus increasing the cost service charged to Op2 until it exceeds the incomes gained from users' exchange, Fig. 5. It is obvious, in this scenario, that Op2 is not benefiting directly from this cooperation. But, since Op2 has served guest users, we can say that he has benefitted by avoiding resource underutilization. Op2 can achieve more profits by controlling his service cost Cs and set a higher price for service renting. IV shows the direction of application (client) exchange. For Op1, all clients seeking a real-time service are migrated to Op3. The latter can guarantee a good QoS for this type of service. Moreover, when the transferred clients of Op1 are seeking a non realtime, they are distributed on Op2 and Op3 networks. A deeper analysis of this transfer showed that clients are moved to Op3 instead of Op2, only when Op3 is the unique choice for exchange. For Op2, the majority of real-time services are transferred to UMTS technology delivering the best jitter, but capacity limitations of Op1 caused that a portion of those services is moved to Op3. In case of non real-time services, all clients are moved to Op3 delivering better QoS specifications, espacially that UMTS technology offers high BER for this kind of service. For Op3, the real-time services are distributed on Op1 and Op2 networks, since Op1 has limited capacity. But all non real-time services are moved to Op2, offering better BER. We can say that, the selection algorithm could

4) Sensitivity Analysis: Table

V. CONCLUSION

In this paper, a hybrid decision algorithm for the selection of the access in a multi-operator network has been presented. A cost function has been used. It combined the performance information given by the different wireless network and the requirements of the mobile user's application, added to the resulting profit of the user exchange. Moreover, it considered user preferences and operator's strategy, in order to guarantee the ABC user profile and a global gain for all cooperating operators. Simulation results proved the efficiency of the proposed scheme in terms of user and operator satisfaction, load balancing and network performance enhancement. Future work will investigate the effect of the weights related to operator strategy [W u W Op ], and the pricing policy, to show how the operator can achieve more revenues and ameliorate its profits, while cooperating.

Fig. 1 .

 1 Fig. 1. Decision Parameters

Fig. 2 .

 2 Fig. 2. Global Blocking Probability Comparison

Fig. 4 .

 4 Fig. 4. Operators' Profits before and after cooperation

Fig. 5 .

 5 Fig. 5. Operators' Income Composition and Service Cost after Cooperation

  =W JReq *J Req +W DReq *D Req +W BWReq *BW Req W BERReq *BER

Req 

Where, J Req , D Req , BW Req and BER Req are the required jitter, delay, bandwidth and BER respectively, for user's application. These parameters are determined from the application QoS class, normalized and associated to their corresponding weights W JReq , W DReq , W BWReq and W BERReq respectively, before computing Su.

TABLE I .

 I UMTS AND WLAN NETWORK PARAMETERS[START_REF] Song | A network selection mechanism for next generation networks[END_REF]

Network Technology QoS Parameters Bandwidth(Kb/s) Jitter(ms) Delay(ms) BER(dB)

	UMTS	1700	6	19	10 -3
	WLAN1	11000	10	30	10 -5
	WLAN2	5500	10	45	10 -5

TABLE II

 II

	.	NORMALIZED NETWORK PARAMETERS
			QoS Parameters a
	RAT	BW Jitter Delay BER
	UMTS	1	1	1	1
	WLAN1	1	1	1	1
	WLAN2	1	1	1	1
	a. Normalization is done with respect to real-time service rquirements

TABLE III

 III

	.	APPLICATION REQUIREMENTS
			QoS Parameters
	Service Type	Jitter(ms) Delay(ms) BER(dB)
	Real-Time	10	100	10 -3
	Non Real-Time	20	150	10 -5

TABLE IV .

 IV DIRECTION OF APPLICATION EXCHANGE

Application Type Real-Time Non Real-Time

	To
	From	Op1 Op2 Op3	Op1	Op2	Op3
	Op1	-	0	100%	-	20%	80%
	Op2	90% -	10%	0	-	100%
	Op3	10% 90% -	0	100%	-


Soha Farhat

Abed Ellatif Samhat

Samer Lahoud

Bernard Cousin

Best Operator Policy in a Heterogeneous Wireless Network

Keywords: Multi-operator networks, cooperation awareness, resource management, access selection, operator strategy. I

In this paper, we perform a business analysis of our hybrid decision algorithm for the selection of the access in a multi-operator networks environment. We investigate the ability of the operator to express his strategy and influence the access selection for his client. In this purpose, we study two important coefficients of the previously proposed cost function, Wu and Wop, and show that the value of these coefficients is not arbitrary. Simulation results show that the value of the ratio Wu/Wop enables a selection decision respecting operator's strategy and it affects the achieved global profit for all cooperating operators.

INTRODUCTION

To cooperate, or not to cooperate: It shouldn't be anymore a difficult decision to take, for wireless network operators. Cooperation is promising and brings a lot of benefits for network operators, in terms of capacity, data rates and coverage expansion. Besides, it helps operators to decrease investment costs and brings more revenues [START_REF] Hutell | Business models and resource management for shared wireless networks[END_REF]. Moreover, in a multi-operator sharing network, where competing operators share their radio access networks, operators can avoid the waste of radio resources, and defeat QoS degradation through cooperation.

However, when an operator decides to cooperate, this decision must be done with an intangible consciousness of what and how to share, and with whom to cooperate. Network operator must be aware of different characteristics of his networks and other competing operators' networks such size, geographical coverage and deployment, operators' market share, access technology, service availability, cost ...etc.

In fact, in a cooperative environment, when an operator is unable to insure satisfaction constraints to its user, he tries to give him access to the service through another network operator, thus avoiding his rejection. But, among cooperating operators, one operator may be able to offer the best QoS specifications for the user's application; while another may be able to guarantee higher profit for the user home operator. Then, the choice of the cooperating operator for user transfer may induce different profits, and it is to consider when cooperating. Additionally, competing operators can adopt different strategies when it comes to increase profits or to satisfy the user, and the priority of each goal can change with time, shared network state or the competition situation. Moreover, when the decision process of the access selection is based on a cost function as the case in our work, the strategy of the operator must be explicitly expressed and be effective, when tuned, at the selection.

In a previous work [START_REF] Farhat | Hybrid Decision Algorithm for Access Selection in Multi-operator Networks[END_REF], a hybrid decision algorithm for the selection of the access in a multi-operator network was proposed. A cost function was used combining the performance information given by the different wireless network and the requirements of the mobile user's application, added to the resulting profit of the user exchange. The proposed cost function considered user preferences and operator's strategy, in order to guarantee the ABC user profile and a global gain for all cooperating operators. Simulation results proved the efficiency of the proposed scheme in terms of user and operator satisfaction, load balancing and network performance enhancement. This paper extends the previous work to investigate the effect of the weights related to operator strategy [W u W op ], used in the previously proposed cost function, and show the effect of the ratio Wu/Wop on the selection decision and the global profit.

The rest of the paper is organized as follows: Section II presents some existing work related to business models in a multi-operator environment. Section III presents the system model and the proposed scenario to evaluate the decision cost function for a hybrid decision algorithm. Simulation results are discussed in section IV. And section V summarizes paper conclusions.

II. BACKGROUND AND RELATED WORKS

In a multi-operator multi-technology wireless network, an independent Radio Resource Management (RRM) is inefficient, and a proper interworking is needed to perform a Coordinated Radio Resource Management (CRRM) in order to prevent any resource under-utilization or an overload in any Radio Access Network (RAT).

In literature, CRRM in a multi-operator context has been faced from different perspectives [START_REF] Hutell | Business models and resource management for shared wireless networks[END_REF][START_REF] Johansson | Cost Effective Deployment Strategies for Heterogenous Wireless Networks : doctoral dissertation in telecommunication[END_REF][START_REF] Giupponi | Improved revenue and radio resource usage through inter-operator joint radio resource management[END_REF]. In [START_REF] Giupponi | Improved revenue and radio resource usage through inter-operator joint radio resource management[END_REF] a two layered approach is adopted to improve radio resource usage and different business models are studies to show that cooperation is always beneficent for all operators. Authors introduced the concept of the Metaoperator, who acts as a third trusty party and maintains and guarantees inter-operator agreements especially for service pricing. This Metaoperator is also, responsible of the decision making process for operator selection; he communicates with the different cooperating operators the information collected the decision p and the suitable serving operator is s authors in [START_REF] Hutell | Business models and resource management for shared wireless networks[END_REF] found that a third party is n competition between operators and p information messages between them. M proposed that network selection is perfor service provider or an inter-connectio though it reduces network performance integration.

Consequently, in a multi-RAT environment, when an operator is una client, he communicates with the third p access selection process. This will trigg of each operator to find the suitable R user. The third party is made to com cooperating operators and retrieve funct the selection decision in a two layered from different offered access network party will select the best RAT. Thus, find in an operator centric vision, is to technology guaranteeing better profits. H the selection of the best RAT? In o weights of our cost function will be tun selection.

In the following we will present the c and the decision algorithm adopted selection. Then, the previously conceive described briefly and the choice of W u /W s and according to rocess is triggered selected. As well, needed to preserve prevent any false Moreover, authors rmed by either the on provider, even due to a less tight T multi-Operator able to satisfy his party to trigger the ger the RRM units RAT for the guest mmunicate with all tional statistics for framework. Then, ks the third trusty ding the best RAT, select the access How can we insure ur approach, two ned to control the cooperating system d for the access ed cost function is W op is analyzed for the selection control.

III. OPERATOR SELE

When a group of operator share their Radio Resource, a inter-operator agreements is to a third trusty party to preserve selection algorithm is to be ma suitable unit guaranteeing a cor system formed by three co managing a single radio access can be served in the network of by H-op, bound by a contract, o operator, denoted by serving op admit his user or is unable to in his application, H-op intends to cooperating operator to av transaction is transparent to the

A. Decision Cost Function

In our previous work [START_REF] Farhat | Hybrid Decision Algorithm for Access Selection in Multi-operator Networks[END_REF], w able to insure user's appl guarantee lower service cost function intends to minimize score of the service network an S T |. In addition, it permits to who maximizes the home oper Cs). Where, Su is the score application QoS requirements a is the network score combinin parameters and the service p operator for his own clients, an by the service operator for gue input parameters for the decis parameters comes from the user paid prices and user prefe parameters are available from e the QoS delivered parameters, service cost Cs. The decision operator by minimizing the foll

CF=W u *|Su-S T |-W
We can point here to W u , degree of importance for the H W op , the weight determining th the H-op, to improve his prof W u /W op is not arbitrary and is degree of importance of satisfy higher profits as in AHP scale study of the proposed cost fun is bounded by limits, which ar between the achieved profit between the scores distances operators are compared pair wi W op could be dynamic or considered scenario.

The determines the group of value permits to select the operating m and the group of values that environment.

Op3

RRM3 T3

ECTION ALGORITHM rs decide to cooperate and a previous establishment of be done and guaranteed by e competition. In addition, a aintained and processed in a rrect decision. Fig. 1 shows a ooperating operators, each network. A connecting user f the home operator, denoted or in the network of another perator. When, H-op cannot nsure QoS requirements for o transfer this user to another void his rejection. This users.

we proposed a cost function lication requirements and t for the H-op. This cost the distance between the nd the score of the user |Suselect the service operator rator profit per exchange (pof the user combining his and his paid price p H-op, S T ng different QoS delivered rice sp set by the service nd Cs is the service cost set est service. Fig. 2 shows the sion algorithm. A group of r as the application type, the erences, and a group of each cooperating operator as the service price sp and the process will select the best lowing cost function:

W op *(p-Cs) (1)
the weight determining the H-op, to satisfy the user, and he degree of importance for fits. The choice of the ratio s not simply related to the ying the user over achieving e [START_REF] Saaty | The Analytical Hierarchy Process: Planning, Priority Setting, Ressource Allocation[END_REF]. In fact, an analytical nction showed that this ratio re function of the difference (p-Cs) and the difference s |Su-S T |, when candidate ise. So, the value of W u and static depending on the limits mentioned above es of the ratio W u /W op that maximizing the H-op profit, t permits to satisfy, to the maximum, user's application requirements. To illustrate what it is described above, we consider two candidates operator for the selection, Op1 and Op2, having the scores S T1 and S T2 and setting Cs1and Cs2 for the service cost, thus having CF1 and CF2 as cost function, respectively:

CF1=Wu* Su-ST1 -Wop* p-Cs1 CF2=Wu* Su-ST2 -Wop*(p-Cs2) (2)
If the profits per exchange are higher when the user is served by Op1, H-op must set CF1<CF2 to select Op1, thus W u /W Op must fulfill the condition:

Wu Wop < p-Cs1 -p-Cs2 Su-ST1 -Su-ST2 (3)
In other scenarios, where there are more than two candidates for the selection, the ratio W u /W op will be bounded by two or more limits.

IV. SIMULATION RESULTS

A. System Model

We consider three cooperating operators, Op 1 , Op 2 and Op 3 , each managing a single radio access network UMTS, WLAN1 and WLAN2, respectively. The conditions of the networks are shown in Table I. In this study, we suppose that all RATs are capable of delivering a constant value for the mean jitter J M , mean delay D M and mean bit error rate BER M [START_REF] Song | A network selection mechanism for next generation networks[END_REF]. The normalization of the different parameters is done for each access network with respect to the service requirements. We consider one single service type for real-time application, this service requirements are determined in Table II, taking into account that bandwidth consumption of a service varies with the network technology.

Jitter(ms) Delay(ms) BER(dB)

Real-Time 10 100 10 -3

B. Effect of Wu/Wop

To study the effect of the ratio Wu/Wop on the selection decision, we consider the system model described above with the jitter as decision parameter. Besides, without loss of generality, the service price sp is set to 0.9, 0.1, and 0.5 units/Kbytes for Op1, Op2 and Op3 respectively. The service cost is set equal to the service price for all cooperating operators Cs=sp. Consequently, a client served in his H-op network will pay for the H-op p=sp, and when this user is served in another S-op network he will pay p=spi for his H-op Opi and the latter will pay Cs=spj for the S-op Opj.

As described previously, when there are two candidates for selection, one operator may offer the best score and the other may offer the best profit for the H-op. Thus, an upper limit L bounds the values of Wu/Wop that guarantee the selection of the operator with best profit, and all values above L select the best scored operator. L can be calculated from equation ( 3): so, if the H-op intends to choose the service operator with lower cost, Wu/Wop must be chosen below L, else if he seeks the operator delivering the best parameters for his client, Wu/Wop must chosen above L. Note that the limit L, for every operator, changes with the system model, the pricing scenario and the score distances (if the considered QoS parameters vary during simulation).

In this scenario, the mean jitter delivered by RATS is constant, so L is constant. And for more simplification a common limit is deduced analytically for the three cooperating operators, and without loss of generality, two values are decided for simulation Wu/Wop=1/4<L and Wu/Wop=8>L.

1) Effect on the selection decision:

We are interested, to present for each H-op, the service operator, S-op, with a minimum score distance (dmin) to the user requirements, and the S-op generating best profit for Hop, in this scenario, Table III. Simulation results for the effect of the choice of Wu/Wop on the selection are presented in Table IV. Selection results show that, a ratio below the limit L guarantee all the time that H-op selects the operator maximizing his profits. Besides, when the selection is between two operators causing losses for Hop, the selection algorithm guarantee the lower loss with In fact, in this scenario where Cs=sp, we can distinguish three cases:

1. The H-op must choose between two operator inducing different profits (case of Op1): in this case, when Wu/Wop is tuned below L, the S-op with better profit is selected. 2. The H-op must choose between an operator with some profits and other causing him losses (case of Op3): in this case a value below L guarantees the selection without losses. 3. The H-op must choose between two operators, each having high service costs and causes losses to the H-op (case of Op2): in this case, when Wu/Wop is lower than L, H-op selects the S-op causing him lower loss. And, note that for all cases, when Wu/Wop>L the selection goes to the operator having the closest score to Su. 2) Effect on the network performance: We used the blocking rate as an indicator for the network performance. Fig. 3 represents this blocking probability for all operators when varying the strategy ratio Wu/Wop. Results showed that strategy ratio has no effect on the performance; the blocking probability is conserved within a 90 % confidence intervalle.

3) Effect on the operator profit: So, it is enough to have information about the service cost set by different cooperating operators and the delivered QoS score, to decide the values of Wu and Wop and insert them into the decision cost function to guarantee the selection of the best operator ( achieving best profit for H-op). But, results showed that the selection of the best operator won't always ameliorate the global profit achieved by H-op. Fig. 4 represents operators' global profits variation when tuning the strategy ratio. It shows a great amelioration in profits for Op3, when setting Wu/Wop<L. In fact, Op3 had to choose between Op2 that brings profits and Op1 that causes losses. So, when the strategy is changed to a value>L and the selection falls 100% to Op1, Op3 was penalized with a lot of losses causing profit degradation. It is the same for Op2, little improvement is detected since a value of Wu/Wop<L permits to select the operator with lower losses. In fact, in this scenario, Op2 offers the cheapest service, so he is always loosing when exchanging a client, in term of revenue. But, it is not the same for Op1. Tuning Wu/Wop below L causes lower profit, but a value>L ameliorates it. Indeed, the value of Wu/Wop affects the whole exchange process and thus, the probability that each operator acts as an S-op and the amount of added guests in each operator network, besides the direction of users' migration from each H-op and thus the charged costs. And, while the global profit is calculated from the revenues of the added clients, guest users and exchanged clients minus the cost charged for the client exchange, the value of Wu/Wop will affect it in some way. So, in this scenario, when Wu/Wop was set above L for all cooperating operators, Op1 is more selected to serve Op2 and Op3 users (Table IV), since having better score distance, which increases hugely the amount of revenues from guest users, and ameliorates his profits. We can conclude briefly, that the value of Wu/Wop<L was efficient to prevent a choice with losses and ameliorate profits, but when choosing between two profiting operators the operator must consider the resulting exchange process and the probability to achieve higher revenues. In this paper, we have showed that our decision algorithm for access selection gives operators the ability to exchange clients with respect to their decided strategy by tuning the ratio Wu/Wop above or below a calculated limit L. This limit L depends of the system model, i.e, the number of cooperating operators, the delivered QoS parameters of the different networks of the competing operators, the service price sp set for the clients of the different operators and finally the pricing scenario adopted for the service cost Cs charged to guest's H-op. Moreover, setting the ratio to a value that guarantees the selection of the most profitable operators does not always guarantee a better global profit gain. The value of the ratio Wu/Wop will affect the direction of users exchange and the probability that an operator acts as a service operator or. Thus, operators must be aware of the user exchange process and the best pricing scenario, to have a good prediction of the extra revenues that can be achieved and the possible profit improvement gained from cooperation. Future work will investigate the pricing scenario that can be adopted during cooperation and how to choose the best one to ameliorate profits.

Fig. 1 .Fig. 2 .

 12 Fig. 1.Multi-operators mono-technology e

Fig. 3 .

 3 Fig. 3. Blocking probability conservation

Fig. 4 .

 4 Fig. 4.Operators' global profit variation

TABLE I .

 I

UMTS AND WLAN NETWORK PARAMETERS

[START_REF] Song | A network selection mechanism for next generation networks[END_REF]

Network Technology QoS Parameters Bandwidth(Kb/s) Jitter(ms) Delay(ms) BER(dB)

	UMTS	1700	6	19	10 -3
	WLAN1	11000	10	30	10 -5
	WLAN2	5500	10	45	10 -5

TABLE II

 II

	.	APPLICATION REQUIREMENTS
	Service Type	QoS Parameters

TABLE III .

 III CANDIDATE OPERERATORS QUALIFICATION

H-op Candidate Operator with dmin with Best profit

	Op1	Op3	Op2
	Op2	Op1	Op1
	Op3	Op1	Op2

TABLE IV

 IV

			.	SERVICE OPERATOR SELECTION (%)
				Selection Direction
		Wu/Wop=8			Wu/Wop=1/4
		(dminOp selection)	(best profit Op selection)
		Op1	Op2	Op3	Op1	Op2	Op3
	Op1	-	0	100% Op1	-	100%	0
	Op2 100%	-	0	Op2 100%	-	0
	Op3 100%	0	-	Op3	0	100%	-
	Hence, results showed that the ratio Wu/Wop had reflected
	the operator strategy for the selection decision. But, it
	would be necessary to test if tuning the operator strategy
	(varying Wu/Wop above and below L) has any effect on
	the network performance and if it ameliorates the global
	profit, achieved by each operator. Results are presented
	briefly in the following subsectors:


Mathieu Aubry

Daniel Maturana

Alexei A Efros

Bryan C Russell

Josef Sivic

Seeing 3D chairs: exemplar part-based 2D-3D alignment using a large dataset of CAD models

This paper poses object category detection in images as a type of 2D-to-3D alignment problem, utilizing the large quantities of 3D CAD models that have been made publicly available online. Using the "chair" class as a running example, we propose an exemplar-based 3D category representation, which can explicitly model chairs of different styles as well as the large variation in viewpoint. We develop an approach to establish part-based correspondences between 3D CAD models and real photographs. This is achieved by (i) representing each 3D model using a set of view-dependent mid-level visual elements learned from synthesized views in a discriminative fashion, (ii) carefully calibrating the individual element detectors on a common dataset of negative images, and (iii) matching visual elements to the test image allowing for small mutual deformations but preserving the viewpoint and style constraints. We demonstrate the ability of our system to align 3D models with 2D objects in the challenging PASCAL VOC images, which depict a wide variety of chairs in complex scenes.

Introduction

From its very beginnings [START_REF] Roberts | Machine perception of 3-D solids[END_REF] and up until the early nineties [29], object recognition research has been heavily geometry-centric. The central tenet of the time was alignment 1 , and the act of recognition was posed as correctly aligning a 3D model of an object with its 2D depiction in the test image [START_REF] Huttenlocher | Object recognition using alignment[END_REF][START_REF] Lowe | The viewpoint consistency constraint[END_REF]. The parameters recovered during alignment (object pose, object scale, etc.) served as the output of the recognition process, to be used, for instance, in the perception-manipulation loop in robotics applications. Unfortunately, the success of these 3D model-based methods was largely limited to instance recognition tasks for objects with well-pronounced rectilinear structures (e.g. sta- * WILLOW project-team, Département d'Informatique de l' École Normale Supérieure, ENS/INRIA/CNRS UMR 8548, Paris, France.

1 Indeed, one of the oft-told stories is that when a student asked Takeo Kanade what are the three most important problems in computer vision, his reply was: "Alignment, alignment, alignment!".

(a) Input images (b) Aligned output (c) 3D chair models Figure 1: Given an input image (left), our algorithm searches a database of 1,393 3D chair models to detect any depicted chairs in the image. The algorithm returns a 3D model matching the style of the chair and recovers its viewpoint relative to the camera (outlined in green, right). We overlay a projection of the returned 3D model onto the input image (middle). Notice the agreement of the returned model with the depicted chair style and pose. plers were a favorite example). As the field moved toward category recognition and objects with more complex appearance, 3D model-based object recognition has been replaced by the new 2D appearance-based methods (e.g. [9,14,[START_REF] Viola | Rapid object detection using a boosted cascade of simple classifiers[END_REF]). These methods forgo 3D and operate directly on the 2D image plane. Thus, instead of a 3D model of an object, they use a large dataset of 2D views of the object class from different viewpoints, as the model. These methods have shown steadily improving performance on a number of challenging tasks, such as the PASCAL VOC dataset [START_REF] Everingham | The Pascal visual object classes (VOC) challenge[END_REF]. However, their main drawback is that the result of a successful recognition is typically just the name of the object that was found (e.g. "chair") and a bounding box to indicate its rough location 1 within the image. While this type of result is reasonable for tasks such as retrieval (e.g. "find all chairs in this dataset"), it is rather unsatisfying for doing any deeper reasoning about the scene (e.g. "what's the pose of the chair?", "can I sit on it?", "what is this chair occluding?", "how can I fold this chair?", etc). All these questions could be trivially answered, if only we had a 3D model of the chair aligned with the image!

The work presented in this paper aims to combine some of the benefits of the 3D model-based instance alignment methods with the modern, appearance-based object category tools towards getting a best-of-both-worlds object recognition engine. The idea is to use a large library of textured 3D object models that have become publicly available on the Internet to implicitly represent both the 3D shape of the object class, as well as its view-dependent 2D appearance. Our approach can be considered as a marriage between part-based discriminative models [14] and exemplar-based matching [28]. Like part-based models, we represent objects using a set of connected appearance parts. But, like exemplar-based methods, we avoid explicitly training an object model by relying on a large dataset of object instances that serve as their own model, both in 2D as well as 3D.

We picked the "chair" category as the running example in this paper because: 1) it is very hard even for the stateof-the-art methods [14], achieving only 0.13-0.20 average precision (AP) on PASCAL VOC [1]; 2) it is a category wellrepresented in publicly-available 3D model collections (e.g. Google/Trimble 3D Warehouse), 3) chairs have huge intraclass variation -whereas there are perhaps only hundreds of types of cars ever made, there are thousands of different types of chairs!

Related Work

Our paper is part of an emerging trend towards reclaiming some of the early successes in 3D recognition, and combining them with modern visual recognition tools.

3D geometry with multi-view constraints has served as a strong alignment oracle for instance-level recognition [START_REF] Li | Worldwide pose estimation using 3D point clouds[END_REF][START_REF] Rothganger | 3D object modeling and recognition using affine-invariant patches and multi-view spatial constraints[END_REF] and retrieval [START_REF] Chum | Total Recall: Automatic query expansion with a generative feature model for object retrieval[END_REF]. Images are typically represented using local invariant features such as SIFT [27], which work best for textured objects such as building facades [START_REF] Li | Worldwide pose estimation using 3D point clouds[END_REF][START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF][START_REF] Sattler | Fast image-based localization using direct 2D-to-3D matching[END_REF]. More recent work has seen the reemergence of contour-based representations for matching skylines [START_REF] Baatz | Large scale visual geo-localization of images in mountainous terrain[END_REF] and smooth objects such as furniture pieces [START_REF] Lim | Parsing IKEA objects: Fine pose estimation[END_REF] or statues [START_REF] Arandjelović | Smooth object retrieval using a bag of boundaries[END_REF], however, these efforts have also largely focused on instance recognition.

In category-level recognition, recent work has explored recognition, alignment and fine pose estimation for cars and bicycles in outdoor scenes using low-dimensional parametric deformable 3D models combined with a relatively small number of learnt part detectors [20,[START_REF] Pepik | Teaching 3D geometry to deformable part models[END_REF][START_REF] Zia | Detailed 3D representations for object recognition and modeling[END_REF]. Others have explored simplified 3D cuboid models for reasoning about outdoor scenes [START_REF] Gupta | Blocks world revisited: Image understanding using qualitative geometry and mechanics[END_REF] or detecting and estimating pose for box-like objects such as printers, beds or sofas [START_REF] Fidler | 3D object detection and viewpoint estimation with a deformable 3D cuboid model[END_REF][START_REF] Xiao | Localizing 3D cuboids in single-view images[END_REF], often using simplifying 3D box-layout constraints for indoor scenes [START_REF] Choi | Understanding indoor scenes using 3D geometric phrases[END_REF][START_REF] Del Pero | Understanding Bayesian rooms using composite 3D object models[END_REF]. Indoor objects have been also represented by simplified models consisting of a small set of planar parts [START_REF] Xiang | Estimating the aspect layout of object categories[END_REF]. Finally, a collection of registered images of 22 cars has been used in a Hough-like voting procedure to estimate the poses of cars [START_REF] Glasner | Viewpoint-aware object detection and pose estimation[END_REF]. In a separate line of research, a discriminative, exemplar-based object detection framework demonstrated (anecdotal) results for transferring 3D object geometry onto a test image once 2D-to-2D alignment with an exemplar was established [28]. However, [28] models an object with a single global template, thus requiring a large number of exemplars to represent categories with high intraclass variation. Non-parametric representations have also shown promising results for 2D-to-3D matching of indoor scenes [START_REF] Satkin | Data-driven scene understanding from 3D models[END_REF], but again, due to the use of a global scene descriptor, this method works only for highly structured scenes, such as (tidy) bedrooms.

Addressing the need for descriptors that capture less than a full object/scene, but are more descriptive than low-level features such as SIFT [27], are a new breed of mid-level visual elements. Recently, discriminatively trained mid-level representations have shown great promise for various visual recognition tasks, both in a supervised regime [START_REF] Bourdev | Poselets: Body part detectors trained using 3D human pose annotations[END_REF], as well as unsupervised [START_REF] Jain | Representing videos using mid-level discriminative patches[END_REF][START_REF] Juneja | Blocks that shout: Distinctive parts for scene classification[END_REF]36], including 2D-to-3D alignment of object instances across large changes in appearance [START_REF] Aubry | Painting-to-3D model alignment via discriminative visual elements[END_REF]. While here we build on the latter work, which aligned a single image to a single 3D model, we address the much more difficult problem of category-level recognition, which must align a single image to over 1300 3D chair models.

Approach Overview

Our representation consists of a large set of 3D CAD models, which captures both the large variety of chair styles and their different possible viewpoints. Chair detection in new images is accomplished by finding an alignment between the 2D chair and the most similar 3D chair model rendered at the most appropriate camera viewpoint, as shown in Figure 1. Aligning photographed 2D objects with the most similar (but not identical) computer-generated 3D model is a very hard problem. Here we address it by representing the collection of all 3D models by more than 800,000 calibrated view-dependent mid-level visual elements learned in a discriminative fashion from rendered views. At test time, all the learned visual elements are applied to the test image in parallel. The most spatially and appearance-wise consistent alignment is found, while preserving the style and viewpoint-consistency constraints. The details of the algorithm are described in Section 3.

Contributions.

Posing object category detection in images as a 3D instance alignment problem, we: 1) develop an exemplar-based 3D category representation capturing vari-ations across object style and viewpoint; 2) establish the correspondence between computer-generated 3D models and 2D photographs using a large collection of mid-level visual elements; 3) collect a dataset of more than 1,300 3D chairs from the Internet, publicly available at [2].

Large dataset of 3D chairs

We explicitly represent the shape variation of an object category by a large collection of 3D CAD models. The 3D models used in this work have been downloaded from the Google/Trimble 3D Warehouse, an on-line repository of publicly available, user-contributed 3D graphics content created using Google SketchUp. We initially searched the repository for "chair" and downloaded over two thousand 3D models. However, many of them were not of good visual quality; some weren't even chairs. After manually culling the data, we were left with 1, 393 high-quality 3D chair models, representing a variety of chair styles.

Each 3D chair model was rendered on a white background from 62 different viewpoints sampled over the upper half of the viewing sphere centered on the chair. The resulting chair dataset contains a total of 1, 393 * 62 = 86, 366 synthesized images, each annotated with the chair ID indicating the different style, as well as the viewing orientation (θ, φ). This dataset is our non-parametric representation of the object category explicitly representing the large variety of chair styles and the set of possible viewing positions.

Building Discriminative Visual Element Detectors

Explicitly representing and synthesizing the fine-grained style and viewpoint of the 3D object category significantly simplifies the difficult task of 2D-to-3D alignment. Nevertheless, reliably matching a synthesized view of an object to a real photograph is still challenging due to differences in, e.g., texture, materials, color, illumination or geometry. Furthermore, it is well known that computer generated images have different statistical properties than real photographs. To address these issues we cast the matching problem as a classification task, and represent the collection of 3D models using a large set of mid-level visual elements -linear classifiers over HOG features learnt from the rendered views in a discriminative fashion (section 3.1). As each of the hundreds of thousands of visual elements is learnt individually, calibrating their matching scores becomes a critical issue. We address this by learning a linear calibrating function for each element on a common dataset of negative images (section 3.2). Finally, we wish to be tolerant to small geometric deformations (such as a chair with longer legs or shorter armrests). We develop a matching procedure (section 3.3) that allows for small deformations in the spatial configurations of the matched visual elements while preserving consistent viewpoint and style.

Large-scale learning of visual element detectors

The goal is to match a square image patch q, represented as a HOG descriptor [9], in a rendered 3D view to its corresponding patch in the input image. Following [START_REF] Aubry | Painting-to-3D model alignment via discriminative visual elements[END_REF], we treat matching as a classification task where we wish to find the patch x * in the input image that maximizes the following linear classifier score that is dependent on q:

S q (x) = w T q x. (1)
Here w q is a vector of learned weights for the classifier dependent on q. In contrast to measuring similarity via Euclidean distance between q and x, the weights w q emphasize feature dimensions that are discriminative for the patch's appearance.

As we are given only a single rendered view for each 3D chair viewpoint, following [28] we learn the weights w q by training an exemplar classifier using the patch q as a single positive example (with label y q = +1) and a large number of negative patches x i for i = 1 to N (with labels y i = -1). As we have a large number of patches q (in our case close to 1 million patches), we compute w q analytically via Linear Discriminant Analysis (LDA). Recent works [START_REF] Gharbi | A Gaussian approximation of feature space for fast image similarity[END_REF][START_REF] Hariharan | Discriminative decorrelation for clustering and classification[END_REF] have shown that linear HOG-based object detectors computed with LDA can reach similar object detection accuracy as detectors learnt by expensive iterative SVM training [28]. The resulting w q has the following form [START_REF] Aubry | Painting-to-3D model alignment via discriminative visual elements[END_REF][START_REF] Gharbi | A Gaussian approximation of feature space for fast image similarity[END_REF][START_REF] Hariharan | Discriminative decorrelation for clustering and classification[END_REF]]

w q = Σ -1 (q -µ n ), (2)
where

µ n = 1 N N i=1 x i and Σ = 1 N N i=1 (x i -µ n )(x i - µ n ) T are
estimated from a large set of HOG descriptors {x i } extracted from patches that are sampled from a set of ("negative") photographs independent of all images considered in this work. As noted in [START_REF] Aubry | Painting-to-3D model alignment via discriminative visual elements[END_REF][START_REF] Gharbi | A Gaussian approximation of feature space for fast image similarity[END_REF] the weights obtained from LDA can also be derived analytically from a least-squares cost function, with the resulting weights differing from the LDA weights by a constant scale factor. Using weights (2), the similarity score (1) can be re-written [START_REF] Aubry | Painting-to-3D model alignment via discriminative visual elements[END_REF] as

S q (x) = Φ(q) T Φ(x) -Φ(q) T Φ(0), (3)
where Φ(x) is the "whitening" transformation given by

Φ(x) = Σ -1 2 (x -µ n ). (4)
Note that the first term in (3) is a dot product between whitened q and x and the second term is an additive scalar factor, which is independent of x. As a result, another way to see our matching method is that, for a given q, it ranks patches x using the dot product between whitened q and x as the similarity measure. Other similarity measures such as normalized cross-correlation between whitened q and x also could be potentially used [START_REF] Doersch | Mid-level visual element discovery as discriminative mode seeking[END_REF].

To cope with the millions of patches in the set of rendered views of the 3D chairs, we aim to select a few of the most discriminative ones in each view (dubbed discriminative visual elements). Similar to [START_REF] Aubry | Painting-to-3D model alignment via discriminative visual elements[END_REF] we assume that patches, which have the smallest probability under the Gaussian approximation of the negative patch distribution, are the most discriminative. Since the "whitening" transformation given by eq. ( 4) takes this Gaussian to a unit covariance Gaussian centered at the origin, patches in the whitened space furthest from the origin are considered most discriminative. For a patch q from a rendered view, this can be measured by taking the square of the norm of the whitened patch Φ(q) 2 . This whitened norm can also be viewed as the Bhattacharyya distance between the Gaussian approximations of the positive and negative data. Finally, it can be shown [START_REF] Aubry | Painting-to-3D model alignment via discriminative visual elements[END_REF] that patches with larger whitened norm are better separated from the negative training data in terms of the least squares cost.

To select the discriminative visual elements, we densely compute the squared whitened norm response at multiple spatial scales. We select 10 visual elements per rendered 3D view having highest response after non-maximum suppression. For non-maximum suppression, we used an intersection area to union ratio of 0.25. We require the visual elements to be square patches and filter out patches less than 100×100 pixels. This filtering removes small spurious noisy patches while ensuring good coverage of the object. We used the publicly available implementation of HOG from [14] and extracted contrast insensitive features from 10 × 10 HOG cells, resulting in a 900 dimensional feature vector. We also set to zero components of w q corresponding to spatial bins with sum of the absolute value across the HOG channels less than 0.01. This effectively downweights the background (white) pixels in the rendered views and focuses the detector weights on the foreground chair. We found without this normalization the visual element detector tends to have high score for constant intensity regions in the input image.

Discussion. As demonstrated in section 4, this procedure outputs reliable matches between the rendered views and cluttered photographs. The success can be attributed to three main factors. First, both images and synthesized views are represented by mid-size HOG descriptors. This captures object boundaries in a "soft" manner without attempting to explicitly detect object edges, which is difficult to do reliably, especially in cluttered photographs. Second, the discriminative matching procedure further enhances the salient boundaries in the specific image region by re-weighting the different dimensions of the HOG descriptor. Finally, the visual elements representing each view are chosen to be distinctive and thus more reliably detectable in the photographs.

Calibrating visual element detectors

As noted in prior work [START_REF] Aubry | Painting-to-3D model alignment via discriminative visual elements[END_REF]28], calibration of matching scores across different visual element detectors is important for the quality of the final detection outputs. As we learn more than 800K element detectors independently, we found careful calibration of their scores to be critical. We address this issue by running all detectors on a common large dataset of 200K negative patches that do not contain the object of interest. In detail, we use an affine calibration of the linear classifier of Equation (1):

S ′ q (x) = a q S q (x) + b q , (5)
where for each visual element detector we seek to find the scalars a q and b q .

We recover the calibration parameters with respect to two operating points. To select the first operating point, we run the visual element detector on 200K patches that are randomly sampled from the negative image set, which is known to not contain any chairs. We select the negative patch x n that yields a false positive rate of 0.01%, i.e., x n is the patch having the 99.99 percentile detection score. We choose as the second operating point µ n the mean HOG feature vector. Given these two points, we set S ′ q (x n ) = 0 and S ′ q (µ n ) = -1. This calibration leads to the expected false positive rate of 0.01% when S ′ q (x) = 0. We found this to be a good compromise between representing the tail of the score distribution and the amount of time to scan the negative data.

Matching visual element spatial configurations

For the final object detection, we wish to enforce a consistent spatial layout of the visual element detections corresponding to a rendered 3D view. We assume a star model for the spatial layout, similar in spirit to [14]. The star model provides spatial constraints, while allowing for small spatial deformations. Moreover, the star model can be run in a sliding-window fashion, enabling detection of multiple object instances in the scene.

More concretely, for all of the visual elements for a rendered 3D view we compute a dense response map across different spatial scales of the 2D input image. For each visual element, we consider the 2D patch locations whose response exceeds a threshold τ = 0.2. We anchor these patches as the root for the star model and compute the detection scores of the remaining visual elements centered around their expected 2D locations relative to the root patch. We perform a local search in a 3×3 HOG cell grid around the expected locations and return the maximum response. The final score is the sum of the visual element detection scores given by Equation (1). Note that we require all visual element detections to come from the same synthesized view, which provides a strong constraint on the viewpoint and style consistency of the detected chair. We found this matching procedure to work well, though the view and style consistency constraints can be potentially relaxed to accumulate matches across multiple close-by views or models with a similar style.

We perform non-max suppression on the resulting bounding boxes in the following manner. Starting from the most confident detection in the image we (i) remove all other detections that overlap this detection with more than 0.5 area ratio overlap but only (ii) downweight (not remove) the remaining detections with non-zero overlap. This procedure is then iterated starting from the next remaining most confident detection. We found this strategy removes well overlapping false positives while preserving highly confident (and correct) close-by detections (e.g. chairs around a table). This motivates a system that would reason about the entire scene jointly.

Results

In this section we show qualitative output alignment results of our system and quantitatively evaluate our approach on images from the challenging PASCAL VOC dataset.

Qualitative results. In Figure 2 we show example output alignments of our algorithm. Notice that our algorithm can detect many different styles of chairs in different poses. For many cases, the predicted chair matches closely the input depicted chair style and pose. In many other cases a similar style is returned, often retrieving an accurate partial match to the depicted chair. Moreover, our approach shows some robustness to background clutter, partial occlusion, and cropping.

In Figure 3 we compare the output of our algorithm with the Deformable Parts Model (DPM) [14]. While the DPM correctly predicts the 2D location of the depicted chairs, along with the 2D locations of its parts, our algorithm pro-duces a more informative result. The aligned 3D chair pose and style allows for true 3D reasoning about the input scene.

For a given chair detection, often there is a set of related, highly confident 3D chair alignments having the same pose and similar style. We visualize these similar chair alignments in Figure 4. Notice that the styles are similar, often sharing one or more 3D parts. This suggests that when there is not an exact style match in the database a composite representation could be used to explain the entire input chair by composing well-matching 3D parts from different 3D chairs. Results for the entire dataset are available on the project webpage [2].

Quantitative evaluation. We report detection precisionrecall on images marked as nonoccluded, nontruncated, and not-difficult in the chairs validation set. While this is an easier set compared to the full validation set, nonetheless it is very challenging due to the large intraclass variation, chair poses, and background clutter. Note that removing these difficult examples nonetheless yields some partially-occluded and truncated chairs, as seen in Figure 2. The resulting set contains 179 images with 247 annotated chairs. In Figure 5 we report full precision-recall curves for our algorithm and compare it against two baselines: (i) DPM [14] and (ii) a root template detector using the LDA version of Exemplar-SVM [28]. We train the root template exemplar detector using the whitened HOG formulation in Section 3.1 assuming a single root template that covers the entire 3D chair for the given viewpoint. We calibrate the template as described in Section 3.2. During detection we run the template in a sliding-window fashion across the input image.

Our approach achieves an average precision (AP) of 0.339 on this task. The DPM and root template exemplar detector baselines achieve AP 0.410 and 0.055, respectively. Our performance is noteworthy as it does not use any of the our algorithm with DPM for the detection task. For this we estimated an affine transformation for the DPM scores to calibrate it in the range of our returned scores. For overlapping detected windows for the two methods, we give one twice the confidence and discard the other. Combining our approach with DPM yields an AP of 0.452, which significantly out-performs the state-of-the-art DPM baseline.

We performed a user study to evaluate the quality of the output alignment and returned chair style. For correct detections at 25% recall, users were asked to label the alignment as "Good" (the returned alignment has very similar pose as the depicted chair) or "Bad" (the alignment is incorrect) and to label the returned chair style as "Good" (the returned chair style is an accurate match), "Ok" (part of the returned chair matches the depicted chair style), or "Bad" (no style match).

We report the results of the user study evaluating the quality of the returned alignments and chair styles in Table 1. We compare against the root template exemplar baseline and out-perform it on both tasks. The fact that the number of exact matches is only 3% for the baseline exemplar detector suggests that there are just too many variations within the chair category. This also motivates using a part-based approach since we are able to obtain high quality partial matches, allowing us to find a close-by chair, whereas the root template detector (Exemplar-LDA baseline) must match the entire chair at once. We found that it was somewhat difficult to judge the returned styles from the exemplar-LDA baseline since the matches were not as good.

Finally, we quantitatively evaluated the accuracy of the estimated chair orientation. For this, we manually annotated the azimuth angle for the same set of detections as used in the user study. Our algorithm returns an azimuth angle within 20 • of the ground truth for 87% of the examples. The complete distribution of the orientation errors is shown in figure 6.

Failure cases. In Figure 7 we show common failure modes of our algorithm. We observed two main causes for false positives. First, some of the database chairs have a particular texture that can produce confident detections on textured regions, such as the rear view of the chair matching the checkered window pattern in Figure 7(a). Second, there exist many regions in images that, through the eyes of a HOG descriptor, appear as a chair, as seen in Figure 7(b). We also observed this effect in estimating the pose of the chair, which resulted in confusing the front/back of the chair, as seen in Figure 7(c). The chairs our algorithm miss are mainly special chair types, such as sofa-like chairs, for which we do not have training examples, and chairs strongly occluded by other objects and people.

Computational cost. Computing the discriminative elements takes 6 seconds per rendered view (1 second for ex-traction and 5 seconds for calibration) on a single machine, which can be performed offline and parallelized. The main bottleneck is having to match and align an image to the large number of rendered views from the 3D models, which involves detecting over 800K discriminative visual elements. Our Matlab implementation matches and aligns an image in 2 minutes on an 80-core cluster. While this computational complexity is high, there is room for optimism that our approach can be made significantly more efficient. For instance, the recent part-based hashing technique of [START_REF] Dean | Fast, accurate detection of 100,000 object classes on a single machine[END_REF] could be directly applied to our algorithm by applying winner-take-all hashing [START_REF] Yagnik | The power of comparative reasoning[END_REF] on the discriminative visual elements. As we have a similar number of part detectors as considered in their work, we believe we can process an image in less than 20 seconds on a single multicore processor.

Conclusion

We have demonstrated successful detection and alignment of 3D CAD chair models to chairs depicted in 2D imagery. Our approach relied on matching spatial configurations of mid-level discriminative visual elements extracted from a large database of CAD models having a large number of rendered views. Our algorithm is able to recover the chair pose, in addition to its style. We evaluated our approach on the challenging PASCAL VOC dataset and showed that, when combined with the output of the deformable parts model detector [14], we are able to achieve higher detection accuracy than using either method alone. We also demonstrated that our algorithm is able to reliably recover the chair pose and style, as shown in our user study and orientation error analysis. The output alignments produced by our system open up the possibility of joint 3D reasoning of the depicted objects in a scene toward the larger goal of full 3D scene understanding.

Figure 2 :

 2 Figure 2: Our output alignments. Parts are colored based on their detection confidence (warmer colors are more confident). Please see additional results on the project webpage [2].

  : 0.055) DPM (AP: 0.410) Ours (AP: 0.339) DPM + Ours (AP: 0.452)

Figure 5 :

 5 Figure 5: Precision-recall We evaluate the detection accuracy of our algorithm on the PASCAL VOC 2012 dataset [1].We report detection precisionrecall on images marked as nonoccluded, nontruncated, and not-difficult in the chairs validation set. While this is an easier set compared to the full validation set, nonetheless it is very challenging due to the large intraclass variation, chair poses, and background clutter. Note that removing these difficult examples nonetheless yields some partially-occluded and truncated chairs, as seen in Figure2. The resulting set contains 179 images with 247 annotated chairs.

  (a) Input images (b) DPM [14] output (c) Our aligned outputs (d) Retrieved 3D chairs

Figure 3 :

 3 Figure 3: Comparison of our algorithm output with the deformable parts model (DPM) [14]. While the DPM correctly predicts the 2D location of the depicted chairs, along with the 2D location of its parts, our algorithm is able to predict the 3D pose and style of the chair.

Figure 4 :

 4 Figure 4: For each image (left), we show the most confident matches (right). Even if we do not have an exact match in our dataset, our algorithm returns meaningful matches.

Figure 6 :

 6 Figure 6: Azimuth angle error.

Table 1 :

 1 PASCAL VOC training images. We investigated combining Results of user study to evaluate the goodness of the alignment and style recovery. The data used in the user study appears on the project webpage [2].

		Alignment		Style
		Good Bad	Good	Ok	Bad
	Exemplar-LDA 52% 48%	3%	31% 66%
	Ours	90% 10%	21% 64% 15%

Acknowledgments. We are grateful to the anonymous reviewers for their constructive comments. This work was partly supported by the EIT ICT Labs, MSR-INRIA laboratory, ANR project SEMAPO-LIS (ANR-13-CORD-0003), ONR-MURI Grant N000141010934 and Google Research Grants.