new image-type: composite, or not

new image-type: composite, or not

[Andreas Politz]

Hi,

lately I started to develop an isearch mode for PDF files, since being
able to search a document effectively is one of the few things that
lets me start-up xpdf, while writing LaTeX.  I came across a library
called poppler, a fork of xpdf, that makes query these kinds of
documents fairly easy.

The idea was to annotate doc-views png pages with ,,colored
rectangles'', you know like isearch does.  I started out doing this
with imagemagicks convert tool, but I soon realized, that creating and
loading a new image (with Millions of pixel) is far too costly
time-wise, in order for this to become a pleasurable experience.  (It
takes around 750ms for reasonable sized images on my labtop.)

So the idea of doing this all in Emacs sprang to my mind; not creating
and loading new images, but reusing already loaded ones and compose
them in new ways. That way a new image type came to live, which I
ingeniously called `composite'.  A patch against the latest bzr
version is at the end of this message.

It looks a bit uglier than the convert version, because of non-fuzzy
masking of the background, but is totally usable, regarding
performance.

Alas, all this made me realize, that maybe a simpler approach would
suffice.  Something like a single function

(mark-image foreground background &rest edges-list)

,which does not have the side-effect of reloading the image.  This
would also allow for other things, like having a pseudo point and mark
in such buffers.  E.g. since I have already the positions of all the
text in the document, it'll be easy to implement some basic selection
and copying functions.  Though I don't know if this would be useful
for anything else, besides doc-view.  Maybe selecting a slice of some
image...

What do you think ?

Andreas

Oh, here is an application of this patch, actually it should work with
or without it.

http://www.fh-trier.de/~politza/emacs/pdf-isearch_v0.2.tar.gz

=== modified file 'src/image.c'
*** src/image.c	2013-01-02 16:13:04 +0000
--- src/image.c	2013-01-26 16:21:44 +0000
***************
*** 8717,8722 ****
--- 8717,9162 ----

  \f
  /***********************************************************************
+ 				Composite
+  ***********************************************************************/
+
+
+ /* composite-image-spec ::=
+  * (image :type 'composite
+  *        [:background color]
+  *        [:width int]
+  *        [:height int]
+  *        [:images ((image-spec
+  *                   [:slice (x y w h)]
+  *                   [:offset (x . y)]
+  *                   [:mask t | (r g b)])* )])
+  */
+
+ #ifdef HAVE_X_WINDOWS
+ static bool comp_image_p (Lisp_Object object);
+ static bool comp_load (struct frame *f, struct image *img);
+ static bool
+ comp_determine_size (struct frame *f, Lisp_Object images, Lisp_Object spec_width,
+                      Lisp_Object spec_height, int *width, int *height);
+
+ static void
+ image_comp_get_slice(Lisp_Object slice,int *x,int *y,int *w,int *h);
+ static Pixmap
+ comp_build_mask (struct frame *f, struct image *img,
+                  int x, int y, int width, int height, Lisp_Object how);
+
+ /* The symbol `composite' identifying images of this type.  */
+
+ static Lisp_Object Qcomposite;
+
+ /* Keyword symbols.  */
+
+ static Lisp_Object QCimages, QCslice, QCoffset;
+
+ /* Indices of image specification fields in comp_format, below.  */
+
+ enum comp_keyword_index
+ {
+   COMP_TYPE,
+   COMP_BACKGROUND,
+   COMP_WIDTH,
+   COMP_HEIGHT,
+   COMP_IMAGES,
+   COMP_ASCENT,
+   COMP_MARGIN,
+   COMP_RELIEF,
+   COMP_ALGORITHM,
+   COMP_HEURISTIC_MASK,
+   COMP_MASK,
+   COMP_LAST
+ };
+
+ /* Vector of image_keyword structures describing the format
+    of valid user-defined image specifications.  */
+
+ static const struct image_keyword comp_format[COMP_LAST] =
+ {
+   {":type",		IMAGE_SYMBOL_VALUE,			1},
+   {":background",	IMAGE_STRING_OR_NIL_VALUE,		0},
+   {":width",		IMAGE_POSITIVE_INTEGER_VALUE,		0},
+   {":height", 		IMAGE_POSITIVE_INTEGER_VALUE,		0},
+   {":images", 		IMAGE_DONT_CHECK_VALUE_TYPE,		0},
+   {":ascent",		IMAGE_ASCENT_VALUE,			0},
+   {":margin",		IMAGE_NON_NEGATIVE_INTEGER_VALUE_OR_PAIR, 0},
+   {":relief",		IMAGE_INTEGER_VALUE,			0},
+   {":conversion",	IMAGE_DONT_CHECK_VALUE_TYPE,		0},
+   {":heuristic-mask",	IMAGE_DONT_CHECK_VALUE_TYPE,		0},
+   {":mask",		IMAGE_DONT_CHECK_VALUE_TYPE,		0}
+ };
+
+ /* Indices of image specification fields in comp_images_format, below.  */
+
+ enum comp_images_keyword_index
+ {
+   COMP_IMAGES_SLICE,
+   COMP_IMAGES_OFFSET,
+   COMP_IMAGES_MASK,
+   COMP_IMAGES_LAST
+ };
+
+ /* Vector of image_keyword structures describing the :images format of
+    valid user-defined subimage specifications.  */
+
+ static const struct image_keyword comp_images_format[COMP_IMAGES_LAST] =
+ {
+   {":slice",	IMAGE_DONT_CHECK_VALUE_TYPE,			0},
+   {":offset",	IMAGE_NON_NEGATIVE_INTEGER_VALUE_OR_PAIR,	0},
+   {":mask",	IMAGE_DONT_CHECK_VALUE_TYPE,			0}
+ };
+
+ /* Structure describing the image type `composite'.  */
+
+ static struct image_type comp_type =
+ {
+   &Qcomposite,
+   comp_image_p,
+   comp_load,
+   x_clear_image,
+   NULL,
+   NULL
+ };
+
+
+ /* Return true if OBJECT is a valid composite image
+    specification.  */
+
+ static bool
+ comp_image_p (Lisp_Object object)
+ {
+   struct image_keyword fmt[COMP_LAST];
+   Lisp_Object images, offset, slice, slice0, mask;
+
+   memcpy (fmt, comp_format, sizeof fmt);
+
+   if (!parse_image_spec (object, fmt, COMP_LAST, Qcomposite))
+     return 0;
+
+   /* Check that the :images are valid. */
+   images = fmt[COMP_IMAGES].value;
+   if (images)
+     {
+       if (! CONSP (images) && ! NILP (images))
+         return 0;
+       for (; ! NILP (images); images = XCDR (images))
+         {
+           if (! CONSP (XCAR (images)))
+             return 0;
+           if (! valid_image_p (XCAR (XCAR (images))))
+             return 0;
+
+           /* Can't use image_spec_value, because of type checking.  */
+           offset = Fplist_get (XCDR (XCAR (images)), QCoffset);
+           if (! NILP (offset))
+             {
+               if (! (RANGED_INTEGERP (0, offset, INT_MAX) ||
+                      (CONSP (offset)
+                       && RANGED_INTEGERP (0, XCAR (offset), INT_MAX)
+                       && RANGED_INTEGERP (0, XCDR (offset), INT_MAX))))
+                 return 0;
+             }
+           slice = Fplist_get (XCDR (XCAR (images)), QCslice);
+           if (! NILP (slice))
+             {
+               if (! CONSP(slice) || 4 != XFASTINT (Flength (slice)))
+                 return 0;
+               for (; ! NILP (slice); slice = XCDR (slice))
+                 if (! RANGED_INTEGERP (0, XCAR (slice), INT_MAX))
+                   return 0;
+             }
+           mask = Fplist_get (XCDR (XCAR (images)), QCmask);
+           if (CONSP (mask))
+             {
+               if (3 != XFASTINT (Flength (mask)))
+                 return 0;
+               for (; ! NILP (slice); slice = XCDR (slice))
+                 if (! RANGED_INTEGERP (0, XCAR (slice), 0xffff))
+                   return 0;
+             }
+         }
+     }
+   return 1;
+ }
+
+ /* Create a composite image IMG for use on frame F.  Value is true if
+    successful.  */
+
+ static bool
+ comp_load (struct frame *f, struct image *img)
+ {
+   Lisp_Object images, bg_spec, width_spec, height_spec;
+
+   struct image *src;
+   Lisp_Object slice, offset, mask;
+   int src_x, src_y, dest_x, dest_y, width, height;
+
+   Pixmap dest, mask_pixmap;
+   GC gc;
+   XGCValues gcv;
+   Display *display = FRAME_X_DISPLAY (f);
+   Window window = FRAME_X_WINDOW (f);
+   Screen *screen = FRAME_X_SCREEN (f);
+   int depth = DefaultDepthOfScreen (screen);
+   bool success = 1;
+
+   images = image_spec_value (img->spec, QCimages, NULL);
+
+   /* Determine the resulting image size */
+   width_spec = image_spec_value (img->spec, QCwidth, NULL);
+   height_spec = image_spec_value (img->spec, QCheight, NULL);
+
+   if (! comp_determine_size (f, images, width_spec,
+                              height_spec, &img->width, &img->height))
+     image_error ("Invalid image size (see `max-image-size')", Qnil, Qnil);
+
+   /* Maybe setup up a background */
+   bg_spec = image_spec_value (img->spec, QCbackground, NULL);
+   if (! NILP (bg_spec))
+     {
+       img->background = x_alloc_image_color (f, img, bg_spec,
+                                              FRAME_BACKGROUND_PIXEL (f));
+       img->background_valid = 1;
+     }
+
+
+   block_input ();               /* FIXME: Do I need to do this ? */
+   dest = XCreatePixmap (display, window, img->width, img->height, depth);
+   if (dest == NO_PIXMAP)
+     {
+       image_error ("Unable to create X pixmap", Qnil, Qnil);
+       unblock_input ();
+       return 0;
+     }
+
+   gc = XCreateGC (display, dest, 0, NULL);
+   /* Fill the background. */
+   if (img->background_valid)
+     {
+       gcv.foreground = img->background;
+       gcv.fill_style = FillSolid;
+       XChangeGC (display, gc, GCForeground|GCFillStyle, &gcv);
+       XFillRectangle (display, dest, gc, 0, 0, img->width, img->height);
+     }
+   /* Now draw the images on top of it. */
+   for (; ! NILP (images); images = XCDR (images))
+     {
+       slice = Fplist_get (XCDR (XCAR (images)), QCslice);
+       offset = Fplist_get (XCDR (XCAR (images)), QCoffset);
+       mask = Fplist_get (XCDR (XCAR (images)), QCmask);
+
+       src_x = src_y = dest_x = dest_y = 0;
+       width = img->width;
+       height = img->height;
+       src = IMAGE_FROM_ID (f, lookup_image (f, XCAR (XCAR (images))));
+
+       if (! src || src->pixmap == NO_PIXMAP)
+         {
+           success = 0;
+           break;
+         }
+
+       if (! NILP (slice))
+         image_comp_get_slice(slice, &src_x, &src_y, &width, &height);
+
+       if (! NILP (offset))
+         {
+           if (CONSP (offset))
+             {
+               dest_x = XFASTINT (XCAR (offset));
+               dest_y = XFASTINT (XCDR (offset));
+             }
+           else
+             {
+               dest_x = dest_y = XFASTINT (offset);
+             }
+         }
+
+       if (! NILP (mask))
+         {
+           mask_pixmap = comp_build_mask(f, src, src_x, src_y,
+                                         width, height, mask);
+           if (mask_pixmap == NO_PIXMAP)
+             {
+               image_error ("Unable to create mask pixmap", Qnil, Qnil);
+               success = 0;
+               break;
+             }
+
+           gcv.clip_mask = mask_pixmap;
+           gcv.clip_x_origin = dest_x;
+           gcv.clip_y_origin = dest_y;
+           XChangeGC (display, gc, GCClipMask|GCClipYOrigin|GCClipXOrigin, &gcv);
+         }
+
+       XCopyArea (display, src->pixmap, dest, gc, src_x,  src_y,
+                  width,  height, dest_x,  dest_y);
+
+       if (! NILP (mask) && mask_pixmap != NO_PIXMAP)
+         {
+           gcv.clip_mask = NO_PIXMAP;
+           XChangeGC (display, gc, GCClipMask, &gcv);
+           XFreePixmap (display, mask_pixmap);
+         }
+     }
+
+   XFreeGC(display, gc);
+   if (success)
+     img->pixmap = dest;
+   else
+     XFreePixmap (display, dest);
+
+   unblock_input ();
+   return success;
+ }
+
+ static bool
+ comp_determine_size (struct frame *f, Lisp_Object images, Lisp_Object spec_width,
+                      Lisp_Object spec_height, int *width, int *height)
+ {
+   Lisp_Object slice, offset;
+   int w, h, this_width, this_height;
+   struct image *img;
+
+   w = ! NILP (spec_width) ? XFASTINT (spec_width) : 0;
+   h = ! NILP (spec_height) ? XFASTINT (spec_height) : 0;
+
+
+   if (NILP (spec_width) || NILP (spec_height))
+     {
+       for (; ! NILP (images); images = XCDR (images))
+         {
+           img = IMAGE_FROM_ID (f, lookup_image (f, XCAR (XCAR (images))));
+
+           if (! img || img->pixmap == NO_PIXMAP)
+             continue;
+
+           slice = Fplist_get (XCDR (XCAR (images)), QCslice);
+           if (! NILP (slice))
+             {
+               int sw, sh;
+               image_comp_get_slice(slice, NULL, NULL, &sw, &sh);
+
+               this_width = min (img->width, sw);
+               this_height = min (img->height, sh);
+             }
+           else
+             {
+               this_width = img->width;
+               this_height = img->height;
+             }
+
+           offset = Fplist_get (XCDR (XCAR (images)), QCoffset);
+           if (! NILP (offset))
+             {
+               if (CONSP (offset))
+                 {
+                   this_width += XFASTINT (XCAR (offset));
+                   this_height += XFASTINT (XCDR (offset));
+                 }
+               else
+                 {
+                   this_width += XFASTINT (offset);
+                   this_height += XFASTINT (offset);
+                 }
+             }
+
+           if (NILP (spec_width))
+             w = max (w, this_width);
+           if (NILP (spec_height))
+             h = max (h, this_height);
+         }
+     }
+
+   if (check_image_size (f, w, h))
+     {
+       *width = w;
+       *height = h;
+       return 1;
+     }
+   return 0;
+ }
+
+ static void
+ image_comp_get_slice(Lisp_Object slice,int *x,int *y,int *w,int *h)
+ {
+   if (x)
+     *x = XFASTINT (XCAR (slice));
+   if (y)
+     *y = XFASTINT (XCAR (XCDR (slice)));
+   if (w)
+     *w = XFASTINT (XCAR (XCDR (XCDR (slice))));
+   if (h)
+     *h = XFASTINT (XCAR (XCDR (XCDR (XCDR (slice)))));
+ }
+
+ /* This function is almost identical to x_build_heuristic_mask, but
+    allows for slices. */
+ static Pixmap
+ comp_build_mask (struct frame *f, struct image *img,
+                  int x, int y, int width, int height, Lisp_Object how)
+ {
+   XImagePtr ximg;
+   XImagePtr mask_img;
+   Pixmap mask;
+   bool rc, use_img_background;
+   unsigned long bg = 0;
+
+   /* Create an image and pixmap serving as mask.  */
+   rc = x_create_x_image_and_pixmap (f, width, height, 1, &mask_img, &mask);
+   if (!rc)
+     return NO_PIXMAP;
+
+   /* Get the X image of IMG->pixmap.  */
+   ximg = XGetImage (FRAME_X_DISPLAY (f), img->pixmap, x, y,
+                     width, height, ~0, ZPixmap);
+
+   /* Determine the background color of ximg.  If HOW is `(R G B)'
+      take that as color.  Otherwise, use the image's background color. */
+   use_img_background = 1;
+
+   if (CONSP (how))
+     {
+       int rgb[3], i;
+
+       for (i = 0; i < 3 && CONSP (how) && NATNUMP (XCAR (how)); ++i)
+ 	{
+ 	  rgb[i] = XINT (XCAR (how)) & 0xffff;
+ 	  how = XCDR (how);
+ 	}
+
+       if (i == 3 && NILP (how))
+ 	{
+ 	  char color_name[30];
+ 	  sprintf (color_name, "#%04x%04x%04x", rgb[0], rgb[1], rgb[2]);
+ 	  bg = x_alloc_image_color (f, img, build_string (color_name), 0);
+ 	  use_img_background = 0;
+ 	}
+     }
+
+   if (use_img_background)
+     bg = four_corners_best (ximg, NULL, width, height);
+
+   /* Set all bits in mask_img to 1 whose color in ximg is different
+      from the background color bg.  */
+   for (y = 0; y < height; ++y)
+     for (x = 0; x < width; ++x)
+       XPutPixel (mask_img, x, y, (XGetPixel (ximg, x, y) != bg
+ 				  ? PIX_MASK_DRAW : PIX_MASK_RETAIN));
+
+   /* Put mask_img into img->mask.  */
+   x_put_x_image (f, mask_img, mask, width, height);
+   x_destroy_x_image (mask_img);
+
+   return mask;
+ }
+ #endif  /* HAVE_X_WINDOWS */
+
+ \f
+ /***********************************************************************
  				Tests
   ***********************************************************************/

***************
*** 8814,8819 ****
--- 9254,9264 ----
      return define_image_type (&gs_type);
  #endif

+ #ifdef HAVE_X_WINDOWS
+   if (EQ (type, Qcomposite))
+     return define_image_type (&comp_type);
+ #endif  /* HAVE_X_WINDOWS */
+
    return NULL;
  }

***************
*** 8947,8952 ****
--- 9392,9405 ----
  #endif /* HAVE_NTGUI  */
  #endif /* HAVE_RSVG  */

+ #ifdef HAVE_X_WINDOWS
+   DEFSYM (Qcomposite, "composite");
+   DEFSYM (QCslice, ":slice");
+   DEFSYM (QCoffset, ":offset");
+   DEFSYM (QCimages, ":images");
+   ADD_IMAGE_TYPE (Qcomposite);
+ #endif  /* HAVE_X_WINDOWS */
+
    defsubr (&Sinit_image_library);
  #ifdef HAVE_IMAGEMAGICK
    defsubr (&Simagemagick_types);

Re: new image-type: composite, or not

[Stefan Monnier]

> lately I started to develop an isearch mode for PDF files, since being
> able to search a document effectively is one of the few things that
> lets me start-up xpdf, while writing LaTeX.

Would be very nice, indeed.  A print command would also be welcome
(especially one that can print a subset of the pages).

> That way a new image type came to live, which I ingeniously called
> `composite'.

Sounds good.

> It looks a bit uglier than the convert version, because of non-fuzzy
> masking of the background, but is totally usable, regarding
> performance.

What does it look like?  E.g. can you highlight the text without
obscuring it?

> Alas, all this made me realize, that maybe a simpler approach would
> suffice.  Something like a single function
> (mark-image foreground background &rest edges-list)

I'm not sure exactly how that would work, can you give some details?

> which does not have the side-effect of reloading the image.

Why does the composite type need to reload the image?

> Though I don't know if this would be useful for anything else, besides
> doc-view.  Maybe selecting a slice of some image...

Selecting a slice in image-mode is indeed an obvious candidate.
Not sure what other candidates there can be, neither for mark-image nor
for a composite image.


        Stefan

Re: new image-type: composite, or not

[Andreas Politz]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> What does it look like?  E.g. can you highlight the text without
> obscuring it?

http://public.fh-trier.de/~politza/emacs/pdf-isearch.png

Because of anti-aliasing, the background is not merely a single color,
such that my (single-color) mask is not perfect.  `convert' seems to do
some fuzzy comparing of colors by default.

>
>> Alas, all this made me realize, that maybe a simpler approach would
>> suffice.  Something like a single function
>> (mark-image foreground background &rest edges-list)
>
> I'm not sure exactly how that would work, can you give some details?
>
This kind of function was what I was looking for.  I have a list of
rectangles ((x0 y0 x1 y1)...) and want to ,,fontify'' the image at these
places.  

I don't know.  I just thought, that maybe this kind of low-level
tinkering with images, masks and slices is not really needed and maybe
it does not really fit nicely in the current image-framework.  If that
is true, then some more high-level function could simplify an
implementation or make it cleaner.  Using libmagick instead of X11 is
something else to consider.

>> which does not have the side-effect of reloading the image.
>
> Why does the composite type need to reload the image?
>

No it doesn't. I just stated an imported feature, this supposed
mark-image function would need to have.

> Not sure what other candidates there can be, neither for mark-image nor
> for a composite image.
>

Well, customizing tree-widgets images...

-AP

Re: new image-type: composite, or not

[Stefan Monnier]

> http://public.fh-trier.de/~politza/emacs/pdf-isearch.png
> Because of anti-aliasing, the background is not merely a single color,
> such that my (single-color) mask is not perfect.  `convert' seems to do
> some fuzzy comparing of colors by default.

Ah, so your composite has the PDF on top and the highlighting below?
That means you need to know the background color of the PDF document.
I though you'd be put the highlighting above, but then it tends to
obscure the text it highlights, unless you use something like
α-blending.

>>> Alas, all this made me realize, that maybe a simpler approach would
>>> suffice.  Something like a single function
>>> (mark-image foreground background &rest edges-list)
>> I'm not sure exactly how that would work, can you give some details?
> This kind of function was what I was looking for.  I have a list of
> rectangles ((x0 y0 x1 y1)...) and want to ,,fontify'' the image at these
> places.  

Right, but I'm not sure what foreground and background mean (if you
assume the document is back-on-white, I can guess what you might want
to say, but if the document is a colorful image it's much less clear).

Also, it would require an `image' argument, other it wouldn't know which
image to mark.  And it would need to store the mark-data somehow
somewhere (probably within the `image' descriptor), so that redisplay
knows to put the mark next time it refreshes the display.

> I don't know.  I just thought, that maybe this kind of low-level
> tinkering with images, masks and slices is not really needed and maybe
> it does not really fit nicely in the current image-framework.  If that
> is true, then some more high-level function could simplify an
> implementation or make it cleaner.

That would be nice indeed, but I'm not sure if mark-image would let us
avoid such low-level tinkering.

>> Not sure what other candidates there can be, neither for mark-image nor
>> for a composite image.
> Well, customizing tree-widgets images...

You're thinking of using composite images in the tree-widget icons?


        Stefan

Re: new image-type: composite, or not

[Andreas Politz]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> http://public.fh-trier.de/~politza/emacs/pdf-isearch.png
>> Because of anti-aliasing, the background is not merely a single color,

> Ah, so your composite has the PDF on top and the highlighting below?
> That means you need to know the background color of the PDF document.
> I though you'd be put the highlighting above, but then it tends to
> obscure the text it highlights, unless you use something like
> α-blending.

Yes, and at one point I did.  Here is how this is drawn, from top to
bottom Z-order.

masked Pdf slice
colored background slice
complete Pdf

>>>> (mark-image foreground background &rest edges-list)

> Right, but I'm not sure what foreground and background mean (if you
> assume the document is back-on-white, I can guess what you might want
> to say, but if the document is a colorful image it's much less clear).

Yes, at least some notion of foreground and background colors.

> Also, it would require an `image' argument, other it wouldn't know which
> image to mark.  And it would need to store the mark-data somehow
> somewhere (probably within the `image' descriptor), so that redisplay
> knows to put the mark next time it refreshes the display.
>

>> I don't know.  I just thought, that maybe this kind of low-level
>> tinkering with images, masks and slices is not really needed and maybe
>> it does not really fit nicely in the current image-framework.  If that
>> is true, then some more high-level function could simplify an
>> implementation or make it cleaner.
>
> That would be nice indeed, but I'm not sure if mark-image would let us
> avoid such low-level tinkering.
>

This function was just thrown in as an (not very well thought out)
afterthought.  The question in my mind was, whether some (the
majoriy,regular,me,...) Emacs user wants to compose images in fancy
ways, or if it suffices for him beeing able to say: ,,Highlight this and
that part of the image in this or that (high-level) way.''.

>>> Not sure what other candidates there can be, neither for mark-image nor
>>> for a composite image.
>> Well, customizing tree-widgets images...
>
> You're thinking of using composite images in the tree-widget icons?

I was just running out of ideas...  But with my current implementation,
it would be possible to change some colors on the fly in any image used
by any package.

Andreas

Re: new image-type: composite, or not

[Andreas Politz]

I discovered `imagemagick-render-type', which is a major improvement for
my convert approach.

-AP