Combinatoires

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
kitsumary
Messages: 3
Enregistré le: 21 Nov 2016, 21:28

Combinatoires

par kitsumary » 21 Nov 2016, 23:01

Bonjour à tous,

Je suis nouveau sur le forum et j'espère que ma question sera claire.
Il ne s'agit pas d'un problème lié à des cours, mais bien une question liées à mes recherches en tant que plasticien (art).
Je ne crois pas avoir les connaissances nécessaires en mathématiques pour la résoudre.
Il s'agit d'écrire une formule exprimant un ensemble de combinaisons en fonction de paramètres variables.
Puis de déceler des états remarquables de la combinaison pour affiner le résultat.

Voici l'énoncé du problème, c'est assez simple :

Une image est de longueur x et de hauteur y.
Chacun de ces pixels peut adopter une couleur comprenant une combinaison de trois paramètres : rouge, vert ou bleu pouvant aller de 0 à 255.
On cherche le nombre total d'images à imprimer pour obtenir toutes les combinaisons de pixels possibles dans une image d'une taille donnée.

mon résultat jusque là étant quelque chose comme : i =(x*y)^(r*v*b)
i = nombre d'images, x = largeur de l'image, y=hauteur, r=rouge, v=vert, b=bleu
je souhaiterais que quelqu'un me dise si c'est juste ou non car lorsque je fais le moindre test avec une image de 100px par 100px, le résultat semble si élevé que toutes les calculatrices que j'ai tenté d'utiliser jusqu'à présent ont affiché "erreur"...

Deuxième étape, je cherche en fait à réduire le résultat final pour pouvoir : l'écrire à la main !

Pour cela, si je ne me trompe pas, il faudrait trouver des cas remarquables puis les soustraire de la formule ?

les images de couleurs unies (ça si je ne m'abuse, c'est (x*y)*(r*v*b)) ou présentant trop peu de variation colorimétrique ?
les images dans lesquelles chaque point est entouré de pixels d'une couleur sensiblement différente de la sienne (bruit )
les images où les agencements des pixels forment des cas remarquables (suites, récurrences, géométries) ?
... autres ?

Savez vous comment faire ça ?

:?: :?: :?: :?: :idea: :mrgreen: :idea: :geek: :idea: :mrgreen: :idea: :geek: :idea: :mrgreen: :idea: :?: :?: :?: :?:



Valentin03
Membre Relatif
Messages: 429
Enregistré le: 23 Déc 2012, 13:08

Re: Combinatoires

par Valentin03 » 22 Nov 2016, 11:03

Quel est le but ?

Avatar de l’utilisateur
chan79
Membre Légendaire
Messages: 10330
Enregistré le: 04 Mar 2007, 19:39

Re: Combinatoires

par chan79 » 22 Nov 2016, 11:20

Bonjour
Il faudrait d'abord connaître le nombre de pixels

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21709
Enregistré le: 11 Nov 2009, 21:53

Re: Combinatoires

par Ben314 » 22 Nov 2016, 12:19

Salut,
Déjà, la formule "théorique" n'est pas boone.
Si tu as une image de 640x480 pixels et que la couleur de chaque pixels est décrite par des composantes de Rouge, de Vert et de Bleu allant de 0 à 255 (soit 256 valeurs différentes) alors
- Pour un pixel donné, il y a C=256x256x256=16 777 216 (16 millions) de couleurs théoriquement possible (mais à l'œil nu, on a évidement du mal à toutes les discerner)
- Au total, il y a P=640x480=307 200 pixels sur l'image.
- Comme pour chaque pixel, il y a C possibilités, le nombre total de possibilités est de qui est évidement extrêmement grand.

Ensuite, la façon raisonnable et classique d'avoir un ordre de grandeur d'un nombre de cette taille, c'est de calculer son logarithme (décimal) pour savoir combien de chiffres il possède.
.
Le nombre en question contient donc approximativement 2 millions de chiffres ou, si tu préfère, il est environ égal à .
Comme les calculette numériques s'arrêtent souvent à et les ordi. à (="double précision" de la norme IEEE 754 utilisé par les processeurs actuels) tu est effectivement très loin au delà.

Enfin, que ce nombre soit "gigantesque", c'est archi connu et ça explique pourquoi, lorsque l'on trimbale des images (sur le net ou à l'intérieur d'un appareil photo numérique ou autre), on les "compresse" en utilisant le fait que des pixels proches ont souvent des couleurs proches donc qu'on arrive à "décrire" approximativement l'image avec bien moins d'info. que la connaissance exacte de la couleur de chaque pixel.
Cette "compression", c'est par exemple le cas des images au format JPEG qu'on trouve absolument partout : dans ce format, l'image est "légèrement modifié" au niveau des couleurs pour pouvoir être comprimée "au maximum", et la taille du fichier est en général infiniment plus petite que la taille de l'image "de départ" stockée pixel par pixel (format type BitMaP par exemple)
Et évidement, c'est encore pire pour les films composés d'un grand nombre d'images et où il est inimaginable de stocker pixel par pixel les images successives du film : là, tout les format de stockage utilisent de la "compression" qui provoque une certaine perte de qualité.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

kitsumary
Messages: 3
Enregistré le: 21 Nov 2016, 21:28

Re: Combinatoires

par kitsumary » 23 Nov 2016, 00:51

Re-Bonjour
:D
Tout d'abords, merci beaucoup de vos réponses !

@Valentin : Oh, tu sais, en art comme au foot, les buts... non, en vrai, il y en a plus de deux. ;)
Tout d'abord, de connaître cet ordre de grandeur (ce qui n'était pour moi pas si évident, et là, Ben314 a tout à fait répondu à ma question).
Ensuite, il faut savoir que je travailles pour un mémoire, sur la question des abstractions en peinture. Étant donné du fait que des plasticiens travaillent en générant des images par ordinateur, il était important pour moi de pouvoir poser des bornes à cette pratique.
En l'occurrence, il s'agit de potentiels gigantesque ! Mais pas infini.
Lorsque l'on génère des images de façon aléatoire, il existe des probabilités pour que ne serait-ce que l'une d'entre elles soit figuratives. Wouah ! Une telle apparition serait un cas de passages de l'abstraction à la figuration, à travers une approche "algorithmique" de l'art !
C'est un phénomène que j'étudie (et j'entends par là que j'étudie le "wouah" en tant que cris d'exclamation mais bref).

En tout cas, sans vouloir tout mélanger, je crois ne pas avoir bien expliqué dans mon précédant message,
la deuxième partie de ma question.
En fait j'ai oublié un bon paragraphe...

En effet, je n'ai pas tout à fait défini le nombre de pixel des images que j'étudie, mais c'est tout simplement parce que ce n'est pas nécessaire, un x et un y me suffisent puisque ce qui m'intéresse au final, c'est de voir si une équation peut permettre d'approximer la probabilité qu'une image non abstraite apparaisse, dans le cas où l'on imprimerait toutes les combinaisons de pixels potentielles dans une image de taille x.
Voilà pourquoi une part de ma question concerne les réductions du nombre de résultat, ou du moins, une indication quand aux méthodes ou aux domaines des mathématiques qui permettent de proposer un calcul viable dans ce but.
Et enfin, toujours, de savoir si je pourrais écrire ce calcul à la main ? (non, là je rigole du coup.)
Pour préciser ma question, je mentionnais le fait que par image abstraite, j'entends des paternes, des monochromes, des bruits... etc

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21709
Enregistré le: 11 Nov 2009, 21:53

Re: Combinatoires

par Ben314 » 23 Nov 2016, 01:17

Si la question est posé en termes clairs et sans la moindre ambiguïté, alors on peut essayer de te donner le nombre d'images ayant les désirata demandés, voire éventuellement une approximation de ce nombre.

Par exemple, si par monochromatique, tu entend que tout les pixels soit exactement de la même couleur, alors il y a effectivement images possible.

Mais par contre, de calculer le nombre d'images "présentant trop peu de variation colorimétrique", ça, c'est évidement pas possible à calculer (ni même à évaluer) vu que c'est pas clair du tout ce que ça signifie.
De même, j'ai bien peur qu'on ne puisse absolument rien dire concernant le nombre "d'images non abstraites" vu que le concept de "non abstrait" est bien trop flou pour qu'on puisse dire quoi que ce soit.

Sinon, si j'ai pris des valeurs numériques réelle, c'est principalement pour avoir un résultat réel à la fin (le nombre de chiffres), sinon, tout ce que j'ai écrit c'est parfaitement valable pour n'importe quelle taille d'image et n'importe quel format de couleur pour les différents pixels : à une certaine époque, il était assez standard de prendre Rouge de 0 à 31 ; Vert de 0 à 63 ; Bleu de 0 à 31 de façon à avoir 65536 couleurs différentes (=1 mot de 2 octets par pixel)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

kitsumary
Messages: 3
Enregistré le: 21 Nov 2016, 21:28

Re: Combinatoires

par kitsumary » 23 Nov 2016, 02:43

Ok, je pense que j'ai les réponses qu'il fallait à mes questions du coup !!

si jamais :
https://fr.wikipedia.org/wiki/Reconnaissance_de_formes

Avatar de l’utilisateur
fatal_error
Membre Légendaire
Messages: 6610
Enregistré le: 22 Nov 2007, 12:00

Re: Combinatoires

par fatal_error » 23 Nov 2016, 09:37

je veux pas être négatif, mais dans tous les cas, il faut que __tu__ donnes au moins une info à l'algorithme pour qu'il tente de reconnaitre cette forme (et ou dans le cas d'algo random, ben de donner un crossover (genre un truc qui fait que tu vas "converger" vers certaines formes)

Dans tous les cas, il faut runner les algorithmes donc c'est pas un résultat "instant".

S'il s'agit de compter les images "non" abstraites, je te suggèrerais de partir de motif simples (genre une tete, un carré voir une polyligne) puis d'en compter les occurrences...(par translation, homotéthie, rotation, changement de couleur, ajout de bruit...) ce qui est pas immédiat.
Plus complexe (et chronophage), de prendre une banque d'images, qui constitue ta "base" de motifs, et rebelotte.

Ce pb est franchement pas facile (ne serait-ce que pour poser les limites de là ou tu t'arrêtes) (et dans tous les cas fastidieux), et j'émets certains doute quant à la pertinence de ton travail si tu poursuis dans cette direction!

tout les format de stockage utilisent de la "compression" qui provoque une certaine perte de qualité

en cherchant hier, il semble que dans certains cas il soit utile d'avoir des algo sans pertes (pour l'échange de film avant production, archivage...) et que par exemple h264 permette de compresser la vidéo sans perte. (je n'ai pas regardé le ratio toute fois) source:http://stackoverflow.com/questions/6701805/h264-lossless-coding
la vie est une fête :)

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21709
Enregistré le: 11 Nov 2009, 21:53

Re: Combinatoires

par Ben314 » 23 Nov 2016, 11:55

fatal_error a écrit:en cherchant hier, il semble que dans certains cas il soit utile d'avoir des algo sans pertes (pour l'échange de film avant production, archivage...) et que par exemple h264 permette de compresser la vidéo sans perte. (je n'ai pas regardé le ratio toute fois) source:http://stackoverflow.com/questions/6701805/h264-lossless-coding
Je suis allé regarder sur wiki mais vu la complexité du bidule (et le nombre d'options), j'ai pas été foutu de trouver la réponse...
Sinon, effectivement, sur le principe, je ne doute pas que ça existe, mais vu la taille que ça doit représenter pour un film "réel" (i.e. provenant d'une caméra et pas fabriqué image par image), ça doit quand même être plus que rarissime comme utilisation (pour des films réels).

Sinon le truc qui m'a étonné (et c'est surtout pour ça que je poste), c'est le fait qu'il y ait un brevet sur le bidule : je pensait qu'y compris aux U.S., les algos, c'était comme les maths, c'est à dire qu'il était impossible de poser des brevets. Tu sait de quoi il retourne exactement ?
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
fatal_error
Membre Légendaire
Messages: 6610
Enregistré le: 22 Nov 2007, 12:00

Re: Combinatoires

par fatal_error » 23 Nov 2016, 14:21

Tu sait de quoi il retourne exactement ?

je suis pas avocat, mais en cherchant patent h264
il semble qu'il y ait un paradoxe:
l'algorithme n'est pas patentable MAIS une description de processus oui.
http://yaroslavvb.blogspot.fr/2011/02/h ... in-us.html

l'explication un peu plus théorique:
http://softwareengineering.stackexchang ... e-patented

En cherchant les patents couvrant h264:
http://www.mpegla.com/main/programs/AVC ... tList.aspx, et en prenant les patents US
en cherchant le mot clé algorithme:
pour les trois premiers patents
http://patft1.uspto.gov/netacgi/nph-Par ... 0&f=S&l=50
aucune occurrence n'est trouvée ...

bref aux US, tu peux brevetter une méthode mais pas un algorithme....
la vie est une fête :)

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21709
Enregistré le: 11 Nov 2009, 21:53

Re: Combinatoires

par Ben314 » 23 Nov 2016, 16:59

fatal_error a écrit:bref aux US, tu peux brevetter une méthode mais pas un algorithme....
P..., je sais pas trop comment ça se traduit en Anglais "Méthode" et "Algorithme" ni ce qu'il y a dans un dico. concernant ces deux mots, mais ça doit quand même être chaud de chez chaud de distinguer l'un de l'autre...
Enfin, bon, ça fait du boulot pour les innombrables avocats américains...
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Valentin03
Membre Relatif
Messages: 429
Enregistré le: 23 Déc 2012, 13:08

Re: Combinatoires

par Valentin03 » 23 Nov 2016, 18:47

kitsumary a écrit:Lorsque l'on génère des images de façon aléatoire, il existe des probabilités pour que ne serait-ce que l'une d'entre elles soit figuratives.

Si tu explore de façon exhaustive toutes les combinaisons, tu aura forcément l'ensemble de tout ce qui peut être représenté, y compris tout ce qui est figuratif.
Quand aux algos, il y a les fractales qui peuvent donner des formes telles que celles générées par la nature (cristaux de givre, plantes, paysages...)

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 26 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite