pragma hmpp motion_estimation codelet, target=CUDA; 2 Definition of function motion_estimation()

Keywords:

3 ...

First, i would like to thank my advisors Prof. Jean-François Nezan and Associate Prof. Jean-Gabriel Cousin for their help, suggestion and encouragement, for the time they spent to correct my papers and this PHD thesis. I don't forget that Jean-François revise my first conference paper again and again although he is very busy. I also remember that Jean-Gabriel teaches me to make some slides and to present my work. In particular, i thanks Matthieu Wipliez and Mickaël Raulet who helped me to debug the code when i was falling down with programming. I thanks Jean-François give me such a opportunity to study and make research here. I also thank China Scholarship Council to support my scholarship of 48 months living in Rennes, France.

Three year almost thousand days in our laboratory is quite a long time. I thank all the colleague Matthieu Wipliez, Nicloas Siret, Maxime Pelcat, Jérôme Gorin, Mickaël Raulet, Karol Desnos, Hervé Yviquel, Antoine Lorence, Khaled Jerbi, Julien Heulot, Erwan Raffin, who help me in the research and daily life. I enjoyed the laboratory life and its friendly environment, although i didn't communicate too much with you owing to my poor french speaking. Thanks you Hervé, have helped me making a phone call for house-hunting and something else. Maxime Pelcat, thank you being a listener and advisor in my presentations, also helping me to present the slides in the Dasip13 conference. Thanks Alexandre MERCAT's work on stereo matching on MPPA platform. Thanks to Aurore Gouin and Jocelyne Trenmier for managing administrative works.

I am grateful to all my friends, my Chinese colleagues. Yi Liu, Wenjing Shuai thank you for being my models in my experiment tests. Cong Bai, Ming Liu thank you for giving me the suggestions to revise papers and the templet of Ph.D thesis.

Fu Hua thank you for helping me to write the abstract of French. Thank you all the guys who invited me and prepared the meals almost every weekend when i was alone without my families.

Thank you, my wife Huiwen Tan, for taking care of our son Yixi. I apologize that i cannot live with you and take care of you in the more than three years. Although you always quarrel with me, i thank a lot because of your effort for our family, i am not a good husband and father until now. For my parents, father Dazeng Zhang, mother Xiuling Wang, thank you raising me up and teaching me when i was young. I can only to say i love you.

Introduction

Context

Inspired and motivated by the conclusion made by Gordon Moore in 1965, the density of transistors in a chip was doubled every 18 months. More transistors allow more complex chip-designs, and smaller transistor allows a higher frequency per watt consumed. But there is no more increasing about clock rates because of power consumption. In order to keep the performance increment, modern processors apply a many-cores strategy instead of frequency increment.

In the meantime, image and video applications such as video coding and ultraresolution display with novel features whose aim is to recover a real world for users from the digital world are becoming more and more complex. Thereby, the need for computational power is rapidly increasing. The accuracy and the time-efficiency are two key criterions in the image and video processing applications. Better quality can be achieved by using more sophisticated algorithms, which also means the more computational power.

All these changes make electronic manufactures developing parallel embedded heterogeneous systems which combine with different subsystems optimized to execute different workload. The tradeoff between accuracy and time-efficiency will benefit from technology revolutions of the embedded heterogeneous system and parallel computing. Some heterogeneous systems consist of Central Processing Unit (CPU), Graphics Processing Unit (GPU), and Field-programmable gate array (FPGA). GPU with herds of Processing Element (PE) is the typical case which Chapter 1. Introduction benefits form many core revolutions that considered as special-purpose hardware for graphical computations until the turn of the century. In fact, GPU could employ general-purpose computation in many arithmetic computation domains. There are some successful attempts for general-purpose computing in heterogeneous systems.

Even if they are so less mature and much more difficult to use for terminal users and to develop for researchers. With their immense processing power, GPU can be orders of magnitude faster than CPUs for numerically intensive algorithms that are designed to fully exploit the parallelism available. Lately, the interest in parallel programming has grown even more in popularity because of the availability of many core devices. The General-Purpose Graphics Processing Unit (GPGPU) research field has extended to the fields as diverse as artificial intelligence, medical image processing, physical simulation and financial modeling.

When the heterogeneous computing system became the trend of the hardware design and development in the domain of image and video processing, some parallel embedded System on Chips (SoC) like NVIDIA's Tegra, MediaTex's MT and Qualcomm's Snapdragon series comes up with a high speed development of personal portable devices like smartphone, TabletPC (Tablet Personal Computer) and so on. For these terminal users, parallel embedded heterogeneous systems bring better performance of applications and better user experience; For these researchers and programmers, most of the heterogeneous systems allow to select the best architecture for different demands of task or the best performance for fixed tasks.

However developing software for heterogeneous parallel system is considered to be a non-straightforward task.

With so much heterogeneities, developing efficient solutions and applications for such a wide range of architectures faces a great challenge. In such heterogeneous systems, there are a huge diversity in hardware architectures and configurations.

Meanwhile, these electronic manufacturers provide their standard and development environment for their heterogeneous systems like AMD's Streaming Programming Language: Brook, NVIDIA's Compute Unified Device Architecture (CUDA) and IBM's Unified Parallel C (UPC) and so on. But these tools and corresponding programming languages only support on their specified devices, are not compatible there are parallel computing programming language: CUDA and OpenCL, desinging the kernel code of CUDA and OpenCL is still a complex and troublesome procedure.

Implementing complex applications on such the same complex platforms have already been proven to be a daunting task. Under this context, there is a growing interest in adaptive/reconfigurable platforms that can dynamically adapt themselves to support or provide more flexible configuration and better performance for the application. A possible answer is to follow a model based approach, where both the hardware platform and the application are abstracted through models. These models are used to capture a given domain-specific knowledge into a formal abstract representation. Models of Computations (Kahn Process Network (KPN), Synchronous Dataflow (SDF), etc.) specify the behavior of a system and are a perfect example of such an abstraction. Similarly, platform models which abstract the hardware components of a system (processing resources, communication, etc.) are also a common abstraction for embedded platform designers. However, in spite of some early work done in this direction, there is currently still no modeling approach taking run-time adaptation into consideration (from both a hardware and software point of view).

Chapter 1. Introduction

A prototyping methodology is a software development process which allows developers to create portions of the solution to demonstrate functionality and make needed refinements before developing the final solution. The goal of rapid prototyping framework is to propose generic models for adaptive multi-processors embedded systems. Figure 1.1 describes a global view of rapid prototyping framework, there are lots of attempts and research works around this goal. Basically, our rapid prototyping framework contains:

1. Dataflow Models.

2. Model to Models transformations. -It proposes to rely on a target independent description of the application, particularly focusing on dataflow Model of Computations (MoC) and especially the CAL language [1], developed in the Ptolemy project (Berkeley).

Friendly Graphical User Interface (GUI)

The COMPA project will extend it with constructs for efficient modeling of multi-dimensional dataflow networks.

-To offer additional opportunities for optimizing the application implementation, it proposes to develop a static analysis toolbox for detecting underlying MoCs used in a given CAL description. This analysis will be coupled to optimizing transformations on CAL models.

-It specifies and develops a "Runtime Execution Engine" which will be in charge of the execution of the CAL network on the platform. Providing runtime execution and reconfiguration services imply solving many problems including 1.2. Contributions task-mapping, scheduling, etc. These problems themselves will not only take advantage of knowledge of the target architecture but also from meta data embedded in the CAL network description.

In the COMPA, three tools are proposed: the Open RVC-CAL Compiler (Orcc) [2], the Parallel and Real-time Embedded Executives Scheduling Method (Preesm) [3], and Hybrid Multicore Parallel Programming (HMPP) [4]. Orcc includes an RVC-CAL textual editor, a compilation infrastructure, a simulator and a debugger.

Lots of works have been done with the Orcc and many backends are supported in the Orcc like C, C++, VHDL, HMPP and so on [5] [6] [7]. PREESM tool offers a fast prototyping tool for parallel implementations used in many applications like LTE RACH-PD algorithm and so on [8] [9] [START_REF] Piat | Multi-core code generation from interface based hierarchy[END_REF]. HMPP is a directive-based compiler to build parallel hardware accelerated applications. Previous research works with Orcc and Preesm was to evaluate the full prototyping framework developed in COMPA with video decoders. But video decoders are usually based on the same dataflow, the same structure with a lot of data dependencies which are very hard to map with parallelism and to implement on many core heterogeneous systems. Recently investigated motion estimation and stereo matching algorithm have the high nature of parallelism which can fully make use of the parallelism of target architectures.

They are much more suitable to evaluate the efficiency of the rapid prototyping framework developed in COMPA.

Contributions

The goal of my Ph.D thesis was to evaluate and to improve the prototyping methodology for embedded systems, especially based on the dataflow modeling approach (high level modeling of algorithm) and OpenCL approach (intermediate level of algorithm). The first contribution of this thesis is to participate to the development of the rapid prototyping framework of COMPA project, as shown in Figure 1.2. I described the proposed motion estimation and stereo matching methods with RVC-CAL language. This rapid prototyping framework mainly contains three levels from up to down view: high level programming model, intermediate level The second contribution of this thesis contains three parts of improvement about 1.3. Road Map image and video processing algorithms:

-The proposed parallelized motion estimation (chapter 3) aims at heterogeneous computing system which contains one CPU and one GPU. I also developed one method to balance the workload distribution on such heterogeneous parallel computing system with OpenCL.

-The proposed real-time stereo matching method (chapter 4) adopts combined costs and costs aggregation with square size step to implement on an entrylevel laptop's GPU platform. Experimental results show that the proposed method outperforms other state-of-the-art methods about tradeoff between matching accuracy and time-efficiency.

-The proposed joint motion-based video stereo matching method (chapter 5) makes use of the motion vectors calculated from our parallelized motion estimation method to build the support region for video stereo matching. Then it employs the proposed real-time stereo matching method to process these frames of stereo video as static paired images. Experimental results show that this method outperforms these state-of-the-art stereo video matching methods in the test sequences with abundant movement even in large amounts of noise.

Road Map

The content of this thesis are structured as follows: the fundamental concept of rapid prototyping framework and the images processing algorithms concerned in our approaches are introduced in chapter 2. Approach of parallelized motion estimation based on heterogeneous computing system is presented in chapter 3 while one new accurate method to distribute the workload in video applications based on heterogeneous computing system is proposed. Approach of real time local stereo matching is elaborated in chapter 4. Approach of joint motion-based video stereo matching is detailed in chapter 5 where one new method with joint motion vector to build the support region for stereo video matching is proposed. A conclusion will be given at chapter 6.

Background

This chapter gives an overview of our rapid prototyping methodology from down to up view. It describes the parallel embedded systems, parallel programming models, and the rapid prototyping methodology. The difference of embedded systems is discussed in the section of target architectures. OpenCL is presented as the intermediate level programming model in our rapid prototyping methodology. Dataflow approach is presented as the high level programming model in this methodology.

Some tools used in this methodology are also introduced.

This chapter naturally begins by a presentation of target architectures in section 2.1; Section 2.2 introduces the intermediate level programming model -OpenCL;

Section 2.3 presents the Dataflow approach in our rapid prototyping framework; section 2.4 presents some tools of rapid prototyping methodology. Section 2.5 introduces the concept of Motion Estimation and Stereo Matching algorithms; A brief conclusion is presented in section 2.6.

Target Architectures

Many core architectures like CPU, GPU, FPGA and DSP raised problems in terms of application distribution, data transferring and task synchronization. These problems become more and more complex and result in the loss of development time.

Flynn's taxonomy [START_REF] Flynn | Very high-speed computing systems[END_REF] is the most popular classification of computer architecture which defines four categories of computer architecture according to the concurrency of instruction and data streams as shown in Classical single-processor systems belong to the category of SISD. A system of SIMD treats multiple data streams by using a single instruction stream, and it usually describes a processor array. In a system of MISD, multiple instructions operate on a single data stream. Modern parallel computing systems are mainly divided into two categories of SIMD (GPU, FPGA) and MIMD (Heterogeneous SoC System). MIMD is also divided into two groups: shared memory architecture and distributed memory architecture. These classifications are based on how MIMD processors access memory. Shared memory may be the bus-based, extended, or hierarchical type. Distributed memory may have hypercube or mesh interconnection schemes. We will introduce our shared memory MIMD architecture of heterogeneous system with GPU and CPU in chapter 3 of parallelized motion estimation.

Target Architectures

CPU and GPU

The section begins by one most commonly comparing difference between CPU and GPU as shown in Figure 2.2. A CPU commonly has 4 to 8 fast, flexible cores clocked at 2-3 Ghz which favor threads of heavy workload with its instructions set like AMD's 3DNOW and Intel's Streaming SIMD Extensions (SSE), whereas a GPU has hundreds of relatively simple cores clocked at about 1Ghz that favor threads of light workload. Tasks that can be efficiently divided across many threads will see enormous benefits when running on a GPU. This highly parallel architecture is the reason why a GPU can process such large batches of copy number data so quickly.

OpenCL: An Intermediate Level Programming

Model

In fact we need to manage many core devices like CPU, GPU, SoC (System on Chip), to generate multiple target codes and to distribute suitable workload for different devices. CUDA is a parallel computing platform and programming model created by NVIDIA and implemented by the GPU that they produce. CUDA makes developers access to the virtual instruction set and memory of the parallel computational elements in CUDA GPUs. Different with CUDA, Open Computing Language (OpenCL) is appearing as a standard for parallel programming of diverse heterogeneous hardware accelerators. For existing CUDA projects or implementations of application, there are some useful tool like Swan [START_REF]Cuda2opencl[END_REF] which could translate the kernel code from CUDA to OpenCL. It does several useful things:

-Translates CUDA kernel source-code to OpenCL.

-Provides a common API that abstracts both CUDA and OpenCL runtimes. It can also be usefully used for compiling and managing kernels written directly for OpenCL.

OpenCL is such a programming language which expresses the application by encapsulating its computation into kernels. In our rapid prototyping framework, OpenCL is treated as an intermediate level programming model. The OpenCL compiler aims to parallelize the execution of kernel instances at all the levels of parallelism. Comparing with the traditional C programming language that is sequential, OpenCL enables higher utilization of parallelism available of hardware while still keeping familiar grammar with the C language. Whereas, OpenCL enables application portability but does not guarantee performance portability, eventually requiring additional tuning of the implementation to a specific platform or to unpredictable dynamic workloads. In OpenCL programming model, thread and thread group are Recently, there are so many programming tools and integrated development environment to use and evaluate OpenCL as illustrated in [START_REF] Du | From cuda to opencl: Towards a performance-portable solution for multi-platform gpu programming[END_REF], [START_REF] Paone | An exploration methodology for a customizable opencl stereo-matching application targeted to an industrial multi-cluster architecture[END_REF], [START_REF] Jinen | Opencl-based design methodology for application-specific processors[END_REF]. Du et al. [START_REF] Du | From cuda to opencl: Towards a performance-portable solution for multi-platform gpu programming[END_REF] evaluated OpenCL as a programming tool for developing performance-portable applications for GPGPU They chose triangular solver (TRSM) and matrix multiplication (GEMM) as representative level 3 Basic Linear Algebra Subprograms (BLAS) routines to implement with OpenCL, profiled TRSM to get the time distribution 2.2. OpenCL: An Intermediate Level Programming Model of the OpenCL runtime system, and provided tuned GEMM kernels for both the NVIDIA Tesla C2050 and ATI Radeon 5870. Experimental results described that nearly 50% of peak performance can be obtained in GEMM on both GPUs with OpenCL. Paone et al. [START_REF] Paone | An exploration methodology for a customizable opencl stereo-matching application targeted to an industrial multi-cluster architecture[END_REF] presented a methodology to analyze the customization space of an OpenCL application in order to improve performance portability and to support dynamic adaptation. They formulated their case study by implementing an OpenCL image stereo-matching application customized to the STMicroelectronics Platform 2012 [START_REF]Stmicroelectronics[END_REF]. They used design space exploration techniques to generate a set of operating points that represent specific configurations of the parameters allowing different trade-offs between performance and accuracy of the algorithm itself. Jinen et al. [START_REF] Jinen | Opencl-based design methodology for application-specific processors[END_REF] described one methodology involved in applying OpenCL as an input language for a design flow of application-specific processors. The key of the methodology is a whole program optimizing compiler that links together the host and kernel codes of the input OpenCL program and parallelizes the result on a customized statically scheduled processor.

; i++) { c[i] = a[i] * b[i]; } a[
Since the programmable GPU make its way to mobile devices, it is interesting to study the new use-cases here. To this end, Leskela et al. [START_REF] Leskela | Opencl embedded profile prototype in mobile device[END_REF] of Nokia Corporation created a programming environment based on the embedded profile of the OpenCL standard and verify it against an image processing workload in a mobile device with CPU and GPU back-ends. The early results on performance with CPU + GPU configuration suggested that there is enough room for optimization. Our experimental results based on heterogeneous systems also illustrate the performance enhancement based on the CPU + GPU combination in chapter 3. In the meantime, more and more portable device start to support OpenCL standard. The Mali OpenCL SDK [START_REF]Mail opencl sdk[END_REF] provides developers a framework and series of samples for developing OpenCL 1.1 application on ARM Mali based platforms such as the Mali-T600 family of GPUs. The samples cover a wide range of use cases that use the Mali GPU to achieve a significant improvement in performance when compared to running on the embedded CPU alone. QUALCOMM also release the Adreno SDK [START_REF]snapdragon[END_REF] for developing and optimizing OpenCL applications for Snapdragon 400, 600 and 800-based mobile platforms that include the Adreno 300 series GPU and Krait CPUs both. For example, in the Snapdragon 600 there is a Quad-Core Krait CPU and Adreno 320 GPU. Both the CPU and GPU access to system (host) memory where the input and output data for computations can be stored as shown in Figure 2.5. All calls to OpenCL API functions on the Snapdragon processor are performed on the CPU.

The data parallel workloads are written in OpenCL C kernels. The kernels can be built (compiled) to run on either one or both of the Krait CPU and Adreno GPU. In the case of Snapdragon, the application can choose to create command queue(s) for either one or both devices (CPU or GPU). It is up to the application to decide how to partition work so that it can maximally make use of the compute resources of the CPU and GPU devices. Similarly we will discuss about the workload partition and propose our method about workload distribution in the chapter 3.

2.3. The Dataflow Approach: An High Level Programming Model

29

As above description, heterogeneous systems provide new opportunities to increase the performance of parallel applications on clusters with CPU and GPU architectures like [START_REF] Barak | A package for opencl based heterogeneous computing on clusters with many gpu devices[END_REF], [START_REF] Herlihy | A methodology for implementing highly concurrent data objects[END_REF], [START_REF] Aoki | Hybrid opencl: Connecting different opencl implementations over network[END_REF]. Barak et al. [20] presented a package for running OpenMP, C++ and unmodified OpenCL applications on clusters with many GPU devices. Many GPUs Package (MGP) includes an implementation of the OpenCL specifications that allow applications on one hosting-node to transparently utilize cluster-wide devices (CPUs and/or GPUs). MGP provides means for reducing the complexity of programming and running parallel applications on clusters. Herlihy et al. [START_REF] Herlihy | A methodology for implementing highly concurrent data objects[END_REF] proposed a new methodology for constructing non-blocking and wait free implementations of concurrent objects whose representation and operations are written as stylized sequential programs with no explicit synchronization. Aoki et al. [START_REF] Aoki | Hybrid opencl: Connecting different opencl implementations over network[END_REF] proposed Hybrid OpenCL, which enables the connection between different OpenCL implementations over the network. Hybrid OpenCL consists of a runtime system that provides the abstraction of different OpenCL implementations and a bridge program that connects multiple OpenCL runtime systems over the network. Hybrid OpenCL enables the construction of the scalable OpenCL environments which enables applications written in OpenCL to be easily ported to high performance cluster computers; thus, Hybrid OpenCL can provide more various parallel computing platforms and the progress of utility value of OpenCL applications.

Different with the above OpenCL-based methodologies, our work in this thesis is to generate, to evaluate and to improve OpenCL applications with rapid prototyping methodology. The upper level of this methodology will be detailed in the next section.

The Dataflow Approach: An High Level Programming Model

The complexity introduced by the wide range of hardware architectures makes the optimal implementation of applications difficult to obtain. Moreover the stability of the application has to be early proved in the development stage to ensure the Chapter 2. Background reliability of the final product. Some tools such as PeaCE [START_REF] Sung | Demonstration of codesign workflow in peace[END_REF], SynDEx [START_REF] Grandpierre | From algorithm and architecture specifications to automatic generation of distributed real-time executives: a seamless flow of graphs transformations[END_REF] aim at providing solutions to these problems by automatic steps leading to a reliable prototype in a short time. The aim of rapid prototyping methodologies is from a high-level description of these applications to its real-time implementations on target architecture as automatically as possible.

Definition of reconfigurable video coding

The Reconfigurable Video Coding (RVC) [START_REF] Mattavelli | The reconfigurable video coding standard [standards in a nutshell[END_REF] defines a set of standard coding techniques called Functional Units (FUs). FUs form the basis of existing and future video standards, and are standardized as the Video Tool Library (VTL). A FU is described with a portable, platform-independent language called RVC-CAL. Video decoding process is described as a block diagram in RVC, also known as network or configuration, where blocks are the aforementioned FUs. To this end, RVC defines a XML-based format called FU Network Language (FNL) that is used for the description of networks. FNL is another name for the XML Dataflow Format (XDF).

A FNL network may declare parameters and variables, has interfaces called ports, where a port is either an input port or an output port, and contains a directed graph whose vertices may be instances of FUs from the VTL or ports. Additionally, this allows applications to be reconfigured at runtime by changing the structure of the network that defines the decoding process. This is especially interesting for hardware and memory-constrained devices. Finally, this makes RVC more hardware-friendly because dataflow is a natural way of describing hardware architectures.

Dataflow models of computation

A dataflow Model of Computation (MoC) defines the behavior of a program described as a dataflow graph. A dataflow graph is a directed graph whose vertices are actors and edges are unidirectional First-In-First-Out (FIFO) channels with unbounded capacity, connected between ports of actors. The networks of FUs described by the RVC standard are dataflow graphs. Dataflow graphs respect the semantics of Dataflow Process Networks (DPNs) [START_REF] Lee | Dataflow process networks[END_REF], which are related to Kahn Process Networks (KPNs) [START_REF] Kahn | The semantics of simple language for parallel programming[END_REF] in the following ways:

1. Those models contain blocks (processes in a KPN, actors in a DPN) that communicate with each other through unidirectional, unlimited FIFO channels.

2. Writing to a FIFO is non-blocking, i.e. a write returns immediately.

3. Programs that respect one model or the other must be scheduled dynamically in the general case [START_REF] Haid | Efficient execution of kahn process networks on multi-processor systems using protothreads and windowed fifos[END_REF].

The main difference between the two models is that DPNs adds non-determinism to the KPN model, without requiring the actor to be non-determinate, by allowing actors to test an input port for the absence or presence of data [START_REF] Lee | Dataflow process networks[END_REF]. Indeed, in a KPN

❋✐❣✉r❡ ✻✳✸✿ ❉❛t❛✲✢♦✇ ▼♦❞❡•s ♦❢ ❝♦♠♣✉t❛t✐♦♥ t❛①♦♥♦♠②✳ ■♥ t❤❡ ❢♦••♦✇✐♥❣ ✇❡ ✇✐•• ❣✐✈❡ ❛♥ ✐♥tr♦❞✉❝t✐♦♥ t♦ t❤❡ ❞❛t❛✲✢♦✇ ♣❛r❛❞✐❣♠ st❛rt✐♥❣ ❜② t❤❡ ♠♦t❤❡r ♦❢ ❛••✱ t❤❡ ❑❛❤♥ Pr♦❝❡ss ◆❡t✇♦r❦ ❢♦••♦✇❡❞ ❜② t❤❡ ❉❛t❛ ❋•♦✇ Pr♦❝❡ss ◆❡t✇♦r❦ ❛♥❞ ♣r♦✈✐❞❡ ❛♥ ✐♥✲❞❡♣t❤ ❡①♣•♦r❛t✐♦♥ ♦❢ t❤❡ ♣r❡✈✐♦✉s•② ❝✐t❡❞ ♠♦❞❡•s✳ ✻✳✸✳✷ ❉❛t❛ ❋•♦✇ ♣❛r❛❞✐❣♠ ✐♥tr♦❞✉❝t✐♦♥ ❑❛❤♥ Pr♦❝❡ss ◆❡t✇♦r❦ ✭❑P◆✮ ❆ ♣r♦❝❡ss ♥❡t✇♦r❦ ✐s ❛ s❡t ♦❢ ❝♦♥❝✉rr❡♥t ♣r♦❝❡ss❡s t❤❛t ❛r❡ ❝♦♥♥❡❝t❡❞ t❤r♦✉❣❤ ♦♥❡✲✇❛② ✉♥❜♦✉♥❞❡❞ ❋■❋❖ ❝❤❛♥♥❡•s✳ ❊❛❝❤ ❝❤❛♥♥❡• ❝❛rr✐❡s ❛ ♣♦ss✐❜•② ✜♥✐t❡ s❡q✉❡♥❝❡ ✭❛ str❡❛♠✮ t❤❛t ✇❡ ❞❡♥♦t❡ ✳ ❊❛❝❤ ✐s ❛♥ ❛t♦♠✐❝ ❞❛t❛ ♦❜•❡❝t ❝❛••❡❞ t♦❦❡♥ ❜❡•♦♥❣✐♥❣ t♦ ❛ s❡t✳ ❚♦❦❡♥ ❝❛♥♥♦t ❜❡ s❤❛r❡❞✱ t❤✉s t♦❦❡♥s ❛r❡ ✇r✐tt❡♥ ✭♣r♦✲ ❞✉❝❡❞✮ ❡①❛❝t•② ♦♥❝❡ ❛♥❞ r❡❛❞ ✭❝♦♥s✉♠❡❞✮ ❡①❛❝t•② ♦♥❝❡✳ ❆s ❋■❋❖s ❛r❡ ❝♦♥s✐❞❡r❡❞

Dataflow process network model

Each FIFO channel is a DPN carries a sequence of tokens X = [x 1 , x 2 ...], where each x i is called a token. The sequence of available tokens on the P th input port is The set of all possible sequences is defined as S, and S p is the set of p-tuples of sequence. In other words [X 1 , X 2 , ..., X P ] ∈ S p .

An actor executes or fires when at least one of its firing rules is satisfied. Each firing consumes and produces tokens. An actor has N firing rules:

R = [R 1 , R 2 , ..., R N ] (2.1)
A firing rule R i is a finite sequence of patterns, one for each of the p input ports of the actor:

R i = [P i,1 , P i,2 , ..., P i,p ] ∈ S p (2.2)
A pattern rule P i,j defines an acceptable sequence of tokens: if P i,j ⊑ X j , the pattern is satisfied for the sequence of unconsumed (or available) tokens on the p th input port; if P i,j =⊥, the pattern is satisfied for any sequence, which is different from P i,j = [ * ] that defines a pattern satisfied for any sequence containing at least one token.

Synchronous dataflow model

The Synchronous Dataflow (SDF) [START_REF] Lee | Synchronous data flow[END_REF]

Dataflow sigmaC

To exploit the parallelism available in the platform MPPA, Kalray has developed its own dataflow model: SigmaC. According to this model, the block in dataflow graph is called agent. Each agent is appointed and includes: the C code of the function executed, the number of incoming and outgoing data through the interface together with the set of production/consumption. All these information are assigned through a special syntax, specific SigmaC that illustrated as Figure 2.8.

Every agent define that it remains only to create the graph by interacting. To do this, a new syntax is created in order to create graph and sub-graph and thus to organize the work as cleanly as possible. Figure 2.9 illustrates the example of sub-graph syntax connecting two agents.

RVC-CAL language

This part presents the RVC-CAL language and covers the syntax, semantics with this kind of language. RVC-CAL is a Domain-Specific Language (DSL) that has been standardized by RVC as a restricted version of CAL. CAL was invented by Eker and Janneck and is described in their technical report [1]. 1. the actor may consume tokens from its input ports, 2. it may modify its internal state, 3. it may produce tokens at its output ports.

Consequently, describing an actor involves describing its interface to the outside, the ports, the structure of its internal state, as well as the steps it can perform, what these steps do (in terms of token production and consumption, and the update of the actor state), and how to pick the step that the actor will perform next.

State variables

State variables can be used to define constants and to store the state of the actor. Figure 2

Actions

So far, the only firing condition for actions was that there be sufficiently many tokens for them to consume, as specified in their input patterns. However, in many cases we want to specify additional criteria that need to be satisfied for an action to fire conditions, for instance, that depend on the values of the tokens, or the state of the actor, or both. These conditions can be specified using guards, as for example in the Split actor in Figure 2 Guards are included in scheduling information that defines the criteria for action to fire. The contents of an action, that are not scheduling information, are called its Chapter 2. Background body, and define what the action does. The difference is not so clear, for instance the expressions in the output pattern are part of the body, but the output pattern itself is scheduling information as it holds the number of tokens produced by the action. When an actor fires, an action has to be selected based on the number and values of tokens available and whether its guards are true. Action selection may be further constrained using a FSM, to select actions according to the current state, and priority inequalities, to impose a partial order among action tags.

Finite state machine (FSM)

An FSM is defined by the triple where S is the set of states, is the initial state, and is the state-transition function: Note that a state transition allows a set of actions to be fireable.

Tools of Rapid Prototyping Methodology

This section presents some tools integrated in our rapid prototyping methodology such as Orcc, Preesm, and HMPP.

Orcc, an Open RVC-CAL Compiler

Orcc include an RVC-CAL textual editor, a compilation infrastructure, a simulator and a debugger [2]. The primary purpose of Orcc is to provide developers with a compiler infrastructure to allow several languages and combination of languages (in the case of co-design) to be generated from RVC-CAL actors and networks.

Orcc does not generate assembly or executable code directly; rather it generates source code that must be compiled by another tool. This tool can generate code for any platform, including hardware (VHDL), software (C/C++, Java, LLVM...), and heterogeneous platforms (mixed hardware/software) from a RVC-CAL description.

How we could obtain the target code for specified architecture from the RVC-CAL description of our applications. This is the procedure of compilation. This section describes basic concepts of compilation, and in particular the concepts that are necessary to understand our work as described in the next chapters. Compilation is the process by which a program in a source language is transformed to another semantically-equivalent program in a target language as shown in Figure 2

Preesm, a Parallel and Real-time Embedded Executives Scheduling Method

The PREESM tool offers a fast prototyping tool for parallel implementations [3].

The inputs of the tool are architecture and algorithm graphs and a scenario that basically gathers all information linking algorithm and architecture. The target architectures are embedded heterogeneous architectures, with possibly several processors and many cores. The current version of PREESM focuses on static mapping/scheduling of algorithms. The Model of Computation (MoC) is used to describe algorithms based on Synchronous Dataflow Graphs (SDF) extended with the hierarchy feature.

The PREESM tool is not suitable for adaptable applications (DPN MoC of Orcc) in which the mapping/scheduling should be done partially or completely at runtime.

HMPP, a Hybrid Multicore Parallel Programming model

HMPP developed by CAPS, is a directive-based compiler to build parallel GPU applications, and support for the OpenACC standard [4]. HMPP offers a high level abstraction for hybrid programming that fully leverages the computing power of stream processors with a simple programming model. HMPP compiler integrates powerful data-parallel backends for NVIDIA CUDA and OpenCL that drastically For exploiting the better performance with HMPP, hmppcg directives can optimize the performance of generated HMPP kernel code:

1. The hmppcg gridify directives determine which loop should be parallelized.

Because of the gridif y(i, j), the i and j for-loops in line 3 and 4 will be parallelized.

1 # pragma hmppcg gridify (j , i ) 2 for ( k = 0; k < N ; k ++) 3 for ( j = 0; j < H ; j ++) 4 for ( i = 0; i < W ; i ++){ 5 ... 6 }
2. The hmppcg grid allocate the buffer (data storage region in device) to shared memory. The specified buffer will be loaded into shared memory before complex computations. Because accessing the shared memory is faster than the global memory (more details will be discussed in the 3.1), time efficiency will benefit from the hmppcg grid directive.

1

# pragma hmppcg grid shared buffer 3. Level 1 cache, is a static memory integrated with processor core that is used to store information recently accessed by a processor. Level 1 cache is often abbreviated as L1 cache. The purpose of L1 cache is to improve data access speed in cases when the processor accesses the same data multiple times. In NVIDIA's GPU devices of compute capability 2.0 and later, there is 64 KB of memory for each multiprocessor. This per-multiprocessor on-chip memory is split and used for both shared memory and L1 cache. By default, 48 KB is used as shared memory and 16 KB as L1 cache. The configuration of L1 cache preference: there is an obvious improvement of performance in our experiments.

Concerned Image and Video Processing Algorithms

Video decoders with Orcc and Preesm used to evaluate the prototyping framework in the previous research work. But video decoders are usually based on the dataflow and structure with a lot of data dependencies which are very hard to map with parallelism and to implement on many core heterogeneous systems. Some parallel applications are proposed in this thesis to evaluate the rapid prototyping framework which can fully make use of the parallelism of target architectures. Thus they are suitable to evaluate the efficiency of the rapid prototyping framework.

Motion estimation

Motion estimation (ME) is the process of determining motion vectors that describe the transformation from one 2D image to another, usually from adjacent frames in a video sequence. It is an ill-posed problem as the motion is in three dimensions but the images are a projection of the 3D scene onto a 2D plane. ME is the main time-consuming task of a video encoder with more than half of the whole computation load. In order to eliminate temporal redundancy, ME could find relative motions between two images as shown in Figure 2.17 The methods of motion estimation can be categorized into pixel based direct methods and feature based indirect methods.

Direct Methods

-Block-matching algorithm [START_REF] Wei-Nien | 264/AVC motion estimation implmentation on Compute Unified Device Architecture (CUDA)[END_REF] -Phase correlation and frequency domain algorithms [START_REF] Erdem | Motion estimation in the frequency domain using fuzzy c-planes clustering[END_REF] -Pixel recursive algorithms [START_REF] Fakih | A factorized recursive estimation of structure and motion from image velocities[END_REF] -Optical flow algorithms [START_REF] Werlberger | Motion estimation with non-local total variation regularization[END_REF] Indirect Methods employs features, such as corner detection, and match corresponding features between frames, usually with a statistical function applied over a local or global area. The purpose of the statistical function is to remove matches that do not correspond to the actual motion.

Block matching ME algorithms are most widely used in video compression standard, also the most concerned in this thesis. There is a brief overview of available motion estimation systems shown in Table 2.2. The frames per second (f ps) indicates the processing speed of the different systems. [START_REF] Mehta | A high-performance parallel implementation of sum of absolute differences algorithm for motion estimation using cuda[END_REF] threshold in the SAD 640 × 480, 32 × 32 52.5 GPU martin et al. [START_REF] Martin | Fast Motion estimation on Graphics Hardware for H.264 Video Encoding. Multimedia[END_REF] samll diamond search 352 × 288, 16 × 16 20 GPU chen et al. [START_REF] Wei-Nien | 264/AVC motion estimation implmentation on Compute Unified Device Architecture (CUDA)[END_REF] variable block size 352 × 288, 32 × 32 31.5 GPU Luo et al. [START_REF] Jiancong Luo | Motion estimation for content adaptive video compression[END_REF] content adaptive search technique 352 × 288, 32 × 32 60.7 CPU Lee et al. [START_REF] Chuan-Yiu | Multi-Pass and Frame Parallel Algorithms of Motion Estimation in H.264/AVC for Generic GPU[END_REF] multi-pass full search 352 × 288, 32 × 32 8.89 GPU Li et al. [START_REF] Brianm | Serial and parallel fpga-based variable block size motion estimation processors[END_REF] most significant bit 640 × 480, 32 × 32 129 FPGA Urban et al. [START_REF] Urban | HDS, a real-time multi-DSP motion estimator for MPEG-4 H.264 AVC high definition video encoding[END_REF] HDS for Hierarchical Diamond Search 720 × 576, 32 × 32 100 DSP

Stereo matching

As shown in Figure 2.18, stereo matching is a technique aimed at computing depth information from two cameras used in many applications such as 3D-TV, 3D reconstruction and 3D object tracking.

In Epipolar Geometry, some essential concepts in stereo matching are shown in

B Z = (B + X R ) -X T Z -f ⇒ Z = B • f X T -X R = B • f d (2.4)
The above equation basically demonstrates that the more deep the object lies, the less disparity it has between the stereo pair in the input videos, and this principle is also the basis of stereo matching.

Conclusion

In this chapter, the background has been presented. It also gives the reader the necessary knowledge on the theoretical and practical aspects of parallel computing, rapid prototyping methodology and image of video processing algorithms (motion estimation and stereo matching). In section 2.1, we presented and compared different target architectures CPU, GPU, and MPPA Kalray. We have presented an intermediate level programming model: OpenCL in section 2.2. OpenCL programming model and development environments are described in this section. In section 2.3,

we presented an high level programming model: the dataflow approach. This section introduce the different MoC, dataflow sigmaC for the platform MPPA Kalray, and the high level description language RVC-CAL used in our descriptions of application in the following sections. Some tools of rapid prototyping methodology is presented in section 2.4. Finally, we introduced the basic concept of motion estimation and stereo matching algorithms whose applications are widely used in industry and science in section 2.5. The next chapter will introduce the parallelized motion estimation based on heterogeneous computing system.

Parallelized Motion Estimation Based on

Heterogeneous System

Introduction

Fast ME algorithms

Tourapis et al. [START_REF] Michael | Enhanced predictive zonal search for single and multiple frame motion estimation[END_REF] proposed the Predictive Motion Vector Field Adaptive Search Technique (PMVFAST), which significantly outperforms most previously proposed Cheung et al. [START_REF] Cheung | Novel cross-diamond-hexagonal search algorithms for fast block motion estimation[END_REF] proposed two cross-diamond-hexagonal search (CDHS) algorithms, which differ from each other by their sizes of hexagonal search patterns.

To further reduce the checking points, two pairs of hexagonal search patterns are proposed in conjunction with candidates found located at diamond corners. Experimental results show that their method perform faster than the diamond search (DS) by about 144% and the cross-diamond search (CDS) by about 73%, whereas similar prediction quality is still maintained. Moradi et al. [START_REF] Moradi | Enhanced crossdiamond-hexagonal search algorithms for fast block motion estimation[END_REF] proposes two enhanced CDHS algorithms to solve the motion-estimation problem in video coding. These algorithms differ from each other by their second step search only, and both of them employ cross-shaped pattern in first step. Their method is an improvement over CDHS, which eliminates some checking points of CDHS algorithm. Experimental results show that their methods perform faster than the diamond search (DS) and CDHS, whereas similar quality is preserved.

Yao et al. [START_REF] Nie | Adaptive rood pattern search for fast blockmatching motion estimation[END_REF] In order to obtain better performance with hardware accelerators like GPU, we port our source C code to the kernel code through our rapid prototyping methodology. In general, there are two ways to perform the code porting. One is to manually write the kernel of CUDA or OpenCL which redesign the code and compile the kernel code with the specified compiler. The other way utilize rapid prototyping framework like the one we proposed in the last chapter to automatically generate code executable on hardware accelerators from the high-level description of applications.

1. First we generate the HMPP code (C code with HMPP directives) from the high-level description of RVC-CAL.

2. Second we generate the OpenCL and CUDA kernel through HMPP compiler.

In this chapter, we elaborate the two ways of porting code to GPUs and describe how our rapid prototyping framework works.

This chapter is organized as follows: Section 3.2 illustrates our approach of motion estimation with OpenCL. Section 3.3 presents the optimization strategies of our ME implementation and the experimental results. Section 3.4 applies our proposed algorithm on the heterogeneous computing system with OpenCL and presents the method to distribute workload in the heterogeneous system. Section 3.5 introduces the high level CAL description of ME and how our rapid prototyping framework works, also gives the analysis of experiments result. A brief conclusion is given in Section 3.6.

Parallelized Motion

Parallelized Motion Estimation Algorithm

Two aspects should be considered for distributing workloads to GPUs or CPUs, namely massively parallelized motion search and calculation of the matching criterion in motion estimation algorithms. Full Search ME process is to search the best candidate of macroblock (MB) in reference frame (the frame before current frame in video sequence, N-1 frame in Figure 2.17) for the original macroblock in current frame (N frame in Figure 2.17).

There is one question: how we determine the best candidate macroblock in reference frame? Here, we chose SAD as the matching criterion for selecting the best Motion Vectors (MV) in (3.1). M is the specified block size.

SAD = M i=1 M j=1 |block_current(i, j) -block_ref (i, j)| (3.1)
The proposed Full search ME approach is divided into two OpenCL kernels. One is SADs computation; the other is SADs comparison for the best SAD candidate (final MV). We define the two OpenCL kernels as kernel_compute (see in Algorithm

SAD computation

Based on block matching method, each frame is divided into macroblocks (MBs, This differentiates our approach from approaches of [START_REF] Wei-Nien | 264/AVC motion estimation implmentation on Compute Unified Device Architecture (CUDA)[END_REF] and [START_REF] Chuan-Yiu | Multi-Pass and Frame Parallel Algorithms of Motion Estimation in H.264/AVC for Generic GPU[END_REF]

M B_size = M B_width × M B_height = 16 × 16 =

SAD comparison

In kernel_compare, we search the best candidate with the minimum SAD from cost[1024] using 256 work-items as presented in Algorithm 3. First, the cost [1024] is transferred into local memory. Then, each work-item compares 4 candidates with stride to find the minimum as equation (3.3).

cost[i] = M in(M in(cost[i], cost[i + stride]), M in(cost[i + 2 × stride], cost[i + 3 × stride])) (3.3)
where i is the index of work-items, i ⊆ [0, 255], stride is equal to the number of work-times (stride = 256). At last, there are 256 candidates remained from cost[0]

to cost [255]. We employ the parallel reduction method [START_REF]OpenCL Programming for the CUDA Architecture[END_REF] which adopts x times iterations (2 x = 256, x = 8) to find the candidate with the minimum SAD value from the remaining 256 candidates, also to obtain the final MV. Parallel reduction is usually used to sum up the data in large dataset. Here we use it as one sorting approach.

Optimization Strategies of Parallel Computing 3.3.1 Using shared memory

Accessing shared memory it is where OpenCL local memory reside) is as fast as accessing a register, and the shared memory latency is 100x lower than the device memory latency. To achieve high memory bandwidth for concurrent accesses, the shared memory is divided into equally sized memory banks that can be accessed simultaneously. However, if multiple addresses of a memory request mapping to the same memory bank, these accesses are serialized and caused banks conflict. To gain maximum performance, it is therefore important to understand how memory addresses map to memory banks in order to schedule the memory requests so as to minimize the bank conflicts. The most efficient way to avoid bank conflict is the

Using vector data

There are special vector instruction sets for vector data of Intel's CPU and NVIDIA's GPU, named vectorization. Each work-item can process several elements which benefit from vectorization of kernel code. Algorithm 4 and Algorithm 5 present the pseudo code with vectorization and without vectorization respectively.

In our implementation as shown in Algorithm

Compute Unit Occupancy

Experimental Result

We first briefly introduce the different GPU architectures used in this chapter.

From the Table 3.1, we can find out the different features of selected GPUs which are factors to impact the performance of general purpose computing, and also are foundations that we choose to normalize the performance of different GPUs.

For instance, our GPU NVIDIA GT540m has 2 Compute Units (CUs), and

Matching Accuracy

Secondly, we compare the time consuming and PSNR with selected state-of-theart fast ME algorithms: Four-step search (4SS) [START_REF] Po | A novel four-step search algorithm for fast block motion estimation[END_REF], Adaptive Rood Pattern Search

(current f rame (i, j) -ref f rame (i + dx, j + dy)) 2 (3.5)
where (dx, dy) is the calculated motion vector. Our time consuming and PSNR are the average value based on total 300 frames of test video.

Heterogeneous Parallel Computing with OpenCL

In this section, we employ the special feature of OpenCL -Heterogeneous Parallel

Computing [START_REF] Stone | OpenCL: A parallel programming standard for heterogeneous computing systems[END_REF] to dig for the better performance of our proposed algorithm. First we build one heterogeneous parallel computing environment with one CPU (I7 2630qm) and one GPU (GT540m) as coprocessor for our arithmetic data-parallel computing with OpenCL. Then we distribute the workload to CPU and GPU respectively. In such a heterogeneous computing system, we should determine the usage model of multi-devices and workload distribution. In order to minimize the cost of memory transferring between different devices, we prefer to use multi-input and multioutput for multi devices (assigning workload for different devices respectively).

Under the perfect condition, all devices complete their workload at the same time, and the total time should be the minimum.

Cooperative multi-devices usage model

For heterogeneous computing environment with different devices, we build one cooperative multi-devices model. In OpenCL, there are two kinds of models for multi-devices:

1. Separate contexts for different devices.

Workload distribution

With the fixed problem size, how to distribute the workload to different devices is the key point to gain the enhancement of performance in heterogeneous computing systems. In the video applications, the basic problem unit is the frame or image.

We make one supposition that one test video sequence has N frames. We transfer we can obtain the best performance of heterogeneous computing system.

M

Find the balance of performance

As some results we have presented in [START_REF] Zhang | Implementation of motion estimation based on heterogeneous parallel computing system with opencl[END_REF], we should repeat enough experiments to generate the experimental curves of performance as shown in Figure 3.11 and T cpu (x) = 29x 2 -52x + 6 (3.7)

T gpu (x) = 8x 2 -11x -2.7 (3.8)
Then we calculate the suitable M value according to our hypothesis:

T cpu (M ) = T gpu (N -M ) 29M 2 -52M + 6 = 8(N -M ) 2 -11(N -M ) -2.7 (3.9)
As our test video sequence has 300 frames (N = 300), the final suitable M is calculated as 105 according to equation (3.9). It means that M = 105 is the best tradeoff of proposed ME method based on our heterogeneous computing system.

The practical experiment with CPU and GPU has verified the feasibility of our hypothesis. When the number of frames for CPU is around 100, the heterogeneous system consumes the least time as shown in Figure 3.13.

Analysis of experiments result

To the best of our knowledge, there are several criterions of evaluation for final results of our implementations: algorithm accuracy, time efficiency, percentage of shared memory and compute units occupancy. For the algorithm accuracy, we compare the output (motion vector) of our C, manually writing OpenCL and HMPP OpenCL implementations, all the results are consistent.

Conclusion

This chapter has presented one parallelized ME algorithm with OpenCL, and the proposed algorithm executed on heterogeneous parallel system which contains CPU and GPU. The experimental results show that, our implementation has the better performance than other GPU-based FSME implementations and also obtains better balance between time efficiency and PSNR than the state-of-the-art fast ME algorithms. And our method has the better speed-up ratio comparing with other GPU-based implementations of ME due to our optimizations like shared memory and vectorization.

We have also developed one basic method to find the balance of workload on heterogeneous parallel computing system with OpenCL. Additionally, experimental results show that we have found the accurate method to distribute the workload in video applications based on heterogeneous computing system which achieves obviously enhancement of performance. With the proposed rapid prototyping framework, we can directly and rapidly generate the target code like OpenCL/CUDA for heterogeneous system. In the meantime, we analyze the performance of the two kinds of methods porting source C code to the code executed on GPU.

Real Time Local Stereo Matching Method

Introduction

Due to the high computational complexity, stereo matching is still a great challenge to obtain high quality disparity map in real-time applications. In the case of stereo matching algorithm, the two major concerns are its matching accuracy and time efficiency. To improve them, many algorithms are proposed and splitted into

i=n j=m = | n 2 | i=-| n 2 | | m 2 | j=-| m 2 | (4.1)
The show their local method is effective and robust, and even outperforms some of the well-known global methods. Kaaniche et al. [START_REF] Kaaniche | Vector lifting schemes for stereo image coding[END_REF] proposed a novel approach, based on vector lifting schemes (VLS), which offers the advantage of generating two compact multi-resolution representations of the left and the right views. Trinh et al. [START_REF] Trinh | Unsupervised learning of stereo vision with monocular cues[END_REF] demonstrated unsupervised learning of a 62 parameter slanted plane stereo vision model involving shape from texture cues. Their approach to unsupervised learning is based on maximizing conditional likelihood. The shift from joint likelihood to conditional likelihood in unsupervised learning is analogous to the shift from Markov random fields (MRFs) to conditional random fields (CRFs). The performance achieved with unsupervised learning is close to that achieved with supervised learning for this model.

(I l (x + i, y + j) -I r (x + d + i, y + j)) 2 (4.4) N CC = i=n j=m |I l (x + i, y + j) -I r (x + d + i, y + j)| i=n j=m I l (x + i, y + j) 2 i=n j=m I r (x + d + i, y + j) 2
We mainly focus on paired image methods as the essential components stereo matching. However, it should be relatively straightforward to transform these methods to include multi-images application like multiple-baseline stereo matching [START_REF] Okutomi | A multiple-baseline stereo. Pattern Analysis and Machine Intelligence[END_REF] and its plane-sweep generalizations [START_REF] Collins | A space-sweep approach to true multi-image matching[END_REF][START_REF] Szeliski | Stereo matching with transparency and matting[END_REF]. Speers et al. [START_REF] Speers | Tuning stereo image matching with stereo video sequence processing[END_REF] explored the use of feedback from the environmental model being constructed to the static stereopsis task. A prior estimate of the disparity field is used to seed the stereo matching process within a probabilistic framework. Wang et al. [START_REF] Wang | Global stereo matching leveraged by sparse ground control points[END_REF] presented a novel global stereo model that makes use of constraints from points with known depths, i.e., the Ground Control Points (GCPs) as referred to in stereo literature. Their formulation explicitly modeled the influences of GCPs in a Markov Random Field. A novel GCPs-based regularization term is naturally integrated into our global optimization framework in a principled way using the Bayes rule. The optimal solution of the inference problem can be approximated via existing energy minimization techniques such as graph cuts used in this paper. Their generic probabilistic framework allows GCPs to be obtained from various modalities and provides a natural way to integrate the information from multiple sensors.

GPU-based stereo matching

Facing with dense and complexity computation, high-accuracy stereo matching algorithms are very hard to perform with traditional CPU platform in real-time.

In the meantime, the nature of stereo matching algorithms has a great advantage of employing the parallelism of GPU devices. Hosni et al. [START_REF] Hosni | Real-time local stereo matching using guided image filtering[END_REF] suggested to use the recently proposed guided filter to overcome this limitation. Analogously to the bilateral filter, this filter has edge preserving properties, but can be implemented in a very fast way, which makes their stereo algorithm independent of the size of the match window. The GPU implementation of stereo algorithm can process stereo images with a resolution of 640 × 480 pixels and a disparity range of 26 pixels at 25 fps.

Zhu et al. [START_REF] Zhu | Comparison of dense stereo using cuda[END_REF] proposed a dense stereo matching method implemented using CUDA. It presented the general strategy of the parallelization of matching methods on GPUs, the tradeoff between accuracy and time-consumed on current GPU hardware. Two representative and modern widely-used methods, the Sum of Absolute Differences (SAD) method and the Semi-Global Matching (SGM) method, are used and their results are compared using the Middlebury test sets. Our work of stereo matching also focus on the tradeoff between accuracy and time-comsuming on our heterogeneous platforms which will be discussed in section 4.3.

Stereo applications

Stereo matching technique has a widely applications in computer vision and pattern recognition as follows [START_REF] Nefian | A bayesian formulation for sub-pixel refinement in stereo orbital imagery[END_REF] [92] [START_REF] Bleyer | Temporally consistent disparity maps from uncalibrated stereo videos[END_REF] [94] [95]: Nefian et al. [START_REF] Nefian | A bayesian formulation for sub-pixel refinement in stereo orbital imagery[END_REF] proposed one stereo matching technique used in NASA plans manned missions to generating accurate three dimensional planetary models. Their methods described a stereo correspondence system for orbital images and focuses on a novel approach for the sub-pixel refinement of the disparity maps which uses a Bayesian formulation that generalizes the Lucas-Kanade method for optimal matching between stereo pair images. Their method was demonstrated on a set of high resolution scanned images from the Apollo era missions.

Kuhl et al. [START_REF] Kuhl | Comparison of stereo matching algorithms for mobile robots[END_REF] employed the stereo matching technique in navigation and obstacle avoidance of mobile robots. Depth maps provide an essential description of the world seen through cameras to satisfy the perception and identification of the surrounding environment. They also investigated with different types of stereo matching algorithms to build and to implement a system for generating depth maps on a mobile robot. Bleyer et al. [START_REF] Bleyer | Temporally consistent disparity maps from uncalibrated stereo videos[END_REF] addressed the problem of computing a sequence In all, one of our two main aims in this chapter is to propose a local stereo matching algorithm that greatly balances the matching accuracy and time efficiency.

Our method is shown in the first part of This chapter is organized as follows: Section 4.2 describes our real time stereo matching method; Section 4.3 presents experimental results about matching accu-racy and time efficiency from the Middlebury Stereo Database [START_REF]Middlebury stereo vision[END_REF] and CAL description for different architectures; Section 4.4 gives a brief conclusion.

Proposed Stereo Matching Algorithm

Extending from with the Census cost. The cost aggregation computes the matching cost by a weighted method, which is iterated on both horizontal and vertical directions. In the third stage, the Winner-Takes-All (WTA) method is applied to determine the final disparities.

Combined cost construction

There are various methods of cost measure such as TAD or intensive-based or gradient-based measure, but few methods combine cost measure. In fact a suitable combination can greatly improve the accuracy of the raw matching. To this end, we define the measure method that combines the TAD cost with the Census cost.

In addition, our local method distinguishes each pixel at each disparity as shown in Equation (4.9) combines the two costs to the range from 0 to 1 and controls the outliers by the λ parameters.

Proposed cost aggregation method

Cost aggregation consumes the most time of a stereo matching algorithm. Thus our method limits the aggregation of neighboring pixels in order to reduce the spatial complexity, while maintaining data parallelism required for an efficient implementation on GPU.

To this end, we employ adaptive weights in our implementation: this approach is to adjust weight of each pixel based on the intensity of neighboring pixels and on a geometric relationship with the central pixel [START_REF] Yoon | Locally adaptive support-weight approach for visual correspondence search[END_REF]. Basically, a higher weight will be assigned to a pixel if its intensity and its distance are closer to the central pixel.

We define our adaptive weight w(pl, q) as follows:

w(pl, q) = exp(-|I pl -I q |/λ I -||pl -q||/λ d ) (4.11)
where pl is the central pixel of the left image and q is a pixel in the neighborhood of pl. |I pl -I q | is the intensity absolute difference between the pl and q pixels, while ||pl -q|| is the Euclidean distance between them. λ I and λ d are constant parameters that adjust the balance of both kinds of weight.

Instead of processing with a N × N fixed window, we perform a cross approach on the image that costs are aggregated in a first horizontal pass followed by a second vertical pass. To cover the specified range of influence, several iterations are performed in both directions to get the final aggregated cost. Thus, at each iteration i, each pixel is the aggregation of the costs of three pixels, i.e. the target pixel and where s is the size of the iteration step: a squared step (s = i 2 ) proposed in our implementation in order to reduce the complexity. Thus, our iterative method performs the processing on only 9 (3 × 3) pixels, which provides a significant reduction compared to the conventional method.

Disparity selection

Among all the disparity assumptions, the Winner-Takes-All (WTA) method is performed to determine the disparities:

D(pl) = arg min d∈[d min ,dmax] C(pl, d) (4.13)

Post processing of disparity maps

To improve the disparity maps and eliminate the bad matching pixel, we calculate the disparity maps both the left and right image respectively for post processing of disparity maps. Normally the disparity maps contain outliers in the occlusion and depth discontinuities regions [START_REF] Scharstein | A taxonomy and evaluation of dense two-frame stereo correspondence algorithms[END_REF] [100] [START_REF] Hirschmuller | Stereo processing by semiglobal matching and mutual information[END_REF]. The first step is detecting these outliers as much as possible with left-right consistency check; the second step is adopting refinement methods to fill them with nearest reliable disparities.

left-right consistency check

Left-Right Consistency (LRC) check is performed to get rid of the occlusion (objects scene in one image, and not in other) pixels in the final disparity map. This is computed by taking the computed disparity value in one image, and re-projecting it in the other image. If the difference in the values is less than a given threshold, then the pixels are half-occluded. In the occlusion maps, the light areas are occlusion parts and are not reliable, thus the disparities in these areas are not reliable either.

The function of consistency check is to detect these occlusion areas and modify them with the closest reliable disparities. The adjustment of reliable disparity is given in Equation 4.14.

       |D L (x, y) -D R (x -D(x, y), y)| ≤ threshold, lef t |D R (x, y) -D L (x + D(x, y), y)| ≤ threshold, right (4.14)
where D L (x, y) is the disparity of left image, and the D R (x, y) is the disparity of right image.

In addition, the consistency check also makes up the corresponding unreliable boundaries (left boundary of left depth map and right boundary of right depth map) by replacing them with the nearest reliable disparities in the same scan-line.

Region Voting

The detected outliers should be filled with reliable neighboring disparities value. In the meantime, we also proposed another description of stereo matching. It is designed to distributes the specified workload on multi-DSP platforms as shown in [START_REF]Cuda2opencl[END_REF][START_REF] Sung | Demonstration of codesign workflow in peace[END_REF], [START_REF] Grandpierre | From algorithm and architecture specifications to automatic generation of distributed real-time executives: a seamless flow of graphs transformations[END_REF][START_REF] Werlberger | Motion estimation with non-local total variation regularization[END_REF], [START_REF] Mehta | A high-performance parallel implementation of sum of absolute differences algorithm for motion estimation using cuda[END_REF][START_REF] Zhang | Realtime accurate stereo with bitwise fast voting on cuda[END_REF], [START_REF] Yang | Improved real-time stereo on commodity graphics hardware[END_REF][START_REF] Schwalb | Fast motion estimation on graphics hardware for h.264 video encoding[END_REF] respectively). The block "rebuild" indicates a FU that reorganize these costs from different channels into final costs.

CAL description of stereo matching

Experimental Result and Discussions

For stereo matching algorithm, many test source and test scene are proposed.

Andorko et al. [START_REF] Andorko | Proposal of a universal test scene for depth map evaluation[END_REF] proposed a new disparity map testing scene for consumer electronic devices. The Middlebury stereo database [START_REF]Middlebury stereo vision[END_REF] is the most famous and widely used test benchmark. It has many standard paired images with ground truth. Stereo matching methods calculate the disparity from these paired images, submit to the online benchmark system and obtain the ranking in whole already submitted methods according to the percentage of bad matching pixels. We evaluated the performance of our proposed stereo matching method with the benchmark Middlebury stereo database [START_REF]Middlebury stereo vision[END_REF]. These parameters are constant in our experiments on several stereo datasets, i.e, σ = 12, λ census = 6, λ T AD = 20, λ I = 15, λ d = 15. And we analyse our matching algorithm from its matching accuracy and time efficiency. paring with the two methods: ESAW [START_REF] Yu | Real time stereo vision using exponential step cost aggregation on gpu[END_REF] and RTcensus [START_REF] Humenberger | A fast stereo matching algorithm suitable for embedded real-time systems[END_REF]. Figure 4.13 shows our disparity results and bad pixels maps of Middlebury Stereo Evaluation. Our disparity map outperforms the other two methods in the discontinued region (red circle mark) and flat region (blue circle mark). Table 4.1 lists the error rate of our experimental algorithm according to the evaluation of Middlebury. The error rate in non-occluded (nonocc) regions, all regions (all), and depth-discontinuity (disc) regions are illustrated respectively. As we discussed in the last section, the AD-census method proposed by Mei et al. [START_REF] Mei | On building an accurate stereo matching system on graphics hardware[END_REF] is in the top 5 of Middlebury benchmarks.

Different with our method, it employees the different way of combination of AD and Census costs and aggregate all the possibility in the support region for better matching accuracy. But better accuracy brings huge time consuming of 15 seconds on teddy paired images on Intel Core2Duo 2.2Hz CPU platform who is very hard to be optimized to implement on embedded system in real-time.

In the meantime, we consider and verify the "real-world" problems of illumination condition. We compare the intensity-based method like ESAW with our method in

Time-efficiency results

As shown in Figure 4.12, our GPU-based implementations are over 10 times fast than the C implementation. Our approach obtains 700ms, 1200ms, 3200ms, 3200ms based on the CPU platform and 50ms, 70ms, 150ms, 150ms based on the GPU platform for Tsukuba, Venus, Teddy, Cones of Middlebury stereo benchmark respectively.

Proposed stereo matching method with SigmaC dataflow

In the section 2.1.2, the MPPA of KALRAY is introduced with its own dataflow approach SigmC. Because of its many cores strategy (256 cores total), the MPPA has great potential in parallel computing. Alexandre MERCAT described the proposed stereo matching method with SigmaC dataflow. The implementation of proposed method is verified on the platform of MPPA. In this SigmaC dataflow description, there are six agents assigned for function ComputeGrayImage, nine agents assigned dernière partie est consacrée à l'optimisation de l'algorithme an de générer la version e. Cependant, cette version ne respecte pas entièrement les dépendances de l'algorithme sion de référence de l'algorithme, les diérentes parties étaient réalisées sur diérents c de la mémoire requise pour les agents. A l'inverse, cette version a pour but d'utiliser un

Conclusions

This chapter has presented our real-time stereo matching algorithm. Our method integrates the cost construction by combining Census with TAD measure cost, aggregates the raw matching cost by a adapt weighted method, which is iterated on both horizontal and vertical directions. The Winner-Takes-All (WTA) method is applied to determine the final disparities in the end.

Two high-level descriptions of proposed stereo matching method are introduced.

One is for Orcc HMPP branch, another is designed for multi-core parallel architecture. Based on our rapid prototyping framework, OpenCL/CUDA kernel code is automatically generated for GPU Platform. Our GPU-based implementations are over 10 times faster than C implementation and the Optimized HMPP gains 25%-45% improvement about processing speed compared with default HMPP. Experimental results show that our method outperforms other real-time stereo matching methods about tradeoff between matching accuracy and time-efficiency.

Joint Motion-Based Video Stereo Matching

Introduction

For static paired image, estimating disparity has been well developed in two last several decades. For video sequences, most of stereo matching methods only take care of the "spatial intra-frame" (i.e,paired images with the same order) and a few methods not involve the "temporal inter-frame" (i.e, consequent paired images in video sequence). The use these of spatial intra-frame methods leads to flicker-frames and worse bad matching results.

To deal with this problem, Lee et al. [START_REF] Zucheul Lee | Local stereo matching using motion cue and modified census in video disparity estimation[END_REF] proposed one local method based on the optical flow in a video for the disparity estimation. But their method cost 19 seconds for paired frames at 400×300 resolution which is not fast enough in real applications.

Most of the time is spent for the motion estimation in video sequence. Khoshabeh et al. [START_REF] Khoshabeh | Spatio-temporal consistency in video disparity estimation[END_REF] proposed one method based on the spatio-temporal consistency in the video to estimate the disparity. This method applies an l 1 -normed minimization on a novel three dimensional Total Variation (TV) regularization (Chan et al. [START_REF] Chan | An augmented lagrangian method for total variation video restoration[END_REF]). Due to their unique formulation, other static image stereo matching algorithms could use the method as a post-processing step to refine noisy. The method emphasizes how the motion cue impacts the adaptive weight, and does not consider the way to build the support region with the help of the motion cue. Support region is built by these neighbors' pixels when the costs aggregation happened. Bleyer et al. [START_REF] Bleyer | Temporally consistent disparity maps from uncalibrated stereo videos[END_REF] address this problem of computing a sequence of dense disparity maps from two synchronized video streams recorded by slightly displaced cameras. visual grouping play the significant role of building a support region and relative support-weights. There are so many visual cue used in visual grouping. Beside color similarity and geometric proximity, motion cue is also a key factor in the stereo video matching. The main idea of our proposed method is to build a support region with motion cue from motion estimation. Block-based motion estimation is the process of determining motion vectors between adjacent frames in a video sequence. We obtain accurate motion vectors for each block (these block size equal to 2 n × 2 n ) by directly employing our parallelized GPU-based motion estimator introduced in chapter 3. In White color means there is no motion happened, and the darker color means the more explosive motion. We can make such a supposition: These motion blocks with the similar motion amplitude should have the same disparity.

As inspired by the work of Zhang [START_REF] Zhang | Cross-based local stereo matching using orthogonal integral images[END_REF] and Mer [START_REF] Mei | On building an accurate stereo matching system on graphics hardware[END_REF], we build one pixelwise adaptive cross which consists of vertical and horizontal segments, crossing at pixel p. To model a suited cross for pixel p, we should determine the length of left, Chapter 5. Joint Motion-Based Video Stereo Matching right, up, bottom limit as shown in Figure 5.2. Zhang et al. [START_REF] Zhang | Cross-based local stereo matching using orthogonal integral images[END_REF] employs the color similarity under the connectivity constraint. The length of limits is only decided upon color similarity. For the selected pixel p, the largest span is defined as R, where all these pixels covered in this span have the similar color with pixel p. p q up limit bottom limit left limit (r Π i∈ [1,r] δ(p, p i )), (

right limit p p (a) (b) (c)
where p = (x, y), p i = (x -i, y) and L is the preset largest length of limits (the default value of L is 13). δ(p 1 , p 2 ) is one judgement function based on the color similarity between the pixels p 1 and p 2 .

δ(p 1 , p 2 ) =      1, max c∈[R,G,B] (|I c (p 1 ) -I c (p 2 )|) ≤ τ 0, otherwise . ( 5.2)
where i c is the intensity of color band c (c ∈ R, G, B). τ is the termination threshold in color similarity.

For stereo video matching, we propose such improvements as follows. Extending our above suppose, we also confirm that each pixel in blocks with the similar motion amplitude also have the same disparity. Firstly, each pixel of input RGB image I (current frame of video) can be described as p = (i, (x, y)). i is the gray value transformed form the RGB channels. (x, y) is the 2D coordinates in the input image.

After the motion estimation, every pixel is defined as p = (i, (x, y), (dx, dy)). So the judgment function δ(p 1 , p 2 ) is redefined by:

δ(p 1 , p 2 ) =     
1, (|I gray (p 1 ) -I gray (p 2 )|) ≤ τ gray 0, otherwise .

(

where avoid repetitive comparison in R,G and B channels. In the dataflow of our method, every pixel is one vector set which will benefit of following GPU computing.

Second, we make use of the combination of motion amplitudes (dx, dy) and the color similarity to determine the length of each limit as described in the new definition of largest span:

enlarged motion amplitude of x axis enlarged motion amplitude of y axis

R = max r∈[1,L] (r Π i∈[1,r] δ(p, p i )ϕ(p, p i )), (5.4)
where ϕ(p 1 , p 2 ) is the judgment function based on the motion amplitude between the pixel p 1 and p 2 .

ϕ(p 1 , p 2 ) =      1, (|dx(p 1 ) -dx(p 2 )| + |dy(p 1 ) -dy(p 2 )|) ≤ τ motion 0, otherwise . ( 5.5)
where dx(p) is the motion amplitude of pixels p in x axis, dy(p) is the motion amplitude in y axis.

As shown in Figure 5.1 and 5.

1 1 0 1 0 1 0 1 0 1 1 0 1 1 1 1 0 1 0 1 1 1 1 1

Census cost = 3

Left image window Right image window

0 1 0 1 1 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 1

Combined raw cost construction

We use the combined raw cost construction defined in section 4. Every bit is set to 0 if the neighboring pixel in the census window has a lower intensity than the center pixel, and 1 otherwise [START_REF] Humenberger | A fast stereo matching algorithm suitable for embedded real-time systems[END_REF]. Our sparse sampling of census not only saves 75% of the time for computing census transforming, but also brings

Gaussian adaptive support weights

We have decided the support region and constructed the initial cost C(pl, d).

The support region has been defined and initial cost has been computed. For the accurate matching result, it should aggregate the cost of these support pixels to the central pixel pl with adaptive weights. Motivated by Gestalt theory of perceptual grouping, the weight between two pixels is defined as:

w(pl, q) = exp(-|I pl -I q |/λ i -||pl -q||/λ d ) (5.6)
where pl is one of central pixels in left image, q is one of neighbor pixels around pl, |I pl -I q | and ||pl -q|| is the intensity difference and the Euclidean Distance between pixel pl and pixel q respectively. λ i and λ d are the constant parameter that adjust the balance of two kind of weights. We set the default value of λ I = 17.5 and λ d = 5

as proposed in Yoon's work [START_REF] Yoon | Adaptive support-weight approach for correspondence search[END_REF].

Chapter 5. Joint Motion-Based Video Stereo Matching

Inspired by Richardt's work [START_REF] Richardt | Real-time spatiotemporal stereo matching using the dual-crossbilateral grid[END_REF], we rebuild Yoon's method using Gaussian weight with the help of the motion amplitude.

w(pl, q) = G σ i (|I pl -I q |)•G σ d (||pl-q||)•G σm (|dx(pl)-dx(q)|+|dy(pl)-dy(q)|). (5.7)
where σ i , σ d and σ m are constant parameters, and G σ = exp( -x 2 σ 2 ). When one pixel located in background or moveless region ((|dx(pl) -dx(q))| + |dy(pl) -dy(q)|) = 0, G σm = 1), the equation (5.7) becomes (5.8).

w(pl, q) = G σ i (|I pl -I q |) • G σ d (||pl -q||).
(

The weight branch G σm will not bring extra noise or unreasonable weight for moveless region in cost aggregation.

So our aggregated cost is now recalculated as: ,d) q∈Sp w(pl, q) • w(pr, q) , (5.9)

C ′ (pl, d) = q∈Sp w(pl, q) • w(pr, q) • C(pl

Proposed cost aggregation

We adopt the same cost aggregation as described in section 4.2.2. The conventional adaptive weight method will aggregate cost along horizontal pass and will store the intermediate cost value. Then, the same job in vertical pass will be computed as shown in the Figure 4.5 (b) and 4.5 (c). Instead of aggregating all the pixels in the support region along the horizontal pass, we perform a square step approach. For instance, we use the largest length of support region bras L = 13 to illustrate how the aggregation approach works. To cover the specified bras's length [-13, 13], several iterations are repeated in the horizontal pass. Thus, at each iteration i, every pixel aggregates the costs of three pixels: target pixel and pixels with -s and +s offsets (s = i 2 is the square step size). The aggregated cost is stored as an intermediate cost value in the location of pixel q.

Disparity determination

After matching cost aggregation, the Winner-Takes-ALL (WTA) is performed for disparities determination among all the disparity assumptions as:

D(pl) = arg min d∈[d min ,dmax] C ′ (pl, d) (5.10)
Where d ∈ [d min , ..., d max ] is the set of all possible disparities.

Video Stereo matching Implementation with

Heterogeneous System

The proposed joint-motion based stereo video matching method is very friendly for parallel computing system. The heterogeneous parallel computing with OpenCL

Evaluation and Discussions

To evaluate the proposed method, we test it on 5 synthetic stereo videos from [START_REF] Richardt | Real-time spatiotemporal stereo matching using the dual-crossbilateral grid[END_REF]. The definition of each frame is 400× 300 pixel with 64 disparity ranges. These parameters are preset to constant value: τ gray = 15, τ motion = 8, γ = 10, σ i = 10, σ d = 10 and σ m = 5, L = 13 in our implementation. Likewise, we run our method against LASW [START_REF] Yoon | Adaptive support-weight approach for correspondence search[END_REF], HBP-TV [START_REF] Khoshabeh | Spatio-temporal consistency in video disparity estimation[END_REF], TDCB [START_REF] Richardt | Real-time spatiotemporal stereo matching using the dual-crossbilateral grid[END_REF] on 5.4. Evaluation and Discussions 101 all the 5 synthetic video with synthetic ground truth. LASW is the classic adaptive support-weight approach proposed by Yoon [START_REF] Yoon | Adaptive support-weight approach for correspondence search[END_REF]. HBP-TV is the Hierarchical Belief Propagation (HBP) based method by setting up anl 1 -normed minimization problem with three-dimensional total variation regularization. TDCB is one extension of LASW, which introduce the bilateral filter technique-bilateral grid based on GPU.

Matching accuracy

The ground truths of stereo videos do not contain any noise, but real videos do.

Zero-central Gaussian noise simulated as the thermal imaging noise is added into all color channels of each frame in these 5 synthetic videos. Table 5.1, all these methods are implemented under Gaussian noise with parameter.

We can see that the JMSS method performs well at average error rate on the Book, Tanks, and Tunnel test sequences in comparison with the three methods. We can explain that because some explosive motion happened on those three sequences. In contrast, JMSS performs worse than HBP-TV on temple and street because there is less important motion vectors on these two sequences. A confirmation is thus made that the integration of motion vectors (temporal evidence) between adjacent frames brings improvement of accuracy. LASW [START_REF] Yoon | Adaptive support-weight approach for correspondence search[END_REF] and 4) SGBM method [START_REF] Hirschmuller | Stereo processing by semiglobal matching and mutual information[END_REF]. For the specified method, we can choose whether we use the GPU computing or not, also the way to show the disparity with color or gray.

The Stereo Vision GUI can also capture some real world examples of disparity The proposed method outperforms other method in both synthetic videos and real world videos.

Conclusion and Perspective

Conclusion

Due to both higher accuracy and higher user experience, the most recent image and video processing algorithms become more and more complex. In the meantime, variety of architectures leads to uncertain and unportable designs from a system view of implementation. A system-level view requires algorithm and architecture models. Building a high-level view of a heterogeneous embedded system brings new challenges compared with usual sequential software development chains. This thesis has introduced, analyzed, and studied motion estimation and stereo matching algorithms for heterogeneous systems with a rapid prototyping methodology.

With tools such as Orcc, Preesm, HMPP, our proposed rapid prototyping framework has two branches for many core CPU/GPU and embedded DSP respectively to replace the certain tedious manual development steps. In the two branches of our framework, we make use of the high level description with RCV-CAL to automatically generate the target code for specified architectures.

The background and some fundamental concepts related to rapid prototyping show that, our implementation has better performance than selected GPU-based FSME implementations. It also obtains a better balance between time efficiency and PSNR than the state-of-the-art fast ME algorithms. Additionally, experimental results show that we found the accurate method to distribute the workload in video applications based on heterogeneous computing system. The full search ME is firstly described as a block diagram with RVC-CAL. Then our prototyping framework generates automatically the OpenCL/CUDA code for our target. In the meantime, we proposed a stereo matching algorithm which adopts combined costs and costs aggregation with square size step to reach real-time performance on laptop's GPUs.

Experimental results show that our method outperforms other the state-of-the-art methods providing the best tradeoff between matching accuracy and time-efficiency.

Two high-level descriptions of our stereo matching method are introduced based on our rapid prototyping framework.

Based on our research of motion estimation and stereo matching, we have proposed the joint motion-based square step (JMSS) video stereo matching method.

Our method first builds the support region for selected central pixel with the help of motion vectors, then aggregates raw matching cost with adaptive motion weights.

It then iterates with square step size in support region along the horizontal and vertical pass. We applied adaptive weights to elaborate our approach for the stereo video matching. Our experimental results show that our method outperforms usual stereo video matching methods in video sequences with abundant movement even in noise context. In the end, one stereo matching GUI was proposed, to compare our method with LASW, SGBM and SSL methods. From the system level design view, our proposed image and video applications are rebuilt from the high level descrip-6.2. Perspective 109 tions to executable code on heterogeneous systems through the rapid prototyping framework. The design of an applications design the rapid prototyping framework is really faster and easier, reducing repetitive works on different platforms. All these results confirmed our contributions of several proposals.

Perspective

Based on our proposed motion estimation and video stereo matching method, future works focus on following aspects:

1. Based on the research work of chapter 3, we plan to integrate our parallelized motion estimation into video encoder like x.264 or HEVC, and to evaulate the time efficiency of video encoder with several video resolutions.

2. Another area of future work will concerns our research work of video stereo matching in chapter 4 and chapter 5. Based on the stereo cameras of smart phone and tablet, we plan to calculate the depth map in real-world scenes for developing some electronic consumer applications such as blind-aide, routeplanning, 3D reconstruction and so on.

3. Although improving the time efficiency of stereo matching applications is important, it is equally eventful to improve the matching accuracy. We plan to optimize our stereo matching method with several post processing methods like scanline optimization, interpolation for depth discontinuity, sub-pixel enhancement and so on. With a better matching accuracy, we can compute 3D reconstruction for 3D printers and visualization with obtained depth information. -L'appariement stéréo (cf. chapitre 4) : cet algorithme temps réel a été développé, puis étudié pour cibler les plateformes portables GPU d'entrée de gamme.

Structuration du mémoire

Architectures cibles

De nombreuses architectures telles que les CPU, GPU, FPGA et DSP posent des problèmes en termes de partitionnement de l'application, de transfert de données et de synchronisation des tâches. Ces problèmes deviennent de plus en plus complexes et entraînent une perte en temps de développement. La taxonomie de Flynn [START_REF] Flynn | Very high-speed computing systems[END_REF] est connue pour classer les architectures en quatre catégories, illustrées sur la figure Pour comparaison, un GPU dispose de centaines de coeurs relativement simples, cadencés à 1 GHz typiquement : la charge de travail globale doit alors être partitionnée, parallélisée et répartie en de nombreuses mais légères charges de travail, ce qui peut s'avérer efficace pour des applications à parallélisme élevé. Le fort parallélisme inhérent à une architecture GPU explique en fait la rapidité avec laquelle un tel composant peut effectuer des traitements sur de grandes quantités de données.

Plateforme MPPA de Kalray

La plateforme MPPA (Multi-Purpose Processor Array) de Kalray est multicoeurs (many-core), et optimisée pour les systèmes embarqués de haute performance et faible consommation d'énergie, soit une solution de traitement idéale pour les applications de faible et moyen volumes. Le composant de base de la famille intègre

Le modèle de programmation OpenCL

En fait, puisqu'un système hétérogène est constitué de divers composants tels que les CPU, GPU et SoC, il faut alors pouvoir partitionner l'application, générer de multiples codes cibles et distribuer une charge de travail appropriée par composant.

Le modèle de programmation flot de données

La complexité introduite par le large éventail des architectures matérielles rend difficile une mise en oeuvre optimale des applications. En outre, la stabilité d'une application doit être prouvé tôt dans le développement, afin d'assurer la fiabilité du produit final. Certains outils comme PeaCE [START_REF] Sung | Demonstration of codesign workflow in peace[END_REF] et SynDEx [START_REF] Grandpierre | From algorithm and architecture specifications to automatic generation of distributed real-time executives: a seamless flow of graphs transformations[END_REF] visent à apporter des solutions à ces problèmes par des mesures automatiques menant à un prototype fiable dans un court laps de temps. Une méthodologie de prototypage rapide suit une approche descendante : son objectif est, en partant d'une description de haut niveau d'une application, d'arriver à sa mise en oeuvre en temps réel sur l'architecture cible, aussi automatiquement que possible.

Définition de reconfigurable codage vidéo

Le standard RVC (Reconfigurable Video Coding [START_REF] Mattavelli | The reconfigurable video coding standard [standards in a nutshell[END_REF]), définit un ensemble de techniques de codage standard : les unités fonctionnelles (FUs -Functional Units).

Les FUs forment la base des standards vidéo actuels et futurs, elles sont normalisées dans la bibliothèque d'outils vidéo VTL (Video Tool Library). Une FU est alors décrite en RVC-CAL, langage portable indépendant de la plateforme (cf. section suivante). Le processus de décodage vidéo est décrit en RVC comme un schéma fonctionnel, aussi nommé réseau de configuration. Ce schéma est constitué de blocs, où les blocs sont des FUs. Pour cela, RVC définit le format FNL (FU Network Language), pour décrire les réseaux. FNL correspond au format XDF, format flot de données XML.

Modèles de calcul flot de données

Un modèle de calcul MoC (Model of Computing), flot de données, définit le comportement d'un programme en le décrivant par un graphe flot de données. Un graphe flot de données est un graphe orienté : les sommets représentent les acteurs, tandis que les arcs représentent les canaux unidirectionnels de communication de type FIFO (First In First Out), à capacité illimitée, connectés aux ports des acteurs.

Par exemple, les réseaux d'unités fonctionnelles décrits dans le standard RVC sont des graphes flot de données. Et un graphe flot de données respecte la sémantique d'un réseau DPN (Dataflow Process Network [START_REF] Lee | Dataflow process networks[END_REF]), lié à un réseau KPN (Kahn Process Network [START_REF] Kahn | The semantics of simple language for parallel programming[END_REF]), de la manière suivante : 1. Ces modèles contiennent des blocs : processus dans un KPN , acteurs dans un DPN. Ces blocs communiquent par le biais de FIFO unidirectionnelles à capacité illimitée. 2. L'écriture dans une FIFO est non bloquante. 3. Les programmes qui respectent l'un ou l'autre modèle, doivent être programmés dynamiquement en général [START_REF] Haid | Efficient execution of kahn process networks on multi-processor systems using protothreads and windowed fifos[END_REF].

Flot de données SigmaC

Pour exploiter le parallélisme latent de la plateforme MPPA, Kalray propose son propre modèle flot de données, le SigmaC. Dans ce modèle, un bloc est un agent, comprenant le code C de la fonction exécutée, le nombre de données entrantes et sortantes via l'interface avec le jeu de production/consommation. Ces informations sont définies dans une syntaxe SigmaC spécifique, illustrée par la figure 2.8 (cf. chapitre 2 du mémoire) ; la figure 2.9 montre la syntaxe d'un sous-graphe interconnectant deux agents.

RVC-CAL Langue

RVC-CAL est un langage SDL (Domain-Specific Language), normalisé par RVC : c'est une version restreinte de CAL [1], inventé par Eker et Janneck.RVC-CAL est un langage SDL (Domain-Specific Language), normalisé par RVC : c'est une version restreinte de CAL [1], inventé par Eker et Janneck.

La méthodologie de prototypage rapide

La méthodologie de prototypage rapide présentée par la figure A.2 suit une approche descendante et part d'une description haut-niveau en RVC-CAL d'une application, pour se terminer par l'implantation des codes appropriés sur le système hétérogène cible. Cette méthodologie s'appuie principalement sur trois outils : Orcc, Preesm et HMPP.

L'outil de compilation Orcc

Orcc (Open RVC-CAL Compiler [2]) comprend un éditeur textuel RVC-CAL, une infrastructure de compilation, un simulateur et un débogueur. Son atout principal est une infrastructure de compilation permettant de générer plusieurs langages ou combinaison de langages (dans le cas du co-design), à partir des acteurs et réseaux RVC-CAL. Orcc ne génère, ni du code assembleur, ni du code directement exécutable. Il génère en fait un code source qui doit être compilé par un outil adapté. À partir d'une description en RVC-CAL, Orcc peut générer du code pour toute plateforme : matérielle (VHDL), logicielle (C/C++, Java, LLVM,...), ou hétérogène mixte (matérielle et logicielle). .

Les algorithmes d'image et vidéo utiisés

cost[i] = M in(M in(cost[i], cost[i+stride]), M in(cost[i+2×stride], cost[i+3×stride])) (A.2)

Hétérogène Parallel Computing avec OpenCL

Description en CAL de l'estimation de mouvement

Figure 1 . 1 :

 11 Figure 1.1: Rapid Prototyping framework

4 .

 4 Backend for code generation As a consequence, Conception Orientée Modèle de calcul pour multi-Processeurs Adaptables (COMPA) project is proposed by Institut d'Electronique et de Télécommunications de Rennes (IETR), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Modaë Technologies, CAPS Entreprise, Laboratoire des Sciences et Techniques de l'Information-de la Communication et de la Connaissance (Lab-STICC), Texas Instrument France in 2011. The project addresses several issues related this challenge:

Figure 1 . 2 :

 12 Figure 1.2: Proposed prototyping methodology in COMPA project .

Figure 2 . 1 . 4

 214 The categories are listed as Chapter 2. Background follows: -Single Instruction, Single Data stream (SISD) -Single Instruction, Multiple Data stream (SIMD) -Multiple Instruction, Single Data stream (MISD) -Multiple Instruction, Multiple Data stream (MIMD) 13-8-25 Flynn's taxonomy -Wikipedia, the free encyclopedia en.wikipedia.org/wiki/Flynn%27s_taxonomy 2/Diagram comparing classifications Visually, these four architectures are shown below where each "PU" is a central processing unitof 2006, all the top 10 and most of the TOP500 supercomputers are based on a MIMD architecture. Some further divide the MIMD category into the two categories below, [3][4][5][6][7]and even further subdivisions are sometimes considered.[8] SPMD Main article: SPMD Single Program, Multiple Data: multiple autonomous processors simultaneously executing the same program (but at independent points, rather than in the lockstep that SIMD imposes) on different data. Also referred to as 'Single Process, multiple

Figure 2 . 1 :

 21 Figure 2.1: Flynn's taxonomy of classification of computer architecture, PU: Processing Unit

Figure 2 . 2 :

 22 Figure 2.2: CPU/GPU architecture comparison

Figure 2 . 3 :

 23 Figure 2.3: Structure of MPPA Platform

2. 2 . 25 -

 225 OpenCL: An Intermediate Level Programming Model Preserves the convenience of the CUDA kernel launch syntax by generating C source-code for kernel entry-point functions.

Figure 2 . 4 :

 24 Figure 2.4: GPU device architecture and OpenCL programming model

Figure 2 . 5 :

 25 Figure 2.5: Snapdragon 600 (APQ8064)'s Shared Memory between Host and the Device

Figure 2 .

 2 Figure 2.6 shows an example of the FNL network that represents sobel filter. The block "openImage" indicates the function of load_file, a FU that loads image file, "sobel" indicates the function of sobel_filter, a FU that executes the sobel filter algorithm and "dispImage" indicates the function of display, a FU that shows the final result in the screen. Edges carry data between a source port of the diagram or of an instance to a target port of the diagram or of another instance.

Figure 2 . 6 :

 26 Figure 2.6: Sobel Filter XML Dataflow Format

Figure 2 . 7 :

 27 Figure 2.7: Data-flow Models of Computation (MoC) taxonomy

X

  p . An empty FIFO ⊥ corresponds to the empty sequence. If a sequence X belong another sequence Y , for example X = [1, 2, 3, 4], Y = [1, 2, 3, 4, 5, 6], we can define that X ⊑ Y .

Figure 2 . 8 :Figure 2 . 9 :Figure 2 . 10 :

 2829210 Figure 2.8: SigmaC: syntax of one agent

Figure 2 . 12 :

 212 Figure 2.12: Declaration of a Function

. 13 :Figure 2 . 13 :

 13213 Figure 2.13: Declaration of a Action

Figure 2 .Figure 2 .

 22 Figure 2.14: A simple actor with an FSM

Figure 2 . 15 :

 215 Figure 2.15: Compilation procedure of Orcc

  reduce development time. The HMPP runtime ensures application deployment on multi-GPU systems. Software assets are kept independent from both hardware platforms and commercial software. While preserving portability and hardware interoperability, HMPP increases application performance and development productivity. These are two basic paired directives of HMPP: Codelet and Callsite. Codelet is used before the definition of C functions. Callsite is the HMPP directive for invocation on such an accelerator device. Using only simple paired directives, HMPP can replace the complex procedure of manually writing the CUDA/OpenCL kernel code. For the basic HMPP's transformation, we just need to insert two lines of directives into the source C code as shown in Algorithm 1:

FPGAFigure 2 . 16 : 1 ;

 2161 Figure 2.16: HMPP workflow in COMPA project

Figure 2 . 17 :

 217 Figure 2.17: Motion estimation illustration

Figure 2 . 18 :Figure 2 . 19 :Figure 2 . 19 .

 218219219 Figure 2.18: Overview of the view stereo matching process, where (a) the stereo vision is captured in a left and right image, (b) the disparities are searched through stereo matching.

Figure 2 .Figure 2 . 20 :Figure 2 . 21 :

 2220221 Figure 2.20: Stereo matching scanline

Chapter 3 .

 3 Parallelized Motion Estimation Based on Heterogeneous System algorithms in terms of speed up performance. Their algorithm relies upon robust and reliable predictive techniques and early termination criterion, which make use of parameters adapted to the local characteristics of a frame. Luo et al. [38] proposed a multistage motion estimation algorithm that includes a pre-stage to analyze the motion characteristics of video sequence. This stage predicts the motion vector field (MVF) from the previous coded frame, and clusters macroblocks into background and foreground regions based on the predicted MVF. The information from the prestage are passed on to the next stage, which includes a mathematical model for block distortion surface to estimate the distance from the current search point to the global optimal position.

2 ) 5 end 6 Figure 3 . 1 :

 25631 Figure 3.1: Padding image illustration

2 )

 2 256) which have a search region in the reference frame. We suppose the Search_Range = 32. So every MB has 32 × 32 = 1024 candidates which concern (48) × (48) = 2304 pixels in the reference frames as shown in Figure 3.2. In our design, we set the localsize = M B_size and there are 256 work-items executed in one work-group (work_group_size = 256). Because each work-item processes four candidates SAD, 1024 candidates SAD of one MB are distributed to one work-group perfectly. For every frame, the total number of work-groups is N : When an OpenCL program invokes a kernel, N work-groups are enumerated and distributed as thread blocks to the multiprocessors with available Compute Units of CPU or GPU. In kernel_compute, all pixels of MB are transferred into local memory (local[256]) by the 256 work-items in one work-group. Until all these workitems in the same work-group reach the synchronous point using barrier() function, all the 256 work-items continue transferring the 1024 candidates (2304 pixels of search region concerned) of reference image into local memory (local_ref [2304]).

57 DataFigure 3 . 3 :

 5733 Figure 3.3: SADs comparison in parallel reduction

Figure 3 . 4 :

 34 Figure 3.4: Performance comparison between global and local memory in Matrix and Vector Multiplication application

Figure 3 . 5 :Figure 3 . 6 :

 3536 Figure 3.5: Performance comparison with heterogeneous parallel computing

Figure 3 . 7 :

 37 Figure 3.7: Proposed method performance under different resolutions

Figure 3 . 8 :

 38 Figure 3.8: Time comparison of specified state-of-the-art fast ME algorithms

2 .Figure 3 . 10 :1

 2310 Figure 3.10: Combined context for our heterogeneous computing system

  frames to CPU device and (N -M) frames to GPU device to execute our proposed ME algorithm (kernel_compute and kernel_compare). The suitable number of M 3.4. Heterogeneous Parallel Computing with OpenCL 65 does guarantee the best performance. As discussed in Section 3.2, the time of transferring the needed frames is T memtrans ; The time of kernel computing is T kernel ; the time of copying buffer for kernel executed is T memcopy . The total nonlinear cost time is T device = T memtrans + T kernel + T memcopy . (3.6) T cpu (M ) is the time of CPU processes M frames, and T gpu (N -M ) is the time of GPU processes (N -M) frames. Under the perfect situation, the CPU and GPU will finish their work separately at the same time. When T cpu (M ) = T gpu (N -M ),

Figure 3 . 12 .

 312 Figure 3.12. So we can get the equations of T cpu (M ) and T gpu (N -M ) from our experimental results with the technology of curve fitting [65-67] as shown in equation (3.7) and (3.8).

Figure 3 . 13 :

 313 Figure 3.11: Experimental curves of CPU

3. 5 . 67 3. 5 . 1 CAL

 56751 Figure 3.14.

Figure 3 . 14 :Figure 3 . 15 :

 314315 Figure 3.14: Motion Estimation of SDF diagram

Figure 3 .Figure 3 . 16 :

 3316 Figure 3.16: OpenCL kernel time efficiency analysis

Figure 3 . 17 :

 317 Figure 3.17: Performance difference analysis

  two categories: global methods and local methods. Global methods rely on global energy minimization function along a single scanline or on the entire disparity map. These methods like Belief Propagation [45] [58] [68] [69], or Graph-Cuts [70] [71], or dynamic programming [72] [73] [74], provide good quality but involve a huge computation. Consequently few global methods are suitable in real-time applications (more than 15 frames per second (f ps)). Comparing with global methods, local methods provide faster processing speed, but less accurate disparity maps. They are area-based algorithms which compute the disparity for each pixel with the help of the neighboring pixels. Because of this constraint of area, local algorithms can fail probably in occluded regions and less textured regions. To continue our discussion in section 2.5.2, the area-based stereo matching algorithm is divided into four stages: 1. Cost construction 2. Cost aggregation 3. Disparity determination Chapter 4. Real Time Local Stereo Matching Method 4. Disparity refinement The popular costs calculations methods for pixel p(x, y) in the left image I l and the right image I r are listed as followed. The disparity is defined as d, and the n × m aggregation region is built in the below equation 4.1.

  l (x + i, y + j) -Īl -(I r (x + d + i, y + j) -Īr | (4.6) where Ī = 1 nm i=n j=m (I(x + i, y + j)). Different stereo matching cost Stereo matching technique has many kind of matching criterions, named raw matching costs as shown in equations (4.2, 4.3, 4.4, 4.5, 4.6). Different with above cost computations, there is another strategy to employ a local transform of paired images. Some transforms are the Census and the Rank transforms proposed in [75] [76] [43] [77] [78] [79] [80] [81] [82]. All these transforms are based on intensity relations of between the actual pixel and neighbors pixels in one certain window. The more details information about Census transform will introduced in section 4.2. And the time-consumed of Census based matching mainly depends on Census window size. Due to the similarities between neighboring pixels as well as the intensity-value differences between corresponding pixels, classical matching measures based on intensity similarity produce slightly imprecise results. Hermann et al. [83] provided experimental evidence to show that the gradient as a data descriptor outperforms other pixel-based functions such as absolute differences and the Birchfield and Tomasi (BT) cost functions. Furthermore, analysing the effect of the cost functions when exposure and illumination settings are different between the left and right camera is analysed. Our experimental results in section 4.3 also illustrates the matching results under different condition of illumination. Mei et al. [76] combines the Census cost with the Absolute Difference (AD) cost in RGB channels, and consequently it is in the top 5 of Middlebury benchmarks [42] with complex costs aggregation and post processing of disparity. Our method initializes the Truncated Absolute Difference (TAD) and the Census cost only on gray channel transformed from the RGB channels. It avoids repeatable computation in cost construction. Our method also employ the sparse cost aggregation to improve the time efficiency with sacrifice in matching accuracy as shown in section 4.3. Zhou et al. [80] and Pinggera et al. [84] also proposed a relative gradient stereo matching algorithm. Boundary and low texture problems are resolved by using a Gaussian weighting function and by limiting the search range. Experimental results

Figure 4 . 1 :

 41 Figure 4.1: Proposed stereo matching system

Figure 4 .

 4 1(a), mainly contains the first two stages: In the first stage, the cost volume is constructed by combining the TAD cost with the Census cost; In the second stage, the matching cost is aggregated by applying a weighted and iterative method in both directions to produce the final disparities. The second part of Figure4.1(b) also illustrates our method used to implement our stereo matching algorithm on a GPU platform. This is our second main aim in this chapter.

Figure 4 .

 4 1(a), Figure 4.2 elaborates proposed stereo matching method which consists of color-space transforming, cost construction, cost aggregation, disparity selection and involved parameters like iteration times, maximumminimum disparity and so on. In the beginning, the left and right RGB images are transformed into gray images due to simplify the computation. Gray = 0.299 * R + 0.587 * G + 0.144 * B; (4.7) Our cost construction combines the Truncated Absolute Difference (TAD) cost

Figure 4 .Figure 4 . 2 :

 442 Figure 4.1(c). The TAD cost C T AD (pl, d) computes the intensity absolute difference between the left image and the d-shifted right image, truncated by the σ threshold:

Figure 4 .

 4 4 illustrates census transforming of teddy paired images.

Figure 4 . 3 :

 43 Figure 4.3: Census transforming example

Figure 4 . 4 :

 44 Figure 4.4: Census transforming of Teddy images

.

  ....................................... ........................................

Figure 4 . 5 :

 45 Figure 4.5: 1D Cost aggregation example

Figure 4 .

 4 Figure 4.5 illustrates our aggregation in the horizontal direction (the same process is repeated in the vertical direction).Figure 4.5(a) shows the conventional method

Figure 4 .

 4 5(a) shows the conventional method that performs the processing on 27 pixels[START_REF] Gong | A performance study on different cost aggregation approaches used in real-time stereo matching[END_REF] for the influence range[-13, 13].

Figure 4 .

 4 Figure 4.5(b) describes our iterative method to achieve the same influence range: at least three iterations are needed with the respective values of s equal to 1, then 4, and 9. Consequently the range varies from [-1, 1], then [-6, 6], up to [-13, 13].

Figure 4 . 7 :

 47 Figure 4.7: Proposed stereo matching of SDF diagram

Figure 4 . 8 .

 48 Figure 4.8. The main difference between Figure 4.8 and Figure 4.7 is the part of cost aggregation. As we previously described, we assume that the disparity range is from D min to D max (D ∈ [D min , D max ]). We already know that the cost aggregation is the most time consumed part in the stereo matching algorithm, above 90% of total computation. And all these computation of cost aggregation is based on each level of disparity assumption. So we can optimize cost aggregation by averaging all computation of aggregation into the channels with fixed number (the number is 5 in Figure 4.8) to obtain the better performance. For instance, the disparity range is 60 (D ∈ [0, 59]). Every channel is in charge of 12 level

Figure 4 . 8 :

 48 Figure 4.8: Proposed multi-pass stereo matching method XDF graph

Figure 4 . 9 : 4 . 3 . 1 Figure 4 . 9

 4943149 Figure 4.9: Disparity results comparison,(a) Teddy image reference, (b) ESAW method [103], (c) RTcensus method [43], (d) our method

Figure 4 . 10 .

 410 Figure 4.10. The experiment results indicate that our method outperforms the

Figure 4 . 10 :

 410 Figure 4.10: Matching results under differen condition of illumination, the left image hold the same illumination and the right image has three conditions of illumination as shown in (a,b,c)

Figure 4 .

 4 [START_REF] Flynn | Very high-speed computing systems[END_REF] describes the 3D reconstruction model with our calculated disparity which could reflect the accuracy of matching results.ConesTeddy Venus tsukuba

Figure 4 .Figure 4 . 12 :

 4412 Figure 4.11: 3D reconstruction with depth information

Figure 4 . 13 :

 413 Figure 4.13: Results of Middlebury datasets: Tsukuba, Venus, Teddy and Cones. (a) datasets, (b) disparity of our method, (c) bad pixel (absolute disparity error >1.0) maps where mismatches in non-occluded areas are labeled with black, in occluded areas with gray color.

Chapter 4 .

 4 Real Time Local Stereo Matching Method for function CostConstruction and CostAggregation, one agents assigned for function DispSelect as shown in Figure 4.14. The time consuming of Tsukuba test images is 160 ms which is about 3 times more than the GPU-based implementation. The matching accuracy has little difference between the MPPA-based and GPU-based implementation.

  r l'ensemble du traitement : de ComputeGrayImage à MedianFilter. Pour réaliser ceci, nous iser l'image en 16 selon la hauteur et de traiter ainsi chaque seizième d'image dans chaque c cription graphique réaliser cette version, les optimisations explicitées dans la partie précédente ont été réempl la découpe de chaque bloc pour utiliser le maximum de coeur a dû être revue. Par ex .ECKHA 3.1: Graphe de la version 16 slices

13

 13

Figure 4 . 14 :

 414 Figure 4.14: SigmaC dataflow of proposed stereo matching method

Figure 5 . 1 :

 51 Figure 5.1: Motion amplitudes of stereo video test sequence: book

Figure 5 . 1 ,

 51 Figure 5.1, the resulting motion vectors of each block (blocksize = 8 × 8 ) are drawn with gray-scale values for x and y axis respectively.

Figure 5 . 2 :

 52 Figure 5.2: Support region of selected pixel p

Figure 5 . 3 :

 53 Figure 5.3: Enlarged motion amplitudes of moving page (left up corner) from Figure 5.1(sequence: book)

Figure 5 . 4 :

 54 Figure 5.4: Optimized sparse census transforming example

  2.1. The cost TAD C T AD (pl, d) is calculated using equation (4.8). Different with the usual census transforming described in section 4.2.1, we proposed our sparse census transforming as shown in Figure 5.4. A 7×7 census windows is used to represent the neighbor structure. But we adopt sparse sampling of 12 pixels instead of total 49 pixels to reach the same influence region as normal census transforming. The census cost C census (pl, d) is defined as the Hamming distance (bitwise XOR operations) of the two bit strings about pixels pl and pr along scanline in left and right image respectively.

Figure 5 . 5 :

 55 Figure 5.5: Census transformed image (books)

depicted in chapter 3 Figure 5 . 6 :

 356 Figure 5.6: Multi-contexts for our heterogeneous computing system

Figure 5 .

 5 Figure 5.7 shows some frames from the 5 synthetic stereo videos, ground truths and the disparity maps obtained by our method. Our experimental environment is CPU: I7 2630qm and GPU: NVIDIA GT 540m.

Figure 5 . 7 :

 57 Figure 5.7: Results of stereo video datasets: Book, Tank, Tunnel, Temple and Street [108]. (a) left frame of stereo video, (b) ground truth, (c) disparity result from our method

Figure 5 .Figure 5 . 8 :

 558 Figure 5.8: The book sequence stereo matching result, A with additive Gaussian noise(σ = 20), B with additive Gaussian noise(σ = 60), C with additive Gaussian noise(σ = 100)

Figure 5 . 9 :

 59 Figure 5.9: Error versus curves for increasing Gaussian noise. and (c) stereo matching as shown in Figure 5.11. In the display area, there are three windows to show the left view, right view and disparity respectively. In the camera calibration area, there are some basic configuration for camera calibration which are over the scope of this thesis. In the stereo matching area, we can choose the four stereo matching algorithms: 1) Jonit Motion Square Step method (JMSS) proposed in this chapter, 2) Square Step Local method (SSL) proposed in the chapter 4, 3)

Figure 5 . 10 :Figure 5 . 11 :Figure 5 . 13 :

 510511513 Figure 5.10: Our stereo matching GUI interface

108 Chapter 6 .

 1086 framework and our proposals have been firstly introduced. It also gives the reader the necessary knowledge on the theoretical and practical aspects of parallel embedded computing, rapid prototyping methodology and image and video processing algorithms. We have presented the parallel embedded computing environment which contains parallel embedded systems, parallel programming and rapid prototyping framework. Based on different target architectures, we introduced the basic concept Conclusion and Perspective of motion estimation and stereo matching algorithms which are two applications widely used in the industry and research work. The parallelized motion estimation targets heterogeneous computing systems which contain CPU and GPU. Our method has the better speed-up ratio comparing with other GPU-based implementations of ME due to our optimizations like shared memory and vectorization. A new way to rebuild the full search ME with GPU can be applied easily in next video encoder like HEVC. The experimental results

4 .Figure A. 1 -

 41 Figure A.1 -Environnement générique de prototypage rapide.

Figure A. 2 -

 2 Figure A.2 -Proposé méthodologie de prototypage dans le projet COMPA .

A. 3 . 4

 34 Ces catégories sont répertoriées suivant les flots d'instruction et de données, comme suit : -SISD pour Single Instruction Single Data : un flot d'instruction pour un flot de données ; -SIMD pour Single Instruction Multiple Data : un flot d'instructions pour des flots multiples de données ; -MISD pour Multiple Instruction Single Data : des flots multiples d'instructions pour un flot de données ; -MIMD pour Multiple Instruction Multiple Data : des flots multiples d'instructions pour des flots multiples de données. Les architectures parallèles modernes sont principalement de deux types : les architectures SIMD telles que les GPU et les FPGA, et les architectures MIMD tels que les SoC (System on Chip). Les architectures MIMD sont en outre, soit à mémoire partagée, soit à mémoire distribuée. Cela se répercute sur le réseau d'interconnexions des processeurs : typiquement basé bus ou hiérarchique pour une structure à mémoire partagée, classiquement hypercube ou maillé pour une structure à mémoire distribuée.13-8-25 Flynn's taxonomy -Wikipedia, the free encyclopedia en.wikipedia.org/wiki/Flynn%27s_taxonomy 2/Diagram comparing classifications Visually, these four architectures are shown below where each "PU" is a central processing unitof 2006, all the top 10 and most of the TOP500 supercomputers are based on a MIMD architecture. Some further divide the MIMD category into the two categories below, [3][4][5][6][7]and even further subdivisions are sometimes considered.[8] SPMD Main article: SPMD Single Program, Multiple Data: multiple autonomous processors simultaneously executing the same program (but at independent points, rather than in the lockstep that SIMD imposes) on different data. Also referred to as 'Single Process, multiple

Figure A. 3 -

 3 Figure A.3 -Taxonomie de Flynn des architectures.(PU -Processing Unit)

2. 1 . 1

 11 CPU versus GPU Illustré par la figure A.4, un CPU est classiquement quadri-coeurs ou octo-coeurs, chaque coeur étant programmable, à jeu d'instructions multimédia (SSE par exemple), rapide, cadencé à 2 ou 3 GHz, et à multi-fils d'exécution (threads) : chaque thread peut ou doit supporter alors une forte charge de travail.

Figure A. 4 -

 4 Figure A.4 -Comparaison CPU / GPU.

Figure A. 5 -

 5 Figure A.5 -Structure de la plateforme MPPA.

A

  cet effet, NVidia propose CUDA, une plateforme et un modèle de programmation pour calcul parallèle, implantable sur les GPU du fabricant. CUDA permet au développeur d'accéder au jeu d'instructions virtuel et à la mémoire des éléments de calcul qui composent un GPU NVidia. Pour comparaison, OpenCL (Open Computing Language) est un standard de langage de programmation parallèle pour les accélérateurs matériels hétérogènes. OpenCL permet en fait au programmeur de décrire l'application sous la forme de noyau(x) (kernel). Le compilateur parallélise alors, à tous les niveaux possibles, l'exécution des instances du noyau. Comparé au classique langage C séquentiel, OpenCL permet une meilleure utilisation du parallélisme latent de l'architecture

2. 4 . 2 L

 42 'outil de prototypage PREESM Preesm (Parallel and Real-time Embedded Executives Scheduling Method [3]) est un outil de prototypage rapide pour implémentations parallèles. Illustrées par la figure A.1, les entrées de l'outil sont les graphes d'architecture et d'algorithme, ainsi qu'un scénario qui regroupe l'ensemble des informations liant l'algorithme et l'architecture. Les plateformes cibles sont les architectures hétérogènes embarquées, avec possibilité de plusieurs processeurs et de nombreux coeurs. La version actuelle de l'outil s'appuie sur un ordonnancement et un mapping statiques des algorithmes. Les algorithmes sont décrits via un modèle de calcul SDF (Synchronous Dataflow Graph), hiérarchique. Preesm n'est pas adapté pour les applications adaptables (modèle de calcul DPN d'Orcc), pour lesquelles l'ordonnancement et le mapping devraient se faire partiellement ou totalement à l'exécution...

123 2 . 4 . 3 L

 243 'outil de compilation HMPP Développé par CAPS, HMPP (Hybrid Multicore Parallel Programming [4]) est un compilateur basé directives, supportant le standard OpenACC [4]. Il permet le développement d'applications parallèles sur GPU, assurant même le déploiement d'applications parallèles sur des systèmes multi-GPU. HMPP offre un niveau d'abstraction élevé pour une programmation hybride qui tire profit de la puissance de calcul des processeurs avec un modèle de programmation simple. Ce compilateur intègre des back-ends de données parallèles pour CUDA et OpenCL, réduisant ainsi efficacement le temps de développement. Tout en conservant la portabilité et l'interopérabilité du matériel, cet outil permet d'accroitre les performances des applications et la productivité de développement. HMPP utilise deux directives appariées : Codelet et Callsite. emph Codelet est utilisée en amont des définitions des fonctions C ; Callsite est la directive pour instancier un accélérateur matériel. Par le biais de ces deux directives, HMPP peut remplacer la procédure complexe d'écrire manuellement le code du noyau CUDA ou OpenCL. Pour la transformation, il suffit d'insérer simplement deux lignes dans le code source C (cf. Algorithm 1 chapitre 2).

  Certaines applications parallèles sont proposées dans cette thèse d'évaluer le cadre de prototypage rapide qui peut pleinement utilise du parallélisme des architectures cibles. Ils sont beaucoup plus appropriés pour évaluer l'efficacité du cadre de prototypage rapide.Deux algorithmes de traitement d'image et vidéo sont principalement utilisés dans ce travail de thèse : le premier est l'estimation de mouvement (ME -Motion Estimation), le second est l'appariement stéréo (SM -Stereo Matching).-L'estimation de mouvement : l'algorithme ME détermine les vecteurs de mouvement qui décrivent la transformation d'une image 2D en une autre, généralement à partir des trames adjacentes de la séquence vidéo. Dans un encodeur, l'estimation de mouvement est la tâche la plus gourmande en temps de calcul (plus de la moitié de la charge globale). Pour réduire la redondance temporelle, l'algorithme ME pourrait déterminer les mouvements relatifs entre deux images, comme indiqué sur la figure A.7.

Figure A. 7 -

 7 Figure A.7 -Illustration de l'estimation de mouvement

Figure A. 8 - 3 :

 83 Figure A.8 -Aperçu du processus l'appariement stéréo

3. 1 Figure A. 9 - 3 . 2 Figure A. 10 -

 193210 Figure A.9 -Proposé calcul de SAD dans la mémoire locale

Chapitre 4 :Figure A. 13 - 4 . 1 1 Census cost = 2 Figure A. 14 -Figure A. 15 -

 41341121415 Figure A.13 -Proposé système d'appariement stéréo

Figure A. 17 -Chapitre 5 : 5 . 1 Figure A. 18 -Figure A. 19 - 1 , 5 . 2 5 . 4

 17551181915254 Figure A.17 -Flux de données de la méthode d'appariement stéréo parallèle proposé

  program-

						Chapter 1. Introduction
			RVC-CAL	DPN	High level programming model
		Orcc	Classify	Convert	Generate
	User	C with directives	PSDF		C	Intermediate level programming model
		HMPP	Compiler	Preesm		Archi Model
		OpenMP	OpenCL CUDA	Embedded Runtime	Embedded C
						Code executable on hardware

Table 2 .

 2 -item and work-group respectively as described in Table2.1. Workitem is the basic unit of OpenCL kernel execution, and all the work-items grouped in one work-group execute the same instruction at the same time. The barrier() function is required to ensure completion of reads and writes to local memory. All work-items in a work-group executing the kernel must execute barrier() function before any are allowed to continue execution beyond the barrier. This function must be encountered by all work-items in a work-group executing the kernel. Local and global memories in OpenCL context correspond to the shared and device memories in specified device respectively. As shown in Figure 2.4, each workgroup executes on one Compute Unit (CU), each work-item executes on one Processing Element (PE). Private memory is assigned to one work-item. Local memory is

	1: Relationship between GPU device and OpenCL Devices OpenCL
	thread	work-item
	threads group	work-group
	shared memory local memory
	device memory global memory
	equal to work

work-

group OpenCL programming model work-group Context GPU Architecture work-group work-group work-group work-group work-group work-group work-group

	Compute Device
	Compute Units 1	Compute Units M
	Private Memory 1	Private Memory N	Private Memory 1	Private Memory N
	PE 1	PE N	PE 1	PE N
	Local Memory 1		Local Memory N
		Global /Constant Memory Data Cache
		Global Memory
		Constant Memory
	Compute Device Memory
				float a[4096], b[4096], c[4096]; for (i=0; i<4096

.11 shows the three different ways of declaring a state variable. The uint(size=16) Number

	2.3. The Dataflow Approach: An High Level Programming Model	37
	to initialize a constant and the := used to initialize a variable. The initial value of
	a variable is an expression.
	Function
	As shown in Figure 2.12, a function may declare parameters such as n of bit_-
	number and local variables, like eof. The body of a function is an expression whose
	type must match the specified type of the function.
	function bit_number(int n ) --> bool
	var
	bool eof = get_eof_flag();
	= 0x1fff;
	// the bits of the byte read
	uint(size=16) bits;
	// number of bits remaining in value
	uint(size=4) num_bits := 32;
	Figure 2.11: Declaration of State Variable
	first variable Number is a 16-bit unsigned integer constant. The bits variable is a
	16-bit unsigned integer variable without an initial value. The num_bits variable is
	a 4-bit unsigned integer that is initialized to 32. The difference between the = used

if eof then false else num_bits >= n end end

.15. front-end middle-end back-end

			XDF networks
	RVC-CAL actors	IR actors	IR actors XDF networks
		source code

Table 2 .

 2

2: Overview of Motion Estimation

implementations References Algorithms Resolution and search region fps Platform

mehta et al.

Table 2 .

 2

3: Overview of stereo vision system

References Algorithms

Mde/s fps Platform Yang et al.

[START_REF] Yang | A constant-space belief propagation algorithm for stereo matching[END_REF]

constant space belief propagation 14.4 20 CPU Xiang et al.

[START_REF] Xiang | Real-time stereo matching based on fast belief propagation[END_REF]

hierarchical belief propagation 28.8 16.3 CPU Hosni et al.

[START_REF] Hosni | Real-time local stereo matching using guided image filtering[END_REF]

guided filter 199.6 25 GPU Zhang et al.

[START_REF] Zhang | Realtime accurate stereo with bitwise fast voting on cuda[END_REF]

Bitwise fast voting 100.9 57 GPU Yang et al.

[

48] SAD 283.2 11.5 GPU Miyajima et al. [49] SAD 491.5 20 FPGA Chang et al. [50] SAD 88.4 50 DSP There are two main groups of stereo matching algorithms: feature-based and area-based algorithms [43]. The first category aims to employ suitable features, such as corners or edges of the images and match them afterward. The second category tries to match each pixel independently. Feature-based methods create sparse disparity map because they only obtain disparities for these extracted features. Area-based methods calculate the disparities for each pixel of image, resulting in a dense disparity map. This section introduces an overview of the basic stereo matching technique that contains raw matching cost, stereo vision applications and so on. The stereo techniques discussed in this thesis are restricted to area-based method. There is also a brief overview of available stereo vision systems shown in the Table 2.3. Mde/s is more meaningfully in million disparity evaluations per second (M de/s = width × height × disps × f ps). 2.6. Conclusion

  until the final MV is found. In these fast ME algorithms, the number of evaluated candidates is decreased, but the reduction comes with a loss in terms of quality which means lower Peak Signal to Noise Ratio (PSNR) of the compressed video. In the other hand, many researchers proposed their solutions to accelerate the ME with hardware accelerators like GPU, FPGA and DSP. the host CPU and the GPU. Lee et al.[START_REF] Chuan-Yiu | Multi-Pass and Frame Parallel Algorithms of Motion Estimation in H.264/AVC for Generic GPU[END_REF] proposed one multipass and frame parallel algorithms to accelerate various motion estimation methods with the GPU. By the multi-pass method to unroll and rearrange the multiple nested loops, the ME can be implemented with two-pass process on GPU. Moreover, fractional ME needs six passes for frame interpolation with six-tap filter and motion vector refinement. Motion estimation with multiple reference frames can be implemented with two-pass process with framelevel parallel scheme by use of SIMD vector operations of GPU. In this context, the parallel structure of the full search ME is easy to accelerate the computation without decreasing the PSNR. We propose our parallelized motion estimation method which divides the whole workload of full search ME into two kernels respectively.

	Hardware-based FSME
	Motion estimation becomes a very time consuming task even for today's CPU.
	plement the motion estimation for H.264 using programmable GPU. To overcome
	the dependency problem, they introduce a new implementation which performs ME
	on block-by-block basis. And their implementation is 10 times faster than SIMD

proposed a novel and simple fast block-matching algorithm, called adaptive rood pattern search (ARPS), which consists of two sequential search stages: initial search and refined local search. For each macroblock (MB), the initial search is performed only once at the beginning in order to find a good starting point for the follow-up refined local search. For the initial search stage, an adaptive rood pattern (ARP) is proposed, and the ARP's size is dynamically determined for each MB, based on the available motion vectors (MVs) of the neighboring MBs. In the refined local search stage, a unit-size rood pattern (URP) is exploited repeatedly, and unrestrictedly, On the other hand, modern graphics hardware includes a powerful GPU whose computing power remains idle most of the time. Urban et al.

[START_REF] Urban | HDS, a real-time multi-DSP motion estimator for MPEG-4 H.264 AVC high definition video encoding[END_REF]

proposed one real-time ME for H.264 high definition video encoding on multi-core DSP, which is well-suited for embedded parallel systems. Li et al.

[START_REF] Brianm | Serial and parallel fpga-based variable block size motion estimation processors[END_REF]

proposed a novel most significant bit (MSB) first bit-serial architecture for full-search block matching ME based on FPGA platform. Since the nature of MSB-first processing enables early termination of the sum of absolute difference (SAD) calculation, the average hardware performance can be enhanced.

Some first results about GPU-based ME have been proposed in

[START_REF] Wei-Nien | 264/AVC motion estimation implmentation on Compute Unified Device Architecture (CUDA)[END_REF][START_REF] Chuan-Yiu | Multi-Pass and Frame Parallel Algorithms of Motion Estimation in H.264/AVC for Generic GPU[END_REF][START_REF] Cheng | Speeding up motion estimation algorithms on cuda technology[END_REF][START_REF] Lin | Multi-pass algorithm of motion estimation in video encoding for generic gpu[END_REF][START_REF] Schwalb | Fast motion estimation on graphics hardware for h.264 video encoding[END_REF][START_REF] Ho | Motion estimation for h.264/avc using programmable graphics hardware[END_REF]

with CUDA approach. Chen et al.

[START_REF] Wei-Nien | 264/AVC motion estimation implmentation on Compute Unified Device Architecture (CUDA)[END_REF]

, Lee et al.

[START_REF] Chuan-Yiu | Multi-Pass and Frame Parallel Algorithms of Motion Estimation in H.264/AVC for Generic GPU[END_REF]

and Lin et al.

[START_REF] Lin | Multi-pass algorithm of motion estimation in video encoding for generic gpu[END_REF]

proposed multi-pass GPU-based ME algorithms. They store each matching blocks into shared memory, and they ignore pixels of search range in reference frame. Cheng et al.

[START_REF] Cheng | Speeding up motion estimation algorithms on cuda technology[END_REF]

implemented the full search algorithm, the diamond search algorithm, and the four step algorithms in both the CPU and the CUDA platforms. All the computation about SAD is executed in the global memory. Experiment results show that the CUDA-based implementations of these ME algorithms can be more than 8 times faster than the CPU-based ME implementations. Schwalb et al. and Ho et al. imoptimized CPU implementation. Ko et al. [56] proposed a novel motion estimation algorithm for GPU implementation which is accompanied by a novel pipelining technique, called subframe ME processing, to effectively hide the communication overhead between

Table 2

 2 .2: Overview of ME implementations. The proposed Full search ME approach is divided into two OpenCL kernels. One is SADs computation; the other is SADs comparison for the best SAD candidate (final MV). We define the two

	). The candidate of block_ref will be chosen when it possesses the
	minimum SAD value. The position (x,y) of the best candidate of block_ref relative
	to block_current is the motion vector.

Because the execution time for

Full Search ME method is proportional with the size of search region and blocks, most previous research work employ the [-16,16) (32 × 32 pixels) search region considering a 16 × 16 pixels block as shown 3.2. Parallelized Motion Estimation Algorithm 55 in

Table 3 .

 3 1: Summary of different NVIDIA GPUs in our comparison

	Devices	GeForce GT540m	GeForce 7800GT	GeForce 8800GTX
	Architecture	Fermi	G71	G80
	Compute Unit (CU)	2	6	16
	Processing Element (PE)	96	48	128
	Core Speed/Mhz	672	440	575
	Memory Speed/Mhz	900	900	900
	Memory Bus Width/bits	128	256	384
	each CU has 48 Process Elements (PEs), resulting in a total of 96 processor cores
	(PE). NVIDIA 8800GTX has 16 Compute Units (CUs), and each CU has 8 Process
	Elements (PEs), resulting in a total of 128 processor cores. We evaluate the perfor-
	mance of our proposed ME algorithm with manual OpenCL kernels on such hardware
	HASEE environment: Intel I7 2630qm (2.8GHz), NVIDIA GT540m. We compare
	Time Efficiency
	First, we execute the sequential C implementation of full search ME with single
	CPU core. Then, we run the proposed ME algorithm on the OpenCL CPU platform
	and two different GPUs platforms. We chose three test sequences with different
	resolutions, Foreman (CIF, 352×288), City (4CIF, 704×576), Mobal_ter (720p,
	1280×720) and the same 32x32 search range. As shown in Figure 3.5 from CIF
	to 720P, our proposed method with OpenCL CPU achieves (107,19,7.6) fps, with
	OpenCL GT540m achieves (355,88,38) fps compared with C code that only produces
	(7.5,1.7,0.6) fps. It means that our proposed method achieves 45x to 65x speed-up
	for different resolutions comparing with implementation with single CPU core. The
	CPU I7 2630qm with 4 physical cores and 8 threads achieves more than 10 times

the performance of GPU-based FSME implementation and selected state-of-the-art fast ME algorithms. To the best of our knowledge, there are several criterions of evaluation for final motion vectors of our implementations: time efficiency, matching accuracy. So our experimental results mainly focus on two aspects: time consumed and PSNR. speed-up due to the utilization of vectorization and the unroll procedure.

We also describe the time consuming of selected GPU-based full search ME methods as shown in Table

4

.2. Our method significantly outperforms other GPU-

Table 3 .

 3 2: Integrated Analysis for selected methods of GPU-based ME, unit:fps

	Method	Foreman (CIF)	City (4CIF)	Mobcal_ter (720P)	Device	Rank
	Chen's [32]	31.54	9.19		4.10		NVIDIA Geforce 8800 GTX	3
	Cheng's [57]	91.10	24.7		10.6		NVIDIA Geforce 8800 GTX	2
	Lee's [39]	13.48	3.50		1.17		NVIDIA Geforce 7800 GT	4
	Our method	355	88		38		NVIDIA GT540M	1
		1800.00
		1600.00
		1400.00
		1200.00
		1000.00
		800.00
		600.00
		400.00
		200.00
		0.00
			FS C	FS	FS	4SS	CDHS ARPS
				OCL	OCL
					opt

CIF1 (Forman) 133.33 27.34 4.65 29.45 20.59 16.45 4CIF(CITY) 588.23 87.19 19.47 114.70 108.50 61.70 720P(TER) 1667.66 350.66 45.87 193.80 89.20 112.28

  Most accurate stereo algorithm employ segmented regions for outlier refinement [100, 101]. Region voting is used to select the most frequently emerged disparity in the support region. For one outlier pixel p, the voting firstly build a histogram H(p) over all the disparities from 0 to D max in a region U (p); then adopting cross voting approach to select the disparity with the highest bin value (defined as D maxp ) in disparity histogram H(p), as shown in Equation 4.15 and Figure 4.6.

	8 8 9 9 9	9	6
		8 8 7 8	8
		7 7 7 7	8
	9 8 8 8	7 7 7 7 7 7 8 8 7 7 7 7	7 7 8 7 8 8		2	1
		8 8 9 9	9	d=7	d=8 d=9
					Horizontal Voting
	11
					8 8 9 9 9	9
						8 8 7 8	8
						7 7 7 7	8
		3	3		9 8 8	7 7 7 7 7 7 8 7	7 7 8 7 8
					8	8 7 7 7	8
	d=7	d=8 d=9		8 8 9 9	9
	Vertical Voting

D maxp = argmaxH(d), d ∈ [0, D max -1] (4.

15) 7 Figure 4.6: 2 × 1D horizontal and vertical voting

Table 4 .

 4 1: Quantitative Evaluation Results of the Middlebury Stereo Database[START_REF]Middlebury stereo vision[END_REF]

	algorithm	nonocc	Tsukuba all	disc	nonocc	Venus all	disc	nonocc	Teddy all	disc	nonocc	Cones all	disc	average
	AdaptingBP	1.11	1.37	5.79	0.10	0.21	1.44	4.22	7.06	11.8	2.48	7.92	7.32	4.23
	PMBP	1.96	2.21	9.22	0.30	0.49	3.57	2.88	8.57	8.99	2.22	6.64	6.48	4.46
	Our method	1.03	2.01	5.06	0.21	0.46	1.95	6.67	12.0	13.8	3.51	10.4	9.9	5.58
	ESAW [103]	1.92	2.45	9.66	1.03	1.65	6.89	8.48	14.2	18.7	6.56	12.7	14.4	8.21
	RTCensus [43]	5.08	6.25	19.2	1.58	2.42	14.2	7.96	13.8	20.3	4.10	9.45	12.2	9.73
		Left				intensity-based method		our method
		Right 1								(a)
		Right 2								(b)
		Right 2								(c)

Table 4 .

 4 2: Integrated Analysis of selected real-time methods from The Middlebury Stereo Database[START_REF]Middlebury stereo vision[END_REF]

	Method	Rank	Avg.error %	Avg.runtime (ms)	Device	Estimated time(ms)	Estimation Rank(th)
	costFilter	24	5.55	65	NVIDIA GTX480	325	5
	Plane-fitBP	30	5.78	650	NVIDIA Geforce 8800 GTX	about 650	7
	Proposed method	43	5.58	50	Nvidia GT540M	50	2
	RealtimeHD	59	6.66	15	NVIDIA GTX580	75	3
	Adaptweight	70	6.67	8500	AMD2700+	about 500	6
	RealTimeABW	87	7.90	2807	2.80GHz Core 2 duo	about 280	4
	Real-time GPU	100	9.82	142	ATI Radeon 1800	below 50	1

Table 4 .

 4 In order to normalize the result of time-efficiency, we estimate time-consuming of all these methods running on our GPU device GT540m in the column Estimation of Table4.2. From the Estimated Rank about the time-efficiency of Table4.2, our proposed method can get the second position. It means that our implementation has a great potential in terms of time-efficiency and matching accuracy.

	2 provides one brief introduction and benchmark comparison of these an-
	nounced real-time methods from Middlebury Stereo Evaluation. Our experimental
	environments: GPU: NVIDIA GT 540M (96 CUDA cores), CPU: I7 2630qm, image
	definition: 352 × 288, disparity range: [0,15]. Compared with these announced real-

time methods in Table

4

.2, our method is not the best one about matching accuracy, but we can get the top 10 rank in 140 submissions about the time-efficiency. As described in Table

4

.2, costFilter algorithm is implemented on the Nvidia GTX480

Contexte et environnement de travail

	Chapitre 2 : Ce chapitre donne un aperçu de notre méthodologie de prototypage rapide. L'ap-
	proche est globalement ascendante, du matériel jusqu'au domaine applicatif. Elle
	décrit ainsi les systèmes embarqués parallèles, les modèles de programmation paral-
	lèle, les outils de la méthodologie et finalement les concepts de base des applications
	ciblées.
	Les différents systèmes embarqués sont ainsi discutés dans la section 2.1. Le mod-
	èle de programmation OpenCL est présenté dans la section 2.2 : il est le modèle de
	niveau intermédiaire dans le cadre de notre méthodologie. L'approche flot de données
	est ensuite présentée dans la section 2.3 : elle est le modèle de haut-niveau de notre
	méthodologie. Trois outils de la méthodologie sont ensuite introduits dans la section
	2.4. Finalement, dans la section 2.5, les bases des applications développées sont pré-
	cisées : estimation de mouvement et appariement stéréo. Une brève conclusion est
	effectuée dans la section 2.6.
	Ce mémoire de thèse est structuré comme suit : Le chapitre 2 introduit glob-
	alement le contexte de travail, soient les architectures ciblées, les différents modèles
	de programmation, l'environnement de prototypage rapide et les bases sur les appli-
	cations développées. Les chapitres suivants explicitent ensuite les trois algorithmes
	précédemment cités : le chapitre 3 pour l'estimation de mouvement, le chapitre 4
	pour l'appariement stéréo et le chapitre 5 pour l'appariement stéréo basé mouve-
	ment. Finalement, le chapitre 6 présente la conclusion du mémoire.

group OpenCL programming model work-group Context GPU Architecture work-group work-group work-group work-group work-group work-group work-group

  Le tableau A.1 décrit l'équivalence directe établie entre la structure du langage OpenCL et la structure d'un GPU : thread et work-item, threads-group et workgroup. Un work-item est l'unité atomique d'un noyau d'exécution OpenCL et tous les work-items d'un work-group exécutent la même instruction simultanément. De même, les mémoires locales et globales d'un contexte OpenCL correspondent respectivement à la mémoire partagée et à la mémoire du composant ciblé. Comme le montre la figure A.6 sur un GPU, chaque work-group s'exécute sur une unité de calcul (CU -Computing Unit), et chaque work-item s'exécute sur un élément de traitement (PE -Processing Element). La mémoire privée est affectée à un workitem, tandis que la mémoire locale est partagée par tous les work-items d'un même work-group. Les mémoires globale et constante sont accessibles par tous les workgroups.

	Compute Device
	Compute Units 1		Compute Units M
	Private Memory 1	...	Private Memory N	...	Private Memory 1	...	Private Memory N
	PE 1		PE N		PE 1		PE N	work-item_1	...	work-item_N
	Local Memory 1				Local Memory N
			Global /Constant Memory Data Cache
								a[0] ... a[511]	…...	a[3584] ... a[4095]
				Global Memory				a[4096]
				Constant Memory			b[4096]
		Compute Device Memory
								c[4096]
								float a[4096], b[4096], c[4096]; for (i=0; i<4096; i++) { c[i] = a[i] * b[i]; }
			Table A.1 -Equivalences GPU -OpenCL. Devices OpenCL
					thread		work-item
				threads group	work-group
				shared memory local memory
				device memory global memory

work-Applications Figure A.6 -Architecture GPU et modèle OpenCL. cible, tout en utilisant une grammaire similaire au langage C.

Dans le cadre de notre méthodologie de prototypage rapide, OpenCL est un modèle de programmation de niveau intermédiaire. Si OpenCL permet la portabilité des applications, il ne garantit pas la portabilité des performances, ce qui peut nécessiter un ajustement complémentaire dans la mise en oeuvre sur une plateforme spécifique ou engendrer des charges de travail dynamiques imprévisibles.

  Comme il est difficile de partager un objet de mémoire ou de synchroniser les queues des commandes dans des contextes différents, nous construisons avec OpenCL, un contexte combiné des CPU et GPU, montré dans la figure A.11. Dans ce contexte combiné, le CPU et le GPU ont respectivement leur propre mémoire globale, ce qui évite les transferts de données entre ces deux composants, d'où un gain de temps.

  Annexe A. Résumé étendu en français générer rapidement du code OpenCL ou CUDA.

La figure A.12 est une description flot de données de notre algorithme ME. Le bloc " source " est une FU qui charge la séquence vidéo. Les blocs " ExtractYRef " et " ExtractY " extraient la composante Y de la séquence vidéo codée en YUV, à

  Notre algorithme est meilleur que les autres méthodes d'appariement stéréo pour des séquences vidéo abondantes en mouvement, même fortement bruitées. Finalement, une interface utilisateur graphique a été développée, intégrant nos différents algorithmes.RésuméLe travail présenté dans cette thèse s'inscrit dans un contexte de manipulation croissante d'images et de vidéo sur des systèmes embarqués parallèles. Les limitations et le manque de flexibilité dans la conception actuelle de ces systèmes font qu'il est de plus en plus compliqué de mettre en oeuvre les applications, en particulier lorsque le système est hétérogène. Or, non seulement Open Computing Language (OpenCL) est un nouveau cadre pour utiliser pleinement la capacité de calcul des processeurs généraux ou embarqués, mais, en outre, des outils de prototypage rapide sont disponibles pour la conception des systèmes, leur but étant de générer un prototype fiable ou de mettre en oeuvre de manière automatique les applications de traitement d'images et vidéo sur les systèmes embarqués. L'objectif général de cette thèse est d'évaluer et d'améliorer les processus de conception pour les systèmes embarqués, particulièrement ceux fondés sur des approches flot de données (haut niveau d'abstraction) et OpenCL (niveau intermédiaire d'abstraction). Cet objectif ambitieux fait l'objet de plusieurs projets dont le projet collaboratif COMPA, mettant en oeuvre les outils Orcc, Preesm et HMPP. Dans ce cadre, cette thèse vise à valider et évaluer ces outils sur des applications d'estimation de mouvement et d'appariement stéréo. Nous avons ainsi modélisé ces applications dans le langage hautniveau RVC-CAL. Puis, par le biais des trois outils Orcc, Preesm et HMPP, nous avons généré et vérifié du code C, OpenCL et CUDA, pour des plates-formes hétérogènes CPU multi-coeur et GPU. L'implémentation des algorithmes sur la puce embarquée MPPA multi-coeur (many-core) de la société KALRAY, a été étudiée. Pour atteindre l'objectif, nous avons proposé trois algorithmes. Le premier est un estimateur de mouvement parallélisé pour un système hétérogène constitué d'un CPU et d'un GPU : pour cette implantation, nous avons développé une méthode qui équilibre la répartition des charges entre CPU et GPU. Le second algorithme est une méthode d'appariement stéréo en temps réel : elle utilise une combinaison de fonctions de coût et une agrégation des coûts par pas d'itération carré ; nos résultats expérimentaux surpassent les autres méthodes en offrant un compromis intéressant entre la complexité de l'algorithme et sa précision. Le troisième algorithme est une méthode d'appariement stéréo basée sur le mouvement : elle utilise les vecteurs de mouvements issus du premier algorithme pour déterminer la région d'étude nécessaire pour le second algorithme ; nos résultats montrent que l'approche est particulièrement efficace lorsque les séquences de test sont riches en mouvement, même bruitées.

	INSA de RENNES
	Service des Formations
		AVIS DU JURY SUR LA REPRODUCTION DE LA THESE SOUTENUE
	Titre de la thèse: Prototyping methodology of image processing applications on heterogeneous parallel systems
	Nom Prénorn de l'auteur: ZHANG JINGLIN
		Membres du jury : -Monsieur NEZAN Jean-François -Monsieur COUSIN Jean-Gabriel -Monsieur MOREAU Guillaume -Monsieur PAINDAVOINE Micnel -Monsieur HOUZËT Dominique
		présidentdu jury, i-f ;JC PR ;ru ùffu*itf (
		Date de la soutenance: 19 Décembre2O13
		Reproduction'de la these soutenue
	X tl	Thèse pouvant être reproduite en l'état Thèse pouvant être reproduite après corrections suggérées
		Fait à Rennes, le 19 Décembre 2013
	Mots-clés : méthodologie de prototypage, système hétérogène,
	estimation de mouvement, appariement stéréo, OpenCL,
	HMPP.

(a) (c) (d) (b)

coeurs, ainsi que des interfaces grande vitesse pour communiquer avec son environnement extérieur (PCIe, Ethernet, DDR). Ce MPPA offre une puissance de plus de 500 GOPS pour une faible consommation d'énergie, ce qui le positionne comme une des solutions les plus efficaces sur le marché de l'électronique professionnelle.

Acknowledgments

The work of this thesis is one three-years work and life in INSA-Rennes. It is also a very important part in my life. In here, i have learned how to make research.

Data 9 6 8 4 7 2 5 0

Contents

Chapter 5. Joint Motion-Based Video Stereo Matching

In this chapter we propose one joint motion-based local stereo matching method for video sequence. For each frame of the stereo video, our method first builds the support region for the selected central pixel with the help of motion vectors. Then it aggregates raw matching cost with adaptive motion weight and iterates with square step size in the support region along the horizontal and vertical passes. This chapter is organized as follow: Section 5.2 introduces our stereo video matching algorithm with several procedures. Section 5.3 presents our implementation of the video stereo matching on an heterogeneous system. Section 5.4 describes our experimental results and compare them with other existing stereo video matching methods. Section 5.5 introduces our video stereo matching GUI interface which integrates our proposed method. Section 5.6 gives a brief conclusion.

Joint Motion-Based Stereo Matching

All the local stereo matching methods employ cost aggregation in support region for each pixel. In this sense, there is one common assumption that all the neighboring pixels of the support region have the same disparity. However, without any prior knowledge about disparity, all these pixels should have the similar intensity. Yoon et al. [START_REF] Yoon | Adaptive support-weight approach for correspondence search[END_REF] proposed one adaptive support-weight approach. Their method aggregates cost over large support windows size (35 × 35) according to color similarity and geometric proximity. Zhang et al. [START_REF] Zhang | Cross-based local stereo matching using orthogonal integral images[END_REF] proposed one upright cross local method and dynamically construct a shape-adaptive support region. Their method reduced the complexity of computation due to the shape-adaptive support region instead of fixed support region. In short, the more accuracy of building support region we get, the more accuracy support weights and row matching costs we could use in the cost aggregation of video stereo matching.

Local support region building

Instead of a collection of values associated with individual photo receptors, human perceive a number of visual groups, usually associated with objects or welldefined parts of objects. How the eye tends to group visual information depending Chapter 5. Joint Motion-Based Video Stereo Matching To verify the robustness of our method, we apply the additive noise σ (range from 0 to 100) into 5 synthetic videos as described in [START_REF] Richardt | Real-time spatiotemporal stereo matching using the dual-crossbilateral grid[END_REF]. Plots of the error are shown in Figure 5.9. Our method is superior except "Temple" and "Street" sequence.

Time-efficiency results

Stereo Matching Graphical User Interface (GUI)

Based on our research on stereo matching algorithms, we developed one GUI interface which integrates cameras calibration and stereo matching together. Our GUI The following additional experiments focus on two conditions: real world disparity with fixed camera and moving camera. Figure 5.12 shows the visual result of the JMSS method in different scenes with fixed stereo camera. Several persons are moving in the scene and there is a strong light source. Even with those difficult real world scenes, the proposed JMSS method provides accurate disparities for the different objects.

In particular, Figure 5.13 illustrates some extrem conditions of real stereo visions such as out of focus (the 1st and 2nd examples in the top part), light reflection (the 1st, 3rd and 4th examples in the bottom part), object distortion and occlusion (camera is too close to the objects, the 1st example in the bottom part) with moving camera like the actual conditions of consumer electronics in daily use. JMSS method can efficiently and accurately obtain the real disparity in spite of the high level of noise and the bad matching points of those extreme conditions.

Conclusions

In this chapter, we propose a joint motion-based local stereo video matching algorithm named JMSS. Our method first build the support region for selected central pixel with the help of motion vectors, then aggregates raw matching costs with adaptive motion weights, and finally iterates with square step size in support regions along horizontal and vertical pass. We apply the motion vector component into support regions building and adaptive weights to elaborate our approach for the stereo video matching.

Experimental results show that our proposed method outperforms the state-ofthe-art stereo video matching methods in test sequences with large amount of noise and high motion vectors. We introduce our graphic user interface of stereo matching which consists of three parts: display region, camera calibration, stereo matching. Some real world examples of disparity are verified by our proposed method which focuses on two conditions: real world disparity with fixed camera and moving camera.

Experimental results based on real world video sequences indicate that our method performs better than LASW method. For timing efficiency, our method obtains almost 20 fps in video stereo matching applications with help of GPU computing.

Expérimentations et conclusion

Publications

Journal:

List of Figures

Abstract

The work presented in this thesis takes place in a context of growing demand for image and video applications on parallel embedded systems. The limitations and lack of flexibility of current design with parallel embedded systems make increasingly complicated to implement applications, particularly on heterogeneous systems. But Open Computing Language (OpenCL) is a new framework for fully employ the capability of computation of general purpose processors or embedded processors. In the meantime, some rapid prototyping tools to design systems are proposed to generate a reliably prototype or automatically implement the image and video applications on embedded systems.

The goal of this thesis was to evaluate and to improve design processes for embedded systems, especially based on the dataflow approach (high level of abstraction) and OpenCL approach (intermediate level of abstraction). This challenge is tackled by several projects including the collaborative project COMPA which studies a framework based on the Orcc, Preesm and HMPP tools. In this context, this thesis aims to validate and to evaluate the framework with motion estimation and stereo matching algorithms. For this aim, algorithms have been described using the high-level RVC-CAL language. With the help of Orcc, Preesm, and HMPP tools, we generated and verified C code or OpenCL code or CUDA code for heterogeneous platforms based on multi-core CPU and GPU. We also studied the implementations of these algorithms onto the last generation of many-core for embedded system called MPPA and developed by KALRAY.

We proposed three algorithms. One is a parallelized motion estimation method for heterogeneous system based on one CPU and one GPU: we developed one basic method to balance the workload distribution on such heterogeneous system. The second algorithm is a real-time stereo matching method that adopts combined costs and costs aggregation with square size step to implement on laptop's GPU platform: our experimental results outperform other baseline methods about tradeoff between matching accuracy and time-efficiency. The third algorithm is a joint motion-based video stereo matching method that uses the motion vectors calculated by the first algorithm to build the support region for the second algorithm: our experimental results outperform the stereo video matching methods in the test sequences with abundant movement even in large amounts of noise.

Keywords: prototyping methodology, heterogeneous system, motion estimation, stereo matching, OpenCL, HMPP.