PaperlayerView exact revision on arXiv

Source-linked AI summary

Sketch-based Manga Retrieval using Manga109 Dataset

Yusuke Matsui, Kota Ito, Yuji Aramaki, Toshihiko Yamasaki, Kiyoharu Aizawa

arXiv:1510.04389v1cs.CVcs.IRcs.MM

TL;DR

Manga retrieval requires a more natural query modality and must handle complex pages containing multiple visual scenes. This paper combines manga-specific image description, sketch-based interaction, and the Manga109 dataset, with experiments verifying higher retrieval accuracy, localization, and useful sketch querying.

  • Problem

    Manga retrieval faces a query modality problem because edge-based features do not provide textual or tag information, motivating sketch-based queries.

  • Method

    The system labels margin areas, describes them with edge orientation histograms, searches approximately using product quantization, and interactively reranks results through relevance feedback and query retouch.

  • Results

    Experiments verified higher retrieval accuracy than existing methods, object-instance localization with reasonable runtime and accuracy, and useful sketch querying for manga search.

  • Takeaways & Limitations

    Manga109 provides 21,142 pages from 109 comic books by professional artists and is publicly available for academic use.

Abstract

from arXiv · show

Manga (Japanese comics) are popular worldwide. However, current e-manga archives offer very limited search support, including keyword-based search by title or author, or tag-based categorization. To make the manga search experience more intuitive, efficient, and enjoyable, we propose a content-based manga retrieval system. First, we propose a manga-specific image-describing framework. It consists of efficient margin labeling, edge orientation histogram feature description, and approximate nearest-neighbor search using product quantization. Second, we propose a sketch-based interface as a natural way to interact with manga content. The interface provides sketch-based querying, relevance feedback, and query retouch. For evaluation, we built a novel dataset of manga images, Manga109, which consists of 109 comic books of 21,142 pages drawn by professional manga artists. To the best of our knowledge, Manga109 is currently the biggest dataset of manga images available for research. We conducted a comparative study, a localization evaluation, and a large-scale qualitative study. From the experiments, we verified that: (1) the retrieval accuracy of the proposed method is higher than those of previous methods; (2) the proposed method can localize an object instance with reasonable runtime and accuracy; and (3) sketch querying is useful for manga search.

I. INTRODUCTION

The paper addresses limited e-manga search by combining content-based image retrieval with sketch interaction and a publicly available large-scale manga dataset. Its system targets manga-specific description, retrieval-localization, and query-modality challenges.

  • Current e-manga archives mainly support title, author, or tag searches, which do not incorporate manga image content.
  • Manga retrieval is challenging because black-and-white line drawings differ from natural images, pages contain multiple frames, and users may need to query specific regions.
  • The proposed image-description framework combines margin-area labeling, edge orientation histogram features, and approximate nearest-neighbor search with product quantization.
  • The sketch-based interface supports sketch querying, relevance feedback, and query retouch, with results retrieved interactively and displayed through thumbnails and page previews.
  • Manga109 contains 109 comic books and 21,142 pages drawn by professional artists, and is publicly available for academic research.
  • 70 ms retrieval is reported for a manga image from 21,142 pages using a notebook PC.
  • The paper extends an earlier conference version with a released dataset, algorithmic improvements using objectness and product quantization, and larger evaluations.

II. RELATED WORK

Related work is organized around image description for content-based retrieval, sketch-specific representations, and retrieval-localization methods. The paper compares its approach with established BoF, Fisher vector, and Compact OCM baselines while noting that deep-learning effectiveness for sketch processing remained insufficiently established.

  • Content-based image retrieval commonly represents queries and dataset images as vectors, with BoF using local features quantized into histograms.
  • BoF extensions include query expansion, soft voting, and Hamming embedding, while VLAD and Fisher vector represent state-of-the-art generalized BoF approaches.
  • Because standard descriptions target natural images, sketch retrieval research introduced oriented-gradient BoF, blank-area filling, and line-segment descriptors.
  • The manga feature-description comparison uses BoF, large-window FV, and Compact OCM as representative BoF- and chamfer-based methods.
  • Deep-learning features are outside this paper’s scope because their effectiveness for sketch processing had not yet been sufficiently discussed, while traditional FV remained competitive in one reported task.

B. Retrieval and localization

The system treats manga retrieval and localization as a unified nearest-neighbor problem over candidate regions, addressing pages composed of multiple visually distinct frames. It uses window-based matching and approximate nearest-neighbor search to scale sketch queries across manga pages.

  • Retrieval and localization: Manga pages contain multiple frames that function as distinct visual scenes, making retrieval and localization harder than ordinary single-image retrieval.Spatial-verification methods designed for natural images are unsuitable because manga pages can be interpreted as sets of images, and BoF performs poorly for manga.
  • Retrieval and localization: The system represents candidate regions with window-based features so a query can retrieve a similar page and identify the matching region.Each feature implicitly contains its position in the page, supporting localization during retrieval.
  • Retrieval and localization: Prior manga retrieval studies used cropped frames or characters, small evaluations, and incompletely discussed runtimes, whereas this system retrieves from 21,142 pages in 70 ms.The reported runtime addresses scalability to a large page collection.
  • Retrieval and localization: The framework preprocesses pages, detects regions of interest, extracts EOH features, compresses them into PQ codes, and retrieves similar regions for a query sketch.The pipeline is designed to address both manga image description and retrieval–localization.
  • Retrieval and localization: Approximate nearest-neighbor search with product quantization makes the window-based search practical despite the large number of extracted features.The approach replaces an impractically slow comparison of all window features with one ANN search.

A. EOH feature description with object windows

The method detects likely object regions with selective search and describes them using edge orientation histograms, producing scale-robust features for matching manga content. Experiments indicate that selective search outperforms the sliding-window baseline on the evaluated dataset, while the EOH representation achieves better retrieval accuracy than previous sketch-based methods.

  • EOH feature description with object windows: Candidate object areas are detected automatically with generic object detectors before EOH features are extracted.The detectors produce bounding boxes likely to contain objects, reducing computation compared with applying processing across a sliding window.
  • EOH feature description with object windows: Selective search achieved the best detection rate among BING, selective search, and the sliding-window baseline on the annotated dataset.The experiment annotated heads of men and evaluated proposal detection using the detection-rate metric.
  • EOH feature description with object windows: EOH divides each square region into c × c cells, quantizes edges into four orientation bins, and produces a vector of dimension 4c^2.The vector is normalized, and all-zero features are discarded.
  • EOH feature description with object windows: Using square patches of different sizes gives same-dimensional EOH features, enabling matching across scale changes.This supports queries such as a character face appearing small or large in different manga regions.
  • EOH feature description with object windows: A page is represented as a set of EOH features extracted from candidate windows, allowing matching areas to be found efficiently.The representation is reported to achieve better accuracy than previous sketch-based retrieval methods.

B. Feature compression by product quantization

Product quantization compresses EOH features by splitting each vector into subvectors and quantizing them with learned subcodebooks. The resulting compact codes reduce matching cost and memory use while supporting efficient approximate distance computation.

  • Feature compression by product quantization: Product quantization compresses EOH features into binary codes for efficient approximate nearest-neighbor matching.Distances between a query vector and dataset codes can be computed with simple lookup operations using asymmetric distance computation.
  • Feature compression by product quantization: PQ represents x ∈ R^D as M subvectors, where each subvector has dimension D/M.Each subvector is quantized independently with a subquantizer.
  • Feature compression by product quantization: Each subquantizer maps a subvector to a codeword from a K-centroid subcodebook learned in advance by k-means.The centroids have dimension D/M.
  • Feature compression by product quantization: The product quantizer concatenates the subquantizer outputs, mapping an input vector to a codeword in the Cartesian product of the subcodebooks.The encoded codeword is represented by a tuple of M subcentroid indices.
  • Feature compression by product quantization: With K=256, M=8 or 16 produces code lengths of 64 or 128 bits, respectively.The code length follows M log2 K bits when K is a power of 2.
  • Feature compression by product quantization: After quantization, each page is represented as the set of PQ codes q(x_i) corresponding to its EOH features.The stored page representation contains one quantized code for each extracted feature.

C. Search

The search engine compares a query sketch’s EOH feature with PQ-encoded manga-page features and selects the nearest match efficiently. This separates feature description from approximate-nearest-neighbor search, allowing large feature collections to be searched effectively.

  • Search: The engine represents each manga page with multiple quantized EOH features and compares them with a query sketch feature.For page p, N_p denotes the number of EOH features; the query feature is y.
  • Search: Approximate Euclidean distance d_AD compares the uncompressed query vector with compressed PQ codes through efficient lookup operations.The distance is computed using ADC lookup operations.
  • Search: The nearest result is the feature-page pair ⟨p*, i*⟩ with the smallest approximate distance.The selected feature is interpreted as the nearest feature to the query sketch.
  • Search: Separating feature description from ANN search enables efficient retrieval even when the number of manga features is very large.The paper gives 16 ms as an example runtime for searching one million 64-bit codes.

D. Skipping margins

The system excludes manga margins before feature extraction and supports iterative sketch interaction with retrieved results. Users can reuse retrieved regions and modify queries through added or erased strokes.

  • D. Skipping margins: Margin labeling thickens lines by eroding white regions, labels white-connected areas, and selects the margin regions.This preprocessing identifies interframe spaces that are not important for retrieval.
  • D. Skipping margins: A feature is extracted only when its margin-area ratio U/S is below the threshold 0.1.Areas dominated by margins are skipped during feature extraction.
  • D. Skipping margins: Sketch querying is used because manga are sketches and EOH features do not contain textual or tag information.The paper presents sketching as a natural interface for manga retrieval.
  • D. Skipping margins: The interface supports sketch querying, relevance feedback, and query retouch as three forms of interaction.Relevance feedback reuses retrieved regions, while query retouch modifies and reuses queries.
  • D. Skipping margins: Selecting a region in a retrieved manga page automatically launches another retrieval using that region as the query.This lets novice users reuse professional manga images as queries.
  • D. Skipping margins: Users can add lines or partially erase them, causing retrieval results to change immediately and repeatedly.The interaction is designed to steer results in the desired direction.

V. MANGA DATASET

Manga109 is a publicly available academic dataset created to support large-scale manga image research despite copyright constraints. It contains professionally drawn manga across many titles, genres, and publication years.

  • V. MANGA DATASET: Manga109 contains 109 manga titles and is publicly available for academic research with proper copyright notation.The dataset was introduced specifically for evaluation.
  • V. MANGA DATASET: Manga109 addresses the difficulty of constructing public manga datasets because manga artwork is protected by copyright.The paper identifies copyright as the most serious and intractable dataset-construction problem.
  • V. MANGA DATASET: The collection comprises previously published manga drawn by professional creators and covers a wide range of genres and publication years.Titles were selected from an archive with help from J-comi, and creator permissions were obtained.
  • V. MANGA DATASET: The dataset includes 21,142 pages, averaging 194 pages per title, with average image dimensions of 833 × 1179 pixels.The high resolution reflects the multiple frames contained on manga pages.
  • V. MANGA DATASET: Compared with eBDtheque’s 100 comic pages, Manga109 provides many more pages for large-scale experiments.eBDtheque instead supports smaller, detailed evaluations such as object boundary detection.

VI. EXPERIMENTAL RESULTS

The experiments evaluate description, localization, and query interaction using Manga109-derived frames and sketches from novice and skilled artists. The proposed method achieved the best comparative-study scores, while PQ introduced a compression–accuracy trade-off.

  • VI. EXPERIMENTAL RESULTS: The evaluation covers comparative description, localization, and large-scale qualitative studies addressing three manga-retrieval challenges.The experiments use Manga109 material and compare the proposed framework with previous methods.
  • VI. EXPERIMENTAL RESULTS: The comparative study uses 8,889 cropped frames from 10 Manga109 titles for retrieval.Frames average 372 × 341 pixels and are used because competing features are comparable within a frame.
  • VI. EXPERIMENTAL RESULTS: Localization remains challenging because frames vary greatly in size and may contain small targets alongside other objects and backgrounds.The comparative evaluation is conducted within frames rather than full pages.
  • VI. EXPERIMENTAL RESULTS: The targets range from the relatively easy Boy-with-glasses to the harder Chombo and smallest Tatoo instance.These targets are treated as ground truths, with Tatoo being the most difficult because it is small relative to its frame.
  • VI. EXPERIMENTAL RESULTS: Ten participants produced 30 query sketches, including seven novices and three skilled artists.Each participant drew all three target objects.
  • VI. EXPERIMENTAL RESULTS: In all cases, the proposed method achieved the best scores in recall@k and mean average precision.BoF and FV received almost zero scores for the small Tatoo instance, whereas the proposed method performed best overall.
  • VI. EXPERIMENTAL RESULTS: The comparative study omits approximation steps, including PQ compression, to ensure a fair comparison with the baselines.The proposed method is therefore evaluated without PQ in that comparison.
  • VI. EXPERIMENTAL RESULTS: PQ compression decreases score as quantization increases, revealing a trade-off between compression rate and accuracy.The study selects M = 16, producing a 16-byte code, and c = 8 for feature description.

B. Localization evaluation

The localization evaluation tested whether the proposed method could retrieve target instances across manga pages, using annotated windows and a standard overlap criterion. On Manga109, the method searched millions of patches in hundreds of milliseconds, though the task remained difficult.

  • The evaluation localized query-sketch targets in both a 192-page Lovehina dataset and the 21,142-page Manga109 dataset.The Lovehina set contained 69 manually annotated ground-truth windows; Manga109 comprised all 109 titles.
  • A retrieved bounding box counted as correct when its overlap with a ground-truth window exceeded 0.5.When multiple boxes were produced, at most one was counted as correct; results were summarized using mAP@100.
  • 331 ms was required to search Manga109’s 14M patches with the single-thread implementation.A parallel implementation reduced the runtime to 70 ms, and the complete EOH feature dataset required 204 MB.
  • The localization task was difficult because 138K Lovehina and 14M Manga109 candidate areas were searched for only 69 ground-truth areas.For Manga109, the first successful result appeared at rank 35, while an earlier incorrect result shared the query’s glasses characteristic.

C. Large-scale qualitative study

The large-scale qualitative study examined sketch queries and interactive relevance feedback on Manga109. Retrieval worked especially well for simple geometric shapes and showed that edge features could capture author and character-related visual characteristics, while text regions caused failures.

  • The parallel implementation averaged 70 ms for Manga109’s 21,142 images.Neighbors were computed per manga title in parallel, retaining the most similar feature from each page before merging results.
  • 347 representative sketches, each assigned a category such as “panda,” were used as qualitative queries from a public sketch dataset.
  • Retrieval succeeded particularly well when the target consisted of simple geometric shapes such as squares.This tendency was consistent with previous sketch-based image retrieval systems.
  • Text regions sometimes occupied top-ranked results, motivating future detection and removal of text areas.
  • Relevance feedback retrieved similar character faces and blush-face depictions across manga titles.The authors report that blush faces represented by hatching were retrieved from various manga titles.

VII. CONCLUSION

The paper concludes that its sketch-based retrieval system, interactive query schemes, and Manga109 dataset support content-based manga search. Experiments reported higher retrieval accuracy, reasonable localization performance, and useful sketch querying, while combining sketch and keyword search remained future work.

  • The proposed retrieval pipeline combines margin-area labeling, EOH feature description, and approximate nearest-neighbor search using product quantization.The query schemes add relevance feedback and query retouch for interactive reranking.
  • Manga109 contains 21,142 manga images drawn by professional manga artists and is publicly available to the research community.The paper describes it as the biggest manga image dataset to the authors’ knowledge.
  • The experiments verified higher retrieval accuracy than existing methods, reasonable runtime and accuracy for object localization, and useful sketch querying for manga search.
  • Combining sketch-based and keyword-based searches is identified as a promising direction for future work.
Loading 1510.04389v1…