| 1 |
(* |
| 2 |
Copyright © 2008 Russell O’Connor |
| 3 |
|
| 4 |
Permission is hereby granted, free of charge, to any person obtaining a copy of |
| 5 |
this proof and associated documentation files (the "Proof"), to deal in |
| 6 |
the Proof without restriction, including without limitation the rights to |
| 7 |
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of |
| 8 |
the Proof, and to permit persons to whom the Proof is furnished to do so, |
| 9 |
subject to the following conditions: |
| 10 |
|
| 11 |
The above copyright notice and this permission notice shall be included in all |
| 12 |
copies or substantial portions of the Proof. |
| 13 |
|
| 14 |
THE PROOF IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| 15 |
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS |
| 16 |
FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR |
| 17 |
COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER |
| 18 |
IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
| 19 |
CONNECTION WITH THE PROOF OR THE USE OR OTHER DEALINGS IN THE PROOF. |
| 20 |
*) |
| 21 |
From Coq Require Import ZArith. |
| 22 |
Require Import CoRN.algebra.RSetoid. |
| 23 |
Require Import CoRN.metric2.Metric. |
| 24 |
Require Import CoRN.metric2.UniformContinuity. |
| 25 |
Require Export CoRN.raster.Raster. |
| 26 |
Require Import CoRN.reals.fast.Interval. |
| 27 |
Require Export CoRN.metric2.FinEnum. |
| 28 |
Require Export CoRN.metric2.ProductMetric. |
| 29 |
Require Import CoRN.logic.Classic. |
| 30 |
|
| 31 |
Set Implicit Arguments. |
| 32 |
(** |
| 33 |
** Rasters on Planes |
| 34 |
By attaching coordinates to the top-left and bottom-right corners of |
| 35 |
a raster, it can be interpreted as a finite set in [Q]^2. *) |
| 36 |
Definition Q2 := (ProductMS Q_as_MetricSpace Q_as_MetricSpace). |
| 37 |
|
| 38 |
(** For [Q2], classical membership in a finite enumeration is the |
| 39 |
same as a constructive membership. *) |
| 40 |
Lemma InStrengthen : forall x (l:FinEnum Q2), |
| 41 |
InFinEnumC x l -> exists y : Q2, In y l /\ msp_eq x y. |
| 42 |
Proof. |
| 43 |
induction l. |
| 44 |
intro abs. exfalso; exact (FinSubset_ball_nil abs). |
| 45 |
intros H. |
| 46 |
assert (L:msp_eq x a \/ ~msp_eq x a). |
| 47 |
destruct (Qeq_dec (fst x) (fst a)). |
| 48 |
destruct (Qeq_dec (snd x) (snd a)). |
| 49 |
left. |
| 50 |
split; apply Qball_0; auto. |
| 51 |
right; intros [_ B]. |
| 52 |
apply Qball_0 in B. contradiction. |
| 53 |
right; intros [B _]. |
| 54 |
apply Qball_0 in B. contradiction. |
| 55 |
destruct L. |
| 56 |
exists a. |
| 57 |
split; auto with *. |
| 58 |
destruct (IHl) as [y [Hy0 Hy1]]. |
| 59 |
apply FinSubset_ball_orC in H. |
| 60 |
destruct H as [G | H | H] using orC_ind. |
| 61 |
intro abs. contradict G; intro G. contradiction. |
| 62 |
elim H0; auto. |
| 63 |
exact H. |
| 64 |
exists y. |
| 65 |
split; auto with *. |
| 66 |
Qed. |
| 67 |
|
| 68 |
Definition InterpRow (up : list Q) (v:list bool) : list Q := |
| 69 |
map (@fst _ _ ) (filter (@snd _ _) (combine up v)). |
| 70 |
|
| 71 |
(* TODO define on sparse rasters directly. *) |
| 72 |
Definition CentersOfPixels (n m:positive) (pixels : raster n m) (tl br:Q2) |
| 73 |
: FinEnum Q2 := |
| 74 |
let (l,t) := tl in |
| 75 |
let (r,b) := br in |
| 76 |
let up := (UniformPartition l r n) in |
| 77 |
flat_map (fun (p:Q*list bool) => let (y,r):=p in map (fun x => (x,y)) (InterpRow up r)) |
| 78 |
(combine (UniformPartition t b m) (let (d):=pixels in d)). |
| 79 |
|
| 80 |
(** Notation for the interpretation of a raster. *) |
| 81 |
Notation "a ⇱ b ⇲ c" := (CentersOfPixels b a c) (at level 1, |
| 82 |
format "a ⇱ '[v' '/' b ']' '[v' '/' ⇲ c ']'") : raster. |
| 83 |
|
| 84 |
(* |
| 85 |
Local Open Scope raster. |
| 86 |
Local Open Scope raster_parsing. |
| 87 |
|
| 88 |
Example ex5 := |
| 89 |
(0, 1)⇱ |
| 90 |
⎥█░█⎢ |
| 91 |
⎥░█░⎢ |
| 92 |
⎥░░█⎢ |
| 93 |
⇲(1, 0). |
| 94 |
|
| 95 |
Eval compute in (ex5). |
| 96 |
*) |
| 97 |
|
| 98 |
Lemma In_map_snd_const |
| 99 |
: forall A (v : list A) f (a b : Q), |
| 100 |
In a (map f v) |
| 101 |
-> In (a,b) (map (fun x => (f x, b)) v). |
| 102 |
Proof. |
| 103 |
induction v. |
| 104 |
- intros. contradiction H. |
| 105 |
- intros. simpl. destruct H. |
| 106 |
subst a0. left. reflexivity. |
| 107 |
right. apply IHv, H. |
| 108 |
Qed. |
| 109 |
|
| 110 |
Lemma In_filtered_list |
| 111 |
: forall (l : list Q) (q : Q) (filterList : list bool) (j : nat), |
| 112 |
(length filterList <= length l)%nat |
| 113 |
-> Is_true (nth j filterList false) |
| 114 |
-> In (nth j l q) |
| 115 |
(map fst (filter snd (combine l filterList))). |
| 116 |
Proof. |
| 117 |
induction l. |
| 118 |
- intros. destruct filterList. 2: exfalso; inversion H. |
| 119 |
exfalso. simpl in H0. destruct j; contradiction. |
| 120 |
- intros. destruct filterList. |
| 121 |
destruct j; contradiction. |
| 122 |
simpl in H. apply le_S_n in H. |
| 123 |
simpl. destruct j. |
| 124 |
+ simpl in H0. destruct b. 2: contradiction. |
| 125 |
left. reflexivity. |
| 126 |
+ destruct b. |
| 127 |
right. exact (IHl q _ _ H H0). |
| 128 |
exact (IHl q _ _ H H0). |
| 129 |
Qed. |
| 130 |
|
| 131 |
Lemma In_filter_list |
| 132 |
: forall (filterList : list bool) (j : nat), |
| 133 |
Is_true (nth j filterList false) |
| 134 |
-> (j < length filterList)%nat. |
| 135 |
Proof. |
| 136 |
induction filterList. |
| 137 |
- intros. destruct j; contradiction. |
| 138 |
- intros. destruct j. simpl. apply le_n_S, Nat.le_0_l. |
| 139 |
simpl. apply le_n_S. apply IHfilterList, H. |
| 140 |
Qed. |
| 141 |
|
| 142 |
Lemma Vector_bool_in |
| 143 |
: forall (v : list bool) j, |
| 144 |
Is_true (nth j v false) -> (j < length v)%nat. |
| 145 |
Proof. |
| 146 |
induction v. |
| 147 |
- intros j H. destruct j; contradiction H. |
| 148 |
- intros j H. simpl in H. |
| 149 |
destruct j. apply le_n_S, Nat.le_0_l. |
| 150 |
simpl. apply le_n_S, IHv, H. |
| 151 |
Qed. |
| 152 |
|
| 153 |
Lemma RasterIndex_in |
| 154 |
: forall m n i j (r : raster n m), |
| 155 |
raster_well_formed r -> |
| 156 |
Is_true (RasterIndex r i j) -> (i < Pos.to_nat m /\ j < Pos.to_nat n)%nat. |
| 157 |
Proof. |
| 158 |
intros. destruct r as [l]. |
| 159 |
destruct H. rewrite <- H. |
| 160 |
simpl in H0. |
| 161 |
clear H m. |
| 162 |
simpl in H0. |
| 163 |
revert H0. revert i j. induction l as [|a l]. |
| 164 |
- intros. exfalso. simpl in H0. |
| 165 |
destruct i; destruct j; contradiction. |
| 166 |
- intros. |
| 167 |
inversion H1. subst l0. subst x. clear H1. |
| 168 |
specialize (IHl H4). |
| 169 |
destruct i. |
| 170 |
+ split. apply le_n_S, Nat.le_0_l. |
| 171 |
apply Vector_bool_in in H0. |
| 172 |
rewrite <- H3. exact H0. |
| 173 |
+ specialize (IHl i j H0). |
| 174 |
split. apply le_n_S, IHl. apply IHl. |
| 175 |
Qed. |
| 176 |
|
| 177 |
(** Correctness properties of our interpretation. *) |
| 178 |
Section InterpRasterCorrect. |
| 179 |
|
| 180 |
Let f := fun l r (n:positive) (i:Z) => l + (r - l) * (2 * i + 1 # 1) / (2 * Zpos n # 1). |
| 181 |
|
| 182 |
Lemma InterpRaster_correct1 |
| 183 |
: forall n m (t l b r:Q) (bitmap: raster n m) i j, |
| 184 |
raster_well_formed bitmap |
| 185 |
-> Is_true (RasterIndex bitmap i j) |
| 186 |
-> In (f l r n (Z.of_nat j), f t b m (Z.of_nat i)) |
| 187 |
(CentersOfPixels bitmap (l,t) (r,b)). |
| 188 |
Proof. |
| 189 |
intros n m t l b r bitmap. |
| 190 |
unfold CentersOfPixels, InterpRow, UniformPartition. |
| 191 |
fold (f l r n). |
| 192 |
fold (f t b m). |
| 193 |
generalize (f l r n) (f t b m). |
| 194 |
clear t l b r f. |
| 195 |
unfold RasterIndex. |
| 196 |
intros. |
| 197 |
pose proof (RasterIndex_in i j _ H H0) as [iin jin]. |
| 198 |
destruct bitmap as [bitmap], H. |
| 199 |
apply in_flat_map. |
| 200 |
exists (nth i (map q0 (iterateN_succ 0 m)) (q0 0%Z), nth i bitmap nil). |
| 201 |
split. |
| 202 |
- rewrite <- (combine_nth (map q0 (iterateN_succ 0 m)) bitmap i (q0 0%Z) nil). |
| 203 |
apply nth_In. |
| 204 |
rewrite combine_length, map_length, iterateN_succ_length. |
| 205 |
apply Nat.min_case. exact iin. |
| 206 |
rewrite H. exact iin. |
| 207 |
rewrite map_length, iterateN_succ_length, H. |
| 208 |
reflexivity. |
| 209 |
- rewrite map_map. |
| 210 |
replace (q0 (Z.of_nat i)) |
| 211 |
with (nth i (map q0 (iterateN_succ 0 m)) (q0 0%Z)). |
| 212 |
apply In_map_snd_const. |
| 213 |
replace (q (Z.of_nat j)) |
| 214 |
with (nth j (map q (iterateN_succ 0 n)) (q 0%Z)). |
| 215 |
apply In_filtered_list. |
| 216 |
2: exact H0. |
| 217 |
rewrite map_length, iterateN_succ_length. |
| 218 |
rewrite Forall_forall in H1. |
| 219 |
rewrite (H1 (nth i bitmap nil)). |
| 220 |
apply Nat.le_refl. |
| 221 |
apply nth_In. rewrite H. exact iin. |
| 222 |
rewrite map_nth. apply f_equal. |
| 223 |
apply iterateN_succ_nth, jin. |
| 224 |
rewrite map_nth. apply f_equal. |
| 225 |
apply iterateN_succ_nth, iin. |
| 226 |
Qed. |
| 227 |
|
| 228 |
Lemma InterpRaster_correct2 : forall n m (t l b r:Q) x y (bitmap: raster n m), |
| 229 |
raster_well_formed bitmap -> |
| 230 |
In (x,y) (CentersOfPixels bitmap (l,t) (r,b)) -> |
| 231 |
exists p, Is_true (RasterIndex bitmap (fst p) (snd p)) /\ x=f l r n (Z.of_nat (snd p)) |
| 232 |
/\ y=f t b m (Z.of_nat (fst p)). |
| 233 |
Proof. |
| 234 |
intros n m t l b r x y bitmap. |
| 235 |
unfold CentersOfPixels, InterpRow, UniformPartition. |
| 236 |
fold (f l r n). |
| 237 |
fold (f t b m). |
| 238 |
generalize (f l r n) (f t b m). |
| 239 |
clear t l b r f. |
| 240 |
intros q q0 wf H. apply in_flat_map in H. |
| 241 |
destruct H as [[s v] [H H0]]. |
| 242 |
destruct bitmap as [bitmap]. simpl. |
| 243 |
destruct wf. |
| 244 |
apply In_nth with (d:=(q0 0%Z, nth 0 bitmap nil)) in H. |
| 245 |
destruct H as [i [ilt H]]. |
| 246 |
rewrite combine_length, map_length, iterateN_succ_length in ilt. |
| 247 |
assert (i < Pos.to_nat m)%nat. |
| 248 |
{ apply (Nat.lt_le_trans _ _ _ ilt), Nat.le_min_l. } |
| 249 |
clear ilt. |
| 250 |
rewrite combine_nth in H. |
| 251 |
2: rewrite map_length, iterateN_succ_length, H1; reflexivity. |
| 252 |
inversion H. clear H. subst s. subst v. simpl in H0. |
| 253 |
rewrite map_map in H0. |
| 254 |
apply in_map_iff in H0. |
| 255 |
destruct H0 as [[s b] [H H0]]. |
| 256 |
unfold fst in H. |
| 257 |
inversion H. clear H. |
| 258 |
subst s. clear H6 y. |
| 259 |
apply filter_In in H0. |
| 260 |
destruct H0. unfold snd in H0. subst b. |
| 261 |
apply In_nth with (d:= (q 0%Z,true)) in H. |
| 262 |
destruct H as [j [jlt H]]. |
| 263 |
rewrite Forall_forall in H2. |
| 264 |
rewrite combine_nth in H. |
| 265 |
inversion H. clear H H4 x. |
| 266 |
rewrite combine_length, map_length, iterateN_succ_length in jlt. |
| 267 |
assert (j < Pos.to_nat n)%nat. |
| 268 |
{ apply (Nat.lt_le_trans _ _ _ jlt). apply Nat.le_min_l. } |
| 269 |
clear jlt. |
| 270 |
exists (i,j). split. |
| 271 |
- simpl. |
| 272 |
rewrite (nth_indep _ false true). |
| 273 |
rewrite (nth_indep _ nil (nth 0 bitmap nil)). |
| 274 |
unfold Is_true. rewrite H5. trivial. |
| 275 |
rewrite H1. exact H3. |
| 276 |
rewrite H2. exact H. |
| 277 |
apply nth_In. rewrite H1. exact H3. |
| 278 |
- simpl. split. |
| 279 |
rewrite map_nth. |
| 280 |
apply f_equal. |
| 281 |
apply iterateN_succ_nth. |
| 282 |
exact H. |
| 283 |
rewrite map_nth. |
| 284 |
apply f_equal. |
| 285 |
apply iterateN_succ_nth, H3. |
| 286 |
- rewrite map_length, iterateN_succ_length. |
| 287 |
rewrite H2. reflexivity. |
| 288 |
apply nth_In. rewrite H1. exact H3. |
| 289 |
Qed. |
| 290 |
|
| 291 |
End InterpRasterCorrect. |
| 292 |
(* begin hide *) |
| 293 |
Add Parametric Morphism n m (bm:raster n m) (bmWf : raster_well_formed bm) |
| 294 |
: (@CentersOfPixels n m bm) |
| 295 |
with signature (@msp_eq _) ==> (@msp_eq _) ==> (@msp_eq _) as InterpRaster_wd. |
| 296 |
Proof. |
| 297 |
cut (forall (x1 x2 : Q2), msp_eq x1 x2 -> forall x3 x4 : Q2, |
| 298 |
msp_eq x3 x4 -> forall y, |
| 299 |
InFinEnumC y (CentersOfPixels bm x1 x3) -> |
| 300 |
InFinEnumC y (CentersOfPixels bm x2 x4)). |
| 301 |
{ intro L. split. discriminate. split. |
| 302 |
intros q H1 abs. |
| 303 |
contradiction (abs q). split. exact (L x y H x0 y0 H0 q H1). |
| 304 |
reflexivity. |
| 305 |
intros q H1 abs. |
| 306 |
contradiction (abs q). split. |
| 307 |
symmetry in H, H0. |
| 308 |
exact (L y x H y0 x0 H0 q H1). |
| 309 |
reflexivity. } |
| 310 |
intros [x1l x1r] x2 Hx [y1l y1r] y2 Hy z Hz. |
| 311 |
destruct (@InStrengthen _ _ Hz) as [[ax ay] [Ha0 Ha1]]. |
| 312 |
destruct (InterpRaster_correct2 _ _ _ _ _ _ _ bmWf Ha0) |
| 313 |
as [[bx by'] [Hb0 [Hb1 Hb2]]]. |
| 314 |
rewrite Hb1 in Ha1. |
| 315 |
rewrite Hb2 in Ha1. |
| 316 |
unfold snd, fst in Ha1. |
| 317 |
destruct x2 as [x2l x2r]. |
| 318 |
destruct y2 as [y2l y2r]. |
| 319 |
assert (L0:msp_eq z ((x2l + (y2l - x2l) * (2 * Z.of_nat by' + 1 # 1) / (2 * Zpos n # 1)), |
| 320 |
(x2r + (y2r - x2r) * (2 * Z.of_nat bx + 1 # 1) / (2 * Zpos m # 1)))). |
| 321 |
transitivity ((x1l + (y1l - x1l) * (2 * Z.of_nat by' + 1 # 1) / (2 * Zpos n # 1)), |
| 322 |
(x1r + (y1r - x1r) * (2 * Z.of_nat bx + 1 # 1) / (2 * Zpos m # 1))). |
| 323 |
auto. |
| 324 |
clear - Hx Hy. |
| 325 |
destruct Hx as [Hx1 Hx2]. |
| 326 |
destruct Hy as [Hy1 Hy2]. |
| 327 |
split; unfold fst,snd in *. |
| 328 |
apply Qball_0 in Hx1. |
| 329 |
apply Qball_0 in Hy1. |
| 330 |
rewrite -> Hx1, Hy1. |
| 331 |
reflexivity. |
| 332 |
apply Qball_0 in Hx2. |
| 333 |
apply Qball_0 in Hy2. |
| 334 |
rewrite -> Hx2, Hy2. |
| 335 |
reflexivity. |
| 336 |
unfold InFinEnumC. |
| 337 |
rewrite -> (@FinSubset_ball_wd _ z _ 0 0 |
| 338 |
(CentersOfPixels bm (x2l, x2r) (y2l, y2r)) |
| 339 |
(reflexivity _) L0). |
| 340 |
apply InFinEnumC_weaken. |
| 341 |
auto using InterpRaster_correct1. |
| 342 |
Qed. |
| 343 |
(* end hide *) |