2
\$\begingroup\$

I've hacked a method that auto-fits text into an Imagick image, given a bounding box: the image's width (minus optional margins) and a certain maximum height. What it does is find the optimal font size and line lengths within the bounding box.

It's still a work in progress (still needs thorough checking of the validity of arguments, cleaning up certain routines, etc.), but the basic algorithm works beautifully, except, and I anticipated this already... it's slow as a snail. The longer the supplied text, the slower it will get.

function fitImageAnnotation( Imagick $image, ImagickDraw $draw, $text, $maxHeight, $leading = 1, $strokeWidth = 0.04, $margins = array( 10, 10, 10, 10 ) )
{
    if( strlen( $text ) < 1 )
    {
        return;
    }

    $imageWidth = $image->getImageWidth();
    $imageHeight = $image->getImageHeight();

    // margins are css-type margins: T, R, B, L
    $boundingBoxWidth = $imageWidth - $margins[ 1 ] - $margins[ 3 ];
    $boundingBoxHeight = $imageHeight - $margins[ 0 ] - $margins[ 2 ];

    // We begin by setting the initial font size
    // to the maximum allowed height, and work our way down
    $fontSize = $maxHeight;

    $textLength = strlen( $text );

    // Start the main routine where the culprits are
    do
    {
        $probeText = $text;
        $probeTextLength = $textLength;
        $lines = explode( "\n", $probeText );
        $lineCount = count( $lines );

        $draw->setFontSize( $fontSize );
        $draw->setStrokeWidth( $fontSize * $strokeWidth );
        $fontMetrics = $image->queryFontMetrics( $draw, $probeText, true );

        // This routine will try to wordwrap() text until it
        // finds the ideal distibution of words over lines,
        // given the current font size, to fit the bounding box width
        // If it can't, it will fall through and the parent 
        // enclosing routine will try a smaller font size
        while( $fontMetrics[ 'textWidth' ] >= $boundingBoxWidth )
        {

            // While there's no change in line lengths
            // decrease wordwrap length (no point in
            // querying font metrics if the dimensions
            // haven't changed)
            $lineLengths = array_map( 'strlen', $lines );
            do
            {
                $probeText = wordwrap( $text, $probeTextLength );
                $lines = explode( "\n", $probeText );

                // This is one of the performance culprits
                // I was hoping to find some kind of binary
                // search type algorithm that eliminates
                // the need to decrease the length only
                // one character at a time
                $probeTextLength--;
            }
            while( $lineLengths === array_map( 'strlen', $lines ) && $probeTextLength > 0 );

            // Get the font metrics for the current line distribution
            $fontMetrics = $image->queryFontMetrics( $draw, $probeText, true );

            if( $probeTextLength <= 0 )
            {
                break;
            }
        }

        // Ignore font metrics textHeight, we'll calculate our own
        // based on our $leading argument
        $lineHeight = $leading * $fontSize;
        $lineSpacing = ( $leading - 1 ) * $fontSize;
        $lineCount = count( $lines );
        $textHeight = ( $lineCount * $fontSize ) + ( ( $lineCount - 1 ) * $lineSpacing );


        // This is the other performance culprit
        // Here I was also hoping to find some kind of
        // binary search type algorithm that eliminates
        // the need to decrease the font size only
        // one pixel at a time
        $fontSize -= 1;
    }
    while( $textHeight >= $maxHeight || $fontMetrics[ 'textWidth' ] >= $boundingBoxWidth );

    // The remaining part is no culprit, it just draws the final text
    // based on our calculated parameters
    $fontSize = $draw->getFontSize();
    $gravity = $draw->getGravity();

    if( $gravity < Imagick::GRAVITY_WEST )
    {
        $y = $margins[ 0 ] + $fontSize + $fontMetrics[ 'descender' ];
    }
    else if( $gravity < Imagick::GRAVITY_SOUTHWEST )
    {
        $y = $margins[ 0 ] + ( $boundingBoxHeight / 2 ) - ( $textHeight / 2 ) + $fontSize + $fontMetrics[ 'descender' ];
    }
    else
    {
        $y = ( $imageHeight - $textHeight - $margins[ 2 ] ) + $fontSize;
    }

    $alignment = $gravity - floor( ( $gravity - .5 ) / 3 ) * 3;
    if( $alignment == Imagick::ALIGN_LEFT )
    {
        $x = $margins[ 3 ];
    }
    else if( $alignment == Imagick::ALIGN_CENTER )
    {
        $x = $margins[ 3 ] + ( $boundingBoxWidth / 2 );
    }
    else
    {
        $x = $imageWidth - $margins[ 1 ];
    }
    $draw->setTextAlignment( $alignment );
    $draw->setGravity( 0 );
    foreach( $lines as $line )
    {
        $image->annotateImage( $draw, $x, $y, 0, $line );
        $y += $lineHeight;
    }
}

Usage could be:

$image = new Imagick( '/path/to/an/image.jpg' );
$draw = new ImagickDraw();

// For now, setting a gravity other that 0 is necessary
$draw->setGravity( Imagick::GRAVITY_NORTHWEST );
$text = 'Some text, preferably long, because the longer, the text, the slower the algorithm';
$maxHeight = 120;

// In my actual code it's a class method
fitImageAnnotation( $image, $draw, $text, $maxHeight );

header( 'Content-Type: image/jpeg', true );
echo $image;

As you can see, I've annotated the algorithm, so you can get a feel of what it does, and see where the culprits are.

As noted: I believe I should be able to greatly improve performance with some type of heuristics or perhaps a binary search type of routine: instead of probing wordwrap() one char at a time, and probing $fontSize one pixel at a time, have something more efficient, yet still yield the best possible fit result.

Can you suggest any improvement to the algorithm, without losing the best fit?

\$\endgroup\$
  • \$\begingroup\$ Looking at this code, If I feel you may consider rewriting the entire do-while part.There is a "while" inside the first do block. Inside the "while" there is another do block. This is not only making it difficult to read but also performance will suffer a lot. \$\endgroup\$ – Kinjal Nov 2 '13 at 10:29
1
\$\begingroup\$

I'll give this my best shot, but first...

Some Minor Improvements

strlen() can only return a positive number or 0. If the string is empty you get a 0 otherwise you get the length. So a less than check is unnecessary and can be replaced with a plain boolean check, since we know that 0 is a FALSE value.

if( ! strlen( $text ) ) {
    return;
}

When you access a specific index in an array you are using magic numbers. Its relatively easy to determine what these values ought to represent, but you should declare them anyway.

list( $topMargin, $rightMargin, $botMargin, $leftMargin ) = $margins;
$boundingBoxWidth = $imageWidth - $rightMargin - $leftMargins;
$boundingBoxHeight = $imageHeight - $topMargin - $botMargin;

Performing a function inside a loop tells PHP to call that function on every iteration to update it. When that function itself is essentially a loop you start exponentially decreasing efficiency. I imagine this is also a contributor to your load times.

while( $lineLengths === array_map( 'strlen', $lines ) && $probeTextLength > 0 );

When you find yourself comparing the same value against multiple known values, it might be better to use a switch statement rather than if/elseif/else. One its cleaner, and two its slightly faster, though that speed is negligible. I don't know what the values of those imagick constants are, but it seems like you are only handling a few of them. So, I don't know if using a switch statement is practical here, but in case you want to know how its done, you would use fall-through case statements to cover the less than operation.

switch( $gravity ) {
    case Imagick::LOWERCONST :
    case Imagick::GRAVITY_WEST :
        $y = $margins[ 0 ] + $fontSize + $fontMetrics[ 'descender' ];
    break;

Some Major Improvements

So, that covers the minor improvements. A major improvement would be to break apart this function into separate smaller functions. fitImageAnnotation() is doing entirely too much. A function should describe exactly what it is doing and do no more. Your function doesn't actually start doing what it says its supposed to do until you start messing with the gravity and alignment. You mentioned that this is actually a class method, if so you might also start using class properties to pass shared variables along to these new methods instead of large argument lists.

Analyzing the Algorithm

Now, on to the algorithm. How slow is your program running? I would expect that working with images is likely to run slow all by itself, but I don't have much experience in this department. As such, I can't speak to specifics, so here are a few things that jumped out at me.

You seem to be neglecting PHP's wordwrap() cut and break parameters. Specifying the break parameter tells PHP how newlines should be handled, in your case "\n". Setting the cut parameter to TRUE tells PHP not to cut off words. Using both of these parameters you can do away with $lines until you need to loop over it later (if that's still necessary) and $lineLengths altogether. You don't actually seem to be using $lineLengths anyway; And its repetitive, its the same value only in array form as $probeTextLength. This leaves you with $lineCount, which you can get with substr_count(). This gets rid of a number of explode() function calls, and will make that array_map() function call in your while loop unnecessary.

I imagine this should make a positive impact to your load times. I don't really see anything else right now, but I'll continue looking and edit my answer should I come up with anything else. Hope this helps!

\$\endgroup\$
  • \$\begingroup\$ Thanks for your suggestions. You made some fair points about minor improvements, that will definitely be addressed later. But I'm afraid you've missed the point of $lineLengths === array_map( 'strlen', $lines ) though, so I've edited my question to elaborate of why it's there. And I'm afraid I don't agree about the responsibility of the method; the whole point of the algorithm is what the method says: fit an image annotation. I might call it fitImageAnnotationInBoundingBox(), but the last part of the method is just the rendering, after the fitting calculations are done. \$\endgroup\$ – Decent Dabbler Nov 6 '13 at 23:53
  • \$\begingroup\$ @fireeyedboy: Your method name is fine, but you are doing more than just fitting the text to your image, you are adjusting it as well. Essentially, the contents of each of your loops could be its own function, they actually look repetitive enough that it could probably be just one. You are right about wordwrap's cut parameter, I misread the documentation; but the break parameter stands. With it you don't have to explode the string to compare it, simply compare the old string with the new. If the newlines are in different spots it will object. \$\endgroup\$ – mseancole Nov 7 '13 at 1:24
  • \$\begingroup\$ O, wow, I see what you mean now, about the newlines. You're right, off course! Thank you. I'll have a look and see what that does for the algorithm. \$\endgroup\$ – Decent Dabbler Nov 7 '13 at 11:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.