Java Flood Fill

Som Java-arkitekt är det underbart att ibland få fly bort från de större problemen och få sitta ostörd i ett litet hörn och knåpa med små fiffiga algoritmimplementationer. Det senaste lilla trivsamma i den kategorin jag fick möjlighet att besöka gällde flood fill i en BufferedImage.

Flood fill går till så att man pekar på en pixel i en bild så sätts denna pixel och alla dess närliggande pixlar med samma färg till en ny önskad färg.

Mitt system kraschade plötsligt i flood fill algoritmen med StackOverflowError på 32-bits VM men funkade fin-fint med 64-bit. Jag kastade mig över detta hanterbara lilla problem.

Kraschen var i följande kod:

public void floodFillRecursive(int x, int y,
                               Color targetColor,
                               Color replacementColor) {
      if (x >= 0 && x < imageWidth && 
          y >= 0 && y < imageHeight &&
          image.getRGB(x, y) == targetColor.getRGB()) {

         image.setRGB(x, y, replacementColor.getRGB());
         floodFillRecursive(x - 1, y, targetColor, replacementColor);
         floodFillRecursive(x + 1, y, targetColor, replacementColor);
         floodFillRecursive(x, y - 1, targetColor, replacementColor);
         floodFillRecursive(x, y + 1, targetColor, replacementColor);
      }
   }

Varför finns den koden inte i ett externt lib? Det borde ju rimligen finnas tjogvis med färdiga implementationer, t.ex. i java2d eller apache commons eller nån annanstans.

Efter att ha kastat “Java Flood Fill” på Google så blir första träffen en tråd på Stacktrace där just denna kod finns med. Inte ett spår efter någon alternativ, testad och väl fungerande rutin jag kan lyfta in, ens med någon nytt maven-beroende.

Hm. Världen är grund ibland. Man krafsar lite på ytan så krakellerar det eller så når man snabbt ungefär fram dit mänskligheten hittils nått i ämnet i fråga. Lite som när man grävde lite djupare i sandlådan när man var liten, om någon mer än jag minns det, och man började gräva upp stenblandad ful oanvändbar jord istället. Det var inte så kul då heller. Fast det finns ju förstås en del bivillkor involverade för att man skall uppleva att världen är grund, t.ex. att man håller sig ifrån att gräva på ställen där till exempel Stephen Hawking grävt. Typ.

Tillbaka till stacktrace-tråden då.

Det där är en rekursiv, snabb och enkel rutin. Areorna jag skulle fylla var små så det borde rimligen räcka, men det gjorde det alltså inte - och inte för trådskaparen heller. Jag hade svårt att tro det men en test gav att det räcker att arean som skall fyllas är 64x64 pixlar för att stacken som i java är default 512KB skall ta slut. Det är inte intuitivt tycker jag. Och algoritmen växer inte exponentiellt med areastorlek utan antalet loopar är konstant runt 4 ggr antalet pixlar, ingen loppa där alltså. För att klara images på 2000x2000 pixels var jag tvungen att skrämma upp trådstacken i en halv GB! Jag tror att jag skall skippa tanken på rekursiva algoritmer på pixeldata i framtiden, man tänker lätt fel.

En rekursiv algoritm går vanligen utmärkt att skriva om så den itererar istället. Det är väl bara att göra det då, men varför måste jag göra det själv?!? Det är annars en sak jag har vant mig av med under de senaste åren - att skriva generell kod själv inom projektet. Det finns nästan alltid ett lib man kan lyfta in och använda. Efter ytterligare lite googlande förkastade jag det ena fula kodhärket efter det andra. Okej då, själv bäste dräng, precis som i gamla men inte så goda tider när libc var den enda kod man själv inte skrivit som man vågade stå på.

Låt oss först ge oss på enklaste möjliga lösning. Vi behöver en alternativ stack (pointsToVisit) där man i varje loop lägger upp de pixlar man härnäst skall besöka. Detta blir så att säga substitutet för rekursionen.

  public void floodFillIterative(int x, int y, 
                                 Color targetColor, 
                                 Color replacementColor) {
    final int targetPixelColor = targetColor.getRGB();
    final int replacementPixelColor = replacementColor.getRGB();
    final Deque pointsToVisit = new ArrayDeque();
    nextPoint(x, y, targetPixelColor, pointsToVisit);
    while (!pointsToVisit.isEmpty()) {
      final Point p = pointsToVisit.pop();
      image.setRGB(p.x, p.y, replacementPixelColor);
      nextPoint(p.x + 1, p.y, targetPixelColor, pointsToVisit);
      nextPoint(p.x - 1, p.y, targetPixelColor, pointsToVisit);
      nextPoint(p.x, p.y + 1, targetPixelColor, pointsToVisit);
      nextPoint(p.x, p.y - 1, targetPixelColor, pointsToVisit);
    }
  }

  private void nextPoint(int x, int y, 
                         int targetPixelColor, 
                         Deque pointsToVisit) {
    Point p = new Point(x, y);
    if (x >= 0 && x < imageWidth && y >= 0 && y < imageHeight &&
        targetPixelColor == image.getRGB(x, y)) {
      pointsToVisit.push(p);
    }
  }

Eftersom vi inte sparar vilka pixlar vi besökt så kommer vi att besöka samma pixel flera gånger, precis som i den rekursiva versionen.

Hur är det med prestanda? Den rekursiva tog 266 ms för 1M pixels, och omskriven iterativt enligt ovan tar den 451 ms. Rekursiv kod är snabbare är grundregeln, så det är väl okej då. Hur är det med minnet? För den rekursiva tog minnet i form av trådstack slut. För att kunna köra 1M enligt ovan krävs en stack på 100MB! (-Xss100m) Detta är långt bortom rimligheternas gränser. Nu har vi visserligen betydligt mer heap än stack men heapen är inte oändligt och är bra att ha till annat också. En test gav att den nya stackens (pointToVisit) maximala storlek blev 0.5M element! I varje element ligger ett objekt som består av två integers → 0.5M*32bytes=16MB på en 64-bitars VM. Dvs cirka 4 ggr större än vår BufferedImage (varje pixel är 4 bytes, RGBA). Ops. Om jag uttrycker mig som så att jag inte tycker att detta är en bra lösning, så är jag säker på att jag inte överdriver.

Det finns åtminstånde två saker man kan göra för att minska antalet iterationer och begränsa minnesbehovet.

1 Inte lägga upp en point i pointsToVisit som redan ligger där
2 Hålla reda på vilka punkter vi varit på och hoppa över dessa

Gemensamma krav för 1 och 2 är att man snabbt kan hitta om en viss punkt finns eller ej i en samling (contains). 2 kräver att man snabbt kan hitta nästa punkt i samlingen och ta bort den (pop). Ett HashSet uppfyller det första kravet men inte det andra. Lite ointuitivt är det, men det går inte att effektivt hitta ett objekt i ett HashSet utan att veta var det är, så inte ens typ metoden popAny i någon form går att få. För 1 blir då ett NavigableSet med implementationen TreeSet lösningen. En trist bieffekt av att använda NavigableSet är att objekten man lagrar måste implementera Comparable, varför java.awt.Point går bort. Vi måste alltså implementera vår egen Point-klass också. Suck.

Om man funderar vidare så vill man inte lagra varje Point vi behandlat i ett Set, eller någon annan container heller, där vi slutar med att ha lika många Point-objekt som vi har pixlar i bilden. Så för 2 gäller en boolean array eller kanske BitSet. Dessa blir bara en bråkdel så stora som vår BufferedImage.

public void floodFillBitSet(int x, int y, 
                            Color targetColor,
                            Color replacementColor) {
    BitSet dispatchedPoints = new BitSet();
    final NavigableSet pointsToVisit = new TreeSet();
    final int targetPixelColor = targetColor.getRGB();
    final int replacementPixelColor = replacementColor.getRGB();
    nextPoint(x, y, targetPixelColor, pointsToVisit, dispatchedPoints);
    while (!pointsToVisit.isEmpty()) {
      final Point p = pointsToVisit.pollFirst();
      image.setRGB(p.x, p.y, replacementPixelColor);
      dispatchedPoints.set(p.y * imageWidth + p.x);
      nextPoint(p.x + 1, p.y, targetPixelColor, pointsToVisit, dispatchedPoints);
      nextPoint(p.x - 1, p.y, targetPixelColor, pointsToVisit, dispatchedPoints);
      nextPoint(p.x, p.y + 1, targetPixelColor, pointsToVisit, dispatchedPoints);
      nextPoint(p.x, p.y - 1, targetPixelColor, pointsToVisit, dispatchedPoints);
    }
  }

  private void nextPoint(int x, int y, 
                         int targetPixelColor,
                         NavigableSet pointsToVisit,
                         BitSet dispatchedPoints) {
    Point p = new Point(x, y);
    if (x >= 0 && x < imageWidth && y >= 0 && y < imageHeight &&
            targetPixelColor == image.getRGB(x, y) &&
            !dispatchedPoints.get(p.y * imageWidth + p.x)) {
      pointsToVisit.add(p);
      dispatchedPoints.set(p.y * imageWidth + p.x);
    }
  }

Denna BitSet-baserade implementation slår visserligen inte den rekursiva implementationen i fart men ligger i samma storleksordning med 540 ms mot 266 ms.

Minnet då? Om vi har offrat lite hastighet och vill ha tillbaka sparat minne. Man brukar ju få byta minne mot fart. Den rekursiva tar 100MB i form av trådstack medan floodFillBitSet bara en bråkdel av 1MB (pointsToVisit=3321*32B → 106KB, dispatchedPoints=1M/8 → 128KB). "Check" säger vi om det.

Ytterligare en optimering vi kan göra är att byta BitSet mot en boolean-array, men då är vi tvugna att allokera upp storleken för hela vår BufferedImage i arrayen. Om arean vi skall fylla är substantiellt mindre än vår BufferedImage kräver floodFillBitSet mindre minne. Prestandamässigt kommer vi med array-lösningen ned på 421 ms med marginellt högre minnesanvändning.

image=1024x1024
FloodFillerRecursive            266 ms loops=   4194305 factor=4,00 maxQueueSize=0
FloodFillerIterative            456 ms loops=   2095105 factor=2,00 maxQueueSize=524800
FloodFillerIterativeBitSet      540 ms loops=   1048576 factor=1,00 maxQueueSize=3321
FloodFillerIterativeArray       423 ms loops=   1048576 factor=1,00 maxQueueSize=3321

JDK 6 eller JDK 7 på Windows 7 eller Ubuntu Linux ger bara försumbara skillnader resultaten.

Komplett körbar kod med Maven 3 och enhetstest finns här: https://marell.se/svn/labs/floodfill

För att öppna koden direkt i t.ex. Intellij IDEA, välj Version Control, Checkout from version Control, Subversion.

IT Consultant at CAG Edge. Cloud and Continuous Delivery specialist, software developer and architect, Node.js, Java.

Publicerad i Java

Kategorier

WP to LinkedIn Auto Publish Powered By : XYZScripts.com