Category Archives: Teaching

Oct 06 0 comments
Enseignement, Popularization

L'image numérique nobélisée, l'occasion d'expliquer le fonctionnement des CCDs

Translate original post with Google Translate

Je ne fais que très rarement de commentaires sur l'actualité, mais cette année le comité Nobel à choisi de récompenser les travaux des "maîtres de la lumières" (voir le billet de S. Huet ou celui de A. Gunthert) : Charles K. Kao, Willard S. Boyle, George E. Smith. Les deux derniers pour l'invention de l'imageur semi-conducteur qui a permis à l'image numérique de prendre son essor : le CCD (Charged Coupled Device). Le CCD est le récepteur d'image que l'on trouve dans les appareils photos numériques et les camescopes. Ce récepteur tend à être remplacé par des capteurs CMOS, moins consommateurs d'énergie mais moins précis. Je ne peux donc que me réjouir de cette annonce car c'est la première fois qu'un Nobel récompense des travaux dans un domaine proche du mien.

Je profite donc de l'occasion pour expliquer comment fonctionne un capteur CCD.

ccd

Get the whole story »

Sep 25 3 comments
Enseignement, Research

Image representation (Clojure and Java), part one

In a previous post (Digital images and arrays : the same thing ?) i moaned about the lack of support of negative coordinate in image representations. In order to go beyond a simple observation, and because i need it, here is my firsts lines (of code) on this subject.

First, what are the constraints? I write my programs in Clojure. Why? Because it is a Lisp and i love Lisps. Then because it is a efficient and dynamic language, running on the jvm. This last point is important because my programs need to be portable. In ordre to be really portable, my image representation needs to be usable by a java developper. Thus, I must write a class. But as i dislike Java (the language), this class will be written in Clojure. This is a good exercise of interoperability.

Definitions

From a very generalized point of view, an image is nothing else but a bounded two-dimensional function. The imfun class will be a child of clojure.lang.IFn, the interface representing functions in Clojure. This class contains an invoke method called when an instance is used as a function. It is only needed as internal state for each instance : a definition domain and a function. Here is the beginning of Imfun:

(ns tip.Imfun
  (:gen-class
   :implements [clojure.lang.IFn]
   :state state
   :init init
   :methods [[fun [] clojure.lang.IFn]
             [domain [] clojure.lang.IPersistentCollection]]
   :constructors {[clojure.lang.IPersistentCollection clojure.lang.IFn] []}))
Some details:

  • the first line gives the used namespace: Imfun,
  • :gen-class allows creation of *.class files,
  • this class implements the clojure.lang.IFn interface,
  • the internal state is store in state,
  • the initialisation of an instance is realized with the init function,
  • two methods are exposed : fun and domain,
  • the constructor arguments are : a collection (for the definition domain) and a function.

The init function must returns a vector with : 1/ the arguments to be passed to the parent constructor (nothing here), and 2/ the current instance state. the init arguments must comply the ones defined with :constructor. 

(defn -init [dom f]
  [[] [dom f]])
The two methods fun and domain must returns the underlying function and the definition domain, all stored in state. 
(defn -domain [this]
  (first (.state this)))
(defn -fun [this]
  (second (.state this)))
The invoke method is called when the instance is applied as a function. At this moment, the coordinates must be checked to be inside the definition domain (thanks to indom? function). If the coordinates are outside, the value 0 is returned (this will be changed in the future). 
(defn indom? [dom pt]
  (let [[start end] dom
        [x y] pt]
    (and (>= x (first start))
         (<= x (first end))
         (>= y (second start))
         (<= y (second end)))))



(defn -invoke
  ([this x y] (if (indom? (.domain this) [x y])
                ((.fun this) x y)
                0))
  ([this pt] (let [[x y] pt]
               (this x y))))

Files organisation and compilation

If my working directory is work, two sub-dirs must be created: src and classes. The generated *.class files will go in classes. The arborescence in src must be conforms to the namespace. Thus the previous lines of code should be put in a file work/src/tip/Imfun.clj. The compilation is then realized with:

fredm:work> java -cp clojure.jar:./src:./classes clojure.main -e "(compile 'tip.Imfun)"
(this step can be realized in the clojure repl (read-eval-print-loop))

Use

Open a clojure repl :

fredm:work> java -cp clojure.jar:./src:./classes clojure.main -e
Clojure 1.1.0-alpha-SNAPSHOT
user=> (import '(tip Imfun))
tip.Imfun
Let's create an image im, being defined from (-1, -1) to (1, 1) and returning the sum of the coordinates values: 
fredm:work> java -cp clojure.jar:./src:./classes clojure.main -e
Clojure 1.1.0-alpha-SNAPSHOT
user=> (def f #(+ %1 %2))



'user/f



user=> (def im (Imfun. [[-1 -1] [1 1]] f))



'user/im

im is a bounded function, returning 0 outside of its definition domain. 

user=> (.domain im)
[[-1 -1] [1 1]]
user=> (im -1 -1)
-2
user=> (im 0 1)
1
user=> (im 1 2)
0
It is even possible to apply im on two coordinates x and y, or to a collection of two elements containing the coordinates (i.e. a point): 
user=> (im 1 1)
2
user=> (im [1 1])
2
user=> (im '(1 1))
2
Here it is. Next time a second class will be written, heriting Imfun in order to define images with values stores in a two-dimensional array. In fact, an ImageProcessor from ImageJ library will be used.

FMN

Aug 26 0 comments
Teaching

Project Euler with Clojure (1)

The first Euler project problem is stated as :

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

A first naive solution, can be obtained from a range of integers between 0 and 999, retain only multiples of 3 and 5, and sum the remain ones: 

(def sum #(reduce + %))



(defn euler1-a []
  (sum (filter #(or (zero? (rem % 3))
                    (zero? (rem % 5)))
               (range 1000))))
The obtained value is: 
user> (euler1a)
233168
which is the good answer.

This solution is quite readable. It is some kind of direct translation of the problem into code. However it is not really effective in terms of computation time. All integers (under 1000) are examined. It would be faster to only examine multiples of 3 or 5.

A second solution comes when considering the sequence of 3-multiples: 

(range 0 1000 5)
It is thus only needed to sum the 3-multiples and the 5-multiples : 
user> (+ (sum (range 0 1000 3))
         (sum (range 0 1000 5)))
266333
The obtained value is wrong. Indeed, some numbers appear two times, in each sequence : the mutiples of 3 and 5. Here is a list of these multiples (under 100): 
user> (intersection (set (range 0 100 3)) (set (range 0 100 5)))



{0 75 45 15 90 60 30}

Actually, this is the list of the 15-multiples (i.e. 3 * 5). In order to compute the good value, we need to subtract the sum of the 15-multiples from the initial sum: 

(defn euler1-b []
  (+ (sum (range 0 1000 3))
     (sum (range 0 1000 5))
     (- (sum (range 0 1000 15)))))
This time the value is ok: 
user> (euler1b)
233168
In order to have some fun, here is a solution that only examines different multiples of 3 and 5. The idea is to have two counters, one for the 3-multiples and a second for the 5-multiples. A each iteration, only one counter is incremented (by 3 for the 3-multiples one, and by 5 for the 5-multiples). The value of the counter is added to the final sum: 
(defn euler1-c []
  (loop [x3 0
         x5 0
         s 0]
    (let [x3+ (+ 3 x3)
          x5+ (+ 5 x5)]
      (if (or (< x3+ 1000)
              (< x5+ 1000))
        (cond
          (= x3+ x5+) (recur x3+ x5+ (+ x3+ s))
          (< x3+ x5+) (recur x3+ x5 (+ x3+ s))
          :else (recur x3 x5+ (+ x5+ s)))
        s))))
For each iteration, the smallest counter is chosen to be incremented. By example if x3 equals 9 and x5 equals 10, then x3+ equals 12 and x5+ equals 15. In this case, x3 is incremented. If the two counters are equal, there are all incremented to avoid to add two times the same number. The obtained value is good: 
user> (euler1c)
233168
Here is a little computation time comparison based 1000 function calls: 
user> (defmacro timex [n stuff]
        `(time (dotimes [x# ~n]
                 ~stuff)))



'user/timex



user> (timex 1000 (euler1-a))
"Elapsed time: 2270.722148 msecs"
nil
user> (timex 1000 (euler1-b))
"Elapsed time: 1337.681488 msecs"
nil
user> (timex 1000 (euler1-c))
"Elapsed time: 534.767148 msecs"
nil
The function euler1-c is clearly the fastest, as it only examines the different multiples of 3 and 5. On the otherside, it is clearly not the more readable. As often, it a tradeoff.

FMN.