1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
let random_permutation a =
let len = Array.length a in
for i = 0 to Array.length a - 1 do
let n = Random.int (len - i) + i in
let v1 = a.(i) in
let v2 = a.(n) in
a.(i) <- v2;
a.(n) <- v1
done;
a
let random_indices n =
let a = Array.init n (fun i -> i) in
random_permutation a
let random_partition n a =
let indices = random_indices (Array.length a) in
( Array.init n (fun i -> a.(indices.(i)))
, Array.init (Array.length a - n) (fun i -> a.(indices.(i + n))) )
let array_filter f a =
let in_size = ref 0 in
for i = 0 to Array.length a - 1 do
let v = a.(i) in
if f v then (
let after_in = !in_size in
let v' = a.(after_in) in
a.(i) <- v';
a.(after_in) <- v;
incr in_size)
done;
Array.sub a 0 !in_size
type ('a, 'b) input =
{ model : 'a array -> 'b
; data : 'a array
; subset_size : int
; rounds : int
; distance : 'a -> 'b -> float
; filter_distance : float
; minimum_valid : int
; error : 'a array -> 'b -> float
}
type ('a, 'b) result = { model : 'b; input : 'a array; error : float }
let one_round (r : ('a, 'b) input) : ('a, 'b) result option =
let in_subset, _out_of_subset =
random_partition (min (Array.length r.data / 2) r.subset_size) r.data
in
let model = r.model in_subset in
let fiting =
array_filter (fun p -> r.distance p model < r.filter_distance) r.data
in
if Array.length fiting > r.minimum_valid then
let input = Array.append in_subset fiting in
let model = r.model input in
Some { model; input; error = r.error input model }
else None
let ransac r : (_, _) result option =
let rec loop n (best : (_, _) result option) =
if n >= r.rounds then best
else
let best =
match (one_round r, best) with
| res, None | None, res -> res
| (Some { error; _ } as new_best), Some { error = best_error; _ }
when error < best_error ->
new_best
| Some _, Some _ -> best
in
loop (n + 1) best
in
loop 0 None