Rehema Baguma
email: rbaguma@cit.mak.ac.ug

Marko Myllyluoma
email: marko.myllyluoma@nokia.com

Nancy Mwakaba
email: ext-nancy.mwakaba]@nokia.com

Bridget Nakajubi
email: bridget@applab.org

Usability and Utility Needs of Mobile Applications for Business Management among MSEs: A case of Myshop in Uganda

Keywords: Usability, mobile applications, utility, MSEs, MyShop, business management

This paper discusses the usability needs of mobile applications for basic business management for Micro and Small Scale Enterprises (MSEs) in developing countries. This is based on results from a user study carried out in Uganda on 30 MSEs. The study was carried out on MyShop, an easy to use mobile business management application for cash transactions and book keeping designed for micro-entrepreneurs. The study investigated learning to use MyShop, the support MyShop gives to the user and its usefulness, and value addition to users. The study also covered the pleasure and stimulation MyShop gives to users. Results from the study show that MSE owners/shopkeepers would like an application that is easy to use such as have an intuitive navigation and a simple and clear language. They would also like an application that supports their unique context like multiple people operating a shop, selling goods on credit, ownership of multiple businesses, use of low end phones and regular load shedding. In terms of value addition, MSEs would like the application to assist them in managing the daily operations and developing the business in the long term such as marketing, time saving and control over business.

Introduction

Micro and Small Scale Enterprises (MSEs) play important roles in the economic growth and sustainable development of every nation [START_REF] Moore | Managing small business: An entrepreneurial emphasis[END_REF]. The development and growth of MSEs can provide solutions to the problem of high unemployment facing many countries especially developing countries. [START_REF] Maseko | Accounting practices of SMEs in Zimbabwe: An investigative study of record keeping for performance measurement (A case study of Bindura)[END_REF] noted that MSEs have low start-up costs, low risk and can exploit untapped knowledge bases of creativity in the population for new product development. According to East African Community (EAC) (2010), MSEs are often considered a key source of productivity, growth and job creation. They promote equitable distribution of income because they are owned by relatively low income entrepreneurs, most of whom are women. MSEs are therefore important instruments for both income distri-bution and equitable participation in the process of economic development. For governments, well-managed and healthy MSEs are a source of revenue in form of taxes. Uganda has 0.8 million MSEs that contribute 20% to GDP and employ over 1.5 million people (EAC, 2010). In Uganda, MSEs are categorized according to number of employees, value of capital investments and turn over as follows: From EAC (2010)

As mobile phones are multiplying in the developing world, many social economic services and applications are being innovated by Mobile Network Operators (MNOs), not for profit and for profit organizations. Hellstrom (2010) noted that in a region where the vast majority have limited resources among other constraints, mobile phone solutions provide a means of extending a number of services to the poor who are in rural and remote areas. However, Corbett (2008) remarked that as sales, access, and coverage continue to grow, it is yet to be seen whether the mobile phone technology will play a significant, sustained role in alleviating poverty in the developing world.

In most developing countries such as Uganda, while operators' focus has been people with a high disposable income and revenue generating services like urban youth and entertainment, services and development oriented applications have not been prioritised. Therefore the number of relevant applications for economic and social development is still limited. On the other hand, efforts to develop mobile applications for banking and managing business internationally have been focused on applications for high end phones such as iPhone (e.g. Mint and Splash Money), Android (Xero) and ipad (quickbooks mobile). These sophiscated mobile applications are out of reach for MSEs in developing countries due to their high cost, hi-tech nature (most MSE owners are computer illiterate), energy efficiency (battery consumption) and data dependency (online connection). As a result there is need for applications that can run on low end phones that most MSEs in developing countries use. In addition, most available applications are mainly about personal financial activities such as banking than managing business activities of a business. For example iPhones's Ledger Docs is used for digital capturing of ledger receipts. Mint, another iPhone application, updates account balances, transmits real-time alerts to the phone for low account balances, over-budget, and tracks strange buying and selling activity. Android's Xero keeps the user updated about business finances and cashflow, creates real time reports as well as integrated invoicing for precision management.

To Hence little so far has been done about using mobile phones for business management. Palsey (2011) reports about a mobile book keeping application developed as part of her Honours studies to enable MSEs keep records of their business transactions and automatically generate financial reports. However, the application in question is not available in the public domain. Therefore it is not clear whether it went beyond the university laboratory to be used by the target users.

Business management for MSEs like other business types is important for planning, budgeting and forecasting, taxation, access to finance among other functions. EAC (2010) noted that the quality of information that a firm produces and maintains determines its access to finance. However, EAC (2010) found out that majority of Micro and Small Scale Enterprises do not keep proper records due to lack of appropriate skills. Therefore efforts to provide simple business management tools tailored to the needs and characteristics of MSEs are greatly needed.

This paper discusses attributes for an easy to use and beneficial (utility) mobile application for business management among MSEs in developing countries. This is based on results of a user study carried out in Uganda on MyShop. MyShop is mobile business application for cash transactions and book keeping designed for microentrepreneurs. The study covered ease of use and utility evaluation of MyShop. It investigated learning to use MyShop and the phone (Nokia c3-01), support MyShop gives to the user, the pleasure and stimulation MyShop gives to users and the usefulness, and value addition of MyShop to users.

Nielsen (2012) refers to usability as a quality attribute that assesses how easy the user interfaces are to use. According to Schumacher and Lowry (2010), usability is the effectiveness, efficiency and satisfaction with which specified users can achieve specified goals in a particular environment. Utility on the other hand refers to the design's functionality i.e. whether a product or service does what users need [START_REF] Nielsen | Usability 101: Introduction to Usability retrieved on 1st October 2012 from[END_REF]. Ease of use and utility are equally important and together determine whether something is useful. [START_REF] Nielsen | Usability 101: Introduction to Usability retrieved on 1st October 2012 from[END_REF] noted that it matters little that something is easy to use if it is not what you want and it is also no good if the system can hypothetically do what you want, but you cannot make it happen because the user interface is too difficult. Therefore the attributes discussed in this work are concerned with ease of use and utility needs of mobile applications for business management among MSEs. In particular, this is discussed in the perspective of the MyShop application.

Methodology

The ease of use and utility evaluation of MyShop was carried out on a sample of 30 MSEs dealing in products and services in and around Kampala city, Uganda. The study was conducted between November 2011 to March 2012. The study areas included one urban location and three peri-urban areas namely: Kampala city centre, Kawempe trading centre, Kyaliwajjala trading centre and Natete trading centre. The rationale for selecting one urban location versus 3 peri-urban ones was because most MSEs in Uganda operate in peri-urban and rural areas. The 30 participants were chosen purposively based on the following attributes: ability to read and write in English. The minimum requirement was completion of Ordinary Level (Middle School) but completion of Advanced Level (High School) was preferred. This attribute was important because the application was in English.

The second requirement was ability to use Short Message Service (SMS) or mobile money service. This gave an indication of experience with data applications. In addition, some individual user characteristics were preferred in order to be sure that the participant would perform and fulfill all expected tasks. These included: to attend trainings, willingness to use the application in day to day business, willingness to commit at least 1 hour daily to update information and commitment to meet data collection requirements. Other desired attributes included: located 10 -15 kms from central Kampala, small scale dealing in products and services, 1+ years of operation; 10+ transactions/day, owner operated or employing not more than 5 people and between 200 and 2000 USD start up capital. Three weeks to the beginning of the study, participants were trained (half day) in using the application and phone. After the training, they were given phones loaded with the application to use for three weeks before beginning of interviews. In addition, they were given a user guide covering using the main menu and application settings, and a summary of how each of the application's functions work.

The study was conducted through weekly field visits to the study sites during which, the study team observed how participants were using the application in their cash and book keeping activities. In addition, 3 questionnaires on ease of use, reliability and enjoyment, and utility were administered to participants to elicit quantitative and more detailed qualitative data. There was no requirement for approval from an Institutional Review Board before running the study.

Discussion of Findings

About MSEs that Participated

The study covered one urban area and three peri-urban areas around Kampala city.

The study population was 30 MSEs dealing in products and services. Of the 30 participants, 53% were male and 47% female. Fifty percent had a degree or diploma, 33% had completed Advanced Level (High School) while 17% had completed Ordinary Level (Middle School). All the participants could read and write in English and could use SMS or mobile money. The business premises were located 10-15 KMs from central Kampala and 83% had been in operation for 1+ years. All participating businesses had 10 + transactions/day, were owner operated or employing not more than 5 people and 59% of the businesses were worth 10 million Uganda Shillings and above (approximately $4,200 USD). In the findings discussed below, the names given are not actual names of participants for purposes of protecting the identity and businesses of participants.

Usability and Utility Needs of Mobile Applications for Business Management among MSEs: A case of Myshop in Uganda

This section discusses ease of use and utility needs of mobile applications for business management among MSEs in developing countries. This is based on results from a user evaluation study of MyShop. MyShop was developed by Nokia and has four main functionalities: selling stock (called "Sell"), recording sales and expenses (called "Records"), purchases and inventory management (called "Stock"), and monitoring of business performance over time (called "Reports"). It is available for free in Nokia's online store on http://store.ovi.com/content/249179. The needs discussed are categorized into: ease of use, support to the user, usefulness and value addition to MSE owners/shopkeepers and the pleasure, and stimulation to the user. According to the Webster online dictionary, ease of use is the property of a product or thing that a user can operate without having to overcome a steep learning curve. High ease of use makes products or systems intuitive to use to the average user.

In the context of computer/mobile applications, ease of use simply means an application that is effortless to understand, find what is needed and do what one wants to do. In addition, the user's context such as characteristics of the environment, language preference, cultural or community practices, unique business characteristics, etc., need to be understood and supported for better usability. These attributes are categorized as support to the user in this work. Further more, for a product, service or system to be useful, it should be both easy to use and of value to the users [START_REF] Nielsen | Usability 101: Introduction to Usability retrieved on 1st October 2012 from[END_REF]. Hence value attributes are also important and are classified as value to the users in this work. Besides ease of use, supporting users' context and being of value, a product, service or system should be pleasing and motivating to users to succeed.

Ease of Use

This subsection discusses attributes that can make mobile applications for business management effortless to use for MSE owners/shopkeepers. These include: Using the application as transactions happen: MSE owners/shopkeepers prefer to use the application as transactions happen. In the MyShop usability evaluation study, 80% of the shopkeepers interviewed preferred to use the application as transactions happen. They noted that this helps them avoid forgetting details of transactions performed as Mariam, a shopkeeper from Kyaliwajjala trading centre remarked: "I use it as I transact my business throughout the day because I need to ensure that all records have been entered". In line with this need, developers of mobile applications for business management among MSEs need to focus on making it easier and faster to record transactions because efficiency is very important to shopkeepers. Auto computation of tasks such as profits and losses: MSE owners like the auto computation of tasks by computer/mobile applications. This is much easier and less error prone compared to manual computations on paper. Jolly a shopkeeper in Kawempe trading centre equipped: "auto calculation of sales, profits and losses makes my life easy". Intuitive navigation: MSE owners want a well organized interface that they can easily navigate and find functions needed. Participants in the MyShop study found it easy to use the simple navigation structure of MyShop (4 items at the first level and 3-6 items inside each of the screens on the second level). Betty a saloon operator in Kawempe trading centre said: "I like the fact that it is easy to navigate through the application and know where to find what function when I need it". Simple and clear language: MSE owners/shopkeepers would like mobile applications written in simple and clear business management language. This is preferred because most of them have low levels of education and do not have formal training in book keeping. In the MyShop study, 68% strongly agreed that the language used in MyShop is clear and simple which made the application easy to use. Violet, a drug shop attendant in Kawempe trading centre noted: "the application uses simple business language and the English is clear".

Representative icons: Using icons that are a clear representation of intended function makes such applications easy to use for MSEs. In the MyShop study, most participants found the icons used meaningful in relation to the intended function. Jumba, an operator of a crafts shop in Kyaliwajjala trading centre said: "the icons explain well what function they represent e.g. using a symbol of money notes to mean sell clearly shows that whatever is under that function is money coming in". A key thing about the understandability of the icons is that they are not global abstract metaphors but tangible everyday items. For example, instead of a shopping cart, there is a basket and for stock, the initial metaphor of a delivery truck, was replaced with a pile of boxes.

Easy to learn: MSEs find applications that are easy to learn easy to use. In the MyShop research study, 24% strongly agreed and 48% agreed that learning MyShop was easy which made use of the application easy. This was attributed to the ease of finding functions, simple and clear language, representative icons and an easy to operate phone.

Support to the User

This subsection discusses usability attributes that address contextual needs of MSEs from mobile applications for business management. These include; Multiple user accounts: Some MSE owners have employees hence it is important for the mobile application to support multiple user accounts with varying privileges. This will enable shop owners/managers to restrict access to information on certain aspects such as reports. In the MyShop study, 80% of the participants preferred using the application alone (which meant running a parallel manual system) because the version used did not support multiple user accounts. Portability: MSEs prefer the mobile application to a computer application due to its portability. This helps them carry out offsite business management activities like restocking more easily. In the MyShop study, 35% strongly agreed and 57% agreed that they enjoy using MyShop in business partly due to its portability. Agnes, a grocery shop attendant in Kampala city centre noted: "I go with it when shopping for new stock and I use it to remind me about restocking needs". Easy to operate phone: The phone(s) on which the application works must be easy to operate. In the MyShop study, 28% strongly agreed and 40% agreed that the phone on which MyShop was loaded, was easy to use. This was attributed to the semi-touch screen phone (small touch screen and large physical keys) and participants' previous experience with other Nokia models. Isaac, a video library operator in Kawempe trad-ing centre noted that: "It is very easy to find functions with the touch screen". This finding is not isolated because White (2010) noted that less educated and less technology savy mobile phone users find touch screens easier to use because they directly manipulate interface objects rather than using third party interaction aids like a mouse and keyboard. Short introduction to bookkeeping: EAC (2010) in a study about MSEs in E. African countries found that majority of micro and small enterprises do not keep proper records due to lack of appropriate skills. In the MyShop study, the "Reports" module was used less because most participants confused the "Records" module to offer similar functions to "Reports" and or did not understand how it works. For example Christine, a beverages shop operator in Kyaliwajjala trading centre said: "I really did not understand how the reports function works and since I can assess the business performance with records then I do not need to use reports". The user manual in the version of MyShop used did not cover book keeping. Including an introduction to book keeping in the help module, can benefit those new to book keeping concepts.

Provide cloud or local backup storage:

To prevent against data loss in case of loss of the phone or a problem with the hardware or software, it is important to provide for data back up locally or in the cloud. The MyShop version that was used in the study did not have this provision. Device independence: It is important to make such applications compatible with low end phones so that users are not limited on device choice. In the study, the Nokia c3-01 used had a short battery life (which was a problem to participants due to regular load shedding). In addition, Nokia c3-01 costs approximately USD 200 hence is expensive for most MSE owners but the current version of MyShop runs on lower end Nokia devices that cost as low as USD 50.

Provide for selling services: The MSE sector has both product and service businesses with varying operational procedures. Therefore it is important for such applications to provide for both. One way is to have a product and service version with services offered and details of offering in the place of stock. The MyShop version used was only applicable to MSEs dealing in physical products such as retail shops. Therefore it was a challenge using it on businesses dealing in services like video libraries. Therefore it is important to make it possible for one install to be used for two or more businesses for example through a multi business edition. Link application to mobile money: Like other business people, MSEs make a lot of financial transactions such as paying suppliers, utilities, employees, receiving payments from customers, etc. However, the banking infrastructure in Uganda like other developing countries is still severely limited and very few people can meet requirements of banking institutions (FinScope, 2007). Participants in the study revealed that some of the payments they make in their businesses such as paying suppliers, rent, and receiving payment from some customers are settled using mobile money. Therefore such a function would make the application more useful and relevant for MSEs.

Usefulness and Value addition to MSE Owners/Shopkeepers

This subsection discusses attributes that address relevancy and value addition attributes MSEs desire from mobile applications for business management.

Marketing function: MSEs would like an application that can on top of basic book keeping, perform related functions such as marketing. This can be achieved through mass dissemination of marketing information via Short Message Service (SMS) or multimedia messaging. During the study, some participants used the phone camera to take pictures of their stock for marketing to potential customers. Moses, an operator of an arts and crafts shop in Kyaliwajjala trading centre noted: "I take pictures of current stock and sold out items to show to potential customers". Reduction of workload: MSEs would like an application that reduces their work load thereby making work easier. 60% of the study participants agreed that using MyShop had made work easier in their business such as in stock taking and tracking profits and losses. Deborah, a supermarket operator in Kyaliwajjala remarked: "I track the stock automatically within the application which less tiresome". Time saving: MSEs desire applications that help them save time in the management of their businesses creating more efficiency. In the study, over 60% agreed that MyShop saves time in business management because of automated functions. Joshua an airtime supplier from city centre remarked that: "MyShop has promoted efficiency in business information recording/book keeping". Safe keeping of business information: MSEs would like an application that keeps their business information safe and secure. Katende, a shopkeeper in Kawempe trading centre remarked: "My business is individual therefore I like it that MyShop keeps my business information away from third parties". Therefore it is important for such applications to restrict access to some information like reports. Control over business: MSEs would like the mobile application to help them better control their business such as keeping track when away and easy assessment of performance. Jackson, a mobile video and disco operator in Natete trading centre noted: "the business' performance is easily assessed since everything is automated". This can be further enhanced by making the app an online service that syncs across multiple shopkeepers so that the business owner can monitor while away.

3.1.4

Pleasure and Stimulation to the User

This subsection discusses attributes that will make mobile applications for business management pleasing and motivating to use for MSE owners/shopkeepers. Exciting experience: MSE would be attracted to an application that gives them an exciting experience. This can be achieved through adaptation of the application to their business needs. In the MyShop usability study, 17% had an extremely exciting experience while 62% had an exciting experience. This was attributed to relevancy of MyShop and the semi-touch screen phone which most of them were using for the first time. Miriam a shopkeeper in Kyaliwajjala trading centre said: "MyShop helps me make business decisions based on facts e.g. every day, I look at MyShop to find out what needs restocking before I restock". Enjoy using the application: MSEs would like an application that they enjoy using.

To achieve this, the application must be relevant to their needs and context. In the MyShop study, 35% strongly agreed and 57% agreed that they enjoy using MyShop in business due to its portability and auto computation of tasks. Doris, a mini supermarket operator in Kyaliwajjala said: "I go with it when shopping for new stock and I use it to remind me about restocking needs".

Conclusion

The potential value of Mobile applications for business management among MSEs is enormous but for this to be realized such applications must be usable and have high utility to the target MSEs. For MSEs in developing countries such as Uganda, such applications must be effortless to use, relevant to the needs and context of MSEs add value to their businesses and be pleasurable and stimulating to use. Future efforts on such applications should focus on usability and utility for the target market segments.

  -date, most research on MSEs and mobile phone usage has been focused on the communication function of the phone and mobile commerce. Examples of such include; Kwaka (2012) who reports about mobile phone usage by MSEs in semi-rural Ghana; Melchioly and Aebø (2010) reports about added value concerning economic growth and entrepreneurship to SMEs in terms of communication with suppliers and customers, market solicitation, social cohesion and operational cost reduction; Es-selaar et al (2008) reports on ICT usage and its impact on profitability of SMEs in 13 African Countries. Others are Escobari and Donner (2009), Matambalya and Sussana (2012), Dorflinger et al (2009), Edim and Muyingi (2010) and Giridher et al (2009).

Table 1 :

 1 MSE Definition used in Uganda

		Number of Em-	Capital Investments (Max	Revenue (Max in UGX)
		ployees (Max)	in UGX)
	Micro	4	12m (USD 4800)	12m (USD 4800)
	Small	50	360m (USD 144000)	360m (USD 4800)

Provide for credit transactions:

  Selling on credit is a common practice especially for retail shops in Uganda and other African countries. The MyShop version used in the study did not have this provision and participants expressed a need for it. Betty, a cosmetics shop operator in Kawempe trading centre said: "It is very difficult to keep track of items sold on credit, yet we sometimes offer goods to on credit". Local language version: Most MSE owners are not comfortable with English due to low levels of education. UNESCO (2007) reported that one of the challenges of delivering mobile phone based services is that 41% of the population in developing countries is non-literate and even the literate among the poor are typically novice users of computer technologies. Due to this limitation, the study purposively selected participants whose level of education ranged from Ordinary Level (Middle School) and above. Therefore for this application to succeed in the market like Uganda there is need for it to have a version in a language. In the study, participants requested for a version in Luganda, the most dominant local language in Uganda.

	Natete trading centre said: "I have a video library and a phone accessories shop
	hence I would prefer being able to use one copy of MyShop for both businesses".
	Use one install for two or more businesses: Multiple business ownership is common
	among business people in Uganda and Africa. Ronald, a video library operator in

Acknowledgements

We extend our sincere thanks to Nokia that allowed us to use results from an originally non-academic usability evaluation study on MyShop in Uganda. We also extend thanks to Grammeen Applab-Uganda Office in particular Sean Paavo Krepp, the Country Director and Annete Bogere, the Content and Services Manager. Grammen-Applab coordinated the study in Uganda as a local partner on behalf of Nokia. Our since thanks also go to Gabriel White who worked as a User Experience Consultant and Richard Nuwagaba, and Andrew Gagwera who worked as Research Assistants on the study.


Christine Solnon
email: christine.solnon@liris.cnrs.fr

Jean-Michel Jolion
email: jean-michel.jolion@liris.cnrs.fr

Generalized vs set median strings for histogram-based distances: algorithms and classification results in the image domain

Generalized vs set median strings for histogram-based distances: algorithms and classification results in the image domain

Christine Solnon, Jean-Michel

of Levenshtein, the set median string may be computed in polynomial time, whereas the computation of the generalized median string is a NP-hard problem [START_REF] De La Higuera | Topology of strings: Median string is np-complete[END_REF][START_REF] Sim | The consensus string problem for a metric is npcomplete[END_REF].

In this paper, we focus on three histogram-based distances for strings: the first one, called d H , considers strings as sets of symbols and is basically defined as a sum of differences of distributions of symbols; the second one, called d Hω integrates a notion of order by associating weights to positions in strings; the third one, called d Hω,c , biased distances with individual substitution costs of symbols occurring at a same position, in order to express the fact that some symbols are rather similar, whereas some others are very different. These three histogram-based distances have the same computational complexity, which is linear with respect to the size of the strings and the alphabet, and are an order quicker than the edit distance.

A goal of this paper is to study statistical characterizations of sets of strings when considering these histogram-based distances. For the first two distances, we show that the generalized median string can be computed efficiently; for the third one, that biased histograms with individual substitution costs, we conjecture that this is a NP-hard problem, and we introduce two different heuristic algorithms for approximating it.

An application in image classification is proposed as an illustration of these results.

Background

Notations

The alphabet is noted A and symbols of A are noted α i with 1 ≤ i ≤ |A|. Strings are finite length sequences of symbols from A and are noted s j with j ≥ 1. The set of all strings from A is noted A * . The length of a string s j is noted |s j |, and the k th symbol of a string s j is noted s k j .

Statistical characterisation of a set of strings

Let d : A * × A * → R + be a distance or a dissimilarity measure for any pair of strings from A (see 3). The first moment, also called generalized median, of a set of strings S ⊆ A * is defined as a string of A * that minimizes the sum of distances to every string of S, i.e., generalized median(S) = arg min

sj 1 ∈A * sj 2 ∈S d(s j1 , s j2 ) (1)
The complexity of the computation of the generalized median string depends on the distance considered. When this complexity is too high, one may approximate the generalized median string by constraining the search to the set S, yielding the set median of S as set median(S) = arg min

sj 1 ∈S sj 2 ∈S d(s j1 , s j2 ) (2)
3 Distances between strings

Edit distance

The most famous distance between strings has been proposed by Levenshtein, e.g., the edit distance [START_REF] Levenstein | Binary codes capable of correcting deletions, insertions and reversals[END_REF]. The edit distance between two strings s j1 and s j2 , denoted by d e (s j1 , s j2 ), is defined by the minimum cost set of edit operations required to transform s j1 into s j2 . Three edit operations are allowed (substitution of a symbol by another symbol, deletion of a symbol, and insertion of a symbol); costs are associated with these operations. A simple algorithm using dynamic programming for computing the edit distance can be found in [START_REF] Wagner | The string to string correction problem[END_REF].

Its computational time complexity is in O(|s j1 | • |s j2 |).
For this edit distance, the computation of the generalized median string is a NP-hard problem [START_REF] De La Higuera | Topology of strings: Median string is np-complete[END_REF][START_REF] Sim | The consensus string problem for a metric is npcomplete[END_REF]. The generalized median string may be approximated by using heuristic algorithms, such as greedy algorithms [START_REF] Martinez-Hinarejos | Use of median string for classification[END_REF] or genetic search [START_REF] Jiang | Median strings: A review[END_REF].

Histogram-based distance d H

An alternative to the edit distance is to consider a sequence not as a string but as a set of symbols. Thus a basic distance between two sets is the comparison of the distributions of symbols defined as:

d H (s j1 , s j2 ) = αi∈A abs(H(s j1 , α i ) -H(s j2 , α i )) (3)
where H(s j , α i ) is the number of occurrences of symbol α i in string s j , and abs is the function that returns the absolute value1 . The main advantage of this distance is its computational cost which is in O(|s j1 | + |s j2 | + |A|)2 . For strings of different sizes, the histograms must be normalized before comparison. For this histogram-based distance, the generalized median string of a set of strings S can be constructed as follows: starting from an empty string, for each symbol α i ∈ A, insert k times the symbol α i to the string, where k is the median value of the set {H(s j , α i ), s j ∈ S}. This generalized median string can be computed in O(|S| • (l + |A|)), where l is the length of the strings of S3 .

Weighted histogram-based distance d Hω

The histogram-based distance d H does not take into account the order the symbols appear in the strings. One could integrate information on the sequentiality of the symbols by using n-grams, thus comparing the distributions of sub-sequences of n symbols. However, in some applications (as the one described in section 5), the order of the symbols in a string may not express a strong sequentiality, but a difference in the importance of the symbols. In this case, the fact that a symbol is just before another symbol is not very significant; the main information contained in the string structuring is the global position of symbols, those at the beginning of a string being more important than those at the end.

In this case of decreasing importance strings, one may associate a weight ω k with every position k in strings. To emphasize differences at the beginning of the strings, this weight may be defined, e.g., by ω k = 1 + l -k where l is the length of the string. To compare strings of different sizes, it is then necessary to complete the shortest string with a new extra symbol until the two strings have the same size.

Hence, we define the weighted histogram associated with a string s j and a symbol α i :

H ω (s j , α i ) = 1≤k≤|sj |,s k j =αi ω k
and the weighted histogram-based distance between two strings s j1 and s j2 :

d Hω (s j1 , s j2 ) = αi∈A abs(H ω (s j1 , α i ) -H ω (s j2 , α i )) (4)
This distance has the same computational cost than the basic histogram-based distance d H . For this weighted histogram-based distance, one can construct a "generalized median weighted histogram" of a set of strings S as follows: for each symbol α i ∈ A, set the weighted histogram value associated with α i to the median value of the set {H ω (s j , α i ), s j ∈ S}. This generalized median weighted histogram can be computed within the same time complexity than for the histogram-based distance, i.e., in O(|S| • (l + |A|)), where l is the length of the strings of S. Note that it may not be possible to construct a string corresponding to this weighted histogram. However, it may be used to statistically characterize a set of strings.

Weighted histogram-based distance with substitution costs d Hω,c

The histogram-based distances d H and d Hω assume that all symbols are "equally different". However, some symbols may be considered as rather similar, whereas some others may be very different. Therefore, [START_REF] Ros | Comparing string representations and distances in a natural image classification task[END_REF] has proposed a new distance, which has the same computational complexity as d H and d Hω , but which is biased with individual substitution costs of symbols occurring at a same position.

This new distance is based on weighted histograms with substitution costs. Given two strings s j1 and s j2 and a symbol α i , these histograms are defined as follows

H ω,c (s j1 , α i ) = 1≤k≤|sj 1 |,s k j 1 =αi ω k • c(α i , s k j2 ) H ω,c (s j2 , α i ) = 1≤k≤|sj 2 |,s k j 2 =αi ω k • c(s k j1 , α i )
where c : A × A → R + is a function which defines the cost of substituting one symbol by another symbol.

Then, the weighted histogram-based distance with substitution costs is defined by

d Hω,c (s j1 , s j2 ) = αi∈A abs(H ω,c (s j1 , α i ) -H ω,c (s j2 , α i )) (5)
Note that this distance is not a metric, and does not satisfy the triangular inequality property.

The fact that the histogram is biased by the individual substitution cost of every pair of symbols occurring at a same position implies that one cannot construct a "generalized median weighted histogram" of a set of strings S, independently from any candidate median string. Therefore, we conjecture that the computation of the generalized median string of a set of strings is NP-hard.

Approximations of the generalized median string for d Hω,c

This section describes two algorithms for approximating the generalized median string of a set of strings S ⊆ A * , when considering the weighted histogram-based distance with substitution costs d Hω,c . We shall assume that all strings of S have the same length l: if this is not the case, it is always possible to complete every string that is shorter than l with a new extra symbol.

Greedy algorithm

The generalized median string of S may be approximated in a greedy way: starting from an empty string s greedy , symbols are iteratively added at the end of s greedy until the length of s greedy is equal to l. At each step, one selects the symbol α i ∈ A that minimizes the sum of distances between s greedy •α i and every string of S (restricted to the |s greedy | + 1 first symbols).

A key point to keep a low time complexity is to incrementally evaluate the sum of distances induced by each candidate symbol. This is done by maintaining, at each iteration l ≤ l:

for every string s j ∈ S, two arrays H j 1 and H j 2 such that for every symbol α i ∈ A:

H j 1 [α i ] = 1≤k<l ,s k j =αi ω k • c(α i , s k greedy ) H j 2 [α i ] = 1≤k<l ,s k greedy =αi ω k • c(α i , s k j )
an array sum such that for every string

s j ∈ S, sum[s j ] = αi∈A abs(H j 1 [α i ] -H j 2 [α i ])
Thanks to these data structures, the choice of the next symbol to add is done in O(|A| • |S|). Each time a new symbol is added at the end of the string, these data structures are updated in O(|S|). As a consequence, the time complexity of the greedy algorithm is in O(l • |A| • |S|).

Local search

The generalized median string of S may also be approximated by iteratively modifying an initial string of length l: at each iteration, a symbol of the string is replaced by a new symbol such that the sum of distances to every string of S is decreased; these replacements are performed until no more replacement can decrease the sum of distances, thus obtaining a locally optimal string that cannot be improved by a simple replacement.

We have compared different strategies (including meta-heuristics such as tabu search) for selecting the next replacement to perform at each step. On average, the best compromise between solution quality and CPU-time has been reached when considering a "first-improvement" strategy, i.e., when selecting the first found replacement that decreases the sum of distances.

This local search process may be started from different initial strings, e.g., from the set median string of S, from the string constructed by the greedy algorithm, or a string which is randomly generated from A * .

The same data structures than for the greedy algorithm may be used to evaluate replacements at low cost. With such data structures, given a position k and a new symbol α i , the replacement of the symbol at position k by α i may be done in O(|S|) so that the time complexity of the local search algorithm is in O(n • |S|) where n is the number of replacements that are evaluated. Of course, n depends on the strategies considered for selecting the replacements to perform and for building the initial string from which starting the local search; it also depends on the length of the string.

Experimental results

Table 1 compares the quality of the different approximations of the generalized median string introduced previously, e.g., the set median string, the string computed by the greedy algorithm (greedy), and the strings computed by the local search algorithm starting from different initial strings, i.e., from the set median string (LS(set median)), the string computed by the greedy algorithm (LS(greedy)) and a randomly generated string (LS(random)). This comparison is done on strings of the SIMPLIcity base described in section 5. This base contains 10 classes of 100 strings of 4000 symbols. The table gives average results on the 10 classes, when successively limiting the length of the strings to the 100, 200, 400, and 800 first symbols. For each length, the table first displays the sum of distances to the set median string, and then, for each approximation of the generalized median string, the percentage of improvement with respect to this sum of distances.

Both greedy and local search algorithms significantly better approximate the generalized median string than the set median string. The best improvements are usually obtained by local search, when it is started from the string generated by the greedy algorithm. Surprisingly, starting local search from the set median string often leads to a slightly worse approximation than starting from a randomly generated string. However, all approximations obtain rather close results.

Table 1 also shows that the larger the strings, the better improvements: when strings are limited to the 100 first symbols, the sum of distances to the greedy approximation is 13.76% as small as the sum of distances to the set median string; when considering the 200 (resp. 400 and 800) first symbols, this percentage of improvement rises to 16.56 (resp. 19.41 and 21.29).

Table 2 compares CPU-times spent to compute the different approximations on a 2.16GHz Intel dual core with a 2MB cache. This table shows us that computing the set median string is more than ten times as fast as computing an approximation with the greedy algorithm, which itself is more than ten times as fast as computing an approximation with the local search approaches. Also, when starting local search from the string generated by the greedy algorithm, CPU time is slightly smaller than when starting from a set median or a randomly generated string.

The quality improvement is thus balanced by the CPU-time cost. However, in applications such as classification of unknown strings in already known clusters, the best representative of each cluster, e.g., the generalized median string, is computed off-line, one-for-all.

5 Classification results in the image domain

Representing images by strings

We introduced in [SJ05] a new representation of images based on strings of symbols. This signature, both precise and compact, is based on notions such as interest points, contrast and order. First, a given image is binarized such that it keeps all the contrasts. Then local maxima of the contrast energy are extracted and associated with their local 3×3 binary neighborhood in the binary image. We thus get a 2D map of symbols, e.g. the 3×3 binary patterns. As any local maxima, e.g. interest points, is also characterized by a measure of contrast energy, we use this measure to sort the points, yielding a string of symbols. The contrast energy measure is no longer kept in the final signature. In this application, the alphabet is made of 512 symbols, corresponding to the 2 9 different 3 × 3 binary neighborhoods.

Note that with this representation of images by strings, the edit distance of Levenshtein is not relevant and gives very disappointing results for classification purposes. Indeed, the edit distance mainly considers the "local" order of symbols -their relative positions-whereas we are more interested in a "global" order of symbols -their global positions in the string, as symbols are sorted with respect to their contrast energy and we consider very long strings: we mainly want to distinguish symbols with high contrast energy, at the beginning of the strings, from symbols with low contrast energy, at the end of the strings. Moreover, the edit distance is an order slowler, which makes it prohibitive on large strings of more than one thousand symbols length.

Test suite and experimental settings

We have performed experiments on the SIMPLIcity database [START_REF] Wang | Simplicity: Semantics-sensitive integrated matching for picture libraries[END_REF] which contains 1000 images of size 384 × 256 extracted from the well known old com-mercial COREL database4 . The database contains ten clusters representing semantic generalized medianingful categories such as Africa people and villages, beaches, buildings, buses, dinosaurs, elephants, flowers, food, forses and mountains and glaciers. There are 100 images per cluster. Each image of the database is represented by a string of 4000 symbols max, as described in the previous section.

For distances d Hω and d Hω,c , which associate a weight ω k with every position k in strings, we have defined ω k = l -k + 1, where l is the length of the strings, in order to emphasize differences at the beginning of the strings.

For the distance d Hω,c , which biased histograms with individual substitution costs, we have tuned costs for this database by a basic adaptive process. Let M be a 512 × 512 matrix initialized to 0. We scan all the possible pairs of symbols (s k j1 , s k j2 ). If the strings s j1 and s j2 belong to the same cluster, M (s k j1 , s k j2 ) is decreased by 1 else it is increased by 1 1-N C where N C is the number of clusters (in order to take into account the a priori probability of two strings to belong to the same cluster). The final cost matrix is then discretized based on the sign of M and we set each cost c(α i1 , α i2 ) to 1 (resp. 2 and 3) if M (α i1 , α i2 ) is negative (resp. null and positive).

We have classified the strings extracted from the SIMPLIcity base according to a nearest neighbour approach: to classify a string, we compute the distance between this string and the representative of every class (the set median, or an exact or approximated generalized median); the closest representative determines the class. We have computed representatives of every class according to a "leaveout-one" principle: the string which is classified is removed from its class before computing its representatives.

We have performed experiments with different lengths of strings: strings extracted from images have 4000 symbols (some strings were shorter, but we have completed them with a new extra symbol); to study the influence of the length of the strings, we report experimental results obtained when limiting the number of symbols to different lengths varying from 50 to 2500.

Experimental results

We now compare the different histogram-based distances (d H , d Hω , and d Hω,c ), and the different statistical characterizations (set median string, exact generalized median string for d H and d Hω , and approximated generalized median string for d Hω,c ), for classifying strings representing images of the SIMPLIcity database.

Table 3 compares global classification rates (GCR), i.e., percentages of strings which have been assigned to the right classes. Let us first compare GCR when classes are characterized by set median strings for the three different histogrambased distances introduced in 3. We note that introducing weights ω k to emphasize differences at the beginning of the strings improves GCR when strings are set median strings (exact or approximated) generalized median strings Length H Hω Hω,c H Hω Hω,c Greedy LS(Greedy) 50 28.4 27.2 35.6 33.2 (+4.8) 33.4 (+6.2) 41.0 (+5.4) 43.9 (+8.3) 100 35.2 34.3 41.4 43.7 (+8.5) 41.0 (+6.7) 45.7 (+4.3) 44.6 (+3.2) 300 44.1 45.3 48.6 60.5 (+16.4) 57.8 (+12.5) 55.0 (+6.4) 56.8 (+8.2) 500 55.3 48.1 52.5 63.8 (+8.5) 61.8 (+13.7) 61.0 (+8.5) 61.7 (+9.2) 800 57.2 52.5 61.9 68.1 (+10.9) 66.4 (+13.9) 65.1 (+3.2) 63.9 (+2.0) 1000 59.5 57.8 60.8 69.6 (+10.1) 67.8 (+10.0) 65.1 (+4.3) 65.3 (+4.5) 1250 62.0 58.4 63.4 69.7 (+7.7) 68.9 (+10.5) 67.4 (+4.0) 66.8 (+3.4) 1500 60.7 61.9 65.5 70.3 (+9.6) 70.5 (+8.6) 68.6 (+3.1) 69.4 (+3.9) 1750 62.9 63.3 63.9 68.8 (+5.9) 71.8 (+8.5) 67.9 (+4.0) 68.7 (+4.8) 2000 57.5 64.3 62.7 63.9 (+6.4) 71.4 (+7.1) 68.2 (+5.5) 68.0 (+5.3) 2500 53.7 61.0 62.6 63.3 (+9.6) 70.1 (+9.1) 66.5 (+3.9) 65.9 (+3.3) avg. 52.4 52.2 56.3 61.4 (+9.0) 61.9 (+9.7) 61.0 (+4.7) 61.4 (+5.1) Table 3. Comparison of global classification rates (GCR) (average results for the 10 classes of the SIMPLIcity base, each class having 100 strings). Each line successively displays the length of the strings, the GCR obtained when representatives are set median strings (for distances dH , dH ω , and dH ω,c ), and the GCR obtained when representatives are generalized median strings (for distances dH and dH ω ), and approximations computed by greedy and local search algorithms (for distance dH ω,c ); GCR obtained with (exact or approximated) generalized median strings are followed in brackets by the improvement with respect to the set median string.

long enough (i.e., for lengths greater than a thousand or so symbols), whereas it decreases GCR for shorter strings. Note also that introducing individual substitution costs significantly improves GCR.

Let us now compare GCR when classes are characterized by exact or approximated generalized median strings. We note that these (approximated) generalized median strings are better representatives than set median strings. However, exact generalized median strings, computed for the distances d H and d Hω , improve more significantly GCR than approximated ones, computed for the distance d Hω,c : on average, the GCR is improved by 9 (resp. 9.7) points for d H (resp. d Hω ) when representing classes by generalized instead of set median strings; however, this GCR is only improved by 4.7 (resp. 5.1 ) points for d Hω,c when representing classes by approximations computed by the greedy (resp. local search) algorithm.

Note finally that GCR obtained with approximations computed by local search are not significantly better than GCR obtained with approximations computed by the greedy algorithm: on average, the GCR is improved of 0.4 points only.

We introduced in this paper three histogram-based distances for strings. For the first two ones, the generalized median string can be computed in polynomial time, and we experimentally show that classification is significantly improved when characterizing classes with generalized median strings instead of set median strings. However, we conjecture that the computation of generalized median strings for the third histogram-based distance is a NP-hard problem, so that we have proposed two heuristic algorithms for approximating generalized median strings in this case. Experimental results showed us that, if classification is improved when characterizing classes with these approximations, they are not as relevant as we would like and improvements are twice as small as improvements obtained with exact generalized median strings. Hence, further work will first concern an explanation of these disappointing results: are they due to the fact that our heuristic algorithms build approximations that are far from optimality, or are they due to the distance itself? Actually, we need information on the distribution of strings with respect to distances. We thus are currently working on the definition of a probability density function on such space and algorithms to approximate this function.

Another trend will be to relate our string-based approach to the more usual graph-based representation of images. Of course, we shall investigate the seriation of a graph-based representation of an image but also alternatives such as graphs or trees of strings, each string being related to a localized area in an image.

Table 1 .

 1 Comparison of approximations of the generalized median string: each line first gives the length of the strings and the sum of distances to the set median string, and then the percentage of improvement of this sum of distances when considering strings computed by the greedy and local search algorithms (average results for the 10 classes of the SIMPLIcity base described in 5, each class having 100 strings).

	Length set median greedy LS(set median) LS(greedy) LS(random)
	100	468.87 13.76%	13.63%	14.28%	14.31%
	200	425.57 16.56%	16.50%	17.20%	16.98%
	400	381.29 19.41%	19.18%	20.06%	19.79%
	800	329.93 21.29%	20.93%	22.09%	21.63%
	Length set median greedy LS(set median) LS(greedy) LS(random)
	100	0.02 0.29	2.59	1.67	2.32
	200	0.03 0.51	5.44	4.40	5.03
	400	0.04 1.01	14.62	10.38	13.35
	800	0.09 2.13	33.45	32.24	34.47

Table 2 .

 2 Comparison

of CPU-times: each line displays the length of the strings and the CPU times (in seconds) spent to compute the different approximate generalized median strings (average results for the 10 classes of the SIMPLIcity base described in 5, each class having 100 strings).

There exists many other different histogram-based distances such as, e.g., kullback-Leibler or Kolmogorov-Smirnov. Our work, based on a distance defined by means of absolute differences of distributions, could be extended to other histogram-based distances as well.

2 In case of very large alphabets, one may use a hashing table in order to consider only the symbols of the alphabet that actually occur in the strings, thus computing the distance in O(|sj 1 | + |sj 2 |)

.3 Note that the median element of a set can be selected in linear time with respect to the size of the set by using a "divide-and-conquer" approach similar to the one used for the quicksort[START_REF] Thomas | Introduction to Algorithms[END_REF]: the idea is to partition the set in two parts containing elements greater than (resp. lower or equal to) a given element; depending on the cardinalities of these two parts, the search for the median element can be recursively continued in one of the two parts.

The SIMPLIcity database can be downloaded on the James Z. Wang web site at http://wang.ist.psu.edu/jwang/test1.tar.


Simon Rit

David Sarrut

Serge Miguet

Gated cone-beam CT imaging of the thorax: a reconstruction study

Keywords: Reconstruction, Computed Tomography (CT), Phantom, Thorax, Gated, Dynamic

In radiotherapy, the respiratory motion of the patient in treatment position is determined from gated cone-beam CT images. This method consists in selecting projections according to a respiratory signal for the reconstruction of a CT image of each respiratory state. This selection can be based on the amplitude or the phase of the signal. The number of selected projections also depends on the width of the gating window. The present study compares different reconstructions using a dynamic digital phantom of the thorax and a known respiratory signal. We applied both regular and irregular motions to this phantom and reconstructed the exhale state using different widths. We evaluated these reconstructions with the signal-to-noise ratio, the contrast-to-noise ratio and a blur criterion. In the case of a regular motion, there was no difference between the amplitude and the phase. The signal quality was high, even for the smallest width, and the blur increased with width. In the case of an irregular motion, the difference was noticeable. Amplitude-based reconstructions suffered from severe artifacts with the smallest width because there were respiratory cycles for which no projection was selected. This drawback is overcome by increasing the width of the gating window. Phase-based reconstructions also allowed to avoid artifacts, whatever the width. But the blur was higher, even for the smallest width applied. These results suggest that the gating process must be adjusted in order to select at least one projection per respiratory cycle. Phase gating is a robust way to achieve this goal when respiration is irregular. Amplitude gating may be more effective in terms of blur, but the width must be carefully chosen to avoid severe artifacts. Finally, we observed the potential of dynamic reconstruction by using a motion model to deform different gated CT images toward a common reference and compute the weighted mean. The resulting CT image suffered less from artifacts than each gated CT image separately even if artifacts were still visible.

INTRODUCTION

In the past few years, there has been an increasing interest of the radiation oncology community in cone-beam computed tomography (CT) scanners mounted on the gantry of medical linear accelerators. [START_REF] Jaffray | Cone-beam computed tomography with a flat-panel imager: initial performance characterization[END_REF][START_REF] Jaffray | Flat-panel cone-beam computed tomography for image-guided radiation therapy[END_REF] This imaging device allows to acquire CT images of the patient in treatment position. Unfortunately, like for other CT scanners, the motion of the patient during acquisition causes artifacts such as blur, streaks and bands. [START_REF] Ritchie | Minimum scan speeds for suppression of motion artifacts in CT[END_REF] The methods available to correct these artifacts can be categorized in 3 classes, depending if they use (1) no motion information, [START_REF] Dhanantwari | Correcting organ motion artifacts in X-ray CT medical imaging systems by adaptive processing. I. Theory[END_REF][START_REF] Helenon | Artifacts on lung CT scans: removal with Fourier filtration[END_REF][START_REF] Spies | Characterization and correction of temporal artifacts in CT[END_REF] (2) only simplified motion information like a respiratory signal, in which case the method is called respiratory-correlated or gated imaging, [START_REF] Dietrich | Linac-integrated 4D cone beam CT: first experimental results[END_REF][START_REF] Kriminski | Respiratory correlated cone-beam computed tomography on an isocentric C-arm[END_REF][START_REF] Li | Four-dimensional cone-beam computed tomography using an on-board imager[END_REF][START_REF] Sillanpaa | Developments in megavoltage cone beam CT with an amorphous silicon EPID: reduction of exposure and synchronization with respiratory gating[END_REF][START_REF] Sonke | Respiratory correlated cone beam CT[END_REF] or (3) precise motion information like a dense vector field or a B-spline model, in which case the method is called dynamic imaging. [START_REF] Blondel | Reconstruction of coronary arteries from a single rotational X-ray projection sequence[END_REF][START_REF] Bonnet | Dynamic X-ray computed tomography[END_REF][START_REF] Grangeat | Theoretical framework for a dynamic cone-beam reconstruction algorithm based on a dynamic particle model[END_REF][START_REF] Li | Motion correction for improved target localization with on-board cone-beam computed tomography[END_REF] Gated cone-beam CT images of the thorax are obtained by using a respiratory signal to sort cone-beam projections depending on their position in the periodic respiratory cycle. [START_REF] Dietrich | Linac-integrated 4D cone beam CT: first experimental results[END_REF][START_REF] Kriminski | Respiratory correlated cone-beam computed tomography on an isocentric C-arm[END_REF][START_REF] Li | Four-dimensional cone-beam computed tomography using an on-board imager[END_REF][START_REF] Sonke | Respiratory correlated cone beam CT[END_REF] This signal can be obtained in different ways, either using an external device [START_REF] Dietrich | Linac-integrated 4D cone beam CT: first experimental results[END_REF][START_REF] Kriminski | Respiratory correlated cone-beam computed tomography on an isocentric C-arm[END_REF][START_REF] Sillanpaa | Developments in megavoltage cone beam CT with an amorphous silicon EPID: reduction of exposure and synchronization with respiratory gating[END_REF] or by image processing. [START_REF] Li | Four-dimensional cone-beam computed tomography using an on-board imager[END_REF][START_REF] Sonke | Respiratory correlated cone beam CT[END_REF][START_REF] Rit | Respiratory signal extraction for 4D CT imaging of the thorax from conebeam CT projections[END_REF][START_REF] Zijp | Extraction of the respiratory signal from sequential thorax conebeam X-ray images[END_REF] The question of the respiratory signal has been addressed in several works [START_REF] Li | Technical and dosimetric aspects of respiratory gating using a pressure-sensor motion monitoring system[END_REF][START_REF] Koch | Evaluation of internal lung motion for respiratory-gated radiotherapy using MRI: part I-correlating internal lung motion with skin fiducial motion[END_REF][START_REF] Simon | Lung volume assessment for a cross-comparison of two breathing-adapted techniques in radiotherapy[END_REF] but the motion is too complex to be simplified by a 1D signal [START_REF] Blackall | MRI-based measurements of respiratory motion variability and assessment of imaging strategies for radiotherapy planning[END_REF] and no definitive conclusion has been drawn. However, even if the respiratory signal is perfect, i.e. if two identical values correspond to two identical positions of the thorax and conversely, it can be used in different ways. The first choice is between the use of Further author information: Simon Rit: E-mail: Simon.Rit@gmail.com, Telephone: (+33) (0)4 78 78 51 50 the amplitude of the signal versus the use of the phase of the signal. Phase is linear between processed positions such as end-exhale and end-inhale. [START_REF] Kleshneva | An algorithm for automatic determination of the respiratory phases in four-dimensional computed tomography[END_REF][START_REF] Lu | A comparison between amplitude sorting and phase-angle sorting using external respiratory measurement for 4D CT[END_REF][START_REF] Wink | Phase versus amplitude sorting of 4D-CT data[END_REF] The second choice concerns the width of the gating window. To our knowledge, no study using digital data has addressed these points.

This study aimed to study the reconstruction of a CT image from a subset of the cone-beam projections selected using a respiratory signal known a priori. We proposed to use a dynamic digital phantom and simulated a set of cone-beam projections using regular and irregular signals. We then analyzed the reconstructions obtained by varying the width of the gating window, based on the amplitude or the phase of the signals. Finally, we studied the potential of dynamic reconstruction by a weighted mean of all gated CT images along the respiratory cycle and subjected to appropriate transformation.

METHOD

Digital phantom

The digital thorax phantom at the exhale state was a simplified version of the Forbild phantom * (figure 1). A spherical tumor having a diameter of 3 cm was positioned in the lower part of the right lung. An analytical transformation was applied to this phantom to obtain the inhale state. This transformation was composed of translations and changes of volume of the different geometric parts of the phantom. Intermediate states between inhale and exhale were deduced linearly with a respiratory signal between 0 and 1.

A dense vector field representing the deformation between end-inhale and end-exhale was computed using the demons algorithm with a Gaussian regularization [START_REF] Boldea | Comparison of 3D dense deformable registration methods for breathhold reproducibility study in radiotherapy[END_REF][START_REF] Sarrut | Non-rigid registration method to assess reproducibility of breath-holding with ABC in lung cancer[END_REF] (figure 1). [START_REF] Lujan | A method for incorporating organ motion due to breathing into 3D dose calculations[END_REF][START_REF] Seppenwoolde | Precise and real-time measurement of 3D tumor motion in lung due to breathing and heartbeat, measured during radiotherapy[END_REF] The second irregular signal was computed using a stochastic adaptation of the model with n = 2, τ = 4 ± 0.5 s, z 0 = 0 ± 0.07, b = 1 ± 0.07. The distribution was normal for z 0 and log normal for b and τ . [START_REF] George | The application of the sinusoidal model to lung cancer patient respiratory motion[END_REF] After computation, it was normalized between 0 (exhale) and 1 (inhale). The sampling period was set to 0.18 seconds. For each motion type, 640 analytical projections were computed regularly along a circular source trajectory using the open-source software Take † . The parameters were chosen to simulate acquisition by an Elekta Synergy system(Elekta Oncology Systems Ltd., Crawley, West Sussex, United Kingdom). 1

Reconstruction

Static 3D reconstruction We implemented the method proposed by Feldkamp et al [START_REF] Feldkamp | Practical cone-beam algorithm[END_REF] for cone-beam reconstruction (figure 3). The limited size of the detector provided truncated cone-beam projections and the resulting artifact was partially corrected using the heuristical method described by Ohnesorge et al. (

(2)

(3) (a) (b) (c)

Gated reconstruction

The gating window determines which projections are used in the reconstruction process according to the respiratory signal. We used a gating window centered on the end-exhale position with a varying width w. We studied two different inputs: the amplitude of the respiratory signal directly, and the phase, obtained by processing the respiratory signal. [START_REF] Kleshneva | An algorithm for automatic determination of the respiratory phases in four-dimensional computed tomography[END_REF][START_REF] Wink | Phase versus amplitude sorting of 4D-CT data[END_REF] End-exhale phase was set to 0%. The phase between two consecutive end-exhale phases is set linearly between 0% and 100% (figure 2).

Dynamic reconstruction

We observed the potential of the use of a more complex motion than just a 1D signal in the reconstruction. Several studies [START_REF] Grangeat | Theoretical framework for a dynamic cone-beam reconstruction algorithm based on a dynamic particle model[END_REF][START_REF] Li | Motion correction for improved target localization with on-board cone-beam computed tomography[END_REF][START_REF] Ritchie | Correction of computed tomography motion artifacts using pixel-specific back-projection[END_REF] have proposed to deform each backprojection of the filtered projection using a motion model. If the motion is discretized into several positions, this is equivalent to computing the weighted mean of the different gated CT images along the respiratory cycle deformed toward a common reference. The weights correspond to the number of projections used to reconstruct each CT image. We know that all the points of the phantom move in phase along a straight line, so the vector field used to deform each image is the one computed in 2.1 weighted by the mean value of the respiratory signal of the selected projections.

Criteria

For a quantitative analysis of the reconstructions, we used three criteria previously defined in the literature. These criteria were applied to a region of interest (ROI) containing the tumor in all positions of the thorax (figure 4).

The signal-to-noise ratio: SNR(dB) = 20 log 10 A signal A noise where A I = 1 P P i=1 x 2 i is the root mean square of the intensity of P pixels in image I, the signal is our reference, i.e. the computed end-exhale digital phantom, and the noise is the difference between the reconstruction to be evaluated and the signal. The blur criterion (BC) proposed by Kriminski et al. 8 This method aims to quantify the blur independently from the noise by using an appropriate energy for a binary segmentation robust to noise. The optimal energy is computed with a graph-cut and used as a blur criterion. More details can be found in the article by Kriminski et al. [START_REF] Kriminski | Respiratory correlated cone-beam computed tomography on an isocentric C-arm[END_REF]

RESULTS

We reconstructed the exhale state using different widths w of the gating window, in the presence of a regular or an irregular motion, and based on the amplitude or the phase of the respiratory signals (figure 4). The number N of projections selected by the gating window depends on both the signal and the width.

Regular motion

Results were similar whether using the amplitude or the phase: the SNR, the CNR and the BC gave identical curves (figure 5). The only difference was that amplitude selected more projections than phase for small widths (figure 4) because more time was spent at the extreme states of the respiratory cycle. Signal quality, measured by the SNR and the CNR, slightly increased until 200-250 projections were selected and decreased afterwards. The blur was minimal for the smallest width.

Irregular motion

Results were different whether using amplitude or phase. When using amplitude and the smallest width w = 0.05, no projections were selected from some respiratory cycles. This caused severe visual artifacts (figure 6), confirmed numerically by the lowest values of SNR and CNR and a disturbed BC (figure 5). Results were improved when increasing the width to w = 0.1, a value for which the blur was comparable to the one obtained with a regular motion. No such artifact was found when using the phase, whatever the width, but the minimal blur was higher than the one obtained using amplitude. 2) phase of the respiratory signal. Gray areas at the bottom of the curves correspond to the gating windows and show the position of the selected projections. Severe artifacts are seen in the amplitude-based reconstruction because no projections were selected for some respiratory cycles, i.e. angular portions, which was not the case in the phase-based reconstruction.

Dynamic reconstruction from gated reconstructions

We reconstructed 10 gated CT images obtained with the same window width w = 0.1 and different window centers c in order to select all the projections once, and only once, in all gated reconstructions. This window was applied to the amplitude of the signal to minimize the blur. Table 1 summarizes the number of projections selected for the different motions and the different reconstructions. Figure 7 compares the resulting images with other reconstructions. Figure 8 1. Number of projections selected for a gating window width w = 0.1 and different window centers c, depending on the motion type. The sum of each line is equal to the total number of projections (640), because gating windows are strictly adjacent between 0 and 1.

Dynamic reconstruction significantly improves the quality of the image. SNR and CNR values are close to the reference, i.e. reconstruction with the same number of projections (640) but without motion (figure 8). The blur remains minimal, as in gated CT reconstruction. However, visually, the streak artifacts are not fully eliminated but only attenuated (figure 7).

DISCUSSION

This study of a numerical and dynamic phantom with controllable respiratory signal allows to observe the reconstruction obtained with different widths of the gating window, and variations between the amplitude or the phase of the respiratory signal.

In the presence of a regular motion, amplitude and phase give similar results (figure 5). Minimal width applied to amplitude is a good compromise between the signal quality of the reconstruction and the blur due to the motion. We conclude like Dietrich et al 7 that increasing the width does not significantly increase the signal quality because the additional projections selected are angularly adjacent to the others and, as a consequence, do not fill regularly the angular gaps along the source trajectory. Things are slightly more complicated when the phantom is subjected to irregular motion. The use of minimal width applied to the amplitude of the respiratory signal causes severe artifacts (figure 6). There are two strategies to overcome this problem. The first one is intuitive and consists in increasing the width of the gating window until reaching a good compromise between signal quality and blur due to the motion. But this can be difficult to achieve when using real data. The second strategy is to use the phase of the respiratory signal which equates to deducing a regular signal from the irregular one. This is efficient in terms of signal quality of the reconstructed image because projections are more regularly selected along the source trajectory (figure 5). But, because of the irregular nature of the motion, the reconstruction is based on projections corresponding to different positions of the thorax, which causes blur (figure 5).

The quantitative comparison of the reconstructions obtained with regular and irregular motions is not possible in this case. The observation of the respiratory signals (figure 2) and the number of projections selected for a given width of the gating window (figure 4) and for different motion patterns demonstrate that a lot more projections are available near the exhale position in the case of a regular signal than in the case of an irregular signal. It remains desirable, in radiotherapy, to be able to reconstruct the extreme position occupied by the tumor in both cases, even if this is less likely achieved with an irregular signal than a regular signal. A similar study conducted on an intermediate position in the respiratory cycle would provide interesting complementary results.

If the motion is fully known, one can deform the different gated reconstructions toward a same reference image, calculate the weighted mean and thus obtain clearly better results (figures 7 and 8). Streak artifacts are nevertheless still visible. Dynamic reconstruction assumes that the deformation of each backprojection should conduct to the same result as the reconstruction without motion. This heuristic is false because the analytic formulation of the reconstruction assumes that the integral along the ray follows a straight line. There is yet no analytic reconstruction formula for any complex deformation. Moreover, we simplified the motion model of the respiration by discretizing it in only ten different positions.

CONCLUSION

Figure 1 .

 1 Figure 1. (a) Sagittal, (b) coronal and (c) transverse slices of the digital phantom at the inhale state with computed motion vector field.

2. 2 .

 2 Respiratory signals Two simulated acquisitions of the dynamic phantom were obtained with two different respiratory signals (figure 2). The first regular signal was based on the asymmetric sinusoidal model z = z 0 + b cos 2n (πt/τ ) with n = 2, τ = 4 s, z 0 = 0 and b = 1.

31

 31

Figure 2 .

 2 Figure 2. The first 20 seconds of the (a) regular and (b) irregular respiratory signals with their computed phase (dashed lines). Each point plotted on the curves corresponds to the acquisition of a cone-beam projection.

Figure 3 .

 3 Figure 3. (a) Sagittal, (b) coronal and (c) transverse slices, of the reconstruction using the 640 projections of (1) the static phantom at end-exhale, and of the dynamic phantom with (2) a regular signal and (3) an irregular signal. The artifacts in (2) and (3) are due to the motion of the phantom between cone-beam projections.

  The contrast-to-noise ratio: CNR = | µ foreground -µ background | σ background where µ R and σ R are the mean and the standard deviation of the pixel values in region R. The foreground in our ROI corresponds to the position of the tumor at end-exhale.

Figure 4 .

 4 Figure 4. Coronal slices of amplitude-based and phase-based reconstructed images in the region of interest using different gating window widths w, resulting in the selection of a number N of projections, in the presence of a regular or an irregular motion.

Figure 5 .

 5 Figure5. Signal-to-noise ratio (SNR), Contrast-to-noise ratio (CNR) and normalized blur criterion of the gated reconstruction in the region of interest (figure4) for regular (light green and blue) and irregular (dark black and red) motions based on the amplitude (full lines) or the phase (dashed lines) of the respiratory signal.

Figure 6 .

 6 Figure 6. (a) Sagittal, (b) coronal and (c) transverse slices of (1) amplitude-based and (2) phase-based reconstructions of the phantom using an irregular motion and a gating window width w = 0.05. Curves (d) represent the (1) amplitude and (2) phase of the respiratory signal. Gray areas at the bottom of the curves correspond to the gating windows and show the position of the selected projections. Severe artifacts are seen in the amplitude-based reconstruction because no projections were selected for some respiratory cycles, i.e. angular portions, which was not the case in the phase-based reconstruction.

Figure 7 .

 7 Figure 7. (a) Sagittal, (b) coronal and (c) transverse slices of the reconstructed images with static reconstruction, gated reconstruction or dynamic reconstruction, without motion or in the presence of regular motion or irregular motion.

Figure 8 .

 8 Figure 8. Quantitative criterion applied to the reconstructions displayed in figure 7.

Table

  is a quantitative comparison of the different reconstructions.

	c	0.05 0.15 0.25 0.35 0.45 0.55 0.65 0.75 0.85 0.95
	Regular motion	248	52	45	32	31	32	32	31	45	92
	Irregular motion 104	143	77	54	51	50	48	59	39	15

This study points out the pros and cons of amplitude-based and phase-based reconstructions for gated cone-beam imaging of the thorax. It shows the difficulty of finding a compromise between signal quality and blur. Dynamic reconstruction is potentially very powerful but the achievement of the motion model is still an issue. Future works should address the optimization of acquisition parameters for gated imaging, such as gantry speed, the study of other reconstruction algorithms, particularly for dynamic reconstruction, and a similar comparative study using real data.

ACKNOWLEDGMENTS

This work was supported in part by Elekta Oncology Systems.