15

Agrandissement bilinéaire: Le retour

juil

Il y a quelques temps j’avais proposé un algorithme d’interpolation bilinéaire permettant l’agrandissement d’une image dont les performances quoique correctes m’avaient un peu déçues.

J’ai finalement trouvé une solution pour booster significativement la performance de l’algorithme.
Mais le plus intéressant est sans doute la technique en elle-même, qui permet de coupler les deux unités de calculs que sont l’ARM et NEON

Rappel: Interpolation sur l’axe des X

Le problème pour interpoler sur l’axe des X réside dans la fait que NEON est plutôt doué pour réaliser des opérations identiques sur des données consécutives.
Hors sur l’axe des X, les données ne se suivent pas “régulièrement” et les coefficients changent pour tous les pixels.
Pour représenter le problème sous forme de code, il faut réussir à exécuter (et surtout paralléliser) le code suivant

for (j = 0 ; j < width ; j++)
	pixel_dst[j] = pixel[i] * coef[j] + pixel[i + 1] * (1 - coef[j]);

Sauf que la parallélisation pose quelques problème puisque:

  • i ne peut pas être calculé (simplement) à partir de j et surtout ne suit pas la même progression que j. Si bien qu'au mieux il faudrait faire des chargements de registre 32 bits. Hors NEON n'est pas très doué pour ça !
  • Le coefficient "coef" change pour chaque valeur de j et donc doit être calculé avant d'être chargé dans des registres NEON

Même si avec toute la bonne volonté du monde, si on tentait d'utiliser NEON pour interpoler, on aurait des résultats inférieurs à la version avec transposition que j'ai déjà proposée.

La solution, c'est d'utiliser NEON et l'ARM en même temps.

On va charger les registres NEON non pas grâce à des instructions d'accès mémoire NEON, mais grâce à des VMOV !!!
Les lectures de pixel[i] seront donc faite par l'ARM qui est assez doué pour lire des 32 bits (contrairement à NEON), puis seront poussés dans les registres NEON.
L'ARM et NEON pouvant fonctionner en parallèle, le temps de calcul de i sera perçu comme nul puisqu'il se fera en même temps que le traitement NEON.

Pour les coefficients, on va les pré-calculer, car s'ils changent à pour chaque pixel d'une ligne, ils sont quand même identiques pour chaque ligne.
Un Load sera nettement plus efficace que de tenter de calculer au cours de l'itération leur valeur.

Comme l'ARM fonctionne en même temps que NEON, tout cela va aller très vite et permettre d'obtenir des performances assez importantes !

Pré calcul des coefficients

C'est parti!

strech_x:
@ r0 = width src
@ r1 = height src
@ r2 = width dst
@ r3 = height dst
@ [sp] = *src
@ [sp] = *dst

	push			{r4-r11, lr}						@ saving all registers

	push			{r0-r3, r14}
	sub			r0, r0, #1							@ wSrc - 1
	sub         r1, r2, #1							@ wDst - 1
	lsl         r0, r0, #16							@ wSrc * 65536
	bl				udiv
	mov			r5, r0								@ r5 = wStepFixed16b (fixed 16bit)
	pop			{r0-r3, r14}
	mov			r4, #0								@ r4 = wCoef

Bon tout d’abord on sauve tous les registres, car on va tous les utiliser, y compris r14 (lr) et r13 (sp).
Puis on calcule le delta en X qu’il va nous permettre de calculer le coefficient suivant à partir du précédent.

r5 contient notre fameux delta stocké sous la forme d’un flottant (fixe 16bit) dont la partie entière utilise les 16bits haut du registre et le partie flottante le 16 bit bas.
Pour info, dans le cadre d’un agrandissement, ce delta est toujours inférieur à 1.

r4 enfin est notre accumulateur de delta.

On va pré-calculer les coefficients 2 par deux (pour une raison d’optimisation principalement).
Désolé pour la complexité que ça engendre pour lire le code, mais je n’ai pas le courage de ré-écrire ce code en version plus simple.

	movw        r14, #:lower16:.bilinear_x_coef
	movt        r14, #:upper16:.bilinear_x_coef
	movw        r7, #0x8080
	movt        r7, #0x8080

	ubfx			r12, r4, #9, #7					@ hc2 = (wCoef >> 9) & 127;
	add			r4, r4, r5
	ubfx			r10, r4, #9, #7					@ hc2 = (wCoef >> 9) & 127;
	add			r4, r4, r5			

	add			r12, r12, r12, lsl #8
	add			r10, r10, r10, lsl #8
	add			r12, r12, r12, lsl #16
	add			r10, r10, r10, lsl #16
	rsb			r11, r12, r7						@ hc1 = 128 - hc2;
	rsb			r9, r10, r7							@ hc1 = 128 - hc2;

	mov			r8, r2
.precal_offset:
	vmov			d31, r12, r10
	vmov			d30, r11, r9

	ubfx			r12, r4, #9, #7					@ hc2 = (wCoef >> 9) & 127;
	add			r4, r4, r5
	ubfx			r10, r4, #9, #7					@ hc2 = (wCoef >> 9) & 127;
	add			r4, r4, r5			

	add			r12, r12, r12, lsl #8
	add			r10, r10, r10, lsl #8
	add			r12, r12, r12, lsl #16
	add			r10, r10, r10, lsl #16
	rsb			r11, r12, r7						@ hc1 = 128 - hc2;
	rsb			r9, r10, r7							@ hc1 = 128 - hc2;

	vst1.u32		{q15}, [r14:128]!
	subs			r8, r8, #2
	bne			.precal_offset

r14 va contenir un pointeur sur la table ou nous allons enregistrer nos coefficients précalculés.
r7 contient 128 dans chacun des octets du registre afin de pouvoir calculer le deuxième coefficient.
Comme on travaille avec des coefficients entier sur 7 bit, coef2 = 128 – coef1

Alors pour aider à la compréhension:
r12 contient coef[j] du premier pixel
r11 contient (128 – coef[j]) du premier pixel
r10 contient coef[j + 1] du pixel suivant
r9 contient (128 – coef[j + 1]) du pixel suivant

On calcul donc bien les coefficients 2 par 2, ce qui rappelons-le n’est pas une nécessité.

Les 4 instructions

	add			r12, r12, r12, lsl #8
	add			r10, r10, r10, lsl #8
	add			r12, r12, r12, lsl #16
	add			r10, r10, r10, lsl #16

permettent de dupliquer les coefficients sur chaque octets des registres, car ils seront utilisés sur chaque composante ARGB de nos pixels. Et évidement pour chaque composante, on utilise les mêmes coefficients.

Pour finir on utilise NEON pour stocker ces données pré-calculées, ce qui permet de les enregistrer en 1 seul cycle !!!
On aurait pu se passer de NEON, mais bon.. Un cycle est un cycle.

Donc au final, si votre image destination fait X pixels de large, nous avons pré-calculé X coefficients (7bits) lesquels sont dupliqués 4 fois pour traiter toutes les composantes d’un coup.
A présent NEON pourra obtenir les coefficients à appliquer en faisant un simple accès mémoire. Ce qui résout un de nos deux problèmes.

Calcul des Offset

A présent il faut nous occuper de calculer les Offset (i dans le code initial). C’est à dire calculer pour chaque valeur de j quels sont les pixels qui vont être utilisé pour interpoler.
Ces Offsets auraient eux aussi pu être pré-calculés, Mais du coup, l’ARM aurait du faire deux accès mémoire pour chaque pixel. Le premier pour aller lire l’offset, le deuxième pour aller lire le pixel.
Pour être honnête, je n’ai pas testé le pré-calcul, je me suis dit que si j’arrive à les calculer en moins de temps qu’il n’en faut à NEON pour, de son côté, réaliser l’interpolation alors cela n’avait aucun intérêt. Cela aurait juste augmenté le nombre d’accès mémoire.

Donc je vous donne ici une version non optimisée afin qu’elle soit lisible du couplage de l’ARM et de NEON.
Garder à l’esprit que:

  • L’arm calcul l’offset, puis lit le pixel et enfin le transfert vers NEON
  • NEON s’occupe des calculs d’interpolations et de l’enregistrement des résultats
	ldr			r10, [sp, #36]
	ldr			r11, [sp, #40]
	lsl			r5, r5, #16

.strech_x_loop_y:
	mov			r8, r10								@ r8 = ptr Src
	mov			r4, #0								@ r4 = wCoef

	movw        r14, #:lower16:.bilinear_x_coef
	mov			r12, r2
	movt        r14, #:upper16:.bilinear_x_coef
	mov			r9, r11								@ r9 = ptr Dst

.strech_x_loop_x:
	ldr			r6, [r8]								@ on charge q1 (d0-d1)
	adds			r4, r4, r5
	ldr			r7, [r8, #4]
	addcs			r8, r8, #4
	vmov			s0, r6
	vmov			s2, r7
	ldr			r6, [r8]
	adds			r4, r4, r5
	ldr			r7, [r8, #4]
	addcs			r8, r8, #4
	vmov			s1, r6
	vmov			s3, r7

	vld1.s32		{q12}, [r14:128]!					@ on lit les coefs

	vmull.u8		q4, d0, d24							@ pixel1 * (1 - coef)
	vmlal.u8		q4, d1, d25							@ + pixel2 * coef

	vqrshrn.u16 d16, q4, #7							@ reduce to 8 bit

	pld			[r8, #512]
	vst1.32		{q8-q9}, [r9:128]!					@ write result

	subs			r12, r12, #2
	bne			.strech_x_loop_x

	add			r10, r10, r0, lsl #2
	add			r11, r11, r2, lsl #2

	subs			r1, r1, #1
	bne			.strech_x_loop_y

	pop			{r4-r11, pc}			@ saving all registers

Alors !!!

Tout d’abord on charge dans r10 et r11 les pointeurs source et destination. A ce moment on a toujours le droit d’utiliser r13 puisqu’on ne l’a pas encore modifié !!
Notre registre r5, qui contient notre delta, va quant à lui être décalé de 16 bit. Ainsi il ne nous reste plus que la partie flottante du delta dans ce registre.

r8 et r9 seront les registres pointeurs contenant les adresses source et destination de chaque ligne. On conserve ainsi r10 et r11.
r12 sera le nombre de pixels en largeur, donc notre registre de boucle en X. On ne peut utiliser r2 car pour chaque nouvelle ligne on aura besoin de réinitialiser r12.
r1 sera notre registre de boucle en Y. Lui par contre n’a pas besoin d’être conservé car une fois qu’il sera arrivé à 0, l’algorithme sera terminé.
r4 sera notre accumulateur de delta X.

Le code qui permet de pousser les valeurs dans les registres NEON est celui-ci.
Je le réordonne un peu pour une meilleure compréhension (mais du coup une moins bonne performance).

	ldr			r6, [r8]								@ ce code charge q1 (d0-d1)
	ldr			r7, [r8, #4]
	adds			r4, r4, r5
	addcs			r8, r8, #4
	vmov			s0, r6
	vmov			s2, r7

On charge donc un pixel (pixel[i]) dans r6, puis le pixel suivant (pixel[i + 1]) dans r7, car notre pixel interpolé utilise toujours deux pixels consécutifs.
On ajoute à r4 la valeur de r5, et là, deux cas sont possibles:

  • Soit on a un dépassement de capacité, ce qui veut dire que le pixel suivant (à interpoler) utilisera les pixels sources suivants (qu’il faut incrémenter i).
  • Soit on a pas de dépassement de capacité, et donc le pixel suivant sera calculé à partir des mêmes pixels sources (mais avec des coefficients différents)

Donc on fait avancer (ou non) le pointeur source d’un pixel

Enfin on transfert vers s0 et s2 les pixels chargés.
On recommence afin de remplir s1 et s3.
On a alors deux registres 64 bits NEON prêt pour le calcul. Il ne nous reste plus qu’à exécuter l’interpolation avec NEON. Le code de celui-ci est rigoureusement le même que dans les versions précédentes de l’algorithme.

Conclusion

Ce code non optimisé, nous permet de nous affranchir de la transposition évoquée dans le post précédent, laquelle engendrait de sérieux problèmes de défaut de cache.

Pour réaliser l’agrandissement sur les deux axes, il faudra évidement composer cette interpolation en X avec l’interpolation en Y détaillée dans le post précédent. Il faudra juste penser à retirer de l’interpolation en Y la transposition devenue inutile.

La composition de ces deux fonctions (interpolation en X puis en Y) offre déjà des performances supérieures aux autres versions que j’ai pu tester puisqu’il ne faut maintenant plus que 0.72ms pour effectuer l’agrandissement.

Dans cette version, on traite à chaque itération 2 pixels.
Le résultat optimal est atteint en traitant les pixels 8 par 8.
Dans ce cas, vous pouvez en pipelinant correctement, atteindre une vitesse d’exécution de seulement 0.55ms pour effectuer la conversion (soit 16.3 fois la vitesse de la version C).

Dit autrement, il ne faut que 5.5 cycles pour interpoler un pixel 32bit. Ce qui est plutôt correct !!!

 | Tags: ,

2 Responses to “Agrandissement bilinéaire: Le retour”

  1. schtruck dit :

    salut,

    ton travail m’interesse beaucoup, car actuellement j’ai un morceau de code neon qui effectue une conversion BGR555 vers RGB565, ensuite j’envoi une fonction de stretching Java drawbitmap qui n’est dèjà vraiment pas veloce, et si à cette routine j’active le bilinear filtering en parametre, c’est 40% de cpu en plus qui est consommé.
    Je me pose la question si il ne serait pas judicieux de convertir le BGR555 en RGBA8888 et d’utiliser ton code pour le stretching. Je pense qu’il devrait y avoir une enorme difference.
    Qu’en penses tu?

    PS: Désolé j’ai d’abord posté ce méssage sur un autre de tes articles par erreur.

  2. Etienne SOBOLE dit :

    Salut. Oui c’est clair qu’il est impossible de faire le moindre traitement “efficace” en RGB565.
    Donc je pense que tu as raison, il faut convertir en RGB8888 (ou RG888) avant d’appliquer le redimensionnement.

    Il y a les exemples de conversion RGB565 vers RGB888 et vice versa ici:
    http://blogs.arm.com/software-enablement/277-coding-for-neon-part-4-shifting-left-and-right/

    Ensuite oui tu peux utiliser mon code… (enfin si tu cherches à agrandir l’image pour le moment).
    Voilà.

Répondre

Human control : 8 + 1 =