Get inner rectangle of wonky image on transparent background

[mviereck]

First, thanks for ImageMagick! It is a great tool I begin to discover yet.

I want to get the coordinates of the inner rectangle of a wonky image on a transparent background.
The inner rectangle I look for is the biggest possible one without transparency.

Background: I make image stackshots with same perspective but different focus from microscopic motives. I am aligning the images with some hugin tools. The aligned images are fused together with enfuse to get one overall sharp image.
The aligning process distorts the single shots. and I need to find the region that is shared by all of them.
ImageMagick already helps me here with "-evaluate-sequence min": I get an image that only contains pixels that are shared by all images. If one of the source pixels is transparent, the resulting pixel is transparent, too:



Fred's innercrop script gives me the red rectangle and its coordinates. With these coordinates I can crop all source images.
So far, my problem is already solved.

I want to ask if there is a possibility to do this special task with a few lines instead of Fred's long script that I could include in my own code.
Is there something like a -trim-hard command? The regular -trim only goes up to the first non-transparent pixels. I would need a trim that removes all transparent pixels and gives me the coordinates of the result.
Any ideas?

---------
Running on Debian with:
$ convert -version
Version: ImageMagick 7.0.8-15 Q16 x86_64 2018-12-02 https://imagemagick.org
Copyright: © 1999-2018 ImageMagick Studio LLC
License: https://imagemagick.org/script/license.php
Features: Cipher DPC HDRI OpenMP
Delegates (built-in): fontconfig freetype jbig jng jpeg lzma openexr pangocairo png tiff x zlib

[fmw42]

You can do corner detection. One way is with -morphology. See my script, corners and the morphology reference http://www.site.uottawa.ca/~laganier/pu ... s/coin.pdf. Also see snibgo's corner detection at http://im.snibgo.com/find4corn.htm and his inner trim at http://im.snibgo.com/innertrim.htm

[mviereck]

Thank you!
I admit that I am overcharged with -morphology and also have difficulties to understand find4corn and innertrim scripts.
I have developed a bit of code on my own that does the job fairly well. It is not foolproof and not fast, but I understand it . (With the innercrop script I had some difficulties as it sometimes does not give the greatest possible rectangle and I do not understand why).

The script starts at each corner and compares a horizontal and vertical line ( 1 pixel x partial column/row length) for their amount of the color to trim. The line with the greater amount of color-to-trim is removed.

Output: crop geometry. Usage:

Code: Select all

trim_hard image trimcolor

Code: Select all

#! /bin/bash

cropcolorcount() {
  # Function: Count pixels of color $2 in crop rectangle $3 of image $1
  # $1  $Image      image
  # $2  $Trimcolor  color to count
  # $3  $Crop       crop rectangle to search in
  # Output: Count of color
  local Image Crop Trimcolor
  local Line
  Image="${1:-}"
  Trimcolor="${2:-}"
  Crop="${3:-}"
  Line="$(convert "$Image" -crop "$Crop" txt: | grep -c "$Trimcolor")"
  # second way to count color. Similar speed.
#  Line="$(convert "$Image" -crop "$Crop" -fill black +opaque "$Trimcolor"  -format %c histogram:info: | grep "$Trimcolor")"
#  Line="$(awk '{print $1}' <<< "$Line" | cut -d: -f1)"
  echo "${Line:-0}"
}
trim_hard() {
  # Function: Trim all borders 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 Radius
  local Counthorz Countvert Line
  
  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))
  Radius=$(( (Imagewidth + Imageheight)/12 ))   # a bit arbitrary. Weak point, not foolproof. More is slower, Less may miss the corner.
  
  # 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))"  
  
  # Workflow: 
  # - Begins in a corner
  # - Crops a horizontal and a vertical 1-pixel line with length $Radius
  # - Compares amount of $Trimcolor in both lines
  # - The line with more $Trimcolor will be removed from resulting crop geometry.
  
  # top left corner
  for ((Line=0 ; Line <=$Imageheight ; Line ++)); do
    Counthorz=$(cropcolorcount $Image $Trimcolor "${Radius}x1+$Left+$Top")
    Countvert=$(cropcolorcount $Image $Trimcolor "1x${Radius}+$Left+$Top")
    [ "$Counthorz" -gt "$Countvert" ] && Top=$((Top+1)) || { [ "$Countvert" -gt "0" ] && Left=$((Left+1)) ; }
    [ "${Counthorz}${Countvert}" = "00" ] && break
  done
  
  # top right corner
  for ((Line=0 ; Line <=$Imageheight ; Line ++)); do
    Counthorz=$(cropcolorcount $Image $Trimcolor "${Radius}x1+$((Right - Radius))+$Top")
    Countvert=$(cropcolorcount $Image $Trimcolor "1x${Radius}+$Right+$Top")
    [ "$Counthorz" -gt "$Countvert" ] && Top=$((Top+1)) || { [ "$Countvert" -gt "0" ] && Right=$((Right-1)) ; }
    [ "${Counthorz}${Countvert}" = "00" ] && break
  done
  
  # bottom left corner
  for ((Line=0 ; Line <=$Imageheight ; Line ++)); do
    Counthorz=$(cropcolorcount $Image $Trimcolor "${Radius}x1+$Left+$Bottom")
    Countvert=$(cropcolorcount $Image $Trimcolor "1x${Radius}+$Left+$((Bottom - Radius))")
    [ "$Counthorz" -gt "$Countvert" ] && Bottom=$((Bottom-1)) || { [ "$Countvert" -gt "0" ] && Left=$((Left+1)) ; }
    [ "${Counthorz}${Countvert}" = "00" ] && break
  done
  
  # bottom right corner
  for ((Line=0 ; Line <=$Imageheight ; Line ++)); do
    Counthorz=$(cropcolorcount $Image $Trimcolor "${Radius}x1+$((Right - Radius))+$Bottom")
    Countvert=$(cropcolorcount $Image $Trimcolor "1x${Radius}+$Right+$((Bottom - Radius))")
    [ "$Counthorz" -gt "$Countvert" ] && Bottom=$((Bottom-1)) || { [ "$Countvert" -gt "0" ] && Right=$((Right-1)) ; }
    [ "${Counthorz}${Countvert}" = "00" ] && break
  done
  
  # Output of result
  #echo "$Left,$Top $Right,$Bottom"                 # "draw rectangle" format
  echo $((Right-Left))x$((Bottom-Top))+$Left+$Top  # "-crop" format
  
  # Create and show image with red box at crop geometry
  convert $Image -fill none -stroke red -strokewidth 1 -draw "rectangle $Left,$Top $Right,$Bottom" $Image.trim_hard.tif
  display $Image.trim_hard.tif &
}
trim_hard "$@"

(Edit: bugfix at 2018-12-19 12pm)

Result:

[fmw42]

I have been developing a somewhat similar script that first converts the border color to transparent using a floodfill, then trims. Then it extracts the alpha channel. Then it circulates around the alpha channel sides checking each row and column to see if the mean is less than 1 (in the range 0 to 1). If so, then it crops both alpha channel and the images. Once it finds a row or column that has alpha=1 for the mean, it stops checking that side of the image. It continues until all rows and columns from corresponding sides have alpha=1 for the mean. It is brute force and could be much more efficient it coded in C. I should have that finished perhaps later today or tomorrow and will post to my web site at my link below

My method seems to trim more than you want on your image above.

[snibgo]

I had a similar need to the OP: a series of frames, each made from IM "-distort" of input video frames. The goal was to find the minimum crop that removed the boundary of every frame.

Each distort was roughly symmetrical (unlike the OP example), and the goal was to find the maximal rectangle with a given aspect ratio (eg 1920x1080).

I haven't (yet) published the code. For each image, it walks from four edge pixels (near the corners, depending on the input and desired aspect ratios) towards the centre, stopping at non-boundary pixels.

It doesn't work well on the OP image because the boundary is highly un-symmetrical.

[mviereck]

Then it circulates around the alpha channel sides checking each row and column to see if the mean is less than 1 (in the range 0 to 1). If so, then it crops both alpha channel and the images.
[...]
My method seems to trim more than you want on your image above.

I assume that happens because the checked row/column contains transparent pixels that "belong" to another side of the rectangle.
In my previous image example the first left column containes transparent pixels on top. For that reason your script removes the column although it shouldn't.
(To adress this issue my script does the time-consuming comparision of color count).

An attempt for improvement of your script could be not to check the full row/column, but only the middle part of it, e.g. with 1/3 of row/column length.
If circulating this way is ready, check on the result a greater 2/3 middle part and circulate again.
In a final turn circulate with a check on the whole row/column.

-----------------
Please note that I did a bugfix in my trim_hard script above. For the previous image example it makes a difference of 30 seconds vs. 3 minutes.
I've mixed up Counthorz and Countvert in the comparision check.
Wrong:

Code: Select all

    [ "$Counthorz" -gt "$Countvert" ] && Top=$((Top+1)) || { [ "$Counthorz" -gt "0" ] && Right=$((Right-1)) ; }

Now fixed to:

Code: Select all

    [ "$Counthorz" -gt "$Countvert" ] && Top=$((Top+1)) || { [ "$Countvert" -gt "0" ] && Right=$((Right-1)) ; }

[fmw42]

Your analysis is likely correct. I have the same thoughts after seeing that my code did not work well on your image.

I have thought about testing each side first to see which one has the most background pixels and then only chopping that one side. Then repeat that. I hope to give that a test when I can get back to it, but do not know if that will help.

[mviereck]

I have thought about testing each side first to see which one has the most background pixels and then only chopping that one side. The repeat that.

I've written a second version trim_hard2 based on exactly that approach:

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_hard2() {
  # 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 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))"
  
  # Workflow:
  # - Get permille amount of $Trimcolor from all sides.
  # - Remove side with greatest permille amount of $Trimcolor.
  # - Repeat check with new geometry
  while :; do
    # Get permille of $Trimcolor at each side
    [ "$Skipleft" ]   || Permilleleft=$(cropcolorpermille   $Image "$Trimcolor" 1x$((Bottom-Top+1))+$Left+$Top)
    [ "$Skipright" ]  || Permilleright=$(cropcolorpermille  $Image "$Trimcolor" 1x$((Bottom-Top+1))+$Right+$Top)
    [ "$Skiptop" ]    || Permilletop=$(cropcolorpermille    $Image "$Trimcolor" $((Right-Left+1))x1+$Left+$Top)
    [ "$Skipbottom" ] || Permillebottom=$(cropcolorpermille $Image "$Trimcolor" $((Right-Left+1))x1+$Left+$Bottom)
    
    # Determine maximal permille value
    Permillemax=$(echo "
$Permilleleft
$Permilleright
$Permilletop
$Permillebottom
" | sort -n | tail -n1)
    [ "$Permillemax" = "0" ] && break # Ready
    
    # Remove side with maximal permille of $Trimcolor.
    [ "$Permillemax" = "$Permilleleft" ]   && Left=$((Left+1))
    [ "$Permillemax" = "$Permilleright" ]  && Right=$((Right-1))
    [ "$Permillemax" = "$Permilletop" ]    && Top=$((Top+1))
    [ "$Permillemax" = "$Permillebottom" ] && Bottom=$((Bottom-1))
    
    # Skip check for sides without $Trimcolor in future to save some time
    [ "0" = "$Permilleleft" ]   && Skipleft=yes
    [ "0" = "$Permilleright" ]  && Skipright=yes
    [ "0" = "$Permilletop" ]    && Skiptop=yes
    [ "0" = "$Permillebottom" ] && Skipbottom=yes
    
    # 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" = "25" ] && {
        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_hard2 "$@"

On my image examples above it gives the same result as the first version.
It is slower, but less than I've expected. For the highly distorted image above it takes about 40 seconds compared to 30 seconds of first trim_hard version.

What is looses in speed, it gains in reliability. I have created some ugly test images that give different results:


trim_hard (first version) misses some gaps far from the corners:

trim_hard2 reliably finds the inner rectangle:

[fmw42]

Good news! That was my hope that it would be very reliable at the expense of speed. If so, then I might be able to convince the IM developer to code it in C in ImageMagick. I will take a look at your code when I get a chance.

[snibgo]

Code: Select all

  #echo "$Left,$Top $Right,$Bottom"                 # "draw rectangle" format
  echo $((Right-Left))x$((Bottom-Top))+$Left+$Top  # "-crop" format

One of those is wrong. A rectangle that starts at $Left and ends at $Right has a width of (Right-Left+1). Similarly height.

[mviereck]

One of those is wrong. A rectangle that starts at $Left and ends at $Right has a width of (Right-Left+1). Similarly height.

Good catch, thank you! Same bug took place in calls of cropcolorcount. Is fixed now and updated above.

------------
I've created two test images where the my maximal-color approach previously failed.
The issue appeared if the inner rectangle is far from image center. Entirely color-to-trim sides weren't removed if there are mixed sides with a greater amount of color-to-trim.
This intermediate result demonstrates the issue. The horizontal line contains more white then the vertical line:

This is now fixed calculating and comparing a permille value instead of absolute color counts:

This was a hard one:


The resulting rectangle contains some remaining white dots. But a close check shows that the red rectangle is drawn upon a continuous black rectangle:


The next step would be to work with a black/white mask and mean values. That will probably/hopefully speed it up. But that might be too much for my current knowledge of ImageMagick.

If so, then I might be able to convince the IM developer to code it in C in ImageMagick.

It would be a honour, thank you!

[snibgo]

I have a script, innerTrim2.bat, that uses a similar approach. It trims the edge that has the lowest proportion of boundary colour, and repeats. A pre-process makes the boundary black and non-boundary white, so this is simply the edge with the lowest mean.



The solution found is a rectangle with no boundary colour at any of its edge pixels, and it can't be extended on any side without violating that condition, so it is "locally maximal".

However, it doesn't guarantee to be the global maximum. Perhaps another solution exists that would give a larger rectangle.

The solution found contains boundary colour within the rectangle, but not on the edge.

It seems to me that there are two approaches to the problem: work from the outside inwards (as shown on this page) or from some inner pixel outwards (eg Inner Trim).

A hybrid approach is also possible. For example, an outside-inwards script might include a constraint that it never trims a specified coordinate, so the solution (if any) will be a rectangle that contains that coordinate.

[mviereck]

I have a script, innerTrim2.bat, that uses a similar approach. It trims the edge that has the lowest proportion of boundary colour, and repeats.

It seems you have written your answer while I was editing mine.
Now your and my script follow the same logic. The difference is only that my script calculates a permille value while yours works with a mean value. Concept and result are the same.

I've created a test image where my script fails entirely. Though, I could reason that it does not contain an inner rectangle at all. Do you have a different result or a thought on how this should be handled?


Another failing example:

A possible attempt is to floodfill the border with an unused color to distinguish from enclosed/inner parts of same color as the border:

However, that changes the result for this image:


My own use case for distorted microscopic captures is more than solved already. However, it's fun to find solutions for difficult edge cases. Some of them could be declared as out of scope, though.

[snibgo]

Should an algorithm like this be built into IM, edge cases like this would be reported as bugs by users. Or the documentation has to say "this will not always work".

Though, I could reason that it does not contain an inner rectangle at all.

I would say there are nine possible solutions. Ideally the algorithm would find the largest. I haven't found an outside-inwards algorithm that is guaranteed to find any solution, let alone the best.

By what criteria do we choose the best side to crop? We might decide: the side that gives the biggest reduction in boundary colours. That gives us:

So that fails. The biggest proportional reduction in boundary colours also fails.

For now, I conclude that the best method for cases that have multiple solutions is an inside-outwards algorithm like my original innerTrim.bat. Find the largest island (eg with connected-components) and use a coordinate within that island as the seed for innerTrim.bat.

[snibgo]

Another failing example:
https://up.picr.de/34637003bd.png

Ah, well, that seems to be changing the rules of the problem. I thought the rules were: there is a boundary colour (eg white). Find a rectangle where no edge pixels of the rectangle are the boundary colour.

For this example, the boundary is no longer defined simply by a colour, but by something more complex, eg "a pixel is boundary pixel if it is white, and connected to an image edge by a path of white pixels".