source: trunk/libdjvu/GScaler.cpp @ 199

Last change on this file since 199 was 15, checked in by Eugene Romanenko, 16 years ago

needed libs update

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