Click here to Skip to main content
15,867,308 members
Articles / Desktop Programming / MFC
Article

Fast Dyadic Image Scaling with Haar Transform

Rate me:
Please Sign up or sign in to vote.
4.67/5 (10 votes)
18 Oct 2007GPL33 min read 119K   3.2K   33   26
This article demonstrates the use of Haar transform for dyadic image scaling with MMX optimization

Introduction

This is the fast dyadic image down sampling class based on Haar transform. It extends BaseFWT2D class from my other article 2D Fast Wavelet Transform Library for Image Processing for this specific purpose. It uses MMX optimization and is applicable in the image processing field where you perform dyadic down sampling: 2, 4, 8, 16, 32 ... pow(2, N) times. I use that code as a preprocessing in the face detection process.

Background

You need to be familiar with Haar transform.

Using the Code

I've arranged console project allocating RGB array for 640x480 image and implementing several runs of down sampling to gather statistics and output average time for it. I used the precision time counter - I remember I downloaded it some long time ago from The Code Project. On my 2.2GHz TravelMate under licensed Vista it runs 5-6ms for down sampling this image to 80x60, eight times smaller.

The classes in the project are:

  • C++
    vec1D //1D vector wrapper
  • C++
    vec2D //2D vector wrapper
  • C++
    BaseFWT2D //abstract base class for 2D FWT
  • C++
    Haar : public BaseFWT2D //Haar based down sampling
  • C++
    ImageResize //provides RGB data down sampling

You can learn about vec1D and BaseFWT2D from my 2D Fast Wavelet Transform Library for Image Processing article and about vec2D from my other article 2D Vector Class Wrapper SSE Optimized for Math Operations.

The ImageResize class contains three objects of class Haar for red, green and blue channels down sampling. First, you need to initialize the ImageResize object to specific width, height and down sampling ratio:

  • C++
    void init(unsigned int w, unsigned int h, float zoom = 0.125f);

The zoom is the image down sampling factor, with resulting image down sampled by 1/zoom times. The default one (0.125f) provides 8 times down sampled image. You can down sample the image only with zoom equal to 1/2, 1/4, 1/8, ... 1/pow(2,N).

Then you can proceed with down sampling incoming images with either of the overloaded functions:

  • C++
    int resize(const unsigned char* pBGR);
  • C++
    int resize(const unsigned char* pR, const unsigned char* pG, 
                const unsigned char* pB) const;

The first one takes RGB stream with the first byte in the triplet for blue channel and the last one for red. The second takes the RGB channels in separate buffers.

C++
//your bitmap data goes in that fashion
//unsigned char* pBGR = new unsigned char[width*height*3];

unsigned int width = 640;
unsigned int height = 480;
float zoom = 0.25;

ImageResize resize;
resize.init(width, height, zoom);

//keep resizing incoming data after initialization.
resize.resize(pBGR);

To access down sampled image, the following functions are defined:

  • C++
    char** getr() const;
  • C++
    char** getg() const;
  • C++
    char** getb() const;

Note they provide 2D char pointers to the data in char range -128 ... 127.

C++
//print out resized red channel
char** pr = resize.getr();
for(unsigned int y = 0; y < height * zoom; y++) {
        for(unsigned int x = 0; x < width * zoom; x++)
                wprintf(L" %d", (pr[y][x] + 128));
        wprintf(L"\n");
}

You can also access down sampled gray version of the RGB bitmap after resize() call with:

  • C++
    inline const vec2D* gety() const;

It returns the pointer of vec2D type to it. I've written rgb2y(int r, int g, int b) function to convert a single RGB triplet to gray pixel with SSE optimization, however I use simple floating point arithmetic currently in that version of class and turn on the compiler's SSE optimization. It actually runs slightly faster than my SSE optimized function (have to look at that a moment later).

The Haar extension to the BaseFWT2D is pretty simple. I've provided implementations for virtual functions BaseFWT2D::transrows() and BaseFWT2D::transcols() (I have not written it for BaseFWT2D::synthrows() and BaseFWT2D::synthcols() since this is a down sampling class and not up sampling yet). They are MMX optimized and the math behind Haar transform is that you take 2 consecutive pixels, and calculate their mean. So you first decrease the size of your image twice along the horizontal direction and the same along the vertical. It is easy when you do this column wise but with a single row, you have to select even and odd consecutive pixels and just average them in parallel.

I do it this way:

C++
unsigned char* sour;

__m64 m00FF;
m00FF.m64_u64 = 0x00FF00FF00FF00FF;

__m64 *msour = (__m64 *)sour;

//even coeffs
__m64 even = _mm_packs_pu16(_mm_and_si64
    (*msour, m00FF), _mm_and_si64(*(msour + 1), m00FF));
//odd coeffs
__m64 odd = _mm_packs_pu16(_mm_srli_pi16(*msour, 8), _mm_srli_pi16(*(msour + 1), 8));

msour += 2;

Points of Interest

The Haar class could be modified with SSE2 integer intrinsic for even faster processing, I hope I can implement it later and submit the update, otherwise if someone interested is eager to modify it with SSE2 support, please let me know. I bet it could do the same 640x480 down sampling to 80x60 for about 1-2ms with SSE2.

History

  • 18th October, 2007: Initial post

License

This article, along with any associated source code and files, is licensed under The GNU General Public License (GPLv3)


Written By
Engineer
Russian Federation Russian Federation
Highly skilled Engineer with 14 years of experience in academia, R&D and commercial product development supporting full software life-cycle from idea to implementation and further support. During my academic career I was able to succeed in MIT Computers in Cardiology 2006 international challenge, as a R&D and SW engineer gain CodeProject MVP, find algorithmic solutions to quickly resolve tough customer problems to pass product requirements in tight deadlines. My key areas of expertise involve Object-Oriented
Analysis and Design OOAD, OOP, machine learning, natural language processing, face recognition, computer vision and image processing, wavelet analysis, digital signal processing in cardiology.

Comments and Discussions

 
QuestionA question Pin
dommy1A14-Aug-12 6:06
dommy1A14-Aug-12 6:06 
AnswerRe: A question Pin
Chesnokov Yuriy20-Aug-12 5:10
professionalChesnokov Yuriy20-Aug-12 5:10 
QuestionHow to use resize code with HBITMAP? Pin
Member 33450959-Sep-09 2:52
Member 33450959-Sep-09 2:52 
AnswerRe: How to use resize code with HBITMAP? Pin
Chesnokov Yuriy9-Sep-09 20:02
professionalChesnokov Yuriy9-Sep-09 20:02 
GeneralRe: How to use resize code with HBITMAP? Pin
Member 33450959-Sep-09 22:50
Member 33450959-Sep-09 22:50 
GeneralRe: How to use resize code with HBITMAP? Pin
Member 334509514-Sep-09 22:06
Member 334509514-Sep-09 22:06 
Questionuse this code under Wince Pin
wolf_of_it13-Nov-08 1:55
wolf_of_it13-Nov-08 1:55 
AnswerRe: use this code under Wince Pin
Chesnokov Yuriy13-Nov-08 2:51
professionalChesnokov Yuriy13-Nov-08 2:51 
GeneralResizing from 352x288 to 176x144 Pin
captainc/c++26-Nov-07 3:04
captainc/c++26-Nov-07 3:04 
AnswerRe: Resizing from 352x288 to 176x144 Pin
Chesnokov Yuriy26-Nov-07 3:51
professionalChesnokov Yuriy26-Nov-07 3:51 
GeneralRe: Resizing from 352x288 to 176x144 Pin
captainc/c++26-Nov-07 4:15
captainc/c++26-Nov-07 4:15 
QuestionRe: Resizing from 352x288 to 176x144 Pin
captainc/c++26-Nov-07 15:16
captainc/c++26-Nov-07 15:16 
QuestionRe: Resizing from 352x288 to 176x144 Pin
captainc/c++27-Nov-07 21:52
captainc/c++27-Nov-07 21:52 
AnswerRe: Resizing from 352x288 to 176x144 Pin
Chesnokov Yuriy28-Nov-07 3:01
professionalChesnokov Yuriy28-Nov-07 3:01 
All I can say 'I can not help' you with your programing learning.

You do not need to Resize.init() multiple time once you initialized it to specific width height.

J is the scale, th is threshold.

To put everything together use getr(), getg(), getb() Smile | :) read them to RGB buffer.

chesnokov

GeneralRe: Resizing from 352x288 to 176x144 Pin
captainc/c++28-Nov-07 21:57
captainc/c++28-Nov-07 21:57 
GeneralRe: Resizing from 352x288 to 176x144 Pin
captainc/c++29-Nov-07 3:37
captainc/c++29-Nov-07 3:37 
Generalbroken link Pin
double(U)20-Nov-07 7:29
double(U)20-Nov-07 7:29 
GeneralFace Detection Pin
Dark.Elf.ipl27-Oct-07 0:00
Dark.Elf.ipl27-Oct-07 0:00 
GeneralRe: Face Detection Pin
Chesnokov Yuriy27-Oct-07 1:24
professionalChesnokov Yuriy27-Oct-07 1:24 
GeneralRe: Face Detection Pin
Dark.Elf.ipl27-Oct-07 5:59
Dark.Elf.ipl27-Oct-07 5:59 
GeneralRe: Face Detection Pin
Chesnokov Yuriy27-Oct-07 18:28
professionalChesnokov Yuriy27-Oct-07 18:28 
GeneralRe: Face Detection Pin
Dark.Elf.ipl28-Oct-07 22:24
Dark.Elf.ipl28-Oct-07 22:24 
GeneralRe: Face Detection Pin
Chesnokov Yuriy28-Oct-07 23:57
professionalChesnokov Yuriy28-Oct-07 23:57 
GeneralRe: Face Detection Pin
double(U)20-Nov-07 7:31
double(U)20-Nov-07 7:31 
GeneralRe: Face Detection (Cont.) Pin
Dark.Elf.ipl27-Oct-07 6:09
Dark.Elf.ipl27-Oct-07 6:09 

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.