algorithm to split an image into smaller ones based on "areas"

Question

So let's say I have an image, and I want to let the user give me a set of rectangles inside this image, and then I want to divide the image so that it can be used on, say, a forum, or an HTML document, and the rectangles would end up between link tags. This means that, when this bigger image is divided into smaller ones, every horizontal division will have to go from side to side, while vertical ones aren't required to do so.

Let's take this image for example:

_{(source: s-ul.eu)}

I give the algorithm these rectangles:

_{(source: s-ul.eu)}

And I want it to output different images divided by giving the horizontal axis more importance (since forums and HTML documents are like "writing", if that makes any sense), something like this:

_{(source: s-ul.eu)}

As you can see, horizontal lines have to go from side to side, while vertical lines can start at different horizontal lines.

I will then do stuff to optimize it so it doesnt end up with 5 billion images, then the bbcode etc., by myself, that's not the problem. What I'm looking for is some kind of algorithm that can do the division itself, this way (so that a horizontal line will have to go from side to side).

Answer 1

Let's assume you have the coordinates of the overlay boxes in a file called coords.txt like this:

139 49 281 220
306 46 462 225
49 167 170 338
239 142 364 320
427 100 570 291

Then you can use ImageMagick which is installed on most Linux distros and is available for macOS and Windows, just at the command line in Terminal (Command Prompt).

First, get the image dimensions:

convert scooby.png -format "%w %h" info:
620 365

Now make another image the same size but solid black:

convert -size ${w}x${h} xc:black grid.png

Now read the coords.txt file, one line at a time and for each line in there, draw 4 white lines onto the grid:

• one full width across the whole image at the top of the box,
• one full width across the whole image at the bottom of the box
• two according to the vertical sides

That looks like this:

while read x1 y1 x2 y2 ; do
   convert grid.png -fill white \
      -draw "line 0,$y1 $w,$y1" \
      -draw "line 0,$y2 $w,$y2" \
      -draw "line $x1,$y1 $x1,$y2" \
      -draw "line $x2,$y1 $x2,$y2" grid.png
done < coords.txt

That will give you this in grid.png - that should be looking familiar:

Then do a "Connected Components Analysis" finding all pixels which are 4-connected to pixels of the same colour:

convert grid.png \
   -define connected-components:verbose=true        \
   -define connected-components:area-threshold=100  \
   -connected-components 4 -normalize result.png

That gets you a labelled image where all the black rectangles you want are each identified with a unique, increasingly bright colour:

We don't actually want that - what we want is the output on the Terminal from that command which gives you all the "connected components" and looks like this:

Objects (id: bounding-box centroid area mean-color):
  0: 620x46+0+0 309.5,22.5 28520 gray(0)
  61: 620x26+0+339 309.5,351.5 16120 gray(0)
  51: 142x65+428+226 498.5,258.0 9230 gray(0)
  49: 124x65+240+226 301.5,258.0 8060 gray(0)
  1: 620x293+0+46 308.7,189.8 7930 gray(255)
  9: 157x50+463+50 541.0,74.5 7850 gray(0)
  47: 120x65+50+226 109.5,258.0 7800 gray(0)
  8: 155x50+307+50 384.0,74.5 7750 gray(0)
  60: 449x17+171+321 395.0,329.0 7633 gray(0)
  57: 255x28+365+292 492.0,305.5 7140 gray(0)
  6: 141x50+140+50 210.0,74.5 7050 gray(0)
  5: 139x50+0+50 69.0,74.5 6950 gray(0)
  11: 141x41+140+101 210.0,121.0 5781 gray(0)
  10: 139x41+0+101 69.0,121.0 5699 gray(0)
  35: 107x52+463+168 516.0,193.5 5564 gray(0)
  13: 120x41+307+101 366.5,121.0 4920 gray(0)
  27: 89x52+50+168 94.0,193.5 4628 gray(0)
  48: 68x65+171+226 204.5,258.0 4420 gray(0)
  15: 107x41+463+101 516.0,121.0 4387 gray(0)
  50: 62x65+365+226 395.5,258.0 4030 gray(0)
  29: 68x52+171+168 204.5,193.5 3536 gray(0)
  56: 124x28+240+292 301.5,305.5 3472 gray(0)
  54: 120x28+50+292 109.5,305.5 3360 gray(0)
  17: 139x24+0+143 69.0,154.5 3336 gray(0)
  33: 62x52+365+168 395.5,193.5 3224 gray(0)
  46: 49x65+0+226 24.0,258.0 3185 gray(0)
  52: 49x65+571+226 595.0,258.0 3185 gray(0)
  32: 57x52+307+168 335.0,193.5 2964 gray(0)
  24: 107x24+463+143 516.0,154.5 2568 gray(0)
  26: 49x52+0+168 24.0,193.5 2548 gray(0)
  36: 49x52+571+168 595.0,193.5 2548 gray(0)
  18: 99x24+140+143 189.0,154.5 2376 gray(0)
  30: 41x52+240+168 260.0,193.5 2132 gray(0)
  59: 120x17+50+321 109.5,329.0 2040 gray(0)
  16: 49x41+571+101 595.0,121.0 2009 gray(0)
  55: 68x28+171+292 204.5,305.5 1904 gray(0)
  34: 34x52+428+168 444.5,193.5 1768 gray(0)
  28: 30x52+140+168 154.5,193.5 1560 gray(0)
  22: 62x24+365+143 395.5,154.5 1488 gray(0)
  14: 34x41+428+101 444.5,121.0 1394 gray(0)
  53: 49x28+0+292 24.0,305.5 1372 gray(0)
  21: 57x24+307+143 335.0,154.5 1368 gray(0)
  31: 24x52+282+168 293.5,193.5 1248 gray(0)
  7: 24x50+282+50 293.5,74.5 1200 gray(0)
  25: 49x24+571+143 595.0,154.5 1176 gray(0)
  19: 41x24+240+143 260.0,154.5 984 gray(0)
  12: 24x41+282+101 293.5,121.0 984 gray(0)
  58: 49x17+0+321 24.0,329.0 833 gray(0)
  23: 34x24+428+143 444.5,154.5 816 gray(0)
  2: 306x2+0+47 152.5,47.5 612 gray(0)
  20: 24x24+282+143 293.5,154.5 576 gray(0)
  38: 120x4+50+221 109.5,222.5 480 gray(0)
  44: 107x4+463+221 516.0,222.5 428 gray(0)
  4: 157x2+463+47 541.0,47.5 314 gray(0)
  3: 155x2+307+47 384.0,47.5 310 gray(0)
  39: 68x4+171+221 204.5,222.5 272 gray(0)
  40: 66x4+240+221 272.5,222.5 264 gray(0)
  42: 62x4+365+221 395.5,222.5 248 gray(0)
  41: 57x4+307+221 335.0,222.5 228 gray(0)
  37: 49x4+0+221 24.0,222.5 196 gray(0)
  45: 49x4+571+221 595.0,222.5 196 gray(0)
  43: 34x4+428+221 444.5,222.5 136 gray(0)

Each line corresponds to one of your images. The second field tells you where it is in the image and the last field tells you its colour. We want the black ones, i.e. where colour=gray(0), because we started off with a black grid.

Let's look at the third line, which has 142x65+428+226 as its second field and colour that in semi-transparent magenta on your image:

convert scooby.png -fill "rgba(255,0,255,0.5)" -draw "rectangle 428,226 570,291" one.png

Good, so now let's cut each one out and save in its own image:

i=0
for s in "${images[@]}"; do
   printf -v name "sub-%04d.png" $i
   convert "$image" -crop "$s" "$name"
   ((i=i+1))
done

Let's see what they are called and how many there are:

ls sub*
sub-0000.png    sub-0006.png    sub-0012.png    sub-0018.png    sub-0024.png    sub-0030.png    sub-0036.png    sub-0042.png    sub-0048.png    sub-0054.png    sub-0060.png
sub-0001.png    sub-0007.png    sub-0013.png    sub-0019.png    sub-0025.png    sub-0031.png    sub-0037.png    sub-0043.png    sub-0049.png    sub-0055.png    sub-0061.png
sub-0002.png    sub-0008.png    sub-0014.png    sub-0020.png    sub-0026.png    sub-0032.png    sub-0038.png    sub-0044.png    sub-0050.png    sub-0056.png
sub-0003.png    sub-0009.png    sub-0015.png    sub-0021.png    sub-0027.png    sub-0033.png    sub-0039.png    sub-0045.png    sub-0051.png    sub-0057.png
sub-0004.png    sub-0010.png    sub-0016.png    sub-0022.png    sub-0028.png    sub-0034.png    sub-0040.png    sub-0046.png    sub-0052.png    sub-0058.png
sub-0005.png    sub-0011.png    sub-0017.png    sub-0023.png    sub-0029.png    sub-0035.png    sub-0041.png    sub-0047.png    sub-0053.png    sub-0059.png

Let's see all the pieces put onto a grid:

And also, let's look at one of the sub-images and notice we can see where it came from in the original image:

identify sub-0059.png 
sub-0059.png PNG 49x4 620x365+0+221 8-bit sRGB 139c 931B 0.000u 0:00.000

That one was at coordinates 0,221 in the original image.

---

Here is the full code.

#!/bin/bash

# Pick up filename from parameter
image=$1

# Get width and height
read w h < <(convert "$image" -format "%w %h" info:)
echo DEBUG: width=$w, height=$h

# Make image same size but black
convert -size ${w}x${h} xc:black grid.png

# Read through coords.txt adding white lines accordingly to "grid.png"
while read x1 y1 x2 y2 ; do
   convert grid.png -fill white \
      -draw "line 0,$y1 $w,$y1" \
      -draw "line 0,$y2 $w,$y2" \
      -draw "line $x1,$y1 $x1,$y2" \
      -draw "line $x2,$y1 $x2,$y2" grid.png
done < coords.txt
echo DEBUG: You can view sliced grid in file "grid.png"

# Now do a "Connected Components Analysis" and store coordinates of sub-images in array
images=( $(convert grid.png -define connected-components:verbose=true  -define connected-components:area-threshold=100 -connected-components 4 -normalize result.png | awk '/(0)/{print $2}') )

# Now chop out images from original according to coordinates
i=0
for s in "${images[@]}"; do
   printf -v name "sub-%04d.png" $i
   convert "$image" -crop "$s" "$name"
   ((i=i+1))
done

You just run:

./script scooby.png

---

Note: If you want to make the lines of the grid slightly fatter so that they can be off by a few pixels but still segment the image without tiny slithers a couple of pixels wide, you can add a stroke-width like this:

...
...
# Read through coords.txt adding white lines accordingly
while read x1 y1 x2 y2 ; do
  convert grid.png -fill white -stroke white -strokewidth 5 \
     -draw "line 0,$y1 $w,$y1" \
     ...
     ...

As an alternative, I guess you could round the coordinates that you read from the file to the nearest, say, 5 pixels (or 1% of image width), so that they tended to line up with each other.