{"id":145,"date":"2005-09-06T15:28:52","date_gmt":"2005-09-06T13:28:52","guid":{"rendered":"http:\/\/blogs.bl0rg.net\/netzstaub\/?p=145"},"modified":"2005-09-06T15:28:52","modified_gmt":"2005-09-06T13:28:52","slug":"algorithmic-movie-editing-in-lisp","status":"publish","type":"post","link":"https:\/\/blogs.bl0rg.net\/netzstaub\/2005\/09\/06\/algorithmic-movie-editing-in-lisp\/","title":{"rendered":"Algorithmic movie editing in Lisp"},"content":{"rendered":"

Algorithmic art<\/h2>\n

\"Alt<\/div>\n<\/p>\n

While composing music for a movie by a friend, I took a closer look at
\nhow he was editing the raw movie material. He was working with what
\nI’ll be calling “effects”, for example movie fluttering, where a small
\nsegment of the movie gets cut in short frame sequences and reorganized
\nin a seemingly random manner. These segments would then be synced onto
\nthe underlying soundtrack (for example music, or words). Reorganizing
\nthe frames by hand, even in a quite advanced software like Adobe
\nPremiere, was quite painstaking, and it took a few hours to arrange
\nsomething like 30 seconds of movie material.<\/p>\n

<\/p>\n

I was feeling quite hacky this day, and writing a software that can
\nrearrange movie frames in a random manner can’t be quite complicated,
\ncan it? I first dwelved into DirectShow, the Microsoft API used to
\nhandle movies and similar things, but it turned out to be quite
\noverengineered and a bit to complicated for what I was trying to do
\n(no realtime manipulation, for example). After searching a bit on
\nfreshmeat, I stumbled upon avisplice, a tool in C that can glue
\ndifferent avi movies together. Upon inspection of the code, I noticed
\nthat all avisplice was doing was taking the avi header out of the
\nfirst movie, and then sticking the frames together, assuming that the
\ncompression format of the different avi movies was the same. I
\nmodified the C program to do the permutation effect my friend was
\nworking with, and gave him the executable version to work with. This
\nway, he could try out different parameters (the number of frames to be
\npermutated as a block). Instead of working for hours with Premiere,
\nand then concluding that the permutation was not as good as he wanted
\nit to be, he could generate 20 permutations, try them out, and keep
\nthe best or try a different thing altogether.<\/p>\n

I was playing around with Common Music at this time, and found the
\npattern composition approach quite interesting. What I would do was to
\nformulate some kind of ideas in my mind as to how a specific kind of
\nmusic was working, and then write down the code in Lisp, and play
\naround with certain parameters, and maybe insert some kind of
\nrandomness. For example, in a piece of dub music I was writing, I had
\na pretty terse ground beat, and added some snare hits with big reverb
\non offbeats. To me, this is the musical idea, which sometimes sounds
\ngood, sometimes not so good, but using Common Music, I could generate
\na great number of loops, and then pick the grooviest ones and
\nincorporate them in my music. In a certain way, this was the same
\napproach that my friend was having with his video editing. His idea
\nwas “permutate the frames”, and then he would pick the good
\npermutations. Of course, this is only “technical” stuff. I think it is
\nnot enough to produce “interesting” pieces of art, but in a way, it
\nenables the artist to go much further in what he is trying to do.<\/p>\n

Actually this is a quite interesting debate. Is doing the editing by
\nhand the better way to produce art? In a way, it is, because while
\ndoing the repetitive work, you get a much more organical feel of what
\nis going on, what may be working, what may be not. Doing errors while
\nworking can produce interesting insights. I also think that in the
\nend, you are prouder of your work because a lot of efforts went into
\nit. On the other hand, once you “mastered” the technique, it becomes
\nuninteresting, and gets in the way when formulating your ideas, it
\nstops the artistic flow. I think this is especially true of digital
\ntechniques, because working in front of a screen is frustrating, while
\nworking with your hands is quite “zen”. I don’t mind sitting in front
\nof a stencil for 8 hours cutting paper, but I get very irritated when
\nI’m rearranging HTML documents in my editor for example. The great
\nthing about programming is that as soon as you notice that something
\nis boring, you can try to write down the process behind it, and let
\nthe computer do the work. Then you can work on the metalevel. This
\nalso compels you to analyse what you are doing in a very precise and
\nmethodic way, because you have to write a program that does the work
\nfor you.<\/p>\n

Code, show us some code!<\/h2>\n

Well, enough blabla about artsy and brainy stuff. I quickly stumbled
\nupon the limits of the C software when trying to write down new
\nalgorithms for my friend (for example, reversing small fragments of
\nthe movie, and glueing them back together), so I took a few hours to
\nrewrite the software in Lisp. In order to get things done, I set
\nmyself a goal and a deadline, which was to produce a music video for
\nan art event on the following day. The code I’ll show now is really ugly,
\nbut remember it was hacked together in a few hours in a highly
\ncoffeinated state \ud83d\ude42<\/p>\n

\"Alt<\/div>\n<\/p>\n

The AVI file format<\/h3>\n

The first step in writing the software was to be able to read and
\nwrite AVI files. AVI is actually a RIFF container format, and is quite
\nsimilar to for example WAVE. It starts with a RIFF header, and then
\ncontains a succession of RIFF blocks, which consist of a RIFF code
\n(four characters), a length, and the content. A RIFF block can be a
\nRIFF list, containing a variable number of RIFF blocks. An AVI file
\nconsists of an avi header, one or several streams (for example, a
\nvideo stream and an audio stream), and an optional index. The streams
\nare described by stream headers, stored in a RIFF list at the
\nbeginning of the file. The first version of the software could only
\nwork with video streams, and all the video clips I manipulated
\ncontained only uncompressed DV-video streams. I’m doing a rewrite
\nright now, but it is far from finished. Here is the class definition
\nfor an AVI movie. AVIH is the avi header, STRH is the stream header
\nfor the video stream, and STRF is the stream format for the video
\nstream. FRAMES is a list of frames. Like avisplice, a frame is only a
\nfilename, an offset, and a length. The frames themselves are not read
\ninto memory, but are only copied from file to file when rendering a
\nmovie.<\/p>\n

\n(defclass avi ()\n  ((type :initform nil\n\t :accessor avi-type\n\t :initarg :type)\n\n   (avih :initform nil :accessor avi-avih\n\t :initarg :avih)\n   (strh :initform nil :accessor avi-strh\n\t :initarg :strh)\n   (strf :initform nil :accessor avi-strf\n\t :initarg :strf)\n\n\n   (size :initform 0\n\t :accessor avi-size\n\t :initarg :size)\n   \n   (frames :initform nil\n\t   :initarg :frames\n\t   :accessor avi-frames)\n   \n   (pathname :initform nil\n\t     :accessor avi-pathname\n\t     :initarg :pathname)))\n\n(defmethod print-object ((avi avi) s)\n  (print-unreadable-object (avi s :type t :identity (unless (avi-pathname avi) t))\n    (format s \"\\\"~A\\\" (~A frames)\" (or (avi-pathname avi)\n\t\t\t\t       \"virtual avi file\")\n\t    (avi-num-frames avi))))\n<\/pre>\n
Reading the AVI file is quite straight forward. The file is opened,
\nthe RIFF header is read, and then a list of RIFF blocks is
\nread. These blocks are parsed according to the RIFF block type. The
\nbasic binary types present in the RIFF file are FOURCC codes (four
\ncharacters), and little endian short and long values. These are
\nextracted from arrays of type (UNSIGNED-BYTE 8) using the following
\nfunctions:<\/p>\n
\n(defun make-fourcc (seq)\n  (coerce (mapcar #'code-char (coerce seq 'list)) 'string))\n\n(defun make-long (seq)\n  (loop for i from 0 below 4\n\tsum (* (elt seq i) (expt 256 i))))\n\n(defun make-short (seq)\n  (loop for i from 0 below 2\n\tsum (* (elt seq i) (expt 256 i))))\n<\/pre>\n
The functions to parse the avi file. Notice that READ-CHUNK recognizes
\nthe different block types. “00dc” is the code for a compressed AVI
\nframe. In this case, READ-CHUNK adds the frame (the filename, the
\noffset and the size) to the frame list of the avi file.<\/p>\n
\n(defun read-avi-file (filename)\n  (with-open-file (s filename :element-type '(unsigned-byte 8)\n\t\t     :direction :input)\n    (let ((avi (make-instance 'avi\n\t\t\t      :pathname filename)))\n      (read-riff-hdr avi s)\n      (read-list avi s (avi-size avi))\n      avi)))\n\n(defun read-riff-hdr (avi s)\n  (let ((hdr-arr (make-array 12 :initial-element 0 :element-type '(unsigned-byte 8))))\n    (read-sequence hdr-arr s)\n    (unless (string-equal (make-fourcc (subseq hdr-arr 0 4)) \"RIFF\")\n      (error \"~A is not an AVI file\" (avi-pathname avi)))\n    (setf (avi-type avi) (make-long (subseq hdr-arr 8 12))\n\t  (avi-size avi) (make-long (subseq hdr-arr 4 8)))))\n\n(defun read-list (avi s list-size)\n  (let ((cur-size 0))\n    (loop while ( size max-size))\n\t(error \"Chunk size is incorrect\"))\n      (cond ((string-equal type \"LIST\")\n\t     (let ((list-arr (make-array 4 :initial-element 0 :element-type '(unsigned-byte 8))))\n\t       (read-sequence list-arr s)\n\t       (let ((list-type (make-fourcc list-arr)))\n\t\t (cond ((string-equal list-type \"movi\")\n\t\t\t(read-movi avi s (- size 4)))\n\t\t       (t (read-list avi s (- size 4))))\n\t\t (incf size 4))))\n\t    ((string-equal type \"strh\")\n\t     (read-strh avi s))\n\t    ((string-equal type \"avih\")\n\t     (read-avih avi s))\n\t    ((string-equal type \"strf\")\n\t     (read-strf avi s))\n\t    ((string-equal type \"00dc\")\n\t     (let ((avi-offset (file-position s)))\n\t       (push (list (avi-pathname avi) avi-offset size) (avi-frames avi))\n\t       (file-position s (+ avi-offset size))))\n\t    (t ; (warn \"Unknown chunk ~A at offset ~A\" type (file-position s))\n\t       (file-position s (+ (file-position s) size))))\n      (+ size 8))))\n\n(defun read-movi (avi s size)\n  (read-list avi s size)\n  (setf (avi-frames avi)\n\t(nreverse (avi-frames avi))))\n\n(defun read-strf (avi s)\n  (let ((strf (make-array 40 :initial-element 0 :element-type '(unsigned-byte 8))))\n    (read-sequence strf s)\n    (setf (avi-strf avi) strf)\n    40))\n\n(defun read-avih (avi s)\n  (let ((avih (make-array 56 :initial-element 0 :element-type '(unsigned-byte 8))))\n    (read-sequence avih s)\n    (setf (avi-avih avi) avih)\n    56))\n\n(defun read-strh (avi s)\n  (let ((strh (make-array 56 :initial-element 0 :element-type '(unsigned-byte 8))))\n    (read-sequence strh s)\n    (setf (avi-strh avi) strh)\n    56))\n<\/pre>\n
AVI files are written in quite the same way. A few functions convert
\nthe basic binary types:<\/p>\n
\n(defun write-fourcc (fourcc s)\n  (write-sequence (mapcar #'char-code (coerce fourcc 'list)) s))\n\n\n(defun long->seq (long)\n  (loop for i from 0 below 4\n\tcollect (mod (floor (\/ long (expt 256 i))) 256)))\n\n(defun write-long (long s)\n  (write-sequence (long->seq long) s))\n\n(defun write-short (short s)\n  (write-sequence (loop for i from 0 below 2\n\t\t\tcollect (mod (floor (\/ short (expt 256 i))) 256)) s))\n\n<\/pre>\n
Writing a RIFF block is quite straight forward too. While writing a
\nRIFF list, we need to recognized embedded lists, and AVI frames have
\nto be written in a special way too. This is quite hacked together, but
\nit works \ud83d\ude42 When writing AVI frames, I open the original file (which
\nis stored in the frame list), seek to the offset of the frame, read
\nthe binary data into a temporary buffer of 64k bytes, and write it
\ninto the output file. This is a bit of overhead, as writing a sequence
\nof frames involves reopening the same file over and over again, but
\nhopefully the operating system will cache everything \ud83d\ude42 <\/p>\n
\n(defun write-chunk (s type data)\n  (write-fourcc type s)\n  (write-long (length data) s)\n  (write-sequence data s)\n  (+ 8 (length data)))\n\n(defun write-frame (s filename offset length)\n  (with-open-file (in filename :direction :input\n\t\t      :element-type '(unsigned-byte 8))\n    (write-fourcc \"00dc\" s)\n    (write-long length s)\n    (file-position in offset)\n    (let* ((buffer-size 65536)\n\t   (c (make-array buffer-size :element-type '(unsigned-byte 8))))\n      (loop for i from 0 below length by buffer-size\n\t    for l = (min buffer-size (- length i))\n\t    do (read-sequence c in :end l)\n\t    (write-sequence c s :end l)))\n    (+ length 8)))\n<\/pre>\n
When writing a list, we don’t know how much bytes the list will take
\nup in the AVI file, so we remember the start offset of the list,
\nsubtract this from the end offset, rewind to the list header, and
\nwrite the value there (4 additional bytes for the list type).<\/p>\n
\n(defun write-list (s type chunks)\n  (write-fourcc \"LIST\" s)\n  (let ((pos (file-position s)))\n    (write-long 0 s)\n    (write-fourcc type s)\n    (let ((length (loop for chunk in chunks\n\t\t\tsum (cond ((string-equal (first chunk) \"LIST\")\n\t\t\t\t   (write-list s (second chunk) (third chunk)))\n\t\t\t\t  ((string-equal (first chunk) \"00dc\")\n\t\t\t\t   (write-frame s (second chunk) (third chunk)\n\t\t\t\t\t\t(fourth chunk)))\n\t\t\t\t  (t (write-chunk s (first chunk) (second chunk)))))))\n      (let ((end-pos (file-position s)))\n\t(file-position s pos)\n;\t(warn \"list length is ~A\" (+ 4 length))\n\t(write-long (+ 4 length) s)\n\t(file-position s end-pos))\n      (+ 12 length))))\n<\/pre>\n
Writing the AVI file is a bit more involved. We first have to write
\nthe RIFF header, then the avi header and the stream headers, then the
\nframes, and finally the index, because Premiere won’t import AVI files
\nwithout a working index. The index is a special RIFF block containing
\nthe offsets of the frames in the “movi” list relative to the beginning
\nof the list. The flags are fixed, because we don’t have keyframes in
\nuncompressed DV streams. We also remember the start position to write
\nthe correct file size in the RIFF header.<\/p>\n
\n(defmethod write-avi-file ((avi avi) filename)\n  (let ((len 12))\n    (with-open-file (s filename :element-type '(unsigned-byte 8)\n\t\t       :if-does-not-exist :create\n\t\t       :if-exists :supersede\n\t\t       :direction :output)\n      (write-fourcc \"RIFF\" s)\n      (let ((pos (file-position s))\n\t    frames-pos)\n\t(write-long 0 s)\n\t(write-long (avi-type avi) s)\n\t(loop for i in (long->seq (avi-num-frames avi))\n\t      for j from 0\n\t      do (setf (aref (avi-avih avi) (+ 16 j)) i\n\t\t       (aref (avi-strh avi) (+ 32 j)) i))\n\t(incf len\n\t      (write-list s \"hdrl\" `((\"avih\" ,(avi-avih avi))\n\t\t\t\t     (\"LIST\" \"strl\"\n\t\t\t\t      ((\"strh\" ,(avi-strh avi))\n\t\t\t\t       (\"strf\" ,(avi-strf avi)))))))\n\t(incf len\n\t      (write-list s \"movi\" (let ((cur-pos 4))\n\t\t\t\t     (mapcar #'(lambda (data)\n\t\t\t\t\t\t (let ((len (third data)))\n\t\t\t\t\t\t   (push (list cur-pos len) frames-pos)\n\t\t\t\t\t\t   (incf cur-pos (+ 8 len)))\n\t\t\t\t\t\t `(\"00dc\" ,@data))\n\t\t\t\t\t     (avi-frames avi)))))\n\t(setf frames-pos (nreverse frames-pos))\n\n\t(incf len\n\t      (write-chunk s \"idx1\"\n\t\t\t   (coerce (mapcan #'(lambda (pos-len)\n\t\t\t\t\t       (append '(#x30 #x30 #x64 #x63) ; 00dc RIFF header\n\t\t\t\t\t\t       '(#x10 #x00 #x00 #x00) ; FLAGS\n\t\t\t\t\t\t       (long->seq (first pos-len))\n\t\t\t\t\t\t       (long->seq (second pos-len))))\n\t\t\t\t\t   frames-pos) 'array)))\n\t\t\t\t\t\t     \n\t\n\t(file-position s pos)\n\t(write-long len s))\n      )))\n<\/pre>\n
Manipulating movies<\/h3>\n
\"Alt<\/div>\n<\/p>\n
Now that the basic functionality has been implemented, we can start to
\nwork on movies, and reorganize frames. This is done by working on the
\nframe list stored in AVI objects. In order to work nondestructively on
\navi movies, we define a function COPY-AVI which copies the avi header
\nand the stream headers out of an AVI object, but allows the programmer
\nto supply a new frame list. This function will be the basic building
\nblock for all the editing algorithms we will implement later on.<\/p>\n
\n(defmethod copy-avi ((avi avi) &key (frames :noframes) strh type strf avih (class 'avi))\n  (make-instance class\n\t :type (or type (avi-type avi))\n\t :strh (or strh (avi-strh avi))\n\t :strf (or strf (avi-strf avi))\n\t :avih (or avih (avi-avih avi))\n\t :frames (if (eq frames :noframes)\n\t\t     (avi-frames avi)\n\t\t     frames)))\n\n(defmethod copy-frames ((avi avi))\n  (copy-list (avi-frames avi)))\n<\/pre>\n
We are now ready for the first algorithm, which is just pasting avi
\nmovies together (the original functionality of avisplice).<\/p>\n
\n(defmethod concatenate-avis (avis)\n  (copy-avi (first avis) :frames (mapcan #'copy-frames avis)))\n<\/pre>\n
Now that was quite elegant, now we want to extract segments out of
\navis, maybe using a random start and a random length.<\/p>\n
\n(defmethod subsegment ((avi avi) &key start length random)\n  (let ((len (length (avi-frames avi))))\n    (if random\n\t(progn\n\t  (unless start\n\t    (setf start (random len)))\n\t  (unless length\n\t    (setf length (random (- len  start)))))\n\t(progn (unless start (setf start 0))))\n    (copy-avi avi :frames (subseq (avi-frames avi) start (when length (+ start length))))))\n<\/pre>\n
Let’s split avi files into groups of N frames.<\/p>\n
\n(defun group-by (list n)\n  (do ((i 0 (1+ i))\n       (l list (cdr l))\n       group res)\n      ((null l)\n       (when group (push (nreverse group) res))\n       (nreverse res))\n    (push (first l) group)\n    (when (= (length group) n)\n      (push (nreverse group) res)\n      (setf group nil))))\n\n(defmethod split-avi ((avi avi) n)\n  (let ((groups (group-by (avi-frames avi) n)))\n    (mapcar #'(lambda (frames)\n\t\t(copy-avi avi :frames frames)) groups)))\n<\/pre>\n
We can also write a few manipulation functions to permutate avis,
\nreverse them. Notice that there is a version of the function producing
\na new AVI object, and another version producing a list of frames, for
\nfurther manipulation by list functions.<\/p>\n
\n(defun permutate-list (list)\n  (let* ((arr (coerce list 'array))\n\t (length (length arr)))\n    (dotimes (i length)\n      (let* ((i1 (random length))\n\t     (i2 (random length))\n\t     (tmp (aref arr i1)))\n\t(setf (aref arr i1) (aref arr i2)\n\t      (aref arr i2) tmp)))\n    (coerce arr 'list)))\n\n(defmethod reverse-avi ((avi avi))\n  (copy-avi avi :frames (reverse (avi-frames avi))))\n\n(defmethod permutate-avi ((avi avi) n)\n  (concatenate-avis (permutate-list (split-avi avi n))))\n\n(defmethod permutate-avi-to-segments ((avi avi) n)\n  (permutate-list (split-avi avi n)))\n\n(defmethod permutate-avis (avis n)\n  (concatenate-avis (permutate-list (mapcan #'(lambda (avi) (split-avi avi n)) avis))))\n\n(defmethod permutate-avis-to-segments (avis n)\n  (permutate-list (mapcan #'(lambda (avi) (split-avi avi n)) avis)))\n\n(defmethod crop-avi ((avi avi) &key (start 0) length)\n  (subsegment avi :start start :length length))\n\n<\/pre>\n
Other interesting editing algorithms are mixing different clips
\ntogether, taking N frames of the first, then N frames of the next,
\nproducing some kind of flickering effect (FLIMMERN is german for
\nFLICKERING).<\/p>\n
\n(defun flatten1 (list)\n  (let (res)\n    (dolist (l list)\n      (if (listp l)\n\t  (dolist (l2 l)\n\t    (push l2 res))\n\t  (push l res)))\n    (nreverse res)))\n\n(defun repeat (list n)\n  (loop repeat n\n\tappending list))\n\n(defun flimmern (groups n)\n  (loop for group1-2 on groups by #'cddr\n\tfor group1 = (car group1-2)\n\tfor group2 = (cadr group1-2)\n\tappending (if (and group1 group2)\n\t\t      (list group1\n\t\t\t    (repeat (list (first group2)\n\t\t\t\t\t  (car (last group1))) n)\n\t\t\t    group2)\n\t\t      (list group1))))\n\n(defmethod flimmer-avis (avis n)\n  (copy-avi (first avis) :frames (flatten1  (flimmern (mapcar #'avi-frames avis) n))))\n<\/pre>\n
Actually, there are no boundaries to what effects you can achieve, as
\nlong as you can write them down as a Lisp function \ud83d\ude42 You can get the
\ncomplete code to the movie editing software here<\/a>, but remember it
\nis a one-shot, ugly version that is being rewritten. The code can only
\nwork on the ordering of frames at the moment, but a very interesting
\nstep would be to manipulate the frames directly. I have some code to
\nload Quart Composer compositions and control them programmatically in
\nobjective C, and it would be quite interesting to build a Lisp bridge
\nto it. This way, a Lisp program could control the outlets of a
\ncomposition, feeding it with images, numerical values, music, and
\nproduce very nice video effects without having to control everything
\nper hand. I’ll have a look at it as soon as my powerbook is working
\nagain.<\/p>\n
A music video written in Lisp<\/h3>\n
\"Alt<\/div>\n<\/p>\n
I mentioned above that my goal was to produce a music video using the
\nediting software. I fell in love with “Ongyilkos Vasarnap” by Venetian
\nSnares, a dark remix of “Gloomy Sunday”, with a hypnotic 7\/4
\ndrum’n’bass beat. I first imported the audio track into live, warped
\nit and exported it to have a stable 144 bpm timing on the whole
\ntrack. I then took apart the track on paper, writing down specific
\nscenes, and also a few drum breaks. Sadly, I didn’t have enough time
\nto do this for the whole track, so most effects are not precisely beat
\nmatched (I’ll render a new version when I’ll have enough time). I had
\nsome very nice video clips of a friend hanging herself in a dark
\ncorridor. Actually all the video clips come from an art installation
\nby the friend for whom I wrote the software. The art installation,
\ncalled the Angstapparat (the Fear Machine) consisted of a long dark
\ncorridor built in the Pirateria<\/a> in
\nCologne. Inside the corridor were a few TV-screens showing clips
\nrecorded in the installation, and a camera recorded the visitors, also
\nprojecting the images on the outside of the installation. These images
\nwere later on manipulated by the artist, and reintroduced into the
\ninstallation.<\/p>\n
So I wrote down the story I imagined to the song: a girl enters the
\nmachine, there are flashbacks of happier times when she was laughing,
\nbut then she hangs herself, influenced by demons and ghosts, and
\nfinally she herself becomes a ghost and leaves the machine. Actually,
\nI’m not happy at all with the video, because it is overloaded with
\nvideo effects, there is no real basic rhythm, which shows that I have
\nno clue about movie editing \ud83d\ude42 . As mentioned above, I think that’s
\nexactly the danger of algorithmic art, doing something without
\nunderstanding its implications, something which I think comes only
\nwith a lot of work and effort.<\/p>\n
Anyway, I imagined the movie to consist of 9 “scenes”. The first two
\nscenes show the girl entering the machine, interrupted by flashes of
\nan eye and flashes of herself matching the music. The basic movie of
\nthe girl entering the machine is itself slowed down and sped up
\naccording to the rhythm of the song. The speed manipulation is done
\nusing the function BESCHLEUNIG-AVI (SPEED-AVI in german), which takes
\na movie and a list of frame offsets. An offset of 1 is the “standard”
\nspeed, and offset of 2 means skip the next frame, actually speeding up
\nthe movie by a factor of 2. A factor of 1\/3 means repeat each frame 3
\ntimes, actually slowing down the movie by a factor of 3.<\/p>\n
\n(defmethod beschleunig-avi ((avi avi) frame-speeds)\n  (copy-avi avi :frames\n\t    (loop with cur = 0\n\t\t  for speed in frame-speeds\n\t\t  collect (elt (avi-frames avi) (round cur))\n\t\t  do (incf cur speed))))\n<\/pre>\n
The speeds themselves are generated using the functions
\nMAKE-CONSTANT-SPEED and ACCELERATE2:<\/p>\n
\n(defun accelerate2 (from acc2 steps)\n  (loop for acc = 0 then (+ acc acc2)\n\tfor speed = from then (+ speed acc)\n\trepeat steps\n\tcollect speed))\n\n(defun make-constant-speed (speed length)\n  (make-list (round length) :initial-element speed))\n<\/pre>\n
Generating accelerations matching the music was done “by hand”. A list
\nof 4 different acceleration patterns was used. The different pattern
\nwere then chosen randomly.<\/p>\n
\n(defparameter *erster-abschnitt-speeds*\n  (list\n   (append (make-constant-speed 0.3 10)\n\t   (accelerate2 0.3 0.04 11)\n\t   (make-constant-speed 0.3 10)\n\t   (accelerate2 0.3 0.04 11)\n\t   (make-constant-speed 0.3 10)\n\t   (accelerate2 0.3 0.04 10)\n\t   (accelerate2 0.3 0.04 11))\n   (append (make-constant-speed 0.5 21)\n\t   (accelerate2 0.3 0.01 21)\n\t   (make-constant-speed 0.5 10)\n\t   (accelerate2 0.5 0.03 10)\n\t   (accelerate2 0.5 0.03 11))\n   (append (make-constant-speed 0.5 21)\n\t   (make-constant-speed 0.3 10)\n\t   (accelerate2 0.3 0.04 11)\n\t   (make-constant-speed 0.3 10)\n\t   (accelerate2 0.5 0.03 10)\n\t   (accelerate2 0.5 0.03 11))\n   (append (make-constant-speed 0.3 10)\n\t   (accelerate2 0.3 0.04 11)\n\t   (accelerate2 0.3 0.01 21)\n\t   (make-constant-speed 0.3 10)\n\t   (accelerate2 0.3 0.04 10)\n\t   (accelerate2 0.3 0.04 11))))\n\n(defun random-erster-abschnitt-speed ()\n  (random-elt *erster-abschnitt-speeds*))\n<\/pre>\n
The flashes for the first segment are chosen randomly. 20% of the time
\nthere will be the flash of an eye, the rest of the time the flash will
\nbe chosen from the clip of the girl entering the machine.<\/p>\n
\n(defun reinrenn-flash (n length)\n  (subsegment (permutate-avi *reinrenn* n) :length length))\n\n(defun augen-flash (n length)\n  (subsegment (permutate-avi *auge* n) :length length))\n\n(defmacro random-choice (&rest choices)\n  (let ((rand (gensym)))\n  `(let ((,rand (random 1.0)))\n    (cond ,@(loop for choice in choices\n\t\t  for p = (first choice) then (if (eql (first choice) t)\n\t\t\t\t\t\t  1.0\n\t\t\t\t\t\t  (+ p (first choice)))\n\t\t  when (> p 1.0)\n\t\t  do (error \"p can not be > 1.0\")\n\t\t  collect `((\n\n
These flashes are inserted on the beats of the music, with a varying\nlength and probability. The base pattern of the music is stored into a\nfunction called ERSTER-ABSCHNITT-SIMPLE-MUSTER\n(FIRST-SEGMENT-BASIC-PATTERN in german). On beat 1, 3, 5 and 7, with a\ndefault probability of 60%, a flash will be inserted.<\/p>\n\n
\n(defun erster-abschnitt-simple-muster (&optional (start 0) (func #'erster-abschnitt-flash)\n\t\t\t\t       &key (p 0.6))\n  (remove nil\n\t  `(,(when (\n\n
The first scene is then rendered using the function ERSTER-ABSCHNITT,\nwhich takes the sped up base movie, a list of patterns and flashes,\ninserting the flashes on top of the base movie.<\/p>\n\n
\n(defun reinrenn-grundfilm ()\n  (let* ((reinrenn (repeat-loop-avi *reinrenn* 1))\n\t (film\n\t  (schedule-avis (loop for i from 0 below 16\n\t\t\t       with start = 0\n\t\t\t       for speed = (random-erster-abschnitt-speed)\n\t\t\t       for segment = (beschleunig-avi (subsegment reinrenn :start start) speed)\n\t\t\t       collect (list segment (beat-length (1+ (* 7.0 i))))\n\t\t\t       do (incf start (count-speed-frames speed))))))\n    (setf *erster-abschnitt-grundfilm* (subsegment film :length (round (* 8 *takt-frames*)))\n\t  *zweiter-abschnitt-grundfilm* (subsegment film :start (round (* 8 *takt-frames*))\n\t\t\t\t\t\t    :length (round (* 8 *takt-frames*))))))\n\n(defun erster-abschnitt ()\n  (insert-avis *erster-abschnitt-grundfilm*\n\t       (beat-offsets->avi-offsets\n\t\t(append `((,(erster-abschnitt-flash 2) 3)\n\t\t\t  (,(erster-abschnitt-flash 2) 5)\n\t\t\t  (,(erster-abschnitt-flash 4) 7))\n\t\t\t(erster-abschnitt-simple-muster 7)\n\t\t\t(erster-abschnitt-simple-muster 14)\n\t\t\t`((,(erster-abschnitt-flash 2) 22)\n\t\t\t  (,(erster-abschnitt-flash 2) 24)\n\t\t\t  (,(erster-abschnitt-flash 2) 28)\n\t\t\t  (,(erster-abschnitt-flash 10) 28))\n\t\t\t(erster-abschnitt-simple-muster 28)\n\t\t\t(erster-abschnitt-simple-muster 35)\n\t\t\t(erster-abschnitt-simple-muster 42)\n\t\t\t`((,(erster-abschnitt-flash 2) 50)\n\t\t\t  (,(erster-abschnitt-flash 2) 52)\n\t\t\t  (,(erster-abschnitt-flash 2) 54)\n\t\t\t  (,(erster-abschnitt-flash 10) 56))))\n\t       :insert nil))\n<\/pre>\n
The other eight scenes are generated in a similar way, using different
\nflash parameters, other effects for the base movies. The resulting
\nmovie is available here<\/a> (thank you xach), meanwhile the code can be
\ndownloaded here<\/a>. The movie is
\nactually quite bad, for the reasons I mentioned above. Because of the
\ndeadline, I didn't take enough time to keep good scenes, understand
\nthe effects, and so on. As a result, the movie is overloaded with
\nflashes and flickering effects, and has no \"real rhythm\". However, I
\nthink it is a quite interesting way to go, a way which is pretty
\nconventional in music for example. I didn't find much on algorithmic
\nmovie editing though, and would be quite interested if someone could
\ngive me some pointers.<\/p>\n
Future ideas<\/h3>\n
The next step is going to be the complete rewrite, and adding a GUI
\nto the software so that non-hackers can use it. The challenge here is
\nto preserve the flexibility to integrate new algorithms, combine them,
\nstore them and apply them on different movie snippets. Another
\nimportant feature will be to store the process that produced a certain
\nclip, including the random values produced. It should be possible for
\neach frame to trace where it came from, which algorithms it went
\nthrough, and which random values or external values influenced the
\nalgorithms.<\/p>\n","protected":false},"excerpt":{"rendered":"
Algorithmic art While composing music for a movie by a friend, I took a closer look at how he was editing the raw movie material. He was working with what I’ll be calling “effects”, for example movie fluttering, where a … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[19,3],"tags":[],"class_list":["post-145","post","type-post","status-publish","format-standard","hentry","category-english","category-lispstaub"],"_links":{"self":[{"href":"https:\/\/blogs.bl0rg.net\/netzstaub\/wp-json\/wp\/v2\/posts\/145","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.bl0rg.net\/netzstaub\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.bl0rg.net\/netzstaub\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.bl0rg.net\/netzstaub\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.bl0rg.net\/netzstaub\/wp-json\/wp\/v2\/comments?post=145"}],"version-history":[{"count":0,"href":"https:\/\/blogs.bl0rg.net\/netzstaub\/wp-json\/wp\/v2\/posts\/145\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.bl0rg.net\/netzstaub\/wp-json\/wp\/v2\/media?parent=145"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.bl0rg.net\/netzstaub\/wp-json\/wp\/v2\/categories?post=145"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.bl0rg.net\/netzstaub\/wp-json\/wp\/v2\/tags?post=145"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}