Hacker News Reader

Comment by bbor | Hacker News Reader

Wow, fascinating! I hope I’m not the only OCR-minded soul on here that immediately started thinking of pipelines for this one could assemble from all our new DL-enabled toys… it’s a shame that “some American kid” probably doesn’t meet their contracting requirements.

One thing that kinda baffles is that it sounds like the snippets (I bet that German word is fun) haven’t been scanned(/photographed…?) yet. No matter who they contract with, wouldn’t that necessarily be step #1? Or is the scanning the part that needs contracting, and the “e-Puzzler” name was just a lil melodramatic?

For one thing, I feel like it’ll be wildly helpful that they’re on a variety of papers, not challenging like they imply. Once that and bag index have narrowed down neighbor candidates, you’ve got rules and glyphs to go off of, much less recognizable form layouts. It feels like the Vesuvius scrolls but actually tractable…

View on HN

Scanning 16,000 bags of tangled snippets does not sound that trivial to me. Surely that’s a significant problem and cost on its own.

Let’s say it costs €100 to digitize each bag, that’s only €1,600,000 significantly less than what has already been spent.

That’s an odd price. Not knowing what a “bag” means, I think 13-gallon (“kitchen”) or larger lawn clippings bag is possible.

I wouldn’t for €100 sign up to scan even an office wastebasket (6-8 gallon) bag of torn-up paper. Make it €2000 for that quantity, and we’ll start talking.

I worked in the Pentagon from 1989-1995. I handled “burn bags”, among the other classified stuff I did.

I can’t speak for what their bags are like, but ours were basically large, thick, grocery-size paper bags without handles. Thick enough that they most likely wouldn’t tear, even if they were full and mid-handled somewhat. You rolled down the top and stapled them shut.

Like these: https://live.staticflickr.com/4129/4987369106_ab71780b90_z.j...

But we didn’t shred our documents first. We just put in whole sheets and reams of paper, and we left it up to them to shred first and then burn. But then, that was 1989.

“Each bag contains between 2,500 and 3,500 fragments of torn-up pages.”

Agreed, €100 seems low to process a single bag.

16k bags with 3k shreds each is a few million pieces. You could scan 10-20, or more, at a time spreading a them over a glass sheet, putting other on top and making two pictures. Have a few people doing that and you can process a bag in a few hours. 16k bags for a team that can process 10 bags in parallel is like a year of work.

After that I bet the full reconstruction takes like a month tops with AI matching pieces.

It helps that they used bags; because if all snippets were in one bag, then combinatorially, things would be much more difficult.

n pieces residing in the same b_i, i<16501 bags can be viewed as a blocking function in record linkage. That means while comparisons are O(N^2), here N=16500 and not N=i*16500. In practice, filtering by compatible color (effectively a 2nd-level blocking function) prunes the search space further.

The simplifying heuristic (works not always, but most of the time): "assume that all snippets belong to the same bag".

One important question is how big the individual snippets are - ideally, they'd contain fractions of more than one line of text on top of each other. According to @Pebblebox (see below), “Each bag contains between 2,500 and 3,500 fragments of torn-up pages.”, which means the fragments must be large enough on average to be amenable to language model application.

Then I'd create a data structure with the color of a snippet and its lines of text (either full lines, or prefixes and suffixes at the [left/right] fringes):

  type snippet_type = record
                        snippet_color: RGBColor;
                        text_height:   integer;
                        text:          lines[1..5] of record
                                                        left:  string;
                                                        right: string
                                                      end
                      end;

A statistical or neural language model should be able to piece individual pieces together and come up with a list (sorted by likelihood) of locally probable solutions (called "trellis" or "sausage" in ASR parlance), which can be combined using a beam search.

New captcha challenge?

>Scanning 16,000 bags of tangled snippets does not sound that trivial to me.

Only because you imagine doing it by hand instead of automating the process.

Sorry, I didn't mean to imply it was trivial, but rather that it's necessary if they are to make any progress at all. I mean, right? How could one assemble a puzzle without being able to perceive the pieces?

> Or is the scanning the part that needs contracting

I assume both scanning and reconstruction would be part of the same contract.

Well that seems like problem #1, then. One is a data science/applied ML task, and the other is a large-scale, human-labor-intensive process; the best company for the latter would probably be some sort of bespoke machinery producer from the food industry, TBH.

Reply on news.ycombinator.com