IETT, Université Lei Peng

Jean-Moulin Lyon3

The Negotiation of Minority Identities and Representation in the Independent Music Scene of Urban China

This talk shows my efforts to trace a distinctive thread through the practices of two groups in the independent music sector concerning issues of minority identities, representation and new spheres of musical practice in a globalizing China.

I should emphasize in the first place that this talk is not a professional musical analysis of different groups, since I'm not specialized in music. What I attempt to do is to illustrate the negociation of Minority identities and representation in the music of two distinct yet in some respects analogical groups, Hanggai 杭盖 and 3Steps 三跺脚 by investigating the social, cultural and aesthetic aspects of their musical practice. The two groups have been ascribed to a newly emerged musical trend called "xinminyao 新民谣" in a changing China ( xinminyao could be literally translated as neo-folk in English but it implies in fact different meanings in the context of contemporary China, so I would keep the original pinyin form "xinminyao" in this talk in order to distinguish it from the neofolk movement in Europe).

Context and some questions

Before discussing the songs and performances of the two groups in detail, I shall first address the context of their musical practices in terms of the politics and musicculture of the past three decades. As you may know, since the late 1970s, there has been a significant transformation in the People's Republic of China (PRC), the shift to a freemarket economy, and the opening of the country to outside influence' have led to the resurgence of a relevant social and cultural diversity.

The new ideologies, technologies, and mode of economy challenged not only the state, they equally challenged dominant social groups that traditionally have had more control over the means of cultural production and dissemination-dominant groups such as men, members of the Han 汉 majority, and the intellectual elite. As a matter of fact, remapping 1 and renegotiating the ranking of social scales has become a sheer necessity nowadays in any metropolitan Chinese city, not only because hasty, large-scale urban development since the early 1990s has demolished much of the old cityscape and replaced it with similar high-rise buildings and commercial blocks, rendering printed maps inadequate, but also because of the mobility of people, the circulation of capital, ideas and images, technologies, and modes of communication. So today even when people stay in a local place, their subjectivities may be transformed by trans-local 1 Yingjin ZHANG talks about the concept of "remapping" and renegotiating the ranking of social scales in chapter one "Introduction : Cinema, Sphere, Polylocality" of his new book Cinema, Sphere, and Polylocality in a Globalizing China, Hawaii, Universiy of Hawaii Press, 2010.

processes and Internet. The emerging independent music scene since the mid-1990s in China has participated in various projets of remapping the city, of producing urban imaginaries that negotiate changing urban values, and create new spheres where the negotiation between traditional dichotomies such as aboveground/underground, Majority/Minority or region/global become possible.

The Mongolian-based folk group Hanggai 杭盖, who are at the forefront of the ongoing musical trend xinminyao 新民谣 in China that is taking traditional Mongolian folk elements and instrumentations and projects them into a loosely rock-based structure; the Yunnan/Guangzhou-based group 3Steps 三跺脚 combine the traditional music of minorities in Yunnan (the south-ouest Han-Ethnic mixed region of China) with the reggae rhythm of Caribbean. What I try to argue in this talk is that the two groups have participated in the process of establishing an imagined sphere within a new generation of urban youth. I shall call this sphere Minjian 民间 here, (the term minjian could be translated as "among the people", "non-official", or "non-governmental" according to the different contextes), it is actually a third sphere which is based in the city, but "integrates" (not just "puts in") some "rural", "folkloric" or "minority" elements.

Here come some questions I'd like to raise : What is the nature of the so-called xin minyao movement in contemporary China exactly, and how do we practise it? Could this new sphere minjian be employed by the minority people to narrate or negotiate their own life experience instead of assuming an orthodox representation from "above" or the majority culture? Could this "third sphere" created both by the musicians and their audiences not merely negotiate or resist, but also "shape the society" in terms of "composition" argued by Jacque Attali in his inspiring work Noise?2 The consideration of these points remains a task still to be undertaken, apparently there are more questions to formulate than answers to give, but let's keep these questions in mind for the moment, and I'm going to give you some illustrations of music of the two groups.

Hanggai : at home in the world

Hanggai is a Beijing-based group of Mongolian musicians established in 2003, a few of whom are originally from China's Inner Mongolia province' while the other members are original Han, two of the members play the morin khuur (the traditional mongolia horse-hair string instrument), while another plays the tobshuur, another two-stringed traditional lute, they comprise the foundation of their sound' together with some typical rock-based instruments like guitar, base and drum set. The bandleader Ilchi was born in the inner Mongolia but went to settle in Beijing with his family at the age of 12, he was formerly in a Beijing hardcore punk group T9 and put this band together after hearing the traditional khoomei throat-singing technics. Fascinated by the sound of this centuries-old singing style, he went to Inner Mongolia to learn it and finally built-up his new band Hanggai (in Mongolian it means a beautiful place with blue sky and spreading grassland). They combine the deep throat singing with a Western compositional sense of tension and they sing in Mongolian.

Here are some extracts of their live performances in different cities of the world

Illustrations

In the MIDI music festival (30'') -Beijing

http://xiyou.cntv.cn/video/c03f0c54-4475-11df-be82-001e0bbb2454 2. Festival of Sine (1'30'') -Portugal
In this extract, we can easily identify three important elements comprising the music of Hanggai -the deep throat singing technique, the use of tradional Mongolian instruments (the morin khuur) and the rock-based, often rapid and regular rhythm. The throat singing and the traditonal instrumentation have been subtly projected into the accelerated rhythm built by the drumbeat in the background, which distinguish their music from the original or "primitive" local music practice in the region of Mongolia. This ambiguity between the folk and rock give their music a "fresh touch". The regional, traditional folk forms put in the modern (read: westernized) structure has actually created a relatively new listening experience that can be recognised by the urban people with their familiar code.

3. Europalia perfermance (2'03'') -Belgium https://www.youtube.com/watch?v=suBQh4lEKFM

This extract shows clearly how the musicians of Hanggai deliberately use progressive sonic tactics in order to penetrate their music into the heart of their audience.

The first "riff" is composed by a simple round singing in Mongolian accompanied by a three stringed banjo-like instrument, then the drumbeat joined in to provide a regular ryhthm structure; later come the electronic guitar as well as the moring ghruu, we can see that they carefully use the Mongolien symbolic instrumentation with addition of some lelectronic textural elements' established step by step,as a consequence, the music of Hanggai can easily remind the audience about the symbolic elements of a general "Mongolien culture" and get the sympathy of them. 3Steps : sphere of transculturality 3Steps takes its name from a popular local song and dance practice in the southern part of Yunnan province, and brings the traditional elements of minority cultures in Yunnan into a Reggae-based structure. Three members are originally from the minority regions of Yunnan (two are original Bulang 布朗 and one of them is original Dai 傣), together with two other members of Han 汉,Thomas-French and Adam-American,they tried to use the European dub music technique of incorporating electronic sounds and live digital manipulation to intensify their sound. Lyrics in Mandarin, Yunnan dialect, minority dialects, English, and French go further to create a lively dialogue with the audience. 3Steps could be considered as one of the "hybrid communities" or "transcultural sound makers" argued by many scholars recently, they are not national cultural communities, but then, as Tzvetan Todorov has demonstrated, a common culture is not necessarily national and is generally "of a smaller size" and more ever "it can also be transnational."3 Some illustrations:

1. 三跺脚 ("3 Steps") 1'20" This is the beginning of the song which has the same name as the group, we can almost find the same sonic strategy with the music of Hanggai. The song begins with a simple riff performed by the traditional instrument sheng 笙 (which is broadly used in the local musical practice in the region of Yunnan), then the electronic guitar and drumbeat joined in to establish a reggae-based structure, the latter subtly melted in with the sound of sheng, then the vocal in Mandarin entered, which was based on a local Minority song's melody.

撒伊阿卡 ("Sayiaka") 50" 珠江啤酒 ("Zhujiang Beer") 58"

The first extract is sung in the dialect of the Minority, and the chord in the background was an extract of the typical sound in the local practice in some region of Yunnan, while the second was sung both in Mandarin and English. or rock bands and they moved onto this sort of music later on. The major vocal/drum of 3Steps Xiaodao for example, who is originally from a Dai village of Yunnan initially "went out " to the city in order to learn about western percussion in a music school. In this sense, the musical explorations of those musicians seem to be a manifestation of "refinding the culture identity", their musical practices appear not only to a regional /Minority diversity including the different dialects and costumes, the different way of Meanwhile, the frequent audience of the xinminyao performance are basically the urban youth generation, they are living in a globalised, rapidly urbanized China, and are surrounded by the double cultural oppressions. On the one hand, there is the state or "international" sanctioned "cultural heritage" (like the often-mentioned term chuantong wenhua -"traditional culture" or shijie wenhua yichan 世界文化遗产 -"world cultual heritage"). On another hand, there is the trend of the modern popular music coming from "outside" in terms of modernization and globalization (including rock music, world music, etc). 4 As a matter of fact, neither of the two dominant mainstream popular cultures is directly connected to the everyday life experience of those urban youths. So the trend xinminyao emerged from this "fracture", it is actually a "third sphere" in-between that promoted the utopia of a distant "non-official sphere of China", an utopia which I name with the term "minjian 民间",an utopia could encompass the everyday experiences of Chinese urban youth with their longings, desires, hopes, frustrations and leisure needs, make them able to feel an undefined nostalgic longing for something "real" which had to exist somewhere.

花头巾 ("Colorful

However, the audience of xinminyao is not looking for a so-called "authentic regional/Minority folklore" as such neither, they are longing for this "ambiguous third 4

Wei Xiaoshi 魏小石 discussed the notion of minjian 民间 as a production of imaginary, as well as the two dominated mainstream cultures ( the official sanctioned and the globalized popular music trend) nowadays in urban China in his article "Xinminyao zai Zhongguo, shei de huanxiang?" 新民谣在中国,谁 的幻想?,published in the chinese journal Shucheng 书城,2010,4.

sphere namely minjian" where the boundary of "urban and rural" is no more clear, where they can "return to innocence" with their own familiar urban code. Therefore, we can define the "xinminyao" as a production of imaginary by re-coding the "traditional elements" in a modernized way.

Conclusion or some more questions

The success key of Hanggai and 3Steps is their well-balanced deployment between the ethnical/regional uniqueness and the cosmopolitism. Again, like the bandleader of Hanggai annonced in the media : "deep inside our music is still Mongolian, but we want to deliver to the audience the message that we are not a traditional band. We play modern music."

Then comes the question, Hanggai's first album Introducing Hanggai is recorded by two western producers, they resumed their working principle with Hanggai as below:

"Beijing is in northern China, and the grasslands are just outside Beijing, and within the Chinese psyche, that's the wild west, where the cowboys and horsemen are; it's dangerous and exotic. And that whole culture plays a big part in the Chinese psyche, so what we wanted to do was make an album based in the city, thinking about the grasslands -imagining this culture and these songs, from the city."

-Matteo Scumaci & Robin Haller "Chinese Crisis: Recording Hanggai's Folk Music"

These words demonstrate that the two western producers are clearly conscious of their "re-coding" role as well as their mission to "create an otherness" within the "the great China" ideology. Their efforts in musical terms have not weakened or alienated the power of Hanggai's distinctive sound, but rather give the album enough diversity and structure to appeal more especially to Western audiences up to now. Once entered in the global market of music industry, they have been placed within a capitalist ideology and could hardly escape the commodification which always function in the interests of capital, both economically and ideologically. As market activity intensified, there was an increasing demand for minority otherness, which in the cosmopolitan and consumerist environment was transformed into an exotic commodity. So how far can Hanggai's negotiation between a somehow distinct Mongolian identity and the ideology of a "Great China" go? We still need some time and observation to find the right answers.

Nevertheless, another characteristic of xinminyao is the very dynamic interaction between the musicians and their audience en Live. Hanggai play frequently all over the world while 3Steps travelled every year in the mountain areas of Yunnan, they have the constant contact with the local people, and they play, communicate with the local Minority people as well as learn from them in the villages. Through such a mobility of musicians, different information, local practices, values, ideas, ways of life have been circulated simultaneously while the music was being made. At the same time, the dissemination of their music through Internet has provided a wider sphere of communications and possibilities of "transculturality". All of these factors make every single "live performance" a Temporary Autonomous Moment 5 in terms of Hakim Bey, that could hardly "control" or "centralize" by the nationalist or any other "center".

During the "Live show", the marginals, minorities, people with different cultural backgrounds are united, then, in their embracing of a local/regional inclusive culture, they share a marginal sphere. 6 That brings me to my conclusion : the undergoing xinminyao movement in urban China reminds us to direct our attention not just to the dominant official sphere, but to an array of dominated yet alternative, interstitial, and contingent spheres that have been opened up since the mid-1990s. Hanggai and 3Steps' success both in China and outside provides one example of the significant shift that took place recently in the role that minority people play in the general culture in the PRC, and particularly in the representation of their ethnic identity in this sphere.

We realize that live performance and the new way of dissemination though internet (a typical translocal and transcultural net) have opened up a new sphere of identity and subjectivity for the Chinese independent musicians especially for these who have an regional/minority background, for during these Temporary Autonomous Moments , they are no more a "gazed-up" object but could participate, negotiate, possibly re-ranking the social scale. The newly created, although still marginal and unstable sphere of unofficial musical communities like Hanggai and 3Seps have attracted considerable attention and facilitate the sincere dialogue between different voices from different age groups in different localities on different geographic/subjective/imagined scales. Thus, the term minjian could be considered as a "collective imaginary sphere" constructed both by the musicians and the audience, where they could temporarily escape the aggressive assertion of control by State or Capital. At the same time, some individual subjectivities and cultural diversities could hopefully be forged.

5

To know more about the TAZ theory, see Hakim Bey, T.A.Z.: The Temporary Autonomous Zone: Ontological Anarchy, Poetic Terrorism (Brooklyn, NY : Autonomedia, 1991,p100, quoted by Gregory Lee in Troubadours, Trumpeter, Troubled Makers : Lyricism, Nationalism and Hybridity in China and its Others, Durham, Duke University Press, 1996, p247.

  Headscarf") 45" This extract shows the utilization of Dub music techniques and the digital manipulation of sound effect of 3Steps. The original vocal sample recorded by 3Steps in the Minority village of Yunnan has been subtly treated by the modern electronic techniques and was well integrated in the whole Reggae-based song. Hanggai and 3Steps : negotiating minority identities and the sphere of minjian 民 间 To sum up, both the musical practices of Hanggai and 3Steps have demonstrated some vivid local and Minority culture characteristics, and their music was generally referred to as the music trend "xinminyao" in China by some urban music amateurs or musical critiques. So what is the nature of this so-called xinminyao music in China exactly? As far as I know, half of the musicians of xinminyao started out playing in punk

  life, but also to the cultural invasion of the Han Chinese Majority. Nowadays, less than 20 percent of the population of Inner Mongolia is Mongolian; most are Han Chinese, as the bandleader Ulchi once said in an interview, "Most of our people have moved away from the old way of life, after moving to the cities, many of us have gradually been subjected to a very strong cultural invasion by an oppressive culture. So this traditional music has completely lost its space." That is the same thing for most of the Minority people living in the mountains of Yunnan, or other parts of mainland China. Their own languages, habits and everyday life experiences have been more or less neutralised and centralised by the orthodox representation of the State or the Han major culture. All sort of diversities and autonomies are disappearing quickly with rapid urbanization and the modernization of China.

Jacques Attali, Bruits : Essai sur l'économie politique de la musique (nouvelle édition), Paris, Presses Universitaires de France et Librairie Arthème Fayard, 2001. It has been translated into English and published by University of Minnesota Press in 1985.

Tzvetan Todorov, Nous et les autres. La reflexion française sur la diversité humaine, Paris, seuil, 1989 p 241, quoted in the work of GregoryLee, Troubadours, Trumpeter, Troubled Makers,1996.

See comment on Zebda and the Fabulous Trobadors by GregoryLee, in Troubadours, Trumpeter, Troubled Makers, 1996.p236


Jean-Baptiste Barreau

Yann Bernard

Quentin Petit

Laurent Beuchet

Emilien Petit

Volker Platen

Ronan Gaugne

Julien Le Rumeur

Valérie Gouranton

Combination of 3D Scanning, Modeling and Analyzing Methods around the Castle of Coatfrec Reconstitution

Keywords: Breton castles, virtual archaeology, 3d scanning, 3d modeling, digital preservation, 3d volume comparison

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In April 2013, the association which manages the castle of Coatfrec contacted our team, made up of archaeologists, graphic designers and computer scientists, to consider a 3D scanning and modeling of the castle. Over the progression of this project, an idea emerged to combine the all of the produced digital data from the scans, so to provide new analytic tools for archaeologists. Since the democratization of 3D scanning and modeling technologies, the use of such methods for castles has become common place [START_REF] D'agostino | Lasergrammétrie et photogrammétrie appliquées à l'étude archéologique des châteaux médievaux : le programme franco-italien AVER -des montagnes de châteaux[END_REF] [START_REF] Inman | Tutbury castle: Recovering a period site, Digital Heritage International Congress[END_REF]. Ten years ago, when these technologies were still in their relative infancy, the archeological importance of such monuments, scattered across Europe, inspired their early adoption and utilization [7] [8]. From a general archeological viewpoint, the evolution of these techniques to produce 3D data [START_REF] Böhler | High Quality Scanning and Modeling of Monuments and Artifacts[END_REF], projects [START_REF] Arnold | 3D-COFORM: Tools and Expertise for 3D Collection Formation[END_REF] [START_REF] Havemann | The Presentation of Cultural Heritage Models in Epoch, Open Digital Cultural Heritage Systems[END_REF] and teams [START_REF] Barreau | The West Digital Conservatory of Archaeological Heritage project[END_REF] now allows for the development of more complete analysis and simulation of 3D structures which might better respond to complex archeological query [START_REF] Vergnieux | Virtual Archaeological research and 3D models (Restitution, validation and simulation)/L'usage scientifique des modèles 3D en archéologie, de la validation à la simulation[END_REF]. From this supposition, we'll begin by presenting the archeological context of the site, followed by an overview of the 3D scanning and modeling conducted by two teams at different times. We will then explore how 3D analysis was used to answer specific archeological questions. Finally we'll conclude by discussing this project, and briefly touching on future work.

Archaeological Context

History

The castle of Coatfrec is located in the department Côtes-d'Amor (northwest France) to the east of the town Ploubezre and southeast of Lannion, on the western bank of the small coastal river Léguer. Its name is as obscure as its orgins, as even today it is uncertain whether it is called Coatfrec or Coëtfrec. Originally, it was built as a fortress to overlook the winding Léguer, its hills, and its densely wooded and sparsely populated valley. Its role was to prevent the intrusion of enemy combatants whenever war occurred. The first mentions of the family name Coëtfrec and their lordship appear simultaneously with the foundations of the castle in the 14 th century. It was during this period that the castles surroundings were burdened by the War of Breton Succession, and towards the end of the century, Jeanne de Coëtgourden and her husband Alain de Kerimel strived to restore the castle [START_REF] De | Le Château de Coëtfrec[END_REF] [START_REF] Barbier | Le Trégor historique et monumental. Étude historique et archéologique sur l'ancien Evêché de Tréguier[END_REF]. By the end of the 15 th century, the castle reflected other military architectures of the time. A letter written on the 7 th of August 1462 by François II, the duke of Brittany, stated he feared war with Louis XI and thus sent to the castle two of his officers. Their task, if possible, was to repair the existing fortifications and to raze them if they found them irreparable, but they found them sound enough to allow for the restitution of the castle's walls. In 1589, the French Wars of Religion extended throughout the territory. In Brittany, members of the Catholic League led by the duke of Mercoeur opposed to members loyal to King Henri III. At the same time, the Lord of Kergomar joined the royalist cause and decided to restore the castle of Coatfrec. He began by digging moats, raising the parapets of the entrance, built artillery rooms and stockpiled various weapons and ammunitions. After he demolished farmhouses and leveled the grounds. In 1592 the duke of Mercoeur instructed Guy Eder de la Fontenelle, an infamous brigandeer nicknamed "Ar Bleiz" ("the wolf" in Breton), to capture the castle. He did so, without any bloodshed, then upgraded its fortifications, installed a strong garrison and pillaged the countryside all the way to Lannion. In the end, royalists of Kergomar and Sourdéac besieged the castle of Coatfrec in 1593. La Fontenelle capitulated and the castle was destroyed. Then it was abandoned and served thereafter mainly as quarry for nearby residents [START_REF] Germain | Le Château de Coatfrec à Ploubezre, dans Association bretonne[END_REF].

The Archaeological Site

The ruins of the castle today represent an area of 1700 m² encircled by a 4m deep moat. To the southeast a 30m high tower adjoins the "Grand Logis", a residential wing dating from the 15 th century (fig 1). A structure composed of few rooms with 20m high chimneys, kitchens and the bread oven is located west of the site. This part is connected by the north to the gatehouse, dating from the late 14 th or early 15 th century, by a complex of walls which shows signs of numerous modifications. To the east, a wall dated after 1462 connects to a residential tower with the gatehouse to its north. This wall exhibits three crenellations with loopholes and wooden beams below them assigned to a parapet walk. Each of these elements indicates that aggressors had a relatively limited point of contact.

3D Scanning

Initially, the process of 3D scanning the castle of Coatfrec was motivated by two specific goals: to prohibit further degradation of the monument, as well as to assist the association responsible for the preservation of the site by providing a more complete reconstruction of its parts. Therefore a team constituted of archaeologists, professional climbers and surveyors from German companies ("Laserscan Berlin", "denkmal3D", Vechta, "Moscito Seiltechnik", Heidelberg and "Rope Access Solutions", Bremen) came twice to France. In 2007, a team covered 90% of the site with the scanner in ten days. The last 10% was measured in 2012 and included mural crowns, parts of the tower, the crenellation and the cistern, which is over 12 m deep (fig 2). The laser scanner used in 2012 could measure 500,000 points per second, its range of accuracy was within a few millimeters with a maximum range of around 79m. After scanning, generated pictures were added to the existing point cloud in order to create a photo-realistic 3D model on which each stone and other details might be viewed at close range. This point cloud further assisted in producing a map of the current state of the ruins. The greatest challenges to the process proved to be the weight of the scanner at 15kg, rain, and overgrowth. But thanks to the assistance of the association of the castle of Coatfrec, the project was a success [START_REF] Hummel | Eine Burg in der Bretagne -das Château de Coatfrec[END_REF]. The idea here was to model the castle using a combination of plans, sketches and discussions with archaeologists produced independently of the 3D scanned data from the current ruins. Resulting 3d model rendering is presented in Fig 3.

Northern and Southern Front

The section to the northern front proved rather curious for the team of archaeologists. After modeling was complete and proposals were offered as to potential approximate volumes representing two towers with a linking block, a debate between archaeologists was born. The first hypothesis, formulated by an archaeologist using a 2D plane, suggested the presence of a porch building forming a separate "châtelet", supported by a turret with a spiral staircase, and surrounded by two nearly identical towers. Recent considerations, supplemented by the 3d scanning in 2012 as well as aerial imagery, revealed rather the presence of a large square tower attached to the drawbridge and a smaller tower slightly further behind it. Regarding the north structure, it continues all along the width of the castle and serves as support for the western residential wing. According to the latest suggestions mentioned above, it is unclear that there was ever a homogeneous "châtelet", whereas the entrance seems indeed to have undergone several successive developments. The southern front forms a more coherent structure: the two towers and the central body had certainly a uniform horizontal movement of traffic at floor and wall-walk levels. Despite the lack of remains which had formed the west tower, it was decided to render the towers framing this great residential building symmetrically. Window locations are still subject of discussion, but the modeled proposal seems likely with regard to the existing remains.

Western Front and Eastern Curtain Wall

The rear western buildings are more contemporary in design meaning that their ridgepoles were adjoined to themselves. A hexagonal staircase tower, reminiscent to that of Suscinio castle, also stands behind the large residential building to the southwest. A question regarding its linked wall-walk is ongoing and it would eventually be relevant to render it covered by a furring strip overlapping the building's edge. To the other side, there is also uncertainty about the coronation curtain wall but archaeologists believe that battlements and parapets were of the same type as those of the castle of Combourg. A set of three latrines is hung to the corner of the curtain wall and the large south-east tower.

Related Structures

Two different types of chimneys were scattered over the roofs of the castle. On the northern front, it would seem to be the same model as the la Roche-Jagu castle used.

Other chimneys look more like those of the Hac manor. Their locations were identified by archaeologists. Regarding machicolations on the whole, their appearances correspond most closely to the Breton pyramid-shaped types with their spacing being the same as those of the castle of Fougères.

Digital Elevation Model

In order to produce a mesh of the surrounding castle grounds inclusive in particular of the the moat, two solutions had been considered: to build a mesh from the point cloud resulting from laser scanning or directly use a mesh from a ten years old topographic survey. This last solution was adopted because the mesh is not very dense and untouched by any intrusive vegetation. It was thus easy to handle and it required just a simple vector smoothing to obtain satisfactory results. This topographic survey was conducted in 2005 by civil engineering students and was commissioned by an archaeologist. Two total stations Leica TC1100 and TC705 were used for the survey; isometric curves and a mesh were generated using the Covadis software and were easily imported through 3DSmax with great assistance of the model's .dwg file format.

3D Analysis

A principle advantage of combining scanning and modeling is the ability to compare a site's hypothetical reconstitutions with its existing parts. In order to garner the maximum benefits from these complimentary data, we choose to utilize two methods: the Meshlab Hausdorff distance method as well as a 3d volume calculation. To mix existing and hypothetical data within the same 3D model, so to have a visual comparison, our first approach was to simply superimpose the point cloud over the modeling. The problem of this approach is that the point cloud can cover up modeling in certain areas and vice versa. The Meshlab Hausdorff distance tool [START_REF] Cignoni | Metro: measuring error on simplified surfaces[END_REF] avoids this problem because it allows a representation of the modeling textured with a color gradient defining its differences with the cloud (fig 4). In an attempt to both discover the volume of lost remains of the site as well as to pinpoint areas of particular interest to excavate, we sought to estimate the volume of "hypothetical material quantity"; i.e. the sum of the volumes of the absent walls, roofs and related structures. First our point cloud had to be cleaned and put through a Screen Poisson Reconstruction [START_REF] Kazhdan | Screened poisson surface reconstruction[END_REF] with a depth of 8. We then filled the blanks of the resulting mesh and calculated its volume using MeshLab (Compute Geometric Measures). The result, as they corresponded to the existing remains, was 3561.27m 3 .

To generate a mesh corresponding only to the hypothetical parts, we developed an algorithm that subtracts the point cloud from the mesh by removing mesh points inside the cloud's radius (see below for a simplified presentation of the algorithm). It uses the "radiusSearch" function from Point Cloud Library (PCL) which searches for all the nearest neighbors of the query point in a given radius. To convert the model in a thick and closed mesh, without going through an additional modeling step, we finally applied a solidify modifier on the resulting mesh with Blender software (fig 5). Because we only focused on the volume of the castle, we tried to remove the maximum of polygons corresponding to the ground. We obtained a volume, corresponding to the hypothetical parts, of 6686.23m3. The volume ratio between the existing structures and the hypothetical ones added to them was 34.8% (3561.27/(3561.27+6686.23)).

Discussion

The volume estimations described above provided an interesting metric for on-going discussions and further analysis. Because the thickness of the walls weren't equal for every part, we used an approximate average value indicated by the archaeologists and applied that average over the entire building: 1.50m. Moreover, the solidifying modifier we used was then applied to the roofs, which obviously should be considerably thinner than the walls. Even if the work is quite significant, it would have been appropriate in the first place to divide the model into parts of equal thickness, in correspondence with specialized archaeologists for each structural type (walls, frames, roofs etc.). Then, we could apply the solidifying modifier to each parts corresponding thickness value. The point cloud was cleaned of polygons representing the ground, but not entirely, in part because of the rich complexity of some areas. A low wall was also removed from the cloud because the "Screened Poisson Surface", with low resolution, turned it into a mass of non-exploitable polygons. This addition and subtraction of polygons must certainly have distorted the overall volume comparison. The methods, these initial results and visualizations appeared however to be particularly interesting for the archaeologists studying the site. And we believe that this "wear ratio", if the calculation is improved and achieved within a stricter framework, could eventually be used in the field of heritage conservation. This framework, thanks to its quantitative aspects, would allow for better identification of sites "in danger" as well as to estimate their evolutions and degradation rates. 3D scanning and modeling are today widely exploited, not necessarily by archaeologists themselves, but at least by specialists in these techniques gravitating towards the archeological and research communities. 3D digitization of existing structures allows analytical approaches to increase democratization of projects which entail in particular the restoration of sites. We tried, through the example of the castle of Coatfrec, to combine digitization of existing along with the reconstruction of hypothetical to quantify their differences and commonalities.

Future works shall involve principally a continuation of the castle modeling, in collaboration with the archaeologists. This will entail finishing general volume estimates, texturing the models and beginning to propose suggestions for its interior.

A rethinking of the evaluation of various elements thicknesses will then be done to achieve a more accurate estimate of the missing volumes. Due to the current change of proprietorship of the castle, no new scans are currently scheduled at this time.

Fig. 1 .

 1 Fig. 1. Photos of the ruins: eastern tower, southern wall and the "Grand Logis"

Fig. 2 .

 2 Fig. 2. 3D scanning of the castle

Fig. 3 .

 3 Fig. 3. 3D renderings showing northern and western parts surrounded by ground and moat

Fig. 4 .

 4 Fig. 4. 3D renderings showing cloud and modeling glued together (left) and the modeling textured with a color gradient illustrating its distances with the cloud (right)

  Overview of the subtraction algorithm PC = {x,y,z ∈ ℝ} // Input Points Cloud to remove M = (MP, MF) // Input Mesh MP = {x,y,z ∈ ℝ} // Mesh points of M MF = {a, b, c ∈ MP} // Mesh faces of M Radius ∈ ℝ*+ // Input Radius for search precision var Ptr = {p ∈ MP} // Points to remove for each P in PC //Find points to remove Ptr = Ptr ∪ radiusSearch(kdtree(MP), P, Radius) for each F in MF for each P in F if P ∈ Ptr then MF = MF -F MP = MP -Ptr

Fig. 5 .

 5 Fig. 5. Left to right: Detection of faces to delete during an algorithm test, application of the algorithm on castle model and point cloud without and with solidify modifier


Andrés Romero
email: andres.romero@lri.fr

Lionel Lacassagne
email: lionel.lacassagne@lri.fr

Michèle Gouiffès
email: michele.guiffes@u-psud.fr

Ali Hassan Zahraee

Covariance tracking: architecture optimizations for embedded systems

Keywords: Covariance tracking, SIMD, Multi-core, Embedded systems

Covariance matching techniques have recently grown in interest due to their good performances for object retrieval, detection, and tracking. By mixing color and texture information in a compact representation, it can be applied to various kinds of objects (textured or not, rigid or not). Unfortunately, the original version requires heavy computations and is difficult to execute in real time on embedded systems. This article presents a review on different versions of the algorithm and its various applications; our aim is to describe the most crucial challenges and particularities that appeared when implementing and optimizing the covariance matching algorithm on a variety of desktop processors and on low-power processors suitable for embedded systems. An application of texture classification is used to compare different versions of the region descriptor. Then a comprehensive study is made to reach a higher level of performance on multi-core CPU architectures by comparing different ways to structure the information, using single instruction, multiple data (SIMD) instructions and advanced loop transformations. The execution time is reduced significantly on two dual-core CPU architectures for embedded computing: ARM Cortex-A9 and Cortex-A15 and Intel Penryn-M U9300 and Haswell-M 4650U. According to our experiments on covariance tracking, it is possible to reach a speedup greater than ×2 on both ARM and Intel architectures, when compared to the original algorithm, leading to real-time execution.

Introduction

Tracking consists in estimating the evolution in state (e.g., location, size, orientation) of a moving target over time. This process is often subdivided into two other subproblems: detection and matching. Detection deals with the difficulties of generic object recognition, i.e., finding instances from a particular object class or semantic category (e.g., humans, faces, vehicles) registered in digital images and videos. On the other hand, matching methods provide the location which maximizes the similarity with the objects previously detected in the sequence. Generic object recognition requires models that cope with the diversity of instances' appearances and shapes. This is generally made by learning techniques and classification. Conversely, matching algorithms analyze particular information and construct discriminative models that allow to disambiguate different instances from the same category and avoid confusions.

The main difficulty of tracking is to trace target trajectories and adapt to changes of appearance, pose, orientation, scale, and shape. Since the beginnings of computer vision, a diversity of tracking methods have been proposed, some of them construct path and state evolution estimations using a Bayesian framework (e.g., particle filters, hidden Markov models), others measure the perceived optical flow in order to determine object displacements and scale changes (median flow) [START_REF] Kalal | Tracking-learning-detection[END_REF]. Exhaustive appearancebased methods compare a dense set of overlapping candidate locations to detect the one that fits best with some kind of template or model. When a priori information about the target location and its dynamics (e.g., speed and acceleration) is available, the number of comparisons can be reduced enormously by giving preference to the more likely target regions. Other accelerations can be achieved using local searches that are based on gradient-descent algorithms able to handle small target displacements and geometrical changes. Among these approaches, feature points tracking techniques are very popular [START_REF] Bd Lucas | An iterative image registration technique with an application to stereo vision[END_REF] since points can be extracted in most scenes, contrary to lines or other geometric features. Because they represent very local patterns, their motion models can be assumed as rigid and be estimated in a very efficient way. This method, as well as block matching, are raw-pixel methods, since the target is directly represented by its pixels matrix.

In order to deal with non-rigid motion, kernel-based methods such as mean-shift (MS) [START_REF] Comaniciu | Kernel-based object tracking[END_REF] and [START_REF] Gouiffès | Color connectedness degree for mean-shift tracking[END_REF] use a representation based on color or texture distribution.

Covariance tracking (CT) [START_REF] Porikli | Covariance tracking using model update based on lie algebra[END_REF] is a very interesting and elegant alternative which offers a compact target representation based on the spatial correlation of different features computed at each pixel in the target bounding box. Very satisfying tracking performances have been observed for diverse kinds of objects (e.g., with rigid motion or not, with texture or not). CT has been studied extensively, and many feature configurations and arrays of covariance descriptors have been proposed to improve its discrimination power [START_REF] Li | Local Log-Euclidean Covariance Matrix (L2ECM) for Image Representation and Its Applications[END_REF][START_REF] Zhang | Gabor-LBP based region covariance descriptor for person re-identification[END_REF][START_REF] Guo | Facial expression recognition using local binary covariance matrices[END_REF][START_REF] Pang | Gabor-based region covariance matrices for face recognition[END_REF][START_REF] Bak | Multiple-shot human re-identification by mean Riemannian covariance grid[END_REF][START_REF] Romero | Covariance descriptor multiple object tracking and reidentication with colorspace evaluation[END_REF] and. Smoother trajectories can be obtained by considering target dynamics; therefore, they increase tracking accuracy and reduce the search space [START_REF] Wu | Probabilistic tracking on Riemannian manifolds[END_REF][START_REF] Tyagi | Steepest descent for efficient covariance tracking[END_REF]. Genetic algorithms [START_REF] Zhang | Genetic algorithms. A new optimization and search algorithms[END_REF] can also be used to accelerate the convergence towards the optimal solution of the best candidate position, considering a search in a large image. But, to our knowledge, little work has been done to analyze the computational demands of CT and its portability to embedded systems [START_REF] Romero | Real-time covariance tracking algorithm for embedded systems[END_REF]. The goal of this article is to fill this gap, analyze the algorithm's computational behavior for different implementations, and measure their load on embedded architectures. A study is also made to compare different sizes and configurations of the descriptors in terms of discrimination power through a texture classification application.

The article is structured as follows. The first section introduces some of the basic principles of the CT algorithm and provides a brief description of the different searching and matching methods that can be associated with C. Then various configurations of the covariance matrix are evaluated. Finally, we provide an in-depth description of implementation details and suitable acceleration techniques proposed to achieve a higher level of performance. Experiments and details about the algorithm implementation are presented in the final section that comes followed by our conclusions.

Let I represent a luminance (grayscale) or a color image with three channels and consider a rectangular region of size n = W × H (it can be the bounding box of the target to be tracked for example). Let F be the W × H × n F dimensional feature image extracted from I

F uv = F (p uv ) = φ(I, p uv )with p uv = (x u , y v ) (1)
where φ is any n F -dimensional mapping forming a feature vector for each pixel of the bounding box. The features can be spatial coordinates p uv , intensity, color (in any color space), gradients, filter responses, or any possible set of images obtained from I. Now, let {z k } k=1•••n be a set of n F -dimensional feature vectors inside the rectangular region R ⊂ F of n pixels. Concerning notations, p uv stands for the pixel at uth row and vth column.

The region R is represented with the n F × n F covariance matrix

C R = 1 n -1 n k=1 (z k -µ)(z k -µ) T ( 2
)
where µ is the mean feature vector computed on the n points.

The covariance matrix is a n F × n F matrix which fuses multiple features naturally by measuring their correlations. The diagonal terms represent the variance of each feature, while elements outside this diagonal are the correlations. Thanks to the averaging in the covariance computation, noisy pixels are largely filtered out, which is an interesting advantage when compared to raw-pixel methods. Covariance matrices are more compact than most classical object descriptors. Indeed, due to symmetry, C R has only (n 2 F + n F )/2 different values whatever the size of the target. To some extent, it is robust against scale changes, because all values are normalized by the size of the object, and against rotation when the locations coordinates p uv are replaced by the distance to the center of the bounding box.

The covariance descriptor ceases to be rotationally invariant when orientation information is introduced in the feature vector such as the norm of gradients with respect to x and y directions. The information considered by the covariance descriptor should be adapted to the problem at hand, because they depend on the application, as described in the next paragraph.

Covariance descriptor feature spaces

Covariance descriptors have been used in computer vision for object detection [START_REF] Tuzel | Pedestrian detection via classification on Riemannian manifolds[END_REF], reidentification [START_REF] Bak | Multiple-shot human re-identification by mean Riemannian covariance grid[END_REF][START_REF] Romero | Covariance descriptor multiple object tracking and reidentication with colorspace evaluation[END_REF] and tracking [START_REF] Porikli | Covariance tracking using model update based on lie algebra[END_REF]. The recommended set of features to use depends significantly on the application and the nature of the object: tracking faces is different than tracking pedestrians because faces are somehow more rigid than pedestrians which have more articulations. Color is an important hint for pedestrian or vehicle tracking/reidentification because of their clothes or bodywork color. But color is less significant for reidentification or tracking faces because the set of colors they exhibit is relatively limited. x + I 2 y , and its angle calculated as arctan |Ix| |Iy| . Foreground images G resulting from background subtraction methods and its gradients G x and G y . Features g 00 (x, y) to g 74 (x, y) represent the 2D Gabor kernel as a product of an elliptical Gaussian and a complex plane wave [START_REF] Pang | Gabor-based region covariance matrices for face recognition[END_REF].

Table 1 Features considered by the covariance descriptor depending on the application

Application

Feature set φ(I, p) with p = (x, y)

Face tracking and recognition [START_REF] Pang | Gabor-based region covariance matrices for face recognition[END_REF] x y |Ix| |Iy| |Ixx| |Iyy|

x y I |Ix| |Iy| |Ixx| |Iyy| θ(x, y)

x y I g00(x, y) g01(x, y) • • • g74(x, y)

Pedestrian detection [START_REF] Tuzel | Pedestrian detection via classification on Riemannian manifolds[END_REF][START_REF] Yao | Fast human detection from videos using covariance features[END_REF] x Pedestrian tracking [START_REF] Porikli | Covariance tracking using model update based on lie algebra[END_REF][START_REF] Bak | Multiple-shot human re-identification by mean Riemannian covariance grid[END_REF][START_REF] Romero | Covariance descriptor multiple object tracking and reidentication with colorspace evaluation[END_REF][START_REF] Tuzel | Pedestrian detection via classification on Riemannian manifolds[END_REF]] and [START_REF] Romero | Enhanced local binary covariance matrices ELBCM for texture analysis and object tracking[END_REF] x y R G B |Ix| |Iy|

x y R G B |Ix| |Iy| |Ixx| |Iyy| x y H S V |Ix| |Iy| x y R G B VarLBP x y I sin(LBP θ 0 ) cos(LBP θ 0 ) sin(LBP θ 1 ) cos(LBP θ 1 )
x y R G B sin(LBP θ 0 ) cos(LBP θ 0 ) sin(LBP θ 1 ) cos(LBP θ 1 )

Some texture analysis and tracking methods use local binary patterns (LBP) in the place of Gabor filters and the reason is that LBP operators are much more simple and economical. Values Var LBP , LBP θ 0 , and LBP θ 1 in Table 1 represent local binary pattern variance (which is a classical property of the LBP operator [START_REF] Pietikäinen | Computer Vision Using Local Binary Patterns[END_REF]) and the angles defined by them, as detailed in [START_REF] Romero | Enhanced local binary covariance matrices ELBCM for texture analysis and object tracking[END_REF]. This version of the feature vector has shown very good performances for tracking, both in terms of robustness and computation times, and requires a far shorter vector (n F = 7) when compared to Gabor filters (n F = 43). In the rest of the paper, for the algorithmic optimization, a vector of five to nine features is considered, but note that the proposed optimizations can be applied to any matrix size. Now, let us detail the computation of the covariance descriptor.

Covariance descriptor computation

After some term expansions and rearrangements on Equation 2, the (i, j)-th element of the covariance matrix can be expressed as

C R (i, j) = 1 n -1 n k=1 z k (i)z k (j) - 1 n n k=1 z k (i) n k=1 z k (j) . (3)
Therefore, the covariance in a given region depends on the sum of each feature dimension z(i) i=1•••n , as well as the sum of the multiplications of any pair of features z(i)z(j) i,j=1•••n , requiring in total n F + n 2 F /2 integral images, one for each feature dimension z(i) and one for the multiplication of any pair of feature dimensions z(i)z(j) (the covariance matrix is symmetric).

Let A be a W × H × n F tensor of the integral images of each feature dimension

A uv (i) = p∈R(11,uv) F uv (i)for i = i • • • n F , (4)
where R(11, uv) is the region bounded by the top-left image corner p 11 = (1, 1) and any other point in the image p uv = (x u , y v ). In a general way, let R(uv, u ′ v ′ ) be the rectangular region defined by the topleft point p uv and the right-bottom point p u ′ v ′ . Similarly, the tensor containing the feature product-pair integral images is denoted as

B uv (i, j) = p∈R(11,uv) F uv (i)F uv (j)for i, j = i • • • n F . (5)
Now, for any point p uv , let A uv be a n F -dimensional vector and B a n F × n F dimensional matrix such as

A uv = [A uv (1) • • • A uv (n F )] T and B uv =    B uv (1, 1) • • • B uv (1, n F ) . . . B uv (n F , 1) • • • B uv (n F , n F )    . (6)
The covariance of the region bounded by (1, 1) and p uv is

C R (11, uv) = 1 n -1 B uv - 1 n A uv A T uv , (7)
where n is the number of pixels in the R under investigation. Similarly, and after some algebraic manipulations, the covariance of the region R(uv, u ′ v ′ ) as it was presented in [START_REF] Tuzel | Region covariance: a fast descriptor for detection and classification[END_REF] is

C R(uv,u ′ v ′ ) = 1 n-1 (B u ′ v ′ + B uv -B u ′ v -B uv ′ ) -1 n (A u ′ v ′ + A uv -A uv ′ -A u ′ v ) • (A u ′ v ′ + A uv -A uv ′ -A u ′ v ) T . (8)
Once the integral images have been calculated, the covariance of any rectangular region can be computed in O(n 2 F ) time regardless of the size of the region R(uv, u ′ v ′ ). The complete process is represented graphically in Figure 1, where different image-processing operators are applied to the initial image (top left) to calculate the set of feature images (top right). Each feature component i is used to generate the integral image A uv (i) (bottom left) and the crossed product between features i and j is used to calculate the second order integral images B uv (i, j).

Figure 1 Covariance descriptor computation.

The image is first decomposed into an array of feature images (feature image tensor) applying the feature map F uv = φ(I, p uv ). Then the crossed-products of these features are computed; using these arrays, the tensor integral images A u ′ v ′ (i) and the second order integral images tensor B u ′ v ′ (i, j) are computed.

Next section explains the covariance matching process.

Searching and matching

Covariance models and instances can be compared and matched using a simple nearest neighbor approach, i.e., by finding the covariance descriptors that best resemble a model. The problem is that covariance matrices and symmetric positive definite (SPD) matrices in general is that they do not lie on the Euclidean space and many common and widely known operations in Euclidean spaces are not applicable or require to be adapted (e.g., a SPD matrix multiplied by a negative scalar is no longer a valid SPD matrix). A n F × n F SPD matrix only has n F × (n F + 1)/2 different elements; while it is possible to vectorize them and perform element-by-element subtraction, this approach provides very poor results as it fails to analyze the correlations between variables and the patterns stored in them. A solution to this problem is proposed in [START_REF] Förstner | A metric for covariance matrices[END_REF] where a dissimilarity measure between two covariance matrices is given as

ρ(C 1 , C 2 ) = n F i=1 ln 2 λ i (C 1 , C 2 ) (9)
where

{λ i (C 1 , C 2 )} i=1,••• ,n F are the generalized eigenvalues of C 1 and C 2 computed from λ i C 1 x i -C 2 x i = 0i = 1, • • • , n F . ( 10
)
The tracking starts in the first frame of the sequence, by computing the covariance matrix C 1 in the bounding box of the target under consideration (i.e., the model). The initial detection is not detailed in this paper since it can be made in various ways, by object recognition or background subtraction for example. The tracking procedure consists in determining the new target positions for the successive frames by comparing the covariance matrix C 2 (i.e., the candidate position) and minimizing the Riemannian distance (9).

Figure 2 depicts two possible searching strategies: the exhaustive search approach (left) and a gradientbased local search or steepest descent approach (right). Exhaustive search methods uniformly sample a large number of candidate positions scanning the whole image (or the region surrounding the previous target position). Steepest descent methods look for the position which maximizes the appearance similarity when compared to the target model. Gradient-based methods do not require a large number of matrix comparisons; however, they do require to run iteratively until convergence, causing their computation time to be very unpredictable. Another limitation (and probably the most important one) is that contrary to exhaustive search approaches, local search may fail for targets undergoing brutal motion or target occlusions. The reason behind this problem is that local search methods tend to fall into local minima. Due to these limitations, the exhaustive search method was preferred for the tracking application implemented for this research.

Feature vector evaluation

The objective of this section is to determine the most discriminative vector combination and the ideal number of features (n F ) to use. Multiple feature combinations were tested using a texture classification method. The KTH-Tips dataset [START_REF] Hayman | On the significance of real-world conditions for material classification[END_REF] is composed of ten different texture classes each one represented by 81 different samples of size 200 × 200 taken at different scales, illuminations, and poses.

There are different approaches for texture classification with covariance matrices. Most methods subdivide the image in small overlapping subregions and compute a descriptor associated to each one. The drawback with this approach is that it increases the number of matrix comparisons and the storage required. To avoid this problem, the local log-Euclidean covariance matrix (L2ECM) [START_REF] Li | Local Log-Euclidean Covariance Matrix (L2ECM) for Image Representation and Its Applications[END_REF] computes a single covariance matrix from the log-Euclidean transformations of other (simpler) covariance matrices calculated at every pixel neighborhood (typical sizes are 15 × 15 or 30 × 30). While L2ECM provides high texture reidentification scores, its main drawback is that it considerably increases the number of computations and the memory space that is required during the computation phase. Therefore, L2ECM is clearly not appropriate for embedded platforms; hence, for the sake of simplicity, we were much more inclined to use a very simple approach and compute a single covariance descriptor for every sample and feature combination.

Ten random images were selected for the training of each texture class (from the set of 81 samples that represents each one); the remaining samples were used during the classification evaluation. The descriptor obtained from each test image is compared against all the covariance matrices inside the different training sets (ten samples for each texture class) using the Riemannian metric proposed in [START_REF] Tuzel | Region covariance: a fast descriptor for detection and classification[END_REF].

A label is assigned to each class using the KNN a algorithm counting the number of votes of each texture class for the closest k = 5 samples. The same procedure was repeated ten times to summarize and avoid unstable or misguiding results.

To evaluate the quality of our classification results, we counted the number of true/false positives and negatives and calculated their associated F 1 score (this represents the weighted average of the precision and recall) defined as Three observations can be made from Figure 3: (1) that ELBCM-based combinations tend to have slightly higher scores than gradient-based ones (i.e., their F 1 scores are higher and more concentrated), (2) that color plays a crucial role to improve the discriminative power (purely gradient and ELBCMbased configurations both improve their scores when color information is included), and (3) the relevance of the spatial coordinates (x and y) seems to be small for the texture recognition problem.

F 1 = 2 • precision • recall precision + recall , (11)
According to Figure 3, the ideal number of features (among the set of feature combinations evaluated here) is between n F = 7 and n F = 9 given that most of the smaller configurations produce less accurate results. However, for such as size of covariance matrix, real-time execution (40 ms for 25 frames per second) as required for visual tracking is impossible without optimizations.

Three strategies are studied to optimize the CT on multi-core CPUs. The first one is based on the structure of arrays (SoA) towards array of structures (AoS) transformation: SoA→AoS. The second one consists in architectural optimizations: either multi-threading the SoA version with open multiprocessing (OpenMP) middleware or using single instruction, multiple data (SIMD) instructions (SSE and AVX for Intel, Neon on ARM) for the AoS version. The third and final strategy consists of using loop-fusion transformations. In-depth information about the transformations employed in this article can be found in [START_REF] Lacassagne | High level transforms for SIMD and low-level computer vision algorithms[END_REF].

Let us introduce a set of notations for describing the algorithms and theirs optimizations (Table 2): In the baseline version of the algorithm, the complete set of feature images F is stored separately using a cube data structure (referred to as fmat[k][i][j]) which can be regarded as an instance of a SoA data structure. The index k is used here to select one of the n F feature images while the pair (i,j) is used to select the spatial coordinates. Image cubes are straightforward to implement, the required arithmetic to compute the memory of an address using a table of 3D pointers only demands three integer additions; still, the latency time of a memory access is extremely dependent on the data access pattern.

SoA to AoS transform

The goal of SoA→AoS transform consists of transforming a set of independent arrays into one array, where each cell is a structure combining the elements of each independent array. The contribution of such a transform is to leverage the cache performance by enforcing spatial and temporal cache locality. Table 2 introduces the notations we will use from now on.

The first aspect we want to optimize is the locality of the features for a given point of coordinates (i, j).

In the SoA version, we have two cubes: one that stores all the pixel features F SoA (fmat) which size is n F × h × w and a different cube P SoA (prmat) of size n P × h × w that stores the feature crossedproducts. In the AoS data layout, these cubes are transformed into two 2D arrays F AoS and P AoS of size h × (w • n F ) and h × (w • n P ).

The SoA→AoS transform swaps the loop nests and changes the addressing computations from a 3Dform cube

[k][i][j] into a 2D-form like matrix[i][j ×n+k],
where n is the structure cardinal (here n F or n P ). The lack of spatial locality within the features in the SoA representation is illustrated in Figure 4; here, the SoA layout (on the left) stores pixels features in discontiguous 2D arrays (distant in memory) while for the AoS representation (on the right) features belonging to the same pixel are gathered together in contiguous memory addresses. The covariance tracking algorithm is composed of three stages:

1. point-to-point product computation of all features, 2. the integral image computation of features, 3. the integral image computation of products.

The product of features and its transformation are described in Algorithms 1 and 2. Thanks to commutativity of the multiplication, only half of the products have to be computed (the loop on k 2 starts at k 1 , line 3). As the two last stages are similar, we only present a generic version of integral image computation (Algorithm 3) and its transformation (Algorithm 4).

Algorithm 1: Product of features -SoA version

1 k ← 0 2 foreach k1 ∈ [0..nF -1] do 3 foreach k2 ∈ [k1..nF -1] do 4 foreach i ∈ [0..h -1] do 5 foreach j ∈ [0..w -1] do 6 P [k][i][j] ← F [k1][i][j] × F [k2][i][j] 7 k ← k + 1
Algorithm 2: Product of features -AoS version

1 foreach i ∈ [0..h -1] do 2 foreach j ∈ [0..w -1] do 3 k ← 0 4 foreach k1 ∈ [0..nF -1] do 5 foreach k2 ∈ [k1..nF -1] do 6 P [i][j × nP + k] ← F [i][j × nP + k1] × F [i][j × nP + k2] 7 k ← k + 1
Concerning the index k of Algorithms 1 and 2, the increment k ← k + 1 can be replaced by k = k 1 n F -k 1 (k 1 + 1)/n + k 2 for direct access to the product of feature k 1 by feature k 2 .

Algorithm 3:

Integral image -SoA version, n ∈ {n F , n P } 1 foreach k ∈ [0..n -1] do 2 foreach i ∈ [0..h -1] do 3 foreach j ∈ [0..w -1] do 4 I[k][i][j] ← I[k][i][j] + I[k][i][j -1] + I[k][i -1][j] -I[k][i -1][j -1]
Algorithm 4: Integral image -AoS version, n ∈ {n F , n P }

1 foreach i ∈ [0..h -1] do 2 foreach j ∈ [0..w -1] do 3 foreach k ∈ [0..n -1] do 4 I[i][j × n + k] ← I[i][j × n + k] + I[i][(j -1) × n + k] + I[i -1][j × n + k] -I[k][i -1][(j -1) × n + k]

SIMD or OpenMP parallelization?

Once this transform is done, one can also apply SIMD to the different parts of the algorithm. For the product part, the two internal loops on k 1 and k 2 are fully unrolled in order to show the list of all multiplications and the list of vectors to construct through permutation instructions (e.g., _mm_shuffle_ps in streaming SIMD extensions (SSE)). For example, for a typical value of n F = 7, there are n P = 28 products. The associated vectors are (the numbers are the feature indexes) as follows:

[P 0 , P 1 , P 2 , P 3 ] = [F 0 , F 0 , F 0 , F 0 ] × [F 0 , F 1 , F 2 , F 3 ] [P 4 , P 5 , P 6 , P 7 ] = [F 0 , F 0 , F 0 , F 1 ] × [F 4 , F 5 , F 6 , F 1 ] [P 8 , P 9 , P 10 , P 11 ] = [F 1 , F 1 , F 1 , F 1 ] × [F 2 , F 3 , F 4 , F 5 ] [P 12 , P 13 , P 14 , P 15 ] = [F 1 , F 2 , F 2 , F 2 ] × [F 6 , F 2 , F 3 , F 4 ] [P 16 , P 17 , P 18 , P 19 ] = [F 2 , F 2 , F 3 , F 3 ] × [F 5 , F 6 , F 3 , F 4 ] [P 20 , P 21 , P 22 , P 23 ] = [F 3 , F 3 , F 4 , F 4 ] × [F 5 , F 6 , F 4 , F 5 ] [P 24 , P 25 , P 26 , P 27 ] = [F 4 , F 5 , F 5 , F 6 ] × [F 6 , F 5 , F 6 , F 6 ]
In that case, the 7th vector is 100% filled, but it will become suboptimal if n P is not divisible by the cardinal of the SIMD register (4 with SSE and Neon). In SSE, some permutations can be achieved using only one _mm_shuffle_ps instruction while others need a maximum of two. Because some permutations can be reused to perform other permutations, it is possible to achieve a factorization over all the required permutations. For example with n F = 7, 15 shuffles are required.

In advanced vector extensions (AVX)2, there is a new instruction (compared to AVX) that greatly simplifies permutations : _mm256_permutevar8x32_ps. This instruction implements a full cross-bar, so we need exactly one AVX2 permutation per register that is a total 8 (for n F = 7).

In Neon it is more complex. If some permutations can be done into 128-bits registers -that is with a parallelism of 4 -other permutations require instructions only available with 64-bit registers, like the lookup table instruction named vtbl. So in Neon, 128-bit float registers should be: 1) split into 64-bit registers with vget_low_f32 and vget_high_f32 instructions, 2) type-casted into 64-bit integer registers with vreinterpret_u8_f32 -no latency, just for the compiler -, 3) permuted with vtbl1_u8 and vtbl2_u8 instructions, 4) type-casted into 64-bit float registers with vreinterpret_f32_u8, and 5) combined into 128-bit float registers with vcombine_f32. Finally it requires 31 SIMD Neon instructions to create the seven pairs of products (and 17 extra instructions for the castings). Table 3 gives the values of vn F and vn P depending on n F ∈ {7, 8} and card, the number of block within an SIMD register. For the same values of vn F , Table 4 provides the number of permutations for SSE, AVX and Neon. The first part of Table 5 provides the algorithmic complexity and the amount of memory accesses for scalar version. Just replace n F and n P with vn F and vn P from Table 3 to get the SIMD value. This table also provides the arithmetic intensity (AI) -popularized by Nvidia -that is the ratio between the number of operations and the number of memory accesses. Concerning OpenMP, the point is to evaluate SOA + OpenMP versus AoS + SIMD. Indeed, for a common 4-core General Purpose Processor (GPP), the degree of parallelism with a multi-threaded version and with a SIMDized version is the same, i.e., four. Results are provided in cycles per point (cpp) versus the data amount (image size). The cpp is a normalized metric thats help to detect cache overflow (when data do not fit in the cache): the curve of cpp increases significantly.

= n F (n F + 1)/2 1.5n 2 F + 3.5n F n 2 F + 4n F ∼ 1.5
The three versions (SoA + OpenMP, AoS, AoS + SIMD) have been benchmarked on three generations of Intel processors: Penryn, Nehalem, and SandyBridge for image sizes varying from 128 × 128 up to 1024 × 1024. It appears (Figure 5) that a 4-threaded version is always slower than a 1-threaded SIMD version. Eight threads are required on the Nehalem to be faster. The reason is the low AI inducing a high stress on the architecture's buses and also because manipulating SoA requires n P = 28 active references in the cache; that is more than the usual L2 or L3 associativity (24 on the Intel processor). In the next steps of this article, SIMDization is the only architectural optimization being considered as realistic.

Loop fusion

We have tested three versions with loop-fusion in order to increase the AI ratio by reducing the amount of memory accesses. But for that, we first have to rewrite the integral image computation. As integral image computation is known as being memory bound, but also a very simple algorithm (3 LOADs, 1 STORE, and 3 ADDs), it is quite impossible to reduce its complexity. Nevertheless, one can remove 2 LOADs by using a register that holds the accumulation along a line. Algorithm 5 implements this optimization for basic integral image computation.

Algorithm 5: Integral image -computation in place with an accumulator

1 x ← I[0][0], s ← x 2 foreach j ∈ [1..w -1] do 3 x ← I[0][j], s ← s + x, I[0][j] ← s 4 foreach i ∈ [0..h -1] do 5 x ← I[i][0], s ← x 6 foreach j ∈ [1..w -1] do 7 x ← I[i][0], s ← s + x, I[i][j] ← s + I[i -1][j]
The first one is a scalar parametric version (with n F ) that fuses the external i-loop and keeps the three j-loops unchanged. The second one is a specialized version with n F = 7 where the three internal loops are fused together. The third one is the SIMDized version of the second one. The internal loop fusion allows to save the LOAD/STORE instructions in order to write a product of features into memory and to read it afterwards to compute the integral image of products. The loop-fusion has been done by hand, but some tools like PIPS [START_REF]PIPS[END_REF] can do such a kind of transformation automatically [START_REF] Irigoin | Semantical interprocedural parallelization: an overview of the PIPS project[END_REF]. The complexity of scalar and SIMD versions are provided in Table 5. The numerical value of these expressions is given in Table 6.

To be efficient loop-fusion is combined to full loop-unwinding (on k 1 and k 2 ) and scalarisation (to store temporary results within a register instead of a memory cell of an array). The behavior of the code is the following, for a given pixel (i, j):

• all the features associated to point (i, j) are loaded into n F registers:

f 0 , f 1 , • • • f n F -1 ,
• the integral image computation of features is done on the fly and in place with Algorithm 5 with n F accumulators sf 0 , sf

1 • • • sf n F -1 .
The point fmat(i,j,k) that previously holds n F features is replaced by the sums stored in the n F accumulator,

• the n P products are then calculated in n P registers: p 00 , p 01 , ...

p k 1 k2 , • • • p n F -1nF -1
• the integral image computation of the product of features is done in the same way, with n P accumulators. The point prmat(i,j,k) is filled with the n P accumulators of products.

The code is quite big (as internal loops are unwound) but very efficient (see next section), but it can be easily generated automatically by a C program, as it is very systematic: load features do accumulation of features, store accumulations, and compute products and do accumulation of products and store accumulations. It is relevant for a bigger value of n F to avoid bugs. The complexity of these new versions are given in the second part of Tables 5 and6.

We can observe that without loop-fusion has the lowest AI of 0.5. We can notice that, for a given version, loop-fusion divides the complexity by a factor 1.2 (by rewriting image integral steps) and memory accesses by a factor 2.5 by avoiding LOADs and STOREs of temporary results.

Embedded systems

Let us now focus on more embedded processors like the Intel ULV (ultra low voltage) family and ARM processors. In order to observe the performance evolution for each family, two processors were benchmarked: Penryn-M U9300 ( Firstly, for all processors, the SoA version is very inefficient compared to the best one (AoS+T+SIMD). The SIMDization alone is also inefficient: around ×1.5 instead of ×4 the ideal speedup for 128-bit SIMD and ×2.5 instead of ×8 for 256-bit SIMD. The reason is that SIMD is really efficient only (a speedup close to the SIMD register cardinal) when data fit in the cache [START_REF] Lacassagne | High level transforms for SIMD and low-level computer vision algorithms[END_REF]. Secondly, there is one big difference between them: the cpp values. The Intel cpp's are up to ×4.5 smaller than ARM ones that comes from higher latency instructions.

Cortex-A15 is faster than A9 for two reasons: a faster cache and a faster external memory (same for Haswell-M versus Penryn-M) and because A15 can execute one Neon instruction every cycle instead of every two cycles: the SIMD throughput has been multiplied by two.

Regarding the impact of loop-fusion, Table 7 shows that the speedup with AoS version is from ×1.6 up to ×1.7 for ARM and Intel processor and for scalar and SIMD version, respectively. So the loop-fusion is as efficient as SIMDization. The total speedup is from ×3.8 up to ×4.9 for ARM and Penryn-M processor, respectively, but reaches ×7.9 for Haswell-M (with SSE instructions). Concerning execution time, the Penryn-M and the Haswell-M are, respectively, ×4.3 and ×2.2 faster than the A9 and the A15. If we compare the estimation energy consumption (based on approximative TDP as previously said), the A9 and the A15 are, respectively, ×3.8 and ×2.1 more efficient than the Penryn-M and the Haswell-M. ARM embedded processors are still more efficient than Intel ones.

Impact of other parameters: SIMD width and n F value

The impact of a twice wider SIMD -256 bits for AVX2 instead of 128 for SSE -has been evaluated on a Haswell-M processor. It appears that there is quite no difference in performance between SSE and AVX2. First, AVX (and AVX2) processors can pair two SSE instructions within one AVX instruction, thanks to the out-of-order capabilities of these processors. Once the SIMD are fetched and decoded into the pipeline, they are put in the 'instructions ready' window before being dispatched to an execute unit (named port in Intel vocabulary). If the processor can find two SSE data-independent instructions that are ready to be executed, it pairs them together and sends the new instruction to an execute unit.

The impact of n F has been also evaluated for the four processors. The two specialized scalar and SIMD versions AoS + T and AoS + T + SIMD have been instanced for n F = 8 SSE, AVX, and Neon. It makes sense for AVX architecture as eight features 100% fills one AVX register (see Table 3). The cpp ratio (cpp(n F = 8)/cpp(n F = 7)) varies from 1.11 up to 1.35 for ARM processors and 1.21 up to 1.27 for Intel processors. These values are very close to the theoretical ratios (1.27 and 1.25) of the complexity and memory access amounts of Table 5. It means that the execution time of that part of the global algorithm is predictable until we run out of register and generate spill code.

Two sequences have been used to evaluate the global performance on the four processors. Panda and Pedxing for which the robustness of the algorithm have been evaluated in [START_REF] Romero | Covariance descriptor multiple object tracking and reidentication with colorspace evaluation[END_REF] and [START_REF] Romero | Enhanced local binary covariance matrices ELBCM for texture analysis and object tracking[END_REF]. For both of them, the execution times are given in cpp for each version of the algorithm: SoA is the basic version, and AoS++ stands for AoS transform + SIMDization + loop-fusion transform.

Two counter-intuitive results can be noticed. The first one is the features computation cpp: it is lower for SoA. The reason is obviously the memory layout of SoA (versus AoS) when computing the features and storing them into a cube or a matrix. The second counter-intuitive result is even more interesting: it concerns the tracking part of the algorithm which is based on the computation of a similarity criterion that requires the computation of the generalized eigenvalues, inversions, and matrix logarithms [START_REF] Pang | Gabor-based region covariance matrices for face recognition[END_REF]. In order to have the same behavior, we use GNU Scientific Library to perform these computations on both platforms, but we can also use Intel MKL or Eigen libraries. The future position is chosen by evaluating 40 (in our case, but it is parameterizable) random positions in a research window, so matrix operations represent a high percentage of the tracking part. It appears that the features used for tracking lead to a 'more' ill-conditioned matrix requiring more computations for Panda than for the Pedxing-3 sequence.

Concerning the acceleration, Tables 8 and9 show that the optimization of the kernel provides a speedup of ×2.8 to ×2.9 for Intel processors and ×2.0 to ×2.6 for ARM ones that assets the need of all the optimizations. As both processors have two cores, all the processing parts can be done either on one core (the execution time is the sum of all parts) or on two cores (the biggest part is on one core and the two other parts are on the second core). With such a coarse grain thread distribution, the Penryn-M and the Haswell-M can track targets in real time for 640 × 480 images. The Haswell-M is even real time with only one core. The Cortex-A9 can do it for image sizes up to 320 × 240 and the Cortex-A15 is close to real time for 640 × 480 images. Once the kernel computation has been optimized, the biggest processing part becomes the features computation. With the optimization of this part, the Cortex-A15 should be able to reach real-time execution.

The performance ratio of the whole algorithm is close to the performance ratio of the kernel: the Penryn-M and the Haswell-M are, respectively, ×4.0 and ×3.3 faster than the Cortex-A9 and the Cortex-A15. We can also observe that the image size has quite no impact on the performance ratio. From an energy point of view, the Cortex-A9 and the Cortex-A15 are, respectively, ×2.1 and ×2.7 more energy efficient than the Penryn-M and the Haswell-M.

Conclusions

We have presented the implementation of a robust covariance tracking algorithm, with a parameterizable complexity that can be adapted to trade-off between robustness and execution time. A study has been made to qualitatively compare different covariance matrices in terms of number and nature of visual features. Classical software and hardware optimizations have been applied: SIMDization and loopfusion transform combined with AoS-SoA transform to accelerate the kernel of the algorithm. These optimizations allow a real-time execution (25 fps or about 40 ms per image) for 320 × 240 image size on ARM Cortex-A9 and for 640 × 480 on Intel Penryn-M and Haswell. ARM Cortex-A15 should also reach real-time execution for such image size, once the other parts of the algorithm will be optimized.

Our future work will focus on (1) the optimization of the features computation and (2) the multithreading of the tracking in order to perform multi-target tracking with load balancing on the available core. A more thorough study should also be made concerning the impact of the ill-conditioning of the matrix on the execution time.

To the best of our knowledge, our implementation of the covariance tracking algorithm is the first realtime implementation for embedded systems, while perfectly maintaining the quality of the tracking.

Endnotes

a K-Nearest Neighbours

Figure 2

 2 Figure 2 Illustration of two possible covariance tracking search strategies. The exhaustive search approach (left) where a large number of candidate bounding boxes is uniformly sampled and evaluated, and the steepest descent method (right) where gradient-based local search is launched looking for the position that minimizes the Riemannian distance.

  where precision = #True positives #True positives+#False positives recall = #True positives #True positives+#False negatives .

( 12 )

 12 Multiple feature combinations were evaluated based on the spatial coordinates (x and y), the luminance (I) and color channels (R, G, and B), the first and second order gradient magnitudes (|I x |, |I y |, |I xx |, |I xy | and |I yy |), and the enhanced local binary covariance matrices (ELBCM) features proposed in [18].

Figure 3

 3 Figure 3 depicts the set of feature combinations that were evaluated and their associated F 1 scores. Each combination has a set of points representing the score associated to each one of the different texture classes. Boxplots are used to highlight their concentration and their median (depicted by the horizontal bars in pink inside the boxes). The figure is divided in two rows for grayscale and color-based configurations. Each row is further divided into two parts: firstly, the feature combinations including gradient components only (on the left), and secondly, all feature combinations based on the ELBCM descriptor (on the right). Within each cell, the different feature combinations are sorted by their number of features (n F ) in increasing order and by their F 1 scores median.

Figure 3 F

 3 Figure 3 F 1 -scores measuring the texture classification accuracy for the KTH-TIPS dataset using multiple feature combinations. Boxplots are used to highlight the concentration of F 1 scores and their median.

Figure 4

 4 Figure 4 Layout of SoA cube and the AoS feature matrix.

Figure 5

 5 Figure 5 Performance in cpp of a 1×4-core Penryn (top), 2×4-core Nehalem (middle), 1×4-core SandyBridge (bottom) for image sizes ∈ [128..1024].

Figure 6

 6 Figure 6 Performance of Penryn-M and Haswell-M.

Figure 7

 7 Figure 7 Performance of Cortex-A9 and Cortex-A15.

Figure 2 Figure 3

 23 Figure 2

{

Figure 4 Figure 5

 45 Figure 4

Figure 6

 6 Figure6

Figure 7

 7 Figure7

Table 1

 1 displays a summary of the more common feature combinations used by covariance descriptors in computer vision. The most obvious ones are the components from different color spaces such as RGB and HSV. Pixel brightness in the grayscale image I and its local directional gradients as absolute values |I x | and |I y |, gradient magnitude I 2

Table 2 Covariance descriptor algorithm notations

 2 Number of crossed-products of features n P = n F (n F + 1)/2 F A data structure that contains all the features images P A data structure containing all the feature image products I F and I P The summed area tables (integral images) computed from F or P card the cardinal of SIMD register: 4 for SSE and Neon, 8 for AVX vn

	Notation Meaning
	I	Input image
	h and w	Height and width of I
	n F	Number of features used to build the descriptor
	n P

F

Number SIMD registers to hold n F features: vn F = ⌈n F /card⌉ vn P Number SIMD registers to hold n P products: vn P = ⌈n P /card⌉ (see Table

3

)

Table 3 Parameters values for scalar, 128-bit (SSE and Neon), and 256-bit (AVX) SIMD

 3

	Scalar			128-bit SIMD	256-bit SIMD
	n F	n P	vn F	vn P	vn F	vn P
	7	28	2	7	1	4
	8	36	2	9	1	5

Table 4 Permutation instructions for SSE, AVX, and Neon (permutation + cast) instruction set

 4

	n F	SSE	AVX	Neon
	7	15	8	31
	8	17	10	35

  Table 6 provides numerical results from Table 5 for scalar, SSE, AVX, and Neon version; for 3-loop version; and for the 1-loop version with loop-fusion transform.

Table 5 Complexity, memory accesses, and arithmetic intensity of AoS versions with/without loop- fusion

 5

	Instructions	MUL	ADD	LOAD	STORE	AI
	AoS version with 3 loops
	Product of features	n P	0	2n P	n P	-
	Integral of features	0	3n F	4n F	n F	-
	Integral of products	0	3n P	4n P	n P	-
	Total	n P	3(n P + n F )	6n P + 4n F	2n P + n F	-
	Total with n P = n F (n F + 1)/2	2n 2 F + 5n F	4n 2 F + 9n F	∼ 0.5
	AoS version + loop fusion with 1 loop
	Integral of features	0	2n F	2n F	n F	-
	Integral product of features	n P	2n P	n P	n P	-
	Total	n P	2(n P + n F )	n P + 2n F	n P + n F	-
	Total with n P

Table 6 Complexity, memory accesses, and arithmetic intensity of scalar/SIMD versions with/without loop-fusion: numerical results for n

 6

	Version		Without loop-fusion		With loop-fusion
	SIMD	n F	Arith	Mem	AI	Arith	Mem	AI
	Scalar	7	133	259	0.51	98	105	0.93
	Scalar	8	168	328	0.51	124	132	0.94
	SSE	7	49	66	0.74	40	27	1.48
	SSE	8	59	82	0.72	48	33	1.45
	Neon	7	65	66	0.98	56	27	2.07
	Neon	8	77	82	0.94	66	33	2.00
	AVX	7	27	37	0.73	22	15	1.47
	AVX	8	33	45	0.73	27	18	1.50

F = 7 and n F = 8

For a given version, loop-fusion divides the complexity by 1.2 and memory accesses by 2.5.

  1.2GHz, 10 W, SSSE3), Haswell-M 4650U (1.7 GHz, 15 W, AVX2), ARM Cortex A9 (1.2 GHz, 1.2 W, Neon), and ARM Cortex A15 (1.7 GHz, 1.7 W, Neon). For Penryn-M and Haswell-M, the power consumption is the thermal dissipation power (TDP) provided by Intel; for ARM, these processors are part of SoC (Pandaboard OMAP4 from Texas Instruments and Samsung Chromebook with Exynos5 from Samsung) and it is very difficult to find out any figures from ARM or Samsung. So these figures were collected on the internet and cross-validated on trustable websites.Figures6 and 7provide the cpp of the processor for image size varying from 64 to 1024 for Intel processors and from 64 to 512 for ARM processors.

  Here the cache overflow appears for image size around 150 × 150 for ARM and 200 × 200 for Intel. As a matter of fact, a 512 × 512 image requires a cache of size of 36 MB, while a 640 × 480 needs 43 MB. If the biggest server processors just start to have such large cache (IBM Power7+, Intel Xeon Ivy bridge), such an amount of cache is far from the embedded ARM and Intel laptop processor (from 1 to 4 MB). The important fact, also common to the four processors, is that the cpp of AoS + T version remains constant, unlike SoA and AoS versions. So the execution time can be predicted.

Table 7 Impact of memory layout and loop-fusion transform

 7

		Penryn-M	Haswell-M	Cortex-A9	Cortex-A15
			cpp
	SoA	447	300	830	646
	AoS	207	178	836	520
	AoS + T	126	66	503	238
	AoS + SIMD	165	69	476	325
	AoS + T SIMD	92	38	201	169
			speedups
	SoA/AoS	×2.2	×1.7	×1.0	×1.2
	AoS/AoS + T	×1.6	×2.7	×1.7	×2.2
	SIMD/SIMD + T	×1.8	×1.8	×2.4	×1.9
	SoA/AoS+SIMD + T	×4.9	×7.9	×4.1	×3.8
		Execution time (ms) for 512 × 512 images
	AoS+T SIMD	20.1	6.1	43.9	26.1
		Estimated energy consumption (mJ) for 512 × 512 images
	AoS+T SIMD	201	91.4	52.7	44.3
	cpp and speedups, execution time, and energy consumption for Penryn-M, Haswell-M, Cortex-A9 and Cortex-A15.

Table 8 cpp and execution time for Intel Penryn-M and Haswell-M

 8

	Sequence	Panda		Pedxing
	Size	312 × 233	640 × 480
		Intel Penryn-M
	Algorithm version	SoA	AoS++	SoA	AoS++
	Features computation (cpp)	128	150	128	150
	Kernel computation (cpp)	599	87	618	91
	Tracking (cpp)	23	23	11	11
	Total (cpp)	738	248	769	264
	Kernel/total	81%	35%	80%	34%
	Total speedup	×2.9		×2.8
	1-C execution time (ms)	45	15	197	68
	2-C execution time (ms)	36	9	158	38
		Intel Haswell-M
	Algorithm version	SoA	AoS++	SoA	AoS++
	Features computation (cpp)	78	79	88	72
	Kernel computation (cpp)	190	36	207	40
	Tracking (cpp)	13	23	2	3
	Total (cpp)	281	138	297	115
	Kernel/total	67%	26%	69%	34%
	Total speedup	×2.0		×2.6
	1-C execution time (ms)	12	5	54	21
	2-C execution time (ms)	8	3	37	13

Table 9 cpp and execution time for ARM Cortex-A9 and Cortex-A15

 9

	Sequence	Panda		Pedxing
	Size	312 × 233	640 × 480
		ARM Cortex-A9
	Algorithm version	SoA	AoS++	SoA	AoS++
	Features computation (cpp)	461	461	486	486
	Kernel computation (cpp)	1491	395	1600	415
	Tracking (cpp)	96	96	19	19
	Total (cpp)	2048	952	2106	921
	Kernel/total	73%	42%	73%	45%
	Total speedup	×2.2		×2.3
	1-C execution time (ms)	149	69	647	283
	2-C execution time (ms)	108	36	492	149
		ARM Cortex-A15
	Algorithm version	SoA	AoS++	SoA	AoS++
	Features computation (cpp)	207	207	205	205
	Kernel computation (cpp)	562	170	582	177
	Tracking (cpp)	28	52	4	7
	Total (cpp)	797	429	791	389
	Kernel/total	70%	39%	73%	45%
	Total speedup	×1.9		×2.0
	1-C execution time (ms)	38	20	161	79
	2-C execution time (ms)	27	10	119	42

Competing interests

The authors declare that they have no competing interests.