FR2834397A1 - Sous- echantillonnage de donnees images pixelisees - Google Patents
Sous- echantillonnage de donnees images pixelisees Download PDFInfo
- Publication number
- FR2834397A1 FR2834397A1 FR0117032A FR0117032A FR2834397A1 FR 2834397 A1 FR2834397 A1 FR 2834397A1 FR 0117032 A FR0117032 A FR 0117032A FR 0117032 A FR0117032 A FR 0117032A FR 2834397 A1 FR2834397 A1 FR 2834397A1
- Authority
- FR
- France
- Prior art keywords
- blocks
- sub
- result
- accumulators
- sampling
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000005070 sampling Methods 0.000 title claims abstract description 29
- 230000015654 memory Effects 0.000 claims abstract description 72
- 238000000034 method Methods 0.000 claims abstract description 15
- 238000007792 addition Methods 0.000 description 6
- 238000004364 calculation method Methods 0.000 description 5
- 230000006835 compression Effects 0.000 description 5
- 238000007906 compression Methods 0.000 description 5
- 238000012545 processing Methods 0.000 description 5
- 230000008901 benefit Effects 0.000 description 4
- 239000011159 matrix material Substances 0.000 description 3
- 230000008569 process Effects 0.000 description 3
- 238000012163 sequencing technique Methods 0.000 description 2
- 238000012935 Averaging Methods 0.000 description 1
- 238000009825 accumulation Methods 0.000 description 1
- 230000005540 biological transmission Effects 0.000 description 1
- 230000008859 change Effects 0.000 description 1
- 230000003247 decreasing effect Effects 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 238000007599 discharging Methods 0.000 description 1
- 239000000284 extract Substances 0.000 description 1
- 230000006870 function Effects 0.000 description 1
- 239000000463 material Substances 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 230000009466 transformation Effects 0.000 description 1
- 238000000844 transformation Methods 0.000 description 1
- 238000011144 upstream manufacturing Methods 0.000 description 1
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T3/00—Geometric image transformations in the plane of the image
- G06T3/40—Scaling of whole images or parts thereof, e.g. expanding or contracting
- G06T3/4023—Scaling of whole images or parts thereof, e.g. expanding or contracting based on decimating pixels or lines of pixels; based on inserting pixels or lines of pixels
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
- H04N19/85—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using pre-processing or post-processing specially adapted for video compression
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Multimedia (AREA)
- Signal Processing (AREA)
- Image Processing (AREA)
- Storing Facsimile Image Data (AREA)
- Editing Of Facsimile Originals (AREA)
Abstract
L'invention concerne un procédé et un circuit de sous-échantillonnage de données image pixelisées regroupées par blocs se chevauchant, consistant à lire, ligne par ligne, une mémoire image (M1) contenant l'image pixelisée, à accumuler autant de lignes que le prévoit le rapport de sous-échantillonnage dans le sens vertical, en utilisant autant de groupes d'accumulateurs (Aij) qu'il y a de blocs dans le sens horizontal de l'image et autant d'accumulateurs par groupe que le prévoit le rapport de sous-échantillonnage dans le sens horizontal, et à mémoriser les valeurs accumulées dans autant de mémoires de résultat (MR) qu'il y a de groupes d'accumulateurs, chaque mémoire de résultat contenant des matrices sous-échantillonnées d'un nombre de blocs correspondant au nombre de blocs se chevauchant dans la direction verticale.
Description
SOUS-ÉCHANTILLONNAGE DE DONNÉES IMAGES PIXELISÉES
La présente invention concerne de façon générale le traitement d' images numériques et, plus particulièrement, le
sous-échantillonnage dimages numériques. Un sous-échantil-
lonnage revient à approximer une image d'origine pixelisce pour en réduire la taille Le plus souvent, un tel sous-échantillonnage est effectué de manière réqulière en dimensions, c'est-à-dire qu'à un groupe de pixels de dimensions donnces on fait correspondre une valeur résultante, le nombre de pixels du groupe étant constant pour toute l' image. L' ensemble de valeurs résultantes constitue une matrice pouvant s'apparenter à une image de dimensions réduites. Les données que contient cette matrice correspondent généralement à une valeur moyenne fonction des données d'origine de l' image (par exemple niveau de gris ou
niveau dans une couleur donnce, etc.).
La présente invention s' applique plus particulièrement au souséchantillonnage d' images numériques découpées en blocs recouvrants. Au sens de la présente invention, on considère que des blocs se recouvrent si le nombre de pixels séparant les
origines des deux blocs est inférieur au rapport de sous-échan-
tillonnage dans la direction verticale et/ou dans la direction horizontale. Le rapport de sous-échantillonnage correspondant au
nombre de pixels pris pour calculer une seule valeur résultante.
Un exemple d' application de la présente invention concerne le codage fractal d' images numériques et plus précisé ment l'étape de souséchantillonnage des blocs dits de domaine
d'un tel codage fractal.
Le codage fractal d' images consiste à rechercher, dans une image numérique, des portions de cette image qui peuvent être considérées comme identiques après avoir le cas échéant subi des transformations simples (symétrie, rotation) appelées isométries. La figure 1 représente une image I devant subir un
codage fractal et illustre le découpage effectué de cette image.
On commence par définir, dans l' image I, une fenêtre de recherche SW dans laquelle on souhaite déterminer si des parties de l' image peuvent s'apparenter à un bloc de référence RB de l' image. La fenêtre de recherche correspond, au maximum, à la taille de l' image I. Pour obtenir des blocs d' image, appelés des blocs de domaine, à comparer à l' image de référence, on part de blocs
d' image de plus grandes dimensions B1, B2 etc. qui sont sous-
échantillonnés pour être ramenés à la taille souhaitée pour les blocs de domaine. La taille des blocs de domaine correspond à la taille du bloc de référence recherché, généralement appelé ''Range''. Par exemple, le bloc de référence et les blocs de domaine correspondent à des matrices 8*8 tandis que les blocs B pris dans la fenêtre de recherche sont des blocs de 32*32 pixels. La figure 2 illustre le sous-échantillonnage opéré à partir des blocs B1, Bi, B9 pour obtenir des blocs de domaine
réduits DB1, DBi, DB9.
Dans un procédé de codage fractal, les blocs d'origine sont choisis, avec recouvrement, dans la fenêtre de recherche, ce qui est indispensable pour déterminer l'identité éventuelle des blocs de domaine, par rapport aux blocs de référence ou
leurs isométries, sur toute la fenêtre de recherche.
La comparaison des blocs de domaine et des blocs de référence s'effectue soit par différence de niveau de gris pixcl à pixel soit en sommant les différences des carrés entre les
valeurs respectives des blocs de domaine et de référence.
Le codage fractal d' images numériques constitue une technique de compression d' images utilisoe pour réduire le volume des transmissions d' images. Plutôt que d'envoyer tous les blocs d'une image, on se contente, pour des blocs similaires, d'envoyer une seule fois le bloc de référence puis le numéro de ce bloc et de son isométrie éventuelle pour définir les blocs de
domaine similaires.
La technique de codage ou compression fractale dimages est décrite, par exemple, dans l'ouvrage "Fractal image compression: Theory and application to digital images" de Yuval Fisher publié par Springer Verlag, New-York en 1995. Un autre exemple d'algorithme de compression fractale d' images est décrit dans l 'article "Design of an ASIC architecture for high speed fractal image compression" de Ancarani De Gloria et Olivieri Stazzone publié dans IEEE "International ASIC conference" en
septembre 1996.
L'homme de l'art pourra également se référer à la
demande de brevet français 2 775 812.
Le nombre d'opérations et d'accès mémoire à effectuer pour souséchantillonner les blocs de la fenêtre de recherche afin d'obtenir les blocs de domaine est très important. En effet, on effectue classiquement une lecture séquentielle, pixel par pixel, d'une mémoire contenant les valeurs des pixels de la fenêtre de recherche pour isoler les différents blocs et
calculer leurs valeurs sous-échantillonnées respectives.
L'échantillonnage consiste à faire la moyenne des
valeurs individuelles des pixels des sous-blocs à sous-échantil-
lonner. En d'autres termes, on additionne les valeurs respecti ves des pixels de chaque sous-bloc (par exemple, les seize valeurs des sous-blocs de 4*4 pixels en reprenant l'exemple précédent) et l'on divise le résultat par le nombre de pixels du sous-bloc afin d'obtenir la valeur moyenne comme valeur de sous échantillon. On a déjà proposé, pour réduire le nombre d'accès mémoire, de conserver les sommes intermédiaires afin de n'effec tuer que quatre extractions de valeurs de pixels pour chaque
nouvelle valeur échantillonnée.
Extraire séquentiellement les seize valeurs de chaque sous-bloc de la mémoire image requiert, même en conservant les sommes intermédiaires, d'effectuer pour chaque pixel des blocs de domaine (donc souséchantillonnés) seize accès mémoire, seize
additions puis une division.
La présente invention vise à proposer un nouveau procédé et système de sous-échantillonnage d' images numériques recouvrantes qui réduise le nombre d'accès mémoire et de calculs
nécessaires à l'obtention des images sous-échantillonnées.
L' invention vise également à proposer une solution qui puisse s' adapter à différents rapports de sous-échantillonnage
et dimensions d' images.
L' invention vise également, sans exclure une réalisa-
tion logicielle, à proposer une solution permettant une
réalisation matérielle particulièrement simple.
Pour atteindre ces objets et d'autres, l' invention prévoit un procédé de sous-échantillonnage de données image pixelisées regroupées par blocs se chevauchant, comprenant les étapes suivantes: lire, ligne par ligne, une mémoire image contenant l' image pixelisée; accumuler autant de lignes que le prévoit le rapport de sous-échantillonnage dans le sens vertical, en utilisant autant de groupes d'accumulateurs qu'il y a de blocs dans le sens horizontal de l' image et autant d'accumulateurs par groupe que le prévoit le rapport de sous-échantillonnage dans le sens horizontal; et mémoriser les valeurs accumulées dans autant de mémoires de résultat qu'il y a de groupes d'accumulateurs,
chaque mémoire de résultat contenant des matrices sous-
échantillonnées d'un nombre de blocs correspondant au nombre de blocs se chevauchant dans la direction verticale.
Selon un mode de mise en oeuvre de la présente inven-
tion, la mémorisation est effectuée de facon entrelacée.
Selon un mode de mise en oeuvre de la présente inven-
tion, on divise les valeurs accumulées par le produit des rapports de sous-échantillonnage dans les deux directions, pour
obtenir des valeurs moyennes à mémoriser en tant que sous-
échantillons.
Selon un mode de mise en oeuvre de la présente inven-
tion, la division dune valeur accumulée de plusieurs lignes de la mémoire image pour obtenir une valeur moyenne est obtenue en ne tenant compte que d'un nombre de bits les plus significatifs,
inférieur au nombre de bits de la valeur résultat.
Selon un mode de mise en oeuvre de la présente inven-
tion, les lignes de la mémoire image sont lues successivement depuis la première pour un nombre de lignes correspondant au rapport de souséchantillonnage dans la direction verticale, et on lit ensuite alternativement la première ligne suivante et une
ligne précédemment utilisée.
L' invention prévoit également un circuit de sous échantillonnage de donnces images pixelisées et reparties en blocs se chevauchant, comprenant: un nombre de sommateurs correspondant au nombre de pixels de blocs résultat dans une première direction, multiplié par le nombre de blocs dans une deuxTème direction; un nombre d'accumulateurs identique au nombre de sommateurs; et un nombre de mémoires de résultat des valeurs sous échantillonnées correspondant au nombre de blocs dans la
première direction.
Selon un mode de réalisation de la présente invention,
les accumulateurs sont commandables en addition ou en soustrac-
tion d'une valeur courante au résultat accumulé précédemment.
Selon un mode de réalisation de la présente invention, le nombre d'entrses de chaque sommateur correspond au rapport de
sous-échantillonnage dans la première direction.
Selon un mode de réalisation de la présente invention, lesdites mémoires de résultat comprennent un nombre de lignes correspondant au nombre de blocs dans la deuxième direction, multiplié par le nombre de pixels des blocs résultat dans la
deuxième direction.
Selon un mode de réalisation de la présente invention, le nombre de bits d'une valeur résultat stockée dans l'une desdites mémoires de résultat est inférieur au nombre de bits des valeurs des donnces images pixeliséss, la différence entre les deux nombres de bits définissant le rapport de division d'obtention de la valeur moyenne des pixcls de chaque groupe sous-échantillonné. Ces objets, caractéristiques et avantages, ainsi que d'autres de la présente invention seront exposés en détail dans
la description suivante de modes de mise en oeuvre et de réali-
sation particuliers faite à titre non-limitatif en relation avec les figures jointes parmi lesquelles: les figures 1 et 2 qui ont été décrites précédemment illustrent un exemple d' image et de sous-échantillonnage auxquels s 'applique la présente invention; et la figure 3 représente un mode de réalisation d'un circuit de sous-échantillonnage de blocs d' images selon la
présente invention.
Les mêmes éléments ont été désignés par les mêmes références aux différentes figures. Pour des raisons de clarté, seuls les éléments du circuit et les étapes du procédé qui sont nécessaires à la compréhension de l' invention ont été représen tés aux figures et seront décrits par la suite. En particulier, les traitements de l' image en amont et en aval de la mise en oeuvre du procédé de l' invention n'ont pas été illustrés et ne font pas l'objet de la présente invention. De plus, les cTrcuits d'adressage des mémoires utiliséss par l' invention n'ont pas été détaillés pour être à la portée de l'homme du métier à partir
des indications fonctionnelles de la présente description.
Une caractéristique de la présente invention est d'organiser le souséchantillonnage des blocs recouvrants d'une image en traitant simultanément toutes les valeurs des pixels d'une ligne de la fenêtre de recherche. Ainsi, selon l 'invention, une mémoire contenant les valeurs des pixels de la fenêtre de recherche, dans une disposition matricielle similaire à celle de l' image, est adressée simultanément pour toutes ses colonnes de façon à traiter simultanément une ligne entière. Par conséquent, le balayage de la mémoire selon l' invention s'effec
tue ligne à ligne.
Une autre caractéristique de l' invention est de traiter, en parallèle, le sous-échantillonnage des blocs recouvrant dans le sens des lignes. En d'autres termes, on prévoit autant de séries d'opérateurs de regroupement qu'il y a
de blocs recouvrants dans le sens des lignes.
L' invention sera décrite par la suite en relation avec un exemple d' application au sous-échantillonnage de blocs d'une fenêtre de recherche pour obtenir des blocs de domaine dans un codage fractal d'une image. On notera toutefois que celle-ci s 'applique plus généralement à tout souséchantillonnage de
blocs d' images se chevauchant dans au moins une direction.
Pour simplifier, on fera référence à des lignes et des colonnes correspondant respectivement aux directions horizontale et verticale d' image. On notera toutefois que ces notions de direction sont arbitraires et peuvent être inversées sans
changer les principes de l' invention.
La figure 3 représente un exemple d' architecture d'un circuit de souséchantillonnage d'une mémoire image selon l'invention. Dans cet exemple, on considère le cas d'une fenêtre de recherche SW telle quillustrce en figure 1, ciest-à-dire comprenant 34 colonnes et 34 lignes. La fenêtre de recherche
comprend 9 blocs de 32*32 pixels qui doivent être sous-
échantillonnés en 9 blocs de domaine de 8*8 pixcls. En pratique, on utilise une fenêtre de recherche de plus grandes dimensions, par exemple, 64 par 64 pixcls. Pour simplifier, l' invention sera décrite en relation avec un exemple de fenêtre de recherche de 34 par 34 pixels. Elle s'applique cependant quel que soit le
nombre de pixels de la fenêtre de recherche et des blocs.
Le sous-échantillonnage correspond, comme précédem ment, à prendre la moyenne de groupes de 16 pixels (4*4) de chaque bloc pour constituer un pixel du bloc de domaine résultant. Par la suite, on considérera à titre d'exemple le cas d'une image en niveaux de gris. Obtenir la moyenne revient donc à additionner les niveaux de gris respectifs des pixels de chaque groupe et à diviser le nombre obtenu par le nombre de pixels. En variante, on pourra se passer de la division si le facteur multiplicatif du nombre de pixels de chaque groupe est
pris en compte dans le bloc de référence (RB, figure 1).
Un circuit de sous-échantillonnage selon l' invention comporte autant d'entrées que la fenêtre de recherche à traiter comporte de colonnes, c'est-à-dire autant dentrées quil y a de
mots mémoire par ligne à traiter.
Selon l 'invention, les blocs B1 à Bg sont traités 3 par 3 de façon à minimiser le nombre d'opérations à exécuter. Le traitement 3 par 3 correspond au nombre de recouvrements de blocs qu'il y a dans la fenêtre de recherche dans chacune des directions. Pour chaque série de blocs, on prévoit autant de sommateurs qu'il y a de valeurs moyennes dans chaque ligne du bloc de domaine. En reprenant l'exemple précédant, on prévoit une ligne de sommateurs S11 à S18 pour le premier groupe de blocs B1, B4 et B7 à traiter. Chaque sommateur S11 à S18 reçoit en entrée quatre valeurs prélevées dans la mémoire M1. Chaque sommateur S11 à S18 est associé en sortie à un accumulateur A11 à A18 destiné à sommer les valeurs successives des lignes de chaque groupe de pixcls constituant une valeur moyenne du bloc
de domaine concerné.
Selon l' invention, les accumulateurs sont commandables en incrémentat ion ou en décrémentat ion de la valeur accumulée par la valeur courante. En figure 3, les accumulateurs Aij (i représentant la ligne à laquelle appartient l'accumulateur ou le sommateur, et j représentant le rang horizontal de la valeur moyenne des domaines concernés) ont été symbolisés par des blocs à deux entrées, une première entrée étant rebouclée sur la sortie tandis qu'une deuxième entrée est reliée à la sortie du sommateur Sij correspondant. Les accumulateurs sont commandables non seulement en configuration addition ou soustraction de la
valeur courante, mais également en remise à zéro si nécessaire.
En reprenant l'exemple du traitement de la fenêtre de recherche de la figure 1, la première ligne de sommateurs S11 à
S18 est reliée aux colonnes respectives 1 à 32 de la mémoire M1.
La deuxième ligne de sommateurs S21 à S28 est reliée aux colonnes respectives 2 à 33 de la mémoire M1. La troisième ligne de sommateurs S31 à S38 est reliée aux colonnes 3 à 34 de la
mémoire M1.
Selon un mode de réalisation préféré de la présente invention, la division est effectuée en ne prenant qu'un certain nombre de bits de poids fort du résultat obtenu dans les accumulateurs. Le nombre de bits retenu dépend du facteur de division souhaité. Dans le cas d'un mot binaire sur 12 bits et d'une division par 16, on ne prend que les 8 bits de poids fort du résultat obtenu. Cela revient à effectuer une division par seize, arrondie au plus petit entier. Un tel mode de division est particulièrement simple et présente les avantages notables de ne nécessiter aucun circuit de calaul ni de temps de cycle pour effectuer ce calcul. Le prix à payer est une approximation par valeur inférieure. Une telle approximation n'est toutefois pas préjudiciable dans la mesure o le résultat est de toute façon un sous-échantillonnage. En figure 3, la sélection des 8 bits de poids fort a été illustrée par des coupures des liaisons des accumulateurs aux mémoires. La sélection revient à ne
prendre que 8 fils sur les 12 fils des liaisons.
Selon l' invention, les résultats des accumulateurs respectifs sont stockés dans trois mémoires de résultat MR1, MR2, MR3 (ou trois zones d'une même mémoire) correspondant aux blocs de domaine obtenus regroupés par colonnes. Le stockage dans les mémoires de résultat est effectué à chaque fois qu'un accumulateur contient une valeur complète. Cette synchronisation est effectuée au moyen d'un circuit de commande qui sera décrit
par la suite de façon fonctionnelle.
Le résultat obtenu dans cette mémoire correspond, de préférence, aux blocs de domaine stockés de façon entrelacée, la lecture des mémoires de résultat étant alors commandée de façon adéquate pour restituer les blocs de domaine correctement. En variante, la lecture se fera ligne à ligne mais la mémorisation des résultats des accumulateurs dans les différentes mémoires est commandée de façon appropriée. Le mode de réalisation correspondant à un stockage entrelacé simplifie l'enregistrement dans la mesure o il suffit d'incrémenter les adresses des
mémoires de résultat d'une unité à chaque nouvel enregistrement.
L'adressage de la mémoire M1 s'effectue, de
préférence, ligne par ligne (adresses AD1, AD2, etc.).
Selon l 'invention, la commande du circuit de sous
échantillonnage est effectuce de la facon suivante.
On commence par lire la première ligne de la mémoire M1 et les sommes respectives fournies par les sommateurs Sij sont additionnées dans les accumulateurs respectifs Aij
préalablement initialisés à zéro.
On lit ensuite successivement les deuxième, troisième et quatrième lignes de la mémoire M1, et les sommations par groupe de quatre colonnes au moyen des circuits Sij sont additionnées aux valeurs précédentes des accumulateurs Aij. En fin de quatrième ligne, on obtient, dans les accumulateurs respectifs, les premières lignes de valeur des blocs de domaine
D1, D2 et D3.
Ces valeurs sont alors stockées dans les premières
lignes des mémoires de résultat MR1, MR2 et MR3 respectivement.
Les valeurs moyennes qui sont calculées ensuite correspondent aux premières lignes des blocs de domaine D4, D5 et D6. Pour cela, on commence par relire la première ligne de la mémoire M1 et les sommes respectives par groupe de quatre colonnes des niveaux de gris sont soustraites des valeurs précédemment accumulées dans les accumulateurs Aij. Ils contiennent alors le cumul des lignes 2, 3 et 4. On lit ensuite la cinquième ligne de la mémoire M1 que l'on somme au contenu des accumulateurs Aij par groupe de quatre colonnes. Le résultat des accumulateurs (lignes 2, 3, 4 et 5) est ensuite déchargé vers les deuxièmes lignes respectives des mémoires MR1, MR2 et
MR3 en subissant la division éventuelle.
L'étape de calcul de valeur moyenne suivante consiste à soustraire la deuxième ligne de la mémoire M1 et à ajouter la sixième ligne. Le résultat obtenu alors correspond à la première
2 0 ligne des valeurs moyennes des blocs de domaine D7, D8 et D9.
Pour le calcul des valeurs moyennes de la deuxième ligne des blocs de domaine D1 D2 et D3, deux solutions sont possibles. Une première solution consiste à réinitialiser les accumulateurs et à lire successivement les lignes 5, 6, 7 et 8 2 5 accumulées de façon positive pour constituer les valeurs moyennes recherchées. Une deuxième solution consiste à relire le s l ignes 3 et 4 pour les soustraire de s valeurs précédemment accumulées puis à lire les lignes 7 et 8 et les additionner aux résultats des accumulateurs. Quelle que soit la solution prise, cette étape requiert quatre cycles de calculs et d'accès mémoire. La deuxième solution constitue cependant un mode de réalisation préféré dans la mesure o elle permet une simplification de l'algorithme de séquencement de la commande de circuit de sous-échantillonnage. En effet, cette solution respecte la succession d'étapes de soustraction et d'addition dans les accumulateurs. I1 suffit de commencer par soustraire la ligne 3 et ajouter la ligne 7, puis soustraire la ligne 4 et
aj outer la ligne 8.
Le séquencement décrit ci-dessus se poursuit pour le reste de la mémoire M1 jusqu'à obtenir la dernière ligne des blocs de domaine D7, D8 et D9 correspondant à la dernière
lecture de la ligne 34 de la mémoire M1.
Le nombre total de cycles de calculs nécessaires pour sous-échantillonner l' ensemble de la mémoire dans l'exemple ci dessus est de 64 cycles (correspondant au nombre de pixels d'un bloc sous-échantillonné). Par cycle, on entend la période de temps nécessaire pour effectuer un adressage et une lecture de
la donnée dans la mémoire ainsi que l 'addition correspondante.
Cette addition sieffectue cependant sans consommation temporelle dans la mesure o elle peut être effectuée au moyen de simples portes logiques. Le temps de cycle correspond plus généralement au temps d'accès mémoire majoré du temps d'addition et
d' accumulation.
Le nombre de 64 cycles indiqué ci-dessus est à comparer à un nombre de 16x9x64 cycles nécessaires en cas d'adressage d'une mémoire par sous groupes de 16 pixels (4x4) pour calculer les valeurs moyennes successives dans le cas classique. Un avantage de la présente invention est qu'elle permet de réduire considérablement le nombre des accès mémoire et le temps requis pour sous-échantillonner une fenêtre de recherche. Un autre avantage de l' invention est qu'elle est particulièrement simple à mettre en oeuvre de facon matérielle
avec des circuits simples.
Bien entendu, la présente invention est susceptible de diverses variantes et modifications qui apparaîtront à l'homme de l'art. En particulier, bien que l' invention ait été décrite 3 5 ci-dessus en relation avec un exemple d' application à une fenêtre de recherche de codage fractal, celle-ci sapplique plus généralement quelle que soit la taille de la fenêtre de recherche et le nombre de blocs d' images recouvrants que l'on doit sous-échantillonner. De façon générale, en considérant une image ou fenêtre de recherche de n*m pixels définissant la taille (nombre de lignes et nombre de colonnes) de la mémoire M1, et en supposant des blocs à sous-échantillonner de p*q pixels avec pn et q<m, la mise en oeuvre de l' invention peut se décrire de la façon suivante. On doit tout d'abord supposer que les blocs de p*q pixels se chevauchent ou sont recouvrants, c'est-à-dire que le nombre k de blocs dans l'alignement vertical est supérieur à n/p et que le nombre l de blocs dans l'alignement horizontal est supérieur à m/q. Le nombre k définit le nombre de blocs entrelacés dans chaque mémoire de résultat MR. Le nombre l définit le nombre de mémoires de résultat, donc de lignes de sommateurs et de lignes d'accumulateurs. Le nombre de colonnes des mémoires de résultat, qui correspond au nombre de sommateurs et d'accumulateurs par ligne, est fonction du rapport de sous-échantillonnage souhaité dans le sens
horizontal, de même que le nombre d'entrées de chaque sommateur.
Le nombre total de sommateurs et d'accumulateurs correspond donc au nombre de pixels des blocs résultat dans le sens horizontal multiplié par le nombre de blocs dans le sens vertical. Le rapport de sous- échantillonnage souhaité dans le sens vertical est contrôlé par le circuit de commande en déchargement des accumulateurs dans les mémoires de résultat. Le nombre de lignes de chaque mémoire de résultat correspond au nombre de blocs dans le sens vertical, multiplié par la dimension (p) du bloc dans le sens vertical et divisé par le rapport de sous- échantillonnage dans ce sens vertical, donc au nombre de blocs dans le sens vertical multiplié par le nombre de pixels des blocs résultat
dans le sens vertical.
La réalisation pratique du circuit de sous-
échantillonnage et de ses sélecteurs et circuits de commande est à la portée de l'homme du métier à partir des indications fonctionnelles données ci-dessus. De plus, la mise en oeuvre de 1' invention pour d'autres applications que celle décrite à titre d'exemple est également à la portée de l'homme du métier à partir des indications fonctionnelles et de généralisation données ci-dessus. Enfin, l' invention s'applique quelle que soit les données à traiter contenue dans la mémoire image. Il pourra s'agir de niveaux de gris dans le cas d' image noir et blanc ou de niveaux de couleur, ou encore de données relatives au contraste des différents pixels. Le nombre de bits de chaque mot mémoire représentant un pixel dépend de l 'application et n'est pas critique au sens de la présente invention. Par ailleurs, les dernières lignes de la mémoire image peuvent subir un traitement particulier pour le cas o les tailles des blocs à sous échantillonner conduisent à un nombre de lignes ne s'inscrivant pas exactement dans la mémoire image. Il en est de méme pour les
dernières colonnes.
Claims (10)
1. Procédé de sous-échantillonnage de données image pixelisées regroupées par blocs (B) se chevauchant, caractérisé en ce qu'il comprend les étapes suivantes lire, ligne par ligne, une mémoire image (M1) contenant l' image pixclisée; accumuler autant de lignes que le prévoit le rapport de sous-échantillonnage dans le sens vertical, en utilisant autant de groupes d'accumulateurs (Aij) qu'il y a de blocs dans le sens horizontal de l' image et autant d'accumulateurs par groupe que le prévoit le rapport de sous-échantillonnage dans le sens horizontal; et mémoriser les valeurs accumulées dans autant de mémoires de résultat (MR) qu'il y a de groupes d'accumulateurs, chaque mémoire de résultat contenant des matrices sous échantillonnées d'un nombre de blocs correspondant au nombre de
blocs se chevauchant dans la direction verticale.
2. Procédé selon la revendication 1, caractérisé en ce
que la mémorisation est effectuée de façon entrelacée.
3. Procédé selon la revendication 1 ou 2, caractérisé en ce qu'il consiste à diviser les valeurs accumulées par le produit des rapports de sous-échantillonnage dans les deux directions, pour obtenir des valeurs moyennes à mémoriser en
tant que sous-échantillons.
4. Procédé selon la revendication 3, caractérisé en ce que la division d'une valeur accumulée de plusieurs lignes de la mémoire image pour obtenir une valeur moyenne est obtenue en ne tenant compte que d'un nombre de bits les plus significatifs,
inférieur au nombre de bits de la valeur résultat.
5. Procédé selon l'une quelconque des revendications 1
à 4, caractérisé en ce que les lignes de la mémoire image (M1) sont lues successivement depuis la première pour un nombre de lignes correspondant au rapport de sous-échantillonnage dans la direction verticale, et en ce qu'on lit ensuite alternativement
la première ligne suivante et une ligne précédemment utilisée.
6. Circuit de sous-échantillonnage de données images pixelisées et reparties en blocs (B) se chevauchant, caractérisé en ce qu'il comprend: un nombre de sommateurs (Sij) correspondant au nombre de pixels de blocs résultat dans une première direction, multiplié par le nombre de blocs dans une deuxième direction; un nombre d'accumulateurs (Aij) identique au nombre de sommateurs; et un nombre de mémoires de résultat (MR) des valeurs sous-échantillonnées correspondant au nombre de blocs dans la
première direction.
7. Circuit selon la revendication 6, caractérisé en ce que les accumulateurs (Aij) sont commandables en addition ou en soustraction d'une valeur courante au résultat accumulé
précédemment.
8. Circuit selon la revendication 6 ou 7, caractérisé en ce que le nombre d'entrées de chaque sommateur correspond au
rapport de sous-échantillonnage dans la première direction.
9. Circuit selon l'une quelconque des revendications 6
à 8, caractérisé en ce que lesdites mémoires de résultat (MR) comprennent un nombre de lignes correspondant au nombre de blocs dans la deuxième direction, multiplié par le nombre de pixels
des blocs résultat dans la deuxième direction.
10. Circuit selon l'une quelconque des revendications 6
à 9, caractérisé en ce que le nombre de bits d'une valeur résultat stocRée dans l'une desdites mémoires de résultat est inférieur au nombre de bits des valeurs des données images pixelisées, la différence entre les deux nombres de bits définissant le rapport de division d'obtention de la valeur
Priority Applications (5)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| FR0117032A FR2834397A1 (fr) | 2001-12-28 | 2001-12-28 | Sous- echantillonnage de donnees images pixelisees |
| EP02805812A EP1459559A2 (fr) | 2001-12-28 | 2002-12-27 | SOUS−ECHANTILLONNAGE DE DONNEES IMAGES PIXELISEES |
| JP2003557217A JP2005513689A (ja) | 2001-12-28 | 2002-12-27 | ピクセル化されたイメージデータのサブサンプリング |
| US10/500,314 US20050147326A1 (en) | 2001-12-28 | 2002-12-27 | Pixellated image data sub-sampling |
| PCT/FR2002/004580 WO2003056834A2 (fr) | 2001-12-28 | 2002-12-27 | Sous-echantillonnage de donnees images pixelisees |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| FR0117032A FR2834397A1 (fr) | 2001-12-28 | 2001-12-28 | Sous- echantillonnage de donnees images pixelisees |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| FR2834397A1 true FR2834397A1 (fr) | 2003-07-04 |
Family
ID=8871074
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| FR0117032A Pending FR2834397A1 (fr) | 2001-12-28 | 2001-12-28 | Sous- echantillonnage de donnees images pixelisees |
Country Status (5)
| Country | Link |
|---|---|
| US (1) | US20050147326A1 (fr) |
| EP (1) | EP1459559A2 (fr) |
| JP (1) | JP2005513689A (fr) |
| FR (1) | FR2834397A1 (fr) |
| WO (1) | WO2003056834A2 (fr) |
Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4656516A (en) * | 1985-03-25 | 1987-04-07 | Rca Corporation | Vertical subsampling and memory synchronization system for a picture within a picture television receiver |
| US5694149A (en) * | 1993-07-01 | 1997-12-02 | Intel Corporation | Vertically scaling image signals using digital differential accumulator processing |
| WO1999066449A1 (fr) * | 1998-06-19 | 1999-12-23 | Equator Technologies, Inc. | Decodage d'une image d'une premiere resolution donnant directement une image decodee d'une seconde resolution |
| US6091844A (en) * | 1993-10-14 | 2000-07-18 | Omron Corporation | Image processing device and method for identifying an input image and copier including same |
| EP1049044A2 (fr) * | 1999-04-29 | 2000-11-02 | Xerox Corporation | Procédé pour éviter la contrefacon |
Family Cites Families (14)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5341142A (en) * | 1987-07-24 | 1994-08-23 | Northrop Grumman Corporation | Target acquisition and tracking system |
| US5384912A (en) * | 1987-10-30 | 1995-01-24 | New Microtime Inc. | Real time video image processing system |
| US5335295A (en) * | 1991-05-08 | 1994-08-02 | International Business Machines Corporation | System and method for scaling a digital image |
| US5237432A (en) * | 1991-12-23 | 1993-08-17 | Xerox Corporation | Image scaling apparatus |
| US5400051A (en) * | 1992-11-12 | 1995-03-21 | International Business Machines Corporation | Method and system for generating variably scaled digital images |
| US5717394A (en) * | 1993-02-10 | 1998-02-10 | Ricoh Company Ltd. | Method and apparatus for encoding and decoding data |
| EP0626661A1 (fr) * | 1993-05-24 | 1994-11-30 | Societe D'applications Generales D'electricite Et De Mecanique Sagem | Circuit de traitement d'images digitales |
| US5790714A (en) * | 1994-11-01 | 1998-08-04 | International Business Machines Corporation | System and method for scaling video |
| US5712799A (en) * | 1995-04-04 | 1998-01-27 | Chromatic Research, Inc. | Method and structure for performing motion estimation using reduced precision pixel intensity values |
| US6108047A (en) * | 1997-10-28 | 2000-08-22 | Stream Machine Company | Variable-size spatial and temporal video scaler |
| US6424751B2 (en) * | 1998-09-23 | 2002-07-23 | Xerox Corporation | Apparatus and method for efficient implementation of 2-dimensional pixel window averaging |
| AU1823400A (en) * | 1998-11-17 | 2000-06-05 | Quantum3D, Inc. | Device and method for antialiasing high resolution pixel data for lower resolution display |
| EP1107107A1 (fr) * | 1999-12-10 | 2001-06-13 | Koninklijke Philips Electronics N.V. | Traitement de données en parallèle et permutation |
| US6420979B1 (en) * | 2000-11-15 | 2002-07-16 | Nec Corporation | Method for compressing and decompressing image signals and apparatus for compressing and decompressing image signals |
-
2001
- 2001-12-28 FR FR0117032A patent/FR2834397A1/fr active Pending
-
2002
- 2002-12-27 WO PCT/FR2002/004580 patent/WO2003056834A2/fr active Application Filing
- 2002-12-27 JP JP2003557217A patent/JP2005513689A/ja not_active Withdrawn
- 2002-12-27 US US10/500,314 patent/US20050147326A1/en not_active Abandoned
- 2002-12-27 EP EP02805812A patent/EP1459559A2/fr not_active Withdrawn
Patent Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4656516A (en) * | 1985-03-25 | 1987-04-07 | Rca Corporation | Vertical subsampling and memory synchronization system for a picture within a picture television receiver |
| US5694149A (en) * | 1993-07-01 | 1997-12-02 | Intel Corporation | Vertically scaling image signals using digital differential accumulator processing |
| US6091844A (en) * | 1993-10-14 | 2000-07-18 | Omron Corporation | Image processing device and method for identifying an input image and copier including same |
| WO1999066449A1 (fr) * | 1998-06-19 | 1999-12-23 | Equator Technologies, Inc. | Decodage d'une image d'une premiere resolution donnant directement une image decodee d'une seconde resolution |
| EP1049044A2 (fr) * | 1999-04-29 | 2000-11-02 | Xerox Corporation | Procédé pour éviter la contrefacon |
Non-Patent Citations (1)
| Title |
|---|
| ANONYMOUS: "Pipelined Convolver for Two Dimensional Images. July 1971", IBM TECHNICAL DISCLOSURE BULLETIN, IBM CORP. NEW YORK, US, vol. 14, no. 2, July 1971 (1971-07-01), pages 475 - 476, XP002116385, ISSN: 0018-8689 * |
Also Published As
| Publication number | Publication date |
|---|---|
| JP2005513689A (ja) | 2005-05-12 |
| EP1459559A2 (fr) | 2004-09-22 |
| US20050147326A1 (en) | 2005-07-07 |
| WO2003056834A2 (fr) | 2003-07-10 |
| WO2003056834A3 (fr) | 2004-02-26 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP0204603B1 (fr) | Circuit de calcul rapide de la transformée en cosinus, directe ou inverse, d'un signal discret | |
| EP0248729B1 (fr) | Dispositifs de calcul de transformées cosinus monodimensionnelles, et dispositif de codage et dispositif de décodage d'images comportant de tels dispositifs de calcul | |
| EP0492702B1 (fr) | Dispositif de correlation | |
| FR2504762A1 (fr) | Systeme de mise en conference de type reparti pour un reseau de telecommunications | |
| FR2599873A1 (fr) | Systeme d'affichage video | |
| WO2010037570A1 (fr) | Dispositif de traitement en parallele d'un flux de donnees | |
| EP0298002B1 (fr) | Mémoire de transposition pour circuit de traitement de données | |
| FR2834397A1 (fr) | Sous- echantillonnage de donnees images pixelisees | |
| FR2565382A1 (fr) | Appareil de reorganisation de donnees | |
| FR2718590A1 (fr) | Procédé de détection d'un motif dans une transmission série. | |
| FR2475250A1 (fr) | Multiplieur rapide | |
| FR2780184A1 (fr) | Procede et dispositif de decodage d'images, permettant un nombre reduit d'ouvertures de pages-memoire dans le traitement de prediction | |
| EP0674444B1 (fr) | Filtre de matrices de pixels | |
| EP0716395A1 (fr) | Procédé pour le décodage d'images comprimées | |
| FR2703802A1 (fr) | Dispositif d'estimation de mouvement entre des images successives d'une séquence d'images animées subdivisées en blocs bidimensionnels d'éléments d'image. | |
| FR2600223A1 (fr) | Procede de formattage et de deformattage de donnees resultant du codage d'informations numeriques a l'aide d'un code a longueur variable, et dispositif de mise en oeuvre | |
| EP0407311B1 (fr) | Circuit de brassage de données | |
| FR2787669A1 (fr) | Procede d'adressage pour la memorisation de blocs d'image | |
| EP1459260A2 (fr) | Adressage de memoire de blocs de reference en codage fractal | |
| EP0778545A1 (fr) | Procédé et dispositif d'estimation de mouvement | |
| EP0567377B1 (fr) | Procédé de pistage à partir d'images d'éléments déformables, et/ou aux contours fortement bruités | |
| FR2556902A1 (fr) | Procede et dispositif de filtrage de rang determine d'un signal numerique et application au filtrage median bidimensionnel separable | |
| EP0046105B1 (fr) | Dispositif opérateur numérique rapide | |
| EP0668557A1 (fr) | Circuit de réorganisation de données | |
| FR2882185A1 (fr) | Procede et dispositif de traitement d'image |