RANSAC fitting in Clojure

2013-02-26

RANdom SAmple Consensus is a robust non-deterministic method to fit model parameters to data in the presence of outliers. It works as a iteration of a basic non-robust model estimation. This snippet of code implements RANSAC in Clojure:

(defn ransac
  "RANdom SAmple Consensus, robust model fitting.

  data                a sequence of data points
  optimize-fn         : data -> model
  error-fn            : model -> datum -> error measure
  min-sample-size     the minimum number of data required to fit the model
  iters               number of iterations
  max-error           a threshold to determine when a datum fits
  min-consensus-size  the number of data values required to accept a consensus set"
  [data optimize-fn error-fn
   min-sample-size iters max-error min-consensus-size]
  (letfn [(ransac-step [best-model]
            (let [maybe-inliers (take min-sample-size (shuffle data))
                  other-data    (filter (comp not (set maybe-inliers)) data)
                  maybe-model   (optimize-fn maybe-inliers)
                  consensus-set (into maybe-inliers
                                      (filter #(< (error-fn maybe-model %) max-error)
                                              other-data))]
              (if (>= (count consensus-set) min-consensus-size)
                (let [new-model (optimize-fn consensus-set)
                      new-errors (map #(error-fn new-model %) consensus-set)
                      new-max-error (apply max new-errors)]
                  (if (< new-max-error (:max-error best-model))
                    {:model new-model
                     :consensus-set consensus-set
                     :max-error new-max-error}
                    best-model))
                best-model)))]
    (last
     (take iters
           (iterate ransac-step {:model nil
                                 :consensus-set nil
                                 :max-error Double/POSITIVE_INFINITY})))))