21

Réduction du nombre de couleurs avec NEON

sept

Aujourd’hui, je m’intéresse aux algorithmes de conversion d’une image RGB888 (16 million de couleurs) à une image RGB565 (65000 couleurs).
NEON n’a pas de prédispositions particulières pour traiter les pixels 16 bits (RGB565 sur Android) ce qui conduit souvent les développeurs à effectuer les opérations complexes sur des pixels 32 bits puis de convertir le résultat en 16 bits une fois le traitement terminé.
Contre toute attente, il existe des algorithmes très efficace et peu gourmand en temps CPU pour réaliser de façon correcte cette conversion…

L’image test

Pour mes tests de conversion j’ai utilisé l’image ci-dessous. Le dégradé de Bleu est un vrai stress test pour les divers algorithmes puisqu’une fois converti en RGB565 il n’y aura plus que 32 niveaux de bleu contre 256 dans l’image originale.

Image source 256*256

La méthode de base.

La méthode la plus simple (et la plus rapide) pour convertir un pixel est fournie sur le blog d’ARM.
Elle consiste simplement à supprimer les bits de poids faible de chaque composante.

	vld4.u8		{d0 - d3}, [r1]!			@ reading 8 pixels (d0:red, d1:green, d2:bleu, d3:alpha)

	vshll.u8 	q2, d0, #8					@ shift red value and convert components to 16 bits
	vshll.u8		q3, d1, #8					@ shift green value and convert components to 16 bits
	vsri.16		q2, q3, #5					@ insert green into red 16 bit lane
	vshll.u8 	q3, d2, #8					@ shift blue value and convert components to 16 bits
	vsri.16		q2, q3, #11					@ insert blue into red 16 bit lane

	vst1.u16		{q2}, [r0]!

Cette algorithme peut être facilement pipeliné pour en optimiser sa performance. Néanmoins il est tellement déjà simple et rapide que le principale goulot d’étranglement vient des accès mémoires.
Le résultat est sans surprise! Il est tout juste correct. Cependant il est sans doute suffisant dans un certain nombre de cas.

Image source 256*256 Aucun traitement

On voit clairement des bandes de couleurs apparaître sur le bleu ou bien le gris. La réduction du nombre de couleur sur chaque composante est ici bien visible.

Floyd: le maître est dans la place

S’il est bien un algorithme de j’aime bien, c’est l’algorithme de tramage par diffusion d’erreur de Floyd-Steinberg. C’est sans doute due au fait que c’est l’un des premiers programme un peu intéressant que j’ai codé il y a très longtemps… Du coup il m’est resté en mémoire comme un bon souvenir, et le sentiment qu’il s’agit du meilleur algorithme de réduction de couleur existant (pas sur que ce soit vrai !!!).
Donc forcément j’ai tout de suite pensé à lui lorsque j’ai commencé mes expérimentations.

Fonctionnement de l’algorithme!

Lorsque l’on réduit le nombre de couleur d’une image, on a forcement (généralement) une perte de qualité due au fait que l’on a moins de couleurs pour représente la même chose. Chaque pixel de l’image est remplacé par un autre pixel qui généralement n’a pas exactement la même couleur. La différence entre la couleur du pixel d’origine et la couleur du pixel final peut donc être considéré comme la quantité de couleur qui manque (ou qui est en trop) pour retrouver la couleur d’origine.
Cette quantité est appelée l’erreur.

L’idée de Floyd est de distribuer cette erreur sur les pixels alentour. En gros si vous convertissez un pixel bleu en un pixel bleu un peu plus sombre, on va essayer de répartir une petite quantité du bleu manquant (l’erreur) sur les pixels voisin.

La distribution de l’erreur est quantifié et répartie sur le pixel de gauche ainsi que sur les pixels de dessous selon les coefficients suivants:

Le fait de propager l’erreur sur les pixel adjacents va avoir deux effets intéressants:

  • D’une part, l’image “globale” va conserver la même intensité lumineuse. Si on avait ignoré l’erreur on aurait pu avoir une image plus clair ou plus sombre selon la méthode retenue pour sélectionner la couleur de destination. Ce problème ne se pose plus aujourd’hui car on n’utilise plus de mode paletté pour gérer les images. Donc cet intérêt n’a plus court.
  • D’un autre coté l’ajout de l’erreur sur les pixels adjacent va induire la modification de certaines couleurs et introduire une sorte de trame qui va partiellement gommer l’effet bande de couleurs que l’on a dans le rendu le plus simple. C’est principalement ce qui nous intéresse ici.

L’algorithme de Floyd est donc finalement très simple, mais seulement en apparence! En fait il soulève deux questions assez complexes:

  • Qu’est ce que l’erreur ?
  • Comment utiliser NEON pour réaliser ce traitement ?
Calculer l’erreur

Comment obtenir l’erreur lorsque l’on converti une image RGB888 en une image RGB565 ?
Pour la suite de ce paragraphe on ne va s’occuper que d’une seule composante (au hasard le rouge) puisque le problème est le même pour chaque composante.
Le rouge de notre image original peut avoir 256 valeurs distinctes (8 bits). La destination, elle, n’en a que 32 (5 bits).
Pour obtenir la couleur la plus proche, on ne conserve que les 5 pixels forts de notre octet d’origine. On serait tenté de penser que les 3 bits faibles représentent l’erreur, mais en fait pas du tout !

Supposons que ce soit le cas et prenons le cas d’un pixel noir (valeur 0)

Dans ce cas, notre couleur destination vaut 0
et notre erreur 0 également.
C’est assez logique, notre couleur noire est resté bien noire. Il n’y a donc pas d’erreur à propager.

Prenons a présent un pixel blanc (valeur 255)

Ici notre couleur destination vaut 31, ce qui est bien du blanc dans notre mode RGB565.
Par contre l’erreur vaut 7.

Hors, il n’y a pas d’erreur. Notre pixel est bien blanc. Il n’est pas gris clair !!! L’erreur devrait donc valoir 0 et non pas 7!

Le problème vient de la répartition des couleurs.
Le problème devient limpide si vous essayez de convertir une image dans l’autre sens. C’est à dire du RBG565 vers le RGB888.
Si vous ajoutez des bits à 0 pour aligner sur 8 bits vos composantes, votre noir va rester noir mais votre blanc sera gris clair.
Si vous ajoutez des bits à 1 pour aligner sur 8 bits vos composantes, votre blanc va être bien blanc, mais votre noir sera en fait gris foncé!

Ce que l’on a donc appelé erreur dans notre postulat, n’est donc en fait par l’erreur à propager. Il va falloir la corriger.
Cette correction est assez simple car elle est linaire.
Appelons C la couleur d’origine et R la couleur obtenue après réduction (les 5 bits de poids fort).

Pour trouver l’erreur exact, il faut en fait effectuer la conversion inverse:
Rc = R * 255 / 31
255 est ici le nombre de niveaux de rouge -1 dans l’image source.
31 est le nombre de niveaux de rouge – 1 dans l’image destination.
On obtient alors l’erreur en faisant la différence entre le couleur d’origine C et Rc

Donc:

Erreur = C - R * 255 / 31
Floyd et NEON ne sont pas bon copain

Le deuxième problème qui se pose à nous, c’est que NEON est très doué pour effectuer des calculs sur des pixels qui sont indépendants les un des autres. Par contre traiter un pixel dont la valeur dépend du résultat d’un calcul sur le pixel précédent n’est pas son fort. On peut même dire qu’il n’est pas du tout adapté à ce type de traitement…

Heureusement, l’algorithme de Floyd peut être segmenté en deux parties.

  • La première consiste à propager l’erreur sur le pixel de gauche.
  • La seconde consiste à propager l’erreur sur les pixels de la lignes suivantes.

Si la première partie risque de nous poser des problèmes, la deuxième par contre pourra assez facilement être réalisée de façon efficace (parce qu’au final c’est quand même pour ça qu’on utilise NEON) par l’extension SIMD de l’ARM !
Et comme tout et bien qui fini bien, il se trouve que la traitement de la deuxième partie va nous permettre de réaliser la première sans trop de perte de cycles !
Enfin évidement le nombre de registres important de NEON et le fait que l’on va de toute façon pouvoir traiter les 3 composantes d’un pixels en même temps rendent de toute façon NEON plus efficace même pour ce genre de traitement.

Bon je préviens tout de suite, ça va être assez compliqué à expliquer !

Nous allons calculer les pixels 4 par 4. Et nous allons faire en sorte de manipuler chaque pixel dans un registre 64 bits. Ce qui veut dire que nous allons devoir étendre les pixels 32bits sur 64bit grâce à un VSHLL.

Les registres de travail vont être utilisés comme suit:
d20, d21, d22 et d23 contiennent l’erreur provenant de la ligne précédente.
d25 contient l’erreur provenant du pixel précédent.
d0, d1, d2 et d3 contiennent les pixels.
d26, d27, d28, d29, d30 et d31 contiennent les erreurs a propager sur la ligne suivante.
On utilisera d24 pour stocker des calculs temporaire et d4 pour stocker les coefficients de Floyd (1,3, 5 et 7).
q7 contient un masque de but permettant de mettra a 0 la couche alpha.
q7 contient des valeur de décalage permettant de placer les composante rouges, vertes et bleues à la bonne position afin de pouvoir ensuite les fusionner grâce a des vpadd.
d18 va contenir des valeurs permettant de supprimer les bits de poids faible des pixels.
d19 quant a lui va contenir les coefficients permettant la correction de l’erreur.

Tous les calculs se feront avec une précision de 7 bits et des opérations signées puisque l’erreur peut aussi bien être positive que négative.

On commence donc par charger les registres contenant des constantes et mettre a zero les registres d26 à d31.

.neon_dither_floyd2_data:
	.word		0x00ffffff, 0x00ffffff, 0x00ffffff, 0x00ffffff @ used to remove alpha value
	.hword	11, 5, 0, 0, 11, 5, 0, 0			@ used to shift red, green and blue before vpadd
	.hword	-10, -9, -10, 0						@ used to shift red, green and blue to remove lower bits.
	.hword	1053, 518, 1053, 0					@ coef for error correction (255 * 128 / 31) for red and blue (255 * 128 / 63) for green
	.hword	1, 3, 5, 7								@ floyd coef (d4)

...

	mov			r8, #0
	vld1.u32		{q7}, [r4]!							@ bit field used to reset alpha channel
	vld1.u64		{q8, q9}, [r4]!					@ shift values and coefs
	vld1.s16		{d4}, [r4]!							@ floyf coef
	vdup.u8		q13, r8								@ reset q13, q14, q15
	vdup.u8		q14, r8
	vdup.u8		q15, r8

	mov			r6, r5								@ r5 is a pointeur to a free memory zone
	add			r7, r2, #2							@ need to reset width + 2 64 bits error values
.neon_dither_floyd2_reset_loop:
	str			r8, [r6], #4						@ pour chaque pixel on a 4 * 16 bit d'erreur
	str			r8, [r6], #4
	subs			r7, r7, #1
	bne			.neon_dither_floyd2_reset_loop

Coté ARM:
r0 contient le pointeur destination
r1 contient le pointeur destination
r2 contient la largeur de l’image (multiple de 4 !!!)
r3 contient la hauteur de l’image

r5 devra pointer sur une petite zone mémoire dont la longueur est (largeur de l’image + 2) * 8 octets. cette zone va contenir les valeurs d’erreurs pour les lignes suivantes et précédentes.
r6 vaudra toujours r5 + 8 et sera le pointeur qui va contenir l’erreur de la ligne précédente.
r7 sera un pointeur de travail pour enregistrer les erreurs de la lignes suivante.

En fait on va utiliser la même zone mémoire pour lire l’erreur de la ligne précédente puis écrire dedans la nouvelle erreur obtenu pour le ligne suivante.

C’est parti !!!

.neon_dither_floyd2_loop_y:
	mov			r7, r5								@ ptr dst erreur
	add			r6, r5, #8							@ ptr src erreur
	mov			r9, r2
	vdup.u8		d25, r8								@ reset d25 because there is not error comming form previous pixel for the first pixel.
.neon_dither_floyd2_loop_x:

	...

	subs			r9, r9, #4
	bgt			.neon_dither_floyd2_loop_x

	subs			r3, r3, #1
	bgt			.neon_dither_floyd2_loop_y

Tout d’abord, regardons la boucle sur l’axes des Y avant d’entrer dans le vif du sujet.
r6 et r7 pointent tous les deux sur la même zone mémoire.
r6 sera utilisé pour lire d20, d21, d22 et d23 qui sont l’erreur provenant de la ligne précédente.
r7 sera utilisé pour stoker d26, d27, d28 et d29.

Lorsqu’on traite 4 pixels, on lit d’abord d20 – d23. ensuite on n’aura plus besoin d’accéder a cette zone mémoire (pour cette ligne). on peut donc écraser a la fin du calcul des 4 pixels cette zone mémoire par les valeur de l’erreur de la lignes suivante. A savoir d26 – d29.

d25 contient l’erreur propagée du pixel précédent. A chaque début de ligne, cette erreur est remise à 0 !

Voila.
Voyons à présent le corps de la boucle .neon_dither_floyd2_loop_x

	vld1.u32		{q0}, [r1]!							@ Read 4 32bits pixels
	vld1.u64		{q10 - q11}, [r6]!				@ Read 4 64bits errors.

	vand.u32		q0, q0, q7							@ remove alpha channel

	vshll.u8		q1, d1, #7							@ convert each component to signed 16 bits
	vshll.u8		q0, d0, #7

	vqadd.s16	d0, d0, d20							@ add error from up pixel (using saturation!)
	vqadd.s16	d24, d0, d25						@ add error from left pixel (using saturation!)
	vcgt.s16		d5, d24, #0							@ if (component < 0)
	vand.u16		d24, d24, d5						@ then component = 0
	vshl.s16		d0, d24, d18						@ pixel shifting to have only the RBG565 component value into d0
	vmls.s16		d24, d0, d19						@ compute error correction
															@ d24[0](8bit red) = d24[0](8bit red) - d0[0](5bit red) * 255 * 128 / 31
															@ d24[1](8bit green) = d24[1](8bit green) - d0[1](6bit green) * 255 * 128 / 63
															@ d24[2](8bit blue) = d24[2](8bit blue) - d0[2](5bit blue) * 255 * 128 / 31

	vrshr.s16	d24, d24, #4						@ divide the error by 16

	vmla.s16		d26, d24, d4[1]					@ error * 3 / 16
	vmla.s16		d27, d24, d4[2]					@ error * 5 / 16
	vmla.s16		d28, d24, d4[0]					@ error * 1 / 16
	vmul.s16		d25, d24, d4[3]					@ error * 7 / 16

	vqadd.s16	d1, d1, d21							@ PIXEL 2
	vqadd.s16	d24, d1, d25
	vcgt.s16		d5, d24, #0
	vand.u16		d24, d24, d5
	vshl.s16		d1, d24, d18
	vmls.s16		d24, d1, d19
	vrshr.s16	d24, d24, #4

	vmla.s16		d27, d24, d4[1]
	vmla.s16		d28, d24, d4[2]
	vmla.s16		d29, d24, d4[0]
	vmul.s16		d25, d24, d4[3]

	vqadd.s16	d2, d2, d22							@ PIXEL 3
	vqadd.s16	d24, d2, d25
	vcgt.s16		d5, d24, #0
	vand.u16		d24, d24, d5
	vshl.s16		d2, d24, d18
	vmls.s16		d24, d2, d19
	vrshr.s16	d24, d24, #4

	vmla.s16		d28, d24, d4[1]
	vmla.s16		d29, d24, d4[2]
	vmla.s16		d30, d24, d4[0]
	vmul.s16		d25, d24, d4[3]

	vqadd.s16	d3, d3, d23							@ PIXEL 4
	vqadd.s16	d24, d3, d25
	vcgt.s16		d5, d24, #0
	vand.u16		d24, d24, d5
	vshl.s16		d3, d24, d18
	vmls.s16		d24, d3, d19
	vrshr.s16	d24, d24, #4

	vmla.s16		d29, d24, d4[1]
	vmla.s16		d30, d24, d4[2]
	vmla.s16		d31, d24, d4[0]
	vmul.s16		d25, d24, d4[3]

	vshl.u16		q0, q0, q8							@ moving each component to the right position before vpadd
	vshl.u16		q1, q1, q8

	vst1.u64		{q13 - q14}, [r7]!				@ recording d26 - d29 because those error values will not be updated.
	vmov.u8		q13, q15								@ for the next iteration q13 become q15
	vdup.u8		q14, r8
	vdup.u8		q15, r8

	vpadd.i16	d0, d0, d1							@ merging components
	vpadd.i16	d1, d2, d3
	vpadd.i16	d0, d0, d1

	vst1.u16		{d0}, [r0]!						@ write 4 16bits pixels !

Même si le code est commenté quelques explications ne feront pas de mal.

D'abord on charge 4 pixels 32 bits ainsi que les valeurs d'erreur provenant de la ligne précédente. Ces erreurs sont des 64 bits (4 * 16 bits). Pour la première lignes, ces erreurs valent 0.
Puis on convertit les composantes en 16 bits signés grâce à un décalage de 7 bits.

On ajoute l'erreur provenant du pixel du dessus et celle provenant du pixel précédent.
On utilise des opérations avec saturation (vqadd) afin de s'assurer que notre composante ne pas dépasser 255.
pour la saturation inférieur (0) le vqadd ne sert a rien puisque l'opération est signée.
On doit donc contrôler que la valeur est bien supérieure à 0 et si ce n'est pas le cas remplacer la valeur par 0.

C'est exactement ce que font ces deux instructions.

	vcgt.s16		d5, d24, #0							@ if (component < 0)
	vand.u16		d24, d24, d5						@ then component = 0

Puis on réduit chaque composantes afin de pouvoir effectuer le calcul d'erreur.
Enfin arrive l'instruction magique qui en une seule opération corrige l'erreur

	vmls.s16		d24, d0, d19						@ compute error correction
															@ d24[0](8bit red) = d24[0](8bit red) - d0[0](5bit red) * 255 * 128 / 31
															@ d24[1](8bit green) = d24[1](8bit green) - d0[1](6bit green) * 255 * 128 / 63
															@ d24[2](8bit blue) = d24[2](8bit blue) - d0[2](5bit blue) * 255 * 128 / 31

d24 contient alors l’erreur corrigé pour chaque composante.
Il ne reste plus qu’a multiplier cette erreur par 1/16, 3/16, 5/16 et 7/16 afin de la répartir sur les autres pixels.

Le code est ensuite répété 4 fois, puisqu’on traite 4 pixels par itération.

Enfin, on fusionne les composantes (grâce à des vpadd)
On enregistre l’erreur que l’on propage vers la ligne suivante et qui sera utilisée lors de l’itération suivante de la boucle Y.
Puis on enregistre les pixels 16 bits obtenus !

Résultat
Image source 256*256 Aucun traitement Dithering de Floyd

Si Floyd est un peu mieux que rien du tout, c’est quand même pas la panacée. Je suis quelques peu déçu par le résultat.
Les bandes de couleurs sont certes adoucies, mais on les distingue encore clairement.
J’ai pas trouvé le moyen de tester le dithering de Floyd avec PhotoShop ou ImageMagick, mais il semble bien que cet algorithme soit particulièrement performant lorsque le nombre de couleurs de l’image destination est très limité. Ce qui limite de nos jours grandement l’utilité de cet algorithme…

En testant ImageMagick, J’ai pu constaté que ce dernier utilisait un autre algorithme très nettement plus performant pour réaliser la conversion RGB888 vers RGB565…

Le tramage ordonné

L’algorithme de Floyd est assez compliqué pour un résultat une peu moyen. On pourrait se dire que c’est super s’il n’y avait pas mieux, mais le problème c’est qu’il existe un algorithme:

  • Plus simple
  • Plus rapide
  • Et qui donne un meilleur résultat

Il s’agit du tramage ordonné de type Bayer.

C’est quoi ?

Le principe est assez simple. Il consiste à ajouter un bruit régulier et ordonné à l’image.
On trouve quelques explications ici.

L’implémentation est assez simple, même s’il a fallu que le fasse quelques petits réglages sur l’algorithme original pour avoir un rendu correct (ce qui me laisse a penser que j’ai pas totalement tout compris sur le méthode d’implémentation exact de cet algorithme).

Le code

Comme l’algorithme est extrêmement simple je donne tout de suite le code, puis j’explique après sont fonctionnement.

La seule subtilité tiens dans la représentation de la matrice de bayer.
Celle-ci normalement, ressemble à cela.

1	49	16	61	4	52	16	64
33	17	45	29	36	20	48	32
9	57	5	53	12	60	8	56
41	25	37	21	44	28	40	24
3	51	15	63	2	50	14	62
35	19	47	31	34	18	46	30
11	59	7	55	10	58	6	54
43	27	39	23	42	26	38	22

Je l’ai transformé pour la que les valeurs soient signées. C’est à dire que parfois j’ajoute de la couleur et parfois j’en enlève.
Ce qui me donne cette matrice.

-31	17		-16	29		-28	20		-16	32
1		-15	13		-3		4		-12	16		0
-23	25		-27	21		-20	28		-24	24
9		-7		5		-11	12		-4		8		-8
-29	19		-17	31		-30	18		-18	30
3		-13	15		-1		2		-14	14		-2
-21	27		-25	23		-22	26		-26	22
11		-5		7		-9		10		-6		6		-10

Enfin j’ai directement pondéré pour me donner une première matrice utilisable par les composantes rouges et bleues, et une deuxième matrice utilisable par la composante verte.
Enfin j’ai séparé chaque matrice en 2 matrices.

  • La première contient les valeurs positives de la matrice. Les valeurs négatives sont mises à 0
  • La deuxième contient les valeurs absolues des valeurs négatives. Les valeurs positives sont mises à 0

Donc au final d’une matrice de bayer, je me retrouve avec 4 matrices que j’ai en plus entrelacées… Bref, ça devient incompréhensible mon histoire. Mais bon vous pouvez soit utiliser tel quel le code suivant, soit simplement essayer de recoder l’algorithme et vous arriverez sans doute sur un truc plus ou moins semblable.

	.type		neon_dither_bayer, %function
	.align 4
.neon_dither_bayer_data:
	.byte			0, 4, 0, 7, 0, 5, 0, 8
	.byte			8, 0, 4, 0, 7, 0, 4, 0
	.byte			0, 2, 0, 4, 0, 3, 0, 4
	.byte			4, 0, 2, 0, 4, 0, 2, 0
	.byte			0, 0, 3, 0, 1, 0, 4, 0
	.byte			0, 4, 0, 1, 0, 3, 0, 0
	.byte			0, 0, 2, 0, 1, 0, 2, 0
	.byte			0, 2, 0, 0, 0, 2, 0, 0
	.byte			0, 6, 0, 5, 0, 7, 0, 6
	.byte			6, 0, 7, 0, 5, 0, 6, 0
	.byte			0, 3, 0, 3, 0, 4, 0, 3
	.byte			3, 0, 3, 0, 3, 0, 3, 0
	.byte			2, 0, 1, 0, 3, 0, 2, 0
	.byte			0, 2, 0, 3, 0, 1, 0, 2
	.byte			1, 0, 1, 0, 2, 0, 1, 0
	.byte			0, 1, 0, 1, 0, 1, 0, 1
	.byte			0, 5, 0, 8, 0, 5, 0, 8
	.byte			7, 0, 4, 0, 8, 0, 5, 0
	.byte			0, 2, 0, 4, 0, 2, 0, 4
	.byte			4, 0, 2, 0, 4, 0, 2, 0
	.byte			1, 0, 4, 0, 1, 0, 4, 0
	.byte			0, 3, 0, 0, 0, 4, 0, 1
	.byte			0, 0, 2, 0, 0, 0, 2, 0
	.byte			0, 2, 0, 0, 0, 2, 0, 0
	.byte			0, 7, 0, 6, 0, 7, 0, 6
	.byte			5, 0, 6, 0, 6, 0, 7, 0
	.byte			0, 3, 0, 3, 0, 3, 0, 3
	.byte			3, 0, 3, 0, 3, 0, 3, 0
	.byte			3, 0, 2, 0, 3, 0, 2, 0
	.byte			0, 1, 0, 2, 0, 2, 0, 3
	.byte			1, 0, 1, 0, 1, 0, 1, 0
	.byte			0, 1, 0, 1, 0, 1, 0, 1

neon_dither_bayer:
	push			{r4-r11, r12, lr}

	adr			r8, .neon_dither_bayer_data
	add			r9, r8, #256

.neon_dither_bayer_loop_y:
	vld1.u8		{q4, q5}, [r8]!					@ reading 4 blocs of 8 bayer values

	mov			r7, r2
.neon_dither_bayer_loop_x:
	vld4.u8		{d0 - d3}, [r1]!					@ reading 8 pixels

	vqadd.u8		d0, d0, d8							@ add bayer on red
	vqadd.u8		d1, d1, d10							@ add bayer on green
	vqadd.u8		d2, d2, d8							@ add bayer on blue
	vqsub.u8		d0, d0, d9							@ sub bayer on red
	vqsub.u8		d1, d1, d11							@ sub bayer on green
	vqsub.u8		d2, d2, d9							@ sub bayer on blue

	vshll.u8 	q2, d0, #8							@ conversion to RGB565
	vshll.u8		q3, d1, #8
	vsri.16		q2, q3, #5
	vshll.u8 	q3, d2, #8
	vsri.16		q2, q3, #11

	vst1.u16		{q2}, [r0]!

	subs			r7, r7, #8
	bgt			.neon_dither_bayer_loop_x	

	cmp			r8, r9								@ if reach the 9th line then restart bayer
	adrge			r8, .neon_dither_bayer_data

	subs			r3, r3, #1
	bgt			.neon_dither_bayer_loop_y

	pop			{r4-r11, r12, pc}
	.size			neon_dither_bayer, .-neon_dither_bayer

Donc c’est vraiment très simple.
On lit 8 pixels dont on sépare les composantes dans d0, d1 et d2.
On ajoute les valeurs du bruits que l’on veut injecter. Dans mon code, il y a pour chaque composantes:

  • un vqadd qui permet d’ajouter les valeurs positives de ma matrice
  • un vqsub qui permet de soustraire les valeurs négatives de ma matrice

Chaque bloc de 8 pixels utilise les mêmes valeurs de bruit, ce qui explique pourquoi ces valeurs sont chargées avant la boucle sur l’axe des X.
Ces valeurs sont changées à chaque ligne et bouclent toutes les 8 lignes.

Résultats
Aucun traitement Dithering de Floyd pulsar “Bayer”

Le résultat, quoique bruité, est bien meilleur que le rendu de Floyd…

N’est pas bayer qui veut

En fait, l’algorithme présenté n’est pas vraiment l’algorithme de Bayer.
Pour s’en rendre compte il suffit de voir le rendu obtenu par imagemagick. Imagemagick offre un rendu encore meilleur.

pulsar “Bayer” imagemagick Bayer

La différence est faible mais pourtant bien visible. C’est encore plus visible si vous zoomez ces images avec un logiciel de dessin !
Je n’ai pas vraiment compris le “vrai” algorithme de Bayer, son implémentation est assez peu détaillée sur Internet. Mais je ne m’avoue pas vaincu.
Je vais aller matter le code source d’imagemagick jusqu’à ce que j’arrive à comprendre son fonctionnement.

Conclusion et remarque

Je ne me suis pas du tout intéressé à la performance (ni l’optimisation) des ces algorithmes. Il est clair qu’une version utilisant de NEON est de doute façon toujours plus efficace qu’un version sans NEON. Dans tous les cas de figure, NEON est toujours capable (au pire) de traiter les composantes rouge, verte et bleue en parallèle.
Dans le cas du tramage ordonné, NEON est même ultra efficace. il est a peine plus lent que la conversion sans dithering.

Enfin il est à noter qu’il existe l’algorithme de réduction de couleur de Riemersma qui semble extrêmement efficace (en termes qualitatif).
Par contre son implémentation n’est absolument pas adaptée à NEON. Il est de plus récursif, ce qui généralement n’est guère compatible avec un niveau de performances élevé.
J’essayerai aussi cet algorithme lorsque j’aurai un peu de temps.

 | Tags: , ,

4 Responses to “Réduction du nombre de couleurs avec NEON”

  1. denis 18 dit :

    Je suis intérréssé par la performance et aussi l’optimisation – cependant ton article semble pour le moins curieux et l’heure ou le codage de chaque compossants de la vidéo s’effectue sur 64 bits je croix que tu retarde un peut.

  2. Etienne SOBOLE dit :

    Il n’y a pas que la video dans la vie.
    Par exemple, la majeure partie des jeux sur Android sont en 16bits…
    Je me sert de la réduction de couleur pour préparer mes sprites à l’affichage.

    Apres faut aussi garder à l’esprit, que j’ai un boulot, et que je code en assembleur pour le plaisir. Donc je m’en fou un peu de faire des trucs “moyennement” utiles.

  3. Pavel dit :

    Nice article. Just FYI, pixman library has neon optimized code for resizing/converting images. A few years ago I also needed to do RGB3 R565 conversion and I also had that banding problem. I also solved it with FS-dithering. Have no idea why, but I had no visible banding with FS dithering.

  4. [...] expliquées ici afin qu’ils soit adaptés à la résolution du device. Enfin je les réduis en 16 bits puis les encode dans un format particulier requis par mon moteur [...]

Répondre

Human control : 3 + 3 =