186
Le format de compression JPEG ou comment les mathématiques servent (parfois) à quelque chose... E. Le Pennec INRIA Saclay - IdF – SELECT Lycée J.B. Corot - Savigny / 04/02/2011

Le format de compression JPEG ou comment les mathématiques

  • Upload
    others

  • View
    1

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Le format de compression JPEG ou comment les mathématiques

Le

form

atde

com

pre

ssio

nJP

EG

ou

com

men

tle

sm

athém

atiq

ues

serv

ent

(par

fois

quel

que

chose

...

E.Le

Pen

nec

INR

IASacl

ay-

IdF

–SELEC

T

Lyc

éeJ.

B.C

oro

t-

Savi

gny

/04/02/2011

Page 2: Le format de compression JPEG ou comment les mathématiques

Erw

anL

eP

ennec

Page 3: Le format de compression JPEG ou comment les mathématiques

Erw

anL

eP

ennec

→→

Page 4: Le format de compression JPEG ou comment les mathématiques

Erw

anL

eP

ennec

→→

Bac

Sci

entifique

(C)

–ly

cée

P.Langev

in,Sure

snes

(93).

Pré

pa

–ly

cée

Past

eur,

Neu

illy

(93–95).

EN

SC

ach

an

(95).

Lic

ence

etM

aîtrise

de

Math

àPar

is7

(96).

DEA

:M

ath

ématiques

etIn

telli

gen

ceA

rtifi

ciel

le–

Cach

an

(97).

Agré

gation

de

Math

(98).

Doct

ora

t:B

andel

ette

set

repré

senta

tion

géo

mét

rique

des

images

(98–02).

Let

ItW

ave

:Tra

item

ent

d’im

age

eten

par

ticu

lier

com

pre

ssio

nd’im

age

de

visa

ge

(02–04).

Maître

de

Confé

rence

(sta

tist

ique)

–Par

is7

–LPM

A(0

4–10).

Char

de

Rec

her

che

(sta

tist

ique)

–IN

RIA

Sacl

ay–

SELEC

T(1

0–).

Page 5: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nd’im

age

Page 6: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nd’im

age

Page 7: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nd’im

age

→0110101..

.

Page 8: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nd’im

age

→0110101..

.→

Page 9: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nd’im

age

Page 10: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nd’im

age

Image

num

ériq

ue

etm

otiva

tions

Page 11: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nd’im

age

Image

num

ériq

ue

etm

otiva

tions

Com

pre

ssio

nsa

ns

per

te:

TIF

,

GIF

,

PN

G...

Page 12: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nd’im

age

Image

num

ériq

ue

etm

otiva

tions

Com

pre

ssio

nsa

ns

per

te:

TIF

,

GIF

,

PN

G...

Com

pre

ssio

nave

cper

te:

JPEG

,

JPEG

2K

Page 13: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nd’im

age

Image

num

ériq

ue

etm

otiva

tions

Com

pre

ssio

nsa

ns

per

te:

TIF

,

GIF

,

PN

G...

Com

pre

ssio

nave

cper

te:

JPEG

,

JPEG

2K

Et

aprè

s?

Page 14: Le format de compression JPEG ou comment les mathématiques

Imag

enum

ériq

ue

Page 15: Le format de compression JPEG ou comment les mathématiques

Imag

enum

ériq

ue

Image

défi

nie

(captu

rée)

dans

un

rect

angle

(fonct

ion).

Page 16: Le format de compression JPEG ou comment les mathématiques

Imag

enum

ériq

ue

Image

défi

nie

(captu

rée)

dans

un

rect

angle

(fonct

ion).

Image

num

ériq

ue

:ve

rsio

ndiscr

étisée

enposition

(matr

ice,

mosa

ïque)

eten

vale

urs

(8bits)

.

Page 17: Le format de compression JPEG ou comment les mathématiques

Imag

enum

ériq

ue

Image

défi

nie

(captu

rée)

dans

un

rect

angle

(fonct

ion).

Image

num

ériq

ue

:ve

rsio

ndiscr

étisée

enposition

(matr

ice,

mosa

ïque)

eten

vale

urs

(8bits)

.

Pour

laco

ule

ur

:utilis

ation

de

3im

ages

(RG

B-

24

bits)

.

Page 18: Le format de compression JPEG ou comment les mathématiques

Imag

enum

ériq

ue

Image

défi

nie

(captu

rée)

dans

un

rect

angle

(fonct

ion).

Image

num

ériq

ue

:ve

rsio

ndiscr

étisée

enposition

(matr

ice,

mosa

ïque)

eten

vale

urs

(8bits)

.

Pour

laco

ule

ur

:utilis

ation

de

3im

ages

(RG

B-

24

bits)

.

Occ

upation

mém

oire

import

ante

:

2048×3072×24=18×223

bits=18

Mo

Page 19: Le format de compression JPEG ou comment les mathématiques

Imag

enum

ériq

ue

Image

défi

nie

(captu

rée)

dans

un

rect

angle

(fonct

ion).

Image

num

ériq

ue

:ve

rsio

ndiscr

étisée

enposition

(matr

ice,

mosa

ïque)

eten

vale

urs

(8bits)

.

Pour

laco

ule

ur

:utilis

ation

de

3im

ages

(RG

B-

24

bits)

.

Occ

upation

mém

oire

import

ante

:

2048×3072×24=18×223

bits=18

Mo

Bes

oin

de

com

pre

ssio

n.

Page 20: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nd’im

age

Page 21: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nd’im

age

Image

idéa

le...

Page 22: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nd’im

age

Image

idéa

le...

Image

=Im

age

num

ériq

ue

enniv

eau

de

gris

pro

venant

des

capte

urs

de

l’appar

eilphoto

.

Page 23: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nd’im

age

Image

idéa

le...

Image

=Im

age

num

ériq

ue

enniv

eau

de

gris

pro

venant

des

capte

urs

de

l’appar

eilphoto

.

Sim

plifi

cation

!:ré

solu

tion,co

ule

ur,

motifde

Bay

er,.

..

Page 24: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nd’im

age

→→ ←

0110101..

.

Image

idéa

le...

Image

=Im

age

num

ériq

ue

enniv

eau

de

gris

pro

venant

des

capte

urs

de

l’appar

eilphoto

.

Sim

plifi

cation

!:ré

solu

tion,co

ule

ur,

motifde

Bay

er,.

..

Com

pre

ssio

nsa

ns

per

te(le

reto

urve

rsla

vers

ion

origin

ale

est

poss

ible

):

TIF

,G

IF,PN

G,.

..

Page 25: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nd’im

age

→→

0110101..

.

Image

idéa

le...

Image

=Im

age

num

ériq

ue

enniv

eau

de

gris

pro

venant

des

capte

urs

de

l’appar

eilphoto

.

Sim

plifi

cation

!:ré

solu

tion,co

ule

ur,

motifde

Bay

er,.

..

Com

pre

ssio

nsa

ns

per

te(le

reto

urve

rsla

vers

ion

origin

ale

est

poss

ible

):

TIF

,G

IF,PN

G,.

..

Com

pre

ssio

nave

cper

te(r

etour

imposs

ible

):JP

EG

,JP

EG

2K

,...

.

Page 26: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nsa

ns

per

te

Page 27: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nsa

ns

per

te

→ ←0110101..

.

Page 28: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nsa

ns

per

te

→ ←0110101..

.

Com

pre

ssio

nde

type

ZIP

,R

AR

and

co.

Page 29: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nsa

ns

per

te

→ ←0110101..

.

Com

pre

ssio

nde

type

ZIP

,R

AR

and

co.

Ret

our

poss

ible

=pas

de

per

ted’info

rmation.

Page 30: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nsa

ns

per

te

→ ←0110101..

.

Com

pre

ssio

nde

type

ZIP

,R

AR

and

co.

Ret

our

poss

ible

=pas

de

per

ted’info

rmation.

Exp

loitation

de

lare

dondance

(rép

étitio

n)

dans

les

suites

de

vale

urs

.

Page 31: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nsa

ns

per

te

→ ←0110101..

.

Com

pre

ssio

nde

type

ZIP

,R

AR

and

co.

Ret

our

poss

ible

=pas

de

per

ted’info

rmation.

Exp

loitation

de

lare

dondance

(rép

étitio

n)

dans

les

suites

de

vale

urs

.

Intu

itio

n:la

nguage

=le

sm

ots

les

plu

sutilis

ésso

nt

les

plu

sco

urt

s...

Page 32: Le format de compression JPEG ou comment les mathématiques

TIF

etR

LE

Page 33: Le format de compression JPEG ou comment les mathématiques

TIF

etR

LE

0−0−0−1−1−1−1−1−0−0−0−0−2−2−2−2−128−128−128

Page 34: Le format de compression JPEG ou comment les mathématiques

TIF

etR

LE

0−0−0−1−1−1−1−1−0−0−0−0−2−2−2−2−128−128−128

Liste

de

lava

leur

des

pix

els

Page 35: Le format de compression JPEG ou comment les mathématiques

TIF

etR

LE

0−0−0−1−1−1−1−1−0−0−0−0−2−2−2−2−128−128−128

Liste

de

lava

leur

des

pix

els

Alg

orith

me

de

com

pre

ssio

nle

plu

ssim

ple

.

Page 36: Le format de compression JPEG ou comment les mathématiques

TIF

etR

LE

0−0−0−1−1−1−1−1−0−0−0−0−2−2−2−2−128−128−128

Liste

de

lava

leur

des

pix

els

Alg

orith

me

de

com

pre

ssio

nle

plu

ssim

ple

.

Run

Len

gth

Enco

din

g:C

odage

de

laLongueu

rde

laSér

ieen

Cours

...

Page 37: Le format de compression JPEG ou comment les mathématiques

TIF

etR

LE

0−0−0−1−1−1−1−1−0−0−0−0−2−2−2−2−128−128−128

(0,3)−(1,5)−(0,4)−(2,4)−(128,3)

Liste

de

lava

leur

des

pix

els

Alg

orith

me

de

com

pre

ssio

nle

plu

ssim

ple

.

Run

Len

gth

Enco

din

g:C

odage

de

laLongueu

rde

laSér

ieen

Cours

...

Utilis

ation

de

laré

pét

itio

n(a

ssez

rare

dans

lavr

aie

vie)

.

Page 38: Le format de compression JPEG ou comment les mathématiques

TIF

etR

LE

0−0−0−1−1−1−1−1−0−0−0−0−2−2−2−2−128−128−128

(0,3)−(1,5)−(0,4)−(2,4)−(128,3)

Liste

de

lava

leur

des

pix

els

Alg

orith

me

de

com

pre

ssio

nle

plu

ssim

ple

.

Run

Len

gth

Enco

din

g:C

odage

de

laLongueu

rde

laSér

ieen

Cours

...

Utilis

ation

de

laré

pét

itio

n(a

ssez

rare

dans

lavr

aie

vie)

.

Rem

pla

cer

une

suite

de

vale

ur

iden

tique

par

un

sym

bole

suiv

ide

la

vale

ur

etdu

nom

bre

de

fois

elle

appar

aît.

Page 39: Le format de compression JPEG ou comment les mathématiques

TIF

etR

LE

0−0−0−1−1−1−1−1−0−0−0−0−2−2−2−2−128−128−128

(0,3)−(1,5)−(0,4)−(2,4)−(128,3)

Liste

de

lava

leur

des

pix

els

Alg

orith

me

de

com

pre

ssio

nle

plu

ssim

ple

.

Run

Len

gth

Enco

din

g:C

odage

de

laLongueu

rde

laSér

ieen

Cours

...

Utilis

ation

de

laré

pét

itio

n(a

ssez

rare

dans

lavr

aie

vie)

.

Rem

pla

cer

une

suite

de

vale

ur

iden

tique

par

un

sym

bole

suiv

ide

la

vale

ur

etdu

nom

bre

de

fois

elle

appar

aît.

Utilis

erdans

lefo

rmat

TIF

pour

des

images

«ca

rtoons

».

Page 40: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nsa

ns

per

te

Page 41: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nsa

ns

per

teLangue

:co

nce

pt

fréq

uen

t=

mot

court

.

Page 42: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nsa

ns

per

teLangue

:co

nce

pt

fréq

uen

t=

mot

court

.

Théo

rie

de

l’in

form

ation

(Sta

tist

ique)

:va

leur

fréq

uen

te=

code

court

.

Page 43: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nsa

ns

per

teLangue

:co

nce

pt

fréq

uen

t=

mot

court

.

Théo

rie

de

l’in

form

ation

(Sta

tist

ique)

:va

leur

fréq

uen

te=

code

court

.

Mes

ure

de

lafr

équen

ce:pro

babili

tés.

pi=

Nb

appar

itio

ns

de

lava

leuri

Nb

tota

l

Page 44: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nsa

ns

per

teLangue

:co

nce

pt

fréq

uen

t=

mot

court

.

Théo

rie

de

l’in

form

ation

(Sta

tist

ique)

:va

leur

fréq

uen

te=

code

court

.

Mes

ure

de

lafr

équen

ce:pro

babili

tés.

pi=

Nb

appar

itio

ns

de

lava

leuri

Nb

tota

l

Longueu

rdu

mes

sage

:∑

i

(Nb

appar

itio

ns

de

lava

leuri×

longueu

rdu

code

pouri)

=N

bto

tal×

(

i

pi×

longueu

rdu

code

pouri)

Page 45: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nsa

ns

per

teLangue

:co

nce

pt

fréq

uen

t=

mot

court

.

Théo

rie

de

l’in

form

ation

(Sta

tist

ique)

:va

leur

fréq

uen

te=

code

court

.

Mes

ure

de

lafr

équen

ce:pro

babili

tés.

pi=

Nb

appar

itio

ns

de

lava

leuri

Nb

tota

l

Longueu

rdu

mes

sage

:∑

i

(Nb

appar

itio

ns

de

lava

leuri×

longueu

rdu

code

pouri)

=N

bto

tal×

(

i

pi×

longueu

rdu

code

pouri)

Choix

del i=

longueu

rdu

code

pouri?

Page 46: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nsa

ns

per

teLangue

:co

nce

pt

fréq

uen

t=

mot

court

.

Théo

rie

de

l’in

form

ation

(Sta

tist

ique)

:va

leur

fréq

uen

te=

code

court

.

Mes

ure

de

lafr

équen

ce:pro

babili

tés.

pi=

Nb

appar

itio

ns

de

lava

leuri

Nb

tota

l

Longueu

rdu

mes

sage

:∑

i

(Nb

appar

itio

ns

de

lava

leuri×

longueu

rdu

code

pouri)

=N

bto

tal×

(

i

pi×

longueu

rdu

code

pouri)

Choix

del i=

longueu

rdu

code

pouri?

Longueu

roptim

ale

:

l i=−log2(pi)

Page 47: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nsa

ns

per

teLangue

:co

nce

pt

fréq

uen

t=

mot

court

.

Théo

rie

de

l’in

form

ation

(Sta

tist

ique)

:va

leur

fréq

uen

te=

code

court

.

Mes

ure

de

lafr

équen

ce:pro

babili

tés.

pi=

Nb

appar

itio

ns

de

lava

leuri

Nb

tota

l

Longueu

rdu

mes

sage

:∑

i

(Nb

appar

itio

ns

de

lava

leuri×

longueu

rdu

code

pouri)

=N

bto

tal×

(

i

pi×

longueu

rdu

code

pouri)

Choix

del i=

longueu

rdu

code

pouri?

Longueu

roptim

ale

:

l i=−log2(pi)

Alg

orith

mes

:D

ictionnaire

(LZ)

/Pro

babili

ste

(Huffm

an/A

rith

mét

ique)

.

Page 48: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

npar

dic

tionnai

re

Page 49: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

npar

dic

tionnai

re

0−0−0−1−1−1−1−1−0−0−0−0−2−2−2−2−128−128−128

(1)−0−(2)−1−(3)−(4)−(5)−128

Rem

pla

cem

ent

d’u

ne

suite

de

sym

bole

par

son

num

éro

dans

un

dic

tionnaire.

Page 50: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

npar

dic

tionnai

re

0−0−0−1−1−1−1−1−0−0−0−0−2−2−2−2−128−128−128

(1)−0−(2)−1−(3)−(4)−(5)−128

ave

c

(1)=0−0,(2)=1−1−1−1,(3)=0−0−0−0,

(4)=2−2−2−2,(5)=128−128

Rem

pla

cem

ent

d’u

ne

suite

de

sym

bole

par

son

num

éro

dans

un

dic

tionnaire.

Diffi

culté

:avo

irle

mêm

edic

tionnaire

au

codage

etau

déc

odage.

Page 51: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

npar

dic

tionnai

re

0−0−0−1−1−1−1−1−0−0−0−0−2−2−2−2−128−128−128

(1)−0−(2)−1−(3)−(4)−(5)−128

ave

c

(1)=0−0,(2)=1−1−1−1,(3)=0−0−0−0,

(4)=2−2−2−2,(5)=128−128

Rem

pla

cem

ent

d’u

ne

suite

de

sym

bole

par

son

num

éro

dans

un

dic

tionnaire.

Diffi

culté

:avo

irle

mêm

edic

tionnaire

au

codage

etau

déc

odage.

Const

ruct

ion

d’u

ndic

tionnaire

ave

cle

train

bin

aire

déj

àlu

:pas

bes

oin

de

transm

ettr

ece

dic

tionnaire!

Page 52: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

npar

dic

tionnai

re

0−0−0−1−1−1−1−1−0−0−0−0−2−2−2−2−128−128−128

(1)−0−(2)−1−(3)−(4)−(5)−128

ave

c

(1)=0−0,(2)=1−1−1−1,(3)=0−0−0−0,

(4)=2−2−2−2,(5)=128−128

Rem

pla

cem

ent

d’u

ne

suite

de

sym

bole

par

son

num

éro

dans

un

dic

tionnaire.

Diffi

culté

:avo

irle

mêm

edic

tionnaire

au

codage

etau

déc

odage.

Const

ruct

ion

d’u

ndic

tionnaire

ave

cle

train

bin

aire

déj

àlu

:pas

bes

oin

de

transm

ettr

ece

dic

tionnaire!

LZ77,LZW

,ZIP

,R

AR

...

Page 53: Le format de compression JPEG ou comment les mathématiques

GIF

Page 54: Le format de compression JPEG ou comment les mathématiques

GIF

Alg

orith

me

de

com

pre

ssio

nsa

ns

per

tein

troduit

par

Com

puse

rve

en

1987.

Page 55: Le format de compression JPEG ou comment les mathématiques

GIF

→ ←0−116−128−255−...

Alg

orith

me

de

com

pre

ssio

nsa

ns

per

tein

troduit

par

Com

puse

rve

en

1987.

Liste

de

lava

leur

des

pix

els.

Page 56: Le format de compression JPEG ou comment les mathématiques

GIF

→ ←0−116−128−255−...→ ←

0110101..

.

Alg

orith

me

de

com

pre

ssio

nsa

ns

per

tein

troduit

par

Com

puse

rve

en

1987.

Liste

de

lava

leur

des

pix

els.

Com

pre

ssio

nsa

ns

per

tepar

un

codage

entr

opiq

ue

(ZIP

).

Page 57: Le format de compression JPEG ou comment les mathématiques

GIF

→ ←0−116−128−255−...→ ←

0110101..

.

Alg

orith

me

de

com

pre

ssio

nsa

ns

per

tein

troduit

par

Com

puse

rve

en

1987.

Liste

de

lava

leur

des

pix

els.

Com

pre

ssio

nsa

ns

per

tepar

un

codage

entr

opiq

ue

(ZIP

).

Effi

cace

mais

limité

àdes

fact

eurs

de

com

pre

ssio

nde

2-3

maxi

mum

pour

les

images

natu

relle

s.

Page 58: Le format de compression JPEG ou comment les mathématiques

PN

G

Page 59: Le format de compression JPEG ou comment les mathématiques

PN

G

Alg

orith

me

LZW

bre

veté

:bes

oin

d’u

ne

solu

tion

de

rem

pla

cem

ent

(95).

Page 60: Le format de compression JPEG ou comment les mathématiques

PN

G

→ ←0−116−128−255−...

Alg

orith

me

LZW

bre

veté

:bes

oin

d’u

ne

solu

tion

de

rem

pla

cem

ent

(95).

Liste

des

pix

els

=lis

tede

vale

ur

d’inte

nsité

lum

ineu

se.

Page 61: Le format de compression JPEG ou comment les mathématiques

PN

G

→ ←0−116−128−255−...

→ ←0−116−12−127−...

Alg

orith

me

LZW

bre

veté

:bes

oin

d’u

ne

solu

tion

de

rem

pla

cem

ent

(95).

Liste

des

pix

els

=lis

tede

vale

ur

d’inte

nsité

lum

ineu

se.

Pré

dic

tion

poss

ible

d’u

ne

vale

ur

enfo

nct

ion

de

celle

sdéj

àvu

eset

codage

de

l’er

reur

de

pré

dic

tion.

Page 62: Le format de compression JPEG ou comment les mathématiques

PN

G

→ ←0−116−128−255−...

→ ←0−116−12−127−...→ ←

0110101..

.

Alg

orith

me

LZW

bre

veté

:bes

oin

d’u

ne

solu

tion

de

rem

pla

cem

ent

(95).

Liste

des

pix

els

=lis

tede

vale

ur

d’inte

nsité

lum

ineu

se.

Pré

dic

tion

poss

ible

d’u

ne

vale

ur

enfo

nct

ion

de

celle

sdéj

àvu

eset

codage

de

l’er

reur

de

pré

dic

tion.

Page 63: Le format de compression JPEG ou comment les mathématiques

PN

G

→ ←0−116−128−255−...

→ ←0−116−12−127−...→ ←

0110101..

.

Alg

orith

me

LZW

bre

veté

:bes

oin

d’u

ne

solu

tion

de

rem

pla

cem

ent

(95).

Liste

des

pix

els

=lis

tede

vale

ur

d’inte

nsité

lum

ineu

se.

Pré

dic

tion

poss

ible

d’u

ne

vale

ur

enfo

nct

ion

de

celle

sdéj

àvu

eset

codage

de

l’er

reur

de

pré

dic

tion.

Modèl

esim

ple

:va

leur

pré

céden

te,m

oye

nne

loca

le,.

..

Page 64: Le format de compression JPEG ou comment les mathématiques

PN

G

→ ←0−116−128−255−...

→ ←0−116−12−127−...→ ←

0110101..

.

Alg

orith

me

LZW

bre

veté

:bes

oin

d’u

ne

solu

tion

de

rem

pla

cem

ent

(95).

Liste

des

pix

els

=lis

tede

vale

ur

d’inte

nsité

lum

ineu

se.

Pré

dic

tion

poss

ible

d’u

ne

vale

ur

enfo

nct

ion

de

celle

sdéj

àvu

eset

codage

de

l’er

reur

de

pré

dic

tion.

Modèl

esim

ple

:va

leur

pré

céden

te,m

oye

nne

loca

le,.

..

Utilis

ation

d’u

ne

mei

lleure

modél

isation

statist

ique

d’u

ne

image.

Page 65: Le format de compression JPEG ou comment les mathématiques

PN

G

→ ←0−116−128−255−...

→ ←0−116−12−127−...→ ←

0110101..

.

Alg

orith

me

LZW

bre

veté

:bes

oin

d’u

ne

solu

tion

de

rem

pla

cem

ent

(95).

Liste

des

pix

els

=lis

tede

vale

ur

d’inte

nsité

lum

ineu

se.

Pré

dic

tion

poss

ible

d’u

ne

vale

ur

enfo

nct

ion

de

celle

sdéj

àvu

eset

codage

de

l’er

reur

de

pré

dic

tion.

Modèl

esim

ple

:va

leur

pré

céden

te,m

oye

nne

loca

le,.

..

Utilis

ation

d’u

ne

mei

lleure

modél

isation

statist

ique

d’u

ne

image.

=⇒

Am

élio

ration

de

l’effi

caci

tédes

alg

orith

mes

de

type

dic

tionnaire.

Page 66: Le format de compression JPEG ou comment les mathématiques

Modél

isat

ion

stat

isti

que

Page 67: Le format de compression JPEG ou comment les mathématiques

Modél

isat

ion

stat

isti

que

Le

fact

eur

de

com

pre

ssio

ndép

end

de

lapro

babili

tédans

lem

odèl

e.

Page 68: Le format de compression JPEG ou comment les mathématiques

Modél

isat

ion

stat

isti

que

Le

fact

eur

de

com

pre

ssio

ndép

end

de

lapro

babili

tédans

lem

odèl

e.

Import

ance

de

const

ruire

des

modèl

esst

atist

iques

adapté

s.

Page 69: Le format de compression JPEG ou comment les mathématiques

Modél

isat

ion

stat

isti

que

Le

fact

eur

de

com

pre

ssio

ndép

end

de

lapro

babili

tédans

lem

odèl

e.

Import

ance

de

const

ruire

des

modèl

esst

atist

iques

adapté

s.

Modèl

ede

distr

ibutions

sim

ple

s(iid

ave

cune

distr

ibution

connue)

:

OC

RO

HLO

RG

WR

NM

IELW

ISEU

LL

NB

NESEB

YA

TH

EEI

ALH

EN

HT

TPA

OO

BT

TVA

NA

HB

RL

Page 70: Le format de compression JPEG ou comment les mathématiques

Modél

isat

ion

stat

isti

que

Le

fact

eur

de

com

pre

ssio

ndép

end

de

lapro

babili

tédans

lem

odèl

e.

Import

ance

de

const

ruire

des

modèl

esst

atist

iques

adapté

s.

Modèl

ede

distr

ibutions

sim

ple

s(iid

ave

cune

distr

ibution

connue)

:

OC

RO

HLO

RG

WR

NM

IELW

ISEU

LL

NB

NESEB

YA

TH

EEI

ALH

EN

HT

TPA

OO

BT

TVA

NA

HB

RL

Modèl

ede

dép

endance

enfo

nct

ion

du

pass

é:

INN

OIS

TLAT

WH

EY

CR

AT

ICT

FR

OU

RE

BIR

SG

RO

CID

PO

ND

EN

OM

EO

FD

EM

ON

ST

UR

ES

OF

TH

ER

EPTAG

INIS

REG

OAC

TIO

NA

OF

CR

E

Page 71: Le format de compression JPEG ou comment les mathématiques

Modél

isat

ion

stat

isti

que

Le

fact

eur

de

com

pre

ssio

ndép

end

de

lapro

babili

tédans

lem

odèl

e.

Import

ance

de

const

ruire

des

modèl

esst

atist

iques

adapté

s.

Modèl

ede

distr

ibutions

sim

ple

s(iid

ave

cune

distr

ibution

connue)

:

OC

RO

HLO

RG

WR

NM

IELW

ISEU

LL

NB

NESEB

YA

TH

EEI

ALH

EN

HT

TPA

OO

BT

TVA

NA

HB

RL

Modèl

ede

dép

endance

enfo

nct

ion

du

pass

é:

INN

OIS

TLAT

WH

EY

CR

AT

ICT

FR

OU

RE

BIR

SG

RO

CID

PO

ND

EN

OM

EO

FD

EM

ON

ST

UR

ES

OF

TH

ER

EPTAG

INIS

REG

OAC

TIO

NA

OF

CR

E

Modèl

ede

distr

ibution

plu

sco

mple

xes

:

TH

EH

EA

DA

ND

INFR

ON

TA

LAT

TAC

KO

NA

NEN

GLIS

HW

RIT

ER

TH

AT

TH

EC

HA

RAC

TER

OF

TH

ISPO

INT

IST

HER

EFO

RE

AN

OT

HER

MET

HO

DFO

RT

HE

LET

TER

ST

HAT

TH

ET

IME

OF

WH

OEV

ER

TO

LD

TH

EPR

OB

LEM

FO

RA

NU

NEX

PEC

TED

Page 72: Le format de compression JPEG ou comment les mathématiques

Modél

isat

ion

stat

isti

que

Le

fact

eur

de

com

pre

ssio

ndép

end

de

lapro

babili

tédans

lem

odèl

e.

Import

ance

de

const

ruire

des

modèl

esst

atist

iques

adapté

s.

Modèl

ede

distr

ibutions

sim

ple

s(iid

ave

cune

distr

ibution

connue)

:

OC

RO

HLO

RG

WR

NM

IELW

ISEU

LL

NB

NESEB

YA

TH

EEI

ALH

EN

HT

TPA

OO

BT

TVA

NA

HB

RL

Modèl

ede

dép

endance

enfo

nct

ion

du

pass

é:

INN

OIS

TLAT

WH

EY

CR

AT

ICT

FR

OU

RE

BIR

SG

RO

CID

PO

ND

EN

OM

EO

FD

EM

ON

ST

UR

ES

OF

TH

ER

EPTAG

INIS

REG

OAC

TIO

NA

OF

CR

E

Modèl

ede

distr

ibution

plu

sco

mple

xes

:

TH

EH

EA

DA

ND

INFR

ON

TA

LAT

TAC

KO

NA

NEN

GLIS

HW

RIT

ER

TH

AT

TH

EC

HA

RAC

TER

OF

TH

ISPO

INT

IST

HER

EFO

RE

AN

OT

HER

MET

HO

DFO

RT

HE

LET

TER

ST

HAT

TH

ET

IME

OF

WH

OEV

ER

TO

LD

TH

EPR

OB

LEM

FO

RA

NU

NEX

PEC

TED

Pour

les

images≃

fact

eur

4de

com

pre

ssio

nave

cle

sm

eille

urs

modèl

es

(Mar

kovi

enave

cappre

ntiss

age.

..).

Page 73: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nav

ecp

erte

Page 74: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nav

ecp

erte

→ ←

→ ←0110101..

.01..

.

Taux

de

com

pre

ssio

nsa

ns

per

teso

uve

nt

insu

ffisa

nt.

Page 75: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nav

ecp

erte

→→ ←

0110101..

.

Taux

de

com

pre

ssio

nsa

ns

per

teso

uve

nt

insu

ffisa

nt.

Pour

am

élio

rer

leta

ux

de

com

pre

ssio

n,il

faut

per

dre

de

l’in

form

ation

!

Page 76: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nav

ecp

erte

→→ ←

0110101..

.

Taux

de

com

pre

ssio

nsa

ns

per

teso

uve

nt

insu

ffisa

nt.

Pour

am

élio

rer

leta

ux

de

com

pre

ssio

n,il

faut

per

dre

de

l’in

form

ation

!

Exe

mple

s(f

act

eur

16

de

com

pre

ssio

n)

:

Page 77: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nav

ecp

erte

→→ ←

0110101..

.

Taux

de

com

pre

ssio

nsa

ns

per

teso

uve

nt

insu

ffisa

nt.

Pour

am

élio

rer

leta

ux

de

com

pre

ssio

n,il

faut

per

dre

de

l’in

form

ation

!

Exe

mple

s(f

act

eur

16

de

com

pre

ssio

n)

:

changem

ent

de

réso

lution,

Page 78: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nav

ecp

erte

→→ ←

0110101..

.

Taux

de

com

pre

ssio

nsa

ns

per

teso

uve

nt

insu

ffisa

nt.

Pour

am

élio

rer

leta

ux

de

com

pre

ssio

n,il

faut

per

dre

de

l’in

form

ation

!

Exe

mple

s(f

act

eur

16

de

com

pre

ssio

n)

:

changem

ent

de

réso

lution,

nom

bre

de

coule

urs

utilis

ées,

Page 79: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nav

ecp

erte

→→ ←

0110101..

.

Taux

de

com

pre

ssio

nsa

ns

per

teso

uve

nt

insu

ffisa

nt.

Pour

am

élio

rer

leta

ux

de

com

pre

ssio

n,il

faut

per

dre

de

l’in

form

ation

!

Exe

mple

s(f

act

eur

16

de

com

pre

ssio

n)

:

changem

ent

de

réso

lution,

nom

bre

de

coule

urs

utilis

ées,

fact

eur

de

qualit

é(J

PEG

)

Page 80: Le format de compression JPEG ou comment les mathématiques

Com

pre

ssio

nav

ecp

erte

→→ ←

0110101..

.

Taux

de

com

pre

ssio

nsa

ns

per

teso

uve

nt

insu

ffisa

nt.

Pour

am

élio

rer

leta

ux

de

com

pre

ssio

n,il

faut

per

dre

de

l’in

form

ation

!

Exe

mple

s(f

act

eur

16

de

com

pre

ssio

n)

:

changem

ent

de

réso

lution,

nom

bre

de

coule

urs

utilis

ées,

fact

eur

de

qualit

é(J

PEG

)

Com

men

tça

mar

che

JPEG

?

Page 81: Le format de compression JPEG ou comment les mathématiques

JP

EG

Page 82: Le format de compression JPEG ou comment les mathématiques

JP

EG

Alg

orith

me

pro

posé

en1990

par

un

com

ité

d’e

xper

t(J

oin

t

Photo

gra

phic

Exp

erts

Gro

up).

Page 83: Le format de compression JPEG ou comment les mathématiques

JP

EG

Alg

orith

me

pro

posé

en1990

par

un

com

ité

d’e

xper

t(J

oin

t

Photo

gra

phic

Exp

erts

Gro

up).

Princi

pes

:

Quantifica

tion

aprè

sun

changem

ent

de

base

(DC

T).

Codage

sans

per

te.

Page 84: Le format de compression JPEG ou comment les mathématiques

JP

EG

Alg

orith

me

pro

posé

en1990

par

un

com

ité

d’e

xper

t(J

oin

t

Photo

gra

phic

Exp

erts

Gro

up).

Princi

pes

:

Quantifica

tion

aprè

sun

changem

ent

de

base

(DC

T).

Codage

sans

per

te.

Cer

tain

succ

ès!

Page 85: Le format de compression JPEG ou comment les mathématiques

Bas

es..

.

Page 86: Le format de compression JPEG ou comment les mathématiques

Bas

es..

.

Un

peu

de

math

!

Page 87: Le format de compression JPEG ou comment les mathématiques

Bas

es..

.

128=1×100+2×10+8×1

Un

peu

de

math

!

Base

pour

les

nom

bre

s.

Page 88: Le format de compression JPEG ou comment les mathématiques

Bas

es..

.

128=1×100+2×10+8×1

~ V=(1,2,8)=1~x+2~y+8~z

Un

peu

de

math

!

Base

pour

les

nom

bre

s.

Base

pour

les

vect

eurs

.

Page 89: Le format de compression JPEG ou comment les mathématiques

Bas

es..

.

128=1×100+2×10+8×1

~ V=(1,2,8)=1~x+2~y+8~z

P(X)=1+2X+8X2=1X0+2X+8X2(+...)

Un

peu

de

math

!

Base

pour

les

nom

bre

s.

Base

pour

les

vect

eurs

.

Base

pour

les

poly

nôm

es.

Page 90: Le format de compression JPEG ou comment les mathématiques

Bas

es..

.

128=1×100+2×10+8×1

~ V=(1,2,8)=1~x+2~y+8~z

P(X)=1+2X+8X2=1X0+2X+8X2(+...)

f(x)=1f 1(x)+2f 2(x)+8f 3(x)(+...)

Un

peu

de

math

!

Base

pour

les

nom

bre

s.

Base

pour

les

vect

eurs

.

Base

pour

les

poly

nôm

es.

Base

pour

les

fonct

ions!!!.

Page 91: Le format de compression JPEG ou comment les mathématiques

Bas

ede

Fouri

er

Page 92: Le format de compression JPEG ou comment les mathématiques

Bas

ede

Fouri

er

Jose

ph

Fourier

(1807)

:La

pro

pagation

de

lach

ale

ur

dans

les

solid

es.

Page 93: Le format de compression JPEG ou comment les mathématiques

Bas

ede

Fouri

er

Jose

ph

Fourier

(1807)

:La

pro

pagation

de

lach

ale

ur

dans

les

solid

es.

Déc

om

position

des

fonct

ions

sur

l’in

terv

alle[0,1]dans

une

base

de

cosinus

etsinus.

Page 94: Le format de compression JPEG ou comment les mathématiques

Bas

ede

Fouri

er

Jose

ph

Fourier

(1807)

:La

pro

pagation

de

lach

ale

ur

dans

les

solid

es.

Déc

om

position

des

fonct

ions

sur

l’in

terv

alle[0,1]dans

une

base

de

cosinus

etsinus.

Toute

fonct

ion

sur

l’in

terv

alle

s’éc

rit

com

me

som

me

de

sinuso

ïdes

:

f(x)=c 0+c 1cos(2π×x)+s 1cos(2π×x)+c 2cos(2×2π×x)

+s 2sin(2×2π×x)+c 3cos(3×2π×x)+s 3sin(3×2π×x)+···

Page 95: Le format de compression JPEG ou comment les mathématiques

Bas

eet

sim

plifica

tion

Page 96: Le format de compression JPEG ou comment les mathématiques

Bas

eet

sim

plifica

tion

Nb

de

sinus

Rec

onst

ruct

ion

01

00

20

03

00

40

05

00

60

07

00

80

09

00

10

00

−3

0

−2

0

−1

00

10

20

30

40

50

Page 97: Le format de compression JPEG ou comment les mathématiques

Bas

eet

sim

plifica

tion

Nb

de

sinus

Rec

onst

ruct

ion

1024

01

00

20

03

00

40

05

00

60

07

00

80

09

00

10

00

−3

0

−2

0

−1

00

10

20

30

40

50

Page 98: Le format de compression JPEG ou comment les mathématiques

Bas

eet

sim

plifica

tion

Nb

de

sinus

Rec

onst

ruct

ion

512

01

00

20

03

00

40

05

00

60

07

00

80

09

00

10

00

−3

0

−2

0

−1

00

10

20

30

40

50

Page 99: Le format de compression JPEG ou comment les mathématiques

Bas

eet

sim

plifica

tion

Nb

de

sinus

Rec

onst

ruct

ion

256

01

00

20

03

00

40

05

00

60

07

00

80

09

00

10

00

−3

0

−2

0

−1

00

10

20

30

40

50

Page 100: Le format de compression JPEG ou comment les mathématiques

Bas

eet

sim

plifica

tion

Nb

de

sinus

Rec

onst

ruct

ion

128

01

00

20

03

00

40

05

00

60

07

00

80

09

00

10

00

−3

0

−2

0

−1

00

10

20

30

40

50

Page 101: Le format de compression JPEG ou comment les mathématiques

Bas

eet

sim

plifica

tion

Nb

de

sinus

Rec

onst

ruct

ion

64

01

00

20

03

00

40

05

00

60

07

00

80

09

00

10

00

−3

0

−2

0

−1

00

10

20

30

40

50

Page 102: Le format de compression JPEG ou comment les mathématiques

Bas

eet

sim

plifica

tion

Nb

de

sinus

Rec

onst

ruct

ion

32

01

00

20

03

00

40

05

00

60

07

00

80

09

00

10

00

−3

0

−2

0

−1

00

10

20

30

40

50

Page 103: Le format de compression JPEG ou comment les mathématiques

Bas

eet

sim

plifica

tion

Nb

de

sinus

Rec

onst

ruct

ion

16

01

00

20

03

00

40

05

00

60

07

00

80

09

00

10

00

−3

0

−2

0

−1

00

10

20

30

40

50

Page 104: Le format de compression JPEG ou comment les mathématiques

Bas

eet

sim

plifica

tion

Nb

de

sinus

Rec

onst

ruct

ion

1024

01

00

20

03

00

40

05

00

60

07

00

80

09

00

10

00

−3

0

−2

0

−1

00

10

20

30

40

50

Page 105: Le format de compression JPEG ou comment les mathématiques

Bas

ede

Fouri

er2D

Page 106: Le format de compression JPEG ou comment les mathématiques

Bas

ede

Fouri

er2D

Base

de

Fourier

1D

:co

sinus

etsinus.

Page 107: Le format de compression JPEG ou comment les mathématiques

Bas

ede

Fouri

er2D

Base

de

Fourier

1D

:co

sinus

etsinus.

Base

de

Fourier

2D

:co

sinus

etsinus

dans

les

deu

xdirec

tions.

Page 108: Le format de compression JPEG ou comment les mathématiques

Bas

ede

Fouri

er2D

Base

de

Fourier

1D

:co

sinus

etsinus.

Base

de

Fourier

2D

:co

sinus

etsinus

dans

les

deu

xdirec

tions.

Base

sur

des

carr

és8×8

DC

T.

Page 109: Le format de compression JPEG ou comment les mathématiques

Bas

ede

Fouri

er2D

Base

de

Fourier

1D

:co

sinus

etsinus.

Base

de

Fourier

2D

:co

sinus

etsinus

dans

les

deu

xdirec

tions.

Base

sur

des

carr

és8×8

DC

T.

Base

utilis

éedans

JPEG

(Join

tPic

ture

Exp

ert

Gro

up)

en1990.

Page 110: Le format de compression JPEG ou comment les mathématiques

JP

EG

Page 111: Le format de compression JPEG ou comment les mathématiques

JP

EG

Image

initia

le.

Page 112: Le format de compression JPEG ou comment les mathématiques

JP

EG

Image

initia

le.

Déc

oupage

enca

rré8×8.

Page 113: Le format de compression JPEG ou comment les mathématiques

JP

EG

Image

initia

le.

Déc

oupage

enca

rré8×8.

Déc

om

position

dans

labase

de

Fourier

.

Page 114: Le format de compression JPEG ou comment les mathématiques

JP

EG

Image

initia

le.

Déc

oupage

enca

rré8×8.

Déc

om

position

dans

labase

de

Fourier

.

Appro

xim

ation

(sim

plifi

cation)

des

coeffi

cien

ts(≃

réduct

ion

du

nom

bre

de

coule

urs

).

Page 115: Le format de compression JPEG ou comment les mathématiques

JP

EG

Image

initia

le.

Déc

oupage

enca

rré8×8.

Déc

om

position

dans

labase

de

Fourier

.

Appro

xim

ation

(sim

plifi

cation)

des

coeffi

cien

ts(≃

réduct

ion

du

nom

bre

de

coule

urs

).

Appar

itio

nde

nom

bre

ux

zéro

s(b

on

pour

laco

mpre

ssio

n)

sans

trop

d’e

ffet

visu

el.

Page 116: Le format de compression JPEG ou comment les mathématiques

JP

EG

Image

initia

le.

Déc

oupage

enca

rré8×8.

Déc

om

position

dans

labase

de

Fourier

.

Appro

xim

ation

(sim

plifi

cation)

des

coeffi

cien

ts(≃

réduct

ion

du

nom

bre

de

coule

urs

).

Appar

itio

nde

nom

bre

ux

zéro

s(b

on

pour

laco

mpre

ssio

n)

sans

trop

d’e

ffet

visu

el.

Com

pre

ssio

nsa

ns

per

te(p

robabili

ste

/H

uffm

an).

Page 117: Le format de compression JPEG ou comment les mathématiques

JP

EG

Image

initia

le.

Déc

oupage

enca

rré8×8.

Déc

om

position

dans

labase

de

Fourier

.

Appro

xim

ation

(sim

plifi

cation)

des

coeffi

cien

ts(≃

réduct

ion

du

nom

bre

de

coule

urs

).

Appar

itio

nde

nom

bre

ux

zéro

s(b

on

pour

laco

mpre

ssio

n)

sans

trop

d’e

ffet

visu

el.

Com

pre

ssio

nsa

ns

per

te(p

robabili

ste

/H

uffm

an).

Tro

pde

zéro

s=

appar

itio

ns

des

blo

csdans

les

images

.

Page 118: Le format de compression JPEG ou comment les mathématiques

JP

EG

2000

Page 119: Le format de compression JPEG ou comment les mathématiques

JP

EG

2000

Nouveau

standard

(2000..

.).

Page 120: Le format de compression JPEG ou comment les mathématiques

JP

EG

2000

Nouveau

standard

(2000..

.).

Com

ité

JPEG

2000

:pre

mie

rje

t(D

écem

bre

2000),

vers

ion

défi

nitiv

e

(Août

2002).

Page 121: Le format de compression JPEG ou comment les mathématiques

JP

EG

2000

Nouveau

standard

(2000..

.).

Com

ité

JPEG

2000

:pre

mie

rje

t(D

écem

bre

2000),

vers

ion

défi

nitiv

e

(Août

2002).

Diff

éren

ces

ave

cJP

EG

:

Autr

ebase

(ondel

ette

),

Modél

isation

plu

sfine

Page 122: Le format de compression JPEG ou comment les mathématiques

JP

EG

2000

Nouveau

standard

(2000..

.).

Com

ité

JPEG

2000

:pre

mie

rje

t(D

écem

bre

2000),

vers

ion

défi

nitiv

e

(Août

2002).

Diff

éren

ces

ave

cJP

EG

:

Autr

ebase

(ondel

ette

),

Modél

isation

plu

sfine

Ava

nta

ge

:

Per

form

ance

,

Usa

ge

(éch

elonnabili

té,pro

gre

ssiv

ité,

...)

Page 123: Le format de compression JPEG ou comment les mathématiques

Ondel

ette

s1D

Page 124: Le format de compression JPEG ou comment les mathématiques

Ondel

ette

s1D

Fourier

:m

odèl

est

ationnaire.

Page 125: Le format de compression JPEG ou comment les mathématiques

Ondel

ette

s1D

Fourier

:m

odèl

est

ationnaire.

Ondel

ette

s:lo

calis

ation.

Page 126: Le format de compression JPEG ou comment les mathématiques

Ondel

ette

s1D

Fourier

:m

odèl

est

ationnaire.

Ondel

ette

s:lo

calis

ation.

Str

uct

ure

multirés

olu

tion

:appro

xim

ations

succ

essive

set

dét

ails

.

Page 127: Le format de compression JPEG ou comment les mathématiques

Com

pét

itio

nde

bas

es

Page 128: Le format de compression JPEG ou comment les mathématiques

Com

pét

itio

nde

bas

es

Lin

éaire

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

1024

Fourier

Ondel

ette

s

Non

Lin

éaire

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

Page 129: Le format de compression JPEG ou comment les mathématiques

Com

pét

itio

nde

bas

es

Lin

éaire

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

512

Fourier

Ondel

ette

s

Non

Lin

éaire

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

Page 130: Le format de compression JPEG ou comment les mathématiques

Com

pét

itio

nde

bas

es

Lin

éaire

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

256

Fourier

Ondel

ette

s

Non

Lin

éaire

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

Page 131: Le format de compression JPEG ou comment les mathématiques

Com

pét

itio

nde

bas

es

Lin

éaire

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

128

Fourier

Ondel

ette

s

Non

Lin

éaire

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

Page 132: Le format de compression JPEG ou comment les mathématiques

Com

pét

itio

nde

bas

es

Lin

éaire

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

64

Fourier

Ondel

ette

s

Non

Lin

éaire

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

Page 133: Le format de compression JPEG ou comment les mathématiques

Com

pét

itio

nde

bas

es

Lin

éaire

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

32

Fourier

Ondel

ette

s

Non

Lin

éaire

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

Page 134: Le format de compression JPEG ou comment les mathématiques

Com

pét

itio

nde

bas

es

Lin

éaire

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

16

Fourier

Ondel

ette

s

Non

Lin

éaire

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

Page 135: Le format de compression JPEG ou comment les mathématiques

Com

pét

itio

nde

bas

es

Lin

éaire

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

1024

Fourier

Ondel

ette

s

Non

Lin

éaire

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

0100

200

300

400

500

600

700

800

900

1000

−30

−20

−100

10

20

30

40

50

Page 136: Le format de compression JPEG ou comment les mathématiques

Ondel

ette

s2D

Page 137: Le format de compression JPEG ou comment les mathématiques

Ondel

ette

s2D

Const

ruct

ion

sim

ilaire

mais

bid

imen

sionnel

le.

Page 138: Le format de compression JPEG ou comment les mathématiques

Ondel

ette

s2D

Const

ruct

ion

sim

ilaire

mais

bid

imen

sionnel

le.

Page 139: Le format de compression JPEG ou comment les mathématiques

Ondel

ette

s2D

Const

ruct

ion

sim

ilaire

mais

bid

imen

sionnel

le.

Page 140: Le format de compression JPEG ou comment les mathématiques

Ondel

ette

s2D

Const

ruct

ion

sim

ilaire

mais

bid

imen

sionnel

le.

Page 141: Le format de compression JPEG ou comment les mathématiques

Ondel

ette

s2D

Const

ruct

ion

sim

ilaire

mais

bid

imen

sionnel

le.

Gra

nds

coeffi

cien

tsco

rres

ponden

taux

conto

urs

.

Page 142: Le format de compression JPEG ou comment les mathématiques

JP

EG

vs

JP

EG

2000

Page 143: Le format de compression JPEG ou comment les mathématiques

JP

EG

vs

JP

EG

2000

Changem

ent

de

base

(Fourier

/O

ndel

ette

s)et

quantifica

tion.

Page 144: Le format de compression JPEG ou comment les mathématiques

JP

EG

vs

JP

EG

2000

Changem

ent

de

base

(Fourier

/O

ndel

ette

s)et

quantifica

tion.

Codage

sans

per

tede

ces

coeffi

cien

ts.

Page 145: Le format de compression JPEG ou comment les mathématiques

JP

EG

vs

JP

EG

2000

Origin

ale

JPEG

JPEG

2000

Changem

ent

de

base

(Fourier

/O

ndel

ette

s)et

quantifica

tion.

Codage

sans

per

tede

ces

coeffi

cien

ts.

Page 146: Le format de compression JPEG ou comment les mathématiques

Et

aprè

s

Page 147: Le format de compression JPEG ou comment les mathématiques

Et

aprè

s

Pro

blè

me

clos?

Page 148: Le format de compression JPEG ou comment les mathématiques

Et

aprè

s

Pro

blè

me

clos?

Codage

sans

per

te:pre

que

OU

Im

ais

codage

sourc

e/ca

nal.

Page 149: Le format de compression JPEG ou comment les mathématiques

Et

aprè

s

Pro

blè

me

clos?

Codage

sans

per

te:pre

que

OU

Im

ais

codage

sourc

e/ca

nal.

Modél

isation

:N

ON

.

Page 150: Le format de compression JPEG ou comment les mathématiques

Et

aprè

s

Pro

blè

me

clos?

Codage

sans

per

te:pre

que

OU

Im

ais

codage

sourc

e/ca

nal.

Modél

isation

:N

ON

.

Tra

nsf

orm

ation

:N

ON

.

Page 151: Le format de compression JPEG ou comment les mathématiques

Et

aprè

s

Pro

blè

me

clos?

Codage

sans

per

te:pre

que

OU

Im

ais

codage

sourc

e/ca

nal.

Modél

isation

:N

ON

.

Tra

nsf

orm

ation

:N

ON

.

Vid

éo,Sons.

..

Page 152: Le format de compression JPEG ou comment les mathématiques

Géo

mét

rie

Page 153: Le format de compression JPEG ou comment les mathématiques

Géo

mét

rie

Car

act

éristique

des

images

natu

relle

s.

Page 154: Le format de compression JPEG ou comment les mathématiques

Géo

mét

rie

Car

act

éristique

des

images

natu

relle

s.

Inutilis

éedans

les

repré

senta

tions

pré

céden

tes.

Page 155: Le format de compression JPEG ou comment les mathématiques

Géo

mét

rie

Car

act

éristique

des

images

natu

relle

s.

Inutilis

éedans

les

repré

senta

tions

pré

céden

tes.

Apport

théo

rique

pré

visible

.

Page 156: Le format de compression JPEG ou comment les mathématiques

Géo

mét

rie

Car

act

éristique

des

images

natu

relle

s.

Inutilis

éedans

les

repré

senta

tions

pré

céden

tes.

Apport

théo

rique

pré

visible

.

Direc

tion

de

rech

erch

eact

uel

le:cu

rvel

ets,

edgel

ets,

wed

gel

ets,

ondel

ette

sgéo

mét

riques

,bandele

ttes..

.

Page 157: Le format de compression JPEG ou comment les mathématiques

Ban

del

ette

s

Page 158: Le format de compression JPEG ou comment les mathématiques

Ban

del

ette

s

Fourier

Base

Page 159: Le format de compression JPEG ou comment les mathématiques

Ban

del

ette

s

Fourier

Ondel

ette

s

Base

Multié

chel

le

Page 160: Le format de compression JPEG ou comment les mathématiques

Ban

del

ette

s

Fourier

Ondel

ette

sB

andel

ette

s

Base

Multié

chel

leG

éom

étrie

Page 161: Le format de compression JPEG ou comment les mathématiques

Ban

del

ette

s

Fourier

Ondel

ette

sB

andel

ette

s

Base

Multié

chel

leG

éom

étrie

Coût

:ch

oix

de

lagéo

mét

rie.

Page 162: Le format de compression JPEG ou comment les mathématiques

Ban

del

ette

s

Fourier

Ondel

ette

sB

andel

ette

s

Base

Multié

chel

leG

éom

étrie

Coût

:ch

oix

de

lagéo

mét

rie.

Alg

orith

me

rapid

epour

cech

oix

.

Page 163: Le format de compression JPEG ou comment les mathématiques

Ban

del

ette

s

Fourier

Ondel

ette

sB

andel

ette

s

Base

Multié

chel

leG

éom

étrie

Coût

:ch

oix

de

lagéo

mét

rie.

Alg

orith

me

rapid

epour

cech

oix

.

Tra

vail

de

rech

erch

esu

rl’optim

alit

éde

lam

éthode.

Page 164: Le format de compression JPEG ou comment les mathématiques

Ban

del

ette

s

Fourier

Ondel

ette

sB

andel

ette

s

Base

Multié

chel

leG

éom

étrie

Coût

:ch

oix

de

lagéo

mét

rie.

Alg

orith

me

rapid

epour

cech

oix

.

Tra

vail

de

rech

erch

esu

rl’optim

alit

éde

lam

éthode.

Implé

men

tation

sans

optim

isation

fine.

Page 165: Le format de compression JPEG ou comment les mathématiques

Origin

ale

Disto

rsio

n-D

ébit

0.2

0.4

0.6

0.8

1

30

32

34

36

38

40

PSNR

R/N2

Ondele

ttes

Bandele

ttes

R/N2=0,22

bpp

Bandel

ette

s(33,05

db)

Ondel

ette

s(32,54

db)

Page 166: Le format de compression JPEG ou comment les mathématiques

Origin

ale

Bandel

ette

sO

ndel

ette

s

Page 167: Le format de compression JPEG ou comment les mathématiques

Modèl

esp

écia

lisé

Page 168: Le format de compression JPEG ou comment les mathématiques

Modèl

esp

écia

lisé

Com

pre

ssio

nsp

écia

lisée

pour

les

visa

ges

.

Page 169: Le format de compression JPEG ou comment les mathématiques

Modèl

esp

écia

lisé

Com

pre

ssio

nsp

écia

lisée

pour

les

visa

ges

.

500

oct

ets

=fa

cteu

r400

de

com

pre

ssio

n!

Page 170: Le format de compression JPEG ou comment les mathématiques

Modèl

esp

écia

lisé

Com

pre

ssio

nsp

écia

lisée

pour

les

visa

ges

.

500

oct

ets

=fa

cteu

r400

de

com

pre

ssio

n!

Com

par

aison

de

diff

éren

tsalg

orith

mes

.

Page 171: Le format de compression JPEG ou comment les mathématiques

Modèl

esp

écia

lisé

JPEG

Com

pre

ssio

nsp

écia

lisée

pour

les

visa

ges

.

500

oct

ets

=fa

cteu

r400

de

com

pre

ssio

n!

Com

par

aison

de

diff

éren

tsalg

orith

mes

.

Page 172: Le format de compression JPEG ou comment les mathématiques

Modèl

esp

écia

lisé

JPEG

JPEG

-2000

Com

pre

ssio

nsp

écia

lisée

pour

les

visa

ges

.

500

oct

ets

=fa

cteu

r400

de

com

pre

ssio

n!

Com

par

aison

de

diff

éren

tsalg

orith

mes

.

Page 173: Le format de compression JPEG ou comment les mathématiques

Modèl

esp

écia

lisé

JPEG

JPEG

-2000

Let

ItW

ave

Com

pre

ssio

nsp

écia

lisée

pour

les

visa

ges

.

500

oct

ets

=fa

cteu

r400

de

com

pre

ssio

n!

Com

par

aison

de

diff

éren

tsalg

orith

mes

.

Page 174: Le format de compression JPEG ou comment les mathématiques

Modèl

esp

écia

lisé

JPEG

JPEG

-2000

Let

ItW

ave

Com

pre

ssio

nsp

écia

lisée

pour

les

visa

ges

.

500

oct

ets

=fa

cteu

r400

de

com

pre

ssio

n!

Com

par

aison

de

diff

éren

tsalg

orith

mes

.

Clé

:sp

écia

lisation.

Page 175: Le format de compression JPEG ou comment les mathématiques

Vid

éos

etso

ns

Page 176: Le format de compression JPEG ou comment les mathématiques

Vid

éos

etso

ns

Page 177: Le format de compression JPEG ou comment les mathématiques

Vid

éos

etso

ns

Mêm

esprinci

pes

s’appliq

uen

t!

Page 178: Le format de compression JPEG ou comment les mathématiques

Vid

éos

etso

ns

Mêm

esprinci

pes

s’appliq

uen

t!

Vid

éos

:utilis

ation

de

lare

dondance

tem

pore

lle(M

PEG

2,M

PEG

4,.

..).

Page 179: Le format de compression JPEG ou comment les mathématiques

Vid

éos

etso

ns

Mêm

esprinci

pes

s’appliq

uen

t!

Vid

éos

:utilis

ation

de

lare

dondance

tem

pore

lle(M

PEG

2,M

PEG

4,.

..).

Sons

:utilis

ation

de

modèl

esauditifs

(MP3,.

..).

Page 181: Le format de compression JPEG ou comment les mathématiques

Concl

usi

on

Panora

ma

de

laco

mpre

ssio

nd’im

age.

Page 182: Le format de compression JPEG ou comment les mathématiques

Concl

usi

on

Panora

ma

de

laco

mpre

ssio

nd’im

age.

Les

math

ématiques

serv

ent

(par

fois)

àquel

que

chose

!

Page 183: Le format de compression JPEG ou comment les mathématiques

Concl

usi

on

Panora

ma

de

laco

mpre

ssio

nd’im

age.

Les

math

ématiques

serv

ent

(par

fois)

àquel

que

chose

!Les

math

sso

nt

par

tout!

Page 184: Le format de compression JPEG ou comment les mathématiques

Concl

usi

on

Panora

ma

de

laco

mpre

ssio

nd’im

age.

Les

math

ématiques

serv

ent

(par

fois)

àquel

que

chose

!Les

math

sso

nt

par

tout!

On

peu

ts’

am

use

ren

faisant

de

lasc

ience

!

Page 185: Le format de compression JPEG ou comment les mathématiques

Concl

usi

on

Panora

ma

de

laco

mpre

ssio

nd’im

age.

Les

math

ématiques

serv

ent

(par

fois)

àquel

que

chose

!Les

math

sso

nt

par

tout!

On

peu

ts’

am

use

ren

faisant

de

lasc

ience

!

Plu

sd’info

s:

[email protected]

http://www.math.jussieu.fr/~lepennec

Page 186: Le format de compression JPEG ou comment les mathématiques

Concl

usi

on

Panora

ma

de

laco

mpre

ssio

nd’im

age.

Les

math

ématiques

serv

ent

(par

fois)

àquel

que

chose

!Les

math

sso

nt

par

tout!

On

peu

ts’

am

use

ren

faisant

de

lasc

ience

!

Plu

sd’info

s:

[email protected]

http://www.math.jussieu.fr/~lepennec

En

par

ticu

lier

des

pré

senta

tions

etun

articl

ede

vulg

arisat

ion

sur

la

com

pre

ssio

n.