How to get drawing order of objects?

[mlissner]

I'm building a tool for identifying bad redactions that look like this:

So far the tool that we've developed is working pretty well, but it has a lot of false positives on PDFs that have rectangles under text instead of on top of it. This is fine, for example, but our program identifies the gray rectangles as a problem:

A colleague of mine that's good at PDF-stuff says that the way to know if text is on top of a rectangle or under it is by looking at the "drawing order" of the PDF. My code currently uses page.get_drawings() and page.get_text("rawdict"), but I don't see anything about the drawing order in either of those.

Is there something I'm missing or a trick I should be using?

Thank you!

[JorjMcKie]

The observation of your colleague is correct:
For drawings, I have built my own variant of MuPDF's "trace device". This is a vehicle that scans a page's appearance building source (which is the /Contents' object in PDF). My "drawings device" subselects the drawing relevant commands ... and ignores everything else, like text, images etc. On the other hand, variants of method page.get_text()` that are capable of extracting mixtures of text and images, deliver the right sequence for those two categories ... but do not deliver drawings at all.

I have been thinking about all this a lot, but I have no solution at hand yet.

Your use case is a valid, but not a frequent one if you allow this comment. You could take a look at the trace device's output directly. This is XML. I have attached an example for you. It contains a PDF with a rectangle upon which some text is written. The xml file has been created by mutool trace text-oc.pdf > text-oc.xml under Windows. The trace outputs to the terminal which is being intercepted by parameter > text-oc.xml.

Looking at the XML source you can easily see that the drawing comes before all the text:

<document filename="text-oc.pdf">
<page number="1" mediabox="0 0 595 842">
<set_default_colorspaces gray="DeviceGray" rgb="DeviceRGB" cmyk="DeviceCMYK" oi="None"/>
<layer name="ocg2"/>
<group bbox="35 35 365 345" isolated="0" knockout="1" blendmode="Normal" alpha="1">
    <fill_path winding="nonzero" colorspace="DeviceGray" color=".5" alpha=".5" transform="1 0 0 -1 0 842">
        <moveto x="45" y="507"/>
        <lineto x="355" y="507"/>
        <lineto x="355" y="797"/>
        <lineto x="45" y="797"/>
        <closepath/>
    </fill_path>
    <stroke_path linewidth="1" miterlimit="10" linecap="0,0,0" linejoin="0" dash_phase="0" dash="3 1" colorspace="DeviceRGB" color="0 0 1" alpha=".5" transform="1 0 0 -1 0 842">
        <moveto x="45" y="507"/>
        <lineto x="355" y="507"/>
        <lineto x="355" y="797"/>
        <lineto x="45" y="797"/>
        <closepath/>
    </stroke_path>
</group>
<end_layer/>
<layer name="ocg1"/>
<fill_text colorspace="DeviceGray" color="0" transform="1 0 0 -1 0 842">
    <span font="Ubuntu-Italic" wmode="0" bidi="0" trm="11 0 0 11">
        <g unicode="D" glyph="39" x="52.2" y="781.748" adv=".691"/>
        <g unicode="e" glyph="72" x="59.801004" y="781.748" adv=".518"/>
        <g unicode="r" glyph="85" x="65.499" y="781.748" adv=".372"/>
... and so on ...

The commands between <fill_path...> and </fill_path> draw the inner part of the rectangle, between <stroke_path ...> and </stroke_path> you will find the commands for the rectangle's border.

A few more notes:

• the fact that the fill path and the stroke path belong together and describe the "same" rectangle must be detected.
• the fact that one "moveto" and three "lineto" commands actually draw a rectangle must be detected by looking at e.g. the coordinates accompanying them.
• coordinates are given as document (i.e. PDF in this case) coordinates. The associated transformation matrix is given by parameters like transform="1 0 0 -1 0 842". Which in this case would correspond to fitz.Matrix(1, 0, 0, -1, 0, 842). So the point fitz.Point(45, 507) given by <moveto x="45" y="507"/> is actually the point fitz.Point(45, 507) * fitz.Matrix(1, 0, 0, -1, 0, 842) = fitz.Point(45.0, 335.0). Please note here, that PDF draws rectangles by starting at the lower left corner in an anti-clockwise manner. Only 3 lines are drawn, but because of <closepath/> we know that last and first point of the whole path must be connected by some imaginated line, too.

text-oc.zip

[JorjMcKie]

You made me thinking about a way out of all this. How about the following:

• Create a new page method that returns all bboxes on the page, each one accompanied by a type indicator, like "text", "image", "fill-path", etc.
• The order of bboxes in that list is as encountered in the page appearance source.
• That list could then be matched with bboxes contained in page.get_drawings() and page.get_text(), etc.

Then you would be able to tell whether some text bbox is contained in some drawing (or rather "fill-path") bbox encountered further down in the bbox list ...

Your reaction?

[mlissner]

These solutions sound pretty good to me, but since we're running this on millions of PDFs (and AWS lambda charges by the millisecond), I'm thinking about performance too. A couple thoughts:

1. Your approach of creating a new page method would be fine. I could definitely work with it.

2. When I set out to fix my issue, my assumption was that the get_drawings and get_text methods would include a draw_order integer for every item returned. My code currently gets drawings, then text, then looks for overlaps by bbox, so if there was a draw_order int associated with every bbox from both drawings and text, I could easily compare a drawing with a text bbox, note that they intersect, then compare their drawing order. Something like:

   drawings = page.get_drawings()
   rectangles = [item[1] for item in drawing["items"] if item[0] == "re"]
   blocks = page.get_text(
       "rawdict",
       # Use flags for performance boost, to not return images
       flags=fitz.TEXT_PRESERVE_LIGATURES
       | fitz.TEXT_PRESERVE_WHITESPACE
       | fitz.TEXT_DEHYPHENATE,
   )["blocks"]
   for block in blocks:
       bad_redaction = text_block_under_rectangle(block, rectangles)
   

   And in text_block_under_rectangle, there would be:

   def text_block_under_rectangle(block, rectangles):
       # (Pretend this is doing chars, not blocks, for simplicity)
       for rectangle in rectangles:
           if not block & rectangle:
               # They don't intersect, check the next rectangle
               continue
           if block.draw_order < rectangle.draw_order:  # <-------------------- HERE'S THE NEW THING
               # The text is drawn first, i.e., is under the rectangle
               return True  # it intersects badly
       return False  # it's fine
   

   This general design would work really well for me, and seems like it'd be a logical upgrade to the returned values from get_text and get_drawings, but I have no idea what the inside of PyMuPDF looks like. I'm guessing it might be nice not to have new method signatures to document and support and that adding a new attribute to existing results would be easier documentation- and upgrade-wise.

3. When I didn't find draw_order in the returns from get_drawings or get_text calls, my next thought was to see if there was an option for get_text that'd return it, so I looked at the docs there. Unfortunately nothing was there either, but if I could pass something like flags=fitz.INCLUDE_DRAW_ORDER or get_text("superrawdict"), that'd be spectacular.

Thank you for your interest in adding this feature. I'm useless at C, but if I can help with design or in other ways, this is an important feature for our tool, so I'd be happy to do whatever I can.

[mlissner]

Oh, one other thing: I'm sure you understand my use case, so don't feel obligated to reply to my suggestions above if you agree or think differently or whatever.

Really, whatever API design you come up with will be great, and surely better than my ideas.

I think my top goals would be performance, not ergonomics or backwards compatibility.

[JorjMcKie]

Oh, one other thing: I'm sure you understand my use case, so don't feel obligated to reply to my suggestions above if you agree or think differently or whatever.
Really, whatever API design you come up with will be great, and surely better than my ideas.
I think my top goals would be performance, not ergonomics or backwards compatibility.

No worries, these are good ideas. And as I wrote, I know there is some feature gap and it does bother me since some time.
There have been several users asking for how to detect that text is hidden - which is very similar to your request.
While there are limit as to how precise I can get without rewriting a whole PDF viewer, I think there are ways to definitely get better.

To your and my ideas:

• The get_text() method collection is based on a MuPDF object, called TextPage. This object does the actual extraction from a doc page (not necessarily PDF! Could be XPS, SVG, whatever) and then puts that to some intermediate place. So this is the maximum amount of info I can ever get with any of the get_text() options. Turns out that a few things simply are not there: text opaqueness, hiddenness, some other things. There is nothing I can do to add something here. Especially not a text / image extraction order number.
• The drawings extraction is exclusively my own making - not based on TextPage (but of course based on MuPDF low-level code). I could certainly extend this to include a sequence number.
• Similarly I have written my own text extraction method, page.get_texttrace(), also not based on TextPage. This is somewhat similar to get_text("rawdict") but lacks some comfort compared to that. On the other hand, there is more information, like text alpha and more. Could also be extended by a sequence number.
• I have just jotted down a new page method that returns all bboxes of a page, whether caused by drawings, text or images. Together with information what type of object is inside the bbox.

So overall I am pretty sure I can come up with something usable.
As far as performance is concerned: This is my personal crusade anyway. All methods mentioned are written in C with fairly thin Python wrappers.
If you are looking for a top performance drawings extraction BTW, use page.get_cdrawings() instead of page.get_drawings(). Delivers (almost) the same, but is 3 times faster.

[mlissner]

Thank you Jorj! It sounds like you're actively thinking and maybe working on this and all those thoughts make sense.

I'm not on a tight timeline for my project. Is my impression correct that I should hang tight for some sort of solution on this? Sounds like you're about to create something amazing in no time at all?

[JorjMcKie]

😂
Hard to comment on this. Let me give it a try nonetheless:
Yes, I am interested in finding a solution. Yes, there are promising options to pursue.
No, the bbox list is not quite there yet, but still extendable.
Overall I am optimistic.

[JorjMcKie]

Question:
Can you let me have that example file / page? Confidentiality assured, you can send it to my e-mail.
I would like to test a few things with it.

[mlissner]

Absolutely. It's here: https://github.com/freelawproject/x-ray/blob/38-draw-order-analysis/tests/assets/opaque_box_under_text.pdf. Our work is all in the open, so our code and files are easy to share.

[JorjMcKie]

Thanks for the file. I modified it a bit such that there exists a problem (covered) word. Then I wrote a script that uses my new numbering feature to determine if any text is covered by some drawing.
If coverage is detected, the respective word and drawing are marked by colored borders.
Good news: so far already works. Here is your modified file/page:

I just arbitrarily picked word "approval" and overlaid it with a black rectangle - but for demo purposes let the transparency be 0.5. This also is a point for discussion...!

Then let my script eat that file. The output:

The green border is the drawing rectangle, the red one the covered word. You see that the words in the table are correctly found to be harmless ...

[JorjMcKie]

Some comments / questions:

• if you are interested to do testing, please give me your platform (OS, Python version plus bitness) so I can make a wheel for you
• what should happen with drawings that are not 100% opaque? Ignore?
• I used "words" output to inspect text. I would argue this should be sufficient - as opposed to single characters. As I am counting (significant) partial overlaps, the level of detail achieved by this approach should be ok. The "words" output of get_text() is very much fast then "dict" or even more so "rawdict".

[JorjMcKie]

One more comment in response to a remark on your repo home page:
To minimize rectangles encircling text use fitz.TOOLS.set_small_glyph_heights(True) - early enough in your script, preferrably immediately after import.
This will affect all text-related methods (get_text(), search_for(), etc.). Each text bbox should then be computed to be of height fontsize.

You will see the difference in my last posted image: the red rectangle was made using this setting, the green one with the standard setting.

[mlissner]

• if you are interested to do testing, please give me your platform (OS, Python version plus bitness) so I can make a wheel for you

Absolutely. I'm on 64 bit Linux, with Python 3.8.10

• what should happen with drawings that are not 100% opaque? Ignore?

x-ray ignores any drawing that is transparent, yes, because in that case it's probably a highlighter.

• I used "words" output to inspect text. I would argue this should be sufficient - as opposed to single characters. As I am counting (significant) partial overlaps, the level of detail achieved by this approach should be ok. The "words" output of get_text() is very much fast then "dict" or even more so "rawdict".

I did it with "rawdict" in x-ray because I wanted to know exactly which characters were redacted and found that in some cases a word was partially redacted. I found the performance of rawdict to be pretty OK if you excluded images (as in my example above).

I am also calculating the intersection percentage in x-ray. So if the intersection is less than some threshold for a letter, I figure it's mostly visible and therefore not part of the failed redaction. I found that sometimes the bottoms or tops of letters would be outside of the redaction rectangle. and having that configurable threshold helped. I think it's 80% intersection is considered a redacted character right now?

You can see this here: https://github.com/freelawproject/x-ray/blob/main/xray/pdf_utils.py#L85

To minimize rectangles encircling text use fitz.TOOLS.set_small_glyph_heights(True) - early enough in your script, preferrably immediately after import.

Woah. I'll have to play with that, thank you for reading our docs and mentioning that. I'm pretty happy with the threshold approach above, but, well, this does seem more elegant!

[JorjMcKie]

Woah. I'll have to play with that, thank you for reading our docs and mentioning that. I'm pretty happy with the threshold approach above, but, well, this does seem more elegant!

It actually is independent from the percentage approach: even a character with minimized bounding box could be partially contained / covered by a drawing, couldn't it.

Please find your wheel here. I hope you can access it. It is wrapped in a ZIP called "linux-wheel3x".
Drop me a note if there are problems.
Here is the script I have been using. I have modified it in the meantime to ignore fill path drawings with fill_opacity < 1
findcovers.zip
.

[mlissner]

This is great and I was able to download everything. I haven't had time today to try it out, but I'll be back soon with my results. Looking at your script though, it all seems about like how I'd imagine, more or less. Thank you and have a great weekend!

[JorjMcKie]

I have done more work on this:

• page.get_drawings() now also returns a paint sequence number - so no need to look it up somewhere else.
• my homegrown internal text extractor page._get_texttrace() now also has a paint sequence number. As mentioned, its overall comfort is a bit slender, but sufficient for your purposes I suppose. It should come close enough to your preferred use of "rawdict".

I made a new wheel with those changes. To test the functionality, you might start with this script:
findcovers2.zip

As you will see, it is very much shorter - and also much faster than the other solution. It also requires no use of page.get_bboxlog(), because sequence numbers are delivered by drawings and text extraction directly.

[JorjMcKie]

Update on the wheel link. The other one had been created wrong by Github Actions.

[mlissner]

Sorry for the delay. My org's work is getting a lot of press this week and I wear the developer and the director hat, so I've had to respond to it. But I will absolutely be getting back to this. Just wanted to make sure you knew I hadn't just wandered off. This, generally, looks great.

[mlissner]

I was finally able to test this today and rewrite my code to use it. A few responses; sorry to take so long:

1. Just a comment. Something that made my code more complex was that attributes weren't where I needed them:

   • I wanted the seqno to be on get_drawings()[n]["items"][n] (the paths) not get_drawings()[n] (the shapes)
   • I wanted the seqno to be on _get_texttrace()[n]["chars"][n] (the chars) not _get_texttrace()[n] (the spans)
   • I wanted color attributes to be on chars and paths, not on spans and shapes.

   I think this probably just means I want the PDF standard to be different, but thought I'd mention it.

2. Small thing, but will _get_texttrace be promoted into a public method?

3. The last thing I noticed is that in my tests, the performance of using _get_texttrace is about 3× worse than when I used this:

   blocks = page.get_text(
       "rawdict",
       # Use flags for performance boost, to not return images
       flags=fitz.TEXT_PRESERVE_LIGATURES
       | fitz.TEXT_PRESERVE_WHITESPACE
       | fitz.TEXT_DEHYPHENATE,
   )["blocks"]
   

   I think the reason is not _get_textrace itself, but that when I use _get_textrace I have to check for intersections of every char. With get_text, I can begin by checking if a whole block intersects, if so, then check the line, then the span, then, finally, the char. This drastically reduced the number of intersections I had to check from thousands per page to a couple dozen.

   Since _get_textrace returns spans, one easy fix (maybe) would be for it to provide a bbox of the span. I don't think there's enough info returned presently to get that. That'd surely help.

   The other fix that comes to mind is adding the sequence number to the spans in the results of the get_text calls. I don't know if that's practical, but I think it would help since I could work with blocks and lines again.

Anyway, I've got a working method now, so that's good. Thanks again for all your help and efforts! I'm excited to find out how many court records are revealing things they shouldn't be, but I'm going to hold off on running that to see if you have thoughts about performance, since lamba charges by the millisecond.

---

PS, if you're curious, this is the news that kept me from returning to this. It was on the cover of the WSJ. Kind of a big deal for us, but sorry it impacted this discussion. I doubt this project will do as well, but I do hope to get some press for it and try to get some reforms to protect people's privacy.

[JorjMcKie]

Thanks for your detailed feedback!
Never mind for the "delay": I have been very busy anyway preparing for support of MuPDF v1.19.0 which came out a day ago or so.

this is the news that kept me from returning to this

Very interesting! I feel a little proud that my baby plays a role in your work 😉!

As per which information piece can be found on which level:
I am generally aiming to provide data on the highest possible level in a hierarchy of course. E.g. each character in a span is in that particular span, because it shares that span's characteristics, as there font, fontsize, color and more.
There is some background to this though: MuPDF walks through the page's "source code" (the /Contents object) in a sequential manner - no surprise here.
But: there is no guarantee at all, that the PDF creator has coded his text characters in the same sequence as they would appear in some PDF viewer. In fact, there are up to N! different ways to code an identically looking PDF page (N = number of characters on it). This is possible, because every text piece is accompanied by position information, which Adobe Acrobat et al. use ... and thus produce the same view of the content.

This "feature" is exploited by some PDF creators as a simple protection against copy / paste, because most viewers will then deliver garbage. In other cases, different fonts, colors, ... are coded in separate code chunks for coding efficiency. All this will cause different spans in MuPDF and consequential loss of "natural" reading order in text extractions.

I will however see to include a span bbox in page._get_texttrace(). Shouldn't be a big deal. What kept me from doing this, is the work associated with calculating the correct value when the writing direction span["dir"] is not equal to (1, 0) (horizontal, left to right). If the writing angle is not an integer multiple of 90°, things are getting a lot nastier: compute the non-rotated bbox, then multiply each of its corners with the associated rotation matrix (delivering the quad), then build the rectangle hull of that quad.
A simple solution might be to ingore non-multiples of 90° and simply deliver what comes out for (1,0). For your use cases presumably sufficient.

What makes me hesitate officializing that method is its currently still somewhat experimental state ... but I do not loose that goal out of my site.

[mlissner]

This all makes sense. Thanks for the details. That's really dumb about the way PDF creators scramble to protect copy/paste. Totally makes sense though now that you've explained it.

A simple solution might be to ingore non-multiples of 90° and simply deliver what comes out for (1,0). For your use cases presumably sufficient.

Yep, that'd do it. I don't think I've ever seen angled text in legal docs. The rest of the algorithm does sound kind of fun though. :)

If you can provide a bbox of the spans, that'd be great and would be a fine solution that should help or fix the performance issue.

What's stopping you from adding seqno to the get_text calls? That feels like a better solution to me, since it uses a public method.

[JorjMcKie]

What's stopping you from adding seqno to the get_text calls? That feels like a better solution to me, since it uses a public method.

I'll give it another try definitely. It's encapsulated MuPDF code though - which I don't want to replace as a whole. All I could do (and that'll be my try), is doing another call to make that bbox list, scan through and match it with with get_text output.
Obviously would be a worse performance than today, but might still be ok for you. Only measurements can tell the difference here. If that path is fine, I would make inclusion of sequence numbers an option for the get_text() method.

That's really dumb about the way PDF creators scramble to protect copy/paste.

Sure. Only the lazy ones do it that way. There are (at least) two more elegant alternatives:
(1) do not write text directly at all, but instead simulate the single characters by drawing them: an "o" is a little circle, a "D" is a "|" combined with a left-open semicircle, and so on.
(2) use a font with a secret mapping from the character codes to their visual appearances (called "glyphs"): you will see a character all right, but you will always text-extract unknown / undefined character unicodes: the PDF-internal text command says "write glyph 0x4711" - and this is what text extractions will deliver. There is no way of tracing back to the intention to write character "D".

[JorjMcKie]

@mlissner - latest news:
I am making progress with v1.19.0. as per your requirements, I looked again the MuPDF code behind get_text() and determined, that there is no way to squeeze in some like a sequence number.
What therefore did, is computing a "bbox" for the spans returned by page._get_texttrace() - in addition to "seqno". I used the simple assumption for this: the bbox is correct for writing direction (1, 0) only.
So the span["bbox"] is the union of all char bboxes in the span.

Question for you:
Currently, the items in the span["chars"] list look like (unicode, glyph, (origin.x, origin.y), width). In order to speed up your programs, I think it makes sense to include the character bbox instead of the width. This ...

• is no extra effort because the char bbox must be computed anyway
• saves your scripts the effort to compute the char bbox

If you agree, the character items would look like (unicode, glyph, (origin.x, origin.y), (x0, y0, x1, y1)).
To check character intersections, your effort would then be along the lines:

• check whether fitz.Rect(span["bbox"]) intersects the drawing
• if yes, check which character's fitz.Rect(char[3]) are intersecting.

I also think I should always compute the character heights as if fitz.TOOLS.set_small_glyph_heights(True) had been specified. This seems adequate for such a technical method.

[mlissner]

That sounds like a great way forward, yes, thank you!

[JorjMcKie]

Thanks for your prompt answer.
I will proceed as proposed then.

[JorjMcKie]

@mlissner -
Here you can find my newest version 1.19.0.

There are the following changes:

• Text tracing is now a public method - I finally dared to do it 😎 - page.get_texttrace().
• The proposed recent changes are included: text spans and each character now have bbox information - implemented as a tuple of 4 floats, representing the rectangle coordinates x0, y0, x1, y1.

Official publication of v1.19.0 is still a few days away, but the features you are presumably interested in will not be touched anymore. I will now focus on the new integrated Tesseract OCR support and get rid of remaining rough edges there.
But please do continue to ask questions and express admonitions you may have on coverage detection.
Our discussions have lead to a new exciting capability, which I am sure many people are interested in.
Thank you again for your contribution!

Here is a ZIP containing your example PDF with some added black drawings covering text.
I also included a script that discovers and reports this type of problem.
findcovers.zip
Over the next few minutes I will also upload updated documentation to this file. The official version update on Read The Docs will to wait until v1.19.0 is out.

[mlissner]

Well, that is just perfect. Thank you so much for all the work you've done here. I'll be back in the Show & Tell forum once this gets rolled out and we get it the publicity it deserves. If you want a shout out somewhere, we can probably do that. Send me an email at mike@free.law if you want.

I updated my code to use the new wheel and it's back to the speed it was before. I think I'm all set here. I'll wait patiently for the release!

Thank you!

[JorjMcKie]

Thank you very much for the feedback!
I am glad I could help your important work a bit.
Please do not hesitate to drop me a note if you see anything I could do.