Get inner rectangle of wonky image on transparent background

[fmw42]

Personally, I think all this is going overboard. There are too many special cases to try to solve. I am of the opinion that IM should have a basic algorithm that trims excess background are around the outside of an image. This will cover the most likely use case of the majority of image that people need to trim, such as slight rotations or simple borders. I think the main script that works outside inward that chops of the edge with the most background area (after a flood fill) is likely what would be acceptable. The inside trim likely needs a seed location to start it, which is one extra argument. However, perhaps both approaches would be useful. What do you guys think? For simple one region cases, would there be a difference in outside in versus inside out?

[fmw42]

I guess there would be differences between outside in and inside out, if there were any background color pixels interior to the single region of interest.

[snibgo]

I think the proposed operation, and its limitations, should be clearly defined. Otherwise users will keep coming back asking for tweaks to the algorithm.

What do you guys think? For simple one region cases, would there be a difference in outside in versus inside out?

Yes, there is a difference, as the outside-inwards version can leave background colours inside the rectangle, as you say. In addition, I show on Inner Trim that even in simple one-region cases, different seed points can give different results.

[mviereck]

I am of the opinion that IM should have a basic algorithm that trims excess background are around the outside of an image. This will cover the most likely use case of the majority of image that people need to trim, such as slight rotations or simple borders.

I agree. The current solution will likely cover most use cases. At this point the concept is simple and effective.

The inside trim likely needs a seed location to start it, which is one extra argument. However, perhaps both approaches would be useful.

If there is an easy way to automatically find a useful seed point, the inside-out way could be better. In that case a custom seed point could be given optionally and be a great value for special use cases, but users wouldn't be forced to provide it.

If auto-detection of a seed point is too hard and the seed point must be specified, the easier way outside-in should be available in any case.

I guess there would be differences between outside in and inside out, if there were any background color pixels interior to the single region of interest.

This could be solved with a flood fill of the border with an unused color like in the example above.


One open point is the color definition. The current -trim auto-decides which color(s) to trim, but unfortunately misses an option to set the color.
trim_hard2 expects a color as an option. It would be nice if the color could be either auto-detected or specified optionally.

[snibgo]

The current solution will likely cover most use cases.

For me, that's not good enough.

If there is an easy way to automatically find a useful seed point, the inside-out way could be better.

A two phase approach seems good: outside-inwards to get a line of seed points, then inside-outwards to expand the line to the maximal rectangle.

This isn't as simple as either algorithm alone. It guarantees the rectangle contains no pixels of boundary colour (which is good or bad, depending on what we want).

I'm currently testing it.

[fmw42]

A two phase approach seems good: outside-inwards to get a line of seed points, then inside-outwards to expand the line to the maximal rectangle.

But I thought you said you get different result from different seed points. Is that only the case when you have more than one region? Does it always give the same result if there are no background colored pixels inside the region.

Also will it not be slower if you consider that most of the image in most cases will contain more inside rows/columns to test than outside rows/columns?

[snibgo]

Different seed points give different solutions, because bhere is no unique locally-maximal rectangle.

I'm trying to devise an algorithm that guarantees to find a solution if there is one. The performance in a script with repeated reads of the source is lousy. In well-written C, it might take twice as long as a similar "-trim".

[fmw42]

I have my outside inward processing working in a bash test script. I do not actually chop off the rows and columns from the sides, but simply increment counters as I crop each row and column and compare to the min of the mean values. Then at the end, I simply chop as many rows and columns from each side that are needed in one convert command. It cut my time for one particular image from 26 s to 16 s.

Note: I permit the user to specify a coordinate to get the background color (default northwest corner) or to specify the background color directly. Then I add a 1 pixel border of that color and flood fill to convert the color to transparency and do a -trim. Then I export the alpha channel and test that for the means. I am not concerned about a few pixels inside the rectangle region that might be background color. I mainly want to trim off outer regions of background color.

I would not be concerned it your resulting tool, when converted or written in C, is twice as long as a simple -trim. We know this is a brute force appoach and will be slower.

I think it will be handy to have such a new feature in Imagemagick even if slow.

[mviereck]

I've found a solution that finds rectangles in previously failing images. I'll call it trim_hard3

The previous trim_hard2 only checks sides. This can fail in cases where more than one center is possible and the checked geometry contains entirely empty rows or columns. This can be seen well in the last seconds of snibgo's animated gif above.

This version trim_hard3 does an area check before it checks the sides.
- If the area contains empty rows or columns, the part with greater mean is removed. (The search for empty rows/columns begins in the middle of the area.)
- Only if there is no empty row or column, the side with greatest mean is removed.
- Repeat.

The script is quite slow. It is just a proof of concept for an outside-inwards approach entirely based on mean values.
It has a good chance, but no guarantee to find the greatest possible rectangle if there are several similar sized islands.
The expensive part is a check of each row and column on each iteration. That can be improved.
Currently I have no failing test images.

Results:
(30 seconds)

(9 minutes)

(36 minutes)

Code: Select all

#! /bin/bash

showimage() {
  display "${1:-}" &
}
cropcolorpermille() {
  # Function: Calculate permille part of pixels of color $2 in crop rectangle $3 of image $1
  # $1  $Image         image
  # $2  $Trimcolor     color to count
  # $3  $Cropgeometry  crop rectangle to search in
  # Output: Permille part of color in crop region
  
  local Image Trimcolor Cropgeometry
  local Colorcount Cropwidth Cropheight Permille
  
  Image="${1:-}"
  Trimcolor="${2:-}"
  Cropgeometry="${3:-}"
  
  Cropwidth=$(cut -dx -f1 <<< "$Cropgeometry")
  Cropheight=$(cut -dx -f2 <<< "$Cropgeometry" | cut -d+ -f1)

  Colorcount="$(convert "$Image" -crop "$Cropgeometry" txt: | grep -c "$Trimcolor")"
  # second way to count color, a bit slower.
#  Colorcount="$(convert "$Image" -crop "$Cropgeometry" -fill black +opaque "$Trimcolor"  -format %c histogram:info: | grep "$Trimcolor")"
#  Colorcount="$(awk '{print $1}' <<< "$Colorcount" | cut -d: -f1)"

  Permille=$((1000 * $Colorcount / ($Cropwidth*$Cropheight) ))
  echo "${Permille:-0}"
}
trim_hard3() {
  # Function: Trim all border with color $2 from image $1
  # Results in a maximal inner rectangle without border color.
  # $1  $Image      image
  # $2  $Trimcolor  color to trim. Default: transparent
  # Output: crop geometry
  
  local Image Trimcolor
  local Imagewidth Imageheight
  local Left         Right         Top         Bottom
  local Skipleft     Skipright     Skiptop     Skipbottom
  local Permilleleft Permilleright Permilletop Permillebottom Permillemax
  local Row Column Emptyrow Emptycolumn Partialcroppermille1 Partialcroppermille2 Width Height
  local Return
  local Debugmode Loopcount
  
  Image="${1:-}"
  Trimcolor="${2:-"#00000000"}"
  
  Imagewidth=$(convert  -format '%w'  $Image info:)
  Imageheight=$(convert -format '%h'  $Image info:)
  
  Left=0
  Top=0
  Right=$((Imagewidth-1))
  Bottom=$((Imageheight-1))
  
  # First cut with regular trim to save some time.
  # Add a colored border so trim uses the desired color. Afterward remove border from canvas to get correct geometry values. 
  Line="$(convert "$Image" -bordercolor "$Trimcolor" -border 1x1  -trim -set page '%[fx:page.width-2]x%[fx:page.height-2]+%[fx:page.x-1]+%[fx:page.y-1]' info:)"
  Left="$(awk '{print $4}' <<< "$Line" | cut -d+ -f2)"
  Top="$(awk '{print $4}' <<< "$Line" | cut -d+ -f3)"
  Right="$(awk '{print $3}' <<< "$Line" | cut -dx -f1)"
  Right="$((Left+Right-1))"
  Bottom="$(awk '{print $3}' <<< "$Line" | cut -dx -f2)"
  Bottom="$((Top+Bottom-1))"

  # Concept:
  # - Area check: [might be substituted with -connected-components]
  #   - Check for empty rows and columns, starting from the middle.
  #   - If there are empty rows or columns, divide area and skip the part with greater amount of $Trimcolor.
  # - Border check:
  #   - If no empty rows or colums are found, trim side with greatest permille (mean) value of $Trimcolor.
  # - Repeat
  while :; do
  
    ## Step 1: Area check ##
    # Check for a row/column that consists entirely of $Trimcolor and would split an inner rectangle. 
    # (A pure border check can fail in that case.)
    Width=$((Right-Left+1))
    Height=$((Bottom-Top+1))
    Halfwidth=$((Width/2))
    Halfheight=$((Height/2))
    # check for empty rows between Top and Bottom, starting from the middle.
    for ((i=1 ; i<Halfheight ; i++)); do
      Row=$((Halfheight-i))
      [ "1000" = "$(cropcolorpermille "$Image" "$Trimcolor" ${Width}x1+$Left+$((Top+$Row)) )" ]   && Emptyrow="$Row"       && break || Emptyrow=""
      Row=$((Halfheight+i-1))
      [ "1000" = "$(cropcolorpermille "$Image" "$Trimcolor" ${Width}x1+$Left+$((Top+$Row)) )" ]   && Emptyrow="$Row"       && break || Emptyrow=""
    done
     # check for empty columns between Left and Right, starting from the middle.
    for ((i=1 ; i<Halfwidth ; i++)); do
      Column=$((Halfwidth-i))
      [ "1000" = "$(cropcolorpermille "$Image" "$Trimcolor" 1x${Height}+$((Left+Column))+$Top)" ] && Emptycolumn="$Column" && break || Emptycolumn=""
      Column=$((Halfwidth+i-1))
      [ "1000" = "$(cropcolorpermille "$Image" "$Trimcolor" 1x${Height}+$((Left+Column))+$Top)" ] && Emptycolumn="$Column" && break || Emptycolumn=""
    done

    # If current geometry is splitted by empty row/column, skip the part with more $Trimcolor inside.
    Width=$((Right-Left+1))
    Height=$((Bottom-Top+1))
    [ "$Emptyrow" ] && {
      Partialcroppermille1=$(cropcolorpermille $Image "$Trimcolor" ${Width}x$((Emptyrow))+$Left+$Top)
      Partialcroppermille2=$(cropcolorpermille $Image "$Trimcolor" ${Width}x$((Height-Emptyrow+1))+$Left+$((Top + Emptyrow-1)) )
      [ "$Partialcroppermille1" -gt "$Partialcroppermille2" ] && Top=$((Top+Emptyrow+1)) || Bottom=$((Top+Emptyrow-1))
    }
    Width=$((Right-Left+1))
    Height=$((Bottom-Top+1))
    [ "$Emptycolumn" ] && {
      Partialcroppermille1=$(cropcolorpermille "$Image" "$Trimcolor" $((Emptycolumn))x${Height}+$Left+$Top)
      Partialcroppermille2=$(cropcolorpermille "$Image" "$Trimcolor" $((Width-Emptycolumn+1))x${Height}+$((Left+Emptycolumn-1))+$Top)
      [ "$Partialcroppermille1" -gt "$Partialcroppermille2" ] && Left=$((Left+Emptycolumn+1)) || Right=$((Left+Emptycolumn-1))
    }
    
    ## Step 2: Border check ##
    # If no empty rows/columns are left, trim side with greatest mean/permille of $Trimcolor
    [ "${Emptyrow}${Emptycolumn}" = "" ] && {
      # Get permille of $Trimcolor at each side
      Width=$((Right-Left+1))
      Height=$((Bottom-Top+1))
      Permilleleft=$(cropcolorpermille   $Image "$Trimcolor" 1x${Height}+$Left+$Top)
      Permilleright=$(cropcolorpermille  $Image "$Trimcolor" 1x${Height}+$Right+$Top)
      Permilletop=$(cropcolorpermille    $Image "$Trimcolor" ${Width}x1+$Left+$Top)
      Permillebottom=$(cropcolorpermille $Image "$Trimcolor" ${Width}x1+$Left+$Bottom)
    
      # Determine maximal permille value
      Permillemax=$(echo "
$Permilleleft
$Permilleright
$Permilletop
$Permillebottom
" | sort -n | tail -n1)
      [ "$Permillemax" = "0" ] && break # Ready
      
      # Remove side with greatest permille amount of $Trimcolor.
      [ "$Permillemax" = "$Permilleleft" ]   && Left=$((Left+1))
      [ "$Permillemax" = "$Permilleright" ]  && Right=$((Right-1))
      [ "$Permillemax" = "$Permilletop" ]    && Top=$((Top+1))
      [ "$Permillemax" = "$Permillebottom" ] && Bottom=$((Bottom-1))
    }
    
    # Out-of-range error
    { [ "$Left" -gt "$Right" ] || [ "$Top" -gt "$Bottom" ] ; } && {
      echo "Error: Failed to find an inner rectangle. Unuseable result: $((Right-Left+1))x$((Bottom-Top+1))+$Left+$Top" >&2
      Return=1
      Left=0
      Top=0
      Right=$((Imagewidth-1))
      Bottom=$((Imageheight-1))
      break
    }
    
    # Debugging: show intermediate results
    #Debugmode=yes
    [ "$Debugmode" ] && {
      Loopcount=$((Loopcount+1))
      [ "$Loopcount" = "10" ] && {
        Loopcount=0
        convert $Image -fill none -stroke red -strokewidth 1 -draw "rectangle $Left,$Top $Right,$Bottom" $Image.trim_hard.png
        showimage $Image.trim_hard.png
      }
    }
  done
  
  # Output of result
  #echo "$Left,$Top $Right,$Bottom"                     # "-draw rectangle" geometry
  echo $((Right-Left+1))x$((Bottom-Top+1))+$Left+$Top  # "-crop" geometry
  
  # Create image with red rectangle at crop coordinates and show it
  convert $Image -fill none -stroke red -strokewidth 1 -draw "rectangle $Left,$Top $Right,$Bottom" $Image.trim_hard.png
  showimage $Image.trim_hard.png
  
  return ${Return:-0}
}
trim_hard3 "$@"

[fmw42]

I am really not sure why go to all the trouble for the above, since you can extract all the green regions using connected-components. Going further, once could extract all regions above a certain size using CCL and then run either an outside inward or inside outward trim method on each region.

On the otherhand, I do not mean to discourage your activity. You both have gone quite far in adding more features to the simple outside inward approach.

[snibgo]

On mviereck's propsal, of checking for empty rows and columns: this is expensive, and would be in C code, but (a) ensures that any solution found is locally maximal, and (b) may avoid the problem with negative width or height. See below.


The outside-inwards scripts shown above loop round, removing edges from the rectangle until one of two conditions is met:

1. All edge pixels are not boundary colour, so a solution is found, and it is locally maximal.

2. The width or height of the rectangle is negative, so a solution has not been found, and the algorithm has failed.

To me, the problem is condition (2), which can occur even when a solution is possible.

A cure is to remove an edge only if this would not make the width or height negative. So: if the width is currently zero (right==left), we can only remove from the top or bottom. If the height is zero, we can only remove from the left or right. If both width and height are zero, we have a single pixel and can't remove any side, so the algorithm ends. If that single pixel is background, the algorithm has failed. If it is not background, the algorithm has found a solution, but it probably isn't locally maximal, and can be used as a seed for an inside-outwards algorithm.

I think that if the image has any non-background pixels, the final single pixel will always be non-background. In other words: if a solution is possible, this will find a solution. But I'm not certain of this.

I think the amended algorithm will always find a solution (provided a solution is possible). If it isn't locally maximal, an inside-outward algorithm can make it so.

This works so far in tests with a Windows BAT script. My bash skills are feeble, so I'll leave that exploration to mviereck or anyone.

[snibgo]

On checking for empty rows and columns:

The first time round, rows and columns should both be checked. Each following time, if we have trimmed left or right we only need to check for empty rows, because no columns have changed. And if we have trimmed top or bottom we only need to check for empty columns.

This halves the expense of the test.

[snibgo]

On checking for empty rows (and similarly for empty columns):

In a script, running "convert" and reading the image for every row is expensive. It can be simplified to a single convert by scaling to a single column, chopping this in half, inverting the first half, and appending.

Here, I assume "empty" means "black".

Windows BAT syntax:

Code: Select all

set SRC=34636180qx.png

%IMG7%magick ^
  %SRC% ^
  -fill Black +opaque White ^
  -negate ^
  -scale "1x^!" ^
  -crop 1x2@ +repage ^
  ( -clone 0 -flip ) ^
  -delete 0 ^
  +append ^
  x.png

x.png has 2xN pixels. The problem is now reduced to: find the top-most black pixel in x.png, if any.

Code: Select all

%IMG7%magick compare ^
  -metric RMSE ^
  -subimage-search ^
  x.png ^
  xc:Black ^
  NULL:

If the subimage-search finds an exact match, the column (0 or 1) tells us whether it was in the lower or upper half.

Instead of a subimage-search, we can turn non-black into white, add a white border and trim white, and examine the top two pixels. This is usually faster than searching, but maybe not for these small images.

EDIT: The proposed algorithm for empty rows etc works fine if there are only two candidate solutions. When there are more than two, the splitting may result in a rectangle that needs further splitting, which would happen in the next pass of the loop. If two small pieces are larger in total than one large piece, one of the smaller pieces will eventually be selected.

It may be cleaner to test from the top, instead of from the middle outwards. Then the splitting always finds the top-most candidate, and we know this candidate cannot (yet) be split.

[mviereck]

The proposed algorithm for empty rows etc works fine if there are only two candidate solutions. When there are more than two, the splitting may result in a rectangle that needs further splitting, which would happen in the next pass of the loop. If two small pieces are larger in total than one large piece, one of the smaller pieces will eventually be selected.

Yes, that is an issue. There are further weak points that mislead the algorithm where we can't rely on a closer check of empty rows and columns. trim_hard3 will never find the big rectangle on the right, but will result in a small one on the left:


While the mean value check for borders is fine, it has some weak points for area checks. It avoids the previous failures of trim_hard2 with border check only, but cannot recognice the largest island.

Btw., your ideas to improve the row/column check are clever and inspiring!

Probably the best way is to detect islands with connected-components on every iteration. I had a first look at this option, its output looks quite useful. If it works well, the row/column check could be dropped.

[fmw42]

You do not need to find islands on each iteration, if I understand. You can filter the CCL output to export only the coords of the largest regions. Then process that only.