# Gnral Dveloppement > Algorithme & Mathmatiques > Traitement d'images >  interpolation bicubique : help

## ale2000

Bonjour,

c'est encore moi qui revient avec mes interpolations.
Afin de raliser une mesure plus prcise, je veux finallement passer par une interpolation bicubique de ma recherche de contour.
Pour prciser le besoin :
  je dois calculer le rayon de 2 cercles concentriques et ce, tous les 15 degrs et de manire hyper prcise. 

donc, la premire chose que je fais est de rechercher le centre de la pice ainsi que les points de contours qui m'intresse (intercection entre les cercle et les rayons tous les 15.

Ds que j'ai ces points, j'avais fait une interpolation bilinaire afin d'avoir plus de prcision.

premire question, sur les rayons horizontaux et verticaux, l'interpolation que j'utilise est linaire (pas besoin des 2 axes) et c'est OK, mais pour mon point  15 par exemple, qui se trouve en (x,y) je le calcul avec la valeur des points (x,y), (x+1, y), (x, y-1) et (x+1, y-1)
Est-ce que c'est logique pour un point qui est sur une courbe ?

deuxime question, comme dit dans le prcdant post, cette interpolation me permet d'avoir une prcision au 1/10 de pixel. Pseudocode m'a signal qu'il avait post l'interpolation bicubique. Merci, mais quelqu'un pourait-il m'expliquer, avec des mots simples (ben oui, pas trs malin moi) comment cette interpolation permet d'avoir une plus grande prcision et comment je peux calculer, au sein de mon pixel, la recherche de la transition fond/objet avec plus de prcision grace  cet outil.


merci d'avance

----------


## souviron34

bah de manire TRES simple (voire simpliste  :;):  ) :

on approxime par un polynme de degr 2 (une cubique :hyperbole, parabole,  ...) : on a donc quelque chose de nettement plus "souple" et raliste qu'une approximation linaire..
Et comme c'est en 2d, c'est... N (4 ??) fois plus prcis... Mais c'est surtout que c'est plus "physique" : 

si tu as quelque chose comme un dbut de "sinus", disons quelque chose qui dmarre lentement puis varie plus vite,mais que tu es DANS l'intervalle, une approximation linaire sera pas mal fausse au dbut, puis pas mal en dessous  la fin.. Si c'est cubique tu seras nettement plus prs de la "vraie" variation...

----------


## pseudocode

Une autre maniere de le voir:

- l'interpolation bilinaire prend en compte seulement les valeurs voisines

- l'interpolation bicubique prend en compte les valeurs voisines et leurs variations (derive)

----------


## ale2000

Donc, si j'ai bien compris, L'interpolation bilinaire permet de calculer, au sein d'un pixel, la variation de son intensit en fonction de sa propre intensit et celle de ses voisin, un genre de moyenne linaire en somme sur les axes X et Y.

L'interpolation bicubique ralise la mme chose mais en prenant en compte de l'interaction des uns par rapport aux autre  ::P:  

Pouvez-vous, svp, rpondre aux reste deux questions poses dans le premier post. Dsol d'tre aussi insistant, mais un projet important pour moi en dpend ...

----------


## pseudocode

> L'interpolation bicubique ralise la mme chose mais en prenant en compte de l'interaction des uns par rapport aux autre


Yes. une petite demo:

http://www.molecularexpressions.com/...oom/index.html




> Pouvez-vous, svp, rpondre aux reste deux questions poses dans le premier post.





> pour mon point  15 par exemple, qui se trouve en (x,y) je le calcul avec la valeur des points (x,y), (x+1, y), (x, y-1) et (x+1, y-1)
> Est-ce que c'est logique pour un point qui est sur une courbe


Quel courbe ? 




> comment je peux calculer, au sein de mon pixel, la recherche de la transition fond/objet avec plus de prcision grace  cet outil.


Recherche du maxima du gradient => chercher le zero de la derive 2nde (laplacien). On obtient une meilleure approximation du "zero-crossing" avec une interpolation bicubique puisqu'on tient compte des variations d'intensit en plus des valeurs d'intensit.

----------


## ale2000

Merci pour la dmo, trs parlant...

j'entend par 'courbe' le cercle sur lequel se trouve le point d'intercection entre la droite de 15 passant par le centre et le cercle lui-mme

Pour ce qui est de plus de prcision, j'ai bien compris, mais je ne sais pas comment m'y prendre en fait, pour ce qui est du bilinaire je fais :
Exemple :

soit 4 pixels

100 150   y+1
175 200   y
 x     x+1

pour trouver la valeur interpole en (x+0.7, y+0.2) voir fichier ci-joint.



Donc, pour trouver les valeur dans mon pixel, je n'ai qu'a faire varier les X' et Y' jusqu' dpassement d'un seuil.


je ne vois pas comment raliser ceci avec l'interpolation bicubique...

----------


## ale2000

Oups, je viens de faire tilt, en fait, et vous me dites si je me trompe, mais pour l'interpolation bicubique je dois faire de la mme manire que pour l'interpollation bilinaire  ceci prs que l'interpolation bilinaire je dois la faire par pas de 0.1 (donc de x  x+0.9) car plus petit ne m'offre pas plus de prcision tandis qu'avec l'interpolation bicubique je peux faire de x  x+0.999)

par contre, je n'ai pas de solution pour mon premier problme (question 1)

----------


## pseudocode

> Oups, je viens de faire tilt, en fait, et vous me dites si je me trompe, mais pour l'interpolation bicubique je dois faire de la mme manire que pour l'interpollation bilinaire  ceci prs que l'interpolation bilinaire je dois la faire par pas de 0.1 (donc de x  x+0.9) car plus petit ne m'offre pas plus de prcision tandis qu'avec l'interpolation bicubique je peux faire de x  x+0.999)


heu... oui et non  ::aie:: . L'interpolation bicubique n'offre pas "plus" de prcision. C'est juste une prcision differente. En fait ce n'est meme pas une "prcision" mais une "estimation".

Si j'ai bien compris, ta methode de detection consiste a avancer le long des rayons du cercle et a chercher un depassement de seuil dans les intensits.

Exemple: Mettons que le fond soit a 0 et le cercle recherch a 255, tu avances le long du rayon et tu t'arretes quand l'intensit depasse 128. La distance parcouru te donne le rayon de ton cercle.

Dans ce cas, meme en interpolant les valeurs tu n'auras jamais une prcision meilleur que 1 pixel (le cas ideal)

Dans le cas "ideal" (Fond=0, Cercle=255) il y a un seul changement brutal 0->255.  Dans ce cas, tout ce qu'on peut dire c'est que le cercle commence quelquepart entre les 2 pixels de changement. La precision est donc d'1 pixel, ce qui est le max possible.

Dans les cas "rels" les valeurs sont bruits et echantillones, ce qui donne une transition (0+bruit) -> (255+bruit) progressive sur quelques pixels consecutifs: ...,1,0,3,0,22,61,112,201,248,255,251,255,254...

Dans ce cas, le mieux a faire est de se ramenner au cas "idal" en filtrant le signal et en cherchant le "milieu" de la transition. Mais ca ne te donne pas pour autant une prcision meilleur que le cas ideal.

----------


## ale2000

La dmarche est bien celle que je suit.
Ce n'est pas le cas idal que j'ai (qui n'offrirait justement pas assez d'informations) mis bien le cas rel.

J'ai fait pas mal de recherche sur ce point, et l'effet "d'estimation" permet justement une dtection plus prcise.
au niveau tests, bcp de recherches ont prouvs qu'en interpollant (bicubique) il y avait moyen d'avoir des prcisions jusqu' 1/1000 de pixel !!!
Des mesures sur des micro fissures  l'aide de camra matrice 480*640 permette des prcisions au 1/1000 de mm pour un carr de 40mm*40mm

Pas mal non...

----------


## pseudocode

> La dmarche est bien celle que je suit.
> Ce n'est pas le cas idal que j'ai (qui n'offrirait justement pas assez d'informations) mis bien le cas rel.
> 
> J'ai fait pas mal de recherche sur ce point, et l'effet "d'estimation" permet justement une dtection plus prcise.


Ah ok. C'est donc une estimation statistique. La "courbe" d'intensit 0->255 est vue comme une fonction de rpartition 0->1.

Dans ce cas, je pense qu'il serait plus "juste" de filtrer cette courbe, de la modeliser et enfin de chercher ton seuil. Je pense qu'une loi normale devrait etre un bon debut.

----------


## ale2000

Waw, l tu me "squotche"
o vas-tu chercher tout ca ?

Bon, l je ne te sis plus.

J'essaye, je trouve donc une coure  partir de l'interpolation, jusque l... OK

la filtrer.. oui, pour supprimer le bruit ... OK

la modliser ... L, je ne te suis plus, j'ai regard la loi normale, mais j'avoue que je ne vois pas comment l'appliquer  ce que j'obtient  partir de l'interpolation...

Si tu peux m'aider je suis preneur...

----------


## pseudocode

lol. Oui je me suis un peu enflamm sur la theorie... bon, faisons plus simple.

Lorsque tu "avances" le long du rayon, la valeur que tu obtiens est "0+bruit" avant avant d'arriver au debut du cercle puis "255+bruit" apres avoir dpass le debut du cercle.

Maintenant, si on prend ca du cot "statistique", ca veut dire que si tu es dans une zone de "0+bruit" il y a de grandes chances que tu sois "avant le cercle". De meme si tu est dans une zone de "255+bruit" il y a de grandes chances que tu sois "aprs le cercle".

Ce qui nous interesse c'est d'estimer quand on est "juste sur le cercle". Donc si on est dans une des 2 zones "0+bruit" ou "255.bruit" la probabilit d'etre "juste sur le cercle" est proche de 0. 

C'est ce que modelise la loi normale. Le graphique en haut a droite de wikipedia represente cette probabilit: trs a gauche et trs a droite, les proba sont nulles. Ce qu'on cherche c'est le "pic" de proba maximum.

La therorie nous dit que ce "pic" de proba maximum est atteint quand la fonction de rpartiton (graphique du dessous) atteint 0.5.  Or, cette fonction de rpartiton ressemble etrangement (  :;):  ) a la courbe que tu mesures.

Donc, si tu peux filtrer/retailler ta courbe de mesure pour qu'elle corresponde  cette fonction de rpartiton, il suffira de chercher la postion "x" pour laquelle "y=0.5".  ::king::  

En premiere approche, modelise ta courbe pour qu'elle soit en 3 parties: 
x<xd -> horizontale y=0x>=xd & x<=xf -> lineaire y = a.x +bx>xf -> horizontale y=255
le but etant de trouver xd et xf, qui sont le debut et la fin de la zone lineaire (par exemple avec des seuils) puis a et b (par exemple avec une regression lineaire)

----------


## Danious

> Donc, si j'ai bien compris, L'interpolation bilinaire permet de calculer, au sein d'un pixel, la variation de son intensit en fonction de sa propre intensit et celle de ses voisin, un genre de moyenne linaire en somme sur les axes X et Y.
> 
> L'interpolation bicubique ralise la mme chose mais en prenant en compte de l'interaction des uns par rapport aux autre  
> 
> Pouvez-vous, svp, rpondre aux reste deux questions poses dans le premier post. Dsol d'tre aussi insistant, mais un projet important pour moi en dpend ...





> - l'interpolation bilinaire prend en compte seulement les valeurs voisines
> 
> - l'interpolation bicubique prend en compte les valeurs voisines et leurs variations (derive)


Je me trompe peut tre, mais l'interpolation bilinaire ne dsigne pas dj un calcul simple sur la drive premire?
Le fait qu'elle soit *bi*linaire ne dsigne pas juste le fait qu'elle soit faite sur 2 variables (comme dans une image o il y a 2 dimensions)?

Travailler sur la variation de la drive ne dsigne pas dans ce cas une interpolation quadratique (par la drive seconde) et non une interpolation cubique (drive 3me)?

Pour moi, une interpolation cubique consiste  utiliser 4 points pour trouver un polynme de degr 3 passant par ces points. C'est donc seulement la drive 3 de ce polynome qui est constante... Et faire une interpolation bicubique ncessite 4*4 points...

Encore une fois, c'est possible que je me trompe, mais il me semble bien que a marche comme a non?

----------


## pseudocode

> Pour moi, une interpolation cubique consiste  utiliser 4 points pour trouver un polynme de degr 3 passant par ces points. C'est donc seulement la drive 3 de ce polynome qui est constante... Et faire une interpolation bicubique ncessite 4*4 points...
> 
> Encore une fois, c'est possible que je me trompe, mais il me semble bien que a marche comme a non?


Oui, c'est exactement ca.  Quand je parlais de "drive" je n'ai pas spcifi l'ordre (1ere, 2nde, 3eme, ...)

L'interpolation cubique assure la continuit des valeurs et des drives 1ere et 2nde. A l'echelle de l'image la drive 3eme est constante "par morceaux".

----------


## yan

tu peut regarder 
http://www.nrbook.com/a/bookcpdf.php

il y as des parties sur les interpolations

(attention,faut avoir le plug in "FileOpen " pour adobe  ::?:  )

----------


## ale2000

Bonjour,

Merci pour ce lien, (j'avoue l'avoir dj lu)

Maintenant je comprend bien les interpollation et j'essaye de digrer les dernires remarques de pseudocode (sur la normale).
Je n'ai malheureusement pas bcp de temps et je n'arrive pas  en 'faire' pour crer un 'petit' programme qui me ferait cette interpolation bicubique suivie de l'application de la normale  x dimentions...

Je vous tiens au courant ds que ce sera fait..

----------


## pseudocode

ma remarque sur la "loi normale" etait une autre approche a ton probleme qui ne necessitait pas de passer par des interpolations (cubique ou autre).

----------


## ale2000

Oui, j'ai remarqu la btise de ma rponse il y a peu...
Mais j'avoue n'avoir plus qu'un trs lointain souvenir de la loi normale...

J'avoue n'avoir aucune ide  comment interprter cela par rapport  des pixel...

----------


## pseudocode

il faut deja que tu regardes la courbe Intensite / position le long du rayon.

C'est a dire que tu construits un tableau a une dimension dans lequel tu stocke les valeurs que tu rencontres en partant du centre du cercle et en suivant un des rayons.

Donc, normalement tu as dans ce tableau:

au debut: que des valeurs proches de zero (je considere que le fond est noir=0)

a la fin: que des valeurs proches de 255 (je considere que ton objet est blanc=255)

quelquepart au milieu:  une transition (+/- lineaire) de noir=0 a a blanc=255

Si deja tu obtiens ca, c'est un bon debut.  ::P:

----------


## ale2000

OK, jusque l, c'est dj programm.
Le calcul avec formule du cercle me permet d'avoir un point approximatif sur le cercle dans un angle donn et je connais le centre -> les deux donnes me permette d'avoir l'quation d'une droite.

----------


## pseudocode

> OK, jusque l, c'est dj programm.
> Le calcul avec formule du cercle me permet d'avoir un point approximatif sur le cercle dans un angle donn et je connais le centre -> les deux donnes me permette d'avoir l'quation d'une droite.


ok, mais est-ce que les valeurs obtenues en parcourant cette droite ressemblent a une sigmoide ?

----------


## ale2000

Au bruit prs, oui, c'est tout  fait cela.
Sauf que j'en ai plusieurs qui se suivent car l'image d'origine est un ensemble de disque inclus les uns aux autres.
Mais localement, j'ai bien cela.

----------


## pseudocode

bien... maintenant:

1. decoupage de la courbe sigmoide par sigmoide (a chaque fois qu'il y a une transition 255->0)

2. pour chaque sigmoide, on recherche les 2 parties constantes (=0 et =255) et la partie du milieu (transition).

2a. On part de la gauche (x=0 et on s'arrete des que la courbe depasse un seuil (par exemple 10% = 25). On appelle ce point d'arret "xd"

2b. On part de la droite (x=max) et on s'arrete des que la courbe descend sous un seuil (par exemple 90% = 230). On appelle ce point d'arret "xf"

2c. On extrait les points entre xd et xf -> on obtient une liste de couple (x,y)

2d. On fait une regression lineaire sur tous ces points -> on obtient l'equation de la meilleure droite passant par ces points: Y = a.X + b

2e. on cherche le point X tel que Y=128

Fini !  ::mrgreen::

----------


## ale2000

En effet, c'est tout simple.

Mais, dans ce cas, je me retrouve avec une estimation liniare par rapport aux voisins. Ca revient  faire une interpolation linaire mais avec plus de voisins si je ne me trompe ?

Donc, dans ce cas, est-ce que l'interpolation bicubique avec 16 voisins ne sera pas plus 'prcise' dans l'estimation, car elle tient compte de la prvision en Y ?

J'ai encore une question, par rapport  la bilinaire.
Lorsque j'essaye de trouv l'interpollation d'un point sur le cercle  0, les points  prendre en compte sont :

(x,y-1)  , (x+1,y-1)
(x,y)     , (x+1, y)

maitenant, si j'esssaye de faire cette interpollation sur une le point d'intercection entre le cercle et une droite  15 passant par le centre, le point (x,y), correspond  ma transition, mains que prendre comme autre points ? faut il les calculer ./.  des parallle  mon rayon ou ???

----------


## pseudocode

> En effet, c'est tout simple.
> 
> Mais, dans ce cas, je me retrouve avec une estimation liniare par rapport aux voisins. Ca revient  faire une interpolation linaire mais avec plus de voisins si je ne me trompe ?
> 
> Donc, dans ce cas, est-ce que l'interpolation bicubique avec 16 voisins ne sera pas plus 'prcise' dans l'estimation, car elle tient compte de la prvision en Y ?


Non, c'est different d'une interpolation. 

Dans la methode dcrite ci-avant, on ne s'interesse pas au valeurs des pixels. Ce qui nous interesse c'est la "rpartition" de ces valeurs. 

Avoir des valeurs plus precise ne va pas "beaucoup" changer l'equation de la droite. On peut meme dire que les bruits sur les valeurs se compensent (bruit blanc -> moyenne nulle). 

Dans cette methode, ce qui est vraiment important c'est d'avoir des points. Plus on a de points, meilleure est la modelisation.




> maitenant, si j'esssaye de faire cette interpollation sur le point d'intercection entre le cercle et une droite  15 passant par le centre, le point (x,y), correspond  ma transition, mains que prendre comme autre points ? faut il les calculer ./.  des parallle  mon rayon ou ???


Heu, j'ai pas tout compris...  ::aie::  

L'interpolation sert a estimer la valeur d'un point(x,y), ou x et y ne sont pas des nombres entiers, par exemple x=2.52 et y=4.75. 

Dans ce cas, il faut prendre les points (entiers) qui entourent le point a estimer. Dans notre exemple ca serait : (2,4) (3,4) (2,5) et (3,5)

----------


## ale2000

J'avais bien compris la diffrence, mais ce sont toutes les deux des oprations linaire ...

Sinon, pour la question, voici un petit shmas



Donc, si je veux calculer l'interpolation bilinaire pour le point (X1,Y1) je dois prendre les points :
(x1,y1-1) , (x1+1,y1-1)
(x1,y1) , (x1+1, y1)

Par contre, si je veux calculer l'interpolation bilinaire pour le point (X2,Y2) et si je suis la logique, je dois prendre les points :
(x2,y2-1) , (x2+1,y2-1)
(x2,y2) , (x2+1, y2)

Ce qui ne me parat pas trs 'optimal' car je ne suis pas dans le sens de ma droite (rayon)

----------


## pseudocode

> J'avais bien compris la diffrence, mais ce sont toutes les deux des oprations linaire ...


Heu.. oui. Ce sont deux oprations linaires.

Mais si tu veux, tu peux "fitter" la courbe sur autre chose qu'une droite: une sigmoide, la fonction de rpartition de la loi normale, ... Mais les calculs vont etre plus chauds....




> ... Donc, si je veux calculer l'interpolation bilinaire pour le point (X1,Y1) ...
> 
> ... si je veux calculer l'interpolation bilinaire pour le point (X2,Y2) ...


je me rpte:




> L'interpolation sert a estimer la valeur d'un point(x,y), ou x et y ne sont pas des nombres entiers


Si (X1,Y1) et (X2,Y2) sont des coordonnes entiere, il n'y a rien a interpoler.

----------


## ale2000

OK,
Ce que je veux, c'est calculer l'interpollation pour le point (X,Y) avec x = x+0  x+0.9 et Y+0  Y+0.9

mais pour interpoller, on prend 4 voisins, et ces sur ces 4 voisins que porte ma question ?

----------


## pseudocode

> OK,
> Ce que je veux, c'est calculer l'interpollation pour le point (X,Y) avec x = x+0  x+0.9 et Y+0  Y+0.9
> 
> mais pour interpoller, on prend 4 voisins, et ces sur ces 4 voisins que porte ma question ?


je suppose que tu veux dire:

"le point (u,v) avec x<=u<x+1 et y<=v<y+1 et x,y entiers"

Dans ce cas, il faut prendre les points "entourant" qui ont des coordonnes entieres. 

Pour une interpo bilineaire avec 4 voisins: (x,y) (x+1,y) (x+1,y+1) (x,y+1)

----------


## ale2000

Oui, c'est bien ce que j'avais mis, mais ca me parat trange de ne pas sivre le sens de la droite...


En tout cas, merci beaucoup pour l'aide, je vais tudier toutes les pistes et voir ce qui donne le meilleur rsultat.

----------


## pseudocode

::lahola::  

et bon courage...

----------

