Wednesday, August 18, 2010

QComicBook can detect comic frames now!

'Frame view' option.
The latest QComicBook code available in the git repository (dev/framedect branch) brings support for comic book frames detection - the new 'Frame View' mode allows for reading comic book frame-by-frame! I'm pretty excited about this new feature because this is something I dreamed about and started investigating several months ago. Comic frames extraction requires very smart image processing algorithms and some CPU power; a few articles are available on this subject on the internet. The most interesting ideas come from Japanese (e.g. 'Layout Analysis of Tree-Structured Scene Frames in Comic Images' article by Takamasa Tanaka, Kenji Shoji, Fubito Toyama and Juichi Miyamichi; 'Automatic E-Comic Content Adaptation' by Kohei Arai and Herman Tolle) as comic frame extraction solutions have already been implemented by online comic-book providers in Japan.
'Frame view' mode displaying single comic book frame.
The solution implemented in QComicBook is based on the 'Automatic E-Comic Content Adaptation' article and it's core is a contour-tracing algorithm described in 'A Linear-Time Component-Labeling Algorithm Using Contour Tracing Technique' article by Fu Chang, Chun-Jen Chen and Chi-Jen Lu from Taiwan. The main idea of this algorithm is to analyze a binarized image (black-white pixels only, with threshold applied) and find image frames (blobs) using contour-tracing. The algorithm is very fast and accurate (over 90% success rate). The accuracy of frame extraction implemented in QComicBook depends on the complexity of comic book images; it works best for pages with solid background (e.g. white or black), rectangular comic frames and simple frame layouts.  When it comes to performance, current implementation allows for comfortable comic book reading with a 2GHz Core2 Duo CPU. As frames for next page are extracted in advance for next page in a separate thread, it should also work nicely on slower CPUs.
Nothing is perfect, though. As already noted, the accuracy depends on the complexity of comic book page layout. Other than that, current implementation doesn't detect overlapping frames (e.g. a comic baloon spanning two frames), as described in the 'Automatic E-Comic...' article; overlapping frames are detected as a single frame. I'm going to implement this later.
Having said that, current implementation of comic frames extraction in QComicBook is already in good shape and  I'm happy that QComicBook is the first open-source comic book viewer to bring such feature :). Thanks to the aforementioned guys whose articles provided invaluable help when implementing this feature!
Frame view detection will soon be added to the master branch of the QComicBook source code repository, and then will be made available in the upcoming version 0.7.0 (to be released in a few weeks).
Stay tuned!