eigenclass logo
MAIN  Index  Search  Changes  PageRank  Login

Fast image enlargement through seam insertion in OCaml

I have implemented the last major feature missing in my content-aware image resizer based on seam carving/insertion, image enlargement via seam insertion. It took a whole 50 lines of OCaml code which you can find below. My program now does everything the Gimp LiquidRescale plug-in does, so a direct comparison can be done.

Looking at the rendering part only, I have needed under 500 lines of OCaml code *1. LiquidRescale's render.{c,h} comprise over 2100 lines of code. On my box, seam carving and insertion in OCaml are both over 5 times faster than LiquidRescale's (remember I'm not comparing my code to a Python script; LiquidRescale is written in C).

Here's a tiny sample of what seam insertion is about. Given this image

buildings_orig.jpg

if you just rescale it, it will look like this

buildings_expanded.jpg

The image can be enlarged while preserving the aspect ratios of the salient objects using seam insertion:

buildings_inserted.jpg

Content-aware image enlargement is not as flashy as object removal with seam carving, but it's still somewhat useful.

How seam insertion works

Seam insertion is very easy once you have seam carving, since it can be trivially built atop it as reflected also by the code, where seam insertion is performed by a functor which abstracts over the seam carving module:

 module Make(Carving: Seamcarving.S) = struct ... end

This means that I automatically get biased seam insertion, as I already had biased seam carving, which is used to remove objects from an image (see my first post for an explanation of the seam carving algorithm itself).

There are basically two steps to image enlargement through seam insertion:

  • pretend we're carving seams from the image as if we were shrinking it, and record all the seams (connected paths) that were removed
  • on the original image, follow those paths and insert new pixels whose colors are the average of that of their neighbors

It's conceptually easy, and also simple in practice. I wrote that code two weeks ago, as well as a 5-line cheap command-line tool to invoke it. Unfortunately, it didn't work on the very first run after it typed. I left it there at that time because it was 3am or so (my code gets buggier past ~1-2am). As I revisited it today, I found the bug within a few seconds. I was doing

 let insert_seams t n =
   let rec loop t i acc =
     if i < n then begin
       let t, path = Carving.seam_carve_h' t in
         loop t (i - 1) (path :: acc)
     end else Array.of_list (List.rev acc) in
 ...

Obviously, that (i - 1) should have been (i + 1), but I prefer to change the test to i > 0. I'll stick to decreasing counters in tail-recursive functions from now on.

Other than that, as far as I can tell everything works fine. As for the command-line, I had just copy-pasted the code used for seam carving, but that code duplication felt so dirty I ended up creating a functor that takes a RESIZER (which can either enlarge or shrink the image) and instantiates a full-blown command line tool. I did it in auto mode, without much thought, and this time everything just worked once it typed, even though I was refactoring blindly.

(*
 * seamcarve, content-aware image resizing using seam carving
 * Copyright (C) 2007 Mauricio Fernandez <mfp@acm.org>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 *)

open Seamcarving

module Make(Carving: Seamcarving.S) =
struct
  type t = {
    carver : Carving.t;
    image : image;
  }

  let make ecomputation img =
    let seam_carver = Carving.make ecomputation (Seamcarving.copy_image img) in
      { carver = seam_carver; image = img }

  let insert_seams t n =
    let rec loop t i acc =
      if i > 0 then begin
        let t, path = Carving.seam_carve_h' t in
          loop t (i - 1) (path :: acc)
      end else Array.of_list (List.rev acc) in

    let paths = loop t.carver n [] in
    let h = t.image.height in
    let w = Array.length paths in
    let m = Array.make_matrix h w 0 in
      (* path matrix, each path is a column *)
      Array.iteri (fun i p ->
                     for j = 0 to h - 1 do
                       m.(j).(i) <- p.(i)
                     done)
        paths;
      (* adjust paths depending on previous ones *)
      for j = 0 to h - 1 do
        let row = m.(j) in
          for i = 0 to w - 2 do
            let rx = row.(i) in
              for k = i + 1 to w - 1 do
                let v = row.(k) in
                  if v >= rx then row.(k) <- v + 2
              done
          done
      done;

      let insert_seam row pos imgwidth =
        Array.blit row pos row (pos+1) (imgwidth - pos);
        if pos > 0 then row.(pos) <- average_color row.(pos-1) row.(pos) in

      let imgwidth = t.image.width in
      let img2 = Seamcarving.enlarge_image t.image n in
        (* insert seams *)
        for j = 0 to h - 1 do
          let srow = m.(j) in
          let row = img2.rgb.(j) in
            for i = 0 to w - 1 do
              insert_seam row srow.(i) (imgwidth + i)
            done
        done;

        { img2 with width = imgwidth + n }
end


using your code - gilles (2007-10-24 (Wed) 08:07:52)

How can I use your code ? Can it be used from within GIMP or only from the command line ?

mfp 2007-10-24 (Wed) 08:54:36

The build instructions are in README.txt. Command-line only. If I ever use this seriously it will be for batch resizing of thousands of images; I don't personally care about speed under GIMP. It should be possible to hack LiquidScale to delegate the work to my code, but I'm not very interested in that.

$ carve 
Content-aware rescaling using seam carving.
Usage: carve (-vert <n>| -horiz <n>) [options] <files>
 -o Set output file.
 -vert Change height by given amount of pixels.
 -horiz Change width by given amount of pixels.
 -bias Use energy bias from given file.
 -verbose Verbose mode.
 -help  Display this list of options
 --help  Display this list of options
Name:
Comment:
TextFormattingRules
Preview:

... vs CoreImageTool - freno (2007-10-25 (Don) 04:24:23)

Just wondering if this could be (done &) compared with CoreImageTool, http://www.entropy.ch/software/macosx/coreimagetool/ .

Anyway, very cool!

mfp 2007-10-25 (Thr) 05:02:07

This is a command line front end to Appleā€™s Core Image framework introduced in Mac OS X 10.4. It makes core image filter processing available to scripting languages like bash or Perl/Python/Ruby/PHP used for command-line or web applications.

I couldn't see any filter based on seam carving/insertion in the Core Image filter reference, so I cannot compare my implementation to Apple's nonexistent one :-)

Name:
Comment:
TextFormattingRules
Preview:

Use this form to create a new top-level comment; for direct replies to existing comments, use the text entries you'll find below.

Name:
Subject:

TextFormattingRules
Preview:
Last modified:2007/10/24 04:16:17
Keyword(s):[seam] [carving] [insertion] [ocaml] [liquidrescale] [blog] [frontpage]
References:

*1 120 lines for the sobel filter, 180 for the seam carving algorithm, 50 for seam insertion, 50 for energy biasing and some 60 lines for miscellaneous image manipulation functions (rotation, loading, saving, etc.)