-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathtutorial.html
875 lines (761 loc) · 39.8 KB
/
tutorial.html
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
<!DOCTYPE html>
<html>
<head>
<meta charset='utf-8' />
<meta http-equiv="X-UA-Compatible" content="chrome=1" />
<meta name="description" content="Jsreeram.github.com : jsreeram.github.com" />
<link rel="stylesheet" type="text/css" media="screen" href="stylesheets/stylesheet.css">
<title>River Trail</title>
<script type="text/javascript">
var fixGistRules = [
".gist .gist-highlight { border-left: 3ex solid #eee; position: relative;}",
".gist .gist-highlight pre { counter-reset: linenumbers;}",
".gist .gist-highlight pre div:before { color: #aaa; content: counter(linenumbers); counter-increment: linenumbers; left: -3ex; position: absolute; text-align: right; width: 2.5ex;}" ];
var head = document.getElementsByTagName('head')[0],
style = document.createElement('style');
rules = new Array();
var i=0;
for ( i=0; i< fixGistRules.length; i++ ){
var fullrule = document.createTextNode(fixGistRules[i]);
rules.push(fullrule);
}
style.type = 'text/css';
for ( var i=0; i< rules.length; i++ ){
if(style.styleSheet){
style.styleSheet.cssText = rules[i].nodeValue;
}else {
style.appendChild(rules[i]);
head.appendChild(style);
}
}
</script>
<script type="text/javascript" src="javascripts/XRegExp.js"></script> <!-- XRegExp is bundled with the final shCore.js during build -->
<script type="text/javascript" src="javascripts/shCore.js"></script>
<script type="text/javascript" src="javascripts/shBrushJScript.js"></script>
<link type="text/css" rel="stylesheet" href="stylesheets/shCoreDefault.css"/>
<link type="text/css" rel="Stylesheet" href="stylesheets/shThemeDefault.css" />
<script type="text/javascript">SyntaxHighlighter.all();</script>
</head>
<body>
<!-- HEADER -->
<div id="header_wrap" class="outer">
<header class="inner">
<a id="forkme_banner" href="https://github.com/rivertrail/rivertrail">View on GitHub</a>
<h1 id="project_title">Building a Video Effects Editor with River Trail</h1>
<h2 id="project_tagline">jsreeram.github.com</h2>
</header>
</div>
<!-- MAIN CONTENT -->
<div id="main_content_wrap" class="outer">
<section id="main_content" class="inner">
In this hands-on tutorial we will use River Trail to parallelize the
computationally instensive parts of a HTML5
video application. If you haven't already, read the <a
href="index.html">API description</a> and come back. It is also a
good idea to have this API description to refer to while reading
through this tutorial.
<h2>Index</h2>
<a href="#setup" style="cursor:pointer">1. Setup</a><br>
<a href="#skeleton" style="cursor:pointer">2. The Skeleton</a><br>
<a href="#manip" style="cursor:pointer" >3. Manipulating pixels on canvas</a><br>
<a href="#sepia" style="cursor:pointer" >4. Sepia Toning</a><br>
<a href="#3D" style="cursor:pointer" >5. Stereoscopic 3D</a><br>
<a href="#edge" style="cursor:pointer" >6. Edge Detection/Sharpening</a><br>
<!--<a href="#face" style="cursor:pointer" >7. Color-based Face
Detection</a><br>-->
<h2><a name="setup"></a>Setup</h2>
<h3>Download and Install</h3>If you have not already, <a
href="https://github.com/RiverTrail/RiverTrail/wiki">download
and install River Trail</a>. For this tutorial, you do
<strong>not</strong> need
to build the extension. You only need the
River Trail distribution and the River Trail binary
extension for Firefox.
To be able to manipulate video from a webcam you will also need
to install the <a
href="https://addons.mozilla.org/en-us/firefox/addon/mozilla-labs-rainbow/">Rainbow</a>
extension.
<h3>Configure</h3>
Because of Firefox's security policies, you may have to
install Apache (or another webserver) and configure it so that
it serves files from the River Trail directory.
<h3>Verify</h3>
To verify that extension is installed, go to the <a
href="http://rivertrail.github.com/RiverTrail/interactive/">interactive shell</a>
On the last line, you should see a message saying:<br><br>
<code>It appears that you have River Trail installed. Enabling
compiled mode...</code> <br><br>
If you see this, then the extension has been installed correctly.
However if you only see something like:<br><br>
<code>PS: This page uses the sequential library implementation of
River Trail. You won't need the extension but there will be no
speedup either.</code><br><br> then the extension isn't installed properly.
See the <a href="https://github.com/RiverTrail/RiverTrail/wiki"></a>
instructions to install it.<br><br>
Once the extension is installed correctly, try running one of the
included examples in <em>rivertrail/examples/</em>. For instance, the
n-body simulation example in <em>idf-demo</em>.
<!--Check if you can run the examples in
<em>rivertrail/examples </em> by loading them in Firefox. If you can,
you are good to go. -->
<h2><a name="skeleton"></a>The Skeleton </h2>
The directory <em>rivertrail/examples/video-app</em> contains a
skeleton for the video application that you can start with. Load up
<code>index.html</code> in this directory in Firefox and you should see the
default screen for the application skeleton:
<img src="images/skeleton3.png"/>
The large box in the center is a <a
href="https://developer.mozilla.org/en-US/docs/Canvas_tutorial">
Canvas </a> that is used for rendering the video output. The
video input is either a HTML5 video stream embedded in a <a href
="https://developer.mozilla.org/en-US/docs/HTML/Element/video">
video tag </a> or live video caputured by a webcam. On the
right of the screen you will see the various filters that can applied
to this input video stream - sepia toning, lightening, desaturation
etc. Click on the box in the center screen to start playback and try
out these filters. To switch to webcam video, click the "Webcam" toggle in
the top-left corner.
The sequential JavaScript versions of the filters on the right are already
implemented and in this tutorial we will implement the "parallel"
versions using River Trail. Before we dive into implementation, lets
look at the basics of manipulating video using the Canvas API.
<h2><a name="manip"></a> Manipulating pixels on Canvas </h2>
Open up <code>main.js</code> in your favorite code editor. This file implements
all the functionality in this web application except the filters
themselves. When you load the page, the <code>doLoad()</code> function is called
after the body of the webpage has been loaded. This function sets up
the drawing contexts, initializes the list of filters (or kernels)
and assigns a click event handler for the output canvas.
The <code>computeFrame()</code> function is the workhorse that reads an input
video frame, applies all the selected filters on it to produce an
output frame that is written to the output canvas context.
The code below shows how a single frame from a HTML video element is drawn to a 2D context associated with a canvas element.
<!--<p><script
src="http://gist.github.com/3419413.js#L2"></script></p>-->
<pre class="brush: js;first-line: 240">
// main.js : computeFrame()
output_context.drawImage(video, 0, 0, output_canvas.width,
output_canvas.height);
</pre>
After this video frame is drawn to canvas, we need to capture the
pixels so that we can apply our filters. This is done by calling
getImageData() on the context containing the image we want to
capture.
<pre class="brush: js;first-line: 248">
// main.js : computeFrame(), line number 249
frame = input_context.getImageData(0, 0, input_canvas.width,
input_canvas.height);
len = frame.data.length;
w = frame.width ; h = frame.height;
</pre>
Now we have an <a
href="https://developer.mozilla.org/en-US/docs/HTML/Canvas/Pixel_manipulation_with_canvas">ImageData</a>
object called <code>frame</code>. The <code>data</code> attribute of this
object contains the pixel information and the "width"/"height" attributes
contain the dimensions of the image we have captured.
The data attribute contains RGBA values for each pixel in a row-major format.
That is, for a frame with h rows of pixels and w columns, it contains a
1-dimensional array
of length w * h * 4 as shown below:<br>
<img src="images/imgdata.png" width="300"/><br>
So for example to get the color values of a pixel in the 100th row and
50th column in the image, we would do:
<pre class="brush: js;first-line: 1">
var red = frame.data[100*w*4 + 50*4 + 0];
var green = frame.data[100*w*4 + 50*4 + 1];
var blue = frame.data[100*w*4 + 50*4 + 2];
var alpha = frame.data[100*w*4 + 50*4 + 3];
</pre>
To set, for example the red value of this pixel, simply write the new value at the
offset shown above in the <code>frame.data</code> buffer.
<h2><a name="sepia"></a> Sepia Toning </h2>
<a
href="http://en.wikipedia.org/wiki/Photographic_print_toning#Sepia_toning">Sepia
Toning</a> is a process performed on black-and-white print
photographs to give them a warmer color. This filter simulates the
sepia toning process on digital photographs or video.
Let us first look at the sequential implementation of this filter in
the function called <code>sepia_sequential()</code> in filters.js.
<pre class="brush: js;first-line: 820">
function sepia_sequential(frame, len, ctx) {
var pix = frame.data;
var r = 0, g = 0, b = 0;
for(var i = 0 ; i < len; i = i+4) {
r = (pix[i] * 0.393 + pix[i+1] * 0.769 + pix[i+2] * 0.189);
g = (pix[i] * 0.349 + pix[i+1] * 0.686 + pix[i+2] * 0.168);
b = (pix[i] * 0.272 + pix[i+1] * 0.534 + pix[i+2] * 0.131);
if(r>255) r = 255;
if(g>255) g = 255;
if(b>255) b = 255;
if(r<0) r = 0;
if(g<0) g = 0;
if(b<0) b = 0;
pix[i] = r;
pix[i+1] = g;
pix[i+2] = b;
}
ctx.putImageData(frame, 0, 0);
}
</pre>
Remember from the previous snippet that the frame.data buffer
contains color values as a linear sequence of <strong>rgba</strong> values. The
<code>for</code> loop in line 823
iterates over this buffer and for each pixel it reads the red, green
and blue values (which are in <code>pix[i]</code>,
<code>pix[i+1]</code> and <code>pix[i+2]</code> respectively).
It computes a weighted average of these colors to produce the new
red, green, blue values for that pixel. It then clamps the new
red, green and blue values to [0, 255] and writes them back into the
"data" buffer. When the loop is finished, we have replaced the RGB
values for all the pixels with their sepia-toned values and we can
now write the image back into the output context <code>ctx</code>
with the <code><a href="http://www.whatwg.org/specs/web-apps/current-work/multipage/the-canvas-element.html#dom-context-2d-putimagedata">putImageData()</a></code>
method. The result should look like this (image on the left is the
original frame, image on the right is the output): <br>
<img src="images/se1.png" height="170"/>
<img src="images/se2.png" height="170"/>
<h3> Can we make this parallel? </h3>
If you look closely at the <code>sepia_sequential</code> function
above, you'll notice that each pixel can be processed independently
of all other pixels as its new RGB values depend only on its current
RGB values. And each iteration of the <code>for</code> loop does
not produce or consume side-effects. This makes it easy to
parallelize this operation with River Trail.
<p>Recall that the <em>ParallelArray</em> type has a constructor that
takes a canvas object as an arugment and returns a freshly minted
ParallelArray object containing the pixel data.</p>
<pre class="brush: js;first-line: 1">
var pa = new ParallelArray(canvas);
</pre>
This creates a 3-dimensional ParallelArray <code>pa</code> with shape
[h, w, 4] that looks like the following:
<img src="images/pacanvas1.png" height="300" style="margin:auto;display:block;"/>
So for pixel on the canvas at coordinates (x, y), pa.get(x, y, 0)
will contain the red value, pa.get(x, y, 1) will contain the green
value and pa.get(x, y, 2) will contain the blue value.
The input ParallelArray that is given to the filter(s) (line 253, main.js):
<pre class="brush: js;first-line: 253">
else if (execution_mode === "parallel") {
stage_output = stage_input = new ParallelArray(input_canvas);
w = input_canvas.width; h = input_canvas.height;
}
</pre>
<code>stage_input</code> and <code>stage_output</code> are
ParallelArray objects that contain the input and output pixel data
for each filtering "stage". Now lets look at the code that causes the
filters to be applied (line 271, main.js):
<pre class="brush: js;first-line: 271">
if(execution_mode === "parallel") {
switch(filterName) {
case "sepia":
case "lighten":
case "desaturate":
case "color_adjust":
case "edge_detect":
case "sharpen":
case "A3D":
case "face_detect":
break;
default:
}
// Make this filter's output the input to the next filter.
stage_input = stage_output;
}
</pre>
You will see that this code block is wrapped in a <code>for</code>
loop that iterates over all the available filters.
To implement a
particular filter, we add code to produce a new ParallelArray object
containing the transformed pixel data and assign it to
<code>stage_output</code>.
So for example, for the sepia filter, we would write:
<pre class="brush: js;first-line: 272; highlight:[275,276,277]">
...
switch(filterName) {
case "sepia":
stage_output = /*new parallel array containing
transformed pixel data */;
break;
...
</pre>
Now, all we have to do above is produce a new ParallelArray object
on the right-hand-side of the the statement above.
We can produce this new ParallelArray one of two ways - by using the
powerful ParallelArray constructor or by using the combine method.
Let us look at the constructor approach first. <br>
Recall the the comprehension constructor has the following form:
<pre class="brush: js;first-line: 1">
var pa = new ParallelArray(shape_vector, elemental_function,
arg1, arg2..);
</pre>
where elemental_function is a JavaScript function that produces the
value of an element at a particular index in <code>pa</code>.
Recall that the input to our filter <code>stage_input</code> is a [h,
w, 4] shaped ParallelArray. You can think of it as a two-dimensional
ParallelArray with shape [h, w] in which each element (which corresponds to
a single pixel) is itself a ParallelArray of shape [4].
<!--
where the first two dimensions correspond to the
2D corrdinates of the pixel in the image and the 3rd dimension
corresponds to the color values.
-->
The output ParallelArray we will
produce will have this same shape - we will produce a new
ParallelArray of shape [h, w] in which each element has a shape of
[4], thereby making the ParallelArray have a final shape of [h, w, 4].
Modify line 275 to this:
<pre class="brush: js;first-line: 272; highlight: [275, 276]">
...
switch(filterName) {
case "sepia":
stage_output = new ParallelArray([h, w], kernelName,
stage_input);
break;
...
</pre>
The first argument [h, w] specifies the shape of the new
ParallelArray we want to create.
<code>kernelName</code> is a Function object pointing to the
sepia elemental function (that we will talk about in a moment) and
<code>stage_input</code> is an argument to this elemental
function. This line of code creates a new
ParallelArray object of shape [h, w] in which each element is
produced by executing the function <code>kernelName</code>. This
new ParallelArray is then assigned to <code>stage_output</code>.
<br>
Finally, we have to create the elemental function that produces the
color values for each pixel. You can think of it as a function that
when supplied indices, produces the ParallelArray elements at those indices.
Create a function called <code>sepia_parallel</code> in filters.js as follows:
<pre class="brush: js;first-line: 1">
// elemental function for sepia
function sepia_parallel (indices, frame) {
}
</pre>
The first argument <code>indices</code> is a vector of indices from the
iteration space [h, w]. indices[0] is the index along
the 1st dimension (from 0 to h-1) and indices[1] is the index along
the 2nd dimension (from 0 to w-1).
<!--
[gray gradient kernel to show how these indices map to pixel coords,
although it is not strictly required for sepia] <br>
-->
The <code>frame</code> parameter is the ParallelArray object that was passed as an
argument to the constructor above.<br>
Now let's fill in the body of the elemental function.
<pre class="brush: js;first-line: 1;
highlight:[3,4,5,6,7,8,9,10,11,12,13]">
// elemental function for sepia
function sepia_parallel (indices, frame) {
var i = indices[0];
var j = indices[1];
var old_r = frame[i][j][0];
var old_g = frame[i][j][1];
var old_b = frame[i][j][2];
var a = frame[i][j][3];
var r = old_r*0.393 + old_g*0.769 + old_b*0.189;
var g = old_r*0.349 + old_g*0.686 + old_b*0.168;
var b = old_r*0.272 + old_g*0.534 + old_b*0.131;
return [r, g, b, a];
}
</pre>
In lines 3-9, we grab the indices and read the RGBA values from the
input ParallelArray <code>frame</code>. then, just like in the
sequential version we mix these colors in lines 11-13 and return a
4-element array consisting of the new color values for the pixel at
position <code>i, j</code>.
And thats it. Select the "River Trail" toggle on the top-right of the
app screen and play the video. You should see the same sepia toning
effect you saw with the sequential implementation.<p>
The River Trail compiler takes your elemental function and parallelizes
its application over the iteration space. Note that you did not have to
create or manage threads, write any non-JavaScript code or deal with
race conditions and deadlocks.
<h2>Exercise</h2>
We could have also implemented the sepia filter by calling the
<code>combine</code> method on the <code>stage_input</code> ParallelArray.
Let us try and write that.
<pre class="brush: js;first-line: 1">
stage_output = stage_input.combine(1, function(index) {
var old_r = this.get(index, 0);
var old_g = this.get(index, 1);
var old_b = this.get(index, 2);
var a = this.get(index, 3);
var r = old_r * 0.393 + old_g * 0.769 + old_b * 0.189;
var g = old_r * 0.349 + old_g * 0.686 + old_b * 0.168;
var b = old_r * 0.272 + old_g * 0.534 + old_b * 0.131;
return [r, g, b, a];
});
</pre>
<!--
[Do we have time to explain the combine alternative?]
-->
<h2><a name="3D"></a> Stereoscopic 3D</h2>
Let's consider a slightly more complicated filter - one that transforms
the input video stream into 3D in real time. <a
href="http://en.wikipedia.org/wiki/Stereoscopy">Stereoscopic 3D </a> is a
method of creating the illusion of depth by simulating the different
images that a normal pair of eyes see (see <a
href="http://en.wikipedia.org/wiki/Binocular_disparity">Binocular
Disparity</a>).
In essence, when looking at a 3-dimensional object our eyes each see a
slightly different 2D image due to the distance between them on our
head. Our brain uses this difference to extract depth information from
these 2D images.
To implement stereoscopic 3D, we will use this same methodology - we
present two 2D images each one slightly different from the other to the
viewer's eyes. The difference between these images - let's call them
left-eye and right-eye images; are two-fold. Firstly, the right-eye image
is offset slightly to the left in the horizontal direction. Secondly,
the red channel is masked off in the right-eye image and the blue and
green channels are masked off in the left-eye image. The result looks
something like the following (image on the left is the original, image
on the right is the 3d version).<br>
<div align="center">
<img src="images/42.png" height="130"/>
<img src="images/3d42-all.png" height="130"/>
<br>
</div>
Let's look at the sequential implementation first:
<pre class="brush: js;first-line: 810">
function A3D_sequential(frame, len, w, h, dist, ctx) {
var pix = frame.data;
var new_pix = new Array(len);
var r1, g1, b1;
var r2, g2, b2;
var rb, gb, bb;
for(var i = 0 ; i < len; i = i+4) {
var k = i-(dist*4);
if(Math.floor(j/(w*4)) !== Math.floor(i/(w*4))) j = i;
r1 = pix[i]; g1 = pix[i+1]; b1 = pix[i+2];
r2 = pix[k]; g2 = pix[k+1]; b2 = pix[k+2];
var left = dubois_blend_left(r1, g1, b1);
var right = dubois_blend_right(r2, g2, b2);
rb = left[0] + right[0] + 0.5;
gb = left[1] + right[1] + 0.5;
bb = left[2] + right[2] + 0.5;
new_pix[i] = rb;
new_pix[i+1] = gb;
new_pix[i+2] = bb;
new_pix[i+3] = pix[i+3];
}
for(var i = 0 ; i < len; i = i+1) {
pix[i] = new_pix[i];
}
ctx.putImageData(frame, 0, 0);
}
</pre>
Don't worry about the details of the implementation just yet, just note
that the structure is somewhat similar to the sepia filter. One important
distinction is that while the sepia filter updated the pixel data in-place,
we cannot do that here - processing each pixel involves reading a
neighboring pixel. If we updated in-place, we may end up reading the
updated value for this neighboring pixel. In other words, there is a
write-after-read loop carried dependence here. So instead of updating in place, we
allocate a new buffer <code>new_pix</code> for holding the updated
values of the pixels.<br><br>
Lets start implementing the parallel version. What we want to implement is an operation
that reads the pixel data in the input ParallelArray object and produces
new pixel data into another. So just like sepia we can use the constructor
+ elemental function approach.
<pre class="brush: js;first-line: 272; highlight: [275, 276]">
...
switch(filterName) {
case "A3D":
stage_output = new ParallelArray([h, w], kernelName,
stage_input, w, h);
break;
...
</pre>
Then create the elemental function in <code>filters.js</code> as follows:
<pre class="brush: js;first-line: 1; highlight:[1,2,3,4,5]">
// elemental function for 3D
function A3D_parallel (indices, frame, w, h, dist) {
var i = indices[0];
var j = indices[1];
}
</pre>
Each pair <code>(i, j)</code> corresponds to a pixel in the output
frame. Recall that each pixel such pixel in the output frame is
generated by blending two images - the left-eye and right-eye images
the latter being a copy of the former except shifted along the negative
x-axis (i.e., to the left).
<!--
So we first need two images from <code>frame</code> one for the left-eye and
one for the right-eye which is a copy of the left-eye image except it
is shifted along the negative x-axis (i.e., to the left).
-->
Let's call the pixel <code>frame[i][j]</code> the left eye pixel.
To get the right-eye pixel we will simply read a neighbor of the left
eye pixel that is some distance away. This distance is given to us the
the argument dist (which is updated everytime the 3D slider on the UI is
moved):
<pre class="brush: js;first-line: 1; highlight:[5,6]">
// elemental function for 3D
function A3D_parallel (indices, frame, w, h, dist) {
var i = indices[0];
var j = indices[1];
var k = j - dist;
if(k < 0) k = j;
}
</pre>
Now <code>frame[i][k]</code> is the right eye pixel. We need to guard
against the fact that if the distance is large we cannot get the right
eye pixel as it would be outside the frame we have. There are several
approaches for dealing with this situation - for simplicity we will
simply make the right eye pixel the same as the left eye pixel. Now,
lets mask off the appropriate colors in each of the left and right eye
pixels. We use the <code>dubois_blend_left/right()</code> functions for this. You
don't have to understand the details of these functions for this
tutorial; just that they take in an RGB tuple and produce new RGB tuple
that is appropriately masked for the right and left eyes. For details
on these functions, read about the Dubois method <a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=941256&tag=1">here</a>.
<pre class="brush: js;first-line: 1; highlight:[7,8,9,10,11,12,13,14]">
// elemental function for 3d
function a3d_parallel (indices, frame, w, h, dist) {
var i = indices[0];
var j = indices[1];
var k = j - dist;
if(k < 0) k = j;
var r_l = frame[i][j][0];
var g_l = frame[i][j][1];
var b_l = frame[i][j][2];
var r_r = frame[i][k][0];
var g_r = frame[i][k][1];
var b_r = frame[i][k][2];
var left = dubois_blend_left(r_l, g_l, b_l);
var right = dubois_blend_right(r_r, g_r, b_r);
}
</pre>
Now we have the separately masked and blended left and right eye pixels. We now
blend these two pixels togther to produce the final color values.
<pre class="brush: js;first-line: 1; highlight:[15,16,17,18]">
// elemental function for 3d
function a3d_parallel (indices, frame, w, h, dist) {
var i = indices[0];
var j = indices[1];
var k = j - dist;
if(k < 0) k = j;
var r_l = frame[i][j][0];
var g_l = frame[i][j][1];
var b_l = frame[i][j][2];
var r_r = frame[i][k][0];
var g_r = frame[i][k][1];
var b_r = frame[i][k][2];
var left = dubois_blend_left(r_l, g_l, b_l);
var right = dubois_blend_right(r_r, g_r, b_r);
var rb = left[0] + right[0] + 0.5;
var gb = left[1] + right[1] + 0.5;
var bb = left[2] + right[2] + 0.5;
return [rb, gb, bb, 255];
}
</pre>
And thats it. Select "RiverTrail" execution, click play and select the
3D filter. Put on Red-Cyan 3D glasses and you should be able to notice
the depth effect. Without the glasses this is how it looks (original
video frame on the left, with 3D on the right):
<img src="images/se1.png" height="170"/>
<img src="images/3d1.png" height="170"/>
<h2><a name="edge"></a> Edge Detection and Sharpening</h2>
Let's move on to something a little more complicated - <a
href="http://en.wikipedia.org/wiki/Edge_detection">edge
detection</a> and <a
href="http://en.wikipedia.org/wiki/Edge_enhancement">sharpening</a>.
Edge detection is a common tool used in digital image processing and
computer vision that seeks to highlight points in the image where the
image brightness changes sharply. Select the edge detection effect and
click play to look at the result of the effect.
<img src="images/se1.png" height="170"/>
<img src="images/ed1.png" height="170"/>
There are many diverse approaches to edge detection but we are
interested in the most popular 2D discrete <a
href="http://en.wikipedia.org/wiki/Convolution">convolution</a>
based approach.
<img src="images/convolution2.png" height="200" style="margin:auto;display:block;"/>
At a high-level, discrete convolution on a single pixel in an image
involves taking this pixel (shown in dark blue above) and computing the
weighted sum of its neighbors that lie within some specific window to produce the output pixel (shown in dark
red above). The weights and the window are described by the convolution
<em>kernel</em>. This process is repeated for all the pixels to produce
the final output of the convolution.
<br><br>
Consider a 5x5 matrix convolved with a 3x3 kernel as shown below. For
simplicity, we are only interested in the input element highlighted in blue.
<img src="images/convolution4.png" height="150" style="margin:auto;display:block;"/>
The weighted sum for this element is:<br>
(1*2) + (1*3) + (2*0) + <br>
(2*0) + (2*1) + (1*3) + <br>
(1*3) + (5*0) + (0*3) + <br>
= 13. The value of this element in the output matrix is therefore
13.<br>
You can take a look at the sequential implementation of edge detection in
<code>edge_detect_sequential</code> in filters.js. Don't worry about
understanding it in detail yet.
<!--
<pre class="brush: js;first-line: 1405">
function edge_detect_sequential(frame, len, w, h, ctx) {
var pix = frame.data
var ekernel = [[1,1,1,1,1], [1,2,2,2,1], [1,2,-32,2,1], [1,2,2,2,1], [1,1,1,1,1]];
var new_pix = new Array(len);
var kernel_width = (kernel.length-1)/2; // how many elements in each direction
var neighbor_sum = [0, 0, 0, 255];
var weight;
for(var n = 0; n < len; n = n + 4) {
neighbor_sum[0] = 0;
neighbor_sum[1] = 0;
neighbor_sum[2] = 0;
for(var i = -1*kernel_width; i <= kernel_width; i++) {
for(var j = -1*kernel_width; j <= kernel_width; j++) {
var offset = n+(i*4*w)+(j*4);
if(offset < 0 || offset > len-4) offset = 0;
weight = kernel[i+kernel_width][j+kernel_width];
neighbor_sum[0] += pix[offset] * weight;
neighbor_sum[1] += pix[offset+1] * weight;
neighbor_sum[2] += pix[offset+2] * weight;
}
}
new_pix[n] = neighbor_sum[0];
new_pix[n+1] = neighbor_sum[1];
new_pix[n+2] = neighbor_sum[2];
new_pix[n+3] = pix[n+3];
}
for(var n = 0 ; n < len; n++) {
var val = new_pix[n];
if(val < 0) val = 0;
if(val > 255) val = 255;
pix[n] = val;
}
ctx.putImageData(frame, 0, 0);
}
</pre>
-->
Let us try and implement this using RiverTrail. Make a function called
<code>edge_detect_parallel</code> in filters.js.
<pre class="brush: js;highlight: [1,2,3,4,5,6,7]">
function edge_detect_parallel(index, frame, w, h) {
var m = index[0];
var n = index[1];
var ekernel = [[1,1,1,1,1], [1,2,2,2,1], [1,2,-32,2,1], [1,2,2,2,1], [1,1,1,1,1]];
var kernel_width = (ekernel.length-1)/2; // will be '2' for this kernel
var neighbor_sum = [0, 0, 0, 255];
}
</pre>
The first two lines of the body are the same as the beginning of the
parallel sepia implementation. (m, n) is now the position of a pixel in
the input ParallelArray <code>frame</code>. The variable
<code>ekernel</code> is the 5x5 kernel we will be using for
convolution (you can copy this over from the sequential version). And
we also need a 4 element array <code>neighbor_sum</code> to hold the weighted sum.
<br><br>
At this point we have an input frame (<code>frame</code>) and a
specific pixel <code>(m, n)</code> which we will call the "input pixel". Now we need to define a "window" of
neighboring pixels such that this window is centered at this input
pixel. We can define such a window by using a nested loop as follows:
<pre class="brush: js;highlight: [7,8,9,10,11]">
function edge_detect_parallel(index, frame, w, h) {
var m = index[0];
var n = index[1];
var ekernel = [[1,1,1,1,1], [1,2,2,2,1], [1,2,-32,2,1], [1,2,2,2,1], [1,1,1,1,1]];
var kernel_width = (ekernel.length-1)/2; // will be '2' for this kernel
var neighbor_sum = [0, 0, 0, 255];
for(var i = -1*kernel_width; i <= kernel_width; i++) {
for(var j = -1*kernel_width; j <= kernel_width; j++) {
var x = m+i; var y = n+j;
}
}
}
</pre>
And there. Now we have an iteration space <code>(x, y)</code> that goes
from [m-2, n-2] to [m+2, n+2] which is precisely the set of neighboring
pixels we want to add up. That is, frame[x][y] is a pixel in within the
neighbor window. So lets add them up with the weights from
<code>ekernel</code>:
<pre class="brush: js;highlight: [7,11,12,13,14]">
function edge_detect_parallel(index, frame, w, h) {
var m = index[0];
var n = index[1];
var ekernel = [[1,1,1,1,1], [1,2,2,2,1], [1,2,-32,2,1], [1,2,2,2,1], [1,1,1,1,1]];
var kernel_width = (ekernel.length-1)/2; // will be '2' for this kernel
var neighbor_sum = [0, 0, 0, 255];
var weight;
for(var i = -1*kernel_width; i <= kernel_width; i++) {
for(var j = -1*kernel_width; j <= kernel_width; j++) {
var x = m+i; var y = n+j;
weight = ekernel[i+kernel_width][j+kernel_width];
neighbor_sum[0] += frame[x][y][0] * weight;
neighbor_sum[1] += frame[x][y][1] * weight;
neighbor_sum[2] += frame[x][y][2] * weight;
}
}
}
</pre>
There is a detail we have ignored so far. What do we do with pixels on
the borders of the image for whom the neighbor window goes out of the
image ? There are several approaches to handle this situation - we
could pad the original ParallelArray on all 4 sides so that the
neighbor window is guaranteed to never go out of bounds. Another
approach is to wrap around the image. For simplicity, we will simply
clamp the neighbor window to the borders of the image.
<pre class="brush: js;first-line:10;highlight: [11,12]">
var x = m+i; var y = n+j;
if(x < 0) x = 0; if(x > h-1) x = h-1;
if(y < 0) y = 0; if(y > w-1) y = w-1;
weight = ekernel[i+kernel_width][j+kernel_width];
</pre>
After the loops are done, we have our weighted sum for each color in
neighbor_sum which we return.
<pre class="brush: js;highlight: [19]">
function edge_detect_parallel(index, frame, w, h) {
var m = index[0];
var n = index[1];
var ekernel = [[1,1,1,1,1], [1,2,2,2,1], [1,2,-32,2,1], [1,2,2,2,1], [1,1,1,1,1]];
var kernel_width = (ekernel.length-1)/2; // will be '2' for this kernel
var neighbor_sum = [0, 0, 0, 255];
var weight;
for(var i = -1*kernel_width; i <= kernel_width; i++) {
for(var j = -1*kernel_width; j <= kernel_width; j++) {
var x = m+i; var y = n+j;
if(x < 0) x = 0; if(x > h-1) x = h-1;
if(y < 0) y = 0; if(y > w-1) y = w-1;
weight = ekernel[i+kernel_width][j+kernel_width];
neighbor_sum[0] += frame[x][y][0] * weight;
neighbor_sum[1] += frame[x][y][1] * weight;
neighbor_sum[2] += frame[x][y][2] * weight;
}
}
return neighbor_sum;
}
</pre>
<!--
For a particular
pixel we need to grab a pixel that is some distance to the right along the
x-axis if we imagine the origin to be at the top-left of the frame. This distance
is given to us by the <code>dist</code> argument which is updated
everytime the 3D slider on the UI is moved. But if this distance is
larger than the x-position,
-->
<!--<h2><a name="face"></a> Color-based Face Detection</h2>-->
<!--
One instance of this function produces the color value for
one pixel in the input ParallelArray. The first step is to
-->
<!--
Next, lets create a 4 element array to hold the weighted sum.
<pre class="brush: js;first-line: 1;highlight: 5">
function edge_detect_parallel(index, frame, w, h) {
var m = index[0];
var n = index[1];
var ekernel = [[1,1,1,1,1], [1,2,2,2,1], [1,2,-32,2,1], [1,2,2,2,1], [1,1,1,1,1]];
}
</pre>
-->
</section>
</div>
<!-- FOOTER -->
<div id="footer_wrap" class="outer">
<footer class="inner">
<p>© 2012 Jaswanth Sreeram. Published with <a href="http://pages.github.com">GitHub Pages</a></p>
</footer>
</div>
</body>
</html>