source: trunk/libdjvu/GScaler.cpp @ 206

Last change on this file since 206 was 206, checked in by Eugene Romanenko, 14 years ago

DJVU plugin: djvulibre updated to version 3.5.19

File size: 18.7 KB
Line 
1//C-  -*- C++ -*-
2//C- -------------------------------------------------------------------
3//C- DjVuLibre-3.5
4//C- Copyright (c) 2002  Leon Bottou and Yann Le Cun.
5//C- Copyright (c) 2001  AT&T
6//C-
7//C- This software is subject to, and may be distributed under, the
8//C- GNU General Public License, either Version 2 of the license,
9//C- or (at your option) any later version. The license should have
10//C- accompanied the software or you may obtain a copy of the license
11//C- from the Free Software Foundation at http://www.fsf.org .
12//C-
13//C- This program is distributed in the hope that it will be useful,
14//C- but WITHOUT ANY WARRANTY; without even the implied warranty of
15//C- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16//C- GNU General Public License for more details.
17//C-
18//C- DjVuLibre-3.5 is derived from the DjVu(r) Reference Library from
19//C- Lizardtech Software.  Lizardtech Software has authorized us to
20//C- replace the original DjVu(r) Reference Library notice by the following
21//C- text (see doc/lizard2002.djvu and doc/lizardtech2007.djvu):
22//C-
23//C-  ------------------------------------------------------------------
24//C- | DjVu (r) Reference Library (v. 3.5)
25//C- | Copyright (c) 1999-2001 LizardTech, Inc. All Rights Reserved.
26//C- | The DjVu Reference Library is protected by U.S. Pat. No.
27//C- | 6,058,214 and patents pending.
28//C- |
29//C- | This software is subject to, and may be distributed under, the
30//C- | GNU General Public License, either Version 2 of the license,
31//C- | or (at your option) any later version. The license should have
32//C- | accompanied the software or you may obtain a copy of the license
33//C- | from the Free Software Foundation at http://www.fsf.org .
34//C- |
35//C- | The computer code originally released by LizardTech under this
36//C- | license and unmodified by other parties is deemed "the LIZARDTECH
37//C- | ORIGINAL CODE."  Subject to any third party intellectual property
38//C- | claims, LizardTech grants recipient a worldwide, royalty-free,
39//C- | non-exclusive license to make, use, sell, or otherwise dispose of
40//C- | the LIZARDTECH ORIGINAL CODE or of programs derived from the
41//C- | LIZARDTECH ORIGINAL CODE in compliance with the terms of the GNU
42//C- | General Public License.   This grant only confers the right to
43//C- | infringe patent claims underlying the LIZARDTECH ORIGINAL CODE to
44//C- | the extent such infringement is reasonably necessary to enable
45//C- | recipient to make, have made, practice, sell, or otherwise dispose
46//C- | of the LIZARDTECH ORIGINAL CODE (or portions thereof) and not to
47//C- | any greater extent that may be necessary to utilize further
48//C- | modifications or combinations.
49//C- |
50//C- | The LIZARDTECH ORIGINAL CODE is provided "AS IS" WITHOUT WARRANTY
51//C- | OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
52//C- | TO ANY WARRANTY OF NON-INFRINGEMENT, OR ANY IMPLIED WARRANTY OF
53//C- | MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
54//C- +------------------------------------------------------------------
55//
56// $Id: GScaler.cpp,v 1.15 2007/03/25 20:48:32 leonb Exp $
57
58#ifdef HAVE_CONFIG_H
59# include "config.h"
60#endif
61#if NEED_GNUG_PRAGMAS
62# pragma implementation
63#endif
64
65// Rescale images with fast bilinear interpolation
66// From: Leon Bottou, 1/31/2002
67// Almost equal to my initial code.
68
69#include "GScaler.h"
70
71
72#ifdef HAVE_NAMESPACES
73namespace DJVU {
74# ifdef NOT_DEFINED // Just to fool emacs c++ mode
75}
76#endif
77#endif
78
79
80////////////////////////////////////////
81// CONSTANTS
82
83
84#define FRACBITS  4
85#define FRACSIZE  (1<<FRACBITS)
86#define FRACSIZE2 (FRACSIZE>>1)
87#define FRACMASK  (FRACSIZE-1)
88
89
90
91
92
93
94////////////////////////////////////////
95// UTILITIES
96
97
98static int interp_ok = 0;
99static short interp[FRACSIZE][512];
100
101static void
102prepare_interp()
103{
104  if (! interp_ok)
105    {
106      interp_ok = 1;
107      for (int i=0; i<FRACSIZE; i++)
108        {
109          short *deltas = & interp[i][256];
110          for (int j = -255; j <= 255; j++)
111            deltas[j] = ( j*i + FRACSIZE2 ) >> FRACBITS;
112        }
113    }
114}
115
116
117static inline int
118mini(int x, int y) 
119{ 
120  return (x < y ? x : y);
121}
122
123
124static inline int
125maxi(int x, int y) 
126{ 
127  return (x > y ? x : y);
128}
129
130
131
132
133
134
135////////////////////////////////////////
136// GSCALER
137
138
139GScaler::GScaler()
140  : inw(0), inh(0), 
141    xshift(0), yshift(0), redw(0), redh(0), 
142    outw(0), outh(0),
143    gvcoord(vcoord,0), ghcoord(hcoord,0)
144{
145}
146
147
148GScaler::~GScaler()
149{
150}
151
152
153void
154GScaler::set_input_size(int w, int h)
155{ 
156  inw = w;
157  inh = h;
158  if (vcoord)
159  {
160    gvcoord.resize(0);
161  }
162  if (hcoord)
163  {
164    ghcoord.resize(0);
165  }
166}
167
168
169void
170GScaler::set_output_size(int w, int h)
171{ 
172  outw = w;
173  outh = h;
174  if (vcoord)
175  {
176    gvcoord.resize(0);
177  }
178  if (hcoord)
179  {
180    ghcoord.resize(0);
181  }
182}
183
184
185static void
186prepare_coord(int *coord, int inmax, int outmax, int in, int out)
187{
188  int len = (in*FRACSIZE);
189  int beg = (len+out)/(2*out) - FRACSIZE2;
190  // Bresenham algorithm
191  int y = beg;
192  int z = out/2;
193  int inmaxlim = (inmax-1)*FRACSIZE;
194  for  (int x=0; x<outmax; x++)
195    {
196      coord[x] = mini(y,inmaxlim);
197      z = z + len;
198      y = y + z / out; 
199      z = z % out;
200    }
201  // Result must fit exactly
202  if (out==outmax && y!=beg+len)
203    G_THROW( ERR_MSG("GScaler.assertion") );
204}
205
206
207void 
208GScaler::set_horz_ratio(int numer, int denom)
209{
210  if (! (inw>0 && inh>0 && outw>0 && outh>0))
211    G_THROW( ERR_MSG("GScaler.undef_size") );
212  // Implicit ratio (determined by the input/output sizes)
213  if (numer==0 && denom==0) {
214    numer = outw;
215    denom = inw;
216  } else if (numer<=0 || denom<=0)
217    G_THROW( ERR_MSG("GScaler.ratios") );
218  // Compute horz reduction
219  xshift = 0;
220  redw = inw;
221  while (numer+numer < denom) {
222    xshift += 1;
223    redw = (redw + 1) >> 1;
224   numer = numer << 1;
225  }
226  // Compute coordinate table
227  if (! hcoord)
228    ghcoord.resize(outw);
229  prepare_coord(hcoord, redw, outw, denom, numer);
230}
231
232
233void 
234GScaler::set_vert_ratio(int numer, int denom)
235{
236  if (! (inw>0 && inh>0 && outw>0 && outh>0))
237    G_THROW( ERR_MSG("GScaler.undef_size") );
238  // Implicit ratio (determined by the input/output sizes)
239  if (numer==0 && denom==0) {
240    numer = outh;
241    denom = inh;
242  } else if (numer<=0 || denom<=0)
243    G_THROW( ERR_MSG("GScaler.ratios") );
244  // Compute horz reduction
245  yshift = 0;
246  redh = inh;
247  while (numer+numer < denom) {
248    yshift += 1;
249    redh = (redh + 1) >> 1;
250    numer = numer << 1;
251  }
252  // Compute coordinate table
253  if (! vcoord)
254  {
255    gvcoord.resize(outh);
256  }
257  prepare_coord(vcoord, redh, outh, denom, numer);
258}
259
260
261void
262GScaler::make_rectangles(const GRect &desired, GRect &red, GRect &inp)
263{
264  // Parameter validation
265  if (desired.xmin<0 || desired.ymin<0 ||
266      desired.xmax>outw || desired.ymax>outh )
267    G_THROW( ERR_MSG("GScaler.too_big") );
268  // Compute ratio (if not done yet)
269  if (!vcoord) 
270    set_vert_ratio(0,0);
271  if (!hcoord) 
272    set_horz_ratio(0,0);
273  // Compute reduced bounds
274  red.xmin = (hcoord[desired.xmin]) >> FRACBITS;
275  red.ymin = (vcoord[desired.ymin]) >> FRACBITS;
276  red.xmax = (hcoord[desired.xmax-1]+FRACSIZE-1) >> FRACBITS;
277  red.ymax = (vcoord[desired.ymax-1]+FRACSIZE-1) >> FRACBITS;
278  // Borders
279  red.xmin = maxi(red.xmin, 0);
280  red.xmax = mini(red.xmax+1, redw);
281  red.ymin = maxi(red.ymin, 0);
282  red.ymax = mini(red.ymax+1, redh);
283  // Input
284  inp.xmin = maxi(red.xmin<<xshift, 0); 
285  inp.xmax = mini(red.xmax<<xshift, inw); 
286  inp.ymin = maxi(red.ymin<<yshift, 0); 
287  inp.ymax = mini(red.ymax<<yshift, inh); 
288}
289
290
291void 
292GScaler::get_input_rect( const GRect &desired_output, GRect &required_input )
293{
294  GRect red;
295  make_rectangles(desired_output, red, required_input);
296}
297
298
299
300
301
302
303////////////////////////////////////////
304// GBITMAPSCALER
305
306
307GBitmapScaler::GBitmapScaler()
308  : glbuffer(lbuffer,0), gconv(conv,0), gp1(p1,0), gp2(p2,0)
309{
310}
311
312
313GBitmapScaler::GBitmapScaler(int inw, int inh, int outw, int outh)
314  : glbuffer(lbuffer,0), gconv(conv,0), gp1(p1,0), gp2(p2,0)
315{
316  set_input_size(inw, inh);
317  set_output_size(outw, outh);
318}
319
320
321GBitmapScaler::~GBitmapScaler()
322{
323}
324
325
326unsigned char *
327GBitmapScaler::get_line(int fy, 
328                        const GRect &required_red, 
329                        const GRect &provided_input,
330                        const GBitmap &input )
331{
332  if (fy < required_red.ymin)
333    fy = required_red.ymin; 
334  else if (fy >= required_red.ymax)
335    fy = required_red.ymax - 1;
336  // Cached line
337  if (fy == l2)
338    return p2;
339  if (fy == l1)
340    return p1;
341  // Shift
342  unsigned char *p = p1;
343  p1 = p2;
344  l1 = l2;
345  p2 = p;
346  l2 = fy;
347  if (xshift==0 && yshift==0)
348    {
349      // Fast mode
350      int dx = required_red.xmin-provided_input.xmin;
351      int dx1 = required_red.xmax-provided_input.xmin;
352      const unsigned char *inp1 = input[fy-provided_input.ymin] + dx;
353      while (dx++ < dx1)
354        *p++ = conv[*inp1++];
355      return p2;
356    }
357  else
358    {
359      // Compute location of line
360      GRect line;
361      line.xmin = required_red.xmin << xshift;
362      line.xmax = required_red.xmax << xshift;
363      line.ymin = fy << yshift;
364      line.ymax = (fy+1) << yshift;
365      line.intersect(line, provided_input);
366      line.translate(-provided_input.xmin, -provided_input.ymin);
367      // Prepare variables
368      const unsigned char *botline = input[line.ymin];
369      int rowsize = input.rowsize();
370      int sw = 1<<xshift;
371      int div = xshift+yshift;
372      int rnd = 1<<(div-1);
373      // Compute averages
374      for (int x=line.xmin; x<line.xmax; x+=sw,p++)
375        {
376          int g=0, s=0;
377          const unsigned char *inp0 = botline + x;
378          int sy1 = mini(line.height(), (1<<yshift));
379          for (int sy=0; sy<sy1; sy++,inp0+=rowsize)
380            {
381              const unsigned char *inp1;
382              const unsigned char *inp2 = inp0 + mini(x+sw, line.xmax) - x;
383              for (inp1=inp0; inp1<inp2; inp1++)
384                {
385                  g += conv[*inp1];
386                  s += 1;
387                }
388            }
389          if (s == rnd+rnd)
390            *p = (g+rnd)>>div;
391          else
392            *p = (g+s/2)/s;
393        }
394      // Return
395      return p2;
396    }
397}
398
399
400void 
401GBitmapScaler::scale( const GRect &provided_input, const GBitmap &input,
402                      const GRect &desired_output, GBitmap &output )
403{
404  // Compute rectangles
405  GRect required_input; 
406  GRect required_red;
407  make_rectangles(desired_output, required_red, required_input);
408  // Parameter validation
409  if (provided_input.width() != (int)input.columns() ||
410      provided_input.height() != (int)input.rows() )
411    G_THROW( ERR_MSG("GScaler.no_match") );
412  if (provided_input.xmin > required_input.xmin ||
413      provided_input.ymin > required_input.ymin ||
414      provided_input.xmax < required_input.xmax ||
415      provided_input.ymax < required_input.ymax  )
416    G_THROW( ERR_MSG("GScaler.too_small") );
417  // Adjust output pixmap
418  if (desired_output.width() != (int)output.columns() ||
419      desired_output.height() != (int)output.rows() )
420    output.init(desired_output.height(), desired_output.width());
421  output.set_grays(256);
422  // Prepare temp stuff
423  gp1.resize(0);
424  gp2.resize(0);
425  glbuffer.resize(0);
426  prepare_interp();
427  const int bufw = required_red.width();
428  glbuffer.resize(bufw+2);
429  gp1.resize(bufw);
430  gp2.resize(bufw);
431  l1 = l2 = -1;
432  // Prepare gray conversion array (conv)
433  gconv.resize(0);
434  gconv.resize(256);
435  int maxgray = input.get_grays()-1;
436  for (int i=0; i<256; i++) 
437    {
438      conv[i]=(i<= maxgray)
439        ?(((i*255) + (maxgray>>1)) / maxgray)
440        :255;
441    }
442  // Loop on output lines
443  for (int y=desired_output.ymin; y<desired_output.ymax; y++)
444    {
445      // Perform vertical interpolation
446      {
447        int fy = vcoord[y];
448        int fy1 = fy>>FRACBITS;
449        int fy2 = fy1+1;
450        const unsigned char *lower, *upper;
451        // Obtain upper and lower line in reduced image
452        lower = get_line(fy1, required_red, provided_input, input);
453        upper = get_line(fy2, required_red, provided_input, input);
454        // Compute line
455        unsigned char *dest = lbuffer+1;
456        const short *deltas = & interp[fy&FRACMASK][256];
457        for(unsigned char const * const edest=(unsigned char const *)dest+bufw;
458          dest<edest;upper++,lower++,dest++)
459        {
460          const int l = *lower;
461          const int u = *upper;
462          *dest = l + deltas[u-l];
463        }
464      }
465      // Perform horizontal interpolation
466      {
467        // Prepare for side effects
468        lbuffer[0]   = lbuffer[1];
469        lbuffer[bufw+1] = lbuffer[bufw];
470        unsigned char *line = lbuffer+1-required_red.xmin;
471        unsigned char *dest  = output[y-desired_output.ymin];
472        // Loop horizontally
473        for (int x=desired_output.xmin; x<desired_output.xmax; x++)
474          {
475            int n = hcoord[x];
476            const unsigned char *lower = line + (n>>FRACBITS);
477            const short *deltas = &interp[n&FRACMASK][256];
478            int l = lower[0];
479            int u = lower[1];
480            *dest = l + deltas[u-l];
481            dest++;
482          }
483      }
484    }
485  // Free temporaries
486  gp1.resize(0);
487  gp2.resize(0);
488  glbuffer.resize(0);
489  gconv.resize(0);
490}
491
492
493
494
495
496
497////////////////////////////////////////
498// GPIXMAPSCALER
499
500
501GPixmapScaler::GPixmapScaler()
502  : glbuffer(lbuffer,0), 
503    gp1(p1,0), 
504    gp2(p2,0)
505{
506}
507
508
509GPixmapScaler::GPixmapScaler(int inw, int inh, int outw, int outh)
510  : glbuffer(lbuffer,0), 
511    gp1(p1,0), 
512    gp2(p2,0)
513{
514  set_input_size(inw, inh);
515  set_output_size(outw, outh);
516}
517
518
519GPixmapScaler::~GPixmapScaler()
520{
521}
522
523
524GPixel *
525GPixmapScaler::get_line(int fy, 
526                        const GRect &required_red, 
527                        const GRect &provided_input,
528                        const GPixmap &input )
529{
530  if (fy < required_red.ymin)
531    fy = required_red.ymin; 
532  else if (fy >= required_red.ymax)
533    fy = required_red.ymax - 1;
534  // Cached line
535  if (fy == l2)
536    return p2;
537  if (fy == l1)
538    return p1;
539  // Shift
540  GPixel *p=p1;
541  p1 = p2;
542  l1 = l2;
543  p2 = p;
544  l2 = fy;
545  // Compute location of line
546  GRect line;
547  line.xmin = required_red.xmin << xshift;
548  line.xmax = required_red.xmax << xshift;
549  line.ymin = fy << yshift;
550  line.ymax = (fy+1) << yshift;
551  line.intersect(line, provided_input);
552  line.translate(-provided_input.xmin, -provided_input.ymin);
553  // Prepare variables
554  const GPixel *botline = input[line.ymin];
555  int rowsize = input.rowsize();
556  int sw = 1<<xshift;
557  int div = xshift+yshift;
558  int rnd = 1<<(div-1);
559  // Compute averages
560  for (int x=line.xmin; x<line.xmax; x+=sw,p++)
561    {
562      int r=0, g=0, b=0, s=0;
563      const GPixel *inp0 = botline + x;
564      int sy1 = mini(line.height(), (1<<yshift));
565      for (int sy=0; sy<sy1; sy++,inp0+=rowsize)
566        {
567          const GPixel *inp1;
568          const GPixel *inp2 = inp0 + mini(x+sw, line.xmax) - x;
569          for (inp1 = inp0; inp1<inp2; inp1++)
570            {
571              r += inp1->r; 
572              g += inp1->g; 
573              b += inp1->b; 
574              s += 1;
575            }
576        }
577      if (s == rnd+rnd)
578        {
579          p->r = (r+rnd) >> div;
580          p->g = (g+rnd) >> div;
581          p->b = (b+rnd) >> div;
582        }
583      else
584        {
585          p->r = (r+s/2)/s;
586          p->g = (g+s/2)/s;
587          p->b = (b+s/2)/s;
588        }
589    }
590  // Return
591  return (GPixel *)p2;
592}
593
594
595void 
596GPixmapScaler::scale( const GRect &provided_input, const GPixmap &input,
597                      const GRect &desired_output, GPixmap &output )
598{
599  // Compute rectangles
600  GRect required_input; 
601  GRect required_red;
602  make_rectangles(desired_output, required_red, required_input);
603  // Parameter validation
604  if (provided_input.width() != (int)input.columns() ||
605      provided_input.height() != (int)input.rows() )
606    G_THROW( ERR_MSG("GScaler.no_match") );
607  if (provided_input.xmin > required_input.xmin ||
608      provided_input.ymin > required_input.ymin ||
609      provided_input.xmax < required_input.xmax ||
610      provided_input.ymax < required_input.ymax  )
611    G_THROW( ERR_MSG("GScaler.too_small") );
612  // Adjust output pixmap
613  if (desired_output.width() != (int)output.columns() ||
614      desired_output.height() != (int)output.rows() )
615    output.init(desired_output.height(), desired_output.width());
616  // Prepare temp stuff
617  gp1.resize(0);
618  gp2.resize(0);
619  glbuffer.resize(0);
620  prepare_interp();
621  const int bufw = required_red.width();
622  glbuffer.resize(bufw+2);
623  if (xshift>0 || yshift>0)
624    {
625      gp1.resize(bufw);
626      gp2.resize(bufw);
627      l1 = l2 = -1;
628    }
629  // Loop on output lines
630  for (int y=desired_output.ymin; y<desired_output.ymax; y++)
631    {
632      // Perform vertical interpolation
633      {
634        int fy = vcoord[y];
635        int fy1 = fy>>FRACBITS;
636        int fy2 = fy1+1;
637        const GPixel *lower, *upper;
638        // Obtain upper and lower line in reduced image
639        if (xshift>0 || yshift>0)
640          {
641            lower = get_line(fy1, required_red, provided_input, input);
642            upper = get_line(fy2, required_red, provided_input, input);
643          }
644        else
645          {
646            int dx = required_red.xmin-provided_input.xmin;
647            fy1 = maxi(fy1, required_red.ymin);
648            fy2 = mini(fy2, required_red.ymax-1);
649            lower = input[fy1-provided_input.ymin] + dx;
650            upper = input[fy2-provided_input.ymin] + dx;
651          }
652        // Compute line
653        GPixel *dest = lbuffer+1;
654        const short *deltas = & interp[fy&FRACMASK][256];
655        for(GPixel const * const edest = (GPixel const *)dest+bufw;
656          dest<edest;upper++,lower++,dest++)
657        {
658          const int lower_r = lower->r;
659          const int delta_r = deltas[(int)upper->r - lower_r];
660          dest->r = lower_r + delta_r;
661          const int lower_g = lower->g;
662          const int delta_g = deltas[(int)upper->g - lower_g];
663          dest->g = lower_g + delta_g;
664          const int lower_b = lower->b;
665          const int delta_b = deltas[(int)upper->b - lower_b];
666          dest->b = lower_b + delta_b;
667        }
668      }
669      // Perform horizontal interpolation
670      {
671        // Prepare for side effects
672        lbuffer[0]   = lbuffer[1];
673        lbuffer[bufw+1] = lbuffer[bufw];
674        GPixel *line = lbuffer+1-required_red.xmin;
675        GPixel *dest  = output[y-desired_output.ymin];
676        // Loop horizontally
677        for (int x=desired_output.xmin; x<desired_output.xmax; x++,dest++)
678          {
679            const int n = hcoord[x];
680            const GPixel *lower = line + (n>>FRACBITS);
681            const short *deltas = &interp[n&FRACMASK][256];
682            const int lower_r = lower[0].r;
683            const int delta_r = deltas[(int)lower[1].r - lower_r];
684            dest->r = lower_r + delta_r;
685            const int lower_g = lower[0].g;
686            const int delta_g = deltas[(int)lower[1].g - lower_g];
687            dest->g = lower_g + delta_g;
688            const int lower_b = lower[0].b;
689            const int delta_b = deltas[(int)lower[1].b - lower_b];
690            dest->b = lower_b + delta_b;
691          }
692      }
693    }
694  // Free temporaries
695  gp1.resize(0);
696  gp2.resize(0);
697  glbuffer.resize(0);
698}
699
700
701
702#ifdef HAVE_NAMESPACES
703}
704# ifndef NOT_USING_DJVU_NAMESPACE
705using namespace DJVU;
706# endif
707#endif
708
Note: See TracBrowser for help on using the repository browser.