Debian Codegraph @

reals/fast/RasterQ.v

raw
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 *)