Obrazkowy bruteforce

Wczoraj uświadomiłem sobie, że skoro piksel (w bitmapach 24-bitowych) przyjmuje wartości R,G i B z zakresu 0-255, to istnieje 256^3 (czyli 16 777 216) kombinacji jednego piksela. Bitpama 2-megapikselowa zawiera 1600×1200=1 920 000 pikseli, czyli istnieje (256^3)^1920000 => (((2^8)^3)^1920000) => 2 ^ 46080000 kombinacji bitmap dwumegapikselowych…

Przypuścmy, że istnieje komputer kwantowy, który wygenerowałby wszystkie 2 ^ 46 080 000 kombinacje takowych bitmap Jakie zdjęcia znalazłyby się w tej “bazie”? Każde Np. każda chwila z Twojego życia widziana z każdej możliwej kamery, dodatkowo na każdym możliwym tle, z kiełbasą, drukarką, papieżem i kartonie po mleku na pierwszym planie…

Ty z 23 nogami, Ty uprawiający seks ze zwierzętami, Ty siędzący w tej chwili przed komputerem czytający ten wątek, najpiekniejsze zdjęcie na świecie, zdjęcia z nieodkrytych planet, zdjęcia nieistniejących marsjaninów z tobą w tle jedzącym słonecznik i to wszystko w różnych poziomach zaszumienia od wysokiego/niskiego ISO oraz wiele wiele innych ciekawych zdjęć A te “sensowne” zdjęcia to mikroskopijna część tych wszystkich 2 ^ 46 080 000, bo reszta to jakieś kolorowe śmieci…

Tamyl @ DigArt

Mnie ten tekst zainteresował ze strony programistycznej. Napisałem prosty skrypt w PHP (:P), który metodą bruteforce generuje sobie takie kolejne obrazki. W drodze uproszczeń obrazki są tylko kwadratami, a liczba kolorów ograniczona do dwóch. Już przy wymiarach 4×4 liczba kolejnych obrazków przyrastała niesamowicie szybko.

Dla ciekawskich zamieszczam niżej kod klasy. Całość jest prosta, banalna wręcz. Algorytm wydaje się być poprawny, natomiast całość mogłaby być inaczej (czyt. lepiej) napisana. Może kiedyś spróbuję zaimplementować w kod klasy możliwość zatrzymywania i wznawiania kolejnych iteracji. Ciekaw jestem jak takie coś zrobić.

<?php
/**
 * @class ImgGen
 *
 * @author radmen <radmen_at_gmail.com>
 * @license WTFPL <http://sam.zoy.org/wtfpl/>
 */
class ImgGen {
  
  private $mImgSize = 3;
  
  private $mColors = array();
  
  private $mImage;
  
  private $mImgCount = 0;
  
  private $mFileType = 'gif';
  
  public function __construct() {
    $this->mImage = imagecreatetruecolor($this->mImgSize, $this->mImgSize);
    
    $this->mColors = array(
        'black' => imagecolorallocate($this->mImage, 0, 0, 0),
        'white' => imagecolorallocate($this->mImage, 255, 255, 255),
    );
    
  }
  
  public function CreateImg() {
    
    foreach ($this->mColors as $name => $color) {
      $this->Iterate(0, $name);
    }
  }
  
  private function Iterate($pIteration, $pColorName, & $pPoints = false) {
    
    if(false === $pPoints) {
      $pPoints = array();
    }
    
    if($pIteration == ($this->mImgSize * $this->mImgSize)) {
      $this->Save2File($this->mFileType, $pPoints);
      return;
    }
    
    $x = $pIteration % $this->mImgSize;
    $y = floor($pIteration / $this->mImgSize);
    
    // echo "x: {$x} y: {$y}\n";
    
    $pPoints[$pColorName][] = array(
      'x' => $pIteration % $this->mImgSize,
      'y' => floor($pIteration / $this->mImgSize),
    );
    
    foreach ($this->mColors as $name => $color) {
      $this->Iterate($pIteration+1, $name, & $pPoints);
    }
  }
  
  private function Save2File($pType, $pPoints) {
    
    $path = 'imgs/'.md5($this->mImgCount++);

    if(false === file_exists(dirname($path))) {
      mkdir(dirname($path), 0777);
    }
    
    foreach($pPoints as $color_name => $points) {
      foreach($points as $point) {
	imagefilledrectangle($this->mImage, $point['x'], $point['y'], $point['x'], $point['y'], $this->mColors[$color_name]);
      };
    }

    if('gif' == $pType) {
      imagegif($this->mImage, $path.".gif");
    }
    else {
      imagepng($this->mImage, $path.'.png');
    }
  }
  
  public function __toString() {
    return $this->mImgCount." obrazkow wygenerowano\n";
  }
  
}
?>

17 Responses to “Obrazkowy bruteforce”

  1. Dodek October 6, 2009 at 9:36 pm #

    PROTIP: Tych możliwych kombinacji jest więcej niż atomów we wszechświecie.

  2. viralion October 6, 2009 at 9:36 pm #

    Cuś chyba nie generuje tak jak powinno…

  3. mt3o October 6, 2009 at 9:36 pm #

    Zrób to w C, dla obrazków o większej rozdzielczości i ilości barw, daj większy skok, odrzucaj te bardziej podobne do siebie i coś z tego programu będzie.
    Gdyby tak jeszcze wyświetlać na ekran ostatnio wygenerowane obrazki i dać możliwość cofnięcia do n’tego poprzedniego obrazka, można by te ciekawsze wychwycić z niewielką pomocą urządzenia znajdującego się między krzesłem i klawiaturą.

  4. viralion October 6, 2009 at 9:36 pm #

    Generuje tysiące obrazków, wszystkie czarne, tylko ostatnia linia się zmienia…

  5. Cichy October 6, 2009 at 9:36 pm #

    A ja ciekaw jestem, jak bardzo trzeba się nudzić, żeby tracić czas na takie zabawy. Wiadomo, że od strony programistycznej zadanie jest banalne – skoro wszystko jest liczbą, to nic prostszego jak wypisywanie kolejnych liczb w jakimś tam formacie. Chcesz się wykazać – dodaj do tej klasy sito, które odcedzi sensowne obrazki spośród śmieci, a będziesz wielki;-).

  6. Dodek October 6, 2009 at 9:36 pm #

    Nie, to nie ma sensu ;) Naprawdę, zanim wyjdzie coś sensownego to drzewa zapuszczą korzenie w waszych kościach.

  7. Satanowski October 6, 2009 at 9:36 pm #

    To rzeczywiście nie ma sensu :-) .
    Dla obrazka 8×8 px czyli praktycznie plamki, przy użyciu zaledwie 2 kolorów, np. czarnego i białego mamy: 2^64=18446744073709551616 możliwych obrazów. Nawet gdyby generować 1000obrazow/s na 1000 komputerów jednocześnie, wciąż potrzebowalibyśmy 18446744073709sekund, czyli 805675 lat.

  8. remiq October 6, 2009 at 9:36 pm #

    “Ta pornografia dziecięca to tylko wytwór komputerowego generowania obrazów, Panie Sędzio.”
    ;)

  9. viralion October 6, 2009 at 9:36 pm #

    Jeszcze musiałbyś to udowodnić ;p

  10. remiq October 6, 2009 at 9:36 pm #

    O ile wciąż żyjemy w państwie prawa, domyślnie jesteś niewinny. Oni muszą udowodnić, że tak nie jest ;) Ale fakt, wytłumaczenie wytrzymałoby jakieś 5 minut. I jest nieefektywne w przypadku Polańskiego. ;)

  11. chester October 6, 2009 at 9:36 pm #

    A gdyby pójść dalej i skorzystać z pomocy np. takiego gugla ? wszak maszyn trochę ma, trochę mocy udzieli choćby przez google app engine..
    A później wszystko do picasaweb, jest rozpoznawanie twarzy więc sam znajdzie odpowiednie ;) )

  12. egzemplarz October 6, 2009 at 9:36 pm #

    @Dodek
    Dlatego potrzebujemy komputera kwantowego ;) .

  13. radmen October 6, 2009 at 9:36 pm #

    Oj, wiem, że w ogóle to ten skrypt nie ma sensu. W wolnym czasie przepiszę go sobie na Pythona (ot tak, żeby sobie przepisać i przypomnieć język).

    @viralion: hmm sprawdzałem ten skrypt na najbardziej banalnych przypadkach i tam jakoś zamalowywał wszystkie pola.

    @all: pomijając kwestie algorytmu i czasu wykonania to trzeba by również mieć całkiem sporo miejsca na dysku :)

  14. mateyko October 6, 2009 at 9:36 pm #

    I tak wszyscy umrzemy

  15. wariat October 6, 2009 at 9:36 pm #

    hmmm no to generujemy, obrazkow czarno-bialych 16*16 jest tylko 2^16^2 = 115792089237316195423570985008687907853269984665640564039457584007913129639936, kazdy ma 32 bajty czyli … kiedy beda takie dyski? :D
    pozniej tylko wyslac je na flickr i wszystkie czarno-biale ikonki na swiecie (16×16) CC-BY :D powodzenia :D

  16. Dodek October 6, 2009 at 9:36 pm #

    2^16^2 to więcej, niż jest atomów we wszechświecie.

  17. D4rky October 6, 2009 at 9:36 pm #

    Ty uprawiający seks ze zwierzętami,

    Eeee… to ty może lepiej nie baw się za dużo… :P