Recherche avancée

Sur d’autres sites (6509)

• Re-solving My Search Engine Problem

  28 juillet 2012, par Multimedia Mike — General, swish-e

  14 years ago, I created a web database of 8-bit Nintendo Entertainment System games. To make it useful, I developed a very primitive search feature.

  A few months ago, I decided to create a web database of video game music. To make it useful, I knew it would need to have a search feature. I realized I needed to solve the exact same problem again.

  Requirements
  The last time I solved this problem, I came up with an excruciatingly naïve idea. Hey, it worked. I really didn’t want to deploy the same solution again because it felt so silly the first time. Surely there are many better ways to solve it now ? Many different workable software solutions that do all the hard work for me ?

  The first time I attacked this, it was 1998 and hosting resources were scarce. On my primary web host I was able to put static HTML pages, perhaps with server side includes. The web host also offered dynamic scripting capabilities via something called htmlscript (a.k.a. MIVA Script). I had a secondary web host in my ISP which allowed me to host conventional CGI scripts on a Unix host, so that’s where I hosted the search function (Perl CGI script accessing a key/value data store file).

  Nowadays, sky’s the limit. Any type of technology you want to deploy should be tractable. Still, a key requirement was that I didn’t want to pay for additional hosting resources for this silly little side project. That leaves me with options that my current shared web hosting plan allows, which includes such advanced features as PHP, Perl and Python scripts. I can also access MySQL.

  Candidates
  There are a lot of mature software packages out there which can index and search data and be plugged into a website. But a lot of them would be unworkable on my web hosting plan due to language or library package limitations. Further, a lot of them feel like overkill. At the most basic level, all I really want to do is map a series of video game titles to URLs in a website.

  Based on my research, Lucene seems to hold a fair amount of mindshare as an open source indexing and search solution. But I was unsure of my ability to run it on my hosting plan. I think MySQL does some kind of full text search, so I could have probably made a solution around that. Again, it just feels like way more power than I need for this project.

  I used Swish-e once about 3 years ago for a little project. I wasn’t confident of my ability to run that on my server either. It has a Perl API but it requires custom modules.

  My quest for a search solution grew deep enough that I started perusing a textbook on information retrieval techniques in preparation for possibly writing my own solution from scratch. However, in doing so, I figured out how I might subvert an existing solution to do what I want.

  Back to Swish-e
  Again, all I wanted to do was pull data out of a database and map that data to a URL in a website. Reading the Swish-e documentation, I learned that the software supports a mode specifically tailored for this. Rather than asking Swish-e to index a series of document files living on disk, you can specify a script for Swish-e to run and the script will generate what appears to be a set of phantom documents for Swish-e to index.
  

  When I ’add’ a game music file to the game music website, I have a scripts that scrape the metadata (game title, system, song titles, composers, company, copyright, the original file name on disk, even the ripper/dumper who extracted the chiptune in the first place) and store it all in an SQLite database. When it’s time to update the database, another script systematically generates a series of pseudo-documents that spell out the metadata for each game and prefix each document with a path name. Searching for a term in the index returns a lists of paths that contain the search term. Thus, it makes sense for that path to be a site URL.

  But what about a web script which can search this Swish-e index ? That’s when I noticed Swish-e’s C API and came up with a crazy idea : Write the CGI script directly in C. It feels like sheer madness (or at least the height of software insecurity) to write a CGI script directly in C in this day and age. But it works (with the help of cgic for input processing), just as long as I statically link the search script with libswish-e.a (and libz.a). The web host is an x86 machine, after all.

  I’m not proud of what I did here— I’m proud of how little I had to do here. The searching CGI script is all of about 30 lines of C code. The one annoyance I experienced while writing it is that I had to consult the Swish-e source code to learn how to get my search results (the "swishdocpath" key — or any other key — for SwishResultPropertyStr() is not documented). Also, the C program just does the simplest job possible, only querying the term in the index and returning the results in plaintext, in order of relevance, to the client-side JavaScript code which requested them. JavaScript gets the job of sorting and grouping the results for presentation.

  Tuning the Search
  Almost immediately, I noticed that the search engine could not find one of my favorite SNES games, U.N. Squadron. That’s because all of its associated metadata names Area 88, the game’s original title. Thus, I had to modify the metadata database to allow attaching somewhat free-form tags to games in order to compensate. In this case, an alias title would show up in the game’s pseudo-document.

  Roman numerals are still a thorn in my side, just as they were 14 years ago in my original iteration. I dealt with it back then by converting all numbers to Roman numerals during the index and searching processes. I’m not willing to do that for this case and I’m still looking for a good solution.

  Another annoying problem deals with Mega Man, a popular franchise. The proper spelling is 2 words but it’s common for people to mash it into one word, Megaman (see also : Spider-Man, Spiderman, Spider Man). The index doesn’t gracefully deal with that and I have some hacks in place to cope for the time being.

  Positive Results
  I’m pleased with the results so far, and so are the users I have heard from. I know one user expressed amazement that a search for Castlevania turned up Akumajou Densetsu, the Japanese version of Castlevania III : Dracula’s Curse. This didn’t surprise me because I manually added a hint for that mapping. (BTW, if you are a fan of Castlevania III, definitely check out the Akumajou Densetsu soundtrack which has an upgraded version of the same soundtrack using special audio channels.)

  I was a little more surprised when a user announced that searching for ’probotector’ correctly turned up Contra : Hard Corps. I looked into why this was. It turns out that the original chiptune filename was extremely descriptive : "Contra - Hard Corps [Probotector] (1994-08-08)(Konami)". The filenames themselves often carry a bunch of useful metadata which is why it’s important to index those as well.

  And of course, many rippers, dumpers, and taggers have labored for over a decade to lovingly tag these songs with as much composer information as possible, which all gets indexed. The search engine gets a lot of compliments for its ability to find many songs written by favorite composers.

• Open Media Developers Track at OVC 2011

  11 octobre 2011, par silvia

  The Open Video Conference that took place on 10-12 September was so overwhelming, I’ve still not been able to catch my breath ! It was a dense three days for me, even though I only focused on the technology sessions of the conference and utterly missed out on all the policy and content discussions.

  Roughly 60 people participated in the Open Media Software (OMS) developers track. This was an amazing group of people capable and willing to shape the future of video technology on the Web :

  • HTML5 video developers from Apple, Google, Opera, and Mozilla (though we missed the NZ folks),
  • codec developers from WebM, Xiph, and MPEG,
  • Web video developers from YouTube, JWPlayer, Kaltura, VideoJS, PopcornJS, etc.,
  • content publishers from Wikipedia, Internet Archive, YouTube, Netflix, etc.,
  • open source tool developers from FFmpeg, gstreamer, flumotion, VideoLAN, PiTiVi, etc,
  • and many more.

  To provide a summary of all the discussions would be impossible, so I just want to share the key take-aways that I had from the main sessions.

  WebRTC : Realtime Communications and HTML5

  Tim Terriberry (Mozilla), Serge Lachapelle (Google) and Ethan Hugg (CISCO) moderated this session together (slides). There are activities both at the W3C and at IETF – the ones at IETF are supposed to focus on protocols, while the W3C ones on HTML5 extensions.

  The current proposal of a PeerConnection API has been implemented in WebKit/Chrome as open source. It is expected that Firefox will have an add-on by Q1 next year. It enables video conferencing, including media capture, media encoding, signal processing (echo cancellation etc), secure transmission, and a data stream exchange.

  Current discussions are around the signalling protocol and whether SIP needs to be required by the standard. Further, the codec question is under discussion with a question whether to mandate VP8 and Opus, since transcoding gateways are not desirable. Another question is how to measure the quality of the connection and how to report errors so as to allow adaptation.

  What always amazes me around RTC is the sheer number of specialised protocols that seem to be required to implement this. WebRTC does not disappoint : in fact, the question was asked whether there could be a lighter alternative than to re-use dozens of years of protocol development – is it over-engineered ? Can desktop players connect to a WebRTC session ?

  We are already in a second or third revision of this part of the HTML5 specification and yet it seems the requirements are still being collected. I’m quietly confident that everything is done to make the lives of the Web developer easier, but it sure looks like a huge task.

  The Missing Link : Flash to HTML5

  Zohar Babin (Kaltura) and myself moderated this session and I must admit that this session was the biggest eye-opener for me amongst all the sessions. There was a large number of Flash developers present in the room and that was great, because sometimes we just don’t listen enough to lessons learnt in the past.

  This session gave me one of those aha-moments : it the form of the Flash appendBytes() API function.

  The appendBytes() function allows a Flash developer to take a byteArray out of a connected video resource and do something with it – such as feed it to a video for display. When I heard that Web developers want that functionality for JavaScript and the video element, too, I instinctively rejected the idea wondering why on earth would a Web developer want to touch encoded video bytes – why not leave that to the browser.

  But as it turns out, this is actually a really powerful enabler of functionality. For example, you can use it to :

  • display mid-roll video ads as part of the same video element,
  • sequence playlists of videos into the same video element,
  • implement DVR functionality (high-speed seeking),
  • do mash-ups,
  • do video editing,
  • adaptive streaming.

  This totally blew my mind and I am now completely supportive of having such a function in HTML5. Together with media fragment URIs you could even leave all the header download management for resources to the Web browser and just request time ranges from a video through an appendBytes() function. This would be easier on the Web developer than having to deal with byte ranges and making sure that appropriate decoding pipelines are set up.

  Standards for Video Accessibility

  Philip Jagenstedt (Opera) and myself moderated this session. We focused on the HTML5 track element and the WebVTT file format. Many issues were identified that will still require work.

  One particular topic was to find a standard means of rendering the UI for caption, subtitle, und description selection. For example, what icons should be used to indicate that subtitles or captions are available. While this is not part of the HTML5 specification, it’s still important to get this right across browsers since otherwise users will get confused with diverging interfaces.

  Chaptering was discussed and a particular need to allow URLs to directly point at chapters was expressed. I suggested the use of named Media Fragment URLs.

  The use of WebVTT for descriptions for the blind was also discussed. A suggestion was made to use the voice tag <v> to allow for “styling” (i.e. selection) of the screen reader voice.

  Finally, multitrack audio or video resources were also discussed and the @mediagroup attribute was explained. A question about how to identify the language used in different alternative dubs was asked. This is an issue because @srclang is not on audio or video, only on text, so it’s a missing feature for the multitrack API.

  Beyond this session, there was also a breakout session on WebVTT and the track element. As a consequence, a number of bugs were registered in the W3C bug tracker.

  WebM : Testing, Metrics and New features

  This session was moderated by John Luther and John Koleszar, both of the WebM Project. They started off with a presentation on current work on WebM, which includes quality testing and improvements, and encoder speed improvement. Then they moved on to questions about how to involve the community more.

  The community criticised that communication of what is happening around WebM is very scarce. More sharing of information was requested, including a move to using open Google+ hangouts instead of Google internal video conferences. More use of the public bug tracker can also help include the community better.

  Another pain point of the community was that code is introduced and removed without much feedback. It was requested to introduce a peer review process. Also it was requested that example code snippets are published when new features are announced so others can replicate the claims.

  This all indicates to me that the WebM project is increasingly more open, but that there is still a lot to learn.

  Standards for HTTP Adaptive Streaming

  This session was moderated by Frank Galligan and Aaron Colwell (Google), and Mark Watson (Netflix).

  Mark started off by giving us an introduction to MPEG DASH, the MPEG file format for HTTP adaptive streaming. MPEG has just finalized the format and he was able to show us some examples. DASH is XML-based and thus rather verbose. It is covering all eventualities of what parameters could be switched during transmissions, which makes it very broad. These include trick modes e.g. for fast forwarding, 3D, multi-view and multitrack content.

  MPEG have defined profiles – one for live streaming which requires chunking of the files on the server, and one for on-demand which requires keyframe alignment of the files. There are clear specifications for how to do these with MPEG. Such profiles would need to be created for WebM and Ogg Theora, too, to make DASH universally applicable.

  Further, the Web case needs a more restrictive adaptation approach, since the video element’s API is already accounting for some of the features that DASH provides for desktop applications. So, a Web-specific profile of DASH would be required.

  Then Aaron introduced us to the MediaSource API and in particular the webkitSourceAppend() extension that he has been experimenting with. It is essentially an implementation of the appendBytes() function of Flash, which the Web developers had been asking for just a few sessions earlier. This was likely the biggest announcement of OVC, alas a quiet and technically-focused one.

  Aaron explained that he had been trying to find a way to implement HTTP adaptive streaming into WebKit in a way in which it could be standardised. While doing so, he also came across other requirements around such chunked video handling, in particular around dynamic ad insertion, live streaming, DVR functionality (fast forward), constraint video editing, and mashups. While trying to sort out all these requirements, it became clear that it would be very difficult to implement strategies for stream switching, buffering and delivery of video chunks into the browser when so many different and likely contradictory requirements exist. Also, once an approach is implemented and specified for the browser, it becomes very difficult to innovate on it.

  Instead, the easiest way to solve it right now and learn about what would be necessary to implement into the browser would be to actually allow Web developers to queue up a chunk of encoded video into a video element for decoding and display. Thus, the webkitSourceAppend() function was born (specification).

  The proposed extension to the HTMLMediaElement is as follows :

  partial interface HTMLMediaElement 
    // URL passed to src attribute to enable the media source logic.
    readonly attribute [URL] DOMString webkitMediaSourceURL ;
    bool webkitSourceAppend(in Uint8Array data) ;
    // end of stream status codes.
  
    const unsigned short EOS_NO_ERROR = 0 ;
  
    const unsigned short EOS_NETWORK_ERR = 1 ;
  
    const unsigned short EOS_DECODE_ERR = 2 ;
    void webkitSourceEndOfStream(in unsigned short status) ;
    // states
  
    const unsigned short SOURCE_CLOSED = 0 ;
  
    const unsigned short SOURCE_OPEN = 1 ;
  
    const unsigned short SOURCE_ENDED = 2 ;
    readonly attribute unsigned short webkitSourceState ;
  
   ;
  

  The code is already checked into WebKit, but commented out behind a command-line compiler flag.

  Frank then stepped forward to show how webkitSourceAppend() can be used to implement HTTP adaptive streaming. His example uses WebM – there are no examples with MPEG or Ogg yet.

  The chunks that Frank’s demo used were 150 video frames long (6.25s) and 5s long audio. Stream switching only switched video, since audio data is much lower bandwidth and more important to retain at high quality. Switching was done on multiplexed files.

  Every chunk requires an XHR range request – this could be optimised if the connections were kept open per adaptation. Seeking works, too, but since decoding requires download of a whole chunk, seeking latency is determined by the time it takes to download and decode that chunk.

  Similar to DASH, when using this approach for live streaming, the server has to produce one file per chunk, since byte range requests are not possible on a continuously growing file.

  Frank did not use DASH as the manifest format for his HTTP adaptive streaming demo, but instead used a hacked-up custom XML format. It would be possible to use JSON or any other format, too.

  After this session, I was actually completely blown away by the possibilities that such a simple API extension allows. If I wasn’t sold on the idea of a appendBytes() function in the earlier session, this one completely changed my mind. While I still believe we need to standardise a HTTP adaptive streaming file format that all browsers will support for all codecs, and I still believe that a native implementation for support of such a file format is necessary, I also believe that this approach of webkitSourceAppend() is what HTML needs – and maybe it needs it faster than native HTTP adaptive streaming support.

  Standards for Browser Video Playback Metrics

  This session was moderated by Zachary Ozer and Pablo Schklowsky (JWPlayer). Their motivation for the topic was, in fact, also HTTP adaptive streaming. Once you leave the decisions about when to do stream switching to JavaScript (through a function such a wekitSourceAppend()), you have to expose stream metrics to the JS developer so they can make informed decisions. The other use cases is, of course, monitoring of the quality of video delivery for reporting to the provider, who may then decide to change their delivery environment.

  The discussion found that we really care about metrics on three different levels :

  • measuring the network performance (bandwidth)
  • measuring the decoding pipeline performance
  • measuring the display quality

  In the end, it seemed that work previously done by Steve Lacey on a proposal for video metrics was generally acceptable, except for the playbackJitter metric, which may be too aggregate to mean much.

  Device Inputs / A/V in the Browser

  I didn’t actually attend this session held by Anant Narayanan (Mozilla), but from what I heard, the discussion focused on how to manage permission of access to video camera, microphone and screen, e.g. when multiple applications (tabs) want access or when the same site wants access in a different session. This may apply to real-time communication with screen sharing, but also to photo sharing, video upload, or canvas access to devices e.g. for time lapse photography.

  Open Video Editors

  This was another session that I wasn’t able to attend, but I believe the creation of good open source video editing software and similar video creation software is really crucial to giving video a broader user appeal.

  Jeff Fortin (PiTiVi) moderated this session and I was fascinated to later see his analysis of the lifecycle of open source video editors. It is shocking to see how many people/projects have tried to create an open source video editor and how many have stopped their project. It is likely that the creation of a video editor is such a complex challenge that it requires a larger and more committed open source project – single people will just run out of steam too quickly. This may be comparable to the creation of a Web browser (see the size of the Mozilla project) or a text processing system (see the size of the OpenOffice project).

  Jeff also mentioned the need to create open video editor standards around playlist file formats etc. Possibly the Open Video Alliance could help. In any case, something has to be done in this space – maybe this would be a good topic to focus next year’s OVC on ?

  Monday’s Breakout Groups

  The conference ended officially on Sunday night, but we had a third day of discussions / hackday at the wonderful New York Lawschool venue. We had collected issues of interest during the two previous days and organised the breakout groups on the morning (Schedule).

  In the Content Protection/DRM session, Mark Watson from Netflix explained how their API works and that they believe that all we need in browsers is a secure way to exchange keys and an indicator of protection scheme is used – the actual protection scheme would not be implemented by the browser, but be provided by the underlying system (media framework/operating system). I think that until somebody actually implements something in a browser fork and shows how this can be done, we won’t have much progress. In my understanding, we may also need to disable part of the video API for encrypted content, because otherwise you can always e.g. grab frames from the video element into canvas and save them from there.

  In the Playlists and Gapless Playback session, there was massive brainstorming about what new cool things can be done with the video element in browsers if playback between snippets can be made seamless. Further discussions were about a standard playlist file formats (such as XSPF, MRSS or M3U), media fragment URIs in playlists for mashups, and the need to expose track metadata for HTML5 media elements.

  What more can I say ? It was an amazing three days and the complexity of problems that we’re dealing with is a tribute to how far HTML5 and open video has already come and exciting news for the kind of applications that will be possible (both professional and community) once we’ve solved the problems of today. It will be exciting to see what progress we will have made by next year’s conference.

  Thanks go to Google for sponsoring my trip to OVC.

  UPDATE : We actually have a mailing list for open media developers who are interested in these and similar topics – do join at http://lists.annodex.net/cgi-bin/mailman/listinfo/foms.

• RoQ on Dreamcast

  18 mars 2011, par Multimedia Mike — Sega Dreamcast

  I have been working on that challenge to play back video on the Sega Dreamcast. To review, I asserted that the RoQ format would be a good fit for the Sega Dreamcast hardware. The goal was to play 640x480 video at 30 frames/second. Short version : I have determined that it is possible to decode such video in real time. However, I ran into certain data rate caveats.

  First off : Have you ever wondered if the Dreamcast can read an 80mm optical disc ? It can ! I discovered this when I only had 60 MB of RoQ samples to burn on a disc and a spindle full of these 210MB-capacity 80mm CD-Rs that I never have occasion to use.

  
  
  

  New RoQ Library
  There are open source RoQ decoders out there but I decided to write a new one. A few reasons : 1) RoQ is so simple that I didn’t think it would take too long ; 2) it would be nice to have a RoQ library that is license-compatible (BSD-like) with the rest of the KallistiOS distribution ; 3) the idroq.tar.gz distribution, while license-compatible, has enough issues that I didn’t want to correct it.

  Thankfully, I was correct about the task not being too difficult : I put together a new RoQ decoder in short order. I’m a bit embarrassed to admit that the part I had the most trouble with was properly converting YUV -> RGB.
  
  About the approach I took : While the original idroq.tar.gz decoder maintains YUV 4:2:0 codebooks (which led to chroma bugs during motion compensation) and FFmpeg’s decoder maintains YUV 4:4:4 codebooks, this decoder is built to convert the YUV 4:2:0 vectors into RGB565 vectors during the vector unpacking phase. Thus, the entire frame is rendered in RGB565 — no lengthy YUV -> RGB conversion after decoding — and all pixels are shuffled around as 16-bit units (minor speedup vs. shuffling everything as bytes).

  I also entertained the idea of maintaining YUYV codebooks (since the DC supports that colorspace as a texture format). But I scrapped that idea when I remembered it would lead to the same chroma bleeding problem seen in the original idroq.tar.gz decoder.

  Onto The Dreamcast
  I developed the library on a Linux computer, allowing it to output a series of PNM files for visual verification and debugging. Dropping it into a basic DC/KOS-compatible program was trivial and the first order of business was profiling.

  At first, I profiled the entire decode operation : open file, then read and decode each chunk while tossing away the results. I was roundly disappointed to see that, e.g., an 8.5-second RoQ sample needed a little more than 20 seconds to complete. Not real time. I performed a series of optimizations on the decoding library that netted notable performance gains when profiling on Linux. When I brought these same optimizations over to the DC, decoding time didn’t improve at all. This was my first suspicion that perhaps my assumptions regarding the DC’s optical drive’s data rate were not correct.

  Dreamcast Data Rate Profiling
  Let’s start with some definitions : In terms of data rate, an ’X’, i.e., 1X is the minimum data rate needed to read CD quality audio from a disc. At that speed, a drive should be able to stream 75 sectors each second. When reading mode 1/form 1 CD-ROM data, each sector has 2048 bytes (2 kbytes), so a single-speed data rate should achieve 150 kbytes/sec.

  The Dreamcast is supposed to possess a 12X optical drive. This would imply a maximum data rate of 150 kbytes/sec * 12 = 1800 kbytes/sec.

  Rigging up a trivial experiment using the RoQ samples burned on a few different CD-R discs, the best data rate I can see is about 500-525 kbytes/sec, or around 3.5X.

  Where’s the discrepancy ? My first theory has to do with the fact that not all optical media is created equal. This is why optical drives often advertise a slew of numbers which refer to the best theoretical speed for reading a CD vs. writing a CD-R vs. writing a CD-RW, etc. Perhaps the DC drive can’t read CD-Rs very quickly. To test this theory, I tried streaming a large file from a conventionally mastered CD-ROM. This worked well for the closest CD-ROM I had on hand : I was able to stream data at a rate that works out to about 6.5X.

  I smell a science project for another evening : Profiling read speeds from a mastered CD-ROM, burned CD-R, and also a mastered GD-ROM, on each of the 3 Dreamcast consoles I possess (I’ve heard that there’s variance between optical drives depending on manufacturing run).

  The Good News
  I added a little finer-grained code to profile just the video decoding functions. The good news is that the decoder meets my real time goals : That 8.5-second RoQ sample encoded at 640x480x30fps makes its way through the video decoding functions on the DC in a little less than 5 seconds. If the optical drive can supply the data fast enough, the video decoder can take care of the rest.

  The RoQ encoder included with FFmpeg does not honor any bitrate parameters. Instead, I encoded the same file at 320x240. It reportedly decoded in real time and can be streamed in real time as well.

  I say "reportedly" because I’m simply working from textual output at this point ; the next phase is to hook the decoder up to the display hardware.