Click here to Skip to main content
15,435,432 members
Articles / Programming Languages / XML
Article
Posted 8 Apr 2020

Tagged as

Stats

13.9K views
663 downloads
6 bookmarked

Fast 2:1 Image Shrink (Scale Down)

Rate me:
Please Sign up or sign in to vote.
5.00/5 (11 votes)
30 Mar 2022CPOL3 min read
Fast implementation of 2:1 image shrink (full image or part of it)
This article includes a fast implementation of 2:1 image shrink algorithm.

Image 1

Introduction

This article offers a simple and fast, practical implementation of 2:1 image shrink algorithm.
2:1 image shrink is used in a very specific cases, but it does a nice job.

Background

Image processing is always an expensive job. When one needs to show a scaled picture, it is always better to use GPU for rendering (OpenGL, DirectX). But using GPU is not always possible and it is good to have an alternative.

The high-quality image resize (enlarge/shrink) is extremely CPU demanding, especially on large images. In additon, sometimes it is required to do the processing multiple times. To relieve this, there are different tricks that could be applied. If a picture has to be shrunk (scaled down), a trick that is similar to mip-maps could be applied. Such case is if we want to shrink a picture more than twice (destination size is less than half of the original), we could speed up the whole proces by applying half-shrink prior to actual scale. 2:1 scale-down is very fast, due to simplest algorithm that uses less computations.

For example, if we have image 1920x1024 and need to shrink it to 500x281, we have to execute code like this:

C++
shrink( imageDst, imageSrc )

But we could optimize this by pre-shrink 2:1 like this:

C++
shrinkHalf( imageHalf, imageSrc );
shrink( imaheDst, imageHalf );

In one of my projects, when I had to scale the image of 3 monitors to generate a preview, the result was:

Scale: 46 ms
ShrinkHalf + Scale: 25 ms
ShrinkHalf + ShrinkHalf + Scale: 16 ms

Which means, the trick applied once, causes %36 speedup.
And the trick applied twice, causes %66 speedup.

The demo application has 2 buttons:

  • Shrink 2:1 - performs image shrink of the whole source image
  • Shrink 2:1 rnd - performs image shrink of random rectangle from the source image

On the left, there is the original image. On the right, there is the original image in grayscale and the shrunked image (or shrunked part) in color.

Shrinking only parts of the image is appropriate when the original were updated and there is a need to update the shrunked copy too. This could save a lot of CPU and time for processing.

2:1 of the whole picture

Image 2

2:1 of random rectangle

Image 3

Using the Code

There is a pair of files in the project: ShrinkHalf.h and ShrinkHalf.cpp
To use the code, you only need to put these files into your project and include the ShrinkHalf.h file.
These files contain the implementations of all algorithms.

All functions receive as arguments:

  • BYTE* pixels - an array of pixels in format 24 bit BGR (b,g,r, b,g,r, ..., b,g,r)
  • int width - width in pixels of the image
  • int height - height in pixels of the image

So, in order to use the functions, you should do the following:

C++
#include "ShrinkHalf.h"

...

// This will convert the color image to black/white using 16x16 matrix
shrinkHalf( dstPixels, srcPixels, srcWidth, srcHeight );

Note that, the destination does not provide dimensions, as they are calculated from the source sizes.

Here are the functions available:

C++
/////////////////////////////////////////////////////////////////////////////
//    Fast and smooth 2:1 image resize
/////////////////////////////////////////////////////////////////////////////

void    shrinkHalf    ( BYTE* target, const BYTE* source, int srcWidth, int srcHeight );
void    shrinkHalfPart( BYTE* target, const BYTE* source, int srcWidth, 
                        int srcHeight, int x1, int y1, int x2, int y2 );

/////////////////////////////////////////////////////////////////////////////

The first function performs 2:1 shrink of the whole image.
The second function performs 2:1 shrink of the specified rectangle from the source image, calculating the respective rectangle for the destination image.
If you use this, you should pay attention that you could need correction +1/-1 of the source rectangle points, because of integer roundup.
This is very useful if there are intensive updates that should be applied (for example, video rendering).

Points of Interest

In the shrinkHalf function, there is commented code that works, but I preferred to leave the internal call to shrinkHalfPart.

C++
//static
void    shrinkHalf( BYTE* target, const BYTE* source, int srcWidth, int srcHeight )
{
    shrinkHalfPart( target, source, srcWidth, srcHeight, 0, 0, srcWidth-1, srcHeight-1 );

    //~~~~~
/*
    int    dstWidth    = srcWidth  / 2;
    int    dstHeight   = srcHeight / 2;

    int    srcLineBytes    = srcWidth * 3;
    int    dstLineBytes    = dstWidth * 3;
    int    dstRows         = dstHeight;

    const BYTE*    sl    = source;
          BYTE*    tl    = target;
    const BYTE*    te    = target + srcHeight/2 * dstLineBytes;

    while( tl < te )
    {
              BYTE*    pt    = tl;
        const BYTE*    p1    = sl;
        const BYTE*    p2    = p1 + srcLineBytes;
        const BYTE*    pe    = sl + srcLineBytes;

        while( p1 < pe )
        {
            *pt++    = (p1[0] + p1[3] + p2[0] + p2[3]) >> 2;    //    / 4;    blue;
            *pt++    = (p1[1] + p1[4] + p2[1] + p2[4]) >> 2;    //    / 4;    green;
            *pt++    = (p1[2] + p1[5] + p2[2] + p2[5]) >> 2;    //    / 4;    red;

            p1    += 6;//2*3;
            p2    += 6;//2*3;
        }

        sl    += srcLineBytes << 1;    //    Shift by 1 is equal to " * 2 "
        tl    += dstLineBytes;
    }
*/
}

So, if someone wants a clean and simpler function, they could remove the first line that calls shrinkHalfPart and uncomment the commented code.

History

  • 8th April, 2020: Initial version

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Technical Lead Brosix
Bulgaria Bulgaria
I am a software development engineer .

Programming Languages: C/C++, Java, Delphi, HTML, CGI, Assembly x86, CNC G-language
RDBMS Microsoft SQL Server, MySQL, SQLite, MS Access, ODBC, JDBC

Networking: TCP/IP, Winsock, HTTP, HTTPS, FTP, SMTP, POP3, TELNET, IMAP, SOCKS 4/5, RTSP, CGI, MS Internet Information Server

Projects I have worked on:
  • Brosix
  • Screen-Sharing product
  • Video chat application
  • Server software
  • Java Virtual Machine
  • Application Server + Internet Proxy Services
  • Instant Messenger - like MSN and Yahoo ones
  • Voicer - Freeware VoIP application
  • Web Server
  • SSH Proxy - SOCKS 4&5 Proxy that can relay TCP Connections through HTTPS Proxy
  • HTTP Proxy
  • SOCKS proxy
  • Battery Test Suite
  • MFC custom UI controls
  • Internet Address Book - Synchronizes local Outlook, Outlook Express, Netscape and Eudora address book with database on WEB server located in the Internet
  • Advertising Screen Saver - Screen Saver that sends e-mails and gain prizes for the computer owner
  • Proxy Send Mail - Send Mail service that can send e-mails through SOCKS 4, SOCKS 5 and HTTPS proxies
  • Proxy Hunter - Very fast, and also works as proxy checker
  • Java Disassembler
  • Java custom UI controls
  • Delphi custom UI controls
  • CNC Gravuring System
  • Font editor for DOS
  • Little DOS games
  • Graphics library for DOS (in Assembly)
  • Galaxian like game for Apple][ in assembly
  • Graphics editor for Apple][
  • Font editor for Apple][
  • More information about my current work you can find here:
    www.brosix.com


    Comments and Discussions

     
    QuestionWhy not use bitblt or stetch bitblt? Pin
    Member 1507871629-Jun-22 16:35
    MemberMember 1507871629-Jun-22 16:35 
    AnswerRe: Why not use bitblt or stetch bitblt? Pin
    Svetoslav Chekanov9-Aug-22 2:24
    MemberSvetoslav Chekanov9-Aug-22 2:24 
    GeneralMy vote of 5 Pin
    tugrulGtx4-Apr-22 3:18
    mvatugrulGtx4-Apr-22 3:18 
    GeneralRe: My vote of 5 Pin
    Svetoslav Chekanov17-May-22 22:20
    MemberSvetoslav Chekanov17-May-22 22:20 
    QuestionAt what threshold the quality of the image is affected substantial? Pin
    deepok13-Apr-22 0:14
    Memberdeepok13-Apr-22 0:14 
    Nice job btw!
    AnswerRe: At what threshold the quality of the image is affected substantial? Pin
    Svetoslav Chekanov17-May-22 22:26
    MemberSvetoslav Chekanov17-May-22 22:26 
    SuggestionLinux utility Pin
    Member 1514928613-Apr-21 2:03
    MemberMember 1514928613-Apr-21 2:03 
    SuggestionMore than just half pre-scaling Pin
    Chad3F16-Apr-20 9:30
    MemberChad3F16-Apr-20 9:30 
    GeneralRe: More than just half pre-scaling Pin
    Svetoslav Chekanov1-Jun-20 7:03
    MemberSvetoslav Chekanov1-Jun-20 7:03 
    QuestionLevel of quality loss? Pin
    Chad3F16-Apr-20 9:18
    MemberChad3F16-Apr-20 9:18 
    AnswerRe: Level of quality loss? Pin
    Svetoslav Chekanov1-Jun-20 6:58
    MemberSvetoslav Chekanov1-Jun-20 6:58 

    General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

    Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.